JP5512031B2 - Bit determination circuit, bit string data selection circuit, and bit string data sequential selection circuit - Google Patents

Description

The present invention relates to a bit determination circuit for determining a bit at the same bit position of a plurality of bit string data, and information for selecting a bit string data having a minimum value or a maximum value among the plurality of bit string data using the bit determination circuit Relates to a bit string data selection circuit for outputting. The present invention also relates to a bit string data sequential selection circuit that outputs information for extracting bit string data in ascending or descending order from a set of a plurality of bit string data using the bit string data selecting circuit.

In the technical field of information processing, a minimum value or a maximum value is obtained from a plurality of bit string data. The processing for obtaining the minimum value or the maximum value is performed by executing a program using a digital signal processor (DSP), for example, as shown in Patent Document 1 below. The DSP has a built-in device for obtaining a minimum value or a maximum value as hardware that operates under program control.

FIG. 1A is a diagram illustrating a processing example of the above-described conventional minimum value search processing, and FIG. 1B is a diagram illustrating a processing example of the above-described conventional maximum value search processing. As illustrated in FIGS. 1A and 1B, the conventional minimum value search process and maximum value search process search for a minimum value or a maximum value by repeatedly comparing the magnitudes of bit string data.

In the example of the minimum value search process shown in FIG. 1A, the bit string data group 101 that is a set of a plurality of bit string data is composed of four bit string data, D1, D2, D3, and D4. D1 = 111, D2 = 010, D3 = 011, D4 = 100.

As shown in FIG. 1A, in step 1, for example, bit string data D1 located at the head of the bit string data is set as a temporary minimum value 111a. Next, in step 2, the magnitude comparison 121a between the bit string data D1 and the next bit string data D2 is performed. Since the bit string data D2 is smaller than the bit string data D1, the bit string data D2 is set as a temporary minimum value 111b in step 3.

Next, in step 4, the magnitude comparison 121b of the bit string data D2 which is the provisional minimum value 111b and the next bit string data D3 is performed, and the bit string data D2 is smaller than the bit string data D3. Set as 111c.

Next, in step 6, the bit string data D2 which is the provisional minimum value 111c and the last bit string data D4 are compared in size 121c. Since the bit string data D2 is smaller than the bit string data D4, the bit string data D2 is converted into the true minimum value in step 7. It is determined as 111d.

The example of the maximum value search process shown in FIG. 1B also uses the bit string data group 101 as in the example of the minimum value search process shown in FIG. 1A, and D1 = 111, D2 = 010, D3 = 011, and D4, respectively. = 100.

As shown in FIG. 1B, in step 1, for example, bit string data D1 located at the head of the bit string data is set as a temporary maximum value 112a. Next, in step 2, the magnitude comparison 122a between the bit string data D1 and the next bit string data D2 is performed. Since the bit string data D1 is larger than the bit string data D2, the bit string data D1 is set as a temporary maximum value 112b in step 3.

Next, in step 4, the bit string data D1 having the provisional maximum value 112b is compared with the next bit string data D3 122b. Since the bit string data D1 is larger than the bit string data D3, the bit string data D1 is converted to the provisional maximum value in step 5. 112c is set.

Next, in step 6, the size comparison 122c of the bit string data D1 which is the temporary maximum value 112c and the last bit string data D4 is performed. 112d is determined.

The above-described maximum value / minimum value search processing is realized by software processing using hardware suitable for the maximum value / minimum value search. As disclosed in Patent Document 2 below, a plurality of comparisons are performed. What is realized by hardware processing using a container is also known.

Japanese Patent No. 3188467 JP 2010-224818 A

In the minimum value / maximum value search processing described in Patent Document 1 described above, two bit string data to be processed are sequentially selected by software control, and a magnitude comparison is executed. Therefore, when the number of bit string data increases, it is proportional to it. As a result, the processing time increases.
In addition, the minimum value / maximum value search processing described in Patent Document 2 requires a large number of comparators as the number of bit string data increases.

Therefore, the problem to be solved by the present invention is that even if the number of bit string data to be processed increases, the processing time does not increase proportionally, and the minimum value of a plurality of bit string data is not required without requiring a large number of comparators. It is an object to provide a hardware circuit for outputting information for selecting bit string data or outputting information for selecting bit string data having a maximum value among a plurality of bit string data.

According to one aspect of the present invention, N bits (N is an integer greater than or equal to 2) are extracted from the same bit position of each of N bit string data, and are the same consisting of N bits corresponding to each bit string data. A position bit string and a selection bit for selecting each bit of the same position bit string as a bit determination target or a non-selection bit for non-selection as a bit determination target, each consisting of N bits corresponding to each bit string data This is a bit extracted from the bit position next to the same bit position of each bit string data based on the bit of the same position bit string selected by the selection bit of the selected bit string and input to each bit string data. Select each bit of the next identically-positioned bit string consisting of the corresponding N bits. A non-selected bit to a selected bit or non-selection of each to provide a bit determination circuit for outputting a next selection bit string of N bits corresponding to the bit string data.

According to another aspect of the present invention, the bit determination circuit described above is connected in series for the bit width of the bit string data. And providing a bit string data selection circuit for outputting information for selecting the bit string data having the minimum value, or outputting information for selecting the bit string data having the maximum value among the plurality of bit string data, and further providing the bit string data. Provided is a bit string data sequential selection circuit for outputting information for extracting bit string data in ascending or descending order from a set of a plurality of bit string data using a selection circuit.

According to the present invention, even if the bit string data to be processed increases, the processing time does not increase proportionally, and the bit string data having the minimum value among a plurality of bit string data is selected without requiring a large number of comparators. A hardware circuit for outputting information for outputting or selecting information for selecting bit string data having a maximum value among a plurality of bit string data, and bit string data in ascending or descending order from a set of the plurality of bit string data A hardware circuit that outputs information for extraction can be provided.
Then, by using the hardware circuit provided by the present invention, the bit string data having the minimum value among the plurality of bit string data is obtained, or the bit string data having the maximum value among the plurality of bit string data is obtained, or Bit string data can be extracted from a plurality of bit string data in ascending or descending order.

It is a figure explaining the conventional minimum value search process. It is a figure explaining the conventional maximum value search process. It is a figure which illustrates notionally the minimum value selection process in the 1st Embodiment of this invention. It is a figure which illustrates notionally the maximum value selection process in the 2nd Embodiment of this invention. It is a figure which illustrates notionally the minimum value selection circuit in the 1st Embodiment of this invention. It is a figure which illustrates notionally the maximum value selection circuit in the 2nd Embodiment of this invention. It is a figure explaining the 1st Example of the bit determination circuit in the 1st and 2nd embodiment of this invention. It is a figure explaining the 1st Example of the bit determination circuit in the 3rd Embodiment of this invention. It is a figure explaining the 2nd Example of the bit determination circuit in the 2nd Embodiment of this invention. It is a figure explaining the 2nd Example of the bit determination circuit in the 3rd Embodiment of this invention. It is a figure explaining the 3rd Example of the bit determination circuit in the 1st and 2nd embodiment of this invention. It is a figure explaining the 3rd Example of the bit determination circuit in the 3rd Embodiment of this invention. It is a figure explaining the maximum value / minimum value selection circuit block and peripheral circuit examples in the third embodiment of the present invention. It is a figure which illustrates notionally the bit string data ascending order selection process in the 4th Embodiment of this invention. It is a figure which illustrates notionally the bit string data descending order selection process in the 5th Embodiment of this invention. It is a figure explaining the bit-sequence data sequential selection circuit block and peripheral circuit example in the 4th and 5th embodiment of this invention. It is a figure explaining the bit-sequence data sequential selection circuit block and peripheral circuit example in the 6th Embodiment of this invention. It is a figure explaining the example of the next selection bit setting circuit in the 4th, 5th, and 6th embodiment of this invention. It is a figure explaining the timing chart example of the bit string data sequential selection circuit in the 4th Embodiment of this invention.

Hereinafter, embodiments for carrying out the present invention will be described with reference to the drawings.
FIG. 2A is a diagram for conceptually explaining the minimum value selection processing in the first embodiment of the present invention. The first embodiment of the present invention relates to minimum value selection. The bit string data group 101 illustrated in FIG. 2A is the same as that illustrated in FIGS. 1A and 1B.

As shown in FIG. 2A, in step 1, “1111” is set as an initial value in the selected bit string 210a. E1, E2, E3, and E4 described on the left side of the selected bit string 210a indicate bits of the selected bit string, and each bit of E1, E2, E3, and E4 corresponds to the bit string data D1, D2, D3, and D4, respectively. ing. If the bit Ex of the selected bit string is “1”, the corresponding bit string data Dx is selected as a bit determination target described below. In the following description, the selected bit string may be represented by the symbol E.

In the bit string data group 101, bit positions 0, 1, and 2 of each bit string data are shown. The bit string obtained by extracting the bits surrounded by the dotted line for each bit position is the same position bit string. By extracting the bits at bit positions 0, 1, and 2 of the bit string data D1, D2, D3, and D4, the same position bit strings 240, 241, and 242 are configured. In step 2 and subsequent steps, reference numerals 240, 241, and 242 of the same bit string are omitted. In the following description, the same position bit string may be denoted by the symbol F.

In step 2, as shown by the bidirectional arrow 220a, the bit determination of the same position bit string 240 is performed by the selected bit string 210a.
In the first embodiment of the present invention, the bit determination determines whether the bit selected in the selected bit string is “0” among the bits in the same position bit string. Based on this determination result, the next selected bit string used as the selected bit string in the next step is output.

If it is determined in the above determination that the bit is “0”, the bit of the next selected bit string corresponding to the bit string data to which the selected bit, that is, the bit determined to be “0” belongs is set to “1”. If it is determined that the bit is “1”, the bit of the next selected bit string corresponding to the bit string data to which the selected bit, that is, the bit determined to be “1” belongs is set to “0”. Further, among the bits in the same position bit string, the bit of the next selected bit string corresponding to the bit string data to which the bit not selected in the selected bit string belongs is set to “0”.

In the example of FIG. 2A, since the selected bit string 210a is “1111” and the same position bit string 240 is “1001”, the next selected bit string 211a of the determination result is “0110” as indicated by the dotted arrow 230b.

In the next step 3, as shown by the bidirectional arrow 220b, the next selected bit string 211a that is the determination result in step 2 is used as the selected bit string 210b, and the bit positions 1 of the bit string data D1, D2, D3, and D4 are the same. Bit determination of the position bit string 241 is performed.

In the example of FIG. 2A, the selected bit string 210b is “0110”, the same position bit string 241 is “1110”, and all the selected bits of the same position bit string 241 are “1”, and therefore, as indicated by the dotted arrow 230c. In addition, the next selected bit string 211b of the determination result is “0110”, which is the same as the selected bit string 210b.

