This paper considers multiplexing two sequences of messages with two different decoding delays over a packet erasure channel. In each time slot, the source constructs a packet based on the current and previous messages and transmits the packet, which may be erased when the packet travels from the source to the destination. The destination must perfectly recover every source message in the first sequence subject to a decoding delay T v and every source message in the second sequence subject to a shorter decoding delay T u ≤ T v . We assume that the channel loss model introduces a burst erasure of a fixed length B on the discrete timeline. Under this channel loss assumption, the capacity region for the case where T v ≤ T u + B was previously solved. In this paper, we fully characterize the capacity region for the remaining case T v > T u + B.
This paper investigates the achievable rates of an additive white Gaussian noise (AWGN) energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed (i.i.d.) random variables. The blocks have length $L$, which can be interpreted as the coherence time of the energy arrival process. If $L$ is a constant or grows sublinearly in the blocklength $n$, we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability $\varepsilon$. The first-order term is known as the $\varepsilon$-capacity. In addition, we obtain lower and upper bounds on the second-order term in the asymptotic expansion, which reveal that the second order term scales as $\sqrt{\frac{L}{n}}$ for any $\varepsilon$ less than $1/2$. The lower bound is obtained through analyzing the save-and-transmit strategy. If $L$ grows linearly in $n$, we obtain lower and upper bounds on the $\varepsilon$-capacity, which coincide whenever the cumulative distribution function (cdf) of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks.
In this paper, we consider single- and multi-user Gaussian channels with feedback under expected power constraints and with non-vanishing error probabilities. In the first of two contributions, we study asymptotic expansions for the additive white Gaussian noise (AWGN) channel with feedback under the average error probability formalism. By drawing ideas from Gallager and Nakibo\u{g}lu's work for the direct part and the meta-converse for the converse part, we establish the $\varepsilon$-capacity and show that it depends on $\varepsilon$ in general and so the strong converse fails to hold. Furthermore, we provide bounds on the second-order term in the asymptotic expansion. We show that for any positive integer $L$, the second-order term is bounded between a term proportional to $-\ln_{(L)} n$ (where $\ln_{(L)}(\cdot)$ is the $L$-fold nested logarithm function) and a term proportional to $+\sqrt{n\ln n}$ where $n$ is the blocklength. The lower bound on the second-order term shows that feedback does provide an improvement in the maximal achievable rate over the case where no feedback is available. In our second contribution, we establish the $\varepsilon$-capacity region for the AWGN multiple access channel (MAC) with feedback under the expected power constraint by combining ideas from hypothesis testing, information spectrum analysis, Ozarow's coding scheme, and power control.
This paper considers transmitting a sequence of messages (a streaming source) over a packet erasure channel. In each time slot, the source constructs a packet based on the current and the previous messages and transmits the packet, which may be erased when the packet travels from the source to the destination. Every source message must be recovered perfectly at the destination subject to a fixed decoding delay. We assume that the channel loss model introduces either one burst erasure or multiple arbitrary erasures in any fixed-sized sliding window. Under this channel loss assumption, we fully characterize the maximum achievable rate by constructing streaming codes that achieve the optimal rate. In addition, our construction of optimal streaming codes implies the full characterization of the maximum achievable rate for convolutional codes with any given column distance, column span and decoding delay. Numerical results demonstrate that the optimal streaming codes outperform existing streaming codes of comparable complexity over some instances of the Gilbert-Elliott channel and the Fritchman channel.
In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. In the classical discrete memoryless network (DMN), every node incurs a delay. A well-known result for the classical DMN is the cut-set outer bound. In this paper, we generalize the model of the DMN in such a way that some nodes may incur no delay, and we obtain the cut-set bound on the capacity region of the generalized DMN. In addition, we establish the cut-set outer bound on the positive-delay region - the capacity region of the generalized DMN under the constraint that every node incurs a delay. Then, we use the cut-set bound on the positive-delay region to show that in some two-node generalized DMN, the positive-delay region is strictly smaller than the capacity region. Finally, we demonstrate that our cut-set bound on the capacity region subsumes an existing cut-set bound for the causal relay network.
Ahlswede et al., (2000) established that if coding is applied to nodes in a network, rather than routing alone, the network capacity can be improved. Li et al., (2003) proved that linear network coding is sufficient to achieve the maximum capacity in a single-source finite acyclic network. In this paper, we study variable-rate linear network coding and propose a scheme for efficient implementation
This paper revisits the Gaussian degraded relay channel, where the link that carries information from the source to the destination is a physically degraded version of the link that carries information from the source to the relay. The source and the relay are subject to expected power constraints. The ε-capacity of the channel is characterized and it is strictly larger than the capacity for any ε > 0, which implies that the channel does not possess the strong converse property. The proof of the achievability part is based on several key ideas: block Markov coding, which is used in the classical decode-forward strategy, power control for Gaussian channels under expected power constraints, and a careful scaling between the block size and the total number of block uses. The converse part is proved by first establishing two non-asymptotic lower bounds on the error probability, which are derived from the type-II errors of some binary hypothesis tests. Subsequently, each lower bound is simplified by conditioning on an event related to the power of some linear combination of the codewords transmitted by the source and the relay. Lower and upper bounds on the second-order term of the optimal coding rate are also obtained.
This paper investigates polar codes for the additive white Gaussian noise (AWGN) channel. The scaling exponent $\mu$ of polar codes for a memoryless channel $q_{Y|X}$ with capacity $I(q_{Y|X})$ characterizes the closest gap between the capacity and non-asymptotic achievable rates in the following way: For a fixed $\varepsilon \in (0, 1)$, the gap between the capacity $I(q_{Y|X})$ and the maximum non-asymptotic rate $R_n^*$ achieved by a length-$n$ polar code with average error probability $\varepsilon$ scales as $n^{-1/\mu}$, i.e., $I(q_{Y|X})-R_n^* = \Theta(n^{-1/\mu})$. It is well known that the scaling exponent $\mu$ for any binary-input memoryless channel (BMC) with $I(q_{Y|X})\in(0,1)$ is bounded above by $4.714$, which was shown by an explicit construction of polar codes. Our main result shows that $4.714$ remains to be a valid upper bound on the scaling exponent for the AWGN channel. Our proof technique involves the following two ideas: (i) The capacity of the AWGN channel can be achieved within a gap of $O(n^{-1/\mu}\sqrt{\log n})$ by using an input alphabet consisting of $n$ constellations and restricting the input distribution to be uniform; (ii) The capacity of a multiple access channel (MAC) with an input alphabet consisting of $n$ constellations can be achieved within a gap of $O(n^{-1/\mu}\log n)$ by using a superposition of $\log n$ binary-input polar codes. In addition, we investigate the performance of polar codes in the moderate deviations regime where both the gap to capacity and the error probability vanish as $n$ grows. An explicit construction of polar codes is proposed to obey a certain tradeoff between the gap to capacity and the decay rate of the error probability for the AWGN channel.
This paper revisits the Gaussian degraded relay channel, where the link that carries information from the source to the destination is a physically degraded version of the link that carries information from the source to the relay. The source and the relay are subject to expected power constraints. The $\varepsilon$-capacity of the channel is characterized and it is strictly larger than the capacity for $\varepsilon>0$, which implies that the channel does not possess the strong converse property. The proof of the achievability part is based on several key ideas: block Markov coding which is used in the classical decode-forward strategy, power control for Gaussian channels under expected power constraints, and a careful scaling between the block size and the total number of block uses. The converse part is proved by first establishing two non-asymptotic lower bounds on the error probability, which are derived from the type-II errors of some binary hypothesis tests. Subsequently, each lower bound is simplified by conditioning on an event related to the power of some linear combination of the codewords transmitted by the source and the relay. Lower and upper bounds on the second-order term of the optimal coding rate in terms of blocklength and error probability are also obtained.
This paper considers transmitting a sequence of messages (a streaming source) over a packet erasure channel. In each time slot, the source constructs a packet based on the current and the previous messages and transmits the packet, which may be erased when the packet travels from the source to the destination. Every source message must be recovered perfectly at the destination subject to a fixed decoding delay. We assume that the channel loss model introduces either one burst erasure or multiple arbitrary erasures in any fixed-sized sliding window. Under this channel loss assumption, we fully characterize the maximum achievable rate by constructing streaming codes that achieve the optimal rate. In addition, our construction of optimal streaming codes implies the full characterization of the maximum achievable rate for convolutional codes with any given column distance, column span and decoding delay. Numerical results demonstrate that the optimal streaming codes outperform existing streaming codes of comparable complexity over some instances of the Gilbert-Elliott channel and the Fritchman channel.
'%3e%3cpath fill='%23012169' d='M0 0v30h60V0z'/%3e%3cpath stroke='%23fff' stroke-width='6' d='m0 0 60 30m0-30L0 30'/%3e%3cpath stroke='%23C8102E' stroke-width='4' d='m0 0 60 30m0-30L0 30' clip-path='url(%23b)'/%3e%3cpath stroke='%23fff' stroke-width='10' d='M30 0v30M0 15h60'/%3e%3cpath stroke='%23C8102E' stroke-width='6' d='M30 0v30M0 15h60'/%3e%3c/g%3e%3c/svg%3e)
'/%3e%3cuse xlink:href='%23a' transform='translate(288.889 -214.211)'/%3e%3cuse xlink:href='%23a' transform='translate(108 342.749)'/%3e%3cuse xlink:href='%23a' transform='translate(469.189 342.749)'/%3e%3c/svg%3e)