THE BINARY SYMMETRIC CHANNEL

THE BINARY SYMMETRIC CHANNEL
(Diajukan guna memenuhi tugas Teori Pengkodean)









Disusun Oleh:
Kelompok 4.
Zainul Gufron Syahroni (070210191048)
Dian Purnomo (070210191075)
Hendra Desma Adi Wiguna (070210191129)






PROGRAM STUDI PENDIDIKAN MATEMATIKA
FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
UNIVERSITAS JEMBER
2010

BINARY SYMMETRIC CHANNEL (BSC)

Teori Koding (Coding theory) merupakan ilmu yang mempelajari teknik dan metoda transmisi data/infomasi melalui saluran komunikasi yang tidak bebas gangguan (noisy) secara efisien dan akurat. Teori Koding telah berkembang begitu pesat dan memliki aplikasi yang sangat cukup luas, diantaranya minimisasi gangguan dari perekaman compact disc, transfer data dari memori ke CPU komputer atau antar CPU komputer, transaksi ATM, dan komunikasi satelit.
Media fisis yang digunakan untuk melakukan transfer data biasa disebut dengan saluran; Sebagai contoh, kabel telepon dan atmosfir. Gangguan (noisy) didefinisikan sebagai sesuatu yang tidak diinginkan yang dapat menyebabkan informasi yang diterima tidak sama dengan informasi yang dikirimkan. Gangguan dapat terjadi karena adanya petir, goresan, hujan meteor, panas matahari, gangguan radio, dan lain-lain. Teori koding bekerja hanya sebatas pada masalah pendeteksian dan pengoreksian kesalahan transmisi yang disebabkan oleh gangguan tersebut. Pada sistem ini, adanya gangguan adalah bagian yang paling penting; Karena tanpa gangguan, teori koding tidak begitu diperlukan.
Informasi dapat dinyatakan sebagai barisan 0  1. Kita sebut '0' dan '1' sebagai digit. Katakode merupakan suatu barisan digit. Panjang dari katakode adalah banyaknya digit yang menyusun katakode tersebut. Katakode 10010 misalnya mempunyai panjang n = 5. Saluran komunikasi yang digunakan pada kajian ini adalah saluran biner. Kode biner merupakan suatu himpunan katakode biner (tersusun oleh digit '0' dan '1').
Suatu saluran biner dikatakan simetri bila digit 0 dan 1 ditransmisikan dengan akurasi yang sama. Ini berarti bahwa probabilitas menerima digit yang benar tidak tergantung pada digit yang dikirimnya. Kepercayaan suatu binary symmetric channel (BSC) adalah bilangan real p, 0 ≤ p ≤ 1, dimana p adalah probabilitas menerima digit yang salah.
Beberapa asumsi tambahan untuk saluran perlu diberikan. Pertama, panjang katakode yang diterima tidak mengalami perubahan. Ini berarti bahwa katakode yang dikirim berpanjang n maka kata yang diterima pasti berpanjang n. Kedua, dalam membaca kode, kita dapat dengan mudah mengetahui awal dari suatu kata. Sebagai contoh, bila kita menggunakan katakode panjang 3 dan menerima 100110001, maka dibaca secara berturutan 100, 110 dan 001. Ketiga, gangguan dapat terjadi dimana saja. Ini berarti, kita tahu bahwa setiap digit dalam katakode dapat mengalami gangguan dalam transmisi.
Dalam banyak hal, sangat sukar menaksir probabilitas p untuk suatu saluran yang diberikan. Namun, nilai eksak p tidak mempengaruhi secara siknifikan pada kerangka teori koding itu sendiri. Bila p = 0 maka saluran komunikasi sangat baik (tidak pernah ada gangguan transmisi data).
Misal ambil sebarang kata kode dengan panjang n, yaitu: X1 X2 X3 . . . Xn.
kata kode yang dikirim kata kode yang diterima
X1 X2 X3 . . . Xn
X1’ X2 X3 . . . Xn
Pada pengiriman kata kode di atas, terdapat 1 kesalahan pada digit pertama yaitu X1  X1’ sehingga peluang kesalahannya adalah p. Sedangkan digit ke 2 sampai digit yang ke– n adalah benar(dikirim sama dengan yang diterima), jadi peluang tiap digitnya adalah ( 1 p ). Karena jumlah digit dari kata kode adalah n, sedangkan terjadi 1 kesalahan pada digit pertama sehingga banyaknya digit yang benar adalah (n1), jadi peluang tiap digit yang benar adalah ( 1 p )n-1 . Peristiwa di atas merupakan kejadian yang saling bebas ( karena pengiriman tiap digit merupakan kejadian yang tidak saling mempengaruhi ). Oleh karena itu, kejadian di atas termasuk berdistribusi binomial newton, sehingga peluang terjadi kesalahan tepat 1 pada digit pertama dapat dicari dengan rumus : p1( 1-p )n-1
Jadi dapat disimpulkan, peluang terjadi kesalahan tepat k adalah Pk( 1-p )n-k.

 
Diagram di bawah menggambarkan binary symmetric channel:







