Начини за изграждане на двоични кодове - математика
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.
Азбучно неравномерно двоично кодиране. Префикс код
След като разгледахме една от опциите за двоично неравномерно кодиране, нека се опитаме да намерим отговори на следните въпроси: възможно ли е такова кодиране без използване на разделител на символи? Има ли най-оптимален начин за неравномерно двоично кодиране?
Същността на първия проблем е да се намери такъв вариант на кодиране на съобщението, при който последващото извличане на всеки отделен знак от него (т.е. декодиране) се оказва недвусмислено без специални знаци, разделящи символите. Най-простите и най-често използваните кодове от този тип са така наречените префикс кодове, които отговарят на следното условие (условие на Фано):