Network coding can greatly improve network throughput and performance by allowing coding at the intermediate nodes. For communication network employing linear network coding, the network nodes create new packets by taking (random) linear combinations of the packets they have, resulting in the so called linear operator channel (LOC). A natural question to ask is: What is the capacity of the LOC?

In this thesis, we first study the sparse LOC whose channel matrix is sparse. By investigating the cardinality of the null space of the sparse LOC matrix, a lower bound on the capacity of the sparse LOC is obtained. The linear rank distribution of the sparse LOC matrix is also calculated, which is then used to derive an upper bound on the capacity of the sparse LOC. Furthermore, the uppe...[ Read more ]

Network coding can greatly improve network throughput and performance by allowing coding at the intermediate nodes. For communication network employing linear network coding, the network nodes create new packets by taking (random) linear combinations of the packets they have, resulting in the so called linear operator channel (LOC). A natural question to ask is: What is the capacity of the LOC?

In this thesis, we first study the sparse LOC whose channel matrix is sparse. By investigating the cardinality of the null space of the sparse LOC matrix, a lower bound on the capacity of the sparse LOC is obtained. The linear rank distribution of the sparse LOC matrix is also calculated, which is then used to derive an upper bound on the capacity of the sparse LOC. Furthermore, the upper bound can be shown to be exact as the channel matrix size tends to infinity. Numerical results show our bounds are tight for various matrix sizes and sparsity.

The second part of this thesis investigates the subspace coding over the LOC with given rank distribution. Among all the LOCs with the same rank distribution, both the worst-case and the best-case channels are characterized, with the subspace coding capacity being the primary concern. The lower and upper bounds on the subspace coding capacity of LOC with given rank distribution are obtained, by calculating the subspace coding capacity of both the worst-case and the best-case channels. We further reduce the problems of calculating the subspace coding capacity of both the worst-case and the best-case channels to some convex optimization problems, which can be efficiently solved by numerical computation. Interestingly, many of the existing channel models such as the purely random model, the uniform full rank model, the uniform given rank model and the column-space symmetric model, are all special cases of the worst-case channels. Therefore our lower bound gives the exact value of the capacity of such channels. Moreover, our lower and upper bounds coincide, as the packet size tends to infinity. Numerical results show our bounds are tighter than the existing bounds, especially for small to moderate packet sizes.