maths.free › Abstract Algebra › 8. Algebraic Coding Theory › Linear Codes

Linear Codes

To gain more knowledge of a particular code and develop more efficient techniques of encoding, decoding, and error detection, we need to add additional structure to our codes.

Linear Codes

To gain more knowledge of a particular code and develop more efficient techniques of encoding, decoding, and error detection, we need to add additional structure to our codes. One way to accomplish this is to require that the code also be a group. A group code is a code that is also a subgroup of \({\mathbb Z}_2^n\).

To check that a code is a group code, we need only verify one thing. If we add any two elements in the code, the result must be an \(n\)-tuple that is again in the code. It is not necessary to check that the inverse of the \(n\)-tuple is in the code, since every codeword is its own inverse, nor is it necessary to check that \({\mathbf 0}\) is a codeword. For instance, \[\begin{aligned}\end{aligned}\].

Example

Suppose that we have a code that consists of the following 7-tuples: \[\begin{aligned}&(\codeword{0000000}) & & (\codeword{0001111}) & & (\codeword{0010101}) & & (\codeword{0011010}) \\ &(\codeword{0100110}) & & (\codeword{0101001}) & & (\codeword{0110011}) & & (\codeword{0111100}) \\ &(\codeword{1000011}) & & (\codeword{1001100}) & & (\codeword{1010110}) & & (\codeword{1011001}) \\ &(\codeword{1100101}) & & (\codeword{1101010}) & & (\codeword{1110000}) & & (\codeword{1111111})\end{aligned}\]. It is a straightforward though tedious task to verify that this code is also a subgroup of \({\mathbb Z}_2^7\) and, therefore, a group code. This code is a single error-detecting and single error-correcting code, but it is a long and tedious process to compute all of the distances between pairs of codewords to determine that \(d_{\min} = 3\). It is much easier to see that the minimum weight of all the nonzero codewords is \(3\). As we will soon see, this is no coincidence. However, the relationship between weights and distances in a particular code is heavily dependent on the fact that the code is a group.

Lemma

Let \({\mathbf x}\) and \({\mathbf y}\) be binary \(n\)-tuples. Then \(w({\mathbf x} + {\mathbf y}) = d({\mathbf x}, {\mathbf y})\).

Proof

Suppose that \({\mathbf x}\) and \({\mathbf y}\) are binary \(n\)-tuples. Then the distance between \({\mathbf x}\) and \({\mathbf y}\) is exactly the number of places in which \({\mathbf x}\) and \({\mathbf y}\) differ. But \({\mathbf x}\) and \({\mathbf y}\) differ in a particular coordinate exactly when the sum in the coordinate is \(1\), since \[\begin{aligned}1 + 1 & = 0 \\ 0 + 0 & = 0 \\ 1 + 0 & = 1 \\ 0 + 1 & = 1\end{aligned}\]. Consequently, the weight of the sum must be the distance between the two codewords.

Linear Codes

From , it is now easy to check that the minimum nonzero weight is \(3\); hence, the code does indeed detect and correct all single errors. We have now reduced the problem of finding good codes to that of generating group codes. One easy way to generate group codes is to employ a bit of matrix theory.

Define the inner product of two binary \(n\)-tuples to be \[\begin{aligned}\end{aligned}\], where \({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) and \({\mathbf y} = (y_1, y_2, \ldots, y_n)^\transpose\) are column vectors. Since we will be working with matrices, we will write binary \(n\)-tuples as column vectors for the remainder of this chapter. For example, if \({\mathbf x} = (\codeword{011001})^\transpose\) and \({\mathbf y} = (\codeword{110101})^\transpose\), then \({\mathbf x} \cdot {\mathbf y} = 0\). We can also look at an inner product as the product of a row matrix with a column matrix; that is, \[\begin{aligned}{\mathbf x} \cdot {\mathbf y} & = {\mathbf x}^\transpose {\mathbf y} \\ & = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix} \\ & = x_{1}y_{1} + x_{2}y_{2} + \cdots + x_{n}y_{n}\end{aligned}\].

Example

Suppose that the words to be encoded consist of all binary \(3\)-tuples and that our encoding scheme is even-parity. To encode an arbitrary \(3\)-tuple, we add a fourth bit to obtain an even number of \(1\)s. Notice that an arbitrary \(n\)-tuple \({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) has an even number of \(1\)s exactly when \(x_1 + x_2 + \cdots + x_n = 0\); hence, a \(4\)-tuple \({\mathbf x} = (x_1, x_2, x_3, x_4)^\transpose\) has an even number of \(1\)s if \(x_1+ x_2+ x_3+ x_4 = 0\), or \[\begin{aligned}\end{aligned}\]. This example leads us to hope that there is a connection between matrices and coding theory.

Example

Suppose that \[\begin{aligned}\end{aligned}\]. For a \(5\)-tuple \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5)^\transpose\) to be in the null space of \(H\), \(H{\mathbf x} = {\mathbf 0}\). Equivalently, the following system of equations must be satisfied: \[\begin{aligned}x_2 + x_4 & = 0 \\ x_1 + x_2 + x_3 + x_4 & = 0 \\ x_3 + x_4 + x_5 & = 0\end{aligned}\]. The set of binary \(5\)-tuples satisfying these equations is \[\begin{aligned}\end{aligned}\]. This code is easily determined to be a group code.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Symbols used here

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

matrix
A rectangular array of numbers; a linear map.

\neq

not equal
The two sides are different.

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

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

x \in A,\ A \subseteq B

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

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

የራስዎን ይሞክሩ

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

በ 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