14:332:548, E
or Control Coding
Homework 4
Rutgers University
1. Let F be the ternary field GF (3) and let C be a linear code over F that is generated by
G =
(
2 1 2 1
1 1 1 0
)
(a) List all the codewords of C.
(b) Find a systematic generator matrix and a parity check matrix of C.
(c) Compute the minimum distance of C.
(d) A codeword of C is transmitted through noisy channel and the word y = (1, 1, 1, 1) is received.
Find all the codewords of C that can be produced as an output by a nearest-codeword decode
for C when applied to y.
(e) Suppose that the encoding is ca
ied out by the mapping u −→ uG. A nearest-codeword
decoder for C is applied to the word y in part (d) to produce a codeword ĉ. Denote by û
the information word and that is associated with ĉ. Can any of the entries of û be uniquely
determined – regardless of which nearest-codeword decoder is used?
(f) Repeat part (e) for the case where a systematic generator matrix replaces G in the encoding.
2. Let C be a linear code over F = GF (2) with a parity check matrix
H =
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
(a) What is the parameters n, k, and d of C?
(b) Write a generator matrix of C.
(c) Find the largest integer t such that every pattern of up to t e
ors will be decoded co
ectly by a
nearest-codeword decoder for C.
(d) A codeword of C is transmitted through an additive channel (F, F, Prob) and the word y =
(1, 0, 1, 0, 1, 0, 1, 0, 1) is received. What will be the respective output of a nearest-codeword
decoder for C when applied to y?
(e) Given that the answer to part (d) is the co
ect codeword, how many e
ors does a nearest-
codeword decoder co
ect in this case? And how is this number consistent with the value t in
part (c)?
1
3. Show that the number of distinct generator matrices of a linear [n, k, d] code over F = GF (q) is∏k−1
i=0 (q
k − qi).
Hint: First show that the sought number equals to the number of k× k nonsingular matrices over F .
Next, count the latter matrices
4. Let G be a k × k generator matrix of a linear code C ≠ {0} over a field F . Show that the minimum
distance of C is the largest integer d such that every k × (n− d+ 1) sub matrix of G has rank k.
5. Let (a1, a2, ..., ak) be a nonzero vector over F = GF (q) and consider the mapping f : F k −→ F
defined by f(x1, x2, ..., xk) =
∑k
i=1 aixi. Show that each element of F is the image under f of
exactly qk−1 vectors in F k.
6. (a) Let C be a linear (n, k, d) code over F = GF (q) and let T be a qk×n a
ay whose rows are the
codewords of C. Show that each element of F appears in every nonzero column in T exactly
qk−1 times.
Hint: Use Problem 5.
(b) (The Plotkin bound for linear codes) Show that every linear (n, k, d) code over F = GF (q)
satisfies the inequality
d ≤ n(q − 1)q
k−1
qk − 1
Hint: Using Part (a), start by showing that the average Hamming weight of the qk − 1 nonzero
codewords in the code is at most n(q − 1)qk−1/(qk − 1).
7. (First-order Reed-Muller codes) Let F = GF (q) and for a positive integer m let n = qm. The first-
order Reed-Muller code over F is defined as the linear (n,m+1) code C over F with an (m+1)×n
generator matrix whose columns range over all the vectors in Fm+1 with a first entry equaling 1.
(Observe that for q = 2, the first-order Reed-Muller code is the dual code of the extended Hamming
code)
(a) Show that the minimum distance of C equals q(qm−1) and this number is the Hamming weight
of q(qm− 1) codewords in C. What are the Hamming weights of the remaining q codewords in
C?
Hint: Use problem 5
(b) Show that no linear (n,m+1) code over F can have minimum distance greater than qm−1(q−
1).
Hint: Use the Plotkin bound.
(c) The shortened first-order Reed-Muller code over F is defined as the linear (n − 1,m) code C′
over F with an m× (n−1) generator matrix whose columns range over all the nonzero vectors
in Fm. Show that C′ can be obtained from C by a shortening operation that deletes the same
single coordinate in all the codewords in C.
(d) Show that every nonzero codeword in the shortened code C′ has Hamming weight qm−1(q− 1)
and verify that the shortened code C′ attains the Plotkin bound.
2