A Factor Graph Approach to Joint OFDM Channel Estimation and Decoding in Impulsive Noise Environments

I Introduction

The main impairments to a communication system, whether wireless or wireline, are due to multipath propagation through a physical medium and additive noise. Multipath propagation is commonly modeled as a linear convolution that, in the slow-fading scenario, can be characterized by a channel impulse response $\left\{h_{j}\right\}_{j=0}^{L-1}$ that is fixed over the duration of one codeword. In the well-known “uncorrelated Rayleigh/Ricean-fading” scenario, the (complex-baseband) channel “taps” $h_{j}$ are modeled as independent circular Gaussian random variables, and in the well known “additive white Gaussian noise” (AWGN) scenario, the time-domain additive noise samples $\{n_{t}\}_{\forall t}$ are modeled as independent circular Gaussian random variables .

In this work, we focus on applications where the uncorrelated-Rayleigh/Ricean-fading assumption holds but the AWGN assumption does not. Our work is motivated by extensive measurement campaigns of terrestrial wireless installations wherein the additive noise is impulsive, with peak noise amplitudes reaching up to $40$ dB above the thermal background noise level . The noise affecting powerline communications (PLC) has also been shown to be highly impulsive, as well as bursty .

We restrict our attention to systems employing (coded or uncoded) orthogonal frequency division multiplexing (OFDM) , as used in many modern cellular wireless standards (e.g., IEEE802.11n and LTE) and PLC standards (e.g., PRIME and IEEE1901). OFDM is advantageous in that it facilitates data communication across convolutive multipath channels with high spectral efficiency and low complexity.

The impulsivity of noise has particular consequences for OFDM systems. Recall that, in conventional OFDM receivers, the time-domain received signal is converted to the frequency domain through a discrete Fourier transform (DFT) , after which each subcarrier (or “tone”) is demodulated independently. Such tone-by-tone demodulation is in fact optimal with AWGN and perfect channel estimates , and is highly desirable from a complexity standpoint, since it leaves the DFT as the primary source of receiver complexity, and thus requires only $O(N\log N)$ multiplies per symbol for $N$ tones. When the time-noise is impulsive, however, the corresponding frequency-domain noise samples will be highly dependent, and tone-by-tone demodulation is no longer optimal. We are thus strongly motivated to find near-optimal demodulation strategies that preserve the $O(N\log N)$ complexity of classical OFDM. In this work, we propose one such solution that exploits recent breakthroughs in loopy belief propagation.

I-B Prior Work

One popular approach to OFDM reception in impulsive noise stems from the argument that the noiseless time-domain received OFDM samples can be modeled as i.i.d Gaussian (according to the central limit theorem with sufficiently many tones), in which case the noise impulses can be detected using a simple threshold test. This approach straightforwardly leads to a decoupled procedure for impulse mitigation and OFDM reception: the time-domain received signal is pre-processed via clipping or blanking techniques or (nonlinear) MMSE estimation , and the result passed to a conventional DFT receiver for decoding. While agreeable from a complexity standpoint, these techniques perform relatively poorly, especially when the power of the implusive noise is comparable to the power of the OFDM signal, or when higher order modulations are used . This loss of performance can be explained by the fact that OFDM signal structure is not exploited for noise mitigation. In an attempt to improve performance, it has been suggested to iterate between such pre-processing and OFDM decoding, but the approaches suggested to date (e.g., ) have shown limited success, mainly because the adaptation of preprocessing with each iteration is challenging and often done in an ad-hoc manner.

Another popular approach models the time-domain impulsive noise sequence as a sparse vector and then uses sparse-reconstruction techniques to estimate this sequence from the observed OFDM null and pilot (i.e., known) tones. The recovered impulse vector is then subtracted from the time-domain received signal, and the result is passed to a conventional DFT receiver for decoding. Algebraic techniques were proposed in , and sparse reconstruction techniques based on compressive-sensing were proposed in . With typical numbers of known tones, these techniques have been shown to work well for very sparse impulsive noise sequences (e.g., one impulse in a $256$-tone OFDM system with $30$ known tones) but not for practical sparsity rates .

A more robust approach was proposed in , which performs joint symbol detection and impulse-noise estimation using sparse Bayesian learning (SBL). Still, because decouples channel estimation from impulse-noise estimation and symbol detection, and because it integrates coding in an ad-hoc manner, there is considerable room for improvement. In addition, it performs matrix inversion that is impractical for typical OFDM receivers with hundreds of tones.

I-B2 Factor Graph Receivers

Factor-graph-based receivers have been proposed as a computationally efficient means of tackling the difficult task of joint channel, symbol, and bit (JCSB) estimation. Here, messages (generally in the form of pdfs) are passed among the nodes of the factor graph according to belief propagation strategies like the sum-product algorithm (SPA) . Due to the loopy nature of the OFDM factor graph, however, exact implementation of the sum product algorithm is infeasible, and so various approximations have been proposed . Notably, merged the “generalized approximate message passing” (GAMP) algorithm with a soft-input soft-output decoder in a “turbo” configuration to accomplish near-optimalThe approach was shown to be near-optimal in the sense of achieving the pre-log factor of the sparse channel’s noncoherent capacity . joint structured-sparse-channel estimation and decoding of bit-interleaved coded-modulation (BICM)-OFDM with $O(N\log N)$ complexity. To our knowledge, no factor-graph-based OFDM receivers have been proposed to tackle impulsive noise, however.

I-C Contribution

