Online Learning of Trellis Diagram Using Neural Network for Robust Detection and Decoding

The received signal in an ISI channel can be expressed as

where $L$ is the channel length, $h_{l},0=1,\cdots,L-1$ are the channel coefficients, and $z_{k}$ denotes the i.i.d additive noise, which is not necessarily Gaussian.

The ISI channel can be modeled as a tapped delay line as shown in Fig. 1. Owing to the shift register structure, the channel can be modelled by a trellis diagram [1].

As the transmitted symbols are drawn from a set of ${\mathcal{X}}$, the ISI channel modeled in (1) can be represented by a trellis diagram consisting of a set ${\mathcal{S}}$ of the states with cardinality $|\mathcal{S}|=|{\mathcal{X}}|^{L-1}$. Denote the state set at time $k$ as $s_{k}$, which corresponds to the combination of $L-1$ symbols $x_{k-L+1},...,x_{k-1}$. The state transitions $s_{k}\rightarrow s_{k+1}$ is associated with the output signal $v_{k}=\sum_{l=0}^{L-1}h_{l}x_{k-l}$. As an illustrative example, consider an ISI channel with coefficients $h_{0}=0.407$, $h_{1}=0.815$, and $h_{2}=0.407$ and the binary phase shift key (BPSK) signal as the input. The trellis consists of $|\mathcal{S}|=4$ states, with $r_{0}=(-1,-1)$, $r_{1}=(+1,-1)$, $r_{2}=(-1,+1)$, $r_{3}=(+1,+1)$, as shown in Fig. 2. The numbers on the branches represent $u_{k}$ and $v_{k}$. Take the state $r_{0}$ for example: if the input symbol $u_{k}=-1$, the branch output $v_{k}=-h_{0}-h_{1}-h_{2}=-1.629$; if $u_{k}=+1$, $v_{k}=h_{0}-h_{1}-h_{2}=-0.815$.

The trellis diagram can also be used to model a modulation with memory. As an example, we review the GFSK, which is used in the PHY of Bluetooth [28]. The GFSK with bandwidth $1/T$ sampled at $t=nT$ is

where

Here $I_{n}\in\{0,1\}$ is the information bits, ${\sf h}$ is the modulation index, and the pulse shaping function

with $Q(x)=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{\frac{-\tau^{2}}{2}}d\tau$.

If ${\sf h}=0.5$ (as specified in [28]), (3) becomes

where $\theta_{n}=\frac{\pi}{2}\sum_{m=1}^{n-1}I_{m}$. Here we set the frequency-time product $BT=0.5$ (also as specified in [28]). As shown in Fig. 3, $q(t)=0$ for $t\leq 0$, and $q(t)\approx 0.5$ for $t\geq 2T$.

We can model the continuous phase modulation as a process of finite state transition based on the phase transition (it is $\theta_{n}$ not $\phi_{n}$) as shown in Fig. 4. Denote $(r_{i},r_{j})$ as the state transition from $r_{i}\in{\mathcal{S}}$ at time $nT$ to $r_{j}\in{\mathcal{S}}$ at time $(n+1)T$ driven by $I_{n}$. Here $\mathcal{S}$ stands for the set of the states of the trellis. The dash branches correspond to $I_{n}=-1$, the solid branches correspond to $I_{n}=1$, and the associated signal is

where we have used the fact that $q(T)=\frac{1}{4}$.

If the input to the ISI channel (1) is an GFSK signal, we can combine the GFSK modulation and the multi-path channels into a (larger) trellis diagram.

Based on the trellis diagram, the receiver can use the Viterbi algorithm or the BCJR algorithm for optimal symbol detection. We briefly review them to make this paper self-contained.

The Viterbi algorithm is for maximum likelihood (ML) detection. By exploiting the Markovian structure of the finite-memory channel, it computes the likelihood of each branch, i.e., the conditional probability density function (PDF) of the channel output given the inputs

where $x_{k}=0,k<0$. For a given channel output $\mathbf{y}$, we should have

Combining (8) and (7), we can rewrite (7) as:

where $p(y_{k}|s_{k},s_{k+1})$ is the likelihood of $y_{k}$ associated with the state transition from $s_{k}$ to $s_{k+1}$. The Viterbi algorithm can solve (9) efficiently by searching for the shortest path across the trellis diagram.

