Abstract: Abstract In this paper, we construct linear codes over \({\mathbb {Z}}_4\) with bounded GC-content. The codes are obtained using a greedy algorithm over \({\mathbb {Z}}_4\) . Further, upper and lower bounds are derived for the maximum size DNA codes of length n with constant GC-content w and edit distance d. PubDate: 2019-03-21
Abstract: Abstract Just by looking at the lengths of irreducible cyclic codes, we present a simple numerical characterization by which we can easily identify those codes that are either one-weight or semiprimitive two-weight irreducible cyclic codes over any finite field. We then particularize our characterization to the class of irreducible cyclic codes of dimension two, and with this, we show that regardless of the finite field any code in this class is always either a one-weight or a semiprimitive two-weight irreducible cyclic code. We also explore the weight distribution of another kind of irreducible cyclic codes and present an infinite family comprising two subfamilies of irreducible cyclic codes that were recently studied. PubDate: 2019-03-15
Abstract: Abstract Codes over commutative Frobenius rings are studied with a focus on local Frobenius rings of order 16 for illustration. The main purpose of this work is to present a method for constructing a generating character for any commutative Frobenius ring. Given such a character, the MacWilliams identities for the complete and symmetrized weight enumerators can be easily found. As examples, generating characters for all commutative local Frobenius rings of order 16 are given. In addition, a canonical generator matrix for codes over local non-chain rings is discussed. The purpose is to show that when working over local non-chain rings, a canonical generator matrix exists but is less than useful which emphases the difficulties in working over such rings. PubDate: 2019-03-07
Abstract: Abstract One of the main problems of coding theory is to construct codes with best possible parameters. Cyclic codes and their various generalizations, such as quasi-twisted codes, have been a fruitful source in achieving this goal. Recently, a new generalization of cyclic codes that are known as skew cyclic codes have been introduced and some new codes obtained from this class. Unlike many other types of codes considered in algebraic coding theory, skew cyclic codes require one to work in a non-commutative ring called skew polynomial ring. In this paper, we present some new linear codes obtained from the class of skew cyclic codes and describe computational challenges in working with this class of codes. PubDate: 2019-03-05
Abstract: Abstract In this paper, we present a refinement of the Cipolla–Lehmer type algorithm given by H. C. Williams in 1972, and later improved by K. S. Williams and K. Hardy in 1993. For a given r-th power residue \(c\in \mathbb {F}_q\) where r is an odd prime, the algorithm of H. C. Williams determines a solution of \(X^r=c\) in \(O(r^3\log q)\) multiplications in \(\mathbb {F}_q\) , and the algorithm of K. S. Williams and K. Hardy finds a solution in \(O(r^4+r^2\log q)\) multiplications in \(\mathbb {F}_q\) . Our refinement finds a solution in \(O(r^3+r^2\log q)\) multiplications in \(\mathbb {F}_q\) . Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SageMath shows a substantial speed-up compared with the existing algorithms. It should be mentioned that our method also works for a composite r. PubDate: 2019-03-01
Abstract: Abstract As a special type of linear codes, minimal linear codes have important applications in secret sharing. Up to now, only a few infinite families of minimal binary linear codes with \(w_{\min }/w_{\max }\le 1/2\) were reported in the literature, while vast knowledge exists on the ones with \(w_{\min }/w_{\max }> 1/2\) . Herein, \(w_{\min }\) and \(w_{\max }\) respectively denote the minimum and maximum nonzero Hamming weights in a linear code. Recently, several classes of linear codes with certain properties were constructed by Zhou et al. from a generic construction. The objective of this paper is to obtain four families of minimal binary linear codes with \(w_{\min }/w_{\max }\le 1/2\) from those linear codes proposed by Zhou et al. The parameters of our minimal linear codes are quite different from known ones. Based on the properties of Krawtchouk polynomials, the weight distributions of all these four families of binary linear codes are established. PubDate: 2019-03-01
Abstract: Abstract Applying the Gram–Schmidt process (also called Gram–Schmidt orthogonalization) to a matrix \(M\in GL(n, {\mathbb {R}})\) , set of \(n\times n\) invertible matrices over the field of real numbers, with the usual inner product gives easily an orthogonal matrix. However, the orthogonality in the vector space \({\mathbb {F}}_{q}^k\) , where \({\mathbb {F}}_{q}\) is a binary finite field, is quite tricky as there are non-zero vectors which are orthogonal to themselves. For this reason the computational variants of Gram–Schmidt orthogonalization can fail. This paper presents an algorithm for constructing random orthogonal matrices over binary finite fields. The approach is inspired from the Gram–Schmidt procedure. Since the inverse of orthogonal matrix is easy to compute, the orthogonal matrices are used to construct a proactive variant of Bloom’s threshold secret sharing scheme. PubDate: 2019-03-01
Abstract: Abstract In their seminar paper, Miyaji, Nakabayashi and Takano introduced the first method to construct families of prime-order elliptic curves with small embedding degrees, namely \(k = 3, 4\) , and 6. These curves, so-called MNT curves, were then extended by Scott and Barreto, and also Galbraith, McKee and Valença to near prime-order curves with the same embedding degrees. In this paper, we extend the method of Scott and Barreto to introduce an explicit and simple algorithm that is able to generate all families of MNT curves with any given cofactor. Furthermore, we analyze the number of potential families of these curves that could be obtained for a given embedding degree k and a cofactor h. We then discuss the generalized Pell equations that allow us to construct particular curves. Finally, we provide statistics of the near prime-order MNT curves. PubDate: 2019-03-01
Abstract: Abstract In the past decades, linear codes with a few weights have been extensively studied for their applications in space communication, data storage and cryptography etc. We construct several classes of binary linear codes and determine their weight distributions. Most of these codes can be used in secret sharing schemes. PubDate: 2019-03-01
Abstract: Abstract Let \(R = {{\mathbb {F}}_q} + {v_1}{{\mathbb {F}}_q} + \cdots + {v_r}{{\mathbb {F}}_q},\) where q is a power of a prime, \(v_i^2=v_i,\; v_iv_j=v_jv_i=0\) for \(1\le i,j \le r\) and \(r\ge 1\) . In this paper, the structure of cyclic codes over the ring R is studied and a Gray map \(\phi \) from \({R^n}\) to \({\mathbb {F}}_q^{(r + 1)n}\) is given. We give a construction of quantum codes from cyclic codes over the ring R. We derive Euclidean dual containing codes over \({\mathbb {F}}_q\) and Hermitian dual containing codes over \({\mathbb {F}}_{p^{2m}}\) as Gray images of cyclic codes over R. In particular, we use \(r+1\) codes associated with a cyclic code over R of arbitrary length to determine the parameters of the corresponding quantum code. Furthermore, some new non-binary quantum codes are obtained. PubDate: 2019-03-01
Abstract: Abstract Let G be a finite group, and S a sum-free subset of G. The set S is locally maximal in G if S is not properly contained in any other sum-free set in G. If S is a locally maximal sum-free set in a finite abelian group G, then \(G=S\cup SS\cup SS^{-1}\cup \sqrt{S}\) , where \(SS=\{xy ~x,y\in S\}\) , \(SS^{-1}=\{xy^{-1} ~x,y\in S\}\) and \(\sqrt{S}=\{x\in G ~x^2\in S\}\) . Each set S in a finite group of odd order satisfies \( \sqrt{S} = S \) . No such result is known for finite abelian groups of even order in general. In view to understanding locally maximal sum-free sets, Bertram asked the following questions: Does S locally maximal sum-free in a finite abelian group imply \( \sqrt{S} \le 2 S \) ' Does there exist a sequence of finite abelian groups G and locally maximal sum-free sets \(S\subset G\) such that \(\frac{ SS }{ S }\rightarrow \infty \) as \( G \rightarrow \infty \) ' Does there exist a sequence of abelian groups G and locally maximal sum-free sets \(S\subset G\) such that \( S <c G ^{\frac{1}{2}}\) as \( G \rightarrow \infty \) , where c is a constant' In this paper, we answer question (i) in the negative, then (ii) and (iii) in affirmative. PubDate: 2019-03-01
Abstract: Abstract Recent research within the field of cryptography has suggested that S-boxes should be chosen to contain few fixed points, motivating analysis of the fixed points of permutations. This paper presents a novel mean of obtaining fixed points for all functions satisfying a property put forth by Carlitz. We determine particular results concerning the fixed points of rational functions. Such concepts allow the derivation of an algorithm which cyclically generates fixed points for all three classes of functions satisfying the Carlitz property, the most renowned of which are Rédei rational functions. Specifically, we present all fixed points for any given Rédei function in a single cycle, generated by a particular non-constant rational transformation. For the other two classes of functions, we present their fixed points in cycles consisting of smaller cycles of fixed points. Finally, we provide an explicit expression for the fixed points of all Rédei functions over \({\mathbb {F}}_q\) . PubDate: 2019-02-06
Abstract: Abstract A classification of extremal double circulant self-dual codes of lengths up to 88 is known. We extend this classification to length 96. We give a classification of extremal double circulant self-dual codes of lengths 90, 92, 94 and 96. We also classify double circulant self-dual codes with parameters [90, 45, 14] and [96, 48, 16]. In addition, we demonstrate that no double circulant self-dual [90, 45, 14] code has an extremal self-dual neighbor, and no double circulant self-dual [96, 48, 16] code has a self-dual neighbor with minimum weight at least 18. PubDate: 2019-02-02
Abstract: Abstract In this paper we prove that all bent functions in the Kerdock code, except for the coset of the symmetric quadratic bent function, are bent–negabent. In this direction, we characterize the set of quadratic bent–negabent functions and show some results connecting quadratic bent–negabent functions and the Kerdock code. Further, we note that there are bent–negabent preserving nonsingular transformations outside the well known class of orthogonal ones that might provide additional functions in the bent–negabent set. This is the first time we could identify non-orthogonal (nonsingular) linear transformations that preserve bent–negabent property for a special subset. PubDate: 2019-01-31
Authors:T. L. Alderson Abstract: Abstract We generalize to higher dimensions the notions of optical orthogonal codes. We establish upper bounds on the capacity of general n-dimensional OOCs, and on ideal codes (codes with zero off-peak autocorrelation). The bounds are based on the Johnson bound, and subsume bounds in the literature. We also present two new constructions of ideal codes; one furnishes an infinite family of optimal codes for each dimension \( n\ge 2 \) , and another which provides an asymptotically optimal family for each dimension \( n\ge 2 \) . The constructions presented are based on certain point-sets in finite projective spaces of dimension k over GF(q) denoted PG(k, q). PubDate: 2019-01-19 DOI: 10.1007/s00200-018-00379-3
Authors:Giorgos Kapetanakis Abstract: Abstract In this note, we employ the techniques of Swan (Pac J Math 12(3):1099–1106, 1962) with the purpose of studying the parity of the number of the irreducible factors of the penatomial \(X^n+X^{3s}+X^{2s}+X^{s}+1\in \mathbb {F}_2[X]\) , where s is even and \(n>3s\) . Our results imply that if \(n \not \equiv \pm 1 \pmod {8}\) , then the polynomial in question is reducible. PubDate: 2019-01-02 DOI: 10.1007/s00200-018-0378-7
Authors:Sayaka Ishizuki; Michio Oyamaguchi; Masahiko Sakai Abstract: Abstract This paper presents a counterexample for the open conjecture whether innermost joinability of all critical pairs ensures confluence of innermost terminating term rewriting systems. We then show that innermost joinability of all normalized instances of the critical pairs is a necessary and sufficient condition. Using this condition, we give a decidable sufficient condition for confluence of innermost terminating systems. Finally, we enrich the condition by introducing the notion of left-stable rules. As a corollary, confluence of innermost terminating left-weakly-shallow TRSs is shown to be decidable. PubDate: 2019-01-02 DOI: 10.1007/s00200-018-0377-8
Authors:Krzysztof Ziemiański Abstract: Abstract Let K be an arbitrary semi-cubical set that can be embedded in a standard cube. Using Discrete Morse Theory, we construct a CW-complex that is homotopy equivalent to the space \(\vec {P}(K)_v^w\) of directed paths between two given vertices v, w of K. In many cases, this construction is minimal: the cells of the constructed CW-complex are in 1–1 correspondence with the generators of the homology of \(\vec {P}(K)_v^w\) . PubDate: 2018-05-23 DOI: 10.1007/s00200-018-0360-4
Authors:Joris van der Hoeven Abstract: Abstract In this paper, we will present several algorithms for computing with D-algebraic power series. Such power series are specified by one or more algebraic differential equations and a sufficient number of initial conditions. The emphasis is not on the efficient computation of coefficients of such power series (various techniques are known for that), but rather on the ability to decide whether expressions involving D-algebraic power series are zero. We will both consider univariate and multivariate series and, besides the usual ring operations and differentiation, we will also consider composition, implicitly determined power series and monomial transformations. PubDate: 2018-05-03 DOI: 10.1007/s00200-018-0358-y
Authors:Shanding Xu; Xiwang Cao; Guangkui Xu; Chunming Tang Abstract: Abstract Direct-sequence spread spectrum and frequency-hopping (FH) spread spectrum are two main spread-coding technologies. Frequency-hopping sequences (FHSs) achieving the well-known Lempel–Greenberger bound play an important part in FH code-division multiple-access systems. Our objective is to construct more FHSs with new parameters attaining the above bound. In this paper, two classes of FHSs are proposed by means of two partitions of \({{\mathbb {Z}}_{v}}\) , where v is an odd positive integer. It is shown that all the constructed FHSs are optimal with respect to the Lempel–Greenberger bound. By choosing appropriate injective functions, infinitely many optimal FHSs can be recursively obtained. Above all, these FHSs have new parameters which are not covered in the former literature. PubDate: 2018-04-13 DOI: 10.1007/s00200-018-0356-0
Hybrid journal (It can contain Open Access articles)
[2626 journals]
