信道编码PPT课件.ppt

第第1 1章：概述章：概述第第2 2章：信源熵章：信源熵第第3 3章：信道容量章：信道容量第第4 4章：信息率失真函数章：信息率失真函数第第5 5章：信源编码章：信源编码第第6 6章：信道编码章：信道编码第第7 7章：密码体制的安全性测度章：密码体制的安全性测度§6.1 信道编码的概念信道编码的概念§ 6.2 线形分组码线形分组码§ 6.3 循环码循环码§ 6.4 卷积码卷积码§§6.1.1 6.1.1 信道编码的作用和分类信道编码的作用和分类§ 6.1.2：编码信道：编码信道§ 6.1.3：检错和纠错原理：检错和纠错原理§ 6.1.4：检错和纠错方式和能力：检错和纠错方式和能力¨信道编码是以信息在信道上的正确传输为信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：目标的编码，可分为两个层次上的问题：¨如何正确接收载有信息的信号如何正确接收载有信息的信号¨－－线路编码－－线路编码¨如何避免少量差错信号对信息内容的影响如何避免少量差错信号对信息内容的影响¨－－纠错编码－－纠错编码广义信道编码广义信道编码=特定信道上传输信息而进行的特定信道上传输信息而进行的传输信号或信号格式的设计与实现传输信号或信号格式的设计与实现  描述编码描述编码 用于对特定数据信号的描述用于对特定数据信号的描述 约束编码约束编码 用于对特定信号特性的约束用于对特定信号特性的约束 扩频编码扩频编码 用于扩展信号频谱为近似白噪声谱并满用于扩展信号频谱为近似白噪声谱并满足某些相关特性足某些相关特性 纠错编码纠错编码 用于检测与纠正信号传输过程中因噪声用于检测与纠正信号传输过程中因噪声干扰导致的差错干扰导致的差错1234§§ 6.1.1 6.1.1：信道编码的作用和分类：信道编码的作用和分类§6.1.2 编码信道编码信道§§6.1.36.1.3：检错和纠错原理：检错和纠错原理§§6.1.46.1.4：检错和纠错方式和能力：检错和纠错方式和能力消息消息信道编码信道编码 编码信道编码信道 信道译码信道译码 码字码字接收向量接收向量消息消息编码信道模型编码信道模型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BSC转移概率转移概率BSC编码信道编码信道BSC输入输出关系等效为输入输出关系等效为差错图案：随机序列差错图案：随机序列 或或 ，， 第位上的一个随机错误：第位上的一个随机错误：  长的突发错误：第长的突发错误：第 至第至第 位之间位之间有很多错误有很多错误 对于一个对于一个BSCBSC信道总有转移概率信道总有转移概率 1/21/2，， 比比特传输中发生差错数目越少，概率越大，即特传输中发生差错数目越少，概率越大，即 从而总认为发生差错的图案是差错数目较少的图案从而总认为发生差错的图案是差错数目较少的图案 二元软判决信道二元软判决信道  用多个比特（理想情况下为实数）表示用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出每一个无记忆编码信道的二元符号输出  信道干扰信道干扰z z为零均值正态分布的随机为零均值正态分布的随机变量，噪声干扰功率为均方差变量，噪声干扰功率为均方差 ，，z z的概的概率分布为率分布为 。

对于对于BPSKBPSK调制，二元输入调制，二元输入符号符号 为二元符号取值为为二元符号取值为+1+1或或-1 -1 §§ 6.1.1 6.1.1：信道编码的作用和分类：信道编码的作用和分类§§ 6.1.2 6.1.2：编码信道：编码信道§§6.1.3 6.1.3 检错和纠错原理检错和纠错原理§§ 6.1.4 6.1.4：检错和纠错方式和能力：检错和纠错方式和能力检纠错是根据信道输出序列检纠错是根据信道输出序列 自身判断自身判断是是否否可可能能是是发发送送 的的，，或或纠纠正正导导致致 不不等等于于 的错误冗余编码：码字冗余编码：码字 的长度的长度 一定大于消息一定大于消息 的长度的长度 纠错编码纠错编码编码码率编码码率 ：每个码字的序列符号（或码元）：每个码字的序列符号（或码元）平均传送的消息比特数平均传送的消息比特数 偶（或奇）校验方法：实现检纠错偶（或奇）校验方法：实现检纠错目的的一个基本方法目的的一个基本方法 一个偶校验位一个偶校验位 是对消息是对消息 使得如下校验方使得如下校验方程成立的二进制符号，即程成立的二进制符号，即 一个偶校验码码字一个偶校验码码字 一一个个码码率率为为 的的 偶偶校校验验码码，，所所有可能的有可能的 的全体的全体校验方程为校验方程为1 1表明一定有奇数个差错，校验方程为表明一定有奇数个差错，校验方程为0 0表明可能有偶数个差错表明可能有偶数个差错  m0+m1+m2+…+mk－1+p=0 （mod 2） 称称c=(m0,m1,m2…mk-1,p)为一个偶为一个偶校验字校验字 确定校验位确定校验位P的编码方程为：的编码方程为： P=m0+m1+…+mk-1编码可以产生多个奇偶校验位，即一个校编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部按某种校验位可以由消息位的部分或全部按某种校验方程产生，例如对阵列消息进行垂直与验方程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字水平校验以及总校验的码字 和其码率和其码率分别为分别为 重复消息位：实现检纠错目的第二个基本方法重复消息位：实现检纠错目的第二个基本方法 一一个个 重重复复码码是是一一个个码码率率为为 的的码码，，仅仅有有两两个个码码字字 和和 ，传送，传送1 1比特（比特（ ）消息。

消息重重复复码码可可以以检检测测出出任任意意小小于于 个个差差错错的的错错误误图案，纠正任意小于图案，纠正任意小于 个差错的错误图案个差错的错误图案纠纠1 1位差错位差错的的3 3重复码重复码 等重码或定比码：实现检纠错的第三个方法等重码或定比码：实现检纠错的第三个方法 设计码字重量设计码字重量 恒为常数，即恒为常数，即 例如一种用于表示例如一种用于表示0 0至至9 9数字的数字的5 5中取中取3 3等重码如表等重码如表（（6.1.16.1.1）所示，其码率）所示，其码率 为为 5 5中取中取3 3等重码等重码 1 12 23 34 45 56 67 78 89 90 00101101011 1100111001 1011010110 1101011010 0011100111 1010110101 1110011100 0111001110 1001110011 01101011015 5中中取取3 3等等重重码码可可以以检检测测出出全全部部奇奇数数位位差差错错，，对对某某些些码字的传输则可以检测出部分偶数位差错码字的传输则可以检测出部分偶数位差错§ 6.1.1：信道编码的作用和分类：信道编码的作用和分类§ 6.1.2：编码信道：编码信道§ 6.1.3：检错和纠错原理：检错和纠错原理§6.1.4 检错和纠错方式和能力检错和纠错方式和能力纠错码的应用方式：前向纠错方式（纠错码的应用方式：前向纠错方式（FECFEC），），自动自动请求重发（请求重发（ARQARQ））方式，混合纠错（方式，混合纠错（HECHEC））方式以及方式以及信息反馈（信息反馈（IRQIRQ方式）方式） FEC与ARQ纠错应用方式  常用汉明距离来描述检纠差错的数目，对于两n 长向量u，v汉明距离为： 最小汉明距离最小汉明距离 （最小码距（最小码距d d）：）：任意两码任意两码字之间的汉明距离的最小值字之间的汉明距离的最小值 定理定理 对一个最小距离为对一个最小距离为 纠错码，如下三个纠错码，如下三个结论仅有其中任意一个结论成立，结论仅有其中任意一个结论成立， （（1 1）） 可以检测出任意小于等于可以检测出任意小于等于 个差错；个差错；（（2 2）） 可以纠正任意小于等于可以纠正任意小于等于 个差错；个差错；（（3 3））可可以以检检测测出出任任意意小小于于等等于于l同同时时纠纠正正小小于于等于等于t个差错，其中个差错，其中l和和t满足满足最小码距与检纠错能力最小码距与检纠错能力 差差错错概概率率：：通通信信作作为为一一个个统统计计过过程程时时，，纠纠检检错错能力的统计特性。

能力的统计特性FECFEC方式纠错码的码字差错概率方式纠错码的码字差错概率：发送码字：发送码字 的先验概率的先验概率 ：：码字数，对于充分随机的消息源码字数，对于充分随机的消息源 对对BSCBSC信道信道 最大化最大化 等价于等价于 最小化，最小差错概最小化，最小差错概率译码等价为使接收向量与输出码字距离最小率译码等价为使接收向量与输出码字距离最小的最小距离译码，即的最小距离译码，即 信息比特信噪比信息比特信噪比 ：传输一个比特信息：传输一个比特信息所需的最小信噪比所需的最小信噪比  比特差错概率比特差错概率 （又称误码率）与信噪比（又称误码率）与信噪比 的关系如下图所示，采用纠错码后，达到同样比特的关系如下图所示，采用纠错码后，达到同样比特差错概率实际需要的信噪比减小量称为编码增益差错概率实际需要的信噪比减小量称为编码增益 编码增益编码增益 §6.2 线性码线性码 §6.2.1 线性分组码的描述线性分组码的描述§6.2.2 线性分组码的译码线性分组码的译码§6.2.3 码例与码的重构码例与码的重构§§6.2.1 6.2.1 线性分组码的描述线性分组码的描述§§6.2.2 6.2.2 线性分组码的译码线性分组码的译码§§6.2.3 6.2.3 码例与码的重构码例与码的重构一个（一个（n,k））线形分组码线形分组码C是称为码字是称为码字c的的n维维向量的集合向量的集合 C={c| c=mG}其中其中m为任意的为任意的k维向量并称为维向量并称为消息向量。

消息向量G是是k行行n行列秩为行列秩为k（（n≥k））的矩阵并称为的矩阵并称为生成矩阵，生成矩阵，对于对于二元二元编码，编码， 和和 是二元向量，是二元向量， 是一个是一个二元矩阵，二元矩阵， ，向量与矩阵，矩阵与矩阵，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算之间的基本运算是模二加和模二乘运算 表表6.2.1 6.2.1 模二加模二加/ /乘法表乘法表 例例6.2.1 6.2.1 3 3重复码是一个（重复码是一个（3 3，，1 1）线性分组码）线性分组码 例例6.2.26.2.2（（4 4，，3 3））偶偶校校验验码码是是一一个个（（4 4，，3 3））线线性性分分组码组码当生成矩阵当生成矩阵 给定时线性分组码有如下性质：给定时线性分组码有如下性质：（（1 1））零零向向量量 一一定定是是一一个个码码字字，，称称为零码字；为零码字；（（2 2）任意两码字的和仍是一个码字；）任意两码字的和仍是一个码字；（（3 3））任任意意码码字字 是是 的的行行向向量量 的的线性组合；线性组合；（（4 4）线性分组码的最小距离等于最小非零码字）线性分组码的最小距离等于最小非零码字重量。

重量 由偶校验码的检错概念，可以通过计算接收向量由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为的所有校验方程值是否为0 0来判断传输是否可能来判断传输是否可能有错，那么必有一个矩阵有错，那么必有一个矩阵 满足满足 显然显然 的每一列或的每一列或 的每一行确定了一个可的每一行确定了一个可能的分组码的校验方程，能的分组码的校验方程， 的线性不相关行数的线性不相关行数最少要等于该码的所有可能的校验方程数，称最少要等于该码的所有可能的校验方程数，称这样的这样的 矩阵矩阵 为为 线性分组码的一致校线性分组码的一致校验矩阵 由由 的每一行都是一个码字有的每一行都是一个码字有 由由现行空间的理论，当现行空间的理论，当H的行秩为的行秩为r时，时，H作为一个作为一个(n,k)线性分组码的生成矩阵所生成的码是与线性分组码的生成矩阵所生成的码是与G对应空间正交对应空间正交的的r维线性子空间，称为维线性子空间，称为(n,k)线性分组码的对偶码或对线性分组码的对偶码或对偶空间，并且有如下的维数关系成立偶空间，并且有如下的维数关系成立T定理定理： 任何满足下式的任何满足下式的n维向量维向量a均是一均是一（（n,k））线形分组码的码字线形分组码的码字 aH=Ө其中其中满足公式的足公式的H矩矩阵形式不唯一，但一形式不唯一，但一个个码的的对偶偶码是惟一的。

是惟一的T系统码：系统码：生成矩阵生成矩阵 具有如下形式具有如下形式 在在码码字字集集合合不不变变的的情情况况下下，，任任何何一一个个线线性性分分组组码码都可以一对一的去对应一个系统码都可以一对一的去对应一个系统码对于系统码相应的一致校验矩阵对于系统码相应的一致校验矩阵注意注意 与与 仍然满足仍然满足  以以线线性性分分组组码码的的一一致致校校验验矩矩阵阵为为生生成成产产生生的的线线性性分组码称为原线性分组码的对偶码分组码称为原线性分组码的对偶码例例6.2.36.2.3一个（一个（5 5，，3 3）线性分组码的）线性分组码的 其中其中 到到 的行初等变换过程为（的行初等变换过程为（ 表示第表示第i i行），行）， （5，3）线性分组码码例 消息消息mG生成码字生成码字Gs生成码字生成码字对偶码码字对偶码码字00000101001110010111011100000110100101110001101100110011101001110000000111010110110010001101101101011101  00000111010111010011由一致校验矩阵可以比较容易确定线性分组码由一致校验矩阵可以比较容易确定线性分组码的最小码距的最小码距 定理定理 线性分组码的最小码距为线性分组码的最小码距为 ，当，当且仅当其一致校验矩阵且仅当其一致校验矩阵H中任意中任意 列线性无列线性无关，某关，某 列线性相关。

列线性相关 该定理实际给出了计算线性分组码最小码距的一该定理实际给出了计算线性分组码最小码距的一种方法种方法 §§6.2.1 6.2.1 线性分组码的描述线性分组码的描述§6.2.2 线性分组码的译码线性分组码的译码§§6.2.3 6.2.3 码例与码的重构码例与码的重构译码的概念检检错错译译码码：：译译码码器器输输出出为为当当前前接接收收向向量量r和和r是是否否有有差错的标志差错的标志s s，，即即 纠错译码的译码成功状态纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字 ，即 纠错译码的译码成功状态：译码器能够在达到纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的译码码字差错概率最小条件下输出一个确切的码字码字 ，即，即 纠错译码的译码失败状态：译码器不能输出一纠错译码的译码失败状态：译码器不能输出一个确切的码字，通常此时的输出个确切的码字，通常此时的输出y y与检错译码输与检错译码输出相同 定义：定义： (n,k(n,k））线形分组码的伴随式是一个线形分组码的伴随式是一个r(r=n-k)r(r=n-k)维维向量向量s s ，则传输中一定有错误发生 ，则传输中要么无差错发生，要么差错图案恰好为一个码字。

定理定理 可纠可纠t错的错的q元线性分组码满足元线性分组码满足 伴随式纠错译码的通用译码方法伴随式纠错译码的通用译码方法 （1）按最可能出现的 个差错图案 ，计算相应 的伴随式 ，并构造伴随式—差错图案表 ；（2）对接收向量 计算伴随式 ；（3）查 表得 ；（4）纠错计算 §§6.2.1 6.2.1 线性分组码的描述线性分组码的描述§§6.2.2 6.2.2 线性分组码的译码线性分组码的译码§6.2.3 码例与码的重构码例与码的重构常见的线形分组码有重复码，汉明常见的线形分组码有重复码，汉明码，里德码，里德-穆勒码，戈雷码穆勒码，戈雷码（（1）汉明码：）汉明码：二元二元 HammingHamming码是一种码是一种 的完备码，的完备码，满足满足 其中列向量其中列向量 为全部可能的非零为全部可能的非零 元组 Hamming码的对偶码是一个 线性分组码，称为最大长度码，由于所有非零码字的重量均为 ，又称为等距码或单形（simplex）码。

例例6.2.4 6.2.4 一个二元（一个二元（7 7，，4 4））HammingHamming码的系统码形码的系统码形式的矩阵和校验矩阵分别为式的矩阵和校验矩阵分别为 等价的编码方程为等价的编码方程为 伴随式计算方程伴随式计算方程 （（2 2））HadamardHadamard码码 HadamardHadamard码是由码是由HadamardHadamard矩阵派生出的一种纠错码矩阵派生出的一种纠错码 阶实阶实HadamardHadamard矩阵由元素为矩阵由元素为+1+1，，-1-1的矩的矩阵递归定义为阵递归定义为 例如例如  Hadamard矩阵为正交矩阵，即 中的任意不同两行（列）的点积为0，即 超正交矩阵 ：Hadamard矩阵 中的第1列（全+1列）去掉后由于任两行的点积为-1 将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。

（A）正交码：以 的全部行向量的0/1映射向量为码字 （B）双正交码：以 和- 的全部行向量的0/1映射向量为码字 （C）超正交码：以 的全部行向量的0/1映射向量为码字 可以证明正交码、双正交码和超正交码均是线性分组码 例例6.2.56.2.5（（7 7，，3 3）超正交码的超正交矩阵）超正交码的超正交矩阵 和生和生成矩阵成矩阵G G分别为分别为 (3)里德里德-穆勒（穆勒（Reed-Muller））阶码阶码 是一种是一种线性分组码，满足线性分组码，满足其中各个子矩阵的定义为 1） 为 矩阵，由全1向量构成2） 为 矩阵，由所有可能的m元组组成矩阵的列向量3） 为 的所有两不同行向量的叉积构成其全部行向量的矩阵两向量的叉积为4） 为 的所有三不同行向量的叉积构成其全部行向量的矩阵5） 为 的所有 个不同行向量的叉积构成其全部行向量的矩阵 r例例6.2.66.2.6 的 阶RM码的各个子矩阵有 码的对偶码仍是一个Reed-Muller码，为 码。

 （（4 4）戈雷码）戈雷码 二元戈雷码是一种就纠二元戈雷码是一种就纠3个错的完备个错的完备线形分组码，线形分组码， 满足：满足： n=23 k=12{由于由于 因此某种二元（因此某种二元（23,12）码一定可以纠正任）码一定可以纠正任意小于等于意小于等于3 3个差错，所以个差错，所以 §6.3 循环码循环码 §6.3.1循环码的多项式描述循环码的多项式描述§6.3.2循环码的生成矩阵循环码的生成矩阵§6.3.4多项式运算电路多项式运算电路§6.3.3系统循环码系统循环码§6.3.5循环码的编码电路循环码的编码电路§6.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测§6.3.7BCH码与码与RS码码§§6.3.1 6.3.1 循环码的多项式描述循环码的多项式描述§§6.3.26.3.2循环码的生成矩阵循环码的生成矩阵§§6.3.36.3.3系统循环码系统循环码§§6.3.46.3.4多项式运算电路多项式运算电路§§6.3.56.3.5循环码的编码电路循环码的编码电路§§6.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测§§6.3.7BCH6.3.7BCH码与码与RSRS码码 更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。

循环码即是采用循环移位特性界定的一类线性分组码 6.3.1 6.3.1 循环码的多项式描述循环码的多项式描述定义定义 如果一个线性分组码的任意一个码如果一个线性分组码的任意一个码字字c(n元组元组)都是另外一个码字都是另外一个码字c’的循环移位的循环移位,称此线性分组码为一个循环称此线性分组码为一个循环码码. 将循环码的码字用多项式将循环码的码字用多项式c(x)c(x)，，称为码多称为码多项式（简称码式）表示后，循环码集合表项式（简称码式）表示后，循环码集合表示示C(x),C(x), 例 6.3.2 如下确定的如下确定的C CA A是线性循环码是线性循环码，，C CB B是非循环的线性分组码，是非循环的线性分组码，C CC C是非线性的循环是非线性的循环码 ，      ，      定理：定理： （n,k）循环码循环码C( x)中存在唯一的一个中存在唯一的一个非零的，首一的和最低次为非零的，首一的和最低次为r（（r

循环码由生成多项式的倍式组成循环码由生成多项式的倍式组成定理：定理： g(x)是（是（n,k））循环码的生成多项式，循环码的生成多项式，当且仅当当且仅当g(x)是是xn-1的的r=n-k次因式§§6.3.16.3.1循环码的多项式描述循环码的多项式描述§6.3.2 循环码的生成矩阵循环码的生成矩阵§§6.3.36.3.3系统循环码系统循环码§§6.3.46.3.4多项式运算电路多项式运算电路§§6.3.56.3.5循环码的编码电路循环码的编码电路§§6.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测§§6.3.7BCH6.3.7BCH码与码与RSRS码码6.3.2循环码的生成矩阵和校验矩阵(n,k)循环码的生成矩阵为循环码的生成矩阵为(n,k)循环码的校验矩阵为循环码的校验矩阵为§§6.3.16.3.1循环码的多项式描述循环码的多项式描述§§6.3.26.3.2循环码的生成矩阵循环码的生成矩阵§6.3.3 系统循环码系统循环码§§6.3.46.3.4多项式运算电路多项式运算电路§§6.3.56.3.5循环码的编码电路循环码的编码电路§§6.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测§§6.3.7BCH6.3.7BCH码与码与RSRS码码6.3.3 系统循环码系统循环码循环码的系统码码式为循环码的系统码码式为§§6.3.16.3.1循环码的多项式描述循环码的多项式描述§§6.3.26.3.2循环码的生成矩阵循环码的生成矩阵§§6.3.36.3.3系统循环码系统循环码§§6.3.4 6.3.4 多项式运算电路多项式运算电路§§6.3.56.3.5循环码的编码电路循环码的编码电路§§6.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测§§6.3.7BCH6.3.7BCH码与码与RSRS码码6.3.4 6.3.4 多项式运算电路多项式运算电路因为多项式因为多项式表示时间序列表示时间序列所以多项式的计算表现为对时间序列的操作.多项式多项式a(x)与与b(x相加电路相加电路 a(x)与与g(x)的一般乘法电路的一般乘法电路§§6.3.16.3.1循环码的多项式描述循环码的多项式描述§§6.3.26.3.2循环码的生成矩阵循环码的生成矩阵§§6.3.36.3.3系统循环码系统循环码§§6.3.46.3.4多项式运算电路多项式运算电路§6.3.5 循环码的编码电路循环码的编码电路§§6.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测§§6.3.7BCH6.3.7BCH码与码与RSRS码码1.1.非循环码编码器非循环码编码器 根据多项式乘法电路和循环码码式是生多多项式乘法电路和循环码码式是生多项式倍式原理，多项式乘法电路项式倍式原理，多项式乘法电路( (图图6.3.4) 6.3.4) 是循环码的非系统码电路，又称为是循环码的非系统码电路，又称为循环循环码乘法编码电路码乘法编码电路图图 6.3.46.3.42. 2. 系统编码电路系统编码电路 循环码系统编码电路由乘法电路，求余式循环码系统编码电路由乘法电路，求余式电路以及加法开关电路组成电路以及加法开关电路组成,如图如图6.3.14所所示示,电路工作过程如表电路工作过程如表6.3.2所示所示.图图 6.3.14表表 6.3.2 6.3.2 循环码系统码编码电路工作过程循环码系统码编码电路工作过程§§6.3.1 6.3.1 循环码的多项式描述循环码的多项式描述§§6.3.2 6.3.2 循环码的生成矩阵循环码的生成矩阵§§6.3.3 6.3.3 系统循环码系统循环码§§6.3.4 6.3.4 多项式运算电路多项式运算电路§§6.3.5 6.3.5 循环码的编码电路循环码的编码电路§§6.3.6 6.3.6 循环码的伴随多项式与检测循环码的伴随多项式与检测§§6.3.7 BCH6.3.7 BCH码与码与RSRS码码循环码的译码分成检错译码与纠错译码两类循环码的译码分成检错译码与纠错译码两类.1.1.检错译码原理检错译码原理2.2.纠错译码纠错译码 循环码的纠错译码要达到码的最小距离依赖于循环码的纠错译码要达到码的最小距离依赖于具体的循环码的结构具体的循环码的结构.§§6.3.16.3.1循环码的多项式描述循环码的多项式描述§§6.3.26.3.2循环码的生成矩阵循环码的生成矩阵§§6.3.36.3.3系统循环码系统循环码§§6.3.46.3.4多项式运算电路多项式运算电路§§6.3.56.3.5循环码的编码电路循环码的编码电路§§6.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测§§6.3.7 BCH6.3.7 BCH码与码与RSRS码码BCH码是一类能够先确定纠错能力码是一类能够先确定纠错能力t，，然后设然后设计码长和生成多项式的码。

对于任意的整计码长和生成多项式的码对于任意的整数数m和可达到纠错数和可达到纠错数t，，都可以构造出一个都可以构造出一个设计距离为设计距离为d0的二元本原的二元本原BCH码满足：码满足： n=2m-1,r=n-k≤mt,dmin≥d0=2t+1RS码是多元码是多元BCH码的一个子类，码字向量码的一个子类，码字向量的每个分量可以表示的每个分量可以表示`为为m比特，其基本参数为：比特，其基本参数为： 码长：码长：n=2m-1( 符号符号)=m(2m-1)（（比特）比特） 校验位长：校验位长： r=n-k=2t(符号符号)=m·2t其中其中t为为RS码可以纠正的差错符号数码可以纠正的差错符号数.§§6.4 6.4 卷积码卷积码 §§6.4.26.4.2卷积码的多项式描述卷积码的多项式描述 §§6.4.36.4.3卷积码的状态转移图与格描述卷积码的状态转移图与格描述§§6.4.46.4.4维特比（维特比（ViterbiViterbi））译码算法译码算法§§6.4.16.4.1卷积码的矩阵描述卷积码的矩阵描述§6.4.1 卷积码的矩阵描述卷积码的矩阵描述§6.4.2卷积码的多项式描述卷积码的多项式描述§6.4.3卷积码的状态转移图与格描述卷积码的状态转移图与格描述§6.4.4维特比（维特比（Viterbi））译码算法译码算法卷积码编码卷积码编码：当前输出 不仅与当前输入消息 相关，还与此前输入的 个消息 相关， 二元线性卷积码二元线性卷积码： 是仅由模二加运算组成的布尔函数布尔函数 的长度恒为 比特， 的长度恒为长度恒为 n比特，均称为一段 任意一输入段 与输出段 的关系都是一个特殊的 线性分组码的编码线性分组码的编码 卷积编码的离散卷积表达式卷积编码的离散卷积表达式卷积码的记忆长度（段）： 约束长度（段）： 或或 结尾处理结尾处理：额外输入 段无效的0数据 比特，保证编码器回到全全0 0的初态的初态 有限 段长消息的编码速率为： 渐近编码速率渐近编码速率： 卷积码的生成矩阵卷积码的生成矩阵 二元线性 卷积码 定义定义基本生成矩阵基本生成矩阵 ：生成矩阵 的前 行， 列组成的子矩阵 第 个生成元 ： 的第 行，描述 了所有各段输入中的第 位输入比特 对所有输出比特输出比特的影响 将 的元素 的列下标 表示为表示为 则输入移位寄存器移位寄存器中的第 段的第 位输入比特 参与第 位输出比特的编码 < -- > 不参与第 位输出比特的编码 < -- > 卷积码卷积码的子生成元或生成序列生成序列： 元组 线性卷积码的矩阵（或向量）描述描述： 生成矩阵 ，基本生成矩阵基本生成矩阵 ，生成序列（生成元） 系统卷积码系统卷积码：卷积码每段输出的 位中有 位（如当前 位）恒等于每段输入的 位 其中 均为均为 矩阵。

由于对每个独立的输入段输入段（每段 比特，共3段）分别有分别有 基本生成矩阵 为 ，生成矩阵为 ，生成元为 ，生成 序列为序列为 §6.4.1卷积码的矩阵描述卷积码的矩阵描述§6.4.2 6.4.2 卷积码的多项式描述卷积码的多项式描述§6.4.3卷积码的状态转移图与格描述卷积码的状态转移图与格描述§6.4.4维特比（维特比（Viterbi））译码算法译码算法6.4.2 6.4.2 卷积码的多项式描述卷积码的多项式描述消息段序列的多项式表示消息段序列的多项式表示多项式描述更直接的描述了描述了（二元） 卷积码作为一个 （比特）入， （比特） 出的编码关系编码关系 编码输出段序列的多项式表示编码输出段序列的多项式表示线性 卷积码的多项式表达式为 线性 卷积码的多项式矩阵 ：为 的多项式矩阵 又称又称 为卷积码的延迟算子生成矩阵延迟算子生成矩阵 定理定理 线性 卷积码的多项式生成矩阵 对 满足 的 幂次项系数幂次项系数等于 生成序列 的第 个分量， 1 1即 的最大次数最大次数等于卷积码的记 忆长度 ，即 2例例6.4.56.4.5 前述例（2,1,2）卷积码重画如图 §6.4.1卷积码的矩阵描述卷积码的矩阵描述§6.4.2卷积码的多项式描述卷积码的多项式描述§§6.4.3 6.4.3 卷积码的状态卷积码的状态 转移图与格描转移图与格描述述§6.4.4维特比（维特比（Viterbi））译码算法译码算法卷积码与分组码的卷积码与分组码的明显区别明显区别是卷积码编是卷积码编码器要存储码器要存储m段信息，这些信息数据既要段信息，这些信息数据既要因新的输入而改变，又要影响当前的编码因新的输入而改变，又要影响当前的编码 输出，因此称存储表达这些数据的参量为输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，卷积编码器的内部状态，简称状态。

简称状态状态状态：既要因新的输入而改变，又要 影响当前的编码输出的数据编码输出的数据 卷积编码器有效的存贮单元存贮单元数为 其中 为每个输入移位寄存器的 有效级数有效级数（寄存单元数）因此二元卷积 码的状态变量记为状态向量 或简记为简记为 状态数状态数：二元 卷积码共有 个不同的状态，记为 状态转移状态转移：当状态为 （或 ）时， 输入段 （或 ）产生编码输出段编码输出段 （或 ），并使该 状态改变（称为 转移）到新的状态 （或 ） 转移分支转移分支： 到 的转移过程，记为 （ ， ）或（ ， ），并标 记为 或 分支为有向边描述卷积码的所有不同状态 转移的有向图 状态转移图：以状态为结点，转移 状态转移方程状态转移方程： 与 的关系 输出方程输出方程：  与 的关系 尽管卷积码有 个状态，但是由于每段 的输入为 比特只有 种状态的变 化，每个状态只转移到 个状态的某个 子集（ 个状态）中去，每个状态 也只能由某 个状态的状态子集转移状态子集转移 而来 例例 6.4.106.4.10状态转移图（闭合形）状态转移图（闭合形） 状态转移图（开放形）状态转移图（开放形） 状态转移方程和输出方程分别为 卷积编码器工作过程：卷积编码器工作过程： * 卷积编码器工作初态为 （全0状态） * 消息段序列 产生输出段序列 * 消息段序列产生状态序列 栅格图或篱笆图栅格图或篱笆图：开放形的状态转移图按时间顺序级联 编码路径编码路径：状态序列 在栅格图中形成一条有向路径 一个卷积码码字一个卷积码码字：有向路径始于全0状态 ，又终于 时的一条有向路径 对于 的卷积码，常用实线表示时输入产生的转移分支，用虚线表示时输入产生的转移分支 例 6.4.13 前述例6.4.1（2，1，2）码的栅格图及几条路径例 路径A                               消息A（100）    输出A（11 10 11）路径B                               消息B（10110）  输出B（11 10 00 01 01）路径C 消息C（110100） 输出C（11 01 10 01 11） （1）卷积码的一个分支或转移是栅格图（或状态图）中接续状态的容许连接。

2）  卷积码的一条路径是可容许连接的分支串3） 卷积码的码字是始于零状态并首次终于零状态的路径结论结论§§6.4.16.4.1卷积码的矩阵描述卷积码的矩阵描述§§6.4.26.4.2卷积码的多项式描述卷积码的多项式描述§§6.4.36.4.3卷积码的状态转移图与格描述卷积码的状态转移图与格描述§6.4.4 维特比（维特比（Viterbi）译码算法）译码算法 卷积码的最大似然译码的基本方法卷积码的最大似然译码的基本方法：： 寻找一条路径 使似然值（概率）或对数似然值最大* 对应于发送码字或路径的接收段序列为* 各个码字假设为等概发送 对于无记忆信道和有限 段接收序列，最大似然译码是寻求一条路径 ，使得 其中 表示一条段记号从 到 的 段长路径 分分支支似似然然值值：：第   时刻连接至状态    的分支的分支度量值               ，简记连接至连接至 最大累积度量值最大累积度量值 ：：路径的分支度量值之和的最大值，简记 定义定义定义定义连接至状态连接至状态      幸幸存存路路径径：：具有最大累积度量值的路径的幸存分支：的幸存分支： 的最后分支 显然每个状态有 个可能的分支度量，每个状态只有一条幸存路径，每个时刻有 个可能的分支度量，每个时刻有 条幸存路径 定义定义有限长度有限长度 的的ViterbiViterbi算法算法：： （1.1）   段计数    =0（1.2）   最大累积度量值（1.3）幸存路径 （1）初始化（2）迭代 （2.1）接收序列段（2.2）段计数加1，（2.3）对 重复进行 （2.3.1）对分别计算分支度量值 （2.3.2）对 分别计算累积度量值 （2.3.3）计算最大累积度量值 （2.3.4）形成第 状态 的幸存分支，并存贮到达此状态的幸存路径（3）输出 （3.1）若 ，则返回第（2）步迭代 （3.2）若 ，则求最大累积度量值为的幸存路径 并输出该条路径对应的消息序列 。

 例例6.4.146.4.14 对例6.4.1非系统（2，1，2）卷积码的Viterbi译码例 设编码器输出为全0比特序列，经过BSC，接收序列 为 * 在Viterbi译码的极小（大）计算中，如果有两条以上路径的累积路径值相等，则任选一条为幸存路径* 当差错图案是可纠正的情形时，Viterbi译码过程会产生路径合并现象 =（10 00 01 00 00 00 00 …） 自由距离自由距离 ：所有非零码字路径的最小Hamming重量，即 其中 是长为 段的非零消息， 是对应的卷积编码码字 例例6.4.156.4.15对例6.4.1非系统（2，1，2）码其自由距离 =5 定义定义。