Search

The problem of private information retrieval with graph-based replicated storage was recently introduced by Raviv, Tamo and Yaakobi. Its capacity remains open in almost all cases. In this work the asymptotic (large number of messages) capacity of this problem is studied along with its generalizations to include arbitrary T-privacy and X-security constraints, where the privacy of the user must be protected against any set of up to T colluding servers and the security of the stored data must be protected against any set of up to X colluding servers. A general achievable scheme for arbitrary storage patterns is presented that achieves the rate (ρ -X-T)/N, where N is the total number of servers, and each message is replicated at leastρ times. Notably, the scheme makes use of a special structure inspired by dual Generalized Reed Solomon (GRS) codes. A general converse is also presented. The two bounds are shown to match for many settings, including symmetric storage patterns. Finally, the asymptotic capacity is fully characterized for the case without security constraints (X=0) for arbitrary storage patterns provided that each message is replicated no more than T+2 times. As an example of this result, consider PIR with arbitrary graph based storage (T=1, X=0) where every message is replicated at exactly 3 servers. For this 3-replicated storage setting, the asymptotic capacity is equal to 2/ν 2(G) where ν 2(G) is the maximum size of a 2-matching in a storage graph G[V,E]. In this undirected graph, the vertices V correspond to the set of servers, and there is an edge uv\in E between vertices u,v only if a subset of messages is replicated at both servers u and v.

The revolution in the field of information processing systems has created a huge demand for reliable and enhanced data storage capabilities. This demand is being met by advances in channel coding algorithms along with upward scaling of the capacities of hardware devices. NAND Flash memory is a type of non-volatile memory. Scaling of the size of flash memories from Single Level Cell (SLC) devices to Multilevel cell (MLC) devices has increased the storage capacity. However, these multi-bit per cell architectures are characterized by significantly higher Raw Bit Error Rate (RBER) values when compared with SLC architectures. The requirement of low Undetected Bit Error Rate (UBER) values has motivated us to synthesize powerful channel codes for enhancing the integrity of information Storage in multi-level NAND Flash Memory devices. This paper describes the synthesis of novel Subfield Subcodes of Reed Solomon Codes (SSRS) and Reed-Solomon (RS) codes which are matched to multi-bit per cell architectures. UBER values have been calculated for each of the synthesized codes described in this paper. This allows the determination of the performance and the improvement in data storage integrity brought by using these codes. We have shown that the synthesized SSRS and RS codes can provide very low UBER even when the corresponding RBER values are appreciable. As RS codes permit the detection and correction of a greater number of errors for a given code length, their performance is superior to that of SSRS codes. This improved performance is obtained at the cost of greater complexity of encoding and decoding processes.

A new Chase-type soft-decision decoding algorithm for Reed-Solomon codes is proposed, referred to as tree-based Chase-type algorithm. The proposed tree-based Chase-type algorithm takes the set of all vectors as the set of testing patterns, and hence definitely delivers the most-likely codeword provided that the computational resources are allowed. All the testing patterns are arranged in an ordered rooted tree according to the likelihood bounds of the possibly generated codewords, which is an extension of Wu and Pados’ method from binary into q-ary linear block codes. While performing the algorithm, the ordered rooted tree is constructed progressively by adding at most two leafs at each trial. The ordered tree naturally induces a sufficient condition for the most-likely codeword. That is, whenever the tree-based Chase-type algorithm exits before a preset maximum number of trials is reached, the output codeword must be the most-likely one. But, in fact, the algorithm can be terminated by setting a discrepancy threshold instead of a maximum number of trials. When the tree-based Chase-type algorithm is combined with Guruswami-Sudan (GS) algorithm, each trial can be implement in an extremely simple way by removing from the gradually updated Gröbner basis one old point and interpolating one new point. Simulation results show that the tree-based Chase-type algorithm performs better than the recently proposed Chase-type algorithm by Bellorado et al. with less trials (on average) given that the maximum number of trials is the same.

The structural parameters, electronic, optical, and elastic properties of Niobium Carbide (NbC) compound within four different structures: rock-salt (RS), wurtzite (WZ), cesium chloride (CsCl), and Nickel Arsenide (NiAs) are examined using the Full-Potential Linearized-Augmented Plane Wave (FP-LAPW). The exchange–correlation potential (VXC) has been treated by Perdew, Burke, and Ernzerhof's generalized gradient approximation (PBE-GGA) when structural properties, transition pressure, and elastic properties are estimated. For electronic properties, in addition to (PBE-GGA), the modified Becke–Johnson (mBJ-GGA) was used for increased accuracy. Present results show that the RS of NbC is the most stable among the four examined structures with the lowest equilibrium energy. The calculated lattice constants are in good agreement with the former calculations. The elasticity and the formation energy calculations show that NbC is stable within the four studied structures. The electronic band structure calculations of NbC show that it has a metallic nature in the four considered structures. [ABSTRACT FROM AUTHOR]

We show new and improved list decoding properties of folded Reed--Solomon (RS) codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the source of recent advances in coding theory: folded RS codes were the first known explicit construction of capacity-achieving list decodable codes [V. Guruswami and A. Rudra, IEEE Trans. Inform. Theory, 54 (2008), pp. 135--150], and multiplicity codes were the first construction of high-rate locally decodable codes [S. Kopparty, S. Saraf, and S. Yekhanin, J. ACM, 61 (2014), 28]. In this work, we show that folded RS codes and multiplicity codes are in fact better than previously known in the context of list decoding and local list decoding. Our first main result shows that folded RS codes achieve list decoding capacity with constant list sizes, independent of the block length. Prior work with constant list sizes first obtained list sizes that are polynomial in the block length and relied on pre-encoding with subspace evasive sets to reduce the list sizes to a constant [V. Guruswami and C. Wang, IEEE Trans. Inform. Theory, 59 (2013), pp. 3257--3268], [Z. Dvir and S. Lovett, Proc. 44th STOC, ACM, 2012, 351--358]. The list size we obtain is (1/\varepsilon)O(1/\varepsilon) where \varepsilon is the gap to capacity, which matches the list size obtained by pre-encoding with subspace evasive sets. For our second main result, we observe that univariate multiplicity codes exhibit similar behavior, and we use this, together with additional ideas, to show that multivariate multiplicity codes are locally list decodable up to their minimum distance. By known reductions, this gives, in turn, capacity-achieving locally list decodable codes with query complexity exp(\~ O((logN)5/6)). This improves on the tensor-based construction of [B. Hemenway, N. Ron-Zewi, and M. Wootters, SIAM J. Comput., 49 (2019), pp. 157--195], which gave capacity-achieving locally list decodable codes of query complexity N \~ O(1/\mathrm{l}\mathrm{o}\mathrm{g} \mathrm{l}\mathrm{o}\mathrm{g}N), and is close to the best known query complexity of exp(\~ O(\surd logN)) for high-rate locally (uniquely) decodable codes [S. Kopparty et al., J. ACM, 64 (2017), 11]. [ABSTRACT FROM AUTHOR]

In this paper we take a combinatorial approach to the problem of list-decoding, which allows us to determine the precise relation (up to the exact constant) between the decoding radius, list size, and code rate. We prove a generalized Singleton bound for a given list size, and conjecture that the bound is tight for most Reed--Solomon (RS) codes over large enough finite fields. We also show that the conjecture holds true for list sizes 2 and 3, and as a by product show that most RS codes with a rate of at least 1/9 are list-decodable beyond the Johnson radius. Last, we give the first explicit construction in the literature of such RS codes. The main tools used in the proof are a new type of linear dependency between codewords of a code that are contained in a small Hamming ball, and a surprising connection between list-decoding and the notion of cycle space in graph theory. Both of them are new, and may be of independent interest. [ABSTRACT FROM AUTHOR]

In this paper, we focus on extensions of methods for interpolating rational functions from their evaluations, in the context of erroneous evaluations. This problem can be seen both from a computer algebra and a coding theory point of view. In computer algebra, this is a generalization of Simultaneous Rational Function Reconstruction with errors and multiprecision evaluations. From an error correcting codes point of view, this problem is related to the decoding of some algebraic codes such as Reed-Solomon, Derivatives or Multiplicity codes. We give conditions on the inputs of the problem which guarantee the uniqueness of the interpolant. Since we deal with rational functions, some evaluation points may be poles: a first contribution of this work is to correct any error in a scenario with poles and multiplicities that extends (Kaltofen et al., 2020). Our second contribution is to adapt rational function reconstruction for random errors , and provide better conditions for uniqueness using interleaving techniques as in (Guerrini et al., 2021). [ABSTRACT FROM AUTHOR]

Barren lands are being transformed into agricultural fields with the growing demand for agriculture-based products. Hence, monitoring these regions for better planning and management is crucial. Surveying with high-resolution RS (remote sensing) satellites like Worldview-2 provides a faster and cheaper solution than conventional surveys. In the study, the arid region comprising cropland and barrenlands are efficiently and autonomously delineated using its spectral and textural properties using state-of-the-art random forest (RF) ensemble classifiers. The textural information window size is optimized and at a GLCM (gray-level co-occurrence matrix) window size of 13, a stable trend in classification accuracy was observed. A further rise in window sizes did not improve the classification accuracy; beyond GLCM 19, a decline in accuracy was observed. Comparing GLCM-13 RF with the no-GLCM RF classifier, the GLCM-based classifiers performed better; thus, the textural information assisted in removing isolated crop-classified outputs that are falsely predicted pixel groups. Still, it also obscured information about barren lands present within croplands. Delineation accuracy was 93.8 % for the no-GLCM RF classifier, whereas, for the GLCM-13 RF classifier, an accuracy of 97.3 % was observed. Thus, overall, a 3.5 % improvement in accuracy was observed while using the GLCM RF classifier with window size 13. The textural information with proper calibration over high-spatial resolution datasets improves crop delineation in the present study. Henceforth, a more accurate cropland identification will provide a better estimate of the actual cropland area in such an arid region, which will assist in formulating a better resource management policy. [ABSTRACT FROM AUTHOR]

We prove that the cyclic and constacyclic codes constructed by Grassl and Rötteler in International Symposium on Information Theory (ISIT), pp. 1104–1108 (2015) are generalised Reed–Solomon codes. This note can be considered as an addendum to Grassl and Rötteler International Symposium on Information Theory (ISIT), pp 1104–1108 (2015). It can also be considered as an appendix to Ball and Vilar IEEE Trans Inform Theory 68:3796–3805, (2022) where Conjecture 11 of International Symposium on Information Theory (ISIT), pp 1104–1108 (2015), which was stated for Grassl–Rötteler codes, is proven for generalised Reed–Solomon codes. The content of this note, together with IEEE Trans Inform Theory 68:3796–3805, (2022) therefore implies that Conjecture 11 from International Symposium on Information Theory (ISIT), pp. 1104–1108 (2015) is true. [ABSTRACT FROM AUTHOR]

With the development of various information and communication technologies, the amount of big data has increased, and distributed file systems have emerged to store them stably. The replication technique divides the original data into blocks and writes them on multiple servers for redundancy and fault tolerance. However, there is a symmetrical space efficiency problem that arises from the need to store blocks larger than the original data. When storing data, the Erasure Coding (EC) technique generates parity blocks through encoding calculations and writes them separately on each server for fault tolerance and data recovery purposes. Even if a specific server fails, original data can still be recovered through decoding calculations using the parity blocks stored on the remaining servers. However, matrices generated during encoding and decoding are redundantly generated during data writing and recovery, which leads to unnecessary overhead in distributed file systems. This paper proposes a cache-based matrix technique that uploads the matrices generated during encoding and decoding to cache memory and reuses them, rather than generating new matrices each time encoding or decoding occurs. The design of the cache memory applies the Weighting Size and Cost Replacement Policy (WSCRP) algorithm to efficiently upload and reuse matrices to cache memory using parameters known as weights and costs. Furthermore, the cache memory table can be managed efficiently because the weight–cost model sorts and updates matrices using specific parameters, which reduces replacement cost. The experiment utilized the Hadoop Distributed File System (HDFS) as the distributed file system, and the EC volume was composed of Reed–Solomon code with parameters (6, 3). As a result of the experiment, it was possible to reduce the write, read, and recovery times associated with encoding and decoding. In particular, for up to three node failures, systems using WSCRP were able to reduce recovery time by about 30 s compared to regular HDFS systems. [ABSTRACT FROM AUTHOR]

To handle the complexity of the atmospheric boundary layer (ABL) and make accurate feature detection (top height, low‐level jets, inversions, etc.), a prior necessary step is to identify the type of boundary layer. This study proposes a new method to identify the boundary layer type through unsupervised classification and the synergistic use of ground‐based remote sensing. Unsupervised classification is used to lighten the human supervision. The new classification was applied to a 1‐day case study collected during wintertime in the Arve River valley near Chamonix–Mont‐Blanc during the Passy‐2015 field experiment. The ABL classification obtained from microwave radiometer and ceilometer observations (ground‐based remote sensors [GBReS]) combination is compared with high‐frequency radiosoundings (RS) data and the French convective scale AROME model outputs. Classifications from RS and GBReS broadly agree, demonstrating the good behavior of the method, AROME leading to different results at night. The difference of AROME is likely due to the different nature of the data (model fields are smoother and include forecasting errors). The results show the ability of unsupervised classification to segment relevant objects in the boundary layer and the benefit to use a combination of GBReS. [ABSTRACT FROM AUTHOR]

The hull of a linear code is the intersection of itself with its dual code with respect to certain inner product. Both Euclidean and Hermitian hulls are of theorical and practical significance. In this paper, we construct several new classes of maximum distance separable (MDS) codes via (extended) generalized Reed-Solomon (GRS) codes and determine their Euclidean or Hermitian hulls. As a consequence, four new classes of MDS codes with Hermitian hulls of flexible dimensions and six new classes of MDS codes with Euclidean hulls of flexible dimensions are constructed. As applications, for the former, we further construct four new families of entanglement-assisted quantum error-correcting codes (EAQECCs) and four new families of MDS EAQECCs of length n > q + 1 . Meanwhile, many of the distance parameters of our MDS EAQECCs are greater than ⌈ q 2 ⌉ or q; for the latter, we show some examples on Euclidean self-orthogonal and one-dimensional Euclidean hull MDS codes. In addition, two new general methods for constructing extended GRS codes with (k - 1) -dimensional Hermitian hull and Hermitian self-orthogonal extended GRS codes are also provided. [ABSTRACT FROM AUTHOR]

Summary: VHF data exchange system (VDES) is an emerging maritime communications standard that is meant to provide ship‐to‐shore, shore‐to‐ship, and ship‐to‐ship information services. VDES also includes a satellite component to extend the service coverage also to the high sea. Ships can receive important information via VDES and access this service via satellite when they are far from the shore. This paper uses data taken during a measurement campaign to develop an ON‐OFF model for the VDE‐SAT downlink channel taking the multipath effects caused by sea reflections into account. This model has been used to evaluate the impact of packet‐level forward error correction (FEC) schemes (i.e., ideal codes, RaptorQ codes, and 2‐Dimension Reed‐Solomon codes) to further protect transmissions from deep fading events and to evaluate the impact at the transport level considering the possibility to adopt the transmission control protocol (TCP) for a file map delivery service. [ABSTRACT FROM AUTHOR]

We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an oracle function f : L m → F q , where L ⊂ F q , a verifier distinguishes whether f is the evaluation of a low-degree polynomial or is far (in relative Hamming distance) from being one, by making only a few queries to f. This topic has been studied in the context of locally testable codes, interactive proofs, probalistically checkable proofs, and interactive oracle proofs. We present the first interactive oracle proofs of proximity (IOPP) for tensor products of Reed–Solomon codes (evaluation of polynomials with bounds on individual degrees) and for Reed–Muller codes (evaluation of polynomials with a bound on the total degree) that simultaneously achieve logarithmic query complexity, logarithmic verification time, linear oracle proof length and linear prover running time. Such low-degree polynomials play a central role in constructions of probabilistic proof systems and succinct non-interactive arguments of knowledge with zero-knowledge. For these applications, highly-efficient multivariate low-degree tests are desired, but prior probabilistic proofs of proximity required super-linear proving time. In contrast, for multivariate codes of length N, our constructions admit a prover running in time linear in N and a verifier which is logarithmic in N. Our constructions are directly inspired by the IOPP for Reed–Solomon codes of [Ben-Sasson et al., ICALP 2018] named "FRI protocol". Compared to the FRI protocol, our IOPP for tensor products of Reed–Solomon codes achieves the same efficiency parameters. As for Reed–Muller codes, for fixed constant number of variables m, the concrete efficiency of our IOPP for Reed–Muller codes compares well, all things equal. [ABSTRACT FROM AUTHOR]

