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.

Minimum storage regenerating (MSR) codes are extensively studied in the literature to reduce the network bandwidth consumed during node repair. In this paper, we focus on repairing multiple node failures and construct binary cooperative MSR codes with optimal access bandwidth. Specifically, we present explicit constructions of the codes by designing the parity-check matrices over a special polynomial ring ${\mathcal{R}} = {{\mathbb{F}}_2}[x]/\left({1 + x + \cdots + {x^{p - 1}}}\right)$ where p is a prime. The obtained codes with length n and dimension k achieve the lower bound on repair bandwidth under cooperative repair model with optimal access property for any 2 ≤ h ≤ r and k+1 ≤ d ≤ n – h where h and d are the number of failure nodes and helper nodes, respectively. Moreover, the computation operations involved in encoding, decoding and nodes repair are only exclusive ORs and cyclic shifts, resulting in less CPU overhead compared with the complex multiplication operations over finite fields.

In this paper, we provide non-asymptotic upper bounds on the size and average size of s-insertion s-deletion balls. As a corollary, we conclude an explicit non-asymptotic lower bound on the size of optimal s-insertionldeletion correcting code which is a strict improvement of Levenshtein's lower bound given in 2002. Particularly, in the case of single insertionldeletion, comparing with Levenshtein's bound, we reduce the gap to the maximum potential lower bound by at least 1/3.

In distributed storage, cooperative repair is to simultaneously recoverh(h> 1) node erasures by downloading data from surviving nodes as well as collaboration between thehreplacement nodes. In this work, we propose a generalized cooperative repair framework for Reed-Solomon (RS) codes with two erasures. The key idea is to construct parity-check polynomials for the two replacement nodes respectively and then reduce the repair problem to the design of a linearized permutation polynomial related to the parity-check polynomials. We provide constructions of the linearized permutation polynomial in several cases, leading to cooperative repair schemes accordingly. Compared with the schemes given by Dauet al. 2021, our schemes retain the same repair bandwidth while apply to a much wider parameter regime and need only one-round collaboration. Finally we further reduce the repair bandwidth by the lifting method for RS codes of short length.

In this paper, due to the important value in practical applications, we consider the coded distributed matrix multiplication problem of computing$AA^{\top} $in a distributed computing system with$N$worker nodes and a master node, where the input matrices$A$and$A^{\top} $are partitioned into$m$-by-$p$and$p$-by-$m$blocks of equal-size sub-matrices respectively. For effective straggler mitigation, we propose a novel computation strategy, named folded polynomial code, which is obtained by modifying the entangled polynomial codes. Moreover, we characterize a lower bound on the optimal recovery threshold among all linear computation strategies when the underlying field is the real number field, and our folded polynomial codes can achieve this bound in the case of$m=1$. Compared with all known computation strategies for coded distributed matrix multiplication, our folded polynomial codes outperform them in terms of recovery threshold, download cost, and decoding complexity.

An (n, k, d) cooperative regenerating code provides the optimal-bandwidth repair for any t (t > 1) node failures in a cooperative way. In particular, an MSCR (minimum storage cooperative regenerating) code retains the same storage overhead as an (n, k) MDS code. Suppose each node stores α symbols which indicates the sub-packetization level of the code. A scalar MSCR code attains the minimum sub-packetization, i.e., α = d - k + t. By now, all existing constructions of scalar MSCR codes restrict to very special parameters, eg. d = k or k = 2, etc. In a recent work, Ye and Barg construct MSCR codes for all n, k, d, t, however, their construction needs α ≈ exp(nt) which is almost infeasible in practice. In this paper, we give an explicit construction of scalar MSCR codes for all d ≥ max{2k-1-t, k}, which covers all possible parameters except the case of k ≤ d ≤ 2k - 2 - t when k <; 2k - 1 - t. Moreover, as a complementary result, for k <; d <; 2k - 2 - t we prove the nonexistence of linear scalar MSCR codes that have invariant repair spaces. Our construction and most of the previous scalar MSCR codes all have invariant repair spaces and this property is appealing in practice because of convenient repair. In this sense, this work presents an almost full description of usual scalar MSCR codes.

Suppose a database containing M records is replicated in each of N servers, and a user wants to privately retrieve one record by accessing the servers such that identity of the retrieved record is secret against any up to T servers. A scheme designed for this purpose is called a T -private information retrieval (T -PIR) scheme.In this paper we focus on the field size of T -PIR schemes. We design a general capacity-achieving T -PIR scheme whose queries are generated by using some MDS array codes. It only requires field size q≥ℓ√N, where ℓ = min {tM-2, (n - t)M-2}, t = T/gcd(N, T), n = N/gcd(N, T) and has the optimal sub-packetization NnM-2. Comparing with existing capacity-achieving T -PIR schemes, our scheme has the following advantage, that is, its field size monotonically decreases as the number of records M grows. In particular, the binary field is sufficient for building a capacity-achieving T-PIR scheme as long as M ≥ 2 + ⌈logμlog2N⌉, where μ = min{t, n - t} > 1.