信息论基础第七章信道编码

信息论基础第七章信道编码第一页，共一百二十四页，2022年，8月28日2023/1/18

本章的基本内容

•信道编码的基本概念；

•线性分组码；

•循环码、BCH码；

•卷积码与Viterbi译码；

•纠突发差错的Fire码；

•交织码；

•级连码；

•实际信道编码的应用。信道编码

第二页，共一百二十四页，2022年，8月28日2023/1/18

从编码的角度看信道的分类按照差错类型大致可分为三类：

1）独立差错信道：噪声独立随机的影响每个码元，白噪声信道属于这类信道。差错独立随机出现；

2）突发差错信道：差错成片，成串出现，衰落信道、码间干扰、脉冲干扰信道属于这类；

3）混合差错信道：差错既有随机独立的，也有成片，成串出现的，实际的移动信道属于此类；信道编码的基本概念第三页，共一百二十四页，2022年，8月28日2023/1/18

信道编码的分类从功能上看可分为检错（发现错误）码与纠错（不仅发现而且能自动纠正）码两类，本章中仅讨论纠错编码。纠错码可根据不同信道类型相应划分为

———以纠独立随机差错为主的信道编码；

———以纠突发差错为主的信道编码；

———纠混合差错的信道编码。信道编码的基本概念（续）第四页，共一百二十四页，2022年，8月28日2023/1/18

信道编码的任务：构造出以最小多余度的代价换取最大抗干扰性的“好“码；下面，首先从直观概念出发，寻求“好“码性能的两个极端情况：高可靠性，低有效性的重复码；高有效性，低可靠性的奇偶校验码。

重复码

—不重复时:

信道编码的基本概念（续）收端第五页，共一百二十四页，2022年，8月28日2023/1/18

结论：不重复，方法简单，但没有任何抗干扰能力，既不能发现，更不能纠正错误。

—重复一次：

结论：重发一次，效率降低一倍.可以换取在传输过程中允许产生一个错误（收端能发现它），但不能纠正。信道编码的基本概念（续）发端收端能发现一个错第六页，共一百二十四页，2022年，8月28日2023/1/18—重复二次：结论：重发二次，效率降低二倍，但换取了可纠正一个差错或发现两个差错的性能改善。信道编码的基本概念（续）发端收端能纠正一个错或发现两个错第七页，共一百二十四页，2022年，8月28日2023/1/18

奇偶检验码其编码规则为：

其中结论：这类码效率高，但可靠性较差，仅具有部分（奇或偶）检错功能。能否找到可靠性既高效率又不低的信道编码，这就是本章中要讨论的核心问题。信道编码的基本概念（续）例：第八页，共一百二十四页，2022年，8月28日2023/1/18

线性分组码从信道编码的构造看，往往可以划分为：线性分组码是其中最为常用的一类它可记为(n，k)码，即每k位信息为一组进行编码，可编成n位码长的信道编码，其中监督（校验）位为n-k位，编码效率为。线性分组码中，通常采用码重与码距的概念。信道编码的基本概念（续）第九页，共一百二十四页，2022年，8月28日2023/1/18

线性分组码中的码重是指码组C中所含“1”的数目，比如在上述(3，1)重复码中：

线性分组码中的码距是指两个码组Ci与Cj中相应码元不相同的数目。比如在上述重复码中：（1，1）重复码：，

信道编码的基本概念（续）第十页，共一百二十四页，2022年，8月28日2023/1/18

（2，1）重复码：，（3，1）重复码：，纠正随机独立差错能力与码距之间的关系：

——若要发现e个独立差错，则要求最小码距；

——若要纠正t个独立差错，则要求最小码距；

——若要求发现e个又纠正t个独立差错，则；信道编码的基本概念（续）第十一页，共一百二十四页，2022年，8月28日2023/1/18

在线性码中

——(n，1)重复码，随着n的增大，可靠性不断提高，但有效性却在下降：；

——(n，n-1)奇偶监督码，随着n的增大，其效率，很高，但是可靠性差，仅能发现奇（偶）数个独立差错；

——我们要寻找的是高可靠性即差错率，且编码效率的理想信道编码，这类信道编码理论上编码定理已指出是存在的，但是实际上构造起来很困难，目前已找到的绝大部分码是当时，亦趋于0，仅有少数比如turbo码，两者性能都比较好。信道编码的基本概念（续）第十二页，共一百二十四页，2022年，8月28日2023/1/18

目前大多数信道编码性能却不很理想，因此目前信道编码的主要目标是以可靠性为主，即在寻求抗干扰强的码的基础上，寻求适当的有效性，寻求和构造最小距离比较大的码。有关线性分组码的n种等效研究方法

所谓有限域，是指有限个元素的集合，可以进行按规定的代数四则运算，其结果仍属于集合中的有限元素。信道编码的基本概念（续）第十三页，共一百二十四页，2022年，8月28日2023/1/18

在信道编码中，可以将码组（字）中的每个码元0与1的产生、运算规律，引用最简单的二元有限域{0，1}来描述，称它为二元Galois域，记为，并规定其加法与乘法运算⊙如下：显然中，对0、1的、⊙运算是自封闭的，并可以进一步验证这两种运算满足域运算的全部运算规则，故称它为二元有限域。在一个码组中若含有n位码元，记为，其中每个码元取值为0、1，遵从GF(2)运算规律。则可将码元的GF(2)拓广至码组的上，即有：信道编码的基本概念（续）第十四页，共一百二十四页，2022年，8月28日2023/1/18

其中，

显然对于码组它应该遵从有限扩域的运算规则，也可看作是由扩展成的n维的矢量空间。这类引用有限域有限扩域（矢量空间）的方法，在信道编码的理论研究中非常有用，即可引用有限域理论分析研究信道编码的性质，寻找性能好的信道编码等等。

信道编码的基本概念（续）第十五页，共一百二十四页，2022年，8月28日2023/1/18

在信道编码的工程构造上往往引用另一种等效的概念，即模多项式分析方法更为方便。

信道编码的基本概念（续）一个n元码组（字）

一个n元码多项式

一一对应同构映射第十六页，共一百二十四页，2022年，8月28日2023/1/18

线性分组码中的线性是指编码规律即码元之间的约束关系是线性的，而分组则是对编码方法而言，即编码是将每k个信息为分为一组进行独立处理——编码，编成长度为n位（n>k）的二进制码组。

线性分组码

第十七页，共一百二十四页，2022年，8月28日2023/1/18

按数学上更为一般的定义可表示为：，其中n>k，若f进一步满足下列线性关系：其中：

由上述定义，可见线性分组码f可看成：

线性分组码（续）

——线性空间的变换——有限域空间的变换第十八页，共一百二十四页，2022年，8月28日2023/1/18

线性分组码是分组码中最重要最有实用价值的一个子类，下面将从具体例子入手，阐明它的一些基本概念。

例：以（7，3）二元线性分组码为例，其中：，，，这时输入编码器的信息分成三个一组，即，它可按下列线性方程组编码：

线性分组码（续）

第十九页，共一百二十四页，2022年，8月28日2023/1/18

写成矩阵形式

称G为生成矩阵，若即能分解出单位方阵为子阵，且I的位置可任意，则称为系统码（或组织码）若将上述监督线性方程组改写为:线性分组码（续）

第二十页，共一百二十四页，2022年，8月28日2023/1/18即线性分组码（续）

第二十一页，共一百二十四页，2022年，8月28日2023/1/18再改变为矩阵形式:

即H·CT=OT(P┆I)·CT=OT

称H为监督(校验)矩阵，若H=(P┆I)，即能分解出单位方阵为子阵，且I的位置可任意，则称C为系统（组织）码。线性分组码（续）

第二十二页，共一百二十四页，2022年，8月28日2023/1/18

生成矩阵G一般用于发端编码，而监督矩阵H则一般用于接收端的译码。由于生成矩阵G中的每一行及其线性组合都是线性（n,k）码的码组（字），因此有：

H·GT=OT或G·HT=O

它说明矩阵G与H互为零化空间。由线性空间理论，一个n维的线性空间Vn可以分解为一对互为对偶的正交子空间Vk与Vn-k。即：线性分组码（续）

互为对偶码可构成(7,3)线性分组码可构成(7,4)线性分组码第二十三页，共一百二十四页，2022年，8月28日2023/1/18

结合上面n=7的例子,则有

显然有：(7,3)码的生成矩阵G3就是(7,4)码监督矩阵H’3

，(7,3)码的监督矩阵H4就是(7,4)码的生成矩阵G’4采用系统（组织）码来描述生成矩阵G与监督矩阵H，仅是其中的一种。在很多情况下是采用非系统码的描述方式，那么两者之间有没有什么实质上的差别？线性分组码（续）

可构成(n,k)线性分组码可构成(n,n-k)线性分组码互为对偶码第二十四页，共一百二十四页，2022年，8月28日2023/1/18由线性代数理论，任何一个非系统的生成矩阵G均可以通过矩阵的初等变换得到相应的系统码的生成矩阵G。因此，我们可以得到如下结论：任何一个线性分组（n,k）码，均可找到一个等价的系统码，而且还可以进一步证明只要在码率R和码长n相同的条件下，最优的系统码与最优的线性分组码具有相同的错误概率。线性分组码特别是系统码的编码器极其简单，其具体结构可参见书上有关章节，这里就不再赘述。线性分组码（续）

第二十五页，共一百二十四页，2022年，8月28日2023/1/18线性分组码（续）

线性分组码的译码，特别是系统码也比较简单，在数据通信中，最优译码即为最小误码准则下的译码，它在信源等概率即p0=p1时，可等效为最大似然准则，当信道为BSC时，它又可等效为最小汉明距离准则，关于准则问题将在后面讨论卷积码的译码时进一步详细讨论。译码时，在接收端收到的信号为：

