RU2747881C1 - Method for decoding long block code using viterbi algorithm - Google Patents

Abstract

FIELD: transmission of encoded messages.

SUBSTANCE: invention relates to the field of transmission of encoded messages. The technical result is achieved in the method of decoding a long block code using the Viterbi algorithm, in which the incoming code stream is received as an infinite convolutional code and fed by subblocks of n₀ code symbols to the input of the Viterbi decoder, and after receiving by the decoder all code subblocks are fed to the decoder again the same code subblocks , after which the decoding process is interrupted and the decision symbols of the Viterbi decoder are selected, which are at a distance of at least the number of symbols from the place of reception of the last code subblock of size n₀, while after receiving a longer part of the code stream, the adopted decision symbols along all paths are replaced with the calculated symbols - decisions of the decoder and replace the paths of the received part of the codestream stored by the AV decoder with a single final decision vector and store the total number of symbols closest to the receiving location, and the middle part of the decision vector is transmitted to the recipient of the original message.

EFFECT: expanding the range of technical means that can be used to decode block codes while reducing requirements for decoder memory.

1 cl

Description

The invention relates to the field of transmission of encoded messages and can be used, mainly, when decoding long block codes using the Viterbi algorithm in conditions of a high probability of errors in the corrected data.

Decoders and their corresponding algorithms for decoding digital data are widely used to correct errors in the transmission and storage of digital information.

Known methods and devices for decoding error-correcting codes.

One of the known methods of decoding error-correcting codes, including the majority decoding [Ovechkin G.V. and Zolotarev V.V. Effective algorithms for error-correcting coding for digital communication systems. Electrosvyaz, No. 9, 2003, p. 34-37] is that the information symbols transmitted to the recipient are sent to the decoder from the communication channel, in which errors can be introduced into the digital message, together with redundant code symbols, which are converted into syndrome symbols, the values of which depend only on errors that occurred in the communication channel, and do not depend on the values of information symbols transmitted to the recipient, and are summed in the decoder using a threshold element at each cycle of operation after the next shift of data in their registers, the corresponding symbols in the register cells determined by the selected code, and after summing, they are comparing the result with a threshold value, according to the results of which it is judged about the need to replace the decoded information symbol.

The disadvantage of this method is the relatively low efficiency due to the operation of summing integers, which reduces the speed of decoding. In addition, this method does not work at high noise levels.

Another close in technical essence and the achieved result is a method for decoding an error-correcting code [RU 2377722, C1, H03M 13/43, 27.12.2009], which consists in the fact that binary and / or non-binary information symbols of the code are sent to the decoder from the communication channel together with redundant symbols of the code, convert them into symbols of the syndrome register and send them to the threshold element, where estimates of the values of the decoded symbols are calculated based on the symbols in the cells of the syndrome determined by the decoded error-correcting code, the computation result is compared with the threshold value and, based on the comparison results, a decision is made on the need to change the decoded information symbol, moreover, the syndrome symbols are sent to the threshold element for such a number of cycles of its operation relative to the moment of making a decision on the value of the decoded symbol, which corresponds to the number of symbols of the syndrome register at the input of the threshold element, while the decision on the need to change the information o symbols are made on the basis of pipelined calculations, in which decisions are made simultaneously at different stages regarding the whole group of symbols to be decoded.

The disadvantage of this method is the complexity of the pipelined multi-cycle computer and the same inability to operate with a high level of input noise.

The closest in technical essence to the proposed one is a method for encoding and decoding a block code using the Viterbi algorithm [RU 2608872, H03M 13/43, 01/25/2017], including the supply of the original message with a code rate R = k ₀ / n ₀ to the encoder containing k ₀ shift registers with a length of K bits each, the contents of the cells of which, in accordance with the code used, are fed to the inputs of n ₀ adders mod2, from the outputs of which code symbols are _{sent by subblocks of n 0} symbols to the data transmission channel, from which they are fed by subblocks of n ₀ characters to the input of a decoder operating according to the Viterbi algorithm, containing 2 ^{(K-1) * k0} memory cells for storing the weights of the difference of paths and the received message, 2 ^{(K-1) * k0} shift registers for storing surviving paths, 2 ^{K * k0} calculators additional weights of the path difference, 2 ^{K * k0} calculators of total new path differences and 2 ^k0 devices for comparing the weights of paths and choosing the path with the least weight, while the encoded information sequences they are divided into blocks, which are additionally divided into k ₀ smaller blocks, which are placed in k ₀ encoder registers for the same code, but with an increased register length up to the value K + U, U≥K, and all k ₀ registers after entering into them information symbols are folded cyclically by connecting the outputs of the last cells of each of these registers with their inputs, after which K + U synchronous shifts of all the resulting cyclic registers are performed, during which K + U code subblocks of n ₀ code symbols are formed, which are sent to the channel, and then subblocks of n ₀ code symbols are fed to the input of the Viterbi decoder, and after the decoder has received all K + U code subblocks of size n _{0, the} same code subblocks are fed to the decoder again in the same order at least two more times, after which the decoding process is interrupted and on the surviving path of minimum weight, (K + U) * k ₀ symbols of decisions of the Viterbi decoder are selected, which are at a distance of at least 5 * K * k ₀ symbols from the place of reception of the last th code subblock of size n ₀ .

When using this method, at the transmitting end of the information transmission system, it is encoded with a block quasi-cyclic code of length n using a generating polynomial of a convolutional code of significantly smaller length K, so that nR >> K, where R is the code rate of the applied block code.

At the receiving end of the information transmission system, the decoder implementing the Viterbi algorithm operates in the same way as when decoding the original long convolutional code from an arbitrary place. It takes the first sub-block of code symbols and processes them according to the rules of the Viterbi decoding algorithm. Then it accepts the next same block, and so on.

Since the symbols of a binary block quasi-cyclic code longer than the original convolutional code are transmitted over the information transmission channel, after receiving and processing the last code subblock of this block code of size n, the decoder is cyclically fed again the first subblock of the already received code symbols of this code, then the second and etc. Depending on the length of the code and the noise level, the decoder can be cyclically fed m = 2 ÷ 5 or more times all the code symbols of the received code block, depending on the code and the noise level of the channel.

However, since the quasi-cyclic code does not have a conditional beginning, the decoding algorithm, as in the case of an infinite convolutional code, provides an exit to the correct solution only after the first code subblocks arrive at the decoder D ~ (3 ÷ 20) K.

After receiving the indicated D = (3 ÷ 20) K code subblocks, when the Viterbi algorithm of the convolutional code provides access to the level of sufficiently reliable decisions with respect to the decoded code stream, the decisions of the decoder are necessarily repeated with a period nR. Therefore, taking into account the fact that it is not an infinite message that is decoded, but a block with nR binary information symbols, the recipient of information can only transmit a binary information block of length nR from the middle of the sequence processed by the Viterbi decoder of a slightly larger total length mnR.

The closest solution has a serious drawback. To implement the method, the block AV decoder must store all 2 ^(K-1) paths tracked during operation, and their length is mnR bits. This means that if it is necessary to decode long codes, the memory size used by such a block AV decoder must be of the order of M ~ mnR2 ^(K-1) For large values of n, which is typical for long codes, this can amount to many hundreds of Gigabits, which is unjustified complicates the decoding hardware.

The problem that is solved in the invention is to develop a method for decoding a long block code using the Viterbi algorithm while reducing the requirement for the complexity of decoders, in particular, for their memory size.

The required technical result consists in expanding the arsenal of technical means that can be used to decode long block codes using the Viterbi algorithm while reducing the requirements for the complexity of the implemented decoding methods, in particular, for their memory size.

The problem is solved, and the required technical result is achieved by the fact that, according to the method of decoding a long block code using the Viterbi algorithm, which consists in the fact that the incoming code stream is received as an infinite convolutional code and fed by sub-blocks of n ₀ code symbols to the input of the decoder Viterbi, and after the decoder receives all K + U code subblocks of size n _{0, the} same code subblocks are fed to the decoder in the same order at least two more times, after which the decoding process is interrupted and (K + U) * k ₀ symbols of decisions of the Viterbi decoder, which are at a distance of at least 5 * K * k ₀ symbols from the receiving place of the last code sub-block of size n ₀ , according to the invention, after receiving a longer part of the code stream than the length of the generating polynomial of the convolutional code K, K≤≤nR, decoder decision symbols along all paths are replaced with computed decoder decision symbols and stored paths are replaced. th part of the codestream of the entire code to a single final decision vector and store the total number of decoder decision symbols closest to the receiving location from the received part of the codestream, and the middle part of the final decision vector from it is transmitted to the recipient of the original message.

Let's give an example of the implementation of the proposed method.

The received codestream is supplied to an AV block decoder and is then received as an infinite convolutional code. Since the block AV decoder works, as it were, with an infinite input sequence, then after receiving the very first symbols of the decoded message in the immediate vicinity of the place where symbols are received from the channel, the values of the decisions of the AV decoder in most positions and along all stored paths contain many erroneous values. And only at a sufficient distance D from the place of receiving symbols from the channel, the share of errors of the AB decoder becomes small in accordance with the selected correcting capabilities of the code for the AB decoder. This follows, in particular, from [V.V. Zolotarev, G.V. Ovechkin. Anti-jamming coding. Methods and algorithms. Directory. M., "Hot line - telecom", 2004, p. 67-68,] which illustrates the process of convergence of the convolutional AV decoder solutions to the correct values, i. E. with a small number of errors at a sufficient distance from the place of receiving code symbols from the channel. Therefore, in the block AB decoder at a sufficient distance D ~ (3-10) K from the beginning of reception, the symbols of all stored decoder paths will be basically correct and identical. Even more accurate and correct values can be obtained by different methods, for example, majority. This means that you don't have to store an exponentially large number of full long paths. It is possible, at a distance D from the place where the code symbols are received from the channel, to perform refinement calculations, which are quite simple, and then store only these (mnR-D) symbols of the conditionally final decisions of the AV decoder until the decoding procedure is completed m times of the received block, and then select the required symbols from the middle this is already the only stored sequence. In this case, the new required memory capacity of such a block AV (BAV) decoder will be only M ₀ ~ D2 ^(K-1) << M. For large lengths of n block codes, this, on the one hand, will save tens and hundreds of times the memory of BAS decoders, which no longer needs to be increased to hundreds of Gbits. But, in addition, such a BAV decoder freely decodes block codes of arbitrarily large length, since its memory will always be of the order of M ₀ .

This achieves the required technical result, which provides a large saving in the memory of the BAS decoder and at the same time provides the ability to decode block codes of arbitrary length. In this case, it remains important that the value D of the length of completely stored paths in the decoder is sufficient so that the vector of final decisions formed in the improved block AV decoder does not really differ from the true optimal solution.

The verification of the proposed technical solution was carried out by computer simulation of a block code of length n = 1000 for a generating polynomial of length K = 15. As a result, it turned out that even if the ratio of the relative energy of the Gaussian binary channel (ABGN channel) E _b / N ₀ = 1.5 dB is quite heavy for the decoder, the solutions of the original optimal BAS decoder almost always coincided with the solutions of the decoder operating according to the proposed modified algorithm with greatly reduced memory size for all 2 ¹⁴ = 16384 stored path segments from the place of receiving symbols of length D≥200 bits.

The differences did not increase the bit error probability of the tested decoder by more than 1.23 times in several experiments of a sufficiently long duration with a total number of transmitted symbols of more than 3 million information symbols. This is undoubtedly a good result when comparing the known and proposed methods. For a lower noise level, the characteristics of both decoders turned out to be practically the same.

When considering block codes of length n = 2000 and n = 4000 with the same polynomial K, the decoding results also did not change. Together, these data fully confirm the correctness of the proposed technical solution, which greatly expands the real scope of application of block codes with optimal decoding according to the Viterbi block algorithm with the actual minimum required amount of memory used in the decoder.

Claims (1)

A method for decoding a long block code using the Viterbi algorithm, which consists in the fact that the incoming code stream is received as an infinite convolutional code and fed by subblocks of n ₀ code symbols to the input of the Viterbi decoder, and after the decoder receives all code subblocks of n ₀ code symbols in the decoder again serves the same code subblocks in the same order at least two more times, after which the decoding process is interrupted and the symbols of decisions of the Viterbi decoder are selected on the surviving path of the minimum weight, which are at a distance of at least the number of symbols from the place of reception of the last code subblock of size n ₀ , characterized in that after receiving a longer part of the codestream than the length of the generating polynomial of the convolutional code in the quasi-cyclic code, the decision symbols of the AB decoder along all paths are replaced by the calculated decoder decision symbols and the stored paths of the received part of the codestream of the entire code are replaced with a single one final solution vector and zap The total number of symbols closest to the receiving location from the received part of the codestream is remembered, and the middle part of the final decision vector from it is transmitted to the recipient of the original message.