九随机教学讲解课件

第九章差错控制编码9.1引言9.2纠错编码的基本原理9.3常用的简单编码9.4线性分组码9.5循环码9.6卷积码第九章差错控制编码9.1引言9.1引言一、信源编码与信道编码

数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。

信源编码：提高数字信号的有效性，如，PCM编码，编码，图象数据压缩编码等。

信道编码：提高传输的可靠性，又称抗干扰编码，纠错编码。9.1引言一、信源编码与信道编码

从差错控制角度看：信道分三类：（信道编码技术）随机信道：由加性白噪声引起的误码，错码是随机的，错码间统计独立。突发信道：错码成串，由脉冲噪声干扰引起。混合信道：既存在随机错误，又存在突发错码，那一种都不能忽略不计的信道。从差错控制角度看：信道分三类：（信道编码二：差错控制的工作方式检错重发前向纠错，不要反向信道反馈校验法，双向信道二：差错控制的工作方式检错重发9.2纠错编码的基本原理一：分组码，码重，码距（樊书P282表9-1）

将码组分段：分成信息位段和监督位段，称为分组码，记为（n,k）n~编码组的总位数，简称码长（码组的长度）k~每组二进制信息码元数目（信息位段）n-k=r~监督码元数目，（监督位段）（见樊书P282，图9-2）9.2纠错编码的基本原理一：分组码，码重，码距（樊书P在分组码中，有“1”的数目称为码组的重量，简称码重。例如，码组（11010），码长n=5，码重为3。把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称Hamming（汉明）的距离。例如，码组（11000）与（10011）的距离为3。在分组码中，有“1”的数目称为码组的重量，简称码重。而码组集合中，全体码组之间的距离的最小值称为最小码距（d0

）。检测e个错，纠正t个错,纠正t个错同时检测e个错码长n发生r个错的概率纠1，2个错误码率也下降几个数量级而码组集合中，全体码组之间的距离的最小值称为最小码距（d09.3常用的简单编码纠错码的分类：(1)奇偶校验码“1”的数目应为偶或奇数）(2)二维奇偶校验码(3)恒比码(4)正反码9.3常用的简单编码纠错码的分类：(1)奇偶校验码

偶校验位信息位110011(1)奇偶校验码偶校验位信息位11(2)二维奇偶校验码

列监督位，

行监督位，

/0/1/0/1对称出现4个错码也检不出来

(2)二维奇偶校验码

列监督位，行监督位，/0/1/0

(3)恒比码

例如，我国电传机传输阿拉伯数字时，用5位代码表示，其中恒有3个“1”，称为“5中取3”

恒比码。

阿拉伯数字保护电码阿拉伯数字保护电码123450101111001101101101000111678901010111100011101001101101(3)恒比码

例如，我国电传机传输阿拉伯数字时，用5(4)正反码

正反码的信息位段长与监督位段长相同，如正反码组：信息位段有奇数个1：1100111001

（监督位与信息位重复）

信息位段有偶数个1：1000101110

（监督位是信息位反码）信息位监督位信息位监督位(4)正反码

正反码的信息位段长与监督位段长相同，如正反码9.4线性分组码

一：基本概念可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码。在代数码中，常见的是线性码，即编码中的信息位和监督位是由一些线性代数方程联系着，或者说可用线性代数方程表述编码的规律性。

9.4线性分组码

一：基本概念二：线性分组码的一种

——汉明码

构造原理

先回顾偶校验码

在接收端实际上计算监督关系式：

~无错

~有错

~称校正子

二：线性分组码的一种

——汉明码

构造原理两个监督式就有两个校正子，其可能值有4种组合：00，01，10，11，这4种组合代表不同信息。若用1种组合表示无错,其余3种组合就可以用来表示一位错码的3种不同位置。同理，r个监督式能指示一位错码的个可能位置。

一般来说，若码长n，信息位数k，则监督位,汉明码n与r满足：

