Search

An $(r, \delta)$ -locally repairable code ($(r, \delta)$ -LRC for short) was introduced by Prakash et al. for tolerating multiple failed nodes in distributed storage systems, which was a generalization of the concept of $r$ -LRCs produced by Gopalan et al.. An $(r, \delta)$ -LRC is said to be optimal if it achieves the Singleton-like bound. Recently, Chen et al. generalized the construction of cyclic $r$ -LRCs proposed by Tamo et al. , and constructed several classes of optimal $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively in terms of a union of the set of zeros controlling the minimum distance and the set of zeros ensuring the locality. Following the work of , , this paper first characterizes $(r, \delta)$ -locality of a cyclic code via its zeros. Then we construct several classes of optimal cyclic $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively from the product of two sets of zeros. Our constructions include all optimal cyclic $(r,\delta)$ -LRCs proposed in , , and our method seems more convenient to obtain optimal cyclic $(r, \delta)$ -LRCs with flexible parameters. Moreover, many optimal cyclic $(r,\delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively with $(r+\delta -1)\nmid n$ can be obtained from our method. [ABSTRACT FROM AUTHOR]

Consider several source nodes communicating across a wireless network to a destination node with the help of several layers of relay nodes. Recent work by Avestimehr has approximated the capacity of this network up to an additive gap. The communication scheme achieving this capacity approximation is based on compress-and-forward, resulting in noise accumulation as the messages traverse the network. As a consequence, the approximation gap increases linearly with the network depth. This paper develops a computation alignment strategy that can approach the capacity of a class of layered, time-varying wireless relay networks up to an approximation gap that is independent of the network depth. This strategy is based on the compute-and-forward framework, which enables relays to decode deterministic functions of the transmitted messages. Alone, compute-and-forward is insufficient to approach the capacity as it incurs a penalty for approximating the wireless channel with complex-valued coefficients by a channel with integer coefficients. Here, this penalty is circumvented by carefully matching channel realizations across time slots to create integer-valued effective channels that are well suited to compute-and-forward. Unlike prior constant gap results, the approximation gap obtained in this paper also depends closely on the fading statistics, which are assumed to be i.i.d. Rayleigh. [ABSTRACT FROM PUBLISHER]

This paper studies the multiple-access channel (MAC) with rate-limited feedback. The channel output is encoded into one stream of bits, which is provided causally to the two users at the channel input. An achievable rate region for this setup is derived, based on superposition of information, block Markov coding, and coding with various degrees of side information for the feedback link. The suggested region coincides with the Cover–Leung inner bound for large feedback rates. The result is then extended for cases where there is only a feedback link to one of the transmitters, and for a more general case where there are two separate feedback links to both transmitters. We compute achievable regions for the Gaussian MAC and for the binary erasure MAC. The Gaussian region is computed for the case of common rate-limited feedback, whereas the region for the binary erasure MAC is computed for one-sided feedback. It is known that for the latter, the Cover–Leung region is tight, and we obtain results that coincide with the feedback capacity region for high feedback rates. [ABSTRACT FROM PUBLISHER]

This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters $(n,k,d,r,\delta )$ of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by Gopalan et al. for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters $(n,k,d,r,\delta )$ and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by Song et al. [ABSTRACT FROM AUTHOR]

Algebraic topology studies topological spaces with the help of tools from abstract algebra. The main focus of this paper is to show that many concepts from algebraic topology can be conveniently expressed in terms of (normal) factor graphs. As an application, we give an alternative proof of a classical duality result of Kramers and Wannier, which expresses the partition function of the 2-D Ising model at a low temperature in terms of the partition function of the 2-D Ising model at a high temperature. Moreover, we discuss analogous results for the 3-D Ising model and the Potts model. [ABSTRACT FROM AUTHOR]

The state-dependent point-to-point Gaussian channel with a helper is first studied, in which a transmitter communicates with a receiver via a state-corrupted channel. The state is not known to the transmitter nor to the receiver, but known to a helper noncausally, which then wishes to assist the receiver to cancel the state. Differently from the previous work that characterized the capacity only in the infinite state power regime, this paper explores the general case with arbitrary state power. A lower bound on the capacity is derived based on an achievable scheme that integrates direct state subtraction and single-bin dirty paper coding. By analyzing this lower bound and further comparing it with the existing upper bounds, the capacity of the channel is characterized for a wide range of channel parameters. Such an idea of characterizing the capacity is further extended to study the two-user state-dependent multiple access channel with a helper. By comparing the derived inner and outer bounds, the channel parameters are partitioned into appropriate cases, and for each case, either segments on the capacity region boundary or the full capacity region are characterized. [ABSTRACT FROM PUBLISHER]

Maximum distance profile codes over finite non-binary fields have been introduced and thoroughly studied in the last decade. These codes have the property that their column distances are maximal among all codes of the same rate and degree. In this paper, we aim at studying this fundamental concept in the context of convolutional codes over a finite ring. We extensively use the concept of $p$ -encoder to establish the theoretical framework and derive several bounds on the column distances. In particular, a method for constructing (not necessarily free) maximum distance profile convolutional codes over ${\mathbb Z}_{p^{r}}$ is presented. [ABSTRACT FROM AUTHOR]

Linear codes with certain special properties have received renewed attention in recent years due to their practical applications. Among them, binary linear complementary dual (LCD) codes play an important role in implementations against side-channel attacks and fault injection attacks. Self-orthogonal codes can be used to construct quantum codes. In this paper, four classes of binary linear codes are constructed via a generic construction which has been intensively investigated in the past decade. Simple characterizations of these linear codes to be LCD or self-orthogonal are presented. Resultantly, infinite families of binary LCD codes and self-orthogonal codes are obtained. Infinite families of binary LCD codes from the duals of these four classes of linear codes are produced. Many LCD codes and self-orthogonal codes obtained in this paper are optimal or almost optimal in the sense that they meet certain bounds on general linear codes. In addition, the weight distributions of two sub-families of the proposed linear codes are established in terms of Krawtchouk polynomials. [ABSTRACT FROM AUTHOR]

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (first) part of this paper introduces the mathematical framework that we will use in the second part to characterize the polarizing operations. We define uniformity preserving, irreducible, ergodic, and strongly ergodic operations, and we study their properties. The concepts of a stable partition and the residue of a stable partition are introduced. We show that an ergodic operation is strongly ergodic if and only if all its stable partitions are their own residues. We also study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic. In the second part of this paper, we provide a foundation of polarization theory based on the ergodic theory of binary operations that we develop in this part. [ABSTRACT FROM PUBLISHER]

Tang and Ding [IEEE IT 67 (2021) 244-254] studied the class of BCH codes $\mathcal {C}_{(q,q+1,4,1)}$ and their dual codes with $q=2^{m}$ and established that the codewords of the minimum (or the second minimum) weight in these codes support 4-designs or 3-designs. Motivated by this, we further investigate the codewords of the next adjacent weight in such codes and discover more infinite classes of $t$ -designs with $t=3,4$. In particular, we prove that codewords of weight 7 in $\mathcal {C}_{(q,q+1,4,1)}$ support 4-designs for odd $m \geqslant 5$ and they support 3-designs for even $m \geqslant 4$ , which provide infinite classes of simple $t$ -designs with new parameters. Another significant class of $t$ -designs we produce in this paper has complementary designs with parameters 4- $(2^{2s+1}+ 1,5,5)$ ; these designs have the smallest index among all the known simple 4- $(q+1,5,\lambda)$ designs derived from codes for prime powers $q$ ; and they are further proved to be isomorphic to the 4-designs admitting the projective general linear group PGL $(2,2^{2s+1})$ as the automorphism group constructed by Alltop in 1969. [ABSTRACT FROM AUTHOR]

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

A function computation problem over a directed acyclic network has been considered in the literature, where a sink node is required to compute a target function correctly with the inputs arbitrarily generated at multiple source nodes. The network links are error free but capacity limited, and the intermediate nodes perform network coding. The computing rate of a network code is the average number of times that the target function is computed for one use of the network, i.e., each link in the network is used at most once. In the existing papers, two cut-set bounds were proposed on the computing rate. However, we in this paper show that these bounds are not valid for general network function computation problems. We analyze the reason of the invalidity and propose a general cut-set bound by using a new equivalence relation associated with the inputs of the target function. Moreover, some results in the existing papers were proved by applying the invalid upper bound. We also justify the validity of these results. [ABSTRACT FROM AUTHOR]

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over \mathrm GF(q) with length n=(q^m-1)/(q-1) . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n=(3^{m}-1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated. [ABSTRACT FROM PUBLISHER]

It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper. [ABSTRACT FROM AUTHOR]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

The binary quadratic-residue codes and the punctured Reed-Muller codes ${\mathcal {R}}_{2}((m-1)/2, m))$ are two families of binary cyclic codes with parameters $[n, (n+1)/2, d \geq \sqrt {n}]$. These two families of binary cyclic codes are interesting partly due to the fact that their minimum distances have a square-root bound. The objective of this paper is to construct two families of binary cyclic codes of length $2^{m}-1$ and dimension near $2^{m-1}$ with good minimum distances. When $m \geq 3$ is odd, the codes become a family of duadic codes with parameters $[2^{m}-1, 2^{m-1}, d]$ , where $d \geq 2^{(m-1)/2}+1$ if $m \equiv 3 \pmod {4}$ and $d \geq 2^{(m-1)/2}+3$ if $m \equiv 1 \pmod {4}$. The two families of binary cyclic codes contain some optimal binary cyclic codes. [ABSTRACT FROM AUTHOR]

High peak values of transmission signals in wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made by Boche and Farell toward the understanding of peak value reduction, using the strategy known as tone reservation for orthogonal transmission schemes. There it was shown that for orthogonal frequency-division multiplexing (OFDM) systems, the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method. In this paper, we show that the combinatorial object introduced as perfect Walsh sum (PWS) plays a similar role for code-division multiple access (CDMA) systems as arithmetic progression for OFDM systems. By specific construction, we show that for a chosen numbers $m$ and $n$ , all subsets $\mathcal {I} $ of the set $[N]$ of the first $N=2^{n}$ natural numbers, which has the density in $[N]$ larger than a given $\delta \in (0,1)$ , i.e., $\left |{ \mathcal {I} }\right |/N\geq \delta $ , and which is sufficiently large enough, in the sense that $\left |{ I }\right |\geq 2(2/\delta)^{2^{m}-1}$ , contains a PWS of size $2^{m}$. By means of this result, and motivated by the previously mentioned connection between arithmetic progression and PWS, we show results for the PWS which are analogous to the famous Szemerédi theorem on arithmetic progressions, Conlon-Gower’s theorem on probabilistic construction of “sparse” sets containing an arithmetic progression, and even a solution of an analogon to the Erdős’ conjecture on arithmetic progressions. Those results give in particular an insight into the asymptotic limitations of tone reservation method for the CDMA systems. Besides, we show that a subset $I$ of $[N]$ is a PWS if and only if the embedding inequality of the subspace of $L^{1}([{0,1}])$ , containing linear combinations of Walsh functions indexed by elements of $\mathcal {I} $ , holds with the minimum possible embedding constant $\sqrt { \left |{ \mathcal {I} }\right |}$. The corresponding approach based in particular by the fact that the PWSs are the only Walsh sums having unit $L^{1}$ -norm, proven in this paper. By means of that results, we show that the minimum possible threshold constant for which the tone reservation method is applicable yields $\sqrt { \left |{ \mathcal {I} }\right |}$ if and only if the information set $\mathcal {I} $ is a PWS. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) codes are very important in both theory and practice. There is a classical construction of a family of $[{2^{m}+1, 2u-1, 2^{m}-2u+3}]$ MDS codes for $1 \leq u \leq 2^{m-1}$ , which are cyclic, reversible and BCH codes over ${\mathrm {GF}}(2^{m})$. The objective of this paper is to study the quaternary subfield subcodes and quaternary subfield codes of a subfamily of the MDS codes for even $m$. A family of quaternary cyclic codes is obtained. These quaternary codes are distance-optimal in some cases and very good in general. Furthermore, two infinite families of 3-designs from these quaternary codes and their duals are presented. [ABSTRACT FROM AUTHOR]

Let $n$ be a positive integer and $p$ a prime. The power mapping $x^{p^{n}-3}$ over ${\mathbb {F}}_{p^{n}}$ has desirable differential properties, and its differential spectra for $p=2,\,3$ have been determined. In this paper, for any odd prime $p$ , by investigating certain quadratic character sums and some equations over ${\mathbb {F}}_{p^{n}}$ , we determine the differential spectrum of $x^{p^{n}-3}$ with a unified approach. The obtained result shows that for any given odd prime $p$ , the differential spectrum can be expressed explicitly in terms of $n$. Compared with previous results, a special elliptic curve over ${\mathbb {F}}_{p}$ plays an important role in our computation for the general case $p \ge 5$. [ABSTRACT FROM AUTHOR]

A k-plex of order n is an ${n} \times {n}$ matrix on n symbols, where every row contains k distinct symbols, every column contains k distinct symbols, and every symbol occurs exactly k times. Yi et al. (2019) introduced 3-plex codes which are 2-erasure codes (2-erasure tolerant array codes) derived from 3-plexes. In this paper, we generalize 3-plex codes to k-plex codes. We introduce the notion of a “strong” k-plex which implies the derived k-plex code is 2-erasure tolerant. Moreover, k-plex codes derived from strong $k$ -plexes have a straightforward algorithm for reconstruction. These general k-plex codes offer greater flexibility when choosing a suitable code for a storage system, enabling the operator to better optimize the unavoidable trade-offs involved. Blackburn asked for the maximum number of entries in an ${n} \times {n}$ partial Latin square on n symbols in which if distinct cells $({i},{j})$ and $({i}',{j}')$ contain the same symbol, then the cells $({i}',{j})$ and $({i},{j}')$ are empty. A “strong” k-plex satisfies the Blackburn property (along with two other properties related to erasure coding). We investigate the necessary conditions for the existence of Blackburn k-plexes (and hence necessary conditions for the existence of strong k-plexes). We show that any Blackburn k-plex has order ${n} \geq \lceil (\sqrt {2}+1){k}-2 \rceil $. We describe how to construct strong k-plexes of order n when $k \in \{2,3,4,5\}$ for all possible orders n, and we give a simple construction of strong k-plexes of order ${k}^{2}$ for $k \geq 2$. [ABSTRACT FROM AUTHOR]

Boolean functions, coding theory and $t$ -designs have close connections and interesting interplay. A standard approach to constructing $t$ -designs is the use of linear codes with certain regularity. The Assmus-Mattson Theorem and the automorphism groups are two ways for proving that a code has sufficient regularity for supporting $t$ -designs. However, some linear codes hold $t$ -designs, although they do not satisfy the conditions in the Assmus-Mattson Theorem and do not admit a $t$ -transitive or $t$ -homogeneous group as a subgroup of their automorphisms. The major objective of this paper is to develop a theory for explaining such codes and obtaining such new codes and hence new $t$ -designs. To this end, a general theory for punctured and shortened codes of linear codes supporting $t$ -designs is established, a generalized Assmus-Mattson theorem is developed, and a link between 2-designs and differentially $\delta $ -uniform functions and 2-designs is built. With these general results, binary codes with new parameters and explicit weight distributions are obtained, new 2-designs and Steiner system $S(2, 4, 2^{n})$ are produced in this paper. [ABSTRACT FROM AUTHOR]

In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results. [ABSTRACT FROM AUTHOR]

Following the very recent studies on \mathbb Z2\mathbb Z4 -additive codes, \mathbb Z2\mathbb Z2[u] -linear codes have been introduced by Aydogdu et al. In this paper, we introduce and study the algebraic structure of cyclic, constacyclic codes and their duals over the R -module \mathbb {Z}_{2}^\alpha R^\beta where R=\mathbb {Z}_{2}+u\mathbb {Z}_{2}=\left \{{0,1,u,u+1}\right \} is the ring with four elements and u^2=0 . We determine the generating independent sets and the types and sizes of both such codes and their duals. Finally, we present a bound and an optimal family of codes attaining this bound and also give some illustrative examples of binary codes that have good parameters which are obtained from the cyclic codes in \mathbb Z_2^\alpha R^\beta . [ABSTRACT FROM AUTHOR]

In this paper, we make use of channel symmetry properties to determine the capacity region of three types of two-way networks: 1) two-user memoryless two-way channels (TWCs); 2) two-user TWCs with memory; and 3) three-user multiaccess/degraded broadcast (MA/DB) TWCs. For each network, symmetry conditions under which a Shannon-type random coding inner bound (under independent non-adaptive inputs) is tight are given. For two-user memoryless TWCs, prior results are substantially generalized by viewing a TWC as two interacting state-dependent one-way channels. The capacity of symmetric TWCs with memory, whose outputs are functions of the inputs and independent stationary and ergodic noise processes, is also obtained. Moreover, various channel symmetry properties under which the Shannon-type inner bound is tight are identified for three-user MA/DB TWCs. The results not only enlarge the class of symmetric TWCs whose capacity region can be exactly determined but also imply that interactive adaptive coding, not improving capacity, is unnecessary for such channels. [ABSTRACT FROM AUTHOR]

The $q^{t} \times (q+1)t$ ordered orthogonal arrays (OOAs) of strength $t$ over the alphabet $ \mathbb {F}_{q}$ were constructed using linear feedback shift register sequences (LFSRs) defined by primitive polynomials in $ \mathbb {F}_{q}[x]$. In this paper, we extend this result to all polynomials in $\mathbb {F}_{q}[x]$ which satisfy some fairly simple restrictions, i.e., the restrictions that are automatically satisfied by primitive polynomials. While these restrictions sometimes reduce the number of columns produced from $(q+1)t$ to a smaller multiple of $t$ , in many cases, we still obtain the maximum number of columns in the constructed OOA when using non-primitive polynomials. For $2 \le q \le 9$ and small $t$ , we generate OOAs in this manner for all permissible polynomials of degree $t$ in $ \mathbb {F}_{q}[x]$ and compare the results to the ones produced in , , and showing how close the arrays are to being “full” orthogonal arrays. Unusually for the finite fields, our arrays based on the non-primitive irreducible and even reducible polynomials are closer to the orthogonal arrays than those built from the primitive polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we generalize constructions in two recent works of Ding, Heng, and Zhou to any field $\mathbb {F}_{{q}}$ , ${q}$ odd, providing infinite families of minimal codes for which the Ashikhmin–Barg bound does not hold. [ABSTRACT FROM AUTHOR]

In frequency hopping (FH) communication systems, frequency hopping sequences (FHSs) are crucial in determining the system’s anti-jamming performance. If FHSs can ensure a wide-gap between two adjacent frequency points to avoid the frequency points with high interference probability, it will significantly improve the FH communication system’s anti-interference ability. Moreover, if each frequency point appears at the same number of times in a sequence period, the system’s anti-electromagnetic interference will be enhanced. Therefore, it is desirable to employ FHSs with low Hamming autocorrelation, wide frequency-hopping gap, and good uniformity in practical applications. However, to the best of our knowledge, no such infinite classes of FHSs have been reported in the literature to date. This paper aims to present two constructions of uniform wide-gap frequency-hopping sequences (WGFHSs) by concatenating two or three adequately designed sequences. For the first time, we obtain two infinite classes of WGFHSs, which are optimal with respect to the well-known Lempel-Greenberger bound. [ABSTRACT FROM AUTHOR]

This paper considers “ $\delta $ -almost Reed–Muller codes”, i.e., linear codes spanned by evaluations of all but a $\delta $ fraction of monomials of degree at most $d$. It is shown that for any $\delta > 0$ and any $\varepsilon >0$ , there exists a family of $\delta $ -almost Reed–Muller codes of constant rate that correct $1/2- \varepsilon $ fraction of random errors with high probability. For exact Reed–Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed–Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC ’15). Our proof is based on the recent polarization result for Reed–Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed–Muller code entropies. [ABSTRACT FROM AUTHOR]

The expansion complexity is a new figure of merit for cryptographic sequences. In this paper, we present an explicit formula of the (irreducible) expansion complexity of ultimately periodic sequences over finite fields. We also provide improved upper and lower bounds on the $N$ th irreducible expansion complexity when they are not explicitly determined. In addition, for some infinite sequences with given nonlinear complexity, a tighter upper bound of their $N$ th expansion complexity is given. [ABSTRACT FROM AUTHOR]

In this paper, a generic construction of codebooks based on binary codes is introduced. With this generic construction, a few previous constructions of optimal codebooks are extended, and a new class of codebooks almost meeting the Levenshtein bound is presented. Exponentially many codebooks meeting or almost meeting the Levenshtein bound from binary codes are obtained in this paper. The codebooks constructed in this paper have alphabet size 4. As a byproduct, three bounds on the parameters of binary codes are derived. [ABSTRACT FROM PUBLISHER]

An error model with asymmetric single error with magnitude four is considered. In this paper, the constructions of codes correcting single error of magnitude four over $\mathbb {Z}_{2^{{a}}3^{{b}}{r}}$ are studied which is equivalent to construct $B_{1}[{4}](2^{{a}}3^{{b}}{r})$ sets. Firstly, we reduce the construction of a maximal size ${B}_{1}[{4}](2^{{a}}3^{{b}}{r})$ set for ${a}\geq 4$ and $ \gcd ({r},6)=1$ to the construction of a maximal size ${B}_{1}[{4}](2^{{a}-3}3^{{b}}{r})$ set. Furthermore, we will show that maximal size ${B}_{1}[{4}](8\cdot 3^{{b}}{r})$ sets can be reduced to maximal size ${B}_{1}[{4}](3^{{b}}{r})$ sets and also give lower bounds of maximal size ${B}_{1}[{4}](12{r})$ and ${B}_{1}[{4}](2\cdot 3^{{b}}{r})$ sets. Finally, we give a necessary and sufficient condition on the existence of perfect ${B}_{1}[{4}]({p})$ set for prime $p$. [ABSTRACT FROM AUTHOR]

In this paper, we provide two complementary results for cyclic codes of composite length. First, we give a general construction of cyclic codes of length nr from cyclic codes of length n and a lower bound on the minimum distance. Numerical data show that many cyclic codes of composite length with the best parameters can be obtained in this way. Second, in the other direction, we show that for cyclic codes of length n with a primitive n-th root of unity as a non-zero, the minimum distance is roughly bounded by the square-free part of n. This means that we shall not expect good cyclic codes of length n in general if, for example, the length n is divisible by a high power of a prime. [ABSTRACT FROM AUTHOR]

Linear complementary-dual (LCD for short) codes are linear codes that intersect with their duals trivially. LCD codes have been used in certain communication systems. It is recently found that LCD codes can be applied in cryptography. This application of LCD codes renewed the interest in the construction of LCD codes having a large minimum distance. Maximum distance separable (MDS) codes are optimal in the sense that the minimum distance cannot be improved for given length and code size. Constructing LCD MDS codes is thus of significance in theory and practice. Recently, Jin constructed several classes of LCD MDS codes through generalized Reed-Solomon codes. In this paper, a different approach is proposed to obtain new LCD MDS codes from generalized Reed-Solomon codes. Consequently, new code constructions are provided and certain previously known results by Jin are extended. [ABSTRACT FROM AUTHOR]

In the literature, all the known high-rate MDS codes with the optimal repair bandwidth possess a significantly large sub-packetization level, which may prevent the codes to be implemented in practical systems. To build MDS codes with small sub-packetization level, existing constructions and theoretical bounds imply that one may sacrifice the optimality of the repair bandwidth. Partly motivated by the work of Tamo et al. (IEEE Trans. Inform. Theory, 59(3), 1597–1616, 2013), in this paper, we present a transformation that can greatly reduce the sub-packetization level of MDS codes with the optimal repair bandwidth with respect to the same code length n. As applications of the transformation, four high-rate MDS codes having both small sub-packetization level and near-optimal repair bandwidth can be obtained, where three of them are explicit and the required field sizes are around or even smaller than the code length ${n}$. Additionally, we propose another explicit MDS code which has a similar structure as that of the first resultant code obtained by the generic transformation, but can be built on a smaller finite field. [ABSTRACT FROM AUTHOR]

We study a class of real robust phase retrieval problems under a Gaussian assumption on the coding matrix when the received signal is sparsely corrupted by noise. The goal is to establish conditions on the sparsity under which the input vector can be exactly recovered. The recovery problem is formulated as residual minimization in the $\ell _{1}$ -norm. The main contribution is a robust phase retrieval counterpart to the seminal paper by Candes and Tao on compressed sensing ($\ell _{1}$ regression) [Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005]. The analysis depends on a key new property of the coding matrix called the Absolute Range Property (ARP) which is the analogue to the Null Space Property (NSP) in compressed sensing. When the residuals are computed using squared magnitudes, we show that ARP follows from a standard Restricted Isometry Property (RIP). However, when the residuals are computed using absolute magnitudes, a different kind of RIP or growth property is required. We conclude by showing that the robust phase retrieval objectives are sharp with respect to their minimizers with high probability. [ABSTRACT FROM AUTHOR]

A network of three nodes mutually communicating with each other is studied. This multi-way network is a suitable model for three-user device-to-device communications. The main goal of this paper is to characterize the capacity region of the underlying Gaussian three-way channel (3WC) within a constant gap. To this end, a capacity outer bound is derived using cut-set bounds and genie-aided bounds. For achievability, the 3WC is first transformed into an equivalent star channel. This latter is then decomposed into a set of “successive” sub-channels, leading to a sub-channel allocation problem. Using backward decoding, interference neutralization, and known results on the capacity of the star-channel relying of physical-layer network coding, an achievable rate region for the 3WC is obtained. It is then shown that the achievable rate region is within a constant gap of the developed outer bound, leading to the desired capacity approximation. Interestingly, in contrast to the Gaussian two-way channel (TWC), adaptation is necessary in the 3WC. Furthermore, message splitting is another ingredient of the developed scheme for the 3WC, which is not required in the TWC. The two setups are, however, similar in terms of their sum-capacity pre-log, which is equal to 2. Finally, some interesting networks and their approximate capacities are recovered as special cases of the 3WC, such as the cooperative broadcast channel and multiple access channel. [ABSTRACT FROM PUBLISHER]

In this paper, a new construction of zero-difference balanced functions defined on \BBZv is given, where v is an odd positive integer. Based on the generic constructions proposed by Ding, optimal constant composition codes and perfect difference systems of sets with new parameters can be generated from the zero-difference balanced functions constructed in this paper. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over ${\mathbb F}_{2^{9}}$ and includes an example of another APN function $x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$ over ${\mathbb F}_{2^{8}}$ , known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions. [ABSTRACT FROM AUTHOR]

In Eurocrypt’18, Cid et al. proposed a new cryptanalysis tool called Boomerang Connectivity Table (BCT), to evaluate S-boxes of block ciphers. Later, Boura and Canteaut further investigated the new parameter Boomerang uniformity for cryptographic S-boxes. It is of great interest to find new S-boxes with low Boomerang uniformity for even dimensions. In this paper, we prove that a class of permutation quadrinomials over $\mathbb {F}_{2^{2m}}$ with $m$ odd has Boomerang uniformity four, which gives the fifth class of such kind of permutation polynomials. Further, the occurrences of 0 and 4 in the BCTs of the investigated permutation polynomials are also completely determined. [ABSTRACT FROM AUTHOR]

In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out that the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length $ {n} > {q}+1$ are also obtained. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. There are several methods to construct linear codes, one of which is based on functions over finite fields. Recently, many construction methods for linear codes from functions have been proposed in the literature. In this paper, we generalize the recent construction methods given by Tang et al. in [IEEE Transactions on Information Theory, 62(3), 1166-1176, 2016] to weakly regular plateaued functions over finite fields of odd characteristic. We first construct three-weight linear codes from weakly regular plateaued functions based on the second generic construction and then determine their weight distributions. We also give a punctured version and subcode of each constructed code. We note that they may be (almost) optimal codes and can be directly employed to obtain (democratic) secret sharing schemes, which have diverse applications in the industry. We next observe that the constructed codes are minimal for almost all cases and finally describe the access structures of the secret sharing schemes based on their dual codes. [ABSTRACT FROM AUTHOR]

This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and nonadditive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5, 6, 2)) code found by Rains et al. It also extends to operator quantum error correcting codes. [ABSTRACT FROM AUTHOR]

This paper compares the power divergence statistics of orders α > 1 with the information divergence statistic in the problem of testing the uniformity of a distribution. In this problem, the information divergence statistic is equivalent to the entropy statistic. Extending some previously established results about information diagrams, it is proved that the information divergence statistic in this problem is more efficient in the Bahadur sense than any power divergence statistic of order α > 1. This means that the entropy provides in this sense the most efficient way of characterizing the uniformity of a distribution. [ABSTRACT FROM AUTHOR]

Permutation and multipermutation codes in the Ulam metric have been suggested for use in non-volatile memory storage systems such as flash memory devices. In this paper we introduce a new method to calculate permutation ball sizes in the Ulam metric using Young Tableaux and prove the non-existence of non-trivial perfect permutation codes in the Ulam metric. We then extend the study to multipermutations, providing upper and lower bounds on multipermutation Ulam ball sizes and resulting upper and lower bounds on the maximal size of multipermutation codes in the Ulam metric. [ABSTRACT FROM AUTHOR]

An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications, such as cryptography and coding theory. Following the idea by Wang to characterize the involutory behavior of the generalized cyclotomic mappings, this paper gives a more concise criterion for $x^{r}h(x^{s})\in {\mathbb F} _{q}[x]$ being involutions over the finite field ${\mathbb F}_{q}$ , where $r\geq 1$ and $s\,|\, (q-1)$. By using this criterion, we propose a general method to construct involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ from given involutions over some subgroups of ${\mathbb F}_{q}^{*}$ by solving congruent and linear equations over finite fields. Then, many classes of explicit involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ are obtained. [ABSTRACT FROM AUTHOR]

Recently, Gallager's bounding techniques have been used to derive tight performance bounds for coded systems in fading channels. Most works in this field have thus far dealt with coherent decoding. This paper develops Gallager bounds for noncoherent systems in fading channels. Unlike coherent decoding, the exact error probability of a noncoherent decoder/detector conditioned on the fading coefficients does not admit a closed-form expression. This difficulty is overcome in this paper by employing the Chernoff technique. Although it weakens the bounds to some extent, the Chernoff technique enables the derivations of the limit-before-average (LBA) bound and Gallager bounds in closed form for noncoherent fading channels. Numerical examples show that the proposed bounds are convergent and are tighter than the conventional union bound. [ABSTRACT FROM AUTHOR]

In multiple-input multiple-output (MIMO) multi- user detection theory, the QR decomposition of the channel matrix H can be used to form the back-cancellation detector. In this paper, we propose an optimal QR decomposition, which we call the equal-diagonal QR decomposition, or briefly the QRS decomposition. We apply the decomposition to precoded successive-cancellation detection, where we assume that both the transmitter and the receiver have perfect channel knowledge. We show that, for any channel matrix H, there exists a unitary precoder matrix S, such that HS = QR, where the nonzero diagonal entries of the upper triangular matrix H in the QR decomposition of HR are all equal to each other. The precoder and the resulting successive-cancellation detector have the following properties. a) The minimum Euclidean distance between two signal points at the channel output is equal to the minimum Euclidean distance between two constellation points at the precoder input up to a multiplicative factor that equals the diagonal entry in the R-factor. b) The superchannel HS naturally exhibits an optimally ordered column permutation, i.e., the optimal detection order for the vertical Bell Labs layered space-time (V-BLAST) detector is the natural order. c) The precoder S minimizes the block error probability of the QR successive cancellation detector. d) A lower and an upper bound for the free distance at the channel output is expressible in terms Of the diagonal entries of the H-factor in the QR decomposition of a channel matrix. e) The precoder S maximizes, the lower bound of the channel's free distance subject to a power constraint. 1) For the optimal precoder 5, the performance of the QR detector is asymptotically (at large signal-to-noise ratios (SNRs)) equivalent to that of the maximum-likelihood detector (MLD) that uses the same precoder. Further, in this paper we consider two multiplexing schemes: time-division multiple access (TDMA) and orthogonal frequency-division multiplexing (OFDM). We design the optimal precoder for binary phase-shift keying (BPSK) with these multiplexing schemes, but outline the procedure to extend' the method to nonbinary schemes such as pulse amplitude modulation (PAM), phase-shift keying (PSK), and quadrature amplitude modulation (QAM). Finally, examples are given that illustrate the performance of the precoder and the corresponding successive cancellation detector. [ABSTRACT FROM AUTHOR]

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros. [ABSTRACT FROM PUBLISHER]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]