CN100561421C - Circuit and method for realizing data sorting - Google Patents

Abstract

The invention discloses a circuit and method for realizing data sorting, which is invented to solve the problem that existing software sorting takes a long time and does not meet real-time requirements. The circuit and method of the present invention: according to the number n of extreme values to be searched, determine the register group, the comparator group, the multiplexer group where n selects 1, the first group of 2 selectors 1 multiplexer, and the second group The depth of the multiplexer and the extremum pointer register, and the width of the first group of 2-to-1 multiplexers and the second group of multiplexers and the extremum pointer register group; according to the number m of data sources, determine the circuit The running time is m clocks; according to the search value type, select the output type of the comparator; reset the register group, the extreme value pointer register group; input a sampling data to the circuit every clock cycle; stop the circuit after m clocks, At this time, n extreme values are stored in the register group. The circuit and the method of the present invention have strong real-time processing capability, and the sorting time is doubled.

Description

Circuit and method for realizing data sorting

technical field

The invention relates to the field of digital signal processing, in particular to a hardware circuit and method for realizing data sorting.

Background technique

In digital signal processing, it is often necessary to sort a series of data, such as sorting the size order of m data, or finding the n largest (or smallest) data from m data, m≥n, to Prioritize this data.

Existing technologies are mainly software sorting. Although there are many algorithms for software sorting, due to the slow computing speed of the software, it cannot meet the environment with high real-time requirements. For example, when the base station of the communication system searches for a cell, it needs to find the real signal from a large amount of data and quickly feed back the information to the mobile terminal. When there are many communities, the amount of data to be processed is very large, often reaching the order of 100,000. The software cannot search and sort so much data in such a short period of time.

Contents of the invention

In order to overcome the above-mentioned defects, the object of the present invention is to provide a hardware circuit and method for realizing data sorting that meet the requirements of relatively high real-time performance.

In order to achieve the above object, a circuit for realizing data sorting of the present invention includes:

A register group (A), a comparator group (B), a multiplexer group (C) where n selects 1, a multiplexer group (D) where the first 2 selects 1, and a second 2 selector group 1 multiplexer group (E), an extreme value pointer register group (F), an address decoder (G), an AND gate array (H); said register group (A), comparator group ( B), the number of the multiplexer group (C) and the extreme value pointer register group (F) that n selects 1 is n, and the multiplexer group (D) that the first 2 selects 1 and the second 2 The number of multiplexer groups (E) that select 1 is n-1;

Wherein, n is the integer greater than 1, defines i=0,1,...,n-1,

The register group (A) is used to store the current extreme value in the sorting process, and the output of the register group (A) and the data input of this circuit are used as the input of the comparator group (B);

The comparison results output by the comparators (B0, B-1, ..., B-n-1) in the comparator group (B) are used as the input of the multiplexer (C-i) where each n selects 1;

The extremum pointer register group (F) is used to record the storage location and current extremum sequence of the register group (A) where the current extremum is located, and serves as the control terminal of the multiplexer group (C) where n selects 1;

The i+1th n-choice multiplexer (C-i) outputs the result of comparing the data input by this circuit with the current extreme value, as the i+1th first 2-choice 1 multiplexer (D-i) The selection control terminal,

The i+1th extreme value pointer register (F-i) and the nth extreme value pointer register (F-n-1) are used as the input end of the i+1th first 2-to-1 multiplexer (D-i) ;

The output of the ith n-selecting 1 multiplexer (C-i-1) is used as the selection control terminal of the i+1 second 2-selecting 1 multiplexer (E-i);

The output of the i+1 first 2-choice 1 multiplexer (D-i) and the i-th extreme value pointer register (F-i-1) are used as the i+1 second 2-choice 1 multiplexer ( E-i) input;

The output of the i+1 second 2-to-1 multiplexer (E-i) is used as the input of the i+1 extreme value pointer register (F-i);

The n-1th extreme value pointer register (F-n-1) is used as the input end of the address decoder (G);

The output of the n-1 multiplexer (C-n-1) and the address decoder (G) for n selecting 1 is used as the input of the AND gate array (H);

The output of the AND gate array (H) is connected to the input enable terminal of the register (A).

Wherein, the data input of the circuit is connected to the register group (A) and the comparator group (B), and the register group (A) and the extremum pointer register group (F) are connected to the output.

Wherein, the address decoder (G) and the AND gate array (H) are combined into an address decoder with an enable terminal.

In order to achieve the above object, the present invention provides a method for realizing data sorting based on the circuit described in claim 1, comprising:

(1) According to the number n of extremum values to be searched, determine the register group (A) with a depth of n, the comparator group (B), the multiplexer group (C) where n selects 1, and the extremum pointer register group ( F); and the first group of 2-choice multiplexers (D) and the second group of multiplexer groups (E) with a depth of n-1; wherein, the n-choice 1 multiplexer group The output bit width of each selector of (C) is 1, the multiplexer (D) of described first group of 2 selecting 1, the second group of multiplexer (E) and the extremum pointer register group (F ) The output bit width of each unit is greater than or equal to or equal to the minimum integer of log 2(n);

(2) According to the number m of data sources, determine the running time of the circuit as m clocks;

(3) Select the output type of the comparator group (B) according to the search value type;

(4) reset register group (A), extreme value pointer register group (F);

Each register in the described extremum pointer register group (F) will be reset to different values respectively; its maximum value;

(5) Each clock inputs sampling data to the circuit;

(6) Stop the circuit after m clocks.

The method and device of the invention overcome the disadvantages that software sorting takes a long time and cannot be used in occasions with high real-time requirements. The present invention uses a hardware circuit to realize the sorting of data. Each clock of this circuit can process one data. The current integrated circuit can generally work above 100MHz, and the time for sorting 100,000 data is less than 1ms. If multiple sets of sorting circuits are used Working in parallel, the sorting time can also be reduced exponentially, so this circuit has strong real-time processing performance and can meet the occasions that require relatively high processing time.

Description of drawings

Fig. 1 is a schematic diagram of a singly linked list;

Fig. 2 rearranges Fig. 1 and removes the singly linked list obtained after the null pointer;

Fig. 3 is a multiplexer that selects 1 from 2;

Fig. 4 is a multiplexer of 16 selections;

Fig. 5 is the circuit structure block diagram that the present invention realizes data sorting;

Fig. 6 is a specific embodiment of realizing data sorting in the present invention;

FIG. 7 is a flow chart of the method for implementing data sorting in the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments.

The main idea of this method comes from the single-linked list in the software data structure. The single-linked list is a structure for storing data. When accessing the data stored in the linked list, it is necessary to query a set of pointers. The content of this set of pointers is the storage of these data. Location.

Figure 1 is a schematic diagram of a singly linked list, the head pointer is the storage location of d0, the pointer 1 is the storage location of d1, ..., the pointer n is the storage location of dn, and the last is a null pointer, if n is a fixed number, The final null pointer may not be used.

Figure 2 is the singly linked list obtained after rearranging Figure 1 and removing the null pointer.

In order to better explain the present invention, some elements used in the present invention are described below.

Figure 3 is a 2-to-1 multiplexer, i0, i1 are data input ports, s is a selection control port, z is an output port, when s is 0, the output of z is i0, when s is 1, The output of z is i1.

Figure 4 is a 16-to-1 multiplexer, i is the data input port, s is the selection control port, and z is the output port. The bit width of i is 16, and i is composed of i15, i14, i13,..., i1, i0; the bit width of s is 4, and the value range is 0~15. When the value of s is j, the output of z is j, where the value of j ranges from 0 to 15. If the input bit width of a multiplexer is other values, its working principle is similar to that of a 16-to-1 multiplexer. A 2-to-1 multiplexer can be used to build a 16-to-1 multiplexer or other types of multiplexers, which are discussed in general digital circuit textbooks and will not be repeated here.

A general-purpose comparator generally has two inputs a and b, and three outputs. One output judges whether a is greater than b, one judges whether a is equal to b, and the other judges whether a is smaller than b.

The comparator used in the present invention only needs one output, and it can judge whether a is greater than b or whether a is smaller than b as required.

The sorting circuit of the present invention is mainly used to find out the n largest (or smallest) data from m data, m≥n, and at the same time realize the size sorting of the n largest (or smallest) values.

As shown in Figure 5, this circuit is mainly composed of the following parts: a set of registers A, a set of comparators B, a set of n to 1 multiplexer C, a set of 2 to 1 multiplexer D , a group of 2-to-1 multiplexers E, a group of extremum pointer registers F, an address decoder G, and an AND gate array H.

The input of this circuit is connected to register group A and comparator group B, and the output of this circuit is register group A and extremum pointer register group F.

The output of the AND gate array H is connected to the input enable terminal of the register group A; the output of the register group A and the data input of this circuit are used as the input of the comparator group B; the output of the comparator group B is used as the input of the multiplexer group C Input, the extreme value pointer register group F is used as the control terminal of the multiplexer group C; the output of the multiplexer group C is used as the control terminal of the multiplexer group D, and the extreme value pointer register group F is used as the multiplexer group The input terminal of D; the output of the multiplexer group C is used as the control terminal of the multiplexer group E, and the output of the multiplexer group D and the extreme value pointer register group F are used as the input terminal of the multiplexer group E; The output of the multiplexer group E is used as the input terminal of the extreme value pointer register group F; the extreme value pointer register group F is used as the input terminal of the address decoder G; the output of the multiplexer group C and the address decoder G is used as Input to AND gate array H.

The circuit is suitable for finding n largest or smallest data from m data, and realizing size sorting of the largest or smallest data.

The address decoder and the AND gate array can be combined into an address decoder with an enable terminal.

The method for sorting data by utilizing the above circuit comprises the following steps:

Step 1, according to the number n of maximum value (or minimum value) to be searched, determine register A, comparator B, n in the circuit of the present invention select 1 multiplexer C, 2 select 1 multiplexer D, The depth of the 2-to-1 multiplexer E, the extremum value pointer register F, and the width of the 2-to-1 multiplexer D, the 2-to-1 multiplexer E, and the extremum pointer register F;

The depth of A, B, C, F is n, the depth of D, E is n-1, the width of C is 1, and the width of D, E, F is the smallest integer greater than or equal to log2(n).

Step 2. Select the number m of data sources to be searched to determine the running time of the circuit as m clocks.

Step 3. Select the output type of the comparator according to the search value type, that is, to find the maximum value or the minimum value.

Step 4, reset register group A, extreme value pointer register group F;

F should be reset to 0, 1, 2, ..., n-1 respectively, and the values after reset should be guaranteed to be different; when searching for the maximum value, all register group A is reset to its minimum value, otherwise all register group A is reset to its maximum value.

Step 5, each clock cycle inputs a data (sampling) to this circuit;

Step 6. Stop the circuit after m clocks. At this time, n extreme values are stored in the register group A, and the magnitude order of these extreme values is stored in the extreme value pointer register group F.

Register group A is used to save the current n extremum values, and extremum pointer register group F is used to record the magnitude order of each extremum value in A.

The new sample is compared with all values in A at the same time, and whether the new sample is a new extremum is judged according to the comparison result of the extremum pointer register group F and the comparator group B, and the new order of magnitude is judged at the same time.

If the current sample is not a new extremum, the order of the original size remains unchanged, otherwise one of the original extremum will no longer be an extremum, and the storage position of this extremum in A will become the write of the current sample in A into position.

The above-mentioned adjustment of the extreme value order and the operation of judging the writing position of the current sample are performed through the multiplexer group C of n to 1, the multiplexer group D of 2 to 1, the multiplexer group E of 2 to 1, The extremum pointer register group F, the address decoder G and the AND gate array H are realized together.

Taking the selection of 16 maximum values from 1000 unsigned data as an example, the circuit of the present invention will be explained in detail below.

The principle of finding the minimum value is similar to the principle of finding the maximum value.

The detailed structure of this circuit is shown in accompanying drawing 6, 16 extremum pointer registers record the storage position of current 16 maximum values in register group A, pointer register F-0 records the position of current maximum value, pointer register F- 1 records the position of the current second largest value, ..., the pointer register F-14 records the position of the current second smallest value, and the pointer register F-15 records the position of the current minimum value. Although 16 maximum values are stored in memory A, they are not necessarily stored in order of size, and the order of their size is recorded by the 16 extreme value pointer registers here.

After the current sample comes in, it is compared with the 16 values in register group A at the same time to determine whether it is a new extreme value. If the current sample is not as large as the minimum of the current 16 maximum values, A and F do not need to be updated; if the current sample is larger than any of the previous 16 maximum values, the current sampled data will be written into the original 16 maximum values value, and adjust the contents of 16 extreme value pointers at the same time, that is, adjust the order of the size of each data in register group A at the same time.

After the system is reset, all the register group A is reset to 0, and the 16 pointer registers F are reset, where the pointer register F-0 is reset to 15, the pointer register F-1 is reset to 14, and the pointer register F-2 is reset to 13, ..., the pointer register F-14 is reset to 1, and the pointer register F-15 is reset to 0 (as shown on the far right in FIG. 6 ).

