# How do I calculate MDS codes?

We are given $n, m$ with $n - m > 1$. Let $S$ be the set of all $n$-bit words. Form $2^{n-m}$ disjoint subsets of $S$ of size $2^m$, denote a typical one of them by $A$, and let $B = S \setminus A$. With $H(a,b)$ denoting the Hamming distance of elements $a \in A$ and $b \in B$, let $G(a) = \max_{b \in B} H(a,b)$ and $F(A) = \min_{a \in A} G(a)$. How could one construct the $A$s such that the $F(A)$ values are as small as possible?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – D.W. Apr 30 '16 at 18:27
• Not sure I get your question. What is a `typical' one? why not taking A to be all vectors of form $0001000$, where the 1 is in different place. Then, for any $a\in A$, $G(a) = n$, no? (here |A|=m rather than $2^m$, but this could easily be extended; just checking I get the question correctly) – Ran G. May 2 '16 at 3:10
• I like to have a given number (2**(n-m)) of disjoint A's such that, given any n-bit word w, I can identify a particular A such that either w is alrady in that A or is such that with at most F(A) corrections it will become an element of A. I desire that the A's be generated such that the said maximal correction efforts would be as small as possible under all circumstances. If that goal is realizable, I should appreciate it very much if you would help me. – Mok-Kong Shen May 2 '16 at 13:58
• @RanG.: Correction to my last comment: Please read after its 2nd line as follows: become an element of A and that maximal correction effort is as small as possible (in comparison to the other As). The A's should be generated to enable that optimum property be realized. – Mok-Kong Shen May 2 '16 at 14:34
• Your question is still unclear to me, but it feels like you are looking for MDS codes, and along with their affine cosets. – Ran G. May 2 '16 at 15:19

It seems you are looking after (linear) MDS codes. A linear $[n,k,d]$-MDS code "partitions" the space into $2^k$ balls of size $2^n/2^k$ elements each, so that the minimal distance between any two codewords is at least $d=n-k+1$. This is the maximal possible distance by the singleton bound.
Now, Let $C$ be such a code, and consider its cosets, that is, given any word $w\in \{0,1\}^n$ look at the affine subspace $w+C = \{ w+u \mid u\in C\}$. It is not difficult to see that any such coset is also an MDS code (namely, it partitions the entire space into balls of the same size, with the same distance guarantees; however it are no longer a linear space, but an affine one).
To answer your question, given any $\alpha\in \{0,1\}^n$ and any coset $\beta = w+C$, $\alpha$ is within distance $\lceil d/2\rceil$ from one word in $w+C$ (the center of the appropriate ball where $\alpha$ lies). Due to the singleton bound, such a distance is optimal.