The Singleton Bound is blocking my path

Question

let's assume I'd like to print 28 bits of Information on a sheet of paper. To make it easy-to-read by humans, let's convert this into 7 hex digits.

Now I can add two more hex digits to produce an error-correcting code. This code has length $n=9$ and dimension $k=7$ over the field $\mathbb F_{16}$. Due to the singleton bound I can correct at most $$\left\lfloor{\dfrac{(n-k+1)-1}2}\right\rfloor=1$$ errors. This can be achieved by means of a MDS code, e.g. Reed-Solomon.

Now one can add more and more of these check digits. But the next improvement, i.e. being able to correct two errors, needs four check digits.

My question is: if I'd want to print my 7 hex digits plus only three more digits:

$$1234567ABC$$

can I somehow correct 2 errors? Maybe by rearranging the digits?

I already know that making the alphabet larger would make it easy to squeeze the 28 bits into 6 letters/digits. Then one would end up with a code like $123456ABCD$.

Answer 1

Maybe I'm misunderstanding you, but if you need print $28 + 4\times 4 = 44$ bits (all the $2^{44}$ numbers are possible), this requires exactly $11$ hexadecimal digits.

Using for example [0-9],[A-Z],[a-z] (62 different characters) the 44 bits fit in 8 characters because $$62^8 = 218340105584896 > 17592186044416 = 2^{44}.$$

Answer 2

can I somehow correct 2 errors? Maybe by rearranging the digits?

I though I understood the first question, but the second one is so puzzling that it makes me doubt...

First, do we agree that the amount of "errors" here refer to the elements of $\mathbb F_{16}$ (hexadeximal digits, if you prefer to call them so), no? It's not the amount of bit errors.

Now, if you are asking if we can construct a linear block code over block $\mathbb F_{16}$ with $n=10$ and $k=7$ that can correct 2 errors...

Such a code would require $t=2$, $d=5$. The Hamming bound tells us that the maximum size of the codebook is

$$A_{16}(10,5)\le \frac{16^{10}}{\binom{10}{0} + \binom{10}{1} 15 + \binom{10}{2}15^2}=\frac{16^{10}}{1+ 150 + 10125} \approx 107 \times 10^6$$

But $16^7\approx 268.4 \times 10^6$

Hence, no, (if I understood you question) you can't.