You get a bonus - 1 coin for daily activity. Now you have 1 coin

Linear group codes (LGK).

Lecture



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 1 and with 2 - 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 1 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 n   words, code is only 2 k .

Example: k = 3, n = 6, 2 6 = 64, 2 3 = 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.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Informatics

Terms: Informatics