低硬件开销Reed－Solomon解码器

摘要

本发明公开了一种低硬件开销Reed－Solomon解码器，包括：“校正子多项式/钱式搜索/错误估计值计算多功能模块”，通过算法Si＝((rn－1αi－1+rn－2)αi－1+…+r1)αi－1+r0 1≤i≤2t，实现校正子多项式的计算，其还可用于时分实现钱式搜索和错误估值计算等功能。"错误位置多项式/错误估计值多项式求取多功能模块"，通过改进型无逆Berlekamp－Massey算法，使得在进行错误位置多项式迭代算法求解时不需要每次迭代调用求逆运算，节省了硬件资源，同时该模块还可时分实现对错误位置多项式和错误估计值多项式的求取。本发明优化了Reed－Solomon解码器的解码算法，降低了解码的硬件复杂度，大大减小了硬件开销，降低了解码器的芯片面积和功耗。

说明书

技术领域

本发明涉及一种T-DMB系统中的Reed-Solomon解码器，尤其涉及一种T-DMB系统中的低硬件开销Reed-Solomon解码器。

背景技术

T-DMB是韩国推出的地面数字多媒体广播标准，该标准是基于欧洲数字广播标准DAB基础上做了一些修改而成的，以便向手机、PDA和便携电视等手持设备传送无线数字电视节目。为了延长这些手持设备收看无线电视节目的时间和降低设备的成本，市场对T-DMB系统接收芯片的面积和功耗提出了很高的要求。

在T-DMB系统中，为了抵抗传输过程中的突发性错误，需要在T-DMB发射端对数据进行Reed-Solomon编码，相应的在T-DMB接收机端对数据进行Reed-Solomon解码。Reed-Solomon编码是基于伽罗华域GF(2^m)上，是码元符号域和根域相一致的BCH码。T-DMB系统中的RS码是基于RS(255，239，t＝8)码的RS(204，188，t＝8)截短码。其本原多项式为：P(x)＝x⁸+x⁴+x³+x²+1其生成多项式为$G\left(x\right)=\underset{i=0}{\overset{15}{\Pi }}(x+{\alpha }^i),$其码间最小距离为d_min＝2t+1＝17，其中最大能纠错误数为t＝8字节的突发性错误。

Reed-Solomon编码和一般循环码的编码方法相同，设待编码的信息为m＝(m_k-1，…，m₁，m₀)，相应的信息多项式为m(x)＝m_k-1x^k-1+…+m₁x+m₀，其码字为c＝(m_k-1，…，m₁，m₀，r_n-k-1，...，r₁，r₀)，所以其码字的多项式表示方法为C(x)＝m_k-1x^n-1+…+m₀x^n-k+r_n-k-1x^n-k-1+…+r₀＝m(x)x^n-k+r(x)≡0(modg(x))，所以相应的校验位的多项式求取方法为-r(x)＝-C(x)+m(x)x^n-k≡m(x)x^n-k(modg(x))。所以通过基于伽罗华域GF(2^m)的LFSR就能对信息进行Reed-Solomon编码。

而Reed-Solomon解码相对编码则要复杂的多。RS解码器算法主要分时域和频域两大类，频域解码算法由于需要额外的错误值变换模块，反变换模块和伴随式延迟模块，因此这时芯片功耗和面积要比时域解码大。时域解码算法中，根据求解错误位置多项式的不同方法，主要可分为Berlekamp-Messy和Eu-Clidean两种方法，但相比较而言，Berlekamp-Messy算法，尤其是基于硬件设计而优化后的改进Berlekamp-Messy算法由于使用了迭代和寄存器复用等技术，因此比Eu-clidean算法硬件复杂度小，从而使得芯片面积和芯片功耗也相对更小。各种解码算法的工作流程也都相似，下面以Berlekamp-Massey迭代算法为例，说明一般解码算法及流程：

1、计算校正子，判断是否有错。如有校正子多项式为零，则该接收码字没有错误。如校正子多项式为非零，则需纠错。其中，校正子多项式系数算法如下：

${\overrightarrow{S}}^T=\overrightarrow{H}·{\overrightarrow{R}}^T$

$=\left(\begin{array}{ccccc}1& 1& ...& 1& 1\\ {\alpha }^{n-1}& {\alpha }^{n-2}& ...& \alpha & 1\\ .& .& & .& .\\ .& .& & .& .\\ .& .& & .& .\\ {\alpha }^{(2t-1)(n-1)}& {\alpha }^{(2t-1)(n-2)}& ...& {\alpha }^{2t-1}& 1\end{array}\right)\left(\begin{array}{c}{r}_{n-1}\\ r_{n-2}\\ .\\ .\\ .\\ r_0\end{array}\right)$

$=\left(\begin{array}{c}{r}_{n-1}+r_{n-2}+...+r_1+r_0\\ r_{n-1}{\alpha }^{n-1}+r_{n-2}{\alpha }^{n-2}+...+r_1\alpha +r_0\\ .\\ .\\ .\\ r_{n-1}{\alpha }^{(2t-1)(n-1)}+r_{n-2}{\alpha }^{(2t-1)(n-2)}+...+r_1{\alpha }^{(2t-1)}+r_0\end{array}\right)---\left(1\right)$

$=\left[\underset{j=0}{\overset{n-1}{\Sigma }}{r}_j{\left({\alpha }^i\right)}^j\right]$

$=(s_0,s_1,...,s_{2t-1}),i=\mathrm{0,1},...,2t-1$

2、利用计算所得的校正子，采用Berlekamp-Massey迭代算法求取错误位置多项式，其具体过程为：

首先，定义C⁽⁰⁾(D)＝1，B⁽⁰⁾(D)＝1，L⁽⁰⁾(D)＝1；

然后，按下面算法循环，直到2t次迭代完成：

定义${\Delta }^{(k+1)}=\underset{j=0}{\overset{L^{\left(k\right)}}{\Sigma }}{C}_j^{\left(k\right)}{S}_{2t-j},$

并进行以下计算：

         C^(k+1)(D)＝C^(k)(D)-Δ^(k+1)B^(k)(D)D

         B^(k+1)(D)＝DB^(k)(D)......if(Δ^(k+1)＝0‖2L^(k)＞k)

         B^(k+1)(D)＝DB^(k)(D)......if(Δ^(k+1)≠0‖2L^(k)≤k)    (2)

         L^(k+1)＝L^(k).............if(Δ^(k+1)＝0‖2L^(k)＞k)

         L^(k+1)＝k+1-L^(k).........if(Δ^(k+1)≠0‖2L^(k)≤k)

这里C^2t(D)就是错误位置多项式；

3、根据解得的校正子和错误位置多项式求取错误估值多项式，其算法如下：

ω(x)＝S(x)σ(x)mod x^2t

＝(S₁+S₂x+...S₁₆x¹⁵)(σ₀+σ₁x+...σ₈x⁸)modx¹⁶                 (3)；

＝σ₀S₁+(σ₀S₂+σ₁S₁)x+...(σ₀S₈+σ₁S₇+σ₂S₆...+σ₇S₁)x⁷

4、根据钱式搜索(Chien Search)找出错误位置。错误位置多项式的根指示了错误位置；

5、根据钱式搜索和Forney算法$Y_l=-\frac{\omega \left(x_l^{-1}\right)}{{x_l^{-1}\sigma }^{\prime }\left(x_l^{-1}\right)}$计算出错误位置的错误值，$\hat{C}\left(x\right)=R\left(x\right)-\hat{E}\left(x\right),$完成解码纠错。

因此，根据上述解码算法，现在常用的Reed-Solomon解码器的结构框图如图1所示，包括：求解校正多项式模块、求取错误位置多项式迭代算法模块、求取错误估值模块、钱式搜索模块、Forney算法模块和错误纠值模块，来实现上面所述的算法，从而完成解码纠错。

发明内容

本发明所要解决的技术问题是提供一种T-DMB系统中的低硬件开销Reed-Solomon解码器，可在传统Reed-Solomon解码算法的基础上对解码器所采用的解码算法进行优化，从而可降低Reed-Solomon解码的硬件复杂度，减小芯片的面积和功耗。

为解决上述技术问题，本发明提供一种低硬件开销Reed-Solomon解码器，其特征在于，包括：

“校正子多项式/钱式搜索/错误估计值计算多功能模块”，通过算法S_i＝((r_n-1α^i-1+r_n-2)α^i-1+…+r₁)α^i-1+r₀  1≤i≤2t实现对校正子多项式的计算；同时用于时分实现钱式搜索和错误估计值计算；

“错误位置多项式/错误估计值多项式求取多功能模块”，通过改进型无逆Berlekamp-Massey算法，时分实现对错误位置多项式和错误估计值多项式的求取。

本发明由于采用了上述技术方案，具有这样的有益效果，即使用“校正子多项式/钱式搜索/错误估计值计算多功能模块”通过如下算法：S_i＝((r_n-1α^i-1+r_n-2)α^i-1+…+r₁)α^i-1+r₀  1≤i≤2t，实现校正子多项式的计算，而且该模块还可时分实现钱式搜索和错误估值计算等功能；使用“错误位置多项式/错误估计值多项式求取多功能模块”，通过改进型无逆Berlekamp-Massey(modified inverse free Berlekamp-Massey)算法时分实现错误位置多项式的迭代算法和错误估计值多项式的求取，因此在硬件实现复杂度上有了较大优化，而且使得在进行错误位置多项式迭代算法求解时不需要每次迭代调用求逆运算，同时易于时分实现错误估值多项式的求取；因此，综上所述，本发明优化了Reed-Solomon解码器所实现的解码算法，降低了Reed-Solomon解码的硬件复杂度，大大减小了硬件开销，降低了解码器的芯片面积和功耗。

附图说明

下面结合附图与具体实施方式对本发明作进一步详细的说明：

图1为使用现有技术中常用的解码算法实现的Reed-Solomon解码器的结构框图；

图2为使用本发明所述的优化解码算法实现的Reed-Solomon解码器的结构框图；

图3为本发明所述“校正子多项式/钱式搜索/错误估计值计算多功能模块”的电路结构示意图；

图4为“校正子多项式/钱式搜索/错误估计值计算多功能模块”中计算单元的结构示意图；

图5为本发明所述“错误位置多项式/错误估计值多项式求取多功能模块”的电路结构示意图；

图6为“错误位置多项式/错误估计值多项式求取多功能模块”中计算单元的结构示意图。

具体实施方式

如图2所示，为本发明所述T-DMB接收系统中Reed-Solomon解码器的结构框图，包括“校正子多项式/钱式搜索/错误估计值计算多功能模块”、“错误位置多项式/错误估计值多项式求取多功能模块”、Forney算法模块和错误纠值模块。其中，所述“校正子多项式/钱式搜索/错误估计值计算多功能模块”可在T-DMB接收系统中时序控制模块的控制下时分实现校正子计算、钱式搜索和错误估值计算等功能。而所述“错误位置多项式/错误估计值多项式求取多功能模块”，可实现采用改进型无逆Berlekamp-Massey算法为错误位置多项式求解迭代算法，该修改后算法不需要每次迭代调用求逆运算，在硬件实现复杂度上有较大优化；而且，该模块由于采用了改进型无逆Berlekamp-Massey算法，还易于在所述T-DMB接收系统中时序控制模块的控制下时分实现错误估值多项式的求取。因此，大大减小了硬件开销，降低了解码器的芯片面积和功耗。

根据前面式(1)可知，校正子多项式系数的计算公式为：

$S_i=\underset{j=0}{\overset{n-1}{\Sigma }}{r}_j{\alpha }^{j(i-1)}---\left(4\right)$

因此，在本发明中，为了优化其硬件实现，并使其与钱式搜索和错误估值计算分时复用同一个电路结构成为可能，将式(4)转化为如下计算公式：

$S_i=\underset{j=0}{\overset{n-1}{\Sigma }}{r}_j{\alpha }^{j(i-1)}---\left(5\right)$

$=((r_{n-1}{\alpha }^{i-1}+r_{n-2}){\alpha }^{i-1}+...+r_1){\alpha }^{i-1}+r_0,1\le i\le 2t$

因此，根据式(5)，在一个实施例中，所述“校正子多项式/钱式搜索/错误估计值计算多功能模块”的硬件结构示意图可如图3所示，包括17个(即2t+1个，t表示本发明所述解码器的最大能纠错误数)第一计算单元(即图3中的S1～S16和B8)，其中每个第一计算单元的结构示意图如图4所示，包括：第一多路复用器M1，其三个输入分别为校验位r_i、0和σ_j/ω_k，其中，σ_j为“错误位置多项式/错误估计值多项式求取多功能模块”输出的错误位置多项式系数，ω_k为“错误位置多项式/错误估计值多项式求取多功能模块”输出的错误估值多项式系数，i为1到2t中的数字；j为0到t中的数字；k为0到t-1中的数字。该第一计算单元还包括第一伽罗华域加法器，其输入为所述第一多路复用器M1的输出和第一伽罗华域乘法器的输出，而其输出则送入Si寄存器中；所述第二多路复用器M2的两个输入分别为α^i-1和α^j，其中α^i-1为进行校正子计算时的迭代乘数，α^j为进行钱式搜索/错误估计值计算时的迭代乘数(此处i为1到2t中的数字，j在用于钱式搜索时为0到t中的数字，j在用于错误估值计算时为0到t-1中的数字)，而该第二多路复用器M2的输出则送入所述第一伽罗华域乘法器中；所述第一伽罗华域乘法器的输入为所述第二多路复用器M2的输出及所述Si寄存器的输出，而其输出则送入所述第一伽罗华域加法器中。本发明所述“校正子多项式/钱式搜索/错误估计值计算多功能模块”的工作原理如下：当进行校正子多项式计算时，第一多路复用器M1选择r_i支路来迭代计算；每个时钟周期输入一个r_i值，并且Si寄存器中的值S_i-1＝((r_n-1α^i-1+r_n-2)α^i-1+…r_i+2)α^i-1+r_i+1经所述第一伽罗华域乘法器乘以α^i-1后再通过所述第一伽罗华域加法器与r_i进行相加，得到S_i＝((r_n-1α^i-1+r_n-2)α^i-1+…+r_i+1)α^i-1+r_i，然后再存入到Si寄存器中；重复前面的计算，直到r₀输入后，这时Si寄存器中存的值即为校正子多项式各项的系数。而利用钱式搜索算法计算错误位置多项式/计算错误估值多项式各项时，完成以下操作：先通过第一多路复用器M1把σ_j/ω_k系数存入Si寄存器中，然后选择第一多路复用器M1的输入为0，其后每个时钟周期不断迭代乘以α^j，重复迭代j次后就得到α^j时错误位置多项式或错误估值多项式各项的值。因为校正子多项式为2t项，而错误位置多项式最多为t+1项，错误估值多项式最多为t项，所以只用校正子多项式计算的硬件开销，就可以分时实现钱式搜索算法和错误位置多项式的求值。

为了求取错误位置多项式，本发明采用如下的改进型无逆Berlekamp-Massey算法，该算法与一般Berlekamp-Massey算法相比省去了罗华域GF(2^m)求逆的计算单元，因此可达到简化电路结构的目的：

${\delta }^{(k+1)}=\underset{j=0}{\overset{l\left(k\right)}{\Sigma }}{\mu }_j^{\left(k\right)}{S}_{m0+k-j}---\left(6\right)$

μ^(k+1)(D)＝γ^(k)μ^(k+1)λ^(k)(D)D                   (7)

λ^(k+1)(D)＝Dλ^(k)(D)...if(δ^(k+1)＝0‖2l^(k)＞k)

                                                    (8)

λ^(k+1)(D)＝μ^(k)(D)....if(δ^(k+1)≠0& 2l^(k)≤k)

l^(k+1)＝l^(k)............if(δ^(k+1)＝0‖2l^(k)＞k)

                                                    (9)

l^(k+1)＝k+1-l^(k)........if(δ^(k+1)≠0‖2l^(k)≤k)

γ^(k+1)＝γ^(k)..................if(δ^(k+1)＝0‖2l^(k)＞k)

                                                           (10)

γ^(k+1)＝δ^(k+1)................if(δ^(k+1)≠0‖2l^(k)≤k)

而错误估值多项式求取算法式如下：

ω(x)＝S(x)σ(x)mod x^2t

＝(S₁+S₂x+...S₁₆x¹⁵)(σ₀+σ₁x+...σ₈x⁸)modx¹⁶              (11)

＝σ₀S₁+(σ₀S₂+σ₁S₁)x+...(σ₀S₈+σ₁S₇+σ₂S₆...+σ₇S₁)x⁷

根据上述式(6)～式(10)的改进型无逆Berlekamp-Massey错误位置多项式求取算法和式(11)的错误估值多项式求取算法式，并根据式(11)与式(6)计算方式的相似性，因此在一个实施例中，本发明可采用如图5所示的“错误位置多项式/错误估计值多项式求取多功能模块”，来时分实现错误位置多项式和错误估值多项式的求取。由图5可知，该模块包括9个(即t+1个，t表示本发明所述解码器的最大能纠错误数)第二计算单元，其中各第二计算单元的具体结构可如图6所示，包括T_i寄存器，其输入为校正子多项式的系数S_i，而其输出则送入第二伽罗华域乘法器中；所述第二伽罗华域乘法器的两个输入分别为T_i寄存器的输出、μ_i寄存器的输出，而其输出则为δ_i；所述μ_i寄存器的输入为第二伽罗华域加法器的输出，其输出送入第二伽罗华域乘法器、第三伽罗华域乘法器及第三多路复用器中；所述第三伽罗华域乘法器的两个输入分别为所述μ_i寄存器的输出和γ，而其输出则送入第二伽罗华域加法器中；所述第二伽罗华域加法器的两个输入分别为所述第三伽罗华域乘法器的输出和第四伽罗华域乘法器的输出，而其输出则送入μ_i寄存器中；所述第四伽罗华域乘法器的两个输入分别为δ和λ_i-1，而其输出则送入所述第二伽罗华域加法器中；所述第三多路复用器的两个输入分别为λ_i-1和μ_i寄存器的输出，而其输出则送入λ_i寄存器中；而所述λ_i寄存器的输入为第三多路复用器的输出，而其输出则为λ_i。当该模块用于进行错误位置多项式的计算时，计算所得的错误位置多项式系数σ_j将被保存最终在所述μ_i寄存器中；而当该模块用于进行错误估值多项式的计算时，计算所得的错误估值多项式系数ω_k将被最终保存在所述λ_i寄存器中。

在本发明中，当使用如图2所示的Reed-Solomon解码器，并且当所述“校正子多项式/钱式搜索/错误估计值计算多功能模块”的结构为如图3所示，而所述“错误位置多项式/错误估计值多项式求取多功能模块”的结构为如图5所示时，该解码器的解码过程如下所述：

(1)计算校正子多项式：将接收到的R(x)逐项输入到“校正子多项式/钱式搜索/错误估计值计算多功能模块”中，累积运算，直到最后一项被输入计算后，存在S_i寄存器中的就是校正子多项式的各项系数。判断校正子多项式是否为零，如果为零，则说明收到的R(x)没有错误，解码结束。如果校正子多项式为非零，则进入第(2)步。

(2)错误位置多项式求取：将校正子多项式系数S_i逐项移入到“错误位置多项式/错误估计值多项式求取多功能模块”中，按改进型无逆Berlekamp-Massey算法迭代2t次求取错误位置多项式。如果求取过程中出现错误位置多项式次数高于t，则说明收到的R(x)中有多于8字节的错误，没有办法纠错，解码结束。如果错误位置多项式次数小于等于t，则进入第(3)步。

(3)错误估值多项式求取。保持“错误位置多项式/错误估计值多项式求取多功能模块”中μ_i寄存器中的错误位置多项式系数不变，清除Ti寄存器中的值，然后重新逐项移入校正子多项式系数S_i，逐项计算错误估值多项式的系数ω_i，直到S_t项系数输入计算得到错误估值多项式最高项系数ω_t时，则所求的错误估值多项式各项系数存在λi寄存器中。

(4)通过“校正子多项式/钱式搜索/错误估计值计算多功能模块”钱式搜索错误位置，并判断接受到的R(x)中是否有多于8字节的错误。钱式搜索统计在错误位置多项式在罗华域GF(2^m)中有多少个根，如果求得的根的个数和错误位置多项式的最高阶次不同，则说明收到的R(x)中有多于8字节的错误，没有办法纠错，解码结束。否则进入第(5)步。

(5)利用钱式搜索和Forney算法计算出错误位置的错误值，$\hat{C}\left(x\right)=R\left(x\right)-\hat{E}\left(x\right),$完成解码纠错。