Skip to main content
SUPERVISOR
Morteza Esmaeili
مرتضی اسمعیلی (استاد راهنما)
 
STUDENT
Marzieh Omidi Salmi
مرضیه امیدی سلمی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1392

TITLE

Matroidal characterization of optimal linear network codes over cyclic networks
Network coding is an important subject in the application of networks and was raised first by Ahlswede in 2000 . In a network coding , the intermediate nodes have the ability of applying some process on their received data . In fact these nodes have the ability to encode the information received from their input edges and then transmit the encoded data . Li et . al . in 2003 showed that if in a network instead of just routing data , an appropriate coding is used the capacity of network is increased; they also showed that linear coding is sufficient to achieve the optimal transmission rate which is the maximum flow from the source node to the destination nodes . \\\\ A linear network code is called optimal if it achieves the capacity of multicast transmission which has few different interpretations , one of which is the existence of capability of recovering transmitted message from the source node at each sink node , and another interpretation is achieving transmission rate equal to the network's max-flow by every sink node . All of these are related to the linear independence of coding vectors of some specific edges of the underlying network.\\\\ A matroid is a set with an independent structure on its elements . It has been shown in recent years , that matroid concept has many applications in network coding . In 2008 , Sun et . al . studied matroid structure of the edge set of a network and showed that the path independent sets in a given network form a matroid which is called network matroid . On the other hand , in a linear network code a coding vector is assigned to each edge; it can be shown that the linear independence among coding vectors creates a matroid . It has been shown that in the case of generic linear network codes on acyclic networks these two matroids are the same . \\\\ A related topic in network coding is known as variable-rate linear network coding , meaning that the source node in a network sends massages with different rates at different time units and each nonsource node recovers the massages according to its recovery potential . It is known that in the case of generic coding , if a set of generating edges of the network are removed , then the code restricted to the resulting reduced network remains generic.\\\\ In this thesis , initially we study different features of optimal linear network codes and then generalize that matroid characterization of optimal codes from acyclic network to cyclic network; this generalization is established on cyclic network in way quite different from that used in the case of acyclic network and by using a layering method which changes a cyclic network to an acyclic network , we extend the matroidal properties of acyclic networks to cyclic ones . We also extend the distribution variable-rate property of generic linear network codes from acyclic networks to cyclic networks.
یک کدشبکه خطی (LNC) بهینه نامیده می‌شود هرگاه ظرفیت انتقال چندپخشی را بدست آورد که این مفهوم معانی متعددی دارد که یک مورد آن کدگشایی پیام های ارسال شده از منبع در هر گره دریافتی درنظر گرفته شده است و دیگری بدست آوردن نرخ داده مساوی با بیش‌ترین جریان از منبع به هر گره است که همه این تعاریف به استقلال خطی بردارهای کدگذاری متناظر با یک مجموعه خاص از یال‌ها مربوط می‌شوند. روی یک شبکه‌ غیر‌دوری مشخصه‌ای از (LNC) کلی وجود دارد که انطباقی بین متروید مجموعه‌های مستقل خطی و متروید شبکه است و با ساختار مسیرهای یال-مجزای مناسب تعریف می‌شود. در این پایان نامه ابتدا به ویژگی‌های کدشبکه‌های خطی روی شبکه‌های غیردوری پرداخته می‌شود و بعد از آن با روش‌هایی متفاوت از آن‌چه در شبکه‌های غیر دوری به‌کار رفته است نشان داده‌ می‌شود ویژگی‌های مترویدی که روی شبکه‌های غیردوری برقرارند برای شبکه‌های دوری نیز برقرار هستند. همچنین خاصیت نرخ-متغیر بودن کدشبکه‌های خطی کلی روی شبکه‌های غیردوری به شبکه‌های دوری توسیع داده می‌شوند. کلمات کلیدی: شبکه‌های دوری، کدشبکه‌های ‌‌خطی، متروید، متروید شبکه.

ارتقاء امنیت وب با وف بومی