Abstract Algebra: Theory and Applications · Problem 8.10.4

Isomorphisms — Thomas Judson

Mathematics — Abstract Algebra · perfect-codes-sage

Problem

A code with minimum distance

d

is called perfect if every possible vector is within Hamming distance

(d-1)/2

of some codeword. If we expand our notion of geometry to account for the Hamming distance as the metric, then we can speak of a sphere of radius

r

around a vector (or codeword). For a code of length

n

, such a sphere will contain

1 + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{r}

vectors within it. For a perfect code, the spheres of radius

d

centered at the codewords of the code will exactly partition the entire set of all possible vectors. A consequence of a code of dimension

k

being perfect is that

2^k \left( \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{\frac{d-1}{2}} \right) = 2^n

Conversely, if a code has minimum distance

d

and the condition above is true, then the code is perfect. Write a Python function, named is\_perfect() which accepts a linear code as input and returns True or False. Demonstrate your function by checking that the (binary) Golay code is perfect, and then use a loop to verify that the (binary) Hamming codes are perfect for all lengths below 32.

Browse the problem library