The BCJR algorithm [26] is for maximum a posteriori probability (MAP) detection. It computes the a posteriori log-likelihood ratio (LLR) of bits $\{u_{k}\}$

where $\mathcal{S}^{+}$, $\mathcal{S}^{-}$ are the set of the ordered pairs $(s_{k},s_{k+1})$ corresponding to all states transitions driven by $u_{k}=1$ and $u_{k}=0$, respectively. The sequence $\mathbf{y}$ in $p(s_{k},s_{k+1},\mathbf{y})$ can be written as $p(s_{k},s_{k+1},(y_{1},\cdots,y_{k-1}),y_{k},(y_{k+1},\cdots,y_{N}))$. Applying the chain rule for joint probabilities, we can decompose $p(s_{k},s_{k+1},\mathbf{y})$ into:

where $\alpha_{k}(s_{k})\triangleq p(s_{k},y_{1:k-1})$, $\gamma_{k}(s_{k},s_{k+1})\triangleq p(y_{k},s_{k+1}|s_{k})$, and $\beta_{k+1}(s_{k+1})\triangleq p(y_{k+1:N}|s_{k+1})$. They can be recursively computed as

with the initialization $\alpha_{0}(s_{0})=1$ and $\beta_{N}(s_{N})=1$.

Driven by $u_{k}$, the probability of the state transition is

Examining (9) and (12), we see that the likelihood $p(y_{k}|s_{k},s_{k+1})$ plays a key role in both Viterbi and BCJR algorithms. Indeed, the Viterbi algorithm depends solely on the likelihood, while the BCJR also exploits the a priori information on the state transition probability $p(s_{k+1}|s_{k})$, which is independent of the CSI [cf. (12c) and (13)]. Hence, $p(y_{k}|s_{k},s_{k+1})$ is the only CSI-dependent component for both algorithms.

The conventional method calculates $p(y_{k}|s_{k},s_{k+1})$ assuming known CSI and that the channel noise is zero-mean Gaussian with variance $\sigma^{2}$. Hence the likelihood can be computed to be

where $v_{k}=\sum_{l=0}^{L-1}h_{l}x_{k-l}$ is the channel output associated with the state transition from $s_{k}$ to $s_{k+1}$ (cf. Fig. 2).

But when the CSI is unknown or the distribution of the noise is unknown owing to non-Gaussian co-channel interference, the model-based likelihood (14) will be erroneous, causing severe degradation to the performance of Viterbi or BCJR. To address this issue, we propose to use an ANN to learn online the likelihood function $p(y_{k}|s_{k},s_{k+1})$ of the trellis diagram based on a pilot sequence, assuming no CSI nor the noise statistics.

As shown in Fig. 5, we construct a fully connected and one hidden-layered ANN [35], whose input is the real and imaginary part of the received sample $y_{k}$ and the output nodes correspond to all the state transitions in the trellis diagram. For example, we can use a network with 8 output nodes to learn the trellis diagram in Fig. 4, which has 8 state transitions. The hidden-layer nodes adopt the Sigmoid activation function, while the output layer employs the Softmax activate function. The reason of using the softmax function is to be explained in Section III-D.

Given the pilot sequence $\{y_{k},k=1,\ldots,P\}$, we know the true transition $s_{k}\rightarrow s_{k+1}$ corresponding to each $y_{k}$ and thus label the normalized likelihood $p(y_{k}|s_{k},s_{k+1})$ corresponding to the true transition to be 1 and all the others to be 0; this is the so-called one-hot encoding. The ANN is optimized according to the minimum cross-entropy criterion. Note that the OLTD method requires neither the CSI nor the noise statistics, which is its main advantage over the model-based method.

After the ANN is trained, the payload signals $\{y_{i},i=P+1,\ldots,P+Q\}$ are then fed into the network; for each $y_{i}$ the ANN will yield the normalized likelihoods $p(y_{i}|s_{i},s_{i+1})$ for all the $2|{\mathcal{S}}|$ state transitions. The numerical examples in Section V indicates that the likelihoods yielded by the ANN is sufficiently accurate when it is trained with a pilot with length $P$ no more than a few hundred.

