JPS60695B2 - Three input/output classification device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a binary value sorting device that rearranges three numerical values in order of value and outputs the rearranged values.

Classifying and processing large amounts of information is one of the strengths of digital computers, and is one of the most important processes that is indispensable for file operations and the like.

Among these, the operation of sorting a plurality of numerical values in order of size (largest or smallest) is an example of the simplest and basic classification process, and is performed by repeating simple numerical comparisons. The issue here is the time spent on classification processing.

Particularly when there is a large amount of information to be classified, if the above-described simple repetitive operation is applied, an enormous amount of processing time will be required in proportion to the amount of data. For this reason, efforts are being made to shorten the processing time by applying variously devised classification algorithms. Furthermore, as an example of a method to solve such a problem, Tominaga and Hirayama, ``A method of content addressing in file memory,'' is published in the Institute of Electronics and Communication Engineers Computer Research Group Material, January 21, 1972, Material No. EC.
71-61 (1972-01) (hereinafter referred to as Document 1), a parallel classification processing method is proposed.

According to this method, the basic cell is a classification circuit that compares two binary values bit by bit, determines the order of magnitude, and outputs it, and these classification cells are arranged in an array and combined by regular combinations. A parallel classification processing device has been constructed using these methods, achieving faster processing. In this case, the advantage is that the individual classification cells that make up the device have a simple structure, but in order to simultaneously classify a large amount of information, it is necessary to install a number of classification cells that correspond to the amount of data. The biggest drawback is that the processing time increases as the device becomes larger. on the other hand,
Advances in integration technology have made it possible to accommodate complex and large-scale circuits on a single chip. Considering this fact together with the method of configuring the device described above, increasing the functionality of the classification cell appropriately and reducing the number of elements that make up the device will result in a smaller device and faster processing. Although this can be used as a means, an increase in processing time cannot be avoided. In view of the above circumstances, it is an object of the present invention to provide a three-input/output classification device that can perform more advanced functions as a component of a parallel classification processing device, is capable of high-speed processing, and has a structure that allows for integration. .

According to the present invention, in an apparatus for sequentially inputting three binary values from the most significant bits and sorting the three binary values in order of magnitude, six states of an initial state, a first level, and a second level are provided. a memory circuit that distinguishes and represents the internal state of a one-needle circle consisting of six states, a drive circuit having three input signal lines, and an output circuit having three output signal lines,
The drive circuit sequentially determines combinations of three input signals inputted sequentially from the upper bits of the three binary values, drives the memory circuit, and determines the internal state of the memory circuit based on the successively determined results. When the order of none of the three binary values is determined, it is kept in the initial state, and when the order of any one of the three binary values is determined based on the results of sequential determination, the order is changed from the initial state to the first state. Transition to one predetermined state among the six states of the level,
Furthermore, based on the results of the sequential determination, the transition state of the first level is maintained until the order of the remaining two binary values whose order has not yet been determined is determined, and the order of the remaining two binary values is determined. When the transition is made from the transitioned state of the first level to any predetermined state among the six states of the second level, the order relationship of the three binary values is determined according to the sequentially determined results. The classified order relationships are classified and stored in each of the 13 internal states of the storage circuit, and the output circuit rearranges the three input signals according to the classified order relationships, and stores the classified order relationships separately for each of the 13 internal states of the storage circuit. A three-input/output classifier is obtained that outputs to three output signal lines. Next, the present invention will be explained in detail with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of a three-input/output classification device implemented according to the prior art, and is a diagram for pointing out its drawbacks. 11, 12, and 13 are shift registers, each of which stores a binary value to be classified.

20 is a three-input/output classification device constructed according to the prior art.

21, 22, and 23 are two input/output classification cells, and the two binary values described in Document 1 are input sequentially from the upper bits, and the order of magnitude is determined by determining the combination. , is a circuit that sequentially outputs a small value to one of two output signal lines and a large value to the other from the upper bit.

That is, according to the prior art, the three-input/output classification device 20' can be constructed by combining three two-input/output classification cells in three stages. 101, 102, and 103 are output signal lines of the shift registers 11, 12, and 13, respectively, and are also input signal lines of the three-input/output classification device 20.

201, 202, 203 are output signal lines of the three input/output classification device 20, and at the same time, they are the output signal lines of the shift register 1, respectively.
It is also the input signal line 12 and 13.

X, , X2, and X3 are shift registers 11 and 12, respectively.
, 13 represents the input signal of the three-input/output classification device 20. Z,,Z,Z3
represents a 1-bit output signal output from the three-input/output classification device 20. 100 is a signal line that supplies the synchronization signal C. By this synchronization signal C, the numerical values stored from each shift register 11, 12, 13 are sequentially output from the upper bits, and input signals X, .
Supplied as X2 and X3.

The input signals X, , X2, and X3 are input to each two input/output classification cells 21,
22, 23 and the ordered output signals Z, B,
Z3 is obtained. The output signals B, Z2, and Z3 are again sequentially shifted into the shift registers 11, 12, and 13 and stored. When this operation is completed for one cycle, that is, for the bit length of the shift register, the numerical values stored in the shift registers 11, 12, and 13 are rearranged in order of size. Furthermore, the following measures are required to ensure that such operations are performed accurately.

Delay circuits 24 and 25 supply the synchronizing signal C to the two-input/output classification cells 22 and 23, respectively, at appropriate timing.

This is to prevent malfunctions due to sequential operation of each two-input/output classification cell and delay in propagating signals by synchronizing circuit operations. However, this measure slows down the circuit operation, and the effect becomes even more pronounced when a larger classifier is configured with this three-input/output classifier, which is a drawback of the prior art. Next, a description will be given of the present invention in which the three-input/output classification device 20 is implemented by other means.

FIG. 2 is a diagram for explaining the principle of the present invention, and is a state transition diagram defining the operation of the three-input/output classification device according to the present invention.

Corresponding to Figure 1, the input/output signals are expressed as X,, X2, X3 and Z,, Z, Z3, and in particular, the numerical values corresponding to each input/output signal are expressed as the numerical value X,, numerical value X2, numerical value X3, etc. . What this state transition diagram means is three binary values X, ,
The combinations of input signals X, , X2, X3 obtained by daily extracting X2, X3 from the upper bits are sequentially classified, and the output signals Z, , Z,
The purpose is to clearly show the procedure for obtaining Z3.

In the figure, So,S,,......,S,2 are internal state names, and in particular, So is the initial state, S. ，・・・・・・
......, S6 is the first level state, S7, ......
S. 2 is called the second level state.

401, 402, etc. are arrows indicating transitions between internal states, and symbols such as X, X2×3, Represents a combination.

As an example, an arrow 401 indicates that in the initial state So, when the combination of input signals becomes X, X2×3, a state transition to the first level state S occurs. Here X,
X2×3 is (X,,X2,X3)=(0,0,1), and X,X2 are (X,,X2)=(0,1), and X3 is either 0 or 1. But it means it's okay. Although omitted to simplify the drawing, if a combination of input signals other than those described occurs, the same state remains. It is also assumed that a reset signal R input separately causes a state transition from all states to the initial state So. Furthermore, descriptions of omitted output signals will be made later in the description. Initial state S. is the initial state in which the operation begins, and the order of magnitude of any of the numerical values X, , X2, and X3 is not determined. In the initial state So, all combinations of input signals X, , X2, and ，，・・・・・・・・・
. . . , S6.
First level state S,,......,S6
corresponds to each of the states in which only one of the numerical values X, , X2, and X3 is ranked (classified into six cases). For example, in the initial state So, "When the combination of input signals is X, X2 × 3 or X. When X2×3, a state transition occurs to state S, and when X,
2 is the number X. represents the state in which is determined to be the minimum, and so on. If the seal is in one of the first level states S, , ......, S6, the combination of input signals for the remaining two numbers whose order is not determined is examined, It remains in the same state until the order is determined, and once the order is determined, it enters the second level state S7,......,S
, 2 to a predetermined state.

Second level state S7,・・・・・・・・・・・・,SI
2 corresponds to each of the states in which all the orders of the numbers X, , X2, and X3 are determined (classified into six cases).

As an example, in state S, where the numerical value X3 is determined to be the maximum, the remaining two numerical values X,,X2 are compared, and when the combination of input signals is
．． . Also, in state S2 where the numerical value X is determined to be the minimum, state S? when X2×3? A transition occurs. In other words, state S7 is the numerical value
．． For example, it represents a state in which it is determined that the order is 1. From the order relationship of the three -adic values implied by the valley interior pillow state explained above, the output signals Z, Z2, Z
is determined as follows.

In the initial state So, any of the input signals X, , X2, and X3 may be output to the output signals B, Z2, and Z3.

