7

Why the only binary MDS codes are trivial ones?

I have been thinking how to draw a contradiction by assuming the MDS code is not trivial.

Thank you very much!

xxxxxxxxx
  • 13,302
user200977
  • 71
  • 1
    Not many people are going to know the list of codes that are considered trivial, so you might want to include it. – rschwieb Dec 13 '14 at 21:04
  • And I guess there are more people who know about this stuff at [cs.se]... –  Dec 13 '14 at 21:32
  • 1
    I dare guess that in this context trivial means either the universal code, the even weight subcode, or the repetition code. Snowball seems to agree. – Jyrki Lahtonen Dec 15 '14 at 10:17

3 Answers3

3

This is Proposition 9.2 on p. 212 of Elements of Algebraic Coding Theory by L. R. Vermani.

Definiton 9.2

We have shown that linear $[n, 1, n]$, $[n, n- 1, 2]$ and $[n, n, 1]$ codes exist over any finite field $F$ and these are MDS codes. These are called trivial MDS codes.

Proposition 9.2

The only binary MDS codes are the trivial codes.

Proof

Let $C$ be a binary $[n, k, d]$ MDS code. If $k = 1$, then $C$ is a trivial MDS code and so we may suppose that $k > 1$. Let $G$ be a generator matrix of $C$ with the first $k$ columns of $G$ forming the identity matrix. If $n > k + 1$, then $C$ has a column, say $j$th, of weight less than $k$ and greater than $1$. Suppose that the $i$th entry of this column is $0$. Then the first $k$ columns of $G$ except the $i$th together with the $j$th column are linearly dependent. This proves that $C$ cannot be an MDS code. Hence

$$k \le n \le k + 1$$

and $C$ is a trivial MDS code.

Snowball
  • 3,078
  • 18
  • 37
  • @Jonathan: Any MDS code is linear by definition. – Snowball Dec 14 '14 at 13:06
  • Damn these pesky details! Thanks. Just to clarify, then: are there non-linear binary codes (hence, not the single word code, nor repetition code, Hamming code or the entire space) achieving the Singleton bound? – Jonathan Y. Dec 14 '14 at 13:16
  • @Jonathan: Yes. If you add a fixed vector to every codeword of one of those codes, the resulting code will achieve the Singleton bound and may be nonlinear. I'm not sure if there are any that aren't a translation of a linear code. – Snowball Dec 15 '14 at 07:13
  • 2
    +1 But I feel like pointing out that the Hamming code does not usually achieve the Singleton bound. The length three Hamming code is equal to the repetition code, and that is the only Hamming code satisfying the Singleton bound. Which really shows how useless the Singleton bound is in the binary world. Even perfect codes won't achieve it. – Jyrki Lahtonen Dec 15 '14 at 10:23
3

Let $G$ be the generator matrix of the code in standard form $[I_k|A]$ where $A$ is a $k \times (n - k)$ matrix. Since the minimum weight of the code is $d = n - k + 1$, all entries of $A$ are non-zero, and hence $A$ is the all one matrix. If $A$ has only one row, then $k = 1$ and the parameters of the code are $[n, 1, n]$. So, say that $A$ has at least two rows. The sum of first two rows is a vector of weight $2$ which is a codeword. Therefore, $d = n - k + 1 \leq 2$, which shows that $n = k$ or $n = k + 1$. For both cases we have a trivial code, of parameters $[n, n, 1]$ and $[n, n-1, 2]$, respectively.

Anurag
  • 755
-3

The only binary codes that are MDS are the trivial (n, n, 1) universe codes, the (n, n − 1, 2) single-parity-check (SPC) codes, and the (n, 1, n) repetition codes. http://web.stanford.edu/class/ee392d/Chap8.pdf

RE Ali
  • 1