The reversible extended secret image sharing (RESIS) scheme can safely segment the secret image into a shadow image and embed it into the cover image, while ensuring that both the secret image and the cover image are completely restored. The existing schemes do not consider the attack on the information transmission channel, and often cannot correctly recover the secret image when attacked. In view of this, this paper fully considers the active attack on the information channel, and then proposes a RESIS scheme with error correction capability. In this paper, the Reed-Solomon code is used to detect modification attacks and correct errors to a certain extent. Additionally, the lossless recovery effect of both the secret image and the cover image is accomplished in conjunction with secret sharing scheme based on the Chinese remainder theorem. According to experimental findings, this method can resist certain active attacks.

Entanglement-assisted quantum-error-correcting (EAQEC) codes are quantum codes which use entanglement as a resource. These codes can provide better error correction than the (entanglement unassisted) codes derived from the traditional stabilizer formalism. In this paper, we provide a general method to construct EAQEC codes from cyclic codes. Afterwards, the method is applied to Reed–Solomon codes, BCH codes, and general cyclic codes. We use the Euclidean and Hermitian construction of EAQEC codes. Three families have been created: two families of EAQEC codes are maximal distance separable (MDS), and one is almost MDS or almost near MDS. The comparison of the codes in this paper is mostly based on the quantum Singleton bound. [ABSTRACT FROM AUTHOR]

We give a description of the duals of linearized Reed–Solomon codes in terms of codes obtained by taking residues of Ore rational functions. Our construction shows in particular that, under some assumptions on the base field, the class of linearized Reed–Solomon codes is stable under duality. As a byproduct of our work, we develop a theory of residues in the Ore setting, extending the results of [7]. [ABSTRACT FROM AUTHOR]

The paper deals with applying the gradually growing fracture technique to study inhomogeneous high-gradient residual stress (RS) fields developing in areas of structural inhomogeneity of flat parts (specifically, in welded joints). The method of electronic speckle interferometry (ESI) is used to register the strain response in the form of surface field displacement of the object studied caused by generated and steadily growing incised fracture. It allows registering displacements directly without contact in digital form with high accuracy. The schematic diagrams of a specialized interferometer are described. The features are listed for recording displacement fields caused by the stepwise increase in the fracture length. The use of a return mechanism made it possible to take the test object out of the optical scheme and bring it back to the initial position as soon as the required mechanical operations are completed. A new method is outlined to determine the stress intensity factor (SIF) in fractures operating as RS indicators on the basis of mathematical processing of the tangential displacement fields. The potential of the interactive program operating in the semiautomated mode (in the MATLAB environment) to implement this approach is explained. The accuracy of the RS calculation procedure is estimated on the basis of the mathematical processing of the experimentally obtained RS indicator, i.e., the dependence of SIF on the fracture length. An example is given to apply techniques developed, equipment, and programs to study RS distribution in highly crack-resistant sheets made of 1163T aircraft alloy using the stir welding technique. [ABSTRACT FROM AUTHOR]

For the identification of Reed‐Solomon (RS) codes, the existing methods need to test the possible codeword length and the primitive polynomials exhaustively. Exhaustive search leads to high computational complexity. To overcome this limitation and fulfill the requirement in practice, a fast blind identification method is proposed. Different with most methods, our identification method is discussed in Galois Field of 2. First, by using Gaussian elimination, the bit matrix is transformed to the simplest upper triangular form. If the assumed codeword length is right, the matrix is of deficient rank, and the parameters of an RS code can be estimated according to the rank. The null space of the matrix, defined as the equivalent binary parity check matrix, can also be obtained from the simplification result. Then, a candidate set of primitive polynomials is constructed according to the estimated codeword length. By using the matrix null space, the correctness of a candidate primitive polynomial is tested through matrix analysis. Finally, by combining the estimated parameters, the generator polynomial of an RS code is identified. To decrease the bit errors in the matrix, soft‐decision data is used to select reliable bits. Experimental results show the effectiveness and robustness of our method. [ABSTRACT FROM AUTHOR]

The construction of quantum maximum distance separable (MDS for short) codes is one of the hot issues in quantum information theory. As far as we know, researchers have done a lot of constructive work in the construction of quantum MDS codes. However, the known results do not cover all parameters. In this paper, we propose an efficient construction implemented by concatenating two existing quantum MDS codes. Compared to a previous work (Fang and Luo in Quantum Inf Process 19(1):16, 2020), we relax the restrictions of the construction and propose some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

Erasure codes offer a storage-efficient redundancy mechanism for maintaining data availability guarantees in storage clusters, yet also incur high network traffic consumption and recovery time in failure repair. Extensive research has been carried out to reduce the recovery time. However, previous works either target specific erasure code constructions which are not commonly used in today’s distributed storage clusters or neglect the heterogeneous bandwidth property in real network environments. Since erasure-coded clusters are typically composed of multi-node with heterogeneous bandwidth and accessed in parallel, the whole recovery time is mainly restricted by the low-bandwidth links. In this article, we propose SMFRepair, a single-node multi-level forwarding repair technique that is designed to improve the performance in heterogeneous networks based on Reed-Solomon codes for general fault tolerance. SMFRepair carefully selects the helper nodes and uses idle nodes to bypass low-bandwidth links. Idle nodes have sufficient and unused network bandwidth. It also pipelines the repair links that are optimized by idle nodes. Furthermore, a multi-node scheduling repair technique, called MSRepair, is proposed. MSRepair carefully schedules the multi-node repair link to saturate the most unoccupied bandwidth and transfers data from as large-bandwidth links as possible, with the primary objective of minimizing the recovery time. Large-scale simulation and Amazon EC2 real experiments show that compared to state-of-the-art repair techniques, SMFRepair can accelerate the single-node recovery by up to 47.69%, and MSRepair can reduce the multi-node recovery time by 33.78% $\sim$ ∼ 67.53%. [ABSTRACT FROM AUTHOR]

In this work, we consider the leakage-resilience of algebraic-geometric (AG for short) codes based ramp secret sharing schemes extending the analysis on the leakage-resilience of linear threshold secret sharing schemes over prime fields that is done by Benhamouda et al. in the effort to construct linear leakage-resilient secret sharing schemes with constant share size. Since there does not exist any explicit efficient construction of AG codes over prime fields with constant field size, we consider constructions over prime fields with the help of concatenation method and constructions of codes over field extensions. Extending the Fourier analysis done by Benhamouda et al., one can show that concatenated algebraic geometric codes over prime fields do produce some nice leakage-resilient secret sharing schemes. One natural and curious question is whether AG codes over extension fields produce better leakage-resilient secret sharing schemes than the construction based on concatenated AG codes. Such construction provides several advantage compared to the construction over prime fields using concatenation method. It is clear that AG codes over extension fields give secret sharing schemes with a smaller reconstruction threshold for a fixed privacy parameter $t$. In this work, it is also confirmed that indeed AG codes over extension fields have stronger leakage-resilience under some reasonable assumptions. Furthermore, we also show that AG codes over extension fields may provide strong multiplicative property which may be used in its application to the study of multiparty computation. In contrast, the same cannot be said for constructions based on concatenated AG codes, even when we are considering multiplication friendly embeddings. These advantages strongly motivate the study of secret sharing schemes from AG codes over extension fields. The current paper has two main contributions: (i) we obtain leakage-resilient secret sharing schemes with constant share sizes and unbounded numbers of players. Some of the schemes constructed without the use of concatenation also possesses strong multiplicative property (ii) via Fourier Analysis, we analyze the leakage-resilience of secret sharing schemes from codes over extension fields. This is of its own theoretical interest independent of its application to secret sharing schemes from algebraic geometric codes over extension fields. [ABSTRACT FROM AUTHOR]

An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters $[n,k,d]$ and the list size $L$. $L$ -MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed–Solomon (GRS) codes. [ABSTRACT FROM AUTHOR]

Twisted generalized Reed-Solomon (TGRS) codes are a family of codes that contains a large number of maximum distance separable (MDS) codes that are non-equivalent to generalized Reed-Solomon (GRS) codes. In this paper, we characterize a sufficient and necessary condition that a twisted Reed-Solomon (TRS) code with two twists is MDS; give a sufficient and necessary condition that a TGRS code with two twists is self-dual, and present some constructions of self-dual TGRS codes. These self-dual codes are MDS, NMDS or 2-MDS. Furthermore, we study the non-GRS properties of TGRS codes with two twists and prove that these codes are non-GRS in most cases. [ABSTRACT FROM AUTHOR]

A new Chase-type soft-decision decoding algorithm for Reed-Solomon codes is proposed, referred to as tree-based Chase-type algorithm. The proposed tree-based Chase-type algorithm takes the set of all vectors as the set of testing patterns, and hence definitely delivers the most-likely codeword provided that the computational resources are allowed. All the testing patterns are arranged in an ordered rooted tree according to the likelihood bounds of the possibly generated codewords, which is an extension of Wu and Pados' method from binary into q -ary linear block codes. While performing the algorithm, the ordered rooted tree is constructed progressively by adding at most two leafs at each trial. The ordered tree naturally induces a sufficient condition for the most-likely codeword. That is, whenever the tree-based Chase-type algorithm exits before a preset maximum number of trials is reached, the output codeword must be the most-likely one. But, in fact, the algorithm can be terminated by setting a discrepancy threshold instead of a maximum number of trials. When the tree-based Chase-type algorithm is combined with Guruswami-Sudan (GS) algorithm, each trial can be implement in an extremely simple way by removing from the gradually updated Gröbner basis one old point and interpolating one new point. Simulation results show that the tree-based Chase-type algorithm performs better than the recently proposed Chase-type algorithm by Bellorado et al. with less trials (on average) given that the maximum number of trials is the same. [ABSTRACT FROM AUTHOR]

This paper proposes a distributed Reed-Solomon coded cooperative labeling diversity (DRSCC-LD) scheme over the Rayleigh frequency-flat fast fading channel to further improve the BER performance. The non-binary Reed-Solomon (RS) code with more consecutive roots is applied at the relay to provide additional redundancy. As a novel diversity technique, labeling diversity (LD) with three different mappers is employed in the proposed DRSCC-LD scheme utilizing 16-QAM and 64-QAM, respectively, which may achieve diversity gain and greatly decrease the error floor (EF). Besides, a reduced-complexity detection algorithm based on a variable signal subset (RC-VSS) is proposed to lower the complexity of detection at both relay and destination. The proposed critical SNR-assisted (CSA) joint decoding algorithm then collaborates with the joint detection based on the RC-VSS algorithm to improve the overall BER performance. Theoretical analysis and Monte Carlo simulated results reveal that the proposed DRSCC-LD scheme clearly outperforms its corresponding non-cooperative RS coded scheme by a gain of more than 7 dB and the existing schemes by a margin of more than 3.5 dB under the identical conditions, respectively. [ABSTRACT FROM AUTHOR]

