maths.free › Abstract Algebra › 8. Algebraic Coding Theory › Algebraic Coding Theory: exercises

Algebraic Coding Theory: exercises

Algebraic Coding Theory: exercises — from Judson, Abstract Algebra: Theory and Applications.

Practice (26)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

Why is the following encoding scheme not acceptable?

Information	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
Codeword	\(\codeword{000}\)	\(\codeword{001}\)	\(\codeword{010}\)	\(\codeword{011}\)	\(\codeword{101}\)	\(\codeword{110}\)	\(\codeword{111}\)	\(\codeword{000}\)	\(\codeword{001}\)

Without doing any addition, explain why the following set of \(4\)-tuples in \({\mathbb Z}_2^4\) cannot be a group code. \[\begin{aligned}\end{aligned}\]

Giải đáp

Hint:
This cannot be a group code since \((\codeword{0000}) \notin C\).
Compute the Hamming distances between the following pairs of \(n\)-tuples.
1. \((\codeword{011010}), (\codeword{011100})\)
2. \((\codeword{11110101}), (\codeword{01010100})\)
3. \((\codeword{00110}), (\codeword{01111})\)
4. \((\codeword{1001}), (\codeword{0111})\)
Giải đáp

Hint:
(a) \(2\); (c) \(2\).
Compute the weights of the following \(n\)-tuples.
1. \((\codeword{011010})\)
2. \((\codeword{11110101})\)
3. \((\codeword{01111})\)
4. \((\codeword{1011})\)
Giải đáp

Hint:
(a) \(3\); (c) \(4\).
Suppose that a linear code \(C\) has a minimum weight of \(7\). What are the error-detection and error-correction capabilities of \(C\)?
In each of the following codes, what is the minimum distance for the code? What is the best situation we might hope for in connection with error detection and error correction?
1. \((\codeword{011010}) \; (\codeword{011100}) \; (\codeword{110111}) \; (\codeword{110000})\)
2. \((\codeword{011100}) \; (\codeword{011011}) \; (\codeword{111011}) \; (\codeword{100011}) \\ (\codeword{000000}) \; (\codeword{010101}) \; (\codeword{110100}) \; (\codeword{110011})\)
3. \((\codeword{000000}) \; (\codeword{011100}) \; (\codeword{110101}) \; (\codeword{110001})\)
4. \((\codeword{0110110}) \; (\codeword{0111100}) \; (\codeword{1110000}) \; (\codeword{1111111}) \\ (\codeword{1001001}) \; (\codeword{1000011}) \; (\codeword{0001111}) \; (\codeword{0000000})\)
Giải đáp

Hint:
(a) \(d_{\min} = 2\); (c) \(d_{\min} = 1\).
Compute the null space of each of the following matrices. What type of \((n,k)\)-block codes are the null spaces? Can you find a matrix (not necessarily a standard generator matrix) that generates each code? Are your generator matrices unique?
1. \[\begin{aligned}\end{aligned}\]
2. \[\begin{aligned}\end{aligned}\]
3. \[\begin{aligned}\end{aligned}\]
4. \[\begin{aligned}\end{aligned}\]
Giải đáp
Hint:
1. \((\codeword{00000}), (\codeword{00101}), (\codeword{10011}), (\codeword{10110})\) \[\begin{aligned}\end{aligned}\]
2. \((\codeword{000000}), (\codeword{010111}), (\codeword{101101}), (\codeword{111010})\) \[\begin{aligned}\end{aligned}\]
Construct a \((5,2)\)-block code. Discuss both the error-detection and error-correction capabilities of your code.
Let \(C\) be the code obtained from the null space of the matrix \[\begin{aligned}\end{aligned}\]. Decode the message \[\begin{aligned}\end{aligned}\] if possible.

Giải đáp

Hint:
Multiple errors occur in one of the received words.
Suppose that a \(1000\)-bit binary message is transmitted. Assume that the probability of a single error is \(p\) and that the errors occurring in different bits are independent of one another. If \(p = 0.01\), what is the probability of more than one error occurring? What is the probability of exactly two errors occurring? Repeat this problem for \(p = 0.0001\).
Which matrices are canonical parity-check matrices? For those matrices that are canonical parity-check matrices, what are the corresponding standard generator matrices? What are the error-detection and error-correction capabilities of the code generated by each of these matrices?
1. \[\begin{aligned}\end{aligned}\]
2. \[\begin{aligned}\end{aligned}\]
3. \[\begin{aligned}\end{aligned}\]
4. \[\begin{aligned}\end{aligned}\]
Giải đáp

Hint:
(a) A canonical parity-check matrix with standard generator matrix \[\begin{aligned}\end{aligned}\].
(c) A canonical parity-check matrix with standard generator matrix \[\begin{aligned}\end{aligned}\].
List all possible syndromes for the codes generated by each of the matrices in .

Giải đáp

Hint:
(a) All possible syndromes occur.
Let \[\begin{aligned}\end{aligned}\]. Compute the syndrome caused by each of the following transmission errors.
1. An error in the first bit.
2. An error in the third bit.
3. An error in the last bit.
4. Errors in the third and fourth bits.
Let \(C\) be the group code in \({\mathbb Z}_2^3\) defined by the codewords \((\codeword{000})\) and \((\codeword{111})\). Compute the cosets of \(C\) in \({\mathbb Z}_2^3\). Why was there no need to specify right or left cosets? Give the single transmission error, if any, to which each coset corresponds.
For each of the following matrices, find the cosets of the corresponding code \(C\). Give a decoding table for each code if possible.
1. \[\begin{aligned}\end{aligned}\]
2. \[\begin{aligned}\end{aligned}\]
3. \[\begin{aligned}\end{aligned}\]
4. \[\begin{aligned}\end{aligned}\]
Giải đáp

Hint:
(a) \(C\), \((\codeword{10000}) + C\), \((\codeword{01000}) + C\), \((\codeword{00100}) + C\), \((\codeword{00010}) + C\), \((\codeword{11000}) + C\), \((\codeword{01100}) + C\), \((\codeword{01010}) + C\). A decoding table does not exist for \(C\) since this is only a single error-detecting code.
Let \({\mathbf x}\), \({\mathbf y}\), and \({\mathbf z}\) be binary \(n\)-tuples. Prove each of the following statements.
1. \(w({\mathbf x}) = d( {\mathbf x}, {\mathbf 0})\)
2. \(d( {\mathbf x}, {\mathbf y}) = d( {\mathbf x} + {\mathbf z}, {\mathbf y} + {\mathbf z} )\)
3. \(d({\mathbf x}, {\mathbf y}) = w({\mathbf x}- {\mathbf y})\)
A metric on a set \(X\) is a map \(d: X \times X \rightarrow {\mathbb R}\) satisfying the following conditions.
1. \(d( {\mathbf x}, {\mathbf y}) \geq 0\) for all \({\mathbf x}, {\mathbf y} \in X\);
2. \(d( {\mathbf x}, {\mathbf y}) = 0\) exactly when \({\mathbf x} = {\mathbf y}\);
3. \(d( {\mathbf x}, {\mathbf y})= d( {\mathbf y}, {\mathbf x})\);
4. \(d( {\mathbf x}, {\mathbf y}) \leq d( {\mathbf x}, {\mathbf z}) + d( {\mathbf z}, {\mathbf y})\).
In other words, a metric is simply a generalization of the notion of distance. Prove that Hamming distance is a metric on \({\mathbb Z}_2^n\). Decoding a message actually reduces to deciding which is the closest codeword in terms of distance.
Let \(C\) be a linear code. Show that either the \(i\)th coordinates in the codewords of \(C\) are all zeros or exactly half of them are zeros.
Let \(C\) be a linear code. Show that either every codeword has even weight or exactly half of the codewords have even weight.

Giải đáp

Hint:
Let \({\mathbf x} \in C\) have odd weight and define a map from the set of odd codewords to the set of even codewords by \({\mathbf y} \mapsto {\mathbf x} + {\mathbf y}\). Show that this map is a bijection.
Show that the codewords of even weight in a linear code \(C\) are also a linear code.
If we are to use an error-correcting linear code to transmit the \(128\) ASCII characters, what size matrix must be used? What size matrix must be used to transmit the extended ASCII character set of \(256\) characters? What if we require only error detection in both cases?
Find the canonical parity-check matrix that gives the even parity check bit code with three information positions. What is the matrix for seven information positions? What are the corresponding standard generator matrices?
How many check positions are needed for a single error-correcting code with \(20\) information positions? With \(32\) information positions?

Giải đáp

Hint:
For \(20\) information positions, at least \(6\) check bits are needed to ensure an error-correcting code.
Let \({\mathbf e}_i\) be the binary \(n\)-tuple with a \(1\) in the \(i\)th coordinate and \(0\)'s elsewhere and suppose that \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\). Show that \(H{\mathbf e}_i\) is the \(i\)th column of the matrix \(H\).
Let \(C\) be an \((n,k)\)-linear code. Define the dual or orthogonal code of \(C\) to be \[\begin{aligned}\end{aligned}\].
1. Find the dual code of the linear code \(C\) where \(C\) is given by the matrix \[\begin{aligned}\end{aligned}\].
2. Show that \(C^\perp\) is an \((n, n-k)\)-linear code.
3. Find the standard generator and parity-check matrices of \(C\) and \(C^\perp\). What happens in general? Prove your conjecture.
Write a program to implement a \((16, 12)\)-linear code. Your program should be able to encode and decode messages using coset decoding. Once your program is written, write a program to simulate a binary symmetric channel with transmission noise. Compare the results of your simulation with the theoretically predicted error probability.

Symbols used here

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

Thử đi.

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

More in Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula