1
SISTEM KOMUNIKASI DIGITAL Berikut ini digambarkan salah satu blok diagram sistem komunikasi sederhana. Sumber Informasi
Koder Sumber
Koder Kanal
Modulator Gelombang
Kanal Gelombang
Pengguna Informasi
Dekoder Sumber
Dekoder Kanal
Demodulator Gelombang
Gbr. 1 : Salah satu model sistem komunikasi
• •
•
•
Fungsi sistem komunikasi adalah memancarkan informasi secara andal dari sumber informasi ke pengguna informasi Dari blok diagram diatas dapat dilihat bahwa : o keluaran dari sumber informasi adalah sudah berbentuk signalsignal digital , yaitu berupa urutan simbol-simbol dari berbagai abjad yang sudah menjadi signal-signal diskrit Simbol-simbol ini diproses oleh koder sumber menjadi simbol-simbol bentuk lain (atau disebut kelompok simbol) agar supaya : o dapat dibuat menjadi simbol-simbol yang pada saat dipancarkan ke pengguna informasi , banyaknya simbol tersebut adalah menjadi seminimal mungkin Keluaran dari koder sumber menjadi masukan bagi koder saluran dimana : o koder saluran tersebut berfungsi untuk memperbesar efisiensi
komunikasi , yaitu dengan jalan : mengubah urutan bit keluaran koder sumber menjadi urutan bit simbol yang berbeda dari abjad yang dikirim dari sumber informasi Keluaran koder saluran masuk ke modulator , kemudian dipancarkan lewat Kanal Diskrit Tanpa Memori = DMC (Discrete Memoryless Channel) menuju ke demodulator yang menjadi bagian sistem penerima, terus masuk ke dekoder kanal sistem penerima Manfaat DMC ini mencakup : o melakukan pengurangan terhadap pengaruh distorsi
•
•
signal sewaktu melewati kanal komunikasi gelombang •
detektor kanal yang mendapat masukan dari demodulator , akan berupaya untuk : o merekonstruksi urutan keluaran yang berasal dari koder sumber , menjadi urutan bit yang seasli mungkin • Dengan menggunakan disain enkoder-dekoder yang tepat, maka akan dapat :
2
o mengoreksi beberapa kesalahan transmisi yang terjadi di Kanal Diskrit Tak Bermemori (DMC) tadi, sehingga dapat memperbaiki keandalan komunikasi • Dengan memakai keluaran dekoder kanal, maka dekoder sumber akan dapat membuat
perkiraan urutan bit informasi yang dipan-
carkan KODE KELOMPOK (Block Code) Kode kelompok adalah suatu kode yang dapat mengoreksi kesalahan bit secara mandiri (self error correction) , dimana : • bentuk kode terdiri atas : o kode yang menggambarkan suatu kharakter sebanyak k buah bit o kode yang digunakan sebagai uji paritas sebanyak q buah bit • kemungkinan kharakter yang terjadi = m buah = 2 k buah • pada kode kelompok banyaknya bit menjadi k + q = n buah bit Jika salah satu kharakter tersebut adalah :
d = (d1
•
d2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅dk )
d1 s/d k bernilai 0 atau 1 , maka : dengan memakai enkoder (alat untuk membuat kode), maka : o kode kharakter data yang terdiri atas k bits tersebut diubah
menjadi kharakter baru yang terdiri atas n bits o tambahan bit sebanyak = q = (n − k ) bits, merupakan bit uji paritas
• •
Kata kodenya ditulis dengan kode (n , k) Tujuan penambahan q bits paritas tersebut adalah : untuk membuat kode yang terdiri atas n bits tadi menjadi
kode yang dapat mendeteksi dan mengoreksi kesalahan bit secara mandiri (self detection and correcting •
•
code) Kesalahan bit tersebut dapat terjadi karena signal-signal biner tersebut melalui media transmisi dalam perjalanannya dari sumber signal ke tujuan Data yang keluar dari encoder tersebut , yang disebut dengan kata kode (code word), dinyatakan sebagai berikut :
x = (x1
x 2 ⋅ ⋅ ⋅ ⋅ ⋅ xk
x = (x1
atau x 2 ⋅ ⋅ ⋅ ⋅ ⋅ x k x k +1
x k +1
xk + 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅xk + q ) xk + 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅xn )
Untuk kode sistematis, maka :
x1 = d1
x2 = d2
x3 = d3 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅xk = dk
Banyaknya bit uji paritas = q buah
3
Banyaknya seluruh bit setiap kode baru = n = k + q
Bit-bit uji paritas untuk kode sistimatis tersebut dibuat memenuhi hubungan yang sesuai dengan persamaan berikut ini :
x k +1
= h 11 d 1 + h 12 d 2 + h 13 d 3 + ⋅ ⋅ ⋅ ⋅ ⋅ + h 1k d k
xk+2
= h 21 d 1 + h 22 d 2 + h 23 d 3 + ⋅ ⋅ ⋅ ⋅ + h 2k d k
.......... .......... .......... .......... .......... .......... .......... .. x k + q = x n = h q1 d 1 + h q2 d 2 + h q3 d 3 + ⋅ ⋅ ⋅ ⋅ + h qk d k
⎡ xk+1 ⎤ ⎡h11 ⎢ x ⎥ ⎢h ⎢ k+2 ⎥ = ⎢ 21 ⎢ M ⎥ ⎢ M ⎢ ⎥ ⎢ ⎣ xn ⎦ ⎣⎢hq1
h12 L h1k ⎤ ⎡d1 ⎤ h22 L h2k ⎥⎥ ⎢d2 ⎥ ⎢ ⎥ M M M ⎥⎢ M ⎥ ⎥⎢ ⎥ hq2 L hqk ⎦⎥ ⎣dk ⎦
Contoh : Suatu kode (15,11), mempunyai kode data :
d = (0 1 0 1 1 1 0 1 0 1 1) , dengan n = 15 ; q=4 dan k = 11 ;
Misalkan kode uji paritas dinyatakan dengan persamaan matrix sebagai berikut :
⎡ xk +1 ⎤ ⎡ x11+1 ⎤ ⎡ x12 ⎤ ⎡ h11 h12 L h1k ⎤ ⎡ d1 ⎤ ⎡1 ⎢ x ⎥ ⎢ x ⎥ ⎢ x ⎥ ⎢h h L h2 k ⎥⎥ ⎢d 2 ⎥ ⎢0 ⎢ ⎥=⎢ ⎢ k +2 ⎥ = ⎢ 11+2 ⎥ = ⎢ 13 ⎥ = ⎢ 21 22 M M M ⎥ ⎢ M ⎥ ⎢0 ⎢ M ⎥ ⎢ x11+3 ⎥ ⎢ x14 ⎥ ⎢ M ⎥⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎣ xn ⎦ ⎣ x11+4 ⎦ ⎣ x15 ⎦ ⎢⎣hq1 hq 2 L hqk ⎥⎦ ⎣d k ⎦ ⎣1
⎡ x12 ⎤ ⎡ 1 ⎢ x ⎥ ⎢0 ⎢ 13 ⎥ = ⎢ ⎢ x14 ⎥ ⎢ 0 ⎢ ⎥ ⎢ ⎣ x15 ⎦ ⎣ 1
1 1
1 1
1 1
0 1
1 0
0
1
1
1
0 1
1 0
1 1
0 1
1
1
0
1
1
0
1
0
1
0
1
1
0
0
0⎤ 0 ⎥⎥ 1⎥ ⎥ 1⎦
1 1 1 0 1 0 1 1 0 0⎤ ⎡ d1 ⎤ 1 1 1 1 0 1 0 1 1 0⎥⎥ ⎢⎢ d 2 ⎥⎥ 0 1 1 1 1 0 1 0 1 1⎥ ⎢ M ⎥ ⎥⎢ ⎥ 1 1 0 1 0 1 1 0 0 1⎦ ⎣d11 ⎦
⎡0 ⎤ ⎢1 ⎥ ⎢ ⎥ ⎢0 ⎥ ⎢ ⎥ ⎢1 ⎥ ⎡ 0 ⊕ 1 + 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⎤ ⎡0 ⎤ ⎢1 ⎥ ⎢ ⎢ ⎥ ⎢ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⎥⎥ ⎢⎢ 0 ⎥⎥ = ⎢1 ⎥ = ⎢ ⎢ 0 ⎥ ⎢ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⎥⎥ ⎢⎢ 0 ⎥⎥ ⎢ ⎥ ⎣ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1⎦ ⎣ 0 ⎦ ⎢1 ⎥ ⎢0 ⎥ ⎢ ⎥ ⎢1 ⎥ ⎢ ⎥ ⎣1 ⎦
Maka kode sistimatis lengkap yang dikirimkan adalah :
x = (x1 x2 LLLx11 x12 x13 x14 x15 ) = (0 1 0 1 1 1 0 1 0 1 1 0 0 0 0) Jika m adalah salah satu dari 2k buah kode untuk data yang mungkin terjadi, maka salah satu kode data adalah xm1 , xm 2 ,....., xmk . Dengan kata lain salah satu kode data tesebut adalah :
x dm = [x m1 , x m 2 , L , x mk ]
4
Jika kode tersebut diberi bit uji paritas ( parity checking bit ) yang banyaknya q buah bit , maka keseluruhan bit keluaran dari enkoder yang menggambarkan suatu kharakter, akan menjadi terdiri atas n buah bit, sehingga susunannya menjadi :
xm = [xm1
xm 2 L xmn ]
Jika digambarkan secara blok diagram :
Masukan
Keluaran
Enkoder
k bit
n bit
Operasi enkoder yang dikerjakan dalam suatu enkoder blok biner linier dapat digambarkan sebagai himpunan n buah persamaan dalam bentuk matrix sebagai berikut :
c m j = x m1 g 1 j + x m 2 g 2 j + L + x m j g k dengan j = 1, 2, L , n ; m = 1, 2, ⋅ ⋅ ⋅ ⋅2 dimana g i j = 0 atau 1
j
k
Contoh : Kode ( 7,4 ) ; maka m j adalah salah satu dari 2 4 kemungkinan kode Data yang mungkin terjadi jika setiap data terdiri atas 4 bit adalah Kode-kode bit paritas yang terkait tergantung dari matrix H. Matrix H tersebut dapat dilihat pada pembahasan berikut :
] •
0 0
0 0
0 0
0 1
0
0
1
0
0 0
0 1
1 0
1 0
0 0
1 1
0 1
1 0
0
1
1
1
1 1
0 0
0 0
0 1
1
0
1
0
1 1
0 1
1 0
1 0
1 1
1 1
0 1
1 0
1
1
1
1
Seperti sudah dibahas sebelumnya, kata kode dinyatakan dengan :
x = ( x1
x2 ⋅ ⋅ ⋅ ⋅ ⋅ xk
d = (d m1
x k +1
xk + 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅xn )
d m 3 .........d mk )
•
Kode data dinyatakan dengan
•
dimana : mj adalah salah satu dari 2 k buah jenis kata kode yang mungkin terjadi Selanjutnya dapat ditulis :
d m2
x = dG
dimana :
5
G = matrix generator kode dan merupakan matrix k x Matrix generator G dinyatakan dengan persamaan matrix : G = [I k P ]
n
dengan I k = matrix identitas dan ⎡ h11 h21 LL hqn ⎤ ⎢h ⎥ ⎢ 12 h22 LL hq2 ⎥ P = H T = ⎢h13 h23 LL hq3 ⎥ ⎢ ⎥ M M M ⎥ ⎢ M ⎢h1k h2k LL hqn ⎥ ⎣ ⎦ Contoh : Suatu kode (7,4) dengan generator matrix : G = [I k P ] Disini n = 7 ; k = 4 ; q = 3 ⎡1 0 0 0 1 0 1⎤
⎡1 1 1 0⎤ H=⎢⎢0 1 1 1⎥⎥ ⎢⎣1 1 0 1⎥⎦
⎢0 1 0 0 1 1 1⎥ ⎥ G =⎢ ⎢0 0 1 0 1 1 0⎥ ⎢ ⎥ ⎣0 0 0 1 0 1 1⎦
Matrix Data
P = HT
Ik
Dari contoh ini, karena : • banyaknya bit untuk setiap kode adalah k = 4 • banyak bit untuk paritas adalah q = 3 , maka : o dapat digambarkan kemungkinan seluruh kode blok yang terjadi adalah :
x = dG =
⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣
0 0
0 0
0 0
0
0
1
0
0
1
0 0
1 1
0 0
0
1
1
0
1
1
1 1
0 0
0 0
1
0
1
1
0
1
1 1
1 1
0 0
1
1
1
1
1
1
0 ⎤ 1 ⎥⎥ 0 ⎥ ⎥ 1 ⎥ 0 ⎥ ⎥ 1 ⎥ 0 ⎥ ⎥ 1 ⎥ 0 ⎥ ⎥ 1 ⎥ ⎥ 0 ⎥ 1 ⎥ ⎥ 0 ⎥ 1 ⎥ ⎥ 0 ⎥ 1 ⎥⎦
⎡1 ⎢0 ⎢ ⎢0 ⎢ ⎣0
0 1 0 0
0 0 1 0
0 0 0 1
1 1 1 0
0 1 1 1
1⎤ 1⎥⎥ 0⎥ ⎥ 1⎦
⎡0 0 0 0 0 0 0 ⎤ ⎢0 0 0 1 0 1 1 ⎥ ⎥ ⎢ ⎢0 0 1 0 1 1 0 ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ =⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎦ ⎣
Jika rumus-rumus yang ada diuraikan lebih lanjut : ⎡ ⎡1 0 L 0 ⎡ h11 h12 L h1k ⎤ T ⎤ ⎤ ⎢ ⎢ ⎢ ⎥ ⎥⎥ ⎢ ⎢0 1 L 0 ⎢h21 h22 L h2 k ⎥ ⎥ ⎥ c = dG = [d [I k P ]] = ⎢[d1 d 2 L d k ] ⎢ M L M ⎥ ⎥⎥ M M L L⎢ M ⎢ ⎢ ⎢ ⎥ ⎥⎥ ⎢ ⎢0 0 M 1 ⎢⎣hq1 hq 2 L hqk ⎥⎦ ⎥ ⎥ ⎣ ⎦⎦ ⎣
6
⎡ ⎡1 ⎢ ⎢ 0 c = ⎢[d1 d 2 L d k ] ⎢ ⎢ ⎢M ⎢ ⎢ ⎣⎢0 ⎣⎢
h21 L hq1 ⎤ ⎤ ⎥ h22 L hq 2 ⎥⎥ ⎥ = [d1 d 2 L d k M L M ⎥⎥ ⎥⎥ h2 k L hqk ⎦⎥ ⎦⎥ Maka c = [d dP ] = c c p
0 L 0 h11 1 L 0 h12 M L L M 0 M 1 h1k
[
[d1 d 2 Ld k ]P]
]
Jadi urutan bit uji paritas adalah c p = dP Jika urutan bit yang diterima adalah kata kode yang tepat , maka : dP ⊕ c p = 0 Urutan bit Urutan bit yang dihitung uji paritas di dekoder yang diterima
Jika urutan bit yang diterima tepat , maka rumus diatas dapat ditulis dalam persamaan matrix sebagai berikut : ⎡P ⎤ 0 = dP + c p = d c p ⎢ ⎥ ⎣Iq ⎦
[
]
hal ini karena
[ ]
cp Iq = cp
Jika tak terjadi kesalahan bit , maka : dP ⊕ c p = 0
⎡ ⎡P ⎤ ⎤ cH T = d c p P = ⎢ d c p ⎢ ⎥ ⎥P = 0P = 0 ⎣Iq ⎦ ⎦⎥ ⎣⎢ Syarat urutan bit yang diterima dekoder tidak terjadi kesalahan bit : cH T = 0 Didalam hal ini , sesuai dengan perhitungan diatas , yang dimaksudkan dengan H T adalah : ⎡P⎤ H T = ⎢ ⎥ → H = PT I q ⎣I q ⎦
[
]
[
]
[
Dalam persamaan matrix ⎡h11 h12 ⎢h ⎢ 12 h22 M Matrix uji paritas = H = ⎢ M ⎢ M ⎢ M ⎢ hq1 hq 2 ⎣
]
L h1k ⎤ L h2 k ⎥⎥ L M ⎥ ⎥ L M ⎥ L hqk ⎥⎦
Contoh : Kode (7, 3) dengan matrix uji paritas : ⎡1 ⎢1 H =⎢ ⎢0 ⎢ ⎣0
0 1 1 0
1 1 1 1
1 0 0 0
0 1 0 0
⎡1 ⎢0 ⎢ 0 0⎤ ⎢1 0 0⎥⎥ ⎢ T → p = H = ⎢1 1 0⎥ ⎢0 ⎥ 0 1⎦ ⎢ ⎢0 ⎢0 ⎣
1 1 1 0 1 0 0
0 1 1 0 0 1 0
0⎤ 0⎥⎥ 1⎥ ⎥ 0⎥ 0⎥ ⎥ 0⎥ 1⎥⎦
7
Kata kode : c = dG Bila tanpa kesalahan bit maka : cH T = 0 Bila terjadi kesalahan bit yang diterima di dekoder , maka vektor kode yang diterima adalah : r = c⊕e Jika terjadi kesalahan bit , maka : r ≠ c → e ≠ (0 0 LL 0 ) Jika tidak terjadi kesalahan bit , maka : r = c → e = (0 0 LL 0 ) Syndrome =
•
s = rH T = (c ⊕ e ) H T = cH T ⊕ eH T = 0 + eH T
Syndrome = s = eH T Jika tanpa kesalahan bit , maka : s = (0 0 LL 0 ) Jika ada kesalahan bit , maka : s ≠ (0 0 LL 0 ) Anggaplah bahwa terjadi kesalahan pada bit ke-i vektor kesalahann ya adalah e = (0 0 0 LL 1 LL 0 ) digit ke − i
⎡ h11 ⎢h ⎢ 21 ⎢ ⋅ H ' = [H I k ] = ⎢ ⎢ ⋅ ⎢ ⋅ ⎢ ⎢⎣hq1
Syndrome = s = e(H ')
T
•
h12 h22 ⋅ ⋅ ⋅
LL h1k LL h2 k LL ⋅ LL LL
⋅ ⋅
h q 2 LL hqk
⎡ h11 ⎢h ⎢ 12 ⎢M ⎢h ⎢ 1i ⎢M = (0 0 L 1 L 0 ) ⎢ h ⎢ 1k1 ⎢ 1 ⎢ 0 ⎢ ⎢ ⋅ ⎢ ⎣ 0
h21 h22 M h2 i M h2 k 0 1 ⋅ 0
0⎤ 0⎥⎥ ⋅⎥ ⎥ ⋅⎥ ⋅ ⋅ LL ⋅ ⎥ ⎥ 0 0 LL 1⎥⎦
1 0 LL 0 1 LL ⋅ ⋅ LL ⋅ ⋅ LL
⋅ ⋅ ⋅ hq1 ⎤ ⋅ ⋅ ⋅ hq 2 ⎥⎥ M M M M ⎥ ⋅ ⋅ ⋅ hqi ⎥ ⎥ M M M M ⎥ = (h1i ⋅ ⋅ ⋅ hqk ⎥ ⎥ ⋅ ⋅ ⋅ 0 ⎥ ⋅ ⋅ ⋅ 0 ⎥ ⎥ ⋅ ⋅ ⋅ ⋅ ⎥ ⎥ ⋅ ⋅ ⋅ 1 ⎦
h2 i
⋅ ⋅ ⋅ hqi )
Persyaratan suatu kode dapat dikoreksi bilamana terjadi 1 kesalahan bit adalah : o Semua kolom matrix H sudah ditentukan nilainya dengan pasti o Semua isi kolom ke-1 s.d. ke-k sudah tertentu nilainya dengan pasti o q kolom berikutnya merupakan matrix identitas Ik o Agar matrix identitas Ik dapat membuat syndrome yang dapat ditentukan nilainya, maka harus : 2q − (q − 1) ≥ k o Misalkan q = 3 → 8 − 2 = 6 ≥ k o Jadi kode blok (7, 4) , yang berarti bahwa : k = 4 → q = 3 → memenuhi 2q − (q − 1) ≥ k o Ketidak samaan (inequity) 2 q − (q − 1) ≥ k yang harus dipenuhi bagi kode berkesalahan tunggal adalah hal yang khusus daripada ketidak samaan Hamming d H ≥ 2 t + 1 → d H min = 2 t + 1
8
•
•
•
Ketidak samaan Hamming d H ≥ 2 t + 1 yang dapat digunakan secara umum untuk pengoreksian kode yang mengalami kesalahan t buah bit , dapat diterangkan dengan contoh berikut ini : o Kode blok ( 7, 3 ) berarti n = 7 ; k = 3 ; q = 4 . o Penerapan ketidak samaan 2 q − (q − 1) ≥ k → 2 4 − (4 − 1) = 13 ≥ k = 3 o Dengan demikian kode blok ( 7, 3 ) adalah kode yang dapar mengoreksi kesalahan tunggal o Contoh kode blok yang tak dapat mengoreksi meskipun kesalahannya tunggal adalah kode bloK ( 6, 4) , yang berati q =2 ; dengan memasukkan ke ketidak samaan 2 q − (q − 1) ≥ k , dimana 2 2 − (2 − 1) = 3 < k = 4 Kode dengan kesalahan yang lebih besar dari 1 , misalnya terjadi kesalahan t bit , salah satunya dapat diselesaikan dengan Hamming bound , yang mana salah satunya yang khusus adalah menggunakan rumus ketidak samaan 2 q − (q − 1) ≥ k Hamming bound ini menentukan , bahwa : o Banyaknya pattern bit uji paritas yang mungkin terjadi harus setidak-tidaknya sama dengan banyaknya cara , dimana kesalahan dapat terjadi sampai dengan t buah kesalahan bit o Untuk kode ( n, k ) berlaku hubungan : t ⎛n⎞ 2 n−k ≥ ∑ ⎜⎜ ⎟⎟ i =0 ⎝ t ⎠
⎛n⎞ ⎛n⎞ ⎛n⎞ ⎛n⎞ Ini berati bahwa 2n − k = 2q = ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ + LL + ⎜⎜ ⎟⎟ ⎝t⎠ ⎝0⎠ ⎝1⎠ ⎝2⎠ Untuk kode (7, 4) dan banyaknya kesalahan bit adalah t = 3 , maka : ⎛7⎞ ⎛7⎞ ⎛7⎞ ⎛7⎞ n−k 7−4 2 = 2 = 8 ≥ ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ ⎝0⎠ ⎝1⎠ ⎝2⎠ ⎝3⎠ Penyelesaian persamaan diatas dapat digunakan untuk membuat tabel berikut ini : Tabel kode-kode yang dapat mengoreksi kesalahan
Kode - kode yang dapat mengoreksi kesalahan tunggal ( t = 1 ) n k max Kode Efisiensi 4 1 (5, 2) 5 2 0.4 (6, 3) 6 3 0.5 (7, 4) 7 4 0.57 15 11 (15, 11) 0.73 Kode - kode yang dapat mengoreksi kesalahan ganda ( t = 2 ) n k max Kode Efisiensi (10, 4) 10 4 0 .4 (11, 4) 11 4 0.36 (15, 8) 15 8 0.53 20 11 (20, 11) 0.55 25 13 (25, 13) 0.52
9
Kode - kode yang dapat mengoreksi kesalahan ganda ( t = 3 ) n k max Kode Efisiensi (10, 2) 10 4 0.2 (15, 5) 15 5 0.33 23 12 (23, 12 ) 0.52 24 12 (24, 12 ) 0.55 • • •
• •
Jarak Hamming : perbedaan banyaknya posisi diantara 2 kata kode apa saja Jarak Hamming ini memegang peranan kunci didalam penaksiran kapasitas atau kemampuan kode-kode mengoreksi kesalahan Jarak Hamming = d H ≥ 2 t + 1 → d H min = 2 t + 1 dimana : t = banyaknya bit yang salah dan dapat dikoreksi Kode-kode yang dapat mengoreksi kesalahan tunggal : t = 1 → d H min = 2(1) + 1 = 3
JARAK HAMMING DAN BOBOT HAMMING (HAMMING DISTANCE and HAMMING WEIGHT)
4 7 Dari tabel tersebut dapat dilihat bahwa setip kata kode (setelah dibalik cara penulisannya ) berbeda satu-sama lain , dengan perbedaan paling tidak 3 posisi , yang dapat dilihat pada tabel dibawah ini : Tabel kode blok khusus
Sebagai contoh adalah kode blok ( 7, 4) ; Efisiensi kode = R =
•
No berita 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
• •
⎡0 ⎢0 ⎢ ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢1 ⎢ ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1` ⎢1 ⎢ ⎢1 ⎢1 ⎣
Kata kode
Berita 0 0 0⎤ 0 0 1 ⎥⎥ 0 1 0⎥ ⎥ 0 1 1⎥ 1 0 0⎥ ⎥ 1 0 1⎥ 1 1 0⎥ ⎥ 1 1 1⎥ 0 0 0⎥ ⎥ 0 0 1⎥ ⎥ 0 1 0⎥ 0 1 1⎥ ⎥ 1 0 0⎥ 1 0 1⎥ ⎥ 1 1 0⎥ 1 1 1 ⎥⎦
⇒
⎡0 ⎢0 ⎢ ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢1 ⎢ ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎣
0 0 0 0 0 0⎤ 0 0 1 0 1 1 ⎥⎥ 0 1 0 1 1 0⎥ ⎥ 0 1 1 1 0 1⎥ 1 0 0 1 1 1⎥ ⎥ 1 0 1 1 0 0⎥ 1 1 0 0 0 1⎥ ⎥ 1 1 1 0 1 0⎥ 0 0 0 1 0 1⎥ ⎥ 0 0 1 1 1 0⎥ ⎥ 0 1 0 0 1 1⎥ 0 1 1 0 0 0⎥ ⎥ 1 0 0 0 1 0⎥ 1 0 1 0 0 1⎥ ⎥ 1 1 0 1 0 0⎥ 1 1 1 1 1 1 ⎥⎦
Kata kode
Berita
dibalik menjadi
⎡0 ⎢1 ⎢ ⎢0 ⎢ ⎢1 ⎢0 ⎢ ⎢1 ⎢0 ⎢ ⎢1 ⎢0 ⎢ ⎢1 ⎢ ⎢0 ⎢1 ⎢ ⎢ 0` ⎢1 ⎢ ⎢0 ⎢1 ⎣
0 0 0⎤ 0 0 0 ⎥⎥ 1 0 0⎥ ⎥ 1 0 0⎥ 0 1 0⎥ ⎥ 0 1 0⎥ 1 1 0⎥ ⎥ 1 1 0⎥ 0 0 1⎥ ⎥ 0 0 1⎥ ⎥ 1 0 1⎥ 1 0 1⎥ ⎥ 0 1 1⎥ 0 1 1⎥ ⎥ 1 1 1⎥ 1 1 1 ⎥⎦
⇒
⎡0 ⎢1 ⎢ ⎢0 ⎢ ⎢1 ⎢1 ⎢ ⎢0 ⎢1 ⎢ ⎢0 ⎢1 ⎢ ⎢0 ⎢ ⎢1 ⎢0 ⎢ ⎢0 ⎢1 ⎢ ⎢0 ⎢1 ⎣
0 0 0 0 0 0⎤ 1 0 1 0 0 0 ⎥⎥ 1 1 0 1 0 0⎥ ⎥ 0 1 1 1 0 0⎥ 1 1 0 1 1 0⎥ ⎥ 0 ` 1 0 1 0⎥ 0 0 0 1 1 0⎥ ⎥ 1 0 1 1 1 0⎥ 0 1 0 0 0 1⎥ ⎥ 0 1 1 0 0 1⎥ ⎥ 1 0 0 1 0 1⎥ 0 0 1 1 0 1⎥ ⎥ 1 0 0 0 1 1⎥ 0 0 1 0 1 1⎥ ⎥ 0 1 0 1 1 1⎥ 1 1 1 1 1 1 ⎥⎦
Jadi jika terjadi kesalahan bit sampai dengan 2 buah , maka kesalahan tersebut tidak akan menyebabkan kodenya menjadi kode yang sama dengan setiap kode lainnya , apapun juga kode lain itu Berita dan kata kode (serta berita dan kata kode yang dibalik cara penulisannya) yang mungkin terjadi adalah sebagai tabel berikut ini :
10
•
Didalam hal ini penulisan kata kode yang telah dibalik susunannya akan mampu memberi tahu pengguna bahwa kesalahan transmisi telah terjadi , meskipun tidak dapat mengoreksi kesalahan-kesalahan tersebut
•
Suatu kode khusus ditampilkan pada tabel berikut ini :
• Contoh : Kode blok(7, 4) ; kode datanya terdiri atas k bit atau 4 bit ; kode paritasnya terdiri atas q bit atau 3 bit Jenis kode data yang terdiri atas 4 bit adalah 2k = 24 = 16 buah . Semua jenis kode data yang masing-masing terdiri atas 4 bit dapat digambarkan sebagai berikut : ⎡0 ⎢0 ⎢ ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢1 ⎢ ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎣
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0⎤ 1 ⎥⎥ 0⎥ ⎥ 1⎥ 0⎥ ⎥ 1⎥ 0⎥ ⎥ 1⎥ 0⎥ ⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥ 1 ⎥⎦
Misalkan matrik uji paritas adalah : ⎡ h11 h12 h13 h14 ⎤ H = ⎢⎢h21 h22 h23 h24 ⎥⎥ ⎢⎣ h31 h32 h33 h34 ⎥⎦ Bit uji paritasnya adalah :
11
⎡ h11 h12 h13 h14 ⎤ ⎡ h11d1 ⊕ h12 d 2 ⊕ h13 d 3 ⊕ h14 d 4 ⎤ d 2 d 3 d 4 ]⎢⎢h21 h22 h23 h24 ⎥⎥ = ⎢⎢h21d1 ⊕ h22 d 2 ⊕ h23 d 3 ⊕ h24 d 4 ⎥⎥ ⎢⎣ h31 h32 h33 h34 ⎥⎦ ⎢⎣ h31d1 ⊕ h32 d 2 ⊕ h33 d 3 ⊕ h34 d 4 ⎥⎦ ⎡1 1 1 0 ⎤ ⎡ c 5 ⎤ ⎡ d 1 ⊕ d 2 ⊕ d 3 ⎤ Jika H = ⎢⎢0 1 1 1⎥⎥ → ⎢⎢c6 ⎥⎥ = ⎢⎢d 2 ⊕ d 3 ⊕ d 4 ⎥⎥ ⎢⎣1 1 0 1⎥⎦ ⎢⎣c7 ⎥⎦ ⎢⎣ d1 ⊕ d 2 ⊕ d 4 ⎥⎦ Rumus untuk kata kode adalah c = dG = [dI k P ] = dI k H T c = Seluruh kata kode yang mungkin terjadi
⎡ c5 ⎤ ⎢c ⎥ = dH = [d 1 ⎢ 6⎥ ⎢⎣c7 ⎥⎦
[
c
d ⎡0 ⎢0 ⎢ ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 ⎢1 ⎢ ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎣
0 0 0⎤ 0 0 1⎥⎥ 0 1 0⎥ ⎥ 0 1 1⎥ 1 0 0⎥ ⎥ 1 0 1⎥ 1 1 0⎥ ⎡1 ⎥ 1 1 1⎥ ⎢⎢0 0 0 0⎥ ⎢0 ⎥⎢ 0 0 1⎥ ⎣0 ⎥ 0 1 0⎥ 0 1 1⎥ ⎥ 1 0 0⎥ 1 0 1⎥ ⎥ 1 1 0⎥ 1 1 1⎥⎦
P
Ik
0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1
⎡0 ⎢0 ⎢ ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎢0 1⎤ ⎢0 ⎢ 1⎥⎥ ⎢0 = 0⎥ ⎢1 ⎥ ⎢ 1⎦ ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎢ ⎢1 ⎢1 ⎣
]
W (x ) non − zero weight
0 0 0 0 0 0⎤ ⎡0⎤ 0 0 1 0 1 1⎥⎥ ⎢⎢3⎥⎥ 0 1 0 1 1 0⎥ ⎢3⎥ ⎥ ⎢ ⎥ 0 1 1 1 0 1⎥ ⎢4⎥ 1 0 0 1 1 1⎥ ⎢4⎥ ⎥ ⎢ ⎥ 1 0 1 1 0 0⎥ ⎢3⎥ 1 1 0 0 0 1⎥ ⎢3⎥ ⎥ ⎢ ⎥ 1 1 1 0 1 0⎥ ⎢4⎥ = 0 0 0 1 0 1⎥ ⎢3⎥ ⎥ ⎢ ⎥ 0 0 1 1 1 0⎥ ⎢4⎥ ⎥ ⎢ ⎥ 0 1 0 0 1 1⎥ ⎢4⎥ 0 1 1 0 0 0⎥ ⎢3⎥ ⎥ ⎢ ⎥ 1 0 0 0 1 0⎥ ⎢3⎥ 1 0 1 0 0 1⎥ ⎢4⎥ ⎥ ⎢ ⎥ 1 1 0 1 0 0⎥ ⎢4⎥ 1 1 1 1 1 1⎥⎦ ⎢⎣7⎥⎦
W ( x ) = non-zero weight = pembobot bukan nol = banyaknya bit bukan nol dalam 1 kata kode
W ( x )min = d H min ; d H min = 2 t + 1
=3 min jika t = 1
• •
Untuk kode blok (n, k) ; berarti q= n - k Misalkan n = 7 ; k = 4 , berarti q = m = 3; khusus kode ini memenuhi hubungan : n = 2 q − 1 → 23 − 1 = 8 − 1 = 7 O Tidak semua jenis kode blok memenuhi hubungan itu ; misalnya kode blok (7, 3) ; jika diterapkan rumus diatas , maka n = 2 q − 1 = 2 4 − 1 = 16 − 1 = 15 ≠ 7
•
Efisiensi kode = code rate =
k n−q q = = 1− n n n
O Untuk kode blok khusus sebagaimana contoh diatas : O Untuk efisiensi kode ≅ 1 → O Untuk kode blok khusus
Berarti q >> 1
k q = 1− q n 2 −1
k ≅1 n
k q q ≅ 1 = 1− q → q ≅ 0 → 2q −1 ≅ ∞ → 2q ≅ ∞ n 2 −1 2 −1
12
• •
Kata kode yang ke-i adalah xi yang terdiri atas : o mi buah bit berita , dimana i = 1, 2, 3 …… k o ci - k buah bit koreksi, dimana i = k+1, k+2, ……n. Sebagai contoh adalah sebuah kata kode ( 7,4 ) o ini berarti n = 7 dan k = 4 q = banyak-nya bit uji paritas = 3 o Dengan 7 bit per kata kode berarti banyaknya kode yang bisa terjadi adalah = 27 = 128 jenis kata kode yang berbeda satu sama lain o Namun karena kode untuk data hanya terdiri atas 4 bit saja, maka hanya terdapat 24 = 16 jenis kata kode saja yang digunakan, dari 128 buah jenis kata kode yang mungkin terjadi o Bentuk kata kode tersebut adalah : x = [m1 m2 m3 m4 c1 c 2 c3 ] T o Jika H = matrix uji paritas, maka H adalah matrix persegi q x n yang bentuknya sebagai berikut : q k
⎡ h11 ⎢h 21 H = ⎢ ⎢ M ⎢ ⎢⎣ h q 1
h12 h 22 M hq 2
L L M L
h1 k h2 k M h qk
1 0
0 1
0 0
L 0
M 0
M 0
M 0
M L
0⎤ 0 ⎥⎥ M⎥ ⎥ 1 ⎥⎦
q
o dimana bagian kanan dari matrix tersebut adalah matrix satuan (unit matrix) qxq o Dengan pemilihan matrix uji paritas tersebut maka harus dipenuhi : H x = 0 ( dimana x = kode tertentu )
Dengan demikian :
⎡ h11 h12 L h1k ⎢h h22 L h2k 21 Hx = ⎢ ⎢M M M M ⎢ ⎢⎣hq1 hq 2 L hqk
⎡ h11 h12 L h1k ⎢h h22 L h2k 21 =⎢ ⎢M M M M ⎢ ⎣⎢hq1 hq 2 L hqk
1 0 0 L 0⎤ 0 1 0 0 0⎥⎥ m m2 L mk M M M M M⎥ 1 ⎥ 0 0 0 L 1⎥⎦ ⎡ m1 ⎤ ⎢m ⎥ ⎢ 2⎥ 1 0 0 L 0⎤ ⎢ M ⎥ ⎡0⎤ ⎢ ⎥ 0 1 0 L 0⎥⎥ ⎢mk ⎥ ⎢0⎥ =⎢ ⎥ M M M M M ⎥ ⎢ c1 ⎥ ⎢ M ⎥ ⎥⎢ ⎥ ⎢ ⎥ 0 0 0 L 1⎦⎥ ⎢ c2 ⎥ ⎣0⎦ ⎢ M ⎥ ⎢ ⎥ ⎢⎣ cq ⎥⎦
[
c1 c2 L cq
]
T
13
Maka : h j1 m1 ⊕ h j 2 m 2 ⊕ L ⊕ h jk m k ⊕ c j = 0 ; j = 1, 2, L q Misalkan sebuah kata kode x dipancarkan mengalami beberapa kesalahan bit-nya sewaktu diteri-ma di tujuan. Jika kata kode yang diterima adalah y , dimana pola kesalahannya (errorpattern) adalah e. Maka y = x ⊕ e. Ini berarti setiap kata kode yang diterima adalah y i = xi ⊕ ei dengan i = 1, 2, L k . ⎧1 → y i ≠ xi Jika ei = ⎨ ⎩0 → y i = x i
Contoh : x = [0 1 0 0 1]
T
Kesalahan terjadi pada digit ke-3 dan ke-5
e = [0 0 1 0 1] T →
y = [0 1 1 0 0] T Jika di penerima kesalahan e dapat ditentukan , maka semua kesalahan yang terjadi dapat diko-reksi. Untuk dapat menentukan kesalahan “e” dari kata kode yang diterima “ y” , maka kata kode yang dipancarkan “x” harus diketahui. Untuk itu harus dihitung sebuah q-digit syndrome. Yang dimaksudkan dengan q-digit syndrome adalah : s = Hy Lebih lanjut s dapat diuraikan menjadi : s = Hx ⊕ He Karena Hx = 0 , maka : s = He Jadi dapat dilihat bahwa jika tanpa kesalahan atau e = 0 maka s = 0 . Jika berita yang diterima hanya salah 1 digit saja, misalkan yang mengalami kesalahan digit ke-j, maka dapat dibuktikan bahwa : s = [h1 j h2 j L hqj ] T
dimana j ≤ k
Contoh : Kode ( 7,4 ) berarti k = 4 ; n = 7 ; q =3 Kode paritas untuk setiap berita adalah : k
q
h 12 L h 1 k q1 0 0 L 0⎤ ⎡ h 11 ⎢h h 22 L h2k 0 1 0 0 0⎥ 21 H = ⎢ Hc = 0 ( dimana c = kode tertentu yang dikirim) ⎥ ⎢ M M M M M M M M M⎥ ⎢ ⎥ hq2 L h qk 0 0 0 L 1 ⎦⎥ ⎣⎢ h q 1
q
]Dengan demikian : ⎡ h11 ⎢h 21 Hc=⎢ ⎢ M ⎢ ⎢⎣ h q 1
h12 h 22 M hq 2
L L M L
h1 k h2 k
1 0
0 1
0 0
L 0
M
M 0
M 0
M 0
M L
h qk
0⎤ 0 ⎥⎥ d M⎥ 1 ⎥ 1 ⎥⎦
[
d2
L
dk
c1
c2
L
cq
]
T
14
⎡ h11 ⎢h 21 Hc = ⎢ ⎢ M ⎢ ⎢⎣hq1
h12 h22
L h1k L h2 k
M M M hq 2 L hqk
1 0 0 L 0⎤ 0 1 0 L 0⎥⎥ M M M M M⎥ ⎥ 0 0 0 L 1⎥⎦
⎡ d1 ⎤ ⎢d ⎥ ⎢ 2⎥ ⎢ M ⎥ ⎡0 ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ d k ⎥ = ⎢0 ⎥ ⎢ c1 ⎥ ⎢ M ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ c 2 ⎥ ⎣0 ⎦ ⎢M⎥ ⎢ ⎥ ⎢⎣ c q ⎥⎦
h j1 d 1 ⊕ h j 2 d 2 ⊕ L ⊕ h jk d k ⊕ c j = 0 ; j = 1, 2, L q Untuk : q = 3 ; k = 4 ; d1 = 0 d 2 = 1 d3 = 1 d 4 = 0 :
j = 1 → h11 0 ⊕ h121 ⊕ h131 ⊕ h14 0 ⊕ c1 = 0 → h121 ⊕ h131 ⊕ c1 = 0 •
Matrix Uji Paritas adalah :
c k +1 ⎡ ⎢ ck+2 ⎢ ⎢ M ⎢ ⎣⎢ c n = c k + q
⎤ ⎡ h 11 ⎥ ⎢ ⎥ = ⎢ h 21 ⎥ ⎢ M ⎥ ⎢ ⎦⎥ ⎣⎢ h q 1
h 12 h 22
L L
M
M
hq2
L
h1 k ⎤ ⎡ d 1 h 2 k ⎥⎥ ⎢ d 2 ⎢ M ⎥ ⎢ M ⎥ ⎢ h qk ⎦⎥ ⎣ d k
⎤ ⎥ ⎥ ⎥ ⎥ ⎦
⎡d ⎤ h 14 ⎤ ⎢ 1 ⎥ d h 22 h 23 h 24 ⎥⎥ ⎢ 2 ⎥ ⎢d ⎥ h 32 h 33 h 34 ⎥⎦ ⎢ 3 ⎥ ⎣d 4 ⎦ c 5 = h 11 d 1 ⊕ h 12 d 2 ⊕ h 13 d 3 ⊕ h 14 d 4 c 6 = h 21 d 1 ⊕ h 22 d 2 ⊕ h 23 d 3 ⊕ h 24 d 4 c 7 = h 31 d 1 ⊕ h 32 d 2 ⊕ h 33 d 3 ⊕ h 34 d 4
⎡c5 → ⎢⎢ c 6 ⎢⎣ c 7
• • • •
⎡ h 11 ⎤ ⎥ = ⎢h ⎢ 21 ⎥ ⎢⎣ h 31 ⎥⎦
h 12
h 13
Nilai syndrome atau s ini sama dengan isi kolom ke-j dari kolom matrix uji paritas H Karena itu syndrome memberikan informasi seolah-olah tidak ada kesalahan yang terjadi (no error) , atau posisi sebuah kesalahan asalkan semua kolom matrix uji paritas H adalah berbeda dan bukan nol Dengan demikian didapatkan kode pengoreksi kesalahan tunggal (jika kesalahan yang terjadi hanya 1, maka langsung dikoreksi) Jika digunakan dengan model ini, maka suatu kode (n,k) akan mempunyai Probabilitas Kesalahan :
Pe , word ≈ Pn (2)
Pe , bit ≈ •
k 2 Pn (2) ≈ k ( n − 1 ) c 2 n
Namun kesalahan-kesalahan yang terjadi berulang-ulang (multiple errors) akan menyebabkan keruwetan atau komplikasi
15
•
• •
o karena meskipun kesalahan-kesalahan yang sebenarnya itu bisa dihilangkan, tapi akibatnya akan salah didalam membetulkan digit berita lainnya o yang mana beritanya akan menjadi lebih jelek o Akibatnya dikehendaki kode yang lebih kuat kecuali jika c sebegitu kecil sehingga kesalahan-kesalahan yang berulang akan amat jarang terjadi. Sayangnya dengan melengkapi suatu syndrome dan matrix uji paritas yang tepat untuk mengoreksi kesalahan yang berulang-ulang adalah : o suatu kerja yang jauh lebih ruwet o Oleh karena itu kode pengoreksi dua kesalahan yang pertama kali dibuat orang : lebih didasarkan pada coba-coba (trial-and-error) daripada dirancang berdasarkan metode tertentu. Akhirnya Slepian pada tahun 1956 mengambil teori koding yang berdasarkan sepenuhnya pada matematika, pada saat dia : o berhasil menemukan relasi konsep koding dengan aljabar modern. Segera setelah itu , dengan memakai teori medan Galois, para ahli yang bernama : o Bose, Chaudhuri dan Hocquenghem mengembangkan ke-lompok kode yang dapat mengoreksi kesalahan yang berulang-ulang (sekarang disebut dengan kode BCH (singkatan dari Bose-Chaudhuri-Hocquenghem) yang : efisien dan mempunyai hubungan relative sederha-na dengan persyaratan perangkat keras bagi coding dan dekoding.
Pendeteksian Kesalahan Dengan Kode Siklis -
-
-
-
Meskipun sebagian besar upaya didalam penkodean (coding) yang telah dipelajari adalah yang berkaitan dengan kode-kode FEC = Forward Error Correction , namun pendeteksian kesalahan juga dipakai secara luas dilam komunikasi data modern Pendeteksian kesalahan tersebut biasanya memerlukan lintasan catubalik dari penerima informasi ke pemancar , yang memberi tahu bahwa telah terjadi kesalahan bit yang diterima , yaitu urutan bit informasi tidak cocok dengan urutan bit paritasnya Selanjutnya pemancar akan mengirim ulang urutan bit katakode yang benar Beberapa versi implementasi FEC adalah dengan cara : o Pengenalan negatip (NAKs = Negative Acknowledments) berarti lintasan catubalik hanya diterapkan terhadap signal yang diterima salah saja , dimana pemancar akan mengirim ulang signal informasi jika signal NAK diterima o Pengenalan positip (ACKs) berati bahwa lintasan catubalik hanya diterapkan terhadap signal yang diterima dengan benar saja , dimana akan secara otomatis dikirim ulang signal informasi dari pemancar jika tidak diterima signal ACK , selama interval waktu tertentu o Kombinasi ACK dan NAK Cara seperti yang disebutkan diatas disebut ARQ = Automatic Repeat reQuest , atau pengenalan dengan cara teknik pengiriman kembali (retransmission) Semua jaringan switching data-paket dan jaringan komputer melakukan pendeteksian kesalahan dengan pengiriman kembali bilamana kesalahan terdeteksi Contoh jaringan-jaringan tersebut adalah : o Jaringan-jaringan dengan pembagian waktu (time-shared networks) o Jaringan-jaringan data untuk masyarakat (public-data networks)
16
o
-
-
Jaringan-jaringan perusahaan swasta (private corporate networks) , misalnya perbankan , pemesanan tiket pesawat udara , penjualan produk manufacture secara eceran , dan sebagainya) dan jaringan-jaringan yang terus berkembang , yang menggunakan banyak komputer untuk komunikasi data secara bersama Jaringan-jaringan ini terdiri atas banyak saluran komunikasi (jalur = link) yang dihubungkan dengan berbagai topologi jaringan , dengan pendeteksian kesalalahan dilakukan secara umum terhadap jalur-lalur tersebut Kode siklis digunakan paling sering digunakan didalam melakukan fungsi pendeteksian kesalahan Blok-blok data yang dikirimkan didalam jaringan-jaringan ini sering kali disebut dengan paket Paket-paket tersebut dapat berentang dari 500 sampai dengan 1000 bit panjangnya , bahkan lebih Jadi pengkoreksian kesalahan untuk kata-kode kode sepanjang itu bukanlah pekerjaan yang mudah Pendeteksian kesalahan terhadap kata-kata kode yang bit uji paritasnya tetap dapat mudah dilakukan Adanya q buah bit uji paritas memungkinkan setiap kesalahan lonjakan (burst error) sepanjang q buah bit (ataupun kurang) tersebut untuk dideteksi kesalahannya (jika terjadi) Pendeteksian tersebut tidak tergantung pada panjang paket data Karena pada umumnya dirancang agar k >> q (agar efisiensi pengkodean tinggi) , maka deret generator g ( x ) , atau enkoder siklis jenis-sisa (remaider-type cyclic encoder) pada umumnya digunakan didalam aplikasi pendeteksian kesalahan tersebut Misalkan kode siklis (n, k) , pada pendeteksian ini , dimana n = 10 ; k = 6 ; q = 4 Pada pendeteksian ini , k buah bit data tersebut dikelompokkan menjadi Perlu untuk dicatat bahwa hanya terdapat 1 bit saja didalam setiap lonjakan b buah bit (ataupun kurang) yang akan mempengaruhi setiap bit uji paritas , dan selanjutnya dapat yang dideksi Hal ini adalah benar , apakah lonjakan-lonjakan tersebut terjadi dalam salah satu dari segmen-segmen b buah bit , dimana urutan data telah dikelompokkan , ataupun bertumpang tindih sampai meluberi 2 buah segmen seperti itu Sebagai tambahan terhadap pendeteksian sebuah lonjakan didalam b buah bit (ataupun kurang) suatu kode linier dengan bit uji paritas sebanyak q = b buah bit akan mendeteksi lonjakan-lonjakan yang lebih panjang dengan
prosentasi yang tinggi
- Jika sebagian daripada lonjakan b buah bit tersebut menyebabkan : o b > q , maka yang tetap tak terdeteksi pada kode siklis (n, k) adalah
-
2− q , jika b > q + 1 o Jika b = q + 1 maka yang tetap tak terdeteksi pada kode siklis (n, k) adalah 2− (q −1) Teorema o Jika banyaknya kode paritas q cukup banyak , maka hampir semua kesalah-an dapat terdeteksi o Sebagai misal jika q = 16 , maka semua lonjakan kesalahan sebanyak 16 buah ataupun kurang akan dapat dideteksi
17
o Jika bagian lonjakan kesalahan yang terjadi menyebabkan b > 17 , maka yang
o
o o o
o
o
o
o o
o
tetap tak dapat dideteksi adalah 2−16 s.d . 4 x10−6 (suatu jumlah yang betul-betul kecil) Untuk membuktikan teorema tersebut , misalkan suatu lonjakan kesalahan terjadi di pengelompokan b buah bits , mulai dari bit yang ke-i dan berakhir dengan bit yang ke- [i + (b − 1)] Dalam bentuk deret lonjakan kesalahan (burst polynomial : b( x ) = x' b1 ( x ) b1 ( x ) deret berpangkat tertinggi (b −1) → b1 (x ) = xb −1 + xb − 2 + L + xi + xi −1 + L + xb −b −1 + 1 Jika diperlihatkan dengan gambar , dimana adanya kesalahan ditunjukkan dengan bit 1 , yang terjadi pada bit i dan bit diakhir lonjakan , yaitu bit (i + b − 1) sebagai berikut ini : LLLL 1 1 ← Pattern Kesalahan − − LLL − − bit (i + b − 1) LLLL bit i Lonjakan kesalahan sepanjang b buah bit mempunyai kemungkinan sebanyak 2b − 2 buah simbol (1 atau 0) diantara permulaan dan akhir , yang bedasarkan difinisi , masing-masing dikendalai dengan bit 1 (untuk menyatakan bahwa pada urutan bit tersebut terjadi kesalahan) Hal ini sesuai dengan 2b − 2 kemungkinan pattern lonjakan kesalahan disepanjang b buah bit tadi , atau kemungkinan terjadinya 2b − 2 buah bentuk daripada deret b1 ( x ) Oleh karena perhitungan bit uji paritas di penerima dilakukan dengan jalan pembagian oleh deret generator g ( x ) yang mempunyai pangkat tertinggi r , satu kesalahan tetap tak terdeteksi , jika dan hanya jika b1 ( x ) dapat dibagi oleh g ( x ) Dari sini persyaratan bagi suatu pattern kesalahan lonjakan untuk tetap tak terdeteksi adalah bahwa b1 ( x ) mempunyai b1 (x ) = g (x )Q( x ) Karena b1 ( x ) adalah deret dengan pangkat tertinggi (b − 1) dan g ( x ) adalah deret dengan pangkat tertinggi q , maka Q( x ) adalah deret dengan pangkat tertinggi [(b −1) − q] Kemungkinan yang bisa terjadi adalah : Yang pertama adalah : lonjakan kesalahan sepanjang (b −1) = q , sehingga pangkat tertinggi daripada Q( x ) adalah [(b − 1) − q ] = 0 , sehingga Q( x ) = 1 ; dengan demikian hanya terdapat 1 pattern lonjakan yang tak dapat terdeteksi • Bagian lonjakan yang tak terdeteksi secara sederhana dirumuskan sebagai 1 Bagian dari lonjakan kesalahan yang tak terdetekasi = b − 2 2 − ( q −1) =2 dimana b − 1 = q Yang kedua adalah jika b − 1 > q ; oleh karena pangkat tertinggi deret Q( x ) adalah [(b −1) − q ] , dan harus berakhir dengan 1 , maka suku daripada deret Q( x ) adalah sebanyak [(b − 1) − q − 1] , yang masing-masing dengan koefisien 1 atau 0
18
2b −1− q −1 = 2q b−2 2 Dua kemungkinan hasil yang diperoleh diatas membuktikan bahwa kode yang dapat mendeteksi kesalahan dengan bit uji paritas moderat atau cukup , akan mendeteksi kejadian pada sebagian besar pattern lonjakan kesalahan Bagian dari lecutan kesalahan bit yang tak terdetekasi =
o
Karena semua jaringan data maupun komputer yang modern menggunakan beberapa bentuk deteksi kesalahan dengan teknik ARQ bila menerima paket data yang salah , maka : Pemakaian teknik pendeteksi kesalahan akan dapat mengurangi probabilitas terjadinya kesalahan suatu paket data , sehingga menjadi 2− q Prosedur deteksi kesalahan yang khusus , mempunyai bit uji paritas dengan rentang antara 8 s.d. 32 buah bit Standard internasional untuk pengontrolan jalur data (link data control) , adalah menggunakan protokol HDLC (High-Level Data Link Control) , dimana pada pengontrolan jalur ini menggunakan : • bit uji paritas sebanyak 16 bit dan deret generator g (x ) = x16 + x12 + x 5 + 1
o Perhitungan sebenarnya daripada probabilitas kesalahan suatu paket atau blok data yang dilindungi oleh suatu bit uji paritas siklis adalah : sulit dilakukan karena masih kurangnya pengetahuan tentang mekanisme yang menghasilkan ledakan-ledakan kesalahan khusus Jika mekanisme yang dimaksudkan adalah : • noise suhu yng terus-menerus terjadi dan pengaruh-pengaruhnya diberi model sebagai AWGN = Additive White Gaussian Noise , maka : o kesalahan-kesalahan bit yang berturut-turut didalam suatu burst (lecutanan bit) akan bebas satu sama lain o Probabilitas bahwa suatu paket atau blok sepanjang n bit akan diterima salah adalah : [1 − (1 − p )] n ≅ np ; np << 1 ; p = probabilitas kesalahan bit Namun pada kanal telepon band terbatas , yang paling sering dipakai sebagai tulang punggung jalur komunikasi untuk jaringanjaringan data , noisenya tidak dimodelkan sebagai kanal AWGN Lecutan-lecutan kesalahan pada kanal ini berpengaruh terhadap : • memory • menimbulkan kesalahan yang tergantung pada : o bit-bit yang berturut didalam suatu aliran data (data stream) o Hal ini membuat perhitungan probabilitas-probabilitas kesalahan sangat sulit o Namun demikian , pengujian-pengujian telah menunjukkan bahwa : pengaruh kesalahan terhadap blok-blok data : • membuat suatu kesalahan blok bergerak sebanding sewaktu panjang blok bertambah o hal ini adalah model yang tepat untuk : probabilitas kesalahan blok yang mempunyai hubungan yang sebanding dengan panjang blok
19
• • •
o Dengan demikian dapat dirumuskan : Probabilitas kesalahan blok = Pb ≅ np dimana p = suatu parameter yang ditentukan berdasarkan pengamatan o Jadi semakin panjang blok , maka semakin besar kesalahan yang terjadi Jika dilakukan pengujian siklis , hasil yang sederhana adalah 2− q kejadian kesalahan tak dapat dideteksi (hal ini dilakukan dengan menganggap panjang lonjakan b > q , atau q >> 1 Probabilitas kesalahan blok keseluruhan dapat didekati dengan : Pe ≅ np 2− q Contoh : 500 (105 ) ≅ 2 x10 −5 1. p = 10 −5 ; n = 500 bits ; q = 8 bits → Pe ≅ (500 ) (10 −5 )(2 −8 ) = 256
2.
(
)(
)
p = 10 − 5 ; n = 1000 bits ; q = 32 bits → Pe ≅ (1000 ) 10 − 5 2 − 32 =
( ) ≅ 4 (10 ) ≅ 4 (10 ) ≅ 4 x10 64 (256 ) (2 )
1000 10 −5 8 4
−5
−14
−12
3
Rangkuman -
-
-
-
-
Tekanan pembahasan sistem komunikasi digital ini adalah mengenai pengoptimalan rancangan sistem dengan memaximalkan kecepatan transmisi informasi , yang menghadapi kendala-kendala berupa daya signal terbatas , noise dan lebar pita Beberapa aspek optimisasi dibahas dari berbagai sudut pandang Dalam pembahasan tentang komunikasi biner , diutarakan tentang pengaturan ambang pengambilan keputusan , apakah suatu signal diputuskan bernilai 0 atau 1 Konsep matched filter dibahas untuk pemaximalan SNR pada transmisi biner Ketidak samaan Schwarz digunakan didalam membicarakan jaringan emphasis (preamphasis dan deemphasis) yang optimal untuk transmisi analog FM dan AM Pembahasan tentang SNR , perubahan lebarpita pada sistem PCM Teori Shanon tentang sistem transmisi digital optimum Pembahasan transmisi optimum dengan cara yang lebih statistik didalam sistem komunikasi digital Prosedur optimisasi pada sistem komunikasi digital berdasarkan minimisasi probabilitas terjadinya kesalahan bit , dalam keadaan adanya AWGN Prosedur ini akan menjawab pertanyaan “apakah ada gelombang-gelombang biner yang optimum dan mekanisme penerima yang optimum untuk meminimalkan probabilitas terjadinya kesalahan Pembahasan dimulai dari sample-sample signal tunggal yang diterima dan selanjutnya melakukan generalisasi terhadap sample-sample yang berulang (multiple) secara bebas Dari probabilitas distribusi yang diketahui dapat diperoleh prosedur pemrosesan optimum , yang terdiri atas peningkatan pengaturan perbandingan kemungkinam (likelihood ratio) dan menentukan apakah perbandingan tersebut lebih besar atau lebih kecil dibandingkan dengan suatu konstanta yang diketahui Sebagai alternatip , prosedur optimum terdiri atas sample-sample signal terima ruang berdimensi-m , yang dapat dibagi menjadi 2 daerah untuk pengambilan keputusan yang tidak tumpang tindih (disjoint decision regions) Dengan melakukan pensignalan multidimensi yang menggunakan signal-signal orthogonal M-susun , maka : o dapat diperoleh penurunan probabilitas kesalahan , namun : memerlukan lebarpita yang lebih lebar rangkaian memjadi bertambah komplex
20
-
-
-
-
Cara diatas adalah hal yang khusus daripada teorema kapasitas kanal Shanon , dimana : • secara teoritis dapat dibuat sistem komunikasi dengan probabilitas kesalahan rendah , meskipun terdapat adanya noise AWGN , sehingga : o dapat dilakukan operasi pengkodean dan pendekodean secara memuaskan o Hal diatas dimungkinkan asalkan : kecepatan transmisi bit = R bps tidak melebihi kapasitas kanal , yang mana : kapasitas kanal tersebut ditentukan oleh : • lebarpita kanal transmisi , daya signal rata-rata dan kerapatan spektral Penggunaan metode-metode untuk mendeteksi dan mengoreksi kesalahan bit adalah : o sebagai suatu cara untuk memperbaiki kinerja sistem komunikasi digital Cara yang umum dilakukan untuk mendeteksi dan mengoreksi kesalahan bit adalah : o dengan jalan menyisipkan bit-bit uji paritas dalam aliran biner (binary stream) , sehingga dimungkinkan untuk : mendeteksi dan mengoreksi kesalahan dalam jumlah tertentu Langkah yang diambil dalam hal ini adalah : o memilih kode yang mendekati kinerja kesalahan yang diramalkan oleh Shanon
PEMBUATAN KODE SIKLIS • • • •
Deret generator g ( x ) langsung dapat digunakan untuk pembuatan kode siklis Pembuatan kode secara serial dapat dilakukan dengan mengimplementasikan register geser Dasar pemikirannya sebagai berikut : Berdasarkan rumus untuk deret katakode = c( x ) = a( x )g (x ) , dimana : o deret urutan data : d (x ) = d1 x k −1 + L + d k −1 x + d k ; derajat (pangkat tertinggi) deret ini adalah (k − 1) o namum derajat deret urutan data bisa menjadi kurang dari (k − 1) jika d1 = 0 hal ini tergantung pada nilai-nilai bit data o operasi x n − k d ( x ) akan menghasilkan deret berderajat (n − k ) + (k − 1) = (n − 1) , atau lebih kecil bila koefisien dari suku deret yang berpangkat (n − 1) adalah 0 o
x n − k d (x ) = hasil pembagian + sisa hasil pembagian = q( x ) + r ( x ) g (x )
x n− k d ( x ) o Derajat deret adalah : g (x )
o
[(n − k ) + (k − 1) − { pangkat tertinggi g (x )= q }] = (n − 1) − q = k − 1 Deret kata kode = c( x ) = a( x )g ( x ) = x n − k d ( x ) + r ( x ) x n − k d (x ) x n − k d (x ) = sisa hasil pembagian r ( x ) = rem g (x ) g (x ) Contoh :
21
Buktikan bahwa kode (7, 3) jika kode datanya = d = 111 , maka kata kodenya adalah : c = (1110100 ) Bukti : 2 d = 111 → d ( x ) = x + x + 1
(
)
x n − k d (x ) x7 −3 x 2 + x + 1 x6 + x5 + x 4 = rem 4 = g (x ) x + x3 + x 2 + 1 x 4 + x3 + x 2 + 1 x2 x 4 + x3 + x 2 + 1 x6 + x5 + x 4 x6 + x5 + x 4 + x 2 rem = x 2 x n − k d (x ) r ( x ) = rem = x 2 = 1x 2 + 0 x + 0(1) g (x ) Jadi c = (d , koefisien - koefisien rem ) = [(1110 ), (100 )] = (1110100 ) r ( x ) = rem
Arithmatika polynomial Sebelum menentukan deret generator g ( x ) , akan dibahas lebih dahulu tentang arithmatika (perhitungan aljabar) perkalian dan pembagian polynomial sebagai berikut : • Misalkan w(D ) = w0 + w1 D + w2 D 2 + LL + wk −1 D k −1 adalah deret ukur , dimana nilai setiap w j •
= 0 atau 1 j = 0 , 1, 2LLk −1
Jika semua nilai w j
j = 0 , 1, 2LLk −1
= 1 → w(D ) = 1 + D + D 2 + LL + D k −1
o Jika k = 4 → w(D ) = 1 + D + D 2 + D 3
•
Jika untuk k = 6 tidak semua w j o
• •
bernilai 1 , misalnya : j = 0 , 1, 2LLk −1
w0 = 1 ; w1 = 1 ; w2 = 0 ; w3 = 0 ; w4 = 1 ; w5 = 1 , maka :
w(D ) = 1 + D + w4 D 4 + w5 D 5 Polynomial tersebut memberi gambaran yang sesuai dengan vektor informasi – k bit : w = w0 w1 w2 LL wk −1 Perhatikanlah beberapa polynomial berikut : g (D ) = g 0 + g 1 D + g 2 D 2 + L L + g n −1 D n −1 y (D ) = y 0 + y1 D + y 2 D 2 + L L + y n −1 D n −1
x (D ) = x 0 + x1 D + x 2 D 2 + L L + x n −1 D n −1
•
e (D ) = e 0 + e1 D + e 2 D 2 + L L + e n −1 D n −1
Penjumlahan modulo-2 daripada 2 buah polynomial , misalnya : y ( D ) = x ( D ) + e( D )
y (D ) = x0 + x1 D + x 2 D 2 + LL + x n −1 D n −1 + e0 + e1 D + e2 D 2 + LL + en −1 D n −1
22
y (D ) = y 0 + y1 D + y 2 D 2 + LL + y n −1 D n −1 = (x 0 + e0 ) + (x1 + e1 )D + ( x 2 + e 2 )D 2 + L + (x n −1 + e n −1 )D n −1
Jadi : y 0 = x 0 + e0 y1 = x1 + e1 M y n −1 = x n −1 + en −1 Secara umum : y j = x j + e j •
Perkalian daripada 2 polynomial , misalnya : g (D )w(D ) = g 0 + g1 D + g 2 D 2 + LL + g n −1 D n −1 w0 + w1 D + w2 D 2 + LL + wn −1 D n −1
{
}{
}
g (D )w(D ) = g 0 w0 + g 0 w1 D + g 0 w2 D 2 + L + g 0 wn −1 D n −1 + g 1 w0 D + g 1 w1 D 2 + g 1 w2 D 3 + L + g 1 wn −1 D n + L + g n −1 w0 D n −1 + g n −1 w1 D n + g n −1 w2 D n +1 + L + g n −1 wn −1 D 2 n − 2
g (D )w(D ) = g 0 w0 D 0 + (g 0 w1 + g 1 w0 )D + (g 0 w2 + g 1 w1 + + g 2 w0 )D 2 + (g 0 w3 + g 1 w2 + g 3 w0 )D 31 wn −1 D n + (g 0 wn −1 + g 1 wn − 2 + g 2 wn − 2 + L + g n −1 w0 )D n −1 + (g 0 wn − 2 + g 1 wn −3 + g 2 wn − 4 + L)D n − 2 + L
Dapat ditulis : g (D )w(D ) = ( g n − k wk −1 )D n +1
+ ( g n − k wk − 2 + g n − k −1 wk −1 ) D n − 2
+ ( g n − k wk −3 + g n − k −1 wk − 2 + g n − k − 2 wk −1 )D n −3
M
+ (g 0 w0 )D 0 Kata kode keluaran adalah : q
xq = ∑ wi g q −i i =0
dimana perhitungan dan rangkaian berikut ini secara konsep dapat digunakan untuk menggambarkan perkalian x(D ) = w(D )g (D ) q = 0 → x0 = w0 g 0 q = 1 → x1 = w0 g1 + w1 g 0 q = 2 → x2 = w0 g 2 + w1 g1 + w2 g 0 q = 3 → x3 = w0 g 3 + w1 g 2 + w2 g1 + w3 g 0 q = 4 → x4 = w0 g 4 + w1 g 3 + w2 g 2 + w3 g1 + w4 g 0
Untuk menghitung persamaan diatas dapat dilakukan dengan menggunakan rangkaian logika berikut :
Keluaran x0 , x1 , L, xn −2 , xn−1 Σ
X
g n−k
1
Masukan w0 , w1 , L , wk − 2 , wk −1
X
Σ
g n−k −1
2
X
Σ
g n−k −2
3
X
Σ
g n−k −3
X n-k
g0
23
Cara kerjanya :
•
Koefisien-koefisien w(D ) adalah masukan pertama pada saat awal dengan wk −1
•
Keluaran pertama adalah xn −1 = wk −1 g n − k
•
Register geser (shift-register) selanjutnya dikunci sekali sehingga wk −1 disimpan di register 1 Keluaran xn − 2 = wk − 2 g n − k ⊕ wk −1 g n − k −1 Register geser totak dikunci sebanyak (n − 1) kali , untuk menghasilkan semua koefisien daripada x(D ) Setelah koefisien masukan yang ke-k , maka bit-bit 0 adalah masukan ke register geser ; cara ini akan sangat menyederhanakan pengenkodea kode-kode siklis Selanjutnya perhatikan hasil-bagi daripada x (D ) − g (D ) Sebagai misal x(D ) = 1 + D + D 2 + D 4 + D 5 ; g (D ) = 1 + D + D 3 , maka :
• • • • •
D 2 + D + 1 → Hasil bagi D3 + D + 1 D5 + D4 + D2 + D +1 5 3 D + D + D2 D4 + D3 + D +1 4 2 D + D +D D3 + D2 + 1 D3 + D +1 D 2 + D → Sisa
• •
Perlu untuk diperhatikan bahwa hampir dalam semua kasus , hasil bagi polynomial menghasilkan sisa Sisa hasil bagi ini ditulis dengan : Rg ( D ) [x(D )] = ρ (D )
SIFAT-SIFAT KODE SIKLIS •
Untuk setiap kode siklis (n, k ) , semua vektor kode ( deret ukur kode = codepolynomial ) dapat dinyatakan sebagai : o Hasil kali dari suatu deret generator g (D ) , yang mempunyai derajat q = n − k dengan deret berita w(D ) yang mempunyai derajat k − 1 o Hasilkali x(D ) = w(D )g (D ) mempunyai derajat (k − 1) + (n − k ) = n − 1 o Karena setiap berita terdiri atas k buah bit , maka akan terdapat 2k buah kemungkinan berita , sehingga akan terjadi 2k buah deret ukur yang berbeda w(D ) = w0 + w1 D + w2 D 2 + LL + wk −1D k −1 , sesuai dengan semua bilangan biner yang mungkin terjadi untuk mengisi nilai koefisien w j o Terdapat 2k buah katakode yang munkin terjadi
24
•
Kata kode untuk suatu kode siklis biner dapat mudah dihasilkan dengan menggunakan rangkaian sebagai berikut : Keluaran x0 , x1 , L, xn −2 , xn−1 Σ
X
g n−k
Σ
X
g n−k −1
Σ
g n−k −2
X
2
1
X
Σ
g n−k −3
X
g0
n-k
3
Masukan w0 , w1 , L , wk − 2 , wk −1
•
•
•
Beberapa sifat penting daripada deret generator adalah sebagai berikut : o Deret generator untuk setiap kode siklis adalah suatu faktor daripada D n + 1 o Karena itu akan tidak terdapat sisa jika dilakukan proses pembagian yang panjang daripada D n + 1 oleh g (D ) o Setiap deret berderajat n − k , yang mana adalah sebuah faktor daripada D n + 1 , adalah generator polynomial untuk suatu kode siklis (n, k ) o Derajat dari deret generator selalu n − k o Pergeseran siklis ke-q daripada suatu katakode , adalah sisa daripada hasilbagi D q x(D ) oleh D n + 1 Deret generator g (D ) = g 0 + g1D + L + g n − k D n − k untuk kode siklis , adalah matrix generator k x n sebagai berikut : 0 0 L 0 ⎤ ⎡ g 0 g1 L L g n − k ⎢0 g g L g 0 L 0 ⎥⎥ gn−k 0 1 n − k −1 ⎢ o G = ⎢ 0 0 g 0 g1 L g n − k −1 g n − k L 0 ⎥ ⎥ ⎢ M M M M M M M M ⎥ ⎢M ⎢⎣ 0 0 0 0 0 g0 g1 L g n − k ⎥⎦ Matrix uji paritas untuk kode siklis adalah : 0 L 0⎤ ⎡hk hk −1 L L h0 0 ⎢0 h hk −1 L h1 h0 0 L 0 ⎥⎥ k ⎢ o H = ⎢0 0 hk hk −1 L h1 0 L 0⎥ ⎥ ⎢ M M M M M M M M⎥ ⎢M ⎢⎣ 0 0 0 0 0 hk hk −1 L h0 ⎥⎦ Dimana h(D ) = h0 + h1D + L + hk D k , adalah hasil pembagian daripada D n + 1
oleh g (D ) o tidak terdapat sisa jika dilakukan proses pembagian yang panjang daripada D n + 1 oleh g (D ) (sesuai dengan sifat 2 ) 2k + 2 ⎡ hk ⎢0 ⎢ H =⎢0 ⎢ ⎢M ⎢⎣ 0
hk −1
L
L
0
0
hk
hk −1
0
hk
L h1 h0 hk −1 L h1
0
M 0
M 0
M 0
h0
M 0
M hk
0 M hk −1
0⎤ L 0 ⎥⎥ L 0⎥ ⎥ M M⎥ L h0 ⎥⎦ L
k +1
25
2q ⎡g0 ⎢0 ⎢ G=⎢0 ⎢ ⎢M ⎢⎣ 0
•
• • • • • •
• •
g1 g0 0
L L g n−k g1 L g n − k −1 g 0 g1 L
0 ⎤ 0 ⎥⎥ L 0 ⎥ ⎥ M M ⎥ L g n − k ⎥⎦
0
0
L
g n−k
0
L
g n − k −1
g n−k
M
M
M
M
M
M
0
0
0
0
g0
g1
q
x(D ) = 1 + D + D 2 + D 4 + D 5 dibagi g (D ) = 1 + D + D 3
Kode-Kode Hamming Kode-kode Hamming adalah sekelompok kode yang ditemukan oleh R. W. Hamming (1950) kode-kode Hamming ini semuanya mempunyai jarak minimum 3 , yang dapat : o mengoreksi sebuah kesalahan tunggal (t = 1) didalam suatu kelompok n o mendeteksi semua kesalahan ganda Kode-kode Hamming adalah kode-kode sistematis siklis linier Kode-kode Hamming dengan n = 2 j − 1 dan k = n − j akan ada jika interger j ≥ 3 k Nilai kode atau Efisiensi kode = R = n Tabel nilai kode atau efisienssi kode R j k 3 4 4 11 5 26 6 57 7 120 8 247
2 j −1− j = 2 j −1 : n R = k /n 7 57 % 15 73 % 31 84 % 63 90 % 127 94 % 255 97 %
9 502 511 98 % 10 1013 1023 99 % Kode-kode Hamming selalu ditentukan oleh matrix uji paritas H , yang banyak kolomnya = n − k = j dan banyak barisnya = n Kolom-kolom tersebut terdiri atas semua vektor komponen - j yang bukan nol
26
•
Contoh : o Matrix uji paritas untuk kode Hamming (7,4) adalah : ⎡1 0 0 1 0 1 1 ⎤ H = ⎢⎢0 1 0 1 1 1 0⎥⎥ ⎢⎣0 0 1 0 1 1 0⎥⎦
o Matrix generator untuk kode-kode Hamming diperoleh dengan menggunakan hubungan : x m = [x m, 0 x m,1 L x m,n − k −1 wm, 0 wm ,1 L wm ,k −1 ]
x m = [wm , 0
•
• • • •
wm ,1
L
g 0,n − k −1
L
g1,n − k −1
L M
g 2,n − k −1 M
L g k −1,n − k −1
wm ,n −1 ] [G ]
1 0 0 L 0⎤ 0 1 0 L 0⎥⎥ 0 0 1 L 0⎥ ⎥ M M M M M⎥ 0 0 0 L 1⎥⎦
asalkan kode-kodenya linier sistematis Generator polynomial g (D ) adalah : o Anggota dari kelas polynomials tertentu yang disebut dengan polynomials primitip o Tabel singkat daripada polynomial primitip yang dapat digunakan sebagai generator bagi kode-kode Hamming , sampai dengaan panjang = k n = 2 − 1 adalah sebagai beri-kut : j 3 4 5 6 7 8 9 10 11
•
g 0,1 ⎡ g 0,0 ⎢ g g 1,1 ⎢ 1, 0 g 2,1 L wm ,n −1 ] ⎢ g 2, 0 ⎢ M ⎢ M ⎢ g k −1,0 g k −1,1 ⎣ x m = [wm, 0 wm ,1 L
1 1 1 1 1 1 1 1 1
+ + + + + + + + +
D + D2 D + D4 D + D5 D + D6 D3 + D7 D2 + D3 + D4 +D8 D4 + D9 D3 + D10 D2 + D11
j 14 15 16 17 18 19 20 21 22
1+ D14 1+ 1+ D16 1+ 1+ 1+ 1+
D + D6 + D10 + D + D15 D + D3 + D12 + D3 D7 D2 D3
+ + + +
D17 D18 D3 + D4 +D8 D20
Pengenkodean Kode-kode Hamming
Enkoder yang digunakan bagi kode-kode Hamming terdiri dari berbagai bentuk : o Jika kecepatan pengenkodean tidak kritis , maka : Enkoder dapat diimplementasikan / dilakukan dalam software , dengan jalan menghitung perkalian ma-trix generator secaaara langsung o Jika kecepatan pengenkodean kritis , biasanya diguna-kan implementasi yang lain Gambar berikut ini melukiskan implementasi secara langsung bagi suatu enkoder Hamming , yang dapat dibuat dengan memakai rangkaian logika berkecepatan tinggi Register geser (k − 1)bits dipuncak gambar menerima bit-bit in-formasi dari sumber data Setelah register masukan terisi , maka keluaran modulo-2 adders adalah simbol-simbol kata kode yang benar
27
• • •
• • • • • • •
• • •
•
•
Setiap simbol adalah suatu “penjumlahan modulo-2” daripada bit-bit informasi tertentu , yang ditentukan oleh matrix gene-rator Generator matrix dapat diperoleh daari generator polynomial , dengan cara sebagai berikut :
Biasanya, banyaknya bit uji paritas < banyaknya bit kharakter, agar efisiensi kode > 50 % Dengan demikian daya yang digunakan untuk pengiriman kode sebagian besar digunakan untuk keperluan pengiriman kode kharatter. Bit uji paritas tersebut isinya tergantung pada kode kharakter Tiap-tiap kharakter mempunyai bit-bit penguji sendiri-sendiri Banyaknya bit uji paritas tersebut paling sedikit sebanyak 3 bit Banyaknya perbedaan bit tersebut disebut dengan jarak Hamming (Hamming distance) Jadi untuk kode ( 7,4 ), dimana : o banyaknya bit seluruhnya = n = 7 o banyaknya bit untuk kharakter = k = 4 o banyaknya bit uji paritas adalah = q = n − k = 3 o karena itu untuk kode ( 7 , 4 ), jarak Hammingnya adalah = k − q = 4 − 3 = 1 Kode yang mengikuti aturan ini disebut dengan kode Hamming Syndrome s pada kode belitan (convolution code) terdiri atas q bit Sebagai contoh jika : o banyaknya bit keseluruhan = n = 7 o banyaknya bit uji paritas = q = 4 o maka banyknya bit kharakter = k = n − q = 7 − 4 = 3 . Jika tanpa kesalahan penerimaan bit, maka : o syndrome nya adalah = s = 000 o Jika syndromnya = s = 001 → maka terjadi kesalahan pada bit ke-1 (dari yang paling kiri atau LSB) o Oleh karena itu diperlukan petunjuk (n + 1) buah kesalahan (dibuktikan pada contoh dihalaman berikutnya) o Apa yang ditunjukan pada contoh itu adalah tentang kode yang : “tanpa kesalahan” (no error) satu kesalahan pada setiap digit dari kata kode lebih dari satu kesalahan pada setiap digit dari kata kode , sampai dengan seluruh digit kata kode salah q adanya 2 buah kemungkinan syndrom yang berlain-an Sebagai contoh, untuk menjelaskan pernyataan diatas , diam-bil : o
suatu kode yang banyaknya bit keseluruhan
= n = k + q = 3+ 4 = 7
o
Untuk kode kharakter 000 : 1. Jika tanpa kesalahan penerimaan, syndrome-nya = s = 000 2. Jika terjadi kesalahan pada bit pertama (LSB) → s = 001 3. Jika terjadi kesalahan pada bit kedua → s = 010 4. Jika terjadi kesalahan pada bit ketiga → s = 100 5. Jika terjadi kesalahan pada bit pertama dan kedua → s = 011 6. Jika terjadi kesalahan pada bit pertama dan ketiga → s = 101
28
• • • •
• •
• • •
Banyaknya bit kharakter = k = 3 Semua kharakter yang mungkin terjadi = 2k = 23 =8, yaitu : o 000, 001, 010, 011, 100, 101, 110, 111 Maka pada kode Hamming ini : banyaknya bit uji paritas dan bit berita adalah sesuai dengan hubungan berikut : 2q = n + 1 q = log 2 (n + 1) dimana q = banyaknya bit uji paritas ; n = banyaknya bit keseluruhan untuk kata kode 1 k n−q q Efisiensi kode = R = = = 1 − = 1 − log 2 (n + 1) n n n n Jika nilai n semakin besar, maka effisiensi kode akan semakin tinggi sebagaimana contoh berikut : 2 n = 3 ; q = 2 → R = 1 − = 33.33 % 3 3 4 n = 7 ; q = 3 → R = 1 − = = 57.14 % 7 7 4 11 n = 15 ; q = 4 → R = 1 − = = 76.66 % 15 15 Matrix uji paritas dapat dibentuk dengan lebih mudah Dengan hanya 1 kesalahan digit, misalkan digit yang ke-j, maka syndrome s = kolom ke-j matrix H Untuk kata kode Hamming ( 7, 4 ), maka sebagai contoh matrix uji paritas = H adalah : ⎡0 H = ⎢⎢ 0 ⎢⎣ 1
•
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1⎤ 1 ⎥⎥ 1 ⎥⎦
Banyaknya baris = q = 7 – 4 = 3
Banyaknya kolom = n = 7 Dibandingkan dengan matrix uji paritas pada kode blok sebelumnya, dapat dilihat bahwa o kode Hamming ini bukan kode yang sistematis o Hal ini disebabkan bahwa posisi-posisi digit uji paritas harus sesuai dengan kolom-kolom H yang hanya mempu-nyai sebuah digit 1
29
•
dalam hal ini, jika dilihat dari matrix H diatas , maka kolom-kolom yang memenuhi syarat adalah kolom ke-1 dan kolom ke-2 saja Untuk lebih jelas, perhatikan kata kode ( 7, 4 ) berbentuk sebagai berikut :
x = [c1 •
c2
m1
c3
m2
m3
m4 ] T
Digit-digit paritasnya adalah sesuai dengan persamaan beikut :
c1 = m 1 ⊕ m 2 ⊕ m 4
c2 = m1 ⊕ m 3 ⊕ m 4 c3 = m 2 ⊕ m 3 ⊕ m 4 •
Contoh : Untuk kata kode dengan :
m1 = 0 ; m 2 = 1 ; m 3 = 1 ; m 4 = 1
c 1 = 0 ⊕ 1 ⊕ 1 = 10 → diambil
= 0
c 2 = 0 ⊕ 1 ⊕ 1 = 10 → diambil
= 0
c 3 = 1 ⊕ 1 ⊕ 1 = 11 → diambil •
• •
Maka kata kode tersebut adalah :
x = [c1
c2
= [0
0
m1 c3 0
1
m2
m3
m4 ] T
1
1
1] T
Perhatikan, bahwa kata-kode ini sama dengan baris pertama dari matrik H diatas tadi Selanjutnya dibuat tabel kode Hamming sebagai berikut : o Jika n = 7, maka banyaknya kode blok yang mungkin terjadi adalah 27 = 128 buah o Jika banyaknya bit untuk sebua berita adalah k = 4, maka hanya 24 = 16 buah kode blok yang digunakan untuk mewakili seluruh berita yang mungkin terjadi o Tabel untuk kode blok adalah sebagai berikut Nomor Kode Kata Kode Berita Berita 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
•
=1
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0000000 1010001 1110010 0100011 0110100 1100101 1000110 0010111 1101000 0111001 0011010 1001011 1011100 0001101 0101110 1111111
Jika penulisan kode berita dilakukan secara pembacaan terbalik, artinya jika kode untuk menyatakan nilai suatu level amplitudo, misalnya amplitudo yang terdiri atas 4
30
level, yang biasanya bilangan binernya adalah 0100 dibalik penulisannya menjadi dari arah sebelah kanan sehingga menjadi 0010 , ma-ka : o tabelnya akan berubah menjadi tabel kode Hamming berikut ini : No 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Berita 0000 1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
Kata kode 0000000 1101000 0110100 1011100 1110010 0011010 1000110 0101110 1010001 0111001 1100101 0001101 0100011 1001011 0010111 1111111
Jika kata kode untuk berita nomor 2 yaitu 0110100 dikirimkan dan kesalahan terjadi pada posisi 1, 2 dan 4, maka : • signal yang salah tersebut adalah :“1011100” , yang mana berarti sama dengan kata kode untuk berita nomor 3 • Karena itu detektor akan menganggap berita nomor 2 sebagai berita nomor 3 • Jadi dengan terjadinya 3 kesalahan, maka detektor tidak dapat mendeteksi kesalahan tersebut • Jika kesalahan lebih dari 3 bit, maka hanya akan dapat mende-teksi kesalahan jika kata kode yang diterima (atau vetor yang diterima) tidak sama dengan kata kode yang ditunjukkan pada table • Banyaknya perbedaan diantara sepasang kata kode yang berturutan, misalnya xm dan xm’ , adalah sesuatu yang benar-benar penting dan disebut dengan : o jarak Hamming ( Hamming –distance ) • Simbolnya adalah dH atau dH ( xm , xm’ ) Berdasarkan tabel kata kode yang terdapat pada halaman sebelum-nya, maka dapat dilihat bahwa setiap kata kode yang digunakan un-tuk menyatakan sebuah berita, maka : • Setiap kata kode yang berturutan nilainya berbeda 3 posisi • Berita berbeda dapat mempunyai bit uji paritas yang sama • Bit uji paritas ditulis mendahului bit data • Dengan demikian 1 atau 2 kesalahan transmisi tidak akan dapat mengubah suatu kata kode menjadi kata kode yang lain • Karena itu dekodernya akan dapat memberitahukan kepada pengguna bahwa telah terjadi kesalahan transmisi (meskipun tidak dapat mengoreksi kesalahan tersebut • Namun jika terjadi 3 kesalahan transmisi maka akan dapat mengubah kata kode yang dipan-carkan menjadi sebuah blok yang sama dengan kata kode yang memenuhi syarat • Karena itu dekodernya tidak akan dapat mendekti dan mengo-reksi kesalahan. Tabel tertentu yang dibuat sebagai contoh tersebut adalah termasuk kelompok kode Hamming
31
• • •
Pada tabel tersebut terdapat 3 buah jarak Hamming minimum Ketiga jarak Hamming minimum tersebut dapat digunakan untuk mengoreksi sebuah kesalahan transmisi tunggal didalam setiap blok kata kode yang dipancarkan Hasil penjumlahan kedua kata kode yang berturutan ini dinamakan dengan jarak Hamming. Jadi : Kata kode nomor 2 = x2 = 0110100 Kata kode nomor 3 = x3 = 1011100 + Jarak Hamming = dH = 1101000 Bobot Hamming (Hamming-weight) = banyaknya angka 1 pada setiap kata kode
Contoh : Kode Hamming ( 7,4 ) sebagaimana diberikan pada tabel kode Hamming diatas, misalkan mempunyai keluaran kanal simetrik biner seperti yang dituliskan berikut ini : y = 1011010 Detektor menghitung jarak-jarak Hamming antara y dan semua kata kode yang mungkin terjadi xm . Keluaran dekoder mengistimasikan x& adalah x m yang mempunyai jarak minimum dari y. Dari tabel kode Hamming, kata kode nomor lima adalah : x5 = 0011010. Jarak Hamming antara y dan x5 adalah pertambahan modulo-2 antara y dengan kata kode x5, yaitu 1011010 + 0011010 = 1000000. Bobot Hamming-nya = 1 = jarak Hamming minimum. Jadi jarak Hamming minimum antara y dan xm akan terjadi antara y dengan kode berita untuk x5 = 0011010 .
Probabilitas Kesalahan Blok Probabilitas kesalahan blok = PB daripada kode-kode yang dapat mengoreksi kesalahan tunggal adalah : • Probabilitas dua atau lebih kesalahan terjadi selama transmisi 2 j −1
PB = 1 − (1 − p ) − ∑ p (1 − p ) n−1 n
•
Probabilitas kesalahan Blok =
•
Terdapat sebuah “pattern kesalahan” tunggal , dengan tanpa kesalahan , yang mana terjadi dengan probabilitas = p(1 − p ) n Terdapat 2 j − 1 pattern kesalahan dengan sebuah kesalahan tu-nggal , yang mana terjadi dengan probabilitas = p(1 − p ) n −1 Berikut ini gambar yang melukiskan probabilitas kesalahan blok PB sebagai fungsi daripada p = probabilitas daripada fungsi pin-dah silang (crossover) BSC (Binary Symetric Code) , untuk kode-kode Hamming , berdasarkan tabel berikut :
• •
•
j =1
Vektor Kesalahan
32
Jika kata kode xm ditransmisikan menggunakan Kode Simetrik Biner ( BSC = Binary Symmetric Code ) , maka selama transmisi kesalahan dapat terjadi. Vektor kesalahannya dapat ditulis sebagai e = e0 e1 e2 ⋅ ⋅ ⋅ ⋅ ⋅ en −1 Jika salah satu atau lebih dari nilai vektor tersebut adalah “1”, maka telah terjadi kesalahan transmisi diposisi bit tersebut. Contoh : Vektor kata kode → xm = 0 1 1 0 1 0 0 Vektor kesalahan
→ e =1 1 0 1 0 0 0
Vektor yang diterima → y = 1 0 1 1 1 0 0 Jika kanal dianggap tak bermemory, maka probabilitas terjadinya kesalahan pada setiap simbol tertentu adalah tak tergantung pada semua simbol yang lainnya. Jadi pada kode simetrik biner, probabilitas-probabilitas transisi ( transition probabilities BSC ) adalah konstan untuk seluruh transmisi. Maka :
Pr [ y x] = Π Pr ( y n ' x n ' ) n −1 n'
Untuk BSC, Pr(1 0) = Pr(0 1) = p → Pr(0 0) = Pr(1 1) = 1 − p Dengan demikian probabilitas bahwa BSC menyebabkan terjadinya vektor kesalahan : e = 1101000 adalah : P [e = 1101000] = p x p x (1 − p ) x p x (1 − p ) x (1 − p ) x (1 − p) Secara umum, probabilitas bahwa BSC menyebabkan kesalahan-kesalahan kanal e’ pada posisi tertentu didalam blok kata kode yang panjangnya n adalah : ⎡ kesalahan e' pada ⎤ Pr ⎢⎢lokasi − lokasi tertentu ⎥⎥ = p e ' (1 − p ) n −e ' ⎣⎢ dalam kata kode ⎦⎥ Hasil diatas tersebut digunakan untuk mencari Pr[ y x m ], yaitu Probabilitas y = signal tertentu yang diterima jika signal yang dikirim adalah xm . Rumus lainnya yang dapat digunakanadalah :
Pr[ y x m ] = p d H (1 − p ) d H Pada kode Hamming ini untuk memeriksa kesalahan kode dilakukan secara kontinyu, dengan cara yang dikenal dengan nama pembelitan atau konvolusi (convolution). Untuk menggambarkan kode Hamming ini secara lebih jelas, dimisalkan setiap kharakter yang dibuat menjadi kode terdiri atas k buah bit, dan disebut dengan kode asli. Setelah masing-masing kharakter diberi bit-bit penguji-nya masing-masing, jumlah bit untuk menggambarkan setiap kharakter menjadi n buah bit. Jadi banyaknya bit penguji adalah sebanyak m = (n-k) buah bit. k Maka Efisiensi kode = η = 100% . n Kelompok kode yang termasuk dalam kode Hamming ini dapat ditulis sebagai berikut : (n, k ) = {(2 m − 1) , (2 m − 1 − m ) } dimana : n = jumlah bit total untuk menyatakan kharakter m = banyaknya bit penguji k = banyaknya bit asli Jadi jika banyaknya bit penguji m = 4 , maka :
33
kode seluruhnya adalah n = 2 4 − 1 = 15 dengan jumlah bit penguji sebanyak k = 2 m − 1 − m = 2 4 − 1 − 4 = 11 bit Dengan demikian kode aslinya adalah : (n, k ) = (15,11) Jika m = 3 bit, maka n = 23 − 1 = 7 dan m = 23 − 1 − 3 = 4 ; kodenya = Contoh kode (7,4) adalah :
1 0 0 1 0 0 1 k • • •
m
n Kode asli tersebut secara seri digeser melalui register geser sehingga pada setiap penggeseran akan menghasilkan kode yang terdiri atas n buah bit Hal ini dapat dicapai dengan jalan membuat rangkaian tertentu yang dapat memenuhi kebutuhan yang diinginkan Teknik yang diterapkan untuk mencapai keinginan itu adalah dengan menggunakan rangkaian sebagai berikut :
Coding untuk Kanal Simetrik Biner (BSC =Binary Symetric Channel) Shanon telah mendemonstrasikan jika kapasitas kanal transmisi melebihi banyaknya bit per detik yang melewatinya, maka : dimungkinkan diperoleh transmisi bit-bit tanpa kesalahan Jadi jika C = kapasitas kanal transmisi ; R = banyak bit yang dikirimkan per detik. Maka jika C ≥ R akan dimungkinkan transmisi bit-bit tanpa kesalahan
Dasar-dasar Teori Informasi Sebelumnya sudah dibahas bahwa : • signal yang mengandung informasi yang dibangkitkan di pemancar tidak dapat diterjemahkan secara benar di penerima . sebagai akibat : • adanya signal yang mengalami cacat di kanal antara pemancar dan penerima • Cacat ini menyebabkan matched filter detector di penerima membuat kesalahan • Disain sistem komunikasi yang baik akan dapat : • meminimalkan kemungkinan matched filter tersebut membuat kesalahan dengan cara : • melebarkan lebarpita
34
• menambah daya pancar • sekali gus mempertahankan beaya pembutan sistem yang layak. Hal ini memang membuat disain menjadi lebih ruwet. Studi teori informasi menunjukkan bahwa terdapat batas-batas teori fundamentil yang ada hubungannya dengan : • probabilitas kesalahan • daya pemancar • interferensi • lebarpita signal • keruwetan sistem Hubungan ini digunakan untuk : • menelaah kelayakan kinerja probabilitas kesalahan sistem yang telah dibahas secara mendalam, dengan memakai sumber daya yang tersedia • mendapatkan wawasan tentang teknik yang digunakan bagi pencapaian kinerja yang dinginkan tersebut. Bidang teori informasi dimulai dengan karya Shanon, diakhir tahun 1940. Sejak saat itu banyak ahli riset telah mengembangkannya dan telah berhasil mendapatkan teknik yang terperinci untuk merancaang efisiensi komunikasi. Keseluruhan daripada bidang pengontrolan kesalahan tersebut harus dibahas secara mendalam, untuk : • dapat melakukan pengembangan teknik-teknik yang diperlukan bagi tercapainya kinerja yang diharapkan
• terwujudnya apa yang telah dibuktikan oleh Shanon Pada bab ini sejumlah teknik pengontrolan kesalahan yang paling penting akan dibahas. Dari studi yang sangat mendalam , maka akan dapat diperlihatkan tentang : • pengertian bagaimana kinerja sistem komunikasi mungkin akan menghadapi berbagai hambatan (constraints) tambahan • Studi tentang berbagai teknik pengontrolan kesalahan akan dapat memberi pengertian tentang : o prinsip pengontrolan kesalahan o teknik-teknik tentang bagaimana caranya mencapai kinerja sistem komunikasi yang diinginkan tersebut • Teknik pengontrolan kesalahan yang dibahas akan mencakup tentang : o pengkodean signal yang merupakan salah satu yang diperlukan pada sistem komunikasi digital , agar diperoleh : kode yang dapat melakukan self correction jika mengalami kesalahan didalam urutan bit-bit , misalnya : • kode blok • kode konvolusi • automatic repeat request system dengan menggunakan deteksi kesalahan. Jenis interferensi oleh noise yang dibahas , adalah : • yang terkait dengan pengontrolan kesalahan • dibatasi hanya pada interferensi noise Gaussian saja.
35
KONSEP DASAR TEORI INFORMASI Studi tentang teori informasi secara klasik dibagi menjadi : • studi tentang koding sumber informasi • studi tentang koding kanal Dari gambar mode sistem komunikasi sebelumnya , terlihat bahwa keluaran dari sumber informasi adalah masukan ke enkoder sumber, yang mana fungsinya adalah : • memperkecil banyaknya bit data rata-rata pada setiap waktu tertentu, yang harus dipancarkan ke pengguna informasi melalui kanal • membuat banyaknya bit data rata-rata tersebut adalah seminimum
mungkin. Jika koding sumber informasi bukan menjadi pokok pengamatan, maka : - akan menjadi mudah untuk mengelompokkan enkoder sumber informasi dengan sumber informasi itu sendiri - mengamati hasil dari sumber informasi - Keluaran sumber informasi adalah masukan ke enkoder kanal - Fungsi dari enkoder kanal, yang mana fungsinya dapat disingkat dengan melakukan koding , adalah yang menjadi pokok dari kebanyakan pembahasan tentang teori informasi ini.
KODING ( PENYANDIAN ) SUMBER INFORMASI Ada banyak kemungkinan sumber informasi yang akan dikirimkan, yang : • rentangnya mulai dari halaman-halaman ketikan sampai dengan bayanganbayangan atau gambar-gambar video • suara analog yang didigitalkan sampai dengan kandungan biner di memory komputer. Semua sumber informasi analog dianggap harus diubah menjadi urutan waktu diskrit, dengan : - simbol-simbol diskrit wi , dari suatu abjad adalah : W = {0, 1, 2,⋅ ⋅ ⋅ ⋅ ⋅, q w − 1} ; banyaknya simbol = w buah - prosesnya adalah dengan pen ”sampling”an dan pencapaian perubahan dari analog ke digital - didalam setiap interval waktu T , wi dapat bernilai salah satu dari qw buah simbol yang berbeda-beda - nilai-nilai tersebut adalah mulai dari 0, 1, 2, ⋅ ⋅ ⋅ ⋅⋅, q w − 1
36
•
Setiap simbol adalah : o salah satu dari keluaran dari sumber informasi yang terjadi pada setiap waktu Tw detik (disini w menunjukkan berita). • Simbol-simbol itu tidak lebih dahulu dianggap sebagai keluaran dengan probabilitas yang sama Probabilitas keluaran sumber informasi adalah : • sebuah simbol w1 = j j, yaitu Qw(j), dimana j = 0,1,2,…..,qw-1 • Simbol-simbol dianggap bebas satu sama lain • setiap simbol keluaran dari sumber informasi , dengan simbol yang berikutnya, dinyatakan dengan index waktu yang berbeda sehingga simbolnya juga berbeda-beda Jika qw= banyaknya abjad , maka setiap simbol terdiri atas log2 qw digit biner. Contoh : qw = 256 = 28 Setiap simbol terdiri atas log2 28 = 8 buah digit biner Kecepatan bit sumber informasi per detik = banyaknya bit per detik : Rm =
•
1 log 2 qw bps Tm
dimana : Tm = waktu yang diperlukan untuk menyatakan sebuah simbol bit Banyaknya bit per simbol = Rm ' = log 2 qw simbol Meskipun urutan keluaran sumber informasi dapat dinyatakan dengan suatu arus bit (bit stream) yang mempunyai kecepatan Rm bps, namun biasanya : o dimungkinkan untuk menyatakan urutan dengan menggunakan arus bit dengan kecepatan yang lebih rendah o Kecepatan bit terendah yang mungkin adalah sama dengan kandungan informasi rata-rata dari urutan simbol o Kandungan informasi pada setiap simbol , yang berarti banyaknya bit setiap simbol, adalah :
I ( j ) = − log 2 Pw ( j ) ;
j = 0, 1, 2,........., qw − 1
yang mana adalah : fungsi probabilitas kejadian simbol tersebut • Rumus tersebut memperlihatkan bahwa : o kejadian keluarnya event dari sample yang ada adalah : lebih sering tidak sama besarnya dibandingkan dengan kejadian keluaran event yang sama pada bidang komunikasi ini Dengan kata lain random events outcome lebih sering terjadi dibanding dengan equally likely events outcome. • Probabilitas keluaran yang kecil akan menghasilkan kandungan
informasi yang tinggi • •
Jika banyaknya abjad hanya 1, maka simbolnya hanya terdiri atas 1 bit sehingga probabilitas keluarnya simbol tersebut adalah Pw( j ) =1 Akibatnya kandungan informasinya = 0, atau tanpa kandungan informasi apapun juga
37
•
Kandungan informasi rata-rata dari sumber berita disebut dengan :
Entropy yang satuannya adalah :
bits simbol
Entropy Intisari dari teori komunikasi adalah tentang : • ukuran informasi • Yang dimaksudkan dengan informasi didalam teori komunikasi ini adalah : o segala sesuatu yang dihasilkan oleh sumber berita untuk ditransfer ke pengguna yang memerlukannya • Jika isi informasi yang ditransfer ke pengguna tersebut , mempunyai : o kemungkinan yang kecil untuk diketahui lebih dahulu oleh pengguna, maka : nilai informasinya tinggi o Sebaliknya : o jika kemungkinannya besar, maka nilai informasinya rendah. Sebagai contoh jika seseorang berpapasan dengan temannya, lalu bertanya : • “kemana kamu hendak pergi” • jika dijawab : o ”saya mau kedepan “, maka : nilai informasi yang didapat oleh penanya adalah rendah sekali, sebab sipenanya hampir sudah pasti tahu bahwa kemungkinan temannya berjalan menuju kearah depan Namun jika temannya yang ditanya tadi menjawab : “saya mau ke stasiun bis”, maka nilai informasi yang diperoleh penanya adalah tinggi, sebab kemungkinan bahwa yang ditanya akan menuju ke stasiun bis hanya merupakan sebagian kecil dari kemungkinan-kemungkinan lain yang bisa kerjadi. Nilai informasi disebut juga dengan entropy. Simbol untuk intropy adalah H(X). Rumusnya adalah sebagai berikut : Probabilitas isi informasi diketahui lebih dahulu oleh pengguna
informasi = P ( xi ) =
1 untuk semua i. n Maka entropynya adalah : n
n
n 1 1 1 H ( X ) = −∑ P ( xi )log P ( xi ) = −∑ log = −∑ (− log n ) n i =1 i =1 n i =1 n n
1 = ∑ log n i =1 n Informasi yang terkandung dalam sebuah gambar
Sering dikatakan bahwa sebuah gambar lebih bermakna daripada ribuan kata. Suatu gambar dapat diuraikan dalam sejumlah titik dis-krit atau elemen, dimana masing-masing elemen
38
tersebut mempu-nyai level “kecerahan” (brightness) yang rentang-warnanya mulai dari warna hitam sampai ke warna putih. Sebagai contoh sebuah gambar pada televisi baku, mempunyai elemen kecerahan sebanyak 500 x 600 = 3 x 10 5 buah dan 8 buah level yang dengan mudah dapat dibedakan. 3 x105
buah elemen gambar yang mungkin terjadi, dengan masingDengan demikian terdapat 8 5 nasing gambar mempunyai kemungkinan kemunculan yang sama, yaitu 8 − 3 x10 , apabila dianggap semua kemunculan gambar berlangsung secara acak. Oleh karena itu jika semua elemen gambar yang mungkin terjadi tersebut dinyatakan dengan digit-digit biner, maka kebutuhan bit yang dapat memfasilitasi semua elemen gambar tersebut ada-lah sebesar :
ℑ = log2 83 x10 = 3x105 x3 ≅ 106 bits 5
Sebagai alternatip, dengan menganggap semua elemen gambar mempunyai kemungkinan yang sama (equally likely) untuk muncul, dengan informasi per elemen = log 8 = 3 bit, maka kebutuhan bit total untuk menyatakan seluruh elemen gambar adalah = 3 x 3 x 10 5≅ 10 6 bits. Jika dianggap bahwa suatu perbendaharaan kata (vocubolary) terdiri atas 100.000 kata dengan kemungkinan keluar yang sama, maka kemungkinan munculnya setiap kata = 10 – 5. Oleh karena itu informasi yang terkandung pada 1000 kata membutuhkan digit biner sebanyak : 5 5 3 log 10 10 ℑ = 1000 x log 2 10 = 10 = 10 3 (3.32 )(5) = 15.6 x10 3 ≅ 2 x10 6 bits log10 2 Kebutuhan bit sebesar itu akan sangat kecil dibandingkan dengan kebutuhan bit untuk seluruh elemen daripada sebuah gambar. Anggapan diatas masih dapat didiskusikan lebih lanjut.
Entropy dan Nilai Informasi Informasi sendiri (self information) didifinisikan sebagai masing-masing berita atupun masing-masing simbol daripada semua yang dihasilkan oleh suatu sumber berita. Namun elemen sendiri itu bukanlah gambaran (description) yang bermanfaat tentang apa yang dihasilkan oleh sebuah sumber berita, relatip terhadap apa dikomunikasikan. Sistem komunikasi tidaklah dirancang untuk pengiriman dan penerimaan suatu berita khusus, melainkan untuk pengiriman dan penerimaan segala berita yang mungkin terjadi. , yang berarti bahwa semua apa yang dapat dihasilkan oleh suatu sumber berita adalah sesuatu yang berbeda dengan suatu kejadian tertentu. Jadi meskipun aliran informasi sesaat dari sumber berita bisa saya sesuatu yang tidak menentu (erratic), namun harus digambarkan bahwa sumber berita tersebut mengeluarkan informasi rata-rata. Informasi rata-rata ini dinamakan entropy sumber berita. Untuk suatu sumber yang mengirimkan simbol-simbol diskrit yang secara statistik bebas satu sama lain, untuk merumuskan entropy-nya, diambil misal m = banyaknya simbol yang berbeda, misalnya simbol daripada abjad yang mana jumlah abjadnya adalah m. Jika simbol-simbol tersebut mempunyai probabilitas yang tidak sama untuk dipancarkan dari sumber, maka simbol atau abjad yang ke-j mempunyai probabilitas untuk 1 dipancarkan = Pj , maka informasi yang dibawa adalah sebanyak ℑ = log 2 bit informasi. Pj Untuk suatu berita yang panjang, N 〉〉 1 simbol, simbol ke-j mempunyai probabilitas kemunculan sebesar NPj kali , sehingga bit informasi total pada berita panjang tersebut menjadi :
39
NP1ℑ1 +NP2 ℑ2 + ⋅⋅⋅⋅ + NPmℑm =
m
∑ NP ℑ j =1
j
j
bits
Informasi rata-rata per simbol, yang didifinisikan seabagi entropy, adalah : m m 1 H (W ) = ∑ Pj ℑ j = ∑ Pj log 2 bits / simbol Pj j =1 j =1 Jadi Entropy adalah banyaknya bit yang diperlukan untuk menyatakan setip simbol. Perata-rataan diatas merupakan perata-rataan yang berpasangan (ensemble average). Jika sumber informasi tersebut tidak stasioner, maka probabilitas bisa berubah dengan waktu sehingga entropy menjadi tidak sangat penting. Jika sumber dianggap ergodic, maka perata-rataan berpasangan maupun perata-rataan waktu adalah identik. Entropy PCM
Misalkan suatu sistem PCM, dimana : • input kontinyunya = x(t) • pita frekuensinya terbatas hanya sampai dengan 50 Hz. • x(t) disample mengikuti Nyquist rate, yaitu dengan frekuensi sample = fs = 2W = 100 Hz • Jika simbol yang mungkin terjadi sebanyak 4 buah • berarti setiap sample digambarkan dengan 2 bit saja • dimana dimisalkan probabilitas munculnya simbol, secara berturut-turut adalah 0.5, 0.25, 0.125 dan 0.125. Banyaknya level kuantisasi terbanyak , yaitu banyaknya level kuatisasi yang mewakili amplitudo pulsa tersampling paling tinggi adalah m = 22 = 4. Simbol biner yang mungkin keluar dari sistem PCM tersebut adalah 0 0
01 1 0 1 1
P1 = 0.5 P2 = 0.25 P3 = 0.125 P4 = 0.125
Maka entropy-nya adalah : m
H = ∑ Pj log j =1
1 1 1 1 = P1 log 2 + P2 log 2 + P3 log 2 + P4 log 2 P4 Pj P1 P2 P3
= 0.5 log 2 2 + 0.25 log 2 4 + 0.125 log 2 8 + 0.125 log 2 8 = 0.5 x1 + 0.25 x 2 + 0.125 x3 + 0.125 x3 = 1.75 bit / simbol Dengan frekuensi sampling = fs = 100 Hz, maka periode sampling = Ts= 0.01 detik 1 Dalam 1 detik terdapat = 100 simbol yang dikirim. 0.01 Dengan entropy 1.75 bits/simbol, maka dalam 1 detik akan dikirim R = 100x1.75 = 175 bit/detk. Karena setiap simbol harus dinyatakan dengan banyak bit yang genap, maka tidak mungkin menyakan setiap simbol dengan 1,75 bits, tapi harus dibulatkan keatas menjadi 2 bits/simbol. Hal ini sesuai dengan anggapan semula. Dengan demikian setiap detik dikirimkan 200 bit.
40
Contoh : Misalkan suatu sumber informasi menghasilkan tiga buah kemung-kinan simbol, yaitu A,B atau C, dengan probabilitas 0.7, 0.2 dan 0.1, selama interval pensignalan berturut-turut. Ditanyakan : (a) carilah kandungan informasi per simbol ! (b) carilah entropy atau informasi rata-rata dari keluaran sumber ! (c) jika setiap detik dikirim 1000 simbol oleh sumber informasi , carilah kecepatan informasi rata-rata ! (d) Berapakah kecepatan informasi maximum yang mungkin ? Jawab: (a). Kandungan informasi setiap simbol : untuk simbol A, adalah : I(A) = -log2 (0.7) = 0.515 untuk simbol B, adalah : I(B) = -log2 (0.2) = 2.322 untuk simbol C, adalah : I(C ) = -log2 (0.1) = 3.322 (b). Entropy-nya dicari dengan rumus :
Semakin tinggi kemungkinannya, semakin rendah kandungan informasinya
n
H (W ) = −∑ P( x i ) log P( x i ) i =1
Jadi entropy-nya adalah :
H (W
)=
−
= − = −
{ P ( A ) log 2 P ( A ) + P (B ) log 2 P (B ) + P (C ) log 2 P (C ) } (0 . 7 ) (log 2 0 . 7 ) − (0 . 2 ) (log 2 0 . 2 ) − (0 . 1 ) (log 2 0 . 1 ) (0 . 7 x {− 0 . 515 } ) − (0 . 2 x {− 2 . 322 } ) − (0 . 1 x {− 3 . 322 } )
= 1 . 157
bit simbol
(c). Oleh karena itu jika setiap detik dikirim 1000 simbol, maka banyaknya informasi ratarata per detik adalah = 1157 bps (d). Kecepatan informasi maximum yang mungkin dan entropy sumber informasi maximum, dicapai jika simbol-simbol keluaran dari sumber informasi adalah benarbenar sama kemungkinan keluarnya (equally likely).
Rumus Rumus yang digunakan adalah Rm =
1 log 2 qw bps Tm
Karena dalam 1 detik dikirim 1000 simbol, maka waktu yang diperlukan untuk 1 simbol adalah 10-3 detik. qw = banyaknya abjad = 3 ; agar kecepatan informasinya yang mungkin terjadi maximum. maka probalitas keluarnya setiap abjad adalah sama, yaitu Jadi Rmax = 1000 log 2 3 = 1585 bps Dapat juga dicari dengan rumus :
1 3
1⎤ ⎡ 1 Rmax = 1000 x 3 ⎢− log 2 ⎥ = −1000 x(− 1.58489 ) = 1585 bps 3⎦ ⎣ 3
41
Perlu dicatat bahwa seiap simbol atau kharakter harus dinyatakan dengan bit yang banyaknya bulat, bukan pecahan. Jadi jika dalam perhitungan setiap simbol terdiri atas susunan bit sebabit nyak H(W) = 1.157 , maka dalam praktek setiap simbol harus dinyatakan dengan lebih simbol dari 2 bit. Contoh : Pada sistem komunikasi PCM, dimana inputnya adalah signal pembicaraan manusia yang lebar pita frekuensi W = 4 kHz. Fekuensi sampling = fs = 2W = 8 KHz. Setiap simbol digital dinyatakan dalam 8 bit. Probabilitas keluarnya simbol dianggap bahwa 12.5 % dari seluruh 3 simbol masing-masing adalah , 25 % dari seluruh simbol masing-masing adalah 256 2 1 dan sisanya masing-masing adalah . 256 1280 a. entropy sistem PCM – nya. b. bit-rate-nya.
Jawab: Karena setiap simbol dinyatakan dalam 8 bit, yang mungkin terjadi adalah 256. Simbol-simbol yang mungkin terjadi adalah : 0 0 0 0 0 0 0 0 0 0 0 0 M M M M 1 1 1 1 a. Entropy sistem PCM adalah :
maka m = 28 = 256. Maka banyaknya simbol
0 0 0 M 1
0 0 0 M 1
0 0 1 M 1
0 1 0 M 1
⎞ ⎛ ⎟ ⎜ 1 3 1 ⎟ H = ∑ P j log log 2 = ( 12 . 5 % x 256 ) ⎜ 3 ⎟ ⎜ Pj 256 j =1 ⎟ ⎜ 256 ⎠ ⎝ ⎞ ⎛ ⎛ ⎟ ⎜ ⎜ 1 1 1 ⎟ 2 ⎜ log 2 + ( 67 . 5 % x 256 ) ⎜ + ( 25 % x 256 ) log 2 1 2 ⎟ ⎜ 1280 ⎜ 256 ⎟ ⎜ ⎜ 1280 256 ⎠ ⎝ ⎝ m
⎞ ⎟ ⎟ ⎟ ⎟ ⎠
256 ⎞ ⎞ ⎛ 1 ⎞ ⎛ 1 ⎛ 3 log 2 log 2 128 ⎟ + 160 ⎜ log 2 1280 ⎟ H = 32 ⎜ ⎟ + 64 ⎜ 3 ⎠ ⎠ ⎝ 1280 ⎠ ⎝ 128 ⎝ 256 256 ⎞ ⎛ H = 0.375 ⎜ log 2 ⎟ + 0.5 (log 2 128 + log 1280 ) 3 ⎠ ⎝ H = 0.375 (8 − log 2 3) + 0.5 (7 + 7 − log 2 10) = 3 − 0.594 + 7 − 1.661 = 7.745 bit / simbol
42
Dengan frekuensi sampling = fs = 8 kHz, maka periode sampling = Ts= 125 μ detik 1 = 8000 simbol yang dikirim. Dalam 1 detik terdapat 125 x10− 6 Dengan entropy 7.745 bits/simbol, maka dalam 1 detik akan dikirim R = 8000x7.745 = 61960 bit/detk.
b. Bit-rate = R = 61960 bps Karena setiap simbol harus dinyatakan dengan banyak bit yang genap, maka tidak mungkin menyakan setiap simbol dengan 7,745 bit, tapi harus dibulatkan keatas menjadi 8 bits/simbol. Hal ini sesuai dengan anggapan semula. Dengan demikian setiap detik dikirimkan 8000x 8 = 64 k bit. Teori matematis tentang informasi memberikan baik batas bawah dan panjang rata-rata kode sumber informasi, yang mana panjang kode tersebut bervariasi , maupun untuk mencari kodekode yang panjang rata-ratanya dicapai atau didekati oleh batas bawah kode tersebut. Contoh sistem kode dengan panjangny bervariasi adalah sistem kode Morse, dimana abjadabjad yang paling sering dipakai , misalkan huruf hidup “ a”, “ i”, “ u”, “ e”, “ o” diberi kode yang lebih pendek, sedang kode yang jarang dipakai , misalkan huruf “ z” diberi kode yang lebih panjang. Entropy sumber informasi, yaitu H(W), adalah batas bawah atau banyak bit rata-rata terkecil yang digunakan untuk menyatakan suatu simbol atau kharakter. Salah satu metode pengkodean sumber informasi adalah kode Huffman. Prosedur pembentukan kode Huffman ini dapat dilihat dari contoh berikut ini : - misalkan suatu sumber informasi menghasilkan 3 jenis simbol, A ,B dan C - probabilitas keluarnya berturur-turut adalah : 0.70 , 0.20, 0.10. Sebelumnya sudah dihitung tentang kasus yang sama, bahwa entropy sumber informabit . sinya adalah 1.157 simbol Prosedur Huffman untuk mengkode sumber informasi tersebut menjadi kode biner dengan panjang yang bervariasi mulai dengan mendaftar simbol-simbol keluaran dari sumber informasi, sebagai gambar berikut ini : Pasangan simbol-simbol sumber informasi yang paling kecil ke-mungkinannya (yang berarti 0.20 dan 0.10), kemudian digabungkan untuk menghasilkan apa yang disebut dengan sumber informasi yang diperkecil (reduced source), yang probabilitasnya men-jadi 0.20 + 0.10 = 0.30. Probabilitas simbol-simbol gabungan adalah jumlah dari probabili-tas simbol-simbol gabungan yang dipakai untuk menghasikannya. Gabungan probabilitas tersebut misalnya : 0.20 +0.10 = 0.30 ; 0.70 + 0.30 = 1.0
] Kata-kata kode Huffman
0
Sumber Info Asli
Reduksi 1
Reduksi 2
0.70
0.70
1. 0
A
A
ABC
43
0 1 0 1
Prosedur pengkodean Huffman terhadap sumber informasi Dikolom pertama terlihat kata-kata kode Huffman yang berkaitan dengan 3 simbol A,B,C. Pada kolom kedua terlihat simbol-simbol gabungan yang dimaksudkan disertai probabilitas keluarnya simbol untuk dikrimkan ke tujuan. Langkah dikolom ke-2 ini , dapat dilihat bahwa B dan C digabung menjadi simbol BC, yang probabilitasnya menjadi = 0.20 + 0.10 =0.30. Garis-garis terlihat menghubungkan simbol-simbol asli dengan reduksi pertama. Hanya garisgaris yang menghubungkan simbol-simbol yang sedang digabung diberi label sebuah “0” dan sebuah “1”. Simbol-simbol dari sumber informasi yang tereduksi sekarang diatur lagi dengan jalan memperkecil order dari probabilitas-probabilitas yang berturutan. Sumber informasi yang tereduksi adalah simbol yang banyaknya kurang satu dibandingkan dengan sumber informasi masukannya. Reduksi terhadap sumber informasi ini berlanjut sampai tinggal satu simbol informasi gabungan tunggal saja, dimana probabilitasnya adalah 1. Keluaran kode Huffman untuk simbol-simbol informasi asli, secara sederhana adalah urutan dati “0” dan “1”, yang didapatkan dari simbol gabungan terakhir dari smibol sumber informasi asli. Sekali lagi perlu dijelaskan bahwa simbol-simbol itu diperuntukkan untuk dibuat cabangcabang , dimana simbol-simbol itu digabung. Kata-kata kode Huffman dapat dilihat pada gambar sebelumnya. Jika banyaknya kode yang mungkin keluar adalah n jenis dan panjang katakode yang ke-j dinyatakan dengan lj , dan probabilitas keluarnya simbol j tersebut adalah Pw( j ), maka panjang kode rata-rata adalah :
L=
n −1
∑l j =0
j
Pw ( j )
Pada contoh sebelumnya , n = 3 , yaitu A,B dan C , dengan kata kode A panjangnya 1 bit ; kata kode B panjangnya 2 bit ; kata kode C panjangnya 3 bit ; probabilitas masing-masing berturut-turut adalah P(A) = 0.70 ; P(B) =0.20 ; P(C ) = 0.10, maka : L=
n −1
∑l j=0
j
Pw ( j ) = l 0 Pw (0 ) + l1 Pw (1) + l 3 −1 Pw (3 − 1)
= 1 x 0 . 70 + 2 x 0 . 20 + 2 x 0 . 10 = 1 . 30 Nilai ini lebih besar dari nilai minimum yang mungkin, yaitu 1.157 (sudah dihitung sebelumnya).
44
Hasil ini jauh lebih baik dibandingkan apabila tidak digunakan koding, dimana diperlukan bit ingat : karena ada 3 buah simbol, maka diperlukan 2 bit per simbol, jika 2.00 simbol tidak dilakukan teknik pengkodean Huffman. Dasar pemikiran teori informasi adalah membuat probabilitas kesalahan berita menjadi nol., E dengan cara penambahan komplexi-tas gelombang pada b tetap. N0 Dasar pemikiran ini berlaku selama nilai transmisi informasi (banyaknya bit yang dikirimkan per satuan waktu) keseluruhan dibawah kapasitas kanal. Cara-cara yang dilakukan para teknolog informasi untuk mencapai tujuan diatas, yaitu untuk mengurangi nilai kesalahan berita, adalah dengan jalan memakai teknik-teknik tertentu, misalnya : menambah daya pemancar ataupun dengan mengurangi besarnya daya pemancar agar probabilitas kesalahan berita menjadi kecil. KODE BLOK
Suatu blok yang terdiri atas k buah bit informasi dinyatakan dalam k-vektor, sebagai : wm = wm 0 wm1 wm 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ wm (k −1) semua wmi bernilai 0 atau 1 Subcript m menyatakan berita tertentu yang sedang diperhatikan dari 2k buah berita yang mungkin terjadi jika setiap berita terdiri atas k buah bits. Jadi banyaknya kode untuk informasi atau kode untuk data yang mungkin terjadi = 2k buah. Jadi m = 1, 2, 3, ………………2k Q M(m) = probilitas berita yang keluar adalah berita ke-m. Jika berita yang keluar mempunyai kemungkinan keluar yang sama , maka QM(m) = 2-k Contoh : Jika k =3, maka berita yang mungkin keluar adalah m = 2k = 23 = 8, yaitu w0 w1 w2 w3 w4 w5 w6 w7
= = = = = = = =
000 001 010 011 100 101 110 111
Jika m = 5, maka berita yang dimaksudkan adalah wm –1 = w4 = 1 0 0 Enkoder akan memetakan setiap berita tertentu , yaitu wm (yang terdiri atas k bits) , menjadi n buah vektor biner tertentu atau berita yang terdiri atas n bits = ( k + q ) bits , yaitu : x m = x m 0 x m1 x m 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ x m (n −1) Disini yang dimaksud dengan n = jumlah bit berita ( = k bits) ditambah dengan bit paritas ( = m bits ). Pemetaan ini adalah satu berita ke satu peta, sehingga setiap berita mempunyai satu peta tersen-diri. Kode blok (n,k) adalah himpunan dari semua simbol xm ( yang banyaknya 2n buah anggota himpunan ) Dalam kode blok ini k < n, yang berarti banyaknya bit kode asli lebih kecil daripada banyak seluruh bit dari kode blok. Banyaknya bit paritas atau bit penguji = q = n – k Banyaknya berita yang mungkin terjadi = 2k
45
Banyaknya kata kode yang mungkin terjadi jika setiap berita terdiri atas n bits = 2n > 2k Maka tidak semua kata kode yang mungkin terjadi digunakan sebagai kata kode ( dari 2n buah kata kode yang mungkin terjadi hanya 2k buah saja yang digunakan sebagai kata kode ) k Efisiensi kode = Nilai kode (code-rate) = R = < 1 n
Singkatan : 1. -
2. 3.
4.
5.
Disain sistem baik harus efisien didalam hal : pemakaian sumber dayanya lebarpita frekuensinya kompak menghasilkan komunikasi informasi yang andal dari sumber informasi ke tujuan informasi o Untuk itu ukuran keandalannya adalah : besarnya probabilitas kesalahan adalah harus kecil dan dibawah nilai max yang diijinkan. Sumber koding harus : menggunakan kode redundance sekecil mungkin untuk memini-malkan penggunaan bit untuk setiap kode yang dikomunikasi-kan Hal ini berarti dapat menghemat kebutuhan akan lebarpita frekuensi. Kode kanal digunakan untuk memperbaiki sebanyak mungkIn kesalahan kode yang terjadi pada kanal tersebut, yang pada gilirannya dapat memperbaiki keandalan komunikasi. Sumber signal diskrit tanpa menggunakan memory menggambarkan informasi yang menggunakan urutan simbol-simbol bebas, wo , w1 , ….yang sesuai dengan simbol abjad W = [0,1,2,…….qw – 1 ]. Probabilitas bahwa simbol keluaran DMS adalah = j eselama interval I adalah Qw(j). Kandungan informasi suatu simbol keluaran DMS tunggal j , adalah I(j) = -log2Qw(j). Simbol-simbol keluaran DMS yang banyak kesamaannya mempunyai kandungan informasi yang kecil dibandingkan dengan simbol-simbol yang sedikit kesamaannya. Entropy sumber informasi adalah : q w −1
H (W ) = − ∑ Qw ( j ) log 2 Qw ( j ) j =0
yang mana adalah kandungan informasi rata-rata sumber. Intropy sumber adalah banyaknya bit rata-rata minimum per simbol keluaran DMS, yang harus dipancarkan lewat kanal. Jadi informasi sumber tidak dapat dikomunikasikan dengan memakai jumlah bit rata-rata per simbol DMS yang lebih sedikit jumlahnya dibandingkan dengan entropynya. 6. Prosedur Huffman adalah sesuatu yang secara intuitip memenuhi koding sumber. Prosedur ini menggunakan urutan biner yang lebih panjang terhadap simbol-simbol DMS yang rendah probabilitasnya, dibandingkan dengan simbol-simbol yang lebih tinggi probabilitasnya.Simbol-simbol DMS dapat dibuat menjadi kode Huffman sebagai simbol-simbol tunggal ataupun dalam kelompok-kelompok. Kode Huffman daripada kelompok-kelompok simbol-simbol DMS menghasilkan hasil yang terbaik. 7. Kapasitas suatu kanal, yaitu C , adalah jumlah bit per detk yang teoritis dapat dipancarkan tanpa salah. Kapasitas tersebut adalah fungsi dari lebar pita kanal dan SNR (Signal to Noise Ratio) yang diterima. Kapasitas Shannon adalah : ⎛ P ⎞ ⎟ C = B log 2 ⎜⎜1 + N o B ⎟⎠ ⎝
46
Jika kecepatan transmisi yang dinginkan adalah Rm
Penyandian Belitan (Convolution Coding) Salah satu metode untuk mengontrol kesalahan didepan (forward error control) adalah dengan menggunakan penyandian belitan. • Pada teknik penyandian ini : • simbol-simbol tidak dikelompokkan kedalam kelompok yang berbeda-beda kemudian disandi (encoded) , namun : • urutan bit-bit informasi yang kontinyu dipetakan kedalam urutan kontinyu simbol-simbol keluaran penkoder (enkoder) • Pemetaan ini disusun secara khusus, yang memungkinkan : • metode pengdekodean (dekoding) sangat berbeda dibandingkan dengan metode pengdekodean kelompok • Dapat dibuktikan bahwa penyandian belitan dapat mencapai : • gain penyandian yang lebih besar dibandingkan dengan yang dicapai dengan menggunakan kode kelompok (block code) dengan keruwetannya (koplexitasnya) yang serupa • Apapun teknik yang digunakan, baik dengan penyandian kelompok maupun penyandian belitan : • mana yang lebih baik untuk digunakan adalah tergantung pada perincian (details) dari penggunaannya serta teknologi yang ada pada saat itu.
KONSEP DASAR PENYANDIAN BELITAN Banyak dari konsep kode blok langsung digunakan terhadap kode konvolusi, khususnya : • urutan peta enkoder daripada keluaran pengkode sumber ke dalam urutan simbol kode untuk transmisi melalui DMC (Discrete Memoryless Channel) • Untuk menggambarkan konsep penyandian belitan secara mudah dapat digambarkan sebagai berikut : x1 (D )
g1 (D ) = 1 + D + D
2
+ Urutan kode keluaran
w(D )
g 1 (D ) = 1 + D 2
+ x1 (D )
47
Gbr. Pengkode belitan ½ kecepatan (Rate ½ convolution encoder)
• • • • •
• • • • • • • • •
Bit-bit masukan di”clock” kedalam rangkaian dari sebelah kiri Setelah setiap masukan diterima , maka keluaran koder dihasilkan dengan cara pencuplikan dan multiplexing keluaran-keluaran daripada penambah-penambah (adder) modulo-2 Untuk kode yang sederhana ini , simbol-simbol dihasilkan untuk setiap bit masukan , sehingga kecepatan kode adalah ½ nya Periksalah , bahwa suatu bit masukan tertentu akan mempengaruhi keluaran selama intervalnya sendiri , maupun oleh 2 interval bit masukan Suatu kode belitan ditentukan oleh : • banyaknya tahap pada register-register geser • banyaknya keluaran (banyaknya penambah modulo-2) • hubungan (koneksi) antara register geser dan penambah modulo-2 Tahap (state) enkoder ditentukan sebagai : • isi daripada register geser dan sepenuhnya ditentukan oleh 2 buah informasi masukan daripada bit yang mendahuluinya Enkoder di gbr. pengkode belitan ½ kecepatan bisa mempunyai 4 keadaan yang mungkin , sesuai dengan semua isi yang mungkin terjadi daripada register geser 2 tahap
w(D) = w0 + w1D + w2D 2 +………..+ wjD j + ……. = urutan bit informasi masukan ; wj ∈ [ 0, 1] x1(D) = Keluaran adder modulo –2 bagian atas adalah hasil kali antara w(D) dengan g1(D) w2 (D) = Keluaran adder modulo-2 bagian bawah adalah hasil kali antara w(D) dengan g2 (D) Kode konvolusi disebut juga dengan kode sekuensial ataupun kode berulang-ulang (recurrent codes) Pada kode konvolusi ini digit-digit uji paritas terus-menerus disisip-kan kedalam arus bit (bit stream) Karena itu prosedure enkoding dan dekoding adalah proses yang kontinyu, yang menghilangkan (eliminiting) pemisah (buffering) ataupun penyimpanan (storage) perangkat keras yang diperlukan dengan kode-kode blok Prinsip kode konvolusi dapat disederhanakan dengan menggu-nakan prinsip rangkaian enkoder konvolusi sebagai berikut ini :
mi
mi - 1
mi - 2
mi - 3
mi - 4
xi xi
+
• • •
(m)
(c)
= mi = mi − 4 ⊕ mi − 2 ⊕ mi
+
dimana mi s.d. mi –4 adalah shift register Rangkaian enkoder tersebut terdiri atas 5 buah shift register, 2 buah adder modulo-2. dan sebuah switch Digit-digit berita bergerak dari kiri ke kanan
48
•
Switch mengambil digit berita ke-i, yaitu xi( m ) = mi dan digit uji paritas ke-I sebagai beikut : xic = mi − 4 ⊕ m1− 2 ⊕ mi
= xi − 4 ⊕ xi − 2 ⊕ xi Digit-digit berita digeser satu cell dan prosesnya berulang (m) (c) (m ) (c ) Karena itu digit-digit yang dipancarkan adalah x1 x1 x 2 x 2 ⋅ ⋅ ⋅ ⋅ Jadi banyaknya digit yang dipancarkan menjadi 2 kali digit data yang masuk Hal ini dinamakan dengan “kode bercadangan tinggi “ (high redundancy codes) Sebagai akibatnya efisiensi kode konvolusi adalah rendah, yaitu R = 50 % Di dekorder, dibuat digit syndrome ke-i dari dari urutan berita yang diterima dan mungkin mengalami kesalahan, menggunakan rumus : ( m) (m) (m) (c) si = yi −4 ⊕ yi −2 ⊕ yi ⊕ yi ; i≥5 (m)
• • • • • •
(m)
(m)
dimana akibat adanya kesalahan maka : y i = xi Maka persamaan digit syndrome ke-i dapat ditulis menjadi : (m) (m) (c) s i = e i − 4 ⊕ e i − 2 ⊕ ei ; i≥5 (m)
• • • • •
(m)
⊕ ei
(m)
Disini jika syndrom si = 1 , maka berarti pada digit tersebut mengalami kesalahan digit-digit yang benar ditandai dengan digit syndrome bernilai 0 Untuk gejala peralihan awal (start up transient), ambillah 1 ≤ i ≤ 4 Maka sindrome-nya adalah : (m) (c ) (m) (m) (c) s1 = e1 ⊕ e1 s 3 = e1 ⊕ e3 ⊕ e3
s 2 = e2 ⊕ e2 s 4 = e2 ⊕ e4 ⊕ e4 Persamaan diatas ditampilkan secara grafis sebagai berikut : (m) (c) (m) (c) (m) (c) (m) (c) (m) (c ) (m) (c ) e1 e1 e2 e2 e3 e3 e4 e4 e5 e5 e6 e6 s1 X X (m)
(c)
(m)
(m)
(c)
s2 X
X
s3 X
X
s4
X X
X
s5 X
X
X
X X
X
X
X
X
s6
•
Dengan mempelajari gambar diatas dapat dilihat bahwa jika terdapat 2 atau 3 buah bit “1” di
s1 , s 3 dan s5 , maka : •
vektor kesalahan e1 dan harus dikoreksi
(m)
= 1 , yang berarti y1
(m)
mengan-dung kesalahan
49
• • • • • •
(m)
Dengan cara serupa, y 2 harus dikoreksi jika terdapat lebih banyak bit “1” daripada bit “0”; demikian seterusnya Algorithme seperti diatas dinamakan dengan pengdekodean ambang (threshold decoding) pada pengdekodean ini akan dapat mengoreksi sampai 4 buah kesalahan berturutan (termasuk juga digit uji paritas) asalkan 8 buah digit yang lain tidak mengalami kesalahan Pengdekodean ambang ini efektip terutama jika kanal-kanalnya terisolasi dari dadakan kesalahan (error burst) yang disebabkan oleh noise denyut, dan masalah utama terjadinya kesalahan adalah berasal dari noise denyut tersebut. Algorithme pengdekodean yang lain untuk kode-kode konvolusi adalah : • dengan menggunakan metode algorithme probabilistic atau metode algorithme berurutan (sequential). Oleh karena teori kode-kode konvolusi tidak dikembangkan sebaik teori kode-kode blok, maka : • sulit untuk membuat tafsiran yang teliti relatip terhadap ke-baikannya.
Soal –soal :
1. Suatu sistem mempunyai persamaan : p (t ) = sinc r (1 + ε )t ; 0 < ε < 1 . Kecepatan pensignalan kurang sedikit dibanding dengan kecepatan sinkron r (1 + ε ) . Datanya berupa urutan bit sebanyak 2 M + 1 buah, yang secara matematis dapat ditulis : Ak = (−1) k A ; k = 0, ± 1, ± 2, ⋅ ⋅ ⋅ ⋅ ⋅ ⋅, ± M . Buktikanlah : bagian ISI (Inter Symbol Interference) dari persamaan : ⎛m − k ⎞ y (t m ) = A m + ∑ A k p ⎜ ⎟ + n (t m ) r ⎝ ⎠ k ≠ m jika m = 0 adalah :
⎡ Aε ⎤ M ⎢2 1 + ε ⎥ ∑ sin c kε ≈ 2 Mε A jika Mε < 1 ⎣ ⎦ k =1
2. Suatu sistem biner mengalami interferensi antar simbol (ISI). Tanpa adanya noise, nilai y (t m ) dan probablitasnya ditabelkan berikut ini , jika yang dikirimkan adalah bit “ 1 “ :
y (t m ) : A − ∞
P[ y (t m )] :
1 4
A
A−∞
1 2
1 4
Tabel diatas berlaku juga untuk bit yang dikirimkan “0”, apabila A diganti dengan – A . (a). Dengan menganggap noisenya jenis Gaussian, carilah Pe ! (b). Carilah Pe untuk
A
σ
= 4.0 jika
α
A
= 0.05 dan 0.25 !
Bandingakan dengan Pe untuk α = 0 ! PENDEKODEAN KODE-KODE KONVOLUSI Dekoder mempunyai pengetahuan tentang struktur kode
50
ALGORITHME VITERBI Algorithme Viterbi adalah : • suatu metode yang sangat bagus untuk melakukan pendekodean (decoding = membuat signal yang menggunakan urutan bit-bit menjadi pulsa tersampling kembali) dengan kemungkinan kebenaran maximum terhadap kode-kode konvolusi • Hal ini disebabkan bahwa enkoder (alat yang berfungsi untuk membuat kode yang berupa orutan bit-bit) konvolusi adalah suatu peralatan keadaan yang tertentu (finite state divice) • Oleh A.J. Viterbi pada tahun 1967 algorithme tersebut telah digambarkan secara mathematis • Sejak itu algorithme tersebut terus menerus berkembang , misalnya apa yang telah dilakukan oleh Forney, dimana dia membuat tulisan yang luas wawasannya dan tinggi mutunya terhadap apa yang telah dilakukan oleh Vitebri, baik : • mengenai algorithmenya itu sendiri • maupun tentang bagaimana pemakaiannya. Dengan meninjau kembali terhadap fungsi dari suatu detektor dengan kemungkinan kebenaran yang maximum, maka : • apa yang dilakukan oleh Forney adalah : • mencari urutan kode yang paling mirip dengan kode yang telah dipancarkan sebelumnya ke kanal transmisi , sehingga membentuk urutan kode keluaran kanal yang memenuhi syarat • Kode itu mungkin diterima salah, sehingga harus secara otomatis dikoreksi (self correction) • Ini berarti bahwa : • harus mencari lintasan dengan melalui trellis (terali) yang akan dibahas kemudian , yang mana : • urutan kodenya mempunyai fungsi kemungkinan logarithmis tertinggi • Secara mathematis , rumus “kemungkinan log” (log-likehood) ditulis sebagai berikut :
ln { Pr ( y x m ) } = • •
∑ ln {P (y ∞
r
n =1
n
' x m ,n '
)}
Untuk BSC (Binary Symetric Code), pemaximalan fung-si ini sama saja artinya dengan mencari lintasan me-lalui terali (trellis) yang urutan kodenya paling dekat dengan jarak Hamming ke urutan kode yang diterima VA (Vitebri Alborithm) akan diterangkan pada contoh , untuk BSC (Binary Symetric System) yang menggunakan ukuran jarak Hamming
PENDEKODEAN KEPUTUSAN KERAS Perhatikanlah diagram teralis berbentuk kerucut terpotong berikut ini : Kedalaman
1 10
Urutan
yang diterima
00
00
2 10
00
3 10
00 11 11
4 11
5 11
00 11
11
6 10
00 11
11
00 11
11
8 11
7 01
00
00
51
Dari gambar diatas , untuk memudahkan penjelasan : • kedalaman (depth) kedalam teralis dinyatakan dengan diatas teralis • Sigmen-sigmen (bgian-bagian) lintasan ditunjukkan dengan keadaan-keadaan (states) teralis, yaitu : • {S1, S2 ...} yang dilewati oleh lintasan • Teralis tersebut dibentuk seperti kerucut yang terpotong (truncated) dengan jalan mengosongkan (clearing) pengkoder (encoder), yaitu : • dengan jalan memberikan masukan (inputting) 2 zeros (nol) yang diketahui, dimana dalam hal ini adalah bit nomor 7 dan nomor 8 • Alat pendekoder (decorder), yaitu alat yang berfungsi untuk membuat bit-bit kode menjadi signal analog kembali, akan mengetahui bahwa: • pada saat itu pengkoder telah dikosongkan • urutan bit yang diterima dituliskan didekat garis-garis teralis • Langkah pedekodean pertama adalah untuk : • menghitung jarak Hamming antara 2 buah simbol pertama yang diterima , dan 2 buah simbol pada cabang-cabang teralis yang meninggalkan keadaan 00 pada kedalaman 0 dan menuju ke kedalaman kadaan 1 • Jika diambil sigmen daripada gambar diatas : Kedalaman
Urutan bit
10
yang diterima
00
Jarak-jarak Hamingnya keduanya adalah 1 atau tunggal , dan dituliskan diatas node-node keadaan. Hal tersebut dapat dilihat pada gambar teralis yang berikutnya. Sebagai diketahui bahwa jarak Hamming tersebut dapat dilihat pada pertambahan modulo–2 berikut ini :
1
00
x1 0 11 0 1 0 0 x3 1 0 111 0 0 11 0 1 0 0 0
11
00 01
00
00
11 •
00
00
11
11
00
00
(X ) 10 01
01 10
(X )
10
10
01
11
11
(X )
(X )
01
01 10
10
10 01
01 10
00
11
11
11
11
11
11 10
10
00 11 11
01
01
01
10
Jika penulisan kode berita dilakukan secara pembacaan terbalik, yaitu : • jika kode untuk menyatakan nilai suatu level amplitudo, misalnya amplitudo yang terdiri atas 4 level, maka : • level amplitudo yang setinggi 4 buah level kuantisasi (quantization level), jika kodenya dinyatakan dengan kode biner , yang diperoleh adalah 0100 • dengan dibalik penulisannya , maka kodenya menjadi 0010 maka tabelnya akan berubah menjadi tabel berikut ini
52
Contoh : Misalkan enkoder terpotong bagian atas yang sama dengan yang digunakan untuk VA ( Viterbi Algorithm ) keputusan keras , diguna-kan pada sistem komunikasi keputusan lunak . Masukan biner DMC (Discrete Memoryless Channel) tergambar se-bagai berikut : 0.80
0 0
0.15 0.04 0.01
1 0.01 0.04
2 0.15
3
0.80
3
Probabilitas-probabilitas transisi kanal adalah sebagai berikut : ln[Pr (0 0)] = ln[Pr (3 3)] = ln Pr (0.80) ln[Pr (1 0)] = ln[Pr (2 3)] = ln Pr (0.15) ln[Pr (2 0 )] = ln[Pr (1 3)] = ln Pr (0.04 ) ln[Pr (3 0)] = ln[Pr (0 3)] = ln Pr (0.0.01)
= − 0.22 = − 1.90 = − 3.22 = − 4.61
Teralis enkoder tergambar sebagai berikut :
Gambar-gambar terali tersebut mencakup urutan keputusan lunak yang diterima , maupun ukuran-ukuran cabangnya (branch metrics). Ukuran-ukuran cabang tersebut dihitung dari urutan yang diterima dan fungsi kemungkinanlog diatas . Sebagai contoh : Ukuran cabang untuk cabang diantara kedalaman keadaan nol (depth zero state) 00 dan keadaan keadaan satu (depth one state) 10 , adalah : ln[Pr (31)] + ln[Pr (2 3)] = −0.22 − 1.90 = −2.12 Ukuran cabang adalah nomor diantara kurung (parenthesis) pada cabang . Semua cabang diberi label. Untuk penggambaran yang lebih jelas daripada proses penkodean itu , maka digambar lagi berikut :
Pada gambar tersebut , ukuran kumulatip (cummulative metric) • Untuk mempertahankan (surviving) sigmen lintasan yang menuju ke sebuah node, segera ditulis diatas node tersebut • Untuk node-node pada kedalaman satu , ukuran kumulatip betul-betul sama dengan ukuran cabang pertama
53
• •
• •
Untuk node-node pada kedalaman dua , ukuran kumulatip sama dengan jumlah dari ukuran kedalaman satu dan ukuran yang diakumulasikan pada cabang , yang mengarah dari kedalaan satu ke kedalaman dua Sebagai contoh , ukuran komulatip yang mengarah ke keadaan 01 di kedalaman dua adalah ukuraan -2.12 pada kedalaman keadaan satu 10 , ditambah ukuran cabang -3.80 yang dikumula-sikan pada cabang diantara kedalaman keadaan satu 10 dan kedalaman keadaan dua 01 Sebagaimana sebelumnya , pendekodean menjadi lebih menarik pada kedalaman tiga , dimana sigmen-sigmen lintasan mulai menjadi terbuang (dicarded) Perhatikan dua buah sigmen lintasan yang mengarah kedalam keadaan 00 dikedalaman tiga , dimana : • • • • • • •
Ukuran kumulatip untuk sigmen lintasan [ 00, 00, 00, 00] adalah : - 7.83 - 5.12 – 9.22 = - 22.17 Ukuran kumulatip untuk sigmen lintasan [ 00, 10, 01, 00] adalah : - 2.12 – 3.80 – 0.44 = - 6.36 Lintasan dengan ukuran terkecil adalah : -22.17 , dibuang dengan jalan menempatkan suaatu “x” pada cabang Ukuran daripada lintasan yang mempertahankan ditulis diatas keadaan 00 , dikedalaman tiga Pendekodean berlanjut dengan cara ini , sampaai dengan terali terakhir Setelah pendekode mencapai kedalaman delapan , pendekode tersebut berbalik arah , mengikuti lintasan yang mempertahankan , dengan tujuan untuk menentukan lintas-an yang benar lewat terali Amatilah bahwa lintasan yang mempertahankan adalah identik dengan lintasan yang diperoleh dengaan pendeko-dean keputusan keras
Probabilitas Kesalahaan Pendekodean Probabilitas kesalahan pendekodean bagi pendekodean Vitebri terhadap kode-kode konvolusi , dihitung dengan : - memakai konsep dasar yang sama dengan yang digunakan untuk menghitung probabilitas kesalahan bagi : o pengdekodean kemungkinan maximum kode-kode blok - Peristiwa-peristiwa kesalahan : o dihitung satu-satu (enumerated) o probabilitas-probabilitasnya dihitung o hasilnya dipakai untuk menghitung batas-batas probabili-tas kesalahan pengkodean o pada pendekodean Vitebri untuk kode-kode konvolusi , maka ukuran keandalan probabilitas yang tepat adalah : probabilitas bahwa lintasan yang tepat melalui tera-lis dibuang dikedalaman j o Ini berarti bahwa ukuran keandadalan yang benar ada-lah: probabilitas terbentuknya sebuah kesalahan pada setiap kesempatan pendekodean kesalahan suatu kesempatan untuk membuang lintasan benar , timbul : • msetiap saat dekoder bergerak satu unit lebih dalam ke teralis tersebut o Ukuran ini dibandingkan dengan ukuran yang digunakan pada kode-kpde blok , dimana :
54
kempatan timbulnya kesalahan pada setiap
Singkatan : 1. Kode konvolusi berbeda sangat mendasar dibanding kode blok . Proses kode konvolusi ini melalui urutan bit-bit informasi yang semi-infinite 2. Kode konvolusi dapat digambarkan dengan enkoder register ge-sernya , diagram transisi keadaanya atau diagram teralisnya 3. Kemungkinan (Likelihood) maximum dekoder , menggunakan di-finisi kode, urutan simbol yang diterima dan kharateristik kanal , untuk memperkirakan urutan simbol yang dikirimkan , yang se-tara dengan untuk memperkirakan lintasan (path) yang diikuti melewati teralis oleh enkoder . Perkiraan keluaran dekoder ada-lah urutan , yang mana : ∞
ln[Pr ( y x m )] = ∑ ln[Pr ( y n ' x mn ' )] n'
adalah maximum Urutan informasi keluaran dekoder adalah urutan yang membangkitkan urutan keluaran enkoder yang diperkirakan 4. Fungsi generator T(D , L , N) daripada kode konvolusi menggam-barkan bobot Hamming (ukuran N = power of N ) , panjang Ham-ming ( ukuran L ) dan banyaknya informasi 1s (ukuran N ) , untuk semua lintasan teralis , yang menyebar dari kembali memusat keadaan teralis nol . Fungsi generator dapat diperoleh dengan menyelesaikan himpun-an persamaan keadaan untuk diagram transisi keadaan yang dimodifikasi . 4. Algorithme Vitebri (VA) memberikaan cara-cara yang mudah bagi pendekodean dengan kemungkinan kebenaran maximum untuk kode-kode konvolusi 5. Probabilitas bahwa VA memilih lintasan yang salah (mengelemi-nasi lintasan yang benar) pada setiap kedalaman ke teralis diba-tasi oleh : Probabilitas Kesalahan :
PE <
∞
∑a
k=d
k
Pk
free
dimana a k dihitung dengan memakai fungsi pembangkit : T (D, 1, 1) <
∞
∑a
k = d free
k
Dk
dan probabilitas-probabilitas terjadi kesalahan : untuk kanal-kanal keputusan keras
Pk =
⎛k ⎞ e 1⎛ k ⎞ e k −e k/2 ⎫ ⎟⎟ p (1 − p ) ⎬ unt ⎜⎜ ⎟⎟ p (1 − p ) + ⎜⎜ 2 ⎝ k / 2⎠ ⎝e⎠ ⎭ k ⎧ ⎛k ⎞ k −e ⎫ Pk = ∑ ⎨ ⎜⎜ ⎟⎟ p e (1 − p ) ⎬ unt. k = ganjil e = (k / 2 ) + 1 ⎩ ⎝ e ⎠ ⎭
⎧ ∑ ⎨ e = (k / 2 ) + 1 ⎩ k
untuk keluaran kontinyu kanal keputusan lunak ∞ ⎛ 2kREb ⎞ ⎛ − x2 ⎞ 1 ⎟ ⎟⎟ dx = Q⎜ exp⎜⎜ Pk = ∫ ⎜ ⎟ 2 2 π N ⎝ o ⎠ 2 kREb ⎝ ⎠ No
6. Fungsi Q didifinisikaan sebagai
k = genap
55 ∞
Q( x ) = 1 − P ( x ) = ∫ Z (t ) dt x
7. Uraian asiptotis untuk Q(x) yang berlaku untuk nilai x besar adalah : n ( Z (x ) ⎡ 1 1.3 − 1) 1.3.5. ⋅ ⋅ ⋅ ⋅(2n + 1) ⎤ Q( x ) = + + ⋅⋅⋅⋅⋅⋅ + ⎥ + Rn ⎢1 − x ⎣ x2 x4 x 2n ⎦ dimana : ∞ Z (t ) n +1 Rn = (− 1) 1.3.5 ⋅ ⋅ ⋅ ⋅ ⋅ (2n + 1)∫ 2 n + 2 dt x t • •
yang mana nilai absolutnya adalah lebih kecil dibandingkan dengan nilai suku pertama diabaikan Untuk nilai x yang moderat (tidak terlalu besar), terdapat bebe-rapa pendekatan yang rational. Salah satu pendekatan tersebut adalah : 1 − Q( x ) = P( x ) = 1 − Z ( x )(b1t + b2 t + b3 t + b4 t + b5 t ) + ε ( x ) 1 ; ε ( x ) < 7.5 (10 −8 ) , dengan nilai-nilai : dimana t = 1 + px p = 0.2316419 b1 = 0.319381530 b2 = -0.356563782 b3 = 1.781477937 b4 = -1.8212559978 b5 = 1.330274429
8. Fungsi kesalahan dapat dikaitkan dengan fungsi Q, sesuai rumis berikut ini : x 2 −t2 erf ( x ) ∫ e dt = 1 − 2Q 2 x
π
(
)
0
9. Fungsi kesalahan pelengkap (complementary error function) dapat didekati serupa dengan fungsi-Q Tabel : tabel singkat nilai-nilai Q(x) dan Z(x) x
Q(x)
Z(x)
x
Q(x)
Z(x)
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
0.50000 0.46017 0.42074 0.38209 0.34458 0.30854 0.27425 0.24196 0.21186 0.18406 0.15866
0.39894 0.39695 0.39104 0.38138 0.36827 0.35206 0.33322 0.31225 0.28969 0.26608 0.24197
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1
0.13567 0.11507 0.09680 0.08076 0.06681 0.05480 0.04457 0.03593 0.12872 0.02275 0.1786
0.21785 0.19419 0.17137 0.14973 0.12952 0.11092 0.09405 0.07895 0.06562 0.05399 0.04398
Note : tabel diatas berdasarkan pada rumus untuk Probabilitas Kesalahan Pe ( x ) = Q( x ) =
1 ⎛ x ⎞ erfc⎜ ⎟ 2 ⎝ 2⎠
Contoh jika x = 2 ; untuk mencari besarnya probabilitas kesalahan dapat diselesaikan dengan program Matlab , dengan perintah sebagai berikut : >> 0.5.*erfc(2./(2.^0.5)) ans = 0.0228 ; hasilnya boleh dikatakan sama dengan 0.02275 (yang terdapat pada tabel)
56
10. Probabilitas Kesalahan Bit untuk pendekodean Vitebri terhadap kode-kode konvolusi , dibatasi dengan persyaratan sebagai beri-kut :
Pb =
∞
∑c
k = d free
k
Pk
dimana Pk dihitung dari hubungan : ∞ d {T (D, 1, 1) } = ∑ c k Dk dN k = d free
11. Diketahui banyak kode konvolusi yang bagus , dimana sebagian besar diperoleh dengan mencari lewat komputer . Gain pengkodean untuk kode konvolusi yang bagus dapat setinggi nilai pendekatan , yaitu 6 dB , dengan cara memakai pengdekodean keputusan lunak . Beberapa yang terbaik adalah kode konvolusi bernilai 1/2 dan dan bernilai 1/3 , telah dibuat petanya . 12. Kode-kode konvolusi dapat didekode memakai pendekodean sekuensial . Keruwetan pendekodean sekuensial adalah bebas dari panjang kendala , sehingga kodekode dengan panjang kendala yang tinggi , dapat didekode . 13. Pendekodean blok daripada kode konvolusi berentetan (con-cantenated convolution) serta kode Reed-Solomon dapat digu-nakan jika dikehendaki untuk yang gain penkodeanya besar (large coding gain) . Sistem-sistem penkodean berentetan telah digunakan misi ruang angkasa .
Soal-soal tentang VA :
1. Dengan menggunakan kode yang ditentukan oleh teralis sebagai gambar berikut :
lakukan dekode memaakai pendekodean Vitebri keputusan keras Perhatikan 4 buah vektor-7 berikut ini : g 0 = 1101000 g1 = 0110100 g 2 = 1110010 g 3 = 1010001 Dengan 4 buah vektor tersebut akan terdapat 24 = 16 buah kombinasi linier ; hal ini sesuai dengan 16 jenis kombinasi urutan bit , yang masing-masing kombinasi terdiri atas 4 buah bit yang tersusun secara seri. Contoh : Kombinasi linier yang disebabkan oleh w = [w0 w1 w2 w3 ] = [1 0 1 1] adalah : x = w g = (1 . g 0 ) + (0 . g1 ) + (1 . g 2 ) + (1 . g 3 ) = 1101000 + 0000000 + 1110010 + 1010001 = 1001011 Secara lengkap terdapat 16 jenis urutan bit , yang urutan–urutan bit tersebut berbeda satu sama lain.
57
Jika disusun tabel kombinasi linier dan secara lengkap, maka didapatkan hasil yang persis sama , sebagaimana tabel kode blok , sebagai berikut :
w0
w1
w2
w3
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
Kombinasi Linier 0000000 1101000 0110100 1011100 1110010 0011010 1000110 0101110 1010001 0111001 1100101 0001101 0100011 1001011 0010111 1111111
Fungsi denyut : semua fungsi yang memenuhi hubungan ∞
∫ δ (t − t )x(t ) = x(t ) 0
0
−∞
maka δ (t − t0 ) adalah fungsi denyut yang terjadi pada t = t 0 Fungsi periodic : Jika fungsi periodic h(t ) = A cos(2π f 0 t ) → H ( f ) =
∞
∫ A cos(2π
f 0 t ) e − j 2π f t dt
−∞
H(f ) =
∞
(
)
∞
{
}
A A e i 2π f 0 t + e −i 2π f 0 t e − 2π f t dt = ∫ e i 2π ( f 0 − f ) t + e −i 2π ( f 0 + f ) t dt ∫ 2 −∞ 2 −∞
58 ∞ ∞ ⎫⎪ A A ⎧⎪ −i 2π ( f − f0 )t −i 2π ( f 0 + f ) t H( f ) = ⎨ ∫ e dt + ∫ e dt⎬ = {δ ( f − f 0 ) + δ ( f + f 0 )} 2 ⎪⎩− ∞ ⎪⎭ 2 −∞ ∞
Note : δ ( f ) = ∫ δ (t )e
−i 2π
(f )t
∞
dt =
−∞
∫ (1 )e
−i 2π
(f ) t
∞
dt =
−∞
Kebalikan H ( f ) → h(t ) adalah :
h(t ) =
∫e
− i 2π
(f )t
dt
−∞
∞ ∞ ∞ ⎫⎪ A A ⎧⎪ j 2π f t j 2π f t j 2π f t { ( ) ( ) } ( ) ( ) δ f f δ f f e df δ f f e df δ f f e df − + + = − + + ⎬ ⎨ 0 0 0 0 ∫ 2 −∫∞ 2 ⎩⎪−∫∞ −∞ ⎭⎪ A A h(t ) = e j 2 π f t + e − j 2 π f t = A cos 2 π f t 2 2
∞
Note :
j 2π f t 2π f t ∫ δ ( f ) f 0 )e df = e
−∞
∞
dan
∫ δ ( f − f )e 0
j 2π f t
df = e − j 2π f t
−∞
A • Jadi A cos 2π f t ⇔ {δ ( f − f 0 ) + δ ( f + f 0 )} 2 • Jika kendala panjang (length constraint) = M , relatip pendek , yaitu jika M ≤ 8 , maka : • dekoder dapat melakukan “pendekodean” secara optimal relatip dengan sedikit perhitungan saja . Pengdekodean yaang dilakukaan adalah : • pengdekodean keputusaan keras (hard dececion decoding) • pengdekodean keputusaan lunak (soft dececion decoding) - Dekoder keputusaan keras : menerima keputusan bit (bit dececion) dari demodulator . Setiap bit yang diterima diputus-kan “0” ataau “1” - Dekoder keputusaan lunak : meliputi pemakaian dari keluaran demodulator yang sebanding dengan “kemungkinan log” (log- likehood) daripada bit yang dimodulasi , baik yang “0” maupun “1” . - Kemungkinan log (loglikehood) adalah : logarithme dari proba-bilitas menjadi suatu bit 0 ataupun 1 - Rumus : loglikehood = log (Pr< x = 0⏐z = 1 >) - Sebagai misal , jika bit yang didemodulasi adalah 1 , maka bit hasil demodulasi adalah 0. - Jika bit yang dipancarkan adalah variable x dan yang didemo-dulasi adalah variabel z , maka expresi ini adalah loglikehood , bahwa x adalah 0 asalkan z adalah 1 . • Pendekodean keputusaan lunak biasanya menghasilkan kinerja yang lebih baik , namun lebih komplex
Pendekodean Keputusaan Lunak Pada pendekodean ini , kata kode yang diterima bisa berupa setiap bilangan riil apapun juga . Oleh karena adanya : • kekaburan kanal (channel fading) • noise • interferens • faktor-faktor lain maka bit yang lewat media transmisi bisa berubah , misalnya 0 men-jadi bukan nilai nol , ataupun sebaliknya . Misalnya : akibat terjadinya kesalahan , dari bit “0” berubah menjadi nilai riil bukan nol , yang diberi simbol dengan “x” .
59
Jika probalitas “0” menjadi (-Inf s.d. 1/10) adalah 2/5 probalitas “0” menjadi (1/10s.d 1/2) adalah 1/3 2/5+1/3+1/5+1 probalitas “0” menjadi (1/2 s.d. 9/10) adalah 1/5 probalitas “0” menjadi (9/10. Inf) adalah 1/15 Jika probalitas “1” menjadi (-Inf s.d. 1/10) adalah 1/16 probalitas “1” menjadi (1/10 s.d. 1/2) adalah 1/8 1/16+1/8+3/8+ probalitas “1” menjadi (1/2 s.d. 9/10) adalah 3/8 7/16=1 probalitas “1” menjadi (9/10 s.d. Inf) adalah 7/16 Penulisan secara matematis adalah sebagai berikut : Probabilitas Penerimaan Probabilitas Penerimaan Jika Mengirim 0 Jika Mengirim 1 P((-Inf. 1/10)|0) = 2/5 P((-Inf . 1/10)|1) = 1/16 P((1/10 . 1/2)|0) = 1/3 P(( 1/10. 1/2)|1) = 1/8 P((1/2 . 9/10)|0) = 1/5 P((1/2 . 9/10)|1) = 3/8 P((9/10 . Inf)|0) = 1/15 P((9/10 . Inf)|1) = 7/16 Limtasan optimum (Optimum path) untuk keputusaan lunak (soft de-cision) ini adalah memaximalkan matrix signal yang diterima r dan signal yang dikoreksi c . Untuk panjang kata kode sebanyak N transmisi (=N buah bit) , maka matrix M (r c ) = ∑ log P (ri / ci ) N
i =1
⎡ LB1 ⎢ Transfer Probability = ⎢ P( [LB1.LB 2] 0 ) ⎢⎣ P( [LB1.LB 2] 0 )
1 ⎡ −∞ ⎢ 10 ⎤ LB 2 1 ⎥ ⎢ 2 P( [LB 2.LB3] 0 )⎥ = ⎢ 3 ⎢ 5 P( [LB 2.LB3] 0 ) ⎥⎦ ⎢ 1 1 ⎢⎣ 16 8
1 9⎤ 2 10 ⎥ 1 1⎥ ⎥ 5 15 ⎥ 3 7⎥ 8 16 ⎥⎦
APLIKASI FFT Jika fungsi e −t dihitung dengan menggunakan pendekatan FFT , untuk transfomasi Fourienya , maka : • Langkah ke-1 didalam penggunaan DFT adalah : • Menentukan N = tinggi maximum sample dan T = interval sample • Sebagai contoh , N = 32 , maka setiap sample dinyatakan dengan 5 buah bit ; jika T = 0.25 detik , maka pada waktu tersebut nilai e − t ≅ 0 • Hal tersebut digambarkan dengan kurva e −t , yang dilukis berdasarkan program Matlab berikut ini : » t=0:0.01:7; » x=[exp(-t)]; » plot(t,x); » plot(t,x)
60
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
•
Berdasarkan
0
1
kurva
e −6 = 0.0025 ≅ 0 ) •
2
diatas
3
,
maka
4
5
6
e −t ≅ 0 t ≅6
7
(menurut
perhitung-an
,
