Partial sum computation for polar code decoding

1. A method comprising:

receiving a word that is based on a codeword of a polar code;

decoding bits in a decoding segment of the received word to generate decoded bits;

updating and storing a lower-order partial sum based on the decoded bits;

starting decoding of a subsequent bit in the received word;

computing a higher-order partial sum based on the lower-order partial sum during the decoding of the subsequent bit in the received word; and

storing the computed higher-order partial sum.

2. The method of claim 1 , wherein the updating and storing comprises updating the lower-order partial sum in partial sum storage.

3. The method of claim 1 ,

wherein storing the computed higher-order partial sum comprises storing the computed higher-order partial sum to partial sum memory.

4. The method of claim 3 , wherein the computing comprises computing the higher-order partial sum based on multiple lower-order partial sums including the lower-order partial sum and at least one further lower-order partial sum, and wherein the method further comprises:

retrieving one of the multiple lower-order partial sums from the partial sum memory; and

retrieving another one of the multiple lower-order partial sums from partial sum scratchpad storage.

5. The method of claim 1 , further comprising:

decoding bits in a subsequent decoding segment in the received word using the higher-order partial sum.

6. The method of claim 5 , wherein decoding bits in the subsequent decoding segment comprises traversing nodes in a Data Dependency Graph (DDG) of the polar code in a reverse order relative to node indices of at least some of the nodes in the DDG.

7. The method of claim 5 ,

wherein the computing comprises combining multiple lower-order partial sums, including the lower-order partial sum and at least one further lower-order partial sum, which lower-order partial sums are based on previously decoded bits including the generated decoded bits, and

wherein the combining comprises combining the multiple lower-order partial sums according to a reverse order relative to an order in which at least some of the previously decoded bits were decoded.

8. An apparatus comprising:

a receiver to receive a word that is based on a codeword of a polar code; and

a decoder, coupled to the receiver, to decode bits in a decoding segment of the received word to generate decoded bits, to update and store a lower-order partial sum based on the decoded bits, to start decoding of a subsequent bit in the received word, to compute a higher-order partial sum based on the lower-order partial sum during the decoding of the subsequent bit in the received word, and to store the computed higher-order partial sum.

9. The apparatus of claim 8 , further comprising:

partial sum storage, coupled to the decoder, storing the lower-order partial sum,

wherein the decoder is configured to update and store the lower-order partial sum by updating the lower-order partial sum in the partial sum storage.

10. The apparatus of claim 8 , further comprising:

partial sum memory coupled to the decoder,

wherein the decoder is configured to store the computed higher-order partial sum to the partial sum memory.

11. The apparatus of claim 10 , further comprising:

partial sum scratchpad storage coupled to the decoder,

wherein the decoder is configured to compute the higher-order partial sum based on multiple lower-order partial sums including the lower-order partial sum and at least one further lower-order partial sum, and

wherein the decoder is further configured to retrieve one of the multiple lower-order partial sums from the partial sum memory, and to retrieve another one of the multiple lower-order partial sums from the partial sum scratchpad storage.

12. The apparatus of claim 8 ,

wherein the decoder is further configured to decode bits in a subsequent decoding segment in the received word using the higher-order partial sum,

wherein the decoder is configured to decode the bits in the subsequent decoding segment by traversing nodes in a Data Dependency Graph (DDG) of the polar code in a reverse order relative to node indices of at least some of the nodes in the DDG.

13. The apparatus of claim 8 ,

wherein the decoder is further configured to decode bits in a subsequent decoding segment in the received word using the higher-order partial sum,

wherein the decoder is configured to compute the higher-order partial sum by combining multiple lower-order partial sums, including the lower-order partial sum and at least one further lower-order partial sum, which lower-order partial sums are based on previously decoded bits including the generated decoded bits, and

wherein the decoder is configured to combine the multiple lower-order partial sums according to a reverse order relative to an order in which at least some of the previously decoded bits were decoded.

14. A non-transitory processor-readable medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform a method comprising:

receiving a word that is based on a codeword of a polar code;

decoding bits in a decoding segment of the received word to generate decoded bits;

updating and storing a lower-order partial sum based on the decoded bits;

starting decoding of a subsequent bit in the received word;

computing a higher-order partial sum based on the lower-order partial sum during the decoding of the subsequent bit in the received word; and

storing the computed higher-order partial sum.

15. A method comprising:

receiving a word that is based on a codeword of a polar code;

decoding bits in the received word to generate decoded bits;

computing and storing a partial sum based on the decoded bits; and

decoding subsequent bits in the received word using the partial sum in traversing nodes in a Data Dependency Graph (DDG) of the polar code in a reverse order relative to node indices of at least some of the nodes in the DDG.

16. The method of claim 15 , further comprising:

combining the partial sum, and at least one further partial sum that is based on previously decoded bits, into a higher-order partial sum according to a reverse order relative to an order in which the decoded bits and the previously decoded bits were decoded.

17. The method of claim 16 , wherein the combining is performed during the decoding of the subsequent bits, and wherein the subsequent bits in the received word are decoded using the higher-order partial sum.

18. An apparatus comprising:

a receiver to receive a word that is based on a codeword of a polar code;

a decoder, coupled to the receiver, to decode bits in the received word to generate decoded bits, to compute and store a partial sum based on the decoded bits, and to decode subsequent bits in the received word using the lower-order partial sum in traversing nodes in a Data Dependency Graph (DDG) of the polar code in a reverse order relative to node indices of at least some of the nodes in the DDG.

19. The apparatus of claim 18 , wherein the decoder is further configured to combine the lower-order partial sum and at least one further lower-order partial sum that is based on previously decoded bits into a higher-order partial sum according to a reverse order relative to an order in which the decoded bits and the previously decoded bits were decoded.

20. The apparatus of claim 19 , wherein the decoder is configured to combine the lower-order partial sum and the further lower-order partial sum during the decoding of the subsequent bits, and to decode the subsequent bits in the received word using the higher-order partial sum.

21. A non-transitory processor-readable medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform a method comprising:

receiving a word that is based on a codeword of a polar code;

decoding bits in the received word to generate decoded bits;

computing and storing a partial sum based on the decoded bits; and

decoding subsequent bits in the received word using the partial sum in traversing nodes in a Data Dependency Graph (DDG) of the polar code in a reverse order relative to node indices of at least some of the nodes in the DDG.