Search

This article presents a novel method for establishing an information theoretically secure encryption key over wireless channels. It exploits the fact that data transmission over wireless links is accompanied by packet error, while noise terms, and thereby the error events observed by two separate receivers are independent of each other. A number of data packets, with random data, are transmitted from a first legitimate node, say Alice, to a second legitimate node, say Bob. Bob identifies all packets that are received error-free in the first transmission attempt and sends their indices to Alice over a public channel. Then, both Alice and Bob mix the contents of identified packets, e.g., using a hash function, and thereby derive an identical encryption key. Since error events from Alice to Bob is independent of error events from Alice to Eve, the chances that Eve has successfully received all packets used in key generation error-free diminishes as the number of packet increases. In many wireless standards, the first stage in error detection and Automatic Repeat Request (ARQ) is deployed at the PHY/MAC (Physical Layer/Medium Access Control) layer. In such setups, the first re-transmission is manged by the PHY/MAC layer without informing higher layers. This makes it impossible to directly access the information related to packet errors through high-level programming interfaces available to an end-user. A method is presented for determining packets received error-free in first transmission attempts through high-level programming. Examples are presented in conjunction with an LTE cellular network.

This article bridges the gap between two topics used in sharing an encryption key: (i) Key Consolidation, i.e., extracting two identical strings of bits from two information sources with similarities (common randomness). (ii) Quantum-safe Key Encapsulation by incorporating randomness in Public/Private Key pairs. In the context of Key Consolidation, the proposed scheme adds to the complexity Eve faces in extracting useful data from leaked information. In this context, it is applied to the method proposed in [1] for establishing common randomness from round-trip travel times in a packet data network. The proposed method allows adapting the secrecy level to the amount of similarity in common randomness. It can even encapsulate a Quantum-safe encryption key in the extreme case that no common randomness is available. In the latter case, it is shown that the proposed scheme offers improvements with respect to the McEliece cryptosystem which currently forms the foundation for Quantum safe key encapsulation. [1] A. K. Khandani, "Looping for Encryption Key Generation Over the Internet: A New Frontier in Physical Layer Security," 2023 Biennial Symposium on Communications (BSC), Montreal, QC, Canada, 2023, pp. 59-64

This work presents some novel techniques to enhance an encryption scheme motivated by classical McEliece cryptosystem. Contributions include: (1) using masking matrices to hide sensitive data, (2) allowing both legitimate parties to incorporate randomness in the public key without sharing any additional public information, (3) using concatenation of a repetition code for error correction, permitting key recovery with a negligible decoding complexity, (4) making attacks more difficult by increasing the complexity in verifying a given key candidate has resulted in the actual key, (5) introducing memory in the error sequence such that: (i) error vector is composed of a random number of erroneous bits, (ii) errors can be all corrected when used in conjunction with concatenation of a repetition code of length 3. Proposed techniques allow generating significantly larger keys, at the same time, with a much lower complexity, as compared to known post-quantum key generation techniques relying on randomization.

The idea of Media-based Modulation (MBM) is to embed information in the variations of the transmission media (channel states). Using an RF closure with $w$ RF walls, MBM creates a set of $2^w$ select-able states for the end-to-end channel. Each state represents an index of an MBM constellation point. In each state, the wave (tone) emanating from the transmit antenna experiences many pseudo-random back-and-forth reflections within the RF closure. The RF signal, upon finally leaving the RF closure, further propagates in the rich scattering environment to reach the receiver. This results in an independent complex channel gain to each receive antenna. As a result, coordinates of different MBM constellation points (vectors of channel gains formed over received antennas) will be independent of each other. This is unlike legacy transmission schemes where a fixed constellation structure used at the transmitter will be multiplied by a fixed, but random, channel gain. Due to this independence property, MBM offers several advantages vs. legacy systems, including "additivity of information over multiple receive antennas (regardless of the number of transmit antennas)", and "inherent diversity over a static fading channel". This work studies the Diversity-Multiplexing Trade-off of an MBM constellation. Analytical expressions are provided that demonstrate the advantages of MBM vs. legacy systems. In particular, it is shown that a $1\times N_r$ SIMO-MBM constellation equipped with an MDS code (even with a relatively small code length) significantly outperforms an $N_r\times N_r$ legacy MIMO.

This article shows that achieving capacity region of a 2-users weak Gaussian Interference Channel (GIC) is equivalent to enlarging the core in a nested set of Polymatroids (each equivalent to capacity region of a multiple-access channel) through maximizing a minimum rate, then projecting along its orthogonal span and continuing recursively. This formulation relies on defining dummy private messages to capture the effect of interference in GIC. It follows that relying on independent Gaussian random code-books is optimum, and the corresponding solution corresponds to achieving the boundary in HK constraints., Comment: 20 pages, 4 figures

This article shows that the set of HK constraints correspond to projecting the intersection of two multiple access channels on its sup-spaces. A key property of HK constraints is that the private message of user 1 (or of user 2) is the last layer in superposition coding for the MAC formed at receiver 2 (or at receiver 1) and will be treated as noise in the decoding operations at receiver 2 (or at receiver 1). This property is used in this article to show that, in a HK rate region based on an additive Gaussian noise model, Gaussian distribution is optimum for enlarging the region. It is known that the HK rate region is achievable in an interference channel. On the other hand, reference [Khandani-arXiv:2011.12981] presents a method for code-book construction in a 2-users weak GIC, using Gaussian inputs, based on covering the boundary of the capacity region in infinitesimal steps. The region constructed in [Khandani-arXiv:2011.12981] coincides with the intersection of the same two multiple access channels that surface in the HK rate region. Reference [Khandani-arXiv:2011.12981] also shows that, due to the aforementioned key property, 2-users GIC capacity region cannot extend beyond the HK rate region. This means, using Gaussian code-books, the HK rate region is optimally enlarged and the same Gaussian code-books achieve the capacity region of the 2-users GIC., Comment: 4 pages, 1 figure

Computing capacity of Gaussian Interference Channel (GIC) is complex since knowledge of input distributions is needed to find the mutual information terms in closed forms, which should be optimized over input distributions and associated resource allocation. The optimum solution may require dividing the available resources among several GIC (each called a "constituent region", hereafter) and apply time-sharing among them. The current article focuses on a single constituent region (meaning the constraints on resources are all satisfied with equality) for a 2-users weak GIC. It is shown that, by relying on a different, intuitively straightforward, interpretation of the underlying optimization problem, one can determine the encoding/decoding strategies in the process of computing the optimum solution. This is based on gradually moving along the boundary of the capacity region in infinitesimal steps, where the solution for the end point in each step is optimized relying on the solution at the step's starting point. This approach enables proving Gaussian distribution is optimum over the entire boundary, and also allows finding simple closed form solutions describing different parts of the capacity region. The solution for each constituent 2-users GIC coincides with the optimum solution to the Han Kobayashi (HK) system of constraints with i.i.d. (scalar) Gaussian inputs. Although the article is focused on 2-users weak GIC, the proof for optimality of Gaussian distribution is independent of the values of cross gains, and thereby is universally applicable to strong, mixed and Z interference channels, as well as to GIC with more than two users. In addition, the procedure for the construction of boundary is applicable for arbitrary cross gain values, by re-deriving various conditions that have been established assuming cross gains being less than one., Comment: 65 pages, 27 figures

The Interference Channels (ICs) represent fundamental building blocks of wireless communication networks. Despite considerable progress in network information theory, available capacity results for ICs, specifically those with more than two users, are still very limited. One of the main difficulties in the analysis of these networks is how to establish useful capacity outer bounds for them. In this paper, novel techniques requiring subtle sequential application of Csiszar-Korner identity are developed to establish efficient single-letter outer bounds on the sum-rate capacity of interference networks. By using the outer bounds, a full characterization of the sum-rate capacity is then derived for various multi-user ICs under specific conditions. Our capacity results hold for both discrete and Gaussian networks., Comment: 18 pages. arXiv admin note: text overlap with arXiv:1207.3040

Quantum key distribution (QKD) has the potential to improve communications security by offering cryptographic keys whose security relies on the fundamental properties of quantum physics. The use of a trusted quantum receiver on an orbiting satellite is the most practical near-term solution to the challenge of achieving long-distance (global-scale) QKD, currently limited to a few hundred kilometers on the ground. This scenario presents unique challenges, such as high photon losses and restricted classical data transmission and processing power due to the limitations of a typical satellite platform. Here we demonstrate the feasibility of such a system by implementing a QKD protocol, with optical transmission and full post-processing, in the high-loss regime using minimized computing hardware at the receiver. Employing weak coherent pulses with decoy states, we demonstrate the production of secure key bits at up to 56.5 dB of photon loss. We further illustrate the feasibility of a satellite uplink by generating secure key while experimentally emulating the varying channel losses predicted for realistic low-Earth-orbit satellite passes at 600 km altitude. With a 76 MHz source and including finite-size analysis, we extract 3374 bits of secure key from the best pass. We also illustrate the potential benefit of combining multiple passes together: while one suboptimal "upper-quartile" pass produces no finite-sized key with our source, the combination of three such passes allows us to extract 165 bits of secure key. Alternatively, we find that by increasing the signal rate to 300 MHz it would be possible to extract 21570 bits of secure finite-sized key in just a single upper-quartile pass., Comment: 12 pages, 7 figures, 2 tables

In this paper, capacity bounds for the two-user Interference Channel (IC) with cooperative receivers via conferencing links of finite capacities is investigated. The capacity results known for this communication scenario are limited to a very few special cases of the one-sided IC. One of the major challenges in analyzing such cooperative networks is how to establish efficient capacity outer bounds for them. In this paper, by applying new techniques, novel capacity outer bounds are presented for the ICs with conferencing users. Using the outer bounds, several new capacity results are proved for interesting channels with unidirectional cooperation in strong and mixed interference regimes. A fact is that the conferencing link (between receivers) may be utilized to provide one receiver with information about its corresponding signal or its non-corresponding signal (interference signal). As a remarkable consequence, it is demonstrated that both strategies can be helpful to achieve the capacity of the channel. Finally, for the case of Gaussian IC, it is mathematically shown that our outer bound is strictly tighter than the previous one derived by Wang and Tse., Comment: 13 pages

The idea of media-based modulation (MBM) is to embed information in the channel states via intentional perturbations of the transmission media. This article covers a broad range of topics regarding MBM, expanding on its benefits and reviewing relevant challenges, alluding to potential future research directions. The article starts by arguing how MBM differs from a source-based modulation; we highlight the key shortcomings in a legacy multiple-input multiple-output (MIMO) system that MBM sets out to address, including the issue of deep fades and MIMO diversity-multiplexing trade-off. The article further explains how MBM works in harmony with other index modulations and improves upon them by providing similar advantages with a more compact transmitter. Numerical results (simulation and analytical) are provided to support the claims on the discussed benefits. The highlights of numerical results include: 1) outage comparison with legacy MIMO systems; 2) comparisons with other state-of-the-art modulation schemes such as generalized spatial modulation; and 3) performance example of sending 32 bits of information in a single transmission with an excellent symbol error rate of $\mathsf{SER} \simeq 10^{-5}$ at \say{energy per bit to noise power spectral density ratio} of $\mathsf{E_b/N_0} \simeq -3.5$ dB. The article continues with methods to address the issues of receiver training and decoding for large constellation sets. A number of other research questions, such as pulse shaping to limit spectral growth due to the time-varying nature of MBM and the effect of forward error correcting codes on MBM diversity order are discussed. Finally, an RF transceiver structure is presented to generate independent propagation paths for embedding information. Fabrication and testing of the transceiver structure show close agreement between simulation and measurement., Comment: The current update includes significant revisions to previous versions and new developments

