Skip to main content
eScholarship
Open Access Publications from the University of California

Reed-Solomon Codes and the Deep Hole Problem

  • Author(s): Keti, Matt
  • Advisor(s): Wan, Daqing
  • et al.
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Public License
Abstract

In many types of modern communication, a message is transmitted over a noisy medium. When this is done, there is a chance that the message will be corrupted. An error-correcting code adds redundant information to the message which allows the receiver to detect and correct errors accrued during the transmission. We will study the famous Reed-Solomon code (found in QR codes, compact discs, deep space probes,\ldots) and investigate the limits of its error-correcting capacity. It can be shown that understanding this is related to understanding the ``deep hole" problem, which is a question of determining when a received message has, in a sense, incurred the worst possible corruption. We partially resolve this in its traditional context, when the code is based on the finite field $\mathbb{F}_q$ or $\mathbb{F}_q^*$, as well as new contexts, when it is based on a subgroup of $\mathbb{F}_q^*$ or the image of a Dickson polynomial. This is a new and important problem that could give insight on the true error-correcting potential of the Reed-Solomon code.

Main Content
Current View