CN-115268830-B - Circuit and method for long sequence data ordering

CN115268830BCN 115268830 BCN115268830 BCN 115268830BCN-115268830-B

Abstract

The invention discloses a circuit and a method for sequencing long sequence data. The circuit is used for sequencing N data under a K system, the largest element in the data comprises m bits under the K system, the circuit comprises a base number counting unit, a first address generating unit, a data distributing unit and two sequencing buffers, the two sequencing buffers are respectively used as a source buffer and a target buffer, the two sequencing buffers can be used for reading out the data in a given address or writing one data into a designated address, the base number counting unit, the first address generating unit and the data distributing unit are sequentially connected, and the two sequencing buffers are respectively connected with the data distributing unit and the base number counting unit. The data sorting circuit is simple in structure and can be flexibly adjusted according to specific requirements, and the data sorting method has linear order time complexity and short sorting time.

Inventors

WANG YUXUAN
ZHOU ZIHENG
PAN HONGBING

Assignees

南京大学

Dates

Publication Date: 20260508
Application Date: 20220624

Claims (7)

1. The circuit for sequencing long-sequence data is characterized by comprising a base number counting unit, a first address generating unit, a data distributing unit and two sequencing buffers, wherein the base number counting unit, the first address generating unit and the data distributing unit are sequentially connected, and the two sequencing buffers are respectively used as a source buffer and a target buffer and can be used for reading out the data in a given address or writing one data into a designated address; The radix counting unit comprises K element number registers ~ The radix counting unit is expressed as a current input element in a K system Corresponding element number counter The value of (2) is added to 1; the head address generating unit comprises K head address registers ~ Respectively connected with the K element number registers in one-to-one correspondence, wherein the first address register Constant 0, remaining head address registers ~ The value of (2) is accumulated by all element number registers with the base number smaller than that of the current first address register in the base number counting unit; the data allocation unit includes K address pointer registers ~ The data distribution unit reads out the data in the source buffer area from 0 in sequence from small to large and according to the base number of the corresponding bit of the current data to be distributed Select the first Address pointer register And write the current data to be allocated into the address pointer register in the target buffer The address pointed to.
2. A circuit for long sequence data ordering according to claim 1, characterized in that the two ordering buffers are each capable of accommodating at least all N data.
3. A circuit for long sequence data sequencing according to claim 1 wherein the radix counting unit is connected to the source buffer and the circuit external data respectively via a data selector.
4. The circuit for long sequence data ordering according to claim 1, wherein the address pointer register when the data allocation unit starts a new data allocation ~ Head address registers assigned as head address generating units, respectively ~ When the bit base number corresponding to the input data to be distributed is When the cardinality is to be Corresponding first Address pointer register The value of (2) is increased by 1.
5. A sorting method using a circuit for sorting long sequence data according to claim 1, characterized in that the step of the sorting method comprises: Step one, inputting data to be sequenced into a source buffer area; sequentially counting the times of occurrence of the 0 th to m-1 th bits of input data in the K system and the 0 th to K-1 th bases in each bit by the base number counting unit in a plurality of data iterations, and recording the times in an element number register one by one; generating a first address of each base number in a target buffer area by the first address generating unit through accumulating element number registers, and storing the first address in the first address register in a one-to-one correspondence manner; Step four, the data distribution unit reads out the sequence to be sequenced from the source buffer area, and redistributes each element to the corresponding position of the target buffer area according to the address pointer register, when each element is redistributed, the value of the corresponding address pointer register is added with 1; And fifthly, sequentially reading the target buffer area after the last data redistribution is completed, and outputting the data to be sequenced from small to large.
6. The method of claim 5, wherein in the first step, the iterative data is from a source buffer or outside the circuit.
7. The sequencing method of claim 5 wherein said steps two through four are iterated m times.

Description

Circuit and method for long sequence data ordering Technical Field The invention relates to the field of digital signal processing, in particular to a hardware circuit and a method for realizing rapid data ordering of long sequences in an integrated circuit. Background In digital signal processing, it is often necessary to order a series of data. For example, it is necessary to estimate noise energy by solving the median of wavelet decomposition coefficients in the wavelet domain, or to find t maximum (or minimum) data from among the u data, to determine the priority level of these data. The software scheme is limited by processor resources, is generally low in speed, and is difficult to be used in occasions with high requirements on real-time performance, such as image processing, radar signal processing and the like. Because the circuit structure can be specifically optimized for the ordering method, the implementation of data ordering on hardware platforms such as FPGAs (field programmable gate arrays) generally has better performance than software schemes. Hardware implementations can be categorized into ordering networks and linear structures. The ordering network can generally achieve higher ordering speed through parallelization design, but as the sequence to be ordered is prolonged, the hardware complexity and the cost of the ordering network are exponentially increased, the cost of linear structure hardware resources is smaller, but the sequence to be ordered needs to be iterated for a plurality of times, and the ordering speed is relatively lower. Disclosure of Invention In view of the above drawbacks of the prior art, the present invention provides a circuit and method for ordering data for long sequences, which aims to achieve a higher ordering speed with less hardware complexity. In order to solve the technical problems, the invention adopts the following technical scheme: The circuit comprises a base number counting unit, a first address generating unit, a data distribution unit and two sequencing buffers, wherein the two sequencing buffers are respectively used as a source buffer and a target buffer, can be used for reading data in a given address or writing one data into a designated address, the base number counting unit, the first address generating unit and the data distribution unit are sequentially connected, and the two sequencing buffers are respectively connected with the data distribution unit and the base number counting unit. Further, the two sorting buffers can accommodate at least all N data, respectively. Further, the radix counting unit is connected with the source buffer and the circuit external data through the data selector respectively. Further, the radix counting unit comprises K element number registers ereg 0～eregK-1 in total, and when the current input element is represented as x in K system, the value of the corresponding element number counter ereg x is increased by 1. Further, the first address generating unit includes K first address registers saddr 0～saddrK-1, which are respectively connected with the K element number registers in a one-to-one correspondence manner, wherein the first address register saddr 0 is constantly 0, and the values of the remaining first address registers saddr 1～saddrK-1 are accumulated by all element number registers in the radix counting unit, where the radix number is smaller than that of the current first address register. Further, the data distribution unit comprises K address pointer registers paddr 0～paddrK-1 which are respectively connected with the K first address registers in a one-to-one correspondence manner, reads out the data in the source buffer area sequentially from 0 according to the sequence from small to large, selects the xth address pointer register paddr x according to the base number x of the corresponding bit of the data to be distributed currently, and writes the data to be distributed currently into the address pointed by the address pointer register paddr x in the target buffer area. Further, when the data allocation unit starts new data allocation, the address pointer registers paddr 0～paddrK-1 are respectively assigned as the first address registers saddr 0～saddrK-1 of the first address generation unit, and when the base number of the bit corresponding to the input data to be allocated is x, the value of the xth address pointer register paddr x corresponding to the base number x is added by 1. The invention provides a sequencing method of a circuit for sequencing long sequence data, which comprises the following steps: Step one, inputting data to be sequenced into a source buffer area; sequentially counting the times of occurrence of the 0 th to m-1 th bits of input data in the K system and the 0 th to K-1 th bases in each bit by the base number counting unit in a plurality of data iterations, and recording the times in an element number register one by one; generating a first address of each base number in a