Device for sorting two-dimensional data array

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

 

Device for sorting a two-dimensional array of data belongs to the field of computer hardware, namely, devices for the processing of numerical data, and is intended 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.

The closest in technical essence and the achieved result of the claimed invention is a 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 terms, is for analogue and proposed technical solutions are two groups of n registers. The disadvantage of this device is that the object of permutations is a one-dimensional array data.

The device is intended for solving the following tasks.

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 following binary matrix

If you carry out the following permutation of rows:

you get transformed matrix:

For each row of the matrix, while the matrix is a two-dimensional array of data recorded in the registers of the first memory, the external impact is set corresponding to the new 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 block of buttons or switches, in fact, is also an external device to the claimed invention. Another external device may be a logical device (computing device, the digital device)that generates the control signals by permuting the rows until the WMD-or rule.

May require sorting of both lines and columns. Thus similarly, you can sort the columns, if you have specified an array by switching rows to columns during the initial process of recording information in the first memory. Therefore, in the future, speaking about the lines will mean that their place can be columns, and respectively, then instead of columns should mean line. For the memory of the computing device or any electronic device the concept of row and column with respect to the stored two-dimensional array is relative, so when describing the structure of the device used the concept of a set. The relevant sets can be correlated with the rows or columns that are used for clarity.

The present device may be made in the form of chips or join chip as part of a computing device and is intended for the technical implementation of the sorting algorithm of two-dimensional data array, in particular a relational database or processing of numerical matrix when solving equations using technology (automatic) processing of information.

Device for sorting a two-dimensional array data contains the block of registers of the first memory block of registers of the second memory, the switch connected to the first the inputs with corresponding outputs of the register unit, the first memory; outputs to the corresponding inputs of the unit registers of the second memory; the second input of the switch filed the control signals of the switching blocks of registers of the first and second memory between themselves, which are the control inputs of the device for sorting a two-dimensional array of data; the inputs of the unit registers of the first memory and the third input of the switch filed with the sync signal (shift pulse).

The unit registers of the first memory contains mn first cell storing data representing the first unit shift registers storing one unit of data; each cell belongs to one of the m first disjoint sets containing n these cells and symbolizing one (one) of m rows (columns) of a two-dimensional array data, and simultaneously belongs to one of the n second disjoint sets containing m cells and symbolizing one (one) of n columns (rows) of two-dimensional data array; each of the m first disjoint sets n first unit shift registers to form one of m first n-cell shift register by connecting the shear outputs of the i-th unit shift register with the corresponding shear inputs i+1-th unit shift register; shift input 1 single shift register in each of the m first n-cell shift registers are the two which is input to the sync signal (shift pulse); the status outputs of the n-th unit shift register in each of the m first n-cell shift registers is one of the m outputs of the register unit, the first memory and is connected with the corresponding one of the m first inputs of the switch.

In each one of the m, the first n-cell shift register the first unit shift registers interconnected in such a way that the third output of the i-th unit shift register connected to the first input of the i+1-th unit shift register for transmission from the i-th register to the i+1-th logical zero; the fourth output of the i-th unit shift register connected to a second input of the i+1-th unit shift register for transmission from the i-th register to the i+1-th logical units; the first input 1-th single shift register in each of the m first n-cell shift registers is the entrance of this first n-cell shift register and one of the m inputs of the device to sort two-dimensional data array for supplying signals (shift pulse).

The unit registers of the second memory contains mn of the second cell storing data representing the second unit shift registers storing one unit of data; each cell belongs to one of the m third disjoint sets containing n these cells and symbolizing one (one) of m rows (columns) on umemulo data array, and simultaneously belongs to one of the n fourth disjoint sets containing m cells and symbolizing one (one) of n columns (rows) of two-dimensional data array; each of the m third disjoint sets of n unit shift registers to form one of the m second n-cell shift register by connecting the shear outputs of the i-th unit shift register with the corresponding shear inputs i+1-th unit shift register; shift inputs of the 1st single shift register in each of the m second n-cell shift registers connected to respective outputs of the switch.

Each of the second n-cell shift register second unit shift registers interconnected in such a way that the third output of the i-th unit shift register connected to the first input of the i+1-th unit shift register for transmission from the i-th register to the i+1-th logical zero, the fourth output of the i-th unit shift register connected to a second input of the i+1-th unit shift register for transmission from the i-th register to the i+1-th logical units; a first input 1 of a single shift register in each of the m second n-cell shift registers is the input of this second n-cell shift register for transmitting a logical zero and is zero input according to stuudy one of the m pairs of inputs of the unit registers of the second memory; the second input of the 1st single shift register in each of the m second n-cell shift registers is the input of this second n-cell shift register for transmission to the logical unit and is a single input of a corresponding one of the m pairs of inputs of the unit registers of the second memory.

Blocks of registers of the first and second memory are almost identical and differ only by the connection of its inputs and outputs.

Below is a description of two possible embodiments of the switch.

Option 1. The switch has m first logic conjunction (elements), the second inputs of which are the first m inputs of the switch and connected to respective m outputs of the register unit, the first memory; a first logical disjunction (OR element), each of the m inputs is connected to the output of the corresponding one of the m first conjunction, and the output is connected with the second inputs of the m second logic conjunction (elements), at the first input of each of which, one of the m first 2m of the second inputs of the switch and at the same time one of the control inputs of the device for sorting a two-dimensional array of data to control the switching shift register block registers the first and second memory between them, filed a corresponding one of the m first control signal; the first input is s the first conjunction are second from the second input switch, each of which serves one of the m second control signals, which control inputs of the device for sorting a two-dimensional array of data; the output of each of the m second conjunction connected to the input of the corresponding one of the m first inverter and the first input of the corresponding one of the m third conjunction, the second inputs of which are connected together and are the third input of the switch for an external sync signal (shift pulse); the output of each of the first inverter is connected to the first input of the corresponding one of the m fourth conjuncture, the second input of each of which is connected with the second input of the corresponding third conjuncture; third inputs of the respective third and fourth of conjunction connected with each other and with the respective first inputs of the second conjunction; the outputs of the respective third and fourth of conjunctural form m pairs of outputs, which are the outputs of the switch and connected to the corresponding inputs of the unit registers of the second memory.

This embodiment of the switch allows you to transfer information row by row (column) from one memory to another. Below is an embodiment of a switch that allows you to transfer information from one memory to another simultaneously for all rows (columns), which reduces the time the disorder, but complicates its design.

Option 2. The switch contains m-fifths logical conjunction (elements), each of which belongs to one of the m-fifths of disjoint sets containing m elements And symbolizing one (one) of m rows (columns) of a two-dimensional matrix, and simultaneously belongs to one of m sixth disjoint sets containing m elements And symbolizing one (one) of m columns (rows) of a two-dimensional matrix; at the first input of each of the fifth element And filed a corresponding one of the m2control signals, which is the second inputs of the switch and simultaneously control inputs of the device for sorting a two-dimensional array of data to control the switching blocks of registers of the first and second memory among themselves; the second inputs of the fifth element And forming a single (one) column (row), i.e. belonging to one of m sixth disjoint sets, are connected together and are connected with the corresponding output of one of the m, of the unit registers of the first memory and m are the first inputs of the switch; the outputs of each of the m fifth elements And forming a row (column), connected to respective m inputs of the corresponding second logical disjunctor one of the m; the output of each of the m second disjunction connected to the input of the corresponding one of the m second invert the ditch and to the first input of the corresponding one of the m-sixths of conjunction, the second inputs of which are connected together and are the third input of the switch for an external sync signal (shift pulse); the output of each of the second inverter is connected to the first input of the corresponding one of the m seventh conjuncture, the second input of each of which is connected with the second input of the corresponding sixth conjuncture; the outputs of the respective sixth and seventh of conjunctural form m pairs of outputs, which are the outputs of the switch and connected to the corresponding inputs of the unit registers of the second memory.

Spelling words in brackets means that these words can be used instead of previous, related words, such as "column" instead of "string".

Figure 1 shows the block diagram of the device, here 1 is the unit shift registers of the first memory, 2 - unit shift registers of the second memory, 3 - switch 4 - control unit reading, 5 - synchronizer. In the rectangle defined by the dotted line are units of the claimed invention, the synchronizer and control unit reads are external devices.

Figure 2 shows two variants of a functional circuit block of registers of the first memory 1. Here 6 is the first single shift registers. The variants differ in the way the connection of the inputs of the block 1 with the synchronizer 5. In the first embodiment, each of the m inputs of the block 1 is coupled to one of the m outputs of the block 5. In the second embodiment, all inputs to the block 1 are connected together and connected to a single output unit 5.

Figure 3 presents the block diagram of the registers of the second memory 2. Here the 7 - second unit shift registers.

4 shows a variant of the functional circuit of the switch 3, which will be referred to as the first (or option 1). Here 8 is the first logical conjuncture, m pieces, the first inputs they are second from the second control inputs of the switch; 9 - the first m-shadowy element OR (logical disjunction); 10 - second elements And (logical conjuncture), m pieces, the first inputs are managers first or second inputs of the switch; 11 - the first element is NOT (logical inverter); 12 and 13, respectively, the third and fourth elements And. the Elements 11, 12 and 13 are combined in the sub 14, which is indicated by the dotted line. Such subunits 14 in the scheme of m pieces. Also shown synchronizer 5, the control unit reads 4 and blocks of registers of the first 1 and second 2 memory.

Figure 5 shows the second option (or option 2) functional schematic switch 3. There are 15 five elements And their m2pieces, the first inputs are managers; 16 - second m-input elements OR the m pieces; 17 - the second inverter; 18 and 19, respectively, the sixth and seventh elements And. the Elements 17, 18 and 19 are combined in the sub 20. These subunits in the scheme of m pieces. She is also shown synchronizer 5, the control unit reads 4 and blocks of registers of the first 1 and second 2 memory. The block 4 may be composed of m identical subunits that control one relevant column elements 15, so the rectangle denoting the drawing unit 4, contains within itself the rectangles corresponding to the subunits, forming part of block 4. This shows the numbering of the outputs of the block 4 is a General block 4, and in each of the subunits related outputs. The numbering of the control inputs of unit 3 connected to the outputs of block 4, figure 5 is not shown, but it is fully consistent with the numbering of the outputs of the block 4. Bold line represents a common bus for connecting outputs of the elements 16 and inputs subunits 20 (input elements 17 and 18) in this bus m connections.

"1" and "0" in figure 2-5 represent the chain shift, respectively, a logical zero and a logical unit in the shift register. In the images the dotted line symbolizes not displayed items and blocks, similar to the ellipsis means not shown in the drawings, the inputs and outputs. The numbering of the inputs and outputs at all similar items and blocks are the same and correspond to the designations shown on the example of the individual elements and blocks.

Figure 3-5 at the switch and the unit register of the second memory are numbered pairs respectively inputs and outputs, and not according to the corresponding inputs and outputs. This is due to the fact that a couple of joints shall be functional load, and depending on the values of the transmitted signal is a logical zero and unit activates one or the other channel in the pair. In the future sometimes, instead of a pair will be referred to respectively input or output, when I will be talking about the logic of the device as a whole, without specifying the values transmitted in the moment of the beep.

Figure 1-5 all blocks have inputs on the left and outputs on the right, except for blocks 4 and 5, which have only outputs. Where there is one input and/or one output, respectively, the entrance and/or exit is not numbered, for example the inverters 10 figure 4 not numbered outputs, as each of the elements 10 of them one by one. The subscript in the name of the blocks indicates the sequence number of the corresponding block or item in a group are identical in design and functionality in the inventive device elements (blocks).

Simple lines in figure 2-5 shows the connections between the elements, transmitting potential signals that may correspond to specific values of electrical voltages, the presence of such a signal at the input element maintains the last state of that signal. Arrows denote connections, which are transmitted short pulses, the trigger is lementa receiver of such a signal occurs on the leading edge of the input for his pulse.

Figure 6 shows four different possible scenarios decoder line number (column)that is part of unit 4.

The principle of operation of the claimed technical solution is that when applying control signals to the switch, the switch connects the i-th row of the first memory with the j-th row in the second memory. This is the connection string according to the rule of one-to-one, i.e. one row of the first memory can be connected to only one row in the second memory and Vice versa. Some lines may remain and not connected, in this case information from some of the k-th line of the first memory will not be overwritten in the second memory, and some string t the second memory will be empty (null) or unmodified, it will be a source of information, if it was there.

When applying shift pulses from an external device (synchronizer 5) to the input unit 1 information from the shift registers corresponding to the rows of the array in the first memory (block 1), will be overwritten in the shift registers of the second memory corresponding to the row in the second memory (block 2). This is done as follows. One shear (clock) pulse moves all of the information in the shift register made up of a sequence of unit shift registers, one position. The first is nulls, thus, pushes the information from the last cell of the shift register one line to the output of this register. The task switch is to supply this information to the input of the corresponding shift register, i.e. the desired line in the second memory. As a result, the value of the last cell of the row in the block 1 is overwritten in the first cell of the corresponding row of the block 2. The second shift pulse promotes all the information one position, etc. Only one pack of sync must contain the n shift pulses, i.e. as many as there are cells in one shift register corresponding to one row of the array.

Design options switch allow you to perform two different algorithm overwriting rows from the first memory to the second.

The first option involves line-by-line rewrite. In this case, the synchronizer is served alternately m reams, n shift pulses (clock pulses) for each of the m rows of the original array in order, starting with the first. Synchronously with the beginning of each pulse packet to the appropriate managing second input of the switch signal from the corresponding output unit 4. This second m control signals specify the number of rows 1 through m in ascending order, indicating which line is currently perezapisyvat is camping in a new position, and the first m control signals specify a new number of rows. The number of each of the m first control signals corresponds to the number of rows in the second memory into which you want to overwrite the first line memory, which is currently filed a pack of sync. The connection in this case, the blocks 5 and 1 are shown in figure 2 as option 1.

Every moment should appear only one first control signal and only one second control signal, however, their combined effect should be carried out at intervals not less than the duration of one clock and not longer than the repetition period of these packs. This is necessary so that one row of the first memory could Peresopnytsia only one row in the second memory.

Supply packs of clock pulses to the input of the switch for supplying signals and simultaneous supply of the first control signal at the j-th first control input of the switch and the second control signal at the i-th second control input of the switch overwrites the i-th line of the first memory in the j-th row of the second memory.

After rewriting a single line overwrites the next line.

Such a device makes it easier, but increases the time, so as to rearrange the rows of the original array takes time for the filing of the m packets of n clock pulses in each.

Another variant provides for the filing of packets of pulses simultaneously to the m inputs of the first memory. In this case, the block 4 serves to control the second inputs of switch m2control signals, by which the switch redistributes the flow of information between the rows of the first and second memory. The connection in this case, the blocks 5 and 1 are shown in figure 2 as option 2. In this case, the design of the switch is more complicated, but the battery is decreasing in m times in comparison with the first option.

The first variant is the same network technology with a shared bus, when a pair of subscribers, in which roles are rows of memory blocks that are interconnected in series. The second version of the same network technology, in which there is a connection of subscribers by rule a point-to-point, when at the same time, the formation of m pairs of subscribers.

It should be noted that the block 4 and the synchronizer 5 can be combined in a single device, or block 4 can be controlled by the unit 5, which will synchronize the generation of control signals supplied to the block 3, block 4.

The unit shift registers (URR) 6 and 7 in their design and logic are identical. They have two shear input 1 and 2, two shear output 3 and 4. Pair 1-3 serves to transfer from one movement to the next is logical zero, pair 2-4 serves to transfer from one movement to the next logical units. Initially, each register is set to the state corresponding to a logical zero or one. This is done through a separate installation inputs which are not shown in the drawings. These inputs can be used for the initial recording of the original array in the first memory. Depending on the condition at the moment is this ECP, output, called the exit status, you receive the value of logical zero or a logical unit. Figure 2 is exit 5 in block 6, the corresponding ECP1n. Below is the truth table (functioning) of the ECP.

1234QQ+1
1--110
1-1-00
-1-111
-11-01

In the table in the first row of figures denote the number of inputs and outputs according to the drawings, the Q - state movement before receipt of the next pulse is is input 1 or 2, Q+1 - state of ECP after receipt of the pulse on input 1 or 2, i.e. this new state movement, caused by the appearance of a pulse on input 1 or 2, in which goes ECP from the state of Q. the values of the variables Q and Q+1 correspond to the signals at the output 5 of the ECP. The simultaneous occurrence of pulses at the inputs 1 and 2 is prohibited, the responsibility lies external to the ECP devices. In other rows of the table except the first are listed the values of the logical signals at the inputs and outputs of the ECP. The appearance of the pulse at the inputs 1-4 are indicated by unit, no count - dash. The appearance of the pulse at the input 1 or 2 calls depending on the status of the ECP the appearance of the pulse at the output 3 or 4. Since the outputs 3 and 4 one ECP associated with inputs 1 and 2 respectively of another movement, a shift of information from the first movement in the second. The potential signal at the output 5 of the ECP can correspond to a value of an electrical voltage. It is supported at the outlet 5 as long as this movement is in an appropriate state. The signals at the inputs 1 and 2 and outputs 3 and 4 of the ECP are short pulses and trigger the corresponding element, the input of which is served at their leading edge.

The blocks 6 ECPi1in block 1 (figure 2) is applied only on the input 1. We believe that in the initial status and ECP, when he is not recorded no information at its output 5 there is a potential corresponding to logical zero. The information recording means moving some of ECP in one state, while others will remain in the zero state. In the result of the shift register composed of the ECP will be recorded some combination of zeros and ones. The need to move the register to the output. The pulses applied to the input 1 of the first movement of the corresponding m-th shift register, will promote the combination of the output of the register and write zeros to the place vacated cells (shift register).

The data from the m output (n-s) URR first memory through the switch m 1-s ECP second memory is performed as follows. Unit 3 switches the output 5 of the last movement of the first memory with the appropriate string, i.e. corresponding to the first movement of the second memory, by implementing logical functions performed by the elements of the block 3. As a result, if the output 5 of the last movement of the first memory is a logical unit, then through a prescribed switching clock pulse from a pack of clock pulses is applied to the input 2 of the first movement of the second memory if the corresponding output 5 ECP logical zero, then the sync pulse about the result not to the second input, and to the first input of the corresponding first movement of the second memory. Thus overwrites the values from the last movement of the first memory corresponding to the first movement of the second memory. Naturally, the pulses supplied to the respective input of the first memory and to the appropriate input switch for submission to the appropriate input of the second memory are synchronous, but rather, it is the same impulse, as specified inputs for the supply of the clock can be connected.

The device operates as follows.

In the initial state in ECP 6 block 1 is written to logical zeros and ones (hereinafter simply ones and zeros)corresponding to the source two-dimensional array. The elements 7 are in the zero state. At the outputs of the 5 elements 6 are units or zeros. At the first inputs of the elements 8, 10 and 15 are zeros, so as long as there are no control signals. The output element 9 is zero. The outputs of the elements 10 and 15 zeros, respectively, from the outputs of the elements 16 and the inputs of the elements 11 and 17 and the input 1 of the elements 12 and 18 are also zeros. The outputs of the elements 11 and 17 are units, and respectively at the inputs 1 elements 13 and 19 are units. In the absence of clock pulses and control signals at the outputs of the elements 12, 13, 18 and 19 of the zeros and the signals on inputs 1 and 2 elements 7 are not. The state of the Loka 2 remains unchanged.

Next, the operation of the device will be considered separately for the two variants of its execution.

Option 1.

When applying the first control signal from the i-th output unit 4, which is one of the first m output unit 4 to the input 1 of the i-th element 10 Andithe latter becomes transparent to the signal unit through one of the elements 8 and item 9 of block 1. The second control signal with m+1-th output unit 4 is supplied to the input 1 of item 8 And1that becomes transparent to the transmission unit on its output from element 6 ECP1nfrom the block 1. Other elements 10 and 8 are locked in their outputs remain set to 0. If the element 6 ECP1nrecorded 1, it will go through the elements 8 And19 and 10 Andito the input of the inverter 11 in subblock 14i. This unit is an input unit 1 12 subunit 14i. With the output element 11 to the first input of the element 13 will be submitted to 0, i.e. the signal opposite to the signal on the first input element 12. Signal units will be served also on the 3 inputs of the respective elements 12 and 13 sub 14ifrom the i-th output unit 4, which is one of the first m output unit 4.

When applying the first pulse of the first bundle from the output m+1 unit 5 to the inputs of 2 elements 12 and 13 sub 14ithis pulse will be output or item 12, item 13 sub 14iin resulttable filed a pulse on input 1 or 2 item 7 URR i1unit 2, i.e. in the first cell of the i-th row block 2 will be written to 1 or 0.

Simultaneously with the synchronizing pulse output m+1 block 5 will be Popayan clock pulse of the first bundle to the input 1 of item 6 of URR11. The result will be a movement information for the first row of the block 1. Each element 6 ECP1i+1go into the condition in which prior to the filing of this impulse was the element 6 ECP1i. The first item will go to the zero state. The information flow on shift register will cause the signal at the output 5 item 6 ECP1n. The sequence of the values of these signals will correspond to the combinations recorded initially in the first row of the array. Depending on the signals at the output 5 item 6 ECP1nwill change the values of the signals at the inputs of the elements 11 and 12 subunit 14iand , accordingly, will receive a pulse that the output of the element 12, the output element 13, and element 7 URRi1will be recorded then 0, then 1. The previous value in the cell 7 URRi1will move into the cell 7 URRi2and from her cell 7 URRi3etc.

After passing n of clock pulses of the first bundle, the first row of the original array will be overwritten in the 1st row of the second memory.

Then begins the next cycle for the second row. You receive 1 at the first input e is ment 8 And 2and the control signal at the output j of block 4, j≠i. All these m cycles. Output m+1 block 5 only served mn of the shift pulses, each portion of n pulses appears synchronously with one of the packs on the outputs from 1 to m.

Option 2.

The elements 15 form a square matrix of size m. In the initial state, the signals from the outputs of the block 4 are absent, then the outputs of all blocks 15 and 16 are zeros. The clock output unit 5 is also not available, so the outputs of all of the elements 18 and 19 pulse no.

The logic operation of the device requires that the outputs of the unit 4 control signals appeared so that in each column of elements 15 unit input 1 appeared only one item 15 of this column and in each row only one item from this line. The output of each element 6 ECPinconnected with the second inputs of the elements 15 of 1st column. The emergence of, for example, 1 on the first input element 15 And21will cause its output will repeat the output value 1 of block 1 and through the element 16 OR2and element 17 subunit 202will switch the sequence of clock pulses between the outputs of the elements 18 and 19 sub 202depending on the state change of the output 1 of block 1. Thus information from the first row of block 1 will move to the second line b is the eye 2. A similar pattern is repeated on other outputs of subunits 20 and respectively at the inputs of the block 2. The whole procedure will occur for n clock cycles. In this embodiment, block 5 should give n shift pulses. These clock pulses simultaneously serves as the input unit 4 and unit 1 with the same output block 5.

Device for sorting a two-dimensional array data from the electronic discrete components that perform logical functions. ECP 6 and 7 represent a logical electronic elements on the basis of the trigger, designed to store a logical zero or one. They are able to save its state in the absence of input signals. Change their state 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 the elements must have a duration sufficient to provide for the switching of all elements in the given 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 (shear) pulses or signals.

The elements of AND, OR and NOT can be made of elements of the Pier and/or Scheffer.

Unit 4 option 1 may have the Ostrava 2 different decoder line number, made in one of the options, as shown in Fig.6. The outputs of one decoder correspond to the first m output unit 4, and outputs the second outputs from m+1 to 2m.

Unit 4 option 2 may be composed of either decoder, made in options 1 or 2 according to Fig.6, the number of outputs is not m, as shown in the drawing, and m2or to present a logical device forming the appropriate combination of m2discharge.

1. Device for sorting a two-dimensional array of data containing the block of registers of the first memory for storing the original two-dimensional array and the register unit, a second memory for storing the output of a two-dimensional array, characterized in that it further comprises a switch connected to the first inputs with corresponding outputs of the register unit, the first memory; outputs to the corresponding inputs of the unit registers of the second memory; the second input of the switch filed the control signals of the switching blocks of registers of the first and second memory between themselves, which are the control inputs of the device for sorting a two-dimensional array of data; the inputs of the unit registers of the first memory and the third input of the switch filed shear pulses.

2. The device according to claim 1, characterized in that the block of registers of the first memory contains mn of the first storage cells of the data, before the bringing of a first unit shift registers storing one unit of data; each cell belongs to one of the m first disjoint sets containing n these cells and symbolizing one (one) of m rows (columns) of a two-dimensional array data, and simultaneously belongs to one of the n second disjoint sets containing m cells and symbolizing one (one) of n columns (rows) of two-dimensional data array; each of the m first disjoint sets n first unit shift registers to form one of the m first n-cell shift register by connecting the shear outputs of the i-th unit shift register with the corresponding shear inputs i+1-th unit shift register; shift input 1 single shift register in each of the m first n-cell shift registers is input to the shift pulses; the output state of the n-th unit shift register in each of the m first n-cell shift registers is one of the m outputs of the register unit, the first memory and is connected with the corresponding one of the m first inputs of the switch.

3. The device according to claim 2, characterized in that each one of the m, the first n-cell shift register the first unit shift registers interconnected in such a way that the third output of the i-th unit shift register connected to the first input of the i+1-th unit shift register of teleperedachi from the i-th register to the i+1-th logical zero; the fourth output of the i-th unit shift register connected to a second input of the i+1-th unit shift register for transmission from the i-th register to the i+1-th logical units; a first input 1 of a single shift register in each of the m first n-cell shift registers is the entrance of this first n-cell shift register and one of the m inputs of the device to sort two-dimensional data array for supplying shift pulses.

4. The device according to claim 1, characterized in that the block of registers of the second memory contains mn of the second cell storing data representing the second unit shift registers storing one unit of data; each cell belongs to one of the m third disjoint sets containing n these cells and symbolizing one (one) of m rows (columns) of a two-dimensional array data, and simultaneously belongs to one of the n fourth disjoint sets containing m cells and symbolizing one (one) of n columns (rows) of two-dimensional data array; each of the m third disjoint sets n unit shift registers to form one of the m second n-cell shift register by connecting the shear outputs of the i-th unit shift register with the corresponding shear inputs i+1-th unit shift register; shear inputs 1-what about the single shift register in each of the m second n-cell shift registers connected to respective outputs of the switch.

5. The device according to claim 4, wherein each of the second n-cell shift register second unit shift registers interconnected in such a way that the third output of the i-th unit shift register connected to the first input of the i+1-th unit shift register for transmission from the i-th register to the i+1-th logical zero, the fourth output of the i-th unit shift register connected to a second input of the i+1-th unit shift register for transmission from the i-th register to the i+1-th logical units; the first the entrance of the 1st single shift register in each of the m second n-cell shift registers is the input of this second n-cell shift register for transmitting a logical zero and is zero input of the corresponding one of the m pairs of input register unit, a second memory; a second input of the 1st single shift register in each of the m second n-cell shift registers is the input of this second n-cell shift register for transmission to the logical unit and is a single input of a corresponding one of the m pairs of inputs of the unit registers of the second memory.

6. The device according to claim 1, characterized in that the switch has m first logic conjunction (elements), the second inputs of which are the first m inputs of the switch and connected to respective m outputs of the block p is Gustrow first memory; the first logical disjunction (OR element), each of the m inputs is connected to the output of the corresponding one of the m first conjunction, and the output is connected with the second inputs of the m second logic conjunction (elements), at the first input of each of which, one of the m first 2m of the second inputs of the switch and at the same time one of the control inputs of the device for sorting a two-dimensional array of data to control the switching of the shift register block registers the first and second memory between them, filed a corresponding one of the m first control signal; the first input of the first conjunction are second from the second input switch, each of which serves one of the m second control signals, which control inputs of the device for sorting a two-dimensional array of data; the output of each of the m second conjunction connected to the input of the corresponding one of the m first inverter and the first input of the corresponding one of the m third conjunction, the second inputs of which are connected together and are the third input of the switch for applying an external shear pulses; the output of each of the first inverter is connected to the first input of the corresponding one of the m fourth conjuncture, the second input of each of which is connected with the second input of the corresponding third conjun the Torah; the third inputs of the respective third and fourth of conjunction connected with each other and with the respective first inputs of the second conjunction; the outputs of the respective third and fourth of conjunctural form m pairs of outputs, which are the outputs of the switch and connected to the corresponding inputs of the unit registers of the second memory.

7. The device according to claim 1, characterized in that the switch has m2fifth logic conjunction (elements), each of which belongs to one of the m-fifths of disjoint sets containing m elements And symbolizing one (one) of m rows (columns) of a two-dimensional matrix, and simultaneously belongs to one of m sixth disjoint sets containing m elements And symbolizing one (one) of m columns (rows) of a two-dimensional matrix; at the first input of each of the fifth element And filed a corresponding one of the m2control signals, which is the second inputs of the switch and simultaneously control inputs of the device for sorting a two-dimensional array of data to control the switching blocks of registers of the first and second memory among themselves; the second inputs of the fifth element And forming a single (one) column (row), i.e. belonging to one of m sixth disjoint sets, are connected together and are connected with the corresponding output, one is from m, unit registers the first memory and m are the first inputs of the switch; the outputs of each of the m fifth elements And forming a row (column), connected to respective m inputs of the corresponding second logical disjunctor, one of the m; the output of each of the m second disjunction connected to the input of the corresponding one of the m second inverter and the first input of the corresponding one of the m-sixths of conjunction, the second inputs of which are connected together and are the third input of the switch for applying an external shear pulses; the output of each of the second inverter is connected to the first input of the corresponding one of the m seventh conjuncture, the second input each of which is connected with the second input of the corresponding sixth conjuncture; the outputs of the respective sixth and seventh of conjunctural form m pairs of outputs, which are the outputs of the switch and connected to the corresponding inputs of the unit registers of the second memory.



 

Same patents:

FIELD: computer science.

SUBSTANCE: device has n-1 logic modules, each of which has register, locking and unlocking keys, ROM device.

EFFECT: broader functional capabilities due to possible sorting of n (n ≥ 2) m-digit binary numbers, set by binary signals.

2 dwg

FIELD: computer science.

SUBSTANCE: device has numeric conversion block for converting numbers to digit-wise signals, block for forming selection strobes, commutator of selection of minimal or maximal number.

EFFECT: higher speed of operation.

4 cl, 3 dwg, 1 tbl

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

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

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

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

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

Up!