Linear group codes (LGK).

Linear group codes (LGK).

The simplest codes belonging to the class of noise-resistant codes are LGK codes. The theory of these codes is based on the concept of a group.

A group G is a collection of elements for which some binary operation (*) is defined and the following axioms are fulfilled: 1) closure - the selected binary operation can be applied to any 2 elements of the group. The result of the operation must belong to the group. 2) associativity a * b * c = a * (b * c), 3) the presence of a single element. In the group there is necessarily a single element, and only one. If the selected operation is addition, then the unit element is denoted by “0”: a + 0 = a, 0 + a = a, where a is any element of the group. If multiplication, then - “1”: a * 1 = a, 1 * a = a, 4) the presence of the inverse element. Each element of the group except the unit possesses the inverse element. For addition: a + (- a) = 0, if multiplication: a * a ^-1 = 1.

Definition: a group is called additive if addition is used as an operation on it.

Definition: A group is called abelian if it is commutative: a + b = b + a, ab = ba.

Definition: A group consisting of a finite set of elements is called a finite group.

In noise immunity coding, finite, commutative, and additive groups are used. The elements of the groups are 0 and 1, and the operation (+) is addition modulo 2.

Example: M = {0,1} (+). Is this set a group?

0 (+) 1 = 1; (0 + 1) + 1 = 0 + (1 + 1). There is a single element: it is “0”, and the inverse element for “0” is “0”, and for “1” - “1”. Thus, a given set M with an operation is a group.

Definition: LGK is a finite, additive, commutative group G whose elements are binary vectors and is used as operations in the group. The binary vector is a sequence of 0 and 1: 10110001. Its length is equal to 8. An LGA is defined in two ways: 1) either by listing the vectors 2) or by a matrix representation. The maximum set of linearly non-dependent binary vectors form the generating matrix of some code. Any vector of code that does not belong to the matrix can be obtained by a linear combination of a certain number of rows to this matrix.

Consider the matrix G:

The resulting code combination belongs to a three-digit binary code, all the vectors of this code obtained from the generating matrix G by all possible combinations above the rows of the matrices. The zero vector belongs to any code because it is .... !!!!!!!!!!

Definition: 1) Hamming distance between two vectors a and b is the number of mismatched positions.

Example: A = 1011001, B = 1101001, ρ (a, b) = 2.

2) The word weight is the number of units in a word, ω (A) = 4, ω (B) = 4.

Detecting ability b - the ability of the code to detect b and less errors.

Corrective ability of the code t - the ability of the code to correct t and less errors.

d _{min is the} code distance. (the minimum Hamming distance between any pair of vectors is called the code distance ). Since 0 is also a vector, the distance between an arbitrary vector a and a zero vector will be ρ (A, 0) = ω (A).

d _min = ω _min .

Definition: d _min ≥b + 1 (*), d _min ≥2t + 1 (**).

We prove (**): If d≥2t + 1, then the spheres do not adjoin, otherwise there is uncertainty with ₁ and with ₂ - the centers of the spheres in n-dimensional space, representing code words. The radii of spheres t is the correcting ability of the code.

If d≥2t + 1, then the spheres do not touch and each non-code word having no more than t errors can be replaced with a code one, which is not the center of the corresponding sphere. If d = 2t, then the spheres are tangent. And if the wrong word is in the field of touch, then it is not known what to replace it with. If d≤2t, then the spheres have a total volume, within which non-code words cannot be corrected.

Since, as a word, for example, with ₁ can be the origin of coordinates, the distance d must be equal to the weight of the code word. (**) proven.

Thus, the task of constructing error-correcting codes is to ensure that the distance between words is at least d. For this, the generator matrix G is constructed according to the following rule:

Definition: the power of the code N is the number of words belonging to the code and N = 2 ^k .

Total can build 2 ⁿ   words, code is only 2 ^k .

Example: k = 3, n = 6, 2 ⁶ = 64, 2 ³ = 8.

Such a code representation is called canonical, left-sided, systematic. The matrix I code is an information bit matrix, with useful information in them. P bits - contain the detecting and correcting ability of the given code. The larger the size (nk), the larger the b, t, while the efficiency of the code drops. Code speed: R = k / n.

Example: k = 3, n = 6

ω _min = 3, d _min = 3 = 2t + 1 => t = 1, b + 1 = 3 => b = 1

Conclusion: this generating matrix generates a code characterized by the following properties: N = 2 ^k = 8, code speed R = k / n = 1/2, the detecting ability b = 2, the correcting ability t = 1.

The generating matrix LGA of length n with k information bits can be constructed by the following rules: 1) all vectors of the generating matrix should be different and linearly independent. 2) the zero vector is not included in the set of vectors of the generating matrix, but is a mandatory code word. 3) each vector of the generating matrix V _i must have weight ω _Vi ≥ d _min . 4) Hamming distance between any two vectors of the generating matrix ρ (V _i , V _j ) ≥ d _min .

The generating matrix LGC constructed by these rules should be checked for compliance with the required values ​​of b and t. For this, all the vectors of the code are constructed from the constructed matrix and written out from the weight. If the weight is ≥d _min , then the construction of the code is complete. We set the task to construct an LKG of a given power and a given corrective ability.