BattOS

Her Gün Cebiri: QR Kodlar ve Reed-Solomon Kodları

Bazen matematik ve özellikle cebir çok soyut gelebilir. Nerede kullanılıyor ki diye düşünülebilir. Bu çok normal bir düşüncedir. Cevabı ise her yerde. Özellikle Coding Theory başlığı altındaki hata düzeltme kodları (error correcting codes) günlük hayatta her yerde kullanılıyor. DVD/CD’lerde, 5G teknolojisini kullandığınızda, internetten bir mesaj gönderdiğinizde, ve daha birçok yerde. Bu kullanım alanlarından en basit ve yaygını ise QR kodlarıdır.

Kafelerde menü okurken, ödeme yaparken veya bir konsere girerken… QR kodlar artık modern hayatın görünmez dokusunun bir parçası. Peki ama akıllı telefonumuzun kamerası, bu siyah-beyaz kareler yığınından anlamlı bir veriyi nasıl çekip çıkarıyor? Daha da ilginci; bu kodlar yırtıldığında, üzerine kahve döküldüğünde veya silik basıldığında nasıl oluyor da hala kusursuz bir şekilde okunabiliyor?

Cevap sadece piksellerde değil, cebirin ve polinomların dünyasında gizli.

QR Kodların Anatomisi

QR (Quick Response) kodlar, veriyi siyah ve beyaz karelerden (modüllerden) oluşan iki boyutlu bir matris üzerinde görselleştirir. Rastgele bir gürültü gibi görünse de aslında her QR kodun çok sıkı kurallara bağlı bir anatomisi vardır:

Görsel 1: QR kodların anatomisi (https://www.thonky.com/qr-code-tutorial/function-patterns2.png)

Peki bu matris sıfırdan nasıl inşa edilir?

Adım Adım QR Kodların Oluşturulması

Bir QR kodun inşası, görsel yerleşimden cebirsel hata düzeltmeye uzanan 7 adımlık ardışık bir mühendislik mimarisi içerir:

Adım 1: Veri Analizi (Data Analysis)

İlk adım, koda yazılacak verinin tipini belirlemektir. Veri sadece sayılardan mı oluşuyor? Harfler var mı? Yoksa evrensel bir format olan Byte (Bayt) modunda mı çalışılacak? Verinin karakteristiği, kodun ne kadar sıkıştırılabileceğini belirler.

Adım 2: Veri Kodlama (Data Encoding)

Veri tipine karar verildikten sonra karakterler bit dizilerine (1 ve 0’lara) çevrilir. Bu veri akışı daima bir Mod Belirteci (Mode Indicator) ile başlar. Örneğin veri sadece sayılardan oluşuyorsa farklı, harflerden oluşuyorsa (Alfanumerik: 0010) farklı, bayt modundaysa (0100) farklı bir kodla başlar. Ardından karakter uzunluğu belirtilir. Tüm mesaj yazıldıktan sonra sistem özel bir sonlandırma kodu (0000) ile kapanır.

Görsel 2: QR kodların modları ile ilgili tablo. (Reed–Solomon codes for coders - Wikiversity)

Adım 3: Hata Düzeltme Kodlaması (Error Correction Coding)

İşte matematiğin devreye girdiği yer! Fiziksel dünyada hiçbir şey kusursuz değildir. Kötü ışıklandırma veya kağıt yırtıkları nedeniyle kod hasar gördüğünde (Buna “Burst Error” yani kümelenmiş hata denir), kurtarıcı olarak sahneye Reed-Solomon (RS) Kodları çıkar.

QR kodlar baytlar (8 bit) halinde yapılandırıldığı için, matematiksel işlemler 256 elemanlı $GF(2^8)$ sonlu cismi (Galois Field) üzerinde gerçekleştirilir. Bu cisim, genellikle şu indirgenemez (irreducible) polinom etrafında inşa edilir:

\[P(x) = x^8 + x^4 + x^3 + x^2 + 1\]

Şifreleme (kodlama) aşamasında, Adım 2’de hazırlanan veri baytları bir $M(x)$ mesaj polinomu olarak ifade edilir. $t$ adet sembol hatasını (bozuk baytı) düzeltebilecek bir yapı kurmak için $2t$ dereceli özel bir üreteç polinomu olan $g_{RS}(x)$ kullanılır. Mesaj polinomu kaydırılır ve üreteç polinoma bölünür:

\[R(x) = M(x) \cdot x^{2t} \pmod{g_{RS}(x)}\]

Buradan elde edilen kalan olan $R(x)$, QR kodumuzu koruyacak olan “Hata Düzeltme Baytları”nın ta kendisidir.

Adım 4: Final Mesajı Yapılandırma (Structure Final Message)

QR kodun toplam veri kapasitesi ikiye bölünür: Mesaj Baytları ve Hata Düzeltme Baytları. Örneğin, yüksek güvenlikli (Level H - %30 tolerans) bir QR kodda sadece 9 baytlık asıl veriyi korumak için, hesaplanan 17 baytlık hata düzeltme verisi eklenebilir. Bu adımda, orijinal veri blokları ile matematiksel kalanlar (hata düzeltme blokları) belirli bir sıraya göre uç uca eklenerek matrise yazılmaya hazır tek bir uzun dizi haline getirilir.

Görsel 3: QR kodların hata düzeltme seviyeleri tablosu. (Reed–Solomon codes for coders - Wikiversity)

Adım 5: Matrise Modül Yerleşimi (Module Placement in Matrix)

Hazırlanan 1’ler (siyah) ve 0’lar (beyaz), matrise yerleştirilir. Yerleştirme işlemi sağ alt köşeden başlar ve yukarı-aşağı yönlü bir zig-zag şablonu izleyerek matrisin içine doğru ilerler.

Görsel 4: QR kodlarda verilerin yerleştirilmesi. (Reed–Solomon codes for coders - Wikiversity)

Adım 6: Veri Maskeleme (Data Masking)

Bazen veriler tesadüfen yan yana gelerek kamerayı yanıltacak şekiller (örneğin bulucu desenlerin taklitleri veya devasa siyah/beyaz boşluklar) oluşturabilir. Bunu engellemek için kodlayıcı, verilerin üzerine XOR ($\oplus$) tabanlı bir “Maskeleme” uygular. Kontrast dengelenir ve optik illüzyonların önüne geçilir.

Görsel 5: QR kodlarda kullanılan maskeleme örüntüleri. (Reed–Solomon codes for coders - Wikiversity)

Görsel 6: QR kodlarda maskeleme. (Reed–Solomon codes for coders - Wikiversity)

Adım 7: Biçim ve Sürüm Bilgisi (Format and Version Information)

Son olarak, kodu okuyacak kameranın işini kolaylaştırmak için hangi maskenin kullanıldığı ve “Hata Düzeltme Seviyesi” (L, M, Q, H) bilgileri, bulucu desenlerin hemen etrafına iki farklı kopya halinde “Biçim Bilgisi” olarak işlenir.

Artık QR kodumuz basılmaya veya ekranda gösterilmeye hazırdır!

Kurtarma Operasyonu (Decoding) ve Hasar Tespiti

Diyelim ki oluşturduğumuz QR kodun köşesi yırtıldı veya üzerine bir leke bulaştı. Leke, yan yana duran 24 bit’i bozduğunda, Reed-Solomon algoritması bunu devasa bir çöküş olarak değil, sadece “3 bozuk bayt” olarak algılar.

Kamera zig-zag yolunu izleyip veriyi okuyup çözücüye (decoder) gönderdiğinde, sistem okunan verinin polinom köklerini analiz eder. Bu “Sendrom Hesaplaması” sayesinde, devasa matrisin tam olarak hangi bölgesindeki baytların bozulduğu matematiksel bir kesinlikle bulunur (Hata yeri tespiti). Ardından hasar gören baytlar orijinal haline geri döndürülür (Hata düzeltme).

Uygulamalı Örnek: SageMath ile Hata Düzeltme Simülasyonu

Soyut formüllerin gerçek hayatta nasıl çalıştığını görmek için küçük bir SageMath kod simülasyonu yapalım. Bu senaryoda 19 baytlık bir veriyi kodlayacak, üzerine kasten bir “leke” (hata) ekleyecek ve algoritmanın bunu nasıl tespit edip onardığını izleyeceğiz.

# Matematiksel Evrenin (GF(2^8)) Kurulması
sage: F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x^2 + 1)
sage: R.<x> = PolynomialRing(F)

# Orijinal Veri ve Kodlama (Encoding)
sage: data_bytes = [64, 132, 214, 87, 38, 134, 22, 38, 18, 16, 236, 17, 236, 17, 236, 17, 236, 17, 236]
sage: M_x = sum(F.fetch_int(val) * x**(18 - i) for i, val in enumerate(data_bytes))
sage: g_x = prod(x - a**i for i in range(7)) # Üreteç polinomu
sage: rem_x = (M_x * x**7) % g_x             # Polinom bölmesi (Kalanı bulma)
sage: Encoded_x = M_x * x**7 + rem_x         # Korumalı verimiz

# Fiziksel Hasar (Leke/Çizik) Simülasyonu
# Diyelim ki QR kodun 5. indeksine denk gelen yere bir kahve damladı. 
# Değeri matematiksel olarak 50 olan bir hata (E_x) ekliyoruz.
sage: E_x = F.fetch_int(50) * x**5
sage: Received_x = Encoded_x + E_x           # Kameranın okuduğu bozuk veri

# Kurtarma Operasyonu (Decoding)
sage: syndromes = [Received_x(a**k) for k in range(7)]
sage: from sage.matrix.berlekamp_massey import berlekamp_massey
sage: Lambda_poly = berlekamp_massey(syndromes[:6])
sage: Lambda_x = R(Lambda_poly).reverse()

# Sisteme "Hata nerede?" diye soruyoruz:
sage: error_positions = []
sage: for i in range(255):
....:     if Lambda_x(a**(-i)) == 0:
....:         error_positions.append(i)
....:
sage: print(f"Tespit Edilen Hata İndeksi: {error_positions}")
Tespit Edilen Hata İndeksi: [5]

# Hatanın Düzeltilmesi
sage: S_x = sum(S * x**i for i, S in enumerate(syndromes[:6]))
sage: Omega_x = (S_x * Lambda_x) % (x**6)
sage: Lambda_prime_x = Lambda_x.derivative()
sage: Corrected_x = Received_x

# Bozuk olan yeri hesaplayıp tersine çevirerek orijinal veriyi kurtarıyoruz.
sage: for i in error_positions:
....:     e_i = (Omega_x(a**(-i)) / Lambda_prime_x(a**(-i))) * a**i
....:     Corrected_x = Corrected_x + (e_i * x**i)
....:
# Kurtarılan veri, orijinal şifrelenmiş veriyle aynı mı?
sage: Corrected_x == Encoded_x
True

Çıktının sonundaki o tatmin edici True ifadesi, okuyucu uygulamanıza iletilen verinin, fiziksel dünyadaki tüm o yırtıklara ve lekelere rağmen ilk günkü gibi pürüzsüz ve hatasız olduğunu kanıtlar.

Yazıyı olabildiğince temel tutmaya çalıştım. Reed-Solomon kodlarını ve yukarıdaki kodun tam olarak nasıl çalıştığını merak ediyorsanız iletişime geçmekten çekinmeyin.

Gelecek Bölümde: Klasik sistemler bu şekilde tıkır tıkır işlerken, kuantum bilgisayarlarının gelişiyle her şey değişmek üzere. RSA ve ECC neden ölüyor? McEliece algoritması, QR kod mantığındaki bu hataları nasıl kendi avantajına çevirip kırılmaz bir şifreye dönüştürüyor? 1978’den gelen bu kurtarıcıyı inceleyeceğiz.

Kaynakça ve İleri Okuma: