On the construction of polar codes for channels with moderate input alphabet sizes

Current deterministic algorithms for the construction of polar codes cannot be argued to be practical for channels with input alphabets of moderate size. In this paper, we show that any construction algorithm which follows the paradigm of “degrading after each polarization step” will inherently be impractical with respect to a certain “hard” underlying channel having an input alphabet of moderate size. This result also sheds light on why the construction of LDPC codes using density evolution is impractical for channels with moderate sized input alphabets.