# Publications

## Monographs

1. C. Fragouli and E. Soljanin, Network Coding Fundamentals, Foundations and Trends in Networking, Now Publishers, June 2007.
2. C. Fragouli and E. Soljanin, Network Coding Applications, Foundations and Trends in Networking, Now Publishers, January 2008.

## Book chapters

1. K. Argyraki, C. Fragouli and L. Keller, Multipath diversity and robustness for sensor networks, chapter in Sensor Networks - Where Theory Meets Practice, Springer-Verlag, 2009.
2. C. Fragouli, Network coding for Sensor Network Applications, chapter in Handbook on Array Processing and Sensor Networks, IEEE-Wiley, 2009.

## Journal and conference papers

#### A PHP Error was encountered

Severity: Warning

Message: Creating default object from empty value

Filename: gettext/gettext.inc

Line Number: 195

### Preprints

1. , , and , SenseCode: Network Coding for Reliable Sensor Networks, ACM Transactions on Sensor Networks, 9:2, 2013
Citation: BibTeX RIS
Designing a communication protocol for sensor networks often involves obtaining the “right” trade-off be- tween energy efficiency and end-to-end packet error rate. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks—and, to the best of our knowledge, the first such implemented pro- tocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing end-to-end packet error rate in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it reduces end-to-end packet error rate in highly dynamic environments, while consuming a comparable amount of network resources. We have implemented SenseCode as a TinyOS module and evaluate it through extensive TOSSIM simulations.
2. and , Combinatorial algorithms for wireless information flow, ACM Transactions on Algorithms, 2011
Citation: BibTeX RIS
A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts. In this paper, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
3. , , and , SmartCast: Cooperative video streaming on smartphones, in IEEE Allerton Conference on Communications, Control and Computing, 2011
Citation: BibTeX RIS
Video applications are increasingly popular over smartphones. However, in current cellular systems, the downlink data rate fluctuates and the loss rate can be quite high. We are interested in the scenario where a group of smartphone users, within proximity of each other, are interested in viewing the same video at the same time and are also willing to cooperate with each other. We propose a system that maximizes the video quality by appropriately using all available resources, namely the cellular connections to the phones as well as the device-to-device links that can be established via Bluetooth or WiFi. Key ingredients of our design are: (i) the cooperation among users, (ii) network coding, and (iii) exploiting broadcast in the mobile-to-mobile links. Our approach is grounded on a network utility maximization formulation of the problem. We present numerical results that demonstrate the benefit of our approach, and we implement a prototype on android phones.
4. , and , Inferring Logical Topologies using Network Coding, N/A, 2010

Citation: BibTeX RIS
The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity, etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. Our main idea behind using network coding is to introduce topologydependent correlation, which can be exploited at the receivers to infer the topology. We explored this idea in [33] for trees. We also combined network coding and tomographic techniques to infer the topology of a Directed Acyclic Graph (DAG), under specific routing assumptions, in [34]. The supporting idea in [34] was to decompose a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem into multiple two source, two receiver subproblems, as shown in [12]. In this paper, we unify and extend our two previous pieces of work. Our main contribution is that when intermediate nodes perform network coding, topological information contained in network coded packets allows to uniquely identify a tree topology, or to accurately distinguish among all different 2-by-2 subnetwork components in a general DAG; this knowledge can then be used to merge the subnetworks and reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.
5. , and , A network coding approach to network tomography, IEEE Transactions on Information Theory, 2009

Citation: BibTeX RIS
6. , , and , Approximate capacity of a class of gaussian interference-relay networks, IEEE Transactions on Information Theory, 2009

Citation: BibTeX RIS
7. , and , Subspace properties of network coding and their applications, IEEE Transactions on Information Theory, 2008

Citation: BibTeX RIS

### 2013

1. , and , Broadcast erasure channel with feedback: the two multicast case - algorithms and bounds, in IEEE Symposium on Network Coding (NetCod), 2013
Citation: BibTeX RIS
2. , , , , and , Creating Secrets out of Erasures, in Proceedings of the ACM Conference on Mobile Computing and Networking (MobiCom), Miami, Florida, USA, 2013
Citation: BibTeX RIS
Current security systems often rely on the adversary's computational limitations. Wireless networks offer the opportunity for a different, complementary kind of security, which relies on the adversary's limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We present a system that leverages this opportunity to enable N wireless nodes to create a shared secret S, in a way that an eavesdropper, Eve, obtains very little information on S. Our system consists of two steps: (1) The nodes transmit packets following a special pattern, such that Eve learns very little about a given fraction of the transmitted packets. This is achieved through a combination of beam forming (from many different sources) and wiretap codes. (2) The nodes participate in a protocol that reshuffles the information known to each node, such that the nodes end up sharing a secret that Eve knows very little about. Our protocol is easily implementable in existing wireless devices and scales well with the number of nodes; these properties are achieved through a combination of public feedback, broadcasting, and network coding. We evaluate our system through a 5-node testbed. We demonstrate that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.
3. , , and , Exchanging Pairwise Secrets Efficiently, in Proceedings of the 32nd Annual IEEE International Conference on Computer Communications (INFOCOM), Turin, Italy, 2013
Citation: BibTeX RIS
We consider the problem where a group of wireless nodes, connected to the same broadcast domain, want to create pairwise secrets, in the presence of an adversary Eve, who tries to listen in and steal these secrets. Existing solutions assume that Eve cannot perform certain computations (e.g., large-integer factorization) in useful time. We ask the question: can we solve this problem without assuming anything about Eve's computational capabilities? We propose a simple secret-agreement protocol, where the wireless nodes keep exchanging bits until they have agreed on pairwise secrets that Eve cannot reconstruct with very high probability. Our protocol relies on Eve's limited network presence (the fact that she cannot be located at an arbitrary number of points in the network at the same time), but assumes nothing about her computational capabilities. We formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure (it leaks zero information to Eve about the secrets). Using a small wireless testbed of smartphones, we provide experimental evidence that it is feasible for 5 nodes to create thousands of secret bits per second, with their secrecy being independent from the adversary's capabilities.
4. , , and , Exploiting Common Randomness: a Resource for Network Secrecy, in IEEE Information Theory Workshop (ITW), 2013

Citation: BibTeX RIS
5. , , and , Low cost security for sensor networks, in Proceedings of the 2013 IEEE International Symposium on Network Coding (NetCod), Calgary, Canada, 2013
Citation: BibTeX RIS
We design and evaluate a lightweight encryption protocol suitable for sensor networks, that enables weak security in the presence of passive eavesdroppers. At every communication round, our protocol creates a key between each sensor node and the sink, by appropriately mixing and coding information packets that the nodes passively overhear. Evaluation using the TOSSIM simulator indicates that with our protocol we can gain significant security benefits at low overhead cost.
6. , and , On the structure of approximately optimal schedules for half-duplex diamond networks, in Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 2013

Citation: BibTeX RIS
7. and , Pliable Index Coding - The Multiple Requests Case, in Proceedings of the IEEE International Symposium on Infromation Theory (ISIT), 2013

Citation: BibTeX RIS
8. , , , and , Quantize-Map-Forward (QMF) Relaying - An Experimental Study, 2013

Citation: BibTeX RIS
9. , , and , Secure Network Coding with Erasures and Feedback, in Annual Allerton Conference on Communication, Control, and Computing, 2013
Citation: BibTeX RIS
10. , , and , Securing Broadcast Against Dishonest Receivers, in IEEE Symposium on Network Coding (NetCod), 2013
Citation: BibTeX RIS
11. , , and , Stable and capacity achieving XOR-based policies for the broadcast erasure channel with feedback, 2013

Citation: BibTeX RIS

### 2012

1. , and , Active topology inference using network coding, Physical Communication, 2012

Citation: BibTeX RIS
2. , , and , Broadcasting Private Messages Securely, in IEEE International Symposium on Information Theory (ISIT), IEEE, 2012
Citation: BibTeX RIS
3. , , and , Creating shared secrets out of thin air, in Proceedings of the 11th ACM Workshop on Hot Topics in Networks, Redmond, Washington, ACM, 2012

Citation: BibTeX RIS
4. , and , Feedback-based coding algorithms for broadcast erasure channels with degraded message sets, in Proceedings NETCOD, 2012
Citation: BibTeX RIS
5. , , and , Function computation via subspace coding, Physical Communication, 2012
Citation: BibTeX RIS
This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.
6. , , and , Is non-unique decoding necessary?, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012

