Technical Program

Paper Detail

Paper Title Dynamic Programming for Quantization of q-ary Input Discrete Memoryless Channels
Paper IdentifierMO3.R7.1
Authors Xuan He, Kui Cai, Wentu Song, Zhen Mei, Singapore University of Technology and Design, Singapore
Session Network Information Theory
Location Bièvre, Level 5
Session Time Monday, 08 July, 14:30 - 16:10
Presentation Time Monday, 08 July, 14:30 - 14:50
Manuscript  Click here to download the manuscript
Abstract In this paper, we present a general framework of applying dynamic programming (DP) to the sequential deterministic quantization for discrete memoryless channels (DMCs) with pre-labelled outputs. The DP has complexity $O(q (N-M)^2 M)$, where $q$, $N$, and $M$ are alphabet sizes of the DMC input, DMC output, and the quantizer output, respectively. Then, starting from the quadrangle inequality (QI), we apply two techniques to reduce the DP's complexity. One technique makes use of the SMAWK algorithm with complexity $O(q (N-M) M)$, while the other technique is much easier to be implemented and has complexity $O(q (N^2 - M^2))$. Moreover, we give a sufficient condition on the channel transition probability, under which the two low-complexity techniques can be applied for designing quantizers that maximize the $\alpha$-mutual information, which is a generalized objective function for channel quantization. This condition works for the general $q$-ary input case, including the previous work for $q = 2$ as a subcase.