Search

In this paper, the large family of generalized Kasami sequences has been studied. In particular, the cross-correlation distribution among these sequences has been explicitly calculated. Meanwhile, the weight distributions of two classes of cyclic codes could also be determined. This paper generalizes the results from several previous papers. [ABSTRACT FROM AUTHOR]

The capacity region of a class of discrete memoryless interference channels with common information is established. The setup is similar to the class of deterministic interference channels without common information studied by El Gamal and Costa, which was later extended to the class of deterministic interference channels with common information. In this paper, certain conditions that were originally imposed by El Gamal and Costa are relaxed and it is shown, by a specific example, that this new class of interference channels is strictly larger than the class of deterministic interference channels previously studied. In fact, the result of this paper is obtained by combining the class of deterministic interference channels with the class of discrete memoryless interference channels with strong interference. Hence, it also includes the capacity region of the class of discrete memoryless interference channels with strong interference as a special case. [ABSTRACT FROM AUTHOR]

In this paper, a coding-theory construction of Cartesian authentication codes is presented. The construction is a generalization of some known constructions. Within the framework of this generic construction, several classes of authentication codes using certain classes of error-correcting codes are described. The authentication codes presented in this paper are better than known ones with comparable parameters. It is demonstrated that the construction is related to certain combinatorial designs, such as difference matrices and generalized Hadamard matrices. [ABSTRACT FROM AUTHOR]

In this paper, a special class of wireless networks, called wireless erasure networks, is considered. In these networks, each node is connected to a set of nodes by possibly correlated erasure channels. The network model incorporates the broadcast nature of the wireless environment by requiring each node to send the same signal on all outgoing channels. However, we assume there is no interference in reception. Such models are therefore appropriate for wireless networks where all information transmission is packetized and where some mechanism for interference avoidance is already built in. This paper looks at multicast problems over these networks. The capacity under the assumption that erasure locations on all the links of the network are provided to the destinations is obtained. It turns out that the capacity region has a nice max-flow mm-cut interpretation. The definition of cut-capacity in these networks incorporates the broadcast property of the wireless medium. It is further shown that linear coding at nodes in the network suffices to achieve the capacity region. Finally, the performance of different coding schemes in these networks when no side information is available to the destinations is analyzed. [ABSTRACT FROM AUTHOR]

The capacity of a particular large Gaussian relay network is determined the limit as the number of relays tends to infinity. Upper bounds are derived from cut-set arguments, and lower bounds follow from an argument involving uncoded transmission. It is shown that in cases of interest, upper and lower bounds coincide in the limit as the number of relays tends to infinity. Hence, this paper provides a new example where a simple cut-set upper bound is achievable , and one more example where uncoded transmission achieves optimal performance. The findings are illustrated by geometric interpretations. The techniques developed in this paper are then applied to a sensor network situation. This is a network joint source-channel coding problem, and it is well known that the source-channel separation theorem does not extend to this case. The present paper extends this insight by providing an example where separating source from channel coding does not only lead to suboptimal performance-it leads to an exponential penalty in performance scaling behavior (as a function of the number of nodes). Finally, the techniques developed in this paper are extended to included certain models of ad hoc wireless network, where a capacity scaling law can be established: When all nodes act purely as relays for a single sources-destination pair, capacity grows with the logarithm of the number of nodes. [ABSTRACT FROM AUTHOR]

Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding, and representable discrete polymatroids. We consider the vector linear solutions of networks over a field \mathbb Fq , with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. It is well known that a scalar linear solution over \mathbb Fq exists for a network if and only if the network is matroidal with respect to a matroid representable over \mathbb Fq . We define a discrete polymatroidal network and show that a linear fractional solution over a field \mathbb Fq exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over \mathbb Fq . An algorithm to construct the networks starting from certain class of discrete polymatroids is provided. Every representation over \mathbb Fq for the discrete polymatroid, results in a linear fractional solution over \mathbb Fq for the constructed network. Next, we consider the index coding problem, which involves a sender, which generates a set of messages X=\x1,x2,\dotso xk\ , and a set of receivers \mathcal R , which demand messages. A receiver R \in \mathcal R is specified by the tuple $(x,H)$ , where x \in X$ is the message demanded by R$ and is the side information possessed by $R$ . We first show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid, satisfying certain conditions, which are determined by the index coding problem considered. Rouayheb et al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. The multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of Rouayheb et al., by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid. [ABSTRACT FROM PUBLISHER]

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver, since the battery will drain during intervals with low signal energy. In this paper, we analyze subblock energy-constrained codes (SECCs), which ensure that sufficient energy is carried within every subblock duration. We consider discrete memoryless channels and characterize the SECC capacity and the SECC error exponent, and provide useful bounds for these values. We also study constant subblock-composition codes (CSCCs), which are a subclass of SECCs where all the subblocks in every codeword have the same fixed composition, and this subblock composition is chosen to maximize the rate of information transfer while meeting the energy requirement. Compared with constant composition codes (CCCs), we show that CSCCs incur a rate loss and that the error exponent for CSCCs is also related to the error exponent for CCCs by the same rate loss term. We exploit the symmetry in CSCCs to obtain a necessary and sufficient condition on the subblock length for avoiding power outage at the receiver. Furthermore, for CSCC sequences, we present a tight lower bound on the average energy per symbol within a sliding time window. We provide numerical examples highlighting the tradeoff between the delivery of sufficient energy to the receiver and achieving high information transfer rates. It is observed that the ability to use energy in real-time imposes less of penalty compared with the ability to use information in real-time. [ABSTRACT FROM PUBLISHER]

Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature—via simulation and via instanton analysis—that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding’s high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders—ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with \ell 1 and \ell 2 penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs. [ABSTRACT FROM AUTHOR]

A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert–Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets. [ABSTRACT FROM AUTHOR]

This paper investigates various subtleties of applying linear physical-layer network coding (PNC) with $q$ -level pulse amplitude modulation ( $q$ -PAM) in two-way relay channels. A critical issue is how the PNC system performs when the received powers from the two users at the relay are imbalanced. In particular, how would the PNC system perform under slight power imbalance that is inevitable in practice, even when power control is applied? To answer these questions, this paper presents a comprehensive analysis of $q$ -PAM PNC. Our contributions are as follows. First, we give a systematic way to obtain the analytical relationship between the minimum distance of the signal constellation induced by the superimposed signals of the two users (a key performance determining factor) and the channel-gain ratio of the two users, for all $q$ . In particular, we show how the minimum distance changes in a piecewise linear fashion as the channel-gain ratio varies. Second, we show that the performance of $q$ -PAM PNC is highly sensitive to imbalanced received powers from the two users at the relay, even when the power imbalance is slight (e.g., the residual power imbalance in a power-controlled system). This sensitivity problem is exacerbated as $q$ increases, calling into question the robustness of high-order modulated PNC. Third, we propose an asynchronized PNC system in which the symbol arrival times of the two users at the relay are deliberately made to be asynchronous. We show that such asynchronized PNC, when operated with a belief propagation decoder, can remove the sensitivity problem, allowing a robust high-order modulated PNC system to be built. [ABSTRACT FROM AUTHOR]

This paper presents an outage analysis for a two-user parallel Gaussian interference channel consisting of two sub-channels. Each sub-channel is modeled as a two-user Gaussian interference channel with quasi-static and flat fading. Both users employ single-layer Gaussian code-books and maintain a statistical correlation \rho between the signals transmitted over the underlying sub-channels. When joint decoding (JD) is performed at the receivers, setting \rho =0 minimizes the outage probability, regardless of the value of the signal-to-noise ratio (SNR). It is shown, however, that if the receivers treat interference as noise (TIN) or cancel interference (CI), the value of optimum \rho approaches 1 as SNR goes to infinity. Motivated by these observations, we let \rho =0 under JD and \rho =1 , it is shown that the outage probability scales like \mathrm snr^-(1-r) under both TIN and CI, while it vanishes at least as fast as \mathrm snr^-\min \2-r,4(1-r)\\log \mathrm snr under JD. This paper is concluded by extending some of the results to a two-user parallel Gaussian interference channel with an arbitrary number of sub-channels. [ABSTRACT FROM AUTHOR]

This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide. [ABSTRACT FROM AUTHOR]