Two constructions of lattice packings of n$ n$‐dimensional cross‐polytopes (ℓ1$ \ell _1$ balls) are described, the density of which exceeds that of any prior construction by a factor of at least 2nlnn(1+o(1))$ 2^{\frac{n}{\ln n}(1 + o(1))}$. The first family of lattices is explicit and is obtained by applying Construction A to a class of Reed–Solomon codes. The second family has subexponential construction complexity and is based on the notion of Sidon sets in finite Abelian groups. The construction based on Sidon sets also gives the highest known asymptotic density of packing discrete cross‐polytopes of fixed radius r⩾3$ r \geqslant 3$ in Zn$ \mathbb {Z}^n$. [ABSTRACT FROM AUTHOR]

Regard T = { (g , ... , g) ∈ F q n : g ∈ F q } as an additive subgroup of the vector space F q n over a finite field F q . A code C ⊂ F q n is T-invariant if T acts on C induced by the addition of F q n . Using linear algebra and finite fields results, we investigate which important families of codes are T-invariant, including perfect codes, first-order Reed–Muller codes, and some Reed–Solomon codes. In particular, we characterize which perfect linear codes are T-invariant. A version of the Gilbert–Varshamov theorem for T-invariant codes is presented. We characterize which Hadamard codes are T-invariant for nonlinear codes. As an application, constructions of difference schemes are obtained using our results. Finally, difference schemes of strength 2 over a finite field are characterized using quasigroups endowed with a distributive law. [ABSTRACT FROM AUTHOR]

Subsystem codes are one of the most versatile tools in quantum error correction because they allow one to combine passive error correction in decoherence subspaces and noiseless subsystems with active error correction methods of quantum error correction codes. In this paper, based on the classical (extended) GRS codes, we propose several new methods for constructing optimal subsystem codes over finite fields with even and odd characteristics. It is worth noting that a large amount of optimal subsystem codes can be generated by our constructors. [ABSTRACT FROM AUTHOR]

In 1978, McEliece built the first public key cryptosystem based on error-correcting codes. This cryptosystem based on Goppa codes is considered promising and cryptographically stable, taking into account quantum computing. At the same time, effective attacks on the secret keys of this cryptosystem have not yet been found. In the paper, algorithms for decoding Goppa codes in the case of errors and erasures are investigated. Four decoding algorithms based on the algorithms for Reed–Solomon codes proposed by Gao, Berlekamp and Massey, Sugiyama, and others are given. The first two algorithms are based on Gao algorithm and related to syndrome-free decoding algorithms, the rest are related to syndrome decoding algorithms. Moreover, any of these algorithms is also applicable for the case of a communication channel with errors only. Examples of decoding separable Goppa codes using these algorithms are also given.

We study the problem of solving a system of m polynomials in n variables over the ring of integers modulo a prime-power p k. The problem over finite fields is well studied in varied parameter settings. For small characteristic p = 2 , Lokshtanov et al. (SODA'17) initiated the study, for degree d = 2 systems, to improve the exhaustive search complexity of O (2 n) ⋅ poly (m , n) to O (2 0.8765 n) ⋅ poly (m , n) ; which currently is improved to O (2 0.6943 n) ⋅ poly (m , n) in Dinur (SODA'21). For large p but constant n , Huang and Wong (FOCS'96) gave a randomized poly (d , m , log ⁡ p) time algorithm. Note that for growing n , system-solving is known to be intractable even with p = 2 and degree d = 2. We devise a randomized poly (d , m , log ⁡ p) -time algorithm to find a root of a given system of m integral polynomials of degrees bounded by d , in n variables, modulo a prime power p k ; when n + k is constant. In a way, we extend the efficient algorithm of Huang and Wong (FOCS'96) for system-solving over Galois fields (i.e., characteristic p) to system-solving over Galois rings (i.e., characteristic p k); when k > 1 is constant. The challenge here is to find a lift of singular F p -roots (exponentially many); as there is no efficient general way known in algebraic-geometry for resolving singularities. Our algorithm has applications to factoring univariate polynomials over Galois rings. Given f ∈ Z [ x ] and a prime-power p k (k ≥ 2), finding factors of f mod p k has a curious state-of-the-art. It is solved for large k by p -adic factoring algorithms (von zur Gathen, Hartlieb, ISSAC'96); but unsolved for small k. In particular, no nontrivial factoring method is known for k ≥ 5 (Dwivedi, Mittal, Saxena, ISSAC'19). One issue is that degree- δ factors of f (x) mod p k could be exponentially many, as soon as k ≥ 2. We give the first randomized poly (deg ⁡ (f) , log ⁡ p) -time algorithm to find a degree- δ factor of f (x) mod p k , when k + δ is constant. Our method has potential application in algebraic coding theory. In particular, extending algebraic geometric and Reed-Solomon codes to Galois rings could enable new and improved bounds on their underlying efficiency parameters. [ABSTRACT FROM AUTHOR]

Let F q denote the finite field of size q and F q n denote the set of n -tuples of elements from F q. A family of k -dimensional subspaces of F q n , which forms a partial spread, is called L -almost affinely disjoint (or briefly [ n , k , L ] q -AAD) if each affine coset of a member of this family intersects with only at most L subspaces from the family. Polyanskii and Vorobyev introduced AAD subspace families in [23] (2019) in order to construct some types of primitive batch codes. For this purpose, they made use of Reed-Solomon codes and hence they presented [ n = 2 k + 1 , k , L = k ] -AAD subspace families of size ⌊ q / k ⌋. Later on, AAD spaces received a notable attention and have been studied for various parameters, see Liu et al. [18] (2021) and Otal and Arıkan [21] (2022) for example. In Arıkan et al. (2023) [1] , we presented a construction of [ 2 k + 1 , k , k ] -AAD subspace families of size q , which improves the lower bound ⌊ q / k ⌋ given by Polyanskii and Vorobyev in [23] (2019) k times. We also proved that our construction yields AAD subspace families for k = 2 and k = 3 , and left the proof of the case k ≥ 4 as a conjecture. In this paper, we now prove this conjecture by a newer and more abstract approach. For the proof, we carefully utilize several sophisticated arguments coming from coding theory, algebraic geometry, and linear algebra. In particular, we interpret each subspace as a suitable generator matrix (the lifting idea in random network coding), then algebraically manipulate their AAD-ness relation and produce suitable Van der Monde matrices (the fundamental tools for the BCH bound in coding theory), later apply Cramer's rule (a well-known key tool in linear algebra), and lastly obtain low-degree polynomials as contradictions (the trick coming from algebraic geometry utilized for Goppa codes). We present our constructive proof step-by-step to make it more easy to understand. [ABSTRACT FROM AUTHOR]

We used modulating retro-reflector (MRR), hybrid frequency-phase-keying (FPK) modulation, and Reed-Solomon (RS) code technology to improve the performance of the terrestrial-satellite laser communication link. A system using FPK modulation and RS codes based on the Fisher-Snedecor (F) distribution atmospheric turbulence model is proposed for the MRR-assisted terrestrial-high-altitude-platform (HAP)-satellite laser communication, in which MRR is installed on the HAP. The laser beam without signal is transmitted to HAP through the forward path. The MRR loads the optical signal from the terrestrial-HAP link onto the optical carrier, which is then reflected back to the satellite terminal along the backward path. The combined effects of light intensity scintillation of atmospheric turbulence, beam wander of uplink, atmospheric attenuation, pointing error, and HAP random jitter on the terrestrial-HAP (equipped with MRR)-satellite (T-HMRR-S) laser communication link are considered. The expression of the BER of RS codes and FPK modulation (RS-FPK) system under weak atmospheric turbulence is derived and compared with terrestrial-HAP-satellite (T-H-S) system with different modulation and without MRR. At the same time, the effects of modulation coding parameters, zenith angle, the field-of-view angle, and the coverage area of the MRR on the performance of the T-HMRR-S system are simulated and analyzed. The simulation results show that the T-HMRR-S system using RS-FPK technology has better performance. These works provide a theoretical basis for the research of modulation coding technology of T-HMRR-S link systems. [ABSTRACT FROM AUTHOR]

Entanglement-assisted quantum error-correcting codes (EAQECCs) extend the usual structure of quantum error-correcting codes (QECCs) by introducing the pre-shared entanglement. This new ingredient increases quantum error-correcting capability in some cases. The nonexistence of general constructions of q -ary quantum maximum distance separable (MDS) codes with minimum distances d > q + 1 motivates us to establish entanglement-assisted quantum MDS codes whose minimum distances are greater than q + 1. In this paper, we propose new constructions of EAQECCs achieving the quantum Singleton bound. Our constructions are based on Reed-Solomon codes over the finite field F q 2 . The constructed q -ary EAQECCs have new parameters and minimum distances d > q + 1. [ABSTRACT FROM AUTHOR]

Considering the availability of the global navigation satellite system (GNSS) signals and the increase in its data rate in the future, this paper proposes some new Reed-Solomon coded (RS-coded) orthogonal modulation schemes using the Hadamard codes, as an alternative to the RS-coded code-shift-keying (CSK) modulation in the Quasi-Zenith Satellite System L-band experimental (QZSS-LEX) signals. The simulation result of the proposed schemes shows that, though the frame size and hence the data rate is increased with much reduced complexity in the receiver, the bit error rate performance of RS-coded orthogonal modulation is slightly better than or comparable to the QZSS-LEX.

Aiming to improve the error correction performance of polar codes, researchers have proposed employing the product coding structure involving RS codes of different rates in the horizontal direction and the short polar codewords along the vertical direction. However, there is no efficient algorithm optimizing the rate allocation of RS codes. In order to address this problem, this paper provides an analytical formulation by maximizing the number of correctly decoded information bits. The proposed rate allocation formulation takes the channel statistics into consideration, and we further find that the number of different RS code rates could be limited to a small value. By doing so, the complexities of both the rate allocation optimization and the iterative product decoding could be reduced. Simulation results demonstrate the superiority of RS-polar product codes with the proposed rate allocation method over both additive white Gaussian noise channels and Gilbert–Elliott channels. When the inner polar codes of rate 1 / 2 are utilized, the optimized RS-polar product codes of low-to-medium rates significantly outperform the successive cancellation decoding of long polar codes, in the regime of a frame error rate ≥ 10 − 3 . [ABSTRACT FROM AUTHOR]

The high storage costs brought by the full-replication storage strategy adopted in most existing blockchain systems have become the main bottleneck to system scalability. To address the above, we propose an asynchronous committee-based blockchain storage strategy named lightweight BFT (LBFT), which can be applied to more diverse scenarios with better system performance. It is the first blockchain storage scheme that is designed on the conception of the zero-trust model, achieving higher-level security and fending off internal, as well as external attackers. In addition, it makes the following progress on system performance on the premise of maintaining the merits of the blockchain: (1) decreases communication complexity by involving only a part of the nodes in each decoding round; (2) enhances the robustness of the scheme regardless of the time assumption of the network; (3) improves the computational efficiency in the encoding and decoding process; and (4) reduces the storage costs and improves system scalability. In addition, we implemented experiments on LBFT and two other existing blockchain-based storage strategies, and the experimental results showed that LBFT indeed has significant improvements in system performance. [ABSTRACT FROM AUTHOR]

An $(n,r,h,a,q)$ -Local Reconstruction Code (LRC) is a linear code over $\mathbb {F}_{q}$ of length $n$ , whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies ‘ $a$ ’ local parity checks to recover from ‘ $a$ ’ erasures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience—namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to ‘ $a$ ’ erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$ -MR LRCs with field size $q$ bounded by $\left ({O\left ({\max \{r,n/r\}}\right)}\right)^{\min \{h,r-a\}}$. This significantly improves upon known constructions in many practically relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=\Theta (\sqrt {n})$ , $r-a=\Theta (\sqrt {n})$ and $h$ is a fixed constant with $h \leqslant a+2$ , achieving the optimal field size of $\Theta _{h}(n^{h/2})$. Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory. [ABSTRACT FROM AUTHOR]

Copyright of Przegląd Elektrotechniczny is the property of Przeglad Elektrotechniczny and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Quick Response (QR) codes are two-dimensional bar codes that have become a common medium for easily accessing information such as URLs, phone numbers, and small amounts of text. Creating a QR code requires placing data in a prescribed format so that it can be displayed on a surface and then detected by common QR code scanner software. Like other physical means of storing data, QR codes are prone to errors when their data is interpreted in a digital format. Reed- Solomon codes provide a mechanism for ensuring that QR code scanners can reliably process information when errors occur. This involves encoding information in the form of polynomial coefficients using finite field arithmetic. Utilizing Reed-Solomon codes can sometimes allow a logo and emblem to be embedded within a QR code to advertise its purpose, even while the logo or emblem covers part of the data to be scanned. In this paper we will describe how QR codes are constructed, and how Reed-Solomon codes are incorporated within them to provide error correction. To assist in demonstrating this, we will use technology involving Maplets. [ABSTRACT FROM AUTHOR]

In this paper, we determine all dihedral subgroups in $PGL_{2}(\mathbb {F}_{q})$ , where $q=2^{l}$ and $l$ is a positive integer; and construct binary expurgated and extended Goppa codes with dihedral automorphism groups. Moreover, it is easy to obtain binary quasi-cyclic expurgated or extended Goppa codes. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Consider a file synchronization problem at two remote nodes A and B connected by a noiseless link. The node A has a binary file $X$ , and node B has a binary file $Y$ which is an edited version of $X$ with random insertions and deletions (indels). The goal is to reconstruct $X$ at node B from $Y$ with minimal exchange of information between A and B. In this letter, we design a single-round, thus low latency, file synchronization scheme with low redundancy. In particular, a series of redundancy bits, including markers, check symbols of Reed-Solomon (RS) codes for hashes and Varshamov-Tenengolts (VT) syndromes, are constructed from $X$ at node A and send to node B. According to the received redundancy and $Y$ , we develop a recovery algorithm at node B to reconstruct $X$. The amount of exchanged information of the proposed scheme is significantly reduced when compared with the existing single-round synchronization scheme under random indels. [ABSTRACT FROM AUTHOR]

Light nodes in blockchains improve the scalability of the system by storing a small portion of the blockchain ledger. In certain blockchains, light nodes are vulnerable to a data availability (DA) attack where a malicious node makes the light nodes accept an invalid block by hiding the invalid portion of the block from the nodes in the system. Recently, a technique based on LDPC codes called Coded Merkle Tree (CMT) was proposed by Yu et al. that enables light nodes to detect a DA attack by randomly requesting/sampling portions of the block from the malicious node. However, light nodes fail to detect a DA attack with high probability if a malicious node hides a small stopping set of the LDPC code. To mitigate this problem, Yu et al. used random LDPC codes that achieve large minimum stopping set size with high probability. Although effective, these codes are not necessarily optimal for this application, especially at short code lengths, which are relevant for low latency systems, IoT blockchains, etc.. In this paper, we focus on short code lengths and demonstrate that a suitable co-design of specialized LDPC codes and the light node sampling strategy can improve the probability of detection of DA attacks. We consider different adversary models based on their computational capabilities of finding stopping sets in LDPC codes. For a weak adversary model, we devise a new LDPC code construction termed as the entropy-constrained PEG (EC-PEG) algorithm which concentrates stopping sets to a small group of variable nodes. We demonstrate that the EC-PEG algorithm coupled with a greedy sampling strategy improves the probability of detection of DA attacks. For stronger adversary models, we provide a co-design of a sampling strategy called linear-programming-sampling (LP-sampling) and an LDPC code construction called linear-programming-constrained PEG (LC-PEG) algorithm. The new co-design demonstrates a higher probability of detection of DA attacks compared to approaches in earlier literature. [ABSTRACT FROM AUTHOR]

Binary quasi-reversible BCH codes whose defining set contains consecutive elements from negative to positive integers have received considerable attention in recent years due to their efficient decoding suitable for a wide range of applications. This paper combines the concept of the weight and quasi-reversible structures to introduce two subclasses of BCH codes: odd-like/even-like quasi-reversible BCH codes. The step-by-step decoding of these codes is developed as follows: First, the weight evaluation of a received polynomial is able to judge whether the number of errors is odd or even, which helps to simplify the decoding processes. Second, based on Chiò’s pivotal condensation process which can be easily implemented in a parallel computing architecture, the determinant calculation of the band matrix instead of Peterson’s matrix in column-echelon form is faster. Third, a newly proposed non-monic error-locator polynomial is sparser than the conventional ones. As a consequence, the theoretical analysis and experimental results validate potential benefits in requiring fewer finite field additions and multiplications used in the decoding of binary odd-like/even-like quasi-reversible BCH codes up to half the minimum distance when compared with the narrow-sense BCH codes with small error-correcting capability. [ABSTRACT FROM AUTHOR]