FPGA设计篇之冒泡排序 |
您所在的位置：网站首页 › 冒泡排序逻辑规律 › FPGA设计篇之冒泡排序 |
FPGA设计篇之冒泡排序
|
FPGA设计篇之冒泡排序
一、写在前面二、冒泡排序原理三、冒泡排序RTL实现四、TestBench五、仿真结果六、写在后面
一、写在前面
在前面，我们分别学习了并行全排序算法和双调排序算法的原理及其RTL代码的编写，在本文中我们将继续学习经典的排序算法——冒泡排序算法，学习其原理及其Verilog实现。 二、冒泡排序原理冒泡排序算法（Bubble Sort）是一种简单的排序算法，它会逐个元素地重复遍历输入列表，将当前元素与后面的元素进行比较，并根据升序排序或者降序排序交换它们的值。从前往后或者从后往前重复遍历这个列表，直到在一次遍历期间不必执行任何交换，这意味着列表已完全排序。一个长度为N的序列，对该列表的遍历次数为N-1次。那么，具体步骤可以分为以下几个步骤： （1）对一个序列中的数值从前往后依次比较相邻的两个数值，如果前面的数值（数值一）大于后面的数值（数值二），则交换这两个数值； （2）重复步骤（1）的操作（N-1）次，排序完成； 那么，对于一个长度N=5的序列，其排序过程如下图所示。
那么，根据冒泡排序的原理，我们可以编写对于的Verilog代码，如下。对于一个长度为N的序列，每轮排序总共需要进行(N-1)次比较，而总共要进行(N-1)轮的排序，所以在代码中我们分别设置了单论排序计数器cnt_1和排序轮数计数器cnt_2用于计数，如果单轮排序计数器cnt_1达到N-2，则表示单轮排序结束，开始下一轮的排序，如果排序轮数计数器cnt_2达到N-2，则表示对该序列排序结束，输出排序后的数值和标签。另外，我们可以修改参数值ASCEND，设置对序列进行升序排序还是降序排序。 module bubble_sort #( parameter DATA_WIDTH = 8, parameter LABEL_WIDTH = 8, parameter DATA_NUMBER = 8, parameter ASCEND = 1 ) ( clk, rst_n, start, data_unsort, label_unsort, data_sorted, label_sorted, data_valid ); input clk; input rst_n; input start; input [DATA_NUMBER*DATA_WIDTH-1:0] data_unsort; //未排序数值 input [DATA_NUMBER*LABEL_WIDTH-1:0] label_unsort; //未排序标签 output reg [DATA_NUMBER*DATA_WIDTH-1:0] data_sorted; //排序后数值 output reg [DATA_NUMBER*LABEL_WIDTH-1:0] label_sorted; //排序后标签 output reg data_valid; //数据输出有效标志 reg [DATA_NUMBER*DATA_WIDTH-1:0] data_temp; reg [DATA_NUMBER*LABEL_WIDTH-1:0] label_temp; reg [2:0] FSM_state; //排序状态机 reg [$clog2(DATA_NUMBER)-1:0] cnt_1; //单轮排序次数计数器 reg [$clog2(DATA_NUMBER)-1:0] cnt_2; //排序轮数计数器 localparam Initial = 3'b001; //初始化 localparam Sort = 3'b010; //排序 localparam Finish = 3'b100; //排序结束 // 状态机 always @(posedge clk or negedge rst_n) if(!rst_n) FSM_state |
【本文地址】