Consider a channel W with input alphabet X and output alphabet Y. Suppose Y is large and thus we would like to approximate W by a new channel W’ with the same input alphabet X, and a reduced output alphabet Y’.
Suppose we further require that W’ is upgraded with respect to W.
This problem arises naturally when constructing polar codes in the presence of a wiretap. Moreover, it provides an upper bound on the transmission rate of an error-correcting polar code.
In this talk, we present an algorithm to build an upgraded channel W’ which is a good approximation to W, in the sense that the capacity difference between W’ and W is O((1/|Y’|)^(1/|X|)).
Joint work with Ido Tal.