number of detected 1 bits changes: in either case the parity bit will not correspond to the number of
detected 1s in the block, so the single error is detected. Linear block codes extend this notion by using
a larger number of parity bits to either detect more than one error or correct for one or more errors.
Unfortunately linear block codes, along with convolutional codes, trade their error detection or correction
capability for either bandwidth expansion or a lower data rate, as will be discussed in more detail below.
We will restrict our attention to binary codes, where both the original information and the corresponding
code consist of bits taking a value of either 0 or 1.
8.2.1
Binary Linear Block Codes
A binary block code generates a block of n coded bits (symbols) from k information bits. Both the coded
bits and the information bits take on values of 0 or 1. We call this an (n, k) binary block code. The n
coded bits can take on 2
n
possible values corresponding to all possible combinations of the n binary bits.
We select 2
k
codewords from these 2
n
possibilities to form the code, such that each k bit information
block is uniquely mapped to one of these 2
k
codewords. The rate of the code is R
c
= k/n bits/symbol.
If we assume that symbols are transmitted across the channel at a symbol rate R
s
symbols/second, then
the information rate associated with an (n, k) block code is R
b
= R
c
R
s
= kR
s
/n bits/second. Thus we
see that block coding reduces the data rate compared to what we obtain with uncoded modulation by
the code rate R
c
.
A block code is called a linear code when the mapping of the k information bits to the n coded bits
is a linear mapping. In order to describe this mapping and the corresponding encoding and decoding
functions in more detail, we must first discuss properties of the vector space of binary n-tuples and
its corresponding subspaces. The set of all binary n-tuples B
n
is a vector space over the binary field,
which consists of the two elements 0 and 1. All fields have two operations, addition and multiplication:
for the binary field these operations correspond to binary addition (modulo 2 addition) and standard
multiplication. A subset S of B
n
is called a subspace if it satisfies the following conditions:
1. The all-zero vector is in S.
2. The set S is closed under addition, such that if S
i
S and S
j
S, then S
i
+ S
j
S.
An (n, k) block code is linear if the 2
k
length-n codewords of the code form a subspace of B
n
. Thus, if
C
i
and C
j
are two codewords in an (n, k) linear block code, then C
i
+ C
j
must form another codeword
of the code.
Example 8.1: The vector space B
3
consists of all binary tuples of length 3:
B
3
=
{000, 001, 010, 011, 100, 101, 110, 111}.
Note that B
3
is a subspace of itself, since it contains the all zero vector and is closed under addition.
Determine which of the following subsets of B
3
form a subspace:
· S
1
=
{000, 001, 100, 101}
· S
2
=
{000, 100, 110, 111}
· S
3
=
{001, 100, 101}
Solution: It is easily verified that S
1
is a subspace, since it contains the all-zero vector and the sum
of any two tuples in S
1
is also in S
1
. S
2
is not a subspace since it is not closed under addition, as
177