且

其中表示发送的码组（字）

表示传输中的差错。

第二十六页，共一百二十四页，2022年，8月28日2023/1/18

由监督方程：即只要在传输中不产生差错，即则必满足上式。实际上传输中一定产生差错，这时，则有且有我们称s为伴随子（校正子），这是由于s仅与e有关，而与码组(字)c无关。对于一个(n,k)线性分组码，H矩阵是一个(n-k)行n列的矩阵，所以s为一个（n-k）维的矢量。

它仅可以给出（n-k）个独立方程组，监督(n-k)位的差错。然而在信线性分组码（续）

第二十七页，共一百二十四页，2022年，8月28日2023/1/18线性分组码（续）

道中传输的差错e是一个n维矢量，有可能产生n位差错。因此仅上述伴随子方程不能求解n位差错，由于2n=2n-k×2k，半随子方程仅能解出2n-k个差错图样，也可以说有2k个差错图样共用一个伴随子方程，真正的差错是2n-k中的某一个。在二进制对称信道BSC条件下，最可能出现的错误图样是接收码组中汉明重量最小的码组，即非0个数最小的码组。下面以(7,4)线性分组码为例，不过这里的(7,4)码不是直接与(7,3)码互为对偶码，而是将其对偶码再经过矩阵初等变换后的(7,4)码，监督矩阵和生成矩阵分别如下：第二十八页，共一百二十四页，2022年，8月28日2023/1/18线性分组码（续）

第二十九页，共一百二十四页，2022年，8月28日2023/1/18线性分组码（续）

第三十页，共一百二十四页，2022年，8月28日2023/1/18线性分组码（续）

第三十一页，共一百二十四页，2022年，8月28日2023/1/18

按照上述规则，可以将一个（n，k）线性分组码的译码，按照伴随式的规则划分为个行矢量乘以个列矢量所构成的下列标准阵列：线性分组码（续）

第三十二页，共一百二十四页，2022年，8月28日2023/1/18

称这种译码为伴随式译码，或称为查表译码。它原则上适合于任何（n，k）线性分组码。伴随式译码步骤可归纳如下：

1）计算接收矢量的伴随式：

2）由伴随式决定相对应的陪集首

3）将译成其具体实现框图如下：线性分组码（续）

第三十三页，共一百二十四页，2022年，8月28日2023/1/18线性分组码（续）

第三十四页，共一百二十四页，2022年，8月28日2023/1/18线性分组码（续）

伴随式

陪集首00000000001001000000010010000000100100001100001000011000010011100000101010000001<表>(7,4)码的陪集首集合第三十五页，共一百二十四页，2022年，8月28日2023/1/18

对于(7,4)码，若

其具体运算和纠正差错过程可参考书上的(7,4)线性分组码译码电路图。线性分组码（续）

第三十六页，共一百二十四页，2022年，8月28日2023/1/18

循环码是线性分组码中最主要，最有适用价值的一类，它是1957年由Prange首先提出循环码第三十七页，共一百二十四页，2022年，8月28日2023/1/18

基本定义：一个（n,k）线性分组码，经任意循环移位之后，仍然是线性分组码，则称它为循环码主要特点

1）理论成熟：可利用成熟的代数结构深入探讨其性质；

2）实现简单；可利用循环移位特性在工程上进行编，译码；

3）循环码的描述方式有很多，但在工程上可采用最有用的多项式的描述方法。一一对应：

n元码组(字)n阶(含0阶)码多项式

有限域多项式域模运算码组模2运算多项式乘积运算循环码（续）第三十八页，共一百二十四页，2022年，8月28日2023/1/18在多项式描述中，我们可以将“同余”（模）运算推广到多项式中。即循环码（续）例：第三十九页，共一百二十四页，2022年，8月28日2023/1/18则有下列多项式除法:循环码（续）第四十页，共一百二十四页，2022年，8月28日2023/1/18下面给出(7,3)码循环移位特性：（见下页）循环码（续）第四十一页，共一百二十四页，2022年，8月28日2023/1/18循环码（续）码组

码多项式0

1011100

1+x2+x3+x41

0101110

x(1+x2+x3+x4)2

0010111

x2(1+x2+x3+x4)3

1001011

x3(1+x2+x3+x4)=1+x3+x5+x6,mod(1+x7)4

1100101

x4(1+x2+x3+x4)=1+x

+x4+x6,mod(1+x7)5

1110010

x5(1+x2+x3+x4)=1+x

+x2+x5,mod(1+x7)6

0111001

x6(1+x2+x3+x4)=x+x2+x3+x6,mod(1+x7)7

1011100

x7(1+x2+x3+x4)=1+x2+x3+x4,mod(1+x7)x0x1x2x3x4x5x6移位次数第四十二页，共一百二十四页，2022年，8月28日2023/1/18

可见推移7位后出现周期性循环特性.

