Does dual exist for non-linear codes also?

Question

In almost all the definitions I have seen for the dual of a code, the definitions start with

Dual of a Linear code is defined as ...

Since the linearity of a code is not used while defining the dual of a code, I was wondering if dual codes for non-linear codes exist?

Answer 1

It is possible to define the dual code of a binary $(n,M)$ code $\mathcal C$ (which here denotes a collection of $M$ (distinct) binary vectors of length $n$) in the usual way, but the concept is not particularly useful when $\mathcal C$ is not a linear code.

The dual code $\mathcal C^\perp$ of code $\mathcal C$ is the set of all binary vectors $\mathbf y$ of length $n$ such that $$\sum_{i=1}^n x_iy_i = 0$$ for all choices of $\mathbf x \in \mathcal C$.

Note that regardless of whether $\mathcal C$ is a linear code or a nonlinear code, $\mathcal C^\perp$ always includes the all-zeroes word. Indeed, if ${\mathbf y}^{(1)}$ and ${\mathbf y}^{(2)}$ are two distinct members of $\mathcal C^\perp$, that we have that $$\sum_{i=1}^n x_iy_i^{(1)} = \sum_{i=1}^n x_iy_i^{(2)} = 0 \implies \sum_{i=1}^n x_i\left(y_i^{(1)}+y_i^{(2)}\right) = 0$$ and so ${\mathbf y}^{(1)} + {\mathbf y}^{(2)}$ is also a member of $\mathcal C^\perp$, that is, $\mathcal C^\perp$ is a linear code that is the dual of the linear code spanned by the codewords of $\mathcal C$. When $\mathcal C$ is a nonlinear code, it is often the case that the all-zeroes word is the only member of $\mathcal C^\perp$ (which is also trivially a linear code).

In contrast, if $\mathcal C$ happens to be a linear code (and so $M$ necessarily equals $2^k$ for some $k, 0 \leq k \leq n$), then $\mathcal C^\perp$ is also a linear code with $2^{n-k}$ codewords. In particular, the sum of the rates of $\mathcal C$ and $\mathcal C^\perp$ is $1$. No such relationship exists between the rates of $\mathcal C$ and $\mathcal C^\perp$ when $\mathcal C$ is a nonlinear code, not even when $M=2^k$ for some $k$. $\big($The rate of a nonlinear $(n,M)$ code is $\frac{\log_2M}{n}\big). $ Thus, the dual of a nonlinear code (while it can be defined) is not a very useful concept.

Answer 2

No because linear codes satisfy the relationship given by the MacWilliams identities $$ W_C^{\perp}(x,y)=\frac{1}{|C|}W_C(x+y,x-y) $$ where the coefficient of $x^{n-i}y^i$ in the weight enumerator $W_C(x,y)$ is equal to the number of codewords of weight exactly $i$ in the respective code. If you have nonlinear codes, the relevant machinery breaks down and this does not hold in general.

The main practical interest in duality is to obtain the weight enumerator $W_C$ of a code efficiently from that of its dual [which hopefully is easier to obtain]. The weight enumerator can be used for computing probabilities related to error correction.

It was a mystery for many years that some codes satisfied the relationship even though they were nonlinear. For example the Kerdock and Preparata codes did, and some prominent researchers thought this was only a "coincidence".

In work starting in Boztas, Hammons, Kumar and independently Sole ([a1] and [a9] respectively) in the linked document, and culminating in Hammons, Kumar, Calderbank, Sloane and Sole [a4], the mystery of formal duality of Kerdock and Preparata codes was explained by converting the binary codes to a $Z_4$ representation (using Galois rings) and led to a lot of ensuing research on $Z_4$ codes. See this entry of the Encyclopedia of Math on Kerdock and Preparata codes for details.

As an aside [a1] also gave the first example of near optimal QPSK (nonbinary) CDMA sequences for wireless communications thus explaining a discrepancy in Sidelnikov and Welch lower bounds on the best possible signal sets for binary vs nonbinary signaling, which had also stood for decades.