Search

In this paper, we consider a lossy single-user caching problem with correlated sources. We first describe the fundamental interplay between the source correlations, the capacity of the user’s cache, the user’s reconstruction distortion requirements, and the final delivery-phase (compression) rate. We then illustrate this interplay using a multivariate Gaussian source example and a binary symmetric source example. To fully explore the effect of the user’s distortion requirements, we formulate the caching problem using \mathsf f -separable distortion functions recently introduce by Shkel and Verdú. The class of \mathsf f -separable distortion functions includes separable distortion functions as a special case, and our analysis covers both the expected- and excess-distortion settings in detail. We also determine what “common information” should be placed in the cache, and what information should be transmitted during the delivery phase. To this end, two new common-information measures are introduced for caching, and their relationship to the common-information measures of Wyner, Gács, and Körner is discussed in detail. [ABSTRACT FROM PUBLISHER]

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over \mathrm GF(q) with length n=(q^m-1)/(q-1) . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n=(3^{m}-1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated. [ABSTRACT FROM PUBLISHER]

In general, it is hard to find the cross correlation distribution between two sequences. In particular, there are only few cases that the cross correlation is three-valued. In this paper, new pairs of binary sequences with three cross correlation values are presented. These two sequences have different lengths: 2^2k-1 and 3(2^k-1) , respectively. We determine the cross correlation distribution between these two sequences. We also give the possible correlation values for the shift decimated sequences. The magnitude of cross correlation values is shown to be low. The techniques presented in this paper may be useful to handle other similar cases. [ABSTRACT FROM PUBLISHER]

For 35 years, the cryptographic community has created the impression that anonymous communication is always possible. Chaum’s dining cryptographer’s solution is regarded as achieving unconditional security. Chaum’s MIX approach, namely, applying a uniformly random permutation on the plaintexts to be sent, is often given as a definition for anonymity. However, people working in law enforcement know that attempts by whistle-blowers and criminals to remain at large, often fail. The content of the message may reveal the name of the sender or may leak for whom the message is really intended. To understand this issue, we give a definition of perfect anonymity. We contrast our definition with Chaum’s approach and discuss the impact on Chaum’s dining cryptographer’s solution. [ABSTRACT FROM AUTHOR]

This paper investigates the joint source-channel coding problem of sending a memoryless source over a memoryless broadcast channel. An inner bound and several outer bounds on the admissible distortion region are derived, which, respectively, generalize and unify several existing bounds. As a consequence, we also obtain an inner bound and an outer bound for the degraded broadcast channel case. When specialized to the Gaussian or binary source broadcast, the inner bound and outer bound not only recover the best known inner bound and outer bound in the literature but also generate some new results. Besides, we also extend the inner bound and outer bounds to the Wyner–Ziv source broadcast problem, i.e., source broadcast with side information available at decoders. Some new bounds are obtained when specialized to the Wyner–Ziv Gaussian and Wyner–Ziv binary cases. [ABSTRACT FROM AUTHOR]

Cyclic codes have been widely used in many applications of communication systems and data storage systems. This paper proposes a new procedure for decoding cyclic codes up to actual minimum distance. The decoding procedure consists of two steps: 1) computation of known syndromes and 2) computation of error positions and error values simultaneously. To do so, a matrix whose all entries are syndromes is called syndrome matrix. A matrix whose entries are either syndromes or the elements of a finite field is said to be partial syndrome matrix. In this paper, two novel methods are presented to determine error positions and error values simultaneously and directly. The first method uses a new partial syndrome matrix along with Gaussian elimination. The partial syndrome matrices for binary (respectively, ternary) cyclic codes of lengths from 69 to 99 (respectively, 16 to 37) are tabulated. For some cyclic codes, the partial syndrome matrices contain unknown syndromes; the second method constructs a matrix from a system of equations, which is generated by the determinants of different partial syndrome matrices and makes use of Gaussian elimination to determine its row rank. Many more cyclic codes beyond the Bose–Chaudhuri–Hocquenghem bound can be decoded with these methods. [ABSTRACT FROM AUTHOR]

Let $q$ be a prime power and $m\geq 3$ be odd. Suppose that $n=\frac {q^{2m}-1}{a}$ with $a|(q^{m}+1)$ and $3\leq a \leq 2(q^{2}-q+1)$. This paper mainly determines the actual maximum designed distance of Hermitian dual-containing Bose-Chaudhuri-Hocquenghem (BCH) codes over $\mathbb {F}_{q^{2}}$ of length $n$. Firstly, we give the maximum designed distance $\delta _{m,a}^{R}$ of narrow-sense Hermitian dual-containing BCH codes. Secondly, we show that there are also non-narrow-sense ones of designed distance up to $\delta _{m,a}^{R}$. It is worth mentioning that our maximum designed distance $\delta _{m,a}^{R}>\lceil \frac {a}{2}\rceil \delta _{m}^{A}$ , where $\delta _{m}^{A}$ is given by Aly et al. (IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1183-1188, 2007). Thus, many families of Hermitian dual-containing BCH codes with relatively large designed distance are obtained. Using the Hermitian construction to them, we can subsequently construct different classes of nonprimitive quantum codes, which are new in the sense that their parameters are not covered in the literature. [ABSTRACT FROM AUTHOR]

The tone reservation method can be used to reduce the peak to average power ratio (PAPR) in orthogonal frequency division multiplexing (OFDM) transmission systems. In this paper, the tone reservation method is analyzed for OFDM with a restricted carrier set, where only the positive carrier frequencies are used. Performing a fully analytical analysis, we give a complete characterization of the information sets for which the PAPR problem is solvable. To derive our main result, we connect the PAPR problem with a geometric functional analytic property of certain spaces. Furthermore, we present applications of our theory that give guidelines for choosing the information carriers in the finite setting and discuss a probabilistic approach for selecting the carriers. In addition, it is shown that if there exists an information sequence for which the PAPR problem is not solvable, then the set of information sequences for which the PAPR problem is not solvable is a residual set. [ABSTRACT FROM AUTHOR]

The objective of low-delay codes is to protect communication streams from erasure bursts by minimizing the time between the packet erasure and its reconstruction. Previous work has concentrated on the constant-delay scenario, where all erased packets need to exhibit the same decoding delay. We consider the case of heterogeneous delay, where the objective is to minimize the average delay across the erased packets in a burst. We derive delay lower bounds for the average case, and show that they match the constant-delay bounds only at a single rate point $R=0.5$ . We then construct codes with optimal average delays for the entire range of code rates. The construction for rates $R\leq 0.5$ achieves optimality for every erasure instance, while the construction for rates $R>0.5$ is optimal for a $(1-R)/R$ fraction of all burst instances and close to optimal for the remaining fraction. The paper also studies the benefits of delay heterogeneity within the application of sensor communications. It is shown that a carefully designed code can significantly improve the temporal precision at the receiving node following erasure-burst events. [ABSTRACT FROM PUBLISHER]

In 1964, Massey introduced a class of codes with complementary duals which are called linear complimentary dual (LCD) codes. He showed that LCD codes have applications in communication system, side-channel attack and so on. LCD codes have been extensively studied in literature. On the other hand, MDS codes form an optimal family of classical codes which have wide applications in both theory and practice. The main purpose of this paper is to give an explicit construction of several classes of LCD MDS codes, using tools from algebraic function fields. We exemplify this construction and obtain several classes of explicit LCD MDS codes for the odd characteristic case. [ABSTRACT FROM AUTHOR]

Linear complementary-dual (LCD for short) codes are linear codes that intersect with their duals trivially. LCD codes have been used in certain communication systems. It is recently found that LCD codes can be applied in cryptography. This application of LCD codes renewed the interest in the construction of LCD codes having a large minimum distance. Maximum distance separable (MDS) codes are optimal in the sense that the minimum distance cannot be improved for given length and code size. Constructing LCD MDS codes is thus of significance in theory and practice. Recently, Jin constructed several classes of LCD MDS codes through generalized Reed-Solomon codes. In this paper, a different approach is proposed to obtain new LCD MDS codes from generalized Reed-Solomon codes. Consequently, new code constructions are provided and certain previously known results by Jin are extended. [ABSTRACT FROM AUTHOR]

We consider a multi-channel communication system in which a transmitter has access to $M$ channels, but does not know the state of any of the channels. We model the channel state using an ON/OFF Markov process, and allow the transmitter to probe a single channel at predetermined probing intervals to decide over which channel to transmit. For models in which the transmitter must transmit over the probed channel, it has been shown that a myopic policy probing the channel most likely to be ON is optimal. In this paper, we allow the transmitter to select a channel over which to transmit that is potentially different from the probed channel. For a system of two channels, we show that the choice of which channel to probe does not affect the throughput. For a system with many channels, we show that a probing policy that probes the channel that is the second-most likely to be ON results in higher throughput. We extend the channel probing problem to dynamically choose when to probe based on probing history, and characterize the optimal probing policy for various scenarios. [ABSTRACT FROM PUBLISHER]

This paper considers the relationship between code-rate selection and queueing performance for communication systems subject to time-varying channel conditions. While error-correcting codes offer protection against channel uncertainties, there exists a natural tradeoff between the enhanced protection of low-rate codes and the rate penalty imposed by additional redundancy. In the limiting regime where codewords are asymptotically long, this tradeoff is well understood and characterized by the Shannon capacity. However, for delay-sensitive communication systems and finite block lengths, a complete characterization of this tradeoff is not fully developed. This paper offers a new perspective on the queueing performance of communication systems with finite block lengths operating over correlated erasure channels. A rigorous framework that links code rate to overall system performance for random codes is presented. Guidelines for code-rate selection in delay-sensitive systems are identified. These findings are supported by a numerical study. [ABSTRACT FROM AUTHOR]

Cyclic codes are a subclass of linear codes and have wide applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. In this paper, the two-prime sequence is employed to construct several classes of cyclic codes over GF(q). Lower bounds on the minimum weight of these cyclic codes are developed. Some of the codes obtained are optimal or almost optimal. The p-ranks of the twin-prime difference sets and a class of almost difference sets are computed. [ABSTRACT FROM PUBLISHER]

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]

Frequency hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. In this paper, we investigate constructions of FHSs and FHS sets with optimal partial Hamming correlation. We first establish a correspondence between FHS sets with optimal partial Hamming correlation and multiple partition-type balanced nested cyclic difference packings with a special property. By virtue of this correspondence, some FHSs and FHS sets with optimal partial Hamming correlation are constructed from various combinatorial structures, such as cyclic difference packings and cyclic relative difference families. As a consequence, our constructions yield new FHSs and FHS sets with optimal partial Hamming correlation. [ABSTRACT FROM AUTHOR]

Frequency-hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. In this paper, lower bounds on the partial Hamming correlation of FHSs and FHS sets are proposed. They slightly improve the known bounds by Eun et al. and Zhou et al. A construction of FHSs and FHS sets having optimal partial Hamming correlation with respect to the improved bounds is also presented based on the theory of generalized cyclotomy. Our construction yields optimal FHSs and FHS sets with new and flexible parameters not covered in this paper. [ABSTRACT FROM AUTHOR]

The outage probability limit is a fundamental and achievable lower bound on the word error rate of coded communication systems affected by fading. This limit is mainly determined by two parameters: the diversity order and the coding gain. With linear precoding, full diversity on a block fading channel can be achieved without error-correcting code. However, the effect of precoding on the coding gain is not well known, mainly due to the complicated expression of the outage probability. Using a geometric approach, this paper establishes simple upper bounds on the outage probability, the minimization of which yields to precoding matrices that achieve very good performance. For discrete alphabets, it is shown that the combination of constellation expansion and precoding is sufficient to closely approach the minimum possible outage achieved by an i.i.d. Gaussian input distribution, thus essentially maximizing the coding gain. [ABSTRACT FROM PUBLISHER]

This paper considers the performance of digital communication systems transmitting messages over finite-state erasure channels with memory. Information bits are protected from channel erasures using error-correcting codes; successful receptions of codewords are acknowledged at the source through instantaneous feedback. The primary focus of this research is on delay-sensitive applications, codes with finite block lengths, and, necessarily, nonvanishing probabilities of decoding failure. The contribution of this paper is twofold. A methodology to compute the distribution of the time required to empty a buffer is introduced. Based on this distribution, the mean hitting time to an empty queue and delay-violation probabilities for specific thresholds can be computed explicitly. The proposed techniques apply to situations where the transmit buffer contains a predetermined number of information bits at the onset of the data transfer. Furthermore, as additional performance criteria, large deviation principles are obtained for the empirical mean service time and the average packet-transmission time associated with the communication process. This rigorous framework yields a pragmatic methodology to select code rate and block length for the communication unit as functions of the service requirements. Examples motivated by practical systems are provided to further illustrate the applicability of these techniques. [ABSTRACT FROM AUTHOR]

We consider the problem of power allocation over one or more time-varying channels with unknown distributions in energy harvesting communications. In the single-channel case, the transmitter chooses the transmit power based on the amount of stored energy in its battery with the goal of maximizing the average rate over time. We model this problem as a Markov decision process (MDP) with transmitter as the agent, battery status as the state, transmits power as the action and rate as the reward. The average reward maximization problem can be modeled by a linear program (LP) that uses the transition probabilities for the state-action pairs and their reward values to select a power allocation policy. This problem is challenging because the uncertainty in channels implies that the mean rewards associated with the state-action pairs are unknown. We therefore propose two online learning algorithms: linear program of sample means (LPSM) and Epoch-LPSM that learn these rewards and adapt their policies over time. For both algorithms, we prove that their regret is upper-bounded by a constant. To our knowledge this is the first result showing constant regret learning algorithms for MDPs with unknown mean rewards. We also prove an even stronger result about LPSM: that its policy matches the optimal policy exactly in finite expected time. Epoch-LPSM incurs a higher regret compared with the LPSM, while reducing the computational requirements substantially. We further consider a multi-channel scenario, where the agent also chooses a channel in each slot, and present our multi-channel LPSM (MC-LPSM) algorithm that explores different channels and uses that information to solve the LP during exploitation. MC-LPSM incurs a regret that scales logarithmically in time and linearly in the number of channels. Through a matching lower bound on the regret of any algorithm, we also prove the asymptotic order optimality of MC-LPSM. [ABSTRACT FROM AUTHOR]

A mapping from \BBZN to \BBZM can be directly applied for the design of a sequence of period N with alphabet size M, where \BBZN denotes the ring of integers modulo N. The nonlinearity of such a mapping is closely related to the autocorrelation of the corresponding sequence. When M is a divisor of N, the sequence corresponding to a perfect nonlinear mapping has perfect autocorrelation, but it is not balanced. In this paper, we study balanced near-perfect nonlinear (NPN) mappings applicable for the design of sequence sets with low correlation. We first construct a new class of balanced NPN mappings from \BBZp^{2-p} to \BBZp for an odd prime p. We then present a general method to construct a frequency-hopping sequence (FHS) set from a nonlinear mapping. By applying it to the new class, we obtain a new optimal FHS set of period p^2-p with respect to the Peng–Fan bound, whose FHSs are balanced and optimal with respect to the Lempel–Greenberger bound. Moreover, we construct a low-correlation sequence set with size p, period p^2-p, and maximum correlation magnitude p from the new class of balanced NPN mappings, which is asymptotically optimal with respect to the Welch bound. [ABSTRACT FROM AUTHOR]

Sequences with optimal autocorrelation property are needed in certain communication systems and cryptography. In this paper, a construction of balanced quaternary sequences with period N \equiv 2 (mod\ 4) and optimal autocorrelation value and a construction of almost balanced binary sequences with period N \equiv 0 (mod\ 4) and optimal autocorrelation value are presented. Both constructions are a generalization of earlier ones. [ABSTRACT FROM AUTHOR]

In this paper, a multiuser communication system in which wireless users cooperate to transmit information to a base station is considered. The proposed scheme can significantly enlarge the achievable rate region, provided that the wireless connections between pairs of cooperating users are stronger than the. connection from every user to the base station. The gains in transmission rate remain substantial even when the channel phase information is only available at the receivers, not at the transmitters. In the proposed scheme, a transmission period is divided into two time intervals. During the first time interval, wireless users send data to the base station and to the neighboring users simultaneously using a broadcast channel paradigm. During the second time interval, the users cooperate to transmit information to the base station. The achievable rate region corresponding to this paradigm is characterized under a random phase channel model for a two-user system. Results are then generalized to a multiple-user scenario. For fixed system parameters, the achievable rate region is strictly larger than that of the traditional multiple-access channel, thereby allowing a fair distribution of the wireless resources among users. Numerical analysis suggests that cooperating with a single partner is enough to achieve most of the benefits associated with cooperation. [ABSTRACT FROM AUTHOR]

Frequency-hopping sequences (FHSs) with favorable partial Hamming correlation properties are desirable in many synchronization and multiple-access systems. An FHS set is said to be strictly optimal if it has optimal partial Hamming correlation for any correlation window. In this paper, we derive upper bounds on the family sizes of FHS sets with respect to partial Hamming correlation from some classical bounds on error-correcting codes. We then present strictly optimal FHS sets having optimal family sizes with respect to one of the new bounds. In particular, our construction gives new parameters not covered in the literature. [ABSTRACT FROM AUTHOR]

This paper discusses the Slepian-Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the achievable region. The technique employs a simple ‘source-splitting’ strategy that does not require common sources of randomness at the encoders and decoders. This approach allows for pipelined encoding and decoding so that the system operates with the complexity, of a single user encoder and decoder. Moreover, when this splitting approach is used in conjunction with iterative decoding methods, it produces a significant simplification of the decoding process. We demonstrate this approach for synthetically generated data. Finally, we consider the Slepian-Wolf problem when linear codes are used as syndrome-formers and consider a linear programming relaxation to maximum-likelihood (ML) sequence decoding. We note that the fractional vertices of the relaxed polytope compete with the optimal solution in a manner analogous to that observed when the ‘min-sum’ iterative decoding algorithm is applied. This relaxation exhibits the ML-certificate property: if an integral solution is found, it is the ML solution. For symmetric binary joint distributions, we show that selecting easily constructable ‘expander’-style low-density parity check codes (LDPCs) as syndrome-formers admits a positive error exponent and therefore provably good performance. [ABSTRACT FROM AUTHOR]

For the class of rate k/(k+1) convolutional codes, Yamada et al. (1983) proposed an efficient maximum-likelihood decoding algorithm called the YHM algorithm. In order to reduce the complexity of the YHM algorithm, this paper presents two techniques for simplifying the trellis diagram used in the YHM algorithm. We further observe that the proposed techniques effectively reduce the complexity of the YHM algorithm for two classes /spl Xi/ and /spl Xi//sub f/ (which is a subclass of /spl Xi/) of rate k/(k+1) convolutional codes. The construction of codes in these classes is also discussed. It is shown that /spl Xi/ codes with d/sub free/=3,4 can be obtained by simple construction. A code search algorithm for /spl Xi/ codes with d/sub free//spl ges/5 is also introduced. Computer searches are performed to construct good /spl Xi/ and /spl Xi//sub f/ codes. For specified decoding complexities, a number of these new codes give better error performance than previously reported codes. [ABSTRACT FROM PUBLISHER]

We revisit a fundamental open problem in quantum information theory, namely, whether it is possible to transmit quantum information at a rate exceeding the channel capacity if we allow for a non-vanishing probability of decoding error. Here, we establish that the Rains information of any quantum channel is a strong converse rate for quantum communication. For any sequence of codes with rate exceeding the Rains information of the channel, we show that the fidelity vanishes exponentially fast as the number of channel uses increases. This remains true even if we consider codes that perform classical post-processing on the transmitted quantum data. As an application of this result, for generalized dephasing channels, we show that the Rains information is also achievable, and thereby establish the strong converse property for quantum communication over such channels. Thus, we conclusively settle the strong converse question for a class of quantum channels that have a non-trivial quantum capacity. [ABSTRACT FROM PUBLISHER]

We correct two errors that appeared in the paper by Kaneko [ABSTRACT FROM PUBLISHER]

We investigate compressibility of the dimension of positive semidefinite matrices, while approximately preserving their pairwise inner products. This can either be regarded as compression of positive semidefinite factorizations of nonnegative matrices or (if the matrices are subject to additional normalization constraints) as compression of quantum models. We derive both lower and upper bounds on compressibility. Applications are broad and range from the analysis of experimental data to bounding the one-way quantum communication complexity of Boolean functions. [ABSTRACT FROM AUTHOR]

We present new constructions for perfect and odd perfect sequences over the quaternion group $Q_{8}$. In particular, we show for the first time that perfect and odd perfect quaternion sequences exist in all lengths $2^{t}$ for $t\geq 0$. In doing so we disprove the quaternionic form of Mow’s conjecture that the longest perfect $Q_{8}$ -sequence that can be constructed from an orthogonal array construction is of length 64. Furthermore, we use a connection to combinatorial design theory to prove the existence of a new infinite class of Williamson sequences, showing that Williamson sequences of length $2^{t} n$ exist for all $t\geq 0$ when Williamson sequences of odd length $n$ exist. Our constructions explain the abundance of Williamson sequences in lengths that are multiples of a large power of two. [ABSTRACT FROM AUTHOR]

We focus on the problem of modulating a parameter onto a power-limited signal transmitted over a discrete-time Gaussian channel and estimating this parameter at the receiver. Considering the well-known threshold effect in the non-linear modulation systems, our approach is the following: instead of deriving upper and lower bounds on the total estimation error, which weighs both weak-noise errors and anomalous errors beyond the threshold, we separate the two kinds of errors. In particular, we derive upper and lower bounds on the best achievable tradeoff between the exponential decay rate of the weak-noise expected error cost and the exponential decay rate of the probability of the anomalous error event, also referred to as the outage event. This outage event is left to be defined as a part of the communication system design problem. Our achievability scheme, which is based on lattice codes, meets the lower bound at the high signal-to-noise limit and for a certain range of tradeoffs between the weak-noise error cost and the outage exponent. [ABSTRACT FROM AUTHOR]

To apply network coding for quantum computation, we study the distributed implementation of unitary operations over all separated input and output nodes of quantum networks. We consider networks where quantum communication between nodes is restricted to sending a qubit, but classical communication is unrestricted. We analyze which $N$ -qubit unitary operations are implementable over cluster networks by investigating transformations of a given cluster network into quantum circuits. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for classical network coding. We also analyze probabilistic implementations of unitary operations over cluster networks. [ABSTRACT FROM PUBLISHER]

In quantum state redistribution as introduced by Luo and Devetak and Devetak and Yard, there are four systems of interest: the $A$ system held by Alice; the $B$ system held by Bob; the $C$ system that is to be transmitted from Alice to Bob; and the $R$ system that holds a purification of the state in the $ABC$ registers. We give upper and lower bounds on the amount of quantum communication and entanglement required to perform the task of quantum state redistribution in a one-shot setting. Our bounds are in terms of the smooth conditional min- and max-entropy, and the smooth max-information. The protocol for the upper bound has a clear structure, building on the work of Oppenheim: it decomposes the quantum state redistribution task into two simpler coherent state merging tasks by introducing a coherent relay. In the independent and identical (i.i.d.) asymptotic limit our bounds for the quantum communication cost converge to the quantum conditional mutual information $I(C;R|B)$ , and our bounds for the total cost converge to the conditional entropy $H(C|B)$ . This yields an alternative proof of optimality of these rates for quantum state redistribution in the i.i.d. asymptotic limit. In particular, we obtain a strong converse for quantum state redistribution, which even holds when allowing for feedback. [ABSTRACT FROM AUTHOR]

Given the possibility of communication systems failing catastrophically, we investigate limits to communicating over channels that fail at random times. These channels are finite-state semi-Markov channels. We show that communication with arbitrarily small probability of error is not possible. Making use of results in finite blocklength channel coding, we determine sequences of blocklengths that optimize transmission volume communicated at fixed maximum message error probabilities. We provide a partial ordering of communication channels. A dynamic programming formulation is used to show the structural result that channel state feedback does not improve performance. [ABSTRACT FROM AUTHOR]

Wireless systems offer a unique mixture of connectivity, flexibility, and freedom. It is therefore not surprising that wireless technology is being embraced with increasing vigor. For real-time applications, user satisfaction is closely linked to quantities such as queue length, packet loss probability, and delay. System performance is therefore related to, not only Shannon capacity, but also quality of service (QoS) requirements. This work studies the problem of resource allocation in the context of stringent QoS constraints. The joint impact of spectral bandwidth, power, and code rate is considered. Analytical expressions for the probability of buffer overflow, its associated exponential decay rate, and the effective capacity are obtained. Fundamental performance limits for Markov wireless channel models are identified. It is found that, even with an unlimited power and spectral bandwidth budget, only a finite arrival rate can be supported for a QoS constraint defined in terms of exponential decay rate. [ABSTRACT FROM AUTHOR]