3,076 results
Search Results
152. The Capacity Region of a Class of Semideterministic Interference Channels.
- Author
-
Hon-Fah Chong and Motani, Mehul
- Subjects
ELECTRIC interference ,ELECTRIC capacity ,COMPUTATIONAL mathematics ,GAUSSIAN processes ,CODING theory ,DECODERS (Electronics) - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
153. A Generic Construction of Cartesian Authentication Codes.
- Author
-
Cunsheng Ding, Helleseth, Tor, Kløve, Torleiv, and Xuesong Wang
- Subjects
INFORMATION theory ,COMBINATORIAL designs & configurations ,ARTIFICIAL intelligence ,CODING theory ,DIGITAL electronics ,TELECOMMUNICATION - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
154. Capacity of Wireless Erasure Networks.
- Author
-
Dana, Amir F., Gowaikar, Radhika, Palanki, Ravi, Hassibi, Babak, and Effros, Michelle
- Subjects
WIRELESS communications ,COMPUTER networks ,DATA transmission systems ,INFORMATION services ,INFORMATION science ,CODING theory ,DIGITAL communications ,ELECTRONIC data processing ,ELECTRONIC systems - Abstract
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]
- Published
- 2006
- Full Text
- View/download PDF
155. On the Capacity of Large Gaussian Relay Networks.
- Author
-
Gastpar, Michael and Vetterli, Martin
- Subjects
RADIO relay systems ,DATA transmission systems ,SENSOR networks ,CODING theory ,DATA compression ,TELECOMMUNICATION - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
156. Linear Network Coding, Linear Index Coding and Representable Discrete Polymatroids.
- Author
-
Muralidharan, Vijayvaradharaj Tirucherai and Rajan, B. Sundar
- Subjects
MATROIDS ,LINEAR network coding ,CODING theory ,COMMUNICATION ,FRACTIONAL programming - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
157. Subblock-Constrained Codes for Real-Time Simultaneous Energy and Information Transfer.
- Author
-
Tandon, Anshoo, Motani, Mehul, and Varshney, Lav R.
- Subjects
ENERGY harvesting ,DECODING algorithms ,MEMORYLESS systems ,KNOWLEDGE transfer ,CODING theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
158. The ADMM Penalized Decoder for LDPC Codes.
- Author
-
Liu, Xishuo and Draper, Stark C.
- Subjects
LINEAR programming ,CODING theory ,LOW density parity check codes ,SIMULATION methods & models ,SIGNAL-to-noise ratio - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
159. Bounds on the Parameters of Locally Recoverable Codes.
- Author
-
Tamo, Itzhak, Barg, Alexander, and Frolov, Alexey
- Subjects
MATHEMATICAL bounds ,CODING theory ,MATHEMATICAL functions ,SET theory ,DERIVATIVES (Mathematics) - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
160. On the Subtleties of $q$ -PAM Linear Physical-Layer Network Coding.
- Author
-
Shi, Long, Liew, Soung Chang, and Lu
- Subjects
MULTIPLEXING ,CODING theory ,BROADCAST data systems ,LINEAR network coding ,BROADCAST channels ,SIGNAL theory ,INFORMATION theory ,TELECOMMUNICATION channels - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
161. Signaling Over Two-User Parallel Gaussian Interference Channels: Outage Analysis.
- Author
-
Ebrahimzadeh, Ehsan, Moshksar, Kamyar, and Khandani, Amir K.
- Subjects
MULTIPLEXING ,CODING theory ,BROADCAST data systems ,LINEAR network coding ,BROADCAST channels ,SIGNAL theory ,INFORMATION theory ,TELECOMMUNICATION channels - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
162. An LP Characterization of the Secret-message Capacity of Three Erasure Networks With Feedback.
- Author
-
Czap, Laszlo, Prabhakaran, Vinod M., Fragouli, Christina, and Diggavi, Suhas N.
- Subjects
MULTIPLEXING ,CODING theory ,BROADCAST data systems ,LINEAR network coding ,BROADCAST channels ,SIGNAL theory ,INFORMATION theory ,TELECOMMUNICATION channels - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
163. The Two-Modular Fourier Transform of Binary Functions.
- Author
-
Hong, Yi, Viterbo, Emanuele, and Belfiore, Jean-Claude
- Subjects
CODING theory ,BROADCAST data systems ,MULTIPLEXING ,LINEAR network coding ,BROADCAST channels ,SIGNAL theory ,INFORMATION theory ,TELECOMMUNICATION channels - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
164. Near-Optimal Modulo-and-Forward Scheme for the Untrusted Relay Channel.
- Author
-
Zhang, Shengli, Fan, Lisheng, Peng, Mugen, and Poor, H. Vincent
- Subjects
MULTIPLEXING ,ELECTRIC currents ,CODING theory ,SIGNAL theory ,ELECTROMAGNETIC noise ,INFORMATION theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
165. Coding Schemes With Rate-Limited Feedback That Improve Over the No Feedback Capacity for a Large Class of Broadcast Channels.
- Author
-
Wu, Youlong and Wigger, Michele
- Subjects
BROADCAST channels ,PROBABILITY theory ,CODING theory ,TRANSMITTERS (Communication) ,SIGNAL quantization - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
166. On the Age of Information in Status Update Systems With Packet Management.
- Author
-
Costa, Maice, Codreanu, Marian, and Ephremides, Anthony
- Subjects
TELECOMMUNICATION systems ,PROTOCOL analyzers ,PACKET switching (Data transmission) ,CODING theory ,QUEUING theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
167. Some Gabidulin Codes Cannot Be List Decoded Efficiently at any Radius.
- Author
-
Raviv, Netanel and Wachter-Zeh, Antonia
- Subjects
CODING theory ,DECODING algorithms ,SUBSPACES (Mathematics) ,POLYNOMIALS ,METRIC geometry - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
168. Linear Boolean Classification, Coding and the Critical Problem.
- Author
-
Abbe, Emmanuel, Alon, Noga, Bandeira, Afonso S., and Sandon, Colin
- Subjects
BOOLEAN functions ,VECTORS (Calculus) ,MATRICES (Mathematics) ,CODING theory ,PROBABILITY theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
169. On the SNR-Evolution of the MMSE Function of Codes for the Gaussian Broadcast and Wiretap Channels.
- Author
-
Bustin, Ronit, Schaefer, Rafael F., Poor, H. Vincent, and Shamai Shitz, Shlomo
- Subjects
SIGNAL-to-noise ratio ,MEAN square algorithms ,GAUSSIAN channels ,EQUIVOCATION ,CODING theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
170. Involutions Over the Galois Field \mathbb F2^{n}.
- Author
-
Charpin, Pascale, Mesnager, Sihem, and Sarkar, Sumanta
- Subjects
PERMUTATION groups ,FINITE fields ,CRYPTOGRAPHY ,CODING theory ,BOOLEAN functions - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
171. Polar Codes in Network Quantum Information Theory.
- Author
-
Hirche, Christoph, Morgan, Ciara, and Wilde, Mark M.
- Subjects
CODING theory ,QUANTUM theory ,INFORMATION theory ,POLAR coordinates (Mathematics) ,DATA compression - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
172. On the List Decodability of Burst Errors.
- Author
-
Ding, Yang
- Subjects
CODING theory ,SINGLETON bounds ,DECODING algorithms ,ERROR analysis in mathematics ,BURST errors (Telecommunications) ,SIGNAL theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
173. Apparent Distance and a Notion of BCH Multivariate Codes.
- Author
-
Bernal, Jose Joaquin, Bueno-Carreno, Diana H., and Simon, Juan Jacobo
- Subjects
BCH codes ,CYCLIC codes ,CODING theory ,INFORMATION theory ,ERROR-correcting codes - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
174. Non-Random Coding Error Bounds for Lattices.
- Author
-
Domb, Yuval and Feder, Meir
- Subjects
CODING theory ,MATHEMATICAL bounds ,LATTICE theory ,ERROR analysis in mathematics ,MATHEMATICAL sequences - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
175. The Random Coding Bound Is Tight for the Average Linear Code or Lattice.
- Author
-
Domb, Yuval, Zamir, Ram, and Feder, Meir
- Subjects
CODING theory ,MATHEMATICAL bounds ,LINEAR codes ,RANDOM variables ,MATHEMATICAL proofs ,LATTICE theory - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
176. On the Evaluation of the Polyanskiy-Poor–Verdú Converse Bound for Finite Block-Length Coding in AWGN.
- Author
-
Erseghe, Tomaso
- Subjects
CODING theory ,MATHEMATICAL bounds ,RANDOM noise theory ,GENERALIZATION ,NUMERICAL analysis - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
177. The Gaussian Multiple Access Diamond Channel.
- Author
-
Kang, Wei, Liu, Nan, and Chong, Weiwei
- Subjects
GAUSSIAN channels ,CODING theory ,MATHEMATICAL bounds ,MARKOV processes ,DIFFERENTIAL entropy ,LOGARITHMIC functions - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
178. On Stopping Sets of AG Codes Over Certain Curves With Separated Variables.
- Author
-
Tenorio, Wanderson and Tizziotti, Guilherme Chaud
- Subjects
CODING theory ,LINEAR codes ,REED-Muller codes ,INFORMATION theory ,ITERATIVE decoding - Abstract
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]- Published
- 2021
- Full Text
- View/download PDF
179. Optimal Zero-Delay Jamming Over an Additive Noise Channel.
- Author
-
Akyol, Emrah, Rose, Kenneth, and Basar, Tamer
- Subjects
RADIO interference ,CODING theory ,TELECOMMUNICATION channels ,DATA compression ,RADIO transmitters & transmission - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
180. Rank-Modulation Rewrite Coding for Flash Memories.
- Author
-
En Gad, Eyal, Yaakobi, Eitan, Jiang, Anxiao Andrew, and Bruck, Jehoshua
- Subjects
PERMUTATIONS ,FLASH memory ,RANDOM access memory ,SEMICONDUCTOR storage devices ,CODING theory - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
181. Multiple Object Identification Coding.
- Author
-
Yamamoto, Hirosuke and Ueda, Masashi
- Subjects
CODING theory ,CHANNEL coding ,DATA compression ,FEEDBACK control systems ,SIGNAL theory - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
182. Variable-Length Compression Allowing Errors.
- Author
-
Kostina, Victoria, Polyanskiy, Yury, and Verdu, Sergio
- Subjects
LOSSLESS data compression ,RATE distortion theory ,CODING theory ,DATA compression ,SOURCE code - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
183. Generalized Cut-Set Bounds for Broadcast Networks.
- Author
-
Salimi, Amir, Liu, Tie, and Cui, Shuguang
- Subjects
LINEAR network coding ,SYSTEMS theory ,SUBMODULAR functions ,CODING theory ,DIFFERENTIAL entropy - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
184. Online Fountain Codes With Low Overhead.
- Author
-
Cassuto, Yuval and Shokrollahi, Amin
- Subjects
CODING theory ,DATA distribution ,RANDOM graphs ,UNIFORM distribution (Probability theory) ,DECODING algorithms - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
185. A Noncommutative Analogue of the Odlyzko Bounds and Bounds on Performance for Space-Time Lattice Codes.
- Author
-
Linowitz, Benjamin, Satriano, Matthew, and Vehkalahti, Roope
- Subjects
NONCOMMUTATIVE algebras ,RAYLEIGH number ,ALGEBRAIC number theory ,MIMO systems ,CODING theory ,SPACE-time codes - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
186. A Unified Approach to Hybrid Coding.
- Author
-
Minero, Paolo, Lim, Sung Hoon, and Kim, Young-Han
- Subjects
CODING theory ,GAUSSIAN channels ,DISCRETE memoryless channels ,CHANNEL coding ,INFORMATION theory - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
187. Compressing Sets and Multisets of Sequences.
- Author
-
Steinruecken, Christian
- Subjects
SET theory ,CODING theory ,DATA structures ,DECODERS & decoding ,DATA compression - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
188. Partition Information and its Transmission Over Boolean Multi-Access Channels.
- Author
-
Wu, Shuhang, Wei, Shuangqing, Wang, Yue, Vaidyanathan, Ramachandran, and Yuan, Jian
- Subjects
BOOLEAN algebra ,MASSAGE ,MULTIPLE access protocols (Computer network protocols) ,CODING theory ,DATA extraction - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
189. On Cooperative Multiple Access Channels With Delayed CSI at Transmitters.
- Author
-
Zaidi, Abdellatif and Shamai Shitz, Shlomo
- Subjects
TRANSMITTERS (Communication) ,INFORMATION theory ,CODING theory ,DISCRETE memoryless channels ,FEEDBACK control systems - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
190. On the Minimum Energy of Sending Correlated Sources Over the Gaussian MAC.
- Author
-
Jiang, Nan, Yang, Host-Madsen, Anders, and Xiong, Zixiang
- Subjects
GAUSSIAN channels ,CHANNEL coding ,CODING theory ,ENTROPY (Information theory) ,DATA transmission systems ,ENERGY consumption - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
191. The Finite State MAC With Cooperative Encoders and Delayed CSI.
- Author
-
Goldfeld, Ziv, Permuter, Haim H., and Zaidel, Benjamin M.
- Subjects
FINITE state machines ,CODING theory ,INFORMATION theory ,MARKOV processes ,DATA transmission systems - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
192. Communication Over Finite-Chain-Ring Matrix Channels.
- Author
-
Feng, Chen, Nobrega, Roberto W., Kschischang, Frank R., and Silva, Danilo
- Subjects
CODING theory ,FINITE rings ,POLYNOMIALS ,COMPUTATIONAL complexity ,FINITE fields - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
193. Infeasibility Proof and Information State in Network Information Theory.
- Author
-
Gohari, Amin and Anantharam, Venkat
- Subjects
INFORMATION theory ,DATA transmission systems ,MESSAGE passing (Computer science) ,INTERFERENCE channels (Telecommunications) ,CODING theory - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
194. Codes on Graphs: Fundamentals.
- Author
-
Forney, G. David
- Subjects
CODING theory ,LINEAR codes ,GROUP theory ,DUALITY theory (Mathematics) ,CONTROLLABILITY in systems engineering - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
195. Achieving AWGN Channel Capacity With Lattice Gaussian Coding.
- Author
-
Ling, Cong and Belfiore, Jean-Claude
- Subjects
ADDITIVE white Gaussian noise channels ,CODING theory ,SIGNAL-to-noise ratio ,GAUSSIAN distribution ,INFORMATION theory - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
196. Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound.
- Author
-
Gopi, Sivakanth, Kopparty, Swastik, Oliveira, Rafael, Ron-Zewi, Noga, and Saraf, Shubhangi
- Subjects
CODING theory ,INFORMATION theory ,MATHEMATICAL bounds ,ERROR correction (Information theory) ,ERROR detection (Information theory) ,BINARY codes - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
197. Exact Random Coding Exponents and Universal Decoders for the Asymmetric Broadcast Channel.
- Author
-
Averbuch, Ran and Merhav, Neri
- Subjects
ERROR functions ,BROADCAST channels ,DECODING algorithms ,CODING theory ,COMPUTER simulation - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
198. An Improvement of the Asymptotic Elias Bound for Non-Binary Codes.
- Author
-
Kaipa, Krishna
- Subjects
INFORMATION theory ,ASYMPTOTIC expansions ,ELIAS (Information retrieval system) ,CODING theory ,MATHEMATICAL bounds - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
199. A New Class of Rank-Metric Codes and Their List Decoding Beyond the Unique Decoding Radius.
- Author
-
Xing, Chaoping and Yuan, Chen
- Subjects
DECODING algorithms ,CODING theory ,ERROR-correcting codes ,MONTE Carlo method ,POLYNOMIALS - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
200. Mismatched Multi-Letter Successive Decoding for the Multiple-Access Channel.
- Author
-
Scarlett, Jonathan, Martinez, Alfonso, and Guillen i Fabregas, Albert
- Subjects
MAXIMUM likelihood decoding ,CODING theory ,EMAIL systems ,NUMERICAL analysis ,ERROR analysis in mathematics ,CHANNEL capacity (Telecommunications) - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.