下面进一步研究(7,3)循环码生成矩阵表达式:循环码（续）第四十三页，共一百二十四页，2022年，8月28日2023/1/18

可见,在循环码中,其生成矩阵结构更加简化,它是由生成多项式g(x)循环推移构成.书中给出k位信息位的一般化表达式,以及在一般情况下,当为系统码时循环码的生成矩阵表达式.有兴趣者可进一步仔细阅读.

在线性分组码中有:

对应于循环码中有:

例:仍以(7,3)循环码为例:循环码（续）第四十四页，共一百二十四页，2022年，8月28日2023/1/18(7,3)码生成多项式的阶次为:n-k=7-3=4,故有或者由线性分组码的对偶性,可求得对应(7,4)码的生成多项式与监督多项式如下:

或循环码（续）第四十五页，共一百二十四页，2022年，8月28日2023/1/18循环码的编码例:若输入信息码元为:u=(1001)即,下面将简介最简单的系统循环码的编译码.仍以(7,4)系统循环码为例:

我们所选的多项式,由系统码生成规则:

即：循环码（续）第四十六页，共一百二十四页，2022年，8月28日2023/1/18循环码（续）第四十七页，共一百二十四页，2022年，8月28日2023/1/18其中最右边的4位是信息元，这样编码器结构图如下：循环码（续）输入信息码字输出门D0D1D2第四十八页，共一百二十四页，2022年，8月28日2023/1/18循环码（续）输出码字为:D0D1D2D2D1D01第四十九页，共一百二十四页，2022年，8月28日2023/1/18上述编码过程如下：三级寄码器的初态为000，信息元组以(即1001）分两路,一路直接输出，另一路送入g(x)除法电路；经四次移位后，信息元组1001全部输出，另一路也全部送入g(x)除法电路并完成除法电路运算。这时寄存器中的状态为余式r(x)即监督元

输出开关由1倒向2，并经三次移位，将监督元跟在信息元后依次输出得到

c==(0111001)。循环码（续）第五十页，共一百二十四页，2022年，8月28日2023/1/18（7,4）循环码译码过程如下：若即y=(1111001)

将其输入译码器，其译码过程如下列表格所示：循环码（续）第五十一页，共一百二十四页，2022年，8月28日2023/1/18循环码（续）i次移位后伴随矢量错误图样

伴随式

1+x+x2

伴随矢量移位次数

e61+x2

101

0

101

e5

111

1

101

e4x+x2011

2

101

e31+x

110

3101

e2x2

0014101e1

x010

5

101

e01

1006101e(x)s(x)s0s1

s2is0s1

s2第五十二页，共一百二十四页，2022年，8月28日2023/1/18生成的（7,4）循环码译码器原理图循环码（续）第五十三页，共一百二十四页，2022年，8月28日2023/1/18上述译码器工作步骤如下：首先将移位寄存器复0，清洗到初始状态；输入y分两路进入译码器，一路进入缓存器，另一路经门1进入伴随式计算电路，分别计算s0s1s2；在输出y的同时，s0s1s2依次循环移位，无差错时，错误检测电路无输出，最后输出码元与接收的y中码元一致；有错误时，错误检测电路输出为1，它正好与y中的错误位在模2加中相遇，并自动予以纠正。这一循环译码器与前面线性分组（7，4）码的译码器比较是实现结构简化了，在线性分组码中，对每一种伴随式要设计一个相对应的伴随式计算电路，而在循环（7，4）码中，可利用码的循环特性共用一套设备。循环码（续）第五十四页，共一百二十四页，2022年，8月28日2023/1/18

循环码特别适合于检测错误，这是由于它具有很强的检测错误的能力，同时实现起来也较简单；CRC一般能检测如下错误：

·突发长度<

n-k+1的突发错误；

·大部分长度=n-k+1的突发错误，其中不可检测错误仅占2-(

n-k-1)；

·大部分长度>n-k+1的突发错误，其中不可检测错误仅占2-(

n-k)；

·所有与许用码组码距≤dmin-1的错误；

·所有奇数个错误；常用的CRC码，已成为国际标准的有：

·CRC-12，其生成多项式：g(x)=1+x+x2+x3+x11+x12CRC检错码（cyclicredundancycheck）第五十五页，共一百二十四页，2022年，8月28日2023/1/18·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+x10+x11+x12+x16+x22+x23+x26+x32

其中CRC-12用于6bit字符，其余则用于8bit字符。CRC检错码（续）第五十六页，共一百二十四页，2022年，8月28日2023/1/18

BCH

码是一类最重要的循环码，它能纠正多个随机错误，它是1959-1960年由Hocquenghem，Bose与Chandari三位学者独立发现的二元线性循环码。人们将三人名字的字头BCH命名为BCH码。

BCH

码具有纠错能力强，构造方便，编、译码易于实现的一系列优点。我们这里不讨论BCH码的理论与性质，因为它要涉及更深的近世代数的群、环、域的知识；重点侧重于对BCH码的工程上的使用，即利用已知的BCH码表格，构造对应的生成多项式。若循环码生成多项式为：

g(x)=LCM[m1(x),m3(x),……m2t-1(x)]

这里t为纠错的位数，mi(x)为素多项式，LCM为求最小公倍数。BCH码第五十七页，共一百二十四页，2022年，8月28日2023/1/18

则由此生成多项式生成的循环码称为BCH码，其最小距：dmin≥d0=2t+1(d0为设计码距)，它能纠正t个随机独立差错。

BCH码的码长为n=2m―1或是n=2m―1的因子，通常称前者为本原BCH码，称后者为非本原BCH码。书中列出n≤127的本原BCH码，和部分非本原BCH码的生成多项式表与部分不可约的多项式表。例1：BCH(15，5)码。

它是一个可纠正3个随机独立差错的BCH码，即t=3;

d≥d0=2t+1=2*3+1=7;BCH码（续）第五十八页，共一百二十四页，2022年，8月28日2023/1/18

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)=LCM[m1(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

是八进制表达式**.本节中编码序列与以前相反，它是从高位向低位排列，其原因，这里引用的三个表格是从高向低排。BCH码（续）第五十九页，共一百二十四页，2022年，8月28日2023/1/18

它是一类纠错能力很强的特殊的非二进制BCH码.对于任选正整数S可构造一个相应的码长为n=qS-1的q进制BCH码,其中码元符号取自有限域GF(q),而q作为某个素数的幂.当S=1，q>2时所建立的码长n=q-1的q进制BCH码,称它为RS码.当q=2m(m>1),其码元符号取自于F(2m)的二进制RS码可用来纠正突发差错，它是最常用的RS码．

RS码的构造一个可纠正t个符号错误的RS码有如下参数：码长：n=2m-1符号，或m(2m-1)比特；信息位：k符号，或km比特；监督位：n-k=2t符号，或m(n-k)=2mt比特；

RS(ReedSolomen)码第六十页，共一百二十四页，2022年，8月28日2023/1/18

最小码距：dmin=d0=2t+1,或mdmin=m(2t+1)比特．RS码的纠错能力具有同时纠正随机与突发差错的能力．它可纠正的错误图样有：总长度为：b1=(t-1)m+1比特的单个突发；

总长度为：b2=(t-3)m+3比特的两个突发；

………

总长度为：bi=(t-2i+1)m＋2i-1比特的i个突发．

RS(ReedSolomen)码(续)第六十一页，共一百二十四页，2022年，8月28日2023/1/18

例：试构造一个能纠正三个符号错误，码长n=15，m=４的RS码．已知t=3，n=4，m=4；求得码距为：d=2t+1

=2*3+1

=7个符号

=7*4=28比特；监督位：n-k＝2t=2*3

=6个符号；

=6*4=24比特；

RS(ReedSolomen)码(续)第六十二页，共一百二十四页，2022年，8月28日2023/1/18

信息位：k=n-(n-k)

=15－6=9个符号；

=9*4＝36比特；码长：n=15个符号=15*4=60比特；该码应为：(15,9)RS码或(15*4，9*4)

=(60,36)二进制码

RS(ReedSolomen)码(续)第六十三页，共一百二十四页，2022年，8月28日2023/1/18

卷积码是非分组码，它与分组码的主要差别是有记忆编码，即在任意时段，编码器的n个输出不仅与此时段的k个输入有关，而且还与存贮其中的前m个输入有关，故卷积码一般可表示为(n，k，m)，典型的卷积码一般选n和k(n＜k)较小，但m值较大(m＜10左右)，以获取高性能．

•卷积码是1955年Elias最早提出；

•1957年Wozencraft提出了序列的译码法;

•1963年，Massey提出比较实用的门限译码法；

•1967年，Viterbi提出最大似然的Viterbi译码法

卷积码第六十四页，共一百二十四页，2022年，8月28日2023/1/18

卷积码的编码

卷积码（续）

卷积码编码器是由一个有k个输入端口,n个输出端且具有m节移位寄存器所构成的有限状态有记忆系统,通常也称它为时序网络。第六十五页，共一百二十四页，2022年，8月28日2023/1/18描述卷积码的方法很多，它大致可划分为两大类

卷积码（续）第六十六页，共一百二十四页，2022年，8月28日2023/1/18

具体例子下列图形给出一个（2,1,3）卷积码编码器结构：

卷积码（续）

若输入信息序列为：第六十七页，共一百二十四页，2022年，8月28日2023/1/18

对应输出两码组为：对应的编码方程为：其中“*”表示卷积运算，故卷积码因此而得名。而表示编码的两个脉冲冲击响应。一般情况下，最后可求得

卷积码（续）第六十八页，共一百二十四页，2022年，8月28日2023/1/18

卷积码（续）若：则有至于离散卷积应在信号与系统中学过，不了解者可参见书中有关介绍。第六十九页，共一百二十四页，2022年，8月28日2023/1/18下面介绍解析法中的生成矩阵法：若将冲击响应看成生成序列，则将该生成序列

进行交织，可构成如下生成矩阵：

则前面的编码方程可改写为下列矩阵形式：若输出信息序列为一半无限序列：则上述生成矩阵就是一个半无限的矩阵。

卷积码（续）第七十页，共一百二十四页，2022年，8月28日2023/1/18

例：若则有：

它与卷积运算结果完全一致。

卷积码（续）第七十一页，共一百二十四页，2022年，8月28日2023/1/18下面介绍解析法中的码多项式法:

卷积码（续）第七十二页，共一百二十四页，2022年，8月28日2023/1/18则有:

卷积码（续）第七十三页，共一百二十四页，2022年，8月28日2023/1/18

它亦与前面两种方法所求得的结果完全一致.再举两个例子若给出一个二元(3,2,1)卷积码编码器如下:

卷积码（续）

它是由k=2两个输入端，n=3三个输出端，m=1一节移位寄存器构成的编码器。第七十四页，共一百二十四页，2022年，8月28日2023/1/18若输入，则它可分两路并行由上述编码器结构图可求出生成序列如下：

卷积码（续）第七十五页，共一百二十四页，2022年，8月28日2023/1/18则

卷积码（续）第七十六页，共一百二十四页，2022年，8月28日2023/1/18再给出一个(2,1,2)卷积码的例子。若已知码的生成多项式为：g1(x)=1+x+x2

g2(x)=1+x2

输入信息为:u(x)=1+x2+x3+x4

试求1)卷积码编码器的结构图

2)输出码组c=?

解：由生成多项式可给出卷积码编码器结构如下：

卷积码（续）第七十七页，共一百二十四页，2022年，8月28日2023/1/18

卷积码（续）且第七十八页，共一百二十四页，2022年，8月28日2023/1/18下面讨论图形表示法，首先从状态图入手：对于(2,1,2)卷积码：k=1，n=2，m=2，其总状态数为2km=21×2=22=4个，即a=00，b=10，c=01，d=11。每状态可能输入和输出有2k=21=2个，用0和1表示。若输入序列为u=(1011100…)，其状态图可以按以下步骤画出：[对照（2,1,2）编码器结构图]1)首先，移位寄存器复0，其状态为002)输入u0=1，状态改为10，输出

3)输入u1=0,状态改为01,输出c11=1,c12=0,求得c1=（10）；

卷积码（续）第七十九页，共一百二十四页，2022年，8月28日2023/1/184)输入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)；按以上步骤可画出如下状态图:

卷积码（续）第八十页，共一百二十四页，2022年，8月28日2023/1/18

再讨论树图结构:它是由状态图展开成的.即按输入信息序列u的输入顺序按时间l=0,1,2,…展开,并展示所有可能的输入,输出情况如下:

卷积码（续）第八十一页，共一百二十四页，2022年，8月28日2023/1/18第八十二页，共一百二十四页，2022年，8月28日2023/1/18

由图可见，以初始状态s0=a=00为树根（l=0）,若节点级数用l表示，每个节点分为两个分支：0分支向上，1分支向下，即可求得l=0,1,2…7不断延伸的树状结构。它是按上述状态图按照l值展开的。对特殊的输入信息序列u=(1011100…)相对应的输出码组c=(11100001100111…)图中我们用红线表示，且它与前面状态中用红线表示的结果完全一致。树图最大特点是按时间顺序展开的（即l=0,1,2…）且能将所有时序状态表示为不相重合的路径，但是它也存在很大的缺点：结构太复杂，结构重复性太多。

卷积码（续）第八十三页，共一百二十四页，2022年，8月28日2023/1/18

最后讨论格图（又称篱笆图）格图的最大特点是保持了树图的时序展开性，同时又克服了树图中太复杂的缺点，它将树图中产生的重复状态合并起来，形成格状结构如下：

卷积码（续）第八十四页，共一百二十四页，2022年，8月28日2023/1/18

卷积码（续）第八十五页，共一百二十四页，2022年，8月28日2023/1/18格图在Viterbi译码中特别有用。将树图转化为格图是很方便的。在树图中，当l=m+1=3时，状态a,b,c,d呈现重复，如果将重复状态，折合起来加以合并，就可以得到纵深宽度（有称高度）为2km=21*2=22=4的格状图。图中实线表示输入为“0”时所走的分支，虚线则表示输入为“1”时所走的分支。由于格图既能体现时序关系，又能较简洁的表示状态结构，所以它是卷积码的一种简洁的表达形式。

卷积码（续）第八十六页，共一百二十四页，2022年，8月28日2023/1/18

图中粗红线是表示输入u=(1011100)时其对应编码为c这一结果与前面状态图方式，树图方式所得结果完全一致。不同的信息序列在树图上所对应路径完全不重合，但是在格图上则有可能有部分重合，这样两个不同输入序列，只需计算格图中不相重合部分即可，所以在译码时利用格图更加方便。

卷积码（续）第八十七页，共一百二十四页，2022年，8月28日2023/1/18

卷积码的译码可分为两大类型:代数译码与概率译码.属于代数译码的有Massey1963年提出的门限(或称为大数逻辑)译码;属于概率译码的有1957年Wozencraft提出的序列译码和1967年Viterbi提出的最大似然译码(后来人们就称它为Viterbi译码).在分组码中,我们重点介绍了代数译码,这里只重点介绍Viterbi译码.

卷积码的译码第八十八页，共一百二十四页，2022年，8月28日2023/1/18首先介绍译码准则:

在数字、数据通信中常用的准则是最小平均误码率准则.卷积码的译码（续）第八十九页，共一百二十四页，2022年，8月28日2023/1/18由Bayes公式：若发送码组（字）是等概率的，这时为常数，当已知接受码组（字）时，亦为常数，则结论：当发送码组等概率时，最小平均误码率准则与最大后验概率准则以及最大似然准则等效。对于离散无记忆信道（DMC）有：由于对数函数为单调函数，故可将其改写为对数函数形式：卷积码的译码（续）第九十页，共一百二十四页，2022年，8月28日2023/1/18我们称按上述公式进行译码的算法为最大似然译码算法，同时称为对数似然函数，有时简称为似然函数。进一步，对于二进制对称信道BSC，似然函数可以进一步改写为：

其中为与之间的汉明距离，由于且为常数，而，则有卷积码的译码（续）第九十一页，共一百二十四页，2022年，8月28日2023/1/18

结论：对于BSC最大似然译码等效于最小汉明距离译码。ΔViterbi算法的举例：在二进制对称信道BSC下卷积码译码的Viterbi算法就是建立在前面介绍的格图基础上的最小汉明距离算法，下面仍以具体例子入手来分析。·例：以最简单的(2,1,2)卷积码为例若发送的信息序列为，即L=5,

经过编码后输出的码组(字)为接收到的信号序列为：卷积码的译码（续）第九十二页，共一百二十四页，2022年，8月28日2023/1/18

在BSC下，其译码在格图上的每一步的计算结果（距离图）和累计计算结果幸存路径图如下述两个图形所示：卷积码的译码（续）a=00b=10c=01d=11l=0l=1l=2l=3l=4l=5l=6l=7状态数第九十三页，共一百二十四页，2022年，8月28日2023/1/18

结论:最后求得的最小汉明距离路径如图中粗黑线表示为:

a0b1c2b3d4d5c6a7,最小汉明距离值为2.卷积码的译码（续）l=0l=1l=2l=3l=4l=5l=6l=7a=00b=10c=01d=11第九十四页，共一百二十四页，2022年，8月28日2023/1/18Viterbi算法由上面的例子可以总结出如下规律:

维特比算法,对于DMC信道(或BSC信道),主要体现在上述格形图中寻找具有最大似然值的路径,具体是采用迭代法进行处理.即在每一步中,它将进入每一状态的所有路径的度量值进行比较,保存并度量最大度量值(或最小汉明距离值),称为幸存路径,并丢弃其他路径;

DMC(或BSC)中viterbi算法可归结为如下三步:1.从时刻l=m开始,(l<m为起始状态)计算进入每一状态的单个路径的部分度量值,并存入每一状态下的幸存路径及其度量值.2.l增加1,即l=m+1,将进入某一状态的分支度量值,与前一时段的幸存度量值相加,然后计算进入该状态的所有最大度量的路径(或最小汉明距离路径)即幸存路径及其度量,并删去所有其它路径.卷积码的译码（续）第九十五页，共一百二十四页，2022年，8月28日2023/1/183.若l<L+m=5+2=7,重复步骤2,否则停止.

上述三个步骤中,1是2的初始化,3是2的延续,关键在于第2步,它主要包括两部分,一是对每个状态进行度量和比较,并决定幸存路径,另一个是记录幸存路径与度量值.上述三步的进一步细化:1.

从l=m=2时刻开始,使网格图充满状态,将路径存储器(PM)和路径度量存储器(MM)从l=0到l=m=2进行初始化;2.

l=l+1=2+1=33.接收到新的一组数据,它代表l=l+1的分支上接收符号组;4.对每一状态:

a.进行分支度量计算;卷积码的译码（续）第九十六页，共一百二十四页，2022年，8月28日2023/1/18

b.从MM中取出第l时刻幸存路径度量值;

c.进行累加---比较---选择(ACS)基本运算,产生新的幸存路径;

d.将新的幸存路径及其度量值分别存入PM及MM中;5.如果l<L+m=5+2=7,回到步骤2,否则继续往下做;6.求MM中最大似然值对应路径,从PM中输出判决结果.

Viterbi译码实现的三种结构

1.全并行,即采用2m个ACS单元同时运算并作PM、MM操作；

2.全串行，即采用一个ACS单元进行2m次ACS与PM、MM操作；

3.时分复用方案，即部分并行，采用少于2m个ACS单元分数次完成全部2m次的ACS与相应PM、MM操作。卷积码的译码（续）第九十七页，共一百二十四页，2022年，8月28日2023/1/18卷积码的译码（续）Viterbi译码过程

输入u=(1011100)后两位为尾比特.

以(2,1,2)码为例,BSC下

c=(11,10,00,01,10,01,11)

y=(10,10,00,01,11,01,10)具体步骤如下:00汉明距离d(d’)估值1)l=01,y0=10,S0010

S11111第九十八页，共一百二十四页，2022年，8月28日2023/1/18卷积码的译码（续）第九十九页，共一百二十四页，2022年，8月28日2023/1/18卷积码的译码（续）第一百页，共一百二十四页，2022年，8月28日2023/1/18

软判决译码

为了提高译码性能可将硬判决改为软判决，即多电平判决，这是由于两电平的硬判决在强噪声时容易丢失有用信息，而采用多电平软判决后大约可改进1.5-2dB，在具体实现时，考虑到实现的复杂度，一般可取4-8电平。

软判决的依据：对最大似然比作下列线性变换：卷积码的译码（续）第一百零一页，共一百二十四页，2022年，8月28日2023/1/18其中：a为任意正整数，b为任意实数；

实例：以(2,1,2)卷积码为例，通过DMC信道采用简单的四电平软判决。

1）DMC信道转移图如下：卷积码的译码（续）第一百零二页，共一百二十四页，2022年，8月28日2023/1/18表1经DMC转移后的对数比特值卷积码的译码（续）2）DMC转移后的对数比特度量值以及经过上面公式线性变换后的值用下列表格表示：O1O2I2I10-0.4-0.52-0.70-11-1-0.7-0.52-0.40

表2取参数a=16.8，b=1后相应整数度量值O1O2I2I1010850105810第一百零三页，共一百二十四页，2022年，8月28日2023/1/183）若输入：u=（1011100），后两位为尾比特，

DMC输入：c=（11，10，00，01，10，01，11）

DMC输出：y=（I2O1，I1O1，O1O2，O1I1，I1I2

，O2I1，I2O2）软判决译码输出：u=（1011100）=

u结论：

--软与硬判决译码过程完全类似；不同之处有：

--信道模型不一样，硬为BSC，软为DMC；

--度量值及准则不一样，一个为最小汉明，一个为最大似然；

--软比硬复杂度增加不多，但性能却有1.5～2dB改善；卷积码的译码（续）第一百零四页，共一百二十四页，2022年，8月28日2023/1/18引言●级联码是由短码构造长码的一种有效的方法,它是由Forney首先提出.●级联码可用于纠正混合差错.即既有独立随机差错又有突发差错,且纠错能力很强.●级联码是由内外两个短码构成一个长码,内码可设计成一般复杂度以纠正随机独立差错为主的纠错码,外码可设计为较复杂,且纠错能力较强,即可纠正内码不能纠正的随机独立差错和部分突发差错的码.●原则上,无论是内码还是外码,均可采用分组码和卷积码,但目前采用最多的是内码为卷积码,外码是RS分组码.级联编码第一百零五页，共一百二十四页，2022年，8月28日2023/1/18基本原理●它由两个短码即内码与外码串接而成:即(n,k)=[n1×

n2,k1×k2]=[(n1k1)(n2

k2)]●称(n1,k1)为内码,(n2,k2)为外码。一组k位信息可分解为k2个字节，而每个字节中有k1个信息位,(n1,k1)可纠字节内独立随机差错,一般由卷积码构成,称为内码;(n2,k2)可纠正余下的差错以及字节间的突发差错.一般由纠错能力强的RS码构成,称为外码。级联编码（续）第一百零六页，共一百二十四页，2022年，8月28日2023/1/18基本方框图级联编码（续）●若(n1,k1)最小距离为d1

(n2,k2)最小距离为d2,串接后级联码最小距离d≥d1×d2,●级联码是由内外码串接而成,又称为串行级联码,其设备仅是两者的制机组合,它要比采用一个长码时所需的设备简单得多.第一百零七页，共一百二十四页，2022年，8月28日2023/1/18

级联码标准●

最早采用级联码的是八十年代美国宇航局NASA,将它用于深空遥测数据的纠错.●

1987年NASA制定了级联码深空遥测标准CCSDS.●

典型标准级联码系统框图如下:级联编码（续）第一百零八页，共一百二十四页，2022年，8月28日2023/1/181984年,NASA采用上述的典型标准，其中：内码为(2,1,7)卷积码,外码为(255,223)RS码.而交织器深度大约为2～8个外码块,其性能很优异,当Eb／N0=2.53dB时，误码率Pb≤10-6。

级联码的性能下面给出在Pb≤10-6条件下(Pb为误比特率)，一些级联码的性能:级联编码（续）第一百零九页，共一百二十四页，2022年，8月28日2023/1/18

内码

外码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