Kode Hamming – Teknik deteksi dan koreksi error pada jaringan nirkabel


Hamming Code (1 bit error correction)

Achieves the theoretical limit for minimum number of check bits to do 1-bit error-correction.

Bits of codeword are numbered: bit 1, bit 2, …, bit n.
Check bits are inserted at positions 1,2,4,8,.. (all powers of 2).
The rest are the m data bits.

Setiap cek bit memeriksa (seperti bit paritas) sejumlah bit data. Setiap bit cek memeriksa sekumpulan bit data yang berbeda. Check bit hanya memeriksa data, bukan bit cek yang lain.

Hamming Codes used in:

Wireless comms, e.g. Fixed wireless broadband. High error rate. Need correction not detection.

Angka apapun dapat ditulis sebagai jumlah dari pangkat 2

Pertama catatan setiap angka dapat ditulis dalam basis 2 sebagai jumlah dari pangkat 2 dikalikan dengan 0 atau 1

i.e. As a simple sum of powers of 2.

Number is sum of these:         1       2       4       8       16

Number:

1                               x

2                                       x

3                               x       x

4                                               x

5                               x               x

6                                       x       x

7                               x       x       x

8                                                       x

9                               x                       x

10                                      x               x

11                              x       x               x

12                                              x       x

13                              x               x       x

14                                      x       x       x

15                              x       x       x       x

16                                                              x

17                              x                               x

18                                      x                       x

19                              x       x                       x

20                                              x               x

21                              x               x               x

22                                      x       x               x

23                              x       x       x               x

24                                                      x       x

25                              x                       x       x

26                                      x               x       x

27                              x       x               x       x

28                                              x       x       x

29                              x               x       x       x

30                                      x       x       x       x

31                              x       x       x       x       x

Scheme for check bits

Now here is our scheme for which bits each check bit checks:

Checked by check bit:           1       2       4       8       16

Bit:

1 (not applicable – this is a check bit)

2 (n/a)

3                               x       x

4 (n/a)

5                               x               x

6                                       x       x

7                               x       x       x

8 (n/a)

9                               x                       x

10                                      x               x

11                              x       x               x

12                                              x       x

13                              x               x       x

14                                      x       x       x

15                              x       x       x       x

16 (n/a)

17                              x                               x

18                                      x                       x

19                              x       x                       x

20                                              x               x

21                              x               x               x

22                                      x       x               x

23                              x       x       x               x

24                                                      x       x

25                              x                       x       x

26                                      x               x       x

27                              x       x               x       x

28                                              x       x       x

29                              x               x       x       x

30                                      x       x       x       x

31                              x       x       x       x       x

32 (n/a)

Check bit mencatat paritas genap atau ganjil dari semua bit yang discover, sehingga sembarang error 1 bit dalam data akan memicu error pada check bit. Asumsi bahwa satu bit error : Jika sembarang bit data rusak, maka beberapa check bit juga akan rusak (tidak pernah hanya satu check bit).

Bagimana dia bekerja ?

21 (sebagai jumlah pangkat 2) = 1 + 4 + 16

Bit 21 diperiksa oleh check bit 1, 4, 16. Tidak ada bit lain yang diperiksa oleh 3 check bit ini. Jika diasumsikan 1 bit error maka jika tepat 3 check bit ini yang rusak, maka kita dapat mengetahui bahwa data bit 21 yang rusak dan yang lainnya tidak.

Asumsikan satu bit error :

  1. Error dalam bit data

Akan menyebabkan beberapa error dalam check bit. Akan menyebebkan error dalam tepat check bit yang berkorelasi dengan pangkat dari 2 dimana angka bit dapat ditulis sebagai jumlah pangkat dari 2.

  1. Error dalam check bit

Tidak ada bit lain yang dipengaruhi selain check bit yang error tersebut. Misalnya satu check bit rusak (tidak ada check bit lain yang rusak seperti diatas).

Hamming Code example for 3-bit data

Consider standard encoding of numbers 0 to 7:

000
001
010
011
100
101
110
111

(bits 1 to 3).

Encode this such that a 1 bit error can be detected and corrected.


Add check bits:

 
cc0c00
cc0c01
cc0c10
cc0c11
cc1c00
cc1c01
cc1c10
cc1c11

(now have bits 1 to 6).

Check bit 1 looks at bits 3 5.
If the number of 1s is 0 or even, set check bit to 0.
If the number of 1s is 1 or odd, set check bit to 1.

 
0c0c00
0c0c01
1c0c10
1c0c11
1c1c00 (flip previous 4 bits)
1c1c01
0c1c10
0c1c11


Check bit 2 looks at bits 3 6.
If the number of 1s is 0 or even, set check bit to 0.
If the number of 1s is 1 or odd, set check bit to 1.

 
000c00
010c01
100c10
110c11
111c00 (flip previous 4 bits)
101c01
011c10
001c11


Check bit 4 looks at bits 5 6.
If the number of 1s is 0 or even, set check bit to 0.
If the number of 1s is 1 or odd, set check bit to 1.

 
000000
010101
100110
110011
111000
101101
011110
001011


Error detection:

 
Distance from pattern:  0       1       2       3       4       5       6       7

Pattern:
0       000000          -       3       3       4       3       4       4       3
1       010101          3       -       4       3       4       3       3       4
2       100110          3       4       -       3       4       3       3       4
3       110011          4       3       3       -       3       4       4       3
4       111000          3       4       4       3       -       3       3       4
5       101101          4       3       3       4       3       -       4       3
6       011110          4       3       3       4       3       4       -       3
7       001011          3       4       4       3       4       3       3       -

Minimum distance 3.
If assume only 1 bit error, can always tell which pattern nearest.

Calculating the Hamming Code

The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error. Create the code word as follows:

  1. Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
  2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
  3. Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
    Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,…)
    Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,…)
    Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,…)
    Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,…)
    Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,…)
    Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,…)
    etc.
  4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

Here is an example:

A byte of data: 10011010
Create the data word, leaving spaces for the parity bits: _ _ 1 _ 0 0 1 _ 1 0 1 0
Calculate the parity for each parity bit (a ? represents the bit position being set):

  • Position 1 checks bits 1,3,5,7,9,11:
    ?
    _ 1 _ 0 0 1 _ 1 0 1 0. Even parity so set position 1 to a 0: 0 _ 1 _ 0 0 1 _ 1 0 1 0
  • Position 2 checks bits 2,3,6,7,10,11:
    0 ? 1 _ 0 0 1 _ 1 0 1 0. Odd parity so set position 2 to a 1: 0 1 1 _ 0 0 1 _ 1 0 1 0
  • Position 4 checks bits 4,5,6,7,12:
    0 1 1 ? 0 0 1 _ 1 0 1 0. Odd parity so set position 4 to a 1: 0 1 1 1 0 0 1 _ 1 0 1 0
  • Position 8 checks bits 8,9,10,11,12:
    0 1 1 1 0 0 1 ? 1 0 1 0. Even parity so set position 8 to a 0: 0 1 1 1 0 0 1 0 1 0 1 0
  • Code word: 011100101010.

Finding and fixing a bad bit

Contoh di atas membuat sebuah code word 011100101010. Misalkan word yang diterima adalah 011100101110. Kemudian penerima bisa menghitung yang bit yang salah dan benar. Metode ini untuk memeriksa setiap bit check. Tuliskan semua bit parity yang salah. Lakukan, dan anda akan menemukan bahwa paritas bit 2 dan 8 adalah tidak benar. Ini bukan suatu kebetulan bahwa 2 + 8 = 10, dan bahwa posisi bit 10 adalah lokasi bit yang salah. Secara umum, periksa setiap bit paritas, dan menambahkan posisi yang salah, ini akan memberikan kita lokasi bit yang salah.

Try one yourself

Test if these code words are correct, assuming they were created using an even parity Hamming Code . If one is incorrect, indicate what the correct code word should have been. Also, indicate what the original data was.

  • 010101100011
  • 111110001100
  • 000010001010

Error correction:

List all patterns and find nearest one? Computationally expensive. Especially with longer strings (much more patterns).

With Hamming, can find nearest quickly by just looking at one pattern:

  1. Let’s say error in a data bit:
    100 sent
    111000
    became: 111001
    i.e. data 101, but check bits wrong

Check bit 1 – 1 – checks bits 3,5 – 1 0 – OK
Check bit 2 – 1 – checks bits 3,6 – 1 1 – WRONG
Check bit 4 – 0 – checks bits 5,6 – 0 1 – WRONG

The bad bit is bit 2 + 4 = bit 6. Data was corrupted. Data should be 100.


  1. Let’s say error in a check bit:
    100 sent
    111000
    became: 011000
    i.e. data 100, but check bits wrong

Check bit 1 – 0 – checks bits 3,5 – 1 0 – WRONG
Check bit 2 – 1 – checks bits 3,6 – 1 0 – OK
Check bit 4 – 0 – checks bits 5,6 – 0 0 – OK

The bad bit is bit 1. Check bit was corrupted. Data is fine.

Summary

If assume 1-bit error:

  1. If 1 check bit bad:
    Data is good, check bit itself got corrupted.
    Ignore check bits. Data is good.
  2. If more than 1 check bit bad:
    Data in error (single-bit error in data). Which check bits are bad shows you exactly where the data error was. They point to a unique bit which is the bit in error.
    Can reconstruct data.

i.e. If 1 bit error – can always tell what original pattern was.
This, by the way, proves that distance between two patterns must be at least 3.
Q. Any other way of proving distance >= 3?

Hamming code to correct burst errors

Dasar kode Hamming di atas mengoreksi kesalahan 1-bit saja.
Trik untuk menggunakannya untuk memperbaiki burst error :

Perhatikan pengiriman k codeword, panjang tiap codeword adalah n.
Susun dalam matriks (seperti dalam diagram), setiap baris adalah suatu codeword.
Matrix n lebar, tinggi k.
Biasanya ini akan dikirimkan baris-per-baris.
Trik: Transmit kolom-per-kolom.

Jika ledakan k yang panjang terjadi dalam blok kxn seluruh (dan tidak ada kesalahan lainnya) paling banyak 1 bit dalam codeword dipengaruhi masing-masing.
Jadi kode Hamming dapat merekonstruksi codeword masing-masing.
Sehingga kode Hamming dapat merekonstruksi seluruh blok.

Kuning adalah burst error.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: