Abstract:
An encoder for turbo coded trellis code modulation comprises an encoder data block for storing incoming data, and at least two recursive systematic convolutional encoders, said convolutional encoders being connected to receive data in parallel from said encoder data block. The decoder also employs a parallel implementation.

Description:
Our co-pending patent application Ser. No. 09/562,322 of even date describes how turbo code can be used to code only the least significant bit (LSB) in the constellation and thereby achieve better performance than currently used trellis-coded modulation, such as Wei code. The achievable data rate is only a couple of dB away from Shannon capacity. 
    
    
     FIELD OF INVENTION 
     This invention relates to the field of digital communications, and in particular to an encoder and decoder for use in the implementation of a turbo trellis-coded modulation scheme. 
     BACKGROUND OF THE INVENTION 
     Turbo code has attracted a lot of interest due to its larger coding gain. See for example, “Application of Turbo Codes for Discrete Multi-Tone Modulation”, Hamid R. Sadjapour, AT&amp;T Shannon Labs., 1996. Turbo code consists of two or more convolutional constituent codes separated by an interleaver acting on the input sequence of the first encoder. In a digital subscriber loop (DSL) system, Turbo code can be used to replace trellis code to get better Bit-Error Rate (BER) performance. However, when the constellation size increases, the coding gain advantage of turbo code starts to reduce. This is because the redundant bits makes the constellation size even larger. 
     SUMMARY OF THE INVENTION 
     According to the present invention there is provided encoding apparatus generating a turbo trellis code modulation signal, comprising an encoder data block for storing incoming data, and at least two recursive systematic convolutional encoders, said convolutional encoders being connected to receive data in parallel from said encoder data block. 
     The described parallel implementation structure reduces the implementation cycle for both encoder and decoder. Also, the memory (RAM) requirement for the turbo decoder can also be saved by ⅓ in the case of a three bit parallel implementation. 
     The invention also provides decoding apparatus for a turbo coded trellis code modulation signal, comprising a pair of decoders performing forward and backward iteration on an input signal, and interleaver and de-interleaver, each decoder taking at n soft bit inputs for each turbo decoder iteration, where n is an integer greater than 1. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention will now be described in more detail, by way of example only, with reference to the accompanying drawings, in which: 
     FIG. 1 is a block diagram of an encoder for turbo trellis code modulation; 
     FIG. 2 is a block diagram of a parallel implementation of the encoder; 
     FIG. 3 shows a typical RSC encoder; 
     FIG. 3 b  shows a parallel RSC encoder in accordance with the principles of the invention; 
     FIG. 4 is a block diagram of a parallel turbo decoder; 
     FIG. 5 illustrates the operation of the decoder; 
     FIG. 6 illustrates the implementation of the forward iteration; 
     FIG. 7 shows a detail of FIG. 6; and 
     FIG. 8 illustrates the implementation of backward iteration. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Parallel Encoder 
     The general constellation encoder structure for a turbo trellis-coded modulation scheme is shown in FIG. 1 for cases x&gt;1 and y&gt;1. The input binary word u=(u z′ , u z′−1 , . . . , u 1 ) determines two binary words v=(v z′−y , . . . , v 0 ) and w=(w y−1 , . . . , w 0 ) (where z′=x+y−1), which are used to look up two constellation points in an encoder table. 
     Encoder data block  10  receives a portion of the data from an input bit stream and stores it in memory. The lowest order bits are read out of encoder data block and passed to recursive systematic convolutional encoders RSC 1  and RSC 2 . 
     The turbo encoder formed by block  20  is a systematic encoder with coding rate ¾ punctured at rate ½. The turbo encoder consists of two recursive systematic convolutional encoders, RSC 1  and RSC 2 . The RSC 1  takes sequential data from the encoder data block and RSC 2  takes interleaved data from the same data block. In this structure, three implementation cycles are required to get a single constellation point, which is mainly due to the implementation requirement of the turbo encoder. 
     To speed up the process, a parallel encoder structure is presented in FIG.  2 . The difference over FIG. 1 is that both RSC 1  and RSC 2  take three input data simultaneously and create one error check bit in a single implementation cycle. 
     A comparison between a normal RSC encoder and a parallel RSC encoder is shown in FIG. 3, where FIG.  3 ( a ) is a normal 8 state RSC encoder and FIG.  3 ( b ) shows a parallel implementation. The parallel encoder takes only one implementation cycle for every three input bits. Although FIG.  3 ( b ) shows the same encoder as FIG.  3 ( a ), it is not necessary that the parallel encoder be derived from a normal RSC encoder. 
     Parallel Turbo Decoder 
     The decoding procedure for turbo trellis-coded modulation consists of following steps: 
     1. Soft decode for the least significant bit (LSB); 
     2. Hard decoder for the most significant bits (MSB). 
     3. Decode the LSB using turbo decoder algorithm 
     4. Determine all data bits. 
     In order to decode the LSB (third step), the parallel turbo decoder takes three soft-bit inputs for each forward (α) and backward (β) iteration. In this way, only ⅓ cycles are used for each turbo decoder iteration and the memory requirements for storing α and β values are also reduced by a factor of three. 
     The parallel turbo decoder is shown in FIG.  4 . It consists of two decoders  40 ,  42 , and an interleaver  41 , and de-interleaver  43 . 
     FIG. 5 shows a detail of decoder  40  (decoder  42  has the same structure). The decoders  40 ,  42  consist of blocks for calculating γ values, blocks for performing iteration, and a soft bit output block. 
     The first step in the decoding operation as shown in FIG. 5 is to take three soft bits P 3k ( 0 ), P 3k ( 1 ), P 3k+1 ( 0 ), P 3k+1 ( 1 ), P 3k+2 ( 0 ), P 3k+2 ( 1 ) to form eight probability values (a normal turbo decoder has only two values because it contains only one bit of information): P k 000, P k 001, P k 010, P k 011, P k 100, P k 101, P k 110, and P k 111. For example,                P   000   k     =     log        [     Prob        (         b     3      k       =   0     ,       b       3      k     +   1       =   0     ,       b       3      k     +   2       =   0       )       ]                   =         P     3      k            (   0   )       +       P       3      k     +   1            (   0   )       +       P       3      k     +   2            (   0   )                                      
     In general, 
     P k j (j=mn 1 =000, 001, . . . , 111) can be obtained as                P   mn1   k     =     log        [     Prob        (         b     3      k       =   m     ,       b       3      k     +   1       =   n     ,       b       3      k     +   2       =   1       )       ]                   =         P     3      k            (   m   )       +       P       3      k     +   1            (   n   )       +       P       3      k     +   2            (   1   )                                      
     With p k j and the corresponding error check bit (P ck ( 0 ), P ck ( 1 )), the value γ j (R k , s′, s) can be obtained as 
     
       
         γ j ( R   k   , s′, s )=log( Pr ( d   k   =j, S   k   =s, R   k   |S   k−1   =s ′))= P   j   k   +P   ck ( m ) 
       
     
     where j=000, 001, . . . , 111 and m=0 or 1 depending on the error check bit when transferring from state s′ to s. R k  represents the received information. 
     With γ j (R k , s′, s), the forward iteration (α) iteration with LOG-MAP algorithm) can be implemented as shown in FIG. 6, where the normalization block puts all γ j (R k , s′, s) into the center of the dynamic range with the same normalization factor so that the whole dynamic range in a fixed point implementation can be utilized. 
     The same principle is applied to the output α k (s), i.e., all α k (s) at different state s (for the same iteration k) are normalized with a same normalize factor so that they are all located in the center of dynamic range. The determination of normalization factor is the same as that used in the normal turbo decoder implementation. The difference in the forward iteration is that each state s at iteration k (α k (s)) is determined by eight previous states (α′ k−1 (s′ 000 ), α′ k−1 (s′ 001 ), . . . , α′ k−1 (s′ 111 )), each corresponding one input γ j (R k , s′, s) value (in a conventional turbo decoder, each state at iteration k is determined by only two previous states because the input is only one bit information). The LOG-ADD OPERATION in FIG. 6 is shown in FIG. 7, which consists of a max operation and a look-up table. 
     The backward iteration has the same structure as the forward iteration and is shown in FIG.  8 . 
     After finishing forward and backward iteration, the soft bit outputs are calculated in two steps as follows: 
     first calculate eight P j   k  values for j=000, 001, . . . , 111 as 
     
       
           P   k   j =MAX (s, s′) [γ j ( R   k   , s, s ′)α k−1 ( s ′)β k ( s )] 
       
     
     Then the soft output is the combination of P j   3k  values, such as 
     
       
           P   o   3k ( 0 )=prob( b   3k =0)= P   000   k   +P   010   k   +P   100   k   +P   110   k   
       
     
     
       
           P   o   3k ( 1 )=prob( b   3k =1)= P   001   k   +P   011   k   +P   101   k   +P   111   k   
       
     
     
       
           P   o   3k+1 ( 0 )=prob( b   3k =1)= P   000   k   +P   001   k   +P   100   k   +P   101   k   
       
     
     
       
           P   o   3k+1 ( 1 )=prob( b   3k+1   = 1   )= P   010   k   +P   011   k   +P   110   k   +P   111   k   
       
     
     
       
           P   o   3k+2 ( 0 )=prob( b   3k+2 =0)= P   000   k   +P   001   k   +P   010   k   +P   011   k   
       
     
     
       
           P   o   3k+2 ( 1 )=prob( b   3k+2 =1)= P   100   k   +P   101   k   +P   110   k   +P   111   k   
       
     
     At the last iteration, the soft error check bits are also outputted as:            P   c       3      k     +   2            (   1   )       =       prob        (       b   c       3      k     +   2       =   1     )       =       MAX     (     s   ,     s   ′       )            [         γ   ck1          (         R     k   ,          s     ,     s   ′       )              α     k   -   1            (     s   ′     )              β   k          (   s   )         ]                     P   c       3      k     +   2            (   0   )       =       prob        (       b   c       3      k     +   2       =   0     )       =       MAX     (     s   ,     s   ′       )            [         γ   ck0          (         R     k   ,          s     ,     s   ′       )              α     k   -   1            (     s   ′     )              β   k          (   s   )         ]                                
     where γ ck0 (R k , s, s′) and γ ck1 (R k , s, s′) represent the transferring probability from state s′ to s with error check bit (at time 3k+2) being 0 and 1 respectively. 
     The blocks described above can be implemented in a digital signal processor using standard digital processing techniques known to persons skilled in the art of digital signal processing. 
     The described techniques increase the implementation speed of the turbo encode and decoder and result in significant memory savings in the parallel decoder. 
     The invention is applicable to a decoder with a variable coding rate.