Lu?»

.u'

371d; uni-1503.!

.tl \
. 2.1... 1.. .
almandiflfa.

1 .
d

r

I) \ . ‘
u. ..os-.!r.fin . . .

.litlt

 

 

 

 

 

 

& UBRARY
200") Michigan State
uanCl ally

-—7rv.—__.—...-___

 

 

This is to certify that the
dissertation entitled

THE MAXIMUM-LIKELIHOOD DECODING ALGORITHMS OF
LOW-DENSITY CODES OVER BINARY ERASURE
CHANNELS

presented by

KI-MOON LEE

has been accepted towards fulfillment
of the requirements for the

PHD. degree in MATHEMATICS

 

 

Q;<;; / /2/

//Major Professor’s Signature

8/16 1/ 1007

Date

MSU is an affinnative-action, equal-opportunity employer

- _.-.-.-._.—.-.-.-_-.-._.-.-.-._.-,- -.-.-.-.-—.-.-.-.—A--—.—-.—A--.-._.—-—I—p-.-.—.-.-.—-—---.-.— _

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/07 p:/ClRC/DateDue.mdd-p.1

 

THE MAXIMUM-LIKELIHOOD DECODING
ALGORITHMS OF LOW-DENSITY CODES OVER
BINARY ERASURE CHANNELS

B y

KI—MOON LEE

A DISSERTATION

Submitted to
MICHIGAN STATE UNIVERSITY
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

DEPARTMENT OF MATHEMATICS

2007

ABSTRACT

THE MAXIMUM-LIKELIHOOD DECODING
ALGORITHMS OF LOW-DENSITY CODES OVER
BINARY ERASURE CHANNELS

By

KI-MOON LEE

We develop an advanced form of the Maximum Likelihood Decoding Algorithm
(MLDA) for Low-Density Parity—Check (LDPC) codes and Luby Transform (LT)
codes called the Separated MLDA (S—MLDA). We then present our design of LT
degree distributions by supplementing the Robust Soliton Distribution with small
fractions of dense rows that is optimized for the S-MLDA based decoding of LT
codes. Simulation results which show the viability of the proposed MLDA of LDPC
and LT codes are also presented. We also substantiate by extensive experimental
results that, under the S—MLDA, LT codes from an arranged encoder matrix can
achieve performance in stable overhead 7 for the successful S-MLDA Close to 0, while
the S—MLDA maintains the computational complexity in number of symbol additions

less than few tens of block lengths n.

To my parents, Si-Hyuk Lee and Kyung-Im Bong, to my wife Jin-Hee

Gil, and to my daughter Lynn

iii

ACKNOWLEDGMENTS

First of all, I take this opportunity to express my profound gratitude to my parents
Lee and Bong, my wife Jin-Hee Gil, and my younger brother Ki-Nam Lee for their
moral support and patience during my study in Michigan State University.

I would like to express my deepest sense of gratitude to my adviser Dr. Hayder
Radha for his patient guidance, encouragement and excellent advice throughout this
study. I have to say that, with the Markov Process I learned from his Random
Process class, I was able to establish and finalize the main theorems of this thesis,
particularly the design of LT degree—distributions by analyzing the MPA as a time-
and degree-varying l\'Ia.rkov Process on a random matrix H over F2.

I would like to express my gratitude to my co-adviser Dr. Jonathan I. Hall who
taught me Algebraic Coding Theory and Low—Density Codes over Binary Erasure
Channels. From his coding theory class and the independent study for Low-Density
codes, I was able to set up the essential problems in both developing decoding algo-
rithms for the S—MLDA and generalizing degree-distributions of Low-Density codes
for the RSD.

My sincere thanks to Dr. Nikolai Ivanov for his excellent teaching in both Corn-
binatorics and Graph Theory classes. I should say that all combinatorial arguments
in my thesis, particularly the rank—distribution theorems in chapter 2 related with
Kovalenko’s Rank Distribution Theorem, come from his Combinatorics and Graph
Theory class.

I am thankful to Dr. Ulrich hv‘leier‘frankenfeld for his excellent lectures in Algebra
I and II. I still remember the moment when he addressed the role of changing bases
and its matrix representations over Galois extension fields and modules. I should say
that the essential part of the algorithm design for the S-MLDA and the MPA in the

thesis was contributed by the basis changes and their matrix representations.

I am thankful to Dr. Gerald D. Ludden for being my committee member and his
recon'imendation for teaching reference.

I also express my special thanks to my friends in Korea, Hyung—Seok No, Young-
Sam Lee, and Young—Seok Hong for their friendships and financial support during my
PhD. in l\-Iichigan State University.

Finally, I acknowledge my gratitude to my colleagues Kiran Misra and Shirish
Karandes, and Dr. VVook—Joong Kim from ETRI Korea for their fruitful collaboration

and valuable advises in the research and software design.

TABLE OF CONTENTS

LIST OF FIGURES ............................. v11
LIST OF ALGORITHMS ......................... v111
LIST OF TABLES .............................. 1x
1 Introduction ................................ 1
1.1 Overview of the Thesis ..........................
1.2 Gaussian Elimination on a Linear System over F2 ........... 11
1.3 Low-Density Parity—Check Codes .................... 20
1.3.1 Encoding and Decoding Algorithm of LDPC Codes ...... 20
1.3.2 Probability Density Evolutions on Degree Ensembles ..... 26
1.4 Luby Transform Codes over BEC .................... 30
1.4.1 Encoding and Decoding Algorithms of LT codes ........ 31
1.4.2 The Robust Soliton Degree Distribution ............ 33
2 The Maximum-Likelihood Decoding Algorithms of LT Codes . . 39
2.1 Introduction and Backgrounds ...................... 39
2.2 The. Separated MLDA .......................... 45
2.3 Computational Complexities of the MLDA ............... 50
2.4 Degree Distribution Design with Dense Rows .............. 52
2.5 The Rank Distributions of [:1 ...................... 58
2.6 Simulation Results ............................ 63
2.7 LT Codes of Short. Block Lengths From an Arranged Encoder Matrix 70
2.8 Conclusions ................................ 78
3 The Maximum-Likelihood Decoding Algorithms of LDPC Codes 79
3.1 Introduction and Backgrounds ...................... 79
3.2 The S-MLDA Design with LDPC Codes ................ 83
3.3 The Complexity of the MLDA ...................... 90
3.4 Simulations ................................ 93
3.5 Conclusions ................................ 99
INDEX .................................... 100
BIBLIOGRAPHY .............................. 102

vi

2.3

2.4
2.5
2.6

2.7
2.8

2.9
2.10

3.1

3.2

3.3
3.4

LIST OF FIGURES

Date Transn’iission over Binary Erasure Channels ........... 3
The MLDA on H ............................. 41
Perforn'rances of LT Codes in Decoding Failure Rates (DFR) (under the

S-MLDA (black curves 1) and the MPA (gray curves 2). The codes
are generated by the p(;t') in Table 2.1 over the block lengths from

n. = 1, 000 to 10.000 ........................... 65
Number of Symbol Additions by the Post-Decoding and the MLDA in

[3] ..................................... 66
Fraction of References .......................... 68

The Rank-Deficiency 77 = dim(Ker(H)) (or the Number of Free Variables) 69
Rank Deficiency (top figure) and DFR (bottom figure) of LT codes of
n : 5. 000, generated by [)(J') and pplupg ............... 7O
Performances in Decoding Error Rates under the S-MLDA and the MPA 74
Number of Symbol Additions made by the post-decoding and the orig-

inal MLDA based on the encoding scheme E1 ............. 75
Fraction of References based on the Encoding Scheme E1 ....... 76
Number of Free Variables based on the Encoding Scheme E1 ..... 77

Decoding Failure Rate of LDPC codes under the S—MLDA (black
curves) and the MPA (gray curves) for block lengths 2,000 S n. 3 20,000 94
Number of Symbol Additions made by the Post-Decoding and the orig-

inal MLDA ................................ 96
Number of References ........................... 97
Number of Free \I’ariables by the S—MLDA ............... 98

vii

1.1
1.2
1.3
1.4
1.5
3.1
3.2
3.3
3.4
3.5
3.6

LIST OF ALGORITHMS

The LU—factorization on H ........................ 16
Recovery of a by the column-wise FS and BS .............. 18
Recovery of (r by the row-wise F S and BS ................ 19
The Message Passing Algorithm on It! .................. 24
The recovery of QXR by the FS in Algorithm 1.3 ........... 25
The ALTA on AI .............................. 84
The BSR. on MR by m2, SW - MR ................... 86
The GE on [FIR with T and R ...................... 87
The computation of UTILTISU“) - QT .................. 89
The recovery of X72 by FFS ....................... 90
The overall S-MLDA ........................... 90

viii

2.1

LIST OF TABLES

The row-degree distribution [)(I)

CHAPTER 1

Introduction

In the advent of the Internet, data transmission over the (TCP/IP based) Internet
becomes a part of our daily lives. Over the Internet, data transmission between a
sender and a receiver is accomplished in a form of packet transmission in the following
manner. For a given packet, a sender transmits the packet repeatedly until a receiver
acknowledges the arrival of the packet. In this transmission scheme, there is no
“decoding success/failure”, because every lost packet is retransmitted by a sender
till a receiver acquires the packet. Therefore, this retransmission scheme is 100%
reliable. This acknowlgement (ACK) based retransmission scheme, however, feasibly
causes heavy network congestion, that could lead to explosively many retransmission
requests if a large number of dropped (or lost) packets occur. This is particularly
true for multicast services where ACK-based communication is virtually impossible
to support (see [5,6,10,11,14] and references therein).

Let us now consider the following data transmission scheme. For a given binary
information data set I, a sender subdividcs it into k packets first. It then transforms
the k packets into n packets with n > k, and transmits packets till a receiver provides
a feedback message that informs the sender to stop the transmission. A receiver then
recovers the original It packets with randomly received (1 + e)k packets (out of n
possible packets) for some 6 > 0. If there exists an efficient way for the recovery of

the original 7: packets from the (1 + c)k received packets, particularly with 6 close to

0, then this transmission scheme may reduce the number of retransmission requests
significantly.

Then the question is how to recover the n packets. Many advanced solutions have
been developed to optimally address this question. This includes the Forward Error
Correction (F EC) schemes that is based on Reed-Solomon codes as proposed by Rizzo
et al. in [10.11] and the FEC scheme based on LT and Raptor codes proposed by

Digital Fountain co. [2,5,6].

1.1 Overview of the Thesis

In this thesis. rather than using polynomial based coding techniques such as the Reed-
Solomon codes in [10,11], we approach the above issue using linear algebra on vector
spaces over F2. \Ve will define several terminologies shortly. We then continue the
issue of transformations that take place at the sender and the receiver. Let a] be
a representation of a given data. set I that consists of [6 packets of equal size 3, i.e.,
o] = (all, . . . ,0]. . . . , 0%.), where (ti 6 F3 for ‘1? = 1,... ,Ir. Let us call a packet a; as a
symbol. Let (r 6 (F3)” be the transformed vector from a]. \Ve refer to the transformer
and a] as the encoder and the in formation symbol vector, respectively, and we call
the a as the codeword. Now let Z denote a received symbol vector that consists of
m. received symbols with m > lx‘. at the receiver side. Suppose a can be recovered
from Z by a certain (inverse) transformer of the encoder. we call a transformer of
the receiver as a decoder. In the remainder of the thesis, we assume that a received
vector Z is always a sul')-‘vector of a codeword a. If a symbol 0:,- is not arrived at the
receiver, we refer to the symbol as an erasure. Considering that a symbol is a binary
vector in F3, we call the overall routes (or paths) between a sender and a receiver a
Binary Erasure Channel (BEC). This data transmission scheme can be depicted as
the diagram in Figure 1.1.

Let us now consider two types of encoding methods that use linear transformations

 

 

A sender A Receiver

Packet Loss
Encoder(a1) = a —* BEC m I—* Decoder(Z) = a

 

 

 

 

 

 

 

 

 

Figure 1.1. Date Transmission over Binary Erasure Channels

over F2. By doing so, we turn the task of a decoder into a problem of solving a
consistent linear system over F3. The first type is as follows. At the encoder side,
we first. fix k, the number of symbols of a], so that any given information data set I
is represented as a symbol vector 0 I in (F 3),” . We then transform a] into a longer

symbol vector (1 : (01, . . . ,an) in the kernel space
Ker(H) : {v e (11‘3“)an - VT = 0}, (1.1.1)

where H is an m X 72 matrix over F2 with Rank(H) = m, m : n — k, and VT
is the symbol-wise transpose of V. Let G = [Smxkilmxm] be row—equivalnet to
H which is obtainable by Gaussian Elimination (GE) on H. Let us now consider
En(G) = [ I’M,“ ], the n X k induced matrix from G. Then for any a] E (173),“, a]

mxk

is transformed to a kernel vector a such that.

OT 2 E11(G)a?=(a1,ap)T, (131;: Sumkcr? (1.1.2)

where GT is the symbol—wise transpose of a. It is not hard to see that En(G) is a
(vector space) isomorphism between (F3)k and Ker(H). Therefore, in this case, an
encoder is simply the isomorphism En(G) and a codeword is a symbol vector a in
Ker(H). Notice that, for any a] E (F3)k, H - OT 2 0. For a given codeword a, let us
now suppose that a receiver acquires 71g symbols of or at random with Hg 2 (1 + e)lc,
and denote the received symbol vector as 05. By rearranging symbols of a, we may
express a into a form (Q§,X), where X represents the lost symbol vector. Then

by rearranging columns of H associated with the expression (dg,X), we may also

express H into a form [N; M], where N and M consists of columns of H associated

with symbols of (1,: and X, respectively. With the expressions, the kernel space

constraint HaT = O in (1.1.1) is expressed as Na? + MXT = 0, and thus,
AIXT : 371, where {3T = Nag. (1.1.3)

Therefore, in this encoding scheme, the task of a. decoder is in solving a consistent
linear system (1.1.3) for its unique solution, say the unique solution by X = 0:5. Once
at. is obtained, then an information symbol vector at] can be retrieved from (ag, 08).
It should be emphasized that, for the unique solution of the system, the number of
columns of M should be less than or equal to the number of rows m. In other words,
the number of received symbols né must be greater than or equal to n — k. We refer
to Ker(H) as the Parity-Check code over F3. If H has relatively few 1’s, or say H
is sparse, then we refer to Ker(H) as the Low-Density Parity-Check (LDPC) code
generated by H.

The second type of encoding is as following. We first consider the following trans-
mission scheme over BEC. For a given information symbol vector 01 in (F 3)k, an
encoder directly sets a codeword a as a z: a] so that n = It. It then constantly
generates row vectors H ,3 E F 3 in random by following a certain rule, and at the
same time, it generates a symbol ,3,- by 3, :: HialT and transmits it over BEG. The
transmission continues in this fashion, till a receiver acquires enough number of such
31's Suppose that a receiver acquires more than (1 + 7)n symbols in random, say
the acquired symbol vector as ,3 : (31, . . . ,3"). Then at a receiver end, with each
acquired l3i« a decoder generates the associated check row H i, 1 g 2' g m, and sets
up the linear system

HXT = [3'12 ,3 e mgr”. (1.1.4)

where H is now an m X 72. matrix over F2 that consists of rows Hfs such that H ,X T =
31'- In this transmission scheme, the task of the decoder is also in solving the consistent

linear system (1.1.4) for its unique solution X = 0:. For a given (0, 1)-vector V E F",

let |V| denote the number of 1‘s of V and refer to as the degree of V. If an encoder
uses a certain probability distribution function, say 11(17) :2 Z adard, for the degree
of H,- by Pr(]H,'| = d) = rid, then we refer to this transmission scheme as Luby
'I‘ransform (LT) transmission, and refer to the set of pairs {(H,£3)} as the LT code
generated by )1(.r). Note that each pair (H, ,3) corresponds to a consistent linear
system HXT 2 ,3T.

We now impose two fundamental questions on the systems (1.1.3) and (1.1.4):

Ql) With how many received symbols of Z can the decoders solve the systems

tmiquely?
Q2) At. the same time, how efficiently can they solve the systems?

Let M in system (1.1.3) be an m. x 71.8 random matrix that consists of columns of
H. Likewise, let H in system (1.1.4) be an m X 11. random matrix generated by
a prol:)abilit_\,' distribution /_i(.r). What we want to do in Q1) is to maximize 718
the column dimension of M and is to minimize m the row dimension of H, while
maintaining Rank(M) 2 716- and Rank(H) = it. 'With Q2), at the same time, we also
want to solve the systems in the fastest way as possible. Straightforwardly, both Q1)
and Q2) are the. problem of designing the check matrix H in (1.1.1) for LDPC codes

and the distribution ,11(;1..') for LT codes from which

1. a randomly chosen ill and H (in (1.1.4)) has its full column rank with the largest

number of columns and with the least number of rows as possible, respectively;

2. at the same time, a. check matrix H in (1.1.1) and a random H (1.1.4) are as

sparse as possible.

In the thesis, we exploit LDPC codes for system (1.1.3) and LT codes for sys—
tem (1.1.4). VV'ith the codes, we develop an efficient decoding algorithm that can

solve the systems as long as they have their unique solution. Let us call LDPC and

LT codes together as Low-Density codes. Known so far, LDPC and LT codes are
generally considered as the best answer to the questions Q1) and Q2). The reason
behind this is in the fact that, for a large n the column dimension of H in (1.1.1) and
(1.1.4), if a check matrix H and Mr) is designed well then a random M and H in
(1.1.3) and (1.1.4), respectively, can be lower triangulated by a simple row and col-
umn perrmitatitm, called the Message Passing Algorithm (MPA) [3—6], and thus, the
solution of the systems can be solved by a simple Forward Substitution (F S) [23,24]
over a triangulated matrix very efficiently. It is also possible to design an LDPC check
matrix H and an LT degree—distribution 11(17) with the log-density condition such that
an H in both (1.1.1) and (1.1.4) meets the log-density constraint IH| S cnln(n) for
some constant c > 0, where [H] indicates the number of 1’s of H.

LDPC codes were pioneered by Gallager [1] at 1969, and they were originally
designed to protect data transmission against Binary Gaussian Noisy Channels and
Binary Syn'in‘ietric Channels. The codes were widely forgotten for the decades and
rediscovered by Mackay and Neal in [8] at 1995. LDPC codes were used for BBC
based transmission scheme for the first time in tornado codes by Luby et al in [5, 6]
with the MPA. Soon later, Shockrollahi et a1 developed LDPC codes over BBC as
capacity approaching codes optimized with the MPA for large block lengths n [7,12].
Briefly speaking, a capacity approaching code is a code such that, when a check
matrix H in (1.1.1) is generated by a certain row and column degree distribution, say
a capacity approaching sequence, then system (1.1.3) can be solved by the MPA with
rate 1) = 3,9, referred to as loss rate or erasure rate, close to 1;? (or the block-rate 7.71,?
of M close to 1). Further analysis for capacity approaching sequences can be found
at [4,9,13].

LT codes were invented by Luby [2] and were designed for multi—cast of mass
data. At a sender side, an LT encoder constantly generates symbols by 3,- = Hid?

where each check row H2: is randomly generated by a degree distribution a(:1:), such

as the Robust Soliton Distribution (RSD) in [2]. At a receiver end, assuming that H
in system (1.1.4) follows the RSD in its row-degree distribution and the number of
received symbols m is greater than (1 + 7)n for some 7 > 0, the system can be solved
uniquely by the MPA with an overhead 7 close to 0. With this feature, LT codes were
classified as optimal codes for multi-cast and broadcast. Shokrollahi generalizes the
codes into Raptor codes by employing pre-coding strategy on a with LDPC codes or
other known codes in prior to LT encoding. The decoding algorithm of Raptor code
is a combination of the MPA and GE [14,15].

In practice. however, those capacity approaching and optimal features are not
guaranteed when n is not large enough, say it within several thousands. Through
our extensive simulations with the MPA, we (the author KiMoon Lee and Hayder
Radha) observed that a stable erasure rate 7—3— of LPDC codes and a stable overhead
o," of LT codes for the successful MPA are far away from their ideal limits 1 —— 11,3 and
0, respectively. Instead, we observed that, by the Approximate Lower Triangulation
Algorithm (ALTA) in [3,4], a random M of an LDPC code system (1.1.3) or a random
H in LT code system (1.1.4) can be approximate lower triangulated into a form
PMQT( or PHQT) = [g g] , where B is an l X 1 lower triangular matrix with l close
to a column dimension rte (or n) and (P, Q) is a pair of row and column permutation
of .11 (or H) (see Figure 2.4 and Figure 3.3). Once such a triangulation is obtained,

the systems (1.1.3) and (1.1.4) can be permuted to

AB
CD

(PQ) IIIXT 2 3T (LLB)

QXTzer arm

 

 

HXT=eT nae

Assuming that the permuted system (the left-hand side in 1.1.5) has its unique
solution, it can be solved efficiently by the h-‘Iaximum-Likelihood Decoding Algorithm
(MLDA), developed by Burshtein and Miller in [3] for decoding of LDPC codes.
We tested the MLDA with 3-rate PEG-LDPC codes [13], and the result was quite

surprising. A random m x 716 matrix M in system (1.1.3) feasibly has its full column
rank with the loss-rate p = Zéf- very close to 1 — 7+5, For an example, with n a
few thousands and Tie close to m — 20, a random M has its full rank 71,; with high
probability (see Figure 3.4).

Although the MLDA is much more efficient than a conventional GE in computa-
tional complexities. it still has a lot of redundant computations. First, the MLDA
in [3] requires an explicit construction of the permuted Fri/{QT = [3183] after the
ALTA that is not necessary for solving systems (1.1.3) and (1.1.4). To remove the
explicit construction, we interpreted systems of the MLDA into a equivalent set of
systems that do not require the construction of PM QT. Second, it also results in a
large number of redundant symbol-additions on 3. To remove all possible redundant
additions, we further developed the MLDA into the Separated MLDA (S-MLDA) by
exploiting the MLDA in two steps: the pre-decoding on M in a bit-level and then the
post-decoding in a symbol-level with 3. Shortly speaking, in the pre-decoding step, the
S-ML DA computes all the row operations with M (or H) alone that needs for recovery
of the solution X = no, it then discards all redundant equations in A! X T = 3T. In
the post-decoding step, the algorithm computes the solution by applying the obtained
operations on 3 with an alternative recovery step. To see the improvement in compu—
tational efficiency in number of symbol additions, compare the curves in Figure 3.2
for LDPC codes and Figure 2.3 for LT codes. The S-MLDA with simulation results
tested with 3-rate PEG-LDPC codes [13] was presented in [18, CISS 2007].

We also applied the S—MLDA to the system (1.1.4) for decoding of LT codes. At
the very first simulation, the obtained decoding failure rate of the S-MLDA with a
random H, generated by the RSD, was significantly less than that of the MFA. As
7 decreases, however, the S-MLDA feasibly fails to recover the unique solution a of
system (1.1.4) due to the rank deficiency of H, i.e., 7) = dim(Ker(H)) > 0. On the

other hand, with it several thousands, r} was less than 15 for any ’7 > 0. To remove

