s eHT
信道编码技术
伴随式解码
错误图案e与伴随式的对应关系表：
No e0 e1 e2 e e3 e4 e5 s0 S No s1 s2 e0 e1 e2 e3 e4 e5 s0 s1 s2 e s
0 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0


注意如果一共有2k 个码字, 那 么共有 k 个基底码字
如果一种编码是线性的，那么它的 最小距离就等于它的最小权重
即在任意码字中的“1”的个数的 最小值（全0码除外）
通信与信息工程学院
信道编码技术
生成矩阵
将基底码字作为矩阵的行
生成矩阵
b1 1 1 0 1 0 0 G b 2 0 1 1 0 1 0 b3 1 0 1 0 0 1
循环码
对于二进制码组，多项式的每个系数不是0就是1，x仅是码元位置的标 志。因此，这里并不关心x的取值。 例如，表中的第7码字可以表示为：
预备知识点：整数运算中的模n运算 若一个整数m可以表示为: 那么在模n运算下，有m≡p（模n），也就是说，在模n运算下，一整 数m等于其被n除所得的余数。 比如1+2=3≡1（模2），3+4=7 ≡ 2（模5）
无线通信技术 线通信技术
翟旭平 zhaixp@shu edu cn zhaixp@
2013-4-28
信道编码技术
4.1.1 编码技术概述
编码技术是用一系列编码后的信息取代原始信息的技术，其作用是 编码技术是用 系列编码后的信息取代原始信息的技术 其作用是 帮助原始信息的重构
Coding g Cryptography to preserve secrecy Line coding to improve spectral characteristics
通信与信息工程学院
信道编码技术
线性和基底
如果一个编码是线性的，可以 选择码字中的一些子集来生成 其他的任意码字 其 的任意码字
这些码字称为基底 在前面给出的码字例子中我们选择
(a) (b) 01110 10011
举例
一个编码的码字为
000000, 000000 110100, 011010, 101110, , 101001 011101 110011 000111
信道编码技术
编码的分类
分组码、卷积码
– 分组码:
• 校验比特仅取决于传输信息的一 校验比特仅取决于传输信息的 个有限分组 • 码的表示方式(n,k) --- n=码字 长度, k=信息比特长度, n-k=校验 比特长度 • 有时候表示方式中还会出现第三 个数，dmin, 或可纠正的错误比特 数


例如:
G 为 k n; 码字 c 长度为n; 一个码字的校验部分p的长度为 (n - k)
通信与信息工程学院
信道编码技术
校验矩阵

校验矩阵H 定义为:
GH 0
T

