HAMMING CODE

HAMMING CODE

Dalam telekomunikasi , Hamming  Code adalah keluarga dari linear kesalahan-kode koreksi yang menggeneralisasi Hamming (7,4) -kode , dan diciptakan oleh Richard Hamming pada tahun 1950. Kode Hamming dapat mendeteksi sampai kesalahan dua-bit atau benar satu-bit kesalahan tanpa deteksi kesalahan tidak dikoreksi. Sebaliknya, sederhana kode paritas tidak bisa memperbaiki kesalahan, dan dapat mendeteksi hanya ganjil bit kesalahan. Hamming kode ini kode yang sempurna , yaitu, mereka mencapai tertinggi mungkin tingkat untuk kode dengan mereka panjang blok dan jarak minimum tiga. ^[1]

Dalam matematika hal, Hamming kode adalah kelas linier kode biner. Untuk setiap bilangan bulat r ≥ 2 ada kode dengan panjang blok n = 2 ^r - 1 dan panjang pesan k = 2 ^r - r - 1. Oleh karena itu tingkat kode Hamming adalah R = k / n = 1 - r / (2 ^r - 1), yang merupakan tertinggi untuk kode dengan jarak minimal tiga (yaitu, jumlah minimal perubahan bit yang dibutuhkan untuk pergi dari setiap kata kode untuk setiap kata kode lain adalah tiga) dan blok panjang 2 ^r - 1. The paritas-cek matriks dari kode Hamming dibangun dengan membuat daftar semua kolom panjang r yang non-nol, yang berarti bahwa kode ganda dari kode Hamming adalah kode Hadamard dipersingkat . Matriks parity-cek memiliki properti bahwa setiap dua kolom berpasangan linear .

Karena redundansi terbatas yang kode Hamming menambah data, mereka hanya dapat mendeteksi dan memperbaiki kesalahan ketika tingkat kesalahan rendah. Ini adalah kasus di memori komputer ( memori ECC ), di mana kesalahan bit sangat langka dan kode Hamming digunakan secara luas. Dalam konteks ini, kode Hamming diperpanjang memiliki satu bit paritas ekstra sering digunakan. Kode Hamming diperpanjang mencapai jarak Hamming empat, yang memungkinkan decoder untuk membedakan antara saat paling banyak satu kesalahan satu-bit terjadi dan bila ada kesalahan dua-bit terjadi. Dalam hal ini, kode Hamming diperpanjang adalah single-mengoreksi kesalahan dan mendeteksi double-kesalahan, disingkat SECDED.

Sejarah

Richard Hamming, penemu kode Hamming, bekerja di Bell Labs pada tahun 1940 pada komputer Bell Model V, elektromekanis mesin berbasis relay dengan waktu siklus di detik.Masukan diumpankan pada kartu menekan , yang akan selalu membaca kesalahan. Selama hari kerja, kode khusus akan menemukan kesalahan dan lampu flash sehingga operator bisa memperbaiki masalah. Selama periode setelah-jam dan pada akhir pekan, ketika tidak ada operator, mesin hanya pindah ke pekerjaan berikutnya.

Hamming bekerja pada akhir pekan, dan tumbuh semakin frustrasi dengan harus me-restart program nya dari awal karena tidak dapat diandalkan dari pembaca kartu. Selama beberapa tahun berikutnya, ia bekerja pada masalah koreksi kesalahan, mengembangkan sebuah array semakin kuat algoritma. Pada tahun 1950, ia menerbitkan apa yang sekarang dikenal sebagai Hamming Code, yang tetap digunakan saat ini dalam aplikasi seperti memori ECC .

Kode mendahului Hamming 

Sejumlah sederhana kesalahan-mendeteksi kode yang digunakan sebelum kode Hamming, tapi tidak ada yang seefektif Hamming kode di atas sama ruang.

Paritas

Artikel utama: Parity bit

Paritas menambahkan satu bit yang menunjukkan apakah jumlah yang (sedikit-posisi dengan nilai-nilai satu) dalam data sebelumnya adalah bahkan atau ganjil . Jika ganjil bit berubah dalam transmisi, pesan akan mengubah paritas dan kesalahan dapat dideteksi pada saat ini; Namun, sedikit yang berubah mungkin telah paritas bit itu sendiri. Konvensi yang paling umum adalah bahwa nilai paritas satu menunjukkan bahwa ada ganjil yang di data, dan nilai paritas nol menunjukkan bahwa ada bahkan jumlah yang. Jika jumlah bit berubah bahkan, sedikit cek akan berlaku dan kesalahan tidak akan terdeteksi.

Selain itu, paritas tidak menunjukkan yang sedikit mengandung kesalahan, bahkan ketika itu bisa mendeteksi itu. Data harus dibuang seluruhnya dan ditransmisikan kembali dari awal. Pada media transmisi berisik, transmisi yang sukses bisa memakan waktu lama atau mungkin tidak pernah terjadi. Namun, sementara kualitas pengecekan paritas miskin, karena hanya menggunakan satu bit, metode ini menghasilkan sedikit overhead.

Dua-out-of-lima kode 

Artikel utama: Dua-out-of-lima kode

Sebuah kode dua-out-of-lima adalah skema encoding yang menggunakan lima bit yang terdiri dari tiga orang 0s dan dua 1s. Ini memberikan sepuluh kemungkinan kombinasi, cukup untuk mewakili angka 0-9. Skema ini dapat mendeteksi semua bit-error tunggal, semua bernomor ganjil bit-kesalahan dan beberapa bahkan nomor bit-kesalahan (misalnya membalik kedua 1-bit). Namun tetap saja tidak bisa memperbaiki kesalahan ini.

Pengulangan 

Artikel utama: Tiga redundansi modular

kode lain yang digunakan pada saat itu diulang setiap bit data beberapa kali untuk memastikan bahwa itu dikirim dengan benar. Misalnya, jika bit data yang akan dikirim adalah 1, n = 3 kode pengulangan akan mengirimkan 111. Jika tiga bit yang diterima tidak identik, terjadi kesalahan selama transmisi. Jika saluran tersebut cukup bersih, sebagian besar waktu hanya satu bit akan berubah di setiap tiga. Oleh karena itu, 001, 010, dan 100 masing-masing sesuai dengan 0 bit, sedangkan 110, 101, dan 011 sesuai dengan 1 bit, seolah-olah bit dihitung sebagai "orang" terhadap apa yang sedikit dimaksud adalah. Sebuah kode dengan kemampuan untuk merekonstruksi pesan asli di hadapan kesalahan dikenal sebagai kode error-correcting. Kode pengulangan tiga ini adalah kode Hamming dengan m = 2, karena ada dua paritas bit, dan 2 ² - 2 - 1 = 1 bit data.

Kode tersebut tidak dapat benar memperbaiki semua kesalahan, namun. Dalam contoh kita, jika saluran membalik dua bit dan penerima mendapat 001, sistem akan mendeteksi kesalahan, tetapi menyimpulkan bahwa bit asli adalah 0, yang tidak benar. Jika kita meningkatkan jumlah kali kita menduplikasi setiap bit ke empat, kita bisa mendeteksi semua kesalahan dua-bit tetapi tidak dapat memperbaikinya (suara "mengikat"); di lima pengulangan, kita dapat memperbaiki semua kesalahan dua-bit, tetapi tidak semua kesalahan tiga bit.

Selain itu, kode pengulangan adalah sangat tidak efisien, mengurangi throughput dengan tiga kali dalam kasus kami asli, dan efisiensi turun secara drastis seperti yang kita meningkatkan jumlah kali setiap bit diduplikasi untuk mendeteksi dan kesalahan lebih benar.

Hamming kode 

Jika lebih mengoreksi kesalahan-bit disertakan dengan pesan, dan jika mereka bit dapat diatur sedemikian rupa sehingga bit yang salah yang berbeda menghasilkan hasil kesalahan yang berbeda, maka bit buruk bisa diidentifikasi. Dalam pesan tujuh-bit, ada tujuh kemungkinan kesalahan satu bit, sehingga kontrol tiga kesalahan bit berpotensi menentukan tidak hanya bahwa terjadi kesalahan tetapi juga yang sedikit menyebabkan kesalahan.

Hamming mempelajari skema pengkodean yang ada, termasuk dua dari lima, dan generalisasi konsep mereka. Untuk mulai dengan, ia mengembangkan nomenklatur untuk menggambarkan sistem, termasuk jumlah bit data dan bit koreksi kesalahan dalam satu blok. Misalnya, paritas termasuk satu bit untuk setiap kata data, sehingga dengan asumsi ASCII kata-kata dengan tujuh bit, Hamming menggambarkan ini sebagai (8,7) kode, dengan delapan bit secara total, yang tujuh adalah data. Pengulangan contoh akan(3,1), mengikuti logika yang sama. The code rate adalah jumlah kedua dibagi dengan yang pertama, misalnya pengulangan kami, 1/3.

Hamming juga melihat masalah dengan membalik dua atau lebih bit, dan menggambarkan ini sebagai "jarak" (sekarang disebut jarak Hamming , setelah dia). Paritas memiliki jarak 2, jadi satu bit sandal dapat dideteksi, tapi tidak diperbaiki dan dua bit membalik tidak akan terlihat. The (3,1) pengulangan memiliki jarak 3, tiga bit harus membalik dalam tiga sama untuk mendapatkan kata kode lain dengan tidak ada kesalahan yang terlihat. Hal ini dapat memperbaiki kesalahan satu-bit atau mendeteksi tetapi tidak kesalahan dua-bit yang benar. A (4,1) pengulangan (setiap bit diulang empat kali) memiliki jarak 4, jadi membalik tiga bit dapat dideteksi, tapi tidak diperbaiki. Ketika tiga bit membalik dalam kelompok yang sama bisa ada situasi di mana berusaha untuk memperbaiki akan menghasilkan kata kode yang salah. Secara umum, kode dengan k jarak dapat mendeteksi tetapi tidak k yang benar - 1 kesalahan.

Hamming tertarik dalam dua masalah sekaligus: meningkatkan jarak sebanyak mungkin, sementara pada saat yang sama meningkatkan tingkat kode sebanyak mungkin.Selama tahun 1940-an ia mengembangkan beberapa skema encoding yang perbaikan dramatis pada kode yang ada. Kunci untuk semua sistem adalah untuk memiliki paritas bit tumpang tindih, sehingga mereka berhasil untuk memeriksa satu sama lain serta data.

General algoritma 

Berikut algoritma umum menghasilkan single-mengoreksi kesalahan (SEC) kode untuk setiap jumlah bit.

1.     Jumlah bit mulai dari 1: bit 1, 2, 3, 4, 5, dll

2.     Menulis angka bit dalam biner: 1, 10, 11, 100, 101, dll

3.     Semua posisi bit yang merupakan pangkat dua (hanya satu 1 bit dalam bentuk biner dari posisi mereka) adalah paritas bit: 1, 2, 4, 8, dll (1, 10, 100, 1000)

4.     Semua posisi bit lainnya, dengan dua atau lebih 1 bit dalam bentuk biner dari posisi mereka, adalah data bit.

5.     Setiap bit data termasuk dalam satu set unik dari 2 atau lebih paritas bit, sebagaimana ditentukan oleh bentuk biner dari posisi bit nya.

1.    Paritas bit 1 mencakup semua posisi bit yang memiliki setidaknya bit set signifikan: bit 1 (paritas bit itu sendiri), 3, 5, 7, 9, dll

2.    Paritas bit 2 meliputi semua posisi bit yang memiliki setidaknya kedua signifikan bit set: bit 2 (paritas bit itu sendiri), 3, 6, 7, 10, 11, dll

3.    Paritas bit 4 mencakup semua posisi bit yang memiliki ketiga bit set paling signifikan: bit 4-7, 12-15, 20-23, dll

4.    Paritas bit 8 mencakup semua posisi bit yang memiliki setidaknya empat signifikan bit set: bit 8-15, 24-31, 40-47, dll

5.    Secara umum setiap bit paritas mencakup semua bit di mana bitwise DAN dari posisi paritas dan posisi bit adalah non-nol.

Bentuk paritas tidak relevan. Bahkan paritas lebih sederhana dari perspektif matematika teoritis, tetapi tidak ada perbedaan dalam praktek.

Aturan umum ini dapat ditampilkan secara visual:

posisi bit

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

...

Dikodekan bit data

p1

p2

d1

p4

d2

d3

d4

p8

d5

d6

d7

d8

d9

d10

D11

p16

d12

D13

D14

d15

Keseimbangan sedikit liputan

p1

X

X

X

X

X

X

X

X

X

X

p2

X

X

X

X

X

X

X

X

X

X

p4

X

X

X

X

X

X

X

X

X

p8

X

X

X

X

X

X

X

X

p16

X

X

X

X

X

Tampil hanya 20 bit dikodekan (5 paritas, 15 data) tapi pola terus tanpa batas. Kuncinya tentang Kode Hamming yang dapat dilihat dari inspeksi visual adalah bahwa setiap bit yang diberikan termasuk dalam seperangkat unik paritas bit. Untuk memeriksa kesalahan, periksa semua bit paritas. Pola kesalahan, disebut sindrom kesalahan , mengidentifikasi bit dalam kesalahan. Jika semua bit paritas yang benar, tidak ada kesalahan. Jika tidak, jumlah dari posisi paritas bit yang salah mengidentifikasi bit yang salah.Misalnya, jika paritas bit di posisi 1, 2 dan 8 menunjukkan kesalahan, lalu menggigit 1 + 2 + 8 = 11 adalah kesalahan. Jika hanya satu bit paritas menunjukkan kesalahan, paritas bit itu sendiri adalah kesalahan.

Seperti yang Anda lihat, jika Anda memiliki paritas bit, dapat menutupi bit 1 sampai dengan{\ displaystyle 2 ^ {m} -1}. Jika kitakurangi keluar paritas bit, kita dibiarkan dengan {\ displaystyle 2 ^ {m} m-1}bit kita dapat menggunakan data tersebut. Sebagai  {\ displaystyle m}bervariasi, kita mendapatkan semua kode Hamming mungkin:

paritas bit	Jumlah bit	Data bit	Nama	Menilai
2	3	1	Hamming (3,1) (Triple kode pengulangan )	1/3 ≈ 0,333
3	7	4	Hamming (7,4)	4/7 ≈ 0,571
4	15	11	Hamming (15,11)	11/15 ≈ 0,733
5	31	26	Hamming (31,26)	26/31 ≈ 0,839
...
{\ displaystyle m}	{\ displaystyle 2 ^ {m} -1}	{\ displaystyle 2 ^ {m} m-1}	Hamming  {\ displaystyle (2 ^ {m} -1,2 ^ {m} m-1)}	{\ displaystyle (2 ^ {m} m-1) / (2 ^ {m} -1)}

Jika, di samping itu, sebuah bit paritas keseluruhan (bit 0) disertakan, kode dapat mendeteksi (tetapi tidak benar) kesalahan dua-bit, membuat kode SECDED. Keseluruhan paritas menunjukkan apakah jumlah total kesalahan adalah genap atau ganjil. Jika kode Hamming dasar mendeteksi kesalahan, tetapi paritas keseluruhan mengatakan bahwa ada bahkan jumlah kesalahan, sebuah 2-bit kesalahan uncorrectable telah terjadi.