Методи за конструиране на двоични кодове

2.3 Методи за конструиране на двоични кодове

От края на 60-те години компютрите се използват все по-често за обработка на текстова информация и в момента повечето компютри в света се занимават с прецизна обработка на текстова информация.

Традиционно за кодиране на един символ се използва количество информация, равно на 1 байт, т.е. 8 бита. Ако разглеждаме символите като възможни събития, тогава получаваме, че броят на различните символи, които могат да бъдат кодирани, ще бъде равен на 256. Този брой знаци е напълно достатъчен, за да представи текстова информация, включително главни и малки букви на руската и латинската азбука, както и числа, пунктуационни знаци и математически операции, графични символи и така нататък.

Но има много начини за изграждане на такива кодове, разгледайте някои от тях:

Азбучно неравномерно двоично кодиране

При азбучния метод на двоично кодиране символите на определена първична азбука (например руска) се кодират чрез комбинации от символи на двоичната азбука (т.е. 0 и 1), освен това дължината на кодовете и съответно продължителността на предаването на индивидуален код може да се различава. Можете да оптимизирате кодирането поради общата продължителност на съобщението.

Общата продължителност на съобщението ще бъде по-малка, ако приложим следния подход: отколкото буквата на първичната азбука се среща по-често, тогава ние й присвояваме по-кратък код. Следователно кодовете от букви, чиято вероятност в съобщението е по-голяма, трябва да се изграждат от възможно най-малкия брой елементарни сигнали.

Възможни са различни варианти на двоично кодиране, но не всички от тях ще бъдат подходящи за практическа употреба - важно е кодираното съобщение да може да бъде недвусмислено декодирано, т.е. така че в последователността 0 и 1, която е многобуквено кодирано съобщение, винаги би било възможно да се прави разлика между обозначенията на отделните букви.

Помислете за пример за изграждане на двоичен код за символи на руската азбука:

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

За да се улесни декодирането на съобщения, е измислен код с разделители.

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

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

- буквените кодове не трябва да съдържат две или повече нули подред в

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

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

- разделителят на думи (000) винаги се предшества от терминатор на знак;

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

Продължителността на предаване на всеки отделен код 4 очевидно може да бъде намерена: ti = ki • τ, където ki е броят на чиповете (битовете) в символния код L.

Азбучно неравномерно двоично кодиране. Префикс код

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

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

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

Например, ако има софтуерен код, тогава вече не могат да се използват кодове 1, 11, 1101, 110101 и т. Н. Ако условието на Fano е изпълнено, тогава при четене (декодиране) на кодирано съобщение чрез сравняване със списък на кодовете, винаги можете да посочите къде точно завършва един код и започва друг.

Пример: Да предположим, че имате следната таблица с префикс кодове:

Необходимо е да се декодира съобщението: 00100010000111010101110000110. Декодирането се извършва чрез циклично повторение на следните действия:

1. изрежете най-левия знак от текущото съобщение, прикачете към работната кодова дума;

2. сравнете работещата кодова дума с кодовата таблица; ако няма съвпадение, отидете на (1);

3. декодирайте работната кодова дума, изчистете я;

4. проверете дали в съобщението има повече знаци; ако да, отидете на (1).

Приложението на този алгоритъм дава:

След като приключим процедурата до края, ще получим съобщението: „Мама изми рамката“.

Оптималният метод за двоично кодиране на префикс е предложен от Д. Хъфман. Ще разгледаме конструкцията на кодовете на Хафман, като използваме следния пример: нека има първична азбука A, състояща се от шест знака a1 ... a6 с вероятностите за поява в съобщението, съответно 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Нека създадем нова спомагателна азбука Ab, като комбинираме два знака с най-ниска вероятност (a5 и a6) и ги заменим с един символ (например a (1)); вероятността за нов знак ще бъде равна на сумата от вероятностите на тези, които са го въвели, т.е. 0,15; останалите знаци от оригиналната азбука ще бъдат включени в новата без промени; общият брой знаци в новата азбука очевидно ще бъде с 1 по-малък от този в оригиналната. По същия начин ще продължим да създаваме нови азбуки, докато в последната не останат два знака; ясно е, че броят на такива

стъпките ще бъдат равни на N - 2, където N е броят на символите в оригиналната азбука (в нашия случай N = 6, следователно е необходимо да се изградят 4 спомагателни азбуки). В междинните азбуки всеки път ще пренареждаме знаците в низходящ ред на вероятностите. Цялата строителна процедура е представена под формата на таблица:

Сега ще извършим процедурата за кодиране в обратна посока. Присвояваме кодове 0 и 1 на двата знака на последната азбука (което няма значение какво; съгласни сме, че горният знак ще има код 0, а долният - 1). В нашия пример знакът a1 (4) на азбуката A (4), който има вероятност 0,6, ще получи код 0, а a2 (4), с вероятност 0,4, ще получи код 1. В азбуката A (3), знакът a1 (3) c с вероятност 0,4 ще запази своя код (1); кодовете a2 (3) и a3 (3), обединени от знака a1 (4) с вероятност 0,6, вече ще бъдат двуцифрени: първата им цифра ще бъде кодът на свързания с тях знак (т.е. 0 ), а втората цифра ще бъде като уговорена - отгоре 0, отдолу - 1; по този начин a2 (3) ще има код 00, а a3 (3) - код 01. Пълна процедура за кодиране

е представен в следната таблица:

От процедурата за конструиране на кодове е лесно да се види, че те отговарят на условието на Фано и следователно не изискват разделител. В този случай средната дължина на кода се оказва: K (2) = 0,3-2 + 0,2-2 + 0,2-2 + 0,15-3 + 0,1-4 + 0,05-4 = 2, 45

Кодът на Хафман е теоретично важен, тъй като е най-икономичен от всички възможни, т.е. За никакъв метод на кодиране по азбучен ред дължината на кода може да бъде по-малка от кода на Хафман. Може да се заключи, че съществува метод за изграждане на оптимален неравномерен азбучен код. Методът на Huffman и неговата модификация - адаптивният метод на кодиране (динамично Huffman кодиране) - намери приложение в програми за архивиране, програми за архивиране на файлове и дискове, в системи за компресиране на информация в модеми и факсове.

Единно азбучно двоично кодиране. Байтов код

В този случай двоичният код на първичната азбука се изгражда от вериги с еднаква дължина, т.е. с всички знаци се свързва еднакво количество информация, равно на 10. Не е необходимо да се предава знакът на края на знака, следователно, за да определите дължината на кодовата верига, можете да използвате формулата: K (2) > log2N. Получаващото устройство просто отброява предварително определения брой чипове и интерпретира низа (определя на кой символ отговаря). Вярно е, че в този случай неуспехите са неприемливи, например пропускането (непрочитането) на един елементарен сигнал ще доведе до промяна в цялата кодова последователност и неговата неправилна интерпретация; проблемът се решава чрез синхронизиране на предаването или по друг начин. От друга страна, използването на унифициран код се оказва едно от средствата за контрол на коректността на предаването, тъй като фактът на пристигането на допълнителен елементарен сигнал или, обратно, пристигането на непълен код веднага се интерпретира като грешка.