Name
Title | ||
|---|---|---|
Quantization of binary input DMC at optimal mutual information using constrained shortest path problem |
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]. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/ICT.2015.7124674 | International Conference on Telecommunications |
Keywords | Field | DocType |
channel quantization, hop constrained single source shortest path problem, k-hop shortest path problem, Bellman-Ford algorithm, dynamic programming, binary input DMC, optimal mutual information | Dynamic programming,Discrete mathematics,Mathematical optimization,Algorithm design,Vertex (geometry),Shortest path problem,Computer science,Real-time computing,Mutual information,Quantization (signal processing),Asymptotically optimal algorithm,Binary number | Conference |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vangala, H. | 1 | 4 | 1.14 |
| Emanuele Viterbo | 2 | 1638 | 191.54 |
| Yi Hong | 3 | 621 | 45.07 |