Applications of graph theory to error correcting codes

Abstract

ÖZET GRAF TEORİSİNİN HATA DÜZELTEN KODLARA UYGULANMASI Graf teorisinin başta kombinatorik olmak üzere birçok değişik alanda uygulamaları bulunmaktadır. Bu çalışmada, graflar yardımı ile hata düzelten kodlar elde etmek için geliştirilen bazı metodları araştırıyoruz. İlk olarak bir grafın döngü ve kesen küme uzaylarından elde edilen kodlar üzerinde duruluyor. Kodlar kurulduktan ve hata düzeltme algoritmaları verildikten sonra, bu kodların boyutlarının arttırılması ile ilgili metodlar inceleniyor. Son olarak bu yeni elde edilen kodların hata düzeltme algoritmaları veriliyor. İncelenen ikinci method kübik düzlemsel iki parçalı graflardan kendi duali olan kodlar elde edilmesidir. Son olarak mükemmel tek hata düzelten kodlar elde etmek için geliştirilmiş bir metod inceleniyor. Bunun için Hanoi Kulesi probleminden yola çıkarak oluşturulmuş bazı graflar kullanılmıştır.

IV ABSTRACT APPLICATIONS OF GRAPH THEORY TO ERROR CORRECTING CODES Graph Theory has applications in many different fields, especially in combinatorics. In this study, we investigate the methods developed for obtaining error-correcting codes using graphs. First, the codes obtained from cycle and cut-set spaces of a graph are considered. After constructing the codes and giving the decoding schemes, methods for increasing the dimensions of these codes are examined. Then decoding schemes for these new codes are given. Next, a method for obtaining self-dual codes using cubic planar bipartite graphs is examined. The last method covered is to obtain perfect one error-correcting codes using some graphs that are constructed from the Tower of Hanoi Puzzle.