即：H的行 是与G的行正交的 即 是与G的行 交的 利用该矩阵可以检验一个接 收到的码字r是否是有效码字
dGHT 0 if r is a codeword s rH otherwise 0
T
对于一个系统二进制码，我 们可以从G中构造H: T In k P 如果 G P Ik then put H
其中 Ik 代表一个k k 单位矩阵
那么: 那
I n k GHT P I k PP 0 P
注意这里仍然为模2加
1 1 0 1 0 0 G 0 1 1 0 1 0 [P [ | I3] 1 0 1 0 0 1
1 0 0 1 0 1 H 0 1 0 1 1 0 0 0 1 0 1 1 1 0 0 HT 1 0 1 0 0 1 0 0 1 1 0 1 1 0 1
伴随式解码
4、接收码字的伴随式为 s rHT
1 0 0 [ [0 1 1 1 1 0] ] 1 0 1
0 0 1 0 0 1 [1 1 0] ] [ 1 0 1 1 0 1
5、查表可得，伴随式[1 1 0]所对应的错误图案为e=[0 0 0 1 0 0]，所以接收 码字纠错后为 ’ r + e =[0 码字纠错后为r’= [0 1 1 0 1 0]


选出其中的三个作为基底:
000000, 101001 110100, , 011101 011010, 110011 1 = 1 1 1 0 1 以上加法为模2加（或异或） 因此，所有的码字都可以由这 些码字的和来生成，通过乘以 1或0

注意信息比特会出现在码字中
即该编码为系统码
这是因为生成矩阵包含一个单位 阵I:
G P I c dP I p d

我们可以通过给生成矩阵G相 乘信息比特向量d来得到任意的 码字c :
注意使用模2加
b1 c dG 1 1 0 b2 1 b1 1 b2 0 b3 b3 110100 011010 000000 101110
s rHT dG e HT dGH T eHT eHT
这样，译码纠错的步骤就可以总结为： 1、找出生成矩阵； 找出校验 阵； 2、找出校验矩阵； 3、列出错误图案与伴随式表格； 4、列出接收码字的伴随式； 5 纠错 5、纠错； 下面来看一个例题。
可见，伴随式仅取决于错误图案。 伴随式 案 由此就可以列出一个错误图案及其 对应的伴随式的表格，然后我们对每 个接收到的信号找到对应的伴随式， 查询错误图案，来纠正其中的传输错 误
纠错只有在加入校验比特后采用可能
汉明距离是指两个码字之间相同位置 明 离是指两个码字 间相同位置 上的比特信息不同的位置数之和 使用纠错码的其他应用:
– 拼写错误 – 电视画面噪声

编码后可能的传输信号称之为 码字
通信与信息工程学院
信道编码技术
汉明距离
00000 2 4 3 3 4 4 3 3 00110 1 01110
思考：1、伴随式与错误图案是一一对应的关系吗？Why？ 2 为什么只是选择了错误图案[000100]，而没有选择错误图案[110000]来纠错？ 2、为什么只是选择了错误图案[000100]，而没有选择错误图案[110000]来纠错？
信道编码技术
4.1.3 循环码
信道编码技术
循环码
信道编码技术
一种编码可以检测 dmin - 1 个 错误比特, 同时纠正每个码 字中的dmin/2 个错误比特。 个错误比特
d min d min 2
最佳编码是所有码字间均具 有最大距离
3 11101
10011
最小汉明距离dmin 是任意两 个码字间汉明距离的最小值
越长的码字意味着越多的错 误比特可以被纠正过来 代价是: 代价是 – 传输信息速率下降, – 复杂度增加
0 0 0 0 0 1 0 0 0 0 1
1 0 0 1 0 1 1 1 0 1 0
0 1 0 1 1 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 1
11 12 13 14 15 16 17 18 19 20 21
0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
– 卷积码: 编码序列取决于数个分组
• 码的表示方式(n,k,m),第三个数通 常表示的是约束长度
从这些码字中不能直接读出哪些是信息 这些码字中 能直接读出哪些是信息 比特。
线性码
–任意两个码字的和（模2加）是另一个 码字 –码字中包含全0码
编码速率- 每个码字中信息比特数 所占的百分比---》k/n
信道编码技术
4.1.2 FEC编码原理
加入冗余，使得原始信号在传 输中被破坏后仍然能够被恢复 出来
例如： 2 比特二进制信息，我们加 入校验比特
信息比特：校验比特 0 0 : 0 0 0 0 1 : 1 1 0 1 0 : 0 1 1 1 1 : 1 0 1
假设接收码字为0 0 1 1 0 – 可以检测出有错误发生- 接收码字 不在可能传输的码字范围内 – 传输错误可以通过选择具有“最 近距离”的码字纠正过来 01110
系统码、非系统码
–系统码：码字中明显地包含信息比特
0000 000, 0010 111, 0101 110, 0111 001 1001 011 , 1011 100, 1100 101, 1110 010 –非系统码：码字中无对应的信息比特 例如，将下列信息比特映射为四种码字:
00: 00 01: 10: 11: 00000 11101 00111 11010
Source coding to compress d data
信道 编码 编
Error-control coding to permit robust transmission of data
Error-detection coding allows re-transmission of erroneous data
信道编码技术
伴随式解码
伴随式可以被用来解码：当传输发生 错误时，一个接收到的码字r可以表 示成一个有效码字c和一个错误错误 G e 图案e 的和：r c e dG 其中 c=(co,c1,…,cn-1),e=(e0,e1,…,en-1) ci , ei∈(0,1) 这样，伴随式可以写为: