IEEE Transactions on Information Theory

Distribuir contenido
TOC Alert for Publication# 18
Updated: hace 9 horas 52 mins

Table of contents

Vie, 12/01/2017 - 00:00

A Simple Proof of Fast Polarization

Vie, 12/01/2017 - 00:00
Fast polarization is a key property of polar codes. It was proved for the binary polarizing $2 times 2$ kernel by Arıkan and Telatar. The proof was later adapted to the general case by Şaşoğlu. We give a simplified proof.

Capacity-Achieving Rate-Compatible Polar Codes

Vie, 12/01/2017 - 00:00
A method of constructing rate-compatible polar codes that are capacity achieving at multiple code rates with low-complexity sequential decoders is presented. The underlying idea of the construction exploits certain common characteristics of polar codes that are optimized for a sequence of successively degraded channels. The proposed code consists of parallel concatenation of multiple polar codes with information-bit divider at the input of each polar encoder. Thus, it is referred to as parallel concatenated polar (PCP) codes. A lower-rate PCP code is simply constructed by adding more constituent polar codes, which enables incremental retransmissions at different rates in order to adapt to channel conditions. Due to the length limitation of polar codes, the PCP code can only support a restricted set of rates that is characterized by the size of the kernel when conventional polar codes are used. To overcome this limitation, punctured polar codes, which provide more flexibility on blocklength by controlling a puncturing fraction, are considered as constituent codes. The existence of capacity-achieving punctured polar codes for any given puncturing fraction is proven. Using such punctured polar codes as constituent codes, it is shown that the proposed PCP code is capacity achieving for an arbitrary sequence of rates and for any class of degraded channels.

Splitter Sets and $k$ -Radius Sequences

Vie, 12/01/2017 - 00:00
Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict-avoiding codes. The study of $k$ -radius sequences was motivated by some problems occurring in large data transfer. It is observed that the existence of splitter sets yields $k$ -radius sequences of short length. In this paper, we obtain several new results contributing to splitter sets and $k$ -radius sequences. We give some new constructions of perfect splitter sets, as well as some nonexistence results on them. As a byproduct, we obtain some new results on optimal conflict-avoiding codes. Furthermore, we provide several explicit constructions of short $k$ -radius sequences for certain values of $n$ , by establishing the existence of $k$ -additive sequences. In particular, we show that for any fixed $k$ , there exist infinitely many values of $n$ such that $f_{k}(n) =frac {n^{2}}{2k}+O(n)$ , where $f_{k} (n)$ denotes the shortest length of an $n$ -ary $k$ -radius sequence. This result partially affirms a conjecture posed by Bondy, Lonc, and Rzążewski.

Construction of Sequences With High Nonlinear Complexity From Function Fields

Vie, 12/01/2017 - 00:00
Complexity of sequences plays an important role in pseudorandom sequences and cryptography. In this paper, we present a construction of sequences with high nonlinear complexity from function fields. The main idea is to make use of function fields with many rational places as well as an automorphism of large order. We illustrate our construction through rational function fields and cyclotomic function fields in which there exist some automorphisms of large order. It turns out that we are able to: 1) slightly increase the length of the inversive sequence without losing nonlinear complexity and 2) obtain sequences with much larger nonlinear complexity than random sequences.

Coset Construction for Subspace Codes

Vie, 12/01/2017 - 00:00
One of the main problems of the research area of network coding is to compute good lower and upper bounds of the achievable cardinality of so-called subspace codes in ${ mathcal {P}_{q}(n)}$ , i.e., the set of subspaces of $mathbb {F}_{q}^{n}$ , for a given minimal distance. Here we generalize a construction of Etzion and Silberstein to a wide range of parameters. This construction, named coset construction, improves or attains several of the previously best-known subspace code sizes and attains the maximum-rank distance bound for an infinite family of parameters.

Constacyclic Symbol-Pair Codes: Lower Bounds and Optimal Constructions

Vie, 12/01/2017 - 00:00
Symbol-pair codes introduced by Cassuto and Blaum (2010) are designed to protect against pair errors in symbol-pair read channels. The higher the minimum pair distance, the more pair errors the code can correct. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense that pair distance cannot be improved for given length and code size. The contribution of this paper is twofold. First, we present three lower bounds for the minimum pair distance of constacyclic codes, the first two of which generalize the previously known results due to Cassuto and Blaum (2011) and Kai et al. (2015). The third one exhibits a lower bound for the minimum pair distance of repeated-root cyclic codes. Second, we obtain new MDS symbol-pair codes with minimum pair distance seven and eight through repeated-root cyclic codes.

