本发明涉及信号处理领域，具体涉及一种基于fpga的序列多峰值搜索排序装置。
背景技术：
序列排序是经典的算法问题，已经有冒泡排序、插入排序、快速排序等大量的排序算法。对序列进行排序是信号处理中常见处理，往往无需得到序列的全部顺序的信息，仅需要部分峰值及其排序信息即可。例如在目标搜索等应用中，往往关注排序的头部目标信息，或由于噪声的影响，部分能量较低的序列信息被干扰，因此只需分析排序的头部信息。如果直接套用已有全序列排序算法，需要存储大量的序列值，会浪费大量的时间和资源。
fpga具备并行信号处理的能力，其计算资源，寄存器资源等均可通过编程直接调用，在信号处理领域应用广泛。
技术实现要素：
本发明需解决技术问题是提供一种占用存储空间少，排序时间短的序列多峰值搜索排序装置。
为解决上述技术问题，本发明提供了一种基于fpga的序列多峰值搜索排序装置，采取技术方案如下：
所述装置包括峰值寄存器、标识常量寄存器、比较寄存器和处理单元；
所述峰值寄存器的数量为n，与需要搜索并排序的峰值数量相同，峰值寄存器实时存储当前已排序序列的前n个峰值，n个峰值寄存器按大小顺序排列；
所述标识常量寄存器用于存储n个峰值寄存器对应的n个峰值寄存器标识常量，标识常量的位宽为n，对于第n个峰值寄存器，其标识常量的常量值为(2^(n-n 1))-1；
所述比较寄存器数量为1；比较寄存器位宽为nbit，位宽与峰值寄存器的个数相同，每1bit对应一个峰值寄存器；比较寄存器最高位对应n个峰值寄存器中的存储最大值的峰值寄存器，比较寄存器最低位对应n个峰值寄存器中的存储最小值的峰值寄存器，其他顺序对应；
所述处理单元使用峰值寄存器、标识常量寄存器、比较寄存器对输入序列进行多峰值搜索排序。序列依次流水进行序列值输入，设在t时刻输入序列值i1，并行比较i1与n个峰值寄存器中的值，根据比值大小，t 1时刻将所述比较寄存器中nbit的值更新为一个对应值j1；将所述标识常量寄存器中的标识常量并行与j1进行比较，在t 2时刻完成n个峰值寄存器峰值筛选与排序更新，直至序列搜索完毕，n个峰值寄存器中存储的值即为n个峰值。
进一步的，所述比较寄存器中nbit的值j1获取方法如下：
对于每一个峰值寄存器，如果i1小于等于某个峰值寄存器中的值，则将比较寄存器中此峰值寄存器对应的bit的值置为0，如果i1大于某个峰值寄存器中的值，将比较寄存器中此峰值寄存器对应的bit的值置为1。
进一步的，所述在t 2时刻完成n个峰值寄存器峰值筛选与排序更新，具体如下：
t 1时刻比较寄存器的值更新为j1后，将标识常量寄存器中对应的各峰值寄存器的标识常量并行与j1比较，如果第n个峰值寄存器的标识常量大于j1，则t 2时刻第n个峰值寄存器保持t 1时刻值；如果第n个峰值寄存器的标识常量等于j1，则t 2时刻第n个峰值寄存器的值更新为i1；如果第n个峰值寄存器的标识常量小于j1，则t 2时刻第n个峰值寄存器的值更新为t 1时刻峰值寄存器n-1的值。
本发明相比于现有技术其有益效果如下：
本发明提出一种基于fpga的序列多峰值搜索排序装置，充分发挥了fpga的并行性和灵活性优势，可快速、高效、稳定搜索出序列的前n个峰值，并按大小进行排序。本发明的时间复杂度为o(n)，仅需要被搜索序列遍历一遍，有效提升了序列多峰值排序的速度，从而快速搜索到目标值。本发明空间复杂度为o(1)，存储空间与序列的长度无关，仅需要少量寄存器资源即可，无需额外的片内ram存储资源，从而节约了片内ram存储资源，提高了排序效率。传统排序算法中常见待排序序列的数据分布会使排序时间不同，不利于计算时间的估算，本发明计算时间固定，便于后续信号处理规划。相比于传统排序算法，本发明兼具排序时间短、占用存储空间少，排序时间稳定的优点，具有较强的实用性。搜索排序的序列可以为定点值，也可为浮点值，具有较强的通用性。
附图说明
图1为本发明序列多峰值搜索排序装置流水处理示意图。
具体实施方式
下面结合附图对本发明的技术方案进一步进行阐述。
一种基于fpga的序列多峰值搜索排序装置，包括峰值寄存器、标识常量寄存器、比较寄存器和处理单元。
所述峰值寄存器的数量为n，与需要搜索并排序的峰值数量相同。峰值寄存器实时存储当前已排序序列的前n个峰值，待序列搜索完毕，n个峰值寄存器中存储的值即为前n个峰值。n个峰值寄存器，每个峰值寄存器排序为n，n＝1，2，3…n,排序为n的寄存器称为第n个寄存器，n个峰值寄存器按大小顺序排列，第1个峰值寄存器中存储n个峰值寄存器中存储数据的最大值，第n个峰值寄存器中存储n个峰值寄存器中存储数据的最小值。n需要小于或等于需要搜索的序列的长度。
所述峰值寄存器的位宽为m，m的值根据待排序序列的数据位宽确定；确认序列是有符号数还是无符号数，以确定m位宽所能表示的最小值；初始化n个峰值寄存器的值为m位宽所能表示的最小值。
所述标识常量寄存器用于存储n个峰值寄存器对应的n个峰值寄存器标识常量，标识常量的位宽为n，对于第n个峰值寄存器，其标识常量的常量值为(2^(n-n 1))-1，标识常量寄存器中的值为定值。
所述比较寄存器数量为1；比较寄存器位宽为nbit，位宽与峰值寄存器的个数相同，每1bit对应一个峰值寄存器；比较寄存器最高位对应n个峰值寄存器中的存储最大值的峰值寄存器，比较寄存器最低位对应n个峰值寄存器中的存储最小值的峰值寄存器，其他顺序对应。
比较寄存器的值初始化为无符号数最大值，即nbit宽数据，各bit数据均为1。
所述处理单元使用峰值寄存器、标识常量寄存器、比较寄存器对输入序列进行多峰值搜索排序。
待排序的序列值输入，设其值依次为i1，12，i3…,对待排序的序列值进行流水处理，如图1所示。
设t时刻输入i1，并行比较i1与n个峰值寄存器中的值后，比较寄存器中nbit的值在t 1时刻更新。t 1时刻比较寄存器作为一个整体得到一个对应值j1。
具体的，对于每一个峰值寄存器，如果i1小于等于某个峰值寄存器中的值，则将比较寄存器中此峰值寄存器对应的bit的值置为0，如果i1大于某个峰值寄存器中的值，将比较寄存器中此峰值寄存器对应的bit的值置为1。
以n＝4为例，设此t时刻峰值寄存器的值为99，88，77，66，i1为79，则t 1时刻比较寄存器的值为0b0011，具体可参考表1。由表1可知此时j1的值为0b0011。
表1t 1时刻比较寄存器计算示意表
将标识常量寄存器中对应的各峰值寄存器的标识常量并行与j1进行比较，在t 2时刻完成n个峰值寄存器峰值筛选与排序更新。
具体的，t 1时刻比较寄存器的值更新为j1后，将标识常量寄存器中对应的各峰值寄存器的标识常量并行与j1比较，如果第n个峰值寄存器的标识常量大于j1，则t 2时刻第n个峰值寄存器保持t 1时刻值；如果第n个峰值寄存器的标识常量等于j1，则t 2时刻第n个峰值寄存器的值更新为i1；如果第n个峰值寄存器的标识常量小于j1，则t 2时刻第n个峰值寄存器的值更新为t 1时刻峰值寄存器n-1的值。
如上述例子，t 1时刻峰值寄存器值为99，88，77，66，i1为79，比较寄存器j1的值为0b0011，第1个、第2个峰值寄存器的标识常量大于0b0011，则t 2时刻第1个、第2个峰值寄存器保持t 1时刻的值；第3个峰值寄存器的标识常量等于0b0011，则t 2时刻第3个峰值寄存器的值更新为79；第4个峰值寄存器的标识常量小于0b0011，则t 2时刻第4个峰值寄存器的值更新为t 1时刻峰值第3个寄存器的值77，如表2所示。
表2t 2时刻峰值寄存器变化示意表
序列依次流水进行序列值输入，并行比较，对当前输入进行峰值筛选与排序处理。
当序列搜索完毕，n个峰值寄存器中存储的值即为n个峰值，并且已经按照n＝1到n＝n的顺序由大到小进行了排序。
本发明序列多峰值搜索排序装置可以处理定点值也可以处理浮点值。如果为定点值，t 1时刻与t时刻的时间差1个时刻为1个信号处理时钟周期。如果为浮点值，t 1时刻与t时刻的时间差1个时刻为1个浮点运算操作需要的处理时钟周期个数，具体时钟周期个数需要根据fpga的运算能力确定。
上述具体实施方式仅用于解释和说明本发明的技术方案，但并不能构成对权利要求的保护范围的限定。本领域技术人员应当清楚，在本发明的技术方案的基础上做任何简单的变形或替换而得到的新的技术方案，均将落入本发明的保护范围之内。
1.一种基于fpga的序列多峰值搜索排序装置，其特征在于，包括峰值寄存器、标识常量寄存器、比较寄存器和处理单元；
所述峰值寄存器的数量为n，与需要搜索并排序的峰值数量相同，峰值寄存器实时存储当前已排序序列的前n个峰值，n个峰值寄存器按大小顺序排列；
所述标识常量寄存器用于存储n个峰值寄存器对应的n个峰值寄存器标识常量，标识常量的位宽为n，对于第n个峰值寄存器，其标识常量的常量值为(2^(n-n 1))-1；
所述比较寄存器数量为1；比较寄存器位宽为nbit，位宽与峰值寄存器的个数相同，每1bit对应一个峰值寄存器；比较寄存器最高位对应n个峰值寄存器中的存储最大值的峰值寄存器，比较寄存器最低位对应n个峰值寄存器中的存储最小值的峰值寄存器，其他顺序对应；
所述处理单元使用峰值寄存器、标识常量寄存器、比较寄存器对输入序列进行多峰值搜索排序；
序列依次流水进行序列值输入，设在t时刻输入序列值i1，并行比较i1与n个峰值寄存器中的值，根据比值大小，t 1时刻将所述比较寄存器中nbit的值更新为一个对应值j1；将所述标识常量寄存器中对应的各峰值寄存器的标识常量并行与j1进行比较，在t 2时刻完成n个峰值寄存器峰值筛选与排序更新，直至序列搜索完毕，n个峰值寄存器中存储的值即为n个峰值。
2.根据权利要求1所述的一种基于fpga的序列多峰值搜索排序装置，其特征在于，所述比较寄存器中nbit的值j1获取方法如下：
对于每一个峰值寄存器，如果i1小于等于某个峰值寄存器中的值，则将比较寄存器中此峰值寄存器对应的bit的值置为0，如果i1大于某个峰值寄存器中的值，将比较寄存器中此峰值寄存器对应的bit的值置为1。
3.根据权利要求2所述的一种基于fpga的序列多峰值搜索排序装置，其特征在于，所述在t 2时刻完成n个峰值寄存器峰值筛选与排序更新，具体如下：
t 1时刻比较寄存器的值更新为j1后，将标识常量寄存器中对应的各峰值寄存器的标识常量并行与j1比较，如果第n个峰值寄存器的标识常量大于j1，则t 2时刻第n个峰值寄存器保持t 1时刻值；如果第n个峰值寄存器的标识常量等于j1，则t 2时刻第n个峰值寄存器的值更新为i1；如果第n个峰值寄存器的标识常量小于j1，则t 2时刻第n个峰值寄存器的值更新为t 1时刻峰值寄存器n-1的值。
4.根据权利要求1、2或3所述的一种基于fpga的序列多峰值搜索排序装置，其特征在于，所述序列值为定点值或浮点值。
技术总结