Binary-Coded Modulation and Applications in Free-Space Optics by Trung Thanh Nguyen M.A.Sc., The University of British Columbia, 2006 B.Eng., The University of Sydney, Australia, 2004 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) March 2011 c© Trung Thanh Nguyen 2011 Abstract Binary-coded modulation techniques such as bit-interleaved coded modu- lation (BICM) and multilevel coding (MLC) are pragmatic methods to achieve both high power and bandwidth efficiencies in digital communi- cations. These techniques enable the combination of powerful and popular off-the-shelf binary codes with bandwidth-efficient multilevel signaling with- out considerable performance loss compared to joint coding and modulation designs. Today, binary-coded modulation has become almost universal in digital communication systems. This thesis concerns several aspects of binary-coded modulation and its applications. For BICM, we study the use of approximate decoding metrics to reduce detection complexity. Specifically, we propose metric correction functions which can improve achievable rates. We further propose a metric scaling which can improve throughput performance of symbol-by-symbol (SBS) decoding, which is the basis of state-of-the-art error-control coding systems. To this end, we also discover an intriguing relationship between the generalized Gallager function and the performance of sum-product SBS decoding. For MLC, we develop the concept of reduced-layer coding that facilitates a trade-off between performance and structural complexity. We then propose a novel rateless MLC scheme which can seamlessly adapt to ii Abstract the instantaneous channel quality and achieve throughput gains compared to BICM in a number of transmission scenarios. Finally, we apply binary-coded modulation techniques to free-space optics (FSO). FSO is an interesting transmission technology which has recently emerged as a low-cost solution to a range of communication challenges. We consider advanced signaling schemes such as channel coding diversity with mismatched decoding metrics and multipulse pulse-position modulation (MPPM). Combined with binary codes, these schemes are practical means to improve rate and reliability in FSO systems. iii Preface This thesis is based on work conducted at UBC Department of Electrical and Computer Engineering under the guidance and supervision of Professor Lutz Lampe. Parts of this thesis have been published or submitted in the following articles and papers. Names of journals for articles under review are not shown. Journal articles 1. (Part of Chapter 4) T. T. Nguyen and L. Lampe, “Channel coding diversity with mismatched decoding metrics,” under review, submitted Jan. 2011. 2. (Part of Chapter 3) T. T. Nguyen and L. Lampe, “Multilevel cod- ing with general decoding metrics and rateless transmission,” under review, submitted Nov. 2010, revised Feb. 2011. 3. (Part of Chapter 2) T. T. Nguyen and L. Lampe, “Mismatched bit- interleaved coded noncoherent orthogonal modulation,” IEEE Com- munications Letters, accepted Mar. 2011. 4. (Part of Chapter 4) T. T. Nguyen and L. Lampe, “MPPM constel- iv Preface lation selection for free-space optical communications,” under review, submitted Aug. 2010. 5. (Part of Chapter 2) T. T. Nguyen and L. Lampe, “Bit-interleaved coded modulation with mismatched decoding metrics,” IEEE Trans- actions on Communications, vol. 59, no. 2, pp. 437-447, Feb. 2011. 6. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, “Coded mul- tipulse pulse-position modulation for free-space optical communica- tions,” IEEE Transactions on Communications, vol. 58, no. 4, pp. 1036-1041, Apr. 2010. 7. (Part of Chapter 4) A. AbdulHussein, A. Oka, T. T. Nguyen, and L. Lampe, “Rateless coding for hybrid free-space optical and radio- frequency communication,” IEEE Transactions on Wireless Commu- nications, vol. 9, no. 3, pp. 1615-1619, Mar. 2010. Conference papers 1. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, “Rateless mul- tilevel coding and applications,” in Proc. IEEE GLOBECOM, Hon- olulu, Hawaii, USA, Nov.-Dec. 2009. 2. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, “Coded pulse- position modulation for free-space optical communications,” in Proc. IEEE ICC, Dresden, Germany, Jun. 2009. 3. (Part of Chapter 4) T. T. Nguyen and L. Lampe, “Capacity-maximized MPPM constellations for free-space optical communications,” in Proc. CSNDSP, Graz, Austria, Jul. 2008. v Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . xiii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xv 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 BICM with Mismatched Decoding Metrics . . . . . . . . . 6 2.1 Random Coding with A Given Decoding Rule . . . . . . . . 8 2.2 BICM and Mismatched Decoding . . . . . . . . . . . . . . . 11 2.2.1 Log-Likelihood Ratio . . . . . . . . . . . . . . . . . . 14 2.2.2 Independent Binary Channel Model . . . . . . . . . . 14 2.2.3 BICM and Binary I-curves . . . . . . . . . . . . . . . 15 vi Table of Contents 2.3 Metric Manipulation . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.1 Metric Scaling and GMI . . . . . . . . . . . . . . . . 16 2.3.2 Metric Scaling and Symbol-By-Symbol Decoding . . . 19 2.3.3 Cascaded Channel Model and Metric-Mismatch Cor- rection . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4.1 Discrete Metrics and Metric Correction . . . . . . . . 32 2.4.2 Noncoherent Carrier-Modulated Orthogonal Signaling 36 2.4.3 Pulse-Position Modulation with Direct Detection . . 44 2.4.4 MIMO-QAM with Clipped Max-Log Metric . . . . . 47 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3 Multilevel Coding: Reduced-Layer, General Decoding Met- rics, and Rateless Transmission . . . . . . . . . . . . . . . . . 54 3.1 Reduced-Layer MLC . . . . . . . . . . . . . . . . . . . . . . 57 3.2 Multilevel Coding with General Decoding Metrics . . . . . . 59 3.2.1 Achievable Rates . . . . . . . . . . . . . . . . . . . . 59 3.2.2 Per-Layer Transmission and GMI . . . . . . . . . . . 61 3.2.3 Metric-Mismatch Correction . . . . . . . . . . . . . . 67 3.3 Rateless Multilevel Coding . . . . . . . . . . . . . . . . . . . 67 3.3.1 Encoding and Decoding . . . . . . . . . . . . . . . . . 68 3.3.2 Operation Analysis and Control . . . . . . . . . . . . 72 3.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.4.1 MIMO-QAM . . . . . . . . . . . . . . . . . . . . . . . 81 3.4.2 Noncoherent Carrier-Modulated Orthogonal Signaling 83 vii Table of Contents 3.4.3 Pulse-Position Modulation with Direct Detection . . 87 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4 Applications in Free-Space Optics . . . . . . . . . . . . . . . 91 4.1 Rateless Hybrid FSO-RF for Last-Mile Access . . . . . . . . 91 4.1.1 Channel Coding Diversity Model and Rate Analysis . 92 4.1.2 Numerical Examples . . . . . . . . . . . . . . . . . . 96 4.2 Multipulse Pulse-Position Modulation . . . . . . . . . . . . . 99 4.2.1 Constellation Selection . . . . . . . . . . . . . . . . . 103 4.2.2 Subset Selection . . . . . . . . . . . . . . . . . . . . . 105 4.2.3 Labeling and Binary-Coded Modulation . . . . . . . . 109 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . 115 5.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . 115 5.2 Suggested Future Work . . . . . . . . . . . . . . . . . . . . . 117 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 viii List of Tables 2.1 BICM metric manipulation methods and their effects. . . . . 31 ix List of Figures 2.1 Elements of a digital communication system. . . . . . . . . . 8 2.2 Example of the generalized Gallager function E0qX,Y (ρ, s). . . 11 2.3 BICM transmitter and receiver. . . . . . . . . . . . . . . . . . 12 2.4 Shift the critical point of the I-curve by metric scaling. . . . . 17 2.5 Throughput achieved with a Raptor code over a BAC and SBS decoding with mismatched metrics versus the metric- scaling parameter c. . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 BICM demodulator as part of a cascaded channel. . . . . . . 27 2.7 8-ASK constellation and labeling. . . . . . . . . . . . . . . . . 33 2.8 I-curves for 8-ASK transmission over the AWGN channel with matched detection, hard detection, and different metric mis- match correction functions. . . . . . . . . . . . . . . . . . . . 34 2.9 Approximation to the function ln(I0(·)). . . . . . . . . . . . . 39 2.10 BICM GMI of noncoherent orthogonal modulation. . . . . . . 41 2.11 BICM I-curve and coded throughput of 16-ary noncoherent orthogonal modulation over AWGN channel at SNR of 6.35 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 x List of Figures 2.12 BICM I-curve and coded throughput of 16-ary noncoherent orthogonal modulation over Rayleigh fading channel at SNR of 8.5 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13 BICM GMI for decoding with matched metric and max-log metric, and IqX,Y (1) for max-log metric. 64-PPM transmis- sion over Poisson channel. . . . . . . . . . . . . . . . . . . . . 46 2.14 BICM I-curve and simulated rates for 64-PPM. . . . . . . . . 48 2.15 I-curves for a 2× 2 MIMO transmission. . . . . . . . . . . . . 50 2.16 Metric manipulation functions for a MIMO transmission. . . 51 3.1 Example of conventional MLC. . . . . . . . . . . . . . . . . . 57 3.2 Two examples of reduced-layer MLC. . . . . . . . . . . . . . . 58 3.3 MLC transmitter and receiver. . . . . . . . . . . . . . . . . . 61 3.4 GMI of conventional MLC, BICM, and 2-layer MLC for 128- PPM over Poisson channel with λb = 0.2. . . . . . . . . . . . 66 3.5 Rotation rateless MLC transmitter and receiver. Stream redi- rection occurs at switching to a new interval. . . . . . . . . . 69 3.6 Information segments at the receiver. . . . . . . . . . . . . . . 70 3.7 Interval length `[t] of an unstable system. . . . . . . . . . . . 76 3.8 Model predictive control technique. . . . . . . . . . . . . . . . 79 3.9 Controlling structural loss in an unstable system. . . . . . . . 80 3.10 GMI and throughput of rateless MLC for 4-QAM MIMO transmission with 4 transmit and 2 and 4 receive antennas over an i.i.d. Rayleigh fading channel. . . . . . . . . . . . . . 83 xi List of Figures 3.11 GMI and throughput of rateless MLC for M = 128 nonco- herent orthogonal modulation. . . . . . . . . . . . . . . . . . 84 3.12 Example of 2-layer rateless MLC over slow fading channel. The value R[t] approximates the average throughput during time interval t. . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.13 Layer I-curves of an 128-PPM MLC scheme. . . . . . . . . . . 88 4.1 Channel coding diversity scheme. . . . . . . . . . . . . . . . . 92 4.2 Rateless BICM hybrid FSO-RF communication system. . . . 95 4.3 Scatter plot of throughput vs. GMI for 1000 codewords over the hybrid (diversity) FSO-RF scheme. . . . . . . . . . . . . . 96 4.4 Throughput and GMI during the transmission of 200 consec- utive codewords over the hybrid FSO-RF scheme. . . . . . . . 97 4.5 BICM I-curve of individual FSO and RF channels. . . . . . . 100 4.6 BICM I-curve and coded throughput of hybrid (diversity) channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.7 Power-bandwidth efficiency chart of MPPM. Parameter sets are triplets (n,w,M). . . . . . . . . . . . . . . . . . . . . . . 105 4.8 Pseudo-code for random search. . . . . . . . . . . . . . . . . . 106 4.9 Pseudo-code for greedy ascent. . . . . . . . . . . . . . . . . . 107 4.10 Pseudo-code for simulated annealing. . . . . . . . . . . . . . . 108 4.11 Constrained channel capacity of MPPM constellations. . . . . 110 4.12 Pseudo-code for Gray labeling search. . . . . . . . . . . . . . 112 4.13 Constrained capacities or GMIs of an MPPM transmission. . 113 xii List of Abbreviations ASK Amplitude-Shift Keying AWGN Additive White Gaussian Noise BER Bit-Error Rate BICM Bit-Interleaved Coded Modulation bpcu Bits Per Channel Use CWC Constant-Weight Code ECC Error-Control Coding FSK Frequency-Shift Keying FSO Free-Space Optics or Free-Space Optical communications GMI Generalized Mutual Information IM-DD Intensity Modulation with Direct Detection LDPC Low-Density Parity Check LLR Log-Likelihood Ratio MIMO Multiple-Input Multiple-Output ML Maximum Likelihood MLC MultiLevel Coding MPC Model Predictive Control MPPM Multipulse Pulse-Position Modulation MSD MultiStage Decoding xiii List of Abbreviations MSL Minimum Segment Length OOK On-Off Keying pdf Probability Density Function PPM Pulse-Position Modulation QAM Quadrature Amplitude Modulation RF Radio Frequency RL-MLC Reduced-Layer MLC SBS Symbol-By-Symbol SNR Signal-to-Noise Ratio TCM Trellis-Coded Modulation xiv Acknowledgements I wish to give my foremost gratitude to my supervisor, Prof. Lutz Lampe, for his support throughout my years at UBC, for his guidance, and for believing in me and giving me the freedom to pursue different research directions. He has always expected the highest dedication and integrity from his students; and living up to his expectation has made me a better researcher. I wish to thank Profs. Robert Schober, Vincent Wong, Jane Wang, Vic- tor Leung, Cyril Leung, Vijay Bhargava, Nando de Freitas, Ozgur Yilmaz, and Ian Blake for being in my supervisory and examining committees. I would like to thank my external examiner, Prof. Lars Rasmussen, for his enthusiasm and encouraging evaluation of my work. My special thanks to my colleagues for a warm and intellectually stimu- lating working environment. I would like to thank fellow scholars at Green College for a special place I call home. I want to thank all friends for sharing the ups and downs during all these years. As always, my deepest thanks to my family for their love and support. Vancouver, Canada March 2011 xv Chapter 1 Introduction Digital communication has become an essential part of our daily lives. The last decade has seen an explosive growth in the number of communication devices and the volume of data traffic. This growth is likely to continue over the coming years. Today, cheaper, faster, and more environmentally friendly communication systems are in ever greater demand. The two primary resources of a communication system are channel band- width and transmit power [1]. Channel bandwidth utilization can often be increased by using larger multilevel constellations. Transmit power require- ment can be minimized by error-control coding (ECC). However, non-binary codes for multilevel constellations are usually harder to design and imple- ment, and thus binary codes are much more popular in practice. A prag- matic approach to achieve both high power and bandwidth efficiencies is to combine binary ECC with multilevel constellation signaling. Bit-interleaved coded modulation (BICM) [2,3] and multilevel coding (MLC) [4,5] are two popular techniques that offer such a combination. In Chapter 2 and 3, we make a number of contributions to the development of these techniques. Our contributions focus on the use of suboptimal designs and decoding met- rics which, with a small trade-off in the achievable rate, greatly reduce the 1 Chapter 1. Introduction detection and decoding complexity. This complexity reduction can in turn be exploited in several ways. For example, it can be translated into lower hardware cost and consumption power, or into higher throughput for a given computational complexity constraint. Recently, free-space optics (FSO) has regained attention as a secure, low cost, rapidly deployable, and license-free wireless connectivity, e.g. [6,7]. We investigate this interesting communication technology in Chapter 4. Due to the high frequency of optical waveform signal, practical FSO transmission often uses intensity modulation with direct detection (IM-DD) like fiber optics. However, unlike in the fiber medium, FSO signal suffers from fading similar to radio-frequency (RF) signal in wireless communications. These combined characteristics pose a unique technical challenge to achieve both high rate and reliability with FSO. To address this challenge, we consider the use of advanced signaling schemes and apply coding techniques developed in earlier chapters to FSO systems. Our contributions are organized as follows: • Chapter 2 – BICM with Mismatched Decoding Metrics: BICM is cur- rently the de facto coding standard for digital communication. Re- cently, BICM has been cast as a mismatched decoding scheme due to the assumption of independent bit metrics [8, 9]. In addition to this inherent mismatch, practical demodulators may produce mismatched decoding metrics to reduce computational complexity. In this chapter, we investigate BICM with such metrics. In line with recent works on this topic, we adopt the generalized mutual information (GMI) [10,11] 2 Chapter 1. Introduction as the pertinent performance measure. First, we show that level- dependent scaling of logarithmic bit metrics can improve the BICM GMI. Second, we consider the effect of metric scaling on symbol-by- symbol (SBS) decoding, which is used in a number of modern capacity- approaching ECC systems. We propose a uniform metric scaling which can lead to an improved performance of mismatched sum-product SBS decoding, even if the GMI is not changed. Third, we investigate gen- eral metric-mismatch correction functions and analyze their effects in terms of the GMI. We then provide extensive numerical evidence to demonstrate that our proposed metric manipulation methods can sig- nificantly increase the performance of mismatched BICM. • Chapter 3 – Multilevel Coding: Reduced-Layer, General Decoding Met- rics, and Rateless Transmission: MLC is the main contender to the celebrated BICM technique for combining binary ECC with multilevel constellations. Although MLC has a more complex encoding-decoding structure, it can achieve a larger rate in a number of important sce- narios such as multiple-input multiple-output (MIMO) and orthogo- nal modulation transmission. In this chapter, we make three distinct contributions to MLC. First, based on a previous work [12], we de- velop the concept of reduced-layer MLC (RL-MLC), which includes both conventional MLC and BICM as special cases. This new concept facilitates a trade-off between achievable rates and MLC structural complexity, which is measured by the number of decoding layers. Sec- ond, we present rate analysis and metric-mismatched correction for 3 Chapter 1. Introduction MLC with general decoding metrics. This contribution is an exten- sion of the results for BICM from Chapter 2. Third, we consider the combination of MLC with rateless codes, e.g. [13]. Such a com- bination eliminates the need to carefully design code rate for each layer. Furthermore, in slow fading environments, rateless coding can seamlessly adapt to the instantaneous channel quality and achieve an increased average throughput compared to fixed-rate MLC transmis- sion. However, despite these great potential benefits, we show that a careless combination of MLC and rateless coding would lead to sig- nificant rate loss. Thus, we propose a novel rateless scheme which preserves the rate advantage of MLC over BICM. We provide relevant examples with MIMO, noncoherent carrier-modulated orthogonal sig- naling, and IM-DD pulse-position modulation (PPM) to demonstrate that our scheme can achieve throughput gains compared to BICM in a variety of transmission scenarios. • Chapter 4 – Applications in Free-Space Optics: In the first half of this chapter, in light of results from Chapter 2, we revisit the rateless BICM scheme with hybrid FSO-RF transmission [14]. Hybrid FSO-RF is an example of channel coding diversity [15]. The use of an RF link in conjunction with the FSO link is promising to improve communica- tion reliability because these links are complementary in a wide variety of weather-induced fading conditions. We show a new achievable rate analysis for channel coding diversity with general decoding metrics. We then demonstrate the applicability of our analytical result in rele- 4 Chapter 1. Introduction vant examples. In the second half of this chapter, we design a balanced power-bandwidth efficient modulation format for FSO. Currently, the two most popular FSO signaling formats are on-off keying (OOK) and pulse-position modulation (PPM). OOK is more bandwidth-efficient, but it has several drawbacks such as the need to select an appropriate decision threshold at the receiver and more complex synchronization. PPM, on the other hand, is more power-efficient, but its bandwidth ef- ficiency rapidly declines with increasing constellation size. We consider multipulse pulse-position modulation (MPPM) [16] as an alternative modulation for FSO. It is a generalization of PPM with more than one pulse per symbol. We design decimated MPPM constellations that are suitable for combining with binary codes and have both high power and bandwidth efficiencies. Concluding remarks are given in Chapter 5. Chapter 2 is self-contained and can be read independently of the other chapters. 5 Chapter 2 BICM with Mismatched Decoding Metrics BICM is a technique to combine binary ECC with multilevel constellations. Invented in 1992 by Zehavi [2], it has become the de facto coding standard for modern digital communication systems. The key advantages of BICM are its excellent performance and its flexibility in allowing separate code and modulation design. An up-to-date overview of BICM can be found in [8]. In a recent work by Martinez et al. [9], the BICM decoder has been cast as a mismatched decoder [10, 11] and the GMI [10] has been used as a performance measure. This new perspective readily enables the study of BICM with mismatched demodulators, that is, when a twofold mismatch occurs. The first mismatch is due to the assumption of independent bit met- rics and is inherent to BICM. The second mismatch occurs because of some approximation in the computation of bit metrics. The use of approximate metrics is common in practice to reduce detection and decoding complexity, e.g. [17–23]. Following this direction, Jaldén et al. [24] have recently de- vised and analyzed a metric correction method for BICM with mismatched demodulation. 6 Chapter 2. BICM with Mismatched Decoding Metrics In this chapter, we extend this new line of work. In particular, we study the manipulation of mismatched bit metrics to improve the performance of BICM. We start in Section 2.1 by first revisiting the concept of random coding and introducing the “I-curve,” whose maximum is the GMI. In Sec- tion 2.2, we establish that the BICM I-curve is equal to the sum of the binary I-curves of the levels. This relation suggests that the GMI of BICM can be increased by aligning the binary I-curves so that their peaks are added in a totally constructive manner. In Section 2.3.1, we show that this alignment can be achieved by scaling the log-likelihood ratio (LLR) metrics with suitable constant factors. In Section 2.3.2, we investigate the effect of metric scaling on SBS decoding where the concept of GMI does not apply. SBS decoding is used in a number of state-of-the-art ECC systems such as repeat-accumulate [25], low-density parity check (LDPC) [26–31], and Rap- tor codes [13, 32, 33]. Based on the properties of the I-curve, we propose a scaling rule which can lead to rate improvements in sum-product SBS decoding, even if the GMI remains unchanged. Finally, in Section 2.3.3, we consider the BICM demodulator as part of a cascaded channel. This point of view naturally leads to metric correction methods that increase the BICM GMI, including the scalar function used in [24], and new vector functions which provide different performance-complexity trade-offs. Using four specific application examples in Section 2.4, we provide extensive nu- merical evidence that the proposed metric manipulations can improve the performance of mismatched BICM. 7 2.1. Random Coding with A Given Decoding Rule 2.1 Random Coding with A Given Decoding Rule A digital communication system can be divided into the transmitter, the channel, and the receiver as illustrated in Figure 2.1. x channel pY |X(y|x) y receivertransmitter decoded bits message bits Figure 2.1: Elements of a digital communication system. We consider a discrete-time memoryless channel whose random input and output variables are denoted X and Y , respectively. Input symbols are drawn from the discrete alphabet X with the probability mass function pX(x). The discrete or continuous output alphabet is denoted Y. The chan- nel can be fully described by the transition probability function pY |X(y|x). At the receiver, given the received symbol y ∈ Y, a symbol metric of the general form qX,Y (x, y) can be calculated for each x ∈ X . We assume that qX,Y (x, y) > 0, ∀x ∈ X , y ∈ Y. Consider a code with the codebook C that consists of M length-N codewords x = [x0 . . . xN−1]. Each codeword in C is equally likely chosen for transmission. Given the received sequence y = [y0 . . . yN−1], for each codeword x ∈ C, the word metric is calculated as qX,Y (x,y) = N−1∏ k=0 qX,Y (xk, yk) . (2.1) 8 2.1. Random Coding with A Given Decoding Rule The decoder output is determined by x̂ = argmax x∈C qX,Y (x,y) . (2.2) The symbol metric qX,Y (x, y) is called a matched metric if it is propor- tional to the channel transition probability pY |X(y|x). It is called a mis- matched metric otherwise [10, 11]. With matched metrics, (2.2) coincides with the maximum-likelihood (ML) decoding rule and, since all codewords are equally likely, becomes x̂ = argmin x∈C ( 1− pX|Y (x|y) ) . That is, it minimizes the word error probability [34, p. 120]. The word error probability, averaged over all codewords and random codebook realizations, can be upper-bounded by [34, Ch. 5], [10, Sec. 2], [8, Sec. 3.1.2], cf. [35] P ≤MρEX,Y {(∑ x∈X pX(x) [ qX,Y (x, Y ) qX,Y (X,Y ) ]s)ρ}N (2.3) for all 0 ≤ ρ ≤ 1 and s > 0. Alternatively, P ≤ 2−NErqX,Y (R), (2.4) where R , logMN (notation log(·) denotes logarithm with base 2) is the code rate, ErqX,Y (R) , max0≤ρ≤1 maxs>0 ( E0qX,Y (ρ, s)− ρR ) (2.5) 9 2.1. Random Coding with A Given Decoding Rule is the random coding exponent, and E0qX,Y (ρ, s) , − log EX,Y {(∑ x∈X pX(x) [ qX,Y (x, Y ) qX,Y (X,Y ) ]s)ρ} (2.6) is the generalized Gallager function. If ErqX,Y (R) > 0, the error probability vanishes with increasing N and the rate R is said to be achievable. The maximum achievable rate that can be inferred from (2.5) and the properties of the generalized Gallager function E0qX,Y (ρ, s), cf. [34, Theorem 5.6.3], is the GMI, which is defined as [10] IgmiqX,Y , maxs>0 IqX,Y (s) , (2.7) with IqX,Y (s) , ∂E0qX,Y (ρ, s) ∂ρ ∣∣∣∣∣ ρ=0 = lim ρ→0 E0qX,Y (ρ, s) ρ = −EX,Y { log ∑ x∈X pX(x) [ qX,Y (x, Y ) qX,Y (X,Y ) ]s} . (2.8) We call the plot of IqX,Y (s) vs. s the I-curve of the symbol metric qX,Y (x, y). The peak value of the I-curve is the GMI. Figure 2.2 illustrates a typical picture of the generalized Gallager function E0qX,Y (ρ, s). The I- curve is the intersection of the plane ρ = 1 and the surface which is tangent to the generalized Gallager function at ρ = 0. With matched metrics, the line E0qX,Y (ρ, 1 1+ρ) is the conventional one-dimensional Gallager function, 10 2.2. BICM and Mismatched Decoding tangent surface GMI I−curve generalized Gallager function s ρ Figure 2.2: Example of the generalized Gallager function E0qX,Y (ρ, s). the I-curve peaks at s = 1, and the GMI is the average mutual information I(X;Y ) [34, Ch. 5], which is I(X;Y ) = −EX,Y { log ∑ x∈X pX(x) pY |X(Y |x) pY |X(Y |X) } . (2.9) 2.2 BICM and Mismatched Decoding We now focus on the BICM scheme [3, 8], whose transmitter and receiver are presented in Figure 2.3. The BICM transmitter consists of a binary encoder and a mapper (or modulator) which maps coded bits into transmit symbols. The BICM receiver consists of a detector (or demodulator) and a binary decoder. The detector produces bit metrics for the binary decoder. 11 2.2. BICM and Mismatched Decoding decoded bits y binary decoderdetector bit metrics binary encoder coded bits mapper message bits x BICM transmitter BICM receiver Figure 2.3: BICM transmitter and receiver. We note that, despite the “bit-interleaved” part in the name of BICM, bit interleaving is immaterial for the random coding argument [9] and also not needed in many practical situations1. Therefore, we do not include such bit (de)interleavers in our discussion. Let 2m be the size of the constellation X and B0, . . . , Bm−1 be the m binary random variables for the labeling bits of the transmit symbol. Fur- thermore, let bi(x) be the i-th bit in the label of symbol x. The probability mass functions pBi(b), b ∈ B , {0, 1}, and pX(x), x ∈ X , are related by pBi(b) = ∑ x∈X bi pX(x) , (2.10) 1When using LDPC codes, for example, bit interleaving is equivalent to re-ordering the columns of the parity-check matrix, which does not affect the decoding outcome. 12 2.2. BICM and Mismatched Decoding where X bi , {x ∈ X : bi(x) = b}, and pX(x) = m−1∏ i=0 pBi(bi(x)) . (2.11) Instead of directly producing 2m symbol-metric values for each possible transmit symbol x given the received symbol y, the BICM detector produces 2m bit-metric values corresponding to the m levels. Bit metrics for the i-th level have the general form qBi,Y (b, y). We assume qBi,Y (b, y) > 0, ∀b ∈ B, ∀y ∈ Y. The BICM symbol metric is then calculated as qX,Y (x, y) = m−1∏ i=0 qBi,Y (bi(x), y) . (2.12) Even if qBi,Y (b, y) matches to the binary-input channel with input Bi and output Y , i.e., it is proportional to the transition probability pY |Bi(y|b) = ∑ x∈X bi pY |X(y|x)pX(x) , (2.13) the BICM symbol metric (2.12) still does not match to the channel with in- put X and output Y . Therefore, BICM is inherently a mismatched decoding scheme [8,9]. 13 2.2. BICM and Mismatched Decoding 2.2.1 Log-Likelihood Ratio The binary decoder is fed with the 2m bit-metric values per received symbol, or alternatively, with m log-metric ratios ΛqBi,Y (y) , ln qBi,Y (0, y) qBi,Y (1, y) , (2.14) since they are sufficient statistics for Bi given qBi,Y (b, y) (notation ln(·) de- notes the natural logarithm). Conventionally, ΛqBi,Y (y) is the log-likelihood ratio (LLR) only when qBi,Y (b, y) is proportional to the likelihood pY |Bi(y|b). However, for convenience and brevity, we will refer to ΛqBi,Y (y) as an LLR even when qBi,Y (b, y) is not proportional to pY |Bi(y|b). 2.2.2 Independent Binary Channel Model The classical approach to analyze BICM is to use the independent binary channel model [3], in which transmission is performed in m parallel channels with inputs Bi, i = 0, . . . ,m− 1, and output Y . This model is equivalent to multilevel coding (MLC) with parallel decoding of levels [5]. For level i and its bit metric, the binary generalized Gallager function is defined as E0qBi,Y (ρ, s) , − log EBi,Y {(∑ b∈B pBi(b) [ qBi,Y (b, Y ) qBi,Y (Bi, Y ) ]s)ρ} (2.15) = − log EX,Y {(∑ b∈B pBi(b) [ qBi,Y (b, Y ) qBi,Y (bi(X), Y ) ]s)ρ} , (2.16) where the transition from EBi,Y {·} to EX,Y {·} is possible because the term inside the expectation in (2.16) is the same for all transmit symbols x that 14 2.2. BICM and Mismatched Decoding have the same i-th labeling bit, and ∑ x∈X bi pX,Y (x, y) = pBi,Y (b, y) . (2.17) The function E0qBi,Y (ρ, s) gives rise to the binary random coding exponent ErqBi,Y (R), the I-curve function IqBi,Y (s), and the GMI I gmi qBi,Y for the i-th level, applying (2.5), (2.8), and (2.7), respectively. In particular, IqBi,Y (s) = −EBi,Y { log ∑ b∈B pBi(b) [ qBi,Y (b, Y ) qBi,Y (Bi, Y ) ]s} = −EX,Y { log ∑ b∈B pBi(b) [ qBi,Y (b, Y ) qBi,Y (bi(X), Y ) ]s} , (2.18) and IgmiqBi,Y = max s>0 IqBi,Y (s) . (2.19) For the special case of uniform input, from (2.14) and (2.18), the binary I-curve function IqBi,Y (s) can be expressed in terms of the LLR as IqBi,Y (s) = 1− EX,Y { log(1 + exp(− sgn(bi(X))ΛqBi,Y (Y )s)) } , (2.20) where the function sgn(·) is defined for the labeling bits as sgn(0) = 1 and sgn(1) = −1. 2.2.3 BICM and Binary I-curves Substituting (2.11) and (2.12) into (2.8) and considering (2.18), we obtain (cf. [9, proof of Theorem 2]) 15 2.3. Metric Manipulation IqX,Y (s) = −EX,Y { log ∑ x∈X m−1∏ i=0 pBi(bi(x)) [ qBi,Y (bi(x), Y ) qBi,Y (bi(X), Y ) ]s} = −EX,Y { log m−1∏ i=0 ∑ b∈B pBi(b) [ qBi,Y (b, Y ) qBi,Y (bi(X), Y ) ]s} = − m−1∑ i=0 EX,Y { log ∑ b∈B pBi(b) [ qBi,Y (b, Y ) qBi,Y (bi(X), Y ) ]s} = m−1∑ i=0 IqBi,Y (s) . (2.21) That is, the BICM I-curve equals the sum of the binary I-curves IqBi,Y (s). This relation will be important for our subsequent discussion. 2.3 Metric Manipulation We now present and discuss different metric manipulations that can improve the performance of BICM with a mismatched demodulator. 2.3.1 Metric Scaling and GMI For the general mismatched decoding scheme from Section 2.1, let sqX,Y be the critical point of the I-curve IqX,Y (s), i.e. the value of s at which IqX,Y (s) attains its maximum. Let us consider a new metric q′X,Y (x, y) = [qX,Y (x, y)] c with some constant c > 0. It follows from (2.6) that the new generalized Gal- lager function is E0q′X,Y (ρ, s) = E0qX,Y (ρ, cs) and hence Iq′X,Y (s) = IqX,Y (cs). That is, the I-curve of the metric q′X,Y (x, y) is simply a compressed (for c > 1) or expanded (for c < 1) version of the I-curve of the metric qX,Y (x, y) 16 2.3. Metric Manipulation shift IqX,Y (s) Iq′ X,Y (s) s sqX,Ysq′X,Y = sqX,Y /c IgmiqX,Y Figure 2.4: Shift the critical point of the I-curve by metric scaling. along the s-axis. In particular, the GMI remains unchanged, while the crit- ical point changes to sq′X,Y = sqX,Y /c. This coordinate shift is illustrated in Figure 2.4 for an example with c > 1. Since raising symbol metric qX,Y (x, y) to a power corresponds to scaling with the same factor in the logarithmic domain, in LLR-based decoding we refer to this operation as “metric scal- ing.” Metric scaling allows us to control the critical point of the I-curve. The fact that it does not affect the GMI should not come as a surprise. Using q′X,Y (x, y), the decoding rule (2.2) becomes x̂ = argmax x∈C [qX,Y (x,y)] c , which returns exactly the same codeword as using qX,Y (x, y). 17 2.3. Metric Manipulation We now apply metric scaling to BICM. Theorem 2.1. Two I-curves are called harmonic if they have the same critical point. The BICM GMI equals the sum of the binary GMIs if the binary I-curves are harmonic, and is less than that otherwise. Let sqBi,Y be the critical point of the binary I-curve of the i-th level. The binary I- curves can be made harmonic at s∗ > 0 by metric scaling with the factor ci = sqBi,Y /s ∗ at level i, i = 0, . . . ,m− 1. Proof. Let q′Bi,Y (b, y) = [qBi,Y (b, y)] ci with some ci > 0. Then, Iq′Bi,Y (s) = IqBi,Y (cis), which peaks at (sqBi,Y /ci, I gmi qBi,Y ). According to Section 2.2 and in particular (2.12) and (2.21), BICM with these bit metrics has the symbol metric q′X,Y (x, y) = m−1∏ i=0 q′Bi,Y (bi(x), y) and the I-curve function Iq′X,Y (s) = m−1∑ i=0 Iq′Bi,Y (s) . The BICM GMI is upper-bounded as Igmi q′X,Y = max s>0 m−1∑ i=0 Iq′Bi,Y (s) ≤ m−1∑ i=0 max s>0 Iq′Bi,Y (s) (2.22) = m−1∑ i=0 IgmiqBi,Y . (2.23) Equality in (2.22) is achieved if and only if all binary I-curves {Iq′Bi,Y (s), 18 2.3. Metric Manipulation i = 0, . . . ,m − 1}, attain their maximum at the same value of s, i.e. if they are harmonic. By metric scaling in the logarithmic domain with the constant factor ci = sqBi,Y /s ∗, all binary I-curves will be harmonic at s∗ for arbitrary s∗ > 0. Remark 1: If the original binary I-curves are already harmonic, no align- ment is needed and IgmiqX,Y = ∑m−1 i=0 I gmi qBi,Y . This is the case if, for example, qBi,Y (b, y) ∝ pY |Bi(y|b), for which sqBi,Y = 1 ∀i [9, Corollary 1]. When the binary I-curves are not harmonic, the above proof provides a constructive procedure for choosing the scaling factors to increase the BICM GMI. This requires the computation of sqBi,Y , i = 0, . . . ,m − 1, which can be done offline, either through analysis or through simulation when closed-form ex- pressions cannot be obtained. Remark 2: According to the independent binary channel model, BICM always achieves a rate equal to the sum of the achievable rates of the levels. In the context of random coding and the GMI, Theorem 2.1 shows that this is only conditionally true. We recall that the independent binary channel model requires m binary encoder-decoder pairs instead of just one as BICM. 2.3.2 Metric Scaling and Symbol-By-Symbol Decoding We again consider the general mismatched decoding scheme in Section 2.1. The derivation of the random coding exponent and the GMI is based on the word decoding rule (2.2). However, some important modern error-correction schemes employ SBS decoding. That is, given the received sequence y, for 19 2.3. Metric Manipulation each position k = 0, . . . , N − 1, the SBS metric qXk,Y (x,y) , ∑ x∈Cxk qX,Y (x,y) = ∑ x∈Cxk ( N−1∏ k=0 qX,Y (xk, yk) ) (2.24) is computed, where Cxk denotes the set of codewords whose k-th symbol equals x, and the decoding rule x̂k = argmax x∈X qXk,Y (x,y) (2.25) is applied. For sparse-graph based codes, (2.25) with metric (2.24) can be ef- ficiently evaluated (or approximated) using the sum-product algorithm [36]. With matched metrics and equally likely chosen codewords, (2.25) becomes x̂k = argmax x∈X ∑ x∈Cxk pY |X(y|x) = argmax x∈X ∑ x∈Cxk pX|Y (x|y) = argmax x∈X pXk|Y (x|y) = argmin x∈X ( 1− pXk|Y (x|y) ) . Thus, sum-product SBS decoding with matched metrics minimizes the coded symbol error probability, cf. word decoding as in [34, p. 120]. This holds true regardless of the probability mass function pX(x). However, minimizing the coded symbol error probability may not be the same as minimizing the 20 2.3. Metric Manipulation message symbol (or bit) or the word error probability. In particular, the collection of decoded symbols [x̂0 . . . x̂N−1] is not necessarily a codeword in C. Therefore, achievable rates, in the sense that the word error probability can still be driven to zero with increasing code length, further depend on the translation of the decoded symbols into a valid codeword. Another popular SBS decoding metric is qXk,Y (x,y) =  max x∈Cxk qX,Y (x,y) , if Cxk 6= ∅ 0 , otherwise . =  max x∈Cxk ( N−1∏ k=0 qX,Y (xk, yk) ) , if Cxk 6= ∅ 0 , otherwise . (2.26) Metric (2.26) can be estimated by the max-product algorithm, which is also known as the min-sum algorithm from its form in the logarithmic do- main [36]. The metric (2.26) is derived from (2.24) by approximating a sum by its largest term. As in word decoding, metric scaling does not affect the decoding out- come in max-product SBS decoding. However, if we replace qX,Y (x, y) by [qX,Y (x, y)] c in sum-product decoding using (2.25), the decoding outcome might change. When c → 0, the decoding outcome generally becomes ran- dom, with exceptions, e.g., repetition codes where the sum (2.24) would consist of only a single term. On the other hand, when c→∞, sum-product decoding approaches max-product decoding. With matched metrics, c = 1 is the optimal scaling factor when the coded symbol error probability is the 21 2.3. Metric Manipulation performance measure. The I-curve peaks at s = 1 in this case. For mis- matched metrics, we propose that metric scaling with the factor c = sqX,Y is applied in sum-product decoding. This scaling shifts the critical point of the I-curve to 1. In the following, we provide a numerical example which shows that this scaling yields the largest throughput in a rateless transmis- sion. Further practical examples which illustrate the benefit of this scaling are presented in Section 2.4. Example 2.1. Consider a binary asymmetric channel (BAC) with crossover probabilities p0 and p1, 0 < p0, p1 < 1, for transmit symbol x = 0 and x = 1, respectively. A matched demodulator produces the LLR of ln((1 − p0)/p1) for received symbol y = 0 and of ln(p0/(1−p1)) for y = 1. Assuming uniform input, the matched I-curve follows from (2.8) or (2.20) as IpY |X (s) = 1− 1− p0 2 log ( 1 + ps1 (1− p0)s ) − p0 2 log ( 1 + (1− p1)s ps0 ) −p1 2 log ( 1 + (1− p0)s ps1 ) − 1− p1 2 log ( 1 + ps0 (1− p1)s ) , (2.27) which peaks at (1, I(X;Y )). Suppose that a mismatched demodulator produces LLR of +1 and −1 for received symbol y = 0 and y = 1, respectively. The corresponding mismatched I-curve is given by IqX,Y (s) = 1− p log(1 + es)− (1− p) log(1 + e−s) , (2.28) where p = (p0 + p1)/2. The GMI I gmi qX,Y = 1 + p log(p) + (1− p) log(1− p) = 22 2.3. Metric Manipulation 1 − Hb(p) is attained at sqX,Y = ln((1 − p)/p), where Hb is the binary entropy function. We have IgmiqX,Y ≤ I(X;Y ), and equality holds if and only if p0 = p1, i.e. when the channel is a binary symmetric channel (BSC). Applying scaling with factor c to this mismatched LLR, we obtain Iq′X,Y (s) = IqX,Y (cs). Consider Iq′X,Y (1) as a function of c. It attains its maximum with c = sqX,Y = ln((1− p)/p), for which Iq′X,Y (1) = I gmi q′X,Y = IgmiqX,Y . Our proposal states that scaling with this value of c should be applied in sum-product decoding. Let us consider a specific example with p0 = 0.03 and p1 = 0.07. This pair results in I(X;Y ) = 0.72 bit per channel use (bpcu), p = 0.05, IgmiqX,Y = 0.71 bpcu, and sqX,Y = 2.94. Figure 2.5 shows the plot of Iq′X,Y (1) vs. c. To demonstrate the effect of scaling, we measure the average throughput achieved by coded transmission using a Raptor code. The code consists of an outer LDPC code of length 10 000 and code rate 0.95 and an inner Luby transform (LT) code [37] with degree distribution [13, Table I, second column] Ω(x) = 0.007969x+ 0.493570x2 + 0.166220x3 +0.072646x4 + 0.082558x5 + 0.056058x8 +0.037229x9 + 0.055590x19 + 0.025023x65 + 0.003135x66 . The parity-check matrix of the LDPC code is generated by the progres- sive edge growth (PEG) algorithm [38,39] with degree-3 variable nodes and almost regular check nodes. The transmitter sends coded bits until the receiver successfully determines the correct message, at which point the 23 2.3. Metric Manipulation 0 2 4 6 8 10 12 14 0.2 0.3 0.4 0.5 0.6 0.7 0.8 w/o i.i.d. channel adaptor w/ i.i.d channel adaptor sum-product decoding max-product decoding Iq′ X,Y (1) c→ R at e [b p cu ] → Figure 2.5: Throughput achieved with a Raptor code over a BAC and SBS decoding with mismatched metrics versus the metric-scaling parameter c. instantaneous throughput is measured. Figure 2.5 shows the empirical av- erage throughput achieved with sum-product and max-product decoding as a function of c (consider only lines labeled “w/o i.i.d. channel adapter” for the moment). Both methods use a maximum of 200 iterations to decode the joint factor graph of the LDPC and LT codes [32, Fig. 1(b)]. The decoder uses an update schedule similar to the one described in [31, Sec. 4.3]. We observe that scaling with the factor c = sqX,Y indeed yields the best throughput for sum-product decoding. It can also be seen how the achieved throughput degrades as c → 0. For large c, sum-product decod- ing starts to converge towards max-product decoding. However, since we 24 2.3. Metric Manipulation applied LLR bounding for improved numerical stability in our decoder im- plementation, this convergence is not fully achieved in Figure 2.5. We can turn the asymmetric channel into a symmetric one by using i.i.d. channel adapters suggested in [40]. These adapters are synchronized random sign- adjusters applied to the encoded bits and LLR streams at the transmitter and receiver, respectively, cf. [40, Fig. 8]. With uniform input, the I-curve is not changed by i.i.d. channel adaptation, cf. (2.20). Symmetrization is sometimes considered useful when codes are designed under the assumption of a symmetric channel. The simulation results for the symmetrized chan- nel in Figure 2.5 (star makers labeled “w/ i.i.d. channel adapter”) show that the conclusions about scaling are not an artifact of transmission over asymmetric channels. Remark 1: Understanding the impact of metric scaling in fact relates to a familiar research problem. In systems with additive Gaussian noise, for example, inaccurate estimation of the signal-to-noise ratio (SNR) results in a mismatched metric that is a scaled version (in the logarithmic domain) of the matched metric. The scaling factor c is proportional to the estimated SNR. Thus, impact of SNR mismatch on sum-product decoding is a special case of our discussion. The results in Figure 2.5 agree with the known result that for sum-product decoding we would rather overestimate (have a large c) than underestimate the SNR (have a small c), cf. e.g. [41,42] and references therein. When sqX,Y > 1, which is the case of underestimated SNR, the simulation results in Figure 2.5 suggests an intriguing upper bound IqX,Y (1) to the achievable rate with sum-product decoding. 25 2.3. Metric Manipulation Remark 2: We would like to contrast our scaling from LLR scaling as investigated in e.g. [43–46]. In these works, scaling is derived from studying the internal operation of the decoder and has the purpose of offsetting ap- proximations to lower implementation complexity. On the other hand, our proposed scaling is characterized only by the metric and is aimed to improve the performance of exact sum-product decoding. Application to BICM: In connection with Theorem 2.1, in BICM with sum-product decoding we propose aligning all binary I-curves at s∗ = 1. For max-product decoding, only the alignment matters, but not the value of the critical point s∗. This is analogous to the case of word decoding considered in Section 2.3.1. 2.3.3 Cascaded Channel Model and Metric-Mismatch Correction BICM as defined by (2.12), (2.1) and (2.2) constitutes a mismatched decod- ing rule, for which an achievable rate is given by the GMI IgmiqX,Y defined in (2.7). In Section 2.3.1, we have shown that metric scaling applied to LLRs ΛqBi,Y (y) can increase this GMI. In this section, we consider the generation of ΛqBi,Y (y) as part of the transmission channel and determine the rates achievable by further processing and other ways of decoding. Cascaded Channel Model Let zi , ΛqBi,Y (y) be the channel output to be processed. Accordingly, we have a cascaded channel as shown in Figure 2.6(a) with input X and output Z , [Z0, . . . , Zm−1]. From the data-processing inequality [34, Sec. 2.3] [47, 26 2.3. Metric Manipulation (c) (d) (a) (b) zi ∈ R I(Bi;Ri) I(Bi;Zi) pY |X(y|x) y ∈ Y ΛqB0,Y (y), . . . ,ΛqBm−1,Y (y) pY |X(y|x) y ∈ Y ΛqB0,Y (y), . . . ,ΛqBm−1,Y (y) x ∈ X z ∈ Rm bi(x) ∈ B I(X;Z) I(Bi;Z) pY |X(y|x) y ∈ Y ΛqBi,Y (y) pY |X(y|x) y ∈ Y ΛqBi,Y (y), {ΛqBj,Y (y)} bi(x) ∈ B ri ∈ Rmi z ∈ Rm bi(x) ∈ B Figure 2.6: BICM demodulator as part of a cascaded channel. Also indicated above each block diagram is the associated average mutual information. (a) symbol-input cascaded channel; (b), (c) and (d) different binary-input cascaded channels. 27 2.3. Metric Manipulation Sec. 2.8], the corresponding average mutual information I(X;Z) is less than or equal to I(X;Y ). Let us consider the use of binary codes for the cascaded channel X → Z. The chain rule of mutual information [34, p. 22] reads as I(X;Z) = m−1∑ i=0 I(Bi;Z|B0, . . . , Bi−1) . (2.29) For the terms on the right-hand side, we have the following inequalities I(Bi;Z|B0, . . . , Bi−1) ≥ I(Bi;Z) (2.30) ≥ I(Bi;Zi) (2.31) ≥ IgmiqBi,Y . (2.32) The mutual information I(Bi;Z) in (2.30) represents the constrained chan- nel capacity, i.e. the maximum achievable rate with a given input distribu- tion, of the binary-input channel Bi → Z illustrated in Figure 2.6(b). For this cascaded channel, I(Bi;Z) ≤ I(Bi;Y ) [34, Sec. 2.3]. We note, how- ever, that there is no definitive relation between I(Bi;Z|B0, . . . , Bi−1) and I(Bi;Y ). The mutual information I(Bi;Zi) in (2.31) is the constrained ca- pacity of the channel Bi → Zi shown in Figure 2.6(c). Equality in (2.31) is achieved if Zi is a sufficient statistic for Bi given Z. Inequality (2.32) holds because IgmiqBi,Y is just an achievable rate by a mismatched decoding, whereas I(Bi;Zi) is the maximum achievable rate by matched decoding over the channel Bi → Zi. Inequality (2.31) suggests that Zj , j 6= i, can provide further information for the decoding of Bi. In between the two extremes of using only Zi and using all m elements of Z, we might opt to process a subset Ri = [Zi, {Zj}] 28 2.3. Metric Manipulation of 1 < mi < m elements of Z to produce decoding metrics for Bi. The resulting channel is included in Figure 2.6(d) and the inequalities I(Bi;Zi) ≤ I(Bi;Ri) ≤ I(Bi;Z) (2.33) hold for its associated mutual information. In summary, we obtain the following inequality chain: IgmiqX,Y ≤ m−1∑ i=0 IgmiqBi,Y ≤ m−1∑ i=0 I(Bi;Zi) ≤ m−1∑ i=0 I(Bi;Ri) ≤ m−1∑ i=0 I(Bi;Z) ≤  m−1∑ i=0 I(Bi;Y ) I(X;Z) ≤ I(X;Y ) . (2.34) Metric-Mismatch Correction The processing of original LLRs to achieve the above rates can be considered as metric-mismatch correction. The matched bit-metrics for BICM trans- mission over the cascaded channel X → Z corresponds to corrected LLRs ΛpZ|Bi (z) = ln pZ|Bi(z|0) pZ|Bi(z|1) (2.35) for i = 0, . . . ,m−1. This metric correction realizes the rate I(Bi;Z) over the binary-input channel Bi → Z, and, considering (2.34), it is the optimal cor- rection in terms of achievable rate. The bit-metric correction corresponding 29 2.3. Metric Manipulation to the channel Bi → Ri and achievable rate I(Bi;Ri) is given by ΛpRi|Bi (ri) = ln pRi|Bi(ri|0) pRi|Bi(ri|1) . (2.36) Finally, the scalar metric correction ΛpZi|Bi (zi) = ln pZi|Bi(zi|0) pZi|Bi(zi|1) (2.37) leads to I(Bi;Zi). Since metrics (2.35), (2.36), and (2.37) match to their cor- responding binary-input channels, their binary I-curves are already aligned at s = 1. As a result, the BICM GMI with these metrics is equal to∑m−1 i=0 I(Bi;Z), ∑m−1 i=0 I(Bi;Ri), and ∑m−1 i=0 I(Bi;Zi), respectively. While, according to (2.34), the associated BICM GMI degrades from (2.35) to (2.37), the computational complexity for metric correction is also reduced. This trade-off renders (2.36) and (2.37) potentially attractive. The scalar LLR correction (2.37) has been studied in the literature [24, 48–51], cf. also [52]. In [24], (2.37) has been shown to be the optimum scalar metric correction in terms of GMI, a fact that is also clear from the above derivation. It has further been pointed out in [24] that non-scalar metric correction functions could further increase the GMI. We have provided such corrections in (2.35) and (2.36). In practice, the correction functions are prepared offline and stored as look-up tables. Online evaluation is then done by table look-up and possibly with additional interpolation [51, 52]. For clarity, we summarize all bit- metric manipulations and their effects in Table 2.1. 30 2.3. Metric Manipulation Table 2.1: BICM metric manipulation methods and their effects. Metric Manipulation Effect Original mismatched LLR ΛqBi,Y (y) I gmi qX,Y ≤ ∑m−1 i=0 I gmi qBi,Y is achiev- able. Scale all LLRs by the same factor c = sqX,Y : Λq′Bi,Y (y) = sqX,Y ΛqBi,Y (y) Shift the critical point of the BICM I-curve to 1, aim to im- prove the performance of sum- product SBS decoding. Scale LLRs differently by factors ci = sqBi,Y /s ∗ for some s∗ > 0: Λq′Bi,Y (y) = (sqBi,Y /s ∗)ΛqBi,Y (y) Binary I-curves are aligned at s∗. The BICM GMI is Igmi q′X,Y =∑m−1 i=0 I gmi qBi,Y . Choose s∗ = 1 in sum-product SBS decoding. Apply scalar metric mismatch cor- rection: Λp i|Bi (zi) = ln pZi|Bi(zi|0) pZi|Bi(zi|1) Bit metrics are matched to the cascaded channels Bi → Zi. The BICM GMI is ∑m−1 i=0 I(Bi;Zi). Apply reduced-dimensional vector metric mismatch correction: ΛpRi|Bi (ri) = ln pRi|Bi(ri|0) pRi|Bi(ri|1) Bit metrics are matched to the cascaded channels Bi → Ri. The BICM GMI is ∑m−1 i=0 I(Bi;Ri). Apply optimal vector metric mis- match correction: ΛpZ|Bi (z) = ln pZ|Bi(z|0) pZ|Bi(z|1) Bit metrics are matched to the cascaded channels Bi → Z. The BICM GMI is ∑m−1 i=0 I(Bi;Z). 31 2.4. Applications Remark: Inequality (2.34) also shows that no metric manipulation allows BICM to attain a GMI better than ∑m−1 i=0 I(Bi;Y ), i.e., the GMI of matched BICM over the original channel X → Y . To achieve I(X;Z) or I(X;Y ) with binary codes, we need to use MLC with multistage decoding [5] applied to the channels X → Z and X → Y , respectively. 2.4 Applications In this section, we present and discuss a number of illustrative and rele- vant examples for BICM transmission applying the metric manipulations described in the previous sections. We assume uniform input in all cases. The binary I-curves are obtained from (2.20) via Monte-Carlo integration. 2.4.1 Discrete Metrics and Metric Correction Setup Metric corrections are relatively easy to implement by means of look-up tables if the mismatched metrics are drawn from a small set of discrete values. Such cases arise if quantization and in particular hard detection is applied at the receiver. In the following, we consider the example of 8-ary amplitude-shift keying (8-ASK) transmission over the additive white Gaus- sian noise (AWGN) channel with hard detection. We apply binary reflected Gray labeling with [b0b1b2] = [000], [100], [110], [010], [011], [111], [101], [001] for the eight signal points from left to right, as in Figure 2.7. This is the best labeling in the moderate SNR range [53], cf. also [54]. Let the SNR be equal to 6.43 dB, at which matched BICM attains a GMI of 32 2.4. Applications [001][000] [b0b1b2] = [100] [110] [010] [011] [111] [101] Figure 2.7: 8-ASK constellation and labeling. IgmiqX,Y = 2∑ i=0 I(Bi;Y ) = 1.50 bpcu, and I(X;Y ) = 1.56 bpcu. Hard detection that produces LLRs +1 and −1 leads to the GMI IgmiqX,Y = 1.07 bpcu, which is the maximum of the BICM I-curve IqX,Y (s) = 2∑ i=0 IqBi,Y (s), attained at sqX,Y = 1.65. The I-curves for matched and hard-decision decoding are plotted in Figure 2.8(d). Metric-Mismatch Correction We now examine the effect of metric manipulation. Consider level 2, whose I-curves are shown in Figure 2.8(c). With matched LLR, the binary GMI is I(B2;Y ) = 0.77 bpcu. With hard detection, B2 → Z2 is a BSC with the GMI equal to I(B2;Z2) = 0.63 bpcu, cf. Example 2.1. For a BSC, scalar correction (2.37) is identical to the scaling that shifts the critical point to 1 and leaves the GMI unchanged (line Z2 in Figure 2.8(c)). On the other hand, the optimum vector correction (2.35) yields I(B2;Z) = 0.75 bpcu (line Z2Z0Z1 in Figure 2.8(c)), which is significantly higher than I(B2;Z2) and rather close to I(B2;Y ). The price for this is a more complex mapping. In scalar correction, we map z2 from two input values {1,−1} to two output values {2.56,−2.56}, i.e., ΛpZ2|B2 (1) = 2.56 and ΛpZ2|B2 (−1) = −2.56. In optimum vector correction, we need a larger look-up table to map [z2, z0, z1] from {[1, 1, 1], [1,−1, 1], [1,−1,−1], [1, 1,−1], [−1, 1,−1], 33 2.4. Applications 0.5 1 1.5 2 0.05 0.1 0.15 0.2 0.25 matched hard Z0, Z0Z1, Z0Z2, or Z0Z1Z2 0.5 1 1.5 2 2.5 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 matched hard Z1 or Z1Z2 Z1Z0 or Z1Z0Z2 0.5 1 1.5 2 2.5 3 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 matched hard Z2 Z2Z0 Z2Z1 Z2Z0Z1 0.5 1 1.5 2 2.5 0.4 0.6 0.8 1 1.2 1.4 1.6 matched hard scalar (Z0+Z1+Z2) optimum (Z0 + Z1Z0 + Z2Z0Z1) s → s → s → s → (d) BICM (b) level 1(a) level 0 (c) level 2 B in a ry I- cu rv e [b p cu ] → B in a ry I- cu rv e [b p cu ] → B in a ry I- cu rv e [b p cu ] → B IC M I- cu rv e/ T h ro u h g p u t [b p cu ] → Figure 2.8: I-curves for 8-ASK transmission over the AWGN channel with matched detection (“matched”), hard detection (“hard”), and different metric-mismatch corrections (identified by the used LLRs zi in the sub- figures). Subfigures (a)-(c) show I-curves for binary levels. Subfigure (d) shows BICM I-curves. Bullet markers show simulated throughput using a Raptor code and sum-product decoding, and the double-arrowed arcs link the simulated points to the peak of the corresponding I-curves. 34 2.4. Applications [−1,−1,−1], [−1,−1, 1], [−1, 1, 1]} to the corrected LLRs {12.5, 7.40, 3.63, 1.05, −1.05, −3.63, −7.40, −12.5}. Between these two correction methods, we have two choices for reduced-dimensional vector correction (2.36), namely R2 = {Z2, Z0} or R2 = {Z2, Z1}, each of which maps four input values to four output values. The two corresponding I-curves in Figure 2.8(c) are labeled Z2Z0 and Z2Z1, respectively. Since I(B2;Z2Z0) < I(B2;Z2Z1), the latter is preferred. We have a BAC at both level 0 and 1. For level 1, we can see from Figure 2.8(b) that scalar correction hardly increases the GMI. It is interest- ing to observe that correction with R1 = {Z1, Z2} yields the same I-curve as scalar correction, whereas correction with R1 = {Z1, Z0} yields the same I-curve as the optimum correction. For level 0, different correction functions result in identical binary I-curves, as shown in Figure 2.8(a). These phe- nomena can be explained from examining the labeling of signal points. To avoid repetition, we only explain why knowing z0 helps to increase the GMI at level 1, whereas knowing z2 does not. Consider the labeling bits at level 1. They are {0, 0, 1, 1, 1, 1, 0, 0} for the eight symbols from left to right. We can divide the four labeling bits 1 into two groups: the outer two bits that are adjacent to a bit 0, and the other two inner bits which are not. To better approach the performance of the matched decoding, we should distinguish if a received bit 1 is an outer bit or an inner bit. Indeed, additional knowl- edge about z0 tells us if the received bit 1 at level 1 is an outer bit (when z0 = −1) or not (when z0 = 1). On the other hand, knowing z2 would not help. Similarly, the four labeling bits 0 can be divided into two groups, and knowledge of z0, but not z2, helps to distinguish if the received bit 0 is an 35 2.4. Applications inner or an outer bit. The BICM I-curve for scalar and the best of all metric-mismatch cor- rections are included in Figure 2.8(d). For the latter, full vector correction is only required for level 2, while scalar correction and reduced-dimensional correction are sufficient at level 0 and level 1, respectively. The increase in the GMI by scalar correction comes mostly from the effect of having all the binary curves aligned at s = 1. Optimum correction results in a much improved GMI of 1.40 bpcu, which is 93% of the GMI for matched BICM. Throughput Using the Raptor code from Example 2.1, the simulated average through- put is shown in Figure 2.8(d) (markers without lines). We observe that the throughput closely follows the associated GMIs if metric-mismatch correc- tion is applied. In these cases, the GMI is achieved at s = 1. In the case of hard detection metrics, the gap between GMI and simulated rate is sig- nificantly larger. This phenomenon has also been observed in Figure 2.5. It corroborates our discussion in Section 2.3.2 that, when sqX,Y > 1, the achieved throughput by sum-product SBS decoding seems to be determined by IqX,Y (1) rather than the GMI. 2.4.2 Noncoherent Carrier-Modulated Orthogonal Signaling Carrier-modulated orthogonal signaling (orthogonal modulation) with non- coherent detection is attractive due to its low complexity detector imple- mentation. This type of signaling, e.g. in the form of frequency shift-keying 36 2.4. Applications (FSK) and pulse-position modulation (PPM), has been used in scenarios where coherent detection is impossible or expensive to employ. Examples of such scenarios include fast fading environment and large Doppler spread in military communications. Transmission Model An M -ary orthogonal transmit symbol can be represented by a vector x = [x0 . . . xM−1] of M elements where only one element is one and all the others are zero. Let h = a ejφ be the complex channel gain, and n be the length-M complex AWGN vector with variance N0 per element. The received sample is a length-M complex vector y = a ejφ x+ n . (2.38) Noncoherent detection requires only knowledge of the magnitude of the chan- nel gain and received sample. The channel transition probability is [55] pY |X(y|x) ∝ I0 ( 2a|ye(x)| N0 ) , (2.39) where I0(·) is the zeroth order modified Bessel function of the first kind [56], and |ye(x)| is the magnitude of the element of y at the position of the non- zero element of x. 37 2.4. Applications Metrics The matched LLR metric for noncoherent orthogonal modulation is Λmatchedi (y) = ln pY |Bi(y|0) pY |Bi(y|1) = ln ∑ x∈X 0i I0 ( 2a|ye(x)| N0 ) ∑ x∈X 1i I0 ( 2a|ye(x)| N0 ) , (2.40) The popular max-log LLR metric is Λmax−logi (y) = max x∈X 0i ln I0 ( 2a|ye(x)| N0 ) − max x∈X 1i ln I0 ( 2a|ye(x)| N0 ) . (2.41) Since both functions ln(·) and I0(·) are monotonic with positive input, the max-log LLR can be presented as Λmax−logi (y) = ln I0 ( 2a N0 max x∈X 0i |ye(x)| ) − ln I0 ( 2a N0 max x∈X 1i |ye(x)| ) . (2.42) That is, the detector can search for the maximum values of |ye(x)| before computing ln I0(·). We now consider metrics resulting from approximation to the function ln I0(α) with positive α ∈ R as illustrated in Figure 2.9. When α is large, I0(α) can be asymptotically approximated by e α/ √ 2piα and ln I0(α) can be approximated α. From (2.42), this approximation leads to a new LLR Λa−max−logi (y) = 2a N0 ( max x∈X 0i |ye(x)| − max x∈X 1i |ye(x)| ) . (2.43) 38 2.4. Applications 0 2 4 6 8 10 12 0 2 4 6 8 10 12 α ln(I0(α)) α→ α2 4 Figure 2.9: Approximation to the function ln(I0(·)). A similar metric has been considered in [57]. When α is small, I0(α) can be approximated by the first two terms in its power series expansion 1 + α2/4, and ln I0(α) can be approximated by α2/4. The corresponding LLR is Λps−max−logi (y) = a2 N20 ( max x∈X 0i |ye(x)|2 − max x∈X 1i |ye(x)|2 ) . (2.44) Metrics (2.43) and (2.44) require less computational complexity than the max-log metric (2.42), which in turn is computationally cheaper than the matched metric (2.40). If we drop the factor 2a/N0 in (2.43) and a 2/N20 in (2.44), we have the 39 2.4. Applications parameter-free metrics Λpf−a−max−logi (y) = max x∈X 0i |ye(x)| − max x∈X 1i |ye(x)| , (2.45) Λpf−ps−max−logi (y) = max x∈X 0i |ye(x)|2 − max x∈X 1i |ye(x)|2 . (2.46) Both channel gain and noise power estimation are not needed in the cal- culation of these metrics. This simplification further reduces the detection complexity. The parameter-free power series max-log metric (2.46) has been considered in [58] for BICM with iterative decoding (BICM-ID) [59,60]. Numerical Results For orthogonal constellations, all levels have the same binary I-curves if the same metric is applied. Thus, the BICM I-curve is simply m times the binary I-curve of any level, and the BICM GMI is m times the binary GMI (2.19). GMI: We consider the cases M = 4, 16, and 64 and AWGN and Rayleigh fading channels. Figure 2.10 shows the BICM GMI with the matched met- ric (2.40) and the five mismatched metrics (2.42), (2.43), (2.44), (2.45), and (2.46) at different SNR values (defined as E{a2}/N0). It is interesting, and perhaps surprising, to observe that all the five mismatched metrics attain practically the same GMI across the whole SNR range. Furthermore, this GMI is very close to that of the matched metric. Throughput with SBS Decoding: Figure 2.11 shows the BICM I-curve of the case M = 16 and AWGN channel at a moderate SNR of 6.35 dB, where all mismatched metrics attain a GMI of 2.0 bpcu. The BICM I- 40 2.4. Applications 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 GMI, matched metric GMI, mismatched metrics 5 10 15 20 0 1 2 3 4 5 6 GMI, matched metric GMI, mismatched metrics R at e [b p cu ] → M = 64 M = 16 M = 4 SNR [dB] → (a) AWGN channel M = 64 M = 16 M = 4 SNR [dB] → (b) Rayleigh fading channel R at e [b p cu ] → Figure 2.10: BICM GMI of noncoherent orthogonal modulation. 41 2.4. Applications curve of the max-log (2.42), asymptotic max-log (2.43), power series max- log (2.44), parameter-free asymptotic max-log (2.45), and parameter-free power series max-log (2.46) peaks at s = 0.83, 0.77, 0.19, 6.6, and 3.5, respectively. In comparison, the BICM I-curve of the matched metric (2.40) has a slightly larger GMI and peaks at s = 1. Below the peak of each I- curve, we present the average throughput obtained by simulation with the Raptor code from Example 2.1 and sum-product SBS decoding. We see that while the mismatched GMIs are the same, the throughputs are notably different. Furthermore, for each of the two parameter-free metrics with critical point of the I-curve greater than 1, the throughput is upper bounded by IqX,Y (1). Following Section 2.3.2, we apply constant LLR scaling with the factor 0.83, 0.77, 0.19, 6.6, and 3.5 to the metric (2.42), (2.43), (2.44), (2.45), (2.46), respectively. Now, the scaled mismatched metrics achieve the same throughput of 1.86 bpcu, which agrees with the corresponding GMI. This throughput leaves just a small gap to the throughput of the matched metric. Therefore, metric scaling appears to provide a very favorable trade- off between complexity and effect of metric-mismatch correction. However, we note that the factor for metric scaling is SNR-dependent, and thus the seemingly parameter-free metrics lose advantage over their counterparts if scaling is applied. Next, we consider the throughput with max-product decoding. The re- sults are also included in Figure 2.11. Mismatched metrics attain a through- put of approximately 1.34 bpcu. The throughput seems to be determined by the GMI alone. Although the throughput is lower than in the case of sum-product decoding with metric scaling, the low detection complexity 42 2.4. Applications 0.1 0.19 0.3 0.5 1 1.34 1.86 2 2.5 Sum−product Sum−product w/ scaling Max−product 0.5 1 0.5 1 1.34 1.86 2 2.5 0 1 3.5 6.6 0.5 1 1.34 1.86 2 2.5 p s- m a x -l og m ax -l o g a -m a x -l og p f- a- m ax -l og p f- p s- m a x -l og s→ R at e [b p cu ] → m a tc h ed Figure 2.11: BICM I-curve and coded throughput of 16-ary noncoherent orthogonal modulation over AWGN channel at SNR of 6.35 dB. associated the parameter-free metrics is particularly attractive. Similar phenomena are observed for the case M = 16, Rayleigh fading channel, and SNR of 8.5 dB in Figure 2.12: (i) the mismatched metrics achieve GMIs that are close to that of the matched metric; (ii) sum-product decoding with metric scaling attains improved throughout; and (iii) the combination of parameter-free metrics with max-product decoding is a low- complexity option for noncoherent orthogonal modulation. We note an ex- ception for the throughput of power series max-log metric with sum-product decoding. It is expected to be larger than that of max-product decoding. 43 2.4. Applications 0.05 0.086 0.15 0.5 1 1.5 2 2.5 Sum−product Sum−product w/ scaling Max−product 0.5 1 0.5 1 1.5 2 2.5 1 4.4 6.3 0.5 1 1.5 2 2.5 s→ R at e [b p cu ] → p s- m ax -l og m ax -l og a- m ax -l og p f- a- m ax -l og p f- p s- m ax -l og m at ch ed Figure 2.12: BICM I-curve and coded throughput of 16-ary noncoherent orthogonal modulation over Rayleigh fading channel at SNR of 8.5 dB. However, the LLR values are often too large, cf. Figure 2.9, that they are clipped by our decoder implementation to avoid numerical overflow, result- ing in a reduced throughput. 2.4.3 Pulse-Position Modulation with Direct Detection Our next example considers M -ary pulse-position modulation (PPM) with intensity modulation and direct detection. It is a popular signaling scheme for fiber and free-space optical communication, cf. e.g. [61]. Each M -ary 44 2.4. Applications PPM symbol is a vector x = [x0 . . . xM−1] with exactly one element equal to 1 (on slot) and the others equal to 0 (off slots). We apply the photon- counting channel model [61], by which the received vector is y = [y0 . . . yM−1] and yi = xiai + ni . (2.47) The variables ai and ni are i.i.d. Poisson random variables with mean λs and λb, respectively. The channel transition probabilities are given by p(yi|xi) = (λsxi + λb) yi yi! exp (−[λsxi + λb]) , (2.48) and p(y|x) = ∏M−1i=0 p(yi|xi). It follows that p(y|x) ∝ ( 1 + λs λb )yo(x) , (2.49) where yo(x) is the magnitude of the slot of y which corresponds to the on slot of x. The matched LLR for PPM is ΛpY |Bi (y) = ln ∑ x∈X 0i ( 1 + λsλb )yo(x) ∑ x∈X 1i ( 1 + λsλb )yo(x) . (2.50) The simplified max-log metric is ΛqBi,Y (y) = ( max x∈X 0i yo(x)− max x∈X 1i yo(x) ) ln ( 1 + λs λb ) , (2.51) which has considerably lower computational complexity than (2.50). 45 2.4. Applications −10 −9 −8 −7 −6 −5 −4 −3 −2 0 1 2 3 4 5 6 GMI, matched GMI, max−log Iq X,Y (1), max−log 10 log10(λs/(Mλn)) [dB] → R at e [b p cu ] → Figure 2.13: BICM GMI for decoding with matched metric and max-log metric, and IqX,Y (1) for max-log metric. 64-PPM transmission over Poisson channel. Background radiation has mean λb = 0.2 photon/slot. Similar to the carrier-modulated signaling schemes in Section 2.4.2, PPM constellations are orthogonal and thus, the BICM I-curve and GMI are m times the binary I-curve and GMI of any level if the same metric is ap- plied at all levels. Figure 2.13 shows the GMI of matched metric (2.50) and max-log metric (2.51) as a function of the SNR for the example of 64- PPM and λb = 0.2 [62]. We observe only a relatively small gap between the two GMIs. This suggests that the max-log metric (2.51) could be ap- plied with little loss in the achievable rate. Also included in Figure 2.13 is IqX,Y (1) for the max-log metric, for which a notable gap to the correspond- 46 2.4. Applications ing mismatched GMI can be seen, especially at low SNR values. Following the discussion in Section 2.3.2, we expect that scaling the max-log LLR such that the critical point is shifted to 1 should be applied to improve the performance of sum-product decoding. This prediction is confirmed by the results presented in Figure 2.14 for an example SNR of −8 dB. It shows the I-curves for matched, max-log, and scaled max-log metric with the scaling factor c = sqX,Y = 0.56, together with simulated throughputs for sum-product and max-product decoding. The throughput figures are obtained from simulation using the same Raptor code as in Example 2.1. We observe that the simulated throughput using sum-product decoding well approaches the associated GMI for matched metric. For the max-log met- ric, however, the gap between throughput and GMI is considerably larger. With scaling, the throughput accomplished with sum-product decoding is significantly improved to 1.96 bpcu compared to 1.74 bpcu without scal- ing. More specifically, the gap between throughput and GMI is closed by 60%. Finally, the performance of max-product decoding is notably inferior to sum-product decoding and, as expected, is not changed by scaling. 2.4.4 MIMO-QAM with Clipped Max-Log Metric The final illustration of BICM with mismatched decoding metric and metric- mismatch correction uses the example considered in [24, Sec. IV]. The trans- mission system is a 2 × 2 multiple-input multiple-output (MIMO) system with 16-ary quadrature amplitude modulation (16-QAM) and Rayleigh fad- ing channels, and the average SNR is fixed to 9.13 dB. Furthermore, the BICM demodulator uses the max-log metric and the max-log LLR is clipped 47 2.4. Applications 0.2 0.4 0.6 0.8 1 1.2 1.4 1.2 1.4 1.6 1.8 2 2.2 2.4 sum−product max−product max−log matched scaled max−log s→ I- cu rv e / T h ro u gh p u t [b p cu ] → Figure 2.14: BICM I-curve and simulated rates. Matched, max-log, and scaled max-log metric with the scaling factor c = sqX,Y = 0.56. The bul- let markers show simulated rates using a Raptor code and sum-product and max-product decoding. 64-PPM over Poisson channel at SNR of 10 log10(λs/(Mλb)) = −8 dB and λb = 0.2 photon/slot. to the range [−2,+2]. LLR clipping is helpful to reduce complexity in list- based detection [51]. It has been shown in [24, Sec. IV] that the optimum scalar correction (2.37) improves the GMI and the bit-error rate (BER) per- formance of the coded scheme. In this section, we also consider LLR scaling and a hybrid scalar correction as explained below. We assume a binary reflected Gray labeling for the 16-QAM symbols. The 2× 2 MIMO system with 16-QAM has in total m = 8 binary levels, of which four are equivalent to level 0 and four to level 1. Hence, we only need 48 2.4. Applications to consider those two levels when showing results. Figure 2.15(a) presents the I-curves of the levels with matched and clipped max-log metrics. The curves for the matched metrics serve as an upper bound and will be used to gauge the success of mismatched-metric manipulation. It can be seen that the two binary I-curves for the clipped max-log metric are misaligned. We expect that scaling to align them at s∗ = 1 will increase the BICM GMI and improve sum-product decoding performance. The BICM GMI curves for matched, clipped max-log, and scaled clipped max-log metric are shown in Figure 2.15(b). Also included are simulated throughputs, again using the Raptor code from Example 2.1 with sum-product decoding. We observe that, for clipped max-log with sqX,Y = 1.50 > 1, the throughput seems to be upper bounded by IqX,Y (1). This might explain the large gap between the BER curve and the GMI limit of the uncorrected LLR in [24, Fig. 2(b)]. Metric scaling aligns the binary I-curves at s∗ = 1 and leads to an improved GMI. While the GMI increase is only slightly, the throughput improvement is much more significant. Applying the optimum scalar metric-mismatch correction (2.37), also considered in [24, Sec. IV], [51, Sec. V], further improves both the GMI and the performance with sum-product decoding. At the same time, it is more complex than scaling as the correction requires table look-up and interpo- lation (see also the plot of the scalar correction function in Figure 2.16 and the discussion below). Noting that metric scaling treats all values ΛqBi,Y (y) the same, even though the two extreme values −2 and +2 would warrant a special consideration, we propose the following hybrid metric manipulation 49 2.4. Applications 0.5 1 1.5 2 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 matched clipped max−log scaled scalar correction hybrid 0.5 1 1.5 2 3.2 3.4 3.6 3.8 4 4.2 4.4 matched clipped max−log scaled scalar correction hybrid (a) (b) level 0 level 1 R a te [b p cu ] → s→ R at e [b p cu ] → s→ Figure 2.15: I-curves for 2 × 2 MIMO transmission as in [24, Sec. IV]. Matched, clipped max-log, scaled clipped max-log metric that shifts the critical point of the I-curve to 1, scalar metric-mismatch correction, and a hybrid correction. (a) I-curves for binary levels. (b) BICM I-curves. The bullet markers show simulated rates using a Raptor code and sum-product decoding, and the double-arrowed arcs link the simulated points to the peak of the corresponding I-curves. The curves for “scalar correction” and “hy- brid” are numerically on top of each other. 50 2.4. Applications −2 −1 0 1 2 −4 −2 0 2 4 linearly scaled scalar correction hybrid −2 −1 0 1 2 −4 −2 0 2 4 linearly scaled scalar correction hybrid input LLR input LLR level 0 level 1 ou tp u t L L R ou tp u t L L R Figure 2.16: Metric manipulations for 2 × 2 MIMO transmission with 16- QAM over Rayleigh fading and SNR of 9.13 dB. Hybrid metric manipulation requires channel symmetrization before applying (2.52). 51 2.5. Conclusion for this particular case: Λq′Bi,Y (y) =  ln pZi|Bi (zi|0) pZi|Bi (zi|1) , if zi = ±2 cizi , otherwise . (2.52) That is, the two extreme LLR values are mapped as in the optimum scalar correction, and the immediate values are scaled with a factor such that the resulting I-curve peaks at s = 1. This correction function is indeed a good approximation of the optimum scalar correction for the symmetric channel at level 1. However, this is not the case for the asymmetric channel at level 0. Hence, we apply channel symmetrization according to [40] as discussed in Example 2.1 before using the hybrid rule (2.52). The different metric ma- nipulations are plotted in Figure 2.16. From Figure 2.15, we observe that hybrid manipulation results in I-curves and throughput performances that are practically identical to those achieved with optimum scalar correction. Considering its simpler implementation, this hybrid metric manipulation would be the method of choice for this application example. 2.5 Conclusion We have studied BICM with mismatched decoding metrics. We adopted the GMI as a pertinent performance measure and showed that scaling of logarithmic bit-metrics can improve the BICM GMI. We also suggested and provided numerical evidence that metric scaling also improves throughput in practical coding schemes using SBS decoding, even if the GMI remains 52 2.5. Conclusion unchanged. Furthermore, we studied general mismatched metric correc- tion methods, including a previously proposed scalar correction. We pre- sented a number of practically relevant applications in which mismatched demodulation occurs, and our numerical results highlighted the benefits and performance-complexity trade-offs for the different metric-mismatch correc- tion approaches. 53 Chapter 3 Multilevel Coding: Reduced-Layer, General Decoding Metrics, and Rateless Transmission MLC enables the combination of binary ECC with multilevel constella- tions [4, 5]. It can achieve the same rate as coded transmission with non- binary codes. In comparison, BICM also combines binary ECC with multi- level constellations, but in a simpler layout with just one instead of several coding layers and decoding stages as in MLC. The disadvantage of BICM over MLC is some rate loss. This loss can be small with Gray mappings [53] and thus, BICM has been widely employed in practice. Nevertheless, there are important cases where Gray mapping does not exist, or loses its relevance when the Euclidean-distance neighborhood of signal points is changed by the channel. For these cases, MLC might considerably outperform BICM. Ex- amples of such cases are multiple-input multiple-output (MIMO) signaling and orthogonal modulation. In this chapter, we present a number of contri- 54 Chapter 3. Multilevel Coding butions to the development of MLC. Our contributions can be grouped into three sections as follows. Conventional MLC requires as many coding layers (and thus encoder- decoder pairs) as the number of levels. In Section 3.1, we introduce the general scheme of reduced-layer MLC (RL-MLC) which can decrease the number of coding layers with a trade-off to the achievable rate. RL-MLC is a generalization of a previous work [12]. Conventional MLC and BICM are special cases of RL-MLC where the number of layers equals the number of levels and one, respectively2. In Section 3.2, we consider the use of general decoding metrics in MLC3. We show that, for any metric, the maximum achievable rate of MLC equals the sum of the maximum achievable rates of the layers. Furthermore, these layer rates can be estimated separately with the assumption that estimated data from lower layers is always correct. We then view each layer as a BICM scheme and adopt the results as presented in Chapter 2 for BICM into the MLC case. In particular, we use the GMI as an indication of the maximum achievable rate, and apply metric manipulations to improve the performance of MLC. Recently, the notion of rateless transmission has gained much attention in the communications community, e.g., [13, 37]. In the context of MLC, rateless transmission offers at least two attractive features. Firstly, it would 2We would like to stress the difference between “level” and “layer.” Each level corre- sponds to a bit position in the labels of the signal points. Each layer corresponds to an encoder-decoder pair, and may be comprised of one or multiple levels. 3Henceforth, without further clarification, by “MLC” we to refer to the general RL- MLC scheme. When the reduced-layer nature is material in a discussion, we will make it explicit. 55 Chapter 3. Multilevel Coding eliminate the need for carefully tailoring code rate for each layer, e.g. ac- cording to the capacity design rule [5, Sec. IV-A]. Secondly, for transmission over time-varying channels, rateless codes seamlessly adapt to the instanta- neous channel quality and attain a larger average throughput compared to channel adaptation by switching between fixed-rate codes. In Section 3.3, we propose a novel rateless MLC scheme, which is compatible with any de- coding metric and requires only one binary rateless code. We illustrate that combining rateless codes with MLC is not as straightforward as it is with BICM, and that a careless combination might lead to a considerable rate loss compared to fixed-rate MLC. We distinguish between coding loss due to the imperfectness of the code, and structural loss due to the structure of MLC. In our proposed scheme, the structural loss is non-zero only in so- called unstable systems. The stable or unstable nature of a rateless MLC scheme depends on the relationship between achievable rates of the layers. We illustrate that structural loss can be largely alleviated by controlling the acknowledgment delay from the receiver, and in practice a simple minimum segment-length (MSL) control rule can be effective enough in reducing this loss and maintaining the rate advantage of MLC. Application of our contributions to MIMO and orthogonal modulation systems are presented in Section 3.4. Section 3.5 completes the chapter with concluding remarks. 56 3.1. Reduced-Layer MLC MAP channel E2 E1 E0 D0 D1 D2 x y b0 b1 b2 b̂0 b̂1 b̂2 Figure 3.1: Example of conventional MLC. 3.1 Reduced-Layer MLC We consider a discrete-time memoryless channel with transmit symbol X ∈ X and received symbol Y ∈ Y. Let M = 2m be the cardinality of X and B0, . . . , Bm−1 be the random variables of the labeling bits. The concept of reduced-layer MLC is best described by an example. Figure 3.1 shows the diagram of conventional MLC [5] with an 8-ary constellation. At the transmitter, there are m = 3 independent binary encoders E0, E1, and E2 which produce encoded bits for the mapper. At the receiver, there are three binary decoders working in three consecutive stages. In the first stage, estimation of b0 is based on the channel output y alone. In the second stage, estimation of b1 is based on the channel output y and b̂0 (the estimated value b0). Finally, in the third stage, estimation of b2 is based on y, b̂0, and b̂1. In conventional MLC, the number of coding layers is equal to the number of labeling bits. For large constellations, this structural complexity becomes cumbersome. In reduced-layer MLC, we combine several layers into one, as in BICM. For example, we can reduce the number of coding layers from three 57 3.1. Reduced-Layer MLC channelMAP (a) E1 E0 D0 D1 b0 x y b̂0 b1, b2 b̂1, b̂2 channelMAP (b) E1 E0 D0 D1 x y b0, b1 b2 b̂0, b̂1 b̂2 Figure 3.2: Two examples of reduced-layer MLC. to two as in Figure 3.2. In Figure 3.2(a), layer 1 and 2 are combined into a single layer. In Figure 3.2(b), layer 0 and 1 are combined. Given the number of levels m and the number of layers κ < m, there are κ!S(m, k) possible combinations, where S(m, k) is the Stirling number of the second kind. For the best throughput performance, we want to choose the configuration which yields the largest achievable rate. Rate analysis for reduced-layer MLC is presented in Section 3.2. Full enumeration to find the best configuration is possible for small κ, which is typically the design goal. In many cases, we can also expedite the search by exploiting special properties of the signaling scheme, as in Example 3.1 below. 58 3.2. Multilevel Coding with General Decoding Metrics 3.2 Multilevel Coding with General Decoding Metrics In this section, we first establish that the MLC achievable rate can be ex- pressed in terms of the achievable rates of the layers. Applying this result, we then focus on the transmission over each MLC layer and provide expres- sions for the per-layer GMI. Based on these expressions, we propose metric- mismatch correction technique for MLC. The latter two contributions are an extension of the results in Chapter 2 to the MLC case. 3.2.1 Achievable Rates Given a detection rule, we say the rate C is achievable if for any  > 0 and sufficiently large N , there exists a code C(N ′, R) of length N ′ ≥ N and rate R ≥ C and a decoding algorithm D such that the block error probability is less than or equal to , cf. [34, Ch. 5], [63, Ch. 10]. We say C is the maximum achievable rate if it is the tightest upper bound on achievable rates. We have the following theorem regarding achievable rates of MLC. Theorem 3.1. Given a detection rule, let Ck be an achievable rate of the k- th layer given decoding decisions from lower layers are correct, k = 0, . . . , κ− 1. The MLC scheme achieves rate C = ∑κ−1 k=0 Ck. Furthermore, if each Ck is the maximum achievable rate of layer k, then C is the maximum achievable rate of the MLC scheme. Proof. We first show achievability. Let Ck and mk be an achievable rate 59 3.2. Multilevel Coding with General Decoding Metrics and the number of levels (bits) in layer k, respectively. That is, in layer k, conditioned on correct decoding at all lower layers 0, . . . , k−1, for any k > 0 and large enough N , there exists a code Ck(mkN ′, Rk) of length mkN ′ > N and rate Rk ≥ Ck and a decoding algorithm Dk such that the block error probability Pk ≤ k. MLC with these codes has rate R ≥ C = ∑κ−1 k=0 Ck. Furthermore, the block error probability of MLC is upper bounded by [64, Inequality 4.1] P ≤ κ−1∑ k=0 Pk ≤ κ−1∑ k=0 k =  . (3.1) Hence, rate C is achievable. Now let Ck be the maximum achievable rate for each layer k and C =∑κ−1 k=0 Ck. Transmission with rate R > C by the MLC scheme requires that at least one layer, say k′, has to transmit with rate Rk′ > Ck′ . Hence, there exists an  > 0 such that for any code and decoding algorithm at this layer, the block error probability is Pk′ > . Since P ≥ Pk ∀k , (3.2) C is the maximum achievable rate for MLC. We have the following remarks. Firstly, as the theorem makes no as- sumptions about detection rules being matched to the channel transition probabilities, it can be applied to mismatched decoding in the layers. Sec- ondly, Theorem 3.1 allows us to consider each layer separately without con- cerning about error propagation when estimating achievable rates and when manipulating mismatched metrics to increase these rates. 60 3.2. Multilevel Coding with General Decoding Metrics . . . . . . (b) Receiver (a) Transmitter . . . v̂0 v̂1 ûκ−1 û1 = v̂0 x MAP Eκ−1 E0 E1 y v0 vκ−1 v1 D1 Dκ−1 D0 Figure 3.3: MLC transmitter and receiver. 3.2.2 Per-Layer Transmission and GMI Since the maximum achievable rate of a mismatched decoding scheme is not known in general [65], we follow recent literature on BICM [8,9] and use the GMI as an approximation to the layer maximum achievable rate. An m-level, κ-layer MLC configuration can be described by a length-m vector h = [h0 . . . hm−1] with hi ∈ {0, . . . , κ − 1} and hj ≤ hi if j < i. The element hi = k indicates that level i is in layer k. The MLC transmitter with κ independent binary encoders is presented in Figure 3.3(a). The corre- sponding MLC receiver with κ binary decoders is presented in Figure 3.3(b). Let Vk be the multivariate random variable of the labeling bits at layer k. 61 3.2. Multilevel Coding with General Decoding Metrics That is, the elements of Vk are {Bi : hi = k}. In Vk and other multivariate random variables below, we assume that the binary random variables {Bi : hi = k} are ordered by their index i. At the receiver, the detection of Bi depends on the received symbol Y and the estimated value of bits from lower layers. Let Di denote the multivariate random variable of these lower-layer bits, i.e., the elements of Di are {Bj : hj < hi}. Furthermore, let bi(X) and di(X) denote the value of Bi and Di corresponding to the transmit symbol X. In conventional MLC where each level is put in a separate layer, h = [0 . . .m − 1] and Di = [B0 . . . Bi−1]. In BICM where all levels are grouped into one layer, h = 01×m and Di = ∅. Let Uk be the multivariate random variable of all lower-layer bits common to all levels at layer k. The elements of Uk are {Bj : hj < k}. For the scheme in Figure 3.2(a), h = [0 1 1], V0 = [B0], V1 = [B1 B2], U0 = D0 = ∅, and U1 = D1 = D2 = [B0]. The detector calculates bit metrics of the general form qBi,Y,D̂i(b, y, d) for Bi based on the received sample y ∈ Y and estimated data from lower layers d ∈ B|Di|, B = {0, 1}. We assume qBi,Y,D̂i(b, y, d) > 0, ∀ b ∈ B, y ∈ Y, and d ∈ B|Di|. The corresponding LLR is defined as ΛqBi,Y,D̂i (y, d) , ln qBi,Y,D̂i(0, y, d) qBi,Y,D̂i(1, y, d) . (3.3) For all levels i at layer k, we have Di = Uk. Thus, qBi,Y,D̂i(b, y, d) can also be written as qBi,Y,Ûk(b, y, u). The layer metric is defined as qVk,Y,Ûk(v, y, u) = ∏ i:hi=k qBi,Y,Ûk(b, y, u) , (3.4) 62 3.2. Multilevel Coding with General Decoding Metrics with v ∈ B|Vk| and u ∈ B|Uk|. From Theorem 3.1, in the following calculations we assume that the estimated data from lower layers is always the same as transmitted. That is, we use Di instead of D̂i, and Uk instead of Ûk. For the i-th level and bit metric qBi,Y,Di(b, y, d), the binary I-curve is defined as IqBi,Y,Di (s) , −EBi,Y,Di { log ∑ b∈B pBi(b) [ qBi,Y,Di(b, Y,Di) qBi,Y,Di(Bi, Y,Di) ]s} (3.5) = −EX,Y { log ∑ b∈B pBi(b) [ qBi,Y,Di(b, Y, di(X)) qBi,Y,Di(bi(X), Y, di(X)) ]s} .(3.6) With uniform input, the binary I-curve can be expressed in terms of the LLR as, cf. (2.20) IqBi,Y,Di (s) = 1− EX,Y { log(1 + exp(− sgn(bi(X))ΛqBi,Y,Di (Y, di(X))s) } . (3.7) The binary GMI of the level is the peak value of this curve, IgmiqBi,Y,Di , max s>0 IqBi,Y,Di (s) . (3.8) For matched metrics, i.e., when qBi,Y,Di(b, y, d) is proportional to the tran- sition probability pY |Bi,Di(y|b, d), the binary I-curve peaks at s = 1 and the GMI equals the average mutual information I(Bi;Y |Di). The layer I-curve corresponding to the layer metric qVk,Y,Uk(v, y, u) is 63 3.2. Multilevel Coding with General Decoding Metrics defined as IqVk,Y,Uk (s) , −EVk,Y,Uk log ∑ v∈B|Vk| pVk(v) [ qVk,Y,Uk(v, Y, Uk) qVk,Y,Uk(Vk, Y, Uk) ]s = −EX,Y log ∑ v∈B|Vk| pVk(v) [ qBi,Y,Di(v, Y, uk(X)) qBi,Y,Di(vk(X), Y, uk(X)) ]s . (3.9) As in Section 2.2.3, the layer I-curve can be shown to be equal to the sum of the binary I-curves of the levels, IqVk,Y,Uk (s) = ∑ i:hi=k IqBi,Y,Di (s) . (3.10) The layer GMI is the peak value of this layer I-curve, IgmiqVk,Y,Uk , max s>0 IqVk,Y,Uk (s) . (3.11) By Theorem 3.1, the MLC scheme achieves a rate equal to the sum of the layer GMIs. For convenience, we call this rate the MLC GMI. We note that Theorem 2.1 is also applicable to the per-layer MLC transmission. That is, layer GMI (3.11) is less than or equal to the sum of the binary GMIs (2.19) in that layer. Equality is achieved if and only if the binary I-curves are harmonic. Example 3.1. We consider IM-DD PPM transmission as in Section 2.4.3. Given the number of levels m and the number of layers κ, we want to find the MLC configuration which yields the largest MLC GMI. Due to the orthogonality of the PPM constellation, all levels in the same layer will 64 3.2. Multilevel Coding with General Decoding Metrics have the same binary I-curve if the same metric is applied. Let Igmi(i) be the binary GMI of level i when the lower-layer bits are Di = [B0 . . . Bi−1]. Furthermore, let mk be the number of levels at layer k. The MLC GMI is then equal to Igmi = κ−1∑ k=0 mkI gmi ( k−1∑ i=0 mi ) . (3.12) Thus, we only need to obtain at most m binary GMI values Igmi(0), . . . , Igmi(m− 1) in order to calculate the GMI of any MLC configuration. We consider 128-PPM (hencem = 7) with background radiation λb = 0.2 photons/slot and matched LLR ΛqBi,Y,D̂i (y, d) = ln ∑ x∈X d,0di,i pY |X(y|x) ∑ x∈X d,1di,i pY |X(y|x) , (3.13) = ln ∑ x∈X d,0di,i ( 1 + λs λb )ye(x) ∑ x∈X d,1di,i ( 1 + λs λb )ye(x) , (3.14) where the notation X d,0di,bi (X d,1 di,bi ) denotes the set of x that has the labeling bits di(x) = d and bi(x) = 0 (bi(x) = 1). The GMI of conventional MLC, BICM, 2-layer MLC specified by h = [0 0 0 0 1 1 1], and 3-layer MLC specified by h = [0 0 0 1 1 2 2] are plotted in Figure 3.4. We recall h = [0 0 0 0 1 1 1] indicates that the lower four levels are grouped into layer 0 and the remaining three levels are grouped into layer 1. Similarly, 65 3.2. Multilevel Coding with General Decoding Metrics −12 −11 −10 −9 −8 −7 −6 −5 1 2 3 4 5 6 7 Conventional MLC (7 layers) BICM (1 layer) 2−layer MLC 3−layer MLC R at e [b p cu ] → 10 log10 λs/M [dB] → Figure 3.4: GMI of conventional MLC, BICM, and 2-layer MLC for 128- PPM over Poisson channel with λb = 0.2. h = [0 0 0 1 1 2 2] indicates that the lowest three levels are groups into layer 0, the next two levels are grouped into layer 1, and the highest two levels are grouped into layer 2. The plots show that conventional MLC can outperform BICM by a large GMI gap. MLC with only two layers can close this GMI gap by more than a half. MLC with three layers further narrows the gap. Thus, reduced-layer MLC enables a trade-off between the achievable rate and the number of decoding layers. 66 3.3. Rateless Multilevel Coding 3.2.3 Metric-Mismatch Correction Metric-mismatch correction methods from Table 2.1 can be extended to the MLC case. In particular, metric scaling Λq′ Bi,Y,D̂i (y, d) = sqBi,Y,DiΛqBi,Y,D̂i (y, d) (3.15) can be applied to improve the GMI and throughput performance with sum- product SBS decoding in each layer, where sqBi,Y,Di is the critical point of IqBi,Y,Di (s). We would like to stress that the scaling factor sqBi,Y,Di in (3.15) is obtained without consideration of possible errors at lower layers. 3.3 Rateless Multilevel Coding Having discussed achievable rates and metric mismatch correction in MLC, we proceed by presenting our novel rateless MLC scheme. After the de- scription, we provide an operation analysis and develop a control technique to reduce the structural rate loss of rateless MLC when necessary. Our scheme is compatible with any mismatched metric, metric-mismatch correc- tion method, and decoding algorithm in the layers. Following Theorem 3.1 and for generality, we continue using the notations Ck, k = 0, . . . , κ − 1, and C = ∑κ−1 k=0 Ck to denote the maximum achievable rates of the layers (assuming there is no error from lower layers) and of MLC, respectively. We will resort to the GMI as an approximation for maximum achievable rates again when showing numerical results in Section 3.4. 67 3.3. Rateless Multilevel Coding 3.3.1 Encoding and Decoding In rateless BICM, the binary encoder takes in a fixed-length block of mes- sage bits and continuously produces coded bits, which are mapped to trans- mit symbols. The receiver can produce metric samples immediately after each received symbol. These metric samples are accumulated until they can provide enough information for successful decoding. At this point, the receiver acknowledges the transmitter and the transmitter switches to a new message block, cf. [13]. In this manner, rateless codes combine forward ECC with automatic repeat-request (ARQ), and hence realize a hybrid ARQ scheme [66]. We now consider a “naive” combination of rateless coding and MLC, in which the encoder-decoder pair at each layer (see Figure 3.3) is simply implemented in a rateless fashion. At layer 0, metric samples be- come available to the decoder immediately after each received symbol, as in rateless BICM. However, at any upper layer k > 0, the decoder collects sym- bol samples and waits for estimated data from lower layers to arrive. Only then, bit metrics can be calculated. The estimated data from lower layers does not become available immediately after each received symbol, but in large blocks. Thus, by the time this data is available and bit metrics are calculated, the collection of bit metrics at layer k may have already accumu- lated more information than necessary for successful decoding. This means that layer k is underutilized and the exceeding channel uses are wasted as rate loss. It is only at the lowest layer that we are able to collect just-enough information for successful decoding and avoid this underutilization. The above observation leads us to propose the following scheme. The 68 3.3. Rateless Multilevel Coding . . . (b) Receiver . . . (a) Transmitter . . . . . . Eκ−1 Eκ−2 E0 Dκ−2 x decoded dataBit Calculation y Metric MAP D0 Dκ−1 Figure 3.5: Rotation rateless MLC transmitter and receiver. Stream redi- rection occurs at switching to a new interval. transmitter employs κ binary rateless encoders Ek, k = 0, . . . , κ− 1. In the naive combination above, output from encoder Ek is always mapped to layer k. In our proposed scheme as illustrated in Figure 3.5(a), output from Ek is mapped to different layers at different time intervals. More specifically, Ek cyclically directs its output through layers (κ − 1), (κ − 2), . . . , 0 during κ time intervals t− (κ− 1), t− (κ− 2), . . . , t. Each time interval corresponds to the transmission of a number of symbols. The number of symbols in each 69 3.3. Rateless Multilevel Coding time (b) (a) layer 0 ... ℓ[t− 1] ℓ[t] ℓ[t− (κ− 2)] ... ... ... C1 C0Cκ−2 ℓ[t− (κ− 1)] Cκ−1 layer κ− 2 layer κ− 1 layer 1 Figure 3.6: (a) Information segments at the receiver. Segments with the same shading belong to the same codeword of a binary encoder-decoder pair. White segments are already decoded information. Segments may have different lengths. Among the κ binary decoders, during any time interval, only the one that is collecting information from layer 0 attempts to decode. (b) Each binary encoder-decoder pair experiences a time-varying channel with different interval maximum achievable rates Ci, i = 0, . . . , κ− 1. interval might vary from one interval to another, and is discussed in detail below. The corresponding receiver is shown in Figure 3.5(b). Each binary de- coder Dk, k = 0, . . . , κ − 1, collects information from all layers, starting from the highest layer κ− 1 and ending at the lowest layer 0. The decoders attempt to decode only when collecting information from layer 0. Thus, dur- ing any time interval, among the κ decoders, only the one decoder collecting information from layer 0 attempts to decode. Figure 3.6(a) shows the information segments at the receiver over κ time 70 3.3. Rateless Multilevel Coding intervals. Suppose some decoder Dk is collecting information from layer 0 during interval t. This decoder has also collected information segments from layers (κ − 1), . . . , 1 in the preceding (κ − 1) intervals. When Dk gathers that it might have accumulated enough information, it makes a decoding attempt. If decoding fails, Dk continues to collect information from layer 0, and attempts decoding again. Eventually, decoding will be successful, which marks the end of this time interval. The receiver then sends an acknowledgment to the transmitter. Upon receiving the acknowledgment, the transmitter: (i) changes the input of the corresponding encoder Ek to a new message block, and (ii) re-maps the encoded bit streams to different layers in the cyclical manner illustrated in Figure 3.5(a). That is, the stream that was mapped to layer k is now mapped to layer (k−1), for k = 1, . . . , κ− 1, and the stream that was mapped to layer 0 is now mapped to layer κ− 1. In the next time interval t + 1, the decoders will collect information from different layers, corresponding to this new streaming. From the viewpoint of a fixed encoder-decoder pair (Ek,Dk), the overall channel is segment- wise time varying. Each segment is associated with a different maximum achievable rate. This is illustrated in Figure 3.6(b). The proposed scheme requires an initialization. This can be seen in Figure 3.6(a), where white segments represent already decoded informa- tion. Therefore, at the start of the transmission session, the transmitter sends some preamble data that is known to the receiver in the correspond- ing segments. This preamble transmission appears only once and thus the associated rate loss will be negligible for sufficiently long sessions. 71 3.3. Rateless Multilevel Coding 3.3.2 Operation Analysis and Control As shown in Figure 3.6, let `[t] ≥ 0 be the number of transmit symbols during time interval t. While `[t] is an integer number, for simplicity we let `[t] assume real values in the following analysis; the effect of this relaxation becomes negligible for long codewords. By the end of time interval t, one codeword has been successfully decoded. We distinguish three variables related to the transmission of this codeword: K[t] is the number of bits in the message block taken by the encoder, θ[t] is the nominal amount of information collected by the receiver, i.e., θ[t] = κ−1∑ k=0 Ck`[t− k] , (3.16) and finally, ν[t] is the minimal amount of information sufficient for successful decoding. Since we assume successful decoding, we have ν[t] ≤ θ[t]. We call a binary rateless code ideal if ν[t] = K[t]. Practical codes, e.g. Raptor codes [13], require positive overheads and thus have a positive average (ν[t] −K[t]). We call this value the coding loss as it measures the required overhead of the code. The difference between θ[t] and ν[t] is due to the MLC structure. We therefore call the average of (θ[t] − ν[t]) the structural loss. The total rate loss of an MLC scheme, i.e., the gap between the average throughput and C, is the sum of its coding and structural loss. If successful decoding does not occur at the start of the interval when `[t] = 0, we can collect just enough additional information with `[t] > 0 and terminate decoding such that θ[t] = ν[t]. That is, no structural loss occurs. However, if successful decoding is possible at `[t] = 0, we have likely 72 3.3. Rateless Multilevel Coding accumulated more than enough information and wasted channel resources. Therefore, if `[t] varies around an equilibrium length and `[t] > 0, we assume that the transmission has no structural loss. In the following we will elabo- rate on this equilibrium length and the conditions under which the system is stable, that is, when `[t] automatically converges to and remains around the equilibrium length. Equilibrium Length For simplicity, we assume that K[t] = K, which means that all encoders always take in message blocks of the same length. This also means that all the κ binary encoder-decoder pairs can use the same binary rateless code. Let n[t] be a vector of (κ − 1) non-negative previous transmission lengths that represents the receiver state at the beginning of interval t, n[t] = ( `[t− (κ− 1)] . . . `[t− 1] )T . In systems with no structural loss, we have θ[t] = ν[t]. From (3.16), for t ≥ tinitial = 0, the state evolves according to the linear time-invariant state- space equation n[t+ 1] = An[t] + bν[t] , (3.17) with A =  0 1 . . . 0 ... ... ... ... 0 0 . . . 1 −Cκ−1C0 − Cκ−2 C0 . . . −C1C0  and b =  0 ... 0 1 C0  . 73 3.3. Rateless Multilevel Coding Let ν̄ be the mean value of ν[t]. We call the solution of the equation n[t+ 1] = An[t] + bν̄ , (3.18) the equilibrium point. This equilibrium point is found as ne = ν̄(Iκ−1 −A)−1b = `e1(κ−1)×1 , (3.19) where `e is the equilibrium length `e = ν̄∑κ−1 i=0 Ci = ν̄ C , (3.20) and 1(κ−1)×1 and Iκ−1 is the all-one column vector of length κ− 1 and the identity matrix of size (κ− 1)× (κ− 1), respectively. We observe that: • If ν[t] is a constant, i.e. ν[t] = ν̄, once at the equilibrium point, the system stays there. • With ideal codes, i.e. ν[t] = K, once at the equilibrium point, the system stays there and suffers zero total loss. Thus, with ideal codes, we can achieve a throughput equal to C. Stable Systems The system is stable if the eigenvalues of the matrix A in (3.17) lie inside the unit circle in the complex plane. In this case, the state n[t] will automatically hover around the equilibrium point ne. Then, the interval length `[t] stays close to `e and is positive, so that θ[t] = ν[t] holds and the transmission has 74 3.3. Rateless Multilevel Coding zero structural rate loss. For stable systems, the only loss with respect to C is the coding loss and our proposed MLC scheme is a rate-optimal way of combining binary rateless codes and multilevel constellations. The eigenvalues of A are the roots ri of the polynomial U(z) = 1 + C1 C0 z−1 + C2 C0 z−2 + . . .+ Cκ−1 C0 zκ−1 . (3.21) There are several methods to determine whether |ri| < 1 for all roots of (3.21) [67, Ch. 4.5]. For the special cases of κ = 2 and κ = 3 layers, we can make the criteria for stability explicit: • κ = 2: U(z) = 1 + C1C0 z−1, and the root r1 = −C1/C0 lies inside the unit circle if and only if C0 > C1. In other words, a two-layer scheme is stable if the lower layer has larger maximum achievable rate than the upper layer. • κ = 3: U(z) = 1+ C1C0 z−1+ C2C0 z−2, and the two roots r1,2 = 12C0 (−C1±√ C21 − 4C0C2) lie inside the unit circle if and only if (C0 > C2 and C0 + C2 > C1). Unstable Systems If the linear system (3.17) is unstable, the interval length `[t] would oscillate with increasing amplitude. Due to the constraint `[t] ≥ 0, the length `[t] will eventually swing between zero and some extreme values. This behavior is illustrated in Figure 3.7 for the example of κ = 3, C0 = 1, C1 = 1.7, C2 = 1.3, and thus C = 4 bit per channel use (bpcu), ν[t] = K for all t (the 75 3.3. Rateless Multilevel Coding 0 10 20 30 40 50 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 t→ ℓ[ t] /K → Figure 3.7: Interval length `[t] of an unstable system. binary code is ideal), and the initial state n[0] = (K/C)[1.0 1.2]T . At large values of t, the system settles into the following pattern: there is one long interval of length K, followed by two intervals of length zero. In the long interval, one codeword is decoded with all samples from layer 0. In the next interval, one codeword is decoded with all samples from layer 1 and no more samples from layer 0 are needed (hence, the interval length is 0). Similarly, the next codeword is decoded with all samples from layer 2. Even though the rateless code is ideal, the system achieves a data rate of only 3 bpcu, which is well below C. This behavior calls for a control mechanism to minimize the structural loss for unstable systems. 76 3.3. Rateless Multilevel Coding Control for Unstable Systems The receiver can delay sending the acknowledgment to the transmitter after successful decoding. By controlling this delay, we can reduce the structural loss. To illustrate the potential of such a control, we consider a scenario where we can predict the values of ν[t] in a near future. Suppose that at the beginning of time interval τ , the receiver state is n[τ ], and we predict the values of ν[t] over the finite time horizon T to be ν[τ ], . . . , ν[τ + T − 1]. Beyond this horizon, we extrapolate that ν[t] equals to the average of the predicted values ν̄[τ ], given by ν̄[τ ] = 1 T τ+T−1∑ t=τ ν[t] . (3.22) We observe from Eqns. (3.17) to (3.20) that, if ν[t] remains constant as ν[t] = ν̄[τ ] for t ≥ τ +T , the transmission suffers no structural loss if all the segment lengths equal ν̄[τ ]/C. Therefore, we want to settle into the state `[t] = ν̄[τ ]/C for t ≥ τ + T . We end up having an extended control period from τ to τ + T + κ− 2 with the desired ending state `[τ + T ] = . . . = `[τ + T + κ− 2] = ν̄[τ ] C . (3.23) For the period [τ, τ + T − 1], we plan the lengths `[τ ], . . . , `[τ + T − 1] to minimize the structural loss. The initial amount of information stored at the receiver at the beginning of time interval t = τ (the initial information 77 3.3. Rateless Multilevel Coding inventory) is Ibeginning = κ−1∑ k=1 κ−1∑ j=k Cj`[τ − k] . (3.24) The ending information inventory at the end of time interval τ + T + κ− 2 (or beginning of the time interval t = τ + T + κ− 1), is Iend = κ−1∑ k=1 κ−1∑ j=k Cj ν̄[τ ] C . (3.25) During the control period, the total amount of arriving information is C ∑τ+T+κ−2 t=τ `[t], and we spend ∑τ+T+κ−2 t=τ ν[t] to successfully decode T + κ− 1 codewords. The structural loss is therefore Istructural loss = C τ+T+κ−2∑ t=τ `[t]− τ+T+κ−2∑ t=τ ν[t] + Ibeginning − Iend . (3.26) Since the beginning and ending receiver state are fixed, the structural loss is minimized if ∑τ+T−1 t=τ `[t] is minimized. Planning the segment lengths can then be stated as the following linear programming (LP) problem: {ˆ̀[τ ] . . . ˆ̀[τ + T − 1]} = argmin τ+T−1∑ t=τ `[t] subject to:∑κ−1 k=0 Ck`[t− k] ≥ ν[t], ∀ t ∈ [τ, τ + T + κ− 2],( `[τ − (κ− 1)] . . . `[τ − 1] )T = n[τ ], `[τ + T ] = . . . = `[τ + T + κ− 1] = ν̄[τ ]/C, `[t] ≥ 0 . (3.27) As the transmission progresses, we apply the model predictive control 78 3.3. Rateless Multilevel Coding // Model predictive control 1: At the beginning of time interval t = τ , predict ν[τ ], . . . , ν[τ + T − 1]. 2: Plan the segment lengths for the period [τ, τ + T − 1] by solving (3.27). 3: Receive at least ˆ̀[τ ] symbols in this time interval. 4: Repeat for t← τ + 1. Figure 3.8: Model predictive control technique. (MPC) technique, e.g. [68], to adjust to the increment of t. This technique can also be effective in compensating for imperfect prediction of future values of ν[t]. The MPC technique is summarized as in Figure 3.8. An alternative control rule to the MPC technique above is to always receive at least `min symbols in each interval. We call this the minimal seg- ment length (MSL) control rule. This simple rule comes from observing the behavior of unstable systems without control, as described in Section 3.3.2. Since the decoders have to wait for their turn, the one that collects most of the information from a low-rate layer needs a relatively long interval and forces other decoders to accumulate too much information. By setting a proper minimum value for all `[t], MSL reduces the long wait by making the total amount of information to be distributed more equally over the κ intervals. Example 3.2. We now illustrate the effectiveness of the control techniques via a hypothetical example. Let ν[t] be a random process such that ν[t] = (1.05 + [t])K. The component [t] is Rayleigh-distributed with mean 0.04. Therefore, ν̄/K = 1.09 and thus the coding loss is 9%. This model ap- proximates the simulation result of a Raptor code from [69, Fig. 6]. We 79 3.3. Rateless Multilevel Coding 0.96 0.98 1 1.02 1.04 1.06 1.08 1.1 1.12 1.14 0.01 0.02 0.03 0.04 0 2 4 6 8 10 12 14 16 18 20 0 0.01 0.02 0.03 S tr u ct u ra l lo ss θ̄ − ν̄ K → S tr u ct u ra l lo ss θ̄ − ν̄ K → ×K C ℓmin → T → Figure 3.9: Controlling structural loss in an unstable system with maximum achievable rates [C0 C1 C2] = [1.0 1.7 1.3] bpcu. Top: structural loss vs. T for model predictive control (MPC) with perfect prediction. Bottom: structural loss vs. `min for minimum segment length (MSL) control. consider the same MLC example as in Section 3.3.2. That is, κ = 3, C0 = 1, C1 = 1.7, and C2 = 1.3 bpcu. Without control, the transmission suffers a structural loss of 36%. For MPC with perfect prediction, the structural loss versus T is plotted in the upper half of Figure 3.9. It is interesting to observe that even with short T = 1, MPC reduces the structural loss to just about 2%. With long horizon T , it can almost completely eliminate the structural loss. Thus, controlling the acknowledgment delay can indeed re- duce the structural loss. Unfortunately, perfect prediction of ν[t] over a long horizon is rather idealistic. With the simple and practical MSL control rule, 80 3.4. Applications the structural loss versus `min is plotted in the lower half of Figure 3.9. The result shows that MLC can reduce the structural loss to a very small value of less than 2%. This value is much less than the coding loss. These results suggest that MSL control is indeed a practical way of stabilizing rateless MLC systems, and we apply it in the application examples below. 3.4 Applications In this section, we demonstrate the efficacy of our rateless MLC scheme in a number of transmission scenarios. The application examples include MIMO and orthogonal modulation transmission in stationary or slow fading chan- nels, and using matched or approximate metrics. Following Section 3.2.2, we use the GMI as an approximation to the maximum achievable rates of the layers. We use the same Raptor code as in Example 2.1 with K = 9500 and sum-product SBS decoding. When a decoding attempt fails, an additional information amount of 0.01K is collected before the next attempt. 3.4.1 MIMO-QAM Consider MIMO transmission with Nt transmit and Nr receive antennas. Each transmit antenna emits symbols from a constituent quadrature ampli- tude modulation (QAM) constellation A of size MA. Each symbol of the MIMO constellation X is thus a vector of Nt elements x = [x0 . . . xNt−1]T , where each element xi ∈ A is a complex number. The size of the multidi- mensional transmit constellation is M = (MA)Nt . Assuming a flat fading channel with the matrix of complex gains H and complex additive white 81 3.4. Applications Gaussian noise (AWGN) vector n with variance N0 per element, the re- ceived symbol is given by y = Hx+ n . (3.28) The channel transition probability follows as pY |X(y|x) ∝ exp ( −|y −Hx| 2 N0 ) . (3.29) It was shown in [17, Sec. IV-E] that there exists a significant gap between the BICM GMI and the constellation-constrained channel capacity I(X;Y ), even when Gray mappings are applied for the constituent constellation A, and hence for X . Thus, it is appealing to use MLC with MIMO signaling. Let us consider the case of 4-QAM with Nt = 4 transmit antennas and matched decoding metric (3.13). The size of the constellation is M = 256 and the number of labeling bits is m = 8. We use MLC with κ = 2 layers. The first four bits are grouped into layer 0, and the other four bits are grouped into layer 1. We consider an i.i.d. Rayleigh fading channel and two scenarios of Nr = 2 and Nr = 4 receive antennas. For both scenarios, the GMI of layer 0 is less than that of layer 1, and therefore the system is unstable. We apply the MSL control with `min = 1.06K/C. The signal-to- noise ratio (SNR) is defined as Er/N0, where Er is the average received power at each antenna, cf. [17]. The simulation results are plotted in Figure 3.10. It can be observed that MLC with just two layers can considerably reduce the gap between BICM GMI and the average mutual information I(X;Y ). Over the whole SNR range, the simulated throughput is about 92% of the MLC GMI. This ratio is close to the reported value in [69] for a Raptor 82 3.4. Applications 0 2 4 6 8 10 12 14 16 18 20 1 2 3 4 5 6 7 8 I(X;Y) GMI, BICM GMI, 2−layer MLC Throughput, BICM Throughput, 2−layer MLC 4-QAM 4-Tx R at e [b p cu ] → 4-Rx 2-Rx 10 log10Er/N0 [dB] → Figure 3.10: GMI and throughput of rateless MLC for 4-QAM MIMO trans- mission with 4 transmit and 2 and 4 receive antennas over an i.i.d. Rayleigh fading channel. code over a binary AWGN channel. Therefore, we conclude that most of the rate loss is the coding loss, and the structural loss is small. Overall, the results demonstrate a significant throughput gain from using our rateless MLC scheme instead of BICM. 3.4.2 Noncoherent Carrier-Modulated Orthogonal Signaling In orthogonal modulation, the Euclidean distances between signal points are the same. Hence, for constellations with size M > 2, Gray mappings 83 3.4. Applications 6 8 10 12 14 16 18 20 0 1 2 3 4 5 6 7 I(X;Y) GMI, BICM GMI, 2−layer MLC GMI, layer 0 GMI, layer 1 Throughput, BICM Throughput, w/o control Throughput, w/ control 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 I(X;Y) GMI, BICM GMI, 2−layer MLC GMI, layer 0 GMI, layer 1 Throughput, BICM Throughput, w/o control Throughput, w/ control (b) i.i.d. Rayleigh fading channel (a) AWGN channel R a te [b p cu ] → 10 log 10 Er/N0 [dB] → 10 log 10 Er/N0 [dB] → R a te [b p cu ] → Figure 3.11: GMI and throughput of rateless MLC for M = 128 noncoherent orthogonal modulation. Label “w/o control” and “w/ control” are for the rotational scheme without and with MSL control, respectively. 84 3.4. Applications do not exist. We apply rateless MLC to carrier-modulated orthogonal sig- naling with noncoherent detection. The channel model is described in Sec- tion 2.4.2. Let us consider a system with m = 7 levels [70], κ = 2 layers and h = [0 0 0 0 1 1 1]. Similarly to the MIMO-QAM application above, the SNR is defined as Er/N0, and for this modulation Er = E{a2}. The layer GMIs are plotted in Figure 3.11(a) for the case of an AWGN channel and in Figure 3.11(b) for the case of an i.i.d. Rayleigh fading channel. Depending on the SNR, the GMI of layer 0 can be smaller or larger than that of layer 1. Therefore, the MLC system can be unstable or stable, respectively. We re- call that when the system is stable, no control is needed and no structural loss results. For all SNR values, we apply our rateless scheme (i) without control and (ii) with MSL using `min = 1.06K/C. As expected, Figure 3.11 shows that when the system is unstable, MSL improves the throughput. Furthermore, when the system is stable, MSL practically does not incur structural loss, achieving the same throughput as the case without control. This suggests that we can safely apply MSL control to the whole range of SNR values. Rateless transmission is most beneficial in slow-fading channel environ- ments. Thus, we now illustrate the performance of our scheme in a slow fading example. To this end, we assume the complex channel gain g = a ejφ evolves from one symbol to the next according to the first-order autoregres- sive (AR1) model gi = αgi−1 + √ 1− α2wi , (3.30) where wi is an i.i.d. zero mean complex Gaussian process with variance 85 3.4. Applications Er. The parameter 0 ≤ α ≤ 1 determines the rate of fading. The extreme values α = 1 and α = 0 turn (3.30) into an AWGN channel and an i.i.d. Rayleigh fading channel, respectively. In slow fading cases, we modify the MSL control to: always receive at least an amount of information Imin in each segment. Corresponding to N0 and the magnitude of the instantaneous channel gain, the instantaneous GMI can be obtained from the GMI plots in Figure 3.11(a). Let C[t] be the MLC GMI averaged over time interval t. We use the value R[t] = C[t]K/θ[t] as an indication of the throughput in interval t. We recall that θ[t] (3.16) is the total amount of information associated with the codeword that has just been decoded in this interval. The ratio K/θ[t] is the relative throughput efficiency of the codeword. As an interesting example, we consider 10 log10(Er/N0) = 8 dB and α = 0.999 such that C[t] would change significantly across intervals. We use MSL control with Imin = 1.06K. Samples of average MLC GMI and R[t] obtained from a simulation are plotted in Figure 3.12. For comparison, the BICM GMI of the same channel realizations, averaged over the same segment boundaries, is also included. We observe that the throughput of our scheme closely follows the associated MLC GMI. Furthermore, R[t] exceeds the BICM GMI for the majority of the times. Averaging over the whole 70 sample intervals illustrated in Figure 3.12, the MLC GMI is 3.03 bpcu, R[t] is 2.70 bpcu, and the BICM GMI is 2.48 bpcu. That is, our scheme attains a throughput gain in slow fading channels as well. 86 3.4. Applications 10 20 30 40 50 60 70 0 1 2 3 4 5 6 7 Average MLC GMI Average BICM GMI R[t] t→ R a te [b p cu ] → Figure 3.12: Example of 2-layer rateless MLC over slow fading channel. The value R[t] approximates the average throughput during time interval t. 3.4.3 Pulse-Position Modulation with Direct Detection We continue with the PPM transmission in Example 3.1. Consider 128-PPM with 2-layer MLC such that h = [0 0 0 0 1 1 1]. Simulation results with the matched metric (3.14) demonstrate the same trends as in the case of noncoherent orthogonal modulation above, and therefore are not presented here. We now consider the popular max-log approximate LLR metric, which is ΛqBi,Y,Di (y, d) =  max x∈X d,0di,i ye(x)− max x∈X d,1di,i ye(x)  ln(1 + λs λb ) . (3.31) 87 3.4. Applications 0.55 0.75 1 1.5 1 1.2 1.4 1.6 1.8 2 Matched Max−log Scaled max−log layer 0 layer 1 s→ R at e [b p cu ] → Figure 3.13: Layer I-curves of the 128-PPM MLC scheme with λb = 0.2 photons/slot and 10 log10(λs/(Mλb)) = −10.5 dB and different metrics. Each doubled-arrowed arc connects the peak of an I-curve with a marker that represents the associated throughput with an off-the-shelf Raptor code. This max-log LLR requires less computation than the matched metric (3.14). We consider a mid-range SNR of 10 log10(λs/(Mλb)) = −10.5 dB, at which the 2-layer MLC scheme with matched metric attains a GMI of 3.5 bpcu. Figure 3.13 shows the I-curves (3.10) of the two layers with matched and max-log metrics. We recall that the I-curve of layer 0 is equal to four times the binary I-curve of any level in layer 0. Similarly, the I- curve of layer 1 is equal to three times the binary I-curve of any level in that layer. From Figure 3.13, we see that the max-log metric incurs only a small reduction in the GMI. The critical point (the s-coordinate of the 88 3.4. Applications peak) of the I-curve of layer 0 is 0.55 and that of layer 1 is 0.75. As the critical point of the I-curve is not equal to 1, the throughput achieved by sum-product SBS decoding can be considerably lower than the GMI, see Section 2.3.2. We illustrate this phenomenon via a simulation in which the Raptor decoder is fed with LLR samples from layer 0 or layer 1 alone. In the detection at layer 1, we use transmitted data from layer 0 instead of the estimated data. The resulting throughputs are presented as bold markers in Figure 3.13. The phenomenon is especially pronounced at layer 0: while the throughput with metric (3.13) is about 93% of the corresponding GMI, this ratio reduces to only 80% with metric (3.31). The most simple correction to reduce this gap is to scale the mismatched LLR with a factor equal to the critical point of the I-curve, following (3.15). That is, we multiply the max-log LLR at layer 0 with 0.55 and at layer 1 with 0.75. This scaling shifts the critical point to 1 without changes in the GMI. We stress again that the scaling factor for layer 1 is obtained without considering errors in layer 0. The scaled max-log metric results in an improved throughput, as shown in Figure 3.13. Finally, using the scaled max-log metric in our rota- tional rateless scheme with appropriate `min, we obtain a throughput of 3.1 bpcu. In comparison, a simulation of matched BICM with the same Raptor code results in a throughput of 2.5 bpcu. Thus, scaled max-log MLC attains a throughput gain of more than 20% compared to matched BICM. 89 3.5. Conclusion 3.5 Conclusion In this chapter we considered three practical issues of MLC. Our first contri- bution is the development of reduced-layer MLC which can favorably trade the achievable rate for MLC structural complexity reduction. Our second contribution involves rate analysis and metric mismatch correction for MLC with approximate metrics. We use the GMI as an approximation to the maximum achievable rate of the layer, which can be estimated separately and with the assumption that there is no error in the decoding at lower layers. Our last contribution is the proposal of a novel rateless MLC scheme with no or negligible structural rate loss. We provide extensive numerical examples with MIMO, noncoherent carrier-modulated orthogonal signaling, and IM-DD PPM in stationary or slow-fading scenario, using matched or max-log metric, which show that our scheme can attain throughput gains compared to rateless BICM. 90 Chapter 4 Applications in Free-Space Optics FSO has recently emerged as a cost-effective solution for a wide range of communication applications [7]. It possesses a multi-Gigabits-per-second capacity, is highly secure, rapidly deployable, and re-installable. We have considered coded PPM for FSO in Section 2.4.3, Example 3.1, and Sec- tion 3.4.3. In this chapter, we continue with several advanced signaling schemes and apply coding techniques from the previous chapters to improve FSO’s rate and reliability. 4.1 Rateless Hybrid FSO-RF for Last-Mile Access While the telecommunications backbone infrastructure has been remark- ably improved over the past decade, bridging its enormous capacity to end- users remains a difficult challenge. Existing copper wires and wireless LAN technologies cannot handle the data rate necessary to deliver modern high- definition multimedia in real time, whereas coaxial cables and fiber optics 91 4.1. Rateless Hybrid FSO-RF for Last-Mile Access mapper 2 mapper 1 channel 2 channel 1 detector 1 detector 2 E transmitter D receiver Figure 4.1: Channel coding diversity scheme. are often too inconvenient and expensive to deploy at end-users’ premises. FSO has been anticipated to be a low-cost solution to this “last-mile chal- lenge.” However, last-mile FSO has one major drawback: adverse weather can dramatically reduce the signal strength and make the communication unreliable [71,72]. One of the most promising solutions to tackle this reliabil- ity issue is to use an RF link in conjunction with the FSO link, e.g. [73–77]. The rationale for FSO-RF conjunction is that fog and rain, which can dra- matically reduce FSO and RF link quality respectively, rarely occur at the same time. In light of results from Chapter 2, in this section we revisit the rateless hybrid FSO-RF scheme from [14] and present rate analysis for the case of general decoding metrics. 4.1.1 Channel Coding Diversity Model and Rate Analysis The hybrid FSO-RF scheme from [14] is an instance of channel coding di- versity [15]. The block diagram of a channel coding diversity scheme is presented in Figure 4.1. The diversity channel consists of two individual channels 1 and 2. There is a single encoder E which controls both of the mappers to produce transmit symbols for the individual channels. Cor- 92 4.1. Rateless Hybrid FSO-RF for Last-Mile Access respondingly, there is a single decoder D which makes decoding decisions based on symbol metrics from the two detectors. We consider indepen- dent discrete-time memoryless individual channels with input and output random variables Xi ∈ Xi and Yi ∈ Yi, and channel transition probability functions pYi|Xi(yi|xi), i = {1, 2}. The detectors produce symbol metrics qXi,Yi(xi, yi) > 0 for all transmit symbols xi ∈ Xi and received symbols yi ∈ Yi. Following Section 2.1, we consider codebooks of M codewords x = [x1 x2]. Component xi is a length-Ni sub-codeword whose elements are to be transmitted via channel i. Let N = N1 +N2 and ηi = Ni/N . As in Section 2.1, the word error probability, averaged over all codewords and random codebook realizations, is upper bounded as P ≤Mρ 2∏ i=1 EXi,Yi  ∑ xi∈Xi pXi(xi) [ qXi,Yi(xi, Yi) qXi,Yi(Xi, Yi) ]sρ Ni . (4.1) In parallel with (2.4), (2.5), and (2.6), the above equation can be written as P ≤ 2−NEr(R), (4.2) with R , logM N , (4.3) the random coding exponent Er(R) , max 0≤ρ≤1 max s>0 ( E0(ρ, s)− ρR) , (4.4) 93 4.1. Rateless Hybrid FSO-RF for Last-Mile Access and the generalized Gallager function of the diversity channel E0(ρ, s) , η1E0qX1,Y1 (ρ, s) + η2E 0 qX2,Y2 . (4.5) In (4.5), E0qXi,Yi (ρ, s), i = {1, 2} is the generalized Gallager function of the individual component channel i defined by (2.6). Similarly to (2.7) and (2.8), the GMI and I-curve of the diversity channel are Igmi , max s>0 I(s) , (4.6) and I(s) = η1IqX1,Y1 (s) + η2IqX2,Y2 (s) . (4.7) Again, IqXi,Yi (s) is the I-curve of the individual channel defined by (2.8). Let ri be the baud rate 4 of channel i, we can also define the I-curve of the diversity channel as I(s) = r1IqX1,Y1 (s) + r2IqX2,Y2 (s) . (4.8) The GMI (4.6) is now measured in bits per time unit. Let IgmiqXi,Yi be the individual GMI of channel i. Interestingly, from (4.6) 4Or symbol rate, which is the inverse of the symbol period. 94 4.1. Rateless Hybrid FSO-RF for Last-Mile Access FSO RF mapper mapper FSO RF channel channel FSO RF detector detector d em u lt ip le x er E bits message D m u lt ip le x er receivertransmitter Figure 4.2: Rateless BICM hybrid FSO-RF communication system. and (4.8), it follows that Igmi = max s>0 ( r1IqX1,Y1 (s) + r2IqX2,Y2 (s) ) ≤ r1 max s>0 IqX1,Y1 (s) + r2 maxs>0 IqX2,Y2 (s) = r1I gmi qX1,Y1 + r2I gmi qX2,Y2 . That is, the GMI of the diversity channel is less than or equal to the baud- rate weighted sum of the individual channels’ GMIs. Equality Igmi = r1I gmi qX1,Y1 + r2I gmi qX2,Y2 . (4.9) holds if and only if the individual I-curves are harmonic, see Theorem 2.1. In BICM with channel coding diversity as the hybrid scheme in [14] and presented in Figure 4.2, each I-curve IqXi,Yi (s), i = {1, 2}, is in turn equal to the sum of the binary I-curves in that channel. Furthermore, we can apply metric manipulation methods from Section 2.3 to increase the individual channel’s or the diversity channel’s BICM GMI. 95 4.1. Rateless Hybrid FSO-RF for Last-Mile Access 4.1.2 Numerical Examples The BICM hybrid FSO-RF scheme from [14] uses rateless codes, which can seamlessly and simultaneously utilize each of the links’ resources. 40 60 80 100 120 140 160 40 60 80 100 120 140 160 T h ro u gh p u t [M b p s] → GMI [Mbps] → Figure 4.3: Scatter plot of throughput vs. GMI for 1000 codewords over the hybrid (diversity) FSO-RF scheme. In the first numerical example, we consider the same scenario as in [14] with matched metrics. Thus, all binary I-curves are aligned at s = 1 and equality (4.9) holds. The FSO link uses on-off keying (OOK) with symbol period of 10 ns. The photo-counting model (2.47) applies with background radiation λb = 39 photons/slot. We assume a moderate transmitter-receiver distance of 1000 m, wind speed of 5 m/s and a relatively strong turbulence scintillation condition as described in [14, Sec. IV]. In this scenario, the FSO 96 4.1. Rateless Hybrid FSO-RF for Last-Mile Access 0 50 100 150 200 40 60 80 100 120 140 160 GMI Througput R at e [M b p s] → Codeword index → Figure 4.4: Throughput and GMI during the transmission of 200 consecutive codewords over the hybrid FSO-RF scheme. transmission experiences a slow fading condition and the value of the GMI IgmiFSO varies from 0 to 1 bpcu. In particular, the FSO channel gain changes from one symbol to the next, but the two values are almost the same, cf. Figure 4.4 and the explanation below. The RF modulator produces 64-QAM with symbol period of 60 ns. The RF channel is i.i.d. Rayleigh fading and has an average SNR such that the GMI IgmiRF is 3.0 bpcu. The hybrid, or diversity, GMI is therefore in the range of 50 Mbps (when the FSO link is completely “blacked out”) to 150 Mbps (when the FSO link achieves its maximum rate). We use the same Raptor code from Example 2.1 for coded transmission. Figure 4.3 shows the scatter plot of throughput vs. the GMI 97 4.1. Rateless Hybrid FSO-RF for Last-Mile Access for 1000 codewords. It shows that the rateless code consistently achieves a throughput close to the GMI. The ability of the rateless code to seamlessly adapt to the channel quality is further illustrated by the plot of throughput and GMI during the transmission of 200 consecutive codewords in Figure 4.4. This numerical evidence shows that rateless coding is suitable for last-mile hybrid FSO-RF communications. In the second numerical example, we demonstrate the use of approximate metrics. The RF link has the same modulation and symbol period as above, except now we use the max-log LLR metric and adjust the SNR so that the GMI of the RF link is 2.0 bpcu. The FSO link now uses 64-PPM with a baud rate equal to 1.5 times the baud rate of the RF link. The photo-counting model (2.47) applies with λb = 2.44 photons/slot. This new value of λb reflects the changes in the FSO modulation format and baud rate compared to the previous example. We consider the max-log metric (2.51) with SNR such that the GMI of the FSO link is also 2.0 bpcu. The BICM I-curves of the individual channels are shown in Figure 4.5. We see that they attain their peaks at different values of s (s = 0.675 for the FSO I-curve IFSO(s) and s = 1.225 for the RF I-curve IRF(s)). The I-curve of the diversity channel is (with the diversity channel GMI (4.6) measured in bits per TRF) I(s) = 1.5IFSO(s) + IRF(s) , (4.10) and is plotted in Figure 4.6. This I-curve peaks at s = 0.775 and attains a GMI of 4.86 bits/TRF. Now, if we scale all the FSO LLR values by 0.675 and all the RF LLR values by 1.225, the FSO and RF I-curves will attains their 98 4.2. Multipulse Pulse-Position Modulation peak at the same critical point s = 1. The resulting I-curve of the diversity channel Iscaled(s) is plotted in Figure 4.6 with a GMI of 5.0 bits/TRF. That is, equality (4.9) holds. Below each I-curve in Figure 4.6, we plot a marker which represents the throughput by the Raptor code from Example 2.1. The transmission with max-log metrics attains a throughput of 4.37 bits/TRF whereas the transmission with scaled max-log metrics attains a significantly higher throughput of 4.62 bits/TRF. We perform a further simulation where all the FSO and RF LLR values is scaled by 0.775. This scaling shifts the peak of the I-curve of the diversity channel to s = 1, but leaves the GMI remains at 4.86 bits/TRF. Now, the transmission attains a throughput of 4.49 bits/TRF, which is still lower than the case where both the individual I-curves achieve their peaks at the same s = 1. Thus, our GMI analysis indeed reflects the performance of actual coded transmission. 4.2 Multipulse Pulse-Position Modulation In this section we consider multipulse pulse-position modulation (MPPM) as a power- and bandwidth-efficient format for FSO. This modulation can be used in hybrid systems as in Section 4.1 or in stand-alone FSO applications. Currently, the most common format for FSO are OOK and PPM [61, 62,78,79]. OOK achieves higher bandwidth efficiency, but it has low power efficiency. In addition, its possible long sequences of on and off slots are not favorable to synchronization. On the other hand, PPM has higher power efficiency but lower bandwidth efficiency. MPPM has been proposed as a well-suited format for intensity modulation [16] with a balanced trade-off be- 99 4.2. Multipulse Pulse-Position Modulation 0.5 0.675 1 1.225 1.5 1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 s→ R at e [b p cu ] → IFSO(s) IRF(s) Figure 4.5: BICM I-curve of individual FSO and RF channels. tween power and bandwidth efficiencies. Its regulated pulsed and non-pulsed slots is also friendly to synchronization. In this section, we investigate the combination of ECC with MPPM to realize power- and bandwidth-efficient FSO transmission. In particular, we are interested in the application of bi- nary ECC schemes for which a large number of powerful codes have been developed. One difficulty with this approach is that the sizes of w-pulse n-slot MPPM constellations are ( n w ) , which are not powers of 2. Thus, bit-to-symbol mapping can be complicated. A common-sense solution is decimating the constellations to the nearest power-of-2 sizes. Since this in turn reduces bandwidth efficiency, (at least) two questions immediately arise. First, under what circumstances would MPPM indeed offer notable 100 4.2. Multipulse Pulse-Position Modulation 0.5 0.775 1 1.25 1.5 4.2 4.4 4.6 4.8 5 5.2 s→ R at e [b it s/ T R F ] → I(s) Iscaled(s) Figure 4.6: BICM I-curve and coded throughput of hybrid (diversity) chan- nel. throughput or power efficiency gains over the popular alternative PPM for- mat? Second, how can those gains be realized by practical ECC schemes? To address the first question, MPPM and PPM have been compared based on different criteria and under various transmission conditions, cf. e.g. [16,62,80–85]. It has been shown that although MPPM can potentially be two times more bandwidth efficient than PPM with the same power ef- ficiency [16], considerable throughput gains are only present for high signal power and duty cycle w/n [62, 80]. In terms of error-rate performance, it was recognized that no PPM or MPPM constellation is universally superior to all the others, and that different modulation formats are preferable under 101 4.2. Multipulse Pulse-Position Modulation different transmission constraints, such as peak- or average-power or band- width constraints [83]. Hence, before designing specific ECC schemes for MPPM, a careful selection of appropriate MPPM constellations is needed. As for the second question, we note that several coding schemes have been studied for MPPM. Analytical results for Reed-Solomon coded MPPM were given in [80–82, 86]. Sato et al. [82] also analyzed the performance of convolutional coded 2-pulse MPPM and investigated the effect of imperfect slot synchronization on the error rate performance. The combination of trellis-coded modulation (TCM) with 2-pulse MPPM was outlined in [83]. A more detailed description of TCM with 2-pulse MPPM, including asymptotic coding gain calculation, was given in [87]. Serially concatenated TCM was also considered for 2-level 2-pulse MPPM (each of the two pulses can take two values) in [88]. It should be noted that none of these ECC schemes is capacity-approaching. Hence a significant performance gain is left to be realized. Furthermore, most authors have considered only 2-pulse MPPM, probably for ease of analysis. In the following, we revisit both of the above questions concerning the application of coded MPPM. Firstly, we compare MPPM with PPM in terms of achievable data rate under simultaneous peak power, average power, and bandwidth constraints. A similar comparison has been performed by Hamkins and Moision [62]. However, they considered full-sized MPPM con- stellations and mostly focused on low duty-cycle modulations for deep-space communication, where MPPM’s throughput gains are very limited. Our comparison here focuses on high duty-cycle and thus bandwidth-efficient MPPM with decimated constellations suitable for coded transmission. Sec- 102 4.2. Multipulse Pulse-Position Modulation ondly, we investigate the application of binary ECC to MPPM using such decimated constellations. In particular, we design BICM and MLC schemes for MPPM. We find that BICM is only an appropriate ECC scheme for MPPM at relatively high SNR, whereas MLC can attain a significantly higher throughput at lower SNR values. 4.2.1 Constellation Selection Each (n,w)-MPPM symbol is represented by a vector x = [x1 . . . xn] of n elements, each of which is transmitted in one slot, and 1 < w ≤ bn/2c elements of 1 and the others are 0. We use the photo-counting model (2.47). The SNR is defined as γ = (w/n)λs/λb. The channel transition probability is p(y|x) ∝ ( 1 + λs λb ) . (4.11) The notation < y, x > denotes the inner product between y and x, which turns out to be the sum of the elements of y at the locations of the non-zero elements of x. We assume uniform input distribution. The constellation- constrained channel capacity is C(X ) = 1 n I(X;Y ) [bits/slot] . (4.12) The set U of all distinct (n,w)-MPPM symbols has size Mmax = ( n w ) = n! w!(n− w)! , (4.13) which is never a power of 2. Since constellations of sizes M = 2m, m ∈ Z, are 103 4.2. Multipulse Pulse-Position Modulation preferred for coded transmission, we will use only a decimated constellation X ⊂ U of M < Mmax distinct symbols. We now turn to the problem of selecting “good” MPPM constellations. Our approach consists of two steps. First, we determine parameters (n,w,M) such that MPPM transmission with a corresponding set X potentially offers throughput gains compared to PPM under the same transmission constraints. Then, we obtain the set X from decimation of the full-size MPPM set U such that C(X ) is maximized. We compare MPPM constellations based on the maximal throughput τ = log(M)/n bits/slot under simultaneous peak power, average power, and bandwidth constraints. Peak and average power constraints require identical duty cycles 1/ρ = w/n, where ρ is the peak-to-average power ratio (PAPR), and the bandwidth constraint is accounted for by measuring throughput in bits per slot. The “OOK bound” τ = H(1/ρ), where H(·) is the binary entropy function, upper bounds the MPPM throughput for given PAPR ρ [80]. Furthermore, an n-slot PPM constellation has ρ = n and τ = (log ρ)/ρ. Figure 4.7 shows the power-bandwidth efficiency chart for MPPM con- stellations with M ≤ 256 and τ ≥ (log ρ)/ρ. There are 89 triplets (n,w,M) satisfying these conditions. Each triplet (n,w,M) is presented as a point in the figure, and several (n,w,M) triplets may take the same point. In- cluded are the upper “OOK bound” τ = H(1/ρ) and the lower “PPM bound” τ = (log ρ)/ρ. With this figure, we are able to locate the param- eters (n,w,M) of MPPM constellations that offer both high power and bandwidth efficiencies. For example, if we want a transmission which re- quires ρ to be around 4.0 we could select one of the three constellations 104 4.2. Multipulse Pulse-Position Modulation 2 4 6 8 10 12 14 16 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 τ [b it s/ sl o t] −→ OOK bound τ = H(1/ρ) ρ −→ PPM bound τ = log(ρ)/ρ (12, 3, 128) (13 3, 256) (11, 3, 128) Figure 4.7: Power-bandwidth efficiency chart of MPPM. Parameter sets are triplets (n,w,M). where (n,w,M) equals (11, 3, 128) , (13, 3, 256), or (12, 3, 128), for which Mmax = ( n w ) = 165, 286, and 220, respectively. 4.2.2 Subset Selection Having determined the MPPM constellation parameters, we need to decide which M out of the Mmax symbols are to be used. Selection of subsets based on symbol-error rate or avoidance of long sequences of zeros and ones has been considered in [83, 86, 87]. As mentioned above, here we use the constellation-constrained channel capacity C(X ) as the relevant criterion. 105 4.2. Multipulse Pulse-Position Modulation Therefore, we formulate subset selection as a combinatorial optimization (CO) problem: Maximize: C(X ) subject to: X ⊂ U and |X | = M (4.14) Since the solution of this CO problem with the objective function C(X ) from (4.12) seems to require total enumeration, we aim at a possibly suboptimal solution using CO search algorithms. Search Algorithms We now briefly describe the three popular search algorithms, whose pseudo- code are presented in Figures 4.8, 4.9, and 4.10. All algorithms excecute N search iterations. Further details can be found in [89]. // Random search 1: Randomly select X 2: for i = 1 . . . N do 3: Randomly select X ′ 4: if (C(X ′) > C(X )) then 5: X = X ′ 6: end if 7: end for 8: Return X Figure 4.8: Pseudo-code for random search. Random search: In each iteration, a new trial solution is generated by randomly picking M elements of U . The result is the best of all trials. Greedy ascent: The search starts with a random initial solution. In each iteration, greedy ascent tries to replace only one MPPM symbol in the solution by another one that would improve the quality of the solution. 106 4.2. Multipulse Pulse-Position Modulation // Greedy ascent 1: Randomly select X 2: for i = 1 . . . N do 3: V = U \ X 4: Select x ∈ X and v ∈ V 5: X ′ = {X , v} \ {x} (i.e. replace x by v in X ) 6: if (C(X ′) > C(X )) then 7: X = X ′ 8: end if 9: end for 10: Return X Figure 4.9: Pseudo-code for greedy ascent. In this way, the good structure of the best-so-far solution is exploited in generating new trail solutions. Simulated annealing: For a difficult search landscape, the greedy as- cent solution would eventually be trapped into a local maximum and no further improvement could be attained. Simulated annealing [90] is one of the metaheuristical algorithms where the search can probabilistically escape local maxima. Simulated annealing is deduced from the physical anneal- ing process of solid materials. Its solution asymptotically approaches the global maximum. Simulated annealing requires the specification of a start and end temperature from which the cooling coefficient α is derived. These values can be determined by inspecting the annealing curve of the search problem [91]. CWC-Based Search For the CO algorithms, focusing the search in “good” regions of the signal space can improve the quality of the result. To this end, we observe that 107 4.2. Multipulse Pulse-Position Modulation // Simulated annealing 1: Randomly select X 2: Best solution X̂ = X 3: Initial temperature T 4: for i = 1 . . . N do 5: V = U \ X 6: Select x ∈ X and v ∈ V 7: X ′ = {X , v} \ {x} 8: δ = C(X )− C(X ′) 9: Generate uniform random number r in (0,1) 10: if (δ < 0 or r < e−δT ) then 11: X = X ′ 12: end if 13: if (C(X ′) > C(X̂ )) then 14: X̂ = X ′ 15: end if 16: Cool down: T = αT with α < 1 17: end for 18: Return X̂ Figure 4.10: Pseudo-code for simulated annealing. MPPM symbols can be considered as the codewords of a length-n weight-w constant-weight code (CWC). We argue that optimized CWCs with a large minimum Hamming distance dmin are such good regions to focus our search. Since CWCs are only available for certain size A (see tables in [92,93]), the following approach is applied: (i) find a constant-weight code U ′ with large dmin and size A close to M ; (ii) if A ≥ M then replace U in the search algorithms by U ′, i.e. we search only within the CWC; otherwise, we make X always contain U ′. 108 4.2. Multipulse Pulse-Position Modulation Numerical Result We consider the case (n,w,M) = (12, 3, 128), for which the set of all dis- tinct MPPM symbols U has size Mmax = 220. For the Poisson channel with λb = 0.2 [94], the constrained capacity C(U) is plotted in Figure 4.11. Now we use the CO search algorithms above, together with the CWC-based strategy, to find a constellation X ∈ U of size M = 128 which yields the best C(X ). We perform the optimization at SNR of 6.9 dB, at which C(U) = (1/n) logM . Surprisingly, all the search algorithms result in constel- lations that have similar value C(X ) (4.12). This suggests that in practice we can use the simplest algorithm, namely random search5. Having the op- timized constellation by random search, we add the plot of C(X ) vs. SNR to Figure 4.11. It shows that this constellation also yields good C(X ) over the whole range of SNR. For comparison, the constrained channel capacity for 4-PPM is included, which has the same PAPR of ρ = 4.0. We observe that the selected (12, 3, 128) MPPM constellation always outperforms 4-PPM for the entire range of the SNR value. 4.2.3 Labeling and Binary-Coded Modulation With a good MPPM constellation X , we now consider the combination of MPPM with binary coding. We start with the simpler scheme of BICM. 5We further test the algorithms for (n,w,M) = (16, 4, 128) and (16, 4, 256) with several transmission scenarios and also find that the CWC-based random search algorithm yields good results in these cases. 109 4.2. Multipulse Pulse-Position Modulation 3 4 5 6 7 8 9 10 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 C(U) 4-PPM C a p ac it y [b it s/ sl ot ] −→ C(X ) γ [dB] −→ Figure 4.11: Constrained channel capacity of MPPM constellations. Given X , the BICM GMI depends on the labeling L Ibicm(L) = 1 n m−1∑ i=0 I(Bi;Y ) . (4.15) Our goal is to find a labeling that maximizes Ibicm(L). Due to the large search space and the high computational cost to estimate the objective func- tion Ibicm(L), this is again a difficult CO problem. Therefore, we take an indirect approach as below. Generally, Gray labeling is suggested for BICM [3, 53], cf. also [95]. In Gray labeling, the labels of nearest-neighbor signal points differ at only one 110 4.2. Multipulse Pulse-Position Modulation position. For MPPM, where adjacency is measured in terms of Hamming distance between signal vectors, we may not be able to construct a Gray labeling. This is because a necessary condition for the existence of a Gray labeling is that the number of nearest-neighbor signal points to any signal point must not exceed the number of labeling bits. In most relevant cases, MPPM constellations do not satisfy this condition. As an example, for the (12, 3, 128) constellation found in Section 4.2.2, each constellation point has between 11 and 19 nearest neighbors, whereas m = 7. We therefore attempt to find labelings L that are “as Gray as possible.” To this end, we consider the CO problem Mimimize: fG(L) = 1 M M∑ i=1 1 |N (xi)| ∑ xj∈N (xi) dH(bi, bj) , subject to: {bi ∈ {0, 1}m|i = 1, . . . ,M} , (4.16) where N (xi) is the set of the nearest neighbors of xi, bi is the label of xi, and dH(bi, bj) denotes the Hamming distance between labels bi and bj . We note that the cost function fG(L) ≥ 1 is the average Hamming distance between labels of nearest-neighbor symbols, and fG(L) = 1.0 if and only if L is a Gray labeling. Incidentally, a similar cost function has been applied in [96, Eqs. (4), (5)] for a BICM scheme with RF signaling over AWGN channels. Finding the optimal solution of (4.16) might still require the prohibitive total enumeration. We therefore propose a “local search with best improve- ment and random restart” algorithm, which we refer to as Algorithm 1 in the following. The pseudo-code of the algorithm is listed in Figure 4.12. 111 4.2. Multipulse Pulse-Position Modulation // Gray labeling search 1: Generate random labeling L 2: Best-so-far labeling L̂ = L 3: for t = 1 . . . N do 4: L′ = argmin i,j=0...M−1 {fG(L′) : L′ = S(L, i, j), i 6= j} 5: if (fG(L′) < fG(L)) then 6: L = L′ 7: else 8: Generate new random labeling L 9: end if 10: if (fG(L) < fG(L̂)) then 11: L̂ = L 12: end if 13: end for 14: Return L̂ Figure 4.12: Pseudo-code for Gray labeling search. S(L, i, j) denotes the label-swapping operation applied on L such that the labels of the i-th and j-th symbols are swapped. Figure 4.13 (line (b)) shows the BICM GMI corresponding to the optimized labeling for the (12, 3, 128) constellation from Section 4.2.1 and N = 1000 search steps in Algorithm 1. To illustrate the effectiveness of Algorithm 1, we also compare the result with labelings found by a search over 1000 randomly generated labelings (line (c) in Figure 4.11). We observe that the Gray-like labeling obtained from using (4.16) with Algorithm 1 significantly improves the BICM GMI. However, while the GMI associated with 4-PPM BICM (line (g)) is virtually as good as 4-PPM MLC (line (f)), MPPM BICM leaves a notable gap to the constrained capacity (line (a)), especially at medium-to- low SNR values. We therefore propose RL-MLC architecture, which makes use of the BICM-optimized labeling, and is able to narrow this gap (line (d) and (e)). The MLC configurations for line (d) and (e) are h = [1 1 1 1 2 2 2] 112 4.2. Multipulse Pulse-Position Modulation 3 4 5 6 7 8 9 10 0.1 0.2 0.3 0.4 0.5 0.6 (a) (b) (c) (d) (e) (f) (g) R at e [b it s/ sl ot ] −→ γ [dB] −→ Figure 4.13: Constrained capacities or GMIs of MPPM transmission: (a) C(X ) with (n,w,M) = (12, 3, 128) by a random search; (b) BICM GMI with Gray-like labeling obtained with Algorithm 1 (Figure 4.12); (c) BICM GMI with labeling from a random search; (d) GMI of a 2-layer MLC; (e) GMI of a 3-layer MLC. For comparison, (f) and (g) are the constrained capacity and BICM GMI of 4-PPM, which has the same PAPR ρ as (12,3)-MPPM. and h = [1 1 2 2 3 3 3], respectively. It is worth pointing out that we have arrived at the MLC schemes via two greedy optimization stages: finding a labeling that maximizes the BICM GMI, and then determining an MLC configuration that maximizes the MLC GMI for this labeling. Nevertheless, the results in Figure 4.13 indicate that there is only little room for possible improvement by a joint optimization of labeling and MLC configurations. 113 4.3. Conclusion 4.3 Conclusion In this chapter, we first revisited the rateless BICM scheme for hybrid FSO- RF transmission and showed a new approach to rate analysis via the concept of the I-curve. In the second part, we presented the design process for coded MPPM transmission. In particular, we considered the two fundamental questions of when MPPM is preferable over PPM and how MPPM could be combined with ECC. To this end, we compared MPPM and PPM FSO transmission under simultaneous limited peak-power, average power, and bandwidth constraints. We then devised decimation and labeling strategies for the application of binary ECC to MPPM. It has been found that BICM GMI leaves a notable gap to the constrained channel capacity at medium- to-low SNR range, which can be bridged by MLC schemes with only several encoder-decoder pairs. 114 Chapter 5 Concluding Remarks 5.1 Summary of Contributions Since binary-coded modulation is the current de facto coding standard for digital communication systems, and since practical implementations of such systems almost certainly use some low-complexity approximate metrics, the scope and results of this thesis are particularly interesting and relevant to professionals in communications. Our contributions in this thesis range from labeling design for a specific scheme to new insights that are useful for improving the performance of many practical systems and have implications beyond the binary coding framework. In the following, we summarize our main contributions with remarks on their impacts and some ideas for further research. • Relationship between the I-curve and SBS throughput performance: The I-curve is derived from the generalized Gallager function, which is in turn derived from the random coding argument with word decoding. Its peak value, the GMI, has been routinely used in the literature as an upper bound to the throughput performance of SBS decoding. In this thesis we further discovered an intriguing influence of the critical point 115 5.1. Summary of Contributions of the I-curve on the performance of SBS decoding, cf. Example 2.1. • I-curve decomposition: We showed that the I-curve of a compound channel is equal to the baud-rate weighted sum of the individual chan- nels’ I-curves. In Section 2.2, this decomposition is between the BICM channel and the virtual binary channels of the levels, regardless of the input distribution pX(x). The same result has been reported in [9] for uniform input. In Section 4.1, the decomposition is between the coding diversity channel and the component physical channels. • Metric scaling: We discovered in Section 2.3.1 and 2.3.2 that metric scaling with a constant factor in the logarithmic domain can shift the critical point of the I-curve without affecting the GMI. Together with the two above contributions, this finding leads to a versatile and very practical metric manipulation method that can improve coded performance in a wide range of mismatched transmission scenarios. • Multidimensional metric correction functions for BICM: By consider- ing the BICM approximate detector as part of a cascaded channel, we naturally arrived at metric mismatch correction functions for BICM. These functions can be practical in certain situations, and in general shed new light on the upper GMI limit of BICM with mismatched decoding metrics, cf. Section 2.3.3. • Reduced-layer and rateless MLC: The two main drawbacks of MLC are its structural complexity and the need to carefully design code rate for each layer to realize its performance gains compared to BICM. Our 116 5.2. Suggested Future Work contributions in Chapter 3 can alleviate both of these drawbacks. With the reduced-layer coding concept, we can design MLC schemes with any number of coding layer. Next, using our rateless MLC scheme, we can preserve the rate advantage of MLC while not having to design individual codes for each coding layer. • Design of MPPM signaling: We showed a systematic design process for MPPM signaling in Section 4.2. Unlike previous studies on the application of MPPM, we start by identifying parameters which po- tentially yield better performances compared to MPPM’s main com- peting modulation formats. Then, using suitable optimization tools, we select decimated constellations and symbol labels that return good achievable rates in BICM and MLC schemes. 5.2 Suggested Future Work Perhaps the most interesting unsolved problem that has been opened up by this thesis is to find a rigorous theoretical explanation for the variation of the achieved SBS decoding throughput versus the critical point of the I-curve, as illustrated in Example 2.1. In particular, a solution to this prob- lem should explain why the SBS decoding throughput approaches the GMI when sqX,Y = 1, but only IqX,Y (1) when sqX,Y > 1. It should also lead to an estimation of the achievable throughput by max-product SBS decoding, which can be of great interest for communication system designers. The contributions of this thesis to the GMI framework for BICM and MLC are generic and applicable to many practical systems with mismatched 117 5.2. Suggested Future Work decoding metrics. Specifically, the achievable rates by these systems can be measured in terms of the GMI, and metric correction methods from this thesis can be applied to increase both the GMI and throughput performance by SBS decoding. Examples of such systems are wireless communications with simplified metrics, orthogonal-frequency division multiplexing (OFDM) systems with exceeding peak-to-average power ratio (PAPR), and multiuser detection. 118 Bibliography [1] S. Haykin, Communication Systems, 4th ed. New York, NY: Wiley, 2000. [2] E. Zehavi, “8–PSK trellis codes for a Rayleigh channel,” IEEE Trans. Commun., vol. 40, no. 5, pp. 873–884, May 1992. [3] G. Caire, G. Taricco, and E. Biglieri, “Bit-interleaved coded modula- tion,” IEEE Trans. Inf. Theory, vol. 44, pp. 927–946, May 1998. [4] H. Imai and S. Hirakawa, “A new multilevel coding method using error correcting codes,” IEEE Trans. Inf. Theory, vol. 23, pp. 371–377, 1977. [5] U. Wachsmann, R. Fischer, and J. B. Huber, “Multilevel codes: theo- retical concepts and practical design rules,” IEEE Trans. Inf. Theory, vol. 45, no. 5, pp. 1367–1391, Jul. 1999. [6] S. Hranilovic, Wireless Optical Communication Systems. Springer, 2005. [7] A. K. Majumdar and J. C. Ricklin, Eds., Free-Space Laser Communi- cations: Principles and Advances. Springer, Dec. 2010. 119 Bibliography [8] A. Guillén i Fàbregas, A. Martinez, and G. Caire, “Bit-interleaved coded modulation,” Found. Trends Commun. Inf. Theory, vol. 5, no. 1-2, pp. 1–135, 2008. [9] A. Martinez, A. Guillén i Fàbregas, G. Caire, and F. Willems, “Bit- interleaved coded modulation revisited: A mismatched decoding per- spective,” IEEE Trans. Inf. Theory, vol. 55, no. 6, Jun. 2009. [10] G. Kaplan and S. Shamai, “Information rates and error exponents of compound channels with application to antipodal signaling in a fading environment,” Archiv Elektronik Übertragungstechnik (AEÜ), vol. 47, no. 4, pp. 228–239, 1993. [11] N. Merhav, A. Lapidoth, and S. Shamai, “On information rates for mismatched decoders,” IEEE Trans. Inf. Theory, vol. 40, no. 6, pp. 1953–1967, 1994. [12] L. Lampe, R. Schober, and R. Fischer, “Multilevel coding for multiple- antenna transmission,” IEEE Trans. Wireless Commun., vol. 3, pp. 203–208, Jan. 2004. [13] A. Shokrollahi, “Raptor codes,” IEEE Trans. Inf. Theory, vol. 52, no. 6, pp. 2551–2567, Jun. 2006. [14] A. AbdulHussein, A. Oka, T. T. Nguyen, and L. Lampe, “Rateless cod- ing for hybrid free-space optial and radio-frequency communication,” IEEE Trans. Wireless Commun., vol. 9, no. 3, pp. 907–913, Mar. 2010. 120 Bibliography [15] J. N. Laneman, E. Martinian, G. W. Wornell, and J. G. Apostolopou- los, “Source-channel diversity for parallel channels,” IEEE Trans. Inf. Theory, vol. 51, no. 10, pp. 3518–3539, 2005. [16] H. Sugiyama and K. Nosu, “MPPM: a method for improving the band- utilization efficiency in optical PPM,” J. Lightwave Tech., vol. 7, no. 3, pp. 465–472, Mar. 1989. [17] S. H. Muller-Weinfurtner, “Coding approaches for multiple antenna transmission in fast fading and OFDM,” IEEE Trans. Signal Process., vol. 50, no. 10, pp. 2442–2450, 2002. [18] M. Butler and I. B. Collings, “A zero-forcing approximate log-likelihood receiver for MIMO bit-interleaved coded modulation,” IEEE Commun. Lett., vol. 8, no. 2, pp. 105–107, Feb. 2004. [19] M. R. McKay and I. B. Collings, “Capacity and performance of MIMO- BICM with zero-forcing receivers,” IEEE Trans. Commun., vol. 53, no. 1, pp. 74–83, Jan. 2005. [20] ——, “Error performance of MIMO-BICM with zero-forcing receivers in spatially-correlated rayleigh channels,” IEEE Trans. Wireless Com- mun., vol. 6, no. 3, pp. 787–792, Mar. 2005. [21] I. B. Collings, M. Butler, and M. McKay, “Low complexity receiver design for MIMO bit-interleaved coded modulation,” in Proc. IEEE ISSTA, Aug.-Sep. 2004, pp. 12–16. 121 Bibliography [22] D. Seethaler, G. Matz, and F. Hlawatsch, “An efficient MMSE-based demodulator for MIMO bit-interleaved coded modulation,” in Proc. IEEE GLOBECOM, vol. 4, Nov.-Dec. 2004, pp. 2455–2459. [23] R. Ghaffar and R. Knopp, “Low complexity metrics for BICM SISO and MIMO systems,” in Proc. IEEE VTC 2010-Spring, 2010, pp. 1–6. [24] J. Jaldén, P. Fertl, and G. Matz, “On the generalized mutual informa- tion of BICM systems with approximate demodulation,” in IEEE Inf. Theory Workshop, Cairo, Egypt, Jan. 2010. [25] D. Divsalar, H. Jin, and R. J. McEliece, “Coding theorems for turbo-like codes,” in Proc. 36th Allerton Conf. Commun., Control and Computing, 1998, pp. 201–210. [26] R. G. Gallager, Low Density Parity Check Codes. M.I.T. Press, 1963. [27] R. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory, vol. 27, no. 5, pp. 533–547, Sep. 1981. [28] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399–431, 1999. [29] T. Richardson and R. Urbanke, “The capacity of low-density parity- check codes under message-passing decoding,” IEEE Trans. Inf. The- ory, vol. 47, no. 2, pp. 599–618, Feb. 2001. [30] S. Chung, G. Forney, T. Richardson, and R. Urbanke, “On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit,” IEEE Commun. Lett., vol. 5, no. 2, pp. 58–60, 2001. 122 Bibliography [31] W. E. Ryan, “An introduction to LDPC codes,” in CRC Handbook for Coding and Signal Processing for Recording Systems. CRC Press, 2004. [32] O. Etesami and A. Shokrollahi, “Raptor codes on binary memoryless symmetric channels,” IEEE Trans. Inf. Theory, vol. 52, no. 5, pp. 2033– 2051, May 2006. [33] J. Castura and Y. Mao, “Rateless coding over fading channels,” IEEE Commun. Lett., vol. 10, no. 1, pp. 46–48, Jan. 2006. [34] R. G. Gallager, Information Theory and Reliable Communication. New York, NY: Wiley, 1968. [35] I. Sason and S. Shamai, “Performance analysis of linear codes under maximum-likelihood decoding: a tutorial,” Found. Trends Commun. Inf. Theory, vol. 3, no. 1-2, pp. 1–223, 2006. [36] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 498–519, 2001. [37] M. Luby, “LT codes,” in Proc. 43rd IEEE Symp. Found. Comp. Sc. (FOCS), Vancouver, BC, Canada, Nov. 2002, pp. 271–280. [38] X.-Y. Hu, E. Eleftheriou, and D. Arnold, “Regular and irregular pro- gressive edge-growth Tanner graphs,” IEEE Trans. Inf. Theory, vol. 51, no. 1, pp. 386–398, Jan. 2005. 123 Bibliography [39] X.-Y. Hu, “Source code for progressive edge growth parity- check matrix construction,” 2003. [Online]. Available: http: //www.inference.phy.cam.ac.uk/mackay/PEG ECC.html [40] J. Hou, P. Siegel, L. Milstein, and H. Pfister, “Capacity-approaching bandwidth-efficient coded modulation schemes based on low-density parity-check codes,” IEEE Trans. Inf. Theory, vol. 49, no. 9, pp. 2141– 2155, 2003. [41] W. Tan and J. R. Cruz, “Signal-to-noise ratio mismatch for low-density parity-check coded magnetic recording channels,” IEEE Trans. Magn., vol. 40, no. 2, pp. 498–506, 2004. [42] H. Saeedi and A. H. Banihashemi, “Performance of belief propagation for decoding LDPC codes in the presence of channel estimation error,” IEEE Trans. Commun., vol. 55, no. 1, pp. 83–89, Jan. 2007. [43] J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Com- mun., vol. 53, no. 8, pp. 1288–1299, 2005. [44] S. G. Lechner and J. Sayir, “Improved sum-min decoding for irregular LDPC codes,” in Proc. Intl. Symp. Turbo Codes and Related Topics, Munich, Germany, Apr. 2006. [45] G. Lechner, “Efficient decoding techniques for LDPC codes,” Ph.D. dissertation, Vienna Univ. of Tech., Jul. 2007. 124 Bibliography [46] S. Papaharalabos and P. Mathiopoulos, “Simplified sum-product al- gorithm for decoding LDPC codes with optimal performance,” IEE Electronics Letters, vol. 45, no. 2, pp. 116–117, 2009. [47] T. Cover and J. Thomas, Elements of Information Theory, 2nd ed. Wiley, 2006. [48] A. Burg, M. Wenk, and W. Fichtner, “VLSI implementation of pipelined sphere decoding with early termination,” in Proc. Europ. Sig. Processing Conf., Florence, Italy, Sep. 2006. [49] S. Schwandter, P. Fertl, C. Novak, and G. Matz, “Log-likelihood ratio clipping in MIMO-BICM systems: Information geometric analysis and impact on system capacity,” in Proc. IEEE ICASSP, Taipei, Taiwan, Apr. 2009, pp. 2433–2436. [50] C. Novak, P. Fertl, and G. Matz, “Quantization for soft-output demod- ulators in bit-interleaved coded modulation systems,” in Proc. IEEE Intl. Symp. Inf. Theory (ISIT), Seoul, Korea, Jun. 2009, pp. 1070–1074. [51] C. Studer and H. Bölcskei, “Soft-input soft-output single tree-search sphere decoding,” IEEE Trans. Inf. Theory, vol. 56, no. 10, pp. 4827– 4842, Oct. 2010. [52] M. van Dijk, A. J. E. M. Janssen, and A. G. C. Koppelaar, “Correct- ing systematic mismatches in computed log-likelihood ratios,” Europ. Trans. Telecommun., vol. 14, no. 3, pp. 227–244, 2003. 125 Bibliography [53] C. Stierstorfer and R. F. H. Fischer, “(Gray) mappings for bit- interleaved coded modulation,” in Proc. IEEE Vehicular Tech. Conf. (VTC) Spring, May 2007, pp. 1703 –1707. [54] ——, “Mappings for BICM in UWB scenarios,” in Proc. 7th Intl. ITG Conf. Source Channel Coding (SCC), Ulm, Germany, 2008. [55] J. Proakis, Digital Communications, 4th ed. New York, NY: McGraw- Hill, 2001. [56] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with Fomulas, Graphs, and Mathematical Tables. New York, NY: Dover Press, 1972. [57] J. Panaro, “Simplified soft-output demapper for bit-interleaved coded orthogonal modulation,” in Proc. Intl. Conf. Wireless Mobile Com- mun., Jul. 2006. [58] A. Guillén i Fàbregas and A. J. Grant, “Capacity approaching codes for non-coherent orthogonal modulation,” IEEE Trans. Wireless Com- mun., vol. 6, no. 11, pp. 4004–4013, Nov. 2007. [59] X. Li and J. A. Ritcey, “Bit-interleaved coded modulation with iterative decoding using soft feedback,” Electron. Lett., vol. 34, no. 10, pp. 942– 943, 1998. [60] ——, “Trellis-coded modulation with bit interleaving and iterative de- coding,” IEEE J. Sel. Areas Commun., vol. 17, no. 4, pp. 715–724, Apr. 1999. 126 Bibliography [61] S. J. Dolinar, J. Hamkins, B. E. Moision, and V. A. Vilnrotter, “Op- tical modulation and coding,” in Deep Space Optical Communications, H. Hemmati, Ed. Wiley-Interscience, Apr. 2006. [62] J. Hamkins and B. Moision, “Multipulse pulse-position modulation on discrete memoryless channels,” JPL Interplanetary Network Progress Report, vol. 42, p. 161, May 2005. [63] D. J. C. MacKay, Information Theory Inference and Learning Algo- rithms. Cambridge University Press, 2003. [64] U. Wachsmann, Coded Modulation: Theoretical Concepts and Practical Design Rules. Aachen, Germany: Shaker Verlag, 1999. [65] A. Ganti, A. Lapidoth, and I. Telatar, “Mismatched decoding revisited: general alphabets, channels with memory, and the wide-band limit,” IEEE Trans. Inf. Theory, vol. 46, no. 7, pp. 2315–2328, 2000. [66] C. Lott, O. Milenkovic, and E. Soljanin, “Hybrid ARQ: Theory, state of the art and future directions,” in Proc. IEEE Inf. Theory Workshop, Jul. 2007, pp. 1–5. [67] R. Unbehauen, Systemtheorie. Oldenbourg, 1993. [68] E. F. Camacho and C. Bordons, Model Predictive Control. Springer, Jun. 1999. [69] R. Palanki and J. Yedidia, “Rateless codes on noisy channels,” 2004. [Online]. Available: http://www.merl.com/reports/docs/TR2003-124. pdf 127 Bibliography [70] R. Khalona, “Unified performance analysis of Reed-Solomon coded M- ary FSK modulation in AWGN, Rician and Rayleigh fading channels,” in Proc. Intl. Conf. Universal Personal Commun. (ICUPC), vol. 2, Oct. 1993, pp. 662–668. [71] I. I. Kim and E. Korevaar, “Availability of free space optics (FSO) and hybrid FSO/RF systems,” in Proc. SPIE, Optical Wireless Communi- cations IV, vol. 4530, Denver, CO, Aug. 2001, pp. 84–95. [72] J. Pan, M. Evans, T. Euler, H. Johnson, and F. DeNap, “Free-space optical communications: opportunities and challenges from a carrier’s perspective,” in Proc. SPIE, Wireless and Mobile Communications II, vol. 4911, Shanghai, China, 2002, pp. 58–72. [73] E. Leitgeb, M. Gebhart, U. Birnbacher, W. Kogler, and P. Schrotter, “High availability of hybrid wireless networks,” in Proc. SPIE, vol. 5465, 2004, pp. 238–249. [74] J. Derenick, C. Thorne, and J. Spletzer, “On the deployment of a hybrid free-space optic/radio frequency (FSO/RF) mobile ad-hoc network,” in Proc. IEEE/RSJ Intl. Conf. Intelligent Robots and Systems, 2005, pp. 3990–3996. [75] A. Akbulut, H. Ilk, and F. Ari, “Design, availability and reliability analysis on an experimental outdoor FSO/RF communication system,” in Proc. Intl. Conf. Transparent Optical Networks (ICTON), 2005, pp. 403–406. 128 Bibliography [76] W. Zhang, S. Hranilovic, and C. Chi, “Soft-switching hybrid FSO/RF links using short-length raptor codes: Design and implementation,” IEEE J. Sel. Areas Commun., vol. 27, no. 9, pp. 1698–1708, Dec. 2009. [77] B. He and R. Schober, “Bit-interleaved coded modulation for hybrid RF/FSO systems,” IEEE Trans. Commun., vol. 57, no. 12, Dec. 2009. [78] J. Massey, “Capacity, cutoff rate, and coding for a direct-detection optical channel,” IEEE Trans. Commun., vol. 29, pp. 1615–1621, 1981. [79] R. McEliece, “Practical codes for photon communication,” IEEE Trans. Inf. Theory, vol. 27, pp. 393–398, 1981. [80] M. Takahasi, H. Yashima, I. Sasase, and S. Mori, “Capacity and ef- fects of Reed-Solomon codes on multi-pulse PPM in optical communi- cations,” in Proc. IEEE ICC, vol. 4, 1990, pp. 1663–1667. [81] J. M. Budinger, M. J. Vanderaar, P. K. Wagner, S. B. Bibyk, and G. S. Mecherle, “Combinatorial pulse position modulation for power-efficient free-space laser communications,” in Proc. SPIE, vol. 1866, Jan. 1993, pp. 214–225. [82] K. Sato, T. Ohtsuki, and I. Sasase, “Performance of coded multi-pulse PPM with imperfect slot synchronization in optical direct-detection channel,” in Proc. IEEE ICC, vol. 1, 2004, pp. 121–125. [83] C. N. Georghiades, “Modulation and coding for throughput-efficient optical systems,” IEEE Trans. Inf. Theory, vol. 40, no. 5, Sep. 1994. 129 Bibliography [84] M. K. Simon and V. A. Vilnrotter, “Multi-pulse pulse-position modu- lation signaling for optical communication with direct detection,” IPN Progress Report, vol. 42-155, pp. 1–22, Nov. 2003. [85] H. Park, “Performance bound on multiple-pulse position modulation,” Optical Review, vol. 10, no. 3, pp. 131–132, May 2003. [86] G. E. Atkin and K.-S. L. Fung, “Coded multipulse modulation in optical communication systems,” IEEE Trans. Commun., vol. 42, pp. 574–582, Apr. 1994. [87] H. Park and J. R. Barry, “Trellis-coded multiple-pulse-position modu- lation for wireless infrared communications,” IEEE Trans. Commun., vol. 52, no. 4, pp. 643–651, 2004. [88] A. S. Alahmari, “Turbo coded pulse position modulation for optical communications,” Ph.D. dissertation, Georgia Institute of Technology, 2003. [89] C. R. Reeves, Ed., Modern Heuristic Techniques for Combinatorial Problems. London, UK: Blackwell Scientific Publications, Apr. 1993. [90] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by sim- ulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983. [91] S. R. White, “Concepts of scale in simulated annealing,” in Proc. IEEE ICCD, 1984, pp. 646–651. 130 Bibliography [92] A. Brouwer, J. Shearer, N. Sloane, and W. Smith, “A new table of constant weight codes,” IEEE Trans. Inf. Theory, vol. 36, no. 6, pp. 1334–1380, 1990. [93] D. H. Smith, L. A. Hughes, and S. Perkins, “A new table of constant weight codes of length greater than 28,” Electron. J. Combinatorics, vol. 13, no. A2, 2006. [94] B. Moision and J. Hamkins, “Coded modulation for the deep-space optical channel: Serially concatenated pulse-position modulation,” IPN Progress Report, vol. 42-161, May 2005. [95] V. Sethuraman and B. Hajek, “Comments on “Bit-interleaved coded modulation”,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1795–1797, 2006. [96] S. Y. Le Goff, “Signal constellations for bit-interleaved coded modula- tion,” IEEE Trans. Inf. Theory, vol. 49, pp. 307–313, Jan. 2003. 131