CN1119869C - 一种采用里德－索洛门码的长突发纠错译码方法 - Google Patents

Abstract

本发明属于通信技术领域，涉及一种采用里德-索洛门码的长突发纠错译码方法。本方法包括：基于RS码的循环特性，通过有效利用RS码接收多项式循环移位前后的关系，以及长突发的错误位置相关性，将突发错误的错误位置假设为接收多项式的最低2t位，使译码方法简化成了先对接收多项式进行循环移位，然后通过一组线性方程求解错误图样的方法。本发明以相对小得多的译码延时和以相对于高得多的信息传输速率实现了适合于长突发错误的纠错译码。

Description

一种采用里德-索洛门码的长突发纠错译码方法

技术领域

本发明属于通信技术领域，特别涉及采用前向差错控制(FEC)技术在数据传输及存贮系统中的一种采用里德-索洛门码(以下简称RS码)纠正长突发错误的有效而快速的译码方法。

背景技术

数据在存贮以及传输过程中经常会引发突发错误。产生这种错误的原因有线性噪声、解调过程中的同步丢失、无线传输中的多径衰落、磁性存储器中的磁道缺损等。这种突发错误一般呈周期性出现并且持续时间比较长。由于这种长突发错误的存在，大大限制了特定带宽下的信息传输速率和特定面积下存储器的存储容量。特别是在无线传输系统中，由于多径衰落的影响，这一问题变得更加突出。

里德-索洛门码(RS码)具有较强的纠正突发错误的能力，被广泛用于数据传输和存储系统中。

采用RS码纠正长突发错误的译码方法原理为：

RS码的定义和参数：RS码是一种多进制BCH码，其定义为：设f(x)为伽罗华域GF(q)(q为任一素数的任意次幂)上小于n阶的多项式，α为GF(q)的本原元素，则当且仅当α，α²，…，α^d-1(d为不小于2的整数)皆为f(x)的根时，集合{f(x)}是一个RS码，或者说该RS码是以g(x)＝(x-α)(x-α²)…(x-α^d-1)为生成多项式且码多项式的根域和符号域一致(都在GF(q)上)的多元BCH码。纠t个符号错误的RS码的参数有：码长n＝q-1，信息符号数目k，校验符号数目n-k＝2t，以及码的最小距离d＝2t+1。

常规的纠错译码方法：

设码元符号在传输或存储过程中发生错误，错误多项式可以表示为： $E\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_2}+\·\·\·+e_{i_v}{x}^{i_v}---\left(1\right)$ 式中，ν是实际发生的错误个数，0≤ν≤t；

表示第r个错误的值；i_r表示第r个错误的位置。在发送端(n，k)RS码多项式为C(x)＝c_n-1x^n-1+c_h-2x^n-2+…+c₁x+c₀，该多项式经过调制后在噪声信道中传输。在接收端，经过解调后得到接收多项式。因此接收多项式可表示为：

R(x)＝C(x)+E(x)    (2)根据接收多项式得到伴随式为：S_j＝R(α^j)(1≤j≤2t)。根据RS码的定义知α^j(1≤j≤2t)为生成多项式g(x)的根，而码多项式C(x)为g(x)的倍式，因此C(α^j)＝0，(1≤j≤2t)。从而可以得到伴随式与错误多项式的关系为：

S_j＝R(α^j)＝C(α^j)+E(α^j)＝E(α^j)(1≤j≤2t)    (3)

为了方便起见，定义 $Y_r=e_{i_r}$ (r＝1，2，…，ν)为错误值； $X_r={\mathrm{\α}}^{i_r}$ (r＝1，2，…，ν)为错误位置，则： $E\left({\mathrm{\α}}^j\right)=e_{i_1}{\left({\mathrm{\α}}^j\right)}^{i_1}+e_{i_2}{\left({\mathrm{\α}}^j\right)}^{i_2}+\·\·\·+e_{i_v}{\left({\mathrm{\α}}^j\right)}^{i_v}$ $=e_{i_1}{\left({\mathrm{\α}}^{i_1}\right)}^j+e_{i_2}{\left({\mathrm{\α}}^{i_2}\right)}^j+\·\·\·+e_{i_v}{\left({\mathrm{\α}}^{i_v}\right)}^j---\left(4\right)$ $=Y_1{X}_1^j+Y_2{X}_2^j+\·\·\·+Y_v{X}_v^j$ 将(4)式代入(3)式并将所得的式子展开，得到2t个方程式：

上面方程组中有2t个方程，只有不到2t个未知数，而且X₁，X₂，…，X_ν在方程式中构成一个始终可逆的范德蒙矩阵，因此方程有解。常规译码方法采用比如Berlekamp迭代方法来解这个方程组首先得到错误位置然后再代入(5)式求得错误图样值，最后进行纠错。这类方法对于纠正随机错误以及随机和短突发的混合错误非常有效。但是它只能够纠正最大长度为t的突发，而且方程组(5)还是一个非线性方程，译码方法复杂度很大，因此不适合于纠正长突发错误。

现有的采用RS码纠正长突发错误的方法主要有两种：方法一是采用编码交织技术，它主要是通过交织把多个短码组成一个长码。例如，对(n，k)线性码进行j级交织，可以得到(jn，jk)码。假如原来的(n，k)码纠突发错误的能力为t，则交织后得到的(jn，jk)码纠突发错误的能力为jt。这种做法实际上是把突发错误打散成随机错误并使之均匀分布到各个短码中去。其优点是在保持信息率不变的情况下提高了RS码纠长突发错误的能力。但是，由于在码矢量编码后和解码前要分别进行交织和解交织，因此会带来比较大的传输延时，并且增加系统实现的复杂度。方法二是采用降低信息率的方法来提高码矢量的纠错能力。比如在保持码长不变的前提下通过减少信息位的长度来增加监督位的长度，或者在保持信息位长度不变的前提下通过增加码长来增加监督位的长度。这种方法在保证不增加传输延时的前提下通过牺牲信息传输速率使得码矢量空间的最小距离加大，从而提高了纠错能力。

发明内容

本发明的目的在于克服已有技术的不足之处，提出一种采用里德-索洛门码的长突发纠错译码方法，通过利用突发错误的特性，以相对于上述方法一小得多的译码延时和以相对于上述方法二高得多的信息传输速率，实现适合于长突发错误的纠错译码。

本发明提出的一种采用里德-索洛门码的长突发纠错译码方法，包括以下步骤：1)进行初始化：设置当前最大可能的错误图样的突发长度ν_m的值为2t，突发图样Y_m的值为0，最低突发位置N_m的值为0；同时移位计数变量N_c的值设置为0；2)开始接收传输信息系列，得到接收多项式R(x)为： $R\left(x\right)=C\left(x\right)+E\left(x\right)=c_{n-1}{x}^{n-1}+\·\·\·+{(c}_{i_1+v}+e_v)x^{i_1+v}+\·\·\·+(c_{i_1}+e_1)x^{i_1}+\·\·\·+c_0,$ 式中，C(x)为(n，k)RS码多项式：C(x)＝c_n-1x^n-1+c_n-2x^n-2+…+c₁x+c₀，E(x)为错误多项式： $E\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_1+1}+\·\·\·+e_{i_v}{x}^{i_1+v-1},$ 其中i₁为长突发错误在码矢量中的最低位置，ν为突发长度；并计算其相应的伴随式S_j＝R(α^j)(1≤j≤2t)，α为伽罗华域GF(q)的本原元素；3)对上一步所得的伴随式进行判断：如果伴随式不等于零，则下一步转移到步骤4，否则下一步跳转到步骤9；4)计算突发图样Y_c： $\left[\begin{array}{c}{Y}_1\\ Y_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]={\left[\begin{array}{cccc}{\mathrm{\α}}^0& \mathrm{\α}& ...& {\mathrm{\α}}^{(2t-1)}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^2& ...& {\mathrm{\α}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^{2t}& ...& {\mathrm{\α}}^{2t(2t-1)}\end{array}\right]}^{-1}\left[\begin{array}{c}{S}_1^{\′}\\ S_2^{\′}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\′}\end{array}\right],$ 这里S^′ _j＝S_j(1≤j≤2t)并计算相应的突发长度ν_c，这里ν_c为突发图样Y_c中最大的非零元素距离；5)比较ν_c与ν_m的大小：如果ν_c＜ν_m，下一步转移到步骤6，否则下一步跳转到步骤7；6)Y_c、ν_c、N_c是当前最大可能的突发图样的参数，分别用它们的值覆盖掉Y_m、ν_m、N_m的值；7)判断N_c的值是否大于码长n：如果是，则下一步转移到步骤9；否则转移到步骤8；8)接收多项式循环右移2t-ν_max+1个码字长度并计算对应的伴随式，即计算 $S_j^{\′}=\frac{S_j}{{\left({\mathrm{\α}}^j\right)}^{{2t-v}_{\max }+1}}$ (在译码过程中也可以采用循环左移为的方法，每次将接收多项式循环左移2t-ν_max+1个码字长度，即计算 $S_j^{\′}=S_j\·{\left({\mathrm{\α}}^j\right)}^{{2t-v}_{\max }+1}),$ 同时将移位计数变量N_c的值增加2t-ν_max+1，然后下一步返回到步骤4；9)根据错误图样Y_m和错误位置N_m的值进行纠错，同时输出纠错后的信息系列；该步骤完成后，转移到步骤10；10)判断译码过程是否结束：如果是，结束译码过程；否则下一步跳回到步骤1，重新开始下一个码矢量的译码。

本发明所述方法的原理及采用的算法说明如下：

首先考虑长突发错误，其多项式可以表示为： $E\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_1+1}+\·\·\·+e_{i_v}{x}^{i_1+v-1}---\left(6\right)$

其中i₁为长突发错误在码矢量中的最低位置，ν为突发长度。由于RS码具有循环码的性质，即将编码后得到的码矢量循环移位，得到的新矢量仍然是一个码矢量。因此接收矢量 $R\left(x\right)=C\left(x\right)+E\left(x\right)=c_{n-1}{x}^{n-1}+\·\·\·+{(c}_{i_1+v}+e_v)x^{i_1+v}+\·\·\·+(c_{i_1}+e_1)x^{i_1}+\·\·\·+c_0---(7)$

经过向左移位n-i₁个码元长度(也可以向右循环移位i₁个码元长度)，可以得到突发最低位为x⁰＝1的接收多项式： $R^{\′}\left(x\right)=R\left(x\right)\·x^{n-i_1}=C\left(x\right)\·x^{n-i_1}+E\left(x\right)\·x^{n-i_1}=C^{\′}\left(x\right)+E^{\′}\left(x\right)---\left(8\right)$ 由于C′(x)仍然是一个码矢量，因此可以用(3)、(8)式计算R′(x)的伴随式。通过计算得到R′(x)对应的伴随式为：

S^′ _j＝S_j·(α^j)^n-i(1≤j≤2t)    (9)。

将上述的ν扩展到2t，如果实际的突发长度ν小于2t，则其余2t-ν个突发单元的值为0。这样结合(6)式，(9)式可以写成：其中突发图样的最低位为x⁰，即X₁＝α⁰＝1。由此(10)式可以改写为： $\left[\begin{array}{c}{S}_1^{\′}\\ S_2^{\′}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\′}\end{array}\right]=\left[\begin{array}{cccc}{\mathrm{\α}}^0& \mathrm{\α}& ...& {\mathrm{\α}}^{(2t-1)}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^2& ...& {\mathrm{\α}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^{2t}& ...& {\mathrm{\α}}^{2t(2t-1)}\end{array}\right]\left[\begin{array}{c}{Y}_1\\ Y_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]---\left(11\right)$ 式中的系数矩阵是一个非奇异范德蒙矩阵且α⁰，α¹，…，α^(2t-1)为互不相同的根，该系数矩阵可逆。因而，有： $\left[\begin{array}{c}{Y}_1\\ Y_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]={\left[\begin{array}{cccc}{\mathrm{\α}}^0& \mathrm{\α}& ...& {\mathrm{\α}}^{(2t-1)}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^2& ...& {\mathrm{\α}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^{2t}& ...& {\mathrm{\α}}^{2t(2t-1)}\end{array}\right]}^{-1}\left[\begin{array}{c}{S}_1^{\′}\\ S_2^{\′}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\′}\end{array}\right]---\left(12\right)$

注意，上式中的方程组中突发图样的长度由常规译码方程的t增加到了2t；求解方程由非线性方程(5)变为线性方程(12)且系数矩阵为满秩矩阵，伴随式和突发图样之间一一对应。这意味着如果接收多项式中包含有突发错误，则经过适当的循环移位后突发错误的最低位一定可以移到x⁰，此时突发图样可以用(12)式算出。

假设在实际应用中出现的最大突发长度为ν_max，在伴随式不等于零时，循环移动2t-ν_max+1个符号位然后计算相应的突发图样，如此重复 $\left[\frac{n+2t-v_{\max }}{2t-v_{\max }+1}\right]$ 次，则实际发生的突发图样一定包含在所得到的 $\left[\frac{n+2t-v_{\max }}{2t-v_{\max }+1}\right]$ 个突发图样中。根据最大似然译码准则，可以选取这些突发图样中突发长度最短的作为译码所求得的突发图样，并用它来对信息系列进行纠错。

由于(n，k)RS码的码间最小距离为d＝n-k+1＝2t+1，因此在突发长度小于或等于t时采用本译码方法不存在译码错误，当突发长度大于t而小于或等于2t时，则在译码过程中有可能找到比实际突发长度更短的突发，此时将发生译码错误。但是采用本发明的译码方法其错误概率仍然是很低的。作为一个例子，(255，223)RS码的特定突发下的错误译码概率如表1所示，其中ν_max＝2t＝32。这里需要说明的是当实际突发长度等于2t时，由于译码过程中所算得的突发图样都不大于2t，因此无法正确译码，错误译码概率为1。由表1可见，在突发长度为28个符号(等于224比特)时，本译码方法的错误概率可以低至10^-8量级。

          表1(255，223)RS码在不同突发长度下的错误译码概率。

突发长度(符号)	错误译码概率	突发长度(符号)	错误译码概率
				17	8.4×10-35	25	1.4×10-15
18	2.1×10-32	26	3.4×10-13
				19	5.3×10-30	27	8.6×10-11
20	1.3×10-27	28	2.2×10-8
				21	3.4×10-25	29	5.4×10-6
22	8.5×10-23	30	1.4×10-3
				23	2.1×10-20	31	0.34
24	5.4×10-18	32	1.0

可见，采用本方法能够以很高的准确性纠正长度接近2t的长突发错误，因此大大提高了RS码纠正长突发错误的能力。

本发明的效果是，通过利用突发错误的特点，使得RS码能够纠正的长突发错误的长度由传统译码方法的t增加到接近2t，其纠错能力提高了将近一倍。同时，与已有的方法一相比，它减少了交织和解交织所带来的延时，与已有的方法二相比，它没有损失信息传输速率；此外该方法还把传统方法所采用的解非线性方程组的复杂方法简化成了解线性方程组的译码方法，既降低了译码方法的复杂度，使之便于硬件实现，又有利于采用提高电路工作频率的办法进一步降低译码延时。因此，在RS码应用于纠正长突发错误时，本译码方法的性能明显优于其他方法。

附图说明

图1为本发明的软件实现流程框图。

图2为按照本发明方法设计的译码器的方框图。

图3为应用本发明方法的纠正长突发错误的通信系统图。

图4为采用本译码方法的RS码作为外码和采用卷积码作为内码组成的级联码应用于复合信道的通信系统框图。

具体实施方式

下面，根据附图和两个实施例更加详细地解释本发明：

实施例一：本实施例为采用软件实现本发明提出的纠错译码方法，如图1所示。本实施例采用(255，223)RS码，最大可纠正突发长度为28个码字的译码算法，译码过程包括以下步骤：译码开始后，译码器从步骤1a转移到步骤1b，进行初始化：设置当前最大可能的错误图样的突发长度ν_m的值为32，突发图样Y_m的值为0，最低突发位置N_m的值为0；同时移位计数变量N_c的值设置为0；然后译码器转移到步骤1c，开始接收传输信息系列R(x)，并用(3)式计算其相应的伴随式S_j(1≤j≤32)；做完这一步以后译码器转到步骤1d，对上一步所得的伴随式进行判断：如果伴随式不等于零，则下一步转移到步骤1e，否则下一步跳转到步骤1j。在步骤1e，用(12)式计算突发图样Y_c(这里S′_j＝S_j(1≤j≤32))并计算相应的突发长度ν_c。然后译码器由步骤1e转移到步骤1f，比较ν_c与ν_m的大小：如果ν_c＜ν_m，下一步转移到步骤1g，否则下一步跳转到步骤1h。在步骤1g中，Y_c、ν_c、N_c是当前最大可能的突发图样的参数，分别用它们的值覆盖掉Y_m、ν_m、N_m的值。随后，译码器转移到步骤1h，判断N_c的值是否大于255：如果是，则下一步转移到步骤1j；否则转移到步骤1i。在步骤1i，译码器将接收多项式循环右移5个码字长度并计算对应的伴随式，即计算 $S_j^{\′}=\frac{S_j}{{\left({\mathrm{\α}}^j\right)}^5}$ (1≤j≤32)(在译码过程中也可以采用循环左移为的方法，每次将接收多项式循环左移5个码字长度，即计算S′_j＝S_j·(α^j)⁵(1≤j≤32))，同时将移位计数变量的值增加5，然后下一步返回到步骤1e。在步骤1j，译码器根据错误图样Y_m和错误位置N_m的值进行纠错，同时输出纠错后的信息系列。完成步骤1j的操作以后，译码器转移到步骤1k，判断译码过程是否结束：如果是，则下一步转移到步骤1l，结束译码过程；否则下一步跳回到步骤1b，重新开始下一个码矢量的译码。

实施例二：本实施例为采用硬件的方法实现本发明的译码方法。本实施例仍然采用(255，223)RS码、最大可纠正突发长度为28个码字的译码算法，该硬件电路的组成及译码工作过程：如图2所示，在码流21的输入过程中，32个伴随式计算及移位寄存电路22-24处于计算伴随式状态，输入码流的信息部分被同步地暂存到容量为223个码字的存储器25中。在这个期间内右边部分的译码电路完成初始化：突发图样寄存器29置0值，突发长度计算及比较电路2a中的寄存器置初值为32，突发最低位存储器2b的值置为0，移位计数器2c复位为0状态。当一个码多项式被接收完毕，译码器切换成计算突发图样状态。此时32个伴随式计算及移位电路22-24工作在移位状态，每到来一个时钟脉冲伴随式电路完成一次移位运算，同时移位计数器加5，所得新伴随式的值通过由组合逻辑电路构成的矩阵乘法电路26完成(12)式的运算而得到相应的突发图样27、28。其中突发图样28输出到突发长度计算及比较电路2a进行突发长度计算，并与这部分电路中的寄存器值进行比较。如果算得的突发长度小于寄存器值，则将突发长度值取代寄存器值的同时使比较结果输出高电平，使得突发图样寄存器用突发图样27覆盖掉原来的图样值，同时突发最低位置存储器载入移位计数器2c的当前值作为相应的突发最低位置。如此循环工作直到移位计数器2c的值大于码长255，随后译码电路左边部分21-25转入接收状态；同时右边电路25-2d转入纠错输出状态：信息队列依时钟节拍从存储器25输出，突发最低位置存储器2b在突发位置上使能突发图样寄存器29和二选一选择器2d，使突发图样输出与信息系列相加完成纠错。

从上面的实施例可见，本译码方法与前面介绍过的两种方法所采用的常规纠错译码方法相比不但纠错能力强、延时小，而且实现也简单。下面再通过两个例子来说明本发明在通信系统中的应用。

例一，参照图3，纠正长突发错误的通信系统包括一个产生数字信息流的信源31，RS编码器33，突发信道35，以及如图2所示的纠正突发错误译码器37。在本例中，信源31产生的携带信息的数据符号流32被送往RS码编码器33，RS码编码器33对信息进行信道编码。编码后的RS码流34在长突发信道35传输过程中受到干扰而产生长突发错误，包含长突发错误的码流36被纠正长突发错误的RS码译码器37所接收。经过纠正长突发错误的RS码译码器37的纠错译码，输出的码流38为正确的数字信息流。

本译码方法不仅适用于纯突发信道，还可以和其他码一起组成级联码用于纠正复合信道中出现的既有随机错误又有长突发错误的混合错误。下面给出一个例子。

例二：如图4所示，数字信源41产生的数据流依次被送到RS码编码器43和卷积码编码器45进行外码和内码的编码，随后输出的级联码流46通过复合信道47传输。由于在传输过程中受到多种因素的影响，接收到的级联码流48将包含随机错误和突发错误的复合错误，这些包含复合错误的信息流首先被送到卷积码译码器进行主要针对随机错误的纠错译码。当一段码流中只含有在卷积码纠错能力范围内的随机错误时，通过卷积码的译码可以把这些随机错误纠正过来，它的输出4a是一段正确的信息系列；当这一段码流中包含了长突发串或者随机错误的个数已经大于卷积码的纠错范围，则卷积码译码失败，它的输出4a可以认为是一个长突发错误。通过RS码的纠突发错误译码器4b进行纠错译码后，长突发错误得到纠正。显然，根据信道特性合适选取内、外码的长度及纠错能力并采用本方法作为外码的译码方法，可以得到纠错能力更强的级联码，从而在相同的信息传输速率下得到更低差错率的数据，或者在同一差错率的条件下可以采用更高的数据率进行传输。

由于RS码是BCH码的一个子类，本发明的方法完全适用于BCH码，而且还可以推广到一切循环码中去。

Claims (1)

1、一种采用里德-索洛门码的长突发纠错译码方法，包括以下步骤：1)进行初始化：设置当前最大可能的错误图样的突发长度ν_m的值为2t，突发图样Y_m的值为0，最低突发位置N_m的值为0；同时移位计数变量N_c的值设置为0；2)开始接收传输信息系列，得到接收多项式R(x)为： $R\left(x\right)=C\left(x\right)+E\left(x\right)=c_{n-1}{x}^{n-1}+\·\·\·+{(c}_{i_1+v}+e_v)x^{i_1+v}+\·\·\·+(c_{i_1}+e_i)x^{i_1}+\·\·\·+c_0,$ 式中，C(x)为(n，k)RS码多项式：C(x)＝c_n-1x^n-1+c_n-2x^n-2+…+c₁x+c₀，E(x)为错误多项式： $E\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_1+1}+\·\·\·+e_{i_v}{x}^{i_1+v-1},$ 其中i₁为长突发错误在码矢量中的最低位置，ν为突发长度；并计算其相应的伴随式S_j＝R(α^j)(1≤j≤2t)，α为伽罗华域DF(q)的本原元素；3)对上一步所得的伴随式进行判断：如果伴随式不等于零，则下一步转移到步骤4，否则下一步跳转到步骤9；4)计算突发图样Y_c： $\left[\begin{array}{c}{Y}_1\\ Y_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]={\left[\begin{array}{cccc}{\mathrm{\α}}^0& \mathrm{\α}& ...& {\mathrm{\α}}^{(2t-1)}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^2& ...& {\mathrm{\α}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\α}}^0& {\mathrm{\α}}^{2t}& ...& {\mathrm{\α}}^{2t(2t-1)}\end{array}\right]}^{-1}\left[\begin{array}{c}{S}_1^{\′}\\ S_2^{\′}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\′}\end{array}\right],$ 这里S^′ _j＝S_j(1≤j≤2t)并计算相应的突发长度ν_c，这里ν_c为突发图样Y_c中最大的非零元素距离；5)比较ν_c与ν_m的大小：如果ν_c＜ν_m，下一步转移到步骤6，否则下一步跳转到步骤7；6)Y_c、ν_c、N_c是当前最大可能的突发图样的参数，分别用它们的值覆盖掉Y_m、ν_m、N_m的值；7)判断N_c的值是否大于码长n：如果是，则下一步转移到步骤9；否则转移到步骤8；8)接收多项式循环右移2t-ν_max+1个码字长度并计算对应的伴随式，即计算 $S_j^{\′}=\frac{S_j}{{\left(a^j\right)}^{{2t-v}_{\max }+1}}$ 或在译码过程中采用循环左移为的方法，每次将接收多项式循环左移2t-ν_max+1个码字长度，即计算 $S_j^{\′}=S_j\·{\left(a^j\right)}^{{2t-v}_{\max }+1},$ 同时将移位计数变量N_c的值增加2t-ν_max+1，然后下一步返回到步骤4；9)根据错误图样Y_m和错误位置N_m的值进行纠错，同时输出纠错后的信息系列；该步骤完成后，转移到步骤10；10)判断译码过程是否结束：如果是，结束译码过程；否则下一步跳回到步骤1，重新开始下一个码矢量的译码。

Images