Dynamic Programming for Sequential Deterministic Quantization of Discrete Memoryless Channels
Xuan He, Kui Cai, Wentu Song, Zhen Mei
Abstract
In this article, under a general cost function C, we present a dynamic programming (DP) method to obtain an optimal sequential deterministic quantizer (SDQ) for q-ary input discrete memoryless channel (DMC). The DP method has complexity O(q (N-M) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> M), where N and M are the alphabet sizes of the DMC output and quantizer output, respectively. Then, starting from the quadrangle inequality, two techniques are applied to reduce the DP method's complexity. One technique makes use of the Shor-Moran-Aggarwal-Wilber-Klawe (SMAWK) algorithm and achieves complexity O(q (N-M) M). The other technique is much easier to be implemented and achieves complexity O(q (N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> - M <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> )). We further derive a sufficient condition under which the optimal SDQ is optimal among all quantizers and the two techniques are applicable. This generalizes the results in the literature for binary-input DMC. Next, we show that the cost function of α-mutual information ( α-MI)-maximizing quantizer belongs to the category of C. We further prove that under a weaker condition than the sufficient condition we derived, the aforementioned two techniques are applicable to the design of α-MI-maximizing quantizer. Finally, we illustrate the particular application of our design method to practical pulse-amplitude modulation systems.