A Linear-Programming Approach to The Design of LDPC Codes for Non-Uniform Channels

We propose a linear-programming approach to the design of low-density parity-check codes for non-uniform channels, i.e., when different bits of the codeword experience different channel parameters. Non-uniform channels are encountered in many communication systems, e.g., in a network that different packets are sent through parallel routes; in orthogonal frequency division multiplexing, where the codeword bits are modulated in different frequency bins with different SNR; also in multi-input multi-output systems, where different channel pairs have different parameters. We formulate the problem of optimizing the rate of an irregular low-density parity-check code, with guaranteed convergence over such a channel, as an iterative linear-programming. The number of design-parameters for code-design over non-uniform channels is much greater than the number of design-parameters in conventional channels. Therefore, search-based optimization methods are impractical. As a result, a linear-programming approach is significantly more efficient. The methodology of this paper is directly applicable to all decoding algorithms for which an exact or accurate-enough one-dimensional analysis is possible. For other decoding algorithms, we show that the method can still be applied after minor modifications.