Encoding (part 1: noiseless coding)

.: Tulisan ini bertujuan untuk menjelaskan dasar dari teknik pengkodean (selanjutnya disebut encoding) :.

Encoding tidak terlepas dari permasalahan saat transfer data dari suatu lokasi ke lokasi lain atau saat pengambilan data yang disimpan (data storage). Fokus dari permasalahan adalah pada pengemasan informasi dan deteksi serta koreksi error data. Dari permasalahan tersebut, encoding dapat dikategorikan ke dalam dua jenis: noiseless coding dan noissy coding.

Noiseless Coding
Teknik ini biasa juga disebut source coding atau teknik kompresi atau encoding for efficiency. Noiseless coding bertujuan untuk mengkodekan sumber informasi sedemikian rupa sehingga total informasi pada message yang di encode sedekat mungkin dengan besarnya entropy dari message aslinya. Shannon pertama kali meletakkan dasar dari Noiseless Coding Theorem secara matematis dengan pertidaksamaan sebagai berikut

H_{r}(S) \leq MinAveCodeLen_{r}(S) ,   (1)

dimana H_{r} adalah entropy dengan logaritma berbasis r, S adalah sumber alphabet dengan n simbol: x_1, x_2, \cdots, x_n , dan MinAveCodeLen adalah fungsi panjang codeword rata-rata yang terkecil. Panjang codeword rata-rata bisa diekspresikan dengan persamaan sebagai berikut

AveCodeLen = \sum\limits_{i = 1}^{n} p_{i} l_{i},   (2)

dimana p_i adalah probabilitas kemunculan dari simbol x_i dan l_i adalah panjang codeword dari simbol x_i. Persamaan (1) menunjukkan bahwa entropy merupakan batas bawah (lower bound) dari fungsi panjang codeword rata-rata terkecil. Teori ini kemudian berkembang dengan skema Shannon-Fano encoding sehingga diperoleh batas atas (upper bound) dari fungsi panjang codeword rata-rata terkecil yaitu sebesar H_{r}(S) + 1 sehingga pertidaksamaan Noiseless Coding Theorem menjadi

H_{r}(S) \leq MinAveCodeLen_{r}(S) < H_{r}(S)+1 ,   (3)

Contoh :

Dalam ekspedisinya di planet Mars, robot Rover menemukan 4 buah elemen yang sering muncul dari suatu lubang. Keempat elemen tersebut masing-masing berwarna abu-abu, biru, merah, dan kuning (a, b, m, dan k). Peluang kemunculan elemen a adalah p(a) = 2/17, peluang kemunculan ketiga elemen lainnya adalah sebagai berikut: p(b) = 2/17, p(m) = 8/17, p(k) = 5/17. Rover harus melaporkan hasil pengamatannya dengan cara mengkodekan informasi yang diperolehnya dengan binary (0 atau 1). Dalam algoritma encodingnya, Rover menemukan 2 skema yang mungkin:
– skema 1,   a: 11 , b: 0, m: 100, k: 1010
– skema 2,   a: 01010, b: 00, m: 10, k: 11
Pertanyaan:
1. manakah pengkodean yang paling effisien? (efisien = skema encoding yang memiliki panjang codeword rata-rata yang terkecil)
2. apakah informasi tersebut masih bisa dikodekan lebih efisien lagi? Apa alasannya?

Advertisements

4 thoughts on “Encoding (part 1: noiseless coding)

  1. pak guru, saya iseng jawab ya. kalo salah tolong dikoreksi. kalo bener, jangan lupa kasih hadiah 😛
    hasil itung2an minAveCodeLen : skema 1 = 2.94, skema 2 = 2.35
    1. skema 2 lebih efisien
    2. masih bisa, soalnya codeword rata-ratanya masih bisa dibuat lebih kecil. contoh, a: 001, b: 000, m: 01, k: 1

    o iya, noiseless coding itu maksudnya coding yang ga dimaksudkan buat kena noise bukan? soalnya kalo dikompres seekstrim itu kayaknya bakal langsung rusak deh pas kena noise :-/
    terus nilai antar kode itu mesti unik sesuai urutan ga? atau ga mesti unik? boleh ga misalnya dibikin, a:00, b:10, c: 0, d: 1 (c sama dengan bagian depannya a, d sama dengan bagian depannya b). sori malah jadi tanya balik, hihihi

  2. Yup, jawaban 1 benar.
    average code length untuk skema 1: 2*2/17 + 1*2/17 + 3*8/17 + 4*5/17 = 50/17 = 2.94
    average code length untuk skema 2: 5*2/17 + 2*2/17 + 2*8/17 + 2*5/17 = 40/17 = 2.35
    Jadi, skema 2 lebih efisien.

    Jawaban 2 masih kurang memuaskan :p. Walaupun codeword bisa dibuat lebih kecil, belum tentu bisa di-decode dengan benar. Hint: lower bound

    Noiseless coding tujuannya untuk meningkatkan efisiensi dalam sistem komunikasi dimana noise diabaikan. Jadi noise ga perlu dihadirkan dalam encoder atau decoder. Beda dengan noissy coding yang memang tujuannya untuk mendeteksi & mengkoreksi error. Kalo ga ada error ya ga perlu (noisy) coding, tapi source coding (noiseless) masih perlu untuk kompresi.

    Codeword jelas harus unik. Contoh yang Felis kasih juga unik. Pertanyaannya, apakah decoder akan selalu sukses men-decode-nya? Seandainya ada codeword 000000, gimana decoder bisa membedakan a dan c ? Seandainya peluang kemunculan c lebih besar & algoritma decoder mempertimbangkan hal ini, bisa jadi hasil decodernya : cccccc, simbol a tidak pernah diperoleh.

    FYI, Shannon hanya menunjukkan batasan-batasan atau bounds nya, tapi ga memberikan koding apa yang bisa mencapai atau melampaui batasan itu. Itulah yang menyebabkan para peneliti sibuk membuat teknik pengkodingan yang terbaik, sampai akhirnya muncul LDPC nya Galager (noissy coding, dari disertasi doktornya tahun 1963 lalu setelah adanya super komputer coding itu “reinvented” tahun 2001 dan telah dibuktikan performanya hanya beda 0.0045 dB dari Shannon limit). Sejak saat itu, bisa dibilang penelitian untuk ini sudah tidak menarik lagi. Performa maksimum sistem komunikasi point-to-point sudah bisa ditebak. Issue nya tinggal dibagian implementasi, dan ini tidak menarik bagi orang teori :D.

  3. wow… mantab penjelasannya 🙂

    tadi saya buka blog post Ade soal entropy, baru ngeh, he he he.
    batas bawahnya berarti liat dari Shannon limit:
    H_r(S) = – ( 2/17 * log2(2/17) + 2/17 * log2(2/17) + 8/17 * log2(8/17) + 5/17 * log2(5/17) ) = 1.75
    ralat jawaban nomer 2 tadi, masih bisa lebih efisien karena average code length masih lebih besar dari Shannon limit. (semoga kali ini bener)

    oya, satu lagi yang saya masih penasaran soal Shannon limit ini. Dulu sering denger kalo LDPC mendekati Shannon limit. Terus Ade juga bilang selisihnya cuma 0.00045 dB. Yang saya masih bingung, itu 0.00045 dB antara nilai apa di Shannon limit dengan nilai apa di LDPC ya? Dulu saya ngiranya itu selisih SNR mereka saat BER tertentu. Setelah tau kalau Shannon limit itu noiseless, jadi bingung deh. Apa itu perbandingan dengan nilai entropy tadi? @_@

    1. Uppss.. sepertinya comment saya bikin ambigu ya. Shannon Limit ga sama dengan Entropy. Entropy disini hanya menjadi lower bound untuk source coding. Kalo bicara Shannon Limit pasti masalah noissy coding.
      Ralat, selisih (Eb/N0) 0.0045 dB (bukan 0.00045 dB), untuk mencapai BER yang sama, BER = 10^-6. Silahkan cek papernya

      Jawabannya sudah memuaskan :).
      Seandainya kita mengasumsikan peluang kemunculan semua informasi adalah sama (untuk kasus ini p = 1/4), artinya sama dengan hanya melihat jumlah informasi yang ada (jumlah informasi = 4 yaitu a,b,m,k), maka kita bisa mendapatkan average code length = 2 (nilai ini masih lebih kecil daripada skema 1 dan 2). Dengan demikian kita bisa meng-encode seperti berikut: a –> 00, b –> 01, m –> 10, k –> 11. Kasus ini sama dengan teori informasi yang diperkenalkan Hartley. Untuk mendapatkan average code lebih kecil lagi, bisa menggunakan Huffman Encoding. Berani coba dan buktikan sendiri? 😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s