2024年4月14日发(作者：)
汉明码(Hamming)的编码和译码算法
本文所讨论的汉明码是一种性能良好的码，它是在纠错编码的实践中较早发
现的一类具有纠单个错误能力的纠错码，在通信和计算机工程中都有应用。例如：
在“计算机组成原理”课程中，我们知道当计算机存储或移动数据时，可能会产
生数据位错误，这时可以利用汉明码来检测并纠错。简单的说，汉明码是一个错
误校验码码集，由Bell实验室的g发明，因此定名为汉明码。如果
对汉明码作进一步推广，就得出了能纠正多个错误的纠错码，其中最典型的是
BCH码，而且汉明码是只纠1bit错误的BCH码，可将它们都归纳到循环码中。
各种码之间的大致关系显示如下。
一、 汉明码的编码算法
输入：信源消息u（消息分组u）
输出：码字v
处理：
信源输出为一系列二进制数字0和1。在分组码中，这些二进制信息序列分成
固定长度的消息分组（message blocks）。每个消息分组记为u，由k个信息位
组成。因此共有2
k
种不同的消息。编码器按照一定的规则将输入的消息u转换为
二进制n维向量v，这里n >k。此n维向量v就叫做消息u的码字（codeword）或码
向量（code vector）。 因此，对应于2
k
种不同的消息，也有2
k
种码字。这2
k
个
码字的集合就叫一个分组码（block code）。若一个分组码可用，2
k
个码字必须
各不相同。因此，消息u和码字v存在一一对应关系。由于n符号输出码字只取决
于对应的k比特输入消息，即每个消息是独立编码的，从而编码器是无记忆的，
且可用组合逻辑电路来实现。
定义：一个长度为n，有2
k
个码字的分组码，当且仅当其2
k
个码字构成域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为：
1
0
G =
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1
，
0
1
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1
，
0
1
1
0
(v
0
,v
1
,v
2
,v
3
,v
4
,v
5
,v
6
) =(u
0
,u
1
,u
2
,u
3
) ·
0
0
所以我们有：
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
,
发布者：admin，转转请注明出处：http://www.yc00.com/web/1713077477a2178388.html
评论列表（0条）