Network Coding Theory

venessa724

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
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
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