Search

In this paper, we use the CSS and Steane's constructions to establish quantum error-correcting codes (briefly, QEC codes) from cyclic codes of length 3 p s over F p m . We obtain several new classes of QEC codes in the sense that their parameters are different from all the previous constructions. Among them, we identify all quantum MDS (briefly, qMDS) codes, i.e., optimal quantum codes with respect to the quantum Singleton bound. In addition, we construct quantum synchronizable codes (briefly, QSCs) from cyclic codes of length 3 p s over F p m . Furthermore, we give many new QSCs to enrich the variety of available QSCs. A lot of them are QSCs codes with shorter lengths and much larger minimum distances than known non-primitive narrow-sense BCH codes. [ABSTRACT FROM AUTHOR]

In this paper, by using the Hamming distance, we establish a relation between quantum error-correcting codes ((N , K , d + 1)) s and orthogonal arrays with orthogonal partitions. Therefore, this is a generalization of the relation between quantum error-correcting codes ((N , 1 , d + 1)) s and irredundant orthogonal arrays. This relation is used for the construction of pure quantum error-correcting codes. As applications of this method, numerous infinite families of optimal quantum codes can be constructed explicitly such as ((3 , s , 2)) s for all s i ≥ 3 , ((4 , s 2 , 2)) s for all s i ≥ 5 , ((5 , s , 3)) s for all s i ≥ 4 , ((6 , s 2 , 3)) s for all s i ≥ 5 , ((7 , s 3 , 3)) s for all s i ≥ 7 , ((8 , s 2 , 4)) s for all s i ≥ 9 , ((9 , s 3 , 4)) s for all s i ≥ 11 , ((9 , s , 5)) s for all s i ≥ 9 , ((10 , s 2 , 5)) s for all s i ≥ 11 , ((11 , s , 6)) s for all s i ≥ 11 , and ((12 , s 2 , 6)) s for all s i ≥ 13 , where s = s 1 ⋯ s n and s 1 , ... , s n are all prime powers. The advantages of our approach over existing methods lie in the facts that these results are not just existence results, but constructive results, the codes constructed are pure, and each basis state of these codes has far less terms. Moreover, the above method developed can be extended to construction of quantum error-correcting codes over mixed alphabets. [ABSTRACT FROM AUTHOR]

In this paper, we use a method inspired by the valuation theory to classify completely cyclic codes of length 3 p s over p m + u p m + u 2 p m . Then, we compute their separation parameters which was useful to compute the Hamming distance in [8]. [ABSTRACT FROM AUTHOR]

This paper presents an approach to the construction of block error-correcting code for data transmission systems with short packets. The need for this is driven by the necessity of information interaction between objects of machine-type communication network with a dynamically changing structure and unique system of commands or alerts for each network object. The codewords of a code are permutations with a given minimum pairwise Hamming distance. The purpose of the study is to develop a statistical method for constructing a code, in contrast to known algebraic methods, and to investigate the code size. An algorithm for generating codewords has been developed. It can be implemented both by enumeration of the full set of permutations, and by enumeration of a given number of randomly selected permutations. We have experimentally determined the dependencies of the average and the maximum values of the code size on the size of a subset of permutations used for constructing the code. A technique for computing approximation quadratic polynomials for the determined code size dependencies has been developed. These polynomials and their corresponding curves estimate the size of a code generated from a subset of random permutations of such a size that a statistically significant experiment cannot be performed. The results of implementing the developed technique for constructing a code based on permutations of lengths 7 and 11 have been presented. The prediction relative error of the code size did not exceed the value of 0.72% for permutation length 11, code distance 9, random permutation subset size 50,000, and permutation statistical study range limited by 5040. [ABSTRACT FROM AUTHOR]

