Trapping Sets in Fountain Codes over Noisy Channels
Loading...
Authors
Orozco, Vivian
Date
2009-11-04T15:40:12Z
Type
thesis
Language
eng
Keyword
rateless codes , Fountain codes , belief propagation algorithm , trapping sets , Luby Transform (LT) codes , LDGM codes , Raptor codes , early termination methods , stopping criteria , graph codes
Alternative Title
Abstract
Fountain codes have demonstrated great results for the binary erasure channel and have already been incorporated into several international standards to recover lost packets at the application layer. These include multimedia broadcast/multicast sessions and digital video broadcasting on global internet-protocol. The rateless property of Fountain codes holds great promise for noisy channels. These are more sophisticated mathematical models representing errors on communications links rather than only erasures. The practical implementation of Fountain codes for these channels, however, is hampered by high decoding cost and delay.
In this work we study trapping sets in Fountain codes over noisy channels and their effect on the decoding process. While trapping sets have received much attention for low-density parity-check (LDPC) codes, to our knowledge they have never been fully explored for Fountain codes. Our study takes into account the different code structure and the dynamic nature of Fountain codes. We show that 'error-free' trapping sets exist for Fountain codes. When the decoder is caught in an error-free trapping set it actually has the correct message estimate, but is unable to detect this is the case. Thus, the decoding process continues, increasing the decoding cost and delay for naught. The decoding process for rateless codes consists of one or more decoding attempts. We show that trapping sets may reappear as part of other trapping sets on subsequent decoding attempts or be defeated by the reception of more symbols. Based on our observations we propose early termination methods that use trapping set detection to obtain improvements in realized rate, latency, and decoding cost for Fountain codes.
Description
Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2009-10-29 14:33:06.548
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.