18 October 2010 in IEEE Transactions on Information Theory
We consider a communication system where two transmitters wish to exchange information through a central relay. The transmitter and relay nodes exchange data over synchronized, average power constrained additive white Gaussian noise channels with a real input with signal-to-noise ratio (SNR) of snr. An upper bound on the capacity is 1/2 log(1 + snr) bits per transmitter per use of the multiple access phase and broadcast phase of the bidirectional relay channel. We show that, using lattice codes and lattice decoding, we can obtain a rate of 1/2 log(1/2 + snr) bits per transmitter, which is essentially optimal at high SNR. The main idea is to decode the sum of the codewords modulo a lattice at the relay followed by a broadcast phase which performs Slepian-Wolf coding. We also show that if the two transmitters use identical lattices with minimum angle decoding, we can achieve the same rate of 1/2 log(1/2 + snr). The proposed scheme can be thought of as a joint physical-layer network-layer code which outperforms other recently proposed analog network coding schemes.
14 June 2010 in IEEE Transactions on Information Theory
The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages X={x1,...,xk} and a set of receivers R. Each receiver (x,H) in R needs to obtain a message x X and has prior side information consisting of a subset H of X . The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.
27 February 2012 in IEEE Transactions on Information Theory
We consider the problem of securing a multicast network against a wiretapper that can eavesdrop on the packets on a limited number of network edges of its choice. We assume that the network employs network coding to simultaneously deliver the packets available at the source to all the destinations. We show that this problem can be looked at as a network generalization of the wiretap channel of type II introduced in a seminal paper by Ozarow and Wyner. In particular, we show that the transmitted information can be secured by using the Ozarow-Wyner approach of coset coding at the source on top of the existing network code. This way, we quickly and transparently recover some of the results available in the literature on secure network coding for wiretap networks. Moreover, we use this framework to derive new bounds on the code alphabet size that are independent of the network size, and provide algorithms for explicit construction of secure network codes. We also analyze the amount of information that can be leaked to the wiretapper as a function of the number of wiretapped edges.
24 October 2019 in IEEE Transactions on Information Theory
We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of $K$ independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of $M$ messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message with downloading minimum amount of data from the servers while achieving information-theoretic privacy in one of the following two scenarios: (i) the user wants to protect jointly the identities of the demand and the side information; (ii) the user wants to protect only the identity of the demand, but not necessarily the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is $K-M$ messages, and in the second scenario it is $\lceil K/(M+1)\rceil $ messages, which should be compared to $K$ messages—the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.
5 June 2006 in IEEE Transactions on Information Theory
In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying communication network G. The nodes of the multicast network can be broadly categorized into two groups. The first group includes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper, we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by h/sup 3/k/sup 2/. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by h/sup 3/k/sup 2/. We show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require /spl Omega/(h/sup 2/k) encoding nodes. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the minimum feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. We prove that the number of encoding nodes is bounded by (2B+1)h/sup 3/k/sup 2/, where B is the minimum size of a feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of required encoding nodes is an /spl Nscr/P-hard problem.
19 March 2012 in IEEE Transactions on Sustainable Energy
In this paper, wake effect is explicitly incorporated in the reliability evaluation of a wind farm. Energy loss resulting from this effect is included in calculating the reliability indices. Three models for wake effect are discussed and the Jensen model is used in this research. In this model, wind shade, shear effect, and wind direction are also reflected. After incorporating the wake effect, the Monte Carlo technique is used to compute reliability indices. Wind farm model and correlation between load and wind speed are considered. The proposed methodology is applied to a wind farm using wind speed data from the National Renewal Energy Laboratory and load from IEEE Reliability Test Systems. The simulation results show that the proposed techniques are effective and efficient in practical applications.