Dört sayılık bir liste
Elimde dört sayı var, sana göndereceğim, ama yolda biri bozulabilir.
Birinci adım: sonuna toplamı yaz.
Diyelim ikinci sayı yolda silindi:
Kolay. 3 + 2 + 5 = 10, toplam 17 olmalı, eksik sayı 7. Tek bir fazladan sayıyla kaybolan bir sayıyı geri getirdim. Listeyi iki kere göndermeme gerek kalmadı.
İkinci adım: peki kaybolduğunu bilmiyorsam?
Asıl zor durum bu. Sayı kaybolmuyor — yanlış geliyor:
Toplarsam 19 çıkıyor, oysa 17 yazıyor. Bir yerde hata var, nerede olduğunu bilmiyorum.
Çözüm: ikinci bir kontrol sayısı. Bu sefer her sayıyı sırasıyla çarparak toplayayım:
1×3 + 2×7 + 3×2 + 4×5 = 43Göndereceğim şey artık:
Hatalı liste geldiğinde iki ipucum var:
gelen liste: 3 9 2 5
toplam : 19 ama 17 olmalıydı → 2 fazla
çarpımlı toplam: 47 ama 43 olmalıydı → 4 fazlaŞimdi bak: 4 ÷ 2 = 2. Hata 2. sırada. Ve 2 fazla çıkmış: 9 − 2 = 7.
Liste düzeldi. Hem hatanın yerini hem doğru değerini buldum — sadece iki fazladan sayıyla.
Kural tek cümle
Her fazladan kontrol sayısı sana bir cevap veriyor:
Hatanın nerede olduğunu biliyorsan, 1 kontrol sayısı = 1 kurtarılan sayı. Bilmiyorsan, 2 kontrol sayısı = 1 düzeltilen hata — biri yerini bulur, öbürü değerini. Beş hata düzeltmek istiyorsan on kontrol sayısı eklersin. Hepsi bu.
Ve işin güzeli: liste dört sayı yerine dört yüz sayı olsaydı, bir hatayı düzeltmek için yine sadece iki kontrol sayısı yeterdi.
Kontrol sayısının maliyeti listenin uzunluğuna değil, düzeltmek istediğin hata sayısına bağlı.
Listeyi üç kez göndermek yerin üç katına çıkması demekti; burada fazlalık neredeyse sıfıra iniyor.
Bir de şöyle görebilirsin: iki noktadan tek bir doğru geçer. Ben sana bir doğrunun beş noktasını göndereyim. Üçü yolda kaybolsun — kalan ikisini birleştir, aynı doğru geri geliyor. Hangi ikisinin kaldığı hiç fark etmez.
Bu kadar basit görünen numaranın endüstriyel halini bulmak, yüzyılın ortasını buldu. 1948'de Claude Shannon gürültülü bir kanaldan hatasız iletişimin mümkün olduğunu ispatladı — ama nasıl yapılacağını söylemedi. Bir şeyin var olduğunu kanıtlayıp elinize vermemek gibi. On yıllarca insanlar Shannon'ın çizdiği sınıra yaklaşmaya çalıştı.
Reed ve Solomon 1960'ta çözümü buldu: az önceki numaranın genelleştirilmiş hali — daha uzun listeler, daha çok kontrol sayısı, daha akıllı çarpanlar. Makale beş sayfaydı, güzeldi ve kullanılamazdı: kodu çözmenin verimli bir yolu yoktu. Teori doğruydu, hesap pratikte bitmiyordu. Berlekamp'ın algoritması 1968'de gelene kadar sekiz yıl daha bekledi. Ancak ondan sonra makineye girebildi.
Makineye girerken bir engel daha vardı — ve bu engel bizi bu kolun en eski ismine götürecek.
Ama bu aritmetik bir bayta sığmıyor
Güzel numaranın pratik bir problemi var. Bilgisayarlar veriyi baytlarla taşır — 0'dan 255'e kadar sayılar. 255 baytlık bir bloğun ağırlıklı toplamı, normal aritmetikle en fazla:
1×255 + 2×255 + ... + 255×255 = 8.323.200Bu 23 bit eder. Yani 1 baytlık veriyi korumak için 3 baytlık kontrol sayısı yazacaksın. Blok uzadıkça bu sayı da uzuyor. Sistem daha başlamadan çöktü.
"Mod 256 alalım" da işe yaramıyor. En doğal refleks bu: taşan kısmı at, kalanı sakla. Toplama için sorun yok, ama çarpma bozuluyor:
mod 256'da:
2 × 128 = 0 ← bilgi tamamen yok oldu
2 × 200 = 144
2 × 72 = 144 ← iki farklı sayı, aynı sonuçSonuç 144 geldiğinde girdinin 200 mü 72 mi olduğunu bilemiyorsun. Bölme yapamıyorsun.
Oysa hatanın yerini bulma numarası tam olarak bölmeye dayanıyordu: 4 ÷ 2 = 2. pozisyon. Bölme çalışmıyorsa numara çalışmıyor.
Çözüm: aritmetiği baştan tasarlamak
GF(256), şu şartları aynı anda sağlayan bir sayı dünyası: tam 256 eleman var ve hepsi bir bayta sığıyor; toplama, çıkarma, çarpma, bölme hepsi tanımlı; sonuç asla 255'i geçmiyor; ve sıfır olmayan her sayının böleni var — çarpma her zaman geri alınabiliyor.
Toplama = XOR. Elde taşıma yok, o yüzden taşma da yok:
200 = 11001000
100 = 01100100
XOR 10101100 = 172 ✓ tek baytÇıkarma da aynı işlem. a XOR b XOR b = a.
Çarpma biraz daha karmaşık: sayıyı polinom gibi çarpıp, sonucu sabit bir polinoma bölüp kalanı alıyorsun. Sonuç yine garantili tek bayt:
GF(256)'da:
200 × 100 = 79
172 × 231 = 159
2 × 128 = 29 ← artık sıfır değil, bilgi kaybolmuyor
2 × 200 = 141
2 × 72 = 144 ← farklı sonuçlar, karışmıyor
tüm 65.536 çarpımın maksimumu: 255Ve bölme gerçekten çalışıyor:
79 ÷ 100 = 200 ✓ geri geldikPeki bu sayı dünyasını kim kurdu? İşte söz verdiğim en eski isim. Évariste Galois, 1832'de, yirmi yaşında, bir düelloda öldü. Uğraştığı soru bugünkü gözle tamamen soyuttu: hangi denklemler kök alma işlemleriyle çözülebilir, hangileri çözülemez? Bunun için sayıların değil, simetrilerin yapısını incelemek gerektiğini gördü. Sonlu cisimler — GF harflerinin açılımı Galois Field — o incelemenin yan ürünüydü. Reed ve Solomon'un 1960'ta raftan aldığı alet, 128 yıldır orada duruyordu.
Adamın aklında ne çizik plastik vardı ne uzaydan gelen sinyal. Sadece bir denklem sorusu.
Bu sahneyi burada donduralım. Elimizde bozuk veriyi kurtarabilen bir cebir var — ama okuyacak bir şey yok. Şimdi bambaşka bir yere gidiyoruz.
Kaybolan ve kalan
Önünde bir kare var. Ona tam karşıdan bakıyorsun: dört eşit kenar, dört dik açı.
Şimdi başını yana eğ.
Artık kare değil. Kenarlar eşit değil, açılar dik değil. Ama hâlâ "o kare" olduğunu biliyorsun. Peki neyi biliyorsun tam olarak? Görüntüde değişen bunca şeyin arasında, elinde kalan ne?
Şekli eğdiğinde, döndürdüğünde, gerdiğinde, ölçeklediğinde hayatta kalan şey paralellik. Karenin karşılıklı kenarları paralelse, eğik görüntüsünde de paraleldir. Kare paralelkenara dönüşür — ama paralelkenar kalır.
Euler 1748'de bu akrabalığa bir isim verdi: affinis. Latince "akraba" demek. Şekli tanınmayacak hale getirebilirsin, akrabalık durur.
Bu dönüşümün cebiri şöyle görünüyor:
x' = a·x + b·y + c
y' = d·x + e·y + fAltı katsayı. Yani altı bilinmeyen.
Ve şimdi güzel kısım: bozulmuş görüntüde bir noktanın nerede olduğunu biliyorsan, bu sana iki denklem verir — biri x için, biri y için. Üç nokta = altı denklem. Tam oturuyor. Ne eksik ne fazla.
Bir affine bozulmayı geri almak için üç referans noktası yeterlidir. Bu sayıyı bir kenara yaz.
Affine'in yapamadığı tek şey
Affine dönüşüm çok şey yapar ama bir şeyi yapamaz: derinlik.
Karşıdan bakarken sorun yok. Ama gerçekten eğik bakıyorsan — yukarıdan, yandan, aşağıdan — uzak kenar yakın kenardan kısa görünür. Paralel çizgiler artık paralel değildir; ufuk noktasına doğru yakınsarlar.
Tren rayları. Affine dönüşüm tren raylarını çizemez.
Bunun için bir üst basamak gerekiyor: homografi, yani projektif dönüşüm.
x' = (a·x + b·y + c) / (g·x + h·y + 1)
y' = (d·x + e·y + f) / (g·x + h·y + 1)Payda geldi. Ve paydayla birlikte iki yeni bilinmeyen: g ve h. Toplam sekiz.
Sekiz bilinmeyen, her nokta iki denklem → dört nokta gerekiyor. Üç yetmiyor.
Perspektif bozulmayı geri almak için dört nokta gerekir. İkinci sayıyı da yaz.
Bu denklemleri yazabilmek için önce birilerinin perspektifi ciddiye alması gerekiyordu — ve ilk ciddiye alanlar matematikçiler değildi. Brunelleschi ve Alberti, 1400'lerde perspektifi teori için değil, resim yapabilmek için çözdüler. Duvara üç boyutlu bir sahneyi nasıl doğru çizersin? Homografinin ilk pratik kullanımı bir sanat atölyesinde oldu.
Matematiğin konuyu geri alması dört yüzyıl sürdü ve hiç beklenmedik bir yerde oldu. Jean-Victor Poncelet, Napolyon'un Rusya seferinde esir düştü. Elinde kitap yokken, hapiste, sadece hatırlayabildiği geometriden başlayarak projektif geometriyi yeniden kurdu. 1822'de yayımlanan kitabı — serbest kaldıktan sonra çıktı — bu dönüşümleri bir disipline çeviren kitaptır.
Klein'ın tersten sorusu
Poncelet'nin açtığı alanda, elli yıl sonra, Felix Klein geometrinin ne olduğu sorusunu tersinden sordu.
Ona kadar geometri, "uzay nedir, nokta nedir, doğru nedir" diye tanımlanıyordu. Klein 1872'de bunun yerine şunu önerdi:
Bir geometri, hangi dönüşümler altında neyin değişmediğiyle tanımlanır.
Projektif geometride uzunluk gitti, açı gitti, paralellik bile gitti. Ama bu bir kayıp listesi değil — bir güç sıralaması. En tepedeki geometri, en vahşi bozulmadan bile bir şey kurtarabilen geometri.
Bu soru biçimini bir yerden tanıyor olabilirsin. Birinci sahnede GF(256)'yı kurarken aynısını sormuştuk: hangi kuralları korursam sayılar bir bayta sığar? Orada taşma feda edilip bölme kurtarılmıştı. Klein'ın hiyerarşisi de aynı pazarlık — uzunluğu feda et, paralelliği tut; onu da feda et, doğruluğu tut. İki sahne birbirinden habersiz — ama aynı türden bir soru soruyorlar.
Klein bu fikri 1872'de bir programa dönüştürdü. Ama ilk örneği ondan 1550 yıl önce yazılmıştı. İskenderiyeli Pappus, MS 320 civarında, bir doğru üzerindeki dört noktanın oluşturduğu çapraz oranın perspektif altında değişmediğini biliyordu. "Görüntü değişse de bazı oranlar sabit kalır" fikri neredeyse 1700 yaşında.
Pappus'tan Klein'a bu kolun hiçbir insanının aklında bir uygulama yoktu. Ne olabilirdi ki? Kamera yoktu.
İkinci sahne de burada donuyor. Elimizde iki sayı var — üç ve dört — ve "neyin değişmediği önemli" diyen bir fikir.
Japonya. Denso Wave — Toyota grubuna bağlı Denso'nun bir yan kuruluşu — otomotiv parçalarını takip etmek için bir şey arıyor. Barkod ~20 karakter alıyor ve yetmiyor.
Mühendisler bir kare desen tasarlıyorlar: siyah-beyaz modüllerden oluşan bir ızgara. Adı QR kodu olacak.
Ve tasarımın köşelerine bak:
Üç köşede büyük, iç içe geçmiş birer kare. Sağ altta küçük bir tane daha. Üç artı bir.
Üç büyük kare, affine'in altı bilinmeyenini çözen üç nokta. Sağ alttaki küçük kare, homografiye yükselmek için gereken dördüncü nokta.
Karelerin içinde, verinin arasına serpiştirilmiş kontrol baytları — dört sayılık listenin sonundaki 17 ve 43'ün torunları.
Köşelerdeki şekiller estetik değil. Bir denklem sisteminin boyutu.
Bir kol ızgarayı yerine oturtuyor, öbür kol ızgaradaki hasarı onarıyor. Projektif geometri okumayı, sonlu cisimler kurtarmayı sağlıyor. İkisi de raftan hazır alındı — mühendislerin ne Galois'nın denklemleriyle ne Poncelet'nin esaretiyle ilgilenmesi gerekti.
Yarım saniyede olan on üç şey
Sokak satıcısının tezgâhında laminatlı bir kağıt duruyor. Kenarı yırtık, üstünde yağ lekesi var, güneşten solmuş. Telefonu eğik tutuyorsun — kimse dosdoğru tutmaz — ve yarım saniye sonra ödeme ekranı açılıyor.
O yarım saniyede olan şey şu:
1. Gri tonlama
2. Eşikleme ← kontrast kararı burada
3. Köşedeki 3 hedef kareyi bul (1:1:3:1:1 oranı)
4. Yön / dönüklük
5. Zamanlama deseni → kaç modül var
6. Hizalama desenleri → perspektif düzeltme
7. Izgarayı kur, her modülün merkezini oku
──────────── buraya kadar geometri sahnesi ────────────
8. Format bilgisi
9. Maskeyi kaldır
10. Zigzag sırayla veri modüllerini oku
11. Blokları ayrıştır (de-interleave)
12. Reed-Solomon
13. Metni çöz
──────────── burası cebir sahnesi ────────────Şimdi bu adımların içine biraz daha yakından bakalım — çünkü iki sahnenin parmak izleri her yerde.
Küçük kod, küçük hata
Versiyon 1'de (21×21) hiç hizalama deseni yok. Çünkü kod o kadar küçük ki, affine ile yapılan hata en uzak köşede bile yarım modülü geçmiyor. Izgara yine doğru hücreye düşüyor. Dördüncü noktayı koymak boşa yer harcamak olurdu.
Kod büyüdükçe sapma birikiyor:
| Versiyon | Boyut | Hizalama deseni |
|---|---|---|
| 1 | 21×21 | 0 |
| 2–6 | 25–41 | 1 |
| 7–13 | 45–69 | 6 |
| 14–20 | 73–97 | 13 |
| 35–40 | 157–177 | 46 |
Büyük kodlarda desenler bir ızgara oluşturuyor. Artık tek bir global homografi bile yetmiyor — her bölge için ayrı yerel dönüşüm hesaplanıyor. Sebebi pratik: kod düz olmayabilir. Şişe etiketine, buruşuk kağıda, kavisli ambalaja basılmış olabilir. Hiçbir tek dönüşüm eğri bir yüzeyi düzleştiremez — ama parça parça yaklaşırsan olur.
Ve okuyucu Klein'ın hiyerarşisinde basamak basamak çıkıyor. ZXing gibi gerçek çözücülerdeki sıra şöyle: önce üç hedef kareyi bul; affine kur ve dördüncü köşenin nerede olması gerektiğini tahmin et; o tahminin etrafında küçük bir alanda hizalama desenini ara; bulunca homografiye yükselt.
Affine, atılıp bir kenara konan bir ara adım değil. Dördüncü noktayı bulabilmek için önce kaba bir haritaya ihtiyaç var.
Pappus'un torunu
Bir tavuk-yumurta problemi var: hedef kareleri bulmak için dönüşümü bilmen lazım, dönüşümü hesaplamak için hedef kareleri bulman lazım.
Çözüm, geometrinin kendisinde saklı. Hedef karenin merkezinden geçen herhangi bir doğru boyunca renk uzunlukları hep aynı oranda:
Yani desen, dönüşümü henüz bilmezken bile tanınabilecek şekilde tasarlanmış. Tarayıcı görüntüyü satır satır süpürüp bu oranı arıyor — kod ters mi, eğik mi, uzak mı, hiç fark etmiyor. Oran orada.
"Görüntü değişse de bazı oranlar sabit kalır." Pappus bunu 320'de yazmıştı. 1994'te birileri aynı fikri bir tasarım kararına çevirdi: bu şeklin nasıl göründüğü değil, hangi özelliğinin sabit kaldığı önemli.
Karelerin içinde ne var
Izgara oturdu, sıra okumaya geldi. Bir kare tam olarak bir bit taşıyor: siyahsa 1, beyazsa 0. İnsanların burada takıldığı iki nokta var.
Piksel ≠ kare. En küçük birime modül deniyor ve ekranda ya da baskıda genelde tek piksel değil:
1 modül (1 bit) = ████
████ ← ekranda 16 piksel olabilir
████
████Sebebi basit: kameranın rahatça ayırt edebilmesi. Yani "bir piksel bir bitten fazla taşıyor" değil — birçok piksel bir araya gelip tek bir biti taşıyor. Tam ters yönde.
Bit ≠ harf. Bir harf tek kareye sığmaz:
"A" = 01000001
░█░░░░░█ ← 8 ayrı kareİçinde 100 harflik bir adres olan kod en az 800 kare ister. En küçük QR kodu 21×21 = 441 kare; sabit işaretler çıkınca veriye 26 bayt kalıyor, onun da 7'si kontrol baytı. Elde kalan: 19 harf civarı. En büyük kod 177×177 = 31 bin küsur kare, ancak birkaç bin karakter taşıyabiliyor.
Format bilgisi neden ilk okunuyor?
Bir tavuk-yumurta problemi daha. Veri modüllerini okuyabilmek için maskenin hangisi olduğunu bilmen lazım; maskeyi öğrenmek için de bir şey okuman lazım.
Çözüm: sol üst hedef karenin hemen yanında duran 15 bitlik küçük bir alan. İçinde sadece 5 bit gerçek bilgi var — 2 bit hata düzeltme seviyesi, 3 bit maske numarası. Kalan 10 bit tamamen koruma. Bu alan Reed-Solomon değil, BCH kodu kullanıyor ve 3 bitlik hatayı düzeltebiliyor. Üstelik iki ayrı yere kopyalanmış. 5 bit için abartılı görünüyor — ama burası giderse tüm kod ölür.
Maskenin işi görsel. Veri alanı ham haliyle yazılmıyor; sabit bir desenle XOR'lanıyor. Amaç: kodun içinde kocaman düz siyah/beyaz alanlar oluşmasın (kamera ızgarayı kaybeder) ve veri alanında yanlışlıkla hedef karelere benzeyen bir şekil çıkmasın. Kodlayıcı sekiz maskeyi de dener, en dengeli görüntüyü seçer, numarasını format bitlerine yazar.
Sonra veri modülleri, iki modül genişliğinde sütunlar halinde, sağ alttan başlayıp yukarı-aşağı zikzak çizerek okunuyor. Çıkan bayt dizisi doğrudan Reed-Solomon'a gitmiyor — önce de-interleave ediliyor: büyük kodlarda veri bloklara bölünmüş ve bloklar birbirine karıştırılarak yazılmış. Amaç şu: tek bir yerdeki büyük leke, tek bir bloğu tamamen öldürmek yerine birçok bloğun birer baytını götürsün.
QR'ın kullandığı GF(256) polinomu bu arada 0x11D — cebir sahnesindeki çarpım tabloları o polinomla hesaplandı.
Ne kadar koruma, ne pahasına
| Seviye | Kurtarabildiği | Anlamı |
|---|---|---|
| L (Low) | ~%7 | az koruma, çok veri |
| M (Medium) | ~%15 | varsayılan |
| Q (Quartile) | ~%25 | sağlam |
| H (High) | ~%30 | kodun üçte biri gitse bile okunur |
Karşılığında verdiğin şey yer. Kontrol sayıları da karelerde duruyor. En küçük kodda (toplam 26 bayt) bölüşüm şöyle:
H seviyesinde kodun üçte ikisi kontrol baytı. Ortasına logo koyulmuş kodların neden H seviyesinde olduğunu da bu tablo açıklıyor: logo, kodun ortasını yiyen kasıtlı bir hasar.
Neden kazandı
Denso Wave patenti aldı — ve kullanmamayı seçti. Standarda uyan herkes bedava üretebilir, bedava okuyabilir. Lisans yok, telif yok, izin yok. Rakip 2B barkodların çoğu bu kadar açık değildi. Ücretsiz olan bir şey, iyi olan bir şeyi neredeyse her zaman yener.
Teknik tarafta da doğru kararlar vardı. Her açıdan okunur: üç hedef kare sayesinde kodu ters tutsan da olur; barkodu hizalaman gerekir. Kapasite: 20 karakter yerine binlerce. Hırpalanmaya dayanır: kirli, buruşuk, üstü çizik kod bile okunur. Ölçeklenir: aynı desen tırnak kadar da basılır, bina duvarına da.
Ama asıl güç ekonomik:
Kod üretmek : bedava, birkaç milisaniye
Kodu basmak : mürekkep, birkaç mm²
Kod tarafında : elektrik yok, pil yok, çip yok, ağ yok
Okuyucu : zaten herkesin cebindeFiziksel dünyadan dijitale köprü kurmanın bilinen en ucuz yolu. NFC çip ister, uygulama ister, uyumlu telefon ister. QR sadece mürekkep ister. Kağıda, ekrana, cama, kumaşa, ekmeğe basılabiliyor.
İki dalga onu altyapıya çevirdi. Çin: WeChat ve Alipay 2014'ten itibaren ödemeyi tamamen QR üzerine kurdu — sokak satıcısının POS cihazına ihtiyacı yok, laminatlı bir kağıt yeterli. Pandemi: 2020'de menüler, giriş kayıtları, aşı belgeleri QR'a taşındı; dünyanın geri kalanı da kod okutmayı refleks haline getirdi.
Kapanış: 1674 yıl ve 162 yıl
İki sahneyi tek zaman çizgisine koyalım:
Geometri kolu 320'de Pappus ile başlayıp 1994'te bitiyor: 1674 yıl. Cebir kolu 1832'de Galois ile başlayıp 1994'te bitiyor: 162 yıl.
Yakın zamanda işler hızlanmış gibi görünüyor. Ama geometri kolunun uzunluğu asıl şeyi söylüyor:
Bir fikrin ne zaman işe yarayacağını kimse bilmiyor.
Pappus çapraz oranı yazarken kamera yoktu. Poncelet hapishanede geometriyi baştan kurarken aklında hiçbir uygulama yoktu. Galois sonlu cisimleri kurarken dijital iletişim yoktu — elektrik bile yoktu. Reed ve Solomon makaleyi yazdıklarında kendi kodlarını çözecek bir algoritma bile yoktu.
Hiçbiri "bunun bir gün ne işe yarayacağını" savunmak zorunda kalmadı — ya da kaldıysa bile doğru cevabı veremezdi. Cevap yüzyıllar sonra, bir Japon otomotiv fabrikasında, plastik parçaların üstünde ortaya çıktı.
Başa dönelim. Bir liste bozuk geliyor; ama iki fazladan sayı gerçeği geri getiriyor. Bir kareye eğik bakıyorsun; hiçbir şey durduğu yerde durmuyor ama bir şey kalıyor. İki soru, iki ayrı yüzyıl, iki ayrı gelenek.
Yağ lekeli kağıt yarım saniyede açılıyor. İkisi birden orada.
0x11D.