第六章信道编码.pptx
信道编码的作用和分类信道编码的作用和分类：编码信道：检错和纠错原理：检错和纠错方式和能力第1页/共153页信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号线路编码如何避免少量差错信号对信息内容的影响纠错编码广义信道编码=特定信道上传输信息而进行的传输信号或信号格式的设计与实现 第2页/共153页 描述编码 用于对特定数据信号的描述 约束编码 用于对特定信号特性的约束 扩频编码 用于扩展信号频谱为近似白噪声谱并满足某些相关特性 纠错编码 用于检测与纠正信号传输过程中因噪声干扰导致的差错1234第3页/共153页：信道编码的作用和分类：信道编码的作用和分类编码信道编码信道：检错和纠错原理：检错和纠错原理：检错和纠错方式和能力：检错和纠错方式和能力第4页/共153页消息消息信道编码信道编码编码信道编码信道信道译码信道译码码字码字接收向量接收向量消息消息编码信道模型编码信道模型第5页/共153页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第6页/共153页BSC转移概率BSC编码信道BSC输入输出关系等效为第7页/共153页差错图案：随机序列 或 ，第位上的一个随机错误：长的突发错误：第 至第 位之间有很多错误对于一个BSCBSC信道总有转移概率 1/21/2，比特传输中发生差错数目越少，概率越大，即从而总认为发生差错的图案是差错数目较少的图案第8页/共153页二元软判决信道 用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出 信道干扰信道干扰z z为零均值正态分布的随机变为零均值正态分布的随机变量，噪声干扰功率为均方差量，噪声干扰功率为均方差 ，z z的概率分的概率分布为布为 。对于。对于BPSKBPSK调制，二元输入符号调制，二元输入符号 为二元符号取值为为二元符号取值为+1+1或或-1-1 第9页/共153页第10页/共153页：信道编码的作用和分类：信道编码的作用和分类：编码信道：编码信道检错和纠错原理检错和纠错原理：检错和纠错方式和能力：检错和纠错方式和能力第11页/共153页检纠错是根据信道输出序列 自身判断是否可能是发送 的，或纠正导致 不等于 的错误。冗余编码：码字 的长度 一定大于消息 的长度纠错编码编码码率 ：每个码字的序列符号（或码元）平均传送的消息比特数第12页/共153页偶（或奇）校验方法：实现检纠错目的的一个基本方法。一个偶校验位 是对消息 使得如下校验方程成立的二进制符号，即一个偶校验码码字一个码率为 的 偶校验码，所有可能的 的全体校验方程为1 1表明一定有奇数个差错，校验方程为0 0表明可能有偶数个差错第13页/共153页 m0+m1+m2+mk1+p=0（mod 2）称c=(m0,m1,m2mk-1,p)为一个偶校验字 确定校验位P的编码方程为：P=m0+m1+mk-1第14页/共153页编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部按某种校验方程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字 和其码率分别为第15页/共153页第16页/共153页重复消息位：实现检纠错目的第二个基本方法一个 重复码是一个码率为 的码，仅有两个码字 和 ，传送1 1比特（）消息。重复码可以检测出任意小于 个差错的错误图案，纠正任意小于 个差错的错误图案。纠纠1 1位差错位差错的的3 3重复码重复码第17页/共153页等重码或定比码：实现检纠错的第三个方法。设计码字重量 恒为常数，即例如一种用于表示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等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错第18页/共153页：信道编码的作用和分类：编码信道：检错和纠错原理检错和纠错方式和能力检错和纠错方式和能力第19页/共153页纠错码的应用方式：前向纠错方式（FECFEC），自动请求重发（ARQARQ）方式，混合纠错（HECHEC）方式以及信息反馈（IRQIRQ方式）FEC与ARQ纠错应用方式第20页/共153页 常用汉明距离来描述检纠差错的数目，对于两n 长向量u，v汉明距离为：最小汉明距离 （最小码距d d）：任意两码字之间的汉明距离的最小值第21页/共153页定理 对一个最小距离为 纠错码，如下三个结论仅有其中任意一个结论成立，（1 1）可以检测出任意小于等于 个差错；（2 2）可以纠正任意小于等于 个差错；（3 3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足第22页/共153页最小码距与检纠错能力最小码距与检纠错能力 第23页/共153页差错概率：通信作为一个统计过程时，纠检错能力的统计特性。FECFEC方式纠错码的码字差错概率：发送码字 的先验概率：码字数，对于充分随机的消息源第24页/共153页对BSCBSC信道最大化 等价于 最小化，最小差错概率译码等价为使接收向量与输出码字距离最小的最小距离译码，即第25页/共153页信息比特信噪比 ：传输一个比特信息所需的最小信噪比 比特差错概率 （又称误码率）与信噪比 的关系如下图所示，采用纠错码后，达到同样比特差错概率实际需要的信噪比减小量称为编码增益。编码增益编码增益第26页/共153页6.2 线性码线性码 线性分组码的描述线性分组码的译码码例与码的重构第27页/共153页线性分组码的描述线性分组码的描述线性分组码的译码线性分组码的译码码例与码的重构码例与码的重构第28页/共153页一个（n,k）线形分组码C是称为码字c的n维向量的集合 C=c|c=mG其中m为任意的k维向量并称为消息向量。G是k行n行列秩为k（nk）的矩阵并称为生成矩阵，第29页/共153页对于二元编码，和 是二元向量，是一个二元矩阵，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算。表模二加表模二加/乘法表乘法表第30页/共153页例3 3重复码是一个（3 3，1 1）线性分组码第31页/共153页例（4 4，3 3）偶校验码是一个（4 4，3 3）线性分组码第32页/共153页当生成矩阵 给定时线性分组码有如下性质：（1 1）零向量 一定是一个码字，称为零码字；（2 2）任意两码字的和仍是一个码字；（3 3）任意码字 是 的行向量 的线性组合；（4 4）线性分组码的最小距离等于最小非零码字重量。第33页/共153页由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为0 0来判断传输是否可能有错，那么必有一个矩阵 满足显然 的每一列或 的每一行确定了一个可能的分组码的校验方程，的线性不相关行数最少要等于该码的所有可能的校验方程数，称这样的 矩阵 为 线性分组码的一致校验矩阵。第34页/共153页由 的每一行都是一个码字有由现行空间的理论，当H的行秩为r时，H作为一个(n,k)线性分组码的生成矩阵所生成的码是与G对应空间正交的r维线性子空间，称为(n,k)线性分组码的对偶码或对偶空间，并且有如下的维数关系成立第35页/共153页T定理：任何满足下式的n维向量a均是一（n,k）线形分组码的码字 aH=其中满足公式的H矩阵形式不唯一，但一个码的对偶码是惟一的。T第36页/共153页系统码：生成矩阵 具有如下形式在码字集合不变的情况下，任何一个线性分组码都可以一对一的去对应一个系统码。对于系统码相应的一致校验矩阵注意 与 仍然满足 。以线性分组码的一致校验矩阵为生成产生的线性分组码称为原线性分组码的对偶码。第37页/共153页例6.2.36.2.3一个（5 5，3 3）线性分组码的其中 到 的行初等变换过程为（表示第i i行），第38页/共153页（5，3）线性分组码码例 消息mG生成码字Gs生成码字对偶码码字0000010100111001011101110000011010010111000110110011001110100111000000011101011011001000110110110101110100000111010111010011第39页/共153页由一致校验矩阵可以比较容易确定线性分组码的最小码距定理 线性分组码的最小码距为 ，当且仅当其一致校验矩阵H中任意 列线性无关，某 列线性相关。该定理实际给出了计算线性分组码最小码距的一该定理实际给出了计算线性分组码最小码距的一种方法种方法。第40页/共153页线性分组码的描述线性分组码的描述线性分组码的译码线性分组码的译码码例与码的重构码例与码的重构第41页/共153页译码的概念检错译码：译码器输出为当前接收向量r和r是否有差错的标志s s，即 。第42页/共153页纠错译码的译码成功状态纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字 ，即 。第43页/共153页纠错译码的译码成功状态：译码器能够在达到纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的译码码字差错概率最小条件下输出一个确切的码字码字 ，即，即 。纠错译码的译码失败状态：译码器不能输出一纠错译码的译码失败状态：译码器不能输出一个确切的码字，通常此时的输出个确切的码字，通常此时的输出y y与检错译码输与检错译码输出相同。出相同。第44页/共153页定义：定义：(n,k (n,k）线形分组码的伴随式是一个）线形分组码的伴随式是一个r(r=n-k)r(r=n-k)维向量维向量s s ，则传输中一定有错误发生，则传输中要么无差错发生，要么差错图案恰好为一个码字。第45页/共153页定理 可纠t错的q元线性分组码满足 第46页/共153页伴随式纠错译码的通用译码方法（1）按最可能出现的 个差错图案 ，计算相应 的伴随式 ，并构造伴随式差错图案表 ；（2）对接收向量 计算伴随式 ；（3）查 表得 ；（4）纠错计算 。第47页/共153页线性分组码的描述线性分组码的描述线性分组码的译码线性分组码的译码码例与码的重构码例与码的重构第48页/共153页常见的线形分组码有重复码，汉明码，里德-穆勒码，戈雷码（1）汉明码：二元 HammingHamming码是一种 的完备码，满足其中列向量 为全部可能的非零 元组。第49页/共153页Hamming码的对偶码是一个 线性分组码，称为最大长度码，由于所有非零码字的重量均为 ，又称为等距码或单形（simplex）码。第50页/共153页例一个二元（7 7，4 4）HammingHamming码的系统码形式的矩阵和校验矩阵分别为等价的编码方程为第51页/共153页伴随式计算方程第52页/共153页（2 2）HadamardHadamard码HadamardHadamard码是由HadamardHadamard矩阵派生出的一种纠错码。阶实HadamardHadamard矩阵由元素为+1+1，-1-1的矩阵递归定义为例如第53页/共153页第54页/共153页 Hadamard矩阵为正交矩阵，即 中的任意不同两行（列）的点积为0，即 超正交矩阵 ：Hadamard矩阵 中的第1列（全+1列）去掉后由于任两行的点积为-1。将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。第55页/共153页（A）正交码：以 的全部行向量的0/1映射向量为码字。（B）双正交码：以 和-的全部行向量的0/1映射向量为码字。第56页/共153页（C）超正交码：以 的全部行向量的0/1映射向量为码字。可以证明正交码、双正交码和超正交码均是线性分组码。第57页/共153页例6.2.56.2.5（7 7，3 3）超正交码的超正交矩阵 和生成矩阵G G分别为第58页/共153页(3)里德-穆勒（Reed-Muller）阶码 是一种线性分组码，满足第59页/共153页其中各个子矩阵的定义为1）为 矩阵，由全1向量构成。2）为 矩阵，由所有可能的m元组组成矩阵的列向量。3）为 的所有两不同行向量的叉积构成其全部行向量的矩阵。两向量的叉积为4）为 的所有三不同行向量的叉积构成其全部行向量的矩阵。5）为 的所有 个不同行向量的叉积构成其全部行向量的矩阵。r第60页/共153页例6.2.66.2.6 的 阶RM码的各个子矩阵有第61页/共153页码的对偶码仍是一个Reed-Muller码，为 码。第62页/共153页（4 4）戈雷码）戈雷码 二元戈雷码是一种就纠3个错的完备线形分组码，满足：n=23 k=12第63页/共153页由于因此某种二元（23,12）码一定可以纠正任意小于等于3 3个差错，所以第64页/共153页6.3 循环码循环码 循环码的多项式描述循环码的生成矩阵多项式运算电路系统循环码循环码的编码电路循环码的伴随多项式与检测码与RS码第65页/共153页循环码的多项式描述循环码的多项式描述循环码的生成矩阵循环码的生成矩阵系统循环码系统循环码多项式运算电路多项式运算电路循环码的编码电路循环码的编码电路循环码的伴随多项式与检测循环码的伴随多项式与检测码与码与RSRS码码第66页/共153页 更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。循环码的多项式描述循环码的多项式描述第67页/共153页第68页/共153页第69页/共153页定义 如果一个线性分组码的任意一个码字c(n元组)都是另外一个码字c的循环移位,称此线性分组码为一个循环码.将循环码的码字用多项式c(x)c(x)，称为码多项式（简称码式）表示后，循环码集合表示C(x),C(x),第70页/共153页例 如下确定的如下确定的C CA A是线性循环码，是线性循环码，C CB B是非循环是非循环的线性分组码，的线性分组码，C CC C是非线性的循环码。是非线性的循环码。，第71页/共153页定理：（n,k）循环码C(x)中存在唯一的一个非零的，首一的和最低次为r（rn）的码 多项式g(x)满足：g(x)=xr+gr-1xr-1+.+g1X+g0 g00 r=n-k并且c(x)是码式当且仅当c(x)是g(x)的倍式第72页/共153页定义 由上述定理确定的码式g(x)g(x)称为循环码(n,k)(n,k)的生成多项式.因此(n,k)(n,k)循环码的构造是如何构造生成多项式g(x)g(x)。循环码由生成多项式的倍式组成第73页/共153页定理：g(x)是（n,k）循环码的生成多项式，当且仅当g(x)是xn-1的r=n-k次因式。第74页/共153页第75页/共153页第76页/共153页第77页/共153页循环码的多项式描述循环码的多项式描述循环码的生成矩阵循环码的生成矩阵系统循环码系统循环码多项式运算电路多项式运算电路循环码的编码电路循环码的编码电路循环码的伴随多项式与检测循环码的伴随多项式与检测码与码与RSRS码码第78页/共153页循环码的生成矩阵和校验矩阵循环码的生成矩阵和校验矩阵(n,k)循环码的生成矩阵为第79页/共153页(n,k)循环码的校验矩阵为第80页/共153页循环码的多项式描述循环码的多项式描述循环码的生成矩阵循环码的生成矩阵系统循环码系统循环码多项式运算电路多项式运算电路循环码的编码电路循环码的编码电路循环码的伴随多项式与检测循环码的伴随多项式与检测码与码与RSRS码码第81页/共153页系统循环码循环码的系统码码式为第82页/共153页第83页/共153页循环码的多项式描述循环码的多项式描述循环码的生成矩阵循环码的生成矩阵系统循环码系统循环码多项式运算电路多项式运算电路循环码的编码电路循环码的编码电路循环码的伴随多项式与检测循环码的伴随多项式与检测码与码与RSRS码码第84页/共153页多项式运算电路多项式运算电路因为多项式因为多项式表示时间序列表示时间序列所以多项式的计算表现为对时间序列的操作.第85页/共153页多项式a(x)与b(x相加电路第86页/共153页 a(x)与g(x)的一般乘法电路第87页/共153页第88页/共153页循环码的多项式描述循环码的多项式描述循环码的生成矩阵循环码的生成矩阵系统循环码系统循环码多项式运算电路多项式运算电路循环码的编码电路循环码的编码电路循环码的伴随多项式与检测循环码的伴随多项式与检测码与码与RSRS码码第89页/共153页1.1.非循环码编码器非循环码编码器 根据多项式乘法电路和循环码码式是生多多项式乘法电路和循环码码式是生多项式倍式原理，多项式乘法电路项式倍式原理，多项式乘法电路(图是循环码的非系统码电路，又称为图是循环码的非系统码电路，又称为循环码循环码乘法编码电路乘法编码电路图图 6.3.46.3.4第90页/共153页2.2.系统编码电路系统编码电路 循环码系统编码电路由乘法电路，求余式电路以及加法开关电路组成,如图所示,电路工作过程如表所示.图 6.3.14第91页/共153页表表 循环码系统码编码电路工作过程循环码系统码编码电路工作过程第92页/共153页循环码的多项式描述循环码的多项式描述循环码的生成矩阵循环码的生成矩阵系统循环码系统循环码多项式运算电路多项式运算电路循环码的编码电路循环码的编码电路循环码的伴随多项式与检测循环码的伴随多项式与检测码与码与RSRS码码第93页/共153页循环码的译码分成检错译码与纠错译码两类.1.1.检错译码原理检错译码原理第94页/共153页2.2.纠错译码纠错译码 循环码的纠错译码要达到码的最小距离依赖于具体的循环码的结构.第95页/共153页循环码的多项式描述循环码的多项式描述循环码的生成矩阵循环码的生成矩阵系统循环码系统循环码多项式运算电路多项式运算电路循环码的编码电路循环码的编码电路循环码的伴随多项式与检测循环码的伴随多项式与检测码与码与RSRS码码第96页/共153页BCH码是一类能够先确定纠错能力t，然后设计码长和生成多项式的码。对于任意的整数m和可达到纠错数t，都可以构造出一个设计距离为d0的二元本原BCH码满足：n=2m-1,r=n-kmt,dmind0=2t+1第97页/共153页RS码是多元BCH码的一个子类，码字向量的每个分量可以表示为m比特，其基本参数为：码长：n=2m-1(符号)=m(2m-1)（比特）校验位长：r=n-k=2t(符号)=m2t其中t为RS码可以纠正的差错符号数.第98页/共153页6.4 6.4 卷积码卷积码 卷积码的多项式描述卷积码的多项式描述 卷积码的状态转移图与格描述卷积码的状态转移图与格描述维特比（维特比（ViterbiViterbi）译码算法）译码算法卷积码的矩阵描述卷积码的矩阵描述第99页/共153页卷积码的矩阵描述卷积码的矩阵描述卷积码的多项式描述卷积码的状态转移图与格描述维特比（Viterbi）译码算法第100页/共153页卷积码编码卷积码编码：当前输出 不仅与当前输入消息 相关，还与此前输入的 个消息 相关，二元线性卷积码二元线性卷积码：是仅由模二加运算组成的布尔函数布尔函数 第101页/共153页的长度恒为 比特，的长度恒为长度恒为 n比特，均称为一段 第102页/共153页任意一输入段 与输出段 的关系都是一个特殊的 线性分组码的编码线性分组码的编码 第103页/共153页卷积编码的离散卷积表达式卷积编码的离散卷积表达式卷积码的记忆长度（段）：约束长度（段）：或或 第104页/共153页结尾处理结尾处理：额外输入 段无效的0数据 比特，保证编码器回到全全0 0的初态的初态 有限 段长消息的编码速率为：渐近编码速率渐近编码速率：第105页/共153页卷积码的生成矩阵卷积码的生成矩阵 二元线性 卷积码 定义定义第106页/共153页基本生成矩阵基本生成矩阵：生成矩阵 的前 行，列组成的子矩阵 第 个生成元：的第 行，描述 了所有各段输入中的第 位输入比特 对所有输出比特输出比特的影响 第107页/共153页将 的元素 的列下标 表示为表示为 则输入移位寄存器移位寄存器中的第 段的第 位输入比特 参与第 位输出比特的编码 不参与第 位输出比特的编码 第108页/共153页卷积码卷积码的子生成元或生成序列生成序列：元组 第109页/共153页线性卷积码的矩阵（或向量）描述描述：第110页/共153页生成矩阵，基本生成矩阵基本生成矩阵，生成序列（生成元）系统卷积码系统卷积码：卷积码每段输出的 位中有 位（如当前 位）恒等于每段输入的 位 第111页/共153页其中 均为均为 矩阵。第112页/共153页由于对每个独立的输入段输入段（每段 比特，共3段）分别有分别有 基本生成矩阵 为，生成矩阵为，生成元为，生成 第113页/共153页序列为序列为 第114页/共153页卷积码的矩阵描述卷积码的多项式描述卷积码的多项式描述卷积码的状态转移图与格描述维特比（Viterbi）译码算法第115页/共153页卷积码的多项式描述卷积码的多项式描述消息段序列的多项式表示消息段序列的多项式表示第116页/共153页多项式描述更直接的描述了描述了（二元）卷积码作为一个（比特）入，（比特）出的编码关系编码关系 编码输出段序列的多项式表示编码输出段序列的多项式表示第117页/共153页线性 卷积码的多项式表达式为 线性 卷积码的多项式矩阵：为 的多项式矩阵 又称又称 为卷积码的延迟算子生成矩阵延迟算子生成矩阵。第118页/共153页定理定理 线性 卷积码的多项式生成矩阵 对 满足 的 幂次项系数幂次项系数等于 生成序列 的第 个分量，1 1第119页/共153页即的最大次数最大次数等于卷积码的记 忆长度，即2第120页/共153页例例 前述例（2,1,2）卷积码重画如图 第121页/共153页卷积码的矩阵描述卷积码的多项式描述卷积码的状态卷积码的状态 转移图与格描述转移图与格描述维特比（Viterbi）译码算法第122页/共153页卷积码与分组码的明显区别是卷积码编码器要存储m段信息，这些信息数据既要因新的输入而改变，又要影响当前的编码 输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，简称状态。第123页/共153页状态：既要因新的输入而改变，又要影响当前的编码输出的数据。卷积编码器有效的存贮单元数为第124页/共153页其中为每个输入移位寄存器的有效级数（寄存单元数）。因此二元卷积码的状态变量记为状态向量或简记为第125页/共153页状态数：二元卷积码共有个不同的状态，记为状态转移：当状态为（或）时，输入段（或）产生编码输出段编码输出段（或），并使该状态改变（称为转移）到新的状态（或）。第126页/共153页转移分支转移分支：到 的转移过程，记为（，）或（，），并标 记为 或 分支为有向边描述卷积码的所有不同状态 转移的有向图 状态转移图：以状态为结点，转移 第127页/共153页状态转移方程状态转移方程：与的关系输出方程输出方程：与的关系第128页/共153页尽管卷积码有个状态，但是由于每段的输入为比特只有种状态的变化，每个状态只转移到个状态的某个子集（个状态）中去，每个状态也只能由某个状态的状态子集转移状态子集转移而来。第129页/共153页例例 第130页/共153页状态转移图（闭合形）状态转移图（闭合形）第131页/共153页状态转移图（开放形）状态转移图（开放形）状态转移方程和输出方程分别为 第132页/共153页卷积编码器工作过程：*卷积编码器工作初态为 （全0状态）*消息段序列 产生输出段序列*消息段序列产生状态序列第133页/共153页栅格图或篱笆图：开放形的状态转移图按时间顺序级联编码路径：状态序列 在栅格图中形成一条有向路径一个卷积码码字：有向路径始于全0状态 ，又终于 时的一条有向路径对于 的卷积码，常用实线表示时输入产生的转移分支，用虚线表示时输入产生的转移分支第134页/共153页例 前述例（2，1，2）码的栅格图及几条路径例 第135页/共153页路径A消息A（100）输出A（111011）路径B消息B（10110）输出B（1110000101）路径C 消息C（110100）输出C（11 01 10 01 11）第136页/共153页（1）卷积码的一个分支或转移是栅格图（或状态图）中接续状态的容许连接。（2）卷积码的一条路径是可容许连接的分支串。（3）卷积码的码字是始于零状态并首次终于零状态的路径。结论结论第137页/共153页卷积码的矩阵描述卷积码的矩阵描述卷积码的多项式描述卷积码的多项式描述卷积码的状态转移图与格描述卷积码的状态转移图与格描述维特比（Viterbi）译码算法 第138页/共153页卷积码的最大似然译码的基本方法卷积码的最大似然译码的基本方法：寻找一条路径 使似然值（概率）或对数似然值最大*对应于发送码字或路径的接收段序列为*各个码字假设为等概发送 第139页/共153页对于无记忆信道和有限 段接收序列，最大似然译码是寻求一条路径 ，使得其中 表示一条段记号从 到 的 段长路径第140页/共153页分支似然值：第时刻连接至状态的分支的分支度量值，简记连接至 最大累积度量值 ：路径的分支度量值之和的最大值，简记定义定义第141页/共153页连接至状态幸存路径：具有最大累积度量值的路径的幸存分支：的最后分支显然每个状态有 个可能的分支度量，每个状态只有一条幸存路径，每个时刻有 个可能的分支度量，每个时刻有 条幸存路径定义第142页/共153页有限长度 的ViterbiViterbi算法：（1.1）段计数=0（1.2）最大累积度量值（1.3）幸存路径（1）初始化第143页/共153页（2）迭代（2.1）接收序列段（2.2）段计数加1，（2.3）对 重复进行（2.3.1）对分别计算分支度量值（2.3.2）对 分别计算累积度量值（2.3.3）计算最大累积度量值（2.3.4）形成第 状态 的幸存分支，并存贮到达此状态的幸存路径第144页/共153页（3）输出（3.1）若 ，则返回第（2）步迭代（3.2）若 ，则求最大累积度量值为的幸存路径 并输出该条路径对应的消息序列 。第145页/共153页例例 对例非系统（2，1，2）卷积码的Viterbi译码例 设编码器输出为全0比特序列，经过BSC，接收序列 为*在Viterbi译码的极小（大）计算中，如果有两条以上路径的累积路径值相等，则任选一条为幸存路径*当差错图案是可纠正的情形时，Viterbi译码过程会产生路径合并现象=（10 00 01 00 00 00 00）第146页/共153页第147页/共153页第148页/共153页第149页/共153页第150页/共153页第151页/共153页自由距离 ：所有非零码字路径的最小Hamming重量，即其中 是长为 段的非零消息，是对应的卷积编码码字。例6.4.156.4.15对例6.4.1非系统（2，1，2）码其自由距离 =5定义第152页/共153页感谢您的观看！第153页/共153页