In this paper, we propose a novel OFDM receiver that performs near-optimally in the presence of impulsive noise while maintaining the $O(N\log N)$ complexity order of the conventional $N$-tone OFDM receiver. Our approach is based on computing joint soft estimates of the channel taps, the impulse-noise samples, the finite-alphabet symbols, and the unknown bits. Moreover, all observed tones (i.e., pilots, nulls, and data tones) are exploited in this joint estimation. To do this, we leverage recent work on “generalized approximate message passing” (GAMP) , its “turbo” extension to larger factor graphs , and off-the-shelf soft-input/soft-output (SISO) decoding . The receiver we propose can be categorized as an extension of the factor-graph-based receiver that explicitly addresses the presence of impulsive noise. The resulting receiver provides a flexible performance-versus-complexity tradeoff and can be parallelized, making it suitable for FPGA implementations.

I-D Organization and Notation

In Section II, we describe our OFDM, channel, and noise models, and provide an illustrative example of impulsive noise. Then, in Section III, we detail our proposed approach, which we henceforth refer to as joint channel, impulse, symbol, and bit (JCISB) estimation. In Section IV we provide extensive numerical results, and in Section V we conclude.

II System Model

For OFDM modulation, an inverse of the unitary $N$-point discrete Fourier transform (IDFT) matrix $\mathbf{F}$ is applied to the $q$th OFDM symbol’s tone vector $\boldsymbol{\mathsf{S}}[q]$, producing the time-domain sequence $\mathbf{F}^{\ast}\boldsymbol{\mathsf{S}}[q]=\boldsymbol{s}[q]=[s_{0}[q],\dots,s_{N-1}[q]]^{T}$, to which a cyclic prefix is prepended. The resulting sequence propagates through an $L$-tap linear-time-invariant channel with impulse response $\mathbf{h}[q]=[h_{0}[q],\dots,h_{L-1}[q]]^{T}$ before being corrupted by both AWGN and impulsive noise. Assuming a cyclic prefix of length $L\!-\!1$, inter-symbol interference is avoided by simply discarding the cyclic prefix at the receiver, after which the remaining $N$ samples are

where $\mathbf{n}[q]$ is the time-domain noise vector and $\mathbf{H}[q]$ is the circulant matrix formed by $\mathbf{h}[q]$ . Applying a DFT, the resulting frequency-domain received vector becomes

where $\boldsymbol{\mathsf{H}}[q]=\sqrt{N}\mathbf{F}_{:,1:L}\mathbf{h}[q]$ is the frequency-domain channel vector, $\boldsymbol{\mathsf{N}}[q]=\mathbf{F}\mathbf{n}[q]$ is the frequency-domain noise vector, and $\circ$ denotes the Hadamard (i.e., elementwise) product. The second equality in (2) follows from the fact that a circulant matrix is diagonalized by the Fourier basis. In fact, (2) illustrates the principal advantage of OFDM: each transmitted tone $\mathsf{S}_{k}[q]$ experiences a flat scalar subchannel, since

II-B Channel Modeling

We assume that the channel taps remain constant during the entire duration of one OFDM symbol, as required by (2). Since we make no assumptions on how the taps change across symbols, for simplicity we take $\mathbf{h}[q]$ and $\mathbf{h}[q^{\prime}]$ to be statistically independent for $q\neq q^{\prime}$. Furthermore, we use the Rayleigh-fading uncorrelated-scattering model

where $[\nu_{0},\dots,\nu_{L-1}]^{T}=\boldsymbol{\nu}$ is the power delay profile. Extensions to sparse , structured-sparse , and time-varying sparse channels are straightforward, but not covered here.

II-C Impulsive Noise Models

In many wireless and power-line communication (PLC) systems, the additive noise is non-Gaussian (see the example in Figure 1) and the result of random emission events from uncoordinated interferers (due to, e.g., aggressive spectrum reuse) or non-communicating electronic devices. In his pioneering work, Middleton modeled these random spatio-temporal emissions, or the “noise field,” using Poisson point processes (PPP), giving rise to the “Middleton class-A” and “Middleton class-B” noise models. (For a recent review see .) Recently, his approach has been extended to modeling fields of interferers in wireless and PLC networks using spatial and temporal PPPs, and the resulting interference was shown to follow either the Symmetric alpha stable, the Middleton class-A (MCA), or the more general Gaussian mixture (GM) distribution, depending on the network architecture . Figure 1 illustrates that a GM model provides a significantly better fit to a noise realization collected from a receiver embedded in a laptop than a Gaussian model does.

Since our factor-graph-based receiver is inherently Bayesian, these statistical models provide natural priors on the noise. Thus, we model the additive noise using a GM model, noting that—given the pdf parameters—there is no distinction between the MCA and GM models. In particular, we decomposeOur approach is equivalent to modeling the total noise $n_{t}$ by a GM pdf $p(n_{t})=\sum_{k=0}^{K-1}\pi^{(k)}\mathfrak{N}(n_{t};0,\nu^{(k)})$ with $\nu^{(0)}=\gamma^{(0)}$ and $\nu^{(k)}=\gamma^{(0)}+\gamma^{(k)}$ for $k>1$. a given time-domain noise sample $n_{t}=g_{t}+i_{t}$ into a Gaussian background component $g_{t}\sim\mathfrak{N}(0,\gamma^{(0)})$ and a sparse impulsive component $i_{t}$ with Bernoulli-GM pdf

where $\delta(\cdot)$ denotes the Dirac delta and $\sum_{k=0}^{K-1}\pi^{(k)}=1$. Equivalently, we can model the (hidden) mixture state $z_{t}\in\{0,\dots,K\!-\!1\}$ of the impulsive component $i_{t}$ as a random variable, giving rise to the hierarchical model (with $\gamma^{(0)}=0$)

In many applications, such as PLC, the noise is not only impulsive but also bursty and thus the noise samples are no longer statistically independent. Such burstiness can be captured via a Bernoulli-Gaussian hidden Markov model (BGHMM) on the impulse-noise $\{i_{t}\}$ or equivalently a Markov model on the GM state $z_{t}$ in (6). For this, we model the sequence $\{z_{t}\}$ as a homogeneous (stationary) $K$-ary Markov chain with a state transition matrix $\mathbf{T}$ such that

