Pertimbangkan ansambel pesan kepada mereka dengan probabilitas yang sesuai. Setiap pesan harus diwakili oleh kata kode yang terdiri dari simbol-simbol berurutan milik alfabet tertentu. Mari kita nyatakan dengan jumlah simbol yang berbeda dalam alfabet, dengan jumlah simbol dalam kata kode yang sesuai dengan pesan. Jumlah rata-rata simbol per pesan, menurut definisi, adalah.

Tugas pertama kita adalah menemukan batas bawah

Di Sekte. 2.8 kita melihat bahwa entropi suatu ansambel pesan adalah jumlah rata-rata informasi yang diperlukan untuk mengidentifikasi secara unik sebuah pesan dari ansambel ini. Pada bagian yang sama kita melihat bahwa simbol-simbol membawa rata-rata kuantitas maksimum informasi ketika kemungkinannya sama. Nilai maksimum ini merupakan kapasitas kode alfabet. Selain itu, persamaan (2.100) dan (2.105) menunjukkan bahwa ketergantungan statistik suatu simbol tertentu terhadap simbol sebelumnya tidak dapat meningkatkan jumlah rata-rata informasi untuk simbol tersebut. Atas dasar ini kita dapat menyimpulkan bahwa

Dari mana kita mendapatkannya?

yaitu, jumlah rata-rata simbol per pesan tidak boleh kurang dari entropi entropi pesan dibagi keluaran alfabet. Bukti langsung dari hasil ini diberikan di Bagian. 3.5.

Alasan yang digunakan untuk menurunkan batas bawah ini memungkinkan kita untuk mengusulkan aturan umum membangun kata sandi dengan panjang rata-rata yang cukup dekat dengan batas ini. Aturan pertama adalah bahwa di setiap posisi kata sandi, simbol alfabet yang berbeda harus digunakan dengan probabilitas yang sama, sehingga dapat memaksimalkan jumlah rata-rata informasi yang disampaikan oleh simbol tersebut. Aturan kedua adalah probabilitas terjadinya

Karakter pada setiap posisi codeword harus independen terhadap semua karakter sebelumnya. Jika aturan ini diikuti dengan tepat, maka panjang rata-rata kata kode yang dihasilkan akan sama dengan nilai minimum yang ditentukan oleh rumus (3.3). Akan tetapi, kita akan melihat bahwa hanya dalam kasus khusus simbol dapat digunakan dengan probabilitas yang sama dan dibuat independen dari semua simbol sebelumnya. Aturan untuk menyusun kumpulan kata kode ini paling baik dijelaskan dengan menggunakan contoh spesifik berikut. Prosedur pengkodean yang digunakan mirip dengan yang pertama kali dikemukakan oleh Shannon.

Pesan dari alfabet sumber ditulis dalam urutan kemungkinan kemunculannya. Selanjutnya, pesan-pesan tersebut dibagi menjadi dua bagian sehingga probabilitas total pesan-pesan di masing-masing bagian ini sedekat mungkin. Pesan bagian pertama diberi 0 sebagai karakter pertama, dan pesan bagian kedua diberi 1 (bisa juga sebaliknya). Kemudian masing-masing bagian ini (jika berisi lebih dari satu pesan) dibagi menjadi dua bagian yang kemungkinannya sama dan simbol kedua untuk bagian pertama adalah 0, dan untuk bagian kedua - 1. Proses ini diulangi hingga tidak ada lagi satu pun. pesan pada suatu waktu. Untuk contoh yang diberikan dalam tabel. 1 pada tahap pertama pemisahan bagian pertama akan ada satu pesan A 1 dengan probabilitas P(A 1)=0,4, di bagian kedua - pesan yang tersisa dengan probabilitas total P Σ ( A 2 -A 6)=0,6. Mari kita kaitkan pesannya A 1 karakter adalah 0, dan pesan lainnya memiliki 1 sebagai karakter pertama.

Tabel 1. Pengkodean pesan sewenang-wenang

Pada tahap kedua, kita akan memisahkan pesan-pesan ( A 2 ,A 3 ,A 4 ,A 5 ,A 6) menjadi dua bagian yang kemungkinannya sama, termasuk pada bagian pertama pesan A 2, dan di bagian kedua - pesan ( A 3 ,A 4 ,A 5 ,A 6). Mari kita kaitkan pesannya A 2 karena karakter kedua adalah 0, dan pesan lainnya adalah 1, dst. Hasilnya, kami sampai pada kodenya KE 2, diberikan dalam tabel. 2.

