THESIS
2013
xiii, 68 pages : illustrations ; 30 cm
Abstract
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.
Post a Comment