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
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 exampl ...
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
Algebraic may refer to any subject related to algebra in mathematics and related branches like algebraic number theory and algebraic topology. The word algebra itself has several meanings.
Algebraic may also refer to:
* Algebraic data type, a data ...
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
The compact disc (CD) is a 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 released in O ...
players,
DVDs,
disk drives,
USB flash drive
Universal Serial Bus (USB) is an industry standard that establishes specifications for cables, connectors and protocols for connection, communication and power supply ( interfacing) between computers, peripherals and other computers. A bro ...
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 a ...
s,
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
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), 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 ...
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 ...
.
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 poly ...
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 t ...
.)
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
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 ...
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
: