SEN2008 · 3. hafta · Data Link Layer Concepts (I) : error detection and correction, elementary protocols, sliding window protocols

Hata tespiti ve düzeltme: parity, checksum, CRC, Hamming

Link katmanının bit hatalarını nasıl yakaladığı: tek ve iki boyutlu parity, Internet checksum, CRC polinom bölmesi ve Hamming koduyla tek bit düzeltme. Sınavda hepsi elle hesap sorusu olarak gelir.

error detectionerror correctionparity bittwo-dimensional parityInternet checksumone's complementCRC (cyclic redundancy check)generator polynomialmodulo-2 arithmeticHamming codeHamming distancesyndromeburst errorFEC (forward error correction)

Fiziksel katman kusursuz değildir. Gürültü, parazit, zayıf sinyal bazı bitleri ters çevirir. Link katmanının ilk işi bu hataları tespit etmek (detection), bazen de düzeltmektir (correction). Sınavda bu konu neredeyse her zaman elle hesap sorusudur: “compute the CRC”, “compute the checksum”, “which bit is in error?”. Formül değil, prosedür ezberleyeceksin.

Altın kurallar:

Mod-2 aritmetik = XOR. Toplama ve çıkarma aynı, elde ve borç yok.
CRC’de veriye derece kadar sıfır ekle. Üreteç 4 bitse 3 sıfır.
Internet checksum’da elde biti başa döner (wraparound), en sonda bitler ters çevrilir.
Hamming sendromu hatalı bitin konumunu ikili olarak verir.

Tespit mi, düzeltme mi?

Göndericiye $D$ veri bitine ek olarak $EDC$ (error detection and correction) bitleri ekler. Alıcı $D'$ ve $EDC'$ ‘yi alır ve tutarlılığı kontrol eder. Hiçbir yöntem %100 garanti vermez; amaç yakalanmayan hata olasılığını çok küçültmektir.

Yöntem	Ek bit	Ne yapar	Nerede
Tek parity	1	Tek sayıda hatayı tespit	Basit seri hatlar
2D parity	satır + sütun + 1	Tek hatayı düzeltir	Öğretici örnek
Internet checksum	16	Tespit (zayıf)	IP, TCP, UDP başlıkları
CRC	$r$ (16, 32)	Güçlü tespit	Ethernet, Wi-Fi
Hamming	$\approx \log_2 m$	Tek hatayı düzeltir	Bellek (ECC RAM)

Hata düzeltme (FEC, forward error correction) alıcıya yeniden iletim istemeden düzeltme imkanı verir. Uydu gibi gecikmesi büyük linklerde değerlidir. Hata tespiti + yeniden iletim (ARQ) ise kısa gecikmeli linklerde daha ucuzdur. Yeniden iletimi bu haftanın ikinci sayfasında göreceksin.

Parity

Tek boyutlu parity. Veriye bir bit eklenir. Even parity’de toplam 1 sayısı çift, odd parity’de tek olur.

Veri 1011001  -> 1'ler: 4 (çift)
even parity biti = 0  -> 10110010
odd  parity biti = 1  -> 10110011

Tek bit ters dönerse parity bozulur ve hata yakalanır. İki bit ters dönerse parity yine tutar: çift sayıda hata kaçar. Hatalar genellikle ardışık (burst) geldiği için bu ciddi bir zaaf.

İki boyutlu parity. Veri bir tabloya yazılır, her satır ve her sütun için parity hesaplanır:

          c0 c1 c2 c3 | satır parity
satır 1:   1  0  1  1 |  1
satır 2:   0  1  1  0 |  0
satır 3:   1  1  0  0 |  0
-----------------------+---
sütun:     0  0  0  1 |  1   (köşe)

Satır 2, sütun 2’deki bit ters dönerse (0110 → 0100) satır 2 parity’si ve sütun 2 parity’si bozulur. Kesişim tek bir bit gösterir: hatalı bit bulunur ve düzeltilir.

TUZAK · dikdörtgen hatası. Bir dikdörtgenin dört köşesindeki bitler birlikte ters dönerse her satırda ve her sütunda iki değişiklik olur; bütün parity’ler doğru görünür. 2D parity bunu kaçırır.

Hamming mesafesi

İki bit dizisinin Hamming mesafesi, farklı oldukları bit sayısıdır (XOR’daki 1 sayısı). Bir kodun minimum mesafesi $d_{min}$ , geçerli iki kod sözcüğü arasındaki en küçük mesafedir.

$\text{tespit: } d_{min} \ge s + 1 \qquad \text{düzeltme: } d_{min} \ge 2t + 1$

$d_{min} = 3$ olan bir kod 2 hatayı tespit eder ya da 1 hatayı düzeltir. Sezgi: her geçerli sözcüğün etrafına yarıçapı $t$ olan bir küre çiz; küreler çakışmıyorsa en yakın geçerli sözcüğe “yuvarlayarak” düzeltebilirsin.

Internet checksum

IP, UDP ve TCP başlıklarında kullanılır. Veri 16 bitlik sözcüklere bölünür.

Sözcükleri topla. 16 biti aşan elde (carry) çıkarsa onu sonucun en altına ekle (wraparound, one’s complement toplama).
Toplamın tüm bitlerini ters çevir. Sonuç checksum’dır.
Alıcı bütün sözcükleri checksum dahil toplar. Hata yoksa sonuç 0xFFFF (bütün bitler 1) olur.

Çözümlü örnek

Sözcükler: 0x6E2B, 0x9C71, 0x13A5.

  6E2B
+ 9C71
------
 10A9C      17. bit taştı (elde = 1)
  0A9C + 1 = 0A9D        wraparound
+ 13A5
------
  1E42      taşma yok
checksum = ~1E42 = FFFF - 1E42 = E1BD

Alıcı: 6E2B + 9C71 + 13A5 + E1BD  ->  FFFF  (hata yok)

Checksum hesaplaması yazılımda ucuzdur ama zayıftır: örneğin iki sözcüğün yer değiştirmesini hiç fark etmez. Bu yüzden link katmanında daha güçlü CRC kullanılır.

CRC (cyclic redundancy check)

CRC’de bit dizileri polinomların katsayısı gibi düşünülür. Gönderici ve alıcı $r+1$ bitlik bir üreteç (generator) $G$ üzerinde anlaşır. Üretecin derecesi $r$ ‘dir.

Polinomdan bit dizisine: her dereceye bir bit, eksik dereceye 0.

x^3 + x + 1      = 1·x^3 + 0·x^2 + 1·x + 1  -> 1011
x^4 + x + 1      -> 10011
x^4 + x^3 + 1    -> 11001

Prosedür:

Veri $D$ ‘nin sonuna $r$ tane 0 ekle ( $D \cdot 2^r$ ).
Bunu mod-2 bölmeyle $G$ ‘ye böl. Her adımda baştaki 1’in altına $G$ ‘yi hizala, XOR al. Baştaki bit 0 ise bir sağa kay.
Son $r$ bit kalan $R$ ‘dir. Gönderilen: $D$ ardından $R$ .
Alıcı gelen $D R$ dizisini (sıfır eklemeden) $G$ ‘ye böler. Kalan 0 ise kabul, değilse hata.

Çözümlü örnek: $D$ = `11010110`, $G$ = `1011`

$r = 3$ , üç sıfır ekle. Her satırda bölünen diziyi XOR sonrası haliyle yazıyoruz:

11010110000        D + 000
1011               baştaki 1'e hizala, XOR
01100110000
 1011
00111110000
  1011
00010010000
   1011
00000100000        baştaki sıfırları atla
     1011
00000001100
       1011
00000000111        kalan R = 111 (son 3 bit)

Gönderilen: 11010110 111
Kontrol   : 11010110111 / 1011  -> kalan 000  (doğru)

İPUCU · hızlı kontrol. Kalan her zaman $r$ bittir (üreteçten bir bit kısa). Kalanın 4 bit çıktıysa bir yerde hizalamayı kaçırdın.

CRC neden güçlü?

$r$ dereceli üreteç, uzunluğu $r$ ‘den küçük ya da eşit bütün burst hataları yakalar. Ethernet’in CRC-32’si 32 bit ve altı tüm burst’leri yakalar; daha uzunları $1 - 0.5^{r}$ olasılıkla.
Tek bit hataları, $G$ en az iki terimliyse hep yakalanır.
$(x+1)$ çarpanı içeren üreteç tek sayıda hatanın hepsini yakalar.
Donanımda bir kaydırma register’ı ve birkaç XOR kapısıyla hat hızında çalışır.

TUZAK · CRC bir güvenlik mekanizması değil. CRC rastgele hatalara karşı tasarlandı. Kötü niyetli biri çerçeveyi değiştirip CRC’yi yeniden hesaplayabilir, çünkü algoritma gizli değil. Kasıtlı değişikliğe karşı anahtarlı bir MAC gerekir (12. hafta).

Hamming kodu: tek bit düzeltme

Hamming(7,4), 4 veri bitine 3 parity biti ekler. Parity bitleri 2’nin kuvveti olan konumlara (1, 2, 4), veri bitleri geri kalanlara (3, 5, 6, 7) yerleşir. Her parity biti, konum numarasının ikili gösteriminde kendi bitini içeren konumları kontrol eder.

Parity	Kontrol ettiği konumlar	Neden
p1	1, 3, 5, 7	ikili gösterimde en alt bit 1
p2	2, 3, 6, 7	ortadaki bit 1
p4	4, 5, 6, 7	üst bit 1

Kodlama: veri `1011`

d3=1, d5=0, d6=1, d7=1
p1 = d3 ⊕ d5 ⊕ d7 = 1 ⊕ 0 ⊕ 1 = 0
p2 = d3 ⊕ d6 ⊕ d7 = 1 ⊕ 1 ⊕ 1 = 1
p4 = d5 ⊕ d6 ⊕ d7 = 0 ⊕ 1 ⊕ 1 = 0
konum : 1  2  3  4  5  6  7
bit   : 0  1  1  0  0  1  1     -> 0110011

Çözme: 6. bit ters döndü, `0110001` alındı

s1 = b1⊕b3⊕b5⊕b7 = 0⊕1⊕0⊕1 = 0
s2 = b2⊕b3⊕b6⊕b7 = 1⊕1⊕0⊕1 = 1
s4 = b4⊕b5⊕b6⊕b7 = 0⊕0⊕0⊕1 = 1
sendrom s4 s2 s1 = 110 (ikili) = 6   -> 6. biti ters çevir -> 0110011

Sendrom 0 ise hata yok. Bu kod iki hatayı doğru düzeltemez; yanlış bir biti “düzeltir”.

Kaç parity biti gerekir? $m$ veri biti, $r$ parity bitiyle toplam $m + r$ konum var; sendrom bunların her birini ve “hata yok” durumunu ayırt etmeli:

$2^r \ge m + r + 1$

$m = 4 \Rightarrow r = 3$ , $m = 8 \Rightarrow r = 4$ , $m = 16 \Rightarrow r = 5$ , $m = 32 \Rightarrow r = 6$ .

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
CRC’de üreteç uzunluğu kadar sıfır eklemek	Derece kadar: 4 bitlik üreteç için 3 sıfır.
$x^4 + x + 1$ = `1011`	Eksik dereceler 0: `10011`.
Mod-2 bölmede borç almak	Borç yok, sadece XOR.
Alıcı da sıfır ekleyip böler	Alıcı gelen sözcüğün tamamını olduğu gibi böler.
Checksum’da taşan biti atmak	Elde en alta eklenir (wraparound).
Checksum = toplam	Toplamın tersi (one’s complement).
Tek parity çift hatayı yakalar	Çift sayıda hata parity’yi değiştirmez.
Hamming sendromu “hangi parity bozuk” der	Sendromun ikili değeri doğrudan hatalı bitin konumu.
CRC kasıtlı değişikliği önler	Hayır, CRC’yi herkes yeniden hesaplayabilir.

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

Using even parity, what parity bit is appended to the 7-bit data 1100101?

Cevabı göster

Even parity: toplam 1 sayısı çift olmalı. 1100101 içinde 1'ler: 1,1,1,1 yani 4 tane. Zaten çift, parity biti 0.

Soru 2kolay

What is the Hamming distance between 10110110 and 10011100?

Cevabı göster

XOR al, 1'leri say: 10110110 XOR 10011100 = 00101010. Üç tane 1 var, mesafe 3.

Soru 3orta

A code has minimum Hamming distance 5. How many bit errors can it detect, and how many can it correct?

Detect 5, correct 2
Detect 4, correct 2
Detect 4, correct 4
Detect 2, correct 4

Cevabı göster

B) Detect 4, correct 2

$d$ hatayı tespit için $d_{min} \ge d+1$ , $t$ hatayı düzeltmek için $d_{min} \ge 2t+1$ . $d_{min} = 5$ : tespit $5 - 1 = 4$ , düzeltme $\lfloor (5-1)/2 \rfloor = 2$ .

Soru 4orta

Compute the CRC remainder for data 1010011 with generator 1101. What bits are transmitted?

Cevabı göster

R = 111, transmitted 1010011111

Üreteç 4 bit, derece $r = 3$ . Veriye 3 sıfır ekle: 1010011000.
Mod-2 bölme (XOR, borç yok). Her adımda baştaki 1'in altına 1101 koy:1010 XOR 1101 = 0111; sonra 1110 XOR 1101 = 0011; 1111 XOR 1101 = 0010; 1000 XOR 1101 = 0101; 1010 XOR 1101 = 0111.
Son 3 bit kalan: R = 111. Gönderilen: 1010011 + 111 = 1010011111.

Soru 5orta

A receiver using generator 1011 receives 1001110101. Is an error detected?

No, the remainder is 000
Yes, the remainder is 101
Yes, the remainder is 011
Cannot be determined without the original data

Cevabı göster

B) Yes, the remainder is 101

Alıcı gelen sözcüğün tamamını (sıfır eklemeden) üretece böler. Kalan 0 değilse hata var.
Mod-2 bölmenin sonunda kalan 101 çıkar, sıfır değil. Hata tespit edildi, çerçeve atılır.

Soru 6orta

Compute the 16-bit Internet checksum of the two words 0xA1B2 and 0x7C3D.

Cevabı göster

0xE20F

Topla: $\mathtt{A1B2} + \mathtt{7C3D} = \mathtt{11DEF}$ . 16 biti aşan elde (carry) var.
Wraparound: elde biti en alta ekle: $\mathtt{1DEF} + 1 = \mathtt{1DF0}$ .
One's complement (bitleri ters çevir): $\mathtt{FFFF} - \mathtt{1DF0} = \mathtt{E20F}$ .
Alıcı her şeyi checksum dahil toplar; hata yoksa sonuç 0xFFFF olur.

Soru 7orta

Encode the 4 data bits 0110 (d3 d5 d6 d7) with a Hamming(7,4) code using even parity, bit positions 1..7 = p1 p2 d3 p4 d5 d6 d7.

Cevabı göster

1100110

d3 = 0, d5 = 1, d6 = 1, d7 = 0.
p1 = d3 ⊕ d5 ⊕ d7 = 0 ⊕ 1 ⊕ 0 = 1.
p2 = d3 ⊕ d6 ⊕ d7 = 0 ⊕ 1 ⊕ 0 = 1.
p4 = d5 ⊕ d6 ⊕ d7 = 1 ⊕ 1 ⊕ 0 = 0.
Sıra p1 p2 d3 p4 d5 d6 d7: 1 1 0 0 1 1 0 = 1100110.

Soru 8zor

A Hamming(7,4) codeword (same layout, even parity) is received as 1110101. Which bit is in error, and what are the corrected data bits d3 d5 d6 d7?

Cevabı göster

bit 2; data 1101

Bitler: b1=1 b2=1 b3=1 b4=0 b5=1 b6=0 b7=1.
s1 = b1⊕b3⊕b5⊕b7 = 1⊕1⊕1⊕1 = 0.
s2 = b2⊕b3⊕b6⊕b7 = 1⊕1⊕0⊕1 = 1.
s4 = b4⊕b5⊕b6⊕b7 = 0⊕1⊕0⊕1 = 0.
Sendrom $s_4 s_2 s_1 = 010_2 = 2$ : 2. bit hatalı. Düzelt: 1010101. Veri (3,5,6,7. bitler): 1101.

Soru 9orta

How many check bits $r$ does a single-error-correcting Hamming code need for $m = 16$ data bits?

Cevabı göster

Koşul: $2^r \ge m + r + 1$ . $r = 4$ : $16 \ge 21$ ? Hayır. $r = 5$ : $32 \ge 22$ ? Evet. Cevap 5 (toplam 21 bit).

Soru 10zor

Which error pattern is NOT detected by two-dimensional even parity?

Any single-bit error
Two errors in the same row
Three errors in different rows and columns
Four errors at the corners of a rectangle

Cevabı göster

D) Four errors at the corners of a rectangle

Dikdörtgenin köşelerindeki 4 hata her etkilenen satırda 2, her etkilenen sütunda 2 bit değiştirir. Tüm parity'ler yine çift kalır, hata görünmez.
Aynı satırdaki 2 hata satır parity'sini bozmaz ama iki sütun parity'sini bozar, yani tespit edilir (düzeltilemez).

Soru 11zor

Compute the CRC for data 1101101 using the generator polynomial $x^4 + x + 1$ .

Cevabı göster

1001

$x^4 + x + 1$ → katsayılar $x^4, x^3, x^2, x^1, x^0$ = 1 0 0 1 1. Derece 4, veriye 4 sıfır: 11011010000.
Adımlar: 11011⊕10011=01000; 10000⊕10011=00011; 11100⊕10011=01111; 11110⊕10011=01101; 11010⊕10011=01001.
Kalan (son 4 bit): 1001. Gönderilen 11011011001.

Soru 12kolay

Why is CRC preferred over a simple checksum at the link layer?

CRC can correct any number of errors
CRC detects all burst errors of length up to r+1 bits and is easy to compute in hardware
CRC encrypts the frame
CRC uses fewer bits than a single parity bit

Cevabı göster

B) CRC detects all burst errors of length up to r+1 bits and is easy to compute in hardware

$r$ dereceli bir üreteçle CRC, $r+1$ bit ya da daha kısa tüm ardışık (burst) hataları yakalar, daha uzunlarını da çok yüksek olasılıkla. Kaydırmalı XOR devresiyle donanımda hızlıdır.
CRC şifreleme değildir ve kasıtlı değişikliğe karşı koruma vermez: saldırgan veriyi değiştirip CRC'yi yeniden hesaplayabilir. Bütünlük için MAC gerekir (12. hafta).

Doğrulama: Tüm parity, checksum, CRC kalanları, Hamming kod sözcükleri ve sendromlar node ile hesaplandı (verify/SEN2008/03a.mjs: mod-2 bölme izi, 16 bit one's complement toplam, Hamming(7,4) kodlayıcı/çözücü, 2^r >= m+r+1 döngüsü).

Deftere not kartı

Parity: even -> toplam 1 sayısı çift. 1 biti tespit, düzeltme yok, çift hatayı kaçırır 2D parity: tek bit hatayı BULUR ve DÜZELTİR (satır x sütun kesişimi); 4 köşe dikdörtgen kaçar Hamming mesafe d: d-1 hata tespit, floor((d-1)/2) düzeltme Checksum: 16 bit topla, ELDE'yi en alta ekle (wrap), sonra tersle (~) alıcı: toplam FFFF CRC: G'nin derecesi r -> veriye r sıfır ekle -> mod-2 böl (XOR) -> son r bit = R gönder D + R ; alıcı tüm sözcüğü böler, kalan 0 ise OK x^4+x+1 = 10011 x^3+x+1 = 1011 (eksik dereceye 0 yaz!) CRC: tüm r+1 ve daha kısa burst hataları yakalar; donanımda kolay Hamming(7,4): p1 p2 d3 p4 d5 d6 d7 p1:1,3,5,7 p2:2,3,6,7 p4:4,5,6,7 sendrom s4 s2 s1 = hatalı bit konumu (0 ise hata yok) check bit sayısı: 2^r >= m + r + 1 (m=4->3, 8->4, 16->5, 32->6) Hiçbiri saldırıya karşı koruma değil: kasıtlı değişiklikte MAC/hash gerekir

Tespit mi, düzeltme mi?

Parity

Hamming mesafesi

Internet checksum

Çözümlü örnek

CRC (cyclic redundancy check)

Çözümlü örnek: DDD = 11010110, GGG = 1011

CRC neden güçlü?

Hamming kodu: tek bit düzeltme

Kodlama: veri 1011

Çözme: 6. bit ters döndü, 0110001 alındı

Sık yapılan hatalar

Kendini test et

Deftere not kartı

Çözümlü örnek: $D$ = `11010110`, $G$ = `1011`

Kodlama: veri `1011`

Çözme: 6. bit ters döndü, `0110001` alındı