Lompat ke konten utama

Topologi: Pendekatan Berbasis Inkuiri: Bab 1-17 - Himpunan, Fungsi, Ruang Metrik, Ruang Topologi, Kekontinuan, Homeomorfisme, Subruang, Ruang Kuosien, Ruang Kompak, serta Pendamping Belajar Mandiri

Steven Schlicker

Bagian Metrik Hamming

Dalam masyarakat kita, banyak sekali informasi dikomunikasikan secara elektronik. Transaksi bank, program televisi, komunikasi militer, panggilan telepon seluler, citra digital, dan hampir setiap pertukaran yang dapat dibayangkan dapat didigitalkan dan dikirimkan secara elektronik, atau memang sudah dilakukan dengan cara tersebut. Dalam banyak situasi, kita perlu membandingkan satu kumpulan data dengan kumpulan lainnya (misalnya, pencarian untai teks atau pencocokan citra di Internet, serta untaian DNA), dan metrik sering digunakan untuk tujuan ini. Komputer bekerja dengan sistem biner, artinya komputer hanya mengenali nol dan satu. Karena itu, pesan teks digital merupakan suatu untai nol dan satu. Dengan kata lain, pesan digital merupakan kumpulan unsur dalam ruang \(X^n\) untuk suatu bilangan bulat positif \(n\text{,}\) dengan \(X = \{0,1\}\text{.}\) Setiap unsur dalam \(X^n\) disebut kata—yakni, kata adalah unsur dalam \(X^n\) yang dinyatakan dalam bentuk \((x_1, x_2, \ldots, x_n)\text{.}\) Seperti halnya dalam bahasa Inggris, yang tidak setiap kombinasi hurufnya membentuk kata yang bermakna, tidak setiap kata dapat dikenali sebagai bagian dari pesan yang dapat dipahami. Sebagai contoh, kita dapat mengodekan huruf-huruf dalam alfabet dengan menetapkan bilangan 1 sampai 26 pada huruf-huruf tersebut, kemudian menjadikannya unsur dalam \(X^n\) dengan mengonversinya ke bentuk biner. Himpunan semua kata yang dapat dipahami disebut kode. Jadi, kode hanyalah suatu subhimpunan \(X^n\) yang unsur-unsurnya disepakati oleh semua pihak sebagai kata-kata yang bermakna. Kata-kata dalam suatu kode disebut kata kode. Untuk menangani masalah yang terjadi dalam pengiriman pesan digital, seperti mengacak pesan (pengodean), memulihkan pesan dari bentuk teracak (pendekodean), serta mendeteksi dan memperbaiki galat dalam pesan, kita perlu memiliki cara untuk mengukur jarak antarkata. Salah satu caranya adalah menggunakan metrik Hamming.

Definisi 4.1.

Misalkan \(x = (x_1, x_2, \ldots, x_n)\) dan \(y = (y_1, y_2, \ldots, y_n)\) merupakan kata-kata dalam \(X^n\text{.}\) Jarak Hamming \(d_H\) antara \(x\) dan \(y\) adalah
\begin{equation*} d_H(x,y) = \sum_{i=1}^n | x_i-y_i |\text{.} \end{equation*}
Ingatlah bahwa untuk setiap \(i\text{,}\) baik \(x_i\) maupun \(y_i\) bernilai 0 atau 1. Oleh karena itu,
\begin{equation*} | x_i-y_i | = \begin{cases}0 \amp \text{ jika } x_i=y_i \\ 1 \amp \text{ jika } x_i \neq y_i. \end{cases} \end{equation*}
Dengan kata lain, \(d_H(x,y)\) menghitung banyaknya komponen tempat \(x\) dan \(y\) berbeda.

Kegiatan 4.1.

(a)

Jelaskan mengapa \(d_H\) merupakan suatu metrik.

(b)

Misalkan kita membuat kode
\begin{equation*} C = \{c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8\} \end{equation*}
dalam \(X^6\text{,}\) dengan
\begin{align*} c_1 \amp = (0,0,0,0,0,0) \amp c_2 \amp =( 0,0,0,0,1,1) \amp c_3 \amp = (0,0,0,1,0,1)\\ c_4 \amp = (0,0,1,0,0,1) \amp c_5 \amp = (0,0,0,1,1,0) \amp c_6 \amp = (0,0,1,0,1,0)\\ c_7 \amp = (0,0,1,1,0,0) \amp c_8 \amp = (0,0,1,1,1,1) \amp \amp \end{align*}
Artinya, kata-kata \(c_1\text{,}\) \(c_2\text{,}\) \(c_3\text{,}\) \(c_4\text{,}\) \(c_5\text{,}\) \(c_6\text{,}\) \(c_7\text{,}\) dan \(c_8\) merupakan satu-satunya kata yang dapat menyusun suatu pesan. Hitung \(d_H(c_2, c_8)\text{.}\)

(c)

Misalkan kita menerima pesan
\begin{equation} (0,0,0,1,1,1) \ (0,0,1,1,0,0) \ (1,0,0,0,0,0) \ (0,0,0,0,1,1) \ (0,0,1,0,0,1)\text{.}\tag{4.1} \end{equation}
(i)
Bagaimana kita mengetahui bahwa telah terjadi galat dalam transmisi pesan yang kita terima?
(ii)
Untuk memperbaiki galat dalam pesan yang diterima ini, kita mengganti kata-kata yang salah dengan kata kode dalam \(C\) yang paling dekat dengan masing-masing kata tersebut. Perbaikilah pesan ini. (Perhatikan bahwa mungkin terdapat lebih dari satu kemungkinan penggantian. Temukan semua kemungkinannya.)
<Sebelumnya^AtasBerikutnya>