Design 12-bit forward error correction code

Question

I'm looking for an forward error correction mechanism that satisfies the following constraints:

1. Encodes 4 or more input data bits into a 12-bit word (adding 8 or less redundancy bits)
2. Corrects 2 or more errors

Any ideas?

---

What I've seen so far:

• It can't be done by using 12-bit Hamming codes since it can only correct up to 1 error (violating constraint number 2)
• I'm not sure if it can be achieved by general BCH codes (unfortunately it's beyond my math comprehension). I know that QR Codes use a (18,6) BCH to encode version bits (ISO 18004, page 78), which is (from my understanding) not a primitive narrow-sense one.
• There is something called Binary Golay Code that can correct 3 bits from a 12-bit input encoded into a 23-bit word. Is there any magic that can 'make it work' for 12 bits? (I know this is quite vague, but who knows...)

Answer 1

The BCH-code with length $n=2^4-1=15$ and designed minimum distance $d=5$ has dimension $k=15-2\cdot4=7$. If you shorten that in three positions you get a binary linear $[12,4,5]$-code which is exactly what you need.

---

In a comment you ask whether this is code is optimal in the sense that can we have a code with minimum distance $\ge6$. I don't know the answer to that question right away, if we limit ourselves to binary linear codes. However, a non-linear code of length $12$, $2^4=16$ words and minimum distance $d=6$ can be constructed by shortening the famous $\Bbb{Z}_4$-linear Nordstrom-Robinson code. See my answer to an earlier question for a description of the Nordstrom-Robinson code. With that code you are guaranteed to be able to correct all errors of at most two bits, and detect the occasions (but not uniquely decode) when exactly three bit errors have occured.

Answer 2

Here's the generator matrix for a [12,4,6] code found with gap software (+guava package); this should be the best linear code with these parameters.

100001111010

010010110110

001011101111

000100011111