Search

This work presents a population genetic model of evolution, which includes haploid selection, mutation, recombination, and drift. The mutation-selection equilibrium can be expressed exactly in closed form for arbitrary fitness functions without resorting to diffusion approximations. Tractability is achieved by generating new offspring using n-parent rather than 2-parent recombination. While this enforces linkage equilibrium among offspring, it allows analysis of the whole population under linkage disequilibrium. We derive a general and exact relationship between fitness fluctuations and response to selection. Our assumptions allow analytical calculation of the stationary distribution of the model for a variety of non-trivial fitness functions. These results allow us to speak to genetic architecture, i.e., what stationary distributions result from different fitness functions. This paper presents methods for exactly deriving stationary states for finite and infinite populations. This method can be applied to many fitness functions, and we give exact calculations for four of these. These results allow us to investigate metastability, tradeoffs between fitness functions, and even consider error-correcting codes. [ABSTRACT FROM AUTHOR]

DNA-based storage has been a promising technique of data storage, due to its high density and long duration. During synthesizing and sequencing of DNA storage, edit errors including insertions, deletions and substitutions are introduced inevitably. An effective way to reduce the error probability is to limit the content of G and C in DNA sequences to around 50%, which is called GC-balanced. To deal with edit errors, DNA sequences are also expected to have error-correcting capabilities. In this paper, GC globally balanced and GC locally balanced error-correcting codes are explicitly constructed, respectively. Inspired by repetition codes, the proposed codes are able to correct multiple edit errors. Furthermore, an efficient decoding algorithm applied for both codes is derived when only one kind of edit error occur. [ABSTRACT FROM AUTHOR]

Planar functions are of great importance in the constructions of DES-like iterated ciphers, error-correcting codes, signal sets and mathematics. They are defined over finite fields of odd characteristic originally and generalized by Y. Zhou [28] in even characteristic. In 2016, L. Qu [23] proposed a new approach to constructing quadratic planar functions over F 2 n . Very recently, D. Bartoli and M. Timpanella [4] characterized the condition on coefficients a , b such that the function f a , b (x) = a x 2 2 m + 1 + b x 2 m + 1 ∈ F 2 3 m [ x ] is a planar function over F 2 3 m by the Hasse-Weil bound. In this paper, using the Lang-Weil bound, a generalization of the Hasse-Weil bound, and the new approach introduced in [23] , we completely characterize the necessary and sufficient conditions on coefficients of four classes of planar functions over F q k , where q = 2 m with m sufficiently large (see Theorem 1.1). The first and last classes of them are over F q 2 and F q 4 respectively, while the other two classes are over F q 3 . One class over F q 3 is an extension of f a , b (x) investigated in [4] , while our proofs seem to be much simpler. In addition, although the planar binomial over F q 2 of our results is finally a known planar monomial, we also answer the necessity at the same time and solve partially an open problem for the binomial case proposed in [23]. [ABSTRACT FROM AUTHOR]

The error-correcting pair is a general algebraic decoding method for linear codes, which exists for many classical linear codes. Since every linear code is contained in an MDS linear code with the same minimum distance over some finite field extension, we focus our study on MDS linear codes. It is well-known that an MDS linear code with minimum distance 2 ℓ + 1 has an ℓ -error-correcting pair if and only if it is a generalized Reed-Solomon code. In this paper, we show that for an MDS linear code C with minimal distance 2 ℓ + 2 , if it has an ℓ -error-correcting pair, then the parameters of the pair are three cases. For one case, we give a necessary condition that C is a generalized Reed-Solomon code, and then give some counterexamples that C is a non-generalized Reed-Solomon code for the other two cases. [ABSTRACT FROM AUTHOR]

Abstract Binary asymmetric error-correcting codes (AECC) play an important role in communication systems modeled by the binary symmetric channel (Z-channel). Varshamov proposed a general construction of binary AECC via V h -sequences and obtained many good binary AECC. In this paper, we give a general construction of V h -sequences in ray class groups of algebraic function fields. Our construction induces new lower bounds for binary AECC which improves the results in [18]. [ABSTRACT FROM AUTHOR]

