Density Devolution for Ordering Synthetic Channels

Constructing a polar code is all about selecting a subset of rows from a Kronecker power of $ \left[ {\begin{array}{c} {10} \\ {11} \end{array}} \right] $. It is known that, under successive cancellation decoder, some rows are Paretobetter than the other. For instance, whenever a user sees a substring 01 in the binary expansion of a row index and replaces it with 10, the user obtains a row index that is always more welcomed. We call this a "rule" and denote it by 10 ≽ 01. In present work, we first enumerate some rules over binary erasure channels such as 1001 ≽ 0110 and 10001 ≽ 01010 and 10101 ≽ 01110. We then summarize them using a "rule of rules": if 10a ≽ 01b is a rule, where a and b are arbitrary binary strings, then 100a ≽ 010b and 101a ≽ 011b are rules. This work’s main contribution is using field theory, Galois theory, and numerical analysis to develop an algorithm that decides if a rule of rules is mathematically sound. We apply the algorithm to enumerate some rules of rules. Each rule of rule is capable of generating an infinite family of rules. For instance, 10c01 ≽ 01c10 for arbitrary binary string c can be generated. We found an application of 10c01 ≽ 01c10 that is related to integer partition and the dominance order therein.