Given the likelihoods $p(y_{i}|s_{i},s_{i+1})$’s per received sample of the payload, the Viterbi (or BCJR) algorithm can then be directly applied to obtain the ML (or MAP) detection.

Taking the BCJR algorithm for example, given the sample $y_{k}$’s associated likelihoods $p(y_{k}|s_{k},s_{k+1})$’s, the BCJR algorithm can calculate $\gamma_{k}$ according to (12c) and further compute the forward recursion (12a) and the backward recursion (12b) to obtain the LLR $L(u_{k}|\mathbf{y})$ by (11) and (10). The combination of the OLTD method and the BCJR algorithm is termed as the OLTD-based BCJR. The OLTD-based Viterbi is even simpler: it just needs to search the most likelihood trellis path according to (9).

Observe from (9) that to multiply $p(y_{k}|s_{k},s_{k+1})$’s by a common positive factor does not affect the output result of the Viterbi algorithm, neither does it affect the BCJR as can be seen from (10) and (12). Hence, instead of learning the original likelihoods, which can be anywhere in $[0,\infty)$, the ANN can simply learn the normalized likelihoods

which is why we can adopt the softmax as the activation function of the output layer even though the actual likelihood value may be out of the range $[0,1]$. The above insight is the underlying reason why our method is significantly simpler than the state-of-the-art method [24], which has to compute the marginal distribution $p(y_{k})$ besides using a deep neural network to learn the conditional probability $p(s_{k},s_{k+1}|y_{k})$ [24, Fig. 3].

We can gain more insights into the OLTD method by drawing its analogy to the classic least square (LS) fitting method. An LS method optimizes the parameters of a signal model to fit the true signal; the OLTD method trains the ANN to approximate the ground truth of the normalized likelihoods, which is a one-hot vector in absence of the channel noise. The LS method uses the LS criteria; the OLTD adopts the minimum cross-entropy criterion. The LS method does not assume knowledge of the noise statistics, neither does the OLTD, which is why the OLTD is robust against non-Gaussian noise as shown in Section IV.

Last but not least, our proposed OLTD-based BCJR algorithm can be readily applied for turbo equalization [36], which is an important advantage over the BCJRNet [23] as we will explain in the next.

The whole procedure of turbo equalization is as shown in Fig. 7, where BCJR equalization and BCJR decoding are conducted iteratively ²²2Readers unfamiliar with turbo equalization may refer to [36] for an excellent tutorial..

On the equalization side, the BCJR algorithm takes the a priori probabilities of $b_{n}$’s to calculate the state transition probabilities as

takes the normalized likelihoods from the OLTD algorithm, and then calculate (12) and (11) to calculate $L(b_{n}|\mathbf{y})$ in (10).

Note that the a posteriori LLR of $\{b_{n}\}$ can also be computed as

Since the bit interleaver decorrelates the neighboring coded bits, it holds that $p(\mathbf{b})=\prod_{n=1}^{N}p(b_{n})$; thus, $L(b_{n}|\mathbf{y})$ can be decomposed into

where

is the extrinsic information about $b_{n}$ contained in $\mathbf{y}$, and

is called the intrinsic information. Hence, it follows from (18) that

On the decoding side, after deinterleaving $L_{ext}(b_{n}|\mathbf{y})$ into $L_{ext}(a_{n}|\mathbf{y})$, the BCJR decoder takes the extrinsic information as the “received signal”, i.e., $\tilde{\mathbf{y}}\triangleq L_{ext}(a_{n}|\mathbf{y})$ to update the a posteriori LLR of the coded bits $L(a_{n}|\tilde{\mathbf{y}})$ based on the trellis diagram associated with the FEC (15). As another input into the BCJR decoder, the uncoded bits $\{u_{k},k=1,\ldots,K\}$ are assumed to satisfy $P(u_{k}=1)=P(u_{k}=0)=1/2$.

Note from (18) that we can update the intrinsic LLRs

which can be fed into the BCJR equalizer after being interleaved into $L(b_{n})$. Using the relationship [cf. (20)]

and (16), we can obtain the state-transition probabilities $p(s_{n+1}|s_{n})$’s, which are needed for the next round of BCJR equalization.

After a prescribed number of iterations, we calculate $\tilde{\gamma}_{k}(r_{i},r_{j})$ as [36, eq.(22)]

