Maximum Distance Profile (MDP) convolutional codes are an important class of channel codes due to their maximal delay-constrained error correction capabilities. The design of MDP codes has attracted significant attention from the research community. However, only limited attention was given to addressing the complexity of encoding and decoding operations. This paper aims to reduce encoding complexity by constructing partial unit-memory MDP codes with structured and sparse generator matrices. In particular, we present a matrix completion framework that extends a structured superregular matrix (e.g., Cauchy) over a small field to a sparse sliding generator matrix of an MDP code. We show that the proposed construction can reduce the encoding complexity compared to the current state-of-the-art MDP code designs.

In this paper, we present a framework for generic decoding of convolutional codes, which allows us to do cryptanalysis of code-based systems that use convolutional codes as public keys. We then apply this framework to information set decoding, study success probabilities and give tools to choose variables. Finally, we use this to attack two cryptosystems based on convolutional codes. In the case of Bolkema et al. (Variations of the McEliece cryptosystem. In: Algebraic geometry for coding theory and cryptography: IPAM, Los Angeles, CA, Feb 2016. Springer, Cham, pp 129-150, 2017. https://doi.org/10.1007/978-3-319-63931-4_5), our code recovered about 74% of errors in less than 10 h each, and in the case of Almeida et al. (Smaller keys for code-based cryptography: McEliece cryptosystems with convolutional encoders. CoRR abs/2104.06809, 2021. arXiv: https://arxiv.org/abs/2104.06809v1), we give experimental evidence that 80% of the errors can be recovered in times corresponding to about 70 bits of operational security, with some instances being significantly lower.

Abstract In this paper, we propose a new erasure decoding algorithm for convolutional codes using the generator matrix. This implies that our decoding method also applies to catastrophic convolutional codes in opposite to the classic approach using the parity-check matrix. We compare the performance of both decoding algorithms. Moreover, we enlarge the family of optimal convolutional codes (complete-MDP) based on the generator matrix.

The most famous error-decoding algorithm for con-volutional codes is the Viterbi algorithm. In this paper, we present a new reduced complexity version of this algorithm which can be applied to a class of binary convolutional codes with optimum column distances called k-partial simplex convolutional codes.

This paper investigates the concept of self-dual convolutional codes. We derive the basic properties of this interesting class of codes and we show how some of the techniques to construct self-dual linear block codes generalize to self-dual convolutional codes. As for self-dual linear block codes we are able to give a complete classification for some small parameters.

There exists a large literature of construction of convolutional codes with maximal or near maximal free distance. Much less is known about constructions of convolutional codes having optimal or near optimal column distances. In this paper, a new construction of convolutional codes over the binary field with optimal column distances is presented.

Abstract In this paper, a construction of $$(n,k,\delta )$$ ( n , k , δ ) LDPC convolutional codes over arbitrary finite fields, which generalizes the work of Robinson and Bernstein and the later work of Tong is provided. The sets of integers forming a (k, w)-(weak) difference triangle set are used as supports of some columns of the sliding parity-check matrix of an $$(n,k,\delta )$$ ( n , k , δ ) convolutional code, where $$n\in {\mathbb {N}}$$ n ∈ N , $$n>k$$ n > k . The parameters of the convolutional code are related to the parameters of the underlying difference triangle set. In particular, a relation between the free distance of the code and w is established as well as a relation between the degree of the code and the scope of the difference triangle set. Moreover, we show that some conditions on the weak difference triangle set ensure that the Tanner graph associated to the sliding parity-check matrix of the convolutional code is free from $$2\ell $$ 2 ℓ -cycles not satisfying the full rank condition over any finite field. Finally, we relax these conditions and provide a lower bound on the field size, depending on the parity of $$\ell $$ ℓ , that is sufficient to still avoid $$2\ell $$ 2 ℓ -cycles. This is important for improving the performance of a code and avoiding the presence of low-weight codewords and absorbing sets.

This paper provides a construction of non-binary LDPC convolutional codes, which generalizes the work of Robinson and Bernstein. The sets of integers forming an (n - 1,w)- difference triangle set are used as supports of the columns of rate (n - 1)/n convolutional codes. If the field size is large enough, the Tanner graph associated to the sliding parity-check matrix of the code is free from 4 and 6-cycles not satisfying the full rank condition. This is important for improving the performance of a code and avoiding the presence of low-weight codewords and absorbing sets. The parameters of the convolutional code are shown to be determined by the parameters of the underlying difference triangle set. In particular, the free distance of the code is related to w and the degree of the code is linked to the "scope" of the difference triangle set. Hence, the problem of finding families of difference triangle set with minimum scope is equivalent to find convolutional codes with small degree.

Maximum distance profile (MDP) convolutional codes have been proven to be very suitable for transmission over an erasure channel. In addition, the subclass of complete MDP convolutional codes has the ability to restart decoding after a burst of erasures. However, there is a lack of constructions of these codes over fields of small size. In this article, we introduce the notion of complete 3-MDP convolutional codes, which are a generalization of complete MDP convolutional codes, and describe their decoding properties. In particular, we present a decoding algorithm for decoding erasures within a given time delay T and show that complete T-MDP convolutional codes are optimal for this algorithm. Moreover, using a computer search with the MAPLE software, we determine the minimal binary and non-binary field size for the existence of (2, 1, 2) complete 3-MDP convolutional codes and provide corresponding constructions. We give a description of all (2, 1, 2) complete MDP convolutional codes over the smallest possible fields, namely F13and F16and we also give constructions for (2, 1, 3) complete 4-MDP convolutional codes over F128obtained by a randomized computer search.