现以（n，k）=（7，4），r=3为例的汉明码来说明如何具体构造这些监督关系式。两个监督式就有两个校正子，其可能值有4种组合：一般来设码字（n，k）=

～校正子

的值与错码位置的对应关系如下表

只要（s1或s2，或s3）为“1”，就表示有错设码字（n，k）=～校正子的值与错码位置的对应关系如下错码位置错码位置001101010110100111011000无

错全为零，表示无错。

全为零，表示无错。

在发端编码时，信息位的值是随机的，监督位应根据信息位按监督关系来确定，即监督位应使上面的监督式为零。

即要求：

在发端编码时，信息位的值是随机的，或写成监督码元在左边的形式：

信息位一旦确定后，可直接按上式计算出监督位。（见樊书P289图9-5）

接收端收到每个码字（码组）后，先计算出偶监督关系式，再按表9-4（樊书P288）判断错码情况。

或写成监督码元在左边的形式：信息位

如果不全零，可判出在哪一位出错。查樊书表9-4，判错哪一位并纠正之发送端，将信息位按此式加上监督位后发送接收端，先计算校正为零否，不为零则出错码，查表后，纠正改之

汉明码最小距=3（见樊书表9-5），能够纠正单个错误。

如果不全零，可判出在哪一位三：线性分组码的一般原理

(1)监督阵和生成矩阵将上述汉明码（7，4）的监督关系式改写成：（见樊书P289，9.4-8）

上式中简写为+，表示模2相加。

三：线性分组码的一般原理

(1)监督阵和生成矩阵上式中写成矩阵形式：

=（模2）

写成矩阵形式：（模2）

简记（H~监督矩阵）监督矩阵H为（行，列）阶矩阵，H阵的每行之间彼此线性无关。也可将H矩阵分为两部分：

H=

其中P为r×k阶矩阵，为r×r阶单位矩阵。简记若把监督关系式改写补充：

若把监督关系式改写补充：THANKYOUSUCCESS2023/1/925可编辑THANKYOUSUCCESS2023/1/825

可改写为矩阵形式：

Q=PT

可改写为矩阵形式：Q=PT

G称为生成矩阵，如果找到G，则纠错编码方法就确定了，可由信息组和G可产生全部码字。

～也称典型生成矩阵，其中

为k×k方阵，

由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后，这种码称为系统码。

G称为生成矩阵，如果找到G，则纠错(2)校正子S（伴随式）

设发送码组设接收码组

则发送码组与接收码组之差定义为E（也称错误图样）：（模2）其中

(2)校正子S（伴随式）设发送码组则发送码组与接

因此，若,表示该位接收码元无错；若，则表示有错。

,也可改写为

例如：发送A=[1000111]

错误E=[0000100]

接收B=[1000011]令

令

称S为校正子，也称伴随式。

零矩阵

因此，若,表示该位接收码元无错；若

由此可见，校正子S与错误图样E之间有确定的线性变换关系，若S和E之间一一对应，则S将能代表错码的位置。

接收端译码器的任务就是从校正子S确定错误图样，然后，从接收到的码字中减去错误图样E。

上述（7，4）汉明码的校正子S与错误图样E的对应关系见下表：表中，校正子S的种形式分别代表A码无错和-1种有错的图样。由此可见，校正子S与错误图样E序号错误码位错误图样

E校正子

S

0——

00000000001

00000010012

00000100103

00001001004

00010000115

00100001016

01000001107

1000000111e6e5e4e3e2e1e0序号错误码位错误图样E校正子S0——09.5循环码一、特点：编码和解码设备都不太复杂，且检（纠）错能力较强。具有线性和循环性，即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，仍为该码中的一个码组。9.5循环码一、特点：

将各码元当作是一个多项式的系数，樊书P293页，表9－6中的任一码组可表示为

