Lewati ke konten utama

Latihan 3.6 Latihan Tambahan: Mendeteksi Kesalahan

1. Simbol UPC.

Simbol Universal Product Code (UPC) terdapat pada sebagian besar produk di toko bahan pangan dan toko ritel. Simbol UPC merupakan kode 12 digit yang mengidentifikasi produsen suatu produk dan produk itu sendiri (Gambar 3.6.1). Sebelas digit pertama memuat informasi tentang produk; digit kedua belas digunakan untuk mendeteksi kesalahan. Jika \(d_1 d_2 \cdots d_{12}\) merupakan nomor UPC yang valid, maka
\begin{equation*} 3 \cdot d_1 + 1 \cdot d_2 + 3 \cdot d_3 + \cdots + 3 \cdot d_{11} + 1 \cdot d_{12} \equiv 0 \pmod{10}\text{.} \end{equation*}
  1. Tunjukkan bahwa nomor UPC 0-50000-30042-6, yang ditampilkan dalam Gambar 3.6.1, merupakan nomor UPC yang valid.
  2. Tunjukkan bahwa nomor 0-50000-30043-6 bukan nomor UPC yang valid.
  3. Tuliskan rumus untuk menghitung digit pemeriksa, \(d_{12}\text{,}\) dalam nomor UPC.
  4. Skema pendeteksian kesalahan UPC dapat mendeteksi sebagian besar kesalahan transposisi; artinya, skema tersebut dapat menentukan apakah dua digit telah saling dipertukarkan. Tunjukkan bahwa kesalahan transposisi 0-05000-30042-6 tidak terdeteksi. Temukan suatu kesalahan transposisi yang terdeteksi. Dapatkah Anda menemukan aturan umum untuk jenis kesalahan transposisi yang dapat dideteksi?
  5. Tulislah program yang menentukan apakah suatu nomor UPC valid.
Garis-garis vertikal kode batang UPC untuk 0-05000-30042-6.
Gambar 3.6.1. Kode UPC

2.

Notasi hasil kali dalam sering berguna untuk skema pendeteksian kesalahan jenis ini; oleh karena itu, kita akan menggunakan notasi
\begin{equation*} (d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n } \end{equation*}
untuk menyatakan
\begin{equation*} d_1 w_1 + d_2 w_2 + \cdots + d_k w_k \equiv 0 \pmod{ n}\text{.} \end{equation*}
Andaikan bahwa \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) merupakan skema pendeteksian kesalahan untuk nomor identifikasi \(k\) digit \(d_1 d_2 \cdots d_k\text{,}\) dengan \(0 \leq d_i \lt n\text{.}\) Buktikan bahwa semua kesalahan satu digit terdeteksi jika dan hanya jika \(\gcd( w_i, n ) = 1\) untuk \(1 \leq i \leq k\text{.}\)

3.

Misalkan \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) merupakan skema pendeteksian kesalahan untuk nomor identifikasi \(k\) digit \(d_1 d_2 \cdots d_k\text{,}\) dengan \(0 \leq d_i \lt n\text{.}\) Buktikan bahwa semua kesalahan transposisi dua digit \(d_i\) dan \(d_j\) terdeteksi jika dan hanya jika \(\gcd( w_i - w_j, n ) = 1\) untuk \(i\) dan \(j\) di antara \(1\) dan \(k\text{.}\)

4. Kode ISBN.

Setiap buku mempunyai kode International Standard Book Number (ISBN). Kode 10 digit ini menunjukkan penerbit dan judul buku. Digit kesepuluh merupakan digit pemeriksa yang memenuhi
\begin{equation*} (d_1, d_2, \ldots, d_{10} ) \cdot (10, 9, \ldots, 1 ) \equiv 0 \pmod{11}\text{.} \end{equation*}
Salah satu masalahnya adalah bahwa \(d_{10}\) mungkin harus bernilai 10 agar hasil kali dalam bernilai nol; dalam hal ini, diperlukan 11 digit agar skema tersebut dapat bekerja. Oleh karena itu, karakter X digunakan untuk digit kesebelas. Jadi, ISBN 3-540-96035-X merupakan kode ISBN yang valid.
  1. Apakah ISBN 0-534-91500-0 merupakan kode ISBN yang valid? Bagaimana dengan ISBN 0-534-91700-0 dan ISBN 0-534-19500-0?
  2. Apakah metode ini mendeteksi semua kesalahan satu digit? Bagaimana dengan semua kesalahan transposisi?
  3. Ada berapa banyak kode ISBN yang berbeda?
  4. Tulislah program komputer yang menghitung digit pemeriksa untuk sembilan digit pertama suatu kode ISBN.
  5. Sebuah penerbit mempunyai cabang di Jerman dan Amerika Serikat. Awalan penerbit tersebut di Jerman adalah 3-540. Jika awalannya di Amerika Serikat akan berupa 0-abc, tentukan abc sedemikian sehingga bagian lain kode ISBN sama untuk buku yang dicetak di Jerman dan di Amerika Serikat. Dalam metode pengodean ISBN, digit pertama mengidentifikasi bahasa; bahasa Jerman adalah 3 dan bahasa Inggris adalah 0. Kelompok angka berikutnya mengidentifikasi penerbit, dan kelompok terakhir mengidentifikasi buku tertentu.
Sblm.Paling AtasLanjut