Hücresel dönüşümlerle hata düzelten kodlar

Abstract

1948 yılında yayınladığı çalışmasında Claude E. Shannon ilk kez gürültülü bir kanal üzerinden yapılan iletişim için kanal kapasitesi denilen bir kavram ortaya koydu. Shannon, eğer uygun kodlama ve dekodlama teknikleri kullanılırsa kanal kapasitesinin altında herhangi bir oranda güvenli iletişimin teorik olarak mümkün olduğunu kanıtladı. Ancak Shannon bahsedilen uygun kodlama ve dekodlama algoritmalarına ilişkin herhangi bir metot önermiyordu. Richard W. Hamming 1950 yılında Shannon'ın varlığını kanıtladığı uygun kodlama ve dekodlama yeteneğine sahip ilk kod ailesini buldu. Aynı yıl Golay tarafından da bir kod ailesi keşfedildi. Sırasıyla Hamming ve Golay kodları olarak bilinen bu iki kod ailesi (lineer blok kod) bilinen ilk hata düzelten optimal kodlardır.Hata düzelten kodlar dijital iletişim, haberleşme uyduları, uzay araştırmaları, dijital bilgi depolama gibi birçok alanda yaygın olarak kullanılmaktadır. Bu kodlama tekniğinin temel amacı herhangi bir bilgi kodlandıktan sonra gerek iletim esnasında gerekse depolanan bilginin geri çağrılması esnasında oluşabilecek hataları belli şartlar altında fark etmek ve hatta düzeltmektir. Bunun için temel olarak bilgi bitlerine belli sayıda kontrol bitleri eklenmektedir. Hücresel dönüşümlerle hata düzelten kodların da temel amacı diğer hata düzelten kodlarda olduğu gibi Shannon kapasitesine yakın kodlama ve dekodlama yapabilen verimli algoritmalar geliştirmektir.Bu çalışmada ilk olarak hücresel dönüşümler ve hücresel dönüşümlerle hata düzelten kodların tarihçesi hakkında bilgi verilmiştir. İkinci bölümde hücresel dönüşümlerle ilgili bilgiler zaman zaman ayrıntılı sayılabilecek biçimde sunulmuştur. Üçüncü bölümde hata düzelten kodlar ile ilgili gerekli bilgiler sıralandıktan sonra literatürde yapılan çalışmalar sunulmuştur. Dördüncü bölümde ise daha önce ikili cisim üzerinde yapılmış olan çalışmalar F_q ilkel cisimleri üzerine genellenmiştir. Son bölüm ise sonuç ve önerilere ayrılmıştır.

In the paper published in 1948, Claude E. Shannon for the first time revealed the concept of communication through a noisy channel called channel capacity. Shannon proved that if suitable encoding and decoding techniques were used, then reliable communication theoretically could be possible at any rate below the channel capacity. However, Shannon didn?t come up with any method for the suitable encoding and decoding techniques. In 1950, Richard W. Hamming found the first code family which had suitable encoding and decoding ability the existence of which had been proved by Shannon. In the same year, a code family was also discovered by Golay. These two code families (linear block codes), known as the Hamming and Golay codes, respectively, are the first known optimal error correcting codes.Error correcting codes are widely used in many areas such as digital communication, communication satellites, space research, and storage of digital information. The main objective of the coding technique is to detect possible errors that may occur and even correct them under certain conditions, when any information has been encoded both during transmission and retrieval of information stored. Towards this end, basically certain number of check bits are added to the information bits. The main objective of the cellular automata based error correcting codes, similar to classical error correcting codes, is to develop effective algorithms which have an encoding and decoding capacity close to that of Shannon.In this thesis, information about the history of cellular automata and cellular automata based error correcting codes is given first. In the second section, further information regarding cellular automata is introduced and some concepts are also studied in detail. In the third section after covering the information required for error correcting codes, recent studies in the literature are presented. The fourth section contains the generalization to primitive finite fields F_q of an original study made on binary fields. The last section is reserved for the conclusions and future research directions.