Trellis encoder and decoder based upon punctured rate ½ convolutional codes

Abstract

An encoder for encoding data as trellis coded data and a decoder for decoding the trellis coded data. The encoder uses a rate ½ convolutional encoder punctured to a rate k/n to produce n symbols from k input bits. The symbols are converted by a converter to sets of p symbols and provided to an interleaver. In the interleaver certain ones of the symbols are delayed. Symbol sets are output from the interleaver to a 2 P -ary modem for modulation and transmission. The decoder uses a modem for providing from the modulated data sets of p symbols. A deinterleaver delays certain ones of the symbols to achieve time alignment of the originally interleaved symbols. The sets of time aligned symbols are provided to metric calculators for computing signal metrics which are provided to a converter for providing n sets of metrics to a metric decoder. The metric decoder computes from the n sets of metrics an estimate of the encoded k data bits.

We claim:  
     
       1. A method for encoding digital data for trellis modulation comprising the steps of: 
       receiving k input data bits;  
       encoding said k input data bits according to a first encoding format of a rate {fraction ( 1 / 2 )} encoder punctured for rate k/n where k and n are integers and k/n is a fraction greater than {fraction ( 1 / 2 )} to provide n symbols;  
       converting said n symbols to provide said n symbols as a sequence of sets of at least three symbols;  
       delaying for a predetermined first duration a second symbol of each set of three symbols;  
       delaying for a predetermined second duration a third symbol of each set of three symbols; and  
       providing for modulation an interleaved symbol set including a first symbol of one of said sets of symbols with corresponding delayed second and third symbols of previous symbol sets.  
     
     
       2. The method of  claim 1  wherein said step of providing for modulation an interleaved symbol set includes the step of mapping said interleaved symbol set to a modulation value according to a second encoding format. 
     
     
       3. A method for decoding interleaved trellis modulated data comprising the steps of: 
       receiving and decoding, in accordance with a first decoding format;  of rate {fraction ( 1 / 2 )} punctured for rate k/n where k and n are integers and k/n is a fraction greater than {fraction ( 1 / 2 )}; said interleaved trellis modulated data to provide sets of three symbols;  
       delaying for a predetermined first duration a first symbol of each set of three symbols;  
       delaying for a predetermined second duration a second symbol of each set of three symbols;  
       combining delayed first and second symbols with third symbols of said sets of three symbols to provide a set of n symbols; and  
       decoding according to a decoding format said set of n symbols.  
     
     
       4. The method of  claim 3  wherein said step of decoding is performed with a second decoding format. 
     
     
       5. An apparatus for encoding data, comprising: 
       encoding means for receiving user data and encoding said user data into a first number of encoded symbol streams by a rate {fraction ( 1 / 2 )} encoder punctured for rate k/n where k and n are integers and k/n is a fraction greater than {fraction ( 1 / 2 )};  
       symbol grouping means for converting said first number of encoded symbol streams into a different second number of reordered encoded symbol streams, said symbol grouping means comprising a plurality of delay means wherein each of said plurality of delay means delays ones of said second number of reordered encoded symbol streams by different delays; and  
       transmitter means for receiving successive sets of encoded symbols provided by said second number of reordered encoded symbol streams, and for modulating and transmitting said successive sets of encoded symbols in accordance with a predetermined encoding format.  
     
     
       6. The apparatus of  claim 5  wherein said encoding means is a convolutional encoder. 
     
     
       7. The apparatus of  claim 5  wherein said encoding means is a rate ½ encoder punctured for rate k/n where k and n are integers and k/n is a fraction greater than ½. 
     
     
       8. The apparatus of  claim 5  wherein said symbol grouping means further includes parallel conversion means for generating each of said second number of reordered encoded symbol streams by grouping symbols from selected ones of said first number of encoded symbol streams. 
     
     
       9. The apparatus of  claim 5  wherein said predetermined encoding format is a modified Gray code. 
     
     
       10. The apparatus of  claim 5  wherein said predetermined encoding format is an 8-ary phase-shift keying (PSK) modulation format. 
     
     
       11. A method for encoding data, comprising the steps of: receiving user data; encoding said user data in accordance with a predetermined coding format to provide a first number of encoded symbol streams; 
       converting said first number of encoded symbol streams into a different second number of reordered encoded symbol streams, the step of converting further including the step of delaying ones of said second number of reordered encoded symbol streams by different delays; and  
       transmitting symbol sets provided by said second number of reordered encoded symbol streams in accordance with a predetermined encoding format;  
       
         wherein said predetermined coding format is a convolutional rate {fraction ( 1 / 2 )} encoding punctured for rate k/n where k and n are integers and k/n is a fraction greater than {fraction ( 1 / 2 )}.  
       
     
     
       12. The method of  claim 11  wherein said step of encoding is a convolutional encoding. 
     
     
       13. The method of  claim 11  wherein said step of encoding format is a rate ½ encoding punctured for rate k/n where k and n are integers and k/n is a fraction greater and ½. 
     
     
       14. The method of  claim 11  further comprising the step of generating each of said symbol sets using at least one encoded symbol from each of said second number of reordered encoded symbol streams. 
     
     
       15. The method of  claim 11  wherein said step of transmitting is performed in accordance with a modified Gray code. 
     
     
       16. The method of  claim 11  wherein said step of transmitting is performed in accordance with an 8-ary phase-shift keying (PSK) modulation format. 
     
     
       17. A system for encoding data, comprising: 
       an encoder having an input for receiving user data and encoding said user data in accordance with a first predetermined coding format and having an output for providing encoded symbols;  
       a symbol buffer having an input coupled to said encoder output for reordering said encoded symbols in accordance with a predetermined grouping format and having an output, said symbol buffer comprising a plurality of delay elements wherein each of said plurality of delay elements delays ones of said encoded symbols by different delays; and  
       a transmitter having an input coupled to said symbol buffer output for modulating and transmitting sets of said reordered encoded symbols, said sets of said reordered encoded symbols each being mapped to a modulation value in accordance with a second predetermined coding format;  
       
         wherein said predetermined encoder is a convolutional rate {fraction ( 1 / 2 )} encoding punctured for rate k/n where k and n are integers and k/n is a fraction greater than {fraction ( 1 / 2 )}.  
       
     
     
       18. The system of  claim 17  wherein said encoder is a convolutional encoder. 
     
     
       19. The system of  claim 18  wherein said encoder is a rate ½ punctured for rate k/n where k and n are integers and k/n is a fraction greater than ½. 
     
     
       20. The system of  claim 17  further comprising a rate converter disposed having an input coupled to said encoder output having an output coupled to said symbol buffer input. 
     
     
       21. The system of  claim 17  wherein said predetermined encoding format is a modified Gray code. 
     
     
       22. The apparatus of  claim 17  wherein said predetermined encoding format is an 8-ary phase-shift keying (PSK) modulation format. 
     
     
       23. An apparatus for decoding data, comprising: 
       demodulator means for receiving a transmitted signal and for demodulating said transmitted signal in accordance with a predetermined demodulation format to provide a first number of streams of symbol estimates;  
       symbol grouping means for converting said first number of streams of symbol estimates into a different second number of streams of reordered symbol estimates, said symbol means comprising a plurality of delay means wherein each of said plurality of delay means delays ones of said first number of streams of symbol estimates by different delays; and  
       decoder means for decoding symbol sets provided by said second number of streams of reordered symbol estimates.  
     
     
       24. The apparatus of  claim 23  wherein said decoder means is a Viterbi decoder. 
     
     
       25. The apparatus of  claim 23  wherein said symbol grouping means includes means for providing said symbol sets so as to include at least one of said symbol estimates from each of said second number of streams of reordered symbol estimates. 
     
     
       26. The apparatus of  claim 23  further comprising a metric computer means disposed between said symbol grouping means and said decoder means for receiving said symbol estimates and generating sets of decoder metrics in accordance with a predetermined metric computation format. 
     
     
       27. A method for decoding data, comprising the steps of: 
       receiving a transmitted signal;  
       demodulating said transmitted signal in accordance with a predetermined demodulation format to provide a first number of streams of symbol estimates;  
       converting said first number of streams of symbol estimates into a different second number of streams of reordered symbol estimates, said step of converting including the step of delaying ones of said first number of streams of symbol estimates by different delays; and  
       decoding symbol sets provided by said second number of streams of reordered symbols estimates.  
     
     
       28. The method of  claim 27  wherein said decoder format is a Viterbi decoding format. 
     
     
       29. The method of  claim 27  further comprising the step of providing each of said symbol sets so that at least one of said symbol estimates from each of said second number of streams of reordered symbol estimates is included within each of said symbol sets. 
     
     
       30. The method of  claim 27  further comprising the step of generating sets of decoder metrics for said symbol estimates in accordance with a predetermined metric computation format. 
     
     
       31. A system for decoding data, comprising: 
       a demodulator having an input for receiving a transmitted signal and for demodulating said transmitted signal in accordance with a predetermined demodulation format and having an output to provide sets of symbol estimates, each of said sets of symbol estimates being associated with a modulation value based upon said predetermined demodulation format;  
       a symbol buffer having an input coupled to said demodulator output, for reordering said sets of symbol estimates in accordance with a predetermined grouping format and having an output for providing sets of reordered symbol estimates, said symbol buffer comprising a plurality of delay elements wherein each of said plurality of delay elements delays ones of said symbol estimates within each of said sets of symbol estimates by different delay durations; and  
       a decoder having an input coupled to said symbol buffer output for decoding said sets of reordered symbol estimates in accordance with a predetermined decoding format.  
     
     
       32. The system of  claim 31  wherein said decoder is a Viterbi decoder. 
     
     
       33. The system of  claim 31  further comprising a rate converter disposed between said symbol buffer and said decoder having an input coupled to said symbol buffer and having an output coupled to said decoder input. 
     
     
       34. The system of  claim 31  further comprising a metric computer having an input coupled to said symbol buffer and having an output coupled to said decoder input. 
     
     
       35. A system for encoding digital data for trellis modulation comprising: 
       first means for receiving k input data bits;  
       second means for encoding said k input data bits according to a first encoding format to provide n symbols;  
       third means for converting said n symbols to provide said n symbols as a sequence of sets of at least three symbols;  
       fourth means for delaying for a predetermined first duration a second symbol of each set of three symbols;  
       fifth means for delaying for a predetermined second duration a third symbol of each set of three symbols; and  
       sixth means for providing an interleaved symbol set including a first symbol of one of said sets of symbols with corresponding delayed second and third symbols of previous symbol sets.  
     
     
       36. A system for decoding interleaved trellis modulated data comprising: 
       first means for receiving and decoding said interleaved trellis modulated data to provide sets of three symbols;  
       second means for delaying for a predetermined first duration a first symbol of each set of three symbols;  
       third means for delaying for a predetermined second duration a second symbol of each set of three symbols;  
       fourth means for combining delayed first and second symbols with third symbols of said sets of three symbols to provide a set of n symbols; and  
       fifth means for decoding according to a decoding format said set of n symbols.