КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Равномерное кодирование
Задача кодирования
Пусть имеется некоторое множество А = {, ,…, }. Будем называть это множество алфавитом, а объекты – буквами. Кортеж из букв =, ,…, будем называть словом. Последовательность слов – S называется сообщением. Множество сообщений над алфавитом А будем обозначать А . Пусть имеется алфавит В = {, ,…, }. Задача кодирования заключается в том, что сообщение S, заданное над алфавитом А, преобразуется в сообщение S , заданное над алфавитом В (код). Функция f (), переводящая сообщение S в S , называется кодированием. Последовательность символов , ,…, , соответствующая букве алфавита А, называется элементарным кодом этой буквы. Общее количество символов ─ длина кода. Замечание: В качестве буквы алфавита А, могут выступать и сообщения. Функция, обратная функции кодирования F (), называется декодированием. Задача заключается в том, чтобы произвести кодирование, удовлетворяющее некоторым условиям (порой даже взаимоисключающим друг друга). Примеры:
Равномерное кодирование – это кодирование, при котором каждый элементарный код имеет одинаковую длину. Например, если выбрать в качестве алфавита В цифры, то одноразрядным кодом можно закодировать 10 символов, а двухразрядными числами – 100. Пусть алфавит В содержит к букв, а длина элементарного кода n букв. Сколько символов (m) при равномерном кодировании можно закодировать? Элементарные коды ─ это кортежи из n букв, взятых из данных к, поэтому они являются размещениями с повторениями. По известной формуле их число равно
m = кn (1) Поставим обратную задачу. Имеется m букв алфавита А. Сколько букв должны содержать элементарные коды при равномерном кодировании? Из формулы (1), логарифмируя, получи n = log к m (2) Если же алфавит В ={0,1} – двоичный, то закодировать n – битным кодом можно в силу формулы (1) имеем букв m = 2 n (3) Пусть имеется алфавит А, состоящий из m символов. Сколько бит должен содержать каждый элементарный код при равномерном кодировании? Из формулы (2) получим, если m – степень 2, n = log 2m (4) Если m – не степень 2, то по формуле: n=\ logm | + 1 (5) где | logm | - целая часть logm.. Формулы (4) - (5) называются формулами Хартли. Например. Если в качестве алфавита А взять русский алфавит, который содержит 33 символа и пробел, то для 34 символов: по формуле Хартли n =|log 34 | +1=5+1- 6 бит. При этом мы можем 6-битным кодом закодировать еще 30 символов. Такое кодирование называется избыточным. В компьютерах применяется 1-байтовое кодирование (256 символов) и оно также является избыточным. Задача: Дано сообщение S. Производится равномерное кодирование длиной k – бит. Найти общую длину кода. Решение: Если длина сообщения | S |=, то длина кода L = k .
Дата добавления: 2014-01-06; Просмотров: 11275; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |