Error correction for short strings

Question

For the past few days I' was looking for an error correction code which can correct $\sim 30\%$ errors of a short string.
What is a short string? I want to encode a $7$-$10$ bit string to an $X$ bit string ($X$ as small possible) and to be able to decode the received string with $X\cdot0.3$ random located errors.
So far the best I could find was Repetition Code.
Information Theory is not my specialty so I'm struggling with this.

Answer 1

OK, let your error rate be $23\%$ and let $d=23n/50$ correcting approximately $23n/100$ errors.

The Plotkin bound (see https://en.wikipedia.org/wiki/Plotkin_bound) can be used for the case $d$ odd only for this $d.$ You need $2d+1>n$ to use it, i.e., $\frac{46n}{50}+1>n$ which yields $1>\frac{4n}{50}$ or $n\leq 12.$

Then using the bound $$ A_2(n,d)\leq 2 \left\lfloor \frac{\frac{23n}{50}+1}{\frac{46n}{50}+1-n}\right\rfloor=2\left\lfloor \frac{50+23n}{50-4n}\right\rfloor $$ for odd $n\leq 12$ gives the possible parameters (taking floors to find feasible $d$)

$$A_2(7,3)\leq 18,$$ $$A_2(8,3)\leq 26,$$ $$A_2(11,5)\leq 100,$$ $$A_2(12,5)\leq 326.$$

All this means is that the plotkin bound does not rule out the existence of such code parameters.

There are tables of best codes known and you might want to search for those with these parameters of $n$ and $d$.

One simple idea (since you consider $p<1/4$) is to use a first order Reed-Muller code. Such a code has dimension $k=m+1,$ message length $n=2^m$ and distance $2^{m-1}=n/2.$ For 7 bits of information, you'll have a code of length $n=64.$ The decoding is via the Fast Hadamard Transform, so is quite efficient.