Network Coding Theory (Now Publishing)

×

Network Coding Theory (Now Publishing)

Close

«Network Coding Theory»
ENGLISH | Author(s): R. W. Yeung et al. | Publisher: Now Publisher | ISBN: 1-933019-24-7 | Release Date: June 2006 | Pages: 155 | File Type: PDF | File Size: 15.0 MB (UNCOMPRESSED)

Title: Network Coding Theory
Author(s): R. W. Yeung et al.
Publisher: Now Publisher
ISBN: 1-933019-24-7
Release Date: June 2006
Pages: 155
File Type: PDF
File Size: 15.0 MB (UNCOMPRESSED)

Introduction

Consider a network consisting of point-to-point communication channels. Each channel transmits information noiselessly subject to the channel capacity. Data is to be transmitted from the source node to a prescribed set of destination nodes. Given the transmission requirements, a natural question is whether the network can fulfill these requirements and how it can be done efficiently.

In existing computer networks, information is transmitted from the source node to each destination node through a chain of intermediate nodes by a method known as store-and-forward. In this method, data packets received from an input link of an intermediate node are stored and a copy is forwarded to the next node via an output link. In the case when an intermediate node is on the transmission paths toward multiple destinations, it sends one copy of the data packets onto each output link that leads to at least one of the destinations. It has been a folklore in data networking that there is no need for data processing at the intermediate nodes except for data replication.

Recently, the fundamental concept of network coding was first introduced for satellite communication networks in [211] and then fully developed in [158], where in the latter the term “network coding” was coined and the advantage of network coding over store-and-forward was first demonstrated, thus refuting the aforementioned folklore. Due to its generality and its vast application potential, network coding has generated much interest in information and coding theory, networking, switching, wireless communications, complexity theory, cryptography, operations research, and matrix theory.

Table of Contents

1 Introduction 1

1.1 A historical perspective 1
1.2 Some examples 4

I SINGLE SOURCE 9

2 Acyclic Networks 11
2.1 Network code and linear network code 12
2.2 Desirable properties of a linear network code 18
2.3 Existence and construction 25
2.4 Algorithm refinement for linear multicast 40
2.5 Static network codes 44

3 Cyclic Networks 51
3.1 Non-equivalence between local and global descriptions 52
3.2 Convolutional network code 55
3.3 Decoding of convolutional network code 67

4 Network Coding and Algebraic Coding 73
4.1 The combination network 73
4.2 The Singleton bound and MDS codes 74
4.3 Network erasure/error correction and error detection 76
4.4 Further remarks 77

II MULTIPLE SOURCES 79

5 Superposition Coding and Max-Flow Bound 81
5.1 Superposition coding 82
5.2 The max-flow bound 85

6 Network Codes for Acyclic Networks 87
6.1 Achievable information rate region 87
6.2 Inner bound Rin 91
6.3 Outer bound Rout 107
6.4 RLP – An explicit outer bound 111

7 Fundamental Limits of Linear Codes 117
7.1 Linear network codes for multiple sources 117
7.2 Entropy and the rank function 119
7.3 Can nonlinear codes be better asymptotically? 122

Appendix A Global Linearity versus Nodal Linearity 127

Acknowledgements 133

References 135