Abstract
We consider the problem of reducing the output alphabet size of a binary input discrete memoryless channel from M to K at minimal loss in mutual information. It was found in [1] that this problem can be solved optimally using a dynamic programming approach, which takes only O(M3) worst-case complexity. We first present a new formulation of the problem, as a K-hop single source shortest path problem (K-hop SSSPP) in a graph G(V, E) with M+1 vertices and (M2 (M+1)-K2 (K-1)) edges. This new formulation can in the future serve as a basis to several algorithms on channel quantization. Then we found that the algorithm in [1] has asymptotically optimal complexity in the class of path-comparison based algorithms for general graphs. This implies that we can only expect a constant factor improvement in complexity with any other optimal quantizers, until more specific properties of the graph such as edges and their cost-structure with concave mutual information function are exploited in designing the algorithms (e.g. [2], [3]). We finally present a new optimal quantizer algorithm based on the classic Bellman-Ford algorithm on G, achieving a constant factor improvement in complexity. We claim that our algorithm will be about 50 faster than [1].
Original language | English |
---|---|
Title of host publication | 22nd IEEE International Conference on Telecommunications (ICT 2015) |
Editors | Abbas Jamalipour, Shahrokh Valaee |
Place of Publication | Piscataway NJ USA |
Publisher | IEEE, Institute of Electrical and Electronics Engineers |
Pages | 151 - 155 |
Number of pages | 5 |
ISBN (Print) | 9781479980789 |
DOIs | |
Publication status | Published - 2015 |
Event | IEEE International Conference on Telecommunications 2015 - Sydney, Australia Duration: 27 Apr 2015 → 29 Apr 2015 Conference number: 22nd https://ieeexplore.ieee.org/xpl/conhome/7109533/proceeding (Proceedings) |
Conference
Conference | IEEE International Conference on Telecommunications 2015 |
---|---|
Abbreviated title | ICT 2015 |
Country/Territory | Australia |
City | Sydney |
Period | 27/04/15 → 29/04/15 |
Internet address |