unscratchable

Aşağıda, bir kompakt diskin, bir QR kodun ya da derin uzay sondasının saklayacağı gibi saklanmış bir mesaj var. Fırçayı al ve onu oy. Sertçe karala. Bıraktığında, matematiğin ne yaptığını izle.

Below is a message stored the way a compact disc, a QR code, or a deep-space probe would store it. Take the brush and gouge it. Scribble hard. When you let go, watch what the mathematics does.

Çözücüye hayatta kalanlardan başka hiçbir şey gösterilmedi. Yok ettiğin baytlar gitmişti ve geriye kalan, eksik her baytı adlandırmaya ve değerlerinin her birini yeniden var etmeye yetecek kadar yapı taşıyordu. Alttaki o altın şerit bir yedek değil — çok daha tuhaf bir şey; bu denemenin sonunda nasıl çalıştığını tam olarak bileceksin. (Sayfa aslıyı bellekte tutar — ama yalnızca çözücüyü yalan söylerken yakalamak ve sıfırlama düğmesine hizmet etmek için. İyileşmek için ona asla başvurulmaz.)

The decoder was shown nothing but the survivors. The bytes you destroyed were gone, and what remained held enough structure to name every missing byte and compute every one of their values back into existence. That golden strip at the bottom is not a backup — it is something far stranger, and by the end of this essay you will know exactly how it works. (The page does keep the original in memory — but only to catch the decoder ever lying, and to serve the reset button. It is never consulted to heal.)

Baştan dürüst bir açıklama: yüzey, çözücüye nerede çizildiğini söyler — tıpkı bir CD çaların hangi çerçevelerin okunamaz döndüğünü bilmesi gibi. Adresi bilinen hasara silinti denir. Çözücünün hasarı önce bulması gereken sessiz bozulmayı onarmak tam iki kat pahalıdır. 7. bölüm bu iki katı hissettirir.

One honest disclosure up front: the surface tells the decoder where it was scratched — the way a CD player knows which frames came back illegible. Damage with known addresses is called an erasure. Silent corruption, where the decoder must find the damage first, costs exactly twice as much to fix. Chapter 7 lets you feel that factor of two.

Her ortam seni ele verir. Kozmik ışınlar RAM’de bit çevirir; çizikler lazerleri kör eder; termal gürültü yapılmış her telin üzerinde fısıldar. Fiziksel dünyanın sunacak temiz bir kanalı yok — yalnızca gürültülü olanları var. İşte böyle bir kanalı geçen beş harfli bir sözcük. Her bit yalnızca 1 − p olasılıkla hayatta kalır.

Every medium betrays you. Cosmic rays flip bits in RAM; scratches blind lasers; thermal noise whispers over every wire ever made. The physical world does not have a clean channel to offer — only noisy ones. Here is a five-letter word crossing such a channel. Each bit survives only with probability 1 − p.

%2 gürültüde bile — çizik bir diskten çok daha iyi bir kanal — 40 bitlik bir mesaj zamanın yarısından azında sağlam ulaşır. Ham veriyi dünyanın içinden göndermek mühendislik değildir. Duadır.

Even at 2% noise — a channel far better than a scratched disc — a 40-bit message arrives intact less than half the time. Sending raw data through the world is not engineering. It is prayer.

Besbelli çözüm, her insanın zaten bildiği şey: kendini tekrarla. Her biti üç kez gönder ve çoğunluk konuşsun. Bu gerçekten işe yarar — ilk hata düzelten koddur ve tüm konuyu minyatür hâlinde zaten içerir. Ama iki çirkin sorunu da var.

The obvious fix is the one every human already knows: repeat yourself. Send each bit three times and let the majority speak. This genuinely works — it is the first error-correcting code, and it already contains the whole subject in miniature. It also has two ugly problems.

