一种基于钱搜索算法和福尼算法的并行电路

摘要

为了解决现有电路硬件资源消耗过大，处理速度不能满足当前高速数据传输的技术问题，本发明提供了一种基于钱搜索算法和福尼算法的并行电路，在实现并行转换时，采用在s个时钟周期对输入的一组错误位置多项式和错误值多项式同时处理，或者在2s个时钟周期内对一组错误位置多项式和错误值多项式分时处理的方式，不但能够满足高速并行处理数据并且结构简单，硬件资源消耗较小。

说明书

技术领域

本发明涉及译码技术领域，具体涉及一种基于钱搜索算法和福尼算法的并行电路。

背景技术

设定义在伽罗华域GF(2

随着现代通信技术和专用集成电路设计的快速发展，在数据高速传输的情况下如何降低误码率成为目前重要的研究方向。因为大量的实验结果表明钱搜索算法和福尼算法有着优良的降低误码率的能力，可以大大提升系统的可靠性。所以对于钱搜索算法和福尼算法的优化占据了重要的地位。

现有的钱搜索和福尼算法的并行电路在之前传输速度较慢的情况下，电路的硬件资源消耗还可以被接受，但是随着传输速率的增大，一般并行电路所需要的资源会显著提升，所以在数据高速传输的同时，减少硬件资源消耗是需要解决的问题。

发明内容

为了解决现有电路硬件资源消耗过大，处理速度不能满足当前高速数据传输的技术问题，本发明提供了一种基于钱搜索算法和福尼算法的并行电路，能够满足高速并行处理数据并且结构简单，硬件资源消耗较小。

本发明的技术方案是：

一种基于钱搜索算法和福尼算法的并行电路，其特殊之处在于：

包括并行转换模块、寄存器堆、p路结构相同的钱搜索电路模块和p路结构相同的福尼电路模块；

并行转换模块包括错误位置初始化电路和错误值初始化电路；

错误位置初始化电路用于将输入的错误位置多项式分为p个子错误位置多项式；

错误值初始化电路的用于将输入的错误值多项式分为p个子错误值多项式；

p路钱搜索电路模块用于对所述p个子错误位置多项式并行处理，搜索出错误位置；

p路福尼电路模块用于对p路钱搜索电路模块搜索出的错误位置所对应的p个子错误值多项式进行处理，得到所述错误位置的错误图样。

进一步地，错误位置初始化电路由n-k个第一伽罗华域乘法器构成；n-k个第一伽罗华域乘法器的输入端分别对应接收错误位置多项式的第1项至第n-k项，以及分别接收n-k个伽罗华域固定数(α

错误值初始化电路由n-k个第二伽罗华域乘法器并联构成；n-k个第二伽罗华域乘法器的输入端分别对应接收错误值多项式的第1项至第n-k项，以及分别接收n-k个伽罗华域固定数(α

进一步地，第p路钱搜索电路模块由n-k个第三伽罗华域乘法器、第一加法器、第二加法器和比较器构成；n-k个第三伽罗华域乘法器的其中一个输入端分别接收来自寄存器堆的第p个子错误位置多项式的n-k项，n-k个第三伽罗华域乘法器的另一个输入端分别接收n-k个伽罗华域固定数α

进一步地，第p路福尼电路模块由n-k个第四伽罗华域乘法器、第三加法器、求倒数模块和第五伽罗华域乘法器构成；n-k个第四伽罗华域乘法器的其中一个输入端分别接收来自寄存器堆的第p个子错误值多项式的n-k项，n-k个第四伽罗华域乘法器的另一个输入端分别接n-k个伽罗华域固定数α

或者，

所述并行转换模块包括选择器和n-k个第一伽罗华域乘法器；

选择器用于实现向所述n-k个第一伽罗华域乘法器输入的错误位置多项式和错误值多项式的切换；

当n-k个第一伽罗华域乘法器的其中一个输入端分别对应接收错误位置多项式的第1项至第n-k项，另一个输入端分别对应接收n-k个伽罗华域固定数(α

当n-k个第一伽罗华域乘法器的其中一个输入端分别对应接收错误值多项式的第1项至第n-k项，另一个输入端分别对应接收n-k个伽罗华域固定数(α

n-k个第一伽罗华域乘法器的输出端接所述寄存器堆的输入端。

进一步地，第p路钱搜索电路模块由n-k个第三伽罗华域乘法器、第一加法器、第二加法器和比较器构成；n-k个第三伽罗华域乘法器的其中一个输入端分别接收来自寄存器堆的第p个子错误位置多项式的n-k项，n-k个第三伽罗华域乘法器的另一个输入端分别接收n-k个伽罗华域固定数α

进一步地，第p路福尼电路模块由n-k个第四伽罗华域乘法器、第三加法器、求倒数模块和第五伽罗华域乘法器构成；n-k个第四伽罗华域乘法器的其中一个输入端分别接收来自寄存器堆的第p个子错误值多项式的n-k项，n-k个第四伽罗华域乘法器的另一个输入端分别接n-k个伽罗华域固定数α

与现有技术相比，本发明的优点是：

1.本发明能够显著提升电路处理速度，在RS(255,223)的情况下，现有并行钱搜索和福尼算法电路吞吐量只有16.8Gbps，而本发明的吞吐量为23.7Gbps。而且本发明在RS(1023,847)的情况下，吞吐量达到了35.9Gbps。

2.现有并行电路中的并行转换模块实现p路并行通常是在1个时钟周期内实现的，但是需要2s*(n-k)个乘法器单元，硬件消耗资源很大。

而本发明的并行转换模块有两种实现方式，一种实现方式是对输入的一组错误位置多项式和错误值多项式同时处理，另一种实现方式是对输入的一组错误位置多项式和错误值多项式间隔若干个时钟周期进行分时处理；

当采用同时处理的方式时，需要s个时钟周期实现p路并行，所需的乘法器单元仅为2*(n-k)个，在少量增加时钟周期的情况下，大大降低了乘法器单元的数目，减少了硬件资源的消耗；

当采用分时处理时，并行转换模块在2s个时钟周期内，前s个时钟周期内每个周期计算出一个子错误位置多项式，后s个时钟周期内每个周期计算出一个子错误值多项式，因此在2s个时钟周期总共分出p个子错误位置多项式和p个子错误值多项式分别输入到p路钱搜索电路模块和p路福尼电路模块(s在数量上与p相等，但物理意义不同)，这样的分时处理操作实现了伽罗华域乘法器的复用，使得并行转换模块只需要使用n-k个伽罗华域乘法器，较之现有技术，使用乘法器的个数减少了2s倍，显著降低了硬件资源的消耗，而时钟周期仅仅增加了2s-1。

附图说明

图1为本发明并行电路的结构图。

图2为本发明的并行转换模块中错误位置初始化电路的结构图。

图3为本发明的并行转换模块中错误值初始化电路的结构图。

图4为本发明中寄存器堆的输入、输出示意图。

图5为本发明的第p路钱搜索电路模块的结构图。

图6为本发明的第p路福尼电路模块的结构图。

图7为本发明的并行转换模块的另一实施例的结构图(分时复用n-k个伽罗华域乘法器的方案)。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。

一、钱搜索算法和福尼算法流程

钱搜索算法的本质是求有限域多项式的根，因为多项式的项数是有限的，所以对多项式中每一项的元素求值，如果多项式结果为0，那么这个元素的值就是多项式的根，则该元素的位置就是错误位置。以RS码为例，钱搜索算法处理输入的错误位置多项式，根据错误位置多项式验证每个位置的根的形式来搜索错误。

基于钱搜索算法的错误位置多项式为：

σ(α

基于钱搜索算法的错误位置搜索为：

σ(α

其中α(α

由于基于钱搜索算法的错误位置计算采用串行方法需要的时钟周期数过长，无法对数据进行有效的处理，而现有并行方法的电路资源又消耗过大，所以本发明对基于钱搜索算法的错误位置计算进行高效并行化处理。

基于钱搜索算法的错误位置的判定条件是依次将α

钱搜索算法并行化公式为：

σ

σ

…

σ

钱搜索算法并行化错误位置搜索为：

σ

σ

...

σ

福尼算法的本质是计算错误位置上的错误图样，用于纠错。以RS码为例，福尼算法处理输入的错误值多项式，在钱搜索算法搜索出错误位置后，则计算该错误位置的错误图样用于与输入码字进行异或纠错。

基于福尼算法的错误值多项式为：

ω(α

基于福尼算法的错误图样计算式为：

其中ω(α

基于福尼算法的串行错误值计算需要的时钟周期过长，无法对高速数据进行有效的处理，所以本发明对基于福尼算法的错误值计算进行高效并行化处理。

基于福尼算法的错误值的计算条件是依次将α

福尼算法并行化公式为：

ω

ω

…

ω

福尼算法并行化错误图样计算为：

二、基于钱搜索和福尼算法的并行电路结构描述

如图1所示，本发明所提供的并行电路，包括并行转换模块、由2s*(n-k)个寄存器单元构成的寄存器堆、p路结构相同的钱搜索电路模块、p路结构相同的福尼电路模块。其中，并行转换模块包括错误位置初始化电路和错误值初始化电路。

如图2、4所示，错误位置初始化电路由n-k个第一伽罗华域乘法器并联构成；n-k个第一伽罗华域乘法器的输入端分别对应接收错误位置多项式的第1项至第n-k项(LambdaIn_0、LambdaIn_1，…，LambdaIn_n-k-1)和n-k个伽罗华域固定数((α

如图3、4所示，错误值初始化电路由n-k个第二伽罗华域乘法器并联构成；n-k个第二伽罗华域乘法器的输入端分别对应接收错误值多项式的第1项至第n-k项(OmegaIn_0，OmegaIn_1…，OmegaIn_n-k-1)和n-k个伽罗华域固定数((α

如图1、2、5所示，p路钱搜索电路模块的输入端分别接收来自寄存器堆的p个子错误位置多项式；p路钱搜索电路模块的输出端分别接p路福尼电路模块的输入端。

如图1、2、6所示，p路福尼电路的输入端分别接p路钱搜索电路模块的输出端和来自寄存器堆的p个子错误值多项式，p路福尼电路模块的输出端输出错误图样。

三、并行电路中各子模块电路结构描述

1.并行转换模块

并行转换模块包括错误位置初始化电路和错误值初始化电路。

1.1错误位置初始化电路的功能是将输入的错误位置多项式分为p个子错误位置多项式。如图2所示，错误位置初始化电路中，第一伽罗华域乘法器的一个输入((α

基于钱搜索算法的p路子错误位置多项式初始化为：

σ

σ

...

σ

初始化后，第1，第t+1，…，第(p-1)t+1个位置上的错误位置搜索为：

σ

σ

...

σ

1.2错误值初始化电路的功能是将输入的错误值多项式分为p个子错误值多项式。如图3所示，错误值初始化电路中第二伽罗华域乘法器的一个输入((α

基于福尼算法的p路子错误值多项式初始化为：

ω

ω

...

ω

若第1，第t+1，…，第(p-1)t+1个位置上有错，则错误图样计算为：

2.钱搜索电路模块

本发明中p路钱搜索电路模块的结构相同，这里仅以第p路钱搜索电路模块为例进行说明。

如图5所示，第p路钱搜索电路模块由n-k个第三伽罗华域乘法器、第一加法器、第二加法器和比较器构成。

n-k个第三伽罗华域乘法器的其中一个输入端分别接收来自寄存器堆的第p个子错误位置多项式的n-k项，n-k个第三伽罗华域乘法器的另一个输入端分别接收n-k个伽罗华域固定数(α

下面对p路钱搜索电路模块在一个时钟周期内的操作进行描述。p路钱搜索电路模块对初始化后的p个并行子错误位置多项式在接下来的

时钟周期的基础给多项式中的每项分别乘α

第一个时钟周期：

错误位置计算公式：

σ

σ

...

σ

错误位置搜索：

σ

σ

...

σ

第二个时钟周期：

错误位置计算公式：

σ

σ

...

σ

错误位置搜索：

σ

σ

...

σ

第j个时钟周期(j＜t)：

错误位置计算公式：

σ

σ

...

σ

错误位置计算公式：

σ

σ

...

σ

第t个时钟周期(最后一个时钟周期)：

错误位置计算公式：

σ

σ

...

σ

错误位置搜索：

σ

σ

...

σ

3.福尼电路模块

本发明中p路福尼电路模块的结构相同，这里仅以第p路福尼电路模块为例进行说明。

如图6所示，第p路福尼电路模块由n-k个第四伽罗华域乘法器、第三加法器、求倒数模块和第五伽罗华域乘法器构成。

n-k个第四伽罗华域乘法器的其中一个输入端分别接收来自寄存器堆的第p个子错误值多项式的n-k项，n-k个第四伽罗华域乘法器的另一个输入端分别接收n-k个伽罗华域固定数(α

下面对p路福尼电路模块在一个周期内的操作进行描述。p路福尼电路模块对初始化后的并行错误值多项式在接下来的

第一个时钟周期：

错误值计算公式：

ω

ω

...

ω

错误图样计算：

第二个时钟周期：

错误值计算公式：

ω

ω

...

ω

错误图样计算：

第j个时钟周期(j＜t)：

错误值计算公式：

ω

ω

...

ω

错误图样计算：

第t个时钟周期(最后一个时钟周期)：

错误值计算公式：

ω

ω

...

ω

错误值计算公式：

以上用到的乘法和加法均为伽罗华域上的计算方式，乘法使用伽罗华域乘法器(异或操作实现)方式实现。

本发明上述方案中，并行转换模块是采用同时处理的方式，在s个时钟周期对错误位置多项式和错误值多项式进行同时处理，将输入的一组错误位置多项式和错误值多项式在s个时钟周期同时乘以p组对应的伽罗华域系数，分成p组子错误位置多项式和p组子错误值多项式，然后送入p路钱搜索电路模块及p路福尼电路模块。

在其他实施例中，为了进一步减少占用资源，本发明还可以在上述并行化技术方案的基础上对并行转换模块进行优化，利用选择器select实现对一组错误位置多项式和一组错误值多项式的分时处理(即间隔若干个时钟周期分别进行处理)，例如在第1个时钟周期，向n-k个伽罗华域乘法器中选择输入包含n-k项的一组错误位置多项式和对应的伽罗华域固定系数，得到第1个子错误位置多项式，然后在第2个时钟周期，向n-k个伽罗华域乘法器中选择输入包含n-k项的一组错误值多项式和对应的伽罗华域固定系数，得到第1个子错误值多项式，…，以此类推，在第2s-1个时钟周期，向n-k个伽罗华域乘法器中选择输入包含n-k项的同样一组错误位置多项式和对应的伽罗华域固定系数，得到第p(p＝s)个子错误位置多项式，在第2s个时钟周期，向n-k个伽罗华域乘法器中选择输入包含n-k项的同样一组错误值多项式和对应的伽罗华域固定系数，得到第p(p＝s)个子错误值多项式，从而实现p路并行化；在此过程中，并行转换模块中的错误位置初始化电路和错误值初始化电路共用了同一组n-k个伽罗华域乘法器，如图7所示。该方案相比上述并行化方案而言，节省了n-k个伽罗华域乘法器，但是处理时钟周期仅增加了s个时钟周期。