Outer bounds on the capacity of interference channels (Corresp.)

New outer bounds are demonstrated for the capacity regions of discrete memoryless interference channels and Gaussian interference channels. The bound for discrete channels coincides with the capacity region in special cases. The bound for Gaussian channels improves previous knowledge when the interference is of medium strength.     

The Two-User Compound Interference Channel

We introduce the two-user finite state compound interference channel. The main contributions involve both novel inner and outer bounds. For the Gaussian case, we characterize its capacity region to within one bit. The inner bound is multilevel superposition coding but the decoding of the levels is opportunistic, depending on the channel state. The genie aided outer bound is motivated by the typical error events of the achievable scheme.     

A New Outer Bound and the Noisy-Interference Sum–Rate Capacity for Gaussian Interference Channels

A new outer bound on the capacity region of Gaussian interference channels is developed. The bound combines and improves existing genie-aided methods and is shown to give the sum–rate capacity for noisy interference as defined in this paper. Specifically, it is shown that if the channel crosstalk coefficient magnitudes lie below thresholds defined by the power constraints then single-user detection at each receiver is sum–rate optimal, i.e., treating the interference as noise incurs no loss in performance. This is the first capacity result for the Gaussian interference channel with weak to moderate interference. Furthermore, for certain mixed (weak and strong) interference scenarios, the new outer bounds give a corner point of the capacity region.      

Discrete Memoryless Interference and Broadcast Channels With Confidential Messages: Secrecy Rate Regions

We study information-theoretic security for discrete memoryless interference and broadcast channels with independent confidential messages sent to two receivers. Confidential messages are transmitted to their respective receivers while ensuring mutual information-theoretic secrecy. That is, each receiver is kept in total ignorance with respect to the message intended for the other receiver. The secrecy level is measured by the equivocation rate at the eavesdropping receiver. In this paper, we present inner and outer bounds on secrecy capacity regions for these two communication systems. The derived outer bounds have an identical mutual information expression that applies to both channel models. The difference is in the input distributions over which the expression is optimized. The inner bound rate regions are achieved by random binning techniques. For the broadcast channel, a double-binning coding scheme allows for both joint encoding and preserving of confidentiality. Furthermore, we show that, for a special case of the interference channel, referred to as the switch channel, derived bounds meet. Finally, we describe several transmission schemes for Gaussian interference channels and derive their achievable rate regions while ensuring mutual information-theoretic secrecy. An encoding scheme in which transmitters dedicate some of their power to create artificial noise is proposed and shown to outperform both time-sharing and simple multiplexed transmission of the confidential messages.     

一种符号执行制导的循环内界分析方法

循环是计算机中重要的复杂程序结构.很多应用场景要求静态分析循环可能达到的最大迭代次数,即循环边界（Loop Bound）.对应技术在文献中被称为循环边界分析（Loop Bound Analysis）.现有的循环边界分析均使用保守方式进行外界分析,即产生略高于循环边界的近似值.基于这一现状,本文提出了一种自动地循环内界分析方法,产生略低于循环边界的近似值.当用户综合利用外界与内界分析,能将循环边界值约束到一个统计区间,从而能对分析结果获得更为完整的认识.本文基于循环条件制导的符号执行（Symbolic Execution）技术实现了循环内界分析,该技术的本质在于它能够利用符号执行符号化推导程序执行约束的特点,准确求解循环在程序所有合法输入条件下的边界值,并由生成的测试用例来保证该边界值一定可达（即保证是循环内界）.本文对符号执行制导技术进行了优化,并在多组已有研究采用的基准用例集上进行了实例评估,实验结果表明,本文的循环内界分析方法具备准确性和高效性,可以满足应用需求.     

Capacity Bounds for Broadcast Channels With Confidential Messages

This paper studies capacity bounds for discrete memoryless broadcast channels with confidential messages. Two private messages as well as a common message are transmitted; the common message is to be decoded by both receivers, while each private message is only for its intended receiver. In addition, each private message is to be kept secret from the unintended receiver where secrecy is measured by equivocation. Both inner and outer bounds are proposed to the rate equivocation region for broadcast channels with confidential messages. The proposed inner bound generalizes Csiszar and Korner's rate equivocation region for broadcast channels with a single confidential message, Liu 's achievable rate region for broadcast channels with perfect secrecy, Marton's and Gel'fand-Pinsker's achievable rate region for general broadcast channels. The proposed outer bounds, together with the inner bound, help establish the rate equivocation region of several classes of discrete memoryless broadcast channels with confidential messages, including the less noisy, deterministic, and semideterministic broadcast channels. Furthermore, specializing to the general broadcast channel by removing the confidentiality constraint, the proposed outer bounds reduce to new capacity outer bounds for the discrete memory broadcast channel.     