The 16 values A-0, A-1, ..., A-15 in register group A are compared with the current sample at the same time, and 16 comparators B-0, B-1, ..., B-15 are used for comparison, if The current sampling is larger than A-s, and the output of B-s is 1, otherwise, the output of B-s is 0, s=0,...15. The extreme value pointer register F-i records the storage location of the i-th maximum value, i=0, ... 15, so the comparison result of the i-th maximum value and the current sampling can be obtained through the extreme value pointer register F-i. There are 16 16-to-1 multiplexers in the multiplexer group C, the extreme value pointer register F-i is used as the selection control terminal of C-i, and B-0, B-1, ..., B-15 are used as the input of C-i , the output of C-i is the comparison result between the extreme value corresponding to the extreme value pointer register F-i and the size of the current sample (as shown in Figure 6).

Among the 16 maximum value pointer registers, the extreme value pointer register F-i records the storage location of the current i-th maximum value, i=0,...,15, that is, the extreme value pointer 0 corresponds to the current maximum value, and the extreme value pointer 1 corresponds to The current next largest value, ..., the extreme value pointer 15 corresponds to the minimum value among the current 16 maximum values.

If the current sample is not greater than the minimum of the current 16 maximum values in register bank A, then register bank A and the extremum pointer register bank F remain unchanged; if the current sample is greater than any of the current 16 maximum values in register bank A If one is large, the current sample is written to the position of the minimum value among the original 16 maximum values, that is, the value of the extreme value pointer register F-15.

For any pointer register F-i in the 16 extreme value pointer registers, if the current sample is not as large as its corresponding value, the content of the pointer register F-i does not need to be changed; if the current sample just replaces the value of the original i-th maximum value size position, the pointer register F-i is replaced by the content of the pointer register F-15; if the current sample is larger than the corresponding value of the pointer register F-i-1, the content of the pointer register F-i is replaced by the content of the pointer register F-i-1; here , the priority of the comparison result between the current sample and the i-1th maximum value is higher than the comparison result between the current sample and the i-th maximum value.

In the present invention, its circuit is realized as: using the comparison result C-i of the ith maximum value and the current sampling as the selection control terminal of the multiplexer D-i, F-15 and F-i as the input of D-i, when C-i is 1, D-i The output is F-15, otherwise the output is F-i; the comparison result C-i-1 of the i-1th maximum value and the current sampling is used as the selection control terminal of the multiplexer E-i, and D-i and F-i-1 are used as the input of E-i , when C-i-1 is 1, the output of E-i is F-i-1, otherwise the output is D-i; the output of E-i is used as the input of pointer F-i, as shown in Figure 6.

For pointer 0, since pointer 0 corresponds to the maximum value among the 15 maximum values, E-0 is not needed, and the output of D-0 is directly used as the input of F-0, as shown in FIG. 6 .

For E-15, since the two input terminals of D-15 are both F-15, it is not necessary to use D-15, and directly use F-15 and F-14 as the input of E-15, as shown in Figure 6 shown in .

The write position of the current sample is the output of the extremum pointer register F-15, and the current sample is connected to the input port of all registers in register group A, and each register in register group A has an enable port. The output of the extremum pointer register F-15 is sent to the 4-16 decoder G, and the enable of each register in the register group A is generated by G and the AND gate array H. The output bit width of the address decoder G is 16, and its output signals are respectively G15, G14, . . . , G1, G0. When the input value of the 4-16 decoder is s, its output Gs is valid, and other outputs are invalid, s=0,1,...15. Whether the current sampling should be written into register group A still needs to be judged according to C-15. The AND gate array H ANDs the outputs G15, G14, ..., G1, G0 of G with C-15 respectively, and H15, H14, ..., H1, H0, Hs are connected to the enable ports of A-s. In this way, whether the current sample can be written into register group A can be controlled according to whether the current sample is a new extreme value.

Through the above operation, after 1000 clocks, 16 maximum values can be selected, and these values are stored in register group A, and their storage locations in register group A are stored in 15 extreme value pointer registers, which are extremely The value pointer register F-0 corresponds to the maximum value, the pointer register F-1 corresponds to the next largest value, ..., and the pointer register F-15 corresponds to the minimum value among the 16 maximum values.

Utilize the process that the device among Fig. 6 finds maximum value, comprise the following steps:

Step 1. According to the number 16 of the maximum value to be found, it can be determined that the depth of A, B, C, and F is 16, the depth of D, E is 15, the width of C is 1, and the width of D, E, and F is 4 ;

Step 2. According to the number of 1000 data sources to be searched, determine that the running time of the circuit is 1000 clocks,

Step 3, according to the search type, that is, to find the maximum value and select the output type of the comparator;

Step 4, reset all the register group A to 0, and reset the extremum pointer register group F to 0, 1, 2, ..., 15 respectively;

Step 5, each clock inputs a data (sampling) to the circuit of the present invention;

Step 6. Stop the circuit after 1000 clocks. At this time, the 16 maximum values are stored in the register group A, and the extreme value pointer register group F stores the order of the magnitudes of these extreme values.

By adopting the method and device of the present invention, compared with the prior art, the present invention overcomes the disadvantages that software sorting takes a long time and cannot be used in occasions with high real-time requirements. The present invention uses a hardware circuit to realize the sorting of data. Each clock of this circuit can process one data. The current integrated circuit can generally work above 100MHz, and the time for sorting 100,000 data is less than 1ms. If multiple sets of sorting circuits are used Working in parallel, the sorting time can also be reduced exponentially, so this circuit has strong real-time processing performance and can meet the occasions that require relatively high processing time.

Claims (4)

1, a kind of circuit of realizing data sorting comprises:

One registers group (A), a comparator bank (B), a n selects 1 MUX group (C), one the 1 selects 1 MUX group (D), and one the 22 selects 1 MUX group (E), an extreme value pointer register set (F), one address decoder (G), one with gate array (H); Described registers group (A), comparator bank (B), it is n that n selects 1 the MUX group (C) and the number of extreme value pointer register set (F), the described the 1 to select 1 MUX group (D) and the 22 to select the number of 1 MUX group (E) be n-1;

Wherein, n is the integer greater than 1, definition i=0, and 1 ..., n-1;

Described registers group (A) is used for the current extreme value of memory sequencing process, and the output of registers group (A) and the data of this circuit are imported the input of device group (B) as a comparison;

Each comparer in the described comparator bank (B) (B-0, B-1 ..., B-n-1) Shu Chu comparative result selects the input of 1 MUX (C-i) as each n;

Described extreme value pointer register set (F) is used to write down the memory location and the current extreme value order of current extreme value place registers group (A), and selects the control end of 1 MUX group (C) as n;

Described i+1 n selects 1 MUX (C-i) to export data and the current ratio of extreme values result of the input of this circuit, selects the selection control end of 1 MUX (D-i) as i+1 the individual the 1,

Described i+1 extreme value pointer register (F-i) and described n extreme value pointer register (F-n-1) select the input end of 1 MUX (D-i) as i+1 the individual the 1;

The selection control end of 1 MUX (E-i) is selected in the output that described i n selects 1 MUX (C-i-1) as i+1 the 22;

Described i+1 the individual the 1 selects the output of 1 MUX (D-i) and i extreme value pointer register (F-i-1) selects 1 MUX (E-i) as i+1 the individual the 22 input;

Described i+1 the individual the 22 selects the input of the output of 1 MUX (E-i) as i+1 extreme value pointer register (F-i);

Described n extreme value pointer register (F-n-1) is as the input end of address decoder (G);

The output that described n n selects 1 MUX (C-n-1) and address decoder (G) as with the input of gate array (H);

Described and output gate array (H) is connected to the input Enable Pin of register (A).

2, the circuit of realization data sorting according to claim 1 is characterized in that, the data input of this circuit is connected to registers group (A) and comparator bank (B), and registers group (A) and extreme value pointer register set (F) are connected to output.

3, the circuit of realization data sorting according to claim 1 is characterized in that, described address decoder (G) and with gate array (H) be combined as one the band Enable Pin address decoder.

4, a kind of method based on the described circuit realization of claim 1 data sorting comprises:

(1), determines that the degree of depth is that registers group (A), comparator bank (B), the n of n selects 1 MUX group (C) and extreme value pointer register set (F) according to the extreme value number n that will search; And the degree of depth is that the 1 of n-1 selects 1 the MUX group (D) and the second MUX group (E); Wherein, it is the 1, the described the 1 to select the output bit wide of each unit in 1 MUX group (D), the second MUX group (E) and the extreme value pointer register set (F) for being greater than or equal to log that described n selects the output bit wide of each selector switch of 1 MUX group (C) ₂(n) smallest positive integral;

(2) according to the number m of data source, be m clock the working time of determining circuit;

(3) according to searching value type, select the output type of comparator bank (B);

(4) reseting register group (A), extreme value pointer register set (F);

Each register in the described extreme value pointer register set (F) will be reset to different values respectively; When searching maximal value, described registers group (A) all is reset to its minimum value, otherwise registers group (A) all is reset to its maximal value;

(5) each the time clockwise to the circuit input sampling data;

(6) stop this circuit through behind m clock.

Images