汉明码的编码和译码算法
- 格式：doc
- 大小：348.50 KB
- 文档页数：17
汉明码(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=(u0,u1,u2,u3)，v=(v0,v1,v2,v3,v4,v5,v6)，则我们有 (v0,v1,v2,v3,v4,v5,v6)=(u0,u1,u2,u3) ·G 。
Hamming (7,4,3) 的生成矩阵G为：
G =1101000011010011100101010001，
(v0,v1,v2,v3,v4,v5,v6) =(u0,u1,u2,u3) ·1101000011010011100101010001，
所以我们有：
v0= u0,
v1= u1,
v2= u2,
v3= u3,
v4= u0+u1+u2,
v5= u1+u2+u3,
v6=u0+u1+u3, 例如u=1101，对应→v=1101001。处理完毕。■
其他汉明码照此处理，甚至其他线性分组(n, k)码都照此办理即可。
线性分组(n, k)码的校正子（伴随式）有2n-k个，设该码的纠错能力为t，那么重量小于或者等于t的所有错误模式（图样）都要有唯一的校正子（伴随式）与之对应，因而，对于二进制(n, k)码，有汉明限：2n-k≥tiin0 ，当2n-k=tiin0时，
(n, k)码称为完备码（Perfect Code）。完备码的伴随式得到了充分的利用，不存在解码不唯一的问题，然而完备码不一定是纠错能力强的码，因为它的最小距离dmin未必最大。完备码也是稀少的，已知的二进制完备码有t=1的汉明码（Hamming Code）和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, dmin=3 。
汉明码的校验矩阵H具有特殊的性质：它的m维列向量正好是除零向量以外的所有可能的向量组合，共有2m-1个，恰好构成了H矩阵的列数n。
格雷码通常是指线性分组（23,12）码，最小距离dmin=7，纠错能力 t=3。由于223-12=2048=1+323223123 ，所以格雷码是完备码，其码重（码的重量）分布见下面表0-1。
表0-1 格雷码的码重分布
码重 0 7 8 11 12 15 16 23
码个数 1 253 506 1288 1288 506 253 1
备注：
1、汉明码的生成矩阵：
Hamming (7,4,3) 的生成矩阵G 1101000011010011100101010001
Hamming (17,12,3) 的生成矩阵G
101001010101001011101101010111100011111001011101001111101111111111110111
Hamming (13,9,3) 的生成矩阵G
110010110100111110111010101011111010111111111
Hamming (15,11,3) 的生成矩阵G 1100101101001111101110101010111110101111111111011110011
Hamming (16,11,4) 的生成矩阵G
111001101101100111011011110101101011011101001111111111010111110011
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, … ,vn-1)表示要通过有噪信道传输的码字，r = (r0,r1, … ,rn-1)为信道输出端接收到的码字。由于信道中的噪声，r可能与v不同。向量和e= r +v=( e0,e1,…,en-1)是一个n维向量，其中ri≠ vi时，ei=1，而ri= vi时，ei=0。该n维向量e称为差错向量(error vector)或错误模式或错误图样（error pattern）, 它直接指出接收向量r不同于传输码字v的位置。e中的1表示由于信道噪声引起的传输差错（transmission
errors）。
接收向量r的译码包括如下三个步骤：
1、 计算r的校正子（伴随式）s = r·HT；
2、 确定校正子（伴随式）s = r·HT对应的陪集首el，于是el被假定为由信道引起的错误模式（错误图样）；
3、 将接收向量r译为码字v*=r+ el 。
上述译码方案被称为校正子（伴随式）译码（syndrome decoding）或查表译码（table lookup decoding）。 输入接收向量r计算r的校正子（伴随式）s =
r·HT；确定校正子（伴随式）s=r·HT对应的陪集首el，于是el被假定为由信道引起的错误模式（错误图样）；输出：译码所得码字v*将接收向量r译为码字v* = r +
el 校正子和可纠正错误模式（陪集首）的对应表
例2-1：Hamming (7,4,3) 的生成矩阵G= [ Ik P ]k×n
=1101000011010011100101010001，
则奇偶校验矩阵H为
H = [ PT In-k ](n-k)×n=100101101011100010111，这里n=7, k=3。
该码有23=8个陪集：
校正子s 可纠正错误模式（陪集首）el
s0 s1 s2 e0 e1 e2 e3 e4 e5 e6
0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0
1 1 0 0 0 1 0 0 0 0
0 1 1 0 0 0 1 0 0 0
1 0 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 1
假设传输码字为v=1110100，接收向量为r=0110100（错1位），其校正子s=
r·HT=101, 对应e=1000000，v*=r + e=1110100，所以译码正确！
假设传输码字为v=1110100，接收向量为r=0110000（错2位），其校正子s=
r·HT=001, 对应e=0000001，v*=r + e=0110101，所以译码错误！
可以看出：汉明码Hamming (7,4,3)可以纠正含单个差错的错误模式或者检测出含两个差错的错误模式（而不能纠正含两个或两个以上差错的错误模式）。
例2-2：Hamming (17,12,3) 的生成矩阵G= [ Ik P ]k×n=
101001010101001011101101010111100011111001011101001111101111111111110111
奇偶校验矩阵H = [ PT In-k ](n-k)×n=
11001011001111010010110011110110011111010101100111111001011001111
