Coding and decoding in the Central Committee.

Coding and decoding in the Central Committee.

Shift register is used for encoding and decoding. Consider a device that allows you to automatically encode and decode words.

Constructions of the coder for the Hamming code (15.11): t = 1, g (x) = x ⁴ + x + 1.

This scheme is a device for multiplying two polynomials, one of which g (x) is implemented as links in this shift register. i (x) is an information word that is pushed bit by bit to the input of the circuit. In this encoder, the information word i (x) is 11-bit and 4 “0” is assigned to it to the low-order bits. Over 15 clock cycles at the output of the circuit, the word C (x) appears, which is the code of the word i (x) and represents the product i (x) * g (x). Pluses: simplicity. Disadvantages: non-systematic code C (x).

Consider a systematic code encoder. g (x) = x ⁴ + x + 1.

C (x) = i (x) * x ^r + R [(i (x) * x ^r ) / g (x)]

The information word i (x) simultaneously enters both the lower shift register and the upper dividing device. For 15 cycles, the word i passes through the lower register and enters the output channel with the most significant digits ahead. At the same time, the remainder of the division of the product (i (x) * x ^r ) / g (x) is obtained in the divider. After 15 cycles, the key in the divider opens, and the output signal is connected to the output of the divider. Another 4 bars and the remainder of the dividing device is moving into the output channel. Thus, the total encoding time is 19 clocks.

Decoder in the Central Committee.

Decoding in the Central Committee is carried out on the basis of the remainder of the division of the received word into the generating polynomial. The decoder gets V (x) = C (x) + e (x), e (x) is the error vector. We divide by g (x): V (x) / g (x) = C (x) / g (x) + e (x) / g (x). R [V (x) / g (x)] = R [C (x) / g (x) + e (x) / g (x)] = R [C (x) / g (x) +] + R [e (x) / g (x)] = R [e (x) / g (x)] - This expression says that the remainder of the division by the generating polynomial depends only on the error polynomial e (x) and not depends on the code word.

g (x) = x ⁴ + x + 1

Block diagram of the DECODER (15.11)

The information word V (x) is fed to the input of the shift register 2, where in 15 clock cycles it is completely

fills it up. At the same time, the upper part of the circuit, which is a divisor by the generator polynomial of the code (15.11), performs division, and after 15 cycles there remains a remainder in it. This remainder as an address goes to the ROM, in which the error word e (x) corresponding to the remainder is written at each address. This word is selected from the ROM and is written to shift register 1. For the next 15 cycles, registers 1 and 2 shift the contents. On the element summation is carried out V (x) = C (x) + e (x), V (x) + e (x) = C (x) + e (x) + e (x) = C (x). At the same time, C (x) is fed to a 2 separating device, the output of which produces an 11-bit information word i (x). The main disadvantage of this scheme is the preliminary compilation of a table for writing to the ROM.

Meggit decoder

For large lengths of codes with high corrective power, this is quite difficult. In real decoders, Meggit decoder is used. The theoretical basis for the construction of the Meggit decoder is the Meggit theorem, which states that if the received word V (x) has a remainder from the division R [V (x) / g (x)] = S, then if we calculate the remainder from the division R [ (x * V (x)) / g (x)] = x * S (mod x ⁿ -1).

Example: Hamming code (15, 11), g (x) = x ⁴ + x + 1, e (x) = x ¹⁴ is the current error in the high-order bit.

If e (x) = x ¹⁴ / x ⁴ + x + 1 ... R ₁₄ = 1001

After 15 shifts in the shift register, V (x) is filled, and in the divider, the remainder is obtained, corresponding to the error word e (x). If the error is in the high-order bit, then the remainder will be 1001 and the output of circuit i will form 1. Then the 15-bit, summing up from this 1 by the 16-clock cycle, will be inverted, i.e. corrected. The next 14 cycles are simply moving the word out of the shift register, since the output of cell i will be 0. If the error is not 15, but 14, then the combination 1 and 0 will not be 1001 in the remainder; on the 16th shift, the 15th digit is summed from 0, on the 17th shift - the remainder in the divider will shift and take the value 1001. At the output of the circuit, 1 appears, which is summed up from 14 digits of the word V (x), and the remaining 13 digits are simply shifted to the output.

e (x) = 001000000000000

| e (x) = 000000000000 1 00

e (x) = x ¹² / x ⁴ + x + 1 ... R ₁₂ = x ³ + x ² + x + 1 (1111)

Examples:

Code (7,4), g (x) = x ³ + x + 1.

e (x) = 1000000 = x ⁶ / x ³ + x + 1 ... R ₇ (x) = 101

e (x) = 0001000 - the word of error

| e (x) = 000 1 000