Sample Solution

MMTE-005 Solved Assignment | CODING THEORY | M.Sc. MACS | IGNOU Sample Solution

MMTE-005 Solved Assignment 2024

CODING THEORY

(Valid from January 1st, 2024 – December 31st, 2024)

Which of the following statements are true and which are false? Justify your answer with a short proof or a counterexample.
i) If the weight of each element in the generating matrix of a linear code is at least $r$ , the mininum distance of the code is at least $r$ .
ii) There is no linear self orthogonal code of odd length.
iii) There is no 3-cyclotomic coset modulo 121 of size 25.
iv) There is no duadic code of length 15 over $F_{2}$ .
v) There is no LDPC code with parameters $n = 16, c = 3$ and $r = 5$ .
a) Which of the following binary codes are linear?
i) $C = {(0, 0, 0, 0), (1, 0, 1, 0), (0, 1, 1, 0), (1, 1, 1, 0)}$
ii) $C = {(0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}$

Justify your answer.
b) Find the minimum distance for each of the codes.
c) For each of the linear codes, find the degree, a generator matrix and a parity check matrix.(3)
3) Let

C_{1}

and

C_{2}

be two binary codes with generator matrices

G_{1} = [\begin{array}{llll} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{array}], G_{2} = [\begin{array}{llll} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array}]

respectively.
a) Find the minimum distance of both the codes.
b) Find the generator matrix of the code

C = {(u ∣ u + v) ∣ u \in C_{1}, v \in C_{2}}

obtained from

C_{1}

and

C_{2}

(u ∣ u + v)

construction. Also, find the minimum distance of

C

a) If $x, y \in F_{2}^{n}$ , show that

w t (x + y) = w t (x) + w t (y) - 2 w t (x \cap y)

where

x \cap y

is the vector in

F_{2}^{n}

which has 1s precisely at those positions where

x

and

y

have 1s.
(Hint: Let

x = (x_{1}, x_{2}, \dots, x_{n})

and

y = (y_{1}, y_{2}, \dots, y_{n})

. Suppose

n_{1} = | {i ∣ x_{i} = y_{i} = 1} |, n_{2} = | {i ∣ x_{i} = 1, y_{i} = 0} |, n_{3} = | {i ∣ x_{i} = 0, y_{i} = 1} |

Observe that

w t (x) = n_{1} + n_{2}

and

w t (y) = n_{1} + n_{3} .)

b) Let

C

be a binary code with a generator matrix each of whose rows has even weight. Show that, every codeword of

C

has even weight.
(Hint: Why is it enough to prove that sum of vectors of even weight in

F_{2}^{n}

is a vector of even weight? )
c) Show that, if

x \in F_{3}^{n}

w t (x) \equiv x \cdot x (mod 3)

Deduce that, if

C

is a ternary self orthogonal code, the weight of each codeword is divisible by 3 .
(Hint: Observe that

x^{2} = 1

for all

x \neq 0 \in F_{3}

)
d) The aim of this exercise is to show that every binary repetition code of odd length is perfect.
i) Find the value of

t

and

d

for a perfect code of length

2 m + 1, m \in N

.
ii) Show that

\sum_{i = 0}^{m} (\binom{2 m + 1}{i}) = 2^{2 m}

(Hint: Start with the relation

2^{2 m + 1} = \sum_{i = 0}^{2 m + 1} (\binom{2 m + 1}{i})

iii) Deduce that every repetiition code of odd length is perfect.

Let $α$ be a root of $x^{2} + 1 = 0$ in $F_{9}$ .
a) Check whether $α$ is a primitive element of $F_{9}$ . If it is not a primitive element in $F_{9}$ find a primitive element $γ$ in $F_{9}$ in terms of $α$ .
b) Make a table similiar to Table 5.1 on page 184 for $F_{9}$ with the primitive element $γ$
c) Factorise $x^{8} - 1$ over $F_{3}$ .
d) Find all the possible generator polynomials of a $[8, 6]$ cyclic code.
a) Let $C_{1}$ and $C_{2}$ be cyclic codes over $F_{q}$ with generator polynomials $g_{1} (x)$ and $g_{2} (x)$ , respectively. Prove that $C_{1} \subseteq C_{2}$ if and only if $g_{2} (x) ∣ g_{1} (x)$ .
b) Over $F_{2}, (1 + x) ∣ (x^{n} - 1)$ . Let $C$ be the binary cyclic code $(1 + x)$ of length $n$ . Let $C_{1}$ be any binary cyclic code of length $n$ with generator polynomial $g_{1} (x)$ .
i) What is the dimension of $C$ ?
ii) Let $w$ be subspace of $F_{2}^{n}$ containing all the vectors of even weight. Prove that $W$ has dimension $n - 1$ . (Hint: Consider the map $w : F_{2}^{n} \to F_{2}$ given by

w ((a_{1}, a_{2}, \dots, a_{n})) = a_{1} + a_{2} + \dots + a_{n} .)

iii) Prove that

C

is the vector space of all vectors in

F_{2}^{n}

with even weight.
iv) If

C_{1}

has only even weight codewords, what is the relationship between

(1 + x)

and

g_{1} (x) ?

v) If

C_{1}

has some odd weight codewords, what is the relationship between

1 + x

and

g_{1} (x) ?

7) a) Let

C

be the ternary

[8, 3]

narrow-sense BCH code of designed distance

δ = 5

, which has defining set

T = {1, 2, 3, 4, 6}

. Use the primitive root 8 th root of unity you chose in 4a) to avoid recomputing the the table of powers. If

g (x) = x^{5} - x^{4} + x^{3} + x^{2} - 1

is the generator polynomial of

C

and

y (x) = x^{7} - x^{6} - x^{4} - x^{3}

is the received word, find the transmitted codeword.
b) Let

C

be the

[5, 2]

ternary code generated by

G = (\begin{array}{lllll} 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{array})

Find the weight enumerator

W_{C} (x, y)

C

.
c) Find the generating idempotents of duadic codes of length

n = 23

over

F_{3}

.
(Hint: Mimic example 6.1.7.)
8) a) Let

C = {0000, 1113, 2222, 3331, 0202, 1313, 2020, 3131, 0022, 1131, 2200, 3313, 0220, 1333, 2002, 3111}

be the

Z_{4}

-linear code. Find the Gray image of

C

.
b) Draw the Tanner graph of the code

C

with parity check matrix

[\begin{array}{llllllllll} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \end{array}] .

c) Find the convolutional code for the message 11011. The convolutional encoder is given in Fig. 1.

Expert Answer:

Question:-1

Which of the following statements are true and which are false? Justify your answer with a short proof or a counterexample.

i) If the weight of each element in the generating matrix of a linear code is at least

r

, the minimum distance of the code is at least

r

ii) There is no linear self-orthogonal code of odd length.
iii) There is no 3-cyclotomic coset modulo 121 of size 25.
iv) There is no duadic code of length 15 over

F_{2}

.
v) There is no LDPC code with parameters

n = 16, c = 3

, and

r = 5

Answer:

i) If the weight of each element in the generating matrix of a linear code is at least $r$ , the minimum distance of the code is at least $r$ .

False.

Counterexample:
Consider a code over

F_{2}

with a generating matrix

G = (\begin{matrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{matrix}) .

The weights of the rows are both 3, but the minimum distance of the code is 2 (since

v_{1} + v_{2} = (1, 0, 0, 1)

has weight 2). Therefore, the weight of the rows does not guarantee that the minimum distance is at least

r

ii) There is no linear self-orthogonal code of odd length.

True.

Proof:
A code

C

is self-orthogonal if for every pair of codewords

x, y \in C

, the inner product

x \cdot y = 0

. In a linear self-orthogonal code, the inner product of each codeword with itself must also be zero, i.e.,

x \cdot x = 0

, meaning that the weight of each codeword must be even (since over

F_{2}

, the inner product is just the sum of the components mod 2, and an even number of 1s is required to make the inner product zero).

However, if the length of the code is odd, the weight of the codewords cannot always be even (since it is impossible to have all codewords of odd length being of even weight), so no such self-orthogonal code exists.

iii) There is no 3-cyclotomic coset modulo 121 of size 25.

True.

Proof:
Cyclotomic cosets modulo

n

are formed by taking powers of some integer

b

modulo

n

, and their size is determined by the smallest integer

m

such that

b^{m} \equiv 1 \mod n

. For

n = 121 = 11^{2}

, we consider the powers of 3 modulo 121.

By calculating powers of 3 modulo 121, we see that no cyclotomic coset of size 25 arises. Cyclotomic coset sizes are determined by the order of elements in the multiplicative group modulo 121, and none have size 25.

iv) There is no duadic code of length 15 over $F_{2}$ .

True.

Proof:
Duadic codes exist only for lengths that are divisible by 4 or for lengths that are powers of 2. Since 15 is neither divisible by 4 nor a power of 2, there is no duadic code of length 15 over

F_{2}

