最小汉明码距和数据编码的纠错能力的关系

大家好，我是讯享网，很高兴认识大家。

最小汉明码距和数据编码的纠错能力的关系

在读《计算机组成与设计：软硬件接口》这本书的5.5 Dependable Memory Hierarchy的时候，虽然知道SEC/DED的用法，但是对下面这一段话不是很理解，最小汉明码距离位4为什么就可以correct single bit error and detect double bit errors，想了很久，然后看到一些博客的解释，才理解。
在这里插入图片描述
讯享网

minimum Hamming distance = 1

如果一组编码的码长为n，那么这组编码共可以表示2^n种符号，但这样一来这个编码就没有任何抗干扰能力，因为合法码字之间的最小汉明码距为1，任何一个符号的编码的任意一位发生错误，就变成了另外一个合法的符号编码。因此接收端也无法判断是否有错误发生。

minimum Hamming distance = 2

minimum Hamming distance = 3

如果编码的最小汉明距离为3，那么任何合法码字发生一位错误都会变成非法码字，而且距离原来的码字距离为1，而距离其他任何合法码字的最小距离为2(这样就可以很明显区分是由哪一个合法编码发生错误转化而来)，
最小汉明距离为3的编码如果发生了两位错误，也可以发现，但是不能够区分到底是一位还是两位，因为存在一个合法的编码与这个错了两位的数据的汉明距离为1，所以接收端并不能分辨到底是什么情况，只能都当成一位的错误去修正。但是如果试图纠正这个错误就会产生新的错误
Hamming Error Correction Code (ECC) 就是一种最小距离为3的编码：

Of course, a parity code cannot correct errors, which Hamming wanted to do
as well as detect them. If we used a code that had a minimum distance of 3, then
any single bit error would be closer to the correct pattern than to any other valid
pattern. He came up with an easy to understand mapping of data into a distance 3
code that we call Hamming Error Correction Code (ECC) in his honor. We use extra parity bits to allow the position identification of a single error. Here are the steps to
calculate Hamming ECC

Start numbering bits from 1 on the left, contrary to the traditional
numbering of the rightmost bit being 0.

Mark all bit positions that are powers of 2 as parity bits (positions 1, 2, 4, 8,
16, …).

All other bit positions are used for data bits (positions 3, 5, 6, 7, 9, 10, 11, 12,
13, 14, 15, …).

The position of parity bit determines sequence of data bits that it checks
(Figure 5.24 shows this coverage graphically) is:
■ Bit 1 (0001two) checks bits (1,3,5,7,9,11,…), which are bits where rightmost
bit of address is 1 (0001two, 0011two, 0101two, 0111two, 1001two, 1011two,…).
■ Bit 2 (0010two) checks bits (2,3,6,7,10,11,14,15,…), which are the bits
where the second bit to the right in the address is 1.
■ Bit 4 (0100two) checks bits (4–7, 12–15, 20–23,…), which are the bits
where the third bit to the right in the address is 1.
■ Bit 8 (1000two) checks bits (8–15, 24–31, 40–47,…), which are the bits
where the fourth bit to the right in the address is 1.
Note that each data bit is covered by two or more parity bits.

Set parity bits to create even parity for each group.

minimum Hamming distance = 4

如果最小距离为4，发生一位和两位就是可以区分的，因为错了两位的数据和任意一个合法的数据的最小汉明距离都是2，而错了一位的数据离最近的合法数据的距离是1，所以它们是可区分的，但是两位错误还是不能修正。
比如汉明提出的SEC/DED：
在这里插入图片描述

在原来的基础上加上一个奇偶校验位，就把最小汉明距离又增加了1，使得它可以correct single bit error and detect double bit errors

最小汉明码距和数据编码的纠错能力的关系