本技术涉及一种基于FPGA的高效多项式综合BM算法装置,包括控制模块和序列模块。控制模块负责初始化和迭代计算,以完成多项式综合的BM算法求解。序列模块则用于缓存输入数据,确保算法的高效执行。
背景技术
设是上长度为N的序列,上的多项式为:;
其中,,如果序列中的元素满足递推关系:;;则称产生二元序列。其中表示以为反馈多项式的级线性移位寄存器。如果是一个能产生并且级数最小的线性移位寄存器的反馈多项式,是该移存器的级数,则称为序列的线性综合解。
Berlekamp-Massey算法(简称BM算法)采用迭代的方式求解序列的线性综合解。BM算法的流程如下:
1、初始化,设置:;
其中,为当前的输出多项式,为当前的输出多项式级数,为中间多项式,为中间多项式的级数,n为迭代次数,m为对应的样点索引。
2、迭代计算
从n=0开始进行迭代计算,迭代计算公式如下:;
其中,为第n步迭代计算的差值,分两种情况讨论:
当=0时,则,为迭代更新后的输出多项式。
当=1时,的迭代公式分两种情况:
1)若=0,则,为迭代更新后的输出多项式级数;
2)若≠0,则,。
当 =1时,的迭代公式如下:
1)若,则;
2)若,则保持不变。
BM算法采用了迭代的计算方法,特别适合FPGA进行实现,当多项式级数较短时,迭代计算时使用的寄存器资源相对较少,FPGA能够满足逻辑资源要求。当多项式级数长达上万级时,迭代计算时所用的寄存器资源也将达到数万个,时序也将变得非常复杂,采用寄存器进行迭代计算将消耗大量的资源甚至不可实现。
FPGA具备大规模的片内BRAM资源,BRAM资源具备容量大、速度快的优点,如果能够利用BRAM来替代迭代所用的移位寄存器,则能够解决长级数多项式综合的BM算法实现问题。常规地,BRAM资源支持的缓存深度高达百万样点。因此,需要开发一种基于FPGA的长级数多项式综合的BM算法实现装置。
实现思路