CN102650982B - 一种基于fpga的lm算法实现方法 - Google Patents

Abstract

本发明涉及一种基于FPGA的LM算法实现方法，特别涉及一种用于高斯曲线拟合的LM算法的FPGA实现技术，属于数据处理技术领域。首先对输入的串行数据流进行串并转换并进行归一化处理，之后进行LM算法迭代循环，循环中首先计算拟合变量，然后进行指数查找，进而计算迭代系数，迭代系数计算后利用延时子模块实现同步各个参数到达功能模块的时间，通过并行判断子模块对迭代系数进行修正，进而修正拟合变量。本发明提高了LM算法的处理速度，在满足高精度测量的同时，还能达到高速实时的需求，该算法模块既能计算线性模型参数，又能计算非线性模型参数，同时具有低功耗、小型化、高速等特点，可应用于实时高精度的信号处理领域。

Description

一种基于FPGA的LM算法实现方法

技术领域

本发明涉及一种基于FPGA的LM算法实现方法，特别涉及一种用于高斯曲线拟合的LM算法的FPGA实现技术，属于数据处理技术领域。

背景技术

当前测量数据处理过程中，在观测值服从正态分布的前提下，最小二乘估计是最优线性无偏估计，因而在数据处理中被广泛应用。而当测量的函数模型是非线性模型时，一般是将非线性模型利用泰勒公式近似化为线性模型，然后用最小二乘估计法处理。非线性的最小二乘法是有偏的，在需要高精度求解非线性模型参数时，计算结果精度较低，有的甚至不能线性近似，因而求得的结果实用价值不大。这时需要研究非线性模型的精确数值解法。

Levenberg-Marquard算法(常被简称为LM算法)既能计算线性模型参数，又能计算非线性模型参数，并且无论法方程是良态、病态还是秩亏，该算法都能收敛，计算结果可靠。如果函数模型是线性并且呈良态，该算法只需迭代一次便可得到精确解，呈病态时迭代几次可以收敛到稳定解。如果函数模型是非线性模型，一般只需迭代几次便可收敛，当初值偏离真值较远时，可以通过增加迭代次数来获得最优解。

然而正是由于LM算法需要多次迭代，运算量大，用通用计算机或DSP等进行计算时实时性很难保证，用高性能计算机来处理成本又非常高。FPGA芯片虽然在速度上与DSP略有差距，但能实现并行结构。最新推出的FPGA器件中，不仅集成有丰富的可配置逻辑块资源，还包括大量面向计算密集应用的DSP单元、块状RAM和高速串行通信单元。因此选择可编程的逻辑器件进行数字信号处理是当今世界的发展趋势。

发明内容

本发明的目的是为了克服上述现有技术的缺陷，能够在实现LM算法时既保证实时性又不会成本太高，提出了一种基于FPGA的LM算法实现方法，该模块全部由硬件描述语言实现，可以提升数据处理的运行速度和稳定性以及数据的计算效率，节省开发成本。

本发明的目的是通过以下技术方案实现的。

本发明的一种基于FPGA的LM算法实现方法，其实现平台为FPGA，采用硬件描述语言实现，模块输入为采用串行数据流方式的外部测量数据，LM算法模块包括以下子模块：串并转换子模块、归一化处理子模块、拟合变量计算子模块、指数计算子模块、迭代系数计算A子模块、延时A子模块、迭代系数计算B子模块、延时B子模块和并行判断子模块；首先通过串并转换子模块将输入的串行数据流转换成并行数据并送入归一化处理子模块进行归一化处理，之后进行LM算法迭代循环，也即首先进入拟合变量计算子模块计算拟合变量，然后通过指数计算子模块进行指数查找，进而通过迭代系数计算子模块计算迭代系数，迭代系数计算后利用延时子模块实现同步各个参数到达功能模块的时间，通过并行判断子模块对迭代系数进行修正，进而修正拟合变量。

上述一种基于FPGA的LM算法实现方法，其步骤如下：

1)通过串并转换子模块将本算法模块外部输入串行数据流转换为并行数据流送入归一化子模块；

2)归一化模块对步骤1)生成的并行数据进行归一化处理后送入拟合变量计算子模块；

3)拟合变量计算子模块根据步骤2)归一化处理后的数据计算拟合变量及拟合变量的初值，并将该拟合变量及拟合变量初值送入指数计算子模块；

4)指数计算子模块对步骤3)的拟合变量进行指数查找，并将指数计算值送入迭代系数计算子模块；

5)迭代系数计算A子模块对步骤4)产生的指数计算值进行计算，计算得到迭代过程中所需要修正的迭代参数，并将各迭代参数送入延时子模块；

6)利用延时A子模块同步步骤5)产生的各个迭代参数到达并行判断子模块的时间，并将处理结果送入并行判断子模块；

7)通过并行判断子模块对经步骤6)处理的各迭代参数进行修正，得出当前情况下的拟合变量值X_i；

8)对拟合变量值X_i再通过迭代系数计算B子模块和延时B子模块进一步对拟合变量进行处理；

9)将经过步骤8)处理后的拟合变量送入步骤3)，计算拟合变量初值，并将当前拟合变量及拟合变量初值送入步骤4)，重复步骤4)～步骤9)进行LM算法迭代直到达到预先设定的迭代次数或者算法收敛。

上述指数计算子模块的指数查找过程中的指数查找表采用分段处理方式，根据指数曲线概率分布特性来确定各曲线段的查找精度，其中曲线段越陡峭，则该段的查找精度越高，这种方式不仅保证了查找表的整体精度不变，而且减少了查找表占用的资源。

上述延时子模块采用移位寄存器实现，将每个迭代参数的计算结果存储在移位寄存器中，所有参数计算结束后，同时输出到下一个功能模块并行判断子模块，避免由于时间延迟造成数据流的丢失，并实现同步各个参数到达功能模块的时间；

并行判断子模块首先对迭代参数进行判断然后采用并行处理方式，针对各迭代参数的判断结果实施三种情况下的拟合变量算法，根据对迭代参数的判断结果选择输出当前情况下的拟合变量值X_i，节约了算法的处理时间。

有益效果

本发明提出了一种基于FPGA的LM算法实现方法，提高了LM算法的处理速度，将该算法模块应用于光纤传感测量等测量领域，在满足高精度测量的同时，还能达到高速实时的需求。该算法模块既能计算线性模型参数，又能计算非线性模型参数，同时具有低功耗、小型化、高速等特点，可应用于实时高精度的信号处理领域，尤其用于高精度的高斯曲线拟合。

附图说明

图1为基于FPGA的LM算法实现方法的总体流程框图；

图2为本发明中指数计算子模块的流程框图；

图3为本发明中并行判断子模块的原理框图。

具体实施方式

下面结合附图和实施例对本发明做进一步说明。

一种基于FPGA的LM算法实现方法，其输入为采用串行数据流方式的外部测量数据，如图1所示，LM算法模块包括以下子模块：串并转换子模块、归一化处理子模块、拟合变量计算子模块、指数计算子模块、迭代系数计算A子模块、延时A子模块、迭代系数计算B子模块、延时B子模块和并行判断子模块；

首先通过串并转换子模块将输入的串行数据流转换成并行数据并送入归一化处理子模块进行归一化处理，之后进行LM算法迭代循环；

LM算法迭代循环中，首先进入拟合变量计算子模块计算拟合变量，然后通过指数计算子模块进行指数查找，进而通过迭代系数计算子模块计算迭代系数，迭代系数计算后利用延时子模块实现同步各个参数到达功能模块的时间，通过并行判断子模块对迭代系数进行修正，进而修正拟合变量。

上述一种基于FPGA的LM算法实现方法，其算法步骤如下：

1)通过串并转换子模块将本算法模块外部输入串行数据流转换为并行数据流送入归一化子模块；

2)归一化模块对步骤1)生成的并行数据进行归一化处理后送入拟合变量计算子模块；

3)拟合变量计算子模块根据步骤2)归一化处理后的数据计算拟合变量及拟合变量的初值，并将该拟合变量及拟合变量初值送入指数计算子模块；

4)指数计算子模块对步骤3)的拟合变量进行指数查找，并将指数计算值送入迭代系数计算子模块；

5)迭代系数计算A子模块对步骤4)产生的指数计算值进行计算，计算得到迭代过程中所需要修正的迭代参数，并将各迭代参数送入延时子模块；

6)利用延时A子模块同步步骤5)产生的各个迭代参数到达并行判断子模块的时间，并将处理结果送入并行判断子模块；

7)通过并行判断子模块对经步骤6)处理的各迭代参数进行修正，得出当前情况下的拟合变量值X_i；

8)对拟合变量值X_i再通过迭代系数计算B子模块和延时B子模块进一步对拟合变量进行处理；

9)将经过步骤8)处理后的拟合变量送入步骤3)，计算拟合变量初值，并将当前拟合变量及拟合变量初值送入步骤4)，重复步骤4)～步骤9)进行LM算法迭代直到达到预先设定的迭代次数或者算法收敛。

上述指数计算子模块的指数查找过程中的指数查找表采用分段处理方式，根据指数曲线概率分布特性来确定各曲线段的查找精度，其中曲线段越陡峭则该段的查找精度越高，这种方式不仅保证了查找表的整体精度不变，而且减少了查找表占用的资源。

上述延时子模块采用移位寄存器实现，将每个参数的计算结果存储在移位寄存器中，所有参数计算结束后，同时输出到下一个功能模块，避免由于时间延迟造成数据流的丢失，并实现同步各个参数到达功能模块的时间；

并行判断子模块首先对迭代参数进行判断然后采用并行处理方式，计算三个拟合变量算法，根据对迭代参数的判断结果选择输出当前情况下的拟合变量值X_i，节约了算法的处理时间。

实施例

将上述一种基于FPGA的LM算法实现方法对该模块输入的串行数据流进行处理，串并转换子模块将输入的串行数据流转换为并行的N个数据输出Y₁，Y₂，...Y_N，归一化子模块对所有数据进行归一化处理输出，首先查找N个数据其中的最大值Y_max，经过归一化模块后输出为(Y₁/Y_max)，(Y₂/Y_max)，...，(Y_max/Y_max)，...，(Y_N/Y_max)；

得到归一化数据后，进入LM算法迭代循环，首先在拟合变量计算子模块中计算拟合变量X＝(A，B，C)，得到拟合变量初值X₀，然后将拟合变量X及初值X₀送入指数计算子模块；

指数计算子模块的内部流程结构如图2所示，包括指数幂计算子模块、正数查找表、负数查找表和指数输出子模块，指数查找表采用分段处理方式，根据指数曲线概率分布特性，曲线平坦段的查找精度低于曲线陡峭段的查找精度，针对指数的幂存在正负数情况，整个查找功能通过正数幂和负数幂两张查找表完成，指数计算子模块通过以下步骤实现：

41)通过指数幂计算子模块计算幂值为正或者负；

42)根据指数计算子模块的正负信号，选择正数查找表或者负数查找表，进行指数查找；

43)经过指数输出子模块输出查找后的指数计算值；

指数计算子模块输出的指数计算值输入到迭代参数计算A子模块，用来计算迭代过程中所需要修正的参数，其中包括阻尼因子，Jacobi矩阵等，该模块主要包括矩阵求逆、矩阵与列向量相乘等部分内容，所计算得出的各迭代参数再利用延时A子模块实现同步各个参数到达下一个功能模块并行判断子模块的时间；

由并行判断子模块进行对迭代准则的判断选择，并行判断子模块原理框图如图3所示，以计算后的迭代参数rat为例，根据进入判断子模块的rat的值有三种情况：情况A，0＜rat＜0.5时对应拟合变量算法A，nu＝max(nu*10，0.1)；情况B，0.5＜rat＜1时对应拟合变量算法B，nu＝0；情况C，rat＞1时对应拟合变量算法C，nu的值不改变，判断输出的拟合变量值X通过输出子模块输出；并行判断子模块首先对迭代参数进行判断然后采用并行处理方式，计算A、B、C三个拟合变量算法，根据对迭代参数的判断结果选择输出当前情况下的拟合变量值X_i；

将拟合变量值X_i再通过迭代系数计算B子模块和延时B子模块，进而修正迭代系数，进入图1中的拟合变量计算子模块进入第二次的迭代过程，根据迭代次数判断是否进行下一次迭代，从而完成对拟合变量的LM算法拟合。

以上所述为本发明的较佳实施例而已，本发明不应该局限于该实施例和附图所公开的内容。凡是不脱离本发明所公开的精神下完成的等效或修改，都落入本发明保护的范围。

Claims (2)

1.一种基于FPGA的LM算法实现方法，其实现平台为FPGA，采用硬件描述语言实现，模块输入为采用串行数据流方式的外部测量数据，其特征在于，LM算法模块包括以下子模块：串并转换子模块、归一化处理子模块、拟合变量计算子模块、指数计算子模块、迭代系数计算A子模块、延时A子模块、迭代系数计算B子模块、延时B子模块和并行判断子模块；

所述一种基于FPGA的LM算法实现方法，其步骤如下：

1)通过串并转换子模块将本算法模块外部输入串行数据流转换为并行数据流送入归一化处理子模块；

2)归一化处理子模块对步骤1)生成的并行数据进行归一化处理后送入拟合变量计算子模块；

3)拟合变量计算子模块根据步骤2)归一化处理后的数据计算拟合变量及拟合变量的初值，并将该拟合变量及拟合变量初值送入指数计算子模块；

4)指数计算子模块对步骤3)的拟合变量进行指数查找，并将指数计算值送入迭代系数计算A子模块；

5)迭代系数计算A子模块对步骤4)产生的指数计算值进行计算，计算得到迭代过程中所需要修正的迭代参数，并将各迭代参数送入延时A子模块；

6)利用延时A子模块同步步骤5)产生的各个迭代参数到达并行判断子模块的时间，并将处理结果送入并行判断子模块；

7)通过并行判断子模块对经步骤6)处理的各迭代参数进行修正，得出当前情况下的拟合变量值Xi；

8)对拟合变量值Xi再通过迭代系数计算B子模块和延时B子模块进一步对拟合变量进行处理；

9)将经过步骤8)处理后的拟合变量送入步骤3)，计算拟合变量初值，并将当前拟合变量及拟合变量初值送入步骤4)，重复步骤4)～步骤9)进行LM算法迭代直到达到预先设定的迭代次数或者算法收敛。

2.根据权利要求1所述的一种基于FPGA的LM算法实现方法，其特征在于，所述指数计算子模块包括指数幂计算子模块、正数查找表、负数查找表和指数输出子模块，正数查找表和负数查找表均采用分段处理方式，根据指数曲线概率分布特性来确定各曲线段的查找精度，其中曲线段越陡峭，则该段的查找精度越高，指数计算子模块通过以下步骤实现：

41)通过指数幂计算子模块计算幂值为正或者负；

42)根据指数幂计算子模块的正负信号，选择正数查找表或者负数查找表，进行指数查找；

43)经过指数输出子模块输出查找后的指数计算值。