124
Ecole Doctorale d’Informatique Télécommunications et Electronique de Paris Ecole Nationale Supèrieure des Télécommunications Thèse Présentée pour obtenir le grade de docteur de l’École Nationale Supérieure des Télécommunications Spécialité : Electronique et Communications Amira ALLOUM Sujet : C ONSTRUCTION AND ANALYSIS OF N ON -S YSTEMATIC C ODES ON G RAPH FOR R EDUNDANT D ATA .

Phd dissertation

Embed Size (px)

DESCRIPTION

Construction and Analysis of Non Systematic Codes on Graph for Redundant data.

Citation preview

Page 1: Phd dissertation

Ecole Doctorale d’Informatique

Télécommunications et Electroniquede Paris

Ecole Nationale Supèrieure des Télécommunications

Thèse

Présentée pour obtenir le grade de docteurde l’École Nationale Supérieure des Télécommunications

Spécialité : Electronique et Communications

Amira ALLOUM

Sujet :

CONSTRUCTION AND ANALYSIS OF

NON-SYSTEMATIC CODES ON GRAPH FOR

REDUNDANT DATA.

Page 2: Phd dissertation
Page 3: Phd dissertation

Contents

Contents i

List of figures iii

List of tables v

Acronyms vii

Introduction 1

1 Non Systematic Constructions of Codes on Graph for Redundant data 5

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.1 Motivation and Related Work . . . . . . . . . . . . . . . . . . . . . . 61.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 SystemModel and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Information Theoretical Limits for Non Uniform Sources . . . . . . . . . . 9

1.3.1 AWGN Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.2 Binary Erasure Channel . . . . . . . . . . . . . . . . . . . . . . . . . 111.3.3 Binary Symmetric Channel . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Design Principles for Non Systematic Codes on Graph . . . . . . . . . . . 131.4.1 Preliminaries on LDPC codes . . . . . . . . . . . . . . . . . . . . . . 151.4.2 Mackay-Neal Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.4.3 Non Systematic LDPC Framework . . . . . . . . . . . . . . . . . . . 18

1.4.3.1 Scramble-LDPC Construction . . . . . . . . . . . . . . . . 191.4.3.2 Split-LDPC Construction . . . . . . . . . . . . . . . . . . . 20

1.4.4 Information Theoretical Comparison of Splitting and Scrambling 221.5 Source Controlled Sum-Product Decoding . . . . . . . . . . . . . . . . . . 241.6 Multi Edge classification to the Non Systematic LDPC Codes . . . . . . . . 271.7 Simulation and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2 Density Evolution Analysis for Split-LDPC Codes 35

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.1.1 Motivation and Related Work . . . . . . . . . . . . . . . . . . . . . . 362.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.2 Preliminaries on Density Evolution . . . . . . . . . . . . . . . . . . . . . . . 382.2.1 Concentration and The local tree assumption . . . . . . . . . . . . . 382.2.2 Symmetry Assumptions and the All one Codeword Restriction . . 39

i

Page 4: Phd dissertation

CONTENTS

2.2.3 General Statement of Density Evolution . . . . . . . . . . . . . . . 402.3 Statement of Split-LDPC Density Evolution . . . . . . . . . . . . . . . . . . 432.4 Analytic Properties of Split-LDPC Density Evolution . . . . . . . . . . . . 47

2.4.1 The Consistency Condition . . . . . . . . . . . . . . . . . . . . . . . 472.4.2 Monotonicity and Convergence to Fixed Points . . . . . . . . . . . 492.4.3 Thresholds and Density Evolution Fixed Points . . . . . . . . . . . 50

2.5 The Stability Analysis of Split-LDPC Density Evolution . . . . . . . . . . . 512.5.1 The Stability Condition for Systematic LDPC Codes : . . . . . . . . 522.5.2 The Stability Condition for the Non Systematic Split-LDPC Code . 54

2.6 Simulations and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3 Exit Chart Analysis and Design of Irregular Split-LDPC Codes 65

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.1.1 Motivation and Related Work . . . . . . . . . . . . . . . . . . . . . . 663.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.2 Preliminaries on the EXIT Chart Analysis of LDPC Codes . . . . . . . . . . 683.2.1 The EXIT Charts Principle . . . . . . . . . . . . . . . . . . . . . . . . 693.2.2 The Semi-Gaussian Approximation and the Related Metrics . . . . 703.2.3 Analysis of Regular Structures . . . . . . . . . . . . . . . . . . . . . 723.2.4 Analysis of Irregular Structures . . . . . . . . . . . . . . . . . . . . . 73

3.3 The Two Dimensional EXIT Charts Analysis of Split-LDPC Codes . . . . . 753.3.1 Analysis of Regular Structures . . . . . . . . . . . . . . . . . . . . . 793.3.2 Analysis of Irregular Structures . . . . . . . . . . . . . . . . . . . . . 81

3.4 Design of Irregular Split LDPC codes . . . . . . . . . . . . . . . . . . . . . . 863.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4 Enhancing Iterative Decoding via EM Source-Channel Estimation 91

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 924.1.1 Motivation and Related Work . . . . . . . . . . . . . . . . . . . . . . 924.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4.2 SystemModel and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . 944.2.1 Source State Information . . . . . . . . . . . . . . . . . . . . . . . . . 954.2.2 Channel State Information . . . . . . . . . . . . . . . . . . . . . . . . 95

4.3 General Statement of the EM Algorithm . . . . . . . . . . . . . . . . . . . . 964.4 EM application to BECBSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.4.1 Expectation step on BECBSC . . . . . . . . . . . . . . . . . . . . . . 974.4.2 Maximization step on BECBSC . . . . . . . . . . . . . . . . . . . . . 984.4.3 Two simple special cases, BEC and BSC . . . . . . . . . . . . . . . . 99

4.5 EM application to AWGN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 994.5.1 Expectation step on AWGN . . . . . . . . . . . . . . . . . . . . . . . 994.5.2 Maximization step on AWGN . . . . . . . . . . . . . . . . . . . . . . 100

4.6 Simulations and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5 Conclusions and Perspectives 103

Bibliography 107

ii

Page 5: Phd dissertation

List of Figures

1.1 Block Diagram for a Source Controlled Channel Coding System . . . . . . 81.2 Minimum achievable Ebr/N0 vs. source entropyHs Coding rateR = 0.5. . 121.3 Minimum Achievable SNR versus Coding Rate in AWGN, Hs = 0.5. . . . 131.4 Capacity limit versus source entropy for BEC and BSC. . . . . . . . . . . . 141.5 Factor Graph of an LDPC Code . . . . . . . . . . . . . . . . . . . . . . . . . 151.6 Mackay-Neal Codes: Block and Tanner Graph descriptions . . . . . . . . . 181.7 General Non-Systematic LDPC Encoding Framework . . . . . . . . . . . . 191.8 Scramble LDPC Tanner Graph and block Diagram Description . . . . . . 201.9 Split-LDPC Tanner Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.10 General Structure of a Split-LDPC Parity Check Matrix . . . . . . . . . . . 221.11 Mutual information vs. Ebr/N0 forHs = 0.5 and coding rates R = 0.5, 0.8 231.12 Minimum achievable Ebr/N0 vs. source entropyHs Coding rate R = 0.8. . 241.13 The local message node to checknode update rule. . . . . . . . . . . . . . . 251.14 The local checknode to bitnode update rule. . . . . . . . . . . . . . . . . . . 261.15 Multi-Edge graphical interpretation of Split and Scramble-LDPC. . . . . . 281.16 Performance of systematic and non systematic LDPC with R = 0.5, µ = 0.1 301.17 Performance of systematic and non systematic LDPC with R = 0.5, µ = 0.2 311.18 Performance of systematic and non systematic LDPC with R = 0.9, µ = 0.1 311.19 The effect of splitter degree variation over Split-LDPC codes with R = 0.5 32

2.1 The tree describing a regular (db, dc) LDPC. . . . . . . . . . . . . . . . . . . 402.2 Tree representation for type-1 messages for rate R = 1/2 split-LDPC. . . . 432.3 Tree representation for type-2 messages for rate R = 1/2 split-LDPC. . . . 442.4 Tree representations for type-3 messages for rate R = 1/2 split-LDPC. . . . 442.5 Consistency of the Splitter Output distribution . . . . . . . . . . . . . . . . 492.6 The equivalent channel that is seen by the core-LDPC . . . . . . . . . . . . 562.7 Threshold versus source entropy variation for the Split-LDPC . . . . . . . 61

3.1 EXIT charts Analysis General Principle. . . . . . . . . . . . . . . . . . . . . 693.2 The evolution of densities at the bitnode output (left) and checknode out-

put(right) for a regular (3, 6) LDPC at 1.18dB. . . . . . . . . . . . . . . . . . 703.3 Elementary GA charts with single Gaussian pdf input for different variable

degrees for a regular LDPC with dc = 6 on an AWGN at SNR = −2.0dB . 723.4 Elementary charts with Gaussian mixture input for the different variable

nodes degrees for an irregular LDPC with ρ6 = 0.7855 ρ7 = 0.2145 andλ(x) = .3266x + .1196x2 + .1839x3 + .3698x4 on an AWGN channel atSNR=-2.0dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

iii

Page 6: Phd dissertation

LIST OF FIGURES

3.5 EXIT charts trajectory with Gaussian mixture input for an irregular LDPCwith ρ6 = 0.7855 ρ7 = 0.2145 and λ(x) = .3266x + .1196x2 + .1839x3 +.3698x4 on an AWGN channel at SNR=-2.0dB. (the tunnel is open). . . . . 74

3.6 Tree representation for type-1 messages for rate R = 1/2 split-LDPC. . . . 753.7 Tree representation for type-2 messages for rate R = 1/2 split-LDPC. . . . 763.8 Tree representations for type-3 messages for rate R = 1/2 split-LDPC. . . . 763.9 Transfer chart F (x, y) without mixtures. Illustration for ds = db = 3, dc =

6, Es

N0= −5.00dB. Input distributions are single Gaussian.EntropyHs = 0.5 79

3.10 Trajectory of error probability near the code threshold over the surfaceassociated to the transfer chart F (x, y) without mixtures. Illustration fords = db = 3, dc = 6, right to the threshold : Es

N0= −5.00dB. Input distribu-

tions are single Gaussian. EntropyHs = 0.5 . . . . . . . . . . . . . . . . . . 803.11 Open tunnel obtained from the EXIT chart of the ds = db = 3, dc = 6

regular split-LDPC with at Es

N0= −5dB , Entropy Hs = 0.5. The tunnel

is made by plotting the trajectory of error probability and its z = x planereflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.12 Transfer chart F (x, y) with mixtures. Illustration for a (ds = 3, db = 3, dc =6) regular LDPC code at Es

N0= −5.00dB. Input distributions are Gaussian

mixtures. Channel initial point at top of the sail. Fixed point of zero errorrate at bottom of the sail.EntropyHs = 0.5 . . . . . . . . . . . . . . . . . . . 82

3.13 Transfer chartF (x, y)with andwithoutmixtures and associated error prob-ability trajectories. Illustration for a regular LDPC code at Es

N0= −5.00dB.

Channel initial point at top of the sail. Fixed point of zero error rate atbottom of the sail.EntropyHs = 0.5 . . . . . . . . . . . . . . . . . . . . . . . 82

3.14 Trajectory of error probability near the code threshold. Illustration for anirregular split LDPC code with λ(x) = 0.3266x + 0.1196x2 + 0.18393x3 +0.36988x4 , ρ(x) = 0.78555x5 + 0.21445x6 . Right to the threshold: Es

N0=

−5.58dB, Threshold=−5.68dB. Final fixed point is 0.EntropyHs = 0.5 . . 833.15 Trajectory of error probability near the code threshold. Illustration for an

irregular split LDPC code with λ(x) = 0.3266x + 0.1196x2 + 0.18393x3 +0.36988x4 , ρ(x) = 0.78555x5 + 0.21445x6 . Left to the threshold: Es

N0=

−5.78dB, Threshold=−5.68dB. Final fixed point is non-zero.EntropyHs =0.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

3.16 Stability of fixed points beyond the code threshold. Illustration for an ir-regular split LDPC code with λ(x) = 0.3266x + 0.1196x2 + 0.18393x3 +0.36988x4 , ρ(x) = 0.78555x5 + 0.21445x6 . Left to the threshold: Es

N0=

−5.78dB, Threshold=−5.68dB. Stable and unstable fixed points.EntropyHs = 0.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.17 Open tunnel obtained from the EXIT chart of an irregular split-LDPC withλ(x) = 0.3266x + 0.1196x2 + 0.18393x3 + 0.36988x4 , ρ(x) = 0.78555x5 +0.21445x6 , at Es

N0= −5.58dB , Entropy Hs = 0.5. The tunnel is made by

plotting the trajectory of error probability and its z = x plane reflection . . 85

4.1 General Model of a coded communication system with EM estimation . . 944.2 General model for the EM source-channel estimation . . . . . . . . . . . . 964.3 Estimated source distribution µ versus EM iterations. . . . . . . . . . . . . 1004.4 EM Performance for the (3,6) LDPC over BEC . . . . . . . . . . . . . . . . . 1014.5 EM Performance for systematic and non-systematic LDPC over AWGN . 102

iv

Page 7: Phd dissertation

List of Tables

1.1 Multinomial description of Split (top) and Scramble (bottom) LDPC . . . 29

2.1 Threshold table for regular Split LDPC with R = Hs = 12 and ds ∈ {3, 5} . 62

2.2 Threshold tables for regular Split-LDPC with ds = 3, R = 12 and Hs ∈ {1, .3} 62

2.3 Threshold table for irregular Split-LDPC with R = Hs = 12 and ds = 3 . . 63

3.1 Error in approximation of threshold (dB) using EXIT chart analysis for var-ious regular split-LDPC codes of Rate one-half with ds = 3 and Hs = 0.5.∆ is the log-ratio quantization step. . . . . . . . . . . . . . . . . . . . . . . . 86

3.2 Threshold table for irregular split LDPC withHs = 12 and ds = 3 . . . . . . 88

v

Page 8: Phd dissertation

LIST OF TABLES

vi

Page 9: Phd dissertation

ACRONYMS

ACRONYMS

Here we list the main acronyms used in this document. The meaning of the acronymis usually indicated once, the first time it appears in the text.

JSCC Joint Source Channel CodingSCCD Source Controlled Channel DecodingLDPC Low Density Parity Check CodeMN Mackay-NealAWGN Additif White Gaussian NoiseBIAWGN Binary Input Additif White Gaussian NoiseBEC Binary Erasure ChannelBSC Binary Symmetric ChannelQLI Quick Look Inpdf Probability density functionpmf Probability mass functioni.i.d independant and idenitcally distributedBPSK Binary Phase Shift KeyingLDGM Low Density Generator MatrixLLR Log Likelihood RatioSNR Signal to Noise RatioDE Density EvolutionEM Expectation MaximizationCSI Channel State InformationSSI Source State InformationBECBSC Binary Symmetric Channel with ErasuresAPP A Posteriori ProbabilityBWT Burrows Wheeler transformEXIT Extrinsic Information TransferMIMO Multi Input Multi OutputGA Gaussian Approximation

vii

Page 10: Phd dissertation

ACRONYMS

viii

Page 11: Phd dissertation

Introduction

In the past decade, the field of Modern Coding Theory has known a focused interestand an intensity of efforts for the design of capacity achieving codes defined on graphsand the analysis of the associated iterative decoding algorithms [52],[72].This excitement for codes on graphs and the iterative techniques was ignited in the

mid-1990s by the excellent performance exhibited by the turbo codes of Berrou andGlavieux[17], and the resuscitated Gallager codes [33].Afterwards, iterative methods have been influencing a wide range of applications

within and beyond communications, allowing the development of sophisticated com-munication systems.Inmost of those communication systems, the channel coding procedures are designed

independently of the source statistics assuming uniformly distributed sources. This ap-proach is justified by the Shannon’s famous separation theorem [83] stating that separatesource channel coding incurs no loss of optimality as long as the entropy of the source isless than the capacity of the channel providing that blocklength goes to infinity.Because of various considerations (such as legacy and the difficulty in adapting uni-

versal data compressors to short-packet transmission systems), certain existing applica-tions do not compress the redundant data prior to channel encoding (including third-generation wireless data transmission systems)[60]. In other applications, such as theGlobal System for Mobile Communications (GSM) second-generation cellular wirelesssystem, the vocoder leaves some residual redundancy prior to channel encoding [111],[64], [108], [60] . In those cases, the signal sent through the channel incorporates redun-dancy due to its channel encoder and the data itself.While Shannon has been establishing the famous separation theorem, he intuited that

any redundancy in the source will usually help if it is utilized at the receiving point [83].In other words, when the residual source redundancy is ignored by the receiver, somelosses are induced and the system performs worse than its potentiality.The first practical embodiment of this idea was the proposal of the Source Controlled

Channel Decoding technique (SCCD) made by Hagenauer in [39] and consisting in ex-ploiting the redundancy as an a priori information during the iterative decoding process.Besides, Shamai and Verdu have shown in [78] that the use of non systematic coding

schemes is more appropriate in presence of redundant sources. This is because thoseconstructions supply the capacity achieving distribution to the channel.In the light of these two pioneering contributions several research directions have

been drawn, where most important concepts encountered during the study of codes ongraphs within the uniform sources assumption are to be carried over to the non uniformcase.Some of the major concerns of those directions are:

1

Page 12: Phd dissertation

INTRODUCTION

• Investigating the new information theoretical limits in presence of redundant sources.

• Designing capacity achieving non-systematic codes on graph.

• Defining associated source controlled iterative decoding algorithms.

• Building analysis tools in order to investigate the asymptotical performance of non-systematic codes in presence of redundancy, and to design the best constructions.

These guidelines meet the challenges of the present thesis, where the purpose is tointroduce the design principles and the analysis tools for a novel class of non systematiclow density parity check codes dedicated to non uniform memoryless sources. In partic-ular, we study the most performant scheme of the class namely the split-LDPC code thatconsist in the concatenation of a pre-coding with an LDPC code [5],[80].In 1997 Mackay and Neal pioneered the field with a class of non systematic codes

called ’MN codes’ and obtained by the scrambling of a low-density generator-matrix[53],[51]. One of the main drawbacks related to MN codes , is that their decoder is specif-ically designed for the binary symmetric channel. Anothermajor proposal has been doneby Alajaji for non systematic parallel turbo-codes in [116].Afterwards, in 2005 G.Shamir and J.J.Boutros have introduced a novel general ap-

proach to design a special class of non systematic low density parity check codes dedi-cated to non uniform memoryless sources. This code family is including MN codes as aparticular case.First, the authors proposed several design configurations based on the concatenation

of a pre-coding or a post-coding with an LDPC code. We went on with further investi-gations and found out that the most performant scheme consist in the concatenation of apre-coding with an LDPC code namely the split-LDPC [5],[80].In this thesis we focus on the design of the split-LDPC codes in presence of redundant

memoryless data; and the asymptotical analysis of the associated source-controlled sum-product decoding.Firstly, we shall investigate the new theoretical limits in presence of non uniform

sources and show theoretically the advantage of non systematic constructions over sys-tematic ones. Then we shall introduce the novel class of non systematic LDPC codes andprove the supremacy in term of performance of splitting structures over all other nonsystematic codes on graph constructions including MN codes.Secondly, we shall perform the asymptotical analysis of split-LDPC codes through

new tools obtained by adapting the classical general theory related to Density Evolutionand EXIT Chart analysis to the split-LDPC case and the non uniform source assumption.Using the tools introduced for the analysis, we shall address the problem of designinggood irregular split-LDPC constructions.Finally, we shall extend the context of our communication setting by considering the

practical scenarios, where the knowledge of the source and channel parameters is im-possible. For so doing, we shall investigate jointly the decoding and the estimation ofthe source and channel parameters, using an iterative estimation technique based on theExpectation Maximization (EM) algorithm.The material covered in this thesis has the special appeal that it unifies many themes

of information theory, coding, and communication.The outline of this thesis is as follows:

2

Page 13: Phd dissertation

INTRODUCTION

• In Chapter 1, we demonstrate using information theory tools why non systematicconstructions show the best theoretical limits in presence of redundancy. In order toattain these limits, we introduce a universal family of non systematic LDPC codesextending Mackay construction and well suited to SCCD sum-product decoding.The proposed configurations are based on the concatenation of a pre-coding or apost-coding with an LDPC code. The precoding module consist in a sparse matrix’scrambler’ or the inverse of a sparse matrix ’splitter’ dedicated to transform the re-dundant data bits into uniformly distributed coded bits . We show how to performa source controlled iterative decoding (SCCD) on the factor graph associated to thenon-systematic LDPC codes. We prove the supremacy in term of performance ofsplitting structures over prior non-systematic LDPC constructions as well as theother realizations of our codes. The material of this chapter is reported in part in [5]and [80].

• Chapter 2 intends to determine the asymptotical performance of the split-LDPCcodes, and evaluate how close are they from the theoretical limits. In this pur-pose, we derive a message-oriented density evolution analysis of the split-LDPCsource controlled sum-product decoding. The basic concepts,features, assumptionsand results of the general theory are conformed to the split-LDPC construction andthe presence of redundant data. The analysis reveals that the split-LDPC construc-tion shows a good asymptotical performance. In order to make our analysis com-plete, we perform a stability analysis of the dynamical system associated to thesplit-LDPC density evolution algorithm. We derive a general stability condition as-sociated to the split-LDPC code and involving the source statistics as well as thesplitter structure. We investigate if the stability of the whole system is related tothe stability of the constituent LDPC code for a considered channel condition. Thematerial of this chapter is reported in part in [5] and [4].

• In Chapter 3, we propose a message oriented two-dimensional EXIT chart analysisfor split-LDPC codes. Our approach is based on the elimination of the Gaussian as-sumption at the output of the checknodes , and the use of themutual information asameasure of approximation. By doing so, we compute the split-LDPC codes thresh-oldswithin few thousandths of a decibel, at the cost of a lower complexity than den-sity evolution approaches. Through the formulation of the two-dimensional EXITchart analysis of split-LDPC codes, the source controlled iterative decoder is to beillustrated as a bi-dimensional dynamical system. Hence, the graphical representa-tion of charts will bring more insight to the process of convergence to fixed points,as well as to the stability issues of the associated iterative decoding system. Finally,within the framework of our proposal, we formulate the problem of designing ir-regular split-LDPC codes as a linear program. We propose practical algorithms tosolve this problem and design capacity achieving split-LDPC codes. Hence, weobtain irregular split-LDPC constructions, with a significantly reduced gap to theShannon limit. The material of this chapter is reported in part in [4].

• Chapter 4 is devoted to the practical scenarios, where the knowledge of the sourceand channel parameters is impossible and an estimationmodule is required. There-fore, we investigate jointly the decoding and the estimation of the source and chan-nel parameters, using an iterative estimation technique based on the ExpectationMaximization (EM) algorithm. We describe how the estimation technique can be

3

Page 14: Phd dissertation

INTRODUCTION

integrated into the non systematic decoding process. We propose a scheduling forthe interaction between the sum-product decoder and the EM estimation module.Our approach includes both systematic and non systematic LDPC codes, and can beextended to any other block codes [58] decoded by the sum-product algorithm. Ourstudy is applied to the discrete binary symmetric channel with erasures (BECBSC)and the continuous complex additive white Gaussian noise channel (AWGN). Thesimulation results confirm that using the EM estimation technique no loss in error-rate performance is observed with respect to the perfect knowledge case, at theexpense of a negligible complexity. Hence, we show that the decoder is able in ablind mode to perform as good as a perfect knowledge situation. The material ofthis chapter is reported in part in [19].

• Eventually,conclusions, future work perspectives and open problems are given inChapter 5.

4

Page 15: Phd dissertation

Chapter 1

Non Systematic Constructions ofCodes on Graph for Redundant data

Claude Elwood Shannon in his gospel mandates :"The redundancy must be introduced in the proper way to combat the particular noise struc-

ture involved. However any redundancy in the source will usually help if it is utilized at thereceiving point. In particular if the source already has a certain redundancy and no attempt ismade to eliminate it in matching to the channel, this redundancy will help to combat noise".In a tandem view, when channel and source coding are treated independently , the firstcited redundancy is the one introduced by the forward error correcting code, while thesecond one is related to the source and could be natural (no source coding applied)orresidual (compression is applied).

Two directions have been taken, to demonstrate Shannon intuition. In 1995 Hage-nauer has shown how iterative probabilistic decoding is able to exploit the source statis-tics via the Source Controlled Channel Decoding (SCCD) strategy. At the end of the nineties,Mackay then later Alajaji proposed to use non systematic constructions to encode redun-dant data, because their theoretical limits are better than systematic ones in presence ofredundancy. Both authors focused on capacity achieving codes family, in order to ap-proach as close as possible the challenging theoretical limits shown with non systematicconstructions. Hence, a well designed non systematic construction added to an SCCDdecoding constitute the key of success of a coding system in presence of redundant data.

In our setting, we investigate this idea and demonstrate using information theorytools why non systematic constructions show the best theoretical limits in presence ofredundancy. In order to attain these limits we describe a particular design of non sys-tematic LDPC codes extending Mackay’s construction and well suited to SCCD beliefpropagation decoding. We reveal that one specific realization of this code family outper-forms the prior LDPC constructions as well as the other realizations of the family. Weexplain how the introduced design criterias are involved in such performance.

5

Page 16: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

1.1 Introduction

1.1.1 Motivation and Related Work

In most of tandem communication schemes, the channel coding procedures are designedand analyzed for uniformly distributed sources.To a large extent, this approach was justified by Shannon’s famous separation theo-

rem [83] stating that separate source channel coding incurs no loss of optimality as longas the entropy of the source is less than the capacity of the channel providing that block-length goes to infinity. In practice, delay and complexity restrictions related to extremelylong blocklength, made the Joint Source Channel Coding (JSCC) approaches expected tooffer improvements for the combination of a source with significant redundancy and achannel with significant noise[110]. Also, the separation is no longer valid in multi-userscenarios [72].Enhancing the tandem schemes performance by making the channel codes exploiting

the source redundancy which could be natural or residual, is in essence a joint source-channel coding problem. This problem was first intuited by Shannon [83], then for-malized by Hagenauer proposal via Source Controlled Channel Decoding (SCCD) [39]thanks to iterative probabilistic approaches.The natural redundancy is considered in the situations where it is not worth to com-

press, for instance when the channel conditions are bad or medium, thus it is preferredexploiting this redundancy in the decoding step instead of compressing the source [20].Conversely,when sources are highly redundant, a source encoder would be used. An"ideal" source encoder would produce an independent, identically distributed (i.i.d.)sequence of equiprobable bits at the output and eliminate all the source redundancy.However, lossless Variable length or entropy codes (e.g., Huffman codes), which can beasymptotically optimal,are avoided since they imply error-propagation problems in thepresence of channel noise. Therefore, over noisy channels we commonly use fixed lengthencoders which are suboptimal and leave some residual redundancy at their output[37].In presence of non uniform sources, the study of information theoretical limits has

shown that the non systematic codes exhibits better asymptotical limits than systematicconstructions . Those codes supply the capacity achieving distribution to the consideredchannel as highlighted by Shamai and Verdu in [78]. Consequently, when a redundantsource is coded with a non systematic code, then is transmitted over a noisy channel anddecoded via a SCCD strategy, the Shannon capacity limits are moving to better regions.Best candidates in the race to these challenging information theoretical limits are

capacity achieving codes on graphs, namely Turbo Codes introduced by Berrou andGlavieux in 1993 [17] and Gallager Low Density Parity Check codes (LDPC) codes [33]proposed in the sixties and resurrected after turbo code invention [53], [51] and [70]. Thisclass of codes defined on graph is renowned to be able to approach Shannon capacitybound very closely with a reasonable decoding complexity. Both families are obtainedby connecting simple component codes through an interleaver then decoded via itera-tive algorithms consisting of the application of soft, decentralized decoding algorithmsof these simple codes, (eg., BCJR and message passing) [10],[33]. Those algorithms arerealizations of the "Belief Propagation" [63], a more general algorithm that is well suitedto integrate the SCCD strategy.Until the end of the twentieth century, most developments in coding area have con-

sidered the design and optimization of codes defined on graphs for uniformly distributed

6

Page 17: Phd dissertation

1.1. INTRODUCTION

sources, until David Mackay with Oliver Neal[53] made the exception in 1995 when theyproposed Mackay-Neal (MN) codes which are a class of non systematic codes obtainedby the scrambling of low-density generator-matrix [51]. The decoder of an MN code wasspecifically designed for binary symmetric channel. Hence, when it is applied to additivewhite Gaussian noise (AWGN) channel, this is done by hard decision quantization of thea priori values,which is involving a degradation in decoding performance.Other work for SCCD with LDPC codes using systematic LDPC codes was proposed

by Shamir in [81]. The author has shown a gain compared to standard decoding owingto the utilization of source statistics, however this performance is still less than the oneexpected with non systematic constructions.The main following proposals were made by Alajaji et al. and were mainly related

to non systematic Turbo codes for AWGN channels [3],[114],[116], [115], [113],and morerecently for wireless fading channels [112]. In [1], Adrat et. al proposed an improvediterative source-channel decoding for systematic Turbo codes using EXIT charts.Another straightforward solution to obtain non systematic code, is to generate a lower

rate systematic LDPC code, puncture the systematic bits and transmit the parity bits.However puncturing has been proved to be unsuccessful and the gain attained not suffi-cient to offset the loss of performance due to puncturing [79].In the IEEE 2005 International Symposium on Information Theory G.Shamir and

J.J.Boutros have introduced a novel general approach to design a special class of nonsystematic low density parity check codes suited for non uniform memoryless sources.First, the authors proposed several design configurations based on the concatenation

of a pre-coding or a post-coding with an LDPC code. Subsequently we have carried on,with further investigations to reveal the most performant scheme namely the split-LDPC[5],[80].The purpose of the present chapter is to introduce this universal class of non sys-

tematic low density parity check codes through the underlying concepts and techniquesinvolved in the design of this family code as well as in the algorithmic strategies un-dertaken to decode it. Moreover, we will prove using information theoretical tools thesupremacy of the split-LDPC construction.

1.1.2 Contributions

The main contributions of the author for this chapter are based on the results reportedin the two papers presented at the Allerton Conference on Communication, Control, andComputing [5], and the inaugural of Information Theory and Applications Workshop[80].The innovative contribution in this chapter is threefold.First, we demonstrate in term of Information theoretical limits the advantage of non

systematic code constructions over systematic ones, in presence of non-equiprobablememoryless sources. We focus on binary memoryless channels namely BEC, BSC andAWGN channel, and evaluate analytically the losses involved in systematic coding interms of mutual information and energy.Then, we introduce and study the generalmethod proposed by Shamir and Boutros to

construct a universal family of non systematic LDPC encoders and decoders comprisingtwo kinds of constructions called scramble and split LDPC. We describe how to performsource controlled decoding (SCCD) for exploiting the redundancy of the source duringthe decoding step.

7

Page 18: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

Finally, we place the split and scramble LDPC codes in the more general frameworkof non systematic codes, and prove the split-LDPC as the most performant code designover other non systematic constructions namely the scramble-LDPC and the MN codes.We show that MN and our class of non systematic-LDPC codes are both members of amore general family called Multi-Edge LDPC [69].The most important results are the following :

• We demonstrate that in the presence of source redundancy there may be a signifi-cant advantage to the use of a well designed non-systematic channel encoding overa systematic one.

• We describe general methods for designing non-systematic LDPC codes by scram-bling or splitting redundant data bits into coded bits. These methods consist mainlyof cascading a sparse matrix or the inverse of a sparse matrix with an LDPC code.

• Splitting based LDPC codes achieve better gains in the presence of redundancy thanother known codes, including MacKay-Neal (MN) codes, without significant lossin performance even if the data contains no redundancy.

1.2 SystemModel and Notations

Source Sink

01

Channel Channel DecoderChannel Encoder

0.9

0.1

p(s = 1) = µ

µ

Figure 1.1: Block Diagram for a Source Controlled Channel Coding System

Let us describe the considered systemmodel following the block diagram illustrationgiven in the Figure (1.1).Our setting assumes a non-uniform binary independent identically distributed (i.i.d)

source which generates a binary sequence of length K denoted by s , (s1, s2, ..., sK)T

where si ∈ {0, 1}. The source follows a discrete Bernoulli probability distribution (pdf),characterized by the parameter µ = P (si = 1). This parameter is the probability that asource symbol equals 1, i.e. 0 < µ ≤ 1

2 . The source entropy is given byHs = H2(µ),where0 < Hs ≤ 1 and H2(x) = −x log(x) − (1 − x) log(1 − x) is the binary entropy function.The logarithm function is taken, here and elsewhere in the report, to be the logarithmfunction of base of 2.Ourmodel is not restrictive, because it still possible to convert a general finite-memory

source into a piecewise i.i.d. non-uniform source as proposed in [28]. The interestedreader may find the developments related to finite memory sources in [36].

8

Page 19: Phd dissertation

1.3. INFORMATION THEORETICAL LIMITS FOR NON UNIFORM SOURCES

We assume that the source sequence is directly fed to a linear blocklength channelencoder C(N,K) without any data compression. Our study is restricted to channel en-coding via systematic and non-systematic binary linear codes of rate R = K/N . Thecodeword has length N ≥ K and is denoted by c , (c1, ..., cN )T .We assume x , (x1, ..., xN )T the (B.P.S.K) modulated codeword which is transmitted

over a symmetric memoryless noisy channel. Three kinds of binary input symmetric out-put channels are considered in our setting: the binary erasure channel (BEC), the binarysymmetric channel (BSC) and the binary input additive white Gaussian noise channel(BIAWGN). In all the following we denote by AWGN the binary input AWGN channel,continuous input AWGN channel will be indicated if necessary.The BEC channel has a binary input and a ternary output and is characterized by

an erasure probability denoted ε. The BSC channel is characterized by its cross-overprobability denoted λ. The AWGN channel is characterized by one sided power spectraldensityN0.The received noisy vector denoted by y , (y1, ..., yN )T is introduced in the decoder

which is supposed to know the distribution of the source as well as its parameter µ.

1.3 Information Theoretical Limits for Non Uniform Sources

In this section, we illustrate the advantage of the best possible non-systematic codes oversystematic codes, when the source is redundant.We show how the mutual informationbetween channel input and output can be made closer to the maximal achievable oneusing well designed non systematic codes, while systematic codes constrain the mutualinformation to be smaller. We start by introducing some useful information theory facts :Let I(X;Y) , H(Y) − H(Y|X) denotes the mutual information between the channel

input vectorX and the channel output vectorY . Capital letters are used to denote randomvariables and Capital boldface letters are used to denote random vectors. The channelcapacity is given by :

C = maxp(x)

I(X;Y) (1.1)

where the maximum is taken over all possible input distribution p(x) [22]. In practice,we use the following capacity expressions for the continuous channel case , when thechannel is discrete we replace integration operator by the summation one :

C = maxP (x)

x

y

P (x)P (y|x) logP (y|x)∫

x′

P (x′)P (y|x′) dx dy (1.2)

For a given channel and channel input distribution, the theoretically achievable channelcode rate R satisfies :

N × Hs × R = I(X;Y) (1.3)

Let us recall that the discrete uniform input distribution is achieving the capacityfor a binary discrete input memoryless channels, as well as the Gaussian distributiondoes with the continuous input AWGN channel. Besides, the discrete uniform inputdistribution attains the maximal achievable mutual information over the binary inputAWGN (BIAWGN), which is indeed lower than the exact capacity of the channel and isusually limited by th size of the modulation.

9

Page 20: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

The systematic code weakness arises from the fact that they result in channel se-quences that are not uniformly distributed for most redundant sources. Hence, the em-pirical distribution of the transmitted sequences is far from the capacity achieving distri-bution. (see [78] for discussion about the empirical distribution of good codes)In the following, let us evaluate the mutual information I(X;Y ) for both systematic

and non systematic codes design for the BEC(ε), BSC(λ) and BIAWGN (N0), hence theequation (1.3) becomes :

HsR = I(X;Y ) (1.4)

For a systematic code, when the source is non uniform the modulated sequence x in-cludes a non uniformly distributed information sequence xs and a uniformly distributedparity sequence. The mutual information for a systematic code is the average taken overthese two populations :

Isys(X;Y ) = R Iinformation(Xs;Ys) + (1 −R) Iparity(X;Y ) (1.5)

Besides, a well designed theoretically optimal non systematic code can generate anempirical uniform distribution, achieving the maximal achievable mutual information asso-ciated to the channel as well as to the considered modulation i.e. BPSK:

Inonsys(X;Y ) = Iparity(X;Y ) (1.6)

Accordingly, the systematic construction reveals a loss in mutual information as wewill demonstrate in the following.

1.3.1 AWGN Channel

Let us begin with the continuous case and consider an AWGN channel with a real Gaus-sian code book of rate R = K/N for channel encoding.The information rate transmittedby the encoder is the product Hs × R (bits per real dimension) and the Gaussian dis-tribution is the capacity achieving input distribution for the Gaussian channel. For agiven source distribution and a fixed coding rate, in order to fix the minimal achievablesignal-to-noise ratio per bit, Ebr/N0, where Ebr denotes the energy per redundant sourcesymbol, following (1.3)and (1.4) we solve the equation where information rate is equal tothe channel capacity to obtain :

Hs R =1

2log (1 + 2REbr/N0) (1.7)

Then , we find the well known expression of the theoretical minimum achievable SNR[36]

Ebr/N0 =22Hs R − 1

2 R. (1.8)

We obtain the Shannon limit to the uniform source case, by considering Hs = 1, as anupper bound to (1.8). Consequently if one doesn’t consider the statistics of the sourceand assumes it uniform, a suboptimal limits would be achieved and a potential gainwould be lost.For an AWGN channel with BPSK input and a real continuous output, the maximal

achievable mutual information denoted CBPSK is written as:

CBPSK = 1 − E [log2 (1 + exp(−2X/N0))] , X is N (1, N0) (1.9)

10

Page 21: Phd dissertation

1.3. INFORMATION THEORETICAL LIMITS FOR NON UNIFORM SOURCES

where the mathematical expectation is denoted by E[·], andN (1, N0) denotes a Gaussianrandom variable with mean 1 and variance N0. The BPSK amplitude A =

√2RcEbr is

normalized to 1.As argued in equation (1.5) we obtain the best achievable average mutual information

for a systematic code with BPSK modulation by averaging the systematic bits mutualinformation denoted I(Xs;Ys) and the parity bits best mutual information CBPSK aswritten in the following:

Isys(X,Y)/N = R I(Xs;Ys) + (1 −R) CBPSK ≤ CBPSK . (1.10)

Where :

I(Xs;Ys) = (1 − µ) E [log2 (1 − µ (1 − exp(2Y/N0)))] (1.11)

+ µ E [log2 (1 − (1 − µ) (1 − exp(−2X/N0)))] ,

whereX is N (1, N0) and Y is N (−1, N0).A theoretically optimal non-systematic code, can generate uniform distributions for allcomponents of X and achieve CBPSK . Accordingly, we can deduce that :

Isys = Inonsys − R × E

[

log2

(f(X)µf(−X)1−µ

f12 (X)

)]

(1.12)

We define f(X) = µeX/N0 + (1 − µ)e−X/N0 where X is N (1, N0) , and keep the samenotations and assumptions as in (1.9). The equations (1.10) and (1.12) demonstrate theloss in mutual information induced when systematic codes are encoding non uniformdata.The minimum achievable Ebr/N0 for AWGN channel corresponding to the threshold

is found by solving numerically the equality between the information rate with (1.9) forthe non systematic case on the one hand, then with (1.12) for the systematic case on theother hand. The threshold variation versus the source entropy is illustrated in Figure(1.2) where we can observe that the gain of non systematic codes is more significant withhighly biased sources.Furthermore, the Figure (1.3) shows that the loss of systematic codes is increasing

significantly with the channel code rate, pointing out that for high rate codes there is asignificant benefit in using non-systematic codes. This is expected, since high rate sys-tematic codes contain more non-uniformly distributed bits, supplying to the channel adistribution far from the capacity achieving one.

1.3.2 Binary Erasure Channel

The maximal achievable mutual information attained with a non systematic code in abinary erasure channel with ε as erasure probability is :

Inonsys(X;Y ) = 1 − ε (1.13)

With a systematic construction we find using (1.5):

Isys(X;Y ) = Inonsys(X;Y ) − R (1 − ε) (1 −Hs) (1.14)

11

Page 22: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

-12

-10

-8

-6

-4

-2

0

2

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Min

imum

Ach

ieva

ble

Eb/

N0

(dB

)

Source Entropy (bits)

Systematic code, BPSK inputScrambled ds=3Scrambled ds=5

Non-Systematic code, BPSK inputGaussian input

Figure 1.2: Minimum achievable Ebr/N0 vs. source entropyHs Coding rateR = 0.5.

The upper limit on ε noted εth characterizing the threshold of the code should satisfy(1.4); thus we obtain :

εthsys = 1 −R Hs (1.15)

εthnonsys =1 −R

1 −R(1 −Hs)(1.16)

The loss of mutual information is equivalent to an increase of the threshold as we canobserve in the Figure (1.4).

1.3.3 Binary Symmetric Channel

The maximal achievable mutual information attained with a non systematic code in abinary symmetric channel with λ as channel transition probability is :

Inonsys(X;Y ) = 1 −H2(λ) (1.17)

With a systematic construction let us define γ = µ(1 − λ) + (1 − µ)λ, then using (1.5)we find:

Isys(X;Y ) = Inonsys(X;Y ) − R [1 −H2(γ)] (1.18)

In order to evaluate the threshold in the BSC case, we need to solve (1.4) numerically.In a similar way to last mentioned BEC case, the loss of mutual information is equivalentto an in crease of the threshold as we can observe in Figure (1.4).In presence of redundant sources non systematic codes are more advantageous, be-

cause when some constraints are satisfied, they generate asymptotically uniform output.Whereas, systematic constructions involve a mismatch between the biased distribution

12

Page 23: Phd dissertation

1.4. DESIGN PRINCIPLES FOR NON SYSTEMATIC CODES ON GRAPH

-5

-4

-3

-2

-1

0

1

2

3

4

5

6

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Min

imum

Ach

ieva

ble

Eb/

N0

(dB

)

Coding Rate

Systematic codes, BPSK inputScrambled ds=3Scrambled ds=5

Non-Systematic code, BPSK inputGaussian input

Figure 1.3: Minimum Achievable SNR versus Coding Rate in AWGN, Hs = 0.5.

of the systematic symbols and the uniform input distribution needed to achieve channelcapacity. This interpretation comes in light of Shamai and Verdu work in [78] provingthat the empirical distribution of any good code should approach the capacity achievinginput distribution.To attain the challenging theoretical limits computed in the present section, well de-

signed non systematic constructions are required. As a matter of fact, capacity achievingcodes are the best candidates to attain these limits. Accordingly, we propose to set inthe following section, the main issues related to the design principles of non systematiccodes. Then, we will describe the prior and novel non systematic capacity achievingcodes constructions suited to non uniform sources.

1.4 Design Principles for Non Systematic Codes on Graph

Non systematic constructions are made attractive because of their better use of codingspace, and their convenience for redundant data. Puncturing the systematic bits of alower rate systematic code, could be a straightforward method to build a non systematiccode , then passing the a-priori probabilities to the punctured systematic bits during thedecoding process would help improving performance of the punctured code, neverthe-less the gain attainedwith SCCD is not sufficient to offset the loss of puncturing. Buildinggood non systematic codes for redundant source requires setting-up some design crite-rias following two main issues :

• Encoding should ensure the transformation of a non uniform distributed sourceinto a uniformly distributed one.

• Decoding should follow an SCCD strategy exploiting the statistics of the source.

13

Page 24: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Cha

nnel

Tra

nsiti

on P

roba

bilit

y

Source Entropy (bits)

BEC

BSC

BEC + Non Systematic

BEC + Systematic

BSC + Non Systematic

BSC + Systematic

Figure 1.4: Capacity limit versus source entropy for BEC and BSC.

First proposals for non systematic codes have been made for turbo code first byMassey et al. in [55], then [11], where the proposed asymmetric nonsystematic turbocodes (NSTC) outperform Berrou’s (37, 21)code [16] by about 0.2 dB at the 10−5 BERlevel. The motivation for using these NSTC is due to their larger code space, while inpresence of highly biased sources these codes don’t approach Shannon capacity as closeas in the uniform case. In order to fill this gap Alajaji in [116], then Shamir in [82] camewith non systematic turbo codes constructions well suited for non uniform sources.In most of those proposals, constituent codes with the Quick-Look-in (QLI) property

are used. The QLI property is defined such that the two parity sequences added together(modulo 2) are equal the information sequence (or a delayed version of it). Actually, theQLI property makes the nonsystematic constituent code close to a systematic one, thenthe initial extrinsic estimates for the information bits are enhanced and good enough tostart-up the iterative convergence process for the second constituent. Consequently, theperformance in thewaterfall region is made better for uniform distributions of the source.Similarly, in the case of more redundant data, Shamir et al. have shown in [82] that QLIcodes exhibits a good adaptation.Recently, Zhu et al. in [116], have found out necessary and sufficient conditions, for

recursive convolutional encoders, to supply an asymptotically uniform marginal outputdistributions,regardless of the degree of source non uniformity. These properties offerpertinent design criterias for constructing good turbo codes dedicated to heavily biasednon uniform i.i.d sources.Themost significant proposal for non systematic LDPC-like codes, wasMackay’s con-

struction in 1999 [51]. TheMackay-Neal (MN) codes are based on a low density generatormatrix (LDGM) code. this construction was followed by Shamir and Boutros in [79] witha novel general approach called "Non Systematic LDPC" and including MN encoder con-

14

Page 25: Phd dissertation

1.4. DESIGN PRINCIPLES FOR NON SYSTEMATIC CODES ON GRAPH

struction as particular case, while the general decoder procedure enhances theMN’s one.The two approaches dedicated to redundant data follow the same design principle, i.e.the use of a pre-coder, or post coder emulating the effect obtained by the quick look inproperty in the non systematic turbo code proposal in [82].Besides, we should also cite, another class of non systematic LDGM-like codes called

"Rateless codes" or "Fountain codes" dedicated to network communication. This codesfamily includes LT codes [49] and Raptor codes [87]. Some common design guidelinesmay be found between Raptor and scramble-LDPC codes, however to the best of ourknowledge, so far there is no study applying rateless channel encoding to non uniformdata.In the following, after some preliminaries on LDPC codes, let us give a detailed de-

scription of the design and decoding of the two codes family MN, then the universal classof non systematic LDPC codes.

1.4.1 Preliminaries on LDPC codes

RA

DN

OM

G

AP

R

H

db

c2

dc

cN

ci

PCE1

PCEj

PCEℓ

ℓ subcode nodesN bitnodes

c1

Figure 1.5: Factor Graph of an LDPC Code

LowDensity Parity Check codes (LDPC) invented by Robert Gallager in 1963 [34], arelinear block codes, which are described by a low density parity check matrix and repre-sented through a sparse bi-partite factor graph . The graphical and matricial descriptionsare related by the fact that the parity check matrix of the code is the adjacency matrix ofthe bi-partite graph. Similar descriptions are used with Low Density Generator Matrix(LDGM) codes, by considering the generator matrix instead of the parity check one in alldescriptions.The sparse nature of both parity check matrix and graph structure is the key property

involving the algorithmic efficiency of LDPC codes. Hence,in the matricial description

15

Page 26: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

the code is defined through the evaluation of the nonzero entries in the matrixH per lineor column. The code is regular if the number of these nonzero entries doesn’t changefrom a column to another as well as from a line to another. Otherwise, we say that thecode is irregular. The irregular structure being more general, will be the one described inthe following.The LDPC codes are usually , described and studied in term of their graphical rep-

resentation. The graphical descriptions for codes started with Tanner graphs for linearcodes [89], then the graphical understanding of the "codes on graphs" has been shaped,when the more general concept of "factor graph" was introduced [46]. Genealogically,factor graphs are a straightforward generalization of the "Tanner graphs" of Wiberg etal. [102], [31]. In Tanner’s original formulation, all variables are codeword symbols andhence are "visible"; Wiberg et al., introduced "hidden" state variables and also suggestedapplications beyond coding. Factor graphs take these graph-theoretic models one stepfurther, by applying them to functions, in order to represent the factorization of a mul-tivariate function into simpler functions. Therefore, a factor graph is a graphical modelwhich is naturally more convenient for problems that have a probabilistic side.Following the factor graph trend, Turbo codes and LDPC have been unified as "codes

on graphs", and their decoding algorithms have been revealed in ([45],[56]) as specialinstances of the belief propagation algorithm on general Bayesian networks [63]. Notonly has this understanding helped coding theorists in analysis of these codes and designof decoding algorithms for them, they also learned how to design their codes to get thebest out of a given decoding algorithm.A factor graph for an LDPC code is always a bipartite graph related to a parity check

matrix H of size ℓ×N , and partitioned to N left nodes called variable nodes and ℓ rightnodes as function nodes usually called checknodes, and E edge linking the two parts.The Figure (1.5) shows an example of such a bipartite graph. Notice that in this Figure,the variable nodes are shown by circles and the checknodes by squares, as is the case formost factor graphs.A variable node is a binary variable from the alphabet {0, 1} representing theN sym-

bols of the codeword c. A checknode PCEj is an even parity constraint on its neigh-boring variable nodes. Each checknode represents a row of the parity check matrix H aseach variable node corresponds to a column . Each non zero entry at the position (i,j) inthe matrix coincides to an edge from the variable node cj to the checknode PCEi .Therepresented linear code is of dimension k ≥ (N − ℓ) with equality if and only if all theparity constraints are linearly independent.A graph ensemble is specified through two polynomials :

• the polynomial λ(x) associated to variable nodes denoted as :

λ(x) =dbmax∑

i

λi xi−1 (1.19)

Where λ = {λ2, λ3, ..., λdbmax} denotes the variable edge degree distribution; where

λi denotes the fraction of edges incident on variable nodes of degree i and λi ∈ [0, 1].

• the polynomial ρ(x) associated to checknodes denoted as :

ρ(x) =

dcmax∑

i

ρi xi−1 (1.20)

16

Page 27: Phd dissertation

1.4. DESIGN PRINCIPLES FOR NON SYSTEMATIC CODES ON GRAPH

Where ρ = {ρ2, ρ3, ..., ρdcmax} denotes the check edge degree distributions; where

ρj denotes the fraction of edges incident on checknodes of degree j and ρi ∈ [0, 1].

Notice that the graph is characterized in terms of the fraction of edges of each degreeand not the nodes of each degree. For a given length N and a given degree distribution(λ, ρ), we define an ensemble of codes by choosing edges randomly. It has been shown in[73] that the average behavior of almost all instances of an ensemble of irregular codes isconcentrated around its expected behavior, when the code is large enough. Additionally,the expected behavior converges to the cycle- free case.Given the degree distribution of an LDPC code (λ, ρ)and its number of edges E, it is

easy to see that the number of variable nodes n is

N = E ×∑

i

λi

i= E

∫ 1

0λ(x) dx (1.21)

and the number of checknodes ℓ is

ℓ = E ×∑

i

ρi

i= E

∫ 1

0ρ(x) dx (1.22)

Therefore the design rate of the code will be

R = 1 −∫ 10 ρ(x) dx∫ 10 λ(x) dx

(1.23)

Finding a good asymptotically family of irregular codes is equivalent to finding agood degree distribution. The task of finding a degree distribution that results in a codefamily with some required properties is not a trivial task and will be one of the focusesof this thesis.

1.4.2 Mackay-Neal Codes

Mackay-Neal codes [51], also called ’MN’ codes, are non systematic LDGM codes.Thekey idea behind MN codes is that the generator matrix is constructed in terms of aninvertible matrix, in such a way that the sparse source and the sparse noise can be treatedsymmetrically during the decoding process.The coding principle consists in encoding a source vector s by a Low Density Gener-

ator Matrix (LDGM) code defined by the matrix C1, followed by the scrambling of theLDGM codewords by the inverse of a sparse matrix denoted C2.The block diagram description of theMN encoding process is illustrated in Figure (1.6)

and is written as following :c = C−1

2 C1 s (1.24)

The dimensions of C1 and C2 are respectively N × K , and N × N . Both matricesare sparse and can be found by applying a Gaussian elimination to an N × (K + N)LDPC matrix H of column weight db and row weight dc (see the construction proposedin [51]). After applying column permutations to guarantee the full rank, H is written asH = [C1|C2].The decoding problem is considered for a BSC, where the received vector is

y = c + n (1.25)

17

Page 28: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

Splitter

s c

LDGM

C1

C2

C2

PCE

PCE

PCE

n

s

y

n

s

y

C−12

[N × N ][N × K]

C1

Figure 1.6: Mackay-Neal Codes: Block and Tanner Graph descriptions

n is the binary noise vector of length N , assumed to be sparse with independent andidentically distributed bits.The decoding procedure should solve :

C2 y = C1 s + C2 n (1.26)

In this purpose, message passing decoding is performed on the Tanner Graph corre-sponding to the equation (1.26) as it is illustrated in the Figure (1.6).In the above description, MN codes are regular since the column weight of C1 and C2 isequal to db. Improved irregular MN codes have been proposed by Kanter and Saad in[43]. Stability of irregular MN codes has been improved in [69].One of the main drawbacks related to MN codes , is that their decoder is specificallydesigned for the binary symmetric channel . The decoding principle can be extended toreal-output channels by hard decision quantization of the a-priori values passed to thenoise bitnodes [51], however the quantization imply a degradation of the decoding per-formance.

1.4.3 Non Systematic LDPC Framework

In this section, we propose a novel general approach to build an LDPC based non sys-tematic code. We describe several different ways for building the encoder. All the config-urations can successfully utilize redundancy in the coded sequence during the decodingprocess.The general idea is to concatenate a pre-coding (or post-coding) block that uses an

invertible square matrix with an LDPC or an LDGM encoder. Then the decoder performsover one single irregular bipartite factor graph combining the code and the precoder orthe post coder. The systematic bits are not sent over channel, but included in the decodinggraph as a subset of the set of bitnodes, to which a-priori information can be provided.

18

Page 29: Phd dissertation

1.4. DESIGN PRINCIPLES FOR NON SYSTEMATIC CODES ON GRAPH

Pre−Coding

Post−Coding

C−1s or Cs

[K × K]s c

C−1s or CsLDPC or LDGMs c

LDPC or LDGM

[N × N ]

Figure 1.7: General Non-Systematic LDPC Encoding Framework

The set of bitnodes is completed with the set of transmitted codeword bits, and in someof the configurations, but not all, another subset of un-transmitted bits can be added. Theparity checknodes in the decoder graph are those,of both the pre-coder or post-coder andof the LDPC or LDGM code.The pre-coder (or post-coder) is a square matrix which is either of low density or has

an inverse that is sparse. The main idea is that the pre-coder (or post-coder) emulates theeffect obtained by the Quick-Look-In property in turbo codes, by converting the system-atic non uniform message to an almost uniformly distributed one. Hence, there are eightdifferent possible configurations as illustrated in Figure (1.7). Each one depends on thecombination choices among:

1. LDPC or LDGM as a core code.

2. Pre-coder or Post-coder.

3. Low density square matrix denoted as scrambler or a matrix whose inverse is lowdensity denoted as splitter.

One specific configuration of our codes is the encoder of an MN code which could beviewed as a concatenation of a non-systematic LDGM code with a post coding splitter.However our proposed general decoder procedure is channel independent and is differ-ent from the one proposed in the original MN proposal [51]. Thus, the proposed generaldecoder procedure gives an enhanced decoding alternative for the MN.In the remainder of this section, we focus on pre-coding with either a scrambler or

a splitter combined with an LDPC code. We refer to a pre-coding scrambler system asa scramble-LDPC code, and to the pre-coding splitter as a split-LDPC code. Post-codingscrambler and splitter LDPC codes will be referred to as LDPC-scramble and LDPC-splitcodes, respectively. The methods described herein may be easily adapted to implementall the other configurations.

1.4.3.1 Scramble-LDPC Construction

Definition 1.1. A scramble-LDPC code is built by the concatenation of a pre-coding moduledenoted "Scrambler" with an LDPC code.The scrambler is described by a sparse matrix denotedCs.

19

Page 30: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

R.N

R.N

(1−R).N

R.N

Scrambler

LDPC

(1−R).N

LDPC

Scrambler

s

dc

v

u

s

s

v

s

α

β

β

db

db

α

u

α

ds

ds

Cs

Csc

Figure 1.8: Scramble LDPC Tanner Graph and block Diagram Description

The block diagram as the factor graph of the scramble-LDPC are illustrated in theFigure (1.8).A scramble-LDPC encoder first encodes (scrambles) the source vector s intou by :

u = Cs s (1.27)

Let Cs be a sparse matrix of dimensions K ×K .For a regular scrambler, Cs has row andcolumn weight ds . Similarly to the LDPC case, we can consider building scramblers withan irregular structure. Afterwards, standard LDPC systematic encoding is performed onthe scrambled vector u,to generate the codeword :

c = [uT |ϑT ]T = G u (1.28)

where G is a systematic generator matrix for the low-density parity check matrix H ,and the superscript T denotes the transpose operator. Hence, the codeword c consists ofthe K scrambled bits of u and the N −K parities over the scrambled bits denoted ϑ.Fora regular LDPC code, the parity-check matrix H has column weight db and row weightdc. The decoding graph for the scramble-LDPC combines parity checks of the LDPCcodes, denoted by β, with those obtained from the scrambler, denoted by α as shown inFigure (1.8). The decoding process is realized , by performing over this whole graph, asource controlled belief propagation as described further in the next section.

1.4.3.2 Split-LDPC Construction

Definition 1.2. A split-LDPC code is built by the concatenation of a pre-coding module denoted"Splitter" with an LDPC code.The splitter is described by the inverse of a sparse matrix denotedC−1

s .

20

Page 31: Phd dissertation

1.4. DESIGN PRINCIPLES FOR NON SYSTEMATIC CODES ON GRAPH

R.N

(1−R).N

R.N

(1−R).N

R.N

Splitter

LDPC

LDPC

Splitter

v

u

s

db

s

u

v

s α

α

α

β

β

ds

ds

dc

Cs cC−1

ss

Figure 1.9: Split-LDPC Tanner Graph

The block diagram as the factor graph of the split-LDPC are illustrated in the Fig-ure (1.9).The split-LDPC encoder is very similar to the scramble-LDPC one’s describedupwards, except that the scrambling operation is replaced by splitting performed by

u = C−1s s (1.29)

Where Cs is a sparse matrix of dimensions K × K , that has in the regular case rowand column weight ds.Similarly to the scrambler case, we can consider building splitterswith an irregular structure.Afterwards, standard LDPC systematic encoding is performed on the scrambled vec-

tor u,to generate the codeword :

[uT |ϑT ]T = G u (1.30)

where G is a systematic generator matrix for the low-density parity check matrix H ,and the superscript T denotes the transpose operator. Hence, the codeword c consists ofthe K splitted bits of u and the N − K parities over the scrambled bits denoted ϑ.For aregular LDPC code, the parity-check matrix H has column weight db and row weight dc.The matrix C−1

s describing the splitter is a dense matrix, given that it is the inverseof a sparse one, according to [12]. The latter fact gives a reason to believe that, withredundant sequences, a split-LDPC code has an advantage over a scramble-LDPC codein generating channel distribution closer to the uniform capacity achieving one. This isalso because splitting results in an even split to 1 and 0 bits; while scrambling leads tooutput distribution closer to uniform from the original nonuniform one, this distributioncan still be shown to be nonuniform.

21

Page 32: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 00 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 00 0 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 00 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Permutation

0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0

SystematicLDPC

Square Low−Density Scrambler

ϑ bits u bits s bits

Figure 1.10: General Structure of a Split-LDPC Parity Check Matrix

Besides, the splitter can be viewed as if an incoming source bit is splitted into severalcoded bits, that is why splitting resembles theQuick-Look-In (QLI) property in turbo codes[11],in which two (or more) parity bits sum up to the original source bit. Let us remindthat, MN codes are also obtained by LDGM followed by a splitter.The decoding graph for the split-LDPC combines parity checks of the LDPC codes,

denoted by β, with those obtained from the splitter , denoted by α as shown in Fig-ure (1.9). By the same token, we illustrate in Figure (1.10) the parity check matrix relatedto this graph. Encoding, is realized by performing the Gaussian elimination over this par-ity check matrix. The systematic form of this matrix reveals a highly dense scramblingapplied to the source bits during the encoding.The decoding process is realized , by performing over this whole graph, a source

controlled belief propagation as described further in the next section.

1.4.4 Information Theoretical Comparison of Splitting and Scrambling

In the present section, we analyze the mutual information of the best regular scramblingbased code and show that it is smaller than that of the best splitting based code. A split-LDPC code multiplies the nonuniform sequence s by a dense matrix, generating a splitvector that has distribution very close to uniform [12]. Hence, the best possible splittingbased code may be close to achieving the BPSK capacity.For a regular scrambling-based code as described in section (1.4.3.1), ds systematic

nonuniform bits are scrambled into a code bit. Assuming that the parity bits that aregenerated by the LDPC code part are uniformly distributed, the best achievable mutualinformation can be computed using the equations (1.10) and (1.11) where µ in (1.11) isreplaced by γ . The probability γ denotes the probability of 1 in the scrambled sequence

22

Page 33: Phd dissertation

1.4. DESIGN PRINCIPLES FOR NON SYSTEMATIC CODES ON GRAPH

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

-10 -5 0 5 10

Mu

tua

l in

form

atio

n

Eb/N0(dB)

Gaussian inputNon-Systematic code, BPSK input

Scrambled ds=5Scrambled ds=3

Systematic codes, BPSK input

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

2.2

-10 -5 0 5 10

Mu

tua

l in

form

atio

n

Eb/N0(dB)

Gaussian inputNon-Systematic code, BPSK input

Scrambled ds=5Scrambled ds=3

Systematic codes, BPSK input

Figure 1.11: Mutual information vs. Ebr/N0 for Hs = 0.5 and coding rates R = 0.5 (left)and R = 0.8 (right).

u. For a regular scrambler of degree ds, it can be obtained, using Gallager’s lemma [34] :

γ = 0.5[1 − (1 − 2 µ)ds

](1.31)

For an irregular scrambler, similar computation can be done, considering all the differentscrambling degrees.The Figure (1.11) shows curves of the best possible mutual information versusEbr/N0

for the different methods discussed above for a nonuniform source with µ = 0.1 withcoding rates R = 0.5 and R = 0.8. The BPSK input curve bounds the mutual informa-tion of the splitting based code. As both graphs show, a splitter based code is better thanthe scrambler based codes, and both classes have gains over systematic codes. We ob-serve that as the scrambler degree increases, the scrambler approaches the behavior ofthe splitter. This is expected, since the scrambler is converging to the splitter behavior inthe equation (1.31) where γ → 1/2 when ds is increasing.The Figures (1.2) and (1.12) show the theoretical minimum Ebr/N0 as a function of

the source entropy for channel code rates R = 0.5 and R=0.8 respectively. The curves inboth cases support the advantage of non-systematic codes, and in more particular waythe supremacy of splitting based codes. Moreover, the loss in using systematic codes isshown to increase significantly as the non-uniformity of the source increases.Additionally to point out that for high rate codes there is a significant benefit in using

non-systematic codes, the Figure (1.3) reveals also the improvement of scramblers withthe increase of ds.Conversely, in most of finite length cases, we find out that a scrambler/splitter with

an improper degree for a distribution can degrade the performance from that of system-atic codes, even if the considered degree value is high enough . This fact indicates thatthe degree of the scrambler/splitter should be optimized for each value of µ.These results, despite being incoherent with the theoretical limits described above,

might be interpreted with the increasing of cycles’density in the lower subgraph re-lated to the scrambler/splitter. Actually, the increase of ds for a constant code length,

23

Page 34: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

-12

-10

-8

-6

-4

-2

0

2

4

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Min

imum

Ach

ieva

ble

Eb/

N0

(dB

)

Source Entropy (bits)

Systematic code, BPSK inputScrambled ds=3Scrambled ds=5

Non-Systematic code, BPSK inputGaussian input

Figure 1.12: Minimum achievable Ebr/N0 vs. source entropyHs Coding rate R = 0.8.

induces an increase of edges locally in this lower subgraph for a constant number ofnodes (R × N), involving doubtlessly more cycles.In this section, split-LDPC have been revealed as being theoretically the best non

systematic LDPC structure. Moreover, The simulations results, presented in section (1.6),show that gains of about 1dB are achieved when the scrambler is replaced by a splitter.Accordingly, we expect the MN codes to outperform scramble-LDPC, since MN codesbelong to the split-LDPC general structure.

1.5 Source Controlled Sum-Product Decoding

The sum-product algorithm is a generic message-passing algorithm, that operates overa factor graph in order to compute various marginal functions associated with a globalfunction [46].A wide variety of algorithms developed in the artificial intelligence, signalprocessing, and digital communication communities may be seen as specific instances ofthe sum-product algorithm, operating in an appropriated chosen factor graph.One important subclass of the sum-product algorithm is the Pearl’s powerful belief

propagation algorithm , which operates by message-passing over a Bayesian network, in-cluding as instances the iterative decoding algorithms related to LDPC and turbo codesas it was shown in [56],[86].In his original work; Gallager has already proposed a simplified version of the sum-

product algorithm to decode LDPC codes [33] consisting on the propagation of beliefsor probabilities between variable nodes and checknodes. This messages exchange is thereason why this kind of algorithms are also referred to asMessage Passing algorithms.Without going into much detail,we define the nature of the messages and the sim-

plified update rules on them, for our class of non systematic LDPC in presence of nonuniform sources.

24

Page 35: Phd dissertation

1.5. SOURCE CONTROLLED SUM-PRODUCT DECODING

The most common message type used in the literature is the log-likelihood ratio (LLR)namely log p(x=0|y)

p(x=1|y) , this is because it is more appropriate to computer implementation,since we can represent probability values that are very close to zero or one without caus-ing a precision errors, moreover its update rules are quiet simple.The message passing algorithm is an iterative algorithm, where in each round mes-

sages are sent frommessage nodes to checknodes, then from checknodes back to messagenodes.In order to describe the algorithm let us consider the following notations:

• The bipartite graph describing our non systematic LDPC codes with three type ofmessage nodes ci ∈ {u, ϑ, s}and two types of checknodes PCEi ∈ {α, β} (seeFigure (1.15)).

• Sciis the set of checknodes involving the message node ci .

• SPCEiis the set of bitnodes involving the checknode PCEi .

• LLR0 denotes the channel observation LLR.

• LLRs = log(1 − µ

µ) denotes the LLR related to the source statistics.

• LLRci→PCEidenotes the LLR coming from a message node ci towards a checknode

PCEi, respectively, LLRPCEi→cidenotes the LLR coming from a checknode PCEi

towards a message node ci.

The bitnode to checknode step

Extrinsic Information

PCEj

s

Observation LLR0 A priori LLRs

ϑ

Figure 1.13: The local message node to checknode update rule.

The variable node to checknode update rule is written as :

LLRci→PCEi= LLRtype +

PCEj∈Sci−{PCEi}

LLRPCEj→ci(1.32)

where :

LLRtype =

{LLR0 if the bitnode type ∈ {u, ϑ}LLRs if the bitnode type ∈ {s} (1.33)

25

Page 36: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

Each variable node receives the beliefs that all its neighboring checknodes have aboutit, then after processing these messages via the summation of all received LLRs, the vari-able node sends its updated belief about itself back to these same neighboring checkn-odes.

In the case of our non systematic structure, the message sent from a message nodeci to a checknode PCEi, should be based jointly on an extrinsic information, obtained bycombining the messages received from the other neighboring checknodes in the previ-ous round, then on an a priori additional message LLRtype which depends on the mes-sage node type. At the first iteration the bitnodes send only LLRtype, since they haven’treceived yet any messages from their neighbors.

The value LLRtype represents the channel observation message LLR0 when the con-sidered message node belongs to the parity nodes type {u, ϑ}, whose are assumed uni-formly distributed . Otherwise,LLRtype equalsLLRswhen the consideredmessage nodeis a source symbol that belongs to the message type {s} (see Figure (1.13)). Indeed, thesource symbols are interpreted on the multi-edge graph as punctured, hidden or statemessage nodes, thus they don’t receive any observation from the channel. However thesource statistics are exploited as a priori information to skew the decoding, that is whywe talk about Source Controlled Channel Decoding (SCCD).

If the code is systematic, LLRtype includes both of the observation with the sourcestatistics messages in the update rule related to the systematic variable nodes. Moreover,we can state that the ignorance of the source statistics is equivalent to a uniform sourceassumption where LLRs = 0 inducing a loss in the decoding performance, as we can seefurther in the results section.

The reliability of messages at a variable node increases as the received beliefs aboutitself increases , similarly to a repetition code,which receives multiple beliefs for a singlebit from the channel and hence is able to make a more reliable decision.

The checknode to bitnode step

Extrinsic Information

PCEj

ci

Figure 1.14: The local checknode to bitnode update rule.

26

Page 37: Phd dissertation

1.6. MULTI EDGE CLASSIFICATION TO THE NON SYSTEMATIC LDPC CODES

The checknode to variable node update rule is written as :

LLRPCEi→ci= 2 tanh−1(

cj∈SPCEi−{ci}

tanh(LLRcj→PCEi

2)) (1.34)

A checknode is dedicated to force its neighbors to satisfy an even parity, as does aparity code. Thus, for a neighboring variable node ci, it processes the beliefs of otherneighboring variable nodes about themselves and sends a message to ci , which indicatesthe belief of this checknode about its value.The message sent from a checknode PCEi to a message node ci, is computed based

on all the incoming messages from the other neighboring message nodes in the previousround as an extrinsic information except ci the one which receives the outgoing message[40].The checknode to bitnode update rule is still unchanged, independently of the chec-

knode type. The sign of this message is chosen to force an even parity check and itsmagnitude depends on the reliability of the other incoming messages. It is known thatthe reliability of the outgoing message is even less than that of the least reliable incomingmessage. Hence, the reliability of messages decreases at the checknodes.The checknodes force the neighboring variable nodes to satisfy an even parity check at

the expense of losing reliability in the messages, while variable node strengthen the relia-bilities. This process is repeated iteratively to clear the errors introduced by the channel.The sumproduct algorithm shows a complexity growing linearly with the code length

and allows a parallelizable implementation. These implementation advantages are com-promised by the fact that this decoding algorithm requires more iterations than turbodecoding to attain the convergence and induces an important encoding complexity .Similarly to turbo decoding, the sum-product shows a sub-optimal decoding on a

factor graphs with cycles, because these latters make the algorithm loosing the inde-pendence assumptions accomplished over a cycle free graph[96]. However, the perfor-mances of Belief Propagation over loopy graphs are still surprisingly good dependingmostly on the cycles’ size[32]. Conversely, it has been shown in [30] that asymptoticallygood codes which have cycle free tanner graph don’t exist.In order to mitigate the effect of cycles, several update schedules have been proposed

and optimized following the considered loopy graphs and the associated code length[54].

1.6 Multi Edge classification to the Non Systematic LDPC Codes

The Multi-Edge type LDPC codes introduced in [69], are a generalization of irregularLDPC codes. This framework is described in a universal formalism including variousexisting structures as irregular LDPC [73], [50], then more other constructions fallingoutside the scope of this latter class, as Kanter and Saad codes [43], Repeat Accumulatecodes [42] , concatenated codes [65] and other particular graphs admitted as special cases.The purpose of this generalization is to specify ensembles, in order to designmacroscopicinterconnection structure.The principle of the multi-edge type is the consideration of ensembles with multiple

equivalence class of edge, by contrast to standard irregular LDPC ensembles definition,where all edges in the Tanner Graph are statistically interchangeable since they belong tothe same statistical equivalence class.

27

Page 38: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

db dc db dc

Rc.N

Rc.N

(1 − Rc).N ϑ

dc

db

(1 − Rc).N

Rc.N

ds ds

1

1

β

α

u

s

(1 − Rc).N

Rc.N

Rc.N

(1 − Rc).N ϑ

dc

db

ds

ds

1 1

Rc.N

β

αs

u

Figure 1.15: Multi-Edge graphical interpretation of Split and Scramble-LDPC.

A multi-edge ensemble is comprised of a finite number ηe of edge types. Edges aretyped as they pair sockets of the same type. The structure of the graph is describedthrough a node perspective multinomial representation. In a multi-edge description, dif-ferent variable-node types may have different received distributions,i.e, the associatedbits may go through ηr different channels.Hence the "degree type" of a variable node is described by a vector which is two parts.

The first one and denoted by b := (b1, ..., bηr ) ∈ GF (2)ηr , of length ηr, and termed the"received degree", is indicating the different channels involved in the considered bitnodetransmission. The second part denoted by d := (d1, ..., dηe ) ,of length ηe, and referredto as the "edge degree" ,is recording the number of sockets of each type connected to theconsidered variable node.By the same way, the "degree type" of a constraint node is a vector of integers of length

ηe playing the same role as the " edge degree" for the variable nodes and denoted also byd := (d1, ..., dηe ) .A graph ensemble is specified through two multinomials, ν(r,x) associated to vari-

able nodes and µ(x) associated to constraint node, where the degree types are interpretedas exponents,similarly to irregular LDPC. These polynomials are denoted as following :

ν(r,x) =∑

νb,d rb xd and µ(x) =∑

µd xd (1.35)

where we introduce:

• x = (x1, ..., xηe ) to denote the vector variables. We use xd to denote

∏ηe

i=1 xdi

i .

• r = (r1, ..., rηr ) to denote the variables corresponding to received distributions. Weuse rb to denote

∏ηr

i=1 rbi

i .

• νb,d and µd are non negatives reals coefficients where for each variable node degreetype (b,d) the quantity (νb,d × N) is the number of variable nodes of type (b,d) .Respectively, for each constraint node degree type d the quantity (µd × N) is thenumber of constraint nodes of type d in the graph.

Among the main significant advantages of the multi edge extension of LDPC ensem-bles:

28

Page 39: Phd dissertation

1.7. SIMULATION AND RESULTS

νb,d b d µd dR N 0 1 0 0 db (1 −R) N 0 0 dc

R N 0 1 0 ds db R N 1 ds 0R N 1 0 1 0 0

νb,d b d µd dR N 0 1 0 0 db (1 −R) N 0 0 dc

R N 0 1 0 1 db R N ds 1 0R N 1 0 ds 0 0

Table 1.1: Multinomial description of Split (top) and Scramble (bottom) LDPC

• Admitting degree one variable nodes without sacrificing the threshold,

• Controlling degree two variable nodes, while allowing a relatively large number ofthem making the encoding simpler without loosing stability.

• Addition of state or punctured variables, allowing increasing threshold and lower-ing error floors.

• Allowing different node types to have different received distributions associated tothem , which is useful in combining multi-level modulation with LDPC coding.

All schemes of the non systematic LDPC framework described herein, lay out a cas-caded Tanner Graph structure,this is because they can be decomposed into two disjointsubgraphs connected by a set of edges finding their variable sockets in one graph andtheir constraint sockets in the other. The split-LDPC code belongs to the multi-edge par-ticular case of simple degree one cascade constructions.The multi-edge cascaded constructions are known to be used for introducing degree

one variable nodes, as well as for the design of very low rate LDPC codes, similarly tothe recently introduced Raptor codes [87].Moreover, split-LDPC codes include punctured source bits, which represent the state

variables in the Multi-edge LDPC codes. Besides, the presence of source a priori is equiv-alent to transmitting source bits on an asymmetric channel.Accordingly, the general class of non systematic LDPC is revealed as another special

case of multi-edge cascaded construction, dedicated to encoding redundant data.Let us give amulti-edge description to our non systematic LDPC class of code through

a Tanner-like graphical illustration in the Figure (1.15) as first introduced in [5]. In theFigure (1.15) we consider the case of a simple cascade of a regular ds-degree scrambler(left) and ds-degree splitter (right) with a regular (db, dc) binary LDPC code. One can alsoconsider further variations with a multi-edge structure as a core code instead of a simpleirregular LDPC code. The number of nodes is indicated as a fraction of the code lengthN . The Table (1.1) shows the multinomial description for the codes illustrated in theFigure (1.15), following the notations described upwards and according to the originaldescription in [69].

29

Page 40: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

1E-05

1E-04

1E-03

1E-02

1E-01

-2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5

Bit E

rro

r R

ate

SNR

(3,6) systematic LDPC without SCCD(3,6) systematic LDPC with SCCD

scrambler ds=3MN code db=3

splitter ds=4

1E-04

1E-03

1E-02

1E-01

1E+00

-2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5

Fra

me

Err

or

Ra

teSNR

(3,6) systematic LDPC without SCCD(3,6) systematic LDPC with SCCD

scrambler ds=3 MN code db=3

splitter ds=4

Figure 1.16: Bit (left) and word (right) error probabilities vs. signal to noise ratio forcodes with rate R = 1/2 length N = 2000 and non uniform source distribution µ = 0.1: systematic (3,6) LDPC with and without SCCD, split-LDPC with ds = 4 and scramble-LDPC ds = 3 and MN Codes db = 3.The systematic code is the core code of the nonsystematic ones.

1.7 Simulation and Results

We illustrate our experimental results in Figures (1.16), (1.17), (1.18) and (1.19). In all oursimulations 100 erroneous blocks and 500 erroneous bits have been counted to estimatethe word error probability and the bit error probability respectively. The number of beliefpropagation iterations is 200 iterations.The Figures (1.16), (1.17), (1.18) show simulation results for the different codes includ-

ing systematic codes, MN codes, scramble-LDPC and split-LDPC codes. All simulatedcodes have a regular structure, and for the scramble and split-LDPC codes, regular scram-blers / splitters are considered with degree ds. Only the best ds is shown for a specificcode; those degrees have been found empirically.The Figure (1.16) shows the advantage of the SCCD with systematic codes first, then

with non systematic ones. In the systematic case, SCCD induces a gain of 1.5 dB. Theuse of the source statistics with best non systematic codes induces an additional gain ofabout 1.5dB for FER 10−4 with µ = 0.1 in Figure (1.16), this gain decreases to over 0.9dBwhen µ = 0.2 in Figure (1.17).In fact, these simulation results meet the theoretical limits shown in Figures (1.12)

and (1.2) expecting that the disadvantage of systematic codes is more significant withhighly biased sources. It is also more significant at high rates as depicted in Figure (1.18)withR = 0.9. While the gain of the split based code over a systematic code is about 1.5dBfor FER 10−4 at rate R = 1/2, this gain increases to over 4.9dB for R = 0.9. Such gains arein agreement with the minimum achievable SNR gains shown in Figures (1.3),then withthe mutual information curves shown for different coding rates in (1.11).MN codes and scramble-LDPC codes have very close performance in Figure (1.16),

while MN codes still slightly better as expected in section (1.4.4).In the Figure (1.18) we

30

Page 41: Phd dissertation

1.7. SIMULATION AND RESULTS

1E-04

1E-03

1E-02

1E-01

1E+00

-1 -0.5 0 0.5 1 1.5 2 2.5

Fra

me

Err

or R

ate

SNR

(3,6) systematic LDPC without SCCD(3,6) systematic LDPC with SCCD

scrambler ds=2splitter ds=5

Figure 1.17: Word error probabilities vs. signal to noise ratio Eb/N0 for codes with rateR = 1/2 length N = 2000 and non uniform source distribution µ = 0.2 : systematicregular (3,6) LDPC with and without SCCD,and scramble-LDPC ds = 2.and split-LDPCwith ds = 5.The systematic code is the core code of the non systematic ones.

1E-04

1E-03

1E-02

1E-01

1E+00

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5 4

Fra

me

Err

or R

ate

SNR

(3,30) systematic LDPC with SCCDscrambler ds=5

splitter ds=7

Figure 1.18: Word error probabilities vs. signal to noise ratio Eb/N0 for codes with rateR = 0.9 length N = 2000 and non uniform source distribution µ = 0.1 : systematicregular (3,30) LDPC with SCCD,and scramble-LDPC ds = 5.and split-LDPC with ds = 7.The systematic code is the core code of the non systematic ones.

31

Page 42: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

1E-04

1E-03

1E-02

1E-01

1E+00

-2.5 -2 -1.5 -1 -0.5 0

Fra

me

Err

or R

ate

SNR

ds=3ds=5ds=4ds=2

Figure 1.19: Word error probabilities vs. signal to noise ratio Eb/N0 for codes with rateR = 1/2 length N = 2000 and non uniform source distribution µ = 0.1 with differentsplitter degrees ds = 2, 3, 4, 5.

observe that the scramble-LDPC codes achieve close performance to split-LDPC codes athigh rates, this is because their ds values at these rates are rather large.The results showthe advantage of the split-LDPC codes over all the other codes.The Figure (1.19) shows simulations of a regular split-LDPC for different values of

ds and a (3,6) LDPC core code. The performances vary subject to the splitter degree ds,while the variations are not linear. If a splitter or a scrambler with an improper degreedistribution is used, the performance can actually degrade from that of systematic codesas shown in the scramble-LDPC case in [79]. Hence, we conclude that the degree of thesplitting as scrambling should be optimized for a fixed source entropyHs.

1.8 Conclusions

In this first chapter we have introduced and studied a general approach to design a novelnon systematic LDPC codes family dedicated to encode non redundant data and able tobe decoded through an SCCD belief propagation over its related factor graph.We have shown theoretically the advantage of non systematic constructions over sys-

tematic one’s, as well as the importance of an SCCD decoding in both cases. It has beenrevealed using information theoretical tools, that this advantage is more significant withhigh rate codes and highly biased sources. Simulation results support these theoreticaldemonstrations except for those related to the degree of scrambling.In fact, splitting and scrambling degrees have been shown empirically to have a non

linear impact on the performances. Thus, it has been pointed out that those degreesshould be optimized following the considered source entropy.

32

Page 43: Phd dissertation

1.8. CONCLUSIONS

Simulation results as well as theoretical one’s confirm the supremacy in term of per-formance of splitting structures over all other non systematic codes on graph construc-tions including MN codes. This latter family has been identified as a specific configura-tion of our proposed design framework. Besides, the proposed general decoding proce-dure gives an enhanced decoding alternative for the MN codes.In addition, we have revealed the non systematic LDPC general framework as a spe-

cial case of a multiedge cascaded construction dedicated to channel encoding non uni-form sources. This general classification involves an additional significance to the multi-edge extension of LDPC ensembles.While the study has been made for i.i.d sequences with known statistics, extending

it to more complex source models even if the statistics are unknown in advance still anopen issue to further study.

33

Page 44: Phd dissertation

1. NON SYSTEMATIC CONSTRUCTIONS OF CODES ON GRAPH FOR REDUNDANT DATA

34

Page 45: Phd dissertation

Chapter 2

Density Evolution Analysis forSplit-LDPC Codes

In the previous chapter, we have demonstrated using information theory tools thatthe theoretical limits related to non systematic constructions are moving to better regionsin presence of redundancy. In order to attain these limits we have introduced a novelclass of non systematic constructions belonging to the capacity achieving LDPC codefamily. Among those constructions the split-LDPC one has been revealed to outperformthe prior LDPC constructions as well as the other realizations of our codes.

In the present chapter we propose to perform an asymptotical analysis of the split-LDPC source controlled sum-product decoding, for the purpose of evaluating how closethe asymptotical performance of the considered construction is approaching the challeng-ing theoretical limits in presence of redundancy. Therefore, we have chosen the densityevolution as an asymptotic analytical tool for modeling how decoding would proceed onan infinitely long code.

We start with a general background on the density evolution principle for systematicLDPC codes. Subsequently , we propose a message type oriented density evolution for-malism dedicated to the split-LDPC. We follow with extending the general density evo-lution analysis of LDPC codes to our non systematic construction. Hence, we detail eachfeature, assumption and result (consistency, monotonicity, fixed points) extended fromthe general theory to the split-LDPC case. Finally, we provide a complete stability anal-ysis dedicated to the convergence of the split-LDPC source controlled iterative decoder.The latter analysis will be completed by deriving a novel general stability condition forthe split-LDPC codes.

35

Page 46: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

2.1 Introduction

2.1.1 Motivation and Related Work

The analysis of iterative decoders consists in the study of the statistics of the extrinsicmessages at each iteration. In a successful decoding, the extrinsic information gets betterand better as the decoder iterates using the information from the channel (the intrinsicinformation) and the information from the previous iteration (the extrinsic information).The most complete analysis is known to be the "Density Evolution Analysis" that has

been proposed by Richardson et al. in 2001 and consists in studying the evolution of thepdf of extrinsic messages iteration by iteration ([75], [73]). However, as an approximateanalysis, onemay study the evolution of a single parameter representative of this density.In their original work , Richardson and Urbanke extended the main idea of LDPC

code analysis used by Gallager for Algorithm A and also BEC decoding to more gen-eral message passing algorithms, where the message alphabet is the set of real numbers[75]. They also showed that for many interesting channels, including additive whiteGaussian noise channels, one can calculate a threshold value for the ensemble of ran-domly constructed LDPC codes which determines the boundary of the error-free regionasymptotically, as the block length tends to infinity. This is because, the LDPC codes areasymptotically good [33] and are showing their best average asymptotical performancewith infinite length.In essence, the density evolution algorithm is an asymptotic analytical tool used to

modeling how decoding would proceed on an infinitely long code by determining thestatistics of the entire decoding process. Using this technique one can compute the pdfof LLR messages at any iteration, or test whether, for a given channel condition, thedecoder converges to zero error-probability or not. Density Evolution is also used as aprobe for the design of good irregular LDPC codes, i.e, finding the convergence thresholdof different irregular codes and choosing the best one.In practice, the threshold evaluation is done using basic features, assumptions and re-

sults (consistency, monotonicity, fixed points) issued from the density evolution analysis[67], [68], [72].Such analysis is based on the consideration of the density evolution formalism as

a dynamic system in a space of probability distributions representing the progress ofiterative decoders in the infinite block length limit where convergence is interpreted asthe convergence of the system to a fixed point and the threshold is the point at whichother fixed point solutions come into existence[90], [66], [44], [109], [71].In addition to make the threshold calculation feasible, the density evolution analysis

gives more insight and understanding to the behavior and the convergence of iterativedecoding systems.Density evolution is not specific to LDPC codes and is a technique able to be adopted

for other codes defined on graphs associated with iterative decoding. For instance , thesame general theory is applied for turbo decoding analysis [68] ,[66],[90].After identifying the split-LDPC codes, as the best non systematic LDPC construc-

tion to encode redundant data, we propose to determine their asymptotical performanceand evaluate how close are they from the theoretical limits by using the density evolutiontechnique. For this purpose, we need to conform the general theory associated to the clas-sical density evolution analysis, with the particularities of the Split-LDPC construction aswell as those of the considered source statistics.

36

Page 47: Phd dissertation

2.1. INTRODUCTION

The latter task is opening a number of specific issues, we propose to answer in thepresent chapter. First, in order to derive a particular density evolution algorithm forsplit-LDPC, it is required to define an associate support tree considering the differentmessage types.Then, we will study and exhibit some analytic properties of density evolution for

split-LDPC source controlled belief propagation decoders. We will check that the as-sumptions and conditions associated to the general theory, remain realized in presence ofredundancy. For instance, the non uniform distribution of the source, makes some sourcesequences more likely than others. This fact cancels the all-one codeword assumption inits classical form. Which is similar to the case of symbol-dependent asymmetric chan-nels where the noise distribution is codeword dependent, and thus, some codewords aremore noise resistant than others [100].In order to make our analysis complete, we need to consider the stability of the dy-

namical system associated to the split-LDPC density evolution algorithm . Accordingly,we propose to figure out if the stability of the whole system is associated to the stabilityof the constituent LDPC code for a considered channel condition.Deriving a stability condition associated to the split-LDPC codes is the ultimate issue

to be investigated in the present chapter. Besides determining wether the convergence ofa specific construction would be stable or not, adressing that issue would help to find outwether the source statistics and the splitter structure are involved in the system stability.

2.1.2 Contributions

The novelty of this chapter is based on the results reported in the two papers presentedat the Allerton Conference on Communication, Control, and Computing in 2005 [5] and2006 [4].The innovative contribution in this chapter is threefold.First, we derive a message-type oriented density evolution algorithm for the split-

LDPC codes. The proposed formalism is done on more than one associated supporttree. Moroever, the non realization of the all one codeword restriction is circumvented byaveraging over all valid codewords.Then, we study and exhibit some analytic properties of density evolution for split-

LDPC source controlled belief propagation decoders. We describe the basic features, as-sumptions and results (consistency, monotonicity, fixed points) issued from the classicaldensity evolution analysis and extended to the split-LDPC case. Using these concepts wedefine the threshold determination procedure.Finally, we carry out a stability analysis for the split-LDPC iterative decoding con-

vergence and derive an associated stability condition involving the source statistics aswell as the splitter structure. The developed asymptotical analysis is generic to all binarymemoryless symmetric channels.The most important results are the following :

• We derive a message type oriented density evolution algorithm for Split LDPCcodes despite the non realization of the all-one codeword restriction. We use thedensity evolution as an analytical tool to evaluate the threshold value of several ir-regular and regular constructions. The obtained results reveal that the split-LDPCconstruction is capacity achieving and show good asymptotical performances.

37

Page 48: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

• We study the main analytic properties of density evolution for split-LDPC sourcecontrolled belief propagation decoders. The basic features, assumptions and re-sults of the general theory including consistency, monotonicity and fixed points, areextended to the split-LDPC case. Using these concepts we define the threshold de-termination procedure.

• We perform a message type oriented stability analysis to the split-LDPC and derivea general stability condition depending on the source statistics and the degree ofthe splitter.

• We reveal the local convergence of the split-LDPC decoder to be stable if the con-stituent LDPC code realizes the general stability condition for a considered channelcondition. We show that the concatenated splitter doesn’t disturb the stability ofthe constituent core-LDPC.

2.2 Preliminaries on Density Evolution

In our notations we still consider a linear binary LDPC code with B.P.S.K modulatedcodewords transmitted over a binary input memoryless channel then decoded via a mes-sage passing algorithm.We still consider the L.L.R representation such that the sign of the LLR message in-

dicates whether the transmitted bit is estimated to be −1 or 1, and its absolute value is ameasure of the reliability of this estimate.

2.2.1 Concentration and The local tree assumption

Theorem 1. The general concentration theorem: As n increases , certain quantities such asthe average decoded bit error probability, concentrate: In the probabilistic sense, different instancesof the graph and different channel realizations will behave similarly with respect to average quan-tities.

The latter theorem include two distinct parts. The first one shows convergence ofthe expected performance to the asymptotic value, the second part shows concentrationof the performances around the mean as a function of length. This concentration is fur-ther separated into concentration over input noise and concentration over the randomensemble of graphs.In practice the second one is of most interest as it brings a major simplification for

the analysis by asserting that the individual behavior of elements of an ensemble is withhighly probability close to the ensemble average. Therefore, Assuming sufficiently largeblocklengths, the ensemble average is a good indicator for the individual behavior andit is preferred to focus on the design of ensembles whose average performance approachthe Shannon theoretical limits.In the other side, the key asymptotic behavior highlighted in the first part of the the-

orem is that, as n increases, the graphs become more and more locally tree-like, i.e., loopfree. This property leads to the "local tree assumption," where we assume that the girthof the graph is large enough so that the the subgraph forms a tree . This assumption al-lows a straightforward analysis of the decoding algorithm since the incoming messagesto every node become independent.

38

Page 49: Phd dissertation

2.2. PRELIMINARIES ON DENSITY EVOLUTION

Hence by the general concentration theorem we are assured that, for almost all ran-domly constructed codes and for almost all inputs, the decoder performance will be closeto the decoder performance under the local tree assumption with high probability, if theblock length of the code is long enough. From now on we base our analysis on this localtree assumption.

2.2.2 Symmetry Assumptions and the All one Codeword Restriction

Let us consider observations messages as random variables taken their values in O. Themessages exchanged between nodes are also random variables taking their values insome message alphabetM.Let us also denote the variable node message map as :

ψℓv : O ×Mdb−1 −→ M

ψℓv(LLR0, LLR1, ..., LLRdb−1) = LLR0 +

j=1,db−1

LLRj

We denote the checknode message map as :

ψℓc : Mdc−1 −→ M

ψℓc(LLR1, ..., LLRdc−1) = 2 tanh−1(

j=1,dc−1

tanh(LLRj

2))

The analysis and notations are simplified by assuming the symmetry of the channeland decoder defined as following:

Definition 2.1 (Symmetry Conditions). :

• Channel Symmetry: The channel is output symmetric

p(yi = 1|xi = 1) = p(yi = −1|xi = −1)

• Checknode Symmetry: Signs factor out of checknode message maps:

ψℓc(b1LLR1, ..., bdc−1LLRdc−1) = ψℓ

c(LLR1, ..., LLRdc−1)(dc−1∏

i=1

bi)

for any ±1 sequence (b1, ..., bdc−1)

• Variable node Symmetry: Sign inversion invariance of variable node message maps:

ψℓv(−LLR0,−LLR1, ...,−LLRdb−1) = −ψℓ

v(LLR0, LLR1, ..., LLRdb−1)

and ψ0v(−LLR0) = −ψ0

v(LLR0).

It has been proved [75] that under these conditions the error probability is indepen-dent of the transmitted codeword. The great simplification resulting from the symmetryassumptions is that one need only to determine the probability of error for a single code-word, the all-one codeword. Thus, messages are correct when their sign is positive andincorrect when their sign is negative. In term of message distribution, the probability ofan incorrect message is the probability mass of the distribution supported on negativevalues.In the sequel we assume the all-one codeword transmitted, and the symmetry condi-

tions fulfilled.

39

Page 50: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

2.2.3 General Statement of Density Evolution

In 2001, Richardson and Urbanke extended the main idea of LDPC code analysis usedfor Algorithm A and B and also BEC-decoding to other message passing decoding algo-rithms [75]. Considering the general case, where the message alphabet is the set of realnumbers, they proposed a technique called density evolution, which tracks the evolutionof the pdf of the messages,iteration by iteration.This algorithm computes numerically the average asymptotic behavior of a sum-

product decoder for LDPC codes, which is the limit of the average performance of an en-semble LDPC (n, λ, ρ) in terms of the blocklength, following the Theorem (1).This asymp-totic performance is evaluated under the local tree assumption, exploiting the recursivestructure of the tree.

dc − 1

db − 1

PCEdc

PCE2PCE1

cdb

PCEdc−1

c1 c2 cdb−1

Figure 2.1: The tree describing a regular (db, dc) LDPC.

Let us describe first the density evolution algorithm for a regular (db, dc) LDPC overthe tree illustrated in Figure (2.2.3), then we will generalize to irregular structures.Firstly, let Po denotes the initial message distribution under the assumption of the all-

one codeword. Following the sum-product description in the section (1.5) let us remindthat the message from a variable node to a checknode denoted v equals the sum of allincoming LLRs.

v =

db−1∑

i=0

ui (2.1)

where ui, i = 1, ..., db − 1, are the incoming LLRs from the neighbors of the variablenode, except the checknode that gets the message v.

40

Page 51: Phd dissertation

2.2. PRELIMINARIES ON DENSITY EVOLUTION

The density of the sum of db random variables can be easily calculated by convolutingthe densities of the ui’s, which can be efficiently done in the Fourier domain [75].Let fw denotes the distribution of a random variable w. Then the distribution at the

output of a bitnode is written as :

Pv =

db−1⊗

i=0

Pui(2.2)

where⊗denotes convolution.

The message from checknode to variable node denoted u follows the tanh rule as thefollowing :

tanh(u

2) =

dc−1∏

i=1

tanh(vi

2) (2.3)

Hence, we define the operatorRi as :

Ri : Ri −→ R (2.4)

Ri(v1, v2, ..., vi) = 2 tanh−1( i∏

j=1

tanh(vj

2))

(2.5)

Then the update rule is written as :

u = Rdc−1(v1, v2, ..., vdc−1) (2.6)

where vi , i = 1, ..., dc−1, are the incoming LLRs from dc−1 neighbors of a checknode.To evaluate the output distribution at the checknode we need to take the logarithm

on each side of the equation (2.3) to convert the product into a sum:

(su, log | tanhu

2|) =

dc−1∑

j=1

(svj, log | tanh

vj

2|) (2.7)

where su and svjare the signs of u and vj , 1 ≤ j ≤ dc − 1, respectively. sx is defined

as 0 if x ≥ 0 and 1 otherwise. Thus the sum for the sign is performed in Z2, and the sumfor the magnitude is in R. The checknode’s update rule can be done numerically usinggeneralized Fourier transforms.The generalization to irregular codes is given in the following theorem :

Theorem 2. Density EvolutionLet P0 denote the initial message distribution, under the assumption that the all one codewordwas transmitted, of a low-density parity check code specified by edge degree distributions λ(x) =∑

i λixi−1 and ρ(x) =

∑i ρix

i−1. If P ℓu denotes the density of the messages passed from the

checknodes at round ℓ of the belief propagation, with P 0u = δ0, then we have :

P ℓu = ρ(P0 ⊗ λ(P ℓ−1

u )) (2.8)

The detailed analytical formulation of this technique can be found in [75] and also in[21], but in many cases it is too complex to be useful for direct use. In practice, discretizeddensity evolution [21] is used. The idea is to quantize the message alphabet and use

41

Page 52: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

probability mass functions (pmf) instead of pdfs to make a computer implementationpossible.In the discrete version of density evolution, in the update rule for computing the

distribution at the variable node output, the convolution is replaced by discrete convo-lution. At the checknode output, the output distribution is obtained using a pairwiseR-convolution between input pmfs. Note that this operation can be done using a pre-computed table, which is the key step for making discretized density evolution compu-tationally efficient.Considering the sum-product update rule for a checknode with two inputs whose

input densities are given as pmfx and pmfy and assuming a uniform quantization of themessages with a quantization interval of ∆, The R-convolution is defined as :

pmf [k] =∑

(i,j):K∆=R(i∆,j∆)

pmfx[i] × pmfy[j], (2.9)

where the operatorR is defined as :

R(x, y) = Q(R2(x, y)) (2.10)

where x and y are quantized messages and Q is defined as the quantization function andis given as :

Q(w) =

⌊w∆

+1

2⌋.∆ if w ≥ ∆

2

⌊w∆

− 1

2⌋.∆ if w ≤ ∆

2

0 otherwise

(2.11)

R operates pairwise over the discrete values :

u = R(v1,R(v2,R(v3, ...R(vdc−2, vdc−1)))) (2.12)

The R operation can be done using a pre-computed table, which makes discretized den-sity evolution computationally efficient. The R-convolution is also referred to using theoperatorR, which still pairwise with pmfs as in the following :

Pu = Rj−1(Pv) = R(Pv ,R(Pv ,R(Pv , ...R(Pv , Pv)))) (2.13)

By defining λ(p) =∑db

i=2 λi⊗i−1 p, and ρ(p) =

∑dc

j=2 ρjRj−1p, we can define discretizeddensity evolution as in the following theorem :

Theorem 3. Discrete Density evolutionDiscrete density evolution is described by :

P ℓ+1u = ρ(Pu0 ⋆ λ(P (ℓ)

u )) (2.14)

where the initial pmf is P(0)u = δ0, ℓ is the iteration number, and ⋆ denotes the discrete convolu-

tion.

42

Page 53: Phd dissertation

2.3. STATEMENT OF SPLIT-LDPC DENSITY EVOLUTION

2.3 Statement of Split-LDPC Density Evolution

In this section, we describe how density evolution can be performed on a split-LDPCcode, in presence of redundant data, in order to determine the code threshold underiterative decoding on a binary symmetric channel.The proposed density evolution should take into account the non uniformity of the

source and the unique structure of the split-LDPC decoding graph. Consider a split-LDPC code built by the simple cascade of a (η(x), ρα(x)) splitter and a (λ(x), ρ(x)) binaryLDPC code.The multiedge structure of the split-LDPC including three variable nodes types and

two checknodes types, imply three types of messages going from bitnodes toward chec-knodes denoted P1, P2 and P3, then two types of messages flowing from checknodestoward variable nodes denoted Pα and Pβ .Accordingly, the the local tree assumption has to be done over three types of trees,

where the density evolution algorithm would describe separately the evolution of eachone of the messages P1, P2 and P3.Messages propagating on graph edges are of LLR-type, and will be characterized by

their probability density function (pmf in the implemented discretized version).The notations related to the three tree types are described in the following accordingly

to the Figures (2.2), (2.3) and (2.4) :

• The probability distribution of LLR-messages going from u nodes to α nodes isp1(x). These are type-1 messages. A type-1 message includes ds − 1 incomingextrinsics from checknodes α and db incoming extrinsics from checknodes β.Thetree representation of type-1 messages is illustrated in Figure (2.2). Source nodes sare hidden inside α checknodes.

dc − 1

βα β

u

ds − 1

u u

α

12u + 1

ds − 1 db

12u + 1

η(x) xλ(x)

α

R P2 + (1 − R) P3P1

P1

Figure 2.2: Tree representation for type-1 messages for rate R = 1/2 split-LDPC.

43

Page 54: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

dc − 1

βα β

u

ds − 1

u u

α

β

db − 1ds

12u + 1

2ϑ12u + 1

xη(x) λ(x)

P1 R P2 + (1 − R)P3

P2

Figure 2.3: Tree representation for type-2 messages for rate R = 1/2 split-LDPC.

ϑ

β

β

dc − 1

db − 1

12u + 1

2ϑ12u + 1

P3

β βR P2 + (1 − R)P3

Figure 2.4: Tree representations for type-3 messages for rate R = 1/2 split-LDPC.

44

Page 55: Phd dissertation

2.3. STATEMENT OF SPLIT-LDPC DENSITY EVOLUTION

• The probability distribution of LLR-messages going from u nodes to β nodes isp2(x). These are type-2messages. A type-2message includes ds incoming extrinsicsfrom checknodes α and db − 1 incoming extrinsics from checknodes β. The treerepresentation of type-2 messages is illustrated in Figure (2.3).

• The probability distribution of LLR-messages going from ϑ nodes to β nodes isp3(x). These are type-3 messages. A type-3 message includes db − 1 incoming ex-trinsics from checknodes β. The tree representation of type-3messages is illustratedin Figure (2.4).

• The probability distribution of LLR-messages propagating from α checknodes to uvariable nodes is denoted pα(x). Finally, in a similar fashion, probability distribu-tion of messages generated by β is pβ(x).

• The source nodes s are considered as absorbed in the α nodes, hence they don’tappear in the tree . However their pmf is considered in the DE computation as asource probability mass ps(x) = δs = δ(x−s) located on the source a priori messagedenoted s = log

(1−µ

µ

).

Lemma 2.3.1. Consider a split-LDPC code built by the cascade of a splitter and a (λ(x), ρ(x))binary LDPC code. For uniform sources, the threshold of the split-LDPC code under iterativedecoding is equal to the threshold of the embedded (λ(x), ρ(x)) LDPC code.

Proof: If the source is uniform then LLR-message distribution propagating from s nodesto α is ps(x) = δ0, the unit mass on the origin. Hence, at any decoding iteration, it isobvious that pα(x) = δ0. The simple cascade in Figure (1.15) is now reduced to the origi-nal LDPC code with density evolution on u, ϑ and β. Also, p2(x) and p3(x)will be equal.Since a source bit is equal to the sum of a finite number ds of u bits, then, error probabilityon source bits admits the same threshold as that on u bits. �

Theorem 4. Consider a split-LDPC code built by the simple cascade of a ds-splitter and a(λ(x), ρ(x)) binary LDPC code. For a nonuniform binary i.i.d. source characterized by µ. Letus introduce the distribution qm

1 (x) = ρα (pm1 (x)), hence the density evolution is performed as

follows:

pmα (x) = R

(ps(x), (1 − µ) qm

1 (x) + µ qm1 (−x)

)

pmβ (x) = ρ (Rc p

m2 (x) + (1 −Rc) p

m3 (x))

pm+11 (x) = p0(x) ⊗ λ1α (pm

α (x)) ⊗ λ1

(pm

β (x))

pm+12 (x) = p0(x) ⊗ λ2α (pm

α (x)) ⊗ λ(pm

β (x))

pm+13 (x) = p0(x) ⊗ λ

(pm

β (x))

where the superscriptm represents the decoding iteration index, the symbol ⊗ represents classicalconvolution, p0(x) is the Gaussian distribution conditioned on a +1 transmitted symbol, and thepolynomials are given by ρα(x) = λ1α(x) = xds−1, λ2α(x) = xλ1α(x) and λ1(x) = xλ(x).

45

Page 56: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

Proof: The local tree assumption aswell as the symmetry assumptions are realized thanksto the channel symmetry and the split-LDPC structure.However, the all one codeword restriction is not always applicable with non uniformsources. When a non-uniform source is encoded by a systematic LDPC code, the sizeof the typical set of transmitted codewords is reduced from 2K to 2KHs . The zero code-word is the most probable codeword (0 < µ < 1/2) but it does not belong to the typicalset. Classical density evolution assuming a zero transmitted codeword cannot work forthe ensemble of systematic LDPC codes defined by the mono-edge degree distribution(λ(x), ρ(x)) with a nonuniform source.Fortunately, in the case of split-LDPC,the splitter produces a marginal uniform distribu-tion at its output (the inverse of a sparse matrix is dense, see [12]), i.e. P (u = 0) = P (u =1) = 1/2 for any bitnode u. In addition, in the ensemble of split-LDPC codes defined by arandom splitter and random LDPC code, we have p1(x|u = 0) = p1(−x|u = 1), the sameassumption is valid for p2(x) and also p3(x|ϑ = 0) = p3(−x|ϑ = 1).The nonuniform source distribution is taken into account during the split-LDPC densityevolution process by two means:

1. Source a priori information is represented by a probability mass ps(x) = δs located

on the log-ratio log(

1−µµ

). Adding the source a priori is made inside α checknodes

while propagating p1(x) and p2(x).

2. Thanks to the symmetry in the R-operator, and the symmetry of message distribu-tions in the split-LDPC ensemble, when s = 1 a unique u bit connected to α will beequal to 1 with probability µ, which makes p1(x|u = 1) replaced by p1(−x|u = 0).Other u bits connected to α can be forced to zero.

3. Let us consider a distribution q(x) = R(p(x), p(x)). With the use of the R-operatorsymmetry property , we haveR(p(−x), p(−x)) = q(x) andR(p(−x), p(x)) = q(−x).Then we consider a distribution q(x) = R(p(x),R(p(x), p(x))). With the use of theR-operator symmetry property , we can write:

R(p(−x),R(p(x), p(x))) = q(−x).

Then we consider a distribution q(x) = R(p(x),Rds−2(p(x))), that also realizes :.

R(p(−x),Rds−2(p(x))) = q(−x)

Following these considerations, the distribution at the output of the α checknodes, isobtained by averaging the related output distributions with respect to the source variablenode value s as in the following :

pmα (x) = R

(ps(x), (1 − µ) ρα (pm

1 (x)) + µ R (pm1 (−x), ρ1α (pm

1 (x))))

where

ρ1α(x) = ρα(x)/x.

Regarding, the other equations of the density evolution algorithm, they are obtainedfrom each tree’s structure in a straightforward manner.

46

Page 57: Phd dissertation

2.4. ANALYTIC PROPERTIES OF SPLIT-LDPC DENSITY EVOLUTION

The density evolution statement given in the present section, describes the evolutionof the message distributions all over the decoding iterations. The density of messagesafter ℓ iterations is only a function of the channel condition. In [75], Richardson andUrbanke showed that there is a worst case channel condition for which the message er-ror rate approaches zero as the number of iterations approaches infinity. This channelcondition is called the threshold .In the next section, we will consider the analysis of source controlled belief propa-

gation for split-LDPC. Some issues will be very resembling with the general analysis ofbelief propagation decoding, and others will require a more particular study.

2.4 Analytic Properties of Split-LDPC Density Evolution

In the present section we propose to analyze the split-LDPC density evolution developedin the previous section and stated in the theorem (4).We propose to start with extending the important concepts of the general theory to

the split-LDPC case. These concepts are supporting the practical procedure dedicatedto the threshold determination described afterwards. Then, we will show how the con-sequent features, assumptions and results contribute to give a dynamic system orientedinterpretation to the iterative decoders’ behavior. Finally, we will study the local conver-gence of our SCCD iterative decoder through a stability analysis and derive a split-LDPCrelated stability condition.

2.4.1 The Consistency Condition

For channels of interest the density of a received log-likelihood value satisfies a certaincondition referred to as the ’Consistency Condition’ and sometimes as ’Symmetry Condi-tion’:

Definition 2.2. We call a distribution f on R consistant if it satisfies :

f(x) = f(−x) ex for all x ∈ R+ (2.15)

We remind that considered messages and received values are conditional log like-lihoods on an associated bit assumed to have been transmitted. When the channel issymmetric the initial message distribution P0 is consistent and the consistency propertyis preserved under density evolution in the general case. Let us notice that δ∞ and δ0 areconsistent distributions.The Split LDPC trees are mostly resemblant to any systematic LDPC one, except in

the regions where the source operates, namely in the subgraphs including the α chec-knode. In fact, in these regions the density evolution equations differ, since the all-onecodeword assumption is not realized anymore. Hence we should prove the consistencyat the output of these nodes.

Lemma 2.4.1. The Consistency is invariant under the splitter processing.

Proof: The distribution at the output of α checknodes is given by :

pα = (1 − µ)R(ps(x), p(x)) + µR(ps(x), p(−x))

Where ps(x) = δ(x− s) = δs and s = log(1 − µ

µ).

47

Page 58: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

Let us denote p(x) = qm1 (x) = ρα (pm

1 (x)) defined in the theorem (4), and proved to beconsistent following the fact that consistency is preserved under R-convolution as wellas under convolution [67].The parametric description of the α checknode output distribution is given by:

t = 2arctanh((1 − 2µ) × tanh(x

2)) (2.16)

pt(x) = [(1 − µ)px(x) + µpx(−x)] ×1 − (1 − 2µ)2tanh2(x/2)

(1 − 2µ) × (1 + tanh2(x

2))

(2.17)

using the consistency property of px(x)we obtain:

pt(x) = px(x)[(1 − µ) + µe−x] × 1 − (1 − 2µ)2tanh2(x/2)

(1 − 2µ) × (1 + tanh2(x

2))

In order to evaluate pt(−t), let us notice that pt(−t) = pt(−x) and write the distributionas:

−t = 2arctanh((1 − 2µ) × tanh(−x2

))

pt(−t) = px(x)[(1 − µ)e−x + µ] × 1 − (1 − 2µ)2tanh2(x/2)

(1 − 2µ) × (1 + tanh2(x

2))

The fractionpt(−t)pt(t)

is evaluate in the following as:

pt(−t)pt(t)

=(1 − µ)e−x + µ

(1 − µ) + µe−x

besides, using the fact that arctanh(x) = 12 ln(

1 + x

1 − x)we can find that :

et = e2arctanh((1−2µ)×tanh(x/2))

=1 + (1 − 2µ)tanh(x/2)

1 − (1 − 2µ)tanh(x/2)

=(1 − µ) + µ e−x

µ+ (1 − µ)e−x

Consequently we obtain et =pt(t)

pt(−t)and :

pt(−t) = pt(t) × e−t

Hence, we have proved that pt(t) is consistent. The Figure (2.5) illustrates this result.�

48

Page 59: Phd dissertation

2.4. ANALYTIC PROPERTIES OF SPLIT-LDPC DENSITY EVOLUTION

0

0.05

0.1

0.15

0.2

0 0.5 1 1.5 2 2.5

Pro

babi

lity

Den

sity

Fun

ctio

n

x

P(-x)=P(x)*exp(-x) when x>0

P(-x)P(x)*exp(-x)

Figure 2.5: Consistency of the Splitter Output distribution

2.4.2 Monotonicity and Convergence to Fixed Points

Let us define the the error probability operator in the following definition:

Definition 2.3. We define the error probability operator related to a consistent function f as :

Prerr(f) =

∫ 0

−∞f(x) dx (2.18)

Hence, the probability of error is defined as the negative tail of the density, this isdue to the symmetry of the considered distributions. Furthermore, the error probabilityoperator plays a central role in the analysis, since it realizes the projection of the messagedistributions living in RR into a one dimensional space of R.The major features and results issued using the projection of the distributions to a

corresponding error probability, can be summarized as in the following:

• The Successful Decoding Characterization : If f(x) is a consistent distributionthen Prerr(f) = 0 if and only if f = δ∞.The convergence of the probability of errorto zero is equivalent to requiring the message density to converge to delta functionat infinity.

• General Monotonicity Law Theorem :

Theorem 5. Let Pℓ be the message distribution at the ℓ-th decoding step and let g be aconsistent distribution on R. Then Prerr(Pℓ ⊗ g) is a non-increasing function of ℓ.

49

Page 60: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

• Fixed Point Theorem :

Theorem 6. Let f be a consistent distribution and assume that f has support over thewhole real axis. Let Pℓ1(x) and Pℓ2(x) denote the message distributions at the ℓ1-th andthe ℓ2-th iteration respectively, with ℓ1 < ℓ2. If Prerr(Pℓ1 ⊗ f) = Prerr(Pℓ2 ⊗ f) thenPℓ1(x) = Pℓ(x) for ℓ ≥ ℓ1, i.e., Pℓ1(x) is a fixed point of density evolution.

We refer the reader to the literature for details and proofs in [67], [73], [75], [72], [68], [71].The above general results show that although the message distributions of the belief

propagation decoder live nominally on RR, they can be ordered by one real parametervia the projection. This is very much like the simple one-dimensional case we encounterwith the erasure channel case. This kind of ordering corresponds to a partial ordering ofchannels with respect to a given code and decoder.In fact, it has been shown [67] that to any consistent density P one can associate a

memoryless binary input symmetric channel defined by p(y|x = 1) = P (y) and p(y|x =−1) = P (−y). Hence given two symmetric densities Q and P , we say P is physicallydegraded with respect to Q if the symmetric channel related to P is physically degradedwith respect to the symmetric channel related to Q. The authors of [73] proved that anysequence of densities ordered by physical degradation converges to a limit density.The particular distribution δ∞ is a fixed point of density evolution characterizing a

successful decoding, where the convergence of densities to δ∞ is equivalent to conver-gence of the associated probability of error to 0. We conclude that the density evolutionis always admitting a fixed point, which is δ∞ when the decoding is successful otherwiseit would be another limit density.The uniqueness of the fixed point δ∞ or the existence of other fixed points depends

on the noise level,and the frontier between the two cases in term of noise level is calledthe decoding threshold. Let us explain in the next subsection more about this concept anddescribe how to evaluate it.

2.4.3 Thresholds and Density Evolution Fixed Points

The decoding threshold of the coding system is usually defined as the supremum noiselevel such that the probability of error tends to zero as the number of iterations tends toinfinity.Considering the density evolution as a non linear dynamic system in a space of prob-

ability distributions, the decoder convergence is interpreted as the convergence of thesystem to a fixed point. One fixed point always exists, it is δ∞ which is the distributionthat correspond to the perfect information.Besides,The decoding threshold can also be defined as the point at which other fixed

point solutions to density evolution come into existence [71]. That is to say that belowthe threshold the existence of other fixed point solutions is impossible even if the iterativeprocess doesn’t converge to them.Let us consider a one parameter family of channels ordered by physical degradation,

and let σ denote the channel parameter with increasing it indicating noisier channels.Then, let us denote the decoding threshold by σ∗.This alternative interpretation associated to the threshold, helps to use density evolu-

tion as a practical tool to evaluate the threshold using the following procedure :

50

Page 61: Phd dissertation

2.5. THE STABILITY ANALYSIS OF SPLIT-LDPC DENSITY EVOLUTION

1. We fix the channel parameter, namely noise power. We also fix a practical errorprobability threshold Pth.

2. We run the density evolution algorithm iteratively until either the extrinsic messagedistribution tends to the δ∞, or it converges to a density with a finite probability oferror.

3. Evaluate the probability of error defined as the negative tail of the density. If theprobability of error is under a threshold Pth increase the noise power and reiteratethe procedure from the second step. Otherwise the present channel parameter willbe the decoding threshold σ∗.

Let us precise that the messages u → α are used for the final decision to estimatesource bits. Thus, the error probability related to those messages type is the one com-pared to Pth.Additionally to the decoding threshold, let us define the stability threshold denoted by

σstab such that when the evolution of the densities has reached a point where the indicatedprobability of error is sufficiently small:

• If σ < σstab the density will actually converge to δ∞ and the probability of error isguaranteed to converge to zero.

• If σ > σstab the probability of error will be bounded away from zero and will di-verge to a limiting value.

When σ < σstab, the fixed point δ∞ is asymptotically stable, i.e. it is an attractorfollowing the non linear dynamic behavior of the density evolution system[109], [44].While the decoding threshold is obtained practically using density evolution, the sta-

bility threshold is evaluated using the stability analysis of the density evolution system.The stability analysis purpose is the study of the local convergence to the fixed point δ∞.Usually it leads to the derivation of a stability condition, which helps in checking thestability of the decoding system.In the next section we will proceed with the stability analysis of the split-LDPC, and

the derivation of the stability condition related to it. we will also investigate asymptoti-cally the effect of the splitter on the core-LDPC stability.

2.5 The Stability Analysis of Split-LDPC Density Evolution

In general, the analysis of density evolution fixed points has so far been quite limited,with the exception of the fixed point δ∞. For this particular case, the analysis is based onthe study of the local convergence to this fixed point, when the evolution of the densitieshas reached a point where the related probability of error is sufficiently small, i.e. whenthe densities evolute to the neighborhood of δ∞.In the neighborhood of δ∞, the convergence of the densities towards this fixed point

is expected; however this wouldn’t be straightforward and might not occur . The conver-gence will happen, only if δ∞ is a stable fixed point, namely an attractor. This is relatedto a precise analytic condition called the stability condition that differentiates the two po-tential behaviors.Let us first start with some brief preliminaries about the stability condition for sys-

tematic LDPC codes, then proceed with deriving a specific stability condition for thesplit-LDPC source controlled sum-product decoding.

51

Page 62: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

2.5.1 The Stability Condition for Systematic LDPC Codes :

In its general form, the stability condition, for a systematic LDPC code, involves the chan-nel parameter σ as well as the considered code construction (λ, ρ) and is expressed as :

λ′(0) ρ′(1) < B−1(P σ0 ) (2.19)

where P σ0 denotes the channel received distribution related to the channel parameter σ

and B(P0) denotes the Bhattacharyya constant defined by :

B(P0) =

∫ +∞

−∞P0(x)e

−x/2 dx (2.20)

where P0 denotes a channel received distribution. The Bhattacharyya constant is alsodenoted as B(P0) = e−r, where r = − ln(2 P0(x) e

−x2 dx) for a consistent distribution P0

[68]. Then the stability expression can be expressed as well as :

λ′(0) ρ′(1) < er (2.21)

The stability condition has been shown to be necessary in [73] [67] and sufficient in[71] to the local convergence of distributions to δ∞. This major result has been stated in[73] through the following theorem :

Theorem 7 (General Stability Condition). .[Necessity] If B(P0)λ

′(0) ρ′(1) > 1 then the probability of error under density evolution isbounded away from zero.[Sufficiency] Conversely, if B(P0)λ

′(0) ρ′(1) < 1 then the probability of error converges to zeroonce it becomes sufficiently small.

Where the necessity proof can be found in [73], and the more involved sufficiency proofhas been proposed later in [71].

Example 1. For the BEC channel with an erasure probability ε we have:

e−r = 2

∫ ∞

0[ε

2δ0 + (1 − ε)δ∞]e−

x2 dx = ε

Then we get stability condition for the BEC given by :

λ′(0) ρ′(1) <1

ε(2.22)

Example 2. For the BSC with an error probability transition λ we have:

e−r = 2

∫ ∞

0(1 − λ)δln( 1−λ

λ)e

−x2 dx = 2

√λ(1 − λ)

Then we get the stability condition for the BSC given by :

λ′(0) ρ′(1) <1

2√λ(1 − λ)

(2.23)

52

Page 63: Phd dissertation

2.5. THE STABILITY ANALYSIS OF SPLIT-LDPC DENSITY EVOLUTION

Example 3. For the BIAWGN channel we have :

e−r = 2

∫ ∞

0

√σ2

8πe−

(y− 2σ2 )2σ2

8 e−x2 dx = e−

12σ2 (2.24)

Then we get the stability condition for the BIAWGN channel given by :

λ′(0) ρ′(1) < e1

2σ2 (2.25)

When the bound is tight the stability condition leads to an analytic upper bound onthe decoding threshold. This upper bound is the previously introduced stability thresholdσstab, hence we can write σ∗ ≤ σstab. In fact,the fixed point δ∞ is unique and stable in theregion lower than the decoding threshold. Beyond the decoding threshold, despite theexistence of several fixed points, the local convergence to δ∞ happens under the stabilitycondition.In many cases of interest the stability condition turns out to have stronger than ex-

pected implications, sometimes determining the decoding threshold. This occurs in thefamous case of cycles codes and the BSC investigated by Decreusefond and Zemor [23],where this upper bound is tight.Furthermore, the quantity λ′(0)ρ′(1) involved in the stability condition and related to

the degree distribution pair turns out to play a crucial role in the theory and practice ofLDPC codes. The relevance of this quantity is increased by the fact that it includes thefraction of edges connecting to degree-two variable nodes denoted by λ′(0). This laterpopulation has been shown necessary to LDPC codes in order to achieve capacity [85].Besides, Di has shown in[25] that for irregular LDPC ensembles when λ′(0)ρ′(1) > 1

theminimum distance grows sublinearly in the block length. Otherwise, it grows linearlyin the block length with probability

√1 − λ′(0)ρ′(1) [62] [26].

Coincidentally, the quantity λ′(0)ρ′(1) is also involved in the encoding complexity ofLDPC ensembles. As a matter of fact, when Richardson and Urbanke [74] investigatedthis issue, they showed that λ′(0)ρ′(1) > 1 is a sufficient condition for designing an "op-timized" linear time uncodable LDPC codes. Otherwise, the authors conjectured that theencoder complexity is O(n2).Furthermore, in the BEC case, Shokrollahi has shown [85] that capacity-achieving ir-

regular LDPC code sequences should fulfill the stability condition to equality, then heconjectured that the same is true for other channels. In the same paper Shokrollahi in-dicates that eventual higher stability conditions, in the general case, would lead to adeterministic algorithm for the design of good LDPC codes.Hence, Capacity-achieving LDPC ensembles satisfying certain technical conditions

over the BEC satisfy λ′(0)ρ′(1) > 1 but cannot have minimum distance growing linearlyin the block length, and are also able to be linear time encodable LDPC codes. Reducingthe gap between the general case and the BEC still presents an important open issue.Additionally to be involved in the stability condition the quantity λ′(0)ρ′(1) connects

three important code characteristics of LDPC codes: performance, encoding complexityand minimum distance. All this goes to show that the stability condition present a theo-retical as well as a practical dimension for the iterative decoding systems understanding.

53

Page 64: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

2.5.2 The Stability Condition for the Non Systematic Split-LDPC Code

In our setting, we investigate the behavior of the iterative decoding system of the split-LDPC in the neighborhood of the fixed point δ∞ and in the presence of a non uniformsource. For this purpose, we use the same general approach used in the uniform caseand study the local convergence when the evolution of the densities has reached a pointwhere the related probability of error is sufficiently small. This analysis will lead us toderive stability condition of the split-LDPC.One of the main questions arising from this context is whether it is possible to loose

the stability of a the core LDPC code, when we concatenate it to the splitter and witha non uniform source. If the answer is affirmative, is there a new stability condition tosatisfy, and does it depend on the splitter structure and the source entropy?Consider a split-LDPC code built by the simple cascade of a regular splitter and a

(λ(x), ρ(x)) binary LDPC code.Let us recall the notations for message distributions :

• p1(x): distribution of LLR messages from u to α nodes

• p2(x): distribution of LLR messages from u to β nodes

• p3(x): distribution of LLR messages from ϑ to β nodes

• pα(x): distribution of LLR extrinsics from α to u nodes

• pβ(x): distribution of LLR extrinsics from β to both u and ϑ nodes

• ps(x): source probability mass ps(x) = δ(x− s)where s = log(

1−µµ

)

Similarly to the density evolution statement, we propose to perform the stability anal-ysis separately for each message type p1(x),p2(x) then p3(x). This approach should helpin deriving a general stability condition for the whole concatenated split-LDPC code.In order to analyze local convergence to the fixed point δ∞ we consider the lineariza-

tion of density evolution about this fixed point.To that effect, consider a consistent density Q0 supposed to be received at the leaf

nodes u and v in order to initialize the density evolution :

Q0 = 2εδ0 + (1 − 2ε)δ∞ (2.26)

Following the density evolution statement described in the theorem (4) let us remindthe expressions of the distributions at the checknodes output as:

pmα (x) = R

(ps(x), (1 − µ) qm

1 (x) + µ qm1 (−x)

)(2.27)

pmβ (x) = ρ (Rc p

m2 (x) + (1 −Rc) p

m3 (x)) (2.28)

where qm1 (x) = ρα (pm

1 (x)).Then, let us recall the expressions of the distributions for each message type at the

output of each one of the three trees :

pm+11 (x) = p0(x) ⊗ λ1α (pm

α (x)) ⊗ λ1

(pm

β (x))

(2.29)

pm+12 (x) = p0(x) ⊗ λ2α (pm

α (x)) ⊗ λ(pm

β (x))

(2.30)

pm+13 (x) = p0(x) ⊗ λ

(pm

β (x))

(2.31)

54

Page 65: Phd dissertation

2.5. THE STABILITY ANALYSIS OF SPLIT-LDPC DENSITY EVOLUTION

where the polynomials are given by ρα(x) = λ1α(x) = xds−1, λ2α(x) = xλ1α(x) = xds andλ1(x) = xλ(x).

The first Iteration

At the first iteration of density evolution, the distributions at the output of each chec-knode are written as:

P 1α = (ds − 1) 2 εδ0 + (1 − µ) (1 − 2 ε(ds − 1)) δs + µ (1 − 2ε(ds − 1)) δ−s (2.32)

P 1β = ρ′(1) 2 ε δ0 + (1 − ρ′(1) 2 ε)δ∞ (2.33)

After a complete iteration of density evolution, the density of each message type willevolve to:

p11(x) ≈ δ∞ (2.34)

p12(x) = 2ε λ′(0)ρ′(1)P0 ⊗ (µ δ−s + (1 − µ) δs)

⊗ ds + (1 − 2ε λ′(0)ρ′(1))δ∞ (2.35)

p13(x) = 2ε λ′(0)ρ′(1)P0 + (1 − 2ε λ′(0)ρ′(1))δ∞ (2.36)

Let us introduce Pu0 such that Pu0 = P0 ⊗ (µ δ−s + (1 − µ) δs)⊗ dS . The latter

distribution appears in the expression of p12(x) describing the density of messages going

after the first iteration from the bitnodes u towards the checknodes β.The expression of Pu0 could be interpreted as the initial message density of an equiv-

alent channel. The equivalent channel is identified as the parallel concatenation of thechannel characterized by P0 and ds parallel concatenated BSC channel with crossoverprobability µ and initial message density µ δ−log( 1−µ

µ) + (1 − µ) δlog( 1−µ

µ).

The equivalent channel is symmetric since it is the parallel concatenation of (ds + 1)symmetric channels. We can also deduce that its initial message density of log-likelihoodratios is consistent since the consistency is invariant under the convolution[67].

Result 1. The message density given by the splitter to the core LDPC is equivalent to the initialmessage density of ds parallel concatenated BSC with a crossover probability µ.

The nth Iteration

At the nth iteration of density evolution, the distributions at the output of each chec-knode are written as:

Pnα = (1 − µ) δs + µ δ−s (2.37)

Pnβ = λ′(0)n−1ρ′(1)n2 ε(R Puo + (1 −R)P0)

⊗(n−1) + (1 − λ′(0)n−1ρ′(1)n2 ε)δ∞ (2.38)

After a n complete iteration of density evolution, the density of each message typewill evolve to

pn1 (x) ≈ δ∞ (2.39)

pn2 (x) = 2 ε(λ′(0)ρ′(1))nPu0 ⊗ (R Puo + (1 −R)P0)

⊗(n−1) + (1 − 2ε(λ′(0)ρ′(1))n)δ∞(2.40)

pn3 (x) = 2ε(λ′(0)ρ′(1))nP0 ⊗ (R Puo + (1 −R)P0)

⊗(n−1) + (1 − 2ε(λ′(0)ρ′(1))n)δ∞ (2.41)

Let us consider each message type separately in our study of the stability. When closeto zero error rate, stability of messages u→ α is not perturbed by the serial Splitter-LDPCconcatenation. Those messages are used for the final decision to estimate source bits.

55

Page 66: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

BSC

BSC

BSC

R

1−R

CHANNEL

µ

µ

µ

s

s

s

u

ϑ β

P0

ϑ

u

ds

(µ δ−s + (1 − µ) δs)⊗ ds

Figure 2.6: The equivalent channel that is seen by the core-LDPC

Result 2. For non-uniform sources,type-1 message distribution (from node u to node α) shows apermanent stability around the fixed point δ∞

The study of the stability of both message densities p2(x) and p3(x) is reduced to thesame problem, since P0 6= δ∞ and Pu0 6= δ∞, and the quantities (λ′(0)ρ′(1))nPrerr(Pu0 ⊗(R Puo+(1−R)P0)

⊗(n−1)) and (λ′(0)ρ′(1))nPrerr(P0⊗(RPuo+(1−R)P0)⊗(n−1)) converge

to zero if and only if (λ′(0)ρ′(1))nPrerr(((R Puo +(1−R)P0)⊗(n−1)) converges to zero (see

Lemma6. in [67]). This could be also explained, by the fact that the edges connecting thebitnodes u and v to the checknodes β are of the same type.Hence, the necessary condition for making the probability of error converge to zero

would be that the probability of error associated with :

(λ′(0)ρ′(1))n(R Puo + (1 −R)P0)⊗(n) (2.42)

be decaying to zero as n grows.Under very general conditions and since (RPuo+(1−R)P0) is a consistent distribution

the limit :r := − lim

n→∞

1

nlogPrerr((R Puo + (1 −R)P0)

⊗n) (2.43)

is well defined (see Lemma7. in [67]).Using the general large deviation principle used in [67] and [73] (see also,e.g.,[76]),

and taking into account the symmetry of the distribution (R Puo(x) + (1 − R)P0(x)) wecan deduce that :

r := − log(2

∫ ∞

0(R Puo(x) + (1 −R)P0(x))e

−x2 dx) (2.44)

Here, we identify the expression of the Bhattacharyya constant as introduced previ-ously in the equation (2.20), then we can write:

56

Page 67: Phd dissertation

2.5. THE STABILITY ANALYSIS OF SPLIT-LDPC DENSITY EVOLUTION

r := − log(B(R Puo(x) + (1 −R)P0(x))

)(2.45)

In our case, the Bhattacharyya constant is associated to an equivalent channel which isthe combination of the channel described by P0 over which the non systematic coded bitsare sent, with a virtual channel characterized by Pu0 which contains the a priori informa-tion on the non uniformly distributed systematic bits.The former channel represents the initial message density received by the bitnodes

v, and the latter is the initial message density received by the bitnodes u combining thechannel with the splitter output. We denote the initial message distribution of the virtualequivalent channel as Peq = R Puo(x) + (1 −R)P0(x).Let us present the stability condition associated to the split-LDPC as a necessary con-

dition to the convergence to zero of the probability of error.

Theorem 8 (General Stability Condition for Split LDPC). .If B(R Puo(x) + (1−R)P0(x))λ

′(0) ρ′(1) > 1 then the probability of error under density evolu-tion is bounded away from zero.

Proof : If we assume that λ′(0) ρ′(1) > er where :

r := − limn→∞

1

nlogPrerr((R Puo + (1 −R)P0)

⊗n)

then there exist an integer n such that :

(λ′(0) ρ′(1))nPrerr((R Puo + (1 −R)P0)⊗n) > 1

In the following we will consider in a common way, the trees and the message densitiesassociated to the messages p2 and p3. Since both of those messages give similar expres-sions to the output message density under n iterations of density evolution, they sharethe same study of stability. Then, each time we will mention a message density or arandom tree, it would be associated to one of those two types cited above.Let density evolution be initialized with a consistent density P where Prerr(P ) = ε andlet Pn denotes the message distribution obtained after n iterations of density evolution.Let Pn denotes the message distribution obtained after n iterations with the initial mes-sage distribution set instead to Q0 = 2εδ0 + (1 − 2ε)δ∞.Let us consider a random tree of depth 2n + 1 with variable nodes at the leaves and avariable at the root. Let the leaf variable nodes have observations from a channel cor-responding to the initial message distribution Q and let the other variable nodes haveobservations from a channel corresponding to P0.Then, Pn and Pn are the message distributions out of the root node corresponding toQ = P and Q = Q0 respectively. Note that in both cases the estimate of the root nodemessage is a maximum likelihood (ML) estimate.Since any symmetric channel is a physical degraded version of an erasure channel, as itwas shown in in [67] and [73], one can think of the channel associated to P is physicallydegraded from the one associated to the densityQ0 (BEC). It then follows that :

Prerr(Pn) ≥ Prerr(Pn)

57

Page 68: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

From the computations given in the equations (2.39), we have shown that concerning themessage types p2 and p3 :

Prerr(Pn) ≈ 2ε(λ′(0)ρ′(1))n(R Puo + (1 −R)P0)⊗ n + (1 − 2ε(λ′(0)ρ′(1))n)δ∞ + (ε2)

For ε sufficiently small it follows that Prerr(Pn), and hence Prerr(Pn), exceeds 2ε.Since the probability of error associated to density evolution is non-increasing it followsthat the probability of error can never reach ε. �

In our study, we have only proven the necessity of the stated stability condition.Demonstrating the sufficiency is leaved as an open issue. We observe that, when thesource is uniformly distributed Pu0 = P0, then the split-LDPC stability condition be-comes the one associated to the embedded LDPC, described in theorem (7).Let us calculate the stability condition explicitly for various channels in the following

examples. First, let us evaluate the quantity (µ δ−s + (1 − µ) δs)⊗ ds to find it equals to:

(µ δ−s + (1 − µ) δs)⊗ ds =

ds∑

i=0

Cids

(1 − µ)i µds−i δ(2i−ds)s (2.46)

where δ(2i−ds) s = δ(x− (2i− ds) s) and s = log(

1−µµ

).

Example 4. For the BEC channel with an erasure probability εwe have P0(x) = εδ0 +(1−ε)δ∞and :

P0(x) ⊗ (µ δ−s + (1 − µ) δs)⊗ ds = ε

ds∑

i=0

Cids

(1 − µ)i µds−i δ(2i−ds)s + (1 − ε)δ∞ (2.47)

The equivalent channel initial message density is :

Peq(x) = (1−R)[εδ0 +(1− ε)δ∞]+R [ε

ds∑

i=0

Cids

(1−µ)i µds−i δ(2i−ds)s +(1− ε)δ∞] (2.48)

We have

e−r = 2

∫ ∞

0Peq(x)e

−x2 dx = ε[(1 −R) +R (2

√µ(1 − µ))ds]

Then we get stability condition for the BEC given by :

λ′(0) ρ′(1) <1

ε[(1 −R) +R (2√µ(1 − µ))ds]

(2.49)

We can prove that :1

ε<

1

ε[(1 −R) +R (2√µ(1 − µ))ds]

Thus, if the embedded LDPC realizes the stability condition λ′(0) ρ′(1) < 1ε , then the split-LDPC

realizes its associated stability condition. �

58

Page 69: Phd dissertation

2.5. THE STABILITY ANALYSIS OF SPLIT-LDPC DENSITY EVOLUTION

Example 5. For the BSC with an error probability transition λ we have:

P0(x) ⊗ (µ δ−s +(1−µ) δs)⊗ ds =

ds∑

i=0

Cids

(1−µ)i µds−i [λδ−L+(2i−ds)s +(1−λ)δL+(2i−ds)s]

(2.50)where L = log(1−λ

λ ). The equivalent channel initial message density is :

Peq(x) = (1−R)[λδ−L+(1−λ)δL]+R [

ds∑

i=0

Cids

(1−µ)i µds−i (λδ−L+(2i−ds)s+(1−λ)δL+(2i−ds)s)]

(2.51)We have :

e−r = 2

∫ ∞

0Peq(x)e

−x2 dx = 2

√λ(1 − λ)[(1 −R) +R(2

√µ(1 − µ))ds]

Then we get stability condition for the BSC given by :

λ′(0) ρ′(1) <1

2√λ(1 − λ) [(1 −R) +R (2

√µ(1 − µ))ds]

(2.52)

We can prove that :

1

2√λ(1 − λ)

<1

2√λ(1 − λ) [(1 −R) +R (2

√µ(1 − µ))ds]

Thus, if the embedded LDPC realizes the stability condition λ′(0) ρ′(1) < 1

2√

λ(1−λ), then the

split-LDPC realizes its associated stability condition . �

Example 6. For the BIAWGN channel with an error probability transition, where the initial

message density is P0(x) =√

σ2

8πe−

(x− 2σ2 )2σ2

8 , we have :

P0(x) ⊗ (µ δ−s + (1 − µ) δs)⊗ ds =

ds∑

i=0

Cids

(1 − µ)i µds−i P0(x− (2i − ds)s) (2.53)

The equivalent channel initial message density is :

Peq(x) = (1 −R)P0(x) +R [ds∑

i=0

Cids

(1 − µ)i µds−i P0(x− (2i − ds)s)] (2.54)

We have :

e−r = 2

∫ ∞

0Peq(x)e

−x2 dx = e−

12σ2 [(1 −R) +R(2

√µ(1 − µ))ds]

Then we get the stability condition for the BIAWGN channel given by :

λ′(0) ρ′(1) < e1

2σ21

[(1 −R) +R (2√µ(1 − µ))ds]

(2.55)

59

Page 70: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

We can prove that :

e1

2σ2 < e1

2σ21

[(1 −R) +R (2√µ(1 − µ))ds]

Thus, if the embedded LDPC realizes the stability condition λ′(0) ρ′(1) < e1

2σ2 , then the split-LDPC realizes its associated stability condition . �

In the previous examples, we have been able to prove that when close to zero errorrate, stability of the LDPC constituent is not perturbed by the splitter.Those examples are to support the more general case stated in the following result:

Lemma 2.5.1. When close to zero error rate, stability of the LDPC constituent is not disturbedby the splitter.

proof : We remind that :

Peq = (1 −R)P0(x) +R P0(x) ⊗ (µ δ−s + (1 − µ) δs)⊗ ds)

We find that :B(Peq) = B(P0) × (R+ (1 −R)L)

where L = (2 ∗√µ(1 − µ))ds is always smaller than or equals one since 0 < µ < 1, it

equals one if µ = 12 .

Consequently R+ (1 −R)L < 1 and :

B(Peq) < B(P0)

Hence if the LDPC constituent is stable over the channel with the initial density P0(x):

B(P0)λ′(0) ρ′(1) < 1

Then the Split LDPC constructed by the concatenation of a ds regular splitter with thisLDPC code would realize its associated stability condition where:

B(Peq)λ′(0) ρ′(1) < 1

Hence, we conclude that the splitter doesn’t disturb the stability of the LDPC. �

2.6 Simulations and Results

To demonstrate the proposed method for density evolution, the thresholds have beencomputed for ds = 3, λ(x) = 0.32660x + 0.11960x2 + 0.18393x3 + 0.36988x4, ρ(x) =0.78555x5 +0.21445x6 and source entropies varying from 0.1 up to 1. The discretized log-ratio interval was [−15 . . .+ 30], with a log-ratio quantization step that equaled to 0.0025.The thresholds that were obtained are plotted on Figure (2.7).The performance of this code is shown to be within a small distance from the theoret-

ical limit as long as the non-uniformity is not too extreme. For extreme non-uniformities,the gap to the theoretical limit increases. This performance is consistent with that ofnon-systematic turbo codes specifically designed for specific non-uniformities, as thosedescribed in [116].

60

Page 71: Phd dissertation

2.6. SIMULATIONS AND RESULTS

-12

-10

-8

-6

-4

-2

0

2

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Min

imum

Ach

ieva

ble

Eb/

N0

(dB

)

Source Entropy (bits)

lambda(x)=0.32660x+0.11960x^2+0.18393x^3+0.36988x^4

rho(x)=0.78555x^5+0.21445x^6

Systematic code, BPSK inputNon-Systematic code, BPSK input

Gaussian inputsplit-LDPC code, DE thresholds

Figure 2.7: Minimum achievable Eb/N0 versus source entropy Hs for a regular ds = 3splitter concatenated to an irregular LDPC code of rateR = 1/2 over a BIAWGN channel.

Density Evolution is also used as a probe for the design of good irregular LDPC codes,i.e, finding the convergence threshold of different irregular codes and choosing the bestone.Let us show the thresholds’ tables for regular and irregular constructions of split-

LDPC codes of rate one-half and Hs = 0.5 in the Tables (2.1), (2.2) and (2.3). We havechosen constituent LDPC codes among the distributions proposed in [73] and [75]. Thediscretized log-ratio interval was [−30 . . . + 30], with a quantization step of 0.005.We observe from the Tables (2.1) and (2.3) that the closeness of the asymptotical per-

formance to the Shannon limits, depends as well on the entropy as on the splitter degreeds. Let us remind with respect to the lemma (2.3.1) that the threshold of a split-LDPCcode is equal to the threshold of the embedded LDPC code in the uniform case whenentropy equals one.Let us consider the classification of codes based on their closeness to the Shannon

limits. The considered classification is to be change with the splitter degree (see Table.(2.1)). Hence we can deduce, that the behavior of the asymptotical performance is notlinear under ds variation. This fact, could be intuited, since the splitter degree has jointlyan impact on the graph connectivity and the source scrambling.We observe a kind of tradeoff in ds variations, since decreasing it would enhance the

graphical connectivity and increasing it would strengthen the scrambling quality of thesplitter. It is a determining factor for the the Split-LDPC performance.In contrast, we observe that under the entropy variation, the closeness to Shannon

limits is varying in a linear way for most regular constructions in Table. (2.2), where the

61

Page 72: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

classification of codes remains the same under the source statistics variation. Besides, theimpact ofHs variation becomes non linear with irregular constructions as we can observefrom the Table. (2.3).

Providing that, we figure out that the selection of the good splitting degree accordingwith a chosen core-LDPC construction for a given source entropy value is a complexoptimization problem.

Let us notice that both of the entropy and the splitter degree are involved in the pro-posed density evolution algorithm, and both should be considered during the search ofoptimized split-LDPC constructions.

We note in the Table. (2.3) that the split-LDPC asymptotical limits are improved usingirregular constituent LDPC codes. They are to be improved even more, with irregularsplitter constructions. This latter case is proposed as an open issue.

Finally, it must be recognized that when density evolution is used for the design of ir-regular constructions, it may be unattractive for requiring intensive computations and/ora long search since the optimization problem is not convex [75]. That is why, we haven’ttaken this way for the split-LDPC optimization. Instead we have preferred using lowcomplexity analysis tools as it will be detailed in the next chapter.

db dc ( Eb

N0)∗(dB) ∆threshold

3 6 −2.24 1.56

2 4 0.31 4.11

4 8 −1.15 2.65

5 10 −0.35 3.45

db dc ( Eb

N0)∗(dB) ∆threshold

3 6 −1.65 2.15

2 4 −0.97 2.83

4 8 −1.03 2.77

5 10 −0.61 3.19

Table 2.1: Threshold values for the BIAWGN under SCCD sum-product decoding forvarious regular split-LDPC of rate one-half and ds = 3 (left) ds = 5 (right) with entropyHs = 0.5 and Shannon limit ( Eb

N0)∗ = −3.8044dB

db dc ( Eb

N0)∗(dB) ∆threshold

3 6 1.14 0.95

2 4 3.25 3.06

4 8 1.59 1.40

5 10 2.06 1.87

db dc ( Eb

N0)∗(dB) ∆threshold

3 6 −0.62 1.36

2 4 1.52 3.50

4 8 0.15 2.13

5 10 0.78 2.76

Table 2.2: Threshold values for the BIAWGN under SCCD sum-product decoding forvarious regular split-LDPC of rate one-half and ds = 3 with entropy Hs = 1 (left) withShannon limit ( Eb

N0)∗ = 0.18706dB and entropy Hs = 0.7 (right) with Shannon limit

( Eb

N0)∗ = −1.9818dB

62

Page 73: Phd dissertation

2.7. CONCLUSIONS

dbmax 4 7 12

λ2 0.38354 0.31570 0.24426

λ3 0.04237 0.41672 0.25907

λ4 0.57409 0.01054

λ5 0.05510

λ6

λ7 0.43810

λ8 0.01455

λ9

λ10 0.01275

λ11

λ12 0.40373

ρ5 0.24123

ρ6 0.75877 0.43810

ρ7 0.56190 0.25475

ρ8 0.73438

ρ9 0.01087

( Eb

N0)∗(dB) −2.85 −2.23 −2.40

∆threshold 0.95 1.57 1.40

( Eb

N0)∗(dB)with Hs = 1 0.8085 0.5153 0.3727

Table 2.3: Threshold values for the BIAWGN under SCCD sum-product decoding forvarious irregular split-LDPC of rate one-half and ds = 3 with entropy Hs = 0.5 andthreshold ( Eb

N0)∗ = −3.8044dB

2.7 Conclusions

In this second chapter, we have performed an asymptotical analysis of split-LDPC sourcechannel controlled iterative decoding in presence of non uniform sources. For this pur-pose, we have extended the most complete analysis tool , namely the density evolution,to the split-LDPC case.First, we have derived a message type oriented density evolution algorithm for split-

LDPC construction, then we have used it in determining the asymptotical performanceof our codes. Simulation results have shown the good asymptotical performance of thesplit-LDPC codes and their capacity approaching quality.Moreover, in order to present a density evolution analysis suited to our considered

code construction, we have proved and extended the basic features, assumptions andresults of the general theory to our case.Then, we have proceeded with establishing a general stability analysis of the dynam-

ical system associated to the split -LDPC density evolution algorithm. This study hasrevealed that for ensuring the stability of the system for a considered channel condition,it is sufficient that the constituent core-LDPC realizes the the general stability condition.Finally, we have completed the stability analysis by deriving a general stability condi-

tion for the split-LDPC construction involving the source statistics as well as the splitter’sdegree. Our results are effective for all binary memoryless symmetric channels.

63

Page 74: Phd dissertation

2. DENSITY EVOLUTION ANALYSIS FOR SPLIT-LDPC CODES

In our study, we have proven the necessity of the stated stability condition. Demon-strating the sufficiency is leaved as an open issue.We also expect that extending our analysis to irregular splitters, would improve the

asymptotical limits of the Split-LDPC codes. This would be an interesting issue to ad-dress in a future work.

64

Page 75: Phd dissertation

Chapter 3

Exit Chart Analysis and Design ofIrregular Split-LDPC Codes

In order to circumvent density evolution complexity inconvenient, alternative lowcomplexity approaches are used for finding convergence behavior of iterative decoders.Most of those techniques are based on the Gaussian approximation and offer faster andmore insightful design processes. The most practical low complexity approach is the"EXIT Chart" analysis, for being more insightful in the iterative decoder behavior. More-over, it facilitates the design process of structures based on iterative processing.

In the present chapter, we address an EXIT chart analysis for the split LDPC codes.We adapt one of themost accurate variation of EXIT chart analysis to the split LDPC case,then proceed with a proposal for the design of good irregular non systematic structuresdedicated for encoding non uniform sources.

This chapter is presented as follows. We begin by introducing some preliminariesto the EXIT chart analysis for the LDPC codes. We pursue, with the description of atwo-dimensional EXIT chart analysis for the split-LDPC case, where the behavior of thesource controlled iterative decoder is investigated for regular and irregular structures.Finally, we address the problem of designing good irregular split-LDPC constructions,and achieve by presenting a number of examples to verify the capabilities of our method.

65

Page 76: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

3.1 Introduction

3.1.1 Motivation and Related Work

Owing to the intensive computations required by the density evolution algorithm; alter-native low complexity analysis approaches have been developed following the principleof tracking the evolution of a single parameter iteration by iteration, instead of trackingthe density of messages. The tracked parameter is selected as a measure of the decoder’ssuccess, and could be the statistic of the extrinsic messages based on their mean or vari-ance [21],the SNR of the extrinsic messages [29] , their error probability [7] or the mutualinformation between messages and decoded bits [92].Most of those approaches are based on a Gaussian Approximation (GA) justified by

Wiberg observation in [102], claiming that the probability density functions of the ex-trinsic output values approach Gaussian-like distributions with increasing number ofiterations. Using Gaussian approximation based on the consistency property, the anal-ysis of iterative decoders is converted from an infinite dimensional problem to a one-dimensional one. This simplification not only allows us to calculate the threshold quicklyand to understand the behavior of the iterative decoders better, but also makes it easierto design good irregular codes on graphs, reducing the related optimization problem toa linear program.Following these guidelines, major contributions to low-complexity analysis approaches

have been made at the beginning of the twenty first century. In 2000 Chung has usedthe Gaussian approximation to propose in [21] a one-dimensional density evolution forLDPC codes, where the mean of a Gaussian density acts as a faithful surrogate for themessage density. In the same year, Ten-Brink has pioneered a more general approachcalled extrinsic information transfer charts (EXIT Charts) analysis [93], [9], [95], includingLDPC codes, turbo codes and other constructions with more complicated constituentcodes [97], [47].The EXIT charts method uses extrinsic information transfer (EXIT) functions of con-

stituent decoders, in the iterative decoding scheme, that characterizes how a priori infor-mation at the soft decoder input converts into extrinsic information at the soft decoderoutput. The exchange of extrinsic information between constituent decoders can be vi-sualized as a decoding trajectory in an EXIT chart. EXIT charts provide a convenienttool for designing capacity-approaching iterative coding systems by matching the EXITfunctions of the constituent decoders based on the area property of the functions [9].In density-evolution-basedmethods, the analysis of later iterations is impossible with-

out first analyzing the early iterations. However, a Gaussian assumption allows us tostart from any stage of decoding. In addition to its lower computational complexity, EXITcharts techniques are reasonably accurate, which makes them attractive, despite not be-ing as accurate as density evolution. Moreover, this approach provides more insight inthe convergence behavior of the decoder, facilitate the design process of codes and is alsoused to analyze the behavior of a large number of iterative turbo techniques designedfor advanced communication systems (multi-input multi-output (MIMO) systems, mul-tiuser detection, turbo equalization) [38], [98], [91],[48],[41].Exit chart analysis allows prediction of iterative decoders behavior by solely looking

at the input/output relations of individual constituent decoders. The iterative decodingof LDPC codes can be seen as a series of elementary decodings of repetition and sin-gle parity- check constituent codes, which are considered as LDPC’s constituent codes.

66

Page 77: Phd dissertation

3.1. INTRODUCTION

Accordingly, the Exit chart analysis related to the LDPC code family is based on the Gaus-sian approximation of the extrinsic output distributions of each constituent code [47],[95].The corresponding EXIT functions were used to be determined by simulations, or usingan approximation based on a duality property of EXIT functions over the BEC.Ardakani et. al have shown in [6] and [7] that Gaussian approximation is less accurate

for messages sent from checknodes than for those emanating from variable nodes. It isonly accurate for checknodes of low degree at high SNR. This hinders analysis and designof very high rates (high checknode degree) and puts also a limit on themaximum variablenode degree.Hence,the authors have introduced in [7] a more accurate one-dimensional analysis,

where the Gaussian assumption is only done for the channel messages and the messagesemanating from variable nodes. By doing so, the authors circumvent also the approx-imation based on a duality property of EXIT functions over the binary erasure channel(BEC). While Ardakani et. al propose to evaluate EXIT functions by simulations, Sharonet. al in [84] have developed an analytical method for computing exact expressions in theform of a series expansion for the EXIT functions.In the present chapter, we propose to perform an EXIT chart analysis for the split

LDPC codes, following the method introduced by Ardakani in [6] for being one of themore accurate in the literature. By using the EXIT chart tool we aim to investigate thebehavior of the source controlled channel iterative decoding of split LDPC codes, andlooking for more insight through the resulting extrinsic transfer charts.In order to accomplish this purpose, the consideration of a message oriented EXIT

chart analysis seems to be the more appropriate approach, in a similar way to the densityevolution analysis. The EXIT chart analysis is able to be conformed to the split LDPCconstruction, since the consistency property is preserved under the source controlled it-erative decoding as we have shown in the previous chapter.However, the presence of three message types and three corresponding trees , makes

it difficult to convert the analysis problem to a one dimensional problem. In this respect,we suggest in the present chapter a dedicated approach, simplifying the problem by com-bining the message types. We propose a two-dimensional EXIT chart for the split-LDPCcodes, as an insightful tool for the analysis of the source controlled iterative decoder be-havior. A three dimensional EXIT chart has been already proposed by ten Brink in [94]with a different approach for turbo codes with three constituent codes.A parallel EXIT chart analysis for split-LDPC codes has been proposed independently

of our work by Xie et.al in [107]. Both works present common motivations and com-plementary results, to a large extent, while our proposal aims to bring more accuracyfollowing the guidelines of Ardakani approach introduced in [7].We conclude our work, by using the proposed two-dimensional EXIT chart approach

in the formulation of the linear program associated to the optimization problem of split-LDPC structures. Then, we propose practical algorithms dedicated to design good ca-pacity approaching split-LDPC codes.

3.1.2 Contributions

The main contributions of the author for this chapter are based on the results presentedat the Allerton Conference on Communication, Control, and Computing [4].

67

Page 78: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

The innovative contributions in this chapter are detailed in the following.First, we propose a two-dimensional EXIT chart analysis for split-LDPC codes, that

is keeping all the advantages of the one-dimensional EXIT chart analysis, namely, lowcomplexity, accuracy, and insightfulness in the convergence behavior. Moreover, the pro-posed approach enables us to compute the threshold of split-LDPC codes with a goodaccuracy.The formulation of the two-dimensional EXIT chart analysis, reveals the source con-

trolled iterative decoder as a bi-dimensional dynamical system and brings new interpre-tations and illustrations to the notions of convergence, fixed points and stability issues.Finally, within the framework of our proposal, we formulate the problem of designing

irregular split-LDPC codes as a linear program. We propose a practical approach to solvethis problem in order to obtain capacity achieving split-LDPC codes.The most important results are the following :

• We propose a two dimensional Exit chart analysis for the split-LDPC codes basedon the elimination of Gaussian assumption at the output of the checknodes , andthe use of the mutual information as a measure of approximation.

• We illustrate the source controlled iterative decoding process of split-LDPC codesas a bi-dimensional dynamical system through the EXIT charts formulation.

• We provide a graphical representation of charts that brings more insight to the pro-cess of convergence to fixed points, as well as to the stability issues of the associatediterative decoding system.

• We compute the threshold of split-LDPC codeswithin few thousandths of a decibel,at the cost of a lower complexity than density evolution approaches.

• We formulate the problem of designing irregular split-LDPC codes as a linear pro-gram.

• We propose practical approaches to solve the linear program and design capacityachieving split-LDPC codes.

3.2 Preliminaries on the EXIT Chart Analysis of LDPC Codes

In the present section, we describe an algorithm corresponding to the analysis of system-atic LDPC codes and based on EXIT charts. It is one of the most accurate of the literatureand has been introduced by Ardakani in [6]. The Figure (3.1) illustrates this algorithm.In all the following we consider an AWGN channel with BPSK modulation and noise

variance σ2n. The LLRmessage from the channel is Gaussianwithmean 2/σ2

n and variance4/σ2

n [93].Moreover, let us notice that the distribution of input LLR messages is consistent, fol-

lowing the fact that a Gaussian distribution with meanm and variance σ2 is consistent ifand only if σ2 = 2m. The related signal to noise ratio (SNR) is defined as m2

σ2 = 1σ2 This

fact makes the Gaussian distribution able to be described by a single parameter.We assume that the transmitter uses a systematic LDPC code and the receiver decodes

using the sum-product algorithm. Hence the consistency condition is preserved underthe decoding process.

68

Page 79: Phd dissertation

3.2. PRELIMINARIES ON THE EXIT CHART ANALYSIS OF LDPC CODES

Uin

Uin

Uout

U0

Uout

U0

f

f−1

Figure 3.1: EXIT charts Analysis General Principle.

3.2.1 The EXIT Charts Principle

One Iteration of LDPC decoding is viewed as a black box that, in each iteration, uses twosources of knowledge : the information from the channel (intrinsic information) and theinformation from the previous iteration (extrinsic information). Using these two sourcesof information, the decoder is processing a better knowledge about the transmitted code-word, using this knowledge as extrinsic information for the next iteration.In our setting, we study the input-output behavior of the decoder from the input of

the iteration (messages from variable nodes to checknodes) to the output of that iteration(messages from variable nodes to checknodes). Therefore, we consider the depth-onedecoding tree with variables nodes at the leaves and a variable node at the root as shownin Figure (3.1). The whole iteration is including the flow of messages from the leaves tothe root variable node, and the analysis includes the check and variable message updatestogether.Let us denoteU as somemeasure of knowledge about the transmitted codeword sym-

bols, e.g., SNR, probability of error, mutual information, and so on.An EXIT chart based on U is a curve with two axes: Uin and Uout, and a parameter U0

which expresses the information from the channel. Any point of this curve shows thatif the knowledge from the previous iteration is Uin, using it together with the channelparameter U0, the information at the output of this iteration is Uout. This curve, can beviewed as a function :

Uout = F (Uin) (3.1)

69

Page 80: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

0

0.05

0.1

0.15

0.2

0.25

-5 0 5 10 15

Extr

insic

Lo

g R

atio

PDF

iteration 9iteration 19iteration 29iteration 39iteration 49

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

-4 -2 0 2 4 6 8

Extr

insic

Lo

g R

atio

PDF

iteration 9iteration 19iteration 29iteration 39iteration 49

Figure 3.2: The evolution of densities at the bitnode output (left) and checknode out-put(right) for a regular (3, 6) LDPC at 1.18dB.

Where, U0 is taken as a fixed parameter, and F depends on the code and the decodingscheme as well. The EXIT chart is represented by plotting both F and F−1 on the samegraph, where the output from one iteration can transfer to the input of the next one. Eacharrow, corresponding to a transfer, represents one iteration of decoding.Hence, the number of required iterations for a target U as well as the threshold of con-

vergence, can be predicted using EXIT charts. While,convergence couldn’t occur whenthe tunnel between F and F−1 is closed, the threshold is defined as the worst channelcondition U0 for which the tunnel is open.Using this method, one can do the analysis for only a few (typically 20-40) points of

the EXIT chart and interpolate a curve on those points. Let us detail in the following,how the measure of knowledge U is obtained.

3.2.2 The Semi-Gaussian Approximation and the Related Metrics

In order to determine the measure of knowledgeU about the transmitted codeword sym-bols, we assume, in every iteration, that the input and the output messages, which areoutputs of variable nodes, are symmetric Gaussian. Then, we execute the following steps:

1. We start with Gaussian distributed messages at the input of the iteration

2. We compute the pdf of messages at the output using Monte-Carlo simulation or"one-step" density evolution.

3. We approximate the output pdf with a symmetric Gaussian.

The describedmethod is called the "semi-Gaussian", in contrastwith the "all-Gaussian"method that assumes all the messages to be Gaussian. It has been suggested in orderto circumvent the drawbacks involved by performing a Gaussian approximation at the

70

Page 81: Phd dissertation

3.2. PRELIMINARIES ON THE EXIT CHART ANALYSIS OF LDPC CODES

checknode output [7]. Only, the messages from variable nodes to checknodes are Gaus-sian approximated. The channel message is Gaussian distributed initially as it was dis-cussed above.Thanks to the consistency property, the Gaussian distribution can be described by

a single parameter, which makes the analysis one-dimensional. This parameter wouldrepresent U the measure of knowledge about the transmitted codeword symbols, repre-sented in the transfer charts. It could be the SNR, the error rate, the mean or variance ofthe Gaussian pdf, or the mutual information between a random variable representing atransmitted bit and another one representing an LLR message carried as a belief of thetransmitted bit.Notice that each parameter representing a measure of a symmetric Gaussian density

can be translated to another measure using the explicit relations they have with eachother. Any parameter of the approximating density can be used to represent that density,once the approximation is made.The Gaussian approximation could be based on different metrics. To approximate

a non Gaussian density with a symmetric Gaussian density one can compute one pa-rameter of the given density and find the symmetric Gaussian density that matches theparameter. For instance one may compute the mean of the non-Gaussian density and usethe symmetric Gaussian density with the same mean as an approximation.The mutual information between a random variable representing a transmitted bit

and another one representing an LLR message carried as a belief of the transmitted bit,the error rate, the variance and the SNR have also been used as Gaussian approximationmetrics. It has been shown that the choice of the approximating parameter makes a dif-ference in the accuracy of the one-dimensional analysis. The best measure is shown to bethe mutual information for both LDPC and turbo codes [6], [93].The Gaussian approximation based on mutual information requires a mapping func-

tion J (σ), which maps the noise deviation σ of a symmetric Gaussian density to its mu-tual information, and can be computed once and tabulated using the following expres-sion proved in [93] :

J (σ) = 1 −∫ +∞

−∞

e−(t−σ2/2)2/2σ2

√2πσ

log(1 + e−t) dt (3.2)

In our setting, the Gaussian approximation is based on the mutual information, andwe consider error rate as a measure of knowledge to Gaussian densities, and representthe charts in a Pin − Pout axis as in [47], [99], [7]. This is because the error rate is moreinsightful, and simplifies the design of irregular LDPC codes as will be discussed further.Let us remind that the error probability related to a consistant Gaussian density of

meanm and variance σ is written as :

Perr = Q(m

σ) = Q(

σ

2) (3.3)

where the function Q(x) denotes the error function and is defined as :

Q(x) =1√2π

∫ +∞

xe−

t2

2 dt (3.4)

71

Page 82: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

0.00

0.02

0.04

0.06

0.08

0.10

0.12

0.14

0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14

Pe(

out)

Pe(in)

db=02db=03db=04db=05db=10db=20db=30

y=x

Figure 3.3: Elementary GA charts with single Gaussian pdf input for different variabledegrees for a regular LDPC with dc = 6 on an AWGN at SNR = −2.0dB

3.2.3 Analysis of Regular Structures

We describe in the following how to find the EXIT chart of an iterative sum-productdecoder for a regular (db, dc) LDPC code.Let us define :

• U(f(x)) as the function which takes a pdf f(x) and returns its U measure.

• G(u) as the function which maps the measure U ∈ [Umin, Umax] to a Gaussian den-sity G.

• Ddc,dv(f(x), U0) as the mapping that takes an input pdf f(x) and channel condition

U0 and returns the output pdf after one iteration of density evolution.

Hence, we the analysis can be formulate as :

Uout = U(Ddc,dv(G(Uin), U0)) (3.5)

Using the equation (3.5) for a fixed U0, a point of Uin − Uout curve is achieved. Wecan repeat this for as many point as we wish and interpolate between points to form theEXIT chart related to the regular (db, dc) LDPC as it is shown in the Figure (3.3).

72

Page 83: Phd dissertation

3.2. PRELIMINARIES ON THE EXIT CHART ANALYSIS OF LDPC CODES

0.00

0.02

0.04

0.06

0.08

0.10

0.12

0.14

0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14

Pe(

out)

Pe(in)

db=02db=03db=04db=05

y=x

Figure 3.4: Elementary charts with Gaussian mixture input for the different variablenodes degrees for an irregular LDPC with ρ6 = 0.7855 ρ7 = 0.2145 and λ(x) =.3266x + .1196x2 + .1839x3 + .3698x4 on an AWGN channel at SNR=-2.0dB.

3.2.4 Analysis of Irregular Structures

We describe in the following how to find the EXIT chart of an iterative sum-product de-coder for an irregular LDPC code defined by its variable and check degree distributions(λ(x), ρ(x)). Let us define λ(x) =

∑λi x

i−1 where λi is the fraction of edges connectedto variable nodes of degree i, and ρ(x) =

∑ρj x

j−1 where ρj is the fraction of edges con-nected to checknodes of degree j. For a fixed check-degree distribution ρ(x), we considera depth-one tree associated to each variable degree, and we refer to it with ’degree i depthone tree’.While the pdf at the output of each degree i depth one tree is still approximated

with a symmetric Gaussian, the input of the same trees is approximated as a mixture ofsymmetric Gaussian densities weighted by the variable degree distribution λ(x).Let us define :

• U(f(x)) as the function which takes a pdf f(x) and returns its U measure

• Gλ(u) as the function which maps U ∈ [Umin, Umax] to a mixed Gaussian density Gλ

• Dρ,i(f(x), U0) as the mapping that takes an input pdf f(x) and channel conditionU0 and returns the output pdf after one iteration of density evolution on the depth-one tree associated to the fixed check-degree distribution ρ(x) and the variable nodedegree i.

Also we define Gλ as the following:

73

Page 84: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

Gλ =∑

i≥2

λi G(mi, 2mi) (3.6)

Where mi is the mean of messages at the output of a degree i variable node. We as-sume thatmi = m0 + (i− 1)mchk wheremchk is the mean of messages at the checknodesoutput andm0 the mean of intrinsic messages. For a fixed λ(x) the set of possible mixedsymmetric Gaussian densities at the input of the iteration is to be expressed by one pa-rameter mchk. Hence,any value of error probability Uin can be mapped to its equivalentmchk and equivalent mixed Gaussian input pdf Gλ(Uin).The analysis can be formulate as :

Uout,i = U(Dρ,i(Gλ(Uin), U0)) (3.7)

Using the equation (3.7) for a fixed U0, a point of Uin − Uout,i curve is achieved, asso-ciated to the variable node degree i. For some choices of U , Uout is able to be computedthrough the linear combination of Uout,i weighted by the variable-degree distributionλ(x):

Uout =∑

i≥2

λi Uout,i (3.8)

This can be done for error probability, mean and mutual information when the messageshave symmetric pdf. By computing Uout, one point of the EXIT chart of the irregular codeis computed. We can repeat this for as many point as we wish and interpolate betweenpoints to form the EXIT chart related to the irregular (λ(x), ρ(x)) LDPC code as it is shownin the Figure (3.4) and (3.5).

0.00

0.02

0.04

0.06

0.08

0.10

0.12

0.14

0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14

Pe(

out)

Pe(in)

Finverse of F

y=x

Figure 3.5: EXIT charts trajectory with Gaussian mixture input for an irregular LDPCwith ρ6 = 0.7855 ρ7 = 0.2145 and λ(x) = .3266x + .1196x2 + .1839x3 + .3698x4 on anAWGN channel at SNR=-2.0dB. (the tunnel is open).

74

Page 85: Phd dissertation

3.3. THE TWO DIMENSIONAL EXIT CHARTS ANALYSIS OF SPLIT-LDPC CODES

3.3 The Two Dimensional EXIT Charts Analysis of Split-LDPC

Codes

In this section, we describe how EXIT chart analysis can be performed on a split-LDPCcode with a nonuniform source in order to determine the code threshold under iterativedecoding on a binary input additive white Gaussian noise channel.The proposed EXIT chart is based on the principles detailed in the previous section

and takes into account the non uniformity of the source and the unique structure of thesplit-LDPC decoding graph. Consider a split-LDPC code built by the simple cascadeof a (η(x), ρα(x)) splitter and a (λ(x), ρ(x)) binary LDPC code. η(x) and ρα(x) denotethe edge distributions of the variable nodes and checknodes belonging to the subgraphconnecting the splitter’s checknodes α to the LDPC code systematic variable nodes u. Inthe regular splitter case η(x) = ρα(x) = xds−1.The multiedge structure of the split LDPC including three variable node types and

two checknode types , induces three types of messages going from bitnodes toward chec-knodes denoted P1, P2 and P3, then two types of messages flowing from checknodes to-ward variable nodes denoted Pα and Pβ . The local tree assumption is done over threetypes of trees as it has been detailed in the previous chapter (2). The messages prop-agating on graph edges are of LLR-type, and will be characterized by their probabilitydensity function (pmf in the implemented discretized version).Let us recall the notations related to the three tree types accordingly to the Figures

(3.6), (3.7) and (3.8) :

dc − 1

βα β

u

ds − 1

u u

α

12u + 1

ds − 1 db

12u + 1

η(x) xλ(x)

α

Pin2Pin1

Pout1 ≈ U (p1)

Figure 3.6: Tree representation for type-1 messages for rate R = 1/2 split-LDPC.

75

Page 86: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

dc − 1

βα β

u

ds − 1

u u

α

β

db − 1ds

12u + 1

2ϑ12u + 1

xη(x) λ(x)

P1

P 1out2 ≈ U (p2)

Pin2

Figure 3.7: Tree representation for type-2 messages for rate R = 1/2 split-LDPC.

ϑ

β

β

dc − 1

db − 1

12u + 1

2ϑ12u + 1

β βPin2

P 2out2 ≈ U (p3)

Figure 3.8: Tree representations for type-3 messages for rate R = 1/2 split-LDPC.

76

Page 87: Phd dissertation

3.3. THE TWO DIMENSIONAL EXIT CHARTS ANALYSIS OF SPLIT-LDPC CODES

• The probability distribution of LLR-messages going from u nodes to α nodes isp1(x). These are type-1 messages. A type-1 message includes ds − 1 incomingextrinsics from checknodes α and db incoming extrinsics from checknodes β.Thetree representation of type-1 messages is illustrated in Figure (3.6). Source nodes sare hidden inside α checknodes.

• The probability distribution of LLR-messages going from u nodes to β nodes isp2(x). These are type-2messages. A type-2message includes ds incoming extrinsicsfrom checknodes α and db − 1 incoming extrinsics from checknodes β. The treerepresentation of type-2 messages is illustrated in Figure (3.7).

• The probability distribution of LLR-messages going from ϑ nodes to β nodes isp3(x). These are type-3 messages. A type-3 message includes db − 1 incoming ex-trinsics from checknodes β. The tree representation of type-3messages is illustratedin Figure (3.8).

• The probability distribution of LLR-messages propagating from α checknodes to uvariable nodes is denoted pα(x). Finally, in a similar fashion, probability distribu-tion of messages generated by β is pβ(x).

• The source nodes s are considered as absorbed in the α nodes, hence they don’tappear in the tree . However their pmf is considered in the DE computation as asource probability mass ps(x) = δs = δ(x−s) located on the source a priori messagedenoted s = log

(1−µ

µ

).

The coexistence of three types of trees, describing the split LDPC structure, makes itdifficult to perform a one-dimensional EXIT chart analysis. Moreover, each message typeis correlated with the others.Thus, we propose to combine the message types p2(x) and p3(x) in order to create

a virtual message type p∗2(x) obtained by averaging p∗2(x) = (1 − R) p3(x) + R p2(x).

Besides, we introduce p∗1(x) = p1(x).We propose to follow the EXIT chart principle detailed in the previous section, for

each one-depth tree type, where the semi-Gaussian assumption is applied to the distri-butions p∗1(x) and p

∗2(x) at the input of each propagation tree, during the one step density

evolution process.For each propagation tree, the output distribution is approximated by a Gaussian

distribution with equal mutual information. We choose the error probability as measureof knowledge about the transmitted codeword. Let us denote Pi the error probabilityrelated to the pdf pi(x). The error probability related to the distribution p∗1(x) denotedP ∗

1 is extracted directly from the output distribution of the propagation tree of type -1.Thus, we can write P ∗

1 = P1. However, the error probability related to p∗2(x) denotedP ∗

2 is obtained by the linear combination of the error probabilities related to the outputdistributions emanating from the type -2 and 3 trees; those are P2 and P3 respectively.Thus, we can write P ∗

2 = (1 −R)P3 +R P2.The linear combination of the distributions p2(x) and p3(x) is reducing the problem to

a bi-dimensional analysis one, and is allowing to represent the split LDPC transfer chartsthrough two curves with three axes P ∗

1in,P∗2in, P

∗1out or P

∗2out, where :

77

Page 88: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

P ∗1out = F (P ∗

1in, P∗2in) (3.9)

P ∗2out = G(P ∗

1in, P∗2in) (3.10)

The system described in the equations (3.9) (3.10) defines a bi-dimensional dynamicalsystem. The global transfer functions F () and G() are linear combinations of elementaryfunctions denoted by fi,j() and gj().Where, the propagation tree of type-1messages with density p1(x) yields to :

F (x, y) =du∑

i=2

db∑

j=2

ηi λj fi,j+1(x, y) (3.11)

The elementary transfer function fi,j+1(, ) describes the mapping from R2 into R

which takes the input error probabilities P ∗1in and P

∗2in then returns the error probability

P ∗1out related to the distribution at the output of the depth one type-1 tree where the rootbitnode receives (i− 1) edges from the α checknode and j edges from the β checknode.Combining both propagation trees of type-2 and type-3 messages with density p2(x)

and p3(x) respectively, yields to :

G(x, y) = R×du∑

i=2

db∑

j=2

ηi λj fi+1,j(x, y) + (1 −R) ×db∑

j=2

λj gj(y) (3.12)

The elementary transfer function fi+1,j(, ) describes the mapping from R2 into R

which takes the input error probabilities P ∗1in and P

∗2in then returns the error probability

P2out related to the distribution at the output of the depth one type-2 tree where the rootbitnode receives i edges from the α checknode and (j − 1) edges from the β checknode.The elementary transfer function gj() describes the mapping from R into R which

takes the input error probability P ∗2in then returns the error probability P3out related to

the distribution at the output of the depth one type-3 tree where the root bitnode receives(j − 1) edges from the β checknode.In order to determine the elementary transfer functions fi,j() and gj() defining the

dynamical system in the equations (3.9) and (3.10), we propose the following process :

• We consider the input Gaussian distributions p∗1(x) and p∗2(x) associated to error

probabilities P ∗1in and P

∗2in, with or without mixtures .

• Given the input distributions, the output message distributions p1(x) , p2(x) andp3(x) are computed via a one-step discretized DE on each one-depth associatedtree.

• Each output distribution is approximated by a Gaussian distribution with equalmutual information.

• We extract the error probabilities P1out , P2out and P3out associated to each outputGaussian distribution. We deduce P ∗

1out and P∗2out following the linear combination

P ∗1out = P1out and P ∗

2out = (1 −R)P3out +R P2out.

• We display the trajectory of error probability P ∗1out(x) and P

∗2out(x) associated to a

given Gaussian distribution .

78

Page 89: Phd dissertation

3.3. THE TWO DIMENSIONAL EXIT CHARTS ANALYSIS OF SPLIT-LDPC CODES

3.3.1 Analysis of Regular Structures

Following the general approach proposed in the previous subsection, let us present ina more detailed manner, the formulation of EXIT chart analysis of an iterative sourcecontrolled sum-product decoder for a regular split LDPC code including a regular splitterof degree ds and a core regular (db, dc) LDPC code.In the regular case the equations (3.9) and (3.10) are reduced to the following :

P ∗1out = F (P ∗

1in, P∗2in) = fds,db+1(P

∗1in, P

∗2in) (3.13)

P ∗2out = G(P ∗

1in, P∗2in) = R × fds+1,db

(P ∗1in, P

∗2in) + (1 −R) × gdb

(P ∗2in) (3.14)

Hence, in the regular case, each elementary function associated to a one-depth tree typeis computed, assuming Gaussian input distributions and using the one-step density evo-lution. When the transfer functions F (, ) and G(, ) are plotted, allowing all values of P ∗

1in

and P ∗2in in the interval [Pmin, Pmax]2, we obtain a surface, which is looking like a carpet

as we can see in the Figure (3.9). The projection on the horizontal plane is a square sinceall values of P ∗

1in and P∗2in are allowed. Both surfaces associated to F (, ) and G(, ) are

supposed to bring the same information to the EXIT chart analysis. Consequently, wepropose to focus on the function F (, ) in our EXIT chart analysis.Using the equation (3.13) for a fixed P0, a point of (P ∗

1in, P∗2in, P

∗1out) curve is achieved

over the surface associated to the transfer chart F (, ). We can repeat this for as many pointas we wish and interpolate between points to form the EXIT chart related to the regular(ds, db, dc) split LDPC as it is shown in the Figure (3.10). In the case of convergence thecurve terminates at the point (0, 0, 0).We can perform the convergence analysis in a two-dimensional projection over the

plane y = 0, comparing the projected trajectory with the diagonal (0, 0) to (1, 1) . Inter-sections of the projection with the diagonal indicates that no convergence is possible.

0.000.020.040.060.080.100.120.140.160.18

0.000.05

0.100.15

0.200.05

0.10

0.15

0.20

0.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Transfer Function F(x,y)

Pin1

Pin2

Pout1

Figure 3.9: Transfer chart F (x, y) without mixtures. Illustration for ds = db = 3, dc = 6,Es

N0= −5.00dB. Input distributions are single Gaussian.EntropyHs = 0.5

79

Page 90: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

0.000.020.040.060.080.100.120.140.160.18

0.000.05

0.100.15

0.200.05

0.10

0.15

0.20

0.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Transfer Function F(x,y)Trajectory of Pout1

Pin1

Pin2

Pout1

Figure 3.10: Trajectory of error probability near the code threshold over the surface asso-ciated to the transfer chart F (x, y) without mixtures. Illustration for ds = db = 3, dc = 6,right to the threshold : Es

N0= −5.00dB. Input distributions are single Gaussian. Entropy

Hs = 0.5

0.000.020.040.060.080.100.120.140.160.18

0.00 0.05 0.10 0.15 0.20 0.050.100.150.200.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1Transfer Function F(x,y)

Trajectory of Pout1Inverse of Trajectory of Pout1

Plan z=x

Pin1Pin2

Pout1

Figure 3.11: Open tunnel obtained from the EXIT chart of the ds = db = 3, dc = 6 regularsplit-LDPC with at Es

N0= −5dB , Entropy Hs = 0.5. The tunnel is made by plotting the

trajectory of error probability and its z = x plane reflection

80

Page 91: Phd dissertation

3.3. THE TWO DIMENSIONAL EXIT CHARTS ANALYSIS OF SPLIT-LDPC CODES

Besides, we can also perform the convergence in the three dimensional space, by com-paring the error probability trajectory with the plane z = x, where the intersection withthe plane indicates that no convergence is possible. Otherwise the trajectory goes up tothe point (0, 0, 0) Similarly to the two-dimensional case, we can fix the required iterationsnumber for the convergence, using the tunnel defined by the error probability trajectoryand its z = x plane reflection as it is shown in the Figure (3.11).

3.3.2 Analysis of Irregular Structures

We describe in the following how to find the EXIT chart of an iterative source controlledsum-product decoder for regular and irregular split LDPC codes, assuming mixture ofGaussian distributions at the input of one-depth trees. Consider a split-LDPC code builtby the simple cascade of a (η(x), ρα(x)) splitter and a (λ(x), ρ(x)) binary LDPC code.For a fixed check-degree distributions ρ(x) and ρα(x), we consider a depth-one tree

associated to each variable degree, and we refer to it with ’degree i depth one tree’.In order to compute the transfer charts of the system,we consider the equations (3.11)

and (3.12). Let us describe in the following how to find fi,j(, ) and gj() in this case.While the pdf at the output of each degree i depth one tree is still approximated

with a symmetric Gaussian, the input of the same trees is approximated as a mixtureof symmetric Gaussian densities weighted by the variable degree distributions λ(x) andη(x).Let us define :

• m0: Mean of messages from the channel.

• mα: Mean of messages from the splitter checknodes α.

• mβ : Mean of messages from the LDPC checknodes β.

Also P ∗1in and P

∗1in are defined by the following system :

P ∗1in =

du∑

i=2

db∑

j=2

ηi λj1

2Q(

1

2

√m0 + (i− 1)mα + jmβ

)(3.15)

P ∗2in = R×

du∑

i=2

db∑

j=2

ηi λj1

2Q(

1

2

√m0 + imα + (j − 1)mβ

)(3.16)

+ (1 −R) ×db∑

j=2

λj1

2Q(

1

2

√m0 + (j − 1)mβ

)]

Accordingly, for a fixed (λ(x), η(x)) the set of possible mixed symmetric Gaussiandensities at the input of the iteration is to be expressed by the couple of parameter(mα,mβ). Hence,any couple of error probability values (P ∗

1in, P∗2in) can be mapped to

its equivalent couple of means (mα,mβ) , and then its equivalent mixed Gaussian inputdistributions.When mixtures are added to the input distributions, only a small part of the plane

defines admissible values for P ∗1in and P

∗2in. The carpet turns out to take the shape of a

sail, as it is illustrated in the Figures (3.12), (3.14).

81

Page 92: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

0.000.020.040.060.080.100.120.140.160.18

0.00

0.05

0.10

0.15

0.20

0.05

0.10

0.15

0.20

0.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Transfer Function F(x,y)

Pin1

Pin2

Pout1

Figure 3.12: Transfer chart F (x, y) with mixtures. Illustration for a (ds = 3, db = 3, dc =6) regular LDPC code at Es

N0= −5.00dB. Input distributions are Gaussian mixtures.

Channel initial point at top of the sail. Fixed point of zero error rate at bottom of thesail.EntropyHs = 0.5

0.000.020.040.060.080.100.120.140.160.18

0.000.05

0.100.15

0.20

0.050.10

0.150.20

0.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Carpet Transfer Function F(x,y)Sail Transfer Function with mixture F(x,y)

Trajectory of Pout1Trajectory with mixture of Pout1

Pin1Pin2

Pout1

Figure 3.13: Transfer chart F (x, y)with and without mixtures and associated error prob-ability trajectories. Illustration for a regular LDPC code at Es

N0= −5.00dB. Channel

initial point at top of the sail. Fixed point of zero error rate at bottom of the sail.EntropyHs = 0.5

82

Page 93: Phd dissertation

3.3. THE TWO DIMENSIONAL EXIT CHARTS ANALYSIS OF SPLIT-LDPC CODES

As in the regular case and for the same reasons, we focus on the analysis of the sur-face associated to the function F (, ). Using the equation (3.9) for a fixed P0, a point of(P ∗

1in, P∗2in, P

∗1out) curve is achieved over the surface associated to the transfer chart F (, ).

We can repeat this for as many point as we wish and interpolate between points to formthe EXIT chart related to the split LDPC code built by the simple cascade of a (η(x), ρα(x))splitter and a (λ(x), ρ(x)) binary LDPC code, as it is shown in the Figure (3.14).We can perform the convergence analysis in a two-dimensional projection over the

plane y = 0, comparing the projected trajectory with the diagonal (0, 0) to (1, 1). Inter-sections of the projection with the diagonal indicates that no convergence is possible.Besides, we can also perform the convergence in the three dimensional case, by com-

paring the error probability trajectory with the plane z = x, where the intersection withthe plane indicates that no convergence is possible. Otherwise the trajectory goes up tothe point (0, 0, 0). Similarly to the two-dimensional case, we can fix the required iterationsnumber for the convergence, using the tunnel defined by the error probability trajectoryand its z = x plane reflection as it is shown in the Figure (3.17).Let us notice that the mixture assumption is generic and can be made with the regular

split LDPC constructions as well as with the irregular ones. This is in contrast with thesystematic LDPC EXIT chart case. However, as it is shown in the Figure (3.13), the sailassociated to the (ds = 3, db = 3, dc = 6) regular split-LDPC code is included in thecarpet surface associated to the same code and built using the procedure detailed abovein the subsection (3.3.1). Moreover, the error probability trajectories obtained from thetwo approaches for a same split-LDPC code are superimposed as it is illustrated in theFigure (3.13).

0.00

0.05

0.10

0.15

0.20

0.00

0.05

0.10

0.15

0.20

0.050.10

0.150.20

0.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Transfer Function F(x,y)Trajectory of Pout1

Pin1

Pin2

Pout1

Figure 3.14: Trajectory of error probability near the code threshold. Illustration for anirregular split LDPC code with λ(x) = 0.3266x+0.1196x2 +0.18393x3 +0.36988x4, ρ(x) =0.78555x5 +0.21445x6 . Right to the threshold: Es

N0= −5.58dB, Threshold=−5.68dB. Final

fixed point is 0.EntropyHs = 0.5

Let us consider an irregular split-LDPC code of rate one-half, with a regular ds =

83

Page 94: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

0.00

0.05

0.10

0.15

0.20

0.00

0.05

0.10

0.15

0.20

0.050.10

0.150.20

0.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Transfer Function F(x,y)Trajectory of Pout1

Pin1

Pin2

Pout1

Figure 3.15: Trajectory of error probability near the code threshold. Illustration for anirregular split LDPC code with λ(x) = 0.3266x+0.1196x2 +0.18393x3 +0.36988x4, ρ(x) =0.78555x5 + 0.21445x6 . Left to the threshold: Es

N0= −5.78dB, Threshold=−5.68dB. Final

fixed point is non-zero.EntropyHs = 0.5

3 splitter, and an irregular embedded LDPC code with λ(x) = 0.3266x + 0.1196x2 +0.18393x3+0.36988x4, ρ(x) = 0.78555x5+0.21445x6 and a threshold ofEs/N0 = −5.68dB.Slightly above the threshold at Es/N0 = −5.58dB, we show in the Figure (3.14) the

trajectory of error rate is starting at P0 and going down the sail until (0, 0, 0). In fact, inthe case of convergence the curve terminates at the point (0, 0, 0), otherwise it remainstrapped by another non zero fixed point as it is the case in the Figure (3.15) where Es/N0

is just below the threshold.Slightly beyond the split LDPC threshold, we show two trajectories in the Figure

(3.16). The first one (the upper one) starts from an initial point inside the sail and goesupward and converges to a non-zero fixed point. The second trajectory (the lower one)starts from a point near (0, 0, 0) and goes down until (0, 0, 0). An unstable fixed pointis located in the center of the sail between the two trajectories, similar to the case of onedimensional analysis. However the point (0, 0, 0) is a stable fixed point.The discussed figures are a fair illustration of the behavior of the iterative decoding

process as a dynamical system as shown in previous studies [44], [109], [90], [66].

The Decoding Threshold Determination

For computation of the approximated threshold using an EXIT chart analysis, we need tovary the SNR and find the minimum value of SNR for which the EXIT chart is still open(3.17). This can effectively be done through a binary search. To find the exact threshold,we perform a similar binary search, however, for each SNR we use discretized densityevolution to verify convergence as shown in the Table (3.1).

84

Page 95: Phd dissertation

3.3. THE TWO DIMENSIONAL EXIT CHARTS ANALYSIS OF SPLIT-LDPC CODES

0.00

0.05

0.10

0.15

0.20

0.05

0.10

0.15

0.20

0.05

0.10

0.15

0.20

0.25

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Transfer Function F(x,y)First Trajectory

Second Trajectory

Pin1Pin2

Pout1

Figure 3.16: Stability of fixed points beyond the code threshold. Illustration for an irreg-ular split LDPC code with λ(x) = 0.3266x + 0.1196x2 + 0.18393x3 + 0.36988x4 , ρ(x) =0.78555x5 + 0.21445x6 . Left to the threshold: Es

N0= −5.78dB, Threshold=−5.68dB. Stable

and unstable fixed points.EntropyHs = 0.5

0.00

0.05

0.10

0.15

0.20

Pin1

Pin2

0.00

0.05

0.10

0.15

0.20

0.25

Pout1

Transfer Function F(x,y)Trajectory of Pout1

Inverse of the trajectory of Pout1plane z=x

0.00 0.05 0.10 0.15 0.20

0.050.10

0.150.20

0.25

Pout1

Figure 3.17: Open tunnel obtained from the EXIT chart of an irregular split-LDPC withλ(x) = 0.3266x + 0.1196x2 + 0.18393x3 + 0.36988x4 , ρ(x) = 0.78555x5 + 0.21445x6, atEs

N0= −5.58dB , EntropyHs = 0.5. The tunnel is made by plotting the trajectory of error

probability and its z = x plane reflection

85

Page 96: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

In the Table (3.1) we compare the EXIT chart threshold values with the density evo-lution ones. Both are computed with the same log-ratio quantization step of ∆ = 0.005,in a discretized log-ratio interval of [−30 . . . + 30]. We also precise just for indication,the density evolution threshold values computed with the log-ratio quantization step of0.0025. In all presented cases, we have used the mixture assumption..As expected from the theoretical motivations, the two dimensional EXIT chart thresh-

old evaluation is performed within a few thousands of a dB of the true value.This good accuracy is reached thanks to the semi-Gaussian assumption and the use

of mutual information as a measure of Gaussian approximation. The results are in agree-ment with those obtained in the original approach for systematic LDPC codes in [7].

Eb/N0∗ (dB) Eb/N0

∗ (dB) Eb/N0∗ (dB) Error∆Eb/N0

db dc Rate DE ∆ = 0.0025 DE ∆ = 0.005 EC∆ = 0.005 for∆ = 0.005

3 6 0.5 −2.24 −2.22 −2.199 0.020

4 8 0.5 −1.15 −1.12 −1.129 0.009

5 10 0.5 −0.35 −0.32 −0.369 0.049

Table 3.1: Error in approximation of threshold (dB) using EXIT chart analysis for variousregular split-LDPC codes of Rate one-half with ds = 3 and Hs = 0.5. ∆ is the log-ratioquantization step.

3.4 Design of Irregular Split LDPC codes

In the present section, we propose to use the EXIT chart analysis proposed in the previoussection in order to design capacity approaching irregular split-LDPC codes.In our study, we restrict ourself to split-LDPC codes, that are built by the concatena-

tion of an irregular (λ(x), ρ(x)) core-LDPC codewith a splitter defined by a knowndegreedistribution (η(x), ρα(x)). We focus on regular splitters where η(x) = ρα(x) = xds−1. Ourproposal, is able to be generalized to the irregular splitters case.The problem of designing an irregular code is reduced to the problem of shaping an

EXIT chart out of a group of elementary EXIT charts, for a fixed checknode distribution.Let us detail in the following how to proceed.

First, we aim to maximize the rate of the codeR = 1−∑ρj/j∑λi/i, while having the EXIT

chart of the irregular code satisfying the system of inequalities :

F (x, y) =du∑

i=2

db∑

j=2

ηi λj fi,j+1(x, y) < x (3.17)

G(x, y) = R×du∑

i=2

db∑

j=2

ηi λj fi+1,j(x, y) + (1 −R) ×db∑

j=2

λj gj(y) < y (3.18)

In our 2-D framework, the design problem is simplified to a linear program, in asimilar way to the 1-D framework in [7]. Hence, our design problem can be formulatedas the following linear program :

86

Page 97: Phd dissertation

3.4. DESIGN OF IRREGULAR SPLIT LDPC CODES

1. Maximize∑

i≥2 λi/i

2. subject to : λi ≥ 0,∑

i≥2 λi = 1

3. and ∀(P ∗1in, P

∗2in) ∈ T (S)

∑du

i=2 λj [

db∑

j=2

ηi fi,j+1(P∗1in, P2in∗)] < P ∗

1in (3.19)

∑db

j=2 λj [R ×du∑

i=2

ηi fi+1,j(P∗1in, P

∗2in) + (1 −R) × gj(P

∗2in)] < P ∗

2in (3.20)

Where T () is the mapping associating to a surface S (carpet or a sail), an ensemble ofcouples (P ∗

1in, P∗2in) defined by the coordinates (x, y) of the points drawing the projection

on the plane z = 0 of the error probability trajectory associated to a channel condition P0.As it has been discussed before, when the code is irregular the elementary EXIT func-

tions are computed assuming a mixture of Gaussian distributions at the input of the treesdescribed in the Figures (3.6), (3.7) and (3.8). However, prior to the design, the bitnodedegree distribution is not known. Therefore, a recursive approach is suggested to cir-cumvent this problem and solve the linear program formulated above. We suggest alsoto apply the linear program on the whole projected surface (carpet or sail) instead ofthe the error probability trajectory. This is because drawing the trajectory is sometimesdifficult, when a surface presents multiple fixed points for a channel condition P0.At first, we assume that the input message to the iteration, has a single symmetric

Gaussian density instead of a Gaussian mixture. Using this assumption, we can mapevery message error rate at the input of the iteration to a unique input pdf, then find theelementary functions associated to different degrees of bitnodes j for a fixed checknodedistribution ρ(x) and a known splitting degree ds . Finally, the elementary functions areused to solve the associated linear program described above, in order to obtain a bitnodedegree distribution λ(x).After finding the appropriate degree distribution based on single Gaussian assump-

tion, we use this degree distribution to find the correct elementary EXIT charts based ona Gaussian mixture assumption. Then, we use the corrected curves to design an irregularcode. In this level of design, the designed degree distribution is close to the used degreedistribution in finding the elementary EXIT charts. One can continue these recursions forhigher accuracy. Let us sum up the design process through the following algorithm:

1. Map every couple (P ∗1in, P

∗2in) to the associated symmetric Gaussian density.

2. Find the EXIT charts surfaces for different variable degrees.

3. Find a linear combination with an open EXIT chart that maximizes the rate andmeets all the required design criterion.

4. Use this degree sequence for mapping (P ∗1in, P

∗2in) to the appropriate input Gaus-

sian mixture densities.

5. Find the EXIT charts surfaces for different variable degrees.

6. Find a linear combination with an open EXIT chart that maximizes the rate andmeets all the required design criterion.

87

Page 98: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

We propose another approach merging the two step of the later algorithm in a uniqueone, as in the following :

1. Select a regular code with the desired coding rate.

2. Use the regular code degree sequence for mapping (P ∗1in, P

∗2in) to the appropriate

input Gaussian mixture densities.

3. Find the EXIT charts surfaces for different variable degrees.

4. Find a linear combination with an open EXIT chart that maximizes the rate andmeets all the required design criterion.

Empirically, the later approach is revealed to show better results with less complexitythan the first one. Accordingly, we have used this method based on an equivalent regularcode to design a number of irregular split-LDPC codes with a variety of rates.The results are presented in Table (3.2), and have been obtained with a log-ratio quan-

tization step of 0.0025, in a discretized log-ratio interval of [−30 . . . + 30]. We have maxi-mized the code rate for a given channel condition. In all our simulations, we have consid-ered regular check degree and use no variable degree greater than 50. Let us notice thatamong the advantages of the semi-Gaussian assumption, the fact that there is no limit onvariable node degree, and the design method works for a wide range of code rates [7].We expect even better asymptotical results using a splitter with irregular structure.

The case study of the irregular splitter and its optimization are left as open issues.

Degree Sequence code1 code2 code3 code4Rate 0.2183 0.4763 0.6374 0.7127

dv1, λdv1 2, 0.4510 2, 0.4027 2, 0.3509 2, 0.3263

dv2, λdv2 3, 0.1665 3, 0.1908 3, 0.2327 3, 0.1212

dv3, λdv3 5, 0.0594 4, 0.0704 4, 0.0001 4, 0.2576

dv4, λdv4 6, 0.1145 5, 0.0734 5, 0.1868 10, 0.0782

dv5, λdv5 26, 0.0802 6, 0.0038 6, 0.0013 11, 0.1056

dv6, λdv6 27, 0.1283 7, 0.0744 10, 0.0644 29, 0.0003

dv7, λdv7 8, 0.0019 11, 0.0694 30, 0.0027

dv8, λdv8 10, 0.0002 31, 0.0267 31, 0.0174

dv9, λdv9 12, 0.0002 32, 0.0673 32, 0.0276

dv10, λdv10 13, 0828 33, 0.0063

dv11, λdv11 14, 0.0114 34, 0.0004

dv12, λdv12 38, 0.0366 50, 0.0556

dv13, λdv13 39, 0.0513

dv14, λdv14 40, 0.0001

dc 4 6 9 12

Threshold ( Eb

N0)∗(dB) −3.51 −3.74 −3.12 −2.66

Gap to the Shannon limit 0.75 0.1 0.44 0.76

Table 3.2: Threshold values on the BIAWGN channel under SCCD sum-product decodingfor irregular split-LDPC codes with ds = 3 ,entropyHs = 0.5 and a variety of rates.

88

Page 99: Phd dissertation

3.5. CONCLUSIONS

3.5 Conclusions

In the present chapter, we have proposed amessage oriented two-dimensional EXIT chartanalysis for split-LDPC codes based on the semi-Gaussian assumption and using themutual information as a measure of approximation. The proposed approach enables usto compute the threshold of split-LDPC codes with a good accuracy, at the cost of a lowercomplexity than density evolution approaches.The elimination of Gaussian assumption at the output of the checknodes makes the

EXIT chart analysis predict the convergence threshold within a few thousandths of deci-bel from the actual threshold. Our approach inherits the advantages of the original one-dimensional analysis proposed in [7].The proposed two-dimensional EXIT chart formalism, has fairly illustrated the source

controlled sum-product iterative decoder as a two dimensional dynamical system. Inaddition the graphical representation of charts has brought more insight to the process ofconvergence to fixed points, as well as to the stability issues.Finally, within the framework of our proposal, we have used the two-dimensional

EXIT chart formalism to propose an algorithm dedicated to design capacity achievingirregular split-LDPC constructions for fixed source distribution and regular splitter con-struction. We have obtained irregular split-LDPC constructions, with a significantly re-duced gap to the Shannon limit.We believe, that the asymptotical performance are to be improved with the use of

irregular splitters. For so doing in a future work, one can extend the optimization algo-rithms proposed herein, to work recursively between the code and the splitter optimiza-tion.

89

Page 100: Phd dissertation

3. EXIT CHART ANALYSIS AND DESIGN OF IRREGULAR SPLIT-LDPC CODES

90

Page 101: Phd dissertation

Chapter 4

Enhancing Iterative Decoding via EMSource-Channel Estimation

In the previous chapters, we have assumed the perfect knowledge of the channelstate information (CSI) as well as the source state information (SSI) during the proba-bilistic source controlled iterative decoding. Indeed, both source and channel statisticalparameters are essential to achieve the full utilization of capacity achieving codes. Whenthey are unknown by the receiver an estimation module is mandatory.

In the present chapter, we propose to investigate the joint source-channel estimationand decoding problem. The proposed joint source-channel iterative estimation techniquerelies on the Expectation Maximization (EM) algorithm that is associated to the sourcecontrolled sum-product decoder.

The EM algorithm has already become a standard tool in the statistical repertoire.Using such iterative estimation technique allows the exchange of soft information be-tween the iterative decoding and the estimation module following the turbo principle.Hence the inference of source and channel parameters is performed jointly with the sum-product decoding.

We start by introducing the systemmodel and the associated notations . Then, we de-scribe the Expectation-Maximization algorithm as a recursive low complexity approachtoML estimation. Subsequently, we show how EM can be integrated into the decoding ofLDPC codes for both binary symmetric channel with erasures and the complex additivewhite Gaussian noise channel. Finally, we illustrate with some results the performance ofEM algorithm where no loss in error-rate is observed with respect to the perfect knowl-edge case.

91

Page 102: Phd dissertation

4. ENHANCING ITERATIVE DECODING VIA EM SOURCE-CHANNEL ESTIMATION

4.1 Introduction

4.1.1 Motivation and Related Work

The full utilization of systematic and non-systematic capacity achieving channel codesfor non-uniform sources requires at the decoder side getting :

• The knowledge of the source probability distribution .

• The knowledge of channel parameters.

When the decoder doesn’t have access to this knowledge an estimation module isrequired. MAP and ML estimation are two possible techniques to compute estimatesof a parameter. However in practical scenarios, especially in the presence of nuisanceparameters, direct access to the data necessary to estimate the parameters is impossible.Therefore, the likelihood function and the a posteriori distribution are often very diffi-cult to evaluate . Furthermore, the maximization is often next to impossible when theestimates are multi-dimensional, even through numerical methods .The estimation on factor graph may be also unattractive from an implementation-

complexity point of view. This is especially when the estimates are in the continuousdomain. Moreover, the associated factor graph are likely to contain many short cycles.These will degrade the sum-product performance and lead to unreliable estimates [103].These drawbacks are to be overcome with the use of the Expectation Maximization

(EM) algorithm [24],[59] which is an iterative estimation technique well suited to thesituations where the direct access to the data necessary to estimate the parameters is im-possible. The expectation maximization algorithm produces maximum-likelihood (ML)estimates of parameters when there is a many-to-one mapping from an underlying dis-tribution to the distribution governing the observation. In addition, the a posteriori prob-ability of successive EM estimates is proved to be non-decreasing.The EM algorithm consists of two major steps: an expectation step, followed by a

maximization step. The expectation is with respect to the unknown underlying variables,using the current estimate of the parameters and conditioned upon the observations. Themaximization step then provides a new estimate of the parameters. These two steps areiterated until convergence.The EM algorithm was discovered and employed independently by several different

researchers until 1977 when Dempster, Laird, and Rubin brought their ideas together,proved convergence, and coined the term "EM algorithm" [24]. The EM includes theBaum-Welch algorithm as a special case, see [57]. The Baum Welch algorithm has beendeveloped by Baum and Welch in the mid-sixties to estimate the parameters of hiddenMarkov models [13], [15] and [14]. One can apply the Baum-Welch algorithm to performbit MAP decoding of a convolutional code. This was first done by Bahl, Cocke, Jelinek,and Raviv [10] and the algorithm is now known as the BCJR algorithm.Accordingly the Baum-Welch algorithm has been used jointly with turbo decoding in

order to estimate hidden Markov chains in [36], then with LDPC codes over finite statebinary Markov channels in [35]. Besides, the authors of [2] noted that the sum-productcould be adapted to calculate one step of the Baum-Welch algorithm. Eckford has com-bined the sum-product algorithm with EM to perform a factor graph EM channel esti-mation for block fading channels in [27]. The cited contributions are among a large listof reference showing how EM algorithm and its variations are well suited to perform

92

Page 103: Phd dissertation

4.1. INTRODUCTION

jointly with probabilistic iterative decoding algorithms. Besides, the EM is of low com-plexity compared to the sum-product decoding algorithm that includes most of iterativedecoding algorithms.In our setting we consider redundant i.i.d memoryless source encoded by systematic

or non systematic low density parity check codes and transmitted over a noisy memory-less channel. The source state information (SSI) and the channel state information (CSI)are assumed unknown by the receiver. We propose the use of the Expectation Maximiza-tion (EM) algorithm in order to jointly estimate both of SSI and CSI. In this respect, weinvestigate wether using EM estimation the decoder is able in a blind mode to performas good as a perfect knowledge situation.We propose to derive EM estimation algorithms for the discrete binary symmetric

channel with erasures (BECBSC) and the continuous complex additive white Gaussiannoise channel (AWGN). The EM is known to be very sensitive to initialization [103].Therefore we consider in the presented simulations different techniques for the initial-ization.The most important related proposals considering source redundancy with non sys-

tematic iterative codes when the statistical parameters governing the sequence are un-known are [106], [105], [101], [60]. Besides, among the major contributions related to thesystematic iterative codes we cite [36], [61], [81]. Most of those studies have consideredthe extraction of statistical parameters of the source. In [18], channel-estimation using EMhas been considered in combination with a systematic turbo-decoding. In contrast withthose studies, our setting considers the joint estimation of source and channel governingstatistical parameters.With non systematic turbo codes the maximum utilization of a priori unknown statis-

tics requires modification of the decoding algorithm as well as a specific structure of theturbo codes [82], [106], [105]. Conversely, with non systematic LDPC codes, there is noneed tomodify the sum-product algorithm in order to integrate the estimation technique.Moreover, thanks to the general structure of the factor graph associated to the split LDPCcodes, our proposal is including both systematic and non systematic LDPC codes. Onlya scheduling is required to be defined in order to combine the interaction between thedecoder and the estimation module.

4.1.2 Contributions

The main contributions of the author for this chapter are based on the results reportedin the paper presented at the International Symposium on Communication Control andSignal Processing [19].The innovative contribution in this chapter are enumerated in the following.We derive a joint source-channel iterative estimation technique based on the Expec-

tation Maximization algorithm. We describe how the estimation technique can be in-tegrated into the non systematic decoder. We propose a scheduling for the interactionbetween the sum-product decoder and the EM estimation module. Where each iterationof the system includes one iteration of decoding and one iteration of estimation .Our approach includes systematic and non systematic LDPC codes, and could be

applied to any other block code decoded by the sum-product algorithm or one of its vari-ations as proposed in [77]. Our model is not restrictive to i.i.d. non-uniform sources, itsextension to stationary finite-memory source could be considered by the use of the Bur-rows Wheeler transform (BWT) to convert the source into a piecewise i.i.d. non-uniform

93

Page 104: Phd dissertation

4. ENHANCING ITERATIVE DECODING VIA EM SOURCE-CHANNEL ESTIMATION

source [28].Furthermore,within this proposed joint source-channel iterative estimation technique

no loss in error-rate performance is observed with respect to the perfect knowledge case,at the expense of a negligible complexity. Moreover, our simulations results confirm thestrong improvement in performance over the case in which source a priori informationis not considered.The most important results are the following :

• We propose a joint source-channel iterative estimation and decoding technique viaExpectation-Maximization. We describe how the estimation technique can be inte-grated into the non systematic source controlled iterative decoder.

• We propose a scheduling in the combination of soft information between the de-coder and the estimation module, in order to realize the turbo principle.

• Our proposal includes both systematic and non systematic LDPC codes and can beextended to any other block code decoded using the sum-product algorithm .

• We show the strong improvement in performance over the case in which source apriori information is not considered

• No loss in error-rate performance is observedwith respect to the perfect knowledgecase, for both systematic and non-systematic LDPC codes (split-LDPC) with non-uniform sources.

4.2 SystemModel and Notations

SSI

Source

EM Estimation

LDPC

Systematic LDPC

DecoderSink

CSI

Source

Universal Channel

Non Systematic

Channel

Uniform

θ = CSI + SSI

θ

Non Uniform

Figure 4.1: General Model of a coded communication system with EM estimation

94

Page 105: Phd dissertation

4.2. SYSTEM MODEL AND NOTATIONS

Let us describe the system model following the illustration given in the Figure (4.1).We consider a non-uniform binary independent identically distributed source. The sourcegenerates a binary sequence of length K denoted by s , (s1, s2, ..., sK) where si ∈{0, 1}.We assume that the source sequence is directly fed to a channel encoder withoutany data compression.Our study is restricted to channel encoding via systematic and non-systematic binary

LDPC codes of rate Rc = K/N . A BPSK modulated LDPC codeword has length N ≥ Kand is denoted by x , (x1, ..., xN ).The codeword x is transmitted over a noisy channel defined by its Channel State Infor-

mation (CSI) which is mandatory to the ldpc decoder, the received noisy vector being y.The LDPC decoder should retrieve s from y with prior knowledge of source and channelstatistics.

4.2.1 Source State Information

The binary i.i.d. source is characterized by the parameter µ = P (si = 1), where 0 < µ ≤12 . The source entropy is given by Hs = H2(µ), 0 < Hs ≤ 1, where H2(x) is the binaryentropy function. The source distribution, denoted by Source State Information (SSI), ismandatory for non-universal source decoding, furthermore it improves the performancesof the system if it is available for the channel decoderSimilarly to the systemmodel introduced in the first chapter, our setting is not restric-

tive. Instead of making a direct estimation of a stationary finite-memory source as in [36],it is possible to convert a finite-memory source into a piecewise i.i.d. non-uniform source[28]. The EM estimation described in the sequel can easily tackle with the piecewise vari-ation of the source.

4.2.2 Channel State Information

Two kinds of binary input symmetric output channels are considered: the binary sym-metric channel with erasures (BECBSC) and the complex binary input additive whiteGaussian noise channel (BIAWGN). The Characteristics and main parameters of bothchannels are summarized below.

The Binary Symmetric Channel with Erasures

The BECBSC channel has a binary input and a ternary output. The cross-over probabilityof its BSC part is λ and the erasure probability of its BEC part is ε. Channel observationsat the decoder input are derived from normalized likelihoods

obs(xi) =p(yi|xi)∑j p(yj|xj)

=

λ′ if yi = xi

1 − λ′ if yi = xi12 if yi = 1

2

(4.1)

where xi denotes the binary complement of xi, and λ′ =λ

1 − ε, where 0 ≤ λ < 1

2 and

0 ≤ ε < 1.The BEC and the BSC are special cases of the BECBSC with λ = 0 and ε = 0, respec-

tively.

95

Page 106: Phd dissertation

4. ENHANCING ITERATIVE DECODING VIA EM SOURCE-CHANNEL ESTIMATION

The Complex BIAWGN Channel

The BIAWGN channel is defined as

yi = Aeℑφxi + ηi with ℑ =√−1 (4.2)

where the three CSI parameters are :

• The amplitude A , which is real positive

• The phase ambiguity φ, which is uniformly distributed between 0 and 2π.

• The Gaussian noise variance σ2.

4.3 General Statement of the EM Algorithm

Channel Encoder

y: incomplete data (observed)x:missing data

yx

Source Channel

CSI

Channel Decoder Sink

01

set of parameters to be estimated, SSI+CSI

κ : complete data, κ = (x, y)

Θ

SSI = µ

0.9

p(s = 1) = µ0.1

Θ=SSI+CSI

Figure 4.2: General model for the EM source-channel estimation in a communicationsystem with non uniform source.

The general model is depicted on the Figure (4.2). The observation y is referred to asincomplete data and κ = (x,y) as complete data. When κ = (x,y) is available, maximum-likelihood estimation can be performed to determine SSI and CSI at the decoder side.In a coded communication system, the incomplete data y is the only available obser-

vation to the decoder. ML estimation of a parameter θ which includes both SSI and CSIis therefore obtained by maximizing the log-likelihood: θ = arg maxθ log p(y|θ). Unfor-tunately, analytical or numerical ML estimation by maximizing log p(y|θ) is not possiblebecause an explicit expression for the log-likelihood does not exist, or when maximiza-tion over θ is an extremely difficult task.The EM algorithm is then employed to compute an update θi+1, knowing that the

final estimate depends on the initial value θ0. As the symbol vector x is missing, thelog-likelihood function is replaced by the mathematical expectation over x, given theobserved data and the current parameter value. The algorithm proceeds in two steps[24][59] :

96

Page 107: Phd dissertation

4.4. EM APPLICATION TO BECBSC

• E-step: Compute the Auxiliary function Q:

Q = E [log p(x,y|θ)|y, θi]

=∑

x

log[P (y|x, θ)P (x|θ)]APPi(x) (4.3)

where E denotes mathematical expectation over x.

• M-step:θi+1 = arg max

θQ(θ|θi) (4.4)

The auxiliary function is a sum over the codewords of a product containing channelobservations (CSI), the source distribution (SSI), and a posteriori information provided bythe decoder from the previous iteration. Afterwards, the decoder exploits updated sourceand channel statistics provided by the estimation module to enhance its decisions.The SSI part in the auxiliary function is :

P (x|θ) ≡ P (s|θ) = µωH(s) (1 − µ)K−ωH(s) (4.5)

where ωH(s) denotes the Hamming weight of s.

4.4 EM application to BECBSC

Let us consider the binary symmetric channel with erasures as introduced in section (4.2).Let us denote :

• e as the channel error vector, of dimension N , such that e(i)=1, if there is an errorat the ith position of the received codeword.

• E as the channel erasure vector, of dimension N , such that E(i)=1 if there is anerasure at the ith position of the received codeword.

The channel observation is written as :

P (y|x, θ) = (λ)ωH(e) (1 − λ− ε)N−ωH(e)−ωH (E) εωH(E) (4.6)

4.4.1 Expectation step on BECBSC

We write the logarithm of the joint distribution function of parameters λ, ε and µ, bycombining (4.5) and (4.6). The conditional quantity P (x|y, θi) is equal to the codeworda posteriori probability at iteration i. After some algebraic manipulations, the auxiliaryfunction becomes

Q(θ|θi) = log[λ

1 − λ− ε]Ex[ωH(e)] + log[

ε

1 − λ− ε]Ex[ωH(E)]

+ log[µ

1 − µ]Ex[ωH(s)] +K log[(1 − µ)]

+N log[(1 − λ− ε)]

(4.7)

97

Page 108: Phd dissertation

4. ENHANCING ITERATIVE DECODING VIA EM SOURCE-CHANNEL ESTIMATION

where Ex[ ] = E [ ] denotes mathematical expectation over x.Now let us introduce soft symbols, soft errors, and soft erasures to further simplify

the expression (4.7).

Soft source symbols sj are identified in the following expectation expression:

E [ωH(s)] =

K∑

j=1

E [sj ] =

K∑

j=1

sj

The exact definitions of soft binary source symbols and soft binary code symbols are :

sj =∑

sj

sj × APPi(sj) = APPi(sj = 1) (4.8)

Let us introduce s such that s =∑K

j=1 sj .Similarly, xj = APPi(xj) and for errors and erasures we have

ej = E [(1 − 2 × yj)2(xj)

yj × (1 − xj)yj ]

= (1 − 2 × yj)2(xj)

yj × (1 − xj)yj

(4.9)

andEj = 4 × yj × (1 − yj) = Ej

Let us introduce e and E respectively such that e =∑N

j=1 ej and E =∑N

j=1 Ej .Finally, thanks to the above definitions of soft symbols, the auxiliary function becomes

Q(θ|θi) = log[λ

1 − λ− ε]e + log[

ε

1 − λ− ε]E

+ log[µ

1 − µ]s +N log[(1 − µ)(1 − λ− ε)]

(4.10)

4.4.2 Maximization step on BECBSC

Derive the auxiliary function with respect to µ, and find the source distribution updaterule

µi+1 =

∑Kj=1 sj

K(4.11)

Derive the auxiliary function with respect to λ to obtain the following second degreeequation

N.λ2 − (N +N∑

j=1

ej).λ+ (1 − ε)N∑

j=1

ej = 0

Let ∆ denote the discriminator of the previous equation. The update rule for the cross-over probability is then given by

λi+1 =N +

∑Nj=1 ej ±

√∆(εi)

2.N(4.12)

98

Page 109: Phd dissertation

4.5. EM APPLICATION TO AWGN

Derive the auxiliary function with respect to ε, then

N.ε2 − (N +

N∑

j=1

Ej).ε+ (1 − λ)

N∑

j=1

Ej = 0

In a similar way, the update rule for the channel erasure probability is

εi+1 =N +

∑Nj=1 Ej ±

√∆(λi)

2.N(4.13)

4.4.3 Two simple special cases, BEC and BSC

For a binary erasure channel without errors (BEC), the update rule for the erasure prob-ability reduces to :

εi+1 =

∑Nj=1 Ej

N(4.14)

Also, for a binary symmetric channel without erasures (BSC), the update rule for thecross-over probability reduces to :

λi+1 =

∑Nj=1 ej

N(4.15)

in agreement with the results given in [18].The Figure (4.3) illustrates the estimated source parameter versus the number of EM

iteration for a joint EM estimation and decoding for a non-uniform i.i.d. source over anerasure channel. The source parameter is µ = 0.1. The LDPC code is a systematic regular(3, 6)with rateRc = 1/2, and lengthN = 2000 bits. In all channel conditions, µ convergesrelatively fast to its exact value.

4.5 EM application to AWGN

In this section, we perform EM joint source-channel estimation to enhance decoding ofLDPC codes over a complex AWGN channel defined by (4.2). The EM equations relatedto the source are identical to the BECBSC case. The observation for a codeword at thedecoder input is

P (y|x, θ) =1

(2πσ2

)N exp(−∑N

j=1

∣∣yj −Aejφxj

∣∣2

2σ2

)(4.16)

4.5.1 Expectation step on AWGN

We Combine the equations (4.5) and (4.16), then after some algebraic manipulations, theresulting expression of the auxiliary function on AWGN channel is :

Q(θ|θi) = log[µ

1 − µ]s +K log[(1 − µ)] −N log[2πσ2]

− 1

2σ2

N∑

j=1

∣∣yj

∣∣2 − A2

2σ2

N∑

j=1

∣∣xj

∣∣2 +A

σ2

N∑

j=1

R{xj

∗e−ℑφyj

} (4.17)

99

Page 110: Phd dissertation

4. ENHANCING ITERATIVE DECODING VIA EM SOURCE-CHANNEL ESTIMATION

0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

0.40

0.45

0.50

0 2 4 6 8 10

Est

imat

ed S

ourc

e D

istr

ibut

ion

Expectation-Maximization Iteration

Channel Erasure Probability 0.65 (Bad)

Channel Erasure Probability 0.55 (Good)

Channel Erasure Probability 0.50 (Very Good)

Figure 4.3: Estimated source distribution µ versus EM iterations.

where soft complex symbols reduce to 2APPi(xj = 1) − 1 for BPSK alphabet. The nota-

tion∣∣xj

∣∣2 means that conditional expectation must be performed after taking the squaredmodule.

4.5.2 Maximization step on AWGN

We derive the auxiliary function with respect to µ to get the same EM update rule forthe source distribution as for BECBSC in (4.11). Then, we derive the auxiliary functionwith respect to the amplitude A, and evaluate high order moments with the product ofmarginals instead of the joint a posteriori probability, to get the amplitude update rule :

Ai+1 =

∑Nj=1 R

{xjy

∗j e

ℑφi}

∑Nj=1

∑xjAPPi(xj)

∣∣xj

∣∣2 =

∑Nj=1 R

{xjy

∗j e

ℑφi}

∑Nj=1

∣∣xj

∣∣2(4.18)

Finally, the EM update rule for noise variance and phase ambiguity are

σ2 (i+1) =1

2N

N∑

j=1

˜∣∣yj −Aieℑφixj

∣∣2

φi+1 = −Arg

N∑

j=1

xj y∗j

The above expressions for the AWGN channel are well-known in the literature in the caseof uncoded modulations and uniform sources.

100

Page 111: Phd dissertation

4.6. SIMULATIONS AND RESULTS

4.6 Simulations and Results

The Figure (4.4) depicts the bit erasure/error rate performance of a systematic regular(3, 6) LDPC code of length N = 2000 bits, over an erasure channel with and withoutsource a priori probability. The source parameter is µ = 0.1.In absence of source a priori,classical BEC decoders are non-probabilistic. Here we use a probabilistic decoder on theBEC in order to embed the EM algorithm. The EM estimation induces no loss. Capacitylimits are εmax = 0.5 in absence of EM estimation and εmax = 0.68 when estimating thesource distribution.

10-4

10-3

10-2

10-1

100

0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7

Bit

Era

sure

/Err

or R

ate

Channel Erasure Probability

Uniform sourcePerfect source apriori + Non uniform sourceEM estimated apriori + Non uniform source

Figure 4.4: Performance of a systematic (3,6) LDPC code on BEC using EM

The Figure (4.5) illustrates the word error rate performance on AWGN in four dif-ferent situations for N = 2000. A systematic regular (3,6)LDPC code is compared toa non-systematic split-LDPC code with a splitter degree ds = 3 [5]. The non-uniformsource has µ = 0.1. The AWGN channel has a uniformly distributed random phase and arandom amplitude in the range 0.1 . . . 10. A small fraction of 2% pilots is used to initilizethe channel parameters. As shown in Figure (4.5), the EM algorithm is able to attain theperformance of the perfect SSI and CSI knowledge scenario.

Two different schedulings are shown for EM estimation with the systematic (3,6)LDPC code. In the first one, the EM algorithm is considering the APP as soft information,in the second one it is using observations. Both curves are superimposed to the perfectknowledge case. Similar behavior is observed on BSC.

101

Page 112: Phd dissertation

4. ENHANCING ITERATIVE DECODING VIA EM SOURCE-CHANNEL ESTIMATION

10-4

10-3

10-2

10-1

100

-2.4 -2 -1.6 -1.2 -0.8 -0.4 0 0.4 0.8 1.2 1.6 2 2.4

Fra

me

Err

or R

ate

Eb/N0 (dB)

Systematic + UniformSystematic + Non Uniform (Perfect)

Systematic + Non Uniform (EM observation)Systematic + Non Uniform (EM APP)

Non Systematic + Non Uniform (Perfect)Non Systematic + Non Uniform (EM APP)

Figure 4.5: Performance of Systematic and non-systematic LDPC codes on the complexAWGN channel using EM, Rc = 1/2.

4.7 Conclusions

In the present chapter we have proposed a joint source-channel iterative estimation tech-nique based on the Expectation Maximization algorithm for unknown redundant i.i.dsource encoded by systematic or non systematic LDPC codes.The sum-product algorithm has been revealed well suited to incorporate the EM algo-

rithm as an estimation module. The proposed scheduling to the exchange of informationbetween the decoder and the estimation module emulating the turbo principle is suc-cessful since no loss in error-rate performance is observed with respect to the perfectknowledge case.Hence, we conclude that using EM estimation the decoder is able in a blind mode to

perform as good as a perfect knowledge situation at the expense of a negligible complex-ity compared to the sum product algorithm.EM is renown to be a very strong and robust algorithm, however it is known to be

very sensitive to initial conditions. Hence we have proposed the use of pilots, in the caseof complex AWGN channel.Our model includes both systematic and non systematic LDPC codes thanks to the

general structure of the split-LDPC factor graph. Our proposal could be extended to anyblock code decoded using the sum-product algorithm. It is also expected to work withsystematic turbo codes. However, with non systematic turbo codes more investigationsare required to find the EM scheduling the more convenient with the code construction.This is considered as an interesting open issue following our proposal. The extension ofour model to stationary finite-memory sources is another open issue.

102

Page 113: Phd dissertation

Chapter 5

Conclusions and Perspectives

State of the Art

In the following, the most important results of this thesis will be summarized and theirimpact on the advance of the knowledge currently available on this topic will be outlined.In the first chapter of the present thesis, we have introduced and studied a general

approach to design a novel non systematic LDPC codes family dedicated to encode nonredundant data and able to be decoded through an SCCD sum-product algorithm overthe associated factor graph. The proposed configurations are based on the concatenationof a pre-coding or a post-coding with an LDPC code. The precoding module consist in asparse matrix ’scrambler’ or the inverse of a sparse matrix ’splitter’ dedicated to transformthe redundant data bits into uniformly distributed coded bits .We have proved using information theoretical tools that within an SCCD decoding

strategy the asymptotical limits are moved to better regions. We have also shown the ad-vantage of non systematic constructions over systematic one’s in presence of non uniformsources in term of capacity. It has been revealed that this advantage is more significantwith high rate codes and highly biased sources. Simulation results support these theoret-ical demonstrations.MN codes family encoder has been identified as a specific configuration of the general

framework of non systematic LDPC codes. Besides, the proposed general decoding pro-cedure is giving an enhanced decoding alternative for the MN codes. Moreover, the nonsystematic LDPC general framework has been identified as a realization of a multiedgecascaded construction.The supremacy in term of performance of splitting structures over all other non sys-

tematic codes on graph constructions including prior MN codes have been demonstratedtheoretically. We have shown finite length simulation results supporting the theoreticaldemonstration.Motivated by the finite-length performance of splitting constructions shown in Chap-

ter (1) and the challenging fundamental limits of non systematic structures in presence ofredundancy, we have investigated in Chapters (2) and (3) the asymptotical analysis of thesplit LDPC source channel controlled iterative decoding to evaluate how close its asymp-totical performance is from the Shannon limit. For this purpose, we have developeddedicated analysis tools by conforming the classical analysis tools of the modern codingtheory to our case study, namely the Density evolution and the EXIT Chart techniques.Hence, in Chapter (2) we have started by deriving a message type oriented density

103

Page 114: Phd dissertation

5. CONCLUSIONS AND PERSPECTIVES

evolution algorithm for split LDPC construction, then we have used it in determiningthe asymptotical performance of our codes. Simulation results have shown the goodasymptotical performance of the split LDPC code, and its capacity approaching quality.Moreover, in the context of the density evolution analysis, we have proved and ex-

tended the basic features, assumptions and results of the general theory to our case. Then,we have proceededwith establishing a general stability analysis of the dynamical systemassociated to the split ldpc density evolution algorithm. Our study has revealed thatfor ensuring the stability of the system for a considered channel condition, it is suffi-cient that the constituent embedded LDPC realizes the the general stability condition.We have completed the stability analysis by deriving a general stability condition for thesplit LDPC construction involving the source statistics as well as the degree of the splitter.The derived condition as well as the analysis are effective for all memoryless symmetricchannels.Afterwards, we have addressed in Chapter (3) the study of an alternative low com-

plexity analysis approach that is the "EXIT Chart" analysis, for being more insightfulin the iterative decoder behavior. Moreover, it facilitates the design process of struc-tures based on iterative processing. Hence, we have proposed a message oriented two-dimensional EXIT chart analysis for split-LDPC codes based on the semi-Gaussian as-sumption and using the mutual information as a measure of approximation. The elim-ination of Gaussian assumption at the output of the checknodes makes the Exit Chartanalysis predict the convergence threshold within a few thousandths of decibel from theactual threshold.In the proposed two-dimensional EXIT Chart formalism, the source controlled sum-

product iterative decoder has been illustrated as a two dimensional dynamical system. Inaddition the graphical representation of charts have brought more insight to the processof convergence to fixed points, as well as to the stability issues.Within the framework of our proposal of Chapter (3), we have used the two dimen-

sional Exit Chart formalism to propose an algorithm dedicated to design capacity achiev-ing irregular split-LDPC constructions for a fixed source distribution and a regular split-ter construction. We have obtained irregular split-LDPC constructions, with a signifi-cantly reduced gap to the Shannon limit.While the results described above are in themselves important to the advance of the

knowledge currently available on capacity achieving codes for redundant data, anotheraspect of interest for this thesis has been themethods available for obtaining these results.Beyond the asymptotic analysis of the codes themselves, what is relevant for practical

applications is mainly their behavior when they are to be decoded in a blind mode whenthe knowledge of the source and and channel parameters is impossible .In this context, we have extended our communication setting, and have investigated

in Chapter (4) the joint decoding and the estimation of the source and channel parame-ters, using an iterative estimation technique based on the ExpectationMaximization (EM)algorithm.The sum-product algorithm has been revealed well suited to incorporate the EM algo-

rithm as an estimation module. The proposed scheduling to the exchange of informationbetween the decoder and the estimation module is successful since no loss in error-rateperformance is observed with respect to the perfect knowledge case. We conclude thatusing EM estimation the decoder is able in a blind mode to perform as good as a per-fect knowledge situation at the expense of a negligible complexity compared to the sumproduct algorithm.

104

Page 115: Phd dissertation

5. CONCLUSIONS AND PERSPECTIVES

Perspectives

The perspectives are two parts, technical and practical.

Technical Direction

Our study is opening issues for future work and developments considering alternativeassumptions :

• Studying more complex source models.The study has been made for i.i.d sequences with known statistics. Further studycan be done by the extension to more complex source models even if the statis-tics are unknown in advance. The extension can be made for the stationary finite-memory sources. One possible direction would be the use of the Burrows Wheelertransform (BWT) to convert the source into a piecewise i.i.d. non-uniform source.

• Extending the analysis and the optimization to non systematic LDPC includingirregular splitters or scramblers.

We believe, that the asymptotical performance are to be improved with the use ofirregular splitters. Therefore, the generalization of the analysis and design of Split-LDPC codes with irregular split-LDPC constitutes an interesting issue for a futurework. One possible direction would be to consider the splitter optimization jointlyto the constituent LDPC code for a fixed source entropy. For so doing, one canextend the optimization algorithms proposed in Chapter (4), to work recursivelybetween the code and the splitter optimization.

• Studying the non systematic LDPC codes for redundant data over more practicalchannels.

Extending the analysis and the optimization of the non systematic LDPC construc-tion over wireless fading channels (for instance) as it has been done already for nonsystematic Turbo codes in [112].

• Investigating the finite length and the complexity optimization of non systematicLDPC codes in presence of redundancy.

This can be done by extending to the non systematic LDPC case the general prin-ciples proposed for systematic LDPC codes for finite-length optimization [104], orcomplexity optimization [88],[8].

Moreover, the chapter (2) could be continued, with establishing the sufficiency proofof the stability theorem in the light of the demonstration accomplished in [71].Chapter (4) has considered both systematic and non systematic LDPC codes thanks

to the general structure of the split-LDPC factor graph. Our proposal can be extended toany block code or any other code on graph decoded using the sum-product algorithm.Furthermore, comparing the performance of the joint source channel system (non

uniform source+ non systematic LDPC code) with that of a tandem scheme for the sameoverall transmission rate, would highlight evenmore the advantage of the non systematic-LDPC codes under realistic constraints of real-world communication systems.

105

Page 116: Phd dissertation

5. CONCLUSIONS AND PERSPECTIVES

Practical Direction

The contributions of the present thesis address the study and the analysis of originalnon systematic LDPC codes constructions proposed to improve the error robustness ofexisting or emerging digital mobile communication systems like GSM (global system formobile communications) or UMTS (universal mobile telecommunications system), or thedigital audio/video broadcasting systems (DAB/DVB).In these systems the source coding part extracts characteristic parameters from the

original speech, audio, or video signal. Usually, these source codec parameters exhibitconsiderable natural residual redundancy such as a nonuniform parameter distributionor correlation. The encoding this residual redundancy with an appropriate well con-structed non systematic-LDPC code helps to cope with transmission errors.Besides, the non systematic LDPC codes can also find application in Network com-

munication (internet, broadcasting, streaming), in order to recover lost packets duringthe transmission.Therefore, a more practical study incorporating the split LDPC in practical digital

communication systems, is a challenging follow up to our work.

106

Page 117: Phd dissertation

Bibliography

[1] M. Adrat and P. Vary. Iterative Source-Channel Decoding: Improved System De-sign Using EXIT Charts. EURASIP Journal on Applied Signal Processing, 2005(6):928–941, 2005.

[2] S.M. Aji and R.J. McEliece. The generalized distributive law. IEEE Transactions onInformation Theory, 46(2):325–343, 2000.

[3] F.I. Alajaji, N.C. Phamdo, and T.E. Fuja. Channel codes that exploit the residualredundancy in CELP-encodedspeech. IEEE Transactions on Speech and Audio Pro-cessing, 4(5):325–336, 1996.

[4] A. Alloum, J.J. Boutros, G.I. Shamir, and L. Wang. Analysis of Belief Propagationfor Non-Systematic LDPC Codes with Redundant Data. Presentation at the 44thAllerton Conference on Communication , Control, and Computing, Monticello, Illinois,2005.

[5] A. Alloum, J.J. Boutros, G.I. Shamir, and L. Wang. Non-Systematic LDPC Codesvia Scrambling and Splitting. 43th Allerton Conference on Communication , Control,and Computing, Monticello, ILLinois,October, 2005.

[6] M. Ardakani. Efficient Analysis, Design and Decoding of Low-Density Parity-CheckCodes. PhD thesis, Department of Electrical and Computer Engineering, Universityof Toronto, 2004.

[7] M. Ardakani and F.R. Kschischang. A more accurate one-dimensional analysis anddesign of irregular LDPC codes. IEEE Transactions on Communications, 52(12):2106–2114, 2004.

[8] M. Ardakani, P. Zarrinkhat, and R. Yazdani. Complexity-Optimized Irregular De-coders. IEEE International Symposium on Information Theory, pages 2393–2397, 2006.

[9] A. Ashikhmin, G. Kramer, and S. Brink. Extrinsic information transfer functions:model and erasure channel properties. IEEE Transactions on Information Theory,50(11):2657–2673, 2004.

[10] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv. Optimal decoding of linear codes forminimizing symbol error rate . IEEE Transactions on Information Theory, 20(2):284–287, 1974.

[11] A. Banerjee, F. Vatta, B. Scanavino, and D.J. Costello Jr. Nonsystematic turbo codes.IEEE Transactions on Communications, 53(11):1841–1849, 2005.

107

Page 118: Phd dissertation

BIBLIOGRAPHY

[12] G. Battail. On Gallager’s low-density parity-check codes. IEEE International Sym-posium on Information Theory, 2000.

[13] L.E. Baum and T. Petrie. Statistical Inference for Probabilistic Functions of FiniteState Markov Chains. The Annals of Mathematical Statistics, 37(6):1554–1563, 1966.

[14] L.E. Baum, T. Petrie, G. Soules, andN.Weiss. AMaximization TechniqueOccurringin the Statistical Analysis of Probabilistic Functions of Markov Chains. The Annalsof Mathematical Statistics, 41(1):164–171, 1970.

[15] L.E. Baum and G.R. Sell. Growth transformations for functions on manifolds. Pa-cific J. Math, 27(2):211–227, 1968.

[16] C. Berrou and A. Glavieux. Near optimum error correcting coding and decoding:turbo-codes. IEEE Transactions on Communications, 44(10):1261–1271, 1996.

[17] C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correctingcoding and decoding: Turbo-codes. IEEE International Conference on Communica-tions. Technical Program, Conference Record, 2, 1993.

[18] J.J. Boutros. A tutorial on iterative probabilistic decoding and channel estimation:Graph representation, information flow and probabilistic algorithms in coding andcommunications. 2004.

[19] J.J. Boutros, A. Alloum, and G.I. Shamir. Enhanced channel decoding via EMsource-channel estimation. The second International Symposium on CommunicationControl and Signal Processing, Marrakech, 2005.

[20] G. Buch, F. Burkert, J. Hagenauer, and B. Kukla. To compress or not to compress?Global Telecommunications Conference, pages 198–203, 1996.

[21] S.Y. Chung. On the Construction of Some Capacity-Approaching Coding Schemes. PhDthesis, Massachusetts Institute of Technology, 2000.

[22] T.M. Cover and J.A. Thomas. Elements of Information Theory. John Wiley and Sons,1991.

[23] L. Decreusfond and G. Zémor. On the Error-Correcting Capabilities of Cycle Codesof Graphs. Combinatorics, Probability and Computing, 6(01):27–38, 1997.

[24] A.P Dempster, N.M Laird, and D.B Rubin. Maximum Likelihood from IncompleteData via the EM Algorithm. Journal of the Royal Statistical Society. Series B (Method-ological), 39(1):1–38, 1977.

[25] C. Di. Asymptotic and Finite-length Analysis of Low-density Parity-check Codes. PhDthesis, Ecole Polytechnique fédérale de Lausanne, 2004.

[26] C. Di, A. Montanari, and R. Urbanke. Weight distributions of LDPC code ensem-bles: combinatorics meets statistical physics. International Symposium on InformationTheory, ISIT 2004.

[27] A.W. Eckford. Channel estimation in block fading channels using the factor graphEM algorithm. The 22nd Biennial Symposium on Communications.

108

Page 119: Phd dissertation

BIBLIOGRAPHY

[28] M. Effros, K. Visweswariah, S.R. Kulkarni, and S. Verdú. Universal lossless sourcecoding with the Burrows Wheeler transform. Transactions on Information Theory,48(05):1061–1081, May 2002.

[29] H. El Gamal and A.R. Hammons. Analyzing the turbo decoder using the Gaussianapproximation. IEEE Transactions on Information Theory, 47(2):671–686, 2001.

[30] T. Etzion, A. Trachtenberg, and A. Vardy. Which codes have cycle-free Tannergraphs? IEEE Transactions on Information Theory, 45(6):2173–2181, 1999.

[31] GD Forney Jr. Codes on graphs: normal realizations. IEEE Transactions on Informa-tion Theory, 47(2):520–548, 2001.

[32] B.J. Frey andD.J.C. MacKay. A revolution: Belief propagation in graphswith cycles.Advances in Neural Information Processing Systems, 10:479–485, 1997.

[33] R. Gallager. Low-density parity-check codes. IEEE Transactions on Information The-ory, 8(1):21–28, 1962.

[34] RG Gallager. L.D.P.C. codes MIT Press. Cambridge, MA, 1963.

[35] J. Garcia-Frias. Decoding of low-density parity-check codes over finite-state binaryMarkov channels. IEEE Transactions on Communications, 52(11):1840–1843, 2004.

[36] J. Garcia-Frias and J.D. Villasenor. Joint Turbo Decoding and Estimation of HiddenMarkov Sources. IEEE Journal On Selected Areas In Communications, 19(9):1671, 2001.

[37] R.M. Gray andD.L. Neuhoff. Quantization. IEEE Transactions on Information Theory,44(6):2325–2383, 1998.

[38] J. Hagenauer. The exit chart: Introduction to extrinsic information transfer in iter-ative processing.

[39] J. Hagenauer. Source-controlled channel decoding. IEEE Transactions on Communi-cations, 43(9):2449–2457, 1995.

[40] J. Hagenauer, E. Offer, and L. Papke. Iterative decoding of binary block and con-volutional codes. IEEE Transactions on Information Theory, 42(2):429–445, 1996.

[41] C. Hermosilla and L. Szczecinski. Exit charts for turbo receivers in MIMO systems.The Seventh International Symposium on Signal Processing and Its Applications, 1, 2003.

[42] H. Jin, A. Khandekar, and R. McEliece. Irregular repeat-accumulate codes. The 2ndInternational Symposium on Turbo Codes and Related Topics, pages 1–8, 2000.

[43] I. Kanter and D. Saad. Error-Correcting Codes That Nearly Saturate Shannon’sBound. Physical Review Letters, 83(13):2660–2663, 1999.

[44] L. Kocarev, F. Lehmann, G.M. Maggio, B. Scanavino, Z. Tasev, and A. Vardy. Non-linear Dynamics of Iterative Decoding Systems: Analysis and Applications. IEEETransactions on Information Theory, 52(4):1366–1384, 2006.

[45] FR Kschischang and BJ Frey. Iterative decoding of compound codes by probabilitypropagation ingraphical models. IEEE Journal on Selected Areas in Communications.,16(2):219–230, 1998.

109

Page 120: Phd dissertation

BIBLIOGRAPHY

[46] F.R. Kschischang, B.J. Frey, and H.A. Loeliger. Factor graphs and the sum-productalgorithm. IEEE Transactions on Information Theory, 47(2):498–519, 2001.

[47] F. Lehmann and G.M. Maggio. Analysis of the iterative decoding of LDPC andproduct codes using the Gaussian approximation. IEEE Transactions on InformationTheory, 49(11):2993–3000, 2003.

[48] K. Li and X. Wang. EXIT chart analysis of turbo multiuser detection. IEEE Transac-tions on Wireless Communications, 4(1):300–311, 2005.

[49] M. Luby. LT codes. The 43rd Annual IEEE Symposium on Foundations of ComputerScience,, pages 271–280, 2002.

[50] M.G. Luby, M. Mitzenmacher, M.A. Shokrollahi, and D.A. Spielman. Improvedlow-density parity-check codes using irregular graphs. IEEE Transactions on Infor-mation Theory, 47(2):585–598, 2001.

[51] D.J.C MacKay. Good error-correcting codes based on very sparse matrices. IEEETransactions on Information Theory, 45(2):399–431, 1999.

[52] D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. CambridgeUniversity Pr., 2003.

[53] D.J.C. MacKay and R.M. Neal. Near Shannon limit performance of low densityparity check codes. Electronics Letters, 33(6):457–458, 1997.

[54] Y. Mao and A.H. Banihashemi. Decoding low-density parity-check codes withprobabilistic schedule. IEEE Pacific Rim Conference on Communications, Computersand signal Processing, 1, 2001.

[55] PC Massey and D.J. Costello Jr. Turbo codes with recursive nonsystematic quick-look-in constituentcodes. IEEE International Symposium on Information Theory, 2001.

[56] R.J. McEliece and D.J.C.J.F. Cheng. Turbo decoding as an instance of Pearl’s beliefpropagation algorithm. IEEE Journal on Selected Areas in Communications., 16(2):140–152, 1998.

[57] G.J. McLachlan and T. Krishnan. The EM algorithm and extensions. Wiley NewYork:,1997.

[58] C. McWilliams. Southern California country: an island on the land. Duell, Sloan &Pearce, New York, 1946.

[59] T.K Moon. The expectation-maximization algorithm. IEEE Signal Processing Maga-zine, 13(6):47–60, 1996.

[60] E. Ordentlich, G. Seroussi, S. Verdu, and K. Viswanathan. Universal algorithmsfor channel decoding of uncompressed sources. IEEE Transactions on InformationTheory, 54(5):2243–2262, May 2008.

[61] E. Ordentlich, G. Seroussi, S. Verdu, K. Viswanathan, M.J.Weinberger, and T.Weiss-man. Channel decoding of systematically encoded unknown redundant sources.International Symposium on Information Theory, 2004.

110

Page 121: Phd dissertation

BIBLIOGRAPHY

[62] A.V. Orlitsky and K.J. Zhang. Stopping set distribution of LDPC code ensembles.IEEE Transactions on Information Theory., 51(3):929–953, 2005.

[63] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.Morgan Kaufmann, 1988.

[64] R. Perkert, M. Kaindl, and T. Hindelang. Iterative source and channel decoding forGSM. IEEE International Conference on Acoustics, Speech, and Signal (ICASSP’01), 4,2001.

[65] Wu K.Y. Ping, L. Concatenated tree codes: a low-complexity, high-performanceapproach. IEEE Transactions on Information Theory, 47(2):791–799, 2001.

[66] T. Richardson. The geometry of turbo-decoding dynamics. IEEE Transactions onInformation Theory, 46(1):9–23, 2000.

[67] T. Richardson, A. Shokrollahi, and R. Urbanke. Design of provably good low-density parity check codes. IEEE Transactions on Information Theory, 47:619–637,2001.

[68] T. Richardson and R. Urbanke. An introduction to the analysis of iterative codingsystems. Codes, Systems, and Graphical Models, pages 1–37, 2001.

[69] T. Richardson and R. Urbanke. Multi-Edge Type LDPC Codes. Workshop honoringProf. Bob McEliece on his 60th birthday (but not included in the proceedings), CaliforniaInstitute of Technology, Pasadena, California, May, pages 24–25, 2002.

[70] T. Richardson and R. Urbanke. The renaissance of Gallager’s low-density parity-check codes. IEEE Communications Magazine, 41(8):126–131, 2003.

[71] T. Richardson and R. Urbanke. Fixed Points And Stability Of Density Evolution.Communications in Information and Systems, 4(1):103–116, 2004.

[72] T. Richardson and R. Urbanke. Modern coding theory. Draft of the book. 2004.

[73] T.J. Richardson, M.A. Shokrollahi, and R.L. Urbanke. Design of capacity-approaching irregular low-density parity-checkcodes. IEEE Transactions on Infor-mation Theory, 47(2):619–637, 2001.

[74] T.J. Richardson and R.L. Urbanke. Efficient encoding of low-density parity-checkcodes. IEEE Transactions on Information Theory., 47(2):638–656, 2001.

[75] T.J. Richardson and R.L. Urbanke. The capacity of low-density parity-checkcodes under message-passing decoding. IEEE Transactions on Information Theory,47(2):599–618, 2001.

[76] A. Schwartz and A. Weiss. Large Deviations for Performance Analysis. London, U.K.: Chapman and Hall, 1995.

[77] M. Schwartz and A. Vardy. On the stopping distance and the stopping redundancyof codes. International Symposium on Information Theory, pages 975–979, 2005.

[78] S. Shamai and S. Verdu. The empirical distribution of good codes. IEEE Transactionson Information Theory, 43(2):836–846, 1997.

111

Page 122: Phd dissertation

BIBLIOGRAPHY

[79] G.I. Shamir and J.J. Boutros. Non-systematic low-density parity-check codes fornonuniform sources. International Symposium on Information Theory, pages 1898–1902, 2005.

[80] G.I. Shamir, J.J. Boutros, A. Alloum, and L.Wang. Non-Systematic LDPC Codes forRedundant Data. Information Theory and Application Workshop, San Diego , California,February, pages 6–10, 2005.

[81] G.I. Shamir and L. Wang. Context decoding of low density parity check codes. The39th Annual Conference on Information Science and Systems,Proceeding of, John HopkinsUniversity, Maryland, March 2005.

[82] G.I. Shamir and K. Xie. Design of non-systematic turbo codes for universal sourcecontrolled channel decoding. IEEE Information Theory Workshop, pages 191–195,1929.

[83] CE Shannon. A mathematical theory of communication. ACM SIGMOBILE MobileComputing and Communications Review, 5(1):3–55, 1948.

[84] E. Sharon, A. Ashikhmin, and S. Litsyn. Analysis of Low-Density Parity-CheckCodes Based on EXIT Functions. IEEE Transactions on Communication, 54(8):1407,2006.

[85] A. Shokrollahi. Capacity-achieving sequences. Codes, Systems, and Graphical Models,(123):153–166.

[86] A. Shokrollahi. LDPC Codes: An Introduction. Digital Fountain, Technical Report,Apr, 2, 2003.

[87] A. Shokrollahi. Raptor codes. IEEE/ACM Transactions on Networking (TON),14:2551–2567, 2006.

[88] B. Smith, M. Ardakani, W. Yu, and F. Kschischang. Design of lowdensity parity-check codes with optimized complexity-rate tradeoff. IEEE Transactions on Informa-tion Theory, 2005.

[89] R. Tanner. A recursive approach to low complexity codes. IEEE Transactions onInformation Theory, 27(5):533–547, 1981.

[90] Z. Tasev, P. Popovski, G.M. Maggio, and L. Kocarev. Bifurcations and Chaos inTurbo Decoding Algorithms. Chaos and Bifurcation Control: Theory and Applications,2.

[91] S. ten Brink. Designing iterative decoding schemes with the extrinsic informationtransfer chart. AEU International Journal on Electronics and Communication, 54(6):389–398, 2000.

[92] S. ten Brink. Iterative decoding trajectories of parallel concatenated codes. The thirdIEEE/ITG Conference on Source and Channel Coding, pages 75–80, 2000.

[93] S. ten Brink. Convergence behavior of iteratively decoded parallel concatenatedcodes. IEEE Transactions on Communications, 49(10):1727–1737, 2001.

112

Page 123: Phd dissertation

BIBLIOGRAPHY

[94] S. ten Brink. Convergence of multidimensional iterative decoding schemes. Confer-ence Record of the Thirty-Fifth Asilomar Conference on Signals, Systems and Computers,1, 2001.

[95] S. ten Brink, G. Kramer, and A. Ashikhmin. Design of low-density parity-check codes for modulation and detection. IEEE Transactions on Communications,52(4):670–678, 2004.

[96] T. Tian, CR Jones, JD Villasenor, and RD Wesel. Selective avoidance of cycles in ir-regular LDPC code construction. IEEE Transactions on Communications, 52(8):1242–1247, 2004.

[97] M. Tuchler and J. Hagenauer. EXIT charts of irregular codes. Conference on Informa-tion Sciences and Systems, pages 748–753, 2002.

[98] M. Tuchler, R. Koetter, and AC Singer. Turbo equalization: principles and newresults. IEEE Transactions on Communications, 50(5):754–767, 2002.

[99] S. Vialle. Construction et analyse de nouvelles structures de codage de canal adaptées autraitement itératif. PhD thesis, Ecole Nationale Supérieure des Télécommunications,ENST Paris.

[100] C.C. Wang, S.R. Kulkarni, and H.V. Poor. Density evolution for asymmetric mem-oryless channels. IEEE Transactions on Information Theory., 51(12):4216–4236, 2005.

[101] L. Wang, G.I. Shamir, and J.J. Boutros. Universal Context Based Decoding withNon-systematic Low-Density Parity-Check Codes. The 41st Annual Conference onInformation Sciences and Systems., pages 469–473, 2007.

[102] N. Wiberg. Codes and decoding on general graphs. PhD thesis, Department of Electri-cal Engineering, Linköping University, 1996.

[103] H. Wymeersch. Software Radio Algorithms for Coded Transmission. PhD thesis, GhentUniversity, Gent, Belgium, 2005.

[104] H. Xiao andAHBanihashemi. Improved progressive-edge-growth (PEG) construc-tion of irregular LDPC codes. IEEE Global Telecommunications Conference, 1, 2004.

[105] K. Xie and G.I. Shamir. Source controlled channel decoding with nonsystematicturbo codes for iid sequences with unknown statistics. Proceedings of The 42nd An-nual Allerton Conference on Communication, Control, and Computing, pages 280–289,2004.

[106] K. Xie and G.I. Shamir. Context and denoising based decoding of non-systematicturbo codes for redundant data. International Symposium on Information Theory,pages 1280–1284, 2005.

[107] K. Xie, L. Wang, G.I. Shamir, and J.J. Boutros. EXIT Chart Analysis for Split-LDPCCodes. IEEE International Symposium on Information Theory, pages 567–571, 2006.

[108] W. Xu. Joint source-channel coding with a redundancy-matched binarymapping inGSM speech transmission. IEEE Global Telecommunications Conference., 1, 1998.

113

Page 124: Phd dissertation

BIBLIOGRAPHY

[109] X. Zheng, F.C.M. Lau, C.K. Tse, and S.C. Wong. Study of nonlinear dynamics ofLDPC decoders. European Conference on Circuit Theory and Design, 2, 2005.

[110] Y. Zhong, F. Alajaji, and L.L. Campbel. On the Joint Source-Channel Coding Er-ror Exponent for Discrete Memoryless Systems. ,IEEE Transactions on InformationTheory, 52(4):1450–1468, 2006.

[111] L. Zhou and Z.Y. Wu. Iterative source-channel decoding for GSM. Journal on Elec-tronics and Information Technology, 27(6):884–887, 2005.

[112] G.C. Zhu and F. Alajaji. Transmission of Non-Uniform Memoryless Sources overWireless Fading Channels via Non-Systematic Turbo Codes.

[113] G.C. Zhu and F. Alajaji. Design of Turbo codes for non-equiprobable memorylesssources. The 39th Allerton Conference on Communication , Control, and Computing,Monticello, Ilinois, 2001.

[114] G.C. Zhu and F. Alajaji. Turbo codes for nonuniform memoryless sources overnoisy channels. IEEE Communications Letters, 6(2):64–66, 2002.

[115] G.C. Zhu, F. Alajaji, J. Bajcsy, and P. Mitran. Non-Systematic Turbo Codes for Non-Uniform IID Sources over AWGN Channels. Conference on Information Sciences andSystems, 2002.

[116] G.C. Zhu, F. Alajaji, J. Bajcsy, and P. Mitran. Transmission of nonuniform memory-less sources via nonsystematic turbo codes. IEEE Transactions on Communications,52(8):1344–1354, 2004.

114