Search

The compute-and-forward framework permits each receiver in a Gaussian network to directly decode a linear combination of the transmitted messages. The resulting linear combinations can then be employed as an end-to-end communication strategy for relaying, interference alignment, and other applications. Recent efforts have demonstrated the advantages of employing unequal powers at the transmitters and decoding more than one linear combination at each receiver. However, neither of these techniques fit naturally within the original formulation of compute-and-forward. This paper proposes an expanded compute-and-forward framework that incorporates both of these possibilities and permits an intuitive interpretation in terms of signal levels. Within this framework, recent achievability and optimality results are unified and generalized. [ABSTRACT FROM PUBLISHER]

This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases. [ABSTRACT FROM PUBLISHER]

In this paper, we study spatially coupled low-density parity-check (SC-LDPC) codes over finite fields GF $(q)$ , q\geq 2$ , and develop design rules for q$ -ary SC-LDPC code ensembles based on their iterative belief propagation decoding thresholds, with particular emphasis on low-latency windowed decoding (WD). We consider transmission over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC) and present results for a variety of (J,K)$ -regular SC-LDPC code ensembles constructed over GF (q)$ using protographs. Thresholds are calculated using the protograph versions of q$ -ary density evolution (for the BEC) and the q$ -ary extrinsic information transfer analysis (for the BIAWGNC). We show that the WD of q increases. Moreover, we demonstrate that the new design rules provide WD thresholds that are close to capacity, even when both $m$ and $W$ are relatively small (thereby reducing decoding complexity and latency). The analysis further shows that, compared with standard flooding-schedule decoding, the WD of $q$ -ary SC-LDPC code ensembles results in significant reductions in both the decoding complexity and the decoding latency and that these reductions increase as $m$ increases. For the applications with a near-threshold performance requirement and a constraint on decoding latency, we show that using $q$ -ary SC-LDPC code ensembles, with moderate $q>2$ , instead of their binary counterparts results in reduced decoding complexity. [ABSTRACT FROM PUBLISHER]

Digital contents distributed storage systems may have different reliability and access delay requirements, and erasure codes with different strengths can provide the best storage efficiency in these systems. At the same time, in such large-scale distributed storage systems, nodes fail on a regular basis, and the contents stored on them need to be regenerated from the data downloaded from the remaining nodes. The efficiency of this repair process is an important factor that affects the overall quality of service. In this paper, we formulate the problem of multilevel diversity coding with regeneration to address these considerations, for which the storage versus repair-bandwidth tradeoff is investigated. We show that the extreme point on the optimal tradeoff curve that corresponds to the minimum possible storage can be achieved by a simple coding scheme, in which contents with different reliability requirements are encoded separately with individual regenerating codes without any mixing. On the other hand, we establish the complete storage-repair-bandwidth tradeoff for the case of four storage nodes, which reveals that codes mixing different contents can, in general, strictly improve the optimal tradeoff over the separate-coding solution. [ABSTRACT FROM PUBLISHER]

The Slepian-Wolf (SW) coding system is a source coding system with two encoders and a decoder, where these encoders independently encode source sequences from two correlated sources into codewords, and the decoder reconstructs both source sequences from the codewords. In this paper, we consider the situation in which the SW coding system is asynchronous, i.e., each encoder samples a source sequence with some unknown delay. We assume that delays are unknown but maximum and minimum values of possible delays are known to encoders and the decoder. We also assume that sources are discrete stationary memoryless and the probability mass function (PMF) of the sources is unknown but the system knows that it belongs to a certain set of PMFs. For this asynchronous SW coding system, we clarify the achievable rate region which is the set of rate pairs of encoders such that the decoding error probability vanishes as the blocklength tends to infinity. We show that this region does not always coincide with that of the synchronous SW coding system in which each encoder samples a source sequence without any delay. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over ${\mathbb F}_{2^{9}}$ and includes an example of another APN function $x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$ over ${\mathbb F}_{2^{8}}$ , known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions. [ABSTRACT FROM AUTHOR]

