Teori Rate-Distortion

Dalam kompresi data lossy, data yang dikompresi perlu sama persis dengan data asli. Sering kali untuk alasan tersebut dilakukan dengan perkiraan. Suatu pengukuran distorsi sebagai entitas matematika akan menyatakan dengan tepat seberapa dekat perkiraan tersebut. Secara umum, terdapat suatu fungsi yang menghubungkan setiap dua huruf  dan  dalam alphabet A yang merupakan nilai non negatif  yang didenotasi sebagai.

                          ................................................... (2.11)

            Di sini,  merupakan data asli,  merupakan perkiraan, dan juga merupakan jumlah distorsi antara  dan . Pengukuran distorsi yang paling umum adalah pengukuran Hamming Distortion

                                                ................................................... (2.12)

dan Squared-Error Distortion (yang hanya dapat diaplikasi ketika A merupakan suatu kumpulan nilai-nilai).

                                  ..................................................... (2.13)

Teori rate-distortion menyatakan bahwa untuk suatu sumber dan pengukuran distorsi yang diberikan, terdapat suatu fungsi yang eksis yaitu R(D), yang disebut dengan rate-distortion function. Bentuk tipikal dari R(D) dapat digambarkan pada grafik di bawah ini.

Gambar  2.12  Grafik  Rate-Distortion Function

Jika sampel sumber bersifat tidak bebas terhadap satu sama lain, fungsi rate-distortion dapat diperoleh dengan memecahkan masalah constrained minimization.

                                                                                  ........................... (2.14)

Subjek untuk constraints dinyatakan dengan:

                                                                          ..................................................... (2.15)

dan

                                                                          ..................................................... (2.16)

Dimana d(i, j)  adalah distorsi antara huruf ke-i dan huruf ke-j dalam alphabet. Dengan menggunakan algoritma Blahut, adalah mungkin untuk mengkalkulasi secara numerik fungsi rate-distortion tersebut.

Teori rate-distortion berdasarkan pada konsep dari block coding (sama seperti di atas). Suatu lossy block code yang dikenal sebagai vector quantizer (VQ). Panjang dari blok n dari kode dikenal sebagai dimensi VQ.

Dalil:  asumsi bahwa sumber adalah stationary dan sampel sumber bersifat tidak bebas. Untuk setiap D ³ 0 dan untuk tiap  Î ³ 0, terdapat sebuah dimensi n VQ yang eksis (cukup besar)  dengan distorsi tidak besar dari

dan laju tidak lebih dari

            Lebih lanjut, tidak ada sebuah VQ yang eksis dengan distorsi D dan laju kurang dari R(D).  Pokok dari dalil tersebut menyatakan bahwa R(D) adalah unjuk kerja dari rate-distortion untuk sebauh VQ yang optimal. Dalil di atas dapat digeneralisasi ke dalam kasus dimana sumber adalah stationary dan ergodic.

 Gap Antara Teori dan Praktek

            Teori tersebut berlaku ketika panjang blok n mencapai tak berhingga. Dalam kompresi real-time, algoritma kompresi harus menunggu hingga sumber sampel konsekutif n sebelum dapat memulai kompresi. Ketika n bernilai besar, nilai delay (waktu tunda) mungkin akan terlalu lama. Sebagai contoh, dalam kompresi speech secara real-time, signal speech disampel pada 8000 sampel / detik. Jika n katakanlah bernilai 4000, maka waktu tunda kompresi adalah setengah detik. Dalam percakapan dua arah, maka waktu tunda ini tidak terlalu menganggu.

            Teori ini tidak perlu menjadi bahan pertimbangan untuk dihubungkan dengan kompleksitas operasi kompresi dan dekompresi. Secara tipikal, sebagaimana  panjang blok n meningkat, kompleksitas akan meningkat juga. Sering, laju peningkatan merupakan nilai eksponensial dari n.

            Teori ini mengasumsikan bahwa statistik properti dari sumber dikenal. Dalam prakteknya, informasi ini mungkin tidak tersedia.

            Teori ini mengasumsikan tidak ada kesalahan dalam mengkompresi bit stream. Dalam prakteknya, dikarenakan oleh noise dalam  kanal (channel) komunikasi atau ketidaksempurnaan dalam medium penyimpan, akan terdapat kesalahan (error) dalam bit stream yang dikompresi.

Tetapi semua masalah-masalah tersebut telah berhasil dipecahkan oleh para periset di lapangan.

 Next Pages...