# Technical Program

## Paper Detail

Paper Title Dynamic Programming for Quantization of q-ary Input Discrete Memoryless Channels MO3.R7.1 Xuan He, Kui Cai, Wentu Song, Zhen Mei, Singapore University of Technology and Design, Singapore Network Information Theory Bièvre, Level 5 Monday, 08 July, 14:30 - 16:10 Monday, 08 July, 14:30 - 14:50 Click here to download the manuscript 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.