Характеристика на основните методи за кодиране на информация

Подобряване на ефективността на предаването на данни, чрез постигане на тяхната максимална скорост като една от основните цели на кодирането. Същността на метода за компресиране на информация, базиран на двоични кодиращи дървета. Разработка на софтуерни програми на Huffman Code.

Изпратете вашата добра работа в базата знания е проста. Използвайте формуляра по-долу

Студенти, аспиранти, млади учени, използващи базата от знания в своето обучение и работа, ще ви бъдат много благодарни.

Публикувано на http://www.allbest.ru

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

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

Кодирането на Huffman е прост алгоритъм за изграждане на кодове с променлива дължина, които имат минимална средна дължина. Този много популярен алгоритъм е в основата на много компютърни програми за компресиране на текстова и графична информация. Някои от тях използват алгоритъма на Хафман директно, докато други го приемат като една от стъпките в процеса на многостепенна компресия. Методът на Хъфман извършва перфектно компресиране (т.е. компресира данни до неговата ентропия), ако вероятностите на символите са точно равни на отрицателни степени на 2. Алгоритъмът започва да изгражда кодовото дърво отдолу нагоре, след което плъзга надолу по дървото, за да изгради всеки индивидуален код отдясно наляво (от най-малко значимия бит до най-значимия). От работата на Д. Хъфман през 1952 г. този алгоритъм е обект на много изследвания.

Кодовете на Хафман се преподават във всички технически университети по света и освен това са включени в програмата за напреднали компютърни науки в училище.

Следователно, изучаването на кодирането на информация и методите за кодиране, по-специално метода на кодиране на Хафман, е от значение.

Обект на изследване: кодиране и методи за кодиране на информация.

Предмет на изследване: софтуерно приложение, показващо основните принципи на кодиране, използвайки примера на кодиращия метод на Хафман.

Целта на курсовата работа е да изучи основите на информационното кодиране, по-специално метода на кодиране на Huffman, и да ги приложи в процеса на софтуерна реализация на този метод. Тази цел доведе до разпределението на следните задачи:

1) да разгледа основните понятия и принципи на кодирането на информация;

2) изследвайте метода на кодиране на Huffman,

3) разработва алгоритми и програма за внедряване на софтуерния продукт "Код на Хафман", използвайки съвременна технология за програмиране;

1. Теоретични основи на кодирането на информация

1.1 Основи и основни понятия за кодиране на информация

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

Кодирането е преобразуване на съобщенията в сигнал, т.е. конвертиране на съобщения в кодови комбинации. Кодът е система за съответствие между елементите на съобщението и комбинациите от кодове. Енкодерът е устройство, което извършва кодиране. Декодерът е устройство, което извършва обратната операция, т.е. преобразуване на кодова дума в съобщение. Азбуката е набор от възможни кодови елементи, т.е. елементарни символи (кодови символи) X =, където i = 1, 2. m. Броят на кодовите елементи - m се нарича негова основа. За двоичен код xi = и m = 2. Крайната последователност от символи на тази азбука се нарича кодова комбинация (кодова дума). Броят на елементите в кодова комбинация - n се нарича стойност (дължина на комбинацията). Броят на различните комбинации от кодове (N = mn) се нарича количеството или мощността на кода.

1) Подобряване на ефективността на предаването на данни, чрез постигане на максимална скорост на предаване на данни.

2) Повишаване на имунитета по време на предаване на данни.

В съответствие с тези цели теорията на кодирането се развива в две основни насоки:

1. Теорията за икономично (ефективно, оптимално) кодиране търси кодове, които позволяват да се повиши ефективността на предаването на информация в канали без смущения, като се елиминира излишъкът на източника и най-доброто съответствие на скоростта на предаване на данни с капацитета на комуникационния канал.

2. Теорията на коригиращото грешки кодиране търси кодове, които повишават надеждността на предаването на информация в шумни канали.

Научните основи на кодирането са описани от К. Шанън, който изследва процесите на трансфер на информация по технически комуникационни канали (теория на комуникацията, теория на кодирането). При този подход кодирането се разбира в по-тесен смисъл: като преход от представяне на информация в една символна система към представяне в друга символна система. Например преобразуване на писмен руски текст в морзова азбука за предаване чрез телеграф или радио комуникация. Такова кодиране е свързано с необходимостта от адаптиране на кода към използваните технически средства за работа с информация.

Декодирането е процес на преобразуване на кода обратно във формата на оригиналната символна система, т.е. получаване на оригиналното съобщение. Например: превод от морзова азбука в писмен текст на руски език.

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

Има и други начини за кодиране на речта. Например стенографията е бърз начин за запис на говорим език. Собственост е само на няколко специално обучени хора - стенографи. Стенографът успява да запише текста синхронно с речта на говорещия човек. В преписа една икона обозначава цяла дума или фраза. Само стенограф може да дешифрира (декодира) стенограмата.

Горните примери илюстрират следното важно правило: могат да се използват различни методи за кодиране на една и съща информация; техният избор зависи от редица обстоятелства: целта на кодирането, условията, наличните средства. Ако трябва да запишете текста със скоростта на речта, използваме стенография; ако трябва да прехвърлите текст в чужбина, използваме английската азбука; ако трябва да представите текста във форма, разбираема за грамотен руснак, ние го записваме според правилата на граматиката на руския език.

