Dalam artikel ini saya akan menjelaskan sedikit mengenai encoding, informasi tentang encoding ini saya dapatkan dan saya kumpulkan melewati beberapa informasi yang ada di internet. Nah selajutnya kita bahas mengenai encoding, berikut pembahasannya.
Coding atau Encoding sering kita jumpai dan kita dengar dalam bahasa computer, banyak orang ketika ditanya tetang Coding, ada yang tau dan ada yang tidak. Sebenarnya apa itu Coding atau Encoding? Dalam bahasa Indonesia Coding atau Encoding dapat di artikan “menyandi” atau “persandian”. Jadi dapat disimpulkan Ecoding atau Coding adalah sandi yang digunakan dalam ilmu computer.sandi yang di maksud berupa sandi digital.
Dalam ilmu komunikasi kita menamai tindakan menghasilkan pesan (misalnya, berbicara atau menulis) sebagai encoding. Dengan menuangkan gagasan-gagasan kita ke dalam gelombang suara atau ke atas selembar kertas, kita menjelmakan gagasan-gagasan tadi ke dalam kode tertentu. Jadi, kita melakukan enkoding.
Kita menamai tindakan menerima pesan (misalnya, mendengarkan atau membaca) sebagai decoding. Dengan menerjemahkan gelombang suara atau kata-kata di atas kertas menjadi gagasan, anda menguraikan kode tadi. Jadi, anda melakukan dekoding.
Oleh karenanya kita menamai pembicara atau penulis sebagai encoder, dan pendengar atau pembaca sebagai decoder. Seperti halnya sumber-penerima, kita menuliskan enkoding-dekoding sebagai satu kesatuan yang tak terpisahkan untuk menegaskan bahwa anda menjalankan fungsi-fungsi ini secara simultan. Ketika anda berbicara (enkoding), anda juga menyerap tanggapan dari pendengar (dekoding).
Dasar teori
Pandangan dasar dari source coding adalah menghilangkan redundansi dari sumber. Source Coding menghasilkan data compresi dan mengurangi rate dari transmisi. Pengurangan dari rate transmisi dapat mengurangi biaya dari sambungan dan memberikan kemungkinan untuk pengguna berbagi dalam sambungan yang sama. Secara umum kita dapat meng-kompres data tanpa menghilangkan informasi (lossless source coding) atau mengkompress data dengan adanya kehilangan informasi (loss source coding). Teori Source Encoding merupakan salah satu dari ketiga teorema dasar dari teori informasi yang diperkenalkan oleh Shannon (1948). Teori Source Encoding mencanangkan sebuah limit dasar dari sebuah ukuran dimana keluaran dari sebuah sumber informasi dapat dikompresi tanpa menyebabkan probabilitas error yang besar. Kita telah mengetahui bahwa entropy dari sebuah sumber informasi merupakan sebuah ukuran dari isi informasi pada sebuah sumber. Sehingga, dari pendapat teori source encoding bahwa entropy dari sebuah sumber sangat penting. 
Efisiensi dari sumber ditentukan oleh H(X)/H(X)max, dimana pi merupakan probabilitas pada simbol ke-I, dan H(X) maksimum ketika sumber mempunyai symbol probabilitas yang sama. Teori Shannon Noiseless Source Coding menyatakan bahwa nilai rata-rata dari symbol biner per keluaran sumber dapat digunakan untuk mendekati entropi dari sumber. Dalam kata lain, efisiensi dari sumber dapat dihasilkan dari source coding. Untuk sumber dengan probabilitas simbol yang sama, dan/atau secara statistic tidak terikat satu dengan yang lain, maka dapat dipetakan (encode) setiap simbol dalam sebuah codeword dengan panjang n. Dalam makalah ini akan dibahas dan dianalisa source encoding berdasarkan
model matematis dari sumber informasi dan pengukuran kuantitatif dari informasi yang dihasilkan oleh sumber.
Algoritma Huffman Coding
Dalam Huffman Coding, panjang blok dari keluaran sumber dipetakan dalam blok biner berdasarkan pajang variable. Cara seperti ini disebut sebagai fixed to variable-length coding. Ide dasar dari cara Huffman ini adalah memetakan mulai simbol yang paling banyak terdapat pada sebuah urutan sumber sampai dengan yang jarring muncul menjadi urutan biner. Dalam variable-length coding, sinkronisasi merupakan suatu masalah. Ini berarti harus terdapat satu cara untuk memecahkan urutan biner yang diterima kedalam suatu codeword. Seperti yang disebutkan diatas, bahwa ide dari Huffman Coding adalam memilih
panjang codeword dari yang paling besar probabilitasnya sampai dengan urutan codeword yang paling kecil probabilitasnya. Apabila kita dapat memetakan setiap keluaran sumber dari probabiltas pi ke sebuah codewortd dengan panjang 1/pi dan pada saat yang bersamaan dapat memastikan bahwa dapat didekodekan secara unik, kita dapat mecari rata-rata panjang kode H(x). Huffman Code dapat mendekodekan secara unik dengan H(x) minimum, dan optimum pada keunikan dari kode-kode tersebut.
Algoritma dari Huffman encoding adalah :
1. Pengurutan keluaran sumber dimulai dari probabilitas paling tinggi.
2. Menggabungkan 2 keluaran yang sama dekat kedalam satu keluaran yang probabilitasnya merupakan jumlah dari probabilitas sebelumnya.
3. Apabila setelah dibagi masih terdapat 2 keluaran, maka lanjut kelangkah berikutnya, namun apabila masih terdapat lebih dari 2, kembali ke langkah 1.
4. Memberikan nilai 0 dan 1 untuk kedua keluaran.
5. Apabila sebuah keluaran merupakan hasil dari penggabungan 2 keluaran dari langkah sebelumnya, maka berikan tanda 0 dan 1 untuk codeword-nya,
ulangi sampai keluaran merupakan satu keluaran yang berdiri sendiri.
Contoh
Apabila kita mempunyai kalimat:
"EXAMPLE OF HUFFMAN CODE"
Pertama, kita kalkulasi probabilitas dari setiap simbol :
Symbol | Probability |
E | 2/25 |
X | 1/25 |
A | 2/25 |
M | 2/25 |
P | 1/25 |
L | 1/25 |
O | 2/25 |
F | 2/25 |
H | 1/25 |
U | 1/25 |
C | 1/25 |
D | 1/25 |
I | 1/25 |
N | 2/25 |
G | 1/25 |
Space | 3/25 |
Huffman Tree dari kalimat tersebut adalah :
Algoritma Shannon-Fano Encoding
Teknik coding Shannon Fano merupakan salah satu algoritma pertama yang tujuannya adalah membuat code word dengan redundansi minimum. Ide dasar dari membuat code word dengan variable-code length, seperti Huffman codes, yang ditemukan beberapa tahun kemudian. Seperti yang disebutkan di atas, Shannon Fano coding didasarkan pada variable length-word, yang berarti beberapa simbol pada pesan (yang akan dikodekan) direpresentasikan dengan code word yang lebih pendek dari simbol yang ada di pesan. Semakin tinggi probabilitasnya, maka code word semakin pendek. Dalam memperkirakan panjang setiap codeword maka dapat ditentukan dari probabilitas setiap simbol yang direpresentasikan oleh codeword tersebut. Shannonm Fano coding menghasilkan codeword yang tidak sama panjang, sehingga kode tersebut bersifat unik dan dapat didekodekan. Cara efisien lainnya dalam variable-length coding adalah Shannon-Fano
encoding. Prosedur dalam Shannon-Fano encoding adalah:
1. Menyusun probabilitas simbol dari sumber dari yang paling tinggi ke yang paling rendah.
2. Membagi menjadi 2 bagian yang sama besar, dan memberikan nilai 0 untuk bagian atas dan 1 untuk bagian bawah.
3. Ulangi langkah ke 2, setiap pembagian dengan probabilitas yang sama sampai dengan tidak mungkin dibagi lagi
4. Encode setiap simbol asli dari sumber menjadi urutan biner yang dibangkitkan oleh setiap proses pembagian tersebut.
Contoh
Apabila kita mempunyai kalimat:
"EXAMPLE OF SHANNON FANO"
Pertama, kita kalkulasi probabilitas dari setiap simbol:
Symbol | Codewords |
E | 2/23 |
X | 1/23 |
A | 3/23 |
M | 1/23 |
P | 1/23 |
L | 1/23 |
O | 3/23 |
F | 2/23 |
S | 1/23 |
H | 1/23 |
N | 4/23 |
Space | 3/23 |
Coding tree dari contoh tersebut adalah :
Algoritma Adaptive Huffman Coding
Adaptive Huffman coding pertama kali diperkenalkan oleh Faller dan Gallager (Faller 1973; Gallaber 1978). Knuth memberikan kontribusi dengan peningkatan pada algoritmanya (Knuth 1985) dan menghasilkan algoritma yang dikenal dengan algoritma FGK. Versi terbaru dari adaptive Huffman Coding diperkenalkan oleh Vitter (Vitter 1987). Semua metode yang ditemukan merupakan skema define-word tabf menentukan mapping dari pesan sumber menjadi codeword didasari pada perkiraan probabilitas pesan sumber. Kode bersifat adaptive, berganti sesuai dengan perkiraan optimalnya pada saat itu. Dalam hal ini, Adaptive Huffman Code merespon lokalitas. Dalam pengertian, encoder mempelajari karakteristik dari sumber. Dekoder harus mempelajari bersamaan dengan encoder dengan selalu memperbaharui Huffman tree sehingga selalu sinkron dengan encoder. Keuntungan lain dari system ini adalah kebutuhan akan lewatnya data, data akan lewat hanya sekali (tanpa table statistic). Tentu saja, metode one-pass tidak akan menarik apabila jumlah bit yang ditransmisikan lebih besar dari metoda twopass. Namun, performa dari metode ini, dalam ruang lingkup jumlah bit yang ditransmisikan, dapat lebih baik daripada static Huffman coding. Permasalahan ini tidak kontradiktif dengan optimalisasi pada metode statis, karena metode ini optimal hanya [ada metode yang mengasumsikan mapping berdasarkan time-variant. Kinerja dari metode adaptive dapat lebih buruk daripada metode static. Metode adaptive Faller, Gallager dan Knuth merupakan dasar dari UNIX utility compact. Kinerja compact ini termasuk bagus, karen factor kompresinya mencapai 30-40% Dasar dari algoritma FGK adalah adanya sibling (factor turunan) property, didefinisikan oleh Gallager [Gallager 1978]: binary code tree mempunyai sibling apabila setiap node )kecuali root) mempunyai sebuah sibling dan apabila node-node tersebut dapat diurutkan dalam weight dengan setiap node berhubungan dengan siblingnya masing-masing. Gallager membuktikan bahwa sebuah code prefik biner merupakan Huffman code jika dan hanya jika code tree mempunyai sibling property. Dalam algoritma FGK, baik pengirim dan penerima menangani perubahan dinamis dari Huffman code tree. Daun dari setiap pohon Huffman code merepresentasikan pesan sumber dan berat dari setiap daun merepresentasikan hitungan frekuensi untuk setiap pesan. Pada titik manapun dalam satuan waktu, k dari kemungkinan n pesan sumber terdapat pada susunan pesan.
Pada awalnya, the code tree consists of a single leaf node, yang disebut 0- node. 0-node digunakan untuk menggambarkan pesan n-k yang tidak digunakan. Untuk setiap pesan yang ditransmisikan, kedua bagian harus menambahkan weight dan menghitung kembali code tree untuk mempertahankan simbling property. Pada titik dalam satuan waktu dimana t pesan telah ditransmisikan. Pada titik dimana t pesan telah ditransmisikan, k dari mereka berbeda, dan k < n, pohon merupakan Huffman tree asli dengan daun sebanyak k+1, 1 yaitu k pesan dan 0-node. Apabila pesan ke (t+1) adalah salah satu dari k, maka algoritma mentrasmisikan code ke a(t+1), menaikkan counter dan menghitung kembali pohon. Apabila terdapat pesan yang tidak digunakan, 0-node dipisah untuk membuat 2 pasang daun, satu untuk a(t+1), dan siblingnya adalah 0-node yang baru. Sekali lagi dalam proses ini, pohon diperhitungkan kembali. Dalam kasus ini, kode untuk 0-node dikirimkan; sebagai tambahan, penerima harus memberitahukan pesan n-k mana yang tidak digunakan
yang muncul. Pada setiap node, penyimpanan perhitngan dari pesan yang muncul dilakukan. Node diberikan nomor untuk mengindikasikan posisi mereka dalam urutan sibling propertinya. Pembaharuan dari pohon dapat dilakukan dalam sebuah single traversal dari node a(t+1) sampai dengan root-nya. Traversal ini harus meningkatkan perhitungan untuk node a(t+1) dan untuk setiap bagian atas dari node tersebut. Node boleh berubah untuk memelihara sibling property-nya, namun perubahan membutuhkan keterlibatan node pada path a(t+1) ke root-nya.
Terimakasih atas perhatiannya, semoga artikel ini bermanfaat bagi pembaca.
