在进行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
数据 | 14 | 45 | 32 | 9 | 43 |
---|---|---|---|---|---|
14 | x | 0 | 0 | 1 | 0 |
45 | 1 | x | 1 | 1 | 1 |
32 | 1 | 0 | x | 1 | 0 |
9 | 0 | 0 | 0 | x | 0 |
43 | 1 | 0 | 1 | 1 | x |
Sum | 3 | 0 | 2 | 4 | 1 |
由此可见,经过一个时钟的比较之后,就得到了各个数据与其他数据的次序信息。
一个值得注意的问题是,如果中间有两个数或者多个数相等如何处理?
做以下规定:
Ø 当前数目大于本数据之前输入数据时,结果记为1,小于或等于记为0。
Ø 当前数目大于等于本数据之后输入数据时,结果记为1,小于时记为0。
如下面待排序序列:
91,23,91,5,8
数据 | 91 | 23 | 91 | 5 | 8 |
---|---|---|---|---|---|
91 | x | 1 | 1 | 1 | 1 |
23 | 0 | x | 0 | 1 | 1 |
91 | 0 | 1 | x | 1 | 1 |
5 | 0 | 0 | 0 | x | 0 |
8 | 0 | 0 | 0 | 1 | x |
Sum | 0 | 2 | 1 | 4 | 3 |
可见,后面输入的数据由于“输入优先级”较小,因此排序结果被“降了”一档,也刚好达到目的。
需要注意的是,重新排序后的资源消耗问题,这个时候行列出现了不一致性。因为大于和大于等于是不同的逻辑。以3个数据d1,d2,d3的排序为例,要完成的比较如下:
d1≥d2
d1≥d3
d2>d1
D2≥d3
d3>d1
d3>d2
因此,除非设计单独的等号判别电路,每次比较都是不重叠的,这样下来,需要的比较器数目为n(n-1)个,.