The application of Probabilistic Graphical Models to Raptor codes over Binary Input Memoryless Symmetric Channel models
Date
2016-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Raptor codes are Forward Error Correction (FEC) codes that fall under the
class of Fountain codes. This class of code can reach data-transmission rates close to the capacity of the Binary Erasure Channels (BECs). It has consequently
been researched and refined for deterministic decoding over these channels. Raptor codes are ideal for communication over the internet as the internet is a realisation of the BEC. This work investigates the use of Raptor codes for probabilistic decoding, assessing their performance over the Binary Symmetric Channel (BSC) and the Binary Additive White Gaussian Noise
Channel (BAWGNC).
Extensive consideration is given to the Belief Propagation (BP) algorithm and Probabilistic Graphical Models (PGMs) - tools of inference that are essential
to the decoding of FECs codes. Focus is given to the application of the Factor Graph (FG), the Cluster graph (CG), and the Junction Tree (JT).
Furthermore, attention is given to how the BP-update rules may be transformed in order to avoid computation over large distributions. The way in which two graph-altering algorithms may improve the decoding success rate, i.e., the Tree-structure Expectation Propagation (TEP) and the Inactivation Decoding (ID) algorithms, is also shown. These algorithms are simulated and
the results analysed.
AFRIKAANSE OPSOMMING: Raptor-kodes is ’n tipe voorwaarde-foutkorreksiekode wat as ’n Fontein-kode geklassifiseer word. Hierdie klas van kodes kan datatransmissie-tempos na aan die kapasiteit van die binêre afskawing-kanale bereik. Dit is gevolglik nagevors en verfyn vir bepalingsdekodering oor hierdie klas van kanale. Raptor-kodes is ideaal vir kommunikasie oor die internet aangesien die internet ’n realisasie van die binêre afskawing-kanaal verteenwoordig. Hierdie werk ondersoek die gebruik van Raptor-kodes vir waarskynlikheidsdekodering en evalueer sy prestasie oor die binêre simmetriese kanaal en die binêre-toevoeging wit Gaussiese ruis-kanaal. Uitgebreide oorweging is gebied aan die oortuigingsvoortplanting-algoritme en waarskeinlikheidsgrafiese modelle; instrumente van afleiding wat noodsaaklik vir die dekodering van voorwaarde-foutkorreksie-kodes is. Fokus word gebied aan die toepassing van die faktorgrafiek, die bundelgrafiek, en die aansluitingsboom. Verder word dit behandel hoe die oortuigingsvoortplantingaanpassingsreëls omskep kan word ten einde berekening oor groot uitkerings te vermy. Dit word ook behandel hoe twee grafiekverandering-algoritmes die dekodering-suksessyfer kan verbeter, dit wil sê, die boom-gewysde verwagtingsvoortplanting- en deaktiveringsdekodering-algoritmes. Hierdie algoritmes is gesimuleer en die resultate is ontleed.
AFRIKAANSE OPSOMMING: Raptor-kodes is ’n tipe voorwaarde-foutkorreksiekode wat as ’n Fontein-kode geklassifiseer word. Hierdie klas van kodes kan datatransmissie-tempos na aan die kapasiteit van die binêre afskawing-kanale bereik. Dit is gevolglik nagevors en verfyn vir bepalingsdekodering oor hierdie klas van kanale. Raptor-kodes is ideaal vir kommunikasie oor die internet aangesien die internet ’n realisasie van die binêre afskawing-kanaal verteenwoordig. Hierdie werk ondersoek die gebruik van Raptor-kodes vir waarskynlikheidsdekodering en evalueer sy prestasie oor die binêre simmetriese kanaal en die binêre-toevoeging wit Gaussiese ruis-kanaal. Uitgebreide oorweging is gebied aan die oortuigingsvoortplanting-algoritme en waarskeinlikheidsgrafiese modelle; instrumente van afleiding wat noodsaaklik vir die dekodering van voorwaarde-foutkorreksie-kodes is. Fokus word gebied aan die toepassing van die faktorgrafiek, die bundelgrafiek, en die aansluitingsboom. Verder word dit behandel hoe die oortuigingsvoortplantingaanpassingsreëls omskep kan word ten einde berekening oor groot uitkerings te vermy. Dit word ook behandel hoe twee grafiekverandering-algoritmes die dekodering-suksessyfer kan verbeter, dit wil sê, die boom-gewysde verwagtingsvoortplanting- en deaktiveringsdekodering-algoritmes. Hierdie algoritmes is gesimuleer en die resultate is ontleed.
Description
Thesis (MEng)--Stellenbosch University, 2016.
Keywords
Probabilistic graphical models, UCTD, Graphical modeling (Statistics), Algorithm, probabilistic graphs, Binary system (Mathematics), Symmetrical components (Electric engineering)