Device for sorting two-dimensional data array (variants)

FIELD: computer science.

SUBSTANCE: device has block of registers of first memory, block of registers of second memory, block for controlling reading of columns, block for controlling reading of rows, block for controlling reverse recording; according to second variant, device has same elements excluding block for controlling reverse recording. Third variant of device is different from second variant by absence of block for controlling reading of columns, and fourth variant of device is different from second one by absence of block for controlling reading of rows.

EFFECT: higher efficiency.

4 cl, 9 dwg

 

Device for sorting a two-dimensional array of data belong to the field of computer hardware, namely, devices for the processing of numerical data, and are designed to permutation of rows and columns of a two-dimensional array data, presented in the form of a matrix and stored in the memory of the computing device.

It is known Device for the study of Petri nets” RF patent No. 2024057 designed to sort the data and contains the control unit, register initial marking, shaper burst, unit assignments topology graph elements OR, the shaper of a single pulse with a time delay, two groups of elements And the decoder, the comparison circuit, the memory block, the delay elements. The memory block is common to analog and the claimed invention.

Also known Device for sorting permutations” RF patent No. 2012054 intended to be formed in arbitrary sequence of permutations, and can be used to solve combinatorial problems. The device includes two decoder, two multipliers, two elements OR a group of n adders, units of the division, two groups of n registers, three groups of delay elements and group elements I. General characteristics for analogue and proposed technical solutions are two groups of the n register of the century The disadvantage of this device is that the object of permutations is a one-dimensional array data.

This device is the closest to the technical essence and the achieved result to the claimed invention and is taken as a prototype.

Device for sorting a two-dimensional array of data belonging to a group of inventions and possessing the greatest number of essential features, contains a block of registers of the first memory block of registers of the second memory block management record in the registers of the second memory, connected to the first mn inputs with the corresponding mn outputs of the unit registers of the first memory, and mn outputs with the corresponding mn inputs of the unit registers of the second memory, the control unit reading the columns corresponding to the n outputs of which are connected with the second n inputs of the control block entry in the registers of the second memory, the control unit reading the rows corresponding to the m outputs of which are connected with the third m inputs of the control unit account in the registers of the second memory, the control unit is write-back, coupled mn inputs with the corresponding mn outputs of the unit registers of the second memory, and mn outputs with the corresponding mn inputs of the register unit, the first memory.

The unit registers of the first memory contains mn first registers storing information units, each of which C is t one of the m disjoint sets, containing n these registers, and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m of these registers, and representing one of the n columns of the two-dimensional data array, the outputs of data registers connected to respective inputs of the control block entry in the registers of the second memory.

The unit registers of the second memory contains mn second registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers, and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m of these registers, and representing one of the n columns of a two-dimensional array of data inputs of the data registers connected to respective outputs of the control block entry in the registers of the second memory.

The control unit reads lines contains m sub-blocks, each of which contains m first logic conjunction, the first inputs of which are the input device to specify the line number, the second inputs are the input devices of the first clock pulses, the first logical disjunctor to m inputs of which are connected the outputs of the first logic conjunction this subunit, and the output is the output of the data subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

The control unit reading the string contains the control block input line numbers connected m2outputs with corresponding m2a control unit reading out the row also contains m sub-blocks, each of which contains m first logic conjunction, the first inputs of which are connected to the corresponding outputs of the control unit input line numbers, the second inputs of which are the input devices of the first clock pulses, the first logical disjunctor to m inputs of which are connected the outputs of the first logic conjunction this subunit, and the output is the output of this subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

The control unit input line numbers contains m (number of rows of a two-dimensional array) of decoders line number, the inputs of which are the device inputs for external signals, and m outputs, each of them connected to respective m inputs of the control unit reading lines, namely m first inputs of the first conjunction corresponding sub control unit reading the string.

The control unit reads column contains n sub-blocks, each of which contains n second logic conjunction, the first inputs of which are the input device to specify column numbers, Deuteronomy the e inputs are the input devices of the second clock pulses, the second logical disjunctor to n inputs of which are connected the outputs of the second logic conjunction this subunit, and the output is the output of this subunit, and connected to the corresponding input of the control block entry in the registers of the second memory.

The control unit reads column contains the control block entry of numbers of columns connected n2outputs with corresponding n2a control unit reading the columns, also contains n sub-blocks, each of which contains n second logic conjunction, the first inputs of which are connected to the corresponding outputs of the control unit input column number, the second inputs of which are the input devices of the second clock pulses, the second logical disjunctor to n inputs of which are connected the outputs of the second logic conjunction this subunit, and the output is the output of this subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

The control unit entering column contains n (the number of columns of a two-dimensional array) of decoders column number, the inputs of which are the device inputs for external signals, and n outputs, each of them connected to respective n inputs of the control unit reading the columns, namely with the first n inputs of the second conju the Ktorov corresponding sub control unit reading the columns.

The control block entry in the registers of the second memory contains a set of mn third logical conjunction, each of which corresponds to one and only one of the registers of the register unit, the first memory and, accordingly, refers to a particular row and a particular column of a two-dimensional data array, the first inputs of which are connected with the corresponding output of the control unit reading lines, namely the output of the corresponding first logical disjunctor, the output of this k-th logical disjunctor connected n third logical conjunction corresponding to a given k-th row, the second inputs of the third logic conjunction connected with the corresponding output of the control unit reading the columns, namely, the output of the corresponding second logical disjunctor, the output of this 1 second logical disjunctor connected m third logical conjunction assigned to the 1st column, the third inputs of the third logic conjunction connected to the outputs of the respective registers of the register unit, the first memory also includes a third logical disjunctor, mn inputs of which are connected the outputs of the third logical conjunction also contains a set of mn fourth logical conjunction, each of which corresponds to one and only one is in the register of the register unit, the second memory and is connected by its output to one input of the corresponding register, the first input of the fourth logic conjunction are interconnected and connected to the output of the third logical disjunctor, the second input of the fourth logic conjunction each k-th line are interconnected and connected to the corresponding bus k-th of the first clock pulse, the third input of the fourth logic conjunction each 1-column are interconnected and connected to the corresponding bus 1 second clock pulse.

The control unit write-back is executed in the form of a set of mn-fifths logical conjunction, each of which corresponds to one and only one of the registers of the register unit of the second memory, the first input of the fifth logic conjunction are interconnected and are the input devices of the second recording signal, a second input connected to the outputs of the respective registers of the register unit of the second memory, and outputs connected to respective inputs of registers of the register unit, the first memory having the same number of rows and columns, and data registers of the register unit of the second memory.

The essence of invention is as follows.

In the matrix registers of the first memory recorded information. The objective of the invention is to realize a given permutation of rows and/or columns of the matrix. For example, to transpose the rows and the table is subjected to the following binary matrix

If you carry out the following permutation:

you get transformed matrix:

For each row and column of the matrix, which is a two-dimensional array of data and recorded in the registers of the first memory, the external impact is given a corresponding number. The nature of the impact can be different, for example, can receive appropriate signals from an external device interfaced with declare, or be specified by the user (operator) by pressing buttons or switches.

The inputs of the control units reading serves polling sequence of pulses of two packages, one for rows and columns or one bundle only rows or only columns (truncated variants of devices). One pulse is supplied by a separate bus simultaneously on all columns (rows), with permission to read this column (row) is performed if the number of the pulse coincides with the set number for this column (row). In the permission to read the columns (rows) are not in the order of the columns (rows) in the matrix and in the order specified for them.

In the device, in which the permutation of both lines and columns, the columns oprative is raised within one survey line. (May be, and Vice versa.)

In each cycle, the reading is carried out only from one single register through schema matching (logic conjuncture), which were permissive signals. The outputs of all of conjunctural going on the diagram OR. The signal with its output fed to the entry in the registers of the second memory. Using this signal to record information in a single case only if filed permissive signals. Permissive signals are first and second clock pulses, with which also polled and the registers of the first memory.

Due to the fact that reading from the first memory is performed in the order specified numbers of rows and columns, and the entry in the second memory is in the order of rows and columns in the matrix, in the registers of the second memory, the information is sorted.

Read information unit having a first memory coordinates <i, j> and set the values of the new coordinates <t, s>, corresponds to the second memory register having coordinates <t, s>. Thus in the second memory is an array, which implemented the permutation of rows and columns of the original matrix. This result is ensured by the fact that the reading of information is performed in order of increasing (decreasing) numbers of rows and columns specified from the outside, and the entry in the second memory is performed in order of increasing (decreasing) numbers actually registers of the second memory.

Upon completion of the transfer of all information the main memory can be reset to zero, and the information can be transferred in parallel from the registers of the second memory into the registers of the first memory having values of row and column numbers that match the numbers respectively of the row and column registers of the second memory. In this case, the new configuration of the array is in the first memory, i.e. in the first memory is a two-dimensional array in which rows and columns are interchanged, which is the result expected from the use of the invention.

As units of information can be not only a binary number, and other data. As a two-dimensional array may be a relational database table, row records, and the columns are the attributes of the records. At intersections are attribute values that correspond to specific objects (records) in the database table. The value of a particular attribute for a separate entry and is a unit of data stored in one register.

It is not always necessary to sort the rows and columns. For example, when working with the database may be a need to swap entries, then the unit should carry out only the permutation of rows. On the contrary, it may be necessary to swap the attributes, then the device must be switched tol is to the columns.

In this regard, the group of inventions included the cases in which there is either a control unit reading the columns, or the control unit reading the string.

Also includes a variant, in which there is reverse overwrite the information in the array of block registers of the second memory block registers of the first memory. In this case prestavlenny the array remains in the second memory. The output in this case are the outputs of the registers of the second memory. In this embodiment, the device is a control block write-back.

Variants of execution units running reading rows or columns is the presence or absence of data blocks control blocks numbers of rows or columns. In the absence of such blocks from an external source serves the control signals directly to the control units reading rows or columns. If the device is performed by control units enter the number of rows and/or columns, there may be some embodiments of decoders row number or column.

As the decoder can be used a set of m (for rows) or n (for columns) two pin switches, the inputs of which are energized and the outputs are the outputs of the decoder.

Also as a decoder can be used mnogo the final switch, on which input voltage, and m (for rows) or n (for columns) outputs are the outputs of the decoder.

Also as a decoder can be used in binary-decimal Converter (decoder), the inputs of which a binary combination corresponding to the line number (column)and m (for rows) or n (for columns) outputs are the outputs of the decoder.

The decoder can be made of a binary counter, the input of which is applied the pulse sequence, and the binary-decimal decoder, the inputs of which are connected to the outputs of the counter, and m (for rows) or n (for columns) outputs which are outputs of the decoder.

The first and second clock pulse signals reset registers, the second recording signal (reverse) may come from an external device, with which is associated a device for sorting a two-dimensional array data, and can generate built-in device synchronizer or block the formation of clock pulses.

Figure 1 shows the functional diagram of the device, here 1 - control input line numbers, 2 - control unit for reading lines, 3 - unit registers the first memory 4 is a control block entry in the registers of the second memory, 5 - unit registers the second memory 6 to the control unit, write-back, 7 - control unit scity is the W column, 8 is a control block entry of numbers of columns, 9 - synchronizer. Shows the complete configuration of the device, for clarity, the control units enter the numbers of rows and columns issued from the control units reading columns and rows. The thick lines are the common bus, containing several individual compounds. So the bus between blocks 6 and 3 contains mn individual channels of the transmission signals, the bus between blocks 2 and 4 has m connections, the bus between 7 and 4 contains n connections, the bus is between 1 and 2 contains m2connections bus between 8 and 7 contains the n2connections between blocks 4 and 5 - mn compounds, between 5 and 6 and between 3 and 4 for mn compounds. Output 3 unit 9 signal reset unit 3, output 4 - second recording signal (reverse), with output 5 signal reset unit 5.

Figure 2 shows a functional diagram of the unit registers of the first memory 3 with blocks of the input control line numbers 1 and column 8, respectively, with control units read row 2 and column 7, respectively, and the fragment control unit entry in the registers of the second memory 4. Blocks the input control rooms and control reading of the disclosed only for columns (7 and 8), similar blocks for rows (1 and 2) have the same design. Here 10 - third logical elements, And (conjuncture)belonging to the control block entry in d is of Istria second memory 4, 11 - first registers storing information units, 12 - subunits control the reading of columns included in the block 7, the number equal to the number of columns 13 - second logic elements OR (disjuncture)having n inputs, 14 - second logical elements, And (conjuncture), 15 - decoders column numbers, 16 - third logical element OR (disjunction). Pin numbering for items 11 and 10 are shown only for the elements in the top row in the left column. The rest of the elements 11 and 10 it is the same.

As mentioned above, the blocks 7 and 8 are disclosed only for the columns, similar blocks for rows 1 and 2 have the same design. Therefore a complete analog of the first logical conjunction, not shown in figure 2, are the elements 14, and a complete analog of the first logical disjunction are elements 13.

Figure 3 presents the block diagram of the registers of the second memory with the second fragment of the control block entry in the registers of the second memory and the control unit is write-back. Here 17 - fifth logic elements And belonging to the control unit, write-back, 18 - registers storing information units, 19 - fourth logic elements And belonging to the control block entry in the registers of the second memory 4. Pin numbering for items 18 and 17 are shown only for the elements in the top row in the left column. The rest elements 18 and 17 it is the same.

4 shows a functional diagram of the synchronizer.

Figure 5 shows four different scenarios decoder column number (string).

Figure 6 presents the timing diagram of the operation of the device. On the fourth from the bottom of the chart corresponding to the first signal recording, the shaded square corresponds to the presence of units in this read register, and not shaded - zero (for the case of processing a binary matrix).

The device operates as follows.

Let the memory device is used for recording a two-dimensional binary array, a unit of information which is recorded in a single register is a logical zero or one. Let the selected option, in which you reposition both rows and columns and is reverse overwrite the result of the conversion from the second memory into the first.

In the initial state of the registers in the first memory 11 recorded some information in the form of a two-dimensional array. Topologically the register unit 3 is a two-dimensional matrix consisting of n columns and m rows (figure 2). Registers 11 are logic electronic elements on the basis of the trigger, designed to store a logical zero or one (in the form of certain levels of electrical voltage). The registers 11 and 18 are arranged so that when under the che unit to the input 1 of the register is set in the zero state, i.e. at the output 3 is a logical zero. When the supply unit to the input 2 - output 3 is set to a logical unit.

Signals record the original information in the registers 11 in figure 2 are not shown, but it can be done by the second inputs of the registers 11 through the scheme, OR.

The first input register 11 and register 18 (Fig 3) signal installation at zero. In the initial state it may be formed when the device is switched on or supplied from an external device before recording array.

The clock pulses are missing, so the inputs 3 and 2 items 10 - a logical zero and therefore their outputs are also zero (figure 2). Accordingly, the first signal recording is missing (or rather, has a value of zero). All signals on the inputs of the elements 19 are equal to zero and the 2 inputs of all the registers 18 goes to zero (figure 3).

With outputs 3 elements 17 to the inputs of 2 elements 11 are zeros, therefore, the registers 11 maintain their status.

The inputs of the control blocks entering column 8 and row 1 (figure 1), respectively, served number of columns and rows. In the initial state at the inputs of the decoders 15 (figure 2), which are blocks of 8 and 2, signals are absent. Respectively to the first inputs of the logic elements And (conjunctio) 14 is a logical zero and their outputs are also logical zero, and, consequently, the outputs lo the practical elements OR 13 is also a logical zero. A similar pattern is present for reading rows where the first logical conjuncture correspond to elements 14, and the first logical disjuncture correspond to items 13 (figure 2 are not shown completely, we are talking about the m outputs of the block 2, which are fed to the inputs 3 items 10).

The inputs of the decoders 15 (similarly for row - m input block 1) are in some way signals corresponding to the numbers of columns (rows), next row down and assumes full analogy with the columns. Signal number column indicates the circuit for each element 15 of one of the tumblers (case 1) figure 5). When this input is selected, the element 15 is supplied with the electric signal corresponding to the signal parameters for the logical unit. Case 2) (figure 5) is similar, but here the n switches replaced with a single switch on the n positions. Case 3) suggests the emergence of the k inputs of the element 15 external signals that represent binary combination equal to the specified number in binary code. This code may be supplied from an external device, which can control the operation of the device in question. Binary-decimal decoder 34 converts the binary code into a decimal, and on one of its outputs a logical unit, which is fed to the input 1 of one of the elements 14 subunit 12 (2)(for rows instead of element 14 should be understood first logical conjunction). In case 4) (5) to the input of the binary counter 35 is supplied from the external device, the packet of pulses containing a number of pulses equal to the specified number. The decoder 36 converts the binary code, gained 35 in decimal, and provides the appearance of a unit at one of its outputs.

As a result, the number of the column (row) is given. This means that for the columns for each subunit 12 at the input 1 of one of the elements 14 (first logical conjuncture for strings) is the unit (figure 2). While the input of each subunit 12 only one unit. It is assumed that the numbers specified for all columns (rows) and no repeated numbers. Clock yet, so on the second inputs of the elements 14 (similar to the first logical conjunction) is a logical zero and at the inputs of all elements OR 13 remains zero (similar to the first logical disjunction).

The lower diagram (Fig.6) shows the first on-time signal, which can match the message you enter the numbers of rows and columns. This message can be either a signal entered by the operator after entering the last number, or a signal generated by an external device. This signal can run the synchronizer 9 (1) by filing units on input 1 trigger 20 (figure 4), resulting in unit output 2 trigger is 20, further triggered the mechanism of formation of clock pulses. If the synchronization operation of the device is performed without synchronizer 9, and using an external control device, the start signal synchronization is internal to the external device, and starts the formation of the clock signals received at the inputs of the claimed device.

After starting sync one way or another (work unit 9 will be discussed below) begin to produce bundles of the first and second clock pulses. One of the m first clock pulses corresponding to the string that corresponds to the n second clock pulses corresponding to columns (6).

These pulses are fed to the inputs 2 elements 14 for columns (similar to lines to the inputs of the first logic conjunction). Thus the j-th pulse is sent to each j-th element 14 in each of the 12 subunits. Thus, for each column sequentially receive signals at the inputs 2 elements 14. If the input 1 of the j-th element 14 in the s-subunit 12 is a unit, and it will be, if the j-th number for this subunit, the output of the j-th element 14 also will be a unit, which will be held at the s-th sub 12 and will go on inputs 2 items 10 s-th column. As a result, permission to read information from the post is as under number s, for which the number is set to j.

Similarly, signals are formed at the inputs 3 elements 10, which control the reading lines. With the simultaneous appearance of the units on the inputs 2 and 3 of the elements 10, if the respective register 11 recorded unit, the unit with the 4 element 10 is applied to one of inputs of the element 16 and through him to the inputs 1 elements 19, as the first recording signal (Fig 3). Read at the moment, the case 11 may be in the zero state, the output element 16, the unit may not appear. The situation in the diagram (Fig.6) symbolize the white squares.

The first and second clock pulses are provided to corresponding inputs of elements 19, namely the inputs 2 t-the-line - t-th first clock pulse inputs 3 s-column - s-th second clock pulse.

If the input 1 item 19 unit occurs, and it occurs when there is a unit in the register 11 with coordinates <i, j>there is a recording unit in register with coordinates <t, s>.

Thus, after the mn second clock pulses all information from the registers 11 to be re-written in the registers 18 new coordinates.

If overwrite is not required, then the operation completes.

If you want to reverse overwrite, then to the inputs of 2 elements 11 signal zeroing the first memory, namely logiteck the I unit, all of the registers 11 are converted to zero. Then, through the elements 17, the input of which is supplied with the second signal recording (reverse), overwrites the contents of register 17 in the registers 11, having the same coordinates as the registers 17. Further inputs 1 registers 18 signal reset registers of the second memory, they must be in the zero state. This operation completes.

The synchronizer 9 (figure 4) may operate as follows.

In the initial state on input 1 trigger 20 signal of the logical unit that sets 20 in one state output 3, also translates the counter 27 in the state in which it recorded the unit, the counter 25 is in the zero state, the shift registers 31, 32 and 33 in the zero state. The counter 27 is transferred into the state of the recorded units in order to save one cycle of n pulses. In the initial state at the outputs of the decoders 21 and 22 zeros, the output of element 30 is zero, and the output of inverter 29 - unit. Once installed in the trigger unit 20 inputs 3 and 1 item 24 - unit, therefore, the clock pulses from the oscillator 23 begin to pass through the element 24.

Their believes on input n+1 counter 25 through the decoder 21 pulses into the output of the synchronizer circuit 9 in the form of second clock pulses. The first clock pulses coming out of the decoder 22.

When n+1-th clock pulse input of the counter 25 input 2 element 26 is opened, and the next clock pulse from 23 passes to the input of m+1 of the counter 27 and adds it to the unit, causing the appearance of the next clock pulse at the output of the synchronizer of the packs of the first clock pulses. The counter 25 is arranged in such a way that counts the pulses only to n+1, the next pulse is reset to zero and starts counting again. As arranged, and the counter 27, with the difference that he believes to m and is reset by the next pulse in the unit.

The first and second clock pulses are produced up until the output m of the decoder 21 and the output n of the decoder 22 at the same time not appear unit. In this case, the offer element 28 for the passage of clock pulses from 23 and closes the element 24 through the inverter 29 and the schema matches 30. The counters 25 and 27 clock pulses are no longer received, on the contrary, they begin to work with the element 28 to the input 1 of the shift register 31.

Upon receipt of a pulse on input 1 element 31 is switched to one state, with its output 3 device takes the signal to reset the registers of the first memory. The appearance of the second pulse 31 resets to zero and generates at its output 4 pulse, which sets the unit shift register 32, the output 3 in which the device post is Paeth signal writeback. Similarly, the third clock pulse causes the signal to reset the registers of the second memory. Simultaneously, the unit output 3 item 33 resets to zero on input 2 trigger 20. Zero at its output 3 locking element 24. This cycle synchronizer fails.

The signal, which erases 20 can also reset the counters 25 and 27.

The signal initial setup 20 per unit can be produced either by power or by pressing the button by the operator, or may come from an external computing device.

Different variants of the device for sorting a two-dimensional array data are from the electronic discrete components that perform logical functions. The trigger 20, the registers 11 and 18, the counters 25, 27, 35, shift registers 31-33 belong to those elements that are able to save its state after loss of the input signal, so their switching, i.e. changing the value of their outputs from zero to one and Vice versa occurs on the leading edge signal, so they can be managed with short pulses. The signals at the inputs and outputs of other elements, as well as on outputs 3 registers 11, 18, 31, 32, 33, trigger 20, also at the outputs of the counters 25 (outputs 1-m), 27 (outputs 1-n) and 35 (outputs 1-k) must have a duration, sufficient to provide for the switching of all elements in the acceptable circuit, i.e. to exceed the total duration of the transient process all elements that need to change their status in a given quantum. Appropriate should be the duration of the clock pulses.

For example, the second clock pulse on one chain must perform switching elements 14, 13, 10, 16, 19 and 18 and on the other the chain 19 and 18 (figure 2 and 3). It is clear that the duration should be not less than the total time of the switching elements in the first circuit. The duration of the clock pulse from generator 23 should be even more, because inside the synchronizer 9 also occur internal switch (figure 4).

The outputs of the 4 shift registers 31-33, made on the basis of the trigger, are used to connect shift registers in a circuit and can produce short pulses to switch the next register in the chain.

The counters 25, 27 and 33 are assembled from logical elements - binary counters, each of which is made on the basis of the trigger.

Decoders can be implemented as state machines using elements of the Pier and/or Scheffer.

Items, And and OR can be made of elements of the Pier and/or Scheffer.

The registers 11 and 18 are custodians of information units. If the device is stored and processed two-dimensional array representing a binary matrix, then each register represents the th elementary discrete element, based on one trigger. If the units of information are more complex objects, for example, the values of database attributes, one register 11 or 18 is a set of elementary discrete elements, which number in the set is equal to the number of binary digits in the code, which is encoded by this value. In this case, the elements 10, 19, 17 and 16 also turn into a corresponding set of discrete binary elements.

1. Device for sorting a two-dimensional array of data containing the block of registers of the first memory and the register unit, the second memory, characterized in that it further comprises a control block entry in the registers of the second memory, connected to the first mn inputs with the corresponding mn outputs of the unit registers of the first memory, and mn outputs with the corresponding mn inputs of the unit registers of the second memory, the control unit reading the columns on the inputs set the column number which serves the numbers of the columns, and the corresponding n outputs of which are connected with the second n inputs of the control block entry in the registers of the second memory, the control unit reading the lines to the inputs set the line number serving line numbers and the corresponding m output which is connected to the third m inputs of the control block entry in the registers of the second memory, the control unit is write-back, with the mn United inputs with the corresponding mn outputs of the unit registers of the second memory, and mn outputs with the corresponding mn inputs of the register unit, the first memory.

2. The device according to claim 1, characterized in that the block of registers of the first memory contains mn first registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and representing one of the n columns of the two-dimensional data array, the outputs of data registers connected to respective inputs of the control block entry in the registers of the second memory.

3. The device according to claim 1, characterized in that the block of registers of the second memory contains mn second registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and representing one of the n columns of a two-dimensional array of data inputs of the data registers connected to respective outputs of the control block entry in the registers of the second memory.

4. The device according to claim 1, characterized in that the control unit reads lines contains m sub-blocks, to which gdy of which includes m first logic conjunction, the first inputs of which are the reference input line number of the device to sort two-dimensional data array, the second inputs are the input of the first clock device for sorting a two-dimensional array of data, the first logical disjunctor to m inputs of which are connected the outputs of the first logic conjunction this subunit, and the output is the output of this subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

5. The device according to claim 1, characterized in that the control unit reads column contains n sub-blocks, each of which contains n second logic conjunction, the first inputs of which are the reference input column number of the device to sort two-dimensional data array, the second inputs are the input of the second clock pulses of a device for sorting a two-dimensional array of data, the second logical disjunctor to n inputs of which are connected the outputs of the second logic conjunction this subunit, and the output is the output of this subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

6. The device according to claim 1, characterized in that the control block entry in the registers of the second memory contains a set of mn third logical conjunction, each of which corresponds to one and the only one of the registers of the register unit, the first memory and, accordingly, refers to a particular row and a particular column of a two-dimensional array of data the first inputs of which are connected with the corresponding output of the control unit reading lines, namely the output of the corresponding first logical disjunctor, the output of this k-th logical disjunctor connected n third logical conjunction corresponding to a given k-th row, the second inputs of the third logic conjunction connected with the corresponding output of the control unit reading the columns, namely the output of the corresponding second logical disjunctor, while for the l-th second logical disjunctor connected m third logical conjunction associated with a given l-th column, the third inputs of the third logic conjunction connected to the outputs of the respective registers of the register unit, the first memory also includes a third logical disjunctor, mn inputs of which are connected the outputs of the third logical conjunction also contains a set of mn fourth logical conjunction, each of which corresponds to one and only one register of the register unit, the second memory and is connected by its output to one input of the corresponding register, the first input of the fourth logic conjunction are interconnected and connected to the output of the third logical disjunctor, the second input of the fourth logic conjunction each k-th row is connected is between a and connected to the corresponding bus k-ro of the first clock pulse, the third input of the fourth logic conjunction each l-th column are connected together and connected to the corresponding bus l-th second clock pulse.

7. The device according to claim 1, characterized in that the control unit is write-back is executed in the form of a set of mn-fifths logical conjunction, each of which corresponds to one and only one of the registers of the register unit of the second memory, the first input of the fifth logic conjunction are interconnected and are the input of the second signal recording device for sorting a two-dimensional array of data, the second inputs connected to the outputs of the respective registers of the register unit of the second memory, and outputs connected to respective inputs of registers of the register unit, the first memory having the same number of rows and columns, and data registers of the register unit of the second memory.

8. Device for sorting a two-dimensional array of data containing the block of registers of the first memory and the register unit, the second memory, characterized in that it further comprises a control block entry in the registers of the second memory, connected to the first mn inputs with the corresponding mn outputs of the unit registers of the first memory, and mn outputs with the corresponding mn inputs of the unit registers of the second memory, the control unit reading the columns on the inputs set the column number under which the are column numbers, and the corresponding n outputs of which are connected with the second n inputs of the control block entry in the registers of the second memory, the control unit reading the lines to the inputs set the line number which serves line numbers and the corresponding m output which is connected to the third m inputs of the control block entry in the registers of the second memory.

9. The device according to claim 8, characterized in that the block of registers of the first memory contains mn first registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and representing one of the n columns of the two-dimensional data array, the outputs of data registers connected to respective inputs of the control block entry in the registers of the second memory.

10. The device according to claim 8, characterized in that the block of registers of the second memory contains mn second registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and symbolizers is x one of the n columns of the two-dimensional data array, the inputs of the data registers connected to respective outputs of the control block entry in the registers of the second memory.

11. The device according to claim 8, characterized in that the control unit reads lines contains m sub-blocks, each of which contains m first logic conjunction, the first inputs of which are the reference input line number of the device to sort two-dimensional data array, the second inputs are the input of the first clock device for sorting a two-dimensional array of data, the first logical disjunctor to m inputs of which are connected the outputs of the first logic conjunction this subunit, and the output is the output of this subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

12. The device according to claim 8, characterized in that the control unit reads column contains n sub-blocks, each of which contains n second logic conjunction, the first inputs of which are the reference input column number of the device to sort two-dimensional data array, the second inputs are the input of the second clock pulses of a device for sorting a two-dimensional array of data, the second logical disjunctor to n inputs of which are connected the outputs of the second logic conjunction this subunit, and the output is the output of this subunit podkluchen to the corresponding input of the control block entry in the registers of the second memory.

13. The device according to claim 8, characterized in that the control block entry in the registers of the second memory contains a set of mn third logical conjunction, each of which corresponds to one and only one of the registers of the register unit, the first memory and, accordingly, refers to a particular row and a particular column of a two-dimensional data array, the first inputs of which are connected with the corresponding output of the control unit reading lines, namely the output of the corresponding first logical disjunctor, the output of this k-th logical disjunctor connected n third logical conjunction corresponding to a given k-th row, the second inputs of the third logic connected conjunction with the corresponding output of the control unit reading the columns, namely the output of the corresponding second logical disjunctor, while for the l-th second logical disjunctor connected m third logical conjunction associated with a given l-th column, the third inputs of the third logic conjunction connected to the outputs of the respective registers of the register unit, the first memory also includes a third logical disjunctor, mn inputs of which are connected the outputs of the third logical conjunction also contains a set of mn fourth logical conjunction, each of which is s corresponds to one and only one register of the register unit, the second memory and its associated the output to the input of the corresponding register, the first input of the fourth logic conjunction are interconnected and connected to the output of the third logical disjunctor, the second input of the fourth logic conjunction each k-th row are interconnected and connected to the corresponding bus k-th of the first clock pulse, the third input of the fourth logic conjunction each l-th column are connected together and connected to the corresponding bus l-th second clock pulse.

14. Device for sorting a two-dimensional array of data containing the block of registers of the first memory and the register unit, the second memory, characterized in that it further comprises a control block entry in the registers of the second memory, connected to the first mn inputs with the corresponding mn outputs of the unit registers of the first memory, and mn outputs with the corresponding mn inputs of the unit registers of the second memory, the control unit reading the lines to the inputs set the line number which serves line numbers and the corresponding m output of which is connected with the second m inputs of the control block entry in the registers of the second memory.

15. The device according to 14, wherein the register unit, the first memory contains mn first registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and symbolizing od is the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and representing one of the n columns of the two-dimensional data array, the outputs of data registers connected to respective inputs of the control block entry in the registers of the second memory.

16. The device according to 14, characterized in that the block of registers of the second memory contains mn second registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and representing one of the n columns of a two-dimensional array of data inputs of the data registers connected to respective outputs of the control block entry in the registers of the second memory.

17. The device according to 14, characterized in that the control unit reads lines contains m sub-blocks, each of which contains m first logic conjunction, the first inputs of which are the reference input line number of the device to sort two-dimensional data array, the second inputs are the input of the first clock device for sorting a two-dimensional array of data, the first logical disjunctor to m inputs of which are connected the outputs of the first l is formed of conjunctural this subunit, and the output is the output of this subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

18. The device according to 14, characterized in that the control block entry in the registers of the second memory contains a set of mn third logical conjunction, each of which corresponds to one and only one of the registers of the register unit, the first memory and, accordingly, refers to a particular row and a particular column of a two-dimensional data array, the first inputs of which are connected with the corresponding output of the control unit reading lines, namely the output of the corresponding first logical disjunctor, the output of this k-th logical disjunctor connected n third logical conjunction corresponding to a given k-th row, the second inputs of the third logic connected conjunction with the corresponding output of the control unit reading the columns, namely the output of the corresponding second logical disjunctor, while for the l-th second logical disjunctor connected m third logical conjunction associated with a given l-th column, the third inputs of the third logic conjunction connected to the outputs of the respective registers of the register unit, the first memory also includes a third logical disjunctor, mn inputs cat who was connected to the outputs of the third logical conjunction, also contains a set of mn fourth logical conjunction, each of which corresponds to one and only one register of the register unit, the second memory and is connected by its output to one input of the corresponding register, the first input of the fourth logic conjunction are interconnected and connected to the output of the third logical disjunctor, the second input of the fourth logic conjunction each k-th row are interconnected and connected to the corresponding bus k-th of the first clock pulse, the third input of the fourth logic conjunction each l-th column are connected together and connected to the corresponding bus l-th second clock pulse.

19. Device for sorting a two-dimensional array of data containing the block of registers of the first memory and the register unit, the second memory, characterized in that it further comprises a control block entry in the registers of the second memory, connected to the first mn inputs with the corresponding mn outputs of the unit registers of the first memory, and mn outputs with the corresponding mn inputs of the unit registers of the second memory, the control unit reading the columns on the inputs set the column number which serves the numbers of the columns, and the corresponding n outputs of which are connected with the second n inputs of the control block entry in the registers of the second memory.

20. The device according to claim 19, trichomania fact, the unit registers of the first memory contains mn first registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and representing one of the n columns of the two-dimensional data array, the outputs of data registers connected to respective inputs of the control block entry in the registers of the second memory.

21. The device according to claim 19, characterized in that the block of registers of the second memory contains mn second registers storing information units, each of which belongs to one of the m disjoint sets containing n these registers and representing one of the m rows of the two-dimensional data array, and simultaneously belongs to one of n disjoint sets containing m these registers and representing one of the n columns of a two-dimensional array of data inputs of the data registers connected to respective outputs of the control block entry in the registers of the second memory.

22. The device according to claim 19, characterized in that the control unit reads column contains n sub-blocks, each of which contains n second logic conjunction, the first inputs of which are the reference input nom the RA device column to sort two-dimensional data array, the second inputs are the input of the second clock pulses of a device for sorting a two-dimensional array of data, the second logical disjunctor to n inputs of which are connected the outputs of the second logic conjunction this subunit, and the output is the output of this subunit and connected to the corresponding input of the control block entry in the registers of the second memory.

23. The device according to claim 19, characterized in that the control block entry in the registers of the second memory contains a set of mn third logical conjunction, each of which corresponds to one and only one of the registers of the register unit, the first memory and, accordingly, refers to a particular row and a particular column of a two-dimensional data array, the first inputs of which are connected with the corresponding output of the control unit reading lines, namely the output of the corresponding first logical disjunctor, the output of this k-th logical disjunctor connected n third logical conjunction corresponding to a given k-th row, the second inputs of the third logic connected conjunction with the corresponding output of the control unit reading the columns, namely the output of the corresponding second logical disjunctor, while for the l-th second logical disjunctor connected m third logical canyon is tori, respective l-th column, the third inputs of the third logic conjunction connected to the outputs of the respective registers of the register unit, the first memory also includes a third logical disjunctor, mn inputs of which are connected the outputs of the third logical conjunction also contains a set of mn fourth logical conjunction, each of which corresponds to one and only one register of the register unit, the second memory and is connected by its output to one input of the corresponding register, the first input of the fourth logic conjunction are interconnected and connected to the output of the third logical disjunctor, the second input of the fourth logic conjunction each k-th row are interconnected and connected to the corresponding bus k-th of the first clock pulse, the third input of the fourth logic conjunction each l-th column are connected together and connected to the corresponding bus l-th second clock pulse.



 

Same patents:

The invention relates to computer technology and can be used for decision making with regard to expert estimations in the development of automated control systems of various processes and large systems

The invention relates to devices and methods of processing information, in which information is recorded, for example, on a disk recording medium for write-once

The invention relates to a system for re-ordering re-ordering of the data elements of the stream of data elements transmitted over the serial connection of the first switching node, the buffer register and the second switching node

The evaluator ranks // 2095850
The invention relates to computer technology and can be used in specialized computers and data processors

The invention relates to automatic control and computer engineering and can be used in systems of associative processing and storing information (associative search, associative memory, associative processors, systems analysis and image processing (recognition systems, robots), online signal processing (processing fields of different physical nature of the signal amplitude) and online analytical processing (sorting, data compression, the construction of the conditional distributions, parallel data retrieval, database management and knowledge)

The invention relates to automation, computer engineering and radar systems and can be used in systems optimal control of measurement processes

The invention relates to automatic control and computer engineering and can be used in systems of associative processing and storage of information

The invention relates to techniques for processing digital data, in particular to a device for determining the code combinations, and may find application in the transmission of digital information for selecting from it the set of code combinations

The invention relates to computer technology and can be used in information retrieval systems to quickly filter the data by coincidence

The invention relates to computer technology and can be used in data mining systems, including processing and analysis of geological and geophysical information and other data obtained in the study of natural or socio-economic objects or phenomena

The invention relates to the field of spectral analysis and can be used in the classification of quasi-periodic signals

The invention relates to computer technology and can be used in specialized solvers for the solution of problems, including digital processing of signals and images

The invention relates to the field of computer engineering and can be used in specialized computer systems for computing the eigenvalues of the matrix (nn)

The invention relates to computer technology and can be used in specialized computer systems to calculate the two-dimensional convolution

The invention relates to the field of computer engineering and can be used in specialized computer systems to calculate swerski

Matrix setprocessor // 2079879
The invention relates to computing and is designed to build on the basis of specialized computers

FIELD: computer science.

SUBSTANCE: device has block of registers of first memory, block of registers of second memory, block for controlling reading of columns, block for controlling reading of rows, block for controlling reverse recording; according to second variant, device has same elements excluding block for controlling reverse recording. Third variant of device is different from second variant by absence of block for controlling reading of columns, and fourth variant of device is different from second one by absence of block for controlling reading of rows.

EFFECT: higher efficiency.

4 cl, 9 dwg

FIELD: computer science, possible use for engineering devices meant for processing numeric information arrays, in particular, for permutation of rows of two-dimensional array (matrix) stored in memory of computing device.

SUBSTANCE: device contains matrix of unary first memory registers and matrix of unary registers of second memory, which are identical to each other. Between them a commutator is positioned. Unary memory registers, positioned conditionally in one row, are connected between each other as shifting row registers. Commutator on basis of law given externally connects output of shifting register of first memory, corresponding to i-numbered row, to input of shifting register of second memory, corresponding to j-numbered row in second memory. After sending a packet of shifting pulses to shifting input of i-numbered shifting register of first memory, information from it moves to j-numbered shifting register of second memory. Therefore, transfer of i-numbered row to j-numbered position in new array occurs. Transfer of rows can be realized row-wise, or simultaneously for all, while structure of commutator is different for different cases.

EFFECT: realization of given permutation of rows and/or columns of two-dimensional array.

7 cl, 10 dwg, 1 tbl

Up!