Question

Let us consider applications of parity checks in error correction codes. (a) A Mind at Play: How Claude Shannon Invented the Information Age is a biography of Shannon, who is generally considered the architect of the information age. The ISBN-10 code for the book can be obtained by removing the prefix 978 from its ISBN13 code and then recalculating the check digit (the last digit). Recall that the 10 digits for the ISBN-10 code satisfy X 10 i=1 ixi = 0 mod 11, whereas the 13 digits for the ISBN-13 code satisfy x1 + 3x2 + x3 + 3x4 + ... = 0 mod 10 You are given 978-147676?690 as the ISBN-13 code. Please find the missing digit, and then derive the corresponding ISBN-10 version. (b) Please explain that if a (15,11)-Hamming code is used but the channel makes 2 or more errors, the decoder, using minimum distance decoding, is always wrong. (c) Consider a (15,11)-Hamming code you just designed in the practice exam, with syndromes designed to indicate bit error positions. Say we now extend each 15-bit codeword by one more parity check, x16, such that x16 = P15 i=1 xi mod 2. (c1) Please explain whether it is still useful to use the four syndromes defined for the original (15,11) code to check for single bit errors. (Hint: Consider which bit error positions the four syndromes can detect. You care most about the data bits.) (c2) Write down any additional syndrome(s) you would add. If not, please briefly explain why. (c3) What is the rate of this new 16-bit code? (1 point only here. Don’t overthink!) (c4) How many errors can we correct now with the 16-bit code? Briefly explain whether adding this 16th bit is worthwhile. (d) If we were to design a Hamming code with 5 check bits per codeword, how many data bits can we have per codeword? Please briefly explain why. What is the minimum distance of this code? Can we now correct 2 errors?

Answer 1