第七章BCH码与Goppa码

第7章BCH码与Goppa码7.1BCH码的描述及其距离限7.2二进制BCH码及其扩展7.3Reed-Solomon(RS)码7.4BCH码的一般译码方法7.5BCH码的迭代译码算法§7.1BCH码的描述及其距离限

一、BCH码的定义BCH码是纠正多个随机错误的循环码，可以用生成多项式g(x)的根描述。定义7.1.1给定任一有限域GF(q)及其扩域GF(qm)，其中q是素数或素数的幂，m为某一正整数。若码元取自GF(q)上的一循环码，它的生成多项式g(x)的根集合R中含有以下δ-1个连续根：时，则由g(x)生成的循环码称为q进制BCH码。

设mi(x)和ei分别是

(i=0，1，…，δ-2)元素的最小多项式和级，则由式（５.２.３）和式(5.2.4)可知，BCH码的生成多项式和码长分别是：g(x)=LCM(m0(x)，m1(x)，…，mδ-2(x))(7.1.1)n=LCM(e0，e1，…，eδ-2)(7.1.2)

如果生成多项式g(x)的根中，有一个GF(qm)中的本原域元素，则n=qm-1，称这种码长n=qm-1的BCH码为本原BCH码；否则，称为非本原BCH码。GF(qm)中元素的级一定是qm-1的因子，所以非本原BCH码的码长也一定是qm-1的因子。二、BCH码的距离限定理7.1.1(BCH限)BCH码的最小距离dBCH至少为δ。BCH码限的证明有两种方法，一种是从码的校验矩阵H出发，另一种是从码的ＤＦＴ或ＭＳ多项式出发。定理7.1.2(HT限)若BCH码的生成多项式g(x)的根集R中含有s组δ-1个α的连续元素：R｛

｜i=0，1，…，s-1;j=0，1，…，δ-2｝且(n，a)=1，α∈GF(qm)是n级元素，则码的最小距离dHT≥δ+s-1。定理7.1.3(Roos限)若BCH码的g(x)根集R含有s组α的δ-1个连续元素R｛

｜i只取0至s+μ-1中的s个整数；j=0，1，…，δ-2｝，且(a，n)=1，αn=1，α∈GF(qm)，则码的最小距离dR≥δ+s-1。§7.2二进制BCH码及其扩展

一、二进制BCH码在实际中应用得最多的是码元取自GF(2)中的二进制BCH码。由BCH码的定义可知，对任一个正整数m，一定可以构造出以下的二进制码。

取m0=1，δ=2t+1，又设α是GF(2m)的本原域元素，则由BCH码的定义可知：若码以α，α2，…，α2t为根，则二进制BCH码的生成多项式g(x)=LCM(m1(x)m2(x)…m2t(x))(7.2.1)式中，mi(x)是αi(1≤i≤2t)的最小多项式，该BCH码一定能纠正t个错误。

由第四章知，在特征为２的GF(2m)域上，α2i的最小多项式与αi的相同，所以，式(7.2.1)也可写成g(x)=m1(x)m3(x)…m2t-1(x)(7.2.2)因此，二进制BCH码以α，α3，α5，…，

α2t-1为根，码长n=LCM(e1，e3，…，e2t-1)(7.2.3)码的校验矩阵是(7.2.4)

式中，e1，e3，…，e2t-1分别是α，α3，…，

α2t-1元素的级。显然，二进制BCH码的码长或者是2m-1或者是它的一个因子。我们把上述结果归结成如下定理。

定理7.2.1对任何正整数m和t，一定存在一个二进制BCH码，它以α，α3，…，α2t-1为根，其码长n=2m-1或是2m-1的因子，能纠正t个随机错误，校验位数目至多为°g(x)=mt个。

例7.1m=4，α∈GF(24)是本原域元素，它是x4+x+1的根。求码长n=24-1=15的二进制BCH码。(1)t=1，则码以α，α2，α4，α8为根，α的最小多项式m1(x)=x4+x+1，所以码的生成多项式g(x)=m1(x)=x4+x+1校验元数目是°g(x)=4，得到一个［15，11，3］BCH码，这是一个纠正单个错误的循环汉明码。可知，纠正单个错误的本原BCH码就是循环汉明码。

(2)t=2,则码以α，α3为根，α3的最小多项式为m3(x)=x4+x3+x2+x+1，所以g(x)

=m1(x)m3(x)=(x4+x+1)(x4+x3+x2+x+1)

=x8+x7+x6+x4+1

n=LCM(15，5)=15有8个校验元，得到一个［15，7，5］码，能纠正2个随机错误。

(3)t=3，则码以α，α3，α5为根，α5的最小多项式m5(x)=x2+x+1，所以g(x)

=m1(x)m3(x)m5(x)

=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)

=x10+x8+x5+x4+x2+x+1得到一个［15，5，7］BCH码。

(4)t=4。码以α，α3，α5，α7为根，α7的最小多项式m7(x)=x4+x3+1，所以码的生成多项式g(x)

=m1(x)m3(x)m5(x)m7(x)

=x14+x13+x12+x11+x10+x9+x8+x7

+x6+x5+x4+x3+x2+x+1

得到一个［15，1，15］码，这是一个重复码，最小距离d=15，能纠正7个随机错误。该码虽以α，α3，α5，α7为根，但由于共轭根系的原因，该码实际上以αi，1≤i＜14，14个连续元素为根，故设计距离δ=15，实际最小距离也为1５。

例7.2求码长n=21，纠2个随机错误的BCH码。

n=21不是2m-1的类型，故必是2m-1的一个因子。26-1=21×3，所以GF(26)是含有21级元素的最小域。设α∈GF(26)是本原域元素，它是x6+x+1的根。令β=α3，则β的级是21。要求纠正2个错误，则g(x)以β，β3为根。β=α3的最小多项式m1(x)=x6+x4+x2+x+1β3=(α3)3=α9的最小多项式m3(x)=x3+x2+1，所以码的生成多项式

g(x)

=m1(x)m3(x)

=(x6+x4+x2+x+1)(x3+x2+1)

=x9+x8+x7+x5+x4+x+1

n=LCM(21，7)=21得到一个［21，12，5］非本原BCH码。二、BCH码的扩展由第三章可知，任何一个奇重量线性码，增加1个全校验位后最小重量增加１。若我们对奇最小距离的［n，k，d］BCH码增加1个全校验位，则变成一个［n+1，k，d+1］码，称它为扩展BCH码。若对［2m-1，k，d］本原BCH码增加1个全校验位，则变成［2m，k，d+1］码，称为扩展本原BCH码。设［n，k，δ］BCH码以α，α2，…，αδ-1为根。由式(7.1.3)可知，码的校验矩阵由H矩阵每行每列的性质可知，［n+1，k，δ+1］扩展码的校验矩阵为(7.2.5)显然，这相当于码增加了以α0=1为根。但是必须注意，这种扩展方法与增加以１为根，减少１个信息位的增余删信BCH码不一样，它们的最小距离虽然都增加了１，但扩展BCH码的码长增加了１，且每个码字之间不一定存在循环关系，而增余删信BCH码的码长与原码相同，且仍是循环码。如二进制［7，4，3］本原BCH码，它以α，α2，α4为根，g(x)=x3+x+1，校验矩阵H=［α6α5

α4α3α2α1

1］该码增加一个全校验位后变成［8，4，4］扩展本原BCH码，它的校验矩阵因［7，4，3］码是一个汉明码，所以［8，4，4］码也称为扩展汉明码。若［7，4，3］码增加以α0=1为根，则码的生成多项式g(x)=(x+1)(x3+x+1)=x4+x3+x2+1，此码的校验矩阵为这是一个［7，3，4］BCH码，它其实就是一个增余删信汉明码。

码长n≤255的二进制本原BCH码，它的k、d和生成多项式g(x)列于表7-4中。表5-2中列出的QR码(除［7，4］和［31，16］码以外)都是非本原BCH码，此外还有一些非本原BCH码，它们的d和g(x)列于表7-5中。表7-4和表7-5中生成多项式g(x)栏下面的数字，代表g(x)的二进制系数的八进制数表示。例如，八进制数１３的二进制数表示为001011，因而代表g(x)=x3+x+1。b和z分别表示该码的纠突发错误能力和最佳程度。这将在第九章中讲到。表7-5中的(QR)表示该码是平方剩余码。由该图可以明显看出：(1)当码的纠错能力t／n固定时，码长越短，码的R越大；当n≤31时接近汉明限；而n≤1023时，接近V-G限；但是随着n→∞，R→0。(2)当码率R固定时，码长≤31时，码的纠错能力接近汉明限；n≤1023时，接近V-G限；但是随着n→∞，码的纠错能力t／n→0。由此可知，BCH码的性能在码长≤1023时很好，都在V-G限以上；特别在短码时性能更好，接近汉明限；但随着码长的增加，性能变坏。因此BCH码做不到香农编码定理所要求的能力。虽然图7-1是根据表7-4的BCH限得到的，但由定理7.1.8可知，BCH码的实际距离d≤qδ+q-2≈qδ=2δ(二进制情况)因此，实际上当R固定时，BCH码的纠错能力随着n的增加仍趋向于0。即使如此，在中、短码长时BCH码仍不愧是一个很好的码。表7-5某些二进制非本原BCH码图7-1某些二进制BCH码的纠错能力§7.3Reed-Solomon(RS)码

RS码是一类有很强纠错能力的多进制BCH码，也是一类典型的代数几何码。它首先由里德(Reed)和索洛蒙(Solomon)应用MS多项式(p178)于1960年构造出来的。当然，用MS多项式构造的RS码是非系统码，而用BCH码构造方法能产生系统码。

一、RS码的时域编码定义7.3.1GF(q)(q≠2)上，码长N=q-1的本原BCH码称为RS码。可知RS码最主要特点之一是码元取自GF(q)上，而它的生成多项式的根也在GF(q)上，所以RS码是码元的符号域与根域一致的BCH码。

因为

αi的最小多项式mi(x)=x-αi。所以，长为N=q-1，设计距离为δ的RS码，由BCH码的定义可知，它的生成多项式

(7.3.1)

通常情况下取m0=1，此时

g(x)=(x-α)(x-α2)…(x-αδ-1)(7.3.2)

由此生成一个q进制的［q-1，q-δ］RS码，有最小距离为δ。由于线性码的最大可能的最小距离是校验元的个数加１，而RS码恰好做到了这一点。因此，称RS码为极大最小距离可分码，简称MDS码。显然，RS码的设计距离δ与实际距离D是一致的。

例7.3设码的符号取自GF(q)=GF(23)中的元素，α∈GF(23)是本原域元素，它是x3+x+1的根，构造D=5的RS码。GF(23)的元素同表4-1。

要求码的D=5，则码必以α，α2，α3，α4为根，因此由式(7.3.2)可知，码的生成多项式g(x)=(x-α)(x-α2)(x-α3)(x-α4)=x4+α3x3+x2+αx+α3由此生成一个GF(23)上的八进制［7，3，5］本原BCH码，也就是［7，3，5］RS码。它的系统码生成矩阵由式(5.1.7)可知为相应的校验多项式

校验矩阵为：

或

一般情况下，GF(q)上系统码形式［q-1，q-D］RS码的H矩阵(7.3.3)或由式(5.1.9)可得H的标准形式为GF(2m)上的RS码是2m进制码，它的编码电路可用k或n-k级2m进制移位寄存器实现。该例中［7，3，5］RS码的编码器，若用k=3级乘法电路实现，则如图7-2所示。图中的移存器必须是能寄存八进制的元件组成，这可用３级触发器组成的移存器完成。α2，α3，α4常乘器也可用模2加法器构成。现以乘α2为例，说明八进制常乘器的组成。GF(23)中每个元素均可表示成它的自然基底1，α，α2的线性组合：a2α2+a1α+a0，在乘以α2后，则α2(a2α2+a1α+a0)

=a2α4+a1α3+a0α2=a2(α2+α)+a1(α+1)+a0α2

=(a2+a0)α2+(a2+a1)α+a1=a′2α2+a′1α+a′0式中

a′2=a2+a0

a′1=a2+a1

a′0=a1所以，乘α2电路如图7-3所示。图7-2［7,3,5］八进制RS码编码器图7-3GF(23)中乘α2电路图7-4［7，3，5］RS码编码器(1)门1、门2、门3关闭，所有移存器清洗为０。然后将３个八进制信息符号cn-1=c6，cn-2=c5，cn-3=c4，一方面送入八进制寄存器中，另一方面送入信道。注意每一节拍移动１个八进制符号。(2)3个八进制信息元送入后，门１、门２、门３打开，移动一个节拍后，这时移存器右移一位送出c6，同时得到第一个校验元c3，它一方面送至信道，另一方面存入八进制寄存器的第一级中（最左面）。这时在八进制寄存器中存贮的数据自左至右是c3，c4，c5。再移动1个节拍，得到第二个校验元c2，这样依次类推移完７个节拍后，得到了所有４个校验元，并且跟随在信息元后送至信道，完成了一个码字的编码过程。(3)清洗寄存器，重新关闭门１、门２、门３，重复（１）、（２）过程，对第二组信息元进行编码。如果GF(q)上RS码的生成多项式为g(x)

=(x-αa)(x-αa+1)…(x-αa+δ-2)

=g0+g1x+…+gδ-1

xδ-1

=g0+g1x+…+g2tx2t这里，α∈GF(q)，αq-1=1，若αaαa+2t-1=1，则生成多项式g(x)的系数具有如下特点：g0=g2t=1，g1=g2t-1，gt-1=gt+1，…。生成多项式的系数有对称性，g(x)的互反多项式g*(x)=g(x)。对这种RS码的编码器，只要t个乘法器就够了。最近，林舒等应用域元素的对偶基表示，使RS码的编译码更为简单，有关这方面的知识可参阅［11］。§7.4BCH码的一般译码方法

一、BCH码译码的基本概念BCH码的译码与第三章讲的线性码的译码步骤相同分为3步：第一步是由接收到的R(x)计算出伴随式S；第二步由伴随式找出错误图样Ê(x)；第三步由R(x)-Ê(x)得到最可能发送的码字(x)，完成译码。

设GF(q)上的［n，k，d］BCH码以

为根，则它的生成多项式

α∈GF(qm)为n级域元素。发送的码字C(x)=q(x)g(x)，接收的n重为R(x)=C(x)+E(x)。设错误图样

E(x)=en-1

xn-1+en-2

xn-2+…+e1x+e0

若信道产生t个错误，则错误位置错误值译码的目标

求解错误位置和错误值由伴随式定义和式(7.1.3)可知：(7.4.1)式中

j=m0，m0+1，…，m0+2t-1若令，则上式可写成

j=m0，m0+1，…，m0+2t-1(7.4.2)

或(7.4.3)通常情况下取m0=1，则(7.4.4)称式中的sj为x的加权幂和对称函数。

求解上述2t个方程可求出2t个未知数(错误值和错误位置)，但上述方程组是非线性的，因此求解变得非常困难。皮特提出了先求解错误位置，再求错误值的方法：直接求解错误位置无法着手，皮特提出用中间变量，构造一个中间方程:

错误位置多项式p270经推导得到7.4.7式，仍求不出，但s1，s2，…，s2t已知，将σ1，σ2，。。。σt与s1，s2，…，s2t联系起来：由7.4.77.4.8的推导得到7.4.10

求解7.4.10线性方程组可得到错误位置，但一般求解起来也很麻烦，钱闻天提出了快速求解错误位置的方法：钱搜索法

二、钱(Chien)搜索和伴随式计算电路用式(7.4.10)求得σ(x)后，下一步的问题是从工程观点看，如何简单地求出它的根即错误位置。１９６４年钱闻天提出了一个求σ(x)根的实用方法，解决了这个问题。思想：σ(x)的根只能在α1

α2，…，αn中出现，逐个带入σ(x)，看是否是满足方程。

解σ(x)的根，就是确定R(x)中哪几位产生了错误。设R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0，为了要检验第一位rn-1是否错误，相当于译码器要确定αn-1是否是错误位置数，这等于检验α-(n-1)是否是σ(x)的根。若

α-(n-1)=α是σ(x)的根，则σ(α-(n-1))=σ(α)=1+σ1α+σ2α2+…+σtαt=0或σ1α+σ2α2+…+σtαt=-1

所以得到了σ(x)后，为了译rn-1，译码器首先计算σ1α，σ2α2，…，σtαt，然后计算它们的和是否为-1。若是，则αn-1是错误位置数，rn-1码元是错误的；否则rn-1是正确的。换言之

σ1α+σ2α2+…+σtαt=-1，rn-1有错σ1α+σ2α2+…+σtαt≠-1，rn-1正确(7.4.15)

同理，为了译rn-l译码器必须计算σ1xl，σ2α2l，…，σtαtl，并计算它们的和，若

σ1αl+σ2α2l+…+σtαtl=-1rn-l有错σ1αl+σ2α2l+…+σtαtl≠-1rn-l正确(7.4.16)这样依次对每一个rn-l

(l=1，2，…，n)进行检验，就求得了σ(x)的根，这个过程称为钱搜索。在工程上，钱搜索过程可用图７－５所示的电路实现，它的工作过程如下：(1)t个寄存器寄存σ1，σ2，…，σt，当错误个数γ＜t，则σγ+1=σγ+2=…=σt=0。(2)rn-1正要从缓冲存贮器读出之前，t个乘法器由移位脉冲控制行乘法运算，且σ1α，σ2α2，…，σtαt存在σ寄存器中，并送入A中进行σ1α+σ2α2+…+σtαt运算和检验。若等于－１，则A输出一个信号，控制门打开，把错误值Yn-1与缓存器输出的rn-1相减，得到rn-1-Yn-1=cn-1。在二进制情况下，A输出1与rn-1进行模2加，即完成对rn-1的纠错。图7-5钱搜索电路图(3)rn-1译完后，再进行一次相乘，此时σ1α2，σ2(α2)2，…，σt(αt)2存在σ寄存器中，并在A中进行相加运算和检验，对rn-2进行纠错。(4)其余码元同(2)一样纠错。图7-6m1(x)、m3(x)、m5(x)除法电路图7-7计算s1至s6电路§7.5BCH码的迭代译码算法

1966年,伯利坎普(Berlekamp)提出了迭代译码算法，1969年梅西（Massey)推导出迭代译码算法与最短线性移位寄存器序列（m序列）之间的关系，用简化的方式解读了伯利坎普(Berlekamp)提出的迭代译码算法，后来称为BM迭代译码算法。§7.5BCH码的迭代译码算法一、迭代译码算法的基本原理由式(7.4.7)可知：

(7.5.1)(7.5.2)式中，s0=1。作乘积S(x)δ(x)，并用

ω(x)=1+ω1x+ω2x2+…(7.5.3)

表示该乘积

S(x)σ(x)=ω(x)

将式(7.5.1)和式(7.5.2)代入上式并展开S(x)σ(x)=1+(s1+σ1)x+(s2+σ1s1+σ2)x2+…+(st+σ1st-1+…+σt)xt+(st+1+σ1st+…+σts1)xt+1+…=1+ω1x+ω2x2+…+ωtxt+ωt+1xt+1+…(7.5.4)由式(7.4.9)可知，若m0=1，则有：

st+1+σ1st+…+σts1=0st+2+σ1st+1+…+σts2=0…(7.5.5)s2t+σ1s2t-1+…+σtst=0所以，式(7.5.4)中大于xt的系数均为0。由于σ(x)的次数为t，而式(7.5.4)中的最高次数为t，所以°ω(x)≤t，或°ω(x)≤°σ(x)。由式(7.5.4)看出，式(7.5.2)中的S(x)及σ(x)都只要选到xt次项即可，因而°S(x)σ(x)≤2t。所以式(7.5.4)成为

S(x)σ(x)≡ω(x)

(modx2t+1)(7.5.6)称它是求σ(x)的

关键方程

。(1)由初值

σ(-1)(x)=1，ω(-1)(x)=0，D(1)=0，d-1=1

σ(0)(x)=1，ω(0)(x)=1，D(0)=0，d0=s1开始迭代。图7-8求σ(x)的迭代算法流程图(2)按式(7.5.12)计算dj，若dj=0，则有：

σ(j+1)(x)=σ(j)(x)

ω(j+1)(x)=ω(j)(x)

D*(j+1)=D*(j)并计算dj+1，再进行下一次迭代。如果dj≠0，则找出j之前的某一行i，它在所有j行之前各行中的i-D*(i)最大，且di≠0，于是按照式(7.5.13)和式(7.5.14)分别计算σ(j+1)(x)和ω(j+1)(x)，这就是第j+1步的解。(3)计算dj+1，重复(2)进行下一次迭代。这样2t次迭代后得到的σ(2t)(x)和ω(2t)(x)即为所求的σ(x)和ω(x)。ω(x)是在求σ(x)过程中得到的辅助多项式，在求解错误值时将用到，故称ω(x)为

错误值多项式

。上述迭代过程如图7-8所示。可列成表７-６，进行迭代时逐步把表格填满即可。

表7-6求σ(x)

的迭代过程表

表7-7求［15，9，7］

RS码σ(x)

的迭代过程表表7-8求［31，11，11］

二进制BCH码σ(x)

的迭代过程表二、二进制