The problem of dual-hop transmission from a source to a destination via two parallel full-duplex relays in block Rayleigh fading environment is investigated. All nodes in the network are assumed to be oblivious to their forward channel gains; however, they have perfect information about their backward channel gains. The focus of this paper is on simple, efficient, and practical relaying schemes to increase the expected-rate at the destination. For this purpose, various combinations of relaying protocols and the broadcast approach (multi-layer coding) are proposed. For the decode-forward (DF) relaying, the maximum finite-layer expected-rate as well as two upper-bounds on the continuous-layer expected-rate are obtained. The main feature of the proposed DF scheme is that the layers being decoded at both relays are added coherently at the destination although each relay has no information about the number of layers being successfully decoded by the other relay. It is proved that the optimal coding scheme is transmitting uncorrelated signals via the relays. Next, the maximum expected-rate of ON/OFF based amplify-forward (AF) relaying is analytically derived. For further performance improvement, a hybrid decode-amplify-forward (DAF) relaying strategy, adopting the broadcast approach at the source and relays, is proposed and its maximum throughput and maximum finite-layer expected-rate are presented. Moreover, the maximum throughput and maximum expected-rate in the compress-forward (CF) relaying adopting the broadcast approach, using optimal quantizers and Wyner-Ziv compression at the relays, are fully derived. All theoretical results are illustrated by numerical simulations. As it turns out from the results, when the ratio of the relay power to the source power is high, the CF relaying outperforms DAF (and hence outperforms both DF and AF relaying); otherwise, DAF scheme is superior., Comment: 30 pages, 6 figures, Submitted to Trans. on Inform. Theory

The point-to-point multiple-antenna channel is investigated in uncorrelated block fading environment with Rayleigh distribution. The maximum throughput and maximum expected-rate of this channel are derived under the assumption that the transmitter is oblivious to the channel state information (CSI), however, the receiver has perfect CSI. First, we prove that in multiple-input single-output (MISO) channels, the optimum transmission strategy maximizing the throughput is to use all available antennas and perform equal power allocation with uncorrelated signals. Furthermore, to increase the expected-rate, multi-layer coding is applied. Analogously, we establish that sending uncorrelated signals and performing equal power allocation across all available antennas at each layer is optimum. A closed form expression for the maximum continuous-layer expected-rate of MISO channels is also obtained. Moreover, we investigate multiple-input multiple-output (MIMO) channels, and formulate the maximum throughput in the asymptotically low and high SNR regimes and also asymptotically large number of transmit or receive antennas by obtaining the optimum transmit covariance matrix. Finally, a distributed antenna system, wherein two single-antenna transmitters want to transmit a common message to a single-antenna receiver, is considered. It is shown that this system has the same outage probability and hence, throughput and expected-rate, as a point-to-point $2\times 1$ MISO channel., Comment: 33 pages; 2 figures

A two-user Gaussian Z-Interference Channel (GZIC) is considered, in which encoders are connected through noiseless links with finite capacities. In this setting, prior to each transmission block the encoders communicate with each other over the cooperative links. The capacity region and the sum-capacity of the channel are characterized within 1.71 bits per user and 2 bits in total, respectively. It is also established that properly sharing the total limited cooperation capacity between the cooperative links may enhance the achievable region, even when compared to the case of unidirectional transmitter cooperation with infinite cooperation capacity. To obtain the results, genie-aided upper bounds on the sum-capacity and cut-set bounds on the individual rates are compared with the achievable rate region. In the interference-limited regime, the achievable scheme enjoys a simple type of Han-Kobayashi signaling, together with the zero-forcing, and basic relaying techniques. In the noise-limited regime, it is shown that treating interference as noise achieves the capacity region up to a single bit per user., Comment: 25 pages, 6 figures, submitted to IEEE Transactions on Information Theory

A $K$-user secure Gaussian Multiple-Access-Channel (MAC) with an external eavesdropper is considered in this paper. An achievable rate region is established for the secure discrete memoryless MAC. The secrecy sum capacity of the degraded Gaussian MIMO MAC is proven using Gaussian codebooks. For the non-degraded Gaussian MIMO MAC, an algorithm inspired by interference alignment technique is proposed to achieve the largest possible total Secure-Degrees-of-Freedom (S-DoF). When all the terminals are equipped with a single antenna, Gaussian codebooks have shown to be inefficient in providing a positive S-DoF. Instead, a novel secure coding scheme is proposed to achieve a positive S-DoF in the single antenna MAC. This scheme converts the single-antenna system into a multiple-dimension system with fractional dimensions. The achievability scheme is based on the alignment of signals into a small sub-space at the eavesdropper, and the simultaneous separation of the signals at the intended receiver. Tools from the field of Diophantine Approximation in number theory are used to analyze the probability of error in the coding scheme. It is proven that the total S-DoF of $\frac{K-1}{K}$ can be achieved for almost all channel gains. For the other channel gains, a multi-layer coding scheme is proposed to achieve a positive S-DoF. As a function of channel gains, therefore, the achievable S-DoF is discontinued., Comment: The conference version of this work has been submitted to ISIT 2010

This paper addresses a unified approach towards communication in decentralized wireless networks of separate transmitter-receiver pairs. In general, users are unaware of each other's codebooks and there is no central controller to assign the resources in the network to the users. A randomized signaling scheme is introduced in which each user locally spreads its Gaussian signal along a randomly generated spreading code comprised of a sequence of nonzero elements over a certain alphabet. Along with spreading, each transmitter also masks its output independently from transmission to transmission. Using a conditional version of entropy power inequality and a key lemma on the differential entropy of mixed Gaussian random vectors, achievable rates are developed for the users. It is seen that as the number of users increases, the achievable Sum Multiplexing Gain of the network approaches that of a centralized orthogonal scheme where multiuser interference is completely avoided. An interesting observation is that in general the elements of a spreading code are not equiprobable over the underlying alphabet. Finally, using the recently developed extremal inequality of Liu-Viswanath, we present an optimality result showing that transmission of Gaussian signals via spreading and masking yields higher achievable rates than the maximum achievable rate attained by applying masking only.

