Important things to note to retain your sanity ---------------------------------------------- In the following Haykin refers to the 3rd Ed. of "Communication Systems" by Simon Haykin, Wiley 1994. CCG refers to the cyclic code generator Java applet program. In the lecture notes on binary linear codes the notation x_{1}x_{2}...x_{k}x_{k+1}...x_{n}, where x_{1}x_{2}...x_{k} represents the k-bit message and x_{k+1}...x_{n} represents the (n-k)-bit check-bits, implies that the bit stream is running towards the "left". That is, x_{1} is the lsb of the message and x_{k} is the msb and then the check-bits follow. However, in Haykin and in the lecture notes on cyclic codes the alternate notation b_{0}b_{1}...b_{n-k-1}m_{0}m_{1}...m_{k-1} where m_{0}m_{1}...m_{k-1} represents the k-bit message and b_{0}b_{1}...b_{n-k-1} represents the (n-k)-bit check-bits, implies that the stream is running to the "right". That is, m_{k-1} is the lsb of the message and m_{0} is the msb and then the check-bits follow. That is: x_{1} == m_{k-1} x_{2} == m_{k-2} ... x_{k} == m_{0} x_{k+1} == b_{n-k-1} ... x_{n} == b_{0} The bits are reversed!!!!! Since we will base the following analysis on the lecture notes you will need to reverse the message or codeword when comparing the Hamming linear binary code with the equivalent cyclic code. Also the CCG assumes the running "left" notation and you will need to reverse the bits when verifying the results with the lecture notes or Haykin. When comparing the parity-check matrix, H, from Haykin to the notation used in the lecture notes you will need to reverse the columns and rows. Thus the (7,4) Hamming code parity-check matrix from Haykin (pg. 684): 1 0 0 1 0 1 1 H = 0 1 0 1 1 1 0 0 0 1 0 1 1 1 is in the systematic form discussed in lectures: 1 1 1 0 1 0 0 H = 0 1 1 1 0 1 0 1 1 0 1 0 0 1 (7,4) Hamming Code Generator Polynomial --------------------------------------- (Haykin Pages: 693-696 for G(x); 683-685 for corresponding linear code) -- Enter G(x) = 1 + x^1 + x^3 (should be the default state of program) -- Select Encode and Enter the Input String: 0010 -- Use Delta Step to get the codeword: 0010110 Carefully follow how the linear-shift register is working so you understand what is happening at each clock tick when the next input-bit (from the left) is clocked into the shift register via the Encode in. The Output String will show the Input String and will then follow this by the contents of the shift register which are flushed out by the Encode out. **** So what is H for this (7,4) Hamming code (i.e. how can we verify that the above is correct)? From Haykin pg. 695 we get: 1 0 0 1 0 1 1 H = 0 1 0 1 1 1 0 0 0 1 0 1 1 1 which when reversed to our systematic form becomes: 1 1 1 0 1 0 0 H = 0 1 1 1 0 1 0 1 1 0 1 0 0 1 from which we see that the message 0010 produces the check-bits 110. -- Verify the above by carrying out the G(x) polynomial encoding methodology. In this case the message is 0100 (remember we have to reverse it!) and M(x) = x^1 and we should get C(x) = x^1 + x^2 + x^4, that is 0110100 which is the reverse of 0010110! -- Try other k=4 bit message sequences and use the CCG to generate the codewords. The codewords are listed in Table 11.1, pg. 684 from Haykin (in reverse sense of course! That is, 0010110 is listed as 0110100 for message 0100) . **** Let's try corrupting some bits. According to Haykin (pg. 692, Property 3) if we corrupt any of the parity-check bits then the syndrome should be equal to the error! Say we corrupt the 3rd bit of 0110100 to 0100100 which is the 3rd parity-check bit. What do we get? -- Select Decode and Enter the Input String: 0010010 (remember to reverse!) -- Use Delta Step to get the syndrome: 100 Carefully follow how the linear-shift register is working so you understand what is happening at each clock tick when the next input-bit (from the left) is clocked into the shift register via the Decode in. The Output String will remain empty until the Input String has been shifted into the register and then it will take on the flushed contents of the shift register through the Encode out. And the syndrome 100 tells us the 3rd bit from the left has to be corrected to give us 0010110! OK let's corrupt some message bits, say, 0010110 to 0000110 (the 3rd message bit). -- Select Decode and Enter the Input String: 0000110 -- Use Step or Delta Step to get the syndrome: 110 which matches the 3rd column of our H and hence we correct the 3rd bit to get 0010110! It works! -- Verify the above by carrying out the G(x) polynomial decoding methodology. In this case the received word is 0110000 (remember we have to reverse it!) and R(x) = x^1 + x^2 and we immediately get S(x) = x^1 + x^2, that is 011 which matches the 5th column of the Haykin parity-check matrix and will thus correct the 5th bit and we get 0110100; as expected! -- Try to corrupting a few other single-bits in selected codewords and use the CCG decoder to generate the syndrome. Does the syndrome always match the corresponding bit error column of the corresponding H? CRC for single-bit error detection ---------------------------------- If G(x) has 2 terms then it can detect all single-bit errors. -- Enter the Polynomial: 1+x -- Set the Input bits to k = 4 -- Enter the Input String: 0110 -- Use Step or Delta Step to get the 5-bit codeword -- Now corrupt on of the bits in the 5-bit codeword and decode. Is the syndrome non-zero? Try corrupting another bit. -- Now try other 4-bit messages sequences. -- Finally, repeat for different values of k. What is another name for this code? Comment on the implentation efficiency of the cyclic code shift register circuit for this particular code for any value of k (or n). The CRC-12 generator polynomial ------------------------------- -- Enter the Polynomial: 1+x+x^2+x^3+x^11+x^12 -- Set the Input bits to k = 6 -- Enter the Input String: 001011 -- Use Step or Delta Step to get the 18-bit codeword -- Select the Output String box and the Select Decode. The Output String is automatically coped to the Input String box. -- Use Step or Delta Step and show that the Output String (syndrome) is all zeros. Select and Paste the Input String so you can re-use it. -- Now try and all combinations of errors on your 18-bit codeword and generate the syndrome. Can you see why CRC codes are so powerful for error detection?