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 ...
, block codes are a large and important family of
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 encode data in blocks.
There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists,
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
s, and
computer scientists
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (including th ...
to study the limitations of ''all'' block codes in a unified way.
Such limitations often take the form of ''bounds'' that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.
Examples of block codes are
Reed–Solomon codes,
Hamming code
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the sim ...
s,
Hadamard code
The Hadamard code is an error-correcting code named after Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mar ...
s,
Expander codes,
Golay codes, and
Reed–Muller code
Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in ...
s. These examples also belong to the class of
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...
s, and hence they are called linear block codes. More particularly, these codes are known as algebraic block codes, or cyclic block codes, because they can be generated using boolean polynomials.
Algebraic block codes are typically
hard-decoded using algebraic decoders.
The term ''block code'' may also refer to any error-correcting code that acts on a block of
bits of input data to produce
bits of output data
. Consequently, the block coder is a ''memoryless'' device. Under this definition codes such as
turbo code
In information theory, turbo codes (originally in French ''Turbocodes'') are a class of high-performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely ...
s, terminated convolutional codes and other iteratively decodable codes (turbo-like codes) would also be considered block codes. A non-terminated convolutional encoder would be an example of a non-block (unframed) code, which has ''memory'' and is instead classified as a ''tree code''.
This article deals with "algebraic block codes".
The block code and its parameters
Error-correcting code
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 ...
s are used to
reliably transmit
digital data
Digital data, in information theory and information systems, is information represented as a string of discrete symbols each of which can take on one of only a finite number of values from some alphabet, such as letters or digits. An example i ...
over unreliable
communication channel
A communication channel refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel in telecommunications and computer networking. A channel is used for informa ...
s subject to
channel noise.
When a sender wants to transmit a possibly very long data stream using a block code, the sender breaks the stream up into pieces of some fixed size. Each such piece is called ''message'' and the procedure given by the block code encodes each message individually into a codeword, also called a ''block'' in the context of block codes. The sender then transmits all blocks to the receiver, who can in turn use some decoding mechanism to (hopefully) recover the original messages from the possibly corrupted received blocks.
The performance and success of the overall transmission depends on the parameters of the channel and the block code.
Formally, a block code is an
injective
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
mapping
:
.
Here,
is a finite and nonempty
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
and
and
are integers. The meaning and significance of these three parameters and other parameters related to the code are described below.
The alphabet Σ
The data stream to be encoded is modeled as a
string over some alphabet
. The size
of the alphabet is often written as
. If
, then the block code is called a ''binary'' block code. In many applications it is useful to consider
to be a
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 ...
, and to identify
with 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 ...
.
The message length ''k''
Messages are elements
of
, that is, strings of length
.
Hence the number
is called the message length or dimension of a block code.
The block length ''n''
The block length
of a block code is the number of symbols in a block. Hence, the elements
of
are strings of length
and correspond to blocks that may be received by the receiver. Hence they are also called received words.
If
for some message
, then
is called the codeword of
.
The rate ''R''
The rate of a block code is defined as the ratio between its message length and its block length:
:
.
A large rate means that the amount of actual message per transmitted block is high. In this sense, the rate measures the transmission speed and the quantity
measures the overhead that occurs due to the encoding with the block code.
It is a simple
information theoretical fact that the rate cannot exceed
since data cannot in general be losslessly compressed. Formally, this follows from the fact that the code
is an injective map.
The distance ''d''
The distance or minimum distance of a block code is the minimum number of positions in which any two distinct codewords differ, and the relative distance
is the fraction
.
Formally, for received words
, let
denote the
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 ...
between
and
, that is, the number of positions in which
and
differ.
Then the minimum distance
of the code
is defined as
: