3
$\begingroup$

This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme would be to ask $2^k$ questions of the form "is $x=[0100001\dots 01]$?" etc, while a refinement would be "is the $i$:th bit a one?" while linear codes generalizes this one step further to "is $x_i + x_j + \dots + x_\ell = 1$?"

With linear codes we can enumerate $k$ independent questions of this form. What I'm wondering is: can we do better?

Call $\{0,1\}^k$ our codebook with a corresponding matrix $C$ containing the coordinates of the codewords in its rows, i.e. $C_0 = [0\dots 0], C_1 = [0\dots 0 1]$ etc. Say we permute this matrix and make the permutation known to the receiver prior to transmission.

Couldn't we produce more than $k$ independent questions by asking questions of the form "is $b_i + b_j + \dots = 1$?", where $b_i$ is the $i$:th bit of the binary representation of the permuted codebook index?

It seems this could generalize into any "type division": to form a question, divide the codebook into $A_i$ and $B_i$ where $|A_i| = |B_i|$ and ask questions of the form "is $x$ of type $A_i$ or $B_i$?"

Clearly, this scheme is a strict generalization of linear coding since parity checks follow this general even division algorithm. Is it a vacuous generalization or could we in fact produce more than $k$ independent questions in this manner?

EDIT: Clarifying independence due to demand - could we by using nonlinear coding construct a list of $k+2$ or more questions such that any size $k$ subset would recover the unique answer? (I made it $k+2$ since I think we can construct a list of $k+1$ questions by using linear codes - just make the $k+1$:th question about the parity of all the rest)

EDIT: This is not a question on decoding tractability, so please refrain on commenting on that aspect.

$\endgroup$
  • $\begingroup$ Questions of the form $x=x_0?$ display this independence: any $2^n-1$ of them are independent, in the sense that knowing the answer to $2^n-2$ of them doesn't always determine the answer of the remaining one. $\endgroup$ – Yuval Filmus Feb 29 '16 at 19:34
  • $\begingroup$ Yeah but we also want any $k$ independent questions to yield the unique answer. $\endgroup$ – Benjamin Lindqvist Feb 29 '16 at 19:44
  • $\begingroup$ I suggest you specify what you mean by independence in your question. $\endgroup$ – Yuval Filmus Feb 29 '16 at 19:45
  • $\begingroup$ Done, but the edit kind of made me suspect that a positive answer to this question could have some serious repercussions in the coding world. Nonetheless, an explanatory answer in the negative would be nice as well. $\endgroup$ – Benjamin Lindqvist Feb 29 '16 at 19:56
3
$\begingroup$

Linear codes which satisfy your requirement are known as linear MDS (maximum distance separable) codes. While there are no non-trivial (in your sense) binary linear MDS codes, there are such codes over larger alphabets. It might be that binary non-linear MDS codes are what you are after. In that case, you might be able to construct some from linear MDS codes over $\mathbb{F}_{2^k}$ for $k>1$.

$\endgroup$
  • $\begingroup$ That is a really interesting reference, many thanks. Although it doesn't seem straightforward to generalize the concept of MDS since the very definition seems to involve generator rank... $\endgroup$ – Benjamin Lindqvist Feb 29 '16 at 21:08
  • $\begingroup$ The definition replaces dimension with logarithm of size. $\endgroup$ – Yuval Filmus Feb 29 '16 at 21:12
  • $\begingroup$ The following is called the MDS conjecture (Fundamentals of Error Correcting Codes, Huffman): "If there is a nontrivial $[n, k]$ MDS code over $F_q$ , then $n ≤ q + 1$, except when $q$ is even and $k = 3$ or $k = q − 1$ in which case $n ≤ q + 2.$" $\endgroup$ – Benjamin Lindqvist Feb 29 '16 at 21:45
  • $\begingroup$ (the source defines MDS as either linear or nonlinear, which means that they believe it can not be done using ANY scheme) $\endgroup$ – Benjamin Lindqvist Feb 29 '16 at 22:09
  • $\begingroup$ Ugh I'm quite confused now. It seems that the conjecture says nothing about nonlinear codes. $\endgroup$ – Benjamin Lindqvist Feb 29 '16 at 22:53

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.