Abstract:
An encoder, decoder, method of encoding, and method of decoding which preserves the turbo coder performance in the waterfall region, while improving upon performance in the error asymptote region, by applying a parser or other similar element to the input bit stream. The parser assigns input bits to a subset of constituent encoders in a pseudo-random fashion. The parsing strategy breaks up input sequences producing low Hamming weight error events, thereby improving the weight spectrum and asymptotic performance of the code, while not impacting waterfall region performance. The parser or other similar element may also strengthen the weight spectrum without adversely affecting convergence of a corresponding decoder.

Description:
This application claims the benefit of a provisional Application No. 60/148,919 filed Aug. 13, 1999. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to forward error correction encoders and decoders and more particularly, to turbo-like forward error correction encoders and decoders with improved weight spectrum and reduce degradation in the waterfall performance region. 
     2. Description of the Related Art 
     FIG. 1 illustrates a conventional Turbo encoder  10  which, as illustrated, includes two parallel constituent encoders  12 ,  14 . An input stream x(k) is encoded by the constituent encoders  12 ,  14  to produce parity bits y 1 (k) and y 2 (k). The encoder  14  sees the input stream x(k) presented in a different order than the encoder  12  due to the presence of an embedded Turbo interleaver  16 . The output coded bits x(k), y 1 (k), y 2 (k) are then punctured by puncturer  18  to produce the desired overall code rate. In the example, the natural rate of the Turbo encoder  10  is 1/3. FIG. 1 shows a periodic puncturing pattern that produces an output code rate equal to 1/2. 
     FIG. 2 illustrates another encoder  20  for a conventional turbo code proposed for third generation CDMA systems. The encoder  20 , as illustrated, includes two constituent coders  22 ,  24  that are systematic recursive convolutional coders having the transfer function G(D). The exemplary constituent coders  22 ,  24  are rate 1/2 (producing one parity bit for each input information bit) and have 8 trellis states (each shift register has three delay elements  221 - 223  and  241 - 243 ). The overall rate of the turbo code is thus R=1/3, since each information bit produces two parity bits, one from each encoder  22 ,  24 . Various puncturing patterns are shown in FIG. 2 to increase the code rate. 
     FIG. 3 illustrates a general block diagram for a Turbo code decoder  30  as generally described in C. Berrou et al., “Near Shannon Limit Error Correcting Coding and Decoding: Turbo Codes,” Proceedings of ICC (Geneva, Switzerland), May 1993 and S. Benedetto et al., “Design of Parallel Concatenated Convolutional Codes,” IEEE Transactions on Communications, May 1996, Vol. COM-44, pp. 591-600. Soft-decision (likelihood) information for the systematic and parity bits from a first constituent coder (such as encoder  12  in FIG. 1) are sent to a first decoder  32 . The first decoder  32  generates updated soft-decision likelihood values for the information bits that are passed to a second decoder  34  as a priori information after reordering in accordance with a Turbo interleaver  36 . 
     In addition, the second decoder  34  accepts updated likelihood information for the systematic bits via an interleaver  38 , and the soft-decision information from the channel for the parity bits from a second constituent encoder (such as encoder  14  in FIG.  1 ). A soft-decision output of the second decoder  34  regarding updated likelihood information for the systematic bits is then fed back to the first decoder  32  via a de-interleaver  40 . This process can be iterated as many times as desired. However, only a relatively small number of iterations is usually needed, since additional iterations generally produce diminishing returns. Hard decisions on the systematic information bits are made after the last decoder iteration is completed. If puncturing is used as depicted in FIG. 1, there is no likelihood information available for the corresponding parity bits. This is readily accounted for in the Turbo decoder  30  by using neutral values (favoring neither a 0-decision or a 1-decision) for the missing channel data. 
     If the two constituents encoders  12 ,  14  or  22 ,  24  are identical, the Turbo decoder  30  need only implement one constituent decoder  32  or  34  provided the VLSI hardware clock rate or DSP processing speed is able to support its reuse every half iteration. 
     Turbo codes as described above in conjunction with FIGS. 1-3 are the current state of the art. Additional details can be found in U.S. Pat. No. 5,446,747 to Berrou and Turbo codes implemented on the Turbo encoder and decoder structures described in conjunction with FIGS. 1-3 operate in two regions; a waterfall region and an error asymptote region. It is known that adding additional constituent encoders to a Turbo encoder can improve the error asymptote performance. However, this improvement comes at the cost of degrading the performance in the waterfall region. Research has shown that the performance in the waterfall region is largely due to convergence characteristics of the iterative decoder rather than the code rate spectrum. In general, the more complicated the code, the less efficient the error of decoder, leading to a degradation in waterfall performance. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to an encoder, a decoder, a method of encoding, and a method of decoding, which preserve performance in the waterfall region, while improving upon performance in the error asymptote region. 
     The present invention is a modification of the basic Turbo encoder and decoder structures that preserves the Turbo coder performance in the waterfall region while improving upon performance in the error asymptote region. 
     The present invention provides a new code construction based on the Turbo code structure (in one example, parallel concatenation of constituent codes) that shares the performance of Turbo codes at low SNR while improving upon their asymptotic performance (so-called error floor region). The present invention includes applying a parser (or other similar element) to the input bit stream, the purpose of which is to assign input bits to a subset of the constituent encoders in a pseudo-random fashion. Provided each bit is presented to at least two of the constituent encoders, iterative decoding can still be accomplished in a similar fashion as for a Turbo code. As a result, each constituent decoder may only update the likelihood information associated with the information bits parsed to the corresponding encoder. The parsing strategy breaks up input sequences producing low Hamming weight error events, thereby improving the weight spectrum and asymptotic performance of the code, while not impacting the waterfall region performance of the corresponding Turbo code. 
     The addition of the parser may also strengthen the weight spectrum without adversely affecting convergence of the iterative decoder. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates a conventional Turbo encoder. 
     FIG. 2 illustrates another conventional encoder. 
     FIG. 3 illustrates a conventional Turbo decoder. 
     FIG. 4 illustrates an encoder, in one exemplary embodiment of the present invention. 
     FIG. 5 illustrates a decoder, in one exemplary embodiment of the present invention. 
     FIG. 6 illustrates the operation of the parser in one exemplary of the present invention. 
     FIG. 7 illustrates reductions in both frame error rate and bit error rate using the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 4 illustrates an encoder  100  in one embodiment of the present invention. In FIG. 4, the input information bit stream x(t) is parsed by parser  101  in a pseudo-random manner among three constituent encoders  102 ,  104 ,  106 . Each of the parsed substreams X A (t), X B (t), x C (t) are separately interleaved by interleavers  108 ,  110 ,  112  and then separately encoded by one of the constituent encoders  102 ,  104 ,  106 . The puncturing unit  114  removes coded bits from the output stream according to a prescribed puncturing pattern in order to produce the desired overall code rate. 
     Although the encoder  100  has been illustrated with three constituent encoders  102 ,  104 ,  106 , it is clear that a different number constituent encoders could also be utilized. 
     The parser  101  may ensure that every information bit is encoded by at least two of the constituent encoders  102 ,  104 ,  106  in order that iterative soft-decision decoding can efficiently refine the likelihood decision statistic for each information bit based on outputs from multiple semi-independent constituent decoders. 
     Likewise, the interleaving applied to the separate substreams by interleavers  108 ,  110 ,  112  may be substantially independent of one another in order to produce a high degree of randomness among the output coded substreams. One of the interleavers  108 ,  110 ,  112  can be taken to be the identity mapping (which is equivalent to saying that the interleaver is not implemented). To reduce implementation complexity, the interleavers applied to the other substreams could be identical. 
     As in ordinary turbo codes, the constituent encoders  102 ,  104 ,  106  can be the same or different. Keeping the constituent encoders  102 ,  104 ,  106  the same has the advantage that the implementation complexity is reduced. 
     A decoder  200  is shown in FIG.  5 . The decoder  200  can be implemented in either VLSI or on a digital signal processor (DSP). As in the conventional turbo code case, the decoder  200  implements soft-input/soft-output decoders  202 ,  204 ,  206  for each of the constituent codes. In FIG. 5, the constituent decoders  202 ,  204 ,  206  (along with de-interleavers  216 ,  218 ,  220 ) are shown operating in parallel on soft channel information and soft likelihood information corresponding to the information and parity bits associated with the corresponding encoder ( 102 ,  104 ,  106  in FIG.  4 ). The decoders  202 ,  204 ,  206  could also be operated sequentially, one after another, as in a conventional turbo decoder. This latter option would be especially attractive when the constituent codes are all the same so that a single constituent decoder could be re-used. 
     In FIG. 5, the decoder  200  is presented with soft channel information r info (t), corresponding to the systematic information bits, and soft channel information r parity (t), corresponding to the transmitted parity bits. The soft information associated with the systematic bits are parsed by parser  201  and interleaved by interleavers  208 ,  210 ,  212  into substreams A, B and C before being delivered to the constituent decoders  202 ,  204 ,  206 . These parsing and interleaving functions may mirror those performed by the encoder  100 . Each constituent decoder  202 ,  204 ,  206  also receives the soft channel information associated with each parity produced by the corresponding constituent encoder via parity parser  211 . Each soft-input/soft-output constituent decoder  202 ,  204 ,  206  then processes these inputs and produces new likelihood information via de-interleavers  216 ,  218 ,  220  for each of the systematic bits to which it has visibility. The likelihood information provided by each constituent encoder  202 ,  204 ,  206  are combined by the Likelihood Information Update module  214  to provide updated likelihood information for all of the systematic bits. This completes one iteration of the decoding process. 
     The decoding process can be iterated as many times as desired, either using a fixed stopping rule or a dynamic stopping rule, both of which are known to one of ordinary skill in this art. A common fixed stopping rule is to perform some maximum number of iterations that the processor (VLSI or DSP) can perform within the available timeline. A common dynamic stopping rule is to continue to iterate until the decoded data passes a cyclic redundancy check (CRC) or a maximum number of iterations is reached. Once the desired number of iterations has been completed, hard decisions regarding the values of the systematic information bits are made based on the final likelihood information provided by the Likelihood Information Update module  214 . Note that it is possible for the decoder  200  to stop after the soft information from any of the constituent decoders  202 ,  204 ,  206  has been used to update the likelihood estimates. Thus, one could stop at any “one-third” of an iteration. 
     If the constituent codes are the same and the decoder  200  re-uses one constituent decoder, the complexity of the decoder of FIG. 5 is not significantly increased compared to that of FIG.  3 . 
     EXAMPLE 1 
     This example compares the new code construction of the present invention with the conventional turbo code of FIG.  2 . In this example, there are three constituents identical to the  8- state recursive convolutional codes used by the conventional turbo code of FIG.  2 . In the new code of the present invention, the input systematic bits are parsed as shown in FIG.  6 . That is, constituent encoder A ( 202 ) sees every information bit x(t) for which t=0 or 1 modulo  3 ; constituent encoder B ( 204 ) sees every information bit x(t) for which t=0 or 2 modulo  3 ; and constituent encoder C ( 206 ) sees every information bit x(t) for which t=1 or 2 modulo  3 . Thus every input bit is processed by two of the constituent encoders. 
     If there are a total of N information bits, then each constituent encoder A, B, C ( 202 ,  204 ,  206 ) produces 2N/3 output parity bits. The overall code rate is therefore R=N/[N+3·(2N/3)]=1/3, the same as the conventional turbo code of FIG.  2 . If a higher composite code rate is desired, then a simple period puncturing scheme similar to that of FIG. 2 can also be applied to the new code construction. For example, the pattern 
     
       
         
               
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 Systematic: 
                 1 
                 1 
                 1 
               
               
                   
                 Parity A: 
                 1 
                 0 
                 N/A 
               
               
                   
                 Parity B: 
                 0 
                 N/A 
                 1 
               
               
                   
                 Parity C: 
                 N/A 
                 1 
                 0 
               
               
                   
                   
               
             
          
         
       
     
     produces an overall rate R=1/2. 
     One advantage of parsing is that low Hamming weight inputs are broken up before delivery to the constituent encoders ( 202 ,  204 ,  206 ). For example, consider the input sequence having exactly two ones at the following positions: x(0)=x(10)=1. The input to the first constituent encoder  202  includes a critical input sequence in which the ones are distance 7 apart. The first constituent encoder  202  will therefore produce a low weight output. Each of the remaining constituent encoders  204 ,  206  sees only one of the two input  1 s. Thus, neither of the two other constituent encoders  204 ,  206  will produce low output weight. The overall effect of the parsing is to reduce the number of low weight code words compared to the conventional turbo code of FIG.  2 . This improves the error asymptote performance of the new code construction compared to the conventional turbo code. 
     Although additional constituent encoders are known to enhance the error asymptote performance of a conventional turbo code, they also degrade the waterfall region of the performance curve. Theoretical analysis of the conventional iterative turbo decoder as shown in H. El-Gamal et al., “Analyzing the Turbo Decoder Using the Gaussian Approximation,” submitted to 1999 Allerton Conference at the University of Illinois at Champaign-Urbana has shown that the degradation occurs due to breakdown in the iterative decoder rather than a change in the code weight spectrum. In the code construction of the present invention, each information bit is associated with two parity bits from two different constituent encoders, as in the case of the conventional turbo code. 
     Theoretical analysis shows that for large enough block sizes (for example, &gt;1000) the structure of the present invention will produce the same waterfall performance as the conventional turbo code. Thus, unlike any prior turbo-like construction, the present invention improves the error asymptote performance while preserving the waterfall performance. 
     FIG. 7 illustrates the results achieved using the present invention. In particular, the dashed line curves illustrate the frame error rates and bit error rates for a regular, four-state (with R=1/3 with a frame size of 1000 using random interleaving), whereas the solid lines illustrate the frame error rates and bit error rates for a parsed four-state (R=1/3, with a frame size of 1000, using random interleaving). As illustrated in FIG. 7, in the waterfall performance region (between 0.4 and 1.2 Ebi/No), the performance is essentially the same in the parsed state as in the regular state. However, in the error asymptote performance region, (0.9 to 1.6 Ebi/No), the performance using the parser is noticeably improved for both the frame error rate and the bit error rate. 
     Turbo codes are utilized for diverse product lines including DirecPC™ and the Personal Earth Station™ (PES). Due to the improved error asymptote performance realized by the present invention, the present invention is also applicable to other diverse product lines. 
     Although the present invention has been described above in conjunction with the parallel code, serial codes may also be utilized. Additionally, trellis-coded modulation, based on turbo codes may also be utilized in the present invention, both serial and parallel. 
     The present invention has been described above in connection with a puncturer  114  illustrated in FIG.  4 . However, the function of the puncturer  114  can be replaced by any hardware or software element that determines whether bits are forwarded or not. Similarly, the embodiment of the present invention has been described above in conjunction with constituent encoders  102 . These encoders  102  may be block encoders, systematic encoders, convolutional encoders, and/or recursive or non-recursive encoders or a combination thereof. 
     Similarly, the present invention has been described above in conjunction with an interleaver  108 . The interleaver  108  can be any general purpose interleaver or could be optimized for weighted spectrum characteristics. The present invention has been described in conjunction with the parser  101 . However, the parser  101  could be replaced with any hardware or software which selectively outputs bits to one of a plurality of interleavers, encoders, or decoders. The parser may be implemented as combinatorial logic, FPGA, a DSP or VLSI. 
     With respect to the constituent decoders illustrated in FIG. 5, these constituent decoders may be soft-input/soft-output decoders used in conventional Turbo codes, maximum a posteriori (MAP) decoders, or soft-output viterbi algorithm (SOVA) decoders or a combination thereof. 
     As described above, one of the features of the present invention is that at least one of the encoders (or decoders) does not encode (or decode) all of the bits. Similarly, although the present invention as described above, encodes every bit twice, some of the bits could be included three or more times. Further, it is not necessary that each of the bits be included twice, although this technique is preferable in order to obtain the benefit of Turbo processing. 
     The invention being thus described, it will be obvious that the same may be varied in many ways. Such variations are not to be regarded as a departure from the spirit and scope of the invention, and all such modifications as would be obvious to one skilled in the art are intended to be included within the scope of the following claims.