当前位置：
  1. 首页
  2. 可编辑器件

FPGA排序-冒泡排序介绍

2023-07-17

排序算法是图像处理中经常使用一种算法，常见的排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序。

如下图>
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第1张
冒泡排序的排序过程如下>
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第2张
整个排序的过程就是两两比较，然后做交换。整个过程的时间复杂度n的平方，也就是说需要交换很多次，如果把这么多交换过程都在一个时钟周期内完成的话，组合逻辑会很长，这样直接影响最后的时序。如果每个时钟周期进行一次交换的话，pipeline是会很长的。
那么我们可以通过变通一下，整个排序过程只做比较，而不做交换。每一次比较的结果都记录下来，然后设置一个计分板，通过计分板就可以知道排序的结果了。
首先是比较的过程：判断输入的两个数哪个大，使用1bit变量来记录比较结果。
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第3张
然后是计分板的生成>
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第4张
最后是排序结果的输出>
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第5张
仿真代码如下>
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第6张
仿真波形>
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第7张
一共三级流水，占用的资源也不多，可以自己通过reduceBalancedTree来增加更多的流水。
FPGA排序-冒泡排序介绍 (https://ic.work/) 可编辑器件 第8张
照例提供SpinalHDL的源码，Verilog有需要的私聊>
 
 

文章推荐
Tags：

上一篇

下一篇

相关推荐