Codes on Graphs and More

Abstract

Modern communication systems strive to achieve reliable and efficient information transmission and storage with affordable complexity. Hence, efficient low-complexity channel codes providing low probabilities for erroneous receptions are needed. Interpreting codes as graphs and graphs as codes opens new perspectives for constructing such channel codes. Low-density parity-check (LDPC) codes are one of the most recent examples of codes defined on graphs, providing a better bit error probability than other block codes, given the same decoding complexity.



After an introduction to coding theory, different graphical representations for channel codes are reviewed. Based on ideas from graph theory, new algorithms are introduced to iteratively search for LDPC block codes with large girth and to determine their minimum distance. In particular, new LDPC block codes of different rates and with girth up to 24 are presented. Woven convolutional codes are introduced as a generalization of graph-based codes and an asymptotic bound on their free distance, namely, the Costello lower bound, is proven. Moreover, promising examples of woven convolutional codes are given, including a rate 5/20 code with overall constraint length 67 and free distance 120.



The remaining part of this dissertation focuses on basic properties of convolutional codes. First, a recurrent equation to determine a closed form expression of the exact decoding bit error probability for convolutional codes is presented. The obtained closed form expression is evaluated for various realizations of encoders, including rate 1/2 and 2/3 encoders, of as many as 16 states. Moreover, MacWilliams-type identities are revisited and a recursion for sequences of spectra of truncated as well as tailbitten convolutional codes and their duals is derived. Finally, the dissertation is concluded with exhaustive searches for convolutional codes of various rates with either optimum free distance or optimum distance profile, extending previously published results.

Abstract (Swedish)

Popular Abstract in Swedish

``Att fela ör mönskligt...'' är början på en sentens som antyder att det krävs någit ytöver det mänskliga för att korrigera fel; sanningen är att det är lika naturligt för människan at korrigera fel som det är att fela, vilket belyses i detta stycke. Trots ett flertal skrivfel är innebörden av texten entydig. Detta beror naturligtvis på att meningsfull svensk text svarar mot endast en liten andel av alla tänkbara kombinationer av symboler (bokstäver och skiljetecken). Då vi ser en följd av symboler, så ``avkodar'' vi automatiskt följden till den ``närmaste'' meningsfulla texten. Svensk text innehåller ungefär tre gånger så många symboler jämfört med vad som krävs för att förmedla dess innehåll. Skillnaden kallas språkets redundans.



Vid överföring av binära sekvenser kan motsvarande feltolerans erhållas. Vi tillför extra symboler (redundans) på ett väldefinierat sätt. Därigenom kommer olika ``meningsfulla'' sekvenser, kodord, att skilja sig åt i tillräckligt många positioner för att vi, då vi mottager en sekvens med ett rimligt antal felaktiga bitar, skall kunna extrahera vår ursprungliga sekvens.



Kodningsteorin har bidragit till en formalisering och ett praktiskt förverkligande av felkorrigeringsprocessen. Den är ett delområde inom den av Claude E. Shannon 1948 grundade informationsteorin, som utgör grundvalen för all telekommunikation. Shannon visade bl a att vi genom kodning kan uppnå godtycklig tillförlitlighet vid kommunikation över en kanal utsatt för störningar om och endast om datahastigheten understiger en för kanalen karakteristisk parameter, kanalkapaciteten.



Kodning kan utföras på olika sätt. Det finns två huvudklasser av koder, nämligen blockkoder och faltningskoder. I denna avhandling har vi konstruerat och analyserat både block- och faltningskoder baserade på grafer. Dessa koder är mycket kraftfulla och lämpar sig för iterativ avkodning. Koder över grafer är ett ``hett'' forskningsområde. Vi kan även gå den omvända vägen och konstruera optimala grafer genom att utgå från koder.



Avhandlingen är teoretisk med inslag av simuleringar som vi gör dels för att undersöka prestanda men ofta för att vässa vår intuition. Teoretisk kodningsforskning har resulterat i tillämpningar som CD-spelare (kodning medför att återgivningen trots smärre defekter i skivan blir exakt den avsedda), mobiltelefoni (kodning medför att det krävs avsevärt lägre sändareffekt för samma ljudkvalitet, vilket möjliggör mindre apparater), modem (kodning möjliggör väsentligt högre datahastigheter), satellitkommunikation (utan kodning skulle antennerna bli orimligt stora) etc. Dessa tillämpningar har kunnat realiseras tack vare att den dramatiska utvecklingen inom mikroelektroniken möjliggjort implementeringar av mycket avancerade system.

• author: Hug, Florian
• supervisor: Rolf Johannesson
• opponent: Professor Emeritus Costello, Jr., Daniel J., Department of Electrical Engineering, University of Notre Dame, USA
• organization: Department of Electrical and Information Technology; Information Theory-lup-obsolete (research group)
• publishing date: 2012
• type: Thesis
• publication status: published
• subject: Electrical Engineering, Electronic Engineering, Information Engineering
• keywords: convolutional codes, woven graph codes, Low-density parity-check (LDPC) codes, tailbiting codes, bit error probability, MacWilliams Identity
• in: Series of licentiate and doctoral dissertations
• pages: 198 pages
• defense location: Lecture hall E:1406, E-building, Ole Römers väg 3, Lund University Faculty of Engineering
• defense date: 2012-05-16 10:15:00
• ISSN: 1654-790X
• ISBN: 978-91-7473-284-9
• language: English
• LU publication?: yes
• id: 285413fb-05d9-431f-9907-534d636738e3 (old id 2439721)
• date added to LUP: 2016-04-04 09:26:29
• date last changed: 2019-05-24 08:39:59