Irving S. Reed (1923-2012)
Hepimiz küçükken arkadaşlarımızla şifreli bir yazışma sistemi oluşturmuşuzdur. Bu yazışma sistemi kimi zaten alfabedeki harfleri değiştirerek, kimi zaman da sayıları kullanarak oluşturulurdu. Ancak maalesef şifreleri her zaman bu kadar masum şeyler için kullanmıyoruz. Savaşlardan tutun da uzaya gitmemize kadar birçok yerde şifreleri kullanıyoruz aslında
Örneğin uzay araştırmaları için şifreli veri iletimi çok önemli bir meseledir. Çünkü bir düşünün, dünyamızdan milyonlarca kilometre uzaklıktaki Mars’a bir rover gönderiyorsunuz. Bu rover’ın görevi elbette bize Mars’tan bilgi göndermektir. Peki ama bunu nasıl yapıyor
İşte matematik tam da burada devreye giriyor. Matematikçiler bilgiyi iletmek ve depolamak için dahice bir yöntem geliştirdiler. Öğrencilerin okulda öğrendikleri cebirle aynı temelde olan Reed-Solomon kodları sayesinde bugün Mars’a gidebiliyoruz.
Peki Nedir Bu Reed-Solomon Kodları?
1960 yılında Irving S. Reed ve Gustave Solomon tarafından Reed-Solomon kodları oluşturulmuştur. Reed-Solomon kodları, ikili olmayan (non-binary) BCH kodlarının bir alt sınıfıdır. Bu kodların non-binary olmasının sebebi, tek tek bitler yerine birden fazla bit üzerinde çalışmasından kaynaklanmaktadır.
Bazı verileri bir ağ üzerinden aktardığımızda, bazı ağ sorunları nedeniyle verilerin bozulma olasılığı vardır. Verilerin içindeki bitler, parazit veya bazı ağ sorunları nedeniyle bozulabilir. Bu nedenle, aktarım sırasında verilerin kaybolma riski vardır. Reed-Solomon kodları, aşağıdakiler de dahil olmak üzere birçok sistemdeki hataları düzeltmek için kullanılır:
Depolama aygıtları (teyp, CD, DVD, barkodlar vb. dahil)
Kablosuz veya mobil iletişim (cep telefonları, mikrodalga bağlantıları vb. dahil)
Uydu iletişimi
Dijital televizyon / DVB
ADSL, xDSL gibi yüksek hızlı modemler.
Reed-Solomon Kodlarını Anlamak İçin Güzel Bir Örnek
Eski günlere dönüp ortaokulda arkadaşınızla şifreli bir şekilde anlaşmaya çalıştığınız bir anı hayal edin. Diyelim ki siz ve arkadaşınız ikişer sayı belirlediniz. Sizin seçtiğiniz sayılar 3 ve 6; arkadaşınızın seçtiği sayılarsa 57 ve 99 olsun.
Sizin seçtiğiniz sayılar x eksenini ve arkadaşınızınkiler de y eksenini temsil ettiğinden (3,57) ve (6, 99) ikililerine sahipsiniz. Reed-Solomon kodlarını kullanarak mesajı çözmek için verilenleri y=Ax + B eşitliğinde yerine koymanız gerekiyor. Bu sayede elinizde şu denklemler olmuş oluyor:
57 = 3A + B
99 = 6A + B
Bundan sonra mesajı bulabilmek için A ve B’yi buluyorsunuz. Eşitlikten de kolaylıkla görülebileceği gibi taraf tarafa çıkardığımızda A=14 ve B=15 bulunur.
Artık A ve B’yi bulduğunuza göre elinizdeki denklem y=14x+15 haline geliyor. Ve siz biliyorsunuz ki Reed-Solomon kodlarında gizli mesaj, katsayılarda gizlidir. Arkadaşınızın yolladığı şifre için üzerinde mutabık olduğunuz alfabenin 14. ve 15. harflerine bakıyorsunuz.
14. harf N ve 15. harf ise O; birleştirince mesajın “NO” olduğunu görüyorsunuz. Buradan da arkadaşınızın okuldan sonra oyun oynamaya gelmeyeceğini anlıyorsunuz.
Diğer şifreleme şemalarında olduğu gibi, mesajları güvende tutan açık ve özel bilgilerin akıllı bir birleşimidir. Arkadaşınız sınıfın ortasında size 57 ve 99 sayılarını söylese dahi sizden başka kimse mesajı anlayamazdı.
Bunun sebebi karşılık gelen özel bilgiler olmadan (yani x eksenlerini temsil eden 3 ve 6) denklemin çözülemeyecek olmasıdır. Bu değerleri yani 3 ve 6’yı arkadaşınızla aranızda tuttuğunuz sürece gizli mesajlarınızı gönül rahatlığıyla iletebilirsiniz.
Ya Daha Uzun Bir Mesaj Göndermek İstersek Ne Olacak?
Diyelim ki arkadaşınız dünkü Türkçe sınavınızın nasıl geçtiğini öğrenmek istiyor. Siz de 3 harfli mesajınızı sayılara çeviriyorsunuz. 14, 59 ve 82 sayılarını arkadaşınıza yolluyorsunuz. Daha önceden 3 harfli mesajlarınız için anlaşmış olduğunuz x eksenini temsil eden 2, 5 ve 6 sayıları ise arkadaşınızda. Böylece arkadaşınız sizin sayılarınızla kendisindekileri birleştirerek (2,14), (5, 59) ve (6, 82) noktalarını elde ediyor.
Şu an bir önceki mesajda olduğu gibi elimizde doğrusal bir denklem yok. Bunun yerine y = Ax2 + Bx + C şeklinde ikinci dereceden bir denkleme sahibiz. Ve ikinci dereceden denklemleri de bir önceki mesajı çözdüğümüz gibi çözeceğiz. Her bir noktayı y = Ax2 + Bx + C denkleminde yerine yazarsak şu 3 eşitliği elde ederiz:
(2, 14): 14 = 4A + 2B + C
(5, 59): 59 = 25A + 5B + C
(6, 82): 82 = 36A + 6B + C
Elimizde 3 denklem olduğu için çözmesi biraz daha uzun sürecek ancak izlediğimiz yol aynı olacak. Denklemleri A ve B’yi kolayca bulabilecek şekilde düzenleyeceğiz. Örneğin; eğer ikinci denklemden birinciyi çıkarırsanız 45=21A+3B bulursunuz. Tıpkı bunun gibi üçüncü denklemden de ikinciyi çıkarırsanız 23=11A+B bulursunuz. Şimdi elimizde iki tane görece daha basit denklem var, yani işimiz kolaylaştı:
45 = 21A + 3B
23 = 11A + B
İkinci satırdaki denklemi -3 ile çarpar ve bu iki denklemi taraf tarafa toplarsak A=2 buluruz. Daha sonra A’yı denklemde yerine yazarsak B=1 ve C=4 buluruz. Alfabenin 2. harfi B; 1. harfi A ve 4. harfi D olduğundan gizli mesaj “BAD” dir. Buradan da arkadaşınız, dünkü Türkçe sınavının sizin için kötü geçtiğini anlayacaktır.
Reed-Solomon Kodlarının Çalışma Prensibi Temel Cebir Bilgisine Dayanıyor
Polinom fonksiyonları sayesinde Reed-Solomon kodlarını kullanarak istediğiniz uzunlukta mesaj iletebilirsiniz. Yaptığımız örneklere dikkat edecek olursanız 2 harfli bir mesaj için 1. dereceden bir denklem kullandık.
3 harfli bir mesaj göndermek içinse 2. dereceden bir denklem kullandık. Yani eğer n harfli bir mesaj göndermek isterseniz (n-1). dereceden bir denklem kullanmanız gerekmektedir. Elbette Reed-Solomon kodları gerçekte bunlardan daha karmaşıktır ancak temel fikir örneklerimizle aynıdır.
Reed-Solomon Kodlarıyla Sadece Gizli Mesaj Göndermekle Kalmaz, Aynı Zamanda Hataları da Düzeltebilirsiniz!
Yazımızın başında belirttiğimiz gibi gönderilen kodlar her zaman doğru bir şekilde iletilemeyebilir. Reed-Solomon kodları bu noktada bize hataları tespit etme imkanı da sunar.
Hataları kodları tespit etmenin yollarından biri verilerin fazladan kopyalarını göndermektir. Örneğin arkadaşınız size [14, 15] yerine [14, 14, 14, 15, 15, 15] gönderebilir. Siz mesajın her bölümünün üç kez gönderileceğini bildiğiniz sürece mesajı çözebilir ve hataları fark edebilirsiniz.
Eğer arkadaşınız size [14, 14, 24, 15, 15, 15] gönderirse 24’ün 14 olması gerektiğini bilirsiniz. Böylece arkadaşınızdan mesajı tekrar göndermesini istemez; zamandan ve enerjiden tasarruf edersiniz.
Ancak Reed-Solomon kodlarının arkasındaki matematik sayesinde hataları daha kolay bir şekilde tespit edebilirsiniz. Bunun için her verinin birden fazla kopyasını göndermek yerine ekstra bir nokta gönderebilirsiniz.
Eğer bu ekstra nokta polinomunuza uymuyorsa hata var demektir. Ve bu ekstra nokta potansiyel olarak hataları da düzeltebilir. Bir hata algılanırsa ve alıcı, mesajı içeren polinom fonksiyonunu oluşturamazsa, bunun yerine regresyon tekniklerini kullanarak en uygun polinomu oluşturabilir. İletinin yapısına ve ne kadar ek bilgi gönderdiğinize bağlı olarak, bu en uygun polinom, hatalı bilgilerden bile doğru mesajı alabilmenize yardımcı olabilir
İletişimin iletilmesi ve düzeltilmesindeki bu verimlilik, NASA’nın neden Ay’a ve Mars’a yaptığı görevlerde Reed-Solomon kodlarını kullandığını açıklıyor. Basit bir cebirin bize başka dünyaların kapısını açması gerçekten hayran olunası
