Lewati ke konten utama

Latihan 8.6 Latihan

1.

Mengapa skema pengodean berikut tidak dapat diterima?
Informasi \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\)
Kata kode \(\codeword{000}\) \(\codeword{001}\) \(\codeword{010}\) \(\codeword{011}\) \(\codeword{101}\) \(\codeword{110}\) \(\codeword{111}\) \(\codeword{000}\) \(\codeword{001}\)

2.

Tanpa melakukan penjumlahan apa pun, jelaskan mengapa himpunan tupel-\(4\) berikut dalam \({\mathbb Z}_2^4\) tidak dapat menjadi kode grup.
\begin{equation*} (\codeword{0110}) \quad (\codeword{1001}) \quad (\codeword{1010}) \quad (\codeword{1100}) \end{equation*}
Petunjuk.
Ini tidak dapat menjadi kode grup karena \((\codeword{0000}) \notin C\text{.}\)

3.

Hitung jarak Hamming antara pasangan-pasangan tupel-\(n\) berikut.
  1. \(\displaystyle (\codeword{011010}), (\codeword{011100})\)
  2. \(\displaystyle (\codeword{11110101}), (\codeword{01010100})\)
  3. \(\displaystyle (\codeword{00110}), (\codeword{01111})\)
  4. \(\displaystyle (\codeword{1001}), (\codeword{0111})\)
Petunjuk.
(a) \(2\text{;}\) (c) \(2\text{.}\)

4.

Hitung bobot tupel-tupel-\(n\) berikut.
  1. \(\displaystyle (\codeword{011010})\)
  2. \(\displaystyle (\codeword{11110101})\)
  3. \(\displaystyle (\codeword{01111})\)
  4. \(\displaystyle (\codeword{1011})\)
Petunjuk.
(a) \(3\text{;}\) (c) \(4\text{.}\)

5.

Misalkan suatu kode linear \(C\) memiliki bobot minimum \(7\text{.}\) Apa kemampuan \(C\) dalam mendeteksi dan mengoreksi kesalahan?

6.

Untuk setiap kode berikut, berapakah jarak minimum kode tersebut? Apa hasil terbaik yang dapat kita harapkan sehubungan dengan pendeteksian dan pengoreksian kesalahan?
  1. \(\displaystyle (\codeword{011010}) \; (\codeword{011100}) \; (\codeword{110111}) \; (\codeword{110000})\)
  2. \(\displaystyle (\codeword{011100}) \; (\codeword{011011}) \; (\codeword{111011}) \; (\codeword{100011}) \\ (\codeword{000000}) \; (\codeword{010101}) \; (\codeword{110100}) \; (\codeword{110011})\)
  3. \(\displaystyle (\codeword{000000}) \; (\codeword{011100}) \; (\codeword{110101}) \; (\codeword{110001})\)
  4. \(\displaystyle (\codeword{0110110}) \; (\codeword{0111100}) \; (\codeword{1110000}) \; (\codeword{1111111}) \\ (\codeword{1001001}) \; (\codeword{1000011}) \; (\codeword{0001111}) \; (\codeword{0000000})\)
Petunjuk.
(a) \(d_{\min} = 2\text{;}\) (c) \(d_{\min} = 1\text{.}\)

7.

Hitung ruang nol dari setiap matriks berikut. Ruang-ruang nol tersebut merupakan kode blok \((n,k)\) jenis apa? Dapatkah Anda menemukan suatu matriks (tidak harus berupa matriks pembangkit standar) yang membangkitkan setiap kode? Apakah matriks-matriks pembangkit Anda unik?
  1. \begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
Petunjuk.
  1. \((\codeword{00000}), (\codeword{00101}), (\codeword{10011}), (\codeword{10110})\)
    \begin{equation*} G = \begin{pmatrix} 0 & 1 \\ 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}
  2. \((\codeword{000000}), (\codeword{010111}), (\codeword{101101}), (\codeword{111010})\)
    \begin{equation*} G = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}

8.

Konstruksikan suatu kode blok \((5,2)\text{.}\) Bahas kemampuan kode Anda dalam mendeteksi maupun mengoreksi kesalahan.

9.

Misalkan \(C\) adalah kode yang diperoleh dari ruang nol matriks
\begin{equation*} H = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}\text{.} \end{equation*}
Dekodekan pesan
\begin{equation*} \codeword{01111} \quad \codeword{10101} \quad \codeword{01110} \quad \codeword{00011} \end{equation*}
jika memungkinkan.
Petunjuk.
Beberapa kesalahan terjadi dalam salah satu kata yang diterima.

10.

Misalkan suatu pesan biner sepanjang \(1000\) bit ditransmisikan. Asumsikan bahwa probabilitas kesalahan pada satu bit adalah \(p\) dan bahwa kesalahan yang terjadi pada bit-bit berbeda saling bebas. Jika \(p = 0.01\text{,}\) berapakah probabilitas terjadinya lebih dari satu kesalahan? Berapakah probabilitas terjadinya tepat dua kesalahan? Ulangi soal ini untuk \(p = 0.0001\text{.}\)

11.

Matriks manakah yang merupakan matriks pemeriksa paritas kanonik? Untuk matriks-matriks yang merupakan matriks pemeriksa paritas kanonik, apa matriks pembangkit standar yang bersesuaian? Apa kemampuan kode yang dihasilkan oleh setiap matriks tersebut dalam mendeteksi dan mengoreksi kesalahan?
  1. \begin{equation*} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
Petunjuk.
(a) Matriks pemeriksa paritas kanonik dengan matriks pembangkit standar
\begin{equation*} G = \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}\text{.} \end{equation*}
(c) Matriks pemeriksa paritas kanonik dengan matriks pembangkit standar
\begin{equation*} G = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \\ 1 & 0 \end{pmatrix}\text{.} \end{equation*}

12.

Cantumkan semua sindrom yang mungkin bagi kode-kode yang dihasilkan oleh setiap matriks dalam Latihan 8.6.11.
Petunjuk.
(a) Semua sindrom yang mungkin muncul.

13.

Misalkan
\begin{equation*} H = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \end{pmatrix}\text{.} \end{equation*}
Hitung sindrom yang disebabkan oleh setiap kesalahan transmisi berikut.
  1. Kesalahan pada bit pertama.
  2. Kesalahan pada bit ketiga.
  3. Kesalahan pada bit terakhir.
  4. Kesalahan pada bit ketiga dan keempat.

14.

Misalkan \(C\) adalah kode grup dalam \({\mathbb Z}_2^3\) yang didefinisikan oleh kata-kata kode \((\codeword{000})\) dan \((\codeword{111})\text{.}\) Hitung koset-koset \(C\) dalam \({\mathbb Z}_2^3\text{.}\) Mengapa koset kanan atau kiri tidak perlu ditentukan? Berikan kesalahan transmisi tunggal, jika ada, yang bersesuaian dengan setiap koset.

15.

Untuk setiap matriks berikut, carilah koset-koset dari kode \(C\) yang bersesuaian. Berikan tabel pendekodean bagi setiap kode jika memungkinkan.
  1. \begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
Petunjuk.
(a) \(C\text{,}\) \((\codeword{10000}) + C\text{,}\) \((\codeword{01000}) + C\text{,}\) \((\codeword{00100}) + C\text{,}\) \((\codeword{00010}) + C\text{,}\) \((\codeword{11000}) + C\text{,}\) \((\codeword{01100}) + C\text{,}\) \((\codeword{01010}) + C\text{.}\) Tabel pendekodean tidak ada untuk \(C\) karena kode ini hanya mendeteksi kesalahan tunggal.

16.

Misalkan \({\mathbf x}\text{,}\) \({\mathbf y}\text{,}\) dan \({\mathbf z}\) adalah tupel-\(n\) biner. Buktikan setiap pernyataan berikut.
  1. \(\displaystyle w({\mathbf x}) = d( {\mathbf x}, {\mathbf 0})\)
  2. \(\displaystyle d( {\mathbf x}, {\mathbf y}) = d( {\mathbf x} + {\mathbf z}, {\mathbf y} + {\mathbf z} )\)
  3. \(\displaystyle d({\mathbf x}, {\mathbf y}) = w({\mathbf x}- {\mathbf y})\)

17.

Suatu metrik pada himpunan \(X\) adalah pemetaan \(d: X \times X \rightarrow {\mathbb R}\) yang memenuhi syarat-syarat berikut.
  1. \(d( {\mathbf x}, {\mathbf y}) \geq 0\) untuk semua \({\mathbf x}, {\mathbf y} \in X\text{;}\)
  2. \(d( {\mathbf x}, {\mathbf y}) = 0\) tepat ketika \({\mathbf x} = {\mathbf y}\text{;}\)
  3. \(d( {\mathbf x}, {\mathbf y})= d( {\mathbf y}, {\mathbf x})\text{;}\)
  4. \(d( {\mathbf x}, {\mathbf y}) \leq d( {\mathbf x}, {\mathbf z}) + d( {\mathbf z}, {\mathbf y})\text{.}\)
Dengan kata lain, metrik hanyalah suatu perumuman dari gagasan jarak. Buktikan bahwa jarak Hamming merupakan metrik pada \({\mathbb Z}_2^n\text{.}\) Mendekode suatu pesan sesungguhnya dapat direduksi menjadi penentuan kata kode yang terdekat dalam hal jarak.

18.

Misalkan \(C\) adalah suatu kode linear. Tunjukkan bahwa semua koordinat ke-\(i\) dalam kata-kata kode \(C\) bernilai nol, atau tepat separuh di antaranya bernilai nol.

19.

Misalkan \(C\) adalah suatu kode linear. Tunjukkan bahwa setiap kata kode berbobot genap, atau tepat separuh kata kode berbobot genap.
Petunjuk.
Misalkan \({\mathbf x} \in C\) berbobot ganjil dan definisikan suatu pemetaan dari himpunan kata kode berbobot ganjil ke himpunan kata kode berbobot genap dengan \({\mathbf y} \mapsto {\mathbf x} + {\mathbf y}\text{.}\) Tunjukkan bahwa pemetaan ini merupakan bijeksi.

20.

Tunjukkan bahwa kata-kata kode berbobot genap dalam suatu kode linear \(C\) juga membentuk kode linear.

21.

Jika kita hendak menggunakan kode linear pengoreksi kesalahan untuk mentransmisikan \(128\) karakter ASCII, matriks berukuran berapa yang harus digunakan? Matriks berukuran berapa yang harus digunakan untuk mentransmisikan himpunan karakter ASCII perluasan yang terdiri atas \(256\) karakter? Bagaimana jika dalam kedua kasus kita hanya memerlukan pendeteksian kesalahan?

22.

Carilah matriks pemeriksa paritas kanonik yang menghasilkan kode bit pemeriksa paritas genap dengan tiga posisi informasi. Bagaimanakah matriksnya untuk tujuh posisi informasi? Apa matriks pembangkit standar yang bersesuaian?

23.

Berapa banyak posisi pemeriksa yang diperlukan bagi kode pengoreksi kesalahan tunggal dengan \(20\) posisi informasi? Bagaimana dengan \(32\) posisi informasi?
Petunjuk.
Untuk \(20\) posisi informasi, diperlukan sekurang-kurangnya \(6\) bit pemeriksa untuk menjamin diperolehnya kode pengoreksi kesalahan.

24.

Misalkan \({\mathbf e}_i\) adalah tupel-\(n\) biner yang memiliki \(1\) pada koordinat ke-\(i\) dan \(0\) di tempat lainnya, dan misalkan \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Tunjukkan bahwa \(H{\mathbf e}_i\) merupakan kolom ke-\(i\) dari matriks \(H\text{.}\)

25.

Misalkan \(C\) adalah suatu kode linear \((n,k)\text{.}\) Definisikan kode dual atau kode ortogonal dari \(C\) sebagai
\begin{equation*} C^\perp = \{ {\mathbf x} \in {\mathbb Z}_2^n : {\mathbf x} \cdot {\mathbf y} = 0 \text{ untuk semua } {\mathbf y} \in C \}\text{.} \end{equation*}
  1. Carilah kode dual dari kode linear \(C\text{,}\) dengan \(C\) diberikan oleh matriks
    \begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}\text{.} \end{equation*}
  2. Tunjukkan bahwa \(C^\perp\) merupakan kode linear \((n, n-k)\text{.}\)
  3. Carilah matriks pembangkit standar dan matriks pemeriksa paritas dari \(C\) dan \(C^\perp\text{.}\) Apa yang terjadi secara umum? Buktikan konjektur Anda.

26.

Misalkan \(H\) adalah matriks \(m \times n\) atas \({\mathbb Z}_2\text{,}\) dengan kolom ke-\(i\) berupa bilangan \(i\) yang ditulis dalam bentuk biner dengan \(m\) bit. Ruang nol dari matriks semacam itu disebut kode Hamming.
  1. Tunjukkan bahwa matriks
    \begin{equation*} H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
    menghasilkan suatu kode Hamming. Apa sifat pengoreksi kesalahan dari kode Hamming?
  2. Kolom yang bersesuaian dengan sindrom juga menunjukkan bit yang salah; artinya, kolom ke-\(i\) dari matriks merupakan \(i\) yang ditulis sebagai bilangan biner, dan sindrom langsung menunjukkan bit mana yang salah. Jika kata yang diterima adalah \((101011)\text{,}\) hitung sindromnya. Pada bit manakah kesalahan terjadi dalam kasus ini, dan kata kode apa yang mula-mula ditransmisikan?
  3. Berikan matriks biner \(H\) bagi kode Hamming dengan enam posisi informasi dan empat posisi pemeriksa. Manakah posisi pemeriksa dan manakah posisi informasi? Kodekan pesan \((\codeword{101101})\) dan \((\codeword{001001})\text{.}\) Dekodekan kata yang diterima \((\codeword{0010000101})\) dan \((\codeword{0000101100})\text{.}\) Apa saja sindrom yang mungkin bagi kode ini?
  4. Berapakah banyaknya bit pemeriksa dan bit informasi dalam kode Hamming blok \((m,n)\text{?}\) Berikan batas atas maupun batas bawah bagi banyaknya bit informasi dalam hubungannya dengan banyaknya bit pemeriksa. Kode Hamming yang memiliki sebanyak mungkin bit informasi dengan \(k\) bit pemeriksa disebut sempurna. Setiap sindrom yang mungkin selain \({\mathbf 0}\) muncul sebagai suatu kolom. Jika banyaknya bit informasi kurang dari maksimum, maka kode tersebut disebut dipendekkan. Dalam kasus ini, berikan contoh yang menunjukkan bahwa beberapa sindrom dapat merepresentasikan lebih dari satu kesalahan.
Sblm.Paling AtasLanjut