NIS2337 Information Theory Notes (5): Channel Coding
Posted onEdited onWord count in article: 5kReading time ≈18 mins.
– “What is this all about? Can’t we just have coding schemes with no
redundancy at all?”
– “Page after page, this is no different from lossy source coding. We
have to account for noise, understand?”
Before delving into channel coding, the author feels it is necessary
to clarify the relationship between source coding and channel coding.
While reading the material in this section, the author often found it
puzzling: the source coding process can be abstracted as a form of
generalized transmission, so why must we spare a precious four lecture
hours out of an eight-week course to study channel coding? In the
preceding chapters, the author painstakingly attempted to remove
redundancy from information, yet the purpose of channel coding is
precisely to add redundancy?
First, source coding and channel coding do not describe the same
thing in information theory – they actually address two independent
problems in the field: leaving aside the channel, how should we compress
information? Leaving aside the source, since noise is inevitable in a
channel, how should we resist its interference? Source coding achieves a
transmission rate close to the entropy of the source by compressing its
redundant parts to the utmost; channel coding, on the other hand,
introduces redundancy to counteract noise, thereby bringing the
transmission rate close to the channel capacity. Thus, source coding and
channel coding are two independent areas of research in information
theory.
In fact, a unified theory does exist – joint source-channel coding.
However, the Shannon separation theorem shows that, under lossless
conditions, source coding and channel coding can be performed separately
without any loss of performance. Since theory supports this decoupling,
why not consider the two problems independently to achieve greater
generality? Engineers working on the H.265 algorithm need not know
whether the data stream they encode will be transmitted via optical disc
or 5G, and 5G communications engineers need not know whether the data
they transmit is a livestream of a SJTU premium course or a popular
forum post. Such decoupling makes system development more flexible and
efficient.
With that motivation, we arrive at this chapter: Channel
Coding. In this chapter, we study errors in channel
transmission, how to decode in order to minimize the probability of
errors, how the channel coding theorem proves the existence of
error-free coding schemes under certain conditions, and the construction
and performance analysis of several classical linear block codes. In the
analysis of linear block codes, we will employ some elegant properties
of linear spaces and cyclic polynomials.
Supplementary materials can be found in Beyond 2337.
Errors and Error Control
Systems
Since channel coding exists for the purpose of error correction, it
is necessary to discuss errors. An error
symbol/symbol error is caused by an error
occurring in a symbol. An error bit/information
error is caused by an error occurring in an information
bit.
For binary transmission systems, error symbols and error bits are
clearly equivalent. For multi-level (M-ary) systems, since one symbol
consists of multiple bits, it is difficult to determine how many bit
errors constitute a single symbol error.
Error pattern. Consider an -ary transmission system where the
transmitted sequence is and the received sequence is . The
error pattern is then . For binary systems, the error pattern is the
XOR of the transmitted and received sequences at
corresponding positions.
Hamming distance. For two -ary sequences and , their Hamming distance is defined as the
number of positions at which the corresponding symbols differ.
Error patterns can be classified as random errors
and burst errors. Random errors refer to the case where
error symbols are randomly distributed in time during transmission, and
the value at each position of the error pattern is independent of time
and position. Burst errors always appear in clusters with temporal
correlation; they begin with an erroneous code symbol and end with an
erroneous code symbol, though not every symbol between the beginning and
end is necessarily erroneous – rather, the probability of error within
this interval exceeds some preset threshold.
An error-correcting code is a code capable of
correcting errors. Its classification is roughly as follows: - By
function: error-detecting codes, error-correcting codes; - By processing
of the information sequence: block codes, convolutional codes; - By
relationship between code symbols and original information bits: linear
codes, nonlinear codes; - By error type: random error-correcting codes,
burst error-correcting codes, and hybrid error-correcting codes that
fall somewhere in between; - By construction theory: algebraic codes,
geometric codes, combinatorial codes, probabilistic codes, etc.
Error control systems can be broadly classified into
three categories: forward error correction,
automatic repeat request, and hybrid error
correction. - Forward Error Correction (FEC)
refers to encoding the information at the transmitter so that the
receiver can correct a certain number of errors through decoding without
requiring retransmission from the transmitter. - Automatic
Repeat reQuest (ARQ) refers to the receiver sending a
retransmission request to the transmitter when an error is detected,
asking the transmitter to resend the erroneous code symbols. -
Hybrid Error Correction (HEC) refers to a mechanism
that combines forward error correction and automatic repeat request:
encoding is performed at the transmitter to resist a certain number of
errors, while the receiver can also send retransmission requests to the
transmitter when errors are detected.
Decoding Methods
Decoding is the process of recovering the original
information from corrupted data as accurately as possible. In the
decoding task, the only information actually known is the received
codeword sequence , the
encoding algorithm used by the transmitter together with the code set
it produces, and the
channel model together with its parameters.
The goal of decoding, i.e., optimal decoding, is to
find, given a received word , a codeword that is the maximum
a posteriori probability (MAP) codeword for , i.e.,
Since is a constant
for a particular received word , this can be simplified to:
In practical communication systems, it is usually assumed that the
transmitted codewords are
equally likely, i.e., , which can be further
simplified to:
This is Maximum Likelihood Decoding (MLD). The goal
of maximum likelihood decoding is to find a codeword that maximizes the
probability of receiving
given that was
transmitted. For a memoryless channel,
From the analysis of the BSC channel, we can observe a connection
between MLD and Minimum Hamming Distance Decoding (MHDD). Let the
crossover probability of the BSC be denoted by . Then, for a specific received word
, the probability of
receiving given that was transmitted is:
where is
the Hamming distance between and . Since , decreases as increases, so
maximum likelihood decoding is equivalent to minimum Hamming distance
decoding, i.e.,
Fano’s inequality. The error probability of the channel and the channel
equivocation satisfy the
following inequality: where is the number of
channel input symbols, is the
channel error probability, and is the binary entropy function.
Fano’s inequality states that the maximum possible entropy in the entire
guessing process must be greater than the true uncertainty remaining in
the system.
Channel Coding Theorem
Why another coding theorem?
Nevertheless, the channel coding theorem answers a question similar
to that addressed by the source coding theorem: given the channel
conditions, does there exist a coding scheme that achieves a zero error
probability? If so, what is the minimum information transmission rate of
such a scheme?
Random Coding and
the Channel Coding Theorem
Engineers today have invented many sophisticated techniques for
constructing error-correcting codes, such as Hamming codes, linear block
codes, and so on. However, when Shannon proved the channel coding
theorem, he put forward a provocative idea: why bother constructing
elaborate algebraic structures? Just ** guess it.
Suppose there are bits of
information to be transmitted, encoded into -bit codewords. Then there are distinct information sequences and
distinct codewords. The idea of
random coding is to randomly select codewords from the possible codewords to form the code
space , and then map
each information sequence to a unique codeword.
Note that different information sequences to be encoded may be mapped
to the same codeword. Consequently, there can be different code sets, which
cannot be counted using combinations. Thus, the probability that the
-th code set is selected is , and let the
corresponding conditional error probability for this code set be . Hence, the average error
probability over all code sets is:
That is, if , then there must exist a family of code sets for which , thereby proving the
existence of a coding scheme achieving arbitrarily small error
probability.
The means to make is simple: let , i.e., increase the
redundancy. On average, the distribution of codewords becomes sparser
and the space between codewords becomes larger, thereby reducing the
error probability. But does converge to zero? Gallager
proved that has an upper
bound that converges exponentially, i.e.,
where is the
reliability function or error
exponent, and is the code rate, which is the amount of information
carried per code symbol.
The reliability function is a straight line with slope in the interval , and gradually converges to in the interval , where is the critical rate
and is the channel capacity. That
is, as long as , there exists
a channel code and its corresponding decoder that, for a sufficiently
long code length , can achieve
reliable communication with an arbitrarily small error probability; if
, then no matter what coding
scheme is adopted, the error probability cannot be reduced to an
acceptably low level.
However, Shannon only proved the existence of an optimal scheme. He
gave no guidance on how to construct a practically feasible coding
scheme to achieve this. In fact, to date, no practically feasible coding
scheme has been found that can achieve channel capacity under all
channel conditions; there are almost no practical information systems
that use random coding, for reasons similar to the advantages of linear
block codes: random coding requires storing the entire code space,
resulting in extremely high computational complexity and making
implementation infeasible.
Joint Source-Channel Coding
Traditional communication systems treat source coding and channel
coding separately, each considering only the statistical characteristics
of its own object. Considering them jointly can yield better
performance. For example, less important information can be compressed
more efficiently, while important information is given stronger
protection; or source coding and channel coding can be jointly designed
so that the coding scheme simultaneously satisfies the requirements of
source compression and channel error correction.
Source-Channel Coding Theorem. If the limit entropy
of a source is less than the capacity of a channel , then there exists a joint
source-channel coding scheme such that the error probability approaches
zero; conversely, if ,
then no matter what coding scheme is adopted, the error probability
cannot be reduced to an acceptably low level.
In other words, if , we
can always find an such that
, first use a source
coding scheme to compress the information to rate , and then use a channel coding scheme
to raise the transmission rate to , thereby achieving reliable
communication.
Linear Block Codes
Block coding refers to encoding an information
sequence of length into a
codeword of length , where . The task is to select out of the possible elements in the -dimensional vector space of -tuples to form the code
space for encoding, and to determine the mapping from the -dimensional space of -tuples to the -dimensional space of -tuples. Different choices of code space
and different mapping algorithms together constitute different block
codes.
Here, the multiplicity of the
space indicates that each element in the space consists of independent code symbols, while the
dimension is the number of basis vectors (each an -tuple) that span the linear space.
The vectors selected for a
-dimensional linear block code
form a subspace. This is motivated by the favorable mathematical
properties of subspaces, which allow optimization of encoding and
decoding algorithms in terms of storage, checking, and performance
evaluation. Compared to nonlinear block codes, a linear block code
requires storing only the basis
vectors, and computing other codewords is simply a matter of matrix
multiplication. Moreover, with the help of the null space, checking a
linear block code can be implemented via matrix multiplication with high
efficiency. Finally, computing the minimum Hamming distance for a
nonlinear block code requires traversing every codeword in the code
space, with a time complexity of ; by exploiting the subspace
structure of linear block codes, the Hamming distance between two codewords and is itself a codeword in the same
linear block code subspace, so computing the minimum Hamming distance
only requires traversing the code space once, with a time complexity of
, greatly simplifying the
computation.
Construction of Linear Block
Codes
From the definition, the code set of a linear block code is
essentially a -dimensional
subspace of an -tuple linear
space. Therefore, selecting basis
vectors of
this subspace, every codeword in the space can be written as a linear
combination of these basis
vectors. Hence, the generator matrix of the linear block code can be formed
from these basis vectors, i.e.,
It is easy to see that . A codeword can be expressed as the product of the
information sequence and the
generator matrix , i.e.,
Since the basis of a subspace is not unique, is also not unique. The same linear
block code can have multiple different generator matrices. Different
bases may generate the same code set; however, since coding involves
both the code set and the mapping, codes with the same code set but
different mappings cannot be considered the same code.
From linear algebra, any generator matrix of an block code can be reduced to the
systematic form through row
operations and column permutations, while still retaining the basis
form. In this case, and are said to be equivalent. That is,
where is the -dimensional identity matrix and is a matrix.
The systematic form of the generator matrix makes encoding simpler:
the first bits of the information
sequence directly become the
first bits of the codeword; the
remaining bits, defined as the
redundancy bits or parity-check bits, are obtained by multiplying the
first bits of the information
sequence by the matrix . This type
of error-correcting code is called a systematic code.
If is not in systematic form, it
is called a nonsystematic code.
It is easy to see that the systematic transformation of the generator
matrix does not change the code set (the subspace is not altered) but
only modifies the mapping rule (the basis has been changed). This
modification is motivated by engineering considerations: if the first
information bits have not
suffered any error, they can be decoded directly; the remaining redundancy bits can then be used to
check whether errors have occurred in the first information bits. This greatly
simplifies circuit design.
Checking of Linear Block
Codes
As mentioned in the overview, linear block codes are easy to check
because they only use dimensions
of the -tuple space, and the
remaining dimensions
constitute its null space. This means that if a vector lies in the code space, it must
satisfy
for every vector in the
null space; conversely, if
does not lie in the code space, then there exists some vector in the null space such that .
By definition, , and
therefore:
For a binary channel,
Syndrome and Standard
Array Decoding
This section discusses the binary channel case. Suppose the
transmitted codeword is and the
received word is ; then
the error pattern is .
However, under the assumed binary channel conditions, we have and
.
From the definition of the parity-check matrix, . Therefore, .
That is, for a fixed parity-check matrix, depends only on the
error pattern and is independent of the transmitted codeword . This leads to the definition
of the syndrome: .
is an -tuple vector, while is an -tuple vector. The syndrome is the projection of the
error pattern onto the
null space; therefore, different error patterns may correspond to the
same syndrome.
Thus, given a syndrome, it follows from the properties of linear
systems of equations or linear spaces that it corresponds to possible error patterns.
Probabilistic decoding selects among these error
patterns the one with the smallest weight as the estimate of , and then obtains .
This method is conceptually simple but computationally extremely
inefficient.
Standard array decoding places the codewords as the first row of the
standard array, with at the
leftmost position. Among the remaining vectors, the vector with the smallest weight is
selected as the first element of the second row, and is placed as
the -th element of the second row.
Then, all vectors in the second row are removed from the vectors.
This process continues until all vectors have been assigned to the
standard array. For each syndrome , the corresponding is found in the standard
array, and then , yielding
.
It can be shown that standard array decoding is valid but not unique.
The standard array has
rows, each called a coset, and the first element of
each coset is called the coset leader. Elements in the
same coset share the same syndrome because they have the same error
pattern. The standard array has
columns, each called a subset, and the first element of
each column is called the subset header.
Code
Distance, Error-Correction Capability, MDC, and Weight Spectrum
In our analysis of the error-correction capability of linear block
codes, we have referred to the minimum Hamming distance without giving a formal
definition. Code Distance refers to the Hamming
distance between any two distinct codewords in the code space.
Minimum Code Distance (MDC) refers to the minimum
Hamming distance between any two distinct codewords in the code
space.
For any linear block code with minimum distance , its error-detection capability is
and its error-correction
capability is . Therefore, the larger the minimum code
distance, the stronger the error-correction capability of the linear
block code.
Hamming weight is the number of nonzero elements in
a codeword. Weight Spectrum refers to the count of
codewords with different Hamming weights in the code space. The weight
spectrum can be used to analyze the performance of linear block codes,
especially under high signal-to-noise ratio conditions, where the
minimum distance and weight spectrum are of great importance for
evaluating the bit error rate. For binary linear block codes, where is the
Hamming weight function and
denotes the XOR operation.
In an linear block code,
since the distance between any two codewords and is also a codeword, when the minimum
distance is , the minimum Hamming
weight of the codewords is also .
Therefore, any set of or more
column vectors in must be
linearly dependent, while any set of fewer than column vectors must be linearly
independent.
Since at most linearly
independent column vectors can be selected from , the minimum code distance satisfies . When , the linear block code is
called a Maximum Distance Separable (MDS) code. MDS
codes have optimal error-correction capability, but their construction
is relatively complex and they are rarely used in practice.
Perfect Codes
Hamming bound. From abstract algebra, it can be
shown that for the entire set of channel codewords, is one of its
cosets. Therefore, the number of distinct syndromes is .
Suppose the error-correction capability of this code is . Then for each syndrome , the corresponding error
pattern must have a
Hamming weight not exceeding .
Therefore, the number of syndromes satisfies:
In other words, if we view the error-correction range of each
codeword as a Hamming ball of radius , these Hamming balls must cover the
entire code space.
If a linear block code satisfies the above inequality with equality,
it is called a perfect code. The existence of perfect
codes is an important research problem; to date, no general construction
method for perfect codes has been found.
Hamming code. Hamming codes are a family of codes
with error-correction capability , and their definition is not limited
to binary. In a binary channel, the parameters of a Hamming code satisfy
, , and . Therefore, the Hamming code
has an error-correction capability of and an error-detection capability of
. The Hamming code is a
perfect code.
The column vectors of the parity-check matrix of a Hamming code are the binary
representations of the numbers
through . Since each column vector
is unique, any two column vectors are linearly independent, and any
three column vectors are linearly dependent, thus satisfying the
condition for a perfect code.
Golay code. The Golay code is a family of codes with
error-correction capability . In
a binary channel, the parameters of the Golay code satisfy , , and . Therefore, the Golay code has
an error-correction capability of and an error-detection capability of
. The Golay code is a
perfect code.
Suppose the information to be transmitted is . First, shift it left by 11 bits to
obtain , then divide it
by the generator polynomial to
obtain the quotient and
remainder . The codeword is
then , where
the generator polynomials are and
.
By appending one parity bit, the Golay code can be extended to a
linear block code, called
the extended Golay code. The parameters of the extended
Golay code satisfy , , , and every codeword has even
weight. Therefore, the extended Golay code has an error-correction
capability of and an
error-detection capability of . The extended Golay code is
not a perfect code.
Cyclic Codes
If for a linear block code , every codeword satisfies
the property that its cyclic right-shifted sequence is
also a codeword, then this linear block code is called a cyclic
code. The codewords of a cyclic code form a subspace of the
-tuple vector space that possesses
the cyclic property.
Describing such a cyclic linear space using matrices is rather
complicated. Therefore, we introduce polynomials modulo to describe cyclic codes.
Representing an -tuple vector
as a
polynomial ,
a cyclic right shift is equivalent to multiplying this polynomial by
and taking the result modulo
, i.e., Furthermore, from abstract algebra, polynomials with integer
coefficients possess the structure of a linear space, so the set of
codewords of a cyclic code is also a linear space. However, while any
cyclic shift of a codeword is still a codeword, not every codeword can
be obtained by cyclically shifting a single codeword.
Generator polynomial. If is an cyclic code, then there exists one
or more monic polynomials such
that , , and . Here, is called the generator polynomial
of the cyclic code. However, such encoding does not produce a systematic
code.
Generator matrix. Once the generator polynomial
is determined, the generator matrix is also determined. The -th row of consists of the coefficients of the
polynomial obtained by cyclically right-shifting by positions. That is,
The generator matrix obtained in this way is not in systematic form.
To convert it to systematic form, consider the following encoding
method: 1. Multiply the message polynomial by , i.e., left-shift by bits; 2. Divide by to obtain the remainder ; 3. Obtain the code polynomial of
the systematic cyclic code: ; 4. Convert the
code polynomial to a codeword.
Assuming , then the
constructed polynomial
satisfies the definition of a cyclic code.
The -th row of the generator
matrix of a systematic cyclic
code consists of the coefficients of the remainder obtained by dividing (with ) by , together with the coefficients of
the message polynomial . That
is,