Rate Regions for Relay Broadcast Channels

A partially cooperative relay broadcast channel (RBC) is a three-node network with one source node and two destination nodes (destinations 1 and 2) where destination 1 can act as a relay to assist destination 2. Inner and outer bounds on the capacity region of the discrete memoryless partially cooperative RBC are obtained. When the relay function is disabled, the inner bound reduces to an inner bound on the capacity region of broadcast channels that includes an inner bound of Marton, and GePfand and Pinsker. The outer bound reduces to a new outer bound on the capacity region of broadcast channels that generalizes an outer bound of Marton to include a common message, and that generalizes an outer bound of GePfand and Pinsker to apply to general discrete memoryless broadcast channels. The proof for the outer bound simplifies the proof of GePfand and Pinsker that was based on a recursive approach. Four classes of RBCs are studied in detail. For the partially cooperative RBC with degraded message sets, inner and outer bounds are obtained. For the semideterministic partially cooperative RBC and the orthogonal partially cooperative RBC, the capacity regions are established. For the parallel partially cooperative RBC with unmatched degraded subchannels, the capacity region is established for the case of degraded message sets. The capacity is also established when the source node has only a private message for destination 2, i.e., the channel reduces to a parallel relay channel with unmatched degraded subchannels.     

On symbol error probability bounds for ISI-like channels

Some issues with Forney's upper and lower bounds (1972) for the symbol error probability in systems with memory (e.g., intersymbol interference channels) have been pointed out in the literature. We expound on these issues. For the upper bound, we show that, although the most commonly cited proofs are not logically consistent, the bound is true for more general conditions. The reasoning leading to the lower bound is shown to be flawed and, in general,to lead to invalid lower bounds. We suggest a lower bound based on Mazo's bound (1975) as an alternative     

Performance bounds for power control supported DCA-algorithms inhighway micro cellular radio systems

To achieve a high spectrum efficiency in cellular radio systems, the radio resource allocation algorithms have to be adaptive to the actual traffic and interference situation. The focus of the paper is on performance bounds of a cellular radio system using dynamic channel assignment (DCA) combined with power control (PC). A trivial upper bound on the performance is identified. The bound is given by the performance of a hypothetical system which is able to use all channels simultaneously in all cells. A lower bound on the performance is derived from a theoretical PC supported DCA-algorithm. For a highway micro cellular system and a deterministic propagation model, numerical results show that the lower and upper bounds are tight. That is, the results indicate that it is possible to use all channels in all cells simultaneously and still provide an acceptable signal-to interference ratio in all assigned communication links     

On the symmetric information rate of two-dimensional finite-state ISI channels

We derive a pair of bounds (upper and lower) on the symmetric information rate of a two-dimensional finite-state intersymbol interference (ISI) channel model. For channels with small impulse response support, they can be estimated via a modified forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm. The convergence of the bounds is also analyzed. To relax the constraint on the size of the impulse response, a new upper bound is proposed which allows the tradeoff of the computational complexity and the tightness of the bound. These bounds are further extended to d-dimensional (d>2) ISI channels.     

On multiple interference error bounds

This letter presents upper and lower bounds for the error rate for (effectively) PAM signalling in the presence of thermal noise, cochannel interference, and intersymbol interference. To accomplish this, two known bounds and one new lower bound are used. For a class of examples from the literature, these simple bounds were found to provide an error-rate estimate accurate to 1 db in system SNR. Computational experiments indicate that this level of accuracy can be achieved when the system's eye is open by at least a factor of two.     

BER performance of turbo-coded PPM CDMA systems on optical fiber

We obtain upper bounds on the bit error rate (BER) for turbo-coded optical code-division multiple-access (CDMA) systems using pulse position modulation (PPM). We use transfer function bounding techniques to obtain these bounds, so our results correspond to the average bound over all interleavers of a given length. We consider parallel concatenated coding (PCC) schemes that use recursive convolutional codes as constituent codes. We consider systems using an avalanche photodiode (APD), and treat APD noise, thermal noise, and multi-user interference using a Gaussian approximation. We compare the performance of turbo-coded systems with that of BCH-coded systems with soft-decision decoding, and that of concatenated coding systems with outer Reed-Solomon (RS) code and inner convolutional code. We show that turbo-coded systems have better performance than BCH-coded systems. We also show that concatenated systems have better performance than turbo-coded systems when the block length is small and the received laser power is somewhat large     

Bounds on the interchannel interference of OFDM in time-varyingimpairments

