纠错编码的基本原理
线性分组码
循环码
卷积码
第 8 章 差错控制编码
返回主目录
差错控制编码也称为纠错编码。在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。为了在已知信噪比情况下达到一定的比特误码率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域、频域均衡，使比特误码率尽可能降低。但实际上，在许多通信系统中的比特误码率并不能满足实际的需求。
此时必须采用信道编码(即差错控制编码)才能将比特误码率进一步降低，以满足系统指标要求。随着差错控制编码理论的完善和数字电路技术的飞速发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与各种存储器中也得到日益广泛的应用。研究各种编码和译码方法是差错控制编码所要解决的问题。
8．1纠错编码的基本原理
常用的差错控制方式
从差错控制的角度看，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。由此传输信道中常见的错误有以下三种：(1)随机错误：错误的出现是随机的，一般不是成片地出现错误。这种情况通常是由信道的加性随机噪声引起。因此，一般将具有此特性的信道称为随机信道。恒参高斯白噪声信道是典型的随机信道。(2)突发错误：错误的的出现是一连串出现的。
通常在一个突发错误持续时间内，开头和末尾的码元总是错的，中间的某些码元可能错也可能对，但错误的码元相对较多。这样的信道我们称之为突发信道。具有脉冲干扰的信道是典型的突发信道。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。(3)混合错误：既有突发错误又有随机差错的情况。这种信道称之为混合信道。
对于不同类型的信道，应采用不同的差错控制技术。常用的差错控制方法有以下几种：
1)检错重发(ARQ)
解码器对接收码组逐一按编码规则检测，若有错，则通过反向信道要求发送端重新发送，直到接收端检查无误为止。虽然ARQ系统需要反馈信道，效率较低，但能达到很好的性能。
2)前向纠错(FEC)
FEC方式是在信息码序列中，以特定结构加入足够的冗余位——称为监督元（或校验元），接收端解码器可以按照双方约定的监督规则，自动识别出少量差错，并能予以纠正。编译码设备相对复杂，FEC最适于高速数传而需实时传输的情况。
3) 反馈校验法(IF)
接收端将收到的信码原样转发回发送端，并与原发送信码相比较，发现错误进行重发，其优点是方法和设备简单，无需纠(检)错编译系统。但需要双向信道，而且传输效率较低，因为每一信码都相当于至少传了两次。只适于低速非实时数据通信。
纠错编码的基本原理：
纠错编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加冗余码的个数可增加纠检错能力。
在阐述纠错编码的原理之前，我们先了解有关纠错编码的几个基本概念 (1)监督码元
监督码元又称监督位或附加数据比特，这是为了检纠错码而在信道编码时加入的判断数据位 。通常以r表示，即为：
r=n－k 或 n=k+r
经过分组编码后的码又称为(n，k)码，即表示总码长为n位，其中信息码长(码元数)为k位， 监督码长(码元数)为r=n－k。通常称其为长为n的码字(或码组、码矢)。
(2)许用码组与禁用码组
信道编码后的总码长为n，总的码组数应为2n，即为2k+r。其中被用作传送的信息码组有2k个，通常称为许用码组；其余的码组共有(2n -2k)个不传送，称为禁用码组。
通常把信息码元数目k 与编码后的总码元数目(码组长度)n之比称为信道编码的编码效率，表示为：
R=k/n=k/(k+r)
(3)码重与码距
在分组编码后，每个码组中码元为“1”的数目称为码的重量，简称码重。两个码组对应位置上取值不同(1或0)的位数，称为码组的距离，简称码距，又称汉明距离，通常用d表示。 例如：000与101之间码距d=2；000与111之间码距d=3。对于(n，k)码，许用码组为2k个， 各码组之间距离最小值称为最小码距，通常用d0表示。最小码距d0的大小与信道编码的检纠错能力密切相关。
纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。最小码距是信道编码的一个重要的参数。在一般情况下，分组码的最小汉明距离d0与检错和纠错能力之间满足下列关系：
(1)为了检测e个误码，要求最小码距应满足：
d0≥e+1
(2)为了纠正t个误码，要求最小码距应满足：
d0≥2t+1
用图-2(b)说明这个关系。
(3)为了纠正t个误码，同时能检测e个误码(e＞t)，要求最小码距应满足：
d0≥t+e+1
信道编码的任务就是要根据不同的干扰特性，设计出编码效率高、纠错能力强的编码。在实际设计过程中，需要根据具体指标要求，纠错编码的纠错和检错能力要尽量强；编码效率尽量高；码长尽量短；编码规律尽量简单。
常用的简单编码
1. 奇偶监督码
奇偶监督码可分为奇监督码和偶监督码，是最基本的检错码。它是由n-1位信息元和1位监督元组成。一般情况下，对任意长的信息码字，奇偶监督码的编码规则是：将各位二元信息码及附加的监督位进行模2加，如果是偶校验，则保证模2和结果为0；如果是奇校验，则保证模2和结果为1。设信息码字长为n，码字为(an-1 an-2 …a1 a0)，a0为监督位。
偶校验时应满足：
an-1⊕an-2⊕…⊕a1⊕a0 = 0
类似的，奇校验时有公式：
an-1⊕an-2⊕…⊕a1⊕a0 = 1
从上面这几个式子可看出：如果发生单个(或奇数个)错误，就会破坏这个关系式，因此通过该式能检测码字中是否发生了单个或奇数个错误，但不能检测出偶数个错误，也不能纠正错误。
2. 行列监督码
行列监督码又称二维奇偶监督码或方阵码。它将l组k位信码先排为l行×k列的阵列，然后按既定的奇（偶）校验规则，在每行及每列中分别加入奇偶校验位。亦即各行和各列对l的数目都实行奇偶监督。可以逐行传输，也可以逐列传输。译码时分别检查各行、各列的监督关系，判断是否有错。它不能检测出构成矩形的四个错码。
3. 恒比码
恒比码又称等重码，这种码的码字中1和0的位数保持恒定比例。由于每个码字的长度是相同的，而1、0的位数恒比，则码字必等重。这种码在检测时，只要计算接收到的码组中“1”的数目是否对，就知道有无错误，是一种检错码。
目前国际上通用的ARQ电报通信系统中，采用“7中取3”码，这种码共有=35个许用码字，93个禁用码字。35个许用码字用来代表26个英文字母和其它符号。实践证明，应用这种码，使国际电报通信的误码率保持在以10-6下。
恒比码的主要优点是简单，并适用于电传机及其它产生固定字符的键盘设备。其缺点是不适用于随机二进制序列的编码。
8．2线性分组码
分组码是一组固定长度的码组，可表示为(n,k)。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，线性分组码具有如下性质：
1、封闭性。即任意两个码组的和(对于二进制码这个和的含义是模2和)还是许用的码组。
2、码组间的最小码距等于非零码的最小码重。
在节中介绍的奇偶监督码，就是一种最简单的线性分组码，它只有一位监督位，通常表示为(n,n-1)，在接收端解码时，实际上就是在计算：
S=an-1⊕an-2⊕…⊕a1⊕a0
其中，an-1、an-2、…、a1 表示接收到的信息位，a0表示接收到的监督位， S＝0或1分别对应于无错或有错。上式被称为监督关系式，S是校正子。校正子S的取值只有“0”和“1”，因此，它只能表示有错和无错这两种信息，而不能纠错。
如果监督位增加一位，则能增加一个的监督关系式，那么计算出的两个校正子S1和S2共有4种组合：00，01，10，11，可以表示4种不同的信息。用00表示无错以外，其余3种状态就可用于指示3种不同的错码位置。
一般来讲，线性分组码(n，k)中，如果满足2r－1≥n，(r＝n－k)，则有可能用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置。
下面我们通过(7，4)分组码的例子来说明如何具体构造这种线性码。设分组码(n，k)中，k = 4，为能纠正一位误码，要求r≥3。现取r＝3，则n＝k＋r＝7。我们用a0ala2a3a4a5a6表示这7个码元，用S1、S2、S3表示由三个监督方程式计算得到的校正子，并假设三位S1、S2、S3校正子码组与误码位置的对应关系如表-2所示。
由表可知，当误码位置在a2、a4、a5、a6时，校正子S1＝1；否则S1＝0。因此有
在编码时a6、a5、a4、a3为信息码元，是随机的，a2、a1、a0为监督码元，根据信息位的取值按监督关系决定。则监督码元可由以下监督方程唯一确定。
由上面方程可得到表-2所示的16个许用码组。在接收端收到每个码组后，计算出S1、S2、S3则可判断是否出错，然后由表-1确定错误位置并予以纠正。例如收到码组为0000011，可算出S1S2S3=011,由表-1可知在a3上有一误码。通过观察可以看出，上述(7，4)码的最小码距为3，它能纠正一个误码或检测两个误码。如果超出纠错能力则反而会因“乱纠”出现新的误码。
上述方法构造的码能纠正单个误码的线性分组码又称为汉明码。它是一种高效码，编码效率为R=k/n=(2r－r－1)/( 2r－1)=1-r/(2r－1)= 1-r/n。由该式可看出，当n很大时，编码效率接近1。
现在我们来讨论线性分组码的一般原理。前面已经提过，线性码中信息位和监督位是由一些线性代数方程联系着的。这样就可以将式(-4)所述(7，4)码的三个监督方程式写成如下形式：
上式可以记作： H·AT=0T或A·HT=0
式中，A称为信道编码得到的码字，H称为监督矩阵，若监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。H的行数就是监督关系式的数目，等于监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由信息位a6 a5 a4之和决定的。
另外，H为r×n阶矩阵，其中P为r×k阶矩阵，Ir为r×r阶单位方阵，具有形式的H矩阵称为典型监督矩阵。典型形式的监督矩阵各行是线性无关的，否则将得不到r个线性无关的监督关系式，从而也得不到r个独立的监督位。
对于式(-5)也可以用矩阵形式来表示：
式中，Q = PT，信息位给定后，用信息位的行矩阵乘矩阵Q就产生监督位。
如果在Q矩阵的左边加上一个k×k阶的单位方阵，就形成了一个新矩阵G：
这里G称为生成矩阵，利用它可以产生整个码组
若式(-12)具有[Ik Q]形式，则称为典型生成矩阵，利用典型生成矩阵产生的分组码中信息码元保持不变，监督码元附加在其后，这种码称为系统码。
H矩阵右方为(n-k)×(n-k)单位矩阵In-k，G矩阵左方总是k×k单位矩阵Ik，加之两阵中含有的P与Q关系，因此在由监督方程组系数构成H矩阵后，可以很方便地得到G矩阵——只要按G=[Ik┊Q]=[ Ik┊PT]直接写出即可。
矩阵G的各行要求线性无关。若某一码字为许用码组，则它必然满足式(-8)。利用这一关系，在接收端将收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件则认为接收正确；反之则认为传输过程中发生了错误，进而设法确定错误的数目和位置。
设发送码组A在传输过程中可能由于干扰而出现误码，假设这时接收到的码组为B，即
B=[bn-1 bn-2… b1 b0]
则收、发码组之差为：
式中
8．3循环码
循环码的原理
循环码是线性分组码中最重要的一个子类码，它的基本特点是编码电路及伴随式解码电路简单易行；循环码代数结构具有很多有用的特性，便于找到有效解码方法。因此在实际差错控制系统中所使用的线性分组码，几乎都是循环码。
循环码的构成突出特点是只要是该码中的一个许用码组，通过循环i位（i=1，2，…，n-1）其结果则可包括全部2k-1个非全0码字，如表-1所示的（7，3）分组码，从信码位001构成的码字（0011101）开始逐一向左（或者向右）移一位，可得其余6个码字：（0111010）、（1110100）、（1101001）、（1010011）、（0100111）、（1001110）。具有这种特性的线性分组码称为循环码。
循环码具有以下一些性质：
1、封闭性。任何许用码组的线性和还是许用码组。由此性质可以知：线性码都包含全零码。且最小码重就是最小码距。
2、循环性。任何许用的码组循环移位后的码组还是许用码组。
表-1一种(7，3)循环码的全部码字
循环码可以用多项式来表示。为了用代数理论的方法研究循环码的特性，我们经常将循环码表示成码多项式的形式，即把一长为n的码组表示成：
例如(1100101)码的多项式表示为。
这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中a6、a5、a2、a0为1，其他均为0。我们不必关心x的取值。
为求循环码的生成矩阵，我们先了解一下码多项式的按模运算。若一任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，也就是：
则可以写为： F(x)≡R(x) (模N(x))
这时，码多项式系数仍按模2运算，即只取值0和1，
如：x7+1=( x4+ x3+ x2+1)( x3+ x2+1)=N(x)·Q(x)
则x7+1≡0 (模N(x)) 即x7+1能被N(x)= x4+ x2+x+1整除
在循环码中，若A(x)是一个长为n的许用码组，则xi·A(x)在按模xn+1运算下，也是一个许用码组，也就是说，如果：xi·A(x) ≡A′(x)(模xn+1)，可以证明A′(x)亦是一个许用码组，并且，A′(x)正是A(x)代表的码组向左循环移位i次的结果。
通过上述分析可以得到了一个重要的结论：一个长度为n的循环码，它必为按模(xn+1)运算的一个余式。
如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n，k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。那么，另一个重要的结论是，(n，k)循环码的生成多项式g(x)一定是xn+1的因式，有且仅有一个，它是n-k次码多项式，而且常数项为1。
循环码的生成矩阵G可以写成
显然，上式不一定不符合形式，但可将此矩阵作线性变换以化成典型矩阵。
因为通过G(x)可求得任一循环码多项式，即
将上式写成
A(x)=h(x)·g(x)
由上式可知，任一循环码多项式都是g(x)的倍式。
又因为：一个长度为n的循环码，它必为按模(xn+1)运算的一个余式。所以
将式(-8)代入上式并简化得
由上式可看出，生成多项式g(x)一定是xn+1的因式。
为寻找生成多项式，必须对xn+1进行因式分解。因式分解可以通过计算机分解的方式分解，也可以通过查表(通常一些参考书已给出了这种因式分解的表格)。
循环码的编、解码方法
分析完循环码的原理，再看循环码的编、解码方法。
编码方法
当给定(n,k)循环码的信息码位M(x)和选定生成多项式g(x)后，根据任一循环码多项式都是g(x)的倍式这一定理，就可以对给定的信息位进行编码。
循环码编码步骤可归纳如下。
(1)用xn-k乘m(x)。即将r个“0”附加在信息(数据)码的低端，使其长度变为k+r 位。
(2)求r(x)。即将xn-k·m(x)除以g(x)，得到商为低于k次的多项式Q(x)，余式r(x)。这是由于循环码多项式A(x)都可以被整除，也就是：
因此，用xn-k·m(x)除以g(x)，就得到商Q(x)和余式r(x)，即
这样就得到了r(x)。
(3)编码输出系统循环码多项式A(x)为：
译码方法
纠错码的译码是该编码能否得到实际应用的关键所在。译码器往往比编码较难实现，对于纠错能力强的纠错码更复杂。根据不同的纠错或检错目的，循环码译码器可分为用于纠错目的和用于检错目的的循环码译码器。
达到检错目的的译码十分简单，由前面所述知识可知，在循环码中，所有的码多项式都能被g(x)整除，因此，通常将接收到的循环码组进行除法运算，即用生成多项式去除，如果接收的码组被g(x)整除除尽，则说明正确传输；如果未除尽，则说明传输中发生了错误。
根据上述原理构成的解码器如图-2所示。从图中可看出，解码器的核心部件是一个除法电路和缓冲移存器，这里的除法电路与发送端的编码器中的除法电路相同。
需要指出的是，出错的接收码组也有可能被g(x)整除，这时解码器就不能检出错码了。这种错误被称为不可检错误，不可检错误中的错码数必将超过这种编码的检错能力。
用于纠错目的的循环码的译码算法比较复杂，因此，对纠错码的研究大都集中在译码算法上。我们知道，校正子与错误图样之间存在某种对应关系。如同其它线性分组码，原则上纠错可按下述步骤进行：
① 用生成多项式g(x)去除接收码组R(x)=A(x)+E(x)，得出余式r(x)；
② 按余式r(x)用查表法或通过某种运算得到错误图样E(x)，就可以确定错码位置。例：通过计算校正子和利用校验子与错码位置的关系可确定错码位置。
③ 从R(x)中减去E(x)，便得到已纠正错误的原发送码组A(x)。
上述第(1)步运算和检错译码相似，即求解R(x)整除g(x)的余式，第(3)步也很简单。因此，纠错码译码器的复杂性主要取决于译码过程的第(2)步，可能需要复杂的设备，并且在计算余式和决定E(x)的时候需要把整个接收码组R(x)暂时存储起来。对于纠正突发错误或单个错误的编码第（2）要求的计算还算简单，但对于纠正多个随机错误的编码却很复杂。
在实际中传输码字是连续不断地输入的。为使译码移位纠错不丢失输入码，则译码器需要两套除法电路(含与门)配合一个缓冲寄存器。这两套除法器由开关控制交替接受码字。另外，在解码器中需要删除监督码元，只输出信息码元即可。这种译码称为梅吉特译码。梅吉特译码器特别适合于纠正2个以下的随机错误。目前，解码器也多采用微处理或数字信号处理器实现。
通常，一种编码可以有不同的几种纠错译码法。对于循环码来说，译码方法除了梅吉特译码以外，还有捕错译码、大数逻辑译码等方法。捕错译码是梅吉特译码的一种变形，也可以用较简单的组合逻辑电路实现，它特别适合于纠正突发错误、单个随机错误和两个错误的码字。大数逻辑译码也称为门限译码，这种译码方法也很简单，但它只能用于有一定结构的为数不多的大数逻辑可译码，虽然在一般情形下，大数逻辑可译码的纠错能力和编码效率比有相同参数的其它循环码(如BCH码)稍差，但它的译码算法和硬件比较简单，因此在实际中有较广泛的应用。
8．4卷积码
卷积码的基本概念
卷积码又称连环码，1955年由P.伊莱亚斯提出，虽经多年努力，在编码方法上还没有找到象分组码那样有效的数学工具和系统的理论。不过，卷积码在译码方面，不论在理论上还是在实用上都超过了分组码，因而在差错控制和数据压缩系统中得到广泛应用。
为了达到一定的纠错能力和编码效率，分组码的码组长度一般都比较大。编译码时必须把整个信息码组存储起来，由此产生的译码延时随n的增加而增加。卷积码和分组码有明显的区别。它也是将k个信息比特编成n个比特，但k和n通常很小，特别适合以串行形式进行传输，时延小。还有一点与分组码不同，即卷积码编码后的n个码元不仅与当前段的k个信息有关，还与前面的m段信息有关。
编码过程中相互关联的码元为n(m+1)个。(m+1)称之为编码约束度，(m+1)段时间内的码元数目n( m+1)通常被称为这种码的编码约束长度。典型的卷积码一般选较小的n和k(k<n)，但存储器m则取较大的值(m <10)，以获得既简单又高性能的信道编码。
卷积码通常用(n，k，m)表示卷积码(注意：有些文献中也用(n，k，N)来表示卷积码)。图-1就是一个卷积码(2，1，2)的编码器，它由移位寄存器、模二加法器即开关电路组成。该卷积码的n = 2，k = 1，m = 2，因此，它的约束长度nN = n×(m+1) = 2×3 = 6。
m1
输出
S1
S2
S3
C1
C2
数据
输入
图-1 (2，1，2)卷积码编码器
m2
在图-1中，寄存器m1与m2的起始状态均为零。C1、C2与S1 、S2 、S3之间的关系如下：
假设输入的数据为D = [11010]，为了使全部数据通过移位寄存器，还必须在信息位后面加3个零。表-1列出了对数据D进行卷积编码时的状态。
表-1 数据D进行卷积编码时的状态
通常，卷积码更适用于前向纠错法，设备简单，纠错能力随着m的增加而增大，在编码器复杂程度相同的情况下，卷段积码的性能优于分组码。这种连环码在它的信息码元中也有插入的监督码元但并不实行分组监督，每一个监督码元都要对前后的信息单元起监督作用，整个编解码过程也是一环扣一环，连锁地进行下去，由此得名连环码。目前大都采用计算机来搜索好码。
卷积码的描述
卷积码的编码器是由一个有k个输入端、n个输出端、m节移位寄存器所构成的有限状态的有记忆系统，通常称它为时序网络。描述这类时序网络的方法很多,大致可分为两大类型：解析表示法与图形表示法。
解析法又可分为离散卷积法、生成矩阵法、码多项式法等；图形表示法可分为状态图法、树图法、格图法等。描述卷积码编、译码的过程，可以用不同的描述方法，如矩阵法、状态图法等。采用何种方法描述卷积码的编码器，与其译码方法有很大关系。例如，在代数译码时，用矩阵法对译码原理的叙述和理解较方便。而借助树图和篱状图能更为清晰地分析和了解概率译码的过程和码的性能。
解析表示较为抽象难懂，而用图形表示法来描述卷积码简单明了。这里，我们仅介绍图形表示法
1、 树图
树图描述的是在任何数据序列输入时，码字所有可能的输出。对应于(2，1，2)卷积码的编码电路，其树图如图-2所示。
-2 (2，1，2)码的树图
以S1 S2 S3=000为起点。若第一位数据S1=0，输出C1C2=00，从起点通过上支路到达状态a，即S1 S2=00；若S1 =1，输出C1C2=11，从起点通过下之路到达状态b，即S3 S2=01；依次类推，可得整个树图。输入不同的信息序列，编码器就走不同的路径，输出不同的码序列。例如当输入数据为[11010]时，其路径如图中虚线所示，并得到输出码序列为[11010100…]，与表-1的结果一致。
2 、状态图
图-3 (2，1，2)码的状态图
除了用树图表示编码器的工作过程外，还可以用状态图来描述，即用有向图表示输出、输入和状态的关系。图-3所示的是(2，1，2)卷积编码器的状态图。图中有4个节点a、b、c、d，分别表示S3 S2的4种可能的状态：00、01、10和11。每个节点有两条线离开该节点，实线表示输入数据为0，虚线表示输入数据为1，线旁的数字即为输出码字。
图-3 (2，1，2)码的状态图
3 、格图
格图也称网络图或篱笆图，将树图中同一级节点上所有相同状态的各分支合并, 或由状态图在时间上展开，便构成格图。图-4即为(2，1，2)码的格图，图中画出了所有可能数据输入时，状态转移的全部可能轨迹，实线表示数据为0，虚线表示数据为1，线旁数字为输出码字，节点表示状态。
图-4 (2，1，2)码的格状图
卷积码的译码
卷积码的译码可分为代数译码和概率译码两大类。代数译码是根据卷积码的本身编码结构进行译码，译码时不考虑信道的统计特性。在代数译码中最主要的方法是大数逻辑译码。代数译码所要求的设备简单，运算量小，但其译码性能(误码)要比概率译码方法差许多。概率译码在计算时要考虑信道的统计特性。概率译码比较常用的有两种，一种叫序列译码，另一种叫维特比译码法。目前在数字通信的前向纠错中广泛使用的是概率译码方法。
1、序列译码
序列译码是根据接收序列和编码规则，在整个码树中搜索(既可以前进，也可以后退)出一条与接收序列距离(或其他量度)最小的一种算法。当m很大时，可以采用序列译码法。 其过程如下：
译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较， 沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后得到一条路径。
若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门限值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。
许多深空和海事通信系统都采用序列译码。
2、维特比译码
维特比译码是一种最大似然译码算法，是根据接收序列在码的格图上找出一条与接收序列距离(或其他量度)为最小的一种算法。由于接收序列通常很长，所以维特比译码时作了简化，即它把接收码字分段处理。每接收一段码字，计算、比较一次，保留码距最小的路径，直至译完整个序列。
现举例说明维特比译码过程。若发送端的信息数据D=[11010000]，由编码器输出的码字C=[1101010010110000]，接收码序列为R=[0101011010010010]，有4位码元错误。
参照图-5，先选前3个码作为标准，对到达第3级的4个节点的8条路径进行比较，逐步算出每条路径与接收码字之间的累计码距。累计码距分别用括号内的数字标出，对照后保留一条到达该节点的码距较小的路径作为幸存路径(当有两条以上取最小值时，可任取其中之一)。再将当前节点移到第4级，计算、比较、保留幸存路径，直至最后得到到达终点的一条幸存路径，即为译码路径，图中实线即为译码路径。
图-5 维特比译码格状图
