Tugas Adaptive Huffman Coding, Arithmetic coding, QAM dan GMSK

Adaptive Huffman Coding pertama kali dikembangkan oleh Faller dan Gallager, kemudian mendapatkan perbaikan oleh Donald Knuth. Sebuah metode lain dikembangkan oleh J.S. Vitter.File yang ter-enkodekan secara dinamis punya dampak besar bagi keefektifan pohon sebagai encoder dan decoder. Adaptive Huffman Coding lebih efektif dari Huffman Coding karena pohon terus berevolusi. Pada Huffman Coding yang static, karakter yang berfrekuensi rendah akan ditempatkan jauh di posisi bawah, dan akan memakan banyak bits untuk encode. Pada Adaptive Huffman Coding, karakter itu akan dimasukkan pada daun tertinggi untuk didekodekan, sebelum akhirnya didorong ke bawah pohon oleh karakter berfrekuensi yang lebih besar. Kuncinya adalah property “sibling” yang mengatakan : Setiap simpul (kecuali akar) mempunyai sibling (saudara) dan setiap simpul dapat diurutkan dengan urutan “tidak bertambah berat”, dengan setiap simpul berdampingan dengan saudaranya” Adaptive coding adalah metoda yang secara dinamis meng-update dua Huffman tree identik di Encoder dan Decoder (didasarkan pada informasi text yg sudah dikirim sampai saat ini). Adaptive Huffman Coding merupakan Suatu binary tree dimana node-nya mempunyai counter frekuensi (kemunculan) memiliki sibling property jika tiap node (kecuali root) saat scanning (breadth-first-right-to-left tree) membangkitkan list dari node-node yg mempunyai harga counter frekuensi yg tidak meningkat. 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%

Pada adaptive Huffman coding : 

1. Tree mencakup counter utk tiap simbol, dan suatu counter di-update setiap input simbol yg sesuai dikodekan.
2. Memeriksa apakah sibling property dipertahankan menjamin Huffman tree yg sedang dibangun tetap Huffman tree.
3. Jika sibling property dilanggar, tree harus direstrukturisasi utk mengembalikan property ini.
4. Algoritma memp. link list nodes berisi node-node dari tree diurut berdasarkan scanning breadth-first-right-to-left tree.
5. Blocki adalah bagian dari list dimana tiap node memp. frekuensi i, dan node pertama dari tiap block disebut leader.
6. Metode SHC mengharuskan kita mengetahui terlebih dahulu frekuensi masing-masing karakter sebelum dilakukan proses pengkodean. 
7. Metode AHC merupakan pengembangan dari SHC dimana proses penghitungan frekuensi karakter dan pembuatan pohon Huffman dibuat secara dinamis pada saat membaca data.
8. Algoritma Huffman tepat bila dipergunakan pada informasi yang bersifat statis. Sedangkan untuk multimedia application, dimana data yang akan datang belum dapat dipastikan kedatangannya (audio dan video streaming), algoritma Adaptive Huffman dapat dipergunakan.
9. Metode SHC maupun AHC merupakan kompresi yang bersifat loseless.

Arithmetic coding adalah salah satu metode kompresi lossless yang memakai teknik statistical modeling yang mengkodekan suatu barisan karakter/pesan dengan floating .Berdasarkan pemodelannya arithmetic coding dibagi menjadi 2, yaitu model statis dan dinamis, Arithmetic coding adalah suatu algoritma kompresi data yang merupakan pengembangan dari huffman coding, bekerja berdasarkan statistik data, yang dalam hal ini diterapkan pada block entropy encoder dari perancangan sistem. Arithmetic coding adalah metoda kompresi model statistic yang paling baik jika dibandingkan dengan metoda kompresi statistic model lainnya. Arithmetic coding menggantikan satu deretan simbol input dengan sebuah bilangan floating point. Semakin panjang dan semkin kompleks pesan yang dikodekan, semakin banyak bit diperlukan untuk keperluan tersebut. Berdasarkan hasil simulasi sistem, bahwa arithmetic coding baik digunakan untuk kompresi data teks.

Prinsip dari arithmetic coding adalah arithmetic coding menggantikan satu deretan simbol input dengan sebuah bilangan floating point. Semakin panjang dan semakin kompleks pesan yang dikodekan, semakin banyak bit yang diperlukan untuk keperluan tersebut. Output dari arithmetic coding ini adalah satu angka yang lebih kecil dari 1 dan lebih besar atau sama dengan 0. Angka ini secara unik dapat di-decode sehingga menghasilkan deretan simbol yang dipakai untuk menghasilkan angka tersebut. Untuk menghasilkan angka output tersebut, tiap symbol yang akan di-encode diberi satu set nilai probabilitas. Gagasan utama pada arithmetic coding adalah memberikan setiap simbol sebuah range atau interval. Dimulai dengan range [0..1), setiap range dibagi dalam beberapa subrange, dimana ukurannya sebanding dengan probabilitas (kemungkinan yang muncul dari simbol-simbol yang sama). Semakin tinggi probabilitas yang dimiliki oleh suatu simbol, semakin tinggi pula range yang diberikan terhadap simbol tersebut. Tanda”[..)“ berarti bahwa angka yang didalamnya diikutsertakan kecuali angka terakhir Dari setiap simbol dicari rangenya. Dari range simbol pertama sudah diketahui range untuk output number yang dibatasi oleh low number dan high number. Yang terjadi berikutnya selama proses encoding yaitu bahwa setiap simbol baru untuk diencode lebih lanjut akan membatasi range dari output angka. Simbol kedua dan selanjutnya akan memiliki low number dan high number yang berada dalam range simbol sebelumnya.

Setelah mengetahui pola encoding tersebut, maka dengan mudah dapat dilihat bagaimana proses decoding bekerja. Dalam proses decoding ini pertama-tama temukan simbol pertama yaitu dengan melihat output angka dari proses encoding itu jatuh pada range simbol mana. Kemudian yang harus dilakukan yaitu mengeluarkan simbol yang telah ter-encode dengan cara membalikkan proses yang menempatkannya. Pertama, dengan mengurangi high number dan low number yang dimiliki simbol tersebut untuk mendapatkan rangenya. Selanjutnya mengurangi output angka encoding angka terendah simbol tersebut, lalu hasilnya untuk kemudian membagi angka tersebut dengan range yang sebelumnya pernah didapat. Lalu hasil dari perhitungan terakhir digunakan untuk memperhitungkan angka tersebut jatuh pada range simbol mana, dan didapatkan symbol berikutnya, demikian selanjutnya dilakukan sampai selesai.

Perancangan Proses Program Kompresi Arithmetic Coding

Dalam proses kompresi, file yang akan dikompresi tidak dapat langsung diubah ke dalam bentuk kode-kode tetapi harus melalui beberapa proses. Pada kompresi arithmetic coding ini, pengubahan file yang akan dikompres meliputi tiga proses utama, yaitu :

1. Penghitungan probabilitas tiap karakter simbol dan inisialisasi Pada proses ini dilakukan pembacaan terhadap file yang akan dikompresi. Kemudian dilakukan perhitungan probabilitas jumlah tiap karakter simbol yang ditampung dalam suatu array. Inisialisasi dilakukan terhadap variabel-variabel yang dibutuhkan dalam perhitungan selanjutnya dalam proses encoding simbol.
2. Perhitungan tiap karakter dari file dan pembuatan kode Pada proses ini dilakukan pembacaan tiap karakter atau pixel, mengkonversikannya ke dalam bentuk simbol, dan kemudian dilakukan proses encoding symbol sehingga didapatkan kode-kode hasil kompresi.
3. Pengubahan file ke dalam kode dan pembuatan file archive File kompresi yang telah didapatkan selanjutnya akan diperiksa apakah ukuran file hasil kompresi lebih besar atau lebih kecil dari ukuran file aslinya. Jika ukuran hasil kompresi lebih besar dari ukuran aslinya maka file akan langsung disimpan, tidak dikompresi. Dan jika sebaliknya maka file kompresi tersebut akan dituliskan ke dalam file archive.

Quadrature amplitude modulation (QAM) adalah sebuah skema modulasi yang membawa data dengan mengubah (memodulasi) amplitudo dari dua gelombang pembawa. Kedua gelombang tersebut, biasanya sinusoid, berbeda fase dengan yang lainnya sebesar 90 ° dan oleh karena itu disebut pembawa-quadrature. Seperti skema modulasi lainnya, QAM membawa data dengan mengubah beberapa aspek dari sinyal pembawa, atau gelombang pembawa (biasanya sinusoid). Dalam kasus QAM, amplitudo dari dua gelombang, saling berbeda fase sebesar 90 derajat diubah (dimodulasi) untuk mewakili sinyal data.

GMSK (Gaussian Minimum Shift Keying) adalah salah satu teknik modulasi yang melewatkan sinyal informasi pada Gaussian Low-Pass Filter sebelum proses modulasi sinyal menggunakan modulator MSK (Frequency (Continuous Phase Shift Keying), di mana deviasi frekuensi puncaknya sama dengan ½ bit rate. Dengan kata lain MSK adalah CPFSK dengan indeks modulasi sama dengan 0.5. GMSK (Gaussian Minimum Shift Keying). Teknik ini bekerja dengan melewatkan data yang akan dimodulasikan melalui Filter Gaussian. Filter ini menghilangkan sinyal-sinyal harmonik dari gelombang pulsa data dan menghasilkan bentuk yang lebih bulat pada ujung-ujungnya. Jika hasil ini diaplikasikan pada modulator fasa, hasil yang didapat adalah bentuk envelope yang termodifikasi (ada sinyal pembawa). Bandwidth envelope ini lebih sempit dibandingkan dengan data yang tidak dilewatkan pada filter gaussian.

Sumber : Wikipedia