QR kodlar hasar görse bile nasıl okunur? Hata düzeltme kodlarının matematiği

Bir restoranın masasındaki QR kodun üstüne çay dökülmüş, köşesi de biraz yıpranmış olsun. Telefonunuzu tuttuğunuzda menü yine de açılır. Oysa bir QR kod, siyah ve beyaz karelerle yazılmış bir bit dizisidir. Bu karelerin bir kısmı okunamıyorsa, eksik bilgi nereden geliyor?

Cevap, hata düzeltme kodları denen matematiksel bir düzendir. QR kod, taşıdığı mesajın yanına özenle hesaplanmış fazladan bilgi ekler. Okuyucu, bu fazlalığı kullanarak bozulan parçaları yeniden hesaplar. Bu yazıda en basit parite bitinden başlayıp QR kodlarda kullanılan Reed–Solomon kodlarının arkasındaki polinom fikrine kadar, kendi küçük örneklerimizle ilerleyeceğiz.

QR kod neyi saklar?

QR kod, 1994’te Japon Denso Wave şirketinde Masahiro Hara’nın ekibi tarafından otomobil parçalarını izlemek için geliştirildi. Adı İngilizce “quick response”, yani hızlı yanıt ifadesinden gelir.

Bir QR kodu oluşturan küçük karelere modül denir. Her modül bir bit taşır: koyu kare 1, açık kare 0 gibi. Köşelerdeki üç büyük kare, okuyucunun kodun yerini ve yönünü bulmasına yardım eder. Geri kalan alanda veriler 8 bitlik gruplar, yani baytlar hâlinde yer alır. Bu baytların bir kısmı asıl mesajı, bir kısmı ise hata düzeltme bilgisini taşır.

Fazlalık fikri: tekrar etmek

Gürültülü bir telefon hattında önemli bir sayıyı söylerken ne yaparsınız? Muhtemelen tekrar edersiniz. En basit hata düzeltme yöntemi de budur. Her biti üç kez gönderelim: 1 yerine 111, 0 yerine 000.

Karşı taraf 101 alırsa, çoğunluğa bakarak asıl bitin 1 olduğuna karar verir. Böylece üç bitten biri bozulsa bile mesaj kurtarılır. Ama bedel ağırdır: Mesajın boyu üç katına çıkar. Matematikçilerin sorusu şudur: Daha az fazlalıkla daha çok hata düzeltilebilir mi?

Parite biti: hatayı fark etmek

Dört bitlik bir mesaj düşünelim: 1011. Bitlerin toplamı 3’tür, yani tektir. Mesajın sonuna, toplamı çift yapacak bir bit ekleyelim. Buna parite biti denir. 1 + 0 + 1 + 1 + 1 = 4 olduğundan gönderilen dizi 10111 olur.

Alıcı 10011 alırsa bitleri toplar: 1 + 0 + 0 + 1 + 1 = 3. Toplam tek çıktığı için bir hata olduğunu anlar. Yalnızca bir bit ekleyerek hatayı fark ettik. Ama hangi bitin bozulduğunu bilmiyoruz, bu yüzden düzeltemiyoruz.

İki boyutlu parite: hatanın yerini bulmak

Bitleri 3 × 3’lük bir tabloya yerleştirip hem her satıra hem her sütuna parite ekleyelim. Örnek mesajımız şu olsun:

	1. sütun	2. sütun	3. sütun	Satır paritesi
1. satır	1	0	1	0
2. satır	1	1	1	1
3. satır	0	0	1	1
Sütun paritesi	0	1	1

Her satırın ve her sütunun toplamı, parite biti de eklendiğinde çift olur. Şimdi ortadaki bit bozulup 1’den 0’a dönsün. Alıcı kontrol eder:

• 2. satır: 1 + 0 + 1 + 1 = 3, tek. Bu satırda hata var.
• 2. sütun: 0 + 0 + 0 + 1 = 1, tek. Bu sütunda hata var.

Hatalı satır ile hatalı sütunun kesiştiği yer, bozulan bittir. Alıcı o biti çevirir ve mesaj düzelir. Dokuz bitlik mesaja altı bit ekleyerek tek bir hatayı hem bulduk hem düzelttik. Ama iki hata aynı satıra düşerse bu yöntem şaşırabilir. Daha güçlü bir fikre ihtiyaç var.

Reed–Solomon sezgisi: iki nokta bir doğru belirler

Irving Reed ve Gustave Solomon, MIT Lincoln Laboratuvarı’nda çalışırken geliştirdikleri yöntemi 1960’ta yayımladılar. Temel fikir, lisede tanıdığımız bir gerçeğe dayanır: İki noktadan tek bir doğru geçer.

Göndermek istediğimiz iki sayı 5 ve 8 olsun. Bu sayıları bir doğrunun iki değeri gibi düşünelim: p(0) = 5 ve p(1) = 8. Bu iki koşulu sağlayan tek doğru p(x) = 5 + 3x’tir.

Şimdi yalnızca iki değer yerine, doğrunun dört noktadaki değerini gönderelim:

• p(0) = 5
• p(1) = 8
• p(2) = 11
• p(3) = 14

Yol boyunca bir değer bozulsun ve alıcıya 5, 8, 17, 14 ulaşsın. Alıcı bu dört değerin aynı doğru üzerinde olması gerektiğini bilir. Hangi üçünün bir doğru üzerinde olduğunu kontrol eder:

• x = 0, 1, 3 için 5, 8, 14 değerleri p(x) = 5 + 3x doğrusuna tam uyar.
• x = 2 için gelen 17 bu doğruya uymaz. Doğru değer 5 + 3 × 2 = 11 olmalıdır.

Alıcı 17’yi 11 ile değiştirir ve asıl mesajı, yani 5 ile 8’i geri kazanır. Fazladan iki değer göndererek bilinmeyen yerdeki bir hatayı düzeltmiş olduk.

Bu fikir genelleşir. k tane veri sayısı, derecesi k’den küçük bir polinomla temsil edilir ve polinomun n farklı noktadaki değeri gönderilir. Eklenen n − k fazla değer sayesinde, yeri bilinmeyen en çok (n − k) ÷ 2 hata düzeltilebilir. Hatanın yeri biliniyorsa, örneğin bir parça tamamen yırtılmışsa, en çok n − k eksik değer yeniden hesaplanabilir.

Gerçek Reed–Solomon kodları bu hesabı sıradan sayılarla değil, 256 elemanlı özel bir sayı sisteminde yapar. Bu sistemde toplama ve çarpma, sonuç her zaman 0 ile 255 arasında kalacak biçimde tanımlanır. Böylece her değer tam olarak bir bayta sığar, kesirler ya da taşmalar ortaya çıkmaz. Hataların hangi değerlerde olduğunu bulmak için de verimli algoritmalar geliştirilmiştir.

QR kodlarda hata düzeltme seviyeleri

QR kodu oluşturan kişi dört hata düzeltme seviyesinden birini seçer. Her seviye, kodun yaklaşık ne kadarının kurtarılabileceğini gösterir:

Seviye	Kurtarılabilecek pay (yaklaşık)
L	%7
M	%15
Q	%25
H	%30

Burada bir denge vardır. Seviye yükseldikçe koda daha çok hata düzeltme baytı eklenir. Aynı boyuttaki bir kod daha az veri taşır ya da aynı veri için daha büyük, daha sık modüllü bir kod gerekir. Temiz ortamlarda düşük bir seviye yeterli olabilirken, kir ve yıpranmaya açık yerlerde yüksek seviyeler tercih edilir.

Bazı QR kodların ortasına küçük bir logo yerleştirilebilmesi de bu paydan yararlanır. Ama bu, hata düzeltme kapasitesinin bir kısmını baştan harcamak demektir. Ayrıca köşelerdeki büyük kareler ağır hasar görürse okuyucu kodu bulmakta zorlanabilir; hata düzeltme yalnızca veri alanındaki kayıpları telafi eder.

Bugün nerede karşımıza çıkar?

Reed–Solomon kodları QR kodlarla sınırlı değildir. Müzik CD’lerinde çizilen yüzeyden okunan verinin düzeltilmesinde, uzak uzay sondalarından gelen sinyallerde ve veri depolama sistemlerinde benzer kodlar kullanılır. Nerede gürültülü bir kanal ya da bozulabilen bir ortam varsa, orada bir hata düzeltme kodu da vardır.

Bu yazıdaki fikirler lise matematiğinin konularıyla doğrudan bağlantılıdır:

• Tek ve çift sayılar ile bölünebilme, parite bitinin temelidir.
• Doğrunun analitiği: İki noktadan tek doğru geçmesi, Reed–Solomon’un çıkış noktasıdır. Koordinatlarla düşünmenin tarihi için Descartes yazımıza bakabilirsiniz.
• Polinomlar: Daha çok veri, daha yüksek dereceli polinom demektir.

Polinomlar ve analitik geometri TYT ve AYT konuları arasında yer alır; ayrıntılı listeyi ne öğrettiğimizi anlattığımız sayfada bulabilirsiniz. Bilginin bitlerle ölçülmesi ve gürültülü kanallardan iletilmesi fikrinin kurucu adımları ise Shannon ve bilgi kuramı yazımızda anlatılıyor.

Kapanış

Yıpranmış bir QR kodun hâlâ okunabilmesi şans değil, tasarımdır. Mesajın yanına eklenen fazladan değerler, bozulan parçaların yeniden hesaplanmasını sağlar. Üç tekrarlı bitten parite tablosuna, oradan iki noktanın belirlediği doğruya uzanan yol, bir soruyu hep daha verimli cevaplamaya çalışır: En az fazlalıkla en çok hatayı nasıl düzeltebiliriz?