In the next step 4, as indicated by the bidirectional arrow 220c, the next selected bit string 211b, which is the determination result in step 3, is used as the selected bit string 210c, and the bit positions 2 of the bit string data D1, D2, D3, D4 are the same. Bit determination of the position bit string 242 is performed.

In the example of FIG. 2A, since the selected bit string 210c is “0110” and the same position bit string 242 is “1010”, the next selected bit string 211c as the determination result is “0100” as indicated by the dotted arrow 230d.

Since the determination of the bit at the least significant bit position is completed in step 4, it can be seen that the bit string data corresponding to the bit of the next selected bit string 211c which is “1” is the minimum value of the bit string data group 101.
In the example of FIG. 2A, as indicated by the arrow 250, it can be seen that the bit string data D2 corresponding to the bit E2 is the minimum value.

If the above processing steps are compared to the winning and remaining competitions, it is determined from the most significant bit to the least significant bit of the bit string data whether the bit at the same bit position of the winning bit string data is “0” or “1”. The bit string data of “1” is the winner and the bit string data of “1” is the loser, and the remaining is selected. If all the selected bits in the same position bit string are “1”, the selected bit string is output as the next selected bit string. If all the bits in the same bit position of the winning bit string data are “1”, the next is selected as a draw. This is equivalent to winning at the bit position.

In the above description, if the bit Ex of the selected bit string is “1”, the bit of the bit string data Dx corresponding to the selected bit string is selected as a bit determination target. However, if the bit Ex is “0”. It is apparent that the minimum value selection process can be performed even when the bit of the bit string data Dx corresponding to the bit string data Dx is selected as a bit determination target. Therefore, the bit Ex of the selected bit string indicating that the bit of the bit string data Dx is selected as the target of the bit determination is the selected bit, and the bit Ex of the selected bit string indicating that the bit of the bit string data Dx is not selected as the target of the bit determination. It can also be called a selection bit.

Further, although all bits are set to “1” as the initial value of the selected bit string, if a bit string data of a part of the minimum value in the bit string data group is selected, bits corresponding to the part of the bit string data are selected. Only “1” can be set.

Furthermore, the same bit string data may be included in the bit string data group. In this case, there is a possibility that a plurality of bits having a bit “1” exist in the next selected bit string that is the output of the bit determination at the least significant bit position.
The description of the bit of the selected bit string, the initial value, and the duplication of the bit string data is not limited to the first embodiment, but the second and third embodiments described later, and the fourth embodiment. The same holds true for the form, the fifth embodiment, and the sixth embodiment.

FIG. 2B is a diagram conceptually illustrating the maximum value selection process in the second embodiment of the present invention. The second embodiment of the present invention relates to maximum value selection. The bit string data group 101 illustrated in FIG. 2B is the same as that illustrated in FIG. 2A. Of the components described in FIG. 2B, the description of the same components as those described in FIG. 2A is omitted.

As shown in FIG. 2B, in step 1, “1111” is set as an initial value in the selected bit string 212a.
In step 2, as shown by a bidirectional arrow 221a, bit determination of the same position bit string 240 is performed by the selected bit string 212a.
In the second embodiment of the present invention, the bit determination determines whether or not the bit is “1” for the bit selected in the selected bit string among the bits in the same position bit string. Based on this determination result, the next selected bit string used as the selected bit string in the next step is output.

When it is determined that the bit is “1” in the above determination, the bit of the next selected bit string corresponding to the selected bit, that is, the bit string data to which the bit determined to be “1” belongs is set to “1”. If it is determined that the bit is “0”, the bit of the next selected bit string corresponding to the bit string data to which the selected bit, that is, the bit determined to be “0” belongs is set to “0”. Further, among the bits in the same position bit string, the bit of the next selected bit string corresponding to the bit string data to which the bit not selected in the selected bit string belongs is set to “0”.

In the example of FIG. 2B, since the selected bit string 212a is “1111” and the identical position bit string 240 is “1001”, the next selected bit string 213a of the determination result is “1001” as indicated by the dotted arrow 231b.
In the next step 3, as shown by the bidirectional arrow 221b, the next selected bit string 213a that is the determination result in step 2 is used as the selected bit string 212b, and the bit positions 1 of the bit string data D1, D2, D3, and D4 are the same. Bit determination of the position bit string 241 is performed.

In the example of FIG. 2B, the selected bit string 212b is “1001”, the identical position bit string 241 is “1110”, and the next selected bit string 213b of the determination result is “1000” as indicated by the dotted arrow 231c.

In the next step 4, as indicated by the bidirectional arrow 221c, the next selected bit string 213b, which is the determination result in step 3, is used as the selected bit string 212c, and the bit positions 2 of the bit string data D1, D2, D3, and D4 are the same. Bit determination of the position bit string 242 is performed.

In the example of FIG. 2B, since the selected bit string 212c is “1000” and the identical position bit string 242 is “1010”, the next selected bit string 213c of the determination result is “1000” as indicated by the dotted arrow 231d.

Since the determination of the bit at the least significant bit position is completed in step 4, it can be seen that the bit string data corresponding to the bit of the next selected bit string 213c which is “1” is the maximum value of the bit string data group 101.
In the example of FIG. 2B, it can be seen that the bit string data D1 corresponding to the bit E1 has the maximum value, as indicated by the arrow 251.

Next, a circuit according to the first and second embodiments of the present invention will be described with reference to FIGS. 3A and 3B. 3A and 3B, the description of the same parts as those in FIGS. 2A and 2B is omitted.

FIG. 3A is a diagram for explaining the outline of the minimum value selection circuit according to the first embodiment of the present invention.
In the data register group 301 illustrated in FIG. 3A, the bit string data group 101 illustrated in FIGS. 2A and 2B is stored. The selection bit register 310 stores the selection bit string 210a illustrated in FIG. 2A.
As shown in FIG. 3A, the minimum value selection circuit 300a includes a bit determination circuit 320a corresponding to the same position bit string 240, a bit determination circuit 320b corresponding to the same position bit string 241, and a bit determination circuit 320c corresponding to the same position bit string 242. Including. In the first embodiment, these bit determination circuits determine whether a bit is “0”. These bit determination circuits can basically use the same configuration.

The same-position bit strings 240, 241, and 242 from which the bits at the same bit position of the bit string data D1, D2, D3, and D4 stored in the data register group 301 are extracted are respectively obtained by 4-bit parallel buses 340a, 340b, and 340c. Input to the bit determination circuits 320a, 320b, and 320c.

The selected bit string stored in the selected bit register 310 is input to the bit determination circuit 320a through the 4-bit parallel bus 330a. The bit determination result output 310b of the bit determination circuit 320a is input to the bit determination circuit 320b through the 4-bit parallel bus 330b. Next, the bit determination result output 310c of the bit determination circuit 320b is input to the bit determination circuit 320c through the 4-bit parallel bus 330c. Further, the bit determination result output of the bit determination circuit 320c is input to the selection result register 360 through the 4-bit parallel bus 330d.
In the example of FIG. 3A, the selection result register 360 stores the next selected bit string 211c shown in FIG. 2A, and it can be seen that the bit string data D2 corresponding to the bit E2 has the minimum value as indicated by the arrow 350.

FIG. 3B is a diagram for explaining the outline of the maximum value selection circuit according to the second embodiment of the present invention.
In the data register group 301 illustrated in FIG. 3B, the bit string data group 101 illustrated in FIGS. 2A and 2B is stored. The selection bit register 310 stores the selection bit string 212a illustrated in FIG. 2B.
As shown in FIG. 3B, the maximum value selection circuit 300b includes a bit determination circuit 321a corresponding to the same position bit string 240, a bit determination circuit 321b corresponding to the same position bit string 241, and a bit determination circuit 321c corresponding to the same position bit string 242. Including. In the second embodiment, these bit determination circuits determine whether the bit is “1”. These bit determination circuits can basically use the same configuration.

The same-position bit strings 240, 241, and 242 from which the bits at the same bit position of the bit string data D1, D2, D3, and D4 stored in the data register group 301 are taken out by the 4-bit parallel buses 341a, 341b, and 341c, respectively. Input to the bit determination circuits 321a, 321b, and 321c.

The selected bit string stored in the selected bit register 310 is input to the bit determination circuit 321a through the 4-bit parallel bus 331a. The bit determination result output 311b of the bit determination circuit 321a is input to the bit determination circuit 321b through a 4-bit parallel bus 331b. Next, the bit determination result output 311c of the bit determination circuit 321b is input to the bit determination circuit 321c through the 4-bit parallel bus 331c. Further, the bit determination result output of the bit determination circuit 321c is input to the selection result register 360 via the 4-bit parallel bus 331d.
In the example of FIG. 3B, the selection result register 360 stores the next selection bit string 213c shown in FIG. 2B, and it can be seen that the bit string data D1 corresponding to the bit E1 has the maximum value as indicated by the arrow 351.

Next, an embodiment of the bit determination circuit will be described with reference to FIGS.
FIG. 4 is a diagram illustrating a first example of the bit determination circuit according to the first and second embodiments of the present invention. FIG. 4A shows a circuit configuration of a first example of a bit determination circuit common to the first and second embodiments of the present invention. FIG. 4B illustrates the input / output logic of the constituent elements of the first example of the bit determination circuit according to the first embodiment of the present invention. FIG. 4C illustrates the input / output logic of the constituent elements of the first example of the bit determination circuit according to the second embodiment of the present invention. In the following description, it is assumed that the bit string data group includes n bit string data. Each bit of the n-bit parallel bus may be represented by a subscript x.

As shown in FIG. 4A, the bit determination circuit 3211 includes a match determination unit 420, a total mismatch determination unit 430, and a determination result selector 440. The same position bit string F is input to the bit determination circuit 3211 via the n-bit parallel bus 340, and the selected bit string E is input via the n-bit parallel bus 330.

The input identical position bit string F and selected bit string E are input to the coincidence determination unit 420 and the all mismatch determination unit 430, respectively. The coincidence determination unit 420 performs an operation for each bit of the same position bit string F and the selected bit string E, and obtains a new bit string Q. (As described above, obtaining a new bit string having the same bit width by an operation for each bit of the bit string or obtaining one bit may be referred to as a bit string operation.) In the all mismatch judgment unit 430, the same position bit string D Then, R which is one bit is obtained by bit string operation of the selected bit string E.
Then, if the output R of the all mismatch determination unit 430 is “1”, the determination result selector 440 outputs the selected bit string E to the n-bit parallel bus 331 as the output bit string Z (next selected bit string), If the output R of the mismatch determination unit 430 is “0”, the bit string Q that is the output of the match determination unit 420 is output to the n-bit parallel bus 331 as the output bit string Z.

The logical expressions of the bit string operation Q of the coincidence determination unit 420 and the bit string operation R of the all mismatch determination unit 430 in the first embodiment of the present invention are described in FIG. 4B, and the coincidence determination unit in the second embodiment The logical expression of the bit string operation Q 420 and the bit string operation R of the all mismatch judgment unit 430 is shown in FIG.

As shown in FIG. 4B, in the case of the first embodiment in which the minimum value is selected, the bit Qx of the bit string Q that is the output of the bit string operation of the coincidence determination unit 420 is the same position bit string F. This is a logical product of the logical negation of the bit Fx and the bit Ex of the selected bit string E. Only Qx corresponding to “1” and Fx “0” is “1”, and the other bits of the bit string Q are “0”. . Further, the bit string operation R of the all mismatch judgment unit 430 is obtained by logically obtaining the logical negation of the logical negation of Fx and the logical product of Ex for every bit. The value of R is “1” only when Fx is “1” for all bits where Ex is “1”, and there is at least one bit where Ex is “1” and Fx is “0”. In this case, it is “0”.

Further, as described in FIG. 4C, in the second embodiment in which the maximum value is selected, the bit Qx of the bit string Q that is the output of the bit string calculation of the coincidence determination unit 420 is the same position bit string. This is a logical product of the bit Fx of F and the bit Ex of the selected bit string E, and only Qx corresponding to Ex = “1” and Fx = “1” is “1”, and the bits of the other bit strings Q are “0”. In addition, the bit string operation R of the all mismatch judgment unit 430 is obtained by taking the logical product of all the bits and negating the logical product of Fx and Ex for each bit. The value of R is “1” only when Fx is “0” for all bits where Ex is “1”, and there is at least one bit where Ex is “1” and Fx is “1”. In this case, it is “0”.

FIG. 5 is a diagram for explaining a first example of the bit determination circuit in the third embodiment of the present invention. The third embodiment of the present invention enables a minimum value selection and a maximum value selection with a common circuit.
FIG. 5A shows a circuit configuration of a first example of the bit determination circuit according to the third embodiment of the present invention. FIG. 5B illustrates the input / output logic of the constituent elements of the first example of the bit determination circuit according to the third embodiment of the present invention.

As shown in FIG. 5A, the bit determination circuit 3231 includes a determination bit setting unit 410 in addition to the match determination unit 420, the total mismatch determination unit 430, and the determination result selector 440 shown in FIG. 4. The determination bit setting unit 410 outputs a bit string P that is the same-position bit string F input from the parallel bus 340 in accordance with the determination bit I input by the serial bus 321 as it is or is inverted, and outputs a match determination circuit 420. And supplied to the all mismatch judgment circuit 430.

The determination bit I is “0” when the minimum value is selected, and the determination bit I is “1” when the maximum value is selected. Each bit Px of the bit string P shown in FIG. 5B is a logical sum of the logical product of negation of I and the negation of Fx and the logical product of I and Fx. That is, if I is “0”, Px is Fx, and if I is “0”, Px is the inverted bit of Fx.
Substituting the above Fx into Qx and R shown in FIG. 5B, the minimum value is selected in the same manner as shown in FIG. 4B, and the maximum value is selected in FIG. This is the same as shown in (c). Therefore, a common circuit can be used for selecting the minimum value or the maximum value.
The introduction of the determination bit setting unit 410 in the third embodiment described above is that the minimum value bit string data in the bit string data group has the maximum value when all bits of the bit string data in the bit string data group are inverted. This is based on bit string data.

FIG. 6 is a diagram for explaining a second example of the bit determination circuit in the second embodiment of the present invention. FIG. 6A shows a circuit configuration of a second example of the bit determination circuit according to the second embodiment of the present invention. FIG. 6B illustrates the input / output logic of the constituent elements of the second example of the bit determination circuit according to the second embodiment of the present invention.

As shown in FIG. 6A, the bit determination circuit 3212 includes a match determination unit 420, a total mismatch determination unit 430, and a determination result selector 440. The bit determination circuit 3212 receives the same-position bit string F through the n-bit parallel bus 340 and receives the selected bit string E through the n-bit parallel bus 330. The above configuration is the same as that of the first example of the bit determination circuit common to the first embodiment and the second embodiment shown in FIG. 4A, but is identical in this first example. While the determination and the total mismatch determination are performed in parallel, the one shown in FIG. 6A first performs the total mismatch determination, selects the determination result based on the result of the total mismatch determination, A match determination is performed based on the selection result.

The inputted identical position bit string F is inputted to the terminals on the 0 side of the all mismatch judgment unit 430 and the judgment result selector 440. The selected bit string E is input to the all mismatch determination unit 430 and the match determination unit 420. An n-bit bit string whose bits are all “1” is input to the terminal on the 1 side of the determination result selector 440. This bit “1” is used as the selection bit described above. The output R of the total mismatch determination unit 430 is connected to the selection terminal s of the determination result selection unit 440. If the value of R is “0”, the selected bit string F input to the terminal on the 0 side is displayed. If it is “1”, an n-bit bit string in which all bits input to the terminal on the 1 side are “1” is output to the coincidence determination unit 420 as a bit string Z.

As shown in FIG. 6B, the output R of the total mismatch determination unit 430 in the second embodiment for selecting the maximum value is the first output shown in FIG. This is the same as the embodiment.
In FIG. 6B, a logical expression of the output Z of the determination result selector 440 is described. This is because the logical expression of the output bit string Q of the coincidence determiner 420 is expressed. The logical expression for each bit of the output Z is the negation of R, the logical product of Fx, and the logical sum of R. Therefore, if R is “1”, Zx is R, and all the values of Zx are “1”. If R is “0”, Zx becomes Fx, so the determination result described above is selected. Since Qx is a logical product of Zx and Ex, Qx output to the parallel bus 331 is a logical product of Ex when R is “1” and Fx and Ex when R is “0”. This is the same as shown in (c).

As described above, the minimum bit string data of the bit string data group becomes the maximum bit string data when all the bits of the bit string data of the bit string data group are inverted. The bit determination circuit 3212 shown in FIG. 6A can also be used for minimum value selection by inputting a bit string obtained by inverting.

FIG. 7 is a diagram for explaining a second example of the bit determination circuit according to the third embodiment of the present invention. FIG. 7A shows a circuit configuration of a second example of the bit determination circuit according to the third embodiment of the present invention. FIG. 7B illustrates the input / output logic of the constituent elements of the second example of the bit determination circuit according to the third embodiment of the present invention.

As shown in FIG. 7 (a), the bit determination circuit 3232 has been described with reference to FIG. 5 (a) at the same position bit string F input to the bit determination circuit 3212 shown in FIG. 6 (a). A determination bit setting unit 410 is inserted. Therefore, since the logical expressions R, Zx, and Qx shown in FIG. 7B are obtained by substituting Px for Fx shown in FIG. 6B, further explanation is omitted.

FIG. 8 is a diagram for explaining a third example of the bit determination circuit in the first embodiment and the second embodiment of the present invention. FIG. 8A shows a circuit configuration of a third example of the bit determination circuit common to the first and second embodiments of the present invention. FIG. 8B illustrates the input / output logic of the components of the third example of the bit determination circuit according to the first embodiment of the present invention. FIG. 8C illustrates the input / output logic of the components of the third example of the bit determination circuit according to the second embodiment of the present invention.

As shown in FIG. 8A, the bit determination circuit 3213 includes a match determination unit 420, a total mismatch determination unit 431, and a determination result selector 440. The coincidence determination unit 420 receives the same position bit string F from the n-bit parallel bus 340 and receives the selected bit string E from the n-bit parallel bus 330, and performs bit string calculation of the same position bit string F and the selected bit string E. Thus, the bit string Q is obtained. In the above configuration, the match determination is performed first, then the total mismatch determination is performed based on the match determination result, and the determination result is further selected based on the non-determination result.

The bit string Q is input to the all mismatch determination unit 431 and the determination result selector 440. The total discriminator 431 obtains R, which is one bit, from the value of each bit Qx of the bit string Q.
Then, if the output R of the all mismatch determination unit 431 is “1”, the determination result selector 440 outputs the selected bit string E to the n-bit parallel bus 331 as the output bit string Z (next selected bit string). If the output R of the mismatch determination unit 431 is “0”, the bit string Q that is the output of the match determination unit 420 is output to the n-bit parallel bus 331 as the output bit string Z.

As shown in FIG. 8B, in the case of the first embodiment in which the minimum value is selected, the bit Qx of the bit string Q that is the output of the bit string calculation of the coincidence determination unit 420 is the same position bit string F. This is a logical product of the negation of the bit Fx and the bit Ex of the selected bit string E. Only Qx corresponding to Ex = “1” and Fx = “0” is “1”, and the other bits of the bit string Q are “0”. Further, the output R of the all mismatch judgment unit 431 is a negative logical product of Qx. Therefore, the value of R is set to “1” only when there is no combination of bits where Ex is “1” and Fx is “0”, in other words, when all Fx whose Ex is “1” is “1”. Therefore, the determination result selector 440 outputs the selected bit string E, and since it is “0” in other cases, the determination result selector 440 outputs the bit string Q that is the output of the coincidence determiner 420.

Further, as described in FIG. 8C, in the second embodiment in which the maximum value is selected, the bit Qx of the bit string Q that is the output of the bit string operation of the coincidence determination unit 420 is the same position bit string. This is a logical product of the bit Fx of F and the bit Ex of the selected bit string E, and only Qx corresponding to Ex = “1” and Fx = “1” is “1”, and the bits of the other bit strings Q are “0”. Further, the output R of the all mismatch judgment unit 431 is a negative logical product of Qx. Therefore, the value of R is set to “1” only when there is no bit combination in which Ex is “1” and Fx is “1”, in other words, only when Fx having Ex “1” is all “0”. Otherwise, it is “0”. If the value of R is “0”, the determination result selector 440 outputs the bit string Q that is the output of the coincidence determiner 420, and if the value of R is “1”, the determination result selector 440 outputs the selected bit string E. Output.

FIG. 9 is a diagram for explaining a third example of the bit determination circuit according to the third embodiment of the present invention. FIG. 9A shows a circuit configuration of a third example of the bit determination circuit according to the third embodiment of the present invention. FIG. 9B illustrates the input / output logic of the components of the third example of the bit determination circuit according to the third embodiment of the present invention.

As shown in FIG. 9 (a), the bit determination circuit 3233 has been described with reference to FIG. 5 (a) at the same position bit string F input to the bit determination circuit 3213 shown in FIG. 8 (a). A determination bit setting unit 410 is inserted. Therefore, since the logical expressions of R and Qx shown in FIG. 9B are obtained by substituting Px for Fx shown in FIG. 8C, further explanation is omitted.

FIG. 10 is a diagram for explaining an example of the maximum value / minimum value selection circuit block and its peripheral circuits in the third embodiment of the present invention. A maximum value / minimum value selection circuit 300c shown in FIG. 10 is suitable for bit string data having n bit widths of m, and a bit determination circuit 3201 for determining the bit of the same position bit string of the most significant 0th bit. M bit determination circuits are connected in series from the bit determination circuit 320m for determining the bit of the same position bit string of the lowest (m-1) th bit.

As peripheral circuits, a selection bit register 310 for setting an initial value of a selection bit string, a data register group 301 for storing a bit string data group, a selection result register 360 for holding an output of a bit determination circuit at the final stage, and a determination bit are held. A determination flag 390 is illustrated.

The selected bit string set in the selected bit register 310 is input to the bit determination circuit 3201. The determination bit held in the determination value flag 390 is supplied in parallel to the m-stage bit determination circuit via the bus 321, and the maximum value / minimum value selection circuit operates as the minimum value selection circuit. Determine what works as.
From the data register group 301, the same position bit string of the 0th bit from the same position bit string to the (m−1) th bit is supplied from the bit determination circuit 3201 to the bit determination circuit 320m via the n-bit parallel buses 3401 to 340m. .

Each bit determination circuit determines the bit in the same position bit string based on the input selection bit string, calculates the next selected bit string, and outputs the selected bit string to the next bit determination circuit. The output of the final-stage bit determination circuit 320m is held in the selection result register 360, and can be used to specify the minimum bit string data or the maximum bit string data stored in the data register group 301.

As is apparent from the detailed description of the first to third embodiments of the present invention, according to the present invention, the minimum value selection circuit, the maximum value selection circuit, and the maximum / minimum value selection circuit are configured by the passive circuit. Therefore, high speed operation is possible. Moreover, it will be apparent to those skilled in the art that various modifications can be made to the embodiment of the present invention in addition to the above description.

Next, a bit string data sequence that outputs information for extracting bit string data in ascending or descending order from a set of a plurality of bit string data using the above-described minimum value selection circuit, maximum value selection circuit, or maximum value / minimum value selection circuit The selection process will be described. In the following description, the terms maximum value / minimum value selection circuit and maximum value / minimum value selection processing are used to include the minimum value selection circuit and minimum value selection processing, and the maximum value selection circuit and maximum value selection processing. There is a case.

As described above, in the maximum value / minimum value selection process, the initial values of the selected bit string need not all be selected bits. Therefore, for example, in order to extract bit string data in ascending order, a minimum value selection process is performed using a selection bit string obtained by replacing the next selection bit obtained by the first minimum value selection process with a non-selection bit, and the next selection bit obtained below Further, the minimum value selection process using the selected bit string in which is replaced with a non-selected bit is repeated, and the next selected bit string obtained by each minimum value selection process may be output as information for extracting the bit string data in ascending order.
In the following description, the next selection bit string obtained by each of the above-described minimum value selection processes may be referred to as a selection result bit string. Similarly, the next selection bit string obtained by each maximum value selection process may be referred to as a selection result bit string.

FIG. 11A is a diagram for conceptually explaining bit string data ascending order selection processing in the fourth embodiment of the present invention. The same bit position bit strings 240, 241, and 242 illustrated in FIG. 11A are the same as those obtained from the bit string data group 101 illustrated in FIG. 2A.

Step 1 shown in FIG. 11A is an initial minimum value selection process. As shown in FIG. 11A, in step 1, “1111” is set as an initial value in the selected bit string 210aA. As indicated by the bidirectional arrow 220aA, the bit determination of the same bit position bit string 240 is performed by the selected bit string 210aA in the same manner as in Step 2 illustrated in FIG. 2A, and the result of the bit determination continues as indicated by the dotted arrow 230bA. Next bit determination is performed based on the obtained next selected bit string 211aA.

In the next bit determination, as shown by the bidirectional arrow 220bA, the bit determination of the same bit position bit string 241 is performed using the next selected bit string 211aA as the selected bit string 210bA as in Step 3 illustrated in FIG. 2A. As indicated by an arrow 230cA, the next bit determination is further performed by the next selected bit string 211bA obtained as a result of the bit determination.

In the next bit determination, as indicated by a two-way arrow 220cA, the bit determination of the same bit position bit string 242 is performed with the next selected bit string 211bA as the selected bit string 210cA as in Step 4 illustrated in FIG. As indicated by 230 dA, it can be seen that the bit string data D2 corresponding to the bit E2 of the selection result bit string 211cA obtained as a result of the bit determination is the minimum value.

Next, bit calculation for setting the next selection bit is performed by the selection bit string 210aA and the selection result bit string 211cA indicated by the bidirectional arrow 220A, and the next selection bit string 211A is obtained as indicated by the dotted arrow 230A. As is apparent from the description in FIG. 11A, the next selection bit string 211A is a selection of the bits of the selection result bit string 211cA obtained as a result of the minimum value selection process in step 1 among the selection bit string 210aA that is the initial value in step 1. The bit E2 is replaced with a non-selected bit.

Step 2 shown in FIG. 11A is the next minimum value selection process. As shown in FIG. 11A, in step 2, the next selection bit string 211A obtained in step 1 is set as a selection bit string 210aB that is an initial value of the minimum value selection process. As indicated by the two-way arrow 220aB, the bit determination of the same bit position bit string 240 is performed by the selected bit string 210aB in the same manner as in Step 2 illustrated in FIG. 2A, and the result of the bit determination continues as indicated by the dotted arrow 230bB. Next bit determination is performed based on the obtained next selected bit string 211aB.

In the next bit determination, as shown by the two-way arrow 220bB, the bit determination of the same bit position bit string 241 is performed with the next selected bit string 211aB as the selected bit string 210bB as in Step 3 illustrated in FIG. 2A, and the dotted line continues. As indicated by an arrow 230cB, the next bit determination is further performed by the next selected bit string 211bB obtained as a result of the bit determination.

In the next bit determination, as shown by a bidirectional arrow 220cB, the bit determination of the same bit position bit string 242 is performed with the next selected bit string 211bB as the selected bit string 210cB as in Step 4 illustrated in FIG. 2A, and a dotted arrow As indicated by 230 dB, it can be seen that the bit string data D3 corresponding to the bit E3 of the selection result bit string 211cB obtained as a result of the bit determination is the next minimum value.

Next, bit calculation for setting the next selection bit is performed by the selection bit string 210aB and the selection result bit string 211cB indicated by the bidirectional arrow 220B, and the next selection bit string 211B is obtained as indicated by the dotted arrow 230B. As in the case of Step 1, the next selection bit string 211B is a selection bit among the bits of the selection result bit string 211cB obtained as a result of the minimum value selection process in Step 2 among the selection bit string 210aB that is the initial value in Step 2. E3 is replaced with a non-selected bit.

Step 3 shown in FIG. 11A is the next minimum value selection process. As shown in FIG. 11A, in step 3, the next selection bit string 211B obtained in step 2 is set as a selection bit string 210aC that is an initial value of the minimum value selection process. As indicated by the two-way arrow 220aC, the bit determination of the same bit position bit string 240 is performed by the selected bit string 210aC in the same manner as in Step 2 illustrated in FIG. 2A, and the result of the bit determination continues as indicated by the dotted arrow 230bC. The next bit determination is performed based on the obtained next selection bit string 211aC.

In the next bit determination, as shown by the bidirectional arrow 220bC, the bit determination of the same bit position bit string 241 is performed with the next selected bit string 211aC as the selected bit string 210bC as in Step 3 illustrated in FIG. 2A. As indicated by an arrow 230cC, the next bit determination is further performed by the next selected bit string 211bC obtained as a result of the bit determination.

In the next bit determination, as shown by a bidirectional arrow 220cC, the bit determination of the same bit position bit string 242 is performed with the next selected bit string 211bC as the selected bit string 210cC as in Step 4 illustrated in FIG. 2A, and a dotted arrow As indicated by 230 dC, it can be seen that the bit string data D4 corresponding to the bit E4 of the selection result bit string 211cC obtained as a result of the bit determination is the next minimum value.

Next, bit calculation for setting the next selection bit is performed by the selection bit string 210aC and the selection result bit string 211cC indicated by the bidirectional arrow 220C, and the next selection bit string 211C is obtained as indicated by the dotted arrow 230C. The next selection bit string 211C replaces E4, which is a selection bit among the bits of the selection result bit string 211cC obtained as a result of the minimum value selection process in step 3, among the selection bit string 210aC that is the initial value in step 3 with a non-selection bit. It is a thing.

Step 4 shown in FIG. 11A is the final minimum value selection process. As a result, information for accessing the maximum value is required. As shown in FIG. 11A, in step 4, the next selected bit string 211C obtained in step 3 is set as a selected bit string 210aD that is an initial value of the minimum value selecting process. As indicated by the bidirectional arrow 220aD, the bit determination of the same bit position bit string 240 is performed by the selected bit string 210aD in the same manner as in Step 2 illustrated in FIG. 2A, and the result of the bit determination continues as indicated by the dotted arrow 230bD. The next bit determination is performed based on the obtained next selection bit string 211aD.

In the next bit determination, as shown by the bidirectional arrow 220bD, the bit determination of the same bit position bit string 241 is performed with the next selected bit string 211aD as the selected bit string 210bD as in Step 3 illustrated in FIG. 2A, and the dotted line continues. As indicated by an arrow 230cD, the next bit determination is further performed by the next selected bit string 211bD obtained as a result of the bit determination.

In the next bit determination, as indicated by a bidirectional arrow 220cD, the bit determination of the same bit position bit string 242 is performed with the next selected bit string 211bD as the selected bit string 210cD, as in Step 4 illustrated in FIG. 2A, and the dotted arrow As indicated by 230dD, it can be seen that the bit string data D1 corresponding to the bit E1 of the selection result bit string 211cD obtained as a result of the bit determination is the next minimum value.

Next, a bit operation for setting the next selection bit is performed based on the selection bit string 210aD and the selection result bit string 211cD indicated by the bidirectional arrow 220D, and the next selection bit string 211D is obtained as indicated by the dotted arrow 230D. The next selection bit string 211D replaces E1 which is a selection bit among the bits of the selection result bit string 211cD obtained as a result of the minimum value selection processing in step 4 among the selection bit string 210aD which is an initial value in step 4 with a non-selection bit. It is a thing.

As shown in FIG. 11A, all the bits of the next selection bit string 211D are non-selection bits, and the end of the search is determined. Through the above processing, the selection result bit strings 211cA, 211cB, 211cC, and 211cD can be output as information for extracting the bit string data from the plurality of bit string data sets {D1, D2, D3, D4} in ascending order.

FIG. 11B is a diagram conceptually illustrating the bit string data descending order selection processing in the fifth embodiment of the present invention. The same bit position bit strings 240, 241, and 242 illustrated in FIG. 11B are the same as those obtained from the bit string data group 101 illustrated in FIG. 2B.

Step 1 shown in FIG. 11B is an initial maximum value selection process. As shown in FIG. 11B, in step 1, “1111” is set as the initial value in the selected bit string 212aA. As indicated by the bidirectional arrow 221aA, the bit determination of the same bit position bit string 240 is performed by the selected bit string 212aA in the same manner as in Step 2 illustrated in FIG. 2B, and the result of the bit determination continues as indicated by the dotted arrow 231bA. Next bit determination is performed based on the obtained next selected bit string 213aA.

In the next bit determination, as indicated by the bidirectional arrow 221bA, the bit determination of the same bit position bit string 241 is performed using the next selected bit string 213aA as the selected bit string 212bA as in Step 3 illustrated in FIG. As indicated by an arrow 231cA, the next bit determination is further performed by the next selected bit string 213bA obtained as a result of the bit determination.

In the next bit determination, as shown by a bidirectional arrow 221cA, the bit determination of the same bit position bit string 242 is performed using the next selected bit string 213bA as the selected bit string 212cA as in Step 4 illustrated in FIG. 2B, and the dotted arrow As indicated by 231 dA, the bit string data D1 corresponding to the bit E1 of the selection result bit string 213cA obtained as a result of the bit determination is found to be the maximum value.

Next, a bit operation for setting the next selection bit is performed using the selection bit string 212aA indicated by the bidirectional arrow 221A and the selection result bit string 213cA, and the next selection bit string 213A is obtained as indicated by the dotted arrow 231A. As is apparent from the description in FIG. 11B, the next selection bit string 213A is selected from the bits of the selection result bit string 213cA obtained as a result of the maximum value selection process in step 1 among the selection bit string 212aA that is the initial value in step 1. The bit E1 is replaced with a non-selected bit.

Step 2 shown in FIG. 11B is the next maximum value selection process. As shown in FIG. 11B, in step 2, the next selection bit string 213A obtained in step 1 is set as a selection bit string 212aB that is an initial value of the maximum value selection process. As indicated by the bidirectional arrow 221aB, the bit determination of the same bit position bit string 240 is performed by the selected bit string 212aB in the same manner as in Step 2 illustrated in FIG. 2B, and the result of the bit determination continues as indicated by the dotted arrow 231bB. Next bit determination is performed based on the obtained next selected bit string 213aB.

In the next bit determination, as shown by the bidirectional arrow 221bB, the bit determination of the same bit position bit string 241 is performed using the next selected bit string 213aB as the selected bit string 212bB as in Step 3 illustrated in FIG. As indicated by an arrow 231cB, the next bit determination is further performed by the next selected bit string 213bB obtained as a result of the bit determination.

In the next bit determination, as shown by the bidirectional arrow 221cB, the bit determination of the same bit position bit string 242 is performed with the next selected bit string 213bB as the selected bit string 212cB, as in Step 4 illustrated in FIG. 2B, and the dotted arrow As indicated by 231 dB, it can be seen that the bit string data D4 corresponding to the bit E4 of the selection result bit string 213cB obtained as a result of the bit determination is the next maximum value.

Next, bit calculation for setting the next selection bit is performed by the selection bit string 212aB and the selection result bit string 213cB indicated by the bidirectional arrow 221B, and the next selection bit string 213B is obtained as indicated by the dotted arrow 231B. As in the case of step 1, the next selection bit string 213B is a selection bit among the bits of the selection result bit string 213cB obtained as a result of the maximum value selection process in step 2 among the selection bit string 212aB that is the initial value in step 2. E4 is replaced with a non-selected bit.

Step 3 shown in FIG. 11B is the next maximum value selection process. As shown in FIG. 11B, in step 3, the next selection bit string 213B obtained in step 2 is set as a selection bit string 212aC that is an initial value of the maximum value selection process. As indicated by the bidirectional arrow 221aC, the bit determination of the same bit position bit string 240 is performed by the selected bit string 212aC in the same manner as in Step 2 illustrated in FIG. 2B, and the result of the bit determination continues as indicated by the dotted arrow 231bC. Next bit determination is performed based on the obtained next selected bit string 213aC.

In the next bit determination, as shown by the bidirectional arrow 221bC, the bit determination of the same bit position bit string 241 is performed using the next selected bit string 213aC as the selected bit string 212bC as in Step 3 illustrated in FIG. 2B, and the dotted line continues. As indicated by an arrow 231cC, the next bit determination is further performed by the next selected bit string 213bC obtained as a result of the bit determination.

In the next bit determination, as indicated by the bidirectional arrow 221cC, the bit determination of the same bit position bit string 242 is performed with the next selected bit string 213bC as the selected bit string 212cC, as in Step 4 illustrated in FIG. 2B, and the dotted arrow As indicated by 231 dC, it can be seen that the bit string data D3 corresponding to the bit E3 of the selection result bit string 213cC obtained as a result of the bit determination is the next maximum value.

Next, bit calculation for setting the next selection bit is performed by the selection bit string 212aC and the selection result bit string 213cC indicated by the bidirectional arrow 221C, and the next selection bit string 213C is obtained as indicated by the dotted arrow 231C. The next selection bit string 213C replaces E3, which is a selection bit among the bits of the selection result bit string 213cC obtained as a result of the maximum value selection processing in step 3, among the selection bit string 212aC that is the initial value in step 3 with a non-selection bit. It is a thing.

Step 4 shown in FIG. 11B is the final maximum value selection process. As a result, information for accessing the minimum value is obtained. As shown in FIG. 11B, in step 4, the next selected bit string 213C obtained in step 3 is set as a selected bit string 212aD that is an initial value of the minimum value selecting process. As indicated by the bidirectional arrow 221aD, the bit determination of the same bit position bit string 240 is performed by the selected bit string 212aD in the same manner as in Step 2 illustrated in FIG. 2B, and the result of the bit determination continues as indicated by the dotted arrow 231bD. Next bit determination is performed based on the obtained next selection bit string 213aD.

In the next bit determination, as shown by the bidirectional arrow 221bD, the bit determination of the same bit position bit string 241 is performed using the next selected bit string 213aD as the selected bit string 212bD as in Step 3 illustrated in FIG. 2B, and the dotted line continues. As indicated by an arrow 231cD, the next bit determination is further performed by the next selected bit string 213bD obtained as a result of the bit determination.

In the next bit determination, as shown by the bidirectional arrow 221cD, the bit determination of the same bit position bit string 242 is performed with the next selected bit string 213bD as the selected bit string 212cD, as in Step 4 illustrated in FIG. 2B, and the dotted arrow As indicated by 231dD, it can be seen that the bit string data D2 corresponding to the bit E of the selection result bit string 213cD obtained as a result of the bit determination is the next maximum value.

Next, bit calculation for setting the next selection bit is performed by the selection bit string 212aD and the selection result bit string 213cD indicated by the bidirectional arrow 221D, and the next selection bit string 213D is obtained as indicated by the dotted arrow 231D. The next selection bit string 213D replaces E2 which is a selection bit among the bits of the selection result bit string 213cD obtained as a result of the maximum value selection processing in Step 4 among the selection bit string 212aD which is an initial value in Step 4 with a non-selection bit. It is a thing.

As shown in FIG. 11B, all the bits of the next selected bit string 213D are non-selected bits, and the end of the search is determined. Through the above processing, the selection result bit strings 213cA, 213cB, 213cC, and 213cD can be output as information for extracting bit string data in descending order from a plurality of bit string data sets {D1, D2, D3, D4}.

Next, a bit string data sequential selection circuit using the maximum value / minimum value selection circuit of the present invention that realizes the bit string data ascending order selection process or the bit string data ascending order selection process described above will be described.
FIG. 12A is a diagram illustrating a bit string data sequential selection circuit block and peripheral circuit examples in the fourth and fifth embodiments of the present invention.

As shown in FIG. 12A, the bit string data sequential selection circuit 500a includes a maximum / minimum value selection circuit 300, a selection bit register 310, a selection result register 360, a next selection bit setting circuit 380, and a sequential selection control circuit 370.

In the case of the fourth embodiment, the maximum value / minimum value selection circuit 300 is, for example, the minimum value selection circuit 300a illustrated in FIG. 3A, and in the case of the fifth embodiment, the maximum value illustrated in FIG. 3B, for example. This is the selection circuit 300b. The selection bit register 310 and the selection result register 360 are the same as those described in FIGS. 3A, 3B, and 10.
The data register group 301 which is a peripheral circuit is the same as that described in FIGS. 3A, 3B and 10.

The signal line 520 is a data setting signal input to the data register group 301 and the next selection bit setting circuit 380, and the timing for setting the bit string data in the data register group 301 and the next selection bit string of the next selection bit setting circuit 380. Gives the timing for initial setting.
The parallel bus 521 which is an input to the data register group 301 is for setting bit string data, and the signal line 522 from the data register group 301 to the maximum value / minimum value selection circuit 300 is at the same position shown in FIG. This represents a parallel bus 3401, 3402,... 340m that outputs a bit string.

A signal line 530 input to the sequential selection control circuit 370 is for a sequential selection start signal that instructs the sequential selection control circuit 370 to start control. The sequential selection control circuit 370 receives a control start instruction and receives a bit string. Supply of a clock for controlling the sequential selection operation in the data sequential selection circuit 500a is started.

The signal or bit string data supplied from the signal line 520, the parallel bus 521, and the signal line 530 is supplied from the peripheral circuit including the data register group 301 to the bit string data sequential selection circuit 500a. The bit string data sequential selection circuit 500a can include the data register group 301, and a peripheral circuit that does not include the data register group can use the bit string data sequential selection circuit.

The signal line 532a from the sequential selection control circuit 370 to the selection bit register 310 and the signal line 532b from the sequential selection control circuit 370 to the selection result register 360 and the next selection bit setting circuit 380 supply the above-described clocks. The clock on the signal line 532a (hereinafter also referred to as clock 532a) and the clock on the signal line 532b (hereinafter also referred to as clock 532b) are clocks of opposite phases, and the maximum value / minimum value selection is performed. This is for controlling the alternate operation of the circuit 300 and the next selection bit setting circuit 380. The signal line 532 to which the same clock as the signal line 532b is supplied gives the external circuit a timing for fetching the selection result bit string. The external circuit is a circuit connected to the bit string data sequential selection circuit, and is an arbitrary circuit using the selection result bit string sequentially output from the bit string data sequential selection circuit.

The next selection bit setting circuit 380 sends the initial value of the selection bit string to the selection bit register 310 every time the maximum value / minimum value selection processing is executed via the signal line 560 as in the steps illustrated in FIGS. 11A and 11B. Reset it. The initial value of the selected bit string in the first step is that all bits are selected bits. After the first step, the selection bit string held in the selection bit register 310 is input to the next selection bit setting circuit 380 via the signal line 540x, and the selection result bit string held in the selection result register 360 is the signal line. This is input to the next selection bit setting circuit 380 via 550x.

Then, a next selection bit string is generated by a bit string operation between the selected bit string and the selection result bit string in synchronization with the clock on the signal line 532b, and the selection bit string of the next maximum value / minimum value selection process is transmitted via the signal line 560. It is set in the selection bit register 310 as an initial value.

Next, the initial value of the selected bit string set in the selected bit register 310 in synchronization with the clock on the signal line 532a is input to the maximum value / minimum value selection circuit, and the last bit of the maximum value / minimum value selection circuit 300 is input. The next selected bit string that is the output of the determination circuit is input as a selection result bit string to the selection result register 360 via the signal line 570. The timing for setting the selection result bit string in the selection result register 360 is controlled by the clock on the signal line 532b.

The selection result bit string stored in the selection result register 360 is input to the next selection bit setting circuit 380 via the signal line 550x and is output to the external circuit via the signal line 550.

When the next selection bit setting circuit 380 detects that all the bits of the generated next selection bit string are non-selection bits, the sequential selection control circuit 370 is instructed to sequentially terminate the selection control operation via the signal line 580x. An end signal is sent, and the end of the selection operation is sequentially notified to the external circuit via the signal line 580. The sequential selection control circuit 370 that has received the sequential selection end signal stops the clock transmission and ends the sequential selection control operation.

FIG. 12B is a diagram illustrating a bit string data sequential selection circuit block and peripheral circuit examples according to the sixth embodiment of the present invention. Compared to the bit string data sequential selection circuit block and the peripheral circuit example in the fourth and fifth embodiments of the present invention shown in FIG. 12A, the bit string data sequential selection circuit 500b in the sixth embodiment has a maximum value and a minimum value. The selection circuit is the maximum value / minimum value selection circuit 300c of the third embodiment. In addition, a determination flag 390 that holds a determination bit is added as a peripheral circuit, and the signal line 520 is also connected to the determination flag 390 to give the determination flag 390 a timing for setting the determination bit.

The determination flag 390 is the same as that described in FIG. A signal line 524 from the determination flag to the maximum value / minimum value selection circuit 300c is equivalent to the bus 321 for outputting the determination bit shown in FIG. Except for the addition of the determination flag, the other parts are the same as those in the fourth and fifth embodiments, and thus further description is omitted.

Next, the next selection bit setting circuit 380 shown in FIGS. 12A and 12B will be described with reference to FIG.
As shown in FIG. 13, the next selection bit setting circuit 380 includes a selection bit string temporary holding register 381, a next selection bit string calculator 382, and an all selection end detector 383.

The selected bit string temporary holding register 381 temporarily holds the value of the selected bit register 310 via the signal line 540x according to the clock given by the signal line 532b. The initial value of the selected bit string temporary holding register 381 is set by a data setting signal given via the signal line 520. The initial value of the selection bit string is that all bits are selection bits, and in the example of selection bits in the embodiment of the present application, all bits are “1”.

The next selected bit string calculator 382 calculates a bit string between the selected bit string input from the selected bit string temporary holding register 381 via the signal line 541x and the selection result bit string input from the selection result register 360 via the signal line 550x. To generate the next initial selection bit string used as the initial value in the maximum value / minimum value selection processing in the next step.

In the bit string operation described above, the selected bit string of the selected bit string input from the selected bit string temporary holding register 381 is the bit string that has been selected using the bit at the bit position where the selected bit of the selection result bit string input from the selection result register 360 exists as a non-selected bit Data is excluded from selection. This bit string operation can be realized by, for example, exclusive OR. The selected bit string generated by the above bit string operation is input to the selected bit register as the next initial selected bit string via the signal line 560 and also input to the all-selection completion detector 383 via the signal line 560x.

The all-selection-end detector 383 detects that all the bit string data has been selected because all the bits of the selected bit string on the signal line 560x are non-selected bits, and sequentially selects the signal indicating the end of the signal line 580x. And sequentially output to the selection control circuit 370 and to the external circuit via the signal line 580.

Next, a timing chart of the bit string data sequential selection circuit shown in FIGS. 12A and 12B will be described.
FIG. 14 is a diagram illustrating an example of a timing chart of the bit string data sequential selection circuit according to the fourth embodiment of the present invention.

(1) shown in FIG. 14 is a waveform of a reset signal input from the peripheral circuit. In FIG. 12A, FIG. 12B, and FIG. 13, the reset signal line is omitted.
(2) and (3) shown in FIG. 14 are the waveforms of the data setting signal on the signal line 520 and the sequential selection start signal on the signal line 530, respectively.
14 is a waveform of a clock generated by the clock generation circuit included in the sequential selection control circuit 370.

(5) shown in FIG. 14 is a waveform of a clock supply signal for supplying the clock 532a and the clock 532b.
(6) shown in FIG. 14 is a waveform of a sequential selection end signal on the signal lines 580 and 580x.
(7) and (8) shown in FIG. 14 are waveforms of clocks sequentially output from the selection control circuit 370. The clock 532b is a reverse phase signal of the clock 532a with respect to the clock 532a. The timing shown in FIG. 14 will be described later.

(9) shown in FIG. 14 is an example of the bit string data held in the data register group 301, and the same bit string data as shown in FIG. 2A is held. As described above, the same position bit string composed of the bits extracted from the bits at the same position of each of these bit string data is output to the maximum value / minimum value selection circuit 300.
(10) shown in FIG. 14 is an example of the initial value of the selected bit string of each maximum value / minimum value selection process output from the next selection bit setting circuit 380 to the selection bit register 310 via the signal line 560.
14 are examples of the selection bit string held in the selection bit register 310 and the selection result bit string held in the selection result register 360, respectively.

Symbols T0, T1, to T9 described in FIG. 14 indicate specific timings, respectively. As shown in FIG. 14, T0 is the timing at which the clock supply signal rises. Supply of the clock 532a is started at T1. Hereinafter, T2 to T8 are timings for each half cycle of the clock. T9 is the timing when the clock supply signal falls in response to the sequential selection end signal.

As shown in (1) of FIG. 14, when a reset signal is input, the selected bit string temporary holding register 381 of the selection bit register 310, the selection result register 360, and the next selection bit setting circuit 380, as indicated by an arrow 510a. Are reset, and all bits of the respective registers are cleared to "0".

Next, when a data setting signal on the signal line 520 shown in (2) of FIG. 14 (hereinafter, a signal on the signal line is described with the same reference numerals as those of the signal line as in the case of the clock 532a), an arrow 520a. As shown, the bit string data is set in the data register group 301, and the bit string “1111” in which all bits are selected bits is set in the selected bit string temporary holding register 381.

Next, when the sequential selection start signal 530 shown in (3) of FIG. 14 rises, as indicated by the arrow 530a and the dotted line 531a, the clock supply signal is supplied so that the clock 532a is supplied from the state “0”. The clocks 532a and 532b of the sequential selection control circuit 370 are synchronized with the clock of the clock generation circuit that is the basis of the clock 532b, and the clock supply signal shown in (5) of FIG. 14 rises at timing T0. Clock supply is started at a timing surrounded by a dotted circle indicated by an arrow 531b.

As shown in (7) of FIG. 14, when the clock 532a rises at timing T1, the initial value “1111” of the first selected bit string is set in the selected bit register 310 as shown by the arrow 560a at the timing shown by the arrow 533a. The Then, as indicated by the arrow 230A, the maximum value / minimum value selection circuit 300 receives the bit string data 541a set in the data register group 301 indicated by the dotted line 591a and the 551a set in the selected bit string register 310 as input. The first value “0100” of the result bit string is obtained.

Next, at the timing T2, when the clock 532b rises, the selection result bit string “0100” that is the selection result of the first maximum value / minimum value selection is set in the selection result register 360 at the timing indicated by the arrow 535a. Although not shown in FIG. 14, as described above, the selected bit string held in the selected bit register is set in the next selected bit string temporary holding register 381. Then, as indicated by an arrow 220A, the initial value “1011” of the next selected bit string is obtained by calculating the selected bit string 540a and the selection result bit string 550a indicated by the dotted line 590a.
The interval between T1 and T2 and the interval between T2 and T3 are defined by the larger of the delay time in the maximum / minimum value selection circuit 300 and the delay time in the next selection bit setting circuit 380.

Next, when the clock 532a rises at timing T3, the initial value “1011” of the next selected bit string is set in the selected bit register 310 as shown by the arrow 560b at the timing shown by the arrow 533b. Then, as indicated by the arrow 230B, the maximum value / minimum value selection circuit 300 receives the bit string data 541b set in the data register group 301 indicated by the dotted circle 591b and the 551b set in the selection bit string register 310 as inputs. The result bit string “0010” is obtained.

Next, when the clock 532b rises at timing T4, the selection result bit string “0010”, which is the selection result of the next maximum / minimum value selection, is set in the selection result register 360 at the timing indicated by the arrow 535b. Then, as indicated by an arrow 220B, the initial value “1001” of the next selected bit string is obtained by calculating the selected bit string 540b and the selection result bit string 550b indicated by the dotted line 590b.

Next, when the clock 532a rises at timing T5, the initial value “1001” of the next selected bit string is set in the selected bit register 310 as shown by the arrow 560c at the timing shown by the arrow 533c. Then, as indicated by the arrow 230C, the maximum / minimum value selection circuit 300 receives the bit string data 541c set in the data register group 301 indicated by the dotted line 591c and the 551c set in the selection bit string register 310 as input. The result bit string “0001” is obtained.

Next, when the clock 532b rises at timing T6, the selection result bit string “0001”, which is the selection result of the maximum value / minimum value selection, is set in the selection result register 360 at the timing indicated by the arrow 535c. Then, as indicated by the arrow 220C, the initial value “1000” of the next selected bit string is obtained by the calculation of the selected bit string 540c and the selection result bit string 550c indicated by the dotted line 590c.

Next, when the clock 532a rises at timing T7, the initial value “1000” of the next selected bit string is set in the selected bit register 310 as shown by the arrow 560d at the timing shown by the arrow 533d. Then, as indicated by an arrow 230D, the maximum value / minimum value selection circuit 300 receives the bit string data 541d set in the data register group 301 indicated by the dotted line 591d and the 551d set in the selected bit string register 310 as input. The result bit string “1000” is obtained.

Next, when the clock 532b rises at timing T8, the selection result bit string “1000”, which is the selection result of the maximum value / minimum value selection, is set in the selection result register 360 at the timing indicated by the arrow 535d. Then, as indicated by the arrow 220D, “0000” is obtained as the initial value of the next selected bit string by the calculation of the selected bit string 540d and the selection result bit string 550d indicated by the dotted circle 590d.

Then, the all selection end detector 393 detects that all the bits of the initial value of the next selected bit string are non-selected bits, and the selection end signal 580 sequentially rises as indicated by an arrow 560e. Then, as indicated by an arrow 580d, the clock supply signal shown in (5) of FIG. 14 falls, and as indicated by an arrow 531d, the supply of the clock 532a and the clock 532b is stopped at a timing T9.