Citation: BibTeX RIS
7. , , , , and , Microcast: Cooperative video streaming on smartphones, in Proceedings of the 10th international conference on Mobile systems, applications, and services, ACM, 2012
Citation: BibTeX RIS
Video streaming is one of the increasingly popular, as well as demanding, applications on smartphones today. In this paper, we consider a group of smartphone users, within proximity of each other, who are interested in watching the same video from the Internet at the same time. The common practice today is that each user downloads the video independently using her own cellular connection, which often leads to poor quality. We design, implement, and evaluate a novel system, MicroCast, that uses the resources on all smartphones of the group in a cooperative way so as to improve the streaming experience. Each 4 phone uses simultaneously two network interfaces: the cellular to connect to the video server and the WiFi to connect to the rest of the group. Key ingredients of our design include the following. First, we propose a scheduling algorithm, MicroDownload, that decides which parts of the video each phone should download from the server, based on the phones’ download rate. Second, we propose a novel all-to-all local dissemination scheme, MicroNC-P2, for sharing content among group members, which outperforms state-of-the-art peer-to-peer schemes in our setting. MicroNC-P2 is designed to exploit WiFi overhearing and network coding, based on a local packet broadcast framework, MicroBroadcast, which we developed specifically for Android phones. We evaluate MicroCast on a testbed consisting of seven Android phones, and we show that it brings significant performance benefits without battery penalty.
8. , , and , MicroPlay: a networking framework for local multiplayer games, in Proceedings of the first ACM international workshop on Mobile gaming, ACM, 2012
Citation: BibTeX RIS
Smartphones are an ideal platform for local multiplayer games, thanks to their computational and networking capabilities as well as their popularity and portability. However, existing game engines do not exploit the locality of players to improve game latency. In this paper, we propose MicroPlay, a complete networking framework for local multiplayer mobile games. To the best of our knowledge, this is the first framework that exploits local connections between smartphones, and in particular, the broadcast nature of the wireless medium, to provide smooth, accurate rendering of all players with two desired properties. First, it performs direct-input rendering (i.e., without any inter- or extrapo- lation of game state) for all players; second, it provides very low game latency. We implement a MicroPlay prototype on Android phones, as well as an example multiplayer car racing game, called Racer, in order to demonstrate MicroPlay’s capabilities. Our experiments show that cars can be rendered smoothly, without any prediction of state, and with only 20–30 ms game latency.
9. and , Multi-terminal secrecy in a linear non-coherent packetized networks, in Network Coding (NetCod), 2012 International Symposium on, IEEE, 2012

Citation: BibTeX RIS
10. , and , On Multicasting Nested Message Sets over Combination Networks, in IEEE Information Theory Workshop (ITW), 2012

Citation: BibTeX RIS
11. , and , Optimizing Quantize-Map-and-Forward in Slow Fading Relay Networks, in 2012 50Th Annual Allerton Conference On Communication, Control, And Computing (Allerton), Ieee, 2012

Citation: BibTeX RIS
Quantize-Map-and-Forward (QMF) relaying has been shown to achieve the optimal diversity-multiplexing trade-off (DMT) for the slow fading single-antenna relay channel, regardless of whether the relay is full-duplex or half-duplex. A key reason for the DMT optimality is that quantizing at the noise level suffices to achieve the cut-set bound approximately and hence the relay does not need any instantaneous channel state information (CSI). However, DMT only captures the high SNR performance and potentially, limited CSI at the relay can help improve the performance in moderate SNR regimes. In this work we propose an optimization framework for QMF relaying in slow fading relay channels. Focusing on vector Gaussian quantizers, for the full-duplex relay we optimize the outage probability by finding the best quantization level according to the available CSI at the relay and the channel statistics. For the half-duplex relay we find good relay schedules using the same framework. Numerical evaluations show the improvement of taking the CSI into account over noise-level quantization and static schedules in moderate SNR regimes.
12. and , Pliable index coding, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012

Citation: BibTeX RIS
13. and , Properties of network polynomials, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012

Citation: BibTeX RIS
14. , and , Real-time delay with network coding and feedback, Physical Communication, 2012
Citation: BibTeX RIS
We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of μ messages to several receivers. The sender can broadcast a single message or a combination of messages at each timestep, through separate erasure channels. Receivers provide feedback as to whether the transmission was received. If, at some time step, a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. Our setup is novel in that it combines coding techniques with feedback information to the end of minimizing delay. We show that it allows Θ(μ) benefits as compared to previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay compared to online algorithms without feedback. Our main complexity result is that the offline minimization problem is NP-hard both under scheduling and coding algorithms. However we show that coding does offer delay and complexity gains over scheduling. We also discuss online heuristics and evaluate their performance through simulations.
15. , and , Simple schedules for half-duplex networks, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012

Citation: BibTeX RIS
16. , and , Subspace properties of network coding and their applications, Information Theory, IEEE Transactions on, 58:5, 2012

Citation: BibTeX RIS
17. , , and , Towards integrating Quantize-Map-Forward relaying into LTE, in Information Theory Workshop (ITW), IEEE, 2012

Citation: BibTeX RIS
We present a method to integrate the Quantize-Map-Forward (QMF) relaying scheme into the standard LTE operation, for a two-relay diamond network configuration. Our approach implements QMF using mainly existing LTE modules and functionalities, and results in minimal changes in the standard link-layer LTE operation. In particular, the destination operation is only affected in that we adapt the log-likelihood ratio (LLR) calculations at the decoder input to take into account the existence of relays; thus, the decoding complexity and operations (apart the LLR calculations) are not modified. We report extensive performance evaluations of our scheme using the OpenAirInterface (OAI) link-level simulation tools.
18. , , and , Untrusting network coding, in Network Coding (NetCod), 2012 International Symposium on, IEEE, 2012

Citation: BibTeX RIS

### 2011

1. , , and , A mobile world of security, in CISS, 2011

Citation: BibTeX RIS
2. , , and , A network coding approach to the sniper detection problem, in IEEE Wireless Measurements Workshop (WinMee), 2011
Citation: BibTeX RIS
This paper experimentally studies the reliability and delay of flooding based multicast protocols for a sniper detection application. In particular using an emulator it studies under which conditions protocols based on network coding deliver performance improvements compared to classic flooding. It then presents an implementation of such protocols on mobile phones.
3. and , Algorithms for vector network coding, IEEE Transactions on Information Theory (Special Issue on Facets of Coding Theory: from Algorithms to Networks), 2011
Citation: BibTeX RIS
We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L x L coding matrices that play a similar role as coding coefficients in scalar coding. We start our work by extending the algebraic framework developed for multicasting over graphs in [1] to include operations over matrices; we build on this generalized framework, to provide a new approach for both scalar and vector code design which attempts to minimize the employed field size and employed vector length, while selecting the coding operations. Our algorithms also lead as a special case to network code designs that employ structured matrices.
4. , , and , Approximate capacity of a class of relay-interference networks, IEEE Transactions on Information Theory, 57:5, 2011

Citation: BibTeX RIS
5. , , and , Degraded multicasting with network coding over the combination network, in IEEE International Symposium on Network Coding (NetCod), 2011

Citation: BibTeX RIS
6. and , Degraded two-message multicast over graphs, in IEEE International Symposium on Information Theory (ISIT), 2011

Citation: BibTeX RIS
7. , , , and , Graph-based codes for Quantize-Map-and-Forward relaying, in Information Theory Workshop (ITW), 2011 IEEE, IEEE, 2011

Citation: BibTeX RIS
8. , , and , Group secret key agreement over state-dependent wireless broadcast channels, in IEEE International Symposium on Information Theory (ISIT), 2011

Citation: BibTeX RIS
9. , and , Maximum likelihood estimation for multiple-source loss tomography with network coding, in IEEE International Symposium on Network Coding (NetCod), 2011

Citation: BibTeX RIS
10. , Network coding: beyond throughput benefits, Special Issue on Network Coding at the Proceedings of the IEEE, 2011
Citation: BibTeX RIS
11. , , and , Network simplification: the Gaussian diamond network with Multiple Antennas, in IEEE International Symposium on Information Theory (ISIT), 2011

Citation: BibTeX RIS
12. and , On secure key exchange in wireless networks, in IEEE International Symposium on Network Coding (NetCod), 2011

Citation: BibTeX RIS
13. , , and , On the capacity of non-coherent network coding, IEEE Transactions on Information Theory (Special Issue on Facets of Coding Theory: from Algorithms to Networks), 57:2, 2011

Citation: BibTeX RIS
We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized network coding operations on the source packets. We propose a channel model for the non-coherent network coding introduced by Koetter and Kschischang in [6], that captures the essence of such a network operation, and calculate the capacity as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.
14. , , and , Reliability of clustered vs. declustered replica placement in data storage systems, in IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), 2011

Citation: BibTeX RIS
15. , , and , Secret message capacity of erasure broadcast channels with feedback, in IEEE Information Theory Workshop (ITW), 2011

Citation: BibTeX RIS

### 2010

1. and , Algebraic techniques for deterministic networks, in International conference on Signal Processing and Communications (SPCOM), 2010

Citation: BibTeX RIS
2. , , , and , Effect of Replica Placement on the Reliability of Large-Scale Data Storage Systems, Modeling, Analysis, and Simulation of Computer Systems, International Symposium on, 2010
Citation: BibTeX RIS
Replication is a widely used method to protect largescale data storage systems from data loss when storage nodes fail. It is well known that the placement of replicas of the different data blocks across the nodes affects the time to rebuild. Several systems described in the literature are designed based on the premise that minimizing the rebuild times maximizes the system reliability. Our results however indicate that the reliability is essentially unaffected by the replica placement scheme. We show that, for a replication factor of two, all possible placement schemes have mean times to data loss (MTTDLs) within a factor of two for practical values of the failure rate, storage capacity, and rebuild bandwidth of a storage node. The theoretical results are confirmed by means of event-driven simulation. For higher replication factors, an analytical derivation of MTTDL becomes intractable for a general placement scheme. We therefore use one of the alternate measures of reliability that have been proposed in the literature, namely, the probability of data loss during rebuild in the critical mode of the system. Whereas for a replication factor of two this measure can be directly translated into MTTDL, it is only speculative of the MTTDL behavior for higher replication factors. This measure of reliability is shown to lie within a factor of two for all possible placement schemes and any replication factor. We also show that for any replication factor, the clustered placement scheme has the lowest probability of data loss during rebuild in critical mode among all possible placement schemes, whereas the declustered placement scheme has the highest probability. Simulation results reveal however that these properties do not hold for the corresponding MTTDLs for a replication factor greater than two. This indicates that some alternate measures of reliability may not be appropriate for comparing the MTTDL of different placement schemes.
3. , and , Function computation over linear channels, in IEEE International Symposium on Network Coding (NetCod), 2010
Citation: BibTeX RIS
This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.
4. , , and , Function computation via subspace coding, in IEEE International Symposium on Information Theory (ISIT), 2010
Citation: BibTeX RIS
This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.
5. , , , and , Joint identity-message coding for sensor networks, IEEE JSAC on Wireless Sensor Networks, 2010
Citation: BibTeX RIS
In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit---for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occurred, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how communication should happen in such identity-aware sensor networks. We calculate theoretical performance bounds for this type of communication, where performance'' refers to the number of transmitted bits. We propose a communication protocol, where the identity and message of each source are specified jointly using subspace coding. We show through analysis and simulation that our protocol's performance is close to optimal and compare it to the performance of a traditional protocol, where identity and message are specified separately.
6. and , Multicasting algorithms for deterministic networks, in IEEE Information Theory Workshop (ITW), 2010
Citation: BibTeX RIS
We present a polynomial time algorithm for multicasting rate h to N receivers over deterministic networks. Our algorithm requires intermediate network nodes to perform coding operations over vectors of a finite length L, through multiplication with L #x00D7; L binary coding matrices that play the same role as coding coefficients over graphs. Our code design consists in selecting these matrices so that each receiver is able to recover the source information. As a special case, we provide an alternative construction for a unicast algorithm over deterministic networks.
7. , , and , On relay placement for deterministic line networks, in IEEE Wireless Network Coding Workshop (WiNC), 2010
Citation: BibTeX RIS
We consider a unicast communication problem where a source transmits information to a destination through a wireless network with the help of k relays positioned on a line. We adopt the linear deterministic model to capture the wireless signal interactions and study the optimal placement of the relays so that the capacity from the source to the destination in the deterministic network is maximized. Analytical results are provided for a number of special cases, and the insights gained are used to provide a heuristic framework for designing large relay networks.
8. and , On the benefits of vector network coding, in 48th Annual Allerton Conference on Communication, Control, and Computing, 2010
Citation: BibTeX RIS
In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L x L coding matrices that play a similar role as coding coefficients in scalar coding. Vector network coding generalizes scalar coding, and thus offers a wider range of solutions over which to optimize. This paper starts exploring the new possibilities vector network coding can offer along two directions. First, we propose a new randomized algorithm for vector network coding. We compare the performance of our proposed algorithm with the existing randomized algorithms in the literature over a specific class of networks. Second, we explore the use of structured coding matrices for vector network coding. We present deterministic designs that allow to operate using rotation coding matrices and thus result in reduced encoding complexity.
9. , and , Silence based communication, IEEE Transactions on Information Theory, 56, 2010
Citation: BibTeX RIS
Communication complexity---the minimum amount of communication required---of computing a function of data held by several parties is studied. A communication model where silence is used to convey information is introduced. For this model the worst-case and average-case complexities of symmetric functions are studied. For binary-input functions the average- and worst-case complexities are determined and the protocols achieving them are described. For functions of non-binary inputs one-round communication, where each party is restricted to communicate in consecutive stages, is considered and the extra amount of communication required by one- over multi-round communication is analyzed. For the special case of ternary-input functions close lower and upper bounds on the worst-case one-round complexity are provided and protocols achieving them are described. Protocols achieving the average-case one-round complexity for ternary-input functions are also described. These protocols can be generalized to inputs of arbitrary size.
10. and , Vector network coding, in IEEE International Symposium on Information Theory (ISIT), 2010
Citation: BibTeX RIS
We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L x L coding matrices that play a similar role as coding coefficients in scalar coding. Our algorithms for scalar network jointly optimize the employed field size while selecting the coding coefficients. Similarly, for vector coding, our algorithms optimize the length L while designing the coding matrices. These algorithms apply both for regular network graphs as well as linear deterministic networks.

### 2009

1. , An overview of network coding for dynamically changing networks, Int. J. Auton. Adapt. Commun. Syst., 2:1, 2009

Citation: BibTeX RIS
2. , , and , Capacity of deterministic Z-chain relay-interference network, in IEEE Information Theory Workshop (ITW), 2009
Citation: BibTeX RIS
The wireless multiple-unicast problem is considered over a layered network, where the rates of transmission are limited by the relaying and interference effect. The deterministic model introduced is used to capture the broadcasting and multiple access effects. The capacity region of the Z-chain relay-interference network is fully characterized. In order to solve the problem, we introduce a new achievability scheme based on ldquointerference neutralizationrdquo and a new analysis technique to bound the number of non-interfering (pure) signals
3. and , Combinatorial algorithms for wireless information flow, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009

Citation: BibTeX RIS
A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear binary deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the binary adjacency matrices describing source-destination cuts. However, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes infeasible. In this work, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in binary linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between edges to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-bit processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
4. , , and , Compressed network coding vectors, in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, 2009
Citation: BibTeX RIS
In networks that employ network coding, two main approaches have been proposed in the literature to allow the receivers to recover the source information: (i) use of coding vectors, that keep track of the linear combinations the received packets contain, and (ii) subspace coding, that dispenses of the need to know the linear combinations, since information is conveyed from the choice of subspaces alone. Both these approaches impose the strong requirement that all source packets get potentially combined. We here present a third approach that relaxes this assumption, and is thus not a special case from either of the previous two. This relaxation allows to employ compressed coding vectors to efficiently convey the coding coefficients, without altering the operation of intermediate network nodes. We develop optimal designs for such vectors.
5. , and , Delay with network coding and feedback, in IEEE International Symposium on Information Theory (ISIT), 2009
Citation: BibTeX RIS
We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of mu messages to several receivers over separate erasure channels. The sender can broadcast a single message or a combination (encoding) of messages at each timestep. Receivers provide feedback as to whether the transmission was received. If at some time step a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. Our setup is novel because it combines coding techniques with feedback information to the end of minimizing delay. It allows Theta(mu) benefits as compared to previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay than online algorithms without feedback. Our main complexity results are that the offline minimization problem is NP-hard when the sender only schedules single messages and that the general problem remains NP-hard even when coding is allowed. However we show that coding does offer delay and complexity gains over scheduling. We also discuss online heuristics and evaluate their performance through simulations.
6. , , and , Distributed Rate Allocation for Network-coded Systems, in Sensor, Mesh and Ad Hoc Communications and Networks Workshops, 2009. SECON Workshops '09. 6th Annual IEEE Communications Society Conference on, 2009
Citation: BibTeX RIS
This paper addresses the problem of distributed rate allocation for a class of multicast networks employing linear network coding. The goal is to minimize the cost (for example, the sum rates allocated to each link in the network) while satisfying a multicast rate requirement for each destination in the network. In essence, this paper aims to achieve network capacity while ensuring that the cost of operation (equivalently, the rate allocated per link in the network) is minimal. This paper uses a belief propagation framework to obtain a distributed algorithm for the rate allocation problem. Simulation results are presented to demonstrate the convergence of this algorithm to the optimal rate allocation solution.
7. , , , and , Identity aware sensor networks, in INFOCOM 2009, IEEE, 2009
Citation: BibTeX RIS
In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occured, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how should communication happen in such identity-aware sensor networks. We reexamine the traditional source-identity/message separation and propose a scheme for jointly encoding the two. We use this to develop a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks - for instance, node failures, or large numbers of nodes where only few are active during each reporting round.
8. , and , Multipath Diversity and Robustness for Sensor Networks, in: Sensor Networks, Springer, 2009
Citation: BibTeX RIS
Balancing energy efficiency and reliability is a common underlying goal for most information collection protocols in sensor networks. Multipath diversity has emerged as one of the promising techniques to achieve such a balance. In this chapter, we provide a unified framework for the multipath techniques in the literature and discuss their basic benefits and drawbacks. We also discuss emerging techniques from the area of network coding.
9. , and , Multiple source multiple destination topology inference using network coding, in Network Coding, Theory, and Applications, 2009. NetCod '09. Workshop on, 2009
Citation: BibTeX RIS
In this paper, we combine network coding and tomographic techniques for topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. We combine and extend two ideas that have been developed independently. On one hand, network coding introduces topology-dependent correlation, which can then be exploited at the receivers to infer the topology. On the other hand, it has been shown that a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem can be decomposed into multiple two source, two receiver subproblems. Our first contribution is to show that, when intermediate nodes perform network coding, topological information contained in network coded packets allows to accurately distinguish among all different 2-by-2 subnetwork components, which was not possible with traditional tomographic techniques. Our second contribution is to use this knowledge to merge the subnetworks and accurately reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.
10. , and , Network coding for undirected information exchange, Communications Letters, IEEE, 13:1, 2009
Citation: BibTeX RIS
We consider the information exchange problem where each in a set of terminals transmits information to all other terminals in the set, over an undirected network. We show that the design of only a single network code for multicasting is sufficient to achieve an arbitrary point in the achievable rate region. We also provide an alternative proof for the set of achievable rate tuples.
11. , , and , On Degraded Two Message Set Broadcast, in IEEE Information Theory Workshop (ITW), 2009
Citation: BibTeX RIS
We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P x U. Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.
12. , , and , On the capacity of multisource non-coherent network coding, in Networking and Information Theory, 2009. ITW 2009. IEEE Information Theory Workshop on, 2009
Citation: BibTeX RIS
We consider multisource non-coherent network coding, where multiple sources send information to one or multiple receivers. We prove that this is equivalent to a ldquosubspacerdquo channel, that takes subspaces as inputs and outputs. We then show that the rate of each individual receiver is upper bounded as deltai(T - delta1 - delta2), where deltai is what we define to be the ldquodominatingrdquo dimension in the subspace codebook of source i, and T is the ldquocoherencerdquo time of the network.
13. , , and , On the capacity of non-coherent network coding, in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, 2009
Citation: BibTeX RIS
The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N ges 1 receivers can also be achieved using packets of length logN bits, if the operations the intermediate nodes perform are deterministically known at the receivers. We here calculate the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.
14. , , and , SenseCode: Network coding for reliable sensor networks, EPFL Technical Report, in submission, 2009

Citation: BibTeX RIS
Designing a communication protocol for sensor networks often involves obtaining the right'' trade-off between energy efficiency and reliability. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks---and, to the best of our knowledge, the first such protocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing reliability in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it achieves higher reliability (typically 20%, in certain cases up to 30%), while consuming the same amount of network resources. We have implemented SenseCode as a TinyOs module, and evaluate it through TOSSIM simulations, as well as a testbed of 30 TinyNode sensors deployed in our department building

### 2008

1. , and , Efficient broadcasting using network coding, IEEE/ACM Transactions on Networking, 16, 2008
Citation: BibTeX RIS
We consider the problem of broadcasting in an ad hoc wireless network, where all nodes of the network are sources that want to transmit information to all other nodes. Our figure of merit is energy efficiency, a critical design parameter for wireless networks since it directly affects battery life and thus network lifetime. We prove that applying ideas from network coding allows to realize significant benefits in terms of energy efficiency for the problem of broadcasting, and propose very simple algorithms that allow to realize these benefits in practice. In particular, our theoretical analysis shows that network coding improves performance by a constant factor in fixed networks. We calculate this factor exactly for some canonical configurations. We then show that in networks where the topology dynamically changes, for example due to mobility, and where operations are restricted to simple distributed algorithms, network coding can offer improvements of a factor of , where is the number of nodes in the network. We use the insights gained from the theoretical analysis to propose low-complexity distributed algorithms for realistic wireless ad hoc scenarios, discuss a number of practical considerations, and evaluate our algorithms through packet level simulation.
2. , Network coding for dynamically changing networks, IEEE International Wireless Communications and Mobile Computing Conference, 2008
Citation: BibTeX RIS
We here advocate the case for network coding as a guiding paradigm for the operation of networks that vary in a small time frame, due to node mobility, channel variations, and varying traffic conditions. Three ideas that appeared succesively in time brought in place an elegant operation for network coding in such environments. These are, use of randomized network coding for intermediate node operation, use of generations to avoid synchronization, and use of subspace coding to allow for small packet sizes. Information theoretical performance limits support these results.
3. , , and , Network-coded broadcast: from canonical networks to random topologies, Network Coding Workshop: Theory and Applications, 2008
Citation: BibTeX RIS
We consider the problem of finding the minimum number of transmissions in an ad-hoc network for all-to-all broadcasting using network coding. This work generalizes previous results for canonical topologies such as the circle and the wrap around grid to the finite-sized line, and non-wrap-around grid. The latter topologies better reflect network coding in random topologies, since the dissemination of information is "directional", in a sense that information usually arrives via the neighbors on the path to its originator instead of from all possible directions. We find that while the line topology requires a higher number of transmissions compared to the circle, this is interestingly not the case for the grid. We further present simulation results on a heuristic that estimates the required minimum number of transmissions in random wireless topologies and compare it to the optimum solution, as well as previously proposed heuristics.
4. , and , Noncoherent multi-source network coding, IEEE International Symposium on Information Theory (ISIT), 2008
Citation: BibTeX RIS
We examine the problem of multiple sources transmitting information to one or more receivers that require the information from all the sources, over a network where the network nodes perform randomized network coding. We consider the noncoherent case, where neither the sources nor the receivers have any knowledge of the intermediate nodes operations. We formulate a model for this problem, inspired from block- fading noncoherent MIMO communications. We prove, using information theoretic tools, that coding over subspaces is sufficient to achieve the capacity, and give bounds for the capacity. We then examine the associated combinatorial problem of code design. We extend the work by Koetter and Kschischang [3] to code constructions for the multisource case. Our constructions can also be viewed as coding for the noncoherent multiple-access finite-field channel.
5. , and , On Locating Byzantine Attackers, Network Coding Workshop: Theory and Applications, 2008
Citation: BibTeX RIS
We examine networks that employ network coding, and are subject to Byzantine attacks. We consider systems where an appropriate network error correcting scheme is employed that is able to correct (up to a certain number of) Byzantine errors. Given this setup, we formulate the problem of locating these malicious nodes that insert errors. We utilize the subspace properties of (randomized) network coding to develop algorithms to locate the Byzantine attackers.
6. , and , Online Broadcasting with Network Coding, in Network Coding, Theory and Applications, 2008. NetCod 2008. Fourth Workshop on, 2008
Citation: BibTeX RIS
Consider a source broadcasting M packets to N receivers over independent erasure channels, where perfect feedback is available from the receivers to the source, and the source is allowed to use coding. We investigate offline and online algorithms that optimize delay, both through theoretical analysis as well as simulation results.
7. , , and , Transmission techniques for relay-interference networks, IEEE Allerton, 2008

Citation: BibTeX RIS
In this paper we study the relay-interference wireless network, in which relay (helper) nodes are to facilitate competing information ﬂows over a wireless network. We examine this in the context of a deterministic wireless interaction model, which eliminates the channel noise and focuses on the signal interactions. Using this model, we show that almost all the known schemes such as interference suppression, interference alignment and interference separation are necessary for relay-interference networks. In addition, we discover a new interference management technique, which we call interference neutralization, which allows for over-the-air interference removal, without the transmitters having complete access the interfering signals. We show that interference separation, suppression, and neutralization arise in a fundamental manner, since we show complete characterizations for special conﬁgurations of the relay-interference network.

### 2007

