FR2808394A1 - METHOD AND DEVICE FOR TURBOCODULATED TRELLIS MODULATION - Google Patents

Abstract

According to a method of transmitting data over a communication channel according to the invention, at least some of the bits of an arriving bit stream (10) are passed through a turbocoder (RSC1, RSC2) in order to generate bits turbocoded output, and words corresponding to symbol points on a constellation in a trellis code modulation scheme are generated using at least the bits that are passed through the turbocoder, possibly in conjunction with other bits that did not pass through the turbocoder. Typically, the turbocoder bits are least significant bits.

Description

Field of the Invention The present invention relates to the field of

  data transmission and more particularly, it relates to a modulation scheme for transmitting data over a communication channel, for example in a discrete multi-frequency modulation system. BACKGROUND OF THE INVENTION In order to increase the efficiency of a data transfer over a communication channel, the data is transferred as symbols each of which represents a number of bits. For example, in a quadrature amplitude modulated (QAM) system, the symbols are represented by the amplitude and phase of the signals. Sixteen unique symbols, i.e., amplitude and phase combinations, for example, will represent four bits at a time. The symbols form a constellation of points on a phase / amplitude diagram. As the number of symbols increases, the possibility of error transmission does the same. Forward error coding schemes are used to allow the receiver to detect

  errors and restore the correct transmitted symbol.

  A preferred form of coding at the data communications level is convolutional coding which is a bit level coding scheme that depends on the previous bit sequence. According to a trellis coded modulation, the number of symbols is increased so

  to ensure redundancy. Only certain transitions are allowed.

  In the case of an error, the receiver can detect the most probably correct transition knowing all the transitions

allowed.

  Unlike block codes that send data according to predetermined blocks, convolutional codes do not permit satisfactory processing of burst errors. In part as an answer to this problem, turbocodes have been developed. In essence, a turbocode consists of two or more convolutional codes that are separated by an interleaver that operates on the input sequence of the first encoder. See for example "Application of Turbo Codes for Discrete Multi-tone

  Modulation "by Hamid R. Sadjapour, AT & T Shannon Labs, 1996.

  The turbocode is attracting more and more interest because of its larger coding gain. In a digital subscriber line or DSL system, a turbocode has been used to replace a trellis code in order to achieve better performance in terms of bit error rates (BER). However, as the size of the constellation increases, the advantage of the coding gain of the turbocode begins to collapse. This is because the redundancy bits or

  Redundants make the dimension of the constellation even more important.

  An object of the present invention is to increase the flow rate of

  data transmission, for example in a DMT system.

  SUMMARY OF THE INVENTION In accordance with the present invention there is provided a method for transmitting data over a communication channel, comprising receiving an incoming bitstream, passing at least some of said bits through a turbo encoder for generating 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 that are passed to the

through said turbocharger.

  According to the present invention, the turbo encoder is preferably used to encode only the least significant bit (LSB) in the constellation since the LSB is the most sensitive to errors. The data rate that can be achieved using this means is far from Shannon's capacity of only 2 dB. The invention combines a powerful turbocode with a trellis coded modulation scheme to increase the throughput of

  data, preferably in a DMT (discrete multi-frequency) system.

  In a DMT system, multiple sub-channels are used to transmit data, each of which has 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 can not support an entire data bit. According to the invention, an extended spectrum algorithm can be combined with trellis-coded modulation so that channels carrying less than one whole bit of information can also be used. As a result, the overall capacity in terms of channels can be greatly increased.

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: Figure 1 shows an encoder according to the principles of the invention for x and y> 1, ox and y are the number bits in each constellation point (symbol); Fig. 2 shows the encoder structure for x = 1 and y> 1, where the turbo-coding rate is 2/3; Fig. 3 shows an encoder structure for the case y = 1 and x> 1; FIG. 4 represents the coder for x = y = 1, where the coding rate is 1/2; Figure 5 is a block diagram of the decoder; Fig. 6 shows a constellation representing how the three final bits are determined; and Figure 7 is a constellation that represents the determination of

bits of the strongest weight.

  Detailed Description of the Preferred Embodiments

  The invention will be described in the context of a discrete DMT or multi-frequency system which could typically contain 1000 subchannels each of which can carry a different number of symbols representing a distinct number of bits, i.e. the number constellation points for each subchannel can vary, and therefore the

  number of bits per constellation point may vary.

  Encoder As shown in FIG. 1, part of an incoming bitstream is applied to an encoder data block 10 which is an addressable memory. Assuming 10 bits per symbol including one control bit for two subchannels, the 1000 channels can carry 9500 bits at a time. Therefore, typically 9500 bits of an arriving bitstream or bit stream are applied in the encoder. A fraction of these bits, typically

  1500, are applied to the encoder data block 10.

  The encoder can preferably be implemented as a parallel encoder as described in our co-pending United Kingdom patent application number 0010330.9 filed April 18, 2000.

  whose contents are incorporated herein by reference.

  In the example shown, three bits μ1, u2, u3 are sequentially outputted from the encoder data block 10 and three bits U'1, u'2, u'3 are output as interleaved data. The data bits u2 and u3 form components vo0, va of the first output word v and the bit u1 forms the bit w1 of the second output word w. The wo bit is formed by turbocharging the groups of bits u1, u2, u3 and u'1, u'2, u'3 by means of recursive systematic convolutional coders 12, 14 after passing through registers to

respective offset 16, 18.

  The structure of the constellation encoder used is similar to that used in an ADSL system. The binary word u = (uz ,, uz,., ..., ul) determines two binary words v = (v, .y, ..., vo) and w = (wy.1, ..., w0 ) (oz '= x + y -1) which are used to look up two constellation points (each contains

  respectively x and y bits) in the encoder look-up table.

  FIG. 1 shows the encoder structure for x> 1 and y> 1, where the turbo encoder used is a systematic encoder with a rate or rate of 3/4 coding brought back to the 1/2 rate. The turbocoder 20 consists of the two recursive systematic convolutional coders 12, 14 (RSC1 and RSC2). The RSC1 encoder extracts sequential data from the encoder data block 10 and the RSC2 encoder extracts data interleaved with

  from the same data block 10.

  The length of the data block depends on the number of data that are transmitted in each signal frame, ie 9500 bits in the example presented above. Normally, an integer number of data blocks will be transmitted in each signal frame. Figures 2 to 4 represent

  the encoder structure for other values of x and y.

  Figure 2 shows the encoder structure for x = 1 and y> 1, where the rate or turbo coding rate is 2/3. For the case of y = 1 and x> 1, the encoder structure shown in Figure 3 is similar to the one

is shown in Figure 2.

  FIG. 3 represents the encoder structure for the case x = y = 1, where the coding rate or coding rate is 1/2. For y <I (or x <1), an encoder structure similar to that shown in Figures 1 to 4 may be used depending on the value of x (or y). The only difference is that a bit will be transmitted in

  using K subchannels o y = 1 / K using a spread code.

  If the spread code that is used is [b1, b2, ..., bK], 0 can be transmitted as [b1, b2, ..., bK] o (k = 1, 2, ..., K) and 1 is transmitted as [bl, b2, ..., bK]. The constellation for each subchannel in the subchannel K group uses one bit per channel constellation and the k-th channel transmits the bk bit. Overall, K sub-channels are required to transmit a bit of data. The advantage of such an arrangement is that autotax can be strongly reduced if different spread codes are used for different modems in the same pair of pairs. Suitable spread codes are described in IEEE Communications Letters, Vol.

  4, No. 3, pp. 80 to 82, March 2000, R. V. Sonalkar and R. R. Shively.

  Decoder The decoding procedure for a trellis-coded modulation consists of the following steps: 1. Flexible decoding of the least significant bit (LSB); 2. Hard decoding of the most significant bits (MSB); 3. Decoding the LSB using a turbodecoder algorithm; and

  4. Determination of all data bits.

  If an N-bit constellation is used for data transmission in a given subchannel, the location of the constellation can be represented by two dimensional vectors Xb = [bxM, bx (M-1), ... bx1, 1] and Yb = [byM, by (M-1), ..., by1, 1] where M = N / 2 for an even number N and M = (N + 1) / 2 for an odd number N. The decoder will be the same for both Xb and Yb. It is assumed that received data is (X, Y). If (2M + 1 + 2k) <X <(-2M + 1 + 2 (k + 1)) ok = 0, 1, ..., 2M-1 and if we put X1 = (-2M + 1 + 2k ) and X2 = (-2M + 1 + 2 (k + 1)), the determination of whether the final X will take the value X1 or X2 depends on the decoder result due to the LSB. For N> 1, the soft bit (a logarithmic probability without a constant) for the LSB in X is determined as follows [_ (X + 1 if N = 2 P1 = 1og (probe (bx1 = 1)) = X_2-l (X + 4k_2M + 3) 2 otherwise L k = 0 l kO 2o2 'aurmn F_ (X + 1) 2 if N = 2 P0 = log (probe (bx1 = 0)) = 2 (X + 4k2M + 1) 2 _2M-1 (X + 4k_2M + 3) Ik = 0 2, otherwise tk = O 2cy where u2 is the noise power The soft bit for the LSB in Y can be obtained in a similar way by replacing X by Y in 'equation

mentioned above.

  If N = 1, the soft bit will be: P1l = log (probe (bx1 = 1)) = _ (X + 1) 2 + (Y + 1) 2 2 2a2 2 a2) P0 = log (probe (bx1 = 0) )) = (X-1) y2 (Y-1) 2 2 If N <1 and if the spread code is [b1, b2, ..., bK], the soft bit can be calculated as follows: K (X - (1-2bk) 2) (Y_ (1-2bk) 2) Po = log (probe (bx1 = 0)) = - + 22) k = 1 2oy2 2o2 The soft bit output is sent to a turbo-decoder circuit which is shown in FIG. 5. The turbodecoder consists of two LOG-MAP decoders 30, 32. Each decoder contains a forward iteration (a) and a backward iteration (13) and performs the output calculation. final soft bit. The only difference is that the output contains not only the data bit but also the error check bit at

level of its last iteration.

  The reason the output of the error check bit is required is that LSB is needed to determine X (or Y) from two possible constellation points Xi and X2 (or Y1 and Y2) although some of these LSBs are error control bits. A detailed example of a turbodecoder can be found in the Sadjapour article referred to above and also in the document by C. Berrou et al., "Near Optimum Error Correcting Coding and Decoding Turbo Codes", IEEE

  Trans. on Communications, vol. 44, No. 10, October 1996.

  The soft output error check bits at time k are computed as follows: Pck1 = probe (bck = 1) = MAX (s, s,) [Yck1 (Rk, S, S ') OEk-1 ( S ') k (S)] Pcko = probe (bck = 0) = MAX (s, s') [YckO (Rk, S, S ') Ok-1 (S') 13k (S)] os is the state of the turbocoder at time k and s' is its state at time k-1. Rk represents the received data. 3k (S) is the probability for the state s (at instant k) for a backward iteration and Ok.l (s ') represents the probability for the state s' (at the instant k- 1) for a forward iteration. YCko (Rk, s, s') and YCk1 (Rk, s, s') are the transition probability from state s' to state s with received data which are Rk and with the control bit error that is worth

respectively 0 and 1.

  After passing through the turbodecoder, the LSBs are determined and if N> 1, the MSBs must still be determined from two possible constellation points. We consider as example X which presents two

  possible values Xi or X2 (which are two neighboring points in the constellation).

  For two neighboring constellation points, the LSBs for Xi and for X2 must be different. Therefore, Xb = [bxM, bX (M-1), ..., bx1, 1] can be determined from X1 and X2 by examining the corresponding LSB. Similarly, Yb = [byM, by (M-1), ..., by1, 1] can be determined. After Xb and Yb are determined, the final received data bits are obtained for the three

following cases.

  When N is even, the final bits are [bN, bN-1, ..., b1] = [bxM, byM, bx (M-

  1), by (M-1), ..., bx1, by1]. If N = 3, the three final bits are determined by means of a constellation which is shown in Figure 6, which is furthermore

  presented in tabular form in Table 1.

bx2bxl by2byl b3b2b1

00 00 000

00 01 101

00 10 001

00 11 001

01 00 000

01 01 101

01 10 111

01 11 111

00 100

01 100

10,110

11,011

11 00 010

11 01 010

11 10 110

11 11 011

  If N is an odd number and N> 3, the weak (N - 5) bit can be determined in the same way as for the case of even N, ie [bN-5, bN-6 , b1] = [bx (M-3), by (M-3), bx (M-4), by (M-4), ..., bx1, b1]. The MSBs are determined in accordance with a constellation as shown in Figure 7, which constellation is further presented in tabular form

at the level of Table 2.

  bxMbx (M-1) bx (M-2) byMby (M-1) by (M-2) bNbN-1bN-2bN-3bN-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

000 10000

001 10001

010 10110

011 10110

100 10111

101 10111

110 11100

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

000 10010

001 10011

010 10011

011 10011

100 11110

101 11110

110 11110

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

000 01000

001 01001

010 11000

011 11000

100 11001

101 11001

110 01100

111 01101

111 000 01010

111 001 01011

111 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 turbocode as described in combination with trellis code provides better performance than is possible with lattice codes presently used. When a spread spectrum algorithm is combined with a trellis-coded modulation, it is possible to use channels carrying less than one information bit, which leads to an increase

  significant capacity in terms of channels.

  The described blocks can be implemented in a digital signal processor or DSP which uses known standard DSP techniques

of the man of the art.

Claims (14)

  A method for transmitting data over a communication channel, characterized in that it comprises receiving an incoming bitstream, passing at least some of said bits through a turbocoder in order to generate bits. turbocharged output 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. 2. Method according to claim 1, characterized in that said bits which have passed through the turbocoder are the least significant bits (LSB) of the incoming data and that the bits of   highest weight are passed directly to the output word.   A method according to claim 1, characterized in that a portion of the arriving bitstream is sent to a memory and interleaved bit groups from said memory are sent to recursive systematic convolutional coders to create said turbocharged output bits.   4. Method according to claim 1, characterized in that said symbols are transported on a plurality of sub-channels in   a discrete multi-frequency system (DMT).   5. Method according to claim 1, characterized in that, for at least some of said subchannels, the symbol points of   constellation contain less than one integer bit and for such sub-   channels, an entire bit is transmitted over K subchannels using a code spread.   6. Process according to any one of claims 1 to 5,   characterized in that said words include error control bits.   7. Method according to claim 1, characterized in that said words are used to obtain the constellation points from   an encoder lookup table.   An encoder for encoding a data stream arriving for transmission over a communication channel, characterized by comprising an encoder data block (10) for storing a portion of the arriving data stream, a first systematic convolutional coder recursive (RSCI) receiving sequential data from the encoder data block and a second recursive systematic convolutional encoder (RSC2) which receives interleaved data from the encoder data block, said convolutional encoders outputting at least the lowest weight of an output data word that forms a symbol point on a constellation in a   trellis code modulation scheme.   9. Encoder according to claim 8, characterized in that it further comprises a shift register (16, 18) connected to the input of each recursive systematic convolutional encoder (RSC1, RSC2), each cell of said shift register receiving a respective bit since   said encoder data block (10).   An encoder according to claim 8, characterized in that, for x = y = 1, where x and y are the numbers of bits in each of two constellations, the inputs of said recursive systematic convolutional encoder are directly connected to said data block of encoder (10).   11il. A method of decoding a lattice-type turbocode modulation signal, characterized in that it comprises: (i) soft decoding of the received signal for the least significant bits; (ii) hard decoding of the input signal for the most significant bits; (iii) decoding the least significant bit using a turbodecoder algorithm; and   (iv) determination of all data bits.   The method of claim 11, characterized in that the received signal is processed to determine the soft bit (log probability without constant) for the LSB as follows: _ (X + 1) 2   2_aX12 if N = 2 Pl = lgsnebll 2o2 P1 1og (probe (bx1 = 1)) - 2M-1 (X + 4k-2M + 3) 2 otherwise k = O 2c2 where s22 is the target (X + 1) 2 if N = 2 2 o2 Pd = log (probe (bc1 = 0)) error.   L10k k0m), otherwise o a2 is the noise power. Method according to claim 12, characterized in that the soft bit is passed over a turbo encoder to generate a bit of   data and an error check bit.   14. The method according to claim 13, characterized in that, after determination of the LSBs, the MSBs are determined from points   possible constellation by examining the LSBs.   15. Method according to claim 11, characterized in that a decoder of LSB and MSB is combined for different constellations. Decoder apparatus for decoding a lattice modulated turbocode signal, characterized in that it comprises a pair of decoders (30, 32) connected to receive soft input bits, an interleaver and a deinterleaver and in that said decoders derive from said input soft bits a data bit and at least one error control bit.   A decoder apparatus according to claim 16, characterized in that each decoder iterates forward and   the back and a calculation of the final soft bit output.   Decoder apparatus according to claim 16, characterized   in that said decoders are LOG-MAP decoders.