In each state of the first level, as an example, in state S, the numerical value X3 is determined to be the maximum, so the input signal X3 is output to the output signal Z, and the input signal , , X2 may be output. Also, in state S4, since the numerical value Any of the signals X, X2 may be output. In each state of the second level, for example, state S7
, it was determined that the numerical values were X, MiX2MiX3, so the input signals X, , X2,
3, respectively. From the above explanation, all the regularities of this state transition table can be easily understood.

To summarize the above explanation, the principle of the present invention is to sequentially judge the combinations of three input signals that are input sequentially from the high-order bits of the three binary values, and first, one of the three binary values is A pre-ordered classification procedure is given to determine the order of the remaining two binary values, and the order relationship of the three binary values classified in this way is expressed as an internal state. and to rearrange and output the input signals according to the order relationship implied by each internal state.

FIG. 3 shows an embodiment of a three-input/output classification device according to the present invention.

Note that the same reference numbers are used for the same signal lines and signals as in FIG. FIG. 3a is a circuit diagram showing a specific configuration of a drive circuit and a memory circuit. 30-1,...
. . . , 30-6 is a part of a drive circuit and a memory circuit, all of which have the same circuit configuration, and their respective input/output signal lines are arranged in the same order.

The details of the circuit configuration are shown inside block 30-1. 31,32,・・・・・・・・・・・・,3
9 is a NAND gate.

NAND gates 36 and 37 and 38 and 39 each form part of a set IJ set flip-flop or storage circuit. NAND gate 31,......
35 constitutes a part of the drive circuit. The four rivers are NOR gates, and 41, 42, and 43 are inverters. 104
is a signal line that supplies the reset signal R.

300 is an output signal line of the NOR gate 40, which is in an initial state S.

A state signal Y corresponding to . convey. 301,……,
306 are blocks 30-1, respectively.
, 30-6, and corresponds to the "first level state S, . . . S6, state signal Y, . . . , tell Y8.

307, ……, 312 are blocks 30-1, respectively.
, 30-6, which is the second level state S7, . . .
..., status signal Y7, ... corresponding to S,2
......, tell Y, 2.

Status signal Yo, Y, , ......, Y,
Only one of 2 becomes 1, and the corresponding internal state S
o, S, ......", S, 2. When the reset signal R is set to 0, the NAND gates 36 and 37, 38 and 39, etc. All constituent flip-flops are turned off.

That is, all of the state signals Y, . In this way, the initial state So is set, and then the reset signal R is set to 1 and the operation is started. NA
When the state signal Yo is 1, the ND gate 33 detects the input signal combination
The flip-flop constituted by is turned on, that is, the state signal Y is set to 1. Further, when the state signal Y becomes 1, the state signal Yo becomes 0 from the NOR gate 4. This is the initial state S. This means that a state transition has occurred from state S to state S.
When the state signal Y is 1, the NAND gates 32 and 35 detect the combination of input signals X and X2 and set the state signal Y to 0 and the state signal Y7 to 1. Similarly, the NAND gates 31 and 34 are connected to the state signal Y. When is 1, the input signal combination X,×2 is detected and the state signal Y, is set to 0, and the state signal Y,2 is set to 1. Other block 30-2,
The circuit operation of . . . , 30-6 is also exactly the same as this, and the state transition shown in FIG. 2 is accurately performed by this circuit configuration. FIG. 3b is a circuit diagram showing a specific configuration of the output circuit.

Blocks 50-1, 50-2, and 50-3 are part of the output circuit, and all have the same circuit configuration. The arrangement order of the input and output signal lines of each block 50-1, 50-2, and 50-3 is also the same. Details of the circuit configuration are shown in block 50.
- is shown inside. 51, 55, 56,……,
59 is an AND gate.

52, 53, and 54 are OR gates.

It is an AND gate with 6 rivers.

The output signal line 201 is wired O of each output signal line of the AND gate 60, AND gates 55, 56, and the corresponding AND gates of the other blocks 50-2, 50-3.
It is R. The output signal line 202 is an AND gate 57, 58
and the corresponding A of other blocks 50-2, 50-3
This is a wired OR of each output signal line of the ND gate. Output signal line 203 connects AND gate 59 and other blocks 50
This is a wired OR of the output signal lines of the corresponding AND gates 12 and 50-3. In order to explain the operation of this output circuit, a logical formula derived from the circuit diagram is shown below. Z,=X,X2×3Y.

10×, X2Y, 10X2X3Y50X, X3Y30×, (
Y2 ten Y7 ten Y8) ten x two (Y6 ten Y,. ten Y, 2) ten x three (Y4 ten Y9 ten Y,.).・・・．・・・． ...(1-
1) Z2=×,X2(Y.

10Y4) 10×2×3 (Y. 10Y2) 10×,
I + Y5 ten Y one ten YI. ) 10×3 (Y30Y50Y80Y,,) ......(1-2) Z3=×, (Y20Y
70Y8) (Y, 10Y30Y90Y, 2) 10×2 (Y6
10Y,, 10Y, 2) (Y, 10Y5 0Y7 0Y,.) 10×
3 (Y40Y90Y,.) (Y30Y50Y80Y,,
) = ×, (Y.

10Y40Y50Y60Y,. 10Y,. ) ten x 2 (Y. ten Y2 ten Y3 ten Y4 ten Y6 ten Y9) ten x three (Y. ten Y, ten Y2 ten Y6 ten Y7 ten Y, 2)...・．． ．． ...(1-3) These logical formulas can be confirmed in more detail as follows.

In the case of the initial state So, that is, Yo=1, the above logical formula becomes ZI=XIX2×3 Z2=XIX2×2×30 XIX3 Z3:XI+X2×3.

This relationship holds that the input signals X, , Z, and Z3 are
This indicates that either X2 or X3 is output respectively. As an example, (X,,X2,X3)=(0,0
, 0) and (1, 1, 1), respectively (Z,,Z2
, Z3) = (0, 0, 0), (1, 1, 1), etc. As an example for the first level, in the case of state S, that is, Y,=1, and the above logical formula (1-1, 2, 3)
becomes ZI ni XIX2 Z2 ni XI x 2 Z3;X3.

This relationship indicates that the input signal X3 is output to the output signal Z, and one of the output signals Z, , Z is output to each. Regarding the second level, as an example state S
7, that is, Y7; 1, and the above logical formula (1-1, 2
・3) becomes Z, :X, Z2=X2 Z3=X3.

This relationship applies to input signals X,,X to output signals Z,,Z,Z3.
2 and X3 are output in this order. As explained above, this output circuit outputs the input signal X according to each internal state represented by the memory circuit of FIG. , , X2, X3 and outputs them.

Furthermore, as can be easily inferred from the above logical formula, this output circuit is designed to further ensure that the output rules in each state of the initial state or the first level are compatible with the output rules in each state that becomes the next transition destination. It is structured with strict conditions,
It enables high-speed operation. FIG. 4 is a circuit diagram showing another embodiment of the drive circuit and memory circuit. 70-1,・
. . . , 70-6 are blocks showing part of a drive circuit and a memory circuit, and each block has the same circuit configuration.

The arrangement of the input/output signal lines of each block 70-1, 70-2 is the same, and especially when the input signal of each block is inverted and input, The input end of each block is marked with a circle to simplify the drawing. Details of the circuit configuration of each block are shown inside block 70-1. 71, . . . , 75 are NAND gates.

NAND gates T4 and 75 constitute a set-reset IJ flop, or a part of a memory circuit. NAND gates 71, 72, and 73 are part of the drive circuit and detect the combination of input signals X, , X2, and X3 to drive the flip-flops. F,,......,F6
is the output signal of the flip-flop included in each block, and this combination changes the internal state So, S,...
......, represents S,2. Signal F...
..., when only one of each of F6 becomes 1, the state of the first level S,,...
・, corresponds to S6, and the signals F, and F2, F2 and F3,...
When only the roughness of two signals is 1, such as F6 and F, the second level state S7,...
......, corresponds to S,2. 81, 82, 83, 84, etc. are AND gates, and the above signals F,......
Detects the combination of ..., F6, and internal state S,...
..., state signal Y representing S,2, ...
..., Y,2 is generated.

Reference numerals 701 and 706 are output signal lines of blocks 70-1 and 70-16, which are specifically attached to clearly indicate the continuation relationship of the signal lines.

Other reference numbers or symbols whose explanations are omitted are shown in Figure 3a.
It is the same as in . The output circuit of this embodiment is exactly the same as that of FIG. 3b. Generally, there are many methods for deriving a logic circuit from the state transition diagram shown in FIG. 2, and the embodiments shown in FIGS. 3 and 4 are one example thereof.

For example, although a set-reset flip-flop is used in the above embodiment, it is easy to supply a synchronizing signal to it or change it to an O-type or JK-type flip-flop using well-known techniques. Can be implemented.

FIG. 5 is a diagram for more clearly explaining the operation of the three-input/output classification device according to the present invention.

As an example, it is assumed that the shift registers 11, 12, and 13 store three numerical values to be classified, "6,""5," and "3."

Each number is expressed in binary, with the most significant bits on the right. 20' is a three-input power classification device according to the present invention, and its internal state and three output signals are displayed.

11', 12', and 13' are shift registers 11, respectively.
, 12, and 13, and are specially separated to clearly indicate the numerical values obtained by ordering.

Therefore, 13' is the largest value, followed by 12'
, 11' are ordered and output. a, b,...
...・． . , e shows how each numerical value is processed one bit at a time from the most significant bit. Figure a shows the state at the beginning of the operation, and is in the initial state So.

At this time, input signal (X,,X2,X3)=(0,0,0
) is still in the initial state So in figure b because the order relationship is not determined. At this time, the next input signal (X, .
Since X2, X3)=(1, 1, 0), the numerical value X3 is determined to be the minimum, and the process moves to state S4 in diagram c. Furthermore, the next input signal (
The numerical values X, and X2 are determined by X,,X2)=(1,0), and the state S in figure d is reached. Move to. Here, the number X3<X2<
All of the ordering relationships that are ×, have been determined. Note that the output signals are output according to the above order relationship. From then on, shift registers 11, 12, 13 maintain this order relationship.
Operation continues until all remaining bits have been output. The result is figure e. By comparing figures a and e, it can be seen that the purpose was carried out correctly.

According to the above explanation, the three-input/output classification device according to the present invention is configured with a single cell, regardless of the combination of multiple cells, so internal signal delay is not a problem.
The effect is great through high-speed processing.

Furthermore, it is possible to configure circuits in a regular manner, and this is highly effective in terms of integration.

[Brief explanation of drawings]

FIG. 1 is a block diagram for explaining a three-input/output classification device and conventional technology, FIG. 2 is a state transition diagram for explaining the principle of the present invention, and FIG. 3 is a block diagram for explaining a three-input/output classification device according to the present invention. In the circuit diagram showing one embodiment, a is a circuit diagram showing a specific configuration of the drive circuit and storage circuit, b is a circuit diagram showing the specific configuration of the output circuit, and FIG. 4 is a circuit diagram showing the specific configuration of the drive circuit and storage circuit. FIG. 5, a circuit diagram showing another embodiment, is a diagram for explaining the operation of the three-input/output classification device of the present invention. In the figure, 11, 12, 13...shift register, 2
1, 22, 23... Two input/output classification cells, 24,
25...delay circuit, 30-1,...・・・
...30-6...Part of the drive circuit and memory circuit with the same configuration, 31, 32,...
・,39...NAND gate, 4 0...NO
R gate, 4 1, 42, 43... Inverter, 50-
1, 50-3... Part of the output circuit, 51,
55, 56, 60...
・・AND gate, 52, 53, 54...OR gate,
70-1, 70-6... Part of the drive circuit and memory circuit, 71, 70-6... Part of the drive circuit and memory circuit, 71,...
5...NAND gate, 8 1, 82, 83,
84 etc. It is an AND gate. O diagram, 2 figures, 3 figures (o), 3 figures (b), 4 figures, 5 figures

Claims (1)

[Claims] 1. In a device that sequentially inputs three binary values starting from the most significant bits, rearranges the three binary values in order of magnitude, and outputs the six states: the initial state, the first level, and the second level. The drive circuit comprises: a memory circuit that distinguishes and represents 13 internal states consisting of 6 states; a drive circuit having three input signal lines; and an output circuit having three output signal lines; sequentially determines the combinations of three input signals that are sequentially input to the three input signal lines starting from the upper bits of the three binary values, and drives the memory circuit to determine its internal state. If the order of none of the three binary values is determined as a result of the determination, it remains in the initial state, and when the order of any one of the three binary values is determined, it changes from the initial state to the first level 6. transition to one determined state out of the two states, and remain in the transitioned state of the first level until the order of the remaining two binary values whose order is not determined yet is determined, and the remaining two states are When the order of the binary values is determined, the storage circuit causes a transition from the transitioned state of the first level to any determined state among the six states of the second level, and the storage circuit storing the order relationship of the binary values that are sequentially classified according to the results of the analysis, distinguishing them for each of the 13 internal states;
The output circuit outputs the three output circuits according to the classified order relationship.
A three-input/output classification device, characterized in that the three input/output classification devices rearrange the three input signals and output the rearranged input signals to the three output signal lines corresponding to a predetermined order.