Foundations and Trends® in
Communications and Information Theory
Raymond Yeung, S.-Y.R. Li, N. CaiandZ.Zhang
 |
| Foundations and Trends® in Communications and Information Theory |
Raymond W. Yeung
The Chinese University of Hong Kong
Hong Kong, China
whyeung@ie.cuhk.edu.hk
Shuo-Yen Robert Li
The Chinese University of Hong Kong
Hong Kong, China
bob@ie.cuhk.edu.hk
Ning Cai
Xidian University
Xi’an, Shaanxi, China
caining@mail.xidian.edu.cn
Zhen Zhang
University of Southern California
Los Angeles, CA, USA
zzhang@milly.usc.edu
Introduction
1.1 A historical perspective
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.
Prior to [211] and [158], network coding problems for special networks
had been studied in the context of distributed source coding
[207][177][200][212][211]. The works in [158] and [211], respectively,
have inspired subsequent investigations of network coding with a single
information source and with multiple information sources. The theory
of network coding has been developed in various directions, and new
applications of network coding continue to emerge. For example, network
coding technology is applied in a prototype file-sharing application
[176]1. For a short introduction of the subject, we refer the reader
to [173]. For an update of the literature, we refer the reader to the
Network Coding Homepage [157].
The present text aims to be a tutorial on the basics of the theory of
network coding. The intent is a transparent presentation without necessarily
presenting all results in their full generality. Part I is devoted to
network coding for the transmission from a single source node to other
nodes in the network. It starts with describing examples on network
coding in the next section. Part II deals with the problem under the
more general circumstances when there are multiple source nodes each
intending to transmit to a different set of destination nodes.
Compared with the multi-source problem, the single-source network
coding problem is better understood. Following [188], the best possible
benefits of network coding can very much be achieved when the
coding scheme is restricted to just linear transformations. Thus the
tools employed in Part I are mostly algebraic. By contrast, the tools
employed in Part II are mostly probabilistic.
While this text is not intended to be a survey on the subject,
we nevertheless provide at <http://dx.doi.org/10.1561/0100000007>
1 See [206] for an analysis of such applications.
1.1. A historical perspective 3
a summary of the literature (see page 135) in the form of a table according
to the following categorization of topics:
1. Linear coding
2. Nonlinear coding
3. Random coding
4. Static codes
5. Convolutional codes
6. Group codes
7. Alphabet size
8. Code construction
9. Algorithms/protocols
10. Cyclic networks
11. Undirected networks
12. Link failure/Network management
13. Separation theorem
14. Error correction/detection
15. Cryptography
16. Multiple sources
17. Multiple unicasts
18. Cost criteria
19. Non-uniform demand
20. Correlated sources
21. Max-flow/cutset/edge-cut bound
22. Superposition coding
23. Networking
24. Routing
25. Wireless/satellite networks
26. Ad hoc/sensor networks
27. Data storage/distribution
28. Implementation issues
29. Matrix theory
30. Complexity theory
31. Graph theory
32. Random graph
33. Tree packing
4 Introduction
34. Multicommodity flow
35. Game theory
36. Matriod theory
37. Information inequalities
38. Noisy channels
39. Queueing analysis
40. Rate-distortion
41. Multiple descriptions
42. Latin squares
43. Reversible networks
44. Multiuser channels
45. Joint network-channel coding
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.
Prior to [211] and [158], network coding problems for special networks
had been studied in the context of distributed source coding
[207][177][200][212][211]. The works in [158] and [211], respectively,
have inspired subsequent investigations of network coding with a single
information source and with multiple information sources. The theory
of network coding has been developed in various directions, and new
applications of network coding continue to emerge. For example, network
coding technology is applied in a prototype file-sharing application
[176]1. For a short introduction of the subject, we refer the reader
to [173]. For an update of the literature, we refer the reader to the
Network Coding Homepage [157].
The present text aims to be a tutorial on the basics of the theory of
network coding. The intent is a transparent presentation without necessarily
presenting all results in their full generality. Part I is devoted to
network coding for the transmission from a single source node to other
nodes in the network. It starts with describing examples on network
coding in the next section. Part II deals with the problem under the
more general circumstances when there are multiple source nodes each
intending to transmit to a different set of destination nodes.
Compared with the multi-source problem, the single-source network
coding problem is better understood. Following [188], the best possible
benefits of network coding can very much be achieved when the
coding scheme is restricted to just linear transformations. Thus the
tools employed in Part I are mostly algebraic. By contrast, the tools
employed in Part II are mostly probabilistic.
While this text is not intended to be a survey on the subject,
we nevertheless provide at <http://dx.doi.org/10.1561/0100000007>
1 See [206] for an analysis of such applications.
1.1. A historical perspective 3
a summary of the literature (see page 135) in the form of a table according
to the following categorization of topics:
1. Linear coding
2. Nonlinear coding
3. Random coding
4. Static codes
5. Convolutional codes
6. Group codes
7. Alphabet size
8. Code construction
9. Algorithms/protocols
10. Cyclic networks
11. Undirected networks
12. Link failure/Network management
13. Separation theorem
14. Error correction/detection
15. Cryptography
16. Multiple sources
17. Multiple unicasts
18. Cost criteria
19. Non-uniform demand
20. Correlated sources
21. Max-flow/cutset/edge-cut bound
22. Superposition coding
23. Networking
24. Routing
25. Wireless/satellite networks
26. Ad hoc/sensor networks
27. Data storage/distribution
28. Implementation issues
29. Matrix theory
30. Complexity theory
31. Graph theory
32. Random graph
33. Tree packing
4 Introduction
34. Multicommodity flow
35. Game theory
36. Matriod theory
37. Information inequalities
38. Noisy channels
39. Queueing analysis
40. Rate-distortion
41. Multiple descriptions
42. Latin squares
43. Reversible networks
44. Multiuser channels
45. Joint network-channel coding
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
Screenshot
Purchase Now !
Just with Paypal
Just with Paypal
Product details
Price
|
|
|---|---|
Pages
| 155 p |
File Size
|
15,393 KB |
File Type
|
PDF format |
ISBN
| 1-933019-24-7 |
Copyright
| 2006 R.W. Yeung, S.-Y.R. Li, N. Cai, and Z. Zhang |
●▬▬▬▬▬❂❂❂▬▬▬▬▬●
●▬▬❂❂▬▬●
●▬❂▬●
●❂●
═════● ●═════
