?
由于HS的第1列和第5列相同而线性相关。 dmin?2。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
简单码例（4/4）──例11.19续
? 不同生成矩阵构造的码字和对偶码的码字见下表。 表11.4.1 (5,3)线性分组码
u G生成码字 GS生成码字 对偶码的码字 000 001 010 011 100 101 110 111 00000 11010 01011 10001 10110 01100 11101 00111 00000 00111 01011 01100 10001 10110 11010 11101 00000 11101 01110 10011 汉明码（1/8）
? 汉明（Richard W. Hamming）1950年首次发现的一类纠
正单个错误的线性分组码。
? 二元m阶汉明码C?H(2,m)：校验阵H?H(2,m)是
以全部二元非零m维向量为列向量的矩阵 ? 二元m阶汉明码的基本特性有：
? n?2?1，k?2?1?m，r?m，正整数m?3。 ? Rc?1?m(2m?1)。 ? dmin?3，tc?1。 ? 是完备码，即，
mm??ni??1?n?2i?0tc?1m?2n?k?2r
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
汉明码（2/8）──二元码基本特性续
? 满足如下递归关系：
?00111?0?,m?2 H(2,m?1)??H(2,m)??H(2,m)0????? 记Ai为重量i的码字的个数，则二元汉明码的重量
分布多项式为，
1?n2(n?1)2?A(x)??Aix??1?x??n?1?x?1?x????n?1i?0
1?n(n?1)2(n?1)2??1?x??n?1?x?1?x????n?1?in??＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
汉明码（3/8）──二元码基本特性续
? 在汉明码H(2,m)的一致校验矩阵H(2,m)构造中，每
一种不同的非零列向量的排列顺序或者对已有H(2,m)11-26
的任意列初等置换，均获得不同形式的校验矩阵H?(2,m)。
? 不同形式的H(2,m)所定义的码在编码映射意义上虽然
不同，但是它们都具有相同的上述汉明码的基本特性，称为是在码结构参数意义上等价的汉明码。
? 存在满足汉明码前三个基本特性的却不等价为汉明码
的非线性分组码。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
汉明码（4/8）
例11.20 ?n,k,d???15,11,3?二元汉明码的两种等价的校
验矩阵分别为，
?10001001101??010000100011010100101001110010111?H(2,4)??01110101111?
10111?????101010101010101?H?(2,4)???011001100110011??000000101010100101010111111111?
???汉明码（5/8）
例11.21 二元汉明码可以推广到多元汉明码。例如一个三元3阶(13,10,3)汉明码的一致校验矩阵为H(3,3)，
?0000111111111?H(3,3)???0111000111222?
?1012012012012??＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
汉明码（6/8）
例11.22 二元3阶汉明码是一个(7,4,3)线性分组码。
?1110100??1000101?H(3)???0111010?, G(3)???0100111??1101001???0010110? ?0001011??＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
汉明码（7/8）──例11.22续
图11.4.1 二元（7,4）汉明码编码电路原理图
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
4-27
汉明码（8/8）──例11.22续
对于消息向量u?(u0u1u2u3)，等价的编码方程和编码
联立方程组分别为，
(c0c1c2c3c4c5c6)?(u0u1u2u3)G(3)
?ci?ui, i?0,1,2,3?c?u?u?u?4012 ?c?u?u?u123?5??c6?u0?u1?u3＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
码的变形、变型与组合
? 码的基本变形分为三类六种：
（1）扩展（extending）与打孔（puncturing）。
（2）增广（augmenting）与删信（expunging或expurgating）。 （3）延长（lengthening）与缩短（shortening）。 ? 码的常见组合有： （1）乘积（product）。 （2）交织（interleaving）。 （3）级连（concatenating）。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
全校验位扩展
? 码的全校验位扩展：增加一位总偶校验位c使得，
?c??c0??
??c2m?2
?n,k,d???n?1,k,d??。
? 若d为奇数，则d?d?1。 ? 增加最小码距的扩展一次有效。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
码的乘积－乘积码（1/2）
? 码的乘积：对消息阵列采用相同或不同的纠错码（称为
子码）分别作消息行和消息列的编码。 ? 乘积分规则与不规则两种，见图11.4.2。
? 对列子码?n1,k1,d1?和行子码?n2,k2,d2?的规则乘积
有d*?d1d2。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
码的乘积－乘积码（2/2）
11-28
k2 r2 k1 消息位 行校验（位） r1
列校验（位） 行校验位的列校验 规则乘积码 k2 r2 k1 消息位 行校验（位） r1
列校验（位） 非规则乘积码
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
码的级连－级连码（1/2）
? 码的级连：对编码后的码字再进行一次（或多次）编码。
首次消息编码所用码称为外码，其后所用码称为内码。 ? 二次级连获得?Nn,Kk,d??分组码，并且d??Dd，D
外码最小码距，d内码最小码距。
? 级连是既纠正随机差错又纠正突发差错的有效方法。采用RS码为外码，卷积码或Turbo码为内码成为工业标准。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
码的级连－级连码（2/2）
例11.23 图11.4.3外码是八元?4,2?码，内码二元?5,3?码，
级联后为二元?20,6?码。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
码的交织（1/2）
? 码的交织或交织编码：改变多个码字或者一个码字中各
码元的传送顺序。 ? 交织编码分为分组交织和卷积交织两种基本类型。
? 典型的分组交织过程见图11.4.4所示。
D个n长码字作为D?n阵列的D个行向量，交织码字则是阵列的n个
4-29
12列向量a??,a??,n,a??，信道传送顺序为递增列序。参
数D称为交织深度。 ? 分组交织不改变码率。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
码的交织（2/2）
? 如果交织编码所用的?n,k,d?码可以纠正t个随机差
错，那么交织深度为D的交织编码可以纠正小于等于bmax?D?t长的连续差错或突发差错。 ? 交织码是目前最为有效的纠正突发差错的码。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
LDPC码（1/3）
? Gallager1962年提出，Mackay等人1996年通过置信传
播BP (Belief propagation)的迭代译码算法“再发现”为逼近香农限的好码。
? 由行秩为r?n-k、大小为m?n (m?r)稀疏校验矩
阵H定义。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
LDPC码（2/3）
? 校验关系的二分图（Bipartite Graph）表示。
? 消息或变量节点表示码元或接收符号。 ? 校验节点表示检验方程。
? 消息节点与校验节点之间的连接边表示该码元参与该检验方程的校验。
? 环：始于某个消息节点，经与其它校验节点或消息节点的边的连接又回至始发消息节点的边序列。
? 环长：环中的边数。最小环长（Girth）：最小环长。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
LDPC码（3/3）
? 二元?n,?,??规则LDPC码：
? （规则性）H的每行元素中恒有?个“1”，每列中恒有?个“1”；
? （低密度性）H是稀疏矩阵，即?n和?m均很小（如小于0.1）；
? 无长4环当且仅当H的任意两行（或任意两列）在相
同列（或行）位置上的元素均为“1”的个数不超过1。 ? 性能良好的LDPC码必有最小环长大于等于6。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
11-30