这种多项式中，x仅是码元位置的标记。这种多项式有时称为码多项式。二、编码原理将各码元当作是一个多项式的系数，樊书P293页，(1)、码多项式的按模运算

若一整数m可以表示为式中Q～整数。则在模n运算下，有(1)、码多项式的按模运算若一整数m可以表示为式在循环码中，若T(x)是一个长为n的许用码组，则在按模运算下，也是一个许用码组，即若则也是一个许用码组。例如在循环码中，若T(x)是一个长为n的许用码组，则在按模运算下(2)、循环码的生成矩阵G

在一个循环码中有个不同码组。若用表示其中前（k－1）位皆为0的码组，则都是码组，而且这k个码组是线性无关的。因此他们可以用来构成此循环码的生成矩阵G。Tab.9-6Page293,k=3,g(x)0010111x^43210(2)、循环码的生成矩阵G在一个

循环码的生成矩阵G可以写成上式可作线性变换成的形式。上式可作线性变换成

循环码的生成多项式应该是的一个次因式。例如，可以分解为

为了求（7，3）循环码的生成多项式g(x)，要从上式中找一个（n-k)=4次的因子。这样的因子有两个，即

以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的循环码码组也就不同。(3)、寻找生成多项式循环码的生成多项式应该是三、循环码编、解码方法（1）编码步骤(代数方法）1、用乘。这一运算实际上是把信息码附加上（）个0。2、用除，得到商Q（x）和余式。3、编出的码组为

(2)T=mG(matrix-operation)三、循环码编、解码方法（1）编码步骤(代数方法）（2）解码步骤1、用生成多项式除接收码组得出余式；2、按余式用查表的方法或通过某种运算得到错误图样就可以确定错码的位置；3、从中减去，变得到已纠正错误的原发送码组。

（2）解码步骤9.6卷积码一.卷积码的结构图D1D29.6卷积码一.卷积码的结构图D1D2由图可知，（2，1，2）卷积码的编码规则为输出码字为由图可知，（2，1，2）卷积码的编码规则为输出码字为二.卷积码的生成多项式则相应的系统冲击响应为用生成多项式表示二.卷积码的生成多项式则相应的系统冲击响应为用生成多项式表三.编码率与约束长度k输入，n输出,每时刻输出与过去(L-1)k个输入亦关编码率=k/n=1/2,约束长度=L=7三.编码率与约束长度k输入，n输出,每时刻输出与过去(L-1L=5L=5四.状态图0001101100/011/110/001/101/010/111/000/1D1D2四.状态图0001101100/011/110/001/10

五.网格图

input=101+00

output=11100010110010011110/011/111/110/000/111/0五.网格图input=101+00

output=

ViterbiDecoding;output=101

HARD:input=11110010110010011110111110001111001011000201111113102012004,61,4114,3013,21100100131103ViterbiDecoding;output=101

HTHANKYOUSUCCESS2023/1/949可编辑THANKYOUSUCCESS2023/1/849第九章差错控制编码9.1引言9.2纠错编码的基本原理9.3常用的简单编码9.4线性分组码9.5循环码9.6卷积码第九章差错控制编码9.1引言9.1引言一、信源编码与信道编码

数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。

信源编码：提高数字信号的有效性，如，PCM编码，编码，图象数据压缩编码等。

信道编码：提高传输的可靠性，又称抗干扰编码，纠错编码。9.1引言一、信源编码与信道编码

从差错控制角度看：信道分三类：（信道编码技术）随机信道：由加性白噪声引起的误码，错码是随机的，错码间统计独立。突发信道：错码成串，由脉冲噪声干扰引起。混合信道：既存在随机错误，又存在突发错码，那一种都不能忽略不计的信道。从差错控制角度看：信道分三类：（信道编码二：差错控制的工作方式检错重发前向纠错，不要反向信道反馈校验法，双向信道二：差错控制的工作方式检错重发9.2纠错编码的基本原理一：分组码，码重，码距（樊书P282表9-1）

将码组分段：分成信息位段和监督位段，称为分组码，记为（n,k）n~编码组的总位数，简称码长（码组的长度）k~每组二进制信息码元数目（信息位段）n-k=r~监督码元数目，（监督位段）（见樊书P282，图9-2）9.2纠错编码的基本原理一：分组码，码重，码距（樊书P在分组码中，有“1”的数目称为码组的重量，简称码重。例如，码组（11010），码长n=5，码重为3。把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称Hamming（汉明）的距离。例如，码组（11000）与（10011）的距离为3。在分组码中，有“1”的数目称为码组的重量，简称码重。而码组集合中，全体码组之间的距离的最小值称为最小码距（d0

）。检测e个错，纠正t个错,纠正t个错同时检测e个错码长n发生r个错的概率纠1，2个错误码率也下降几个数量级而码组集合中，全体码组之间的距离的最小值称为最小码距（d09.3常用的简单编码纠错码的分类：(1)奇偶校验码“1”的数目应为偶或奇数）(2)二维奇偶校验码(3)恒比码(4)正反码9.3常用的简单编码纠错码的分类：(1)奇偶校验码

偶校验位信息位110011(1)奇偶校验码偶校验位信息位11(2)二维奇偶校验码

列监督位，

行监督位，

/0/1/0/1对称出现4个错码也检不出来

(2)二维奇偶校验码

列监督位，行监督位，/0/1/0

(3)恒比码

例如，我国电传机传输阿拉伯数字时，用5位代码表示，其中恒有3个“1”，称为“5中取3”

恒比码。

阿拉伯数字保护电码阿拉伯数字保护电码123450101111001101101101000111678901010111100011101001101101(3)恒比码

例如，我国电传机传输阿拉伯数字时，用5(4)正反码

正反码的信息位段长与监督位段长相同，如正反码组：信息位段有奇数个1：1100111001

（监督位与信息位重复）

信息位段有偶数个1：1000101110

（监督位是信息位反码）信息位监督位信息位监督位(4)正反码

正反码的信息位段长与监督位段长相同，如正反码9.4线性分组码

一：基本概念可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码。在代数码中，常见的是线性码，即编码中的信息位和监督位是由一些线性代数方程联系着，或者说可用线性代数方程表述编码的规律性。

9.4线性分组码

一：基本概念二：线性分组码的一种

——汉明码

构造原理

先回顾偶校验码

在接收端实际上计算监督关系式：

~无错

~有错

~称校正子

二：线性分组码的一种

——汉明码

构造原理两个监督式就有两个校正子，其可能值有4种组合：00，01，10，11，这4种组合代表不同信息。若用1种组合表示无错,其余3种组合就可以用来表示一位错码的3种不同位置。同理，r个监督式能指示一位错码的个可能位置。

一般来说，若码长n，信息位数k，则监督位,汉明码n与r满足：

现以（n，k）=（7，4），r=3为例的汉明码来说明如何具体构造这些监督关系式。两个监督式就有两个校正子，其可能值有4种组合：一般来设码字（n，k）=

～校正子

的值与错码位置的对应关系如下表

只要（s1或s2，或s3）为“1”，就表示有错设码字（n，k）=～校正子的值与错码位置的对应关系如下错码位置错码位置001101010110100111011000无

错全为零，表示无错。

全为零，表示无错。

在发端编码时，信息位的值是随机的，监督位应根据信息位按监督关系来确定，即监督位应使上面的监督式为零。

即要求：

在发端编码时，信息位的值是随机的，或写成监督码元在左边的形式：

信息位一旦确定后，可直接按上式计算出监督位。（见樊书P289图9-5）

接收端收到每个码字（码组）后，先计算出偶监督关系式，再按表9-4（樊书P288）判断错码情况。

或写成监督码元在左边的形式：信息位

如果不全零，可判出在哪一位出错。查樊书表9-4，判错哪一位并纠正之发送端，将信息位按此式加上监督位后发送接收端，先计算校正为零否，不为零则出错码，查表后，纠正改之

汉明码最小距=3（见樊书表9-5），能够纠正单个错误。

如果不全零，可判出在哪一位三：线性分组码的一般原理

(1)监督阵和生成矩阵将上述汉明码（7，4）的监督关系式改写成：（见樊书P289，9.4-8）

上式中简写为+，表示模2相加。

三：线性分组码的一般原理

(1)监督阵和生成矩阵上式中写成矩阵形式：

=（模2）

写成矩阵形式：（模2）

简记（H~监督矩阵）监督矩阵H为（行，列）阶矩阵，H阵的每行之间彼此线性无关。也可将H矩阵分为两部分：

H=

其中P为r×k阶矩阵，为r×r阶单位矩阵。简记若把监督关系式改写补充：

若把监督关系式改写补充：THANKYOUSUCCESS2023/1/974可编辑THANKYOUSUCCESS2023/1/825

可改写为矩阵形式：

Q=PT

可改写为矩阵形式：Q=PT

G称为生成矩阵，如果找到G，则纠错编码方法就确定了，可由信息组和G可产生全部码字。

～也称典型生成矩阵，其中

为k×k方阵，

由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后，这种码称为系统码。

G称为生成矩阵，如果找到G，则纠错(2)校正子S（伴随式）

设发送码组设接收码组

则发送码组与接收码组之差定义为E（也称错误图样）：（模2）其中

(2)校正子S（伴随式）设发送码组则发送码组与接

因此，若,表示该位接收码元无错；若，则表示有错。

,也可改写为

例如：发送A=[1000111]

错误E=[0000100]

接收B=[1000011]令

令

称S为校正子，也称伴随式。

零矩阵

因此，若,表示该位接收码元无错；若

由此可见，校正子S与错误图样E之间有确定的线性变换关系，若S和E之间一一对应，则S将能代表错码的位置。

接收端译码器的任务就是从校正子S确定错误图样，然后，从接收到的码字中减去错误图样E。

上述（7，4）汉明码的校正子S与错误图样E的对应关系见下表：表中，校正子S的种形式分别代表A码无错和-1种有错的图样。由此可见，校正子S与错误图样E序号错误码位错误图样

E校正子

S

0——

00000000001

00000010012

00000100103

00001001004

00010000115

00100001016

01000001107

1000000111e6e5e4e3e2e1e0序号错误码位错误图样E校正子S0——09.5循环码一、特点：编码和解码设备都不太复杂，且检（纠）错能力较强。具有线性和循环性，即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，仍为该码中的一个码组。9.5循环码一、特点：

将各码元当作是一个多项式的系数，樊书P293页，表9－6中的任一码组可表示为

这种多项式中，x仅是码元位置的标记。这种多项式有时称为码多项式。二、编码原理将各码元当作是一个多项式的系数，樊书P293页，(1)、码多项式的按模运算

若一整数m可以表示为式中Q～整数。则在模n运算下，有(1)、码多项式的按模运算若一整数m可以表示为式在循环码中，若T(x)是一个长为n的许用码组，则在按模运算下，也是一个许用码组，即若则也是一个许用码组。例如在循环码中，若T(x)是一个长为n的许用码组，则在按模运算下(2)、循环码的生成矩阵G

在一个循环码中有个不同码组。若用表示其中前（k－1）位皆为0的码组，则都是码组，而且这k个码组是线性无关的。因此他们可以用来构成此循环码的生成矩阵G。Tab.9-6Page293,k=3,g(x)0010111x^43210(2)、循环码的生成矩阵G在一个

循环码的生成矩阵G可以写成上式可作线性变换成的形式。上式可作线性变换成

循环码的生成多项式应该是的一个次因式。例如，可以分解为

为了求（7，