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

Loading...
Thumbnail Image

Authors

Cohen, Adam

Date

2008-12-09T20:39:51Z

Type

thesis

Language

eng

Keyword

Channel Coding , Linear Programming Decoding , LP decoding , Polya Channel , Joint Source-Channel Coding , Non-Uniform Sources , Channels With Memory

Research Projects

Organizational Units

Journal Issue

Alternative Title

Abstract

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.

Description

Thesis (Master, Mathematics & Statistics) -- Queen's University, 2008-12-08 16:24:43.358

Citation

Publisher

License

This 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.

Journal

Volume

Issue

PubMed ID

External DOI

ISSN

EISSN