CN1575548A - 用于里德索罗门码的解码方法和解码器 - Google Patents

Abstract

一种反自由Berlekamp－Massey算法的改良，在这种算法中利用具有公共索引(j)的系数来进行偏差(⊿)计算，因而减少了所需要的乘法器数目。该误符量值也可利用具有公共索引(j)的系数来计算，因而也减少了所需要的乘法器的数目。公共的乘法器(60)可被用于两种计算，因而进一步减少了所需要的乘法器数目。

Description

用于里德索罗门码的解码方法和解码器

技术领域

本发明涉及里德索罗门(REED SOLOMON)编码数据的解码方法、为此的解码器、和包括里德索罗门编码数据解码用的解码器的电子装置。

背景技术

在包括光盘(CD)、数字万用盘(DVD)、数字视频广播(DVB)和硬盘驱动器(HDD)的各种各样的系统内，里德索罗门(RS)码被用来纠错和擦除。(N，K)里德索罗门码具有N个符号，在其代码中K个符号是信息符号，该里德索罗门码可用来在代码中改正s个符号擦除和υ个符号错误，这里s+2υ≤N-K。含有错误和擦除的里德索罗门代码，当该擦除的位置已知时，就可通过下列计算来解码：首先计算该代码的校正子(syndrome)，第二从该校正子和擦除位置计算误符(错误和擦除)定位子多项式(errata locator polynomial)，第三计算该误符多项式的根来获得该错误和擦除的位置，第四计算误符求值子多项式(errata evaluator polynomial)，以及第五计算误符求值子多项式的根来获得该错误和擦除的量值。在本技术中众所周知，Berlekamp-Massey(BM)算法或欧几里得算法都可被用来确定误符定位子多项式和误符求值子多项式；而Chien搜索可被用来确定该多项式的根。由Blahut在其文章：“Theory and practice of errorcontrol codes”，R.E. Blahut，Addison-Wesley，1984中提出，误符定位子多项式可通过使BM算法初始化，用擦除定位子多项式和校正子多项式直接计算，以回避对计算Forney校正子的需要，Forney校正子被定义在下述文章中：″On decoding BCH codes″Forney，Jr.. IEEE Trans. Inform. Theory，vol. IT-11，pp549-557，Oct.1965.

根据这种思想，Jyh-Horng Jeng和Trieu-Kien Troung在文章：“On decoding of both errors and erasures of a Reed-Solomon code using an inverse-free Berlekamp-Masseyalgorithm”IEEE Trans.Commun.，vol.4 7，pp.1488-1494，Oct1999中提出一种反自由BM算法以便直接在用来校正错误和擦除的RS解码器中寻求误符定位子多项式，如下所述。

令g(x)为在GF(2^m)上的(N，K)RS码的代码发生器多项式，这里g(x)按其最一般的形式被定义为：

$g\left(x\right)=\underset{j=0}{\overset{N-K-1}{\mathrm{\Π}}}(x-{\mathrm{\α}}^{m(j+q)})---\left(1\right)$

其中α是构建GF(2^m)的原始多项式p(x)的根，而q和m是确定代码的参数。如果我们将接收的RS代码矢量表示成 r＝[r₀，r₁，...，r_n-1]，则众所周知，该被定义为：

$S\left(x\right)=\underset{n=1}{\overset{N-K}{\mathrm{\Σ}}}{S}_n{x}^n---\left(2\right)$

的校正子多项式S(x)就可被计算如下：

$S_n=\underset{i=0}{\overset{N-1}{\mathrm{\Σ}}}{r}_1\·{\mathrm{\α}}^{m(n+q)i}---\left(3\right)$

如果Zi和Xi分别是 r内的第i个已知擦除位置和第i个错误位置，则擦除定位子多项式就被定义为：

$\mathrm{\Λ}\left(x\right)=\underset{j=1}{\overset{s}{\mathrm{\Π}}}(1-Z_{j}x)=\underset{j=0}{\overset{s}{\mathrm{\Σ}}}{\mathrm{\Λ}}_j{x}^j---\left(4\right)$

其中Λ₀＝1。Λ(x)是在相反擦除位置上为0的多项式。在相反的错误和擦除位置上为0的误符定位子多项式被定义为：

$\mathrm{\τ}\left(x\right)=\left[\underset{i=1}{\overset{v}{\mathrm{\Π}}}(1+X_{1}x)\right]\left[\underset{n=1}{\overset{s}{\mathrm{\Π}}}(1+Z_{n}x)\right]=\underset{j=0}{\overset{v+s}{\mathrm{\Σ}}}{\mathrm{\τ}}_j{x}^j---\left(5\right)$

反自由BM算法(Inverse-Free BM algorithm)被用来从校正子多项式S(x)和擦除定位子多项式Λ(x)确定该误符定位于多项式τ(x)，它被按下述方法确定：

步骤1.首先定义：

k＝0           l⁽⁰⁾＝0       γ⁽⁰⁾＝1         (6)

λ⁽⁰⁾(x)＝Λ(x)      μ⁽⁰⁾(x)＝Λ(x)          (7)

其中k是一迭代计数器。

步骤2.设k＝k+1。如k超过可被该代码校正的错误的最大数目，即如k≥N-K-s则停止。否则，确定

${\mathrm{\δ}}^{\left(k\right)}=\underset{j=0}{\overset{N-K}{\mathrm{\Σ}}}{\mathrm{\μ}}_j^{(k-1)}{S}_{k+s-j}---\left(8\right)$

δ^(k)被叫做偏差。

步骤3.对下述公式进行计算：

步骤4。返回步骤2.

误符定位子多项式τ(x)可通过使μ(x)归一化的方法获得如下：

τ(x)＝μ(x)/μ₀其中μ₀是μ(x)中x⁰的系数，Chien搜索此后可用来决定误符位置。该误符求值子多项式A(x)被定义为：

            A(x)≡S(x)τ(x)modx^N-K-I    (10)此后被用来计算误符的量值。

如Jeng和Troung所描述的那样，该误符(errata)的量值由下式给定

${\tilde{w}}_r=\frac{A\left({\tilde{Z}}_r^{-1}\right)}{{\tilde{Z}}_r^{-(1+q)m}{\mathrm{\τ}}^{\′}\left({\tilde{Z}}_r^{-1}\right)},$ 1≤r≤s+v，其中 是第r个误符位置， 是在 $x={\tilde{Z}}_r^{-1}$ 时τ(x)相对于x的导数。

反自由BM算法的优点在于可避免对Forney校正子和误符定位子多项式的分开计算。其缺点是：与偏差计算有关的乘法器的数目是奇偶符号数的平方的函数，这样就暗示在用硅来实现解码器的面积方面的巨大成本。

发明公开

本发明的目的在于为里德索罗门编码数据提供一种改进的解码方法和解码器。

按照本发明的第一方面，提供了一种解码里德索罗门编码数据的方法，其中偏差计算包括第一乘积项的求和，这里每个第一乘积项都包括具有第一公共索引的系数的第一乘积。

按照根据多项式μ(x)F(x)和E(x)的系数计算偏差δ的方法，其中只有具有公共索引的系数才被相乘在一起，在计算误符定位子多项式τ(x)时所涉及的伽罗瓦域(GF)乘法器的数目是奇偶符号数的线性函数。因而解码器实现的复杂性可被减小，而且对于解码所需要的时钟周期数也被减少。

按照本发明的第二方面，提供了一种解码里德索罗门编码数据的方法，其中误符量值的计算包括第二乘积项的求和，这里每个第二乘积项都包括具有第二公共索引的系数的第二乘积。

按照根据多项式系数μ(x)F(x)和E(x)计算误符量值的方法，其中只有具有公共索引的系数才被相乘在一起，在计算误符量值时所涉及的GF乘法器的数目是奇偶符号数的线性函数。因而解码器实现的复杂性可被减小，而且对于解码所需要的时钟周期数也被减少。

此外，在计算第一和/或第二乘积项时使用环形结构就可使计算本身与在该算法中所涉及的迭代数无关。

按照本发明的第三方面，提供了一种解码里德索罗门编码数据的解码器，包括按照本发明的第一或第二方面的运算装置。

按照本发明的第四方面，提供了按照权利要求6所述的一种解码里德索罗门编码数据的解码器。

按照本发明的第四方面，提供了一种电子装置，它包括按照本发明第三或第四方面所述的解码器。该电子装置可以是一包括解码器的集成电路。电子装置可以是，例如，一从存储介质，如光学存储盘或磁学存储盘，读取数据的设备。该电子装置可以是，例如，一接收传送的信号，如无线信号的设备。

按照根据具有公共索引的系数的乘积计算偏差和错误量值的方法，也可使用用于计算偏差的乘法器来计算错误的量值，进一步减少解码器的复杂性。

新的多项式F^(k)(x)被定义为：

$F^{\left(k\right)}\left(x\right)=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{F}_j^{\left(k\right)}{x}^j---\left(11\right)$

其中一般系数(generic coefficient)F_j ^(k)为：

$F_j^{\left(0\right)}=S_{(s-j)\mathrm{mod}(N-K)+1}---\left(12\right)$

        F^(k)(x)＝xF^(k-1)(x)mod(x^N-K+1)    (13)

F^(k)(x)的方程(13)代表F^(k-1)(x)的循环移位，使能多项式E^(k)(x)被定义为：

$E^{\left(k\right)}\left(x\right)=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{E}_j^{\left(k\right)}{x}^j---\left(14\right)$

其中该一般系数E_j ^(k)为：

        E^(k)(x)＝xE^(k-1)(x)mod(x^N-K+1)    (16)

E^(k)(x)的方程(16)代表E^(k-1)(x)的循环移位。在解码器中两变量F^(k)(x)和E^(k)(x)被用作两环形寄存器，像在方程(12)和(15)中那样被初始化后，环形寄存器将按照方程(13)和(16)在每个时钟周期上发生移位。在方程(8)中定义的偏差是作为F^(k)(x)和E^(k)(x)的函数来计算的：

${\mathrm{\δ}}^{\left(k\right)}=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{\mathrm{\μ}}_j^{(k-1)}{F}_j^{(k-1)}{E}_j^{(k-1)}---\left(17\right)$

在计算δ^(k)时GF乘法总是涉及相同索引的系数，即第j个系数，因而该GF乘法器的数目就等于N-K。在现行技术中按照方程(8)计算δ^(k)时，该GF乘法涉及不同的索引，即第j和第(k+s-j)，该后面的索引是与迭代数有关的；因此按照现行技术要求的GF乘法器数就等于(N-K)²。

为了计算误符量值，代替在方程(10)中定义的A(x)，用下式定义了一新的变量B(x)：

$B\left(x\right)=\underset{t=1}{\overset{N-K}{\mathrm{\Σ}}}{B}_t{x}^t=S\left(x\right)\mathrm{\μ}\left(x\right)\mathrm{mod}{x}^{N-K+1}---\left(18\right)$

其中B(x)的一般系数B_t为：

$B_t=\underset{j=0}{\overset{t-1}{\mathrm{\Σ}}}{\mathrm{\μ}}_j^{(N-K-s)}{S}_{t-j}---\left(19\right)$

通过如下那样对F^(k)(x)和E^(k)(x)进行初始化：

$F_j^{\left(0\right)}=S_{(-j)\mathrm{mod}(N-K)+1}---\left(20\right)$

则B(x)的每个系数B_t就被计算如下：

$B_t=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{\mathrm{\μ}}_j^{(N-K-s)}{F}_j^{\left(t\right)}{E}_j^{\left(j\right)}---\left(22\right)$

在解码器中，将循环移位应用到F^(k)(x)和E^(k)(x)上，就像在方程(13)和(16)中对B(x)的每个系数B_t那样。

在计算B_t时，GF乘法总是涉及相同索引的系数，即第j个系数，因而在硬件执行过程中所要求的GF乘法器的数目就等于N-K。在按照方程(10)对误符求值子多项式A(x)进行现行技术的计算时，该GF乘法就涉及不同的索引，即第j和第k+s-j，后面的索引是与迭代数有关的；因此按照现行技术该GF乘法器的数目就等于(N-K)²。此外在不同时间计算B(x)时可使用与计算偏差δ^(k)所使用的相同的资源。

从B(x)，该误符量值被计算成：

${\tilde{W}}_r=\frac{B\left({\tilde{Z}}_r^{-1}\right)}{{\tilde{Z}}_r^{-(1+q)m}{\mathrm{\μ}}^{\′}\left({\tilde{Z}}_r^{-1}\right)},1\≤r\≤s+\mathrm{\υ}---\left(23\right)$

其中

是第r个误符位置， 是在 $X={\tilde{z}}_r^{-1}$ 上计值时μ(x)相对于x的导数。

附图简介

现在将参考下述附图通过例子对本发明进行描述：

图1是计算δ^(k)和B(x)的电路的框图，

图2是按照本发明的改进的BM解码算法的流程图，

图3是编码装置的框图，

图4是说明里德索罗门解码的三个主要步骤的流程图，

图5图示出里德索罗门解码器的管线运作，它包括改进的BM解码算法，

图6是包括里德索罗门解码器的电子装置的框图。

完成本发明的方式

参考图1，该电路包括环形移位寄存器10，20分别用来存储F^(k)(x)和E^(k)(x)，该E^(k)(x)寄存器20在其反馈路径上包括一反相器30。存在有一寄存器40用来存储μ(x)。来自F^(k)(x)寄存器相应级的输出在具有设定为逻辑0的控制线55的相应多路复用器50中被多路复用。来自E^(k)(x)寄存器20的相应级的输出起着相应多路复用器50的控制线的作用。来自相应多路复用器50的输出在相应乘法器60中与来自μ(x)寄存器40的相应级的输出相乘。相应乘法的积在加法器70中求和，并经多路复用器51传送到存储B(x)的寄存器90和经多路复用器52传送到存储偏差δ的寄存器80。存在有一控制装置56，用来控制该多路复用器51和52，以便确定该加法器70的输出是传送到存储偏差δ的寄存器80或是传送到存储B(x)的寄存器90。

参考图2所示流程图，按照本发明的改进BM算法(R-BM)如下所述，每个R-BM步骤都是在一单个时钟周期内完成的。方框110代表算法的开始。在方框112，对s的值，擦除的数目，进行检验。如果s超出编码的校正能力则错误或擦除就不能被校正，而且该算法就在方框114被终止，否则流程就进行到方框120。

在方框120进行该R-BM的步骤1，在这步骤中将按方程(6)和(7)对在步骤2中使用的变量k，l，y和λ(x)进行初始化。这些变量在图1中没作说明。在寄存器40中对μ(x)按照方程(7)进行初始化。在寄存器10和20中分别按照方程(12)和(15)对F^(k)(x)如E^(k)(x)进行初始化。

然后在方框130再次检验s的值，擦除数。如果该s值是这样的大，以致不能校正错误，而只能校正擦除，则当擦除定位子多项式Λ(x)足够大而误符定位子多项式τ(x)不需要计算时，该R-BM算法就继续到下述的R-BM步骤3。不然，当s足够小以致能校正错误时则就到方框140进行R-BM步骤2，以确定误符(擦除和错误)定位子多项式τ(x)。在R-BM步骤2，该迭代计数器k被增大。按照方程(17)计算偏差δ并将其存储进寄存器80中。变量μ(x)，λ(x)，l和y将按照方程(9)进行更新。按照方程(13)和(16)分别在寄存器10和20中进行变量F^(k)(x)和E^(k)(x)的右移位。

对于每个k值迭代地重复R-BM步骤2并在每次迭代之后在方框150对k值进行检验。如果k超出该编码的错误校正能力，在顾及已知的擦除数s时，则就到方框160进行步骤3，否则进行R-BM步骤2的下一次迭代。R-BM步骤2迭代的结果就是寄存器40内的多项式μ(x)。在R-BM步骤3，该下计数器bcnt被初始化为N-K-1。分别按照方程(20)和(21)在寄存器10和20中对F^(k)(x)和E^(k)(x)进行初始化。然后该算法进行到在方框170的R-BM步骤4。

在R-BM步骤4，按照方程(22)，在寄存器90中计算B(x)的系数B_t，分别按照方程(13)和(16)在寄存器10和20中使F^(k)(x)和E^(k)(x)移位，和使bcnt减小。对bcnt的每个值迭代地重复R-BM步骤4，在每次迭代之后在方框180检验bcnt的值。如果bcnt已达到0，则所有B(x)的系数都已被计算，该算法就在方框190停止，否则就进行R-BM步骤4的下一次迭代。

在编解码器200中实施图1所示电路，如图3所示，该编解码器包括里德索罗门解码器210，两个双端口RAM 220，225和一对接于该解码器和RAM之间的控制块230。第一RAM 220具有保持2数据帧的能力，而第二RAM 225可保持一数据帧，一数据帧等于一里德索罗门代码。当该解码器210运行该校正子和该R-BM算法计算时，该第二RAM225存储数据。该第二RAM 225服务于两个目的。它允许用户编程(借助一串行编程接口；未画出)，按照其顺序从该解码器200输出该解码的数据帧，也就是，字节0到N-I或字节N-I到0。在被传送之前它还可使数据帧延迟，这就使校正信号能与指示接收的代码是否成功被解码的数据帧一起传送。

编解码器200是以一管线结构按三个主要阶段实施的，如图4所示。存在于接收代码中的擦除数s在解码过程开始时是已知的。在第一阶段中该校正子多项式S(x)和擦除定位子多项式Λ(x)可利用已知方法来计算。阶段1是在N个时钟周期内运行的。第二阶段是如上所述的R-BM算法，参考图2。第二阶段进行的时间随存在于接收代码中的擦除数而变化，并在没有擦除而只有错误要校正时具有一最大值2(N-K)+2，而在没有错误而只有擦除要校正时具有一最小值(N-K)+2。第三阶段是著名的Chien搜索，在这阶段将计算μ(x)的根和计算的误符的量值，所述的根与该误符定位子多项式τ(x)的根相同。阶段3进行的时间为N个时钟周期。

该3-阶段的编解码器200被设计成具有一管线结构，使得在任何时间该编解码器200都能处理3个接收代码。该管线结构的计时图示于图5中。当阶段1在第n帧运作时，阶段2和3将分别在第(n-1)和(n-2)帧上运作。

通过编解码器200的等待时间取决于代码的大小、在接收代码中的奇偶位数和擦除与错误数。它在时钟周期内的值由公式2N+2(N-K)-s给定。例如，对于DVB的标准RS码(204，188)来说，最长的等待时间为440个时钟周期，而最短的等待时间为424个时钟周期。

参考图6，在这里图示出了一电子装置，用来从一光学数据存储盘提取里德索罗门编码的声频和视频数据，并将提取的数据转变成声频和视频信号。该装置300包括一读取装置310用来从一光学数据存储盘读取里德索罗门编码数据。按照本发明第三方面，与该读取装置的输出偶联的是一里德索罗门解码器320，用来对被该读取装置310读取的里德索罗门编码数据进行解码。与里德索罗门解码器320的输出偶联的是一反编排装置(deformating means)330用来从解码数据提取声频和视频数据。与反编排装置330输出偶联的是一模-数转换装置340，用来将声频和视频数据转变成模拟的声频和视频信号并将该模拟声频和视频信号提供在输出端350上。该读取装置310，里德索罗门解码器320，反编排装置330以及模-数转换装置340的运作都受处理装置360的控制，该处理装置还可控制用户界面(未画出)。

工业实用性

本发明可用于使用里德索罗门码的数字存储和通信设备。

Claims (7)

1.里德索罗门编码数据的解码方法，其中偏差的计算包括第一乘积项的求和，这里每个第一乘积项包括具有第一公共索引的系数的第一乘积。

2.按权利要求1的里德索罗门编码数据的解码方法，其中所述第一乘积项的总和为 $\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{\mathrm{\μ}}_j^{(k-1)}{F}_j^{(k-1)}{E}_j^{(k-1)},$ 具有第一公共索引的系数的第一乘积为 ${\mathrm{\μ}}_j^{(k-1)}{F}_j^{(k-1)}{E}_j^{(k-1)},$ 而第一公共索引为j，这里k为迭代计数器，N是该编码数据中的符号数，K是该编码数据中的信息符号数，s是该编码数据中的擦除数，S_n是该编码数据中的校正子，这里n＝1到N-K，而且其中

$F^{\left(k\right)}\left(x\right)=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{F}_j^{\left(k\right)}{x}^j,$

$F_j^{\left(0\right)}=S_{(s-j)\mathrm{mod}(N-K)+1},$

F^(k)(x)＝xF^(k-1)(x)mod(x^N-K+1)，

$E^{\left(k\right)}\left(x\right)=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{E}_j^{\left(k\right)}{x}^j,$

如果j≤s， $E_J^{\left(0\right)}=1,$ 否则为0，以及

E^(k)(x)＝xE^(k-1)(x)mod(x^N-K+1)。

3.里德索罗门编码数据的解码方法，其中误符量值计算包括第二乘积项的求和，其中每个第二乘积项包括具有第二公共索引的系数的第二乘积。

4.按权利要求3的里德索罗门编码数据的解码方法，其中第二乘积项的总和为 $\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{\mathrm{\μ}}_j^{(N-K-s)}{F}_j^{\left(i\right)}{E}_j^{\left(j\right)},$ 具有第一公共索引的系数的第二乘积为 ${\mathrm{\μ}}_j^{(N-K-s)}{F}_j^{\left(i\right)}{E}_j^{\left(i\right)},$ 而第二公共索引为j，这里i为误符量值的索引，N是该编码数据中的符号数，K是该编码数据中的信息符号数，s是该编码数据中的擦除数，S_n是该编码数据中的校正子，这里n＝1到N-K，而且其中

$F^{\left(k\right)}\left(x\right)=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{F}_j^{\left(k\right)}{x}^j,$

$F_j^{\left(0\right)}=S_{(-j)\mathrm{mod}(N-K)+1},$

F^(k)(x)＝xF^(k-1)(x)mod(x^N-K+1)，

$E^{\left(k\right)}\left(x\right)=\underset{j=0}{\overset{N-K-1}{\mathrm{\Σ}}}{E}_j^{\left(k\right)}{x}^j,$

如果j≤s， $E_J^{\left(0\right)}=1,$ 否则为0，以及

E^(k)(x)＝xE^(k-1)(x)mod(x^N-K+1)。

5.一种里德索罗门编码数据的解码器，包括按照权利要求1，2，3或4中的任一项所述进行运算的装置。

6.里德索罗门编码数据的解码器，包括按照权利要求1或2结合权利要求3或4所述进行运算的装置，还包括产生第一乘积项而且也产生第二乘积项的乘法器装置。

7.一种电子装置，包括在权利要求5或6中所述的解码器。

Images