Methods and systems for decoding polar codes
Herein provided are methods and systems for decoding polar codes. A data flow graph relating to a predetermined polar code is converted to a tree graph comprising rate-zero nodes, rate- 1 nodes, and rate-R nodes. A rate-R node within the binary tree is replaced with a maximum likelihood node when predetermined conditions are met thereby replacing a sub-tree of the tree graph with a single maximum likelihood node.
1. A method of decoding comprising:
converting a data flow graph relating to a predetermined polar code to a tree graph comprising rate-zero nodes, rate-1 nodes, and rate-R nodes, each of the nodes linked to a root of the tree graph, the tree graph stored in a dual-port random-access memory (RAM);
replacing at least one rate-R node, associated with a sub-tree of the tree graph, with a single maximum likelihood node when predetermined conditions are met, by storing the single maximum likelihood node in the dual-port RAM; and
decoding the tree graph by sequentially visiting each of the nodes at the root.
2. The method according to claim 1 , wherein
the tree graph is associated with a decoder implementing at least one of a pipelined successive cancellation architecture, a line successive cancellation architecture, a semi-parallel successive cancellation architecture, a simplified successive cancellation architecture, and a resource constrained successive cancellation architecture.
3. The method according to claim 1 , wherein
the maximum likelihood node performs a resource constrained exhaustive search maximum likelihood decoding of a constituent code corresponding to a rate-R node it replaces.
4. The method according to claim 1 , wherein
the tree graph is a binary tree.
5. The method according to claim 1 , wherein
the predetermined condition is that (2 k v +1)(n v −1)≤P, where
P is the number of processing elements within a decoder executing the method;
2 k v is the number of candidate codewords; and
n v is the length of the constituent codeword being decoded.
6. A polar code decoder comprising;
a plurality of memory elements, comprising a dual-port random-access memory (RAM), storing a tree graph generated from a data flow graph relating to a polar code being decoded, the tree graph comprising rate-zero nodes, rate-1 nodes, and rate-R nodes each linked to a root of the tree graph; and
a plurality of processing elements configured for decoding the tree graph by:
generating the tree graph from the data flow graph;
replacing at least one rate-R node, associated with a sub-tree of the tree graph, with a single maximum likelihood node when predetermined conditions are met, by storing the single maximum likelihood node in the plurality of memory elements; and
sequentially visiting each of the nodes to decode each of the nodes at the root.
7. The polar code decoder according to claim 6 , wherein
each decoder time step relating to the tree graph is associated with a clock cycle of a clock driving the polar code decoder.
8. The polar code decoder according to claim 6 , wherein
the single maximum likelihood node decodes a sub-tree of the tree graph in a single clock cycle.
9. The polar code decoder according to claim 6 , wherein
the predetermined condition is that (2 k v +1)(n v −1)≤P, where
P is the number of processing elements in the plurality of processing elements;
2 k v is the number of candidate codewords; and
n v is the length of the constituent codeword being decoded.