In this case, the marginal pmf $\boldsymbol{\pi}=[\pi_{0},\dots,\pi_{K-1}]$ of steady-state $z_{t}$ obeys $\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{T}$, and the mean duration of the event $z=k$ is $1/(1-\mathbf{T}_{k,k})$ .

As an illustrative example, Figure 2 plots two realizations of the total noise $\{n_{t}\}$ with impulsive component $\{i_{t}\}$ generated by the hierarchical Bernoulli-GM model (6). Both realizations have identical marginal statistics: their impulsive components have two non-trivial emission states with powers $20$dB and $30$dB above the background noise power that occur $7\%$ and $3\%$ of the time, respectively. However, in one case the emission state $\{z_{t}\}$ was generated i.i.d whereas in the other case it is generated Markov with state-transition matrix

The GHMM realization clearly exhibits bursty behavior.

In practice, assuming the noise statistics are slowly varying, the noise parameters $\{\gamma_{k}\}_{k=0}^{K-1}$ and $\mathbf{T}$ can be estimated using the expectation-maximization (EM) algorithm during quiet intervals when there is no signal transmission.

III Message-Passing Receiver Design

In this section, we design computationally efficient message-passing receivers that perform near-optimal bit decoding which, as we shall see, involves jointly estimating the coded bits, finite-alphabet symbols, channel taps, and impulsive noise samples. In doing so, our receivers exploit knowledge of the statistical channel and noise models discussed above and the OFDM signal structure (i.e., the pilot and null tones, the finite-alphabet symbol constellation, and the codebook).

Maximum a posteriori (MAP) decoding, i.e.,

is well known to be optimal in the sense of minimizing the bit-error rate. Here, $\boldsymbol{\mathsf{Y}}=[\boldsymbol{\mathsf{Y}},\dots,\boldsymbol{\mathsf{Y}}[Q]]$ collects the received OFDM symbols of the corresponding frame. Using the law of total probability, we can write the posterior information-bit probability from (9) as

where “$\propto$” denotes equality up to a constant, $\mathbf{b_{\backslash m}}=[b_{1},\dots,b_{m-1},b_{m+1},\dots,b_{M_{\mathsf{i}}}]^{T}$, and the information bits are assumed to be independent with $P(b_{m})=1/2~{}\forall m$. Equation (12) shows that optimal decoding of $b_{m}$ involves marginalizing over the finite-alphabet symbols $\boldsymbol{\mathsf{S}}$, coded bits $\mathbf{c}$, noise states $\mathbf{z}$, impulse noise samples $\mathbf{i}$, channel taps $\mathbf{h}$, and other info bits $\mathbf{b_{\backslash m}}$.

The probalistic structure exposed by the factorization (12) is illustrated by the factor graph in Figure 3. There and in the sequel, for brevity, we drop the “$q$” (i.e., OFDM symbol) index when doing so does not cause confusion.

Clearly, direct evaluation of $P(b_{m}|\boldsymbol{\mathsf{Y}})$ from (12) is computationally intractable due to the high-dimensional integrals involved. Belief propagation (BP), and in particular the sum-product algorithm (SPA) described below, offers a practical alternative to direct computation of marginal posteriors. In fact, when the factor graph has no loops, the SPA performs exact inference after only two rounds of message passing (i.e., forward and backward). On the other hand, when the factor graph is loopy, the computation of exact marginal posteriors is generally NP hard and thus the posteriors computed by BP are generally inexact. Nevertheless, loopy BP has been successfully applied to many important problems, such as multi-user detection , turbo decoding , LDPC decoding , compressed sensing , and others.

In fact, for certain large densely loopy graphs that arise in the context of compressed sensing, SPA approximations such as the AMP and GAMP algorithms are known to obey a state evolution whose fixed points, when unique, yield exact posteriors . Looking at the factor graph in Figure 3, we see densely loopy sub-graphs between the factors $\{\mathsf{Y}_{k}\}$ and the time-domain noise samples $\{i_{t}\}$ and channel taps $\{h_{l}\}$, which are due to the linear mixing of the Fourier matrix $\mathbf{F}$. It is these types of densely loopy graphs for which AMP and GAMP are designed.Although rigorous GAMP guarantees have been established only for generalized linear inference problems with i.i.d sub-Gaussian transform matrices , equally good performance has been empirically observed over much wider classes of matrices . In the sequel, we will describe exactly how we combine the sum-product and GAMP algorithms for approximate computation of the bit posteriors in (12). First, however, we review the SPA.

III-B Belief Propagation using Sum-Product Algorithm

Belief propagation (BP) transforms a high-dimensional marginalization problem (like (12)) into a series of local low-dimensional marginalization problems by passing beliefs, or messages, which usually take the form of (possibly un-normalized) pdfs or pmfs, along the edges of a factor graph. The sum-product algorithm (SPA) is probably the best known approach to BP, and it operates according to the following rules:

Suppose the pdf factor $f_{s}(x_{1},\dots,x_{L})$ depends on the variables $\mathcal{X}_{s}=\{x_{l}\}_{l=1}^{L}$. Then the message passed from factor node $f_{s}$ to variable node $x_{m}\in\mathcal{X}_{s}$ is

representing the belief that node $f_{s}$ has about the variable $x_{m}$.

III-B2 Messages from Variables to Factor Nodes

Suppose the factors $\mathcal{F}_{m}=\{f_{1},\dots,f_{M}\}$ all involve the variable $x_{m}$. Then the message passed from variable node $x_{m}$ to factor node $f_{s}\in\mathcal{F}_{m}$ is

and represents the belief about the variable $x_{m}$ that node $x_{m}$ passes to node $f_{s}$.

III-B3 Marginal Beliefs

SPA’s approximation to the marginal posterior pdf on the variable $x_{m}$ is

III-C Joint Channel/Impulse-Noise Estimation and Decoding

We now propose a strategy to approximate the bit posteriors in (12) by iterating (an approximation of) the SPA on the loopy factor graph in Figure 3. To distinguish our approach from others in the literature, we will refer to it as “joint channel, impulse, symbol, and bit estimation” (JCISB).

Given the loopy nature of the factor graph, there exists considerable freedom in the message-passing schedule. In JCISB, we choose to repeatedly pass messages from right to left, and then left to right, as follows.

Beliefs about coded bits $\{c_{k,m}\}$ flow rightward through the symbol-mapping nodes $\{\mathcal{M}_{k}\}$, the finite-alphabet symbol nodes $\{\mathsf{S}_{k}\}$, and into the factor nodes $\{\mathsf{Y}_{k}\}$.

GAMP-based messages are then passed repeatedly between the $\{\mathsf{Y}_{k}\}$ and $\{h_{l}\}$ nodes until convergence.

GAMP-based messages are passed repeatedly between the $\{\mathsf{Y}_{k}\}$ and $\{i_{t}\}$ nodes until convergence, and then through the $\{z_{t}\}$ nodes using the forward-backward algorithm, alternating these two steps until convergence.

Finally, the messages are propagated from $\{\mathsf{Y}_{k}\}$ leftward through the symbol nodes $\{\mathsf{S}_{k}\}$, the symbol-mapping nodes $\{\mathcal{M}_{k}\}$, the coded-bit nodes $\{c_{k,m}\}$, and the coding-interleaving block—the last step via an off-the-shelf soft-input/soft-output (SISO) decoder.

In the sequel, we will refer to steps 1)–4) as a “turbo” iteration, and to the iterations within step 3) as “impulse iterations,” We note that it is also possible to execute a parallel schedule if the hardware platform supports it. The details of these four message passing steps are given below.

Beliefs about the coded bits $\{c_{k,m}\}_{m=1}^{M}$ (for each data tone $k\in\mathcal{D}$) are first passed through the symbol mapping factor node $\mathcal{M}_{k}$. The SPA dictates that

where (III-C1) follows from the deterministic symbol mapping $P(\mathsf{S}^{(i)}|\mathbf{c}^{(j)})=\delta_{i-j}$. The resulting message is then copied forward through the $\mathsf{S}_{k}$ node, i.e., $\mu_{\mathsf{S}_{k}\rightarrow\mathsf{Y}_{k}}=\mu_{\mathcal{M}_{k}\rightarrow\mathsf{S}_{k}}$, also according to the SPA. Note that, at the start of the first turbo iteration, we have no knowledge of the bits and thus we take $\mu_{c_{k,m}\rightarrow\mathcal{M}_{k}}(c)$ to be uniform across $c\in\{0,1\}$ for all $m,k$.

III-C2 GAMP for Channel Estimation

The next step in our message-passing schedule is to pass messages between the factor nodes $\{\mathsf{Y}_{k}\}$ and the time-domain channel nodes $\{h_{l}\}$. According to the SPA, the message passed from $\mathsf{Y}_{k}$ to $h_{l}$ is

Exact evaluation of (III-C2) involves an integration of the same high-dimensionality that made (12) intractable, with exponential complexity in $N$. Thus, we instead approximate the message passing between the $\{\mathsf{Y}_{k}\}$ and $\{h_{l}\}$ nodes using generalized approximate message passing (GAMP) algorithm reviewed in Appendix A and summarized in Table I.

From (3) and (15), the $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{H}},\sqrt{N}\mathbf{F},\mathbf{h})$ likelihood is

After $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{H}},\sqrt{N}\mathbf{F},\mathbf{h})$ is iterated to convergence, the outputs $\{\hat{\mathsf{H}}_{k}\}$ and $\{\gamma^{\mathsf{H}}_{k}\}$ of steps (R4)–(R3) are close approximations to the marginal posterior mean and variance, respectively, of $\{\mathsf{H}_{k}\}$. These outputs will be used in the next step of the message-passing schedule, as described below. Similarly, the outputs $\{\hat{h}_{l}\}$ and $\{\gamma^{h}_{l}\}$ of steps (R10)–(R9) are close approximations to the marginal posterior mean and variance, respectively, of $\{h_{l}\}$.

III-C3 Turbo-GAMP for Noise Estimation

The next step in our schedule is to pass messages between the factor nodes $\{\mathsf{Y}_{k}\}$, the time-domain impulse-noise nodes $\{i_{t}\}$, and the noise-state nodes $\{z_{t}\}$. According to the SPA, the message passed from $\mathsf{Y}_{k}$ to $i_{t}$ is

which poses the same difficulties as (12) and (III-C2).

Although GAMP can help approximate the messages in (III-C3), GAMP alone is insufficient due to connections between the $\{d_{t}\}$ nodes, which are used to model the burstiness of the time-domain impulse-noise $\{i_{t}\}$. However, recognizing that the underlying problem is estimation of a clustered-sparse sequence $\{i_{t}\}$ from compressed linear measurements, we can use the solution proposed in , which alternated (G)AMP with the forward-backward algorithm , as described below.

First, by temporarily treating the messages $\{\mu_{d_{t}\rightarrow i_{t}}\}$, $\{\mu_{\mathsf{S}_{k}\rightarrow\mathsf{Y}_{k}}\}$, and $\{\mu_{h_{l}\rightarrow\mathsf{Y}_{k}}\}$ as fixed, we can apply $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$ under the likelihood model

implied by (3) and (15), and the coefficient prior

implied by (5). In (18), $\beta_{k}^{(i)}=\mu_{\mathsf{S}_{k}\rightarrow\mathsf{Y}_{k}}(\mathsf{S}^{(i)})$ are the symbol beliefs coming from the $\{\mathsf{S}_{k}\}$ nodes and $\{\hat{\mathsf{H}}_{k},\gamma_{k}^{\mathsf{H}}\}$ are the frequency-domain channel estimates previously calculated by $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{H}},\sqrt{N}\mathbf{F},\mathbf{h})$. Meanwhile, in (19), $\{\pi_{t}^{(k)}\}_{k=0}^{K-1}$ represents the pmf on the noise state $z_{t}$ that is set as $\pi_{t}^{(k)}=\mu_{z_{t}\rightarrow d_{t}}(k)/(\sum_{l=0}^{K-1}\mu_{z_{t}\rightarrow d_{t}}(l))$. The resulting output MMSE estimation functions, derived in Appendix C, are listed in TABLE II, and the input MMSE estimation functions are

Here, $\{\alpha_{t}^{(k)}\}_{k=0}^{K-1}$ is the posterior pmf for noise-state $z_{t}$, with

where $p(\hat{r}|z_{t}\!=\!k)=\mathfrak{N}(\hat{r};0,\gamma^{r}+\gamma^{(k)})$ is the noise state likelihood.

Using these input and output MMSE estimation functions, $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$ is iterated until convergence, generating (for each $t$) an outgoing belief $\mu_{i_{t}\rightarrow d_{t}}(i_{t})=\mathfrak{N}(i_{t};\hat{r},\gamma^{r})$ about the noise-impulse $i_{t}$. This belief flows through the factor node $d_{t}$ which, according to the SPA, gives the rightward flowing noise-state belief

that acts as a prior for “Markov-chain (MC) decoding,” i.e., inference on the rightmost sub-graph in Figure 3. Since the MC sub-graph is non-loopy, it suffices to apply one pass of the forward-backward algorithm; see for details. Subsequently the refined noise-state beliefs $\{\mu_{z_{t}\rightarrow d_{t}}\}$ are passed back to the noise subgraph where each is used to compute the corresponding pmf $\{{\pi}_{t}^{(k)}\}_{k=0}^{K-1}$ used in (22) by the next invokation of $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$.

When the noise-state beliefs $\{\mu_{z_{t}\rightarrow d_{t}}\}$ have converged, the impulse-noise iterations are terminated and the $\{\hat{\mathsf{I}}_{k},\gamma_{k}^{\mathsf{I}}\}$ produced by $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$ are close approximations to the marginal posterior means and variances of $\{\mathsf{I}_{k}\}$ that will be used by $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{H}},\sqrt{N}\mathbf{F},\mathbf{h})$ in the next turbo iteration. In addition, for each data tone $k\in\mathcal{D}$, $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$ yields the leftward flowing soft symbol beliefs

that are subsequently used for decoding (as described below). Here, $\{\hat{\mathsf{H}}_{k},\gamma^{\mathsf{H}}_{k}\}$ and $\{\hat{\mathsf{I}}_{k},\gamma^{\mathsf{I}}_{k}\}$ play the role of soft frequency-domain channel and impulse-noise estimates, respectively.

Note that if the noise $\{i_{t}\}$ is not modeled as bursty, then there is no need to apply the forward-backward algorithm and it suffices to run $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$ only once per turbo iteration. In this case, (19) reduces to (5) and $\pi_{t}^{(k)}$ reduces to the time-invariant prior parameter $\pi^{(k)}$ discussed in Section II-C.

III-C4 Symbols to Bits

The SPA dictates that the messages flowing leftward through the symbol nodes $\{\mathsf{S}_{k}\}$ come out unchanged, i.e., $\mu_{\mathsf{S}_{k}\rightarrow\mathcal{M}_{k}}=\mu_{\mathsf{Y}_{k}\rightarrow\mathsf{S}_{k}}$. Moreover, it dictates that the message flowing leftward out of the symbol-mapping node $\mathcal{M}_{k}$ and into the coded-bit node $c_{k,m}$ takes the form

Finally, the computed coded-bit beliefs are passed to the coding/interleaving factor node. This can be viewed as passing (extrinsic) soft information into a soft-input/soft-output (SISO) decoder, where it is treated as prior information for decoding according to the “turbo” principle. SISO decoding has been studied extensively and we refer the interested reader to for a detailed account. After SISO decoding terminates, it will produce extrinsic soft information, in the form of beliefs $\{\mu_{c_{k,m}\rightarrow\mathcal{M}_{k}}\}$, that will be passed rightward to the symbol-mapping nodes at the start of the next turbo iteration. The turbo iterations are terminated after either the decoder detects no bit errors, the beliefs $\{\mu_{c_{k,m}\rightarrow\mathcal{M}_{k}}\}$ have converged, or a maximum number of turbo iterations has elapsed.

III-D Simplified Receivers

Although the JCISB receiver, as presented in Section III-C, utilizes all data, pilot, and null tones to perform inference over the complete factor graph in Figure 3, the proposed framework is flexible in that it can be easily modified to provided a desired trade-off between performance and computational complexity. For example, due to computational or architectural constraints, one might opt to simplify the receiver by either 1) using only a subset $\mathcal{U}$ of tones, or 2) replacing variable nodes in the factor graph with fixed exogenous soft estimates of those variables.

Since reducing the size of the tone subset $\mathcal{U}$ will reduce both receiver complexity and performance (see Section III-F), the selection of $\mathcal{U}$ should be done carefully to balance these conflicting objectives. In the sequel, we will denote the JCISB receiver that utilizes only the tone subset $\mathcal{U}\subset\{\mathcal{D}\cup\mathcal{P}\cup\mathcal{N}\}$ by $\text{JCISB}\left(\mathcal{U}\right)$. A generic implementation of $\text{JCISB}\left(\mathcal{U}\right)$ would execute the steps in Section III-F but with $\text{GAMP}(\boldsymbol{\mathsf{Y}}_{\mathcal{U}},\boldsymbol{\mathsf{H}}_{\mathcal{U}},\sqrt{N}\mathbf{F}_{\mathcal{U}},\mathbf{h})$ and $\text{GAMP}(\boldsymbol{\mathsf{Y}}_{\mathcal{U}},\boldsymbol{\mathsf{I}}_{\mathcal{U}},\mathbf{F}_{\mathcal{U}},\mathbf{i})$, and then compute approximate-MMSE estimates of $\{\mathsf{H}_{k}\}_{k\in\overline{\mathcal{U}}}$ and $\{\mathsf{I}_{k}\}_{k\in\overline{\mathcal{U}}}$ at $\overline{\mathcal{U}}=\{\mathcal{D}\cup\mathcal{P}\cup\mathcal{N}\}\setminus\mathcal{U}$ using GAMP’s time-domain approximate-MMSE estimates $\{\hat{h}_{t},\gamma^{h}_{t}\}$ and $\{\hat{i}_{t},\gamma^{i}_{t}\}$ and the linear relationships $\boldsymbol{\mathsf{H}}=\sqrt{N}\mathbf{F}\mathbf{h}$ and $\boldsymbol{\mathsf{I}}=\mathbf{F}\mathbf{i}$. That said, the case $\mathcal{U}=\mathcal{P}\cup\mathcal{N}$ deserves special attention, since here it suffices to perform joint channel and impulse (JCI) estimation in a manner that is decoupled from symbol and bit estimation.

There are several ways that one might remove variable nodes from the factor graph in Figure 3 to simplify the resulting JCISB receiver (at the expense of performance: see Section IV). For example,

Here the time-domain impulse-noise $\{i_{t}\}$ is modeled as non-bursty, in which case it suffices to remove the noise-state nodes $\{z_{t}\}$, use the GM prior (5) in the factor nodes $\{d_{t}\}$, and execute one impulse-noise iteration (without the forward-backward algorithm) per turbo iteration.

III-D2 Joint channel, symbol, and bit (JCSB) estimation

Here we separately estimate $\{\mathsf{I}_{k}\}$ from only the null tones using $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$, and then fix the resulting soft estimates $\{\hat{\mathsf{I}},\gamma^{\mathsf{I}}\}$ over the turbo iterations, avoiding the need to run $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$ more than once.

III-D3 Joint impulse, symbol, and bit (JISB) estimation

Here we compute soft linear-MMSE estimates of the frequency-domain channel coefficients $\{\mathsf{H}_{k}\}$ and use these in place of the GAMP-computed nonlinear-MMSE estimates $\{\hat{\mathsf{H}}_{k},\gamma^{\mathsf{H}}_{k}\}$, avoiding the need to ever run $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{H}},\sqrt{N}\mathbf{F},\mathbf{h})$.

III-D4 GAMP-impulse (GI) estimation

Here we first LMMSE estimate $\{\mathsf{H}_{k}\}$ from the pilot tones, then use those outputs with $\text{GAMP}(\boldsymbol{\mathsf{Y}},\boldsymbol{\mathsf{I}},\mathbf{F},\mathbf{i})$ to estimate $\{\mathsf{I}_{k}\}$ from the pilot and null tones, and finally use both the soft channel and impulse estimates to recover the symbols and bits via standard SISO decoding. The principal feature distinguishing this approach from conventional OFDM estimation is the use of GAMP-impulse estimation from pilot and null tones. The GI provides an important reference point since it uses the same information provided by the null and pilot tones as the prior work in .

III-E Computational Complexity

III-F Pilot and Null Tone Placement and Selection

In conventional OFDM systems, it is typical to place pilot tones on a uniformly spaced grid, as this yields MMSE optimal channel estimates in AWGN-corrupted frequency-selective channels . Meanwhile, it is customary to place null tones at the spectrum edges in order to reduce out-of-band emissions . These practices, however, should be re-examined when the receiver is expected to operate in the presence of impulsive noise, since there the MMSE channel estimator is nonlinear and the frequency-domain noise is dependent across tones, making it suboptimal to ignore null-tones while decoding.

Viewing impulse-noise estimation as a sparse reconstruction problem , we realize that the placement $\mathcal{U}$ of the tones used for estimation strongly affects the isometry of the linear transformation $\mathbf{F}_{\mathcal{U}}$ relating the sparse tone sequence $\mathbf{i}$ to the linearly compressed measurements $\boldsymbol{\mathsf{Y}}_{\mathcal{U}}$. For sparse signal reconstruction, recovery guarantees can be stated when the measurement matrix $\boldsymbol{\Phi}$ has sufficiently low coherence

using $\boldsymbol{\phi}_{k}$ to denote the $k$th column of $\boldsymbol{\Phi}$. Section IV provides evidence that $\mu(\mathbf{F}_{\mathcal{U}})$ predicts the performance of tone placement $\mathcal{U}$ in impulse-noise corrupted OFDM.

IV Numerical Results

In this section, we evaluate the performance of our proposed JCISB receivers using Monte-Carlo simulations, comparing to both existing work and fundamental bounds. We demonstrate that, in both coded and uncoded scenarios, the proposed JCISB framework provides significant performance gains over existing techniques at a computational complexity only slightly higher than the conventional DFT receiver and thus significantly lower than the best performing prior work. In fact, we show that JCISB performs within $1$dB of theoretical performance bounds, establishing its near-optimality. Furthermore, we conduct numerical studies that investigate the impact of receiver simplifications, impulse-noise modeling and mitigation, and pilot/null tone placement.

Unless stated otherwise, pilot tones were spaced on a uniform grid while the null tones were placed randomly. Noise realizations were generated according to one of the two models described in Section II-C: non-bursty i.i.d-GM noise, having two impulsive noise states with powers $20$dB and $30$dB above the background noise occurring $7\%$ and $3\%$ or the time, respectively; and bursty GHMM noise, with the same marginal statistics but with temporal dynamics governed by the state transition matrix in (8). Unless noted otherwise, JCISB was run using at most $5$ turbo iterations, $5$ noise iterations, and $15$ GAMP iterations. Throughout, signal-to-noise ratio (SNR) refers to the ratio of the received signal power to the total noise power.

IV-B Comparison with Existing Schemes

Figure 4 plots uncoded symbol-error rate (SER) versus SNR for a prototypical PLC setting: $4$-QAM modulated OFDM with $256$ subcarriers, of which $80$ tones are nulls and $15$ are pilots, under a $5$-tap Rayleigh-fading channel corrupted by i.i.d GM noise. In Figure 4, the “JCIS” trace represents our proposed JCISB approach but without bit estimation (since here we evaluate uncoded SER), and the “GI” trace represents the proposed GI simplification from Section III-D. The “DFT” trace represents the conventional OFDM receiver, which performs LMMSE pilot-aided channel estimation, LMMSE equalization, and decoupled symbol-detection on each equalized tone. The “PP” trace refers to , which performs MMSE-optimal processing prior to conventional OFDM reception and has been shown to perform best among the “pre-processing” techniques discussed in Section I-B. The “SBL” trace refers to , which was recently shown to perform best among the “sparse reconstruction” methods. Here, the PP and SBL approaches include LMMSE channel estimation, whereas in the original formulations the channel was treated as known. The “MFB” trace shows the matched-filter bound, which computes tone-averaged SER assuming that each symbol is detected under perfect knowledge of every other symbol as well as the channel. By subtracting the known effect of the other symbols, the received signal under MFB is given by

where the unknown symbol $\mathsf{S}$ is sent on tone $k$ and where $\mathbf{e}_{k}$ is the standard basis and $\mathbf{\bar{f}}_{k}$ is the $k$-th column of $\mathbf{H}\mathbf{F}^{\ast}$. Using the factorization of the noise pdf in time domain, it is straightforward to find the MAP detection rule for $\mathsf{S}$ . Due to the non-Gaussianity of the noise, we evaluated the MFB via Monte-Carlo.

The SER curves in Figure 4 show that the proposed JCIS receiver drastically outperforms the conventional OFDM receiver (by $15$dB), the PP receiver (by $15$dB in the high SNR regime), and the state-of-the-art SBL receiver (by $13$dB). We attribute these huge performance gains to the fact that JCIS utilizes all received tones (pilots, nulls, and data) for joint channel, impulse, and symbol estimation. In contrast, PP does not use OFDM signal structure for impulse-noise mitigation; and SBL decouples the estimation of the channel, impulses, and symbols, and performs linear MMSE channel estimation using only pilot tones, which not only ignores information on data and null tones, but is also strongly suboptimal in the presence of impulsive noise. Moreover, the proposed JCIS receiver follows the MF bound to within $1$dB over the full SNR range, demonstrating its near-optimality. Figure 4 also shows that the proposed JCI simplification performs only $3$dB worse than JCIS, and that the GI simplification performs $13$dB worse than JCIS but $2$dB better than the state-of-the-artAlthough PP outperforms both SBL and GI when $\textsf{SNR}<3$, the achieved SERs are unusably high. SBL receiver.

IV-C Impact of Impulse-Noise Modeling and Mitigation

In this section, we evaluate the relative success of various strategies for modeling and mitigating impulsive noise in OFDM, again restricting our attention to uncoded transmissions. For clarity, we consider a trivial (unit-gain non-fading) channel that is perfectly known to the receiver, and thus we include no pilot tones. Without channel estimation and bit decoding, our proposed JCISB approach then reduces to JIS. Below, we compare JIS to the SBL receiver and to the GI simplification proposed in Section III-D. Given the absence of pilot tones, GI and SBL are quite similar: both perform impulse-noise estimation using only null tones and in a manner that is decoupled from symbol estimation.

Figure 5(a) plots NMSE in the estimation of i.i.d GM noise versus SNR for the JIS, GI, and SBL receivers. The GI traces in Figure 5(a) imply that GAMP is a uniformly better estimator of i.i.d GM noise than SBL, although the difference is $<1$dB for SNRs between $-15$ and $8$ dB. This behavior is expected, given that the underlying problem is one of estimating a length-$256$ i.i.d-GM sequence from $60$ randomly selected Fourier observations, for which the superiority of GM-GAMP over SBL was established in . The JIS traces in Figure 5(a) show NMSEs that are significantly (i.e., $\geq 5$dB) better than GI and SBL across the SNR range, and this is because JIS uses both null and data tones, rather than just null tones. To extract meaningful noise information from the data tones, JIS must accurately infer the data symbols. The latter is easier with 4-QAM than with 16-QAM, which explains the gap between the traces in Figure 5(a).

Figure 5(b) plots NMSE in the estimation of GHMM noise versus SNR for the proposed JIS receiver with the forward-backward (FB) iterations, and two simplifications: JIS without FB (labelled as “JIS” for consistency with Figure 5(a)) and GI. Comparing Figure 5(b) to Figure 5(a), we see that GHMM noise is significant more challenging than i.i.d-GM noise: the NMSE of JIS is $7$dB worse, and that of GI is $5$dB worse, in the GHMM case However, the FB iterations help significantly: they restore approximately $6$dB of the lost NMSE .

Next we compare the SER performance of JIS, GI, and SBL in the same trivial-channel setting. Figure 6(a) shows the case of i.i.d-GM noise. There we see that JIS significantly outperforming SBL with both 4-QAM (red) and 16-QAM (blue) constellations, as expected from the superior noise-estimation NMSE in Figure 5 and from the fact that JIS estimates the symbols jointly with the noise impulses. Meanwhile, it shows GI performing on par with SBL with 4-QAM but somewhat better than SBL with 16-QAM, especially at medium SNR.

Figure 6(b) then shows SER under GHMM (i.e., bursty) noise. Comparing Figure 6(b) to Figure 6(a), we see that the burstiness of the noise causes the SER of all receivers to degrade significantly. Moreover, this degradation persists when the JIS receiver uses MC iterations, even though the NMSE results in Figure 5 show only about a $1$dB loss due to burstiness. We attribute the SER sensitivity to the fact that the noise burstiness makes some OFDM-symbols much more noise-corrupted than others, and those heavily corrupted symbols skew the average SER reported in Figure 6(b). Regardless, Figure 6(b) shows that the FB-assisted JIS receiver significantly outperforms non-FB-assisted JIS, GI, and the state-of-the-art SBL algorithm, especially at medium SNR. To investigate whether the kink in the JIS$+$FB trace was due to suboptimality of the FB noise-state inference, we simulated a genie-aided receiver that knows the true state of the GHMM noise at each time index. Since the genie trace also exhibits the kink, it is evidently not due to suboptimality of FB.

IV-D Impact of Pilot and Null Tone Placement

In this section, we investigate the impact of pilot and null tone placement. For this, we examine the uncoded SER of a 4-QAM $256$-tone OFDM system under a $5$-tap Rayleigh-fading channel in i.i.d-GM noise for both the proposed JCIS receiver and its JCI simplification, the latter of which ignores data tones during channel and impulse-noise estimation. Figure 7 shows that the conventional placement of sideband null tones and uniform pilot tones produces the worst SER performance. Randomizing the pilot locations alone provides a modest performance gain for both JCI and JCIS, while randomizing the null locations alone improves the SER performance dramatically, especially for JCI.We expect JCI to be more sensitive to null/pilot-tone placement than JCIS, since the former observes the channel and noise impulses only through those tones. We conjectured in Section III-F that the performance improvement observed with randomized pilot and null tone placements can be explained by the corresponding reduction in coherence $\mu(\mathbf{F}_{\mathcal{P}})$ and $\mu(\mathbf{F}_{\mathcal{N}})$, and the coherence values reported in Figure 7 lend credence to this conjecture.

IV-E Coded Systems

Finally, we investigate the bit error rate (BER) performance of JCISB in the coded scenario. For this, we used an LDPC-coded 16-QAM $1024$-tone OFDM system with $150$ pilot and null tones under a $10$-tap Rayleigh-fading channel and i.i.d-GM noise. The LDPC codes had code-word length $\approx 60\>000$ and rate $1/2$, with a modified coder/decoder implementations from . We also investigate the conventional OFDM receiver (“DFT”) as well as the JCIS simplification, which omits SISO decoding from the turbo iterations. For both JCIS and DFT, we performed SISO decoding as the final step. For all receivers, the maximum number of LDPC iterations was $50$.

Figure 8 shows that, after only one turbo iteration, the proposed JCISBNote that, with only a single turbo iteration, JCISB and JCIS are equivalent. outperforms the conventional OFDM receiver by $10$dB. Additional turbo iterations result in further gains of $4$dB. Figure 8 also shows that JCIS’s decoupling of bit estimation from channel, impulse, and symbol estimation costs approximately $1$dB.

V Conclusion

In a this paper, we presented a factor-graph approach to OFDM reception in multipath distorted and impulse-noise corrupted channels that performs near-optimal joint channel, impulse-noise, symbol, and bit (JCISB) estimation. Our approach merges recent work on generalized approximate message passing (GAMP) , its “turbo” extension to larger factor graphs , and soft-input-soft-output SISO decoding . Extensive numerical simulations show that the proposed JCISB receiver provides drastic performance gains over existing receivers for OFDM in impulsive noise, and performs within $1$dB of the matched-filter bound, all while matching the complexity order of the conventional OFDM receiver. Furthermore, JCISB is easily parallelized, providing a natural mapping to FPGA implementations (see for a recent FPGA implementation of the GI receiver). Additional numerical simulations investigated the impact of JCISB simplifications, noise modeling and mitigation, and null/pilot tone placement.

Appendix A Generalized Approximate Message Passing (GAMP)

$\mathsf{Y}_{k}$ is Gaussian when conditioned on $\mathsf{S}_{k}$, and so according to the definition (D1) in Table I and ,

is the posterior symbol probability and $p(\mathsf{Y}_{k}|\mathsf{S}_{k};\hat{p},\gamma^{p})=\mathfrak{N}(\mathsf{Y}_{k};\hat{\mathsf{I}}_{k}+\hat{p}\mathsf{S}_{k},\gamma^{\mathsf{I}}+|\mathsf{S}_{k}|^{2}\gamma^{p}+\gamma^{(0)})$. Similarly, the law of total variance implies

The derivation for pilot tones $k\in\mathcal{P}$ reduces to the above under $\lambda_{k}^{(1)}=1$, $\lambda_{k}^{(l\neq 1)}=0$, and $\mathsf{S}^{(1)}=\mathsf{p}$.

$\mathsf{Y}_{k}$ is Gaussian when conditioned on $\mathsf{S}_{k}$, and so according to the definition (D1) in Table I and ,

where $\lambda_{k}^{(l)}$ is the posterior symbol probability from (32) but now with $p(\mathsf{Y}_{k}|\mathsf{S}_{k};\hat{p},\gamma^{p})=\mathfrak{N}(\mathsf{Y}_{k};\hat{p}+\hat{\mathsf{H}}_{k}\mathsf{S}_{k},\gamma^{p}+|\mathsf{S}_{k}|^{2}\gamma^{\mathsf{H}}_{k}+\gamma^{(0)})$. Similarly, the law of total variance implies

The derivation for pilot tones $k\in\mathcal{P}$ reduces to the above under $\lambda_{k}^{(1)}=1$, $\lambda_{k}^{(l\neq 1)}=0$, and $\mathsf{S}^{(1)}=\mathsf{p}$. Meanwhile, the derivation for null tones $k\in\mathcal{N}$ is the special case of pilots with $\mathsf{p}=0$.

References