System for encoding and decoding with error correction


H03M13/02 -

 

(57) Abstract:

The invention relates to a multi-valued error-correcting coding for the protection of the transmitted channel information from failures caused by interference. The goal is to provide a method for protecting digital information transmitted over the channel using multivalued ensemble of signals from failures and interference in the communication channel. The transmitted information symbols stored in the memory of the encoder is implemented in the form of a shift register row of the matrix ml with check characters parity columns in the last row and the rows in the last column. The characters are read in the channel diagonally so that the ordinal character associated with the row number i and column number j by the relation n= m[(j-i)mod 1] +i. The channel information is transmitted using the 2mvarious signals, which are mapped to a group of m consecutive binary symbols. In the decoder, the received symbols are written into the shift register and register with the key locked in the ring. Using blocks adders are calculated parity in rows and columns, which sravniatsa each other in the unit of comparison under different cyclic shifts adopted by polemature modulo two added to the sequence of information symbols, correcting its error. 6 Il.

The invention relates to error correcting coding for the protection of the transmitted channel information from faults and errors caused by interference.

Known for a large number of error-correcting codes error-correcting. The most powerful modern systems of encoding and decoding, error correction, are systems with cascade codes. To correct t errors when choosing the right codes of the first and second stages of the cascade code requires 2t check symbols. The disadvantages of cascade code should include the heterogeneity and the logical complexity of its structure and the large number of multi-valued logic elements in the encoder and the decoder, providing operations in the Galois finite field GF(q).

The purpose of the invention to increase hardware reliability and performance of the system caused by a reduction in the number of logic elements.

The goal is achieved in the following way. Information binary characters recorded in the random access memory of the encoder groups l - 1 binary symbols to m - 1 lines of the matrix of size (m - 1) x (l - 1), where l is a Prime number, l > m. The matrix is complemented by a parity check row and the m symbols. The reading begins with the element aoothen the row number and the column number increases by one, until is reached the element of the last line. The group of elements aooand11and22, . . . , am-1m-1forms an oblique line. Further reading begins with the element a01by the same rule, forming an oblique row of a01, a12, . . . , am-1m. Upon reaching the last column of his room is taken modulo l and oblique series continues with a zero column. Ordinal character n one-to-one associated with the row number i and column number j ratio

n = m[(j - 1) mod l] + i, where ( ) mod l - evaluation operation positive modulo l. Each of these groups is mapped to one of the 2msignals in the communication channel. The decoder receives groups of m binary symbols and restores the original matrix from the received symbols. Next, it computes the binary sum of the symbols in rows and columns, forming vectors from m inspections row and the first m inspections on columns. Cyclic shift of the received symbol block by m binary characters up until the first group of m checks on columns does not match the vector checks the data symbols and fix bugs.

Consider a matrix of information symbols aijsize (m - 1) x (l - 1) and add the check characters parity bijas in rows and columns. The resulting matrix is shown in Fig. 2.1, Fig. 2.2 shows the reading order of the matrix when m = 4, l = 5; Fig. 2,3 and provides a matrix in which the errors occurred in the second oblique row. Initially, the matrix contains only zero elements. The test vectors of sums by columns and rows do not match. After the cyclic shift by one group of four binary characters erroneous slash the number of hits in the first place and vectors checks on rows and columns are the same (see Fig. 2,3 b). If you add a check character modulo two to the first slanted row, the error will be corrected. The matrix will again be zero. This method of encoding and error correction easier previously known, which is the goal. A device that implements the encoding consists of the encoder and decoder circuits which are shown in Fig. 4, 5 and 6.

The encoder (Fig. 4) consists of register 9 shift, in which information is recorded in the order specified in the method, and adders 1-8 modulo two.

The encoder for the code length l of symbols from an alphabet of size 2< 6, 7, 8) and m - 1 adders modulo two with l - 1 inputs (2, 3, 4). Adders with m - 1 inputs connected to the cells of the serial shift register with numbers k = m [ (j - 1) mod l] + i, where i is the number of input adder (i = 0, 1, . . . m - 2); j - number adder (j = 0, 1, . . . l - 1). The outputs of these adders are connected to the cells of the serial shift register with numbers k = = m[(j - m + 1) mod l] + m - 1, where j is the number of the adder. Adders with l - 1 inputs connected to the cells of the serial shift register with numbers k = m[(j - 1) mod l] + +i, where i is the number of adder (i = 0, 1, . . . m - 2); j is the number of inputs of the adder (j = 0, 1, . . . l - 2). The outputs of these adders are connected to the cells of the serial shift register with numbers k = m[(l - 1 - i) mod l] + i, where i is the number of the adder. Information bus connected their lines to the cells of register numbers k = m[(j - 1) mod l] + i, where i = 0, 1, . . . m - 2; j = 0, 1, . . . l - 2.

The serial output of the shift register is the output of the encoder. The entry in the serial shift register is performed by the pulse T2 synchronization code groups, coinciding in time with the arrival of information at the encoder input. It is the register pulses sync bits Tabout. The characters from the outputs of the encoder groups m characters arrive at the modulator, where they compare the designed schematic diagram of the encoder for a code length of 5 characters from the alphabet 24.

The General scheme of the decoder is given in Fig. 2.5. The decoder consists of a shift register 10, in which information is stored in the manner described above, the first 11 and second 12 blocks adders (Boolean circuit that computes the check sum (syndromes) in columns 11 and 12 rows), unit 13 of the comparison, the matching unit 14, an adder 15 modulo two (schema component-wise summation modulo two) and key. The group of m binary symbols arranged in an oblique row, starting with the element in the first row, is considered as a multi-valued symbol from the alphabet 2m. In the shift register, this group of characters is located in adjacent cells.

For the code length l symbols from the alphabet 2mregister 16 consecutive shifts lm contains binary cells and it signals sync bits Tabout.

The first block 11 adders that compute a check sum on columns, consists of m adders 17-20 with m inputs. The inputs of the j-th (j = 0, 1, . . . , m - 1) adder connected to the cells of the serial shift register with numbers k = m[(j - 1) mod l] + i, where i is the number of input adder (i = 0, 1, . . . , m - 1). The outputs of the adders are the outputs of this logic circuit.

The second block 12 adders, . . , m - 1) connected to the cells of the serial shift register with numbers k = m[(j - 1) mod l] + i, where j is the number of inputs of the adder (j = 0, 1, . . . l - 1). The outputs of the adders are the outputs of the logic circuit.

Unit 13 comparison consists of m adders 25-28 modulo two with two inputs, the logical element OR NOT 29 with m inputs and a D-flip-flop 30. The inputs of the i-th adder unit connected to the comparison outputs of the i-th adders logic that calculates a check sum by columns and rows. The outputs of adders 25-28 are connected to the inputs of the logic element OR NOT 29, the output of which is connected to the D input of D-flip-flop 30. With the output of this trigger is controlled by the signal symbol synchronization T1that follow every m cycles Tabout. The output of D-flip-flop is the output of the Comparer.

The matching unit 14 consists of a register 31 consecutive shifts of m cells, logic element 32. The inputs of the cells of the shift register are connected to the outputs of the respective adders logic circuit that computes the check sum of the rows (or columns). The output of the shift register connected to the first input of logic element 32. The second input of this element is connected to the output of D-flip-flop 30 Comparer. The entry in the shift register p. the n input to the adder 33 in module two. This adder implements the component-wise summation. The output of the adder is the output of the entire circuit and the second input is connected in accordance with a common schema to the output of the register 16 consecutive shifts. The output register through the key 34 is connected to its input. The key is controlled by signal synchronization code groups T2(in the General scheme of the key is not highlighted).

The decoder operates as follows.

Coming code combination through the key 34 is fed to the input of register 16 consecutive shifts and recorded in groups of m binary symbols (oblique line), considered as a multivalued character of the alphabet 2m.

Output binary adders 17-24 Boolean circuit that computes the check symbols in rows and columns, formed the potentials corresponding to the check symbols. Parity row form the vector S1 of m elements. Check columns form a vector S2 of m elements. Parity in the last columns are not made. If the error is contained in the first group of m binary elements arranged in an oblique row, starting with the first element of the matrix, then the vector inspections on columns coincides with the vector of the error can be corrected. This case corresponds to the error in the first multivalued character of the alphabet 2m. If the error occurred in other multivalue symbol (in another group of m binary symbols arranged in an oblique row, starting with the element in the first row), the decoder starts to move in the cycle the information recorded in the register groups of m binary digits (i.e., equal to one multi-valued symbol) and to compare the test vectors S1 and S2. If S1 = S2, then the erroneous group of m binary symbols are in the first place and it can be fixed, folding its component-wise modulo two with a test vector S1 = S2. When the cyclic shift information in the register groups of m binary digits oblique rows are shifted by a matrix in a circle. The vector inspections on columns is saved, and the vector checks on rows cyclically shifted. If the number of columns is simple, the additional l consecutive cyclic shifts no identical pairs. All l shifts of the corresponding location in the first place l various sequential multi-valued symbols are different. Therefore, this method of decoding is unambiguous.

This code corrects single failure in a group of m binary symbols or one error is two characters from the alphabet 2m. Thus, this method of coding to fix one multivalued character spends two check symbols from the same multi-valued alphabet. Reviewed code is equivalent to the best known codes correcting a single multi-valued symbol: multivalued Hamming code with two check symbols or code is reed-Solomon with the two check characters. Compared with these known codes are considered coding method differs simpler decoder.

Considered the scheme does not contain complex logic elements realizing the multiplication and addition in the Galois field of 16 elements. Instead of complex logic circuits multiplication and addition in an integer field Galois uses XOR circuit, two registers, D-trigger, element OR NOT implemented as standard chips. The ease of implementation and structure of the decoder distinguishes it from known analogues and prototypes. A simpler scheme of the encoder and decoder allow to increase the reliability of the encoder and to increase the speed of encoding and decoding information. The proposed system corrects not only a single binary errors, and failures of entire groups of m binary symbols, which is 56) USSR Author's certificate N 1109924, CL H 04 L 1/10, 1983.

USSR author's certificate N 1358098, CL H 03 M 13/00, 1985.

SYSTEM FOR ENCODING AND DECODING WITH ERROR CORRECTION consisting of the encoder is performed on the shift register and decoder, containing the first and second blocks adders and adder modulo two, the output of which is the output of the decoder, characterized in that, to improve system reliability and performance, the encoder entered l adders modulo two with m - 1 inputs (where l is a Prime number; m is the length of the multivalue code with symbols from the alphabet 2m), the i-th entry of the j-th adder (where i < m - 1 and 0 j < l) combined with the input of the k-th cell of the shift register, where k = m [(j - i)mod l] + i, and is the corresponding information encoder input, and the output connected to the input of the k-th cell of the shift register, where k = m [(j - m + 1)mod l] + m - 1, and m - 1 adders modulo two with l - 1 inputs, the r-th entry of the n-th adder (where 0 r < l - 1, 0 < n < m - 1) combined with the input of the k-th cell of the shift register, where k = m[(r - n)mod l] + n, and the output connected to the input of the k-th cell of the shift register, where k = m[(l - n - 1)modl] + n and is the corresponding information input device that inputs the d - th cell of the serial shift register, where d = m[(q - p)mod l] + p, 0 < p < m - 1, 0 < q < m - 1 are information whom inputs and output of the encoder, in the decoder key is entered, the shift register block comparison and matching block, the first block of adders made in the form of m adders with m inputs, y-inputs s-x of the adders of the first block are connected to the outputs of the k-th cell of the shift register, where k = m[(s - y)mod l] + y, 0 < s < m, 0 < y < m, the second set of adders made in the form of m adders with l inputs, f-I g-x adders of the second block (where 0 f m, 0 < g < l) is connected to the outputs of the k-th cell of the shift register, where k = m[(f - g)mod l] + g, the outputs of the adders of the first block is connected to the first inputs of the block comparison, the outputs of the adders of the second unit is connected to the first input matching unit and the second unit of comparison, the output of which is connected to the second input matching unit, the third and fourth inputs of which are combined respectively with the third input unit of comparison and a clock input of the shift register are input record and a clock input of the decoder, the output matching unit connected to the first input of the modulo two, the output of which is the output of the decoder, the output of the shift register is connected to the second input of the modulo two and the first information input key, the second information and the control inputs and the output of which is connected respectively to the information

 

Same patents:
Up!