基于FPGA的非线性滤波器（二）

基于FPGA的非线性滤波器（二）

之并行全比较排序

在进行FPGA映射之前，必须首先确定排序算法。由于在FPGA的图像处理领域，中值滤波的处理窗口不会太大，因此，在选择排序方法时优先考虑时间开销比较小的算法，在本设计中采用并行全比较排序算法。

并行全比较排序法采用并行结构，其基本原理是在同一时刻完成所有数据与其他数据的比较结果。因此其时间复杂度最小，仅需一个时钟即可完成排序工作，很适合FPGA流水线处理。

假设现在要对n个数据d0，d1，d2，....，dn进行排序。那么进行并行排序的步骤如下：

（1）同时得到这n个数，即对这n个数目对齐。

（2）同时将这n个树分别与其他数做比较，并记录结果。不妨设定：若当前数大于其他数，则将结果记录为1；若当前数小于等于其他数，则将结果记录为0.

（3）计算每个数第（2）步的所以结果之和：由于一共是n个数目，因此，必然有n-1个比较结果。

（4）第（3）步结果的值即为排序结果。

举例子：14，45，32，9，43

由此可见，经过一个时钟的比较之后，就得到了各个数据与其他数据的次序信息。

一个值得注意的问题是，如果中间有两个数或者多个数相等如何处理？

做以下规定：

Ø 当前数目大于本数据之前输入数据时，结果记为1，小于或等于记为0。

Ø 当前数目大于等于本数据之后输入数据时，结果记为1，小于时记为0。

如下面待排序序列：

91，23，91，5，8

可见，后面输入的数据由于“输入优先级”较小，因此排序结果被“降了”一档，也刚好达到目的。

需要注意的是，重新排序后的资源消耗问题，这个时候行列出现了不一致性。因为大于和大于等于是不同的逻辑。以3个数据d1，d2，d3的排序为例，要完成的比较如下：

d1≥d2

d1≥d3

d2>d1

D2≥d3

d3>d1

d3>d2

因此，除非设计单独的等号判别电路，每次比较都是不重叠的，这样下来，需要的比较器数目为n(n-1)个，.