最详细的“ECC-汉明码”原理讲解

  • Post author:
  • Post category:其他

前言

Error Correcting Code (ECC)校验码。

ECC校验技术最常用的就是“汉明码(Hamming Code)”

汉明码可以实现–1-bit纠错2-bit检错

“1-bit纠错,即知道哪一bit错了,并纠正它”

“2-bit检错,即知道传输的码字中错了2-bit,但不知道哪2-bit错了。这种情况,数据只能重传”

大部分都讲了“1-bit纠错”,我们讨论“1-bit纠错2-bit检错

汉明码原理

数据位宽和校验码位宽的关系

汉明码编码中,数据位宽和校验码位宽的关系,如下表所示:

数据位宽(n)

校验码位宽(k)

n=1

3

2 <= n <= 4

4

5 <= n <= 11

5

12 <= n <= 26

6

27 <= n <= 57

7

58 <= n <= 120

8

121 <= n <= 247

9

248 <= n <= 502

10

503 <= n <= 1013

11

1014 <= n <= 2036

12

2037 <= n <= 4083

13

4084 <= n <= 8178

14

汉明码编码规则

以4-bit的数据码为例,假设数据码为:D3,D2,D1,D0。

从上表可知,校验码的位宽为“4-bit”,假设为:PP,P2,P1,P0

校验码的位置,在H=2^k的位置上(k=0,1,2),而最后一个校验码”PP“在最后一个位置,如下表所示。

H8

(1000)

H7

(0111)

H6

(0110)

H5

(0101)

H4

(0100)=2^2

H3

(0011)

H2

(0010)=2^1

H1

(0001)=2^0

PP

D3

D2

D1

P2

D0

P1

P0

求校验码的值

P0的值,为H=xxx1位置上所有数据码的“异或值”,即P0=D0D1D3。

P1的值,为H=xx1x位置上所有数据码的“异或值”,即P1=D0D2D3。

P2的值,为H=x1xx位置上所有数据码的“异或值”,即P2=D1D2D3。

PP的值,为前面所有数据的偶校验,即PP=P0P1D1P2D1D2D3。

按照上述方法,可以计算出对应数据的校验码,即chkbits = {PP,P2,P1,P0}

数据传输时,一般按照“PP,P2,P1,P0,D3,D2,D1,D0”的顺序传输到内存中。

解码规则

当接收端从内存中读出“D3,D2,D1,D0”的数据后,按照上节的编码规则,重新计算出新的校验码。

得到新的4-bit校验码,如:PP’,P2’,P1’,P0′,即chkbits’ = {PP’,P2’,P1’,P0′}

对chkbits 和chkbits ‘进行异或,得到4-bit数据syndrome,即syndrome= chkbitschkbits’

校验规则

  1. 当syndrome[3] == 0时,

  1. 如果syndrome[2:0] == 0,则表示传输的数据中H1~H8位置中,没有任何错误。

  1. syndrome[2:0] != 0,则表示传输的数据H1~H8位置中,存在两个错误,需要重传数据。

  1. 当syndrome[3] == 1时,

  1. syndrome[2:0] > (校验码位宽+数据位宽),则传输的数据无效。

  1. syndrome[2:0] <(校验码位宽+数据位宽),则表示发生了1-bit错误,且错误位置在H[syndrome[2:0]]位置,只需要将对应位置的数据取反即可。

  1. 例如:如果syndrome[2:0] = 3,则表示H3位置的数据发生了错误,即D0传输过程中发生了错误,需要将D0取反。

注意:当数据错误1-bit和错误3-bit的结果是一样的,这种情况是无法区分的。

相关文献说,在通信系统中的一个传输块中,错误1-bit的概率很低,同时错误2-bit的概率更低,那同时错误3-bit以上的概率就更~更低了。但现在通信传输速度越来越高,每秒几十G的速率,同时错多bit的概率还是很高的。

但汉明码作为校验码,因其简单高效以及低成本的特点,依然是通信传输系统中常用的校验手段。


版权声明:本文为qq_37708525原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。