US 4,410,960 AGranted

Sorting circuit for three or more inputs

AssigneeNippon Electric Co., Ltd.

InventorYoshihiro Kasuya

Life of this patent

Estimating the term…

Loading patent…

Abstract

A sorting circuit for sorting three inputs representative of numerical values into first through third outputs representative of the values in the ascending order, checks three binary bits of input sequences supplied thereto at a time from the most significant bit. When only one of the three checked bits is found to be logic "0" and logic "1" for the first time, the sequence including the only one bit represents the minimum and the maximum, respectively. As soon as only one of two bits of the sequences except for the sequence representative of the minimum is subsequently found to be logic "1," the sequence including the only one subsequently found bit represents the maximum. In this manner, the circuit produces the outputs. It is possible to form an array of such three-input-output sorting circuits and conventional two-input-output sorting circuits for use in sorting a multiplicity of inputs. A similar array can be formed for inputs, an integral multiple of four in number, by four-input-output sorting units, each supplied with two sets of ascendingly ordered inputs. The inputs are supplied to the array through a plurality of two-input-output sorting units. The last-mentioned sorting circuit can be formed to be operable either in bit series or in bit parallel.

Claims8

Dependent claims

A sorting circuit for sorting three input values into first through third ascendingly ordered output values, said input values being represented by three input sequences, respectively, said first through said third output values being represented by first through third output sequences, respectively, each of said input and said output sequences being a time sequence having a prescribed number of binary bits arranged from the most significant bit to the least significant bit, said input and said output sequences thereby having corresponding bits, each binary bit having either of a logic "0" and a logic "1" level at a time, said sorting circuit comprising:

state specifying means for specifying any one of an initial state, six first-level states, and six second-level states at a time, each first-level state being accompanied by two second-level states with said two second-level states assigned to two first-level states including said each first-level state, respectively, so that each second-level state may indicate a particular order among said input values, said initial state being a state in which the order of said input values is not yet definite, each first-level state being another state in which the order is determined for only one input value, each of the two second-level states accompanying the last-mentioned first-level state being still another state in which the order is determined for two input values except for said only one input value;
means for resetting said state specifying means into said initial state;
checking and driving means coupled to said state specifying means for checking three corresponding bits of the respective input sequences from time to time to drive, when only one bit is checked to have one of the logic "0" and the logic "1" levels with the two binary bits corresponding thereto checked to have the other of the logic "0" and the logic "1" level for the first time after said state specifying means is reset into said initial state, said state specifying means from said initial state to one of said first-level states that is predetermined according to the input sequence in which said only one bit is present, said checking and driving means subsequently driving said state specifying means from said one first-level state to one of the two second-level states accompanying said one first-level state when a particular bit and the binary bit corresponding thereto of two input sequences except for the input sequence in which said only one bit is present are checked to have a predetermined one and the other of the logic "0" and the logic "1" levels, respectively, for the first time after said state specifying means is driven to said one first-level state;
and
an output circuit coupled to said state specifying means for arranging said input sequences into said first through said third output sequences according to said initial state, said one first-level state, and said one second-level state.

2 more elements

A sorting circuit for sorting n circuit input values into first through n-th ascendingly ordered circuit output values where n represents a predetermined natural number, said input values being represented by n input sequences, respectively, said first through said n-th output values being represented by first through n-th output sequences, respectively, each of said input and said output sequences being a time sequence of a prescribed number of binary bits arranged from the most significant bit to the least significant bit, each binary bit having either of a logic "0" and a logic "1" level at a time, said sorting circuit comprising:

an array of a plurality of first-kind sorting units and a plurality of second-kind sorting units, said first-kind and said second-kind sorting units being connected to one another according to a predetermined rule, each first-kind sorting unit having two input leads and a smaller and a greater value output lead and being responsive to two unit input values supplied to the respective input leads for supplying the smaller and the greater value output leads with the smaller and the greater of the two unit input values in a period related to said prescribed number, each second-kind sorting unit having three input leads and a minimum, a medium, and a maximum output lead and being responsive to three unit input values supplied to the three input leads, respectively for supplying the minimum, the maximum, and the medium output leads in said period with the minimum and the maximum of the three unit input values and a remaining one of the three unit input values, respectively;
first means for supplying the respective input sequences bit by bit to prescribed ones of said second-kind sorting units;
and
second means connected to prescribed ones of the smaller and the greater value output leads of said first-kind sorting units and to prescribed ones of the minimum, the medium, and the maximum output leads of said second-kind sorting units for producing bit by bit n output sequences.

1 more element

A sorting circuit for sorting 4n circuit input values into first through 4n-th ascendingly ordered output values where n represents a natural number except for unity, said input values being represented by 4n input sequences, respectively, said first through said 4n-th output values being represented by first through 4n-th output sequences, respectively, each of said input and said output sequences being a sequence of a prescribed number of binary bits arranged from the most significant bit to the least significant bit, each binary bit having either of a logic "0" and a logic "1" level, said sorting circuit comprising:

2n two-input-output sorting units, each having two input leads and a smaller and a greater value output lead and being responsive to two unit input values supplied to the respective input leads for supplying the smaller and the greater value output leads with the smaller and the greater of the two unit input values;
means for supplying the respective circuit input values to said two-input-output sorting units as the unit input values thereof;
an array of a plurality of four-input-output sorting units, each having a smaller and a greater value input lead of a first set, a smaller and a greater value input lead of a second set, and first through fourth output leads, the sorting units in said array being arranged in first through 2n-th stages, each odd-numbered stage comprising first through n-th four-input-output sorting units, each even-numbered stage comprising first through (n-1)-th four-input-output sorting units, the smaller and the greater value input leads of the first-stage sorting units being connected to the smaller and the greater value output leads of said two-input-output sorting units, respectively, the first-set smaller and greater value input leads and the second-set smaller and greater value input leads of a p-th q-th-stage sorting unit, where p represents each of natural numbers between one and (n-1), both inclusive, and where q represents an even number between two and 2n, both inclusive, being connected to the third and the fourth output leads of the p-th (q-1)-th-stage sorting unit and the first and the second output leads of the (p+1)-th (q-1)-th-stage sorting units, respectively, the first-set smaller and greater value input leads and the second-set smaller and greater value input leads of the first r-th-stage sorting unit, where r represents an odd number between three and (2n-1), both inclusive, being connected to the first and the second output leads of the first (r-2)-th-stage sorting unit and the first and the second output leads of the second (r-1)-th-stage sorting unit, respectively, the first-set smaller and greater value input leads and the second-set smaller and greater value input leads of the n-th r-th-stage sorting unit being connected to the third and the fourth output leads of the (n-1)-th (r-1)-th-stage sorting unit and the third and the fourth output leads of the n-th (r-2)-th-stage sorting unit, respectively, the first-set smaller and greater value input leads and the second-set smaller and greater value input leads of an s-th r-th-stage sorting unit, where s represents each of natural numbers between one and (n-1), both inclusive, being connected to the third and the fourth output leads of the (s-1)-th (r-1)-th-stage sorting unit and the first and the second output leads of the s-th (r-1)-th-stage sorting unit, respectively, each four-input-output sorting unit thereby supplying the values supplied to the four input leads thereof to the first through the fourth output leads thereof in the ascending order;
and
means for producing said first through said 4n-th output values from the first and the second output leads of the first (2n-1)-th-stage sorting unit, the first through the fourth output leads of the first through the (n-1)-th 2n-th-stage sorting units, and the third and the fourth output leads of the 2n-th (n-1)-th-stage sorting units, respectively.

2 more elements

Dependencies are inferred from the claim text.