《信息处理与编码》课件第七章 信道编码

1、2022/7/28目的：提高通信系统传输的可靠性；目标：寻找具体构造编码的理论与方法；在理论上，Shannon第二编码定理已指出，只要当实际传信率Rk）的二进制码组。 线性分组码 2022/7/28线性分组码（续） 按数学上更为一般的定义可表示为： ，其中nk， 若f进一步满足下列线性关系： 其中： 由上述定义，可见线性分组码f可看成： 2022/7/28线性分组码（续） 线性分组码是分组码中最重要最有实用价值的一个子类，下面将从具体例子入手，阐明它的一些基本概念。 例：以（7，3）二元线性分组码为例，其中： ， ， ，这是输入编码器的信息为分成三个一组，即 ，它可按下列线性方程组编码： 20

2、22/7/28线性分组码（续） 写成矩阵形式 称G为生成矩阵，若 即能分解为单位方阵为子阵，且I的位置可任意，则称 为系统码 （或组织码）若将上述监督线性方程组改写为:2022/7/28线性分组码（续） 即 2022/7/28线性分组码（续） 再改变为矩阵形式: 即 HCT= OT (PI)CT=OT 称H为监督(校验)矩阵，若H=(PI)，即能分解为单位方阵为子阵，且I的位置可任意，则称C为系统（组织）码。2022/7/28线性分组码（续） 生成矩阵G一般用于发端编码，而监督矩阵H则一般用于接收端的译码。由于生成矩阵G中的每一行及其线性组合都是线性（n,k）码的码组（字），因此有： HGT=

3、 OT或GHT= O 它说明矩阵G与H互为零化空间。 由线性空间理论，一个n维的线性空间Vn可以分解为一对互为对偶的正交子空间Vk与Vn-k。 即： 2022/7/28线性分组码（续） 结合上面的例子；n=7,则有 显然有：(7,3)码的生成矩阵G3就是(7,4)码监督矩阵H3 ，(7,3)码的监督矩阵H4就是(7,4)码的生成矩阵G4 采用系统（组织）码来描述生成矩阵G与监督矩阵H，仅是其中的一种。在很多情况下是采用非系统码的描述方式，那么两者之间有没有什么实质上的差别？ 2022/7/28由线性代数理论，任何一个非系统的生成矩阵G均可以通过矩阵的初等变换得到相应的系统码的生成矩阵G。因此，

4、我们可以得到如下结论：任何一个线性分组（n,k）码，均可找到一个等价的系统码，而且还可以进一步证明只要在码率R和码长n相同的条件下，最优的系统码与最优的线性分组码具有相同的错误概率。 线性分组码的编码器特别是系统码极其简单，其具体结构可参见书上有关章节，就不再赘述。 线性分组码（续） 2022/7/28线性分组码（续） 线性分组码的译码，特别是系统码也比较简单，在数据通信中，最优译码即为最小误码准则下的译码，它在信源等概率即时，可等效为最大似然准则，当信道为BSC时，它又可等效为最小汉明距离准则，关于准则问题将在后面讨论卷积码的译码时进一步详细讨论。译码时，在接受端收到的信号点为： 且 其中

5、表示发送的码组（字） 表示传输中的差错。 2022/7/28线性分组码（续） 由监督方程： 即只要在传输中不产生差错，即 则必满足上式。实际上传输中一定产生差错，这时 ，则有 且有 我们称 为伴随子（校正子）， 这是由于 仅与 有关，而与码组（字） 无关。 对于一个(n,k)线形分组码，H矩阵是一个(n-k)行n列的矩阵，所以为一个（n-k）维的矢量。 它仅可以给出（n-k）个独立方程组，监督(n-k)位的差错。然而在信2022/7/28线性分组码（续） 2022/7/28线性分组码（续） 2022/7/28线性分组码（续） 2022/7/28线性分组码（续） 2022/7/28线性分组码（续

6、） 按照上述规则，可以将一个（n，k）线性分组码的译码，按照伴随式的规则划分为 个行矢量乘以 个列矢量所构成的下列标准阵列： 2022/7/28线性分组码（续） 称这种译码为伴随式译码，或称为查表译码。它原则上适合于任何（n，k）线性分组码。 伴随式译码步骤可归纳如下： 1）计算接受矢量 的伴随式： 2）由伴随式 决定相对应的陪集首 3）将 译成 其具体实现框图如下： 2022/7/28线性分组码（续） 2022/7/28线性分组码（续） 伴随式 陪集首0 0 00 0 0 0 0 0 0 1 0 01 0 0 0 0 0 00 1 00 1 0 0 0 0 0 0 0 10 0 1 0 0

7、0 01 1 00 0 0 1 0 0 0 0 1 10 0 0 0 1 0 01 1 10 0 0 0 0 1 01 0 10 0 0 0 0 0 1(7.4)码的陪集首集合2022/7/28线性分组码（续） 对于(7.4)码，若 其具体运算和纠正差错过程可参考书上的(7.4)线性分组码译码电路图。2022/7/28最小Hamming距判定定理定理：若C是(n,k)线性分组码，校验矩阵为H，dmin(C)=H矩阵线性相关的最小列数。因此，如果H矩阵所有的2t个列或更少的列之间相互独立，则该码能够纠正所有小于tbit的差错。2022/7/28证明：码字C=(c1, c2 ,cn)满足关系HCT

8、=0，而校验矩阵H=(h1, h2 ,hn)， 则HCT实际上是校验矩阵各列的线性组合，即： HCT= c1 h1+ c2 h2+ cn hn， 这说明，如果码字C的汉明重为w，则对应于H矩阵的w列线性相关，反之也成立。 而最小汉明距等于最小汉明重，因此定理得证。2022/7/28dmin(C1)=5dmin(C2)=2dmin(C3)=32022/7/28循环码 循环码是线性分组码中最主要，最有适用价值的一类，它是1957年由Prange首先提出 2022/7/28循环码（续） 基本定义：一个（n,k）线性分组码，经任意循环移位之后，仍然是线性分组码，则称它为循环码主要特点 1）理论成熟：可

9、利用成熟的代数结构深入探讨其性质； 2）实现简单；可利用循环移位特性在工程上进行编，译码； 3）循环码的描述方式有很多，但在工程上最有用的采用多项式的描述方法。 一一对应： n元码组(字) n阶(含0阶)码多项式 有限域 多项式域模运算 码组模2运算 多项式乘积运算 2022/7/28循环码（续）在多项式描述中，我们可以将“同余”（模）运算推广到多项式中。即2022/7/28循环码（续）则有下列多项式除法: 2022/7/28循环码（续）下面给出(7.3)码循环移位特性：（见下页）2022/7/28循环码（续）2022/7/28循环码（续） 可见推移7位后出现周期性循环特性. 下面进一步研究(

10、7.3)循环码生成矩阵表达式: 2022/7/28循环码（续） 可见,在循环码中,其生成矩阵结构更加简化,它是有生成多项式g(x)循环推移构成.书中给出k位信息位的一般化表达式,以及在一般情况下,当为系统码时循环码的生成矩阵表达式.有兴趣者可进一步仔细阅读. 在线性分组码中有: 对应于循环码中有: 例:仍以(7.3)循环码为例:2022/7/28循环码（续） (7,3)码生成多项式的阶次为:n-k=7-3=4,故有 或者 有线性分组码的对偶性,可求得对应(7,4)码的生成多项式与监督多项式如下: 或2022/7/28循环码（续）循环码的编码 例:若输入信息码元为:u=(1001)即 ,下面将简

11、介最简单的系统循环码的编译码.仍以(7,4)系统循环码为例: 我们所选的多项式 ,由系统码生成规则: 即： 2022/7/28循环码（续）2022/7/28循环码（续）其中最右边的4位是信息元，这样编码器结构图如下： 2022/7/28循环码（续）输出码字为: 2022/7/28循环码（续）上述编码过程如下： 三级寄码器的初态为000，信息元组以(即1001）分两路, 一路直接输出，另一路送入g(x)除法电路； 经四次移位后，信息元组1001全部输出，另一路也全部送入g(x)除法电路并完成除法电路运算。这时寄存器中的状态为余式r(x)即监督元 输出开关由1倒向2，并经三次移位，将监督元 跟在信

12、息元 后依次输出得到 c = = (0111001)。 2022/7/284.4 (n,k)循环码的译码2022/7/28线性码的译码线性码的译码是根据接收多项式的伴随式和可纠的错误图样间的一一对应关系，由伴随式得到错误图样。2022/7/28循环码的译码循环码是线性码的一个特殊子类，循环码的译码与线性码的译码基本一致，不过由于循环码的循环特性，它的译码更加简单。2022/7/28译码过程1. 接收多项式的伴随式计算。2. 求伴随式对应的错误图样。3. 用错误图样纠错。2022/7/28根据伴随式定义计算伴随式S设 ，其中表示H的行矢量；于是得到伴随式各分量的表示式：2022/7/28用k级移

13、存器的伴随式计算电路2022/7/28定理 4.4.1定理 4.4.1 二元线性系统中，接收矢量R的伴随式S等于对R的信息部分所计算的监督数字（相当于对R的信息部分重新编码）与接收的监督数字的矢量和。2022/7/28证明： 设接收矢量 ， 是R的信息部分，它是长度为k的矢量， 是R的监督数字部分，它是长度为 的矢量，监督矩阵为 ，Q为 阶子阵， 为 阶单位子阵。由伴随式的定义得：2022/7/28注意到Q是H中除单位子阵外的 阶子阵，所以 是把 作信息元重新编码计算的监督元。而 为接收的监督元。因此，定理可证。2022/7/28k级移存器实现的伴随式计算电路2022/7/28电路工作步骤 （

14、1）门1通，门2、3、4关，接收字R的k位信息部分输入编码器。（2）门1关，门2、3、4通，接收信息编码所得的监督数字与接收监督数字逐位模2和，得到伴随式。这里的伴随式计算方法只适用于线性系统码。2022/7/28n-k级移存器的伴随式计算电路2022/7/28设接收多项式为 ，它的信息部分表示为 ，监督部分表示为 ，由定理4.4.1经推导可得：上式表明循环码接收多项式的伴随式是接收多项式 除以 的余式，则可得到n-k级移存器的伴随式计算电路如下：2022/7/28n-k级移存器的伴随式计算电路2022/7/28定理4.4.2定理4.4.2 设 为接收矢量 的伴随式，则 的循环移位 （模 ）的

15、伴随式 等于伴随式 的循环移位 （模 ）。即：2022/7/28证明1证明：由伴随式计算式： 可知： 对上式两边作同余运算得 令 模 ，即用 表示 移位一次 模 的码多项式。2022/7/28证明2对式 进行模 运算，则得到 循环移位 的伴随式：由 可得： 证毕。2022/7/28定理4.4.2说明，接收矢量的循环移位（模 运算下）与伴随式在模 运算下（或在除以 的伴随式计算电路中）的循环移位是一一对应的。2022/7/28循环码的通用译码法梅吉特译码法2022/7/28译码电路2022/7/28工作过程整个译码电路的工作过程如下：（1）将接收矢量移入伴随式计算电路，计算出伴随式。同时将接收矢

16、量移入缓存器。（2）伴随式写入错误图样检测器，并在检测器中循环移位（模），同时将接收矢量移出缓存器，当监测器输出“1”时，表示缓存器此时刻的输出符号是错误的，并将错误纠正。同时检测器输出反馈到伴随式计算电路的输入端，去修改伴随式，从而消除该错误对伴随式所产生的影响。直到接收矢量全部移出缓存器，该接收矢量纠错完毕。若随后伴随式寄存器中为全零，则表示错误全部被纠正，否则检出了不可久的错误图样。2022/7/284.5循环汉明码2022/7/28定义4.5.1 ：以r次本原多项式为生成多项式的循环码称为循环汉明码。2022/7/28参数码长： 监督位数： 信息元数目： 码的最小距离为： 2022/7

17、/28特点汉明码是完备码，而且是高效码，这是汉明码的特点。因此，在构造循环汉明码时，只要选择不同的本原多项式作为生成多项式，就可以得到不同的（n, k）循环汉明码。2022/7/28例4.5.1例4.5.1应用梅吉特译码法实现（7，4）循环码的译码。（7，4）循环码是纠一个错误的循环汉明码。该循环码只需一个简单的组合逻辑电路对这一确定的伴随式进行检测就可以完成纠错。译码电路如图：2022/7/28（7，4）循环码译码电路2022/7/28译码电路的工作过程如下：（1）接受矢量送入伴随式计算电路，经七次移位得到伴随式。同时接收矢量移入缓存器。（2）将前一步所计算的伴随式转入伴随式自发运算电路。计

18、算并纠正错误。（3）当接收矢量全部移出缓存器后，完成一个码组的译码。当接收矢量开始移出缓存器时下一个接收矢量紧跟着移入伴随式计算电路和缓存器，重复第二步的过程，可实现连续对接收矢量纠错。2022/7/28例4.5.2例4.5.2 设计由生成的（15，11）循环汉明码的译码电路，如下图：2022/7/28（15，11）循环码译码电路2022/7/28（15，11）循环汉明码与（7，4）循环汉明码姨妈电路的工作原理是相同的。但（15，11）循环汉明码译码器未加伴随式自发运算电路，在接收完一个接收矢量后，伴随式还需要在伴随式计算电路循环一周以纠正所有码位上可能的错误。所以这种电路所需译码时间较长，不

19、能进行连续译码。采用哪种形式的电路要有信号来决定。2022/7/28译码的关键是伴随式译为错误图样的组合逻辑电路的实现问题。梅吉特译码法实现纠单个错误的循环码译码，电路特别简单，但纠多个错误的译码电路就复杂了，甚至难以实现。2022/7/28循环码（续）（7.4）循环码译码过程如下： 若 即 y=(1111001) 将其输入译码器，其译码过程如下列表格所示： 2022/7/28循环码（续）2022/7/28生成的（7.4）循环码译码器原理图循环码（续）2022/7/28上述译码器工作步骤如下： 首先将移位寄存器复0，清洗到初始状态； 输入y分两路进入译码器，一路进入缓存器，另一路经门1进入伴随

20、式计算电路，分别计算s0s1s2； 在输出y的同时，s0s1s2依次循环移位，无差错时，错误检测电路无输出，最后输出码元与接收的y中码元一致；有错误时，错误检测电路输出为1，它正好与y中的错误位在模2加中相遇，并自动予以纠正。 这一循环译码器与前面线性分组（7，4）码的译码器比较是实现结构简化了，在线性分组码中，对每一种伴随式要设计一个相对应的伴随式计算电路，而在循环（7，4）码中，可利用码的循环特性共用一套设备。 循环码（续）2022/7/28 循环码特别适合于检测错误，这是由于它具有很强的检测错误的能力，同时实现起来也较简单；CRC一般能检测如下错误： 突发长度n-k+1的突发错误； 大部

21、分长度=n-k+1的突发错误，其中不可检测错误仅占2-（n-k+1）； 大部分长度n-k+1的突发错误，其中不可检测错误仅占2-（n-k+1）； 所有与许用码组码距dmin-1的错误； 所有奇数个错误；常用CRC码已成国际标准有： CRC-12，其生成多项式：g(x)=1+x+x2+x3+x11+x12CRC检错码（cyclic redundancy check） 2022/7/28 CRC-16，其生成多项式：g(x)=1+x2+x15+x16 CRC-CCITT，其生成多项式：g(x)=1+x5+x12+x16 CRC-32，其生成多项式： g(x)=1+x+x2+x4+x5+x7+x8+

22、x10+x11+x12+x16+x22+x23+x26+x32 其中CRC-12用于6bit字符，其余则用于8bit字符。 CRC检错码（续） 2022/7/28 BCH 码是一类最重要的循环码，它能纠正多个随机错误，它是1959-1960年有Hocquenghem.bose与C handari 三位学者独立发现的二元线性循环码。人们将三人名字的字头BCH命名为BCH码。 BCH 码具有纠错能力强，构造方便，编，译码易于实现的一系列优点。 我们这里不讨论BCH码的理论与性质，因为它要涉及更深的近世代数的 群。环，域的知识；重点侧重于对BCH码的工程上的使用，即利用已知的BCH码表格，构造起对应

23、的生成多项式。 若循环码生成多项式为： g(x) = LCM m1(x),m3(x),m2t-1(x) 这里t为纠错的位数，mi(x)为素多项式，LCM为求最小公倍数。 BCH码2022/7/28 则由此生成多项式生成的循环码称为BCH码，其最小距： dmind0=2t+1(d0为设计码距)，它能纠正t个随机独立差错。 BCH码的码长为n=2m1或是n=2m1的因子，通常称前者为本原BCH码，称后者为非本原BCH码。 书中列出n的本原BCH码，和部分非本原BCH 码的生成多项式表与部分不可约的多项式表。例： 例1： BCH(15，5)码。 它是一个可纠正3个随机独立差错的BCH码，即t=3;

24、dd0 = 2t+1 = 2*3+1=7;BCH码（续）2022/7/28 n = 15 = 2m-1=24-1, m =4;查不可约多项式，可求得 m1(x) =(23)*8 = 010011 = x4 + x + 1 * m3(x) =(37)8 = 011111 = x4 + x3 + x2 + x + 1 m5(x) =(07)8 = 000111 = x2 + x + 1 g(x)=LCMm1(x),m3(x),m5(x) =LCM(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) =x10+x8+x5+x4+x2+x+1 注：*.(x x)8 是八进制表达式 *.本节中编

25、码序列与以前相反，它是从高位向低位排列，其原因，这里引用的三个表格是从高向低排。BCH码（续）2022/7/28 它是一类纠错能力很强的特殊的非二进制BCH码.对于任选正整数S可构造一个相应的码长为n=q5-1的 q进制BCH码,而q作为某个素数的幂.当S=1 q2时所建立的码长n=q-1的q进制BCH码,称它为RS码.当q=2m(m1),其码元符号取自于F(2)的二进制RS码可用来纠正突发差错，它时最常用的RS码 RS码的构造一个可纠正个符号错误的RS码有如下参数： 码长：n2m-1符号，或m（2m-1）比特； 信息位：位符号，或km位比特； 监督位：n-k2t位符号， 或m（n-k）2mt

26、比特； RS(Reed Solomen)码 2022/7/28 最小码距：dmin=d0=2t+1, 或mdminm（2t+1）比特RS码的纠错能力 具有同时纠正随机与突发差错的能力 它可纠正的错误图样有： 总长度为：（t-1）m+1比特的单个突发； 总长度为：（t-3）m+3比特的两个突发； 总长度为：b=（t-2i+1）m2I-1比特的个突发 RS(Reed Solomen)码 （续）2022/7/28 例：试构造一个能纠正三个符号错误，码长n15，m的RS码 已知，； 求得码距为： 个符号 比特； 监督位：n-k2t2 个符号； 6424比特； RS(Reed Solomen)码 （续）

27、2022/7/28 信息位：n-（n-k） 1569个符号； 9436比特； 码长：n15个符号15460比特； 该码应为：（15,9）RS码 或（154，94） （60,36）二进制码 RS(Reed Solomen)码 （续）2022/7/28BCH码的定义及构造定义：设 为 的本原元， 为正整数， 是以 中 个相邻元素 ，其中 为根的最低次二元多项式，则以 为生成多项式的循环码称为二元本原BCH码。 2022/7/28定理：本原BCH码的最小距离 设 为由 生成的BCH码的任意多项式 由于 是 的根，而 是 的倍式，则2022/7/28上式可以写成矩阵形式 则校验矩阵为 2022/7/2

28、8例：利用本原多项式 做出 元素映射表。表中 2022/7/282022/7/282022/7/28BCH码的译码Berlekamp迭代算法设发送码向量为接收向量为信道错误图样为则：2022/7/28又设码的纠错能力为 ，信道产生的实际错误个数 ，因而在 中只有 项不为0。假定这 项为 ，其它项均为0，则有式中 称为错误位置数，而 为错误位置， 相应位置上的错误值。2022/7/28译码的任务就是从接收向量 求出错误位置数 和相应的错误值 ，再从 中减去 ，就得到了码字 的估计 ，从而完成了译码。采用一般的伴随式译码算法电路非常复杂，1966年Berlekamp提出了求差错位置的迭代算法，经过

29、不断改进与完善，形成了完整译码方法。2022/7/28BCH码译码算法的主要步骤如下：1、根据接收向量 ，计算伴随式 ；2、用Berlekamp算法从 求出差错定位多项式 ；3、用Chien搜索法求 的根，其倒数为差错位置数；4、计算错误值(二元BCH码不需要这一步)5、接收多项式减差错多项式，完成纠错。2022/7/281、由接收多项式计算伴随式纠 个错误的BCH码的校验矩阵为接收矢量的伴随式为2022/7/28因而，伴随式的各分量 为2022/7/282、用Berlekamp算法由伴随式求差错定位多项式由下述两式可得其中，2022/7/28将方程展开可得2022/7/28任何纠错的方法都是

30、解上述方程组，以求得错误位置数和错误值。该方程组一般有多组解，每组解产生不同的错误图样。如果实际错误图样可纠正，即 ，则含最少错误数目的图样才是方程组的正确解，即含最少错误数目的错误图样是信道产生的错误图样。2022/7/28直接求解非线性方程组是非常困难的。若设法使求 和 分开求解，可将非线性方程化为线性方程。为此，按照码的纠错能力 定义一个错误位置多项式式中2022/7/28由式可知， 的根是错误位置数的倒数，因此2022/7/28将 代入上式可得上式两边乘以 得两边再乘以 ，并对 求和得2022/7/28利用伴随式展开式，可以将上式写成2022/7/28上式可以展开为方程组上述方程组当实

31、际错误个数 ，该方程组的系数行列式奇异，这时需要进行降阶处理。2022/7/28Berlekamp迭代算法当编码的纠错能力 较大时，采用一般的消元等方法解上述方程组非常繁复。1966年Berlekamp提出的迭代算法，解决了BCH码的译码关键，从而将BCH码推向实用阶段。Berlekamp迭代算法由初始值，经过 次迭代，最后求得错误位置多项式。在迭代过程中，第 次迭代求得的错误位置多项式用 表示2022/7/28其中 为 的次数；另外 表示一个偏差，则迭代过程为：假设已经迭代完第 次，求得先计算 ，然后进行第 次迭代。2022/7/28若 ，则若 ，则式中 是第 次迭代之前的某次迭代次数，满足

32、 ，且 为最大值。2022/7/28迭代初始值：由于每次迭代都涉及前面两次迭代，为使迭代次数从1开始，把初始次数定为-1和0。2022/7/28可将迭代过程表示为填写如下表格：2022/7/28最后一行中所求得的 就是所要求的 ，如果它的次数大于 ，则有 个以上的错误，一般不可能找出它们的位置。 2022/7/283、求错误定位多项式的倒数根，确定错误位置根据错误位置多项式的定义，错误位置数是 的根的倒数。可以用试探法求根，即将 代入 ，便可求出 的根。用试探法求错误位置的代数运算比较繁琐，Chien从BCH码的循环特性出发，采用搜索检验错误位置的方法求根，称为钱搜索。2022/7/28设接收

33、向量为先译最前的最高阶位，然后逐位译码。为了译 ，译码器试验 是否为错误位置数，这就等于试验是否为的根，即或2022/7/28式中 为实际错误个数。因此，把译码器做成求 之和；若和为-1，则 是错误位置数， 是错误数字；否则 便是正确数字。一般，为了译译码器计算 ，并检验下列和式 如果结果是-1，则 是 的根， 是错误数字；否则 是正确数字。2022/7/284、计算错误值对于二元码，错误值为1，因此知道了错误位置就确定了错误值，这一步就不需要了。但对于q元码，错误值是GF(q)中的非0元，在求出错误位置后，还需要计算出错误值。在求出伴随式分量 和错误位置数 后，校验方程组可以写为：2022/

34、7/28求解上述线性方程组，即可得到错误值。但这样做不太方便，因为必须在全部解出 后，才能求解方程组，影响译码速度。2022/7/28由多项式 的根与系数的关系，可以从 的系数和伴随式分量 确定 ， 因而使计算简化。假设实际发生的错误数为 ，这时其中 。另外定义函数 2022/7/28当 时， ，由此可得式中 为 展开式的系数，且由于比较 和 的系数可得到2022/7/28比较上式两边同次项的系数得到或2022/7/28为了导出求错误值 的表示式，做函数改变求和次序得到2022/7/28式中 表示 在 时的值，只有当 时， ， 为其它值时全为0。所以前式可以化为 由此可得：2022/7/28根

35、据上述递推公式求解 比直接解方程组简单，前者的计算量为 ，后者的计算量为 。例 设 上的(7,3)RS码的接收码字为 ，求发送码向量。解：做 的元素表三次本原多项式 ，令 为其根，则2022/7/28那么 。设码的纠错能力为 ，2022/7/28译码步骤如下：1、计算伴随式2、求错误位置多项式2022/7/28迭代过程为填写下列表格所以。2022/7/283、计算错误位置数将 分别代入 ，求得是 的根，得错误位置为 。所以接收符号 是错误的。4、计算错误值2022/7/28代入迭代公式可得得错误图样为5、计算发送码向量所以，判决发送码字为0向量。2022/7/28线性分组码软判决译码算法举例C

36、hase算法信道编码的译码算法可以分为两大类：1、硬判决译码算法；2、软判决译码算法。前述介绍的代数译码算法都属于硬判决译码算法，只利用了信道输出的硬判决信息，而没有利用软判决信息。因此一般而言，只能纠正 个错误。2022/7/281972年Chase提出的线性分组码软判决译码算法，其纠错能力为 ，则与代数译码器相比，可获得3dB的编码增益。Chase算法的几何解释：2022/7/281. Locate the position in the codeword having the smallest likelihood or reliability.2. Let denote the set

37、 of vectors over with at most nonzero symbols 3. Perform algebraic decoding for all vectors4. For each successful decoding, compute the codeword likelihood, or metric, and decide in favor of the best.Chase Algorithm II2022/7/282022/7/28 卷积码是非分组码，它与分组码的主要差别是有记忆编码，即在任意时段，编码器的个输出不仅于此时段的个输入有关，而且还与存贮其中的前

38、个输入有关，故一段可表示为（，）码典型的卷积码一般选和（）较小，但值较大（10左右），以获取高性能 卷积码是1955年Elias 最早提出； 1957年Wozencraft提出了序列的译码法; 1963年，Massey 提出比较实用的门限译码法； 1967年，Viterbi提出最大似然的Viterbi译码法 卷积码 2022/7/28 卷积码的编码 卷积码 （续） 卷积码编码器是由一个有k个输入端口,n个输出端且具有m节移位寄存器所构成的有限状态有记忆系统,通常也称它为时序网络。 2022/7/28描述卷积码的方法很多，它大致可划分为两大类 卷积码 （续）2022/7/28 具体例子 下列图形

39、给出一个（2,1,3）卷积码编码器结构： 卷积码 （续） 若输出信息序列为： 2022/7/28 卷积码 （续） 对应输出两码组为： 对应的编码方程为： 其中“*”表示卷积运算，故卷积码因此而得名。而 表示编码的两个脉冲冲击响应。一般情况下， 最后可求得 2022/7/28 卷积码 （续） 若： 则有 至于离散卷积应在信号与系统中学过，不了解者可参见书中有关介绍。 2022/7/28 卷积码 （续）下面介绍解析法中的生成矩阵法： 若将冲击响应看成 生成序列，则将该生成序列 进行交织，可构成如下生成矩阵： G= 则前面的编码方程可改写为下列矩阵形式： 若输出信息序列为一半无限序列： 则上述生成矩

40、阵就是一个半无限的矩阵。 2022/7/28 卷积码 （续） 例：若 则有： 它与卷积运算结果完全一致。2022/7/28 卷积码 （续）下面介绍解析法中的码多项式法: 2022/7/28 卷积码 （续）则有: 2022/7/28 它亦与前面两种方法所求得的结果完全一致.再举两个例子 若给出一个二元(3,2,1)卷积码编码器如下: 卷积码 （续） 它是由k=2两个输入端，n=3三个输出端，m=1一节一位寄存器构成的编码器。 2022/7/28 卷积码 （续）若输入 ，则它可分两路并行由上述编码器结构图可求出生成序列如下： 2022/7/28 卷积码 （续）则 2022/7/28 卷积码 （续）

41、再给出一个（2，1，2）卷积码的例子。 若已知码的生成多项式为：g1(x)=1+x+x2 g2(x)=1+x2 输出信息为: u(x)=1+x2+x3+x4 试求1)卷积码编码器的结构图 2)输出码组c=? 解：由生成多项式可给出卷积码编码器结构如下： 2022/7/28且 C1(x)=(1+x2+x3+x4)(1+x+x2) =1+x2+x3+x4+x+x3+x4+x5+x2+x4+x5+x6 =1+x+x4+x6C2(x)=(1+x2+x3+x4)(1+x2) =1+x2+x3+x4+x2+x4+x5+x6 =1+x3+x5+x6C1(x)=1+x+x4+x6 C1=(1100101)C2

42、(x)=1+x+x4+x6 C2=(1001011)C=(11100001100111) 卷积码 （续）2022/7/28 卷积码 （续）下面讨论图形表示法，首先从状态图入手： 对于（2,1,2）卷积码：k=1，n=2，m=3，其总状态数为2km =21x2=22=4个，即a=00，b=10，c=01，d=11。每状态可能输入和输出有2k =21=2个，用0和1表示。 若输入序列为u=(1011100)，其状态图可以按以下步骤画出：对照（2,1,2）编码器结构图 1)首先，移位寄存器复0，其状态为00 2)输入u0=1，状态改为10，输出c01 1 0 0=1， c02=1 0=1，c0=（1

43、1）； 3)输入u1=0,状态改为01,输出c11=1,c12=0,求得c1=（10）； 2022/7/28 4)输入u2=1,状态改为10，输出c21=0，c22=0,求得c2=（00）； 5)输入u3=1,状态改为11，输出c31=0，c32=1，求得c3=（01）； 6)输入u4=1,状态仍为11，输出c41=1，c42=0，求得c4=（10）； 7)输入u5=0,状态改为01，输出c51=0，c52=1，求得c5=（01）； 8)输入u6=0,状态改为00,输出c61=1,c62=1，求得c6=(11)； 9)输入u7=0,状态仍为00，输出c71=0，c72=0，求得c7=（00）；

