Hamming Codes Solutions

COMP 222 Quick Quiz #3: Hamming Codes Solutions Problem 1 Given the 8-bit data word 0x57, compute the 12-bit code word. Expand data word to binary and place in table 0 1 0 1 8 7 6 5 0 4 1 3 1 2 1 1 Calculate check bits (xor of indicated data bits) Bit 1 12457 Xor(1 1 0 1 1) = 0 Bit 2 13467 Xor(1 1 0 0 1) = 1 Bit 3 2348 Xor(1 1 0 0) = 0 Bit 4 5678 Xor(1 0 1 0) = 0 Reposition original data bits and calculated check bits into 12-bit code word. 0 (D8) 1 (D7) 0 (D6) 1 (D5) 0 (C4) 0 (D4) 1 (D3) 1 (D2) 12 11 10 9 8 7 6 5 0 (C3) 4 1 (D1) 3 1 (C2) 2 0 (C1) 1 Code word in hex: _0101 0011 0110 = 53616_ Problem 2 Given the 8-bit data word 0xAB, compute the 12-bit code word. Expand data word to binary and place in table (0xAB = 1010 1011) 1 0 1 0 1 8 7 6 5 4 0 3 1 2 1 1 Calculate check bits (xor of indicated data bits) Bit 1 12457 Xor(1 1 1 0 0) = 1 Bit 2 13467 Xor(1 0 1 1 0) = 1 Bit 3 2348 Xor(1 0 1 1) = 1 Bit 4 5678 Xor(0 1 0 1) = 0 Reposition original data bits and calculated check bits into 12-bit code word. 1 (D8) 0 (D7) 1 (D6) 0 (D5) 0 (C4) 1 (D4) 0 (D3) 1 (D2) 12 11 10 9 8 7 6 5 Code word in hex: _1010 0101 1111 = A5F16_ 1 (C3) 4 1 (D1) 3 1 (C2) 2 1 (C1) 1 Problem 3 Given 12-bit code word 0x7C1, extract the data bits, determine bit error if any, and if so, correct it. Expand 12-bit code word into binary. 0x7C1 = 0111 1100 0001 0 (D8) 1 (D7) 1 (D6) 1 (D5) 1 (C4) 1 (D4) 0 (D3) 12 11 10 9 8 7 6 Extract data bits from code word into table. 0 1 1 1 8 7 6 5 0 (D2) 5 1 4 0 (C3) 4 0 3 0 (D1) 3 0 (C2) 2 0 2 1 (C1) 1 0 1 Recalculate check bits (xor of indicated data bits) Bit 1 12457 Xor(0 0 1 1 1) = 1 Bit 2 13467 Xor(0 0 1 1 1) = 1 Bit 3 2348 Xor(0 0 1 0) = 1 Bit 4 5678 Xor(1 1 1 0) = 1 Compare stored check bits with recalculated check bits Bit 4 Bit 3 Original 1 0 Recalculated 1 1 Xor 0 1 Bit 2 0 1 1 Bit 1 1 1 0 Code Word Bit In Error: _0110 = 6_ = Data Bit In Error _3_ Corrected Data Word in Hex: _0111 1000 = 0111 1100 = 7C16_ (same as extracted data word if no error) Problem 4 Given 12-bit code word 0x9DD, extract the data bits, determine bit error if any, and if so, correct it. Expand 12-bit code word into binary. 1 0 0 1 12 11 10 9 1 8 1 7 Extract data bits from code word into table. 1 0 0 1 8 7 6 5 0 6 1 4 1 5 1 4 0 3 1 3 0 2 1 2 1 1 Recalculate check bits (xor of indicated data bits) Bit 1 12457 Xor(1 1 1 1 0) = 0 Bit 2 13467 Xor(1 0 1 0 0) = 0 Bit 3 2348 Xor(1 0 1 1) = 1 Bit 4 5678 Xor(1 0 0 1) = 0 Compare stored check bits with recalculated check bits Bit 4 Bit 3 Original 1 1 Recalculated 0 1 Xor 1 0 Code Word Bit In Error: _1001 = 9_ = Data Bit In Error _5_ Corrected Data Word in Hex: _1001 1011 = 1000 1011 = 8B16_ (same as extracted data word if no error) Bit 2 0 0 0 1 1 Bit 1 1 0 1