Graphical Models and Message Passing Receivers for Interference Limited Communication Systems Marcel Nassar PhD Defense Committee Members: Prof. Gustavo de Veciana Prof. Brian L. Evans (supervisor) Prof. Robert W. Heath Jr. Prof. Jonathan Pillow Prof. Haris Vikalo April 17, 2013 Outline Uncoordinated interference in communication systems Effect of interference on OFDM systems Prior work on receivers in uncoordinated interference Message-passing receiver design Learning interference model parameters: robust receivers Summary and future work Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary

2 Modern Communication Systems Single Carrier System: frequency selective fading || Noise/Interference Channel + 0110010 equalizer

Implementation complexity Orthogonal Frequency Division Multiplexing Noise/Interference (OFDM): Channel 0110010 N sub-bands 0 1 1 0 0 1 0 || + +

Simpler Equalization Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 3 Interference in Communication Systems Wireless LAN in ISM band Co-Channel interference Platfor m Coexisting Protocols NonCommunication Sources Powerline Communication Non-interoperable

standards Electromagnetic emissions Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 4 Interference Management An active area of research Orthogonal Access MAC Layer Access: Co-existence [Rao2002] [Andrews2009] Precoding Techniques: Inter-cell interference cancellation [Boudreau2009], network MIMO (CoMP) [Gesbert2007], Interference Alignment [Heath2013] Successive Interference Cancellation [Andrews2005] What about residual interference? Uncoordinated Interference What about non-communicating sources? What about non-cooperative sources? Complementary approach: statistically model and mitigate

Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 5 Thesis Contributions Contribution I: Uncoordinated Inference Modeling Contribution II: Receiver Design Contribution III: Robust Receiver Design Thesis Statement: Receivers can leverage interference models to enhance decoding and increase spectral efficiency in interference limited systems. Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 6 Uncoordinated Interference Modeling 7 Statistical-Physical Modeling Wireless Systems WiFi, Ad-hoc

[Middleton77, Gulati10] Powerline Systems Middleton ClassA Rural, Industrial, Apartments [Middleton77,Nassar11] A Impulsive Index Mean Intensity WiFi Hotspots [Gulati10] Gaussian Mixture (GM) Dense Urban, Commercial [Nassar11] : # of comp. comp. probability comp. variance Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary

8 Empirical Modeling WiFi Platform [Data provided by Intel] 0 Gaussian Mixture Model: Tail Probabilities [P(X > a)] 10 -5 10 -10 10 Empirical

Middleton Class A Symmteric Alpha Stable Gaussian Gaussian Mixture Model -15 10 -20 10 0 1 2 3 4 5 6

7 8 9 Threshold Amplitude (a) Gaussian HMM Model: 1 2 ( 0, 21 ) ( 0, 22 ) Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 9 Empirical Modeling Powerline Systems Markov Chain Model 1 [Zimmermann2002]

1 2 1 2 Measurement Data [Katayama06] Impulsiv e Proposed Model 5 Backgrou nd Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 10

Receiver Design 11 OFDM Basics System Diagram LDPC Coded Symbol Mapping noise + interference || Inverse DFT Sourc e 0111

DFT + 1+i 1-i -1-i 1+i Noise Model channel Receiver Model After discarding the cyclic prefix: wher e and total background noise noise interference GM or GHMM

After applying DFT: Subchannels: Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 12 Effect of GM Interference on OFDM Single Carrier (SC) Carrier vs. OFDMOFDM Single (symbol by symbol decoding) DFT Impulse energy spread out Impulse energy concentrated Symbol lost ?? Symbol lost with high probability Symbol errors dependent

Symbol errors independent Disjoint minimum distance is Min. distance decoding is MAPImpulse energy high Impulse energy low optimal sub-optimal OFDM sym. OFDM sym. lost recovered Minimum distance decoding Disjoint minimum distance under GM: decoding: In theory, with joint MAP decoding OFDM Single Carrier [Haring2002] tens of dBs Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 13 OFDM Symbol Structure

Coding Added redundancy protects against errors Data Tones Symbols carry information Finite symbol constellation Adapt to channel conditions Pilot Tones Known symbol (p) Used to estimate channel Null Tones Edge tones (spectral masking) Guard and low SNR tones Ignored in decoding estimation symbol

detection pilots linear channel decoding But, there is unexploited information and dependencies Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 14 Prior Work Category TimeDomain preprocessin g Sparse Signal Reconstructi on Iterative Receivers

Referenc es Method [Haring2001] Time-domain signal MMSE estimation [Zhidkov200 8,Tseng2012] Time-domain signal thresholding [Caire2008,L ampe2011] Compressed sensing [Lin2011]

Sparse Bayesian Learning [Mengi2010, Yih2012] Iterative preprocessing & decoding Limitations ignore OFDM signal structure performance vs DFT rx degrades with increasing SNR and modulation order utilize only known tones dont use interference models complexity Suffer from preprocessing limitations Ad-hoc design

[Haring2004] Turbo-like All dont consider the non-linear channel estimation, and dont receiver use code structure Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 15 Joint MAP-Decoding The MAP decoding rule of LDPC coded OFDM is: Can be computed as follows: depends on linearly-mixed non iid & N noise samples and L non-Gaussian channel taps LDPC code Very high dimensional integrals and summations !!

Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 16 Belief Propagation on Factor Graphs Graphical representation of pdf-factorization Two types of nodes: variable nodes denoted by circles factor nodes (squares): represent variable dependence Consider the following pdf: Corresponding factor graph: Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 17 Belief Propagation on Factor Graphs Approximates MAP inference by exchanging messages on graph Factor message = factors belief about a

variables p.d.f. Variable message = variables belief about its own p.d.f. Variable operation = multiply messages to update Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 18 p.d.f. Coded OFDM Factor Graph unknown channel taps Unknown interferenc e samples Symbol Informatio Coding & s n bits Interleavin Bit loading Received & g Symbols Introduction |Messagemodulatio

Passing Receivers | Simulations | Robust Receivers| Summary n 19 BP over OFDM Factor Graph MC Decoding LDPC Decoding via BP [MacKay2003] Node degree=N+L!!! Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 20 Generalized Approximate Message Passing [Donoho2007,Rangan2010] Estimation with Linear variabl observatio Mixing

ns coupli ng Decoupling via Graphs es Generally a hard problem due to coupling Regression, compressed sensing, Interference channel OFDM systems: subgraph subgraph given given and and If graph is sparse use standard BP If dense and large

Central Limit Theorem At factors nodes treat as Normal Depend only on means and variances of incoming messages Non-Gaussian output quad 3 types of output channels for approx. each Similarly for variable nodes Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 21 Series of scalar MMSE estimation Proposed Message-Passing Receiver GA M P Schedule LDPC Dec. GA

M P Initially uniform Turbo Iteration: 1. coded bits to symbols 2. symbols to 3. Run channel GAMP 4. Run noise equalizer 5. to symbols 6. Symbols to coded Equalizer Iteration: bits 1. GAMP 7. Run noise LDPC decoding 2. MC Decoding 3. Repeat Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary

22 Receiver Design & Complexity Design Freedom Not all samples required for sparse interference estimation Receiver can pick the subchannels: Information provided Complexity of MMSE estimation Selectively run subgraphs Monitor convergence (GAMP variances) Complexity and resources GAMP can be parallelized effectively Operation MC Decoding LDPC Decoding GAMP

Complexity per iteration Notation : # tones : # coded bits : # check nodes : set of used tones Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 23 Simulation Settings Interference Model Two impulsive components: 7% of time/20dB above background Two 3%types of time/30dB above of temporal background dynamics:

i.i.d. samples Hidden Markov Model Receiver Parameters 15 GAMP iterations 5 turbo iterations FFT Size 256 (PLC) FFT Size1024 (Wireless) 50 LDPC iterations Definitions SER: Symbol Error Rate BER: Bit Error Rate SNR: Signal to noise + interference power ratio Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 24 Simulation - Uncoded Performance use LMMSE channel estimate performs well when

interference dominates time-domain signal Setting 5 Taps s GM noise 4-QAM N=256 15 pilots 80 nulls use only known tones, requires matrix inverse 2.5dB better than SBL within 1dB of MF Bound 15db better than DFT

Matched Filter Bound: Send only one symbol at tone k Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 25 Simulation Modeling Gain correct marginal: 4dB gain temporal dependency: extra 4dB amplitude accuracy is not important using all tones gives 8dB gain amplitude accuracy gives 7db gain Setting flatsch. N=256

60 nulls Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 26 Simulation Tone Map Design Typical configuration performs significantly worse Tone Map Design How to allocate tones? Limited resources select tones? Optimal solution not known. Dictionary coherence For same node type Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 27 Simulation - Coded Performance one turbo

iteration gives 9db over DFT 5 turbo iterations gives 13dB over DFT Setting s 10 Taps GM noise 16-QAM N=1024 150 pilots Rate L=60k Integrating LDPC-BP into JCNED by passing back bit LLRs gives 1 dB improvement Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 28 Robust Receiver Design

29 Recall - Coded OFDM Factor Graph contains parameters that might be unknown Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 30 Learning the Interference Model Training-Based quiet period model training Robust Receiver parameter estimate Detection 01010011

corrupted transmissio n Computationally simpler detection For slowly varying environments Suffer from model mismatch in rapidly varying environments Detection ^ 01010011 ^ corrupted joint estimation & transmissio detection n More computation for parameter

estimation (but not always) Adapts to rapidly varying environment Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 31 Parameter Estimation via EM Algorithm EM Algorithm Simplifies ML Estimation by: Marginalize over latent Maximize w.r.t parameters Marginalization easy for directly observed GM and GHMM samples EM for Robust Approximate Receivers marginalization using GAMP messages Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary

32 Sparse Bayesian Learning via GAMP Sparse Bayesian Learning Bayesian approach to compressive sensing Prior: Use data to fit via EM If e is sparse lot of end up zero Requires big matrix inverse Use only null tones Linear channel estimation SBL via GAMP

Integrate into GAMP estimation functions Linear input estimator Can include all tones and code Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 33 Simulation Result SBL via GAMP SBL via GAMP using all tones SBL via EM using only null tones EM Parameter estimation Setting 5 Taps s GM

noise 4-QAM N=256 15 pilots 80 nulls Blind EM Parameter Estimation Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary 34 FPGA Test System for G3 PLC Receiver Simplified message-passing receiver using only null tones In collaboration with Karl Nieman NI PXIe-7965R (Virtex 5) NI PXIe-1082 Real-time host Introduction |Message Passing Receivers | Simulations | Robust Receivers| Summary

35 Summary Significant performance gains if receiver accounts for uncoordinated interference Proposed solution combines all available information to perform approximate-MAP inference Asymptotic complexity similar to conventional OFDM receiver Can be parallelized Highly flexible framework: performance vs. complexity tradeoff Robust for fast-varying interference environments 36 Future Work Temporal Modeling of Uncoordinated Interference Wireless Networks Powerline Networks Tractable Inference Pilot and null tone allocation in impulsive noise Coherence not optimal Trade-off between channel and noise estimation

Extension to different interference and noise models Cyclostationary noise ARMA models for spectrally shaped noise Mitigation of narrowband interferers Sparse in frequency domain 37 Related Publications M. Nassar, K. Gulati, M. R. DeYoung, B. L. Evans and K. R. Tinsley, "Mitigating Near-Field Interference in Laptop Embedded Wireless Transceivers", Journal of Signal Processing Systems, Mar. 2009, invited paper. M. Nassar, X. E. Lin and B. L. Evans, "Stochastic Modeling of Microwave Oven Interference in WLANs", Proc. IEEE Int. Comm. Conf., Jun. 5-9, 2011, Kyoto, Japan. M. Nassar and B. L. Evans, "Low Complexity EM-based Decoding for OFDM Systems with Impulsive Noise", Proc. Asilomar Conf. on Signals, Systems and Computers, Nov. 6-9, 2011, Pacific Grove, CA USA. M. Nassar, K. Gulati, Y. Mortazavi, and B. L. Evans, "Statistical Modeling of Asynchronous Impulsive Noise in Powerline Communication Networks", Proc. IEEE Int. Global Comm. Conf.. Dec. 5-9, 2011, Houston, TX USA. J. Lin, M. Nassar and B. L. Evans, "Non-Parametric Impulsive Noise Mitigation in OFDM Systems Using Sparse Bayesian Learning", Proc. IEEE Int. Global Comm. Conf., Dec. 5-9, 2011, Houston, TX USA. M. Nassar, A. Dabak, I. H. Kim, T. Pande and B. L. Evans, "Cyclostationary Noise Modeling In Narrowband Powerline Communication For Smart Grid Applications, Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, March 25-30, 2012, Kyoto, Japan. M. Nassar, J. Lin, Y. Mortazavi, A. Dabak, I. H. Kim and B. L. Evans, "Local Utility Powerline Communications in the 3-500 kHz Band: Channel Impairments, Noise, and Standards", IEEE Signal Processing Magazine, Sep. 2013 J. Lin, M. Nassar, and B. L. Evans, ``Impulsive Noise Mitigation in Powerline Communications using Sparse

Bayesian Learning'', IEEE Journal on Selected Areas in Communications, vol. 31, no. 7, Jul. 2013, to appear. K. F. Nieman, J. Lin, M. Nassar, B. L. Evans, and K. Waheed, ``Cyclic Spectral Analysis of Power Line Noise in the 3-200 kHz Band'', Proc. IEEE Int. Symp. on Power Line Communications and Its Applications, Mar. 24-27, 2013, Johannesburg, South Africa. Won Best Paper Award. M. Nassar, P. Schniter and B. L. Evans, ``Message-Passing OFDM Receivers for Impulsive Noise Channels'', IEEE Transactions on Signal Processing, to be submitted. 38 Thank you 39 BACK UP SLIDES 40 41 42 43