Single error correcting binary code of length $16$ and size $2^{12}$

Question

Consider there is a 12 bit data, and we want to add 4 check bits, such that 1-bit errors can be detected and corrected.

How can this be done ?

Consider the data as :

b15 b14 b13 b12
b11 b10 b09 b08
b07 b06 b05 b04

b03 b02 b01 b00 <- check bits

I tried using parity counting, but that only detects error.

b03 = b15 xor b14 xor b13 xor b12 ; this doesn't allow correction of errors.

Can anyone suggest a way ?

Thanks.

Answer 1

This cannot be done. You want to have a code of length 16 that has $2^{12}$ codewords. To each codeword $x$ we associate the ball of radius one $B(x)$ that consists of the word $x$ itself, and the sixteen words that differ from $x$ in a single position. Thus $|B(x)|=17.$ For the error correction to work out as promised, the balls $B(x)$ and $B(x')$ must not overlap, when $x\neq x'$. There are $2^{12}$ choices for $x$, so between them the balls $B(x)$ contain $17\cdot2^{12}$ bit vectors. But there are only $2^{16}$ vectors of length 16 total.

Answer 2

You are asking for a binary code of length $16$, size $2^{12}$ and minimum Hamming distance at least $3$. Unfortunately, such a code does not exist.