Katalog

Hayatın içindeki matematik (1) KODLAR KURAMI: Matematiğin yaşantımızdaki yeri ve önemi sorulduğunda çoğu kişi Matematiğin çok önemli olduğunu söyler de, bunları açıklamaya kalktığında, çok fazla şey söyleyemez. Sorunun yanıtı göründüğü kadar kolay değildir üstelik verilecek yanıtın soruyu soran kişinin bilgi ve kültür düzeyine de bağlıdır. Bu yazımızda, pek farkında olmasak da çağcıl yaşantımıza giren ve onu kolaylaştıran bir matematik dalından söz edeceğiz. Prof. Dr. Erol Balkanay (İstanbul Kültür Üniv.); Araş. Gör. Sinan Ataseven (İstanbul Kültür Üniversitesi) H CBT 1080 / 16 30 Kasım 2007 ayatın İçindeki Matematik, “Kodlar Kuramı”, Matematiğin çok genç bir dalıdır. 1948 yılında Claude Elwood Shannon'un (19162001) “İletişimin Matematiksel Kuramı” isimli makalesiyle doğdu. 1948'de Marsel Golay'ın “Dijital kodlama üzerine notlar” adlı, 1950 de Richard Hamming'in “Hata sezme ve hata düzeltme kodları” adlı çalışmaları Kodlama kuramının hızla gelişmesini sağladı. Kodlar kuramının (Kodlama Kuramı da denir) amacı, olumsuzluk taşıyan, elverişsiz ortamlarda bile bilgilerin (yazı, görüntü veya ses) güvenli, etkin ve kolay bir biçimde iletilmesini, depolanmasını veya kaydedilmesini sağlamaktır. Günümüzde iletişimin kolay, hızlı ve hatasız gerçekleştirilebilmesinin önemi, Matematiğin yeni bir dalı olan Kodlar kuramını ister istemez güncel kılıyor. Hemen anlaşılacağı gibi her türlü verinin iletimi, kaydedilmesi veya depolanması sürecinde ilk adım, veri veya iletilerin kodlanmasıdır. Kodlama için önce “Alfabe” adı verilen bir semboller kümesi seçilir. Günümüzde çoğu zaman 0 ve 1 sembollerinden oluşan küme, alfabe olarak seçilebilmektedir. Bu sembollerden kodun kuruluş kurallarına uygun olarak oluşturulan bloklar, örneğin 000, 100, 010, 111 gibi, kod sözcüğü adını alır. Kodlanmış mesaj, iletişim kanalı vasıtasiyle alıcıya gönderilir, örneğin bu 0 ve 1'lerden oluşan 0011101010010... gibi bir dizidir. İletişim kanalındaki olumsuz koşullar nedeniyle, bu olumsuz koşulların tümü “gürültü” deyimiyle açıklanır, ileti bozulur ve hatalar oluşabilir. İşte asıl bu aşamada Kodlar Kuramının önemi ortaya çıkar; Mesaj öyle kodlanmalıdır ki, oluşan hata giderilebilsin. Bu işleme, kodun çözümlenmesi veya düzeltilmesi denmektedir. Eğer elverişsiz bir kod kullanılmışsa alınan hatalı verilerin düzeltilmesi olanaksız olur. Zaten bir kodu oluşturan kod sözcüklerindeki semboller iki kısımdan oluşur. Birinci kısım bilgiyi taşır, ikinci kısım ise bilgiyi korumak için eklenen sembollerdir. Şu halde iletişim sırasında oluşacak hataları düzeltme yeteneği olan iyi bir kod kurulması son derece önemlidir, bu da Matematikçilerin görevidir. Eğer aldığımız iletiyi doğrulatma, ya da tekrar gönderilebilme olanağına sahipsek, kullanacağınız kodun sadece hata oluştuğunda bunu “sezme” yeteğine sahip olması yeterli olacaktır. Bu nedenle kodlar için çoğunlukla “hatasezen kodlar”, “hatadüzelten kodlar” (errordetecting codes and errorcorrecting codes ) deyimleri kullanılmaktadır. Daha açık bir deyişle, kodların bir kod sözcüğünde oluşabilecek en fazla kaç hatayı sezdiği ve düzelttiği önemlidir. Örneğin, “İkihata sezen, Tekhata düzelten kod” (doubleerror detecting and single error correcting codes), ifadelerinde olduğu gibi, kodları sezdikleri ve giderdikleri hata sayılarıyla anmak adet olmuştur. Özet olarak söylersek; hata düzeltme kodları bilgi iletimi, işlenmesi veya saklanması sürecinde olumsuz ortam nedeniyle oluşan hataları tamir etmektedir, yani sigorta görevi görmektedir. Bu durumu çok basit bir örnekle açıklayabiliriz. Örneğin “Evet” ve “Hayır” olmak üzere sadece iki mesajımız olsun. “0 evet, 1 hayır” diyelim. İletim sırasında herhangi bir olumsuzluk nedeniyle bir hata oluşur ve ileti bozulursa, “0” iletilecek yerde, hatalı olarak, “1” iletilmiş , “1” iletilecek yerde ise “0” iletilmiş olacaktır. Böyle bir durumda alınan iletinin hatalı alındığı da anlaşılamaz. Şu halde iletiyi bu şekliyle göndermemizin yararı yoktur. Bu kez, “00 evet, 11 hayır” için kullanılsın. Aslına bakılırsa burada “ 00” yazmakla “evet evet” yazmış yani mesajı tekrar etmiş olmaktayız. “00” gönderilmiş olsun. İletişim kanalındaki gürültü nedeniyle tek bir hata oluştuğunu varsayalım. O zaman 00 olan ileti bir hata ile 10 veya 01 olarak alınacaktır. Koddaki sözcükler sadece 00 ve 11 olduğundan 10 ve 01 birer kod sözcüğü değildir. Böylelikle hata oluştuğu anlaşılmış olur. Hata Gürültü sayımıyla kendine ençok benzeyen, aslıyla en az konum farkı olan 000 sözcüğüne dönüştürülerek düzeltme yapılabilir. Gönderilen kodsözcüğü de buydu. 000 sözcüğü gönderilse ve iki hata oluşsa, 110, 101 veya 011 elemanlarından biri alınır, bunlar birer kod sözcüğü olmadığından hata oluştuğu hemen sezilir. Düzeltme işlemi ise gerçekleştirilemez, çünkü iki hata ile alınan 110 sembolü kendine en çok benzeyen sözcüğe dönüştürülerek düzeltme yapılsa, 111 olarak düzeltilmiş olacaktır. Oysa gönderilen sözcük 000 idi. Şu halde bu kod ile iki hata düzeltilemez. Yani {000 , 111} kodu iki hata sezici , tek hata düzeltici bir koddur. Bu aşamada bir iletişim kanalının nasıl olduğunu taslak olarak görmekte yarar vardır: İletişim sürecinde diğer önemli nokta “zaman” sorunudur. İletilmesi veya saklanması gereken bilgiler belirli uzunlukta sözcükler halinde kodlanır. Kod sözcüklerinin yeterinden fazla uzun olması iletim süresini uzatacaktır. Bu da istenmeyen bir durumdur. Kod inşa edilirken kod sözcüklerinin çok uzun olmamasına özen gösterilmelidir. Diğer önemli nokta ise kod sözcüğü sayısının olabildiğince çok olmasını sağlamaktır. Kodun içerdiği sözcük sayısı ne kadar çoksa, gönderilebilecek bilgi o kadar fazla olacaktır. Aynen, anlatım gücünün dillerin zenginliğine bağlı olması gibi. Dil de bir çeşit kod değil mi zaten. Bilgilerin kodlanması ve alınan iletinin hatalarının giderilmesi işleminin kuramsal olarak gerçekleştirilmesi matematikçilerin işidir. Fakat pratikte bir iletişim sisteminde gerek kodlama gerekse kod çözme süreci belli aygıtlarla yapılır. Yani kodlayıcı ve kod çözücü aygıtlara gereksinim vardır. Şu halde inşa edilen kodun uygulamaya geçirilmesi ko İleti İleti Kaynağı Kayna ı ENCODER ENCODER (Kodlayıcı) (Kodlayıcı)) İletişim İLETİŞİM Kanalı KANALI kodsözcü kod sözcüğüü u = u1u2 ... u n DECODER (Kodçözücü) ileti x = x1 x 2 ... xk Alınan Alınan vektör Vektör Düzeltilmi ş Düzeltilmiş Mesaj mesaj Kullanıcı Kullanıcı oluştuğu saptanınca, örneğin 01 alınmış olsun, bunu düzeltme olanağı yoktur. En az hata oluştuğu ve bir sembolün hatalı alınma olasılığının daima hatasız alınma olasılığından küçük olduğu varsayımından hareketle, “alınan sembol dizisinin kendine ençok benzeyen kod sözcüğüne dönüştürülerek” düzeltme yapıldığını düşünelim. Örnek olarak 01 almıştık. Bunun 00 ve 11 sözcüklerine benzerliği aynıdır. Yani 01 ile 00 arasındaki farklı konum sayısı 1'dir. Aynı şekilde, 01 ile 11 arasındaki farklı konum sayısı da 1'dir. Çünkü 01 dizisinde yapılan tek bir değişiklikle 00 veya 11 elde edilmektedir. Şu halde { 00 , 11 } kodu tek hata sezici bir kod olarak adlandırılabilir. Bu kodun, yukarıdaki anlamda, hata düzeltme yeteneği yoktur. Bu kez, “000 ; evet, 111 ; hayır” olmak üzere { 000 , 111} kodu ele alınsın. 000 kod sözcüğü gönderilsin, bir tek hata oluştuğu varsayılsın. 000 kodsözcüğü bir hata ile 100 , 010 veya 001 olarak alınır. Hata oluştuğu hemen sezilir, çünkü alınan sembol bloğuna benzer kod sözcüğümüz yoktur. Bir hata olduğu var lay ve pratik olmalıdır. Daha açık bir anlatımla, kodu inşa eden matamatikçi ya da matematikçiler bilgilerin kodlanması ve kodun çözümlenmesi sürecinin pratikliğini ve uygulanabilirliğini göstermek zorundadırlar ki kodlayıcı (encoder) ve kod çözücü (decoder) aygıtların üretilebilmesi kolaylaşsın. Büyük ölçekli, yüksek hızlı veri ağlarında hataların kontrol altına alınması kodlar sayesinde olanaklı hale geldi. İletişim ile Bilgisayar teknolojilerinin kaynaştırılmasında kodlar kuramının katkısı artarak sürüyor. Örnek olarak manyetik bantlarda, disklerde, manyetik kayıtlarda, CD teknolojisinde ve her türlü sayısal bilgi depolamasında hata kontrolü ve düzeltimi için kodlar kullanılmakta. Kaynaklar ve daha fazla bilgi için: • van Lint, J. H., “Introduction to Coding Theory”, Springer • Hill, Raymond, “A First Course in Coding Theory”, Clarendon Press • MacWilliams, F. J. and Sloane, N. J. A., “The Theory of Errorcorrecting Codes”, AmsterdamNew YorkOxford: North Holland • Lin S., '' Costello D. J., ''Error Control Coding'', PrenticeHall,Inc.