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.
This 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.
This 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.
Following are the few topics covered in this Network coding book.
- Linear coding
- Nonlinear coding
- Random coding
- Static codes
- Convolutional codes
- Group codes
- Alphabet size
- Code construction
- Algorithms/protocols
- Cyclic networks
- Undirected networks
- Link failure/Network management
- Separation theorem
- Error correction/detection
- Cryptography
- Multiple sources
- Multiple unicasts
- Cost criteria
- Non-uniform demand
- Correlated sources
- Max-flow/cutset/edge-cut bound
- Superposition coding
- Networking
- Routing
- Wireless/satellite networks
- Ad hoc/sensor networks
- Data storage/distribution
- Implementation issues
- Matrix theory
- Complexity theory
- Graph theory
- Random graph
- Tree packing
- Multicommodity flow
- Game theory
- Matriod theory
- Information inequalities
- Noisy channels
- Queueing analysis
- Rate-distortion
- Multiple descriptions
- Latin squares
- Reversible networks
- Multiuser channels
- Joint network-channel coding