In this paper, we introduce an explicit family of subcodes of Reed-Solomon (RS) codes that efficiently achieve list decoding capacity with a constant output list size. The codes are constructed by initially forming the tensor product of two RS codes with carefully selected evaluation sets, followed by specific cyclic shifts to the codeword rows. This process results in each codeword column being treated as an individual coordinate, reminiscent of prior capacity-achieving codes, such as folded RS codes and univariate multiplicity codes. This construction is easily shown to be a subcode of an interleaved RS code, equivalently, an RS code evaluated on a subfield. Alternatively, the codes can be constructed by the evaluation of bivariate polynomials over orbits generated bytwoaffine transformations with coprime orders, extending the earlier use of a single affine transformation in folded RS codes and the recent affine folded RS codes introduced by Bhandari et al. (IEEE T-IT, Feb. 2024). While our codes require large, yet constant characteristic, the two affine transformations facilitate achieving code length equal to the field size, without the restriction of the field being prime, contrasting with univariate multiplicity codes.

In a paper from 2015, Ding et al. (IEEE Trans. IT, May 2015) conjectured that for odd m, the minimum distance of the binary BCH code of length$2^{m}-1$and designed distance$2^{m-2}+1$is equal to the Bose distance calculated in the same paper. In this paper, we prove the conjecture. In fact, we prove a stronger result suggested by Ding et al.: the weight of the generating idempotent is equal to the Bose distance for both odd and even m. Our main tools are some new properties of the so-called fibbinary integers, in particular, the splitting field of related polynomials, and the relation of these polynomials to the idempotent of the BCH code.

In this paper, we introduce a novel explicit family of subcodes of Reed-Solomon (RS) codes that efficiently achieve list decoding capacity with a constant output list size. Our approach builds upon the idea of large linear subcodes of RS codes evaluated on a subfield, similar to the method employed by Guruswami and Xing (STOC 2013). However, our approach diverges by leveraging the idea of permuted product codes, thereby simplifying the construction by avoiding the need of subspace designs. Specifically, the codes are constructed by initially forming the tensor product of two RS codes with carefully selected evaluation sets, followed by specific cyclic shifts to the codeword rows. This process results in each codeword column being treated as an individual coordinate, reminiscent of prior capacity-achieving codes, such as folded RS codes and univariate multiplicity codes. This construction is easily shown to be a subcode of an interleaved RS code, equivalently, an RS code evaluated on a subfield.11Due to space limitation the proofs are omitted and can be found in [1].

We present$O(m^{3})$algorithms for specifying the support of minimum-weight codewords of extended binary BCH codes of length$n=2^{m}$and designed distance$d(m,s,i):=2^{m-1-s}-2^{m-1-i-s}$for some values of$m,i,s$, where m may grow to infinity. Here, the support is specified as the sum of two sets: a set of$2^{2i-1}-2^{i-1}$elements, and a subspace of dimension$m-2i-s$, specified by a basis. In some detail, for designed distance$6\cdot 2^{j}$,$j\in \{0,\ldots ,m-4\}$, we have a deterministic algorithm for even$m\geq 4$, and a probabilistic algorithm with success probability$1-O(2^{-m})$for odd$m\gt 4$. For designed distance$28\cdot 2^{j}$,$j\in \{0,\ldots , m-6\}$, we have a probabilistic algorithm with success probability$\geq \frac {1}{3}-O(2^{-m/2})$for even$m\geq 6$. Finally, for designed distance$120\cdot 2^{j}$,$j\in \{0,\ldots , m-8\}$, we have a deterministic algorithm for$m\geq 8$divisible by 4. We also show how Gold functions can be used to find the support of minimum-weight words for designed distance$d(m,s,i)$(for$i\in \{0,\ldots ,\lfloor m/2\rfloor \}$, and$s\leq m-2i$) whenever$2i|m$. Our construction builds on results of Kasami and Lin, who proved that for extended binary BCH codes of designed distance$d(m,s,i)$(for integers$m\geq 2$,$0\leq i\leq \lfloor m/2\rfloor $, and$0\leq s\leq m-2i$), the minimum distance equals the designed distance. The proof of Kasami and Lin makes use of a non-constructive existence result of Berlekamp, and a constructive “down-conversion theorem” that converts some words in BCH codes to lower-weight words in BCH codes of lower designed distance. Our main contribution is in replacing the non-constructive counting argument of Berlekamp by a low-complexity algorithm. In one aspect, the current paper extends the results of Grigorescu and Kaufman, who presented explicit minimum-weight codewords for extended binary BCH codes of designed distance exactly 6 (and hence also for designed distance$6\cdot 2^{j}$, by a well-known “up-conversion theorem”), as we cover more cases of the minimum distance. In fact, we prove that the codeword constructed by Grigorescu and Kaufman is a special case of the current construction. However, the minimum-weight codewords we construct do not generate the code, and are not affine generators, except, possibly, for a designed distance of 6.

We present a new fast Chase decoding algorithm for binary BCH codes. The new algorithm reduces the complexity in comparison to a recent fast Chase decoding algorithm for Reed–Solomon (RS) codes by the authors (IEEE Trans. IT, 2022), by requiring only a single Kötter iteration per edge of the decoding tree. In comparison to the fast Chase algorithms presented by Kamiya (IEEE Trans. IT, 2001) and Wu (IEEE Trans. IT, 2012) for binary BCH codes, the polynomials updated throughout the algorithm of the current paper typically have a much lower degree. To achieve the complexity reduction, we build on a new isomorphism between two solution modules in the binary case, and on a degenerate case of the soft-decision (SD) version of the Wu list decoding algorithm. Roughly speaking, we prove that when the maximum list size is 1 in Wu list decoding of binary BCH codes, assigning a multiplicity of 1 to a coordinate has the same effect as flipping this coordinate in a Chase-decoding trial. The solution-module isomorphism also provides a systematic way to benefit from the binary alphabet for reducing the complexity in bounded-distance hard-decision (HD) decoding. Along the way, we briefly develop the Gröbner-bases formulation of the Wu list decoding algorithm for binary BCH codes, which is missing in the literature.

We consider the repair problem for Reed–Solomon (RS) codes, evaluated on an$\mathbb {F}_{q}$-linear subspace$U\subseteq \mathbb {F}_{q^{m}} $of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb {F}_{q}$is the Galois field of size$q$. For$q>2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}$,$s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb {F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least$1/3$) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme. Our result extend the construction of Dau–Milenkovic to the range$r < m-s$, for a wide range of parameters.

We present a simple syndrome-based fast Chase decoding algorithm for Reed–Solomon (RS) codes. Such an algorithm was initially presented by Wu (IEEE Trans. IT, Jan. 2012), building on properties of the Berlekamp–Massey (BM) algorithm. Wu devised a fast polynomial-update algorithm to construct the error-locator polynomial (ELP) as the solution of a certain linear-feedback shift register (LFSR) synthesis problem. This results in a conceptually complicated algorithm, divided into 8 subtly different cases. Moreover, Wu’s polynomial-update algorithm is not immediately suitable for working with vectors of evaluations. Therefore, complicated modifications were required in order to achieve a true “one-pass” Chase decoding algorithm, that is, a Chase decoding algorithm requiring$O(n)$operations per modified coordinate, where$n$is the RS code length. The main result of the current paper is a conceptually simple syndrome-based fast Chase decoding of RS codes. Instead of developing a theory from scratch, we use the well-established theory of Gröbner bases for modules over$\mathbb {F}_{q}[X]$(where$\mathbb {F}_{q}$is the finite field of$q$elements, for$q$a prime power). The basic observation is that instead of Wu’s LFSR synthesis problem, it is much simpler to consider “the right” minimization problem over amodule. The solution to this minimization problem is a simple polynomial-update algorithm that avoids syndrome updates and works seamlessly with vectors of evaluations. As a result, we obtain a conceptually simple algorithm for one-pass Chase decoding of RS codes. Our algorithm is general enough to work with any algorithm that finds a Gröbner basis for the solution module of the key equation as the initial algorithm (including the Euclidean algorithm), and it is not tied only to the BM algorithm.

We consider the repair problem for Reed-Solomon (RS) codes, evaluated on an$\mathbb{F}_{q}$-linear subspace$U \subseteq \mathbb{F}_{q^{m}}$of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb{F}_{q}$is the Galois field of size$q$. For$q > 2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}, s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb{F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least 1/3) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme.

We consider asymptotically good nonlinear codes recently introduced by Xing (2003). The original definition of these codes relies on a nonconstructive averaging argument. In this paper, it is first shown that in some cases, the codes can be constructed without using any averaging arguments. We then introduce an alternative construction of the codes, based on the union of a geometric Goppa code and its cosets. In some cases, the problem of explicitly describing the codes reduces to the problem of explicitly describing certain n elements of the relevant function field, where n is the code length. Moreover, the number of finite-field operations required to construct these n elements after the construction of the generator matrix of the geometric Goppa code is of the order of n/sup 3/.

Nonlinear Xing codes are considered. It is shown that Xing codes of length p-1 (where p is a prime) are subcodes of cosets of Reed-Solomon codes whose minimum distance equals Xing's lower bound on the minimum distance. This provides a straightforward proof for the lower bound on the minimum distance of the codes. The alphabet size of Xing codes is restricted not to be larger than the characteristic of the relevant finite field F/sub r/. It is shown that codes with the same length and the same lower bounds on the size and minimum distance as Xing codes exist for any alphabet size not exceeding the size r of the relevant finite field, thus extending Xing's results.

Lower bounds on the state complexity of linear tail-biting trellises are presented. One bound generalizes the total-span bound, while another bound can be regarded as a generalization of the cut-set bound. It is shown by examples that the new bounds may be tighter than any of the existing lower bounds.

Linear tail-biting trellises for block codes are considered. By introducing the notions of subtrellis, merging interval, and sub-tail-biting trellis, some structural properties of linear tail-biting trellises are proved. It is shown that a linear tail-biting trellis always has a certain simple structure, the parallel-merged-cosets structure. A necessary condition required from a linear code in order to have a linear tail-biting trellis representation that achieves the square root bound is presented. Finally, the above condition is used to show that for r/spl ges/2 and m/spl ges/4r-1 or r/spl ges/4 and r+3/spl les/m/spl les/[(4r+5)/3] the Reed-Muller code RM(r, m) under any bit order cannot be represented by a linear tail-biting trellis whose state complexity is half of that of the minimal (conventional) trellis for the code under the standard bit order.

An upper bound on the minimal state complexity of codes from the Hermitian function field and some of its subfields is derived. Coordinate orderings under which the state complexity of the codes is not above the bound are specified. For the self-dual Hermitian code it is proved that the bound coincides with the minimal state complexity of the code. Finally, it is shown that Hermitian codes over fields of characteristic 2 admit a recursive twisted squaring construction.

The trellis complexity of the Preparata and Goethals codes is examined. It is shown that at least for a given set of permutations these codes are rectangular. Upper bounds on the state complexity profiles of the Preparata and Goethals codes are given. The upper bounds on the state complexity of the Preparata and Goethals codes are determined by the dimension/length profiles (DLP) of the extended primitive double- and triple-error-correcting BCH codes, respectively. A twisted squaring construction for the Preparata and Goethals codes is given, based on the double- and triple-error-correcting extended primitive BCH codes, respectively.

In this correspondence, the trellis representation of the Kerdock and Delsarte-Goethals codes is addressed. It is shown that the states of a trellis representation of DG(m,/spl delta/) under any bit-order are either strict-sense nonmerging or strict-sense nonexpanding, except, maybe, at indices within the code's distance set. For /spl delta//spl ges/3 and for m/spl ges/6, the state complexity, s/sub max/[DG(m,/spl delta/)], is found. For all values of m and /spl delta/, a formula for the number of states and branches of the biproper trellis diagram of DG(m, /spl delta/) is given for some of the indices, and upper and lower bounds are given for the remaining indices. The formula and the bounds refer to the Delsarte-Goethals codes when arranged in the standard bit-order.