Tabel 2. Pengkodean pesan menggunakan kode Shannon-Fano

Kode berdasarkan konstruksinya memenuhi properti awalan. Oleh karena itu, barisan simbol biner di atas “ L ” diterjemahkan dengan jelas: ( A 1 ,A 1 ,A 4 ,A 1 ,A 1 ,A 1 ,A 6 ,A 1). Jumlah rata-rata karakter per pesan, dengan mempertimbangkan probabilitasnya =0,4*1+0,3*2+0,3*4=2,2, mis. sedikit melebihi entropi sumber pesan.

2.4. Panjang kata sandi rata-rata

Prosedur Shannon-Fano tidak serta merta meminimalkan , karena mencapai nilai rata-rata informasi diri yang besar pada satu huruf kode dapat menyebabkan miskinnya pilihan untuk huruf kode berikutnya. Jika partisi ini dapat dihitung sehingga kelompok-kelompok tersebut memiliki kemungkinan yang sama persis pada setiap tahap partisi, maka probabilitas huruf sumber dan panjang kata sandi akan dihubungkan dengan persamaan

(2)

Batasan panjang kata sandi kode awalan diberikan oleh pertidaksamaan Kraft dan teorema pengkodean sumber.

Teorema 1.(Ketidaksetaraan Kraft). Jika bilangan bulat (
) memenuhi pertidaksamaan

(3)

maka ada suatu kode yang mempunyai sifat awalan dengan huruf volume D, panjang kata sandinya sama dengan angka-angka tersebut. Sebaliknya, panjang kata sandi dari kode apa pun yang menerapkan properti awalan memenuhi pertidaksamaan (3). Teorema tersebut tidak menyatakan bahwa kode apa pun dengan panjang kata kode yang memenuhi (3) adalah awalan. Jadi, misalnya, himpunan kata sandi biner (0; 00; 11) memenuhi (3), tetapi tidak memiliki properti awalan. Teorema tersebut menyatakan bahwa ada beberapa kode awalan dengan panjang seperti itu, misalnya kode (0; 10; 11) . Tidak semua kode decoding unik memiliki properti awalan, misalnya kode K3 pada Tabel. 3. Di dalamnya, setiap kata sandi merupakan awalan dari setiap kata sandi yang lebih panjang. Pada saat yang sama, penguraian kode yang jelas adalah hal yang sepele, karena simbol 0 selalu menentukan awal dari kata sandi baru. Namun, kode-kode yang mempunyai sifat prefiks berbeda dengan kode-kode unik lainnya yang dapat didekodekan karena akhir kata kode selalu dapat dikenali, sehingga penguraian kode dapat dilakukan tanpa menunda urutan kata-kata kode yang diamati (kode K4 Tabel 3) . Oleh karena itu, kode awalan terkadang disebut kode flash.

Tabel 3. Kode unik yang dapat didekodekan

Karena panjang kata kode dari setiap kode unik yang dapat didekodekan memenuhi (3) dan dimungkinkan untuk membuat kode awalan untuk himpunan panjang apa pun yang memenuhi (3), maka kode unik apa pun yang dapat didekodekan dapat diganti dengan kode awalan tanpa mengubah panjangnya. kata sandinya. Dengan demikian, Teorema 2 berikut untuk pengkodean sumber sehubungan dengan panjang rata-rata kata kode diusulkan baik untuk kode unik yang dapat didekodekan dan untuk subkelas kode awalan.

Informasi adalah sekumpulan informasi yang dapat disimpan, dikirim, diproses, dan digunakan dalam aktivitas manusia.

Mengubah ciri-ciri media yang digunakan untuk merepresentasikan informasi disebut sinyal , dan nilai sifat ini, yang berkaitan dengan skala pengukuran tertentu, disebut parameter sinyal .

Membedakan dua jenis sinyal (dan karena itu dua jenis pesan ): kontinu dan diskrit.

Untuk memastikan kesederhanaan dan keandalan pengenalan sinyal diskrit ( tanda-tanda ), disarankan untuk mengurangi jumlahnya seminimal mungkin. Biasanya, mereka menggunakan operasi merepresentasikan karakter asli dalam alfabet lain dengan jumlah karakter yang lebih sedikit, yang disebut simbol . Saat menunjukkan operasi ini, istilah yang sama digunakan - “ pengkodean ».

Informasi sendiri

Jumlah informasi yang dibawa surat X Saya alfabet, sebut saja informasi sendiri terkandung di dalamnya X Saya dan menunjukkan
.

.

rumus Shannon

Mari kita rata-ratakan informasi kita sendiri, mis. Mari kita hitung jumlah rata-rata informasi yang dibawa oleh satu karakter alfabet
:
.

Jumlah rata-rata informasi, jatuh tempo dengan satu huruf, ditelepon entropi alfabet (atau sumber) dan ditunjuk H:

- rumus Shannon .

Jelas sekali rata-rata 1 jumlah informasi dalam panjang pesan N dihitung dengan rumus:

.

Komentar.Jumlah informasi dikaitkan dengan pesan itu sendiri.

Komentar. Entropi adalah karakteristik sumber pesan (alfabet).

rumus Hartley

Pada kemungkinan yang sama karakter alfabet
, dari rumus Shannon kita peroleh: .

- rumus Hartley .

Unit informasi

Satuan informasi per elemen pesan (satuan entropi) disebut sedikit .

Pertimbangkan alfabet simbol-simbol yang kemungkinannya sama yang entropinya sama dengan 1:
. Karena itu mengikuti dari sini
, maka jelas 1 bit adalah banyaknya informasi yang terkandung dalam pesan biner (abjad (0,1)) dengan panjang 1.

Berikut ini, dalam ekspresi I dan H kita akan selalu menggunakan logaritma dengan basis 2.

Sifat-sifat entropi

1. Entropi N- besarnya

- non-negatif(N  0) ,

- terbatas, Sifat-sifat ini berasal dari kenyataan bahwa semua komponennya mempunyai kualitas yang sama.
.

2. Entropi sama dengan nol jika peluang salah satu simbolnya adalah 1. Dalam hal ini, mereka berbicara tentang sumber yang sepenuhnya deterministik dan tidak adanya ketidakpastian di dalamnya, karena pengamat mengetahui pesan dari sumber tersebut sebelum saat pengamatannya.

3. Dapat juga ditunjukkan bahwa entropi maksimum jika semua karakter alfabet memiliki kemungkinan yang sama, yaitu. N maks = catatan M. Jadi, untuk mencari nilai entropi maksimum yang mungkin (untuk sejumlah simbol tetap), digunakan rumus Hartley.

4. Yang menarik adalah pesan biner, menggunakan alfabet biner(0,1). sejak kapan M= 2 probabilitas karakter alfabet P 1  1 dan P 2  1, maka kita dapat memasukkan P 1 = P Dan P 2 = 1-P. Kemudian entropi ditentukan oleh relasi

Dalam contoh pengkodean di atas, semua kata kode memiliki panjang yang sama. Namun, hal ini bukan merupakan persyaratan wajib. Selain itu, jika kemungkinan kemunculan pesan sangat berbeda satu sama lain, maka lebih baik menyandikan pesan dengan kemungkinan kemunculan yang tinggi dengan kata-kata pendek, dan menyandikan pesan yang jarang dengan kata-kata yang lebih panjang. Akibatnya, teks kode rata-rata akan menjadi lebih pendek dalam kondisi tertentu.

Indikator keekonomian atau efisiensi kode yang tidak seragam bukanlah panjang masing-masing kata kode, tetapi panjang “rata-rata”, yang ditentukan oleh persamaan:

di mana adalah kata kode yang digunakan untuk mengkodekan pesan, a adalah panjangnya, probabilitas pesan, dan jumlah total pesan sumber. Untuk singkatnya dalam penulisan rumus, dapat digunakan notasi sebagai berikut: Dan . Perhatikan bahwa penunjukan panjang pengkodean rata-rata dengan menekankan fakta bahwa nilai ini bergantung pada sumber pesan dan metode pengkodean.

Kode yang paling ekonomis adalah kode yang mempunyai panjang rata-rata terkecil. Mari kita bandingkan, dengan menggunakan contoh, efektivitas biaya dari berbagai metode pengkodean sumber yang sama.

Biarkan sumbernya berisi 4 pesan dengan probabilitas. Pesan-pesan ini dapat dikodekan dengan kata sandi dua karakter yang panjangnya konstan dalam alfabet sesuai dengan tabel kode.

Jelasnya, untuk mewakili (mentransmisikan) urutan apa pun, rata-rata diperlukan 2 karakter per pesan. Mari kita bandingkan efektivitas pengkodean tersebut dengan pengkodean yang dijelaskan di atas dengan kata-kata yang panjangnya bervariasi. Tabel kode untuk kasus ini mungkin memiliki bentuk berikut.

Dalam tabel ini, tidak seperti tabel sebelumnya, pesan yang paling sering dikodekan dengan satu karakter biner. Untuk opsi pengkodean terakhir yang kami miliki

sedangkan untuk kode seragam rata-rata panjangnya (sama dengan panjang total kata sandinya). Dari contoh yang dipertimbangkan, jelas bahwa penyandian pesan dengan kata-kata yang panjangnya berbeda dapat memberikan peningkatan efisiensi penyandian yang signifikan (hampir dua kali lipat).

Saat menggunakan kode yang tidak rata, muncul masalah, yang akan kami jelaskan menggunakan contoh tabel kode terakhir. Mari kita gunakan tabel ini untuk menyandikan urutan pesan , sebagai hasilnya diubah menjadi teks biner berikut: 010110. Karakter pertama dari pesan asli didekodekan secara unik - ini. Namun, ketidakpastian lebih lanjut dimulai: atau . Ini hanyalah beberapa kemungkinan opsi untuk menguraikan urutan karakter asli.

Perlu dicatat bahwa ambiguitas penguraian kata muncul meskipun kondisi penguraian tanda yang jelas (injektivitas pemetaan kode) terpenuhi.

Inti masalahnya adalah ketidakmungkinan mengidentifikasi kata-kata kode secara jelas. Untuk mengatasinya, perlu memisahkan satu kata kode dari kata kode lainnya. Tentu saja hal ini dapat dilakukan, tetapi hanya dengan menggunakan jeda antar kata atau tanda pemisah khusus, yang memerlukan penunjukan kode khusus. Kedua cara tersebut, pertama, bertentangan dengan metode pengkodean kata yang dijelaskan di atas dengan menggabungkan kode karakter yang membentuk sebuah kata, dan, kedua, akan menyebabkan pemanjangan teks kode yang signifikan, sehingga meniadakan keuntungan menggunakan kode dengan panjang variabel.

Solusi untuk masalah ini adalah kemampuan untuk memilih kata kode individual dalam teks kode apa pun tanpa menggunakan pembatas khusus. Dengan kata lain, kode tersebut harus memenuhi persyaratan berikut: setiap rangkaian karakter kode dapat dibagi secara unik menjadi kata-kata kode. Kode yang mana persyaratan terakhir puas, disebut dapat didekodekan secara unik (terkadang disebut kode bebas koma).

Mari kita lihat kodenya (skema pengkodean abjad) , ditentukan oleh tabel kode

dan berbagai kata yang terdiri dari kode-kode dasar.

Definisi. Suatu kode dikatakan dapat didekodekan secara unik jika

artinya, setiap kata yang tersusun dari kode-kode dasar dapat diuraikan secara unik menjadi kode-kode dasar.

Jika tabel kode berisi kata kode yang sama, yaitu if

maka kode tersebut jelas tidak dapat didekodekan secara unik (rangkaian tidak dapat dipisahkan). Kode-kode tersebut tidak dipertimbangkan lebih lanjut.

Ide untuk menyimpan jumlah karakter dengan pengkodean tidak merata adalah dengan menetapkan kata-kata yang lebih pendek ke pesan yang lebih mungkin (lebih sering diulang) dan, sebaliknya, kata-kata yang lebih panjang ke pesan yang lebih kecil kemungkinannya (sering). Hal ini memastikan rendahnya jumlah rata-rata karakter per pesan. Namun, perawatan harus dilakukan pada saat yang bersamaan decoding yang jelas. Yang terakhir ini disediakan, khususnya, untuk kode awalan di mana tidak ada kata yang merupakan fragmen awal ( awalan) lain.

Contoh 1.3.1 Kode di bawah ini ( M=4) tidak dapat didekodekan secara unik:

Memang benar, jika kombinasi 00111111 muncul pada output encoder, maka dapat dibaca sebagai X 1 , X 2 , X 3 , X 4, atau X 1 , X 2 , X 4 , X 3, atau X 1 , X 1 , X 4 , X 4, atau X 1 , X 1 , X 3 , X 3 , X 3 .

Contoh 1.3.2 Berbeda dengan yang sebelumnya, kode di bawah ini ( M=4) diberi awalan, sehingga dapat didekodekan secara unik:

Jadi, jika urutan keluaran encoder adalah 0011010111110, maka hanya dapat didekodekan dengan cara: X 1 , X 1 , X 3 , X 2 , X 4 , X 3 .

Kode awalan apa pun dapat didekodekan secara instan. Artinya, setiap kata-katanya dapat langsung dikenali setelah karakter terakhirnya muncul.

Teorema 1.3.1 (Pertidaksamaan Kraft). Kode berisiM kata sandi, dapat diawali jika dan hanya jika panjang kata sandinyaN 1 , N 2 , …, n Mtunduk pada ketimpangan

Panjang rata-rata kode yang tidak rata ditentukan oleh persamaan

Teorema 1.3.2 Panjang rata-rata kode awalan terbaik terletak di dalamnya

Kode Shannon-Fano

Pada langkah pertama dari algoritma yang sedang dipertimbangkan, ansambel sumber dibagi menjadi dua himpunan bagian, yang total probabilitasnya sedekat mungkin satu sama lain, yaitu. menjadi 1/2. Semua pesan dari himpunan bagian pertama diberi simbol pertama dari kata kode 0, dan yang kedua - simbol pertama 1. Pada langkah kedua, masing-masing himpunan bagian dibagi lagi menjadi dua dengan probabilitas kumulatif terdekat, dan kata-kata kode dari subset pertama yang dihasilkan menerima 0 sebagai simbol kedua, dan yang kedua – 1, dll. Segera setelah pesan unik dalam subset, pengkodeannya diverifikasi. Prosedur ini diulangi sampai semua pesan ansambel habis.

Mudah untuk menunjukkan bahwa panjang rata-rata kode Shannon-Fano memenuhi pertidaksamaan sisi kanan Teorema 1.3.2:

Contoh 1.3.3 Mari kita menyandikan sumber terpisah M= 8 pesan memiliki probabilitas yang tercantum dalam tabel.

DI DALAM dalam hal ini mencatat M=3, entropi sumberH(X)"2,44 sedikit , A panjang kata sandi rata-rata:

kode Huffman

Kode ini optimal dalam arti tidak ada kode awalan yang memiliki rata-rata panjang kata yang lebih pendek. Pada langkah pertama pengkodean Huffman, dua pesan yang paling kecil kemungkinannya digabungkan menjadi satu pesan total, yang probabilitasnya sama dengan jumlah probabilitas pesan aslinya. Pada saat yang sama, salah satu dari pesan asli simbol kode diberi 0, dan yang lainnya - 1. Pada langkah kedua, hal yang sama diulangi dengan ansambel baru M-1 pesan dan sekali lagi dua pesan yang paling kecil kemungkinannya digabungkan menjadi satu, menetapkan karakter 0 ke salah satu pesan dan 1 ke pesan lainnya. Prosedur ini diulangi M-1 kali, yaitu hingga langkah di mana salah satu dari dua pesan yang tersisa diberi simbol 0, dan yang lainnya - 1. Hasilnya adalah pohon kode, membaca dari kanan ke kiri, kata-kata kode dibentuk untuk semua pesan dari ansambel yang dikodekan.

Akan lebih mudah, saat memulai prosedur pengkodean, untuk menuliskan semua pesan dalam urutan probabilitasnya. Perlu juga dicatat bahwa, berbeda dengan algoritma Shannon-Fano, selama pengkodean Huffman, setiap kata kode muncul dalam urutan terbalik.

Contoh di bawah mengilustrasikan proses pengkodean dan menunjukkan keunggulan komparatif kode Huffman.

Contoh 1.3.4 Mari Huffman mengkodekan ansambel dari Contoh 1.3.3:

Panjang Rata-rata: