Reed-Solomon Kodları: CD'den QR Koda, Mars'tan Cep Telefonuna

Çizilmiş CD'nin sihri

Bir kompakt disk üstüne 5 mm uzunluğunda çizik çekin. Lazer çiziği geçerken veri kaybedilir. Yine de müzik bozulmadan çıkar.

Bu mucize değil, matematik: Reed-Solomon kodları.

Temel fikir

Mesaj: $k$ bilgi sembolü. Bunları $k-1$ dereceli bir polinom olarak gör.

Sonra polinomu $n > k$ noktada hesapla. Bu $n$ değer gönderilen kod.

Alıcı: $n$ noktadan herhangi $k$ tanesi ile polinomu geri kurar (Lagrange interpolasyonu).

Yani $n - k$ adet hata veya silme tolerans edilebilir.

Sade örnek

3 bilgi sembolü: $(2, 5, 7)$. Polinom $p(x) = 2 + 5x + 7x^2$ (sonlu cisim üzerinde).

Bunu 5 noktada hesapla: $p(0), p(1), p(2), p(3), p(4)$. Gönder.

Alıcı: 5 noktadan herhangi 3'ünü bilirse polinomu tek başına geri çıkarır → mesajı kurtarır.

Tolerans: 2 hata veya silme. Pratikte daha karmaşık modellerle güçlendirilir.

Niçin polinomlar?

Cebrin temel teoremi: $k-1$ dereceli polinom $k$ farklı nokta ile tek olarak belirlenir. Reed-Solomon bu cebrik gerçeği kullanır.

Sonlu cisim üzerinde

Pratikte $GF(2^8) = GF(256)$ üzerinde çalışır — her sembol 1 byte.

CD'lerde CIRC (Cross-Interleaved Reed-Solomon Code): iki Reed-Solomon kodu nestleinmiş + interleaving. Burst hatalar için optimize.

Tarihsel köken

Irving S. Reed ve Gustave Solomon (1960, MIT Lincoln Lab): orijinal makale. 6 sayfa.

Başta teorik kuriozite. Pratik kod çözme algoritmaları yoktu.

1969: Berlekamp-Massey algoritması — etkili kod çözme. Reed-Solomon pratikleşti.

1980'ler: CD'ler standart hale geldi. RS kodları her CD üreticisi için zorunlu.

1990'lar: DVD, Blu-ray, sabit disk. Mars sondaları (Pathfinder, MER).

2000'ler: QR kodları (Denso Wave, Japon).

QR kod örneği

Standart QR kod 4 düzey hata düzeltme:

• L: %7 hata.
• M: %15 hata.
• Q: %25 hata.
• H: %30 hata.

Yani %30 kapalı QR kod hâlâ okunur. Reed-Solomon sayesinde.

Bu, modern reklamcılığın fiziksel dünyada QR kod kullanabilmesinin nedeni: yıpranma, kir, kısmi örtme — sorun değil.

Modern uygulamalar

1. Veri depolama

• CD, DVD, Blu-ray: çiziklere tolerans.
• Sabit diskler: sektör hataları.
• SSD: hücre yıpranması.
• DNA depolama (deneysel).

2. İletişim

• Mars sondaları: NASA Voyager, Curiosity, Perseverance.
• Uydu: GPS, hava durumu.
• Cep telefonu: 4G (modern 5G'de LDPC + Polar).
• DSL modemler.

3. Hesaplama

• RAID-6: disk dizi yedeklilik.
• Distributed storage (Reed-Solomon erasure coding).

4. Tüketici

• QR kodları.
• Barkodlar (2D).

Berlekamp-Massey algoritması

RS kod çözmenin standardı. Hata konumlarını polinom kökleri olarak bulur, sonra hata değerlerini hesaplar.

Karmaşıklık $O(n^2)$ veya daha az.

Niçin hâlâ klasik?

Modern Turbo/LDPC/Polar kodlar Shannon'a daha yakın. Ama RS:

• Sade yapı.
• Donanım uygulaması kolay.
• Burst hatalar için ideal (interleaving ile).
• Garanti $n-k$ hata düzeltme.

Modern sistemlerde kombinasyon: RS dış kod + Turbo/LDPC iç kod.

Sonuç

Reed-Solomon kodları:

• Polinom interpolasyonu matematik temeli.
• 1960'tan beri standart hata düzeltme kodu.
• CD, DVD, Mars sondaları, QR kod — yaygın uygulama.
• Burst hata toleransı ile özel uygulama.

Bir matematik öğrencisi her gün — müzik dinlerken, QR kod tararken, internet sayfasında dosya indirirken — Reed-Solomon kodlarını görmeden kullanır.

1960'da iki MIT mühendisinin 6 sayfalık makalesi, modern dijital çağın vazgeçilmez katmanı oldu. Matematik = pratik zarafetinin örneği.

"Bilgi yıkımdan korunabilir." Reed-Solomon'un sade vaadi.