Sample Solution

MMTE-005 Solved Assignment 2024

CODING THEORY

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

  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 r rrr, the mininum 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.
  2. 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 ) } C = { ( 0 , 0 , 0 , 0 ) , ( 1 , 0 , 1 , 0 ) , ( 0 , 1 , 1 , 0 ) , ( 1 , 1 , 1 , 0 ) } C={(0,0,0,0),(1,0,1,0),(0,1,1,0),(1,1,1,0)}\mathscr{C}=\{(0,0,0,0),(1,0,1,0),(0,1,1,0),(1,1,1,0)\}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 ) } 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)}
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 C 1 C_(1)\mathscr{C}_1C1 and C 2 C 2 C_(2)\mathscr{C}_2C2 be two binary codes with generator matrices
G 1 = [ 1 0 0 1 0 1 0 0 0 0 1 1 ] , G 2 = [ 1 0 0 1 0 1 1 0 ] G 1 = 1      0      0      1 0      1      0      0 0      0      1      1 , G 2 = 1      0      0      1 0      1      1      0 G_(1)=[[1,0,0,1],[0,1,0,0],[0,0,1,1]],G_(2)=[[1,0,0,1],[0,1,1,0]]G_1=\left[\begin{array}{llll} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{array}\right], G_2=\left[\begin{array}{llll} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array}\right]G1=[100101000011],G2=[10010110]
respectively.
a) Find the minimum distance of both the codes.
b) Find the generator matrix of the code
C = { ( u u + v ) u C 1 , v C 2 } C = ( u u + v ) u C 1 , v C 2 C={(u∣u+v)∣uinC_(1),vinC_(2)}\mathscr{C}=\left\{(\mathbf{u} \mid \mathbf{u}+\mathbf{v}) \mid \mathbf{u} \in \mathscr{C}_1, \mathbf{v} \in \mathscr{C}_2\right\}C={(uu+v)uC1,vC2}
obtained from C 1 C 1 C_(1)\mathscr{C}_1C1 and C 2 C 2 C_(2)\mathscr{C}_2C2 by ( u u + v ) ( u u + v ) (u∣u+v)(\mathbf{u} \mid \mathbf{u}+\mathbf{v})(uu+v) construction. Also, find the minimum distance of C C C\mathscr{C}C.
  1. a) If x , y F 2 n x , y F 2 n x,yinF_(2)^(n)\mathbf{x}, \mathbf{y} \in \mathbf{F}_2^nx,yF2n, show that
w t ( x + y ) = w t ( x ) + w t ( y ) 2 w t ( x y ) w t ( x + y ) = w t ( x ) + w t ( y ) 2 w t ( x y ) wt(x+y)=wt(x)+wt(y)-2wt(xnny)w t(\mathbf{x}+\mathbf{y})=w t(\mathbf{x})+w t(\mathbf{y})-2 w t(\mathbf{x} \cap \mathbf{y})wt(x+y)=wt(x)+wt(y)2wt(xy)
where x y x y xnny\mathbf{x} \cap \mathbf{y}xy is the vector in F 2 n F 2 n F_(2)^(n)\mathbf{F}_2^nF2n which has 1s precisely at those positions where x x x\mathbf{x}x and y y y\mathbf{y}y have 1s.
(Hint: Let x = ( x 1 , x 2 , , x n ) x = x 1 , x 2 , , x n x=(x_(1),x_(2),dots,x_(n))\mathbf{x}=\left(x_1, x_2, \ldots, x_n\right)x=(x1,x2,,xn) and y = ( y 1 , y 2 , , y n ) y = y 1 , y 2 , , y n y=(y_(1),y_(2),dots,y_(n))\mathbf{y}=\left(y_1, y_2, \ldots, y_n\right)y=(y1,y2,,yn). 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 } | 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 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}|n_1=\left|\left\{i \mid x_i=y_i=1\right\}\right|, n_2=\left|\left\{i \mid x_i=1, y_i=0\right\}\right|, n_3=\left|\left\{i \mid x_i=0, y_i=1\right\}\right|n1=|{ixi=yi=1}|,n2=|{ixi=1,yi=0}|,n3=|{ixi=0,yi=1}|
Observe that w t ( x ) = n 1 + n 2 w t ( x ) = n 1 + n 2 wt(x)=n_(1)+n_(2)w t(\mathbf{x})=n_1+n_2wt(x)=n1+n2 and w t ( y ) = n 1 + n 3 . ) w t ( y ) = n 1 + n 3 . {:wt(y)=n_(1)+n_(3).)\left.w t(\mathbf{y})=n_1+n_3.\right)wt(y)=n1+n3.)
b) Let C C C\mathscr{C}C be a binary code with a generator matrix each of whose rows has even weight. Show that, every codeword of C C C\mathscr{C}C has even weight.
(Hint: Why is it enough to prove that sum of vectors of even weight in F 2 n F 2 n F_(2)^(n)\mathbf{F}_2^nF2n is a vector of even weight? )
c) Show that, if x F 3 n x F 3 n xinF_(3)^(n)\mathbf{x} \in \mathbf{F}_3^nxF3n,
w t ( x ) x x ( mod 3 ) w t ( x ) x x ( mod 3 ) wt(x)-=x*xquad(mod3)w t(\mathbf{x}) \equiv \mathbf{x} \cdot \mathbf{x} \quad(\bmod 3)wt(x)xx(mod3)
Deduce that, if C C C\mathscr{C}C is a ternary self orthogonal code, the weight of each codeword is divisible by 3 .
(Hint: Observe that x 2 = 1 x 2 = 1 x^(2)=1x^2=1x2=1 for all x 0 F 3 x 0 F 3 x!=0inF_(3)x \neq 0 \in \mathbf{F}_3x0F3 )
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 t ttt and d d ddd for a perfect code of length 2 m + 1 , m N 2 m + 1 , m N 2m+1,m inN2 m+1, m \in \mathbf{N}2m+1,mN.
ii) Show that
i = 0 m ( 2 m + 1 i ) = 2 2 m i = 0 m ( 2 m + 1 i ) = 2 2 m sum_(i=0)^(m)((2m+1)/(i))=2^(2m)\sum_{i=0}^m\binom{2 m+1}{i}=2^{2 m}i=0m(2m+1i)=22m
(Hint: Start with the relation
2 2 m + 1 = i = 0 2 m + 1 ( 2 m + 1 i ) 2 2 m + 1 = i = 0 2 m + 1 ( 2 m + 1 i ) 2^(2m+1)=sum_(i=0)^(2m+1)((2m+1)/(i))2^{2 m+1}=\sum_{i=0}^{2 m+1}\binom{2 m+1}{i}22m+1=i=02m+1(2m+1i)
iii) Deduce that every repetiition code of odd length is perfect.
  1. Let α α alpha\alphaα be a root of x 2 + 1 = 0 x 2 + 1 = 0 x^(2)+1=0x^2+1=0x2+1=0 in F 9 F 9 F_(9)\mathbf{F}_9F9.
    a) Check whether α α alpha\alphaα is a primitive element of F 9 F 9 F_(9)\mathbf{F}_9F9. If it is not a primitive element in F 9 F 9 F_(9)\mathbf{F}_9F9 find a primitive element γ γ gamma\gammaγ in F 9 F 9 F_(9)\mathbf{F}_9F9 in terms of α α alpha\alphaα.
    b) Make a table similiar to Table 5.1 on page 184 for F 9 F 9 F_(9)\mathbf{F}_9F9 with the primitive element γ γ gamma\gammaγ
    c) Factorise x 8 1 x 8 1 x^(8)-1x^8-1x81 over F 3 F 3 F_(3)\mathbf{F}_3F3.
    d) Find all the possible generator polynomials of a [ 8 , 6 ] [ 8 , 6 ] [8,6][8,6][8,6] cyclic code.
  2. a) Let C 1 C 1 C_(1)\mathscr{C}_1C1 and C 2 C 2 C_(2)\mathscr{C}_2C2 be cyclic codes over F q F q F_(q)\mathbf{F}_qFq with generator polynomials g 1 ( x ) g 1 ( x ) g_(1)(x)g_1(x)g1(x) and g 2 ( x ) g 2 ( x ) g_(2)(x)g_2(x)g2(x), respectively. Prove that C 1 C 2 C 1 C 2 C_(1)subeC_(2)\mathscr{C}_1 \subseteq \mathscr{C}_2C1C2 if and only if g 2 ( x ) g 1 ( x ) g 2 ( x ) g 1 ( x ) g_(2)(x)∣g_(1)(x)g_2(x) \mid g_1(x)g2(x)g1(x).
    b) Over F 2 , ( 1 + x ) ( x n 1 ) F 2 , ( 1 + x ) x n 1 F_(2),(1+x)∣(x^(n)-1)\mathbf{F}_2,(1+x) \mid\left(x^n-1\right)F2,(1+x)(xn1). Let C C C\mathscr{C}C be the binary cyclic code ( 1 + x ) ( 1 + x ) (1+x)(1+x)(1+x) of length n n nnn. Let C 1 C 1 C_(1)\mathscr{C}_1C1 be any binary cyclic code of length n n nnn with generator polynomial g 1 ( x ) g 1 ( x ) g_(1)(x)g_1(x)g1(x).
    i) What is the dimension of C C C\mathscr{C}C ?
    ii) Let w w www be subspace of F 2 n F 2 n F_(2)^(n)\mathbf{F}_2^nF2n containing all the vectors of even weight. Prove that W W WWW has dimension n 1 n 1 n-1n-1n1. (Hint: Consider the map w : F 2 n F 2 w : F 2 n F 2 w:F_(2)^(n)rarrF_(2)w: \mathbf{F}_2^n \rightarrow \mathbf{F}_2w:F2nF2 given by
w ( ( a 1 , a 2 , , a n ) ) = a 1 + a 2 + + a n . ) w a 1 , a 2 , , a n = a 1 + a 2 + + a n . {:w((a_(1),a_(2),dots,a_(n)))=a_(1)+a_(2)+cdots+a_(n).)\left.w\left(\left(a_1, a_2, \ldots, a_n\right)\right)=a_1+a_2+\cdots+a_n .\right)w((a1,a2,,an))=a1+a2++an.)
iii) Prove that C C C\mathscr{C}C is the vector space of all vectors in F 2 n F 2 n F_(2)^(n)\mathbf{F}_2^nF2n with even weight.
iv) If C 1 C 1 C_(1)\mathscr{C}_1C1 has only even weight codewords, what is the relationship between ( 1 + x ) ( 1 + x ) (1+x)(1+x)(1+x) and g 1 ( x ) ? g 1 ( x ) ? g_(1)(x)?g_1(x) ?g1(x)?
v) If C 1 C 1 C_(1)\mathscr{C}_1C1 has some odd weight codewords, what is the relationship between 1 + x 1 + x 1+x1+x1+x and g 1 ( x ) ? g 1 ( x ) ? g_(1)(x)?g_1(x) ?g1(x)?
7) a) Let C C C\mathscr{C}C be the ternary [ 8 , 3 ] [ 8 , 3 ] [8,3][8,3][8,3] narrow-sense BCH code of designed distance δ = 5 δ = 5 delta=5\delta=5δ=5, which has defining set T = { 1 , 2 , 3 , 4 , 6 } T = { 1 , 2 , 3 , 4 , 6 } T={1,2,3,4,6}T=\{1,2,3,4,6\}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 g ( x ) = x 5 x 4 + x 3 + x 2 1 g(x)=x^(5)-x^(4)+x^(3)+x^(2)-1g(x)=x^5-x^4+x^3+x^2-1g(x)=x5x4+x3+x21
original image
is the generator polynomial of C C C\mathscr{C}C and
y ( x ) = x 7 x 6 x 4 x 3 y ( x ) = x 7 x 6 x 4 x 3 y(x)=x^(7)-x^(6)-x^(4)-x^(3)y(x)=x^7-x^6-x^4-x^3y(x)=x7x6x4x3
is the received word, find the transmitted codeword.
b) Let C C C\mathscr{C}C be the [ 5 , 2 ] [ 5 , 2 ] [5,2][5,2][5,2] ternary code generated by
G = ( 1 1 0 0 1 0 1 0 1 1 ) G = 1      1      0      0      1 0      1      0      1      1 G=([1,1,0,0,1],[0,1,0,1,1])G=\left(\begin{array}{lllll} 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{array}\right)G=(1100101011)
Find the weight enumerator W C ( x , y ) W C ( x , y ) W_(C)(x,y)W_{\mathscr{C}}(x, y)WC(x,y) of C C C\mathscr{C}C.
c) Find the generating idempotents of duadic codes of length n = 23 n = 23 n=23n=23n=23 over F 3 F 3 F_(3)\mathbf{F}_3F3.
(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 } C = { 0000 , 1113 , 2222 , 3331 , 0202 , 1313 , 2020 , 3131 , 0022 , 1131 , 2200 , 3313 , 0220 , 1333 , 2002 , 3111 } C={0000,1113,2222,3331,0202,1313,2020,3131,0022,1131,2200,3313,0220,1333,2002,3111}C=\{0000,1113,2222,3331,0202,1313,2020,3131,0022,1131,2200,3313,0220,1333,2002,3111\}C={0000,1113,2222,3331,0202,1313,2020,3131,0022,1131,2200,3313,0220,1333,2002,3111}
be the Z 4 Z 4 Z_(4)Z_4Z4-linear code. Find the Gray image of C C CCC.
b) Draw the Tanner graph of the code C C C\mathscr{C}C with parity check matrix
[ 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 ] . 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 . [[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]].\left[\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}\right] .[1000100101010011001000100110010001001110].
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 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.

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.

False.
Counterexample:
Consider a code over F 2 F 2 F_(2)\mathbf{F}_2F2 with a generating matrix
G = ( 1 1 1 0 0 1 1 1 ) . G = 1 1 1 0 0 1 1 1 . G=([1,1,1,0],[0,1,1,1]).G = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{pmatrix}.G=(11100111).
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 ) v 1 + v 2 = ( 1 , 0 , 0 , 1 ) v_(1)+v_(2)=(1,0,0,1)v_1 + v_2 = (1, 0, 0, 1)v1+v2=(1,0,0,1) has weight 2). Therefore, the weight of the rows does not guarantee that the minimum distance is at least r r rrr.

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

True.
Proof:
A code C C CCC is self-orthogonal if for every pair of codewords x , y C x , y C x,y in Cx, y \in Cx,yC, the inner product x y = 0 x y = 0 x*y=0x \cdot y = 0xy=0. In a linear self-orthogonal code, the inner product of each codeword with itself must also be zero, i.e., x x = 0 x x = 0 x*x=0x \cdot x = 0xx=0, meaning that the weight of each codeword must be even (since over F 2 F 2 F_(2)\mathbf{F}_2F2, 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 n nnn are formed by taking powers of some integer b b bbb modulo n n nnn, and their size is determined by the smallest integer m m mmm such that b m 1 mod n b m 1 mod n b^(m)-=1modnb^m \equiv 1 \mod nbm1modn. For n = 121 = 11 2 n = 121 = 11 2 n=121=11^(2)n = 121 = 11^2n=121=112, 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 F 2 F_(2)\mathbf{F}_2F2.

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 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.

True.
Proof:
For an LDPC (Low-Density Parity-Check) code with parameters n = 16 n = 16 n=16n = 16n=16 (length), c = 3 c = 3 c=3c = 3c=3 (column weight, i.e., the number of 1s in each column of the parity-check matrix), and r = 5 r = 5 r=5r = 5r=5 (row weight, i.e., the number of 1s in each row of the parity-check matrix), we need to satisfy the condition n × c = m × r n × c = m × r n xx c=m xx rn \times c = m \times rn×c=m×r, where m m mmm is the number of rows in the parity-check matrix. Here n = 16 n = 16 n=16n = 16n=16, c = 3 c = 3 c=3c = 3c=3, and r = 5 r = 5 r=5r = 5r=5, so we would need 16 × 3 = m × 5 16 × 3 = m × 5 16 xx3=m xx516 \times 3 = m \times 516×3=m×5, which simplifies to m = 48 / 5 = 9.6 m = 48 / 5 = 9.6 m=48//5=9.6m = 48 / 5 = 9.6m=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?

i) C = { ( 0 , 0 , 0 , 0 ) , ( 1 , 0 , 1 , 0 ) , ( 0 , 1 , 1 , 0 ) , ( 1 , 1 , 1 , 0 ) } C = { ( 0 , 0 , 0 , 0 ) , ( 1 , 0 , 1 , 0 ) , ( 0 , 1 , 1 , 0 ) , ( 1 , 1 , 1 , 0 ) } C={(0,0,0,0),(1,0,1,0),(0,1,1,0),(1,1,1,0)}\mathscr{C}=\{(0,0,0,0),(1,0,1,0),(0,1,1,0),(1,1,1,0)\}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 ) } 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)}
Justify your answer.

Answer:

To determine if a binary code is linear, we need to check two properties:
  1. The code must contain the zero codeword (all zeros).
  2. 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 ) } C = { ( 0 , 0 , 0 , 0 ) , ( 1 , 0 , 1 , 0 ) , ( 0 , 1 , 1 , 0 ) , ( 1 , 1 , 1 , 0 ) } C={(0,0,0,0),(1,0,1,0),(0,1,1,0),(1,1,1,0)}\mathscr{C} = \{(0,0,0,0), (1,0,1,0), (0,1,1,0), (1,1,1,0)\}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 ) ( 0 , 0 , 0 , 0 ) (0,0,0,0)(0,0,0,0)(0,0,0,0) is in C C C\mathscr{C}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 ) ( 1 , 0 , 1 , 0 ) + ( 0 , 1 , 1 , 0 ) = ( 1 , 1 , 0 , 0 ) (1,0,1,0)+(0,1,1,0)=(1,1,0,0)(1,0,1,0) + (0,1,1,0) = (1,1,0,0)(1,0,1,0)+(0,1,1,0)=(1,1,0,0) (not in C C C\mathscr{C}C),
    • ( 1 , 0 , 1 , 0 ) + ( 1 , 1 , 1 , 0 ) = ( 0 , 1 , 0 , 0 ) ( 1 , 0 , 1 , 0 ) + ( 1 , 1 , 1 , 0 ) = ( 0 , 1 , 0 , 0 ) (1,0,1,0)+(1,1,1,0)=(0,1,0,0)(1,0,1,0) + (1,1,1,0) = (0,1,0,0)(1,0,1,0)+(1,1,1,0)=(0,1,0,0) (not in C C C\mathscr{C}C),
    • ( 0 , 1 , 1 , 0 ) + ( 1 , 1 , 1 , 0 ) = ( 1 , 0 , 0 , 0 ) ( 0 , 1 , 1 , 0 ) + ( 1 , 1 , 1 , 0 ) = ( 1 , 0 , 0 , 0 ) (0,1,1,0)+(1,1,1,0)=(1,0,0,0)(0,1,1,0) + (1,1,1,0) = (1,0,0,0)(0,1,1,0)+(1,1,1,0)=(1,0,0,0) (not in C C C\mathscr{C}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 ) } 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)}

  • Contains the zero codeword?
    Yes, ( 0 , 0 , 0 ) ( 0 , 0 , 0 ) (0,0,0)(0,0,0)(0,0,0) is in C C C\mathscr{C}C.
  • Closed under addition?
    Let’s check the pairwise sums of the codewords (mod 2):
    • ( 1 , 1 , 0 ) + ( 1 , 0 , 1 ) = ( 0 , 1 , 1 ) ( 1 , 1 , 0 ) + ( 1 , 0 , 1 ) = ( 0 , 1 , 1 ) (1,1,0)+(1,0,1)=(0,1,1)(1,1,0) + (1,0,1) = (0,1,1)(1,1,0)+(1,0,1)=(0,1,1) (which is in C C C\mathscr{C}C),
    • ( 1 , 1 , 0 ) + ( 0 , 1 , 1 ) = ( 1 , 0 , 1 ) ( 1 , 1 , 0 ) + ( 0 , 1 , 1 ) = ( 1 , 0 , 1 ) (1,1,0)+(0,1,1)=(1,0,1)(1,1,0) + (0,1,1) = (1,0,1)(1,1,0)+(0,1,1)=(1,0,1) (which is in C C C\mathscr{C}C),
    • ( 1 , 0 , 1 ) + ( 0 , 1 , 1 ) = ( 1 , 1 , 0 ) ( 1 , 0 , 1 ) + ( 0 , 1 , 1 ) = ( 1 , 1 , 0 ) (1,0,1)+(0,1,1)=(1,1,0)(1,0,1) + (0,1,1) = (1,1,0)(1,0,1)+(0,1,1)=(1,1,0) (which is in C C C\mathscr{C}C).
    All sums of the codewords are in C C C\mathscr{C}C, so it is closed under addition.
Since both conditions are satisfied, C C C\mathscr{C}C is linear.

Final Answer Summary:

  • i) Not linear
  • ii) Linear


Scroll to Top
Scroll to Top