In this paper, we characterize hulls of double cyclic codes over Z 2. Firstly, we give the generators of hulls of double cyclic codes under the separable case and the non-separable case with coprime odd block lengths. Then, using the concept of a generating function in combinatorics, the solution of dimensions of hulls of double cyclic codes over Z 2 is given. Furthermore, the enumeration of double cyclic codes over Z 2 with hulls of a fixed dimension is determined. As an application, some good entanglement-assisted quantum error-correcting codes (EAQECCs) are obtained by the hulls of non-separable double cyclic codes. [ABSTRACT FROM AUTHOR]

Galois hulls of MDS codes can be applied to construst MDS entanglement-assisted quantum error-correcting codes (EAQECCs). Goppa codes and expurgated Goppa codes (resp., extended Goppa codes) over F q m are GRS codes (resp., extended GRS codes) when m = 1. In this paper, we investigate the Galois dual codes of a special kind of Goppa codes and related codes and provide a necessary and sufficient condition for the Galois dual codes of such codes to be Goppa codes and related codes. Then we determine the Galois hulls of the above codes. In particular, we completely characterize Galois LCD, Galois self-orthogonal, Galois dual-containing and Galois self-dual codes among such family of codes. Moreover, we apply the above results to EAQECCs. [ABSTRACT FROM AUTHOR]

Generalized quasi-cyclic (GQC) codes have been investigated as well as quasi-cyclic (QC) codes, e.g., on the construction of efficient low-density parity-check codes. While QC codes have the same length of cyclic intervals, GQC codes have different lengths of cyclic intervals. Similarly to QC codes, each GQC code can be described by an upper triangular generator polynomial matrix, from which the systematic encoder is constructed. In this paper, a complete theory of generator polynomial matrices of GQC codes, including a relation formula between generator polynomial matrices and parity-check polynomial matrices through their equations, is provided. This relation generalizes those of cyclic codes and QC codes. While the previous researches on GQC codes are mainly concerned with 1-generator case or linear algebraic approach, our argument covers the general case and shows the complete analogy of QC case. We do not use Gröbner basis theory explicitly in order that all arguments of this paper are self-contained. Numerical examples are attached to the dual procedure that extracts one from each other. Finally, we provide an efficient algorithm which calculates all generator polynomial matrices with given cyclic intervals. [ABSTRACT FROM AUTHOR]

Quantum error-correcting codes with good parameters can be constructed by evaluating polynomials at the roots of the polynomial trace [18]. In this paper, we propose to evaluate polynomials at the roots of trace-depending polynomials (given by a constant plus the trace of a polynomial) and show that this procedure gives rise to stabilizer quantum error-correcting codes with a wider range of lengths than in [18] and with excellent parameters. Namely, we are able to provide new binary records according to [21] and non-binary codes improving the ones available in the literature. [ABSTRACT FROM AUTHOR]

The construction of quantum maximum distance separable (abbreviated to MDS) error-correcting codes has become one of the major concerns in quantum coding theory. In this paper, we further generalize the approach developed in the previous paper, and construct several new classes of Hermitian self-orthogonal generalized Reed-Solomon (GRS) codes. By employing these classical MDS codes, we obtain several classes of quantum MDS codes with large minimum distance. It turns out that our quantum MDS codes exhibited here have less constraints on the selection of code length and some of them have not been constructed before, and in some cases, have larger minimum distance than previous literature. Meanwhile, about half of the distance parameters of our codes are greater than q 2 + 1. [ABSTRACT FROM AUTHOR]

Cyclic Reed–Solomon codes, a type of BCH codes, are widely used in consumer electronics, communication systems, and data storage devices. This fact demonstrates the importance of BCH codes – a family of cyclic codes – in practice. In theory, BCH codes are among the best cyclic codes in terms of their error-correcting capability. A subclass of BCH codes are the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The objective of this paper is to determine the dimension and minimum distances of two classes of narrow-sense primitive BCH codes with designed distances δ = ( q − 1 ) q m − 1 − 1 − q ⌊ ( m − 1 ) / 2 ⌋ and δ = ( q − 1 ) q m − 1 − 1 − q ⌊ ( m + 1 ) / 2 ⌋ . The weight distributions of some of these BCH codes are also reported. As will be seen, the two classes of BCH codes are sometimes optimal and sometimes among the best linear codes known. [ABSTRACT FROM AUTHOR]