those small deficiencies, we re-designed the RSD M13) and altered into a p(:r) by
supplementing a small fraction of dense rows, so that a random H by a p(:r) may
include a few tens of dense rows. By doing so, we gracefully removed the deficiencies
with overheads 7 less than 0.008. (To see the simulation results, compare the curves
in Figure 2.6). Besides, we develop several combinatorial analysis for the design of
RSD MI) and the p(:r) in section 2.4. In section 2.5, we also develop a finite version
of Kovalenko’s Rank-Distribution Theorem in [21,22, 29] for the rank distribution of
a random H, generated by the p(:r). The S-MLDA tested LT codes generated by our
designed p(;r) was presented at [19, ISIT 2007].

Compare to LDPC codes, although LT codes naturally inherit rate-less feature
from its random transmission scheme, the time-efficiency for both encoding and de-
coding of LT codes is far inferior to that of LDPC codes. The reason to this is in
the facts that, in LDPC codes, a fixed check matrix H is used for every instance of
a : (0'1. (.1 p), furthermore, H has no dense rows in general. In contrast, an LT de-
coder has to generate a random H by using the same random generator of an encoder
for every instance of 0. Otherwise, each check row Hi should be directly delivered
to a decoder attached on 3,. To resolve this problem, we developed LT codes with
an arranged encoder matrix M. Specifically speaking, the check matrix H in sys-
tem (1.1.4) is a random sub-matrix that consists of rows of M. With this arranged
encoding scheme, we tested the S-MLDA with LT codes for short block-lengths n
from 102 to 103. Our experimental results exhibited that, although a stable overhead
’7 for the successful MPA is degraded seriously, a stable overhead '7 for the successful
S-MLDA with codes from 111 is slightly better than the one with codes, generated by
the original LT encoding scheme. The time—efficiency of both encoding and decoding
of LT codes in this arranged encoding scheme is about to be same with that of LDPC
codes. The experimental result together with our combinatorial analysis for the Mac)

and p(.r) has been submitted to Allerton Conference 2007 [20].

The rest of the thesis is as follows. Chapter 1 is dedicated to the introductory
backgrormds for the later chapters 1 and 2. In section 1.2, we describe GE as an
LU —factorization algorithm [23]. In section 1.3, we introduce LDPC codes and the
MPA, as a decoding algorithm of both LDPC and LT codes. The MPA is described
as a lower triangulation algorithm by using row and column permutations on a check
matrix. Then in section 1.4, we introduce row-degree distributions of LT codes.

Chapter 2 is as follows. In section 2.2, based on the factorization, we explain both
the MLDA and S—h’ILDA as an advanced form of GE by exploiting partial pivoting
process over the trizuigular block [1%], as shown in (1.1.5). We first describe the
MLDA as an natural extension of the MPA. we then develop the MLDA into the
S—MLDA. In section 2.3, we present the computational complexity of the S-MLDA
with LT codes in terms of the number of {sign, bit}-flips and the number of symbol
additions made by the pre- and post-decoding stage of the S-MLDA, respectively.
In section 2.4, we derive the RSD #(1‘) by using the IVIackay’s recursive formula
[27, ch. 50]. We then alter Mr.) into a p(.r) by supplementing a small fraction of
dense rows, so that a randomly generated H by our designed p(:1:) may fit for the
S—MLDA. In section 2.5, we derive a finite version of Kovalenko’s Rank-Distribution
formula. [21,22,29]. \Vith the rank-distribution, we demonstrate the rank-distribution
of a random H generated by our designed p(;1:). Simulation results under the S-MLDA
with LT codes, generated by a Mr), are presented in section 2.6. In section 2.7, we
further develop LT codes of short block lengths it, generated by an arranged encoder
matrix, and present the simulation results tested with the LT codes under the S—
MLDA. Finally, we conclude the chapter in section 2.8.

In chapter 3, we apply the S-MLDA demonstrated in section 2.2 for the decoding
of LDPC codes. In section 3.2, we modify the S-l\-"ILDA in section 2.2 for decoding
of LDPC codes. In section 3.3, we present the computational complexity of the S-

MLDA with LDPC codes in terms of the number of {sign,bit}—fiips and the number of

10

symbol additions made through the pre- and the post—decoding stage of the S-MLDA,
respectively. In section 3.4, we use PEG software [13] to construct H of block lengths
n from n = 2, 000 to 20, 000. Simulation results tested with %-rate PEG-LDPC codes
under the S—MLDA are presented in this section. Finally, we conclude the chapter in

section 3.5.

1.2 Gaussian Elimination on a Linear System over ng

In this section, we describe GE on H as an LU -factorization algorithm that returns
LU = PH QT, where P and Q is a row and column permutation matrix of H and L
and U is a lower and upper triangular matrix, respectively. GE is generally considered
to be the most efficient computational method for solving a consistent linear system
H X T 2 3T, since it. involves the least amount of arithmetic operations. In particular,
when GE- is aimed to compute the unique solution of the system only, obtaining an
LU factorization of H in the fastest way is the primary aim of GE algorithms. Further

analysis and issues for GE can be found in linear algebra textbooks [23—26].

Let us first define a linear system over 1173.

Definition 1.2.1 (A Linear System over ng). Let H = (hi1) be an m x n matrix
over F2, and let. 3 == (31, . . . ,,iii’m) E (11%)"? A linear system HXT 2 3T over 1173 is a
system that consists of m linear equations over F; such that

2?}:1h1j‘17j : 1’31:
' : ' E HXT=,3T, (1.2.1)

TI. _ ‘ . _ 1'
ijl hmjl] — #3717,
where the sums are taken on IF: and 3T is the symbol-wise transpose of 3. Let us refer
to 3,- and 3 as a syndrome symbol and a syndrome symbol vector of system (1.2.1),

respectively

Throughout the thesis, unless specified, we assume that a given linear system

11

H XI = 3r has at least one solutions, and we refer to the system as a consistent

‘I n
7

linear system over F; Let us denote Img(H) as the image space of H in (F3) i.e.,

Img(H) : {HI/T E (1173)"1 [V E (33)") (1.2.2)

Thus, a given system (1.2.1) is consistent iff 3 E Img(H). Considering that. XT and

,i can be expressed as an n x .3 matrix ($0) and an m x 5 matrix (327-) over lFQ,
where .r, 2 (15:1,. . . ,;r,-,_,.) and 3,: = (3,1, . . . ,;3,-5), respectively, system (1.2.1) can be

arranged in a parallel form of 5 number of systems over lP‘g such that
HXT = Jr a» [H.rl = .31, . . . , Hrj = 51' . . . ,st = .33], (1.2.3)

where .1?) and 3i now represents the jth' column of X T and ,3T, respectively. Obvi-
ously, solving system (1.2.1) is equivalent to solving one single system H17] 2 ,3] over
ng, and H .rj : ,3]. has its unique solution iff there exists a independent rows of H
that form an n X n nonsingular sub-matrix, say H ’ . Once such H ’ and its inverse
(H ’ )_1 are obtained, the unique solution of H X] 2 3T can be obtained by applying
I—l .. - T_ I-1,-/T - ~ - . I
the same (H ) to the system, i.e., X —— (H ) 3 . So, identifymg such H and

then (H ’ )’1 (ii‘idependently from 3) is the primary task for solving system (1.2.1).

Let us clarify several terminologies for the description of GE.

Definition 1.2.2 (An Approximate Lower Triangular Matrix). Let H = (llij) be an

m X n matrix over F2 with m. 2 n.

1. A Lower Triangular Matrix: H is said to be in a lower triangular form, if

1, for 2' =j
hi} 2 . (1.24)

0, fort<j

2. An Approximate Lower Triangular Matrix: Let H be in a block matrix form
[A; B] such that B is an l X in lower triangular matrix with l close to n. We

call H an approzr'imate lower trzimigular matrix.

12

Definition 1.2.3 (Elementary Row Operation). We call a row operation on H over

ng by adding one row to other rows of H as an elementary row operation.

Let a and 7' be a permutation on the row index set [m] = {1,2, . . . ,m} and a

column index set [12] = {1. 2, . . . , n} of H, respectively.

Definition 1.2.4 (A Row and Colunm Permutation of H by a and r). A row per-
mutation of H by 0 is the rearrangement of rows of H in the order of (2'1, . . . ,i7n)
, i.e., H0 = [H,1,. . .,H.,-m]T (a row-wise transpose) where 0(7)) 2 k. Similarly, a

column permutation of H by r is the rearrangement of columns of H in the order of

(JIM-ah). i‘e'v HT = [Hj'1,...,Hjn] where r(jk) = It.

An elementary row operation and a permutation on H can be explained as
matrix multiplication to H that has the same effect on H as does the operation
and permutation. Let us first consider row and column permutations of H. Let

PH _—. [H,1....,H [T and HQT = [H11,...,Hin]. Let P and Q be the matrix

'1 m

representation of o and T, respectively. Foremost, P and P1 is formed by permuting

rows and columns of Imxm in the order of a, respectively, i.e., P = [62-1, . . . ,eim]T
and P31 : [62!] . . "83:71] By direct calculation, 1:"1 2 PF. Equivalently, they can

be expressed as P : (p51) and PT : (p’st), such that

1, iftz‘is I 1, ifszz’,
p5! = and 7) st 2 . (1.2.5)
0 otherwise 0 otherwise
‘t’, " x 7- r —— - « T ’ T — T «T ‘ ‘
In the same way, Q —— [611" . . ,em] and Q -— [ej1, . . "er1] Thus by a row and

column permutation pair (P, Q) of H, systei'n (1.2.1) can be permuted as
HXT : .«3T 4:) (PHQT)(QXT) = PfiT. (1.2.6)

An elementary row operation on H can be also explained as matrix multiplication

to H on the right. For a given row index k of H, let Sk be a subset of [m] that.

13

includes k, and let XS}: 6 1772” be the support vector of 5;, such that

1, if 'i E SA.
XS), 2 (€1,-~ aEk—1e1?5k+1*"' ,6,,,) where 61:: . (1-2-7)

0 otherwise

When the km equation H kXT = 3),. is added to other equations HiXT = 3,, whose

row index 2' is in Sk \ k, system (1.2.1) is transformed to

II

V (H1+€1Hk)XT 31 +613}.-
(Hk—1+€k—1H/.-)XT = 3k—1+€k—1i’3t~
HXI =sT => ( HkXT 13,, . (1.2.8)
(Hk+1+ €k+1HleT = 13k+1+ €k+15k

 

L (Hm + €nin)‘XT I ,3”), + 5mg];

Let Ell“) be the m x m matrix formed by replacing the kth column of the identity

matrix Imx", with XEA’ i.e.,

f

_ k T T , T T T
E( l : [(3'31""’ek—13XSk ,ek+1, . . . ,E’m]. (1.2.9)
Then system (1.2.8) is exactly same with the system
(13“) ~H)XT 2 Elk) .eT. (1.2.10)

Noting that E(k)E(k)H is simply the addition of Hk to the rows H,- twice for 2' E Sk\k,
ElklEfle = H. This is true for any H, therefore, (Efklrl = Eff“). Let us refer
to E (k) as an elementary matrix. E (kl can be explained the representation of the
identity map I : ng‘ ~—+ F32" with respect to, say, the standard basis 3 == {81, . . . ,em}

on the domain Fla” and the basis 3;, on the range ’2” of the identity map, where

Bk : {U'l : (Cl + (16%),. ' ~ :u'lk : 6k: ' ' ”10,”:(617-13‘ €Nlek)}' (1'211)

Thus, the transformed system (1.2.10) is actually a re-expression of H X T : 3T by

14

changing the coordinate axis 3 with Bk of the range 117.3". In this interpretation, what
GE does on H is a. sort of changing bases on the range, till H is transformed into
a lower or upper triangular matrix. Notice that, no operations were made on the
domain of H , except column permutations. This implies that solutions of the system,
up to rearrangements by column permutations, are not changed by any elementary
row operations on H.

Let us now describe the LU—factorization algorithm on HXT 2 3T. We describe
the algorithm based on the exemplary pseudo-codes in Algorithm 1.1. At each
pivoting round I: of the algorithm (see while loop in the algorithm), starting from
H (0) = H, let H (k) = (hfjl) denote the transformed matrix by adding the kth pivot
row (H(k — 1)),k to the rows (H(k —- 1)).,-, such that 2' E 7—" and fill-5:) = 1. Let
Slk : {i E 7' | b.3321) : 1} (see the line 10 in the algorithm), and let 3“) denote the
elementary matrix obtained by replacing the 2']? column of Imxm with the support

vector 1% (see (12.7)), i.e.,
1};

 

”(k _T T .T _T -T
E( l = [e1,eQ,...,e,-k_1, X393}; ,eeik+1,...,em]. (1.2.12)

 

 

 

Thus, the lines 10-12 (see foreach loop) in the algorithm correspond to H (k) =

ElleM‘. — 1). At the last. round 1, the returned H(l) can be expressed as
1
H(l) = E(1)---E(2)-E(1)H = (H 173(k)) H. (1.2.13)
k=l

With the returned 01 = (i1, . . . ,2'1) and T1 = (jl, . . . ,j[) at the end (see line 14 of the

algorithm), let

{i1+1.. - Him} 2 [m] \le {jl+1a - ' - ajn} = [Til \ Tl- (1-2-14)

 

Algorithm 1.1: The LU -factorization on H
1 Input: H, [m] Output: H(l) and (01,71).

 

/%<-- Initialization: -->%/
set ’7' z: [m];
foreach '2'. E [171] do
if H,- = 0 then
[ L discard 7' :2 71(1)

U‘bWN

/%<-- Pivoting Round k: —->%/
while ’7' 7é (ll do

/°/.<-- Pivot Selection: see Remark 1.2.2 -->°/./
(IF-1) =1 in one’s own way;
we

05

 

choose Etk E 7' such that h

 

 

 

8 set 01(‘ik) = k and Tl(jk) = k;
9 [discard T:=T\ik;[

 

 

/°/.<—— Pivoting:H(k) 2: 3011a — 1) -->7./
10 foreach 2'6 7' with which fig-3:) = 1 do
11 update H(k)i I: H(k — l)1'+ H(lfi — 1)
12 if H(k), = 0 then

13 L discard 17' :2 ”I'VE; //<-— To discard null rows

2),;

 

/7.<—— Say the ’while’ loop stops at k =l -->7./
14 return H(l) and (01,77);

 

 

 

Then rearranging [my] and [n] into

a = (171, . . . ,i[;'271+1, . . . ,im) and r = (j1,. .. ,jl;jl+1,. .. ,jn), (1.2.15)
01 [m] \o l 7'l [n] \Tl

respectively, where 0(2),) 2 k and r(jk) = k, let (P, Q) be the pair of permutation

matrix of (o, 7). Then by P“1 : PT, PH(l)QT can be expressed as

1
T_ -(1.~) r T _ szz An—lxn—l
PH(l)Q _ (glee P )(PHQ )_[ 0 0 ] (1.2.16)

Now let LU“) : PEUflPT, which is the elementary matrix formed by replacing the

16

km column of Imxm with the PXSil.’ i.e.,

 

k T T T T
Ll l: [61 ,...,ek_1, ngik yek+1,...,em]. (1.2.17)

 

 

 

-1
Noting that (Ll/fl) = LU“), the factorization (1.2.16) becomes the factorization of

PHQ as below

-T l k Ur z A 1 - z
PHQ = HLO OX "“0““ . (1.2.18)
k=1

In the algorithm, for each index pair ('lksjk) E (01:71): the (27k,jk)th l is selected
as the Arm diagonal entry of both L and U. Once the pair is chosen, then 2k is
discarded from T for the remainder of pivoting rounds (see the second box at line 9
in Algorithm 1.1). Therefore, each L“) is an m x m. lower triangular matrix, and
thus, L is an m x m. lower triangular matrix, and lel is an upper triangular matrix.

In fact,

I
k T T T T .T
lczl

1

where S,- = '1'. E T lilkf ) 2: l for k = 1,2,. . . ,1 see line 10 in Algorithm 1.1).
k H},-

ln particular, if Rank(H) = n. then An_1xn_l = 0. and therefore,

PHQT = (H 30) [g] . (1.2.20)
k=1

It can be also seen that by pivoting columns of L from the first to the last column of
it, any m x m lower triangular matrix L over IFQ can be factorized into L = [123:1 LU“),

where L ( k)

is formed by replacing the km column of Imxm with the kth column Lk.
Similarly, an n x 71 upper triangular matrix U can be factorized as U = I‘LL.” U (k) by
pivoting its columns from the last to the first column, where U (k) is now formed by

replacing the km column of In M with the km column U k . Without loss of generality,

17

 

Algorithm 1.2: Recovery of or by the colun’m-wise F S and BS

 

1 Input: 3 Output: 02

/°/.<-- FS: (PILHUM) -P5T -->°2/
2 for k=1tonbykz=k+1 do
3 //<-- P3Tz— — Lf ”P371, where le) E Lk by 5;, = {2']l,-k :1}.-—>//
add 3% to all other ,3,- where i6 Sk;

/°/.<—— BS: (1122,2200) rsT —->°/./

5 for 12222 tolbykzzk—l do

6 //<"' PJT I: U(klpi’3T, where Ulk) E Uk by 5k = {ilusz =1}-">//
[ add 3% to all other 3,- where 26 Sk;

/7.<-— oTx’I‘ :: 133T. -—>2./
8 for kzl to n bykz= kr+1 do
9 L copy all: z: 3%.

 

 

10 return a 2 ((11,...,on);

 

we may assume that each Ulk) is an m x m. upper triangular matrix by extending

(k)
U“) as [U 0 ]. (1.2.21)

0 Im—nxm—n

Hence by the GE, HXT 2 ,3T is transformed to (LU) [ mm] (QXT)= P3T, then

is transformed into

1
[1715"](OQX1): (H U( M) (H [400) P/fi’T, (1.2.22)
k=n

Once an LU-factorized system (1.2.22) is obtained, the unique solution a of
H X T 2 ,3T can be identified by computing the right-hand side of system (1.2.22)
ltCIatHEl first by F07‘U’d7d Substitution (FS) over the columns of L (from the first
to the last column) then by Backward Substitution (BS) over columns of U (from
the last to the first column of it). An exemplary pseudo-codes for the F S and BS is

described in Algorithm 1.2.

Remark 1.2.1 (Row-wise FS and BS). L and U can be also row-wise factorized as a

18

 

Algorithm 1.3: Recovery of o- by the row-wise F S and BS
1 Input: 3T Output: 02
/'7.<-- FS: (11,1271 LW) -P,3T -->%/
for k:1t0n byA::=k+1 do
//<-- 133T :- UMP/3T. Note LW 2 Lk. -->//
update 'dik :2 3% + 2:11 12,2312 ;

 

N

CA

ab

/%<-- BS: (r133:1 UW) -P,3T —->°/./
5 for krn to 1 bykzzk—l do
//<-- P3T z: UU‘OP3T. Note UH“) E Uk- -—>//
.« — k ,(
update 3% :2 23)}; + 2):,121k113jt;

O5

/°/.<-— QTXT :2 P,3T . -->°/./
8 for 1:21 ton. byk:=k+1 do
L copy (1ka :2 3.1-k.

CD

 

 

10 return a = ((11,. ..,(.1n);

 

product. of elementary matrices. Since the transpose LT is now an upper triangular
matrix, LT = 112;] LU“), where each L“) is formed by replacing the km column of

Imxm with the km column of LT. Then

m T 1
L = (H H“) = H (NUT, (1.2.23)

k=l

kth

where (Liklfl is formed by replacing the row of I mxm with the (cm row of L.

Similarlv, U can be obtained as a row-wise factorized form

‘4

U = H(W‘l)? (1.2.24)

i=1
where (U(M)T is now formed by replacing the km row of 1.an with the kw row Uk.
The F8 and BS in row-wise factorization is described in Algorithm 1.3. It should
be emphasized that Algorithm 1.3 uses precisely 22. rows of L and U. In contrast,

Algorithm 1.2 uses 72 columns of L and U for the recovery of 02.

19

Remark 1.2.2 (Pivot Selections). Let us go back to the pivot selection in Algo—
rithm 1.1 of GE (see the line 7 of the algorithm). Through the pivoting rounds, let
(H(k — 1),] denote the number of 1’s of the row H(k — 1).,- after the round k — 1 and
refer to as the degree of H (k‘ — 1),. If we set the pivot. selection as to choose a row of
degree 1, then the GE is equivalent. to the MPA (see [2,5,14]). In general, when rows
of degree 1 are exhausted prematurely at. round k‘, a row of degree 1 can be made by
discarding columns in H(k — 1) in an appropriate manner. In this case, the GE is
equivalent to the ALTA in [3.4].

J

1.3 Low-Density Parity-Check Codes

In subsection 1.3.1, we introduce LDPC codes, the MFA in [5,6] as a simple GE,
and an systematic encoding of LDPC codes. In subsection 1.3.2, we introduce the
performance analysis of LDPC codes under the MFA in [7]. By using the analysis,
we show that the tornado sequence in [5] is a capacity approaching sequence. Further

details of the performance analysis can be found in [7] and [28, ch. 2].

1.3.1 Encoding and Decoding Algorithm of LDPC Codes

For a. given m, x 72 matrix H over ng, let IH ] denote the number of nonzero entries of

H. \\’c call |H| as the density of H.

Definition 1.3.1 (LDPC Codes). For a given m x 22. matrix H over F2 with m S n,

a binary parity-check code C (H) is defined as the kernel space
C(H) = {a e(1F§)”|H-aT = 0}. (1.3.1)

We call 02 in C(H) a codeword. If H is sparse, for an example, |H| S cnln(n) for
some ccmstant c > 0, then we call C (H) and H the LDPC code generated by H and

an LDPC matrix, respectively.

20

Let H be an m X 72. LDPC matrix. Let us assume that rows of H are linearly
independent, so that. dim(Ker(H)) = n. — m. By GE, H can be transformed into
a systematic form G = [S.,,,X),.;I.,,,x.,.,,], where k z n — 272. Then since G is row-
equivalent to H up to a. column permutation, C(G) = C(H). For a given a] E (1193),“,
let tip 2 Smxk ~01] Then a 2 ((11,019) satisfies the kernel constraint HOT 2 O, and
thus,

(rpkacm) via 5(a): 11“ . (1.3.2)

Hence by a : E(G)oIT, an or] in (11723),“ can be transformed to a codeword 02 E C(H)
in a form of (1 : ((11,0p). To obtain a row equivalent form C = [Smxki Inmm],
however, the filling-in with 1 by GE makes the ]S,,,xk| proportional to 722. Thus, the
computation for up by Snmko] in symbol additions is 0(212).

In general, the quardractic density of Smxk can be significantly reduced when a
row-equivalent G is replaced with a form C : [Sm x k3 mem], where mem is a lower
triangular matrix. \V’e recall that, from section 1.2, L.,_,,1xm = Him” Lu‘), where LU")
is the elementary matrix formed by replacing the 13’” column of Imxm with the lam

column (mem)k. Therefore, once Smxka}w is computed, ap can be computed very

efficiently by applying the F3 in Algorithm 1.3 to the product

I
of): HLUC) S,,,Xka}". (1.3.3)

kzm
Definition 1.3.2 (A Systematic Encoder). For a given m X n LDPC matrix H over
F2 whose rows are linearly independent, let G = [511sz mem] be an m x 72. matrix
which is row-eqirivalent to H , and where the left. block me-m is in a lower triangular

form. Then for a given a] E (FEW, the codeword a- : ((1,, (1p) can be generated by

1k k T (1T T _1 T
L_1 XS l. .01 Z a]: ’ where OP : LINXI’II(S‘I'ILXk '01) (1.3.4)
272an mx ‘
v Ika y g . ,
Let 1311(6) = [fl S . We call 1311(0), 01, and up a Systematzc encoder Of
mxm 21sz

21

C (H ), a systematic part, and a redundant part, respectively. We refer to R = é”,- as

the code rate, and 1 — R as the redundancy rate of C(H).

If H is randomly generated with a certain row and column degree sequences, called

capacity approaching sequences that will be introduced in the following section 1.3.2,
— A . B
then by the ALTA [3,4], H can be permuted to a form H = C ”("4 D M ,
m—lxn—l m-lxl
where the right-top block B is a lower triangular matrix with I close to m. l\qultiplying
' v _ I 0 — .. . fl.

by S — [—DB_1 1] H can be transformed to
A

SH 2 6 where C7 = -DB_1A + C. (1.3.5)

 

 

Then by Gauss-Jordan reduction [23,24], the bottom-left block 6' can be transformed

into the form [C‘k;1rx7‘], and hence, H is row-equivalent to

 

 

 

 

A A B o. I. 0
—k T or 1‘ ”(r , (1.3.6)
Ck Irxr 0 .4k Ar B
where A = [AM Ar] and k: + 7‘ = n —— 1. Notice that [1:]? g] is now an m x m
- . _ ,- . I 0 A.
lower triangular matrix. Hence, by settmg mem 2: [ :4): B] and Smxk :2 [6:],

L’1 s

m. x m m x k

En(E) = [ Ika ] becomes a systematic encoder of C(H). Also notice that the
number of symbol additions to compute (1}) by En(G) is precisely [Sm xkl + lexml —
272. An exemplary algorithm for the approximate lower triangulation of H is presented
in Algorithm 3.1 in section 3.2. Further details and a variety of greedy algorithms
for the ALTA can be found at [3,4].

Let ac- be a received sub-vector of a, when a codeword a E C (H) was transmitted.
Let. X : (1'1, . . . ,.rnf,) denote the erasure symbol vector, so that a can be expressed
as ((16,06). Similarly, let [N; .M] be the rearrangement of columns of H associated

with (ag, X). Thus, the kernel constraint system H OT 2 0 is now expressed as

MXT 2 3T, where ,3T = Na; (1.3.7)

22

The task of an LDPC decoder is in solving the consistent linear system (1.3.7) in the
fastest way, and at the same time, with largest number of erasures n8 (but 72.6 g m)
as possible. Obviously, the system has its unique solution X = ore iff M has its full
column rank.

In general, no matter what Rank(M) is, all of the solutions of (1.3.7) (including
free variables) can be identified by the LU factorization on IV. Once a factorization
of M is obtained by GE, say PMQT = LU [17‘636‘718], solutions can be identified by
first. FS over L then BS over U with 3 as shown in Algorithm 1.2. In general, the
computational complexity of the LU -factorization in bit operations (or bit-flips) is
in 0(722), and the FS and BS together constitutes the complexity 0(723) in symbol
additions of (3. For a moment, let us now assume that .M can be permuted to a lower
triangular matrix L by a pair of row and column permutation (P, Q), say L = PIMQT.
In that case, the erasure (symbol) vector X can be recovered by the simple FS over
columns (or rows) of L with 3 as in Algorithm 1.2 or 1.3. Therefore, the number
of symbol additions by the FS is less than [M[ + [N] = [H] Furthermore, if H is
sparse. then M is sparse also, and therefore, the FS is very efficient.

Let us now describe the h-‘IPA, the fastest decoding algorithm of LDPC codes
known so far. The MPA was designed for decoding of tornado codes in [5] for the
first time, and is equivalent to a lower triangulation algorithm. We explain the MPA
based on the exemplary pseudo—codes in Algorithm 1.4. The algorithm is based
on the Degree Reduction Rounds that corresponds to the Pivoting Rounds of the
LU -factorization in Algorithm 1.1. At each round k of the reduction (see foreach
loop in Algorithm 1.4), starting from 111(0) 2 M, let 111(k) : (771%)) denote the

transformed matrix by adding the km pivot row MU; — 1),k to the rows M(k —— 1),,
,(k—I)
'1ka

the algorithm), and let deg(rl=[(k),~) 2 [A~[(k),-|, the number of 1’s of 111(k),-. Then

where i E T and "Ni-i1) : 1. Let Sik = {2' E T [ 77

2.“ = 1} (see the line 16 in

the row addition by 111(k),- :: H(lr — 1), + Illa: — 1).,k of the 13”" pivoting round of

23

 

Al orithm 1.4: The Messa e Passin Al orithm 011 A!
%<— Initialization: To identify Ad ->%

1 set ’T 2: [m]

2 foreach (received symbol) aj E are do

3 L discard the column H4 from H;

 

4 Input: Ad Output: (01,71).

5 foreach 7'6 7' do

6 identify deg(.l!,:); //<—— i.e.deg(M,-) = [ll/[1]. —->//
7 if deg(M,') : 0 then

a ]_ discard ’7':=’L\2';

%<— Degree Reduction Rounds ¢$ Pivoting Rounds of GE —>%
9 while if yé U) do
10 //<-- Selection of the km Diagonal Entry of L -—>//
11 if 32'), E ’L such that deg(1’l-1’(k' —1),-k) = 1 then
(k—l)

12 identify j), with which mil.- it :1;
13 set 01“?) : 'ik and 71(k') : jk;
14 discard 7 :2 ’7'\z'k;

15 else goto FinalRound;

'/.<- Degree Reduction (it E(k)fl/[(k' — 1) —>‘/,

16 foreach 7' E ’7' with which "Iii—1) : 1 do
7.<— <=> 111(k),- :: .MUc —1),-+ [H(k —1),-k; ->'/.
17 reduce deg(1lf(k),-) :2 deg(1\[(k — 1),) — 1;
18 if deg(M(k),-) : 0 then
19 L discard T :: T\-i; //<—- To discard null rows

 

20 FinalRound: //<——Say the ’while’ loop stops at k: :l
21 if 1: 71,3 then
22 L return (01,77); //<-— declare ’Decoding Success’

23 else
24 Lreturn (01,77); //<—- declare ’Decoding Failure’

 

 

 

Algorithm 1.1 (LU-factorization algorithm) is simplified as the row-degree reduction
by deg(M(lc),-) :: deg(M(li: — 1),) — 1 (see the lines 16 — 17 in the algorithm). The

reason to this is in the fact that the MPA selects a pivot row from rows of degree

24

 

Algorithm 1.5: The recovery of QXR by the F8 in Algorithm 1.3
1 Input: [N; 1’11] and (01,71) Output: X

 

/%<-- Initialization for £3 :1ng —->7./
2 for 2:1t07n byi::2'+1 do

3 if 2'. E 0 then

4 ]_ set 3,: 2: Niog;
5 else

6 L set ,3,- :: 0;

 

/°/°<-- Q‘XT : (Hizne Li“) PLBT -—>%/
7 recover QXT by using the F8 in Algorithm 1.3 with P3T;

 

 

8 return (2X! ,'

 

1 only, and thus, the resulting upper triangular matrix is simply the identity matrix
Imxm. Then by EU“) formed by replacing the 2'2," column of Imxm with the Xgik
as defined in (1.2.7), the Degree Reduction (the lines 16 -— 19 in Algorithm 1.4)
corresponds to Etklil (k— 1) of GE. Similarly, at the last round I, if the MFA succeeds

(i.e. l 2 He) then 111(1) can be expressed as

1
111(718): H E“) M. (1.3.8)

k=ne
Then by using the permutation pair (P, Q) of (o, T), which is extended from the re-
turned (01,7!) (see line 22 in Algorithm 1.4 with the equations (1.2.14) and (1.215)),
the initial system MXT 2 3T is permuted to (PA'IQT)(QXT) 2 P371, then is trans-

formed to a product. form

1
[Inegnc] QXT ___ H Ltk) PfiT, (1.3.9)

£33718

where L“) is now the elementary matrix formed by replacing the kth row of Imxm
with the km row of the lower triangular matrix L = PAIQT.

Once a lower triangulation of M is obtained by the MPA, the erasure vector QXT

25

can be computed by the F S as described in Algorithm 1.5 in section 1.2. In the
algorithm, notice that for the recovery of the lost X, the number of symbol additions

is less than [H], since the row-wise F S uses precisely 72,; rows of H.

Remark 1.3.1 (Further Development to S-MLDA). The MPA by Algorithm 1.4 is
designed to stop when rows of degree one are exhausted (see line 9 of the algorithm).
If the lastly returned 1 is less than 77.6, then a part of X can be recovered by replacing
71,. with l in system (1.3.8). As a matter of fact, the stopping condition becomes
the major defect of the codes when block lengths n are not large enough, say 72 is
within several thousands. The reason to this is that, quite feasibly, the MPA stops
prematurely (i.e. l < 71.6) but 111 has its full column rank ne. In chapter 2 and 3, this
defect. will be naturally removed by exploiting the ALTA in [3,4] of the MLDA. The
MLDA also has a. couple of inefficiencies at the initialization step and with symbol
additions, but. it can solve the system 1le X T 2 ,BT as long as Rank(rW) 2 72.6. In
the later chapters 2 and 3, the MLDA will be further developed into the S-MLDA by

removing all possible inefficiencies of the MLDA.

1.3.2 Probability Density Evolutions on Degree Ensembles

The design of H that. meet the following conditions in both density and rank property

is the primary issue of LDPC codes:

1. For the time-efficiency of decoding codes, H should be designed as sparse as
possible, at the same time, a randomly chosen m x 72.6 sub-matrix M of H

(72.6 g m) can be lower triangulated by the MPA with high probability;
2. A! has its full column rank 226. with 72,-; close to the row-dimension m as possible.

In this section, we introduce Probability Density Evolution that provides us a
convenient tool for designing H that meet the two conditions above. Let us clarify

several terms for the description of the density evolution.

26

Definition 1.3.3. Let 15;, denote the hat, if h—st, 2 1.

Degree of 13;: For a given 15), let. [HS] 2 i and [Ht] 2 j. We say that a 13; has its

row-degree i and col'u.Inn-degree j.

Entry degree ensemble: Let define

 

 

|{1s-rldogtH t)=J'}| [{1szldeg(H )=2'}| .
Ax— . d — . 1.3.10
)— |H| an Pi |H[ ( )
Then let /\(.r) 2 2:121 Ajrj'l and p(.r 22,-)? pix 1 the column-degree and

row-degree distribution of entries of H, respectively. We call (Mr), p(.2:)) the

entry-degree ensemble of H.

Notice that, rather than the term .ri and a3] , each /\j and p,- is associated with the
term 1:171 and :ri—l, respectively. The reason to this will become clear soon. We also
note that ZAJ- 2 /\(1) 21 and 2p,- 2 p(1)21.
Let m,- and nj be the number of rows and columns of degree 2' and j, respectively.
7 _ ’. _ I. . . _ , __ p'[H[‘ _ P"lH[ 3 r .
Then [H] — Z 2. - 7n,- — Z] - nj. Since 772,- — J7- and nj — —-Lj——, the average row
and column-degree a,-, ac, respectively, is expressed as

__ - _ —1.
(2r : [7171' ___ (2 g) 1 and ac = l—Irjl 2 (Z 14) . (1.3.11)

.1
Thus, 7n 2 73%), and hence, the code rate R 2 % can be expressed in terms of or

and ac as following

 

_k_n—m_ %_ :22 _de>
72-;— n —1—E_1_2TJ/J :1 (NWT (1.3.12)

We also note that. from (1.3.11), once the average degrees or and ac are chosen, then
m is constrained as m 2 74%).

Let. H be an m. x N random matrix that follows the entry-degree distribution
(A(.r).,o(.r)), and let C(H) be the LDPC code by H. Let pg 2 I]? be a fraction of

random erasures when a codeword a E C' (H) was transmitted over BBC. One key

27

component. for analyzing the performance of the MFA in erasure recovery is to study
the initial erasure rate ])0 with which an m x n6 random sub-matrix ll»! of H can be
lower triangulated by the MPA. We first approach a probability density evolution in
erasure rate [7 as a probability generz’rting function associated with (/\(.:r), p(.r)).

Let us now interpret the MPA as the following iterative rounds on H: Each round

of the EPA consists of the following procedures:

Round k: If there exists known columns, then for every known column H t, which
was unknown and declared to be known at the previous round, and for every
151 E H’, the degree of H5 is reduced by 1: if deg(H3) 2 1, the algorithm
identifies the 13,; whose Ht, is unknown by that moment. and Ht, is declared

to be known at this round.

At round 0, a column H J is declared to be known, if the associating symbol aj was
received, otherwise unknown. At each round 1;, we say that a 13¢ is unknown, if the

column Ht is unknown.

Theorem 1.3.1 (Density Evolution). Let pk be the probability that a 1 in H is

unknown at the round h. Then

Pr~+1 = 7203(1— (41—1273)- (1.3-13)

Proof. At the iteration round h, an unknown 13,, has its initial row-degree i with
probability fit» and the degree is reduced to 1 with probability (1 — pk)'i—1, because
all other 1's in the row H5 must be known by the round 1:. Similarly, 131 is still unkown
with probalinlity 1 — (1 —- jay-1. Hence, at this round, the average probability that

an unknown 1 is still unknown at the end of the round is given as

qr.- = Zn.<1—<1—m.>“‘1) = 1-ptl—Pkl (1.3.14)

Now, an unknown 15; of the round k: has the column degree j with probability A],

and it is still unknown if the column Ht is initially lost (with probability p“) and all

28

other 1’s of Ht are still unknown. Thus, the probability that an unknown lst has
a column-degree j and is still unknown at the round k + 1 is given as pg/\j(qk)j—1.

'I‘l'rerefore, at the begining of the round I: + 1, a 1 is unknown with probability
“—1 -'-1
Pk+1 = ZAJlI-ltflli. 1:1102qu1, =71) . M1 — no we). (1.3.15)
j 1
Cl

It should be notice that from (1.3.13), 72(pk — pk“) 2 1 for the successful lower
triangulation of AI by the MPA. Then replacing by pk 2 :13, the MPA should satisfy
the inequality

pg - /\(1 — [)(1— .r)) < .13, VI 6 (0,pg]. (1.3.16)

For a given block length 72, let p*(n) be the suprenrum of such pg satisfying (1.3.16).
Then designing (Mr), p(.r)) such that its p*(n) is closed to the ideal linrit 1—R 2 g:— is

the key part of designing LPDC codes, and not every (M17), p(:r)) fulfills this property.

Example 1.3.1. Let /\(.r) 2 1:2, p(.r) 2 1‘5. Then p* can be obtained by considering

the suprernum of {pg} in which each pg satisfies

[)()(1—(1—1L‘5))2 < 1‘, VI 6 (0,pg]. (1.3.17)
771

It is shown that in [4.9], p* is approxirnately 0.429 which is far from 7 = 0.5 .

The inequality (1.3.16) is useful whether a known (/\,p) holds it or not. Let us
call a entry degree ensemble (A, p) as a capacity approaching sequence, if it holds the

following condition: for a given 6 > 0, there exists Dg such that for all D 2 DO
(1 — R)(1— e)/\D(1— p1)(l —- 13)) < :r, Vr E (0, (1 — R)(1— 6)), (1.3.18)

where /\/)(.r) and [20(2) consists of first D terms of /\(.r) and p(.r), respectively.

20

The first capacity approaching degree sequence for BBC is the tornado sequence

discovered in [5] and [6]. Let D :2 [l/e], and let

 

 

 

1 D 1 D 1
A .« = —— .2” HD = s10. 1. .1
0(1) W, 21—1? . () Z,_, n( >. (3 9)
222 222
- HD
[20(1) 2 cuff—1), a2 ( ). (1.3.20)
720

Plugging in (ADle into (1.3.16) asserts

 

pgAD(1— [20(1— 1.)) Sp0AD(1— cow) < gag) 111(6—027) 2 2:. (1.3.21)

Hence, successful triangulation of M by the MPA is possible, if the fraction of erasures

is no more than flich, “e note that by ()f A)( 2(f p)(l) in (1.3.12),
, 1 _c,
— — 2 — -- . 1. .22
(1 R>H,D——,<1 1/<D+1)> a(1 e ) (3 )
Thus ——32 __u (1 — 1/(D +1)) and is larger than (1 — R)(1 — l/D). Conse—
quently,

(1 — R)(1— 1/D)AD(1— pD(1— .T)) < 1‘, VI. E (0, (1 -- R)(1-1/D)). (1.3.23)

Many other capacity approaching sequences can be found in [12]. In practice,
however, once a good degree sequence is found by linear search as in [5], many other
sequences can be made by changing its fractions slightly. In chapter 3, we simu-
late LDPC codes under the S-MLDA generated by a slightly modified right-degree

er‘rsembles appeared in [4,13].

1.4 Luby Transform Codes over BEC

In this section, we introduce LT codes invented by M. Luby [2], which was designed
for rnulti- and broad-cast of multimedia over BEC without retransmission request of

symbols over the. Internet. For the design of LT codes, we introduce the Ideal Soliton

30

Distribution (ISD) and the Robust Soliton distribution (RSD). We then describe
the ISD in two ways: first by Mackay’s interpretation in [27, ch. 50], then second by
Shokrollahi’s interpretation in [14]. For the original design of the ISD, we refer readers
to the LT paper [2]. In section 2.4, the RSD will be explained well by generalizing

the Mackay's recursive fornnrla (see Lemma 2.4.1 at p. 52).

1.4.1 Encoding and Decoding Algorithms of LT codes

Let. us first describe the LT transmission scheme over BEC. Suppose we would like to
communicate an information data set I to receivers over BEC. We first. subdivide the
I into 72 symbols (or packets) of equal length 5, say 02 2 (01, . . . ,an) 6 (1:3)”. Let
us call a, and a an input symbol and an input symbol vector, respectively. Now let
p(.r) 2 23:1 pdrd be a given probability distribution. The LT transmission scheme
is as follows. For a given input symbol vector 02 E ( .3)" (at an LT server), an LT
encoder constantly generates syndrome symbols 31’s by using the p(:r) and a in the

following manner:

1) a degree d is randomly chosen with probability [1,), then a row Hi 6 IF? of degree

d is chosen at random from the (1]) possible choices;
2) the encoder computes ,3, :2 HiaT, it then transmits 3.,- over BBC.

The transmission stops when a receiver acquires a sufficient number of syndrome
symbols. At the receiver end, if more than m syndrome symbols are received, where
772. 2 (1 + 2,")72. for some o,“ > 0, then an LT decoder recovers a by solving the consistent

linear system
HXT = 137‘, where s = (131,...,;3m) e (rgyn (1.4.1)

and H consists of rows H,- such that Hich 2 32-.

31

Let us compare the systems (1.4.1) for LT codes and (1.3.7) for LDPC codes. In
both LT and LDPC codes transmission scheme, the task of decoders is in solving
the consistent linear systems (1.3.7) and (1.4.1) for their unique solution. Although
the systems are alrrrost same except the notations, there are significant differences
between LT and LDPC code based transmission schemes.

In LDPC code based transmission scheme, for every instance of I, first, I is put
into a] in WE)", where k is fixed by k 2 dim(Ker(H)); second. a] is transformed
into a longer symbol vector (1 2 ((11,013) in Ker(H); then lastly, symbols of a are
transmitted over BEC till a receiver gets enough nurrrber of them, or every symbols
of or is transmitted if a feedback is not available on the channel. The syndrome vector
3 of system (1.3.7) is computed by an LDPC decoder. Since H is already known to a
decoder, an LDPC decoder can quickly identify system (1.3.7) by reading columns of
H. However, since the M in system (1.3.7) is a sub—matrix that consists of columns of
H, the row dimension of M is always fixed by the row-dimension of H, and therefore,
k. is fixed for every instance of I.

In LT transmission scheme, contrastingly, first, 71 can be chosen conveniently for
each instance of an information data. I; second, I is simply put into an 02 E (113.3)";
then lastly. a syndrome vector ,3 in system (1.4.1) is generated by an LT encoder and
is transmitted over BEC. For every instance of (1, however, the system (1.4.1) should
be identified at the initialization step of decoding algorithms. To communicate the
system (1.4.1) to a decoder, each H,- can be directly attached to 3,, or a decoder can
generate H by using the same random generator of the LT encoder. Note that in
both cases. the cost for communicating H in system (1.4.1) is not trivial. A variety
of pseudo—random generators are available for the selection of a degree d and a row
H ,j of degree d. For an example, in the sections 2.6, 2.7, and 3.4, we use Mersenne

Twister Algorithm [16] for the random selection of d and Hi.

Definition 1.4.1. (An LT code by p(.r)) With a received symbol vector 3 from an

32

LT encoder, let H be the m x 77. matrix over F 2 with m 2 n such that 13,: = HiaT for
i = 1, . . . , m. We define the LT code generated by p(:r) as the set of all pairs {(5, H)}

in which each (:3, H) forms a consistent linear system (1.4.1).

Assuming that rows of H follow the distribution p(:1:) such as the RSD in [2], it
is known that. if m 2 (1 + 7')”, El 2 0, then a random m X n matrix H by p(:1:) can
be lower triangulated by the MPA, and hence, a can be recovered by the FS over the
triangulated matrix (see [2, Theorem 17]). In reality, however, particularly for short
block lengths n, say It is within several thousands, the triangulation by the MPA is
not guaranteed, if 7— is not large enough. We note that system (1.4.1) has the unique
solution a iff Rank(H) = 71. When Rank(H) = n, regardless of the failure of the
MPA, system (1.4.1) can be solved for its unique solution a at least by a conventional

GE on H. In section 2.2, we will generalize the MPA on H into the S-MLDA.

1.4.2 The Robust Soliton Degree Distribution

Similar to LDPC codes, the design of LT codes is focused on the design of a row—degree

distribution p(.r) that meets two conditions:

1. A random m x 71. matrix H, generated by p(;r) with the row—dimension m as close

to n. as possible, can be lower triangulated by the MPA with high probability.
2. H is sparse as possible.

Through the degree-reduction rounds of the IVIPA on H, let us call the set of rows
of reduced-degree 1 at. each round It as a Ripple. The basic property required of a
good degree distribution p(:r) is that, the number of rows of reduced degree 1 at each
round It is greater than 1 but is as small as possible. If a size of the ripple is too large,
then some of the rows of reduced degree 1 in the ripple, say H (13),, may be same with

the ones already in the ripple, so the check equation Hz-XT = [3, of system (1.4.1)

33

is redundant. If the ripple is too small, then it may become empty, before the MPA
finishes the lower triangulation of H.

The ISD p(:r) described next exhibits the ideal behavior in terms of the expected
number of rows of a random H generated by {)(12), needed to recover 0. Specifically
speaking, one row of degree 1 in the ripple gives one row of reduced degree 1 for the
next round of the degree-reduction process. In this sense, exactly n rows are needed
to recover n. input symbols by the MFA. The ISD, however, is quite fragile so that it is
useless in practice. Even a small variance of the ripple through the degree-reduction
rounds causes it to be empty. However, it gives many of the crucial ideas for the RSD

described later.

Definition 1.4.2 (Ideal Solitan Distribution). The ISD p(.r) = Zil=1pfl3i is defined

as following:

- for z' = 1,

pi = ‘ . (1.42)
p'iZz'i—l—l) fori=2,...,n

Let. H be an m x 72. matrix generated by the ISD p(.z‘). Then

Tl n
1
H = in - =1+n —. 1.4.3
221 122
Thus. the average row-degree a7. 2 @ can be a[_)proximated as ln(n) for large 71.

Let us first give an easier interpretation for the ISD by using Mackay’s recursive
formula. in [27, pf392]. Let H be a random matrix generated by the ISD p(:c). Through
the degree-reduction round t of the MPA, starting from H (0) := H, let H (2‘) denote
the residual matrix of H (t — 1) by discarding the row Hit and the column H jt, when

tm diagonal of a triangular matrix L by that round. Now,

the 111d}. is selected as the
let [Lt (1') denote the expected number of rows of H (t) having its reduced degree 2' after
the reduction round t. we want to design a degree distribution by which a randomly

generated H gives the ripple size ht(1) = 1 for all t 6 {0,1,. . . ,n -— 1} through the

reduction rounds of the MFA. At the reduction round t, for each degree '27 > 1, since

34

every row of H is generated in random, the probability that a 1 of a row in H(t)
having degree i is in the discarded column H it is ”—14. Thus, the expected number of
rows of H (t), whose degree 2' is reduced to 2' — 1 in H (t + 1) by the discarded column

Hit, is given as Lrifl—‘(fl' Similarly with h¢(2' + 1), a total of i+121h_’(i+1) rows of degree

2' + 1 in H(t) become rows of degree 2' in H(t + 1). Therefore, at the beginning of the

round 1‘. + 1, the expected number of rows of reduced-degree 'i is given as

 

 

(1.4.4)

flt+1(‘i) : ht“) (1— i ) + (2+1)ht(i+ 1).

n—z‘. n—t

Setting by ht+1(1) = h¢(1) = 1 for all t, we get ht,(2) = Ef—t from (1.4.4). Then by

the induction on (1.4.4),

 

met) : .- _ ' . (1.4.5)

Particularly with t = 0. we obtain

TUE—1)- fOI‘ 7 > 1
110(1) 2 (1.4.6)
1 for '2', = 1.
Then normalizing by p, z: 3075;), we obtain the ISD as

 

1 1 1 1
: —,—,—....,__ ,.'..,————— . 1.4-7
/) (71' 2 2 - 3' 2(2. — 1) ’ 71(n — 1)) ( )

In the following remark, we derive a differential equation and the ISD is approxi-

mated frorn the solution of the equation.

Remark 1.4.1 (Sl‘iokrollahi’s Interpretation for the ISD). Let H be an m x n random
matrix H generated by a row-degree distribution p(;z:) = Z, pixi. At the degree—
reduction round t of the MPA, the probability that a row of initial degree i has
exactly one 1 in the residual matrix H (t + 1) is as following. Since every row of H is
generated in random, the probability that exactly one 1 of the row is in the residual

matrix H(t + 1) is '27 (1 — t—jZ—l). Now, the probability that all other i — 1 number of

, . . . . - "—1 . .
1 s of the row is in the t. number of discarded columns at round t 1s (£7)! . L1kew1se,
at the round 11 + 1, the probability that all other i — 1 number of 1’s of the row is in
i—l
the t + 1 number of discarded columns is given as (E) . Thus, the probability

71

that the row of degree 27 in H becomes a row of degree 1 in H (t + 1) after the round

its)(tri‘iei‘)

Hence in average, the probability that a row of H becomes of a row degree 1 in
H(t + 1) is given as

t+1 " f. t+1 “H n . t H
<1— NM .> at)
'2: 2:

= (1— 33—1) (p'((t+1)/n.) — p’(t/n)). (1.4.9)

7L

t + 1 is given as

 

 

 

 

Then by using p’((t + 1)/72.) — p’(t/n) r: %p”(t/71) for large n, the probability (1.4.10)

can be approximated as

 

7'7.

(1— H1) ip"(t/n). (1.4.10)

We now assume that the row dimension m of H is very close to the column dimension

n, so that the expected number of rows of degree 1 in H (t + 1) is approximated as

t+1

771-(1.4.10)z (1— —) p”(t/n). (1.4.11)

71
Then setting by (I — iii—1) p” (t/n) = 1 and (r. 2 %, we derive the differential equation
(1—.r)p"(.17)= 1, for O < .L‘ <1. (1.4.12)

Then using the initial condition p(1) = 1, the solution of the differential equation

(1.4.12) is given as

 

p(.r) = Z 1 Ii. (1.4.13)

222 2(2. — 1)

The distribution above is similar to the ISD, except that the first term p1 = O and it

has infinitely many terms.

As mentioned earlier, the ISD ,0(.r) in Definition 1.4.2 is so weak because, a
random H by the {)(1?) has the expected ripple size as 1 through the degree-reduction
round of the MPA; even a small variance of the ripple causes it to be empty. Fur-
thermore, some of the columns of H could be null. A small modification on the ISD
fixes this problem. The RSD in [2] ensures that the expected size of the ripple is large
enough at. each degree-reduction round of the MPA, so that it never becomes the
empty set with high probability. The idea of the RSD is in the design of a row-degree
distribution ,u.(.r) by which an m x n random H gives the expected ripple size about
c- \/Ti 111(11/6) for every reduction round of the MPA, where 6 is the upper bound of
the probalnlity that the MPA on H fails to the complete lower triangulation of H and
c is a. constant of order 1. The intuition for the ripple size 0- fl ln(n/6) is come from
the observation that, according to Luby’s in [2], the probability of a random walk of
length n. deviates from its mean by more than fl 111(11/(5) is at most 6. So, the RSD

is designed with 110(1) 2 crfilnM/d).

Definition 1.4.3 (Luby’s Robust Solitan Distribution). The RSD Mr) 2 Emmi is
defined as follows. Let R = 0- fl 111(71/6) for some constant c > 0. We first define

’7'(.L‘ = 2 7,11) as following:

R/(in) for27=1,...,n/R—l
Ti 2 Rln(R/6)/n for 2' = n/R (1-4'14)
0 fori=n/R+1,...,n.

We then add the ISD p(.r) to 7'(;17) and normalize it as the RSD n(.'r.) = Emmi
such that

p,- = (p,- + T,)/w where w 2 2(1), + Ti). (1.4.15)

2.

for all i = 1,2, . . . , n.

37

Setting the number of syndrome symbols by m 2 mo gives the expected number

of syndrome symbols of degree i by

n. R - n
2 .
n-m =n~ (01+ a) = £3;— + Rln(R/6) ifz' = 51? - (1-4-16)
n ' ' 71
i i—l If 2 2 R

Especially, notice that mm = 1 + R and m ~ #2 2 n/2 + R/2.
We introduce the main theorem of the LT paper [2]. For the proof of the theorem,

we refer readers to Theorem 17 in the original paper [2].

Theorem 1.4.1 (Theorem 17 in [2]). The MFA on a random m x n. matriz~ H,
generated by the RSD ,u(;r), fails to recover the input symbol a with. probability at

most (5 from a set of m : n 'u.) syndrome symbols.

Remark 1.4.2 (Further Works on the RSD). In section 2.4, replacing the initial
condition h.((1) = 1 with hg(1) = S + l for some integer S _>_ 1, we generalize
h‘Iackay’s recursive formula. (1.4.4) into (2.4.1). we will explain the Luby’s RSD [1(33)
as a particular case of the solution (2.4.4). To ensure the success of the MPA with
high probability, it should be emphasized that the number of syndrome symbols (or

the number of rows of H) should be large enough.

Remark 1.4.3 (Raptor Codes). In [14], Shokrollahi generalizes LT codes into Raptor
codes by using pie-decoding stage on a. The main idea of Raptor codes is that, an
input symbol vector (i is protected by systematic LDPC codes or other codes in prior
to LT encoding called “Pie-Coding”. Then LT encoding is applied to the precoded

input symbol vector. For further detail, see the raptor paper [14].

38

CHAPTER 2

The Maximum-Likelihood Decoding
Algorithms of LT Codes

In this chapter, we first present the S—MLDA as an advanced form of the MLDA in
[3]. We then present the design of LT degree distribution p(r.) by supplementing the
RSD 11(1) with a small fraction of dense rows. Thus, a random H, generated by our
designed p(.r), may fit for the S-MLDA. By using the Kovalenko’s Rank Distribution
in [21, 22, 29], we also present the rank distribution of random H generated by the
p(.r). Simulation results, which show the viability of the proposed MLDA of LT codes,
are also presented in section 2.6. In section 2.7, particularly, we substantiate that, by
experimental results, LT codes from an arranged encoder matrix can achieve a stable

overhead e," (for the successful S-MLDA) close to O.

2.1 Introduction and Backgrounds

Let a : ((11... . .an) 6 (FS)” be a given input symbol vector that we would like
to communicate over BEC. In the LT based data transmission scheme, an LT en-
coder constantly generates syndrome syn'ibols ,3,- E F3 using a. row-degree distribution
p(.r) 2 22:1 pdrd and a in the following manner:

I. a degree d. is randomly chosen with probability pd, then a row H 2'. E If”; of degree

d is chosen at random from the (3) possible choices;

39

2. the encoder generates J, = HiaT, it then transmits 13,- over BBC.

The transmission stops when a receiver acquires a sufficient number of syndrome
symbols. At a receiver end, if more than 771 = (1 + ’7)n syndrome symbols are
received for some 7' > 0. then an LT decoder recovers the a by solving the consistent
linear system

HXY‘ : 5T, )3 Z ()31. . . . “3771) (2H11)

where H consists of rows H,- such that HiaT = 32* Assuming that. rows of H follow
the distribution p(.r) such as the RSD in [2], H can be lower triangulated by means of
permuting rows and columns of H. as in the MFA [5] (or see Algorithm 1.4). Thus
0 can be recovered by the FS algorithms Algorithm 1.2 and 1.3 over a triangulated
matrix of H by the MFA. For short block lengths 71, however, the success of the MFA
(a triangulation of H by the MFA) is not guaranteed as y —* 0.

Nonetheless, regardless of the MFA failure, system (2.1.1) has its unique solution
iff Rank(H) : 72.. If Rank(H) = n, then system (2.1.1) can be solved efficiently by the
MLDA suggested by Burshtein and Miller in [3]. Their MLDA exploits four major

routines as following:

1 ALTA: By the ALTA on H (see [3,4] or Algorithm 3.1), a pair of row and column
permutations (P, Q) of H is obtained with which H = PHQT = [g E], where B

is in a lower triangular form. Thus, system (2.1.1) is permuted into

 

 

.4 B [X72 sf _ _T T
c D Kg ,3?" HX 10' ’ ( l
_ XT] 3T
where XT : QXT 2 X712 and PJT : fl].
2 851?: Multiplying by S = [411—314(1)], called Back-Substitution of References

40

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Q
Q
Q |
O

 

 

 

(a) H by ALTA (b) SH by BSR (c) LU by GE

Figure 2.1. The MLDA on H

(BSR), system (2.1.2) is transformed to

 

_ XT —.T _ _ ,
3 a] = is] ‘1’ WW ”'1‘”
R ,

 

 

where A = B‘lA and C = C —— DA. (See Figure. 2.1-(b)).
3 GE'XR is recovered by using on CXR = BIT (See Figure. 2.1-(c)).
4 Final FS (FFS): X72 is recovered by X7? = AXR + :35.

The core of the MLDA is in the novel combination of the ALTA and the BSR by S
that reduces system (2.1.1) into a small system C'XR = BIT by means of a partial GE
on H over the columns of the triangular block [5] from the first to the last column
of it. When H = [g], the MLDA becomes the MFA. Of particular interest of the
MLDA is in the ALTA on H, generated by the RSD. The prominence of Luby’s RSD
is not just in the perfect triangulation of H by the MFA for large block lengths n and
overheads '7', but is also in the robustness of the RSD. A small perturbation on the
RSD does not affect much the triangulation of H by the MFA. Furthermore, even for
short 71 and ’7' close to 0, H can be permuted into an approximate triangular form

H in system (2.1.2) whose left-block [g] is very small. Thus, the GE on C is very

41

efficient compared to the conventional GE on H. This advanced form of GE also can
be found in [27, EX-50.12] and the US patent [15]. Another MLDA using guessing
strategies on XR at a bit—level was developed in [17]. In the algorithm, whenever the
triangulation of H (by the MFA) stops prematurely, a codeword bit, whose value has
not been determined yet, is chosen and declared to be known (by assigning l or 0).
The triangulation proceeds in this fashion, and the algorithm succeeds decoding as
long as Rank(H) = 71.

Let (1 x r be the matrix dimension of Q, where q = ’yn—l—r. Note that Rank(H) = n
iff. Rank(C—T) = r. If Rank(C) = r, then the GE on C’ can be performed by the LU-
factorization algorithm Algorithm 1.1 (see also [23, ch.7]) that returns Q in an
LL-’—factorized form C = LU [17'6“] such that L and U is a q x q lower and upper
triangular matrix. respectively (see Figure 2.1-(c)). In fact, by the GE, L—1 and

U ‘1 can be obtained in a product form of elementary matrices, so that
r 1
T 7 —l *T —1 k -1 k ,.
XR = (LL) .3, . U = H U< >, L = H L( ), (2.1.4)
A21 [1:1‘

where Lik) and U0“) are the elementary matrices formed by replacing the km row of
Iqxq with the Arm row of L and U, respectively, and B) is the one in system (2.1.3)
whose symbols are associated with rows of Q. Even if Rank(Q) < 7", free variables
in XR can be identified by the GE. Thus, system (2.1.1) can be solved for a by
retransmitting the input symbols of free variables only. Otherwise, the deficiency
may be further reduced by increasing a fraction of dense rows on H.

In this chapter, without explicit. construction of the permuted H in system (2.1.2),
we first identify systems of the MLDA as an equivalent set of linear systems in a prod-
uct form of elementary matrices via the pernuitations (P, Q). Let. HQT 2 (HR; H72],
the rmrrangemeiit of columns of H associated with (XRaszl- We identify sys-

tem (2.1.2) from system (2.1.1) via (P,Q). Then using S = PTSP, we interpret

42

system (2.1.3) (in the BSR) as
3pm; HRJXT = 3137". (2.1.5)

Let HR = SH'R. For each 1:, 1 S k s q, the km row Qk of Q is identical to the
1km row (HR),k of HR for some 1);. Hence, we perform the LU -factorization over
the row set {(HR),k}Z:1 and obtain m x m matrices L and U that. are identical
to an L and U via a permutation pair (argrr), respectively, and whose inverses are

also in a product form of elementary matrices similar to the ones in system (2.1.4).

Consequently, systems (2.1.3) and (2.1.4) together is equivalent to
[(ra)-1.§.(HQT)] .XT ..—. [am-13] .1371 (2.1.6)

Based on routines of the MLDA, we compute system (2.1.6) by exploiting the S-

MLDA that consists of two major steps; pie—decoding and post-decoding as following.
1. [ire-decoding:

(a) compute the left-hand side of system (2.1.6);

(b) discard the equations in system (2.1.1) that become null after the GE on

HR. (See null rows in the bottom of Figure 2.1-(c)).

2. post—decoding:

(a) compute the right—hand side of system (2.1.6) by ,BT :2 (L )-1§,3T;
(b) recover XR from the ,5’ by looking at (of, Ty);
kth

(c) recover each I), of X72 using sparser of the equations of the systems

(2.1.2) and (2.1.3) as in below

em}; :13). +21ng or as, = 8,, + 21,297,“. (2.1.7)

43

The major role of the pre-decod-z'ng step is to find out precisely 71 check equations, and
at the same time, to compute all row operations on H that transform the H in sys-
tem (2.1.1) into a form [[330 é] as shown in Figure 2.1-(c). Then the post-decoding
is designed to recover (XR, X73) by applying the same row operations without any
redundant. symbol additions on d.

For a higher probability Fr(Rank(H) = 71.), small fractions of dense rows are
required in p(.r). Most of the dense rows, however, become null after the GE on C".
Thus, ahead of the post-decoding step, all of redundant rows should be discarded to
avoid symbol additions of 13 over those rows. (See the curves in Figure 2.3 removed
by step 1b)).

A in system (2.1.3) is not sparse in general. Furthermore, its column dimension
7‘ becomes larger as ”y -—+ 0. However, the top part of A is more likely sparser than
the top of [A; B]. In fact, many rows in the top of A are null or with degree one.
On the other hand, the bottom of A is denser than the the bottom of [A; B]. Hence,
the alternative recovery by step 2c) by comparing the degrees l/‘ikl and (lAkl + lBkl)
improves the efficiency in symbol additions significantly. The improvement of the
efficiency in symbol additions is presented in Figure 2.3 (see green curves in the
figure removed by the alternative recovery step 2c)).

The remainder of this chapter is organized as follows. In section 2.2, we elaborate
on the systems (2.1.5) and (2.1.6) from the perspective of basic linear algebra over
lF-Z. For exemplary pseudo-codes of the routines of the S—MLDA, see section 3.2. In
section 2.3, we estimate the computational complexity of the S-MLDA in terms of the
number of {sign, bit}-flips and symbol additions of 6 made by the pie-decoding and
post-decoding, respectively. In section 2.4, we design a row-degree distribution p(:r) by
SUpplEII’lCI’ltlI’lg a small fraction of dense rows for higher Fr(Rank(H) = n). We then
analyze the rank-distribution of H by using Kovalenko’s rank—distribution of random

matrices [21, 22,29] in section 2.5. In section 2.6, we present our simulation results

44

tested with LT codes, generated by a designed p(.r) in section 2.4 with block-lengths

n, 103 S n S 104, for the following scenarios:

1. the decoding error rates of the codes under the S—MLDA and the MPA to tell
a. stable overhead 7 for the successful S-MLDA and MPA,

2. number of symbol additions by the post—decoding to tell the efficiency of the

S-MLDA in symbol additions of ,3;

3. fractions of references % to tell the computational complexity of the pre-decodz’ng

in a Int-level;
4. the rank-deficiency 'r} = dim(Ker(H)).

We then substantiate, based on our experimental results, that a stable overhead '7
for the successful S-MLDA is far better than the stable 7 for the successful MPA,
while the computational complexity of the S-MLDA in symbol additions maintains
within few tens of n. In section 2.7, in the same scenarios 1) — 4) above, we present
the perforn'iances of LT codes of short block-lengths 72., 102 S n S 103 generated by

two encoding schemes:
E1) encoding by rows of a (Iv-n.) x 71 matrix A];
E2) encoding by a random generation of rows of H.

Based on our experin‘iental results, we also substantiate that, under the S—MLDA, LT
codes generated by an arranged encoder matrix M also achieves a stable overhead 7

for the successful S-h’ILDA close to 0. We then summarize the paper in section 2.8.

2.2 The Separated MLDA

We first outline several notations that are used in the remainder of the chapter. For a

given m x 71 matrix K over lF-z, we denote A1,]; Ki, Kj , and [Kl as the (i, j )t'h entry, the

45

th row, the j‘"h column, and the number of 1’s of K, respectively. We use the notation

2'
1,-j to indicate Isl-J- = 1. W'ith the matrix dimension m x n, let [m] = {1,2, . . . ,m}
and [n] = {1, 2 . . . ,n} the row and column index set of K, respectively. In the rest of
the section, we verify the systems (2.1.5) and (2.1.6) in a product form of elementary
matrices.

First, by flipping a known 1 into —1 through the diagonal extension of B, the

ALTA (see [4, p644} or Algorithm 3.1) can be designed to obtain a set of ordered

pairs (01,71) C [m] x [n] such that.

(0[,7'1) =(‘i1,jr+1) >- >- (il,jr+l), n=l+r. (2.2.1)

Thus, an index. pair (2T3,j,-+t) in a) X Tl indicates the (s, t)th entry of the triangular
B which is identical to hier+t in H. With the 01 and 71, let (R, 7?) and (7,71) be

the disjoint pair of [n] and [m]. respectively, such that.

R = {kw-air}: 7—3 '3 T1 = {jr+1’-"vj'r+l}v

With the pairs, we then set. the permutations
a : [m] r—> [m], 0(2).) 2 k, and 7' : [n] r—> [71], 7(3),) 2 k. (2.2.3)

The matrix representations of 0 and 7', say P and QT, is obtainable by permuting
rows of I mxm and columns of [mm in the order of a and 7', respectively (see also

(1.2.5)). Associated with (73,71), let X: (X73, X72) such that

X7; : (.rJ- ,...,;rJ-r) and X7? = (IL‘J‘ ,. . . ,1]; ). (2.2.4)
1 r+1 7+1

Then via (P, Q), system (2.1.1) is permuted to system (2.1.2).
Second. multiplying by 8—1, the top system of (2.1.2) is brought into X71; 2

.4X77é + 8—153, then substituting the X7; into the bottom system of (2.1.2) yields

46

EX}; 2 B‘ldz + 21le as shown in system (2.1.3). This step is the BSR in [3], and
8—

“DB

system (2.1.3). Note that 5‘1 = [g (1)] and is a lower triangular matrix. Therefore,

. . . . l .
it can be accomplished by multiplying S = l _1 ?] to system (2.1.2) as shown in

S can be decomposed as
1
3 2 H 506) = 3(1)S(l-1) . . . 3(2):;(1), (2.2.5)
k=l

k)

where each Si is the elementary matrix formed by replacing (Imx,—,,)k with H k

and l is the number of columns of the left block [ g]. The computation of SH in

system (2.1.3) is accomplished by the. iteration
H :: Slklfl, k = 1,2,. . . ,1. (2.2.6)
Consequently, system (2.1.3) is expressed in a product form

1 l 1
[(11 SW) . [:3] , (II Sm) . 2T 2 (1] gm) -P;3T. (2.2.7)
k=l ” k=l k=l

Notice. that in the iterative BSR system above, since S [ g] is always known as [(1)],

B
D

 

 

 

the explicit computation of S'[ g] is redundant.
We now interpret the systems of the MLDA without explicit construction of the

permuted H = [g 1%]. First, since H = PHQT, system (2.1.3) is expressed as
(SP)(HQT)XT = spuT -=— (2.1.3). (2.2.8)
Then n'nlltiplying by P”1 : PT in both sides,
(PTSP)(HQT)XT = (PTSPmT E (2.2.8). (2.2.9)

Rearranging colun’ms of H associated with (X73, X72), we then interpret the H QT in

system (2.2.8) as (HR; HR] such that

HR = [HJ'I;...;HJ‘r), H72 2 [er+1;... ;er+!]. (2.2.10)

47

Let S = PTSP, and let. S“) = PTS(k)P formed by replacing the column (Imxmyk
with the column er+k via the km index pair (2k,j,.+k) in (a), T1). Then by P"1 =
PT and (2.2.5).

1 1
s = PTSP = H PTS<‘~')P 2: H 5'“). (2.2.11)
k=l k=l
Substituting the product. (2.2.11) and [Hm H72] into system (2.2.9), the iterative BSR

system (2.2.7) is transformed to

1 1 1
[(11 SW) HR; (H 3“”) HR] XT = (H 3“”) 57‘. (2.2.12)
k=l k=l kzl

Note that, once S is known. 5'an is always known as PT [(1)], thus, the computation
of SHR alone is enough for the computation of SHQT and is obtainable by the
iteration

HR :: SWHR, k = 1,2, . . . ,1. (2.2.13)

Let HR : S'HR. Then since Ck = (HRMY via 0(1),.) : Ir. for all ik E T, we replace
the LU—factorization on C7 as the factorization over the row set {(HR).,-k}z:1 with

additional steps. At each pivoting round I: of GE:

1. \Vhen a pivot 1 is chosen for the kth' diagonal of LU, store the index pair

8ka
(ska) E T x R into (0,373.).

—

2. For each pivoted 15% whose row index 3 is in T, flip it into __15‘tlc in (HR)S.
3. Then discard the row (H'Rlsk from the {(H’Rlik} updated up to that round.

After the GE, if Rank(C-U = r then

—.

(armrr) : (.91,t1) >- > (.97.,t7‘) C T x R. (2.2.14)

Thus, for each 8k E 0,. and tJ- E Tr, the —1 or 1 in HR can be identified as

$ij 8ij
the ij of an L or U in system (2.1.4), respectively. Notice that, if Rank(é’) < 7" then

free variables are )recisel ' the .r.-’s whose index ' is in R 7'7.
J

48

Let ,3T = 33T. we note that, each 1;” in. L“) or UV“) in system (2.1.4) cor-
responds to the symbol addition (31);; 1: (31);,. + (3))j, where ,3) is the one in sys-
tem (2.1.3). Sin’iilarly, the _15k1‘j or lskatj in (HRlsk corresponds to the symbol
addition 39,; 1: 39k + st via the km row index 8k and the jth row index sj in or.
Therefore, each L“) (or (full) in system (2.1.4) corresponds to the m x m elementary
matrix EU“) (or £703), formed by placing those —15k?‘j (or 13kg, respectively) as the
15kg}. in the row (Imxm),,.k. In this way, via (own), the product form of L‘1 and

U—1 in system (2.1.4) corresponds to the products

1 1‘
L‘1 : H U“ 4: L’l, (7—1 = H Um 4: U4. (2.2.15)
kzr k=1

Consequently, via (HQ) and (0r,7'7-), the systems (2.1.3) and (2.1.4) together, as

shown in system (2.1.6), is combined as

t‘f‘lIZ—13[HR;HR] RT = U—IL‘IS‘eT. (2.2.16)

where S, 0—1, and 1.2—1 are in a product form of elementary matrices as shown in
(2.2.15) and (2.2.11). In other words, this means that, by representing the (07-, Tr) as

the permutation matrix pair (Pr, (2,) on HR,

A
U’IZ’IHR = P,.TPT 1m. Qr. (2.2.17)
0

In the pie-decoding step in section 2.1, the step 1a) can be sm‘nmarized as the

following diagram

 

1LTA BSR - GE -——
H i——» H , a; H ———>LU. 2.2.18
(01,71) 72 (i l l) (2 2.13) 7C (2.2.15) ( )

Then all redundant check equations HZ'XT = 32:, whose row index 2' is in T \ or, are
discarded at the step 1b). The right-hand side of system (2.2.16) is computed by

the post-decoding step as described in section 2.1. We note that, in (2.1.7) of the

49

alternative recovery step, each Ak, Ak, and Bk is identical to (II-173),” (HR)ik’ and

(HI-2),]; via 0(1),.) 2 11', respectively.

2.3 Computational Complexities of the MLDA

In practice, several supplemental instructions are indispensable for the efficiency of
the S-MLDA, for examples, degree reductions through the rounds of the ALTA and
updating the (01, T1) in the ALTA, and so on. Since a symbol addition or a {sign,
bit}-flip accompanies those instructions within a constant time, we estimate the com-
putational complexity of the S—MLDA by counting the number of {sign, bit}-flips and
symbol additions encountered during the pres-decoding and post-decoding, respectively.
Through the section, let us assume that R 79 01.

We first estimate the complexity of the pres—decoding stage. By the ALTA, every 1
in H is flipped into —1 to obtain a permutation index pair (01,71) in equation (2.2.1).
Hence the number of sign-flips by the ALTA is |H|. While computing HR by the
BSR iteration (2.2.13), each 1 in H72, except in the diagonal of B, corresponds to one
addition of rows in HR. Thus, the number of bit-flips by the BSR is proportional to
'r(|HR[ — n + r), where r is the number of columns of HR. By the GE on HR, when a
pivot 13].-1‘ k is chosen at round 19, the row (HR)3k is added to the rows of T of which
the with column entry is 1. Since [(HRlskl g (7“ — k) and [Tl g (r — k) + 771 at the

round It, the number of {sign, bit}—flips together is less than

 

 

,. 7.
Z I<HR>Sknfl -—- c 2 MI: + W) (23.1)
k=1 k=1

for some constant c. In fact, our simulations exhibit that, at round [13,

— 'r—k — r—k + In
I<HR>.,| s .2 and m s i 2) 1 , (2.3.2)

and thus, c S :11. Hence in aggregate, the number of {sign, bit.}-flips from the pre-

50

decoding step can be upper estimated as

1 1
|H| + 71117—2) + 57cm? + Ear? (2.3.3)
ALTA BSR G'E

\Vhen 7‘ z 671. for large n and small 6 > O, the estimate (2.3.3) may be dominated

by either (762)713 or (e3)n3. Hence, in this case, the computational complexity of the

3 and ’7E2

pie-decoding step in a bit-level is 0(713) but with small constant factors 6
(see [3, p. 4]).

Let us now estimate the number of symbol additions made by the post-decoding
stage. We. recall the removal of all redundant rows (including most of the dense rows)
by the step la) of the pre—decodmg and the alternative recovery step by 2c) of the
post-derxxl'zlng in section 2.1. At the initialization step, since only the 321’s, whose row
index i is in at U or, are copied from ,3 and since IO”) U 07-] = n, precisely, 71 copies of
,3,"s are made for ,3. For the computation of ,3T :- U‘1L“133T in system (2.1.6), due

H
to the removal of redundant dense rows, significantly less than [7337' and less than

7‘2 in number of symbol additions of 3 are made by 3 and U ‘11-4—1, respectively.

Now let (1,- : min{|(HR)i], [Hz-l}. By the alternative recovery in (2.1.7), a total
of d = 211:1 dik symbol additions are made for the recovery of Xfi, that is also
significantly less than [A;—1%. Hence in total, the number of symbol additions from the
post-decoding is significantly less than

H+H~
n.+———--[ I [R[+T2.

2.3.4
1 + 7 ( )

We now assume that the original MLDA in [3] is used for the recovery of X. (Recall
2. BSR, 3. GE, and 4. FFS of the original MLDA section 2.1). In the pre-decodz'ng
step, only the {sign, bit}-fiips that correspond to one row-addition constitute symbol
additions of 3 or 3. First, a total of [H72] by the BSR and less than 22:1(7n+k) row

additions by the GE on HR, are made for the recovery of X73. Then for the recovery

of X72, a total of [A] symbol additions are made by the F F 5. Hence in aggregate, the

51

number of symbol additions by the original MLDA is upper estimated as
[H73] + [A] + 7'('yn + 7“). (2.3.5)

In Figure 2.3, we show that, due to the heavy density [4] and dense rows in H, the
estimate (2.3.5) is much larger than the one made by the post-decoding stage of the

S-MLDA. (Compare black and red curves in Figure 2.3).

2.4 Degree Distribution Design with Dense Rows

In this section, we first go over LT degree distribution design with Mackay’s simple
recursion formula in [27, ch. 9]. A fine analysis of the design in a continuous frame
can be consulted in Shokrollahi’s works in [14].

\Vith a designed distribution 11(27), we then alter ,u,(.z:) into a p(1r) by supplementing
a small fraction of dense rows of degree g. We then analyze rank properties of an
m. x 71 random H generated by p(.r). By doing so, we provide a simple way for the
armropriate value of [JR/2.

Let. 11s first consider the diagonal extension of the MPA on H in [4, p. 644].
Starting from H(0) :2 H, at the tth extension step, let 11bit be selected as the t”‘
diagonal entry of L 2 PH QT, and let H (1‘) denote the residual matrix by discarding

the jtm column and the 11m row from H(t -— 1).

Lemma 2.4.1. Let h.,g(d) denote the eapected number of rows of degree d in H(t).

Then after the (t + 1)’h diagonal extension step, H(t + 1) has

‘n —t —

(h,(1)— 1)( — —1—)+¥:—@, tfd= 1,

I‘I.)+1(d) 2 (2.4.1)
ht(d) (1 — Edi-t) + (d+lizh_[d+1), Othemuz'se
Proof. Once a 1 is chosen for the (t+1)’h diagonal entry of L, say 1it+1Jt+1 is chosen

th

for the diagonal entry, the It+l row counted in 11,2(1) is automatically discarded,

L

thus, there remains ll[;(l) — 1 rows of degree 1 in H(t). \Nhen the jHIH column is

discarded from H(t), each of the ht(1) — 1 remained rows of degree 1 has 1 in the

discarded column with probability 71:, Hence, about (ht(1) - 1)_n—1_—t rows of degree
1 become rows of degree 0, and therefore, about (h.t(1) — 1)(1 — 71—14) rows of degree

1 in H(t) still remain as rows of degree 1 in H(t + 1). Now, a row of degree 2 in

H(t) has a 1 in the discarded column Hji+1 with probability 372:? This implies that

about ht(2)—(—2_—t rows of degree 2 in H(t) become rows of degree 1 in H(t + 1) after

ll

the diagonal extension. Therefore,

 

 

n—t n—t'

hvi_+1<1>=<m<1)—1>(1— 1 )+2h’(2) (2.4.2)

In case of d 2 2, when the jt+1th column is discarded from H (t), a row of degree d

in H(t) has a 1 in the column with probability #7. This implies that ht(d)(1 - —d—)

n—t
rows of degree d in H (1‘) still remain as rows of degree d in H (t + 1), at the same

(1+1

n —t

 

time, about h)(d + 1) rows of degree d + 1 in H (1‘) become rows of degree d in

H(t + 1). Then the sum of the two cases asserts the ht+1(d) in (2.4.1). 1:]

Theorem 2.4.1. Expecting the ripple size by ht(1) = S + 1 for allt = 1,2, . . . ,n,

n — t S
l d = —— —, 1. 2.4.3
Id) d(d—1)+d' 61> ( )
In particular, when t = 0,
S + 1, for d = 1,
hold) = . (2.4.4)
S

___—n .1
d(d—1) + 3) Otherwise

Proof. Setting by [11(1) 2 h.t+1(1) 2 S+ 1, the first recursion in (2.4.1) yields ht(2) =

11 ~ I.
T

+ 73. Let us assume that ht(d) = flit—15 +3 for all (1 2 3. Plugging in ht+1(d) =
n—(t+1)
d(d—1)
(d + 1)ht(d + 1) yields the estimate (2.4.3). (2.4.4) is obvious by t = 0. Cl

+ g into the. second recursion in (2.4.1) then simplifying it into ”—i—t + S =

53

Let us now set m the number rows of H by

H

 

m = Z hO(d) % n + S(1 + ln(n)). (2.4.5)
(i=1
Thus, from the right-hand side of (2.4.5), 7 z W Then normalizing by m,
we derive the RSD as
n h ((1)
11(1‘) = Z [.ldlfd, where 11(d) = 0 . (2.4.6)
m.

(121
The RSD in [2] can be thought of as a special case of (2.4.4) with S = 0111(71/6)\/ii

and hQ(1) = S + l as below

_ S
(1(dn_1)+ga l<d< 2.,

”0“” = -——2(.}’_.) + 5111(5/6). d = g. (24.7)
(1((1n_'_1) , otherwise.

Theorem-17 in the original LT paper [2] guarzmtees that when an m x n matrix H
is randomly generated by the RSD in (2.4.7) with m z n + S(ln(S/(5) + ln(n/S)),
the LT system (2.1.1) has its unique solution and can be solved by the MPA with
1,)I'obability at least 1 — (5.

The triangulation of H by the MFA depends on the constraint ht(1) _>_ 1 for all
t. In particular, for short block lengths n, 7 should be increased for the successful
MBA with high probability. For a stable ripple design, see Shokrollahi’s Raptor paper
[14. pp. 21—22]. In contrast, the success of the S-MLDA depends on Rank(C) = r.
The efficiency of the S-MLDA in computational complexity may be degraded due to
the GE on C. However, the fraction of references £- is quite small for all ’y > 0, and
hence. the GE on C in a. bit-level may not be a major drawback to the efficiency.
(See Figure 2.4)

Let H be an m x n random matrix over ng generated by a row-degree distribution

54

17(2)) 2 Zpdzcd. We first estimate the column—degree distribution of H, say /\(;7:) =
Z'dn‘ZO Ada‘d. Then with A0, the fraction of null columns of H, we estimate a lower

bound of the density [H] to keep A0 small.

Lemma 2.4.2. Let m 2 (1 + ’7-')77.. Then the column-degree distribution ofH can be

(2):}:1 ((1— —)+%2~)(1+7)npd. (2.4.8)

Proo . For a ‘iven row H - let d- = H: . Since H - is random] 2 chosen from n,
8 1: i I. 7 dz

estimated as

possible choices, entries of H,- follow the distribution

fd.( 1‘2) (1— i‘) + %1‘, £3: 1311}le =1). (2.4.9)

I 71

Let H (k) denote the sub-matrix that consists of the first k rows of H. Obviously, the
column degree distribution of H ( ) is f(11(.7: 7:.) Assume that columns of H (k) follow
the degree distribution 11,-_1 fdz- (.7: )2 25L _0 afrj. Now let H(k +1) be an expansion
of H (Iv) supplemented with a random row of degree (Ilk+1. Then, a column of H (k+ 1)
was a column of degree j in H (A) with probability aj and it becomes a column of
degree j +1 111 H(lc+ 1) with probability _k,_d+1 .This case happens with the probability

1
‘I'J(n/+1'Silllllmly1 a column of H(h + 1) was in degree j +1 in H(k) with probability

 

aj+1 and it remains as a colunm of degree j + 1 in H(k‘ + 1 again with probability

1
d +1

1 .
‘AH kn ). Smce these two

 

(1—

 

). This case happens with probability aj+1(1 —
cases are all cases for a column in H (k + 1) being degree j + 1, a column of H (l: + 1)

has degree j + 1 with probability

dk+1 dk+l
(lj‘ ( ’12. ) +aj+1 (1— 77. , (2.4.10)

which is exactly the coefficient of the term .rj H of the product

 

 

k k+1

fdk+1(;13)ZajfEJ—‘ H fdz(:1‘ (2.4.11)

j: —0

Hence, by the induction, H has the column-degree distribution
m
1(2) = [I fdia). (2.4.12)
i=1

Now, H follows the row-degree distribution p(;r) with m = (1 + 7)n, and the number
of rows of degree d is (1 + 7)npd. Therefore, rearranging the product (2.4.12) with

respect to d then substituting (2.4.9) into (2.4.12) asserts (2.4.8). Cl

Theorem 2.4.2. Let a7. be the average row-degree of H. Then the fraction of null
columns of H, A0, is estimated as
71
A0 2 11(1— 4/22.)"(1+1)Pd z 2‘01““). (2.4.13)
d=1
, . . . ,\(k)(0
Proof. By Lemma 2.4.2, the fraction of columns of degree 18 is given as M, = 71—2,
and hence, the product form in (2.4.13) is clear by A0 = A(O). For sufficiently large
77., since

(1 — d/n)”(1+7)pd z erdpdnllfll, (2.4.14)

the product can be approximated as e"(»-1+7")ded. Then since ar = ded, we

conclude (2.4.13). C]

For the unique solution of system (2.1.1) with a destined 6, 0 < 6 < 1, the number
of null columns in estimate is given as n/\0 = ”lie—(”710", and thus, a row-degree
distribution p(.17) should hold the inequality 7ie_(1+7)a7’ < 6 < 1. Therefore

111(71/6)
‘ (1+ 7)

 

or [H] 2 n 111(71/(5). (2.4.15)

ar

To meet this inequality, we note that dense fractions in p(;r) are indispensable.
Most of the fractions of the RSD 11(1) in (2.4.6) are too small to get [nad] Z 1.
For an example, with short block lengths 77. in a few thousands, [71nd] = 0 for d > 60.

V\-"e recall that dense fractions are indispensable to meet the inequality (2.4.15). For

56

this reason, we alter the 11(1) into p(:z:) having 3 parts:
. d 2
[)(1’) = Z pdflid-i- Z pdl‘ +pn/21En/ , (2.4.16)
(16191 dED2

in the following manner:
1. I’d z l‘d for (l E D1 = {1, . . .,20};

2. 0.001 g pg 3 0.01 for d E D2, where D2 consists of few tens of degrees (1 such

that 20 _<_ d S 400;
3. 0.001 g [27,/2 3 0.005.

The idea of the p(.r) is as following. First of all, the fraction pn/Q is for higher
Pr(Rank(H) = 71). Second, D1 is for smaller % with the constraint ZdeDl #d 2 0.9
based on equation (2.4.6). Lastly, based on the density constraint (2.4.15), D2 is
aimed to hold :DlU’DQ dpd Z [EH—(Q. Thus, hopefully, the [A,B] of H in sys—
tem (2.1.2) consists of rows of degree d in D1 U D2 only.

One would set. p(.1:) :2 pplU92(:r)/pplupz(0) that meets the inequality (2.4.15)
with a small 6. It seems to the authors that, even with a large 7, an m x 71 random
matrix H generated by the p(;r) does not achieve the probability Pr(Rank(H) = 71)
close to 1. For an example, in Figure 2.10, rank deficient cases happen just one
or two times (out of 1000 random constructions of H by the p(;7:)) with deficiency
dim(Ker(H)) = 1 or 2. In contrast, when the p(:7:) is supplemented with pn/2 :2 0.005,
the small deficiencies are gracefully removed up to 1 + 'y m 1.008.

Since [H] is increased by 1223(1 + ’7')p,,/2 with the fraction pn/2 alone, a slight
increment on pn/2 may cause [H [ much heavier than desired ones. Let us now present
a simple way for an appropriate value of 1072/2 with an estimated dim(Ker(H)) through
simulations. Let H be an m x 71 random matrix generated by the pDIU32(x) =

ED1UD2 pdrd. For a given V E IFS, let Vl = {X E lf‘lz’lV - X = 0} the complement

57

space of V. \Vith the row space RS(H) 2: {ZiEI H,|VI C [712]}, let Rank(H) =
dim(RS(H)).

Theorem 2.4.3. Let H be an expansion ofH supplemented with Inn/2 random rows

of degree %. Then,

~ 1
Fr (Rank(H) < n) g 77, where 77 = dim(Ker(H)). (2.4.17)
2 71/2 7

Proof. \Ve first note that, from basic linear algebra, RS(H) C VL iff. V E Ker(H),
and Ker(H) C Ker(H). We also note that Rank(H) < n iff. RS(H) C Vi for some
nonzero V E Ker(H). For each nonzero V E Ker(H), since supplemented dense rows

are chosen in random,

Pr(RS(H) c vi) g 2"”’71/2. (2.4.18)

Then since

 

Ker(H)[ 2 2”, the inequality (2.4.17) is clear by the sum of the proba~
bilities (2.4.18) for all V E Ker(H). Cl

The author of the thesis is not aware of any closed form of mathematical estimates
for 7;. Nonetheless, for a given ”191“)sz = ZdevluDg pdxd, n can be estimated
by extensive simulations of the S-MLDA very efficiently. Then by increasing mn/g in
(2.4.17), one would achieve r} = 0 with high probability. Thus, 1071/2 may be assigned

by ) °- 122,—? with “111 '1))1'o)ri'1te N
.. Ill/2"“ “+20” 1 ‘ (ll 1 ‘W l'

2.5 The Rank Distributions of H

In this section, we introduce Kovalenko’s rank distribution theorem over finite fields
[21,22,29]. We then derive a finite version of the rank distribution of the supplemented
matrix H in Theorem 2.4.3.

“'13. first. introduce the limit version of the rank distribution theorem. Let H be

58

an (n + k?) X n random matrix over a finite field qu with the density constraint

ln(n) + .r.
n

l .‘
S PTULI'J' 75 0)_<_1- m, (2.5.1)

71

where 1: ——> oo arbitrarily slowly. Kovalenko and Levitskaya [21] showed that, as

n —+ 00, for any fixed integers k and s with k + s 2 O,

. 1
1 Ilzis+1il —'_7)

 

. i ' . — —- : q .
121220 P1 (Rank(H) — n S) q-“(k+5) Hf:ls(1— _11') . (2.5.2)

For an example. with (q = 2, k = 30, s = 0),

lim Pr(Rank(H) = n) = H (1 — i) (25.3)

n~fix- 21
i=31

which is very close to 1. In [22], Cooper further improved that, under the assumption
that H has no zero columns, the distribution (2.5.2) is also true when the condition
in (2.5.1) is weakened as a: ——> —00. Note that the distribution (2.5.2) is not directly
applicable to a random H generated by a p(;r) in (2.4.16), because both the row and
column-degree distributions of H may not. meet the density constraint in (2.5.1).
Let H be an m x n random matrix over F2 generated by the pDIUv2($) with
rank-deficiency I] = dim(Ker(H)). Starting from H(0) = H, let H(k) be an
expansion of H(k — 1) supplemented with a random row of degree 3%. Now let

(kw/(to) : Pr (Rank(H(k)) = (n — 7}) + to) where O S to S 7].
Proposition 2.5.1. The mnk—distribution of H(k + 1) follows
1 1
Ck+1.r;(W') 1‘ Card's} — 1) 1— W + Ck,n(w)2—,,'_—w~ (2-5-4)

Proof. Only two cases are possible for Rank(HU: + 1)) = n — (n — w); either
Rank(H(k)) : n — (n — a) +1) or Rank(H(k +1)) 2 n — (7) — w). If R.ank(H(k)) =
n — (I) — to + 1), then Rank(H(k f 1)) = n — 7‘} + w iff. the supplemented row is not
in Ker(H(/c)). Since dim(Ker(H(k))) = 7) — LU + 1 in this case, Rank(H(k + 1)) :

59

n — (n —to) with probability (p.001) — 1) (1 — EFF—L?) If Rank(H(k)) = n — (77 —w),
then Rank(H(k + 1)) = n — (7] — LU) iff. the supplemented row is in Ker(H(lc)). Since
di1n(Ker(H(/e))) : n — w in this case, Rank(H(k +1)) 2 n — (7) —w) with probability

<k»'l(W)27—_7/1-'Then the sum of the two probabilities asserts (2. 5. 4). Cl
We now derive the solution of (2.5.4), a finite version of rank-distribution of H(lc).

Lemma 2.5.1. Lot to g ls. to S 7), and let l = k — to. Then

 

u)
1 1

(Ayala!) = H (1‘ 5,1713) W ' 5(wal)» (2-5-5)

121

where _
to i1 l'l—l 1
Shel) = Z Z Z 211+12+m+ir (2.5.6)
'l1=0i2=0 il=0

Proof. Although the same arguments of Theorem 3.2.1 in [29, p. 126] can be used
for the probability (2.5.5), we derive the probability (2.5.5) by using (2.5.4) and the

mathematical induction. If to : 0 or 1 = 0, then clearly

k
1 1
Ch‘.'l](0) = W and Ck,7](k) : H (1— m) . (2.57)

i=1

Assume that (2.5.5) is true for k and (.1. we show that by using (2.5.4), the distribution

 

(2.5.5) also holds for A? + 1 and to. Let l = l; — to. First, (Av/(w — 1) (1— 273;?) in
(2.5.4) is expressed as
“’ 1
H<_ 211+1— ___.) 2ll+1)(n-w+1) .sw — 1.1+ 1), (2.5.8)
and S(w‘ — 1.l + 1) in the above can be expressed as
[+1
Stu — 1,! + 1) = Z 2‘ 29:1“. (2.5.9)

w2i12-°-Z'll+121

60

Similarly, the (Aqua) in (2.5.4) is expressed as

_1_
2fj-w‘

 

[i (1_ 2"+1_i) 2(l+1)(n-w) 'Sw’ 0’ (2'5'10)

where S (to, l) can be expressed as

3(a), 1) : Z 2‘2131111'8. (2.5.11)

w2112---22')2(2'z+1=0)

It can then be seen that, from (2.5.9) and (2.5.11),
S(w‘—1,l+1)+S(.o,l)=S(to,l+1). (2.5.12)

Therefore, the sum of (2.5.8) and (2.5.10) gives Ck+1§,](w) as

 

 

11(1— 2]}+1—i) 2(l+1)(r}—w) SCI-’01 l + 1)) (2.513)
2,:
where.
1
s(...,1+ 1) = Z 211+12+~-+i)+1' (2.5.14)

W22713"'3il+130
1:]

Theorem 2.5.1. With the same notations in Lemma 2.5.1, let H = H(kt). Then

with. to = 7} and Is 2 7}, as a particular case of the distribution (2.5.5),

77
Pr (Rank(H) : n) = H (1— 5%:) .S(17, l). (2.5.15)

i=1
The author is not aware of any simpler form of S (n, l). Furthermore, it is difficult
to compute 8(7). l) because it requires an l-dimensional array for the computation
of the multiple sum. Hence in practice, once a rank-deficiency 77 is estimated from
simulations, the lower-bound (2.4.17) is more practical for the value of 971/2 N onethe-

less, it is straightforward to see that, by Theorem 2.4.17, Theorem 2.5.1, and by

61

lzh-n,

1 '7 1 "1

i=1
Remark 2.5.1. So far, we assumed that H is an expansion of H by supplementing
random rows of degree ’5’. In fact, Lemma 2.5.1 is also true when supplemented rows
are randomly chosen from 2" possible choices (see the proof of Theorem 3.2.1 in
[29]). We may anticipate that the distribution (2.5.5) also holds, if supplemented rows
meet the density constraint (2.5.1). Heuristically, the anticipation is reasonable in
the following sense. Let Ra11k(H(lc)) = n —— (n—w). By GE, H(k?) can be transformed
to a row-eqmvalent form [A; I ] where I is the identity matrix of size n — (77 — w).
Then pivoting the supplemented row of H (k + 1) with diagonal entries of the I,
let the supplen‘iented row be transformed to (Ah-+1? 0), and thus, H (l: + 1) is now
[11:16]. Then Rank(H(k +1)) = 1+ Rank(H(lc)) as long as

AA.“ # 0. Now. if we assume that. Ak+1 is a random vector in 1113—”) where 77 — w =

row—equivalent to [
dim(Ker(H(k))), then Ah.“ 3i 0 with probability 1 — ill—75'
Remark 2.5.2. V'V’hen q = 2, the limit distribution (2.5.2) can be derived from
Lemma 2.5.1 by setting H(0) = (2) (so that 77 = n) and w = n — .9. To see this, we
first rearrange the sum 5(a), l) in (2.5.5) as
S(...»,1).—. :2—21 2 2"‘1—1 Z 2‘21. (2.5.17)
i120 il-lzil i1=i2

Since a} —-> 00 as n —+ 0c», the rearrangement can be simplified as a. product form

_1 oc-
- 1 —1 —22‘
7 u; ' — —— — l. c o I 2
"Inn 5( ,l) — (1 2) E 2 1 E 2

