TY - GEN
T1 - Reed-Muller Codes Polarize
AU - Abbe, Emmanuel
AU - Ye, Min
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/11
Y1 - 2019/11
N2 - Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix G-m= [1/1 0/1] ⊗m but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in G-m; while this is a more elaborate and channel-dependent rule, the top-To-down ordering allows Arikan to show that the conditional mutual information polarizes, and this gives directly a capacity-Achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this paper, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-To-down but from the lightest to the heaviest rows in G-m, the conditional mutual information again polarizes. We further demonstrate that it does so faster than for polar codes. This implies that G-m contains another code, different than the polar code and called here the twin-RM code, that is provably capacity-Achieving on any symmetric channel. This gives in particular a necessary condition for RM codes to achieve capacity on symmetric channels. It further gives a sufficient condition if the rows with largest conditional mutual information correspond to the heaviest rows, i.e., if the twin-RM code is the RM code. We demonstrate here that the two codes are at least similar and give further evidence that they are indeed the same.
AB - Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix G-m= [1/1 0/1] ⊗m but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in G-m; while this is a more elaborate and channel-dependent rule, the top-To-down ordering allows Arikan to show that the conditional mutual information polarizes, and this gives directly a capacity-Achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this paper, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-To-down but from the lightest to the heaviest rows in G-m, the conditional mutual information again polarizes. We further demonstrate that it does so faster than for polar codes. This implies that G-m contains another code, different than the polar code and called here the twin-RM code, that is provably capacity-Achieving on any symmetric channel. This gives in particular a necessary condition for RM codes to achieve capacity on symmetric channels. It further gives a sufficient condition if the rows with largest conditional mutual information correspond to the heaviest rows, i.e., if the twin-RM code is the RM code. We demonstrate here that the two codes are at least similar and give further evidence that they are indeed the same.
KW - Reed-Muller codes
KW - Shannon theory
KW - capacity-Achieving codes
KW - polar codes
UR - http://www.scopus.com/inward/record.url?scp=85078475478&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078475478&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2019.00026
DO - 10.1109/FOCS.2019.00026
M3 - Conference contribution
AN - SCOPUS:85078475478
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 273
EP - 286
BT - Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PB - IEEE Computer Society
T2 - 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Y2 - 9 November 2019 through 12 November 2019
ER -