TR

Hata algılama ve düzeltme kodları

Eşlik, Hamming kodu, Hamming uzaklığı, sağlama toplamları ve CRC

Sayı sistemleri: İkili ve onaltılı Gray kodu BCD kodları Kayan ve sabit nokta Eşlik, Hamming ve CRC

Eşlik biti

Veri

Hamming kodu

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.

Veri

eşlik · veri · genel eşlik · değişen bit.

İki sözcük arasındaki Hamming uzaklığı

Sözcükler

CRC ve sağlama toplamı hesaplayıcı

Ç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.

Çerçeve

Adım adım CRC: polinom bölmesi

Bölme

Neden gerekirler

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:

Hamming uzaklığı

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:

\[ d - 1 \text{ hataya kadar algılar} \qquad \left\lfloor \frac{d-1}{2} \right\rfloor \text{ hataya kadar düzeltir} \]
KodEn küçük uzaklıkAlgılarDüzeltir
Artıklıksız veri1hiçbir şeyhiçbir şey
Eşlik biti, 5’te 221 hatahiçbir şey
Hamming32 hata1 hata
Genel eşlikli Hamming (SECDED)43 hata1 hata, 2’sini algılar
Her biti 3 kez tekrarlamak32 hata1 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.

Eşlik

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.

Hamming kodu

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:

\[ 2^{r} \ge m + r + 1 \]
Örnek: 1011 verisiyle Hamming (7, 4)

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.

KodVeri bitleriEşlik bitleriVerim
Hamming (7, 4)43%57
Hamming (15, 11)114%73
Hamming (31, 26)265%84
Hamming (63, 57)576%90
SECDED (72, 64), ECC bellek648%89

SECDED: birini düzelt, ikisini algıla

İ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.

Sağlama toplamları

Hızlıdır ve programlanması kolaydır ama aynı boydaki bir CRC’den çok daha kötü algılar.

CRC (döngüsel artıklık denetimi)

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.

Örnek: 1011 üreteciyle (\(x^3 + x + 1\)) 11010011101100 iletisi

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:

Aynı «CRC-16» neden farklı sayılar verir

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.

Endüstride CRC

Diğer düzeltici kodlar

İlgili: ikili ve onaltılı dönüştürücü, 5’te 2 kodu ve mantık kapısı simülatörü (XOR).