ECE 460, Fall 2020: Computational Assignment #5
( optional, extra credit )
Due: Sunday, Dec. 13, 2020 at 11:59 pm
In the instructions below, MATLAB is assumed, but similar functionality can be coded using
Octave or Python with the SciPy li
ary.
Part I: Background on Linear Block Codes (no questions in this part)
1. An (n, k) block code C over a finite alphabet A of symbols is a set of |A|k vectors c ∈ An,
which are called codewords. Given a code C, an encoder maps a message vector m ∈ Ak to
a codeword c ∈ C. The rate of the code is given by R = k/n and represents the number of
information bits transmitted per channel use. Note that R < 1, since n > k.
2. The Hamming distance between any two sequences x = (x1, . . . , xn) and y = (y1, . . . , yn) ove
a finite alphabet A is the number of positions in which the co
esponding elements differ. The
minimum distance dmin of a code C is the smallest Hamming distance between two codewords.
A code C can co
ect up to tc = b(dmin − 1)/2c e
ors and detect up to td = dmin − 1 e
ors.
3. For simplicity, we shall assume a binary alphabet, A = {0, 1} and modulo-2 arithmetic.
Under these assumptions block codes are called binary block codes. In modulo-2 arithmetic,
the addition operator + is defined by
0 + 0 = 0; 0 + 1 = 1 + 0 = 1; 1 + 1 = 0
and multiplication operator · is defined by
0 · 0 = 0 · 1 = 1 · 0 = 0; 1 · 1 = 1.
4. A binary (n, k) linear block code is a k-dimensional subspace of an n-dimensional vector space
Vn = {(x1, . . . , xn) : xi ∈ {0, 1}}, which we can also write as {0, 1}n. One can verify that Vn
satisfies the properties of a vector space over the scalar field defined by {0, 1} and modulo-2
arithmetic.
5. Suppose C is an (n, k) linear code as defined in 4. A binary k × n matrix G whose rows
span the vector space C is called a generator matrix for C. Conversely, given a matrix G
with entries in {0, 1}, the vector space spanned by the rows of G is refe
ed to as the code
generated by G. The encoder for a binary linear (n, k) code with generator matrix G maps a
k-bit message m to an n-bit codeword c as follows: c = mG. A systematic generator for an
(n, k) has the form
G = [P Ik], (1)
where Ik is the k× k identity matrix and P is a k× (n− k) matrix that generates the parity
its. With a systematic generator, the encoding operation is
c = mG = m [P Ik] = [mP m]. (2)
Thus, the codeword can be divided into two parts: the part mP consisting of the parity check
its and the part m consisting of the message bits. The parity bits represent the redundant
information that is added to the k-bit message m.
1
Free Hand
Free Hand
6. Let T denote matrix transpose and 0 denote a vector or matrix of all zeros depending on the
context. Given an (n, k) binary linear code C, a k×n binary matrix H with the property that
cHT = 0 for each codeword c ∈ C is called a parity-check matrix for C. This in turn implies
the GHT = 0. When the generator matrix has the systematic form in (1), the co
esponding
parity-check matrix has the form
H = [In−k P
T ]. (3)
The parity-check matrix H is used to decode the received codeword. If c ∈ C is a codeword,
a received codeword is given by r = c + n, where n is an e
or pattern which is caused by
the channel. A received codeword can be decoded by computing a syndrome s as follows
s = rHT . Note that
s = (c + n)HT = cHT + nHT = nHT . (4)
Thus, the syndrome does not depend on the codeword that was sent; it depends only on
the e
or pattern n. Each e
or pattern n that can be determined by the linear block code
co
esponds to a unique syndrome.
7. A syndrome decoding table can be constructed by enumerating the possible e
or patterns
and computing the co
esponding syndromes. This table consists of 2n−k entries, where each
entry consists of an e
or pattern and the syndrome. Syndrome decoding is accomplished by
finding the e
or pattern n̂ co
esponding to the received syndrome in the syndrome decoding
table. The received codeword is then computed as
ĉ = r + n̂. (5)
For codes of large dimension, the syndrome decoding table can be impractically large. There-
fore, it is desirable to consider linear block codes with additional structure. In Part II, we
will look at Hamming codes, which are binary linear block codes with a special structure.
Part II: Hamming Codes
Hamming codes (named after Richard W. Hamming) were among the first important e
or-
co
ecting codes to be invented. Hamming codes belong to the family of binary linear block codes,
ut have additional structure that enables a relatively simple decoding procedure as we shall see
elow.
1. A Hamming code is a binary linear (n, k) code such that n = 2m − 1 and k = 2m −m − 1
for some integer m ≥ 2 and a parity check matrix H can be obtained by writing all possible
inary m-tuples, except the all-zero tuple, as the columns of H.
(a) List the Hamming (n, k) codes obtained for m = 3, 4, 5, 6, and 7 and the co
esponding
code rates R.
(b) What can you say about the rates of the Hamming codes as m increases?
(c) When m = 2, we have a Hamming (3, 1) code. This is equivalent to the repetition code
discussed in HW#4, Problem 2(b). Find a parity-check matrix H and the co
esponding
generator G for the Hamming (3, 1) code in the systematic forms given in (3) and (1),
espectively.
2
2. We shall focus on the Hamming (7, 4) code, obtained when m = 3. The following is a parity-
check matrix H for the (7, 4) Hamming code with the systematic form given in (3):
H =
 XXXXXXXXXX1 0 1 1
XXXXXXXXXX
 . (6)
Note that there are other parity-check matrices for the (7, 4) Hamming code satisfying (3);
i.e., (6) is not unique. Find a systematic generator of the form (1) co
esponding to the
parity-check matrix in (6).
3. Write a MATLAB Hamming (7, 4) encoder function that takes as input a 4-bit message vecto
m and returns a 7-bit codeword c using the generator matrix obtained in 3.
(a) Use the encoder function to generate the set of all (7, 4) Hamming codewords based on
this generator.
(b) What is the minimum distance dmin of this Hamming code?
(c) Based on Part I.2, how many bit e
ors tc can be co
ected using a (7, 4) Hamming code?
How many e
ors td can this code detect?
4. Write a MATLAB Hamming (7, 4) decoder function that takes as input a 7-bit received vecto
and returns an estimate ĉ of the transmitted codeword using the parity-check matrix H
from part 4 according to the following procedure:
1) Compute the syndrome s = rHT .
2) If s = 0, set n̂ = 0. Go to 4).
3) Locate the unique column of H which is equal to s and call it column i. Set n̂ = ei,
where ei is a 7-bit binary vector with all zeros except for a single 1 in the ith coordinate.
4) Set ĉ = r + n̂.
5. Write a MATLAB script to simulate transmission of a bit stream coded using a Hamming
(7, 4) code over a binary symmetric channel (BSC) assuming a crossover probability
p = Q
(√
2E
N0
)
. (7)
The input bit stream is a random i.i.d. sequence of bits in {0, 1}, which are assumed to be
equilikely. Use the encoder and decoder functions from parts 3. and 4., respectively.
(a) Plot the estimated probability of bit e
or Pe as a function of E
N0. Generate a
sufficient number of bits to obtain accurate estimates of the bit e
or probability from
your simulation.
(b) For comparison purposes, on the same graph plot the bit e
or probability of uncoded
transmission over the BSC as a function E
N0 using (7) as was done in Comp. Assign-
ment #2 Part II.5. What observations can you make from these plots?
What to hand in: Your submission should consist of
(1) a PDF file, which includes answers to the questions in Part II above, the requested plots, and
a copy of your code,
(2) source code files (e.g., .m files for MATLAB/Octave or .py files for Python) in text format.
3