A Trellis-Structured Neural Network

Thomas Petsche, Bradley W. DickinsonNeurIPS 1987

Overview

This paper introduces a neural network architecture that mimics the trellis structure of convolutional codes to perform Maximum Likelihood Sequence Estimation (MLSE). By utilizing locally interconnected "on-center off-surround" subnets, the authors provide a hardware-friendly alternative to globally connected networks (such as Hopfield networks) for signal deconvolution and error correction.

The Problem: Global Connectivity in Hardware

In the late 1980s, neural networks like the Hopfield network showed great promise for optimization tasks, but they faced a major hurdle: global connectivity. In a Hopfield network, every neuron is potentially connected to every other neuron. For VLSI (Very Large Scale Integration) hardware designers, this translates to a nightmare of long, crossing wires that consume massive amounts of chip area.

The authors tackle the problem of sequence decoding, specifically for convolutional codes. While the Viterbi algorithm is the gold standard for this task, the authors wanted to determine if a neural network could achieve similar results using only local interconnections. Local connectivity is vastly easier to implement in silicon, as neurons only need to "talk" to their immediate neighbors in the sequence.

Methods and Architecture

The authors propose a "trellis-structured" network composed of several sequential stages.

Trellis structure for a K=3 convolutional code
  • Subnet Architecture: Each stage in the trellis acts as an "on-center off-surround" competitive network based on the Grossberg model. This creates a "winner-take-all" (WTA) dynamic where, ideally, only the neuron representing the most likely state at that specific time step remains active.
  • Inter-stage Connections: Instead of global wiring, neurons are only connected to neurons in adjacent stages. These connections are weighted based on the transition probabilities (log-likelihood) of the convolutional code being decoded.
  • Mathematical Framework: The system is defined by a set of differential equations. To prove the system won't oscillate or explode, the authors utilize Lyapunov stability theory. They demonstrate that in the "large gain limit" (where the neuron's activation function is very steep), the network is equiasymptotically stable.
  • Implementation: The network was simulated using Euler discretization, essentially treating the differential equations as a digital filter.

Experimental Setup

Rather than modern large-scale datasets, the paper evaluates the architecture using simulated signal sequences:

  • Code Type: A rate 1/3, constraint length $K=3$ convolutional code.
  • Channel Model: A Binary Symmetric Channel (BSC) where bits are flipped with a specific probability to simulate noise.
  • Test Cases: The network was tested on unerrored sequences, "burst" errors (multiple consecutive flipped bits), and scattered/distributed errors.

Key Insights

  • Local vs. Global: The most significant insight is that a network with strictly local connections can perform a task that usually requires global knowledge (sequence estimation). Information "flows" through the trellis over time, allowing the network to reach a global consensus without global wiring.
  • The "Four-Nearest" Neighborhood: The authors found that connecting a neuron not just to its immediate neighbors ($i \pm 1$), but also to the next neighbors ($i \pm 2$), significantly improved performance. This allows the network to "communicate around" subsequences that are too noisy to decode locally.
  • Fault Tolerance: Because the representation is distributed across the trellis, the network inherently handles faulty units better—a key requirement for biological systems and large-scale analog hardware.

Key Results

  • Optimal Decoding: For low error rates (up to 3 errors in the test sequence), the neural network performed optimally, matching the results of a standard MLSE/Viterbi decoder.
  • Convergence Speed: In the noiseless case, the network reached equilibrium extremely quickly—roughly within one "RC time constant" of the simulated system.
Simulated neuron activations converging over time
  • Robustness: The "four-nearest" neighbor configuration was notably more robust than the "two-nearest" version. In a test of 500 vectors with 7 errors, the "four-nearest" version failed on 103 cases, while the "two-nearest" failed on 132.
  • Energy Minimization: Simulations confirmed that the defined energy function decreases monotonically over time, validating the authors' theoretical stability claims.

Limitations and Future Work

  • Sub-optimality at High Noise: For sequences with four or more errors, the network occasionally failed to find the sequence that a true MLSE decoder would have found, getting stuck in local minima when noise is too high.
  • Asymptotic Proofs: The proof of stability relies on the "large gain limit." Proving strict Lyapunov stability for the cooperative connections at lower gains remains a difficult mathematical challenge.
  • Scaling: While $K=3$ was manageable, the number of neurons per stage grows exponentially with the constraint length ($2^{K-1}$). Scaling this to very complex codes would require significant hardware resources.
  • Future Direction: The authors suggest investigating these trellis layers within larger multilayer networks to improve error tolerance and neuron replacement strategies.

Summary updated

BibTeX
@inproceedings{petsche1987trellis,
  author = {Thomas Petsche and Bradley W. Dickinson},
  title = {{A Trellis-Structured Neural Network}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1987},
}
Figure