Quantization of Binary-Input Discrete Memoryless Channels, with Applications to LDPC Decoding
Preprint
Abstract
The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. The optimal quantizer, in the sense of maximizing mutual information between the channel input and the quantizer output, may be found by an algorithm with complexity which is quadratic in the number of channel outputs. This is a concave optimization problem, and results from the field of concave optimization are invoked. The quantizer design algorithm is a realization of a dynamic program. Then, this algorithm is applied to the design of message-passing decoders for low-density parity-check codes, over arbitrary discrete memoryless channels. A general, systematic method to find message-passing decoding maps which maximize mutual information at each iteration is given. This may contrasted with existing quantized message-passing algorithms which are heuristically derived. The method finds message-passing decoding maps similar to those given by Richardson and Urbanke's Algorithm E. Using four bits per message, noise thresholds similar to belief-propagation decoding are obtained.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- On the limits of communication with low-precision analog-to-digital conversion at the receiverIEEE Transactions on Communications, 2009
- Design of LDPC decoders for improved low error rate performance: quantization and algorithm choicesIEEE Transactions on Communications, 2009
- New insights into weighted bit-flipping decodingIEEE Transactions on Communications, 2009
- Density Evolution for Asymmetric Memoryless ChannelsIEEE Transactions on Information Theory, 2005
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Decoding under integer metrics constraintsIEEE Transactions on Communications, 1995
- On optimal soft-decision demodulationIEEE Transactions on Information Theory, 1976
- Computation of channel capacity and rate-distortion functionsIEEE Transactions on Information Theory, 1972
- An algorithm for computing the capacity of arbitrary discrete memoryless channelsIEEE Transactions on Information Theory, 1972
- Modulation and demodulation for probabilistic codingIEEE Transactions on Information Theory, 1966