1.本发明涉及数字信号处理领域，具体涉及一种在集成电路中实现对长序列进行快速数据排序的硬件电路及方法。
背景技术：2.在数字信号处理中，常常需要对一系列数据进行排序。例如，在小波域中需要通过求解小波分解系数的中值估算噪声能量，或者从u个数据中找出t个最大(或最小)的数据，以确定这些数据的优先级别。
3.在软件平台上实现数据排序的方案较多，如冒泡排序、堆排序等；软件方案受制于处理器资源，通常速度较慢，难以胜任图像处理、雷达信号处理等对实时性要求较高的场合。
4.由于可以针对排序方法对电路结构进行特定的优化，因此在fpga等硬件平台上实现数据排序通常具有较软件方案更优的性能。硬件实现方案可分为排序网络和线性结构两类。排序网络通过并行化设计，通常能够取得较快的排序速度，但随着待排序序列的延长，排序网络的硬件复杂度与开销将呈指数级增长；线性结构硬件资源开销较小，但需要对待排序序列进行多次迭代，往往具有平方阶时间复杂度，排序速度相对较慢。
技术实现要素：5.针对以上现有技术的缺陷，本发明提供了一种针对长序列进行数据排序的电路及方法，旨在以较小的硬件复杂度实现较高的排序速度。
6.为解决上述技术问题，本发明采用的技术方案如下：
7.一种用于长序列数据排序的电路，用于对n个数据在k进制下进行排序，且数据中的最大元素在k进制下包含m位；所述电路包括基数计数单元、首地址生成单元、数据分配单元和两个排序缓冲区，两个排序缓冲区分别作为源缓冲区与目标缓冲区，均可以读出给定地址中的数据，或将一个数据写入指定地址；所述基数计数单元、首地址生成单元和数据分配单元依次相连；所述两个排序缓冲区均分别与数据分配单元和基数计数单元相连。
8.进一步地，所述两个排序缓冲区分别至少能容纳全部n个数据。
9.进一步地，所述基数计数单元通过数据选择器分别连接源缓冲区和电路外部数据。
10.进一步地，所述基数计数单元共包含k个元素个数寄存器ereg0～ereg
k-1
；所述基数计数单元在当前输入元素在k进制下表示为x时，对应的元素个数计数器ereg
x
的值加1。
11.进一步地，所述首地址生成单元包含k个首地址寄存器saddr0～saddr
k-1
，分别与所述k个元素个数寄存器一一对应连接；其中首地址寄存器saddr0恒为0，其余首地址寄存器saddr1～saddr
k-1
的值由所述基数计数单元中基数编号小于当前首地址寄存器的的全部元素个数寄存器累加得到。
12.进一步地，所述数据分配单元包含k个地址指针寄存器paddr0～paddr
k-1
，分别与
所述k个首地址寄存器一一对应连接；所述数据分配单元按照从小到大的顺序从0开始依次读出源缓冲区中的数据，并根据当前待分配数据对应位的基数x选中第x个地址指针寄存器paddr
x
，并将当前待分配数据写入目标缓冲区中地址指针寄存器paddr
x
所指向的地址。
13.进一步地，所述数据分配单元开始新的数据分配时，地址指针寄存器paddr0～paddr
k-1
分别被赋值为首地址生成单元的首地址寄存器saddr0～saddr
k-1
；当输入的待分配数据对应位基数为x时，将基数x对应的第x个地址指针寄存器paddr
x
的值加1。
14.本发明提供上述一种用于长序列数据排序的电路的排序方法，其步骤包括：
15.步骤一，将待排序数据输入源缓冲区；
16.步骤二，基数计数单元在多次数据迭代中依次统计输入数据在k进制下第0至第m-1位、每一位中基数0至基数k-1出现的次数，并一一记录在元素个数寄存器中；
17.步骤三，首地址生成单元通过累加元素个数寄存器，产生每个基数在目标缓冲区中的首地址，并一一对应地存入首地址寄存器；完成全部累加后数据分配单元的地址指针寄存器一一对应地配置为首地址寄存器；
18.步骤四，数据分配单元从源缓冲区中顺序读出待排序序列，并依据地址指针寄存器将每个元素重分配至目标缓冲区的对应位置；每一个元素被重分配时，对应的地址指针寄存器的值都将加1；重分配完成后交换源缓冲区与目标缓冲区；
19.步骤五，顺序读取最后一次数据重分配完成后的目标缓冲区，即可将所述待排序数据从小到大输出。
20.进一步地，所述步骤一中，迭代数据来自源缓冲区或者电路外部。对所述步骤二至步骤四进行m次迭代。
21.与现有技术相比，本发明的有益效果在于：
22.1、本发明采用“基数排序”的方案，具有稳定的线性阶时间复杂度o(m*n)(m为排序所需的迭代次数)，对长序列排序的速度远优于平方阶时间复杂度的传统方案。。
23.2、本发明可基于现场可编程门阵列(fpga)实现，克服了现有软件实现方案速度慢的缺陷，可用于实时信号处理等对数据处理速度要求较高的领域。
24.3、本发明电路结构简单，且参数化难度低，可依据硬件资源情况快速灵活调整基数选取策略及排序迭代次数，在资源有限的情况下达到最优的排序性能。具有速度快、开销小、易拓展的特点。
附图说明
25.图1是本发明数据排序电路的实施例结构图；
26.图2是本发明数据排序方法的流程图；
27.图3是本发明基数计数单元与首地址生成单元的工作方式；
28.图4是本发明数据分配单元的工作方式；
29.图5是本发明排序耗时与传统方案的对比。
具体实施方式
30.为了更好地理解本发明，下面结合具体实施例对本发明作进一步说明。
31.本发明的一个实施例，用于在16进制下对一个包含1024个元素的序列进行排序，
且序列中最大的元素位宽不超过16bit，即在16进制下共包含m＝4位。如图1所示，该排序电路包括：一个基数计数单元，一个首地址生成单元、一个数据分配单元和两个排序缓冲区。
32.其中，两个排序缓冲区，即第一排序缓冲区与第二排序缓冲区分别至少能容纳全部1024个排序数据。第一排序缓冲区与第二排序缓冲区分别作为源缓冲区与目标缓冲区，若其一为源缓冲区，则另一为目标缓冲区，二者可根据排序的迭代情况互相交换。两个排序缓冲区均可以读出给定地址中的数据，或将一个数据写入指定地址。
33.基数计数单元共包含16个元素个数寄存器ereg0～ereg
15
。基数计数单元在当前输入元素在16进制下某一位表示为x(x为16进制下的基数)时，对应的元素个数计数器ereg
x
的值加1。基数计数单元可通过一个2路数据选择器选择数据输入来自排序电路外部，还是来自源缓冲区。基数计数单元可根据当前排序的迭代次数对选择当前输入元素在16进制下的不同位进行基数个数统计。每次统计开始前，基数计数单元清零16个元素个数寄存器ereg0～ereg
15
。每次统计完成后，元素个数寄存器ereg0～ereg
15
的值被首地址生成单元用于计算基数首地址。
34.首地址生成单元包含16个首地址寄存器saddr0～saddr
15
。其中首地址寄存器saddr0恒为0；其余首地址寄存器saddr1～saddr
15
的值由基数计数单元中基数编号小于该首地址寄存器的的全部元素个数寄存器累加得到。
35.数据分配单元包含16个地址指针寄存器paddr0～paddr
15
。数据分配单元可以按照从小到大的顺序从0开始依次读出源缓冲区中的数据，并根据当前待分配数据对应位的基数x选中第x个地址指针寄存器paddr
x
，并将当前待分配数据写入另一个排序缓冲区中paddr
x
所指向的地址。
36.在一次数据重分配开始前，数据分配单元的16个地址指针寄存器paddr0～paddr
15
被一一对应地配置为首地址生成单元中16个首地址寄存器saddr0～saddr
15
的值。当输入的待分配数据对应位基数为x时，将基数x对应的第x个地址指针寄存器paddr
x
的值加1。
37.相应的，如图2所示，本发明实施例提供一种利用上述数据排序电路对长度为1024的待排序序列在16进制下进行排序的方法，且序列中最大的元素位宽不超过16bit，即在16进制下共包含4位。排序方法具体包括以下步骤：
38.步骤一，数据输入。如图1所示，待排序数据f10从地址0开始顺序输入第一排序缓冲区，直至写入全部1024个数据。数据输入完成后第一排序缓冲区为源缓冲区，第二排序缓冲区为目标缓冲区。
39.步骤二，统计元素基数个数。在统计开始前，将基数计数单元包含的16个元素个数寄存器ereg0～ereg
15
全部清零；首地址生成单元的16个首地址寄存器saddr0～saddr
15
全部清零。当待排序序列在步骤四中在两个缓冲区之间传递时，基数计数单元统计待排序序列在16进制下第l位基数0～基数15(即k-1)出现的次数，其中l的值依据排序迭代次数可能为1，2或3(0＜l≤m-1)。如图1所示，此时基数计数单元的输入来自源缓冲区，即数据流f40(或根据迭代次数不同，来自f40’)。基数计数单元在当前输入元素第l位在16进制下表示为x(0＜x≤k-1)时，对应的元素个数计数器ereg
x
的值加1。例如，当前输入元素第l位在16进制下表示为3时，对应的元素个数计数器ereq3的值加1；
40.特别的，当待排序序列在步骤一中由外部输入第一排序缓冲区时，基数计数单元统计待排序序列在16进制下第0位基数0～基数15出现的次数。如图1所示，此时基数计数单
元的输入来自排序电路外部输入，即数据流f10。
41.在一次排序中迭代执行步骤二时，若本次执行统计了待排序序列在16进制下第l位基数0～基数15出现的次数，则下一次执行时统计待排序序列在16进制下第l+1位基数0～基数15出现的次数。例如，第一次执行步骤二时统计16进制下第0位基数0～基数15出现的次数，则第二次执行步骤二时统计16进制下第1位基数0～基数15出现的次数。
42.如图3所示，一个包含0x891a，0x3200，0x010a，0x02b7四个元素的序列。步骤一，即数据输入第一排序缓冲区时，基数计数单元统计待排序序列在16进制下第0位中基数0～基数15出现的次数，即，基数10(16进制下表示为0xa)两次，基数7一次，基数0一次，故元素个数寄存器ereg
10
、ereg7与ereg0的值分别为2、1、1，其余元素个数寄存器则为0；第一次进行步骤二迭代时，所述基数计数单元统计待排序序列在16进制下第1位中基数0～基数15出现的次数，即，基数11(16进制下表示为0xb)一次，基数1一次，基数0两次，故元素个数寄存器ereg
11
、ereg1与ereg0的值分别为1、1、2，其余元素个数寄存器则为0。
43.步骤三，生成目标缓冲区基数首地址。基数计数单元在步骤二中完成待排序序列在16进制下第l位基数0～基数15出现的次数后，基数计数单元将元素个数寄存器ereg0～ereg
15
的值发送至首地址生成单元，即图1中的数据流f20。首地址生成单元通过元素个数寄存器ereg0～ereg
15
的值计算每个基数在目标缓冲区中对应的首地址，并存入首地址寄存器saddr0～saddr
15
。其中第0个首地址寄存器的值恒为0，其余第x个首地址寄存器saddr
x
的值为第0～x-1个元素个数寄存器ereg0～ereg
x-1
的值的累加和。例如，第12个首地址寄存器saddr
12
的值为第0～11个元素个数寄存器ereg0～ereg
11
的值的累加和；计算完成后将首地址生成单元中的首地址寄存器saddr0～saddr
15
一一对应地写入所述数据重分配单元的地址指针寄存器paddr0～paddr
15
，即图1中的数据流f30。如图3所示，当基数计数单元完成对序列(0x891a，0x3200，0x010a，0x02b7)在16进制下第0位的基数个数统计后，首地址生成器依据元素个数寄存器的值产生各基数对应的首地址。如基数6对应的首地址为前五个元素个数寄存器的累加和，即1；基数11对应的首地址为前10个元素个数寄存器的累加和，即4。
44.步骤四，数据重分配。数据分配单元从源缓冲区顺序读出待排序序列，依据地址指针寄存器paddr0～paddr
15
指向的地址将每个元素重新分配到目标缓冲区。数据分配单元从地址0开始依次顺序读出源缓冲区中的数据，即图1中的f40(依据迭代次数不同，也可能为f40’)。若当前首地址寄存器saddr0～saddr
15
储存的是待排序序列在16进制下第l位基数0～基数15对应的首地址，则当当前待分配元素在第16进制下第l位的基数为x时，将该元素写入目标缓冲区中地址指针寄存器paddr
x
指向的地址，即图1中的f41(依据迭代次数不同，也可能为f41’)，同时将地址指针寄存器paddr
x
的值加1。当源缓冲区中的元素全部被重分配至目标缓冲区时，源缓冲区与目标缓冲区互换。若步骤四执行时通过待排序数据在16进制下的最高位，即第3位进行数据重分配，则本次步骤四执行完毕后执行步骤五，否则执行步骤二。
45.如图4所示，当前首地址寄存器saddr0～saddr
15
储存的是待排序序列在16进制下第1位基数0～基数15对应的首地址，且地址指针寄存器paddr1的值为23，paddr
11
的值为846。数据分配单元正从源缓冲区地址1014处顺序读出数据并进行重分配。
46.源缓冲区地址1014处储存的数据0x02be在16进制下第1位为b，即基数11，故元素0x02be被分配至目标缓冲区中地址指针寄存器paddr
11
指向的地址，即846，并将paddr
11
的
值加1，从而指向地址847。
47.源缓冲区地址1015处储存的数据0x801e在16进制下第1位为1，故元素0x801e被分配至目标缓冲区中地址指针寄存器paddr1指向的地址，即23，并将paddr1的值加1，从而指向地址24。
48.源缓冲区地址1016处储存的数据0x01bf在16进制下第1位为b，即基数11，故元素0x02be被分配至目标缓冲区中地址指针寄存器paddr
11
指向的地址，即847，并将paddr
11
的值加1，从而指向地址848。
49.由于本次数据重分配是根据排序序列在16进制下的第1位进行的，故本次步骤四执行完毕后，返回执行步骤二。
50.步骤五，数据输出。在4次迭代后所述数据分配单元在步骤四依据16进制下待排序元素每一位进行数据重分配后，从地址0开始顺序读出当前源缓冲区的数据，即可将原始待排序序列中的元素按从小到大的顺序输出。这一过程对应了图1中的数据流f50(依据迭代次数不同也可能为f50’)。在本实施例中，由于排序共进行了四次迭代，故步骤五的源缓冲区为第一排序缓冲区，输出数据流为f50。
51.如图2所示，在一次完整的排序过程中，输入元素在16进制下待排序元素共包含4位，则除去步骤一数据输入与步骤五数据输出，步骤二～步骤四共需要循环迭代4次。
52.如图5所示，对长度超过512的长序列进行排序时，本发明(o(m*n)，m为排序所需的迭代次数)耗时远小于传统的对数阶时间复杂度算法(o(n log2(n))，如堆排序)和平方阶时间复杂度算法(o(n2)，如冒泡排序)。
53.以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和替换，这些改进和替换也应视为本发明的保护范围。
技术特征：1.一种用于长序列数据排序的电路，其特征在于，该电路用于对n个数据在k进制下进行排序，且数据中的最大元素在k进制下包含m位；所述电路包括基数计数单元、首地址生成单元、数据分配单元和两个排序缓冲区，两个排序缓冲区分别作为源缓冲区与目标缓冲区，均可以读出给定地址中的数据，或将一个数据写入指定地址；所述基数计数单元、首地址生成单元和数据分配单元依次相连；所述两个排序缓冲区均分别与数据分配单元和基数计数单元相连。2.根据权利要求1所述的一种用于长序列数据排序的电路，其特征在于，所述两个排序缓冲区分别至少能容纳全部n个数据。3.根据权利要求1所述的一种用于长序列数据排序的电路，其特征在于，所述基数计数单元通过数据选择器分别连接源缓冲区和电路外部数据。4.根据权利要求1至3之一所述的一种用于长序列数据排序的电路，其特征在于，所述基数计数单元共包含k个元素个数寄存器ereg0～ereg
k-1
；所述基数计数单元在当前输入元素在k进制下表示为x时，对应的元素个数计数器ereg
x
的值加1。5.根据权利要求4所述的一种用于长序列数据排序的电路，其特征在于，所述首地址生成单元包含k个首地址寄存器saddr0～saddr
k-1
，分别与所述k个元素个数寄存器一一对应连接；其中首地址寄存器saddr0恒为0，其余首地址寄存器saddr1～saddr
k-1
的值由所述基数计数单元中基数编号小于当前首地址寄存器的的全部元素个数寄存器累加得到。6.根据权利要求5所述的一种用于长序列数据排序的电路，其特征在于，所述数据分配单元包含k个地址指针寄存器paddr0～paddr
k-1
，分别与所述k个首地址寄存器一一对应连接；所述数据分配单元按照从小到大的顺序从0开始依次读出源缓冲区中的数据，并根据当前待分配数据对应位的基数x选中第x个地址指针寄存器paddr
x
，并将当前待分配数据写入目标缓冲区中地址指针寄存器paddr
x
所指向的地址。7.根据权利要求6所述的一种用于长序列数据排序的电路，其特征在于，所述数据分配单元开始新的数据分配时，地址指针寄存器paddr0～paddr
k-1
分别被赋值为首地址生成单元的首地址寄存器saddr0～saddr
k-1
；当输入的待分配数据对应位基数为x时，将基数x对应的第x个地址指针寄存器paddr
x
的值加1。8.利用如权利要求1所述一种用于长序列数据排序的电路的排序方法，其特征在于，所述排序方法的步骤包括：步骤一，将待排序数据输入源缓冲区；步骤二，基数计数单元在多次数据迭代中依次统计输入数据在k进制下第0至第m-1位、每一位中基数0至基数k-1出现的次数，并一一记录在元素个数寄存器中；步骤三，首地址生成单元通过累加元素个数寄存器，产生每个基数在目标缓冲区中的首地址，并一一对应地存入首地址寄存器；完成全部累加后数据分配单元的地址指针寄存器一一对应地配置为首地址寄存器；步骤四，数据分配单元从源缓冲区中顺序读出待排序序列，并依据地址指针寄存器将每个元素重分配至目标缓冲区的对应位置；每一个元素被重分配时，对应的地址指针寄存器的值都将加1；重分配完成后交换源缓冲区与目标缓冲区；步骤五，顺序读取最后一次数据重分配完成后的目标缓冲区，即可将所述待排序数据从小到大输出。
9.根据权利要求8所述的排序方法，其特征在于，所述步骤一中，迭代数据来自源缓冲区或者电路外部。10.根据权利要求8所述的排序方法，其特征在于，对所述步骤二至步骤四进行m次迭代。
技术总结本发明公开了一种用于长序列数据排序的电路及方法。该电路用于对N个数据在K进制下进行排序，且数据中的最大元素在K进制下包含m位；电路包括基数计数单元、首地址生成单元、数据分配单元和两个排序缓冲区，两个排序缓冲区分别作为源缓冲区与目标缓冲区，均可以读出给定地址中的数据，或将一个数据写入指定地址；基数计数单元、首地址生成单元和数据分配单元依次相连；两个排序缓冲区均分别与数据分配单元和基数计数单元相连。本发明的数据排序电路结构简单，可根据具体需求进行灵活调整，且本发明的数据排序方法具有线性阶时间复杂度，排序时间较短。序时间较短。序时间较短。
技术研发人员：王宇宣 周自衡 潘红兵
受保护的技术使用者：南京大学
技术研发日：2022.06.24
技术公布日：2022/11/1