for $k=1,2,\cdots,K$, and the decoder will calculate the LLRs of information bits $u_{k}$, and make a final decision

Hence, the only difference between the OLTD-based turbo equalization and a standard model-based one is how the likelihoods $p(\mathbf{y}|s_{n},s_{n+1})$ are obtained, while the whole procedure in the dotted-line box is the same for both methods.

One may attempt to apply the BCJRNet to turbo equalization, but will come across a major issue as explained in the next.

In the BCJRNet, a neural network is trained to obtain the a posteriori probability $p(s_{n},s_{n+1}|y_{n})$. Then by Bayes’ rule ³³3To obtain $p(y_{n}|s_{n},s_{n+1})$, the BCJRNet algorithm actually assumes that $p(s_{n+1},s_{n})=|{\cal S}|^{-L}$ is a constant [23, eq. (13)].

Combining (26) and (12c), we obtain

According to (10) and (11), we have

Substituting (27) into (28) yields

Given the a posteriori probability $p(s_{n},s_{n+1}|y_{n})$ learned by the BCJRNet, one can update $p(s_{n})$ through the forward recursion

where $p(s_{n}|s_{n-1})$ can be obtained according to (16) and (23). Due to this recursion, the BCJR-based turbo equalization is cumbersome.

More important, this method actually does not work as shown by the simulation example in Section V-B. Indeed, the a posteriori probability $p(s_{n},s_{n+1}|y_{n})$ is not the suitable metric to learn, because

relies on the a priori information $p(s_{n},s_{n+1})$; thus, it is impossible to infer $p(s_{n},s_{n+1}|y_{n})$ from $y_{n}$ itself unless $p(s_{n},s_{n+1})$ is a constant, which is usually untrue. In contrast, the likelihood $p(y_{n}|s_{n},s_{n+1})$ relies solely on the distribution of the channel noise and the CSI, and is independent of the channel coding; thus, it can be learned from $y_{n}$ itself.

We first simulate an ISI channel as modelled in (1), where the input signal is uncoded QPSK, the noise is complex-valued Gaussian, and channel coefficients are given by $h_{l}\triangleq\sqrt{\frac{e^{-\gamma\cdot l}}{\sum^{L-1}_{l=0}e^{-\gamma\cdot l}}}$ for $\gamma>0$. We set the channel memory length $L=2$; thus, the trellis diagram is fully-connected with 4 states and 16 branches (state transitions). Fig. 8 compares the bit error rate (BER) performance of model-based BCJR/Viterbi algorithm and OLTD-based BCJR/Viterbi algorithm. The model-based method is simulated based on perfect CSI, while the OLTD is trained based on a 500-sample pilot. The simulation results are obtained by averaging over $10,000$ Monte-Carlo simulations, where the channel coefficients are generated with $\gamma$ being draw at random in the range $[0.1,1]$. Fig. 8 shows that OLTD-based method can achieve performance very close to the model-based benchmark. The Viterbi algorithm performs the same as the BCJR algorithm, since here the bits are generated $0$ or $1$ evenly.

We then simulate the channel noise as complex Cauchy with the PDF

where $\Re\{\cdot\}$ and $\Im\{\cdot\}$ stand for the real and imaginary parts, respectively. The Cauchy’s PDF has much heavier tails than the Gaussian’s.

In the Cauchy noise case, the SNR is undefined since the variance of Cauchy is unbounded. We simulate the BER performance by changing the value of $\gamma$. Fig. 9 shows that the OLTD-BCJR outperforms the model-based BCJR algorithm in this non-Gaussian case, which is not surprising since the OLTD requires no a priori knowledge on the statistics of the noise.

We also simulate the ISI channel scenario where the QPSK signal is interfered by a random 4-ary Pulse Amplitude Modulation (4-PAM) source. The received power of the interference is the same as the QPSK signal, i.e., the signal-to-interference ratio (SIR) is $0$ dB. As shown in Fig. 10, the model-based Viterbi method based on the assumption of Gaussian noise fails. The striking advantage of the OLTD-based approach indicates that the neural network somehow learned the “structure” of the non-Gaussian interference and hence suppressed it effectively.

To demonstrate the influence of training pilot length on reception performance, we simulate the BER performance of the OLTD-based approach when trained using the pilots length of $\{0.5,1,2,5,10,20\}\times 10^{2}$ as shown in Fig. 11. We set SNR = 10 dB under Gaussian channel, and the performance of the OLTD-based method, as the training pilots length increases, gradually approaches that of the model-based method under perfect CSI. A pilot of length a few hundred is sufficient for all the three cases. Fig. 11 illustrates from a different perspective that the OLTD-based method can outperform the model-based method in the two cases of non-Gaussian noise.

In addition to the additive noise channel, we also simulate the Poisson channel as previously considered in [23]. But here we consider a bit-interleaved system as shown in Fig. 6, where the information bits are FEC encoded, bit-interleaved, and then modulated by OOK before being transmitted over a Poisson channel. The channel output $y_{k}$ is of Poisson distribution, i.e.,

where $v=\sum_{l=0}^{L-1}h_{l}x_{k-l}$ with $x_{k-l}\in\{0,1\}$ and $h_{l}\triangleq\sqrt{\frac{e^{-\gamma\cdot l}}{\sum^{L-1}_{l=0}e^{-\gamma\cdot l}}}$ for $\gamma$ being draw at random in the range$[0.1,1]$.

For $L=2$, the Poisson channel can be represented by a fully-connected two-state trellis diagram with 4 branches. Hence, the OLTD uses a neural network with 4 outputs. Fig. 12 shows that using no iterations the OLTD-based method and the BCJRNet have identical performance. The BCJRNet applied for turbo equalization, however, leads to failed decoding as explained in Section IV-B. In contrast, the OLTD-based turbo equalization can achieve significantly improved performance.

We simulate in an AWGN channel a BLE system with bit rate 500 Kbps with a pilot of length 256 as specified in the protocol [30]. A model-based receiver consists of a BCJR demodulator and a Viterbi decoder. It assumes perfect CSI. The OLTD-based receiver differs from the model-based one only in that the likelihoods $p(y_{k}|s_{k},s_{k+1})$ [cf. (12c)] used in the BCJR algorithm is produced by a neural network trained by the 256-sample pilot sequence. According to Fig. 4, the GFSK modulation can be represented by a trellis diagram with 8 state transitions; thus, the neural network for the OLTD has 8 neurons in the output layer. The BER is averaged over $10,000$ Monte Carlo trails of the channel coefficients $h(\theta)=e^{j\theta}$, with $\theta$ being drawn at random in the range $[0,2\pi]$. In Fig. 13, the dot dash line with marker $\triangle$ corresponds to the model-based method, while the dot dash line with marker $\square$ is the OLTD-based one. They essentially overlap, which suggests that the neural network assisted receiver can be practically feasible at least performance-wise.

We also present Shannon limit of the BER performance of the GFSK signal obtained using the numerical method in [38, 39]. The large gap between Shannon limit and the achieved performance of the BLE system motivated us to consider introducing a bit interleaver at the transmitter between encoder and GFSK modulator (cf. Fig. 6). Given the bit-interleaver, the receiver can apply the turbo equalization. Fig. 13 also illustrates the BER performance of the turbo receiver with no iteration, and with 1 and 2 iterations. The three dash lines show the model-based turbo equalization under the perfect CSI and the other three sold lines with markers correspond to the OLTD-based turbo algorithm with pilot length of 256. It can be seen that introducing the bit-interleaver and using the turbo equalization in the receiver can yield $4\sim 5$dB gain compared with the conventional receiver. Hence, to introduce bit-interleaving may be an interesting enhancement to the existing BLE protocol for significantly enhanced performance, which can make it more competitive for IoT communications.

In the last example, we consider the BLE system in a ISI channel with memory $L=2$. The ISI channel is described as $h_{0}\delta(n)+h_{1}\delta(n-1)$, where the channel coefficients are normalized. The combination of the GFSK modulation and the ISI channel can be modeled by a trellis diagram with 16 states. Then we can also apply turbo equalization based on the OLTD method except that here the output layer of the neural network has $16$ neurons. The BER performance of the model-based turbo receiver with known perfect CSI and the OLTD-based turbo receiver in the ISI channel is compared in Fig. 14. It can be seen that the OLTD-based turbo equalization algorithm trained based on a same 256-sample pilot sequence has about 0.5dB loss compared with the model-based method with perfect CSI.