Hata düzelten kodlar açıklandı
Hiçbir kanal kusursuz değildir. Kozmik ışınlar bellekteki bitleri çevirir, çizikler bir diskin bazı kısımlarını siler ve radyo sinyalleri zayıflar. Dijital sistemler en iyisini ummak yerine akıllıca bir şekilde fazlalık ekler; böylece alıcı, bir kısmı hatalı ulaşsa bile neyin gönderildiğini çıkarabilir. 1940'ların sonunda başlayan bu kodların matematiği, sakladığımız ya da gönderdiğimiz neredeyse her biti sessizce korur.
Eşlikle hata algılama
En basit koruma tek bir eşlik bitidir: toplam 1 sayısı çift olacak şekilde bir 1 ya da 0 eklenir. Yolda bir bit ters dönerse sayı tek olur ve alıcı bir şeylerin yanlış gittiğini anlar. Eşlik hangi bitin hatalı olduğunu söyleyemez ve iki çevirme birbirini götürerek fark edilmeden kalır; ama ucuzdur ve onlarca yıl bellekte ve seri bağlantılarda kullanılmıştır. Yine de bir hatayı algılamak işin yalnızca yarısıdır: ardından verinin yeniden gönderilmesi gerekir.
Tekrarlayarak düzeltme
Bir hatayı yeniden sormadan düzeltmek için alıcının onu oy çokluğuyla bastıracak kadar fazlalığa ihtiyacı vardır. Her biti üç kez, 000 ya da 111 olarak göndermek alıcının çoğunluğa uymasını sağlar: üçlüdeki tek bir çevirme düzeltilir. Bedeli ağırdır: her veri biti için üç bit, üstelik aynı üçlüdeki iki çevirme yine kazanır. Kodlama kuramını başlatan soru, bundan daha iyisinin yapılıp yapılamayacağıydı.
Hamming'in kodu
Richard Hamming 1947'de Bell Labs'te programları delikli kartlardan okuyan bir röle bilgisayarı üzerinde çalışıyordu. Makine hafta sonu bir hata bulduğunda basitçe duruyordu ve Hamming pazartesi günü boşa gitmiş çalışmalarla karşılaşıyordu. Bir makine bir hatayı algılayabiliyorsa, diye sordu, neden yerini bulup düzeltemesin? 1950'de yayımlanan yanıtı 4 veri bitini 7 bit olarak gönderir. 1, 2 ve 4. konumlardaki üç eşlik bitinin her biri, üst üste binen farklı bir konum grubunu kontrol eder; gruplar, her tek hatanın kontrollerin benzersiz bir bileşimini bozacağı şekilde seçilmiştir.
Sendrom
Alıcı üç kontrolü yeniden hesaplar. Hepsi tutuyorsa sözcük kabul edilir. Bazıları tutmuyorsa, tutmayan kontroller en yüksek basamak 4 numaralı kontrol olacak şekilde ikili basamaklar olarak yazıldığında 1 ile 7 arasında bir sayı elde edilir: sendrom; bu sayı tam olarak ters dönen bitin konumudur. Biti geri çevirmek kod sözcüğünü geri getirir. Bu hile işe yarar, çünkü konumlar her birinin ikili açılımı ait olduğu kontrolleri listeleyecek biçimde numaralandırılmıştır; kodun üst üste binen üç daire olarak çizildiğinde bu kadar düzenli görünmesinin nedeni de budur.
Hamming uzaklığı
İki sözcük arasındaki Hamming uzaklığı, farklı oldukları konumların sayısıdır. (7,4) kodunda herhangi iki kod sözcüğü arasındaki uzaklık en az 3'tür. Tek hatalı bir sözcük, gönderilen kod sözcüğüne hâlâ 1 uzaklıktadır ve diğer tüm kod sözcüklerine en az 2 uzaklıktadır; bu yüzden en yakın kod sözcüğüne çözümlemek hatayı düzeltir. Genel olarak, kod sözcükleri arasındaki uzaklık en az d olan bir kod d − 1 hatayı algılar ve (d − 1)/2 hatayı, aşağı yuvarlanmış olarak, düzeltir. Genel bir eşlik biti eklemek uzaklığı 4'e çıkarır ve bir hatayı düzelten, iki hatayı algılayan genişletilmiş kodu verir.
Shannon sınırı
1948'de, Hamming'in makalesinden iki yıl önce, Claude Shannon şaşırtıcı bir teorem kanıtladı. Her gürültülü kanalın bir kapasitesi vardır ve yeterince uzun kodlar kullanılarak veri, bu kapasitenin altındaki her hızda istendiği kadar az hatayla gönderilebilir; kapasitenin üstünde hatalardan kaçınılamaz. Shannon bu tür kodların var olduğunu gösterdi ama nasıl kurulacaklarını göstermedi. Onun sınırına yaklaşan pratik kodları bulmak, 1960'taki Reed-Solomon kodlarından 1993'teki turbo kodlara ve düşük yoğunluklu eşlik denetimi kodlarının yeniden keşfine kadar yarım yüzyıl sürdü.
Her yerde kodlar
Reed-Solomon kodları CD'lerin çiziklere rağmen çalmasını ve QR kodlarının sembolün %30'una kadarı hasar görmüşken okunmasını sağlar. Sunucu belleği, kozmik ışınların neden olduğu tek bit çevrilmelerini düzeltmek için genişletilmiş Hamming kodlarını kullanır. Voyager'ın dış gezegenlerden çektiği fotoğraflar Golay, daha sonra da Reed-Solomon kodlarıyla korundu; 5G ve Wi-Fi'ın LDPC ve polar kodları ise kanalın izin verdiği neredeyse her biti sıkıp çıkarır. Bir kitabın üzerindeki barkod ve bir banka hesap numarasının son hanesi bile basit hata algılayan kodlardır.
Keşfedin
Herhangi dört veri bitini Hamming (7,4) koduyla kodlamak, dairelerde ya da satırda tıklayarak bitleri ters çevirmek ve kod çözücü onarmadan önce tutmayan dairelerin ve sendromun hatayı gösterişini izlemek için hata düzelten kod simülatörünü açın. Çift hataların algılandığını görmek için ek eşlik bitini açın ve kodlu ve kodsuz ulaşanı karşılaştırmak için gürültülü bir kanaldan bir mesaj gönderin.
Sık sorulan sorular
Hata algılama ile hata düzeltme arasındaki fark nedir?
Algılama alıcıya yalnızca bir şeylerin yanlış olduğunu söyler, bu yüzden alıcı veriyi yeniden istemek zorundadır; bir eşlik biti ya da sağlama toplamı bunu yapar. Düzeltme ise alıcının sormadan orijinali yeniden oluşturmasını sağlar; bu da daha fazla fazlalık gerektirir. Milyonlarca kilometre uzaktaki bir uzay sondası ya da bir DVD gibi yeniden soramayan sistemler düzeltmeye dayanır.
Neden her şey sadece iki kez gönderilmiyor?
İki kopya bir hata olduğunu gösterir ama hangi kopyanın doğru olduğunu göstermez ve maliyeti ikiye katlar. Üç kopya oy çokluğuna izin verir ama maliyeti üçe katlar. Hamming'in kodu, iki katından az bitle yedi bitlik her blokta tek bir hatayı düzeltir; daha uzun kodlar çok daha iyisini yapar.
Richard Hamming kimdi?
Manhattan Projesi'nde, ardından otuz yıl boyunca Bell Labs'te çalışan Amerikalı bir matematikçi (1915–1998). Kodlarının yanı sıra sinyal işlemedeki Hamming penceresi, Hamming uzaklığı ve You and Your Research adlı konferansıyla tanınır. 1968'de Turing Ödülü'nü aldı.
Bir kod istenen sayıda hatayı düzeltebilir mi?
Yalnızca yeterli fazlalıkla. Bir kod blok başına en fazla (d − 1)/2 hatayı düzeltebilir; burada d, kod sözcükleri arasındaki en küçük uzaklıktır ve daha çok kontrol biti içeren daha uzun kodlar daha büyük d değerlerine ulaşır. Nihai sınırı Shannon teoremi koyar: hiçbir kod kanalın kapasitesini aşamaz.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Hata düzelten kod simülatörünü aç