MDS codes and self-dual codes are important families of classical codes in coding theory. Therefore, it is of interest to investigate MDS self-dual codes. The existence of MDS self-dual codes over finite field ${\mathbb F}_{q}$ is competely solved for $q$ is even. In the literature, there are many known constructions of MDS self-dual codes for $q$ is odd. In this paper, we present a unified approach on the existence of MDS self-dual codes with concise statements and simplified proof. It is illustrated that some of known results can also be stated in this framework. Furthermore, we can obtain some new MDS self-dual codes, especially for the case when $q$ is not a square. [ABSTRACT FROM AUTHOR]

Permutation polynomials (PPs) and their inverses have applications in cryptography, coding theory and combinatorial design theory. In this paper, we make a brief summary of the inverses of PPs of finite fields, and give the inverses of all PPs of degree ≤ 6 over finite fields $\mathbb {F}_{q}$ for all $q$ and the inverses of all PPs of degree 7 over $\mathbb {F}_{2^{n}}$. The explicit inverse of a class of fifth degree PPs is the main result, which is obtained by using Lucas’ theorem, some congruences of binomial coefficients, and a known formula for the inverses of PPs of finite fields. [ABSTRACT FROM AUTHOR]

An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications, such as cryptography and coding theory. Following the idea by Wang to characterize the involutory behavior of the generalized cyclotomic mappings, this paper gives a more concise criterion for $x^{r}h(x^{s})\in {\mathbb F} _{q}[x]$ being involutions over the finite field ${\mathbb F}_{q}$ , where $r\geq 1$ and $s\,|\, (q-1)$. By using this criterion, we propose a general method to construct involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ from given involutions over some subgroups of ${\mathbb F}_{q}^{*}$ by solving congruent and linear equations over finite fields. Then, many classes of explicit involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ are obtained. [ABSTRACT FROM AUTHOR]

Functions with low differential uniformity have important applications in cryptography, coding theory, and sequence design. The differential spectrum of a cryptographic function is of great interest for estimating its resistance to some variants of differential cryptanalysis. Finding power permutations (i.e., monomial bijective mappings) over finite fields with low differential uniformity and determining their differential spectra have received a lot of attention over the past two decades. The objective of this paper is to study the differential properties of the well-known Kasami power permutations $x^{p^{2k}-p^{k}+1}$ over $ {\mathrm {GF}}(p^{n})$ , where $p$ is an odd prime and $k$ is an integer with $\gcd (n,k)=1$. It turns out that this family of monomials is differentially $(p+1)$ -uniform. Our result in the case of $p=3$ gives an affirmative solution to a recent conjecture by Xu, Cao, and Xu. Most notably, the differential spectrum of this family of power permutations is completely determined. [ABSTRACT FROM AUTHOR]

In this paper, we show that the secrecy function conjecture that states that the maximum of the secrecy function of an l -modular lattice occurs at 1/\sqrt {l} is false, by proving that the four-modular lattice C^{(4)}= \mathbb {Z}\oplus \sqrt {2} \mathbb {Z}\oplus 2 \mathbb {Z} fails to satisfy this conjecture. After this, we indicate how the secrecy function must be modified in the l -modular case to provide a more meaningful comparison for l -modular lattices, and show that this new secrecy function indeed has a maximum at for various two-modular lattices and for C^(4) . We conjecture that this must hold true for all l -modular lattices. [ABSTRACT FROM PUBLISHER]

This paper provides a simplified proof for the existence of nested lattice codebooks allowing to achieve the capacity of the additive white Gaussian noise channel, as well as the optimal rate-distortion tradeoff for a Gaussian source. The proof is self-contained and relies only on basic probabilistic and geometrical arguments. An ensemble of nested lattices that is different, and more elementary, than the one used in the previous proofs is introduced. This ensemble is based on lifting different subcodes of a linear code to the Euclidean space using Construction A. In addition to being simpler, the analysis is less sensitive to the assumption that the additive noise is Gaussian. In particular, for additive ergodic noise channels, it is shown that the achievable rates of the nested lattice coding scheme depend on the noise distribution only via its power. Similarly, the nested lattice source coding scheme attains the same rate-distortion tradeoff for all ergodic sources with the same second moment. [ABSTRACT FROM PUBLISHER]

This paper investigates the first- and second-order maximum achievable rates of codes with/without cost constraints for mixed channels whose channel law is characterized by a general mixture of (at most) uncountably many stationary and memoryless discrete channels. These channels are referred to as mixed memoryless channels with general mixture and include the class of mixed memoryless channels of finitely or countably memoryless channels as a special case. For the mixed memoryless channels with general mixture, the first-order coding theorem which gives a formula for the $\varepsilon $ -capacity is established, and then a direct part of the second-order coding theorem is provided. A subclass of mixed memoryless channels whose component channels can be ordered according to their capacity is introduced, and the first- and second-order coding theorems are established. It is shown that the established formulas reduce to several known formulas for restricted scenarios. [ABSTRACT FROM PUBLISHER]

A novel transmission scheme for cooperative relay networks is presented in this paper. The proposed scheme is based on the non-orthogonal selection decode-and-forward protocol with an additional assumption of having a low rate feedback channel from the destination to relays. Benefited from the feedback information, an optimal distributed code that has an extremely short delay equal to four is constructed, and the same code is applicable to networks with the arbitrary number of relays to yield optimal cooperative diversity. The proposed code is sphere decodable with a decoding complexity again independent of the number of relays in high SNR regime. In particular, when operating at multiplexing gain ≥(1/2), the lattice decoder at the destination has a zero complexity exponent, meaning a constant decoding complexity and independent of transmission rate. Analyses for the decoding complexity of other existing diversity-optimal distributed codes are also provided. It is shown that these codes have a linear growth in delay and an exponential growth in decoding complexity as the number of relays increases. [ABSTRACT FROM PUBLISHER]

caching of popular content during off-peak hours is a strategy to reduce network loads during peak hours. Recent work has shown significant benefits of designing such caching strategies not only to locally deliver the part of the content, but also to provide coded multicasting opportunities even among users with different demands. Exploiting both of these gains was shown to be approximately optimal for caching systems with a single layer of caches. Motivated by practical scenarios, we consider, in this paper, a hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer; the second approach provides coded multicasting opportunities across multiple layers. By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both the layers can simultaneously operate at approximately the minimum rate. [ABSTRACT FROM AUTHOR]

In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in \mathbb F2^{m} to a set of constraints in \mathbb F2 that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios. [ABSTRACT FROM AUTHOR]

In distributed storage systems, regenerating codes can achieve the optimal tradeoff between storage capacity and repair bandwidth. However, a critical drawback of existing regenerating codes, in general, is the high coding and repair complexity, since the coding and repair processes involve expensive multiplication operations in finite field. In this paper, we present a design framework of regenerating codes, which employ binary addition and bitwise cyclic shift as the elemental operations, named BASIC regenerating codes. The proposed BASIC regenerating codes can be regarded as a concatenated code with the outer code being a binary parity-check code, and the inner code being a regenerating code utilizing the binary parity-check code as the alphabet. We show that the proposed functional-repair BASIC regenerating codes can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically of functional-repair regenerating codes with less computational complexity. Furthermore, we demonstrate that the existing exact-repair product-matrix construction of regenerating codes can be modified to exact-repair BASIC product-matrix regenerating codes with much less encoding, repair, and decoding complexity from the theoretical analysis, and with less encoding time, repair time, and decoding time from the implementation results. [ABSTRACT FROM AUTHOR]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

We define the common randomness-assisted capacity of an arbitrarily varying wiretap channel (AVWC) when the eavesdropper is kept ignorant about the common randomness. We prove a multi-letter capacity formula for this model. We prove that, if enough common randomness is used, the capacity formula can be given a single-shot form again. We then consider the opposite extremal case, where no common randomness is available, and derive the capacity. It is known that the capacity of the system can be discontinuous under these circumstances. We prove here that it is still stable in the sense that it is continuous around its positivity points. We further prove that discontinuities can only arise if the legal link is symmetrizable and characterize the points where it is positive. These results shed new light on the design principles of communication systems with embedded security features. At last, we investigate the effect of super-activation of the message transmission capacity of AVWCs under the average error criterion. We give a complete characterization of those AVWCs that may be super-activated. The effect is thereby also related to the (conjectured) super-activation of the common randomness assisted capacity of AVWCs with an eavesdropper that gets to know the common randomness. Super-activation is based on the idea of wasting a few bits of non-secret messages in order to enable provably secret transmission of a large bulk of data, a concept that may prove to be of further importance in the design of communication systems. In this paper, we provide further insight into this phenomenon by providing a class of codes that is capacity achieving and does not convey any information to the eavesdropper. [ABSTRACT FROM AUTHOR]

The squashed entanglement of a quantum channel is an additive function of quantum channels, which finds application as an upper bound on the rate at which secret key and entanglement can be generated when using a quantum channel a large number of times in addition to unlimited classical communication. This quantity has led to an upper bound of $\log ((1+\eta )/(1-\eta ))$ on the capacity of a pure-loss bosonic channel for such a task, where $\eta $ is the average fraction of photons that make it from the input to the output of the channel. The purpose of this paper is to extend these results beyond the single-sender single-receiver setting to the more general case of a single sender and multiple receivers (a quantum broadcast channel). We employ multipartite generalizations of the squashed entanglement to constrain the rates at which secret key and entanglement can be generated between any subset of the users of such a channel, along the way developing several new properties of these measures. We apply our results to the case of a pure-loss broadcast channel with one sender and two receivers. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new channel model, which we name the $q$ -ary partial erasure channel (QPEC). The QPEC has a $q$ -ary input, and its output is either the input symbol or a set of $M$ ( $2 \le M \le q$ ) symbols, containing the input symbol. This channel serves as a generalization to the binary erasure channel and mimics situations when a symbol output from the channel is known only partially; that is, the output symbol contains some ambiguity, but is not fully erased. This type of channel is motivated by non-volatile memory multi-level read channels. In such channels, the readout is obtained by a sequence of current/voltage measurements, which may terminate with a partial knowledge of the stored level. Our investigation is concentrated on the performance of low-density parity-check (LDPC) codes when used over this channel, thanks to their low decoding complexity using belief propagation. We provide the exact QPEC density-evolution equations that govern the decoding process, and suggest a cardinality-based approximation as a proxy. We then provide several bounds and approximations on the proxy density evolutions, and verify their tightness through numerical experiments. Finally, we provide tools for the practical design of LDPC codes for use over the QPEC. [ABSTRACT FROM AUTHOR]

This paper introduces the covering dimension of a linear code over a finite field, which is analogous to the critical exponent of a representable matroid and, thus, generalizes invariants that lie at the heart of several fundamental problems in a coding theory. An upper bound on the covering dimension is proved, improving Kung’s classical bound for the critical exponent. In addition, a construction is given for linear codes that attain equality in this covering dimension bound. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a sequence of discrete Fourier transforms and define new versions of bent functions, which we shall call (weak and strong) octa/hexadeca and, in general, 2^k -bent functions. We investigate relationships between these classes and completely characterize the octabent and hexadecabent functions in terms of bent functions. We further find relative difference sets based upon these functions. [ABSTRACT FROM AUTHOR]

We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new way of providing cyclic structures to convolutional codes. We define the skew cyclic convolutional codes as left ideals of a quotient ring of a suitable non-commutative polynomial ring. In contrast to the previous approaches to cyclicity for convolutional codes, we use Ore polynomials with coefficients in a field (the rational function field over a finite field), so their arithmetic is very well known and we may proceed similarly to cyclic block codes. In particular, we show how to obtain easily skew cyclic convolutional codes of a given dimension, and we compute an idempotent generator of the code and its dual. [ABSTRACT FROM AUTHOR]

We introduce a new transform on Boolean functions generalizing the Walsh–Hadamard transform. For Boolean functions $q$ and $f$ , the $q$ -transform of $f$ measures the proximity of $f$ to the set of functions obtained from $q$ by change of basis. This has implications for security against certain algebraic attacks. In this paper, we derive the expected value and second moment (Parseval’s equation) of the $q$ -transform, leading to a notion of $q$ -bentness. We also develop a Poisson summation formula, which leads to a proof that the $q$ -transform is invertible. [ABSTRACT FROM AUTHOR]

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while sector-disk (SD) codes are erasure codes that address the mixed failure mode of current redundant arrays of independent disk (RAID) systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6. [ABSTRACT FROM AUTHOR]

This paper investigates the linear network coding problem for erasure broadcast channel with user feedback. An innovative linear network code is shown to be uniformly optimal for the system. In general, determining the existence of innovative packets is proved to be NP-complete. When the finite field size is larger than the number of users, innovative packets always exist and the problem of finding an innovative encoding vector with smallest Hamming weight is considered. The corresponding decision problem is shown to be NP-complete. Optimal and approximate network coding algorithms for maximizing the sparsity of encoding vectors are designed. [ABSTRACT FROM AUTHOR]

We study the problem of compression for the purpose of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem—the minimal compression rate and the error exponent—were found in a previous work, in this paper, we focus on the nonasymptotic domain and on practical, implementable schemes. We first present a finite blocklength achievability bound based on shape-gain quantization: the gain (amplitude) of the vector is compressed via scalar quantization, and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated, and they converge to the asymptotic values, as predicted by the error exponent. We then give a nonasymptotic lower bound on the performance of any compression scheme, and compare to the upper (achievability) bound. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice. [ABSTRACT FROM AUTHOR]

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered, and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario, we analyze two cases: one, where noncausal state information, is available to the encoder and the strong decoder, and the other, where state information, is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new idea of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple binnings. Finally, we discuss the optimality of using rate-splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of generating arbitrary three-party correlations from a combination of public and secret correlations. Two parties—called Alice and Bob—share perfectly correlated bits that are secret from a collaborating third party, Charlie. At the same time, all three parties have access to a separate source of correlated bits, and their goal is to convert these two resources into multiple copies of some given tripartite distribution \mathbb P(XYZ) . We obtain a single-letter characterization of the tradeoff between public and private bits that are needed to achieve this task. The rate of private bits is shown to generalize Wyner’s classic notion of common information held between a pair of random variables. The problem we consider can be contrasted fruitfully with the task of secrecy formation, in which \mathbb P(XYZ) is generated using public communication and local randomness but with Charlie functioning as an adversary instead of a collaborator. We describe in detail the differences between the collaborative and adversarial scenarios. [ABSTRACT FROM AUTHOR]

Free will (or randomness) has been studied to achieve loophole-free Bell’s inequality test and to provide device-independent quantum key distribution security proofs. The required randomness such that a local hidden variable model (LHVM) can violate the Clauser–Horne–Shimony–Holt (CHSH) inequality has been studied, but a tight bound has not been proved for a practical case that: 1) the device settings of the two parties in the Bell test are independent and 2) the device settings of each party can be correlated or biased across different runs. Using some information theoretic techniques, we prove, in this paper, a tight bound on the required randomness for this case, such that the CHSH inequality can be violated by certain LHVM. Our proof has a clear achievability and converse style. The achievability part is proved using type counting. To prove the converse part, we introduce a concept called profile for a set of binary sequences and study the properties of profiles. Our profile-based converse technique is also of independent interest. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

The classical problem in a network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers that decode the same set of messages. In this paper, computation over multicast networks is considered: each receiver decodes an identical function of the original messages. For a countably infinite class of two-transmitter two-receiver single-hop linear deterministic networks, the computation capacity is characterized for a linear function (modulo-2 sum) of Bernoulli sources. A new upper bound is derived that is tighter than cut-set-based and genie-aided bounds. A matching inner bound is established via the development of a network decomposition theorem, which identifies elementary parallel subnetworks that can constitute an original network without loss of optimality. The decomposition theorem provides a conceptually simple proof of achievability that generalizes to $L$ -transmitter $L$ -receiver networks. [ABSTRACT FROM AUTHOR]

A likelihood encoder is studied in the context of lossy source compression. The analysis of the likelihood encoder is based on the soft-covering lemma. It is demonstrated that the use of a likelihood encoder together with the soft-covering lemma yields simple achievability proofs for classical source coding problems. The cases of the point-to-point rate-distortion function, the rate-distortion function with side information at the decoder (i.e., the Wyner–Ziv problem), and the multi-terminal source coding inner bound (i.e., the Berger–Tung problem) are examined in this paper. Furthermore, a non-asymptotic analysis is used for the point-to-point case to examine the upper bound on the excess distortion provided by this method. The likelihood encoder is also related to a recent alternative technique using the properties of random binning. [ABSTRACT FROM AUTHOR]

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH , the corresponding minimum pair distance is at least dH+3 . In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance dH , the minimum pair distance is at least dH +\left \lceil{ {dH/{2}}}\right \rceil . We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, $b \geqslant 3$ , of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting. [ABSTRACT FROM AUTHOR]

In this paper, we propose two new generic attacks on the rank syndrome decoding (RSD) problem. Let C be a random [n,k] rank code over GF(q^m) and let y=x+e be a received word, such that x \in C and rank (e)=r . The first attack, the support attack, is combinatorial and permits to recover an error e of rank weight r operations on GF(q) . This new attack improves the exponent for the best generic attack for the RSD problem in the case n > m , by introducing the ratio m/n in the exponential coefficient of the previously best known attacks. The second attack, the annulator polynomial attack, is an algebraic attack based on the theory of q rather than in GF(q) as it is usually the case. We consider two approaches to solve the problem in this new setting. The linearization technique shows that if n \ge (k+1) (r+1)-1 the RSD problem can be solved in polynomial time. More generally, we prove that if , the RSD problem can be solved with an average complexity of O(r^3k^3q^r\lceil (((r+1)(k+1)-(n+1))/r) \rceil ) operations in the base field GF(q) . We also consider solving with Gröbner bases for which we discuss theoretical complexity, we also consider hybrid solving with Gröbner bases on practical parameters. As an example of application, we use our new attacks on all recent cryptosystems parameters, which repair the GPT cryptosystem, we break all examples of published proposed parameters, and some parameters are broken in less than 1 s in certain cases. [ABSTRACT FROM AUTHOR]

Wyner’s common information was originally defined for a pair of dependent discrete random variables. Its significance is largely reflected in, and also confined to, several existing interpretations in various source coding problems. This paper attempts to expand its practical significance by providing a new operational interpretation. In the context of the Gray–Wyner network, it is established that Wyner’s common information has a new lossy source coding interpretation. Specifically, it is established that, under suitable conditions, Wyner’s common information equals to the smallest common message rate when the total rate is arbitrarily close to the rate distortion function with joint decoding for the Gray–Wyner network. A surprising observation is that such equality holds independent of the values of distortion constraints as long as the distortions are within some distortion region. The new lossy source coding interpretation provides the first meaningful justification for defining Wyner’s common information for continuous random variables and the result can also be extended to that of multiple variables. Examples are given for characterizing the rate distortion region for the Gray–Wyner lossy source coding problem and for identifying conditions under which Wyner’s common information equals that of the smallest common rate. As a by-product, the explicit expression for the common information between a pair of Gaussian random variables is obtained. [ABSTRACT FROM AUTHOR]

We study the rate-distortion relationship in the set of permutations endowed with the Kendall $\tau $ -metric and the Chebyshev metric (the $\ell _\infty $ -metric). This paper is motivated by the application of permutation rate-distortion to the average-case and worst-case distortion analysis of algorithms for ranking with incomplete information and approximate sorting algorithms. For the Kendall $\tau $ -metric, we provide bounds for various distortion regimes, while for the Chebyshev metric, we present bounds that are valid for all distortions and are especially accurate for small distortions. In addition, for the Chebyshev metric, we provide a construction for covering codes. [ABSTRACT FROM AUTHOR]

