IMPLEMENTASI ALGORITMA SHANNON-FANO PADA KOMPRESI AUDIO
SKRIPSI
MUTIARA NOVELIA RAJAGUKGUK 081402068
PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
IMPLEMENTASI ALGORITMA SHANNON-FANO PADA KOMPRESI AUDIO
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Teknologi Informasi
MUTIARA NOVELIA RAJAGUKGUK 081402068
PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
PERSETUJUAN
Judul
:
IMPLEMENTASI ALGORITMA SHANNONFANO PADA KOMPRESI AUDIO
Kategori
:
SKRIPSI
Nama
:
MUTIARA NOVELIA RAJAGUKGUK
Nomor Induk Mahasiswa
:
081402068
Program Studi
:
SARJANA (S1) TEKNOLOGI INFORMASI
Departemen
:
TEKNOLOGI INFORMASI
Fakultas
:
ILMU KOMPUTER DAN TEKNOLOGI INFORMASI (FASILKOM-TI) UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, 2014
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dedy Arisandi,ST.,M.Kom
M.Fadly Syahputra,B.Sc.,M.Sc.IT
NIP 19610817 198701 1 001
NIP 19830226 201012 2 003
Diketahui/Disetujui oleh Program Studi S1 Teknologi Informasi Ketua,
Prof. Dr. Opim Salim Sitompul, M.Sc. NIP196108171987011001
Universitas Sumatera Utara
PERNYATAAN
IMPLEMENTASI ALGORITMA SHANNON-FANO PADA KOMPRESI AUDIO
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, April 2014
Mutiara Novelia Rajagukguk 081402068
Universitas Sumatera Utara
UCAPAN TERIMA KASIH
Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa sehingga penulis dapat menyelesaikan skripsi ini sebagai syarat untuk memperoleh gelar Sarjana Teknologi Informasi, Program Studi S1 Teknologi Informasi Departemen Teknologi Informasi Universitas Sumatera Utara.
Ucapan terima kasih penulis sampaikan kepada kedua dosen pembimbing yaitu M.Fadly Syahputra,B.Sc.,M.Sc.IT dan Dedy Arisandi,ST.,M.Kom yang telah bersedia meluangkan waktunya untuk memberikan panduan dan masukan kepada penulis dalam menyelesaikan skripsi ini. Ucapan terima kasih juga ditujukan kepada Bapak Baihaqi Siregar, S.Si.M.T dan Bapak Drs. Sawaluddin, M.IT yang telah bersedia menjadi dosen pembanding. Ucapan terima kasih juga penulis tujukan kepada Ketua dan Sekretaris Program Studi Teknologi Informasi, Prof. Dr. Opim Salim Sitompul, M.Sc. dan Drs. Sawaluddin, M.IT, Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, semua dosen serta pegawai di Program Studi S1 Teknologi Informasi.
Skripsi ini penulis persembahkan kepada kedua orang tua penulis Ayah M. Rajagukguk dan Ibu K. L.Tobing dan juga kepada saudara saudara penulis yang senantiasa memberikan dukungan, doa dan semangat kepada penulis. Kepada Desfi Rahmadani, Ester Hannita, Fanny Devina, Ika Hasnita, Lia Hartati, Umi Hani, Fadhly Sani, Siska dan seluruh angkatan 08 serta teman-teman mahasiswa Teknologi Informasi penulis ucapkan banyak terima kasih atas doa dan dukungan yang telah diberikan.
Penulis menyadari bahwa masih terdapat banyak kekurangan dalam penyusunan skripsi ini. Karena itu penulis mengaharapkan saran-saran yang bersifat membangun dari semua pihak untuk kesempurnaan skripsi ini. Akhir kata penulis mengharapkan semoga skripsi ini dapat memberikan manfaat bagi semua pihak.
Universitas Sumatera Utara
ABSTRAK
Besarnya ukuran file audio membuat pengiriman data menjadi lama dan dapat menyebabkan pemborosan media penyimpanan. Oleh karena itu dilakukan kompresi untuk memadatkan isi file dengan cara menghilangkan berbagai redundansi dan menemukan sumber redundansi disetiap data sehingga ukuran audio menjadi lebih kecil. Salah satu metode kompresi adalah metode lossless yaitu metode kompresi dimana pada audio hasil kompresi dapat dikembalikan ke data semula tanpa menghilangkan informasi pada data. Penelitian ini menggunakan algoritma ShannonFano pada audio berjenis mp3 untuk melakukan kompresi dan memainkan kembali audio hasil kompresi. Algoritma Shannon-Fano merupakan algoritma metode lossless yang didasarkan pada variable-length code yang berarti beberapa karakter pada data yang dikodekan direpresentasikan dengan kode yang lebih pendek. Perbandingan antara ukuran audio hasil kompresi dan ukuran audio asli dihitung dengan menggunakan rumus rasio kompresi. Dari hasil pengujian proses kompresi didapat bahwa rasio kompresi untuk 20 file audio mempunyai range antara 25% untuk nilai terendah dan tertinggi 48.86% dengan hasil rata rata rasio kompresi sebesar 41.49% serta menunjukkan bahwa audio hasil kompresi dapat dimainkan kembali tanpa harus melakukan proses dekompresi. Kata kunci: kompresi, dekompresi, redundansi, metode lossless, Shannon-Fano, variable-length code, mp3.
Universitas Sumatera Utara
IMPLEMENTATION OF SHANNON-FANO ALGORITHM FOR AUDIO COMPRESSION
ABSTRACT
The large size of audio increasing time to transferring and also takes space for storage media. To solve this problem is used compression to compresss data for reducing size of audio which eliminating the redundancy in data and find the source of redundancy in each type of data. One of compression method is lossless method which reconstruct the original data from the compressed file without any loss of data. In this study Shannon-Fano algorithm is used for compressing mp3 audio and playing audio compress. Shannon-Fano algorithm is lossless method based on variable-length code where some characters in data encoding are represented by short code. Comparison of audio compress and original audio measured by compression ratio. The result of testing for 20 audio total show average compression ratio amounts 41.49%, range between 25% for low percentage and 48.86% for high percentage, it also show the audio compress can be playback without decompressing.
Keyword: kompresi, dekompresi, redundansi, metode lossless, Shannon-Fano, variable-length code, mp3.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Ucapan Terima Kasih Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii ix x
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan
1 1 2 3 3 3 4 5
Bab 2 Landasan Teori 2.1 Kompresi 2.1.1 Metode kompresi 2.1.2 Compression Ratio 2.1.3 Redundansi 2.2 Pengertian Audio 2.2.1 Representasi Audio Digital 2.2.2 Kelebihan Audio Digital 2.2.3 Sampling Rate 2.2.4 Bit per Sample 2.2.5 Bit Rate 2.2.6 MP3 (MPEG-1 Layer 3) 2.3 Penelitian Sebelumnya 2.4 Algoritma Shannon-Fano 2.5 Binary Tree
7 7 8 9 9 9 10 11 12 12 13 13 17 19 20
Bab 3 Analisis Dan Perancangan 3.1 Analisis Algoritma 3.1.1 Deskripsi Kompresi Algoritma Shannon-Fano 3.1.2 Deskripsi Dekompresi Algoritma Shannon-Fano 3.2 Perancangan Aplikasi 3.2.1 Usecase Diagram
28 28 30 31 31 32
Universitas Sumatera Utara
viii 3.2.2 Activity Diagram 3.2.3 Sequence Diagram 3.3 Perancangan Antarmuka 3.3.1 Menu Utama 3.3.2 Sub Menu Kompresi 3.3.3 Sub Menu Dekompresi 3.3.4 Sub Menu Play 3.3.5 Sub Menu Bantuan
34 37 39 39 40 40 41 42
Bab 4 Implementasi Dan Perancangan 4.1 Implementasi Perancangan Antarmuka Aplikasi 4.1.1 Tampilan Sub Menu Kompresi 4.1.2 Tampilan Sub Menu Dekompresi 4.1.3 Tampilan Sub Menu Play 4.1.4 Tampilan Sub Menu Bantuan 4.2 Pengujian Sistem 4.2.1 Skenario Pengujian 4.2.2 Analisis Data Hasil Pengujian 4.2.2.1 Analisis Kompresi Audio 4.2.2.2 Analisis Dekompresi Audio
44 44 45 49 52 54 54 55 56 56 60
Bab 5 Kesimpulan Dan Saran 5.1 Kesimpulan 5.2 Saran
63 63 64
Daftar Pustaka Lampiran A: Listing Program
65 67
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 2.1 Tabel Frekuensi Sampling dan Kualitas Suara yang Dihasilkan Tabel 2.2 Tabel Penyimpanan Berbagai Konfigurasi Audio Digital Tabel 2.3 Tabel Keterangan Header Mp3 Tabel 2.4 Tabel Distribusi Frekuensi Tabel 2.5 Tabel Hasil Kode Shannon-Fano Tabel 2.6 Tabel Pengubahan Heksadesimal ke Biner Tabel 2.7 Tabel Kode Shannon-Fano Tabel 3.1 Tabel Dokumentasi Naratif Usecase Pilih Kompresi Tabel 3.2 Tabel Dokumentasi Naratif Usecase Pilih Dekompresi Tabel 3.3 Tabel Dokumentasi Naratif Usecase Pilih Play Tabel 4.1 Tabel File Audio Yang Diuji Tabel 4.2 Tabel Hasil Pengujian Proses Kompresi Tabel 4.3 Hasil Pengujian Proses Dekompresi
12 13 15 22 25 26 27 33 33 34 55 57 60
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1 Proses Kompresi Dan Dekompresi (Pu, 2006) Gambar 2.2 Alur Gelombang Suara (Mukhlis, 2012) Gambar 2.3 Proses Digitasi (Mukhlis, 2012) Gambar 2.4 Struktur File Mp3 Gambar 2.5 Header Mp3 (Raissi, 2002) Gambar 2.6 Contoh Binary Tree Gambar 2.7 Contoh Completely Binary Tree Gambar 2.8 Contoh Perfect Binary Tree Gambar 2.9 Contoh Pengurutan Frekuensi Secara Descending Gambar 2.10 Contoh Pembagian Menjadi Dua Node Gambar 2.11 Contoh Pembagian Menjadi Dua Node Kedua Gambar 2.12 Contoh Pembagian Menjadi Dua Node Ketiga Gambar 2.13 Contoh Pembagian Menjadi Dua Node Keempat Gambar 2.14 Contoh Pembagian Menjadi Dua Node Kelima Gambar 2.15 Contoh Pembagian Menjadi Dua Node Keenam Gambar 3.1 Proses Kompresi Algoritma Shannon-Fano Gambar 3.2 Usecase Diagram Aplikasi Kompresi Audio Gambar 3.3 Activity Diagram Menu Utama Gambar 3.4 Activity Diagram Submenu Kompresi Gambar 3.5 Activity Diagram Submenu Dekompresi Gambar 3.6 Activity Diagram Submenu Play Gambar 3.7 Sequence Diagram Kompresi Audio Gambar 3.8 Sequence Diagram Dekompresi Audio Gambar 3.9 Sequence Diagram Play Audio Gambar 3.10 Rancangan Antarmuka Menu Utama Gambar 3.11 Rancangan Antarmuka Sub Menu Kompresi Gambar 3.12 Rancangan Antarmuka Sub Menu Dekompresi Gambar 3.13 Rancangan Antarmuka Sub Menu Play Gambar 3.14 Rancangan Antarmuka Sub Menu Bantuan Gambar 4.1 Tampilan Antarmuka Menu Utama Aplikasi Gambar 4.2 Tampilan Antarmuka Sub Menu Aplikasi Gambar 4.3 Tampilan Sub Menu Kompresi Gambar 4.4 Tampilan Buka File Sub Menu Kompresi Gambar 4.5 Tampilan Hasil Buka File Sub Menu Kompresi Gambar 4.6 Tampilan Proses Kompresi Gambar 4.7 Tampilan Hasil Proses Kompresi Gambar 4.8 Tampilan Sub Menu Dekompresi Gambar 4.9 Tampilan Buka File Sub Menu Dekompresi Gambar 4.10 Tampilan Hasil Buka File Sub Menu Dekompresi Gambar 4.11 Tampilan Proses Dekompresi Gambar 4.12 Tampilan Hasil Proses Dekompresi
8 10 11 14 14 21 21 22 23 23 23 24 24 24 25 29 32 35 35 36 36 37 38 39 39 40 41 42 43 44 45 46 46 47 48 48 49 50 50 51 51
Universitas Sumatera Utara
xi Gambar 4.13 Tampilan Sub Menu Play Gambar 4.14 Tampilan Buka File Sub Menu Play Gambar 4.15 Tampilan Memainkan Audio Gambar 4.16 Sub Menu Bantuan Gambar 4.17 Gambar Grafik Hasil Pengujian Proses Kompresi
52 53 53 54 59
Universitas Sumatera Utara