里德索洛蒙码或扩展里德索洛蒙码的译码方法和译码器

具体实施方式

下面，参照附图说明本发明的实施例。

这里处理的里德索洛蒙码是在伽罗瓦域GF(2⁷)上，使用

原始多项式P(x)＝x⁷+x³+1、

生成多项式G(x)＝(x+α)(x+α²)(x+α³)(x+α⁴)(x+α⁵)的代码长度n＝128、纠错数t＝3、1符号的位数m＝7、信息符号数i₀＝122、校验符号数p₀＝6、

扩展前的代码多项式W₀＝c₁₂₆x¹²⁶+c₁₂₅x¹²⁵+…+c₁x+c₀、

扩展校验符号c_＝W₀(α⁶)

＝c₁₂₆(α⁶)¹²⁶+c₁₂₅(α⁶)¹²⁵+…+c₁α⁶+c₀、

扩展后的代码多项式W(x)＝xW₀(x)+c-

＝c₁₂₆x¹²⁷+c₁₂₅x¹²⁶+…+c₁x²+c₀x+c-的1次扩展里德索洛蒙码。须指出的是，把扩展前的代码即非扩展成分的代码(c₁₂₆，c₁₂₅，…，c₁，c₀)称作非扩展成分。此外，把扩展校验符号c-称作扩展成分。

图1和图2是说明本发明的扩展里德索洛蒙码的译码方法的程序流程图。这里，在接收语即输入数据DI中，假设在输入数据DI中的位置j_u的符号中产生大小e_u的错误。这里假设

只有非扩展成分的接收多项式Y₀(x)＝y₁₂₆x¹²⁶+y₁₂₅x¹²⁵+…+y₁x+y₀

非扩展成分和扩展成分的接收多项式y(x)＝y₁₂₆x¹²⁷+y₁₂₅x¹²⁶+…+y₁x²+y₀x+y-把这样的输入数据DI中的错误符号的位置j_u称作错误的位置。

首先，图1中的步骤S10是第一校正子计算步骤。在该步骤S10中，为了进行校正子计算，进行以下的步骤S11和步骤S12。

在步骤S11中，把输入数据DI＝(y₁₂₆、y₁₂₅、…、y₁、y₀、y-)的校正子作为输入数据校正子SI算出。即在步骤S11A中，计算非扩展成分的输入数据校正子

SI_i＝Y₀(αⁱ)

＝y₁₂₆(αⁱ)¹²⁶+y₁₂₅(αⁱ)¹²⁵+…+y₁αⁱ+y₀(i＝1，2，3，4，5)，在步骤S11B中，计算扩展成分的输入数据校正子SI₆＝Y₀(α⁶)+y-

＝y₁₂₆(α⁶)¹²⁶+y₁₂₅(α⁶)¹²⁵+…+y₁α⁶+y₀+y-。

在步骤S12中，判断输入数据校正子SI的成分是否都为0，当输入数据校正子SI的成分都为0时，判定为输入数据DI中没有错误，转移到步骤S50内的步骤S52的处理。当输入数据校正子SI的成分的任意一个不是0时，判定为输入数据DI中有错误，转移到步骤S20的处理。

在步骤S20中，通过欧几里德算法运算，从输入数据校正子SI求出错误位置多项式σ(z)和错误评价多项式ω(z)的各次数的系数。在欧几里德算法运算结束时，即使错误位置多项式σ(z)的次数为错误评价多项式ω(z)的次数以下时，也输出这些多项式的系数。

在步骤S30中，进行钱搜索，求出错误位置多项式σ(z)的根α^-ju。即在错误位置多项式σ(z)中依次代入伽罗瓦域GF(2⁷)的元，把错误位置多项式σ(z)的值变为0的元作为该错误位置多项式σ(z)的根α^-ju求出。这时，错误位置多项式σ(z)当伽罗瓦域GF(2⁷)中具有的彼此不同的根的数低于该错误位置多项式σ(z)的次数时，不判断能否纠错，输出根α^-ju。错误位置j_u分别与错误位置多项式σ(z)的根α^-ju对应。在错误评价多项式ω(z)中代入错误位置多项式σ(z)的各根α^-ju，求出错误评价值ω(α^-ju)，并且在错误位置多项式σ(z)的导函数中代入错误位置多项式σ(z)的各根α^-ju，求出错误位置多项式的微分值σ’(α^-ju)。

在步骤S40中，把错误评价值ω(α^-ju)除以对应的错误位置多项式微分值σ’(α^-ju)，求出表示错误位置j_u的各符号中的错误位的错误大小e_u。

在步骤S50中，进行第一纠错。具体而言，进行以下的步骤S51、步骤S52、步骤S53和步骤S54。

在步骤S51中，为了进行纠错处理，对非扩展成分和扩展成分进行步骤S51A，对扩展成分进行步骤S51B。

在步骤S51A中，根据与错误位置多项式σ(z)的各根α^-ju对应的错误位置j_u、错误大小e_u，对输入数据DI进行纠错处理，作为纠错处理数据，取只有非扩展成分的纠错处理数据的多项式F₀(x)＝f₁₂₆x¹²⁶+f₁₂₅x¹²⁵+…+f₁x+f₀

非扩展成分和扩展成分的纠错处理数据的多项式F(x)＝xF₀(x)+f-＝f₁₂₆x¹²⁷+f₁₂₅x¹²⁶+…+f₁x²+f₀x+f-(f-为扩展成分(暂定值))。即从输入数据DI的错误位置j_u的符号减去与它对应的错误大小e_u。因为是在伽罗瓦域GF(2)的扩展域上的运算，所以也可以进行相加，以取代减去错误大小e_u的运算。

在步骤S51B中，对于扩展成分，把在只有非扩展成分的纠错处理数据的多项式F₀(x)中代入x＝α⁶而取得的值加上纠错处理数据的扩展成分f-(暂定值)。即计算F₀(α⁶)+f-＝f₁₂₆(α⁶)¹²⁶+f₁₂₅(α⁶)¹²⁵+…+f₁(α⁶)+f₀+f-考虑到F₀(α⁶)+f-为0时，在纠错处理数据的扩展成分f-(暂定值)中没有错误，所以把扩展成分f-(暂定值)原封不动地作为扩展成分的纠错处理数据，扩展成分的错误个数NB为0。当F₀(α⁶)+f-不是0时，判断为纠错处理数据的扩展成分f-(暂定值)中有错误，纠错处理数据的扩展成分f-(暂定值)的错误大小e-变为F₀(α⁶)+f-。因此，对纠错处理数据的扩展成分f-(暂定值)进行纠错处理，即在纠错处理数据的扩展成分f-(暂定值)中加上错误大小e-＝f₀(α⁶)+f-，把f-+e-＝f-+F₀(α⁶)+f-＝F₀(α⁶)+2f-＝F₀α⁶作为扩展成分的纠错处理数据，扩展成分的错误个数NB＝1。

而在步骤S60中，从由步骤S10内的步骤S11计算的输入数据校正子SI推测输入数据DI中发生的错误个数EN1(将在后面详细描述)。

在步骤S80中，从在步骤S30中计算的错误位置多项式σ(z)的根α^-ju求出错误个数NA加上来自步骤S51内的步骤S51B的扩展成分的错误个数NB。即错误个数EN2＝NA+NB。可是，不重复加上扩展成分的错误个数。

在步骤S50内的步骤S53中，判断由步骤S60推测的错误个数EN1和由步骤S80算出的错误个数EN2是否相等，并且在步骤S60中推测的错误个数EN1和在步骤S80中算出的错误个数EN2都为3(纠错数t)以下，即判断是否“EN1＝EN2≤3”，当“EN1＝EN2≤3”时，转移到步骤S54的处理，当不是时(“EN1≠EN2或EN1＞3或EN2＞3”)，转移到步骤S52。

在步骤S54中，当输入数据校正子SI的成分都不为0，并且“EN1＝EN2≤3”时，把纠错处理数据作为第一订正数据C1。

在步骤S52中，当输入数据校正子SI的成分都为0，或“EN1≠EN2或EN1＞3或EN2＞3”时，把输入数据DI原封不动作为第一订正数据C1。

在图2中的步骤S90中，为了进行第一订正数据C1的校正子计算，进行以下的步骤S91和步骤S92。

在步骤S91中，

假设只有非扩展成分的第一订正数据C1的多项式D₀(x)＝d₁₂₆x¹²⁶+d₁₂₅x¹²⁵+…+d₁x+d₀

非扩展成分和扩展成分的第一订正数据C1的多项式D(x)＝d₁₂₆x¹²⁷+d₁₂₅x¹²⁶+…+d₁x²+d₀x+d-，把第一订正数据C1＝(d₁₂₆、d₁₂₅、…、d₁、d₀、d-)的校正子作为订正数据校正子SC算出。即在步骤S91A中，计算非扩展成分的订正数据校正子

SC_i＝D₀(αⁱ)

＝d₁₂₆(αⁱ)¹²⁶+d₁₂₅(αⁱ)¹²⁵+…+d₁αⁱ+d₀(i＝1，2，3，4，5)，在步骤S91B中，计算扩展成分的订正数据校正子

SC₆＝D₀(α⁶)+d-

＝d₁₂₆(α⁶)¹²⁶+d₁₂₅(α⁶)¹²⁵+…+d₁α⁶+d₀+d-

在步骤S92中，判断“订正数据校正子SC的成分全部为0或EN1≠EN2或EN1＞3或EN2＞3”的判定条件的真伪，当该判定条件为真时，判定在第一订正数据C1中没有错误，转移到步骤S100内的步骤S101内的步骤S101的处理。当不是时(订正数据校正子SC的成分中的任一个不是0，并且“EN1＝EN2≤3”时)，判定在第一订正数据C1中有错误，转移到步骤S100内的步骤S102的处理。

步骤S100是第二纠错步骤。具体而言，进行步骤S101和步骤S102。

在步骤S101中，考虑在第一订正数据C1中没有错误，因此，把第一订正数据C1原封不动地作为第二订正数据C2输出。

在步骤S102中，考虑在第一订正数据C1中有错误，所以根据与错误位置多项式σ(z)的各根α^-ju对应的错误位置j_u和错误的大小e_u、对于扩展成分的错误大小e-，进行把第一订正数据C1复原为输入数据DI的处理。即对于第一订正数据C1的错误位置j_u的符号，加上或减去与它对应的错误的大小e_u，对于第一订正数据C1的扩展成分的符号，再加上或减去错误的大小e-(即对于第一订正数据C1的扩展成分的符号加上或减去错误的大小e_u和错误的大小e-)。把复原取得的输入数据DI作为第二订正数据C2输出。

图3是图1中的个数推测步骤S60的详细程序流程图。下面，参照图3说明错误个数的推测方法。

在步骤S61中，判断由第一校正子计算步骤S10内的输入数据校正子计算步骤S11计算的输入数据校正子SI的成分是否都为0，当输入数据校正子SI的成分都为0时，转移到步骤S62的处理，当输入数据校正子SI的成分的任意一个不是0时，转移到步骤S63的处理。

在步骤S62中，输入数据校正子SI的成分都为0，推测错误个数为0个。

在步骤S63中，输入数据校正子SI的成分的任一个不是0时，计算：

第一错误个数推测式N₁＝S₂²+S₁S₃

第二错误个数推测式N₂＝S₃²+S₁S₅

第三错误个数推测式N₃＝S₄²+S₃S₅

第四错误个数推测式N₄＝S₅N₁+S₃N₂+S₁N₃。

在步骤S64中，判断第一、第二、第三错误个数推测式(N₁、N₂和N₃)的值是否都为0。当N₁、N₂和N₃的值都为0时，转移到步骤S65的处理，当N₁或N₂或N₃的值的任一个不是0时，转移到步骤S68的处理。

在步骤S65中，是在步骤S64中N₁、N₂和N₃的值都为0时，判断由步骤S11计算的输入数据校正子的扩展成分SI₆是否为0。当SI₆为0时，转移到步骤S66的处理，当SI₆不是0时转移到步骤S67的处理。

在步骤S66中，当在步骤S65中SI₆为0时，推测错误个数为1个。

在步骤S67中，当在步骤S65中SI₆不是0时，推测错误个数为2个。

在步骤S68中，当在步骤S64中N₁或N₂或N₃的值的任意一个不是0时，判断第四错误个数推测式N₄的值是否为0。当N₄的值为0时，转移到步骤S69的处理，当N₄的值不是0时，转移到步骤S72的处理。

在步骤S69中，当在步骤S68中N₄的值为0时，判断输入数据校正子的扩展成分SI₆是否为0。当SI₆为0时，转移到步骤S70的处理，当SI₆不是0时转移到步骤S71的处理。

在步骤S70，当在步骤S69中SI₆为0时，推测错误个数为2个。

在步骤S71，当在步骤S69中SI₆不是0时，推测错误个数为3个。

在步骤S72，当在步骤S68中N₄的值不是0时，判断SI₆是否为0。当SI₆为0时，转移到步骤S73的处理，当SI₆不是0时转移到步骤S74的处理。

在步骤S73中，当在步骤S72中SI₆为0时，推测错误个数为3个。

在步骤S74中，当在步骤S72中SI₆不是0时，推测错误个数为4个。

如上所述，根据本译码方法，比较从输入数据校正子SI推测的错误个数EN1和由译码过程计算的错误个数EN2，根据该比较结果和输入数据校正子SI进行纠错处理后，对纠错了的数据C1再度进行校正子计算，求出订正数据校正子SC，当进行误订正时或推测的错误个数EN1和计算的错误个数EN2不同时，把输入数据DI作为第二订正数据C2输出，所以对于非扩展成分和扩展成分能防止误订正，不用进行多次欧几里德算法运算处理和多次钱搜索处理。

须指出的是，在图1中，在步骤S51B中，求出扩展成分的错误个数NB，但是如图1中用单点划线所示，在步骤S40中，根据与输入数据DI以及对应于错误位置多项式σ(z)的各根α^-ju的错误位置j_u和错误大小e_u计算F₀(α⁶)+f-，按照F₀(α⁶)+f-是否为0，求出扩展成分的错误个数NB，把该结果反映到步骤S80的处理中。

此外，如从图1中的步骤S52向图2中的步骤S100中延长的单点划线所示，当输入数据校正子SI的成分都为0，或“EN1≠E2或EN1＞3或EN2＞3”时，可以把输入数据DI原封不动作为第二订正数据C2。

此外，在图1中的步骤S80中，从根α^-ju求出错误个数NA，但是也可以在步骤S30中求出错误个数NA。也能代替图3中的步骤S61，使用图1中的步骤S12的判定结果，进行图3中的步骤S62和步骤S63的处理。

此外，可以通过省略图1中的步骤S60、步骤S80和步骤S53的处理，不推测错误个数，也不计算错误个数，只计算订正数据校正子SC校正子，在防止误订正时使用该结果。

下面对用于实现上述本发明的译码方法的装置构成进行说明。

图4是表示本发明的扩展里德索洛蒙码的译码器的结构例的框图。在图4中，10是校正子计算部，20是评价多项式和位置多项式导出部，30是钱(Chien)搜索部，40是纠错部，50是数据存储部，60是错误个数推测部，70是错误个数计算部。

把输入数据DI向校正子计算部10和数据存储部50输入。数据存储部50存储输入数据DI，把与该输入数据DI相同的数据XDI向纠错部40输出。

校正子计算部10把输入数据DI＝(y₁₂₆、y₁₂₅、…、y₁、y₀、y-)的校正子作为输入数据校正子SI算出。即计算非扩展成分的输入数据校正子SI_i＝Y₀(αⁱ)

＝y₁₂₆(αⁱ)¹²⁶+y₁₂₅(αⁱ)¹²⁵+…+y₁αⁱ+y₀(i＝1，2，3，4，5)，计算扩展成分的输入数据校正子SI₆＝Y₀(α⁶)+y-

＝y₁₂₆(α⁶)¹²⁶+y₁₂₅(α⁶)¹²⁵+…+y₁α⁶+y₀+y-。检测输入数据校正子SI的成分是否都为0。当输入数据校正子SI的成分都为0时，判定在输入数据DI中没有错误，使第一标志信号F1有效，向纠错部40输出。当输入数据校正子SI的成分的任意一个不是0时，判定在输入数据DI中有错误，使第一标志信号F1为无效，向纠错部40输出。任何时候，把输入数据校正子SI向评价多项式和位置多项式导出部20和错误个数推测部60输出。可是，把向评价多项式和位置多项式导出部20输出的输入数据校正子表示为XSI，与向错误个数推测部60输出的输入数据校正子SI区分开。

在错误个数推测部60中，从由校正子计算部10计算的输入数据校正子SI推测输入数据DI中发生的错误个数EN1。

评价多项式和位置多项式导出部20根据欧几里德算法运算，从输入数据校正子XSI求出错误位置多项式σ(z)和错误评价多项式ω(z)的各次数的系数，把这些多项式的系数向钱搜索部30输出。此外，评价多项式和位置多项式导出部20具有数据保持器和伽罗瓦运算器，数据保持器保持输入数据校正子XSI和欧几里德算法运算的中间结果，最终输出错误位置多项式σ(z)和错误评价多项式ω(z)的各次数的系数。伽罗瓦运算器从数据保持器的输出进行欧几里德算法运算，求出中间结果，向数据保持器输出。须指出的是，在欧几里德算法运算结束时，即使当错误位置多项式σ(z)的次数为错误评价多项式ω(z)的次数以下时，也输出这些多项式的系数。

钱搜索部30进行钱搜索，求出错误位置多项式σ(z)的根α^-ju。即在错误位置多项式σ(z)中依次代入伽罗瓦域GF(2⁷)的元，把错误位置多项式σ(z)的值变为0的元作为该错误位置多项式σ(z)的根α^-ju求出，向纠错部40和错误个数计算部70输出。这时，错误位置多项式σ(z)当伽罗瓦域GF(2⁷)中具有的彼此不同的根的数低于该错误位置多项式σ(z)的次数时，不判断能否纠错，把根α^-ju向纠错部40和错误个数计算部70输出。错误位置j_u分别与错误位置多项式σ(z)的各根α^-ju对应。在错误评价多项式ω(z)中代入错误位置多项式σ(z)的各根α^-ju，求出错误评价值ω(α^-ju)，并且在错误位置多项式σ(z)的导函数中代入错误位置多项式σ(z)的各根α^-ju，求出错误位置多项式的微分值σ’(α^-ju)，把错误评价值ω(α^-ju)和错误位置多项式的微分值σ’(α^-ju)向评价多项式和位置多项式导出部20输出。此外，评价多项式和位置多项式导出部20中的伽罗瓦运算器把错误评价值ω(α^-ju)除以对应的错误位置多项式微分值σ’(α^-ju)，求出表示错误位置j_u的各符号中的错误位的错误大小e_u，把它向纠错部40输出。

在错误个数计算部70中，把从钱搜索部30计算出的错误位置多项式σ(z)的根α^-ju求出的错误个数NA和来自纠错部40的扩展成分的错误个数NB相加。即计算错误个数EN2＝NA+NB，把计算出的错误个数EN2提供给纠错部40。可是，不重复加上扩展成分的错误个数。

纠错部40根据与钱搜索部30输出的错误位置多项式σ(z)的根α^-ju分别对应的错误位置j_u、评价多项式和位置多项式导出部20输出的错误大小e_u，对于数据存储部50输出的输入数据XDI进行纠错处理，作为纠错处理数据，假设只有非扩展成分的纠错处理数据的多项式F₀(x)＝f₁₂₆x¹²⁶+f₁₂₅x¹²⁵+…+f₁x+f₀

非扩展成分和扩展成分的纠错处理数据的多项式F(x)＝xF₀(x)+f-＝f₁₂₆x¹²⁷+f₁₂₅x¹²⁶+…+f₁x²+f₀x+f-(f-为扩展成分(暂定值))。即从输入数据XDI的错误位置j_u的符号减去与它对应的错误大小e_u。因为是在伽罗瓦域GF(2)的扩展域上的运算，所以也可以进行相加，以取代减去错误大小e_u。对于扩展成分，把在只有非扩展成分的纠错处理数据的多项式F₀(x)中代入x＝α⁶而取得的值加上纠错处理数据的扩展成分f-(暂定值)，即计算F₀(α⁶)+f-＝f₁₂₆(α⁶)¹²⁶+f₁₂₅(α⁶)¹²⁵+…+f₁α⁶+f₀+f-，在F₀(α⁶)+f-为0时，认为在纠错处理数据的扩展成分f-(暂定值)中没有错误，所以把纠错处理数据的扩展成分f-(暂定值)原封不动地作为扩展成分的纠错处理数据，扩展成分的错误个数NB为0。当F₀(α⁶)+f-不是0时，判断为纠错处理数据的扩展成分f-(暂定值)中有错误，纠错处理数据的扩展成分f-(暂定值)的错误大小e-变为F₀(α⁶)+f-。因此，对纠错处理数据的扩展成分f-(暂定值)进行纠错处理，即在纠错处理数据的扩展成分f-(暂定值)中加上错误大小e-＝f₀(α⁶)+f-，把f-+e-＝f-+F₀(α⁶)+f-＝F₀(α⁶)+2f-＝F₀(α⁶)作为扩展成分的纠错处理数据，扩展成分的错误个数NB＝1。然后，检测由错误个数推测部60推测的错误个数EN1和由错误个数计算部70推测的错误个数EN2是否相等，并且在错误个数推测部60中推测的错误个数EN1和在错误个数计算部70中推测的错误个数EN2都为3(纠错数t)以下，即检测是否“EN1＝EN2≤3”，当“EN1＝EN2≤3”时，使后面描述的第三标志信号F3有效。当“EN1＝EN2≤3”(第三标志信号F3有效)，并且输入数据校正子SI的成分的任意一个不是0时(第一标志信号F1是无效，需要纠错时)，把纠错处理数据作为第一订正数据C1向校正子计算部10和数据存储部50输出。当不是这样时，即“EN1≠EN2或EN1＞3或EN2＞3(第三标志信号F3无效)，或输入数据校正子SI的成分都为0(第一标志信号F1有效，没必要纠错)时，把数据存储部50输出的输入数据XDI原封不动作为第一订正数据C1向校正子计算部10和数据存储部50输出。

数据存储部50存储第一订正数据C1，把与它相同的订正数据XC1提供给纠错部40。

校正子计算部10使只有非扩展成分的第一订正数据C1的多项式D₀(x)＝d₁₂₆x¹²⁶+d₁₂₅x¹²⁵+…+d₁x+d₀

并且，第一订正数据C1的多项式D(x)＝d₁₂₆x¹²⁷+d₁₂₅x¹²⁶+…+d₁x²+d₀x+d-，把第一订正数据C1＝(d₁₂₆、d₁₂₅、…、d₁、d₀、d-)的校正子作为订正数据校正子SC算出。即计算非扩展成分的订正数据校正子

SC_i＝D₀(αⁱ)

＝d₁₂₆(αⁱ)¹²⁶+d₁₂₅(αⁱ)¹²⁵+…+d₁αⁱ+d₀(i＝1，2，3，4，5)，计算扩展成分的订正数据校正子

SC₆＝D₀(α⁶)+d-

＝d₁₂₆(α⁶)¹²⁶+d₁₂₅(α⁶)¹²⁵+…+d₁α₆+d₀+d-。再判断“订正数据校正子SC的成分全部为0或“EN1≠EN2或EN1＞3或EN2＞3”(第三标志信号F3无效)”的判定条件的真伪，当该判定条件为真时，判定在第一订正数据C1中没有错误，使第二标志信号F2有效，向纠错部40输出。当不是这样时，即订正数据校正子SC的成分的任意一个不是0，并且“EN1＝EN2≤3”时(第三标志信号F3有效)，判定在第一订正数据C1中有错误，使第二标志信号F2无效，向纠错部40输出。

当第二标志信号F2有效时，纠错部40认为在第一订正数据C1中没有错误，所以把数据存储部50输出的第一订正数据XC1原封不动作为第二订正数据C2输出。可是，当第二标志信号F2无效时，认为第一订正数据C1中有错误，所以根据与钱搜索部30输出的错误位置多项式σ(z)的根α^-ju分别对应的错误位置j_u、评价多项式和位置多项式导出部20输出的错误的大小e_u、对于扩展成分的错误大小e-，进行把数据存储部50输出的第一订正数据XC1复原为输入数据DI的处理。即对于第一订正数据XC1的错误位置j_u的符号加上或减去错误的大小e_u，对于第一订正数据XC1的扩展成分的符号再加上或减去错误的大小e-(即对于第一订正数据XC1的扩展成分的符号加上或减去错误的大小e_u和错误的大小e-)。把复原取得的输入数据DI作为第二订正数据C2输出。

图5是表示图4中的校正子计算部10的主要部分的框图。在图5中，11是选择器，12是校正子运算器，13是输入数据校正子保持器，14是订正数据校正子保持器，15是第一校正子零检测器，16是第二校正子零检测器。

选择器11根据模式信号MOD选择输入数据DI或第一订正数据C1，向校正子运算器12输出。

校正子运算器12根据模式信号MOD与选择器11同步工作，进行求出输入数据校正子SI的计算、求出订正数据校正子SC的计算，把求取了输入数据校正子SI的计算结果向输入数据校正子保持器13和错误个数推测部60输出，把求取了订正数据校正子SC的计算结果向订正数据校正子保持器14输出。为了缩小电路规模，也可以构成校正子运算器12，以便用相同处理器进行非扩展成分校正子的处理和扩展成分校正子的处理。

输入数据校正子保持器13根据模式信号MOD只取入校正子运算器12的输出中的输入数据校正子SI，保持后，把它作为输入数据校正子XSI向第一校正子零检测器15输出。

第一校正子零检测器15当输入数据校正子XSI的成分都为0时，判定输入数据DI中没有错误，使第一标志信号F1有效，当输入数据校正子XSI的成分的任意一个不是0时，判定输入数据DI中有错误，使第一标志信号F1无效，把该第一标志信号F1向纠错部40输出。

此外，输入数据校正子保持器13与第一校正子零检测器15输出第一标志信号F1的定时同步，向评价多项式和位置多项式导出部20输出输入数据校正子XSI。

同样，订正数据校正子保持器14根据模式信号MOD只取入校正子运算器12的输出中的订正数据校正子SC，保持后，把该订正数据校正子SC向第二校正子零检测器16输出。

第二校正子零检测器16当订正数据校正子SC的成分都为0时，判定第一订正数据C1中没有错误，使第二标志信号F2有效，当订正数据校正子SC的成分的任意一个不是0时，判定第一订正数据C1中有错误，使第二标志信号F2无效，把该第二标志信号F2向纠错部40输出。

图6是表示图4中的纠错部40的主要部分的框图。在图6中，41是第一纠错器，42是错误位置数据保持器，43是错误大小数据保持器，44是第二纠错器，45是比较器。

比较器45比较由错误个数推测部60推测的错误个数EN1和由错误个数计算部70计算的错误个数EN2，再把这些错误个数EN1以及EN2与3(纠错数t)比较，当“EN1＝EN2≤3”时，使第三标志信号F3为有效，当不是这样时(“EN1≠EN2或EN1＞3或EN2＞3”)，使第三标志信号F3无效，把该第三标志信号F3向第一纠错器41和第二纠错器44输出。

第一纠错器41当第一标志信号F1有效(没必要对输入数据DI纠错)，或第三标志信号F3无效(“EN1≠EN2或EN1＞3或EN2＞3”)时，把输入数据DI原封不动作为第一订正数据C1输出，扩展成分的错误个数NB＝0。此外，当第一标志信号F1无效(输入数据DI包含错误，需要纠错)，并且第三标志信号F3有效(“EN1＝EN2≤3”)时，在输入数据XDI中，对于与根α^-ju对应的各错误位置j_u表示的符号，进行加上或减去对于该错误位置j_u的错误大小e_u的纠错，把纠错处理后的数据作为纠错处理数据。对于扩展成分，把在只有非扩展成分的纠错处理数据的多项式F₀(x)中代入x＝α⁶而取得的值加上纠错处理数据的扩展成分f-(暂定值)，即计算F₀(α⁶)+f-＝f₁₂₆(α⁶)¹²⁶+f₁₂₅(α⁶)¹²⁵+…+f₁α⁶+f₀+f-，考虑到F₀(α⁶)+f-为0时，在纠错处理数据的扩展成分f-(暂定值)中没有错误，所以把纠错处理数据的扩展成分f-(暂定值)原封不动地作为扩展成分的纠错处理数据，扩展成分的错误个数NB为0。当F₀(α⁶)+f-不是0时，判断为纠错处理数据的扩展成分f-(暂定值)中有错误，纠错处理数据的扩展成分f-(暂定值)的错误大小e-变为F₀(α⁶)+f-。因此，对纠错处理数据的扩展成分f-(暂定值)进行纠错处理，即在纠错处理数据的扩展成分f-(暂定值)中加上错误大小e-＝f₀(α⁶)+f-，把f-+e-＝f-+F₀(α⁶)+f-＝F₀(α⁶)+2f-＝F₀(α⁶)作为扩展成分的纠错处理数据，扩展成分的错误个数NB＝1。然后，把纠错处理数据作为第一订正数据C1输出。按所述而求出的第一订正数据C1向校正子计算部10和数据存储部50输出。

错误位置数据保持器42存储根α^-ju、对于扩展成分的错误位置j-，把它们向第二纠错器44输出。

错误大小数据保持器43存储错误的大小e_u和对于扩展成分的错误大小e-，把它们向第二纠错器44输出。

第二纠错器44当第二标志信号F2有效(对第一订正数据C1没必要纠错)，或第三标志信号F3无效(“EN1≠EN2或EN1＞3或EN2＞3”)时，把第一订正数据XC1原封不动作为第二订正数据C2输出。此外，当第二标志信号F2无效(第一订正数据C1包含错误，有必要纠错)，并且第三标志信号F3有效(“EN1＝EN2≤3”)时，根据与根α^-ju对应的错误位置j_u和错误大小e_u，对扩展成分，再根据错误位置j-和错误大小e-，进行把第一订正数据XC1复原为输入数据DI的复原处理。通过对于第一订正数据XC1的各错误位置j_u表示的符号，加上或减去与该错误位置j_u对应的错误大小e_u，进行该复原处理，对于扩展成分，通过再加上或减去与错误位置j-(扩展成分)对应的错误大小e-(即对于第一订正数据XC1的扩展成分的符号加上或减去错误大小e_u以及错误大小e-)，能进行改复原处理。把这样复原取得的输入数据DI作为第二订正数据C2输出。如上所述，第二纠错器44当在第一纠错器41无法正确进行纠错处理，第一订正数据C1包含错误时，不输出该第一订正数据C1，而输出复原了的输入数据DI。

图7是表示图6中的第一纠错器41的主要部分的框图。在图7中，41A是纠错处理器，41B是扩展成分纠错处理器，41C是总线驱动器。

纠错处理器41A当第一标志信号F1有效(没必要对输入数据DI纠错时)，或第三标志信号F3为无效时(“EN1≠EN2或EN1＞3或EN2＞3”)，把输入数据XDI原封不动作为第一订正数据输出。此外，当第一标志信号F1无效(输入数据DI包含错误，有必要纠错)，并且第三标志信号F3有效(EN1＝EN2≤3)时，在输入数据XDI中对与根α^-ju对应的各错误位置j_u所示的符号进行加上或减去对于该错误位置j_u的错误的大小e_u的纠错，把纠错处理后的数据作为第一订正数据输出。

扩展成分纠错处理器41B当第一标志信号F1有效(没必要对输入数据DI纠错时)，或第三标志信号F3为无效时(“EN1≠EN2或EN1＞3或EN2＞3”)，把纠错处理的扩展成分(暂定值)即扩展成分的输入数据XDI原封不动地作为第一订正数据输出，扩展成分的错误个数NB＝0。此外，当第一标志信号F1无效(输入数据DI包含错误，有必要纠错)，并且第三标志信号F3有效(EN1＝EN2≤3)时，对于扩展成分，把在只有非扩展成分的纠错处理数据的多项式F₀(x)中代入x＝α⁶而取得的值加上纠错处理数据的扩展成分f-(暂定值)，即计算F₀(α⁶)+f-＝f₁₂₆(α⁶)¹²⁶+f₁₂₅(α⁶)¹²⁵+…+f₁α⁶+f₀+f-，考虑到F₀(α⁶)+f-为0时，在纠错处理数据的扩展成分f-(暂定值)中没有错误，所以把扩展成分f-(暂定值)原封不动地作为扩展成分的纠错处理数据，扩展成分的错误个数NB为0。当F₀(α⁶)+f-不是0时，判断为纠错处理数据的扩展成分f-(暂定值)中有错误，纠错处理数据的扩展成分f-(暂定值)的错误大小e-变为F₀(α⁶)+f-。因此，对纠错处理数据的扩展成分f-(暂定值)进行纠错处理，即在纠错处理数据的扩展成分f-(暂定值)中加上错误大小e-＝f₀(α⁶)+f-，把f-+e-＝f-+F₀(α⁶)+f-＝F₀(α⁶)+2f-＝F₀(α⁶)作为扩展成分的纠错处理数据，扩展成分的错误个数NB＝1。然后，扩展成分纠错处理器41B把这些扩展成分的纠错处理数据作为扩展成分的第一订正数据输出。

总线驱动器41C把来自纠错处理器41A的第一订正数据和来自扩展成分纠错处理器41B的第一订正数据统一作为由非扩展成分和扩展成分构成的第一订正数据C1输出。

如上所述，在图4～图7所示的译码器中，用纠错部40比较由错误个数推测部60从输入数据校正子SI推测的错误个数EN1和在译码过程中由错误个数计算部70计算出的错误个数EN2，根据该比较结果和输入数据校正子SI，由纠错部40进行纠错处理后，对于纠错的数据C1，由校正子计算部10再度进行校正子计算，求出订正数据校正子SC，当进行误订正时或推测的错误个数EN1和计算的错误个数EN2不同时，把输入数据DI作为第二订正数据C2输出。

须指出的是，可以把图4的错误个数推测部60的功能移动到校正子计算部10的内部，把错误个数计算部70的功能移动到纠错部40的内部。

此外，在图4中，由错误个数计算部70从根α^-ju求出错误个数NA，但是也可以由钱搜索部30求出错误个数NA。

此外，也可以采用由相同的处理器进行图7中的两个处理器41A、41B的处理的结构。

也可以用分别不同的处理器进行图5中的校正子运算器12的非扩展成分的处理和扩展成分的处理。图8是表示这时的校正子运算器12的主要部分的框图。在图8中，12A是非扩展成分校正子处理器，12B是扩展成分校正子处理器，12C是总线驱动器。

非扩展成分校正子处理器12A分别计算输入数据DI的非扩展成分和第一订正数据C1的非扩展成分的校正子，向总线驱动器12C输出。

扩展成分校正子处理器12B分别计算输入数据DI的扩展成分和第一订正数据C1的扩展成分的校正子，向总线驱动器12C输出。

总线驱动器12C把来自非扩展成分校正子处理器12A的输入数据非扩展成分的校正子、来自扩展成分校正子处理器12B的输入数据扩展成分的校正子统一作为输入数据校正子SI输出，把来自非扩展成分校正子处理器12A的订正数据非扩展成分的校正子、来自扩展成分校正子处理器12B的订正数据扩展成分的校正子统一作为订正数据校正子SC输出。

希望采用把基于校正子计算部10的输入数据校正子SI的计算等处理作为第一阶段，把评价多项式和位置多项式导出部20以及钱搜索部30的处理作为第二阶段，基于纠错部40的第一订正数据C1的输出和基于校正子计算部10的订正数据校正子SC的计算等处理作为第三阶段，并且把基于纠错部40的第二订正数据C2的输出处理作为第四阶段的流水线结构。校正子计算部10以成为基准的时钟信号的2倍频率工作，在一系列的译码过程中，使用2次(第一和第三阶段中)。

如上所述，本发明的译码方法和译码器能防止译码时的误订正，在数字广播、数字磁记录等中里德索洛蒙码或扩展里德索洛蒙码的多重纠错中是有用的。