一种信道纠错码RS码迭代译码解关键方程方法

摘要

本发明一种信道纠错码RS码迭代译码解关键方程方法，其特点在于：对于纠错能力为t比特的RS码来说，采用改进的RiBM迭代译码方法求解关键方程，通过删除部分冗余运算，将RiBM迭代过程中的数据流位宽由3t+1压缩为2t+4，从而大大降低了运算量，提高了运算效率，实现了RS码的高效译码。

说明书

技术领域

本发明涉及一种信道纠错码RS码迭代译码解关键方程方法，属于数字通 信领域的RS迭代译码方法。

背景技术

RS码是由I.S.Reed和G.Solomon于1960年构造出来的，是一类具有很 强纠错能力的多元BCH码，它不仅能纠正随机错误，又能纠正突发错误，特 别适用于信道干扰非常复杂的通信系统，在实际工程应用中非常广泛。

图1所示为传统的RS码译码原理框图，包括计算伴随式101、求解关键 方程102、搜索错误图案103、数据缓存104、纠错输出105五个部分，译码 步骤如下：

(1)对接收到的码字R(x)进行计算，得到伴随多项式S(x)；

(2)对伴随多项式S(x)求解关键方程，得到错误位置多项式Λ(x)和错误 值多项式ω(x)；

(3)采用Chien搜索和Forney算法从错误位置多项式Λ(x)和错误值多项 式ω(x)中计算错误位置和对应的错误值，达到搜索错误图案的目的；

(4)根据得到的错误位置和错误值对经过数据缓存104的接收码字进行 纠错并输出码字C。

RS码在求解关键方程时的译码方法主要有BM(Berlekamp-Massey)法、 Euclid法等，实际使用中以BM法为主。目前最先进的BM译码方法是 D.V.Sarwate等人于2001年提出的RiBM迭代译码方法，并通过简洁的伪码形 成了一种高速高效的RS码迭代译码方法。

图2所示为D.V.Sarwate等人提出的利用RiBM迭代译码方法求解关键方 程，包括：

(1)步骤201：设RS码的纠错能力为t比特，接收2t个伴随多项式系数： s₁,s₂,…,s_2t；

(2)步骤202：对位宽为3t+1的数据流δ_i(r)赋初值：δ_i(0)＝s_i,(i＝1,2,…,2t), δ_i(0)＝0,(i＝2t+1,2t+2,…,3t),δ_3t+1(0)＝1；对中间变量赋初值：θ_i(0) ＝s_i,(i＝1,2,…,2t)，γ(0)＝1,k(0)＝0；

(3)步骤203：首轮迭代次数r初值为0，累加1后转入步骤204；从下 一轮迭代开始，将从步骤208返回的r累加1，并转入步骤204；

(4)步骤204：更新δ_i(r+1)的值，δ_i(r+1)＝γ(r)δ_i+1(r)-δ₁(r)θ_i(r), (i＝1,2,…,3t+1)；

(5)步骤205：令iter＝(δ₁(r)≠0&&k(r)≥0)，若iter＝1则转入步骤206， 若iter＝0则转入步骤207；

(6)步骤206：更新中间变量，γ(r+1)＝δ₁(r)，k(r+1)＝-k(r)-1，θ_i(r+1)＝ δ_i+1(r),(i＝1,2,…,3t+1)，更新完成之后转入步骤208；

(7)步骤207：更新中间变量，γ(r+1)＝γ(r)，k(r+1)＝k(r)+1，θ_i(r+1)＝ θ_i(r),(i＝1,2,…,3t+1)，更新完成之后转入步骤208；

(8)步骤208：比较r与2t，若r小于2t则返回步骤203，同时将步骤 206或207得到的中间变量数据流θ_i(r+1)、中间变量γ(r+1)和k(r+1)用于下一 轮迭代运算；若r等于2t，则迭代结束，转入步骤209；

(9)步骤209：输出错误位置多项式Λ(x)系数：λ_i(2t)＝ δ_i+t(2t),(i＝1,2,…,t+1)，错误值多项式ω(x)系数：ω_i(2t)＝δ_i(2t),(i＝1,2,…,t)。

RiBM迭代译码方法求解关键方程的不足之处是：对于纠错能力为t比特的 RS码来说，随着迭代的进行，数据流δ_i(r)尾部的t比特初值0形成了一定程 度的冗余运算，增加了运算量，降低了运算效率。

发明内容

本发明的技术解决问题是：克服现有技术的不足之处，提出一种改进的 RiBM迭代译码解关键方程方法，删除了数据流δ_i(r)尾部的t比特初值0在迭 代过程中形成的冗余运算，将RiBM迭代过程中的数据流δ_i(r)位宽由3t+1压缩 为2t+4，从而大大降低了运算量，提高了运算效率，实现了RS码的高效译码。

本发明的技术解决方案是：一种信道纠错码RS码迭代译码解关键方程方 法，步骤如下：

(1)设RS码的纠错能力为t比特，从计算伴随式处接收2t个伴随多项式 系数：s₁,s₂,…,s_2t；其中，t为大于0的正整数；

(2)定义迭代次数r，r为整数，初值为0；定义位宽为2t+4的数据流 δ_i(r)以及中间变量数据流θ_i(r)，对位宽为2t+4的数据流δ_i(r)赋初值： δ_i(0)＝s_i,(i＝1,2,…,2t)；δ_i(0)＝0,(i＝2t+1,2t+3,2t+4)；δ_2t+2(0)＝1；对中间变量数据 流θ_i(r)赋初值：θ_i(0)＝s_i,(i＝1,2,…,2t),θ_i(0)＝0,(i＝2t+1,2t+3,2t+4)；θ_2t+2(0)＝1； 定义中间变量γ(r)和k(r)，并赋初值：γ(0)＝1,k(0)＝0；定义迭代变量iter，则 在第r次迭代运算过程中，令iter＝(δ₁(r)≠0&&k(r)≥0)，式中，“&&”为逻辑 与运算；

(3)将步骤(2)的迭代变量iter＝(δ₁(r)≠0&&k(r)≥0)的计算结果分为 Case0、Case1和Case2三种情形；

所述Case0是：迭代变量iter在r＝0时初值为1，随着迭代次数r的累加， 迭代变量iter在1和0之间交替切换，直至迭代变量iter恒为0；

所述Case1是：当r为偶数时，迭代变量iter等于0，随着迭代次数r的 累加，当r为奇数时，出现迭代变量iter等于1的情形；设首次出现Case1情 形且迭代变量iter等于1时对应的迭代次数为r₁；

所述Case2是：当r为偶数时，迭代变量iter等于0，随着迭代次数r的 累加，当r再次为偶数时，出现迭代变量iter等于1的情形；设首次出现Case2 情形且迭代变量iter等于1时对应的迭代次数为r₂；

(4)首轮迭代次数r初值为0，累加1后转入步骤(5)；从下一轮迭代开 始，将从步骤(9)返回的r累加1，并转入步骤(5)；

(5)在步骤(3)所述的Case0情形下：

当r为奇数或r等于2t时，δ_i(r+1)＝γ(r)δ_i+1(r)-δ₁(r)θ_i(r)，(i＝1,2,…,2t+4)；

当r为偶数且r不等于2t时，若2t+2-r/2≤i≤2t+4，δ_i(r+1)更新但不传递， 即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t+1-r/2，则δ_i(r+1)需要进行补0操作， 即δ_i(r+1)＝γ(r)·0-δ₁(r)θ_i(r)；若1≤i≤2t-r/2，则δ_i(r+1)＝γ(r)δ_i+1(r)-δ₁(r) θ_i(r)；

在步骤(3)所述的Case1情形下：

当r＝r₁+1时，若2t+(5-r₁)/2≤i≤2t+4，δ_i(r+1)更新但不传递，即δ_i(r+1)＝ γ(r)δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t+(3-r₁)/2，则δ_i(r+1)接收中间变量θ_i(r)的更新值 但不传递，即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i(r)；若i＝2t+(1-r₁)/2，则δ_i(r+1)需要 进行补0操作，即δ_i(r+1)＝γ(r)·0-δ₁(r)θ_i(r)；若1≤i≤2t-(1+r₁)/2，则δ_i(r+1)＝ γ(r)δ_i+1(r)-δ₁(r)θ_i(r)；当r≠r₁+1时仍然按照Case0情形更新δ_i(r+1)的值；

在步骤(3)所述的Case2情形下：

当r＝r₂时，若2t+3-r₂/2≤i≤2t+4，δ_i(r+1)更新但不传递，即δ_i(r+1)＝γ(r) δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t+1-r₂/2或2t+2-r₂/2，则δ_i(r+1)接收中间变量θ_i(r)的 更新值但不传递，即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i(r)；若1≤i≤2t-r₂/2，δ_i(r+1)＝ γ(r)δ_i+1(r)-δ₁(r)θ_i(r)；

若r<r₂，仍然按照Case0情形更新δ_i(r+1)的值；

若r>r₂，且r为奇数或者r等于2t时，δ_i(r+1)＝γ(r)δ_i+1(r)-δ₁(r)θ_i(r)， (i＝1,2,…,2t+4)；

若r>r₂，且r为偶数但r不等于2t时，若2t+1-r/2≤i≤2t+4，δ_i(r+1)更新 但不传递，即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t-r/2，则δ_i(r+1)需要进行 补0操作，即δ_i(r+1)＝γ(r)·0-δ₁(r)θ_i(r)；若1≤i≤2t-1-r/2，δ_i(r+1)＝γ(r) δ_i+1(r)-δ₁(r)θ_i(r)；

(6)根据步骤(2)中的迭代变量iter决定中间变量数据流θ_i(r+1)、中间 变量γ(r+1)和k(r+1)的更新方式，若iter＝1则转入步骤(7)，若iter＝0则转入 步骤(8)；

(7)更新中间变量γ(r+1)和k(r+1)，γ(r+1)＝δ₁(r)，k(r+1)＝-k(r)-1，根 据步骤(3)的Case0、Case1和Case2三种情形，分别更新中间变量数据流 θ_i(r+1)：

在Case0情形下，θ_i(r+1)＝δ_i+1(r)，(i＝1,2,…,2t+4)；

在Case1情形下，当r＝r₁+1时，若2t+(3-r₁)/2≤i≤2t+4，θ_i(r+1)取当前 δ_i(r)的值，即θ_i(r+1)＝δ_i(r)；若i＝2t+(1-r₁)/2，则θ_i(r+1)需要进行补0操作， 即θ_i(r+1)＝0；若1≤i≤2t-(1+r₁)/2，θ_i(r+1)＝δ_i+1(r)；当r≠r₁+1时仍然按照 Case0情形更新θ_i(r+1)的值；

在Case2情形下，当r＝r₂时，若2t+1-r₂/2≤i≤2t+4，θ_i(r+1)取当前δ_i(r) 的值，即θ_i(r+1)＝δ_i(r)；若1≤i≤2t-r₂/2，θ_i(r+1)＝δ_i+1(r)；

当r≠r₂时，若2t+1-r/2≤i≤2t+4，θ_i(r+1)取当前δ_i(r)的值，即θ_i(r+1)＝ δ_i(r)；若i＝2t-r/2，则θ_i(r+1)需要进行补0操作，即θ_i(r+1)＝0；若1≤i≤2t-1-r/2， θ_i(r+1)＝δ_i+1(r)；

当中间变量数据流θ_i(r+1)、中间变量γ(r+1)和k(r+1)更新完成后转入步骤 (9)；

(8)更新中间变量γ(r+1)和k(r+1)，γ(r+1)＝γ(r)，k(r+1)＝k(r)+1；根据 步骤(3)的Case0和Case2两种情形，分别更新中间变量数据流θ_i(r+1)：

在Case0情形下，当r为奇数或者r等于2t时，θ_i(r+1)＝θ_i(r)， (i＝1,2,…,2t+4)；

当r为偶数且r不等于2t时，若2t+2-r/2≤i≤2t+4，θ_i(r+1)＝θ_i-1(r)；若1 ≤i≤2t+1-r/2，θ_i(r+1)＝θ_i(r)；

在Case2情形下，当r＝r₂时，若2t+2-r₂/2≤i≤2t+4，θ_i(r+1)＝θ_i-1(r)；若 1≤i≤2t+1-r₂/2，θ_i(r+1)＝θ_i(r)；

当r≠r₂时，θ_i(r+1)＝θ_i(r)，(i＝1,2,…,2t+4)；

当中间变量数据流θ_i(r+1)、中间变量γ(r+1)和k(r+1)更新完成后转入步骤 (9)；

(9)比较本轮的r与2t，若r小于2t则返回步骤(4)，直至r等于2t， 则迭代结束，输出错误位置多项式Λ(x)系数：λ_i(2t)＝δ_i+t(2t),(i＝1,2,…,t+1)， 错误值多项式ω(x)系数：ω_i(2t)＝δ_i(2t),(i＝1,2,…,t)。

本发明与现有技术相比的有益效果是：

(1)与RiBM迭代译码解关键方程方法相比，本发明将RiBM迭代过程中 的数据流δ(r)位宽由3t+1压缩为2t+4，删除了数据流δ(r)尾部的t比特初值0 在迭代过程中形成的冗余运算，从而大大降低了运算量，提高了运算效率，实 现了RS码的高效译码。

(2)本发明通过对数据流δ(r)以及中间变量数据流θ(r)更新过程中的精细 化设计，达到了删除迭代过程中冗余运算的目的，形成了一种新的RS码迭代 译码解关键方程方法。

附图说明

图1为RS码译码原理框图；

图2为RiBM迭代译码解关键方程方法；

图3为Case0情形下RiBM迭代译码解关键方程方法δ(r)数据流图；

图4为Case0情形下本发明迭代译码解关键方程方法δ(r)数据流图；

图5为Case1情形下RiBM迭代译码解关键方程方法δ(r)数据流图；

图6为Case1情形下本发明迭代译码解关键方程方法δ(r)数据流图；

图7为Case2情形下RiBM迭代译码解关键方程方法δ(r)数据流图；

图8为Case2情形下本发明迭代译码解关键方程方法δ(r)数据流图；

图9为本发明RS码迭代译码解关键方程方法；

图10为图9中δ(r)更新过程；

图11为图9中iter为1时θ(r)更新过程；

图12为图9中iter为0时θ(r)更新过程。

具体实施方式

图9为本发明RS码迭代译码解关键方程方法，步骤如下：

(1)步骤901：设RS码的纠错能力为t比特，从计算伴随式处接收2t 个伴随多项式系数：s₁,s₂,…,s_2t；其中，t为大于0的正整数；

(2)步骤902：定义迭代次数r，r为整数，初值为0；定义位宽为2t+4 的数据流δ_i(r)以及中间变量数据流θ_i(r)，对位宽为2t+4的数据流δ_i(r)赋初值： δ_i(0)＝s_i,(i＝1,2,…,2t)；δ_i(0)＝0,(i＝2t+1,2t+3,2t+4)；δ_2t+2(0)＝1；对中间变量数据 流θ_i(r)赋初值：θ_i(0)＝s_i,(i＝1,2,…,2t),θ_i(0)＝0,(i＝2t+1,2t+3,2t+4)；θ_2t+2(0)＝1； 定义中间变量γ(r)和k(r)，并赋初值：γ(0)＝1,k(0)＝0；定义迭代变量iter，则 在第r次迭代运算过程中，令iter＝(δ₁(r)≠0&&k(r)≥0)，式中，“&&”为逻辑 与运算；

(3)步骤903：将步骤902的迭代变量iter＝(δ₁(r)≠0&&k(r)≥0)的计算 结果分为Case0、Case1和Case2三种情形；

所述Case0是：迭代变量iter在r＝0时初值为1，随着迭代次数r的累加， 迭代变量iter在1和0之间交替切换，直至迭代变量iter恒为0；

所述Case1是：当r为偶数时，迭代变量iter等于0，随着迭代次数r的 累加，当r为奇数时，出现迭代变量iter等于1的情形；设首次出现Case1情 形且迭代变量iter等于1时对应的迭代次数为r₁；

所述Case2是：当r为偶数时，迭代变量iter等于0，随着迭代次数r的 累加，当r再次为偶数时，出现迭代变量iter等于1的情形；设首次出现Case2 情形且迭代变量iter等于1时对应的迭代次数为r₂；

(4)步骤904：首轮迭代次数r初值为0，累加1后转入步骤905；从下 一轮迭代开始，将从步骤909返回的r累加1，并转入步骤905；

(5)步骤905：在步骤903所述的Case0情形下：

当r为奇数或r等于2t时，δ_i(r+1)＝γ(r)δ_i+1(r)-δ₁(r)θ_i(r)，(i＝1,2,…,2t+4)；

当r为偶数且r不等于2t时，若2t+2-r/2≤i≤2t+4，δ_i(r+1)更新但不传递， 即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t+1-r/2，则δ_i(r+1)需要进行补0操作， 即δ_i(r+1)＝γ(r)·0-δ₁(r)θ_i(r)；若1≤i≤2t-r/2，则δ_i(r+1)＝γ(r)δ_i+1(r)-δ₁(r) θ_i(r)；如图10中1001所示；

在步骤903所述的Case1情形下：

当r＝r₁+1时，若2t+(5-r₁)/2≤i≤2t+4，δ_i(r+1)更新但不传递，即δ_i(r+1)＝ γ(r)δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t+(3-r₁)/2，则δ_i(r+1)接收中间变量θ_i(r)的更新值 但不传递，即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i(r)；若i＝2t+(1-r₁)/2，则δ_i(r+1)需要 进行补0操作，即δ_i(r+1)＝γ(r)·0-δ₁(r)θ_i(r)；若1≤i≤2t-(1+r₁)/2，则δ_i(r+1)＝ γ(r)δ_i+1(r)-δ₁(r)θ_i(r)；当r≠r₁+1时仍然按照Case0情形更新δ_i(r+1)的值； 如图10中1002所示；

在步骤903所述的Case2情形下：

当r＝r₂时，若2t+3-r₂/2≤i≤2t+4，δ_i(r+1)更新但不传递，即δ_i(r+1)＝γ(r) δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t+1-r₂/2或2t+2-r₂/2，则δ_i(r+1)接收中间变量θ_i(r)的 更新值但不传递，即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i(r)；若1≤i≤2t-r₂/2，δ_i(r+1)＝ γ(r)δ_i+1(r)-δ₁(r)θ_i(r)；

若r<r₂，仍然按照Case0情形更新δ_i(r+1)的值；

若r>r₂，且r为奇数或者r等于2t时，δ_i(r+1)＝γ(r)δ_i+1(r)-δ₁(r)θ_i(r)， (i＝1,2,…,2t+4)；

若r>r₂，且r为偶数但r不等于2t时，若2t+1-r/2≤i≤2t+4，δ_i(r+1)更新 但不传递，即δ_i(r+1)＝γ(r)δ_i(r)-δ₁(r)θ_i-1(r)；若i＝2t-r/2，则δ_i(r+1)需要进行 补0操作，即δ_i(r+1)＝γ(r)·0-δ₁(r)θ_i(r)；若1≤i≤2t-1-r/2，δ_i(r+1)＝γ(r) δ_i+1(r)-δ₁(r)θ_i(r)；如图10中1003所示；

(6)步骤906：根据步骤902中的迭代变量iter决定中间变量数据流 θ_i(r+1)、中间变量γ(r+1)和k(r+1)的更新方式，若iter＝1则转入步骤907，若 iter＝0则转入步骤908；

(7)步骤907：更新中间变量γ(r+1)和k(r+1)，γ(r+1)＝δ₁(r)， k(r+1)＝-k(r)-1，根据步骤903的Case0、Case1和Case2三种情形，分别更 新中间变量数据流θ_i(r+1)：

在Case0情形下，θ_i(r+1)＝δ_i+1(r)，(i＝1,2,…,2t+4)；如图11中1101所 示；

在Case1情形下，当r＝r₁+1时，若2t+(3-r₁)/2≤i≤2t+4，θ_i(r+1)取当前 δ_i(r)的值，即θ_i(r+1)＝δ_i(r)；若i＝2t+(1-r₁)/2，则θ_i(r+1)需要进行补0操作， 即θ_i(r+1)＝0；若1≤i≤2t-(1+r₁)/2，θ_i(r+1)＝δ_i+1(r)；当r≠r₁+1时仍然按照 Case0情形更新θ_i(r+1)的值；如图11中1102所示；

在Case2情形下，当r＝r₂时，若2t+1-r₂/2≤i≤2t+4，θ_i(r+1)取当前δ_i(r) 的值，即θ_i(r+1)＝δ_i(r)；若1≤i≤2t-r₂/2，θ_i(r+1)＝δ_i+1(r)；

当r≠r₂时，若2t+1-r/2≤i≤2t+4，θ_i(r+1)取当前δ_i(r)的值，即θ_i(r+1)＝ δ_i(r)；若i＝2t-r/2，则θ_i(r+1)需要进行补0操作，即θ_i(r+1)＝0；若1≤i≤2t-1-r/2， θ_i(r+1)＝δ_i+1(r)；如图11中1103所示；

当中间变量数据流θ_i(r+1)、中间变量γ(r+1)和k(r+1)更新完成后转入步骤 909；

(8)步骤908：更新中间变量γ(r+1)和k(r+1)，γ(r+1)＝γ(r)， k(r+1)＝k(r)+1；根据步骤903的Case0和Case2两种情形，分别更新中间变 量数据流θ_i(r+1)：

在Case0情形下，当r为奇数或者r等于2t时，θ_i(r+1)＝θ_i(r)， (i＝1,2,…,2t+4)；

当r为偶数且r不等于2t时，若2t+2-r/2≤i≤2t+4，θ_i(r+1)＝θ_i-1(r)；若1 ≤i≤2t+1-r/2，θ_i(r+1)＝θ_i(r)；如图12中1201所示；

在Case2情形下，当r＝r₂时，若2t+2-r₂/2≤i≤2t+4，θ_i(r+1)＝θ_i-1(r)；若 1≤i≤2t+1-r₂/2，θ_i(r+1)＝θ_i(r)；

当r≠r₂时，θ_i(r+1)＝θ_i(r)，(i＝1,2,…,2t+4)；如图12中1202所示；

当中间变量数据流θ_i(r+1)、中间变量γ(r+1)和k(r+1)更新完成后转入步骤 909；

(9)步骤909：比较本轮的r与2t，若r小于2t则返回步骤904，直至r 等于2t，则迭代结束，转入步骤910；

(10)步骤910：输出错误位置多项式Λ(x)系数：λ_i(2t)＝ δ_i+t(2t),(i＝1,2,…,t+1)，错误值多项式ω(x)系数：ω_i(2t)＝δ_i(2t),(i＝1,2,…,t)。

图3所示为Case0情形下RiBM迭代译码解关键方程方法δ(r)数据流图， δ(r)赋初值后，随着迭代次数r的增加不断更新，当r＝2t时迭代完成，输出错 误值多项式ω(x)系数303和错误位置多项式Λ(x)系数304。图3中全0块301 和全0块302即为本发明在Case0情形下将要删除的冗余运算。

图4所示为Case0情形下本发明迭代译码解关键方程方法δ(r)数据流图， 图4删除了图3中的全0块301和全0块302，数据δ(r)位宽由3t+1压缩为 2t+4。

为方便表述，以r＝2为例进行说明，此时r＝1时的δ(r)数据流是r＝2迭代 运算的初值。删除全0块301后，当r＝2时，数据δ(r)的运算结果仍然保留有 0值305，设0值305处于数据δ(r)的第i位，则第i位需要进行补0操作才能 得出0值305，即δ_i(r+1)＝γ(r)·0-δ₁(r)θ_i(r)；第i位左侧的低位数据(以第 j位为例)更新方式为：δ_j(r+1)＝γ(r)δ_j+1(r)-δ₁(r)θ_j(r)；第i位右侧的高位数 据(以第m位为例)更新但不往左传递，即以δ_m(r+1)＝γ(r)δ_m(r)-δ₁(r)θ_m-1(r) 的方式进行更新。r＝2时的运算结果即为r＝3时运算的初值，当r＝3时，0值 305的存在使得第j位数据δ_j(r+1)的更新方式为：δ_j(r+1)＝γ(r)δ_j+1(r)-δ₁(r) θ_j(r)。

以此类推，当r为偶数且r不等于2t时，均要进行类似r＝2时操作；当r 为奇数或者r等于2t时，第j位数据δ_j(r+1)的更新方式为：δ_j(r+1)＝γ(r)δ_j+1(r)- δ₁(r)θ_j(r)。全0块401是给Case1和Case2情形下的设计留的余量。

图5所示为Case1情形下RiBM迭代译码解关键方程方法δ(r)数据流图， δ(r)赋初值后，随着迭代次数r的增加不断更新，当r＝2t时迭代完成，输出错 误值多项式ω(x)系数503和错误位置多项式Λ(x)系数504。图5中全0块501 和全0块502即为本发明在Case1情形下将要删除的冗余运算。和全0块301 相比，在第i+1次迭代时，全0块501左侧少删一个0，右侧多删一个0；在 第i+2次迭代时，全0块501左侧少删一个0。和全0块302相比，在第i+1 和i+2次迭代过程中，全0块502左侧各少删一个0。

图6所示为Case1情形下本发明迭代译码解关键方程方法δ(r)数据流图， 图6删除了图5中的全0块501和全0块502，数据δ(r)位宽由3t+1压缩为 2t+4。

假设在Case1情形下，首次出现δ₁(r)不等于0时迭代次数为r＝i，则在第 i+1次迭代中，由于数据505不能被删除，因此数据506出现在了图6中的第 2t+3列601上。由于r＝i时的δ(r)数据流是r＝i+1迭代运算的初值，因此为计 算数据505，需要在第2t+(1-i)/2位进行补0操作，即δ_2t+(1-i)/2(r+1)＝γ(r)·0- δ₁(r)θ_2t+(1-i)/2(r)；为计算数据508，数据507接收第3t+1-i位中间变量θ(r)的 更新值但不往左传递，即δ_3t+1-i(r+1)＝γ(r)δ_3t+1-i(r)-δ₁(r)θ_3t+1-i(r)；第2t+(1-i)/2 位左侧的低位数据(以第j位为例)更新方式为：δ_j(r+1)＝γ(r)δ_j+1(r)-δ₁(r) θ_j(r)；第3t+1-i位右侧的高位数据(以第m位为例)接收第m-1位中间变量 θ(r)的更新值但不往左传递，即以δ_m(r+1)＝γ(r)δ_m(r)-δ₁(r)θ_m-1(r)的方式进行 更新。当r≠i+1时仍然按照Case0情形更新δ(r)的值。

图7所示为Case2情形下RiBM迭代译码解关键方程方法δ(r)数据流图， δ(r)赋初值后，随着迭代次数r的增加不断更新，当r＝2t时迭代完成，输出错 误值多项式ω(x)系数703和错误位置多项式Λ(x)系数704。图7中全0块701 和全0块702即为本发明在Case2情形下将要删除的冗余运算。

假设在Case2情形下，首次出现δ₁(r)不等于0时迭代次数为r＝i。和全0 块301相比，全0块701在第i+1、i+2和i+3次迭代过程中0的数目不同，图 7中全0块705、全0块706和全0块707中0的数目相同，均为t-2-i/2个。 和全0块302相比，全0块702也在第i+1、i+2和i+3次迭代过程中0的数目 不同。

图8所示为Case2情形下本发明迭代译码解关键方程方法δ(r)数据流图， 图8删除了图7中的全0块701和全0块702，并保留了全0块706中的一个 0，数据δ(r)位宽由3t+1压缩为2t+4。

假设在Case2情形下，首次出现δ₁(r)不等于0时迭代次数为r＝i，则在第 i+1次迭代过程中，尾部有效数据流出现在了图8中的第2t+3列801和第2t+4 列802上；在第i+2次迭代过程中，尾部有效数据流出现在了图8中的第2t+3 列801上。

当r＝i时，由于r＝i-1时的δ(r)数据流是r＝i迭代运算的初值，需要将r＝i-1 时的第2t+1-i/2位和第3t-i+2位数据执行接收当前中间变量θ(r)的更新值但不 往左传递的运算，即δ_2t+1-i/2(r+1)＝γ(r)δ_2t+1-i/2(r)-δ₁(r)θ_2t+1-i/2(r)，δ_3t-i+2(r+1)＝ γ(r)δ_3t-i+2(r)-δ₁(r)θ_3t-i+2(r)；第2t+1-i/2位左侧的低位数据(以第j位为例)更 新方式为：δ_j(r+1)＝γ(r)δ_j+1(r)-δ₁(r)θ_j(r)；第3t-i+2位右侧的高位数据(以 第m位为例)接收第m-1位中间变量θ(r)的更新值但不往左传递，即δ_m(r+1)＝ γ(r)δ_m(r)-δ₁(r)θ_m-1(r)。

当r<i时，仍然按照Case0情形更新δ(r)的值；

当r>i，且r为奇数或者r等于2t时，以第j位为例，数据更新方式为： δ_j(r+1)＝γ(r)δ_j+1(r)-δ₁(r)θ_j(r)；

当r>i+1，且r为偶数但r不等于2t时，以r＝i+2为例，因全0块706仍然 保留了一个0值803，且该0值803处于第2t+1-i/2位，则第2t+1-i/2位需要 进行补0操作，即δ_2t+1-i/2(r+1)＝γ(r)·0-δ₁(r)θ_2t+1-i/2(r)；第2t+1-i/2位左侧的 低位数据(以第j位为例)更新方式为：δ_j(r+1)＝γ(r)δ_j+1(r)-δ₁(r)θ_j(r)；第3t-i-1 位及其右侧的高位数据(以第m位为例)接收第m-1位中间变量θ(r)的更新值 但不往左传递，即以δ_m(r+1)＝γ(r)δ_m(r)-δ₁(r)θ_m-1(r)的方式进行更新。

综上，为得到本发明所需数据更新过程，若处于Case0情形，仅需将图4 中所述的数据流编号由图3中的编号按照位宽为2t+4重排即可；若处于Case1 情形，仅需将图6中所述的数据流编号由图5中的编号按照位宽为2t+4重排即 可；若处于Case2情形，仅需将图8中所述的数据流编号由图7中的编号按照 位宽为2t+4重排即可。