CSC264 Comp Org/Arch - Hamming Handout

Hamming Codes

SED/SEC Code for Four Data Bits

Set the check bits so that each circle has even parity.

After the check bits are calculated, the word (including check bits and data bits) is stored in memory, with the bits in the following order:

Bit Number	7	6	5	4	3	2	1
Contents	D4	D3	D2	C4	D1	C2	C1

Or you can calculate the check bits without the circles, using the following table. Again, set each check bit so that the whole group has even parity. Check bits are calculated using the following data bits:

Check Bit	Data Bits
C1	D1 D2 D4
C2	D1 D3 D4
C4	D2 D3 D4

When retrieving a word, put the check bits and data bits back in the circles. If any circle has odd parity, or multiple circles have odd parity, the error is in the one bit that, if changed, will make all circles have even parity.

DED/SEC Code for Four Data Bits

Set check bits C1, C2, C4, so that each circle has even parity. Then set C8 so that the entire diagram has even parity.

The bits are stored in the following order:

Bit Number	8	7	6	5	4	3	2	1
Contents	C8	D4	D3	D2	C4	D1	C2	C1

Check Bit	Data Bits
C1	D1 D2 D4
C2	D1 D3 D4
C4	D2 D3 D4
C8	C1 C2 C4 D1 D2 D3 D4

If a bit is changed so that all circles have even parity, but C8 makes the entire diagram have odd parity, then there are two errors. The code is not strong enough to determine the location of the errors, so it reports that there are two errors.

If all circles have even parity when the word is retrieved, without changing any bits, but C8 makes the entire diagram have odd parity, then there is an error in C8.

SED/SEC Code for Eight Data Bits

The bits are stored in the following order:

Bit Number	12	11	10	9	8	7	6	5	4	3	2	1
Contents	D8	D7	D6	D5	C8	D4	D3	D2	C4	D1	C2	C1

Check bits are calculated using the following data bits. Each check bit is set so the entire group has even parity.

Check Bit	Data Bits
C1	D1 D2 D4 D5 D7
C2	D1 D3 D4 D6 D7
C4	D2 D3 D4 D8
C8	D5 D6 D7 D8

When a word is retrieved, the check bits are recalculated using the retrieved data bits. Then the recalculated check bits and the retrieved check bits are compared using xor to create the syndrome:

      C8 C4 C2 C1 (recalculated)
   ⊕ C8 C4 C2 C1 (retrieved)
   --------------
      S4 S3 S2 S1

If the recalculated and retrieved check bits are the same, then the syndrome will be 0, which means there is no error. Otherwise the syndrome S4 S3 S2 S1 gives the position (1 through 12), in binary, of the error.