0

I'm trying to describe all MDS - code - classes over $GF(2)$.

Let $K - [n,k,d]_{2}$-code, where $dimK=2$, $K \subset GF(2)^n_{GF(2)}$ and $d$-code distance. $K$-MDS-code, so that $d = n - k + 1$.
If $d = n$ or $d = 1$ we have trivial MDS-codes.
If $d = n - 1$ we have parity checking code.
If $d = 3$ we have Hamming's-$[n,n-2,3]_2$ code $H_2(2)$ and nothing more?.
Now if $d = 2,3,\dots,n-2$ I have no idea how to describe these codes. Do some MDS-codes with such distance exist?

travan4k
  • 21
  • 4

1 Answers1

1

Dimension of Hamming code is $k = n - \log_2(n+1) $ and not equal to $n-2$ unless $n = 1$. Over $\mathbb{F}_2$, there are only 3 MDS codes.

Code 1: Repitition code with $k=1$,

Code 2: Single parity check code with $k = n-1$

Code 3: Full space, $k = n$.

By Griesmer bound, for linear codes over $\mathbb{F}_2$: $n \geq \sum_{i=0}^{k-1} \left \lceil \frac{d}{2^i} \right \rceil \approx d + k + \max(d-k,d - \log_2(d))$.

For code to be MDS, we need $n = d+k-1$. So no linear MDS binary code exists for most of the cases.

Try using Hamming bound for non-linear codes over $\mathbb{F}_2$ but its messy bound.

Balaji sb
  • 4,357
  • Thanks a lot. Can you recommend some books about Error-correcting code theory? – travan4k Dec 25 '22 at 12:45
  • Algebraic coding theory by Blahut for codes over finite fields like cyclic codes. Error correcting codes by Shu Lin (my PhD Advisor used to refer this). I would recommend you to search Error correcting codes course online and see what is the text book for the course they recommend. I recommend looking at Error correcting codes lecture by Prof P Vijay Kumar (my PhD Advisor) in NPTEL https://archive.nptel.ac.in/courses/117/108/117108044/ – Balaji sb Dec 25 '22 at 12:49