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

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
ubc_2011_spring_nguyen_trungthanh.pdf [ 1.4MB ]
Metadata
JSON: 1.0071660.json
JSON-LD: 1.0071660+ld.json
RDF/XML (Pretty): 1.0071660.xml
RDF/JSON: 1.0071660+rdf.json
Turtle: 1.0071660+rdf-turtle.txt
N-Triples: 1.0071660+rdf-ntriples.txt
Original Record: 1.0071660 +original-record.json
Full Text
1.0071660.txt
Citation
1.0071660.ris

Full Text

Binary-Coded Modulation andApplications in Free-Space OpticsbyTrung Thanh NguyenM.A.Sc., The University of British Columbia, 2006B.Eng., The University of Sydney, Australia, 2004A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)March 2011c Trung Thanh Nguyen 2011AbstractBinary-coded modulation techniques such as bit-interleaved coded modu-lation (BICM) and multilevel coding (MLC) are pragmatic methods toachieve both high power and bandwidth e ciencies in digital communi-cations. These techniques enable the combination of powerful and popularo -the-shelf binary codes with bandwidth-e cient multilevel signaling with-out considerable performance loss compared to joint coding and modulationdesigns. Today, binary-coded modulation has become almost universal indigital communication systems.This thesis concerns several aspects of binary-coded modulation and itsapplications. For BICM, we study the use of approximate decoding metricsto reduce detection complexity. Speci cally, we propose metric correctionfunctions which can improve achievable rates. We further propose a metricscaling which can improve throughput performance of symbol-by-symbol(SBS) decoding, which is the basis of state-of-the-art error-control codingsystems. To this end, we also discover an intriguing relationship betweenthe generalized Gallager function and the performance of sum-product SBSdecoding. For MLC, we develop the concept of reduced-layer coding thatfacilitates a trade-o between performance and structural complexity. Wethen propose a novel rateless MLC scheme which can seamlessly adapt toiiAbstractthe instantaneous channel quality and achieve throughput gains compared toBICM in a number of transmission scenarios. Finally, we apply binary-codedmodulation techniques to free-space optics (FSO). FSO is an interestingtransmission technology which has recently emerged as a low-cost solutionto a range of communication challenges. We consider advanced signalingschemes such as channel coding diversity with mismatched decoding metricsand multipulse pulse-position modulation (MPPM). Combined with binarycodes, these schemes are practical means to improve rate and reliability inFSO systems.iiiPrefaceThis thesis is based on work conducted at UBC Department of Electricaland Computer Engineering under the guidance and supervision of ProfessorLutz Lampe.Parts of this thesis have been published or submitted in the followingarticles and papers. Names of journals for articles under review are notshown.Journal articles1. (Part of Chapter 4) T. T. Nguyen and L. Lampe, \Channel codingdiversity with mismatched decoding metrics," under review, submittedJan. 2011.2. (Part of Chapter 3) T. T. Nguyen and L. Lampe, \Multilevel cod-ing with general decoding metrics and rateless transmission," underreview, submitted Nov. 2010, revised Feb. 2011.3. (Part of Chapter 2) T. T. Nguyen and L. Lampe, \Mismatched bit-interleaved coded noncoherent orthogonal modulation," IEEE Com-munications Letters, accepted Mar. 2011.4. (Part of Chapter 4) T. T. Nguyen and L. Lampe, \MPPM constel-ivPrefacelation selection for free-space optical communications," under review,submitted Aug. 2010.5. (Part of Chapter 2) T. T. Nguyen and L. Lampe, \Bit-interleavedcoded modulation with mismatched decoding metrics," IEEE Trans-actions on Communications, vol. 59, no. 2, pp. 437-447, Feb. 2011.6. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, \Coded mul-tipulse pulse-position modulation for free-space optical communica-tions," IEEE Transactions on Communications, vol. 58, no. 4, pp.1036-1041, Apr. 2010.7. (Part of Chapter 4) A. AbdulHussein, A. Oka, T. T. Nguyen, andL. Lampe, \Rateless coding for hybrid free-space optical and radio-frequency communication," IEEE Transactions on Wireless Commu-nications, vol. 9, no. 3, pp. 1615-1619, Mar. 2010.Conference papers1. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, \Rateless mul-tilevel coding and applications," in Proc. IEEE GLOBECOM, Hon-olulu, Hawaii, USA, Nov.-Dec. 2009.2. (Part of Chapter 3, 4) T. T. Nguyen and L. Lampe, \Coded pulse-position modulation for free-space optical communications," in Proc.IEEE ICC, Dresden, Germany, Jun. 2009.3. (Part of Chapter 4) T. T. Nguyen and L. Lampe, \Capacity-maximizedMPPM constellations for free-space optical communications," in Proc.CSNDSP, Graz, Austria, Jul. 2008.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 BICM with Mismatched Decoding Metrics . . . . . . . . . 62.1 Random Coding with A Given Decoding Rule . . . . . . . . 82.2 BICM and Mismatched Decoding . . . . . . . . . . . . . . . 112.2.1 Log-Likelihood Ratio . . . . . . . . . . . . . . . . . . 142.2.2 Independent Binary Channel Model . . . . . . . . . . 142.2.3 BICM and Binary I-curves . . . . . . . . . . . . . . . 15viTable of Contents2.3 Metric Manipulation . . . . . . . . . . . . . . . . . . . . . . . 162.3.1 Metric Scaling and GMI . . . . . . . . . . . . . . . . 162.3.2 Metric Scaling and Symbol-By-Symbol Decoding . . . 192.3.3 Cascaded Channel Model and Metric-Mismatch Cor-rection . . . . . . . . . . . . . . . . . . . . . . . . . . 262.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.4.1 Discrete Metrics and Metric Correction . . . . . . . . 322.4.2 Noncoherent Carrier-Modulated Orthogonal Signaling 362.4.3 Pulse-Position Modulation with Direct Detection . . 442.4.4 MIMO-QAM with Clipped Max-Log Metric . . . . . 472.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523 Multilevel Coding: Reduced-Layer, General Decoding Met-rics, and Rateless Transmission . . . . . . . . . . . . . . . . . 543.1 Reduced-Layer MLC . . . . . . . . . . . . . . . . . . . . . . 573.2 Multilevel Coding with General Decoding Metrics . . . . . . 593.2.1 Achievable Rates . . . . . . . . . . . . . . . . . . . . 593.2.2 Per-Layer Transmission and GMI . . . . . . . . . . . 613.2.3 Metric-Mismatch Correction . . . . . . . . . . . . . . 673.3 Rateless Multilevel Coding . . . . . . . . . . . . . . . . . . . 673.3.1 Encoding and Decoding . . . . . . . . . . . . . . . . . 683.3.2 Operation Analysis and Control . . . . . . . . . . . . 723.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 813.4.1 MIMO-QAM . . . . . . . . . . . . . . . . . . . . . . . 813.4.2 Noncoherent Carrier-Modulated Orthogonal Signaling 83viiTable of Contents3.4.3 Pulse-Position Modulation with Direct Detection . . 873.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904 Applications in Free-Space Optics . . . . . . . . . . . . . . . 914.1 Rateless Hybrid FSO-RF for Last-Mile Access . . . . . . . . 914.1.1 Channel Coding Diversity Model and Rate Analysis . 924.1.2 Numerical Examples . . . . . . . . . . . . . . . . . . 964.2 Multipulse Pulse-Position Modulation . . . . . . . . . . . . . 994.2.1 Constellation Selection . . . . . . . . . . . . . . . . . 1034.2.2 Subset Selection . . . . . . . . . . . . . . . . . . . . . 1054.2.3 Labeling and Binary-Coded Modulation . . . . . . . . 1094.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1145 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . 1155.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . 1155.2 Suggested Future Work . . . . . . . . . . . . . . . . . . . . . 117Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119viiiList of Tables2.1 BICM metric manipulation methods and their e ects. . . . . 31ixList of Figures2.1 Elements of a digital communication system. . . . . . . . . . 82.2 Example of the generalized Gallager function E0qX;Y ( ;s). . . 112.3 BICM transmitter and receiver. . . . . . . . . . . . . . . . . . 122.4 Shift the critical point of the I-curve by metric scaling. . . . . 172.5 Throughput achieved with a Raptor code over a BAC andSBS decoding with mismatched metrics versus the metric-scaling parameter c. . . . . . . . . . . . . . . . . . . . . . . . 242.6 BICM demodulator as part of a cascaded channel. . . . . . . 272.7 8-ASK constellation and labeling. . . . . . . . . . . . . . . . . 332.8 I-curves for 8-ASK transmission over the AWGN channel withmatched detection, hard detection, and di erent metric mis-match correction functions. . . . . . . . . . . . . . . . . . . . 342.9 Approximation to the function ln(I0( )). . . . . . . . . . . . . 392.10 BICM GMI of noncoherent orthogonal modulation. . . . . . . 412.11 BICM I-curve and coded throughput of 16-ary noncoherentorthogonal modulation over AWGN channel at SNR of 6:35dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43xList of Figures2.12 BICM I-curve and coded throughput of 16-ary noncoherentorthogonal modulation over Rayleigh fading channel at SNRof 8.5 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.13 BICM GMI for decoding with matched metric and max-logmetric, and IqX;Y (1) for max-log metric. 64-PPM transmis-sion over Poisson channel. . . . . . . . . . . . . . . . . . . . . 462.14 BICM I-curve and simulated rates for 64-PPM. . . . . . . . . 482.15 I-curves for a 2 2 MIMO transmission. . . . . . . . . . . . . 502.16 Metric manipulation functions for a MIMO transmission. . . 513.1 Example of conventional MLC. . . . . . . . . . . . . . . . . . 573.2 Two examples of reduced-layer MLC. . . . . . . . . . . . . . . 583.3 MLC transmitter and receiver. . . . . . . . . . . . . . . . . . 613.4 GMI of conventional MLC, BICM, and 2-layer MLC for 128-PPM over Poisson channel with  b = 0:2. . . . . . . . . . . . 663.5 Rotation rateless MLC transmitter and receiver. Stream redi-rection occurs at switching to a new interval. . . . . . . . . . 693.6 Information segments at the receiver. . . . . . . . . . . . . . . 703.7 Interval length ‘[t] of an unstable system. . . . . . . . . . . . 763.8 Model predictive control technique. . . . . . . . . . . . . . . . 793.9 Controlling structural loss in an unstable system. . . . . . . . 803.10 GMI and throughput of rateless MLC for 4-QAM MIMOtransmission with 4 transmit and 2 and 4 receive antennasover an i.i.d. Rayleigh fading channel. . . . . . . . . . . . . . 83xiList of Figures3.11 GMI and throughput of rateless MLC for M = 128 nonco-herent orthogonal modulation. . . . . . . . . . . . . . . . . . 843.12 Example of 2-layer rateless MLC over slow fading channel.The value R[t] approximates the average throughput duringtime interval t. . . . . . . . . . . . . . . . . . . . . . . . . . . 873.13 Layer I-curves of an 128-PPM MLC scheme. . . . . . . . . . . 884.1 Channel coding diversity scheme. . . . . . . . . . . . . . . . . 924.2 Rateless BICM hybrid FSO-RF communication system. . . . 954.3 Scatter plot of throughput vs. GMI for 1000 codewords overthe hybrid (diversity) FSO-RF scheme. . . . . . . . . . . . . . 964.4 Throughput and GMI during the transmission of 200 consec-utive codewords over the hybrid FSO-RF scheme. . . . . . . . 974.5 BICM I-curve of individual FSO and RF channels. . . . . . . 1004.6 BICM I-curve and coded throughput of hybrid (diversity)channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.7 Power-bandwidth e ciency chart of MPPM. Parameter setsare triplets (n;w;M). . . . . . . . . . . . . . . . . . . . . . . 1054.8 Pseudo-code for random search. . . . . . . . . . . . . . . . . . 1064.9 Pseudo-code for greedy ascent. . . . . . . . . . . . . . . . . . 1074.10 Pseudo-code for simulated annealing. . . . . . . . . . . . . . . 1084.11 Constrained channel capacity of MPPM constellations. . . . . 1104.12 Pseudo-code for Gray labeling search. . . . . . . . . . . . . . 1124.13 Constrained capacities or GMIs of an MPPM transmission. . 113xiiList of AbbreviationsASK Amplitude-Shift KeyingAWGN Additive White Gaussian NoiseBER Bit-Error RateBICM Bit-Interleaved Coded Modulationbpcu Bits Per Channel UseCWC Constant-Weight CodeECC Error-Control CodingFSK Frequency-Shift KeyingFSO Free-Space Optics or Free-Space Optical communicationsGMI Generalized Mutual InformationIM-DD Intensity Modulation with Direct DetectionLDPC Low-Density Parity CheckLLR Log-Likelihood RatioMIMO Multiple-Input Multiple-OutputML Maximum LikelihoodMLC MultiLevel CodingMPC Model Predictive ControlMPPM Multipulse Pulse-Position ModulationMSD MultiStage DecodingxiiiList of AbbreviationsMSL Minimum Segment LengthOOK On-O Keyingpdf Probability Density FunctionPPM Pulse-Position ModulationQAM Quadrature Amplitude ModulationRF Radio FrequencyRL-MLC Reduced-Layer MLCSBS Symbol-By-SymbolSNR Signal-to-Noise RatioTCM Trellis-Coded ModulationxivAcknowledgementsI wish to give my foremost gratitude to my supervisor, Prof. Lutz Lampe, forhis support throughout my years at UBC, for his guidance, and for believingin me and giving me the freedom to pursue di erent research directions. Hehas always expected the highest dedication and integrity from his students;and living up to his expectation has made me a better researcher.I wish to thank Profs. Robert Schober, Vincent Wong, Jane Wang, Vic-tor Leung, Cyril Leung, Vijay Bhargava, Nando de Freitas, Ozgur Yilmaz,and Ian Blake for being in my supervisory and examining committees. Iwould like to thank my external examiner, Prof. Lars Rasmussen, for hisenthusiasm and encouraging evaluation of my work.My special thanks to my colleagues for a warm and intellectually stimu-lating working environment. I would like to thank fellow scholars at GreenCollege for a special place I call home. I want to thank all friends for sharingthe ups and downs during all these years.As always, my deepest thanks to my family for their love and support.Vancouver, CanadaMarch 2011xvChapter 1IntroductionDigital communication has become an essential part of our daily lives. Thelast decade has seen an explosive growth in the number of communicationdevices and the volume of data tra c. This growth is likely to continueover the coming years. Today, cheaper, faster, and more environmentallyfriendly communication systems are in ever greater demand.The two primary resources of a communication system are channel band-width and transmit power [1]. Channel bandwidth utilization can often beincreased by using larger multilevel constellations. Transmit power require-ment can be minimized by error-control coding (ECC). However, non-binarycodes for multilevel constellations are usually harder to design and imple-ment, and thus binary codes are much more popular in practice. A prag-matic approach to achieve both high power and bandwidth e ciencies is tocombine binary ECC with multilevel constellation signaling. Bit-interleavedcoded modulation (BICM) [2,3] and multilevel coding (MLC) [4,5] are twopopular techniques that o er such a combination. In Chapter 2 and 3, wemake a number of contributions to the development of these techniques.Our contributions focus on the use of suboptimal designs and decoding met-rics which, with a small trade-o in the achievable rate, greatly reduce the1Chapter 1. Introductiondetection and decoding complexity. This complexity reduction can in turnbe exploited in several ways. For example, it can be translated into lowerhardware cost and consumption power, or into higher throughput for a givencomputational complexity constraint.Recently, free-space optics (FSO) has regained attention as a secure, lowcost, rapidly deployable, and license-free wireless connectivity, e.g. [6,7]. Weinvestigate this interesting communication technology in Chapter 4. Due tothe high frequency of optical waveform signal, practical FSO transmissionoften uses intensity modulation with direct detection (IM-DD) like  beroptics. However, unlike in the  ber medium, FSO signal su ers from fadingsimilar to radio-frequency (RF) signal in wireless communications. Thesecombined characteristics pose a unique technical challenge to achieve bothhigh rate and reliability with FSO. To address this challenge, we consider theuse of advanced signaling schemes and apply coding techniques developedin earlier chapters to FSO systems.Our contributions are organized as follows: Chapter 2 { BICM with Mismatched Decoding Metrics: BICM is cur-rently the de facto coding standard for digital communication. Re-cently, BICM has been cast as a mismatched decoding scheme due tothe assumption of independent bit metrics [8, 9]. In addition to thisinherent mismatch, practical demodulators may produce mismatcheddecoding metrics to reduce computational complexity. In this chapter,we investigate BICM with such metrics. In line with recent works onthis topic, we adopt the generalized mutual information (GMI) [10,11]2Chapter 1. Introductionas the pertinent performance measure. First, we show that level-dependent scaling of logarithmic bit metrics can improve the BICMGMI. Second, we consider the e ect of metric scaling on symbol-by-symbol (SBS) decoding, which is used in a number of modern capacity-approaching ECC systems. We propose a uniform metric scaling whichcan lead to an improved performance of mismatched sum-product SBSdecoding, even if the GMI is not changed. Third, we investigate gen-eral metric-mismatch correction functions and analyze their e ects interms of the GMI. We then provide extensive numerical evidence todemonstrate that our proposed metric manipulation methods can sig-ni cantly increase the performance of mismatched BICM. Chapter 3 { Multilevel Coding: Reduced-Layer, General Decoding Met-rics, and Rateless Transmission: MLC is the main contender to thecelebrated BICM technique for combining binary ECC with multilevelconstellations. Although MLC has a more complex encoding-decodingstructure, it can achieve a larger rate in a number of important sce-narios such as multiple-input multiple-output (MIMO) and orthogo-nal modulation transmission. In this chapter, we make three distinctcontributions to MLC. First, based on a previous work [12], we de-velop the concept of reduced-layer MLC (RL-MLC), which includesboth conventional MLC and BICM as special cases. This new conceptfacilitates a trade-o between achievable rates and MLC structuralcomplexity, which is measured by the number of decoding layers. Sec-ond, we present rate analysis and metric-mismatched correction for3Chapter 1. IntroductionMLC with general decoding metrics. This contribution is an exten-sion of the results for BICM from Chapter 2. Third, we considerthe combination of MLC with rateless codes, e.g. [13]. Such a com-bination eliminates the need to carefully design code rate for eachlayer. Furthermore, in slow fading environments, rateless coding canseamlessly adapt to the instantaneous channel quality and achieve anincreased average throughput compared to  xed-rate MLC transmis-sion. However, despite these great potential bene ts, we show that acareless combination of MLC and rateless coding would lead to sig-ni cant rate loss. Thus, we propose a novel rateless scheme whichpreserves the rate advantage of MLC over BICM. We provide relevantexamples with MIMO, noncoherent carrier-modulated orthogonal sig-naling, and IM-DD pulse-position modulation (PPM) to demonstratethat our scheme can achieve throughput gains compared to BICM ina variety of transmission scenarios. Chapter 4 { Applications in Free-Space Optics: In the  rst half ofthis chapter, in light of results from Chapter 2, we revisit the ratelessBICM scheme with hybrid FSO-RF transmission [14]. Hybrid FSO-RFis an example of channel coding diversity [15]. The use of an RF linkin conjunction with the FSO link is promising to improve communica-tion reliability because these links are complementary in a wide varietyof weather-induced fading conditions. We show a new achievable rateanalysis for channel coding diversity with general decoding metrics.We then demonstrate the applicability of our analytical result in rele-4Chapter 1. Introductionvant examples. In the second half of this chapter, we design a balancedpower-bandwidth e cient modulation format for FSO. Currently, thetwo most popular FSO signaling formats are on-o keying (OOK) andpulse-position modulation (PPM). OOK is more bandwidth-e cient,but it has several drawbacks such as the need to select an appropriatedecision threshold at the receiver and more complex synchronization.PPM, on the other hand, is more power-e cient, but its bandwidth ef- ciency rapidly declines with increasing constellation size. We considermultipulse pulse-position modulation (MPPM) [16] as an alternativemodulation for FSO. It is a generalization of PPM with more than onepulse per symbol. We design decimated MPPM constellations that aresuitable for combining with binary codes and have both high powerand bandwidth e ciencies.Concluding remarks are given in Chapter 5. Chapter 2 is self-containedand can be read independently of the other chapters.5Chapter 2BICM with MismatchedDecoding MetricsBICM is a technique to combine binary ECC with multilevel constellations.Invented in 1992 by Zehavi [2], it has become the de facto coding standardfor modern digital communication systems. The key advantages of BICMare its excellent performance and its  exibility in allowing separate code andmodulation 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 beencast as a mismatched decoder [10, 11] and the GMI [10] has been used asa performance measure. This new perspective readily enables the studyof BICM with mismatched demodulators, that is, when a twofold mismatchoccurs. The  rst mismatch is due to the assumption of independent bit met-rics and is inherent to BICM. The second mismatch occurs because of someapproximation in the computation of bit metrics. The use of approximatemetrics is common in practice to reduce detection and decoding complexity,e.g. [17{23]. Following this direction, Jald en et al. [24] have recently de-vised and analyzed a metric correction method for BICM with mismatcheddemodulation.6Chapter 2. BICM with Mismatched Decoding MetricsIn this chapter, we extend this new line of work. In particular, we studythe manipulation of mismatched bit metrics to improve the performance ofBICM. We start in Section 2.1 by  rst revisiting the concept of randomcoding and introducing the \I-curve," whose maximum is the GMI. In Sec-tion 2.2, we establish that the BICM I-curve is equal to the sum of thebinary I-curves of the levels. This relation suggests that the GMI of BICMcan be increased by aligning the binary I-curves so that their peaks areadded in a totally constructive manner. In Section 2.3.1, we show that thisalignment can be achieved by scaling the log-likelihood ratio (LLR) metricswith suitable constant factors. In Section 2.3.2, we investigate the e ect ofmetric 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 asrepeat-accumulate [25], low-density parity check (LDPC) [26{31], and Rap-tor codes [13, 32, 33]. Based on the properties of the I-curve, we proposea scaling rule which can lead to rate improvements in sum-product SBSdecoding, even if the GMI remains unchanged. Finally, in Section 2.3.3,we consider the BICM demodulator as part of a cascaded channel. Thispoint of view naturally leads to metric correction methods that increasethe BICM GMI, including the scalar function used in [24], and new vectorfunctions which provide di erent performance-complexity trade-o s. Usingfour speci c application examples in Section 2.4, we provide extensive nu-merical evidence that the proposed metric manipulations can improve theperformance of mismatched BICM.72.1. Random Coding with A Given Decoding Rule2.1 Random Coding with A Given DecodingRuleA digital communication system can be divided into the transmitter, thechannel, and the receiver as illustrated in Figure 2.1.x channelpY|X(y|x)y receivertransmitterdecodedbitsmessagebitsFigure 2.1: Elements of a digital communication system.We consider a discrete-time memoryless channel whose random inputand output variables are denoted X and Y, respectively. Input symbolsare drawn from the discrete alphabet X with the probability mass functionpX(x). The discrete or continuous output alphabet is denotedY. The chan-nel can be fully described by the transition probability function pYjX(yjx).At the receiver, given the received symbol y 2Y, a symbol metric of thegeneral form qX;Y (x;y) can be calculated for each x2X. We assume thatqX;Y (x;y) > 0, 8x 2 X; y 2 Y. Consider a code with the codebook Cthat consists of M length-N codewords x = [x0:::xN 1]. Each codewordin C is equally likely chosen for transmission. Given the received sequencey = [y0:::yN 1], for each codeword x2C, the word metric is calculated asqX;Y (x;y) =N 1Yk=0qX;Y (xk;yk) : (2.1)82.1. Random Coding with A Given Decoding RuleThe decoder output is determined by^x = argmaxx2CqX;Y (x;y) : (2.2)The symbol metric qX;Y (x;y) is called a matched metric if it is propor-tional to the channel transition probability pYjX(yjx). It is called a mis-matched metric otherwise [10, 11]. With matched metrics, (2.2) coincideswith the maximum-likelihood (ML) decoding rule and, since all codewordsare equally likely, becomes^x = argminx2C 1 pXjY (xjy) :That is, it minimizes the word error probability [34, p. 120].The word error probability, averaged over all codewords and randomcodebook realizations, can be upper-bounded by [34, Ch. 5], [10, Sec. 2], [8,Sec. 3.1.2], cf. [35]P  M EX;Y( Xx2XpX(x) qX;Y (x;Y)qX;Y (X;Y) s! )N(2.3)for all 0   1 and s> 0. Alternatively,P  2 NErqX;Y (R); (2.4)where R, logMN (notation log( ) denotes logarithm with base 2) is the coderate,ErqX;Y (R) , max0   1 maxs>0 E0qX;Y ( ;s)  R (2.5)92.1. Random Coding with A Given Decoding Ruleis the random coding exponent, andE0qX;Y ( ;s) , logEX;Y( Xx2XpX(x) qX;Y (x;Y)qX;Y (X;Y) s! )(2.6)is the generalized Gallager function. If ErqX;Y (R) > 0, the error probabilityvanishes with increasing N and the rate R is said to be achievable. Themaximum achievable rate that can be inferred from (2.5) and the propertiesof the generalized Gallager function E0qX;Y ( ;s), cf. [34, Theorem 5.6.3], isthe GMI, which is de ned as [10]IgmiqX;Y , maxs>0 IqX;Y (s) ; (2.7)withIqX;Y (s) , @E0qX;Y ( ;s)@       =0= lim !0 E0qX;Y ( ;s) = EX;Y(logXx2XpX(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 metricqX;Y (x;y). The peak value of the I-curve is the GMI. Figure 2.2 illustratesa typical picture of the generalized Gallager function E0qX;Y ( ;s). The I-curve is the intersection of the plane  = 1 and the surface which is tangentto the generalized Gallager function at  = 0. With matched metrics, theline E0qX;Y ( ; 11+ ) is the conventional one-dimensional Gallager function,102.2. BICM and Mismatched Decodingtangent surfaceGMI I−curvegeneralizedGallager functionsρFigure 2.2: Example of the generalized Gallager function E0qX;Y ( ;s).the I-curve peaks at s = 1, and the GMI is the average mutual informationI(X;Y) [34, Ch. 5], which isI(X;Y) = EX;Y(logXx2XpX(x) pYjX(Yjx)pYjX(YjX)): (2.9)2.2 BICM and Mismatched DecodingWe now focus on the BICM scheme [3, 8], whose transmitter and receiverare presented in Figure 2.3. The BICM transmitter consists of a binaryencoder and a mapper (or modulator) which maps coded bits into transmitsymbols. The BICM receiver consists of a detector (or demodulator) and abinary decoder. The detector produces bit metrics for the binary decoder.112.2. BICM and Mismatched Decodingdecodedbitsy binarydecoderdetectorbitmetricsbinaryencodercoded bits mappermessagebits xBICM transmitterBICM receiverFigure 2.3: BICM transmitter and receiver.We note that, despite the \bit-interleaved" part in the name of BICM, bitinterleaving is immaterial for the random coding argument [9] and also notneeded 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 mbinary random variables for the labeling bits of the transmit symbol. Fur-thermore, let bi(x) be the i-th bit in the label of symbol x. The probabilitymass functions pBi(b), b2B,f0;1g, and pX(x), x2X, are related bypBi(b) =Xx2XbipX(x) ; (2.10)1When using LDPC codes, for example, bit interleaving is equivalent to re-orderingthe columns of the parity-check matrix, which does not a ect the decoding outcome.122.2. BICM and Mismatched Decodingwhere Xbi ,fx2X : bi(x) = bg, andpX(x) =m 1Yi=0pBi(bi(x)) : (2.11)Instead of directly producing 2m symbol-metric values for each possibletransmit symbol x given the received symbol y, the BICM detector produces2m bit-metric values corresponding to the m levels. Bit metrics for the i-thlevel have the general form qBi;Y (b;y). We assume qBi;Y (b;y) > 0, 8b2B,8y2Y. The BICM symbol metric is then calculated asqX;Y (x;y) =m 1Yi=0qBi;Y (bi(x);y) : (2.12)Even if qBi;Y (b;y) matches to the binary-input channel with input Biand output Y, i.e., it is proportional to the transition probabilitypYjBi(yjb) =Xx2XbipYjX(yjx)pX(x) ; (2.13)the BICM symbol metric (2.12) still does not match to the channel with in-put X and output Y. Therefore, BICM is inherently a mismatched decodingscheme [8,9].132.2. BICM and Mismatched Decoding2.2.1 Log-Likelihood RatioThe 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 su cient statistics for Bi given qBi;Y (b;y) (notation ln( ) de-notes the natural logarithm). Conventionally,  qBi;Y (y) is the log-likelihoodratio (LLR) only when qBi;Y (b;y) is proportional to the likelihood pYjBi(yjb).However, for convenience and brevity, we will refer to  qBi;Y (y) as an LLReven when qBi;Y (b;y) is not proportional to pYjBi(yjb).2.2.2 Independent Binary Channel ModelThe classical approach to analyze BICM is to use the independent binarychannel model [3], in which transmission is performed in m parallel channelswith inputs Bi, i = 0;:::;m 1, and output Y. This model is equivalent tomultilevel coding (MLC) with parallel decoding of levels [5]. For level i andits bit metric, the binary generalized Gallager function is de ned asE0qBi;Y( ;s) , logEBi;Y( Xb2BpBi(b) qBi;Y (b;Y)qBi;Y (Bi;Y) s! )(2.15)= logEX;Y( Xb2BpBi(b) qBi;Y (b;Y)qBi;Y (bi(X);Y) s! ); (2.16)where the transition from EBi;Yf g to EX;Yf g is possible because the terminside the expectation in (2.16) is the same for all transmit symbols x that142.2. BICM and Mismatched Decodinghave the same i-th labeling bit, andXx2XbipX;Y (x;y) = pBi;Y (b;y) : (2.17)The function E0qBi;Y( ;s) gives rise to the binary random coding exponentErqBi;Y(R), the I-curve function IqBi;Y (s), and the GMI IgmiqBi;Y for the i-thlevel, applying (2.5), (2.8), and (2.7), respectively. In particular,IqBi;Y (s) = EBi;Y(logXb2BpBi(b) qBi;Y (b;Y)qBi;Y (Bi;Y) s)= EX;Y(logXb2BpBi(b) qBi;Y (b;Y)qBi;Y (bi(X);Y) s); (2.18)andIgmiqBi;Y= maxs>0 IqBi;Y (s) : (2.19)For the special case of uniform input, from (2.14) and (2.18), the binaryI-curve function IqBi;Y (s) can be expressed in terms of the LLR asIqBi;Y (s) = 1 EX;Ynlog(1 + exp( sgn(bi(X)) qBi;Y (Y)s))o; (2.20)where the function sgn( ) is de ned for the labeling bits as sgn(0) = 1 andsgn(1) = 1.2.2.3 BICM and Binary I-curvesSubstituting (2.11) and (2.12) into (2.8) and considering (2.18), we obtain(cf. [9, proof of Theorem 2])152.3. Metric ManipulationIqX;Y (s) = EX;Y(logXx2Xm 1Yi=0pBi(bi(x)) qBi;Y (bi(x);Y)qBi;Y (bi(X);Y) s)= EX;Y(logm 1Yi=0Xb2BpBi(b) qBi;Y (b;Y)qBi;Y (bi(X);Y) s)= m 1Xi=0EX;Y(logXb2BpBi(b) qBi;Y (b;Y)qBi;Y (bi(X);Y) s)=m 1Xi=0IqBi;Y (s) : (2.21)That is, the BICM I-curve equals the sum of the binary I-curves IqBi;Y (s).This relation will be important for our subsequent discussion.2.3 Metric ManipulationWe now present and discuss di erent metric manipulations that can improvethe performance of BICM with a mismatched demodulator.2.3.1 Metric Scaling and GMIFor the general mismatched decoding scheme from Section 2.1, let sqX;Y bethe 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 q0X;Y (x;y) = [qX;Y (x;y)]cwith some constant c> 0. It follows from (2.6) that the new generalized Gal-lager function is E0q0X;Y( ;s) = E0qX;Y ( ;cs) and hence Iq0X;Y (s) = IqX;Y (cs).That is, the I-curve of the metric q0X;Y (x;y) is simply a compressed (forc> 1) or expanded (for c< 1) version of the I-curve of the metric qX;Y (x;y)162.3. Metric ManipulationshiftIqX,Y (s)Iq′X,Y (s)ssqX,Ysq′X,Y =sqX,Y/cIgmiqX,YFigure 2.4: Shift the critical point of the I-curve by metric scaling.along the s-axis. In particular, the GMI remains unchanged, while the crit-ical point changes to sq0X;Y = sqX;Y=c. This coordinate shift is illustrated inFigure 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 logarithmicdomain, in LLR-based decoding we refer to this operation as \metric scal-ing." Metric scaling allows us to control the critical point of the I-curve.The fact that it does not a ect the GMI should not come as a surprise.Using q0X;Y (x;y), the decoding rule (2.2) becomes^x = argmaxx2C[qX;Y (x;y)]c ;which returns exactly the same codeword as using qX;Y (x;y).172.3. Metric ManipulationWe now apply metric scaling to BICM.Theorem 2.1. Two I-curves are called harmonic if they have the samecritical point. The BICM GMI equals the sum of the binary GMIs if thebinary I-curves are harmonic, and is less than that otherwise. Let sqBi;Ybe the critical point of the binary I-curve of the i-th level. The binary I-curves can be made harmonic at s > 0 by metric scaling with the factorci = sqBi;Y=s at level i, i = 0;:::;m 1.Proof. Let q0Bi;Y (b;y) = [qBi;Y (b;y)]ci with some ci > 0. Then, Iq0Bi;Y(s) =IqBi;Y (cis), which peaks at (sqBi;Y=ci;IgmiqBi;Y ). According to Section 2.2 andin particular (2.12) and (2.21), BICM with these bit metrics has the symbolmetricq0X;Y (x;y) =m 1Yi=0q0Bi;Y (bi(x);y)and the I-curve functionIq0X;Y (s) =m 1Xi=0Iq0Bi;Y(s) :The BICM GMI is upper-bounded asIgmiq0X;Y= maxs>0m 1Xi=0Iq0Bi;Y(s) m 1Xi=0maxs>0 Iq0Bi;Y(s) (2.22)=m 1Xi=0IgmiqBi;Y: (2.23)Equality in (2.22) is achieved if and only if all binary I-curvesfIq0Bi;Y(s),182.3. Metric Manipulationi = 0;:::;m 1g, attain their maximum at the same value of s, i.e. ifthey are harmonic. By metric scaling in the logarithmic domain with theconstant factor ci = sqBi;Y=s , all binary I-curves will be harmonic at s forarbitrary s > 0.Remark 1: If the original binary I-curves are already harmonic, no align-ment is needed and IgmiqX;Y = Pm 1i=0 IgmiqBi;Y . This is the case if, for example,qBi;Y (b;y) /pYjBi(yjb), for which sqBi;Y = 1 8i [9, Corollary 1]. When thebinary I-curves are not harmonic, the above proof provides a constructiveprocedure for choosing the scaling factors to increase the BICM GMI. Thisrequires the computation of sqBi;Y , i = 0;:::;m 1, which can be doneo ine, either through analysis or through simulation when closed-form ex-pressions cannot be obtained.Remark 2: According to the independent binary channel model, BICMalways 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 thisis only conditionally true. We recall that the independent binary channelmodel requires m binary encoder-decoder pairs instead of just one as BICM.2.3.2 Metric Scaling and Symbol-By-Symbol DecodingWe again consider the general mismatched decoding scheme in Section 2.1.The derivation of the random coding exponent and the GMI is based on theword decoding rule (2.2). However, some important modern error-correctionschemes employ SBS decoding. That is, given the received sequence y, for192.3. Metric Manipulationeach position k = 0;:::;N 1, the SBS metricqXk;Y (x;y) ,Xx2CxkqX;Y (x;y)=Xx2Cxk N 1Yk=0qX;Y (xk;yk)!(2.24)is computed, where Cxk denotes the set of codewords whose k-th symbolequals x, and the decoding rule^xk = argmaxx2XqXk;Y (x;y) (2.25)is applied. For sparse-graph based codes, (2.25) with metric (2.24) can be ef- ciently evaluated (or approximated) using the sum-product algorithm [36].With matched metrics and equally likely chosen codewords, (2.25) becomes^xk = argmaxx2XXx2CxkpYjX(yjx)= argmaxx2XXx2CxkpXjY (xjy)= argmaxx2XpXkjY (xjy)= argminx2X 1 pXkjY (xjy) :Thus, sum-product SBS decoding with matched metrics minimizes the codedsymbol error probability, cf. word decoding as in [34, p. 120]. This holdstrue regardless of the probability mass function pX(x). However, minimizingthe coded symbol error probability may not be the same as minimizing the202.3. Metric Manipulationmessage symbol (or bit) or the word error probability. In particular, thecollection of decoded symbols [^x0:::^xN 1] is not necessarily a codeword inC. Therefore, achievable rates, in the sense that the word error probabilitycan still be driven to zero with increasing code length, further depend onthe translation of the decoded symbols into a valid codeword.Another popular SBS decoding metric isqXk;Y (x;y) =8><>:maxx2CxkqX;Y (x;y) ; if Cxk 6=;0 ; otherwise :=8>><>>:maxx2Cxk N 1Yk=0qX;Y (xk;yk)!; if Cxk 6=;0 ; otherwise :(2.26)Metric (2.26) can be estimated by the max-product algorithm, which isalso known as the min-sum algorithm from its form in the logarithmic do-main [36]. The metric (2.26) is derived from (2.24) by approximating a sumby its largest term.As in word decoding, metric scaling does not a ect the decoding out-come in max-product SBS decoding. However, if we replace qX;Y (x;y) by[qX;Y (x;y)]c in sum-product decoding using (2.25), the decoding outcomemight change. When c! 0, the decoding outcome generally becomes ran-dom, with exceptions, e.g., repetition codes where the sum (2.24) wouldconsist of only a single term. On the other hand, when c!1, sum-productdecoding approaches max-product decoding. With matched metrics, c = 1is the optimal scaling factor when the coded symbol error probability is the212.3. Metric Manipulationperformance measure. The I-curve peaks at s = 1 in this case. For mis-matched metrics, we propose that metric scaling with the factor c = sqX;Yis applied in sum-product decoding. This scaling shifts the critical point ofthe I-curve to 1. In the following, we provide a numerical example whichshows that this scaling yields the largest throughput in a rateless transmis-sion. Further practical examples which illustrate the bene t of this scalingare presented in Section 2.4.Example 2.1. Consider a binary asymmetric channel (BAC) with crossoverprobabilities 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 uniforminput, the matched I-curve follows from (2.8) or (2.20) asIpYjX(s) = 1 1 p02 log 1 + ps1(1 p0)s  p02 log 1 + (1 p1)sps0  p12 log 1 + (1 p0)sps1  1 p12 log 1 + ps0(1 p1)s ;(2.27)which peaks at (1;I(X;Y)).Suppose that a mismatched demodulator produces LLR of +1 and  1for received symbol y = 0 and y = 1, respectively. The correspondingmismatched I-curve is given byIqX;Y (s) = 1 plog(1 + es) (1 p) log(1 + e s) ; (2.28)where p = (p0 +p1)=2. The GMI IgmiqX;Y = 1 +plog(p) + (1 p) log(1 p) =222.3. Metric Manipulation1  Hb(p) is attained at sqX;Y = ln((1  p)=p), where Hb is the binaryentropy function. We have IgmiqX;Y  I(X;Y), and equality holds if and onlyif p0 = p1, i.e. when the channel is a binary symmetric channel (BSC).Applying scaling with factor c to this mismatched LLR, we obtain Iq0X;Y (s) =IqX;Y (cs). Consider Iq0X;Y (1) as a function of c. It attains its maximum withc = sqX;Y = ln((1 p)=p), for which Iq0X;Y (1) = Igmiq0X;Y= IgmiqX;Y . Our proposalstates that scaling with this value of c should be applied in sum-productdecoding.Let us consider a speci c example with p0 = 0:03 and p1 = 0:07. Thispair results in I(X;Y) = 0:72 bit per channel use (bpcu), p = 0:05, IgmiqX;Y =0:71 bpcu, and sqX;Y = 2:94. Figure 2.5 shows the plot of Iq0X;Y (1) vs. c.To demonstrate the e ect of scaling, we measure the average throughputachieved by coded transmission using a Raptor code. The code consistsof an outer LDPC code of length 10 000 and code rate 0.95 and an innerLuby transform (LT) code [37] with degree distribution [13, Table I, secondcolumn] (x) = 0:007969x+ 0:493570x2 + 0:166220x3+0:072646x4 + 0:082558x5 + 0:056058x8+0:037229x9 + 0:055590x19 + 0:025023x65 + 0:003135x66 :The parity-check matrix of the LDPC code is generated by the progres-sive edge growth (PEG) algorithm [38,39] with degree-3 variable nodes andalmost regular check nodes. The transmitter sends coded bits until thereceiver successfully determines the correct message, at which point the232.3. Metric Manipulation0 2 4 6 8 10 12 140.20.30.40.50.60.70.8  w/o i.i.d. channel adaptorw/ i.i.d channel adaptorsum-product decodingmax-product decodingIq′X,Y(1)c→Rate[bpcu]→Figure 2.5: Throughput achieved with a Raptor code over a BAC and SBSdecoding with mismatched metrics versus the metric-scaling parameter c.instantaneous throughput is measured. Figure 2.5 shows the empirical av-erage throughput achieved with sum-product and max-product decoding asa function of c (consider only lines labeled \w/o i.i.d. channel adapter" forthe moment). Both methods use a maximum of 200 iterations to decodethe joint factor graph of the LDPC and LT codes [32, Fig. 1(b)]. Thedecoder 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 thebest throughput for sum-product decoding. It can also be seen how theachieved throughput degrades as c! 0. For large c, sum-product decod-ing starts to converge towards max-product decoding. However, since we242.3. Metric Manipulationapplied LLR bounding for improved numerical stability in our decoder im-plementation, this convergence is not fully achieved in Figure 2.5. We canturn the asymmetric channel into a symmetric one by using i.i.d. channeladapters suggested in [40]. These adapters are synchronized random sign-adjusters applied to the encoded bits and LLR streams at the transmitterand receiver, respectively, cf. [40, Fig. 8]. With uniform input, the I-curveis not changed by i.i.d. channel adaptation, cf. (2.20). Symmetrization issometimes considered useful when codes are designed under the assumptionof a symmetric channel. The simulation results for the symmetrized chan-nel in Figure 2.5 (star makers labeled \w/ i.i.d. channel adapter") showthat the conclusions about scaling are not an artifact of transmission overasymmetric channels.Remark 1: Understanding the impact of metric scaling in fact relates toa familiar research problem. In systems with additive Gaussian noise, forexample, inaccurate estimation of the signal-to-noise ratio (SNR) results ina mismatched metric that is a scaled version (in the logarithmic domain) ofthe matched metric. The scaling factor c is proportional to the estimatedSNR. Thus, impact of SNR mismatch on sum-product decoding is a specialcase of our discussion. The results in Figure 2.5 agree with the known resultthat 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 referencestherein. When sqX;Y > 1, which is the case of underestimated SNR, thesimulation results in Figure 2.5 suggests an intriguing upper bound IqX;Y (1)to the achievable rate with sum-product decoding.252.3. Metric ManipulationRemark 2: We would like to contrast our scaling from LLR scaling asinvestigated in e.g. [43{46]. In these works, scaling is derived from studyingthe internal operation of the decoder and has the purpose of o setting ap-proximations to lower implementation complexity. On the other hand, ourproposed scaling is characterized only by the metric and is aimed to improvethe performance of exact sum-product decoding.Application to BICM: In connection with Theorem 2.1, in BICM withsum-product decoding we propose aligning all binary I-curves at s = 1. Formax-product decoding, only the alignment matters, but not the value of thecritical point s . This is analogous to the case of word decoding consideredin Section 2.3.1.2.3.3 Cascaded Channel Model and Metric-MismatchCorrectionBICM as de ned by (2.12), (2.1) and (2.2) constitutes a mismatched decod-ing rule, for which an achievable rate is given by the GMI IgmiqX;Y de ned 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 generationof  qBi;Y (y) as part of the transmission channel and determine the ratesachievable by further processing and other ways of decoding.Cascaded Channel ModelLet zi ,  qBi;Y (y) be the channel output to be processed. Accordingly, wehave a cascaded channel as shown in Figure 2.6(a) with input X and outputZ , [Z0;:::;Zm 1]. From the data-processing inequality [34, Sec. 2.3] [47,262.3. Metric Manipulation(c)(d)(a)(b)zi ∈RI(Bi;Ri)I(Bi;Zi)pY|X(y|x) y ∈Y ΛqB0,Y (y),...,ΛqBm−1,Y (y)pY|X(y|x) y ∈Y ΛqB0,Y (y),...,ΛqBm−1,Y (y)x∈X z ∈Rmbi(x) ∈BI(X;Z)I(Bi;Z)pY|X(y|x) y ∈Y ΛqBi,Y (y)pY|X(y|x) y ∈Y ΛqBi,Y (y),{ΛqBj,Y (y)}bi(x) ∈B ri ∈Rmiz ∈Rmbi(x) ∈BFigure 2.6: BICM demodulator as part of a cascaded channel. Also indicatedabove each block diagram is the associated average mutual information.(a) symbol-input cascaded channel; (b), (c) and (d) di erent binary-inputcascaded channels.272.3. Metric ManipulationSec. 2.8], the corresponding average mutual information I(X;Z) is less thanor equal to I(X;Y). Let us consider the use of binary codes for the cascadedchannel X!Z. The chain rule of mutual information [34, p. 22] reads asI(X;Z) =m 1Xi=0I(Bi;ZjB0;:::;Bi 1) : (2.29)For the terms on the right-hand side, we have the following inequalitiesI(Bi;ZjB0;:::;Bi 1) I(Bi;Z) (2.30) I(Bi;Zi) (2.31) IgmiqBi;Y: (2.32)The mutual information I(Bi;Z) in (2.30) represents the constrained chan-nel capacity, i.e. the maximum achievable rate with a given input distribu-tion, of the binary-input channel Bi !Z illustrated in Figure 2.6(b). Forthis cascaded channel, I(Bi;Z)  I(Bi;Y) [34, Sec. 2.3]. We note, how-ever, that there is no de nitive relation between I(Bi;ZjB0;:::;Bi 1) andI(Bi;Y). The mutual information I(Bi;Zi) in (2.31) is the constrained ca-pacity of the channel Bi !Zi shown in Figure 2.6(c). Equality in (2.31)is achieved if Zi is a su cient statistic for Bi given Z. Inequality (2.32)holds because IgmiqBi;Y is just an achievable rate by a mismatched decoding,whereas I(Bi;Zi) is the maximum achievable rate by matched decoding overthe channel Bi!Zi.Inequality (2.31) suggests that Zj, j6= i, can provide further informationfor the decoding of Bi. In between the two extremes of using only Zi andusing all m elements of Z, we might opt to process a subset Ri = [Zi;fZjg]282.3. Metric Manipulationof 1 < mi < m elements of Z to produce decoding metrics for Bi. Theresulting channel is included in Figure 2.6(d) and the inequalitiesI(Bi;Zi) I(Bi;Ri) I(Bi;Z) (2.33)hold for its associated mutual information. In summary, we obtain thefollowing inequality chain:IgmiqX;Y  m 1Xi=0IgmiqBi;Y m 1Xi=0I(Bi;Zi) m 1Xi=0I(Bi;Ri) m 1Xi=0I(Bi;Z) 8>>><>>>:m 1Xi=0I(Bi;Y)I(X;Z) I(X;Y) : (2.34)Metric-Mismatch CorrectionThe processing of original LLRs to achieve the above rates can be consideredas metric-mismatch correction. The matched bit-metrics for BICM trans-mission over the cascaded channel X !Z corresponds to corrected LLRs pZjBi(z) = ln pZjBi(zj0)pZjBi(zj1)(2.35)for i = 0;:::;m 1. This metric correction realizes the rate I(Bi;Z) over thebinary-input channel Bi!Z, and, considering (2.34), it is the optimal cor-rection in terms of achievable rate. The bit-metric correction corresponding292.3. Metric Manipulationto the channel Bi!Ri and achievable rate I(Bi;Ri) is given by pRijBi(ri) = ln pRijBi(rij0)pRijBi(rij1): (2.36)Finally, the scalar metric correction pZijBi(zi) = ln pZijBi(zij0)pZijBi(zij1)(2.37)leads to I(Bi;Zi). Since metrics (2.35), (2.36), and (2.37) match to their cor-responding binary-input channels, their binary I-curves are already alignedat s = 1. As a result, the BICM GMI with these metrics is equal toPm 1i=0 I(Bi;Z),Pm 1i=0 I(Bi;Ri), andPm 1i=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-o 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 scalarmetric correction in terms of GMI, a fact that is also clear from the abovederivation. It has further been pointed out in [24] that non-scalar metriccorrection functions could further increase the GMI. We have provided suchcorrections in (2.35) and (2.36).In practice, the correction functions are prepared o ine and stored aslook-up tables. Online evaluation is then done by table look-up and possiblywith additional interpolation [51, 52]. For clarity, we summarize all bit-metric manipulations and their e ects in Table 2.1.302.3. Metric ManipulationTable 2.1: BICM metric manipulation methods and their e ects.Metric Manipulation E ectOriginal mismatched LLR  qBi;Y (y) IgmiqX;Y  Pm 1i=0 IgmiqBi;Y is achiev-able.Scale all LLRs by the same factorc = sqX;Y : q0Bi;Y(y) = sqX;Y  qBi;Y (y)Shift the critical point of theBICM I-curve to 1, aim to im-prove the performance of sum-product SBS decoding.Scale LLRs di erently by factorsci = sqBi;Y=s for some s > 0: q0Bi;Y(y) = (sqBi;Y=s ) qBi;Y (y)Binary I-curves are aligned ats . The BICM GMI is Igmiq0X;Y=Pm 1i=0 IgmiqBi;Y . Choose s = 1 insum-product SBS decoding.Apply scalar metric mismatch cor-rection: pijBi(zi) = ln pZijBi(zij0)pZijBi(zij1)Bit metrics are matched to thecascaded channels Bi!Zi. TheBICM GMI is Pm 1i=0 I(Bi;Zi).Apply reduced-dimensional vectormetric mismatch correction: pRijBi(ri) = ln pRijBi(rij0)pRijBi(rij1)Bit metrics are matched to thecascaded channels Bi!Ri. TheBICM GMI is Pm 1i=0 I(Bi;Ri).Apply optimal vector metric mis-match correction: pZjBi(z) = ln pZjBi(zj0)pZjBi(zj1)Bit metrics are matched to thecascaded channels Bi!Z. TheBICM GMI is Pm 1i=0 I(Bi;Z).312.4. ApplicationsRemark: Inequality (2.34) also shows that no metric manipulation allowsBICM to attain a GMI better thanPm 1i=0 I(Bi;Y), i.e., the GMI of matchedBICM over the original channel X!Y. To achieve I(X;Z) or I(X;Y) withbinary codes, we need to use MLC with multistage decoding [5] applied tothe channels X!Z and X!Y, respectively.2.4 ApplicationsIn this section, we present and discuss a number of illustrative and rele-vant examples for BICM transmission applying the metric manipulationsdescribed 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 CorrectionSetupMetric corrections are relatively easy to implement by means of look-uptables if the mismatched metrics are drawn from a small set of discretevalues. Such cases arise if quantization and in particular hard detection isapplied at the receiver. In the following, we consider the example of 8-aryamplitude-shift keying (8-ASK) transmission over the additive white Gaus-sian noise (AWGN) channel with hard detection. We apply binary re ectedGray labeling with [b0b1b2] = [000];[100];[110];[010];[011];[111];[101];[001]for the eight signal points from left to right, as in Figure 2.7. This isthe best labeling in the moderate SNR range [53], cf. also [54]. Letthe SNR be equal to 6.43 dB, at which matched BICM attains a GMI of322.4. Applications[001][000][b0b1b2] =[100] [110] [010] [011] [111] [101]Figure 2.7: 8-ASK constellation and labeling.IgmiqX;Y =2Pi=0I(Bi;Y) = 1:50 bpcu, and I(X;Y) = 1:56 bpcu. Hard detectionthat produces LLRs +1 and  1 leads to the GMI IgmiqX;Y = 1:07 bpcu, whichis the maximum of the BICM I-curve IqX;Y (s) =2Pi=0IqBi;Y (s), attained atsqX;Y = 1:65. The I-curves for matched and hard-decision decoding areplotted in Figure 2.8(d).Metric-Mismatch CorrectionWe now examine the e ect of metric manipulation. Consider level 2, whoseI-curves are shown in Figure 2.8(c). With matched LLR, the binary GMIis I(B2;Y) = 0:77 bpcu. With hard detection, B2 ! Z2 is a BSC withthe 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 criticalpoint to 1 and leaves the GMI unchanged (line Z2 in Figure 2.8(c)). Onthe other hand, the optimum vector correction (2.35) yields I(B2;Z) =0:75 bpcu (line Z2Z0Z1 in Figure 2.8(c)), which is signi cantly higher thanI(B2;Z2) and rather close to I(B2;Y). The price for this is a more complexmapping. In scalar correction, we map z2 from two input values f1; 1g totwo output values f2:56; 2:56g, i.e.,  pZ2jB2(1) = 2:56 and  pZ2jB2( 1) = 2:56. In optimum vector correction, we need a larger look-up table tomap [z2;z0;z1] from f[1;1;1], [1; 1;1], [1; 1; 1], [1;1; 1], [ 1;1; 1],332.4. Applications0.5 1 1.5 20.050.10.150.20.25  matchedhardZ0, Z0Z1, Z0Z2, or Z0Z1Z20.5 1 1.5 2 2.50.20.250.30.350.40.450.50.55  matchedhardZ1 or Z1Z2Z1Z0 or Z1Z0Z20.5 1 1.5 2 2.5 30.40.450.50.550.60.650.70.750.8  matchedhardZ2Z2Z0Z2Z1Z2Z0Z10.5 1 1.5 2 2.50.40.60.811.21.41.6  matchedhardscalar (Z0+Z1+Z2)optimum (Z0 + Z1Z0 + Z2Z0Z1)s→ s→s→s→ (d)BICM(b)level1(a)level0(c)level2BinaryI-curve[bpcu]→BinaryI-curve[bpcu]→BinaryI-curve[bpcu]→BICMI-curve/Throuhgput[bpcu]→Figure 2.8: I-curves for 8-ASK transmission over the AWGN channel withmatched detection (\matched"), hard detection (\hard"), and di erentmetric-mismatch corrections (identi ed by the used LLRs zi in the sub- gures). Sub gures (a)-(c) show I-curves for binary levels. Sub gure (d)shows BICM I-curves. Bullet markers show simulated throughput using aRaptor code and sum-product decoding, and the double-arrowed arcs linkthe simulated points to the peak of the corresponding I-curves.342.4. Applications[ 1; 1; 1], [ 1; 1;1], [ 1;1;1]g to the corrected LLRs f12.5, 7.40, 3.63,1.05,  1:05,  3:63,  7:40,  12:5g. Between these two correction methods,we have two choices for reduced-dimensional vector correction (2.36), namelyR2 = fZ2;Z0g or R2 = fZ2;Z1g, each of which maps four input values tofour output values. The two corresponding I-curves in Figure 2.8(c) arelabeled Z2Z0 and Z2Z1, respectively. Since I(B2;Z2Z0) <I(B2;Z2Z1), thelatter is preferred.We have a BAC at both level 0 and 1. For level 1, we can see fromFigure 2.8(b) that scalar correction hardly increases the GMI. It is interest-ing to observe that correction with R1 = fZ1;Z2g yields the same I-curveas scalar correction, whereas correction with R1 =fZ1;Z0g yields the sameI-curve as the optimum correction. For level 0, di erent correction functionsresult in identical binary I-curves, as shown in Figure 2.8(a). These phe-nomena can be explained from examining the labeling of signal points. Toavoid repetition, we only explain why knowing z0 helps to increase the GMIat level 1, whereas knowing z2 does not. Consider the labeling bits at level1. They are f0;0;1;1;1;1;0;0g for the eight symbols from left to right. Wecan divide the four labeling bits 1 into two groups: the outer two bits thatare adjacent to a bit 0, and the other two inner bits which are not. To betterapproach the performance of the matched decoding, we should distinguishif a received bit 1 is an outer bit or an inner bit. Indeed, additional knowl-edge about z0 tells us if the received bit 1 at level 1 is an outer bit (whenz0 = 1) or not (when z0 = 1). On the other hand, knowing z2 would nothelp. Similarly, the four labeling bits 0 can be divided into two groups, andknowledge of z0, but not z2, helps to distinguish if the received bit 0 is an352.4. Applicationsinner or an outer bit.The BICM I-curve for scalar and the best of all metric-mismatch cor-rections are included in Figure 2.8(d). For the latter, full vector correctionis only required for level 2, while scalar correction and reduced-dimensionalcorrection are su cient at level 0 and level 1, respectively. The increasein the GMI by scalar correction comes mostly from the e ect of having allthe binary curves aligned at s = 1. Optimum correction results in a muchimproved GMI of 1.40 bpcu, which is 93% of the GMI for matched BICM.ThroughputUsing the Raptor code from Example 2.1, the simulated average through-put is shown in Figure 2.8(d) (markers without lines). We observe that thethroughput closely follows the associated GMIs if metric-mismatch correc-tion is applied. In these cases, the GMI is achieved at s = 1. In the caseof hard detection metrics, the gap between GMI and simulated rate is sig-ni cantly 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, theachieved throughput by sum-product SBS decoding seems to be determinedby IqX;Y (1) rather than the GMI.2.4.2 Noncoherent Carrier-Modulated OrthogonalSignalingCarrier-modulated orthogonal signaling (orthogonal modulation) with non-coherent detection is attractive due to its low complexity detector imple-mentation. This type of signaling, e.g. in the form of frequency shift-keying362.4. Applications(FSK) and pulse-position modulation (PPM), has been used in scenarioswhere coherent detection is impossible or expensive to employ. Examples ofsuch scenarios include fast fading environment and large Doppler spread inmilitary communications.Transmission ModelAn 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 othersare zero. Let h = aej be the complex channel gain, and n be the length-Mcomplex AWGN vector with variance N0 per element. The received sampleis a length-M complex vectory = aej x+n: (2.38)Noncoherent detection requires only knowledge of the magnitude of the chan-nel gain and received sample. The channel transition probability is [55]pYjX(yjx)/I0 2ajye(x)jN0 ; (2.39)where I0( ) is the zeroth order modi ed Bessel function of the  rst kind [56],and jye(x)j is the magnitude of the element of y at the position of the non-zero element of x.372.4. ApplicationsMetricsThe matched LLR metric for noncoherent orthogonal modulation is matchedi (y) = ln pYjBi(yj0)pYjBi(yj1)= lnXx2X0iI0 2ajye(x)jN0 Xx2X1iI0 2ajye(x)jN0 ; (2.40)The popular max-log LLR metric is max logi (y) = maxx2X0ilnI0 2ajye(x)jN0  maxx2X1ilnI0 2ajye(x)jN0 : (2.41)Since both functions ln( ) and I0( ) are monotonic with positive input, themax-log LLR can be presented as max logi (y) = lnI0 2aN0 maxx2X0i jye(x)j! lnI0 2aN0 maxx2X1i jye(x)j!: (2.42)That is, the detector can search for the maximum values of jye(x)j beforecomputing lnI0( ).We now consider metrics resulting from approximation to the functionlnI0( ) with positive  2R as illustrated in Figure 2.9. When  is large,I0( ) can be asymptotically approximated by e =p2  and lnI0( ) can beapproximated  . From (2.42), this approximation leads to a new LLR a max logi (y) = 2aN0 maxx2X0ijye(x)j maxx2X1ijye(x)j!: (2.43)382.4. Applications0 2 4 6 8 10 12024681012αln(I0(α))α→α24Figure 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  rst two terms inits power series expansion 1 +  2=4, and lnI0( ) can be approximated by 2=4. The corresponding LLR is ps max logi (y) = a2N20 maxx2X0ijye(x)j2 maxx2X1ijye(x)j2!: (2.44)Metrics (2.43) and (2.44) require less computational complexity than themax-log metric (2.42), which in turn is computationally cheaper than thematched metric (2.40).If we drop the factor 2a=N0 in (2.43) and a2=N20 in (2.44), we have the392.4. Applicationsparameter-free metrics pf a max logi (y) = maxx2X0ijye(x)j maxx2X1ijye(x)j; (2.45) pf ps max logi (y) = maxx2X0ijye(x)j2 maxx2X1ijye(x)j2 : (2.46)Both channel gain and noise power estimation are not needed in the cal-culation of these metrics. This simpli cation further reduces the detectioncomplexity. The parameter-free power series max-log metric (2.46) has beenconsidered in [58] for BICM with iterative decoding (BICM-ID) [59,60].Numerical ResultsFor orthogonal constellations, all levels have the same binary I-curves if thesame metric is applied. Thus, the BICM I-curve is simply m times the binaryI-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 Rayleighfading channels. Figure 2.10 shows the BICM GMI with the matched met-ric (2.40) and the  ve mismatched metrics (2.42), (2.43), (2.44), (2.45), and(2.46) at di erent SNR values (de ned as Efa2g=N0). It is interesting, andperhaps surprising, to observe that all the  ve mismatched metrics attainpractically the same GMI across the whole SNR range. Furthermore, thisGMI is very close to that of the matched metric.Throughput with SBS Decoding: Figure 2.11 shows the BICM I-curveof the case M = 16 and AWGN channel at a moderate SNR of 6:35 dB,where all mismatched metrics attain a GMI of 2.0 bpcu. The BICM I-402.4. Applications3 4 5 6 7 8 9 10 11 120123456  GMI, matched metricGMI, mismatched metrics5 10 15 200123456  GMI, matched metricGMI, mismatched metricsRate[bpcu]→M=64M=16M=4SNR[dB]→(a)AWGN channelM=64M=16M=4SNR[dB]→(b) Rayleighfading channelRate[bpcu]→Figure 2.10: BICM GMI of noncoherent orthogonal modulation.412.4. Applicationscurve of the max-log (2.42), asymptotic max-log (2.43), power series max-log (2.44), parameter-free asymptotic max-log (2.45), and parameter-freepower series max-log (2.46) peaks at s = 0:83, 0:77, 0:19, 6:6, and 3:5,respectively. In comparison, the BICM I-curve of the matched metric (2.40)has a slightly larger GMI and peaks at s = 1. Below the peak of each I-curve, we present the average throughput obtained by simulation with theRaptor code from Example 2.1 and sum-product SBS decoding. We seethat while the mismatched GMIs are the same, the throughputs are notablydi erent. Furthermore, for each of the two parameter-free metrics withcritical point of the I-curve greater than 1, the throughput is upper boundedby IqX;Y (1). Following Section 2.3.2, we apply constant LLR scaling withthe 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 thesame throughput of 1.86 bpcu, which agrees with the corresponding GMI.This throughput leaves just a small gap to the throughput of the matchedmetric. Therefore, metric scaling appears to provide a very favorable trade-o between complexity and e ect of metric-mismatch correction. However,we note that the factor for metric scaling is SNR-dependent, and thus theseemingly parameter-free metrics lose advantage over their counterparts ifscaling is applied.Next, we consider the throughput with max-product decoding. The re-sults are also included in Figure 2.11. Mismatched metrics attain a through-put of approximately 1.34 bpcu. The throughput seems to be determinedby the GMI alone. Although the throughput is lower than in the case ofsum-product decoding with metric scaling, the low detection complexity422.4. Applications0.1 0.19 0.30.511.341.8622.5  Sum−product Sum−product w/ scaling Max−product0.5 10.511.341.8622.50 1 3.5 6.60.511.341.8622.5ps-max-log max-loga-max-logpf-a-max-logpf-ps-max-logs→Rate[bpcu]→matchedFigure 2.11: BICM I-curve and coded throughput of 16-ary noncoherentorthogonal 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 fadingchannel, and SNR of 8.5 dB in Figure 2.12: (i) the mismatched metricsachieve GMIs that are close to that of the matched metric; (ii) sum-productdecoding with metric scaling attains improved throughout; and (iii) thecombination of parameter-free metrics with max-product decoding is a low-complexity option for noncoherent orthogonal modulation. We note an ex-ception for the throughput of power series max-log metric with sum-productdecoding. It is expected to be larger than that of max-product decoding.432.4. Applications0.05 0.086 0.150.511.522.5  Sum−product Sum−product w/ scaling Max−product0.5 10.511.522.51 4.4 6.30.511.522.5s→Rate[bpcu]→ps-max-log max-loga-max-logpf-a-max-logpf-ps-max-logmatchedFigure 2.12: BICM I-curve and coded throughput of 16-ary noncoherentorthogonal 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 areclipped by our decoder implementation to avoid numerical over ow, result-ing in a reduced throughput.2.4.3 Pulse-Position Modulation with Direct DetectionOur next example considers M-ary pulse-position modulation (PPM) withintensity modulation and direct detection. It is a popular signaling schemefor  ber and free-space optical communication, cf. e.g. [61]. Each M-ary442.4. ApplicationsPPM symbol is a vector x = [x0:::xM 1] with exactly one element equalto 1 (on slot) and the others equal to 0 (o slots). We apply the photon-counting channel model [61], by which the received vector isy = [y0:::yM 1]andyi = xiai +ni : (2.47)The variables ai and ni are i.i.d. Poisson random variables with mean  sand  b, respectively. The channel transition probabilities are given byp(yijxi) = ( sxi + b)yiyi! exp ( [ sxi + b]) ; (2.48)and p(yjx) = QM 1i=0 p(yijxi). It follows thatp(yjx)/ 1 +  s b yo(x); (2.49)where yo(x) is the magnitude of the slot of y which corresponds to the onslot of x. The matched LLR for PPM is pYjBi(y) = lnPx2X0i 1 +  s b yo(x)Px2X1i 1 +  s b yo(x) : (2.50)The simpli ed max-log metric is qBi;Y (y) = maxx2X0iyo(x) maxx2X1iyo(x)!ln 1 +  s b ; (2.51)which has considerably lower computational complexity than (2.50).452.4. Applications−10 −9 −8 −7 −6 −5 −4 −3 −20123456  GMI, matchedGMI, max−logIqX,Y(1), max−log10log10(λs/(Mλn)) [dB]→Rate[bpcu]→Figure 2.13: BICM GMI for decoding with matched metric and max-logmetric, and IqX;Y (1) for max-log metric. 64-PPM transmission over Poissonchannel. Background radiation has mean  b = 0:2 photon/slot.Similar to the carrier-modulated signaling schemes in Section 2.4.2, PPMconstellations are orthogonal and thus, the BICM I-curve and GMI are mtimes the binary I-curve and GMI of any level if the same metric is ap-plied at all levels. Figure 2.13 shows the GMI of matched metric (2.50)and max-log metric (2.51) as a function of the SNR for the example of 64-PPM and  b = 0:2 [62]. We observe only a relatively small gap betweenthe two GMIs. This suggests that the max-log metric (2.51) could be ap-plied with little loss in the achievable rate. Also included in Figure 2.13 isIqX;Y (1) for the max-log metric, for which a notable gap to the correspond-462.4. Applicationsing mismatched GMI can be seen, especially at low SNR values. Followingthe discussion in Section 2.3.2, we expect that scaling the max-log LLRsuch that the critical point is shifted to 1 should be applied to improvethe performance of sum-product decoding. This prediction is con rmedby the results presented in Figure 2.14 for an example SNR of  8 dB. Itshows the I-curves for matched, max-log, and scaled max-log metric withthe scaling factor c = sqX;Y = 0:56, together with simulated throughputsfor sum-product and max-product decoding. The throughput  gures areobtained from simulation using the same Raptor code as in Example 2.1.We observe that the simulated throughput using sum-product decoding wellapproaches the associated GMI for matched metric. For the max-log met-ric, however, the gap between throughput and GMI is considerably larger.With scaling, the throughput accomplished with sum-product decoding issigni cantly improved to 1.96 bpcu compared to 1.74 bpcu without scal-ing. More speci cally, the gap between throughput and GMI is closed by60%. Finally, the performance of max-product decoding is notably inferiorto sum-product decoding and, as expected, is not changed by scaling.2.4.4 MIMO-QAM with Clipped Max-Log MetricThe  nal illustration of BICM with mismatched decoding metric and metric-mismatch correction uses the example considered in [24, Sec. IV]. The trans-mission system is a 2 2 multiple-input multiple-output (MIMO) systemwith 16-ary quadrature amplitude modulation (16-QAM) and Rayleigh fad-ing channels, and the average SNR is  xed to 9.13 dB. Furthermore, theBICM demodulator uses the max-log metric and the max-log LLR is clipped472.4. Applications0.2 0.4 0.6 0.8 1 1.2 1.41.21.41.61.822.22.4  sum−productmax−productmax−logmatchedscaledmax−logs→I-curve/Throughput[bpcu]→Figure 2.14: BICM I-curve and simulated rates. Matched, max-log, andscaled max-log metric with the scaling factor c = sqX;Y = 0:56. The bul-let markers show simulated rates using a Raptor code and sum-productand max-product decoding. 64-PPM over Poisson channel at SNR of10 log10( s=(M b)) = 8 dB and  b = 0:2 photon/slot.to the range [ 2;+2]. LLR clipping is helpful to reduce complexity in list-based detection [51]. It has been shown in [24, Sec. IV] that the optimumscalar correction (2.37) improves the GMI and the bit-error rate (BER) per-formance of the coded scheme. In this section, we also consider LLR scalingand a hybrid scalar correction as explained below.We assume a binary re ected Gray labeling for the 16-QAM symbols.The 2 2 MIMO system with 16-QAM has in total m = 8 binary levels, ofwhich four are equivalent to level 0 and four to level 1. Hence, we only need482.4. Applicationsto consider those two levels when showing results. Figure 2.15(a) presentsthe I-curves of the levels with matched and clipped max-log metrics. Thecurves for the matched metrics serve as an upper bound and will be used togauge the success of mismatched-metric manipulation. It can be seen thatthe two binary I-curves for the clipped max-log metric are misaligned. Weexpect that scaling to align them at s = 1 will increase the BICM GMIand improve sum-product decoding performance. The BICM GMI curvesfor matched, clipped max-log, and scaled clipped max-log metric are shownin Figure 2.15(b). Also included are simulated throughputs, again usingthe Raptor code from Example 2.1 with sum-product decoding. We observethat, for clipped max-log with sqX;Y = 1:50 > 1, the throughput seems tobe upper bounded by IqX;Y (1). This might explain the large gap betweenthe 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 improvedGMI. While the GMI increase is only slightly, the throughput improvementis much more signi cant.Applying the optimum scalar metric-mismatch correction (2.37), alsoconsidered in [24, Sec. IV], [51, Sec. V], further improves both the GMI andthe performance with sum-product decoding. At the same time, it is morecomplex than scaling as the correction requires table look-up and interpo-lation (see also the plot of the scalar correction function in Figure 2.16 andthe 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 aspecial consideration, we propose the following hybrid metric manipulation492.4. Applications0.5 1 1.5 20.30.350.40.450.50.550.60.65  matchedclipped max−logscaledscalar correctionhybrid0.5 1 1.5 23.23.43.63.844.24.4  matchedclipped max−logscaledscalar correctionhybrid(a)(b)level 0level 1Rate[bpcu]→s→Rate[bpcu]→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 thecritical point of the I-curve to 1, scalar metric-mismatch correction, and ahybrid correction. (a) I-curves for binary levels. (b) BICM I-curves. Thebullet markers show simulated rates using a Raptor code and sum-productdecoding, and the double-arrowed arcs link the simulated points to the peakof the corresponding I-curves. The curves for \scalar correction" and \hy-brid" are numerically on top of each other.502.4. Applications−2 −1 0 1 2−4−2024  linearly scaledscalar correctionhybrid−2 −1 0 1 2−4−2024  linearly scaledscalar correctionhybridinput LLRinput LLRlevel 0level 1outputLLRoutputLLRFigure 2.16: Metric manipulations for 2 2 MIMO transmission with 16-QAM over Rayleigh fading and SNR of 9.13 dB. Hybrid metric manipulationrequires channel symmetrization before applying (2.52).512.5. Conclusionfor this particular case: q0Bi;Y(y) =8>><>>:ln pZijBi(zij0)pZijBi(zij1); if zi = 2cizi ; otherwise :(2.52)That is, the two extreme LLR values are mapped as in the optimum scalarcorrection, and the immediate values are scaled with a factor such that theresulting I-curve peaks at s = 1. This correction function is indeed a goodapproximation of the optimum scalar correction for the symmetric channelat 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 inExample 2.1 before using the hybrid rule (2.52). The di erent metric ma-nipulations are plotted in Figure 2.16. From Figure 2.15, we observe thathybrid manipulation results in I-curves and throughput performances thatare practically identical to those achieved with optimum scalar correction.Considering its simpler implementation, this hybrid metric manipulationwould be the method of choice for this application example.2.5 ConclusionWe have studied BICM with mismatched decoding metrics. We adoptedthe GMI as a pertinent performance measure and showed that scaling oflogarithmic bit-metrics can improve the BICM GMI. We also suggested andprovided numerical evidence that metric scaling also improves throughputin practical coding schemes using SBS decoding, even if the GMI remains522.5. Conclusionunchanged. Furthermore, we studied general mismatched metric correc-tion methods, including a previously proposed scalar correction. We pre-sented a number of practically relevant applications in which mismatcheddemodulation occurs, and our numerical results highlighted the bene ts andperformance-complexity trade-o s for the di erent metric-mismatch correc-tion approaches.53Chapter 3Multilevel Coding:Reduced-Layer, GeneralDecoding Metrics, andRateless TransmissionMLC enables the combination of binary ECC with multilevel constella-tions [4, 5]. It can achieve the same rate as coded transmission with non-binary codes. In comparison, BICM also combines binary ECC with multi-level constellations, but in a simpler layout with just one instead of severalcoding layers and decoding stages as in MLC. The disadvantage of BICMover MLC is some rate loss. This loss can be small with Gray mappings [53]and thus, BICM has been widely employed in practice. Nevertheless, thereare important cases where Gray mapping does not exist, or loses its relevancewhen the Euclidean-distance neighborhood of signal points is changed by thechannel. For these cases, MLC might considerably outperform BICM. Ex-amples of such cases are multiple-input multiple-output (MIMO) signalingand orthogonal modulation. In this chapter, we present a number of contri-54Chapter 3. Multilevel Codingbutions to the development of MLC. Our contributions can be grouped intothree sections as follows.Conventional MLC requires as many coding layers (and thus encoder-decoder pairs) as the number of levels. In Section 3.1, we introduce thegeneral scheme of reduced-layer MLC (RL-MLC) which can decrease thenumber of coding layers with a trade-o to the achievable rate. RL-MLC isa generalization of a previous work [12]. Conventional MLC and BICM arespecial cases of RL-MLC where the number of layers equals the number oflevels 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 equalsthe sum of the maximum achievable rates of the layers. Furthermore, theselayer rates can be estimated separately with the assumption that estimateddata from lower layers is always correct. We then view each layer as a BICMscheme and adopt the results as presented in Chapter 2 for BICM into theMLC case. In particular, we use the GMI as an indication of the maximumachievable rate, and apply metric manipulations to improve the performanceof MLC.Recently, the notion of rateless transmission has gained much attentionin the communications community, e.g., [13, 37]. In the context of MLC,rateless transmission o ers at least two attractive features. Firstly, it would2We would like to stress the di erence between \level" and \layer." Each level corre-sponds to a bit position in the labels of the signal points. Each layer corresponds to anencoder-decoder pair, and may be comprised of one or multiple levels.3Henceforth, without further clari cation, by \MLC" we to refer to the general RL-MLC scheme. When the reduced-layer nature is material in a discussion, we will make itexplicit.55Chapter 3. Multilevel Codingeliminate the need for carefully tailoring code rate for each layer, e.g. ac-cording to the capacity design rule [5, Sec. IV-A]. Secondly, for transmissionover time-varying channels, rateless codes seamlessly adapt to the instanta-neous channel quality and attain a larger average throughput compared tochannel adaptation by switching between  xed-rate codes. In Section 3.3,we propose a novel rateless MLC scheme, which is compatible with any de-coding metric and requires only one binary rateless code. We illustrate thatcombining rateless codes with MLC is not as straightforward as it is withBICM, and that a careless combination might lead to a considerable rateloss compared to  xed-rate MLC. We distinguish between coding loss dueto the imperfectness of the code, and structural loss due to the structureof MLC. In our proposed scheme, the structural loss is non-zero only in so-called unstable systems. The stable or unstable nature of a rateless MLCscheme depends on the relationship between achievable rates of the layers.We illustrate that structural loss can be largely alleviated by controlling theacknowledgment delay from the receiver, and in practice a simple minimumsegment-length (MSL) control rule can be e ective enough in reducing thisloss and maintaining the rate advantage of MLC.Application of our contributions to MIMO and orthogonal modulationsystems are presented in Section 3.4. Section 3.5 completes the chapter withconcluding remarks.563.1. Reduced-Layer MLCMAP channelE2E1E0 D0D1D2x yb0b1b2ˆb0ˆb1ˆb2Figure 3.1: Example of conventional MLC.3.1 Reduced-Layer MLCWe consider a discrete-time memoryless channel with transmit symbol X2X and received symbol Y 2Y. Let M = 2m be the cardinality of X andB0;:::;Bm 1 be the random variables of the labeling bits. The conceptof reduced-layer MLC is best described by an example. Figure 3.1 showsthe diagram of conventional MLC [5] with an 8-ary constellation. At thetransmitter, there are m = 3 independent binary encoders E0, E1, and E2which produce encoded bits for the mapper. At the receiver, there are threebinary decoders working in three consecutive stages. In the  rst 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 estimatedvalue 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 numberof labeling bits. For large constellations, this structural complexity becomescumbersome. In reduced-layer MLC, we combine several layers into one, asin BICM. For example, we can reduce the number of coding layers from three573.1. Reduced-Layer MLCchannelMAP(a)E1E0 D0D1b0x yˆb0b1,b2 ˆb1,ˆb2channelMAP(b)E1E0 D0D1x yb0,b1b2ˆb0, ˆb1ˆb2Figure 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 asingle layer. In Figure 3.2(b), layer 0 and 1 are combined. Given the numberof levels m and the number of layers  < m, there are  !S(m;k) possiblecombinations, where S(m;k) is the Stirling number of the second kind. Forthe best throughput performance, we want to choose the con guration whichyields the largest achievable rate. Rate analysis for reduced-layer MLC ispresented in Section 3.2. Full enumeration to  nd the best con guration ispossible for small  , which is typically the design goal. In many cases, wecan also expedite the search by exploiting special properties of the signalingscheme, as in Example 3.1 below.583.2. Multilevel Coding with General Decoding Metrics3.2 Multilevel Coding with General DecodingMetricsIn this section, we  rst establish that the MLC achievable rate can be ex-pressed in terms of the achievable rates of the layers. Applying this result,we then focus on the transmission over each MLC layer and provide expres-sions for the per-layer GMI. Based on these expressions, we propose metric-mismatch correction technique for MLC. The latter two contributions arean extension of the results in Chapter 2 to the MLC case.3.2.1 Achievable RatesGiven a detection rule, we say the rate C is achievable if for any  > 0 andsu ciently large N, there exists a codeC(N0;R) of length N0 N and rateR C and a decoding algorithm D such that the block error probabilityis less than or equal to  , cf. [34, Ch. 5], [63, Ch. 10]. We say C is themaximum achievable rate if it is the tightest upper bound on achievablerates.We have the following theorem regarding achievable rates of MLC.Theorem 3.1. Given a detection rule, let Ck be an achievable rate of the k-th layer given decoding decisions from lower layers are correct, k = 0;:::;  1. The MLC scheme achieves rate C = P  1k=0Ck. Furthermore, if each Ck isthe maximum achievable rate of layer k, then C is the maximum achievablerate of the MLC scheme.Proof. We  rst show achievability. Let Ck and mk be an achievable rate593.2. Multilevel Coding with General Decoding Metricsand 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 > 0and large enough N, there exists a codeCk(mkN0;Rk) of length mkN0>Nand rate Rk  Ck and a decoding algorithm Dk such that the block errorprobability Pk   k. MLC with these codes has rate R C = P  1k=0Ck.Furthermore, the block error probability of MLC is upper bounded by [64,Inequality 4.1]P    1Xk=0Pk   1Xk=0 k =  : (3.1)Hence, rate C is achievable.Now let Ck be the maximum achievable rate for each layer k and C =P  1k=0Ck. Transmission with rate R>C by the MLC scheme requires thatat least one layer, say k0, has to transmit with rate Rk0 >Ck0. Hence, thereexists an  > 0 such that for any code and decoding algorithm at this layer,the block error probability is Pk0 > . SinceP  Pk 8k; (3.2)C is the maximum achievable rate for MLC.We have the following remarks. Firstly, as the theorem makes no as-sumptions about detection rules being matched to the channel transitionprobabilities, it can be applied to mismatched decoding in the layers. Sec-ondly, Theorem 3.1 allows us to consider each layer separately without con-cerning about error propagation when estimating achievable rates and whenmanipulating mismatched metrics to increase these rates.603.2. Multilevel Coding with General Decoding Metrics......(b) Receiver(a) Transmitter...ˆv0ˆv1ˆuκ−1ˆu1=ˆv0xMAPEκ−1E0E1yv0vκ−1v1D1Dκ−1D0Figure 3.3: MLC transmitter and receiver.3.2.2 Per-Layer Transmission and GMISince the maximum achievable rate of a mismatched decoding scheme is notknown in general [65], we follow recent literature on BICM [8,9] and use theGMI as an approximation to the layer maximum achievable rate.An m-level,  -layer MLC con guration can be described by a length-mvector h = [h0:::hm 1] with hi2f0;:::;  1g and hj  hi if j <i. Theelement hi = k indicates that level i is in layer k. The MLC transmitterwith  independent binary encoders is presented in Figure 3.3(a). The corre-sponding MLC receiver with  binary decoders is presented in Figure 3.3(b).Let Vk be the multivariate random variable of the labeling bits at layer k.613.2. Multilevel Coding with General Decoding MetricsThat is, the elements of Vk are fBi : hi = kg. In Vk and other multivariaterandom variables below, we assume that the binary random variables fBi :hi = kg are ordered by their index i. At the receiver, the detection of Bidepends on the received symbol Y and the estimated value of bits from lowerlayers. Let Di denote the multivariate random variable of these lower-layerbits, i.e., the elements of Di are fBj : hj <hig. Furthermore, let bi(X) anddi(X) denote the value of Bi and Di corresponding to the transmit symbolX. 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 groupedinto one layer, h = 01 m and Di = ;. Let Uk be the multivariate randomvariable of all lower-layer bits common to all levels at layer k. The elementsof Uk are fBj : hj < kg. 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;^Di(b;y;d)for Bi based on the received sample y2Y and estimated data from lowerlayers d2BjDij,B=f0;1g. We assume qBi;Y;^Di(b;y;d) > 0,8b2B, y2Y,and d2BjDij. The corresponding LLR is de ned as qBi;Y;^Di(y;d) , ln qBi;Y;^Di(0;y;d)qBi;Y;^Di(1;y;d): (3.3)For all levels i at layer k, we have Di = Uk. Thus, qBi;Y;^Di(b;y;d) can alsobe written as qBi;Y;^Uk(b;y;u). The layer metric is de ned asqVk;Y;^Uk(v;y;u) =Yi:hi=kqBi;Y;^Uk(b;y;u) ; (3.4)623.2. Multilevel Coding with General Decoding Metricswith v2BjVkj and u2BjUkj.From Theorem 3.1, in the following calculations we assume that theestimated data from lower layers is always the same as transmitted. Thatis, we use Di instead of ^Di, and Uk instead of ^Uk. For the i-th level and bitmetric qBi;Y;Di(b;y;d), the binary I-curve is de ned asIqBi;Y;Di(s) ,  EBi;Y;Di(logXb2BpBi(b) qBi;Y;Di(b;Y;Di)qBi;Y;Di(Bi;Y;Di) s)(3.5)=  EX;Y(logXb2BpBi(b) qBi;Y;Di(b;Y;di(X))qBi;Y;Di(bi(X);Y;di(X)) s):(3.6)With uniform input, the binary I-curve can be expressed in terms of theLLR as, cf. (2.20)IqBi;Y;Di(s) = 1 EX;Ynlog(1 + exp( sgn(bi(X)) qBi;Y;Di(Y;di(X))s)o:(3.7)The binary GMI of the level is the peak value of this curve,IgmiqBi;Y;Di, maxs>0 IqBi;Y;Di(s) : (3.8)For matched metrics, i.e., when qBi;Y;Di(b;y;d) is proportional to the tran-sition probability pYjBi;Di(yjb;d), the binary I-curve peaks at s = 1 and theGMI equals the average mutual information I(Bi;YjDi).The layer I-curve corresponding to the layer metric qVk;Y;Uk(v;y;u) is633.2. Multilevel Coding with General Decoding Metricsde ned asIqVk;Y;Uk(s) , EVk;Y;Uk8<:logXv2BjVkjpVk(v) qVk;Y;Uk(v;Y;Uk)qVk;Y;Uk(Vk;Y;Uk) s9=;= EX;Y8<:logXv2BjVkjpVk(v) qBi;Y;Di(v;Y;uk(X))qBi;Y;Di(vk(X);Y;uk(X)) s9=; : (3.9)As in Section 2.2.3, the layer I-curve can be shown to be equal to the sumof the binary I-curves of the levels,IqVk;Y;Uk(s) =Xi:hi=kIqBi;Y;Di(s) : (3.10)The layer GMI is the peak value of this layer I-curve,IgmiqVk;Y;Uk, maxs>0 IqVk;Y;Uk(s) : (3.11)By Theorem 3.1, the MLC scheme achieves a rate equal to the sum of thelayer GMIs. For convenience, we call this rate the MLC GMI. We note thatTheorem 2.1 is also applicable to the per-layer MLC transmission. Thatis, 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-curvesare 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 nd the MLC con guration which yields the largest MLC GMI. Due tothe orthogonality of the PPM constellation, all levels in the same layer will643.2. Multilevel Coding with General Decoding Metricshave the same binary I-curve if the same metric is applied. Let Igmi(i) bethe 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 isthen equal toIgmi =  1Xk=0mkIgmi k 1Xi=0mi!: (3.12)Thus, we only need to obtain at most m binary GMI values Igmi(0), . . . ,Igmi(m 1) in order to calculate the GMI of any MLC con guration.We consider 128-PPM (hencem = 7) with background radiation b = 0:2photons/slot and matched LLR qBi;Y;^Di(y;d) = lnXx2Xd;0di;ipYjX(yjx)Xx2Xd;1di;ipYjX(yjx); (3.13)= lnXx2Xd;0di;i 1 +  s b ye(x)Xx2Xd;1di;i 1 +  s b ye(x) ; (3.14)where the notation Xd;0di;bi (Xd;1di;bi) denotes the set of x that has the labelingbits di(x) = d and bi(x) = 0 (bi(x) = 1). The GMI of conventional MLC,BICM, 2-layer MLC speci ed by h = [0 0 0 0 1 1 1], and 3-layer MLCspeci ed by h = [0 0 0 1 1 2 2] are plotted in Figure 3.4. We recallh = [0 0 0 0 1 1 1] indicates that the lower four levels are grouped intolayer 0 and the remaining three levels are grouped into layer 1. Similarly,653.2. Multilevel Coding with General Decoding Metrics−12 −11 −10 −9 −8 −7 −6 −51234567  Conventional MLC (7 layers)BICM (1 layer)2−layer MLC3−layer MLCRate[bpcu]→10log10λs/M[dB]→Figure 3.4: GMI of conventional MLC, BICM, and 2-layer MLC for 128-PPM over Poisson channel with  b = 0:2.h = [0 0 0 1 1 2 2] indicates that the lowest three levels are groups into layer0, the next two levels are grouped into layer 1, and the highest two levels aregrouped into layer 2. The plots show that conventional MLC can outperformBICM by a large GMI gap. MLC with only two layers can close this GMIgap by more than a half. MLC with three layers further narrows the gap.Thus, reduced-layer MLC enables a trade-o between the achievable rateand the number of decoding layers.663.3. Rateless Multilevel Coding3.2.3 Metric-Mismatch CorrectionMetric-mismatch correction methods from Table 2.1 can be extended to theMLC case. In particular, metric scaling q0Bi;Y;^Di(y;d) = sqBi;Y;Di qBi;Y;^Di(y;d) (3.15)can be applied to improve the GMI and throughput performance with sum-product SBS decoding in each layer, where sqBi;Y;Di is the critical point ofIqBi;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 CodingHaving discussed achievable rates and metric mismatch correction in MLC,we proceed by presenting our novel rateless MLC scheme. After the de-scription, we provide an operation analysis and develop a control techniqueto reduce the structural rate loss of rateless MLC when necessary. Ourscheme is compatible with any mismatched metric, metric-mismatch correc-tion method, and decoding algorithm in the layers. Following Theorem 3.1and for generality, we continue using the notations Ck, k = 0;:::;  1,and C = P  1k=0Ck to denote the maximum achievable rates of the layers(assuming there is no error from lower layers) and of MLC, respectively. Wewill resort to the GMI as an approximation for maximum achievable ratesagain when showing numerical results in Section 3.4.673.3. Rateless Multilevel Coding3.3.1 Encoding and DecodingIn rateless BICM, the binary encoder takes in a  xed-length block of mes-sage bits and continuously produces coded bits, which are mapped to trans-mit symbols. The receiver can produce metric samples immediately aftereach received symbol. These metric samples are accumulated until theycan provide enough information for successful decoding. At this point, thereceiver acknowledges the transmitter and the transmitter switches to anew message block, cf. [13]. In this manner, rateless codes combine forwardECC with automatic repeat-request (ARQ), and hence realize a hybrid ARQscheme [66]. We now consider a \naive" combination of rateless coding andMLC, in which the encoder-decoder pair at each layer (see Figure 3.3) issimply implemented in a rateless fashion. At layer 0, metric samples be-come available to the decoder immediately after each received symbol, as inrateless BICM. However, at any upper layer k> 0, the decoder collects sym-bol samples and waits for estimated data from lower layers to arrive. Onlythen, bit metrics can be calculated. The estimated data from lower layersdoes not become available immediately after each received symbol, but inlarge blocks. Thus, by the time this data is available and bit metrics arecalculated, the collection of bit metrics at layer k may have already accumu-lated more information than necessary for successful decoding. This meansthat layer k is underutilized and the exceeding channel uses are wasted asrate loss. It is only at the lowest layer that we are able to collect just-enoughinformation for successful decoding and avoid this underutilization.The above observation leads us to propose the following scheme. The683.3. Rateless Multilevel Coding...(b) Receiver...(a) Transmitter......Eκ−1Eκ−2E0Dκ−2xdecodeddataBitCalculationy MetricMAPD0Dκ−1Figure 3.5: Rotation rateless MLC transmitter and receiver. Stream redi-rection occurs at switching to a new interval.transmitter employs  binary rateless encoders Ek, k = 0;:::;  1. In thenaive combination above, output from encoder Ek is always mapped to layerk. In our proposed scheme as illustrated in Figure 3.5(a), output from Ek ismapped to di erent layers at di erent time intervals. More speci cally, Ekcyclically directs its output through layers (  1);(  2);:::;0 during  time intervals t (  1);t (  2);:::;t. Each time interval correspondsto the transmission of a number of symbols. The number of symbols in each693.3. Rateless Multilevel Codingtime(b)(a)layer 0...ℓ[t−1] ℓ[t]ℓ[t−(κ−2)]... ...... C1 C0Cκ−2ℓ[t−(κ−1)]Cκ−1layer κ−2layer κ−1layer 1Figure 3.6: (a) Information segments at the receiver. Segments with thesame shading belong to the same codeword of a binary encoder-decoderpair. White segments are already decoded information. Segments may havedi erent 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 channelwith di erent interval maximum achievable rates Ci, i = 0;:::;  1.interval might vary from one interval to another, and is discussed in detailbelow.The corresponding receiver is shown in Figure 3.5(b). Each binary de-coder Dk, k = 0;:::;  1, collects information from all layers, startingfrom the highest layer   1 and ending at the lowest layer 0. The decodersattempt to decode only when collecting information from layer 0. Thus, dur-ing any time interval, among the  decoders, only the one decoder collectinginformation from layer 0 attempts to decode.Figure 3.6(a) shows the information segments at the receiver over  time703.3. Rateless Multilevel Codingintervals. Suppose some decoder Dk is collecting information from layer 0during interval t. This decoder has also collected information segmentsfrom layers (  1);:::;1 in the preceding (  1) intervals. When Dkgathers that it might have accumulated enough information, it makes adecoding attempt. If decoding fails, Dk continues to collect informationfrom layer 0, and attempts decoding again. Eventually, decoding will besuccessful, which marks the end of this time interval. The receiver then sendsan acknowledgment to the transmitter. Upon receiving the acknowledgment,the transmitter: (i) changes the input of the corresponding encoder Ek toa new message block, and (ii) re-maps the encoded bit streams to di erentlayers in the cyclical manner illustrated in Figure 3.5(a). That is, the streamthat 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 fromdi erent layers, corresponding to this new streaming. From the viewpointof a  xed encoder-decoder pair (Ek;Dk), the overall channel is segment-wise time varying. Each segment is associated with a di erent maximumachievable rate. This is illustrated in Figure 3.6(b).The proposed scheme requires an initialization. This can be seen inFigure 3.6(a), where white segments represent already decoded informa-tion. Therefore, at the start of the transmission session, the transmittersends some preamble data that is known to the receiver in the correspond-ing segments. This preamble transmission appears only once and thus theassociated rate loss will be negligible for su ciently long sessions.713.3. Rateless Multilevel Coding3.3.2 Operation Analysis and ControlAs shown in Figure 3.6, let ‘[t]  0 be the number of transmit symbolsduring time interval t. While ‘[t] is an integer number, for simplicity we let‘[t] assume real values in the following analysis; the e ect of this relaxationbecomes negligible for long codewords. By the end of time interval t, onecodeword has been successfully decoded. We distinguish three variablesrelated to the transmission of this codeword: K[t] is the number of bitsin the message block taken by the encoder,  [t] is the nominal amount ofinformation collected by the receiver, i.e., [t] =  1Xk=0Ck‘[t k] ; (3.16)and  nally,  [t] is the minimal amount of information su cient for successfuldecoding. 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 positiveaverage ( [t] K[t]). We call this value the coding loss as it measures therequired overhead of the code. The di erence between  [t] and  [t] is dueto the MLC structure. We therefore call the average of ( [t]  [t]) thestructural loss. The total rate loss of an MLC scheme, i.e., the gap betweenthe 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] > 0and terminate decoding such that  [t] =  [t]. That is, no structural lossoccurs. However, if successful decoding is possible at ‘[t] = 0, we have likely723.3. Rateless Multilevel Codingaccumulated more than enough information and wasted channel resources.Therefore, if ‘[t] varies around an equilibrium length and ‘[t] > 0, we assumethat the transmission has no structural loss. In the following we will elabo-rate on this equilibrium length and the conditions under which the systemis stable, that is, when ‘[t] automatically converges to and remains aroundthe equilibrium length.Equilibrium LengthFor simplicity, we assume that K[t] = K, which means that all encodersalways take in message blocks of the same length. This also means that allthe  binary encoder-decoder pairs can use the same binary rateless code.Let n[t] be a vector of (  1) non-negative previous transmission lengthsthat 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), fort tinitial = 0, the state evolves according to the linear time-invariant state-space equationn[t+ 1] = An[t] +b [t] ; (3.17)withA =2666666640 1 ::: 0... ... ... ...0 0 ::: 1 C  1C0  C  2C0 :::  C1C0377777775and b =2666666640...01C0377777775:733.3. Rateless Multilevel CodingLet  be the mean value of  [t]. We call the solution of the equationn[t+ 1] = An[t] +b ; (3.18)the equilibrium point. This equilibrium point is found asne =  (I  1 A) 1b = ‘e1(  1) 1 ; (3.19)where ‘e is the equilibrium length‘e =  P  1i=0 Ci=  C ; (3.20)and 1(  1) 1 and I  1 is the all-one column vector of length   1 and theidentity matrix of size (  1) (  1), respectively. We observe that: If  [t] is a constant, i.e.  [t] =  , once at the equilibrium point, thesystem stays there. With ideal codes, i.e.  [t] = K, once at the equilibrium point, thesystem stays there and su ers zero total loss. Thus, with ideal codes,we can achieve a throughput equal to C.Stable SystemsThe system is stable if the eigenvalues of the matrix A in (3.17) lie inside theunit circle in the complex plane. In this case, the state n[t] will automaticallyhover around the equilibrium point ne. Then, the interval length ‘[t] staysclose to ‘e and is positive, so that  [t] =  [t] holds and the transmission has743.3. Rateless Multilevel Codingzero structural rate loss. For stable systems, the only loss with respect to Cis the coding loss and our proposed MLC scheme is a rate-optimal way ofcombining binary rateless codes and multilevel constellations.The eigenvalues of A are the roots ri of the polynomialU(z) = 1 + C1C0z 1 + C2C0z 2 +:::+ C  1C0z  1 : (3.21)There are several methods to determine whether jrij < 1 for all roots of(3.21) [67, Ch. 4.5]. For the special cases of  = 2 and  = 3 layers, we canmake the criteria for stability explicit:  = 2: U(z) = 1 + C1C0z 1, and the root r1 =  C1=C0 lies inside theunit circle if and only if C0 >C1. In other words, a two-layer schemeis stable if the lower layer has larger maximum achievable rate thanthe upper layer.  = 3: U(z) = 1+ C1C0z 1+ C2C0z 2, and the two roots r1;2 = 12C0 ( C1 pC21  4C0C2) lie inside the unit circle if and only if (C0 > C2 andC0 +C2 >C1).Unstable SystemsIf the linear system (3.17) is unstable, the interval length ‘[t] would oscillatewith increasing amplitude. Due to the constraint ‘[t]  0, the length ‘[t]will eventually swing between zero and some extreme values. This behavioris 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 (the753.3. Rateless Multilevel Coding0 10 20 30 40 5000.10.20.30.40.50.60.70.80.91t→ℓ[t]/K→Figure 3.7: Interval length ‘[t] of an unstable system.binary code is ideal), and the initial state n[0] = (K=C)[1:0 1:2]T. At largevalues of t, the system settles into the following pattern: there is one longinterval of length K, followed by two intervals of length zero. In the longinterval, one codeword is decoded with all samples from layer 0. In the nextinterval, one codeword is decoded with all samples from layer 1 and no moresamples 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 therateless code is ideal, the system achieves a data rate of only 3 bpcu, whichis well below C. This behavior calls for a control mechanism to minimizethe structural loss for unstable systems.763.3. Rateless Multilevel CodingControl for Unstable SystemsThe receiver can delay sending the acknowledgment to the transmitter aftersuccessful decoding. By controlling this delay, we can reduce the structuralloss. To illustrate the potential of such a control, we consider a scenariowhere we can predict the values of  [t] in a near future. Suppose that atthe beginning of time interval  , the receiver state is n[ ], and we predictthe values of  [t] over the  nite time horizon T to be  [ ];:::; [ +T 1].Beyond this horizon, we extrapolate that  [t] equals to the average of thepredicted values  [ ], given by [ ] = 1T +T 1Xt=  [t] : (3.22)We observe from Eqns. (3.17) to (3.20) that, if  [t] remains constant as [t] =  [ ] for t  +T, the transmission su ers no structural loss if all thesegment lengths equal  [ ]=C. Therefore, we want to settle into the state‘[t] =  [ ]=C for t  + T. We end up having an extended control periodfrom  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] tominimize the structural loss. The initial amount of information stored atthe receiver at the beginning of time interval t =  (the initial information773.3. Rateless Multilevel Codinginventory) isIbeginning =  1Xk=1  1Xj=kCj‘[  k] : (3.24)The ending information inventory at the end of time interval  +T +  2(or beginning of the time interval t =  +T +  1), isIend =  1Xk=1  1Xj=kCj  [ ]C : (3.25)During the control period, the total amount of arriving information isCP +T+  2t= ‘[t], and we spend P +T+  2t=  [t] to successfully decode T +  1 codewords. The structural loss is thereforeIstructural loss = C +T+  2Xt= ‘[t]  +T+  2Xt=  [t] +Ibeginning Iend : (3.26)Since the beginning and ending receiver state are  xed, the structural lossis minimized if P +T 1t= ‘[t] is minimized. Planning the segment lengths canthen be stated as the following linear programming (LP) problem:f^‘[ ]::: ^‘[ +T 1]g= argmin +T 1Xt= ‘[t]subject to:P  1k=0Ck‘[t k]  [t]; 8t2[ ; +T +  2]; ‘[  (  1)] ::: ‘[  1] T= n[ ];‘[ +T] = ::: = ‘[ +T +  1] =  [ ]=C;‘[t] 0 :(3.27)As the transmission progresses, we apply the model predictive control783.3. Rateless Multilevel Coding// Model predictive control1: 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 techniquecan also be e ective in compensating for imperfect prediction of future valuesof  [t]. The MPC technique is summarized as in Figure 3.8.An alternative control rule to the MPC technique above is to alwaysreceive at least ‘min symbols in each interval. We call this the minimal seg-ment length (MSL) control rule. This simple rule comes from observing thebehavior 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 mostof the information from a low-rate layer needs a relatively long interval andforces other decoders to accumulate too much information. By setting aproper minimum value for all ‘[t], MSL reduces the long wait by makingthe total amount of information to be distributed more equally over the  intervals.Example 3.2. We now illustrate the e ectiveness of the control techniquesvia a hypothetical example. Let  [t] be a random process such that  [t] =(1:05 + [t])K. The component  [t] is Rayleigh-distributed with mean 0.04.Therefore,  =K = 1:09 and thus the coding loss is 9%. This model ap-proximates the simulation result of a Raptor code from [69, Fig. 6]. We793.3. Rateless Multilevel Coding0.96 0.98 1 1.02 1.04 1.06 1.08 1.1 1.12 1.140.010.020.030.040 2 4 6 8 10 12 14 16 18 2000.010.020.03Structuralloss¯ θ−¯ν K→Structuralloss¯ θ−¯ν K→×KCℓmin→T→Figure 3.9: Controlling structural loss in an unstable system with maximumachievable 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 su ersa structural loss of 36%. For MPC with perfect prediction, the structuralloss versus T is plotted in the upper half of Figure 3.9. It is interesting toobserve that even with short T = 1, MPC reduces the structural loss tojust about 2%. With long horizon T, it can almost completely eliminate thestructural loss. Thus, controlling the acknowledgment delay can indeed re-duce the structural loss. Unfortunately, perfect prediction of  [t] over a longhorizon is rather idealistic. With the simple and practical MSL control rule,803.4. Applicationsthe structural loss versus ‘min is plotted in the lower half of Figure 3.9. Theresult shows that MLC can reduce the structural loss to a very small valueof less than 2%. This value is much less than the coding loss. These resultssuggest that MSL control is indeed a practical way of stabilizing ratelessMLC systems, and we apply it in the application examples below.3.4 ApplicationsIn this section, we demonstrate the e cacy of our rateless MLC scheme in anumber of transmission scenarios. The application examples include MIMOand orthogonal modulation transmission in stationary or slow fading chan-nels, and using matched or approximate metrics. Following Section 3.2.2, weuse the GMI as an approximation to the maximum achievable rates of thelayers. We use the same Raptor code as in Example 2.1 with K = 9500 andsum-product SBS decoding. When a decoding attempt fails, an additionalinformation amount of 0:01K is collected before the next attempt.3.4.1 MIMO-QAMConsider MIMO transmission with Nt transmit and Nr receive antennas.Each transmit antenna emits symbols from a constituent quadrature ampli-tude modulation (QAM) constellation A of size MA. Each symbol of theMIMO constellation X is thus a vector of Nt elements x = [x0:::xNt 1]T,where each element xi 2A is a complex number. The size of the multidi-mensional transmit constellation is M = (MA)Nt. Assuming a  at fadingchannel with the matrix of complex gains H and complex additive white813.4. ApplicationsGaussian noise (AWGN) vector n with variance N0 per element, the re-ceived symbol is given byy = Hx+n: (3.28)The channel transition probability follows aspYjX(yjx)/exp  jy Hxj2N0 : (3.29)It was shown in [17, Sec. IV-E] that there exists a signi cant gap betweenthe 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 andmatched decoding metric (3.13). The size of the constellation is M = 256and the number of labeling bits is m = 8. We use MLC with  = 2 layers.The  rst four bits are grouped into layer 0, and the other four bits aregrouped into layer 1. We consider an i.i.d. Rayleigh fading channel andtwo 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 isunstable. We apply the MSL control with ‘min = 1:06K=C. The signal-to-noise ratio (SNR) is de ned asEr=N0, whereEr is the average received powerat 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 reducethe gap between BICM GMI and the average mutual information I(X;Y).Over the whole SNR range, the simulated throughput is about 92% of theMLC GMI. This ratio is close to the reported value in [69] for a Raptor823.4. Applications0 2 4 6 8 10 12 14 16 18 2012345678  I(X;Y)GMI, BICMGMI, 2−layer MLCThroughput, BICMThroughput, 2−layer MLC4-QAM4-TxRate[bpcu]→ 4-Rx2-Rx10log10Er/N0 [dB]→Figure 3.10: GMI and throughput of rateless MLC for 4-QAM MIMO trans-mission with 4 transmit and 2 and 4 receive antennas over an i.i.d. Rayleighfading channel.code over a binary AWGN channel. Therefore, we conclude that most ofthe rate loss is the coding loss, and the structural loss is small. Overall, theresults demonstrate a signi cant throughput gain from using our ratelessMLC scheme instead of BICM.3.4.2 Noncoherent Carrier-Modulated OrthogonalSignalingIn orthogonal modulation, the Euclidean distances between signal pointsare the same. Hence, for constellations with size M > 2, Gray mappings833.4. ApplicationsFigure 3.11: GMI and throughput of rateless MLC for M = 128 noncoherentorthogonal modulation. Label \w/o control" and \w/ control" are for therotational scheme without and with MSL control, respectively.843.4. Applicationsdo not exist. We apply rateless MLC to carrier-modulated orthogonal sig-naling with noncoherent detection. The channel model is described in Sec-tion 2.4.2. Let us consider a system with m = 7 levels [70],  = 2 layers andh = [0 0 0 0 1 1 1]. Similarly to the MIMO-QAM application above, theSNR is de ned as Er=N0, and for this modulation Er = Efa2g. The layerGMIs are plotted in Figure 3.11(a) for the case of an AWGN channel and inFigure 3.11(b) for the case of an i.i.d. Rayleigh fading channel. Dependingon the SNR, the GMI of layer 0 can be smaller or larger than that of layer 1.Therefore, the MLC system can be unstable or stable, respectively. We re-call that when the system is stable, no control is needed and no structuralloss results. For all SNR values, we apply our rateless scheme (i) withoutcontrol and (ii) with MSL using ‘min = 1:06K=C. As expected, Figure 3.11shows that when the system is unstable, MSL improves the throughput.Furthermore, when the system is stable, MSL practically does not incurstructural loss, achieving the same throughput as the case without control.This suggests that we can safely apply MSL control to the whole range ofSNR values.Rateless transmission is most bene cial in slow-fading channel environ-ments. Thus, we now illustrate the performance of our scheme in a slowfading example. To this end, we assume the complex channel gain g = aej evolves from one symbol to the next according to the  rst-order autoregres-sive (AR1) modelgi =  gi 1 +p1  2wi ; (3.30)where wi is an i.i.d. zero mean complex Gaussian process with variance853.4. ApplicationsEr. The parameter 0    1 determines the rate of fading. The extremevalues  = 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 theMSL control to: always receive at least an amount of information Imin ineach segment. Corresponding to N0 and the magnitude of the instantaneouschannel gain, the instantaneous GMI can be obtained from the GMI plotsin Figure 3.11(a). Let C[t] be the MLC GMI averaged over time intervalt. We use the value R[t] = C[t]K= [t] as an indication of the throughputin interval t. We recall that  [t] (3.16) is the total amount of informationassociated with the codeword that has just been decoded in this interval.The ratio K= [t] is the relative throughput e ciency of the codeword.As an interesting example, we consider 10 log10(Er=N0) = 8 dB and = 0:999 such that C[t] would change signi cantly across intervals. Weuse MSL control with Imin = 1:06K. Samples of average MLC GMI andR[t] obtained from a simulation are plotted in Figure 3.12. For comparison,the BICM GMI of the same channel realizations, averaged over the samesegment boundaries, is also included. We observe that the throughput of ourscheme closely follows the associated MLC GMI. Furthermore, R[t] exceedsthe BICM GMI for the majority of the times. Averaging over the whole 70sample 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 attainsa throughput gain in slow fading channels as well.863.4. Applications10 20 30 40 50 60 7001234567  Average MLC GMIAverage BICM GMIR[t]t→Rate[bpcu]→Figure 3.12: Example of 2-layer rateless MLC over slow fading channel. Thevalue R[t] approximates the average throughput during time interval t.3.4.3 Pulse-Position Modulation with Direct DetectionWe continue with the PPM transmission in Example 3.1. Consider 128-PPMwith 2-layer MLC such that h = [0 0 0 0 1 1 1]. Simulation results withthe matched metric (3.14) demonstrate the same trends as in the case ofnoncoherent orthogonal modulation above, and therefore are not presentedhere. We now consider the popular max-log approximate LLR metric, whichis qBi;Y;Di(y;d) =0@ maxx2Xd;0di;iye(x) maxx2Xd;1di;iye(x)1Aln 1 +  s b : (3.31)873.4. Applications0.55 0.75 1 1.511.21.41.61.82  MatchedMax−logScaled max−loglayer 0layer 1s→Rate[bpcu]→Figure 3.13: Layer I-curves of the 128-PPM MLC scheme with  b = 0:2photons/slot and 10 log10( s=(M b)) =  10:5 dB and di erent metrics.Each doubled-arrowed arc connects the peak of an I-curve with a markerthat represents the associated throughput with an o -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, atwhich the 2-layer MLC scheme with matched metric attains a GMI of3.5 bpcu. Figure 3.13 shows the I-curves (3.10) of the two layers withmatched and max-log metrics. We recall that the I-curve of layer 0 is equalto four times the binary I-curve of any level in layer 0. Similarly, the I-curve of layer 1 is equal to three times the binary I-curve of any level inthat layer. From Figure 3.13, we see that the max-log metric incurs onlya small reduction in the GMI. The critical point (the s-coordinate of the883.4. Applicationspeak) of the I-curve of layer 0 is 0.55 and that of layer 1 is 0.75. As thecritical point of the I-curve is not equal to 1, the throughput achieved bysum-product SBS decoding can be considerably lower than the GMI, seeSection 2.3.2. We illustrate this phenomenon via a simulation in which theRaptor decoder is fed with LLR samples from layer 0 or layer 1 alone. Inthe detection at layer 1, we use transmitted data from layer 0 instead of theestimated data. The resulting throughputs are presented as bold markers inFigure 3.13. The phenomenon is especially pronounced at layer 0: while thethroughput with metric (3.13) is about 93% of the corresponding GMI, thisratio reduces to only 80% with metric (3.31). The most simple correctionto reduce this gap is to scale the mismatched LLR with a factor equal tothe critical point of the I-curve, following (3.15). That is, we multiply themax-log LLR at layer 0 with 0:55 and at layer 1 with 0:75. This scalingshifts the critical point to 1 without changes in the GMI. We stress againthat the scaling factor for layer 1 is obtained without considering errors inlayer 0. The scaled max-log metric results in an improved throughput, asshown in Figure 3.13. Finally, using the scaled max-log metric in our rota-tional rateless scheme with appropriate ‘min, we obtain a throughput of 3.1bpcu. In comparison, a simulation of matched BICM with the same Raptorcode results in a throughput of 2.5 bpcu. Thus, scaled max-log MLC attainsa throughput gain of more than 20% compared to matched BICM.893.5. Conclusion3.5 ConclusionIn this chapter we considered three practical issues of MLC. Our  rst contri-bution is the development of reduced-layer MLC which can favorably tradethe achievable rate for MLC structural complexity reduction. Our secondcontribution involves rate analysis and metric mismatch correction for MLCwith approximate metrics. We use the GMI as an approximation to themaximum achievable rate of the layer, which can be estimated separatelyand with the assumption that there is no error in the decoding at lowerlayers. Our last contribution is the proposal of a novel rateless MLC schemewith no or negligible structural rate loss. We provide extensive numericalexamples with MIMO, noncoherent carrier-modulated orthogonal signaling,and IM-DD PPM in stationary or slow-fading scenario, using matched ormax-log metric, which show that our scheme can attain throughput gainscompared to rateless BICM.90Chapter 4Applications in Free-SpaceOpticsFSO has recently emerged as a cost-e ective solution for a wide range ofcommunication applications [7]. It possesses a multi-Gigabits-per-secondcapacity, is highly secure, rapidly deployable, and re-installable. We haveconsidered coded PPM for FSO in Section 2.4.3, Example 3.1, and Sec-tion 3.4.3. In this chapter, we continue with several advanced signalingschemes and apply coding techniques from the previous chapters to improveFSO’s rate and reliability.4.1 Rateless Hybrid FSO-RF for Last-MileAccessWhile the telecommunications backbone infrastructure has been remark-ably improved over the past decade, bridging its enormous capacity to end-users remains a di cult challenge. Existing copper wires and wireless LANtechnologies cannot handle the data rate necessary to deliver modern high-de nition multimedia in real time, whereas coaxial cables and  ber optics914.1. Rateless Hybrid FSO-RF for Last-Mile Accessmapper 2mapper 1channel 2channel 1 detector1detector2EtransmitterDreceiverFigure 4.1: Channel coding diversity scheme.are often too inconvenient and expensive to deploy at end-users’ premises.FSO has been anticipated to be a low-cost solution to this \last-mile chal-lenge." However, last-mile FSO has one major drawback: adverse weathercan dramatically reduce the signal strength and make the communicationunreliable [71,72]. One of the most promising solutions to tackle this reliabil-ity issue is to use an RF link in conjunction with the FSO link, e.g. [73{77].The rationale for FSO-RF conjunction is that fog and rain, which can dra-matically reduce FSO and RF link quality respectively, rarely occur at thesame time. In light of results from Chapter 2, in this section we revisit therateless hybrid FSO-RF scheme from [14] and present rate analysis for thecase of general decoding metrics.4.1.1 Channel Coding Diversity Model and Rate AnalysisThe hybrid FSO-RF scheme from [14] is an instance of channel coding di-versity [15]. The block diagram of a channel coding diversity scheme ispresented in Figure 4.1. The diversity channel consists of two individualchannels 1 and 2. There is a single encoder E which controls both of themappers to produce transmit symbols for the individual channels. Cor-924.1. Rateless Hybrid FSO-RF for Last-Mile Accessrespondingly, there is a single decoder D which makes decoding decisionsbased on symbol metrics from the two detectors. We consider indepen-dent discrete-time memoryless individual channels with input and outputrandom variables Xi 2Xi and Yi 2Yi, and channel transition probabilityfunctions pYijXi(yijxi), i = f1; 2g. The detectors produce symbol metricsqXi;Yi(xi;yi) > 0 for all transmit symbols xi 2Xi and received symbolsyi 2 Yi. Following Section 2.1, we consider codebooks of M codewordsx = [x1 x2]. Component xi is a length-Ni sub-codeword whose elementsare to be transmitted via channel i. Let N = N1 +N2 and  i = Ni=N. Asin Section 2.1, the word error probability, averaged over all codewords andrandom codebook realizations, is upper bounded asP  M 2Yi=1EXi;Yi8<:0@Xxi2XipXi(xi) qXi;Yi(xi;Yi)qXi;Yi(Xi;Yi) s1A 9=;Ni: (4.1)In parallel with (2.4), (2.5), and (2.6), the above equation can be written asP  2 NEr(R); (4.2)withR, logMN ; (4.3)the random coding exponentEr(R) , max0   1 maxs>0  E0( ;s)  R ; (4.4)934.1. Rateless Hybrid FSO-RF for Last-Mile Accessand the generalized Gallager function of the diversity channelE0( ;s) , 1E0qX1;Y1( ;s) + 2E0qX2;Y2: (4.5)In (4.5), E0qXi;Yi( ;s), i = f1; 2g is the generalized Gallager function ofthe individual component channel i de ned by (2.6). Similarly to (2.7) and(2.8), the GMI and I-curve of the diversity channel areIgmi , maxs>0 I(s) ; (4.6)andI(s) =  1IqX1;Y1(s) + 2IqX2;Y2(s) : (4.7)Again, IqXi;Yi(s) is the I-curve of the individual channel de ned by (2.8).Let ri be the baud rate4 of channel i, we can also de ne the I-curve of thediversity channel asI(s) = r1IqX1;Y1(s) +r2IqX2;Y2(s) : (4.8)The GMI (4.6) is now measured in bits per time unit.Let IgmiqXi;Yi be the individual GMI of channel i. Interestingly, from (4.6)4Or symbol rate, which is the inverse of the symbol period.944.1. Rateless Hybrid FSO-RF for Last-Mile AccessFSORFmappermapperFSORFchannelchannelFSORFdetectordetectordemultiplexerEbitsmessageDmultiplexerreceivertransmitterFigure 4.2: Rateless BICM hybrid FSO-RF communication system.and (4.8), it follows thatIgmi = maxs>0 r1IqX1;Y1(s) +r2IqX2;Y2(s)  r1 maxs>0 IqX1;Y1(s) +r2 maxs>0 IqX2;Y2(s)= r1IgmiqX1;Y1+r2IgmiqX2;Y2:That is, the GMI of the diversity channel is less than or equal to the baud-rate weighted sum of the individual channels’ GMIs. EqualityIgmi = r1IgmiqX1;Y1+r2IgmiqX2;Y2: (4.9)holds if and only if the individual I-curves are harmonic, see Theorem 2.1.In BICM with channel coding diversity as the hybrid scheme in [14] andpresented in Figure 4.2, each I-curve IqXi;Yi(s), i =f1; 2g, is in turn equal tothe sum of the binary I-curves in that channel. Furthermore, we can applymetric manipulation methods from Section 2.3 to increase the individualchannel’s or the diversity channel’s BICM GMI.954.1. Rateless Hybrid FSO-RF for Last-Mile Access4.1.2 Numerical ExamplesThe BICM hybrid FSO-RF scheme from [14] uses rateless codes, which canseamlessly and simultaneously utilize each of the links’ resources.40 60 80 100 120 140 160406080100120140160Throughput[Mbps]→GMI [Mbps]→Figure 4.3: Scatter plot of throughput vs. GMI for 1000 codewords over thehybrid (diversity) FSO-RF scheme.In the  rst numerical example, we consider the same scenario as in [14]with matched metrics. Thus, all binary I-curves are aligned at s = 1 andequality (4.9) holds. The FSO link uses on-o keying (OOK) with symbolperiod of 10 ns. The photo-counting model (2.47) applies with backgroundradiation  b = 39 photons/slot. We assume a moderate transmitter-receiverdistance of 1000 m, wind speed of 5 m/s and a relatively strong turbulencescintillation condition as described in [14, Sec. IV]. In this scenario, the FSO964.1. Rateless Hybrid FSO-RF for Last-Mile Access0 50 100 150 200406080100120140160  GMIThrougputRate[Mbps]→Codewordindex→Figure 4.4: Throughput and GMI during the transmission of 200 consecutivecodewords over the hybrid FSO-RF scheme.transmission experiences a slow fading condition and the value of the GMIIgmiFSO varies from 0 to 1 bpcu. In particular, the FSO channel gain changesfrom 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-QAMwith symbol period of 60 ns. The RF channel is i.i.d. Rayleigh fading andhas an average SNR such that the GMI IgmiRF is 3.0 bpcu. The hybrid, ordiversity, GMI is therefore in the range of 50 Mbps (when the FSO linkis completely \blacked out") to 150 Mbps (when the FSO link achieves itsmaximum rate). We use the same Raptor code from Example 2.1 for codedtransmission. Figure 4.3 shows the scatter plot of throughput vs. the GMI974.1. Rateless Hybrid FSO-RF for Last-Mile Accessfor 1000 codewords. It shows that the rateless code consistently achieves athroughput close to the GMI. The ability of the rateless code to seamlesslyadapt to the channel quality is further illustrated by the plot of throughputand GMI during the transmission of 200 consecutive codewords in Figure 4.4.This numerical evidence shows that rateless coding is suitable for last-milehybrid FSO-RF communications.In the second numerical example, we demonstrate the use of approximatemetrics. 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 theGMI of the RF link is 2.0 bpcu. The FSO link now uses 64-PPM with a baudrate equal to 1.5 times the baud rate of the RF link. The photo-countingmodel (2.47) applies with  b = 2:44 photons/slot. This new value of  bre ects the changes in the FSO modulation format and baud rate comparedto the previous example. We consider the max-log metric (2.51) with SNRsuch that the GMI of the FSO link is also 2.0 bpcu. The BICM I-curves ofthe individual channels are shown in Figure 4.5. We see that they attaintheir peaks at di erent 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 diversitychannel 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 aGMI of 4:86 bits/TRF. Now, if we scale all the FSO LLR values by 0:675 andall the RF LLR values by 1:225, the FSO and RF I-curves will attains their984.2. Multipulse Pulse-Position Modulationpeak at the same critical point s = 1. The resulting I-curve of the diversitychannel Iscaled(s) is plotted in Figure 4.6 with a GMI of 5:0 bits/TRF. Thatis, equality (4.9) holds. Below each I-curve in Figure 4.6, we plot a markerwhich represents the throughput by the Raptor code from Example 2.1. Thetransmission with max-log metrics attains a throughput of 4:37 bits/TRFwhereas the transmission with scaled max-log metrics attains a signi cantlyhigher throughput of 4:62 bits/TRF. We perform a further simulation whereall the FSO and RF LLR values is scaled by 0:775. This scaling shifts thepeak of the I-curve of the diversity channel to s = 1, but leaves the GMIremains at 4:86 bits/TRF. Now, the transmission attains a throughput of4:49 bits/TRF, which is still lower than the case where both the individualI-curves achieve their peaks at the same s = 1. Thus, our GMI analysisindeed re ects the performance of actual coded transmission.4.2 Multipulse Pulse-Position ModulationIn this section we consider multipulse pulse-position modulation (MPPM)as a power- and bandwidth-e cient format for FSO. This modulation can beused 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 e ciency, but it has low powere ciency. In addition, its possible long sequences of on and o slots are notfavorable to synchronization. On the other hand, PPM has higher powere ciency but lower bandwidth e ciency. MPPM has been proposed as awell-suited format for intensity modulation [16] with a balanced trade-o be-994.2. Multipulse Pulse-Position Modulation0.5 0.675 1 1.225 1.51.51.61.71.81.922.12.2s→Rate[bpcu]→IFSO(s) IRF(s)Figure 4.5: BICM I-curve of individual FSO and RF channels.tween power and bandwidth e ciencies. Its regulated pulsed and non-pulsedslots is also friendly to synchronization. In this section, we investigate thecombination of ECC with MPPM to realize power- and bandwidth-e cientFSO transmission. In particular, we are interested in the application of bi-nary ECC schemes for which a large number of powerful codes have beendeveloped. One di culty with this approach is that the sizes of w-pulsen-slot MPPM constellations are  nw , which are not powers of 2. Thus,bit-to-symbol mapping can be complicated. A common-sense solution isdecimating the constellations to the nearest power-of-2 sizes. Since thisin turn reduces bandwidth e ciency, (at least) two questions immediatelyarise. First, under what circumstances would MPPM indeed o er notable1004.2. Multipulse Pulse-Position Modulation0.5 0.775 1 1.25 1.54.24.44.64.855.2s→Rate[bits/TRF]→I(s)Iscaled(s)Figure 4.6: BICM I-curve and coded throughput of hybrid (diversity) chan-nel.throughput or power e ciency gains over the popular alternative PPM for-mat? Second, how can those gains be realized by practical ECC schemes?To address the  rst question, MPPM and PPM have been comparedbased on di erent criteria and under various transmission conditions, cf.e.g. [16,62,80{85]. It has been shown that although MPPM can potentiallybe two times more bandwidth e cient than PPM with the same power ef- ciency [16], considerable throughput gains are only present for high signalpower and duty cycle w=n [62, 80]. In terms of error-rate performance, itwas recognized that no PPM or MPPM constellation is universally superiorto all the others, and that di erent modulation formats are preferable under1014.2. Multipulse Pulse-Position Modulationdi erent transmission constraints, such as peak- or average-power or band-width constraints [83]. Hence, before designing speci c ECC schemes forMPPM, a careful selection of appropriate MPPM constellations is needed.As for the second question, we note that several coding schemes havebeen studied for MPPM. Analytical results for Reed-Solomon coded MPPMwere given in [80{82, 86]. Sato et al. [82] also analyzed the performance ofconvolutional coded 2-pulse MPPM and investigated the e ect of imperfectslot synchronization on the error rate performance. The combination oftrellis-coded modulation (TCM) with 2-pulse MPPM was outlined in [83]. Amore detailed description of TCM with 2-pulse MPPM, including asymptoticcoding gain calculation, was given in [87]. Serially concatenated TCM wasalso considered for 2-level 2-pulse MPPM (each of the two pulses can taketwo values) in [88]. It should be noted that none of these ECC schemesis capacity-approaching. Hence a signi cant performance gain is left to berealized. 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 theapplication of coded MPPM. Firstly, we compare MPPM with PPM interms of achievable data rate under simultaneous peak power, average power,and bandwidth constraints. A similar comparison has been performed byHamkins and Moision [62]. However, they considered full-sized MPPM con-stellations and mostly focused on low duty-cycle modulations for deep-spacecommunication, where MPPM’s throughput gains are very limited. Ourcomparison here focuses on high duty-cycle and thus bandwidth-e cientMPPM with decimated constellations suitable for coded transmission. Sec-1024.2. Multipulse Pulse-Position Modulationondly, we investigate the application of binary ECC to MPPM using suchdecimated constellations. In particular, we design BICM and MLC schemesfor MPPM. We  nd that BICM is only an appropriate ECC scheme forMPPM at relatively high SNR, whereas MLC can attain a signi cantlyhigher throughput at lower SNR values.4.2.1 Constellation SelectionEach (n;w)-MPPM symbol is represented by a vector x = [x1:::xn] of nelements, each of which is transmitted in one slot, and 1 < w  bn=2celements of 1 and the others are 0. We use the photo-counting model (2.47).The SNR is de ned as  = (w=n) s= b. The channel transition probabilityisp(yjx)/ 1 +  s b <y;x>: (4.11)The notation < y;x > denotes the inner product between y and x, whichturns out to be the sum of the elements of y at the locations of the non-zeroelements of x. We assume uniform input distribution. The constellation-constrained channel capacity isC(X) = 1nI(X;Y) [bits/slot] : (4.12)The set U of all distinct (n;w)-MPPM symbols has sizeMmax = nw = n!w!(n w)! ; (4.13)which is never a power of 2. Since constellations of sizes M = 2m, m2Z, are1034.2. Multipulse Pulse-Position Modulationpreferred for coded transmission, we will use only a decimated constellationX  U of M < Mmax distinct symbols. We now turn to the problem ofselecting \good" MPPM constellations. Our approach consists of two steps.First, we determine parameters (n;w;M) such that MPPM transmissionwith a corresponding setX potentially o ers throughput gains compared toPPM under the same transmission constraints. Then, we obtain the set Xfrom decimation of the full-size MPPM setU 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 requireidentical duty cycles 1= = w=n, where  is the peak-to-average powerratio (PAPR), and the bandwidth constraint is accounted for by measuringthroughput in bits per slot. The \OOK bound"  =H(1= ), where H( ) isthe binary entropy function, upper bounds the MPPM throughput for givenPAPR  [80]. Furthermore, an n-slot PPM constellation has  = n and = (log )= .Figure 4.7 shows the power-bandwidth e ciency chart for MPPM con-stellations with M 256 and   (log )= . There are 89 triplets (n;w;M)satisfying these conditions. Each triplet (n;w;M) is presented as a pointin the  gure, and several (n;w;M) triplets may take the same point. In-cluded are the upper \OOK bound"  = H(1= ) and the lower \PPMbound"  = (log )= . With this  gure, we are able to locate the param-eters (n;w;M) of MPPM constellations that o er both high power andbandwidth e ciencies. For example, if we want a transmission which re-quires  to be around 4.0 we could select one of the three constellations1044.2. Multipulse Pulse-Position Modulation2 4 6 8 10 12 14 160.20.30.40.50.60.70.80.91τ[bits/slot]−→OOKbound τ =H(1/ρ)ρ−→PPMbound τ =log(ρ)/ρ(12,3,128)(133,256)(11,3,128)Figure 4.7: Power-bandwidth e ciency chart of MPPM. Parameter sets aretriplets (n;w;M).where (n;w;M) equals (11;3;128) , (13;3;256), or (12;3;128), for whichMmax =  nw = 165, 286, and 220, respectively.4.2.2 Subset SelectionHaving determined the MPPM constellation parameters, we need to decidewhich M out of the Mmax symbols are to be used. Selection of subsetsbased on symbol-error rate or avoidance of long sequences of zeros and oneshas been considered in [83, 86, 87]. As mentioned above, here we use theconstellation-constrained channel capacity C(X) as the relevant criterion.1054.2. Multipulse Pulse-Position ModulationTherefore, we formulate subset selection as a combinatorial optimization(CO) problem:Maximize: C(X)subject to:X U and jXj= M(4.14)Since the solution of this CO problem with the objective function C(X) from(4.12) seems to require total enumeration, we aim at a possibly suboptimalsolution using CO search algorithms.Search AlgorithmsWe now brie y describe the three popular search algorithms, whose pseudo-code are presented in Figures 4.8, 4.9, and 4.10. All algorithms excecute Nsearch iterations. Further details can be found in [89].// Random search1: Randomly select X2: for i = 1:::N do3: Randomly select X04: if (C(X0) >C(X)) then5: X =X06: end if7: end for8: Return XFigure 4.8: Pseudo-code for random search.Random search: In each iteration, a new trial solution is generated byrandomly picking M elements of U. The result is the best of all trials.Greedy ascent: The search starts with a random initial solution. Ineach iteration, greedy ascent tries to replace only one MPPM symbol inthe solution by another one that would improve the quality of the solution.1064.2. Multipulse Pulse-Position Modulation// Greedy ascent1: Randomly select X2: for i = 1:::N do3: V =UnX4: Select x2X and v2V5: X0 =fX;vgnfxg (i.e. replace x by v in X)6: if (C(X0) >C(X)) then7: X =X08: end if9: end for10: Return XFigure 4.9: Pseudo-code for greedy ascent.In this way, the good structure of the best-so-far solution is exploited ingenerating new trail solutions.Simulated annealing: For a di cult search landscape, the greedy as-cent solution would eventually be trapped into a local maximum and nofurther improvement could be attained. Simulated annealing [90] is one ofthe metaheuristical algorithms where the search can probabilistically escapelocal maxima. Simulated annealing is deduced from the physical anneal-ing process of solid materials. Its solution asymptotically approaches theglobal maximum. Simulated annealing requires the speci cation of a startand end temperature from which the cooling coe cient  is derived. Thesevalues can be determined by inspecting the annealing curve of the searchproblem [91].CWC-Based SearchFor the CO algorithms, focusing the search in \good" regions of the signalspace can improve the quality of the result. To this end, we observe that1074.2. Multipulse Pulse-Position Modulation// Simulated annealing1: Randomly select X2: Best solution ^X =X3: Initial temperature T4: for i = 1:::N do5: V =UnX6: Select x2X and v2V7: X0 =fX;vgnfxg8:  = C(X) C(X0)9: Generate uniform random number r in (0,1)10: if ( < 0 or r< e  T) then11: X =X012: end if13: if (C(X0) >C( ^X)) then14: ^X =X015: end if16: Cool down: T =  T with  < 117: end for18: Return ^XFigure 4.10: Pseudo-code for simulated annealing.MPPM symbols can be considered as the codewords of a length-n weight-wconstant-weight code (CWC). We argue that optimized CWCs with a largeminimum 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]), thefollowing approach is applied: (i)  nd a constant-weight code U0 with largedmin and size A close to M; (ii) if A  M then replace U in the searchalgorithms by U0, i.e. we search only within the CWC; otherwise, we makeX always contain U0.1084.2. Multipulse Pulse-Position ModulationNumerical ResultWe consider the case (n;w;M) = (12;3;128), for which the set of all dis-tinct MPPM symbols U has size Mmax = 220. For the Poisson channelwith  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-basedstrategy, to  nd a constellation X 2U of size M = 128 which yields thebest C(X). We perform the optimization at SNR of 6.9 dB, at whichC(U) = (1=n) logM. Surprisingly, all the search algorithms result in constel-lations that have similar value C(X) (4.12). This suggests that in practicewe can use the simplest algorithm, namely random search5. Having the op-timized constellation by random search, we add the plot of C(X) vs. SNR toFigure 4.11. It shows that this constellation also yields good C(X) over thewhole range of SNR. For comparison, the constrained channel capacity for4-PPM is included, which has the same PAPR of  = 4:0. We observe thatthe selected (12;3;128) MPPM constellation always outperforms 4-PPM forthe entire range of the SNR value.4.2.3 Labeling and Binary-Coded ModulationWith a good MPPM constellation X, we now consider the combination ofMPPM with binary coding. We start with the simpler scheme of BICM.5We further test the algorithms for (n;w;M) = (16;4;128) and (16;4;256) with severaltransmission scenarios and also  nd that the CWC-based random search algorithm yieldsgood results in these cases.1094.2. Multipulse Pulse-Position Modulation3 4 5 6 7 8 9 100.250.30.350.40.450.50.550.60.65C(U)4-PPMCapacity[bits/slot]−→C(X)γ [dB] −→Figure 4.11: Constrained channel capacity of MPPM constellations.Given X, the BICM GMI depends on the labeling LIbicm(L) = 1nm 1Xi=0I(Bi;Y) : (4.15)Our goal is to  nd a labeling that maximizes Ibicm(L). Due to the largesearch space and the high computational cost to estimate the objective func-tion Ibicm(L), this is again a di cult CO problem. Therefore, we take anindirect approach as below.Generally, Gray labeling is suggested for BICM [3, 53], cf. also [95]. InGray labeling, the labels of nearest-neighbor signal points di er at only one1104.2. Multipulse Pulse-Position Modulationposition. For MPPM, where adjacency is measured in terms of Hammingdistance between signal vectors, we may not be able to construct a Graylabeling. This is because a necessary condition for the existence of a Graylabeling is that the number of nearest-neighbor signal points to any signalpoint 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 hasbetween 11 and 19 nearest neighbors, whereas m = 7. We therefore attemptto  nd labelings L that are \as Gray as possible." To this end, we considerthe CO problemMimimize: fG(L) = 1MMXi=11jN(xi)jXxj2N(xi)dH(bi;bj) ;subject to:fbi2f0;1gmji = 1;:::;Mg;(4.16)where N(xi) is the set of the nearest neighbors of xi, bi is the label of xi,and dH(bi;bj) denotes the Hamming distance between labels bi and bj. Wenote that the cost function fG(L)  1 is the average Hamming distancebetween labels of nearest-neighbor symbols, and fG(L) = 1:0 if and only ifL is a Gray labeling. Incidentally, a similar cost function has been appliedin [96, Eqs. (4), (5)] for a BICM scheme with RF signaling over AWGNchannels.Finding the optimal solution of (4.16) might still require the prohibitivetotal enumeration. We therefore propose a \local search with best improve-ment and random restart" algorithm, which we refer to as Algorithm 1 inthe following. The pseudo-code of the algorithm is listed in Figure 4.12.1114.2. Multipulse Pulse-Position Modulation// Gray labeling search1: Generate random labeling L2: Best-so-far labeling ^L=L3: for t = 1:::N do4: L0 = argmini;j=0:::M 1ffG(L0) :L0 = S(L;i;j);i6= jg5: if (fG(L0) <fG(L)) then6: L=L07: else8: Generate new random labeling L9: end if10: if (fG(L) <fG( ^L)) then11: ^L=L12: end if13: end for14: Return ^LFigure 4.12: Pseudo-code for Gray labeling search. S(L;i;j) denotes thelabel-swapping operation applied on L such that the labels of the i-th andj-th symbols are swapped.Figure 4.13 (line (b)) shows the BICM GMI corresponding to the optimizedlabeling for the (12;3;128) constellation from Section 4.2.1 and N = 1000search steps in Algorithm 1. To illustrate the e ectiveness of Algorithm 1, wealso compare the result with labelings found by a search over 1000 randomlygenerated labelings (line (c) in Figure 4.11). We observe that the Gray-likelabeling obtained from using (4.16) with Algorithm 1 signi cantly improvesthe 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 anotable gap to the constrained capacity (line (a)), especially at medium-to-low SNR values. We therefore propose RL-MLC architecture, which makesuse of the BICM-optimized labeling, and is able to narrow this gap (line (d)and (e)). The MLC con gurations for line (d) and (e) are h = [1 1 1 1 2 2 2]1124.2. Multipulse Pulse-Position Modulation3 4 5 6 7 8 9 100.10.20.30.40.50.6  (a)(b)(c)(d)(e)(f)(g)Rate[bits/slot]−→γ [dB] −→Figure 4.13: Constrained capacities or GMIs of MPPM transmission: (a)C(X) with (n;w;M) = (12;3;128) by a random search; (b) BICM GMI withGray-like labeling obtained with Algorithm 1 (Figure 4.12); (c) BICM GMIwith labeling from a random search; (d) GMI of a 2-layer MLC; (e) GMIof a 3-layer MLC. For comparison, (f) and (g) are the constrained capacityand 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 havearrived at the MLC schemes via two greedy optimization stages:  ndinga labeling that maximizes the BICM GMI, and then determining an MLCcon guration that maximizes the MLC GMI for this labeling. Nevertheless,the results in Figure 4.13 indicate that there is only little room for possibleimprovement by a joint optimization of labeling and MLC con gurations.1134.3. Conclusion4.3 ConclusionIn this chapter, we  rst revisited the rateless BICM scheme for hybrid FSO-RF transmission and showed a new approach to rate analysis via the conceptof the I-curve. In the second part, we presented the design process for codedMPPM transmission. In particular, we considered the two fundamentalquestions of when MPPM is preferable over PPM and how MPPM couldbe combined with ECC. To this end, we compared MPPM and PPM FSOtransmission under simultaneous limited peak-power, average power, andbandwidth constraints. We then devised decimation and labeling strategiesfor the application of binary ECC to MPPM. It has been found that BICMGMI leaves a notable gap to the constrained channel capacity at medium-to-low SNR range, which can be bridged by MLC schemes with only severalencoder-decoder pairs.114Chapter 5Concluding Remarks5.1 Summary of ContributionsSince binary-coded modulation is the current de facto coding standard fordigital communication systems, and since practical implementations of suchsystems almost certainly use some low-complexity approximate metrics, thescope and results of this thesis are particularly interesting and relevant toprofessionals in communications. Our contributions in this thesis range fromlabeling design for a speci c scheme to new insights that are useful forimproving the performance of many practical systems and have implicationsbeyond the binary coding framework. In the following, we summarize ourmain contributions with remarks on their impacts and some ideas for furtherresearch. Relationship between the I-curve and SBS throughput performance:The I-curve is derived from the generalized Gallager function, which isin turn derived from the random coding argument with word decoding.Its peak value, the GMI, has been routinely used in the literature as anupper bound to the throughput performance of SBS decoding. In thisthesis we further discovered an intriguing in uence of the critical point1155.1. Summary of Contributionsof the I-curve on the performance of SBS decoding, cf. Example 2.1. I-curve decomposition: We showed that the I-curve of a compoundchannel is equal to the baud-rate weighted sum of the individual chan-nels’ I-curves. In Section 2.2, this decomposition is between the BICMchannel and the virtual binary channels of the levels, regardless of theinput distribution pX(x). The same result has been reported in [9]for uniform input. In Section 4.1, the decomposition is between thecoding diversity channel and the component physical channels. Metric scaling: We discovered in Section 2.3.1 and 2.3.2 that metricscaling with a constant factor in the logarithmic domain can shiftthe critical point of the I-curve without a ecting the GMI. Togetherwith the two above contributions, this  nding leads to a versatile andvery practical metric manipulation method that can improve codedperformance in a wide range of mismatched transmission scenarios. Multidimensional metric correction functions for BICM: By consider-ing the BICM approximate detector as part of a cascaded channel, wenaturally arrived at metric mismatch correction functions for BICM.These functions can be practical in certain situations, and in generalshed new light on the upper GMI limit of BICM with mismatcheddecoding metrics, cf. Section 2.3.3. Reduced-layer and rateless MLC: The two main drawbacks of MLCare its structural complexity and the need to carefully design code ratefor each layer to realize its performance gains compared to BICM. Our1165.2. Suggested Future Workcontributions in Chapter 3 can alleviate both of these drawbacks. Withthe reduced-layer coding concept, we can design MLC schemes withany number of coding layer. Next, using our rateless MLC scheme, wecan preserve the rate advantage of MLC while not having to designindividual codes for each coding layer. Design of MPPM signaling: We showed a systematic design processfor MPPM signaling in Section 4.2. Unlike previous studies on theapplication of MPPM, we start by identifying parameters which po-tentially yield better performances compared to MPPM’s main com-peting modulation formats. Then, using suitable optimization tools,we select decimated constellations and symbol labels that return goodachievable rates in BICM and MLC schemes.5.2 Suggested Future WorkPerhaps the most interesting unsolved problem that has been opened upby this thesis is to  nd a rigorous theoretical explanation for the variationof the achieved SBS decoding throughput versus the critical point of theI-curve, as illustrated in Example 2.1. In particular, a solution to this prob-lem should explain why the SBS decoding throughput approaches the GMIwhen sqX;Y = 1, but only IqX;Y (1) when sqX;Y > 1. It should also lead toan 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 andMLC are generic and applicable to many practical systems with mismatched1175.2. Suggested Future Workdecoding metrics. Speci cally, the achievable rates by these systems can bemeasured in terms of the GMI, and metric correction methods from thisthesis can be applied to increase both the GMI and throughput performanceby SBS decoding. Examples of such systems are wireless communicationswith simpli ed metrics, orthogonal-frequency division multiplexing (OFDM)systems with exceeding peak-to-average power ratio (PAPR), and multiuserdetection.118Bibliography[1] S. Haykin, Communication Systems, 4th ed. New York, NY: Wiley,2000.[2] E. Zehavi, \8{PSK trellis codes for a Rayleigh channel," IEEE Trans.Commun., vol. 40, no. 5, pp. 873{884, May 1992.[3] G. Caire, G. Taricco, and E. Biglieri, \Bit-interleaved coded modula-tion," IEEE Trans. Inf. Theory, vol. 44, pp. 927{946, May 1998.[4] H. Imai and S. Hirakawa, \A new multilevel coding method using errorcorrecting codes," IEEE Trans. Inf. Theory, vol. 23, pp. 371{377, 1977.[5] U. Wachsmann, R. Fischer, and J. B. Huber, \Multilevel codes: theo-retical concepts and practical design rules," IEEE Trans. Inf. Theory,vol. 45, no. 5, pp. 1367{1391, Jul. 1999.[6] S. Hranilovic, Wireless Optical Communication Systems. Springer,2005.[7] A. K. Majumdar and J. C. Ricklin, Eds., Free-Space Laser Communi-cations: Principles and Advances. Springer, Dec. 2010.119Bibliography[8] A. Guill en i F abregas, A. Martinez, and G. Caire, \Bit-interleavedcoded 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, \Bit-interleaved coded modulation revisited: A mismatched decoding per-spective," IEEE Trans. Inf. Theory, vol. 55, no. 6, Jun. 2009.[10] G. Kaplan and S. Shamai, \Information rates and error exponents ofcompound channels with application to antipodal signaling in a fadingenvironment," Archiv Elektronik  Ubertragungstechnik (AE  U), vol. 47,no. 4, pp. 228{239, 1993.[11] N. Merhav, A. Lapidoth, and S. Shamai, \On information rates formismatched decoders," IEEE Trans. Inf. Theory, vol. 40, no. 6, pp.1953{1967, 1994.[12] L. Lampe, R. Schober, and R. Fischer, \Multilevel coding for multiple-antenna transmission," IEEE Trans. Wireless Commun., vol. 3, pp.203{208, Jan. 2004.[13] A. Shokrollahi, \Raptor codes," IEEE Trans. Inf. Theory, vol. 52, no. 6,pp. 2551{2567, Jun. 2006.[14] A. AbdulHussein, A. Oka, T. T. Nguyen, and L. Lampe, \Rateless cod-ing for hybrid free-space optial and radio-frequency communication,"IEEE Trans. Wireless Commun., vol. 9, no. 3, pp. 907{913, Mar. 2010.120Bibliography[15] J. N. Laneman, E. Martinian, G. W. Wornell, and J. G. Apostolopou-los, \Source-channel diversity for parallel channels," IEEE Trans. Inf.Theory, vol. 51, no. 10, pp. 3518{3539, 2005.[16] H. Sugiyama and K. Nosu, \MPPM: a method for improving the band-utilization e ciency in optical PPM," J. Lightwave Tech., vol. 7, no. 3,pp. 465{472, Mar. 1989.[17] S. H. Muller-Weinfurtner, \Coding approaches for multiple antennatransmission 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-likelihoodreceiver for MIMO bit-interleaved coded modulation," IEEE Commun.Lett., vol. 8, no. 2, pp. 105{107, Feb. 2004.[19] M. R. McKay and I. B. Collings, \Capacity and performance of MIMO-BICM with zero-forcing receivers," IEEE Trans. Commun., vol. 53,no. 1, pp. 74{83, Jan. 2005.[20] ||, \Error performance of MIMO-BICM with zero-forcing receiversin spatially-correlated rayleigh channels," IEEE Trans. Wireless Com-mun., vol. 6, no. 3, pp. 787{792, Mar. 2005.[21] I. B. Collings, M. Butler, and M. McKay, \Low complexity receiverdesign for MIMO bit-interleaved coded modulation," in Proc. IEEEISSTA, Aug.-Sep. 2004, pp. 12{16.121Bibliography[22] D. Seethaler, G. Matz, and F. Hlawatsch, \An e cient MMSE-baseddemodulator for MIMO bit-interleaved coded modulation," in Proc.IEEE GLOBECOM, vol. 4, Nov.-Dec. 2004, pp. 2455{2459.[23] R. Gha ar and R. Knopp, \Low complexity metrics for BICM SISOand 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 informa-tion of BICM systems with approximate demodulation," in IEEE Inf.Theory Workshop, Cairo, Egypt, Jan. 2010.[25] D. Divsalar, H. Jin, and R. J. McEliece, \Coding theorems for turbo-likecodes," 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," IEEETrans. Inf. Theory, vol. 27, no. 5, pp. 533{547, Sep. 1981.[28] D. J. C. MacKay, \Good error-correcting codes based on very sparsematrices," IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399{431, 1999.[29] T. Richardson and R. Urbanke, \The capacity of low-density parity-check codes under message-passing decoding," IEEE Trans. Inf. The-ory, vol. 47, no. 2, pp. 599{618, Feb. 2001.[30] S. Chung, G. Forney, T. Richardson, and R. Urbanke, \On the design oflow-density parity-check codes within 0.0045 dB of the Shannon limit,"IEEE Commun. Lett., vol. 5, no. 2, pp. 58{60, 2001.122Bibliography[31] W. E. Ryan, \An introduction to LDPC codes," in CRC Handbook forCoding and Signal Processing for Recording Systems. CRC Press, 2004.[32] O. Etesami and A. Shokrollahi, \Raptor codes on binary memorylesssymmetric 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," IEEECommun. Lett., vol. 10, no. 1, pp. 46{48, Jan. 2006.[34] R. G. Gallager, Information Theory and Reliable Communication. NewYork, NY: Wiley, 1968.[35] I. Sason and S. Shamai, \Performance analysis of linear codes undermaximum-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 andthe sum-product algorithm," IEEE Trans. Inf. Theory, vol. 47, no. 2,pp. 498{519, 2001.[37] M. Luby, \LT codes," in Proc. 43rd IEEE Symp. Found. Comp. Sc.(FOCS), Vancouver, BC, Canada, Nov. 2002, pp. 271{280.[38] X.-Y. Hu, E. Eleftheriou, and D. Arnold, \Regular and irregular pro-gressive edge-growth Tanner graphs," IEEE Trans. Inf. Theory, vol. 51,no. 1, pp. 386{398, Jan. 2005.123Bibliography[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. P ster, \Capacity-approachingbandwidth-e cient coded modulation schemes based on low-densityparity-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-densityparity-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 propagationfor decoding LDPC codes in the presence of channel estimation error,"IEEE Trans. Commun., vol. 55, no. 1, pp. 83{89, Jan. 2007.[43] J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu,\Reduced-complexity decoding of LDPC codes," IEEE Trans. Com-mun., vol. 53, no. 8, pp. 1288{1299, 2005.[44] S. G. Lechner and J. Sayir, \Improved sum-min decoding for irregularLDPC codes," in Proc. Intl. Symp. Turbo Codes and Related Topics,Munich, Germany, Apr. 2006.[45] G. Lechner, \E cient decoding techniques for LDPC codes," Ph.D.dissertation, Vienna Univ. of Tech., Jul. 2007.124Bibliography[46] S. Papaharalabos and P. Mathiopoulos, \Simpli ed sum-product al-gorithm for decoding LDPC codes with optimal performance," IEEElectronics 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 ofpipelined 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 ratioclipping in MIMO-BICM systems: Information geometric analysis andimpact on system capacity," in Proc. IEEE ICASSP, Taipei, Taiwan,Apr. 2009, pp. 2433{2436.[50] C. Novak, P. Fertl, and G. Matz, \Quantization for soft-output demod-ulators in bit-interleaved coded modulation systems," in Proc. IEEEIntl. Symp. Inf. Theory (ISIT), Seoul, Korea, Jun. 2009, pp. 1070{1074.[51] C. Studer and H. B olcskei, \Soft-input soft-output single tree-searchsphere decoding," IEEE Trans. Inf. Theory, vol. 56, no. 10, pp. 4827{4842, Oct. 2010.[52] M. van Dijk, A. J. E. M. Janssen, and A. G. C. Koppelaar, \Correct-ing systematic mismatches in computed log-likelihood ratios," Europ.Trans. Telecommun., vol. 14, no. 3, pp. 227{244, 2003.125Bibliography[53] C. Stierstorfer and R. F. H. Fischer, \(Gray) mappings for bit-interleaved coded modulation," in Proc. IEEE Vehicular Tech. Conf.(VTC) Spring, May 2007, pp. 1703 {1707.[54] ||, \Mappings for BICM in UWB scenarios," in Proc. 7th Intl. ITGConf. Source Channel Coding (SCC), Ulm, Germany, 2008.[55] J. Proakis, Digital Communications, 4th ed. New York, NY: McGraw-Hill, 2001.[56] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functionswith Fomulas, Graphs, and Mathematical Tables. New York, NY: DoverPress, 1972.[57] J. Panaro, \Simpli ed soft-output demapper for bit-interleaved codedorthogonal modulation," in Proc. Intl. Conf. Wireless Mobile Com-mun., Jul. 2006.[58] A. Guill en i F abregas and A. J. Grant, \Capacity approaching codesfor non-coherent orthogonal modulation," IEEE Trans. Wireless Com-mun., vol. 6, no. 11, pp. 4004{4013, Nov. 2007.[59] X. Li and J. A. Ritcey, \Bit-interleaved coded modulation with iterativedecoding using soft feedback," Electron. Lett., vol. 34, no. 10, pp. 942{943, 1998.[60] ||, \Trellis-coded modulation with bit interleaving and iterative de-coding," IEEE J. Sel. Areas Commun., vol. 17, no. 4, pp. 715{724, Apr.1999.126Bibliography[61] S. J. Dolinar, J. Hamkins, B. E. Moision, and V. A. Vilnrotter, \Op-tical modulation and coding," in Deep Space Optical Communications,H. Hemmati, Ed. Wiley-Interscience, Apr. 2006.[62] J. Hamkins and B. Moision, \Multipulse pulse-position modulation ondiscrete memoryless channels," JPL Interplanetary Network ProgressReport, vol. 42, p. 161, May 2005.[63] D. J. C. MacKay, Information Theory Inference and Learning Algo-rithms. Cambridge University Press, 2003.[64] U. Wachsmann, Coded Modulation: Theoretical Concepts and PracticalDesign 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, stateof 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.pdf127Bibliography[70] R. Khalona, \Uni ed performance analysis of Reed-Solomon coded M-ary FSK modulation in AWGN, Rician and Rayleigh fading channels,"in Proc. Intl. Conf. Universal Personal Commun. (ICUPC), vol. 2, Oct.1993, pp. 662{668.[71] I. I. Kim and E. Korevaar, \Availability of free space optics (FSO) andhybrid FSO/RF systems," in Proc. SPIE, Optical Wireless Communi-cations IV, vol. 4530, Denver, CO, Aug. 2001, pp. 84{95.[72] J. Pan, M. Evans, T. Euler, H. Johnson, and F. DeNap, \Free-spaceoptical communications: opportunities and challenges from a carrier’sperspective," 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 hybridfree-space optic/radio frequency (FSO/RF) mobile ad-hoc network," inProc. IEEE/RSJ Intl. Conf. Intelligent Robots and Systems, 2005, pp.3990{3996.[75] A. Akbulut, H. Ilk, and F. Ari, \Design, availability and reliabilityanalysis on an experimental outdoor FSO/RF communication system,"in Proc. Intl. Conf. Transparent Optical Networks (ICTON), 2005, pp.403{406.128Bibliography[76] W. Zhang, S. Hranilovic, and C. Chi, \Soft-switching hybrid FSO/RFlinks 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 hybridRF/FSO systems," IEEE Trans. Commun., vol. 57, no. 12, Dec. 2009.[78] J. Massey, \Capacity, cuto rate, and coding for a direct-detectionoptical channel," IEEE Trans. Commun., vol. 29, pp. 1615{1621, 1981.[79] R. McEliece, \Practical codes for photon communication," IEEE Trans.Inf. Theory, vol. 27, pp. 393{398, 1981.[80] M. Takahasi, H. Yashima, I. Sasase, and S. Mori, \Capacity and ef-fects of Reed-Solomon codes on multi-pulse PPM in optical communi-cations," in Proc. IEEE ICC, vol. 4, 1990, pp. 1663{1667.[81] J. M. Budinger, M. J. Vanderaar, P. K. Wagner, S. B. Bibyk, and G. S.Mecherle, \Combinatorial pulse position modulation for power-e cientfree-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-pulsePPM with imperfect slot synchronization in optical direct-detectionchannel," in Proc. IEEE ICC, vol. 1, 2004, pp. 121{125.[83] C. N. Georghiades, \Modulation and coding for throughput-e cientoptical systems," IEEE Trans. Inf. Theory, vol. 40, no. 5, Sep. 1994.129Bibliography[84] M. K. Simon and V. A. Vilnrotter, \Multi-pulse pulse-position modu-lation signaling for optical communication with direct detection," IPNProgress 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 opticalcommunication systems," IEEE Trans. Commun., vol. 42, pp. 574{582,Apr. 1994.[87] H. Park and J. R. Barry, \Trellis-coded multiple-pulse-position modu-lation for wireless infrared communications," IEEE Trans. Commun.,vol. 52, no. 4, pp. 643{651, 2004.[88] A. S. Alahmari, \Turbo coded pulse position modulation for opticalcommunications," Ph.D. dissertation, Georgia Institute of Technology,2003.[89] C. R. Reeves, Ed., Modern Heuristic Techniques for CombinatorialProblems. London, UK: Blackwell Scienti c Publications, Apr. 1993.[90] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, \Optimization by sim-ulated annealing," Science, vol. 220, no. 4598, pp. 671{680, 1983.[91] S. R. White, \Concepts of scale in simulated annealing," in Proc. IEEEICCD, 1984, pp. 646{651.130Bibliography[92] A. Brouwer, J. Shearer, N. Sloane, and W. Smith, \A new table ofconstant 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 constantweight 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-spaceoptical channel: Serially concatenated pulse-position modulation," IPNProgress Report, vol. 42-161, May 2005.[95] V. Sethuraman and B. Hajek, \Comments on \Bit-interleaved codedmodulation"," IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1795{1797,2006.[96] S. Y. Le Go , \Signal constellations for bit-interleaved coded modula-tion," IEEE Trans. Inf. Theory, vol. 49, pp. 307{313, Jan. 2003.131

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 11 2
United States 9 1
Vietnam 9 4
India 8 3
United Kingdom 3 0
Taiwan 3 0
Ukraine 3 0
Hong Kong 3 0
Bangladesh 2 0
Canada 2 0
Pakistan 2 0
Japan 2 0
South Africa 1 0
City Views Downloads
Hanoi 9 4
Unknown 9 10
Beijing 7 1
Mumbai 5 0
Ashburn 5 0
Uxbridge 3 0
Central District 3 0
Columbus 2 0
Islamabad 2 0
San Francisco 2 0
Tokyo 2 0
Dhaka 2 0
Shenzhen 2 1

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

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