44、按以上步骤可画出如下状态图: 卷积码 （续）2022/7/28 再讨论树图结构:它是由状态图展开成的.即按输入信息序列u的输入顺序按时间l=0,1,2,展开,并展示所有可能的输入,输出情况如下: 卷积码 （续）2022/7/282022/7/28 由图可见，以初始状态s0=a=00为树根（l=0）,若节点级数用l表示，每个节点分为两个分支：0分支向上，1分支向下，即可求得l=0,1,27不断延伸的树状结构。它是按上述状态图按照l值展开的。 对特殊的输入信息序列u=(1011100)相对应的输出码组c=(11 10 00 01 10 01 11)图中我们用红线表示，且它与前面状态中用红线表示的结

45、果完全一致。 树图最大特点是按时间顺序展开的（即l=0,1,2）且能将所有时序状态表示为不相重合的路径，但是它也存在很大的缺点，结构太复杂，结构重复性太多。 卷积码 （续）2022/7/28最后讨论格图（又称篱笆图） 格图的最大特点是保持了树图的时序展开性，同时又克服了树图中太复杂的缺点，它将树图中产生的重复状态合并起来，形成格状结构如下： 卷积码 （续）2022/7/28 卷积码 （续）2022/7/28编码器举例2022/7/28编码器状态图2022/7/28Trellis图2022/7/28格图在Viterbi 译码中特别有用。 将树图转化为格图是很方便的。在树图中，当l= m+1 =