In this article, tight and universal bounds have been derived for the interchannel interference (ICI) of an orthogonal frequency-division multiplexing (OFDM) signal resulting from Doppler spread. The universal bound depends only on the product of the maximum Doppler frequency and the OFDM symbol duration. The tight bound also depends on the variance of the Doppler spectrum. Compared with the exact ICI expressions derived by other researchers, these bounds are easier to evaluate and can provide useful insight     

Gaussian Interference Networks: Sum Capacity in the Low-Interference Regime and New Outer Bounds on the Capacity Region

Establishing the capacity region of a Gaussian interference network is an open problem in information theory. Recent progress on this problem has led to the characterization of the capacity region of a general two-user Gaussian interference channel within one bit. In this paper, we develop new, improved outer bounds on the capacity region. Using these bounds, we show that treating interference as noise achieves the sum capacity of the two-user Gaussian interference channel in a low-interference regime, where the interference parameters are below certain thresholds. We then generalize our techniques and results to Gaussian interference networks with more than two users. In particular, we demonstrate that the total interference threshold, below which treating interference as noise achieves the sum capacity, increases with the number of users.     

Bounds on information combining

When the same data sequence is transmitted over two independent channels, or when a data sequence is transmitted twice but independently over the same channel, the independent observations can be combined at the receiver side. From an information-theory point of view, the overall mutual information between the data sequence and the received sequences represents a combination of the mutual information of the two channels. This concept is termed information combining. A lower bound and an upper bound on the combined information is presented, and it is proved that these bounds are tight. Furthermore, this principle is extended to the computation of extrinsic information on single code bits for a repetition code and for a single parity-check code of length three, respectively. For illustration of the concept and the bounds on information combining, two applications are considered. First, bounds on the information processing characteristic (IPC) of a parallel concatenated code are derived from its extrinsic information transfer (EXIT) chart. Second, bounds on the EXIT chart for an outer repetition code and for an outer single parity-check code of a serially concatenated coding scheme are computed.     

Error Rate Lower Bounds for Digital Communication with Multiple Interferences

This paper presents simple and general lower bounds for error rates in digital communication systems. The information bearing signal is taken to be impaired by additive interference and carrier phase jitter. The former is taken to be composed of two components; one component is peak-limited while the other is not. Intersymbol and cochannel interference are examples of peak-limited interference while additive thermal noise is an example of a nonpeak-limited interference. The novelty of the paper is in the generality of the results and in obtaining a simple error bound for transmission in the presence of cochannel interference and carrier phase jitter.     

Near-optimal limited-search detection on ISI/CDMA channels anddecoding of long convolutional codes

We derive an upper bound on the bit-error probability (BEP) in limited-search detection over a finite interference channel. A unified channel model is presented; this includes finite-length intersymbol interference channels and multiuser CDMA channels as two special cases. We show that the BEP of the M-algorithm (MA) is bounded from above by the sum of three terms: an upper bound on the error probability of the Viterbi (1967) algorithm (VA) detection given by Forney Jr. (1972), and upper bounds on the error probabilities of two types of erroneous decision caused by the correct path loss event. We prove that error propagation (in terms of the mean recovery step number) is finite for all finite interference channels. The convergence and asymptotic behavior of the upper bounds are studied. The results show that, if a channel satisfies certain mild conditions, all series in the bounds are convergent. One of the key results is that, for any finite interference channel satisfying certain mild conditions. the asymptotic BEP of the MA is bounded by the same upper and lower bounds (which have the same asymptotical behavior) as those for the VA if the correct path loss probability is smaller than that of the VA. Furthermore, we extend the above results to near optimally decode long convolutional codes in a short packet format (about 200-300 bits). We present a nonsorting combined M/T algorithm and showed that the M/T algorithm with M>2( ^dfree/ⁿ) and T>(d_freeE_b)/n can near-optimally decode the code. We also propose a hierarchical decoding algorithm (HDA) to further cut down the average decoding complexity. Numerical results show that the bounds are reasonably tight. The HDA can achieve a performance within about 0.8 dB of the sphere-packing lower bound for a packet error rate of 10^-4 and a packet length below 200 bits, which is the best reported decoding performance so far for block sizes from 100 to 200 bits     

On the capacity region of a discrete two-user channel for strong interference (Corresp.)

The capacity region of a simple discrete two-user channel for the transmission of two separate messages is studied in the strong interference case. It is shown that in this case the inner bound to the capacity region practically coincides with the outer bound.     

On degraded Gaussian two-user channels (Corresp.)

Several bounds to the capacity region of a degraded Gaussian channel are studied. An outer bound utilizing the capacity region of the corresponding broadcast channel is obtained. Two achievable regions obtained previously are compared, and a region including both is introduced by using frequency division multiplexing.