Due to its longevity and enormous information density, DNA is an attractive medium for archival storage. In DNA-based storage, coding techniques (DNA codes) are widely studied to protect data from errors. Besides, some biochemical means are necessary in DNA data processing and storage which may increase data error probability. So DNA codes with some biochemical constraints are desired.In this paper, we construct DNA codes with biochemical constraints, including GC-content constraint, homopolymer run-length limit and secondary structure avoidance, as well as error correcting property. We present novel constructions of DNA codes with high code rate. At first, we give a method to construct constrained DNA codes free of secondary structures of stem length m = 3 and homopolymer run-length > ℓ for any given ℓ ≥ 3. In particular, when ℓ = 4, the code has rate 1.4057 and beats a previous work by Benerjee et al. asymptotically. Then, we construct DNA codes with all of the three mentioned constraints simultaneously as well as single error correction via a code concatenation technique. To the best of our knowledge, few constructions are given to satisfy all these constraints and edit error correction with high code rate. At last, motivated by some PCR amplification techniques that require local GC-content constraint, a transformation converting codes with global GC-content constraint to codes with local GC-content constraint is presented.

Encoding and decoding of Reed-Muller codes have been a major research topic in coding and theoretical computer science communities. Despite of the fact that there have been numerous encoding and decoding algorithms in the literature, most of them are not quasi-linear time algorithms for arbitrary order Reed-Muller codes. Under the decoding framework proposed by Pellikaan and Wu (IEEE TIT, 2004) which regards Reed-Muller codes as subfield subcodes of Reed-Solomon codes, we propose a new decoding algorithm for Reed-Muller codes that improves previous polynomial decoding complexity to quasilinear complexity. Our new decoding algorithm includes multivariate multipoint evaluation (MPE) and interpolation under a new basis of the multivariate polynomial space as two main steps. We show that the MPE and interpolation at certain multipoint sets can be performed in quasi-linear time as well. Our approach is based on a well-known transform between univariate polynomials and multivariate polynomials. We make use of the key fact that the transformation matrix between univariate polynomials and multivariate polynomials is sparse. Due to sparsity, MPE and interpolation of multivariate polynomials and decoding of Reed-Muller codes can be reduced to MPE and interpolation of univariate polynomials and decoding of Reed-Solomon codes without extra cost respectively, i.e, the complexity of MPE and interpolation of multivariate polynomials (and, respectively, decoding of Reed-Muller codes) is dominated by that of MPE and interpolation of univariate polynomials (and, respectively, decoding of Reed-Solomon codes). As a result of this reduction, we obtain our quasi-linear time algorithms.

Fast encoding and decoding of codes have always been an important topic in coding theory as well as complexity theory. Although encoding is easier than decoding in general, designing an encoding algorithm of codes of lengthNwith quasi-linear complexityO(NlogN) is not an easy task. Despite of the fact that algebraic geometry codes (AG codes) were discovered in the early 1980s, encoding algorithms of algebraic geometry codes with quasi-linear complexityO(NlogN) have not been found except for the simplest algebraic geometry codes–Reed-Solomon codes. The best-known encoding algorithm of algebraic geometry codes based on a class of plane curves has quasi-linear complexity at leastO(Nlog2N) (Beelen et al. IEEE Trans. Inf. Theory 2021). In this paper, we design an encoding algorithm for algebraic geometry codes with quasi-linear complexityO(NlogN). Moreover, for these fast encodable AG codes, the inverse of encoding, that is, interpolating the message function from the corresponding codeword, can be computed with the same complexityO(NlogN). Our algorithms are applicable to a large class of algebraic geometry codes based on both plane and non-plane curves, including Kummer extensions, Artin-Schreier extensions, and Hermitian field towers.

Guruswami and Wootters first provided a decoding framework for repairing Reed-Solomon codes. There is a series of work after Guruswami-Wootters' repairing scheme. In particular, based on this framework a repairing scheme achieving the cut-set bound was presented by Tamo, Ye and Barg. Guruswami-Wootters' repairing scheme can be modified so that we require downloading less data, i.e., less communication bandwidth. We illustrate our improvement by two examples given in the pioneer paper by Guruswami and Wootters. These examples show that our repairing scheme can save bandwidth$(1-R)^{2}n$and$(1-2R)n$over the base field, respectively, where$R$is the code rate and$n$is the code length.

Determining the largest size, or equivalently finding the lowest redundancy, of q-ary codes for given length and minimum distance is one of the central and fundamental problems in coding theory. Inspired by the construction of Varshamov-Tenengolts (VT for short) codes via check-sums, we provide an explicit construction of nonlinear codes with lower redundancy than linear codes under the same length and minimum distance. Similar to the VT codes, our construction works well for small distance (or even constant distance). Furthermore, we design$O(n\log^{4}n)$bit operations decoding algorithms for both erasures and adversarial errors, where$n$is the code length.

Locally repairable codes have been extensively investigated due to practical applications in distributed and cloud storage systems in recent years. However, not much work on asymptotic behavior of locally repairable codes has been done. In particular, there is few result on constructive lower bound of asymptotic behavior of locally repairable codes with multiple recovering sets. In this paper, we construct some families of asymptotically good locally repairable codes with multiple recovering sets via automorphism groups of function fields of the Garcia-Stichtenoth towers. The main advantage of our construction is to allow more flexibility of localities.

A locally repairable code is called Singleton-optimal if it achieves the Singleton-type bound. Such codes are of great theoretic interest in the study of locally repairable codes. One of the major problems in this topic is to determine the maximum length of aq-ary Singleton-optimal locally repairable code with fixed locality and minimum distance. Unlike classical MDS codes, the maximum length of Singleton-optimal locally repairable codes is very sensitive to the minimum distance and locality. Thus, determining the maximum length of the Singleton-optimal locally repairable codes is more challenging and complicated. In literature, many efforts are paid to solve this problem especially for small distance and locality regime. Moreover, most of works also requires that (r+ 1)|nand the recovery sets are disjoint so as to simplify the argument,whereris locality andnis the code length. In this paper, we derive some upper bounds on the maximum length of Singleton-optimal locally repairable codes with minimum distance 5, 6 and 7 without the constraint that (r+ 1)|nand the recovery sets are disjoint.It turns out that even without this constraint we still obtain better upper bounds for codes with small locality and distance compared to known results. Furthermore, based on our upper bounds for codes with small distance and locality, we propose the propagation rule to derive some upper bounds for codes with relatively large distance and locality assuming that (r+1)|nand recovery sets are disjoint.

We consider the problem of efficient construction ofq-ary 2-deletion correcting codes with low redundancy. We show that our construction requires less redundancy than any existing efficiently encodableq-ary 2-deletion correcting codes. Precisely speaking, we present an explicit construction of aq-ary 2-deletion correcting code with redundancy 5 logn+10 log logn+ 3 logq+O(1) whereqis assumed to be a constant with respect ton. Using a minor modification to the original construction, we obtain an efficiently encodableq-ary 2-deletion code that is efficiently list-decodable. Similarly, we show that our construction of list-decodable code requires a smaller redundancy compared to any existing list-decodable codes. To obtain our sketches, we transform aq-ary code-word to a binary string which can then be used as an input to the underlying base binary sketch. This is then complemented with additionalq-ary sketches that the originalq-ary codeword is required to satisfy. In other words, we build our codes via a binary 2-deletion code as a black-box. Finally we utilize the binary 2-deletion code proposed by Guruswami and Håstad to our construction to obtain the main result of this paper.

The Gilbert-Varshamov (GV for short) bound has been a benchmark for good Hamming-metric codes. It was even conjectured by some coding theorists that the asymptotic Gilbert-Varshamov bound is tight. The GV bound had remained to be the best asymptotic lower bound for thirty years before it was broken by the Tsfasman-Vlăduţ-Zink bound via algebraic geometry codes. The discovery of algebraic geometry codes by Goppa was a breakthrough in coding theory. After another twenty years, no any improvements on the Tsfasman-Vlăduţ-Zink bound took place before the work by Xing-Elkies [14, 15, 1, 2] in the early of 2000 via tools from algebraic geometry. By using the similar ideas as in [14, 15, 9], some further improvements were given in [7, 17]. Since then, no further progress on asymptotic lower bounds has been made. The main result of this paper is to show that all previous asymptotic lower bounds can be improved in an interval. We present two types of constructions of Hamming-metric codes. Both constructions involve algebraic geometry and need insights on applications of algebraic geometry to coding theory. In order to obtain good codes, one construction requires a larger number of positive divisors of fixed degree, while other construction requires a smaller number of positive divisors of fixed degree. As a result, no matter how large the number of positive divisors of fixed degree is, we can always obtain codes with good parameters. It turns out that all previous asymptotic lower bounds are improved.

In classical coding theory, it is common to construct new codes via propagation rules. There are various propagation rules to construct classical block codes. However, propagation rules have not been extensively explored for locally repairable codes. In this paper, we systematically study some of propagation rules to construct optimal and asymptotically good locally repairable codes. To our surprise, these simple propagation rules produce interesting results. Firstly, by a lengthening propagation rule that adds some rows and columns to a parity-check matrix of a given linear code, we are able to convert a classical maximum distance separable (MDS) code into a Singleton-optimal locally repairable code and provide a simplified proof of the asymptotic Tafasman-Vlăduţ-Zink bound which exceeds the asymptotic Gilbert-Varshamov bound of locally repairable codes. Secondly, by concatenating a locally repairable code as an inner code with a classical block code as an outer code, we obtain a family of dimension-optimal locally repairable codes. Thirdly, we can make use of the shortening technique to produce more dimension-optimal locally repairable codes. Finally, one of phenomena that we observe in this paper is that some trivial propagation rules in classical block codes do not hold anymore for locally repairable codes.

In coding theory, constructing codes with good parameters is one of the most important and fundamental problems. A great many good codes have been constructed over alphabets of sizes equal to prime powers, however, good block codes over other alphabet sizes are rare. In this paper, we provide a new explicit construction of$(q+1)$-ary nonlinear codes via algebraic function fields, where$q$is a prime power. Our codes are constructed by evaluating rational functions at all rational places of an algebraic function field. Compared with algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes over the alphabet$\mathbb {F}_{q}\cup \{\infty \}$. It turns out that our codes have better parameters than those obtained from MDS codes or good algebraic geometry codes via code alphabet extension and restriction.

For codes equipped with metrics such as Hamming metric, symbol pair metric or cover metric, the Johnson bound guarantees list-decodability of such codes. That is, the Johnson bound provides a lower bound on the list-decoding radius of a code in terms of its relative minimum distance$\delta $, list size$L$and the alphabet size$q$. For study of list-decodability of codes with insertion and deletion errors (we call such codes insdel codes), it is natural to ask the open problem whether there is also a Johnson-type bound. The problem was first investigated by Wachter-Zeh and the result was amended by Hayashi and Yasunaga where a lower bound on the list-decodability for insdel codes was derived. The main purpose of this paper is to move a step further towards solving the above open problem. In this work, we provide a new lower bound for the list-decodability of an insdel code. As a consequence, we show that unlike the Johnson bound for codes under other metrics that is tight, the bound on list-decodability of insdel codes given by Hayashi and Yasunaga is not tight. Our main idea is to show that if an insdel code with a given Levenshtein distance$d$is not list-decodable with list size$L$, then the list decoding radius is lower bounded by a bound involving$L$and$d$. In other words, if the list decoding radius is less than this lower bound, the code must be list-decodable with list size$L$. At the end of the paper we use such bound to provide an insdel-list-decodability bound for various well-known codes, which has not been extensively studied before.

Insertion and deletion (insdel for short) codes have recently attracted a lot of attention due to their applications in many interesting fields such as DNA storage, DNA analysis, race-track memory error correction and language processing. The present paper mainly studies limits and constructions of insdel codes. The paper can be divided into two parts. The first part focuses on various bounds, while the second part concentrates on constructions of insdel codes. Although the insdel-metric Singleton bound has been derived before, it is still unknown if there are any nontrivial codes achieving this bound. Our first result shows that any nontrivial insdel codes do not achieve the insdel-metric Singleton bound. The second bound shows that every$[n,k]$Reed-Solomon code has insdel distance upper bounded by$2n-4k+4$and it is known in literature that an$[n,k]$Reed-Solomon code can have insdel distance$2n-4k+4$as long as the field size is sufficiently large. The third bound shows a trade-off between insdel distance and code alphabet size for codes achieving the Hamming-metric Singleton bound. In the second part of the paper, we first provide a non-explicit construction of nonlinear codes that can approach the insdel-metric Singleton bound arbitrarily when the code alphabet size is sufficiently large. The second construction gives two-dimensional Reed-Solomon codes of length$n$and insdel distance$2n-4$with field size$q=O(n^{5})$. The non-explicit construction of insdel codes is based on constant-weight$L^{1}$-codes that are introduced in this paper. We first establish a relation between constant-weight$L^{1}$-codes and insdel codes. Based on this relation, we construct constant-weight$L^{1}$-codes with reasonable parameters and subsequently give insdel codes approaching the insdel-metric Singleton bound. Via automorphism group of rational function field, we provide a necessary and sufficient condition under which a two-dimensional Reed-Solomon code of length$n$has insdel distance$2n-4$. Based on this criterion, we present a construction of$q$-ary two-dimensional Reed-Solomon codes of length$n$and insdel distance$2n-4$with$q=O(n^{5})$. Though this is worse than the current best field size, we provide a new angle to look into the problem.

Maximally recoverable local repairable codes (MR LRCs for short) have received great attention in the last few years. Various constructions have been proposed in literature. The main focus of this topic is to construct MR LRCs over small fields. An interesting parameter regime for an$(N=nr,r,h, \delta)$-MR LRC is the constant global parities$h=O(1)$. In this parameter setting, all previous constructions require the field size$\ell =\Omega _{h} (N^{h-1-o(1)})$. It remains challenging to improve this bound. In this paper, via subspace direct sum systems, we present a construction of MR LRC with the field size$\ell = O\left({N^{h-2+\frac {1}{h-1}-o(1)}}\right)$. In particular, for the interesting cases where$h=2,3$, we improve previous constructions by either reducing field size or removing constraints. In addition, we also offer some constructions of MR LRCs for larger global parity$h$. The main techniques used in this paper is through subspace direct sum systems that we introduce.

An improved CA-SCL (CRC-Aided Successive Cancellation List) decoding algorithm for Polar codes is proposed in this paper. By introducing the global cyclic redundancy check and local parity check, a lower bit error rate is obtained comparing with the known results. The new algorithm constructs a prune decoding path by the parity check in the local processing. Since the parity check can only detect an odd number of errors, the global CRC is used to increase the error detection ability and the decoding accuracy. The performance of the improved decoding algorithm is better than the known results, especially when the code length is either less than or equal to 512, and the code rate is not greater than 0.5 in case of the signal-to-noise ratio (SNR) higher than 3dB. In particular, when the code length is 256 with code rate of 0.5 and decoding list size of 32 under the condition of bit error rate 10-5on the AWGN channel, the proposed algorithm has around 0.25dB and 0.55dB performance gain comparing with that of the CA-SCL and SCL algorithms, respectively.

Insertion and deletion (insdel for short) errors are synchronization errors in communication systems caused by the loss of positional information in the message. Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability in the classical setting. This interest also translates to the insdel metric setting, as the Guruswami-Sudan decoding algorithm can be utilized to provide a deletion correcting algorithm in the insdel metric. Nevertheless, there have been few studies on the insdel error-correcting capability of Reed-Solomon codes. Our main contributions in this article are explicit constructions of two families of 2-dimensional Reed-Solomon codes with insdel error-correcting capabilities asymptotically reaching those provided by the Singleton bound. The first construction gives a family of Reed-Solomon codes with insdel error-correcting capability asymptotic to its length. The second construction provides a family of Reed-Solomon codes with an exact insdel error-correcting capability up to its length. Both our constructions improve the previously known construction of 2-dimensional Reed-Solomon codes whose insdel error-correcting capability is only logarithmic on the code length.

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes.

We investigate the list decodability of symbol-pair codes1in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert-Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert-Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed-Solomon codes beyond the Johnson-type bound in the pair metric.1A symbol-pair code is referred to a code in the pair metric.

Wachter-Zeh showed that every cover metric code can be list decoded up to the Johnson-like bound. Furthermore, it was shown that the efficient list decoding of cover metric codes up to the Johnson-like bound can be performed. From the work of Wachter-Zeh, one natural question is whether the Johnson-like bound can be improved. In this paper, we give a confirmative answer to this question by showing that the cover metric codes can be list decoded up to the Singleton bound. Our contributions consist of three parts. First, we prove that the list decodability of cover metric codes does not exceed the Singleton bound. Second, we show that, with high probability, a random cover metric code can be list decoded up to the Singleton bound, which is better than the Johnson-like bound. Third, by applying the existing decoding algorithms for Hamming metric and rank metric codes, we present explicit constructions of cover metric codes that can be efficiently list decoded up to the Singleton bound.

Efficient list decoding of rank-metric codes seems more difficult compared with classical block codes although list decodability of random rank-metric codes is completely determined by Ding. For example, it was shown by Raviv and Wachter-Zeh that the list decoding radius of Gabidulin codes is the same as the unique decoding radius, i.e., half the minimum distance for some instances of parameters. On the other hand, Guruswami and Xing give an explicit construction of subcodes of Gabidulin codes, which can be list decoded up to the Singleton bound. This implies that subcodes of Gabidulin codes are good candidates for list decoding. In this paper, we confirm that, with overwhelming probability, a random subcode of a Gabidulin code can be list decoded with decoding radius far beyond half of the minimum distance.