Since the landmark work of Shannon in 1948, error-correcting codes have gained widespread use in communication systems. However, the question of obtaining efficient codes that get arbitrarily close to Shannon capacity with polynomial complexity had remained open for decades. In 2008, Arıkan introduced the technique of channel polarization as a means of constructing explicit capacity-achieving error-correcting codes known as polar codes. A subsequent work of Guruswami and Xia established that for binary-input symmetric memoryless channels, polar codes allow communication rates within epsilon of the Shannon capacity with block length and encoding and decoding complexities all bounded polynomially in 1/epsilon. Polar codes are, therefore, the first explicit construction with such provable guarantees.

However, the question of obtaining similar provable guarantees for q-ary polar codes has remained open. In this work, we resolve this question by extending the result of Guruswami and Xia to q-ary codes. Our high level approach is to do a direct analysis of the convergence rate to capacity by proving an entropic inequality over prime alphabets. Such an inequality was implicit and straightfoward in the q=2 case, as the extremal case of the inequality is known, but for other prime q, the inequality is more subtle due to the lack of a simple characterization of the extremal cases. The polarization result for prime q is then used to obtain the general result for all q by splitting a communication channel into multiple channels over prime alphabets and polarizing each channel separately.

This is joint work with Venkatesan Guruswami.