Convolutional codes I: Algebraic structure

TLDR

A convolutional encoder is a constant linear sequential circuit whose output sequences form a code, and encoders are equivalent when they generate the same code. The invariant factor theorem is employed to determine when a convolutional encoder admits a feedback‑free inverse and to compute its minimal inverse delay, while dual codes, syndromes, and systematic encoders are also characterized to relate encoder complexity and canonical classes. All encoders are shown to be equivalent to minimal encoders, which are feedback‑free with delay‑free inverses, use the fewest memory elements, are immune to catastrophic error propagation, and yield the shortest decoded error sequences per error event.

Abstract

A convolutional encoder is defined as any constant linear sequential circuit. The associated code is the set of all output sequences resulting from any set of input sequences beginning at any time. Encoders are called equivalent if they generate the same code. The invariant factor theorem is used to determine when a convolutional encoder has a feedback-free inverse, and the minimum delay of any inverse. All encoders are shown to be equivalent to minimal encoders, which are feedback-free encoders with feedback-free delay-free inverses, and which can be realized in the conventional manner with as few memory elements as any equivalent encoder, Minimal encoders are shown to be immune to catastrophic error propagation and, in fact, to lead in a certain sense to the shortest decoded error sequences possible per error event. In two appendices, we introduce dual codes and syndromes, and show that a minimal encoder for a dual code has exactly the complexity of the original encoder; we show that systematic encoders with feedback form a canonical class, and compare this class to the minimal class.