汉明码的编码和译码算法
- 格式：pdf
- 大小：560.81 KB
- 文档页数：16
汉明码的编码和译码算法
汉明码(Hamming)的编码和译码算法
本⽂所讨论的汉明码是⼀种性能良好的码，它是在纠错编码的实践中较早发现的⼀类具有纠单个错误能⼒的纠错码，在通信和计算机⼯程中都有应⽤。例如：在“计算机组成原理”课程中，我们知道当计算机存储或移动数据时，可能会产⽣数据位错误，这时可以利⽤汉明码来检测并纠错。简单的说，汉明码是⼀个错误校验码码集，由Bell实验室的R.W.Hamming发明，因此定名为汉明码。如果对汉明码作进⼀步推⼴，就得出了能纠正多个错误的纠错码，其中最典型的是BCH码，⽽且汉明码是只纠1bit错误的BCH码，可将它们都归纳到循环码中。各种码之间的⼤致关系显⽰如下。
⼀、汉明码的编码算法
输⼊：信源消息u（消息分组u）
输出：码字v
处理：
信源输出为⼀系列⼆进制数字0和1。在分组码中，这些⼆进制信息序列分成固定长度的消息分组（message blocks）。每个消息分组记为u，由k个信息位组成。因此共有2k种不同的消息。编码器按照⼀定的规则将输⼊的消息u转换为
⼆进制n 维向量v ，这⾥n >k 。此n 维向量v 就叫做消息u 的码字（codeword ）或码向量（code vector ）。 因此，对应于2k种不同的消息，也有2k 种码字。这2k 个码字的集合就叫⼀个分组码（block code ）。若⼀个分组码可⽤，2k 个码字必须各不相同。因此，消息u 和码字v 存在⼀⼀对应关系。由于n 符号输出码字只取决于对应的k ⽐特输⼊消息，即每个消息是独⽴编码的，从⽽编码器是⽆记忆的，且可⽤组合逻辑电路来实现。
定义：⼀个长度为n ，有2k 个码字的分组码，当且仅当其2k 个码字构成域GF(2)
上所有n 维向量组成的向量空间的⼀个K 维⼦空间时被称为线性（linear ）(n, k)码。
汉明码（n ，k ，d ）就是线性分组(n, k)码的⼀种。其编码算法即为使⽤⽣成
矩阵G ：v = u ·G 。
例1-1：针对汉明码Hamming (7,4,3)⽽⾔，u =(u 0,u 1,u 2,u 3)，v =(v 0,v 1,v 2,v 3,v 4,v 5,v 6)，则我们有 (v 0,v 1,v 2,v 3,v 4,v 5,v 6)=(u 0,u 1,u 2,u 3) ·G 。 Hamming (7,4,3) 的⽣成矩阵G 为：
G =
11
1
01101001
1100101010001， (v 0,v 1,v 2,v 3,v 4,v 5,v 6) =(u 0,u 1,u 2,u 3) ·
11
1
01101001
110010
1010001， 所以我们有： v 0= u 0, v 1= u 1, v 2= u 2, v 3= u 3, v 4= u 0+u 1+u 2, v 5= u 1+u 2+u 3, v 6=u 0+u 1+u 3,
例如u =1101，对应→v =1101001。处理完毕。■
其他汉明码照此处理，甚⾄其他线性分组(n, k)码都照此办理即可。
线性分组(n, k)码的校正⼦（伴随式）有2n-k 个，设该码的纠错能⼒为t ，那么
重量⼩于或者等于t 的所有错误模式（图样）都要有唯⼀的校正⼦（伴随式）与之对应，因⽽，对于⼆进制(n, k)码，有汉明限：2n-k
≥∑=???? ??t
i i n 0 ，当2n-k =∑=
t
i i n 0时，
(n, k)码称为完备码（Perfect Code ）。完备码的伴随式得到了充分的利⽤，不存在解码不唯⼀的问题，然⽽完备码不⼀定是纠错能⼒强的码，因为它的最⼩距离d min 未必最⼤。完备码也是稀少的，已知的⼆进制完备码有t=1的汉明码（HammingCode ）和t=3的格雷码（Golay Code ），以及n 为奇数的简单重复(n,1)码。三进制完备码有t=2的（11,6,5）格雷码。
纠错能⼒t=1的完备码统称为汉明码。由定义可知，(n, k)汉明码应当满⾜下列条件：2n-k =1+n ，令校验位长m=n-k ，那么容易知道：n=2m -1, k=2m -1-m, d min =3 。
汉明码的校验矩阵H 具有特殊的性质：它的m 维列向量正好是除零向量以外的所有可能的向量组合，共有2m -1个，恰好构成了H 矩阵的列数n 。
格雷码通常是指线性分组（23,12）码，最⼩距离d min =7，纠错能⼒ t=3。由于223-12
=2048=1+
+ + 323223123 ，所以格雷码是完备码，其码重（码的重
量）分布见下⾯表0-1。
表0-1 格雷码的码重分布
备注：1、汉明码的⽣成矩阵：
Hamming (7,4,3) 的⽣成矩阵G
11
1
011010011100101010001 Hamming (17,12,3) 的⽣成矩阵G
10
1
1
010101
001011
101101
010111
100011
111001
011101
001111
101111
111111
11011
1 Hamming (13,9,3) 的⽣成矩阵G
11
1
01101
00111
11011
1010101011
11101
01111
1111
1
Hamming (15,11,3) 的⽣成矩阵G
11
1
01101
00111
11011
10101
01011
11101
01111
11111
10111
1001
1 Hamming (16,11,4) 的⽣成矩阵G
11
1
1
101101
100111
011011
110101
101011
011101
001111
111111
01011111001
1
2、除了分组码之外，还有卷积码。卷积码编码器同样接受k ⽐特分组的信息序列u ，并产⽣n 符号组的编码序列（码序列）v（卷积码编码中，符号u 和v ⽤来表⽰分组的序列⽽⾮单个分组）。但是，每⼀个编码分组不仅取决于当前单位时间对应的k⽐特消息组，⽽且与前m 个消息组有关。此时，编码器的存储级数(memory order)为m 。编码器所产⽣的所有可能的输出编码序列的集合构成了⼀个码。⽐值R=k/n 称为码率（code rate ）。由于编码器有存储单元，因⽽必须采⽤时序逻辑电路实现。
⼆、汉明码的译码算法
输⼊：接收向量r
输出：译码所得码字v*
处理：
考虑⼀个（n，k）线性分组码，其⽣成矩阵为G，奇偶校验矩阵为H。令v=( v0,v1, … ,v n-1)表⽰要通过有噪信道传输的码字，r = (r0,r1, … ,r n-1)为信道输出端接收到的码字。由于信道中的噪声，r可能与v不同。向量和e= r +v=( e0,e1,…,e n-1)是⼀个n维向量，其中r i≠v i时，e i=1，⽽r i= v i时，e i=0。该n维向量e称为差错向量(error vector)或错误模式或错误图样（error pattern）, 它直接指出接收向量r不同于传输码字v的位置。e中的1表⽰由于信道噪声引起的传输差错（transmission errors）。
接收向量r的译码包括如下三个步骤：1、计算r的校正⼦（伴随式）s = r·H T；
2、确定校正⼦（伴随式）s = r·H T对应的陪集⾸e l，于是e l被假定为由信道
引起的错误模式（错误图样）；3、将接收向量r译为码字v*=r+ e l。
上述译码⽅案被称为校正⼦（伴随式）译码（syndrome decoding）或查表译码（table lookup decoding）。
例2-1：Hamming (7,4,3) 的⽣成矩阵G = [ I k P ]k ×n=
11
101101001
1100101010001， 则奇偶校验矩阵H 为
H = [ P T I n-k ](n-k)×n =
10
1
1
1
0101110
0010111，这⾥n=7, k=3。
该码有23=8个陪集：
假设传输码字为v =1110100，接收向量为r =0110100（错1位），其校正⼦s =r ·H T =101, 对应e =1000000，v *=r + e=1110100，所以译码正确！
假设传输码字为v =1110100，接收向量为r =0110000（错2位），其校正⼦s = r ·H T =001, 对应e =0000001，v *=r +e=0110101，所以译码错误！
可以看出：汉明码Hamming (7,4,3)可以纠正含单个差错的错误模式或者检测出含两个差错的错误模式（⽽不能纠正含两个或两个以上差错的错误模式）。
例2-2：Hamming (17,12,3) 的⽣成矩阵G = [ I k P ]k ×n =
10
11
010101
001011
101101
010111
100011
111001
011101
001111
101111
111111
11011
1
奇偶校验矩阵H = [ P T I n-k ](n-k)×n =
11
1
1
1
1
1
1
1
0100101100111
1011001111101
0101100111111
001011001111
该码有25=32个陪集：