46、3 时， 状态 a,b,c,d呈现重复，如果将重复状态，折合起来加以合并，就可以得到纵深宽度（有称高度）为2km =21*2 =22=4的格状图。图中实线表示输入为“0”时所走的分支，虚线则表示输入为“1”时所走的分支。 由于格图既能体现时序关系，又能较简洁的表示状态结构，所以它是卷积码的一种简洁的表达形式。 卷积码 （续）2022/7/28 图中粗黑线是表示输出 u=(1011100) 时其对应编码为c=(11100001100111)，这一结果与前面状态图方式，树图方式所得结果完全一致。 不同的信息序列在树图上所对应路径完全不重合，但是在格图上则有可能有部分重合，这样两个不同输入序列，只需

47、计算格图中不相重合部分即可，所以在译码时利用格图更加方便。 卷积码 （续）2022/7/28 卷积码的译码可分为两大类型:代数译码与概率译码.属于代数译码的有Massey1963年提出的门限(或称为大数逻辑)译码;属于概率译码的有1957年Wozencraft提出的序列译码和1967年Viterbi提出的最大似然译码.后来人们就成它为Viterbi译码.在分组码中,我们重点介绍了代数译码,这里只重点介绍Viterbi译码. 卷积码的译码2022/7/28卷积码的译码方法代数译码：根据卷积码的本身编码结构进行译码，译码时不考虑信道的统计特性 概率译码：这种译码在计算时要考虑信道的统计特性门限译码

48、序贯译码维特比译码（最佳译码，最大似然译码）2022/7/28最大后验概率（MAP）译码2022/7/28最大似然（ML）译码若发送码字等概出现，MAP等价于ML2022/7/28最大似然（ML）译码对于无记忆信道称上式中的取对数部分为对数似然函数，简称似然函数（或度量值）2022/7/28编码信道硬输出：解调器将信号硬判决为0或1软输出：输出模拟量或经多电平量化的值2022/7/28举例（2PSK）V1(t)=s(t)+n(t)是软输出，或对其进行Q=2m2的多电平量化也是软输出V2(t) 是硬输出，对V1(t)进行了硬判决2022/7/28维特比译码硬判决译码：对应于解调器的硬输出软判决译

49、码：对应于解调器的软输出2022/7/28维特比硬判决译码对于二进制对称信道（BSC）2022/7/28维特比硬判决译码似然函数译码准则（因为P5m时，性能已经非常接近最大似然译码2022/7/28维特比截短译码（优点）时延降低：由n降为L存储量减小：译码序列存储量由n2km减为L2km2022/7/28维特比软判决译码（直接输出：2PSK）直接以V1(l)作为软输出yl其中cl =0,12022/7/28维特比软判决译码（直接输出：2PSK）求最大似然函数等价于求最小欧氏距离若去掉公有项，则2022/7/28维特比软判决译码（多电平量化）以V1(l)经多电平量化后的值作为软输出yl2PSK：

50、将 作为度量值，或将其加上一个常数使之恒为非负2022/7/28维特比软判决译码（多电平量化举例）c=(111,000,001,001,111,001,111,110)y=(101,100,001,011,110,110,111,110)2022/7/28维特比软判决译码（总结）解调直接输出可以看作是多电平量化的一种译码过程与硬判决译码一样，唯一的区别是度量值不同也具有汇聚特性，可以使用维特比截短译码性能优于硬判决译码，增益有1.52.0dB3比特量化即基本足够2022/7/28卷积码的距离特性码的距离特性与纠错能力有密切关系分组码：最小距离dmin卷积码最小距离dmin ：长度为nK的编码后

