Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Binary-coded modulation and applications in free-space optics Nguyen, Trung Thanh 2011

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2011_spring_nguyen_trungthanh.pdf [ 1.4MB ]
Metadata
JSON: 24-1.0071660.json
JSON-LD: 24-1.0071660-ld.json
RDF/XML (Pretty): 24-1.0071660-rdf.xml
RDF/JSON: 24-1.0071660-rdf.json
Turtle: 24-1.0071660-turtle.txt
N-Triples: 24-1.0071660-rdf-ntriples.txt
Original Record: 24-1.0071660-source.json
Full Text
24-1.0071660-fulltext.txt
Citation
24-1.0071660.ris

Full Text

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 modulation (BICM) and multilevel coding (MLC) are pragmatic methods to achieve both high power and bandwidth efficiencies in digital communications. These techniques enable the combination of powerful and popular off-the-shelf binary codes with bandwidth-efficient multilevel signaling without 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 coding 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 bitinterleaved coded noncoherent orthogonal modulation,” IEEE Communications Letters, accepted Mar. 2011. 4. (Part of Chapter 4) T. T. Nguyen and L. Lampe, “MPPM consteliv  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 Transactions on Communications, vol. 59, no. 2, pp. 437-447, Feb. 2011. 6. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, “Coded multipulse pulse-position modulation for free-space optical communications,” 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 radiofrequency communication,” IEEE Transactions on Wireless Communications, vol. 9, no. 3, pp. 1615-1619, Mar. 2010. Conference papers 1. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, “Rateless multilevel coding and applications,” in Proc. IEEE GLOBECOM, Honolulu, Hawaii, USA, Nov.-Dec. 2009. 2. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, “Coded pulseposition 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  ii  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  iv  Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . .  vi  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  ix  List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  x  Abstract Preface  List of Tables  List of Abbreviations  . . . . . . . . . . . . . . . . . . . . . . . . . xiii  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xv 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1  . . . . . . . . .  6  . . . . . . . .  8  . . . . . . . . . . . . . . .  11  2 BICM with Mismatched Decoding Metrics 2.1  Random Coding with A Given Decoding Rule  2.2  BICM and Mismatched Decoding 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 Correction  2.4  2.5  . . . . . . . . . . . . . . . . . . . . . . . . . .  26  . . . . . . . . . . . . . . . . . . . . . . . . . . .  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  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52  Applications  Conclusion  3 Multilevel Coding: Reduced-Layer, General Decoding Metrics, and Rateless Transmission . . . . . . . . . . . . . . . . .  54  3.1  Reduced-Layer MLC  57  3.2  Multilevel Coding with General Decoding Metrics  3.3  3.4  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  59  . . . . . . . . . . . . . . . . . . . .  59  3.2.1  Achievable Rates  3.2.2  Per-Layer Transmission and GMI  3.2.3  Metric-Mismatch Correction  . . . . . . . . . . .  61  . . . . . . . . . . . . . .  67  . . . . . . . . . . . . . . . . . . .  67  3.3.1  Encoding and Decoding . . . . . . . . . . . . . . . . .  68  3.3.2  Operation Analysis and Control  . . . . . . . . . . . .  72  . . . . . . . . . . . . . . . . . . . . . . . . . . .  81  3.4.1  MIMO-QAM . . . . . . . . . . . . . . . . . . . . . . .  81  3.4.2  Noncoherent Carrier-Modulated Orthogonal Signaling  83  Rateless Multilevel Coding  Applications  vii  Table of Contents 3.4.3 3.5  Pulse-Position Modulation with Direct Detection  Conclusion  . .  87  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  90  . . . . . . . . . . . . . . .  91  4 Applications in Free-Space Optics 4.1  4.2  4.3  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  Multipulse Pulse-Position Modulation . . . . . . . . . . . . .  99  4.2.1  Constellation Selection  4.2.2  Subset Selection . . . . . . . . . . . . . . . . . . . . . 105  4.2.3  Labeling and Binary-Coded Modulation . . . . . . . . 109  Conclusion  . . . . . . . . . . . . . . . . . 103  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Eq0X,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 metricscaling 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 mismatch correction functions. . . . . . . . . . . . . . . . . . . .  34  Approximation to the function ln(I0 (·)). . . . . . . . . . . . .  39  2.10 BICM GMI of noncoherent orthogonal modulation. . . . . . .  41  2.9  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 transmission 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 128PPM over Poisson channel with λb = 0.2. . . . . . . . . . . .  3.5  66  Rotation rateless MLC transmitter and receiver. Stream redirection 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 noncoherent 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. . . . . . . . . . . . . .  4.4  96  Throughput and GMI during the transmission of 200 consecutive 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, Victor 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 stimulating 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 bandwidth and transmit power [1]. Channel bandwidth utilization can often be increased by using larger multilevel constellations. Transmit power requirement can be minimized by error-control coding (ECC). However, non-binary codes for multilevel constellations are usually harder to design and implement, and thus binary codes are much more popular in practice. A pragmatic 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 metrics 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 currently the de facto coding standard for digital communication. Recently, 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 leveldependent scaling of logarithmic bit metrics can improve the BICM GMI. Second, we consider the effect of metric scaling on symbol-bysymbol (SBS) decoding, which is used in a number of modern capacityapproaching 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 general 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 significantly increase the performance of mismatched BICM. • Chapter 3 – Multilevel Coding: Reduced-Layer, General Decoding Metrics, 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 scenarios such as multiple-input multiple-output (MIMO) and orthogonal modulation transmission. In this chapter, we make three distinct contributions to MLC. First, based on a previous work [12], we develop 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. Second, we present rate analysis and metric-mismatched correction for  3  Chapter 1. Introduction MLC with general decoding metrics. This contribution is an extension of the results for BICM from Chapter 2. Third, we consider the combination of MLC with rateless codes, e.g. [13]. Such a combination 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 transmission. However, despite these great potential benefits, we show that a careless combination of MLC and rateless coding would lead to significant 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 signaling, 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 communication 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 efficiency 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 metrics 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´en et al. [24] have recently devised 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 Section 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 Raptor 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 numerical 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.  message bits  transmitter  x  channel  y  pY |X (y|x)  receiver  decoded 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 channel 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 N −1  qX,Y (x, y) =  qX,Y (xk , yk ) .  (2.1)  k=0  8  2.1. Random Coding with A Given Decoding Rule The decoder output is determined by  ˆ = argmax qX,Y (x, y) . x  (2.2)  x∈C  The symbol metric qX,Y (x, y) is called a matched metric if it is proportional to the channel transition probability pY |X (y|x). It is called a mismatched 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  ˆ = argmin 1 − pX|Y (x|y) . x x∈C  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  qX,Y (x, Y ) pX (x) qX,Y (X, Y )  s  ρ  N  (2.3)  for all 0 ≤ ρ ≤ 1 and s > 0. Alternatively, P ≤2 where R  log M N  −N Eqr  X,Y  (R)  ,  (2.4)  (notation log(·) denotes logarithm with base 2) is the code  rate, EqrX,Y (R)  max max Eq0X,Y (ρ, s) − ρR  0≤ρ≤1 s>0  (2.5) 9  2.1. Random Coding with A Given Decoding Rule is the random coding exponent, and Eq0X,Y  (ρ, s)  − log EX,Y  x∈X  qX,Y (x, Y ) pX (x) qX,Y (X, Y )  s  ρ  (2.6)  is the generalized Gallager function. If EqrX,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 Eq0X,Y (ρ, s), cf. [34, Theorem 5.6.3], is the GMI, which is defined as [10] Iqgmi X,Y  max IqX,Y (s) ,  (2.7)  s>0  with  IqX,Y (s)  ∂Eq0X,Y (ρ, s) ∂ρ = lim  ρ=0  Eq0X,Y (ρ, s)  ρ→0  = −EX,Y  ρ log  pX (x) x∈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 Eq0X,Y (ρ, s). The Icurve is the intersection of the plane ρ = 1 and the surface which is tangent to the generalized Gallager function at ρ = 0. With matched metrics, the 1 ) is the conventional one-dimensional Gallager function, line Eq0X,Y (ρ, 1+ρ  10  2.2. BICM and Mismatched Decoding  I−curve tangent surface  GMI  generalized Gallager function  s  ρ  Figure 2.2: Example of the generalized Gallager function Eq0X,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  2.2  log  pX (x) x∈X  pY |X (Y |x) pY |X (Y |X)  .  (2.9)  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  message bits  coded bits  binary encoder  mapper  x  BICM transmitter  bit metrics  y detector  binary decoder  decoded bits  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. Furthermore, 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) =  pX (x) ,  (2.10)  x∈Xib 1  When 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 Xib  {x ∈ X : bi (x) = b}, and m−1  pX (x) =  pBi (bi (x)) .  (2.11)  i=0  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 m−1  qX,Y (x, y) =  qBi ,Y (bi (x), y) .  (2.12)  i=0  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) =  pY |X (y|x)pX (x) ,  (2.13)  x∈Xib  the BICM symbol metric (2.12) still does not match to the channel with input 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(·) denotes 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 Eq0B ,Y i  (ρ, s)  − log EBi ,Y = − log EX,Y  b∈B  b∈B  qBi ,Y (b, Y ) pBi (b) qBi ,Y (Bi , Y )  s  qBi ,Y (b, Y ) pBi (b) qBi ,Y (bi (X), Y )  ρ  (2.15) 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  pX,Y (x, y) = pBi ,Y (b, y) .  (2.17)  x∈Xib  The function Eq0B ,Y (ρ, s) gives rise to the binary random coding exponent i  EqrB ,Y i  (R), the I-curve function IqBi ,Y (s), and the GMI Iqgmi Bi ,Y for the i-th  level, applying (2.5), (2.8), and (2.7), respectively. In particular,  IqBi ,Y (s) = −EBi ,Y  log  = −EX,Y  log  b∈B  qBi ,Y (b, Y ) pBi (b) qBi ,Y (Bi , Y )  pBi (b) b∈B  s  qBi ,Y (b, Y ) qBi ,Y (bi (X), Y )  s  ,  (2.18)  and Iqgmi = max IqBi ,Y (s) . B ,Y i  (2.19)  s>0  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  m−1  IqX,Y (s) = −EX,Y  log  = −EX,Y  log  pBi (bi (x)) x∈X i=0 m−1  qBi ,Y (b, Y ) qBi ,Y (bi (X), Y )  s  pBi (b)  qBi ,Y (b, Y ) qBi ,Y (bi (X), Y )  s  pBi (b)  i=0 b∈B  m−1  =−  i=0  EX,Y  log  qBi ,Y (bi (x), Y ) qBi ,Y (bi (X), Y )  b∈B  s  m−1  =  IqBi ,Y (s) .  (2.21)  i=0  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 qX,Y (x, y) = [qX,Y (x, y)]c with some constant c > 0. It follows from (2.6) that the new generalized Gallager function is Eq0  X,Y  (ρ, s) = Eq0X,Y (ρ, cs) and hence IqX,Y (s) = IqX,Y (cs).  That is, the I-curve of the metric qX,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 Iqgmi X,Y  IqX,Y (s)  ′ IqX,Y (s)  ′ = sqX,Y /c sqX,Y  sqX,Y s  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 critical point changes to sqX,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 scaling.” 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 qX,Y (x, y), the decoding rule (2.2) becomes ˆ = argmax [qX,Y (x, y)]c , x x∈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 Icurves 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 qBi ,Y (b, y) = [qBi ,Y (b, y)]ci with some ci > 0. Then, IqB ,Y (s) = i  IqBi ,Y (ci s), which peaks at (sqBi ,Y  /ci , Iqgmi Bi ,Y  ). According to Section 2.2 and  in particular (2.12) and (2.21), BICM with these bit metrics has the symbol metric m−1  qX,Y (x, y) =  qBi ,Y (bi (x), y) i=0  and the I-curve function m−1  IqX,Y (s) =  IqB ,Y (s) . i  i=0  The BICM GMI is upper-bounded as m−1  Iqgmi X,Y  = max s>0  IqB ,Y (s) i=0  i  m−1  ≤  i=0 m−1  =  max IqB ,Y (s)  (2.22)  Iqgmi . B ,Y  (2.23)  s>0  i  i  i=0  Equality in (2.22) is achieved if and only if all binary I-curves {IqB ,Y (s), i  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 alignment is needed and Iqgmi X,Y =  m−1 gmi i=0 IqBi ,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 expressions 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)  qX,Y (x, y) x∈Ckx N −1  =  qX,Y (xk , yk ) x∈Ckx  (2.24)  k=0  is computed, where Ckx denotes the set of codewords whose k-th symbol equals x, and the decoding rule  x ˆk = argmax qXk ,Y (x, y)  (2.25)  x∈X  is applied. For sparse-graph based codes, (2.25) with metric (2.24) can be efficiently evaluated (or approximated) using the sum-product algorithm [36]. With matched metrics and equally likely chosen codewords, (2.25) becomes  pY |X (y|x)  x ˆk = argmax x∈X  x∈Ckx  = argmax x∈X  pX|Y (x|y) x∈Ckx  = argmax pXk |Y (x|y) x∈X  = argmin 1 − pXk |Y (x|y) . x∈X  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 [ˆ x0 . . . 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) =  =     maxx qX,Y (x, y) ,  if Ckx = ∅    0,     max  otherwise .  x∈Ck  x∈Ckx     0,  N −1  qX,Y (xk , yk ) k=0  ,  if Ckx = ∅  (2.26)  otherwise .  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 domain [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 outcome 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 random, 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 mismatched 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 transmission. 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 ps1 p0 (1 − p1 )s 1 − p0 log 1 + − log 1 + 2 (1 − p0 )s 2 ps0 s s (1 − p0 ) p0 p1 1 − p1 log 1 + , − log 1 + − s 2 p1 2 (1 − p1 )s  IpY |X (s) = 1 −  (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 Iqgmi X,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 Iqgmi X,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 IqX,Y (s) = IqX,Y (cs). Consider IqX,Y (1) as a function of c. It attains its maximum with c = sqX,Y = ln((1 − p)/p), for which IqX,Y (1) = Iqgmi = Iqgmi X,Y . Our proposal X,Y  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, Iqgmi X,Y = 0.71 bpcu, and sqX,Y = 2.94. Figure 2.5 shows the plot of IqX,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 progressive 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.8 w/o i.i.d. channel adaptor w/ i.i.d channel adaptor  ′ (1) IqX,Y  0.7  Rate [bpcu] →  0.6  sum-product decoding  0.5 max-product decoding  0.4  0.3  0.2  0  2  4  6  8  10  12  14  c→  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 average 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 decoding 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 implementation, 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 signadjusters 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 channel 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 approximations 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 decoding rule, for which an achievable rate is given by the GMI Iqgmi X,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  I(X; Z)  x∈X  pY |X (y|x)  y∈Y  ΛqB0 ,Y (y), . . . , ΛqBm−1 ,Y (y) z ∈ Rm  (a)  I(Bi ; Z)  pY |X (y|x)  y∈Y  bi (x) ∈ B  ΛqB0 ,Y (y), . . . , ΛqBm−1 ,Y (y) z ∈ Rm  (b)  I(Bi ; Zi )  pY |X (y|x) bi (x) ∈ B  y∈Y  ΛqBi ,Y (y)  (c)  zi ∈ R  I(Bi ; Ri )  pY |X (y|x)  y∈Y  ΛqBi ,Y (y), {ΛqBj ,Y (y)} ri ∈ R m i  bi (x) ∈ B  (d)  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 m−1  I(X; Z) =  I(Bi ; Z|B0 , . . . , Bi−1 ) .  (2.29)  i=0  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)  ≥ Iqgmi . B ,Y  (2.32)  i  The mutual information I(Bi ; Z) in (2.30) represents the constrained channel capacity, i.e. the maximum achievable rate with a given input distribution, 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, however, 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 capacity 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 Iqgmi Bi ,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 = 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: m−1  Iqgmi ≤ X,Y  m−1  Iqgmi ≤ B ,Y i  i=0  m−1  ≤  i=0  I(Bi ; Z) ≤  m−1  I(Bi ; Zi ) ≤  i=0  m−1       I(Bi ; Ri ) i=0  I(Bi ; Y ) i=0     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 transmission 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 correction 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)  pZi |Bi (zi |0) pZi |Bi (zi |1)  (2.37)  Finally, the scalar metric correction  ΛpZi |Bi (zi ) = ln  leads to I(Bi ; Zi ). Since metrics (2.35), (2.36), and (2.37) match to their corresponding 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 bitmetric 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  ΛqB ,Y (y) = sqX,Y ΛqBi ,Y (y)  m−1 gmi Iqgmi ≤ X,Y i=0 IqBi ,Y is achievable. Shift the critical point of the BICM I-curve to 1, aim to improve the performance of sumproduct SBS decoding.  Scale LLRs differently by factors ci = sqBi ,Y /s∗ for some s∗ > 0:  Binary I-curves are aligned at s∗ . The BICM GMI is Iqgmi =  Original mismatched LLR ΛqBi ,Y (y) Scale all LLRs by the same factor c = sqX,Y : i  X,Y  m−1 gmi i=0 IqBi ,Y  ΛqB ,Y (y) = (sqBi ,Y /s∗ )ΛqBi ,Y (y)  . Choose s∗ = 1 in sum-product SBS decoding.  Apply scalar metric mismatch correction:  Bit metrics are matched to the cascaded channels Bi → Zi . The BICM GMI is m−1 i=0 I(Bi ; Zi ).  i  Λpi |Bi (zi ) = ln  pZi |Bi (zi |0) pZi |Bi (zi |1)  Apply reduced-dimensional vector metric mismatch correction: ΛpRi |Bi (ri ) = ln  pRi |Bi (ri |0) pRi |Bi (ri |1)  Apply optimal vector metric mismatch correction: ΛpZ|Bi (z) = ln  pZ|Bi (z|0) pZ|Bi (z|1)  Bit metrics are matched to the cascaded channels Bi → Ri . The BICM GMI is m−1 i=0 I(Bi ; Ri ).  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 relevant 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 Gaussian noise (AWGN) channel with hard detection. We apply binary reflected Gray labeling with [b0 b1 b2 ] = [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  [b0 b1 b2 ] = [000]  [100]  [110]  [010]  [011]  [111]  [101]  [001]  Figure 2.7: 8-ASK constellation and labeling. Iqgmi X,Y =  2  I(Bi ; Y ) = 1.50 bpcu, and I(X; Y ) = 1.56 bpcu. Hard detection i=0  that produces LLRs +1 and −1 leads to the GMI Iqgmi X,Y = 1.07 bpcu, which 2  is the maximum of the BICM I-curve IqX,Y (s) = 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 Z2 Z0 Z1 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.25  0.55  0.2  Binary I-curve [bpcu] →  Binary I-curve [bpcu] →  0.5  0.15  0.1 matched hard Z , Z Z , Z Z , or Z Z Z 0  0.05 0.5  0 1  1  0 2  0.45 0.4 0.35 0.3  matched hard Z1 or Z1Z2  0.25  Z Z or Z Z Z  0 1 2  1.5  1 0  0.2 0.5  2  1  1.5  s→ (b) level 1  0.8  1.6  0.75  1.4 BICM I-curve/Throuhgput [bpcu] →  Binary I-curve [bpcu] →  2.5 s→  (a) level 0  0.7 0.65 0.6 matched hard Z  0.55  2  0.5  Z Z  2 0  Z Z  2 1  0.45  Z Z Z  2 0 1  0.4 0.5  1 0 2  2  1  1.5  2  2.5  3  1.2  1  0.8 matched hard scalar (Z +Z +Z )  0.6  0  1  0  0.4 0.5  1  1.5  s→ (c) level 2  2  optimum (Z + Z Z + Z Z Z ) 1 0  2 0 1  2  2.5 s→  (d) BICM  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 subfigures). 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 Z2 Z0 and Z2 Z1 , respectively. Since I(B2 ; Z2 Z0 ) < I(B2 ; Z2 Z1 ), 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 interesting 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 phenomena 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 knowledge 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 corrections 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 throughput is shown in Figure 2.8(d) (markers without lines). We observe that the throughput closely follows the associated GMIs if metric-mismatch correction 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 significantly 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 noncoherent detection is attractive due to its low complexity detector implementation. 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 channel 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 nonzero element of x.  37  2.4. Applications Metrics The matched LLR metric for noncoherent orthogonal modulation is Λmatched (y) = ln i  = ln  pY |Bi (y|0) pY |Bi (y|1) I0  2a|ye (x)| N0  I0  2a|ye (x)| N0  x∈Xi0  x∈Xi1  ,  (2.40)  The popular max-log LLR metric is Λimax−log (y) = max ln I0 x∈Xi0  2a|ye (x)| N0  − max ln I0 x∈Xi1  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 Λimax−log (y) = ln I0  2a max |ye (x)| N0 x∈Xi0  − ln I0  2a max |ye (x)| N0 x∈Xi1  . (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α / 2πα and ln I0 (α) can be approximated α. From (2.42), this approximation leads to a new LLR Λa−max−log (y) = i  2a N0  max |ye (x)| − max |ye (x)|  x∈Xi0  x∈Xi1  .  (2.43)  38  2.4. Applications  12 α2 4  10  α  8  6  ln(I0 (α))  4  2  0 0  2  4  6  8  10  12  α→  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−log (y) = i  a2 N02  max |ye (x)|2 − max |ye (x)|2  x∈Xi0  x∈Xi1  .  (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 a2 /N02 in (2.44), we have the  39  2.4. Applications parameter-free metrics Λpf−a−max−log (y) = max |ye (x)| − max |ye (x)| , i  (2.45)  Λpf−ps−max−log (y) = max |ye (x)|2 − max |ye (x)|2 . i  (2.46)  x∈Xi0  x∈Xi0  x∈Xi1  x∈Xi1  Both channel gain and noise power estimation are not needed in the calculation 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 metric (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 I40  2.4. Applications  6  M = 64  5  M = 16  Rate [bpcu] →  4 3  M =4 2 1 0  GMI, matched metric GMI, mismatched metrics 3  4  5  6  7  8  9  10  11  12  SNR [dB] →  (a) AWGN channel 6  M = 64 5  M = 16  Rate [bpcu] →  4 3  M =4  2 1 0  GMI, matched metric GMI, mismatched metrics 5  10  15  20  SNR [dB] → (b) Rayleigh fading channel  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 maxlog (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 Icurve, 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 tradeoff 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 results are also included in Figure 2.11. Mismatched metrics attain a throughput 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  2  1.86  1.86  1.86  1.34  1.34  1.34  1  1  1  0.5  0.1  0.19  0.3  Sum−product  0.5 0.5  1  0.5  0 1  Sum−product w/ scaling  pf-a-max-log  matched  2.5  pf-ps-max-log  Rate [bpcu] →  2  max-log  2.5 ps-max-log  2.5  a-max-log  2.4. Applications  3.5  6.6  Max−product  s→  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 lowcomplexity option for noncoherent orthogonal modulation. We note an exception 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  1.5  1.5  1.5  1  1  1  Rate [bpcu] →  2  0.086  0.15  0.5  Sum−product  0.5  1  0.5  Sum−product w/ scaling  1  pf-a-max-log  2.5  2  0.5 0.05  pf-ps-max-log  matched  max-log  2.5  ps-max-log  2.5  a-max-log  2.4. Applications  4.4 6.3 Max−product  s→  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, resulting 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 photoncounting channel model [61], by which the received vector is y = [y0 . . . yM −1 ] and yi = xi ai + 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 ) = and p(y|x) =  (λs xi + λb )yi exp (−[λs xi + λb ]) , yi !  M −1 i=0 p(yi |xi ).  (2.48)  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  1+  λs λb  1+  λs λb  x∈Xi0  x∈Xi1  yo (x)  yo (x)  .  (2.50)  The simplified max-log metric is  ΛqBi ,Y (y) =  max yo (x) − max yo (x) ln 1 +  x∈Xi0  x∈Xi1  λs λb  ,  (2.51)  which has considerably lower computational complexity than (2.50).  45  2.4. Applications  6  5  Rate [bpcu] →  4  3  2  GMI, matched GMI, max−log Iq (1), max−log  1  X,Y  0 −10  −9  −8  −7  −6  −5  −4  −3  −2  10 log10 (λs /(M λn )) [dB] →  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 applied 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 64PPM 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 applied 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 metric, 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 scaling. 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 metricmismatch correction uses the example considered in [24, Sec. IV]. The transmission system is a 2 × 2 multiple-input multiple-output (MIMO) system with 16-ary quadrature amplitude modulation (16-QAM) and Rayleigh fading 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  2.4  matched  I-curve / Throughput [bpcu] →  2.2  max−log  2  1.8  1.6  scaled max−log  1.4  sum−product max−product  1.2 0.2  0.4  0.6  0.8  1  1.2  1.4  s→  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 bullet 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 listbased 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) performance 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 interpolation (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  level 1 0.65  Rate [bpcu] →  0.6 0.55  matched clipped max−log  0.5 0.45  scaled scalar correction  level 0  hybrid  0.4 0.35 0.3 0.5  1  1.5  2 s→  (a) 4.4  matched clipped max−log scaled scalar correction hybrid  4.2  Rate [bpcu] →  4 3.8 3.6 3.4 3.2 0.5  1  1.5  (b)  2 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 “hybrid” are numerically on top of each other.  50  2.4. Applications  4  output LLR  2  0  −2  −4  linearly scaled scalar correction hybrid −2  −1  0  1  level 0  2  input LLR  output LLR  4 2  0 −2  linearly scaled scalar correction hybrid  −4 −2  −1  0  1  2 input LLR  level 1  Figure 2.16: Metric manipulations for 2 × 2 MIMO transmission with 16QAM 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:  ΛqB ,Y (y) = i     ln pZi |Bi (zi |0) , if zi = ±2 p (zi |1) Zi |Bi    ci zi ,  (2.52)  otherwise .  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 manipulations 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 correction methods, including a previously proposed scalar correction. We presented 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 correction approaches.  53  Chapter 3  Multilevel Coding: Reduced-Layer, General Decoding Metrics, and Rateless Transmission MLC enables the combination of binary ECC with multilevel constellations [4, 5]. It can achieve the same rate as coded transmission with nonbinary codes. In comparison, BICM also combines binary ECC with multilevel 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. Examples of such cases are multiple-input multiple-output (MIMO) signaling and orthogonal modulation. In this chapter, we present a number of contri54  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 encoderdecoder 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 2 We would like to stress the difference between “level” and “layer.” Each level corresponds 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. 3 Henceforth, without further clarification, by “MLC” we to refer to the general RLMLC 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. according to the capacity design rule [5, Sec. IV-A]. Secondly, for transmission over time-varying channels, rateless codes seamlessly adapt to the instantaneous 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 decoding 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 socalled 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  E2  E1  E0  b2  b1  D2  MAP  x  channel  b0  y  D1  D0  ˆb2  ˆb1  ˆb0  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 ˆb0 (the estimated value b0 ). Finally, in the third stage, estimation of b2 is based on y, ˆb0 , and ˆb1 . 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  E1  b1 , b2  D1  MAP E0  x  channel  ˆb1 , ˆb2  y  b0  ˆb0  D0  (a) E1  b2  D1  MAP E0  x  channel  b0 , b1  ˆb2  y D0  ˆb0 , bˆ1  (b)  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 expressed in terms of the achievable rates of the layers. Applying this result, we then focus on the transmission over each MLC layer and provide expressions for the per-layer GMI. Based on these expressions, we propose metricmismatch 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 kth 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 (mk N , Rk ) of length mk N > 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] κ−1  P ≤  k=0  κ−1  Pk ≤  k  = .  (3.1)  k=0  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 assumptions about detection rules being matched to the channel transition probabilities, it can be applied to mismatched decoding in the layers. Secondly, Theorem 3.1 allows us to consider each layer separately without concerning 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  ...  vκ−1  ...  Eκ−1  MAP  v1  E1  x  v0  E0  (a) Transmitter  ...  Dκ−1  y D1  D0  vˆ0  u ˆκ−1  vˆ1  u ˆ1 = vˆ0  (b) Receiver  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 corresponding 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 ΛqB ,Y,Dˆ (y, d) i  i  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,Uˆk (b, y, u). The layer metric is defined as qVk ,Y,Uˆk (v, y, u) =  qBi ,Y,Uˆk (b, y, u) ,  (3.4)  i:hi =k  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 ˆ i , and Uk instead of U ˆk . For the i-th level and bit is, we use Di instead of D metric qBi ,Y,Di (b, y, d), the binary I-curve is defined as  −EBi ,Y,Di  IqBi ,Y,Di (s)  = −EX,Y  log  pBi (b) b∈B  log  pBi (b) b∈B  qBi ,Y,Di (b, Y, Di ) qBi ,Y,Di (Bi , Y, Di )  s  qBi ,Y,Di (b, Y, di (X)) qBi ,Y,Di (bi (X), Y, di (X))  (3.5) 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, Iqgmi B ,Y,D i  i  max IqBi ,Y,Di (s) . s>0  (3.8)  For matched metrics, i.e., when qBi ,Y,Di (b, y, d) is proportional to the transition 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   s  qVk ,Y,Uk (v, Y, Uk ) pVk (v) IqVk ,Y,Uk (s) −EVk ,Y,Uk log  q Vk ,Y,Uk (Vk , Y, Uk )  v∈B|Vk |   s  qBi ,Y,Di (v, Y, uk (X)) pVk (v) = −EX,Y log . (3.9)  qBi ,Y,Di (vk (X), Y, uk (X))  |V | v∈B  k  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) =  IqBi ,Y,Di (s) .  (3.10)  i:hi =k  The layer GMI is the peak value of this layer I-curve, Iqgmi V ,Y,U k  k  max IqVk ,Y,Uk (s) . s>0  (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 I gmi (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 κ−1  I gmi =  k−1  mk I gmi  .  mi  (3.12)  i=0  k=0  Thus, we only need to obtain at most m binary GMI values I gmi (0), . . . , I gmi (m − 1) in order to calculate the GMI of any MLC configuration. We consider 128-PPM (hence m = 7) with background radiation λb = 0.2 photons/slot and matched LLR pY |X (y|x) ΛqB ,Y,Dˆ (y, d) = ln i  x∈Xdd,0,i i  pY |X (y|x)  i  ,  (3.13)  x∈Xdd,1,i i  λs λb  ye (x)  λs 1+ λb  ye (x)  1+ = ln  x∈Xdd,0,i i  x∈Xdd,1,i  ,  (3.14)  i  where the notation Xdd,0 (Xdd,1 ) denotes the set of x that has the labeling i ,bi i ,bi 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  7  Rate [bpcu] →  6  5  4  3  Conventional MLC (7 layers) BICM (1 layer) 2−layer MLC 3−layer MLC  2  1 −12  −11  −10  −9  −8  −7  −6  −5  10 log10 λs /M [dB] →  Figure 3.4: GMI of conventional MLC, BICM, and 2-layer MLC for 128PPM 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 ΛqB ,Y,Dˆ (y, d) i  i  (3.15)  can be applied to improve the GMI and throughput performance with sumproduct 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 description, 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 correction 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 message bits and continuously produces coded bits, which are mapped to transmit 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 become available to the decoder immediately after each received symbol, as in rateless BICM. However, at any upper layer k > 0, the decoder collects symbol 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 accumulated 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  Eκ−1  MAP  ...  ...  Eκ−2  x  E0  (a) Transmitter Dκ−1 Dκ−2  decoded data  ...  Bit Metric Calculation  ...  y  D0  (b) Receiver  Figure 3.5: Rotation rateless MLC transmitter and receiver. Stream redirection 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 layer κ − 1 layer κ − 2 ... layer 1  ...  ...  layer 0 ℓ[t − 1] ℓ[t − (κ − 1)]  ℓ[t]  ℓ[t − (κ − 2)]  time  (a) Cκ−1  Cκ−2  ...  C1  C0  (b)  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 decoder 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, during 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 segmentwise 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 information. Therefore, at the start of the transmission session, the transmitter sends some preamble data that is known to the receiver in the corresponding 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., κ−1  θ[t] = 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 elaborate 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 statespace equation n[t + 1] = An[t] + bν[t] , with       A=     0 .. .  1 .. .  ... .. .  0 .. .  0  0  ...  1  − CCκ−1 0  − CCκ−2 0  C1 . . . −C 0    (3.17)    0 .. .                 and b =  .    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)−1 b = where  e  e 1(κ−1)×1  ,  (3.19)  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 +  Cκ−1 κ−1 C1 −1 C2 −2 z + z + ... + z . C0 C0 C0  (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 +  C1 −1 C0 z ,  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. C1 −1 2 −2 • κ = 3: U (z) = 1 + C z +C C0 z , and the two roots r1,2 = 0  1 2C0 (−C1 ±  C12 − 4C0 C2 ) 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  1 0.9 0.8 0.7  ℓ[t]/K →  0.6 0.5 0.4 0.3 0.2 0.1 0 0  10  20  30  40  50  t→  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] .  (3.22)  t=τ  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 κ−1 κ−1  Ibeginning =  k=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 κ−1 κ−1  Iend =  Cj k=1 j=k  ν¯[τ ] . 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 τ +T +κ−2  Istructural loss = C  t=τ  τ +T +κ−2  [t] −  ν[t] + Ibeginning − Iend .  t=τ  (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  { ˆ[τ ] . . . ˆ[τ + T − 1]} = argmin  [t] t=τ  subject to: κ−1 k=0 Ck  [t − k] ≥ ν[t],  ∀ t ∈ [τ, τ + T + κ − 2],  [τ − (κ − 1)] . . . [τ − 1]  T  (3.27)  = n[τ ],  [τ + T ] = . . . = [τ + T + κ − 1] = ν¯[τ ]/C, [t] ≥ 0 . 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 approximates the simulation result of a Raptor code from [69, Fig. 6]. We 79  Structural loss  θ¯ − ν¯ → K  3.3. Rateless Multilevel Coding  0.03  0.02  0.01  0  Structural loss  θ¯ − ν¯ → K  0  2  4  6  8  10  12  14  16  18  20  T →  0.04  0.03  0.02  0.01 0.96  0.98  1  1.02  1.04  1.06  ℓmin →  1.08  1.1  1.12  1.14 K × C  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 reduce 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 channels, 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 amplitude 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 multidimensional 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 received 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  8 4-QAM 4-Tx  7  6  Rate [bpcu] →  5 4-Rx  4  3 I(X;Y) GMI, BICM GMI, 2−layer MLC Throughput, BICM Throughput, 2−layer MLC  2 2-Rx  1  0  2  4  6  8  10  12  14  16  18  20  10 log10 Er /N0 [dB] →  Figure 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. 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  7  6  Rate [bpcu] →  5  4  3 I(X;Y) GMI, BICM GMI, 2−layer MLC GMI, layer 0 GMI, layer 1 Throughput, BICM Throughput, w/o control Throughput, w/ control  2  1  0  6  7  8  9  10  11  12  10 log10 Er /N0 [dB] →  (a) AWGN channel  7  6  Rate [bpcu] →  5  4  3 I(X;Y) GMI, BICM GMI, 2−layer MLC GMI, layer 0 GMI, layer 1 Throughput, BICM Throughput, w/o control Throughput, w/ control  2  1  0  6  8  10  12  14  16  18  20  10 log10 Er /N0 [dB] →  (b) i.i.d. Rayleigh fading channel  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 signaling with noncoherent detection. The channel model is described in Section 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 recall 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 environments. 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 autoregressive (AR1) model gi = αgi−1 +  1 − α 2 wi ,  (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  7  6  Rate [bpcu] →  5  4  3  2  1  0  Average MLC GMI Average BICM GMI R[t]  10  20  30  40  50  60  70  t→  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 ye (x) − max ye (x) ln 1 + x∈Xdd,0,i i  x∈Xdd,1,i i  λs λb  .  (3.31)  87  3.4. Applications  layer 1 2  1.8  Rate [bpcu] →  1.6  layer 0 1.4  1.2 Matched Max−log Scaled max−log  1  0.55  0.75  1  1.5  s→  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 Icurve 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 rotational 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 contribution 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 Section 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 remarkably improved over the past decade, bridging its enormous capacity to endusers remains a difficult challenge. Existing copper wires and wireless LAN technologies cannot handle the data rate necessary to deliver modern highdefinition multimedia in real time, whereas coaxial cables and fiber optics  91  4.1. Rateless Hybrid FSO-RF for Last-Mile Access  mapper 1  channel 1  detector 1  E  D mapper 2  transmitter  channel 2  detector 2  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 challenge.” 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 reliability 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 dramatically 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 diversity [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. Cor92  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 independent 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 2  P ≤ Mρ  i=1    EXi ,Yi    pXi (xi ) xi ∈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−N E  r (R)  ,  (4.2)  with R  log M , N  (4.3)  the random coding exponent E r (R)  max max E 0 (ρ, s) − ρR ,  0≤ρ≤1 s>0  (4.4)  93  4.1. Rateless Hybrid FSO-RF for Last-Mile Access and the generalized Gallager function of the diversity channel E 0 (ρ, s)  η1 Eq0X  1 ,Y1  (ρ, s) + η2 Eq0X  2 ,Y2  .  (4.5)  In (4.5), Eq0X ,Y (ρ, s), i = {1, 2} is the generalized Gallager function of i  i  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 I gmi  max I(s) , s>0  (4.6)  and I(s) = η1 IqX1 ,Y1 (s) + η2 IqX2 ,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 rate4 of channel i, we can also define the I-curve of the diversity channel as  I(s) = r1 IqX1 ,Y1 (s) + r2 IqX2 ,Y2 (s) .  (4.8)  The GMI (4.6) is now measured in bits per time unit. Let Iqgmi Xi ,Yi be the individual GMI of channel i. Interestingly, from (4.6) 4  Or symbol rate, which is the inverse of the symbol period.  94  E  FSO mapper  FSO channel  FSO detector  RF mapper  RF channel  RF detector  transmitter  multiplexer  message bits  demultiplexer  4.1. Rateless Hybrid FSO-RF for Last-Mile Access  D  receiver  Figure 4.2: Rateless BICM hybrid FSO-RF communication system. and (4.8), it follows that I gmi = max r1 IqX1 ,Y1 (s) + r2 IqX2 ,Y2 (s) s>0  ≤ r1 max IqX1 ,Y1 (s) + r2 max IqX2 ,Y2 (s) s>0  s>0  = r1 Iqgmi + r2 Iqgmi . X ,Y X ,Y 1  1  2  2  That is, the GMI of the diversity channel is less than or equal to the baudrate weighted sum of the individual channels’ GMIs. Equality I gmi = r1 Iqgmi + r2 Iqgmi . X ,Y X ,Y 1  1  2  2  (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. 160  Throughput [Mbps] →  140  120  100  80  60  40 40  60  80  100  120  140  160  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  160 GMI Througput 140  Rate [Mbps] →  120  100  80  60  40  0  50  100  150  200  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 gmi varies from 0 to 1 bpcu. In particular, the FSO channel gain changes IFSO  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 gmi has an average SNR such that the GMI IRF 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  2.2  2.1 IFSO (s)  IRF (s)  Rate [bpcu] →  2  1.9  1.8  1.7  1.6  1.5 0.5  0.675  1  1.225  1.5  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 binary 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  5.2  Rate [bits/TRF ] →  5  Iscaled (s) I(s)  4.8  4.6  4.4  4.2 0.5  0.775  1  1.25  1.5  s→  Figure 4.6: BICM I-curve and coded throughput of hybrid (diversity) channel. throughput or power efficiency gains over the popular alternative PPM format? 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 efficiency [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 bandwidth 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 constellations 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. Sec102  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 ≤ n/2 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  <y,x>  .  (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 constellationconstrained channel capacity is  C(X ) =  1 I(X; Y ) [bits/slot] . n  (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 constellations 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. Included are the upper “OOK bound” τ = H(1/ρ) and the lower “PPM bound” τ = (log ρ)/ρ. With this figure, we are able to locate the parameters (n, w, M ) of MPPM constellations that offer both high power and bandwidth efficiencies. For example, if we want a transmission which requires ρ to be around 4.0 we could select one of the three constellations 104  4.2. Multipulse Pulse-Position Modulation  1 0.9 0.8 (11, 3, 128)  0.7 τ [bits/slot] −→  (13 3, 256) (12, 3, 128)  0.6 0.5  OOK bound τ = H(1/ρ)  0.4 PPM bound τ = log(ρ)/ρ  0.3 0.2 2  4  6  8  10  12  14  16  ρ −→  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 =  4.2.2  n w  = 165, 286, and 220, respectively.  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 )  (4.14)  subject to: X ⊂ U and |X | = M 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 pseudocode 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 ascent 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 annealing 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 distinct 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) log M . Surprisingly, all the search algorithms result in constellations that have similar value C(X ) (4.12). This suggests that in practice we can use the simplest algorithm, namely random search5 . Having the optimized 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. 5  We 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  0.65 0.6  C(X )  C(U )  Capacity [bits/slot] −→  0.55 0.5 4-PPM  0.45 0.4 0.35 0.3 0.25 3  4  5  6 γ [dB]  7  8  9  10  −→  Figure 4.11: Constrained channel capacity of MPPM constellations. Given X , the BICM GMI depends on the labeling L I  bicm  1 (L) = n  m−1  I(Bi ; Y ) .  (4.15)  i=0  Our goal is to find a labeling that maximizes I bicm (L). Due to the large search space and the high computational cost to estimate the objective function I bicm (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 1 Mimimize: fG (L) = M  M i=1  1 |N (xi )|  dH (bi , bj ) , xj ∈N (xi )  (4.16)  subject to: {bi ∈ {0, 1}m |i = 1, . . . , M } , 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 improvement 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 ˆ=L 2: Best-so-far labeling L 3: for t = 1 . . . N do 4: L = argmin {fG (L ) : L = S(L, i, j), i = j} i,j=0...M −1  5: 6: 7: 8: 9: 10: 11: 12: 13: 14:  if (fG (L ) < fG (L)) then L=L else Generate new random labeling L end if ˆ then if (fG (L) < fG (L)) ˆ L=L end if end for 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-tolow 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  0.6  0.5  Rate [bits/slot] −→  0.4  0.3 (a) (b) (c) (d) (e) (f) (g)  0.2  0.1  3  4  5  6  γ [dB]  7  8  9  10  −→  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 FSORF 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 mediumto-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 channels’ 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 considering 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 potentially yield better performances compared to MPPM’s main competing 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 problem 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 modulation,” 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: theoretical 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 Communications: Principles and Advances.  Springer, Dec. 2010.  119  Bibliography [8] A. Guill´en i F` abregas, 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´en i F`abregas, G. Caire, and F. Willems, “Bitinterleaved coded modulation revisited: A mismatched decoding perspective,” 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 ¨ ¨ vol. 47, environment,” Archiv Elektronik Ubertragungstechnik (AEU), 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 multipleantenna 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 coding 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. Apostolopoulos, “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 bandutilization 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 MIMOBICM 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 Commun., 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´en, P. Fertl, and G. Matz, “On the generalized mutual information 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 paritycheck codes under message-passing decoding,” IEEE Trans. Inf. Theory, 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 progressive 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. Commun., 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 algorithm 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 demodulators 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¨ olcskei, “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, “Correcting 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 bitinterleaved 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: McGrawHill, 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 Commun., Jul. 2006. [58] A. Guill´en i F` abregas and A. J. Grant, “Capacity approaching codes for non-coherent orthogonal modulation,” IEEE Trans. Wireless Commun., 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 decoding,” 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, “Optical 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 Algorithms.  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 Mary 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 Communications 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 effects of Reed-Solomon codes on multi-pulse PPM in optical communications,” 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 modulation 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 modulation 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 simulated 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 modulation,” IEEE Trans. Inf. Theory, vol. 49, pp. 307–313, Jan. 2003.  131  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0071660/manifest

Comment

Related Items