results for au:Fong_S in:cs

- 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 induces either one burst erasure or multiple arbitrary erasures in any fixed-sized sliding window. Under this channel loss model 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.
- 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 investigates the asymptotic expansion for the maximum rate of fixed-length codes over a parallel Gaussian channel with feedback under the following setting: A peak power constraint is imposed on every transmitted codeword, and the average error probability of decoding the transmitted message is non-vanishing as the blocklength increases. It is well known that the presence of feedback does not increase the first-order asymptotics of the channel, i.e., capacity, in the asymptotic expansion, and the closed-form expression of the capacity can be obtained by the well-known water-filling algorithm. The main contribution of this paper is a self-contained proof of an upper bound on the second-order asymptotics of the parallel Gaussian channel with feedback. The proof techniques involve developing an information spectrum bound followed by using Curtiss' theorem to show that a sum of dependent random variables associated with the information spectrum bound converges in distribution to a sum of independent random variables, thus facilitating the use of the usual central limit theorem. Combined with existing achievability results, our result implies that the presence of feedback does not improve the second-order asymptotics.
- 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.
- This paper considers a multimessage network where each node may send a message to any other node in the network. Under the discrete memoryless model, we prove the strong converse theorem for any network with tight cut-set bound, i.e., whose cut-set bound is achievable. Our result implies that for any network with tight cut-set bound and any fixed rate vector that resides outside the capacity region, the average error probabilities of any sequence of length-$n$ codes operated at the rate vector must tend to $1$ as $n$ grows. The proof is based on the method of types. The proof techniques are inspired by the work of Csiszár and Körner in 1982 which fully characterized the reliability function of any discrete memoryless channel (DMC) with feedback for rates above capacity. In addition, we generalize the strong converse theorem to the Gaussian model where each node is subject to a peak power constraint. Important consequences of our results are new strong converses for the Gaussian multiple access channel (MAC) with feedback and the following relay channels under both models: The degraded relay channel (RC), the RC with orthogonal sender components, and the general RC with feedback.
- 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 investigates the scaling exponent of polar codes for binary-input energy-harvesting (EH) channels with infinite-capacity batteries. The EH process is characterized by a sequence of i.i.d. random variables with finite variances. The scaling exponent $\mu$ of polar codes for a binary-input memoryless channel (BMC) characterizes the closest gap between the capacity and non-asymptotic rates achieved by polar codes with error probabilities no larger than some non-vanishing $\varepsilon\in(0,1)$. It has been shown that for any $\varepsilon\in(0,1)$, the scaling exponent $\mu$ for any binary-input memoryless symmetric channel (BMSC) with $I(q_{Y|X})\in(0,1)$ lies between 3.579 and 4.714 , where the upper bound $4.714$ 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 any binary-input EH channel, i.e., a BMC subject to additional EH constraints. Our result thus implies that the EH constraints do not worsen the rate of convergence to capacity if polar codes are employed. The main result is proved by leveraging the following three existing results: scaling exponent analyses for BMSCs, construction of polar codes designed for binary-input memoryless asymmetric channels, and the save-and-transmit strategy for EH channels.
- 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ğ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 delay-limited communication over quasi-static fading channels under a long-term power constraint. A sequence of length-$n$ delay-limited codes for a quasi-static fading channel is said to be capacity-achieving if the codes achieve the delay-limited capacity, which is defined to be the maximum rate achievable by delay-limited codes. The delay-limited capacity is sometimes referred to as the zero-outage capacity in wireless communications. The delay-limited capacity is the appropriate choice of performance measure for delay-sensitive applications such as voice and video over fading channels. It is shown that for any sequence of capacity-achieving delay-limited codes with vanishing error probabilities, the normalized relative entropy between the output distribution induced by the length-$n$ code and the $n$-fold product of the capacity-achieving output distribution, denoted by $\frac{1}{n}D(p_{Y^n}\|p_{Y^n}^*)$, converges to zero. Additionally, we extend our convergence result to capacity-achieving delay-limited codes with non-vanishing error probabilities.
- 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.
- This paper investigates the information-theoretic limits of energy-harvesting (EH) channels in the finite blocklength regime. The EH process is characterized by a sequence of i.i.d. random variables with finite variances. We use the save-and-transmit strategy proposed by Ozel and Ulukus (2012) together with Shannon's non-asymptotic achievability bound to obtain lower bounds on the achievable rates for both additive white Gaussian noise channels and discrete memoryless channels under EH constraints. The first-order terms of the lower bounds of the achievable rates are equal to $C$ and the second-order (backoff from capacity) terms are proportional to $-\sqrt{ \frac{\log n}{n}}$, where $n$ denotes the blocklength and $C$ denotes the capacity of the EH channel, which is the same as the capacity without the EH constraints. The constant of proportionality of the backoff term is found and qualitative interpretations are provided.
- We consider a communication network consisting of nodes and directed edges that connect the nodes. The network may contain cycles. The communications are slotted where the duration of each time slot is equal to the maximum propagation delay experienced by the edges. The edges with negligible delays are allowed to be operated before the other edges in each time slot. For any pair of adjacent edges $(\ell, i)$ and $(i,j)$ where $(\ell,i)$ terminates at node $i$ and $(i,j)$ originates from node $i$, we say $(\ell,i)$ incurs zero delay on $(i,j)$ if $(\ell,i)$ is operated before $(i,j)$; otherwise, we say $(\ell,i)$ incurs a unit delay on $(i,j)$. In the classical model, every edge incurs a unit delay on every adjacent edge and the cut-set bound is a well-known outer bound on the capacity region. In this paper, we investigate the multimessage multicast network (MMN) consisting of independent channels where each channel is associated with a set of edges and each edge may incur zero delay on some other edges. Our result reveals that the capacity region of the MMN with independent channels and zero-delay edges lies within the classical cut-set bound despite a violation of the unit-delay assumption.
- We prove the strong converse for the $N$-source Gaussian multiple access channel (MAC). In particular, we show that any rate tuple that can be supported by a sequence of codes with asymptotic average error probability less than one must lie in the Cover-Wyner capacity region. Our proof consists of the following. First, we perform an expurgation step to convert any given sequence of codes with asymptotic average error probability less than one to codes with asymptotic maximal error probability less than one. Second, we quantize the input alphabets with an appropriately chosen resolution. Upon quantization, we apply the wringing technique (by Ahlswede) on the quantized inputs to obtain further subcodes from the subcodes obtained in the expurgation step so that the resultant correlations among the symbols transmitted by the different sources vanish as the blocklength grows. Finally, we derive upper bounds on achievable sum-rates of the subcodes in terms of the type-II error of a binary hypothesis test. These upper bounds are then simplified through judicious choices of auxiliary output distributions. Our strong converse result carries over to the Gaussian interference channel under strong interference as long as the sum of the two asymptotic average error probabilities less than one.
- 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. Under the classical model, every node in the network incurs a delay. In this paper, we investigate the multimessage multicast network (MMN) under a generalized-delay model which allows some nodes to incur no delay. We obtain the capacity regions for three classes of MMNs with zero-delay nodes, namely the deterministic network dominated by product distribution, the MMN consisting of independent DMCs and the wireless erasure network. In addition, we show that for any MMN belonging to one of the above three classes, the set of achievable rate tuples under the generalized-delay model and under the classical model are the same, which implies that the set of achievable rate tuples for the MMN does not depend on the delay amounts incurred by the nodes in the network.
- This paper investigates the asymptotic expansion for the size of block codes defined for the additive white Gaussian noise (AWGN) channel with feedback under the following setting: A peak power constraint is imposed on every transmitted codeword, and the average error probability of decoding the transmitted message is non-vanishing as the blocklength increases. It is well-known that the presence of feedback does not increase the first-order asymptotics (i.e., capacity) in the asymptotic expansion for the AWGN channel. The main contribution of this paper is a self-contained proof of an upper bound on the asymptotic expansion for the AWGN channel with feedback. Combined with existing achievability results for the AWGN channel, our result implies that the presence of feedback does not improve the second- and third-order asymptotics. An auxiliary contribution is a proof of the strong converse for the parallel Gaussian channels with feedback under a peak power constraint.
- The efficiency of any metaheuristic algorithm largely depends on the way of balancing local intensive exploitation and global diverse exploration. Studies show that bat algorithm can provide a good balance between these two key components with superior efficiency. In this paper, we first review some commonly used metaheuristic algorithms, and then compare the performance of bat algorithm with the so-called intermittent search strategy. From simulations, we found that bat algorithm is better than the optimal intermittent search strategy. We also analyse the comparison results and their implications for higher dimensional optimization problems. In addition, we also apply bat algorithm in solving business optimization and engineering design problems.
- This paper establishes that the strong converse holds for some classes of discrete memoryless multimessage multicast networks (DM-MMNs) whose corresponding cut-set bounds are tight, i.e., coincide with the set of achievable rate tuples. The strong converse for these classes of DM-MMNs implies that all sequences of codes with rate tuples belonging to the exterior of the cut-set bound have average error probabilities that necessarily tend to one (and are not simply bounded away from zero). Examples in the classes of DM-MMNs include wireless erasure networks, DM-MMNs consisting of independent discrete memoryless channels (DMCs) as well as single-destination DM-MMNs consisting of independent DMCs with destination feedback. Our elementary proof technique leverages properties of the Rényi divergence.
- 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. Under the classical model, every node in a discrete memoryless network (DMN) incurs a unit delay, and the capacity region of the DMN satisfies the well-known cut-set outer bound. In this paper, we propose a generalized model for the DMN where some nodes may incur no delay. Under our generalized model, we obtain a new cut-set outer bound, which is proved to be tight for some two-node DMN and is shown to subsume an existing cut-set bound for the causal relay network. In addition, we establish under the generalized model another cut-set outer bound on the positive-delay region -- the set of achievable rate tuples under the constraint that every node incurs a delay. We use the cut-set bound on the positive-delay region to show that for some two-node DMN under the generalized model, the positive-delay region is strictly smaller than the capacity region.
- We consider the two-hop interference channel (IC), which consists of two source-destination pairs communicating with each other via two relays. We analyze the degrees of freedom (DoF) of this network when the relays are restricted to perform linear schemes, and the channel gains are constant (i.e., slow fading). We show that, somewhat surprisingly, by using vector-linear strategies at the relays, it is possible to achieve 4/3 sum-DoF when the channel gains are real. The key achievability idea is to alternate relaying coefficients across time, to create different end-to-end interference structures (or topologies) at different times. Although each of these topologies has only 1 sum-DoF, we manage to achieve 4/3 by coding across them. Furthermore, we develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop interference channels with linear schemes. As for the case of complex channel gains, we characterize the sum-DoF with linear schemes to be 5/3. We also generalize the results to the multi-antenna setting, characterizing the sum-DoF with linear schemes to be 2M-1/3 (for complex channel gains), where M is the number of antennas at each node.
- We consider the two-hop interference channel (IC) with constant real channel coefficients, which consists of two source-destination pairs, separated by two relays. We analyze the achievable degrees of freedom (DoF) of such network when relays are restricted to perform scalar amplify-forward (AF) operations, with possibly time-varying coefficients. We show that, somewhat surprisingly, by providing the flexibility of choosing time-varying AF coefficients at the relays, it is possible to achieve 4/3 sum-DoF. We also develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop interference channels with time-varying AF relaying strategies.
- Oct 14 2011 cs.CY arXiv:1110.2859v1Nowadays, E-learning system is considered as one of the main pillars in the learning system. Mainly, E-Learning system is designed to serve different types of students. Thus, providing different learning pathways are a must. In this paper, we introduce the variability technique to represent the knowledge in E-learning system. This representation provides different learning pathways which supports the students' diversity. Moreover, we validate the selection of learning pathway by introducing First Order Logic (FOL) rules. Keywords Learning Pathway ; Variability and knowledge representation ; IJCSI