PaperlayerView exact revision on arXiv

Source-linked AI summary

ViterbiNet: A Deep Learning Based Viterbi Algorithm for Symbol Detection

Nir Shlezinger, Nariman Farsad, Yonina C. Eldar, Andrea J. Goldsmith

arXiv:1905.10750v2cs.LGeess.SPstat.ML

TL;DR

The paper targets reliable symbol recovery in digital receivers under degraded or unavailable channel-state information. ViterbiNet replaces CSI-based Viterbi computations with machine-learned components while preserving the detection scheme, and its performance approaches CSI-based Viterbi detection while supporting online tracking of time-varying channels.

  • Problem

    Reliable symbol recovery is fundamental to digital receivers, while inaccurate channel-state information can degrade detection.

  • Method

    ViterbiNet replaces CSI-based parts of the Viterbi algorithm with an ML-based scheme that learns the log-likelihood function without requiring full CSI.

  • Results

    ViterbiNet approaches the performance of the CSI-based Viterbi algorithm and outperforms previously proposed ML-based symbol detectors using a small amount of data.

  • Takeaways & Limitations

    Maintaining the established Viterbi detection scheme while replacing its channel-dependent computations provides a data-driven symbol detector capable of online tracking of time-varying channels.

Abstract

from arXiv · show

Symbol detection plays an important role in the implementation of digital receivers. In this work, we propose ViterbiNet, which is a data-driven symbol detector that does not require channel state information (CSI). ViterbiNet is obtained by integrating deep neural networks (DNNs) into the Viterbi algorithm. We identify the specific parts of the Viterbi algorithm that are channel-model-based, and design a DNN to implement only those computations, leaving the rest of the algorithm structure intact. We then propose a meta-learning based approach to train ViterbiNet online based on recent decisions, allowing the receiver to track dynamic channel conditions without requiring new training samples for every coherence block. Our numerical evaluations demonstrate that the performance of ViterbiNet, which is ignorant of the CSI, approaches that of the CSI-based Viterbi algorithm, and is capable of tracking time-varying channels without needing instantaneous CSI or additional training data. Moreover, unlike conventional Viterbi detection, ViterbiNet is robust to CSI uncertainty, and it can be reliably implemented in complex channel models with constrained computational burden. More broadly, our results demonstrate the conceptual benefit of designing communication systems to that integrate DNNs into established algorithms.

I. INTRODUCTION

The introduction frames CSI-dependent symbol detection as costly and vulnerable to estimation error, then motivates integrating deep learning with the Viterbi algorithm. ViterbiNet preserves Viterbi’s channel structure while replacing CSI-dependent computations with learned, data-driven components.

  • Motivation: Conventional symbol detection requires instantaneous CSI, whose estimation adds overhead and whose inaccuracies degrade detection.The underlying channel model may also be unknown, poorly understood, or difficult to represent accurately.
  • Motivation: The Viterbi algorithm efficiently detects symbols in channels with Markovian input-output relationships but requires knowledge of the exact statistical relationship.This motivates retaining its sequential structure while removing its channel-model dependence.
  • Related motivation: ML methods can operate when the stochastic model is unknown or its parameters cannot be accurately estimated, and may handle complex observed data more effectively than traditional model-based methods.The introduction also notes potential convergence benefits compared with iterative model-based approaches.
  • Proposed approach: ViterbiNet integrates DNNs into the Viterbi algorithm by replacing only its CSI-based computations while preserving the algorithm’s structure and Markovian-channel processing.The design is inspired by deep unfolding but differs by maintaining the Viterbi detector rather than converting every iteration into a network layer.
  • Adaptation: The proposed online meta-learning method adapts ViterbiNet to dynamic channels without requiring new training data whenever the channel model changes.The network is described as trainable with relatively few samples and capable of tracking varying channel conditions.
  • Results: Numerical results report performance roughly matching CSI-based Viterbi detection, improved robustness under CSI uncertainty, and reliable operation in complex channels.The introduction also reports that online training enables tracking of block-fading channel conditions.

II. SYSTEM MODEL AND PRELIMINARIES

The system model considers recovering a block of symbols transmitted through a stationary, causal, finite-memory channel. The receiver knows the constellation and channel structure but does not know the conditional output PDF, which constitutes missing CSI.

  • System model: The receiver aims to recover a block of t transmitted symbols from the corresponding channel outputs.The transmitted symbols belong to a constellation of m points.
  • System model: The channel is modeled as stationary, causal, and finite-memory, with memory l smaller than the blocklength t.Its output at each time depends stochastically on a finite recent sequence of input symbols.
  • CSI assumption: The receiver knows the symbol constellation but does not know the conditional PDF of the channel output given the input sequence.Thus, the receiver lacks the channel state information required by model-based detection.
  • Detection basis: The Viterbi algorithm is selected as the model-based optimal detector for finite-memory channels and serves as the basis for the DNN design.The paper reviews Viterbi detection before introducing the proposed network.

B. The Viterbi Detection Algorithm

The Viterbi algorithm solves finite-memory sequence detection recursively by updating state path costs from channel likelihoods. Its efficiency and sequential operation depend on explicit knowledge of the channel conditional PDF, motivating ViterbiNet’s CSI-free replacement of those computations.

  • Algorithm: Viterbi detection recursively updates a path cost for each state by combining the preceding path cost with a channel-dependent likelihood term.The possible input-symbol histories are treated as states in a dynamic-programming recursion.
  • Algorithm: The algorithm processes a block of channel outputs through initialization, repeated state-cost updates, and termination after t steps.Its state space consists of length-l symbol histories.
  • Properties: The Viterbi algorithm achieves minimal error probability for the relevant channel model and has complexity linear in the blocklength t.Directly solving the corresponding optimization grows exponentially instead.
  • Properties: Viterbi produces symbol estimates sequentially, with each estimate computed once the necessary delayed channel output is received.This supports run-time detection rather than requiring the entire received block for every estimate.
  • CSI dependence: Implementing the recursion requires the conditional channel PDF, or full CSI, to compute every state’s channel-dependent cost.Obtaining full CSI can be difficult in rapidly changing channels and may impose substantial training overhead.
  • ViterbiNet: ViterbiNet addresses this dependence by replacing the CSI-based parts of Viterbi detection with an ML-based scheme that learns the log-likelihood function from data.The remaining Viterbi detection structure is retained while CSI is not required.

III. VITERBINET

ViterbiNet integrates machine learning into the Viterbi algorithm by replacing channel-model-based log-likelihood computation while preserving the algorithm’s remaining structure. The approach supports real and complex channels but assumes known or bounded channel memory and does not yet address unknown memory length.

  • Assumptions and scope: The receiver assumes accurate knowledge or a reliable upper bound on channel memory length, leaving unknown-memory decoding for future work.Estimating channel memory is treated as simpler than symbol detection, but the decoder extension to unknown memory length is explicitly deferred.
  • ML integration: ViterbiNet replaces the Viterbi algorithm’s explicit log-likelihood computation with an ML-based system while leaving the remaining algorithm intact.The learned system takes y[i] as input and estimates c_i(s) for each candidate state s.
  • ML integration: The Viterbi algorithm requires the conditional PDF p_Y[i]|S_i, not the conditional distribution typically produced by a classification DNN.This requirement enables the algorithm to exploit the channel’s finite-memory Markov structure.
  • ML integration: Bayes’ theorem enables recovery of the required likelihood from estimates of the marginal output distribution and p_Si.The marginal distribution can be estimated using kernel density or finite-mixture methods, while p_Si can be estimated with classification DNNs.
  • Channel types: The ML-based log-likelihood computation applies to both real-valued and complex-valued channels with corresponding input and density-estimation modifications.For complex channels, the DNN input uses the real and imaginary parts of y[i], and the density model can use complex Gaussian mixtures.

B. Discussion

ViterbiNet preserves the Viterbi detection structure while replacing channel-model-based computations with learned estimates, enabling CSI-free detection. Its simple DNN can be trained with relatively few samples, but complexity and future extensions remain constrained by the underlying Viterbi formulation.

  • Performance: When properly trained, ViterbiNet is expected to approach the performance of the conventional CSI-based Viterbi algorithm.The paper reports numerical support for this expectation in Section V.
  • Architecture: The DNN estimates the conditional distribution of channel outputs given transmitted symbols rather than directly classifying transmitted symbols.This estimate captures the finite-memory channel structure used by Viterbi detection.
  • Architecture: ViterbiNet replaces the CSI-based parts of the Viterbi algorithm with an ML-based scheme while retaining the remaining detection operations.The learned component estimates channel-related quantities used by the conventional Viterbi procedure.
  • Runtime adaptation: The simple DNN can be trained quickly with relatively few samples, supporting runtime adaptation to channel variations with minimal overhead.The paper suggests that pilot sequences periodically embedded in transmitted frames could support online training.
  • Broader implications: The same design principle could support other trellis or factor-graph detectors, such as BCJR, although those data-driven schemes are left for future investigation.The proposed approach separates algorithmic structure from channel-model-dependent computations.
  • Limitations: ViterbiNet complexity grows exponentially with constellation size m and channel memory l because its DNN label space grows exponentially.Greedy Viterbi reductions may inspire lower-complexity variants, but this remains future work.

IV. EXTENSION TO BLOCK-FADING CHANNELS

The paper extends ViterbiNet to time-varying block-fading channels, where each transmitted block may experience a different statistical transformation. It uses coded-signal structure and online adaptation to track these variations without requiring training on every specific channel.

  • Channel model: Block-fading channels can apply a different statistical transformation to each transmitted block, requiring the receiver to track changing conditions.This setting models dynamic wireless environments in which the channel input-output relationship depends on the block.
  • Generalization: Training ViterbiNet on samples from varied channels can still provide relatively good performance on a tested channel not used for training.The paper presents this as evidence that broad training can support operation across channel conditions.
  • Online adaptation: ViterbiNet is extended to track time-varying channels in real time by exploiting the inherent structure of coded digital communications.The approach uses channel coding to identify and correct detection errors for online retraining.

A. Coded Communications over Block-Fading Channels

In coded block-fading communications, each block carries an encoded and modulated codeword through a potentially different channel. Forward-error correction and error detection allow the receiver to recover information and assess whether detected bits are reliable enough for adaptation.

  • Coded transmission: Each transmitted block represents a codeword carrying b information bits, which is encoded and modulated into channel symbols.The coded symbols are transmitted through the channel during the corresponding block.
  • Coding: Forward-error-correction and error-detection codes support information recovery and indicate whether the recovered bits contain errors.Examples include Reed-Solomon codes, checksums, and cyclic redundancy checks.
  • Block fading: In block-fading channels, the conditional output distribution can change between blocks because each block undergoes a different channel.The resulting model captures dynamic environments in which channel behavior depends on the block index.
  • Motivation: The receiver must track and adapt to varying channel conditions to optimize performance, motivating online training for ViterbiNet.The next subsection combines coded communications with ViterbiNet’s relatively small training sets.

B. ViterbiNet with Online Training

ViterbiNet retrains online from recently decoded and re-encoded blocks, using meta-learning to adapt its DNN and channel model to block-fading variations. Decision errors can corrupt this feedback loop, especially at low SNR, so error thresholds and learning rates trade adaptation against reliability.

  • Meta-training: The method uses recent decisions as meta-training because coded communications can provide recovered channel inputs without new labeled samples for every block.The approach is based on meta-learning and exploits structure induced by channel codes.
  • Online training: The online scheme decodes each block, estimates bit errors, and retrains ViterbiNet only when the recovered information is sufficiently reliable.The decoded bits are re-encoded and modulated to create meta-training pairs with the received channel outputs.
  • Reliability: Decision errors can gradually deteriorate retrained ViterbiNet, making the approach unreliable particularly at low SNRs where decoding errors occur frequently.Error-detection codes can mitigate this effect by permitting retraining only below a chosen error threshold.
  • Online training: Algorithm 2 applies ViterbiNet, decodes the recovered bits, re-encodes them, retrains DNN weights, and updates mixture-model parameters.The procedure uses a bit-error threshold to decide whether meta-training is performed.
  • Design trade-offs: Setting the error threshold to zero protects meta-training-label accuracy under gradual variation but may limit tracking of moderate channel changes.Larger thresholds must account for the error-correction code because few bit errors can still produce a distant codeword.
  • Design trade-offs: Larger retraining learning rates support nontrivial channel adaptation but increase sensitivity to decision errors, requiring smaller error thresholds.The learning rate balances prior DNN weights against the smaller current-block meta-training set.
  • Extensions: The online scheme currently exploits channel-code structure, but preambles, pilots, headers, and management frames could also generate meta-training data.These protocol structures provide known or constrained transmitted sequences for online retraining.

V. NUMERICAL STUDY

The numerical study evaluates ViterbiNet against conventional and learned detectors in time-invariant and block-fading channels. The implementation uses a compact DNN trained with relatively few samples and assumes the channel memory length is known.

  • The study compares ViterbiNet with model-based Viterbi and deep symbol detectors under time-invariant and block-fading channels.
  • The simulations assume the channel memory length l is known, although correlation-based estimation accurately detects it in the simulated setups.
  • ViterbiNet uses a fully connected DNN with three layers and sigmoid and ReLU activations.
  • The network is trained with 5000 samples using cross-entropy loss and Adam optimization.
  • Only a few minutes are required to train the network on a standard CPU because the training set is small and the architecture is simple.

A. Time-Invariant Channels

In time-invariant ISI and Poisson channels, ViterbiNet approaches CSI-based Viterbi performance, remains effective under CSI uncertainty, and operates in channel models that complicate conventional Viterbi detection.

  • The study evaluates symbol error rate across SNR for ISI channels with AWGN and Poisson channels, including perfect and uncertain CSI.
  • ViterbiNet approaches conventional CSI-based Viterbi performance in both channel models.
  • At 8 dB in the AWGN ISI channel, Viterbi and ViterbiNet both achieve SER 4.7 · 10^-3, compared with 8.5 · 10^-3 for SBRNN.
  • Under CSI uncertainty, ViterbiNet significantly outperforms conventional Viterbi, whose performance degrades with imperfect CSI.
  • At high SNR, ViterbiNet needs larger training sets to approach perfect-CSI Viterbi performance, while CSI-uncertain training can provide useful diversity.
  • ViterbiNet also operates reliably in non-conventional channels where conventional Viterbi is difficult to implement even with full CSI.

B. Block-Fading Channels

For block-fading channels, online meta-training lets ViterbiNet track changing channel conditions from recent decisions. Its performance approaches instantaneous-CSI Viterbi mainly at high SNR, while threshold selection limits low-SNR adaptation.

  • The block-fading evaluation transmits RS [255, 223] codewords across 200 consecutive blocks in ISI-AWGN and Poisson channels.
  • At low SNR, BER often exceeds the 2% threshold, limiting coefficient updates and producing only minor improvement over initial training.
  • Online-trained ViterbiNet approaches instantaneous-CSI Viterbi as SNR increases, whereas low-SNR gains over the initial-channel detector are small.
  • At high SNR, reliable meta-training from recent decisions enables ViterbiNet to track the channel and approach optimal performance.
  • Increasing the error threshold can severely degrade low-SNR performance because inaccurate meta-training may be used.
  • Composite training improves BER over initial-only training across broader channel conditions, but remains below instantaneous-CSI Viterbi except with high-SNR online training.
  • Overall, integrating DNNs into Viterbi yields a data-driven detector that approaches optimal performance without CSI and tracks block-fading channels from previous decisions.

VI. CONCLUSIONS

ViterbiNet integrates machine-learning processing into the Viterbi detection scheme by replacing channel-dependent log-likelihood computation while preserving the algorithm’s structure. The resulting detector approaches CSI-based Viterbi performance, outperforms earlier ML-based detectors, and supports CSI uncertainty, complex channels, and online adaptation to block-fading conditions.

  • ViterbiNet design: ViterbiNet identifies log-likelihood computation as the Viterbi component requiring full channel input-output statistics and replaces it with an ML-based architecture.The remaining conventional Viterbi symbol-detection scheme is retained.
  • Online adaptation: Meta-learning enables ViterbiNet to track time-varying channels online under block-fading conditions.The adaptation method is designed to follow changing channel conditions without discarding the established Viterbi structure.
  • Numerical results: ViterbiNet approaches the optimal performance of the CSI-based Viterbi algorithm and outperforms previously proposed ML-based symbol detectors using a small amount of training data.These outcomes are reported from the paper’s numerical results.
  • Robustness and complexity: ViterbiNet reliably operates with CSI uncertainty and in complex channel models where conventional Viterbi detection is extremely difficult to implement.The conclusion presents these capabilities as part of the detector’s demonstrated operating range.
Loading 1905.10750v2…