This paper proposes two low-complexity Chase (LCC) decoding algorithms for elliptic codes, which are realized by K¨otter’s interpolation and the basis reduction (BR) interpolation, respectively. They are both developed from the perspective of computing the Gr¨obner bases of the interpolation modules. By identifying η unreliable symbols, 2η decoding testvectors are formulated and the corresponding interpolation modules can be defined. The re-encoding transform (ReT) is further introduced to facilitate the interpolation. The LCC-K ¨otter decoding performs interpolation for the common elements, producing an intermediate outcome shared by all test-vectors. The desired Gr¨obner basis w.r.t. each test-vector can be obtained in a binary tree growing fashion. The new interpolation process can start from intermediate nodes of the previously interpolated paths, resulting in a low complexity. But the decoding latency cannot be contained. In contrast, the LCC-BR decoding performs the common computation in basis construction, which partly substantiates the bases for all interpolation modules. The subsequent basis construction and reduction can be performed in parallel. Besides a low complexity, it offers a latency advantage over the LCC-K¨otter decoding. The decoding complexity and latency are analyzed and verified numerically. The LCC decoding performance are also presented, demonstrating their advantage over both the Guruswami-Sudan decoding and the algebraic soft decoding. Moreover, the performance advantage of elliptic codes over the Reed-Solomon (RS) codes is demonstrated.

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.

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.

Due to the increasing size of datasets and complexity of models, distributed machine learning is becoming increasingly important. Among the various components of distributed machine learning frameworks, the all-reduce operation holds significant importance, particularly in terms of communication costs among computing nodes. The all-reduce operation distributes to all nodes one or more reductions of data symbols from all nodes. This operation is used in distributed machine learning for aggregating data from computing nodes during the training and synchronizing the results among all computing nodes. This paper considers a distributed system consisting of computing nodes which are connected with each other via one-hop links. The data symbols are encoded and stored in the computing nodes. This paper focuses on the so-called all-linear-reduce operation which distributes to all nodes one or more linear combinations of data symbols from all nodes. This paper aims to determine the optimal bandwidth for the linear all-reduce operation, for an arbitrarily given distributed system. We propose a universal all-linear-reduce operation, which has been proven to achieve the optimal bandwidth in some cases.

In this paper, we present fast encoding algorithms for Hermitian codes based on the Lin-Chung-Han fast Fourier transform (LCH-FFT). For non-systematic encoding, we extend the LCH basis to the bivariate polynomial space and develop a two-dimensional FFT algorithm. For systematic encoding, we propose a modified partial FFT algorithm and present a procedure for computing the unknown intermediates. For a Hermitian code of length $n$, the computational complexity of the presented non-systematic and systematic encoding algorithms are both $O(n{\text{log}}n)$, improving upon the currently best-known encoding complexity $O\left( {n{\text{lo}}{{\text{g}}^2}n{\text{loglog}}n} \right)$.

This paper proposes the re-encoding transformed (ReT) based list decoding using the module basis reduction (BR) interpolation for algebraic geometric (AG) codes on Cabcurves. The two ReT approaches are introduced to facilitate the BR interpolation. One is realized by the bivariate Lagrange polynomial. The other is conducted by the ReT of Reed-Solomon (RS) codes based on the mathematical structure of AG codes. The ReT based BR interpolation (ReT-BR) algorithm for decoding the AG codes is further introduced. Finally, complexity of the proposed algorithm is analyzed and validated by the simulation results, demonstrating its complexity advantage over the non-ReT counterpart.

CRISPR/Cas9 is a widely used genome editing tool for site-directed modification of deoxyribonucleic acid (DNA) nucleotide sequences. However, how to accurately predict and evaluate the on- and off-target effects of single guide RNA (sgRNA) is one of the key problems for CRISPR/Cas9 system. Using computational methods to obtain high cell-specific sensitivity and specificity is a prerequisite for the optimal design of sgRNAs. Inspired by the work of predecessors, we found that sgRNA on-target knockout efficacy was not only related to the original sequence but also affected by important biological features. Hence, we introduce a novel approach called TransCrispr, which integrates Transformer and convolutional neural network (CNN) architecture to predict sgRNA knockout efficacy. Firstly, we encode the sequence data and send the transformed sgRNA sequence, positional information, and biological features into the network as input. Then, the convolutional neural network will automatically learn an appropriate feature representation for the sgRNA sequence and combine it with the positional information for self-attention learning of the Transformer. Finally, a regression score is generated by predicting biological features. Experiments on seven public datasets illustrate that TransCrispr outperforms state-of-the-art methods in terms of prediction accuracy and generalization ability.

This paper proposes two interpolation-based algebraic Chase decoding for elliptic codes. It is introduced from the perspective of computing the Gröbner basis of the interpolation module, for which two Chase interpolation approaches are utilized. They are Kötter’s interpolation and the basis reduction (BR) interpolation. By identifying η unreliable symbols, 2ηdecoding test-vectors are formulated, and the corresponding interpolation modules can be defined. The re-encoding further helps transform the test-vectors, facilitating the two interpolation techniques. In particular, Kötter’s interpolation is performed for the common elements of the test-vectors, producing an intermediate outcome that is shared by the decoding of all test-vectors. The desired Gröbner bases w.r.t. all test-vectors can be obtained in a binary tree growing fashion, leading to a low complexity but its decoding latency cannot be contained. In contrast, the BR interpolation first performs the common computation in basis construction which is shared by all interpolation modules, and then conducts the module basis construction and reduction for all test-vectors in parallel. It results in a significantly lower decoding latency. Finally, simulation results are also presented to demonstrate the effectiveness of the proposed Chase decoding.

This paper proposes the algebraic soft decoding (ASD) for one-point elliptic codes, where the interpolation problem is solved from the perspective of module basis reduction. In ASD, the interpolation polynomial$\mathcal {Q}(x, y, z)$is the minimum candidate of a Gröbner basis. Based on a multiplicity matrix, an interpolation ideal can be defined. With the decoding output list size, an equivalent interpolation module can be led to. By further defining the set of interpolation points, a sequence of modules from the elliptic curve coordinate ring can be obtained. Based on the Lagrange interpolation functions over elliptic function field, a basis of the interpolation module can be constructed. The desired Gröbner basis that contains$\mathcal {Q}$can be determined by reducing the module basis. Re-encoding transform (ReT) is further introduced to reduce the basis reduction complexity. It is also shown that the interpolation can be facilitated by assessing the degree of the Lagrange interpolation polynomials. The decoding complexity is analyzed, which is verified by numerical results. That shows the advantage of this interpolation technique over the conventional Kötter’s interpolation. The ASD performance of elliptic codes is also presented.

This paper proposes algebraic soft decoding (ASD) for one-point elliptic codes, where the interpolation is realized through the perspective of obtaining a Gröbner basis. The desired interpolation polynomial$\mathcal{Q}(x, y, z)$is the minimum candidate in the basis. This work shows how to obtain such a Gröbner basis. Based on an interpolation multiplicity matrix M, an interpolation ideal$\mathcal{I}_{\mathrm{M}}$can be defined. With a predefined decoding output list size (OLS)$l\ (l\geq\deg_{z}\mathcal{Q})$, an equivalent interpolation module$\mathcal{I}_{\mathrm{M}, l}$can be led to. By further defining the Lagrange interpolation functions, a basis of the interpolation module can be constructed. The desired Gröbner basis can be obtained by reducing this module basis. Finally, the decoding complexity is also analyzed.

This paper proposes the Guruswami-Sudan (GS) list decoding algorithm for one-point elliptic codes, in which the interpolation is realized by the module basis reduction (BR). Elliptic codes are a kind of algebraic-geometric (AG) codes with a genus of one. Over the same finite field, they have a greater codeword length than Reed-Solomon (RS) codes, capable of correcting more errors. The GS decoding consists of interpolation and root-finding, while the former that determines the interpolation polynomial$\mathcal {Q}(\text {x}, \text {y}, \text {z})$dominates the decoding complexity. By defining the Lagrange interpolation function over an elliptic function field, a basis of the interpolation module can be constructed. The desired Gröbner basis that contains$\mathcal {Q}(\text {x}, \text {y}, \text {z})$can be determined by reducing the constructed basis. This is namely the BR interpolation and it requires less finite field arithmetic operations than the conventional Kötter’s interpolation, facilitating the GS decoding. Re-encoding transform (ReT) is further introduced to facilitate the BR interpolation. This work also shows that both the BR interpolation and its ReT variant will have a lower complexity as the code rate${k}/{n}$increases, where n and${k}$are the length and dimension of the code, respectively. Our numerical results demonstrate the complexity advantage of the BR interpolation over Kötter’s interpolation, and the performance advantage of elliptic codes over RS codes.

Advancing from Reed-Solomon (RS) codes, the length of algebraic-geometric (AG) codes can exceed the size of finite field, resulting in a greater error-correction capability. However, this is realized with a genus penalty. Usually, they are not maximum distance separable (MDS) codes. One-point elliptic codes are either MDS or almost MDS, yielding a good tradeoff between codeword length and distance property. This paper proposes the Guruswami-Sudan (GS) list decoding algorithm for elliptic codes. To define the interpolated polynomial Q(x, y, z), an explicit construction for the zero basis of each affine point is introduced. Given an interpolation multiplicity m, the error-correction capability τmand the maximum decoding output cardinality lmof the GS algorithm are characterized. An efficient interpolation algorithm is further presented for elliptic codes. Performance of elliptic codes is shown for the first time, demonstrating their advantage over RS codes.