0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – D.W. Apr 30 '16 at 18:27
  • $\begingroup$ 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) $\endgroup$ – Ran G. May 2 '16 at 3:10
  • $\begingroup$ 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. $\endgroup$ – Mok-Kong Shen May 2 '16 at 13:58
  • $\begingroup$ @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. $\endgroup$ – Mok-Kong Shen May 2 '16 at 14:34
  • $\begingroup$ Your question is still unclear to me, but it feels like you are looking for MDS codes, and along with their affine cosets. $\endgroup$ – Ran G. May 2 '16 at 15:19
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I like to write a program to solve the problem of my OP but my knowledge in coding theory is unfortunately very poor. Could you kindly sketch how the computation is to be done through thereby giving literature references to the algorithms (in abstract but not difficult to staightforwardly implement form) that are to be employed in the diverse processing steps? Thanks in advance. $\endgroup$ – Mok-Kong Shen May 4 '16 at 7:38
  • $\begingroup$ Sorry, I can't help with programming advice. I suggest you find some textbook about coding, or read about known MDS codes to get ideas. (or possibly ask in the Computer Science Chat?) $\endgroup$ – Ran G. May 6 '16 at 17:05
  • $\begingroup$ Is the computation of MDS codes feasible in general, i.e. without any restrictions? I vaguely remember to have read in a book which has a statement in the negative sense. $\endgroup$ – Mok-Kong Shen May 7 '16 at 8:15
  • $\begingroup$ over binary fields there are only simple MDS codes, however over large fields there are known codes like Reed-Solomon. If needed for binary, maybe search for "almost MDS" (or "Near MDS") codes. $\endgroup$ – Ran G. May 7 '16 at 15:38
  • $\begingroup$ I just managed to again find the statement which I mentioned to have once seen earlier. On p.83 of G. Kabatiansky et al. "Error correcting coding and security of data networks" there is "The question about the possibility of constructing nontrivial MDS codes (i.e. 2 < d < n) of length n >q+1 is the unsolved problem throwing back to the projective geometry." Since, as said, my knowledge is very poor, I couldn't know whether and how much it has significance in the present context. Anyway, I hope it is understandable that I would sincerely appreciate further helps from experts of this forum. $\endgroup$ – Mok-Kong Shen May 14 '16 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.