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.