Title :
Capacity-achieving codes for channels with memory with maximum-likelihood decoding
Author :
Jung Hyun Bae ; Anastasopoulos, Achilleas
Author_Institution :
Electr. Eng. & Comput. Sci. Dept., Univ. of Michigan, Ann Arbor, MI, USA
fDate :
June 28 2009-July 3 2009
Abstract :
Codes on sparse graphs have been shown to achieve remarkable performance in point-to-point channels with low decoding complexity. Most of the results in this area are based on experimental evidence and/or approximate analysis. The question of whether codes on sparse graphs can achieve the capacity of noisy channels with iterative decoding is still open, and has only been conclusively and positively answered for the binary erasure channel. On the other hand, codes on sparse graphs have been proven to achieve the capacity of memoryless, binary-input, output-symmetric channels with finite graphical complexity per information bit when maximum likelihood (ML) decoding is performed. In this paper, we consider transmission over finite-state channels (FSCs). We derive upper bounds on the average error probability of code ensembles with ML decoding. Based on these bounds we show that codes on sparse graphs can achieve the symmetric information rate (SIR) of FSCs, which is the maximum achievable rate with independently and uniformly distributed input sequences. In order to achieve rates beyond the SIR, we consider a simple quantization scheme that when applied to ensembles of codes on sparse graphs induces a Markov distribution on the transmitted sequence. By deriving average error probability bounds for these quantized code ensembles, we prove that they can achieve the information rates corresponding to the induced Markov distribution, and thus approach the FSC capacity.
Keywords :
Markov processes; graph theory; iterative decoding; maximum likelihood decoding; Markov distribution; average error probability; capacity-achieving codes; decoding complexity; finite-state channels; iterative decoding; maximum-likelihood decoding; point-to-point channels; sparse graphs; symmetric information rate; Channel capacity; Error probability; Information rates; Iterative decoding; Maximum likelihood decoding; Parity check codes; Performance analysis; Power capacitors; Quantization; Upper bound;
Conference_Titel :
Information Theory, 2009. ISIT 2009. IEEE International Symposium on
Conference_Location :
Seoul
Print_ISBN :
978-1-4244-4312-3
Electronic_ISBN :
978-1-4244-4313-0
DOI :
10.1109/ISIT.2009.5205692