1. Show that we can’t improve on the parameters in Theorem 4.1: for any integer t ≥ 0, prove that a code with minimum distance 2t + 1 cannot correct t + 1 or detect 2t + 1 errors.
2. Theorem 4.1 describes the error-detecting and error-correcting properties for a code whose minimum distance is any odd integer. This exercise asks you to give the analogous analysis for a code whose minimum distance is any even integer. Let t ≥ 1 be any integer, and let C be a code with minimum distance 2t. Determine how many errors C can detect and correct, and prove your answers.
Let c ∈ {0, 1} n be a codeword. Until now, we’ve mostly talked about substitution errors, in which a single bit of c is flipped from 0 to 1, or from 1 to 0. The next few exercises explore two other types of errors. An erasure error occurs when a bit of c isn’t successfully transmitted, but the recipient is informed that the transmission of the corresponding bit wasn’t successful. We can view an erasure error as replacing a bit ci from c with a ‘?’ (as in Exercise 4.1, for credit-card numbers). Thus, unlike a substitution error, the recipient knows which bit was erased. (So a codeword 1100110 might become 1?0011? after two erasure errors.) When codeword c ∈ {0, 1} n is sent, the receiver gets a corrupted codeword c′ ∈ {0, 1, ?} n and where all unerased bits were transmitted correctly (that is, if c ′ i ∈ {0, 1}, then c′ i = ci).
Exercise 4.1,
programming required) Implement cc-check in a programming language of your choice. Extend your implementation so that, if it’s given any 16-digit credit/debit-card number with a single digit replaced by a "?", it computes and outputs the correct missing digit