The timing chart example of the bit string data sequential selection circuit according to the fourth embodiment of the present invention has been described above. The timing chart example of the bit string data sequential selection circuit according to the fifth embodiment is shown in (10) and (10) of FIG. The initial value, the selection bit string, and the selection result bit string of the next selection bit string exemplified in 11) and (12) are different, and the others are the same. Further, in the timing chart example of the bit string data sequential selection circuit in the sixth embodiment, the initial value of the selected bit string, the selection result bit string, and the next selected bit string differs depending on the determination bit, and the determination flag is set by the data setting signal. Therefore, the description will be omitted.

As is apparent from the detailed description of the fourth to sixth embodiments of the present invention, according to the present invention, the bit string data is arranged in ascending or descending order using the minimum / maximum value selection circuit configured by the passive circuit. Since the information for extraction can be obtained, high-speed operation is possible. Moreover, it will be apparent to those skilled in the art that various modifications can be made to the embodiment of the present invention in addition to the above description.

For example, it is also possible to detect that the selection processing of all bit string data has been completed when the number of selection bits of the initial value of the next selected bit string becomes 1.
Further, the interval between T1 and T2 and the interval between T2 and T3 in FIG. 14 are defined by the larger of the delay time in the maximum / minimum value selection circuit 300 and the delay time in the next selection bit setting circuit 380. By generating a clock with a duty ratio in which the interval between T1 and T2 is the delay time in the maximum / minimum value selection circuit 300 and the interval between T2 and T3 is the delay time in the next selection bit setting circuit 380, the minimum With this delay time, the bit string data sequential selection circuit can be operated. Furthermore, it is possible to synchronize the clock generation circuit included in the sequential selection control circuit 370 with an external clock to output a sequential selection bit string, or to generate an operation clock for the bit string data sequential selection circuit based on the external clock. is there.

300 Maximum value / minimum value selection circuit 301 Data register group 310 Selection bit register 320a Bit determination circuit 360 Selection result register 370 Sequential selection control circuit 380 Next selection bit setting circuit 381 Selection bit string temporary holding register 382 Next selection bit string calculator 383 All selection End detector 390 Determination flag 410 Determination bit setting unit 420 Match determination unit 430 Total mismatch determination unit 440 Determination result selector

Claims (21)

N bits (N is an integer of 2 or more) bit string data taken from the same bit position, each of the same position bit string consisting of N bits corresponding to each bit string data, and each of the same position bit string Are selected bits that are selected as bit determination targets or non-selected bits that are not selected as bit determination targets, each of which is input a selected bit string consisting of N bits corresponding to each bit string data,
Based on the bit of the same position bit string selected by the selected bit of the selected bit string, it is a bit extracted from the bit position next to the same bit position of each bit string data, and N corresponding to each bit string data A selection bit for selecting each bit of the next identically-positioned bit string consisting of a plurality of bits or the non-selection bit for non-selection, each outputting a next selection bit string consisting of N bits corresponding to each bit string data In the bit decision circuit,
A non-matching discriminator that determines whether all the bits of the same-position bit string selected by the selection bit of the selected bit string are “1”;
When the all mismatch determination unit determines that all the bits in the same position bit string are “1”, the selected bit string is output to the outside as the next selected bit string,
When the all mismatch judgment unit determines that all the bits of the selected same-position bit string are not “1”, the bit of the next selection bit string corresponding to the bit that is “0” of the same-position bit string is selected. A bit of the next selected bit string corresponding to a bit that is “1” of the selected same-position bit string as the non-selected bit, and the next selection corresponding to the non-selected bit of the selected bit string A bit determination circuit characterized in that a bit of a bit string is set as the non-selected bit and the next selected bit string is output to the outside . N bits (N is an integer of 2 or more) bit string data taken from the same bit position, each of the same position bit string consisting of N bits corresponding to each bit string data, and each of the same position bit string Are selected bits that are selected as bit determination targets or non-selected bits that are not selected as bit determination targets, each of which is input a selected bit string consisting of N bits corresponding to each bit string data,
Based on the bit of the same position bit string selected by the selected bit of the selected bit string, it is a bit extracted from the bit position next to the same bit position of each bit string data, and N corresponding to each bit string data A selection bit for selecting each bit of the next identically-positioned bit string consisting of a plurality of bits or the non-selection bit for non-selection, each outputting a next selection bit string consisting of N bits corresponding to each bit string data In the bit decision circuit,
A non-matching discriminator for judging whether all the bits of the same position bit string selected by the selection bit of the selected bit string are "0";
When the all mismatch judgment unit judges that all the bits in the same position bit string are “0”, the selected bit string is output to the outside as the next selected bit string,
When the all mismatch discriminator determines that all the bits of the selected same-position bit string are not “0”, the bit of the next selection bit string corresponding to the bit that is “1” of the same-position bit string is selected. A bit of the next selected bit string corresponding to a bit that is “0” of the selected same-position bit string as the non-selected bit, and the next selection corresponding to the non-selected bit of the selected bit string A bit determination circuit characterized in that a bit of a bit string is set as the non-selected bit and the next selected bit string is output to the outside . N bits (N is an integer of 2 or more) bit string data taken from the same bit position, each of the same position bit string consisting of N bits corresponding to each bit string data, and each of the same position bit string Are selected bits that are selected as bit determination targets or non-selected bits that are not selected as bit determination targets, each of which is input a selected bit string consisting of N bits corresponding to each bit string data,
Based on the bit of the same position bit string selected by the selected bit of the selected bit string, it is a bit extracted from the bit position next to the same bit position of each bit string data, and N corresponding to each bit string data A selection bit for selecting each bit of the next identically-positioned bit string consisting of a plurality of bits or the non-selection bit for non-selection, each outputting a next selection bit string consisting of N bits corresponding to each bit string data In the bit decision circuit,
Enter the judgment bit,
A non-matching discriminator that determines whether all the bits of the same position bit string selected by the selection bit of the selection bit string do not match the determination bit;
When the all mismatch judgment unit determines that all the bits in the same position bit string do not match the judgment bit, the selected bit string is output to the outside as the next selected bit string,
When the all mismatch determination unit determines that at least one bit of the selected same-position bit string matches the determination bit, the next selection corresponding to the bit whose bit in the same-position bit string matches the determination bit A bit of the bit string is the selected bit, and a bit of the next selected bit string corresponding to a bit in which the selected bit of the same position bit string does not match the determination bit is the non-selected bit, and the bit of the selected bit string A bit determination circuit characterized in that a bit of the next selected bit string corresponding to a non-selected bit is used as the non-selected bit and the next selected bit string is output to the outside . The bit determination circuit according to claim 1 ,
A coincidence determination unit that performs a bit string operation between the selected bit string and the same position bit string and outputs a bit string as a result of the calculation, and in the calculation of the selection flag bit of the selected bit string and the bit of the same position bit string, the same The selection bit or the non-selection bit is output depending on whether the bit of the position bit string is “0” or “1”, and the calculation of the non-selection bit of the selection bit string and the bit of the same position bit string is performed Then, it comprises a coincidence determiner that outputs the non-selected bits,
When the all mismatch determination unit determines that all the bits in the same position bit string are “1”, the selected bit string is output to the outside as the next selected bit string,
If the all mismatch judgment unit judges that all the bits in the same position bit string are not "1", the bit judgment circuit outputs the bit string output from the coincidence judgment unit as the next selected bit string to the outside . The bit determination circuit according to claim 1 ,
When the all mismatch judgment unit judges that all the bits in the same position bit string are “1”, it outputs a bit string composed of N bits which are all the selected bits, and the all mismatch judgment unit outputs the same judgment bit. A determination result output selector that outputs the same position bit string when it is determined that all the bits of the position bit string are not "1";
A bit determination circuit, wherein a bit string having a bit product of a bit string output from the determination result output selector and each bit of the selected bit string is output to the outside as the next selected bit string. The bit determination circuit according to claim 1 ,
A coincidence determination unit that performs a bit string operation between the selected bit string and the same position bit string and outputs a bit string as a result of the calculation, wherein in the operation of the selected bit of the selected bit string and the bit of the same position bit string, the same position Depending on whether the bit string bit is “0” or “1”, the selected bit or the non-selected bit is output. In the operation of the non-selected bit of the selected bit string and the bit of the same position bit string, , Comprising a coincidence judging device for outputting the non-selected bits,
Instead of determining whether all the bits in the same-position bit string selected by the selected bits in the selected bit string are “1”, the all-mismatch determiner determines whether the bit string output by the match determiner is It is a judgment whether all are "1",
When the all mismatch judgment unit judges that all the bit strings output by the coincidence judgment unit are “1”, the selection bit string is output to the outside as the next selection bit string,
If the all mismatch determination unit determines that all the bit strings output from the match determination unit are not “1”, the bit determination unit outputs the bit sequence output from the match determination unit as the next selected bit sequence to the outside. circuit. The bit determination circuit according to claim 2 ,
A coincidence determination unit that performs a bit string operation between the selected bit string and the same position bit string and outputs a bit string as a result of the calculation, wherein in the operation of the selected bit of the selected bit string and the bit of the same position bit string, the same position Depending on whether the bit string bit is “1” or “0”, the selection bit or the non-selection bit is output. In the operation of the non-selection bit of the selection bit string and the bit of the same position bit string, , Comprising a coincidence judging device for outputting the non-selected bits,
When the all mismatch judgment unit judges that all the bits in the same position bit string are “0”, the selected bit string is output to the outside as the next selected bit string,
If the all mismatch judgment unit judges that all the bits in the same position bit string are not "0", the bit judgment circuit outputs the output of the coincidence judgment unit as the next selected bit string to the outside . The bit determination circuit according to claim 2 ,
When the all mismatch judgment unit judges that all the bits in the same position bit string are “0”, it outputs a bit string composed of N bits which are all the selected bits, and the all mismatch judgment unit outputs the same judgment bit. A determination result output selector that outputs the same position bit string when it is determined that all the bits of the position bit string are not "0";
A bit determination circuit, wherein a bit string having a bit product of a bit string output from the determination result output selector and each bit of the selected bit string is output to the outside as the next selected bit string. The bit determination circuit according to claim 2,
A coincidence determination unit that performs a bit string operation between the selected bit string and the same position bit string and outputs a bit string as a result of the calculation, wherein in the operation of the selected bit of the selected bit string and the bit of the same position bit string, the same position Depending on whether the bit string bit is “1” or “0”, the selection bit or the non-selection bit is output. In the operation of the non-selection bit of the selection bit string and the bit of the same position bit string, , Comprising a coincidence judging device for outputting the non-selected bits,
Instead of determining whether all the bits of the same-position bit string selected by the selected bits of the selected bit string are “0”, the all non-matching determiner determines that all the bit strings output by the match determiner are “ 0 ”to determine whether
When the all mismatch judgment unit judges that all the bit strings output from the coincidence judgment unit are “0”, the selection bit string is output to the outside as the next selection bit string,
If the all mismatch determination unit determines that all the bit strings output from the match determination unit are not "0", the bit sequence output from the match determination unit is output to the outside as the next selected bit sequence. circuit. The bit determination circuit according to claim 3 ,
A coincidence determination unit that performs a bit string operation between the selected bit string and the same position bit string and outputs a bit string as a result of the calculation, wherein in the operation of the selected bit of the selected bit string and the bit of the same position bit string, the same position The selection bit or the non-selection bit is output depending on whether the bit string bit is the determination bit or not, and an operation of the bit having the non-selection flag of the selection bit string and the bit of the same position bit string is performed Then, it comprises a coincidence determiner that outputs the non-selected bits,
When the all mismatch judgment unit determines that all the bits in the same position bit string do not match the judgment bit, the selected bit string is output to the outside as the next selected bit string,
A bit decision circuit that outputs the output of the match decision unit to the outside as the next selected bit sequence when the all mismatch decision unit determines that at least one of the bits in the same position bit sequence matches the determination bit . The bit determination circuit according to claim 3 ,
If the all mismatch judgment unit determines that all the bits in the same position bit string do not match the judgment bit, it outputs a bit string consisting of N bits that are all the selection bits, and the all mismatch judgment unit A determination result output selector that outputs the same position bit string when it is determined that at least one of the bits of the same position bit string matches the determination bit;
A bit determination circuit, wherein a bit string having a bit product of a bit string output from the determination result output selector and each bit of the selected bit string is output to the outside as the next selected bit string. The bit determination circuit according to claim 3 ,
A coincidence determination unit that performs a bit string operation between the selected bit string and the same position bit string and outputs a bit string as a result of the calculation, wherein in the operation of the selected bit of the selected bit string and the bit of the same position bit string, the same position The selection bit or the non-selection bit is output depending on whether the bit string is a determination bit or not, and in the operation of the non-selection bit of the selection bit string and the bit of the same position bit string, the non-selection bit is output. A coincidence judging device for outputting a selection bit;
The all non-coincidence determiner is configured to determine whether all the bits in the same-position bit string selected by the selected bits of the selected bit string do not match the determination bits, but to replace the bits of the bit string output by the match determiner Are all determined not to match the determination bit,
When the all mismatch judgment unit determines that all the bit strings output by the coincidence judgment unit do not match the judgment bits, the selection bit string is output to the outside as the next selection bit string,
When the all mismatch determination unit determines that at least one of the bit strings output from the match determination unit matches the determination bit, the bit sequence output from the match determination unit is output to the outside as the next selected bit sequence. Bit decision circuit to perform. To select bit string data having a minimum value from selected bit string data among N (N is a positive integer of 2 or more) bit string data each having a bit length m (m is a positive integer). In the minimum value selection circuit,
Claim 1, to enter the bit judging circuit according to any one of claims 4 to 6, the following selection bit string which is the output of the preceding bit judging circuit as the selected bit string of subsequent bit decision circuit Connected to m stages in series,
The next selected bit string output from the m-th bit determination circuit is output to the outside as information for selecting the bit string data having the minimum value corresponding to the bit selected in the selected bit string input to the first-stage bit determination circuit. A bit string data selection circuit characterized by the above. In order to select bit string data having the maximum value from selected bit string data among N (N is a positive integer of 2 or more) bit string data each having a bit length m (m is a positive integer). In the maximum value selection circuit of
Claim 2, to enter the bit judging circuit according to any one of claims 7 to 9, the following selection bit string which is the output of the preceding bit judging circuit as the selected bit string of subsequent bit decision circuit Connected to m stages in series,
The next selected bit string output from the m-th bit determination circuit is output to the outside as information for selecting the maximum value bit string data corresponding to the bit selected in the selected bit string input to the first-stage bit determination circuit. A bit string data selection circuit characterized by the above. Select bit string data having the maximum or minimum value from selected bit string data among N (N is a positive integer of 2 or more) bit string data each having a bit length of m (m is a positive integer) In the maximum / minimum value selection circuit for
Claim 3, to enter the bit judging circuit according to any one of claims 10 to 12, the following selection bit string which is the output of the preceding bit judging circuit as the selected bit string of subsequent bit decision circuit Connected to m stages in series,
The next selected bit string output from the m-th bit determination circuit is externally used as information for selecting the maximum or minimum bit string data corresponding to the bit selected in the selected bit string input to the first-stage bit determination circuit. bit string data selection circuit and outputting the. In a bit string data sequential selection circuit for selecting bit string data in ascending order from N (N is a positive integer of 2 or more) bit string data each having a bit length of m (m is a positive integer)
A bit string data selection circuit according to claim 13 ,
A selection bit register for holding a selection bit string to be input to the bit string data selection circuit;
A selection result register that holds a next selection bit string that is an output of the bit string data selection circuit as a selection result bit string;
The next initial selection of the selected bit string held in the selected bit register by replacing the bit at the same bit position as the selected bit in the selected result bit string held in the selected result register with a non-selected bit A next selection bit setting circuit for obtaining a bit string;
A first clock for causing the selection bit register to set the next initial selection bit string as the selection bit string is supplied to the selection bit register, and a second clock for holding the selection result bit string in the selection result register is provided. A sequential selection control circuit for supplying to the selection result register,
A bit string in which all the bits are the selected bits as an initial value of the next initial selected bit string is set in the selected bit register in synchronization with the first clock, and the bit string data selecting process by the bit string data selecting circuit is started. A selection result bit string that is a result of the bit string data selection processing is set in the selection result register in synchronization with the second clock, and the selection result bit string is output,
Further, the next selection bit setting circuit sets a bit at the same bit position as the bit position where the selection bit of the selection result bit string held in the selection result register of the selection bit string held in the selection bit register exists. The next initial selection bit string obtained by replacing with a non-selected bit is set as the selected bit string in the selected bit register in synchronization with the first clock, and the bit string data selection process by the bit string data selection circuit is executed. The process of setting the selection result bit string, which is the result of the bit string data selection process, in the selection result register in synchronization with the second clock and outputting the selection result bit string is performed for the N bit string data. Bit string data selection processing by the bit string data selection circuit and the selection result bit Bit string data sequentially selected circuit and repeating until the output is finished. In a bit string data sequential selection circuit for selecting bit string data in descending order from N (N is a positive integer of 2 or more) bit string data each having a bit length of m (m is a positive integer),
The bit string data selection circuit according to claim 14 ,
A selection bit register for holding a selection bit string to be input to the bit string data selection circuit;
A selection result register that holds a next selection bit string that is an output of the bit string data selection circuit as a selection result bit string;
The next initial selection of the selected bit string held in the selected bit register by replacing the bit at the same bit position as the selected bit in the selected result bit string held in the selected result register with a non-selected bit A next selection bit setting circuit for obtaining a bit string;
A first clock for causing the selection bit register to set the next initial selection bit string as the selection bit string is supplied to the selection bit register, and a second clock for holding the selection result bit string in the selection result register is provided. A sequential selection control circuit for supplying to the selection result register,
A bit string in which all the bits are the selected bits as an initial value of the next initial selected bit string is set in the selected bit register in synchronization with the first clock, and the bit string data selecting process by the bit string data selecting circuit is started. A selection result bit string that is a result of the bit string data selection processing is set in the selection result register in synchronization with the second clock, and the selection result bit string is output,
Further, the next selection bit setting circuit sets a bit at the same bit position as the bit position where the selection bit of the selection result bit string held in the selection result register of the selection bit string held in the selection bit register exists. The next initial selection bit string obtained by replacing with a non-selected bit is set as the selected bit string in the selected bit register in synchronization with the first clock, and the bit string data selection process by the bit string data selection circuit is executed. The process of setting the selection result bit string, which is the result of the bit string data selection process, in the selection result register in synchronization with the second clock and outputting the selection result bit string is performed for the N bit string data. Bit string data selection processing by the bit string data selection circuit and the selection result bit Bit string data sequentially selected circuit and repeating until the output is finished. In a bit string data sequential selection circuit for selecting bit string data in ascending or descending order from N (N is a positive integer of 2 or more) bit string data each having a bit length of m (m is a positive integer),
A bit string data selection circuit according to claim 15 ,
A selection bit register for holding a selection bit string to be input to the bit string data selection circuit;
A selection result register that holds a next selection bit string that is an output of the bit string data selection circuit as a selection result bit string;
The next initial selection of the selected bit string held in the selected bit register by replacing the bit at the same bit position as the selected bit in the selected result bit string held in the selected result register with a non-selected bit A next selection bit setting circuit for obtaining a bit string;
A first clock for causing the selection bit register to set the next initial selection bit string as the selection bit string is supplied to the selection bit register, and a second clock for holding the selection result bit string in the selection result register is provided. A sequential selection control circuit for supplying to the selection result register,
A bit string in which all the bits are the selected bits as an initial value of the next initial selected bit string is set in the selected bit register in synchronization with the first clock, and the bit string data selecting process by the bit string data selecting circuit is started. A selection result bit string that is a result of the bit string data selection processing is set in the selection result register in synchronization with the second clock, and the selection result bit string is output,
Further, the next selection bit setting circuit sets a bit at the same bit position as the bit position where the selection bit of the selection result bit string held in the selection result register of the selection bit string held in the selection bit register exists. The next initial selection bit string obtained by replacing with a non-selected bit is set as the selected bit string in the selected bit register in synchronization with the first clock, and the bit string data selection process by the bit string data selection circuit is executed. The process of setting the selection result bit string, which is the result of the bit string data selection process, in the selection result register in synchronization with the second clock and outputting the selection result bit string is performed for the N bit string data. Bit string data selection processing by the bit string data selection circuit and the selection result bit Bit string data sequentially selected circuit and repeating until the output is finished. The bit string data sequential selection circuit according to any one of claims 16 to 18 ,
The sequential selection control circuit further supplies the second clock to the next selection bit setting circuit;
The next selection bit setting circuit includes:
A selection bit string temporary holding register that holds the selection bit string held in the selection bit register in synchronization with the second clock;
A bit string operation is performed with the selected bit string held in the selected bit string temporary holding register as a non-selected bit at a bit position identical to the bit position where the selected bit exists in the selection result bit string, and the next initial A bit string data sequential selection circuit comprising a next selection bit string calculator for generating a selection bit string. The bit string data sequential selection circuit according to any one of claims 16 to 19 ,
The bit string data sequential selection circuit, wherein the second clock is obtained by inverting the first clock. The bit string data sequential selection circuit according to any one of claims 16 to 20 ,
By detecting that all the bits of the selection result bit string are non-selected bits, the bit string data selection processing by the bit string data selection circuit and the output of the selection result bit string for the N bit string data are completed. A bit string data sequential selection circuit that detects the bit string data.

Images