信息理论与编码第六章信道编码

信息理论与编码第六章信道编码第一页，共一百五十一页，2022年，8月28日§6.1信道编码的概念§6.2线形分组码§6.3循环码§6.4卷积码第二页，共一百五十一页，2022年，8月28日§6.1.1信道编码的作用和分类§：编码信道§：检错和纠错原理§：检错和纠错方式和能力第三页，共一百五十一页，2022年，8月28日信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号 －－线路编码如何避免少量差错信号对信息内容的影响 －－纠错编码广义信道编码=特定信道上传输信息而进行的传输信号或信号格式的设计与实现

第四页，共一百五十一页，2022年，8月28日

描述编码

用于对特定数据信号的描述约束编码用于对特定信号特性的约束扩频编码用于扩展信号频谱为近似白噪声谱并满足某些相关特性纠错编码用于检测与纠正信号传输过程中因噪声干扰导致的差错1234第五页，共一百五十一页，2022年，8月28日：信道编码的作用和分类§6.1.3编码信道：检错和纠错原理：检错和纠错方式和能力第六页，共一百五十一页，2022年，8月28日消息信道编码

编码信道

信道译码

码字接收向量消息编码信道模型第七页，共一百五十一页，2022年，8月28日n-1

当码字C和接受向量R均由二元序列表时，称编码信道为二进制信道

C=(c0,c1,…cn-1)如果对于任意的n都有：

P(r/c)=∏p(ri/ci)则称此二进制信道为无记忆二进制信道。

p(0/1)=p(1/0)=p0则称此信道为无记忆二进制对称信道BSCi=0第八页，共一百五十一页，2022年，8月28日BSC转移概率BSC编码信道BSC输入输出关系等效为第九页，共一百五十一页，2022年，8月28日差错图案：随机序列

或，

第位上的一个随机错误：

长的突发错误：第至第

位之间有很多错误

对于一个BSC信道总有转移概率1/2，比特传输中发生差错数目越少，概率越大，即

从而总认为发生差错的图案是差错数目较少的图案

第十页，共一百五十一页，2022年，8月28日二元软判决信道

用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出

信道干扰z为零均值正态分布的随机变量，噪声干扰功率为均方差，z的概率分布为。对于BPSK调制，二元输入符号为二元符号取值为+1或-1第十一页，共一百五十一页，2022年，8月28日第十二页，共一百五十一页，2022年，8月28日：信道编码的作用和分类：编码信道§6.1.3检错和纠错原理：检错和纠错方式和能力第十三页，共一百五十一页，2022年，8月28日检纠错是根据信道输出序列自身判断是否可能是发送的，或纠正导致不等于的错误。冗余编码：码字的长度一定大于消息的长度

纠错编码编码码率：每个码字的序列符号（或码元）平均传送的消息比特数

第十四页，共一百五十一页，2022年，8月28日偶（或奇）校验方法：实现检纠错目的的一个基本方法。

一个偶校验位是对消息使得如下校验方程成立的二进制符号，即

一个偶校验码码字

一个码率为的偶校验码，所有可能的的全体校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错

第十五页，共一百五十一页，2022年，8月28日

m0+m1+m2+…+mk－1+p=0（mod2）

称c=(m0,m1,m2…mk-1,p)为一个偶校验字

确定校验位P的编码方程为：

P=m0+m1+…+mk-1第十六页，共一百五十一页，2022年，8月28日编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部按某种校验方程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字和其码率分别为

第十七页，共一百五十一页，2022年，8月28日第十八页，共一百五十一页，2022年，8月28日重复消息位：实现检纠错目的第二个基本方法

一个重复码是一个码率为的码，仅有两个码字和，传送1比特（）消息。

重复码可以检测出任意小于个差错的错误图案，纠正任意小于个差错的错误图案。纠1位差错的3重复码

第十九页，共一百五十一页，2022年，8月28日等重码或定比码：实现检纠错的第三个方法。

设计码字重量恒为常数，即

例如一种用于表示0至9数字的5中取3等重码如表（6.1.1）所示，其码率为

5中取3等重码

1234567890010111100110110110100011110101111000111010011011015中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错第二十页，共一百五十一页，2022年，8月28日§：信道编码的作用和分类§：编码信道§：检错和纠错原理§6.1.4检错和纠错方式和能力第二十一页，共一百五十一页，2022年，8月28日纠错码的应用方式：前向纠错方式（FEC），自动请求重发（ARQ）方式，混合纠错（HEC）方式以及信息反馈（IRQ方式）

FEC与ARQ纠错应用方式

第二十二页，共一百五十一页，2022年，8月28日

常用汉明距离来描述检纠差错的数目，对于两 n长向量u，v汉明距离为：

最小汉明距离（最小码距d）：任意两码字之间的汉明距离的最小值

第二十三页，共一百五十一页，2022年，8月28日定理

对一个最小距离为纠错码，如下三个结论仅有其中任意一个结论成立，

（1）

可以检测出任意小于等于个差错；（2）

可以纠正任意小于等于个差错；（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足第二十四页，共一百五十一页，2022年，8月28日最小码距与检纠错能力

第二十五页，共一百五十一页，2022年，8月28日差错概率：通信作为一个统计过程时，纠检错能力的统计特性。FEC方式纠错码的码字差错概率：发送码字的先验概率

：码字数，对于充分随机的消息源

第二十六页，共一百五十一页，2022年，8月28日对BSC信道

最大化等价于最小化，最小差错概率译码等价为使接收向量与输出码字距离最小的最小距离译码，即

第二十七页，共一百五十一页，2022年，8月28日信息比特信噪比：传输一个比特信息所需的最小信噪比

比特差错概率（又称误码率）与信噪比的关系如下图所示，采用纠错码后，达到同样比特差错概率实际需要的信噪比减小量称为编码增益。

编码增益

第二十八页，共一百五十一页，2022年，8月28日§6.2线性码

§6.2.1线性分组码的描述§6.2.2线性分组码的译码§6.2.3码例与码的重构第二十九页，共一百五十一页，2022年，8月28日§6.2.1线性分组码的描述§6.2.2线性分组码的译码§6.2.3码例与码的重构第三十页，共一百五十一页，2022年，8月28日一个（n,k）线形分组码C是称为码字c的n维向量的集合

C={c|c=mG}其中m为任意的k维向量并称为消息向量。G是k行n行列秩为k（n≥k）的矩阵并称为生成矩阵，第三十一页，共一百五十一页，2022年，8月28日对于二元编码，和是二元向量，是一个二元矩阵，，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算。

表6.2.1模二加/乘法表

第三十二页，共一百五十一页，2022年，8月28日例6.2.13重复码是一个（3，1）线性分组码

第三十三页，共一百五十一页，2022年，8月28日例（4，3）偶校验码是一个（4，3）线性分组码第三十四页，共一百五十一页，2022年，8月28日当生成矩阵给定时线性分组码有如下性质：（1）零向量一定是一个码字，称为零码字；（2）任意两码字的和仍是一个码字；（3）任意码字是的行向量的线性组合；（4）线性分组码的最小距离等于最小非零码字重量。

第三十五页，共一百五十一页，2022年，8月28日由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为0来判断传输是否可能有错，那么必有一个矩阵满足

显然的每一列或的每一行确定了一个可能的分组码的校验方程，的线性不相关行数最少要等于该码的所有可能的校验方程数，称这样的矩阵为线性分组码的一致校验矩阵。

第三十六页，共一百五十一页，2022年，8月28日由的每一行都是一个码字有

由现行空间的理论，当H的行秩为r时，H作为一个(n,k)线性分组码的生成矩阵所生成的码是与G对应空间正交的r维线性子空间，称为(n,k)线性分组码的对偶码或对偶空间，并且有如下的维数关系成立第三十七页，共一百五十一页，2022年，8月28日T定理：任何满足下式的n维向量a均是一（n,k）线形分组码的码字

aH=Ө其中满足公式的H矩阵形式不唯一，但一个码的对偶码是惟一的。T第三十八页，共一百五十一页，2022年，8月28日系统码：生成矩阵具有如下形式

在码字集合不变的情况下，任何一个线性分组码都可以一对一的去对应一个系统码。对于系统码相应的一致校验矩阵注意与仍然满足。

以线性分组码的一致校验矩阵为生成产生的线性分组码称为原线性分组码的对偶码。第三十九页，共一百五十一页，2022年，8月28日例6.2.3一个（5，3）线性分组码的

其中到的行初等变换过程为（表示第i行），

第四十页，共一百五十一页，2022年，8月28日（5，3）线性分组码码例

消息mG生成码字Gs生成码字对偶码码字00000101001110010111011100000110100101110001101100110011101001110000000111010110110010001101101101011101

00000111010111010011第四十一页，共一百五十一页，2022年，8月28日由一致校验矩阵可以比较容易确定线性分组码的最小码距

定理

线性分组码的最小码距为，当且仅当其一致校验矩阵H中任意列线性无关，某列线性相关。

该定理实际给出了计算线性分组码最小码距的一种方法。

第四十二页，共一百五十一页，2022年，8月28日§6.2.1线性分组码的描述§6.2.2线性分组码的译码§6.2.3码例与码的重构第四十三页，共一百五十一页，2022年，8月28日译码的概念检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即。第四十四页，共一百五十一页，2022年，8月28日纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。第四十五页，共一百五十一页，2022年，8月28日纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。纠错译码的译码失败状态：译码器不能输出一个确切的码字，通常此时的输出y与检错译码输出相同。

第四十六页，共一百五十一页，2022年，8月28日定义：(n,k）线形分组码的伴随式是一个r(r=n-k)维向量s

，则传输中一定有错误发生，则传输中要么无差错发生，要么差错图案恰好为一个码字。

第四十七页，共一百五十一页，2022年，8月28日定理

可纠t错的q元线性分组码满足

第四十八页，共一百五十一页，2022年，8月28日伴随式纠错译码的通用译码方法

（1）按最可能出现的个差错图案，计算相应的伴随式，并构造伴随式—差错图案表；（2）对接收向量计算伴随式；（3）查表得；（4）纠错计算。第四十九页，共一百五十一页，2022年，8月28日§6.2.1线性分组码的描述§6.2.2线性分组码的译码§6.2.3码例与码的重构第五十页，共一百五十一页，2022年，8月28日常见的线形分组码有重复码，汉明码，里德-穆勒码，戈雷码（1）汉明码：二元Hamming码是一种的完备码，满足

其中列向量为全部可能的非零元组。

第五十一页，共一百五十一页，2022年，8月28日Hamming码的对偶码是一个线性分组码，称为最大长度码，由于所有非零码字的重量均为，又称为等距码或单形（simplex）码。第五十二页，共一百五十一页，2022年，8月28日例6.2.4一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为

等价的编码方程为

第五十三页，共一百五十一页，2022年，8月28日伴随式计算方程

第五十四页，共一百五十一页，2022年，8月28日（2）Hadamard码

Hadamard码是由Hadamard矩阵派生出的一种纠错码。

阶实Hadamard矩阵由元素为+1，-1的矩阵递归定义为

例如

第五十五页，共一百五十一页，2022年，8月28日第五十六页，共一百五十一页，2022年，8月28日Hadamard矩阵为正交矩阵，即中的任意不同两行（列）的点积为0，即

超正交矩阵：Hadamard矩阵中的第1列（全+1列）去掉后由于任两行的点积为-1。

将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。

第五十七页，共一百五十一页，2022年，8月28日（A）正交码：以的全部行向量的0/1映射向量为码字。（B）双正交码：以和-的全部行向量的0/1映射向量为码字。

第五十八页，共一百五十一页，2022年，8月28日（C）超正交码：以的全部行向量的0/1映射向量为码字。

可以证明正交码、双正交码和超正交码均是线性分组码。

第五十九页，共一百五十一页，2022年，8月28日例6.2.5（7，3）超正交码的超正交矩阵和生成矩阵G分别为

第六十页，共一百五十一页，2022年，8月28日(3)里德-穆勒（Reed-Muller）阶码是一种 线性分组码，满足第六十一页，共一百五十一页，2022年，8月28日其中各个子矩阵的定义为

1）为矩阵，由全1向量构成。2）为矩阵，由所有可能的m元组组成矩阵的列向量。3）为的所有两不同行向量的叉积构成其全部行向量的矩阵。两向量的叉积为4）为的所有三不同行向量的叉积构成其全部行向量的矩阵。5）为的所有个不同行向量的叉积构成其全部行向量的矩阵。

r第六十二页，共一百五十一页，2022年，8月28日例6.2.6

的阶RM码的各个子矩阵有

第六十三页，共一百五十一页，2022年，8月28日

码的对偶码仍是一个Reed-Muller码，为码。

第六十四页，共一百五十一页，2022年，8月28日（4）戈雷码二元戈雷码是一种就纠3个错的完备线形分组码，满足：

n=23k=12{第六十五页，共一百五十一页，2022年，8月28日由于

因此某种二元（23,12）码一定可以纠正任意小于等于3个差错，所以

第六十六页，共一百五十一页，2022年，8月28日§6.3循环码循环码的多项式描述循环码的生成矩阵多项式运算电路系统循环码循环码的编码电路循环码的伴随多项式与检测码与RS码第六十七页，共一百五十一页，2022年，8月28日§6.3.1循环码的多项式描述循环码的生成矩阵系统循环码多项式运算电路循环码的编码电路循环码的伴随多项式与检测码与RS码第六十八页，共一百五十一页，2022年，8月28日

更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。

6.3.1循环码的多项式描述第六十九页，共一百五十一页，2022年，8月28日第七十页，共一百五十一页，2022年，8月28日第七十一页，共一百五十一页，2022年，8月28日定义如果一个线性分组码的任意一个码字c(n元组)都是另外一个码字c’的循环移位,称此线性分组码为一个循环码.

将循环码的码字用多项式c(x)，称为码多项式（简称码式）表示后，循环码集合表示C(x),

第七十二页，共一百五十一页，2022年，8月28日例6.3.2如下确定的CA是线性循环码，CB是非循环的线性分组码，CC是非线性的循环码。

，

，

第七十三页，共一百五十一页，2022年，8月28日定理：

（n,k）循环码C(x)中存在唯一的一个非零的，首一的和最低次为r（r<n）的码

多项式g(x)满足：

g(x)=xr+gr-1xr-1+….+g1X+g0

g0≠0

r=n-k并且c(x)是码式当且仅当c(x)是g(x)的倍式第七十四页，共一百五十一页，2022年，8月28日定义由上述定理确定的码式g(x)称为循环码(n,k)的生成多项式.

因此(n,k)循环码的构造是如何构造生成多项式g(x)。

循环码由生成多项式的倍式组成第七十五页，共一百五十一页，2022年，8月28日定理：

g(x)是（n,k）循环码的生成多项式，当且仅当g(x)是xn-1的r=n-k次因式。第七十六页，共一百五十一页，2022年，8月28日第七十七页，共一百五十一页，2022年，8月28日第七十八页，共一百五十一页，2022年，8月28日第七十九页，共一百五十一页，2022年，8月28日循环码的多项式描述§6.3.2循环码的生成矩阵系统循环码多项式运算电路循环码的编码电路循环码的伴随多项式与检测码与RS码第八十页，共一百五十一页，2022年，8月28日循环码的生成矩阵和校验矩阵(n,k)循环码的生成矩阵为第八十一页，共一百五十一页，2022年，8月28日(n,k)循环码的校验矩阵为第八十二页，共一百五十一页，2022年，8月28日循环码的多项式描述循环码的生成矩阵§6.3.3系统循环码多项式运算电路循环码的编码电路循环码的伴随多项式与检测码与RS码第八十三页，共一百五十一页，2022年，8月28日6.3.3系统循环码循环码的系统码码式为第八十四页，共一百五十一页，2022年，8月28日第八十五页，共一百五十一页，2022年，8月28日循环码的多项式描述循环码的生成矩阵系统循环码§6.3.4多项式运算电路循环码的编码电路循环码的伴随多项式与检测码与RS码第八十六页，共一百五十一页，2022年，8月28日6.3.4多项式运算电路因为多项式表示时间序列所以多项式的计算表现为对时间序列的操作.第八十七页，共一百五十一页，2022年，8月28日多项式a(x)与b(x相加电路第八十八页，共一百五十一页，2022年，8月28日

a(x)与g(x)的一般乘法电路第八十九页，共一百五十一页，2022年，8月28日第九十页，共一百五十一页，2022年，8月28日循环码的多项式描述循环码的生成矩阵系统循环码多项式运算电路§6.3.5循环码的编码电路循环码的伴随多项式与检测码与RS码第九十一页，共一百五十一页，2022年，8月28日非循环码编码器

根据多项式乘法电路和循环码码式是生多项式倍式原理，多项式乘法电路(图6.3.4)是循环码的非系统码电路，又称为循环码乘法编码电路图6.3.4第九十二页，共一百五十一页，2022年，8月28日2.系统编码电路

循环码系统编码电路由乘法电路，求余式电路以及加法开关电路组成,如图所示,电路工作过程如表所示.图6.3.14第九十三页，共一百五十一页，2022年，8月28日表6.3.2循环码系统码编码电路工作过程第九十四页，共一百五十一页，2022年，8月28日§6.3.1循环码的多项式描述§6.3.2循环码的生成矩阵§6.3.3系统循环码§6.3.4多项式运算电路§6.3.5循环码的编码电路§6.3.6循环码的伴随多项式与检测§6.3.7BCH码与RS码第九十五页，共一百五十一页，2022年，8月28日循环码的译码分成检错译码与纠错译码两类.1.检错译码原理第九十六页，共一百五十一页，2022年，8月28日2.纠错译码循环码的纠错译码要达到码的最小距离依赖于具体的循环码的结构.第九十七页，共一百五十一页，2022年，8月28日循环码的多项式描述循环码的生成矩阵系统循环码多项式运算电路循环码的编码电路循环码的伴随多项式与检测§6.3.7BCH码与RS码第九十八页，共一百五十一页，2022年，8月28日BCH码是一类能够先确定纠错能力t，然后设计码长和生成多项式的码。对于任意的整数m和可达到纠错数t，都可以构造出一个设计距离为d0的二元本原BCH码满足：

n=2m-1,r=n-k≤mt,dmin≥d0=2t+1第九十九页，共一百五十一页，2022年，8月28日RS码是多元BCH码的一个子类，码字向量的每个分量可以表示`为m比特，其基本参数为：码长：n=2m-1(符号)=m(2m-1)（比特）

校验位长：r=n-k=2t(符号)=m·2t其中t为RS码可以纠正的差错符号数.第一百页，共一百五十一页，2022年，8月28日§6.4卷积码卷积码的多项式描述

卷积码的状态转移图与格描述维特比（Viterbi）译码算法卷积码的矩阵描述第一百零一页，共一百五十一页，2022年，8月28日§6.4.1卷积码的矩阵描述卷积码的多项式描述卷积码的状态转移图与格描述维特比（Viterbi）译码算法第一百零二页，共一百五十一页，2022年，8月28日卷积码编码：当前输出

不仅与当前输入消息

相关，还与此前输入的

个消息

相关，

二元线性卷积码：是仅由模二加运算组成的布尔函数

第一百零三页，共一百五十一页，2022年，8月28日的长度恒为

比特，

的长度恒为

n比特，均称为一段

第一百零四页，共一百五十一页，2022年，8月28日任意一输入段

与输出段

的关系都是一个特殊的

线性分组码的编码

第一百零五页，共一百五十一页，2022年，8月28日卷积编码的离散卷积表达式卷积码的记忆长度（段）：

约束长度（段）：

或

第一百零六页，共一百五十一页，2022年，8月28日结尾处理：额外输入

段无效的0数据

比特，保证编码器回到全0的初态

有限

段长消息的编码速率为：

渐近编码速率：

第一百零七页，共一百五十一页，2022年，8月28日卷积码的生成矩阵

二元线性

卷积码

定义第一百零八页，共一百五十一页，2022年，8月28日基本生成矩阵

：生成矩阵

的前

行，

列组成的子矩阵

第

个生成元

：

的第

行，描述

了所有各段输入中的第

位输入比特

对所有输出比特的影响

第一百零九页，共一百五十一页，2022年，8月28日将的元素

的列下标

表示为

则输入移位寄存器中的第

段的第

位输入比特

参与第

位输出比特的编码

<-->

不参与第

位输出比特的编码<-->

第一百一十页，共一百五十一页，2022年，8月28日卷积码的子生成元或生成序列：

元组

第一百一十一页，共一百五十一页，2022年，8月28日线性卷积码的矩阵（或向量）描述：

第一百一十二页，共一百五十一页，2022年，8月28日生成矩阵

，基本生成矩阵

，生成序列（生成元）

系统卷积码：卷积码每段输出的

位中有

位（如当前

位）恒等于每段输入的

位

第一百一十三页，共一百五十一页，2022年，8月28日其中

均为

矩阵。

第一百一十四页，共一百五十一页，2022年，8月28日由于对每个独立的输入段（每段

比特，共3段）分别有

基本生成矩阵

为

，生成矩阵为

，生成元为

，生成

第一百一十五页，共一百五十一页，2022年，8月28日序列为

第一百一十六页，共一百五十一页，2022年，8月28日卷积码的矩阵描述§6.4.2卷积码的多项式描述卷积码的状态转移图与格描述维特比（Viterbi）译码算法第一百一十七页，共一百五十一页，2022年，8月28日6.4.2卷积码的多项式描述消息段序列的多项式表示第一百一十八页，共一百五十一页，2022年，8月28日多项式描述更直接的描述了（二元）

卷积码作为一个

（比特）入，

（比特）

出的编码关系

编码输出段序列的多项式表示第一百一十九页，共一百五十一页，2022年，8月28日线性

卷积码的多项式表达式为

线性

卷积码的多项式矩阵

：为

的多项式矩阵

又称

为卷积码的延迟算子生成矩阵。第一百二十页，共一百五十一页，2022年，8月28日定理

线性

卷积码的多项式生成矩阵

对

满足

的

幂次项系数等于

生成序列

的第

个分量，

1第一百二十一页，共一百五十一页，2022年，8月28日即

的最大次数等于卷积码的记

忆长度

，即

2第一百二十二页，共一百五十一页，2022年，8月28日例

前述例（2,1,2）卷积码重画如图

第一百二十三页，共一百五十一页，2022年，8月28日卷积码的矩阵描述卷积码的多项式描述§6.4.3卷积码的状态转移图与格描述维特比（Viterbi）译码算法第一百二十四页，共一百五十一页，2022年，8月28日卷积码与分组码的明显区别是卷积码编码器要存储m段信息，这些信息数据既要因新的输入而改变，又要影响当前的编码输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，简称状态。第一百二十五页，共一百五十一页，2022年，8月28日状态：既要因新的输入而改变，又要

影响当前的编码输出的数据。

卷积编码器有效的存贮单元数为

第一百二十六页，共一百五十一页，2022年，8月28日其中

为每个输入移位寄存器的

有效级数（寄存单元数）。因此二元卷积

码的状态变量记为状态向量

或简记为

第一百二十七页，共一百五十一页，2022年，8月28日状态数：二元

卷积码共有

个不同的状态，记为

状态转移：当状态为

（或

）时，

输入段

（或

）产生编码输出段

（或

），并使该

状态改变（称为

转移）到新的状态

（或

）。

第一百二十八页，共一百五十一页，2022年，8月28日转移分支：到

的转移过程，记为

（

，

）或（

，

），并标

记为

或

分支为有向边描述卷积码的所有不同状态

转移的有向图

状态转移图：以状态为结点，转移

第一百二十九页，共一百五十一页，2022年，8月28日状态转移方程：

与

的关系

输出方程：

与

的关系

第一百三十页，共一百五十一页，2022年，8月28日尽管卷积码有

个状态，但是由于每段

的输入为

比特只有

种状态的变

化，每个状态只转移到

个状态的某个

子集（个状态）中去，每个状态

也只能由某

个状态的状态子集转移

而来。

第一百三十一页，共一百五十一页，2022年，8月28日例第一百三十二页，共一百五十一页，2022年，8月28日状态转移图（闭合形）

第一百三十三页，共一百五十一页，2022年，8月28日状态转移图（开放形）

状态转移方程和输出方程分别为

第一百三十四页，共一百五十一页，2022年，8月28日卷积编码器工作过程：

*卷积编码器工作初态为（全0状态）

*消息段序列产生输出段序列

*消息段序列产生状态序列

第一百三十五页，共一百五十一页，2022年，8月28日栅格图或篱笆图：开放形的状态转移图按时间顺序级联

编码路径：状态序列在栅格图中形成一条有向路径

一个卷积码码字：有向路径始于全0状态，又终于时的一条有向路径

对于的卷积码，常用实线表示 时输入产生的转移分支，用虚线表示 时输入产生的转移分支

第一百三十六页，共一百五十一页，2022年，8月28日例

前述例（2，1，2）码的栅格图及几条路径例

第一百三十七页，共一百五十一页，2022年，8月28日路径A消息A（100）输出A（111011）路径B消息B（10110）输出B（1110000101）路径