The generalized Hamming weights of a linear code have been extensively studied since Wei first use them to characterize the cryptography performance of a linear code over the wire-tap channel of type II. In this paper, we investigate the generalized Hamming weights of three classes of linear codes constructed through defining sets and determine them partly for some cases. Particularly, in the semiprimitive case we solve a problem left in Yang et al. (2015) [30] . [ABSTRACT FROM AUTHOR]

The generalized Hamming weights (GHWs) are fundamental parameters of linear codes. GHWs are of great interest in many applications since they convey detailed information of linear codes. In this paper, we continue the work of [10] to study the GHWs of a family of cyclic codes with arbitrary number of nonzeroes. The weight hierarchy is determined by employing a number-theoretic approach. [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]

Goppa codes were defined by Valery D. Goppa in 1970. In 1978, Robert J. McEliece used this family of error-correcting codes in his cryptosystem, which has gained popularity in the last decade due to its resistance to attacks from quantum computers. In this paper, we present Goppa codes over the p -adic integers and integers modulo p e. This allows the creation of chains of Goppa codes over different rings. We show some of their properties, such as parity-check matrices and minimum distance, and suggest their cryptographic application, following McEliece's scheme. [ABSTRACT FROM AUTHOR]

This work investigates the structure of rank-metric codes in connection with concepts from finite geometry, most notably the q -analogues of projective systems and blocking sets. We also illustrate how to associate a classical Hamming-metric code to a rank-metric one, in such a way that various rank-metric properties naturally translate into the homonymous Hamming-metric notions under this correspondence. The most interesting applications of our results lie in the theory of minimal rank-metric codes, which we introduce and study from several angles. Our main contributions are bounds for the parameters of a minimal rank-metric codes, a general existence result based on a combinatorial argument, and an explicit code construction for some parameter sets that uses the notion of a scattered linear set. Throughout the paper we also show and comment on curious analogies/divergences between the theories of error-correcting codes in the rank and in the Hamming metric. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a finitely presented group, and let p be a prime. Then G is ‘large’ (respectively, ‘p-large’) if some normal subgroup with finite index (respectively, index a power of p) admits a non-abelian free quotient. This paper provides a variety of new methods for detecting whether G is large or p-large. These relate to the group''s profinite and pro-p completions, to its first -Betti number and to the existence of certain finite index subgroups with ‘rapid descent’. The paper draws on new topological and geometric techniques, together with a result on error-correcting codes. [Copyright &y& Elsevier]

Abstract: Traceability codes are combinatorial objects introduced by Chor, Fiat and Naor in 1994 to be used in traitor tracing schemes to protect digital content. A k-traceability code is used in a scheme to trace the origin of digital content under the assumption that no more than k users collude. It is well known that an error correcting code of high minimum distance is a traceability code. When does this ‘error correcting construction’ produce good traceability codes? The paper explores this question. Let ℓ be a fixed positive integer. When q is a sufficiently large prime power, a suitable Reed–Solomon code may be used to construct a 2-traceability code containing codewords. The paper shows that this construction is close to best possible: there exists a constant c, depending only on ℓ, such that a q-ary 2-traceability code of length ℓ contains at most codewords. This answers a question of Kabatiansky from 2005. Barg and Kabatiansky (2004) asked whether there exist families of k-traceability codes of rate bounded away from zero when q and k are constants such that . These parameters are of interest since the error correcting construction cannot be used to construct k-traceability codes of constant rate for these parameters: suitable error correcting codes do not exist when because of the Plotkin bound. Kabatiansky (2004) answered Barg and Kabatiansky''s question (positively) in the case when . This result is generalised to the following: whenever k and q are fixed integers such that and , or such that and , there exist infinite families of q-ary k-traceability codes of constant rate. [Copyright &y& Elsevier]

