Network Coding

Network coding merupakan suatu bagian disiplin ilmu jaringan (networking) dan teori informasi (information theory), dimana ilmu ini mempelajari manipulasi data dalam suatu kerangka jaringan (network) guna (diantaranya) meningkatkan throughput dan sifat robust dari suatu data. Teori ini pertama kali diperkenalkan oleh Rudolf Ahlswede pada tahun 2000 dalam papernya untuk IEEE Transactions on Information Theory yang berjudul Network Information Flow, terinspirasi dari aplikasi jaringan komputer.

Dalam jaringan komputer, kita mengetahui bahwa paket data dari suatu node dapat dikirim multicast ke beberapa node dengan bantuan intermediate node (router) yang bertugas mereplika dan meneruskan paket data ke node yang dituju tanpa mengubah isi dari data tersebut. Namun, dalam komunikasi jaringan (network communication), akan kita dapati bahwa mereplika dan merutekan informasi tidaklah cukup. Sebagai contoh:

perhatikan struktur Butterfly Network di atas. Source S mengirim informasi bit \{ b_{1}, b_{2} \} untuk node D_1 dan D_2. Node 1, 2, 3, dan 4 berfungsi sebagai intermediate node. Kemudian tanpa menghilangkan generalisasi, S secara simetris mentransmit b_1 ke node 1 dan b_2 ke node 2. Gambar 1(a) mengilustrasikan bagaimana aliran bit yang terkirim dalam jaringan. Node 3 menerima b_1 dan b_2 masing-masing dari node 1 dan node 2. Dari dua informasi tersebut, dikarenakan output channel dari node 3 hanya ada 1, maka node 3 harus memilih salah satu diantara bit tersebut untuk diteruskan ke node 4. Pada kasus ini kita memilih b_1, sehingga node 4 mereplika dan kemudian mentransmit b_1 ke node D_1 dan D_2. Node D_2 mendapatkan semua informasi, sedangkan node D_1 hanya memperoleh informasi b_1 baik dari node 1 maupun dari node 4. Artinya metode ini tidak bisa digunakan untuk aliran informasi di dalam jaringan.

Node 3 bisa saja mengirimkan \{ b_{1}, b_2 \} ke node 4 dengan menaikkan kapasitas channel, seperti yang diilustrasikan pada Gambar 1(b). Artinya kita memperbesar power sinyal atau dengan menambah bandwidth. Tentunya ini sangat merugikan dan tidak elegan.

Network coding bisa mengatasi permasalahan ini dengan menggunakan operator “+” atau penjumlahan modulo 2 pada node 3, seperti yang diilustrasikan paga Gambar 1(c). Node 4 mereplika dan mengirim codeword tadi ke node tujuan: D_1 dan D_2. Node D_1 bisa dengan mudah mendapatkan informasi b_2 dengan cara menggunakan operasi penjumlahan: b_1 + ( b_1 + b_2 ) = (b_1 + b_1) + b_2 = 0 + b_2 = b_2 . Dengan cara yang sama, node 2 dapat memperoleh informasi b_1. Disini kita bisa menghemat bandwidth dan pada saat yang sama memperbesar throughput.

Struktur jaringan di atas, dengan sedikit modifikasi akan kita dapatkan topologi jaringan sebagai berikut:

Nc-2multicast

Bit b_1 dibangkitkan oleh node 1 dan b_2 dibangkitkan oleh node 2. Dua multicast dalam jaringan dengan tujuan yang sama yaitu D_1 dan D_2. Jika D_1 atau D_2 memiliki bit dari node 1 maka ia bisa memastikan bit data yang berasal dari node 2, dengan menggunakan operasi yang telah dijelaskan di atas. Begitu pula sebaliknya, jika D_1 atau D_2 memiliki bit dari node 2 maka ia bisa memastikan bit data yang berasal dari node 2 dengan menggunakan operasi yang sama.

Apabila kita gabungkan node 1 dengan D_1 menjadi t_{1}^{'} serta node 2 dengan D_2 menjadi t_{2}^{'} seperti gambar berikut:

Nc-2unicast

kita dapatkan struktur unicast, dimana node t_{1}^{'} dan t_{2}^{'} bertukar informasi dalam jaringan. Jika tidak ada network coding, pada saat node t_{1}^{'} dan t_{2}^{'} mengirimkan informasi bersamaan, maka dibutuhkan kapasitas channel yang besar untuk node 3 dan 4. Maka disinilah perlunya network coding dalam proses routing saat terjadi multiple unicast dalam jaringan.

Perlindungan Dokumen Berharga

secure your documents

Musibah kebakaran, banjir, pencurian sering kita lihat/dengar di media massa. Sebuah nyawa tentu sangat berharga untuk diselamatkan saat musibah itu terjadi. Yang tidak kalah pentingnya adalah dokumen-dokumen berharga seperti : sertifikat tanah, rumah, buku nikah, KTP, SIM, STNK, ijazah, dan lain sebagainya. Semua dokumen tersebut diakui keabsahannya secara fisik, namun tidak ada salahnya kita menyimpan tanda bukti dalam bentuk digital yang suatu saat bisa kita cetak untuk mendapatkan bentuk fisiknya. Bahkan tidak menutup kemungkinan di masa yang akan datang dengan didukung kemajuan teknologi dalam bidang security, dokumen digital dapat diakui keabsahannya.

Mau tau cara mengamankannya? klik disini ;)

Shortcut in 1 Do

Aplikasi Gnome-do (sekarang namanya menjadi Do) ,merupakan killer application bagi saya, memungkinkan kita untuk melakukan berbagai hal dengan sangat mudah dan cepat, seperti melakukan sesuatu dengan shortcut. Beberapa fitur atau plugin yang ada pada Do diantaranya : microblogging (twitter atau identi.ca), del.icio.us tag search, file&folder search, chat dan IM ID search untuk pidgin, music playing, remind me, search favorite video pada youtube, google search, google contact, google calendar, dan lain sebagainya. Cukup panggil aplikasi dengan tombol win+space lalu ketikkan keyword lalu akan muncul opsi apa yang akan dilakukan dengan keyword itu, biasanya Do otomatis mengenali apa yang harus dilakukan, jika tidak maka kita harus memilih opsi di layar sebelah kanannya cukup dengan tombol tab dan tombol panah atas bawah. Berikutnya Do akan otomatis mengenali apa yang harus dilakukan. Hehehe susah dijelaskan hanya dengan kata-kata. Lebih baik dicoba. Untuk menginstall nya di ubuntu cukup dengan ketik

sudo apt-get install gnome-do

pada terminal. Atau silahkan download dari website nya (klik gambar logo Do diatas). Seperti pada tagline website nya :

Seeing is believing

Icip Ubuntu 10.04 (Lucid Lynx)

Pada dasarnya penggunaan unix-like akan lebih menyenangkan jika kita terhubung dalam jaringan internet, karena beberapa aplikasi bisa diinstal langsung dari dunia maya. Cukup dengan ketik ini pada terminal :

sudo apt-get install abcd

dengan abcd adalah nama dari aplikasi yang akan di-install.  Atau bisa juga dari Applications > Ubuntu Software Center , lalu cari aplikasi yang kita inginkan. Sebenarnya unix atau unix-like OS sangat powerful dengan command line interface (CLI). Tapi karena pengguna windows cukup terbiasa dengan tampilan GUI, maka ga ada salahnya kita coba beberapa aplikasi menarik dan bisa diakses dengan GUI. Kali ini kita akan coba beberapa fitur dan aplikasi di Ubuntu 10.04 sepanjang yang saya ketahui dan saya suka :p. Mau tau? Klik ini dong..

WUBI: Cara Aman Icip-icip Ubuntu dari Windows

Ada beberapa Free OS yang basisnya adalah unix atau mirip unix (unix-like) dengan berbagai distro, salah satunya adalah Ubuntu. Karena tak kenal maka tak sayang, maka mari kita berkenalan dengan terlibat langsung pake Ubuntunya. Kali ini saya coba jelaskan cara aman meng-install Ubuntu pada PC atau laptop yang sudah ada OS windows nya.

Seperti tagline pada official website nya : Wubi is an officially supported Ubuntu installer for Windows users that can bring you to the Linux world with a single click. Wubi allows you to install and uninstall Ubuntu as any other Windows application, in a simple and safe way. Intinya kita bisa menginstall Ubuntu dari windows semudah menginstall aplikasi pada windows. Tanpa menggunakan virtual machine. Jika kita ingin menghapus ubuntu nya cukup dengan me-remove nya dari control panel. Sehingga cukup aman, tidak mengganggu file dan OS yang sudah ada. Saat booting pun masih bisa masuk ke windows.

Ok, sekarang saya coba urutkan langkah-langkah peng-install-an (menginstall ubuntu 10.04) :

  1. Siapkan wubi.exe dan image (iso file) ubuntu nya.
    Kedua file ini bisa diambil di site resminya, atau gampangnya gugling aja :p. Kalau kita punya koneksi internet yang mumpuni, sebenarnya file wubi.exe saja cukup, selebihnya wubi akan menarik file installer dari internet. Tapi untuk kasus ini kita gunakan dua-dua nya saja.
    Mau tau langkah selanjutnya ? Klik sini dong.. :)

Ilustrasi ISI-bagian 2

Postingan sebelumnya menggambarkan terjadinya Inter-symbol Interference(ISI) dalam suatu ilustrasi sederhana. Kali ini akan saya jelaskan ilustrasi sederhana lainnya menggunakan rumusan sederhana dari transmit signal itu sendiri.

Jika kita mengirimkan sinyal \textbf{s} dan channel impulse response yang diderita sinyal kita sebut \textbf{H}, maka disisi penerima akan kita peroleh sinyal \textbf{y} = \textbf{H} \ast \textbf{s}

Berikut adalah ilustrasi dari 3 blok* sinyal dengan 3 jenis respon kanal, dan hasil konvolusinya (bisa direpresentasikan dalam perkalian matriks) tanpa menggunakan guard interval:

Konvolusi

Daerah kosong pada matriks \textbf{H} adalah zeros (tidak ditampilkan/ditulis). A_{t-1} menunjukkan nilai A pada saat t-1.

Daerah yang diarsir gelap pada matriks hasil konvolusi adalah blok sinyal yang kita inginkan (blok sinyal biru). Dari ilustrasi tersebut terlihat bahwa pada bagian ini terdapat interferensi yang tidak dapat dihindari, berasal dari sinyal blok sebelumnya(berwarna merah) dan blok setelahnya(berwarna hijau).

*term blok digunakan pada sistem single carrier, sehingga ilustrasi diatas lebih tepat disebut Inter-Block Interference. Akan tetapi kasus yang sama bisa pula berlaku untuk symbol pada multicarrier. Artinya 1 blok disana bisa dianalogikan dengan 1 symbol OFDM

Ilustrasi Inter-symbol Interference(ISI)

Inter-symbol Interferense (ISI) adalah permasalahan yang tidak dapat dihindari dalam sistem komunikasi wireless. Setiap sinyal yang ditransmit akan mengalami multipath, sehingga receiver akan menerima sinyal yang notabene merupakan hasil akumulasi dari message yang sama yang terdelay dan dengan power yang bervariasi.

Berikut adalah ilustrasi mengenai multipath :

Multipath

Base station memancarkan satu frame data. Receiver menerima beberapa sinyal yang datang bersamaan dimana setiap sinyalnya berisikan message yang sama.

ISI

Ilustrasi diatas menunjukkan apa yang terjadi pada sisi penerima. Setiap frame yang diterima di sisi penerima mengalami waktu kedatangan yang berbeda (delay) dan power yang berbeda (bisa dilihat dari tinggi tiap frame yang berbeda). Asumsi synchronizer pada sisi penerima sempurna mendapatkan awal frame dimulai dari awal frame merah.

Setiap frame terdiri dari beberapa simbol. Ilustrasi diatas menunjukkan ada 2 simbol dalam 1 frame. Karena semua frame berisikan message yang sama, maka akumulasi simbol pada waktu yang sama tidak menghilangkan informasi/data pada simbol tersebut. Garis putus-putus pada ilustrasi diatas menunjukkan batas dari simbol pertama. Bisa kita lihat adanya akumulasi simbol pertama dan simbol kedua, dimulai dari frame ungu. Sebagian simbol pertama frame ungu akan terakumulasi dengan simbol kedua frame merah. Begitu pula pada frame hijau, dan seterusnya. Kondisi inilah kita sebut dengan inter-symbol interference (ISI).

Relation between SNR and Eb/No (part 2)

Usually we found in papers or other written sources of data transmission performance in telecommunication system with BER vs Eb/No. Then there is also with BER vs SNR. So which one that we should use?

Actually we can use all of them. It’s depend on our purpose. Eb/No is often used when we want to know how far the performance from the shannon limit boundary. SNR is used when we just want to know the overall signal power, doesn’t care about: how big the bit energy, how far the performance from the shannon limit boundary, using guard interval or not.

Following are the conversion from SNR to Eb/No or vice versa:
\frac{S}{N} = \frac{Eb}{No} \, R \, M \, \frac{1}{J} \, G

\frac{S}{N} [dB] = \frac{Eb}{No} [dB] + 10 log10(R) + 10 log10(M) + 10 log10 (\frac{1}{J}) + 10 log10(G)

where :
R = bit rate
M = number of bits in each constellation symbol
J = sampling rate
G = guard interval ratio.