Eşlik, Hamming kodu, Hamming uzaklığı, sağlama toplamları ve CRC
Veri bitlerini yazın; eşlik bitleri hesaplanır. Sonra bir iletim hatasıymış gibi değiştirmek için sözcüğün herhangi bir bitine tıklayın ve alıcının ne yaptığını görün: sendrom hatalı bitin konumunu verir. Bir ve iki hatayla, genel eşlik bitiyle ve onsuz deneyin.
eşlik · veri · genel eşlik · değişen bit.
Çerçeveyi onaltılı baytlar (boşluklu ya da boşluksuz) veya metin olarak yazın. «Çerçevede» sütunu baytları gönderilme sırasıyla verir.
Hiçbir kanal kusursuz değildir: bir sürücünün yanından geçen RS-485 çerçevesi, bir parçacığın çarptığı bellek biti ya da diskteki bir çizik bir 0’ı 1’e çevirebilir. Bunu fark etmek için verici, verilere onlardan hesaplanan birkaç artıklık biti ekler ve alıcı hesabı tekrarlar. Tutmazsa iki strateji vardır:
Aynı uzunluktaki iki sözcük arasındaki Hamming uzaklığı, farklı oldukları bitlerin sayısıdır: 1011101 ile 1001001 arasında 2’dir. Bir kodun en küçük uzaklığı \(d\), herhangi iki geçerli sözcük arasındaki en küçük uzaklıktır ve kodun neler yapabileceğini belirler:
| Kod | En küçük uzaklık | Algılar | Düzeltir |
|---|---|---|---|
| Artıklıksız veri | 1 | hiçbir şey | hiçbir şey |
| Eşlik biti, 5’te 2 | 2 | 1 hata | hiçbir şey |
| Hamming | 3 | 2 hata | 1 hata |
| Genel eşlikli Hamming (SECDED) | 4 | 3 hata | 1 hata, 2’sini algılar |
| Her biti 3 kez tekrarlamak | 3 | 2 hata | 1 hata (çoğunlukla) |
Fikir geometriktir: geçerli sözcükler arasında en az 3 uzaklık varsa, tek hatalı bir sözcük yine de özgün sözcüğe diğerlerinden daha yakındır.
En basit koddur: toplam 1 sayısı çift (çift eşlik) ya da tek (tek eşlik) olsun diye bir bit eklenir. Tek sayıdaki her hatayı algılar ama aynı anda değişen iki biti algılamaz. Seri portların eşliğidir (8E1, 8 veri biti, çift eşlik ve 1 dur biti demektir; Modbus RTU varsayılan olarak çift eşlik kullanır) ve bazı eski belleklerde kullanılır. Devrede bir XOR kapısı zinciriyle hesaplanır.
İki boyutlu eşlikte veriler bir tabloya dizilir ve her satırın ve her sütunun eşliği eklenir. Tek bir hata bir satırın ve bir sütunun eşliğini değiştirir; kesiştikleri yer düzeltilecek biti gösterir.
Richard Hamming onu 1950’de, röleli makinelerin arızalarının hafta sonu hesaplarını bozmasından bıktığı için tasarladı. Sözcüğün konumları 1’den başlayarak numaralanır; 2’nin kuvveti olanlar (1, 2, 4, 8…) eşlik bitlerini, geri kalanlar veriyi taşır. Her eşlik biti \(p_k\), numarasının ikili yazılışında \(k\) ağırlıklı biti 1 olan konumları kapsar: \(p_1\) 1, 3, 5, 7…; \(p_2\) 2, 3, 6, 7…; \(p_4\) 4–7, 12–15… konumlarını kapsar. \(r\) eşlik bitiyle \(m\) veri biti şu koşulla korunur:
Veri 3, 5, 6 ve 7. konumlara yerleşir. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) ve \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). Gönderilen sözcük \(0110011\)’dir. \(0110111\) gelirse (5. konum bozuk), alıcı aldığı sözcük üzerinden üç eşliği yeniden hesaplar: \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). Sendrom \(s_4 s_2 s_1 = 101_2 = 5\) tam olarak hatanın konumudur ve o biti ters çevirmek yeter.
| Kod | Veri bitleri | Eşlik bitleri | Verim |
|---|---|---|---|
| Hamming (7, 4) | 4 | 3 | %57 |
| Hamming (15, 11) | 11 | 4 | %73 |
| Hamming (31, 26) | 26 | 5 | %84 |
| Hamming (63, 57) | 57 | 6 | %90 |
| SECDED (72, 64), ECC bellek | 64 | 8 | %89 |
İki hatada basit Hamming sıfırdan farklı bir sendrom verir ve doğru olan bir biti «düzelterek» sözcüğü daha da bozar. Bunu önlemek için tüm sözcük üzerinde bir genel eşlik biti P eklenir (single error correction, double error detection):
Sunuculardaki ECC belleğin ve otomotiv ile güvenlik amaçlı birçok mikrodenetleyicinin şemasıdır: her 64 veri biti için 8 denetim biti.
Hızlıdır ve programlanması kolaydır ama aynı boydaki bir CRC’den çok daha kötü algılar.
CRC iletiyi katsayıları 0 ve 1 olan bir polinom olarak ele alır (\(1011 = x^3 + x + 1\)) ve onu \(r\) dereceli bir üreteç polinomuna böler. Bu aritmetikte (mod 2) toplama ve çıkarma özel VEYA ile aynıdır ve elde yoktur. Verici iletiye \(r\) sıfır ekler, böler ve kalanı onların yerine gönderir; alıcı tüm çerçeveyi böler ve hata yoksa kalan 0 olur.
3 sıfır eklenir ve solda kalan her 1’in altına üreteç çıkarılarak (XOR) bölünür. Kalan 100’dür; bu yüzden 11010011101100100 gönderilir. Yukarıdaki hesaplayıcıda yüklü olan örnek budur.
\(r\) dereceli iyi bir polinomla CRC şunları algılar:
Polinomun yanı sıra her CRC; yazmacın başlangıç değerini, her baytın bitlerinin yansıtılmış olarak girip girmediğini (bir UART’tan çıktıkları gibi en az anlamlı bitten başlayarak), sonucun yansıtılıp yansıtılmadığını ve son özel VEYA’nın hangi değerle yapıldığını belirler. Bu yüzden CRC-16/MODBUS, CRC-16/ARC ve CRC-16/CCITT aynı veriyle farklı sonuçlar verir. Bir cihazın hangisini kullandığını anlamak için 123456789 metninin CRC’si hesaplanır ve denetim değeriyle karşılaştırılır: Modbus için 4B37, CCITT-FALSE için 29B1, CRC-32 için CBF43926.
İlgili: ikili ve onaltılı dönüştürücü, 5’te 2 kodu ve mantık kapısı simülatörü (XOR).