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

dc.contributor.authorCohen, Adamen
dc.contributor.departmentMathematics and Statisticsen
dc.contributor.supervisorAlajaji, Fadyen
dc.contributor.supervisorKashyap, Navinen
dc.contributor.supervisorTakahara, Glenen
dc.date2008-12-08 16:24:43.358
dc.date.accessioned2008-12-09T20:39:51Z
dc.date.available2008-12-09T20:39:51Z
dc.date.issued2008-12-09T20:39:51Z
dc.degree.grantorQueen's University at Kingstonen
dc.descriptionThesis (Master, Mathematics & Statistics) -- Queen's University, 2008-12-08 16:24:43.358en
dc.description.abstractLinear 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.en
dc.description.degreeM.Sc.en
dc.format.extent490608 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1974/1605
dc.language.isoengen
dc.relation.ispartofseriesCanadian thesesen
dc.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.en
dc.subjectChannel Codingen
dc.subjectLinear Programming Decodingen
dc.subjectLP decodingen
dc.subjectPolya Channelen
dc.subjectJoint Source-Channel Codingen
dc.subjectNon-Uniform Sourcesen
dc.subjectChannels With Memoryen
dc.titleLinear Programming Decoding for Non-Uniform Sources and for Binary Channels With Memoryen
dc.typethesisen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Cohen_Adam_M_200812_MSc.pdf
Size:
479.11 KB
Format:
Adobe Portable Document Format