基于FPGA的堆排序算法实现与改进.pdf

学兔兔 基于FPGA的堆排序算法实现与改进 An jmproved meth0d for heap sort algorithm based on FPGA 张 鹏，龚晓峰 ZHANG Peng．GONG Xiao．feng (四川大学 电气信息学院，成都610065) 摘 要：在实际计算数字信号调制参数时，为了克~FPGA与上位机接口传输速率受限问题，以及减小 上位机的计算负担，可将调制参数的计算下放至FPGA处理。这样只用上传给上位机调制参数 的计算结果，从而避免了大量原始IQ数据的传输和上位机复杂的参数计算过程。而在FPGA上 计算调制参数时，实现数据的排序是其中的一个难点。介绍了一种基于FPGA的2048点堆排 序的实现方法，通过modelsim仿真验证该算法的可行性，并通过对时序的优化，最终实现将 2048点的堆排序耗时控制在2ms以内。 关键词：堆排序；FPGA；调制参数；ARM 中图分类号：TN92 文献标识码：A 文章编号：1 009-01 34(201 5)04(下)-0033-04 Doi：1 0．3969／J．issn．1 009-01 34．201 5．04(-F)．1 0 0 引言 排序部分是将堆顶的数与堆尾的数互换位置，然后将 在实际应用中，为了计算数字信号的调制参数，通 堆项的数排除，将原来n个数的堆变为n一1个数的新堆，再 常需要将ADC采样后的数据通过FPGA处理后上传给上 将新的堆重复建堆与排序的过程直至完成排序 。 位机进行调制参数的计算。但是由于受到FPGA与上位 2 FPGA方案设计 机接口传输速率的制约，要将大量IQ数据上传至上位机 将消耗大量的时间：同时，IQ数据上传至上位机后要 2．1 FPGA与ARM方案对比 经过大量的计算处理后才能得到调制参数的结果。这大 原始调制参数设计方案与改进后设计方案的对比图 大降低了使用效率，同时给上位机添加了大量的计算负 如图1所示。 担。为此，将调制参数的计算下放至FPGA，仅仅将调 『丽 一—] h lr——] 制参数的计算结果上传至j：位机，如此便可克服上述的 I圈 鼻I f 豳 II 两个难题。 在FPGA上实现凋制参数的计算中，对解调后数据 的排序是其中的一个难点。日前在FPGA上实现排序的 算法较少，且大多排序的点数较少，无法评估大量样本 排序时FPGA所占用的资源与排序的时间…。 本文针对FPGA设计出一种流水线式的堆排序方 法，通过时序优化~modelsim仿真验证，最终实现将 (b)改进后酒制参数计算方案 2048点排序的时间控制在2ms以内。这一结果与原ARM 图l 两种方案的对比图 上位机处理速度相当，从而达到了预期设计目的。 如图l所示，如果采用原始的设计方案，当FPGA完 1 堆排序的原理 成数字下变频处理后，需要上传2048组I