Encoding (part 2: noisy coding)

Bayangkan dalam satu kali SMS yang dibatasi oleh 160 karakter kita bisa mengirimkan informasi yang banyak dengan menggunakan beberapa kata yang disingkat yang masih bisa dimengerti oleh si penerima SMS. Tulisan saya sebelumnya mengenai noiseless coding telah menunjukkan bahwa hal itu bisa dilakukan. Noiseless Coding Theorem mengajarkan kita bahwa sumber informasi bisa dikodekan sedemikian efisien sehingga panjang codeword rata-rata menjadi kecil, hingga mendekati atau sama dengan nilai entropy dari informasi tersebut.  Namun teori ini tidak memperhitungkan adanya error* dalam transmisi SMS dari pengirim ke penerima.

Error dalam transmisi data bisa terjadi karena berbagai sumber, seperti: ketidaksempurnaan hardware, random noise, interferensi, efek channel fading, dan lain sebagainya. Ada beberapa skema yang bisa kita lakukan untuk mengatasi error yang tidak bisa dielakkan tersebut:

  1. mengirim ulang informasi yang error, biasa kita sebut dengan teknik Automatic Repeat reQuest (ARQ).
    Teknik ini sangat sederhana dalam implementasi karena tidak diperlukan perhitungan decoding yang kompleks; si penerima cukup hanya mendeteksi error lalu meminta si pengirim untuk mengirim ulang informasi yang error. Error sangat mungkin bisa dideteksi oleh si penerima walaupun si penerima tidak mengetahui data sebenarnya yang dikirim, salah satu caranya dengan menggunakan Cyclic Redundancy Check (CRC).
  2. Forward Error Correction (FEC).
    Skema ARQ dalam prakteknya, untuk beberapa aplikasi, tidak tepat untuk diaplikasikan. Misalnya dalam sistem broadcasting yang real-time, delay propagasi akibat retransmission tidak dapat ditolerir. Selain itu pula, banyaknya retransmisi menyebabkan berkurangnya throughput. Maka untuk mengatasi masalah ini, kita bisa menggunakan skema FEC. FEC tidak hanya dapat mendeteksi error, tetapi juga bisa mengkoreksi error.
  3. Hybrid ARQ (HARQ).
    Teknik ini merupakan penggabungan antara ARQ dan FEC.

Ketiga skema diatas biasa juga kita sebut dengan skema error control coding. Artikel ini sementara mengabaikan penggunaan CRC (tanpa ARQ).

Bayangkan jika kita mengirimkan 1 bit data yaitu 0, lalu ,dikarenakan error di kanal, si penerima mendapatkan bit 1. Si penerima tidak dapat mengetahui apakah data yang diterimanya benar atau tidak. Maka kita memerlukan suatu indikator atau codeword agar si penerima bisa mendeteksi bahkan mengkoreksi error tersebut. Cara termudah untuk melakukan ini adalah dengan mengirimkan data yang diulang sebanyak n kali dalam satu kali transmisi. Misalkan n = 3, sehingga kita dapatkan codeword untuk bit 0 adalah c_0 = (000) dan codeword untuk bit 1 adalah c_1 = (111). Jika penerima mendapatkan data y = (001), sedangkan y hanya berbeda 1 bit dengan c_0 dibandingkan dengan c_1 yang berbeda 2 bit, maka si penerima dengan segera bisa mengetahui bahwa data yang dikirim adalah 0. Contoh ini menunjukkan kemampuan dari repetition code untuk mendeteksi dan mengkoreksi error.

Shannon’s Theorem dan Kapasitas Kanal

Noisy (channel) encoding tidak terlepas dari penambahan redundant atau parity pada data yang dikirim agar si penerima dapat mendeteksi dan mengkoreksi error, seperti pada contoh di atas. Semakin besar jumlah redundant, peluang mengkoreksi error akan semakin besar. Jika panjang data adalah k dan panjang codeword adalah n, maka coding rate dinyatakan dalam R = k/n. Contoh kasus di atas memiliki coding rate R = 1/3. Pertanyaannya, seberapa kecil peluang terjadinya error jika kita menggunakan coding dengan rate R ?

Shannon dalam paper legendarisnya di tahun 1948 menyatakan bahwa : “Dengan menggunakan error correction code dengan panjang yang cukup, kita bisa mendapatkan peluang error yang kecil, jika code rate lebih kecil dari kapasitas kanal”. Kapasitas kanal, C, didefinisikan sebagai jumlah bit maksimum per satuan waktu yang dapat ditransmisikan tanpa error, atau dirumuskan dengan persamaan sebagai berikut:

C = B \, log_2(1 + SNR),

dimana B adalah bandwidth kanal, dan SNR adalah perbandingan power antara sinyal dan noise.
Dengan kata lain, Shannon menyatakan bahwa tidak akan ada suatu skema (error correction) encoding yang menjamin transmisi tanpa error jika bit informasi ditransmisikan dengan besar rate melebihi kapasitas kanal. Encoding itu ada jika coding rate lebih kecil dari kapasitas kanal.

Shannon Limit

Kita tahu bahwa SNR adalah perbandingan antara power sinyal dan power noise atau : SNR = P/N. Power sinyal dapat diformulasikan dengan: P = R\,E_b, dimana E_b adalah besarnya energi per bit informasi. Sedangkan noise power didefinisikan sebagai berikut: N = B N_0, dimana N_0 adalah double-sided noise spectral density. Maka rate maksimum yang bisa kita dapatkan adalah

R_{max} \leq C = B \, log_2(1 + \frac{R_{max}E_b}{N})

Lebih lanjut, persamaan di atas dapat dimodifikasi menjadi

\frac{R_{max}}{B} \leq log_2(1 + \frac{R_{max}E_b}{B\,N_0})

2^{\frac{R_{max}}{B}} \leq 1 + \frac{R_{max}E_b}{B\,N_0}

\frac{E_b}{N_0} \geq \frac{2^{\frac{R_{max}}{B}}}{\frac{R_{max}}{B}}

Jika kita tertarik pada rate informasi maximum per-Hz, maka kita bisa sederhanakan \frac{R_{max}}{B}  menjadi R_{max}. Sehingga persamaan diatas menjadi

\frac{E_b}{N_0} \geq \frac{2^{R_{max}}-1}{R_{max}}

Kita sudah pelajari bahwa semakin besar parity atau redundan maka informasi yang dikirim akan semakin terlindungi dari error akibat noise di kanal. Memperbesar parity atau redundan artinya kita memperkecil coding rate (n berbanding terbalik dengan R). Sehingga untuk parity yang banyak tak terhingga maka akan kita dapatkan R_{max} = 0. Untuk kasus ini,

  \frac{E_b}{N_0} \geq lim_{R_{max}\to 0}\frac{2^{R_{max}}-1}{R_{max}}

\frac{E_b}{N_0} \geq ln \, 2 .  (Bisa cek di sini)

atau,  \frac{E_b}{N_0} \geq -1.59 \, dB

Jadi, -1.59 dB adalah batas minimum E_b/N_0  agar komunikasi bisa berjalan dengan lancar.


*Error disini didefinisikan sebagai ketidaksamaan informasi yang diterima dengan yang dikirim.

Advertisements

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