芯耀
与非AI
117
一、模块是做什么的？
在图像处理、雷达信号处理等场景中，经常需要对一批数据做排序或求中值/最大最小值。传统冒泡、快排算法需要多周期迭代，实时性差。 sort_32_u8 模块，是一种基于计数排序思想的硬件实现，也常被称为“秩排序”，采用**全并行“秩排序”（Rank Sort）**架构，仅用 3 级流水线、3 个时钟周期就能完成 32 路 8bit 无符号数据的排序输出。
该架构的资源随 N² 增长：32 路数据需要 1024 个比较器和 32 个 5bit 加法树，N 扩大时资源消耗急剧上升，适合 N≤64 的中小规模排序；此外所有比较在同一拍完成，时序收敛压力较大，建议 DATA_WIDTH 较大时插入寄存器切割关键路径。
二、核心原理
秩排序的思想：每个数不需要和其他数交换位置，只需要数清有多少个数比自己小，这个数量就是它排序后的目标位置。
以数据 A 和数据 B 比较为例，A 的排名计数规则是：
-
- A > B：A 得 1 分（B 排在 A 前面）；A < B：A 得 0 分；A == B：
下标靠前的得 1 分，下标靠后的得 0 分
- ，这样保证相等元素也能占据不同位置，避免冲突。
对应代码中 pipe1 的逻辑：
if(din[j] < din[i]) pipe1_flag[j][i] <= 0;
else if(din[j] == din[i]) begin
if(j >= i) pipe1_flag[j][i] <= 0;
else pipe1_flag[j][i] <= 1;
end
else pipe1_flag[j][i] <= 1;
三、三级流水线架构
1、比较阶段
Pipe1（并行比较）：32×32 = 1024 个比较器同时工作，两两比较生成标志矩阵 pipe1_flag[j][i]，同时锁存数据 pipe1_din；
- 模块内部通过两重循环构建了一个 32×32 的比较器阵列。对于每一个输入数据 din[j]，它与其他所有数据 din[i] 进行比较。pipe1_flag[j][i] 存储比较结果：如果 din[j] > din[i]，则置1；如果相等，根据索引 j 和 i 的关系决定（这里实现的是逆序稳定排序，即如果数值相等，索引靠后的元素会被排在前面）；如果 din[j] < din[i]，则置0。本质上，这个 flag 的累加值代表了 din[j] 在所有数据中“大于”其他元素的个数。
2、求和阶段
Pipe2（排名汇总）：对每个数据按行累加 32 个标志位，得到排名值 pipe2_flag_sum[j]（范围 0~31），并通过 pipe1_valid_sum 全与逻辑确保数据整体有效；
- pipe2_flag_sum[j] 对第 j 行的所有比较结果 pipe1_flag[j][0...31] 进行求和。这个和就是 din[j] 在最终有序数组中的目标索引（Rank）。例如，和为0表示它是最小的，和为31表示它是最大的。经过这一级后，知道了每个数据应该被放到哪个位置
3、重排输出阶段
Pipe3（按名次分发）：把每个数据写入以自己的排名为索引的位置：
- 根据计算出的索引 pipe2_flag_sum[k]，将 pipe2_din[k] 放入 pipe3_din 数组的对应位置。输出 dout 直接连接 pipe3_din。
pipe3_din[pipe2_flag_sum[j]] <= pipe2_din[j];
4、关键特性
排名 0 的数落到 pipe3_din[0]，排名 31 的落到 pipe3_din[31]，输出天然有序（升序）。
- 排序顺序：升序（小 -> 大）。dout_0 是最小值，dout_31 是最大值。流水线结构：模块为典型的 3 级流水线结构（Pipe1: 比较与锁存, Pipe2: 求和与锁存, Pipe3: 重排与锁存）。延迟：从 vld_in 有效到 vld_out 有效，固定延迟为 3 个时钟周期。数据处理：全并行处理，32个数据同时进入，排序后同时输出。
四、典型应用场景
中值滤波：图像 3×3、5×5 滤波的加速实现，取排序后中间值即可去除椒盐噪声；
运动目标检测：背景建模中取某区域的中值/分位数作为背景值；
Top-K 挑选：雷达恒虚警（CFAR）检测中筛选最强回波；
流水线化数据处理：由于是纯组合+寄存器结构，数据可以背靠背连续输入，吞吐率达每周期一批数据（本例 valid 控制下为 3 周期延迟的高吞吐流水线）。
五、仿真验证
Testbench 的设计思路：
随机激励：生成 10 组 0~255 随机数据，同时驱动 DUT 输入端口和 tb_i_data_inarray 数组；
黄金参考模型：编写 bubble_sort 任务对同一组数据做软件排序，生成期望结果 ref_sorted；
自动比对：将 32 个输出端口拼成 tb_o_data_outarray 数组，等待 o_data_out_valid 拉高后逐项比对，统计 error_count；
边界用例：额外增加全 0 输入测试，验证相等元素处理逻辑不冲突、无竞争。
if (tb_o_data_outarray[i] !== ref_sorted[i]) begin
$display("Mismatch at index %0d ...", i);
error_count = error_count + 1;
end
六、如何获取？
关注公众号：我是小灰灰的FPGA，关注我，带你从入门到精通数字逻辑设计。
后台回复（建议复制粘贴）：sort_32_u8