The efficient computation of the overdamped, random motion of micron and nanometre scale particles in a viscous fluid requires novel methods to obtain the hydrodynamic interactions, random displacements and Brownian drift at minimal cost. Capturing Brownian drift is done most efficiently through a judiciously constructed time-integration scheme that automatically accounts for its contribution to particle motion. In this paper, we present a generalised drift-correcting (gDC) scheme that accounts for Brownian drift for suspensions of rigid particles with arbitrary shape. The scheme seamlessly integrates with fast methods for computing the hydrodynamic interactions and random increments and requires a single full mobility solve per time-step. As a result, the gDC provides increased computational efficiency when used in conjunction with grid-based methods that employ fluctuating hydrodynamics to obtain the random increments. Further, for these methods the additional computations that the scheme requires occur at the level of individual particles, and hence lend themselves naturally to parallel computation. We perform a series of simulations that demonstrate the gDC obtains similar levels of accuracy as compared with the existing state-of-the-art. In addition, these simulations illustrate the gDC's applicability to a wide array of relevant problems involving Brownian suspensions of non-spherical particles, such as the structure of liquid crystals and the rheology of complex fluids. • A new time integration scheme for hydrodynamically interacting rigid particles that resolves Brownian drift. • The rigid particles can have arbitrary shape. • The scheme requires one full mobility solve per time-step. • The scheme naturally interfaces with fast, matrix-free methods for computing hydrodynamic interactions and random increments. • The effectiveness of the scheme is demonstrated through simulations of complex- shaped particle suspensions. [ABSTRACT FROM AUTHOR]

Let R = Z 4 be the integer ring mod 4. A double cyclic code of length ( r , s ) over R is a set that can be partitioned into two parts that any cyclic shift of the coordinates of both parts leaves invariant the code. These codes can be viewed as R [ x ] -submodules of R [ x ] / ( x r − 1 ) × R [ x ] / ( x s − 1 ) . In this paper, we determine the generator polynomials of this family of codes as R [ x ] -submodules of R [ x ] / ( x r − 1 ) × R [ x ] / ( x s − 1 ) . Further, we also give the minimal generating sets of this family of codes as R -submodules of R [ x ] / ( x r − 1 ) × R [ x ] / ( x s − 1 ) . Some optimal or suboptimal nonlinear binary codes are obtained from this family of codes. Finally, we determine the relationship of generators between the double cyclic code and its dual. [ABSTRACT FROM AUTHOR]

Several bounds on the size of ( n + l , M , d , ( m , 0 ) ) q codes in attenuated space over finite fields are provided in this paper. Then, we prove that codes in attenuated space attain the Wang–Xing–Safavi-Naini bound if and only if they are certain Steiner structures. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we investigate linear error correcting codes and projective caps related to the Grassmann embedding of an orthogonal Grassmannian . In particular, we determine some of the parameters of the codes arising from the projective system determined by . We also study special sets of points of which are met by any line of in at most 2 points and we show that their image under the Grassmann embedding is a projective cap. [Copyright &y& Elsevier]

In 1985, Gabidulin introduced the rank metric in coding theory over finite fields, and used this kind of codes in a McEliece cryptosystem, six years later. In this paper, we consider rank metric codes over Galois rings. We propose a suitable metric for codes over such rings, and show its main properties. With this metric, we define Gabidulin codes over Galois rings, propose an efficient decoding algorithm for them, and hint their cryptographic application. [ABSTRACT FROM AUTHOR]

Abstract: The abundant computing resources in current organizations provide new opportunities for executing parallel scientific applications and using resources. The Enterprise Desktop Grid Computing (EDGC) paradigm addresses the potential for harvesting the idle computing resources of an organization’s desktop PCs to support the execution of the company’s large-scale applications. In these environments, the accuracy of response-time predictions is essential for effective metascheduling that maximizes resource usage without harming the performance of the parallel and local applications. However, this accuracy is a major challenge due to the heterogeneity and non-dedicated nature of EDGC resources. In this paper, two new prediction techniques are presented based on the state of resources. A thorough analysis by linear regression demonstrated that the proposed techniques capture the real behavior of the parallel applications better than other common techniques in the literature. Moreover, it is possible to reduce deviations with a proper modeling of prediction errors, and thus, a Self-adjustable Correction method (SAC) for detecting and correcting the prediction deviations was proposed with the ability to adapt to the changes in load conditions. An extensive evaluation in a real environment was conducted to validate the SAC method. The results show that the use of SAC increases the accuracy of response-time predictions by 35%. The cost of predictions with self-correction and its accuracy in a real environment was analyzed using a combination of the proposed techniques. The results demonstrate that the cost of predictions is negligible and the combined use of the prediction techniques is preferable. [Copyright &y& Elsevier]

Abstract: Castle codes are algebraic geometry one-point codes on Castle curves. This family contains some of the most important AG codes among those studied in the literature to date. The minimum distance of these codes can be bounded by using the order-like bound , which is known to be equivalent to the classical order bound when both can be applied. In this paper we compute for some Castle codes, including those related to semigroups generated by two elements and telescopic semigroups. In particular we compute the bound in full for Suzuki codes. [Copyright &y& Elsevier]

Abstract: Additive codes over have been of great interest due to their application to quantum error correction. As another application, we introduce a new class of formally self-dual additive codes over , which is a natural analogue of the binary formally self-dual codes and is missing in the study of additive codes over . In fact, considered formally self-dual linear codes over of even lengths, and suggested classifying formally self-dual linear codes over of odd lengths in order to study lattices from these codes. These motivate our study on formally self-dual additive codes over . In this paper, we define extremal and near-extremal formally self-dual additive codes over , classify all extremal codes, and construct many near-extremal codes. We discuss a general method (called the weak balance principle) for constructing such codes. We conclude with some open problems. [Copyright &y& Elsevier]

Abstract: Due to the potential wide deployment of Radio Frequency Identification (RFID), the security of RFID systems has drawn extensive attention from both academia and industry, and the RFID authentication protocol is an important mechanism in the security of RFID systems. The desired security requirements of RFID authentication protocols include privacy, integrity, authentication, anonymity/untraceability, and even availability. To design an efficient protocol that satisfies all the requirements with limited resources is a challenge. This paper proposes a new RFID authentication protocol based on Error Correction Codes (ECC). The proposed scheme has excellent performance in terms of security, efficiency, server’s maintenance, robustness, and cost. The tag only performs simple operations, such as random number generation and simple bitwise computations. The lightweight feature makes it attractive to those low-cost RFIDs that support only simple operations. [Copyright &y& Elsevier]

Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability [6] in the classical setting. This interest also translates to other metric setting, including the insertion and deletion (insdel for short) setting which is used to model synchronization errors caused by positional information loss in communication systems. Such interest is supported by the construction of a deletion correcting algorithm of insdel Reed-Solomon code in [22] which is based on the Guruswami-Sudan decoding algorithm [6]. Nevertheless, there have been few studies [3] on the insdel error-correcting capability of Reed-Solomon codes. In this paper, we discuss a criterion for a 2-dimensional insdel Reed-Solomon codes to have optimal asymptotic error-correcting capabilities, which are up to their respective lengths. Then we provide explicit constructions of 2-dimensional insdel Reed-Solomon codes that satisfy the established criteria. The family of such constructed codes can then be shown to extend the family of codes with asymptotic error-correcting capability reaching their respective lengths provided in [3, Theorem 2] which provide larger error-correcting capability compared to those defined in [25]. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we construct some algebraic geometric error-correcting codes on surfaces whose Néron–Severi group has low rank. If the Néron–Severi group is generated by an effective divisor, the intersection of this surface with an irreducible surface of lower degree will be an irreducible curve, and this makes possible the construction of codes with good parameters. Such surfaces are not easy to find, but we are able to find surfaces with low rank, and those will give us good codes too. [Copyright &y& Elsevier]

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]

The component-wise or Schur product C ⁎ C ′ of two linear error-correcting codes C and C ′ over certain finite field is the linear code spanned by all component-wise products of a codeword in C with a codeword in C ′. When C = C ′ , we call the product the square of C and denote it C ⁎ 2. Motivated by several applications of squares of linear codes in the area of cryptography, in this paper we study squares of so-called matrix-product codes, a general construction that allows to obtain new longer codes from several "constituent" codes. We show that in many cases we can relate the square of a matrix-product code to the squares and products of their constituent codes, which allow us to give bounds or even determine its minimum distance. We consider the well-known (u , u + v) -construction, or Plotkin sum (which is a special case of a matrix-product code) and determine which parameters we can obtain when the constituent codes are certain cyclic codes. In addition, we use the same techniques to study the squares of other matrix-product codes, for example when the defining matrix is Vandermonde (where the minimum distance is in a certain sense maximal with respect to matrix-product codes). [ABSTRACT FROM AUTHOR]