Search

Constructing locally repairable codes achieving Singleton-type bound (we call them optimal codes in this paper) is a challenging task and has attracted great attention in the last few years. Tamo and Barg first gave a breakthrough result in this topic by cleverly considering subcodes of Reed-Solomon codes. Thus, $q$ -ary optimal locally repairable codes from subcodes of Reed-Solomon codes given by Tamo and Barg have length upper bounded by $q$. Recently, it was shown through extension of construction by Tamo and Barg that length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al.. Surprisingly it was shown by Barg et al. that, unlike classical MDS codes, $q$ -ary optimal locally repairable codes could have length bigger than $q+1$. Thus, it becomes an interesting and challenging problem to construct $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we make use of rich algebraic structures of elliptic curves to construct a family of $q$ -ary optimal locally repairable codes of length up to $q+2\sqrt {q}$. It turns out that locality of our codes can be as big as 23 and distance can be linear in length. [ABSTRACT FROM AUTHOR]

Using some recent results on asymptotically equivalent sequences of matrices, we present in this paper, a new derivation of the capacity formula given by Brandenburg and Wyner for a discrete-time Gaussian multiple-input-multiple-output channel with memory. In this paper, we tackle not only the case considered by them, where the number of channel inputs and the number of channel outputs are the same, but also when both numbers are different. [ABSTRACT FROM AUTHOR]

As an optimal combinatorial object, zero-difference balanced (ZDB) functions introduced by Ding in 2008, are a generalization of the well-known perfect nonlinear functions. ZDB functions have received much attention in recent years due to its important applications in coding theory and sequence design. One objective of this paper is to present a construction of ZDB functions based on a kind of generalized cyclotomy. It generates ZDB functions over cyclic group with new parameters which can not be produced by earlier constructions. Another objective of this paper is to employ these ZDB functions to obtain at the same time: 1) optimal constant-composition codes; 2) perfect difference systems of sets; and 3) optimal frequency-hopping sequences, all with new parameters. [ABSTRACT FROM PUBLISHER]

This paper studies codes that correct a burst of deletions or insertions. Namely, a code will be called a $b$ -burst-deletion/insertion-correcting code if it can correct a burst of deletions/insertions of any $b$ consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically $\log (n)+b-1$ , the redundancy of the best code construction by Cheng et al. is $b(\log (n/b+1))$ . In this paper, we close on this gap and provide codes with redundancy at most $\log (n) + (b-1)\log (\log (n)) +b -\log (b)$ . We first show that the models of insertions and deletions are equivalent and thus it is enough to study codes correcting a burst of deletions. We then derive a non-asymptotic upper bound on the size of $b$ -burst-deletion-correcting codes and extend the burst deletion model to two more cases: 1) a deletion burst of at most $b$ consecutive bits and 2) a deletion burst of size at most $b$ (not necessarily consecutive). We extend our code construction for the first case and study the second case for $b=3,4$ . [ABSTRACT FROM PUBLISHER]

For generalized gamma probability densities, this paper studies the monotonicity of step sizes of optimal symmetric uniform scalar quantizers with respect to mean squared-error distortion. The principal results are that for the special cases of Gaussian, Laplacian, two-sided Rayleigh, and gamma densities, optimal step size monotonically decreases when the number of levels $N$ increases by two, and that for any generalized gamma density and all sufficiently large $N$ , optimal step size again decreases when $N$ increases by two. Also, it is shown that for a Laplacian density and sufficiently large $N$ , optimal step size decreases when $N$ increases by just one. [ABSTRACT FROM AUTHOR]

When a node in a distributed storage system fails, it needs to be promptly repaired to maintain system integrity. While typical erasure codes can provide a significant storage advantage over replication, they suffer from poor repair efficiency. Locally repairable codes (LRCs) tackle this issue by reducing the number of nodes participating in the repair process (locality), at the cost of reduced minimum distance. In this paper, we study the tradeoff between locality and minimum distance of LRCs with local codes that have arbitrary distance requirements. Unlike existing methods, where both the locality and the local distance requirements imposed on every node are identical, we allow the requirements to vary arbitrarily from node to node. Such a property can be an advantage for distributed storage systems with non-homogeneous characteristics. We present Singleton-type distance upper bounds and also provide an optimal code construction with respect to these bounds. In addition, the feasible rate region is characterized by dimension upper bounds that do not depend on the distance. [ABSTRACT FROM AUTHOR]

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory. [ABSTRACT FROM AUTHOR]

