并行排序电路及并行排序方法

摘要

本发明公开了一种并行排序电路和并行排序方法，主要解决现有技术的排序速度慢、不能满足实时性要求的问题。其包括比较单元、控制单元和输出单元，该控制单元包括插入地址子单元和删除地址子单元。比较单元对数据进行比较，插入地址子单元利用比较单元输出的比较结果，产生插入地址；删除地址子单元利用插入地址子单元输出的插入地址，产生删除地址；输出单元根据插入地址和删除地址，在一个时钟周期内插入新数据，同时删除最早的数据，输出排序结果。该发明基于硬件实现，并行性好，速度快，减少了排序需要的时钟周期数，满足实时性要求，可以应用于雷达探测等对数据处理速度要求较高的领域。

说明书

技术领域

本发明涉及微电子数字电路设计领域，具体涉及一种数据排序的硬件电路及其实 现方法，可用于数据处理中对数据进行排序。

背景技术

排序是数据处理中最基本也是最重要的操作之一，鉴于其重要性，近年来已经陆 续提出了许多排序算法来解决实际问题。目前排序算法大致可以分为软件实现方式和 硬件实现方式。

软件排序算法有很多，如冒泡排序、选择排序、插入排序、快速排序、合并排序、 计数排序等。这些软件实现方式都有一个共同的缺点，那就是速度比较慢而且需要利 用处理器资源。在图像处理、多媒体数据处理以及雷达探测等需要高速数据处理的场 合，这些排序算法的软件实现方式很难达到要求的处理速度。而且在没有处理器资源 的场合，也无法采用软件实现方式。

而硬件实现具有并行性的特点，硬件排序的速度更快。目前，硬件排序的结构可 以分为两种：排序网络和线性排序阵列。排序网络的缺点是当需要排序的数据较多时， 会导致排序网络的面积很大，而且如果要进行排序的数据块中一个数据发生变化，都 需要重新进行排序。而线性排序在处理连续串行输入的数据时很有用，但是目前存在 的问题是速度慢，需要较多的时钟周期才能得到排序结果，实时性不好。

发明内容

本发明的目的在于克服上述已有技术的不足，提出一种并行排序电路及并行排序 方法，以提高电路的排序速度，减少排序所需要的时钟周期数，满足实时性要求。

为实现上述目的，本发明的并行排序电路，包括比较单元、控制单元以及输出单 元，比较单元将新输入的待排序数据和已排序数据以及设定的数据的最大值进行比 较，得到比较结果{c₁,c₂,…,c_i，…,c_N,c_N+1}，其中N为排序数据的个数，c_i为待排序数 据与N个已排序数据的比较结果，i为自然数，取值范围为[1,N]，c_N+1为待排序数据 与设定的数据的最大值的比较结果，该比较结果输出给控制单元，控制单元利用比较 单元的比较结果产生插入地址ins和删除地址del并输出给输出单元，输出单元根据 插入地址ins和删除地址del的值，将输入的待排序数据插入到已排序的数据中，并 删除最早输入的待排序数据，得到排序结果，其特征在于：

所述的控制单元，包括：

插入地址子单元，它包含第一多路选择器A和第二多路选择器B；该第一多路选 择器A的输入信号为{c₁,c₂,…,c_i，…,c_N,c_N+1}，控制信号为删除地址子单元的输出信号 删除地址del，输出信号为标志信号flag，若del=N-i，则flag={c₁,c₂,…,c_i-1, c_i+1,…,c_N,c_N+1}，i的取值范围为[1,N]；该第二多路选择器B的输入信号为所有已排序 数据的地址值N-j，j的取值范围为[1,N]，输出信号为插入地址ins，控制信号为第一 多路选择器A的输出信号flag，其位宽为N，若flag所有位中1的个数为N-j+1,则插 入地址ins=N-j；

删除地址子单元，它包含N个寄存器和N-1个多路选择器，该N个寄存器和N-1 个多路选择器交替排列，第一个寄存器的输入信号为插入地址子单元的输出信号插入 地址ins，其余N-1个寄存器的输入信号分别为它前面一个多路选择器的输出信号， 第i个寄存器的输出信号为第i个中间删除地址h_i，i的取值范围为[1,N-1]， 第N个寄存器的输出信号为该删除地址子单元的输出信号删除地址del；第i个多路 选择器的输入信号为它前面一个寄存器的输出信号h_i，h_i+1以及h_i-1，控制信号为 插入地址ins，删除地址del以及它前面一个寄存器的输出信号h_i，输出信号为中间插 入地址g_i，i的取值范围为[1,N-1]，该中间插入地址g_i按如下规则选取：

若ins>h_i，del>h_i，则g_i=h_i；

若ins<h_i，del<h_i，则g_i=h_i；

若ins<=h_i，del>h_i，则g_i=h_i+1；

若ins>=h_i，del<h_i，则g_i=h_i-1。

为实现上述目的，本发明的并行排序方法，包括如下步骤：

1）初始化步骤：

初始化删除地址del=0；初始化第i个中间删除地址h_i=N-i，i的取值范围为 [1,N-1]；初始化已排序数据d_j=0，j的取值范围为[1,N]；

2）数据大小比较步骤：

将每个时钟周期输入的待排序数据与已排序数据以及设定的数据的最大值进行 比较，若待排序数据小于或者等于已排序数据，则c_i=1，否则，c_i=0；若待排序数据 小于或者等于设定的数据的最大值，则c_N+1=1，否则，c_N+1=0，得到比较结果 {c₁,c₂,…,c_i，…,c_N,c_N+1}，N为排序数据的个数，c_i为待排序数据与N个已排序数据的 比较结果，c_N+1为待排序数据与设定的数据的最大值的比较结果，i的取值范围为 [1,N]；

3）插入地址产生步骤

3a）利用删除地址del和比较结果{c₁,c₂,…,c_i，…,c_N,c_N+1}，产生标志信号flag，若 del=N-i，则flag={c₁,c₂,…,c_i-1,c_i+1，…,c_N,c_N+1}，i的取值范围为[1,N]；

3b）利用标志信号flag作为控制信号进行编码，若flag所有位中1的个数为k+1, 则插入地址ins=k，k的取值范围为[0,N-1]；

4）删除地址产生步骤:

同时进行以下三个操作:

寄存插入地址ins，得到第一个中间删除地址h₁；

将第i个中间删除地址h_i分别与插入地址ins和删除地址del比较，i的取值范围 为[1,N-1]，利用比较的结果作为控制信号产生第j个中间插入地址g_j；寄存第j个中 间插入地址ir_j，得到第j+1个中间删除地址h_j+1，j的取值范围为[1,N-2]，j=i；

将第N-1个中间删除地址h_N-1分别与插入地址ins和删除地址del比较，利用比 较的结果产生第N-1个中间插入地址g_N-1；寄存第N-1个中间插入地址g_N-1，得到更 新的删除地址的值deln；

5）排序结果输出步骤

设插入地址ins=N-j，更新后的删除地址deln=N-n，i、j和n表示已排序数据的序 号，其取值范围均为[1,N]；根据插入地址ins和更新后的删除地址deln的值，确定已 排序数据d_i的移位方式，将待排序数据din插入到相应的位置，得到如下排序结果：

当i＝j时，将待排序数据插入到地址值为N-j的地址处，即d_i=din；

当i≠j时，需要根据j和n的大小确定d_i的结果，具体判断方法如下：

若j=n，则ins=del，使地址值不等于N-j的地址处的数据都保持不变，即i∈[1，j-1] 或者i∈[j+1,N]时，得到d_i=d_i；

若j>n，则ins<del，保持地址值为N-1的地址到地址值为N-n+1的地址处的数据 不变，同时保持地址值为N-j-1的地址到地址为值0的地址处的数据也不变，即i∈[1,n-1] 或者i∈[j+1,N]时，得到d_i=d_i；

若j＞n，则ins<del，将地址值为N-n-1的地址到地址值为N-j的地址处的数据依 次左移，得到地址值为N-n的地址到地址值为N-j+1的地址处的结果，即i∈[n，j-1]时， 得到d_i=d_i+1；

若j<n，则ins>del，保持地址值为N-1的地址到地址值为N-j+1的地址处的数据 不变，同时保持地址值为N-n-1的地址到地址值为0的地址处的数据也不变，即i∈[1,j-1] 或者i∈[n+1,N]时，得到d_i=d_i；

