Hamming Code Generator (Verilog)

Created: 2016-12-28 Wed

Modified: 2016-12-29 Thu

From wikipedia

The following general algorithm generates a single-error correcting (SEC) code for any number of bits.

  1. Number the bits starting from 1: bit 1, 2, 3, 4, 5, etc.
  2. Write the bit numbers in binary: 1, 10, 11, 100, 101, etc.
  3. All bit positions that are powers of two (have only one 1 bit in the binary form of their position) are parity bits: 1, 2, 4, 8, etc. (1, 10, 100, 1000)
  4. All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.
  5. Each data bit is included in a unique set of 2 or more parity bits, as determined by the binary form of its bit position.
    1. Parity bit 1 covers all bit positions which have the least significant bit set: bit 1 (the parity bit itself), 3, 5, 7, 9, etc.
    2. Parity bit 2 covers all bit positions which have the second least significant bit set: bit 2 (the parity bit itself), 3, 6, 7, 10, 11, etc.
    3. Parity bit 4 covers all bit positions which have the third least significant bit set: bits 4–7, 12–15, 20–23, etc.
    4. Parity bit 8 covers all bit positions which have the fourth least significant bit set: bits 8–15, 24–31, 40–47, etc.
    5. In general each parity bit covers all bits where the bitwise AND of the parity position and the bit position is non-zero.

The form of the parity is irrelevant. Even parity is simpler from the perspective of theoretical mathematics, but there is no difference in practice.

Bit position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Encoded data bits p1 p2 d1 p4 d2 d3 d4 p8 d5 d6 d7 d8 d9 d10 d11 p16 d12 d13 d14 d15
Parity
bit
coverage
p1 X X X X X X X X X X
p2 X X X X X X X X X X
p4 X X X X X X X X X
p8 X X X X X X X X
p16 X X X X X

Practice

The hamming code to contain 11-bit is [15,11], and it can detect and correct single-bit error. But since we have 16-bit bandwidth (2-byte), there is no meaning to waste the extra bit. So adding an extra parity bit to extendto single-error-correction and double-error-detection is easy enough. The extra parity bit is just a sum of all the codeword (data and parity) bits. Obviously, using extra parity bit is very timing critical.

The following table, parity bit coverage, determins how to calculate parity.

Parity index Message index
0 0, 1, 3, 4, 6, 8, 10
1 0, 2, 3, 5, 6, 9, 10
2 1, 2, 3, 7, 8, 9, 10
3 4, 5, 6, 7, 8, 9, 10
4 (if SECDED) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, p0, p1, p2, p3

The following table, message bit to parity, determins how to correct error in message.

Message index Parity index
0 0, 1
1 0, 2
2 1, 2
3 0, 1, 2
4 0, 3
5 1, 3
6 0, 1, 3
7 2, 3
8 0, 2, 3
9 1, 2, 3
10 0, 1, 2, 3

Example

http://www.ecs.umass.edu/ece/koren/FaultTolerantSystems/simulator/Hamming/HammingCodes.html

(7,4) (8,4) (15,11) (16,11)
Data 0101 0101 01011010011 01011010011
Parity 101 0 101 0110 0 0110
Data (recv) 0101 0100 01011010011 01011011111
Parity (recv) 101 0 101 0100 0 0110
Parity (dec) 101 1 110 0110 1 0111
Error 0 1 in data 1 in parity 2 in data
Syndrome 0000

000

0001

0 000

00000000000 0010
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s