Search

Recently, there has been a lot of success in using the deterministic approach to provide approximate characterization of Gaussian network capacity. In this paper, we take a deterministic view and revisit the problem of wiretap channel with side information. A precise characterization of the secrecy capacity is obtained for a linear deterministic model, which naturally suggests a coding scheme which we show to achieve the secrecy capacity of the degraded Gaussian model (dubbed as “secret writing on dirty paper”) to within half a bit. [ABSTRACT FROM PUBLISHER]

This paper examines near-capacity dirty-paper code designs based on source-channel coding. We first point out that the performance loss in signal-to-noise ratio (SNR) in our code designs can be broken into the sum of the packing loss from channel coding and a modulo loss, which is a function of the granular loss from source coding and the target dirty-paper coding rate (or SNR). We then examine practical designs by combining trellis-coded quantization (TCQ) with both systematic and nonsystematic irregular repeat-accumulate (IRA) codes. Like previous approaches, we exploit the extrinsic information transfer (EXIT) chart technique for capacity-approaching IRA code design; but unlike previous approaches, we emphasize the role of strong source coding to achieve as much granular gain as possible using TCQ. Instead of systematic doping, we employ two relatively shifted TCQ codebooks, where the shift is optimized (via tuning the EXIT charts) to facilitate the IRA code design. Our designs synergistically combine TCQ with IRA codes so that they work together as well as they do individually. By bringing together TCQ (the best quantizer from the source coding community) and EXIT chart-based IRA code designs (the best from the channel coding community), we are able to approach the theoretical limit of dirty-paper coding. For example, at 0.25 bit per symbol (b/s), our best code design (with 2048-state TCQ) performs only 0.630 dB away from the Shannon capacity. [ABSTRACT FROM AUTHOR]

The "writing on dirty paper"-channel model offers an information-theoretic framework for precoding techniques for canceling arbitrary interference known at the transmitter. It indicates that lossless precoding is theoretically possible at any signal-to-noise ratio (SNR), and thus dirty-paper coding may serve as a basic building block in both single-user and multiuser communication systems. We design an end-to-end coding realization of a system materializing a significant portion of the promised gains. We employ multidimensional quantization based on trellis shaping at the transmitter. Coset decoding is implemented at the receiver using "virtual bits." Combined with iterative decoding of capacity-approaching codes we achieve an improvement of 2 dB over the best scalar quantization scheme. Code design is done using the EXIT chart technique. [ABSTRACT FROM AUTHOR]

Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper, we elaborate on the implication of these parameters and devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes, our bound is often tight. Furthermore, for these codes, the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights. [ABSTRACT FROM AUTHOR]

We derive the capacity region of the two-user dirty-paper Gaussian multiaccess channel (MAC) with conferencing encoders. In this MAC, prior to each transmission block, the transmitters can hold a conference in which they can communicate with each other over error-free bit pipes of given capacities. The received signal suffers not only from additive Gaussian noise but also from additive interference, which is known noncausally to the transmitters but not to the receiver. The additive interference is modeled as Gaussian or uniform over a sphere. We show that the interference can be perfectly mitigated, i.e., that the capacity region without interference can also be achieved in its presence. This holds irrespective of whether the transmitters learn the interference before or after the conference. It follows as a corollary that also for the MAC with degraded message sets, the interference can be perfectly mitigated if it is known noncausally to the transmitters. To derive our results, we generalize Costa's single-user writing-on-dirty-paper achievability result to channels with dependent interference and not-necessarily Gaussian noise. [ABSTRACT FROM AUTHOR]

In this paper, we extend the localized error correction code introduced by L. A. Bassalygo and coworkers from Hamming space to projective space. For constant dimensional localized error correction codes in projective space, we have a lower bound and an upper bound of the capacity, which are asymptotically tight when z< x\leq n-z\over 2, where x, z, and n are dimensions of codewords, error configurations, and the ground space, respectively. We determine the capacity of nonconstant dimensional localized error correction codes when z < n\over 3. [ABSTRACT FROM PUBLISHER]

Explores several studies on convolutional codes which claim different codes to be optimum under the optimum distance spectrum criterion. Definitions and search criterion; Inconsistencies in the studies by Bocharova and Kudryashov and Chang, Hwang and Lin.

We consider a variable-length source coding problem subject to local decodability constraints. In particular, we investigate the blocklength scaling behavior attainable by encodings of $r$ -sparse binary sequences, under the constraint that any source bit can be correctly decoded upon probing at most $d$ codeword bits. We consider both adaptive and non-adaptive access models, and derive upper and lower bounds that often coincide up to constant factors. Such a characterization for the fixed-blocklength analog of our problem, known as the bit probe complexity of static membership, remains unknown despite considerable attention from researchers over the last few decades. We also show that locally decodable schemes for sparse sequences are able to decode 0s (frequent source symbols) of the source with far fewer probes on average than they can decode 1s (infrequent source symbols), thus rigorizing the notion that infrequent symbols require high probe complexity, even on average. Connections to the fixed-blocklength model and to communication complexity are also briefly discussed. [ABSTRACT FROM AUTHOR]

The article presents information on the 2005 Information Theory Society Paper Award, which is given annually to for a valuable publication in the field of information theory. This year the award was jointly awarded to researchers Shuo-Yen Robert Li, Raymond W. Yeung, and Ning Cai for their paper "Linear Network Coding" which appeared in the February 2003 issue of the journal "IEEE Transactions on Information Theory." Shuo-Yen Robert Li has done his B.S. in mathematics from National Taiwan University in 1970 and Ph.D. in mathematics from the University of California, Berkeley, in 1974. Yeung was born in Hong Kong on June 3, 1962. He has done B.S., M.Eng., Ph.D. in electrical engineering from Cornell University in Ithaca, New York. His research work include information theory and network coding. Ning Cai has done his B.S. in mathematics from the Normal College of Beijing in Beijing, China in 1982. He completed his Ph.D. in mathematics from the University of Bielefeld in Bielefeld, Germany in 1988. He has done research in the field of combinatorics, information theory and their applications.