1. , , and , Bottleneck discovery and overlay management in network coded Peer-to-Peer systems, SIGCOMM INM, 2007
Citation: BibTeX RIS
The performance of peer-to-peer (P2P) networks depends critically on the good connectivity of the overlay topology. In this paper we study P2P networks for content distribution (such as Avalanche) that use randomized network coding techniques. The basic idea of such systems is that peers randomly combine and exchange linear combinations of the source packets. A header appended to each packet specifies the linear combination that the packet carries. In this paper we show that the linear combinations a node receives from its neighbors reveal structural information about the network. We propose algorithms to utilize this observation for topology management to avoid bottlenecks and clustering in network-coded P2P systems. Our approach is decentralized, inherently adapts to the network topology, and reduces substantially the number of topology rewirings that are necessary to maintain a well connected overlay. Moreover, this is done passively during the normal content distribution. This work demonstrates another value of using network coding and complements previous work that showed network coding achieves high utilization of the network resources.
2. , , and , Loss Tomography in General Topologies with Network Coding, IEEE GLOBECOM, 2007
Citation: BibTeX RIS
Network tomography infers internal network characteristics by sending and collecting probe packets from the network edge. Traditional tomographic techniques for general topologies typically use a mesh of multicast trees and/or unicast paths to cover the entire graph, which is suboptimal from the point of view of bandwidth efficiency and estimation accuracy. In this paper, we investigate an active probing method for link loss inference in a general topology, where multiple sources and receivers are used and intermediate nodes are equipped with network coding, in addition to unicast and multicast, capabilities. With our approach, each link is traversed by exactly one packet, which is in general a linear combination of the original probes. The receivers infer the loss rate on all links by observing not only the number but also the contents of the received probes. In this paper: (i) we propose an orientation algorithm that creates an acyclic graph with the maximum number of identifiable edges (ii) we define probe combining coding schemes and discuss some of their properties and (iii) we present simulation results over realistic topologies using Belief-Propagation (BP) algorithms.
3. , , and , Network monitoring: it depends on your points of view, ITA, 2007
Citation: BibTeX RIS
End-to-end active network monitoring infers network characteristics by sending and collecting probe packets from the network edge, while probes traverse the network through multicast trees or a mesh of unicast paths. Most reported methods consider given source and receiver locations and study the path selection and the associated estimation algorithms. In this paper, we show that appropriately choosing the number of sources and receivers, as well as their location, may have a significant effect on the accuracy of the estimation; we also give guidelines on how to choose the best points of view'' of a network for link loss monitoring purposes. Though this observation applies across all monitoring methods, we consider, in particular, networks where nodes are equipped with network coding capabilities; our framework includes as special cases the scenarios of pure multicast and network coding. We show that, in network-coding enabled networks, multiple source active monitoring can exploit these capabilities to estimate link loss rates more efficiently than purely tomographic methods. To address the complexity of the estimation problem for large networks, we also propose efficient algorithms, including the decomposition into smaller multicast inference problems, belief-propagation, and a MINC-like algorithm.
4. , , and , On feedback for network coding, in in Proc. of 2007 Conference on Information Sciences and Systems (CISS), 2007
Citation: BibTeX RIS
5. , and , On the capacity of line networks, IEEE Transactions on Information Theory, 53, 2007
Citation: BibTeX RIS
We consider communication through a cascade of discrete memoryless channels (DMCs). The source and destination node of this cascade are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of a fixed length. We investigate how the processing at the relays must be chosen in order to maximize the capacity of the cascade, that is, the maximum achievable end-to-end rate between the source and the destination. For infinite cascades with fixed intermediate processing length at the relays, we prove that this intermediate processing can be chosen to be identical without loss of optimality, and that the capacity of the cascade coincides with the rate of the best zero-error code of length equal to the block length of the intermediate processing. We further show that for fixed and identical intermediate processing at all relays, convergence of capacity as the length of the cascade goes to infinity is exponentially fast. Finally, we characterize how the block length of the intermediate processing must scale with the length of the cascade to guarantee a constant end-to-end rate. We prove that it is sufficient that the block length scales logarithmically with the network length in order to achieve any rate above the zero-error capacity. We show that in many cases of interest logarithmic growth is also necessary
6. , and , Single versus multiple rounds for distributed function computation, in Information Theory, 2007. ISIT 2007. IEEE International Symposium on, 2007
Citation: BibTeX RIS
Communication complexity of computing functions using unrestricted communication and one-round communication are compared. In the standard unrestricted communication each party could potentially communicate several times while in one-round communication each party is restricted to communicate at most once. Results on the ratio of these two complexities are provided for symmetric and asymmetric functions under different scenarios. These results are suitably illustrated with examples.
7. , and , Subspace properties of randomized network coding, in IEEE Information Theory Workshop (ITW), 2007
Citation: BibTeX RIS
Randomized network coding has network nodes randomly combine and exchange linear combinations of the source packets. A header appended to the packet, called coding vector, specifies the exact linear combination that each packet carries. The main contribution of this work is to investigate properties of the subspacesspanned by the collected coding vectors in each network node. We use these properties to exhibit the relationship between the network topology and the subspaces collected at the nodes. This allows us to passively infer the network topology for a general class of graphs.
8. , and , Towards reliable broadcasting using ACKs, ISIT, 2007
Citation: BibTeX RIS
We propose a mechanism for reliable broadcasting in wireless networks, that consists of two components: a method for bandwidth efficient acknowledgment collection, and a coding scheme that uses acknowledgments. Our approach combines ideas from network coding and distributed space time coding.
9. , , , and , Wireless network coding: opportunities and challenges, IEEE MILCOM, 2007
Citation: BibTeX RIS
Wireless networks suffer from a variety of unique problems such as low throughput, dead spots, and inadequate support for mobility. However, their characteristics such as the broadcast nature of the medium, spatial diversity, and significant data redundancy, provide opportunities for new design principles to address these problems. There has been recent interest in employing network coding in wireless networks. This paper explores the case for network coding as a unifying design paradigm for wireless networks, by describing how it addresses issues of throughput, reliability, mobility, and management. We also discuss the practical challenges facing the integration of such a design into the network stack.

### 2006

1. , and , A Network Coding Approach to Energy Efficient Broadcasting: from Theory to Practice, Infocom, 2006
Citation: BibTeX RIS
We show that network coding allows to realize significant energy savings in a wireless ad-hoc network, when each node of the network is a source that wants to transmit information to all other nodes. Energy efficiency directly affects battery life and thus is a critical design parameter for wireless ad-hoc networks. We propose an implementable method for performing network coding in such a setting. We analyze theoretical cases in detail, and use the insights gained to propose a practical, fully distributed method for realistic wireless ad-hoc scenarios. We address practical issues such as setting the forwarding factor, managing generations, and impact of transmission range. We use theoretical analysis and packet level simulation.
2. , , , and , An Analysis of Finite-Memory Random Linear Coding on Packet Streams, 2nd Network Coding Workshop, 2006
Citation: BibTeX RIS
We consider the following packet coding scheme: The coding node has a fixed, finite memory in which it stores packets formed from an incoming packet stream, and it sends packets formed from random linear combinations of its memory contents. We analyze the scheme in two settings: as a self-contained component in a network providing reliability on a single link, and as a component employed at intermediate nodes in a block-coded end-to-end connection. We believe that the scheme is a good alternative to automatic repeat request when feedback is too slow, too unreliable, or too difficult to implement.
3. and , Information Flow Decomposition for Network Coding, IEEE Trans. Inform. Theory, 2006
Citation: BibTeX RIS
The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. The main idea in this paper is the identification of structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition allows us to show that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size and calculate the throughput improvement network coding can offer for different configurations. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.
4. , and , Network coding: an instant primer, ACM SIGCOM Computer Communication Review, 2006
Citation: BibTeX RIS
Network coding is a new research area that may have interesting applications in practical networking systems. With network coding, intermediate nodes may send out packets that are linear combinations of previously received information. There are two main benefits of this approach: potential throughput improvements and a high degree of robustness. Robustness translates into loss resilience and facilitates the design of simple distributed algorithms that perform well, even if decisions are based only on partial information. This paper is an instant primer on network coding: we explain what network coding does and how it does it. We also discuss the implications of theoretical results on network coding for realistic settings and show how network coding can be used in practice.
5. , and , On achievable information rates in single-source non-uniform demand networks, ISIT, 2006