v) There is no LDPC code with parameters $n = 16, c = 3$ , and $r = 5$ .

True.

Proof:
For an LDPC (Low-Density Parity-Check) code with parameters

n = 16

(length),

c = 3

(column weight, i.e., the number of 1s in each column of the parity-check matrix), and

r = 5

(row weight, i.e., the number of 1s in each row of the parity-check matrix), we need to satisfy the condition

n \times c = m \times r

, where

m

is the number of rows in the parity-check matrix. Here

n = 16

c = 3

, and

r = 5

, so we would need

16 \times 3 = m \times 5

, which simplifies to

m = 48 / 5 = 9.6

, which is not an integer. Hence, no such LDPC code exists.

Question:-2(a)

Which of the following binary codes are linear?

C = {(0, 0, 0, 0), (1, 0, 1, 0), (0, 1, 1, 0), (1, 1, 1, 0)}

ii)

C = {(0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}

Justify your answer.

Answer:

To determine if a binary code is linear, we need to check two properties:

The code must contain the zero codeword (all zeros).
The code must be closed under addition (modulo 2) of any two codewords.

i) $C = {(0, 0, 0, 0), (1, 0, 1, 0), (0, 1, 1, 0), (1, 1, 1, 0)}$

Contains the zero codeword?
Yes, $(0, 0, 0, 0)$ is in $C$ .
Closed under addition?
Let’s check the pairwise sums of the codewords (mod 2):
- $(1, 0, 1, 0) + (0, 1, 1, 0) = (1, 1, 0, 0)$ (not in $C$ ),
- $(1, 0, 1, 0) + (1, 1, 1, 0) = (0, 1, 0, 0)$ (not in $C$ ),
- $(0, 1, 1, 0) + (1, 1, 1, 0) = (1, 0, 0, 0)$ (not in $C$ ).
Since the code is not closed under addition, it is not linear.

ii) $C = {(0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}$

Contains the zero codeword?
Yes, $(0, 0, 0)$ is in $C$ .
Closed under addition?
Let’s check the pairwise sums of the codewords (mod 2):
- $(1, 1, 0) + (1, 0, 1) = (0, 1, 1)$ (which is in $C$ ),
- $(1, 1, 0) + (0, 1, 1) = (1, 0, 1)$ (which is in $C$ ),
- $(1, 0, 1) + (0, 1, 1) = (1, 1, 0)$ (which is in $C$ ).
All sums of the codewords are in $C$ , so it is closed under addition.

Since both conditions are satisfied,

C

is linear.

Final Answer Summary:

i) Not linear
ii) Linear

Back to Course

Next Lesson

MMTE-005 Solved Assignment | CODING THEORY | M.Sc. MACS | IGNOU

Sample Solution

MMTE-005 Solved Assignment 2024

CODING THEORY

(Valid from January 1st, 2024 – December 31st, 2024)

Expert Answer:

Question:-1

Which of the following statements are true and which are false? Justify your answer with a short proof or a counterexample.

Answer:

i) If the weight of each element in the generating matrix of a linear code is at least r r rrr, the minimum distance of the code is at least r r rrr.

ii) There is no linear self-orthogonal code of odd length.

iii) There is no 3-cyclotomic coset modulo 121 of size 25.

iv) There is no duadic code of length 15 over F 2 F 2 F_(2)\mathbf{F}_2F2.

v) There is no LDPC code with parameters n = 16 , c = 3 n = 16 , c = 3 n=16,c=3n=16, c=3n=16,c=3, and r = 5 r = 5 r=5r=5r=5.

Question:-2(a)

Which of the following binary codes are linear?

Answer:

ii) C = { ( 0 , 0 , 0 ) , ( 1 , 1 , 0 ) , ( 1 , 0 , 1 ) , ( 0 , 1 , 1 ) } C = { ( 0 , 0 , 0 ) , ( 1 , 1 , 0 ) , ( 1 , 0 , 1 ) , ( 0 , 1 , 1 ) } C={(0,0,0),(1,1,0),(1,0,1),(0,1,1)}\mathscr{C} = \{(0,0,0), (1,1,0), (1,0,1), (0,1,1)\}C={(0,0,0),(1,1,0),(1,0,1),(0,1,1)}

Final Answer Summary:

i) If the weight of each element in the generating matrix of a linear code is at least $r$ , the minimum distance of the code is at least $r$ .

iv) There is no duadic code of length 15 over $F_{2}$ .

v) There is no LDPC code with parameters $n = 16, c = 3$ , and $r = 5$ .

ii) $C = {(0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}$