Convolutional codes with guaranteed error protection from cyclic codes
Convolutional Codes from Cyclic Codes with Guaranteed Free and Local Minimum Distances
Information Theory
Summary
This paper shows a way to create special error-correcting codes, called convolutional codes, that always have strong protections against errors. They do this by building on simpler cyclic codes arranged in a sequence with a nesting property. The resulting codes have predictable minimum error distances to catch mistakes both globally and locally, and can be decoded efficiently in sliding windows. The method doesn’t need complex computer searches and applies to codes of odd lengths.
What this means in practice
- •For communication system engineers: Design convolutional codes with guaranteed minimum error correction levels using cyclic code chains for reliable data transmission.
- •For storage system developers: Implement sliding window decoding schemes for error correction based on locally structured convolutional codes to improve data integrity in disks and memory.
Authors
Khaled Abdel-Ghaffar, Daniel J. Costello, Juane Li, Shu Lin
Abstract
This paper presents an algebraic method to construct convolutional codes with guaranteed \emph{free and local minimum distances} without limit based on cyclic codes of odd lengths. The constructions are simple but effective, and no computer search is needed. For any two positive integers $r$ and $t$ with $1 \leq r < t$, a rate-$r/t$ convolutional code $\mathcal{C}_{\text{convol}}$ can be constructed by using a chain of $r$ cyclic codes $\mathcal{C}_0, \mathcal{C}_1, \ldots, \mathcal{C}_{r-1}$ of the same length $n$ which satisfy the inclusion condition, $\mathcal{C}_0 \supset \mathcal{C}_1 \supset \ldots \supset \mathcal{C}_{r-1}$. Such a convolutional code $\mathcal{C}_{\text{convol}}$ is composed of a \emph{semi-infinite chain of identical local codes} confined in a diagonal band of width $n$. Each local code $\mathcal{C}_{\text{local}}$ of $\mathcal{C}_{\text{convol}}$ is formed from the $r$ cyclic codes in the code chain and is a specially localized subcode of the \emph{mother code} $\mathcal{C}_0$ in the code chain. The minimum distance $d_{\text{local}}$ of each local code of $\mathcal{C}_{\text{convol}}$ is lower bounded by the minimum distance $d_0$ of the mother code $\mathcal{C}_0$ in the code chain. The local structure of $\mathcal{C}_{\text{convol}}$ allows it to be decoded based on a designed parity-check matrix of the mother code $\mathcal{C}_0$ using a sliding window decoding scheme.