Друго важно обстоятелство: изборът на метод за кодиране на информация може да бъде свързан с предвидения метод за нейната обработка. Нека покажем това, като използваме примера за представяне на числа - количествена информация. Използвайки руската азбука, можете да запишете числото "тридесет и пет". Използвайки азбуката на арабската десетична числова система, пишем: „35“. Вторият метод е не само по-кратък от първия, но и по-удобен за извършване на изчисления. Кой запис е по-удобен за извършване на изчисления: „тридесет и пет пъти сто двадесет и седем“ или „35 х 127“? Очевидно - втората.

Ако обаче е важно да запазите номера без изкривяване, по-добре е да го запишете в текстова форма. Например в паричните документи сумата често се записва в текстов вид: „триста седемдесет и пет рубли“. вместо "375 рубли." Във втория случай изкривяването на една цифра ще промени цялата стойност. Когато използвате текстова форма, дори граматическите грешки може да не променят значението. Например, един неграмотен човек пише: „Триста седемдесет и пет рубли“. Смисълът обаче остана.

Нека има съобщение, написано с помощта на някаква "азбука", съдържаща n "букви". Изисква се „кодиране“ на това съобщение, т.е. посочете правило, което присвоява на всяко такова съобщение определена последователност от m различни "чипове", които съставят "азбуката" на предаването. Ще обмислим кодирането, колкото по-изгодно е, толкова по-малко елементарни сигнали трябва да бъдат изразходвани за предаване на съобщение. Ако приемем, че всеки от елементарните сигнали трае едно и също време, тогава най-изгодният код ще ви позволи да отделите най-малко време за предаване на съобщение.

Основното свойство на случайните събития е липсата на пълна увереност в тяхното възникване, което създава известна несигурност при извършване на експерименти, свързани с тези събития. Ясно е обаче, че степента на тази несигурност в различните случаи ще бъде напълно различна. За практиката е важно да можете да оцените числено степента на несигурност на голямо разнообразие от експерименти, за да можете да ги сравните от тази страна. Помислете за два независими експеримента, както и за сложен опит, състоящ се в едновременно изпълнение на експерименти и. Нека опитът има k равностойни резултати, а опитът има l равностойни резултати. Очевидно несигурността на опита е по-голяма от несигурността на опита, тъй като тук несигурността на резултата от експеримента се добавя към несигурността. Естествено е да се приеме, че степента на несигурност на експеримента е равна на сумата от несигурностите, които характеризират експериментите, т.е.

само една функция удовлетворява -:

Помислете за експеримент А, състоящ се от опит и с вероятности. Тогава общата несигурност за експеримент А ще бъде равна на:

Това последно число ще се нарича ентропия на опита и ще се обозначава с .

Ако броят на буквите в "азбуката" е равен на n и броят на използваните елементарни сигнали е равен на m, тогава за всеки метод на кодиране средният брой елементарни сигнали на една буква от азбуката не може да бъде по-малък от; обаче винаги може да се направи произволно близо до това съотношение, ако веднага се сравняват само отделни кодови обозначения с достатъчно дълги "блокове", състоящи се от голям брой букви.

Тук ще разгледаме само най-простия случай на съобщения, написани с помощта на някои n "букви", честотата на появата на което и да е място на съобщението се характеризира напълно с вероятностите p1, p2, ... ..., pn, където, разбира се, p1 + p2 + ... + pn = 1, при което се приема вероятността pi на i-тата буква, която се появява на всяко място на съобщението, да е еднаква, независимо кои букви са били на всички предишни места, т.е. последователните букви на съобщението са независими една от друга. Всъщност в реалните съобщения това често не е така; по-специално, в руския език вероятността за поява на определена буква зависи значително от предишната буква. Строгото разглеждане на взаимната зависимост на писмата обаче би затруднило всички допълнителни съображения, но по никакъв начин няма да промени бъдещите резултати.

Засега ще разглеждаме двоични кодове; обобщаването на резултатите, получени в този случай за кодове, използващи произволен брой m елементарни сигнали, както винаги е изключително просто. Нека започнем с най-простия случай на кодове, които свързват отделно кодово обозначение - поредица от числа 0 и 1 - с всяка „буква“ на съобщението. Всеки двоичен код за n-буквена азбука може да бъде свързан с някакъв метод за отгатване на определено скрито число x, което не надвишава n, като се използват въпроси, на които се отговаря само с "да" (1) или "не" (0), което води ни към двоичен код. За дадени вероятности p1, p2, ... ..., pn на отделни букви, предаването на многобуквено съобщение ще бъде най-икономичният код, за който при тези вероятности n стойности x средната стойност на броят на зададените въпроси (двоични знаци: 0 и 1 или елементарни сигнали) се оказва най-малък.

На първо място, средният брой бинарни елементарни сигнали в кодирано съобщение на една буква от оригиналното съобщение не може да бъде по-малък от H, където H = - p1 log p1 - p2 log p2 - ... - pn log pn е ентропията на експеримента, който се състои в разпознаване на една буква от текста (или, накратко, само ентропия на една буква). От това веднага следва, че за всеки метод на кодиране, за да се напише дълго съобщение от M букви, се изисква не по-малко от MH двоични знаци и по никакъв начин не може да надвишава един бит.

Ако вероятностите p1, p2, ... ..., pn не са равни една на друга, тогава H 0 го прави