FPGA实现冒泡排序法（VHDL）

Diabloa

FPGA实现冒泡排序法（VHDL）

. a! V, g3 D, t" x; e, N4 C! S% P. G

       可能很多人会问，为什么用FPGA来实现冒泡排序？放CPU中用C语言只需短短几行代码即可实现的事情为啥用逻辑来实现，没办法我加入这个项目的时候系统方案已确定下来了。

       通过一个小采集板实现一个窄脉冲（10ns）信号的个数计算功能，控制单元只有一个FPGA（基于成本考虑没有加一个小CPU），与中位机CPU通信采用UART串口（波特率19200），为了减少串口的数据量，系统功能要求将采集到16个数据作为一组，去掉最大值和最小值然后求平均，最后通过串口将平均值输出至中位机CPU。在此不讨论系统方案，只和大家分享一下冒泡排序功能模块的实现。

       1. 冒泡排序模块功能概述：

（1）通过冒泡法实现数据的排序

（2）数据宽度16bit，数量不固定（后期系统方案可能会更改），因此数量作为一个变量参数，但最多不大于128个

（3）逻辑资源和系统时序相对还比较宽松，因此模块的资源和排序耗费时间都还算宽裕，适中即可。

       2.  设计方案确定

       冒泡法排序在学校学习C语言的时候，这个是可是必考的，包括普通变量/数组/指针等不同形式的冒泡排序，怀念一下学校时候的美好时光。简单回忆一下冒泡排序，每次将相邻两数进行比较，较大或较小的数调到前面，n个数需要进行n-1轮比较，第一轮进行n-1次两两比较，第n-1轮只需进行1次比较。这样，没经过一轮的比较，较大或较小的数都会上升一位，如同水底气泡逐步冒出水面一样，故称冒泡排序。

       开始考虑通过RAM来存储排序过程的数，但在排序数的数量不固定的时候，对RAM地址的处理略麻烦一些，而采用FIFO来实现，则可不考虑FIFO中数的数量，只要FIFO中存有数据则会一直进行排序比较。本方案采用三个128*16bit的FIFO来缓存排序数据，其中外部接口将数据写入FIFO1，开始排序之后，FIFO1的数据进行第一轮比较，比较后最大的数存入FIFO3待外部读取，其他数据存入FIFO2。第二轮读取FIFO2的数据进行比较，第三轮读取FIFO1的数据，以此循环，直到所有数据排序完成存入FIFO3。

6 }( F$ `7 |5 v- G

cszxp

:)