FPGA篇(三)基于FPGA的几种排序算法 |
您所在的位置:网站首页 › 排序算法c实现什么变量输出 › FPGA篇(三)基于FPGA的几种排序算法 |
目录 1 冒泡法和比较排序法 1.1 算法原理 1.2 仿真结果 1.3 算法优缺点 2 并行全比较排序法 2.1 算法原理及Verilog实现 2.2 仿真结果 2.3 算法优缺点 3 串行全比较排序法 3.1 算法原理及Verilog实现 3.2 仿真结果 3.3 算法优缺点 2 总结
最近笔者在项目中正好遇到需要排序的情况,以前刚接触C语言的时候排序的方法主要有冒泡排序、选择排序等方法;于是就用Verilog实现了冒泡法,但是发现此方法和选择排序法需要的时间周期太长,比如16个数据差不多需要136个周期才能完成排序,于是笔者在网上找到了并行全比较排序法和改进的串行全比较排序法;以下将一一介绍。 1 冒泡法和比较排序法 1.1 算法原理
这两种方法比较容易理解,下面给出两种排序方法的百科连接,大家可以自行百度。 冒泡排序: https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
选择排序: https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E6%B3%95/2304587?fr=aladdin 1.2 仿真结果
下面给出冒泡法的Verilog仿真结果,蓝色箭头是输入的原始数据,红色箭头所指的是排完序的数据,黄色箭头指的是排序所用的时间,仿真用的是100MHz的始终,所以冒泡总共需要136个周期。 1.3 算法优缺点
选择排序法和冒泡法属于传统的两两比较的算法,但是消耗的周期比较长,在一些对实时性要求较高的情况下无法满足要求。 2 并行全比较排序法 2.1 算法原理及Verilog实现 传统的排序方式是以两两之间顺序比较为基础,而并行全比较实时排序算法是基于序列中任意两个数并行比较实现。由于从原来的串行比较变成了并行比较,所以需要消耗比以前多的比较器,诠释了FPGA中“用面积换速度”的思想。以序列长度为m的数据为例: A: 第一个时钟周期:将其中一个数据和其他数据在一个周期中一一比较,比较器分三种情况: 1. 这个数据大于其他数据,则它的得分为0; 2. 这个数据等于其他数据,若它在这个序列中比和它相等的其他数据靠前,则它的得分为0,反之为1; 3. 这个数据小于其他数据,则它的得分为1; //-------------------------- 计算得分 ---------------------------------- generate genvar i; for(i=1;i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |