迭代链接码解码电路以及使用该电路的编码/解码系统

摘要

本发明提供一种能够减小电路尺寸和提高错误校正能力的迭代链接码解码电路。通过传输路径从第一级内解码器接收的已编码数据被解码，其中已解码数据被输出到第一级去交织器，并且对应于已解码数据的第一级内码校正子系数被输出到第二级内解码器。第一级去交织器对已解码数据去交织，并且将去交织的数据输出到第一级外解码器。第一级外解码器对去交织的数据解码并且将已解码数据输出到第一级交织器，其中第一级内码修正校正子系数被导出并且输出到第二级内解码器。第一级交织器对已解码数据交织并且将交织的数据输出到第二级内解码器。

说明书

技术领域

本发明涉及迭代链接码解码电路以及使用该电路的编码/解码系统。并且更具体而言，本发明涉及一种迭代链接BCH(博斯-乔赫里-霍克文黑姆)解码电路，其中称作内码和外码的两种码被链接。

背景技术

如图12所示，链接BCH(博斯-乔赫里-霍克文黑姆)解码电路能够通过应用迭代解码方案来提高纠错能力。

在图12中，输入数据D_in首先被一个外编码器100编码。已编码数据D_enc-outer被一个交织器200交织，然后被一个内编码器300编码。从内编码器300输出的已编码数据D_enc-inner被输出到传输路径400。

具有通过传输路径400添加的错误的已编码数据D_rev被一个内解码器500解码，并且错误被校正。已解码数据D_dec-inner被一个去交织器600去交织，然后被一个外解码器700解码，并且没有被内解码器500校正的错误被校正。

图13是表示传统的N次迭代链接BCH解码器的结构的框图。通过未示出的传输路径被接收的已编码数据D_rev被第一级内解码器500-1解码。已解码数据D_inner-1被第一级去交织器600-1去交织，然后被第一级外解码器700-1解码。已解码数据D_outer-1再次被第一级交织器200-1交织，然后被第二级内解码器500-2解码。

已解码数据D_inner-2再次被第二级去交织器600-2去交织，然后被第二级外解码器700-2解码。已解码数据D_outer-2再被第二级交织器200-2交织。上述操作被迭代N次以便逐渐校正传输错误。

图14表示传统BCH解码器的结构。BCH解码器包括一个校正子计算部分10、错误定位多项式导出部分20、错误位置计算部分30、接收码字存储部分40和错误校正部分50。

为了解释BCH解码原理，BCH(255，215)码被认为是一个例于。这个码具有每个码字5比特的错误校正能力。

校正子计算部分10为由以下表达式定义的校正子多项式S(z)计算系数S_i：

S(z)＝S₁+S₂z²+…+S₁₀z¹⁰           …(1)

校正子系数S_i由以下表达式定义：

   S_i＝Y(αⁱ)

     ＝Y₀+Y₁αⁱ+Y₂α²ⁱ+Y₃α³ⁱ+…+Y₂₅₄α²⁵⁴ⁱ

    i＝1，…，5                   …(2)

其中Y(x)是一个接收多项式并且α是素元。

接收多项式Y(x)的每个系数对应于通过传输路径接收的已编码数据D_rev的每个比特。如果接收多项式Y(x)不含有错误，则校正子系数成为全零。

错误定位多项式导出部分20采用欧几里得算法导出错误定位多项式σ(z)，并且将它输出到错误位置计算部分30。错误定位多项式σ(z)由以下表达式表示：

σ(z)＝σ₀+σ₁z+… +σ₅z⁵             …(3)

错误位置计算部分30根据错误定位多项式计算错误位置。

在GF(256)的所有域元素中求错误定位多项式σ(z)的值的吉川(Chien)搜索算法可以被用来找到错误位置和数值。如果σ(zⁱ)是错误定位多项式σ(z)的根，则根的幂表示接收码多项式Y(x)的错误位置。

错误校正部分50根据来自错误位置计算部分30的错误位置输入来校正存储在在接收码字存储部分40中的接收的码字，并且将校正的码字输出到外部。

在相关领域的技术中，采用具有对于内码和外码的可比较编码率的BCH码。这种BCH码在T.Mizuochi等人的“Transparentmultiplexer featuring super FEC for optical Transportnetworking(用于光传输网的透明多路复用器特征高级FEC)”(SubOptic 2001，P4.2.3，2001)以及Omar AIT SAB的“FECcontribution in submarine transmission systems(在海底传输系统中FEC的贡献)”(SubOptic 2001，P4.2.6，2001)中被描述。

在如上所述的传统迭代链接BCH解码电路中，如果接收的码字的平均错误数大于或者等于可校正比特数，则错误难以用BCH码校正。因为外解码器具有可以与内解码器的编码率相比的编码率，所以当内解码器难以校正错误时，外解码器也难以校正错误。

此外，在传统的迭代链接BCH解码器中，具有可比较的编码率的外解码器和内解码器必须具有相同的电路结构，这带来电路尺寸变大这样一个问题。特别地，由于欧几里得算法或者吉川搜索算法而增加了电路尺寸。

发明内容

为了解决上述问题，本发明提供一种具有减小的电路尺寸以及提高的错误校正能力的迭代链接码解码电路，以及采用这种电路的编码/解码系统。

本发明的迭代链接码解码电路对于使用具有高编码率的内码和具有低编码率的外码来对一个链接码进行解码，其中编码率由(码字长度-冗余校验长度)/(码字长度)表示。

本发明的另一个迭代链接码解码电路包括一个用于对通过传输路径接收的已编码数据进行解码和校正数据错误的内解码器、用于对于由内解码器解码的数据进行去交织的去交织器、用于对去交织的数据进行解码和校正数据错误的外解码器以及一个用于对外解码器解码的数据进行交织的交织器，其中内解码器、去交织器、外解码器和交织器被布置在N(N是一个正整数)个级中。迭代链接码解码电路采用链接外码和内码这两个码的链接码。内解码器对具有高编码率的内码进行解码，并且外解码器对于具有低编码率的外码进行解码。

本发明的编码/解码系统包括用于对链接外码和内码这两个码的链接码进行编码的编码设备以及一个解码设备，该解码设备包括用于对链接码进行解码的迭代链接码解码电路。编码设备包括用于对具有高编码率的内码进行编码的内编码器、用于对具有低编码率的外码进行编码的外编码器，并且迭代链接码解码电路包括用于对具有高编码率的内码进行解码的内解码器和用于对具有低编码率的外码进行解码的外解码器。

本发明的另一个编码/解码系统包括一个用于对链接外码和内码这两个码的链接码进行编码的编码设备、用于对通过传输路径从编码设备接收的已编码数据进行解码和校正数据错误的内解码器、用于对已解码数据进行去交织的去交织器、用于对去交织的数据进行解码和校正数据错误的外解码器以及用于对外解码器解码的数据进行交织的交织器，其中内解码器、去交织器、外解码器和交织器被布置在N(N是一个正整数)个级中。迭代链接码解码电路采用链接外码和内码这两个码的链接码。编码设备具有用于对具有高编码率的内码进行编码的内编码器以及用于对具有低编码率的外码进行编码的外编码器，并且内解码器对于具有高编码率的内码进行解码，外解码器对于具有低编码率的外码进行解码。

也就是说，本发明的迭代链接码解码电路采用具有高编码率的内码和具有低编码率的外码，从而减小电路尺寸并且提高错误校正能力。

用于本发明的迭代链接码解码电路的内解码器起具有链接码的相等编码率的传统链接码的内解码器具有更高的编码率或者更高的错误校正能力。在下文中链接码的编码率被表示为链接编码率。

因此，本发明的内解码器能够用传统技术的内解码器难以用来校正错误的差的输入错误率来校正错误。外解码器只校正没有被内解码器校正的剩余错误，从而即使本发明的外解码器具有低的错误校正能力或者低的编码率，也不会有问题。

由于本发明的外解码器具有低的编码率，所以错误位置可以被使用ROM(只读存储器)从校正子系数中直接获得。

在这种情况下，本发明的外解码器不需要利用欧几里得算法的错误定位多项式导出部分和利用吉川搜索算法的错误位置计算部分。另一方面，传统技术的内解码器和外解码器中的每一个都需要所述两个部分，所以本发明带来了减小的电路尺寸。

因此，本发明能够提供具有与传统技术相比减小的电路尺寸和提高的错误校正能力的迭代链接码解码电路。

本发明的第一特征是由具有低编码率的外解码器使用ROM获得错误位置和内码修正校正子系数。

在这种情况下，本发明的外解码器不需要利用欧几里得算法的错误定位多项式导出部分和利用吉川搜索算法的错误位置计算部分，传统技术的外解码器需要所述两个部分，所以本发明带来了减小的电路尺寸。

本发明的第二特征是在第二级和随后的级中的内解码器根据在前面级的内解码器的多项式系数S与在前面级的外解码器计算的内码修改多项式系数SR相加的结果来解码。在这种情况下，不像传统技术那样需要来自接收多项式的校正子系数，从而在本发明的第二级和随后级的内解码器具有减小的电路尺寸。

本发明的第三特征是具有高编码率的内码和具有低编码率的外码被采用来实现高的错误校正能力。如果接收的码字的平均错误数大于可校正比特数，则BCH解码器难以校正错误。用于本发明的迭代链接码解码电路的内解码器比传统技术的具有可比较链接编码率的内解码器具有更高的编码率或者更多的可校正比特。

因此，本发明的内解码器能够用传统技术的内解码器难以校正错误的差的输入错误率来校正错误。本发明的外解码器只校正内解码器没有校正的剩余错误，从而即使错误校正能力低，也不会存在问题。

一方面，由于传统技术的外解码器具有几乎等于内解码器的编码率，所以如果错误难以被内解码器校正，则错误也难以由外解码器校正。

本发明的迭代链接码编码电路将被在下面描述，以两维BCH码作为例子。例如，N次迭代链接BCH解码电路被采用，其中交织/去交织的深度是L，内码的码长度是C_inner比特，内码的伽罗瓦域本原多项式阶数是M_inner，内码的每个码字的可校正比特数是T_inner，外码的码长度是C_outer比特，外码的伽罗瓦域本原多项式阶数是M_outer，外码的每个码字的可校正比特数是T_outer比特，并且迭代数是N。

在这种情况下，假设内码的编码率是RA_inner并且外码的编码率是RA_outer，链接码的编码率RA由以下表达式表示：

RA_inner＝C_inner/[C_inner-(T_inner×M_inner)]      …(4)

RA_outer＝C_outer/[C_outer-(T_outer×M_outer)]      …(5)

     RA＝RA_inner×RA_outer

       ＝{C_inner/[C_inner-(T_inner×M_inner)]}

       ×{C_outer/[C_outer-(T_outer×M_outer)]}    …(6)

上述迭代链接BCH解码电路采用具有高编码率RA_inner的内码和具有低编码率RA_outer的外码来减小电路尺寸并且提高错误校正能力。

对于本发明的外解码器的情况是，如果编码率RA_outer低(或者可校正比特数少)，则错误位置可以被采用ROM从校正子系数直接获得。采用ROM获得错误位置的这点被在H.Okano的“A ConstructionMethod of High-Speed Decoders Using ROM’s for Bose-Chaudhuri-Hocquenghem and Reed-Solomon Codes(使用ROM用于博斯-乔赫里-霍克文黑姆和里德-所罗门码的高速解码器的构建方法)”(IEEE trans.Comput.第C-6卷，第10期，1987年10月)中描述。

附图说明

图1是表示根据本发明一个实施例的迭代链接BCH解码电路的结构的框图；

图2是表示图1的第一级内解码器的结构的框图；

图3是表示图1的第二级内解码器的结构的框图；

图4是表示图1的第一级外解码器的结构的框图；

图5是表示根据本发明一个实施例的迭代链接BCH解码电路的结构的框图；

图6是表示由第一级到图5的第三级去交织器的格式转换例子的表；

图7是表示由图5的第一级和第二级交织器的格式转换例子的表；

图8是表示根据本发明另一个实施例的迭代链接BCH解码电路的结构的框图；

图9是表示图8的第一级内解码器的结构的框图；

图10是表示图8的第二级内解码器的结构的框图；

图11是表示图8的第一级外解码器的结构的框图；

图12是表示传统的迭代链接BCH解码电路的结构的框图；

图13是表示传统的N次迭代链接BCH解码电路的结构的框图；以及

图14是传统的BCH解码器的结构。

具体实施方式

现在参考附图来描述本发明的优选实施例。图1是表示根据本发明一个实施例的迭代链接BCH解码电路的结构的框图。根据本发明这个实施例的迭代链接BCH解码电路包括第一级到第N级内解码器1-1到1-N、第一级到第N级去交织器2-1到2-N、第一级到第N级外解码器3-1到3-N以及第一级到第(N-1)级交织器4-1到4-(N-1)。

根据本发明这个实施例的迭代链接BCH解码电路中的编码率由RA_inner×RA_outer表示(链接码的编码率是RA)，其中RA_inner是内码的编码率，而RA_outer是外码的编码率。

第一级到第N级外解码器3-1到3-N使用ROM根据校正子系数计算错误位置，从而利用欧几里得算法的错误定位多项式导出部分以及利用吉川搜索算法的错误位置计算部分可以被省去。

当外解码器校正错误时，用于前面级的内解码器的输出数据的校正子系数与用于后面级的内解码器的输入数据的校正子系数被改变。校正子系数中的变化被称作内码修正校正子系数SR。

内码修正校正子系数SR可以被从外解码器检测的错误位置中导出。第一级到第(N-1)级外解码器3-1到3-(N-1)使用ROM直接从外解码器的校正子系数中获得用于下一级的内码修正校正子系数SR。

在第二级以及随后的级中的第二级到第N级内解码器1-2到1-N中的每一个通过将对应于前面级中的内解码器的输出数据的校正子系数与由前面级中的外解码器计算的校正子系数SR相加来计算对应于内解码器的输入数据的校正子系数。在这种情况下，与有关技术不同，不需要根据输入数据来计算校正子系数，从而在第二级和随后级中的内解码器的电路结构被减小。

下面来描述迭代链接BCH解码电路的操作。首先，在第一级，第一级内解码器1-1对通过传输路径接收的已编码数据D_rev进行解码，并且将已解码数据D_inner-1输出到第一级去交织器。同样，第一级内解码器1-1将对应于已解码数据D_inner-1的第一级内码校正子系数S_inner-1输出到第二级内解码器1-2。

第一个去交织器2-1对已解码数据D_inner-1进行去交织，并且将去交织的数据D_deint-1输出到第一级外解码器3-1。第一级外解码器3-1对去交织的数据D_deint-1进行解码并且将已解码的数据D_outer-1输出到第一级交织器4-1。同样，第一级外解码器3-1导出第一级内码修正校正子系数SR_inner-1，并且将它输出到第二级内解码器1-2。第一个交织器4-1对已解码数据D_outer-1进行交织，并且将交织的数据D_int-1输出到第二级内解码器1-2。

在第二级，第二级内解码器1-2根据第一级内码校正子系数S_inner-1和第一级内码修正校正子系数SR_inner-1对交织的数据D_int-1进行解码，并且将已解码数据D_inner-2输出到第二级去交织器2-2。同样，第二级去交织器1-2将对应于已解码数据D_inner-2的第二级内码校正子系数S_inner-2输出到第三级内解码器1-3。

第二级去交织器2-2对已解码数据D_inner-2进行去交织，并且将去交织的数据D_deint-2输出到第二级外解码器3-2。第二级外解码器3-2对去交织的数据D_deint-2进行解码，并且将已解码数据D_outer-2输出到第二级交织器4-2。同样，第二级外解码器3-2导出第二级内码修正校正子系数SR_inner-2，并且将它输出到第三级内解码器1-3。第二级交织器4-2对已解码数据D_outer-2进行交织，并且将交织的数据D_int-2输出到第三级内解码器1-3。

在第三级到第(N-1)级的电路中的每一个执行与第二级中的每个电路相同的处理。

在最后的级中，第N级内解码器1-N根据第(N-1)级内码校正子系数S_inner-(N-1)和第(N-1)级内码修正校正子系数SR_inner-(N-1)对交织的数据D_int-(N-1)进行解码，并且将已解码数据D_inner-N输出到第N级去交织器2-N。同样，第N级去交织器2-N对已解码数据D_inner-N进行去交织，并且将去交织的数据D_deint-N输出到第N级外解码器3-N。第N级外解码器3-N对去交织的数据D_deint-N进行解码，并且输出链接码解码数据D_correct。

图2是表示图1的第一级内解码器的结构的框图。在图2中，第一级内解码器1-1包括一个校正子计算部分11-1、一个错误定位多项式导出部分12-1、一个错误位置计算部分13-1、一个接收码字存储部分14-1和一个错误校正部分15-1。

校正子计算部分11-1为一个由下式定义的校正子多项式SI(z)计算系数SI_i(i＝1，…，2*T_inner)：

SI(z)＝SI₁z+SI₂z²+…+SI_jz^j

    j＝2*T_inner                     …(7)

校正子系数SI_i由下式定义：

  SI_i＝Y_inner(αⁱ)

     ＝Y₀+Y₁(α_inner)ⁱ+Y₂(α_inner)²ⁱ+…+Y_k(α_inner)^ki

    i＝1，…，2*T_inner

    k＝C_inner-1

其中，Y_inner(x)是接收多项式，并且是α_inner用于伽罗瓦域的素元。

接收多项式Y_inner(x)的每个系数对应于通过传输路径接收的已编码数据D_rev的每个比特。校正子系数SI_i是伽罗瓦域中的一个元，并且由M_inner比特的宽度表示。如果通过传输路径接收的已编码数据D_rev不含有错误，则校正子系数成为全零。计算的校正子系数SI_i被输出到错误定位多项式导出部分12-1。

同样，多项式计算部分11-1将用于第一级内解码器1-1解码的数据D_inner-1的校正子系数作为第一级内码校正子系数S_inner-I,i(i＝1，…，2*T_inner)输出到第二级内解码器1-2。如果接收多项式Y_inner(x)中的错误小于或等于错误可校正比特数，则错误都被校正，并且零被输出作为第一级内码校正子系数S_inner-1，i。如果接收多项式Y_inner(x)中的错误大于错误可校正比特数，则错误没有被校正，并且通过传输路径接收的已编码数据D_rev被直接输出作为已解码数据D_inner-1，从而由校正子计算部分11-1导出的校正子系数SI_i被输出作为第一级内码校正子系数S_inner-1，i。错误位置计算部分13-1判定错误是否是可校正的，并且所述判定结果被输入到校正子计算部分11-1。

错误定位多项式导出部分12-1采用欧几里得算法根据校正子系数SI_i(i＝1，…，2*T_inner)来导出一个错误定位多项式σ_inner(z)，并且将它输出到错误位置计算部分13-1。错误定位多项式σ_inner(z)由下式表示：

σ_inner(z)＝σ₀+σ₁z+…+σ_hz^h

         h＝T_inner                …(9)对于欧几里得算法，可查阅“编码理论”(Hideki Imai，TheTelecommunications Association(电信学会)，第169-172页，1990年3月15日)。

错误位置计算部分13-1根据错误定位多项式σ_inner(z)导出一个错误位置，并且将它输出到错误校正部分15-1。将σ_inner的i次幂即(σ_inner)ⁱ(i＝1，…，C_inner)连续代入错误定位多项式σ_inner(z)，如果σ_inner[(α_inner)ⁱ]等于0，则错误发生在第C_inner-i阶分量的接收码字中。以这种方式，用于通过将σ_inner的i次幂即(σ_inner)ⁱ连续代入来解错误定位多项式的方法称作吉川搜索算法。如果由吉川搜索算法获得的错误数不与错误定位多项式σ_inner(z)的阶相匹配，则错误被确定为不可校正的。这个错误可校正判定结果被输出到校正子计算部分11-1。用于从错误定位多项式导出错误位置的理论背景在上述“编码理论”中描述。

错误校正部分15-1根据来自错误位置计算部分13-1的错误位置输入来校正存储在接收码字存储部分14-1中的接收码字，并且将已解码数据D_inner-1输出到第一级去交织器2-1。

图3是表示图1的第二级内解码器1-2的结构的框图。第二级内解码器1-2包括校正子计算部分11-2、错误定位多项式导出部分12-2、错误位置计算部分13-2、接收码字存储部分14-2和错误校正部分15-2。

校正子计算部分11-2将第一级内码校正子系数S_inner-1与第一级内码修正校正子系数SR_inner-1相加，并且将相加结果SI输出到错误定位多项式导出部分12-2。同样，校正子计算部分11-2根据从错误位置计算部分13-2输入的错误可校正判定结果而将第二级内码校正子系数S_inner-2输出到第三级内解码器1-3。

如果错误是可校正的，则第二级内码校正子系数S_inner-2是零，或者如果错误是不可校正的，则第二级内码校正子系数S_inner-2是校正子系数SI。

一个功能块执行与第一级内解码器1-1完全相同的功能块的操作，除了校正子计算部分11-2以外。第三级到第N级内解码器1-3到1-N中的每一个执行与第二级内解码器相同的处理。不过，在最后一级中的第N级内解码器不输出内码校正子系数。

第一级去交织器2-1对于已解码数据D_inner-1进行去交织(格式转换)。在格式转换之后的数据是外码的码字。去交织的数据D_deint-1被输出到第一级外解码器3-1。第二级到第N级去交织器2-2到2-N中的每一个执行与第一级去交织器2-1相同的处理。

第一级交织器4-1进行交织(与去交织的格式转换相反的反向格式转换)。格式转换之后的数据是内码的码字。第一级交织器4-1将交织的数据D_int-1输出到第二级内解码器1-2。第二级到第(N-1)级交织器4-1到4-(N-1)中的每一个执行与第一级交织器4-1相同的处理。

当交织/去交织的深度是L时，外码字被交织器分解成为L个内码字，并且内码字被去交织器分解成为L个外码字。

图4是表示图1的第一级外解码器的结构的框图。第一级外解码器3-1包括校正子计算部分31-1、内码修正校正子系数导出部分32-1、错误位置计算部分33-1、接收码字存储部分34-1和错误校正部分35-1。

校正子计算部分31-1为由下式定义的校正子多项式SO(z)计算系数SO_i(i＝1，…，2*T_outer)：

SO(z)＝SO₁z+SO₂z²+…+SO_jz^j

    j＝2*T_outer             …(10)

校正子系数SO_i由下式定义：

SO_i＝Y_outer×(α_outer)ⁱ

   ＝Y₀+Y₁(α_outer)ⁱ+Y₂(α_outer)²ⁱ+…+Y_k(α_outer)^ki

  i＝1，…，2*T_outer

  k＝C_outer-1               …(11)

其中，Y_outer(x)是接收多项式，并且α_outer是伽罗瓦域的素元。

接收多项式Y_outer(x)的每个系数对应于从第一级去交织器2-1输入的去交织的数据D_deint-1的每个比特。校正子系数SO_i(i＝1，…，2*T_outer)是伽罗瓦域中的元并且由M_outer比特的宽度表示。如果去交织的数据D_deint-1不含有错误，则校正子系数成为全零。计算的校正子系数SO_i被输出到内码修正校正子系数导出部分32-1和错误位置计算部分33-1。

内码修正校正子系数导出部分32-1根据校正系数SO_i导出第一级内码修正校正子系数SR_inner-1。依据外码字的内码校正子系数的修正量被使用ROM导出。

由于外码字被交织器分解成为L个内码字，所以依据对应于校正子系数SO的L个内码字的量的修正校正子系数被从ROM输出，校正子系数SO作为输入地址。ROM具有M_outer×2*T_outer比特的地址长度以及L×M_inner×2*T_inner比特的字长度。由于ROM的面积与2的(地址长度)次幂成比例，所以在其中外码错误可校正数(T_outer)较小的传统技术中，ROM的面积变得非常大，并且是不切实际的。相反，由于在本发明的外解码器中的外码错误可校正数(T_outer)较小，所以ROM能够被采用。

由于内码字包括L个外码字，所以依据L个外码字的内码校正子系数修正量的相加结果是第一级内码修正校正子系数SR_inner-1。导出的第一级内码修正校正子系数SR_inner-1被输出到第二级内解码器1-2。

错误位置计算部分33-1根据校正子系数SO_i计算错误位置。错误位置被每个错误M_outer比特来表示。由于校正子系数SO_i具有总共M_outer×2*T_outer比特，所以错误位置计算部分33-1能够被具有地址长度为M_outer×2*T_outer比特和M_outer×T_outer比特的一个字长度的ROM实现。错误校正部分35-1根据从错误位置计算部分33-1输入的错误位置来校正存储在接收码字存储部分34-1中的接收码字，并且将已解码数据D_outer-1输出到外部。

第二级到第(N-1)级外解码器3-2到3-(N-1)中的每一个执行与第一级外解码器3-1相同的处理。第N级外解码器3-N还执行与第一级外解码器3-1相同的处理，除了内码修正校正子系数导出部分32-1没有被提供以外。

在传统技术中，BCH码被用于具有几乎相同的编码率的内码和外码。不过，本发明的迭代链接BCH编码电路采用具有高编码率的内码和具有低编码率的外码来减小电路尺寸并且提高校正能力。

尽管上面描述了两维BCH码，但是本发明作为一个整体也可以应用于BCH码。同样，本发明还可以应用于属于BCH码的亚种的里德-所罗门码。

图5是表示根据本发明一个实施例的迭代链接BCH解码电路的结构的框图。假设交织/去交织的深度是2，则内码的码长度是63比特，内码的伽罗瓦域本原多项式阶数是6，内码的每个码字的可校正比特数是4，外码的码长度是39比特，外码的伽罗瓦域本原多项式阶数是6，外码的每个码字的可校正比特数是1，并且迭代数是3，从而迭代链接BCH解码电路的结构被示出。

在图5中，根据本发明一个实施例的迭代链接BCH解码电路包括第一级到第三级内解码器1-1到1-3、第一级到第三级去交织器2-1到2-3、第一级到第三级外解码器3-1到3-3和第一级和第二级交织器4-1和4-2。

第一级内解码器1-1输入通过未示出的传输路径接收的已编码数据D_rev，并且将已解码数据D_inner-1输出到第一级去交织器2-1。同样，第一级内解码器1-1将对应于已解码数据D_inner-1的第一级内码校正子系数S_inner-1输出到第二级内解码器1-2。

第一级去交织器2-1输入已解码数据D_inner-1并且将去交织的数据D_deint-1输出到第一级外解码器3-1。第一级外解码器3-1将已解码数据D_outer-1输出到第一级交织器4-1。同样，第一级外解码器3-1根据去交织的数据D_outer-1导出第一级内码修正校正子系数SR_inner-1，并且将它输出到第二级内解码器1-2。第一级交织器4-1输入已解码数据D_outer-1并且将交织的数据D_int-1输出到第二级内解码器1-2。

第二级内解码器1-2输入第一级内码校正子系数S_inner-1、第一级内码修正校正子系数SR_inner-1和交织的数据D_int-1，根据第一级内码校正子系数S_inner-1和第一级内码修正校正子系数SR_inner-1对交织的数据D_int-1解码，并且将已解码数据D_inner-2输出到第二级去交织器2-2。同样，第二级内解码器1-2将用于已解码数据D_inner-2的第二级内码校正子系数S_inner-2输出到第三级内解码器1-3。

第二级去交织器2-2输出已解码数据D_inner-2并且将去交织的数据D_inner-2输出到第二级外解码器3-2。第二级外解码器3-2输入去交织的数据D_deint-2，并且将已解码的数据D_out-2输出到第二级交织器4-2。同样，第二级外解码器3-2根据去交织的数据D_deint-2导出第二级内码修正校正子系数SR_inner-2，并且将它输出到第三级内解码器1-3。第二级交织器4-2输入已解码数据D_outer-2，并且将交织的数据D_int-2输出到第三级内解码器1-3。

第三级内解码器1-3输入第二级内码校正子系数S_inner-2、第二级内码修正校正子系数SR_inner-2和交织的数据D_int-2，根据第二级内码校正子系数S_inner-2、第二级内码修正校正子系数SR_inner-2对交织的数据D_int-2解码，并且将已解码数据D_inner-3输出到第三级去交织器2-3。

第三级去交织器2-3输入已解码数据D_inner-3，并且将去交织的数据D_deint-3输出到第三级外解码器3-3。第三级外解码器3-3输入去交织的数据D_deint-3，并且输出链接码已解码数据D_correct。

这个实施例的第一级内解码器1-1具有上述图2所示的相同结构，包括校正子计算部分11-1、错误定位多项式导出部分12-1和错误位置计算部分13-1、接收码字存储部分14-1和错误校正部分15-1。

校正子计算部分11-1输入通过传输路径接收的已编码数据D_rev，并且将计算的校正子系数SI输出到错误定位多项式导出部分12-1。同样，如果从错误位置计算部分13-1输入的错误可校正判定结果是错误可校正，则校正子计算部分11-1将具有零值的第一级内码校正子系数S_inner-1输出到第二级内解码器1-2，否则将校正子系数SI输出作为第一级内码校正子系数S_inner-1。

错误定位多项式导出部分12-1输入校正子系数SI，并且将错误定位多项式系数σ_inner输出到错误位置计算部分13-1。错误位置计算部分13-1输入错误定位多项式系数σ_inner，并且将导出的错误位置输出到错误校正部分15-1。同样，错误位置计算部分13-1将错误可校正确定结果输出到校正子计算部分11-1。

接收码字存储部分14-1输入通过传输路径接收的已编码数据D_rev，并且将延迟接收码字输出到错误校正部分15-1。错误校正部分15-1输入从错误位置计算部分13-1输出的错误位置以及从接收码字存储部分14-1输出的延迟接收码字，并且将已解码数据D_inner-1输出到第一级去交织器2-1。

这个实施例的第二级内解码器1-2具有如上述图3所示的相同结构，包括校正子计算部分11-2、错误定位多项式导出部分12-2和错误位置计算部分13-2、接收码字存储部分14-2和错误校正部分15-2。

校正子计算部分11-2输入第一级内码校正子系数S_inner-1和第一级内码修正校正子系数SR_inner-1，并且将相加结果作为校正子系数SI输出到错误定位多项式导出部分12-2。同样，如果从错误位置计算部分13-2输入的错误可校正判定结果是错误可校正，则校正子计算部分11-2将具有零值的第二级内码校正子系数S_inner-2输出到第三级内解码器1-3，否则将校正子系数SI输出作为第二级内码校正子系数S_inner-2。

功能块具有与第一级内解码器1-1的功能块相同的结构，除了校正子计算部分11-2之外。第三级内解码器1-3具有与第二级内解码器1-2相同的结构，除了内码校正子系数没有在最后一级输出之外。

这个实施例的第一级外解码器3-1具有如图4所示的相同结构，包括校正子计算部分31-1、内码修正校正子系数导出部分32-1、错误位置计算部分33-1、接收码字存储部分34-1和错误校正部分35-1。

校正子计算部分31-1输入来自第一级去交织器2-1的去交织的数据D_deint-1，并且计算校正子系数SO。计算的校正子系数SO被输出到内码修正校正子系数导出部分32-1和错误位置计算部分33-1。

内码修正校正子系数导出部分32-1输入校正子系数SO，并且导出第一级内码修正校正子系数SR_inner-1。导出的第一级内码修正校正子系数SR_inner-1被输出到第二级内解码器1-2。

错误位置计算部分33-1输入校正子系数SO并且将错位值输出到错误校正部分35-1。接收码字存储部分34-1输入来自第一级去交织器2-1的去交织的数据D_deint-1，并且将延迟接收码字输出到错误校正部分35-1。错误校正部分35-1输入来自错误位置计算部分33-1的错误位置和来自接收码字存储部分34-1的延迟接收码字，并且将已解码数据D_outer-1输出到第一级交织器4-1。

第二级外解码器3-2具有与第一级外解码器3-1相同的结构。第三级外解码器3-3具有与第一级外解码器3-1相同的结构，除了内码修正校正子系数导出部分没有被提供之外。

下面结合图2到5描述根据本发明一个实施例的迭代链接BCH解码电路的操作。在迭代链接BCH解码电路中，假设交织/去交织的深度是2，内码的码长度是63比特，内码的伽罗瓦域本原多项式阶数是6，内码的每个码字的可校正比特数是4，内码的校验数据长度是24比特，内码的信息数据长度是39比特，外码的码长度是39比特，外码的校验数据长度是6比特，外码的信息数据长度是33比特，外码的伽罗瓦域本原多项式阶数是6，外码的每个码字可校正比特数是1，并且迭代数是3。

首先，在第一级，第一级内解码器1-1对通过传输路径接收的已编码数据D_rev解码，并且将已解码数据D_inner-1输出到第一级去交织器2-1。同样，第一级内解码器1-1将对应于已解码数据D_inner-1的第一级内码校正子系数S_inner-1输出到第二级内解码器1-2。如果已编码数据D_rev是可校正码字，则第一级内码校正子系数S_inner-1是零，如果它是不可校正码字，则所述第一级内码校正子系数S_inner-1是在解码时得到的已编码数据D_rev的校正子系数。

第一级去交织器2-1对已解码数据D_inner-1去交织，并且将去交织的数据D_deint-1输出到第一级外解码器3-1。第一级外解码器3-1根据去交织的数据D_deint-1导出第一级内码修正校正子系数SR_inner-1，并且将它输出到第二级内解码器1-2。同样，第一级外解码器3-1对去交织的数据D_deint-1进行解码，并且将已解码数据D_outer-1输出到第一级交织器4-1。第一级交织器4-1对已解码数据D_outer-1进行交织，并且将交织的数据D_int-1输出到第二级内解码器1-2。

在第二级，第二级内解码器1-2根据第一级内码校正子系数S_inner-1和第一级内码修正校正子系数SR_inner-1来对交织的数据D_int-1进行解码，并且将已解码数据D_inner-2输出到第二级去交织器2-2。同样，第二级内解码器1-2将对应于已解码数据D_inner-2的第二级内码校正子系数S_inner-2输出到第三级内解码器1-3。

第二级去交织器2-2对已解码数据D_inner-2去交织，并且将去交织的数据D_deint-2输出到第二级外解码器3-2。第二级外解码器3-2根据去交织的数据D_deint-2导出第二级内码修正校正子系数SR_inner-2，并且将它输出到第三级内解码器1-3。同样，第二级外解码器3-2对去交织的数据D_deint-2解码并且将已解码数据D_outer-2输出到第二级交织器4-2。第二级交织器4-2对已解码数据D_outer-2进行交织，并且将交织的数据D_int-2输出到第三级内解码器1-3。

此外，在第三级，第三级内解码器1-3根据第二级内码校正子系数S_inner-2和第二级内码修正校正子系数SR_inner-2对交织的数据D_int-2解码，并且将已解码数据D_inner-3输出到第三级去交织器2-3。第三级去交织器2-3对已解码数据D_inner-3去交织，并且将去交织的数据D_deint-3输出到第三级外解码器3-3。第三级外解码器3-3对去交织的数据D_deint-3解码并且输出链接码解码数据D_correct。

接下来，描述每个功能块的详细操作。首先，描述第一级到第三级内解码器1-1到1-3的操作。

校正子计算部分11-1计算用于由下式定义的校正子多项式SI(z)的系数SI_i(i＝1，2，…，8)：

SI(z)＝SI₁z+SI₂z²+…+SI₈z⁸           …(12)

校正子系数SI_i由下式定义：

SI_i＝Y_inner(αⁱ)

   ＝Y₀+Y₁(α_inner)ⁱ+Y₂(α_inner)²ⁱ+…+Y₆₂(α_inner)⁶²ⁱ

  i＝1，2，…，8                     …(13)

其中，Y_inner(x)是接收多项式，α_inner是伽罗瓦域的素元。

接收多项式Y_inner(x)的每个系数对应于通过传输路径接收的已编码数据D_rev的每个比特。校正子系数SI_i是伽罗瓦域中的元并且由6比特宽度表示。如果通过传输路径接收的已编码数据D_rev不含有错误，则校正子系数成为全零。例如，如果错误出现在对应于接收多项式Y_inner(x)的第五阶和第十阶系数的已编码数据D_rev中，则多项式系数SI_i由下式表示：

SI_i＝(α_inner)⁵ⁱ+(α_inner)¹⁰ⁱ

  i＝1，2，…，8                      …(14)

计算的校正子系数SI_i被输出到错误定位多项式导出部分12-1。同样，校正子计算部分11-1将由第一级内解码器1-1解码的数据D_inner-1的校正子系数作为第一级内码校正子系数S_inner-1输出到第二级内解码器1-2。

如果接收多项式Y_inner(x)中的错误小于或者等于错误可校正比特数(4比特)，则错误都被校正，并且零被输出作为第一级内码校正子系数S_inner-1。如果接收多项式Y_inner(x)中的错误大于错误可校正比特数(4比特)，则错误没有被校正，并且通过传输路径接收的已编码数据D_rev直接输出作为已解码数据D_inner-1，从而由多项式计算部分11-1导出的校正子系数SI_i被输出作为第一级内码校正子系数S_inner-1。错误位置计算部分13-1判定错误是否是可校正的，并且判定结果被输入校正子计算部分11-1。

错误定位多项式导出部分12-1采用欧几里得算法根据校正子系数SI_i来导出错误定位多项式α_inner(z)，并且将它输出到错误位置计算部分13-1。错误定位多项式α_inner(z)由下式表示：

σ_inner(z)＝σ₀+σ₁z+…+σ₄z⁴    …  (15)

错误位置计算部分13-1从错误定位多项式α_inner(z)导出错误位置，并且将它输出到错误校正部分15-1。将σ_inner的i次幂即(σ_inner)ⁱ(i＝1，…，63)连续代入错误定位多项式σ_inner(z)，如果σ_inner[(α_inner)ⁱ]等于0，则错误发生在第63-i阶分量的接收码字中。

利用吉川搜索算法获得的错误位置被输出到错误校正部分15-1。不过，如果错误数与错误定位多项式σ_inner(z)的阶数不匹配，则错误被判定为不可校正，并且错误位置被输出到错误校正部分15-1。这个错误可校正判定结果还被输出到多项式计算部分11-1。

错误校正部分15-1根据从错误位置计算部分13-1输入的错误位置来校正接收码字存储部分14-1中存储的接收码字，并且将已解码数据D_inner-1输出到第一级去交织器2-1。

错误定位多项式导出部分12-2、错误位置计算部分13-2、接收码字存储部分14-2和错误校正部分15-2执行与第一级内解码器1-1完全相同的操作。

多项式计算部分11-2将第一级内码校正子系数S_inner-1与第一级内码修正校正子系数SR_inner-1相加，并且将相加结果SI输出到错误定位多项式导出部分12-2。同样，校正子计算部分11-2将由第二级内解码器1-2解码的数据D_inner-2的校正子系数作为第二级内码校正子系数S_inner-2输出到第三级内解码器1-3。如果从错误位置计算部分13-2输入的错误可校正判定结果是错误可校正，则输出零，否则相加结果SI被作为第二级内码校正子系数S_inner-2输出。

例如，当第一级内解码器1-1的接收多项式的第62、61、60、59和58阶系数有错误时，则错误没有被第一级内解码器1-1校正，这是因为错误有4比特或者更多。之后，如果对应于接收多项式的第62阶系数被在第一级外解码器3-1中校正，则第一级内码校正子系数S_inner-1和第一级内码修正校正子系数SR_inner-1被由下式表达：

S_inner-1的第i阶分量

    ＝(α_inner)⁵⁸ⁱ+(α_inner)⁵⁹ⁱ+(α_inner)⁶⁰ⁱ+(α_inner)⁶¹ⁱ+(α_inner)⁶²ⁱ

                                                          …(16)

   i＝1，…，8

SR_inner-1的第i阶分量

    ＝(α_inner)⁶²ⁱ

   i＝1，…，8                                            …(17)

因此，相加结果SI被由下式表达：

 SI_I＝(α_inner)⁵⁸ⁱ+(α_inner)⁵⁹ⁱ+(α_inner)⁶⁰ⁱ+(α_inner)⁶¹ⁱ

   i＝1，…，8                                            …(18)

当接收多项式的第61、60、59和58阶系数有错误时，由表达式(18)表示的相加结果SI与校正子系数一致。在这种情况下，因为错误数在可校正范围(4比特或者更少)中，所以错误定位多项式导出部分12-2、错误位置计算部分13-2、接收码字存储部分14-2和错误校正部分15-2导出错误位置并且校正错误。

第三级内解码器1-3执行与上述第二级内解码器1-2相同的操作。不过，由于第三级内解码器1-3在最后一级，所以内码校正子系数不被输出。

图6中的表格表示由图5的第一级到第三级去交织器2-1到2-3的格式转换的例子。图7中的表格表示由图5的第一级和第二级交织器4-1和4-2的格式转换的例子。下面描述第一级到第三级去交织器2-1到2-3和第一级和第二级交织器4-1和4-2的操作。

第一级到第三级去交织器2-1到2-3中的每一个进行如图6所示的格式转换。在图6中，#X(Y)表示在第X个内码字中的第Y阶分量。图6中的斜线部分表示第一个内码字的信息数据分量(第62到24阶)。如图6所示，内码字的信息数据分量被分解成为两个(＝交织深度)外码字。注意到第一内码字的信息数据，第62阶分量被分解成为第一个外码字的第38阶分量并且第61阶分量被分解成为第二个外码字的第37阶分量。

第一级和第二级交织器4-1和4-2中的每一个进行去交织器的反向转换或者如图7所示的格式转换。％X(Y)表示第X个外码字中的第Y阶分量。图7中的斜线部分表示第一个外码字。如图7所示，外码字被分解成为两个(＝交织深度)内码字。注意到第一个外码字，第38阶分量被分解成为第一个内码字的第62阶分量并且第37阶分量被分解成为第零个内码字的第61阶分量。

在其中内码字的信息数据分量被均匀分解成为多个外码字的交织/去交织方法中，如果不同于这个实施例的方法被采用，则没有问题。

第一个外解码器3-1的校正子计算部分31-1计算由下式定义的校正子多项式SO(z)的系数SO_i(i＝1，2)：

SO(z)＝SO₁z+SO₂z²                        …(19)校正子系数SO_i由下式表达：

  SO_i＝Y_outer×(α_outer)ⁱ

     ＝Y₀+Y₁(α_outer)ⁱ+Y₂(α_outer)²ⁱ+Y₃(α_outer)³ⁱ+…+Y₃₈(α_outer)³⁸ⁱ

    i＝1，2                              …(20)

其中Y_outer(x)是接收多项式，α_outer是伽罗瓦域的素元。

接收多项式Y_outer(x)的每个系数对应于从第一级去交织器2-1输入的去交织数据D_deint-1的每个比特。校正子系数SO_i是伽罗瓦域中的元并且由6比特宽度表示。如果去交织的数据D_deint-1不含有错误，则校正子系数成为全零。计算的校正子系数SO_i被输出到内码修正校正子系数导出部分32-1和错误位置计算部分33-1。

内码修正校正子系数导出部分32-1根据校正子系数SO_i计算第一级内码修正校正子系数SR_inner。利用校正子系数SO_i作为输入地址，依据外码字的内码校正子系数的修正量被使用ROM计算。由于外码字被交织器分解成为两个内码字，所以依据两个内码字的量的修正校正子系数被从ROM输出。ROM有12(＝6×2)比特的地址长度和96[＝2×6×(2*4)]比特的字长度。由于内码字包括两个外码字，所以依据两个外码字的内码字校正子系数修正量的相加结果是第一级内码修正校正子系数SR_inner-1。导出的第一级内码修正校正子系数SR_inner-1被输出到第二级内解码器1-2。

下面采用其中第零个外码字的第38阶分量和第一个外码字的第37阶分量中有错误的例子来描述内码修正校正子系数导出部分32-1的操作。在这种情况下，交织/去交织方法是如图6和7所示的一个。

第零个外码字被分解成为第零个内码字和第(-1)个内码字。因此，当第零个外码字的校正子系数被输入时，第零个内码字和第(-1)个内码字的校正子系数修正量被从ROM输出。由于其中出现错误的第零个外码字的第38阶分量对应于第零个内码字的第68阶分量，所以[(α_inner)⁶⁸，(α_inner)^68*2，…，(α_inner)^68*8]被输出作为来自ROM的第零个内码字的校正子系数修正量。

同样，[0，0，0，0，0，0，0，0]被输出作为第(-1)个内码字的校正子系数修正量。从ROM输出的第零个内码字的校正子系数修正量被存储在未示出的寄存器中。

第一个外码字被分解成为第零个内码字和第一个内码字。因此，当第一个外码字的校正子系数被输入时，第零个内码字和第一个内码字的校正子系数修正量被从ROM输出。由于其中出现错误的第一个外码字的第37阶分量对应于第零个内码字的第67阶分量，所以[(α_inner)⁶⁷，(α_inner)^67*2，…，(α_inner)^67*8]被输出作为来自ROM的第零个内码字的校正子系数修正量。同样，[0，0，0，0，0，0，0，0]被输出作为第一个内码字的校正子系数修正量。

内码修正校正子系数导出部分32-1将第零个外码字被解码时计算的第零个内码字的校正子系数修正量与当第一个外码字被解码时计算的第零个内码字的校正子系数修正量的相加结果[(α_inner)⁶⁷+(α_inner)⁶⁸，(α_inner)^67*2+(α_inner)^68*2，…，(α_inner)^67*8+(α_inner)^68*8]作为第一级内码修正量校正子系数SR_inner-1输出。当内码字的第68阶分量和第67阶分量有错误时，第一级内码修正校正子系数SR_inner-1与内码校正子系数一致。

错误位置计算部分33-1根据校正子系数SO_i(i＝1，2)计算错误位置。错误位置由每个错误6比特表示。由于校正子系数SO_i具有总共12(＝6×2)比特，所以错误位置计算部分33-1被具有12比特地址长度和6比特一个字长度的ROM实现。

错误校正部分35-1根据从错误位置计算部分33-1输入的错误位置来校正存储在接收码字存储部分34-1中的接收码字，并且将已解码数据D_outer-1输出到外部。

第二级外解码器3-2执行与第一级外解码器3-1相同的处理。第三级外解码器3-3执行与第一级外解码器3-1相同的处理，除了内码修正校正子系数导出部分没有被提供之外。

在传统技术中，BCH码被采用于具有相同编码率的内码和外码。不过，如果本发明的迭代链接BCH解码电路采用具有高编码率的内码和具有低码率的外码来减小电路结构规模和提高校正能力。

这样，这个实施例的外解码器就不需要使用欧几里得算法的错误定位多项式导出部分和使用吉川搜索算法的错误位置计算部分，这两部分在传统技术中都是需要的，从而能够减小外解码器的电路结构。具有低编码率的外解码器利用ROM获取错误位置和内码修正校正子系数。

这个实施例的在第二级和随后级中的内解码器不需要象传统技术那样获得来自接收多项式的校正子系数，从而能够减小电路结构。在第二级和随后级中的这个实施例的内解码器根据前面级的内解码器的校正子系数S与在前面级的外解码器计算的内码修正校正子系数SR相加的结果来进行解码。

此外，高错误校正能力能够被通过采用具有高编码率的内码和具有低编码率的外码来实现。在BCH码中，当接收码字的平均错误数大于或者等于可校正比特数时，错误难以被校正。在这个实施例的迭代链接BCH解码电路的内解码器比具有相同编码率的传统技术的内解码器具有更高的编码率，即更多数量的可校正比特。因此，即使因为输入错误率是差的而使得传统技术的内解码器不能校正错误，这个实施例的内解码器也能够校正错误。

由于外解码器能够校正没有被内解码器校正的剩余错误，所以即使象这个实施例中的外解码器那样的可校正比特数小(编码率低)，也没有问题。

一方面，在传统技术中，由于外解码器具有可以与内解码器相比的编码率，所以当内解码器难以校正错误时，外解码器也难以校正错误。

BCH码和里德-所罗门码的典型解码电路能够被利用象两维BCH码那样的相同的电路结构来实现。因此，这个实施例提供如上所述的对于BCH码和里德-所罗门码相同的结果。

图8是表示根据本发明另一个实施例的迭代链接BCH解码电路的结构的框图。假设交织/去交织的深度是2，内码的码长度是63比特，内码的伽罗瓦域本原多项式阶是6，内码的每个码字的可校正比特数是4，内码的校验数据长度是24比特，内码的信息数据长度是39比特，外码的码长度是39比特，外码的校验数据长度是6比特，外码的信息数据长度是33比特，外码的伽罗瓦域本原多项式阶是6，外码的每个码字可校正比特数是1，并且迭代数是3。

根据本发明另一个实施例的迭代链接BCH解码电路包括第一级到第三级内解码器1-1到1-3、第一级到第三级去交织器2-1到2-3、第一级到第三级外解码器3-1到3-3、第一级和第二级交织器4-1和4-2。

在本发明的一个实施例中，在第二级和随后级中的每个内解码器根据前面级中的内解码器的校正子系数S与在前面级中的外解码器中计算的内码修正校正子系数SR相加的结果来进行解码。不过，在本发明的另一个实施例中，在第二级和随后级中的每个内解码器根据从前面级的内解码器中输出的剩余多项式R1和R2与在前面级的外解码器中计算的内码修正剩余多项式RR1和RR2相加的结果来进行解码。

图9是表示图8的第一级内解码器1-1的结构的框图。第一级解码器1-1包括校正子计算部分11-1、错误定位多项式导出部分12-1、错误位置计算部分13-1、接收码字存储部分14-1和错误校正部分15-1。

校正子计算部分11-1根据由下式定义的剩余多项式RI_j(z)(j＝1，3，5，7)来计算校正子系数SI_i(i＝1，…，8)：

    RI(z)＝Y_inner(z)modMI_j(z)

         ＝r_j，0+r_j，1z+r_j，2z²+…+r_j，5z⁵    …(21)

校正子系数SI_i例如如下定义：

SI₁＝RI₁(α_inner)，

 SI₂＝RI₁[(α_inner)²]，

 SI₃＝RI₃[(α_inner)³]，

 SI₄＝RI₁[(α_inner)⁴]，

 SI₅＝RI₅[(α_inner)⁵]，

 SI₆＝RI₃[(α_inner)⁶]，

 SI₇＝RI₇[(α_inner)⁷]，

 SI₈＝RI₁[(α_inner)⁸]            …(22)

其中Y_inner(z)是接收多项式，α_inner是伽罗瓦域的素元，MI_j(z)是(α_inner)^j的最小多项式，并且mod是模数。由表达式(22)定义的校正子系数SI_i具有与由在本发明一个实施例中采用的表达式(13)定义的校正子系数SI_i相同的值。

由于最小多项式MI_j(z)的阶与伽罗瓦域本原多项式阶“6”一致，所以作为接收多项式Y_inner(z)除以最小多项式MI_j(z)的余项的剩余多项式RI_j(z)成为第五阶多项式。剩余多项式RI_j(z)的系数是零或者一，所以剩余多项式RI_j(z)由6比特表示。

由于剩余多项式RI_j(z)只有6比特，所以校正子系数SI_i可以只从剩余多项式RI_j(z)中获得。计算的校正子系数SI_i被输出到错误定位多项式导出部分12-1。同样，校正子计算部分11-1将由第一级内解码器1-1解码的数据D_inner-1的剩余多项式RI_j(z)作为第一级内码剩余多项式R1(z)输出到第二级内解码器1-2。

如果接收多项式Y_inner(z)中的错误少于或者等于错误可校正比特数(4比特)，则错误全部被校正，从而零被作为第一级内码剩余多项式R1(z)输出。如果接收多项式Y_inner(x)中的错误多于错误可校正比特数(4比特)，则错误不被校正，所以通过传输路径接收的已编码数据D_rev被直接作为已解码数据D_inner-1输出，从而在校正子计算部分11-1中导出的剩余多项式RI_j(z)被作为第一级内码剩余多项式R1(z)输出。错误位置计算部分13-1判定错误是否是可校正的，其判定结果被输入校正子计算部分11-1。

错误定位多项式导出部分12-1、错误位置计算部分13-1、接收码字存储部分14-1和错误校正部分15-1执行与本发明一个实施例完全相同的操作。

图10是表示图8的第二级内解码器1-2的结构的框图。第二级内解码器1-2包括校正子计算部分11-2、错误定位多项式导出部分12-2、错误位置计算部分13-2、接收码字存储部分14-2和错误校正部分15-2。

错误定位多项式导出部分12-2、错误位置计算部分13-2、接收码字存储部分14-2和错误校正部分15-2执行与本发明一个实施例完全相同的操作。

校正子计算部分11-2将从第一级内解码器1-1输出的第一级内码剩余多项式R1(z)与从第一级外解码器3-1输出的第一级内码修正剩余多项式RR1(z)相加，并且根据表达式(22)从相加结果RI(z)中计算校正子系数SI_i(i＝1，…，8)。计算的校正子系数SI_i被输出到错误定位多项式导出部分12-2。同样，如果错误可校正判定结果是错误可校正，则校正子计算部分11-2输出零，否则将相加结果RI(z)作为第二级内码剩余多项式R2(z)输出到第三级内解码器1-3。

第三级内解码器1-3执行与上述第二级内解码器1-2相同的操作。不过，由于在最后一级的第三级内解码器1-3没有输出内码剩余多项式。第一级到第三级去交织器2-1到2-3和第一级与第二级去交织器4-1和4-2执行与本发明一个实施例的那些去交织器完全相同的操作。

图11是表示图8的第一级外解码器3-1的结构的框图。第一级外解码器3-1包括校正子计算部分31-1、错误位置计算部分33-1、接收码字存储部分34-1、错误校正部分35-1和内码修正剩余多项式导出部分36-1。

本发明另一个实施例中的校正子计算部分31-1计算由下式定义的剩余多项式RO(z)：

RO(z )＝Y_outer(z)modMO(z)

      ＝r₀+r₁z+r₂z²+…+r₅z⁵         …(23)

校正子系数SO_i(i＝1，2)例如由下式定义：

   SO₁＝RO(α_outer)，

   SO₂＝RO[(α_outer)²]              …(24)

不过，校正子计算部分31-1不采用校正子系数SO_i。其中Y_outer(z)是接收多项式，α_outer是伽罗瓦域中的素元，MO(z)是α_outer的最小多项式，并且mod是模数。

由于最小多项式MO(z)的阶与伽罗瓦域本原多项式阶“6”一致，所以作为接收多项式Y_outer(z)除以最小多项式MO(z)的余项的剩余多项式RO(z)成为第五阶多项式。剩余多项式RO(z)的系数是零或者一，所以剩余多项式RO(z)由6比特表示。

计算的剩余多项式RO(z)被输出到内码修正剩余多项式导出部分36-1和错误位置计算部分33-1。校正子系数SO_i被唯一地从剩余多项式RO(z)中获得。因此，错误位置被唯一地从剩余多项式RO(z)获得。

内码修正剩余多项式导出部分36-1根据剩余多项式RO(z)产生内码修正剩余多项式RR1。内码修正剩余多项式被使用ROM导出。由于外码字被分解成为两个内码字，所以利用剩余多项式RO(z)作为输入地址，对应于剩余多项式RO(z)的两个内码字的剩余多项式修正量被从ROM输出。ROM具有6比特的地址长度和48(＝2×6×4)比特的字长度。由于内码字由两个外码字组成，所以根据两个外码字的内码剩余多项式修正量的相加结果成为第一级内码修正剩余多项式RR1。导出的第一级内码修正剩余多项式RR1被输出到第二级内解码器1-2。

本发明一个实施例中的内码修正校正子系数导出部分32-1利用总共12比特的校正子系数SO_i作为输入地址，由输出总共96比特的两个内码字的修正校正子系数的ROM构成。相反，本发明另一个实施例中的内码修正剩余多项式导出部分36-1由具有6比特地址长度和48比特字长度的ROM构成。因此，与本发明一个实施例中的内码修正校正子系数导出部分32-1对照，本发明另一个实施例中的内码修正剩余多项式导出部分36-1具有一半地址长度、一半字长度和ROM的1/128[＝1/2(2⁶)×1/2]的面积。

错误位置计算部分33-1根据剩余多项式RO(z)产生错误位置。错误位置由每个错误6比特表示。由于剩余多项式RO(z)由6比特表示，所以错误位置计算部分33-1可以利用具有6比特地址长度和6比特字长度的ROM实现。

本发明一个实施例中的错误位置计算部分33-1利用总共12比特的校正子系数SO_i作为输入地址而输出一个6比特错误位置。因此，与本发明一个实施例中的错误位置计算部分33-1对照，本发明另一个实施例中的错误位置计算部分33-1具有一半地址长度、一半字长度和ROM的1/64[＝1/(26)]的面积。接收码字存储部分34-1和错误校正部分35-1执行与本发明一个实施例中完全相同的操作。

第二级外解码器3-2还执行与第一级外解码器3-1相同的处理。第三级外解码器3-3还执行与第一级外解码器3-1相同的处理，尽管内码修正剩余多项式导出部分没有被提供。

同样，剩余多项式被在本发明的另一个实施例中采用，从而与本发明一个实施例相比，用于外解码器中的ROM的面积可以被大大减小。

如上所述，本发明提供采用链接码的迭代链接码解码电路，内码和外码的每一个的编码率由(码字长度-冗余校验长度)/(码字长度)表示。具有高编码率的内码和具有低编码率的外码被采用，从而电路尺寸被减小并且错误校正能力被提高。