The task of constructing an LHC with given properties.

The task of constructing an LHC with given properties.

Algorithm:

1) if N is a given code power, then the information part of the matrix has the size k =] log ₂ N [. 2) any check column is the sum of a mod 2 of some number of columns of the information part of the matrix, and each column of the information part must take part at least once by the weight of the column.

3) the weight of each line should be ω _i ≥d _min .

4) Hamming distance ρ (V _i , V _j ) ≥ d _min .

Example: build a generator matrix. N = 16, b = 2.

K = lod ₂ 16 = 4, d _min ≥b + 1 = 3.

The resulting matrix does not satisfy the condition of the task, because the weight of V ₂ , V ₄ = 2.

ρ (V ₁ , V ₂ ) = 2, ρ (V ₃ , V ₄ ) = 2.

Conclusion: this matrix does not satisfy the condition.

128 → 16 words.

Conclusion: in accordance with the task, the matrix of the generating code was obtained. If, with the selected number of columns of the test part, the requirements cannot be fulfilled, then the number of columns is increased.

Consider:

256 → 16 words.

G ₁ => (7,4), G ₂ => (8,4). Comparing G ₁ and G ₂ , we can conclude: G ₁ generates a code that has a speed R = k / n = 4/7, whereas G ₂ R = 1/2. The code generated by G _{1 is} more profitable.

Determining the required number of check columns.

Error correction is based on redundancy. The discharges of the check part of the matrix G are redundant. Before determining the minimum required number of check bits, we establish the connections that need to be imposed on the check and information bits in order to provide the specified correction ability of the code. Consider this on G ₁ .

p ₁ = a ₁ (+) a ₂ (+) a ₄ , p ₂ = a ₁ + a ₃ + a ₄ , p ₃ = a ₂ + a ₃ + a ₄ ,

p ₁ + a ₁ + a ₂ + a ₄ = S ₁ , p ₂ + a ₁ + a ₃ + a ₄ = S ₂ , p ₃ + a ₂ + a ₃ + a ₄ = S ₃ .

S vector (S ₁ , S ₂ , S ₃ ) - vector of syndromes - a pointer to the presence of errors.

If there are no errors, then S (S ₁ , S ₂ , S ₃ ) = 0, otherwise, if no more than t errors are committed, then S ≠ 0.

d _min ≥2t + 1 => t = 1. As follows from the table, all S vectors with a single

errors ≠ 0 and are different, i.e. each S combination uniquely indicates a number

erroneous discharge. For the correction of this discharge is enough

to invert.

Example: let's say that there are 2 errors in a word, we will build a table of syndromes for this error.

As follows from this table, all syndromes ≠ 0. However, for some combinations of failures or errors, the syndromes recur, therefore it is impossible to say for sure which particular pairs of discharges are erroneous. So The considered code can detect 2 errors, but correct only one. However, in fact, no current pair errors, triple errors are detected. Not detected

only 4 out of 20 possible. Fourfold: 4 out of 15 possible. Any 5 and 6 multiple errors are detected. Thus, out of all 63 possible combinations of errors, only 8 are not detected.

For this code, the number of check columns is 3, and therefore 3 check equations are constructed to construct a three-component syndrome S. In general, the number of equations must be ≥ the number of corrected errors. If there are m check digits, then 2 ^r -1 is the number of possible different check combinations on r digits. Their number must be ≥ the number of corrected errors. If mv we want to correct single errors (t = 1), then 2 ^r -1 = С ¹ _n , if two, then 2 ^r -1 ≥ С ¹ _n + С ² _n . In the general case: 2 ^r -1≥С ¹ _n + С ² _n + ... + С ^t _n .

Example: r = nk, 2 ^{r - n} ≥С ¹ _n + С ² _n +… + С ^t _n , k = 4, t = 1: 2 ^{n -4} ≥С ¹ _n +1, 2 ^{n -4} ≥n +1, n-4≥] log ₂ (n + 1) [.

n = 6: 2≥] log ₂ (7) [- not suitable

n = 7: 3≥] log ₂ (8) [, r = 3 => n≥] log ₂ n (n + 1) / 2 + 1 [+4, n = 10.