若j<n，则ins>del，将地址值为N-j的地址到地址值为N-n+1的地址处的数据依 次右移，得到地址值为N-j-1的地址到地址值为N-n的地址处的结果，即i∈[j+1,n]时， 得到d_i=d_i-1。

本发明现有技术相比，具有如下优点：

1．本发明由于采用现场可编程门阵列FPGA实现整个排序电路，利用FPGA并 行性好的特点，克服了现有技术基于软件的实现方式速度慢的问题，使得本发明速度 快，可以应用于图像处理、多媒体数据处理和雷达探测等对数据处理速度要求较高的 领域；

2．本发明由于采用产生插入地址和删除地址并比较插入地址和删除地址的大小 的方法，对每个时钟周期输入的待排序数据进行排序，可以在一个时钟周期内将待排 序数据插入同时删除最早的数据，减少了排序所需要的时钟周期数，能满足实时性要 求。

附图说明

图1为本发明的电路方框图；

图2为本发明电路中的比较单元方框图；

图3为本发明电路中的控制单元方框图；

图4为本发明电路中的输出单元方框图；

图5为本发明的处理方法流程图。

具体实施方式：

下面结合附图对本发明做进一步的描述：

参照图1，本发明的并行排序电路，包括比较单元、控制单元和输出单元。其中： 比较单元将新输入的待排序数据和已排序数据以及设定的数据的最大值进行比较，得 到比较结果，并将结果输出到控制单元；控制单元利用比较单元的比较结果产生插入 地址ins和删除地址del，并输出给输出单元；输出单元根据插入地址ins和删除地址 del的值，将输入的待排序数据插入到已排序的数据中，并删除最早输入的待排序数 据，得到排序结果。

参照图2，本发明的比较单元包括N+1个比较器，N为排序数据的个数，每个比 较器都有两个输入端口和一个输出端口，其中：

第i个比较器，其输入信号分别为输入的待排序数据din和输出单元输出的已排 序数据d_i，其输出信号为比较结果c_i，i的取值范围为[1,N]，该第i个比较器将待排 序数据din与已排序数据d_i进行比较，若待排序数据din小于或者等于已排序数据d_i， 则c_i为1，否则，c_i为0；

第N+1个比较器，其输入信号分别为输入的待排序数据din和设定的数据的最大 值max，其输出信号为比较结果c_N+1，该第N+1个比较器将待排序数据din与设定的 数据的最大值max进行比较，若待排序数据din小于或者等于max，则c_N+1=1，否则， c_N+1=0，其中，max的值确定了参与比较的数据的范围，一般情况下，c_N+1=1。

参照图3，本发明的控制单元，包括插入地址子单元、删除地址子单元。

所述插入地址子单元，包括第一多路选择器A和第二多路选择器B，其中:

第一多路选择器A，其输入信号为比较单元输出的比较结果 {c₁,c₂,…,c_i，…,c_N,c_N+1}，式中N为排序数据的个数，i的取值范围为[1,N]，其控制信号 为删除地址子单元的输出信号删除地址del，其输出信号为标志信号flag，该第一多 路选择器A根据控制信号del，对输入的比较结果进行选择，得到标志信号flag，若 del=N-i，则flag={c₁,c₂,…,c_i-1,c_i+1,…,c_N,c_N+1}，{c₁,c₂,…,c_i,…,c_N,c_N+1}为输入的待排序 数据与已排序数据以及设定的数据的最大值的比较结果，其中，c_i为待排序数据din 与已排序数据的比较结果，i的取值范围为[1,N]，若待排序数据din小于或者等于已 排序数据d_i，则c_i为1，否则，c_i为0，c_N+1为待排序数据din与设定的数据的最大值 max的比较结果，若待排序数据din小于或者等于max，则c_N+1=1，否则，c_N+1=0；

第二多路选择器B，其输入信号为所有已排序数据的地址值k，k的取值范围为 [0,N-1]，其控制信号为第一多路选择器A的输出信号flag，位宽为N，其输出信号为 插入地址ins，该第二多路选择器B根据控制信号flag，对输入的地址值进行选择， 得到插入地址，若flag所有位中1的个数为N-j+1,则插入地址ins=N-j。

所述删除地址子单元，包括N个寄存器和N-1个多路选择器，该N个寄存器和 N-1个多路选择器交替排列，其中：

第一个寄存器，其输入信号为插入地址ins，其输出信号为第一个中间删除地址 h₁；

第i个寄存器，其输入信号为第i-1个多路选择器的输出信号g_i-1，其输出信号为 第i个中间删除地址h_i，，i的取值范围为[2,N-1]；

第N个寄存器，其输入信号为第N-1个多路选择器的输出信号g_N-1，其输出信号 为删除地址del；

第j个多路选择器，其输入信号为第j个寄存器的输出信号h_j、h_j+1和h_j-1共三 个信号，其控制信号为插入地址ins、删除地址del和第j个寄存器的输出信号h_j共三 个信号，其输出信号为第j个中间插入地址g_j，j取值范围为[1,N-1]，该第j个多路 选择其根据控制信号，对输入信号进行选择，得到如下输出结果：

若ins>h_j，del>h_j，则g_j=h_j；

若ins<h_j，del<h_j，则g_j=h_j；

若ins<=h_j，del>h_j，则g_j=h_j+1；

若ins>=h_j，del<h_j，则g_j=h_j-1。

参照图4，本发明的输出单元，包含N个多路选择器和N个寄存器，每个多路选 择器都与一个寄存器相连，其中：

第j个寄存器，其输入信号为第j个多路选择器的输出信号m_j，其输出信号为输 出单元的输出结果d_j，j的取值范围为[1,N]；

第一个多路选择器，其输入信号为待排序数据din，第一个寄存器的输出信号d₁和第二个寄存器的输出信号d₂共三个信号，其控制信号为删除地址del和插入地址 ins，其输出信号记为m₁，该第一个多路选择器根据控制信号，对输入信号进行选择， 得到如下输出结果：

若ins=N-1，则m₁=din；

若ins<N-1，del=N-1，则m₁=d₂；

若ins<N-1，del<N-1，则m₁=d₂；

第i个多路选择器，其输入信号为待排序数据din，第i-1个寄存器的输出信号d_i-1， 第i个寄存器的输出信号d_i和第i+1个寄存器的输出信号d_i+1共四个信号，其控制信 号为删除地址del和插入地址ins，其输出信号记为m_i，i的取值范围为[2,N-1]，该第 i个多路选择器根据控制信号，对输入信号进行选择，得到如下输出结果：

若ins=N-i，则m_i=din；

若ins<N-i，del<N-i，则m_i=d_i；

若ins<N-i，del>=N-i，则m_i=d_i+1；

若ins>N-i，del>N-i，则m_i=d_i；

若ins>N-i，del<=N-i，则m_i=d_i-1；

第N个多路选择器，其输入信号为待排序数据din，第N-1个寄存器的输出信号 d_N-1和第N个寄存器的输出信号d_N共三个信号，其控制信号为删除地址del和插入地 址ins，其输出信号记为m_N，该第N个多路选择器根据控制信号，对输入信号进行选 择，得到如下输出结果：

若ins=0，则m_N=din；

若ins>0，del=0，则m_N=d_N-1；

若ins>0，del>0，则m_N=d_N；

参照图5，本发明的并行排序方法，包括如下步骤：

步骤1，初始化：

初始化删除地址del=0；初始化第i个中间删除地址h_i=i-1，i的取值范围为[1,N-1]； 初始化已排序数据d_j=0，j的取值范围为[1,N]。

步骤2，比较数据大小：

将每个时钟周期输入的待排序数据din与已排序数据d_i以及设定的数据的最大值 max进行比较，N为排序数据的个数，c_i为待排序数据与N个已排序数据的比较结 果，c_N+1为待排序数据与设定的数据的最大值max的比较结果，i的取值范围为[1,N]， 若待排序数据小于或者等于已排序数据，则c_i=1，否则，c_i=0；若待排序数据小于或 者等于设定的数据的最大值，则c_N+1=1，否则，c_N+1=0，得到比较结果 {c₁,c₂,…,c_i,…,c_N,c_N+1}。

步骤3，产生插入地址：

3a）根据删除地址del对输入的比较结果{c₁,c₂,…,c_i，…,c_N,c_N+1}进行选择，产生标 志信号flag，若del=N-i，则flag={c₁,c₂,…,c_i-1,c_i+1,…,c_N,c_N+1}，i的取值范围为[1,N]， 由于步骤2中将待排序数据与N个已排序数据进行大小比较，因此，需要根据删除地 址的值，删除其中一个比较结果，才能确定输入的待排序数据要插入的位置；

3b）步骤3a）产生的flag信号表征了待排序数据要插入的位置，为了更明确的 表示地址值，利用标志信号flag作为控制信号进行编码，产生插入地址ins，若flag 所有位中1的个数为k+1,则插入地址ins=k，k的取值范围为[0,N-1]；

步骤4，产生删除地址：

由于本发明的并行排序方法，每个时钟周期删除最早输入的数据，同时将新输入 的待排序数据插入到相应的位置，因此，产生的插入地址寄存N次就变成了删除地址， 并且，由于待排序数据插入后会导致已排序数据发生移位，因此，需要根据插入地址 和删除地址的值，得到更新的删除地址的值。该更新的删除地址值通过同时进行以下 三个操作取得：

操作1，寄存插入地址ins，得到第一个中间删除地址dr₁；

操作2，将第i个中间删除地址h_i分别与插入地址ins和删除地址del比较，i的 取值范围为[1,N-2]，利用比较的结果作为控制信号产生第i个中间插入地址g_i，并寄 存第i个中间插入地址ir_i，得到第i+1个中间删除地址h_i+1，i的取值范围为[1,N-2]； g_i的产生规则是：

若ins>h_i，del>h_i，则g_i=h_i；

若ins<h_i，del<h_i，则g_i=h_i；

若ins<=h_i，del>h_i，则g_i=h_i+1；

若ins>=h_i，del<h_i，则g_i=h_i-1；

操作3，将第N-1个中间删除地址h_N-1分别与插入地址ins和删除地址del比较， 利用比较的结果产生第N-1个中间插入地址g_N-1，并寄存第N-1个中间插入地址g_N-1， 得到更新的删除地址的值deln，g_N-1的产生规则如下：

若ins>h_N-1，del>h_N-1，则g_N-1=h_N-1；

若ins<h_N-1，del<h_N-1，则g_N-1=h_N-1；

若ins<=h_N-1，del>h_N-1，则g_N-1=h_N-1+1；

若ins>=h_N-1，del<h_N-1，则g_N-1=h_N-1-1。

步骤5，输出最终的排序结果。

设插入地址ins=N-j，更新后的删除地址deln=N-n，i、j和n表示已排序数据的序 号，其取值范围均为[1,N]；根据插入地址ins和更新后的删除地址deln的值，确定已 排序数据d_i的移位方式，将待排序数据din插入到相应的位置，得到如下排序结果：

当i＝j时，将待排序数据插入到地址值为N-j的地址处，即d_i=din；

当i≠j时，需要根据j和n的大小，确定已排序数据d_i的结果，具体结果如下：

若j=n，则ins=deln，使地址值不等于N-j的地址处的数据都保持不变，即i∈[1，j-1] 或者i∈[j+1,N]时，得到d_i=d_i；

若j>n，则ins<deln，保持地址值为N-1的地址到地址值为N-n+1的地址处的数 据不变，同时保持地址值为N-j-1的地址到地址为值0的地址处的数据也不变，即 i∈[1,n-1]或者i∈[j+1,N]时，得到d_i=d_i；

若j>n，则ins<deln，将地址值为N-n-1的地址到地址值为N-j的地址处的数据依 次左移，得到地址值为N-n的地址到地址值为N-j+1的地址处的结果，即i∈[n，j-1]时， 得到d_i=d_i+1；

若j<n，则ins>deln，保持地址值为N-1的地址到地址值为N-j+1的地址处的数 据不变，同时保持地址值为N-n-1的地址到地址值为0的地址处的数据也不变，即 i∈[1，j-1]或者i∈[n+1,N]时，得到d_i=d_i；

若j<n，则ins>deln，将地址值为N-j的地址到地址值为N-n+1的地址处的数据 依次右移，得到地址值为N-j-1的地址到地址值为N-n的地址处的结果，即i∈[j+1,n] 时，得到d_i=d_i-1。

以上仅是本发明的一个具体实例，不构成对本发明的任何限制，显然，在对本发 明的构思下，可以进行不同程度的变更，但这些均在本发明的保护之列。