Parallel, combined splice code with end bited and decoder therefor

The subject of the invention is a method for coding parallel, combined convolutional codes and an encoder for encoding parallel, combined convolutional codes, generally used in the correction error correction coding for transmission of short messages in weak channels, especially in the technique of parallel, combined convolutional code with end bits and its decoder.

A parallel, combined coding method, known as either parallel, PCCC convolutional convolutional coding or turbo coding, is known to be associated with impressionistic, demonstrated coding enhancements when delivering 10,000 or more bits to blocks, as illustrated, for example, in C. Berrou, A. Glavieux and P. Thitima183 239 jshima titled "Error correction coding and decoding near the Shannon boundary: turbocodes" Proceedings of the IEEE International Conference Communications, 1993, pages 1064-1070, in JD Andersen's publication entitled "Turbocoding scheme", report IT-146 ISSN 0105- 854, Institute of Telecommunication, Technical University of Denmark, December 1994 and in publication P. Robertson, titled "Illuminating Code Structure and Decoder for Parallel, Connected, Recursive Systematic Turbocodes", 1994, IEEE Globecom Conference, pages 1298-1303.

The implementation of turbocode generally deteriorates as the length of the encoded data block decreases. This phenomenon is associated with the strong dependence of its component weighting structures on 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. Mayra titled "Completion of turbocode gratings", IEE Electronics Letters, vol. 30, no. 16.4 August 1994, pages 1285-1286 shows that interleaving used in turbocoders can prevent the termination of both interlaced and non-interlaced encoder input sequences by a single set of end bits. Although it is possible to use a second end sequence located in the message structure so that the encoder working on the interlaced data sequence is properly terminated, it doubles the preliminary operations associated with the end of the encoder and reduces the effective code transfer rate. An alternative is not to finish one of the coder sequences, but this degrades the codec system performance, especially when using short messages. In the publication AS Barbulescu and SS Pietrobon entitled "Completion of turbocode gratings in the same condition", IEE Electronics Letters, 1995, volume 31, No. 1, January 5, pages 22-23, a method is presented that imposes restrictions on the design of the interleaving system to complete the work two-component, recursive, systematic convolutional encoders by a single sequence of termination bits. Their performance results show some deterioration compared to the performance achieved by the termination of both encoders when optimal interleaving is used. In addition, published error rate data in bits as a function of the energy ratio per bit to spectral noise power density Et / N₀ show smoothing of the error rate in bits within the range of E (/ N_aboutwhen RSC codes are used in the turbocoder.

Known turbodecoders use either "maximum a posteriori" MAP decoders, such as those described in LR Bahia, J. Cocke, F. Jelinka and J. Raviva, in the publication "Optimal decoding of linear codes 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 the publication by J. Hagenauer and P. Hoehera, under the title, Viterbi Algorithm with soft decision outputs and its applications ”, 1989 IEEE Globecom Conference, pages 1680-1686.

Formal tab depth of forward decision LF (e) for convolutional codes is presented in the publication of JB Anderson and K. Balachandran titled "Depth of convolutional code decisions", IEEE Transactions on Information Theory, volume IT-35, pages 455-59, March 1989 Many of the properties of LF (e) are disclosed in this publication, as well as in the publication of JB Anderson and S. Mohan under the title "Source and channel coding - algorithmic approximation", Kluwer Academic Publisher, Norwell, MA, 1991. The basic property is that there is a simple linear relationship between LF and e, e.g. for 1/2 rate codes, LF is approximately 9.08e. The algorithm for finding the depth of decision forward LF (e) is also presented in the publication of JB Anderson and K. Balachandran under the title "Depth decision convolutional codes".

It is known that non-recursive, systematic convolutional codes would not be useful as component codes in a parallel, combined coding scheme due to the long distances of RSC codes for relatively large data block lengths, as presented in the publication of S. Benededetto and G. Montorsi under the title "Parallel Design , linked convolutional codes, "IEEE Transactions on Communications.

183 239

The method of the invention consists in providing a block of data bits to a parallel, connected encoder comprising a plurality of N component encoders and N-1 interleavers combined in a parallel system. The data bit block is encoded in the first of the component encoders by supplying it with a non-recursive, systematic convolutional code with the end bits and thereby produces the first component code word containing data bits and parity bits. A data bit block is interleaved to provide a permuted data bit block. The resulting permutated data bit block is encoded in the next component encoder by supplying it with non-recursive, systematic convolutional code with end bits, and thus a second, component code word containing data bits and parity bits is generated. The interleaving and coding of the obtained, permuted block of data bits by the remaining N-2 interleaving circuits and the remaining N-2 component encoders, and as a result, code word components containing data bits and parity bits are generated, and the bits of component word words are formatted for composite delivery code words.

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

Preferably, the formatting is performed such that the composite code word contains only selected from the bits containing the code word components in accordance with a predefined pattern.

The encoder according to the invention is adapted to systematically provide non-recursive, systematic convolutional codes with end bits to a data bit block and various permutations of a data bit block, and to produce code word components, including data bits and parity bits, and a formatter for a composite code word for formatting a set of bits from word components code and providing a composite code word.

Preferably, the composite codeword formatter is adapted to produce a composite codeword so that it includes only one appearance of each bit in a data bit block.

Preferably, the composite code word is a composite code word comprising only selected from bits having component code words according to a predefined pattern.

An advantage of the invention is to provide an improved technique of parallel, combined coding for short data blocks. In the method and arrangement of the invention, the parallel linked convolutional encoding scheme uses non-recursive, systematic NSC convolutional codes with end bits. The decoder iteratively uses maximum a posteriori cyclic decoding to produce hard and soft decision outputs. The use of end-bit codes solves the problem of terminating input data sequences in turbo coding, thereby preventing decoder performance for short messages. While NSC codes are usually weaker than recursive, systematic RSC convolutional codes having the same memory asymptotically, as the data block length increases, any distance of the NSC code is less sensitive to the length of the data block. Thus, parallel, combined coding with NSC codes will be better implemented than with RSC codes having the same memory for messages that are shorter than a certain threshold size of a data block.

The subject of the invention is illustrated in the embodiments in the drawing, in which Fig. 1 is a simplified diagram showing a parallel, connected encoder, Fig. 2 is a simplified diagram showing a decoder for parallel, connected codes, and Fig. 3 is a simplified diagram showing a non-recursive, systematic convolutional encoder with bits terminal for use in the coding scheme of the invention, Fig. 4 - a simplified scheme showing a MAP cyclic decoder, used as a component decoder in a decoder for a parallel, combined convolutional encoding scheme according to the invention and Fig. 5 a simplified scheme showing a different embodiment of a cyclic MAP decoder used as a component decoder for a parallel, combined convolutional encoding scheme according to the invention.

Figure 1 shows an overall block diagram of an encoder signal processing system 10 for parallel, combined coding schemes. It contains many N components, code 183 239, ditch 12, which affect the data bit blocks from the source. Data blocks are permutated by interleaving algorithms through interleavers 14. There are Nl interleavers for N encoders 12. Finally, the component encoder outputs are combined into a single, compound code word through the formatter 16 of the composite code word. The formatter 16 of the compound code word is selected to match the characteristics of the channel, followed by a frame formatter selected to match the channel and channel access techniques of the communication system. The frame formatter can also enter other necessary pre-operations, such as control bits and synchronization symbols.

Significant improvements in code transfer speed can be obtained in parallel connected coding if the component codes are systematic codes. The output code words produced by the systematic encoder contain the original data bits provided as input to the encoder and the additional parity bits. The redundancy introduced by the parity bits gives the ability to correct code errors. Thus, when systematic encoders are used in the parallel connected encoder shown in Fig. 1, the code words produced by all component encoders 12 contain input data bits. If the formatter 16 creates a data packet or composite code word containing only the parity bits generated by each component encoder 12 and a block of coded information bits, a substantial improvement in the transfer rate of the composite, parallel, combined code is accomplished by eliminating the repetition of information bits in the transmitted complex code word. For example, if component coder 1 and component coder 2 of a parallel, combined PCCC convolutional code containing two component codes are both 1/2 speed codes, the transfer rate of the composite, parallel, combined code is increased from 1/4 for unsystematic component codes up to 1/3 for systematic member codes.

Parallel, combined coding schemes that use recursive, systematic RSC convolutional codes have been the last topic of much research. These parallel, connected PCCC convolutional codes are also commonly known in the literature as turbocodes. PCCC convolutional codes can achieve impressive performance in error rate expressions in bits as a function of energy ratio per bit to spectral noise power density E_b/ N_about for relatively large messages, it is ten thousand or more bits. However, it has also been shown that the coding gain obtained by turbocodes decreases significantly as the data block size decreases, because 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 non-recursive, systematic convolutional code with end bits is independent of the length of the data block for most practical purposes, and the performance obtained decreases only when the block of encoded data bits is smaller than the minimum dimension, which is determined by the degree of NSC decision.

Figure 2 shows the general decoder 20 for parallel, combined codes in the form of a block diagram. Decoder 20 includes a converter 22 of a composite code word into a component code word that converts the composite code word received from the channel into individually received code words for each component decoder 24, with the N component decoders 24 corresponding to the N component coders of Fig. 1 of the same type or the same interleaving systems 14 that are used in the parallel connected encoder of Fig. 1 and the first and second payoffs 28 and 29, each of which has the property of reordering the sequence which is equivalent to the serial combination of Nl payoffs corresponding to Nl interleaving systems used for coding. The required ordering of these payout systems is shown in Fig. 2 and is the reverse of the ordering of interleaving systems. At the outputs of the decoder components 24 there is some type of soft decision information about the estimated value of each data bit in the received code words. For example, the output of decoder components may be the first probability function that the decoded bits have a value of 0 or 1 in the received symbol sequence for the channel. One example of such a first function removes the effect of conditional probability P {dJ = 0 | YJ} from the soft decision output of a component decoder, which is introduced into the next, sequential, component decoder after

183 239 proper permutation, where P {d_t^j = 0 | Y_t^j} is the probability that the jth bit information at time t is 0 the jth systematic bit of the received output symbol Yt of the channel. Alternatively, the soft decision information at the output of the component decoders 24 may be a function of the likelihood ratio., J.₌ P {d,^JL = | Y^L} l-Pld, '= ο | γ /}' p {d, '= 0 | Y,^L} P {d,^J = O ^^L} or as a function of the likelihood ratio log [A (d_t^J) J.

The Nth component decoder has a second output, that is, the second function of conditional probabilities for the values ​​of the decoded bits or the above likelihood ratios. An example of the second function is the product P {dJ = 0 | Y,^L} and a priori probability that d_f'= 0 received from the previous component decoder.

The decoder for parallel, connected codes works iteratively in the following way. The first component decoder 1 calculates a set of soft decision values ​​for a sequence of information bits encoded by the first component encoder based on the received code word and any a priori information about 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 likely to be 0 or 1, i.e. P {bit = 0} = P (bit = 1} = 1/2 Soft decision values ​​calculated by decoder 1 are then interleaved using the same type or interleaving system that was used in the encoder to permutate the data bit block for the second encoder. These permuted soft decision values ​​and the received code word contain input data for the next component decoder 2. The permuted soft decision values ​​received from the previous component decoder and the interleaver are used by the next component decoder as a priori information about the decoded data bits. The component decoders work in this manner until the Nth decoder calculates the set of soft output decisions for the data bit block that was encoded by the encoder. The next step is to pay back the value of soft decisions from the Nth decoder, as described above. The first decoder then works on the received code word, again using the new soft decision values ​​from the Nth decoder as its prior information. The decoder works in this way for the required number of iterations. As a result of the final iteration, the sequence of values, which are the second function of the output soft decisions, calculated by the Nth decoder, is interleaved to return the data to the order in which it was received by the PCCC encoder. The number of iterations can be a predetermined number or it can be determined dynamically by decoder convergence detection.

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

dtj = 0>

P {dt = 0 | Y, L} 1 <

dt^J = 1

This is if P {dj = 0 | Yj> 1/2, then dJ = 0, if P {dtJ = 0 | Y, L} <1/2, then dj = 1, otherwise randomly assigns dJ the value 0 or 1.

183 239

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

P {decoded bit is 1}

P {decoded bit is 0} for each decoded bit. This likelihood ratio is obtained from P {decoded bit is 0} and vice versa, using P {decoded bit is 0} = 1 - P {decoded bit is 1}. Some computational benefits were found when either the MAP decoder or SOVA works with a logarithm of the likelihood ratio, i.e.

Ug ⁽

P {decoded bit is 11 P {decoded bit is 0}

The coding gain and error correction capability achieved by the turbo codes decrease significantly as the data block size decreases. The distance of the RSC code increases as the length of the data block increases. On the contrary, the minimum distance of the RSC code decreases as the length of the data block decreases. The second problem is the difficulty in terminating all RSC codes having a turbo coding scheme related to interleaving. Unfavorably different results due to the lack of sequence termination or the introduction of constraints on the interleaver design are significant and become even more as the length of the data block decreases.

According to the invention, the component codes in the parallel, combined convolutional encoding scheme contain non-recursive, systematic convolutional codes with end bits. The use of such codes with end bits solves the problem of termination of the input data sequence in turbo coding, which prevents deterioration of the decoder performance for short messages. Although NSC codes are usually weaker than RSC codes having the same memory, the free distance of the NSC code is less sensitive to the length of the data block. Thus, parallel, combined coding with NSC codes will work better than with codes having the same memory for messages that are shorter than the predefined threshold size of the data block. The resultant performance point is a function of the required decoded bit error rate, code speed and code memory.

Figure 3 shows an example of speed = 1/2, memory = m non-recursive, systematic convolutional encoder with end bits for use in a parallel, combined PCCC convolutional encoding according to the invention. For the purpose of description, the encoder n, k, m and encoder is marked, in which the input symbols contain bits, the output symbols contain n bits and m = the encoder memory in k-bit symbols. For illustration, Fig. 3 is derived for binary input symbols, that is, k = 1. However, the invention is applicable to any k, n and m values.

Initially, the switch 50 is in the down position and the input bits L are shifted to shift register 52, k at a given time, one input symbol at a given time in this example. After entering the L-bit into the encoder, the switch moves to the upper position and the coding begins with the shift of the first bit from the second shift register 54 to the non-recursive, systematic encoder, and the state of the encoder at this time is ... b ^ L- ( km-1)}. 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. The encoding ends when the L-bit is encoded.

Another aspect of the invention is that the respective decoder for the above-described parallel connected encoder includes a cyclic MAP decoder for decoding convolutional codes with end bits. The cyclic MAP decoder provides both coded evaluation

183 239 a block of data as well as reliability information to a data receiver, e.g., a speech synthesis signal processor used in sending a latent error, or a data processor packet as a measure of the probability of a block error, used to repeat the desired decisions.

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

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

P {state m during t / receive y channel outputs_l5..., 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 works on k-bit input symbols to produce n-bit output symbols. Term y_t is the channel exit symbol at time t.

The MAP decoding algorithm actually finds probabilities first:

kt (m) = P {St = m; Y^L} (1) that is, the total probability that the encoder state at time t: Sj is received from the set of channel outputs Y, l = (y ,, ..., yL). These are the required probabilities multiplied by the steel (P {Y, L}, the probability of receiving the channel output set {y ,, ..., yL}).

Now let's define the elements of the matrix Γ, by

Γ (i, j) = P {state j at time t; y / state and at time t-1}

Matrix_tis calculated as a function of the transition probability R (Yt, X), the probability pt (m / m ') that the encoder will make the transition from the state m' in m at time t and the probability qt (X / m ', m) that the output symbol of the encoder is X , assuming the previous state of the encoder is m. In particular, each element Γ_{ is calculated by adding all possible outputs of the X encoder as follows:

s_t (m ', m) = Σ pt (m / m' q, (Χ / m ', m) R (Y_t, X) (2) χ

The MAP decoder calculates L of these matrices, one for each step of the lattice '. They are created from the received channel output symbols and the lattice branch properties for a given code.

Next, let's determine the elements of the total probability M of the vector cq of α, Ο) = P {stanj at time t; y ,. ... ^ l) (3) and elements of conditional probability M of the vector pt of the column by

Pt (j) = P (Yt + 1, .. ·, yL / state j at time t) (4) for j = 01, .., (Μ-1), where M is the number of encoder states. Matrices and vectors are marked here using bold font.

183 239

The steps of the MAP decoding algorithm are as follows:

(i) Calculation of a_b ..., α through forward recursion:

at = α-, Γ »t = 1, ..., L (5) (ii) Calculation of β ,, ..., β-1 by backward recursion:

β »= mercury₊₁^^_1;t = L-1, ..., 1 (6) (iii) Calculation of elements X_t through:

X_t(i) = a (i) β (i), all i, t = 1, .... L (7) (iv) Finding the right quantities as required. For example, let Aj be a set of states of S_t= {S /, St.², ..., St.^km} so that the jth element S_t, Sj, is equal to zero. For conventional non-recursive lattice code, St = dj, jth data bit at time t. Thus, the decoder soft decision output is

P {d? = 0 | Y,^L) = —Η- £ X, (m)

Π^Υ1 Ls, eA_t>

where P {Yi^L} = l_L(m)

m is an index that corresponds to St.

The output of the hard decision decoder or the decoded bit is obtained by entering P {dj = 0 | Y / '} into the following decision rule:

dt = 0>

P {d,^j= 0 | Y^L} 1 <

dj = 1

This is if Pfdt = 0 | Y j^L}> 1/2, then dt = 0; if P {dj = 0 | Y,^L} <1/2, then dj = 1, otherwise randomly assigns d_t^J values ​​of 0 or 1.

As another example of the size for the above step (iv), the probability matrix η contains the elements defined as follows:

ot (i, j) = P {St-i = i; St = j; Yt} = ctt-1 <i) yt (i, j) et (j)

These probabilities are useful when determining the posterior probability for encoder output bits.

In the standard application of the MAP decoding algorithm, forward recursion is initiated by the vector (ą, = (1,0, ... 0) and reverse recursion is initiated by β, / = (1,0, ... 0) T Te the initial conditions are based on the assumption that the initial state of the encoder S_about = 0 and final state Sl = 0.

One implementation of the circular MAP decoder determines the initial state probability distribution by solving the eigenvalue problem as follows. Let α, β, Ę and λ be as before, but let's take the initial and Pl as follows:

Let's enter PL into the column vector (111 ... 1) T.

Let α0 be an unknown variable (vector).

183 239

Then (i) Calculation of Γ, for t = 1, 2, ... L according to equation (2).

(ii) Finding the largest eigenvalue for the product of the matrix Γ, Γ₂ T ..._L . Normalizing the proper eigenvector so that its components give total unity. This vector is the solution for ao. The eigenvalue is P {Yi^L}.

(iii) Creating another a by forward recursion in equation (5).

(iv) Beginning with β_Ε, beginner as above, from β, through backward recursion given in equation (6).

(v) X, as in (7), as well as other required variables, such as, for example, soft decision output P {d,^J = 0 | Y ^} or the σ probability matrix described above.

The unknown variable Oq satisfies the matrix equation

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

At the initial β_Γ. = (111 ... 1) T equation (6) gives β-. So repeated uses of this recursion backwards give all et. After learning c and determining β, all calculations in the cyclic MAP decoder of the invention follow the conventional MAP decoding algorithm.

Figure 4 is a simplified block diagram illustrating a cyclic MAP decoder 110 for decoding lattice code with error correction end bits according to the eigenvector method described above. Decoder 110 includes a counting system 112, 112, which calculates γ as a function of the channel output yt. Counting system γ, receives input data from memory 130: probability R (Y ,, X) channel passage, probability p_t (m / m ') that the encoder makes the transition from the state m' in m at time ti probability q, (X / m ', m) that the encoder output symbol is X, assuming that the previous state of the encoder is m' and the current state of the encoder is m. The counting system Γ calculates each element Γ by adding up all possible outputs of the X encoder according to equation (2).

The calculated values ​​of Γ are supplied to the system counting 114 product of the matrix to form the product of the matrix Γ β₂ ..._L using a unit matrix 116, e.g., received from memory, switch 118 and delay system 120. At t = 1, the unit matrix is ​​provided as one input to the system counting the product of the matrix. In each subsequent time from t = 2 to t = L, the product of the matrix JJ Γ_{ is brought back

1 = and through the delay system to the system that counts the product of the matrix. Then at time t = L, the obtained product of the matrix is ​​supplied by switch 121 to the counting system 122, a standard eigenvector that calculates the standard eigenvector corresponding to the largest eigenvalue of the product of the matrix fed to it. At the initialization, i.e. as this standard eigenvector, successive vectors a, are determined recursively according to equation (5) in a system having 124 the matrix product using delay system 126 and switch 128 as shown. The correct values ​​of Γ are recovered from memory 130 and obtained a, are then stored in memory 130.

The β values ​​are determined in a system having 132 product of the matrix using switch 134 and delay system 136 according to equation (6). Then the probabilities λ are calculated, from the values ​​of a, and β, in a system of 140 product of the element by the element according to equation (7). The λ values ​​are provided to a system with 150 probability decoded bit values ​​that determines the probability that the jth decoded bit at time t: dj is zero. This probability is supplied to the threshold decision device 152, which executes the following decision rule: If the probability from the system

183 239 counting 150 is greater than 1/2, then decides that the decoded bit is zero, and if the probability is less than 1/2, then decides that the decoded bit is one, while if it is equal to 1/2, then the decoded bit is 0 or 1 randomly assigned. The output from the threshold decision device is the decoder output bit at t.

The likelihood that the decoded bit is zero P {d, t = 0 Yj} is also in Fig. 4 as supplied to the soft output function block 154 for providing the probability function, i.e. f (P {dt = 0Yj} ') nal <that for an example

...... ip {d,^J = o | Y,^J[likelihood ratio = -r⁵ P {d, ^J = o | Y_t^J} as the output of the soft decision decoder. Another useful function P {dtj = 0 | Yt} is

1-P {d,^J = 0 | Y,^J} likelihood ratio log = log {-: - r -: -}.

^& p {d,^J = o | Y,^J}

Alternatively, a useful function for block 154 may simply be an identity function such that the soft output is simply P {dt - 0 | Y_t^J}.

In a different embodiment, the cyclic MAP decoder determines state probability distributions by recursion. In particular, in the dynamic convergence method, recursion continues until the decoder convergence is detected. In this method of recursion or dynamic convergence, steps (ii) and (iii) of the eigenvector method described above are replaced as follows:

(ii.a) Beginning at the initial level, equal to (1 / M, ..., 1 / M), where M is the number of lattice states, calculation of recurrence times L forward. Normalization of results so that the elements of each new α add up to unity. Determining all vectors L aj.

(ii.b) Let αθ be equal to aL from the previous stage and starting at t = 1, recalculating the first probability vectors L_Wmni C

Μ-1

That is, calculated as (^m) = Σ a- (i) Yt (i, m) for m = 0.1, ..., M-1 and t = 12, ..., L_Wnm,, i = 0 where LWmin is the correct minimum number of lattice steps. Normalized as before. Only the last set L a found by recursion in steps (ii.a) and (ii.b) and atw ^ m previously found in step (ii.a) is determined.

(ii.c) Comparison of aL_wmin from stage (ii.b) with the previously found team from stage (ii.a). If the respective elements of the new and old M ^ min are within the tolerance range, go to step (iv) above. Otherwise, go to step (ii.d).

(ii.d) Let t = t + 1 and calculate ct = a ^ Ę. Normalizing as before. Determining only the last calculated set L a and aj found previously in step (ii.a).

(ii.e) Comparing new o with previously found team. If M new and old aj is within tolerance, go to step (iv). Otherwise, the transition to stage (ii.d), if the last two vectors are not within the tolerance range, and if the number of recursions does not exceed a particular maximum, usually 2L, otherwise the transition to stage (iv).

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

The recursion method described above is modified such that the decoder only needs to process a predetermined predetermined number of lattice steps for a second time, i.e. a predetermined winding depth. This is advantageous for achieving the set goals, since the number of calculations required for decoding is the same for each coded block of messages. As a result, the complexity of computer hardware and software is reduced.

183 239

One way of assessing the required winding depth for MAP decoding of a convolutional bit code is to determine it based on experiments using computer hardware or software, requiring that a cyclic MAP decoder with variable winding depth be implemented and experiments for measuring the error rate of decoded bits as a function et / N₀ for successively increasing winding depths. A minimum decoder winding depth, which ensures the minimum error probability of decoded bits for a particular EjN0, is found when further increases, further increases in the winding depth do not increase the probability of error.

If the decoded bit error rate is tolerated, which is greater than the minimum achievable with particular E_b/ N₍,, it is possible to reduce the required number of lattice steps processed by the circular MAP decoder. In particular, the winding depth search described above can be simply completed when the required average bit error probability is obtained.

Another way to determine the winding depth for a given code is to use the code distance property. To this end, it is necessary to specify two clear decoder decision depths. The term correct path as used herein refers to a sequence of states or a path passing through a lattice that results from coding a data bit block. The term invalid node subassembly refers to the assembly of all invalid branches except the correct track node and their derivatives. Both of the decision depths specified below depend on the convolutional encoder.

Decision depths are determined as follows:

(i) Specify the forward decision depth for error correction e: LFbe) as the first lattice depth at which all tracks in the incorrect subset of the correct track start node, regardless of whether they later connect to the correct track or not, lie further than Hamming distance 2a from the correct track. The meaning of LF (e) is that if there are e or fewer forward errors of the start node and it is known that the encoding must start there, then the decoder must decode correctly.

(ii) Then specify the depth of the unconnected decision for error correction LU (e) as the first depth in the grate, at which all tracks in the grate, never coming into contact with the correct track, lie further than the distance of Hamming 2e from the correct track.

The meaning of LU (e) for cyclic MAP decoding of soft decisions is that the probability of identifying the state in the current transmission path is high after the decoder has processed the LU (e) lattice degrees. Thus, the minimum winding depth for cyclic MAP decoding is LU (e). Calculations of the depth LU (e) show that it is always greater than LF (e), but uses the same law of approximation. This means that the minimum winding depth can be assessed as the LF (e) forward decision depth if the decision depth of the unconnected code is not known.

By finding the minimum unconnected decision depth for a given encoder, we find the least number of lattice steps that must be processed by a practical cyclic decoder that produces soft decision outputs. To find LU (e):

(i) Extend the lattice code from left to right, starting from all nodes of the lattice simultaneously, except for the zero state.

(ii) At each level, remove all tracks that connect to the correct all-zero track, do not extend any of the tracks beyond the zero valid node.

(ii) At level k, find the smallest Hamming distance or weight between tracks ending at nodes at this level.

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

Experiments using computer simulation lead to two unexpected results: (1) winded processing p improves decoder performance and (2) the use of winding depth LU (e) + LF (e) = 2LF (e) significantly improves performance. Thus, the preferred execution of the MAP decoder cyclic algorithm based on recursion includes the following steps:

183 239 (i) Calculation of Ę for t = 1, 2, ... L according to equation (2).

(ii) Beginning at the initial weight, equal to (1 / M, ..., 1 / M), where M is the number of states in the lattice, calculating forward recursion from equation (5) (L + L_in) times for u = 1, 2, ... (L + L_in), where Lw is the decoder winding depth. The t-level index of the lattice adopts the values ​​((u-1) mod L) + 1. When the decoder winds around the received sequence of symbols from the channel, it is treated as (r The results are normalized so that the elements of each new a, add up to unity The last L α vectors found by this recursion are left.

(iii) Starting at the initial β_ <equal (1 ..., 1) T calculation of back recursion from equation (6) (L + L_in) times for u = 12, ... (L + Lw). The t-level index of the lattice adopts the values ​​L- (u mode L). The decoder then winds around the received sequence, β! is used as e_u and Γ, is used as r_{L + 1}, when calculating the new β_Γ. The results are normalized so that the elements of each new et add up to unity. L is again determined for the last β vectors found by this recursion.

The next step of this recommended recursion method is the same as step (v) above with respect to the eigenvector method for generating soft decisions and decoded bit output by the cyclic MAP decoder.

Figure 5 is a simplified block diagram illustrating the MAP 180 cyclic decoder according to a preferred embodiment of the invention. Decoder 180 includes a Ę 182 counting system that calculates β as a function of channel output yt. Y channel outputs_b ..., yL are supplied to the counting system Γ, via switch 184. With the switch in the down position, the symbols for channel L output are entered into the counting system T_t 182 and shift register 186 once at a given time. Then switch 184 is moved to the up position to allow the shift register to move the first received Lw symbols back to the rt counting system, i.e. to provide cyclic processing. Counting system Γ receives the probability R (Y_t, X) channel transition, probability pt (m / m ') that the encoder makes the transition from state m' to m at t and probability qt (X / m ', m) that the encoder output symbol is X, assuming that the previous state the encoder is m 'and the current state of the encoder is m. The counting system rt calculates each element rt by adding up all possible outputs of the X encoder according to equation (2).

The calculated rt values ​​are supplied to the system counting 190 the product of the matrix, which multiplies the rt matrix by the matrix a ,._: provided recursively by delay system 192 and demultiplexer 194. The control signal CNTRL1 causes the demultiplexer 194 to select from the memory 196 as one input for the system counting 190 the product of the matrix, when t = 1. When 2 <t <L, the control signal CNTRL1 causes, that demultiplexer 194 selects <a_i from delay system 192 as one input to the system of 190 matrix product. Value of_t and cq are remembered in memory 196 as required.

The βt vectors are recursively calculated in a system of 200 matrix product by delay system 202 and demultiplexer 204. The control signal CNTRL2 causes the demultiplexer 204 to select βL from memory 196 as one input to the system of 200 matrix product when t = L-1. When L-2> t> 1, the control signal CNTRL2 causes the demultiplexer 204 to select β + from delay system 102 as one input to the system counting 200 product of the matrix. The obtained values ​​of β are multiplied by the values ​​of as obtained from memory 196, in a system counting 206 the product of the element by the element for providing probabilities λ t, as described above. In the same way, as described above with reference to Fig. 4, the λ values ​​are provided to the decoding bit probability circuit 150, the output of which is fed to the threshold decision device 152, triggering the decoded decoder output bits.

The conditional probability that the decoded bit is zero, (P {d, J = 0IY /} is also shown in Fig. 5 as supplied to the soft output function block 154 for providing the probability function, i.e. f (P {dt = 0 | Y_t^J} so that for example

183 239 likelihood ratio =

P {dt¹ = Qy, ·}

P {dt^J = 0 | Y,^J} as the output of the soft decoder decision. Another useful function P {d, = 0 Ytj} is. 1-P {d, J = 0Y, 1} credibility ratio log = log {---}.

⁶ P {dt^J = 0 | Yt^J}

Alternatively, a useful function for block 154 may simply be an identity function such that the soft output is simply Γ {ά, = 0 | Y}}.

According to the invention, it is possible to increase the speed of a parallel, combined coding scheme comprising non-recursive, systematic codes with terminal bits by removing selected bits in a composite code word formed by a composite code word formatter according to a preferably selected pattern before transmitting the bits of the composite code word in a channel. This technique is known as piercing. This piercing pattern is also known by the decoder. The following simple additional step implemented by the converter of the received compound code word into the component code word provides the required decoder operation: the converter of the received compound code word into the component code word simply introduces a zero value for each known bit pierced when creating the received component code words. For example, the zero value is for the case of diametrically opposite signaling in the channel of additional white Gaussian noise. The other decoder operation is described above.

The minimum distance of the NSC code is less sensitive to the length of the data block and can therefore be used advantageously in communication systems that transmit short blocks of data bits on high-noise channels. The use of end-bit codes solves the problem of terminating the input data sequence in turbocodes. The invention provides a parallel, combined, non-recursive, systematic convolutional encoding scheme with end bits, with a decoder comprising cyclic MAP decoders for decoding component convolutional codes with end bits to provide better performance at small data block lengths than in conventional turbocoding schemes, for measuring for speed bit error as a function of the signal to noise ratio.

183 239

183 239

<img file="PL183239B1_D0001.tif" />

FIG. 2

183 239

<img file="PL183239B1_D0002.tif" />

FIG. 3

183 239

Pf (m) πΐ)

<img file="PL183239B1_D0003.tif" />

183 239 &gt;-

<img file="PL183239B1_D0004.tif" />

Jagiellonian University

about

X

CL

183 239

BLOCK BITS

<img file="PL183239B1_D0005.tif" />

FIG.1

COMPLEX

CODE WORD

CHANNEL

UP Department of Publications. Circulation of 60 copies Price PLN 4.00