Assignment 6

Telecom ParisTech
Prof. Aslan Tchamkerten
COM224, Coding Theory
January 2014
A SSIGNMENT 6 - S OLUTIONS
Exercise 1. Determine the parameters (n, k, d) of the binary code
C = {00001100, 00001111, 01010101, 11011101}
Solution. n = 8, k = 3, d = 2
Exercise 2. For each of the following codes
C1 = {00000, 01010, 00001, 01011, 01001}
C2 = {000000, 101000, 001110, 100111}
C3 = {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111}.
tell if it is linear and evaluate the parameters (n, k, d).
Solution. C1 : since it contains an odd number of vectors it cannot be a linear subspace of F52 . We
have (n = 5, M = 5, d = 1).
C2 : since (101000) + (001110 = 100110) ∈
/ C2 the code is not linear. We have (n = 6, k = 2, d =
2).
C3 : a = (1100), b = (0110), c = (0011) form a basis of C within F42 , d = 2, its error correction
capability is zero, but it can detect up to 1 error.
Exercise 3. Is the code C = {000, 110, 011, 101} MDS?
Solution. n = 3, k = 2, d = 2, hence d = n − k + 1 and it is an MDS code.
Exercise 4. In this exercise we show the existence of linear codes over [q], q ≥ 2, which achieve the
Gilbert-Varshamov bound. To that aim we show the existence of a full rank generator matrix G of
dimension k × n such that
k = (1 − Hq (δ) − ε)n
and such that
wt(mG) ≥ d
for any m ∈ Fkq .
1. Pick G randomly such that each of its elements is independently chosen with the uniform
distribution over [q]. Fix m 6= 0. We first show that for such a random G, mG is a uniformly
chosen vector over [q]n .
(a) Let Xi denote the i-th symbol of the n-vector mG. Show that Xi is independent of Xj
for i 6= j.
1
P
(b) Let Xi = kj=1 mj Gji . Since m 6= 0, at least one of its elements is non-zero. Say m`
P
is the first non-zero element. Thus we can write Xi = m` G`i + kj=`+1 mj Gji . Using
this, show that Xi is uniformly distributed over [q] by conditioning over the possible
realizations of G`+1,i , G`+2,i , . . . , Gk,i .
2. Deduce that
P r[wt(mG) < d] ≤
q nHq (δ)
.
qn
Hint. V olq (d − 1, n) ≤ q nHq (δ) .
3. Deduce that P r(∃m : wt(mG) < d) ≤ q −εn for some appropriate choice of k.
4. Conclude the proof.
Solution.
1. (a) Holds since Xi and Xj involve different columns of G and that these columns
are independent.
(b) We have
P (X` = x) =
=
1
q k−`
1
q k−`
X
P (X` = x|(G`+1,i , G`+2,i , . . . , Gk,i ) = (g`+1,i , g`+2,i , . . . , gk,i ))
(g`+1,i ,g`+2,i ,...,gk,i )
X
(g`+1,i ,g`+2,i ,...,gk,i )
1
q
1
= .
q
2. Holds because of 1.
3. Holds by a union bound over m and by letting k = (1 − Hq (δ) − ε)n.
4. By the previous step, and because the matrix G is uniformly distributed, as n → ∞ the
fraction of the matrices satisfying the desired property tends to one.
Exercise 5. Show that the concatenation of two linear codes gives a linear code. Hint. construct the
generator matrix.
Solution. Let C be the concatenated code obtained from Cin and Cout with generator matrix Gi and
Go , respectively. Then Cin (Cout (m)) = Cin (m · Go )) = m · Go Gi . Hence C is a linear code with
generator matrix Go Gi .
Exercise 6. We will show a way to design an explicit code which achieves positive rate and relative
minimum distance with “low complexity.” By low complexity we mean subexponentially in the
block length.
From the previous exercise there exists linear codes over [q] whose asymptotic rate r =
limn→∞ k(n)
and relative minimum distance δ = limn→∞ d(n)
satisfy
n
n
r ≥ 1 − Hq (δ).
2
1. Argue that to find a length n code whose rate and relative minimum distance satisfy
r ≥ 1 − Hq (δ) − ε
it takes q O(kn) time, as opposed to q O(q
k n)
time if the code has no structure.
2. Consider concatenating a linear code approaching the GV bound and a Reed Solomon code.
Show that such a construction yields an asymptotic rate
δ
R ≥ sup r 1 − −1
Hq (1 − r − ε)
r≥0
for any ε > 0, where δ represents the relative minimum distance of the concatenated code and
where r denotes the rate of the inner code. This bound is called the Zyablov bound.
3. Plot and compare the Zyablov bound and the Gilbert-Varshamov lower bounds (rate as a
function of relative minimum distance).
4. Argue that it is possibe to construct an explicit code achieving the Zyablov bound with time
complexity N O(log N ) where N denotes the length of the concatenated code.
Hence, although the Zyablov bound is lower than the GV bound, it is easier to construct a code
that achieves the Zyablov bound (by concatenation) than to construct a linear code achieving
the GV bound (which takes O(q N ) time).
Solution.
1. Given a k × n generator matrix of a linear code, it takes it takes O(q k kn) time to
generate each codeword (there are q k codewords and each of them takes O(kn) to be written
using the generator matrix). Therefore it takes O(q k kn) to evaluate the minimum distance of
a linear code. Since there are q O(kn) possible matrices, it takes q O(kn) O(q k kn) = q O(kn) to find
a code with the desired minimum distance
Follows from the fact that a linear code is characterized by its generator k × n q-ary matrix.
2. Let Cin approach the GV bound, hence
δin ≥ Hq−1 (1 − r − ε).
Let Cout be a RS code therefore satisfying
δout = 1 − R.
The concatenated code (R, δ) thus satisfies
R = rR
and
δ ≥ (1 − R)Hq−1 (1 − r − ε).
3
Expressing R as a function of δ and r we get
R≥1−
Therefore we can achieve
δ
.
Hq−1 (1 − r − ε)
R≥r 1−
δ
−1
Hq (1 − r − ε)
and maximizing over r yields the desired result.
3. The Zyablov bound (rate vs relative minimum distance) is lower than the GV bound for any
relative minimum distance within (0, 1/2).
2
4. There are q k /r linear codes of rate r = k/n. Given such a code, it takes O(q k (k 2 /r)k/r) =
q O(k) to generate all the codewords and compute their minimum weight. Therefore to find a
linear code with desired rate and minimum distance it takes
qk
2 /r
q O(k) = q O(k
2)
Since the linear code is used as an inner code we have k = log N where N = q t denotes the
size of the RS code. Hence
2
2
q O(k ) = q O((log N ) ) = N O(log N )
which is upper bounded by N O(log N ) where N = nN = N log N denotes the length of the
concatenated code.
Exercise 7. Let C1 and C2 be an [n, k1 , d1 ] and an [n, k2 , d2 ] code, respectively. Let C1 |C2 be the
code consisting of all codewords of the form
(u, u + v) = (u1 , u2 , . . . , un , u1 + v1 , u2 + v2 , . . . , un + vn )
with u = (u1 , u2 , . . . , un ) ∈ C1 and v = (v1 , v2 , . . . , vn ) ∈ C2 . Show that C1 |C2 is an [2n, k1 +
k2 , min{2d1 , d2 }] code. Hint. consider the cases v = v 0 and v 6= v 0 . For the second case use the
triangle inequality.
Solution. That C1 |C2 has length 2n and dimension k1 + k2 is obvious. Let us consider the minimum
distance. If a = u, u + v and b = u0 , u0 + v 0 are different codewords then d(a, b) = d(u, u0 ) + d(u +
v, u0 + v 0 ). Using this we get
• If v = v 0 then d(a, b) ≥ 2d1
• If v 6= v 0 then
d(a, b) = wt(u − u0 ) + wt(u + v − u0 − v 0 )
= wt(u0 − u) + wt(u + v − u0 − v 0 )
≥ wt(u − u0 + u + v − u0 − v 0 )
= wt(v − v 0 )
≥ d2
4
This shows that the minimum distance of C1 |C2 is ≥ min{2d1 , d2 } and it is easy to check that this
bound is indeed achievable.
5

Download Report