51、序列之间的最小汉明距离（用于门限译码，不讨论）自由距离dfree：任意长度的编码后序列的最小汉明距离（用于维特比译码）分组码与卷积码的区别：卷积码没有固定的长度的码字2022/7/28卷积码的距离特性由卷积码的编码器结构，可知卷积码具有线性性质这样，卷积码的码序列之间的自由距离就等于非全零码序列的最小码重2022/7/28卷积码的距离特性（自由距离dfree）求自由距离dfree可以转化为求任意长非全零码序列的最小码重进一步转化：由于一条编码路径的码重在与全0路径汇聚以后不再增加（若在分离码重继续增加，显然不是最小码重），所以求dfree就是找到从全零状态出发后重新汇聚到全零状态的编码路径的最

52、小码重求法：格图法（图）2022/7/28卷积码的距离特性(n,k,K)卷积码的构造方法有多种，通过求生成函数可以求得它们的自由距离（解析方法）随着k，K的增大，状态数目指数增加，求生成函数变得越来越复杂好码的寻找：通过计算机搜索2022/7/28卷积码的距离特性Heller给出的编码效率为1/n的卷积码（即(n,1,K)卷积码）的dfree的上界在上式的基础上，Daut等人给出了编码效率为k/n的卷积码的dfree的修正上界，以及搜索的相应号码的列表2022/7/28引言 级联码是由短码构造长码的一种有效的方法,它是由Forney首先提出. 级联码可用于纠正混合差错.即既有独立随机差错又有突

53、发差错,且纠错能力很强. 级联码是由内外两个短码构成一个长码,内码可设计成一般复杂度以纠正随机独立差错为主的纠错码,外码可设计为较复杂,且纠错能力较强,即可纠正内码不能纠正的随机独立差错和部分突发差错的码. 原则上,无论是内码还是外码,均可采用分组码和卷积码,但目前才用最多的是内码为卷即码,外码是RS分组码.级联编码2022/7/28基本原理 它由两个短码即内码与外码串接而成:即(n,k)=n1 n2,k1k2=(n1 k1)(n2 k2) 称(n1 k1)为内码, (n2 k2)为外码.因为一组k为信息可分解为k2个字节.而每个字节中有k1个信息位, (n1 k1)可纠字节内独立随机差错,一

54、般由卷积码构成,称为内码; (n2 k2)可纠正余下的差错以及字节间的突发差错.一般由纠错能力强的RS码构成,称为外码级联编码（续）2022/7/28基本方框图级联编码（续）若(n1 k1) 最小距离为d1 (n2 k2) 最小距离为d2,串接后级联码最小距离dd1d2,级联码结构是由内外码串接而成又称为串行级联码,其设备仅是两者的制机组合,它要比采用一个长码时所需的设备简单得多.2022/7/28 级联码标准 最早采用级联码的是八十年代美国宇航局NASA将它用于深空遥测数据的纠错. 1987年NASA制定了级联码深空遥测标准CCSDS. 典型标准级联码系统框图如下:级联编码（续）2022/7

55、/28 1984年，NASA采用上述的典型标准为：内码为(2,1,7)卷积码,外码为(255,223)RS码.而交织器深度大约为28个外码块,其性能很优异,当EbN0=2.53dB.误码率达Pb10-6. 级联码的性能 下面给出在Pb10-6条件下(Pb为误比特率) 一些级联码的性能: 级联编码（续）2022/7/28内码外码Pb=10-6条件下Eb/N0 (dB)较标准（基准）系统功率增益(dB)(4,1,5)(255,223)0.911.62(5,1,14)(1023,927)0.571.96(5,1,15)(1023,959)0.502.03(6,1,14)(1023,959)0.472

56、.06(6,1,15)(1023,959)0.422.11(5,1,13)(255,229)0.911.62(5,1,14)(255,231)0.791.74(6,1,14)(255,233)0.631.90级联编码（续）2022/7/28级联编码（续）2022/7/28引言 l交织码主要用于有记忆的信道，特别是无线移动信道； l交织码的基本思路与前面介绍的纠错码思路不同，纠错码是为了适应信道，而交织码则是为了改造信道。即将一个有记忆的突发信道经过交织、去交织变换将信道改造成独立无记忆信道。然后再采用纠正独立随机差错的纠错码充分发挥其纠错功能。基本原理： 交织编码 图1分组交织系统框图2022

57、/7/28 1）若待发送的一组信息为： X= (x1 x2 x3 x24 x25)2）交织存贮器为一个行列交织矩阵，它按列写入，按行读出：交织编码 （续） 3）交织器输出并送入突发信道的信息为： X= (x1 x6 x11 x16 x21 x2 x7 x12 x17 x22 x5 x10 x15 x20 x25 )2022/7/28 4）假设突发信道产生了两个突发差错，第一个产生于x1至x21连错5位，第二个突发产生于x13至x4连错4位 5）突发信道输出端信息为X，它可表示为： 6）在接收端，进入去交织器后，送入另一存贮器，它也是一个行列交织矩阵，但是它是按行写入按列读出： 交织编码 （续）2022/7/28 7）去交织存贮器的输出为X ： 8）由上面分析可见，经过交织矩阵与较之矩阵的变