Random LDPC and Digital Fountains
Research: Zoomable User Interfaces - Multiple Description Coding - Audio Adaptive Playout - Peer2Peer - LDPC/DF - BioElectronic
Teaching: MicroElectronics (UniBG) - MultiMedia Coding (UniMI) - Thesis projects
Miscellanea: About me - Remarks - BlogDownloadDistributed virtual HDD based on digital fountains (pdf 4.4 Mb) in-itinere decoding for Raptor codes: matrix evolution (avi 1.9 Mb) parallel decoding for random (avi 8.2 Mb) and Raptor (avi 4.4 Mb) Partners
| LDPC Digital Fountains Random parity codesParity bits are created by xoring randomly selected data bits. This codes are rateless because parity bits can be continuously generated on a per-need basis. Error correctionAs an example a simple error correction algorithm will be illustrated: hard-decision majority voting.
The loop is repeat until all checks are satisfied (no flipping in step 2) or until a maximum number of iterations is reached. A more sophisticated algorithm uses soft values. E.g. floating point values ranging from -1 (certainly zero), 0 (maximum uncertainty), to +1 (certainly one). Erasure recoveryAs an example a simple erasure recovery algorithm will be described: message passing. Each parity bit form a group with its connected data bits.
When one data bit is recovered, it can happen that for some other parity bit only one (different) data bit is missing. In this case the recovery process can continue until all data bits are recovered or until nothing more can be done (the decoder gets stuck). A more sophisticated algorithm solve the corresponding equation system using Gauss elimination. Erased data bits are the unknowns. Each parity represents a known term. As many (linearly independent) known terms as unknowns are needed to solve the system. The decoder never gets stuck but the number of computations can be very large (cubic complexity). Several variations have been developed:
Random fountains, LT/Raptor codes | Other ResourcesDavid MacKay review of digital fountain codes papers, presentation Digital Fountain (DF), LT/Raptor codes Developers
Antonella Citrano (PoliTO) Michele Bologna (UniBG) Andrea Rota (UniBG) Ruben Lino VIlla (PoliMI) Raffaele Riva (PoliMI) |
Created: 29th April 2008. Updated: 20th October 2008.