Search

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]

In order to evaluate the goodness of frequency hopping (FH) sequence design, the periodic Hamming correlation function is used as an important measure. Usually, the length of correlation window is shorter than the period of the chosen FH sequence, so the study of the partial Hamming correlation of FH sequence is particularly important. If an FH sequence or an FH sequence set has an optimal partial Hamming correlation with respect to the partial Hamming correlation bound for all length of correlation window, then the FH sequence or the FH sequence set is said to be strictly optimal. In this paper, we first prove that there is no strictly optimal FH sequence set of family size $M$ and sequence length $N$ over a frequency slot set of size $q$ with respect to the partial Hamming correlation bound derived by Niu et al. when $N>{q^{2}}/{M}$ and $q\geq 2$ , and that by Cai et al. when $N>{q^{2}}/{M}$ and $q\geq {2N}/({N-2})$. Furthermore, we define a special partition-type difference packing (DP) called $[N,\nabla,H_{a}^{l}]$ PDP and give several classes of $[N,\nabla,H_{a}^{l}]$ PDPs. Then, we present a new construction of strictly optimal FH sequences. By choosing different PDPs, the FH sequences constructed can give new and flexible parameters. By utilizing this construction method recursively, we can obtain new $[N,\nabla,H_{a}^{l}]$ PDPs, which lead to infinitely many classes of strictly optimal FH sequences with new parameters. Moreover, based upon an $[N,\nabla,H_{a}^{l}]$ PDP, we present a construction of strictly optimal FH sequence sets. By preceding construction method and recursive construction, we can also obtain infinite classes of strictly optimal FH sequence sets which can give new and flexible parameters. [ABSTRACT FROM AUTHOR]

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed–Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size $q$. Recently, it was proved through the extension of construction by Tamo and Barg that the length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al. Surprisingly, Barg et al. presented a few examples of $q$ -ary optimal locally repairable codes of small distance and locality with code length achieving roughly $q^{2}$. Very recently, it was further shown in the work of Li et al. that there exist $q$ -ary optimal locally repairable codes with the length bigger than $q+1$ and the distance proportional to $n$. Thus, it becomes an interesting and challenging problem to construct new families of $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen. [ABSTRACT FROM AUTHOR]

Compute-and-forward (CF) harnesses interference in wireless communications by exploiting structured coding. The key idea of CF is to compute integer combinations of code words from multiple source nodes, rather than to decode individual code words by treating others as noise. Compute-compress-and-forward (CCF) can further enhance the network performance by introducing compression operations at receivers. In this paper, we develop a more general compression framework, termed generalized CCF (GCCF), where the compression function involves the selection of message segments over finite fields. We show that GCCF achieves a broader compression rate region than CCF. We also compare our compression rate region with the fundamental Slepian–Wolf (SW) region. We show that GCCF is optimal in the sense of achieving the minimum total compression rate. We also establish the criteria under which GCCF achieves the SW region. In addition, we consider a two-hop relay network employing the GCCF scheme. We formulate a sum-rate maximization problem and develop an approximate algorithm to solve the problem. Numerical results are presented to demonstrate the performance superiority of GCCF over CCF and other schemes. [ABSTRACT FROM AUTHOR]

We study the problem of constructing balanced generator matrices for Reed–Solomon and Tamo–Barg codes. More specifically, we are interested in realizing generator matrices, for the full-length cyclic versions of these codes, where all rows have the same weight and the difference in weight between any columns is at most one. The results presented in this paper translate to computationally balanced encoding schemes, which can be appealing in distributed storage applications. Indeed, the balancedness of these generator matrices guarantees that the computation effort exerted by any storage node is essentially the same. In general, the framework presented can accommodate various values for the required row weight. We emphasize the possibility of constructing sparsest and balanced generator matrices for Reed–Solomon codes, i.e., each row is a minimum distance codeword. The number of storage nodes contacted once a message symbol is updated decreases with the row weight, so sparse constructions are appealing in that context. Results of similar flavor are presented for cyclic Tamo–Barg codes. In particular, we show that for a code with minimum distance $d$ and locality $r$ , a construction in which every row is of weight $d + r - 1$ is possible. The constructions presented are deterministic and operate over the codes’ original underlying finite field. As a result, efficient decoding from both errors and erasures is possible thanks to the plethora of efficient decoders available for the codes considered. [ABSTRACT FROM AUTHOR]

This paper aims to develop the insights into Bayesian truth serum (BTS) mechanism by postulating a sequence of seven natural conditions reminiscent of axioms in information theory. The condition that reduces a larger family of mechanisms to BTS is additivity, akin to the axiomatic development of entropy. The seven conditions identify BTS as the unique scoring rule for ranking respondents in situations in which respondents are asked to choose an alternative from a finite set and provide predictions of their peers’ propensities to choose, for finite or infinite sets of respondents. [ABSTRACT FROM AUTHOR]

Linear complementary dual (LCD) cyclic codes were referred historically to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In particular, it has been shown that binary LCD codes play an important role in implementations against side-channel attacks and fault injection attacks. In this paper, we first present a new characterization of binary LCD codes in terms of their orthogonal or symplectic basis. Using such a characterization, we solve a conjecture proposed by Galvez et al. on the minimum distance of binary LCD codes. Next, we consider the action of the orthogonal group on the set of all LCD codes, determine all possible orbits of this action, derive simple closed formulas of the size of the orbits, and present some asymptotic results on the size of the corresponding orbits. Our results show that almost all binary LCD codes are odd-like codes with odd-like duals, and about half of $q$ -ary LCD codes have orthonormal basis, where $q$ is a power of an odd prime. [ABSTRACT FROM AUTHOR]

An error-erasure channel is a simple noise model that introduces both errors and erasures. While the two types of errors can be corrected simultaneously with error-correcting codes, it is also known that any linear code allows for first correcting errors and then erasures in two-step decoding. In particular, a carefully designed parity-check matrix not only allows for separating erasures from errors but also makes it possible to efficiently correct erasures. The separating redundancy of a linear code is the number of parity-check equations in a smallest parity-check matrix that has the required property for this error-erasure separation. In a sense, it is a parameter of a linear code that represents the minimum overhead for efficiently separating erasures from errors. While several bounds on separating redundancy are known, there still remains a wide gap between upper and lower bounds except for a few limited cases. In this paper, using probabilistic combinatorics and design theory, we improve both upper and lower bounds on separating redundancy. We also show a relation between parity-check matrices for error-erasure separation and special matrices, called X-codes, for data compaction circuits in VLSI testing. This leads to an exponentially improved bound on the size of an optimal X-code. [ABSTRACT FROM AUTHOR]

We investigate the maximum coding rate for a given average blocklength and error probability over a $K$ -user discrete memoryless broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. For the point-to-point case, Polyanskiyet al.(2011) demonstrated that variable-length coding combined with stop-feedback significantly increases the speed of convergence of the maximum coding rate to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, i.e.,zero dispersion. In this paper, we present nonasymptotic achievability and converse bounds on the maximum coding rate of the common-message $K$ -user discrete memoryless broadcast channel, which strengthen and generalize the ones reported in Trillingsgaardet al.(2015) for the two-user case. An asymptotic analysis of these bounds reveals that zero dispersion cannot be achieved for certain common-message broadcast channels (e.g., the binary symmetric broadcast channel). Furthermore, we identify conditions under which our converse and achievability bounds are tight up to the second order. Through numerical evaluations, we illustrate that our second-order expansions approximate accurately the maximum coding rate and that the speed of convergence to capacity is indeed slower than for the point-to-point case. [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]

Racetrack memory is a new technology, which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape, which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory’s speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this paper, we design codes, which combat shift errors in racetrack memory, called position errors, namely, shifting the domains is not an error-free operation and the domains may be over shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. This setup is a special case of the reconstruction problem studied by Levenshtein, however, in our case, the position errors from different heads are correlated. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions. In particular, under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, $d$ deletions with $d+1$ heads if the heads are well separated. Similar results are provided for burst of deletions, sticky insertions, and combinations of both deletions and sticky insertions. [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]

In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with $w_{\min }/w_{\max } \leq 1/2$ from a generic construction, where $w_{\min }$ and $w_{\max }$ , respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined. [ABSTRACT FROM AUTHOR]

Reed–Muller codes belong to the family of affine-invariant codes. As such codes, they have a defining set that determines them uniquely, and they are extensions of cyclic group codes. In this paper, we identify those cyclic codes with multidimensional abelian codes and we use the techniques introduced by Bernal and Simón to construct information sets for them from their defining set. For first- and second-order Reed–Muller codes, we describe a direct method to construct information sets in terms of their basic parameters. [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]

When transmitting information over a noisy channel, two approaches, dating back to Shannon’s work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper, we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with the cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this paper. The first is proving closed-form bounds on the capacity, which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained $(0,k)$ -RLL tends to 1 as $k$ grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems. [ABSTRACT FROM AUTHOR]

This paper considers the signal-to-noise ratio (SNR)-evolution, meaning the behavior as a function of the SNR, of the minimum mean-square error (MMSE) function of code sequences in several multi-user settings in the additive white Gaussian noise regime. The settings investigated in this context include the Gaussian wiretap channel, the Gaussian broadcast channel (BC), and the Gaussian BC with confidential messages (BCC). This paper shows that the specific properties of the SNR-evolution of the MMSE and conditional MMSE functions are necessary and sufficient conditions for capacity or equivocation achieving code sequences. In some cases, the complete SNR-evolution of a family of code sequences can be determined, providing significant insight into the disturbance (in terms of MMSE) such codes have on unintended receivers at other SNRs. Moreover, the effects of an additional MMSE constraint on the capacity region and on the SNR-evolution of code sequences are considered in the BC and BCC settings. Such an analysis emphasizes the tradeoff between rates and limited disturbance on unintended receivers. [ABSTRACT FROM AUTHOR]

An involution is a permutation, such that its inverse is itself (i.e., cycle length ≤ 2). Due to this property, involutions have been used in many applications, including cryptography and coding theory. In this paper, we provide a systematic study of involutions that are defined over a finite field of characteristic 2. We characterize the involution property of several classes of polynomials and propose several constructions. Furthermore, we study the number of fixed points of involutions, which is a pertinent question related to permutations with short cycle. In this paper, we mostly have used combinatorial techniques. [ABSTRACT FROM AUTHOR]

In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file, while minimizing some communication cost. We assume that the users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user’s cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this paper, each user can have any arbitrary convex cost function. We provide deterministic, polynomial-time algorithms (in the number of users and packets), which find an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm, which is based on a random linear network-coding scheme. [ABSTRACT FROM AUTHOR]

Linear codes with a few weights have applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. This paper first generalizes the method of constructing two-weight and three-weight linear codes of Ding et al. and Zhou et al. to general weakly regular bent functions and determines the weight distributions of these linear codes. It solves an open problem proposed by Ding et al. Furthermore, this paper constructs new linear codes with two or three weights and presents their weight distributions. They contain some optimal codes meeting certain bound on linear codes. [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]

In an acyclic multicast network, it is well known that a linear network coding solution over GF( q ) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF( q ) can be efficiently constructed. In this paper, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. In particular, we prove by construction that: 1) for every \omega \geq 3 , there is a multicast network with source outdegree \omega linearly solvable over GF(7) but not over GF(8), and another multicast network linearly solvable over GF(16) but not over GF(17); 2) there is a multicast network linearly solvable over GF(5) but not over such GF( q ) and over GF( q^m2 ) is not necessarily linearly solvable over GF( q^{m1 + m2} ); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size q_{\mathrm{ min}} for a linear solution over GF( q_{\mathrm{ min}} ) is lower bounded by \Theta (\sqrt T) , but not every larger field than GF( q\mathrm{ min} ) suffices to yield a linear solution. The insight brought from this paper is that not only the field size but also the order of subgroups in the multiplicative group of a finite field affects the linear solvability of a multicast network. [ABSTRACT FROM AUTHOR]

The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require a large number of lifetime writes. The proposed approach in this paper for alleviating this problem consists of the efficient integration of two key ideas: 1) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and 2) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. This paper presents a new coding scheme that combines rank-modulation with rewriting. The key benefits of the new scheme include: 1) the ability to store close to 2 bit per cell on each write with minimal impact on the lifetime of the memory and 2) efficient encoding and decoding algorithms that make use of capacity-achieving write-once-memory codes that were proposed recently. [ABSTRACT FROM PUBLISHER]

The history of infections and epidemics holds famous examples where understanding, containing, and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV, and most computer viruses spread person to person, device to device, and through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper, we study two fundamental questions of detection. First, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a random illness operating independently of any contact network (e.g., seasonal allergies)? Second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread—the causative network—without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions that networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the $d$ -dimensional grid, and the Erdös-Renyi graphs. [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]

Frequency-hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. In this paper, lower bounds on the partial Hamming correlation of FHSs and FHS sets are proposed. They slightly improve the known bounds by Eun et al. and Zhou et al. A construction of FHSs and FHS sets having optimal partial Hamming correlation with respect to the improved bounds is also presented based on the theory of generalized cyclotomy. Our construction yields optimal FHSs and FHS sets with new and flexible parameters not covered in this paper. [ABSTRACT FROM AUTHOR]

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. Yan et al. reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into $F$ pieces, where $F$ grows exponentially with the number of users $K$. Such a constraint is obviously infeasible in the practical setting, especially when $K$ is large. Thus, it is desirable to design caching schemes with constant rate $R$ (independent of $K$ ) as well as smaller $F$. In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with $F$ growing linearly with $K$ do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with $F$ growing sub-exponentially with $K$ do exist. [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]

We consider the minimax estimation problem of a discrete distribution with support size $k$ under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number $\epsilon $ measures the privacy level of a privatization scheme. For a given $\epsilon $ , we consider the problem of constructing optimal privatization schemes with $\epsilon $ -privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes known in the literature provide order optimal performance in the high privacy regime where $\epsilon $ is very close to 0, and in the low privacy regime where $e^{\epsilon }\approx k$ , respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when $1\ll e^{\epsilon } \ll k$. More concretely, we prove that when $3.8 < \epsilon <\ln (k/9) $ , our schemes reduce the expected estimation loss by 50% under $\ell _{2}^{2}$ metric and by 30% under $\ell _{1}$ metric over the existing schemes. We also prove a lower bound for the region $e^{\epsilon } \ll k$ , which implies that our schemes are order optimal in this regime. [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]

This paper contributes to increase our knowledge on generalized bent functions (including generalized bent Boolean functions and generalized $p$ -ary bent functions with odd prime $p$ ) by bringing new results on their characterization and construction in arbitrary characteristic. More specifically, we first investigate relations between generalized bent functions and bent functions by the decomposition of generalized bent functions. This enables us to completely characterize generalized bent functions and $\mathbb Z_{p^{k}}$ -bent functions by some affine space associated with the generalized bent functions. We also present the relationship between generalized bent Boolean functions with an odd number of variables and generalized bent Boolean functions with an even number of variables. Based on the well-known Maiorana-McFarland class of Boolean functions, we present some infinite classes of generalized bent Boolean functions. In addition, we introduce a class of generalized hyperbent functions that can be seen as generalized Dillon’s $PS$ functions. Finally, we solve an open problem related to the description of the dual function of a weakly regular generalized bent Boolean function with an odd number of variables via the Walsh–Hadamard transform of their component functions, and we generalize these results to the case of odd prime. [ABSTRACT FROM AUTHOR]

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]

The property of superadditivity of the quantum relative entropy states that, in a bipartite system $ {\mathcal H}_{AB}= {\mathcal H}_{A} \otimes {\mathcal H} _{B}$ , for every density operator $\rho _{AB}$ , one has $ D(\rho _{AB}||\sigma _{A}\otimes \sigma _{B}) \ge D(\rho _{A}||\sigma _{A})+ D(\rho _{B}||\sigma _{B})$. In this paper, we provide an extension of this inequality for arbitrary density operators $\sigma _{AB}$. More specifically, we prove that $ \alpha (\sigma _{AB})\cdot D(\rho _{AB}||\sigma _{AB}) \ge D(\rho _{A}||\sigma _{A})+ D(\rho _{B}||\sigma _{B})$ holds for all bipartite states $\rho _{AB}$ and $\sigma _{AB}$ , where $\alpha (\sigma _{AB})= 1+2 \|\sigma _{A}^{-1/2} \otimes \sigma _{B}^{-1/2} \, \sigma _{AB} \, \sigma _{A}^{-1/2} \otimes \sigma _{B}^{-1/2} - {{\mathsf{1}}}_{AB}\|_\infty $. [ABSTRACT FROM AUTHOR]

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k -threshold access structure, where the qualified subsets are those of size at least k . When k=2 and there are n parties, there are schemes for sharing an \ell bits, and this is tight even for secrets of 1 b. In these schemes, the number of parties n must be given in advance to the dealer. In this paper, we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the {t} {^{\mathrm{ th}}} party arriving the smallest possible share as a function of t$ . Our main result is such a scheme for the k$ -threshold access structure and 1-bit secrets where the share size of party t$ is . For k=2$ we observe an equivalence to prefix codes and present matching upper and lower bounds of the form \log t + \log \log t + \log \log \log t + O(1)$ . Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size . [ABSTRACT FROM AUTHOR]

This paper addresses the correspondence between linear inequalities for Shannon entropy and differential entropy for sums of independent group-valued random variables. We show that any balanced (with the sum of coefficients being zero) linear inequality for Shannon entropy holds if and only if its differential entropy counterpart also holds; moreover, any linear inequality for differential entropy must be balanced. In particular, our result shows that recently proved differential entropy inequalities by Kontoyiannis and Madiman can be deduced from their discrete counterparts due to Tao in a unified manner. Generalizations to certain abelian groups are also obtained. Our proof of extending inequalities for Shannon entropy to differential entropy relies on a result of Rényi which relates the Shannon entropy of a finely discretized random variable to its differential entropy and also helps in establishing that the entropy of the sum of quantized random variables is asymptotically equal to that of the quantized sum; the converse uses the asymptotics of the differential entropy of convolutions with weak additive noise. [ABSTRACT FROM PUBLISHER]

Cooperation strategies allow communication devices to work together to improve network capacity. Consider a network consisting of $k$ encoders, a multiple access channel (MAC), a decoder, and a node, referred to as a “cooperation facilitator” (CF), that is connected to each encoder via a pair of rate-limited links, with one link going from the encoder to the CF and the other link going back. Let the “cooperation rate” be the total outgoing rate of the CF. This paper demonstrates the existence of a class of MACs where the ratio of the sum-capacity gain to cooperation rate tends to infinity as the cooperation rate tends to zero. For any $k\geq 2$ , examples of channels in this class include the $k$ -user binary adder MAC and the $k$ -user Gaussian MAC. [ABSTRACT FROM PUBLISHER]

It is well known that the entropy $H(X)$ of a discrete random variable $X$ is always greater than or equal to the entropy $H(f(X))$ of a function $f$ of $X$ , with equality if and only if $f$ is one-to-one. In this paper, we give tight bounds on $H(f(X))$ , when the function $f$ is not one-to-one, and we illustrate a few scenarios, where this matters. As an intermediate step toward our main result, we derive a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximal and minimal probabilities is known. The lower bound improves on previous results in the literature, and it could find applications outside the present scenario. [ABSTRACT FROM AUTHOR]

This paper studies channel coding for the discrete memoryless multiple-access channel with a given (possibly suboptimal) decoding rule. A multi-letter successive decoding rule depending on an arbitrary non-negative decoding metric is considered, and achievable rate regions and error exponents are derived both for the standard MAC (independent codebooks), and for the cognitive MAC (one user knows both messages) with superposition coding. In the cognitive case, the rate region and error exponent are shown to be tight with respect to the ensemble average. The rate regions are compared with those of the commonly considered decoder that chooses the message pair maximizing the decoding metric, and numerical examples are given for which successive decoding yields a strictly higher sum rate for a given pair of input distributions. [ABSTRACT FROM AUTHOR]

This paper investigates the convexity of the mean squared-error distortion of symmetric uniform scalar quantization with respect to step size. The principal results include proofs for odd numbers of levels that distortion is not convex for any symmetric density and that it is convex for even numbers of levels for densities, such as Gaussian, Laplacian, and gamma, but is not, in general for two-sided Rayleigh. For the latter case, an interval is derived that includes the optimal step size and over which the distortion is convex. The proofs of convexity use the Euler–Maclaurin formula applied to the second derivative of distortion, with upper bounds on the remainder term. These results imply that a zero of the derivative of the distortion for these densities, which has been previously conjectured optimal, is indeed the optimal step size, because the distortion is convex either globally or locally over a sufficiently wide interval to ensure a global minimizer. [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 this paper, we construct a new family of quantum synchronizable codes from repeated-root cyclic codes of lengths p^s and lp^s over \mathbb Fq , where $s\geq 1~and l\geq 2$ are integers, and $p\geq 3$ is the odd characteristic. Within some loose limitations, these synchronizable codes can possess the best possible capability in synchronization recovery, and therefore, enriches the variety of good quantum synchronizable codes. Furthermore, by using known techniques in classical coding theory which convert the computation of the minimum distance of a repeated-root cyclic code to that of a shorter simple-root cyclic code, we prove that the repeated-root cyclic codes of lengths p^s and lp^s are in general better than narrow-sense BCH codes of close lengths in terms of minimum distances, and thereby enable the obtained synchronizable codes to correct more Pauli errors. [ABSTRACT FROM PUBLISHER]

This paper quantifies the intuitive observation that adding noise reduces available information by means of nonlinear strong data processing inequalities. Consider the random variables W\to X\to Y forming a Markov chain, where Y = X + Z with X and Z real valued, independent and X -norm. It is shown that I(W; Y) \le FI(I(W;X)) with FI(t) < t whenever $t > 0$ , if and only if $Z$ has a density whose support is not disjoint from any translate of itself. A related question is to characterize for what couplings $(W, X)$ the mutual information $I(W; Y)$ is close to maximum possible. To that end we show that in order to saturate the channel, i.e., for $I(W; Y)$ to approach capacity, it is mandatory that $I(W; X)\to \infty $ (under suitable conditions on the channel). A key ingredient for this result is a deconvolution lemma which shows that postconvolution total variation distance bounds the preconvolution Kolmogorov–Smirnov distance. Explicit bounds are provided for the special case of the additive Gaussian noise channel with quadratic cost constraint. These bounds are shown to be order optimal. For this case, simplified proofs are provided leveraging Gaussian-specific tools such as the connection between information and estimation (I-MMSE) and Talagrand’s information-transportation inequality. [ABSTRACT FROM PUBLISHER]

This paper investigates the achievable rates of an additive white Gaussian noise energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed random variables. The blocks have length $L$ , which can be interpreted as the coherence time of the energy-arrival process. If L$ is a constant or grows sublinearly in the blocklength n$ , we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability \varepsilon $ . The first-order term is known as the \varepsilon for any $\varepsilon $ less than 1/2. The lower bound is obtained through analyzing the save-and-transmit strategy. If $L$ grows linearly in $n$ , we obtain lower and upper bounds on the $\varepsilon $ -capacity, which coincide whenever the cumulative distribution function of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks. [ABSTRACT FROM PUBLISHER]

This paper considers the communication for omniscience problem: a set of users observe a discrete memoryless multiple source and want to recover the entire multiple source via noise-free broadcast communications. We study the problem of how to determine an optimal rate vector that attains omniscience with the minimum sum rate, the total number of communications. The results cover both asymptotic and non-asymptotic models where the transmission rates are real and integral, respectively. We propose a modified decomposition algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and non-asymptotic models, respectively, both of which determine the value of the minimum sum rate and a corresponding optimal rate vector in polynomial time. For the coordinate saturation capacity algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a fusion method and show by experimental results that this fusion method contributes to a reduction in computation complexity. Finally, we show that the separable convex minimization problem over the optimal rate vector set in the asymptotic model can be decomposed by the fundamental partition, the optimal partition of the user set that determines the minimum sum rate, so that the problem can be solved more efficiently. [ABSTRACT FROM PUBLISHER]

Minimum storage regenerating codes have minimum storage of data in each node and therefore are maximal distance separable (for short) codes. Thus, the number of nodes is upper-bounded by 2^ \mathfrak b , where \mathfrak b is the bits of data stored in each node. From both theoretical and practical points of view (see the details in Section 1), it is natural to consider regenerating codes that nearly have minimum storage of data, and meanwhile, the number of nodes is unbounded. One of the candidates for such regenerating codes is an algebraic geometry code. In this paper, we generalize the repairing algorithm of Reed–Solomon codes given by Guruswami and Wotters to algebraic geometry codes and present a repairing algorithm for arbitrary one-point algebraic geometry codes. By applying our repairing algorithm to the one-point algebraic geometry codes based on the Garcia–Stichtenoth tower, one can repair a code of rate 1- \varepsilon and length n over \mathbb Fq with bandwidth (n-1)(1- \tau)\log q for any \varepsilon =2^(\tau -1/2)\log q with a real $\tau \in (0,1/2)$ . In addition, storage in each node for an algebraic geometry code is close to the minimum storage. Due to nice structures of Hermitian curves, repairing of Hermitian codes is also investigated. As a result, we are able to show that algebraic geometry codes are regenerating codes with good parameters. [ABSTRACT FROM AUTHOR]

We study the communication efficient secret sharing (CESS) problem. A classical threshold secret sharing scheme encodes a secret into $n$ shares given to n$ parties, such that any set of at least t$ , t n$ . However, Staircase codes may require dividing the secret and the shares into many symbols. We also describe how Staircase codes can be used to construct threshold changeable secret sharing with minimum storage cost, i.e., minimum share size. [ABSTRACT FROM AUTHOR]

Zero correlation zone (ZCZ) sequences are a class of spreading sequences having ideal auto-correlation and cross correlation in a zone around the origin. They have been extensively studied in recent years due to their important applications in quasi-synchronous code division multiple access systems. In this paper, a construction of ZCZ sequence sets is proposed based on perfect nonlinear functions. It generates multiple ZCZ sequence sets with the properties: 1) each sequence is perfect in the sense that its out-of-phase auto-correlation is always zero; 2) each ZCZ sequence set is optimal with respect to the Tang–Fan–Matsufuji bound in which all the sequences are pairwise cyclically distinct; and 3) the maximum inter-set cross correlation of multiple sequence sets achieves the well-known Sarwate bound. [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]