Convolutional precoding and decoding of polar codes

Abstract

Devices, systems and methods for convolutional precoding and decoding of polar codes are disclosed. An example method for error correction in a data processing system includes receiving a noisy codeword, the codeword having been generated based on an outer stream decodable code and an inner polar code and provided to a communication channel or a storage channel prior to reception by the decoder, the stream decodable code characterized by a trellis, and performing, based on the trellis, a list-decoding operation on the noisy codeword vector to generate a plurality of information symbols, the list-decoding operation being configured to traverse through a plurality of states at one or more stages of a plurality of decoding stages.

What is claimed is: 
     
       1. A method for improving an error correction capability of an encoder, comprising:
 receiving a plurality of information symbols; 
 generating a plurality of convolutionally encoded symbols by performing a convolutional encoding operation on the plurality of information symbols, wherein the convolutional encoding operation is based on a time-varying trellis; 
 generating a plurality of polar encoded symbols by performing a polar encoding operation on the plurality of convolutionally encoded symbols; and 
 providing the plurality of polar encoded symbols for transmission or storage. 
 
     
     
       2. The method of  claim 1 , wherein the convolutional encoding operation uses a high-rate convolutional code with a code rate greater than ½. 
     
     
       3. The method of  claim 2 , wherein the high-rate convolutional code is generated by applying a time-varying puncturing pattern to a low-rate convolutional code with a code rate less than or equal to ½. 
     
     
       4. The method of  claim 1 , wherein the polar encoding operation uses a polar code and comprises multiplying the plurality of convolutionally encoded symbols by a generator matrix (G). 
     
     
       5. The method of  claim 4 , wherein the generator matrix is defined as 
       
         
           
             
               G 
               = 
               
                 
                   B 
                   ⁡ 
                   
                     [ 
                     
                       
                         
                           1 
                         
                         
                           0 
                         
                       
                       
                         
                           1 
                         
                         
                           1 
                         
                       
                     
                     ] 
                   
                 
                 
                   ⊗ 
                   m 
                 
               
             
           
         
         wherein ⊗ denotes a Kronecker product, wherein B is an n×n bit-reversal permutation matrix, wherein n=2 m  is a length of the polar code, and wherein m and n are integers. 
       
     
     
       6. The method of  claim 1 , wherein the convolutional encoding operation uses a convolutional code characterized by a trellis. 
     
     
       7. The method of  claim 6 , wherein the trellis is a time-varying trellis. 
     
     
       8. The method of  claim 6 , wherein the trellis is a time-invariant trellis. 
     
     
       9. The method of  claim 1 , wherein the convolutional encoding operation uses a convolutional code with mother code-rate ½, and wherein a traceback depth of the convolutional code is equal to five times a constraint length of the convolutional code. 
     
     
       10. A device for improving an error correction capability of an encoder, comprising:
 a processor; and 
 a non-transitory memory including instructions stored thereon, wherein the instructions upon execution by the processor cause the processor to:
 receive a plurality of information symbols; 
 generate a plurality of convolutionally encoded symbols by performing a convolutional encoding operation on the plurality of information symbols, wherein the convolutional encoding operation is based on a time-varying trellis; 
 generate a plurality of polar encoded symbols by performing a polar encoding operation on the plurality of convolutionally encoded symbols; and 
 provide the plurality of polar encoded symbols for transmission or storage. 
 
 
     
     
       11. The device of  claim 10 , wherein the convolutional encoding operation uses a high-rate convolutional code with a code rate greater than ½, and wherein the high-rate convolutional code is generated by applying a time-varying puncturing pattern to a low-rate convolutional code with a code rate less than or equal to ½. 
     
     
       12. The device of  claim 10 , wherein the polar encoding operation uses a polar code and comprises multiplying the plurality of convolutionally encoded symbols by a generator matrix (G). 
     
     
       13. The device of  claim 12 , wherein the generator matrix is defined as 
       
         
           
             
               G 
               = 
               
                 
                   B 
                   ⁡ 
                   
                     [ 
                     
                       
                         
                           1 
                         
                         
                           0 
                         
                       
                       
                         
                           1 
                         
                         
                           1 
                         
                       
                     
                     ] 
                   
                 
                 
                   ⊗ 
                   m 
                 
               
             
           
         
         wherein ⊗ denotes a Kronecker product, wherein B is an n×n bit-reversal permutation matrix, wherein n=2 m  is a length of the polar code, and wherein m and n are integers. 
       
     
     
       14. The device of  claim 10 , wherein the convolutional encoding operation uses a convolutional code characterized by a trellis, and wherein the trellis is either a time-varying trellis or a time-invariant trellis. 
     
     
       15. The device of  claim 10 , wherein the convolutional encoding operation uses a convolutional code with mother code-rate ½, and wherein a traceback depth of the convolutional code is equal to five times a constraint length of the convolutional code. 
     
     
       16. A non-transitory computer-readable storage medium having instructions stored thereupon for improving an error correction capability of an encoder, comprising:
 instructions for receiving a plurality of information symbols; 
 instructions for generating a plurality of convolutionally encoded symbols by performing a convolutional encoding operation on the plurality of information symbols, wherein the convolutional encoding operation is based on a time-varying trellis; 
 instructions for generating a plurality of polar encoded symbols by performing a polar encoding operation on the plurality of convolutionally encoded symbols; and 
 instructions for providing the plurality of polar encoded symbols for transmission or storage. 
 
     
     
       17. The computer-readable storage medium of  claim 16 , wherein the convolutional encoding operation uses a high-rate convolutional code with a code rate greater than ½. 
     
     
       18. The computer-readable storage medium of  claim 17 , wherein the high-rate convolutional code is generated by applying a time-varying puncturing pattern to a low-rate convolutional code with a code rate less than or equal to ½. 
     
     
       19. The computer-readable storage medium of  claim 16 , wherein the polar encoding operation uses a polar code and comprises multiplying the plurality of convolutionally encoded symbols by a generator matrix (G). 
     
     
       20. The computer-readable storage medium of  claim 19 , wherein the generator matrix is defined as 
       
         
           
             
               G 
               = 
               
                 
                   B 
                   ⁡ 
                   
                     [ 
                     
                       
                         
                           1 
                         
                         
                           0 
                         
                       
                       
                         
                           1 
                         
                         
                           1 
                         
                       
                     
                     ] 
                   
                 
                 
                   ⊗ 
                   m 
                 
               
             
           
         
         wherein ⊗ denotes a Kronecker product, wherein B is an n×n bit-reversal permutation matrix, wherein n=2 m  is a length of the polar code, and wherein m and n are integers.