A Balanced Tree Approach to Construction of Length-Compatible Polar Codes

From the perspective of tree, we design a length-compatible coding scheme in this paper. We first construct a balanced binary tree for an arbitrary given code length where the root node represents a codeword, each of the leaf nodes represents either an active bit or a frozen bit and the relationship between a parent node and its child nodes is defined by a modified (U+V|V) construction. Both the encoding and the decoding can be implemented over the constructed tree. In the encoding process, we initialize the active leaf nodes by data bits and the frozen leaf nodes by zero, and then update the other nodes to obtain a codeword at the root node. In the decoding process, we initialize the log-likelihood ratios (LLRs) of the root node by a received vector, and then update the other nodes to obtain the estimates of data bits from the active leaf nodes. For code construction, we propose a universal method to rank the reliability of the leaf nodes and then select the most reliable leaf nodes as the active nodes. Numerical results demonstrate that for a moderate code rate, our proposed codes can perform better than the 5G polar codes.