I'm trying to create error correction code for small binary strings.
My space = all words with X bits (Y = 2^X words total).
I want to transform my space to a new space with the same amount of words - Y but, each word represented by X+Z bits and each word in the new space has hamming distance d.
For example, my space is

00 - 01 - 10 - 11

and I decided d=2, so the new space is:

0000 - 0101 - 1010 - 0011

So I know I can correct 1 error which is 25% of the data. My goal is to correct ~30% with minimum headers.
My questions?
1. What is the max Hamming distance for between Y words with X bits?
2. How do I know if such transform exists?
3. If it exists, how do I find Z and the transform function?


For any code $C$ with minimum distance $d$, you can correct up to $\lfloor\frac{d-1}{2}\rfloor$ errors.

In the case of a distance $d=2$, this means that you can not correct any errors. To use your example, suppose that your codeword $0000$ has 1 error. It is transformed into any of these $\{1000,0100,0010,0001\}$. All of these codes are 1 distance away from 2 different codewords and can therefore not be properly decoded (without a 50% chance of picking the wrong one).

If you want to be able to correct 30% of the digits, meaning that for any codeword of length $n=10$ the minimum distance must be at least $d=7$. I don't know any family of codes which is able to correct this many errors.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.