Efficient Decoding and Application of Rateless Codes by Au AbduiHussein B.A.Sc., Simon Fraser University, Burnaby, B.C., 2006 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Applied Science in The Faculty of Graduate Studies (Electrical and Computer Engineering) The University Of British Columbia (Vancouver) September, 2008 © Ali AbduiHussein 2008 Abstract Fountain codes have recently gained wide attention in the communications research community due to their capacity-approaching performance and rateless properties that allow them to seamlessly adapt to unknown channel statistics. This thesis of fers two key contributions. For the first, we consider the problem of low complexity decoding of Luby Transform (LT) and Raptor codes, which are classes of Fountain codes. We introduce a decoding method which has a significantly reduced compu tational load compared to the commonly used alternative of message-reset decoding with a flooding schedule. This method combines the recently proposed technique of informed dynamic scheduling combined with incremental decoding. Simulation re sults for the example of the binary symmetric channel show complexity reductions (in terms of the total required number of decoding iterations) by 87% compared to conventional message-passing decoding and 54% compared to a recently proposed incremental decoding scheme for Raptor codes. Having proposed our novel decoding method, we then focus on applying rateless codes to free-space optical (FSO) transmission systems. FSO systems enable high speed communication with relatively small deployment costs. However, FSO systems suffer a critical disadvantage, namely susceptibility to fog, smoke, and similar con ditions. A possible solution to this dilemma is the use of hybrid systems employing FSO and radio frequency (RF) transmission. As for the second contribution of this 11 Abstract thesis, we propose the application of rateless coding for such hybrid FSO/RF sys tems. The advantages of our approach are (i) the full utilization of available FSO and RF channel resources at any time and (ii) very little feedback from the receiver. In order to substantiate these claims, we establish the pertinent capacity limits for hybrid FSO/RF transmission and present simulation results for transmission with off-the-shelf Raptor codes, which achieve realized rates close to these limits under a wide range of channel conditions. 111 Table of Contents Abstract ii Table of Contents iv List of Tables vii List of Figures viii Acknowledgements x Dedication xi 1 2 Introduction 1 1.1 Thesis Outline 3 1.2 Contributions 4 Rateless Codes 6 2.1 Background 6 2.2 Encoding Rateless Codes 7 2.2.1 LT Encoding 7 2.2.2 LT Degree Distributions 10 2.2.3 Raptor Encoding 11 iv Table of Contents 3 2.3 Decoding Rateless Codes 13 2.4 Scheduling Techniques for Decoding Rateless Codes 14 2.4.1 Flooding (FL) Schedule for BP Decoding 15 2.4.2 Informed Dynamic Schedule (IDS) for BP Decoding 16 2.5 Incremental Decoding (ID) of Rateless Codes 19 2.6 Stoping Criterion for Decoding Rateless Codes 20 Decoding with Early Termination for Rateless Codes 22 3.1 Introduction 22 3.2 Biased Incremental Decoding (BID) 24 3.3 Combination of ID/BID with IDS 25 3.4 A Hybrid Stopping Criterion for IDIDS and BIDIDS 27 3.5 Computational Complexity 29 3.6 Simulation Results 30 3.6.1 Simulations for LT codes 31 3.6.2 Simulations for Raptor Codes 38 4 Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication 43 4.1 Introduction 43 4.2 1ansmission Model and Proposed Coding Scheme 47 4.2.1 Transmission Model 47 4.2.2 Proposed Coding Scheme 50 4.3 Constrained Capacity of the Hybrid FSO/RF Channel 52 4.4 Simulation Results 54 V Table of Contents 5 Conclusions and Future Work Bibliography 62 64 vi List of Tables 3.1 3.2 3.3 3.4 4.1 4.2 4.3 Pseudo code for IDIDS/BIDIDS algorithms for decoding Rateless codes Values for parameters w and c used in simulations Improvement factors in terms of number of iterations for the different algorithms compared to MRDFL. BSC with C = 0.33 bit/(channel use). Improvement factors in terms of number of iterations for the different algorithms compared to MRDFL. BSC with C = 0.50 bit/(channel use). 26 32 35 35 Considered channel capacities CFso, CRF and channel usage ratios 7Fso/’?aF defined in (4.12) for hybrid FSO/RF transmission such that the total capacity CH = 1 bit/(FSO channel use). The corresponding realized rates are shown in Figure 4.2. (CRF in [bit/RF channel use] and CFS0 in [bit/FSO channel use]) Different parameter combinations simulated for the scatter plot in Fig ure 4.3. (CRF in [bit/RF channel use], CFso and CH in [bit/FSO chan 57 nel use]) 59 Different parameter combinations simulated for the scatter plot shown in Figure 4.4. (CRF in [bit/RF channel use], CFS0 and CH in [bit/FSO channel use]) 59 vii List of Figures 2.1 2.2 LT Code Factor Graph Factor graph of a Raptor code after transmission of n check bits. 3.1 BER as a function of R’ for different decoding methods. BSC with C = 0.50 bit/(channel use) BER as a function of R’ for different decoding methods. BSC with C = 0.33 bit/(channel use) Complexity in terms of number of iterations as a function of R . BSC 1 with C = 0.50 bit/(channel use) Complexity in terms of number of iterations as a function of R’. BSC with C = 0.33 bit/(channel use) Scatter plot for the realized rate for various methods. Arguments (Lma, T) mean that a decoding attempt is made every T newly re ceived samples with L Lmajc iterations. Check-sum satisfaction stop ping for MRDFL/IDFL. IDIDS uses early termination with (3.4). x 3.2 3.3 3.4 3.5 3.6 4.1 4.2 . . . . axis: MRDFL(100,100) with L = Lmax Scatter plot for the total cost in number of iterations until successful decoding. Arguments (Lmax, T) mean that a decoding attempt is made every T newly received samples with L Lm iterations. Check-sum satisfaction stopping for MRDFL/IDFL. IDIDS uses early termination with (3.4). x-axis: MRDFL(100,100) with L = Lmac Block diagram of the proposed coded hybrid FSO/RF transmission system Surface plot for the realized rates when CH = 1 bit/(FSO channel use) and the parameters given in Table 4.1 8 12 33 34 36 37 41 42 47 58 viii List of Figures 4.3 Scatter plot of realized rate versus capacity CH for the parameter com binations given in Table 4.2. The 45°-line is included as a reference. 60 Scatter plot of realized rate versus capacity CH for the parameter com binations given in Table 4.3. The 45°-line is included as a reference. 61 . 4.4 . ix Acknowledgements I wish to express my sincere thanks to my supervisor, Prof. Lutz Lampe. This thesis and work would have not been accomplished without his expert advice and effective communication. I am particularly grateful to him for giving me the opportunity to explore and excel in the field of communications. I would like to express a special word of thanks to Anand Oka, who tirelessly assisted me in every step of this work. I also thank my friends who offered encour agement when it was most needed. A special thanks to my mother and father who supported me throughout my stay at the University of British Columbia. x Dedication This thesis is dedicated to my parents Samar Ibrahim & AbdulSalam Hamze for their perseverance over the years, as they have given me the opportunity to study at this reputable university in this great region of the world. xi Chapter 1 Introduction Fixed-rate codes such as low-density parity-check (LDPC) codes, are typically optimal for channels with known statistics [19]. Practically, however, the channel statistics are unknown to the transmitter in most cases, and fixed-rate codes may fail to perform as well. Fountain (rateless) codes have been introduced in [13] to address this problem. Luby Transform (LT) and Raptor codes are two classes of these codes. They have received considerable attention in the recent past due to their inherent ability to adapt to channel conditions and their capacity-approaching performance. It has been shown that these codes offer good performance not only for erasure channels, but also for other channels such as the binary symmetric channel (BSC), the additive white Gaussian noise channel (AWGNC) and fading channels [4, 17, 20]. In this thesis work, we focus on two main issues concerning the application of rateless codes. First, we investigate the problem of decoding rateless codes more efficiently. Second, we study the application of rateless codes to FSO transmission systems. To address the former issue, we first introduce the existing methods of decoding rateless codes, with a greater focus on scheduling techniques and stopping criteria. We then note that in order to decode rateless codes more efficiently, we have to 1 Chapter 1. Introduction accomplish the following: 1. Fast convergence of decoding, i.e., less computation required before decoding is completed successfully. 2. Early termination of decoding, i.e., smarter method to detect the end of a decoding process, and hence stop earlier without degrading error-performance. The decoding of rateless codes proceeds in multiple attempts, and each attempt is composed of several iterations. If in one attempt, the decoder fails to decode success fully (error-free), another attempt is executed upon the arrival of more information from the channel. As such, to realize fast convergence, we utilize a method of retain ing information from previous decoding attempts as presented in [8]. We combine this method with a newly presented scheduling technique, which was initially intro duced for fixed-rate codes [2]. In this scheduling technique, only less reliable sections of the decoding graph are active in the decoding process. This results in improved (faster) convergence compared to the commonly used techniques. The combination of the aforementioned techniques results in a novel decoding method which we term Incremental Decoding with Informed Dynamic Scheduling (IDIDS). Secondly, to achieve early termination, we present a novel hybrid stopping crite rion which allows for termination of decoding much earlier. This criterion tests for successful completion at a very fine interval (less then one iteration) and is hence capable of stopping the decoding attempt at a much earlier stage than traditional cri teria. We apply this criterion to IDIDS, and find through simulations, that decoding complexity can be reduced greatly. 2 Chapter 1. Introduction In the later sections of this thesis, we introduce FSO transmission systems, their applications, and the constraints limiting their performance. We then discuss the ex isting techniques utilized to combat such constraints such as the use of error control codes, interleaving and spatial diversity. We discover that media diversity is the only way to perform well as proposed as in [101, where a radio frequency (RF) channel is used in conjunction with the FSO channel. However, this approach is deemed in efficient because of duplication of information on RF and FSO channels. Realizing this fact, we propose our alterative which can achieve a close-to-optimal performance under a wide spectrum of channel conditions, yet using minimal feedback and avoid ing duplication. Our method utilizes a practical implementation of Raptor codes. Simulations show that these codes can approach the associated capacity limit of the hybrid FSO/RF channel under various channel conditions. 1.1 Thesis Outline The remainder of this thesis is organized as follows: In Chapter 2, we introduce and compare rateless codes to fixed-rate codes. We then briefly present the procedure for encoding LT and Raptor codes. Subsequently, we discuss the existing techniques for decoding rateless codes with several scheduling recipes. We also talk about the recently presented method for incremental decoding. Finally, we review the stoping criterion for decoding rateless codes. Chapter 3 presents the first contribution of this thesis. A new method for incre mental decoding is presented and discussed. Then, this method is combined with 3 Chapter 1. Introduction the freshly introduced sequential scheduling technique to result in a novel method of decoding rateless codes. A new stoping criterion is catered for this combination to achieve maximal decoding cost reduction. This chapter concludes with simulation results showing the reduction achieved for both LT and Raptor codes. In Chapter 4, we shift our focus to the problem of combating constraints limiting performance of FSO systems. We introduce the existing techniques and then propose our method which is based on the application of rateless codes to hybrid FSO/RF systems. The transmission model and the proposed coding scheme are discussed in details. Simulation results confirm the superiority of our method. Chapter 5 summarizes the thesis conclusions and outlines few suggestions for future work. 1.2 Contributions The overall work of this thesis has lead to two publications as well as a recent sub mission as follows: • Ali AbdulHussein, Anand Oka and Lutz Lampe. Decoding With Early Ter mination for Rateless (Luby Transform) Codes, In Proc. of the IEEE Wireless Communications and Networking Conference (WCNC), Las Vegas, USA, March 2008. • Ali AbdulHussein, Anand Oka and Lutz Lampe. Decoding with Early Ter mination for Raptor Codes, IEEE Communications Letters, 12:444-446, June 2008. 4 Chapter 1. Introduction • Au AbduiHussein, Lutz Lampe and Anand Oka. Rateless Coding for Hybrid FSO/RF Communication System, submitted to the IEEE Communications Let ters, Aug 2008. 5 Chapter 2 Rateless Codes In this chapter, we introduce rateless codes and discuss their differences with fixed-rate codes. Next, we present methods for encoding and decoding rateless codes with more details on techniques used to schedule rateless decoding. The degree distributions used to encode LT codes are also reviewed briefly in this Chapter. We finally introduce the stopping criterion utilized to terminate rateless decoding. 2.1 Background While fixed-rate codes such as LDPC codes have been shown to approach capacity for channels with known statistics [19], in many practical situations the channel statis tics are unknown at the transmitter or, as in e.g. broadcast transmission, different transmitter-receiver links experience different statistics, and hence fixed-rate codes may perform poorly. To address this issue, the concept of rateless codes, and in par ticular Fountain codes, is appealing. LT and Raptor codes, invented by Luby [13], are classes of Fountain codes which are capacity-achieving for erasure channels. For a Fountain code, transmitted bits could be either the input bit itself (degree one) or the exclusive-or of multiple input bits. The size of this multiplicity is referred to as degree and hence a Fountain code is characterized by its degree distribution. 6 Chapter 2. Rateless Codes The success of the LT codes depends critically on using the (robust) Soliton Degree Distribution and long code lengths [13]. However, to maintain low complexity and latency in practical applications, [20] has proposed an optimized degree distribution where the maximum degree is limited to 67. Since this results in a significant error floor, a fixed high-rate outer code like LDPC needs to be used to give good asymp totic performance. Such a concatenation (high-rate outer code and LT code) has been termed a Raptor code [4, 20]. It has been shown that these codes offer good perfor mance not only for erasure channels, but also for other channels such as the binary symmetric channel (BSC), the additive white Gaussian noise channel (AWGNC) and fading channels [4, 17, 20]. Encoding Rateless Codes 2.2 This section first reviews the method of encoding LT codes based on a pre-defined degree distribution. The following section then discusses various degree distributions given in literature. The encoding of Raptor codes is also presented. 2.2.1 LT Encoding The factor graph shown in Figure 2.1 represents the graph for a typical LT code. The , v 2 , 3 LT code encoder, in general, linearly transforms a k-bit input vector (vi, v Vk), ..., labeled as white circles in the graph, into an infinite stream of check symbols (ci, c , c 2 , 3 ..., c,,,), labeled as squares, which passes through a given channel having an arbitrary capacity. The decoder collects channel output symbols progressively (Yl, 7 Chapter 2. Rateless Codes Figure 2.1: LT Code Factor Graph Y2, y3, ..., y,), , 3 (vi, v , v 2 ..., labeled as grey circles, till it has sufficient information to infer the bits uk). The LT code rate is then given by RLT= (2.1) where the random variable n is the number of check symbols required for success ful (error-free) decoding. The rate RLT is therefore a random variable as well that depends on the channel noise realization. The process of generating a check symbol is described as follows: • The value of the encoded symbol is the exclusive-or of d randomly chosen input symbols from the k-bit input vector, where d is called the symbol degree (1 dk). • The value for d is chosen from a degree distribution. More about the design and analysis of degree distributions can be found in the next section. The resulting code can be thought of as an irregular (non-uniform d) low-density code. The connections between the input and check symbols can be represented by 8 Chapter 2. Rateless Codes a generator matrix. Let C be the matrix associated with the factor graph shown in Figure 2.1. This G, therefore, can be written as 11100...o 1001o...o 000 10...1 00011...0 00001...o 00100...l o1001...0 001O1...1 Each row in C is associated with a single check symbol of the code, and the l’s represent the indices of the input bits connected to this check symbol. For instance, the first row, [1 1 1 0 0 ... , connection to 1 01, represents the first check symbol’s, c 1 is given by . Therefore, c 3 ,v 1 v 2 and v =v c 1 e 2 . 3 v (2.2) 9 Chapter 2. Rateless Codes 2.2.2 LT Degree Distributions The degree distribution of an LT code gives the probabilities, p(d), of having a check symbol with degree d. The design of such a distribution has to guarantee two elements: 1. Some encoded symbols should have high degrees to ensure that all input bits are connected to some check symbols. For successful decoding, every input bit must have at least one connection with a check symbol. 2. There must be few check symbols with low degrees, such as one and two, so that the decoding process can get started. In achieving this, one distribution, named the Ideal Soliton Distribution, has been suggested in [131 and is given by p(l) p(d) = 1/n, (2.3) d(d—ly where n is the size of the input vector. However, this distribution is impractical because it may lead the decoding process to a dead-end when there are not enough degree-one check symbols to keep the decoding process going. Notice that this dis tribution guarantees only one degree-one check symbol in average. To mitigate this issue, the Robust Soliton Distribution has been suggested alternatively. This distri bution has two extra parameters, c and 6, which are specifically designed to ensure 10 Chapter 2. Rateless Codes that the expected number of degree-one check symbols is about S = clog () (2.4) instead of 1 which is what the Ideal Soliton Distribution guarantees. c is a constant, and S is the bound on the probability that the decoding process fails after n + e received check symbols, where e > 0 is an overhead factor which accounts for the suboptimality of the (finite-length) code with respect to capacity. The Robust Soliton Distribution [13] is defined as v(d) = p(d) + r(d) (2.5) where p(d) is given by equation (2.3) and r(d) is given by for d=1,2,...,(n/S)—1 r(d) log() for d = n/S (2.6) 0 for d>n/S and the normalization factor Z is defined as Z 2.2.3 = (p(d) + r(d)). (2.7) Raptor Encoding The Raptor encoding process is composed of an outer code encoder (which is typically an LDPC encoder) and an LT code encoder which was described in Section 2.2.1. 11 Chapter 2. Rateless Codes Vt 112 113 114 116 Y5 1l, 117 Figure 2.2: Factor graph of a Raptor code after transmission of n check bits. The factor graph of a typical Raptor code is shown in Figure 2.2. The outer encoder encodes the k-bit input vector into the k’-bit codeword, labeled as white circles in the , a 2 , 3 , a 1 factor graph. The check symbols for this outer code is given by the vector (a ak’_k), labeled as grey squares. The k’-bit codeword is then fed into the LT code encoder to produce an infinite stream of check symbols white squares. The channel output symbols are (yi, , c 2 , 3 (ci, c Y2, , 3 y ..., ..., ca), labeled as yr,), labeled as grey circles. The rate of the Raptor code, RRApT0R, is given by RpToa = , (2.8) where the random variable n is the number of check symbols required for successful decoding. The rate is also a random variable that depends on the channel noise realization. The LT portion of the Raptor code is characterized by a generator matrix, G, though the outer code is characterized differently (a parity check matrix if LDPC is used). 12 Chapter 2. Rateless Codes 2.3 Decoding Rateless Codes Similar to fixed-rate codes, e.g. LDPC codes, rateless LT and Raptor codes (codes de fined on factor graphs) can be decoded with message-passing algorithms such as belief propagation (BP). BP decoding can proceed with different scheduling techniques. A scheduling technique is a recipe of how to communicate reliability information among input and check symbols during the BP process. These techniques will be discussed in the following section. Different from fixed-rate codes, however, the decoding graph of rateless codes grows incrementally with time as new check symbols become available. Normally the decoder requires more symbols when it fails to decode with the available ones. Therefore, a fresh decoding attempt is made after the arrival of each new batch of check symbols on a newly defined factor graph. However, to maintain low decod ing complexity (which is typically measured by the total number of iterations until successful decoding), it is desirable to terminate each decoding attempt as early as possible and hence reduced the overall cost. To do so, a smart stopping criterion is required. The next Chapter of this thesis presents our novel method to terminate decoding early though keeping error performance intact. In the general case of decoding rateless codes, the decoder collects channel output symbols i progressively until it believes to have sufficient information to infer the k input bits. In other words, a receiver-side estimate of the channel statistics (capacity C) is made and the first decoding attempt is executed when are collected. Timin min channel symbols is given by 13 Chapter 2. Rateless Codes Tmin (2.9) k/C. If the decoded information is erroneous, which is typically detected by making use of a cyclic redundancy check (CRC) with only a few bits of additional redundancy, samples has been received. another decoding attempt is made after a new batch of If the number of the current decoding attempt is denoted by ic, then the total number of received channel symbols is given by fl = Thmin + (1i — (2.10) 1) ninc, and the instantaneous code rate is the one given in 2.1 for LT codes or in 2.8 for Raptor codes. Figure 2.2 illustrates the factor graph for a Raptor code, where we labeled the n parity-check nodes involved in the decoding by Cj, j = 1,2,. . . , n. Note that the decoding of LT and Raptor codes can be executed similarly with the exception that the check nodes of the outer code (which typically belong to a high-rate LDPC code) do not exist in the factor graph of an LT code. The scheduling techniques discussed in the next section apply equally to the decoding of both codes. 2.4 Scheduling Techniques for Decoding Rateless Codes Numerous scheduling techniques for BP decoding on factor graphs have been discussed in literature [11, 18]. This section reviews the two main scheduling techniques that 14 Chapter 2. Rateless Codes can be used for decoding rataless as well fixed-rate codes, for example in LT, Raptor and LDPC codes. First, we discuss the simpler case, which is called “flooding” or “parallel” message-passing. We then describe IDS, which is a version of “sequential” message-passing. Decoding with a flooding schedule, being the most widely used method, will be the bench mark to which we compare our proposed methods in simulations. 2.4.1 Flooding (FL) Schedule for BP Decoding Generically, BP involves the exchange of a-posteriori likelihood messages between nodes (i.e. input and output symbols) of the factor graph [11]. The flooding schedule consists of several “iterations” of message-passing. Before describing this procedure, let us define the following: • f(v), called the neighborhood of v, is the set of all check nodes connected to variable node vj, • Pf(cj), called the neighborhood of to check node is the set of all variable nodes connected Cj, denotes the message sent from the variable node v to the check node • Cj • Cj, E .A((v), in the £th iteration, denotes the message sent from the check node v e .A/(cj), in the £t Cj to the variable node iteration, and • Zq is the log-likelihood ratio (LLR) corresponding to the channel information 15 Chapter 2. Rateless Codes on the check node Cj. Note that for different channel models, different equations for calculating this LLR are utilized. In every iteration, the following message update rules are applied in parallel to all variable (input) and check (output) nodes in the factor graph: tanh (mvi) = tanh () fJtanh (Mci) (2.11) VxVj (2.12) m.. = cyEJf(v) cycI 3 is calculated as Then the LLR of each variable node v (2.13) Vjé{1,...,k}. 9= cEAI(v) After a certain number of iterations a hard-decision is made on to obtain the estimated data vector 2, for j = 1,2,.. . , k The way this hard-decision is made also depends on the channel model being used. 2.4.2 Informed Dynamic Schedule (IDS) for BP Decoding Recently, various sequential schedules have been discussed in literature. Different from the parallel updates in the FL schedule, a sequential schedule prescribes a pre defined sequence of variable-node [9] or check-node [24] updates. (Note that an “up date” is a much smaller unit of computation than an “iteration”.) Simulations as well as theoretical analysis demonstrated that sequential scheduling converges faster 16 Chapter 2. Rateless Codes than flooding when applied to decoding codes defined on factor graphs [18]. This in crease in convergence speed does not increase the decoding complexity per iteration and leaves the error performance intact. Therefore, it can result in reduced overall decoding cost. One version of sequential scheduling, called IDS, was recently presented in [2]. Un like traditional sequential scheduling techniques which typically follow a pre-defined update schedule, IDS uses the latest available reliability information to re-schedule future updates (follows dynamic update schedule). IDS, therefore, has the ability to adaptively shift the BP update focus towards less reliable sectors of the factor graph, thus avoiding wastage of efforts in exchanging messages among nodes that have al ready reached high reliability. This leads to faster movement of the high reliability information within the decoding graph, which therefore results in faster convergence. In IDS each message is associated with a residual, which is simply the absolute difference between its value before and after an update. For the use of IDS with rateless codes we consider the residuals check node cj to variable nodes v Im e .iV(cj), for messages sent from a — where m. and are the messages before and after an update, respectively. Each check node, cj, is then assigned the ordering metric of the largest residual among all those of v E .Af(c) as follows old new — — — (2 14) v€.Af(c,) The check node which maximizes this metric is deemed to provide the largest inno vation and is hence selected for the next update. In IDS, the ordering metrics for all 17 Chapter 2. Rateless Codes check-nodes are calculated according to equation (2.14) and stored in a sorted queue Q. Then, an update consists of the following: • The node cj with the highest ordering metric, r, value is selected and messages to all vj e f(c) are calculated and propagated according to equation (2.11), • this same metric, r , is then set to zero and 1 Q is re-ordered. The only residuals that change after the updates corresponding to cj are those of v E iV(Cj), • equation (2.12) is then used to calculate all messages from these variable nodes to the check nodes in J\f(v) (except ci) for each vj E Pf(cj), • the ordering metrics of these check nodes are re-calculated and re-ordered in Q, and the one with the highest value is selected for the next update. The above steps are repeated n times, where n is the number of check symbols in the factor graph. These n updates count as a full iteration. Iterations are executed until a maximal pre-defined number of iterations is reached or a stopping criterion is employed. Note that unlike the case of a flooding schedule, with IDS, it is legitimate to speak of a fraction of an iteration. A fraction of an iteration can be just few updates (less than n). This concept will be significant when we introduce our novel stopping criterion, which can stop an iteration before its end, in the next Chapter. 18 Chapter 2. Rateless Codes 2.5 Incremental Decoding (ID) of Rateless Codes Having discussed two techniques used in scheduling BP decoding, we now discuss a method of retaining information from one decoding attempt to another which was presented in [8] and termed Incremental Decoding (ID). Due to the dynamic nature of rateless LT and Raptor codes’ factor graph, instead of starting from scratch upon the arrival of every new batch of check symbols as in message-reset decoding (MRD), ID continues decoding taking into account the results of the previous decoding attempt. For the time being assume that a FL schedule is used (cf, Section 2.4.1) and hence we call these two techniques MRDFL and IDFL. Generally, both MRD and ID techniques proceed in several decoding attempts. The first attempt, which is identical for both methods, starts when min k/C check symbols are available (cf. Section 2.2). The later decoding attempts, which are executed differently by ID and MRD, commence at the arrival of each new batch of n - check symbols. A decoding attempt consists of several iterations. In each 7 iteration, all variable and check-nodes are updated according to equations (2.11) and (2.12). Instead of initializing messages to zero at the beginning of each attempt as done in MRD, ID utilizes the information produced in the previous attempt. One way of realizing this [8] is to initialize the value of a message in a decoding attempt to its corresponding value from the last iteration of the previous attempt as follows: m” Cj,Vj — — mt,Ii) Cj,Vj (2 15 where m; is the message passed from the check-node cj to the variable-node v in 19 Chapter 2. Rateless Codes the £th iteration of the Kth decoding attempt. This utilization of existing reliability information results in reduced decoding cost. We will refer to this method simply as ID in the following. In the next chapter, we also introduce an alternative method of retaining information from one attempt to another. 2.6 Stoping Criterion for Decoding Rateless Codes In the case of fixed-rate codes such LDPC codes, the check-sum satisfaction test is used to terminate the decoding process and a pre-defined number of iterations is applied in each attempt. The test uses the following metric (2.16) where Cs is the number of satisfied check node equations (a check-node equation is satisfied when the exclusive-or sum of its variable node edges is equal to zero) and N is the number of check nodes in the factor graph. The test is satisfied when j F where F is a user-defined threshold. F is usually set to 1 (i.e. stop decoding when all check node equations are satisfied). Typically, a maximal number of iterations is applied in each attempt and the entire decoding process is halted when the aforementioned test is satisfied as in decoding LDPC codes. To achieve minimal decoding cost, a designated criterion can be used to stop 20 Chapter 2. Rateless Codes the decoding attempt before reaching the maximal number of iterations. For this, we cannot simply use the test given in (2.16) because full satisfaction of check-sum equations cannot be achieved all the time in the early decoding attempts. Therefore, a different P value is required for each attempt, which is rather tedious to optimize for each different code and attempt specially when applied to rateless codes, where N is dynamic. To address this, we present an alternative stopping criterion in the next Chapter which can stop a decoding attempt at a fraction of an iteration when applied with IDS. It is important to note that in practice, CRC bits are utilized to indicate the correctness of the decoded word and hence to stop the decoding process entirely. 21 Chapter 3 Decoding with Early Termination for Rateless Codes 3.1 Introduction In this chapter, we consider the problem of decoding rateless codes with early termi nation, and thus low complexity. In particular, we concentrate on the example of LT and Raptor codes. To achieve early termination, fast convergence of BP decoding and a criterion for termination, commonly referred to as a stopping criterion, are needed. The former problem can be tackled using two, not necessarily mutually exclusive, approaches: • Firstly, and as was presented in Section 2.5, it has been suggested that instead of starting the decoding process from scratch during every decoding attempt, some information should be retained and utilized from previous decoding at tempts [81. This technique, called incremental decoding (ID), typically results in a significantly reduced number of iterations in the later decoding attempts. • Secondly, as is well known for the case of fixed-rate codes, convergence can be improved by clever design of the schedule of message passing. For LDPC 22 Chapter 3. Decoding with Early Termination for Rateless Codes codes a method called informed dynamic scheduling (IDS) has recently been proposed in [2] and was discussed in Section 2.4.2. In this procedure, only unreliable subsets of the factor graph are required to update their messages, while much of the graph remains quiescent. This results in a greatly reduced number of updates compared to the often used flooding schedule, and thus faster convergence. The principal contributions of this chapter, therefore, are: 1. The combined application of the concepts of incremental decoding with IDS to the decoding problem of rateless codes. 2. The formulation of a novel stopping criterion for early stopping to minimize decoding complexity. As for the first contribution, we present an alternative way of retaining informa tion from one decoding attempt to the next, different from ID, which was discussed in Section 2.5. We term this method Biased Incremental Decoding (BID). Then we apply this method with IDS for decoding rateless codes. We also combine ID with IDS. This results in two novel techniques for efficient decoding of rateless codes: Incre mental Decoding with Informed Dynamic Scheduling (IDIDS) and Biased Incremental Decoding with Informed Dynamic Scheduling (BIDIDS). As for the second contribution, we note that, to the best of our knowledge, the existing literature on rateless codes does not explicitly address the problem of when to stop a decoding attempt. We therefore propose a new hybrid stopping criterion that is sensitive enough to terminate decoding within a fraction of an iteration, thus 23 Chapter 3. Decoding with Early Termination for Rateless Codes extracting the maximum possible efficiency of BID/ID with IDS (the notion of a fraction of an iteration is explained in Section 2.4.2). The simulation results show that the devised decoding schemes with early termination achieve considerable reductions in decoding complexity compared to the conventional decoder, where complexity is measured in terms of total number of decoding iterations over all decoding attempts. 3.2 Biased Incremental Decoding (BID) Having introduced ID, we propose a different way of retaining information from one decoding attempt to the next, BID. Instead of initializing messages, the estimates (or belief) of the variable nodes v from the previous decoding attempt are used as a-priori information, or bias, in the next decoding round. However, to avoid stalling of message passing due to positive coupling, a forgetting factor c needs to be applied. Therefore, all variable messages are initialized with the scaled bias at the start of each decoding attempt as follows for all = where E N(v), (3.1) 3 calculated with the equation (2.13) is the LLR of variable-node v in the last iteration of the Kth Cj (t — i)t decoding attempt and 0 a < 1, is used in the decoding attempt. We will call this technique BIDFL when a flooding schedule is used. 24 Chapter 3. Decoding with Early Termination for Rateless Codes 3.3 Combination of ID/BID with IDS We now combine ID/BID with IDS to synergize their computational advantages. Together, this accomplishes BP decoding with early termination and thus reduces complexity compared to the conventional BP decoding approach, i.e., message-reset decoding with flooding schedule (MRDFL). The combination of ID and BID with IDS results in two novel techniques for decoding rateless codes: IDIDS and BIDIDS. In IDIDS the decoder follows the ID procedure for propagating information from one decoding attempt to the next, as discussed in Section 2.5, and in each decoding attempt it uses the schedule defined by IDS to update the check nodes. Moreover, IDIDS also retains the ordering metric queue Q from the previous decoding attempt. BIDIDS applies the BID procedure for retaining information across successive decoding attempts, and employs IDS to update check nodes. We note that when applying IDS to the problem of decoding rateless codes, which are defined through their generator matrix rather than through their parity-check matrix as LDPC codes, an initial flooding iteration is required to initialize the node ordering metrics rq defined in (2.14). The pseudo code for the IDIDS and BIDIDS decoding algorithms is given in Table 3.1. Both methods employ the new hybrid stopping criterion described in the following section. 25 Chapter 3. Decoding with Early Termination for Rateless Codes Table 3.1: Pseudo code for IDIDS/BIDIDS algorithms for decoding Rateless codes 1: Collect 2: Perform one flooding iteration 3: Compute all r (2.14) and generate a sorted 4: // do one decoding attempt 5: Initialize messages according to (2.15) for IDIDS or (3.1) for BIDIDS 6: for £ 7: = received samples min 1 for k . = . . £max do // one iteration // one round of w 1.. n/w . Q updates 8: Perform w IDS updates 9: Calculate 10: if stopping criterion (3.4) is satisfied then go to line 15 j (3.3) 11: end for 12: Calculate 13: if stopping criterion (3.4) is satisfied then go to line 15 (3.2) 14: end for 15: if CRC is satisfied then go to line 18 16: Collect new received samples 17: Go to line 4 18: Terminate decoding 26 Chapter 3. Decoding with Early Termination for Rateless Codes 3.4 A Hybrid Stopping Criterion for IDIDS and BIDIDS Instead of using the metric in (2.16), we present a novel hybrid stopping criterion for terminating a decoding attempt in IDIDS and BIDIDS. This is necessary for the following reasons: 1. Though the metric t is useful for fixed-rate codes, it cannot be used for rateless codes because the value of P needs to be adjusted when the code length and rate are varied. 2. In IDS an iteration is a set of several successive updates. If a satisfactory reliability is reached for a fraction of an iteration, it would be efficient to stop the decoder at that point before completing a full iteration. Therefore, an update-sensitive criterion is necessary. The hybrid stopping criterion suggested in this section is composed of two inde pendent detectors: fl and £, each of which functions optimally in different regions of the instantaneous code rate R. Detector ?- measures the check-sum satisfaction difference over an interval of an iteration with the metric ICs (Cs”\ . which we define as (3.2) — Detector £, in contrast, employs the metric p which measures the repetitiveness of variable nodes being updated between two consecutive intervals of w updates of check nodes in one iteration. Let V be the set of all variable-nodes updated during 27 Chapter 3. Decoding with Early Termination for Rateless Codes interval number i. Similarly, let V be the set of variable nodes updated during the interval number i + 1. We define ii as - IVfl’4+iI — where I is the cardinality of (3.3) , Vj+ 1 For instance, in Figure 2.2, let w = 2 and suppose at interval i, the check nodes c 1 and c 2 are selected and hence the variable nodes (vi, v , v 2 , v 3 ) in their neighborhood are updated. During the next interval, 4 i + 1, the check nodes c 5 and c 7 are selected and the variable nodes (v , v 2 ) are 5 updated. Therefore, = 1/2 since only v 2 is repetitively updated (note that during w check-node updates, it is possible that some check nodes are selected more than once). Then we formally define our hybrid stopping criterion as [p yj-] or [ “c], (3.4) where ‘y- and F are user-defined thresholds independent of the code rate and length. Note that is sampled at every iteration whereas p, is sampled at every interval of w updates within one iteration. The hybrid stopping criterion essentially bridges the two very different convergence behaviors exhibited by the IDIDS/BIDIDS decoder in two distinct regions: • High-rate region: information is scarce and typically several iterations are exe cuted before the messages converge. Hence there is little incentive for stopping within a fraction of an iteration. Instead, a good indication of convergence is given by the fact that the status of check-sum satisfaction is not changing 28 Chapter 3. Decoding with Early Termination for Rateless Codes appreciably, which is detected by the metric • Low-rate region: convergence is rapid, often within a single iteration, and hence it is worthwhile to try and stop in a fraction of an iteration. This cannot be accomplished by . Instead, we need a more fine-grained detector. From sim ulations we observed that in the low-rate region, convergence implies repetitive updates confined to a small set of variable nodes, often in the form of a limitcycle. This phenomenon is sensed by the metric However, since the detector £ is not efficient in the high-rate region, where the order of message updates looks practically pseudo random, we need to use a hybrid combination of de tector 1-1 and £ as in equation (3.4) to achieve early termination with maximal efficiency. For simplicity, we may set -y = 0 and F = 1. This implies that checks for strict invariance in check-sum satisfaction whereas checks for an update limit-cycle. 3.5 Computational Complexity The ultimate goal of the work presented in this chapter is to reduce the overall cost of decoding rateless codes by reducing the number of BP iterations required. For fair comparison between IDIDS/BIDIDS and other existing techniques, we try to keep the cost per iteration equal. In both MRDFL and BIDFL/IDFL (FL refers to the use of a flooding schedule), message-update operations are the major contributor to the overall cost. However, in sequential techniques such as IDIDS/BIDIDS, on top of the message-update operations, the following two additional operations contribute to 29 Chapter 3. Decoding with Early Termination for Rateless Codes the overall cost: 1. Calculating the residual, r , associated with each check node cj. 1 2. Ordering these metrics in a queue Q. As for the problem of computing residuals, we employ the min-BP approximation = (3.5) fjsign (i,) 2 VeAf(C)’ v E.Af(c) v vj V$Vj to compute approximate residuals Im — m. and approximate ordering metrics r in (2.14), cf. [2]. The approximate calculation of ordering metrics reduces the cost substantially without degrading the error-performance which was validated by our simulations. The problem of ordering can also be handled with modest cost since we only need to sort the full queue Q then be inserted into Q progressively during the update process. 3.6 once at the start of the decoding process. New metrics can Simulation Results To evaluate the effectiveness of our suggested methods, we obtain results through Monte Carlo simulations. We discuss the results for simulation conducted for the LT and Raptor codes separately. The following two sections present the examined methods, the simulation settings and the results. 30 Chapter 3. Decoding with Early Termination for Rateless Codes 3.6.1 Simulations for LT codes In this section, we present simulation results to quantify the complexity savings achieved with the new decoding methods compared to the conventional MRDFL de coding applied to LT codes. As motivated above, we adopt the number of iterations until decoding is terminated as the measure of complexity. In order to separate the effects of informed scheduling and incremental decoding, we compare the complexities of the following decoding schemes: • MRDFL, IDFL: the conventional methods with flooding schedule. MRDFL will be the bench line, to which we compare our suggested methods. • BIDFL(a): the incremental decoding technique with our suggested method of retaining information from one attempt to another, biased incremental decoding (a is the scaling factor) • IDIDS (w): our method which combines incremental decoding with IDS (w is the update interval length) • BIDIDS(w,a): our method which combines our suggested biased incremental decoding with IDS (scaling factor a and update interval length w) As interesting examples, we assume the BSC with a capacity of C C = = 0.50 and 0.33 bit/(channel use), respectively, and the LT information-word length is chosen k = 2500. We employ the following degree distribution from [20, Table I]: 31 Chapter 3. Decoding with Early Termination for Rateless Codes Table 3.2: Values for parameters w and a used in simulations. BID IDIDS BIDIDS (x) = C=0.50 WI a N/A 0.2 500 N/A 500 0.05 C=0.33 WI a N/A 0.01 750 N/A 750 0.01 3 0.007969x + 0.493570x 2 + 0.166220x 8 5 + 0.056058x 4 + 0.082558x +0.072646x (3.6) 9 + 0.025023x 65 9 + 0.055590x’ +0.037229x 66 +0.003135x The values for the parameters w and a have been empirically optimized for this LT code to minimize the total decoding cost and are shown in Table 3.2 for C and C = = 0.50 0.33 bit/(channel use). In all cases, the first decoding attempt commences when k/C received samples are available, and a maximum number of 50 iterations is applied. First, we consider the bit-error rate (BER) performances for the different decoding methods, since a reduction in decoding complexity should not come at the cost of increased error rates. Figures 3.1 and 3.2 show the BERs for the different decoders as a function of the inverse instantaneous rate R’. It can be seen that there are hardly any differences between the BER performances, which makes a fair comparison based on decoding complexity fairly straightforward. We note that the relatively large distance to the respective capacity limits, e.g., an overhead of about 10 % is required 32 Chapter 3. Decoding with Early Termination for Rateless Codes 100 .l.U .!. . . :::::::::::.:::::::::::::::::::::::::::::::::::: — 2 — MRDFL IDFL BIDFL(0.2) — 10 a DIDS(500) 0 BIDIDS(500 0 05) ‘..,.‘ 11.1 io io’ 10 2 2.2 2.1 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3 hR Figure 3.1: BER as a function of R 1 for different decoding methods. BSC with C 0.50 bit/(channel use). at a BER of 102, can be reduced by increasing the word length k, while the errorfloor behavior is alleviated by using an outer code [4, 17, 20] (this will be evident with the Raptor code simulations in the next section). We now turn to the complexity comparison. Figures 3.3 and 3.4 plot the average total number of iterations as a function of R’ for the BSC with C C = 0.50 and 0.33 bit/(channel use), respectively. Considering the curves for MRDFL and IDFL we observe that ID can lower the number of iterations until termination by up to a factor of 6 compared to MRD. Similar complexity reductions are achieved with BID for the case of C for the case of C = = 0.50 bit/(channel use), while notably smaller gains are seen 0.30 bit/(channel use). 33 Chapter 3. Decoding with Early Termination for Rateless Codes 100 I 4 — — ——fr”- IDFL — — 10 -l :: ci:: ILl m i02 * IDIDS(750) p BIDIDS(750,0.05) .:::::::::::::::::::x::: :::::::::::::::::::.:::::::::: %. 4 1o 3 3.25 3.5 3.75 4 4.25 4.5 hR Figure 3.2: BER as a function of 1 R for different decoding methods. BSC with C = 0.33 bit/(channel use). 34 Chapter 3. Decoding with Early Termination for Rateless Codes Table 3.3: Improvement factors in terms of number of iterations for the different algorithms compared to MRDFL. BSC with C 0.33 bit/(channel use). R’ 3.3 3.9 4.5 IDFL 1.1 4.6 6.1 BID(0.01) 1.0 1.6 1.6 IDIDS(750) 4.7 47.7 56.0 I BIDIDS(750, 0.01) 4.0 7.3 I 7Th1 Table 3.4: Improvement factors in terms of number of iterations for the different algorithms compared to MRDFL. BSC with C = 0.50 bit/(channel use). R’ 2.2 2.6 3.0 IDFL 1.3 5.8 6.3 BID(0.2) 1.3 4.7 4.8 I IDIDS(500) 4.8 57.1 59.8 BIDIDS(500, 0.05) 3.4 10.4 10.1 I Complexity is further reduced if ID and BID are combined with IDS. In particular the new IDIDS method yields another improvement factor of 10, while the complexity gain with the BIDIDS method saturates earlier. We attribute this to the fact that freezing messages according to (2.15) allows a more structured retrieval of information than biasing in (3.1). We note that the new stopping criterion (3.4) and its ability to stop at a fraction of an iteration when employed with IDS are crucial for accomplishing early termination. Tables 3.4 and 3.3 list the complexity reduction factors (in iterations) for the different algorithms when compared with MRDFL. Improvement factors in the range of 4—60 can be achieved depending, through the instantaneous rate, on the error-rate performance (see Figures 3.1 and 3.2). 35 Chapter 3. Decoding with Early Termination for Rateless Codes 102 0 : : o S . • 4 . — . 4 9 . . oo y”4.._... ,..j_..._.._ Th.--.-....._. - .- V o 0 : . : 0) •O 10° - MRDFL ——fr—IDFL — —0- — BIDFL(0.2) . DIDS(500) . O BIDIOS(500,0.0S) _i 10 2 2.1 2.2 2.3 2.4 2.5 I 2.6 2.7 2.8 2.9 hR Figure 3.3: Complexity in terms of number of iterations as a function of R’. BSC with C = 0.50 bit/ (channel use). 36 Chapter 3. Decoding with Early Termination for Rateless Codes 10 2 :: Cl) C 0 a) G... c::::::N %__0_ 0 101 C .1-’ C’) 0 0 4 \.J\ -,•. C -..- 0 C-) a) 100 --O--MRDFL a) > —+-—IDFL — —0- — BIDFL(0.2) • IDIDS(750) 0 BIOIDS(750,0.05) 10_I 3 3.25 3.5 3.75 4 4.25 4.5 hR . BSC 1 Figure 3.4: Complexity in terms of number of iterations as a function of R with C = 0.33 bit/(channel use). 37 Chapter 3. Decoding with Early Termination for Rateless Codes 3.6.2 Simulations for Raptor Codes In this section, we show quantitative results for the complexity reduction achieved by the proposed IDIDS method with the stopping criterion (3.4) when applied to the full Raptor code. Our measure of complexity is the total number of iterations until decoding is successful, i.e., cyclic-redundancy check is positive. Again we try to separate the effects of informed dynamic scheduling and incremental decoding, so we compare the complexities of the following decoding schemes: • MRDFL(Lmax, T) • IDFL(Lmax, T) • IDIDS(Lmax, T) where T is the interval in number of samples between successive decoding attempts and Lm is the maximal number of iterations per attempt. We note that L = was applied in previous works for Raptor codes (e.g. [8]), where L is the actual number of iterations in a decoding attempt. For a fair comparison with IDIDS, we apply the check-sum satisfaction detector fl to stop decoding attempts in MRDFL and IDFL. In IDIDS, the interval length w = 100 is chosen. As benchmark scheme, we consider MRDFL(100,100) without any termination, i.e., L = = 100, cf. [8]. As an interesting transmission example, we assume the BSC with capacity C = 0.50 bit/(channel use). The Raptor code consists of a rate-0.95 regular LDPC code and an LT code generated using the degree distribution in (3.6). The input-word length is chosen k = 9500 bits, and the first decoding attempt commences when k/C received samples are available. 38 Chapter 3. Decoding with Early Termination for Rateless Codes First, we make sure that the different BP schedules and early termination do not affect the rate performance of Raptor codes. To this end, Figure 3.5 shows a scatter plot for the achieved rate for 50 transmitted words (i.e., the rate R = k/n for which the transmitted word was decoded correctly). That is, for each point the x-value is the rate achieved with the benchmark scheme, MRDFL(100,100) without early termination, and the y-value is the rate achieved with one of the other decoding schemes for the same transmitted data and received samples. We consider both T = 100 and T = 1 for the ID schemes, and set Lm = T to fix the ratio T/Lm, as in [8]. It can be seen that all measured points lie very close to the 45-degree line, which clearly manifests the equivalent performance achieved with the different decoders. In case of IDFL, this is consistent with the findings in [81, according to which only the ratio T/L determines the rate performance (assuming L = Lmax in [8]). Next, we compare decoding complexities. Figure 3.6 shows the scatter plot for the required number of iterations for the same 50 transmissions and decoding schemes that were considered in Figure 3.5. In addition, lines with different slopes are included to emphasize the approximate multiplicative gains in terms of complexity reduction. A number of observations can be made. Firstly, the complexity of MRDFL can be reduced by a factor of two due to check sum-satisfaction stopping. This is interesting in its own right, since only MRDFL without stopping was used in [8] for a comparison with IDFL. Secondly, we observe that IDFL accomplishes further notable complexity savings. IDFL (1,1) is somewhat advantageous over IDFL(100,100), which again is consistent with [8], where the use of L = 1 was advocated for incremental decoding. Thirdly, it can be seen that the 39 Chapter 3. Decoding with Early Termination for Rateless Codes proposed IDIDS is by far the most efficient decoding scheme. The total number of iterations is only 13%, 27%, and 46% of those required for MRDFL without stopping (not shown in Figure 3.6), MRDFL with stopping, and IDFL(1 ,1), respectively. We note that the new stopping criterion (3.4) and its ability to stop at a fraction of an iteration when employed with IDS are crucial for accomplishing early termination and hence yielding these considerable reductions in complexity. Furthermore, since the number of message updates in IDIDS is adapted to the amount of new information available during each decoding attempt, the choice of the interval T between successive decoding attempts is not critical. 40 Chapter 3. Decoding with Early Termination for Rateless Codes 0.48 o a) 0 D 0.47 ÷ a> MRDFL(100,100), IDFL(1 00,100), IDFL(1,1) IDIDS(100,100) IDIDS(1,1) ÷ a) -t .0 0.46 x 0 0 x a> + E 0.45 0 x * 0 > a, 0 a) N Cu a) r 0 :::,,,,,.., 0.42 0.43 x 0.47 0.46 0.45 0.44 Realized rate for MRDFL(1 00,100) [bit/channel use] 0.48 Figure 3.5: Scatter plot for the realized rate for various methods. Arguments (Lmax, T) mean that a decoding attempt is made every T newly received samples with L Lmajc iterations. Check-sum satisfaction stopping for MRDFL/IDFL. IDIDS uses early termination with (3.4). x-axis: MRDFL(100,100) with L = Lm. 41 Chapter 3. Decoding with Early Termination for Rateless Codes 0 0 0 0 0 E 0 0 > 0 0 C.) 0 0 I- 0 500 1000 1500 2000 Total decoding cost for MRDFL(100,100) [# of iterations] Figure 3.6: Scatter plot for the total cost in number of iterations until successful decoding. Arguments (Lmax, T) mean that a decoding attempt is made every T newly received samples with L Lm iterations. Check-sum satisfaction stopping for MRDFL/IDFL. IDIDS uses early termination with (3.4). x-axis: MRDFL(100,100) with L Lm. 42 Chapter 4 Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication 4.1 Introduction Free Space Optics (FSO) refers to the transmission of modulated visible or infrared (IR) light beams through the atmosphere for optical communication. In this sense, it is similar to fiber, but instead of enclosing the data stream in a glass fiber, FSO uses light beams to transmit data through air. FSO communication systems have received renewed interest due to their low deployment costs and potential use in highthroughput applications like last mile access [1]. FSO transmits eye-safe light beams from one point to another using low-power IR lasers in the teraHertz spectrum. FSO light beams are directed to highly sensitive photodetector receivers. These receivers are telescopic lenses which can collect the photon stream carrying digital data used in applications such as video transmission, radio signals and internet connectivity. Transmission is directional, making it more secure than RF technologies though the 43 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication two points, transmitter and receiver, have to be within line-of-sight of each other. FSO communication systems technology has been in development since the 1960s and was initially used in aerospace and military applications. The recent demand for higher bandwidth resulted in more interest in FSO systems and their applications. However FSO systems suffer from many factors, the most prominent of which are: • Atmospheric turbulence, also known as scintillations: this results in light vari ations at the receiver side due to incoherence in the temperature and pressure of atmosphere [14]. • Scattering: this phenomenon is caused by fog. This is the most destructive factor impeding the development of FSO systems [14]. The above factors are typically modeled as a probabilistic process with carefully chosen distributions [15, 25]. To combat the deterioration of signal quality due to adverse atmospheric con ditions, the use of error control codes and interleaving has been proposed in [3]. However, since temporal diversity is hardly available for high-speed terrestrial FSO links unless very large interleavers are employed, the utilization of spatial diversity at both the transmitter and receiver has been studied in [12, 23] as a means to mitigate the fluctuation of signal strength due to atmospheric turbulence. In this context, the use of space-time coding has been advocated in [6] and [26] for optical communication. However, none of the above diversity schemes can tolerate prolonged extreme weather conditions, in particular turbulence and scattering, which limits the availability of FSO links. 44 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication The only way to perform well when the optical channel suffers prolonged impair ments is to use media diversity, as was proposed in e.g. [10] and [1], where an RF channel is used in conjunction with the FSO channel. The practical heuristic for such hybrid FSO/RF systems is that fog and rain, which affect FSO and R,F, do rarely occur simultaneously [10]. Commercially available hybrid solutions use the RF link as a hot-standby backup for the FSO link, to be used only when the FSO channel is inoperative [1]. Needless to say, this approach to hybrid communication is inefficient because of duplication of the messages on the RF and FSO channels, since such rep etition codes perform far from the overall system capacity. This inefficiency can be mitigated only via a non-trivial channel code for the overall hybrid channel. There are two ways to approach this coding problem: 1. In the first approach, one assumes that the transmitter knows the exact channel conditions on both the RF and FSO links, and hence selects the best possible multiplexing ratio (which defines the portion of data to be transmitted on each link) and code rates to exploit the capacity of the hybrid channel under those specific channel conditions. Fixed-rate codes, such as LDPC codes, can be used in this case. This approach, however, relies on significant feedback from the receiver to the transmitter and reconfigurable coding and/or modulation schemes (adaptation of signal bandwidth is typically not a practical option for a hybrid FSO/RF system). Recently, [22] (cf. also [21]) has presented such a coding scheme based on non-uniform punctured LDPC codes, where the code rates for FSO and RF transmission are adjusted according to the instantaneous channel conditions. 45 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication 2. The second approach, which we propose in this chapter, aims to achieve a closeto-optimal throughput under a broad spectrum of channel conditions, while using very little feedback. Thus we do not adapt the transmitter to change the relative utilization of the sub-channels (fixed multiplexing ratio). However our receiver does adapt to the channel variations and, by sending infrequent low-rate feedback, achieves a throughput close to capacity under any channel condition with the given multiplexing ratio. We achieve this robustness by using a practical implementation of rateless Fountain codes [13]. In particular, we provide simulative evidence that a single moderate-length Raptor code design [20] enables us to closely approach the associated capacity limit of the hybrid FSO/RF channel under varying channel conditions. Our results are in line with the findings in [4, 17] that Raptor codes designed for the binary erasure channel perform remarkably well for BSC and AWGN channels too, even though they are provably not universal for these classes of channels. Finally, we remark that the proposed rateless coding scheme still leaves the door open for the possible adaptation of the transmitter multiplexing ratio. For example, the constellation size for RF transmission could be modified for coarse adaptation to the channel condition, while rateless coding accomplishes adaptation on a finer (bit-wise) grain. 46 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication Figure 4.1: Block diagram of the proposed coded hybrid FSO/RF transmission sys tem. 4.2 Transmission Model and Proposed Coding Scheme In this section, we first introduce the channel model and signal schemes used for hybrid FSO/RF transmission and then describe the proposed coding scheme. The block diagram of the coded hybrid transmission system is shown in Figure 4.1. 4.2.1 Transmission Model The transmission model consists of a transmitter, channel and a receiver and is de scribed in details in the following sections. 4.2.1.1 Transmitter The considered hybrid system consists of two transmitter-receiver pairs, one for FSO transmission and another for RF transmission.’ Both transmitters receive a bit stream from a binary encoder, which is specified in detail in Section 4.2.2. The two trans mitters can be described as follows: • The RF transmitter maps mpy = (M) binary symbols to an M-ary quadra 2 log ‘Extensions to multiple FSO or RF transceivers are straightforward. 47 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication ture amplitude modulation (M-QAM) signal point XRF using Gray mapping. The QAM constellation is typically non-binary, i.e., M > 2, for bandwidthefficient transmission. The signal elements 1/TRF XRF are sent with a baud rate of symbols per second using conventional pulse shapes such as a root-raised cosine. • The FS0 transmitter employs intensity modulation with on-off keying (00K), which is the prevalent modulation format for FSO communication. The signal elements are XFSO E {O, 1} and the optical signal intensity is PFSO during the on- period and zero during the off-period, each of which is of length TFso. Obviously, one data bit is represented by one 00K symbol, i.e., 4.2.1.2 mFso = 1. Channel and Receiver The FSO receiver applies direct detection. To formulate the transmission model, we adopt the often used photon-count model for direct detection with an ideal photode tector where the detector output parameter ILFSO TFS0 has a Poisson count distribution with mean which is given by PFSO = I 8 YFSOK + Kb for for (Kb XFSO = 1 (4.1) XFSO=O The constants K 8 and Kb are given by 8 K = PFsoTFso/(hf), (4.2) 48 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication Kb where ij iS (4.3) PbT/(hf), 77 the efficiency of the photodetector, f denotes the center frequency of the transmission, h is Planck’s constant, and Pb represents the power from background radiation incident on the photodetector [5], [23]. The variable Fso accounts for signal attenuation and random signal intensity fluctuation due to scintillation. While a number of statistical scintillation models exist in the literature [23, 25] and also attenuation is time varying due to changing weather conditions, e.g., conditions of fog and smoke, in the context of this work we are content to notice that the coherence time for gFso is much larger than the time horizon for one codeword. The RF system uses a line-of-sight link in the microwave or millimeter wave band and it is therefore well modeled by the classical AWGN channel with a gain factor 9RF. Again, the time variation of gRF due to e.g. occurrence of rain is extremely slow compared to the transmission speed in units of codewords. The RF receiver consists of a classical matched-filter front-end followed by baud-rate sampling. That is, the sampled receiver output in the equivalent complex baseband is written as TRF where gp = variance F,., RFe = = gRFXRF denotes the complex channel gain, 4/TaF and J4 is (4.4) + RF, flRF is complex AWGN with the one-sided noise power spectral density. 0 and rpj’ along with the The FSO/RF receiver passes the received samples r parameters (gF’soK , Kb) for the FSO channel, and (gRF, P) for the RF channel to 3 49 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication the bit-metric calculator (see Figure 4.1). 4.2.2 Proposed Coding Scheme 4.2.2.1 Encoder and Multiplexing The hybrid FS0/RF system employs a single encoder of a binary rateless code. More specifically, we apply the Raptor codes which were introduced in Chapter 2, whose encoder was discussed in Section 2.2.3. The code bits are then demultiplexed into two bit-streams, one entering the RF QAM modulator and the other one being input to the FSO 00K modulator. To be more specific, let us define the positive, mutually prime integers flFSO and RF mFso/TFso RF Then, out of a block of 0 t = (4 5) mRF/TRF FSO + RF bits , 4 [cj, c bits are passed to the FSO modulator and the remaining ..., RF The formulation in (4.5) makes the mild assumption that be expressed ij, cj+ _ 0 the first FSO bits are RF modulated. mFsoTaF/(mRFTFSO) can as a rational number. Encoding of the message ..., vkl [vi, 2 v , is terminated when a positive acknowl edgment of successful decoding has been received. 4.2.2.2 Metric Computation and Demultiplexing Based on the received samples and the channel parameters, decoding metrics in the form of log-likelihood ratios are generated. 50 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication For FSO transmission with the channel and detector model described in Sec tion 4.2.1, the log-likelihood ratio (LLR) associated with AFS0 = rFso log (i + — 0 £ mRF — = max (IraF 1, where Xe,& — gRFXRFI ) — e (4.6) XRF max (IraF — is given by gRFXRFI XRFEX,1 denotes the subset of the which the £th bit of the label is equal to b can be written as . 3 K For RF transmission, the LLR for the £th bit mapped to ARF,e XFSO ) , QAM signal constellation for {0, 1}. According to the demultiplexing of code bits described above, groups of and (4.7) are multiplexed into one stream of LLRs [)i, )2, ..., )FSO which then is forwarded to the decoder (see Figure 4.1). 4.2.2.3 Decoder The decoder for the rateless code collects LLRs ) progressively and a first decoding attempt is made when it is believed that sufficient information for successful decoding has been collected. A good estimate for the number m of collected LLRs is given by k(1±e) (4.8) where CH denotes the constrained capacity of the hybrid FSO/RF channel as defined in Section 4.3, and e> 0 is an overhead factor which accounts for the suboptimality 51 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication of the (finite-length) Raptor code with respect to capacity. Decoding is performed using the well-known BP on the factor graph as discussed in Section 2.3. The variable nodes cj are initialized with the LLRs )‘j, 1 i <n, and extrinsic likelihood messages are exchanged between the variable and check nodes accordingly to a pre-defined schedule. If the decoded message [ci, 2, ..., VJ] after BP decoding is deemed unreliable, which could be determined by either making use of a cyclic redundancy check (CRC) code or estimating the bit-error rate (BER) based on the final LLRs [7], a new decoding attempt is scheduled after a new batch of nj, samples has been received. The value of n will depend on the update schedule applied for BP decoding. Notice that we only use MRDFL for decoding in this Chapter. Once the decoded message 2, .., ] is deemed correct, decoding is termi nated and a 1-bit acknowledgment signal is transmitted to the encoder. 4.3 Constrained Capacity of the Hybrid FSO/RF Channel In order to benchmark the proposed coding scheme, we now specify the information theoretic limit for the hybrid FSO/RF channel. To this end, we first note that the FSO and RF modulation formats are not optimized for maximal mutual information and assumed constant regardless of the channel condition. While the former assumption is rooted in the practical constraints for FSO and RF transmission technology, the latter could be relaxed assuming that 52 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication a more powerful feedback channel is available in order to perform adaptation of the signal constellation for the RF channel. However, as long as the size M of the QAM constellation is chosen such that maF is at least 1 bit above the Shannon capacity of the RF AWGN channel, hardly any gains are achievable with a larger alphabet size [161. Hence, choosing a reasonably large constellation size, say 64QAM, is suffi ciently optimal. Secondly, we note that we are not interested in the capacity in the sense that coding with a rate strictly lower than capacity achieves an arbitrarily low error rate for every FSO and RF channel realization, i.e, every (gFsoKs, Kb) and (gaF’, Pa). Instead of this compound channel capacity we are interested in the capacity where the transmitter is allowed to adapt its codebook according to the current channel state. Let us define the states SFSO, 8 RF, and SH of the FSO, RF, and hybrid FSO/RF channel as follows: SFSO = SRF 8 , Kb] [gFsoK (4.9) 9RFI/Pn (4.10) [SFSO SRFI (4.11) = SH Furthermore, let the mutually prime integers — )RF 7 ?]Fso TRF TFS0’ and jaF be defined by (4 12) 53 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication i.e., o/py is the relative frequency of FSO and RF channel usages. Then, since the FSO and RF channels are used in parallel, the channel capacity for given SH can be written as CH(sH) = —-— )FSO [FsoCFso(sFso) + ??RFCRF(SRF)1 (4.13) , where normalization with 1 )FSO renders the capacity unit “bit per FSO channel use”, and CFS0 (SFSQ) and CRF (SRF) respectively denote the constellation-constrained ca pacities of the FSO and RF channel in bit per FSO and RF channel use for a given channel state. These are given CFso(sFso) by = 1 — IE {1 + (4.14) exp ((_1)0AFso)}, mRF CRF(sRF) = mRF — E1E{i +exp((—1)AaF,e)} where be denotes the £th bit in the label of XRF, , (4.15) and the expectation IE{.} is with respect to the joint probabilities p(rFso, ZFSo) and p(rRF, be), respectively. We note that neither CFS0 (sFSo) nor CRF (SRF) lend themselves for closed-form expressions, and, hence, can be evaluated using Monte Carlo integration. 4.4 Simulation Results In this section, we present numerical results and simulative evidence that the proposed coded hybrid FSO/RF scheme performs close to the information-theoretic limits. The considered hybrid system employs 64QAM modulation for RF transmission, which is 54 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication practically optimal as long as CRF(sRF) 5 bit/(RF channel use) [16]. As specified in Section 4.2.1.1, 00K modulation is used for FSO signalling. Furthermore, we assume a wavelength of 1550 nm, a photodetector efficiency of background radiation of PbT photon count K = = i = 0.5, and a normalized —170 dBJ [23], which yields the average background , 3 39. The FSO channel quality is adjusted through variation of K and the RF channel condition is determined by the signal-to-noise ratio (SNR) given by SNRRF— E{IxRF gaFI } 2 D 4.16 I-n For simulations, we apply a Raptor code consisting of a rate-0.95 regular LDPC code and an LT code generated using the degree distribution given in equation 3.6. The information word length is chosen as k = 9500, which renders the codeword length n moderate in all but very unfavorable channel conditions (simultaneously for both FSO and RF channel). We emphasize that the application of an off-the-shelf Raptor code is motivated by the results in [4, Section IV] and [17] for binary output symmetric channels and the lack of a universally optimal Raptor code. Decoding is continued until the correct codeword has been found, which emulates the use of a CRC outer code. The number n of check bits required for successful decoding is recorded and the realized rate R is determined according to R=°’fl’ ‘lFsO (417) whose unit is bit per FSO channel use. 55 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication We are mainly interested in showing the ability of the coded hybrid FSO/RF system to perform consistently close to the capacity limit for 1. different FSO and RF channel conditions (SFSO, SRF) and thus different capac ities CFso(sFso) and CRF(8RF), and 2. for various relative frequencies of channel usage (so, mF) and thus different multiplexing ratios. For this purpose, we first consider different combinations of capacities CFso (SFSO) and CRF(s), and adapt the relative frequencies of usage lFso and iu’ such that the total hybrid FSO/RF capacity CH(sH) from (4.13) is always 1 bit/(FSO channel use). For example, for CFS0(sFso) = 2.0 bit/(RF channel use), we use o 0.9 bit/(FSO channel use) and = 20 and F CRF(SRF) = 1. Table 4.1 summarizes the parameters for the 54 considered setups. Figure 4.2 shows the realized rate R (in the form of a surface) from (4.17), averaged over 200 transmitted information words for each parameter set from Table 4.1, as a function of the capacities CFS0 (SFSO) and CRF(sRF) of the component channels. We observe that the performance surface is nearly flat and that the capacity limit is closely approached by realized rates of about 90 % of capacity. That is, the same rateless code design performs consistently well for very different mixtures and qualities of FSO and RF channels. From this we conclude that the proposed coded system makes effective use of available mutual information regardless of whether it is provided through a Poisson or a Gaussian channel. In a second experiment, we keep the relative frequency of FSO and RF channel usages constant, and vary the capacities CFso (SFSO) and CRF (SRF) such that a rel 56 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication Table 4.1: Considered channel capacities CFSO, Cp and channel usage ratios ?7Fso/I7RF defined in (4.12) for hybrid FSO/RF transmission such that the total ca pacity CH = 1 bit/(FSO channel use). The corresponding realized rates are shown in Figure 4.2. (CRF in [bit/RF channel use] and CFS0 in [bit/FSO channel use]) ! ?j 0.1 0.2 0.3 15T 0.5 0.6 15T C.) 0.8 0.9 CRF 1 9/8 5/4 7/5 5/3 2/1 5/2 10/3 5/1 10/1 2 9/4 5/2 20/7 10/3 4/1 5/1 20/3 10/1 20/1 3 10/3 15/4 13/3 5/1 6/1 15/2 10/1 15/1 30/1 4 9/2 5/1 23/4 20/3 8/1 10/1 27/2 20/1 40/1 5 11/2 25/4 14/2 25/3 10/1 25/2 33/2 25/1 50/1 6 20/3 15/2 17/2 10/1 12/1 15/1 20/1 30/1 60/1 atively wide range of overall capacities C - (SH) is scanned. In this way we examine 1 the code’s ability to self-tune to time-varying channel conditions which lead to differ ent hybrid channel capacities. Twelve specific parameters combinations are given in Tables 4.2 and 4.3. For each combination we calculate the hybrid channel capacity CH(sH) in (4.13) and simulate the realized rate R in (4.17). Figures 4.3 and 4.4 show the scatter plot of R versus CH(sH). Also included is the 45-degree line, on which the measured points would come to lie if the realized rate exactly equaled the respective capacity value. It can be seen that all measured points are fairly close to the 45- degree line. While the variations among the rate points for a given capacity CH (SH) are alike to the variation of the per-codeword error rate for fixed-rate codes, we note that an increase in capacity results in a very similar increase in realized rate. To gether with Figure 4.2 these results show the robustness of the rateless-coded hybrid FSO/RF systems in performing under different channel conditions and approaching 57 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication A a) U) a) 0.8 C C a) 5 0.6.. 0 Cl) U (5 0.4. 0.2. a) N 0 6 <—— C RF (bit/channel use) 0 0 0 (bitlchannel use) C Figure 4.2: Surface plot for the realized rates when CH and the parameters given in Table 4.1. = ——> 1 bit/(FSO channel use) the respective capacity limit. The scenarios for the parameters in Tables 4.1, 4.2 and 4.3 were chosen to point out the suitability of rateless coding for hybrid FSO/RF transmission, and not so much to show the benefit of joint transmission compared to switching between FSO and RF transmission. The latter follows immediately from a comparison of CH(sH) and max{CFs0 (SFSO), CRF (SRF) }, and it could be formulated in terms of outage probabil ity, if a certain minimal rate needs to be guaranteed, or in terms of average capacity difference, if throughput is of interest. The results presented in this section have pro vided evidence that such a capacity-based analysis is justified since CH (SH) is indeed the appropriate performance parameter for the proposed coded system. 58 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication Table 4.2: Different parameter combinations simulated for the scatter plot in Fig ure 4.3. (CRF in [bit/RF channel use], CFSO and CH in [bit/FSO channel use]) Combination CRF 0 C 1 2 3 4 5 6 2.00 3.00 4.00 4.2O 5.00 6.00 0.30 0.50 0.70 080 0.90 0.90 ?i’so 1 1 1 1 1 1 6 6 6 6 6 6 0.63 iThil 1.37 1.50 1.73 1.90 Table 4.3: Different parameter combinations simulated for the scatter plot shown in Figure 4.4. (Cap’ in [bit/RF channel use], C o and CH in [bit/FSO channel use]) 5 Combination Cru’ CFSO 1 2 3 4 5 6 2.00 3.00 4.00 4.20 5.00 6.00 0.30 0.50 0.70 0.80 0.90 0.90 2 2 2 2 2 2 ‘so CH 6 6 6 6 6 6 0.97 1.50 2.03 2.20 2.57 2.90 59 Chapter 4. Rateless Coding for Hybrid Free-Space Optical and Radio-Frequency Communication a, 0 a, C C a, 0 0 C,) U a, Ca Ca a, Figure 4.3: Scatter plot of realized rate versus capacity CH for the parameter combi nations given in Table 4.2. The 45°-line is included as a reference. 60 Chapter 4. Rateless Coding for Hybrid Free—Space Optical and Radio-Frequency Communication 3 Combination c Combination + Combination x Combination o Combination t Combination 1 a) 0 2.5 a) C C C) 0 2 I 2 3 4 5 6 I. 1 Cl) U 0 - a) 0 0 a) 0.5 1 1.5 2 2.5 3 CH (bits/FSO channel use) Figure 4.4: Scatter plot of realized rate versus capacity CH for the parameter combi nations given in Table 4.3. The 45°-line is included as a reference. 61 Chapter 5 Conclusions and Future Work In this thesis, we developed a method for decoding rateless LT and Raptor codes. We further applied these rateless codes to hybrid free-space optical and radio-frequency communication. First we reviewed rateless codes, namely LT and Raptor codes, then discussed the existing decoding algorithms in the second Chapter. Then, we investigated the prob lem of efficient decoding of rateless codes. It was noted that faster convergence and early termination of decoding attempts are the key to reducing decoding complexity. To this end, we proposed two new decoding methods, namely BIDIDS and IDIDS, which build on the ideas of incremental decoding and informed dynamic scheduling, that improve convergence of the BP process. Furthermore, in order to execute early termination, we formulated a new hybrid stopping criterion, which is particularly suited for rateless codes when decoded with the informed dynamic schedule. As for LT codes, simulations for different channel capacities showed that complex ity improvement factors of up to 60 are possible with IDIDS/BIDIDS, without any degradation in error-rate performance. For Raptor codes, on the other hand, simula tion results for the example of the BSC with a capacity of 0.5 bit/(channel use) have shown that the proposed IDIDS affords significant savings in decoding complexity 62 Chapter 5. Conclusions and Future Work without sacrificing performance in terms of realized rate. In Chapter 4, we proposed the application of rateless codes for hybrid FSO/RF transmission systems. Hybrid FSO/RF systems combine the best of two worlds, i.e., robustness of FSO to rain and RF to fog and atmospheric turbulence, and thus render the system performance robust to short and long-term variations of the FSO and RF transmission channel. This is critical for the adoption of FSO as a reliable high-speed access technology. The distinct feature of the proposed scheme is that it enables to realize (most of) the potential advantages due to parallel FSO and RF channels without the need for redesign or reconfiguration of the transmitter-side coding or modulation. We have established the pertinent information-theoretic limits, and have provided simulative evidence that these limits are well approached with practical offthe-shelf Raptor code designs over wide ranges of channel conditions. We thus believe that the proposed scheme is suitable for practical implementation of efficient hybrid FSO/RF transmission systems. For future work, the rateless coding scheme proposed in this thesis for FSO/RF systems can be investigated at more depth. For instance, the developed IDIDS/BIDIDS methods can be applied to decoding Raptor codes used in the proposed hybrid FSO/RF scheme. Also, adaption of the transmitter multiplexing ratio to the chan nel can be explored. In addition, the constellation size for the RF transmission can be modified for coarse adaptation to the channel condition, while rateless coding accomplishes adaptation on a finder (bit-wise) grain. 63 Bibliography [1] S. Bloom and W. Hartley. The last-mile solution: Hybrid FSO radio. In Whitepa per, AirFiber Inc., May 2002. [2] A.I. Vila Casado, M. Griot, and R. Wesel. Informed dynamic scheduling for belief-propagation decoding of LDPC codes. In Proc. of IEEE mt. Conf Corn mun. (ICC), Glasgow, UK, June 2007. [3] V.W.S. Chan. Coding for the turbulent atmospheric optical channel. IEEE Trans. on Communications, 30:269—275, January 1982. [4] 0. Etesami and A. Shokrollahi. Raptor codes on binary memoryless symmetric channels. IEEE Trans. on Information Theory, 52(5):2033 — 2051, May 2006. [5] R.M. Gagliardi and S. Karp. Optical Communications. John Wiley & Sons, New York, 1976. [6] S.M. Haas, J.H. Shapiro, and V. Tarokh. Space-time codes for wireless opti cal channels. In Proc. IEEE International Symposium on Information Theory (ISIT), page 244, Washington, DC, USA, June 2001. 64 Bibliography [7] P. Hoeher. Adaptive modulation and channel coding using reliability informa tion. In Proc. of 5th International OFDM- Workshop, pages 14.1—14.4, Hamburg, Germany, September 2000. [8] K. Hu, J. Castura, and Y. Mao. Reduced-complexity decoding of Raptor codes over fading cannels. In Proc. of IEEE Global Commun. Conf (GLOBCOM), San Francisco, CA, USA, Nov.-Dec. 2006. [9] H. Kfir and I. Kanter. Parallel versus sequential updating for belief propagation decoding. Physica A, 300:259—270, 2003. [10] I. I. Kim and E. Korevaar. Availability of free space optics (FSO) and hybrid FSO/RF systems. In Proc. SPIE, Optical Wireless Communications 1V volume 4530, pages 84—95, Denver, CO, USA, August 2001. [11] F.R. Kschischang, B.J. Frey, and H.A. Loeliger. Factor graphs and the sumproduct algorithm. IEEE Trans. on Information Theory, 47:498 — 519, February 2001. [12] E. Lee and V. Chan. Optical communication over the clear turbulent atmospheric channel using diversity. IEEE Journal on Selected Areas in Communications, 22:1896—1906, November 2004. [13] M. Luby. LT codes. In Proc. 43rd Annual IEEE Symp. on Foundations of Comp. Sc. (FOCS), pages 271—280, Vancouver, BC, Canada, November 2002. 65 Bibliography [14] A.K. Majumdar and J.C. Ricklin. Effects of the atmospheric channel on freespace laser communications. In Proc. SPIE, Free-Space Laser Communications V, volume 5892, pages 58920K1—58920K16, San Diego, CA, USA, July 2005. [15] S.S. Muhammad, P. Kohidorfer, and E. Leitgeb. Channel modeling for terrestrial free space optical links. In Proc. 7th International Conference on Transparent Optical Networks (ICTON), volume 1, pages 407— 410, Barcelona, Spain, July 2005. [16] L.H. Ozarow and A.D. Wyner. On the capacity of the Gaussian channel with a finite number of input levels. IEEE Trans. on Information Theory, 36(11):1426— 1428, November 1990. [17] R. Palanki and J.S. Yedidia. Rateless codes on noisy channels. In Proc. IEEE International Symposium on Information Theory (ISIT), page 37, Chicago, IL, USA, June-July 2004. (see also www.merl.com/papers/TR2003-124/). [181 P. Radosavljevic, A. de Baynast, and J.R. Cavallaro. Optimized message passing schedules for ldpc decoding. In Proc. 39th Asilomar Conf. Signals, Systems and Computers, pages 591—595, San Antonio, TX, USA, 2005. [19] T. Richardson and R. Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Trans. on Information Theory, 47:595 — 618, February 2001. [20] A. Shokrollahi. Raptor codes. IEEE Trans. on Information Theory, 52(6):2551 — 2567, June 2006. 66 Bibliography [21] S. Vangala and H. Pishro-Nik. A highly reliable FSO/RF communication sys tem using efficient codes. In Proc. IEEE Global Telecommunications Conference (GLOBECOM), pages 2232—2236, Washington, DC, USA, November 2007. [22] S. Vangala and H. Pishro-Nik. Optimal hybrid RF-wireless optical communica tion for maximum efficiency and reliability. In Proc. 41st Annual Conference on Information Sciences and Systems (CISS), pages 684—689, March 2007. [23] S.G. Wilson, M. Brandt-Pearce, Q. Cao, and J.H. Leveque, III. Free-space op tical MIMO transmission with Q-ary PPM. IEEE Trans. on Communications, 53(8):1402 — 1412, August 2005. [24] E. Yeo, P. Pakzad, B. Nikolic, and V. Anantharam. High throughput low-density parity-check decoder architectures. In Proc. of IEEE Global Commun. Conf. (GLOBCOM), pages 3019 — 3024, San Antonio, TX, USA, Nov.-Dec. 2001. [25] X. Zhu and M. Kahn. Free-space optical communication through atmospheric turbulence channels. IEEE Trans. on Communications, 50(8):1293—1300, August 2002. [26] Z. Zhuang, D. Ma, and J. Wei. Diversity coding scheme for wireless optical communication with direct detection. lEE Electronics Letters, 40:407— 410, 2004. 67
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Efficient decoding and application of rateless codes
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Efficient decoding and application of rateless codes AbdulHussein, Ali 2008
pdf
Page Metadata
Item Metadata
Title | Efficient decoding and application of rateless codes |
Creator |
AbdulHussein, Ali |
Publisher | University of British Columbia |
Date Issued | 2008 |
Description | Fountain codes have recently gained wide attention in the communications research community due to their capacity-approaching performance and rateless properties that allow them to seamlessly adapt to unknown channel statistics. This thesis of fers two key contributions. For the first, we consider the problem of low complexity decoding of Luby Transform (LT) and Raptor codes, which are classes of Fountain codes. We introduce a decoding method which has a significantly reduced compu tational load compared to the commonly used alternative of message-reset decoding with a flooding schedule. This method combines the recently proposed technique of informed dynamic scheduling combined with incremental decoding. Simulation re sults for the example of the binary symmetric channel show complexity reductions (in terms of the total required number of decoding iterations) by 87% compared to conventional message-passing decoding and 54% compared to a recently proposed incremental decoding scheme for Raptor codes. Having proposed our novel decoding method, we then focus on applying rateless codes to free-space optical (FSO) transmission systems. FSO systems enable high speed communication with relatively small deployment costs. However, FSO systems suffer a critical disadvantage, namely susceptibility to fog, smoke, and similar con ditions. A possible solution to this dilemma is the use of hybrid systems employing FSO and radio frequency (RF) transmission. As for the second contribution of this thesis, we propose the application of rateless coding for such hybrid FSO/RF sys tems. The advantages of our approach are (i) the full utilization of available FSO and RF channel resources at any time and (ii) very little feedback from the receiver. In order to substantiate these claims, we establish the pertinent capacity limits for hybrid FSO/RF transmission and present simulation results for transmission with off-the-shelf Raptor codes, which achieve realized rates close to these limits under a wide range of channel conditions. |
Extent | 1418117 bytes |
Subject |
Rateless codes LT codes Decoding |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-02-02 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0070788 |
URI | http://hdl.handle.net/2429/4064 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2008-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2008_fall_abdulhussein_ali.pdf [ 1.35MB ]
- Metadata
- JSON: 24-1.0070788.json
- JSON-LD: 24-1.0070788-ld.json
- RDF/XML (Pretty): 24-1.0070788-rdf.xml
- RDF/JSON: 24-1.0070788-rdf.json
- Turtle: 24-1.0070788-turtle.txt
- N-Triples: 24-1.0070788-rdf-ntriples.txt
- Original Record: 24-1.0070788-source.json
- Full Text
- 24-1.0070788-fulltext.txt
- Citation
- 24-1.0070788.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0070788/manifest