Constructions of Formally Self-Dual Codes Over $ {mathbb Z}_{4}$ and Their Weight Enumerators

Vie, 12/01/2017 - 00:00
We present three explicit methods for construction of formally self-dual codes over $ {mathbb Z}_{4}$ . We characterize relations between Lee weight enumerators of formally self-dual codes of length $n$ over $ {mathbb Z}_{4}$ and those of length $n+2$ ; the first two construction methods are based on these relations. The last construction produces free formally self-dual codes over $ {mathbb Z}_{4}$ . Using these three constructions, we can find free formally self-dual codes over $ {mathbb Z}_{4}$ , as well as non-free formally self-dual codes over $ {mathbb Z}_{4}$ of all even lengths. We find free or non-free formally self-dual codes over $ {mathbb Z}_{4}$ of lengths up to ten using our constructions. In fact, we obtain 46 inequivalent formally self-dual codes whose minimum Lee weights are larger than self-dual codes of the same length. Furthermore, we find 19 non-linear extremal binary formally self-dual codes of lengths 12, 16, and 20, up to equivalence, from formally self-dual codes over $ {mathbb Z}_{4}$ by using the Gray map.

Coding for the $boldsymbol ell _infty $ -Limited Permutation Channel

Vie, 12/01/2017 - 00:00
We consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted codeword ${x}=(x_{1},ldots ,x_{n})$ is corrupted by a permutation $pi in S_{n}$ to yield the received word ${y}=(y_{1},ldots ,y_{n})$ , where $y_{i}=x_{pi (i)}$ . We initiate the study of worst case (or zero-error) communication over permutation channels that distort the information by applying permutations $pi $ , which are limited to displacing any symbol by at most $r$ locations, i.e., permutations $pi $ with weight at most $r$ in the $ell _infty $ -metric. We present direct and recursive constructions, as well as bounds on the rate of such channels for binary and general alphabets. Specific attention is given to the case of $r=1$ .

Index Coding With Erroneous Side Information

Vie, 12/01/2017 - 00:00
In this paper, new index coding problems are studied, where each receiver has erroneous side information. Although side information is a crucial part of index coding, the existence of erroneous side information has not been considered yet. We study an index code with receivers that have erroneous side information symbols in the error-free broadcast channel, which is called an index code with side information errors (ICSIE). The encoding and decoding procedures of the ICSIE are proposed, based on the syndrome decoding. Then, we derive the bounds on the optimal codelength of the proposed index code with erroneous side information. Furthermore, we introduce a special graph for the proposed index coding problem, called a $delta _{s}$ -cycle whose properties are similar to those of the cycle in the conventional index coding problem. Properties of the ICSIE are also discussed in the $delta _{s}$ -cycle and clique. Finally, the proposed ICSIE is generalized to an index code for the scenario having both additive channel errors and side information errors, called a generalized error correcting index code.

Zero-Error Capacity of $ P $ -ary Shift Channels and FIFO Queues

Vie, 12/01/2017 - 00:00
The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zero-error capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an $n $ -cell register, where each cell is either empty or contains a particle of one of $P $ possible types and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a $P $ -ary alphabet through a queuing system with an infinite buffer and a first-in-first-out service procedure and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems.

Zero-Error Relaying for Primitive Relay Channels

Vie, 12/01/2017 - 00:00
In a primitive relay channel, a new one-shot relaying scheme termed color-and-forward is proposed that guarantees a probability of error equal to zero. This relaying scheme constructs a relaying compression graph of relay outputs based on the joint conditional distribution of the relay and destination outputs, and forwards a minimum coloring of this graph. The $n$ -letter extension of the proposed color-and-forward scheme is shown to be optimal in the sense that it results in the smallest needed out-of-band relay to destination link rate for the overall message rate to equal the single-input multiple-output outer bound for any fixed number of channel uses. This is used to obtain an upper bound on the asymptotic minimal relay to destination link rate needed to achieve the single-input multiple-output outer bound.

Polynomial Singular Value Decompositions of a Family of Source-Channel Models

Vie, 12/01/2017 - 00:00
In this paper, we show that the conditional expectation operators corresponding to a family of source-channel models, defined by natural exponential families with quadratic variance functions and their conjugate priors, have orthonormal polynomials as singular vectors. These models include the Gaussian channel with Gaussian source, the Poisson channel with gamma source, and the binomial channel with beta source. To derive the singular vectors of these models, we prove and employ the equivalent condition that their conditional moments are strictly degree preserving polynomials.

On Empirical Cumulant Generating Functions of Code Lengths for Individual Sequences

Vie, 12/01/2017 - 00:00
We consider the problem of lossless compression of individual sequences using finite-state (FS) machines, from the perspective of the best achievable empirical cumulant generating function (CGF) of the code length, i.e., the normalized logarithm of the empirical average of the exponentiated code length. Since the probabilistic CGF is minimized in terms of the Rényi entropy of the source, one of the motivations of this paper is to derive an individual-sequence analogue of the Rényi entropy, in the same way that the FS compressibility is the individual-sequence counterpart of the Shannon entropy. We consider the CGF of the code-length both from the perspective of fixed-to-variable length coding and the perspective of variable-to-variable (V-V) length coding, where the latter turns out to yield a better result, that coincides with the FS compressibility. We also extend our results to compression with side information, available at both the encoder and decoder. In this case, the V-V version no longer coincides with the FS compressibility, but results in a different complexity measure.

A Proof of the Strong Converse Theorem for Gaussian Broadcast Channels via the Gaussian Poincaré Inequality

Vie, 12/01/2017 - 00:00
We prove that the Gaussian broadcast channel with two destinations admits the strong converse property. This implies that for every sequence of block codes operated at a common rate pair with an asymptotic average error probability < 1, the rate pair must lie within the capacity region derived by Cover and Bergmans. The main mathematical tool required for our analysis is a logarithmic Sobolev inequality known as the Gaussian Poincaré inequality.

Variants of the Entropy Power Inequality

Vie, 12/01/2017 - 00:00
An extension of the entropy power inequality to the form $N_{r}^alpha (X+Y) geq N_{r}^alpha (X) + N_{r}^alpha (Y)$ with arbitrary independent summands $X$ and $Y$ in $ {mathbb {R}}^{n}$ is obtained for the Rényi entropy and powers $alpha geq ~(r+1)/2$ .

Secure Transmission on the Two-Hop Relay Channel With Scaled Compute-and-Forward

Vie, 12/01/2017 - 00:00
In this paper, we consider communication on a two-hop channel in which a source wants to send information reliably and securely to the destination via a relay. We consider both the untrusted relay case and the external eavesdropper case. In the untrusted relay case, the relay behaves as an eavesdropper, and there is a cooperative node, which sends a jamming signal to confuse the relay when it is receiving from the source. In the external eavesdropper case, the relay is trusted, and there is an external node eavesdropping the communication. We propose two secure transmission schemes using the scaled compute-and-forward technique. One of the schemes is based on a random binning code, and the other one is based on a lattice chain code. It is proved that in the high signal-to-noise-ratio (SNR) scenario and/or the limited relay power scenario, if the destination is used as the jammer, both schemes outperform all existing schemes and achieve the upper bound. In particular, if the SNR is large and the source, the relay, and the cooperative jammer have identical power and channels, both schemes achieve the upper bound for secrecy rate, which is merely 1/2 bit per channel use lower than the channel capacity without secrecy constraints. We also prove that one of our schemes achieves a positive secrecy rate in the external eavesdropper case in which the relay is trusted and there exists an external eavesdropper.

MSE Estimates for Multitaper Spectral Estimation and Off-Grid Compressive Sensing

Vie, 12/01/2017 - 00:00
We obtain estimates for the mean squared error (MSE) for the multitaper spectral estimator and certain compressive acquisition methods for multi-band signals. We confirm a fact discovered by Thomson [Spectrum estimation and harmonic analysis, Proc. IEEE, 1982]: assuming bandwidth $W$ and $N$ time domain observations, the average of the square of the first $K=lfloor 2NWrfloor$ Slepian functions approaches, as $K$ grows, an ideal bandpass kernel for the interval $[ -W,W]$ . We provide an analytic proof of this fact and measure the corresponding rate of convergence in $L^{1}$ norm. This validates a heuristic approximation used to control the MSE of the multitaper estimator. The estimates have also consequences for the method of compressive acquisition of multi-band signals introduced by Davenport and Wakin, giving MSE approximation bounds for the dictionary formed by modulation of the critical number of prolates.

Distributions of Multivariate Correlated Rayleigh and Rician Fading

Vie, 12/01/2017 - 00:00
Single-integral expressions for cumulative distribution functions of multivariate correlated Rayleigh and Rician fading are studied. Mathematical mistakes in the literature are identified and corrected. Corrections are cross-verified against well-known findings in the literature, which can be employed to advance further theoretical developments for correlated fading.