Method of encoding and decoding parallel combined entanglement codes and encoder/decoder system therefor

The present invention relates to a method for encoding and decoding parallel combined convolutional codes and an encoder and decoder for encoding and decoding parallel bonded convolutional codes, generally used in error correction encoding for short message transmission over weak channels, especially in the parallel combined convolutional convolution technique. tail bits and its decoder.

There is known a method of parallel combined coding, called either parallel joint convolution PCCC coding or turbo coding, associated with impressively demonstrated coding gains when delivering 10,000 or more bits to blocks, as shown, for example, in C. Berrou, A. Glavieux and P. Thitimajshima under the title "Error correction encoding and decoding close to the Shannon limit: turbocodes" Proceedings of the IEEE International Conference Communications, 1993, pages 1064-1070, in JD Anderson's publication "Turbocoding scheme", report IT-146 ISSN 0105-854, Institute of Telecommunication, Technical University of Denmark, December 1994 and in P. Robertson, titled "Illuminating the Code and Decoder Structure of Parallel, Linked, Recursive Systematic Turbocodes," 1994, IEEE Globecom Conference, pages 1298-1303.

Turbocode performance degrades substantially as the length of the encoded payload decreases. This phenomenon is related to the strong dependence of its constituent weighting structures of recursive systematic convolutional codes on the block length. The second problem is the proper termination of message blocks delivered to the turbocoder. In the publication of O. Joersson and H. Meyr entitled "The Termination of Turbocode Grids", IEE Electronics Letters,

183 537 Vol. 30, No. 16, Aug. 4, 1994, pages 1285-1286 teaches that interleaving used in turbo coders can prevent both the interleaving and non-interleaving encoder input sequences from terminating with a single set of trailing bits. Although it is possible to use a second trailing sequence arranged in the message structure such that the interleaving data sequence encoder is properly terminated, it doubles the encoder termination preliminary operations and reduces the effective code rate. The alternative is to not finish one of the encoder sequences, but this degrades the performance of the codec system, especially when using short messages. In the publication of AS Barbulescu and SS Pietrobona, "Ending Turbocode Grids in the Same State", IEE Electronics Letters, 1995, Vol 31, No.1, Jan.5, Pages 22-23, shows a method that places constraints on the interleaver design to complete binary recursive systematic convolutional encoders by a single sequence of termination bits. Their performance results show some deterioration compared to the performance achieved by terminating both encoders when the optimal interleaver is used. In addition, the published bit error data as a function of the energy per bit factor to the noise power spectral density Et / Νθ shows a smoothing of the error rate in bits in the range of E_b/ N₀when RSC codes are used in the turbo coder.

Known turbo decoders use "maximum a posteriori" MAP decoders such as those described in LR Bahl, J. Cocke, F. Jelink, and J. Raviv in the publication "Optimal Linear Code Decoding to Minimize Symbol Error Rate", IEEE Transactions of Information Theory, March 1974, pages 284-287, or Viterbi soft-output decoders, such as those described in J. Hagenauer and P. Hoeher, titled "The Viterbi Algorithm with Soft Decision Exits and Its Applications," 1989 IEEE Globecom Conference, pages 1680-1686.

The formal tabulation of the forward decision depth LF (e) for convolutional codes is presented in JB Anderson and K. Balachandran's publication, "Decision Depths of Convolutional Codes", IEEE Transactions on Information Theory, vol. IT-35, pages 455-59, March 1989. Many of the properties of LF (e) are disclosed in this publication as well as in JB Anderson and S. Mohan's "Source and Channel Coding - Algorithmic Approximation", Kluwer Academic Publisher, Norwell, MA, 1991. The essential property is that there is a simple linear relationship between LF and e, for example for 1/2 speed codes, LF is approximately 9.08e. The algorithm for finding the forward decision depth LF (e) is also presented in the publication of JB Anderson and K. Balachandran entitled "Decision depths of convolutional codes".

It is known that non-functional, systematic convolutional codes would not be useful as component codes in a parallel, concatenated coding scheme due to the long RSC code distances for relatively long data blocks, as shown in S. Benededetto and G. Montorsi's publication "Designing Parallel , combined convolutional codes ”, IEEE Transactions on Communications.

The method of the invention consists in encoding a block of data bits in a first component encoder by supplying a non-recursive systematic convolutional code with tail bits, thereby producing a first component code word comprising the data bits and parity bits. A block of data bits is interleaved to provide a permuted block of data bits. The resulting permuted block of data bits is encoded in the subsequent component encoder by supplying a non-recursive, systematic convolutional code with tail bits thereto, thereby producing a second component code word including the data bits and parity bits. The resulting permuted data bit block is repeatedly interleaved and encoded by the remaining N-2 interleavers and the remaining N-2 component encoders, thereby producing code word components including data bits and parity bits, and formatting the component code bits to provide composite code words. Complex words are introduced

183 537 code to a channel, the received composite codeword is received from the channel, the received composite codeword is formed from the received composite codeword, delivering each individual received composite codeword to one of the plurality of the N component composite decoders, each individual component decoder also receives a set of a priori probabilities for the value of data bits, and decodes the received, component codeword through an iteration process through N component decoders and Nl interleavers to provide soft decision outputs from a composite decoder. Through each of the N component decoders, soft decision information is provided on each data bit in the data block in the order encoded by the component encoder, each of the N1 component decoders is interleaved with soft decision information from the previous component decoder to provide the permuted soft information block to the next one. component decoder, the a priori soft decision information set for the first of the N component decoders is computed with the assumption that that the data bit values ​​are equally susceptible to the first iteration and then include a first soft decision information function, which first soft decision information function is provided back from the Nth decoder by a first interpreter comprising Nl punishers corresponding to Nl interleavers, wherein The Nl of the peers of the first deleter are provided in reverse order to the Nl of the interleavers, and the a priori soft decision information set provided to each other component decoder includes a first soft decision information function from the previous subsequent component decoder, and performs the payment in a second payment circuit to provide a second soft decision output function from the N th component decoder. as the decision outputs of the soft complex decoder using Nl of the debuffing circuits corresponding to the Nl of the interleavers, wherein the Nl of the deletion circuits of the second deleter are provided in reverse order to the Nl of the interleavers.

Preferably, the formatting is performed such that the composite code word includes only one occurrence of each bit in a block of data bits.

Preferably, the formatting is performed such that the composite codeword comprises only selected bits containing the codeword components in accordance with a predetermined pattern.

Preferably, the number of iterations through component decoders, interleavers and de-payment circuits is used as a predetermined number.

Preferably, iterations through the component decoders, Nl interleavers and the de-interleavers are performed until decoder convergence is detected, if the number of iterations is less than the maximum number, otherwise the decoding ends after the maximum number of iterations and a second function of decision outputs is provided through the composite decoder. of the Nth component decoder as its soft decision output by the second deleter.

Preferably, a decision rule is performed to provide the hard decision outputs as a function of the soft decision outputs of the composite decoder.

Preferably, decoding is performed by N component decoders comprising circular MAP decoders, wherein the eigenvector problem is solved during decoding.

Preferably, decoding is performed by N component decoders containing circular MAP decoders, and the decoding uses a recursion method.

Preferably, formatting is used to designate bits selected from the component codewords that contain a composite code word according to a predetermined pattern, and decoding to input neutral values ​​for all marked bits when forming the received component code words.

The encoder and decoder arrangement of the invention is adapted to systematically provide non-recursive systematic convolutional codes with tail bits to a block of data bits and various permutations of the data bit block, and to produce component codewords including data bits and parity bits, and a composite codeword formatter for formatting a bit set from component code words for providing a composite word

183 537 code, a composite codeword converter into a composite codeword for receiving the composite codeword from the channel and producing therefrom a plurality of N received component codewords, a plurality of N component decoders, and each individual decoder is adapted to receive a received component codeword from the transducer a composite codeword into a composite codeword, each individual decoder is also set to receive a priori soft decision information set for data bit values, and each of the N component decoders is adapted to provide soft decision information in each data bit in the data block in the order encoded by the component encoder in the parallel, interconnected encoder, the plurality of the N1 interleavers, and each individual interleaver to interleave the component soft decision information. a decoder for providing the permuted soft information block to the next component decoder, and the received codewords are decoded by an iteration process through the N component decoders and Nl interleavers to provide soft-decision output from the composite decoder, a first interpreter including Nl punters corresponding to Nl interleavers, where Nl of the first peers of the first peers are inversely provided. sequences to Nl interleavers, and a priori soft decision information set for the first of the N component decoders is computed assuming that the data bit values ​​are equally susceptible to the first iteration and then contain a first soft decision information function, the first soft decision information function being derived by the N ths a decoder and fed back by the first puncturing circuitry, a priori soft decision information bank, provided to every other component decoder, includes a first soft-decision information function from the previous consecutive component decoder and a second interpreter comprising Nl of the peers corresponding to the Nl interleavers, where Nl of the second peers are provided in reverse order to the Nl of the interleavers and the second interpreter pays the second a soft decision output function of the Nth component decoder to provide the soft decision output of the composite decoder.

Preferably, the composite codeword formatter produces a composite codeword such that it includes only one occurrence of each bit in a block of data bits.

Preferably, the composite code word is a composite code word including only selected bits having component code words according to a predetermined pattern.

Preferably, the number of iterations through the component decoders, interleavers and de-payment circuits is a predetermined number.

Preferably, the component decoders, interleavers and the de-payment circuits are adapted to iterate until decoder convergence is detected if the number of iterations is less than the maximum number, otherwise the decoding ends after the maximum number of iterations and the composite decoder provides a second soft decision output function from N- of this component decoder as its soft decision output by the second deleter.

Preferably, the encoder and decoder circuitry comprises a decision device for executing a decision rule to provide the hard decision outputs as a function of the soft decision outputs of the decoder.

Preferably the N component decoders include circular MAP decoders to be decoded by solving the eigenvector problem.

Preferably, the N component decoders include circular MAP decoders to be decoded using a recursion method.

It is an advantage of the invention to provide an improved parallel joint coding technique for short data blocks. In the method and arrangement of the present invention, the parallel, coupled convolutional coding scheme uses non-recursive systematic NSC convolutional codes with tail bits.

The decoder iteratively uses maximum posterior cyclic decoding to produce hard and soft decision outputs. The use of codes with trailing bits solves the problem of terminating the input data sequences in turbo coding by effect

183 537 which prevents degradation of decoder performance for short messages. While NSCs are typically weaker than recursive, systematic RSC convolutional codes having the same memory asymptotically as the data block length increases, any NSC code distance is less sensitive to the data block length. Thus, parallel combined coding with NSC codes will be performed better than with RSC codes having the same memory for messages that are shorter than a certain payload threshold dimension.

Fig. 1 shows a simplified diagram showing a parallel combined encoder, Fig. 2 - simplified diagram showing a decoder for parallel, connected codes, Fig. 3 - simplified diagram showing a non-recursive systematic convolutional encoder. with trailing bits for use in the inventive encoding scheme, Fig. 4 a simplified diagram showing a circular MAP decoder used as a component decoder in a decoder for the parallel combined convolutional coding scheme of the present invention; and Fig. 5 - a simplified diagram showing a different embodiment of a circular MAP decoder used as a component decoder for the parallel combined convolutional coding scheme of the present invention.

Figure 1 shows a general block diagram of an encoder signal processing circuit 10 for parallel, combined encoding schemes. It includes a plurality of N component encoders 12 that act on blocks of data bits from the source. The data blocks are permuted by the interleaving algorithms through the interleavers 14. There are Nl interleavers for the N encoders 12. Finally, the outputs of the component encoder are combined into a single composite code word by the composite code phonatizer 16. The composite codeword formatter 16 is selected to match the characteristics of the channel, and may be followed by a frame formatter selected to match the channel and channel access technique of the communication system. The frame formatter may also implement other necessary pre-operations, such as control bits and timing symbols.

Significant improvements in the code rate can be obtained in parallel, combined coding if the component codes are systematic codes. The output code words produced by the systematic encoder include the raw data bits provided as input to the encoder and additional parity bits. The redundancy introduced by the parity bits gives the code error correction capability. Thus, when systematic encoders are used in the parallel, coupled encoder shown in Fig. 1, the code words produced by all component encoders 12 include input data bits. If the formatter 16 forms a data packet or composite code word having only parity bits produced by each component encoder 12 and a block of coded information bits, substantial improvement in the rate of the composite, parallel, combined code is accomplished by eliminating repetition of information bits in the transmitted composite code word. . For example, if component encoder 1 and component encoder 2 of a parallel concatenated convolution PCCC code containing two component codes are both 1/2 rate codes, the rate of the composite parallel concatenated code is incremented from 1/4 for non-systematic component codes. to 1/3 for systematic component codes.

Parallel coupled coding schemes that use recursive systematic convolutional RSC codes have been the final topic of much research. These parallel, convolutional PCCC codes are also commonly known in the literature as turbo codes. Convolutional PCCC codes can achieve impressive performance in expressing the bit error rate as a function of the energy per bit factor to the spectral noise power density E_b/ N₀ for relatively large messages, ten thousand or more bits. However, it has also been shown that the coding gain obtained by the turbo codes decreases significantly as the size of the data block decreases, since the forces of recursive systematic component convolutional codes are quite sensitive to the length of the data block. On the other hand, the performance of a non-recursive systematic convolutional code with tail bits is independent of the data block length for most practical purposes, with

183 537, the resulting performance only degrades when the block of coded data bits is smaller than the minimum dimension which is determined by the NSC decision degree.

Figure 2 shows a general decoder 20 for parallel, combined codes in the form of a block diagram. Decoder 20 includes a composite codeword to component codeword converter 22 that converts the composite codeword received from the channel into individually received codewords for each component decoder 24, with N component decoders 24 corresponding to the N component encoders of Fig. 1 of the same type or the same interleavers 14 as are used in the parallel coupled encoder of Fig. 1 and the first and second payment circuits 28 and 29, each having a sequence reordering property that is equivalent to the serial connection Nl of the deaerators 30 Nl corresponding interleavers used for encoding. The required ordering of these payment circuits is shown in Fig. 2 and is inverse to the ordering of the interleaving circuits. At the outputs of the component decoders 24, there is some type of soft decision information about the evaluated value of each data bit in the received codewords. For example, at the decoder component outputs there may be a first function of the probabilities that the decoded bits are 0 or 1 in the received symbol sequence for the channel. One example of such a first function removes the influence of the conditional probability P {d^J.t = 0 | Y^J.t} from the soft component decoder decision output which is input to the next sequential component decoder after the appropriate permutation, where P {d^J._vol = 0 | Y]} is the probability that the j-th information bit at time t is 0 conditioned by the j-th systematic bit of the received output symbol Y_vol channel. Alternatively, the soft decision information at the output of the component decoders 24 may be a likelihood ratio function₌ P {d ;! = 1 |₌ 1 - Ρ {άξ = 0 | Y,^L.} ¹ P {d² = 0 | Y ^} P {d ^ = 0 | Yj^L.} or as a function of the likelihood ratio log [Δ (d^J._vol)].

The Nth component decoder has a second output, i.e. a second conditional probability function for the decoded bit values ​​or the likelihood ratios above. An example of the latter function is the product P {d^J._vol = 0 | Y ^} and the a priori probability that d_vol^J. = 0 received from the previous component decoder.

The decoder for concurrent concatenated codes iteratively works as follows. The first component decoder 1 calculates a set of soft decision values ​​for the information bit sequence encoded by the first component encoder based on the received codeword and any a priori information about the transmitted information bits. In the first iteration, if there is no a priori information about the source statistics, it is assumed that the bits are equally probable to be 0 or 1, i.e. P {bit = 0} = P {bit = l} = l / 2 . The soft decision values ​​computed by decoder 1 are then interleaved using the same type or the same interleaver that was used in the encoder to permutate the data bit block for the second encoder. These permuted soft decision values ​​and the received codeword include the input for the next component decoder 2. The permuted soft decision values ​​received from the previous component decoder and interleaver are used by the next component decoder as a priori information about the decoded data bits. The component decoders work sequentially in this manner until the Nth decoder computes a set of output soft decisions for a block of data bits that was encoded by the encoder. The next step is to pay for the soft decision values ​​from the Nth decoder as described above. The first decoder then acts on the received codeword, again using the new soft decision values ​​from the Nth decoder as its a priori information. The decoder operates in this way for the required number of iterations.

183 537

In the final iteration, a sequence of values ​​that is a second function of the output soft decisions computed by the N-th decoder is interleaved to return the data to the order in which it was received by the PCCC encoder. The number of iterations may be a predetermined number or may be determined dynamically by detecting decoder convergence.

The decoder provides soft decision information which is a probability function P {d] = 0 | Y}}, that is the conditional probability that the jth data bit in the k-bit encoder input symbol at time t is 0, assuming that the set of inputs Y ^ = (yi, ...., y_L.) In addition, the decoder may provide hard decision information as a function of its soft decision output by a decision device that executes a decision rule such as:

dj = 0

P {dJ = 0 | dj = 1

That is, if P {d^J.t = 0 | Υ ^}> 1/2, then d^J.t = 0, if P {d^J._vol = 0 | Y]^L.} <l / 2, then d] = 1, otherwise randomly assigns d, the value 0 or 1.

The MAP decoder creates the probability that the decoded bit value is 0 or 1. On the other hand, a SOVA decoder usually computes a likelihood ratio:

P {the decoded bit is 1}

P {decoded bit is 0} for each bit decoded. This likelihood ratio is obtained from P {the decoded bit is 0} and vice versa, using P {the decoded bit is 0} = 1 - P {the decoded bit is 1}. Some computational advantages have been discovered when either the MAP decoder or the SOVA are working with the log likelihood ratios, i.e.

P {the decoded bit is 1} _λlog (--------------)

P {decoded bit is 0}

The coding gain and error correction capability achieved by the turbo codes decrease significantly as the size of the data block decreases. The RSC code distance increases as the data block length increases. Conversely, the minimum RSC distance decreases with decreasing data block length. The second problem is the difficulty of termination of all RSC codes having a turbo coding scheme related to interleaving. The disadvantageous results of not completing the sequence or introducing constraints on the interleaver design are significant and become even more so as the data block length is decreased.

In accordance with the invention, the component codes in the parallel, coupled convolutional coding scheme include non-recursive systematic convolutional codes with tail bits. The use of such tail-bit codes solves the problem of terminating the input data sequence in turbo coding, thereby preventing decoder performance degradation for short messages. Although NSC codes are usually weaker than RSC codes having the same memory, the free NSC code distance is less sensitive to the data block length. Thus, parallel combined coding with NSC codes will perform better than with RSC codes having the same memory for messages that are shorter than the predetermined threshold size of the payload. The resultant efficiency point is a function of the required decoded bit error rate, code speed, and code memory.

Figure 3 shows an example of rate = 1/2, memory = m non-recursive systematic convolutional coder with tail bits for use in a parallel, combined convolutional PCCC coding scheme according to the invention. For description, marked

183 537 encoder n, k, m and an encoder in which input symbols include k bits, output symbols include n bits and m = encoder memory in k-bit symbols. By way of illustration, Fig. 3 is derived for binary input symbols, i.e. k = 1. However, the invention is applicable to any values ​​of k, n and m.

Initially, switch 50 is in the down position and the input L bits are shifted to shift register 52 k at a time, one input symbol at a time in this example. After the L-th bit is input into the encoder, the switch moves to the up position and encoding begins as the first bit shifts from the second shift register 54 to the non-recursive systematic encoder, the encoder state at this time is {b_L., b_L..!,. . ., / b_L.. (k_m. |)} · In this example, the encoder output contains the current input bit and the parity bit created in block 56, shown as adding modulo 2 in this example, as a function of the encoder state and the current input symbol. Encoding ends when the Lth bit is encoded.

Another aspect of the invention is that the corresponding decoder for the above-described parallel combined encoder comprises a circular MAP decoder for decoding the convolutional codes with the tail bits. The circular MAP decoder provides both the coded data block estimate and reliability information to a data receiver, e.g. a speech synthesis signal processor used in transmitting the hidden error or a protocol processor for the packet data as a block error probability measure used in repeating the requested decisions.

The circular MAP decoder for error correction trellis codes that use trailing bits produces soft decision outputs. The circular MAP decoder provides an estimate of the probabilities of the states in the first trellis state, which probabilities override the a priori knowledge of the starting state in a conventional MAP decoder. The circular MAP decoder provides an initial state probability distribution in either of two ways. The first gives a solution to the eigenvalue problem, for which the obtained eigenvector is the required initial state probability distribution, with the knowledge of the starting state, the circular MAP decoder performs the remaining decoding according to the conventional MAP decoding algorithm. The second is based on recursion for which iterations converge for the initial state distribution. After sufficient iterations, the state of the cyclic sequence of states is known with high probability, and the cyclic MAP decoder performs the remaining decoding according to a conventional MAP decoding algorithm.

The purpose of the conventional MAP decoding algorithm is to find the conditional probabilities:

P {m state at time t / reception of y channel outputs_b..., y_L.}

The term L in this expression represents the length of the data block in units of the number of encoder symbols. The encoder for the (n, k) code acts on k-bit input symbols to produce n-bit output symbols. The term y_vol is the channel exit symbol at time t.

The MAP decoding algorithm actually finds the probabilities first:

X_vol(m) = P {S_vol = m; Y,^L. } / 1 / that is, the total probability that the state of the encoder at time t: S is m and the set of channel outputs is received = {y!, ..., y_L.}. These are the required probabilities, multiplied by the constant Ρ {Υ ^}, the probability of receiving the set of channel outputs {y_b ..., y_L. }).

Now let's define the elements of the matrix r_vol by_vol(i, j) = P {state j at time t; y_vol/ state and time t-1}

The matrix T_vol is computed as a function of the transition probability R (Y_vol, X), probabilities p_vol (m / m ') that the encoder will transition from state m' wm at time t and probability q_vol(X / m ', m) that the encoder output symbol is X, assuming that

183 537, the previous encoder state is m 'and the current encoder state is m. In particular, each element of T_volis computed by summing all possible encoder X outputs as follows:

Pt (m / m ') q_vol (X / m ', m) R (Y_vol, X) ^/2/

X

The MAP decoder computes L of these matrices, one for each trellis stage. They are made up of the received channel output symbols and the trellis branch properties for a given code.

Then let us define the elements of the total probability M of a vector of the order by

Ot (j) = P {state j at time t; yi, ..., y_vol} / 3 / i elements of the conditional probability M of the column vector βι by βι 0)^{= p} {Yt + 1, · ·., Υι / j state at time t} / 4 / for j = 0, 1, .... (M1), where M is the number of encoder states. Matrices and vectors are denoted here using bold font.

The steps of the MAP decoding algorithm are as follows:

/ i / Compute ai, ..., at by forward recursion:

at = at-i r_vol, t = l, ..., L / 5 / / ii / Calculating βι,.,., βΕ-ι by backward recursion:

Pt = T_{t + 1} Fri.₊i, t = Ll, ..., 1/6 / / iii / Computing the elements Xt by:

Xt (i) = oą (i) βι (i), all i, t = l, ..., L / 7 / / iv / Finding the appropriate quantities as required. For example, let A] be the state complex of S._vol = (8 /, S._vol², ..., St ^ / so that the jth element St, S (is equal to zero. For a conventional non-recursive trellis code, S (= d ^J.t, the jth data bit at time t. Thus, the decoder soft decision output is ^{p (d}’ = ^{01 Y}'^l> = X Σ W where P {Y,^L.} = £ X_L.(m) and m is the index that corresponds to state S._vol.

A hard decision decoder or bit decoder output is obtained by inputting P {d (= 01 Yi^L.} to the following decision rule:

d (= 0 = 0 | Y,^L.} * 1 < = 1

That is, if P {d³ = 01 Yi^L.}> 1/2, then d (- 0; if P {d (= 0 | Yi^L.} <1/2, then dj = 1, otherwise randomly assigns d (value 0 or 1.

As another size example for step / iv /, above. probability matrix a_vol includes the elements defined as follows:

about_vol(and_with j) = P {S_vol_! = i; St = j; Y /} = a_vol-i (i) y_vol (i, j) β, (j)

These probabilities are useful when it is desired to determine the posterior probabilities for the encoder output bits.

In a standard application of the MAP decoding algorithm, forward recursion is initiated with the vector ao = (1,0, ... 0) and backward recursion is initiated with. β, = (1, 0, ... 0)^T.. These initial conditions are based on the assumption that the initial state of the encoder S_about= 0 and end state S_L.=0.

183 537

One embodiment of the circular MAP decoder determines the initial state probability distribution by solving the eigenvalue problem as follows. Let oa, Pt> F_voland Xt will be as before, but let's take the initial do and as follows:

Let us introduce the βιάο of the column vector (111 ... 1)^T..

Let ao be an unknown variable / vector /.

Then / i / Calculation of T_vol for t = 1, 2, ... L according to the equation / 2 /.

/ ii / Finding the greatest eigenvalue for the matrix product Fj Γ₂... Γε. Normalizing the corresponding eigenvector so that its components add up to unity. This vector is a solution to ao. The eigenvalue is P {Yi^L.}.

/ iii / Create another a_vol by forward recursion presented in the equation / 5 /.

/ iv / Beginning with Pl, beginning as above, with p_vol by backward recursion presented in equation / 6 /.

NI Creation of Xt as in / 7 /, as well as other required variables, such as for example soft decision output P {(Pt = 0 | Yi^L.} or a probability matrix a_vol described above.

The unknown variable satisfies the matrix equation a₀ P {Y,^L.}

From the fact that this equation expresses the relationship between the probabilities, we conclude that the product of the matrix r_vol to the right has the largest eigenvalue P {Yi} and that the eigenvector must be a probability vector.

At the initial Pl ^ I 11 ... 1)^T., the equation / 6 / gives Pl-i. Thus, repeated applications of this backward recursion yield all Pt. After getting to know Cą and establishing Mr._L., all calculations in the circular MAP decoder according to the invention follow the conventional MAP decoding algorithm.

Figure 4 is a simplified block diagram illustrating a circular MAP decoder 110 for decoding the trellis code with error correction tail bits according to the eigenvector method described above. The decoder 110 includes an r counter_vol 112, which is calculated by T._vol in the function of output y_vol channel. Counting system_vol receives input from memory 130: probability R (Y_vol, X) channel transition, probability p_vol(m / m ') that the encoder transitions from state m' wm at time t and probability q_vol(X / m ', m) that the encoder output symbol is X, assuming the previous encoder state is m' and the current encoder state is m._vol computes each element r_vol by summing all possible encoder outputs X according to equation / 2 /.

Calculated values ​​of F_vol are provided to a numerator 114, a matrix product to form a matrix product ΓιΓ₂ ... T1 using the identity matrix 116, e.g., received from memory, switch 118, and delay circuit 120. At time t = 1, the identity matrix is ​​provided as one input to the matrix product calculator.

t —1

At each successive time from t = 2 to t = L, the matrix product pj is fed 1 = 1 back through the delay circuit to the matrix product system. Then, at time t = L, the resulting matrix product is supplied by a switch 121 to a standard eigenvector calculator 122 which computes the standard eigenvector corresponding to the largest eigenvalue of the matrix product fed thereto. With ao so initialized, i.e. as this standard eigenvector, successive vectors aa are recursively determined according to the equation / 5 / in a matrix product numerator 124 using lag 126 and a switch 128 as shown. The correct values ​​for r_vol are retrieved from memory 130 and the obtained are then stored in memory 130.

183 537

The values ​​of βι are determined in a matrix product counting circuit 132 using a switch 134 and a delay circuit 136 according to the equation / 6 /. Then the probabilities Xt from the value of a are computed_vol ip_vol in a system with 140 the product of an element by an element according to the equation / 7 /. The values ​​are provided to a probability calculator 150 of the decoded bit value which determines the probability that the jth decoded bit at time t: d_vol^J. is zero. This probability is provided to a threshold decision device 152 which executes the following decision rule: If the probability of the numerator 150 is greater than 1/2 then it decides that the decoded bit is zero, and if the probability is less than 1/2 then it decides that the decoded bit is one, whereas if it is 1/2, then the decoded bit is randomly assigned the value 0 or 1. The output of the threshold decision device is the decoder output bit at time t.

Probability that the decoded bit is zero P {d_vol^J. = 0 | Y_vol^J.}, is also shown in FIG. 4 as being provided to soft output function block 154 to provide a probability function, i.e., f (P {d_vol^j = 01Y?}) So that for example. . 1 - P {d ^ - 0 | Y⁷} likelihood ratio = ------_:------------ pK = o | y⁷} as soft-decision decoder output. Another useful function of P {d_vol^J. = 0 | Y_vol^J.} is the log of the likelihood ratio = log

- P {d / = 0 | Y?}

P {dt = 0 | Y '}¹

Alternatively, a useful function for block 154 may simply be an identity function such that 'the soft output is simply P {d_vol^J. = 01 Y_vol^j}.

In an alternate embodiment, the circular MAP decoder determines the state probability distributions by recursion. In particular, in the dynamic convergence method, the recursion continues until decoder convergence is detected. In this recursion or dynamic convergence method, steps / ii / and / iii / of the above-described eigenvector methods are replaced as follows:

/ ii. a / Starting at initial (to equal to (1 / M, ..., 1 / M), where M is the number of lattice states, compute forward recursion L times. Normalize the results so that the elements of each new a_vol add up to unity. Finding all the vectors of L a_vol /ii.b/ Let oa be equal to a_L. from the previous step and starting at t = l, recomputing the first probability vectors Lw_min oh.

Ml

That is, it computes a_vol(m) = Y Ot-i (i) Y_vol(i, m) dlam = 0, l, ..., Ml and t = l, 2, ..., Lw. . where i = 0 ^¹¹

L._{in min} is the actual minimum number of trellis steps. It normalizes as before. Only the last complex of L a found by recursion in steps /ii.a/ and /ii.b/ and aLw is determined_min found previously in step /ii.a/.

/ii.c/ Comparing aLw_min from stage /ii.b/ with the previously found ensemble from stage /ii.a/. If the corresponding elements of the new and old M a_LWmin are within tolerance go to step / iv / above. Otherwise, go to the /ii.d/ stage.

/ii.d/ Let t = t + l and compute at = at-iF_vol. Normalizing as before. Determining only the last computed ensemble Lai oa found previously in step /ii.a/.

/ ii. e / Compare new ts with a previously found ensemble. If the new and old M are within tolerance, go to step / iv /. otherwise going to step /ii.d/ if the last two vectors are not within the tolerance and if the number of recursions does not exceed a particular maximum, typically 2L, otherwise going to step / iv /.

183 537

This method then performs steps / iv / and / v / given above with respect to the eigenvector method to produce the soft decision outputs and the decoded output bits of the circular MAP decoder.

The above-described recursion method is modified such that the decoder only needs to process a predetermined, predetermined number of trellis degrees for the second time, i.e., a predetermined winding depth. This is advantageous for achieving the set goals, since the number of computations required for decoding is the same for each encoded message block. As a result, the complexity of the hardware and software is reduced.

One way to judge the required winding depth for MAP decoding of a convolutional tail bit code is to determine it by experimentation with hardware or software, requiring that a circular MAP decoder with variable winding depth be realized and experiments performed to measure the decoded bit error rate as a function of Eb. / N₀ for successively increasing winding depths. Minimum decoder winding depth that provides the minimum probability of decoded bit error for a particular Eb / N₀, is found when further increases in the winding depth do not increase the error probability.

If a decoded bit error rate is tolerated that is greater than the minimum achievable with a particular Et> / N₀, it is possible to reduce the required number of trellis steps processed by the circular MAP decoder. In particular, the search for the winding depth described above can be simply ended when the required average probability of bit error is obtained.

Another way to specify the winding depth for a given code is to use the code's distance properties. For this, it 's necessary to define two distinct decoder decision depths. The term valid path as used herein refers to a sequence of states or a path traversing a trellis that results from the encoding of a block of data bits. The term invalid subassembly of a node refers to the assembly of all invalid branches except the node of the valid track and their derivatives. Both the decision depths defined below depend on the convolutional encoder.

The decision depths are defined as follows:

/ i / Specify the forward decision depth for error correction e: LF (e) as the first truss depth at which all tracks in the invalid sub-assembly of the starting node of the correct track, whether or not they later join the correct track, lie further than the Hamming distance 2e from the correct track. The meaning of LF (e) is that if there are e or fewer errors ahead of the starting node and it is known that encoding has to start there, then the decoder must decode correctly.

/ ii / Then specify the uncoupled decision depth for error correction LU (e) as the first truss depth at which all grate tracks never touching the correct track lie further than Hamming distance 2e from the correct track.

The significance of LU (e) for the circular soft decision MAP decoding is that the probability of identifying the state in the current transmission path is high after the decoder has processed the LU (e) trellis steps. Thus, the minimum winding depth for circular MAP decoding is LU (e). Calculations of the depth LU (e) show that it is always greater than LF (e) but uses the same approximation law. This implies that the minimum winding depth can be judged as a forward decision depth LF (e) if the uncoupled code decision depth is not known.

By finding the minimum uncoupled decision depth for a given encoder, we find the smallest number of trellis steps that need to be processed by a practical circular decoder producing soft decision outputs. For finding LU (e):

/ i / Extend the code trellis from left to right starting at all trellis nodes simultaneously, except state zero.

/ ii / At each level, remove all tracks that connect to a valid all-zero track, do not extend any track beyond the valid zero-state node.

183 537 / iii / At level k, find the smallest Hamming distance or weight between tracks ending at nodes at this level.

/ iv / If the shortest distance exceeds 2e, stop. Then LU (e) = k.

Experiments with computer simulation lead to two unexpected results: / 1 / winding β processing_ι improves decoder performance; and / 2 / the use of a winding depth LU (e) + LF (e) = 2LF (e) improves the performance significantly. Thus, a preferred implementation of the recursion-based circular MAP decoder algorithm comprises the following steps:

/ i / Calculation of T_vol for t = 1, 2, ... L according to the equation / 2 /.

/ ii / Starting with initial cio equal to (1 / M, ..., 1 / M), where M is the number of states in the trellis, computing forward recursion from the equation / 5 / (L + Lw) times for u = l, 2. . . (L + Lw), where L._in is the decoder winding depth. The trellis level index t takes the values ​​((ul) mod L) + l. When the decoder winds around the received symbol sequence from the channel, a_L. is treated as Oo · The results are normalized such that the elements of each new a_voladd up to unity. The last L vectors found by this recursion are left behind.

/ iii / Starting with initial βΕ equal to (1, .. ,, 1)^T. computing backward recursion from the equation / 6 / (L + Lw) times for u = 1,2, ... (L + Lw). The trellis level index t takes the values ​​L- (u mod L). The decoder then wraps around the received sequence, βι is used as βΕ + ι and Γι is used as r_L.+ i, when computing the new β_Ε. The results are normalized so that the elements of each new β] add up to one. L is re-established for the last β vectors found by this recursion.

The next step of this preferred recursion method is the same as step / v / shown above with respect to the eigenvector method for producing soft decisions and output decoded bits through a circular MAP decoder.

Figure 5 is a simplified block diagram illustrating a circular MAP decoder 180 according to a preferred embodiment of the invention. The decoder 180 includes an r counter_vol 182, which calculates the r_vol as a function of y channel output_vol. The outputs of the channel yi, ..., yt are supplied to the calculator r_vol by switch 184. With the switch in the down position, the output symbols of the L channel are input into the F calculator_vol 182 and shift register 186 once in a given time. The switch 184 is then moved to the up position to allow the shift register to shift the first received symbols Lw back into the r calculator._volThis is for circular processing. T counting system_vol it receives as inputs from memory 130 the probability R (Y_vol, X) channel transition, probability p_vol(m / m ') that the encoder transitions from state m' to m at time t and probability gtX / m ', m) that the encoder output symbol is X, assuming the previous encoder state is m' and the current encoder state is m Counting circuit F_vol computes each F element_vol by summing all possible encoder outputs X according to equation / 2 /.

Calculated values ​​of T_vol is provided to a counting system 190 a matrix product that multiplies the matrix T_vol by a matrix recursively supplied by delay 192 and demultiplexer 194. Control signal CNTRL1 causes demultiplexer 194 to select 0 from memory 196 as one input for matrix product calculator 190 when t = 1. When 2 & lt; t & lt; L, control signal CNTRL1 causes demultiplexer 194 to select from delay circuit 192 as one input to matrix calculator 190. The values ​​of T_vol and cą are stored in memory 196 as required.

The βί vectors are recursively computed over a matrix product of 200 through delay 202 and demultiplexer 204. The control signal CNTRL2 causes the demultiplexer 204 to select βΕ from memory 196 as one input to the matrix product 200 when t = L1. When L-2> t> 1, the CNTRL2 control signal causes the demultiplexer 204 to select β_{ί +}ι from delay 102 as one input to the 200 matrix product. The obtained values ​​of βι are multiplied by the values ​​of cq obtained from the memory 196 in a system counting 206 the product of the element by the element to provide the probabilities Xt as described above. In the same way as described above with reference to Fig. 4, the values ​​of Xt are provided to the counting system 150 possibly

183 537 the value of the decoded bits, the output of which is fed to a threshold decision device 152, triggering the decoded output bits of the decoder. . .

The conditional probability that the decoded bit is zero, (P {d_vol^J. = 0 | Yt^J.}) is also shown in FIG. 5 as being provided to soft output function block 154 to provide a probability function, i.e. f (P {d / = 0 | Yt^J.}) so that, for example. ,. 1 - P {dJ = 0 | Y⁷} and likelihood index = ~ - _{Q |} as the decoder soft decision output. Another useful function of P {d_vol^J. = 0 | Y_vol^J.} is the log of the likelihood ratio =

J 1 - p_id; = o | ΐ;}

Pio; = 0 | Y '}

Alternatively, a useful function for block 154 may simply be an identity function such that the soft output is just (P {d_vol^J. = 0 | Y_vol^J.}).

According to the invention, it is possible to increase the speed of a parallel combined coding scheme including non-recursive systematic codes with trailing bits by deleting selected bits in the composite codeword formed by the composite codeword according to a preferably selected pattern before transmitting the composite codeword bits on the channel. This technique is known as piercing. This piercing pattern is also known by the decoder. The following simple additional step performed by the received composite codeword to component codeword converter provides the required decoder operation: the received composite codeword to component codeword converter simply inputs a zero value for each known punch bit when forming the received component codewords. For example, a value of zero is in the case of diametrically opposed signaling on a channel of additional Gaussian white noise. The rest of the decoder operation is described above.

The minimum NSC code distance is less sensitive to the length of the payload and thus can be advantageously used in communication systems that transmit short blocks of data on high noise channels. The use of codes with trailing bits solves the problem of terminating the input data sequence in turbo codes. The invention provides a parallel, coupled, non-recursive, systematic, tail-bit convolutional encoding scheme with a decoder including circular MAP decoders for decoding component convolutional codes with tail bits to provide better performance at small data block lengths than conventional turbo coding schemes for measuring speed. bit error versus signal-to-noise ratio.

183 537

DOWNLOAD COMPLEX WORD KOOU

CHANNEL

COMPOSITE WORD CODE 00 TRANSMITTER COMPLEX WORD KOOU

OEKOOER 1

OEKOOER 2

OEKOOER N 1 * OEKOOER N

LAYOUT OF INTERLACING 1

THE LAYOUT OF INTERIORS

THE LAYOUT OF INTERIORS

N-1

PAYMENT ARRANGEMENT

<img file="PL183537B1_D0001.tif" />

LAYOUT -.

PAYMENTS 29

PAYMENT ARRANGEMENT

N-1

N-2 PAYMENT SYSTEM

8L0K \ DECODING. INFORMATION \ _

PAYMENT ARRANGEMENT 1

183 537

<img file="PL183537B1_D0002.tif" />

FIG. 3

183 537

Pf (m | m)

<img file="PL183537B1_D0003.tif" />

183 537 &lt;5 - a

<img file="PL183537B1_D0004.tif" />

About a: a.

183 537

DATA BIT BLOCK

<img file="PL183537B1_D0005.tif" />

COMBINED WORD CODE GO CHANNEL

FIG.1

Publishing Department of the UP RP. Mintage 60 copies. Price PLN 4.00.