Birinci sorun bedeldir: her biti üçe katlamak sana üçte biri işe yarayan bir disk kazandırır. İkinci sorun daha incelikli ve daha kötü: tekrar, fazlalığını aptalca harcar. Her biti tek başına korur, diğer bitlerden hiçbir şey öğrenmez; böylece aynı üçlüye gelen iki talihsiz darbe yine de geçer. Kodlama kuramının dörtte üç yüzyılı, özünde tek bir sorudur: fazlalık, her bit için ayrı ayrı yerine mesajın bütününe harcanabilir mi?

Problem one is the price: tripling every bit buys you a disk that is one-third useful. Problem two is subtler and worse: repetition spends its redundancy stupidly. It protects each bit in isolation, learning nothing from the other bits, so two unlucky hits on the same triple still get through. Three-quarters of a century of coding theory is, at heart, one question: can redundancy be spent on the message as a whole, instead of on each bit alone?

Fazlalığı akıllıca harcamak için önce onun ne satın aldığını görmen gerekir. Olası her 3 bitlik diziyi bir küpün köşesi olarak düşün; bir kenarı geçmek bir biti çevirir. Şimdi kod sözcüklerini — gerçekten göndermene izin verdiğin dizileri — 000 ve 111 seç: tekrar kodu, yeniden, yeni gözlerle.

To spend redundancy wisely, you first need to see what it buys. Picture every possible 3-bit string as a corner of a cube, where crossing one edge flips one bit. Now choose your codewords — the strings you actually allow yourself to send — to be 000 and 111: the repetition code again, seen with new eyes.

İki kod sözcüğü Hamming mesafesi 3’te durur — birini diğerine çevirmek için üç bit çevirmen gerekir. O boşluk, sırrın tamamıdır. Tek bir çevirme seni hâlâ yalandan çok gerçeğe yakın bırakır; dolayısıyla en yakın kod sözcüğü doğru olandır. Ve neredeyse fazlaca zarif bir şeyi fark et: iki çözme küresi küpü tam olarak döşer, her köşe tam olarak bir kod sözcüğüne aittir, boşluk yok, örtüşme yok. Bu kadar verimli kodlara kusursuz denir ve yok denecek kadar nadirdirler. Birazdan en ünlüsüyle tanışacaksın.

The two codewords sit at Hamming distance 3 — you must flip three bits to turn one into the other. That gap is the entire secret. One flip leaves you still nearer the truth than the lie, so the nearest codeword is the right one. And notice something almost too neat: the two decoding spheres tile the cube exactly, every corner claimed by exactly one codeword, no gaps, no overlaps. Codes this efficient are called perfect, and they are vanishingly rare. You are about to meet the most famous one.

1950’de Richard Hamming — her parite hatasında duran bir bilgisayara kurban giden hafta sonlarından bıkmış hâlde — fazlalığı örtüştürmenin bir yolunu buldu. Dört veri biti al. Üç parite biti ekle; her biri, kasıtlı olarak örtüşen farklı bir dörtlü konum ekibini gözetir. Toplam yedi bit, burada üç daire olarak çizildi.

In 1950, Richard Hamming — tired of weekends lost to a computer that halted at every parity error — found a way to make redundancy overlap. Take four data bits. Add three parity bits, each one watching a different, deliberately overlapping crew of four positions. Seven bits total, drawn here as three circles.

Tek bir biti çevir; üç parite kontrolü yalnızca şikâyet etmez — tanıklık eder. Kırık kontrolleri ikilik bir sayı olarak oku; çevrilen bitin konumunu hecelerler: hata, kendi adresini itiraf ettirilir. Bedele ne olduğuna da dikkat et: tekrar tek bir hatayı düzeltmek için %200 ek yük istiyordu; Hamming bunu %75’e yapar. Ve bu da bir başka kusursuz koddur — yarıçapı 1 olan küreleri 7-küpün 128 köşesinin tamamını tam döşeyen on altı kod sözcüğü.