The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain properties. In this paper, a natural class of binary tree sources is presented such that the demanded properties are fulfilled. Moreover, for both subclasses considered in the paper of Zhang, Yang, and Kieffer, their result is improved by deriving bounds on the maximal pointwise redundancy (or worst-case redundancy) instead of the average-case redundancy. Finally, using context-free tree grammars instead of DAGs, upper bounds on the maximal pointwise redundancy for certain binary tree sources are derived. This yields universal codes for new classes of binary tree sources. [ABSTRACT FROM AUTHOR]

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprised of a set of $K \in \mathbb {N}$ isolated source nodes and $N \in \mathbb {N}$ encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of the adversarial nodes, denoted by $\beta \in \mathbb {N}$ , and the cardinality of the set of symbols that each one generates, denoted by $v \in \mathbb {N}$ , the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in \mathbb {N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is $t^{*} \in \mathbb {N}$ , the minimum of such $t$ , which is a function of $K$ , $N$ , $\beta $ , and $v$. In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that $t^{*}_{\textrm {Linear}}=K+2\beta (v-1)$ , if $N\ge K+2\beta (v-1)$ , and $t^{*}_{\textrm {Linear}}=N$ , if $N\le K+2\beta (v-1)$. In order to achieve $t^{*}_{\textrm {Linear}}$ , we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. In order to prove the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to construct pliable fractional repetition (FR) codes that are locally recoverable for distributed storage systems (DSSs). FR codes are integral in constructing a class of distributed storage codes with exact repair by transfer. Pliable FR codes are a new type of FR codes in which both the per-node storage and repetition degree can easily be adjusted simultaneously; thus, pliable FR codes are vital for DSSs in which parameters can dynamically change over time. However, the constructions of pliable FR codes with repair locality remain unknown. In addition, the tradeoffs between the code minimum distance of an FR code and its repair locality are not fully understood. To address these problems, this paper first presents general results regarding FR codes. Subsequently, this paper presents an improved Singleton-like bound for locally recoverable FR codes under an additional requirement that each node must be part of a local structure that, upon failure, allows it to be exactly recovered by a simple download process. Moreover, this paper proposes a construction of locally recoverable FR codes that can achieve the proposed Singleton-like bound; this construction is based on bipartite graphs with a given girth. In particular, this paper also proposes a general bipartite-graph-based approach to constructing optimal pliable FR codes with and without repair localities; in this approach, a new family of bipartite graphs, called matching-feasible graphs, is introduced. Finally, this paper proposes the explicit constructions of optimal pliable FR codes by using a family of matching-feasible graphs with arbitrary large girth. Notably, in addition to attaining a Singleton-like bound for FR codes, the explicit pliable FR codes are optimal locally recoverable FR codes from two perspectives of repair locality. The explicit pliable FR codes can also be used as FR batch codes to provide load balancing in DSSs. [ABSTRACT FROM AUTHOR]

The state-dependent Gaussian interference channel (IC) and Z-IC are investigated, in which two receivers are corrupted by the same but differently scaled states. The state sequence is noncausally known at both transmitters, but not known at either receiver. Three interference regimes are studied, i.e., the very strong, strong, and weak regimes. In the very strong regime, the capacity region is characterized under certain channel parameters by designing a cooperative dirty paper coding between the two transmitters to fully cancel the state. In the strong regime, points on the capacity region boundary are characterized under certain channel parameters by designing an achievable scheme based on rate splitting, layered dirty paper coding, and successive state cancellation. In the weak regime, the sum capacity is obtained by independent dirty paper coding at two transmitters. For all the above regimes, the capacity achieves that of the IC/Z-IC without state. Comparison between the state-dependent regular IC and the Z-IC suggests that even with one interference-free link, the Z-IC does not necessarily perform better, because dirty paper coded interference in the regular IC facilitates to cancel the state through the cooperative dirty paper coding between the transmitters. [ABSTRACT FROM AUTHOR]

The variable-length source coding problem allowing the error probability up to some constant is considered for general sources. In this problem, the optimum mean codeword length of variable-length codes has already been determined. On the other hand, in this paper, we focus on the overflow (or excess codeword length) probability instead of the mean codeword length. The infimum of overflow thresholds under the constraint that both of the error probability and the overflow probability are smaller than or equal to some constant is called the optimum overflow threshold. In this paper, we first derive finite-length upper and lower bounds on these probabilities so as to analyze the optimum overflow thresholds. Then, by using these bounds, we determine the general formula of the optimum overflow thresholds in both of the first-order and second-order forms. Next, we consider another expression of the derived general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem. Finally, we apply the general formula derived in this paper to the case of stationary memoryless sources. [ABSTRACT FROM AUTHOR]

Let m be an even positive integer. A Boolean bent function ƒ on F2m-1 × F2 is called a cyclic bent function if for any a ≠ b ∈ F2m-1 and ε ∈ F2, ƒ(ax1, x2)+ ƒ(bx1, x2 + ε) is always bent, where x1 ∈ F2m-1, x2 ∈ F2. Cyclic bent functions look extremely rare. This paper focuses on cyclic bent functions on F2m-1 × F2 and their applications. The first objective of this paper is to establish a link between quadratic cyclic bent functions and a special type of prequasifields, and construct a class of quadratic cyclic bent functions from the Kantor-Williams prequasifields. The second objective is to use cyclic bent functions to construct families of optimal sequences. The results of this paper show that cyclic bent functions have nice applications in several fields such as coding theory, symmetric cryptography, and CDMA communication. [ABSTRACT FROM AUTHOR]

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors. [ABSTRACT FROM PUBLISHER]

The repair problem in distributed storage addresses recovery of the data encoded using an erasure code, for instance, a Reed–Solomon (RS) code. We consider the problem of repairing a single node or multiple nodes in RS-coded storage systems using the smallest possible amount of inter-nodal communication. According to the cut-set bound, communication cost of repairing $h\geqslant 1$ failed nodes for an $(n,k=n-r)$ maximum distance separable (MDS) code using $d$ helper nodes is at least $dhl/(d+h-k)$ , where $l$ is the size of the node. Guruswami and Wootters (2016) initiated the study of efficient repair of RS codes, showing that they can be repaired using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality. In this paper, we construct the families of RS codes that achieve the cut-set bound for repair of one or several nodes. In the single-node case, we present the RS codes of length $n$ over the field ${\mathbb F}_{q^{l}}, l=\exp ((1+o(1))n\log n)$ that meet the cut-set bound. We also prove an almost matching lower bound on $l$ , showing that super-exponential scaling is both necessary and sufficient for scalar MDS codes to achieve the cut-set bound using linear repair schemes. For the case of multiple nodes, we construct a family of RS codes that achieve the cut-set bound universally for the repair of any $h=1,2, {\dots },r$ failed nodes from any subset of $d$ helper nodes, $k\leqslant d\leqslant n-h$. For a fixed number of parities $r$ , the node size of the constructed codes is close to the smallest possible node size for codes with such properties. [ABSTRACT FROM AUTHOR]

In this paper, we study two families of codes with availability, namely, private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter imposes this property for each multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_{P}(n,k)$ and $r_{B}(n,k)$ , for PIR codes and batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$ , $r_{P}(n,k) = \Theta (\sqrt {n})$ and $r_{B}(n,k)= {\mathcal{ O}}(\sqrt {n}\log (n))$. In this paper, we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=\Theta (n^\epsilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1 and show that for all $\epsilon < 1$ , $r_{P}(n,n^\epsilon) = o(n)$ and $r_{B}(n,n^\epsilon) = o(n)$. Furthermore, several more results are proved for the case of fixed $k$. [ABSTRACT FROM AUTHOR]

This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed–Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Padé approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp–Massey type. Fourth, decoding interleaved Reed–Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: if that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp–Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt–Sidorenko–Bossert bound and the Roth–Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms. [ABSTRACT FROM AUTHOR]

This paper considers structure learning from data with $n$ samples of $p$ variables, assuming that the structure is a forest, using the Chow–Liu algorithm. Specifically, for incomplete data, we construct two model selection algorithms that complete in $O(p^{2})$ steps: one obtains a forest with the maximum posterior probability given the data and the other obtains a forest that converges to the true one as $n$ increases. We show that the two forests are generally different when some values are missing. In addition, we present estimations for benchmark data sets to demonstrate that both algorithms work in realistic situations. Moreover, we derive the conditional entropy provided that no value is missing, and we evaluate the per-sample expected redundancy for the universal coding of incomplete data in terms of the number of non-missing samples. [ABSTRACT FROM AUTHOR]

In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. Under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing, our results may be of interest for researchers working in areas as diverse as linear sketching, coding theory, matrix compression and dictionary learning. [ABSTRACT FROM AUTHOR]

An additive white Gaussian noise energy-harvesting channel with an infinite-sized battery is considered. The energy arrival process is modeled as a sequence of independent and identically distributed random variables. The channel capacity $\frac {1}{2}\log (1+P)$ is achievable by the so-called best-effort and save-and-transmit schemes where $P$ denotes the battery recharge rate. This paper analyzes the save-and-transmit scheme whose transmit power is strictly less than $P$ and the best-effort scheme as a special case of save-and-transmit without a saving phase. In the finite blocklength regime, we obtain new non-asymptotic achievable rates for these schemes that approach the capacity with gaps vanishing at rates proportional to $1/\sqrt {n}$ and $({(\log n)/n})^{1/2}$ respectively where $n$ denotes the blocklength. The proof technique involves analyzing the escape probability of a Markov process. When $P$ is sufficiently large, we show that allowing the transmit power to back off from $P$ can improve the performance for save-and-transmit. The results are extended to a block energy arrival model where the length of each energy block $L$ grows sublinearly in $n$. We show that the save-and-transmit and best-effort schemes achieve coding rates that approach the capacity with gaps vanishing at rates proportional to $\sqrt {L/n}$ and $({\max \{\log n, L\}/n})^{1/2}$ , respectively. [ABSTRACT FROM AUTHOR]

Boolean functions with high algebraic immunity are important cryptographic primitives in some stream ciphers. In this paper, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity. Via these general constructions, infinite families of minimal binary linear codes of dimension $m$ and length less than or equal to $m(m+1)/2$ are obtained. Besides, a lower bound on the minimum distance of the proposed minimal linear codes is established. Conjectures and open problems are also presented. The results of this paper show that Boolean functions with high algebraic immunity have nice applications in several fields additionally to symmetric cryptography, such as coding theory and secret sharing schemes. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of coordinating several agents through their actions, focusing on an asymmetric observation structure with two agents. Specifically, one agent knows the past, present, and future realizations of a state that affects a common payoff function, while the other agent either knows the past realizations of nothing about the state. In both cases, the second agent is assumed to have strictly causal observations of the first agent’s actions, which enables the two agents to coordinate. These scenarios are applied to distributed power control; the key idea is that a transmitter may embed information about the wireless channel state into its transmit power levels so that an observation of these levels, e.g., the signal-to-interference-plus-noise ratio, allows the other transmitter to coordinate its power levels. The main contributions of this paper are twofold. First, we provide a characterization of the set of feasible average payoffs when the agents repeatedly take long sequences of actions and the realizations of the system state are i.i.d.. Second, we exploit these results in the context of distributed power control and introduce the concept of coded power-control. We carry out an extensive numerical analysis of the benefits of coded power control over alternative power-control policies, and highlight a simple yet non-trivial example of a power control code. [ABSTRACT FROM PUBLISHER]

In this paper, we examine an input-constrained erasure channel and we characterize the asymptotics of its capacity when the erasure rate is low. More specifically, for a general memoryless erasure channel with its input supported on an irreducible finite-type constraint, we derive partial asymptotics of its capacity, using some series expansion type formula of its mutual information rate; and for a binary erasure channel with its first-order Markovian input supported on the $(1, \infty )$ -RLL constraint based on the concavity of its mutual information rate with respect to some parameterization of the input, we numerically evaluate its first-order Markov capacity and further derive its full asymptotics. The asymptotics obtained in this paper, when compared with the recently derived feedback capacity for a binary erasure channel with the same input constraint, enable us to draw the conclusion that feedback may increase the capacity of an input-constrained channel, even if the channel is memoryless. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of lossy source coding with a specific distortion measure: logarithmic loss. The focus of this paper is on the single-shot approach, which exposes crisply the connection between lossless source coding with list decoding and lossy source coding with log-loss. Fixed-length and variable-length bounds are presented. Fixed-length bounds include the single-shot fundamental limit for average as well as excess distortion. Variable-length bounds include the single-shot fundamental limit for average as well as excess length. Two multi-terminal problems are addressed: coding with side information (Wyner–Ziv) and multiple descriptions coding. In both the cases, the application of the Shannon–McMillan theorem to the single-shot bounds yields the rate-distortion function and the rate distortion-region for stationary ergodic sources. [ABSTRACT FROM PUBLISHER]

Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an $[n, k]$ erasure code encodes $k$ symbols into $n$ symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in $n$ and $k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizing code conversion—the process of converting data encoded with an $[n^{ I}, k^{ I}]$ code into data encoded with an $[{n^{ F}}, {k^{ F}}]$ code while maintaining desired decodability properties. We then introduce convertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters. [ABSTRACT FROM AUTHOR]

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

We investigate the list decodability of symbol-pair codes in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert–Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert–Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed–Solomon codes beyond the Johnson-type bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric. [ABSTRACT FROM AUTHOR]

This paper derives upper and lower bounds on the secrecy capacity-memory tradeoff of a wiretap erasure broadcast channel (BC) with ${\mathsf{K}}_{w} $ weak receivers and ${\mathsf {K}}_{s} $ strong receivers, where weak receivers and strong receivers have the same erasure probabilities and cache sizes, respectively. The lower bounds are achieved by the schemes that meticulously combine joint cache-channel coding with wiretap coding and key-aided one-time pads. The presented upper bound holds more generally for arbitrary degraded BCs and arbitrary cache sizes. When only weak receivers have cache memories, upper and lower bounds coincide for small and large cache memories, thus providing the exact secrecy capacity-memory tradeoff for this setup. The derived bounds further allow us to conclude that the secrecy capacity is positive even when the eavesdropper is stronger than all the legitimate receivers with cache memories. Moreover, they show that the secrecy capacity-memory tradeoff can be significantly smaller than its non-secure counterpart, but it grows much faster when cache memories are small. This paper also presents a lower bound on the global secrecy capacity-memory tradeoff where one is allowed to optimize the cache assignment subject to a total cache budget. It is close to the best known lower bound without secrecy constraint. For small total cache budget, the global secrecy capacity-memory tradeoff is achieved by assigning all the available cache memory uniformly over all the receivers if the eavesdropper is stronger than all the legitimate receivers, and it is achieved by assigning the cache memory uniformly only over the weak receivers if the eavesdropper is weaker than the strong receivers. [ABSTRACT FROM AUTHOR]

In the $q$ -ary online (or “causal”) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf {x} =(x_{1},\ldots,x_{n}) \in \{0,1,\ldots,q-1\}^{n}$ symbol-by-symbol via a channel limited to at most $pn$ errors and $p^{*} n$ erasures. The channel is “online” in the sense that at the $i$ th step of communication the channel decides whether to corrupt the $i$ th symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols $(x_{1},\ldots,x_{i})$. This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge of the sent codeword $\mathbf {x}$. In this paper, we study the capacity of $q$ -ary online channels for a combined corruption model, in which the channel may impose at most $pn$ errors and at most $p^{*} n$ erasures on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies, which present both upper and lower bounds on its capacity. In this paper, we give a full characterization of the capacity as a function of $q,p$ , and $p^{*}$. [ABSTRACT FROM AUTHOR]

Partial MDS (PMDS) codes are a class of erasure-correcting array codes that combine local correction of the rows with global correction of the array. An $\boldsymbol {m}\times \boldsymbol {n}$ array code is called an $(\boldsymbol {r};\boldsymbol {s})$ PMDS code if each row belongs to an ${[}\boldsymbol {n},\boldsymbol {n}-\boldsymbol {r}, \boldsymbol {r}+\textbf {1}{]}$ MDS code and the code can correct erasure patterns consisting of $\boldsymbol {r}$ erasures in each row together with $\boldsymbol {s}$ more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates $(\boldsymbol {r};\boldsymbol {s})$ PMDS codes for all $\boldsymbol {r}$ and $\boldsymbol {s}$ , its field size is exponentially large. In this paper, a family of PMDS codes with field size ${\mathcal{ O}}\left ({\max \{\boldsymbol {m},\boldsymbol {n}^{\boldsymbol {r}+\boldsymbol {s}}\}^{\boldsymbol {s}} }\right)$ is presented for the case where $\boldsymbol {r}= {\mathcal{ O}}(1), \boldsymbol {s}= {\mathcal{ O}}(1)$. [ABSTRACT FROM AUTHOR]

We show an explicit (that is, efficient and deterministic) capacity approaching interactive coding scheme that simulates any interactive protocol under random errors with nearly optimal communication rate. Specifically, over the binary symmetric channel with crossover probability $\epsilon $ , our coding scheme achieves a communication rate of $1 - O(\sqrt {H({\epsilon })})$ , together with negligible $\exp (-\Omega (\epsilon ^{4}\,\,n/\log n))$ failure probability (over the randomness of the channel). A rate of $1 - \tilde \Theta (\sqrt {H({\epsilon })})$ is likely asymptotically optimal as a result of Kol and Raz (2013) suggests. Prior to this paper, such a communication rate was achievable only using randomized coding schemes [Kol and Raz (2013); Hauepler (2014)]. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of constructing maximum distance separable (MDS) codes that enable exact reconstruction (repair) of each code block by downloading a small amount of information from the remaining code blocks. The total amount of information flow from the remaining code blocks during this reconstruction process is referred to as repair bandwidth of the underlying code. Existing constructions of exact-repairable MDS codes with optimal repair bandwidth require working with large subpacketization levels, which restrict their applicability in practice. This paper presents two general approaches to construct exact-repairable MDS codes that aim at significantly reducing the required subpacketization level at the cost of slightly suboptimal repair bandwidth. The first approach provides MDS codes that have repair bandwidth at most twice the optimal repair bandwidth. In addition, these codes also have the smallest possible subpacketization level $O(r)$ , where $r$ denotes the number of parity blocks. This approach is then generalized to design codes that have their repair bandwidth approaching the optimal repair bandwidth at the cost of graceful increment in the required subpacketization level. The second approach transforms an MDS code with optimal repair bandwidth and large subpacketization level into a longer MDS code with small subpacketization level and near-optimal repair bandwidth. For a given $r$ , the codes constructed using this approach have their subpacketization level scaling logarithmically with the code length. In addition, the obtained codes require field size only linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during the exact reconstruction of a code block. [ABSTRACT FROM AUTHOR]

High-performance steganography requires large embedding rate and small distortion, i.e., high embedding efficiency. Steganographic codes (stego-codes) derived from covering codes can improve embedding efficiency. In this paper, a new method is proposed to construct binary stego-codes for LSB embedding in gray-scale signals, which shows that not just one but a family of stego-codes can be generated from a covering code by combining Hamming codes and wet paper codes. This method can greatly expand the set of embedding schemes as applied to steganography. Performances of stego-code families (SCF) of structured codes and random codes are analyzed. SCFs of random codes can approach the rate-distortion bound on LSB embedding for any chosen embedding rate. Furthermore, SCFs are modified for applications in ±1 embedding, and a treble layered embedding method for ±2 embedding is obtained. By combining the modified SCFs and the treble layered method, a near-optimal scheme for ±2 embedding is presented. [ABSTRACT FROM AUTHOR]

This paper considers a state dependent broadcast channel with one transmitter, Alice, and two receivers, Bob and Eve. The problem is to effectively convey (“amplify”) the channel state sequence to Bob while “masking” it from Eve. The extent to which the state sequence cannot be masked from Eve is referred to as leakage. This can be viewed as a secrecy problem, where we desire that the channel state itself be minimally leaked to Eve while being communicated to Bob. This paper is aimed at characterizing the tradeoff region between amplification and leakage rates for such a system. An achievable coding scheme is presented, wherein the transmitter transmits a partial state information over the channel to facilitate the amplification process. For the case when Bob observes a stronger signal than Eve, the achievable coding scheme is enhanced with secure refinement. Outer bounds on the tradeoff region are also derived, and used in characterizing some special case results. In particular, the optimal amplification-leakage rate difference, called as differential amplification capacity, is characterized for the reversely degraded discrete memoryless channel, the degraded binary, and the degraded Gaussian channels. In addition, for the degraded Gaussian model, the extremal corner points of the tradeoff region are characterized, and the gap between the outer bound and achievable rate-regions is shown to be less than half a bit for a wide set of channel parameters. [ABSTRACT FROM PUBLISHER]

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

Polarization phenomenon over any finite field \BBFq with size $q$ being a power of a prime is considered. This problem is a generalization of the original proposal of channel polarization by Arıkan for the binary field, as well as its extension to a prime field by Şaşoğlu, Telatar, and Arıkan. In this paper, a necessary and sufficient condition of a matrix over a finite field \BBFq is shown under which any source and channel are polarized. Furthermore, the result of the speed of polarization for the binary alphabet obtained by Arıkan and Telatar is generalized to arbitrary finite field. It is also shown that the asymptotic error probability of polar codes is improved by using the Reed–Solomon matrices, which can be regarded as a natural generalization of the 2 $\,\times\,$ 2 binary matrix used in the original proposal by Arıkan. [ABSTRACT FROM AUTHOR]

In this paper, a new method is proposed to obtain full-diversity, rate-2 (rate of two complex symbols per channel use) space-time block codes (STBCs) that are full-rate for multiple input double output (MIDO) systems. Using this method, rate-2 STBCs for 4\,\times\,2, 6\,\times\,2, 8\,\times\,2, and 12\,\times\,2 systems are constructed and these STBCs are fast ML-decodable, have large coding gains, and STBC-schemes consisting of these STBCs have a non-vanishing determinant (NVD) so that they are DMT-optimal for their respective MIDO systems. It is also shown that the Srinath-Rajan code for the 4\,\times\,2 system, which has the lowest ML-decoding complexity among known rate-2 STBCs for the 4\,\times\,2 MIDO system with a large coding gain for 4-/16-QAM, has the same algebraic structure as the STBC constructed in this paper for the 4\,\times\,2 system. This also settles in positive a previous conjecture that the STBC-scheme that is based on the Srinath-Rajan code has the NVD property and hence is DMT-optimal for the 4\,\times\,2 system. [ABSTRACT FROM AUTHOR]

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

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

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

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

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

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

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

In this paper, a class of two-weight and three-weight linear codes over \mathrm GF(p) is constructed, and their application in secret sharing is investigated. Some of the linear codes obtained are optimal in the sense that they meet certain bounds on linear codes. These codes have applications also in authentication codes, association schemes, and strongly regular graphs, in addition to their applications in consumer electronics, communication and data storage systems. [ABSTRACT FROM PUBLISHER]

This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords $\mathsf {M}$ , can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the $r$ -wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum $r$ -wise Hamming distance satisfies a generalized $r$ -wise Plotkin bound. The $r$ -wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the $r$ -wise Plotkin bound with equality for all $r$. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < $\delta$ < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the $r$ -wise Hamming distance structure of the code. For a number of codewords $\mathsf {M}$ satisfying $\mathsf {M}\le 4$ and an arbitrary finite blocklength $n$ , the globally optimal codes (in the sense of minimizing the average error probability) are found. For $\mathsf {M}$ = 5 or $\mathsf {M}$ = 6 and an arbitrary finite blocklength $n$ , the optimal codes are conjectured. For larger $\mathsf {M}$ , observations regarding the optimal design are presented, e.g., that good codes have a large $r$ -wise Hamming distance structure for all $r$. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes. [ABSTRACT FROM AUTHOR]