On Skew Convolutional and Trellis Codes

Vladimir Sidorenko, Wenhui Li, Onur Günlü, Gerhard Kramer

Abstract

Two new classes of skew codes over a finite field $\mathbb{F}$ are proposed: skew convolutional codes and skew trellis codes. These classes are defined as left or right sub-modules, respectively, over the skew fields of fractions of skew polynomials over $\mathbb{F}$. Skew convolutional codes can be represented as periodic time-varying ordinary convolutional codes, while skew trellis codes are generally nonlinear over $\mathbb{F}$. Both classes possess a code trellis and can be decoded using standard Viterbi or BCJR algorithms.

Introduction: The Challenge of Time-Varying Codes

In digital communications, convolutional codes are essential for protecting data against noise. Traditionally, these codes are time-invariant, meaning their encoding rules remain constant. However, time-varying codes—where rules change periodically—often provide superior performance, such as higher "free distance." The primary obstacle has been the mathematical complexity involved in describing and analyzing these varying structures. This paper addresses this by utilizing skew polynomials, offering a compact algebraic framework to represent complex time-varying behavior.

Methodology: Skew Polynomial Rings

The authors transition from standard polynomial rings to skew polynomial rings ($R = \mathbb{F}[D; \theta]$). Unlike standard rings where variables and coefficients commute ($Da = aD$), skew rings follow the rule $Da = \theta(a)D$, where $\theta$ is a field automorphism.

This algebraic "twist" allows for two distinct constructions:

  1. Skew Convolutional Codes: Defined as left sub-modules, these are equivalent to periodic, time-varying linear codes.
  2. Skew Trellis Codes: Defined as right sub-modules, these are generally nonlinear because the automorphism acts directly on the information symbols.
Time-varying encoder circuits for even and odd time steps, illustrating the periodic nature of skew convolutional codes.

Structural Properties and Advantages

A key advantage of this approach is algebraic compactness. A single generator matrix $G(D)$ in the skew domain can describe a sequence of different matrices in the time domain. This significantly reduces the overhead required to store and optimize time-varying codes. Furthermore, the authors demonstrate that these codes are naturally "non-catastrophic," preventing small input errors from propagating into infinite output error strings.

Decoding and Trellis Representation

Despite their exotic algebraic origins, these codes can be mapped to a standard code trellis. This ensures that industry-standard decoding tools, such as the Viterbi or BCJR algorithms, remain applicable without modification. The paper provides a concrete example of a $[2, 1]$ skew convolutional code over $\mathbb{F}_4$, showing how the state transitions evolve over time.

The code trellis for the first three time steps, showing the periodic transitions and output labels.

Key Results

  • Equivalence Theorem: Theorem 1 establishes that every skew convolutional code is equivalent to a periodic time-varying ordinary convolutional code with a period $\tau$ determined by the field's automorphism.
  • Optimal Performance: Numerical examples show that unit-memory skew codes can reach upper bounds for free distance ($d_f = 4$) and slope ($\sigma = 1$), outperforming any fixed (time-invariant) convolutional code with the same memory constraints.
  • Duality: The authors provide a method to construct parity-check matrices ($H$), enabling syndrome-based decoding and further theoretical analysis of code duals.

Limitations and Future Directions

While the theoretical foundation is robust, several areas remain for future exploration. The hardware complexity of implementing the field automorphism $\theta$ needs further study compared to standard shift registers. Additionally, while skew trellis codes are identified as nonlinear, their specific performance advantages in non-Gaussian noise environments are yet to be fully quantified. Future work will likely focus on large-scale searches for optimal skew codes across various rates and lengths.

Summary updated

Abstract

Two new classes of skew codes over a finite field F are proposed, called skew convolutional codes and skew trellis codes. These two classes are defined by, respectively, left or right sub-modules over the skew fields of fractions of skew polynomials over $\mathbb{F}$. The skew convolutional codes can be represented as periodic time-varying ordinary convolutional codes. The skew trellis codes are in general nonlinear over $\mathbb{F}$. Every code from both classes has a code trellis and can be decoded by Viterbi or BCJR algorithms.
BibTeX
@misc{sidorenko2021skew,
  author = {Vladimir Sidorenko and Wenhui Li and Onur Günlü and Gerhard Kramer},
  title = {{On Skew Convolutional and Trellis Codes}},
  year = {2021},
  eprint = {2102.01510},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.01510},
}
Figure