Codebooks with low-coherence have wide utilization in many fields, such as direct spread code division multiple access communications, compressed sensing and so on. There are two major ingredients in this paper. The first is to present a new character sum, the hyper Eisenstein sum and study the properties of this character sum. As an application, the second ingredient is to propose two constructions of codebooks with the hyper Eisenstein sum. The codebooks generated by these constructions asymptotically meet the Welch bound. The parameters of these codebooks are new. [ABSTRACT FROM AUTHOR]

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict avoiding codes. In this paper, we prove some nonexistence results for nonsingular perfect splitter sets. We also give some necessary conditions for the existence of purely singular perfect splitter sets. Finally, we apply these results to purely singular perfect $B[-1,k](m)$ and $B[-2,k](m)$ sets for small $k$. In particular, we solve completely the problems left by Schwartz (European J. Combin., vol. 36, pp.130–142, Feb. 2014). [ABSTRACT FROM AUTHOR]

The projective special linear group ${\mathrm {PSL}}_{2}(n)$ is 2-transitive for all primes $n$ and 3-homogeneous for $n \equiv 3 \pmod {4}$ on the set $\{0,1, \ldots, n-1, \infty \}$. It is known that the extended odd-like quadratic residue codes are invariant under ${\mathrm {PSL}}_{2}(n)$. Hence, the extended quadratic residue codes hold an infinite family of 2-designs for primes $n \equiv 1 \pmod {4}$ , an infinite family of 3-designs for primes $n \equiv 3 \pmod {4}$. To construct more $t$ -designs with $t \in \{2, 3\}$ , one would search for other extended cyclic codes over finite fields that are invariant under the action of ${\mathrm {PSL}}_{2}(n)$. The objective of this paper is to prove that the extended quadratic residue binary codes are the only nontrivial extended binary cyclic codes that are invariant under ${\mathrm {PSL}}_{2}(n)$. [ABSTRACT FROM AUTHOR]

In this paper, a construction of codebooks based on a set of bent functions satisfying certain conditions is introduced. It includes some earlier constructions of codebooks meeting the Levenstein bound as special cases. With this construction, two new families of codebooks achieving the Levenstein bound are obtained. The codebooks constructed in this paper could have a very small alphabet size. [ABSTRACT FROM PUBLISHER]

For non-binary codes the Elias bound is a good upper bound for the asymptotic information rate at low-relative minimum distance, whereas the Plotkin bound is better at high-relative minimum distance. In this paper, we obtain a hybrid of these bounds, which improves both. This in turn is based on the anticode bound, which is a hybrid of the Hamming and Singleton bounds and improves both bounds. The question of convexity of the asymptotic rate function is an important open question. We conjecture a much weaker form of the convexity, and we show that our bounds follow immediately if we assume the conjecture. [ABSTRACT FROM AUTHOR]

