Return to search

Linear Programming Decoding for Non-Uniform Sources and for Binary Channels With Memory

Linear programming (LP) decoding of low-density parity-check codes was introduced by Feldman et al. in [1]. In his formulation it is assumed that communication takes place over a memoryless channel and that the source is uniform. Here, we extend the LP decoding paradigm by studying its application to scenarios with source non-uniformity and to decoding over channels with memory. We develop two decoders for the scenario of non-uniform memoryless sources transmitted over memoryless channels. The first decoder uses a modified linear cost function which incorporates the a-priori source information and works with systematic codes. The second decoder differs by using non-systematic codes obtained by puncturing lower rate systematic codes and using an “extended decoding polytope.” Simulations show that the modified decoders yield gains over the standard LP decoder. Next, LP decoding is considered for two channels with memory: the binary additive Markov noise channel and the infinite-memory non-ergodic Polya-contagion channel. For the Markov channel, no linear cost function corresponding to maximum likelihood (ML) decoding could be obtained and hence it is unclear how to proceed. For the Polya channel, two LP-based decoders are developed. The first is derived in a straightforward manner from the ML decoding rule of [2]. The second decoder relies on a simplification of the same ML decoding rule which holds for codes containing the all-ones codeword. Simulations are performed for both decoders with regular and irregular LDPC codes and demonstrate relatively good performance with respect to the channel epsilon-capacity. / Thesis (Master, Mathematics & Statistics) -- Queen's University, 2008-12-08 16:24:43.358

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OKQ.1974/1605
Date09 December 2008
CreatorsCohen, ADAM
ContributorsQueen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.))
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
Format490608 bytes, application/pdf
RightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
RelationCanadian theses

Page generated in 0.0019 seconds