In this paper, we provide a solution to the open problem of computing the Fourier transform of a binary function defined over n -bit vectors taking m -bit vector values. In particular, we introduce the two-modular Fourier transform (TMFT) of a binary function f:G\rightarrow \mathcal R , where G = (\mathbb F2^{n},+) is the group of n bit vectors with bitwise modulo two addition +, and {\mathcal{ R}} is a finite commutative ring of characteristic 2. Using the specific group structure of G and a sequence of nested subgroups of G , we define the fast TMFT and its inverse. Since the image {\mathcal{ R}} of the binary functions is a ring, we can define the convolution between two functions f:G\rightarrow {\mathcal{ R}}$ . We then provide the TMFT properties, including the convolution theorem, which can be used to efficiently compute convolutions. Finally, we derive the complexity of the fast TMFT and the inverse fast TMFT. [ABSTRACT FROM AUTHOR]

This paper studies an untrusted relay channel, in which the destination sends artificial noise simultaneously with the source sending a message to the relay, in order to protect the source’s confidential message. The traditional amplify-and-forward (AF) scheme shows poor performance in this situation because of the interference power dilemma. Providing better security by using stronger artificial noise will consume more power of the relay, impairing the confidential message’s transmission. To solve this problem, this paper proposes a modulo-and-forward (MF) operation at the relay with nested lattice encoding at the source. For the proposed MF scheme with full channel state information at the transmitter (CSIT), theoretical analysis shows that the MF scheme approaches the secrecy capacity within 1/2 bit for all channel realizations, and, hence, achieves full generalized security degrees of freedom (G-SDoF). In contrast, the AF scheme can only achieve a small fraction of the G-SDoF. For the MF scheme without CSIT, the total outage event, defined as either connection outage or secrecy outage, is introduced. Based on this total outage definition, analysis shows that the proposed MF scheme achieves the full generalized secure diversity gain (G-SDG) of order one. On the other hand, the AF scheme can achieve a G-SDG of only 1/2 at most. [ABSTRACT FROM AUTHOR]

We propose two coding schemes for the two-receiver discrete memoryless broadcast channel (BC) with rate-limited feedback from one or both receivers. They improve over the no feedback capacity region for a large class of channels, including the class of strictly essentially less-noisy BCs that we introduce in this paper. Examples of strictly essentially less-noisy BCs are the binary symmetric BC or the binary erasure BC with unequal crossover or erasure probabilities at the two receivers. When the feedback rates are sufficiently large, our schemes recover all previously known capacity results for discrete memoryless BCs with feedback. In both our schemes, we let the receivers feedback quantization messages about their receive signals. In the first scheme, the transmitter simply relays the quantization information obtained from Receiver 1 to Receiver 2, and vice versa. This provides each receiver with a second observation of the input signal and can thus improve its decoding performance unless the BC is physically degraded. Moreover, each receiver uses its knowledge of the quantization message describing its own outputs so as to attain the same performance as if this message had not been transmitted at all. In our second scheme, the transmitter first reconstructs and processes the quantized output signals, and then sends the outcome as a common update information to both receivers. A special case of our second scheme also applies to memoryless BCs without feedback but with strictly causal state-information at the transmitter and causal state-information at the receivers. It recovers all previous achievable regions also for this setup with state-information. [ABSTRACT FROM AUTHOR]

We consider a communication system in which status updates arrive at a source node, and should be transmitted through a network to the intended destination node. The status updates are samples of a random process under observation, transmitted as packets, which also contain the time stamp to identify when the sample was generated. The age of the information available to the destination node is the time elapsed, since the last received update was generated. In this paper, we model the source-destination link using the queuing theory, and we assume that the time it takes to successfully transmit a packet to the destination is an exponentially distributed service time. We analyze the age of information in the case that the source node has the capability to manage the arriving samples, possibly discarding packets in order to avoid wasting network resources with the transmission of stale information. In addition to characterizing the average age, we propose a new metric, called peak age, which provides information about the maximum value of the age, achieved immediately before receiving an update. [ABSTRACT FROM AUTHOR]

Gabidulin codes can be seen as the rank-metric equivalent of Reed–Solomon codes. It was recently proved, using subspace polynomials, that Gabidulin codes cannot be list decoded beyond the so-called Johnson radius. In another result, cyclic subspace codes were constructed by inspecting the connection between subspaces and their subspace polynomials. In this paper, these subspace codes are used to prove two bounds on the list size in decoding certain Gabidulin codes. The first bound is an existential one, showing that exponentially sized lists exist for codes with specific parameters. The second bound presents exponentially sized lists explicitly for a different set of parameters. Both bounds rule out the possibility of efficiently list decoding several families of Gabidulin codes for any radius beyond half the minimum distance. Such a result was known so far only for non-linear rank-metric codes, and not for Gabidulin codes. Using a standard operation called lifting, identical results also follow for an important class of constant dimension subspace codes. [ABSTRACT FROM AUTHOR]

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over $GF(2)$ , whose kernel does not intersect a given set $S$ . In the case where $S$ is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set $S$ , this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where $S$ is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius $nq$ and $np$ respectively, the optimal relative rank is given by the normalized entropy $(1-q)H(p/(1-q))$ , an extension of the Gilbert–Varshamov bound. [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]

Polar coding is a method for communication over noisy classical channels, which is provably capacity achieving and has an efficient encoding and decoding. Recently, this method has been generalized to the realm of quantum information processing, for tasks such as classical communication, private classical communication, and quantum communication. In this paper, we apply the polar coding method to network classical-quantum information theory, by making use of recent advances for related classical tasks. In particular, we consider problems such as the compound multiple access channel and the quantum interference channel. The main result of our work is that it is possible to achieve the best known inner bounds on the achievable rate regions for these tasks, without requiring a so-called quantum simultaneous decoder. Thus, this paper paves the way for developing network classical-quantum information theory further without requiring a quantum simultaneous decoder. [ABSTRACT FROM AUTHOR]

Burst errors are a type of distortion in many data communications and data storage channels. In this paper, we consider the list decodability of codes for single burst error case and phased-burst error case independently. Firstly, we analyze the list decodability of random codes, and we show that the burst list decoding radius and the rate of random codes achieve the Singleton bound and the Gilbert-Varshamov bound for single case and phased case, respectively. Second, we illustrate that cyclic codes and algebraic geometry codes are good burst list-decodable codes for single case and phased case, respectively. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

An upper bound on the error probability of specific lattices, based on their distance spectrum, is constructed. The derivation is accomplished using a simple alternative to the Minkowski–Hlawka mean-value theorem of the geometry of numbers. In many ways, the new bound greatly resembles the Shulman–Feder bound for linear codes. Based on the new bound, error-exponent and channel-dispersion expressions are derived for specific lattice sequences (of increasing dimension) over the AWGN channel. Measuring a sequence’s gap to capacity, using the new asymptotics, is demonstrated. Additional finite dimension results, encountered along the way, are presented. [ABSTRACT FROM PUBLISHER]

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. In addition, it is shown that this property extends to Poltyrev’s random-coding exponent for a random ensemble of lattices. [ABSTRACT FROM PUBLISHER]

A tight converse bound to the channel coding rate in the finite block-length regime and under additive white Gaussian noise conditions was recently proposed by Polyanskiy-Poor–Verdú (PPV). The bound is a generalization of a number of other classical results, and it was also claimed to be equivalent to Shannon’s 1959 cone packing bound. In this paper, we investigate methods for a reliable numerical evaluation of the bound, which is troublesome even for not too large values of the block-length $n$ , by compactly expressing the Polyanskiy, Poor, and Verdú (PPV) converse bound in terms of non-central chi-squared distributions, and by evaluating those through an integral expression and a corresponding series expansion which exploit a method proposed by Temme. As a result, a robust evaluation method and new insights on the bound’s asymptotics, as well as new approximate expressions, are obtained. [ABSTRACT FROM AUTHOR]

In this paper, we study the capacity of the diamond channel. We focus on the special case where the channel between the source node and the two relay nodes are two separate links with finite capacities and the link from the two relay nodes to the destination node is a Gaussian multiple access channel. We call this model the Gaussian multiple access diamond channel. We first propose an upper bound on the capacity. This upper bound is a single-letterization of an $n$ -letter upper bound proposed by Traskov and Kramer, and is tighter than the cut-set bound. As for the lower bound, we propose an achievability scheme based on sending correlated codes through the multiple access channel with superposition structure. We then specialize this achievable rate to the Gaussian multiple access diamond channel. Noting the similarity between the upper and lower bounds, we provide sufficient and necessary conditions that a Gaussian multiple access diamond channel has to satisfy such that the proposed upper and lower bounds meet. Thus, for a Gaussian multiple access diamond channel that satisfies these conditions, we have found its capacity. [ABSTRACT FROM PUBLISHER]

In this paper we study stopping sets of AG codes over a family of curves, denoted by Xƒ,g, that includes several important curves with applications in coding theory. We present results concerning stopping sets of one-point and m-point codes over Xƒ,g , generalizing some results for Hermitian codes presented by Anderson and Matthews. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimal zero-delay jamming over an additive noise channel. Building on a sequence of recent results on conditions for linearity of optimal estimation, and of optimal mappings in source-channel coding, the saddle-point solution to the jamming problem is derived for general sources and channels, without recourse to Gaussianity assumptions. The linearity conditions are shown to play a pivotal role in jamming, in the sense that the optimal jamming strategy is to effectively force both the transmitter and the receiver to default to linear mappings, i.e., the jammer ensures, whenever possible, that the transmitter and the receiver cannot benefit from non-linear strategies. This result is shown to subsume the known result for Gaussian source and channel. The conditions and general settings where such unbeatable strategy can indeed be achieved by the jammer are analyzed. Moreover, a numerical procedure is provided to approximate the optimal jamming strategy in the remaining (source-channel) cases where the jammer cannot impose linearity on the transmitter and the receiver. Next, the analysis is extended to vector sources and channels. This extension involves a new aspect of optimization: the allocation of available transmit and jamming power over source and channel components. Similar to the scalar setting, the saddle-point solution is derived using the linearity conditions in vector spaces. The optimal power allocation strategies for the jammer and the transmitter have an intuitive interpretation as the jammer allocates power according to water-filling over the channel eigenvalues, while the transmitter performs water-pouring (reverse water-filling) over the source eigenvalues. [ABSTRACT FROM PUBLISHER]

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]

In the case of ordinary identification coding, a code is devised to identify a single object among $N$ objects. But, in this paper, we consider a coding problem to identify K$ objects at once among N$ objects in the both cases that K$ objects are ranked or not ranked. By combining Moulin–Koetter scheme with the \varepsilon $ -almost strongly universal class of hash functions used in Kurosawa–Yoshida scheme, an efficient and explicit coding scheme is proposed for K$ -multiple-object identification ( KK$-MOID}} , which is the maximum achievable coding rate in the K -MOID coding, is equal to the ordinary channel capacity, and the proposed scheme can attain C_{\text {K$-MOID}}$ . [ABSTRACT FROM PUBLISHER]

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability \epsilon , for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin’s rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit, which is quite accurate for all but small blocklengths: (1 - \epsilon ) k H(\mathsf S) - {({({k V(\mathsf S)}/{2 \pi })})}^{1/2} \mathop {\rm exp}[- ({( Q^{-1}\left ({\epsilon }\right ))^{2}}/{2})] , where Q^{-1}\left ({\cdot }\right )$ is the functional inverse of the standard Gaussian complementary cumulative distribution function, and $V(\mathsf S)$ is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of $1 - \epsilon $ , but this asymptotic limit is approached from below, i.e., larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties. [ABSTRACT FROM PUBLISHER]

An explicit characterization of the capacity region of the general network coding problem is one of the best known open problems in information theory. A simple set of bounds that is often used in the literature to show that certain rate tuples are infeasible are based on the graph-theoretic notion of cut. The standard cut-set bounds, however, are known to be loose in general when there are multiple messages to be communicated in the network. This paper focuses on broadcast networks, for which the standard cut-set bounds are closely related to union as a specific set operation to combine different simple cuts of the network. A new set of explicit network coding bounds, which combine different simple cuts of the network via a variety of set operations (not just the union), are established via their connections to extremal inequalities for submodular functions. The tightness of these bounds are demonstrated via applications to combination networks. [ABSTRACT FROM AUTHOR]

An online fountain code is defined as a fountain code for which an optimal encoding strategy can be found efficiently given any instantaneous decoding state. This property is important for data distribution in practical networks. In this paper, we formalize the problem of online fountain code construction, and propose new online fountain codes that outperform known ones in having factor 3–5 lower redundancy overhead. The bounding of the code overhead is carried out using the analysis of the dynamics of random-graph processes. [ABSTRACT FROM AUTHOR]

This paper considers space-time coding over several independently Rayleigh faded blocks. In particular, we will concentrate on giving upper bounds for the coding gain of lattice space-time codes as the number of blocks grow. This problem was previously considered in the single antenna case by Bayer-Fluckiger et al. in 2006. Crucial to their work was Odlyzko’s bound on the discriminant of an algebraic number field, as this provides an upper bound for the normalized coding gain of number field codes. In the MIMO context natural codes are constructed from division algebras defined over number fields and the coding gain is measured by the discriminant of the corresponding (noncommutative) algebra. In this paper, we will develop analogues of the Odlyzko bounds in this context and show how these bounds limit the normalized coding gain of a very general family of division algebra based space-time codes. These bounds can also be used as benchmarks in practical code design and as tools to analyze asymptotic bounds of performance as the number of independently faded blocks increases. [ABSTRACT FROM AUTHOR]

Hybrid analog–digital coding has been used for several communication scenarios, such as joint source–channel coding of Gaussian sources over Gaussian channels and relay communication over Gaussian networks. In this paper, a generalized hybrid coding technique is proposed for communication over discrete memoryless and Gaussian systems, and its utility is demonstrated via three examples—lossy joint source–channel coding over multiple access channels, channel coding over two-way relay channels, and channel coding over diamond networks. The corresponding coding schemes recover and extend several existing results in the literature. [ABSTRACT FROM AUTHOR]

This paper describes lossless compression algorithms for multisets of sequences, taking advantage of the multiset’s unordered structure. Multisets are a generalization of sets, where members are allowed to occur multiple times. A multiset can be encoded naïvely by simply storing its elements in some sequential order, but then information is wasted on the ordering. We propose a technique that transforms the multiset into an order-invariant tree representation, and derive an arithmetic code that optimally compresses the tree. Our method achieves compression even if the sequences in the multiset are individually incompressible (such as cryptographic hash sums). The algorithm is demonstrated practically by compressing collections of SHA-1 hash sums, and multisets of arbitrary, individually encodable objects. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel reservation system to study partition information and its transmission over a noise-free Boolean multiaccess channel. The objective of transmission is not to restore the message, but to partition active users into distinct groups so that they can, subsequently, transmit their messages without collision. We first calculate (by mutual information) the amount of information needed for the partitioning without channel effects, and then propose two different coding schemes to obtain achievable transmission rates over the channel. The first one is the brute force method, where the codebook design is based on centralized source coding; the second method uses random coding, where the codebook is generated randomly and optimal Bayesian decoding is employed to reconstruct the partition. Both methods shed light on the internal structure of the partition problem. A novel formulation is proposed for the random coding scheme, in which a sequence of channel operations and interactions induces a hypergraph. The formulation intuitively describes the transmitted information in terms of a strong coloring of this hypergraph. An extended Fibonacci structure is constructed for the simple, but nontrivial, case with two active users. A comparison between these methods and group testing is conducted to demonstrate the potential of our approaches. [ABSTRACT FROM AUTHOR]

We consider a cooperative two-user multiaccess channel in which the transmission is controlled by a random state. Both encoders transmit a common message and, one of the encoders also transmits an individual message. We study the capacity region of this communication model for different degrees of availability of the states at the encoders, causally or strictly causally. In the case in which the states are revealed causally to both encoders but not to the decoder we find an explicit characterization of the capacity region in the discrete memoryless case. In the case in which the states are revealed only strictly causally to both encoders, we establish inner and outer bounds on the capacity region. The outer bound is nontrivial, and has a relatively simple form. It has the advantage of incorporating only one auxiliary random variable. In particular, it suggests that there is none, or at best only little, to gain from having the encoder that transmits both messages also sending an individual description of the state to the receiver, in addition to the compressed version that is sent cooperatively with the other encoder. We then introduce a class of cooperative multiaccess channels with states known strictly causally at both encoders for which the inner and outer bounds agree, and so we characterize the capacity region for this class. In this class of channels, the state can be obtained as a deterministic function of the channel inputs and output. We also study the model in which the states are revealed, strictly causally, in an asymmetric manner, to only one encoder. Throughout this paper, we discuss a number of examples, and compute the capacity region of some of these examples. The results shed more light on the utility of delayed channel state information for increasing the capacity region of state-dependent cooperative multiaccess channels, and tie with recent progress in this framework. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the minimum energy of transmitting correlated sources over the Gaussian multiple-access channel. Compared to other works on joint source-channel coding, we consider the fundamental problem of the minimum transmission energy, where the source and channel bandwidths are not naturally matched. Different models of correlated sources are studied. We first treat lossy transmission of Gaussian sources, including multiterminal sources and CEO sources. We then consider lossless transmission of correlated binary sources. In all cases, we lower bound the minimum energy using a cut-set argument that couples transmission energy and the distortions for the Gaussian cases (or source entropy for the discrete case). For the achievable schemes, separate source and channel coding and uncoded transmission are studied as benchmarks. In addition, we show that hybrid digital/analog transmission achieves the best known energy efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we consider the finite-state multiple access channel (MAC) with partially cooperative encoders and delayed channel state information (CSI). Here, partial cooperation refers to the communication between the encoders via finite-capacity links. The channel states are assumed to be governed by a Markov process. Full CSI is assumed at the receiver, while at the transmitters, only delayed CSI is available. The capacity region of this channel model is derived by first solving the case of the finite-state MAC with a common message. Achievability for the latter case is established using the notion of strategies, however, we show that optimal codes can be constructed directly over the input alphabet. This results in a single codebook construction that is then leveraged to apply simultaneous joint decoding. Simultaneous decoding is crucial here because it circumvents the need to rely on the capacity region’s corner points, a task that becomes increasingly cumbersome with the growth in the number of messages to be sent. The common message result is then used to derive the capacity region for the case with partially cooperating encoders. Next, we apply this general result to the special case of the Gaussian vector MAC with diagonal channel transfer matrices, which is suitable for modeling, e.g., orthogonal frequency division multiplexing-based communication systems. The capacity region of the Gaussian channel is presented in terms of a convex optimization problem that can be solved efficiently using numerical tools. The region is derived by first presenting an outer bound on the general capacity region and then suggesting a specific input distribution that achieves this bound. Finally, numerical results are provided that give valuable insight into the practical implications of optimally using conferencing to maximize the transmission rates. [ABSTRACT FROM AUTHOR]

Though network coding is traditionally performed over finite fields, recent work on nested-lattice-based network coding suggests that, by allowing network coding over certain finite rings, more efficient physical-layer network coding schemes can be constructed. This paper considers the problem of communication over a finite-ring matrix channel \(Y = AX + BE\) , where \(X\) is the channel input, \(Y\) is the channel output, \(E\) is random error, and \(A\) and \(B\) are random transfer matrices. Tight capacity results are obtained and simple polynomial-complexity capacity-achieving coding schemes are provided under the assumption that \(A\) is uniform over all full-rank matrices and \(BE\) is uniform over all rank- \(t\) matrices, extending the work of Silva, Kschischang, and Kötter (2010), who handled the case of finite fields. This extension is based on several new results, which may be of independent interest, that generalize concepts and methods from matrices over finite fields to matrices over finite chain rings. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the structure of infeasibility results in network information theory, based on a notion of information state. We also discuss ideas for generalizing a known outer bound for lossless transmission of independent sources over a network to one of lossy transmission of dependent sources over the same network. To concretely demonstrate this, we apply our ideas and prove new results for lossy transmission of dependent sources by generalizing: 1) the cut-set bound; 2) the best known outer bound on the capacity region of a general broadcast channel; and 3) the outer bound part of the result of Maric, Yates, and Kramer on strong interference channels with a common message. [ABSTRACT FROM AUTHOR]

This paper develops a fundamental theory of realizations of linear and group codes on general graphs using elementary group theory, including basic group duality theory. Principal new and extended results include: normal realization duality; analysis of systems-theoretic properties of fragments of realizations and their connections; minimal \(\Leftrightarrow \) trim and proper theorem for cycle-free codes; results showing that all constraint codes except interface nodes may be assumed to be trim and proper, and that the interesting part of a cyclic realization is its 2-core; notions of observability and controllability for fragments, and related tests; and relations between state-trimness and controllability, and dual state-trimness and observability. [ABSTRACT FROM AUTHOR]

We propose a new coding scheme using only one lattice that achieves the \({1}/{2}~{\rm log(1+ \mathop {\mathrm {\mathsf {SNR}\kern 0pt}}\nolimits )}\) capacity of the additive white Gaussian noise (AWGN) channel with lattice decoding, which is provable for signal-to-noise ratio \( \mathop {\mathrm {\mathsf {SNR}\kern 0pt}}\nolimits >e\) at present. The scheme applies a discrete Gaussian distribution over an AWGN-good lattice, but otherwise does not require a shaping lattice or dither. Thus, it significantly simplifies the default lattice coding scheme of Erez and Zamir which involves a quantization-good lattice as well as an AWGN-good lattice. Using the flatness factor, we show that the error probability of the proposed scheme under minimum mean-square error lattice decoding is almost the same as that of Erez and Zamir, for any rate up to the AWGN channel capacity. We introduce the notion of good constellations, which carry almost the same mutual information as that of continuous Gaussian inputs. We also address the implementation of Gaussian shaping for the proposed lattice Gaussian coding scheme. [ABSTRACT FROM AUTHOR]

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate $R$ and minimum distance $\delta $ of a binary code. The best known tradeoff is the Gilbert–Varshamov bound, and says that for every $\delta \in (0, 1/2)$ , there are codes with minimum distance $\delta $ and rate $R = {R_{\mathsf {GV}}}(\delta) > 0$ (for a certain simple function ${R_{\mathsf {GV}}}(\cdot)$ ). In this paper, we show that the Gilbert–Varshamov bound can be achieved by codes, which support local error-detection and error-correction algorithms. Specifically, we show the following results. 1) Local testing: for all $\delta \in (0,1/2)$ and all $R < {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally testable with $\mathsf {quasipolylog}(n)$ query complexity. 2) Local correction: for all $\epsilon > 0$ , for all $\delta < 1/2$ sufficiently large, and all $R < (1-\epsilon) {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally correctable from $({\delta }/{2}) - o(1)$ fraction errors with $O(n^{\epsilon })$ query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen’s random concatenation technique and the best known locally testable codes by Kopparty et al. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami–Sudan–Indyk list decoding strategy for concatenated codes, Alon–Edmonds–Luby distance amplification, and the local list-decodability, local list-recoverability, and local testability of Reed–Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code. [ABSTRACT FROM AUTHOR]

This paper contains two main contributions concerning the asymmetric broadcast channel. The first is an analysis of the exact random coding error exponents for both users, and the second is the derivation of universal decoders for both users. These universal decoders are certain variants of the maximum mutual information universal decoder, and they achieve the corresponding random coding exponents of optimal decoding. In addition, we introduce some lower bounds, which involve optimizations over very few parameters, unlike the original, exact exponents, which involve minimizations over auxiliary probability distributions. Numerical results for the binary symmetric broadcast channel show improvements over previously derived error exponents for the same model. [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]

Compared with classical block codes, list decoding rank-metric codes efficiently seems more difficult. The evidences to support this view include: 1) so far the only known efficient list decoding of rank-metric codes \mathcal C gives decoding radius beyond (1-R)/2 with positive rate R when the ratio of the number of rows over the number of columns is extremely small, 2) the Johnson bound for rank-metric codes does not exist as opposed to classical codes, and 3) the Gabidulin codes of square matrices cannot be list decoded beyond half of the minimum distance. Although the list decodability of random rank-metric codes and the limits to the list decodability have been determined completely, little work on efficient list decoding of rank-metric codes has been done. The only known efficient list decoding of rank-metric codes 1-R- \varepsilon with positive rate R is extremely small, i.e., O(\varepsilon ^{2}) , where \rho (\mathcal {C}) denotes the ratio of the number of rows over the number of columns of \rho (\mathcal C) close to 1. The main purpose of this paper is to explicitly construct a class of rank-metric codes \mathcal C with the ratio \rho (\mathcal C) up to 1/2 and efficiently list decode these codes beyond unique decoding radius (1-R)/2 . Furthermore, encoding and list decoding algorithms run in polynomial time {\mathrm{ poly}}(n,\exp (1/{ \varepsilon })) . The list size can be reduced to O(1/{ \varepsilon })$ by randomizing the algorithm. Our key idea is to employ bivariate polynomials $f(x,y)$ , where $f$ is linearized in variable $y$ and the variable $x$ is used to “fold” the code. In other words, the rows are used to correct rank errors and the columns are used to “fold” the code to enlarge the decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace whose dimension is linear in the number $n$ of columns. This “periodic” structure allows us to pre-encode the messages to prune down the list. More precisely, we use subspace design introduced by Guruswami and Xing to obtain a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced by Guruswami et al. to obtain a randomized algorithm with a smaller constant list size. [ABSTRACT FROM PUBLISHER]

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]