next up previous contents index
Next: Coding theory exercises using Up: Error-correcting codes Previous: Quadratic residue codes   Contents   Index

Some unsolved problems in coding theory

To begin, a ``code'' in this section is any subset of $ \mathbb{F}^n$, where $ \mathbb{F}$ is a finite field. More precisely, a code is a map $ e:\mathbb{F}^m\rightarrow \mathbb{F}^n$, where $ \mathbb{F}^m$ represents the original message space and $ \mathbb{F}^n$ the space of transmitted messages. Question: Given $ M>1$ and $ n>1$, what is the largest $ d$ for which there is a code $ C$ of size $ M$ and minimum distance $ d$? At the moment, this is only known for $ d=1$ or if $ d > 1$ and $ M$ is relatively small (depending on $ d$). To make the problem easier, let use restrict to the subclass of linear codes. In the case of linear codes, the question can be worded more precisely. Question: Given $ k>1$ and $ n>1$, what is the largest $ d$ for which there is a linear code $ C$ of length $ n$, dimension $ k$, and minimum distance $ d$? Again, this isn't known, except in special cases. Back to general codes. Question: Given $ d > 1$ and $ n>1$, what is the smallest $ M>1$ for which there is a code $ C$ of size $ M$ and minimum distance $ d$? This related problem is not known either (except for some very special cases, as above). Again, to make the problem easier, let use restrict to the subclass of linear codes. In the case of linear codes, the question can be worded more precisely. Question: Given $ d > 1$ and $ n>1$, what is the smallest $ k>1$ for which there is a code $ C$ of length $ n$, dimension $ k$, and minimum distance $ d$? Again, in general this isn't known. In another attempt to make these problems easier, we could ask for something less accurate but still useful. For example, in the last question, instead of fixing $ n$ we could allow $ n\rightarrow \infty$ and simply ask for a sequence of $ k=k_n$'s which asymptotically approach the optimally best dimension. This isn't known either!


next up previous contents index
Next: Coding theory exercises using Up: Error-correcting codes Previous: Quadratic residue codes   Contents   Index
David Joyner 2002-08-23