Citation: BibTeX RIS
A non-uniform demand network consists of a source and a set of receivers that have different min-cut values from the source. We look at the case where the receivers would like to receive from the source a rate that is (approximately) equal to their min-cut value. We formulate this problem and its relaxations and present preliminary results.
6. , and , On Average Throughput Benefits and Alphabet Size in Network Coding, IEEE Trans. Inform. Theory, 2006
Citation: BibTeX RIS
We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard LP formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with $N$ receivers where network coding offers benefits proportional to $\sqrt{N}$. We also discuss other throughput measures in networks, and show how in certain classes of networks, the average throughput can be achieved uniformly by all receivers by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.
7. , and , On the benefits of network coding for wireless applications, 2nd Network Coding Workshop, 2006
Citation: BibTeX RIS
We argue that the main benefits of network coding in a wireless environment might manifest in situations where the topology dynamically changes, and operation is restricted to distributed algorithms that do not employ knowledge about the network environment. We consider several problem instances in this set-up, that include broadcasting information to all nodes of the network and collecting sensor measurements. We show that in many such cases, under some simplifying assumptions, the problem is theoretically equivalent to simple variations of the coupon collector problem. Thus network coding can offer benefits of a factor of $\log n$, where $n$ is the number of nodes and the benefits are in terms of energy efficiency, as was proven in the literature. We present simulation results under more realistic conditions that support this claim.
8. , and , Scaling laws for line networks: from zero-error to min-cut capacity, ISIT, 2006
Citation: BibTeX RIS
We consider communication through a cascade of $L$ identical Discrete Memory less Channels (DMCs).The source and destination node are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of $N$ symbols.It is well known that for any $L$ and $N\to\infty$ the relays can use a capacity achieving code and communicate reliably as long as the rate of this code is below the capacity of the underlying DMC. The capacity of the cascade is hence equal to the network {\em min-cut capacity}.For finite $N$ and $L\to\infty$, we showed in previous work that the optimal intermediate processing is the highest rate zero-error code of length $N$ for the underlying DMC.The capacity of the cascade coincides with the rate of this zero-error code, and is always below the {\em zero-error capacity}.In this work, we characterize how $N$ must scale with $L$ in order to achieve rates in between the zero-error and the min-cut capacity.In particular, we have observed that $N = \Theta(\log L)$ is {\em sufficient} to achieve any rate below the min-cut capacity. Here, we develop a novel upper bound on the capacity of cascades with optimal intermediate processing that applies for any $(N,L)$ pairs and use it to show that $N = \Theta(\log L)$ is {\em necessary} to achieve certain rates above the zero-error capacity. Furthermore, we propose a method to evaluate our upper bound by establishing a connection with the Set-Cover Problem in algorithms.
9. , and , Silence based communication for sensor networks, ISIT, 2006
Citation: BibTeX RIS
We consider a power-efficient communication model for wireless sensor networks where silence is used to convey information. We study the average-case and worst-case complexities of symmetric functions under this model and describe protocols that achieve them. For binary-input functions, we determine the average complexity. For ternary-input functions, we consider a special type of protocols and provide close lower and upper bounds for their worst-case complexity. We also describe the protocol that achieves the average complexity.
10. , and , Topology inference using network coding, Allerton, 2006
Citation: BibTeX RIS
The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network using multiple sources and observations at the edges of the network. In particular, we consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations in incoming links). In previous works (e.g., Ratnasamy \& McCanne '99; Duffield et al '02), the correlation between the observed packet loss patterns is used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among multiple probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary numerical results illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).

### 2005

1. and , A Network Coding Approach to Network Monitoring, Allerton, 2005

Citation: BibTeX RIS
Network Monitoring is a challenging problem that has received a lot of attention in the Internet community, particularly in the context of overlay networks. Independently, recent advances in Network Coding have shown that it is possible to increase network capacity and better share the available resources by allowing intermediate nodes to perform processing operations, in addition to just forwarding packets. In this work, we propose the use of Network Coding techniques to improve Network Monitoring. As a specific application, we use our approach for the well-known problem of network tomography, and in particular for inferring link loss rates from end-to-end measurements. We demonstrate that our approach can decrease the bandwidth used by probes, improve the accuracy of estimation, and decrease the complexity of selecting paths or trees to send probes. Overall, we argue that the use of Network Coding techniques shows great promise for improving several aspects of monitoring in overlay networks.
2. , and , Coding schemes for line networks, ISIT, 2005
Citation: BibTeX RIS
We consider a simple network, where a source and destination node are connected with a line of erasure channels. It is well known that in order to achieve the min-cut capacity, the intermediate nodes are required to process the information. We propose coding schemes for this setting, and discuss each scheme in terms of complexity, delay, achievable rate, memory requirement, and adaptability to unknown channel parameters. We also briefly discuss how these schemes can be extended to more general networks.
3. and , Conditions for constant throughput in wireless networks, ACM Transactions on Sensor Networks, 2, 2005

Citation: BibTeX RIS
In this paper we propose a set of necessary and sufficient conditions under which the throughput in an ad-hoc network can remain constant as the number of nodes $n$ increases. Throughput refers to the minimum achievable rate between a source-destination pair for a given routing mechanism and physical model, when the network is shared by $\Theta(n)$ randomly chosen source-destination pairs. The main idea is to use a {\em connectivity graph}, that does not represent the actual physical network, but rather the available communication resources. This graph also allows to translate the problem of maximizing t he throughput in ad-hoc networks to the multicommodity flow problem and directly apply related results.
4. , and , Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding, 1st Network Coding Workshop, 2005
Citation: BibTeX RIS
Energy efficiency, i.e., the amount of battery energy consumed to transmit bits across a wireless link, is a critical design parameter for wireless ad-hoc networks. This paper examines the problem of broadcasting information to all nodes in an ad-hoc network, when a large percentage of the nodes act as sources. For this application, we theoretically quantify the energy savings that network coding can offer in the cases of a line network and a rectangular grid network. We then propose low-complexity distributed algorithms, and demonstrate through simulation that in practice, for random networks, network coding can in fact offer significant benefits in terms of energy consumption.
5. , and , On average throughput benefits and alphabet size in network Coding, ISIT, 2005
Citation: BibTeX RIS
We analyze a special class of configurations with $h$ sources and $N$ receivers to demonstrate the throughput benefits of network coding and deterministic code design. We show that the throughput benefits network coding offers can increase proportionally to $\sqrt{N}$, with respect to the average as well as the minimum throughput. We also show that while for this class of configurations there exists a deterministic coding scheme that realizes these benefits using a binary alphabet, randomized coding may require an exponentially large alphabet size.
6. , and , On cascaded channels with finite complexity processing at intermediate nodes, Allerton, 2005
Citation: BibTeX RIS
We consider communication through an infinite cascade of identical discrete memoryless channels. We allow the source and destination nodes to use coding schemes of arbitrary complexity, but restrict the intermediate (relay) nodes to process blocks of a fixed blocklength. We calculate the optimal end-to-end rate, maximized over all possible processings at the relays, and show that it coincides with the end-to-end zero-error capacity. The optimal processing is shown to be identical at each relay and to correspond to a zero-error code. We also show that the rate of convergence to the asymptotic value is exponential in the length of the cascade.
7.
Citation: BibTeX RIS
We consider a source that transmits information to a receiver by routing it over a communication network represented by a graph and examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that there exist configurations where the optimal rate is achieved only when coding across independent information streams (channel coding and routing cannot be separated); that optimal processing is a function of the particular set of channel parameters and not only of the network topology; and that there exists a connection between linear codes and routing for a special class of graphs.
8. and , Silence is golden and time is money: power-aware communication for sensor networks, in 43rd Annual Allerton Conference on Communication, Control, and Computing, University of Illinois, Urbana-Champaign, USA, 2005
Citation: BibTeX RIS

### 2004

1. and , A Connection between Network Coding and Convolutional Codes, ICC, 2004
Citation: BibTeX RIS
The min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by liner re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. In this paper we discuss connections between such coding schemes and convolutional codes. We propose a method to simplify the convolutionalencoder design that is based on a subtree decompositionof the network line graph, describe the structure of the associated matrices, investigate methods to reduce decoding complexity and discuss possible binary implementation.
2. and , Decentralized Network Coding, Information Theory Workshop, 2004
Citation: BibTeX RIS
This paper proposes deterministic algorithms for decentralized network coding. Decentralized coding allows to locally specify the coding operations at network nodes without knowledge of the overall network topology, and to accommodate future changes in the network such as addition of receivers. To the best of our knowledge, these are the first deterministic decentralized algorithms proposed for network coding.
3. , and , Network Coding as a Coloring Problem, CISS, 2004
Citation: BibTeX RIS
We consider a multicast configuration with two sources, and translate the network code design problem to vertex coloring of an appropriately defined graph. This observation enables to derive code design algorithms and alphabet size bounds, as well as establish a connection with a number of well-known results from discrete mathematics that increase our insight in the different trade-offs possible for network coding.
4. and , On Average Throughput Benefits for Network Coding, Allerton, 2004
Citation: BibTeX RIS
We calculate the average throughput benefit that network coding can offer as compared to routing for different classes of multicast configurations over directed graphs. The averaging is over the throughput each individual receiver experiences. For the cases we examine, network coding at most doubles the average throughput.
5. , and , On the Throughput of Ad-Hoc Networks using Connectivity Graphs, in 42nd Annual Allerton Conference on Communication, Control, and Computing, University of Illinois, Urbana-Champaign, USA, 2004
Citation: BibTeX RIS
In this paper we propose a set of necessary and sufficient conditions under which the throughput in an ad-hoc network can remain constant as the number of nodes n increases. Throughput refers to the minimum achievable rate between a source-destination pair for a given routing mechanism and physical model, when the network is shared by \Theta(n) randomly chosen source-destination pairs. The main idea is to use a connectivity graph, that does not represent the actual physical network, but rather the available communication resources.
6. and , Processing along the way: forwarding vs. coding, ISITA, Parma, 2004
Citation: BibTeX RIS
We consider a source that transmits to a receiver by routing the information packets over a communication network and examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that the processing capabilities of the intermediate nodes affect not only the end-to-end achievable rate, but also the optimal routing strategy. For example, there exist network configurations where the maximal throughput is achieved only by coding across independent information streams.
7. and , Subtree Decomposition for Network Coding, ISIT, 2004
Citation: BibTeX RIS
We propose a subtree decomposition method for network coding. This approach enables derivation of tight bounds on the network code alpha- bet size, makes connections with convolutional codes transparent, allows specification of coding operations at network nodes without the knowledge of the overall network topology, and facilitates design of codes which can easily accommodate future changes in the network, such as addition of receivers and loss of links.

### 2003

1. , and , Training-based channel estimation for multiple-antenna broadband transmissions, IEEE Transactions on Wireless Communications, vol. 2, no. 2, 2003
Citation: BibTeX RIS
This paper addresses the problem of training sequence design for multiple-antenna transmissions over quasi-static frequency-selective channels. To achieve the channel estimation minimum mean square error, the training sequences transmitted from the multiple antennas must have impulse-like auto correlation and zero cross correlation. We reduce the problem of designing multiple training sequences to the much easier and well-understood problem of designing a single training sequence with impulse-like auto correlation. To this end, we propose to encode the training symbols with a space-time code, that may be the same or different from the space-time code that encodes the information symbols.

### 2002

1. , and , Effect of Spatio-Temporal Channel Correlation on the Performance of Space-Time Codes, ICC 2002, NY, vol. 2, 2002
Citation: BibTeX RIS
The determinant and rank criteria used for space-time code design apply at high SNR. Code design metrics developed for low SNR assume a channel autocorrelation matrix with equal eigenvalues, which does not hold in many practical scenarios. This paper shows that a space-time code designed to ensure full diversity at high SNR can suffer significant degradation when implemented at low-to-medium SNR because of the channel autocorrelation profile. We examine the effect of the channel autocorrelation matrix on a space-time code's performance and discuss how knowledge of this matrix can be used for code design, particularly from the aspect of space-time trellis code minimum memory requirements. Our discussion applies to both flat-fading and frequency-selective channels that are treated in a unified manner.
2. , and , Finite-Alphabet Constant-Amplitude Training Sequences for Multiple-Antennas, ICC 2002, NY, vol. 25, no. 1, 2002
Citation: BibTeX RIS
We propose a method to identify training sequences for multiple-antenna transmissions over quasi-static frequency-selective channels. These sequences are constructed to belong to a standard constant-amplitude 2m-PSK constellation (such as BPSK, QPSK etc) to simplify the transmitter/receiver implementation. Many practical systems use training of predetermined length. Optimal sequences do not exist for all training sequence lengths and constellation alphabets. The proposed method allows us to identify training sequences that belong to a standard constellation for an arbitrary training sequence length and an arbitrary number of unknown channel taps. Performance bounds derived indicate that these sequences achieve near-optimum performance.
3. and , How to choose the number of taps in a DFE?, CISS 2002, 2002
Citation: BibTeX RIS
In this paper, we address the following problem. Given a fixed total number of feedforward and feedback filter taps in a decision feedback equalizer, what is the optimum number of taps of each filter and what is the optimum delay setting? We propose a simple algorithm that resudes the solution search space from being two-dimensional to one-dimensional at a small performance loss. We demosntrate the application of our algorithm for indoor wireless channels.
4. , , and , Multi-Input Multi-Output Fading Channel Tracking and Equalization using Kalman Estimation, IEEE Transactions on Signal Processing, vol. 50, 2002
Citation: BibTeX RIS
This paper addresses the problem of channel tracking and equalization for multi-input multi-output (MIMO) time-varying frequency-selective channels. These channels model the effects of inter-symbol interference (ISI), co-channel interference (CCI), and noise. A low-order autoregressive model approximates the MIMO channel variation and facilitates tracking via a Kalman filter. Hard decisions to aid Kalman tracking come from a MIMO finite-length minimum-mean-squared-error decision-feedback equalizer (MMSE-DFE), which performs the equalization task. Since the optimum DFE for a wide range of channels produces decisions with a delay ~ > 0, the Kalman filter tracks the channel with a delay. A channel prediction module bridges the time gap between the channel estimates produced by the Kalman filter and those needed for the DFE adaptation. The proposed algorithm offers good tracking behavior for multiuser fading ISI channels at the expense of higher complexity than conventional adaptive algorithms. Applications include synchronous multiuser detection of independent transmitters, as well as coordinated transmission through many transmitter/receiver antennas, for increased data rate.
5. , , and , Prefiltered M-BCJR Equalizer for MIMO Frequency-Selective Channels, IEEE Transactions on Communications, vol. 50, no. 5, 2002
Citation: BibTeX RIS
This paper addresses the problem of soft equalization for space-time-coded transmissions over frequency-selective fading channels. The structure of the space-time code is embedded in the channel impulse response for efficient joint equalization and decoding. The proposed equalization/decoding approach uses a prefilter to concentrate the effective channel power in a small number of taps followed by a reduced-complexity maximum a posteriori probability (MAP) equalizer/decoder to produce soft decisions. The prefilter introduces residual intersymbol interference which degrades the performance of MAP when applied to the trellis of the shortened channel. However, the shape of the overall shortened channel impulse response allows the M-algorithm to approximate the prefiltered MAP performance with a small number of states. Based on this general framework, we investigate several enhancements such as using different prefilters for the forward and backward recursions, concatenating two trellis steps during decoding, and temporal oversampling. The performance is evaluated through simulations over the EDGE typical urban channel.
6. , and , Reduced-Complexity Training Schemes for Multiple-Antenna Broadband Transmissions, WCNC 2002, vol. 3, 2002
Citation: BibTeX RIS
This paper addresses the problem of training sequence design for multiple-antenna transmissions over quasi-static frequency-selective channels. As performance metric for channel estimation, mean square error is adopted. To achieve the minimum mean square error, the training sequences transmitted from the multiple antennas must have impulse-like auto-correlation and zero cross-correlation. We reduce the problem of designing multiple training sequences to the much easier and well-understood problem of designing a single training sequence with impulse-like auto-correlation. To this end, we propose to encode the training sequences with a space-time code, that may be the same or different from the space-time code that encodes the information symbols. Designing one instead of multiple training sequences reduces the search space significantly and simplifies the construction of optimal or suboptimal training sequences.
7. and , Serially concatenated coding for broadcasting S-UMTS applications, IEEE Seventh International Symposium on Spread Spectrum Techniques and Applications, vol. 3, 2002
Citation: BibTeX RIS
Satellite-UMTS supports broadcast applications that involve transmission of the same encoded data over channels that may vary significantly. The same code must allow a user with a good channel to recover the information with low complexity, while a user with a bad channel should still be able to achieve an acceptable BER at the cost of increased complexity and/or decoding delay. To this end, we propose serially concatenated multilevel code structures that employ PSK modulation. The receiver has the flexibility to achieve turbo-code, trellis-code or uncoded performance, depending on the decoding effort. Design considerations include the constituent encoder design and the use of a non-uniform constellation. Simulation results investigate the system's performance and highlight different parameters trade-offs.
8. , , , and , Space-Time Coding for Broadband Wireless Transmission, IEEE Communications Magazine issue Technologies for 3G and Beyond'', vol. 40, no. 9, 2002
Citation: BibTeX RIS
We present an overview of research activities on space-time coding for broadband wireless transmission performed at AT&T Shannon Laboratory over the past two years. The emphasis is on physical layer modem algorithms such as channel estimation, equalization, and interference cancellation. However, we also discuss the impact of space-time coding gains at the physical layer on throughput at or above the networking layer. Furthermore, we describe a flexible graphical user interface attached to our physical layer simulation engine in order to explore the performance of space-time codes under a variety of practical transmission scenarios. Simulation results for the EDGE cellular system and the 802.11 wireless LAN environment are presented.
9. and , Symbol-Interleaved Serially Concatenated Turbo Codes, CISS 2002, 2002

Citation: BibTeX RIS

### 2001

1. and , Bit vs. Symbol Interleaving for Parallel Concatenated Trellis Coded Modulation, GlobeCom, vol. 2, 2001
Citation: BibTeX RIS
This paper compares bit versus symbol interleaving for parallel-concatenated trellis-coded turbo codes, employing the turbo encoder structure proposed in Benedetto et al., (1996). To compare systems optimized with the same techniques, the paper extends the turbo-encoder design procedure proposed in Fragouli et al. (2001), to bit-interleaved systems. We discuss a method to jointly design the multiple required interleavers for the bit-interleaved system, and a procedure to select constituent encoders that can take advantage of the interleaver structure to achieve a low error floor. Simulation results for the designed bit-interleaved system show better performance than bit-interleaved performance reported in the literature. The symbol-interleaved system though achieves an earlier convergence, especially with an increased number of decoder iterations, but at the cost of a slightly higher error floor.
2. , and , Minimality for puncturing convolutional codes, ICC 2001, Helsinki, Finland, June, vol. 1, 2001
Citation: BibTeX RIS
This paper investigates encoders optimization for the Hamming weight after periodic puncturing, and discusses minimality issues that may affect the performance of the punctured encoders. Periodically puncturing a minimal encoder produces a higher rate encoder that may or may not be minimal. If it is not minimal, it may have a zero-output loop and it may be catastrophic. A code search can use a fast algorithm to determine whether an encoder's state diagram has a zero-output loop under periodic symbol puncturing, and a proposed method to assess the performance of codes with a zero-output loop that are not catastrophic. As an example, the paper optimizes rate-1/4 unpunctured codes for Hamming weight under both bit-wise and symbol-wise periodic puncturing. Code tables and simulation results are included.
3. , , and , Prefiltered space-Time M-BCJR Equalizer for MIMO Frequency-Selective Channels, CISS, 2001
Citation: BibTeX RIS
This paper addresses the problem of soft equalization for time-variant frequency-selective channels. Such a channel arises in EDGE (Enhanced Data for GSM Evolution), third generation TDMA proposal, which employs 8-PSK modulation with a linearized GMSK pulse shaping filter that introduces strong intersymbol interference. The proposed equalization approach uses a prefilter to concetrate the effective channel power in a small number of taps, followed by a reduced complexity MAP equalizer to produce soft decision outputs. The MAP equalizer is based on the implementation of the M-algorithm in the log domain. The prefilter introduces residual intersymbol interference which degrades the performance of MAP when applied to the trellis of the shortened channel. However, the shape of the overall shortened channel impulse response allows the M-algorithm to approximate the prefiltered MAP performance with a small number of states. Based on this general framework, we investigate several enhancements, such as using a different prefilter for the forward and backward recursion, concatenating two trellis steps during decoding, and temporal oversampling. The performance is evaluated through simulations over the typical urban (TU) EDGE channel.
4. , and , Reduced-trellis equalization using a variation of the M-BCJR algorithm, Journal on Wireless Communications and Mobile Computing, vol. 1, 2001

Citation: BibTeX RIS
5. , , and , Turbo Codes with Non-Uniform Constellation, ICC 2001, Helsinki, Finland, vol. 1, 2001
Citation: BibTeX RIS
This paper presents parallel concatenated turbo codes that employ a non-uniform constellation to achieve shaping gain. The output signal approximates the Gaussian distribution by using equally likely signals with unequal spacing (a non-uniform constellation). The small distance of points near the center of the constellation may lead to a small overall free distance and thus a high error floor for turbo codes. We avoid this situation by a two-step design procedure, that first creates an interleaver, and then identifies the constituent encoders that maximize the turbo code free distance. Simulation results for 4 bits/sec/Hz show that this use of shaping can offer an improvement of approximately 0.2 dB for turbo codes.
6. and , Turbo encoder design for symbol interleaved parallel concatenated trellis coded modulation, IEEE Transactions on Communications, no. 3, vol. 49, 2001
Citation: BibTeX RIS
This paper addresses turbo-encoder design for coding with high spectral efficiency using parallel concatenated trellis-coded modulation and symbol interleaving. The turbo-encoder design involves the constituent encoder design and the interleaver design. The constituent encoders are optimized for symbol-wise effective free distance, and each has an infinite symbol-wise impulse response. We identify the canonical structures for the constituent encoder search space. In many cases of practical interest, the optimal structure for these constituent encoders connects the memory elements in a single row. This single row generally applies to turbo code constituent encoders for parallel concatenation and is not restricted to symbol interleaving. To lower the error floor, a new semi-random interleaver design criteria and a construction method extends the spread-interleaver concept introduced by Divsalar and Pollara (1995). Simulation results show that the proposed system employing symbol interleaving can converge at a lower signal-to-noise ratio than previously reported systems. We report simulation results between 0.5 and 0.6 db from constrained capacity for rates of 2 and 4 bits/s/Hz.

### 2000

1. , , and , Adaptive Multi-Input Multi-Output Fading Channel Equalization using Kalman Estimation, ICC 2000, New Orleans, Louisiana, June 18-22, vol. 3, 2000
Citation: BibTeX RIS
This paper addresses the problem of adaptive channel tracking and equalization for multi-input multi-output (MIMO) time-variant frequency-selective channels. A finite-length minimum-mean-squared-error decision-feedback equalizer (MMSE-DFE) performs the equalization task, while a Kalman filter tracks the MIMO channel, which models the corrupting effects of inter-symbol interference (ISI), inter-user interference (IUI), and noise. The Kalman tracking is aided by previous hard decisions produced by the DFE, with a decision delay ~>0, which causes the Kalman filter to track the channel with a delay. A channel prediction module bridges the time gap between the channel estimates produced by the Kalman filter and those needed for the DFE adaptation. The proposed algorithm offers good tracking behavior for multi-user fading ISI channels at the expense of higher complexity.
2. , and , On reduced trellis equalization using the M-BCJR Algorithm, in CISS, Boston, 2000
Citation: BibTeX RIS
The complexity of channel equalization using the BCJR algorithn [1] grows exponentially with the channel memory. The M-BCJR algorithm [2], provides a method for reduced-trellis channel equalization. This paper examines the algorithm performance for different finite impulse response channels, identifies pathological cases, and introduces designer choices such as the decision delay, maximum and minimum phase transformation, and selection of states used by the algorithm. Simulation results demonstrate the effect of the different parameters in the algorithm's performance.

### 1999

1. , , and , Channel estimation and equalization in fading, 33rd Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, October 24-27, 1999
Citation: BibTeX RIS
This paper addresses the problem of training sequence design for multiple-antenna transmissions over quasi-static frequency-selective channels. To achieve the channel estimation minimum mean square error, the training sequences transmitted from the multiple antennas must have impulse-like auto correlation and zero cross correlation. We reduce the problem of designing multiple training sequences to the much easier and well-understood problem of designing a single training sequence with impulse-like auto correlation. To this end, we propose to encode the training symbols with a space-time code, that may be the same or different from the space-time code that encodes the information symbols. Optimal sequences do not exist for all training sequence lengths and constellation alphabets. We also propose a method to easily identify training sequences that belong to a standard 2m-PSK constellation for an arbitrary training sequence length and an arbitrary number of unknown channel taps. Performance bounds derived indicate that these sequences achieve near-optimum performance.
2. and , Convolutional codes and matrix control theory, Proceedings of the 7th International Conference on Advances in Communications and Control, June 28-July 2, Athens, Greece., 1999

Citation: BibTeX RIS
3. and , Semi-random interleaver design criteria, Communication Theory Symposium at Globecom 99, Rio de Janeiro, Brazil, December 5-9, 5, 1999
Citation: BibTeX RIS
A spread interleaver of length N is a semi-random interleaver based on the random selection without replacement of N integers from 1 to N under a design constraint. This paper extends the spread-interleaver design method to multiple error events, based on the interleaver's role in overall turbo code error event distances. The extension helps to explain why the spread interleaver is specifically designed to be semi-random. Simulation results show the performance achieved for a symbol-interleaved parallel concatenated trellis coded modulation (PCTCM) scheme.
4. and , Symbol interleaved parallel concatenated trellis coded modulation, Communication Theory Miniconference in conjunction with ICC '99, June 6-10 1999, 1999
Citation: BibTeX RIS
This paper presents a method for efficient coding at high spectral efficiency using parallel concatenated trellis coded modulation (PCTCM) with symbol interleaving. The constituent encoders are optimized for symbol-wise free distance, and each has an infinite symbol-wise impulse response. In many cases of practical interest, the optimal structure for these constituent encoders connects the memory elements in a single row. Simulation results show that the performance is as close as 0.5 dB to the constrained capacity.