Abstract:
In a receiver, an outer decoder in an inner/outer decoder scheme receives bit error information or bit error probability information from an inner decoder rather than being generated internally by the outer decoder. The inner decoder may be a soft-decision decoder that provides bit error probabilities, or a sum-product decoder that provides bit error information. Thus, unlike conventional outer decoders, the outer decoder does not require a conventional first stage for determining errors in the output bit stream of the inner decoder based on the bits of the output bit stream themselves. A related transmitter uses a sum-product inner decoder in conjunction with an outer decoder.

Description:
RELATED APPLICATIONS  
       [0001]    This application claims the benefit under 35 U.S.C. Section 119(e) of United States Provisional Patent Application Serial No. 60/221,851, filed on Jul. 28, 2000, incorporated herein by reference in its entirety.  
         [0002]    This application incorporates by reference the entire teachings of: U.S. patent application Ser. No. 09/846,061 entitled “Use of turbo-like codes for QAM modulation using independent I and Q decoding techniques and application to xDSL systems”; U.S. Patent Application PCT/US99/17369 entitled “Method and apparatus for design forward error correction techniques in data transmission over communications systems”; and U.S. Provisional Patent Application Ser. No. 09/702,827 entitled “Use of Turbo Trellis codes with QAM modulation for xDSL modems and other wired and wireless modems.” 
     
    
     
       FIELD OF THE INVENTION  
         [0003]    Embodiments of the invention pertain to encoder structures comprising an inner encoder, such as a Trellis Code Modulation (TCM), Turbo Code (TC) or Low Density Parity Check (LDPC) coder, and an outer encoder such as a Reed-Solomon (RS) encoder or another outer encoder. Further embodiments pertain to a corresponding decoder structure comprising an inner decoder and an outer decoder.  
         BACKGROUND TECHNOLOGY  
         [0004]    Turbo codes and other receiver soft-decision extraction techniques such as Low Density Parity Check Codes (LDPC), are powerful error control techniques that allow communication at very close to the channel capacity. Low Density Parity Check Codes were introduced in 1962. The sum-product algorithm is commonly used to decode LDPC codes. The sum-product algorithm sends information forward and backward between the information bits and the parity bits iteratively, until all the bits are decoder correctly or some bits are indentified as incorrectly decoded. Consequently the sum-product algorithm provides bit error information that indicates which outputted decoded bits have errors.  
           [0005]    LDPC encoders and decoders are conventionally used alone, and are not conventionally used in dual inner/outer coder arrangements. The efficiency of LDPC coding increases with the number of coded bits, and so conventional LDPC implementations have typically used large block sizes (e.g. one megabit) for encoding in order to achieve nearly error free operation. However, since an entire block must be received before an LDPC decoder can decode the block, the use of large blocks can introduce significant delay into the system at the receiver.  
           [0006]    Turbo codes were introduced in 1993. Turbo-type decoders, referred to hereinafter as soft-output decoders, provide bit error probability information that indicates a probability of error for each of the decoded bits.  
           [0007]    The use of an outer coder, such as a Reed-Solomon (RS) coder, in conjunction with an inner coder, enables errors remaining from an inner coder to be corrected by the outer coder. A RS decoder is able to correct up to R/2 errors without having information of the location of the errors. A RS decoder is able to correct up to R errors if the decoder knows where the errors are located. It is therefore desirable for an outer coder to have information indicating where errors are located. Thus the conventional outer decoder comprises two stages. The first stage receives an output bit stream from an inner decoder and determines which of the received bits have errors. The second stage uses the information generated by the first stage to selectively correct errors in the output bit stream of the inner decoder.  
           [0008]    Examples of the use of inner and outer coders are found in the ADSL ITU recommendation G.992.1 and in the Third Mobile Generation Standard UMTS 3GPP 3G TS 25.212 V3.2.0.  
           [0009]    The following references are incorporated by reference as representing the conventional knowledge in the field of the invention:  
           [0010]    R. G. Gallager, “Low Density Parity-Check Codes”, IRE Trans. on Information Theory, pp. 21-Jan. 28 1962.  
           [0011]    C. Berrou, V. Glavieux and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: turbo-codes”, ICC 1993, Geneva, Switzerland, pp. 1064-1070, May 1993.  
           [0012]    H. Feldman and D. V. Ramana, “An introduction to Inmarsat&#39;s New Mobile Multimedia Service”, The Sixth International Mobile Satellite Conference, Ottawa, pp. 226-229, June 1999.  
           [0013]    P. Chaudhury, W. Mohr and S. Onoe, “The 3GPP Proposal for IMT-2000”, IEEE Communications Magazine, vol. 37, no 12, pp.72-81. December 1999.  
           [0014]    3GPP Standard “Multiplexing and channel coding: TS 25.212” 
           [0015]    C. D. Edwards, C. T. Stelzried, L. J. Deutsch and L. Swanson, “NASAS&#39;s deep-Space Telecommunications Road Map” TMO Progress Report 42-136, JPL, Pasadena, Calif. USA. PP. 1-20 February 1999.  
           [0016]    R. Pyndiah, A. Picard and A. Glavieux “Performance of Block Turbo Coded 16 QAM and 64 QAM modulations” Procedings of Globecom 95 pp. 1039-1043.  
           [0017]    Rauschmayer, Dennis J. “ADSLNVDSL Principles”, Macmillan Technical Publishing, 1999.  
           [0018]    ITU G.992.1 “ADSL Transceivers”, ITU, 1999.  
           [0019]    ITU G.992.2 “Splitterless ADSL Transceivers”. ITU 1999.  
           [0020]    ITU 1.432 “B-ISDN user-network interface-physical layer specification”, ITU, 1993.  
           [0021]    Benedetto, Divsalar, Montorsi and F. Pollara, “Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding”, The Telecommunications and Data Acquisition Progress Report 42-126, Jet Propulsion Laboratory, Pasadena, Calif., pp. 1-26, Aug. 15, 1996.  
           [0022]    Benedetto, Divsalar, Montorsi and F. Pollara, “A Soft-Output Maximum A Posteriori (MAP) Module to decode parallel and Serial Concatenated Codes”, The Telecommunications and Data Acquisition Progress Report 42-127, Jet Propulsion Laboratory, Pasadena, Calif., pp. 1-20, Nov. 15, 1996.  
           [0023]    L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, pp. 284-287, March 1974.  
           [0024]    Divsalar and F. Pollara, “Turbo Codes for PCS Applications”, Proceedings of ICC&#39;95, Seattle, Wash., pp. 54-59, June 1995.  
           [0025]    D. Divsalar and F. Pollara, “Multiple Turbo Codes”, Proceedings of IEEE MILCOM95, San Diego, Calif., Nov. 5-8, 1995.  
           [0026]    D. Divsalar and F. Pollara, “Soft-Output Decoding Algorithms in iterative Decoding of Turbo Codes,” The Telecommunications and Data Acquisition Progress Report 42-124, Jet Propulsion Laboratory, Pasadena, California, pp. 63-87, Feb. 15, 1995.  
         SUMMARY OF THE INVENTION  
         [0027]    Embodiments in accordance with the present invention are distinguished over conventional inner/outer coder schemes in that information regarding bit errors in the output of an inner decoder is provided by the inner decoder to the outer decoder, rather than being generated internally by the outer decoder. Thus, unlike conventional outer decoders, the outer decoder in accordance with preferred embodiments of the invention does not require a conventional first stage for determining errors in the output bit stream of the inner decoder based on the bits of the output bit stream themselves.  
           [0028]    In a first preferred embodiment, a soft-output inner decoder is utilized in a conventional manner to generate a bit stream from a received symbol stream and to generate a bit error probabilities for each bit of its output bit stream. This bit error probabilities and the output bit stream of the inner decoder are then provided to an outer decoder where errors in the output of the inner decoder are corrected in accordance with the bit error probabilities.  
           [0029]    In a second preferred embodiment, an LDPC coder is used as an inner encoder in a transmitter, and is used as an inner decoder in a receiver. Thus, unlike in conventional implementations, the LDPC coder is employed in an inner/outer coder scheme. In a receiver, the bit error information generated by the inner LDPC decoder is provided to an outer decoder where errors in the output of the inner LDPC decoder are corrected. Because a second stage of error correction is used, it becomes possible to reduce the block size utilized for the LDPC coding. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0030]    [0030]FIG. 1 shows elements of an ADSL transmitter and receiver that use inner and outer coders;  
         [0031]    [0031]FIG. 2 shows a Coding Scheme;  
         [0032]    [0032]FIG. 3 shows a SRC Scheme;  
         [0033]    [0033]FIG. 4 shows BER curves for use of a Turbo coder as an inner encoder for the rate 4/6 64 QAM scheme in accordance with an embodiment of the invention;  
         [0034]    [0034]FIG. 5 shows BER curves for use of a Turbo coder as an inner encoder for the rate 12/14 16384 QAM scheme in accordance with an embodiment of the invention;  
         [0035]    [0035]FIG. 6 shows a process in accordance with a first preferred embodiment,  
         [0036]    [0036]FIG. 7 shows a first process in accordance with a second preferred embodiment; and  
         [0037]    [0037]FIG. 8 shows a second process in accordance with a second preferred embodiment. 
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0038]    1. Introduction  
         [0039]    The preferred embodiments of the invention presented herein pertain to encoder structures having an inner encoder comprising a soft-output coding scheme, such as Trellis Code Modulation (TCM) or Turbo Code (TC), or a Low Density Parity Check (LDPC) coding scheme. An outer encoder in accordance with the preferred embodiments comprises a Reed-Solomon (RS) encoder. However, alternative embodiments may be implemented using other inner encoders that provide bit error or bit error probability information, and using other outer encoders that utilize bit error or bit error probability information.  
         [0040]    A first preferred embodiment exploits features of a Maximum a Posteriori (MAP) decoder used as an inner soft-output decoder. The MAP decoder provides as output a bit stream and an error probability of each bit of the bit stream (referred to herein as bit error probability information). The bit error probability information is used in the outer decoder to facilitate greater error recovery in the outer decoder (in the case of RS codes this error recovery is doubled). This scheme is contrasted with conventional implementations such as conventional xDSL modems that employ an inner decoder for TCM that uses a Viterbi decoder. This provides only hard decisions as to the value of each output bit and outputs no probability or error information that can be used in the outer RS decoder.  
         [0041]    For purposes of comparison, the preferred embodiments of the invention will be illustrated in the context an Asymmetric Digital Subscriber Line (ADSL) system using an outer encoder and an inner encoder.  
         [0042]    2. System Model  
         [0043]    [0043]FIG. 1 shows a system model of a communication system comprising transmitting and receiving ADSL modems, such as is described in the Recommendation G.992.1 of the ITU. The system uses two dimensional multi-level signals for the inner encoder, as QAM. The transmitting modem  20  comprises a Reed-Solomon outer encoder  1 , a byte interleaver  2 , and an inner encoder  3  that produce an encoded bit stream from an input information bit stream. A signal-space mapper  4  maps the bit stream to symbols of a symbol constellation, and an inverse discrete Fourier transform module  5  modulates the symbols for transmission through a communication channel  6 . In the receiving modem  30 , a discrete Fourier transform module  7  receives the modulated signal from the communication channel  6  and converts it to a received bit stream. The receiving modem further comprises an inner decoder  8 , a byte de-interleaver  9 , and a Reed-Solomon outer decoder  10 . The output of the outer decoder  10  is a reconstructed information bit stream.  
         [0044]    3. Reed-Solomon (RS) Encoder  
         [0045]    The RS outer encoder  1  of FIG. 1 is used very often to correct burst-errors in communication channels, such as telephone lines, deep-space communications, satellite communications, mobile communications, and CD players. The characteristic of an RS code is that it can correct up to R/2 symbols, where R is the number of check symbols used by the RS encoder.  
         [0046]    R, the number of redundant check bytes c 0 , c 1 , . . . , c R−2 , c R−1  shall be appended to K information bytes m 0 , m 1 , . . . , m K−2 , m K−1  to form a RS codeword of size N=K+R bytes. The check bytes are computed from the message byte using the equation:  
           C ( D )= M ( D ) D   R  mod  G ( D )   (1)  
         [0047]    where:  
           M ( D )= m   0   D   K−1   +m   1   D   K−2   + . . . +m   K−2   D+m   K−1    (2)  
         [0048]    is the message polynomial,  
           C ( D )= c   0   D   R−1   +c   1   D   R−2   + . . . +c   R−2   D+c   R−1    (3)  
         [0049]    is the check polynomial, and  
               G        (   D   )       =       ∏     i   =   0       R   -   1                       (     D   -     α   i       )               (   4   )                               
 
         [0050]    is the generator polynomial of the Reed-Solomon code, where the index of the product runs from i=0 to R−1. That is, C(D) is the remainder obtained from dividing M(D) DR by G(D). The arithmetic is performed in the Galois Field GF(256), where α is a primitive element that satisfies the primitive binary polynomial x 8 +x 4 +x 3 +x 2 +1 A data byte (d 7 , d 6 , . . . , d 1 , d 0 ) is identified with the Galois Field element d 7 α 7 +d 6 α 6 + . . . +d 1 α+d 0    
         [0051]    With this definition RS is able to correct up to R/2 symbols. If there are more than R/2 symbols with errors, RS will not be able to correct any of them. Because of this characteristic of RS, a high value for R is used, to make sure that the system is working error- free (assuming impulse noise of duration inferior to 0.5 ms).  
         [0052]    The values of the redundancy to work error free are around 10-15%.  
         [0053]    To improve the performance of the RS outer encoder, a byte interleaver 2 is used as indicated in FIG. 1.  
         [0054]    3. The Soft-Inner Encoder-Decoder  
         [0055]    In accordance with the first preferred embodiment, the inner encoder  3  of FIG. 1 is a TC. Two examples are provided herein addressing the cases of 64 QAM and 16384 QAM modulations to show how information about the probability of each symbol can be use to improve the performance of a RS outer encoder. The signal-space mapper  4  of FIG. 1 in these cases provides independent I&amp;Q QAM Gray mapping.  
         [0056]    3.1. Description of the Method for Implementation  
         [0057]    3.1.1 Capacity Bounds  
         [0058]    The minimum E b /N 0  values to achieve the Shannon bound 64 QAM and 16384 QAM bounds for spectral efficiencies of 4 and 12 bits/s/Hz respectively are as in Table 1 for a BER=10 −5 .  
                             TABLE 1                           Shannon bounds.                Spectral efficiency n   Shannon bound           [bit/s/Hz]   Eb/No [dB]                        4    5.6           12   24.7                      
 
         [0059]    The conversion from SNR of the QAM signal to E b /N 0  is performed using the following relation:  
           E   b   /N   0   [dB]=SNR[dB]− 10 log 10 (η) [ dB ]  (5)  
         [0060]    where η is the number of information bits per symbol.  
         [0061]    For a D-dimension modulation the following formulae are used:  
             SNR   =         E        [          a   k   2          ]         E        [          w   k   2          ]         =         E        [          a   k   2          ]         D                   σ   N   2         =       E   av       D                   σ   N   2                     (   6   )               SNR   =         E   s       D          N   0     2         =       η                   E   b         D          N   0     2                   (   7   )                               
 
         [0062]    where σ 2   N  is the noise variance in each of the D dimension and η is the number of information bits per symbol. From the above relations:  
               σ   N   2     =         E   av          (       2      η                   E   b         N   0       )         -   1               (   8   )                               
 
         [0063]    3.1.2 Coding  
         [0064]    The coding scheme is shown in FIG. 2. The two systematic recursive codes (SRC) used are identical and are defined in FIG. 3. The code is described by the generating polynomials  35   o  and  23   o.    
         [0065]    3.1.3 Turbo Code Internal Interleaver  
         [0066]    The interleaver of this embodiment is an LRI interleaver. The interleaving sequence of the LRI is as follows:  
                                             [0053] Determination of the interleaving buffer size.                                    M:   Number of column in the interleaving buffer (M &gt; 16).           N:   Number of rows in the interleaving buffer (N &gt; 16).           BL:   Interleaving block size (BL = P × P &gt;= M × N).           P:   Minimum prime number that is larger than M.           v:   Minimum primitive root of P.                      
 
         [0067]    Making Basic Random Set Whose Length is M  
           C (0)=1 ; C ( i +1)= vxC ( i )mod  P, i= 0,1, . . .  P− 3   (9)  
         [0068]    Making j-th Inter-row Permutation Pattern  
         [0069]    By shifting output of step 2 one by one per inter-row, a Latin square matrix is made. The last (M−1)th column is processed specially in order to avoid low hamming weight phenomenon caused by the forced termination.  
           CLj ( i )= C ( j+i mod M− 1);  CLj ( M− 1)=0 ; i= 0,1, . . .  M− 2 ; j= 0,1, . . . , N− 1   (10)  
         [0070]    Row by Row 2D-Mapping of di to M×N Buffer  
           d*j  ( i )= i+Mxj , i= 0, 1, . . . , M− 2 ;  j= 0,1, . . . ,  N− 1   (11)  
         [0071]    Permutating of 2D-Mapped Input Set di by the Permutation Pattern made in Point 3  
           d**j ( i )= d* ( N−j ) ( CL ) N−j ) ( i )),,  i= 0,1, . . . ,  M− 1 ;j= 0,1, . . . ,  N− 1   (12)  
         [0072]    Reading a Permuted Input Set Column by Column, and Making Output Set  
           d ′( j+Nxi )= d**j ( i ),  i= 0,1, . . . ,  M− 1 ;j= 0,1, . . . ,  N− 1   (13)  
         [0073]    Pruning Bits  
         [0074]    d′ is pruned by deleting the 1-bits in order to adjust the output d′ to the input block length BL, where the deleted bits are non-existent bits in the input sequence. The pruning number L is defined as L=M×N−BL.  
         [0075]    3.1.4. Coding And Modulation For 4 Bit/S/Hz Spectral Efficiency  
         [0076]    3.1.4.1 Puncturing  
         [0077]    In order to obtain a rate 4/6 code, the puncturing pattern used is shown in Table 2.  
                                                       TABLE 2                       Puncturing and Mapping for Rate 4/6 64 QAM                                    Information bit (d)   d 1     d 2     d 3     d 4             parity bit (p)   p 1     —   —   —           parity bit (q)   —   —   q 3     —                8AM symbol (I)   (d 1 , d 2 , p 1 )           8AM symbol (Q)   (d 3 , d 4 , q 3 )           64 QAM symbol (I, Q)   (I,Q) = (d 1 ,d 2 ,p 1 ,d 3 ,d 4 ,q 3 )                      
 
         [0078]    3.1.4.2 Modulation  
         [0079]    In this embodiment Gray mapping is used in each dimension. Four information bits are required to be sent using a 64 QAM constellation. For a rate 4/6 code and 64 QAM, the noise variance in each dimension is  
           E   av =(8(49+25+9+1+25+49+49+9+49+1+25+9+25+1+9+1)) A   2 /64=42 A   2    (14)  
         [0080]    [0080]               σ   N   2     =           E   av          (       2      η                   E   b         N   0       )         -   1       =       42                       A   2          (       2   ×   4   ×     E   b         N   0       )         -   1         =     5.25                       A   2          (       E   b       N   0       )         -   1                     (   15   )                                 
         [0081]    The puncturing and mapping scheme is shown in Table 2 for 4 consecutive information bits that are encoded into 6 coded bits, therefore one 64 QAM symbol. The turbo encoder with the puncturing presented in Table 2 is a rate 4/6 turbo code which in conjunction with 64 QAM gives a spectral efficiency of 4 bits/s/Hz. Considering two independent Gaussian noises with identical variance σ 2   N , the LLR can be determined independently for each I and Q. It is assumed that at time k u 1   k , u 2   k  and u 3   k  modulate the I component and u 4   k , u 5   k  and u 6   k  modulate the Q component of the 64 QAM scheme. At the receiver, the I and Q signals are treated independently in order to take advantage of the simpler formulae for the LLR values.  
         [0082]    3.1.4.3 Bit Probabilities  
         [0083]    From each received symbol, the bit probabilities for the three I dimension bits are computed as follows:  
                     LLR        (     u   1   k     )       =                  log        (         ∑     i   =   1     4                     exp        [       -     1     2        σ   N   2                  (       I   k     -     a     1   ,   i     k       )     2       ]             ∑     i   =   1     4                     exp        [       -     1     2        σ   N   2                  (       I   k     -     a     0   ,   i     k       )     2       ]           )       =                 =                log        (               exp        [       -     1     2        σ   N   2                  (       I   k     -     A   4       )     2       ]       +     exp        [       -     1     2        σ   N   2                  (       I   k     -     A   5       )     2       ]       +                 exp        [       -     1     2        σ   N   2                  (       I   k     -     A   6       )     2       ]       +     exp        [       -     1     2        σ   n   2                  (       I   k     -     A   7       )     2       ]                         exp        [       -     1     2        σ   N   2                  (       I   k     -     A   0       )     2       ]       +     exp        [       -     1     2        σ   N   2                  (       I   k     -     A   1       )     2       ]       +                 exp        [       -     1     2        σ   N   2                  (       I   k     -     A   2       )     2       ]       +     exp        [       -     1     2        σ   n   2                  (       I   k     -     A   3       )     2       ]                 )                     (   16   )                       LLR        (     u   2   k     )       =                  log        (         ∑     i   =   1     4                     exp        [       -     1     2        σ   N   2                  (       I   k     -     a     1   ,   i     k       )     2       ]             ∑     i   =   1     4                     exp        [       -     1     2        σ   N   2                  (       I   k     -     a     0   ,   i     k       )     2       ]           )       =                 =                log        (               exp        [       -     1     2        σ   N   2                  (       I   k     -     A   2       )     2       ]       +     exp        [       -     1     2        σ   N   2                  (       I   k     -     A   3       )     2       ]       +                 exp        [       -     1     2        σ   N   2                  (       I   k     -     A   6       )     2       ]       +     exp        [       -     1     2        σ   n   2                  (       I   k     -     A   7       )     2       ]                         exp        [       -     1     2        σ   N   2                  (       I   k     -     A   0       )     2       ]       +     exp        [       -     1     2        σ   N   2                  (       I   k     -     A   1       )     2       ]       +                 exp        [       -     1     2        σ   N   2                  (       I   k     -     A   4       )     2       ]       +     exp        [       -     1     2        σ   n   2                  (       I   k     -     A   5       )     2       ]                 )                     (   17   )                       LLR        (     u   3   k     )       =                  log        (         ∑     i   =   1     4                     exp        [       -     1     2        σ   N   2                  (       I   k     -     a     1   ,   i     k       )     2       ]             ∑     i   =   1     4                     exp        [       -     1     2        σ   N   2                  (       I   k     -     a     0   ,   i     k       )     2       ]           )       =                 =                log        (               exp        [       -     1     2        σ   N   2                  (       I   k     -     A   1       )     2       ]       +     exp        [       -     1     2        σ   N   2                  (       I   k     -     A   5       )     2       ]       +                 exp        [       -     1     2        σ   N   2                  (       I   k     -     A   3       )     2       ]       +     exp        [       -     1     2        σ   n   2                  (       I   k     -     A   7       )     2       ]                         exp        [       -     1     2        σ   N   2                  (       I   k     -     A   0       )     2       ]       +     exp        [       -     1     2        σ   N   2                  (       I   k     -     A   4       )     2       ]       +                 exp        [       -     1     2        σ   N   2                  (       I   k     -     A   2       )     2       ]       +     exp        [       -     1     2        σ   n   2                  (       I   k     -     A   6       )     2       ]                 )                     (   18   )                               
 
         [0084]    An analogous computation effort is required for the bits of the Q dimension, the I k  being replaced with the Q k  demodulated value in order to evaluate LLR(u 4   k ), LLR(u 5   k ) and LLR(u 6   k ).  
         [0085]    The bit error probabilities are provided to the outer decoder where they are used by the outer decoder to detect the location of the erroneous bits and to selectively correct the erroneous bits.  
         [0086]    As discussed above, conventional outer decoders comprise a first stage that determines bit error information from the output bits of the inner decoder themselves, and a second stage that corrects bits in accordance with the bit error information. In accordance with the first preferred embodiment of the present invention, the first stage of the conventional outer decoder is replaced with a stage that generates a hard bit error decision for each bit using externally provided bit error probability information, such as by a thresholding procedure, and provides the bit error information to a second stage, such a conventional second stage, where bit errors are corrected in accordance with the bit error information. Those of ordinary skill in the art will be capable of modifying any of the conventional outer decoders of this type to accept externally generated bit error probability information and generated bit error information therefrom for use in the second stage of the decoder. Therefore no further detailed discussion of the outer decoder is provided here apart from the discussion in section 5 below.  
         [0087]    3.1.4.4 Simulation Results  
         [0088]    [0088]FIG. 4 shows simulation results for 10,400 information bits with an S-type interleaver. A BER of 10 −7  can be achieved after 8 iterations at E b /N 0 =8.3 dB.  
         [0089]    3.1.5 Coding And Modulation For 12 Bit/S/Hz Spectral Efficiency  
         [0090]    A second example in accordance with the first preferred embodiment utilizes a rate 12/14 coding scheme with 16384 QAM.  
         [0091]    3.1.5.1 Puncturing  
         [0092]    In order to obtain a rate 12/14 code, a puncturing pattern as shown in Table 3 is used.  
                                                                               TABLE 3                       Puncturing and Mapping for Rate 12/14 16384 QAM                                Information   d 1     d 2     d 3     d 4     d 5     d 6     d 7     d 8     d 9     d 10     d 11     d 12         bit (d)       parity bit (p)   p 1         parity bit (q)                           q 7              128AM   (d 1 , d 2 , d 3 , d 4 d 5 , d 6 , p 1 )       symbol (I)       128AM   (d 7 , d 8 , d 9 , d 10 , d 11 , d 12 , p 7 )       symbol (Q)       16384 QAM   (d 1 , d 2 , d 3 , d 4 d 5 , d 6 , p 1 , d 7 , d 8 , d 9 , d 10 , d 11 , d 12 , p 7 )       symbol (I, Q)                  
 
         [0093]    3.1.5.2 Modulation  
         [0094]    For a 16384 QAM constellation with points at -127A, -125A, -123A, -121A, -119A, -117A, -115A, -113A, -111A, -109A, -107A, -105A, -103A, -101A, -99A, -97A, -95A, -93A, -91A, -89A, -87A, -85A, -83A, -81A, -79A, -77A, -75A, -73A, -71A, -69A, -67A, -65A, -63A, -61A, -59A, -57A, -55A, -53A, -51A, -49A, -47A, -45A, -43A, -41A, -39A, -37A, - 35A, -33A, -31A, -29A, -27A, -25A, -23A, -21A, -19A, -17A, -15A, -13A, -11A, -9A, -7A, -5A, -3A, -A, A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, 17A, 19A, 21A, 23A, 25A, 27A, 29A, 31A, 33A, 35A, 37A, 39A, 41A, 43A, 45A, 47A, 49A, 51A, 53A, 55A, 57A, 59A, 61A, 63A, 65A, 67A, 69A, 71A, 73A, 75A, 77A, 79A, 81A, 83A, 95A, 87A, 89A, 91A, 93A, 95A, 97A, 99A, 101A, 103A, 105A, 107A, 109A, 111A, 113A, 115A, 117A, 119A, 121A, 123A, 125A, 127A, E av  is:  
         E av =5461A 2    (19)  
         [0095]    It is assumed that at time k the symbol u k =(u 1   k , u 2   k , u 3   k , u 4   k , u 5   k , u 6   k , u 7   k , u 8   k , u 9   k , u 10   k , u 11   k , u 12   k , u 13   k , u 14   k ) is sent though the channel. It is assumed that at time k the symbol u 1   k , u 2   k , u 3   k , u 4   k , u 5   k , u 6   k  and u 7   k  modulate the I component and u 8   k , u 9   k , u 10   k , u 11   k , u 12   k , u 13   k  and u 14   k  modulate the Q component of a 16384 QAM scheme.  
         [0096]    For a rate 12/14 code and 16384 QAM, the noise variance is:  
               σ   N   2     =           E   av          (       2      η                   E   b         N   0       )         -   1       =       5461                       A   2          (       2   ×   6   ×     E   b         N   0       )         -   1         =     455.08                       A   2          (       E   b       N   0       )         -   1                     (   20   )                               
 
         [0097]    In order to study the performance of this scheme, a rate 6/7 turbo code and a 128AM is used. The 16384 QAM scheme will achieve a similar performance in terms of bit error rate (BER) at twice the spectral efficiency, assuming an ideal demodulator. The puncturing and mapping scheme shown in Table 8 is for 12 consecutive information bits that are coded into 14 encoded bits, therefore, one 16384 QAM symbol. The turbo encoder is a rate 12/14 turbo code, which in conjunction with 16384 QAM, gives a spectral efficiency of 12 bits/s/Hz.  
         [0098]    3.1.5.3 Bit Probabilities  
         [0099]    The 128AM symbol is defined as u k =(u 1   k , u 2   k , u 3   k , u 4   k , u 5   k , u 6   k k, u 7   k ), where u 1   k  is the most significant bit and u 7   k  is the least significant bit. The following set can be defined.  
         [0100]    bit- 1 -is-0={A 0 , A 1 , A 3 , A 4 , A 5 , A 6 , A 7 , A 8 , A 9 , A 10 , A 11 , A 12 , A 13 , A 14 , A 15 , A 16 , A 17 , A 18 , A 19 , A 20 , A 21 , A 22 , A 23 , A 24 , A 25 , A 26 , A 27 , A 28 , A 29 , A 30 , A 31 , A 32 , A 33 , A 34 , A 35 , A 36 , A 37 , A 38 , A 39 , A 40 , A 41 , A 42 , A 43 , A 44 , A 45 , A 46 , A 47 , A 48 , A 49 , A 50 , A 51 , A 52 , A 53 , A 54 , A 55 , A 56 , A 57 , A 58 , A 59 , A 60 , A 61 , A 62 , A 63 } 
         [0101]    bit- 1 -is-1={A 64 , A 65 , A 66 , A 67 , A 68 , A 69 , A 70 , A 71 , A 72 , A 73 , A 74 , A 75 , A 76 , A 77 , A 78 , A 79 , A 80 , A 81 , A 82 , A 83 , A 84 , A 85 , A 86 , A 87 , A 88 , A 89 , A 90 , A 91 , A 92 , A 93 , A 94 , A 95 , A 96 , A 97 , A 98 , A 99 , A 100 , A 101 , A 102 , A 103 , A 104 , A 105 , A 106 , A 107 , A 108 , A 109 , A 110 , A 111 , A 112 , A 113 , A 114 , A 115 , A 116 , A 117 , A 118 , A 119 , A 120 , A 121 , A 122 , A 123 , A 124 , A 125 , A 126 , A 127 } 
         [0102]    bit-2-is-0={A 0 , A 1 , A 2 , A 3 , A 4 , A 5 , A 6 , A 7 , A 8 , A 9 , A 10 , A 11 , A 12 , A 13 , A 14 , A 15 , A 16 , A 17 , A 18 , A 19 , A 20 , A 21 , A 22 , A 23 , A 24 , A 25 , A 26 , A 27 , A 28 , A 29 , A 30 , A 31 , A 96 , A 97 , A 98 , A 99 , A 100 , A 101 , A 102 , A 103 , A 104 , A 105 , A 106 , A 107 , A 108 , A 109 , A 110 , A 111 , A 112 , A 113 , A 114 , A 115 , A 116 , A 117 , A 118 , A 119 , A 120 , A 121 , A 122 , A 123 , A 124 , A 125 , A 126 , A 127 } 
         [0103]    bit-2-is-1={A 32 , A 33 , A 34 , A 35 , A 36 , A 37 , A 38 , A 39 , A 40 , A 41 , A 42 , A 43 , A 44 , A 45 , A 46 , A 47 , A 48 , A 49 , A 50 , A 51 , A 52 , A 53 , A 54 , A 55 , A 56 , A 57 , A 58 , A 59 , A 60 , A 61 , A 62 , A 63 , A 64 , A 65 , A 66 , A 67 , A 68 , A 69 , A 70 , A 71 , A 72 , A 73 , A 74 , A 75 , A 76 , A 77 , A 78 , A 79 , A 80 , A 81 , A 82 , A 83 , A 84 , A 85 , A 86 , A 87 , A 88 , A 89 , A 90 , A 91 , A 92 , A 93 , A 94 , A 95 } 
         [0104]    bit-3-is-0={A 0 , A 1 , A 2 , A 3 , A 4 , A 5 , A 6 , A 7 , A 8 , A 9 , A 10 , A 11 , A 12 , A 13 , A 14 , A 15 , A 48 , A 49 , A 50 , A 51 , A 52 , A 53 , A 54 , A 55 , A 56 , A 57 , A 58 , A 59 , A 60 , A 61 , A 62 , A 63 , A 64 , A 65 , A 66 , A 67 , A 68 , A 69 , A 70 , A 71 , A 72 , A 73 , A 74 , A 75 , A 76 , A 77 , A 78 , A 79 , A 112 , A 113 , A 114 , A 115 , A 116 , A 117 , A 118 , A 119 , A 120 , A 121 , A 122 , A 123 , A 124 , A 125 , A 126 , A 127 } 
         [0105]    bit-3-is-1={A 16 , A 17 , A 18 , A 19 , A 20 , A 21 , A 22 , A 23 , A 24 , A 25 , A 26 , A 27 , A 28 , A 29 , A 30 , A 31 , A 32 , A 33 , A 34 , A 35 , A 36 , A 37 , A 38 , A 39 , A 40 , A 41 , A 42 , A 43 , A 44 , A 45 , A 46 , A 47 , A 80 , A 81 , A 82 , A 83 , A 84 , A 85 , A 86 , A 87 , A 88 , A 89 , A 90 , A 91 , A 92 , A 93 , A 94 , A 95 , A 96 , A 97 , A 98 , A 99 , A 100 , A 101 , A 102 , A 103 , A 104 , A 105 , A 106 , A 107 , A 108 , A 109 , A 110 , A 111 } 
         [0106]    bit-4-is-0={A 0 , A 1 , A 2 , A 3 , A 4 , A 5 , A 6 , A 7 , A 24 , A 25 , A 26 , A 27 , A 28 , A 29 , A 30 , A 31 , A 32 , A 33 , A 34 , A 35 , A 36 , A 37 , A 38 , A 39 , A 56 , A 57 , A 58 , A 59 , A 60 , A 61 , A 62 , A 63 , A 64 , A 65 , A 66 , A 67 , A 68 , A 69 , A 70 , A 71 , A 88 , A 89 , A 90 , A 91 , A 92 , A 93 , A 94 , A 95 , A 96 , A 97 , A 98 , A 99 , A 100 , A 101 , A 102 , A 103 , A 120 , A 121 , A 122 , A 123 , A 124 , A 125 , A 126 , A 127 } 
         [0107]    bit-4-is-1={A 8 , A 9 , A 10 , A 11 , A 12 , A 13 , A 14 , A 15 , A 16 , A 17 , A 18 , A 19 , A 20 , A 21 , A 22 , A 23 , A 40 , A 41 , A 42 , A 43 , A 44 , A 45 , A 46 , A 47 , A 48 , A 49 , A 50 , A 51 , A 52 , A 53 , A 54 , A 55 , A 72 , A 73 , A 74 , A 75 , A 76 , A 77 , A 78 , A 79 , A 80 , A 81 , A 82 , A 83 , A 84 , A 85 , A 86 , A 87 , A 104 , A 105 , A 106 , A 107 , A 108 , A 109 , A 110 , A 111 , A 112 , A 113 , A 114 , A 115 , A 116 , A 117 , A 118 , A 119 ,} 
         [0108]    bit-5-is-0={A 0 , A 1 , A 2 , A 3 , A 12 , A 13 , A 14 , A 15 , A 16 , A 17 , A 18 , A 19 , A 28 , A 29 , A 30 , A 31 , A 32 , A 33 , A 34 , A 35 , A 44 , A 45 , A 46 , A 47 , A 48 , A 49 , A 50 , A 51 ,, A 60 , A 61 , A 62 , A 63 , A 64 , A 65 , A 66 , A 67 , A 76 , A 77 , A 78 , A 79 , A 80 , A 81 , A 82 , A 83 , A 92 , A 93 , A 94 , A 95 , A 96 , A 97 , A 98 , A 99 , A 108 , A 109 , A 110 , A 111 , A 112 , A 113 , A 114 , A 115 , A 124 , A 125 , A 126 , A 127 } 
         [0109]    bit-5-is-1={A 4 , A 5 , A 6 , A 7 , A 8 , A 9 , A 10 , A 11 , A 20 , A 2 , A 22 , A 23 , A 24 , A 25 , A 26 , A 27 , A 36 , A 37 , A 38 , A 39 , A 40 , A 41 , A 42 , A 43 , A 52 , A 53 , A 54 , A 55 , A 56 , A 57 , A 58 , A 59 , A 68 , A 69 , A 70 , A 71 , A 72 , A 73 , A 74 , A 75 , A 84 , A 85 , A 86 , A 87 , A 88 , A 89 , A 90 , A 91 , A 100 , A 101 , A 102 , A 103 , A 104 , A 105 , A 106 , A 107 , A 116 , A 117 , A 118 , A 119 , A 120 , A 121 , A 122 , A 123 } 
         [0110]    bit-6-is-0={A 2 , A 3 , A 4 , A 5 , A 10 , A 11 , A 12 , A 13 , A 18 , A 19 , A 20 , A 21 , A 26 , A 27 , A 28 , A 29 , A 34 , A 35 , A 36 , A 37 , A 42 , A 43, , A 45 , A 50 , A 51 , A 52 , A 53 , A 58 , A 59 , A 60 , A 61 , A 66 , A 67 , A 68 , A 69 , A 74 , A 75 , A 76 , A 77 , A 82 , A 83 , A 84 , A 85 , A 90 , A 91 , A 92 , A 93 , A 98 , A 99 , A 100 , A 101 , A 106 , A 107 , A 108 , A 109 , A 114 , A 115 , A 116 , A 117 , A 122 , A 123 , A 124 , A 125 } 
         [0111]    bit-6-is-1={A 0 , A 1 , A 6 , A 7 , A 8 , A 9 , A 14 , A 15 , A 16 , A 17 , A 22 , A 23 , A 24 , A 25 , A 30 , A 31 , A 32 , A 33 , A 38 , A 39 , A 40 , A 41 , A 46 , A 47 , A 48 , A 49 , A 54 , A 55 , A 56 , A 57 , A 62 , A 63 , A 64 , A 65 , A 70 , A 71 , A 72 , A 73 , A 78 , A 79 , A 80 , A 81 , A 86 , A 87 , A 88 , A 89 , A 94 , A 95 , A 96 , A 97 , A 102 , A 103 , A 104 , A 105 , A 110 , A 112 , A 113 , A 118 , A 119 , A 120 , A 121 , A 126 , A 127 } 
         [0112]    bit-7-is-0={A 0 , A 3 , A 4 , A 7 , A 8 , A 11 , A 12 , A 15 , A 16 , A 19 , A 20 , A 23 , A 24 , A 27 , A 28 , A 31 , A 32 , A 35 , A 36 , A 39 , A 40 , A 43 , A 47 , A 48 , A 51 , A 52 , A 55 , A 56 , A 59 , A 60 , A 63 , A 64 , A 67 , A 68 , A 71 , A 72 , A 75 , A 76 , A 79 , A 80 , A 83 , A 84 , A 87 , A 88 , A 92 , A 95 , A 96 , A 99 , A 100 , A 103 , A 104 , A 107 , A 108 , A 111 , A 112 , A 115 , A 116 , A 119 , A 120 , A 123 , A 124 , A 127 } 
         [0113]    bit-7-is-1={A 1 , A 2 , A 5 , A 6 , A 9 , A 10 , A 13 , A 14 , A 17 , A 18 , A 21 , A 22 , A 25 , A 26 , A 29 , A 30 , A 33 , A 34 , A 37 , A 38 , A 41 , A 42 , A 45 , A 46 , A 49 , A 50 , A 53 , A 54 , A 57 , A 58 , A 61 , A 62 , A 65 , A 66 , A 69 , A 70 , A 73 , A 74 , A 77 , A 78 , A 81 , A 82 , A 85 , A 86 , A 89 , A 90 , A 93 , A 94 , A 97 , A 98 , A 101 , A 102 , A 105 , A 106 , A 109 , A 110 , A 113 , A 114 , A 117 , A 118 , A 121 , A 122 , A 125 , A 126 } 
         [0114]    From each received symbol, R k , the bit probabilities are computed as follows:  
               LLR        (     u   1   k     )       =     log        (         ∑       A   i     ∈                bit        -        1        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   i                      )             ∑       A   j     ∈                bit        -        1        -        is        -        0              exp        (         -     1     2        σ   N   2                             R   k       -       A   j                      )           )               (   21   )                 LLR        (     u   2   k     )       =     log        (         ∑       A   i     ∈                bit        -        2        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   i                      )             ∑       A   j     ∈                bit        -        2        -        is        -        0              exp        (         -     1     2        σ   N   2                             R   k       -       A   j                      )           )               (   22   )                 LLR        (     u   3   k     )       =     log        (         ∑       A   i     ∈                bit        -        3        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   i                      )             ∑       A   j     ∈                bit        -        3        -        is        -        0              exp        (         -     1     2        σ   N   2                             R   k       -       A   j                      )           )               (   23   )                 LLR        (     u   4   k     )       =     log        (         ∑       A   i     ∈                bit        -        4        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   i                      )             ∑       A   j     ∈                bit        -        4        -        is        -        0              exp        (         -     1     2        σ   N   2                             R   k       -       A   j                      )           )               (   24   )                 LLR        (     u   5   k     )       =     log        (         ∑       A   i     ∈                bit        -        5        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   i                      )             ∑       A   j     ∈                bit        -        5        -        is        -        0              exp        (         -     1     2        σ   N   2                             R   k       -       A   j                      )           )               (   25   )                 LLR        (     u   6   k     )       =     log        (         ∑       A   i     ∈                bit        -        6        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   i                      )             ∑       A   j     ∈                bit        -        6        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   j                      )           )               (   26   )                 LLR        (     u   7   k     )       =     log        (         ∑       A   i     ∈                bit        -        7        -        is        -        1              exp        (         -     1     2        σ   N   2                             R   k       -       A   i                      )             ∑       A   j     ∈                bit        -        7        -        is        -        0              exp        (         -     1     2        σ   N   2                             R   k       -       A   j                      )           )               (   27   )                               
 
         [0115]    An analogous computation effort is required for the bits of the Q dimension, the I k  being replaced with the Q k  demodulated value i order to evaluate LLR(u 8   k ), LLR(u 9   k ), LLR(u 10   k ), LLR(u 11   k ), LLR(u 12   k ), LLR(u 13   k ) and LLR(u 14   k ).  
         [0116]    The bit error probabilities are provided to the outer decoder where they are used by the outer decoder to generate bit error information indicating the location of the erroneous bits and to selectively correct the erroneous bits.  
         [0117]    As discussed above, conventional outer decoders comprise a first stage that determines bit error information from the output bits of the inner decoder themselves, and a second stage that corrects bits in accordance with the bit error information. In accordance with the first preferred embodiment of the present invention, the first stage of the conventional outer decoder is replaced with a stage that generates a hard bit error decision for each bit using externally provided bit error probability information, such as by a thresholding procedure, and provides the bit error information to a second stage, such a conventional second stage, where bit errors are corrected in accordance with the bit error information. Those of ordinary skill in the art will be capable of modifying any of the conventional outer decoders of this type to accept externally generated bit error probability information and generated bit error information therefrom for use in the second stage of the decoder. Therefore no further detailed discussion of the outer decoder is provided here apart from the discussion in section 5 below.  
         [0118]    These probabilities are used by the outer decoder to detect the location of the erroneous bits.  
         [0119]    3.1.5.4 Simulation Results  
         [0120]    [0120]FIG. 5 shows the simulation results for 31200 information bits. A BER of 10 −7  can be achieved after 8 iterations at E b /N 0 =28.25 dB.  
         [0121]    4. IDFT use for ADSL Systems  
         [0122]    After the mapper, the signal is sent to the IDFT, shown as  5  in FIG. 1 and to the channel, shown as  6  in FIG. 1.  
         [0123]    5. Use of the Information by the Reed-Solomon Outer Decoder  
         [0124]    The received signal is sent to the DFT block,  7  in FIG. 1, and to the inner decoder  7  in FIG. 1.  
         [0125]    The probabilities in equations (16), (17) and (18) for the case of 4 bit/s/Hz and the probabilities of equations (21), (22), (23), (24), (25), (26) and (27) for the case of 12 bit/s/Hz are used for the RS decoder, shown as  9  in FIG. 1, in the following way:  
         [0126]    The reliability of the received data is determined with the reliability of the MAP decoder. These data and associated bit error probabilities are carried through the deinterleaver placed between the inner decoder and the outer decoder. The Reed-Solomon uses as indication of error placement the worst of the bit error probabilities. Note that the MAP decoder may assign poor probabilities to all data associated with a frame.  
         [0127]    While the first preferred embodiment utilizes turbo coding for the inner encoder and RS for the outer decoder, it will of course work with any soft-output inner encoder that provides bit error probabilities and outer encoders that utilize bit error probability information. This include turbo code base Maximum a Posteriori (MAP), Logarithmic MAP (LOGMAP), Maximum LAGMAP (MAXLOGMAP), soft-output Viterbi Algorithm (SOVA), Turbo Block Codes, as well as inner encoder using a single convolutional code as such trellis encoding of G.992.1 and G.992.2. It is recognized that the use of soft-output decoders on this non-turbo encoder will also give the same benefit. The significant point to recognize is the use of the inner soft-output decoder and that the outer decoder can take advantage of this information.  
         [0128]    Accordingly, in accordance with the first preferred embodiment, there is a process for decoding a symbol stream with forward error correction to produce an information bit stream. This process is illustrated in FIG. 6. A symbol stream is received  60  from a o transmitter. The symbol stream is decoded  62  in an inner decoder using soft-output decoding to provide an output bit stream and associated bit error probabilities. The bit error probabilities and the output bit stream are provided  64  to an outer decoder, and the outer decoder produces  66  an information bit stream from the output bit stream using the bit error probabilities.  
         [0129]    6. Second Preferred Embodiment using Inner Sum-Product Coding  
         [0130]    In a second preferred embodiment, a sum-product algorithm inner encoder and decoder, such as LDPC coders, are used in a transmitter and receiver, respectively. The second preferred embodiment differs from the first preferred embodiment in that the sum- product inner decoder provides bit error information for its output bit stream, i.e. information indicating the position of each erroneous bit that requires correction by the outer decoder. The bit error information is provided to the outer decoder and used to select bits from the inner decoder output stream for correction in the outer decoder. This embodiment is preferred for its simplicity of implementation.  
         [0131]    Accordingly, in accordance with the second preferred embodiment, there is a process in a transmitter for encoding a symbol stream with forward error correction from an information bit stream. As shown in FIG. 7, an information bit stream is received  70  and is encoded in an outer encoder  72 . The output of the outer encoder is encoded  74  in an inner encoder using sum-product encoding. A symbol stream is then produced  76  by mapping an output bit stream of the inner encoder.  
         [0132]    Further, in accordance with the second preferred embodiment, there is a process in a receiver for decoding a symbol stream with forward error correction to produce an information bit stream. As shown in FIG. 8, a symbol stream is received  80  from a transmitter. The symbol stream is decoded  82  in an inner decoder using sum-product decoding to provide an output bit stream and bit error information for the output bit stream. The bit error information and the output bit stream are provided  86  to an outer decoder, and the outer decoder produces  88  an information bit stream from the bit error information and the output bit stream.  
         [0133]    Further embodiments of the invention pertain to a transmitter or receiver that performs processing as described above. Typically such transmitter or receiver will comprise at least one processor and storage media coupled to the at least one processor and containing programming code for performing processing as described above.