Teori pengekodan. Jenis pengekodan. Lahirnya teori pengekodan Klasifikasi kaedah pengekodan

"Tujuan kursus ini adalah untuk menyediakan anda untuk masa depan teknikal anda."

Hai, Habr. Ingat artikel hebat "Anda dan Kerja Anda" (+219, 2442 penanda halaman, 394k bacaan)?

Jadi Hamming (ya, ya, semak sendiri dan pembetulan sendiri kod Hamming) mempunyai keseluruhan buku berdasarkan kuliahnya. Kami menterjemahkannya, kerana lelaki itu bercakap perkara itu.

Buku ini bukan hanya tentang IT, ini adalah buku tentang gaya pemikiran orang yang sangat keren. “Ia bukan sekadar caj untuk berfikiran positif; ia menerangkan keadaan yang meningkatkan peluang untuk melakukan kerja yang hebat."

Kami telah menterjemah 28 (daripada 30) bab. Dan kami sedang mengusahakan penerbitan "di atas kertas".

Teori pengekodan - I

Setelah mempertimbangkan komputer dan cara ia berfungsi, kini kita akan melihat isu pembentangan maklumat: bagaimana komputer mewakili maklumat yang ingin kita proses. Makna mana-mana aksara boleh bergantung pada cara ia diproses, mesin tidak mempunyai makna khusus untuk bit yang digunakan. Apabila membincangkan sejarah perisian dalam Bab 4, kami mempertimbangkan beberapa bahasa pengaturcaraan sintetik, di mana kod arahan berhenti bertepatan dengan kod arahan lain. Keadaan ini adalah tipikal untuk kebanyakan bahasa, maksud arahan ditentukan oleh program yang sepadan.

Untuk memudahkan masalah penyampaian maklumat, mari kita pertimbangkan masalah pemindahan maklumat dari satu titik ke satu titik. Soalan ini berkaitan dengan isu memelihara maklumat. Masalah penghantaran maklumat dalam masa dan ruang adalah sama. Rajah 10.1 menunjukkan model komunikasi biasa.

Rajah 10.1

Di sebelah kiri dalam Rajah 10.1 ialah sumber maklumat. Apabila mempertimbangkan model, kami tidak mengambil berat tentang sifat sumber. Ia boleh menjadi satu set simbol abjad, nombor, formula matematik, nota muzik, simbol yang kita boleh mewakili pergerakan tarian - sifat sumber dan makna simbol yang disimpan di dalamnya bukan sebahagian daripada model penghantaran. Kami menganggap hanya sumber maklumat, dengan batasan ini, teori umum yang berkuasa diperoleh yang boleh diperluaskan ke banyak kawasan. Ia adalah abstraksi daripada banyak aplikasi.

Apabila Shannon mencipta teori maklumat pada akhir 1940-an, dipercayai bahawa ia harus dipanggil teori komunikasi, tetapi dia menegaskan istilah maklumat. Istilah ini telah menjadi sumber berterusan kedua-dua peningkatan minat dan kekecewaan berterusan dalam teori. Penyiasat ingin membina keseluruhan "teori maklumat", mereka merosot menjadi teori tentang set simbol. Berbalik kepada model penghantaran, kami mempunyai sumber data yang perlu dikodkan untuk penghantaran.

Pengekod terdiri daripada dua bahagian, bahagian pertama dipanggil pengekod sumber, nama tepat bergantung pada jenis sumber. Sumber jenis data yang berbeza sepadan dengan jenis pengekod yang berbeza.

Bahagian kedua proses pengekodan dipanggil pengekodan saluran dan bergantung kepada jenis saluran penghantaran data. Oleh itu, bahagian kedua proses pengekodan dipadankan dengan jenis saluran penghantaran. Oleh itu, apabila menggunakan antara muka standard, data daripada sumber mula-mula dikodkan mengikut keperluan antara muka, dan kemudian mengikut keperluan saluran penghantaran data yang digunakan.

Menurut model dalam Rajah 10.1, pautan data terdedah kepada "bunyi rawak tambahan". Semua bunyi dalam sistem digabungkan pada ketika ini. Diandaikan bahawa pengekod menerima semua simbol tanpa herotan, dan penyahkod melaksanakan fungsinya tanpa ralat. Ini adalah beberapa idealisasi, tetapi untuk banyak tujuan praktikal ia hampir dengan realiti.

Fasa penyahkodan juga terdiri daripada dua peringkat: saluran - standard, standard - penerima data. Pada akhir pemindahan, data dipindahkan kepada pengguna. Sekali lagi, kami tidak mempertimbangkan persoalan bagaimana pengguna mentafsir data ini.

Seperti yang dinyatakan sebelum ini, sistem penghantaran data, contohnya, mesej telefon, radio, program TV, membentangkan data sebagai satu set nombor dalam daftar komputer. Sekali lagi, penghantaran dalam ruang tidak berbeza dengan penghantaran dalam masa atau penyimpanan maklumat. Adakah anda mempunyai maklumat yang akan diperlukan selepas beberapa ketika, maka ia mesti dikodkan dan disimpan di sumber storan data. Maklumat dinyahkod jika perlu. Jika sistem pengekodan dan penyahkodan adalah sama, kami menghantar data melalui saluran penghantaran tidak berubah.

Perbezaan asas antara teori yang dibentangkan dan teori konvensional dalam fizik ialah andaian bahawa tiada bunyi pada sumber dan penerima. Malah, ralat berlaku dalam mana-mana bahagian perkakasan. Dalam mekanik kuantum, bunyi bising berlaku pada mana-mana peringkat mengikut prinsip ketidakpastian, dan bukan sebagai keadaan awal; dalam apa jua keadaan, konsep hingar dalam teori maklumat tidak setara dengan dalam mekanik kuantum.
Untuk kepastian, kami akan mempertimbangkan lagi bentuk perduaan perwakilan data dalam sistem. Bentuk lain dikendalikan dengan cara yang sama, demi kesederhanaan, kami tidak akan menganggapnya.

Mari kita mulakan dengan melihat sistem dengan aksara berkod panjang berubah-ubah, seperti dalam kod titik dan sengkang Morse klasik, di mana aksara biasa adalah pendek dan aksara jarang adalah panjang. Pendekatan ini membolehkan anda mencapai kecekapan kod yang tinggi, tetapi perlu diperhatikan bahawa kod Morse adalah ternary, bukan binari, kerana ia mengandungi aksara ruang antara titik dan sengkang. Jika semua aksara dalam kod adalah sama panjang, maka kod sedemikian dipanggil kod blok.

Sifat pertama kod yang diperlukan adalah keupayaan untuk menyahkod mesej dengan jelas tanpa ketiadaan bunyi, sekurang-kurangnya ini nampaknya merupakan sifat yang diingini, walaupun dalam beberapa situasi keperluan ini boleh diabaikan. Data dari saluran penghantaran kelihatan seperti aliran satu dan sifar kepada penerima.

Mari kita panggil dua simbol bersebelahan pengembangan ganda, tiga simbol bersebelahan tiga pengembangan, dan secara umum, jika kita menghantar simbol N, penerima melihat penambahan kepada kod asas simbol N. Penerima, yang tidak mengetahui nilai N, mesti membahagikan strim kepada blok yang diterjemahkan. Atau, dengan kata lain, penerima mesti dapat menguraikan aliran dengan cara yang unik untuk memulihkan mesej asal.

Pertimbangkan abjad dengan bilangan aksara yang kecil, biasanya abjad yang lebih besar. Abjad bahasa bermula dari 16 hingga 36 aksara, termasuk huruf besar dan kecil, tanda nombor, tanda baca. Contohnya, dalam jadual ASCII, 128 = 2 ^ 7 aksara.
Pertimbangkan kod khas yang terdiri daripada 4 aksara s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Bagaimana penerima harus mentafsir ungkapan yang diterima seterusnya

Bagaimana s1s1s4 atau bagaimana s2s4?

Anda tidak boleh memberikan jawapan yang jelas kepada soalan ini, kod ini pastinya tidak dinyahkodkan, oleh itu, ia tidak memuaskan. Sebaliknya, kod

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Menyahkod mesej dengan cara yang unik. Mari kita ambil rentetan sewenang-wenangnya dan lihat bagaimana penerima akan menyahkodnya. Anda perlu membina pokok penyahkodan Mengikut borang dalam Rajah 10.II. Talian

1101000010011011100010100110 …

Boleh dipecahkan kepada blok aksara

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Mengikut peraturan berikut untuk membina pokok penyahkodan:

Jika anda berada di bahagian atas pokok, anda membaca watak seterusnya. Apabila anda mencapai daun pokok, anda menukar jujukan kepada aksara dan kembali ke permulaan.

Sebab pokok sebegitu wujud ialah tiada aksara merupakan awalan bagi yang lain, jadi anda sentiasa tahu bila hendak kembali ke permulaan pokok penyahkod.

Ia adalah perlu untuk memberi perhatian kepada perkara berikut. Pertama, penyahkodan ialah proses penstriman yang ketat di mana setiap bit diperiksa sekali sahaja. Kedua, protokol biasanya termasuk aksara yang menandakan berakhirnya proses penyahkodan dan diperlukan untuk menunjukkan penghujung mesej.

Mengelakkan penggunaan aksara mengekor adalah kesilapan biasa dalam reka bentuk kod. Sudah tentu, mod penyahkodan berterusan boleh disediakan, dalam hal ini simbol trailing tidak diperlukan.

Rajah 10.II

Soalan seterusnya ialah kod untuk penstriman (segera) penyahkodan. Pertimbangkan kod yang diperoleh daripada yang sebelumnya dengan memaparkan aksara

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Katakan kita mendapat urutannya 011111...111 ... Satu-satunya cara anda boleh menyahkod teks mesej ialah mengumpulkan bit dari penghujung sebanyak 3 dalam kumpulan dan memilih kumpulan dengan sifar pendahuluan sebelum yang, selepas itu anda boleh menyahkod. Kod sedemikian boleh dinyahkodkan dengan cara yang unik, tetapi tidak serta-merta! Untuk menyahkod, anda mesti menunggu sehingga tamat penghantaran! Dalam amalan, pendekatan ini menafikan kelajuan penyahkodan (teorem McMillan), oleh itu, adalah perlu untuk mencari cara penyahkodan segera.

Pertimbangkan dua cara untuk mengekod aksara yang sama, Si:

s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,

Pokok penyahkodan untuk kaedah ini ditunjukkan dalam Rajah 10.III.

Rajah 10.III

Cara kedua

s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111,

Pokok penyahkodan bagi pelepasan ini ditunjukkan dalam Rajah 10.IV.

Cara paling jelas untuk mengukur kualiti kod ialah purata panjang bagi satu set mesej. Untuk melakukan ini, adalah perlu untuk mengira panjang kod setiap aksara didarab dengan kebarangkalian kejadian pi yang sepadan. Ini akan memberikan panjang keseluruhan kod. Formula untuk purata panjang kod L untuk abjad q aksara adalah seperti berikut

Di mana pi ialah kebarangkalian berlakunya aksara si, li ialah panjang yang sepadan bagi aksara yang dikodkan. Untuk kod yang cekap, nilai L hendaklah sekecil mungkin. Jika P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 dan p5 = 1/16, maka untuk kod # 1 kita mendapat nilai panjang kod

Dan untuk kod # 2

Nilai yang diperoleh menunjukkan keutamaan kod pertama.
Jika semua perkataan dalam abjad mempunyai kebarangkalian kejadian yang sama, maka kod kedua adalah lebih baik. Sebagai contoh, dengan pi = 1/5 panjang kod # 1

Dan panjang kod # 2

Keputusan ini menunjukkan keutamaan 2 kod. Oleh itu, apabila mereka bentuk kod "baik", kemungkinan simbol berlaku mesti dipertimbangkan.

Rajah 10.IV

Rajah 10.V

Pertimbangkan ketaksamaan Kraft, yang menentukan nilai pengehadan panjang kod aksara li. Berdasarkan asas 2, ketaksamaan diwakili dalam bentuk

Ketaksamaan ini bermakna bahawa tidak boleh terdapat terlalu banyak simbol pendek dalam abjad, jika tidak jumlahnya akan menjadi agak besar.

Untuk membuktikan ketidaksamaan Kraft untuk sebarang kod penyahkodan unik yang pantas, kami membina pepohon penyahkodan dan menggunakan kaedah aruhan matematik. Jika pokok mempunyai satu atau dua daun, seperti yang ditunjukkan dalam Rajah 10.V, maka tidak syak lagi ketaksamaan adalah benar. Selanjutnya, jika pokok itu mempunyai lebih daripada dua daun, maka kita membelah pokok m yang panjang kepada dua subpokok. Mengikut prinsip aruhan, kami menganggap bahawa ketaksamaan adalah benar untuk setiap cabang ketinggian m -1 atau kurang. Mengikut prinsip aruhan, menggunakan ketaksamaan pada setiap cabang. Mari kita nyatakan panjang kod cabang K "dan K" ". Apabila dua cabang pokok itu digabungkan, panjang setiap dahan bertambah sebanyak 1, oleh itu, panjang kod itu terdiri daripada jumlah K' / 2 dan K '' / 2,

Teorem dibuktikan.

Pertimbangkan bukti teorem Macmillan. Kami menggunakan ketidaksamaan Kraft pada kod penyahkodan yang tidak diselaraskan. Buktinya adalah berdasarkan fakta bahawa untuk sebarang nombor K> 1 kuasa ke-n nombor itu pasti lebih besar daripada fungsi linear n, di mana n ialah nombor yang agak besar. Kami meningkatkan ketidaksamaan Kraft kepada kuasa ke-n dan mewakili ungkapan sebagai jumlah

Di mana Nk ialah bilangan aksara panjang k, penjumlahan bermula dengan panjang minimum perwakilan aksara ke-n dan berakhir dengan panjang maksimum nl, dengan l ialah panjang maksimum aksara yang dikodkan. Ia berikutan daripada keperluan penyahkodan unik itu. Jumlahnya dibentangkan dalam borang

Jika K> 1, maka adalah perlu untuk menetapkan n cukup besar untuk ketaksamaan menjadi palsu. Oleh itu, k<= 1; теорема Макмиллана доказана.

Pertimbangkan beberapa contoh aplikasi ketaksamaan Kraft. Bolehkah terdapat kod yang dinyahkod secara unik dengan panjang 1, 3, 3, 3? Ya, sejak

Bagaimana dengan panjang 1, 2, 2, 3? Kira mengikut formula

Ketaksamaan dilanggar! Terdapat terlalu banyak aksara pendek dalam kod ini.

Kod titik (kod koma) ialah kod yang terdiri daripada 1 aksara, berakhir dengan 0 aksara, kecuali aksara terakhir, yang terdiri daripada kesemuanya. Salah satu kes istimewa ialah kod

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5 = 11111.

Untuk kod ini, kami memperoleh ungkapan untuk ketaksamaan Kraft

Dalam kes ini, kita mencapai kesaksamaan. Adalah mudah untuk melihat bahawa untuk kod titik, ketidaksamaan Kraft merosot menjadi kesamaan.

Apabila membina kod, anda perlu memberi perhatian kepada jumlah Kraft. Jika jumlah Kraft mula melebihi 1, maka ini adalah isyarat tentang keperluan untuk memasukkan aksara dengan panjang yang berbeza untuk mengurangkan purata panjang kod.

Perlu diingat bahawa ketidaksamaan Kraft tidak bermakna kod ini dinyahkod secara unik, tetapi terdapat kod dengan aksara dengan panjang sedemikian yang dinyahkod secara unik. Untuk membina kod unik yang dinyahkod, anda boleh menetapkan nombor binari kepada panjang yang sepadan dalam bit li. Sebagai contoh, untuk panjang 2, 2, 3, 3, 4, 4, 4, 4 kita memperoleh ketaksamaan Kraft

Oleh itu, kod penstriman ternyahkod yang unik mungkin wujud.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

Saya ingin menarik perhatian anda kepada perkara yang sebenarnya berlaku apabila kita bertukar idea. Sebagai contoh, pada masa ini, saya ingin memindahkan idea dari kepala saya kepada idea anda. Saya menyebut beberapa perkataan yang saya percaya anda akan dapat memahami (mendapat) idea ini.

Tetapi apabila anda kemudiannya ingin menyampaikan idea ini kepada rakan anda, anda hampir pasti akan mengatakan perkataan yang sama sekali berbeza. Pada hakikatnya, makna atau makna tidak terhad kepada mana-mana perkataan tertentu. Saya telah menggunakan beberapa perkataan, tetapi anda boleh menggunakan perkataan yang sama sekali berbeza untuk menyampaikan idea yang sama. Oleh itu, perkataan yang berbeza boleh menyampaikan maklumat yang sama. Tetapi, sebaik sahaja anda memberitahu lawan bicara anda bahawa anda tidak memahami mesej itu, maka sebagai peraturan, untuk menyampaikan maksudnya, lawan bicara akan memilih satu lagi set perkataan, kedua atau bahkan sepertiga. Oleh itu, maklumat tidak terkandung dalam set perkataan tertentu. Sebaik sahaja anda menerima kata-kata ini atau itu, kemudian lakukan kerja yang hebat untuk menterjemah perkataan ke dalam idea yang ingin disampaikan oleh lawan bicara kepada anda.

Kami belajar memilih perkataan untuk menyesuaikan diri dengan lawan bicara. Dari satu segi, kami memilih perkataan dengan memadankan pemikiran kami dan tahap hingar dalam saluran, walaupun perbandingan ini tidak menggambarkan dengan tepat model yang saya gunakan untuk mewakili bunyi dalam proses penyahkodan. Dalam organisasi besar, ketidakupayaan untuk mendengar apa yang orang lain katakan adalah masalah utama. Dalam jawatan kanan, pekerja mendengar "apa yang mereka mahu dengar". Dalam sesetengah kes, anda perlu mengingati perkara ini semasa anda menaiki tangga kerjaya. Penyampaian maklumat dalam bentuk formal adalah gambaran sebahagian daripada proses dari kehidupan kita dan telah menemui aplikasi yang meluas jauh melangkaui sempadan peraturan formal dalam aplikasi komputer.

Akan bersambung...

Siapa yang ingin membantu dengan terjemahan, susun atur dan penerbitan buku - tulis dalam peribadi atau e-mel [e-mel dilindungi]

Ngomong-ngomong, kami juga telah melancarkan terjemahan buku yang paling hebat -

Pengekodan. Konsep asas.

Pelbagai kaedah pengekodan telah digunakan secara meluas dalam amalan manusia sejak dahulu lagi. Sebagai contoh, tatatanda kedudukan perpuluhan ialah cara pengekodan nombor asli. Satu lagi cara pengekodan nombor asli ialah angka Rom, dan kaedah ini lebih visual dan semula jadi, sesungguhnya, jari - I, lima - V, dua lima - X. Walau bagaimanapun, dengan kaedah pengekodan ini, lebih sukar untuk melakukan operasi aritmetik pada nombor yang besar, jadi ia digantikan dengan pengekodan kaedah berdasarkan tatatanda perpuluhan kedudukan. Daripada contoh ini, kita boleh membuat kesimpulan bahawa pelbagai kaedah pengekodan mempunyai ciri khusus yang wujud hanya kepada mereka, yang, bergantung pada matlamat pengekodan, boleh menjadi sama ada kelebihan kaedah pengekodan tertentu atau kelemahannya.

Kaedah pengekodan berangka objek geometri dan kedudukannya dalam ruang diketahui secara meluas: Koordinat Cartesian dan koordinat kutub. Dan kaedah pengekodan ini berbeza dalam ciri khusus yang wujud.

Sehingga abad ke-20, kaedah dan alat pengekodan memainkan peranan tambahan, tetapi dengan kemunculan komputer, keadaan berubah secara radikal. Pengekodan digunakan secara meluas dalam teknologi maklumat dan sering menjadi isu utama dalam menyelesaikan pelbagai masalah seperti:

- pembentangan data yang bersifat sewenang-wenang (nombor, teks, grafik) dalam ingatan komputer;

- penghantaran data yang optimum melalui saluran komunikasi;

- perlindungan maklumat (mesej) daripada capaian yang tidak dibenarkan;

- memastikan imuniti bunyi semasa penghantaran data melalui saluran komunikasi;

- pemampatan maklumat.

Dari sudut pandangan teori maklumat, pengekodan adalah proses perbandingan yang tidak jelas abjad sumber mesej dan set simbol bersyarat tertentu, dijalankan mengikut peraturan tertentu, dan kod (abjad kod) adalah set lengkap. (set) simbol bersyarat yang berbeza (simbol kod) yang boleh digunakan untuk pengekodan mesej asal dan yang mungkin dengan peraturan pengekodan yang diberikan. Bilangan simbol kod berbeza yang membentuk abjad kod dipanggil volum kod atau volum abjad kod. Jelas sekali, volum abjad kod tidak boleh kurang daripada volum abjad mesej asal yang dikodkan. Oleh itu, pengekodan ialah transformasi mesej asal kepada koleksi atau urutan simbol kod yang mewakili mesej yang dihantar melalui saluran komunikasi.

Pengekodan boleh menjadi berangka (digital) dan bukan angka, bergantung pada jenis simbol kod diwakili: nombor dalam mana-mana sistem nombor atau beberapa objek atau tanda lain, masing-masing.

Dalam kebanyakan kes, simbol kod ialah koleksi atau jujukan beberapa komponen paling mudah, contohnya, jujukan nombor dalam simbol kod kod berangka, yang dipanggil elemen simbol kod. Lokasi atau nombor siri unsur dalam kata kod ditentukan oleh kedudukannya.

Bilangan elemen watak kod yang digunakan untuk mewakili satu aksara abjad sumber asal mesej dipanggil nilai kod. Jika nilai kod adalah sama untuk semua simbol abjad mesej asal, maka kod itu dipanggil seragam, jika tidak - tidak sekata. Bilangan elemen yang termasuk dalam simbol kod kadangkala dipanggil panjang simbol kod.

Dari sudut pandangan redundansi, semua kod boleh dibahagikan kepada kod bukan redundan dan kod redundan. Dalam kod lewah, bilangan elemen simbol kod boleh dikurangkan kerana penggunaan elemen selebihnya yang lebih cekap, dalam kod bukan lewah, pengurangan bilangan elemen dalam simbol kod adalah mustahil.

Masalah pengekodan jika tiada gangguan dan kehadirannya adalah berbeza dengan ketara. Oleh itu, perbezaan dibuat antara pengekodan yang cekap (entropi) dan pengekodan pembetulan (pembetulan ralat). Dengan pengekodan yang cekap, tugasnya adalah untuk mencapai perwakilan aksara abjad sumber mesej dengan bilangan minimum elemen simbol kod secara purata bagi setiap satu aksara abjad sumber mesej dengan mengurangkan lebihan kod, yang membawa kepada peningkatan dalam kadar penghantaran mesej. Dan dengan pengekodan pembetulan (pembetulan ralat), tugasnya adalah untuk mengurangkan kebarangkalian ralat dalam penghantaran simbol abjad asal dengan mengesan dan membetulkan ralat dengan memperkenalkan redundansi tambahan kod.

Tugas pengekodan yang berasingan adalah untuk melindungi mesej daripada akses, herotan dan pemusnahan yang tidak dibenarkan. Dengan pengekodan jenis ini, mesej dikodkan dengan cara yang walaupun telah menerimanya, penyerang tidak akan dapat menyahkodnya. Proses pengekodan mesej jenis ini dipanggil penyulitan (atau penyulitan), dan proses penyahkodan dipanggil penyahsulitan (atau penyahsulitan). Mesej yang dikodkan itu sendiri dipanggil disulitkan (atau hanya penyulitan), dan kaedah pengekodan yang digunakan dipanggil sifir.

Selalunya, kaedah pengekodan dibezakan ke dalam kelas yang berasingan, yang membolehkan membina (tanpa kehilangan maklumat) kod mesej yang lebih pendek panjangnya daripada mesej asal. Teknik pengekodan sedemikian dipanggil teknik pemampatan atau pembungkusan data. Kualiti mampatan ditentukan oleh nisbah mampatan, yang biasanya diukur sebagai peratusan dan yang menunjukkan berapa banyak mesej yang dikodkan lebih pendek daripada yang asal.

Dalam pemprosesan automatik maklumat menggunakan komputer, sebagai peraturan, pengekodan berangka (digital) digunakan, dan, secara semula jadi, persoalan mewajarkan sistem nombor yang digunakan timbul. Sesungguhnya, dengan penurunan dalam asas sistem nombor, abjad unsur-unsur simbol kod dipermudahkan, tetapi simbol kod dipanjangkan. Sebaliknya, lebih besar asas sistem nombor, lebih sedikit bilangan digit yang diperlukan untuk mewakili satu simbol kod, dan, akibatnya, lebih pendek masa untuk penghantarannya, tetapi dengan pertumbuhan asas sistem nombor , keperluan untuk saluran komunikasi dan cara teknikal untuk mengenali isyarat asas meningkat dengan ketara sepadan dengan pelbagai elemen simbol kod. Khususnya, kod nombor yang ditulis dalam sistem binari secara purata lebih kurang 3.5 kali lebih panjang daripada kod perpuluhan. Oleh kerana dalam semua sistem pemprosesan maklumat adalah perlu untuk menyimpan tatasusunan maklumat yang besar dalam bentuk maklumat berangka, salah satu kriteria penting untuk memilih abjad unsur-unsur simbol kod berangka (iaitu, asas sistem nombor yang digunakan ) adalah untuk meminimumkan bilangan elemen elektronik dalam peranti storan, serta kesederhanaan dan kebolehpercayaannya.

Apabila menentukan bilangan elemen elektronik yang diperlukan untuk menetapkan setiap elemen simbol kod, adalah perlu untuk meneruskan dari andaian praktikal yang wajar bahawa ini memerlukan bilangan elemen elektronik paling mudah (contohnya, transistor) yang sama dengan pangkalan sistem nombor a... Kemudian untuk storan dalam beberapa peranti n elemen aksara kod akan diperlukan M unsur elektronik:

M = a n. (2.1)

Bilangan terbesar nombor berbeza yang boleh direkodkan dalam peranti ini N:

N = a n.

Mengambil logaritma ungkapan ini dan menyatakan daripadanya n kita mendapatkan:

n= ln N/ ln a.

Mengubah ungkapan (2.1) kepada bentuk

M= a ∙ ln N/ ln a(2.2)

adalah mungkin untuk menentukan pada asas logaritma a jumlah elemen M akan menjadi minimum untuk sesuatu yang diberikan N... Membezakan dengan a fungsi M = f (a) dan menyamakan terbitannya kepada sifar, kita dapat:

Jelas sekali, untuk mana-mana terhingga a

ln N/ ln 2 a ≠ 0

dan oleh itu

ln a - 1 = 0,

di mana a = e ≈ 2.7.

Oleh kerana radix hanya boleh menjadi integer, maka a dipilih sama dengan 2 atau 3. Sebagai contoh, mari kita tetapkan kapasiti maksimum peranti storan N= 10 6 nombor. Kemudian untuk asas sistem nombor yang berbeza ( a)jumlah unsur ( M) dalam peranti storan sedemikian, mengikut ungkapan (2.2), yang berikut (Jadual 2.1):

Jadual 2.1.

a
M	39,2	38,2	39,2	42,9		91,2

Oleh itu, jika kita meneruskan daripada meminimumkan jumlah peralatan, maka yang paling berfaedah ialah sistem nombor binari, ternari dan kuaternari, yang hampir dalam parameter ini. Tetapi oleh kerana pelaksanaan teknikal peranti yang beroperasi dalam sistem nombor binari adalah lebih mudah, yang paling meluas dalam pengekodan berangka adalah kod berdasarkan sistem nombor asas 2.

Merupakan cabang teori maklumat yang mengkaji cara mengenal pasti mesej dengan isyarat yang mencerminkannya. Tugas teori pengekodan adalah untuk memadankan sumber maklumat dengan saluran komunikasi.

Objek pengekodan ialah maklumat diskret dan berterusan yang datang kepada pengguna melalui sumber maklumat. Konsep pengekodan bermaksud menukar maklumat ke dalam bentuk yang mudah untuk dihantar melalui saluran komunikasi tertentu.

Operasi terbalik - penyahkodan - terdiri daripada memulihkan mesej yang diterima daripada borang yang dikodkan kepada yang diterima umum yang tersedia untuk pengguna.

Terdapat beberapa arahan dalam teori pengekodan:

• pengekodan statik atau cekap;
• pengekodan anti-jamming;
• kod pembetulan;
• kod kitaran;
• kod aritmetik.

Dengan kemunculan sistem kawalan, khususnya komputer, peranan pengekodan telah meningkat dan berubah dengan ketara, kerana penghantaran maklumat adalah mustahil tanpa pengekodan. Baru-baru ini, berkaitan dengan pembangunan sistem telekomunikasi dan penggunaan meluas teknologi komputer untuk memproses dan menyimpan maklumat, bidang pengetahuan baru telah timbul - keselamatan maklumat.

Pengekodan ialah cara universal untuk memaparkan maklumat semasa penyimpanan, pemprosesan dan penghantarannya dalam bentuk sistem korespondensi antara isyarat dan elemen mesej, dengan bantuan elemen ini boleh diperbaiki.

Kod ialah peraturan untuk menukar mesej secara jelas daripada satu bentuk simbolik mesej kepada yang lain, biasanya tanpa kehilangan maklumat.

Jika semua kata kod mempunyai panjang yang sama, maka kod itu dipanggil seragam, atau blok.

Dengan abjad abstrak yang kami maksudkan adalah set simbol diskret yang tersusun.

Pengekodan abjad. Abjad, i.e. huruf demi huruf, pengekodan boleh ditetapkan oleh jadual kod. Sebenarnya, kod penukaran adalah sejenis penggantian.

Di mana abjad A, set perkataan yang terdiri dalam abjad B. Set kod huruf dipanggil set kod asas. Pengekodan abjad boleh digunakan untuk sebarang set mesej.

Pemprosesan data komputer adalah berdasarkan penggunaan kod binari. Kaedah pengekodan universal ini sesuai untuk sebarang data, tanpa mengira asal dan kandungannya.

Pengekodan teks

Teks ialah urutan aksara yang disertakan dalam abjad tertentu. Pengekodan teks dikurangkan kepada pengekodan binari abjad atas dasar ia dibina. Pengekodan bait abjad yang paling biasa digunakan. Dalam kes ini, kardinaliti maksimum abjad ialah 256 aksara. Abjad sedemikian boleh mengandungi dua set aksara abjad (contohnya, Rusia dan Latin), nombor, tanda baca dan tanda matematik, ruang dan sebilangan kecil aksara tambahan. Contoh abjad sedemikian ialah kod ASCII.

Walau bagaimanapun, set terhad 256 kod aksara tidak lagi memenuhi keperluan komunikasi antarabangsa yang semakin meningkat. Sistem pengekodan aksara 16-bit universal UNICODE semakin meluas.

Kuasa abjad dalam sistem pengekodan UNICODE ialah 216 = 65 536 kod berbeza, di mana 63 484 kod sepadan dengan aksara kebanyakan abjad, dan baki 2048 kod dibahagikan kepada separuh dan membentuk jadual 1024 lajur x 1024 baris . Terdapat lebih sejuta sel dalam jadual ini, yang boleh memuatkan lebih sejuta aksara berbeza. Ini adalah simbol bahasa "mati", serta simbol yang tidak mempunyai kandungan leksikal, petunjuk, tanda, dsb. Aksara tambahan ini memerlukan sepasang perkataan 16-bit (16-bit untuk nombor baris dan 16-bit untuk nombor lajur).

Oleh itu, sistem UNICODE ialah sistem pengekodan sejagat untuk semua simbol sistem tulisan kebangsaan dan mempunyai keupayaan untuk berkembang dengan ketara.

Pengekodan imej

Lukisan, gambar, foto dikodkan dalam format raster... Dalam paparan ini, setiap imej ialah jadual segi empat tepat titik warna. Warna dan kecerahan setiap titik individu dinyatakan dalam bentuk berangka, yang membolehkan kod binari digunakan untuk mewakili data grafik.

Adalah menjadi kebiasaan untuk mewakili imej hitam dan putih dalam skala kelabu; untuk ini, model Skala Kelabu digunakan. Jika kecerahan titik dikodkan dalam satu bait, 256 ton kelabu berbeza boleh digunakan. Ketepatan ini konsisten dengan sensitiviti mata manusia dan keupayaan teknologi percetakan.

Apabila mengekod imej warna, prinsip penguraian warna kepada komponen digunakan; untuk ini, model RGB digunakan. Imej warna pada skrin diperoleh dengan mencampurkan tiga warna asas: merah (Merah, R), biru (Biru, B) dan hijau (Hijau, G).

Setiap piksel pada skrin terdiri daripada tiga elemen jarak rapat yang bersinar dengan warna ini.

Paparan warna menggunakan prinsip ini dipanggil monitor RGB.

Kod warna piksel mengandungi maklumat tentang perkadaran setiap warna asas.

skema pembentukan warna

Jika ketiga-tiga komponen mempunyai keamatan (kecerahan) yang sama, maka 8 warna berbeza boleh diperoleh daripada gabungannya (23):

			coklat

Pembentukan warna pada kedalaman warna 24-bit:

Lebih besar kedalaman warna, lebih luas julat warna yang tersedia dan lebih tepat perwakilannya dalam imej yang didigitalkan. Piksel dengan kedalaman sedikit sama dengan satu hanya mempunyai 2 (dalam kuasa pertama) keadaan yang mungkin - dua warna: hitam atau putih. Piksel dengan sedikit kedalaman 8 mempunyai 28 atau 256 nilai warna yang mungkin. Piksel dengan sedikit kedalaman 24 unit mempunyai 224 darjah) atau 16.7 juta nilai yang mungkin. Adalah dipercayai bahawa imej 24-bit, yang mengandungi 16.7 juta warna, menghasilkan semula warna dunia di sekeliling kita dengan tepat. Biasanya, resolusi bit ditentukan dalam julat dari 1 hingga 48 bit / piksel.

Apabila mencetak di atas kertas, model warna yang sedikit berbeza digunakan: jika monitor memancarkan cahaya, warna diperoleh hasil daripada penambahan warna, kemudian cat menyerap cahaya, warna dikurangkan. Oleh itu, cat cyan (Cyan, C), magenta (Magenta, M) dan kuning (Kuning, Y) digunakan sebagai yang utama. Di samping itu, disebabkan ketidaksempurnaan pewarna, satu perempat biasanya ditambah kepada mereka - hitam (hitam, K). Untuk menyimpan maklumat tentang setiap cat, dan dalam kes ini, 1 bait paling kerap digunakan. Sistem pengekodan ini dipanggil CMYK.

Perwakilan warna yang lebih kasar menggunakan lebih sedikit bit. Sebagai contoh, pengekodan grafik warna dengan nombor 16-bit dipanggil Warna Tinggi. Dalam kes ini, lima digit diberikan kepada setiap warna.

Pengekodan audio dan video

Teknik untuk bekerja dengan maklumat bunyi datang kepada teknologi komputer yang terkini. Kaedah pengekodan analitikal yang digunakan untuk sebarang isyarat audio adalah berdasarkan penukaran analog-ke-digital. Isyarat analog asal diwakili sebagai urutan isyarat digital yang direkodkan dalam kod binari. Bit penukaran menentukan jumlah data yang sepadan dengan isyarat digital tunggal. Apabila memainkan bunyi, lakukan penukaran digital-ke-analog songsang.

Kaedah pengekodan ini mengandungi ralat, supaya isyarat yang dihasilkan semula sedikit berbeza daripada yang asal.

Kaedah pengekodan sintesis jadual hanya terpakai kepada sekeping muzik. Sampel (sampel) bunyi pelbagai alat muzik disimpan dalam jadual yang disediakan. Kod angka mentakrifkan instrumen, nota dan tempoh.

Apabila mengekod isyarat video, anda perlu merakam urutan imej (bingkai) dan bunyi (lagu bunyi). Format rakaman video membolehkan kedua-dua aliran data dimasukkan dalam satu jujukan digital.

04.04.2006 Leonid Chernyak Kategori: Teknologi

"Sistem Terbuka" Penciptaan komputer adalah mustahil jika teori pengekodan isyarat tidak dicipta serentak dengan "penampilan mereka. Teori pengekodan" adalah salah satu bidang matematik yang mempengaruhi perkembangan pengkomputeran dengan ketara.

"Sistem Terbuka"

Penciptaan komputer adalah mustahil jika teori pengekodan isyarat tidak dicipta serentak dengan penampilannya.

Teori pengekodan adalah salah satu bidang matematik yang sangat mempengaruhi perkembangan pengkomputeran. Skopnya meluas kepada penghantaran data melalui saluran sebenar (atau bising), dan subjeknya adalah untuk memastikan ketepatan maklumat yang dihantar. Dalam erti kata lain, ia mempelajari cara terbaik untuk membungkus data supaya selepas isyarat dihantar, maklumat berguna boleh dipercayai dan mudah diekstrak daripada data. Kadangkala teori pengekodan dikelirukan dengan penyulitan, tetapi ini tidak benar: kriptografi menyelesaikan masalah yang bertentangan, tujuannya adalah untuk menyukarkan mendapatkan maklumat daripada data.

Keperluan untuk mengekod data pertama kali ditemui lebih daripada 150 tahun yang lalu, sejurus selepas penciptaan telegraf. Saluran itu mahal dan tidak boleh dipercayai, yang menjadikan tugas untuk meminimumkan kos dan meningkatkan kebolehpercayaan penghantaran telegram menjadi mendesak. Masalah itu diburukkan lagi dengan pemasangan kabel transatlantik. Sejak 1845, buku kod khas telah mula digunakan; ia digunakan oleh pengendali telegraf untuk "memampatkan" mesej secara manual, menggantikan urutan perkataan biasa dengan kod yang lebih pendek. Pada masa yang sama, untuk memeriksa ketepatan penghantaran, mereka mula menggunakan kawalan pariti, kaedah yang digunakan untuk memeriksa ketepatan memasukkan kad tebuk juga dalam komputer generasi pertama dan kedua. Untuk melakukan ini, kad yang disediakan khas dengan checksum telah dimasukkan ke dalam dek yang dimasukkan. Jika peranti input tidak begitu boleh dipercayai (atau dek terlalu besar), maka ralat boleh berlaku. Untuk membetulkannya, prosedur kemasukan diulang sehingga jumlah semak yang dikira sepadan dengan yang disimpan pada kad. Skim ini bukan sahaja janggal, ia juga terlepas kesilapan berganda. Dengan pembangunan saluran komunikasi, mekanisme kawalan yang lebih berkesan diperlukan.

Penyelesaian teori pertama untuk masalah penghantaran data melalui saluran bising telah dicadangkan oleh Claude Shannon, pengasas teori statistik maklumat. Shannon adalah bintang pada zamannya, dia adalah salah seorang elit akademik AS. Sebagai pelajar siswazah Vannevar Bush, pada tahun 1940 beliau menerima Hadiah Nobel (jangan dikelirukan dengan Hadiah Nobel!), Dianugerahkan kepada saintis di bawah umur 30 tahun. Semasa bekerja di Bell Labs, Shannon menulis The Mathematical Theory of Message Transmission (1948), di mana beliau menunjukkan bahawa jika lebar jalur saluran lebih tinggi daripada entropi sumber mesej, maka mesej boleh dikodkan supaya ia akan dihantar. tanpa berlengah-lengah. Kesimpulan ini terkandung dalam salah satu teorem yang dibuktikan oleh Shannon, maksudnya berpunca daripada fakta bahawa jika terdapat saluran dengan lebar jalur yang mencukupi, mesej boleh dihantar dengan beberapa kelewatan masa. Di samping itu, dia menunjukkan kemungkinan teori penghantaran yang boleh dipercayai dengan kehadiran bunyi dalam saluran. Formula C = W log ((P + N) / N), diukir pada monumen sederhana Shannon, didirikan di kampung halamannya di Michigan, dibandingkan nilainya dengan formula Albert Einstein E = mc 2.

Kerja-kerja Shannon memberi makanan untuk banyak penyelidikan lanjut dalam bidang teori maklumat, tetapi mereka tidak mempunyai aplikasi kejuruteraan praktikal. Peralihan daripada teori kepada amalan telah dimungkinkan oleh usaha Richard Hamming, rakan sekerja Shannon di Bell Labs, yang menjadi terkenal kerana penemuan kelas kod yang kemudiannya dipanggil "Kod Hamming." Terdapat legenda bahawa penciptaan kod Hamming mereka didorong oleh kesulitan bekerja dengan kad tebuk pada mesin pengira geganti Bell Model V pada pertengahan 40-an. Dia diberi masa untuk bekerja pada mesin pada hujung minggu apabila tiada operator, dan dia sendiri terpaksa bermain-main dengan input. Walau apa pun, tetapi Hamming mencadangkan kod yang boleh membetulkan ralat dalam saluran komunikasi, termasuk talian penghantaran data dalam komputer, terutamanya antara pemproses dan memori. Kod Hamming memberikan bukti bagaimana kemungkinan yang ditunjukkan oleh teorem Shannon boleh direalisasikan secara praktikal.

Hamming menerbitkan artikelnya pada tahun 1950, walaupun teori pengekodannya bermula pada tahun 1947 dalam laporan dalaman. Oleh itu, ada yang percaya bahawa Hamming harus dianggap sebagai bapa teori pengekodan, bukan Shannon. Walau bagaimanapun, adalah sia-sia untuk mencari bekas dalam sejarah teknologi.

Apa yang pasti ialah Hamming yang mula-mula mencadangkan Kod Pembetulan Ralat (ECC). Pengubahsuaian moden kod ini digunakan dalam semua sistem penyimpanan data dan untuk pertukaran antara pemproses dan memori utama. Salah satu daripada varian mereka, kod Reed-Solomon digunakan dalam CD, membolehkan anda memainkan rekod tanpa bunyi decitan dan bunyi yang boleh menyebabkan calar dan zarah debu. Terdapat banyak versi kod berdasarkan Hamming, ia berbeza dalam algoritma pengekodan dan bilangan bit cek. Kod sedemikian telah memperoleh kepentingan khusus berkaitan dengan pembangunan komunikasi ruang jarak jauh dengan stesen antara planet, sebagai contoh, terdapat kod Reed-Muller, di mana terdapat 32 bit kawalan untuk tujuh bit maklumat, atau 26 untuk enam.

Antara kod ECC terbaharu ialah kod LDPC (Low-Density Parity-check Code). Malah, mereka telah dikenali selama tiga puluh tahun, tetapi minat khusus terhadap mereka telah didedahkan dengan tepat dalam beberapa tahun kebelakangan ini, apabila televisyen definisi tinggi mula berkembang. Kod LDPC tidak 100% tepat, tetapi kadar ralat boleh dilaraskan ke tahap yang dikehendaki dan lebar jalur digunakan sebaik mungkin. Berdekatan dengannya ialah "Kod Turbo", ia berkesan apabila bekerja dengan objek dalam ruang dalam dan lebar jalur terhad.

Nama Vladimir Aleksandrovich Kotelnikov tercatat kukuh dalam sejarah teori pengekodan. Pada tahun 1933, dalam "Bahan mengenai komunikasi radio untuk Kongres Pertama Semua-Kesatuan mengenai pembinaan semula teknikal komunikasi," beliau menerbitkan karya "Pada lebar jalur udara?" dan? wayar?" Nama Kotelnikov, sebagai sama, termasuk dalam tajuk salah satu teorem teori pengekodan yang paling penting. Teorem ini mentakrifkan keadaan di mana isyarat yang dihantar boleh dipulihkan tanpa kehilangan maklumat.

Teorem ini dipanggil dengan pelbagai nama, termasuk "teorem WKS" (singkatan WKS diambil daripada Whittaker, Kotelnikov, Shannon). Sesetengah sumber menggunakan kedua-dua teorem persampelan Nyquist-Shannon dan teorem persampelan Whittaker-Shannon, dan dalam buku teks universiti Rusia, yang paling biasa ialah "teorem Kotelnikov". Malah, teorem itu mempunyai sejarah yang lebih panjang. Bahagian pertamanya telah dibuktikan pada tahun 1897 oleh ahli matematik Perancis Emile Borel. Edmund Whittaker membuat sumbangannya pada tahun 1915. Pada tahun 1920, Kinnosuki Ogura Jepun menerbitkan pindaan kepada penyelidikan Whittaker, dan pada tahun 1928 Harry Nyquist Amerika menjelaskan prinsip pendigitan dan memulihkan isyarat analog.

Claude Shannon(1916 - 2001) dari tahun sekolah menunjukkan minat yang sama dalam matematik dan kejuruteraan elektrik. Pada tahun 1932 beliau memasuki Universiti Michigan, pada tahun 1936 - di Institut Teknologi Massachusetts, dari mana beliau menamatkan pengajian pada tahun 1940, menerima dua ijazah - sarjana dalam kejuruteraan elektrik dan doktor falsafah dalam matematik. Pada tahun 1941, Shannon menyertai Bell Laboratories. Di sini dia mula mengembangkan idea yang kemudiannya menghasilkan teori maklumat. Pada tahun 1948, Shannon menerbitkan artikel "Teori Komunikasi Matematik", di mana idea asas saintis dirumuskan, khususnya, penentuan jumlah maklumat melalui entropi, dan juga mencadangkan satu unit maklumat yang menentukan pilihan dua pilihan yang sama kemungkinan, iaitu, apa yang kemudiannya dipanggil sedikit ... Pada 1957-1961, Shannon menerbitkan karya di mana dia membuktikan teorem mengenai kapasiti saluran komunikasi yang bising, yang kini membawa namanya. Pada tahun 1957, Shannon menjadi profesor di Massachusetts Institute of Technology, dari mana dia bersara 21 tahun kemudian. Pada "persaraan yang wajar" Shannon menyerah sepenuhnya kepada semangatnya yang telah lama bergelar juggling. Dia membina beberapa mesin juggling dan juga membangunkan teori umum juggling.

Richard Hamming(1915 - 1998) memulakan pendidikannya di Universiti Chicago, di mana beliau menerima ijazah sarjana muda pada tahun 1937. Pada tahun 1939 beliau menerima ijazah sarjana dari Universiti Nebraska dan Ph.D dalam matematik dari Universiti Illinois. Pada tahun 1945, Hamming mula bekerja sebagai sebahagian daripada Projek Manhattan, sebuah projek penyelidikan kerajaan berskala besar untuk mencipta bom atom. Pada tahun 1946, Hamming pergi bekerja di Bell Telephone Laboratories, di mana dia bekerja dengan Claude Shannon. Pada tahun 1976, Hamming menerima kerusi di Sekolah Siswazah Tentera Laut di Monterey, California.

Karya yang menjadikannya terkenal, kajian asas pengesanan ralat dan kod pembetulan, diterbitkan oleh Hamming pada tahun 1950. Pada tahun 1956, beliau bekerja pada salah satu kerangka utama awal IBM 650. Kerja beliau meletakkan asas untuk bahasa pengaturcaraan yang kemudiannya berkembang menjadi bahasa pengaturcaraan peringkat tinggi. Sebagai pengiktirafan terhadap pencapaian Hamming dalam sains komputer, IEEE telah memulakan Pingat Perkhidmatan Terbilang untuk Teori Informatik dan Sistem, yang dinamakan sempena namanya.

Vladimir Kotelnikov(1908 - 2005) pada tahun 1926 memasuki Fakulti Kejuruteraan Elektrik Sekolah Teknikal Tinggi Moscow yang dinamakan sempena N.E.Bauman (MVTU), tetapi menjadi lulusan Institut Kejuruteraan Kuasa Moscow (MEI), yang berpisah dari MVTU sebagai institut bebas. Semasa pengajian pascasiswazahnya (1931-1933) Kotelnikov secara matematik merumuskan dan membuktikan "teorem pengiraan", yang kemudiannya dinamakan sempena namanya. Selepas menamatkan pengajian dari sekolah siswazah pada tahun 1933, Kotelnikov, semasa kekal mengajar di MPEI, pergi bekerja di Institut Komunikasi Penyelidikan Saintifik Pusat (TsNIIS). Pada tahun 1941, V.A.Kotelnikov merumuskan pernyataan yang jelas tentang keperluan yang harus dipenuhi oleh sistem yang tidak dapat dihurai secara matematik, dan bukti ketidakmungkinan penyahsulitannya telah diberikan. Pada tahun 1944, Kotelnikov mengambil jawatan profesor, dekan fakulti kejuruteraan radio MPEI, di mana beliau bekerja sehingga tahun 1980. Pada tahun 1953, pada usia 45 tahun, Kotelnikov segera dipilih sebagai ahli penuh Akademi Sains USSR. Dari 1968 hingga 1990, V.A.Kotelnikov juga seorang profesor, ketua jabatan di Institut Fizik dan Teknologi Moscow.

Kelahiran teori pengekodan

Teori pengekodan. Jenis pengekodan Konsep asas teori pengekodan Sebelum ini, alat pengekodan memainkan peranan tambahan dan tidak dianggap sebagai subjek kajian matematik yang berasingan, tetapi dengan kemunculan komputer, keadaan telah berubah secara radikal. Pengekodan benar-benar meresap teknologi maklumat dan merupakan isu utama dalam menyelesaikan pelbagai (hampir semua) masalah pengaturcaraan: ۞ pembentangan data yang bersifat arbitrari (contohnya, nombor, teks, grafik) dalam ingatan komputer; ۞ perlindungan maklumat daripada capaian yang tidak dibenarkan; ۞ memastikan imuniti bunyi semasa penghantaran data melalui saluran komunikasi; ۞ pemampatan maklumat dalam pangkalan data. Teori pengekodan ialah cabang teori maklumat yang mengkaji cara mengenal pasti mesej dengan isyarat yang mewakilinya. Objektif: Untuk menyelaraskan sumber maklumat dengan saluran komunikasi. Objek: Maklumat diskret atau berterusan yang datang kepada pengguna melalui sumber maklumat. Pengekodan ialah transformasi maklumat kepada formula yang sesuai untuk penghantaran melalui saluran komunikasi tertentu. Contoh pengekodan dalam matematik ialah kaedah koordinat yang diperkenalkan oleh Descartes, yang memungkinkan untuk mengkaji objek geometri melalui ungkapan analitikal mereka dalam bentuk nombor, huruf dan gabungannya - formula. Konsep pengekodan bermaksud menukar maklumat ke dalam bentuk yang mudah untuk dihantar melalui saluran komunikasi tertentu. Penyahkodan - pemulihan mesej yang diterima daripada borang berkod ke dalam bentuk yang tersedia kepada pengguna.

Topik 5.2. Pengekodan abjad Secara umumnya, masalah pengekodan boleh diwakili seperti berikut. Biarkan diberikan dua abjad A dan B, yang terdiri daripada nombor terhingga simbol: dan. Unsur-unsur abjad dipanggil huruf. Set tertib dalam abjad A akan dipanggil perkataan, di mana ia dilambangkan dengan n = l () = | |. , nombor n menunjukkan bilangan huruf dalam perkataan dan dipanggil panjang perkataan, Perkataan kosong dilambangkan: Untuk perkataan, huruf a1 dipanggil permulaan, atau awalan, perkataan, huruf an ialah akhir, atau postfix, perkataan. , dan Perkataan boleh disambungkan. Untuk melakukan ini, awalan perkataan kedua mesti serta-merta mengikut postfix yang pertama, manakala dalam perkataan baharu mereka secara semula jadi kehilangan statusnya, melainkan salah satu daripada perkataan itu kosong. Sambungan perkataan dan ditunjukkan, sambungan n perkataan yang sama ditunjukkan, lebih-lebih lagi. Set semua perkataan bukan kosong abjad A akan dilambangkan dengan A *: Set A dipanggil abjad mesej, dan set B dipanggil abjad pengekodan. Set perkataan yang disusun dalam abjad B akan dilambangkan dengan B *.

Kami menandakan dengan F pemetaan perkataan daripada abjad A kepada abjad B. Kemudian perkataan itu dipanggil kod perkataan. Pengekodan ialah cara universal untuk memaparkan maklumat semasa penyimpanan, penghantaran dan pemprosesannya dalam bentuk sistem korespondensi antara elemen mesej dan isyarat, dengan bantuan elemen ini boleh diperbaiki. Oleh itu, kod ialah peraturan untuk transformasi yang tidak jelas (iaitu, fungsi) mesej daripada satu bentuk perwakilan simbolik (abjad asal A) kepada yang lain (abjad objek B), biasanya tanpa kehilangan maklumat. Proses menukar F: A * B * → perkataan abjad asal A kepada abjad B dipanggil pengekodan maklumat. Proses menukar perkataan kembali dipanggil penyahkodan. Oleh itu, penyahkodan ialah fungsi songsang bagi F, i.e. F1. kepada perkataan Memandangkan untuk sebarang pengekodan operasi penyahkodan mesti dilakukan, pemetaan mestilah boleh diterbalikkan (bijection). Jika | B | = m, maka F dipanggil pengekodan mth, kes yang paling biasa ialah B = (0, 1) pengekodan binari. Kes inilah yang dipertimbangkan dalam perkara berikut. Jika semua kata kod mempunyai panjang yang sama, maka kod itu dipanggil seragam, atau blok. Pengekodan abjad (atau huruf demi huruf) boleh ditentukan dengan jadual kod. Beberapa jenis penggantian akan berfungsi sebagai kod atau fungsi pengekodan. Kemudian, di mana,. Pengekodan huruf demi huruf sedemikian ditandakan sebagai satu set kod asas. Pengekodan abjad boleh digunakan untuk sebarang set mesej. Oleh itu, pengekodan abjad adalah yang paling mudah dan sentiasa boleh dimasukkan pada abjad bukan kosong. ... Banyak kod huruf

CONTOH Biarkan abjad A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) B = (0, 1) diberi. Kemudian jadual pengekodan boleh menjadi pengganti:. Ini ialah pengekodan perpuluhan binari, ia adalah satu-satu dan oleh itu boleh dinyahkodkan. Walau bagaimanapun, skim ini bukan satu-dengan-satu. Sebagai contoh, satu set enam yang 111111 boleh memadankan sama ada perkataan 333 atau 77, atau 111111, 137, 3311 atau 7111 ditambah sebarang pilih atur. Skim pengekodan abjad dipanggil awalan jika kod asas satu huruf bukan awalan kod asas huruf lain. Skim pengekodan abjad dipanggil boleh dipisahkan jika mana-mana perkataan yang terdiri daripada kod asas boleh diuraikan secara unik kepada kod asas. Pengekodan abjad dengan skema yang boleh dipisahkan membolehkan penyahkodan. Dapat dibuktikan bahawa skema awalan boleh dipisahkan. Untuk skema pengekodan abjad boleh dipisahkan, panjang kod asas mesti memenuhi hubungan yang dikenali sebagai ketaksamaan Macmillan. Ketaksamaan Macmillan Jika Skim Pengekodan Abjad

adalah boleh dipisahkan, maka ketaksamaan adalah benar CONTOH Skema pengekodan abjad A = (a, b) dan B = (0, 1), boleh dipisahkan, kerana, dan, oleh itu, ketaksamaan Macmillan berlaku. kod asas huruf a ialah awalan kod asas huruf b. Topik 5.3. Pengekodan Lebihan Minimum Dalam amalan, adalah penting bahawa kod mesej adalah sesingkat mungkin. Pengekodan abjad sesuai untuk sebarang mesej, tetapi jika tiada apa yang diketahui tentang set semua perkataan abjad A, maka sukar untuk merumuskan masalah pengoptimuman dengan tepat. Walau bagaimanapun, dalam amalan, maklumat tambahan selalunya tersedia. Sebagai contoh, untuk mesej yang dibentangkan dalam bahasa semula jadi, maklumat tambahan tersebut mungkin pengedaran kebarangkalian huruf yang muncul dalam mesej. Kemudian masalah membina kod optimum memperoleh rumusan matematik yang tepat dan penyelesaian yang ketat.

Biarkan beberapa skema pengekodan abjad yang boleh dipisahkan diberikan. Kemudian mana-mana skema di mana set tertib adalah pilih atur set tertib juga akan boleh dipisahkan. Dalam kes ini, jika panjang set asas kod adalah sama, maka pilih aturnya dalam skema tidak menjejaskan panjang mesej yang dikodkan. Sekiranya panjang kod asas adalah berbeza, maka panjang kod mesej secara langsung bergantung pada kod asas yang diberikan kepada huruf mana, dan pada komposisi huruf dalam mesej. Jika mesej tertentu dan skema pengekodan tertentu ditentukan, maka pilih atur kod sedemikian boleh dipilih, di mana panjang kod mesej akan menjadi minimum. Algoritma untuk memberikan kod asas, di mana panjang kod mesej tetap S akan menjadi minimum untuk skema tetap: ۞ mengisih huruf dalam tertib menurun bagi bilangan kejadian; ۞ menyusun kod asas dalam susunan panjang menaik; ۞ letak kod mengikut huruf mengikut cara yang ditetapkan. Biarkan abjad dan kebarangkalian huruf muncul dalam mesej diberikan:

Di mana pi ialah kebarangkalian kejadian huruf ai, dan huruf dengan kebarangkalian sifar kejadian dalam mesej dikecualikan dan huruf-huruf itu disusun dalam susunan menurun kebarangkalian kejadiannya.mesej, yang ditetapkan dan ditakrifkan sebagai CONTOH. Untuk skema pengekodan abjad yang boleh dipisahkan A = (a, b), B = (0,1), dengan taburan kebarangkalian, kos pengekodan ialah, dan dengan taburan kebarangkalian, kos pengekodan ialah

Topik 5.4. Pengekodan Huffman Algoritma ini telah dicipta pada tahun 1952 oleh David Huffman. Topik 5.5. Pengekodan Aritmetik Seperti algoritma Huffman, semuanya bermula dengan jadual unsur dan kebarangkalian yang sepadan. Katakan abjad input hanya terdiri daripada tiga elemen: a1, a2 dan a3, dan pada masa yang sama P (a1) = 1/2 P (a2) = 1/3 P (a3) ​​​​= 1/6 Katakan juga bahawa kita perlu mengekod urutan a1, a1, a2, a3. Kami membahagikan selang, di mana p ialah beberapa nombor tetap, 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

anjakan dan satu elemen majoritarian dan membetulkan satu ralat mempunyai susunan (bandingkan dengan (2)). Sebagai matematik. Model pengekod dan penyahkod biasanya dipertimbangkan daripada skema elemen berfungsi dan kerumitan difahami sebagai bilangan elemen dalam litar. Untuk kelas kod yang diketahui dengan pembetulan ralat, kajian kemungkinan algoritma untuk algoritma dan algoritma dijalankan, dan sempadan atas untuk kerumitan pengekod dan penyahkod diperolehi. Beberapa perhubungan juga telah ditemui antara kadar penghantaran pengekodan, imuniti hingar pengekodan dan kerumitan penyahkod (lihat). Satu lagi arah penyelidikan dalam teori pengekodan dikaitkan dengan fakta bahawa banyak keputusan (contohnya, teorem Shannon dan terikat (3)) tidak "membina", tetapi mewakili teorem mengenai kewujudan urutan tak terhingga kod (Kn). untuk membuktikan ini menghasilkan kelas jujukan (K n) kod sedemikian, yang mana terdapat mesin Turing yang mengiktiraf bahawa perkataan arbitrari panjang l tergolong dalam set pada satu masa dan mempunyai susunan pertumbuhan yang lebih perlahan berkenaan dengan l ( contohnya, llog l). Pembinaan dan kaedah baharu tertentu untuk mendapatkan sempadan, yang dibangunkan dalam teori pengekodan, telah membawa kepada kemajuan ketara dalam soalan yang, pada pandangan pertama, sangat jauh daripada masalah tradisional teori pengekodan. Di sini adalah perlu untuk menunjukkan penggunaan kod maksimum dengan pembetulan satu ralat dalam kaedah optimum asimptotik untuk merealisasikan fungsi algebra logik oleh litar kenalan; pada dasarnya, peningkatan sempadan atas untuk ketumpatan pembungkusan semula ruang Euclidean dimensi dengan bola yang sama; mengenai penggunaan ketaksamaan (1) apabila menganggarkan kerumitan pelaksanaan dengan formula satu kelas fungsi algebra logik. Idea dan hasil teori pengekodan menemui perkembangan selanjutnya dalam masalah mensintesis litar pembetulan kendiri dan litar yang boleh dipercayai daripada unsur yang tidak boleh dipercayai. Lit.: Shannon K., Bekerja pada teori maklumat dan sibernetik, terj. daripada bahasa Inggeris., M., 1963; Berlekamp E., Teori Pengekodan Algebra, terj. daripada English, M., 1971; Peterson, W., Weldon, E., Kod pembetulan ralat, trans. daripada bahasa Inggeris, ed. ke-2, M., 1976; Matematik diskret dan masalah matematik sibernetik, v.1, Moscow, 1974, bahagian 5; Bassalygo L. A., Zyablov V. V., Pinsker M. S, "Probl. Penghantaran maklumat", 1977, v. 13, no. 3, hlm. 517; [V] Sidelnikov VM, "Mat. Sb.", 1974, jilid 95, v. 1, hlm. 148 58. V. I. Levenshtein.

Ensiklopedia Matematik. - M .: Ensiklopedia Soviet. I. M. Vinogradov. 1977-1985.  PENGEKODAN ABJAD  RUANG KOEUKLID Lihat juga dalam kamus lain:  MENyahkod - lihat Pengekodan dan penyahkodan ... Ensiklopedia Matematik  Pengekodan maklumat audio - Artikel ini hendaklah diwikified. Sila isikannya mengikut peraturan pemformatan artikel. Pengekodan bunyi menggunakan PC adalah berdasarkan proses menukar getaran udara kepada getaran elektrik ... Imej kod Wikipedia), dilakukan mengikut definisi. peraturan, agregat kepada rykh dipanggil. cipher K., ... ... Ensiklopedia Falsafah  PENGEDUAN MAKLUMAT - mewujudkan kesesuaian antara elemen mesej dan isyarat, dengan bantuan elemen ini boleh diperbaiki. Biarkan B, set elemen mesej, A abjad dengan simbol, Biarkan urutan terhingga simbol dipanggil. perkataan dalam ... ... Ensiklopedia fizikal  PENGEDINGAN OPTIMAL - (dalam psikologi kejuruteraan) (pengekodan optimum Inggeris) penciptaan kod yang memastikan kelajuan dan kebolehpercayaan maksimum menerima dan memproses maklumat tentang objek kawalan oleh pengendali manusia (lihat Penerimaan Maklumat, Penyahkodan). Masalah K. o. ... ... Ensiklopedia psikologi besar  MENyahkod (dalam psikologi kejuruteraan) - (ms lihat Pengekodan ... ... Ensiklopedia psikologi besar

 Penyahkodan - pemulihan mesej yang dikodkan oleh isyarat yang dihantar dan diterima (lihat Pengekodan) ... Kamus Ekonomi dan Matematik  PENGEkodan - PENGEkodan. Salah satu peringkat pengeluaran pertuturan, manakala "penyahkodan" ialah penerimaan dan tafsiran, proses memahami mesej ucapan. Lihat psikolinguistik ... Kamus baharu istilah dan konsep metodologi (teori dan amalan pengajaran bahasa)  PENGEDINGAN - (Pengekodan Bahasa Inggeris). 1. Penukaran isyarat daripada satu bentuk tenaga kepada yang lain 2. Penukaran satu sistem isyarat atau tanda kepada yang lain, yang sering juga dipanggil "transcoding", "perubahan kod" (untuk pertuturan, "terjemahan"). 3. K. (mnemonik) ... ... Ensiklopedia Besar Psikologi  Penyahkodan - Rencana ini adalah mengenai kod dalam teori maklumat, untuk makna lain perkataan ini lihat kod (makna). Kod adalah peraturan (algoritma) untuk memadankan setiap mesej tertentu dengan gabungan simbol (tanda) (atau isyarat) yang ditakrifkan dengan ketat. Juga dipanggil kod ... ... Pengekodan optimum Mesej yang sama boleh dikodkan dengan cara yang berbeza. Pengekodan secara optimum akan dianggap sebagai kod di mana masa minimum dihabiskan untuk penghantaran mesej. Jika penghantaran setiap simbol asas (0 atau 1) mengambil masa yang sama, maka kod optimum ialah kod yang mempunyai panjang minimum yang mungkin. Contoh 1. Biarkan terdapat pembolehubah rawak X (x1, x2, x3, x4, x5, x6, x7, x8), yang mempunyai lapan keadaan dengan taburan kebarangkalian. 000, 001, 010, 011, 100, 101, 110 , 111 Untuk menjawab sama ada kod ini baik atau tidak, anda perlu membandingkannya dengan nilai optimum, iaitu menentukan entropi

Setelah menentukan redundansi L mengikut formula L = 1H / H0 = 12.75 / 3 = 0.084, kita melihat bahawa adalah mungkin untuk mengurangkan panjang kod sebanyak 8.4%. Persoalannya timbul: adakah mungkin untuk mengarang kod di mana satu huruf akan, secara purata, lebih sedikit aksara asas. Kod sedemikian wujud. Ini ialah kod ShannonFano dan Huffman. Prinsip membina kod optimum: 1. Setiap simbol asas mesti membawa jumlah maklumat maksimum, untuk ini adalah perlu bahawa simbol asas (0 dan 1) dalam teks yang dikodkan berlaku secara purata sama kerap. Entropi dalam kes ini akan menjadi maksimum. 2. Ia adalah perlu untuk menetapkan perkataan kod yang lebih pendek abjad sekunder kepada huruf abjad utama, yang mempunyai kebarangkalian yang tinggi.