This paper addresses an interference channel consisting of $\mathbf{n}$ active users sharing $u$ frequency sub-bands. Users are asynchronous meaning there exists a mutual delay between their transmitted codes. A stationary model for interference is considered by assuming the starting point of an interferer's data is uniformly distributed along the codeword of any user. This model is not ergodic, however, we show that the noise plus interference process satisfies an Asymptotic Equipartition Property (AEP) under certain conditions. This enables us to define achievable rates in the conventional Shannon sense. The spectrum is divided to private and common bands. Each user occupies its assigned private band and the common band upon activation. In a scenario where all transmitters are unaware of the number of active users and the channel gains, the optimum spectrum assignment is obtained such that the so-called outage capacity per user is maximized. If $\Pr\{\mathbf{n}>2\}>0$, all users follow a locally Randomized On-Off signaling scheme on the common band where each transmitter quits transmitting its Gaussian signals independently from transmission to transmission. Achievable rates are developed using a conditional version of Entropy Power Inequality (EPI) and an upper bound on the differential entropy of a mixed Gaussian random variable. Thereafter, the activation probability on each transmission slot together with the spectrum assignment are designed resulting in the largest outage capacity., Comment: This paperi is withdrawn by the author due to a crucial technicality regarding ergodicity. It will be soon corrected and replaced by a draft called "Randomized On-Off Signaling n Asynchronous Wireless Networks"

A new achievability rate region for the secure discrete memoryless Multiple-Access-Channel (MAC) is presented. Thereafter, a novel secure coding scheme is proposed to achieve a positive Secure Degrees-of-Freedom (S-DoF) in the single-antenna MAC. This scheme converts the single-antenna system into a multiple-dimension system with fractional dimensions. The achievability scheme is based on the alignment of signals into a small sub-space at the eavesdropper, and the simultaneous separation of the signals at the intended receiver. Tools from the field of Diophantine Approximation in number theory are used to analyze the probability of error in the coding scheme., Comment: 5 Pages, Submitted to ISIT 2010

This paper addresses an interference channel consisting of $\mathbf{n}$ active users sharing $u$ frequency sub-bands. Users are asynchronous meaning there exists a mutual delay between their transmitted codes. A stationary model for interference is considered by assuming the starting point of an interferer's data is uniformly distributed along the codeword of any user. The spectrum is divided to private and common bands each containing $v_{\mathrm{p}}$ and $v_{\mathrm{c}}$ frequency sub-bands respectively. We consider a scenario where all transmitters are unaware of the number of active users and the channel gains. The optimum $v_{\mathrm{p}}$ and $v_{\mathrm{c}}$ are obtained such that the so-called outage capacity per user is maximized. If $\Pr\{\mathbf{n}\leq 2\}=1$, upper and lower bounds on the mutual information between the input and output of the channel for each user are derived using a genie-aided technique. The proposed bounds meet each other as the code length grows to infinity yielding a closed expression for the achievable rates. If $\Pr\{\mathbf{n}>2\}>0$, all users follow a locally Randomized On-Off signaling scheme on the common band where each transmitter quits transmitting its Gaussian signals independently from transmission to transmission. Using a conditional version of Entropy Power Inequality (EPI) and an upper bound on the differential entropy of a mixed Gaussian random variable, lower bounds on the achievable rates of users are developed. Thereafter, the activation probability on each transmission slot is designed resulting in the largest outage capacity., Comment: This paper is withdrawn due to some technicality regarding ergodicity. The corrected version will be submitted under the title "Randomized On-Off signaling in Asynchronous Wireless Networks"

This paper studies the general multi-antenna multiple-relay network. Every two nodes of the network are either connected together through a Rayleigh fading channel or disconnected. We study the ergodic capacity of the network in the high SNR regime. We prove that the traditional amplify-forward relaying achieves the maximum multiplexing gain of the network. Furthermore, we show that the maximum multiplexing gain of the network is equal to the minimum vertex cut-set of the underlying graph of the network, which can be computed in polynomial time in terms of the number of network nodes. Finally, the argument is extended to the multicast and multi-access scenarios., Comment: Submitted to the IEEE transaction on Information Theory in Dec. 2009

This paper investigates the benefits of Amplify-and-Forward (AF) relaying in the setup of multi-antenna wireless networks. The concept of Random Sequential (RS) relaying is previously introduced in the literature and showed that it achieves the maximum diversity gain in a general multi-antenna network. Here, we show that random unitary matrix multiplication at the relay nodes empowers the RS scheme to achieve a better Diversity-Multiplexing Tradeoff (DMT) as compared to the traditional AF relaying. First, we study the case of a multi-antenna full-duplex single-relay two-hop network, for which we show that the RS achieves the optimum DMT. Applying this result, we derive a new achievable DMT for the case of multi-antenna half-duplex parallel relay network. Interestingly, it turns out that the DMT of the RS scheme is optimum for the case of multi-antenna two parallel non-interfering half-duplex relays. Next, we show that random unitary matrix multiplication also improves the DMT of the Non-Orthogonal AF relaying scheme in the case of a multi-antenna single relay channel. Finally, we study the general case of multi-antenna full-duplex relay networks and derive a new lower-bound on its DMT using the RS scheme., Comment: Submitted to the IEEE transaction on Information Theory in Dec. 2009

We address a decentralized wireless communication network with a fixed number $u$ of frequency sub-bands to be shared among $N$ transmitter-receiver pairs. It is assumed that the number of users $N$ is a random variable with a given distribution and the channel gains are quasi-static Rayleigh fading. The transmitters are assumed to be unaware of the number of active users in the network as well as the channel gains and not capable of detecting the presence of other users in a given frequency sub-band. Moreover, the users are unaware of each other's codebooks and hence, no multiuser detection is possible. We consider a randomized Frequency Hopping (FH) scheme in which each transmitter randomly hops over a subset of the $u$ sub-bands from transmission to transmission. Developing a new upper bound on the differential entropy of a mixed Gaussian random vector and using entropy power inequality, we offer a series of lower bounds on the achievable rate of each user. Thereafter, we obtain lower bounds on the maximum transmission rate per user to ensure a specified outage probability at a given Signal-to-Noise Ratio (SNR) level. We demonstrate that the so-called outage capacity can be considerably higher in the FH scheme than in the Frequency Division (FD) scenario for reasonable distributions on the number of active users. This guarantees a higher spectral efficiency in FH compared to FD.

In this paper, we consider a decentralized wireless communication network with a fixed number $u$ of frequency sub-bands to be shared among $N$ transmitter-receiver pairs. It is assumed that the number of active users is a random variable with a given probability mass function. Moreover, users are unaware of each other's codebooks and hence, no multiuser detection is possible. We propose a randomized Frequency Hopping (FH) scheme in which each transmitter randomly hops over a subset of $u$ sub-bands from transmission to transmission. We derive lower and upper bounds on the mutual information of each user and demonstrate that, for large Signal-to-Noise Ratio (SNR) values, the two bounds coincide. This observation enables us to compute the sum multiplexing gain of the system and obtain the optimum hopping strategy for maximizing this quantity. We compare the performance of the FH system with that of the Frequency Division (FD) system in terms of several performance measures and show that (depending on the probability mass function of the number of active users) the FH system can offer a significant improvement implying a more efficient usage of the spectrum.

