# The method of decoding of cyclic error-correcting code

(57) Abstract:

The invention relates to the field of communication technology and can be used in data transmission systems, systems, telemetering and telecontrol. The technical result is to increase the noise immunity of the reception of the cyclic code. The technical result is achieved in that on the transmission side to form the output sequence representing the sum modulo two of cyclic error-correcting code and a synchronization sequence at the receiving side perform the decoding of the received sequence, which adopted the first sequence is multiplied by the check polynomial error-correcting code, then perform detection of a particular combination synchronizing sequence taking into account errors and if it finds a certain combination of synchronizing sequence taking into account errors take the decision on whether frame synchronization and produce error-correcting code, and then determine the combination of errors and provide error correction, and the transmitting side output sequence recurrently continued, and on the receiving side of the symbols adopted post decoding of cyclic extensions of the received sequence. The invention relates to the field of communication technology and can be used in data transmission systems, and in systems, telemetering and telecontrol for receiving information without prior phasing.The method described in this application can be used for decoding linear error-correcting cyclic codes. Furthermore, the method also performs cyclic synchronization error correcting codes. Moreover, synchronization is not required to provide additional synchronization symbols, and uses the redundancy of the error correcting code. After the establishment of synchronization, the signs synchronization are removed from the error-correcting code, not reducing correcting ability of the code.Most effectively the proposed method for decoding cyclic code can be applied in communication channels with grouping errors, because the decoding is carried out in the sliding receive window, and outside the window, permit the occurrence of an arbitrary number of errors in the received sequence that does not lead to the transformation of the error correcting code. Under a sliding receive window in this application is understood to be a sequence composed of n consecutive main block length error-correcting code.The proposed method aims to address the urgent problem of increasing the noise immunity of the reception of the cyclic code when working in channels with a high level of noise.There is a method of decoding a cyclic error correcting code, wherein at the receiving side calculates the syndrome of the error correcting code. Upon detection of an undistorted error-correcting code that is determined by a zero syndrome, decide on the admission of error-correcting code and then allocate the data portion of an error-correcting code [1].This method has low immunity due to the low probability of correct synchronization and the fact that the decoding of error-correcting code performs only error detection without correction.There is also known a method of decoding a cyclic error correcting code, wherein on the transmission side to form the output sequence representing the sum modulo two of cyclic error-correcting code and a synchronization sequence at the receiving side, the sequence is multiplied by the check polynomial error-correcting code and calculate the clock consequently the chii frame synchronization and then allocate the data portion of an error-correcting code [2].However, this method has low immunity, due to the fact that decoding of error-correcting code performs only error detection without correction.Closest to the proposed method is a method (prototype) decoding of cyclic error-correcting code, namely, that on the transmission side to form the output sequence representing the sum modulo two of cyclic error-correcting code and the synchronizing sequence. At the receiving side adopted the first sequence is multiplied by the check polynomial error-correcting code and calculate the synchronization sequence. Next, carry out the detection of a particular combination synchronizing sequence with accounting errors imposed on the accepted sequence in the communication channel. Upon detection of the synchronization sequence shall take the decision on whether frame synchronization and produce error-correcting code. Then determine the combination of errors and perform error correction in the error correcting code [3].The disadvantage of this method is low pokahontas the e-correcting ability of the code.The purpose of the present invention is the increased robustness of reception due to the fact that on the transmission side output sequence recurrently continue using test ratio of cyclic error-correcting code on the receiving side additionally carry out decoding of cyclic extensions of the received sequence. When the decoding is carried out in the sliding receive window and outside sliding window, permit the occurrence of any number of errors in the received sequence, including exceeding the correction capability of error-correcting code, but do not result in the transformation code.To achieve the objective, a method for decoding cyclic error-correcting code, namely, that on the transmission side to form the output sequence representing the sum modulo two of cyclic error-correcting code and the synchronizing sequence. At the receiving side perform the decoding of the received sequence, which adopted the first sequence is multiplied by the check polynomial error-correcting code in the calculate synchronizers is lnasty with accounting errors superimposed on the accepted sequence in the communication channel. Upon detection of the synchronization sequence shall take the decision on whether frame synchronization and produce error-correcting code. Then determine the combination of errors and perform error correction in the error correcting code. What's new is that on the transmission side output sequence recurrently continued, at the receiving side of the symbols of the received sequence form a cyclic continuation of the received sequence and additionally carry out the decoding of cyclic extensions of the received sequence.Consider the implementation of the proposed method of decoding cyclic error-correcting code.On the transmission side form the output sequence. To do this, the original message volume k symbols of the first code cyclic error-correcting code. A coding information get the word cyclic code C(n,k)=a_{0},a

_{1}..., and

_{n-1}information whose length is k symbols, and block - n characters. Since the code is cyclic, there is a recurrence relation, with whom,k) are recurrently continue using the same ratio to the length of n

_{1}n and due to the cyclic error-correcting code to obtain a sequence of the same character codeK(n

_{1},k)=a

_{0},a

_{1},...,a

_{n-1},a

_{0},a

_{1},...,a

_{n-1},...,a

_{0},a

_{1},...,a

_{n-1},i.e. get the code with repetition. Property of such a code, unlike conventional code with repetition, is that any combination of characters in a sliding window of length n characters will be the word error-correcting code C(n,k).Next, form a constant cyclic synchronizing sequence of length n symbols. Such a sequence can be any sequence of suitable length with good timing properties, such as the sequence of maximal length code (reed-Muller 1-th order). This sequence recurrently continue up to the length n

_{1}charactersD(n

_{1})=d

_{0}d

_{1},..., d

_{n-1}d

_{0}d

_{1},..., d

_{n-1},..., d

_{0}d

_{1},..., d

_{n-1}.The symbols of the output sequence on the transmitting sideIn the(n

_{1})=b

_{0}b

_{1},...,b

_{n-1}b

_{0}b

_{1},...,b

_{n-1},..., b

_{0}b

_{1},...,b

_{n-1}receive by adding modulo two the end ->i=0...n-1.At the receiving side adopted the sequence, because of errors in the communication channel, in the General case differs from the transmitted sequence B(n

_{1}) and can be written as:B

^{l}(n

_{1})=b

^{1}

_{0}b

^{1}

_{1},...,b

^{1}

_{n-1}b

^{2}

_{0}b

^{2}

_{1},...,b

^{2}

_{n-1},...,b

^{j}

_{0}b

^{j}

_{1},...,b

^{j}

_{n-1}.After receiving the last character b

^{j}

_{n-1}from a communication channel decode the last received code word b

^{j}

_{0}b

^{j}

_{1},...,b

^{j}

_{n-1}and generate and decode cyclic continuation of the received sequence.In the proposed method under cyclic continuation of the received sequence is understood to be a code word composed of the last i(i=n-1...1) symbols of the received sequence, padded to length n symbols previously received symbols, so that the set of subscripts of all characters cyclic continuation is a circular sequence.For example, adopted the sequenceB

^{1}(n

_{1})=b

^{l}

_{0}b

^{1}

_{1},...,b

^{1}

_{n-1}b

^{2}

_{0}b

^{2}

_{1},...,b

^{IMI sequels will be written in the formbl0b11,...,b1n-1b20b21,...,b2n-1,...,bj0bj1,...,bjn-1bj-10bj-11,...,bj-1n-2;bl0b11,...,b1n-1b20b21,...,b2n-1,...,bj0bj1,...,bjn-1bj-20bj-21,...,bj-2n-2;bl0b11,...,b1n-1b20b21,...,b2n-1,...,bj0bj1,...,bjn-1b10b11,...,b1n-2;and yourself cyclic continuation will be presented in the following code wordsbj1,...,bjn-1bj-10; bj2...,bjn-1bj-10bj-11; bj3,...,bjn-1bj-10bj-11bj-12; ...bj1,...,bjn-1bj-20; bj2,...,bjn-1bj-20bj-21; bj3,...,bjn-1bj-20bj-2}

_{2},...,b

^{j}

_{n-1}b

^{1}

_{0}b

^{1}

_{1}; b

^{j}

_{3},...,b

^{j}

_{n-1}b

^{1}

_{0}b

^{1}

_{1}b

^{1}

_{2};...Just may be formed (j-1)x(n-1) cyclic extensions: for each of the j-1 repetitions of the code words in the received sequence can be written n-1 cyclic extensions.In addition to the decoding of the last received code words are also decoding of cyclic extensions.Decoding of error-correcting code begins with the calculation of the syndrome code received in the sliding receive window length of n characters. To do this, use the control ratio (1) is calculated according to the character of the settlement check symbols and then calculate the difference (sum modulo two) between the computed and received check symbols. This operation is equivalent to multiplying the input sequence to test the polynomial error-correcting code and can be implemented, for example, by using a shift register with feedback taken from the discharge register, which correspond to the nonzero coefficients of the test polynomial of cyclic error-correcting code.When decoding bradna binary combination of the d

_{0}corresponding converted synchronizing sequence.When the input sequence with errors will be calculated combination of some set {d

_{i}}, i0, corresponding to the sum of the non-zero syndrome code s

_{i}and converted synchronizing sequence: d

_{i}=s

_{i}d

_{0}.Further, recognizing the combination of the d

_{o}or a combination of the set {d

_{i}} perform the detection of the synchronization sequence. This is possible if the frequency error is within the correcting ability of the code, the synchronization sequence will be applied to a non-zero syndrome whose values for different fixed combinations of errors will be different from each other. The detection of the synchronization sequence can be performed, for example, by using a predetermined table. Entry in this table are all the syndromes to correct combinations of errors in the sum with a synchronizing sequence, and the output is the phase shift of the synchronizing sequence, i.e., the amount of cyclic shift error correcting code.The detection of the synchronizing sequence ¡error correcting code, i.e., to define the beginning of the error-correcting code.Next, the synchronization sequence is subtracted from the input sequence, and the result is the word error correcting code.For undistorted code word data portion of an intact can be transferred to the recipient of the message.In the case of receiving the input code word errors additionally carry out the determination combination of errors and correction of errors in the information part. Correction corresponding to the information symbols of the code is done by recognition of the bits of the syndrome of the codeword and determining a combination of errors. In this case, correction of errors in the selected information part error-correcting code can be performed, for example, by using a predetermined fault tables, the entrance of which are recognized by the combination of the syndrome, and the output is correct combinations of errors.The imposition of a synchronizing sequence for the code word on the transmitting side adds the words of the error correcting code property samsungringtones and does not require the introduction of additional redundancy code for synchronization purposes. This synchronization can NASBA, decoding the code word is carried out in a window that moves and also for cyclic extensions of the received sequence. For correct decoding of the number of errors in the moving window should be within the correcting ability of the error correcting code, and the remaining part of the received sequence can be an arbitrary number of errors that do not result in a transformation of the error correcting code. The last condition for the majority of error-correcting codes is not hard, because, as a rule, the probability of transformation of the error correcting code is significantly less probability of detecting errors. By lengthening the received sequence by the value of its cyclical expansions and increasing thereby the number of attempts to decode the code robustness of the proposed method of decoding above are known. In practice, even the use of a small part of all possible cyclic extensions code to improve noise immunity, can give significant gains. For example, in the proposed method, in contrast to the known, the code word will be accepted, if the symbols adopted in the beginning of the sequence, together with the symbols adopted by the ri in the middle of the adopted sequence may have an arbitrary number of errors, do not result in a transformation of the error correcting code. In this case, to decode only use part of the cyclical expansions of the following formb

^{j}

_{1},...,b

^{j}

_{n-1}b

^{1}

_{0}; b

^{j}

_{2},...,b

^{j}

_{n-1}b

^{1}

_{0}b

^{1}

_{1}; b

^{j}

_{3},...,b

^{j}

_{n-1}b

^{1}

_{0}b

^{1}

_{1}b

^{1}

_{2}; ...and sliding receive window of symbols, in which the decoding error-correcting code is moved according to the sequence, as would be rolled into the ring.As an example, note that when using the proposed method for decoding binary cyclic code, BCH(63,32), recurrently continued to the length of 126 bits, the probability of exclusion of the message is equal to 0.03 for the Gaussian channel, the average probability of error which is 0.01. Decoding the code performs only error detection. For comparison, a similar probability of exclusion for the same channel decoding algorithm without the use of cyclic extensions is equal to 0.13. To obtain the same probability of exclusion, equal to 0.03, for the decoding algorithm without the use of cyclic extensions of interference is in the proposed way.Achievable technical result of the proposed method of decoding cyclic error-correcting code is to increase noise immunity.Sources of information1. Losev centuries, Brody E. B., Korzhik Century. And. Search and decoding of complex discrete signals / Ed. by C. I. Korzhik. - M.: Radio and communication, 1988, page 136.2. Bolkhovitin L. M., Gurkin S. P., Kvashennikov centuries, Sosin P. A. transfer of the formalized messages self-synchronizing code with variable parameters. Technology communications, vol. SCC, vol. 8, 1990, page 39.3. Beck, C., B. C. N., Judge O. P. Method of synchronization messages. Sat.: Construction and analysis of communication systems. M.: Nauka, 1980, page 84. The method of decoding of cyclic error-correcting code, namely, that on the transmission side to form the output sequence representing the sum modulo two of cyclic error-correcting code and a synchronization sequence at the receiving side perform the decoding of the received sequence, which adopted the first sequence is multiplied by the check polynomial error-correcting code, and as a result calculate the synchronized is Telenesti with accounting errors superimposed on the accepted sequence in the communication channel, and when it detects a certain combination of synchronizing sequence with accounting errors imposed on the established sequence, take the decision on whether frame synchronization and produce a cyclic error correcting code, and then determine the combination of errors and carry out the correction of errors in the information part of cyclic error-correcting code, wherein at the transmitting side output sequence recurrently continued, at the receiving side of the symbols of the received sequence form a cyclic continuation of the received sequence and additionally carry out the decoding of cyclic extensions of the received sequence.

**Same patents:**

FIELD: circular memory technologies.

SUBSTANCE: into memory cell, containing the oldest data record, new data record is placed and then pointer is renewed, while aforementioned pointer has first pointer (P1,P1*) and second pointer (P2,P2*), being excessive relatively to first pointer, each of these pointers has control number in form of additional or reversed code of the same pointer.

EFFECT: development of method and circular memory for reliable recording of pointer.

2 cl, 4 dwg

FIELD: information technology.

SUBSTANCE: device has a memory unit (1), input (2) and output (3) coding units, an error detection unit (4), a unit of AND elements (5), an AND element (6) and an OR element (7).

EFFECT: more reliable functioning of the device for storing and transferring information owing to double error detection with minimal time and hardware expenses.

1 dwg, 2 tbl

FIELD: information technology.

SUBSTANCE: highly-reliable information storage and transmission device has a memory unit, an input coding unit, an output coding unit, an error detection unit, a block of AND elements, an AND element, and OR element, a device reset input, a write input, a read input, address inputs, data inputs, a clock input, data outputs and an "error" signal output.

EFFECT: high reliability of the device owing to detection of all single errors and maximum number of double errors with minimum time consumption.

1 dwg, 1 app

FIELD: information technology.

SUBSTANCE: method involves generating and storing a given state of programme objects, and using an error detection mechanism which operates in parallel to execution of the programme object with both computer kernels and which checks results of executing each computer instruction by the computer kernels for identity while identifying errors if said results to not coincide. When detecting errors, said error detection mechanism switches the programme object already specified for execution into a given state and re-launches it from that state, even though at the moment of detecting errors, the programme object was not fully executed, wherein an additional computer device is used to detect errors.

EFFECT: restoration of full operational capability and functional reliability of a computer system owing to constructive processing of sporadic errors.

17 cl, 2 dwg

FIELD: information technology.

SUBSTANCE: apparatus has a memory module, an input coding unit, an output coding unit, an error syndrome calculating unit, a decoder, switches, compensators, OR elements, an inverter and AND elements.

EFFECT: more reliable operation of the apparatus owing to correction of single errors in separate data bytes and detection of random errors in data bytes.

1 dwg, 5 tbl, 1 app

FIELD: information technology.

SUBSTANCE: in one version, the method comprises steps for receiving over one reception channel a discrete code message of magnitude I and weight W, said message is demodulated to the level of a pulse sequence, a symbol message is formed, an lxl square matrix M is formed, its eigen values C_{i} are calculated, the pulse sequence is checked for errors, wherein from the obtained eigen values, the maximum eigen value C_{max} is selected and C_{max} is not equal to W, there are errors in the received discrete message.

EFFECT: indication of boundaries of a block of code combinations of discrete messages within which an error is contained, which enables to use only one reception channel in communication systems employing packet transmission with repeated request.

16 cl, 13 dwg