I am at ITW in Dublin, and I will write a short post or two about it. I missed most of the conference until now due to jetlag and late arrival, but I did make it to Arikan’s plenary lecture this morning on the historical context for polar codes. It was a really nice talk about successive decoding and how it relates to polar codes. A central issue is the computation cutoff rate , which prevents successive decoding from reaching capacity.
He described Pinsker’s “concatenated” construction of convolutional encoders around a block code, which is capacity-achieving but inefficient, and Massey’s 1981 construction of codes for the quaternary erasure channel which decomposes the QEC into two parallel BECs whose noise is correlated (you just relabel the 4 inputs with 2 bits and treat the two bits as going through parallel BECs). This is efficient, increases , but is not enough to get to capacity. However, in a sense, Massey’s construction is like doing one step in polar codes, and combining this with Pinkser’s ideas starts getting the flavor of the channel polarization effect.