In this paper, a dual-hop communication system composed of a source S and a destination D connected through two non-interfering half-duplex relays, R1 and R2, is considered. In the literature of Information Theory, this configuration is known as the diamond channel. In this setup, four transmission modes are present, namely: 1) S transmits, and R1 and R2 listen (broadcast mode), 2) S transmits, R1 listens, and simultaneously, R2 transmits and D listens. 3) S transmits, R2 listens, and simultaneously, R1 transmits and D listens. 4) R1, R2 transmit, and D listens (multiple-access mode). Assuming a constant power constraint for all transmitters, a parameter $\Delta$ is defined, which captures some important features of the channel. It is proven that for $\Delta$=0 the capacity of the channel can be attained by successive relaying, i.e, using modes 2 and 3 defined above in a successive manner. This strategy may have an infinite gap from the capacity of the channel when $\Delta\neq$0. To achieve rates as close as 0.71 bits to the capacity, it is shown that the cases of $\Delta$>0 and $\Delta$<0 should be treated differently. Using new upper bounds based on the dual problem of the linear program associated with the cut-set bounds, it is proven that the successive relaying strategy needs to be enhanced by an additional broadcast mode (mode 1), or multiple access mode (mode 4), for the cases of $\Delta$<0 and $\Delta$>0, respectively. Furthermore, it is established that under average power constraints the aforementioned strategies achieve rates as close as 3.6 bits to the capacity of the channel., Comment: 25 pages, 2 figures, submitted to IEEE Transactions on Information Theory

This paper deals with the delay-throughput analysis of a single-hop wireless network with $n$ transmitter/receiver pairs. All channels are assumed to be block Rayleigh fading with shadowing, described by parameters $(\alpha,\varpi)$, where $\alpha$ denotes the probability of shadowing and $\varpi$ represents the average cross-link gains. The analysis relies on the distributed on-off power allocation strategy (i.e., links with a direct channel gain above a certain threshold transmit at full power and the rest remain silent) for the deterministic and stochastic packet arrival processes. It is also assumed that each transmitter has a buffer size of one packet and dropping occurs once a packet arrives in the buffer while the previous packet has not been served. In the first part of the paper, we define a new notion of performance in the network, called effective throughput, which captures the effect of arrival process in the network throughput, and maximize it for different cases of packet arrival process. It is proved that the effective throughput of the network asymptotically scales as $\frac{\log n}{\hat{\alpha}}$, with $\hat{\alpha} \triangleq \alpha \varpi$, regardless of the packet arrival process. In the second part of the paper, we present the delay characteristics of the underlying network in terms of the packet dropping probability. We derive the sufficient conditions in the asymptotic case of $n \to \infty$ such that the packet dropping probability tend to zero, while achieving the maximum effective throughput of the network. Finally, we study the trade-off between the effective throughput, delay, and packet dropping probability of the network for different packet arrival processes., Comment: Submitted to IEEE Transactions on Information Theory (34 pages)

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages to two receivers, while a wire-tapper also receives the transmitted signal. This model is motivated by wireless communications, where individual secure messages are broadcast over open media and can be received by any illegitimate receiver. The secrecy level is measured by the equivocation rate at the eavesdropper. We first study the general (non-degraded) broadcast channel with an eavesdropper. We present an inner bound on the secrecy capacity region for this model. This inner bound is based on a combination of random binning, and the Gelfand-Pinsker binning. We further study the situation in which the channels are degraded. For the degraded broadcast channel with an eavesdropper, we present the secrecy capacity region. Our achievable coding scheme is based on Covers superposition scheme and random binning. We refer to this scheme as the Secret Superposition Scheme. Our converse proof is based on a combination of the converse proof of the conventional degraded broadcast channel and Csiszar Lemma. We then assume that the channels are Additive White Gaussian Noise (AWGN) and show that the Secret Superposition Scheme with Gaussian codebook is optimal. The converse proof is based on Costas entropy power inequality. Finally, we use a broadcast strategy for the slowly fading wire-tap channel when only the eavesdroppers channel is fixed and known at the transmitter. We derive the optimum power allocation for the coding layers, which maximizes the total average rate., Comment: 18 Pages, Submitted to IEEE Transaction on Information Theory (Revised Version)

A two-user symmetric Gaussian Interference Channel (IC) is considered in which a noiseless unidirectional link connects one encoder to the other. Having a constant capacity, the additional link provides partial cooperation between the encoders. It is shown that the available cooperation can dramatically increase the sum-capacity of the channel. This fact is proved based on comparison of proposed lower and upper bounds on the sum-capacity. Partitioning the data into three independent messages, namely private, common, and cooperative ones, the transmission strategy used to obtain the lower bound enjoys a simple type of Han-Kobayashi scheme together with a cooperative communication scheme. A Genie-aided upper bound is developed which incorporates the capacity of the cooperative link. Other upper bounds are based on the sum-capacity of the Cognitive Radio Channel and cut-set bounds. For the strong interference regime, the achievablity scheme is simplified to employ common and/or cooperative messages but not the private one. Through a careful analysis it is shown that the gap between these bounds is at most one and two bits per real dimension for strong and weak interference regimes, respectively. Moreover, the Generalized Degrees-of-Freedom of the channel is characterized.

A novel coding scheme applicable in networks with single antenna nodes is proposed. This scheme converts a single antenna system to an equivalent Multiple Input Multiple Output (MIMO) system with fractional dimensions. Interference can be aligned along these dimensions and higher Multiplexing gains can be achieved. Tools from the field of Diophantine approximation in number theory are used to show that the proposed coding scheme in fact mimics the traditional schemes used in MIMO systems where each data stream is sent along a direction and alignment happens when several streams arrive at the same direction. Two types of constellation are proposed for the encoding part, namely the single layer constellation and the multi-layer constellation. Using the single layer constellation, the coding scheme is applied to the two-user $X$ channel and the three-user Gaussian Interference Channel (GIC). In case of the two-user $X$ channel, it is proved that the total Degrees-of-Freedom (DOF), i.e. 4/3, of the channel is achievable almost surely. This is the first example in which it is shown that a time invariant single antenna system does not fall short of achieving its total DOF. Using the multi-layer constellation, the coding scheme is applied to the symmetric three-user GIC. Achievable DOFs are derived for all channel gains. As a function of the channel gain, it is observed that the DOF is everywhere discontinuous., Comment: Submitted to IEEE Trans. on Information Theory

In this paper, a two-hop network in which information is transmitted from a source via a relay to a destination is considered. It is assumed that the channels are static fading with additive white Gaussian noise. All nodes are equipped with a single antenna and the Channel State Information (CSI) of each hop is not available at the corresponding transmitter. The relay is assumed to be simple, i.e., not capable of data buffering over multiple coding blocks, water-filling over time, or rescheduling. A commonly used design criterion in such configurations is the maximization of the average received rate at the destination. We show that using a continuum of multilevel codes at both the source and the relay, in conjunction with decode and forward strategy at the relay, performs optimum in this setup. In addition, we present a scheme to optimally allocate the available source and relay powers to different levels of their corresponding codes. The performance of this scheme is evaluated assuming Rayleigh fading and compared with the previously known strategies., Comment: 21 pages, 7 figures, Submitted to IEEE Transactions on Information Theory on April 6, 2009

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers via a Gaussian MIMO broadcast channel. A wire-tapper also receives the transmitted signal via another MIMO channel. It is assumed that the channels are degraded and the wire-tapper has the worst channel. We establish the capacity region of this scenario. Our achievability scheme is a combination of the superposition of Gaussian codes and randomization within the layers which we will refer to as Secret Superposition Coding. For the outerbound, we use the notion of enhanced channel to show that the secret superposition of Gaussian codes is optimal. It is shown that we only need to enhance the channels of the legitimate receivers, and the channel of the eavesdropper remains unchanged., Comment: 5 Pages, 1 Figure, To be Presented at the ISIT 2009

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers via a Gaussian MIMO broadcast channel. A wire-tapper also receives the transmitted signal via another MIMO channel. First we assumed that the channels are degraded and the wire-tapper has the worst channel. We establish the capacity region of this scenario. Our achievability scheme is a combination of the superposition of Gaussian codes and randomization within the layers which we will refer to as Secret Superposition Coding. For the outerbound, we use the notion of enhanced channel to show that the secret superposition of Gaussian codes is optimal. We show that we only need to enhance the channels of the legitimate receivers, and the channel of the eavesdropper remains unchanged. Then we extend the result of the degraded case to non-degraded case. We show that the secret superposition of Gaussian codes along with successive decoding cannot work when the channels are not degraded. we develop a Secret Dirty Paper Coding (SDPC) scheme and show that SDPC is optimal for this channel. Finally, we investigate practical characterizations for the specific scenario in which the transmitter and the eavesdropper have multiple antennas, while both intended receivers have a single antenna. We characterize the secrecy capacity region in terms of generalized eigenvalues of the receivers channel and the eavesdropper channel. We refer to this configuration as the MISOME case. In high SNR we show that the capacity region is a convex closure of two rectangular regions., Comment: 23 pages, 2 figures

Schein and Gallager introduced the Gaussian parallel relay channel in 2000. They proposed the Amplify-and-Forward (AF) and the Decode-and-Forward (DF) strategies for this channel. For a long time, the best known achievable rate for this channel was based on the AF and DF with time sharing (AF-DF). Recently, a Rematch-and-Forward (RF) scheme for the scenario in which different amounts of bandwidth can be assigned to the first and second hops were proposed. In this paper, we propose a \emph{Combined Amplify-and-Decode Forward (CADF)} scheme for the Gaussian parallel relay channel. We prove that the CADF scheme always gives a better achievable rate compared to the RF scheme, when there is a bandwidth mismatch between the first hop and the second hop. Furthermore, for the equal bandwidth case (Schein's setup), we show that the time sharing between the CADF and the DF schemes (CADF-DF) leads to a better achievable rate compared to the time sharing between the RF and the DF schemes (RF-DF) as well as the AF-DF., Comment: 22 pages, 9 figures, Submitted to Transaction on Information Theory

A non-regenerative dual-hop wireless system based on a distributed space-time coding strategy is considered. It is assumed that each relay retransmits an appropriately scaled space-time coded version of its received signal. The main goal of this paper is to investigate a power allocation strategy in relay stations, which is based on minimizing the outage probability. In the high signal-to-noise ratio regime for the relay-destination link, it is shown that a threshold-based power allocation scheme (i.e., the relay remains silent if its channel gain with the source is less than a prespecified threshold) is optimum. Monte-Carlo simulations show that the derived on-off power allocation scheme performs close to optimum for finite signal-to-noise ratio values. Numerical results demonstrate a dramatic improvement in system performance as compared to the case that the relay stations forward their received signals with full power. In addition, a hybrid amplify-and-forward/detect-and-forward scheme is proposed for the case that the quality of the source-relay link is good. Finally, the robustness of the proposed scheme in the presence of channel estimation errors is numerically evaluated., Comment: submitted to IEEE Transactions on Wireless Communications (24 pages)

This study investigates the problem of communication for a network composed of two half-duplex parallel relays with additive white Gaussian noise. Two protocols, i.e., \emph{Simultaneous} and \emph{Successive} relaying, associated with two possible relay orderings are proposed. The simultaneous relaying protocol is based on \emph{Dynamic Decode and Forward (DDF)} scheme. For the successive relaying protocol: (i) a \emph{Non-Cooperative} scheme based on the \emph{Dirty Paper Coding (DPC)}, and (ii) a \emph{Cooperative} scheme based on the \emph{Block Markov Encoding (BME)} are considered. Furthermore, the composite scheme of employing BME at one relay and DPC at another always achieves a better rate when compared to the \emph{Cooperative} scheme. A \emph{"Simultaneous-Successive Relaying based on Dirty paper coding scheme" (SSRD)} is also proposed. The optimum ordering of the relays and hence the capacity of the half-duplex Gaussian parallel relay channel in the low and high signal-to-noise ratio (SNR) scenarios is derived. In the low SNR scenario, it is revealed that under certain conditions for the channel coefficients, the ratio of the achievable rate of the simultaneous relaying based on DDF to the cut-set bound tends to be 1. On the other hand, as SNR goes to infinity, it is proved that successive relaying, based on the DPC, asymptotically achieves the capacity of the network., Comment: 37 pages, 10 figures, submitted to IEEE transaction on Information Theory in October 2008

A distributed single-hop wireless network with $K$ links is considered, where the links are partitioned into a fixed number ($M$) of clusters each operating in a subchannel with bandwidth $\frac{W}{M}$. The subchannels are assumed to be orthogonal to each other. A general shadow-fading model, described by parameters $(\alpha,\varpi)$, is considered where $\alpha$ denotes the probability of shadowing and $\varpi$ ($\varpi \leq 1$) represents the average cross-link gains. The main goal of this paper is to find the maximum network throughput in the asymptotic regime of $K \to \infty$, which is achieved by: i) proposing a distributed and non-iterative power allocation strategy, where the objective of each user is to maximize its best estimate (based on its local information, i.e., direct channel gain) of the average network throughput, and ii) choosing the optimum value for $M$. In the first part of the paper, the network hroughput is defined as the \textit{average sum-rate} of the network, which is shown to scale as $\Theta (\log K)$. Moreover, it is proved that in the strong interference scenario, the optimum power allocation strategy for each user is a threshold-based on-off scheme. In the second part, the network throughput is defined as the \textit{guaranteed sum-rate}, when the outage probability approaches zero. In this scenario, it is demonstrated that the on-off power allocation scheme maximizes the throughput, which scales as $\frac{W}{\alpha \varpi} \log K$. Moreover, the optimum spectrum sharing for maximizing the average sum-rate and the guaranteed sum-rate is achieved at M=1., Comment: Submitted to IEEE Transactions on Information Theory

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers, while a wire-tapper also receives the transmitted signal. This model is motivated by wireless communications, where individual secure messages are broadcast over open media and can be received by any illegitimate receiver. The secrecy level is measured by equivocation rate at the eavesdropper. We first study the general (non-degraded) broadcast channel with confidential messages. We present an inner bound on the secrecy capacity region for this model. The inner bound coding scheme is based on a combination of random binning and the Gelfand-Pinsker bining. This scheme matches the Marton's inner bound on the broadcast channel without confidentiality constraint. We further study the situation where the channels are degraded. For the degraded broadcast channel with confidential messages, we present the secrecy capacity region. Our achievable coding scheme is based on Cover's superposition scheme and random binning. We refer to this scheme as Secret Superposition Scheme. In this scheme, we show that randomization in the first layer increases the secrecy rate of the second layer. This capacity region matches the capacity region of the degraded broadcast channel without security constraint. It also matches the secrecy capacity for the conventional wire-tap channel. Our converse proof is based on a combination of the converse proof of the conventional degraded broadcast channel and Csiszar lemma. Finally, we assume that the channels are Additive White Gaussian Noise (AWGN) and show that secret superposition scheme with Gaussian codebook is optimal. The converse proof is based on the generalized entropy power inequality., Comment: 12 pages, 4 figures

The capacity of a time-varying block-memoryless channel in which the transmitter and the receiver have access to (possibly different) noisy causal channel side information (CSI) is obtained. It is shown that the capacity formula obtained in this correspondence reduces to the capacity formula reported in \cite{Gold07} for the special case where the transmitter CSI is a deterministic function of the receiver CSI., Comment: 8 pages, submitted to IEEE Transactions on Information Theory

An erasure channel with a fixed alphabet size $q$, where $q \gg 1$, is studied. It is proved that over any erasure channel (with or without memory), Maximum Distance Separable (MDS) codes achieve the minimum probability of error (assuming maximum likelihood decoding). Assuming a memoryless erasure channel, the error exponent of MDS codes are compared with that of random codes and linear random codes. It is shown that the envelopes of all these exponents are identical for rates above the critical rate. Noting the optimality of MDS codes, it is concluded that both random codes and linear random codes are exponentially optimal, whether the block sizes is larger or smaller than the alphabet size., Comment: 15 pages, 3 figures

The problem of maximizing the average rate in a multicast network subject to a coverage constraint (minimum quality of service) is studied. Assuming the channel state information is available only at the receiver side and single antenna nodes, the highest expected rate achievable by a random user in the network, called expected typical rate, is derived in two scenarios: hard coverage constraint and soft coverage constraint. In the first case, the coverage is expressed in terms of the outage probability, while in the second case, the expected rate should satisfy certain minimum requirement. It is shown that the optimum solution in both cases (achieving the highest expected typical rate for given coverage requirements) is achieved by an infinite layer superposition code for which the optimum power allocation among the different layers is derived. For the MISO case, a suboptimal coding scheme is proposed, which is shown to be asymptotically optimal, when the number of transmit antennas grows at least logarithmically with the number of users in the network., Comment: presented in ISIT2007, Nice, France, submitted to IEEE Trans. on Information Theory

In this paper, we consider the problem of robust joint source-channel coding over an additive white Gaussian noise channel. We propose a new scheme which achieves the optimal slope of the signal-to-distortion (SDR) curve (unlike the previously known coding schemes). Also, we propose a family of robust codes which together maintain a bounded gap with the optimum SDR curve (in terms of dB). To show the importance of this result, we drive some theoretical bounds on the asymptotic performance of delay-limited hybrid digital-analog (HDA) coding schemes. We show that, unlike the delay-unlimited case, for any family of delay-limited HDA codes, the asymptotic performance loss is unbounded (in terms of dB)., Comment: Submitted to IEEE Transactions on Information Theory

We consider a diamond-shaped dual-hop communication system consisting a source, two parallel half-duplex relays and a destination. In a single antenna configuration, it has been previously shown that a two-phase node-scheduling algorithm, along with the decode and forward strategy can achieve the capacity of the diamond channel for a certain symmetric channel gains [1]. In this paper, we obtain a more general condition for the optimality of the scheme in terms of power resources and channel gains. In particular, it is proved that if the product of the capacity of the simultaneously active links are equal in both transmission phases, the scheme achieves the capacity of the channel.

Path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. In this paper, \textit{Forward Error Correction} (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. Network paths are modeled as erasure Gilbert-Elliot channels. It is known that over any erasure channel, \textit{Maximum Distance Separable} (MDS) codes achieve the minimum probability of irrecoverable loss among all block codes of the same size. Based on the adopted model for the error behavior, we prove that the probability of irrecoverable loss for MDS codes decays exponentially for an asymptotically large number of paths. Then, optimal rate allocation problem is solved for the asymptotic case where the number of paths is large. Moreover, it is shown that in such asymptotically optimal rate allocation, each path is assigned a positive rate \textit{iff} its quality is above a certain threshold. The quality of a path is defined as the percentage of the time it spends in the bad state. Finally, using dynamic programming, a heuristic suboptimal algorithm with polynomial runtime is proposed for rate allocation over a finite number of paths. This algorithm converges to the asymptotically optimal rate allocation when the number of paths is large. The simulation results show that the proposed algorithm approximates the optimal rate allocation (found by exhaustive search) very closely for practical number of paths, and provides significant performance improvement compared to the alternative schemes of rate allocation., Comment: 44 pages, 15 eps files. University of Waterloo Technical Report

This paper studies the setup of a multiple-relay network in which $K$ half-duplex multiple-antenna relays assist in the transmission between a/several multiple-antenna transmitter(s) and a multiple-antenna receiver. Each two nodes are assumed to be either connected through a quasi-static Rayleigh fading channel, or disconnected. We propose a new scheme, which we call \textit{random sequential} (RS), based on the amplify-and-forward relaying. We prove that for general multiple-antenna multiple-relay networks, the proposed scheme achieves the maximum diversity gain. Furthermore, we derive diversity-multiplexing tradeoff (DMT) of the proposed RS scheme for general single-antenna multiple-relay networks. It is shown that for single-antenna two-hop multiple-access multiple-relay ($K>1$) networks (without direct link between the transmitter(s) and the receiver), the proposed RS scheme achieves the optimum DMT. However, for the case of multiple access single relay setup, we show that the RS scheme reduces to the naive amplify-and-forward relaying and is not optimum in terms of DMT, while the dynamic decode-and-forward scheme is shown to be optimum for this scenario., Comment: Submitted to IEEE Trans. on Information Theory, April 28 2008

The capacity region of the two-user Gaussian Interference Channel (IC) is studied. Three classes of channels are considered: weak, one-sided, and mixed Gaussian IC. For the weak Gaussian IC, a new outer bound on the capacity region is obtained that outperforms previously known outer bounds. The sum capacity for a certain range of channel parameters is derived. For this range, it is proved that using Gaussian codebooks and treating interference as noise is optimal. It is shown that when Gaussian codebooks are used, the full Han-Kobayashi achievable rate region can be obtained by using the naive Han-Kobayashi achievable scheme over three frequency bands (equivalently, three subspaces). For the one-sided Gaussian IC, an alternative proof for the Sato's outer bound is presented. We derive the full Han-Kobayashi achievable rate region when Gaussian codebooks are utilized. For the mixed Gaussian IC, a new outer bound is obtained that outperforms previously known outer bounds. For this case, the sum capacity for the entire range of channel parameters is derived. It is proved that the full Han-Kobayashi achievable rate region using Gaussian codebooks is equivalent to that of the one-sided Gaussian IC for a particular range of channel parameters., Comment: 35 pages, 14 figures, submitted to IEEE Trans. on Inf. Theory

We address single-user data transmission over a channel where the received signal incurs interference from a finite number of users (interfering users) that use single codebooks for transmitting their own messages. The receiver, however, is allowed to decode interfering users' messages. This means the signal transmitted from any interfering user is either decoded or considered as noise at the receiver side. We propose the following method to obtain an achievable rate for this channel. Assuming its own data is decoded successfully, the receiver partitions the set of interfering users into two disjoint subsets, namely the set of decodable users and the set of non-decodable users. Then the transmitter's rate is chosen such that the intended signal can be jointly decoded with the set of decodable users. To show the strength of this method, we prove that for the additive Gaussian channel with Gaussian interfering users, the Gaussian distribution is optimal and the achievable rate is the capacity of this channel. To obtain the maximum achievable rate, one needs to find the maximum decodable subset of interfering users. Due to the large number of possible choices, having efficient algorithms that find the set of decodable users with maximum cardinality is desired. To this end, we propose an algorithm that enables the receiver to accomplish this task in polynomial time., Comment: submitted to IEEE Transactions on Information Theory

A network of $n$ wireless communication links is considered in a Rayleigh fading environment. It is assumed that each link can be active and transmit with a constant power $P$ or remain silent. The objective is to maximize the number of active links such that each active link can transmit with a constant rate $\lambda$. An upper bound is derived that shows the number of active links scales at most like $\frac{1}{\lambda} \log n$. To obtain a lower bound, a decentralized link activation strategy is described and analyzed. It is shown that for small values of $\lambda$, the number of supported links by this strategy meets the upper bound; however, as $\lambda$ grows, this number becomes far below the upper bound. To shrink the gap between the upper bound and the achievability result, a modified link activation strategy is proposed and analyzed based on some results from random graph theory. It is shown that this modified strategy performs very close to the optimum. Specifically, this strategy is \emph{asymptotically almost surely} optimum when $\lambda$ approaches $\infty$ or 0. It turns out the optimality results are obtained in an interference-limited regime. It is demonstrated that, by proper selection of the algorithm parameters, the proposed scheme also allows the network to operate in a noise-limited regime in which the transmission rates can be adjusted by the transmission powers. The price for this flexibility is a decrease in the throughput scaling law by a multiplicative factor of $\log \log n$., Comment: Submitted to IEEE Trans. Information Theory

In this paper, a multiple-relay network in considered, in which $K$ single-antenna relays assist a single-antenna transmitter to communicate with a single-antenna receiver in a half-duplex mode. A new Amplify and Forward (AF) scheme is proposed for this network and is shown to achieve the optimum diversity-multiplexing trade-off curve.