Dari diagram di atas, Probabilitas bahwa 0 dikirim akan diterima sebagai 0 adalah 1 - p. Demikian juga kemungkinan bahwa 1 dikirim akan diterima 1 sebagai 1 - p. Probabilitas bahwa 0 dikirim diterima sebagai 1 adalah p, seperti kemungkinan bahwa 1 dikirim diterima sebagai 0.

Keterangan:
0 memiliki panjang n= 1,
0 dikirim sebagai 0 maka k= 0,
Jadi probabilitasnya = pk (1-p)n-k
= p0(1-p)1-0
= 1.(1-p)1
= (1-p)

Keterangan:
1 memiliki panjang n= 1,
1 dikirim sebagai 1 maka k= 0,
Jadi probabilitasnya = pk (1-p)n-k
= p0(1-p)1-0
= 1.(1-p)1
= (1-p)

Keterangan:
0 memiliki panjang n= 1,
0 dikirim sebagai 1 maka k= 1,
Jadi probabilitasnya = pk (1-p)n-k
= p1(1-p)1-1
= p.(1-p)0
= p. 1
= p

Keterangan:
1 memiliki panjang n= 1,
1 dikirim sebagai 0 maka k= 1,
Jadi probabilitasnya = pk (1-p)n-k
= p1(1-p)1-1
= p.(1-p)0
= p. 1
= p
Mari kita melakukan penghitungan kombinatorial, berdasarkan BSC: Secara umum bahwa, katakode yang dikirim dengan panjang n maka probabilitas kesalahan dengan tepat k kesalahan yang terjadi adalah pk (1 - p) n-k dengan k adalah jumlah kesalahan / error setiap digit. Jumlah pola kesalahan tersebut adalah jumlah kemungkinan memilih k elemen dari n. Ini adalah C(n,k). Probabilitas bahwa k kesalahan yang terjadi adalah
C (n,k) pk (1 - p)n-k. Probabilitas bahwa kesalahan tidak lebih dari k adalah:
∑_(i=0)^k▒〖〖C 〗_((n,i)) p^i 〖(1 - p)〗^(n-i) 〗
Mengasumsikan katakode dengan panjang n dikirim melalui saluran. Probabilitas kesalahan bahwa tidak ada kesalahan yang terjadi (k = 0) adalah
(1 - p)n. Sedangkan probabilitas kesalahan bahwa tepat satu kesalahan yang terjadi
(k = 1) adalahp (1 - p) n-1.
PERMASALAH:
Hitung probabilitas bahwa tidak lebih dari k= 1 kesalahan terjadi di transmisi dari bit string dengan panjang n= 10, ketika kesalahan bit probabilitas:
p = 10-3, atau p = 10-40, atau p = 10-5.
Jawab:
p = 10-3
∑_(i=o)^1▒C_((n,i) ) p^i (1-p)^(n-i)
=10!/((10-0)!.0!) (〖10〗^(-3) )^0 (1-〖10〗^(-3) )^(10-0)+ 10!/((10-1)!.1!) (〖10〗^(-3) )^1 (1-〖10〗^(-3) )^(10-1)
=1.1.(999/1000)^10+ 10.(1/1000).(999/1000)^9
=(999/1000)^9 {(999/1000)^1+ (1/100) }
=(999/1000)^9 {(999+10)/1000}
=(999/1000)^9. (1009/1000)

Jika w = 10110 diterima pada saluran SBS dengan p = 0,02. Katakode manakah dari berikut: 11011; 00111; 01000; 10001 yang kemungkinan besar dikirim ?
Jawab:
Karena 00111 paling mendekati w (memiliki kesalahan k paling sedikit) maka 00111 dapat dikatakan katakode yang kemungkinan besar dikirim.
Kenapa saluran dengan p = 0 tidak menarik ?
Jawab: Bila p = 0 maka saluran komunikasi sangat baik (tidak pernah ada
gangguan transmisi data).
DAFTAR PUSTAKA

Cahya P., Antonius. 2010. Slide perkuliahan” ALGEBRAIC CODING THEORY”. Jember: FKIP UNEJ.
http://personal.fmipa.itb.ac.id/ebaskoro/files/2008/02/bukukoding.pdf
(Tanggal Akses: 3 November 2010)





NAMA PENANYA:
Niken Tri Utami
Rina Azizah
Emi Yulianti
 
Lampiran:
Sumber: http://personal.fmipa.itb.ac.id/ebaskoro/files/2008/02/bukukoding.pdf

Chapter 1
Pendahuluan
Teori Koding (Coding theory) merupakan ilmu yang mempelajari teknik dan metoda trans-misi data/infomasi melalui saluran komunikasi yang tidak bebas gangguan (noisy) secara efisien dan akurat. Teori Koding telah berkembang begitu pesat dan memliki aplikasi yangsangat cukup luas, diantaranya minimisasi gangguan dari perekaman compact disc, transfer data dari memori ke CPU komputer atau antar CPU komputer, transaksi ATM, dan komunikasi satelit.
Media fisis yang digunakan untuk melakukan transfer data biasa disebut dengan saluran; Sebagai contoh, kabel telepon dan atmosfir. Gangguan (noisy) didefinisikan sebagai sesuatuyang tidak diinginkan yang dapat menyebabkan informasi yang diterima tidak sama dengan informasi yang dikirimkan. Gangguan dapat terjadi karena adanya petir, goresan, hujanmeteor, panas matahari, gangguan radio, dan lain-lain. Teori koding bekerja hanya sebataspada masalah pendeteksian dan pengoreksian kesalahan transmisi yang disebabkan olehgangguan tersebut. Perhatikan diagram pada Gambar 1.1 yang mengilustrasikan system transmisi informasi secara umum.
Pada sistim ini, adanya gangguan adalah bagian yang paling penting; Karena tanpagangguan, teori koding tidak begitu diperlukan. Dalam kajian selanjutnya, kita akan memberikan asumsi-asumsi berikut ini:

Informasi dapat dinyatakan sebagai barisan 0-1. Kita sebut '0' dan '1' sebagai digit. Kata merupakan suatu barisan digit. Panjang dari kata adalah banyaknya digit yang menyusun kata tersebut. Kata 10010 misalnya mempunyai panjang 5. Saluran komunikasi yang digunakan pada kajian ini adalah saluran biner. Kode biner merupakan suatu himpunan kata biner (tersusun oleh digit '0' dan '1'). Berikut ini contoh dari dua kode:
 

Kode blok adalah suatu kode yang setiap katanya mempunyai panjang sama. Panjang ini disebut panjang kode. Semua kata yang termasuk dalam kode C disebut sebagai katakode.
Diskusi 1.0.1.
1. Cacah semua kata dengan panjang 3, 4 dan 5.
2. Tentukan banyaknya kata dengan panjang n.
3. Berikan suatu kode yang berisi semua kata dengan panjang 6 dan mempunyai jumlah angka '1' yang genap.
Beberapa asumsi tambahan untuk saluran perlu diberikan. Pertama, panjang katakode yang diterima tidak mengalami perubahan. Ini berarti bahwa katakode yang dikirim berpanjang n maka kata yang diterima pasti berpanjang n. Kedua, dalam membaca kode, kita dapat dengan mudah mengetahui awal dari suatu kata. Sebagai contoh, bila kita menggunakan katakode panjang 3 dan menerima 100110001, maka dibaca secara berturutan 100,110 dan 001. Ketiga, gangguan dapat terjadi dimana saja. Ini berarti, kita tahu bahwa setiap digit dalam katakode dapat mengalami gangguan dalam transmisi.
Suatu saluran biner dikatakan simetri bila digit 0 dan 1 ditransmisikan dengan akurasi yang sama. Ini berarti bahwa probabilitas menerima digit yang benar tidak tergantung pada digit yang dikirimnya. Kepercayaan suatu saluran biner simetri (SBS) adalah bilangan real dimana p adalah probabilitas menerima digit sesuai dengan digit yang dikirim. Diagram di bawah menggambarkan saluran biner simetri:
Dalam banyak hal, sangat sukar menaksir probabilitas p untuk suatu saluran yang diberikan. Namun, nilai eksak p tidak mempengaruhi secara siknifikan pada kerangka teorikoding itu sendiri. Bila p = 1 maka saluran komunikasi sangat baik (tidak pernah ada gangguan transmisi data). Sehingga, hal ini tidak menarik. Hal yang serupa berlaku bila p = 0. Setiap saluran dengan dapat dengan mudah diubah menjadi saluran dengan
Sehingga, untuk selanjutnya, dapat mengasumsikan bahwa kita menggunakan saluran biner simetri dengan probabilitas p,
Diskusi 1.0.2.
1. Kenapa saluran dengan p = 0 tidak menarik ?
2. Terangkan bagaimana merubah saluran dengan menjadi suatu saluran dengan
3. Apa yang dapat anda katakan untuk saluran dengan ?
4. Misal w = 0010110 diterima melalui saluran SBS dengan p = :90. Katakode manakah dibawah ini yang kemungkinan besar telah dikirim?
1001011; 1111100; 0001110; 0011001; 1101001: