> hamming | (7,4) | ecc <
// Kod Hamminga – kod korekcji błędów dla niezawodnej transmisji danych
Korekcja błędów
Automatycznie wykrywa i koryguje błędy jednobitowe w danych.
Wykrywanie podwójnych błędów
Potrafi wykryć (ale nie skorygować) błędy dwubitowe w każdym bloku.
Minimalny narzut
Tylko 3 bity parzystości na 4 bity danych (wydajność 75%).
>> informacje techniczne
Jak działa kod Hamminga:
Kod Hamming(7,4) dodaje 3 bity parzystości do każdych 4 bitów danych, tworząc 7-bitowe bloki. Bity parzystości są umieszczane na pozycjach będących potęgami liczby 2 (1, 2, 4). Gdy pojawiają się błędy, syndrom (wynik kontroli parzystości) wskazuje bezpośrednio pozycję błędnego bitu.
Struktura Hamming(7,4):
Dane: 1011 (4 bity) Pozycje: P1 P2 D1 P3 D2 D3 D4 Hamming: 1 0 1 1 0 1 1 P1 = D1 ⊕ D2 ⊕ D4 = 1 ⊕ 0 ⊕ 1 = 0 P2 = D1 ⊕ D3 ⊕ D4 = 1 ⊕ 1 ⊕ 1 = 1 P3 = D2 ⊕ D3 ⊕ D4 = 0 ⊕ 1 ⊕ 1 = 0
Dlaczego warto używać kodu Hamminga:
- >Korekcja błędów w pamięci
- >Komunikacja satelitarna
- >Systemy przechowywania danych
- >Transmisja sieciowa
- >Macierze RAID
>> najczęściej zadawane pytania
Czym jest kod Hamminga?
Kod Hamminga to kod korekcji błędów opracowany przez Richarda Hamminga w 1950 roku. Dodaje do danych bity parzystości, które pozwalają automatycznie wykrywać i korygować błędy jednobitowe.
Co oznacza (7,4)?
Hamming(7,4) oznacza 7 bitów łącznie: 4 bity danych i 3 bity parzystości. Kod może skorygować dowolny błąd jednobitowy w 7-bitowym bloku. Inne warianty to m.in. (15,11) i (31,26).
Jak działa korekcja błędów?
Przy odbiorze danych bity parzystości są ponownie obliczane. Jeśli nie pasują, syndrom (różnica) wskazuje bezpośrednio, który bit jest błędny. Błąd jest naprawiany przez odwrócenie wartości tego bitu.
Kod Hamminga a inne kody ECC?
Kod Hamminga jest prosty i wydajny w przypadku błędów jednobitowych. Bardziej złożone kody, takie jak Reed–Solomon, mogą korygować wiele błędów, ale mają większy narzut. Hamming świetnie sprawdza się w kanałach o małym szumie.
// Krótka ściąga
| Pos | bit | covered by |
|---|---|---|
| 1 | p1 | p1 |
| 2 | p2 | p2 |
| 3 | d1 | p1 p2 |
| 4 | p3 | p3 |
| 5 | d2 | p1 p3 |
| 6 | d3 | p2 p3 |
| 7 | d4 | p1 p2 p3 |
// Przykład krok po kroku
Data 1011 -> positions 3,5,6,7 = 1,0,1,1 p1 = d3^d5^d7 = 1^0^1 = 0 p2 = d3^d6^d7 = 1^1^1 = 1 p3 = d5^d6^d7 = 0^1^1 = 0 Codeword (pos 1..7) 0110011 Received 0110111 (bit 5 flipped) Syndrome s3 s2 s1 = 1 0 1 = 5 -> flip bit 5 -> 0110011 corrected
>> Więcej pytań
P: Co oznacza (7,4) w kodzie Hamminga?
O: 4 bity danych uzupełnia się 3 bitami parzystości do 7-bitowego słowa kodowego. Bity parzystości leżą na pozycjach będących potęgami 2: 1, 2 i 4. Odległość minimalna to 3: koryguje jeden błąd, wykrywa dwa, ale ich nie koryguje.
P: Jak syndrom wskazuje pozycję błędu?
O: Każdy bit parzystości sprawdza pozycje, których numer ma ustawiony odpowiedni bit. Trzy wyniki tworzą binarnie pozycję błędnego bitu (0 = brak błędu). W przykładzie 101 wskazuje pozycję 5.
P: Czym jest rozszerzony kod Hamminga (SECDED)?
O: Dodatkowy ogólny bit parzystości zamienia (7,4) w (8,4): koryguje 1 błąd i wykrywa 2. Pamięć ECC stosuje tę samą zasadę, zwykle jako (72,64): 8 bitów kontrolnych na 64 bity danych.