In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...
, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of
cyclic
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in s ...
error-correcting codes
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
that are constructed using
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s over a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
(also called ''
Galois field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
''). BCH codes were invented in 1959 by French mathematician
Alexis Hocquenghem, and independently in 1960 by
Raj Chandra Bose
Raj Chandra Bose (19 June 1901 – 31 October 1987) was an Indian American mathematician and statistician best known for his work in design theory, finite geometry and the theory of error-correcting codes in which the class of BCH codes is pa ...
and
D.K. Ray-Chaudhuri. The name ''Bose–Chaudhuri–Hocquenghem'' (and the acronym ''BCH'') arises from the initials of the inventors' surnames (mistakenly, in the case of Ray-Chaudhuri).
One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an
algebraic method known as
syndrome decoding
In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, su ...
. This simplifies the design of the decoder for these codes, using small low-power electronic hardware.
BCH codes are used in applications such as satellite communications,
compact disc
The compact disc (CD) is a Digital media, digital optical disc data storage format that was co-developed by Philips and Sony to store and play digital audio recordings. In August 1982, the first compact disc was manufactured. It was then rele ...
players,
DVD
The DVD (common abbreviation for Digital Video Disc or Digital Versatile Disc) is a digital optical disc data storage format. It was invented and developed in 1995 and first released on November 1, 1996, in Japan. The medium can store any kind ...
s,
disk drives
Data storage is the recording (storing) of information (data) in a storage medium. Handwriting, phonographic recording, magnetic tape, and optical discs are all examples of storage media. Biological molecules such as RNA and DNA are consi ...
,
USB flash drive
A USB flash drive (also called a thumb drive) is a data storage device that includes flash memory with an integrated USB interface. It is typically removable, rewritable and much smaller than an optical disc. Most weigh less than . Since firs ...
s,
solid-state drive
A solid-state drive (SSD) is a solid-state storage device that uses integrated circuit assemblies to store data persistently, typically using flash memory, and functioning as secondary storage in the hierarchy of computer storage. It is ...
s,
quantum-resistant cryptography and
two-dimensional bar codes.
Definition and illustration
Primitive narrow-sense BCH codes
Given a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
and
prime power
In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number.
For example: , and are prime powers, while
, and are not.
The sequence of prime powers begins:
2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
with positive integers and such that , a primitive narrow-sense BCH code over the
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
(or Galois field) with code length and
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
at least is constructed by the following method.
Let be a
primitive element of .
For any positive integer , let be the
minimal polynomial with coefficients in of .
The
generator polynomial In coding theory, a polynomial code is a type of linear code whose set of valid code words consists of those polynomials (usually of some fixed length) that are polynomial long division, divisible by a given fixed polynomial (of shorter length, call ...
of the BCH code is defined as the
least common multiple
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
.
It can be seen that is a polynomial with coefficients in and divides .
Therefore, the
polynomial code In coding theory, a polynomial code is a type of linear code whose set of valid code words consists of those polynomials (usually of some fixed length) that are divisible by a given fixed polynomial (of shorter length, called the ''generator polyno ...
defined by is a cyclic code.
Example
Let and (therefore ). We will consider different values of for based on the reducing polynomial , using primitive element . There are fourteen minimum polynomials with coefficients in satisfying
:
The minimal polynomials are
:
The BCH code with
has generator polynomial
:
It has minimal
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
at least 3 and corrects up to one error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.
The BCH code with
has generator polynomial
:
It has minimal Hamming distance at least 5 and corrects up to two errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.
The BCH code with
has generator polynomial
:
It has minimal Hamming distance at least 7 and corrects up to three errors. Since the generator polynomial is of degree 10, this code has 5 data bits and 10 checksum bits. (This particular generator polynomial has a real-world application, in the format patterns of the
QR code
A QR code (an initialism for quick response code) is a type of matrix barcode (or two-dimensional barcode) invented in 1994 by the Japanese company Denso Wave. A barcode is a machine-readable optical label that can contain information about th ...
.)
The BCH code with
and higher has generator polynomial
:
This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.
General BCH codes
General BCH codes differ from primitive narrow-sense BCH codes in two respects.
First, the requirement that
be a primitive element of
can be relaxed. By relaxing this requirement, the code length changes from
to
the
order of the element
Second, the consecutive roots of the generator polynomial may run from
instead of
Definition. Fix a finite field
where
is a prime power. Choose positive integers
such that
and
is the
multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative order ...
of
modulo
As before, let
be a
primitive th root of unity in
and let
be the
minimal polynomial over
of
for all
The generator polynomial of the BCH code is defined as the
least common multiple
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
Note: if
as in the simplified definition, then
is 1, and the order of
modulo
is
Therefore, the simplified definition is indeed a special case of the general one.
Special cases
* A BCH code with
is called a ''narrow-sense BCH code''.
* A BCH code with
is called ''primitive''.
The generator polynomial
of a BCH code has coefficients from
In general, a cyclic code over
with
as the generator polynomial is called a BCH code over
The BCH code over
and generator polynomial
with successive powers of
as roots is one type of
Reed–Solomon code where the decoder (syndromes) alphabet is the same as the channel (data and generator polynomial) alphabet, all elements of
. The other type of Reed Solomon code is an
original view Reed Solomon code which is not a BCH code.
Properties
The generator polynomial of a BCH code has degree at most
. Moreover, if
and
, the generator polynomial has degree at most
.
Each minimal polynomial
has degree at most
. Therefore, the least common multiple of
of them has degree at most
. Moreover, if
then
for all
. Therefore,
is the least common multiple of at most
minimal polynomials
for odd indices
each of degree at most
.
A BCH code has minimal Hamming distance at least
.
Suppose that
is a code word with fewer than
non-zero terms. Then
: