Search

Linear codes with few weights have applications in consumer electronics, communications, data storage systems, secret sharing, authentication codes, and association schemes. As a special class of linear codes, minimal linear codes have important applications in secret sharing and secure computation of data between two parties. The construction of minimal linear codes with new and desirable parameters is an interesting research topic in coding theory and cryptography. Recently, Mesnager et.al. stated that “constructing linear codes with good parameters from non-weakly regular bent functions is an interesting problem.” The goal of this paper is to construct linear codes with two or three weights from non-weakly regular bent functions over finite fields and analyze the minimality of the constructed linear codes. In doing so, we draw inspiration from a paper by Mesnager in which she constructed linear codes with small weights from weakly regular bent functions based on a generic construction method. First, we recall the definitions of the subsets $B_{+}(f)$ and $B_{-}(f)$ associated with a non-weakly regular bent function $f$. Next, we construct two- or three-weight linear $p$ -ary codes on these sets using duals of the non-weakly regular bent functions that are also bent. We note that the constructed linear codes are minimal in almost all cases. Moreover, when $f$ is a non-weakly regular bent function in a certain subclass of Generalized Maiorana-McFarland bent functions, we determine the weight distributions of the corresponding linear codes. As far as we know, the construction of linear codes from non-weakly regular bent functions over finite fields is first studied in the literature by the second author in his dissertation. [ABSTRACT FROM AUTHOR]

The mutual information (MI) of Gaussian multi-input multi-output (MIMO) channels has been evaluated by utilizing random matrix theory (RMT) and shown to asymptotically follow Gaussian distribution, where the ergodic mutual information (EMI) converges to a deterministic quantity. However, with non-Gaussian channels, there is a bias between the EMI and its deterministic equivalent (DE), whose evaluation is not available in the literature. This bias of the EMI is related to the bias for the trace of the resolvent in large RMT. In this paper, we first derive the bias for the trace of the resolvent, which is further extended to compute the bias for the linear spectral statistics (LSS). Then, we apply the above results on non-Gaussian MIMO channels to determine the bias for the EMI. It is also proved that the bias for the EMI is −0.5 times of that for the variance of the MI. Finally, the derived bias is utilized to modify the central limit theory (CLT) and calculate the outage probability. Numerical results show that the modified CLT significantly outperforms previous methods in approximating the distribution of the MI and improves the accuracy for the outage probability evaluation. [ABSTRACT FROM AUTHOR]

This paper deals with two typical random number generation problems in information theory. One is the source resolvability problem (resolvability problem for short) and the other is the intrinsic randomness problem. In the literature, optimum achievable rates in these two problems with respect to the variational distance as well as the Kullback-Leibler (KL) divergence have already been analyzed. On the other hand, in this study we consider these two problems with respect to $f$ -divergences. The $f$ -divergence is a general non-negative measure between two probabilistic distributions on the basis of a convex function $f$. The class of $f$ -divergences includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the random number generation problems with respect to $f$ -divergences. In this paper, we impose some conditions on the function $f$ so as to simplify the analysis, that is, we consider a subclass of $f$ -divergences. Then, we first derive general formulas of the first-order optimum achievable rates with respect to $f$ -divergences. Next, we particularize our general formulas to several specified functions $f$. As a result, we reveal that it is easy to derive optimum achievable rates for several important measures from our general formulas. The second-order optimum achievable rates and optimistic optimum achievable rates have also been investigated. [ABSTRACT FROM AUTHOR]

In this paper, a family of $[{q}^{2}-1, 4, {q}^{2}-{q}-2]$ cyclic codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2}-1,{q}^{2}-5,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of cyclic codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$. Some of the subfield codes are optimal and some have the best known parameters. It is shown that the subfield codes are equivalent to a family of primitive BCH codes and thus the parameters of the BCH codes are solved. The duals of the subfield codes are also optimal with respect to the sphere-packing bound. A family of $[{q}^{2}, 4, {q}^{2}-{q}-1]$ linear codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2},{q}^{2}-4,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of linear codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$. Five infinite families of 2-designs are also constructed with three families of linear codes of this paper. [ABSTRACT FROM AUTHOR]

The article presents the Preparation of Manuscripts, and Graphical Abstract.

The article offers information for authors regarding preparation and submission if articles to the periodical along with the editorial policy of the periodical, which include previous publication of submitted material; and table of contents.

The article provide information for authors in manuscripts in transactions on information theory.

The article presents the aims and objective of the periodical concerned with the transmission, processing and utilization of information, along with the copyright information of the periodical.

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM PUBLISHER]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM PUBLISHER]

This paper explores the network simplification problem for Gaussian full-duplex relay networks with arbitrary topology. Particularly, given an $N$ -relay Gaussian full-duplex network, the network simplification problem seeks to find fundamental guarantees on the capacity of the best subnetwork, among a particular class of subnetworks, as a fraction of the full-network capacity. The focus of this work is the case when the selected subnetwork class is a path from the source to the destination. The main result of the paper shows that for an $N$ -relay Gaussian networks with arbitrary topology, the best route can in the worst case guarantee an approximate fraction $\frac {1}{ \lfloor N/2 \rfloor + 1}$ of the capacity of the full network, independently of the channel coefficients and/or operating SNR. Furthermore, this guarantee is shown to be fundamental, i.e., it is the highest worst-case guarantee that can be provided for routing in relay networks. A key step in the proof of the main result lies in the derivation of a simplification result for antenna selection in MIMO channels that may also be of independent interest. To the best of our knowledge, this is the first result that characterizes the performance of routing in comparison to physical layer cooperation techniques that approximately achieve the network capacity for general wireless network topologies. The results in this paper show that routing can, in the worst case, result in an unbounded gap from the network capacity - or reversely, physical layer cooperation can offer unbounded gains over routing. [ABSTRACT FROM AUTHOR]

In literatures, there are various constructions of frequency hopping sequence (FHS for short) sets with good Hamming correlations. Some papers employed only multiplicative groups of finite fields to construct FHS sets, while other papers implicitly used only additive groups of finite fields for construction of FHS sets. In this paper, we make use of both multiplicative and additive groups of finite fields simultaneously to present a construction of optimal FHS sets. The construction provides a new family of optimal $\left ({{q}^{{m}}-1,\frac {{q}^{{m}-{t}}-1}{{r}},{\it{ rq}}^{{t}};\frac {{q}^{{m}-{t}}-1}{{r}}+1}\right)$ frequency hopping sequence sets archiving the Peng-Fan bound. Thus, some FHS sets constructed in literatures using either multiplicative groups or additive groups of finite fields are included in our family. In addition, some other FHS sets can be obtained via the well-known recursive construction through one-coincidence sequence set. [ABSTRACT FROM AUTHOR]

This paper considers multiplexing two sequences of messages with two different decoding delays over a packet erasure channel. In each time slot, the source constructs a packet based on the current and previous messages and transmits the packet, which may be erased when the packet travels from the source to the destination. The destination must perfectly recover every source message in the first sequence subject to a decoding delay ${T}_{\mathrm{ v}}$ and every source message in the second sequence subject to a shorter decoding delay ${T}_{\mathrm{ u}}\le {T}_{\mathrm{ v}}$. We assume that the channel loss model introduces a burst erasure of a fixed length B on the discrete timeline. Under this channel loss assumption, the capacity region for the case where ${T}_{\mathrm{ v}}\le {T}_{\mathrm{ u}}+{B}$ was previously solved. In this paper, we fully characterize the capacity region for the remaining case ${T}_{\mathrm{ v}}> {T}_{\mathrm{ u}}+{B}$. The key step in the achievability proof is achieving the non-trivial corner point of the capacity region through using a multiplexed streaming code constructed by superimposing two single-stream codes. The main idea in the converse proof is obtaining a genie-aided bound when the channel is subject to a periodic erasure pattern where each period consists of a length-B burst erasure followed by a length- ${T}_{\mathrm{ u}}$ noiseless duration. [ABSTRACT FROM AUTHOR]

Spectral factorization is an operation which appears in many different engineering applications. This paper studies whether spectral factorization can be algorithmically computed on an abstract machine (a Turing machine). It is shown that there exist computable spectral densities with very good analytic properties (i.e. smooth with finite energy) such that the corresponding spectral factor cannot be determined on a Turing machine. Further, it will be proved that it is impossible to decide algorithmically whether or not a given computable density possesses a computable spectral factor. This negative result has consequences for applications of spectral factorization in computer-aided design, because there it is necessary that this problem be decidable. Conversely, this paper will show that if the logarithm of a computable spectral density belongs to certain Sobolev space of sufficiently smooth functions, then the spectral factor is always computable. As an application, the paper discusses the possibility of calculating the optimal causal Wiener filter on an abstract machine. [ABSTRACT FROM AUTHOR]

In their seminal 1996 paper, Anantharam and Verdú showed that feedback does not increase the capacity of a queue under First-in-First-Out service policy and exponentially distributed service time. Since the channel has memory, this negative result raises the question whether it extends to other non-trivial combinations of service policy and service time. This paper addresses this question by providing two sufficient conditions under which feedback either increases capacity or does not increase capacity. The first is a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. The second is a sufficient condition for feedback not to increase capacity and is general in that it depends on the output distribution of the queue, but explicitly depends neither on the queue policy nor on the service time distribution. This condition is satisfied, for instance, by queues with Last-Come-First-Serve service policy and bounded service times. [ABSTRACT FROM AUTHOR]

The problem of recovering a pair of signals from their blind phaseless short-time Fourier transform measurements arises in several important phase retrieval applications, including ptychography and ultra-short pulse characterization. In this paper, we prove that in order to determine a pair of generic signals uniquely, up to trivial ambiguities, the number of phaseless measurements one needs to collect is, at most, five times the number of parameters required to describe the signals. This result improves significantly upon previous papers, which required the number of measurements to be quadratic in the number of parameters rather than linear. In addition, we consider the simpler problem of recovering a pair of generic signals from their blind short-time Fourier transform, when the phases are known. In this setting, which can be understood as a special case of the blind deconvolution problem, we show that the number of measurements required to determine the two signals, up to trivial ambiguities, equals exactly the number of parameters to be recovered. As a side result, we study the classical phase retrieval problem—that is, recovering a signal from its Fourier magnitudes—when some entries of the signal are known a priori. We derive a bound on the number of required measurements as a function of the size of the set of known entries. Specifically, we show that if most of the signal’s entries are known, then only a few Fourier magnitudes are necessary to determine a signal uniquely. [ABSTRACT FROM AUTHOR]

This paper studies an $n$ -dimensional additive Gaussian noise channel with a peak-power-constrained input. It is well known that, in this case, when $n=1$ the capacity-achieving input distribution is discrete with finitely many mass points, and when $n>1$ the capacity-achieving input distribution is supported on finitely many concentric shells. However, due to the previous proof technique, not even a bound on the exact number of mass points/shells was available. This paper provides an alternative proof of the finiteness of the number mass points/shells of the capacity-achieving input distribution while producing the first firm bounds on the number of mass points and shells, paving an alternative way for approaching many such problems. The first main result of this paper is an order tight implicit bound which shows that the number of mass points in the capacity-achieving input distribution is within a factor of two from the number of zeros of the downward shifted capacity-achieving output probability density function. Next, this implicit bound is utilized to provide a first firm upper on the support size of optimal input distribution, an $O(\mathsf {A}^{2})$ upper bound where $\mathsf {A}$ denotes the constraint on the input amplitude. The second main result of this paper generalizes the first one to the case when $n>1$ , showing that, for each and every dimension $n\ge 1$ , the number of shells that the optimal input distribution contains is $O(\mathsf {A}^{2})$. Finally, the third main result of this paper reconsiders the case $n=1$ with an additional average power constraint, demonstrating a similar $O(\mathsf {A}^{2})$ bound. [ABSTRACT FROM AUTHOR]

This paper aims to provide an optimization framework for coded caching that accounts for various heterogeneous aspects of practical systems. An optimization theoretic perspective on the seminal work on the fundamental limits of caching by Maddah-Ali and Niesen is first developed, whereas it is proved that the coded caching scheme presented in that work is the optimal scheme among a large, non-trivial family of possible caching schemes. The optimization framework is then used to develop a coded caching scheme capable of handling simultaneous non-uniform file length, non-uniform file popularity, and non-uniform user cache size. Although the resulting full optimization problem scales exponentially with the problem size, this paper shows that tractable simplifications of the problem that scale as a polynomial function of the problem size can still perform well compared to the original problem. By considering these heterogeneities both individually and in conjunction with one another, evidence of the effect of their interactions and influence on optimal cache content is obtained. [ABSTRACT FROM AUTHOR]

Caching is an efficient way to reduce network traffic congestion during peak hours, by storing some content at the user’s local cache memory, even without knowledge of user’s later demands. Maddah-Ali and Niesen proposed a two-phase (placement phase and delivery phase) coded caching strategy for broadcast channels with cache-aided users. This paper investigates the same model under the constraint that content is placed uncoded within the caches, that is, when bits of the files are simply copied within the caches. When the cache contents are uncoded and the users’ demands are revealed, the caching problem can be connected to an index coding problem. This paper focuses on deriving fundamental performance limits for the caching problem by using tools for the index coding problem that were either known or are newly developed in this work. First, a converse bound for the caching problem under the constraint of uncoded cache placement is proposed based on the “acyclic index coding converse bound.” This converse bound is proved to be achievable by the Maddah-Ali and Niesen’s scheme when the number of files is not less than the number of users, and by a newly derived index coding achievable scheme otherwise. The proposed index coding achievable scheme is based on distributed source coding and strictly improves on the widely used “composite (index) coding” achievable bound and its improvements, and is of independent interest. An important consequence of the findings of this paper is that advancements on the coded caching problem posed by Maddah-Ali and Niesen are thus only possible by considering strategies with coded placement phase. A recent work by Yu et al has however shown that coded cache placement can at most half the network load compared to the results presented in this paper. [ABSTRACT FROM AUTHOR]

Given a ${q}$ -ary frequency hopping sequence set of length ${n}$ and size ${M}$ with Hamming correlation ${H}$ , one can obtain a ${q}$ -ary (nonlinear) cyclic code of length ${n}$ and size nM with Hamming distance n-H. Thus, every upper bound on the size of a code from coding theory gives an upper bound on the size of a frequency hopping sequence set. Indeed, all upper bounds from coding theory have been converted to upper bounds on frequency hopping sequence sets. On the other hand, a lower bound from coding theory does not automatically produce a lower bound for frequency hopping sequence sets. In particular, the most important lower bound, the Gilbert-Varshamov bound in coding theory, has not been transformed to a valid lower bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov bound. One is based on a probabilistic method that requires advanced tool–martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region. [ABSTRACT FROM AUTHOR]

It has been proved that for all stationary and ergodic processes the average Kolmogorov complexity of the first $n$ observations converges almost surely to its Shannon’s conditional entropy. This paper studies the convergence rate of this asymptotic result. In particular, we show that if the process satisfies certain mixing conditions, then a central limit theorem will be respected. Furthermore, we show that under slightly stronger mixing conditions one may obtain non-asymptotic concentration bounds for the Kolmogorov complexity. [ABSTRACT FROM AUTHOR]

Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. The main result is the justification of state evolution (SE) equations conjectured by Ma and Ping. This result implies that the EP-based algorithm achieves the Bayes-optimal performance that was originally derived via a non-rigorous tool in statistical physics and proved partially in a recent paper, when the compression rate is larger than a threshold. The proof is based on an extension of a conventional conditioning technique for the standard Gaussian matrix to the case of the Haar matrix. [ABSTRACT FROM AUTHOR]

Locally repairable codes, or locally recoverable codes (LRC for short), are designed for applications in distributed and cloud storage systems. Similar to classical block codes, there is an important bound called the Singleton-type bound for locally repairable codes. In this paper, an optimal locally repairable code refers to a block code achieving this Singleton-type bound. Like classical MDS codes, optimal locally repairable codes carry some very nice combinatorial structures. Since the introduction of the Singleton-type bound for locally repairable codes, people have put tremendous effort into construction of optimal locally repairable codes. There are a few constructions of optimal locally repairable codes in the literature. Most of these constructions are realized via either combinatorial or algebraic structures. In this paper, we apply automorphism group of the rational function field to construct optimal locally repairable codes by considering the group action on projective lines over finite fields. Due to various subgroups of the projective general linear group, we are able to construct optimal locally repairable codes with flexible locality as well as smaller alphabet size comparable to the code length. In particular, we produce new families of $q$ -ary locally repairable codes, including codes of length $q+1$ via cyclic groups. [ABSTRACT FROM AUTHOR]

Locally repairable codes with more than one recovering set are demanded in the application to distributed storage. For each failure node (or disk), it is desired to have as many recovering sets as possible. In this paper, we make use of automorphisms of rational function fields to construct locally repairable codes with multiple recovering sets. Although we focus on two recovering sets, our construction can be easily generalized to the case of multiple recovering sets. In particular, we obtain a class of locally repairable codes with minimum distance only 1 less than the upper bound. [ABSTRACT FROM AUTHOR]

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of $\ell $ nodes. An $(n,k,d,\ell)$ secure exact-repair regenerating code is an $(n,k,d)$ exact-repair regenerating code that is secure under this eavesdropping model. It has been shown that for some parameters $(n,k,d,\ell)$ , the associated optimal storage-bandwidth tradeoff curve, which has one corner point, can be determined. The focus of this paper is on characterizing such parameters. We establish a lower bound $\hat {\ell }$ on the number of wiretap nodes, and show that this bound is tight for the case $k = d = n-1$. [ABSTRACT FROM AUTHOR]

Locally recoverable codes are very important due to their applications in distributed storage systems. In this paper, by using cyclic codes, we construct two classes of optimal q-ary cyclic $(\text {r}, \delta _{1})$ locally recoverable codes with parameters $[2(\text {q}+1), 2(\text {q}+1)-2\delta _{1}, \delta _{1}+2]_{\text {q}}$ , where $q$ is an odd prime power and $\text {r}+\delta _{1}-1=\text {q}+1$ , and $(\text {r}, \delta _{2})$ locally recoverable codes with parameters $[2(\text {q}+1), 2(\text {q}+1)-4\delta _{2}+2, \delta _{2}+2]_{q}$ , where $\text {q}\geq 7$ is an odd prime power, $\text {q}\equiv 3~ (mod~ 4)$ and $r+\delta _{2}-1=\frac {\text {q}+1}{2}$. Compared with the known cyclic and constacyclic $(\text {r}, \delta)$ locally recoverable codes, our construction yields new optimal cyclic $(\text {r}, \delta)$ locally recoverable codes. [ABSTRACT FROM AUTHOR]

Blind deconvolution is a ubiquitous problem aiming to recover a convolution kernel $\boldsymbol a_{0}\in \mathbb R ^{k}$ and an activation signal $\boldsymbol x_{0}\in \mathbb R ^{m}$ from their convolution $\boldsymbol y\in \mathbb R ^{m}$. Unfortunately, this is an ill-posed problem in general. This paper focuses on the short and sparse blind deconvolution problem, where the convolution kernel is short ($k\ll m$) and the activation signal is sparsely and randomly supported ($\left \|{ \boldsymbol x_{0} }\right \|_{0}\ll m$). This variant captures the structure of the convolutional signals in several important application scenarios. In this paper, we normalize the convolution kernel to have unit Frobenius norm and then cast the blind deconvolution problem as a nonconvex optimization problem over the kernel sphere. We demonstrate that (i) in a certain region of the sphere, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic unit kernel $\boldsymbol a_{0}$ , when the sparsity of activation signal satisfies $\theta \lesssim k^{-2/3}$ and number of measurements $m\gtrsim \mathop {\mathrm {poly}}\nolimits \left ({k }\right) $ , the proposed initialization method together with a descent algorithm which escapes strict saddle points recovers some shift truncation of the ground truth kernel. [ABSTRACT FROM AUTHOR]

This paper studies the two-user causal cognitive interference channel (CCIC), where two transmitters aim to communicate independent messages to two different receivers via a common channel. One source, referred to as the cognitive, is capable of overhearing the other source, referred to as the primary, through a noisy in-band link and thus can assist in sending the primary’s data. The authors of this paper recently characterized to within a constant gap the capacity of the symmetric Gaussian CCIC in: 1) the strong interference regime and 2) for a subset of the weak interference regime when the cooperation link is larger than a given threshold. This paper characterizes to within a constant gap the capacity for the symmetric Gaussian CCIC in the regime that was still open. To this end, two novel outer bounds of the types 2 R\mathsf {p}+ R\mathsf {c} and R\mathsf {p}+2 R\mathsf {c} are derived for the class of injective semideterministic CCICs, where the noises at the different source-destination pairs are independent. These outer bounds, as well as an achievable rate region based on Gelfand-Pinsker binning, superposition coding, and simultaneous decoding at the receivers, are then specialized to the Gaussian noise case. It is shown that the novel outer bounds are necessary to characterize the capacity within a constant gap when the cooperation link is weaker than the direct links, that is, in this regime unilateral cooperation leaves some system resources underutilized. [ABSTRACT FROM PUBLISHER]

This paper examines the close interplay between cooperation and adaptation for distributed detection schemes over fully decentralized networks. The combined attributes of cooperation and adaptation are necessary to enable networks of detectors to continually learn from streaming data and to continually track drifts in the state of nature when deciding in favor of one hypothesis or another. The results in this paper establish a fundamental scaling law for the steady-state probabilities of miss detection and false alarm in the slow adaptation regime, when the agents interact with each other according to distributed strategies that employ small constant step-sizes. The latter are critical to enable continuous adaptation and learning. This paper establishes three key results. First, it is shown that the output of the collaborative process at each agent has a steady-state distribution. Second, it is shown that this distribution is asymptotically Gaussian in the slow adaptation regime of small step-sizes. Third, by carrying out a detailed large deviations analysis, closed-form expressions are derived for the decaying rates of the false-alarm and miss-detection probabilities. Interesting insights are gained from these expressions. In particular, it is verified that as the step-size $\mu $ decreases, the error probabilities are driven to zero exponentially fast as functions of $1/\mu $ , and that the exponents governing the decay increase linearly in the number of agents. It is also verified that the scaling laws governing the errors of detection and the errors of estimation over the network behave very differently, with the former having exponential decay proportional to $1/\mu $ , while the latter scales linearly with decay proportional to $\mu $ . Moreover, and interestingly, it is shown that the cooperative strategy allows each agent to reach the same detection performance, in terms of detection error exponents, of a centralized stochastic-gradient solution. The results of this paper are illustrated by applying them to canonical distributed detection problems. [ABSTRACT FROM PUBLISHER]

This paper studies the problem of information symbol availability in codes: we refer to a systematic code as code with $(r, t)$ -availability if every information (systematic) symbol can be reconstructed from $t$ disjoint groups of other code symbols, each of the sizes at most $r$ . This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum Hamming distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a tradeoff between rate, minimum Hamming distance, and availability parameters. Our codes match the aforementioned bound, and their constructions rely on certain combinatorial structures. Resolvable designs provide one way to realize these required combinatorial structures. The two constructions presented in this paper require field sizes, which are linear and exponential in the code length, respectively. From a practical standpoint, our codes are relevant for distributed storage applications involving hot data, i.e., the information, which is frequently accessed by multiple processes in parallel. [ABSTRACT FROM AUTHOR]

This paper studies networks that consist of $N$ half-duplex relays assisting the communication between a source and a destination. In ISIT’12 Brahma et al. conjectured that in Gaussian half-duplex diamond networks (i.e., without a direct link between the source and the destination, and with N$ non-interfering relays), an approximately optimal relay scheduling policy (i.e., achieving the cut-set upper bound to within a constant gap uniformly over all channel gains) has at most N+1$ active states (i.e., at most N+1 possible relay listen-transmit configurations have a strictly positive probability). Such relay scheduling policies were referred to as simple. In ITW’13, we conjectured that simple approximately optimal relay scheduling policies exist for any Gaussian half-duplex multi-relay network irrespectively of the topology. This paper formally proves this more general version of the conjecture and shows it holds beyond Gaussian noise networks. In particular, for any class of memoryless half-duplex $N$ -relay networks with independent noises and for which independent inputs are approximately optimal in the cut-set upper bound, an approximately optimal simple relay scheduling policy exists. The key step of the proof is to write the minimum of the submodular cut-set function by means of its Lovász extension and use the greedy algorithm for submodular polyhedra to highlight structural properties of the optimal solution. This, together with the saddle-point property of min–max problems and the existence of optimal basic feasible solutions for linear programs, proves the conjecture. As an example, for $N$ -relay Gaussian networks with independent noises, where each node is equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most $N+1$ active states, irrespectively of the total number of antennas in the system, is proved. [ABSTRACT FROM PUBLISHER]

Index coding studies multiterminal source-coding problems where a set of receivers are required to decode multiple (possibly different) messages from a common broadcast, and they each know some messages a priori. In this paper, at the receiver end, we consider a special setting where each receiver knows only one message a priori, and each message is known to only one receiver. At the broadcasting end, we consider a generalized setting where there could be multiple senders, and each sender knows a subset of the messages. The senders collaborate to transmit an index code. This paper looks at minimizing the number of total coded bits the senders are required to transmit. When there is only one sender, we propose a pruning algorithm to find a lower bound on the optimal (i.e., the shortest) index codelength, and show that it is achievable by linear index codes. When there are two or more senders, we propose an appending technique to be used in conjunction with the pruning technique to give a lower bound on the optimal index codelength; we also derive an upper bound based on cyclic codes. While the two bounds do not match in general, for the special case where no two distinct senders know any message in common, the bounds match, giving the optimal index codelength. The results are expressed in terms of strongly connected components in directed graphs that represent the index-coding problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast- $Z$ network is a two-unicast network where the destination intending to decode the second message has a priori side information of the first message. We make three contributions in this paper. First, we describe a new linear network coding algorithm for two-unicast-Z networks over the directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For the graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and the polynomial complexity in terms of the number of edges. Second, we prove that our algorithm achieves the rate pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over the directed acyclic graphs, to an earlier result of Wang et al., which studied the necessary and sufficient conditions for the feasibility of the rate pair (1, 1) in two-unicast networks. Third, we provide a new proof of the classical max-flow min-cut theorem for the directed acyclic graphs. [ABSTRACT FROM AUTHOR]

This paper shows that for the two-user Gaussian interference channel (G-IC) treating interference as noise without time sharing (TINnoTS) achieves the closure of the capacity region to within either a constant gap, or to within a gap of the order O(\log (\ln (\min ( \mathsf S, \mathsf I))/\gamma )) up to a set of Lebesgue measure \gamma \in (0,1] , where {\mathsf {S}} is the largest signal to noise ratio on the direct links and {\mathsf {I}}$ is the largest interference to noise ratio on the cross links. As a consequence, TINnoTS is optimal from a generalized degrees of freedom (gDoF) perspective for all channel gains except for a subset of zero measure. TINnoTS with Gaussian inputs is known to be optimal within 1/2 bit for a subset of the weak interference regime. Rather surprisingly, this paper shows that TINnoTS is gDoF optimal in all parameter regimes, even in the strong and very strong interference regimes where joint decoding of Gaussian inputs is optimal. For approximate optimality of TINnoTS in all parameter regimes, it is critical to use non-Gaussian inputs. This paper thus proposes to use mixed inputs as channel inputs for the G-IC, where a mixed input is the sum of a discrete and a Gaussian random variable. Interestingly, with reference to the Han–Kobayashi achievable scheme, the discrete part of a mixed input is shown to effectively behave as a common message in the sense that, although treated as noise, its effect on the achievable rate region is as if it were jointly decoded together with the desired messages at a non-intended receiver. The practical implication is that a discrete interfering input is a friend, while an Gaussian interfering input is in general a foe. This paper also discusses other practical implications of the proposed TINnoTS scheme with mixed inputs. Since TINnoTS requires neither explicit joint decoding nor time sharing, the results of this paper are applicable to a variety of oblivious or asynchronous channels, such as the block asynchronous G-IC (which is not an information stable channel) and the G-IC with partial codebook knowledge at one or more receivers. [ABSTRACT FROM AUTHOR]

This paper introduces Manhattan sampling in two and higher dimensions, and proves sampling theorems for them. In 2-D, Manhattan sampling, which takes samples densely along a Manhattan grid of lines, can be viewed as sampling on the union of two rectangular lattices, one dense horizontally and the other vertically, with the coarse spacing of each being a multiple of the fine spacing of the other. The sampling theorem shows that the images bandlimited to the union of the Nyquist regions of the two rectangular lattices can be recovered from their Manhattan samples, and an efficient procedure for doing so is given. Such recovery is possible even though there is an overlap among the spectral replicas induced by Manhattan sampling. In three and higher dimensions, there are many possible configurations for Manhattan sampling, each consisting of the union of special rectangular lattices called bi-step lattices. This paper identifies them, proves a sampling theorem showing that the images bandlimited to the union of the Nyquist regions of the bi-step rectangular lattices are recoverable from Manhattan samples, presents an efficient onion-peeling procedure for doing so, and shows that the union of Nyquist regions is as large as any bandlimited region, such that all images supported by such can be stably reconstructed from samples taken at the rate of the Manhattan sampling. It also develops a special representation for the bi-step lattices with a number of useful properties. While most of this paper deals with continuous-space images, Manhattan sampling of discrete-space images is also considered, for infinite, as well as finite, support images. [ABSTRACT FROM AUTHOR]

In this paper, we study a security problem on a simple wiretap network, consisting of a source node S, a destination node D, and an intermediate node R. The intermediate node connects the source and the destination nodes via a set of noiseless parallel channels, with sizes n1 and n2 , respectively. A message $M$ is to be sent from S to D. The information in the network may be eavesdropped by a set of wiretappers. The wiretappers cannot communicate with one another. Each wiretapper can access a subset of channels, called a wiretap set. All the chosen wiretap sets form a wiretap pattern. A random key $K$ is generated at S, and a coding scheme on $(M, K)$ is employed to protect $M$ . We define two decoding classes at D. In Class-I, only $M$ is required to be recovered, and in Class-II, both $M$ and $K$ are required to be recovered. The objective is to minimize $H(K)/H(M)$ for a given wiretap pattern under the perfect secrecy constraint. The first question we address is whether routing is optimal on this simple network. By enumerating all the wiretap patterns on the Class-I/II (3, 3) networks and harnessing the power of Shannon-type inequalities, we find that gaps exist between the bounds implied by routing and the bounds implied by Shannon-type inequalities for a small fraction (<2%) of all the wiretap patterns. The second question we investigate is the following: What is $\min H(K)/H(M)$ for the remaining wiretap patterns where gaps exist? We study some simple wiretap patterns and find that their Shannon bounds (i.e., the lower bound induced by Shannon-type inequalities) can be achieved by linear codes, which means routing is not sufficient even for the (3, 3) network. For some complicated wiretap patterns, we study the structures of linear coding schemes under the assumption that they can achieve the corresponding Shannon bounds. This paper indicates that the determination of the entropic region of six linear vector spaces cannot be sidestepped. Some subtle issues on the network models are discussed, and interesting observations are stated. [ABSTRACT FROM AUTHOR]

In this paper, we derive non-asymptotic achievability and converse bounds on the random number generation with/without side-information. Our bounds are efficiently computable in the sense that the computational complexity does not depend on the block length. We also characterize the asymptotic behaviors of the large deviation regime and the moderate deviation regime by using our bounds, which implies that our bounds are asymptotically tight in those regimes. We also show the second-order rates of those problems, and derive single letter forms of the variances characterizing the second-order rates. Furthermore, we address the relative entropy rate and the modified mutual information rate for these problems. [ABSTRACT FROM AUTHOR]

In this paper, we determine the entire secure degrees of freedom (s.d.o.f.) regions of the $K$ -user Gaussian multiple access (MAC) wiretap channel and the $K$ -user interference channel (IC) with secrecy constraints. For the IC, we consider three secrecy constraints: K-user IC with an external eavesdropper (IC-EE), K-user IC with confidential messages (IC-CM), and their combination Kuser IC with confidential messages and external eavesdropper (IC-CM-EE). The converse for the IC includes constraints both due to secrecy as well as due to interference. For the IC, although the portion of the region close to the optimum sum s.d.o.f. point is governed by the upper bounds due to secrecy constraints, the other portions of the region are governed by the upper bounds due to interference constraints. Different from the existing literature, in order to fully understand the characterization of the s.d.o.f. region of the IC, one has to study the four-user case, i.e., the two- or three-user cases do not illustrate the full generality of the problem. In order to prove the achievability, we use the polytope structure of the converse region. In both MAC and IC cases, we develop explicit schemes that achieve the extreme points of the polytope region given by the converse. In particular, the extreme points of the MAC region are achieved by an $m$ -user MAC wiretap channel with $K-m$ helpers, i.e., by setting $K-m$ users’ secure rates to zero and utilizing them as pure (structured) cooperative jammers. The extreme points of the IC region are achieved by a $(K-m)$ -user IC with confidential messages, $m$ helpers, and $N$ external eavesdroppers, for $m\ge 1$ and a finite $N$ . A byproduct of our results in this paper is that the sum s.d.o.f. is achieved only at one extreme point of the s.d.o.f. region, which is the symmetric-rate extreme point, for both MAC and IC channel models. [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]

This paper focuses on status age, which is a metric for measuring the freshness of a continually updated piece of information (i.e., status) as observed at a remote monitor. In paper, we study a system in which a sensor sends random status updates over a dynamic network to a monitor. For this system, we consider the impact of having messages take different routes through the network on the status age. First, we consider a network with plentiful resources (i.e., many nodes that can provide numerous alternate paths), so that packets need not wait in queues at each node in a multihop path. This system is modeled as a single queue with an infinite number of servers, specifically as an $M/M/\infty $ queue. Packets routed over a dynamic network may arrive at the monitor out of order, which we account for in our analysis for the $M/M/\infty $ model. We then consider a network with somewhat limited resources, so that packets can arrive out of order but also must wait in a queue. This is modeled as a single queue with two servers, specifically an $M/M/2$ queue. We present the exact approach to computing the analytical status age, and we provide an approximation that is shown to be close to the simulated age. We also compare both models with $M/M/1$ , which corresponds to severely limited network resources, and we demonstrate the tradeoff between the status age and the unnecessary network resource consumption. [ABSTRACT FROM AUTHOR]

In this paper, we study a new model of defect memory cells, called partially stuck-at memory cells, which is motivated by the behavior of multi-level cells in non-volatile memories, such as flash memories and phase change memories. If a cell can store the q levels 0, 1, {\dots }, q-1 , we say that it is partially stuck-at level s$ , where $1 \leq s \leq q-1$ , if it can only store values, which are at least $s$ . We follow the common setup where the encoder knows the positions and levels of the partially stuck-at cells whereas the decoder does not. Our main contribution in this paper is the study of codes for masking $u$ partially stuck-at cells. We first derive lower and upper bounds on the redundancy of such codes. The upper bounds are based on two trivial constructions. We then present three code constructions over an alphabet of size $q$ , by first considering the case where the cells are partially stuck-at level $s=1$ . The first construction works for $u

Information retrieval in associative memories was studied in a recent paper by Yaakobi and Bruck (2012). Associations between memory entries give us the t -neighbourhood of an entry. In their model, an information unit is retrieved from the memory with the aid of input clues, which are chosen from a reference set. In this paper, we consider the situation where the information unit is found unambiguously using the associated t -neighbourhoods of the input clues. A varying number of input clues are allowed, but a limit mu on the maximum number of them is imposed. Of course, we would like mu to be as small as possible. We consider the problem over the binary Hamming space \mathbb F^n and focus on the minimum of mu , denoted by $\nu (n;t)$ . Using linear reference sets, we show that $\nu (n;2) \leq 5$ for any $n \geq 9$ . We also give infinite families of reference sets, which provide good bounds on $\nu (n;t)$ for $t=3$ . In addition, efficient methods are given to obtain bounds on $\nu (n;t)$ for any $t$ from known reference sets. We also discuss the applications of this model to the Levenshtein’s sequence reconstruction problem and the sensor network monitoring. [ABSTRACT FROM AUTHOR]

This paper starts by considering the minimization of the Rényi divergence subject to a constraint on the total variation distance. Based on the solution of this optimization problem, the exact locus of the points \bigl ( D(Q\|P1), D(Q\|P2) \bigr ) is determined when P1 , P2 , and $Q$ are arbitrary probability measures which are mutually absolutely continuous, and the total variation distance between P1 and P2 is not below a given value. It is further shown that all the points of this convex region are attained by probability measures which are defined on a binary alphabet. This characterization yields a geometric interpretation of the minimal Chernoff information subject to a constraint on the variational distance. This paper also derives an exponential upper bound on the performance of binary linear block codes (or code ensembles) under maximum-likelihood decoding. Its derivation relies on the Gallager bounding technique, and it reproduces the Shulman–Feder bound as a special case. The bound is expressed in terms of the Rényi divergence from the normalized distance spectrum of the code (or the average distance spectrum of the ensemble) to the binomially distributed distance spectrum of the capacity-achieving ensemble of random block codes. This exponential bound provides a quantitative measure of the degradation in performance of binary linear block codes (or code ensembles) as a function of the deviation of their distance spectra from the binomial distribution. An efficient use of this bound is considered. [ABSTRACT FROM PUBLISHER]

In this paper, we provide a comprehensive survey on designs and analyses of various relay-destination transceiving schemes, such as zero-forcing (ZF), minimum mean squared error (MMSE), and maximum information rate (MIR) criteria, in multiple-input multiple-output (MIMO) amplify-and-forward (AF) relaying systems. In the first part of the paper, we suggest a new framework for the transceiver designs utilizing a decomposable property of the error covariance matrix to give a general insight on the system and make the analysis more tractable. Then, in the second part of the paper, we provide an in-depth analysis on their diversity performance. Our analysis embraces two different scenarios, namely, the diversity-multiplexing tradeoff (DMT) and the diversity-rate tradeoff (DRT). First, we derive compact closed-form expressions for the DMT through tight upper and lower bounds. Then, we observe that while our DMT analysis accurately predicts performance of the ZF and MIR schemes, the MMSE-based designs exhibit a complicated rate-dependent behavior and, thus, are very unpredictable via DMT for finite rate cases. Thus, second, we highlight this interesting observation and characterize the diversity of the MMSE schemes at all finite rates. This leads to closed-form expressions for the DRT which reveals relationship between diversity, spectral efficiency, and the number of antennas at each node. The DRT analysis compliments our work on DMT, and thus, the paper provides a complete understanding on the diversity of MIMO AF relaying systems. [ABSTRACT FROM PUBLISHER]

This paper elucidates the underlying structures of \ell p -regularized least squares problems in the nonconvex case of 0

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. [ABSTRACT FROM AUTHOR]