Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Буквено неравномерно двоично кодиране на сигнали с еднаква продължителност. Префикс кодове

Както подсказва името, в методите на кодиране, принадлежащи към тази група, знаците на основната азбука (например руски) се кодират от комбинации от символи на двоичната азбука (т.е. 0 и 1), освен това, дължината на кодовете и съответно продължителността на предаване на отделен код, може да варира. Продължителността на елементарните сигнали е еднаква (τ 0 = τ 1 = τ). Очевидно е, че за прехвърлянето на информация средно по основната азбука е необходимо времето K (A, 2 ) is τ . По този начин задачата за оптимизиране на неравномерното кодиране може да бъде формулирана, както следва: изграждане на схема за кодиране, в която общата продължителност на кодовете по време на предаването (или общия брой кодове по време на съхранение) на това съобщение ще бъде най-малка. Какво прави тази оптимизация възможна? Очевидно е, че общата продължителност на съобщението ще бъде по-малка, ако се използва следният подход: тези на основната азбука, които се намират в съобщението по-често, получават по-малки кодове по дължина и за тези, чиято относителна честота е по-малка - по-дълги кодове. С други думи, кодовете на знаците на основната азбука, вероятността за поява на които в съобщението по-горе, трябва да бъдат изградени от възможно най-малкия брой елементарни сигнали, а дългите кодове трябва да се използват за знаци с малки вероятности.

Успоредно с това трябва да се реши проблемът с отличителните кодове. Представете си, че следната последователност от елементарни сигнали се получава на изхода на енкодера:

00100010000111010101110000110

Как може да се декодира? Ако кодът е еднороден, приемащото устройство просто ще пресметне дадения (фиксиран) брой елементарни сигнали (например 5, както в кода на Бодо) и ще ги интерпретира в съответствие с кодовата таблица. При използване на неравномерно кодиране са възможни два подхода, за да се направи код различен.

Първият е да се използва специална комбинация от елементарни сигнали, която се интерпретира от декодера като разделителни знаци. Вторият е в използването на кодове с префикси. Нека разгледаме по-подробно всеки от подходите.

Неравномерен код

Ние се съгласяваме, че разделителят на отделните буквени кодове ще бъде последователността 00 (знак на края на знака), а сепараторът на думите ще бъде 000 (знакът на края на думата е интервал). Следните правила за създаване на код са съвсем очевидни:

· Кодът на символа на края на знака може да бъде включен в кода на писмото, тъй като той не съществува отделно (т.е. кодът на всички букви ще завърши с 00 )

· Кодовете от букви не трябва да съдържат две или повече нули в ред в средата (в противен случай те ще се възприемат като край на знака);

· Буквеният код (с изключение на интервала) трябва винаги да започва с 1;

· Разделител на думи ( 000 ) винаги се предхожда от знак за края на знака; в този случай се изпълнява последователността 00000 (т.е. ако в края на кода се намери комбинацията ... 000 или ... 0000, те не се възприемат като сепаратор на думи); следователно кодовете на символите могат да завършват с 0 или 00 (до знака на края на знака).

В съответствие с изброените правила, ние изграждаме кодова таблица. 3.1 за буквите на руската азбука, въз основа на даденото по-горе (Таблица 2.1.) Вероятности за появата на отделни букви.

Сега, използвайки формулата (А.11), можем да намерим средната дължина на кода K ( r, 2) за този метод на кодиране:

Що се отнася до руския език, както е посочено в параграф 2.3., I 1 ( r ) = 4.356 бита, излишъкът на този код съгласно (3.5) е:

това означава, че с този метод на кодиране, ще бъде предадена приблизително 14% повече информация, отколкото съдържа оригиналното съобщение. Подобни изчисления за английския език дават стойността на K ( e, 2) = 4.716, че когато I 1 ( e ) = 4.036 бита водят до излишък на код Q ( e , 2) = 0.168.

Таблица 3.1.

След като разгледаме една от опциите за двоично неравномерно кодиране, ще се опитаме да намерим отговори на следните въпроси: възможно ли е такова кодиране без използването на символен разделител? Има ли най-ефективен (оптимален) начин за неравномерно двоично кодиране?

Същността на първия проблем е да се намери такъв вариант на кодиране на съобщение, при което последващото извличане на всеки отделен символ от него (т.е. декодиране) се оказва недвусмислено без специални индикатори за разделяне на символи. Най-простите и използваеми кодове от този тип са така наречените префикс кодове, които отговарят на следното условие (условие Fano):

Нееднаквен код може да бъде уникално декодиран, ако нито един от кодовете не съвпада с началото (префикс *) на всеки друг по-дълъг код.

* В лингвистиката терминът "префикс" означава "префикс".

Например, ако има код 110, тогава кодове 1, 11, 1101, 110101 и т.н. вече не могат да се използват. а другият започва.





Вижте също:

Йерархията на структури от данни на външни носители

въведение

Пример 4.2

Глава 8. Формализиране на представянето на алгоритми

Пример А.4

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru