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 studied ...
, 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 so ...
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 ...
that are constructed using
polynomials over a
finite field (also called ''
Galois field''). BCH codes were invented in 1959 by French mathematician
Alexis Hocquenghem, and independently in 1960 by
Raj Chandra Bose 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. 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 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 kin ...
s,
disk drives,
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 first ...
s,
solid-state drives,
quantum-resistant cryptography
In cryptography, post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack ...
and
two-dimensional bar codes.
Definition and illustration
Primitive narrow-sense BCH codes
Given a
prime number and
prime power with positive integers and such that , a primitive narrow-sense BCH code over the
finite field (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 of the BCH code is defined as the
least common multiple .
It can be seen that is a polynomial with coefficients in and divides .
Therefore, the
polynomial code 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 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.)
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
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
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 ord ...
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
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
: