Reed-Solomon Kodları: Gizli Kodların ve Uzay İletişiminin Arkasındaki Cebir

Matematikçiler, bilgiyi iletmek ve depolamak için dahiyane yöntemler geliştirdi. Bunlardan biri, öğrencilerin okulda öğrendiği temel cebir üzerine kurulu olan Reed-Solomon kodlarıdır.

Bir ağı kullanarak veri aktardığımızda, çeşitli ağ sorunları nedeniyle verilerin bozulma ihtimali vardır. Parazit veya ağdaki hatalar, verinin içindeki bitleri değiştirebilir ve bu da aktarım sırasında veri kaybına yol açabilir. Reed-Solomon kodları, bu tür hataları tespit etmek ve düzeltmek için geliştirilmiştir.

Peki Nedir Bu Reed-Solomon Kodları?

Eski günlere dönün ve ortaokulda bir arkadaşınızla şifreli biçimde haberleşmeye çalıştığınız bir anı düşünün. Diyelim ki siz iki sayı seçtiniz: 3 ve 6. Arkadaşınız da iki sayı seçti: 57 ve 99.

*Reed-Solomon kodları, 1960 yılında Irving S. Reed ve Gustave Solomon tarafından geliştirilmiştir.*

Sizin seçtiğiniz sayılar $x$ eksenini, arkadaşınızın seçtiği sayılar ise $y$ eksenini temsil etsin. Bu durumda iki nokta elde ederiz: $(3,57)$ ve $(6,99)$ . Reed–Solomon kodlarının temel fikrini uygulamak için bu noktaların $y = Ax + B$ biçimindeki bir doğru üzerinde yer aldığını varsayarız. Noktaları bu denkleme yerleştirdiğimizde şu iki eşitliği elde ederiz:

57=3A+B
99=6A+B

Bu iki denklem çözüldüğünde, doğruyu belirleyen $A$ ve $B$ katsayıları bulunur. Mesaj da bu katsayılarda saklıdır. Denklemleri taraf tarafa çıkardığımızda $A = 14$ ve $B = 15$ elde edilir. Böylece doğru denklemi $y = 14x + 15$ olur.

Reed–Solomon kodlarında mesajın katsayılarda saklı olduğunu bildiğimiz için, önceden üzerinde anlaştığımız alfabeye bakarız. Alfabenin 14. harfi N, 15. harfi ise O olduğuna göre mesajın “NO” olduğunu anlarız. Bu da arkadaşınızın okuldan sonra oyun oynamaya gelmeyeceği anlamına gelir.

Bu basit Reed–Solomon kodunun dayandığı fikir, geometrinin iki temel özelliğidir. Birincisi, iki farklı noktadan yalnızca bir doğru geçer. İkincisi, her doğru $y = Ax + B$ biçiminde yazılabilir. Bu nedenle bir doğru üzerindeki iki noktayı biliyorsanız $A$ ve $B$ katsayılarını hesaplayabilirsiniz. Aynı şekilde, $A$ ve $B$ değerlerini bildiğinizde doğrunun üzerindeki tüm noktaları belirleyebilirsiniz.

Ancak öğrenciler daha uzun bir mesaj paylaşmak isteselerdi ne olurdu? İşte burada cebir, geometri ve doğrusal denklem sistemlerinin tam gücü devreye girer.

Reed-Solomon Kodları Nasıl Çalışır?

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 = Ax² + 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 = Ax² + 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

Üç bilinmeyenli üç denklem, iki bilinmeyenli sisteme göre biraz daha zahmetlidir ama amaç aynıdır: Denklemleri akıllıca birleştirerek değişkenleri teker teker yok etmek. Bu işlemin sonunda $A$ , $B$ ve $C$ bulunur; yani mesaj çözülmüş olur.

Reed-Solomon kodlarını kullanarak herhangi bir uzunluktaki 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 için 2. dereceden bir denklem kullandık.

Eğer uzunluğu 10 olan bir mesaj göndermek isterseniz, mesajı dokuzuncu dereceden bir polinomun katsayıları olarak kodlarsınız. Sonra önceden kararlaştırılmış 10 gizli $x$ değerinde bu fonksiyonu hesaplar ve ortaya çıkan 10 $y$ değerini açıkça gönderirsiniz. Alıcı bu değerlerden polinomu yeniden kurar ve katsayılardan mesajı çözer. Gerçekte Reed–Solomon kodları bundan biraz daha karmaşıktır. Ancak temel fikir aynıdır.

Reed-Solomon Kodlarıyla Hataları da Düzeltebilirsiniz!

Reed-Solomon kodları yalnızca mesajları güvenli tutmakla kalmaz, aynı zamanda basit ve verimli bir şekilde hataları tespit etme ve düzeltme imkanı da sunar. Veri iletimi veya depolama sırasında bilgi kaybı ya da bozulma ihtimali her zaman vardır, bu nedenle hata düzeltme oldukça önemlidir.

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öndersin.. 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.

Reed–Solomon kodlarının arkasındaki matematik, hataları daha etkili biçimde tespit etmeyi sağlar. Bunun için her veriyi tekrar tekrar göndermek yerine ek bir nokta iletmek yeterlidir. Eğer bu ek nokta belirlenen polinoma uymuyorsa, iletim sırasında bir hata oluştuğu anlaşılır.

Bu ek nokta yalnızca hatayı tespit etmeye yaramaz, aynı zamanda düzeltme sürecine de katkı sağlar. Alıcı, mesajı temsil eden polinomu doğrudan oluşturamazsa, verilen noktalara en iyi uyan polinomu hesaplar.

Elde edilen bu yaklaşık polinom, asıl polinomu yeniden kurmaya yardımcı olur. Böylece bozulmuş ya da eksik verilere rağmen orijinal mesaj geri kazanılabilir. Reed–Solomon kodlarının Ay ve Mars görevlerinde NASA tarafından tercih edilmesinin temel nedenlerinden biri de bu güçlü hata düzeltme yeteneğidir.

Sonuç Olarak

Reed–Solomon kodları oldukça etkilidir, ancak bazı sınırlamaları vardır. Mesajı kodlarken kullanılacak sayı kümesi sınırlıdır. Bu küme küçük olduğunda gönderilecek mesajların uzunluğu da azalır. Küme büyüdüğünde ise çözme süreci daha karmaşık hâle gelir.

Matematikçiler bu sınırları aşmak için daha güçlü kodlar geliştirmiştir. Bunlara cebirsel geometri kodları denir. Bu kodlar, daha karmaşık eğriler üzerine kurulur ve küçük bir sayı kümesiyle bile daha uzun mesajların iletilmesini mümkün kılar.

Ancak bu yaklaşımın da bir bedeli vardır. Bu yeni kodların arkasındaki matematik çok daha karmaşıktır. Reed–Solomon kodlarını uygulamak görece kolayken, cebirsel geometri kodlarını bilgisayarlarda verimli biçimde kullanmak hâlâ önemli bir zorluktur.

Bugün için bu büyük bir problem değil; mevcut uygulamaların çoğunda Reed–Solomon kodları yeterlidir. Ancak gelecekte güçlü kuantum bilgisayarlar ortaya çıkarsa, bugünkü bazı şifreleme yöntemleri kırılabilir. Bu yüzden araştırmacılar daha dayanıklı sistemler arıyor ve cebirsel geometri kodları bu arayışta umut verici adaylar arasında yer alıyor.

Kaynaklar ve İleri Okumalar