信道的纠错编码ok

z 将这三类信道编码统称为纠错码或抗干扰码。
15
第3节 纠错码分类
2) 按应用目的分类： • 检错码：只能够检测出错误的码； • 纠错码：既能检测出错误又能自动纠正错误的码； • 纠删码：能够纠正被删除了信息的错误的码。
• 这三类码之间并没有本质区别，每类码都可由采用的译码 方法不同而作为另两类码使用。
23
4.1 线性分组码的生成矩阵和校验矩阵
二元线性分组码: (5,2)分组码: 码长为5，信息位为2。
c1 = m1 c2 = m2 c3 = m1 ⊕ m2 = c1 ⊕ c2 c4 = m1 = c1 c5 = m1 ⊕ m2 = c1 ⊕ c2
用矩阵表示为: c=mG
c = [c1
c2 L
c5 ] = mG = [m1
• 其生成矩阵G的K个相互独立的行向量{g1,g2,…,gK}是它 的一组基底;
例：前面的（5，2）系统码： c1 = m1
G
=
⎡1 ⎢⎣0
0 1
1 1
11⎤ 0 1⎥⎦
2×5
c2 = m2 c3 = m1 ⊕ m2 = c1 ⊕ c2 c4 = m1 = c1
c5 = m1 ⊕ m2 = c1 ⊕ c2
c1 = m1 c2 = m2 c3 = m1 ⊕ m2 = c1 ⊕ c2 c4 = m1 = c1 c5 = m1 ⊕ m2 = c1 ⊕ c2
G
=
⎡1 ⎢⎣0
0 1
1 1
11⎤ 0 1⎥⎦
m1=1, m2=0 m1=0, m2=1
28
4.1 线性分组码的生成矩阵和校验矩阵
• 二元(N,K)线性码C={c}可看成一个N重K维线性空间;
⎪⎪c2 = m2

监督矩阵H 的标准形式：后面 r 列是一单位子阵的监督矩 阵 H。 H 阵的每一行都代表一个监督方程，它表示与该行中“1” 相对应的码元的模2和为0。
H 的标准形式还说明了相应的监督元是由哪些信息元决定 的。例如 (7,3) 码的H 阵的第一行为 (1011000)，说明此码的
第一个监督元等于第一个和第三个信息元的模2和，依此类 推。
线性分组码的生成矩阵: 在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，一 定存在 k 个线性无关的码字：g1,g2,…, gk,。码 CI 中其它任 何码字C都可表示为这 k 个码字的线性组合，即
C mk 1g1 mk 2 g 2 m0 g k 其中：mi GF(2), i 0,1, k 1。写成矩阵形式得 C1n g1 g2 m G mk 1mk 2 m0 1k k n g k
h11 h 21 hr1 h12 h22 hr 2 h1n h2 n hrn C0
H r n
C1n Cn 1 Cn 2 则：
T H rn CT 0 n1 r 1
或
C1n HT nr 01r
称H为(n, k )线性分组码的一致监督 矩阵。
l缺点是译码设 备较复杂；编码 效率较低。
（２）反馈重发(ARQ)方式: ARQ (Automatic Repeat Request) 方式是：发端发出能 够发现错误的码（检错码），收端译码器收到后，判断在 传输中有无错误产生，并通过反馈信道把捡测结果告诉发 端。发端把收端认为有错的消息再次传送，直到收端认为 正确接收为止。 l优点是译码设备简单，在多余度一定的情 况下，码的检错能力比纠错能力要高得多，因 而整个系统能获得极低的误码率。 l应用ARQ方式必须有一条从收端至发端的反馈 信道。并要求信源产生信息的速率可以进行控制， 收、发两端必须互相配合，其控制电路比较复杂， 传输信息的连贯性和实时性也较差。

检错与纠错原理
• 检错、纠错的目的是要根据信道接收端接收 到的信息序列 R 来判断 R 是否就是发送的序 列，如果有错则尽可能纠正其中的错误。 • 要纠正传输差错，首先必须检测出错误。而 要检测出错误，常用的方法是将发送端要传 送的信息序列(常为二进制序列)中截取出长度 相等的码元进行分组，每组长度为k，组成k 位码元信息序列 M 并根据某种编码算法以 一定的规则在每个信息组的后面产生 r 个冗 余码元，由冗余码元和信息码元一起形成 n k r ，因而纠错 C 有 n 位编码序列 “ 编码是冗余编码，如图6.1所示。
9.3.1 线性分组码的基本概念
• 定义：对信源编码器输出的二进制序列进行分
组，设分组长度为 k ，相应的码字表示为： 信道编码(纠错编码)的目的是将信息码字 M 进行 变换，使其成为以下形式：
M (mk , m2 ,
C (cn
, m1 )
c2c1 )
其中： n k ，我们称全体码字 C 的集合为分 组码。若由 M 到 C 之间的变换为线性变换， 则称全体码字 C 的集合为线性分组码，常用 线性分组码 ( n, k ) 表示全体码字 C 的集合.
• 所以，奇偶校验方式只能检测出位 代码中出现的任意奇数个错误，如 果代码中错码数为偶数个，则奇偶 校验不能奏效。由于奇偶校验码容 易实现，所以当信道干扰不太严重 以及码长不很长时很有用，特别是 在计算机通信网的数据传送中经常 应用这种检错码。
9.3
线性分组码
• 线性分组码是纠错码中非常重要的一 类码，虽然对于同样码长的非线性码 来说线性码可用码字较少，但由于线 性码的编码和译码容易实现，而且是 讨论其他各类码的基础，至今仍是广 泛应用的一类码。
• 例1 设信源编码器输出的信息序列 为 M (mk m2m1 ) ，其中 mi (1 i k ) 是二进制 数。信道编码器输出的码字 C (cn c2c1 ) ， 其中 ci (1 i n, n k ) 也是二进制数。若从 M 到 C 的变换规则为： c m

9.1 基本概念 —— 信道分类
随机信道
特征：错误是随机、独立的（前后码元的错误无关） 主要干扰源：高斯白噪声 例：同轴电缆、光纤
突发信道
特征：错误是成串的（前后码元的错误相关） 主要干扰源：强脉冲干扰 例：短波信道、移动通信信道
1
9.1 基本概念 —— 错误图样
定义
对于二元信道，接收序列与发送序列的模2加
6
9.2 线性分组码 —— 纠错码的开端
典型的打孔卡 打孔卡读卡机
7
9.2 线性分组码 —— (7, 3)分组码
检出1-3位错误，纠正1位错误
信息组: x (m2m1m0 )
监督元: b (b3b2b1b0 )
监督元生成方程:
模2运算
b3 m2
m0
b2 m2 m1 m0
b1 m2 m1
1 0 1 1 0 0 0
H
(QT
I
4
)
1 1
1 1
1 0
0 0
1 0
0 1
0 0
0 1 1 0 0 0 1
(QT I4 )CT OT
HCT OT
CHT O
其中 O 0 0 0
11
9.2 线性分组码 —— (7, 3)分组码
接收码字：
R CE
伴随式:
S RHT
S (C E)HT CHT EH T O EH T EH T
x(I3 Q) xG
生成矩阵:
1 0 0 1 1 1 0
G (I3 Q) 0 1 0 0 1 1 1
0 0 1 1 1 0 1
9
9.2 线性分组码 — m0
b1 m2 m1
b0
m1 m0
b3 m2

9.2 纠错编码的基本原理
3、分组码的码重和码距
码重：把码组中“1”的个数目称为码组的重量，简称码 重。 码距：把两个码组中对应位上数字不同的位数称为码组 的距离，简称码距。码距又称汉明距离。 例如，“000”＝晴，“011”＝云，“101”＝阴，“110” ＝雨，4个码组之间，任意两个的距离均为2。
前 向 纠 错 方 式 记 作 FEC(Forword Error Correction) 。发端发送能够纠正错误的码，收端 收到信码后自动地纠正传输中的错误。 特点 : 是单向传输，实时性好，但译码设备较复杂。
11.1 概述
3. 混合纠错方式
混合纠错方式记作 HEC(Hybrid ErrorCorrection) 是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有
误的码，由收端判决传输中无错误产生，如果发现错误，则
通过反向信道把这一判决结果反馈给发端，然后，发端把收 端认为错误的信息再次重发，从而达到正确传输的目的。其 特点是需要反馈信道，译码设备简单，对突发错误和信道干 扰较严重时有效， 但实时性差，主要在计算机数据通信中
得到应用。
11.1 概述
2. 前向纠错方式
接收端在收到禁用码组时，就认为发现了错码。当发生 3个错码时，“000”变成了“111”，它也是禁用码组， 故这种编码也能检测3个错码。 但是这种码不能发现一个码组中的两个错码，因为 发生两个错码后产生的是许用码组。
上面这种编码只能检测错码，不能纠正错码。例如， 当接收码组为禁用码组“100”时，接收端将无法判断 是哪一位码发生了错晴， “011”＝云 ， “101”＝阴 ， “110”＝雨
这时，虽然只能传送4种不同的天气，但是接收端却 有可能发现码组中的一个错码。

外码 译码输出 译码
• 优点：性能较一般短码有译很码器 大改善 • 缺点：编码效率低；当R/C →1时性能迅速恶化
信道编码和纠错编码相关概念
产生背景（续）
• 软输入软输出和迭代译码
对数似然比LLR
^
L' (d)
L(d
|
x)
log
P(d P(d
1| 1|
x) x)
logPP((xx
| |
d d
信道编码和纠错编码相关概念
（2）编码原理
• 原理图
uj0 uj1 uj,k-1
...
xj0
uj-m,0
xj1
...
... ...
uj-m,1
映射
uj-m,k-1
xj,n-1
... ... ...
m stage delay
信道编码和纠错编码相关概念
编码原理（续）
• 几个例子
xj0
+
uj
uj
+
xj1
1) 1)
logPP((dd
1) 1)
L(x| d)L(d) Lc(x)L(d)
^
^
^
^
L(d) L'(d)Le(d) Lc(x)L(d)Le(d)
信道编码和纠错编码相关概念
产生背景（续）
• 软输入软输出和迭代译码
feedback for the next iteration
L(d)
Lc(x)
信道编码和纠错编码相关概念
（2）线性分组码----举例
• 奇偶监督码 • 汉明码 • BCH码 • RS码 • CRC码
信道编码和纠错编码相关概念
奇偶监督码

25
线性分组码
线性系统分组码：用标准生成矩阵 Gk×n 编成的
码字，前面 k 位为信息数字，后面 r=n－k 位
为校验数字，这种信息数字在前校验数字在后 的线性分组码称为线性系统分组码。
Cn-1 信 息 码 Cn-k Cn-k-1 C0
监 督 码
26
线性分组码
例：(7,4) 线性码的生成矩阵为 1 0 0 0
3
错误图样
⑴ 当系统无干扰时 R=C ⑵ 当系统有干扰时 R=C+E 其中，E称为信道的错误图样， E=(e0,e1,…,en-1)；ei∈{ 0,1}；当ei=1，则第i位上有错；反 之，无错。 例： C = 0 0 1 0 1 1 0 1 E= 01001001 R= 01100100 由信道的对称性可知 p(0/1)=p(1/0)=p(e=1)=p 反之，若已知R ，E 则可求出C，这就是纠错码的原理，如： E= 01001001 R= 01100100 4 C= 00101101
对应码字 0000000 0011101 0100111 0111010 1001110 1010011 1101001 1110100
18
线性分组码

为了运算方便，将监 督方程写成矩阵形式， 得:
C6 0 C4 C3 0 0 0 0 C C C 0 C 0 0 0 6 5 4 2 C6 C5 0 0 0 C1 0 0 0 C5 C4 0 0 0 C0 0
20
线性分组码
一致监督阵H
21
线性分组码
⒉ 监督阵与生成阵的关系
由于生成矩阵G的每一行都是一个码字， 所以G 的每行都满足Hr×nCTn×1=0Tr×1，

(3) 举例
(7,4) 线性码的生成矩阵为
(4) 生成矩阵与一致监督矩阵的关系

由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足 Hr×nCTn×1=0Tr×1，则有
Hr×nGTn×k=0Tr×k 或

Gk×nHTn×r=0k×r
线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换。

根据不同的应用场合对差错率有不同的要求。

在电报传送时，允许的比特差错率约为10－4～10 － 5；

计算机数据传输，一般要求比特差错率小于10－ 8～10－9；
在遥控指令和武器系统的指令系统中，要求有更 小的误比特率或码组差错率。

采用信道编码的数字通信系统

在某些情况下，信道的改善可能较困难或者不经济，这 就要求采用信道编码，以便满足系统差错率的技术指标 要求。

例如：(7,3) 码的两个码字 U=0011101,V=0100111， 它们之间第2、3、4和6位不同。因此，码字 U 和 V 的距离为4。 线性分组码的一个码字对应于 n 维线性空间中的一 点，码字间的距离即为空间中两对应点的距离。

汉明重量和汉明球

汉明球：以码字C为中心，半径为 t 的汉明球是与 C 的汉 明距离≤ t 的向量全体 SC(t)


码元的组成及其它们之间的关系

信息码组：数字序列 m 总是以 k 个码元为一组传
输，称这k 个码元的码组为信息码组。例如遥控系 统中的每个指令字，计算机中的每个字节。

码组/码字：信道编码器按一定的规则对每个信息
码组附加一些多余的码元，构成了 n 个码元的码组。

监督码元/监督元：附加的 (n－k) 个码元称为该码

线性分组码
线性分组码的编码过程分为两步： 把信息序列按一定长度分成若干信息码组，每组由 k 位 组成； 编码器按照预定的线性规则(可由线性方程组规定)，把信 息码组变换成 n 重 (n>k) 码字，其中 (n－k) 个附加码元是 由信息码元的线性运算产生的。 信息码组长 k 位，有 2k 个不同的信息码组，则应该有 2k 个 码字与它们一一对应。
⑴满足用户对误码率的要求；
⑵有尽可能高的信息传输速率；⑶有来自可能简单的编译码算法且易于实现；
(4)可接受的成本。
纠错码的分类
按信息位与校验位的关系，可将编码分成以下两大类： （1）线性码——校验位与信息位呈线性关系（即可用一次 方程描述）。 （2）非线性码——校验位与信息位不呈线性关系。
按信息位与校验位之间的约束关系，可分为： （1）分组码——将信息符号分成k位一组，每组增加r位校验位，这r 位校验位仅与本组的k位信息位有关，与其他的信息位无关。 ① 循环码——除全零码字外，其余码字都可由另一码字的码符循 环移位得到； ② 非循环码——某个码字的循环移位不一定还是该码的码字。 （2）卷积码——将信息符号分成k位一组，每组增加r位校验位，这r 位校验位不仅与本组的k位信息位有关，还与前面m组的信息位有关。
差错类型
讨论码字序列c通过离散信道时发生的情况，信道分为无记忆信 道和有记忆信道。 l在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一 个差错的出现与其前后是否有错无关,如图。在无记忆信道中，错 误是随机产生的，因此被称作随机错误，无记忆信道也被称为随机 信道（random channel）。
（３）混合纠错(HEC)方式： HEC (Hybrid Error Control) 方式是上述两种方式的结 合。发端发送的码既能检错、又有一定的纠错能力。收端 译码时若发现错误个数在码的纠错能力以内，则自动进行 纠错；若错误个数超过了码的纠错能力，但能检测出来， 则通过反馈信道告知发方重发。这种方式在一定程度上避 免了 FEC方式译码设备复杂和 ARQ方式信息连贯性差的 缺点。 在设计差错控制系统时，选择何种实现方式，应综合考 虑各方面的因素。主要有：