In the wiretap model of secure communication, Alice is connected to Bob over a noisy channel that is eavesdropped by Eve. The goal is to provide (asymptotic) reliability and perfect secrecy assuming that the Eve has unlimited computational power. The model has attracted considerable attention in recent years because it provides a natural model for passive eavesdropping in wireless communication. We consider a wiretap model with active adversaries, and define adversarial wiretap (AWTP) channels using a (\rho r , \rho w) wiretap adversary who can read a fraction \rho r , and modify a fraction \rho w of a sent codeword. The code components that are read and/or modified can be chosen adaptively, and the subsets of read and modified components could be different. AWTP codes provide secrecy and reliability for communication over AWTP channels. We define the security and reliability of AWTP channels and use these definitions to evaluate the security and reliability of codes for these channels. This paper has two main contributions. First, we prove an upper bound on the rate of AWTP codes for (\rho r , \rho w) -AWTP channels. Second, we give an explicit construction of a perfectly secure AWTP code family with efficient decoding that achieves the bound and, hence, obtain the secrecy capacity of AWTP channels for large alphabets. AWTP model is a natural extension of Wyner’s wiretap models, and somewhat surprisingly, it is also closely related to a seemingly unrelated cryptographic primitive, secure message transmission (SMT). This relation results in a new (and the only known) bound on the transmission rate of 1-round $(\epsilon , \delta )$ -SMT protocols. We discuss our results, give their relations to other works, and propose directions for future work. [ABSTRACT FROM AUTHOR]

Due to recent applications to communications over powerlines, multilevel flash memories, and block ciphers, permutation codes have received a lot of attention from both coding and mathematical communities. One of the benchmarks for good permutation codes is the Gilbert–Varshamov bound. Although there have been several constructions of permutation codes, the Gilbert–Varshamov bound still remains to be the best asymptotical lower bound except for a recent improvement in the case of constant minimum distance. In this paper, we present an algebraic construction of permutation codes from rational function fields, and it turns out that, for a prime number $n$ of a symbol length, this class of permutation codes improves the Gilbert–Varshamov bound by a factor n$ asymptotically for a minimum distance d$ with . Furthermore, for a constant minimum distance $d$ , we improve the Gilbert–Varshamov bound by a factor $n$ as well as the recent one given by Gao et al. by a factor $n/\log n$ asymptotically for all sufficiently large $n$ . [ABSTRACT FROM PUBLISHER]

We consider the multi-user lossy source-coding problem for continuous alphabet sources. In a previous work, Ziv proposed a single-user universal coding scheme which uses uniform quantization with dither, followed by a lossless source encoder (entropy coder). In this paper, we generalize Ziv’s scheme to the multi-user setting. For this generalized universal scheme, upper bounds are derived on the redundancies, defined as the differences between the actual rates and the closest corresponding rates on the boundary of the rate region. For the mean-square error distortion measure, it is shown that this scheme can achieve redundancies of no more than 0.754 b per sample for each user. These bounds are obtained without the knowledge of the multi-user rate region, which is an open problem in general. As a direct consequence of these results, the inner and outer bounds on the rate-distortion achievable region are obtained. [ABSTRACT FROM PUBLISHER]

A q -ary code of length n , size M , and minimum distance d code. An (n,q^{k},n-k+1)_{q} code is called a maximum distance separable (MDS) code. In this paper, some MDS codes over small alphabets are classified. It is shown that every (k+d-1,q^{k},d)_{q} code with k\geq 3 , d \geq 3 , is equivalent to a linear code with the same parameters. This implies that the (6,5^4,3)5 code and the (n,7^{n-2},3)7 MDS codes for n\in \6,7,8\ are unique. The classification of one-error-correcting 8-ary MDS codes is also finished; there are 14, 8, 4, and 4 equivalence classes of (n,8^n-2,3)8 codes for $n=6,7,8$ , and 9, respectively. One of the equivalence classes of perfect (9,8^{7},3)_{8} codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction. [ABSTRACT FROM PUBLISHER]

Recently, symbol-pair codes are proposed to protect against pair errors in symbol-pair read channels. One main task in symbol-pair coding theory is to design codes with large minimum pair distance. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense they attain maximal minimum pair distance. In this paper, based on constacyclic codes, we construct some new MDS symbol-pair codes with minimum pair-distance five and six. Compared with classical $q$ -ary MDS codes, the constructed MDS symbol-pair codes have length up to q^{2}+q+1 . [ABSTRACT FROM PUBLISHER]

Mrs. Gerber’s Lemma lower bounds the entropy at the output of a binary symmetric channel in terms of the entropy of the input process. In this paper, we lower bound the output entropy via a different measure of input uncertainty, pertaining to the minimum mean squared error prediction cost of the input process. We show that in many cases our bound is tighter than the one obtained from Mrs. Gerber’s Lemma. As an application, we evaluate the bound for binary hidden Markov processes, and obtain new estimates for the entropy rate. [ABSTRACT FROM PUBLISHER]

Piggybacking is an efficient method to decrease the repair bandwidth of maximum distance separable codes. In this paper, in order to reduce the repair bandwidth of parity nodes of the known minimum storage regenerating (MSR) codes with high rate, which is usually the whole amount of the original data, i.e., the maximal, a new systematic piggybacking design is proposed through an in-depth analysis of the design of piggybacking. As a result, new MSR codes are obtained with almost optimal repair bandwidth of parity nodes while retaining the optimal repair bandwidth of systematic nodes. Furthermore, MSR codes with balanced download during node repair process are presented based on the new piggybacking design. [ABSTRACT FROM PUBLISHER]

BCH codes are an interesting type of cyclic codes and have wide applications in communication and storage systems. Generally, it is very hard to determine the minimum distances of BCH codes. In this paper, we determine the weight distributions of two classes of primitive BCH codes $\mathcal C_{(q, m, \delta _{2})}$ and $\mathcal C_{(q, m, \delta _{3})}$ and their extended codes, which solve two problems proposed by Ding et al. It is shown that the extended codes $\overline {\mathcal C}_{(q, m, \delta _{2})}$ have four nonzero weights. We also employ the Hartmann-Tzeng bound to present the minimum distance of the dual code $\mathcal C_{(q, m, \delta _{2})}^\perp $ for $q \ge 5$. Inspired by the idea, we then determine the dimensions of a class of cyclic codes and give lower bounds on their minimum distances, which is greatly improved comparing with the BCH bound. Some optimal codes are obtained. [ABSTRACT FROM AUTHOR]

Suppose $M$ records are replicated in $N$ servers (each storing all $M$ records), a user wants to privately retrieve one record by accessing the servers such that the identity of the retrieved record is secret against any up to $T$ servers. A scheme designed for this purpose is called a $T$ -private information retrieval (PIR) scheme. In practice, capacity-achieving and small sub-packetization are both desired for PIR schemes, because the former implies the highest download rate and the latter means simple realization. Meanwhile, sub-packetization is the key technique for achieving capacity. In this paper, we characterize the optimal sub-packetization for linear capacity-achieving $T$ -PIR schemes. First, a lower bound on the sub-packetization $L$ for linear capacity-achieving $T$ -PIR schemes is proved, i.e., $L\geq dn^{M-1}$ , where $d={\mathrm{ gcd}}(N,T)$ and $n=N/d$. Then, for general values of $M$ and $N>T\geq 1$ , a linear capacity-achieving $T$ -PIR scheme with sub-packetization $dn^{M-1}$ is designed. Comparing with the first capacity-achieving $T$ -PIR scheme given by Sun and Jafar in 2016, our scheme reduces the sub-packetization from $N^{M}$ to the optimal and further reduces the field size by a factor of $Nd^{M-2}$. [ABSTRACT FROM AUTHOR]

Fast polarization is crucial for the performance guarantees of polar codes. In the memoryless setting, the rate of polarization is known to be exponential in the square root of the block length. A complete characterization of the rate of polarization for models with memory has been missing. Namely, previous works have not addressed fast polarization of the high entropy set under memory. We consider polar codes for processes with memory that are characterized by an underlying ergodic finite-state Markov chain. We show that the rate of polarization for these processes is the same as in the memoryless setting, both for the high and for the low entropy sets. [ABSTRACT FROM AUTHOR]

A new finite blocklength converse for the Slepian–Wolf coding problem, which significantly improves on the best-known converse due to Miyake and Kanaya, is presented. To obtain this converse, an extension of the linear programming (LP)-based framework for finite blocklength point-to-point coding problems is employed. However, a direct application of this framework demands a complicated analysis for the Slepian–Wolf problem. An analytically simpler approach is presented, wherein LP-based finite blocklength converses for this problem are synthesized from point-to-point lossless source coding problems with perfect side-information at the decoder. New finite blocklength converses for these point-to-point problems are derived by employing the LP-based framework, and the new converse for Slepian–Wolf coding is obtained by an appropriate combination of these converses. [ABSTRACT FROM AUTHOR]