Flip any single bit and the three parity checks do not merely complain — they testify. Read the broken checks as a binary number and it spells out the position of the flipped bit: the error is made to confess its own address. Note what happened to the price, too: repetition needed 200% overhead to fix one error; Hamming does it for 75%. And this is another perfect code — sixteen codewords whose radius-1 spheres tile all 128 corners of the 7-cube exactly.

Sendrom numarası küçük sayıların rastlantısı değildir. Hamming parite bitlerini 1, 2, 4 konumlarına — ikinin kuvvetlerine — yerleştirdi; böylece “hangi kontroller kırıldı” ile “hatanın ikilik adresi” aynı şey hâline gelir. Yapılmış en zarif adres yollarından biridir ve hiçbir şeyden ibarettir.

The syndrome trick is not a coincidence of small numbers. Hamming placed the parity bits at positions 1, 2, 4 — the powers of two — so that “which checks broke” and “binary address of the error” become the same thing. It is one of the most elegant address buses ever built, and it is made of nothing.

Hamming seni rastgele, yalnız bir bit çevrilmesine karşı zırhlandırır. Ama gerçek dünyanın aslında verdiği hasara bak: bir çizik, bir sürtük, bir parazit patlaması. Gerçek hasar diziler hâlinde gelir — ve bir hasar dizisi tek bir kod sözcüğüne yumruk gibi iner, sözcük başı her bütçeyi delip geçer. Çözüm, zekâdan başka hiçbir şeye mal olmaz: kod sözcüklerini yan yana saklama. Onları karıştır.

Hamming armors you against a random, lonely bit-flip. But look at the damage the real world actually deals: a scratch, a scuff, a burst of interference. Real damage arrives in runs — and a run of damage lands on one codeword like a fist, blowing straight through any per-word budget. The fix costs nothing but cleverness: don’t store codewords side by side. Shuffle them.

Harmanlama, bir CD’nin 2,5 milimetrelik bir oyuğu neden umursamadığının sebebidir: verisi öyle örülür ki diskteki komşu baytlar uzak kod sözcüklerine aittir. Çizik engellenmez. Seyreltilir — kodların en çok korktuğu hata deseninden, en iyi başa çıktıkları desene dönüştürülür. Bu sayfanın başındaki ana figür de aynı şekilde örülüdür; en çılgın karalaman bu yüzden birçok bloğa ince ince yayıldı.

Interleaving is why a CD shrugs off a 2.5-millimeter gouge: its data is braided so that neighboring bytes on the disc belong to distant codewords. The scratch is not prevented. It is diluted — converted from the error pattern codes fear most into the one they handle best. The hero at the top of this page is braided the same way, which is why your wildest scribble was spread thin across many blocks.

Geriye tek bir fikir kalır ve o da taçtaki mücevherdir. Hamming bitleri korur; çizikler ise bütün baytları yok eder. Bunun için bitlerden eğrilere sıçrarız. İşte herkesin okulda karşılaştığı, nihayet gerçek yüzüyle beliren olgu: üç nokta bir parabolü belirler — herhangi üç nokta.

One idea remains, and it is the crown jewel. Hamming protects bits; scratches destroy whole bytes. For that we jump from bits to curves. Here is the fact everyone meets in school, wearing its true face at last: three points determine a parabola — any three.

Reed–Solomon kodlarının fikrinin tamamı budur; Irving Reed ve Gustave Solomon tarafından 1960’ta beş sessiz sayfada yayımlandı. k mesaj baytını bir polinomun katsayıları olarak ele al. Onu n > k noktada değerlendir ve bunları gönder. Herhangi k hayatta kalan polinomu yeniden sabitler; diğer n − k tanesi saf, birbirinin yerine geçebilen yedeklerdir. Tek bir pürüz var — baytların içinden eğri çizmek, baytların temiz bölündüğü, yuvarlamanın ve sonsuzlukların olmadığı bir aritmetik gerektirir. Böyle bir aritmetik var: sonlu cisim GF(256); toplama XOR’dur ve sıfır olmayan 255 baytın her birinin tam bir tersi vardır. Figürün altındaki satır bir benzetme değil — bunlar gerçek baytlar, ana figürü zırhlayan aynı kodlayıcı tarafından hesaplandı. (Pratikte, bu sayfa dâhil, kod eşdeğer sistematik biçiminde kurulur — parite bir üreteç polinomundan, mesaj önde dokunulmadan gider — ama herhangi-k-hayatta-kalan güvencesi, iş tulumu giymiş aynı teoremdir.)

That is the entire idea of Reed–Solomon codes, published by Irving Reed and Gustave Solomon in 1960 on five quiet pages. Treat your k message bytes as the coefficients of a polynomial. Evaluate it at n > k points and send those. Any k survivors pin the polynomial back down; the other n − k are pure, interchangeable spares. There is one catch — drawing curves through bytes requires an arithmetic where bytes divide cleanly, no rounding, no infinities. Such an arithmetic exists: the finite field GF(256), where addition is XOR and every one of the 255 nonzero bytes has an exact reciprocal. The line under the figure is not an analogy — those are real bytes, computed by the same encoder that armors the hero. (In practice, this page included, the code is built in its equivalent systematic form — parity from a generator polynomial, message riding untouched in front — but the any-k-survivors guarantee is the same theorem wearing work clothes.)

Artık ilk karalamadan beri makinenin her parçası senin: baytlar GF(256) üzerinde polinom değerlendirmelerine dönüşür (6. bölüm), bloklar patlamalara karşı örülür (5), adresi bilinen hasarı düzeltmek bir yedeğe mal olurken sessiz bozulma ikiye mal olur (0 ve 4 — bir hatayı bulmak işin yarısıdır). İşte kaputu açık makine. Kendi mesajını yaz. Zırhı ayarla. Onu öldürmeyi dene.

Now you own every part of the machine from the first scribble: bytes become polynomial evaluations over GF(256) (chapter 6), blocks are braided against bursts (5), damage with a known address costs one spare to fix while silent corruption costs two (0 and 4 — finding an error is half the work). Here is the machine with the hood open. Write your own message. Tune the armor. Try to kill it.

Ve 0. bölümde kazıdığın sırrın tamamı bu: bir yedek değil, bir kopya değil — kasıtlı olarak fazla belirlenmiş, patlamalara karşı örülmüş, kendi yedek değerlendirmelerini zırh olarak giyen bir mesaj.

And that is the whole secret you scratched at in chapter 0: not a backup, not a copy — a message deliberately over-determined, braided against bursts, wearing spare evaluations of itself as armor.

R. W. Hamming, Error Detecting and Error Correcting Codes (1950) · I. S. Reed & G. Solomon, Polynomial Codes over Certain Finite Fields (1960) · E. R. Berlekamp, Algebraic Coding Theory (1968) · J. L. Massey, Shift-Register Synthesis and BCH Decoding (1969). Bu sayfadaki çözücü, yaklaşık üç yüz okunabilir satırda sendromlar → Forney sendromları → Berlekamp–Massey → Chien araması → Forney algoritması adımlarını uygular — kaynağı oku; her commit’te binlerce rastgele bozulmayla sınanır. Video için 3Blue1Brown’ın Hamming ikilisi harikadır. Daha derine inmek için Wikiversity’nin “Reed–Solomon codes for coders” rehberi klasik giriş rampasıdır.

R. W. Hamming, Error Detecting and Error Correcting Codes (1950) · I. S. Reed & G. Solomon, Polynomial Codes over Certain Finite Fields (1960) · E. R. Berlekamp, Algebraic Coding Theory (1968) · J. L. Massey, Shift-Register Synthesis and BCH Decoding (1969). The decoder in this page implements syndromes → Forney syndromes → Berlekamp–Massey → Chien search → Forney’s algorithm, in about three hundred readable lines — read the source; it is tested by thousands of random corruptions on every commit. For video, 3Blue1Brown’s Hamming pair is superb. For going deeper, the Wikiversity “Reed–Solomon codes for coders” guide is the classic on-ramp.