11:0 i3£i2
1 ‘1 1 “10° —11
: (1_.2_) “(17:0 :2 1
11:0
1 1 _1
= H(l—fi) . (2.5.18)

Then plugging in the product (2.5.18) into the distribution (2.5.13) gives the limit

distribution (2.5.2). (See also [29, p130]).

We. now close this section by providing a formal approach to an estimate of
[Ker(H)[. Let H be an m x 71 random matrix over IFQ generated by a p(;r) in (2.4.6),
and let X be a nonzero random vector in F3 with [X] = k. Then the number of
solutions of system (2.1.1) is exactly |Ker(H)|. Now, for a given random row H,- of

degree (1,,

Pr(H,- - X = 0) 2 (2.5.19)

 

Then since H has "ll/’11 rows of degree d and each of them is generated independently

from all other rows,

 

_ ,. .. d mpd
Pr(X E Ker(H)) = H (1+ (1 22k/n) ) . (2.5.20)
10,1750

Next, X can be chosen in total (2) different ways, therefore, the expectation of
[I‘x'er(H)[ is given as
1 n n d mp4
727; Z k H (1+ (1 — 215/71.) ) . (2.5.21)
k=0 pd#0
If a fine approximation of (2.5.21) is possible, then an appropriate value of [27,/2 can
be assigned for Pr(|Ker(H)| = 1) z 1 without much difficulty. It seems to the author

that, the equation (2.5.21) is more likely blown up to 00 by a small increment on pd.

2.6 Simulation Results

In this section, we provide our experimental results simulated with LT codes of block-
lengths n, 103 S n S 104, generated by a. row-degree distribution p(;r) in (2.4.6)
supplemented with the dense fraction [On/‘2 = 0.005. Particularly in Figure 2.2,

we substantiate that, under the S—MLDA, our designed LT codes can achieve the

63

 

 

 

(p(1)€1F1=(0 015, 0.47, 0.104, 0.074, 0 047,0 032)
D, (11(1),,37: (0. 023, 0 017,0 013, 0.011 0.009 0. 008)
[(120004 for 13<d<20
D2 101120-002 for21 <d<30
pd=0001 for 31 <d<70
pd = 0 004 for d— — 71 72 141 260 350
’D3 pm =0005

 

 

 

 

 

Table 2.1. The row-degree distribution p(:1:)

performance in overhead 7 (for the successful S-MLDA) close to 0. In Figure 2.4,
we also provide the fraction of references rf = g which shows the computational
efficiency of the pre—decodmg with respect to r 2 en. (Recall the small constant
factor 6 in (2.3.3) at p. 51).
The spectrum of our simulation is as follows. First, we generate a distribution
u(.r) in (2 4. 6) with S = 15 and n = 103. Based on (2.4.16) and the conditions
1) - 3)t therein, 11e alter the u(.1) into the p(.r) as shown in Table 2.1. Second,
we tested LT codes under the S-MLDA for the 10 block lengths from n = 103 to
n = 10- 103. For each fixed 71, a row dimension m is increased by 1 from m := n up to
m :2 (1.2)71. Then for each matrix dimension or x 71, an m X 71 random matrix H by
the row-degree distribution p(;1.') is constructed 100 times by generating its rows using

h-Iersenne Twister algorithm [16] on [n]. Then for each instance of H, the S-MLDA

is tested with a nonzero input symbol vector (1 in (173)" for the following scenarios:

1. (_lecoding failure rate of codes under the S-MLDA and the MFA;

M

. number of symbol additions by the S-MLDA and the original MLDA in [3];
3. fractions of references 7'7;

4. rank-deficiency 77 = dim(Ker(H)).

In Figure 2.2, for each fixed 71, a black and gray curve DFR = f (1 +7) shows the

decoding failure rate (DFR) of codes under the S-MLDA and the MPA, respectively.

64

 

Decoding Failure Rate of LT codes by the S-MLDA and MPA

0.5

 

2000

  

 

 

 

 

 

 

1.2 10000 8000 n : block length
by the S-MLDA
=5,000 — by the MPA
1 1 r ' I I I I I . .
0.8 1
a: 0.6 _
u_ .
D o_4 . ............................................... _.
0.2— .. 2
0’ ; ; ' 1 1 1 . 1
1 1.02 1.04 1.06 1.08 1.1 1.12 1.14 1.16 1.18 1.2

1+1

 

 

 

Figure 2.2. Performances of LT Codes in Decoding Failure Rates (DFR) (under the S-
MLDA (black curves 1) and the MPA (gray curves 2). The codes are generated by the p(l‘)
in Table 2.1 over the block lengths from -n = 1,000 to 10,000

For examples, when n = 5, 000 and 1+7 = 1.01 with 100 trials of code constructions
(see the bottom figure in Figure 2.2), the gray point (1.01, 1) indicates that the MPA
never succeeds for the recovery of a, in contrast. the black point (1.01.0) indicates
that the S-MLDA never fails to recover a. We observe that, for any 1 + 7 > 1.007,
the DFR by the S-MLDA is 0. Even if 1 5 1+7 S 1.007, our simulations also exhibit

that Rank(H) 2 n — 12 (see the bottom figure in Figure 2.5). Therefore, a small

65

 

 

Number of Symbol Additlons by the Post-Decodlng and the MLDA

NS : Num. of Symbol Add.

  
    
    

9

      

1N3§§§§

o 7000 8000 9000 10000

600
1+y:0verhead 12 1000 2000 3000 4°00 5°00

 

_ — 1 by the S-MLDA

n ' BIOCk Length — 2 by the Original MLDA
3 by theiRedundant Rows
4 d' = [A —2 1111/71

 

 

 

 

n=5.000

 

 

1 1.02 1.04 1.06 1.08 1.1 1.12 1.14 1.16 1.18 1.2
1+7

 

 

Figure 2.3. Number of Symbol Additions by the Post-Decoding and the MLDA in [3]

increment in p")? (or 7) based on the inequality (2.4.17) or the rank—distribution
(2.5.15) may increase Pr(Rank(H) = 71) very close to 1. Also notice that, by the
MPA, DF R > 0 for any 1 + 7 < 1.08 and 71. Therefore, the desirable 7 for the
successful decoding of codes by the MPA should be greater than 0.08.

In Figure 2.3, for each fixed 71, a. black and gray curve 1 and 2 represents the
number of symbol additions divided by n, denoted as NS, made from the post-decoding

and the original MLDA in [3]. respectively. Similarly, the black and gray curve 3 and

66

4 indicates the NS made by the redundant equations HiXT = B,- whose index 2'
is in ’2' \ or and by the d* = |H| — 22:1 dil/n, as shown in p. 52, reSpectively.
(Recall the alternative recovery and the removal of redundant rows in section 2.1).
When n. = 5, 000 and 1 + 7 z 1.01, for examples, the point (101,12) on the black
curve indicates that, approxin‘iately, 12 - 5, 000 symbol additions is made by the post-
decoding, and the point (1.01, 39) on the gray curve corresponds to 39 - 5, 000 symbol
additions made by the original MLDA in [3]. Similarly, the black point (1.01, 15) on
the curve 3 and the gray point (1.01, 11) on the curve 4 corresponds to 15 - 5, 000 and
(HI — d) = 11 - 5, 000 redundant symbol additions, respectively. It can be observed
that the black curve 1 is mainly contributed by sparse fractions of degree d in D1 U’Dg,
however, the gray curve 2 is mainly contributed by the dense fraction pn/2 = 0.005
and IAII. From the figure, observe that the gray curve 2 is much larger than the black
curve 1.

In Figure 2.4, for each fixed block length n, a black curve shows the fraction of
references (FR), F R 2 %, where r is the column dimension of H7; (or [ él). When
n = 5,000 and 1 + 7' = 1.01, for instance, the point (1.01,0.025) indicates that the
C‘ in systen’i (2.1.3) has its matrix dimension about 150 x 125 which is very small
compared to the matrix dimension of H, 5,050 x 5, 000. Notice that for any 7 and
72, FR 3 0.041 that. substantiates the very small constant factor in the complexity of
the GE on (_7 (see also [3, p. 4]). (To see the lower complexity, compute the upper
bounds (2.3.3) and (2.3.4) with r = 004171).

In Figure 2.5, each curve represents the rank—deficiency r) = dim(Ker(H)), or
the number of free variables under the S-MLDA. For an example, when n = 5,000
(see the bottom figure in Figure 2.5), the point (1 + '7 = 1,7] = 11) indicates that
the S-MLDA fails to recover a with DFR = 1 (see the bottom figure in Figure 2.2)
and the rank deficiency is approximately 11. Even when 1} > 0, the GE on ER (or

C) identifies the all the free variables, and thus, a is obtainable by retransmitting the

67

 

Number of Reference Variables for 1,0003 n 5 10,000

0.02 .
0.01
0
1
1.05
1.1
1+7: Overhead 1,15

200
8000 7000 6000 5000 4000 3000
0

FR : Fraction of References
0
O
u

    

o 1000

1.2

 

 

 

 

 

 

 

10000 900 n : Block Length

$5,000 RF=(Number of References)/n

01,3 . ., ...... ~ ....... '..,..,.. ...... ...... ...... _

0.02- . :.. . . ,_ ..... ...... ...._
n: . . . .

IL . .
. ._.?l.. . , _
o J 1 AL 1 1 l l
1 1.02 1.04 1.06 1.08 1.1 1.12 1.14 1.16 1.18 1.2

1n

 

 

 

Figure 2.4. Fraction of References

input symbols of free variables only.

Figure 2.6 shows how the dense fraction pn/Q = 0.005 gracefully improves the
DFR of the S—MLDA to 0 with Pr(Rank(H) = n) close to 1. In the bottom figure,
a black curve shows the DF R of the S-MLDA on H, generated by p(rc). Similarly,
the gray curve shows the DFR of the S-MLDA on H, generated by pplupzfic). In
both cases, pd‘s are taken from Table 2.1. For the simulation, starting from m := n

to m :: (1.2)72. a row dimension m is increased by 1, and for each matrix dimension

68

 

Rank Deficiency of LT codes for 1,0005 n S 10,000

11 : Rank Deficiency

1.02 6000 7000 3000 9000 1°°°°
5000
1+y:Overhead 1000 2000 3°00 400° n:B|ock Length

n=5,ooo Rank Deficiency

 

 

'l"""' I

20 '-

  

 

 

   

l i

0.995 1 1.005 1.01 1.015 1.02 1.025

 

 

 

 

Figure 2.5. The Rank-Deficiency 7} : dim(Ker(H)) (or the Number of Free Variables)

m x n, an m x n matrix H is generated 1000 times. Then the S—MLDA is tested
for each instance of H and 0 7E 0. When H is constructed by pplUD2 (see the gray
curves). although the DFR and r] is small, rank-deficient cases occur constantly up
to 1 + '7' : 1.1, then sporadically as 1 + 7 increases to 1.2. Contrastingly, when H
is supplemented with pn/2 = 0.005, the small deficiencies are gracefully removed (i.e.
7; : 0) up to 1 + 7 g 1008 (see the black curves). From the bottom figure, observe

that the DF R of of the S—MLDA around 1 + '7' = 1.0076 decreases to 0 dramatically

69

 

 

 

 

 

 

 

 

 

 

Rank Deficiency of LT codes for n=5, 000
3 3 . . . , . , . . .. . .
.3; 25 .. ..... ........ —bypmuoz(")
; i.§byp<xi
a, 2 ....... *. ., . . ....... 3 ...................... _‘
E ‘ . . . : .
Ll. ’ ' ' l f I
I. , .
s - : ~
E I 'lli . .
3
.. i ll,
‘ oi. .. liliiil H l l
1.06108 11 112 1.141.16 1.18 1.2
1+y:0verhead

2
& Decoding Failure Rate of LT codes for n=5, 000
0.1 .
i
'6
u.
01
.E
‘5
o
0
d.)
n
0:
LI...
0 . ,

1.02 1.04 1.06 1.08 1.1 1.12 1.14 1.16 1.18 1.2

1+7:Overhead

 

 

 

Figure 2.6. Rank Deficiency (top figure) and DFR (bottom figure) of LT codes of n =
5,000, generated by p(:1:) and p‘pwp,

by a slight increment on 'y.

2.7 LT Codes of Short Block Lengths From an Arranged En-

coder Matrix

In this section, we present performances of LT codes of short block lengths n, 102 g

n S 103. For higher Pr(Rank(H) = n), we design LT codes with the larger dense

70

fraction Pn/2 = 0.082. Particularly, we substantiate that, under the S-MLDA, LT
codes generated by an arranged encoder matrix [if can achieve a stable overhead '7
for the successful S-MLDA close to 0, while the S-MLDA maintains its complexity of
decoding in symbol additions within few tens of n.

W’hen H is designed by the RSD with short block lengths n within several hun-
dreds, we (the author Ki—Moon Lee and Hayder Radha) observed that the nonzero
rank deficiency r) = Ker(H) is feasibly happened but is less than a few. A small
deficiency r} can be removed by using the pre—eoding strategies as in Raptor codes
[14] but with a small degradation in overheads 'y. In contrast, supplementing dense
fractions in u(.r) can increase Pr(Rank(H) = n) rapidly without extra costs in ’y.

In the earlier work in section 2.6, we designed LT codes with dense rows that fit
for the block lengths n, 103 S n g 104, under the S-MDLA. Particularly, a very
small dense fraction p.,,/2 = 0.005 was supplemented to p.(a:), and a stable 7 for
the successful S-MLDA was less than 0.01 for n a few thousands. With shorter block
lengths n in several hundreds, however, it seems to us that much larger pn/Z is required
for a stable '7'. In this section, we design a distribution p(:r) with pn/2 = 0.082.

Dense rows may cause a nontrivial drawback in communicating H to a decoder.
Note that. for every instance of at, a decoder should identify H by using the same
ramloni generator of an encoder. Otherwise, each H, should be directly delivered to
a receiver attached on syndrome symbols of 1’3. In both cases, due to dense rows,
the cost in communicating H may not be trivial. Dense rows may also degrade the
computational efficiency of the MLDA in [3] seriously. Nonetheless, even with the
7 very close to O, H can be approximate lower triangulated by the ALTA in [3,4].
Furthermore, most of the dense rows become redundant. Therefore, those redundant
rows should be identified so that symbol additions over the redundant rows can be
removed by the S-MLDA.

In this section, we design LT codes for short block lengths n in two perspectives.

71

First, we alter a designed RSD ,u(:r) into a p(:r) = Zpdxd by supplementing a dense
fraction pn/Q for the higher Pr(Rank(H) = n). Thus, even for short block lengths n
and 7 close to 0, a check matrix H of system (2.1.1) may have its full column rank n
with high probability. Second, to communicate H to a decoder efficiently, we use a
(kn) x n. encoder matrix M over F; whose row-degree distribution follows a designed
p(;r). Therefore (at a receiver end), an LT decoder can quickly identify H by reading
rows of M without extra cost in communicating H to a decoder.

In this encoding scheme, however, a row-degree distributions of H may be devi-
ated from the designed p(;r), the distribution of the encoder M, seriously. Therefore,
the random features of the original encoding scheme should be limited. In particu-
lar, a stable overhead 7 of codes for the successful MPA may be degraded seriously.
Nonetheless, our simulation exhibits that the degradation does not affect the perfor-
mance in 7 under the S-lV‘ILDA. (Compare the black and gray curves in Figure 2.7).
Due to the fixed ill, the fixed block—length 71. could be also a drawback to the flexibil-
ity of block lengths 77.. However, if changes in n are not so severe, then this constraint
can be negotiated by using shortening techniques with null symbols on a and resizing
the symbol—size s.

In this section, focusing on LT codes generated by an arranged encoder matrix
M , we simulate LT codes of 10 block lengths n from n = 100 to 1000 in the following

spectrum. First, we construct a row-degree distribution [)(35) in the following way:
1. A MI) in (2.4.6) is generated with S = 15 and n = 103.
2. Then fractions of p(.’L‘) in (2.4.16) are given as:

(a) fld = “d where (16 D1 = {1,2, . - - 320} (for pd, See Table 2.1 at P. 64);
(b) P60 = 0.02 with D2 : {60};

(c) pn/Q = 0.082.
3. Then p(.1:) is normalized as [)(17) = p(:r)/p(0).

72

Second, we arrange a (571) X n. encoder matrix M’ by using PEG algorithm [13] with

the row-degree distribution [)(r). Then an m x 77. matrix H is generated in two ways:
E1) Rows of H are chosen in random from M.

E2) Rows of H are randomly generated by ,5(-.r) using Mersenne Twister Algorithm

[16] on [n].

Then a syndrome symbol 13,: is generated by 13,- = H,- -o-T and transmitted over BEC.

In both encoding schemes E1 and E2, for each fixed 77.:
I. the row dimension m is increased by 1 from m 2: 71 up to m := (1.3)n;
2. for each matrix dimension m X 71, an m x 71 matrix H is constructed 1, 000 times;
3. for each instance of H and a 74 0, the S-MLDA is tested.

Let us now present and compare their dew and computational complexities based on
our extensive simulation results.

In Figure 2.7, for each fixed n, a black curve 1 and a gray curve 2 represent the
DFR of codes by the S—MLDA and the MPA, respectively, on H constructed by El.
Similarly, a black curve 3 and a gray curve 4 are the DF R made by the S-MLDA and
the MPA, respectively, on H constructed by E2. When n = 500 and 1 + 7 = 1.02
in the bottom figure, for an example, the point (1.02, 1) on the gray curves 2 and 4
indicates that the MPA never succeeds for the recovery of a. In contrast, the point
(1.02, 0) on the black curves 1 and 3 indicates that the S-MLDA never fails for the
recovery of a with 1, 000 constructions of H. It can be observed that, for each n, the
DFR. of the S-MLDA on H, generated by E1, is slightly better than the DFR of the
S-MLDA on H, generated by E2. In contrast, as 1 + 7 grows to 1.3, the DF R of the
MPA on H, generated by E2, is better than the DFR on H, generated by El. This
substantiates that, under the S—MLDA, LT codes by an arranged encoder matrix 1W

can also achieve the performance in 7 for the successful S—MLDA close to 0, when A!

73

 

Decoding Failure Rate of LT codes for 1003 n S 1,000

DFR : Decoding Failure Rate

   

 

 

 

 

 

 

     

 

 

 

1+7: Overhead ’ 30°
. — 1 by the s—MLDA with E1
" ' Bl°°k “"9“ — 2 by the MPA with E1
3 by the S-MLDA with E2
n=500 —— 4 b the MPA with E2
1 , , , ..re,....rfi..,...--...
0.8 ..............................
n: 0.6
‘3 0.4
0.2 .........
o , I l l l l
1 1.05 11 115 12 1.25 13

 

 

 

Figure 2.7. Performances in Decoding Error Rates under the S—MLDA and the MPA

is supplemented with a small fraction of dense rows. However, the performance 7 for
the successful MPA may be degraded seriously.
In Figure 2.8, for each fixed 77., each curve represents the number of symbol

additions divided by n, denoted as NS in the figure, by the S—MLDA and the MLDA:

1. A black curve 1 represents the NS made by the post-decoding step of the S—
MLDA;

2. A gray curve 2 is the NS made by the original MLDA in [3];

74

 

Number of Symbol Addition of LT codes for 1005 n g 1,000 based on E1

NS : Num. of Sym. Add.

   

1+7: Overhead

 

— 1 by the S-IV’ILDA
— 2 by original MLDA

 

3 by Redundant Rows
4 d' =HAI {Edi/n

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 2.8. Number of Symbol Additions made by the post-decoding and the original
MLDA based on the encoding scheme E1

3. A black curve 3 is the NS made from redundant rows (recall the removal of all
redundant rows in the pre—decoding):

4. Lastly, a gray curve 4 shows the NS by the difference d* = “M (recall the

11

alternative recovery in section 2.3).

When n = 500 and 1 + 7 = 1.15 (see the bottom figure), for an example, the point

(1 + 7 = 115,713 2 7) on the black curve 1 and the gray point (115,35) on the

75

 

Fraction of References for 100 s n g 1,000

FR : Fraction of References

  

‘I
100
600 500 4“ 3°” 20°
n : Block Length

 
 

.fl'"
1000 900 80° 70°

 

 

FR=(Number of Columns of C)ln]

 

n=500

 

006_H. ., ..._ . f ........ ;. H.._.. ,1 .H.. .3 ........ _

 

 

 

i i I
1 1.05 1.1 1.15 1.2 1.25 1.3
1+7

 

 

 

Figure 2.9. Fraction of References based on the Encoding Scheme E1

gray curve 2 indicates that about 7 . 500 and 35 - 500 symbol additions is made by
the post-decoding and by the original MLDA, respectively. As 7 grows, the NS by
the post-decoding step is mainly contributed by the sparse fractions of fi($) and a few
dense rows of degree 772‘. Observe that, for any instance of II and 7, the NS by the post-
decoding is less than 17. In contrast, the NS by the original MLDA is mainly come
from the dense fraction fin/Q. Due to the dense fractions, notice that, as 71 increases,

the NS by the redundant rows (the black curves 3) far exceeds the NS made by the

76

 

Number of Free Variables for 1005 n g 1,000

40

20

n : Number of Free Variables

    
 

1

1+7 : Overhead 1000

800

 

 

 

 

 

 

 

600
400 n : Block Length

n=500 n = dim (Ker(H))
25 W,, ....... ,.... ., ...... F , ,. , ..... , ......
203, ..... i ...... ....... E ...... , ....... ....... _
15- ................................................ _.

g:- .

10-. ............................................................. _
5- ................................................. _
o . i a i I I .
0.95 0.96 0.97 0.98 0.99 1 1.01 1.02 1.03 1.04 1.05

1+7

 

 

 

Figure 2.10. Number of Bee Variables based on the Encoding Scheme E1

post—decoding.

In Figure 2.9, for each fixed 11, a black curve indicates the fraction of references,
denoted as FR in the fingure, FR 2 7:. When n = 500 and 1 + 7 = 1.1, for instance,
the point (1 +7 2 1.1, rf 2 0.04) says that (7 has its matrix dimension about 20 x 70
that is much smaller than 550 x 500, the dimension of H. It can be seen that, for
any instance of 1 + 7 and 72, FR g 0.12. Thus, the performance of the GE on C’ in

computational complexity is actually very efficient.

77

In Figure 2.10, for each fixed 71, a black curve 77 represents the number of free
variables under the S-MLDA. For an example, when n = 500, the point (1 + 7 =
1, 'r} : 1.7) (see the bottom figure in Figure 2.10) says that the deficiency in rank is
approximately 1.7. From the figure, even the case when m < n, it should be noticed
that 77 S (n — m) + 3. We recall that, if 77 > 0, the GE on 6 identifies the 77 free

variables, and thus, a is obtainable by retransmitting symbols of free variables only.

2.8 Conclusions

In section 2.2, we introduce the S—MLDA as an advanced form of the MLDA in [3].
In section 2.3, we then estimate the complexity of the S-MLDA which is very efficient
compared to the original MLDA. In section 2.4, we present a simple design of LT
degree distributions with a small fraction of dense rows. We then demonstrate rank
properties of a random H (including Kovalenko’s rank-distribution), generated by
our designed row-degree distribution p(r). Simulation results in terms of code per-
formances in both stable overheads 7 and number of symbol additions are presented
in section 2.6. Through the simulation, we provide the evidences that LT codes of
block lengths n. from n = 1,000 to 10,000 can achieve stable overhead '7 for the
successful S-MLDA very close to 0, while the S-MLDA maintains its computational
complexity in symbol addition within few tens of n. Lastly, in section 2.7, we also
present experimental evidences which substantiate that, for short block lengths n,
100 g n S 1, 000, LT codes from an arranged encoder matrix .M can also achieve
performance in 7 close to 0, when M is supplemented with small fraction of dense

TOW-"S.

78

CHAPTER 3

The Maximum-Likelihood Decoding
Algorithms of LDPC Codes

In this chapter, the same S—MLDA developed for LT codes in section 2.2 is applied
for the decoding of BBC based LDPC codes. Clear improvements based on the S-
MLDA over current LDPC decoding algorithms is demonstrated. We also present
experimental results which demonstrate that, under the S-MLDA, LDPC codes can
achieve performance in erasure rate p (for the successful] S-MLDA) very close to
0, while the algorithm maintains the computational complexity in symbol additions

within few tens of block lengths n.

3.1 Introduction and Backgrounds

T).'1)irrai.lly in BBC based LDPC codes, as defined in Definition 1.3.1, an LDPC code

C(H) is the kernel space
Ker(H) = {a e (1F§)”|H-ozT = 0}, (3.1.1)

where H is an m x 72. matrix over IFQ. In general, for any given a] E (1%)!“ , a codeword
a is generated in a systematic form a = (0;; 0}?) such that 0}) = Lglmemxkagl as
shown in (1.3.4). \Vhen a is transmitted over a BBC, the overall codeword vector

0 is expressed as a = (ti-g, a6) where Olé and (re represents the received and the lost

79

part of a, respectixely. Let 716 and 71g denote the number of symbols of 0'6 and (15,
respectively, and let X 2 ac. Associating the columns of H with the expression
(aaX), let [N ; M ] be the rearrangement of H. Then the kernel space constraint

H GT 2 0 is now expressed as the consistent linear system
MXT 2 HT where HT = Na? (3.1.2)

Obviously, the system has the unique solution 016 iff. Rank(A/I) = 77.8.

W'hen H is designed with a good degree sequence, for examples the sequences in
[4,13]. then the unique solution of the system (3.1.2) can be solved by the MPA [5]
For short block lengths n, however, the successful triangulation of M by the MPA is
not guaranteed as the erasure rate p = 7.3; approaches to the ideal limit 1 — R = 7%},
where R 2 £7 and m = n — 1:. (See the DFR of codes by the MPA in Figure 3.1).

Once the initial system (3.1.2) is identified, the problem of solving the system is
same as the one of solving the system (2.1.1) of decoding LT codes, except that the
M in (3.1.2) consists of columns of H in (3.1.1) and ,8 is formed by fiT = NozéT.
Therefore, replacing the LT check matrix H in system (2.1.1) with M, the ALTA
designed for the H is directly applicable to the M in system (3.1.2). After the ALTA
on M, replacing HQT = [HRiHRl in system (2.1.6) with MQT = [MRiMle and
applying the same BSR and GE developed in section 2.2, the S-MLDA system (2.1.6)

for LT codes can be modeled for the decoding of LDPC codes as following

(ZE’YlS-[MmMRWTz(ZU)_IS-,BT. is» (2.1.6) (3.1.3)

Based on the MLDA [3] and the system (3.1.3), the same pas-decoding and post-
decodmg step developed in section 2.1 and section 2.2 are directly applicable for
solving system (3.1.3).

Although the S—MLDA for both LT and LDPC codes are almost same, the contri-

butions to the efficiency in number of symbol additions by the pre- and post-decoding

80

are quite different. In LT codes, the improvement in symbol additions with 13 con-
tributed by the step 1b) of the lire-decoding (or the removal of redundant equations)
is significant, because most of dense rows become null after the CE. On the other
hand, the improvement by the alternative recovery in step 2c) is relatively small,
because the fraction of reference % is quite small. In LDPC codes, contrastingly, the
removal of redundant equations by the step 1b) is less significant than the one for
LT codes, because, in general, the M in system (3.1.2) has no dense rows. On the
other hand, due to the large reference fractions % (or the number of columns of [ g]
in system (2.1.2)), lel is much larger than (Al + IBI. Therefore, in LDPC codes,
the alternative recovery by the step 2c) is indispensable for the efficiency of the post-
decoding. The serious degradation of the efficiency in symbol additions when 231 alone
is used for the F FS is presented in Figure 3.2.

Another significant difference between LT and LDPC codes is in the time-efficiency
of the initialization step of the S-MLDA. In LDPC codes, a fixed H is used for ev-
ery instance of a, and thus, the decoder can quickly setup the initial system (3.1.2)
by reading the columns of H. In contrast, based on the original LT transmission
scheme, for every instance of a received encoding symbol vector 5, rows of H should
be generated by using the same random generator of an encoder to setup the sys-
tem (2.1.1). This random generation of H, as a matter of fact, results in a nontrivial
drawback to the time-efficiency of the S-MLDA. Otherwise, rows of H should be
transmitted to receivers attached on syndrome symbols of ,3 that requires nontrivial
costs in symboLsize.

In LDPC codes, particularly when H in (3.1.1) is designed with capacity ap-
proaching degree sequences, for an example the tornado sequence in [5], the a stable
erasure rate p = "—7,? for the successful S-MLDA is very close to the ideal limit 3%. This
implies that, with high probability, the S-MLDA can recover the lost symbol vector

X = 06 as long as it acquires more than (1 — 1))71 symbols which is very close to k,

81

4

|>~

the number of symbols of the information part (1]. Due to the fixed code rate R = ,

:3

however, the number of symbols of a systematic part a I is constrained by a fixed k.
Thus. depending on the size of source data I, say III, the fixed code rate R could be a
serious drawback in LDPC codes based transmission scheme. Nonetheless, assuming
that a symbol size 5 is flexible to choose, this rate constraint can be negotiated by
selecting an appropriate syn‘ibol-size 5. For an example, 3 can be chosen by s z l-zi—l.
Then the rate constraint may be further improved, if necessary, by plugging in null
symbols into a systematic part a 1, called shortening codes.

The remainder of the chapter is focused on the following subjects. In section 3.2,
using the same arguments of the S—MLDA for LT codes developed in section 2.2, we
derive the S—iVlLDA system (3.1.3) for the decoding of LDPC codes. In this section,
we also provide exemplary pseudo-codes for routines of the S-MLDA. In section 3.3,
with the same manners in section 2.3, we estimate the computational complexities
of the S-MLDA with respect to the number of {sign, bit}-fiips and symbol additions
made by the pre- and post-decoding step, respectively. We also compare the number
of symbol additions made by the post-decoding step and the original MLDA in [3].
In section 3.4, we present the simulation results tested with air-rate PEG codes [13]
under the S—MLDA for 10 block lengths n from n = 2,000 to 20,000 by 2, 000, for

the performances of codes for the following scenarios:

H

. the perforn'iances of the S—MLDA and the MPA in decoding failure rate;
2. the complexity of the post—decoding in symbol additions;

3. the fraction of references % to tell the complexity of the GE on C;

4. the rank-deficiencies 77 = dim(Ker(Al)).

We then summarize the chapter in section 3.5.

82

3.2 The S-MLDA Design with LDPC Codes

In this section, the S-MLDA system (3.1.3) is clarified in detail for the decoding of
LDPC codes. For each routine of the S-MLDA, an exemplary pseudo-code is also
provided. Corresponding to the expression (Org,X) in system (3.1.2), we denote E
and 5— as the index set of X and (15,, respectively. Thus, the M’ in system (3.1.2) has
the row index set [m] and the column index set 8. For other notations used in this
section, see the first paragraph in section 2.2.

By the ALTA on M , first of all, a set of successive pairs in [m] x 8 is obtained for

the triangular block B such that.

(01171) = (NJ-H1) s > (izajwz): 7‘ = 71 — 1- (3-2-1)

)th entry of B can be identified

Then for each index pair (s,t) E a) x T), the (s,t
by reading the (13, jr+t)m entry of H. An exemplary pseudo-code for the ALTA is
described in Algorithm 3.1. In the algorithm, we design the ALTA as the iteration
between the sub-routines MPA() and Referencing() that accompany Sign-Flip().
In the algorithm, whenever the triangulation of B by the MPA() stops prematurely,
a column that is not joined into [1%] nor [9.] by that round, is chosen and declared
to be a column of [ g] by ReferencingO. The triangulation of B proceeds in this
fashion, untill all columns of M are joined into either [6] or [5]. Many other
strategies for ReferencingO can be found in [3,4].

With the returned (01,71) from the ALTA (see line 9 in the algorithm), let 5 =

(R, 7?) and [m] = (T, ’7') the disjoint pair of [m] and 8, respectively, such that

R:£\Tl:{j1’"'3j7‘}i RZTl:{j7-+1,...,jr+[}, (3'22)

’T = 01 = {11,...,i1}, T = [m] \‘71 = {'fl+1: . . . ,im}. (3.2.3)

By extending the (01,71) into a row and column permutation pair (0, T) of A"! such

83

 

Algorithm 3.1: The ALTA on M

 

 

1

10
11
12
13
14
15
16

17

18
19
2O
21
22

23
24
25
26
27
28
29

Input: H and (5,8) Output: (01,71)

/%<—- Initialization: -—>%/
foreach j E 5 do
L Sign-Flip() with Hi;

/%<-- Triangulation: —->%/
while 8 # 0) do

if 91 = Q) then

L Referencing();

else
|_ MPA();

 

return (Jpn); Exit the Algorithm;

/%<—- Sub Routines: -->%/
MPA():
while ‘11 aé (0 do
foreach (z',j) E 91; do
if j E 8 then
reduce 8 2: 8 \j;
Sign-Flip() with Hi;
update (01,71)I=(017T1)U(i,j);

reduce 93 z: 93\ (1,3);

 

_-

 

L»

Referencing();

choose an H, such that [H.il = min{|HS| > 0};

while |Hi| > 1 do

L choose a j such that 113:6 Hi;
Sign-Flip() with H];

Sign-Flipf):
foreach 1,;j E Hj do
flip sign(1,-j) :: —1;
reduce |H,| :: |H,-| — 1;
if |H,-| =1 then
find the (5,75) such that 15¢ E H, and sign(1st) : 1;
L update 91:: ZRU (3,15);

 

—

 

84

 

that.

a : [m] 1—> [771], 0(2).) 2 k, and T : E r—> E, T(jk) = 1:, (3.2.4)

the permutation matrix P and QT of (a, T) can be formed by permuting rows of Imxm
and columns of Inexne in the order of a and T, respectively. Let M 2 PM QT 2

[El B] as shown in Figure 2.1-(a). Then for each (s, t) E [m] x8, the (s, t)th element

X-

_ _ XT
of 111 is exactly the (3,9,jt)th element of H in (3.1.1). Let XT = QTXT = i: 7%]
R

where

X73 2 [my-1,” .,;rj,.] and X72 2 [ (3.2.5)

IIIJ'7_+1,. . . ’xjr+l]°
Then by QT 2 (2‘1, similar to system (2.1.2), system Ply! X T = PBT is interpreted
asith=:PsT.

Let us now rearrange columns of M QT, as in the order of (R, R), into two parts

AhzmmmflWaMAhzwmkwflmfl QM)

Then by using 5’1 : [g 9] which is in a lower triangular form, 5' can be factorized

into a product form of elementary matrices such that
1
S = H 505) = 5(l)5(l—1) . . . 5133(1), (3.2.7)
k=l

where each S (k) is formed by replacing the column (Imxm)k with the km column Mk
and l is the number of columns of the triangular block B. (See equation (1.2.23) at

p. 19). With the product form (3.2.7), SM can be computed by the iteration
1L=SWML kzrauqt 62$

Because the S—IV‘ILDA does not construct the permuted N1 2 [El 1%] explicitly, the
product form (3.2.7) should be interpreted appropriately via (P, Q) into an equivalent
form. With the same way for (2.2.11), let S = PTSP and let Bu“) 2 PTS(k)P,

k 2: 1,2... ,1, formed by replacing the column (Imx.,,,)ik with the column HJTHC.

85

 

Algorithm 3.2: The BSR on 11173 by 11,11,213“) - AIR
1 Input : AIR Output : i’l—IR

 

2 foreach ('ik,j,.+k) E (01,71) as in the order do
/7.<—- NR ;= 3(A‘JMR -—>7,/

3 foreach liefr+k E HJI‘HC, 2i 729 '27), do

4 Ladd (MR), ::(il[R)z-+(A1)ik;

5 return MR; // <—— .1773

 

 

 

Then (3.2.7) is now transformed to
_ 1 l
s = PTSP = H PTs<k>P = II SW (3.2.9)
k=l k=l
Consequently, similar to the one in system (2.1.3), the BSR system SMXT = PfiT

is now transformed to

1 1 1
[(11 SW) M72; (H SW) MR] XT = (H 3‘“) 5T 4: (2.1.3). (3.2.10)
k=l k=l k=l

Let N17; 2 521173 and ill-IR 2 52117-2. Notice that, since 11772 = PT[6], the computation

of 112173 is enough to set up system (3.2.10) and is accomplished by the iteration
MR 2: SWUR, k =1,2,...,1. (3.2.11)

An eernI.)lary pseudo—code for the BSR iteration (3.2.11) is described in Algo-
rithm 3.2. For the GE on 212173 later, we assume that AIR is constructed explicitly

in a ternary format {—1,0, 1}.

Note that the S-MLDA does not construct the 5.1—! = [El—,6

Therefore, the. GE on (_7 should be designed to perform the pivoting processes on the

] of system (2.1.3).

set of rows {(;1_IR).,-|i E T}, which is equivalent to 5' via. P. At the end, the GE

returns an updated MR that consists of {—1, 1,0} with a set of successive pairs

(0,37%) =(51,t1) >- - ° ' > (Sr,t7~) C T X R. (3.2.12)

86

 

Algorithm 3.3: The GE on [1773 with 2' and R

 

 

1 Inputzhle, T, and R. Outputth'IR and (0r,T7~).
/%<—- Initialization: ——>%/
2 foreach iE 7' do
3 if (1177;),- = 0 then
4 L discard 7'2: 7'\2T;
/%<-- General Rounds: -->%/
5 while 7’ ¢ (2) do
/%<-— Pivot Selection: -->%/
6 choose 35k E T such that KMRMSk = n1i118€7{|i’\73|};
8 insert (07-,77.) :2 (or, T,-) U (sk,tk);
/%<—- Pivoting: ——>%/
9 foreach 2' E 7' such that ('ITLRL'Jk = 1 do
10 flip li’tk into '—1zf‘tk;
11 add (MR), ;= (MR),+(ATIR),k;
12 if “Nikki = 0 then
13 L discard ’17" :2 7—"\z'; //<-- To discard null rows
/%<-- Discarding: -->%/
14 _ discard T:=’]_'\sk;

 

 

 

15 return (0r,T,-) and N173;

 

)t‘h entry

After the GE, an entry 1sz- of L or ul-j of U can be identified from the (3.2:, t]-
of the My; where .92- E or and t j E Tr. While computing X7; by the FS over rows of
L then the BS over rows of U in system (2.1.6), each 1k,j of L0“) or UU‘) corresponds
to the symbol addition (5331);: := ((31);; + (131)) Let 3T 2 SfiT. This addition should
be interpreted as the symbol addition on 3T 2 513T with A7173 by looking at (or, Tr)
as in the following way. Each 1’6} of LU‘) or UU“) is recoded as the —13kitj or 15“].
in (fink/,6, respectively. Therefore, the -13h‘tj or 1'9k‘tj corresponds to the symbol
addition 8% 2: (35k + 33]. via 8k, sj in or, and tj in Tr. In this way, lel and U(k)

can be ii’iterpreted as LU“) and U (k), which is the m x m elementary matrix formed

by replacing those —15k‘tj and 15st] as the lgk‘sj in the row (I.,-nxm)3k, respectively.

87

Therefore, the GE on 11773 is equivalent to the factorization
1 7‘
F1 = H W), 0‘1 = H 0“), (3.2.13)
k=r k=1

where r is the number of columns of M73. Consequently, multiplying the product
form (3.2.13) into the BSR system (3.2.10) verifies the S-MLDA system (3.1.3). An
exemplary pseudo-code for the GE on [HR is described in Algorithm 3.3. For the
recovery of X73, initializing by .rtk :2 133k for each (sk,tk) E (ann) in advance
replaces the symbol addition '33}.- := 85k + .st into xtk :2 :rtk + mt]. (see FS/BS in
Algorithm 3.4).

Let us now go back to the GE to remove redundant symbol additions in sys-
tem (3.1.3). It can be observed that, for each i E T \ or, the row (MR),- is nullified
by the GE on 1177;, and thus, any symbol additions made with the syndrome symbol
,3,- is completely redundant. These redundant symbol additions can be removed by
discarding the equations Ail-X7“ = 52‘ in system (3.1.2) for all 2' E T \ or by the
step 1b) of the pre-decodz'ng. In LDPC codes, since rows of H are sparse, these re-
dundant additions may not be a serious drawback to the efficiency of the S—MLDA.
In LT codes, however, a small fraction of dense rows in H is required to ensure that
IHJI 2 1 for all j E [n], and most of them become redundant after the GE on HR
(see [19, p.41] and [27, fix-50.5)). Therefore, ahead of the post-decoding, removal of the
redundant equations is essential for the efficiency of the S-MLDA for LT codes. The
computation of GAL—138T is described in Algorithm 3.4. Note that, if R = 0,
then the lost symbol vector X is simply recovered by the BSR iteration [3T 2: SST
as in Algorithm 3.4.

In the alternative recovery by (2.1.7), it can be seen that, for each 27;: E 01, Mik-
and (Mth corresponds to (Ak,Bk) and Ak, respectively. Hence, by looking at
(ibjk) E (01, 7'1), each 3311.- of X72, in the order of T1, is recovered by either MikX% 2
"Bi/.- + (A‘IRlikX7Tz or by 3er = 13,-); + (11717;),kX7g. The 117173 (or 21) returned from

4

88

 

Algorithm 3.4: The computation of U‘lfflgw 'flT
1 Input: a5 Output: 5, B, XR.

/Z<-- Initialization: ——>%/
2 foreach i E a) U orT do
3 Lset )3,- :: N,- $01 ;—//< recall 8T: Nag

4 copy ,3,- .= 13,; /-/< for the alternative recovery

/'/.<—— ST :2 S . 3T: ——>'/./
5 foreach (1k.j,.+k) E 01 X r; as in the order do
/'/.<—— 3123(1) 337': —->'/./

6 foreach 1 eHj7‘+k '1‘ 7é i], do

ZJ +1.
7 Ladd ~_,3,+3,k;
/%<-- Initialization: -—>%/

s foreach (Sic-tic) E (073,77) as in the order do
9 LCOPY Ifk :: 135k;

/°/.<—— FS by L 1— UL TL ‘ )——>°/./
10 foreach (3k tk)E (,(or Tr) as in the order do
/'/.<—- BT-— — L W" -—>'/./
11 foreach “1315]. E (1173)”; do
12 Ladd rtk 1=1€tk+$j;

//.<-— BS by (3'2—1 [1,; 113(k) ——>7./
13 foreach (.sk.tk)E (o V77) as m the reversed order do
/'/.<-- .3T-— _ W >3T -—>°/./
14 foreach 13!;1 E MIR)“, 3' 7é tk do
15 Ladd Itk :=rtk+1‘j;

 

16 return .3, i3. and XR;

 

 

the BSR is not sparse in general. The top part of A is more likely sparser than the

top part of (A; B]. On the other hand, the bottom part of A is much denser than

the bottom part of [A; B]. Therefore, selecting a sparser equation by comparing the

degrees lMikl and (11],-kl may improve the efficiency of the S—MLDA in number of

symbol additions significantly. An exemplary algorithm for the FFS is described in

Algorithm 3.5. The overall S—MLDA is summarized in Algorithm 3.6.

89

 

Algorithm 3.5: The recovery of X72 by FFS
1 Input: X72 Output: X72.
2 foreach (’ik,jk) E (01,71) as in the order do

 

/'/.<—— Use B,X72T : 6, + A,XRT —->°/./
3 if lilfikl < l<MR>ikl then
4 COPY Tj7+k '— dik; //<-- not 31k
5 foreach likJ E Mik’ j yé jr+k do
6 L add TJr +k T _‘rJr+k +2TJ’
/‘/.<—— Use XRT :13,» +A,XRT ——>°/./
7 else
8 COpy (L‘j T+k: f3iki //<__ 1101; Bi]:
9 foreach 1i]: J E (MRlik do
10 Ladd TJ,«+};: _ IjI-l-k +le

 

11 return X72;

 

 

Al orithm 3.6: The overall S—MLDA

1 Input: [(ig,X] Output: lXR=X72l
2 d0 ALTA by Algorithm 3.1;

3 if R 2 (D then

4 recover X by Algorithm 3.4;

5 return X;

6 exit the S—MLDA;

construct MR with ’R;

do the BSR by Algorithm 3.2;

do the GE by Algorithm 3.3;

if R\r,~ 35 (D then

L return the free variables ’R,\r,~;

p—Iv—a
woomq

exit the S—MLDA;

H
N

_1
CD

recover XR by Algorithm 3.4;
recover X72 by Algorithm 3.5;

D-‘H
0‘;-

return [.X'R,.XR];
exit the S-MLDA;

 

H
O)

 

 

3.3 The Complexity of the MLDA

Similar to LT codes in section 2.3, we estimate the computational complexity of the

S-MLDA by counting the number of {sign, bit}-flips and symbol additions made by

90

the pre-decodmg and the post-decoding, respectively. Throughout this section, we
assume that R 75 (0.

Let us first estimate the complexity of the gore-decoding. By the ALTA based on
Algorithm 3.1, total INI number of 1’s is flipped into —1 to set up 111, and then
every 1 in Al is eventually flipped into -—1. Hence, the complexity of the ALTA in
sign-flip is proportional to IHI. While computing M7; = 311173 by the BSR iteration
(3.2.11), based on Algorithm 3.2, each 1 in M72 (or [5]), except in the diagonal of
B , corresponds to one row addition in MR (or I g] ). Therefore, the BSR constitutes
the complexity proportional to r(I.M7-zI — n + r), where r is the number of columns
of MR- By the GE on 11.173, based on Algorithm 3.3, when a pivot 1%,”: is chosen
at each pivoting round 1:, the row 1173). is added to the rows of T whose tkt‘h column
entry is 1. Since Iii—[,kI S (r — k) and ITI S (m — l — k) at round k, the number of

{sign, bit} -flips together is less than

7' 7'
ZIAISkIITI =cZk((1—R—p)n+k), (3.3.1)
k=1 k=1
where R = fl and c is a constant less than 1. In practice, simulations exhibit that,

n

at each round k, ITI S 95211 and INISkI S 135, thus, c S 211. Hence in total, the

number {sign, bit}—flips by the pre—decoding step is less than

,.
IHI +rIMRI+cZk<(1— R—p)n+k). (3.3.2)

k=1
When r z (n, with a small fraction 5 > 0. we may assume that, in general, the

2 3 3

estimate (3.3.2) is dominated by either (1 — R — ]))€ 71 or e‘ n3

, so that as shown

in I3, p. 4], the overall complexity of the pie-decoding step is 001.3) but with a very

3

small constant factor 6 or (1 — R—p)e2. For an example, as presented in Figure 3.3,

the fraction of references % from simulations of the S-MLDA is less than 0.032.

Second, let us now estimate the number of symbol additions made by the post-

decoding step. We notice that in Algorithm 3.4, precisely, 71.8 number of It’s,

91

whose 1' is in 01 U or, are constructed to set up 13 and 13 at the initialization step of

the algorithm. Let 1) = 1'3. Then approximately, T—£R(

72

 

N] + 77.) number of symbol
additions of (1g is made for 13’ and ,3 at the initialization step. For the computation
of SJT, approximately, fiIMRI symbol additions of B are made. Then for the
— 2r) symbol additions of B is made by (I‘ll—71.

recovery of XR, total of (ILI + U

 

 

Now for each 2' E a), let d,- = min{|(11—IR),I, IM,~I}. By the alternative recovery step
(based on Algorithm 3.5), total (1 2 21:1 dik symbol additions is made for the
recovery of XR, and d < r5711!” I Hence in total, the number of symbol additions

made by the post-decoding is less than

I)
117% (|H| + IMRI + n) + r2. (3.3.3)

Lastly, let us estimate the number of symbol additions by the original MLDA in
I3]. Let the system XR : 3T + AXR alone be used for the recovery of XR, as showed
in 4 FFS in section 2.1. At the pie—decoding step, note that only the {sign, bit}-flips
that. correspond to a row addition constitute one symbol addition of )3 or B. Foremost,
total of IN] + li’l‘lfil symbol additions by the BSR and less than IUI — r + 22:) IT]
row additions by the GE and U ‘1 are made for the recovery of XR. Then for the
recovery of XR, total of Ii’lIIRI +1 (or I/II + l) symbol additions is made. Hence in

total, the number of symbol additions by the original MLDA in I3] is less than

IN] + ill—IR] + r2 + (1 — R — p)nr. (3.3.4)

 

 

AIR] +

In the following section, we substau'itiate that, by experimental results, the estimate

11.173] (or IAI) as 71,) —> m. (See green curves in Figure 3.2

 

(3.3.4) is ('loniinated by

that should be removed by the alternative recovery step).

92

3.4 Simulations

In this section, we present the simulation results of the S-MLDA tested with é-rate
PEG LDPC codes I13]. We then demonstrate, based on the experimental results, that

some LDPC codes under the S-MLDA can achieve performance in stable erasure rates

m
n 7

p (for the successful S-MLDA) very close to the ideal limit while the decoding
complexity of the post-decoding in symbol additions maintains within few tens of n.

The simulation is based on the following spectrum. First of all, for each block
length 72., a check matrix H is arranged in advance by using PEG software [27] that
provides a larger local minimum cycle of columns in the best effort of the greedy

algorithm in I13]. The row and column-degree distribution (A, p) of H, whose average

row-degree is or : 8.33, is as follows

my) 2 0.457332 + 0.32331:3 + 0.021434 + 0.05933:6 + 0.0389127 (3.4.1)
+0.0248zr8 + 0.003339 + 0.0177319 + 0.0475320,

/)(:I') : 0.6708.r8+0.3292.r9.

Using the ALTA in [4], if necessary, we convert H into an approximate triangular
generator matrix C = [Smxki mem] to obtain a codeword a in a systematic form

a = ((11,011)), where 0}) 2 L51 Smxkd? Second, the tested block-lengths n are

mxm
from n. = 2,000 to 20,000 by 2,000. For each 71, starting from he 2 (0.5)n to
71,. = (0.4)71, the number of losses n6 is given by the decrement 72.6 :2 ne — 1. Then
for each pair (71,716), the S-MLDA is tested 100 times by assigning he random losses

on a codeword a by using the Mersenne Twister algorithm [16] on [71] to measure the

)erformances of codes under the S-MLDA in the followin scenarios:
1

1. decoding failure rate of codes under the S-MLDA and the MPA;
2. nun‘iber of symbol additions by the post-decoding and the original MLDA I3];

3. fractions of references I};

93

 

 

 

I ' I '

— by the S-MLDA
n=10,000 _ by the MPA
l ' I r i '

   

 

 

i l i a i . i i
0.49 0.48 0.47 0.46 0.45 0.44 0.43 0.42 0.41 0.4
D

 

 

 

 

 

Figure 3.1. Decoding Failure Rate of LDPC codes under the S-MLDA (black curves) and
the MPA (gray curves) for block lengths 2,000 S n S 20, 000

4. rank-deficiency r) = dim(Ker(H)).

In Figure 3.1, for each fixed 71, a curve represents the decoding failure rate of
LDPC codes (denoted as DFR in the figure) in 100 trials of decoding by the S-MLDA
(black curves) and by the MPA (gray curves). For an example, when n = 10,000
(see the bottom figure in Figure 3.1), the red point (p = 0.49, DFR = 1) indicates

that the MPA never succeeds to recover pn = 4900 random losses of a. In contrast,

94

the blue point (0.49, 0) indicates that the S—MLDA always succeeds for the recovery
of pit ___ 4900 random losses. It can be seen that, when n = 10, 000, the DFR of the
S-MLDA is 0 up to p S 0.496. In contrast, the DFR of the MPA is always greater
than 0 for all p 2 0.435 and is 1 for all p > 0.458. It can be also observed that,
from the top figure, for any pair (12,19) where p S 0.492, the DFR by the S-MLDA
decreases to 0 dramatically by a slight decrement in p. Thus, the maximum loss rate
p 2 LI:- recoverable by the S-MLDA can be projected to the ones close to the ideal
limit 1— H = 0.5.

Figure 3.2 shows the number of symbol additions made by the post-decoding
(based on Algorithm 3.4 and 3.5) and the original MLDA in I3]. For each fixed
72.. curves represent the number of symbol additions divided by n, denoted as NS
in the figure. First, a black curve 1 and a gray curve 2 indicates the NS made by
the post decoding and the original MLDA in [3], respectively. For instance, when
n = 10,000 (see the bottom figure in Figure 3.2), the point (p = 0.49,n3 = 9) on
the black curve 1 indicates that, approximately, (N R)n = 90,000 symbol additions is
made by the post-decoding, and the red point (0.49, 36) corresponds to, approximately,
300. 000 symbol additions by the original MLDA. Sin‘iilarly, a gray curve 3 indicates

the difference

I
1 _
* — _ ,1 _ .
(1 _ H mm 2 11,], , (3.4.2)
k=1
where (1J1; : n'iin{|.llI,-k|, (1177;),-If }, '1'), E 0). (Recall the alternative recovery step 2c)

 

 

in section 2.1). It can be observed that, as p ——+ 0.5, a gray curve 2 is more likely
parallel to a gray curve 3. This tells that, as p approaches to 1 — R = 0.5, the number
of symbol additions by the original MLDA is dominated by IMRI (or I/II). In the
top figure, notice that the NS by the post-decoding is less than 17 for any instance
of (71.1)). In contrast, as n grows and p -—> 0.5, the red NS by the original MLDA
far exceeds the one made by the S-iVILDA. This substantiates that, as p ——> 0.5,

the alternative recovery step of the post-decoding significantly improves the decoding

95

 

Number of Symbol Additions by the Post-Decoding and the MLDA

C

4

/
/ -

0.44
p : Loss Rate 0-42

 

 

3

: Block Length — 1 by the S-MLDA
—- 2 by the Original MLDA
n=10,000 — 3 d‘ =I|14I —Z:diI/n

 

 

 

 

 

 

 

 

0 L 4L 1 i | 1 i l
0.5 0.49 0.48 0.47 0.46 0.45 0.44 0.43 0.42 0.41 0.4
p

 

 

 

Figure 3.2. Number of Symbol Additions made by the Post-Decoding and the original
MLDA

efficiency in symbol additions. Lastly. we recall the removal of redundant equations
by the step 1b) of the {ire-decoding step. In the figure, for any pair (11,71), the NR
made by the redundant rows is too small to tell. The reason to this is in the fact that
redundant rows are sparse with average degree or = 8.33 and the number of those
rows is (1 — R — 1))71. Nonetheless, the number of redundant symbol additions over

the those rows is about 8.33(1 — R — p)n and is not trivial.

96

 

Number of References for 2,0003 n 5 20,000

0.03

FR : (Number of References)ln

 

 

 

 

 

 

 

 

0.45
p:Loss rate .2
o 4 1 e 1 4 1.2 1 0-8 0'6 0'4 o
2 1'8 n : Block Length x 104
n=10,000 -— Fraction of References
0.03.. . I.. l I...I.. .I..T I ...... I ....... I ...... _.
0025, . ...... ...... ..... . V ...... - ........ ..... i ...... ....... _
0_02_ . . . ..... . .....-
E 0.015.. ........ , .. , ......... ‘ ....... l ....... ...... . ...... ....... _
00053‘ . . .............. i ...... - ....... ...... ..
o I i i I i ‘L. l -i 1 4m -
0.5 0.49 0.48 0.47 0.46 0.45 0.44 0.43 0.42 0.41 0.4

p

 

 

 

Figure 3.3. Number of References

In Figure 3.3, for each fixed 71, a black curve represents the fraction of references
FR : %, where r is the number of columns of MR. For an example, when n 2 10, 000
(the bottom figure in Figure 3.3), the point (p = 0.49,rf = 0.023) indicates that
r 3:: 71(FR) : 230. It can be observed that, from the top figure. FR S 0,032 for
any instance of (71.1)). This substantiates the very small constant fraction in the

complexity of the GE on G. (See the last paragraph in section 3.3 or [3, p. 4]).

Therefore, with such small fraction of references, the GE on MR (or G) may not be

97

 

Rank Deficiency of LDPC codes for 2,0005 n 5 20,000

(a)
O

n : Rank Deficiency
8 8

P
or

    

0.495

 

 

-_ 1.5
p : Loss rate 1
0'49 0'5 n : Block Length x 10‘
n=10,000 n = dim (Ker(H))
I ' I r l ‘ I ' I ' I ' I ' I ' I '

15 _ _ . > . . . . j ..
10 - -
5 ._ ...................... _.

 

 

 

o I I I I I I . I I I I I
0.5 0.499 0.498 0.497 0.496 0.495 0.494 0.493 0.492 0.491 0.49
p

 

 

 

 

Figure 3.4. Number of Free Variables by the S-MLDA

a drawback to the overall complexity of the S—MLDA.

In Figure 3.4, for each fixed n, a black curve 77 = f (p) represents the number of
free variables when the S-MLDA fails to recover the lost X = ae. For an example,
when II : 10. 000, the point (p = 0498,77 = 5) (see the bottom figure in Figure 3.4)
says that the S-MLDA fails to recover the lost at: with probability DFR = 0.81 (see
Figure 3.1) and the rank—deficiency in this case is approximately 5. Thus, even the

failure cases of the S—MLDA, a is obtainable by retransmitting less than 5 symbols

98

of free \x'arial'fles only.

3.5 Conclusions

Through the sections (3.1) and (3.2), we provide mathematical models and exemplary
algorithms of the routines of the S-MLDA for the decoding of BBC based LDPC codes.
In section 3.3, we estimate the complexity of the proposed S-MLDA. In section 3.4,
we present the simulation results of the S-MLDA tested with 1.12-rate PEG-LPDC
codes for the performances in decoding failure rates and computational complexities.
Particularly in the section, we substantiate that the PEG-LDPC codes under the S—
MLDA can achieve performance in erasure recovery rate very close to the ideal limit
1 — R. while the S-MLDA maintains the complexity of the post-decoding in symbol

additions within few tens of n and the fraction of references :7 less than 0.032.

99

*LIST OF ABBREVIATIONS

ALTA, 7
BBC, 2
BS, 18
BSR, 41
DFR, 64
FFS, 41
FR, 67
FS, 18
GE, 3
ISD, 31
LDPC, 4
LT, 5
MLDA, 7
MFA, 6
NS, 66
RSD, 31
S-MLDA, 8

*LIST OF NOTATIONS

(72,72), 46
(T, 7"), 46
(01,72), 46
1,}, 46
C(H), 20
H(t), 52
X72, 46
X72, 46
[In], 46
[II], 46

X 46
Ker(H), 3
RS(H), 58
ar, 56

III‘Ig(H), 12

INDEX

ALTA, 7, 40, 80, 83
altered p(:r), 57
alternative recovery, 44, 81, 88, 95

BBC, 2

BS, 18
Row—wise, 18

BSR, 41, 80

capacity approaching, 29
code

LDPC, 2O

LT, 32

raptor, 38, 54

tornado, 30
codeword, 2, 20

decoder, 2
degree

column, 27

row, 27
Degree Reduction, 23
Density Evolution, 26
DFR, 64, 73, 94

elementary row operation, 13
encoder, 2

entry-degree ensemble, 27
erasure, 2

FFS, 41

FR, 67, 77, 97

FS, 18
Row-wise, 18

GE,3,11,41,80

100

ISD, 31, 34 information symbol vector, 2
syndrome, 11

LDPC, 4 .. , . ,
‘ syndrome vector, 11
PEG’ 7 systematic, 22
LT, 5

transmission, 31
LU-factorization, 11, 15

IIIatrix
elementary, 14
LDPC, 21
Lower Triangular, 12
Mersenne Twister algorithm, 64, 93
MLDA, 7
Burshtein and Miller’s, 40
S-MLDA, 8
Separated, 43
MFA, 6, 54

NS, 66, 74, 7.5, 95

optimal, 7
overhead, 39, 41

post-decoding, 43, 81
pie-decoding, 43, 81

rank deficiency, 57, 78
rank distribution, 58
Cooper, 59
Kovalenko, 59
rate
code, 22
erasure. 7
redundancy, 22
redundant, 22
redundant rows, 44, 75, 88, 96
Ripple, 33
RSD, 31, 37
definition of, 54

S-MLDA, 80, 83
symbol, 2

101

BIBLIOGRAPHY

[1] R. G. GALLAGER, Low Density Parity-Check Codes, MIT Press, Cambrige, MA,
1963. 5, (1969), 399-410.

[2] M. LUBY, LT Codes, 43rd Annual IEEE Symposium on Foundations of Computer
Science, 2002.

[3] David Burshtein, Gadi Miller, An Efi‘icient Maximum-Likelihood Decoding of
LDPC Codes Over the Binary Erasure Channel, IEEE Trans. Inform. Theory,
50:2837-2844, 2004.

[4] T. RICHARDSON, R. URBANKE, Efficient Encoding of Low-Density Parity-Check
Codes, IEEE Trans. Inform. Theory, 47:638-656, 2001.

[.5] M. LUBY, M. MITZENMACHER, A. SHOKROLLAHI, D. SPIELMAN., Efficient
Erasure Correcting Codes, IEEE Transl Inform. Theory, 47:569-584, 2001.

[6] M. LUBY, M. MITZENMACHER, A. SHOKROLLAHI, D. SPIELMAN., Practical
Loss~resilient Codes, In Proceedings of the 29th annual ACM Symposium on Theory
of Computing, pages 150-159, 1997.

[7] A. SHOKROLLAHI, LDPC CodessAn Introduction, J. Diff. Eqs., 5, (1999), 399-410.

[8] D. MACKAY AND R. NEAL, Good codes based on very sparse matrices, Cryptog-
raphy and Coding, 5th IMA Conference, Dec. 1995.

[9] L. BAZZI, T. RICHARDSON, R. URBANKE, Exact thresholds and optimal codes
for the binary symmetric channel and Callager’s decoding algorithm A, IEEE Trans.
Inform. Theory, 47, 2001.

[10] L. RIZZO, Effective Erasure Codes for Reliable Computer Communication Pro-
tocols, Comput. Commun. Rev., vol 27, pp.24-36, Apr. 1997.

[11] L. RIZZO, L. VICISANO, A Reliable Multicast Data Distribution Protocol Based
on Software FEC Techniques, in Proc. HPCS, June 1997

[12] P. OSWALD AND A. SHOKROLLAHI, Capacity-Achieving Sequences for the Era-
sure Channel, IEEE Trans. Inform. Theory, 48:3017-3028, 2002.

102

[13] H. Xiao, A. H. Banihashemi,Improved Progressive-Edge-Crowth (PEG) Con-
struction of Irregular LDPC Codes, IEEE Comm. Letters, Vol 8, No.12, December,
2004.

[14] A. SHOKROLLAHI, Raptor codes, Digital Fountain, Inc., Tech. Rep. DF2003-06—
001, June 2003.

[15] A. Shokrollahi, S. Lassen, and R. Karp, Systems and Processes for Decoding
Chain Reaction Codes Through Inactivation US. Patent 1,856,263, Feb. 15, 2005.

[16] MAKA'ro MATSUMOTO AND TAKUJI NISHIMURA Mersenne Twister: A 623-
Dimensionally Equidistiibuted Uniform Pseudo-Random Number Generator, ACM
Trans. on Modeling and Computer Simulation, Vol. 8, No.1, Jan 1998, p3-30.

[17] Hossein Pishro—Nik and Faramarz Fekri, On Decoding of Low-Density Parity-
Check Codes Over the Binary Erasure Channel IEEE Trans. Inform. Theory,
50:439-454, Mar. 2004.

[18] KI-MOON LEE, HAYDER RADHA, The Design of Maximum-Likelihood Decoding
Algorithms of LDPC Codes over Binary Erasure Channels, Accepted to CISS 2007.

[19] KI-MOON LEE AND HAYDER RADHA, The Maximum Likelihood Decoding of
LT codes and Degree Distribution Design. with Dense Fractions, Accepted to ISIT
2007.

[‘20] KI—MOON LEE, HAYDER RADHA, AND Ho-YOUNG CHEONG, “LT Codes from
an Arranged Encoder l\’Iatrix and Degree Distribution Design with Dense Rows”,
submitted to Allerton Conference 2007.

[21] I. N. KOVALENKO, A. A. LEVITSKAYA AND M. N. SAVCHUK, Selected Prob-
lems in Probabilistic Combinatorics ( in Russian ), Naukova Dumka, Kyiv 1986.

[22] C. COOPER, On the rank of random matrices, Random Structures and Algo-
rithms, 1999.

[23] Steven J. Leon, Linear Algebra with Application, Prentice Hall 6th Edition.
['24] Steven Roman, Advanced Linear Algebra, Springer 2nd Edition 2005.

[25] Charles G. Cullen, IIIatrices and Linear Transformations, Addison—Wesely 2nd
Edition 1990.
[26] Sheldon Axler, Linear Algebra Done Right, Springer 2nd Edition 1999.

J

[27] DAVID J.C MACKAY, Information Theori, Inference and Learning Algorithms,
Cambridge University Press 2003.

103

['28] T. RICHARDSON, R. URBANKE, ll'IOdG'I‘I’L Coding Theory, This books is available
at http://lthcwww.epfl.ch/

[29] V. F. Kolchin. Random Graphs, Cambridge University Press 1999.

104

   
  

Il][]]]]][[]]l[l]]]][]I]]]][l

7