Algebraic description of block codes

For description of the linear block codes use a mathematical apparatus of the general algebra [3]. By the block coding form code words b = (b ₁, b ₂,..., b_n). Choose symbols ofbinary codes from the Galois field GF (2). The set of words forms n- dimensional vector space over field GF (2). For elements of this space (vectors) the addition and multiplication operations and operation of multiplication of a vector and also scalar product of a vectors are defined. Some vectors subset of the space B _n which satisfy to the vector space axioms organizessubspace A _k.

the binary block code with block length n and 2 ^k allowed code words is calledas the linear (n, k) code if its code words form k -dimensional vector subspace A _k of n- dimensional space B _n. Subspace A _k is generated by the basis from k linearly independent vectors, which organize the lines ofa generator matrix of the (n, k) code:

. (4.1)

It is possible to present code words in the systematic form, forming separately informational part from k numerals and check part from r = (n – k) additional numerals.

The generator matrix of a systematic code looks like:

Matrix G _syst contains identity matrix I _k which defines the information part of code words and matrix P defines the additional symbols. Transition to the systematic form is made by a linear combination of rows from the matrix (4.1). Such transition is illustrated by a following example.

Example 4.1 matrix transformation of the nonsystematic code. The nonsystematic block code (7,4) is set by the generator matrix:

. (4.3)

Using a method of the linear combination of rows from matrix (4.3) we will transform it to the systematic form (4.2). For forming of a systematic generator matrix the rows of an initial matrix (4.3) it is convenient to present in the form of a table 4.1, in which rows g1 _ns, g2 _ns, g3 _ns and g4 _ns are shown.

table 4.1 – Rows of the nonsystematic generator matrix

g1ns
g2ns
g3ns
g4ns

Using modulo-2 addition rules the elements of these rows by exhaustive search of rows in various combinations it is established that by the most suitable variants for forming of matrixes rows for the systematic code are following:

g1 _syst = (g1 _ns g3 _ns g4 _ns), g2 _syst = (g2 _ns g3 _ns), g3 _syst = g3 _ns, g4 _syst = g4 _ns.

The outcome of an evaluation of the matrixes rows of the systematic code is reduced in table 4.2.

table 4.2 – the matrixes rows of the systematic code

g1syst
g2syst
g3syst
g4syst

The matrix of the systematic code in the standard form low given:

. (4.4)

The concept weight of a code word plays the important role in the block codes theory.

Hamming weight w _H of the binary code word is equal to an amount of units in a code word.

Example 4.2 An evaluation of Hamming weights of a code words.

We will define values of Hamming weights for the code words by table 4.3:

table 4.3 – the Hamming weights of code words

binary code words	weight w H(bi)
b1
b2

structure of a generator matrix allows to define the minimum distance of the block codes. This position is illustrated by following exercises.

Exercise 4.1 Definition of the code distance by its generator matrix.

Generator matrixes of the error-control codes by (4.3) or (4.4) are set. Show how to define code distance of a codes by known generator matrix.

instruction. By elaborating of the method for definition of code distance it is necessary to consider that zero combination b₀ = (0000000) is also allowed.

decision. It is above noticed, that allowed code words are defined by linear combinations of a generator matrix rows. As zero word b₀ = (0000000) also is allowed, and rows of a generator matrix g1, g2, g3, g4 also are the allowed words then Hamming distances from these words to a zero word b₀ it is defined their weights d _H (gi, b₀) = w _H(gi), i = (1,… k). Further it is necessary to find the minimum weight, i.e. the minimum distance. Such conclusion from here follows.

code distance as the value of minimum distance between allowed code words is defined by the least weight of rows of generator matrix.

Example 4.3 Definition of Hamming weights of the generator matrix rows of a systematic code.

define values of row weights of a generator matrix from the Example 4.1 (table 4.2). Outcomes of evaluations are reduced in table 4.4.

table 4.4 – the Hamming weights of generator matrix rows for systematic code

the generating matrix rows	weights w H(gi)
g1syst
g2syst
g3syst
g4syst

The analysis of data makes definition of the minimum distance of systematic code from table 4.4 d _{min syst} = min{ w _H (g i)} = 3.

Exercise 4.2 Define by the same way the code distance of nonsystematic code from an example 4.1 (table 4.1).

instruction. The statement about code distance of block code from Exercise 4.1 is fair both for systematic nonsystematic codes.

decision. We will apply a technique from the Example 4.3. Outcomes of evaluations the weights of rows are reduced in table 4.5.

table 4.5 – the Hamming weights of the generator matrix rows for nonsystematic code

generator matrix rows	weights w H(gi)
g1ns
g2ns
g3ns
g4ns

The analysis of these data makes definition of the minimum distance of nonsystematic code from table 4.5 d _{min ns} = min { w _H (gi)} = 3. The received outcomes allow to state that systematic and nonsystematic codes from the Example 4.1 on the value of code distance are equivalent.

Thus, the code distance of a block code is a least weight of nonzero rows from the codegenerator matrix. The above noted dependence between the minimum distance of block codes and weights of nonzero rows can be used for forming of a generator matrix of block code with the beforehand set code distance. This is illustrated by outcomes of examples 4.4 and 4.5.

Example 4.4 A generator matrix of a code with even number of units.

Let's form the generator matrix of the systematic (n, k) code which detect a single errors (q _det = 1). Such code should have code distance d _min = q _det + 1 = 2. Hence the nonzero rows of generator matrix of this code should have minimum weight w _H = 2. according to the standard form (4.4) each row of systematic code matrix already contains a numeral 1 (defined by the submatrix I _k), the weight should be increased the weight of every rows to 2 having added in last numerals every rows (as a part of submatrix P) a numeral 1.

For example the generator matrix such (7,4) codes with k = 4 will look like

, (4.5)

and unit in submatrix P can be in any place of a line.

Exercise 4.5 Generator matrixes of codes which can detect double errors.

Form generator matrix of the systematic code which can detect double errors.

Instruction. From the theory it does not follow that such code there can be only one. It is recommended to consider at first a principle construction of a matrix at least one code and then on this basis to give generalization and to find matrixes of several more codes.

decision. The code can detect errors with multiplicity q _det = 2 should have the minimum distance d _min = q _det = 2 + 1 = 3. Hence rows of generator matrix of such code should have minimum weight w _H = 3. From general view of generator matrix of a systematic code (4.2) follows what to get such weight it is possible by choice of rows of the additional symbols submatrix P and one of row from this submatrix should have the weight equal 2. Following variants of submatrix P are possible:

; , , (4.6)

which differ by rows permutations. As the minimum of each weight rows of these matrixes is equal to 2, they can be used for forming of systematic codes with minimum distance d _min = 3. In particular, the generator matrix of one of such codes looks like:

. (4.7)