Construction and Decoding of Convolutional Codes with optimal Column Distances

Julia Lieb, Michael Schaller · 2026

Read Construction and Decoding of Convolutional Codes with optimal Column Distances by Julia Lieb, Michael Schaller (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20825.txt.

Introduction

Julia Lieb and Michael Schaller construct a family of error-correcting codes with strong distance properties. Their 2026 paper concerns convolutional codes with optimal column distances. A convolutional code protects a stream of data by mixing nearby symbols. Column distances measure how well errors can be caught early in the stream. Codes with the best profile are called maximum distance profile codes.

Building those best codes usually demands very large finite fields. Large fields make coding and decoding costly. Codes with optimal column distances take a different deal. They maximize the column distances for whatever field is given, large or small. The authors present a construction of such codes. They also cover how to decode them. The result gives code designers strong protection without the price of huge fields.

Catalog record

CREATORJulia Lieb, Michael Schaller
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-20825

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Construction and Decoding of Convolutional Codes with optimal Column Distances Julia Lieb, Michael Schaller Abstract The construction of Maximum Distance Profile (MDP) convolutional codes in general requires the use of very large finite fields. In contrast convolutional codes with optimal column distances maximize the column distances for a given arbitrary finite field. In this paper, we present a construction of such convolutional codes. In addition, we prove that for the considered parameters the codes that we constructed are the only ones achieving optimal column distances. The structure of the presented convolutional codes with optimal column distances is strongly related to first order Reed-Muller block codes and we leverage this fact to develop a reduced complexity version of the Viterbi algorithm for these codes. 1 Introduction Convolutional codes form a class of error-correcting codes which is mainly used for the transmission of streams of data. In contrast to classical linear block codes, where data blocks of fixed size are encoded and decoded independently, convolutional codes possess memory, i.e., in the encoding process dependencies between different data blocks are created. These dependencies allow correction of error patterns that cannot be corrected with block codes of the same length. The drawback is that this additional security against errors also makes the decoding process more complex. The Viterbi algorithm, the most famous decoding algorithm for convolutional codes, has a complexity that is growing exponentially with the memory of the code; see [ 18 ] . Hence, there have been various attempts to make this algorithm more efficient. In addition to the efficiency of the decoding process, the other crucial property of an error-correcting code is the number of errors it can correct. Among the most important measures for the error-correcting capability of a convolutional code are its column distances. There exist Singleton-like upper bounds for these column distances and convolutional codes that reach a maximal number of these upper bounds with equality are called Maximum Distance Profile (MDP) codes. While MDP codes have optimal error-correcting properties, their construction requires in general very large finite fields, see e.g. [ 10 ] , [ 4 ] , [ 3 ] , which makes such constructions often impractical. Therefore, our approach is to first fix the finite field arbitrarily and then determine the largest possible column distances over this given finite field, where we prioritize maximizing the first column distances. In this way we define the notion of optimal column distances. We then present a construction for convolutional codes with optimal column distances for certain code rates. Moreover, we prove that for the given code parameters this construction is the only one achieving optimal column distances. Since our construction uses MacDonald codes and therefore first order Reed-Muller codes as building blocks, we are able to present a reduced complexity version of the Viterbi algorithm for these specific codes with optimal column distances using an efficient algorithm for the decoding of first order Reed Muller codes. Note that this generalizes the work in [ 1 ] and in [ 2 ] to arbitrary finite fields. In [ 1 ] binary convolutional codes with optimal column distances were constructed and in [ 2 ] an efficient decoding algorithm for these codes was presented. To obtain also good constructions for different code rates than the ones covered by our optimal construction, we modify this initial construction using directly first order Reed Muller codes or simplex codes as building blocks. Doing this we loose the optimality of the column distances but the column distances are still close to optimal and the modified constructions can be decoded with the Viterbi algorithm with the same reduced complexity as the original construction. The paper is structured as follows. In Section 2 , we give some background on block codes and convolutional codes, in Section 3 we describe the Viterbi algorithm for convolutional codes. In Section 4 , we present our construction of convolutional codes with optimal column distances. In Section 5 , we explain a decoding algorithm for first order Reed Muller codes and MacDonald codes that we will use in the following. In Section 6 , we present an improved Viterbi algorithm for the codes constructed in Section 4 using results of Section 5 and analyze the complexity of this algorithm. In Section 7 , we present two alternative constructions with good column distances and the same reduced complexity with the Viterbi algorithm as the construction of Section 4 . 2 Preliminaries Let \mathbb{F}_{q} denote a finite field with q elements and denote by \mathbb{F}_{q}[z] the ring of polynomials over \mathbb{F}_{q} . 2.1 Linear block codes In this subsection, we introduce linear block codes with a focus on MacDonald codes, which we will use later for our convolutional code construction. Definition 2.1 . A q -ary [n,k] linear block code C of length n and dimension k is a k -dimensional subspace of \mathbb{F}_{q}^{n} . This means that there exists a generator matrix G\in\mathbb{F}_{q}^{k\times n} of full row rank such that C=\left\{c=uG\in\mathbb{F}_{q}^{n}:\,u\in\mathbb{F}_{q}^{k}\right\}. We denote by \operatorname{wt}(v) the (Hamming) weight of v\in\mathbb{F}_{q}^{n} and by d(u,v) the (Hamming) distance between u,v\in\mathbb{F}_{q}^{n} . We define the minimum (Hamming) distance of C as d_{min}(C)=\min_{u,v\in C,\ u\neq v}d(u,v)=\min_{c\in C\setminus\{0\}}\operatorname{wt}(c). Definition 2.2 . A matrix M\in\mathbb{F}_{q}^{n\times n} is called a monomial matrix if it can be written as M=DP where D\in\mathbb{F}_{q}^{n\times n} is an invertible diagonal matrix and P\in\mathbb{F}_{q}^{n\times n} is a permutation matrix. Note that if we multiply a generator matrix of a linear code with a monomial matrix on the right the parameters of the corresponding code remain unchanged. There exist several bounds relating the different parameters of a linear block code. To optimize the error-correcting capacity it is desirable to construct codes meeting one of these bounds. In the next theorem, we present the Plotkin bound which is met by simplex codes. We will use a result related to this for the proof that the convolutional codes we construct later in the paper have optimal column distances. Theorem 2.3 . [ 17 , Theorem 5.2.4] Let C\subset\mathbb{F}_{q}^{n} be a linear block code with d:=d_{min}(C)<n(1-\frac{1}{q}) . Then, |C|\leq\frac{d}{d-n(1-\frac{1}{q})}. In the following, we define and describe MacDonald codes, the building blocks for our convolutional code construction with optimal column distances. MacDonald codes were introduced in [ 13 ] for the binary case and generalized to arbitrary finite fields in [ 15 ] . These codes are closely related to simplex codes, which we therefore recall first. Let S(q,m)\in\mathbb{F}_{q}^{m\times\frac{q^{m}-1}{q-1}} be a generator matrix of a q-ary simplex code \mathcal{S}(q,m) , i.e., the columns of S(q,m) form a set of representatives for the \frac{q^{m}-1}{q-1} distinct one-dimensional subspaces of \mathbb{F}_{q}^{m} . We have the following lemma. Lemma 2.4 . Let S(q,m),S^{\prime}(q,m) be two generator matrices of simplex codes of the same dimension. Then S^{\prime}(q,m)=S(q,m)M for some monomial matrix M . Proof. Note that row operations do not change the fact that any two columns of a generator matrix are linearly independent. Therefore, row operations just change the set of column representatives. It is clear that any two sets of column representatives are related by right multiplication with a monomial matrix. ∎ Independently of the choice of representatives, there are exactly \frac{q^{m-k}-1}{q-1} of these columns whose first k entries are equal to

Read the complete text