BCH码迭代译码算法的简化由例7.7看出，迭代译码过程中，若j为奇数时dj=0，因而迭代次数可以减少一半，下面我们将证明这一点。若码为二进制BCH码，则E(x)中的错误值Yi均为1，因而式(7.4.3)中的sj成为(7.5.15)由加权幂和对称函数变为一般的

初等幂和对称函数

。另一方面，由二进制BCH码的校验矩阵特点可知s2j=s2j。由关键方程式(7.5.6)出发，把它展开并考虑到式(7.5.5)，可得S(x)σ(x)≡1+(s1+σ1)x+(s2+σ1s1+σ2)x2+(s3+s2σ1+s1σ2+σ3)x3+…+(st+σ1st-1+…+σt)xt

(modx2t+1)(7.5.16)由式(7.4.6)和式(7.5.15)可知，有如下的

牛顿恒等式

：

s1-σ1=0

s2-s1σ1+2σ2=0

s3-s2σ1+s1σ2-3σ3=0

…在任意域中成立。所以在GF(2)中上式成为：

s1+σ1=0

s2+σ1s1=0

s3+s2σ1+s1σ2+σ3=0

…(7.5.17)将式(7.5.17)代入式(7.5.16)得

S(x)σ(x)=1+σ2x2+σ4x4+…+σ2tx2t≡ω(x)

(mod

x2t+1)(7.5.18)这说明关键方程的奇数次项的系数均为0，仅只有偶次项系数。基于上式我们不难相信，在二进制BCH码的迭代译码过程中有如下特点：(1)ω(i)(x)等于σ(i)(x)的偶部多项式σ(i)e(x)；(2)i为奇数时的di=0。为了证明上述两个特点，在特征为2的域中引入逆生成函数R(x)，它定义为

S(x)R(x)=1(7.5.19)

式中，R(x)=1+R1x+R2x2+…，是一个有常数项的幂级数。我们分别用So和Ro记为S和R的奇次幂部分，用Se和Re记为它们的偶次幂部分。

引理7.5.3

在特征为2的域中，Re=0的充要条件是Se=S2。

证明

将S、R写成：

S=1+So+Se

R=1+Ro+Re

代入式(7.5.19)展开得(1+So+Se)(1+Ro+Re)=1+Se+Re+SoRo+SeRe+(1+Se)Ro+(1+Re)So=1比较奇偶部分可得：偶部：1+Se+Re+SoRo+SeRe=1奇部：(1+Se)Ro+(1+Re)So=0消去Ro得

Re=(Se+S2)／(1+S2)

所以，若Se=S2，则Re=0；反之若Re=0，则Se=S2。

定理7.5.2

对二进制BCH码的迭代译码算法有：

ω(i)(x)=σ(i)e(x)i=0，1，2，…，2t和

d2k+1=0k=0，1，2，…，t-1表7-9二进制BCH码求σ(x)

表7-10二进制［31，11，11］BCH码求σ(x)迭代过程三、迭代译码算法与序列的最短线性反馈移位寄存器综合及线性复杂度之间的关系这里将简单讨论一下求σ(x)的迭代算法，与序列的最短线性反馈移位寄存器(LFSR)综合及序列的线性复杂度之间的关系。由上节讨论可知，要解式(7.5.5)st+1+σ1st+…+σts1=0

st+2+σ1st+1+…+σts2=0…

s2t+σ1s2t-1+…+σtst=0线性方程组可用式(7.5.6)

S(x)σ(x)≡ω(x)(modx2t+1)利用迭代方法求解σ(x)。在上述方程组中，如果已知σ1，σ2，…σt和s1，s2，…，st，则可通过计算求得st+1，依次类推就可求得st+2，st+3，…，s2t。这个递推过程可用图7-9的电路实现，与图5-18比较可知它们完全相同。式(7.5.5)显然是一组线性递推关系式。因此只要在电路中放入初始值s1，s2，…，st，通过移位就可在输出端得到一组序列s1，s2，…，s2t。现在的问题是已知s1，s2，…，s2t，问电路应如何联接，并且使用的级数最少，才能使输出的序列为s1，s2，…，s2t。这个问题就是LFSR的综合问题，它与BCH码迭代译码求σ(x)的关系，首先由梅西于１９６９年发现。从BCH码译码的角度考虑，上述问题就是已知伴随式s1，s2，…，s2t，如何确定电路的联接多项式σ(x)=1+