Ph.D Thesis | |

Ph.D Student | Yohananov Lev |
---|---|

Subject | Codes Over Graphs |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Eitan Yaakobi |

Full Thesis text |

In this work, *codes over graphs* are studied. A code
over graphs is a set of complete *graphs* with self-loops with a fixed
number of nodes *n*. Every graph-codeword in such codes stores the
information symbols over some alphabet ⅀ on its edges. If a code over
graphs contains only directed, undirected complete graphs with self-loops, then
it is called a *directed, undirected code over graphs*, respectively. The
number of edges in every codeword of the directed, undirected codes over graphs
is *n ^{2}*,

Another family of codes, called *codes over trees*, is
studied. A code over trees is a set of *undirected trees* with a fixed
number of nodes. Every tree-codeword corresponds to unique information which is
given by the structure of the tree-codeword. These codes are constructed to
tolerate any *ρ* edge erasures, which transform a tree into a forest
with *ρ* sub-trees. The *tree distance* between two trees is
the number of edges that belong to exactly one tree. Studying this distance
measure is important for many applications that use trees and properties on
their locality and the number of neighbor trees. The largest size of codes over
trees with a prescribed minimum tree distance is investigated. In addition,
upper bounds, several constructions, and decoding schemes are presented.

The last work of this thesis studies *functional k-batch*
codes. A functional *k*-batch code of length *n *and dimension *s*
encodes *s* information bits *x*_{0}*,x*_{1}*,?,x _{s}*