In this paper, we establish all quantum error-correcting codes (briefly, QEC codes) from cyclic and negacyclic codes of length 4 p s over F p m using CSS and Steane's constructions. Some new QEC codes are given in the sense that their parameters are different from all the previous constructions. In addition, if we fix the length and the Hamming distance of a QEC code, some QEC codes are better than all QEC codes in the sense that their dimensions are larger than the dimensions of all the previous QEC codes. We also investigate quantum maximum distance separable (briefly, qMDS) codes from cyclic and negacyclic codes of length 4 p s over finite fields using the CSS and Hermitian constructions. We provide all qMDS codes constructed from dual codes of cyclic and negacyclic codes of length 4 p s over finite fields using the Hermitian construction. We also construct quantum synchronizable codes (briefly, QSCs) from cyclic codes of length 4 p s over F p m . To enrich the variety of available QSCs, many new QSCs are constructed to illustrate our results. Among them, there are QSCs codes with shorter lengths and much larger minimum distances than known non-primitive narrow-sense BCH codes. [ABSTRACT FROM AUTHOR]

If we fix the code length n and dimension k, maximum distance separable (briefly, MDS) codes form an important class of codes because the class of MDS codes has the greatest error-correcting and detecting capabilities. In this paper, we establish all MDS constacyclic codes of length ps over F p m . We also give some examples of MDS constacyclic codes over finite fields. As an application, we construct all quantum MDS codes from repeated-root codes of prime power lengths over finite fields using the CSS and Hermitian constructions. We provide all quantum MDS codes constructed from dual codes of repeated-root codes of prime power lengths over finite fields using the Hermitian construction. They are new in the sense that their parameters are different from all the previous constructions. Moreover, some of them have larger Hamming distances than the well known quantum error-correcting codes in the literature. [ABSTRACT FROM AUTHOR]

Due to the wide applications in consumer electronics, data storage systems and communication systems, cyclic codes have been an interesting research topic in coding theory. In this paper, let p be a prime with p ≥ 7. We determine the Hamming distances of all repeated-root cyclic codes of length 5 p s over F q , where q = p m and both s and m are positive integers. Furthermore, we find all MDS cyclic codes of length 5 p s and take quantum synchronizable codes from repeated-root cyclic codes of length 5 p s . By comparing the minimum distances of 5 p s -length repeated-root cyclic codes to BCH codes of close lengths, we illustrated that quantum synchronizable codes constructed from repeated-root cyclic codes have in general better performance in correcting Pauli errors than those from BCH codes. [ABSTRACT FROM AUTHOR]

Hamming codes are of primary concern in information theory and its applications. Despite a number of researches that have been conducted on such codes and their characterizations, dealing with the properties of previously introduced codes in a BCK-algebraic framework has not been considered in earlier works. This paper investigates a code constructed based on BCK-algebraic models and proposes an algorithm corresponding to the presented code. It is noticeable that the suggested rendered algorithm is also established on the basis of the elements of a BCK-algebra. In fact, both the Hamming distance and dimension, associated with the presented code, can be estimated through a BCK-algebra structure due to the mechanism of its algorithm which is heavily dependent on the parity check matrix. In addition, the way in which the codes are designed contributes substantially to classification of them and to extract greater number of their attributes compared to the previous works. The highlight of the proposed method is that the number of atoms of the BCK-algebra plays a key role in calculation of the Hamming distance and dimension of these codes. Moreover, the obtained codes possess specified and recognizable Hamming distance which are essential in performing error-correcting, error-detecting and decoding tasks. [ABSTRACT FROM AUTHOR]

A common way to protect data stored in DRAM and related memory systems is through the use of an error-correcting code such as the extended Hamming code. Traditionally, these error-correcting codes provide equal protection guarantees to all messages. In this paper, we focus on unequal message protection (UMP), in which a subset of messages is deemed as special, and is afforded additional error-correction protection while maintaining the same number of redundancy bits as the baseline code. UMP is a powerful approach when the special messages are chosen based on the knowledge of data patterns in context. Our objective is to construct deterministic, algebraic codes with guaranteed UMP properties, derive their cardinality bounds using novel combinatorial techniques, and to demonstrate their efficacy for realistic memory benchmarks. We first introduce a UMP alternative to the single-bit parity-check code, and then we generalize to a broader UMP code family, including a UMP alternative to the extended Hamming code, offering full double-error correction protection to special messages. Our UMP constructions, applied to main memory in high-performance computing applications, could lead to significant system-level benefits such as less frequent checkpoints in supercomputers and decreased risk of catastrophic failure from erroneous special messages. [ABSTRACT FROM AUTHOR]

It is shown that the certain combinatorial structures called stopping sets have the important role in analysis of iterative decoding. In this paper, the number of minimum stopping sets of a product code is determined by the number of the minimum stopping sets of the corresponding component codes. As an example, the number of minimum stopping sets of the r-dimensional SPC product code is computed. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with $r$ redundancy nodes can correct any $r$ node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, $e$ erasures are a more likely failure event, for some $1 \le e < r$ . Hence, a natural question is how much information do we need to access in order to rebuild $e$ storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of $e$ erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of $1/r$ for the rebuilding of any systematic node when $e=1$ ; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any $r$ erasures can be corrected by accessing some of the remaining information, and any $e=1$ erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of $e/r$ for systematic nodes of MDS codes, for any $1 \le e \le r$ ; 2) we construct systematic codes that achieve optimal rebuilding ratio of $1/r$ , for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances. [ABSTRACT FROM AUTHOR]

A mapping of k -bit strings into n -bit strings is called an ( α , β ) -map if k -bit strings which are more than αk apart are mapped to n -bit strings that are more than βn apart in Hamming distance. This is a relaxation of the classical problem of constructing error-correcting codes, which corresponds to α = 0 . Existence of an ( α , β ) -map is equivalent to existence of a graph homomorphism H ¯ ( k , α k ) → H ¯ ( n , β n ) , where H ( n , d ) is a Hamming graph with vertex set { 0 , 1 } n and edges connecting vertices differing in d or fewer entries. This paper proves impossibility results on achievable parameters ( α , β ) in the regime of n , k → ∞ with a fixed ratio n k = ρ . This is done by developing a general criterion for existence of graph-homomorphism based on the semi-definite relaxation of the independence number of a graph (known as the Schrijver's θ -function). The criterion is then evaluated using some known and some new results from coding theory concerning the θ -function of Hamming graphs. As an example, it is shown that if β > 1 / 2 and n k – integer, the n k -fold repetition map achieving α = β is asymptotically optimal. Finally, constraints on configurations of points and hyperplanes in projective spaces over F 2 are derived. [ABSTRACT FROM AUTHOR]

Cyclic codes with a few weights are very useful in the design of frequency hopping sequences and the development of secret sharing schemes. In this paper, we mainly use Gauss sums to represent the Hamming weights of cyclic codes whose duals have two zeroes. A lower bound of the minimum Hamming distance is determined. In some cases, we give the Hamming weight distributions of the cyclic codes. In particular, we obtain a class of three-weight optimal cyclic codes achieving the Griesmer bound, which generalizes a Vega’s result, and several classes of cyclic codes with a few weights, which solve an open problem proposed by Vega. [ABSTRACT FROM AUTHOR]

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH , the corresponding minimum pair distance is at least dH+3 . In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance dH , the minimum pair distance is at least dH +\left \lceil{ {dH/{2}}}\right \rceil . We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, $b \geqslant 3$ , of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting. [ABSTRACT FROM AUTHOR]

We introduce the class of partition-balanced families of codes, and show how to exploit their combinatorial invariants to obtain upper and lower bounds on the number of codes that have a prescribed property. In particular, we derive precise asymptotic estimates on the density functions of several classes of codes that are extremal with respect to minimum distance, covering radius, and maximality. The techniques developed in this paper apply to various distance functions, including the Hamming and the rank metric distances. Applications of our results show that, unlike the F q m -linear MRD codes, the F q -linear MRD codes are not dense in the family of codes of the same dimension. More precisely, we show that the density of F q -linear MRD codes in F q n × m in the set of all matrix codes of the same dimension is asymptotically at most 1/2, both as q → + ∞ and as m → + ∞. We also prove that MDS and F q m -linear MRD codes are dense in the family of maximal codes. Although there does not exist a direct analogue of the redundancy bound for the covering radius of F q -linear rank metric codes, we show that a similar bound is satisfied by a uniformly random matrix code with high probability. In particular, we prove that codes meeting this bound are dense. Finally, we compute the average weight distribution of linear codes in the rank metric, and other parameters that generalize the total weight of a linear code. [ABSTRACT FROM AUTHOR]