Publications

Click on a publication for abstract and download options.

All algorithms proposed in my papers have been implemented. Some of these are merged into Codinglib, my Sage library for algebraic coding theory, or are available in individual repositories, linked to under the respective article.

2017
Sven Puchinger, Johan Rosenkilde, John Sheekey

We present a new family of maximum rank distance (MRD) codes. The new class contains codes that are neither equivalent to a generalised Gabidulin nor to a twisted Gabidulin code, the only two known general constructions of linear MRD codes.

Download the paper Goto the arXiv page
2017
Sven Puchinger, Johan Rosenkilde, Irene Bouw

We propose a new partial decoding algorithm for one-point Hermitian codes that can decode up to the same number of errors as the Guruswami–Sudan decoder. Simulations suggest that it has a similar failure probability as the latter one. The algorithm is based on a recent generalization of the power decoding algorithm for Reed–Solomon codes and does not require an expensive root-finding step. In addition, it promises improvements for decoding interleaved Hermitian codes.

Download the paper Goto the arXiv page
(2017)
Elise Barelli, Peter Beelen, Mrinmoy Datta, Vincent Neiger, Johan Rosenkilde

In this article we investigate AG codes constructed using the generalized Giulietti-Korchmaros curve. More precisely we consider two-point codes coming from this curve. A special case was considered in [Castellanos–Tizziotti–16], where two-point codes coming from the Giulietti-Korchmaros curve were studied. However, even in this special case, our results improve upon what is currently known. Our method builds on the order bound for AG codes, which is why we study several Weierstrass semigroups before stating our results on two-point codes. We find several further improvements upon the MinT tables.

Download the paper Goto the arXiv page
2017
Mohamed Khochtali, Johan Rosenkilde né Nielsen, Arne Storjohann

Let \(\mathsf{F}[\partial; \sigma, \delta]\) be a ring of Ore polynomials over a field. We give a new deterministic algorithm for computing the Popov form \(P\) of a nonsingular matrix \(A \in \mathsf{F}[\partial; \sigma, \delta]^{n \times n}\). Our main focus is to ensure controlled growth in the size of coefficients from \(\mathsf{F}\) in the case \(\mathsf{F} = \mathsf{K}(z)\), and even \(\mathsf{K} = \mathbb{Q}\). Our algorithms are based on constructing from \(A\) a linear system over \(\mathsf{F}\) and performing a structured fraction-free Gaussian elimination. The algorithm is output sensitive, with a cost that depends on the orthogonality defect of the input matrix: the sum of the row degrees in \(A\) minus the sum of the row degrees in \(P\). The resulting bit-complexity for the differential and shift polynomial case over \(\mathbb{Q}(z)\) improves upon the previous best.

Download the paper
2017
Vincent Neiger, Johan Rosenkilde, Éric Schost

We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field \(\mathbb{K}\). More precisely, given a precision \(d\), and a polynomial \(Q\) whose coefficients are power series in \(x\), the algorithm computes a representation of all power series \(f(x)\) such that \(Q(f(x)) = 0 \bmod x^d\). The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails. Our main motivation comes from coding theory where instances of this problem arise and multiple roots must be handled.

The cost bound for our algorithm matches the worst-case input and output size \(d \deg(Q)\), up to logarithmic factors. This improves upon previous algorithms which were quadratic in at least one of \(d\) and \(\deg(Q)\). Our algorithm is a refinement of a divide & conquer algorithm by Alekhnovich (2005), where the cost of recursive steps is better controlled via the computation of a factor of \(Q\) which has a smaller degree while preserving the roots.

Download the paper Goto the arXiv page
2017
Sven Puchinger, Johan Rosenkilde né Nielsen

We propose a new partial decoding algorithm for \(m\)-interleaved Reed–Solomon (IRS) codes that can decode, with high probability, a random error of relative weight \(1-R^{\frac m {m+1}}\) at all code rates \(R\), in time polynomial in the code length \(n\). This is an asymptotic improvement over the previous state-of-the-art for all rates, and the first improvement for \(R > 1/3\) in the last 20 years. The method combines collaborative decoding of IRS codes with power decoding up to the Johnson radius.

Download the paper Goto the arXiv page
Repository with implementations
2017
Peter Beelen, Sven Puchinger, Johan Rosenkilde né Nielsen

We present a new general construction of MDS codes over a finite field \(\mathbb{F}_q\). We describe two explicit subclasses which contain new MDS codes of length at least \(q/2\) for all values of \(q \ge 11\). Moreover, we show that most of the new codes are not equivalent to a Reed–Solomon code.

Download the paper Goto the arXiv page
Repository with implementations
2017
Sven Puchinger and Johan Rosenkilde né Nielsen and Wenhui Li and Vladimir Sidorenko
In Journal of Designs, Codes and Cryptography, vol. 82 (1), pp. 389-409

For many algebraic codes the main part of decoding can be reduced to row reduction of a module basis, enabling general, flexible and highly efficient algorithms. Inspired by this, we develop an approach of transforming matrices over skew polynomial rings into certain normal forms. We apply this to solve generalised shift register problems, or Pad'e approximations, over skew polynomial rings which occur in error and erasure decoding \(\ell\)-Interleaved Gabidulin codes. We obtain an algorithm with complexity \(O(\ell \mu^2)\) where \(\mu\) measures the size of the input problem. Further, we show how to list-\(\ell\) decode Mahdavifar–Vardy subspace codes in \(O(\ell r^2 m^2)\) time, where \(m\) is a parameter proportional to the dimension of the codewords’ ambient space and \(r\) is the dimension of the received subspace.

Download the paper Goto the arXiv page
2016
Johan Rosenkilde né Nielsen, Arne Storjohann

We describe how to solve simultaneous Padé approximations over a power series ring \(K[[x]]\) for a field \(K\) using \(O~(n^{\omega - 1} d)\) operations in \(K\), where \(d\) is the sought precision and \(n\) is the number of power series to approximate. We develop two algorithms using different approaches and with different advantages. Both algorithms return reduced bases for the complete set of solutions to the input approximation problem. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite Padé approximations.

Go to the publication page for the paper Download the paper (preprint) Goto the arXiv page (preprint)
Repository with implementations
2016
Sven Puchinger and Sven Müelich and David Mödinger and Johan Rosenkilde and Martin Bossert

We prove that Alekhnovich’s algorithm can be used for row reduction of skew polynomial matrices. This yields an \(O(\ell^3 n^{(w+1)/2}\log(n))\) decoding algorithm for \(\ell\)-Interleaved Gabidulin codes of length \(n\), where \(w\) is the matrix multiplication exponent, improving in the exponent of \(n\) compared to previous results.

Download the paper Goto the arXiv page
(2016)
Johan S. R. Nielsen

Power decoding, or “decoding using virtual interleaving” is a technique for decoding Reed–Solomon codes up to the Sudan radius. Since the method’s inception, it has been an open question if it possible to incorporate “multiplicities”, the parameter allowing the Guruswami–Sudan algorithm to decode up to the Johnson radius. In this paper we show how this can be done, and describe how to efficiently solve the resulting key equations. We investigate its failure behaviour theoretically as well as giving simulation results.

In an extended version (the one here and on arXiv), we also show how the method can be made practically faster using the re-encoding technique or a syndrome formulation.

Download the paper Goto the arXiv page
Repository with implementations
2015
Wenhui Li, Johan S. R. Nielsen, Sven Puchinger, Vladimir Sidorenko

For many algebraic codes the main part of decoding can be reduced to a shift register synthesis problem. In this paper we present an approach for solving generalised shift register problems over skew polynomial rings which occur in error and erasure decoding of \(\ell\)-Interleaved Gabidulin codes. The algorithm is based on module minimisation and has time complexity \(O(\ell \mu^2)\) where \(\mu\) measures the size of the input problem.

Note: this publication has been superseded.

Download the paper Goto the arXiv page
2015
Johan S. R. Nielsen and Peter Beelen
In IEEE Transactions on Information Theory, vol. 61 (6), pp. 3225-3240

We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realisation of the Guruswami–Sudan algorithm by using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimisation. The second is a Power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimisation algorithms from computer algebra, yielding similar asymptotic complexities.

Go to the publication page for the paper Download the paper (preprint) Goto the arXiv page (preprint)
Repository with implementations
2014
Johan S. R. Nielsen

Power decoding, or “decoding by virtual interleaving”, of Reed–Solomon codes is a method for unique decoding beyond half the minimum distance. We give a new variant of the Power decoding scheme, building upon the key equation of Gao. We show various interesting properties such as behavioural equivalence to the classical scheme using syndromes, as well as a new bound on the failure probability when the powering degree is 3.

Go to the publication page for the paper Download the paper (preprint) Goto the arXiv page (preprint)
Repository with implementations
2014
Johan S. R. Nielsen

Power decoding, or “decoding using virtual interleaving” is a technique for decoding Reed–Solomon codes up to the Sudan radius. Since the method’s inception, it has been a tantalising goal to incorporate multiplicities, the parameter allowing the Guruswami–Sudan algorithm to decode up to the Johnson radius. In this paper we show how this can be done, and describe how to efficiently solve the resulting key equations.

Note: this publication has been superseded.

Download the paper
2014
Johan S. R. Nielsen

The Kötter–Nielsen–Høholdt algorithm is a popular way to construct the bivariate interpolation polynomial in the Guruswami–Sudan decoding algorithm for Reed–Solomon codes. In this paper, we show how one can use Divide & Conquer techniques to provide an asymptotic speed-up of the algorithm, rendering its complexity quasi-linear in \(n\). Several of our observations can also provide a practical speed-up to the classical version of the algorithm.

Download the paper Goto the arXiv page
Repository with implementations
2014
Mostafa H. Mohammed, Johan S. R. Nielsen, Martin Bossert

We decode Reed-Solomon codes using soft information provided at the receiver. The Extended Euclidean Algorithm (EEA) is considered as an initial step to obtain an intermediate result. The final decoding result is obtained by interpolating the output of the EEA at the least reliable positions of the received word. We refer to this decoding method as reduced list-decoding, since not all received positions are used in the interpolation as in other list-decoding methods, such as the Guruswami–Sudan and Wu algorithms. Consequently the complexity of the interpolation step is reduced considerably. The probability of failure can be minimised by adjusting certain parameters, making it comparable with the Kötter–Vardy algorithm but having a much lower complexity.

Go to the publication page for the paper Download the paper (preprint) Goto the arXiv page (preprint)
2014
Johan S. R. Nielsen
Technical report

We consider a type of Padé approximations over polynomial rings over fields, dubbed “2D Padé approximations”, which generalise both simultaneous and Hermitian Padé approximations. This form is related to but distinct from both matrix-Padé approximations as well as order bases. These approximations occur in e.g.~decoding of algebraic codes.

We demonstrate how to solve such approximations using row reduction of polynomial matrices, and we review the achieved asymptotic complexity when using various fast, known methods for this.

We take a closer look at the Mulders–Storjohann for row reduction and show that its complexity is linked to the orthogonality defect of the input matrix, implying that it is fast when applied to 2D Padeé approximations. We design a new algorithm, which essentially carries out the computations performed by Mulders–Storjohann in a demand-driven manner, yielding an algorithm which is often even faster. This algorithm could be considered as a heavy generalisation of the classical Berlekamp–Massey algorithm.

We also consider “weighted” variants of 2D Padé approximations, and it is shown how the considered algorithms can handle this with very little speed penalty.

Download the paper
2014
Johan S. R. Nielsen and Alexander Zeh
In Journal of Designs, Codes and Cryptography, vol. 73 (2), pp. 507-527

An iterated refinement procedure for the Guruswami–Sudan list decoding algorithm for Generalised Reed–Solomon codes based on Alekhnovich’s module minimisation is proposed. The method is parametrisable and allows variants of the usual list decoding approach. In particular, finding the list of closest codewords within an intermediate radius can be performed with improved average-case complexity while retaining the worst-case complexity.

We provide a detailed description of the module minimisation, reanalysing the Mulders–Storjohann algorithm and drawing new connections to both Alekhnovich’s algorithm and Lee–O’Sullivan’s. Furthermore, we show how to incorporate the re-encoding technique of Kötter and Vardy into our iterative algorithm.

Go to the publication page for the paper Download the paper (preprint)
Repository with implementations
2013
Johan S. R. Nielsen

We show how to solve a generalised version of the Multi-sequence Linear Feedback Shift-Register (MLFSR) problem using minimisation of free modules over \(\mathbb F[x]\). We show how two existing algorithms for minimising such modules run particularly fast on these instances. Furthermore, we show how one of them can be made even faster for our use. With our modelling of the problem, classical algebraic results tremendously simplify arguing about the algorithms. For the non-generalised MLFSR, these algorithms are as fast as what is currently known. We then use our generalised MLFSR to give a new fast decoding algorithm for Reed–Solomon codes.

Go to the publication page for the paper Download the paper (preprint) Goto the arXiv page (preprint)
2013
Wenhui Li, Vladimir Sidorenko, Johan S. R. Nielsen

We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a \(\mathbb Z\)-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of “Power” decoding, suggested for Reed–Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.

Go to the publication page for the paper Download the paper (preprint)
2013
Johan S. R. Nielsen and Alexander Zeh

An iterated refinement procedure for the Guruswami–Sudan list decoding algorithm for Generalised Reed–Solomon codes based on Alekhnovich’s module minimisation is proposed. The method is parametrisable and allows variants of the usual list decoding approach. In particular, finding the list of closest codewords within an intermediate radius can be performed with improved average-case complexity while retaining the worst-case complexity.

Note: this publication has been superseded.

Goto the arXiv page
2013
Peter Beelen, Tom Høholdt, Johan S. R. Nielsen, and Yingquan Wu
In IEEE Transactions on Information Theory, vol. 59 (6), pp. 3269-3281

We derive the Wu list-decoding algorithm for Generalised Reed-Solomon (GRS) codes by using Gröbner bases over modules and the Euclidean algorithm (EA) as the initial algorithm instead of the Berlekamp-Massey algorithm (BMA). We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm (GSA), immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.

Go to the publication page for the paper Goto the arXiv page (preprint)
Repository with implementations
2009
Sune F. Nielsen, Jens Sparsø, Jonas B. Jensen, Johan S. R. Nielsen
Presented at ASYNC Conference

This paper presents a complete design tool which performs automatic behavioral synthesis of asynchronous circuits (resource sharing, scheduling and binding).

The tool targets a traditional control-datapath-style template architecture. Within the limitations set by this template architecture it is possible to optimize for area (which is our main focus) or for speed. This is done by simply using different cost functions.

Input to the tool is a behavioral description in the Haste language, and output from the tool is a Haste program describing the synthesized implementation consisting of a datapath and a controller. The tool may be seen as an add-on to the Haste/TiDE tool flow, and it can be used to automatically optimize parts of a design and to quickly explore alternative optimizations. The paper outlines the design flow, explains key elements of the design tool, and presents a number of benchmark results.

Theses

2013
Johan S. R. Nielsen
In PhD thesis

We investigate three paradigms for polynomial-time decoding of Reed–Solomon codes beyond half the minimum distance: the Guruswami–Sudan algorithm, Power decoding and the Wu algorithm. The main results concern shaping the computational core of all three methods to a problem solvable by module minimisation; by applying the fastest known algorithms for this general problem, we then obtain realisations of each paradigm which are as fast or faster than all previously known methods. An element of this is the “2D key equation”, a heavily generalised form of the classical key equation, and we show how to solve such using module minimisation, or using our new Demand–Driven algorithm which is also based on module minimisation.

The decoding paradigms are all derived and analysed in a self-contained manner, often in new ways or examined in greater depth than previously. Among a number of new results, we give: a fast maximum-likelihood list decoder based on the Guruswami–Sudan algorithm; a new variant of Power decoding, Power Gao, along with some new insights into Power decoding; and a new, module based method for performing rational interpolation for the Wu algorithm. We also show how to decode Hermitian codes using Guruswami–Sudan or Power decoding faster than previously known, and we show how to Wu list decode binary Goppa codes.

Download the paper
2010
Johan S. R. Nielsen
In MSc thesis

Recently, Wu proposed in [Wu08] a new approach to list decoding Reed-Solomon codes, quite different from the Guruswami-Sudan algorithm and its derivatives . It promises lower running-time and has shown new perspectives of the codes. Sadly, the impact of this idea has hitherto been minimal; the contribution is indisputable, so the reason might be found in the idea’s sole exposition: a convoluted article, presenting and proving a long range of intricate results on a strict page limit.

In this thesis, we give a complete, self-contained and novel presentation of Wu’s decoding algorithm. The key mechanics of the algorithm build on a combination of several previous decoders, and we begin with a full presentation of these and their background theory. We then derive Wu’s algorithm itself, with a clear division between the results in general algebraic theory, and the application of these on the decoding problem.

Download the paper