A code is said to be an $r$ -local locally repairable code (LRC) if each of its coordinates can be repaired by accessing at most r$ other coordinates. When some of the r$ coordinates are also erased, the r$ -local LRC cannot accomplish the local repair, which leads to the concept of (r,\delta)$ -locality. A q is said to have (r, \delta)$ -locality ( \delta \ge 2$ ) if for each coordinate i with support containing $i$ , whose length is at most $r + \delta - 1$ , and whose minimum distance is at least $\delta$ . The $(r, \delta)$ -LRC can tolerate $\delta -1$ erasures in every local code (i.e., punctured subcode), which degenerates to an $r$ -local LRC when $\delta =2$ . A $q$ -ary $(r,\delta)$ LRC is called optimal if it meets the singleton-like bound for $(r,\delta)$ -LRCs. A class of optimal $q$ -ary cyclic $r$ -local LRCs with lengths $n\mid q-1$ were constructed by Tamo, Barg, Goparaju, and Calderbank based on the $q$ -ary Reed-Solomon codes. In this paper, we construct a class of optimal $q$ -ary cyclic $(r,\delta)$ -LRCs ( $\delta \ge 2$ ) with length $n\mid q-1$ , which generalizes the results of Tamo et al. Moreover, we construct a new class of optimal $q$ -ary cyclic $r$ -local LRCs with lengths $n\mid q+1$ and a new class of optimal $q$ -ary cyclic $(r,\delta)$ -LRCs ( $\delta \ge 2$ ) with lengths $n\mid q+1$ . The constructed optimal LRCs with length $n=q+1$ have the best-known length for a given finite field with size $q$ when the minimum distance is larger than 4. [ABSTRACT FROM AUTHOR]

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write $n$ incoming packets and read $k$ outgoing packets while using $m$ memory banks, each able to write and read one packet per time unit. Each set of $n$ packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of $k$ packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case $n=k$ . [ABSTRACT FROM AUTHOR]

In recent literature, a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality) is presented. The key ingredient for constructing such optimal linear LRC codes is the so-called $r$ -good polynomials, where r$ is equal to the locality of the LRC code. However, given a prime p$ , known constructions of r exist only for some special integers r$ , and the problem of constructing optimal LRC codes over small field for any given locality is still open. In this paper, by using function composition, we present two general methods of designing good polynomials, which lead to three new constructions of r$ -good polynomials. Such polynomials bring new constructions of optimal LRC codes. In particular, our constructed polynomials as well as the power functions yield optimal (n,k,r) for all positive integers $r$ as localities, where $q$ is near the code length $n$ . [ABSTRACT FROM AUTHOR]

Binary sequences with low odd correlation have important applications in communication systems to reduce interference. In this paper, using the interleaving technique, we present a generic connection between binary sequences with low odd correlation and quaternary sequences with low even correlation. As a result, some new binary sequences with optimal odd auto-correlation magnitude are obtained. Besides, two sets consisting of 2^n+1 binary sequences of period 2(2^n-1) with the maximum odd correlation magnitude 2^((n+1)/ 2)+2 are derived, which are the first two optimal classes of binary sequence sets achieving the Sarwate bound on the odd correlation magnitude in the literature. [ABSTRACT FROM PUBLISHER]

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict-avoiding codes. The study of k -radius sequences was motivated by some problems occurring in large data transfer. It is observed that the existence of splitter sets yields k -radius sequences of short length. In this paper, we obtain several new results contributing to splitter sets and k -radius sequences. We give some new constructions of perfect splitter sets, as well as some nonexistence results on them. As a byproduct, we obtain some new results on optimal conflict-avoiding codes. Furthermore, we provide several explicit constructions of short k -radius sequences for certain values of n , by establishing the existence of k -additive sequences. In particular, we show that for any fixed k , where fk (n) denotes the shortest length of an n -ary $k$ -radius sequence. This result partially affirms a conjecture posed by Bondy, Lonc, and Rzążewski. [ABSTRACT FROM AUTHOR]

Frameproof codes are used to fingerprint digital data. They can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for $w$ -frameproof codes of length N$ over an alphabet of size q$ . The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve one of the previous results when q$ is small compared with w$ , say cq\leq w$ for some constant c\leq q$ . Furthermore, we pay special attention to binary frameproof codes. We show a binary w . [ABSTRACT FROM PUBLISHER]

Codes over Galois rings have been studied extensively during the last three decades. Negacyclic codes over \mathop \mathrm GR\nolimits (2^a,m) of length 2^s have been characterized: the ring \mathcal R2(a,m,-1)= {\mathrm{ GR}}(2^{a},m)[x]/\langle x^{2^{s}}+1\rangle is a chain ring. Furthermore, these results have been generalized to \lambda -constacyclic codes for any unit \lambda of the form 4z-1 , . In this paper, we study more general cases and investigate all cases, where {\mathcal{ R}}_{p}(a,m,\gamma) = {\mathrm{ GR}}(p^{a},m)[x]/\langle x^{p^{s}}-\gamma \rangle is a chain ring. In particular, the necessary and sufficient conditions for the ring {\mathcal{ R}}_{p}(a,m,\gamma) to be a chain ring are obtained. In addition, by using this structure we investigate all \gamma -constacyclic codes over \mathop {\mathrm {GR}}\nolimits (p^{a},m) when {\mathcal{ R}}_{p}(a,m,\gamma)$ is a chain ring. The necessary and sufficient conditions for the existence of self-orthogonal and self-dual \gamma$ -constacyclic codes are also provided. Among others, for any prime p$ , the structure of is used to establish the Hamming and homogeneous distances of $\gamma$ -constacyclic codes. [ABSTRACT FROM PUBLISHER]

Pairs of binary sequences formed using linear combinations of multiplicative characters of finite fields are exhibited that, when compared with a random sequence pairs, simultaneously achieve significantly lower mean square autocorrelation values (for each sequence in the pair) and significantly lower mean square crosscorrelation values. If we define crosscorrelation merit factor analogously to the usual merit factor for autocorrelation, and if we define demerit factor as the reciprocal of merit factor, then randomly selected binary sequence pairs are known to have an average crosscorrelation demerit factor of 1. Our constructions provide sequence pairs with a crosscorrelation demerit factor significantly less than 1, and at the same time, the autocorrelation demerit factors of the individual sequences can also be made significantly less than 1 (which also indicates better than average performance). The sequence pairs studied here provide combinations of autocorrelation and crosscorrelation performance that are not achievable using sequences formed from single characters, such as maximal linear recursive sequences (m-sequences) and Legendre sequences. In this paper, exact asymptotic formulae are proved for the autocorrelation and crosscorrelation merit factors of sequence pairs formed using linear combinations of multiplicative characters. Data is presented that shows that the asymptotic behavior is closely approximated by sequences of modest length. [ABSTRACT FROM PUBLISHER]

In the mid 1960s, Rothaus proposed the so-called “most general form” of constructing new bent functions by using three (initial) bent functions whose sum is again bent. In this paper, we utilize a special case of Rothaus construction when two of these three bent functions differ by a suitably chosen characteristic function of an $n/2$ -dimensional subspace. This simplification allows us to treat the induced bent conditions more easily, also implying the possibility to specify the initial functions in the partial spread class and most notably to identify several instances of the so-called non-normal bent functions. Affine inequivalent bent functions within this class are then identified using a suitable selection of initial bent functions within the partial spread class (stemming from the complete Desarguesian spread). It is also shown that when the initial bent functions belong to the class \mathcal {D} , then, under certain conditions, the constructed functions provably do not belong to the completed Maiorana–McFarland class. We conjecture that our method potentially generates an infinite class of non-normal bent functions (all tested ten-variable functions are non-normal but unfortunately they are weakly normal) though there are no efficient computational tools for confirming this. [ABSTRACT FROM AUTHOR]

Write-once memory (WOM) is a storage device consisting of $q$ -ary cells that can only increase their value. A WOM code is a coding scheme that allows writing multiple times to the memory without decreasing the levels of the cells. In the conventional model, it is assumed that the encoder can read the memory state before encoding, while the decoder reads only the memory state after encoding. However, there are three more models in this setup, which depend on whether the encoder and the decoder are informed or uninformed with the previous state of the memory. These four models were first introduced by Wolf et al., where they extensively studied the WOM capacity in these models for the binary case. In the non-binary setup, only the model, in which the encoder is informed and the decoder is not, was studied by Fu and Vinck. In this paper, we first present constructions of WOM codes in the models where the encoder is uninformed with the memory state (that is, the encoder cannot read the memory prior to encoding). We then study the capacity regions and maximum sum-rates of non-binary WOM codes for all four models. We extend the results by Wolf et al. and show that the capacity regions for the models in which the encoder is informed and the decoder is informed or uninformed in both the $\epsilon $ -error and the zero-error cases are all identical. We also find the $\epsilon $ -error capacity region; in this case, the encoder is uninformed and the decoder is informed and show that, in contrary to the binary case, it is a proper subset of the capacity region in the first two models. Several more results on the maximum sum-rate are presented as well. [ABSTRACT FROM AUTHOR]

Caching is often used in content delivery networks as a mechanism for reducing network traffic. Recently, the technique of coded caching was introduced whereby coding in the caches and coded transmission signals from the central server were considered. Prior results in this area demonstrate that carefully designing the placement of content in the caches and designing appropriate coded delivery signals from the server allow for a system where the delivery rates can be significantly smaller than conventional schemes. However, matching upper and lower bounds on the transmission rate have not yet been obtained. In this paper, we derive tighter lower bounds on the coded caching rate than were known previously. We demonstrate that this problem can equivalently be posed as a combinatorial problem of optimally labeling the leaves of a directed tree. Our proposed labeling algorithm allows for significantly improved lower bounds on the coded caching rate. Furthermore, we study certain structural properties of our algorithm that allow us to analytically quantify improvements on the rate lower bound for general values of the problem parameters. This allows us to obtain a multiplicative gap of at most four between the achievable rate and our lower bound. [ABSTRACT FROM PUBLISHER]

We consider the canonical shared link caching network formed by a source node, hosting a library of $m$ information messages (files), connected via a noiseless multicast link to $n$ user nodes, each equipped with a cache of size $M$ files. Users request files independently at random according to an a-priori known demand distribution q. A coding scheme for this network consists of two phases: cache placement and delivery. The cache placement is a mapping of the library files onto the user caches that can be optimized as a function of the demand statistics, but is agnostic of the actual demand realization. After the user demands are revealed, during the delivery phase the source sends a codeword (function of the library files, cache placement, and demands) to the users, such that each user retrieves its requested file with arbitrarily high probability. The goal is to minimize the average transmission length of the delivery phase, referred to as rate (expressed in channel symbols per file). In the case of deterministic demands, the optimal min-max rate has been characterized within a constant multiplicative factor, independent of the network parameters. The case of random demands was previously addressed by applying the order-optimal min-max scheme separately within groups of files requested with similar probability. However, no complete characterization of order-optimality was previously provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and, for the special yet relevant case of a Zipf demand distribution, we provide a comprehensive characterization of the order-optimal rate for all regimes of the system parameters, as well as an explicit placement and delivery scheme achieving order-optimal rates. We present also numerical results that confirm the superiority of our scheme with respect to previously proposed schemes for the same setting. [ABSTRACT FROM AUTHOR]

Multiply constant-weight codes (MCWCs) have been recently studied to improve the reliability of certain physically unclonable function response. In this paper, we give combinatorial constructions for the MCWCs, which yield several new infinite families of optimal MCWCs. Furthermore, we demonstrate that the Johnson-type upper bounds of the MCWCs are asymptotically tight for fixed Hamming weights and distances. Finally, we provide bounds and constructions of the 2-D MCWCs. [ABSTRACT FROM AUTHOR]

Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes “switch codes,” and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols. [ABSTRACT FROM PUBLISHER]

Both Maximum Distance Separable and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining the existence of q -ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where q is even. This paper focuses on the case where q is odd. We construct a few classes of new MDS self-dual codes through generalized Reed–Solomon codes. More precisely, we show that for any given even length n , we have a q and q is sufficiently large (say q\ge 4^{n}\times n^{2}) . Furthermore, we prove that there exists a q -ary MDS self-dual code of length n if q=r^{2} and n$ satisfies one of the three conditions: 1) n\le r$ and n$ is even; 2) q$ is odd and n-1$ is an odd divisor of and $n=2tr$ for any $t\le (r-1)/2$ . [ABSTRACT FROM PUBLISHER]

In this paper, we introduce the so-called hierarchical interaction models, where we assume that the computation of the value of a function m: \mathbb R^d\rightarrow \mathbb R is done in several layers, where in each layer a function of at most d^* inputs computed by the previous layer is evaluated. We investigate two different regression estimates based on polynomial splines and on neural networks, and show that if the regression function satisfies a hierarchical interaction model and all occurring functions in the model are smooth, the rate of convergence of these estimates depends on d^* (and not on $d$ ). Hence, in this case, the estimates can achieve good rate of convergence even for large $d$ , and are in this sense able to circumvent the so-called curse of dimensionality. [ABSTRACT FROM PUBLISHER]

Given n discrete random variables, its entropy vector is the 2^{n}-1 -dimensional vector obtained from the joint entropies of all non-empty subsets of the random variables. It is well known that there is a close relation between such an entropy vector and a certain group-characterizable vector obtained from a finite group and n of its subgroups; indeed, roughly speaking, knowing the region of all such group-characterizable vectors is equivalent to knowing the region of all entropy vectors. This correspondence may be useful for characterizing the space of entropic vectors and for designing network codes. If one restricts attention to abelian groups then not all entropy vectors can be obtained. This is an explanation for the fact shown by Dougherty et al. that linear network codes cannot achieve capacity in general network coding problems (since linear network codes come from abelian groups). All abelian group-characterizable vectors, and by fiat all entropy vectors generated by linear network codes, satisfy a linear inequality called the Ingleton inequality. General entropy vectors, however, do not necessarily have this property. It is, therefore, of interest to identify groups that violate the Ingleton inequality. In this paper, we study the problem of finding nonabelian finite groups that yield characterizable vectors, which violate the Ingleton inequality. Using a refined computer search, we find the symmetric group S5 to be the smallest group that violates the Ingleton inequality. Careful study of the structure of this group, and its subgroups, reveals that it belongs to the Ingleton-violating family PGL(2,q) with a prime power q \geq 5 , i.e., the projective group of 2\times 2 nonsingular matrices with entries in \mathbb Fq . We further interpret this family of groups, and their subgroups, using the theory of group actions and identify the subgroups as certain stabilizers. We also extend the construction to more general groups such as PGL(n,q) and $GL(n,q)$ . The families of groups identified here are therefore good candidates for constructing network codes more powerful than linear network codes, and we discuss some considerations for constructing such group network codes. [ABSTRACT FROM PUBLISHER]

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class \mathcal N of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil infinitely many new multicast networks linearly solvable over GF( q ) but not over GF( q' ) with q < q' , based on a subgroup order criterion. In particular: 1) for every k\geq 2 ) but not over GF( 2^{2k+1} ) and 2) for arbitrary distinct primes p and p' , there are infinitely many k and k' ) but not over GF( p'^k' ) with p^k < p'^k' . [ABSTRACT FROM PUBLISHER]

One central theme in quantum error-correction is to construct quantum codes that have a relatively large minimum distance. In this paper, we first present a construction of classical linear codes based on certain classes of polynomials. Through these classical linear codes, we are able to obtain some new quantum codes. It turns out that some of the quantum codes exhibited here have better parameters than the ones available in the literature. [ABSTRACT FROM PUBLISHER]

Projective Reed–Muller codes were introduced by Lachaud in 1988 and their dimension and minimum distance were determined by Serre and Sørensen in 1991. In coding theory, one is also interested in the higher Hamming weights, to study the code performance. Yet, not many values of the higher Hamming weights are known for these codes, not even the second lowest weight (also known as the next-to-minimal weight) is completely determined. In this paper, we determine all the values of the next-to-minimal weight for the binary projective Reed–Muller codes, which we show to be equal to the next-to-minimal weight of Reed–Muller codes in most, but not all, cases. [ABSTRACT FROM PUBLISHER]

We study a noiseless broadcast link serving K users whose requests arise from a library of N files. Every user is equipped with a cache of size M files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most N/M file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file F scales to infinity. The asymptotic coding gain obtained is roughly t=KM/N . In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets F is a function of the system parameters . Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of ({4}/{3})g is at least O(({g}/{K})(N/M)^{g-1})$ . We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters. [ABSTRACT FROM AUTHOR]

Bent functions can be classified into regular bent functions, weakly regular but not regular bent functions, and non-weakly regular bent functions. Regular and weakly regular bent functions always appear in pairs, since their duals are also bent functions. In general, this does not apply to non-weakly regular bent functions. However, the first known construction of non-weakly regular bent functions by Çeşmelioğlu et al. yields bent functions for which the dual is also bent. In this paper, the first construction of non-weakly regular bent functions for which the dual is not bent is presented. We call such functions non-dual-bent functions. Until now, only sporadic examples found via computer search were known. We then show that with the direct sum of bent functions and with the construction by Çeşmelioğlu et al., one can obtain infinitely many non-dual-bent functions once one example of a non-dual-bent function is known. [ABSTRACT FROM PUBLISHER]

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude. [ABSTRACT FROM PUBLISHER]

Frequency-hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. Strictly optimal FHSs are those FHSs with optimal partial Hamming autocorrelation irrespective of the correlation window length. In this paper, strictly optimal FHSs are investigated from a combinatorial approach. A generic connection between strictly optimal FHSs and disjoint cyclic perfect Mendelsohn difference families is established. By virtue of this connection, new strictly optimal FHSs are generated from some disjoint CPMDFs. These strictly optimal FHSs have new parameters not covered in the literature. [ABSTRACT FROM AUTHOR]

This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth’s achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth’s achievable rate region is given, and the latter is shown to immediately extend to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters. [ABSTRACT FROM PUBLISHER]

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]

The relevance in a sampling theory of U -invariant subspaces of a Hilbert space \mathcal {H} , where U denotes a unitary operator on \mathcal H , is nowadays a recognized fact. Indeed, shift-invariant subspaces of L^2(\mathbb R) become a particular example; periodic extensions of finite signals also provide a remarkable example. As a consequence, the availability of an abstract $U$ -sampling theory becomes a useful tool to handle these problems. In this paper, we derive a sampling theory for finite dimensional multiple generated $U$ -invariant subspaces of a Hilbert space \mathcal {H} . As the involved samples are identified as frame coefficients in a suitable euclidean space, the relevant mathematical technique is that of the finite frame theory. Since finite frames are nothing but spanning sets of vectors, the used technique naturally meets matrix analysis. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

Motivated by the rank modulation scheme, a recent study by Sala and Dolecek explored the idea of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells. A permutation \sigma \in Sn satisfies the single-neighbor $k$ -constraint if \sigma (i+1)-\sigma (i)\leq k$ for all 1\leq i\leq n-1$ . In this paper, this model is extended into two constraints. A permutation k$ -constraint if for all 2 \leq i \leq n-1$ , \sigma (i)-\sigma (i-1)\leq k$ or \sigma (i \,\, + \,\, 1)-\sigma (i)\leq k$ , and it satisfies the asymmetric two-neighbor k$ -constraint if for all 2 \leq i \leq n-1$ , and the capacity of the second constraint is 1 regardless for any positive $k$ . We also extend our results and study the capacity of these two constraints combined with error-correcting codes in the Kendall $\tau $ -metric. [ABSTRACT FROM AUTHOR]

In this paper, we extend two earlier works further in two directions and compute the weight distribution of these cyclic codes under more relaxed conditions. It is interesting to note that many cyclic codes in the family are optimal and have only a few non-zero weights. Besides using similar ideas, we carry out some subtle manipulation of certain exponential sums. [ABSTRACT FROM AUTHOR]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated. In this problem, each terminal observes a component of correlated sources. All three terminals are required to generate the common SK to be concealed from an eavesdropper that has access to the public discussion, while two designated terminals are required to generate an extra PK to be concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established by Ye and Narayan, and was shown to be achievable for a special case. In this paper, the SK-PK capacity region is established in general by developing schemes to achieve the outer bound for the remaining two cases. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound. [ABSTRACT FROM AUTHOR]