2019/01/07 by Xuan He, Kui Cai, He, Xuan +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1901.01659
openalex publication_date 2019/01/07 · openalex created_date 2021/03/01 · openalex updated_date 2026/07/28
In this paper, 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)2 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 (N2 - M2)). 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.