2
$\begingroup$

In Coding Theory, people use $q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as $\mathbb{R}$ or $\mathbb{C}$?

$\endgroup$
  • $\begingroup$ Coding theory is based on finite fields theory, and finite fields have quite different properties than infinite ones. I’m not an expert so I don’t know much more, but you may probably start from that. $\endgroup$ – gigabytes Dec 21 '17 at 12:47
  • 1
    $\begingroup$ An example to keep in mind: If you felt like cheating, you could encode an entire message into a single element (say one real number), then just send a few copies of it. $\endgroup$ – usul Dec 21 '17 at 14:39
6
$\begingroup$

Sphere packings give a nice analogue of codes over $\mathbb{R}$. A sphere packing is a set $\mathcal{P} \subset \mathbb{R}^n$ such that $d_{\mathcal{P}} := \inf_{x,y \in \mathcal{P}, x \neq y} \|x - y\| > 0$, where $\|\cdot \|$ is the Euclidean norm. This is called a sphere packing because we can place a(n open) sphere of radius $d_{\mathcal{P}}/2$ at each point in $\mathcal{P}$, and the spheres will not overlap.

There are many nice simple analogies between a code $\mathcal{C} \subseteq \mathbb{F}_q^n$ and a sphere packing $\mathcal{P} \subset \mathbb{R}^n$:

  1. $d_{\mathcal{P}}$ is the minimum distance of the sphere packing, and it is the obvious analogue of the minimum distance of the code: $d_{\mathcal{C}} := \min_{x, y \in \mathcal{C}, x \neq y} \|x - y\|_H$, where $\|\cdot\|_H$ is the Hamming weight. In both cases, this can be viewed as a measure of "how correctable errors are when we encode messages via $\mathcal{C}$ or $\mathcal{P}$ over a noisy channel." E.g., $d_{\mathcal{P}}/2$ is the smallest Euclidean noise that we can add to a point in $\mathcal{P}$ so that we are unable to identify the original point uniquely, while $\lceil d_{\mathcal{C}}/2 \rceil$ is the minimal Hamming noise that can be added to a codeword so that we cannot identify the original codeword uniquely.
  2. The analogue of a linear code is a lattice, $\mathcal{L} := \{ z_1 b_1 + \cdots + z_n b_n \ : \ z_i \in \mathbb{Z}\}$, where the $b_i$ are linearly independent vectors in $\mathbb{R}^n$. The minimum distance of a lattice is just the minimal length of a shortest non-zero vector in $\mathcal{P}$, just like the minimal distance of a linear code is the minimal Hamming weight of a non-zero codeword.
  3. The analogue of the rate of the code $\alpha_{\mathcal{C}} := \log |\mathcal{C}|/\log q^n$ is $\delta_{\mathcal{P}} := \lim_{r \to \infty} \log|\mathcal{P} \cap B(r)|/\log \mathrm{vol}(B(r))$, where $B(r)$ is the Euclidean ball of radius $r$. For a lattice $\mathcal{L}$, we have $|\mathcal{L} \cap B(r)| \sim \mathrm{vol}(B(r))/\det(\mathcal{L})$, where $\det(\mathcal{L})$ is the absolute value of the determinant of the matrix given by the basis vectors $(b_1,\ldots, b_n)$. So, $\delta_{\mathcal{L}} = 1-\log \det(\mathcal{L})$.
  4. For codes $\mathcal{C}$, we're often interested in maximizing the minimum distance $d_{\mathcal{C}}$ for a fixed rate $\alpha_{\mathcal{C}}$. For sphere packings $\mathcal{P}$, we are similarly interested in maximizing $d_{\mathcal{P}}$ for fixed $\delta_{\mathcal{P}}$. Notice that we can always scale a sphere packing $\mathcal{P}$ so that, say, $\delta_{\mathcal{P}} = 0$. So, we can assume without loss of generality that a sphere packing satisfies $\delta_{\mathcal{P}} = 0$. In contrast, it seems that codes with rate $\alpha$ and codes with rate $\alpha'$ are fundamentally distinct objects for $\alpha \neq \alpha'$.

Sphere packings are still an active area of research, both in fixed dimensions and in asymptotically large dimension. E.g., the optimal sphere packings are only known in dimensions 1, 2, 3, 8, and 24 (all achieved by lattices), with 8 and 24 dimensions solved only very recently by Viazovska et al (see http://arxiv.org/abs/1603.04246 and http://arxiv.org/abs/1603.06518). In arbitrarily high dimensions, the current record is held by Venkatesh (http://math.stanford.edu/~akshay/research/sp.pdf). A table of the densest known packings in various dimensions is available here: http://www.math.rwth-aachen.de/~Gabriele.Nebe/LATTICES/density.html.

One can also consider packings of objects other than spheres. E.g., one can replace the Euclidean norm in the definition of $d_{\mathcal{P}}$ by any norm.

$\endgroup$
5
$\begingroup$

It is possible to define codes over infinite fields, but it is usually not as useful as codes over finite fields. The original motivation for error-correcting codes comes from the needs to transmits bits over a noisy channel. Over such a channel, it is usually not possible to send real numbers with arbitrary precision.

However, there have been some works that studied error-correcting codes over the reals. Here are two examples:

https://arxiv.org/pdf/1311.5102.pdf

https://arxiv.org/abs/1402.6952v1

$\endgroup$

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.