Abstract:
In a method of transmitting data over a communications channel, at least some of the bits of an incoming bit stream are passed through a turbo encoder to generate turbo encoded output bits, and words corresponding to symbol points on a constellation in a trellis code modulation scheme are generated using at least the bits passed through the turbo encoder, possibly in conjunction with other bits that are not passed the through the turbo encoder. Typically, the turbo encoded bits are the least significant bits.

Description:
FIELD OF INVENTION 
     This invention relates to the field of data transmission, and in particular to a modulation scheme for transmitting data over a communication channel, for example, in a discrete multi-tone modulation system. 
     BACKGROUND OF THE INVENTION 
     In order to increase the efficiency of data transfer over a communications channel, the data is transferred as symbols, each representing a number of bits. For example, in a QAM (Quadrature amplitude modulation) system, the symbols are represented by the amplitude and phase of the signals. Sixteen unique symbols, i.e. combinations of amplitude and phase, for example, will represent four bits at time. The symbols form a constellation of points on a phase amplitude diagram. As the number of symbols increases, so does the possibility for transmission errors. Forward error coding schemes are employed to permit the receiver to detect errors and recover the correct transmitted symbol. 
     A preferred form of coding in data communications is convolutional coding, which is a bit level encoding scheme which depends on the preceding bit sequence. In Trellis coded modulation, the number of symbols is increased to provide redundancy. Only certain transitions are allowed. In the event of an error, the receiver can detect the most likely correct transition with a knowledge of all possible allowed transitions. 
     Unlike block codes, which send data in predetermined blocks, convolutional codes do not cope well with burst errors. Partly, in answer to this problem, turbo codes have been developed. In essence, turbo code consists of two or more convolutional constituent codes separated by an interleaver acting on the input sequence of the first encoder. See for example, “Application of Turbo Codes for Discrete Multi-Tone Modulation”, Hamid R. Sadjapour, AT&amp;T Shannon Labs., 1996. 
     Turbo code is attracting more and more interest due to its larger coding gain. In a DSL (Digital Subscriber Line) system, turbo code has been 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 fall odd. This is because the redundant bits make the constellation size even larger. 
     An object of this invention is to increase the data transmission rate, for example, in a DMT system. 
     SUMMARY OF THE INVENTION 
     According to the present invention there is provided a method of transmitting data over a communications channel, comprising receiving an incoming bit stream, passing at least some of said bits through a turbo encoder to generate turbo encoded output bits, and generating words corresponding to symbol points on a constellation in a trellis code modulation scheme using at least said bits passed through said turbo encoder. 
     In this invention, the turbo coder is preferably used to code only the least significant bit (LSB) in the constellation since the LSB is most sensitive to errors. The achievable data rate by this means is only a couple of dB away from Shannon capacity. The invention combines powerful turbo code with a trellis-coded modulation scheme to increase the data rate, preferably in a DMT (Discrete Multi-tone) system. 
     In a DMT system, multi-subchannels are used to transmit data, each with different carriers and different QAM constellations containing different numbers of bits per constellation point. Normally, the number of bits at each constellation point is an integer and a subchannel is unusable if it cannot support one data bit. In accordance with the invention, a spread spectrum algorithm can be combined with turbo trellis-coded modulation so that channels which carry less than one bit of information can also be used. As a result, the overall channel capacity can be increased greatly. 
    
    
     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 shows an encoder in accordance with the principles of the invention for x and y&gt;1, where x and y are the number of bits in each constellation point (symbol); 
     FIG. 2 shows an the encoder structure for x=1 and y&gt;1, where the turbo coding rate is ⅔; 
     FIG. 3 shows an encoder structure for the case y=1 and x&gt;1, 
     FIG. 4 shows the encoder for x=y=1, where the coding rate is ½; 
     FIG. 5 is a block diagram of the decoder; 
     FIG. 6 shows a constellation showing how the final three bits are determined; and 
     FIG. 7 is a constellation showing the determination of the most significant bits. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The invention will be described in the context of a DMT (Discrete Multitone System), which might typically contain 1000 sub-channels, each capable of carrying a different number of symbols representing a distinct number of bits, i.e. the number of constellation points for each sub-channel can vary, and thus the number of bits per constellation point can vary. 
     Encoder 
     As shown in FIG. 1, a portion of an incoming bit stream is fed to encoder data block  10 , which is an addressable memory. Assuming 10 bits per symbol, including one check bit per two subchannels, the 1000 channels can carry 9500 bits at a time. Thus, typically 9500 bits of an incoming bit stream are fed into the encoder. A fraction of these, typically 1,500, are fed to the encoder data block  10 . 
     The encoder may preferably be implemented as a parallel encoder as described in our co-pending application No. 09/562,352 of even date herewith, the contents of which are herein incorporated by reference. 
     In the example shown, three bits u 1 , u 2 , u 3  are output sequentially from the encoder data block  10 , and three bits, u′ 1 , u′ 2 , u′ 3  are output as interleaved data. The data bits u 2 , and u 3 , form components v 0 , v 1  of the first output word v, and the bit u 1  forms the bit w 1  of the second output word w. The bit w 0  is formed by turbo encoding the groups of bits u 1 , u 2 , u 3 , and u′ 1 , u′ 2 , u′ 3  with recursive systematic convolutional encoders  12 ,  14  after passing through respective shift registers  16 ,  18 . 
     The constellation encoder structure employed is similar to that used in an ADSL system. The 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 (each contains x and y bits respectively) in the encoder look-up table. 
     FIG. 1 shows the encoder structure for x&gt;1 and y&gt;1, where the turbo encoder used is a systematic encoder with coding rate ¾ punctured at rate ½. The turbo encoder  20  consists of the two recursive systematic convolutional encoders  12 ,  14  (RSC1 and RSC2). Encoder RSC1 takes sequential data from the encoder data block  10  and encoder RSC2 takes interleaved data from the same data block  10 . 
     The length of data block depends on the number of data being transmitted in each signal frame, 9500 bits in the example given above. Normally, an integer number of data blocks will be transmitted in each signal frame FIGS. 2 to  4  show the encoder structure for other values of x and y. 
     FIG. 2 shows the encoder structure for x=1 and y&gt;1, where the turbo coding rate is ⅔. For the case y=1 and x&gt;1, the encoder structure, shown in FIG. 3, is similar to that shown in FIG.  2 . 
     FIG. 3 shows the encoder structure for the case x=y=1, where the coding rate is ½. For y&lt;1 (or x&lt;1), a similar encoder structure to that shown in FIGS. 1 to  4  can be used depending on the value of x (or y). The only difference is that one bit will be transmitted using K subchannels where y=1/K using a spread code. 
     If the spread code being used is [b 1 , b 2 , . . . , b K ], 0 can be transmitted as [b 1 , b 2 , . . . , b K ] where (k=1, 2, . . . , K) and 1 is transmitted as [−b 1 , −b 2 , . . . , −b K ]. The constellation for each subchannel in the K subchannel group uses one bit per channel constellation and the k th  channel transmits bit b k . As a whole, K subchannels are required to transmit one data bit. The advantage of such an arrangement is that self cross-talk can be reduced greatly if different spread codes are used for different modems in the same bundle group. Suitable spread codes are described in IEEE Communications Letters, vol. 4, no. 3, pp. 80-82, March 2000, R. V. Sonalkar and R. R. Shively. 
     Decoder 
     The decoding procedure for turbo trellis-coded modulation consists of following steps: 
     1) Soft decode the least significant bit (LSB); 
     2) Hard decode the most significant bits (MSB). 
     3) Decode the LSB using a turbo decoder algorithm; and 
     4) Determine all data bits 
     If an N bit constellation is used for data transmission in a given subchannel, the constellation location can be represented by two dimensional vectors: X b =[b xM , b x(M−1) , . . . , b x1 , 1] and Y b =[b yM , b y(M−1) , . . . , b y1 , 1] where M=N/2 for an even number N and M=(N+1)/2 for odd number N. The decoder will be the same for both X b  and Y b . 
     Let received data be (X, Y). If (−2 M −1+2k)&lt;X&lt;(−2 M −1+2(k+1)) where k=0, 1, . . . , 2 M −1, and retaining X 1 =(−2 M −1+2k) and X 2 =(−2 M −1+2(k+1)), whether the final X will take X 1  or X 2  depends the decoder result from the LSB. For N&gt;1, the soft bit (log probability without a constant) for the LSB in X is determined as          P   1     =       log        (     prob        (       b   x1     =   1     )       )       =     {                     (     X   +   1     )     2       σ   2       ,           N   =   2                   ∑     k   =   0       2     M   -   1                  (     X   +     4      k     -     2   M     +   3     )     2       σ   2         ,         otherwise              
          P   0       =       log        (     prob        (       b   x1     =   0     )       )       =     {                 (     X   -   1     )     2       σ   2       ,           N   =   2                   ∑     k   =   0       2     M   -   1                  (     X   +     4      k     -     2   M     +   1     )     2       σ   2         ,         otherwise                                          
     where σ 2  is the noise power. The soft bit for the LSB in Y can be obtained in a similar way by replacing X with Y in the above equation. 
     If N=1, the soft bit will be          P   0     =       log        (     prob        (       b   x1     =   0     )       )       =     (           (     X   -   1     )     2       σ   2       +         (     Y   -   1     )     2       σ   2         )                 P   0     =       log        (     prob        (       b   x1     =   0     )       )       =     (           (     X   -   1     )     2       σ   2       +         (     Y   -   1     )     2       σ   2         )                   If                 N     &lt;     1                 and                 the                 spread                 code                   is              [       b   1     ,     b   2     ,   …              ,     b   K       ]         ,     the                 soft                 bit             can                 be                 calculated                 as             P   1     =       log        (     prob        (       b   x1     =   0     )       )       =       ∑     k   =   1     K          (           (     X   +     b   k       )     2       σ   2       +         (     Y   +     b   k       )     2       σ   2         )                   P   0     =       log        (     prob        (       b   x1     =   0     )       )       =       ∑     k   =   1     K          (           (     X   -     b   k       )     2       σ   2       +         (     Y   -     b   k       )     2       σ   2         )                                
     The soft bit output is sent to turbo decoder circuit which is shown in FIG.  5 . The turbo decoder consists of two LOG-MAP decoders  30 ,  32 . Each contains forward (α) iteration, backward (β) iteration and performs the final soft bit output calculation. The only difference is the output contains not only the data bit but also the error check bit at its last iteration. 
     The reason that the output of error check bit is required is that the LSB is needed to determine X (or Y) from two possible constellation points X 1  and X 2  (or Y 1  and Y 2 ), while some of these LSBs are error check bits. A detailed example of a turbo decoder can be found in the Sadjapour article referred to above and also in C. Berrou and A., “Near Optimum Error Correcting Coding and Decoding Turbo-Codes”, IEEE Trans. on Communications, Vol. 44, No. 10, Oct., 1996. 
     The soft output error check bits at time k is calculated as 
     
       
           P   ck1 =prob( b   ck =1)=MAX (s, s′) [γ ck1 ( R   k   , s, s ′)α k−1 ( s ′)β k ( s )] 
       
     
     
       
           P   ck0 =prob( b   ck =0)=MAX (s, s′) [γ ck0 ( R   k   , s, s ′)α k−1 ( s ′)β k ( s )] 
       
     
     where s is the state of turbo coder at time k and s′ is the state at time k−1. R k  represents the received data. β k (s) is the probability at state s (time k) for backward iteration and α k−1 (s′) represents the probability at state s′ (time k−1) for forward iteration. γ ck0 (R k , s, s′) and γ ck1 (R k , s, s′) are the probability of transition from state s′ to s with received data being R k  and the error check bit being 0 and 1 respectively. 
     After passing through turbo decoder, the LSBs are determined and if N&gt;1, the MSBs are still to be determined from two possible constellation points. Take X as an example, which has two possible values X 1  or X 2  (which are two neighbor points in constellation). For two neighboring constellation points, the LSB for X 1  and X 2  must be different. Therefore, X b =[b xM , b x(M−1) , . . . , b x1 , 1] can be determined from X 1  and X 2  by examining its LSB. Similarly Y b =[b yM , b y(M−1) , . . . , b y1 , 1] can be determined. After X b  and Y b  are determined, the final received data bits are obtained for following three cases: 
     When N is even, the final bits are [b N , b N−1 , . . . , b 1 ]=[b xM , b yM , b x(M−1) , b y(M−1) , . . . , b x1 , b y1 ]. 
     If N=3, the final three bits are determined by constellation shown in FIG. 6, which is further tabulated in Table 1. 
     
       
         
               
               
               
             
           
               
                   
               
               
                 b x2 b x1   
                 b y2 b y1   
                 b 3 b 2 b 1   
               
               
                   
               
             
             
               
                 00 
                 00 
                 000 
               
               
                 00 
                 01 
                 101 
               
               
                 00 
                 10 
                 001 
               
               
                 00 
                 11 
                 001 
               
               
                 01 
                 00 
                 000 
               
               
                 01 
                 01 
                 101 
               
               
                 01 
                 10 
                 111 
               
               
                 01 
                 11 
                 111 
               
               
                 10 
                 00 
                 100 
               
               
                 10 
                 01 
                 100 
               
               
                 10 
                 10 
                 110 
               
               
                 10 
                 11 
                 011 
               
               
                 11 
                 00 
                 010 
               
               
                 11 
                 01 
                 010 
               
               
                 11 
                 10 
                 110 
               
               
                 11 
                 11 
                 011 
               
               
                   
               
             
          
         
       
     
     If N is an odd number and N&gt;3, the low bit (N−5) can be determined the same way as for even N case, i.e., [b N−5 , b N−6 , . . . , b 1 ]=[b x(M−3) , b y(M−3) , b x(M−4) , b y(M−4) , . . . , b x1 , b y1 ]. The 5 MSBs are determined according to constellation in FIG. 7, which is further tabulated in Table 2. 
     
       
         
               
               
               
             
           
               
                   
               
               
                 b xM b x(M−1) b x(M−2)   
                 b yM b y(M−1) b y(M−2)   
                 b N b N−1 b N−2 b N−3 b N−4   
               
               
                   
               
             
             
               
                 000 
                 000 
                 00000 
               
               
                 000 
                 001 
                 00001 
               
               
                 000 
                 010 
                 10100 
               
               
                 000 
                 011 
                 10100 
               
               
                 000 
                 100 
                 10101 
               
               
                 000 
                 101 
                 10101 
               
               
                 000 
                 110 
                 00100 
               
               
                 000 
                 111 
                 00101 
               
               
                 001 
                 000 
                 00010 
               
               
                 001 
                 001 
                 00011 
               
               
                 001 
                 010 
                 10110 
               
               
                 001 
                 011 
                 10110 
               
               
                 001 
                 100 
                 10111 
               
               
                 001 
                 101 
                 10111 
               
               
                 001 
                 110 
                 00110 
               
               
                 001 
                 111 
                 00111 
               
               
                 010 
                 000 
                 10000 
               
               
                 010 
                 001 
                 10001 
               
               
                 010 
                 010 
                 10110 
               
               
                 010 
                 011 
                 10110 
               
               
                 010 
                 100 
                 10111 
               
               
                 010 
                 101 
                 10111 
               
               
                 010 
                 110 
                 11100 
               
               
                 010 
                 111 
                 11101 
               
               
                 011 
                 000 
                 10000 
               
               
                 011 
                 001 
                 10001 
               
               
                 011 
                 010 
                 10001 
               
               
                 011 
                 011 
                 10001 
               
               
                 011 
                 100 
                 11101 
               
               
                 011 
                 101 
                 11100 
               
               
                 011 
                 110 
                 11100 
               
               
                 011 
                 111 
                 11100 
               
               
                 100 
                 000 
                 10010 
               
               
                 100 
                 001 
                 10011 
               
               
                 100 
                 010 
                 10011 
               
               
                 100 
                 011 
                 10011 
               
               
                 100 
                 100 
                 11110 
               
               
                 100 
                 101 
                 11110 
               
               
                 100 
                 110 
                 11110 
               
               
                 100 
                 111 
                 11111 
               
               
                 101 
                 000 
                 10010 
               
               
                 101 
                 001 
                 10011 
               
               
                 101 
                 010 
                 11000 
               
               
                 101 
                 011 
                 11000 
               
               
                 101 
                 100 
                 11001 
               
               
                 101 
                 101 
                 11001 
               
               
                 101 
                 110 
                 11110 
               
               
                 101 
                 111 
                 11111 
               
               
                 110 
                 000 
                 01000 
               
               
                 110 
                 001 
                 01001 
               
               
                 110 
                 010 
                 11000 
               
               
                 110 
                 011 
                 11000 
               
               
                 110 
                 100 
                 11001 
               
               
                 110 
                 101 
                 11001 
               
               
                 110 
                 110 
                 01100 
               
               
                 110 
                 111 
                 01101 
               
               
                 111 
                 000 
                 01010 
               
               
                 111 
                 001 
                 01011 
               
               
                 011 
                 010 
                 11010 
               
               
                 111 
                 011 
                 11010 
               
               
                 111 
                 100 
                 11011 
               
               
                 111 
                 101 
                 11011 
               
               
                 111 
                 110 
                 01110 
               
               
                 111 
                 111 
                 01111 
               
               
                   
               
             
          
         
       
     
     It will be appreciated that the use of a turbo code as described in combination with a trellis code permits the achievement of better performance than is possible with currently used trellis codes. When a spread spectrum algorithm is combined with turbo-trellis coded modulation, it is possible to use channels carrying less than one bit of information, resulting in a great increase in channel capacity. 
     The described blocks can be implemented in a digital signal processor using standard DSP techniques known to persons skilled in the art.