Question: Error-Correcting Codes / RSA - (Perfect codes.) We say that a q-ary length-n block code C is t-perfect if for every possible string s 2 (Zq)n, there is exactly one codeword c 2 C such that dH(c,s)  t.

(Perfect codes.) We say that a q-ary length-n block code C is t-perfect if for every possible string s 2 (Zq)ⁿ, there is exactly one codeword c 2 C such that d_H(c,s)  t.

To illustrate this with some examples:


 The code C = {000,111} is a 1-perfect code. To see why, take any string s 2 (Z2)³. If s has one or fewer 1’s, then s is distance at most 1 from 000 and distance at least 2 from 111. Otherwise, s has two or more 1’s, and thus is distance at most 1 from 111 and distance at least 2 from 000.

 The code C = {0000,0011,1111} is not a 1-perfect code. To see why, observe that 0001 is distance 1 from two di↵erent strings in our code, namely 0000 and 0011.

 The code C = (Zq)ⁿ of all codewords is a 0-perfect code; trivially, every string in (Zq)ⁿ is distance 0 from itself and not distance 0 from any other word.

1.     Let s be an element of (Z2)ⁿ. Show that there are exactly
   
   many strings in (Z2)ⁿ whose distance from s is at most t.
2.     Find all of the values of t such that a t-perfect length-8 binary code exists. Justify your answer (that is, for every value of t, either find a length-8 t-perfect binary code, or explain why no such perfect code exists.)