Реферат: Основы экономного кодирования - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Основы экономного кодирования

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 74 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

БЕЛОРУССКИЙ ГОСУДАРСТВЕ ННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ кафедра РЭС реферат на т ему: «Основы экономного кодирования» МИНСК, 2009 Сообщения, передаваемые с использованием РТС ПИ (речь, музыка, тел е визионные изображения и т.д.) в большинстве своем предназначены для непосредственного в осприятия органами чувств человека и обычно пл о хо пр испособлены для их эффективной передачи по каналам связи. Поэтому они в процессе передачи, как правил о, подвергаются кодиров а н ию. Что такое ко дирование и зачем оно используется? Под кодированием в общем слу чае понимают преобразование алфавита сообщения A л i , ( i = 1,2… K ) в алфав ит некоторым образом выбранных кодовых си м волов x j , ( j = 1,2… N ) . Обычно (но не обязательно) размер алфавита кодовых символов dim x j меньше или намного меньше размера алфавита ист о чника dim A л i . Кодирование сообщений може т преследовать различные цели. Напр и мер, это кодирован ие с целью засекречивания передаваемой информации. При этом элементарн ым сообщениям i из алфавита A л i ставятся в соо т ветствие последовательности, к примеру, цифр или букв из спец иальных кодовых таблиц, и з вестных лишь отправителю и получателю информации. Другим примером кодирования может служить преобразование дискре т ных сообщений i из одних систем счисления в другие (из десятичной в двоичную, вос ьмеричную и т. п., из непозиционной в позиционную, преобразование бу к венного алфавита в цифровой и т. д.). Кодирование в канале, или пом ехоустойчивое кодирование информации, может быть использовано для уме ньшения количества ошибок, возника ю щих при передаче по каналу с помехами. Наконец, кодирование сообщений может производиться с целью сокр а щения о бъема информации и повышени я скорости ее передачи или сокращения полосы частот, требуемых для перед ачи. Такое к одирование наз ы вают экономным, безызбыточным, или эффективн ым кодированием, а также сжатием данных. В данном разделе будет и дти речь именно о так о го р ода кодировании. Процедуре кодирования обычно предшествуют (и включают ся в нее) дискретизация и ква н тование непрерывного со общения л(t) , то есть его прео бразование в последовательность элементарных дискретных сообщений л iq . Прежде чем перейти к вопросу экономного кодирования, кратко поясним суть самой процедуры кодирования. Любое дискретное сообщение i из алфавита источника A л i объемом в K символов можно з акодировать последовательностью соответствующим обр а зом выбранных кодовых символов x j из ал фавита x j . Например, любое число (а i можно считать числом) можно записать в заданной позиционной системе счисления следующим обр а зом: i = M = x n 1 m n-1 + x n-2 m n-2 +… + x 0 m 0 , (1) где m - основание с истемы счисления; x 0 … x n-1 - коэффициенты при степ е нях m ; x 0, m - 1 . Пусть, к примеру, значение i = M = 59 , тогда его код по основанию m = 8 , б у дет иметь вид M = 59 = 7·8 1 + 3·8 0 =73 8 . Код того же числа, но по основанию m = 4 будет выглядеть следующим о б разом: M = 59 = 3 4 2 + 2 4 1 + 3 4 0 = 323 4 . Наконец, если основание кода m = 2 , то M = 59 = 1 2 5 + 1 2 4 + 1 2 3 + 0 2 2 + 1 2 1 + 1 2 0 = 111011 2 . Таким образом, числа 73 , 323 и 111011 можно считать, соответственно, восьм еричным, четв е ричным и дв оичным кодами числа M = 59 . В принципе основание кода может быть любым, однако наибольшее распростр анение получили двоичные коды , или коды с основанием 2, для которых разме р алфавита кодовых символов x j равен двум, x j 0,1. Двои ч ные коды, то есть коды, сод ержащие только нули и единицы, очень просто формируются и передаются по каналам связи и, гла вное, являются внутре н ним языком цифровых ЭВМ , то есть б ез всяких преобразований могут обрабатываться цифровыми сре д ствами. Поэтому, когда речь идет о ко дировании и кодах, чаще всего имеют в виду именно дв оичные коды. В дальнейшем буд ем рассматривать в основном двоичное кодиров а ние. Самым простым спо собом представления или задания кодов являются код о вые таблицы, ставящие в соответств ие сообщениям i соотве тствующие им к о ды (табл. 1). Буква i Чи с ло i Код с основ а нием 10 Код с основан и ем 4 Код с основан и ем 2 А 0 0 00 000 Б 1 1 01 001 В 2 2 02 010 Г 3 3 03 011 Д 4 4 10 100 Е 5 5 11 101 Ж 6 6 12 110 З 7 7 13 111 Табл и ца 1 Другим наглядным и удобным способом описания код ов является их пре д ста вление в виде кодового дерева (рис..1). Корень Узлы 0 1 Вершина 0 1 0 1 0 1 0 1 0 1 0 1 А Б В Г Д Е Ж З 1 2 3 4 5 6 7 8 Рис. 4. Рис. 1 Для того, чтобы построить кодовое дерево для данного кода, начиная с некоторой то чки - корня кодового дерева - п роводятся ветви - 0 или 1. На вершинах кодового дерева наход ятся буквы алфавита источника, причем каждой б у кве соответствуют своя вершина и свой путь от корня к вершине . К примеру, букве А с о ответ ствует код 000, букве В – 010, букве Е – 101 и т.д. Код, полученный с использованием кодового дерева, изображенного на рис. 1, является ра в номерны м трехразрядным кодом . Равномерные коды очень ш и роко используются в силу своей простоты и удобства процедур кодиров а ния-декодирования: каждой бу кве – одинаковое число бит; принял заданное число бит – ищи в кодовой та блице соответс т вующую бу кву. Наряду с равномерными кодами могут применяться и неравномерные коды, ко гда каждая буква из алфавита источника кодируется различным числом си м волов, к примеру, А - 10, Б – 110, В – 1110 и т.д. Кодовое дерево для неравномерного кодирования может выглядеть, н а пример, так, как показано на рис. 2. Рис. 2 При использовании этого кода буква А будет кодироваться, как 1, Б - как 0, В – как 11 и т.д. Однак о можно заметить, что, закодир овав, к прим е ру, текст АББА = 1001 , мы не сможе м его однозначно декодировать, поскольку такой же код дают фразы: ЖА = 1001, АЕА = 1001 и ГД = 1001. Т а кие коды, не обеспечивающие однозначного декодирования, назы ваются приводимыми, или непрефиксными, кодами и не могут на практике прим е няться без специальных разделяющих символов. Приме ром применения т а кого тип а кодов может служить азбука Морзе, в которой кроме точек и тире есть спец иальные символы раздел е н ия букв и слов. Но это уже не двоичный код. Однако можно построить неравномерные неприводим ые коды, допу с кающие одн означное декодирование. Для этого необходимо, чтобы всем б у квам алфавита соответствовали ли шь вершины кодового дерева, например, такого, как показано на рис. 3. Здесь ни одна кодовая комбинация не я в ляется началом другой, более длинн ой, поэтому неоднозначности декодирования не будет. Такие неравн о мерные коды называются пре фиксными . Рис..3 Прием и декодирование неравномерных кодов - проце дура гораздо более сложная, нежели для равномерных. При этом усложняется аппаратура декодирования и синхронизации, поскольку поступление элем ентов с о общения (букв) ст ановится нерегулярным. Так, к примеру, приняв первый 0, декодер должен посм отреть в кодовую таблицу и выяснить, какой букве соответствует прин я тая последовательность. По скольку такой буквы нет, он должен ждать прихода следующего символа. Есл и следующим символом будет 1, тогда декодирование первой буквы завершитс я – это будет Б, если же вт о рым принятым символом снова будет 0, придется ждать третьего символа и т.д. Зачем же используются неравномерные коды, если они столь н еудобны? Рассмотрим пример кодирован ия сообщений i из алфавита объемо м K = 8 с п о мощь ю произвольного n -разрядно го двоичного кода. Пусть источник сообщения выдает некоторый текст с алфавитом от А до З и одинак овой вероятностью букв Р( i ) = 1/8. Кодирующее устройство кодирует эти буквы равномерным трехразрядным к о дом (см. табл. 1). Определим основные информационные характеристи ки источника с т а ким алфавитом: - энтропия источника , ; - избыточност ь источника ; - среднее чис ло символов в коде ; - избыточнос ть кода . Таким образом, при кодировании сообщений с равнов ероятными буквами избыточность выбранного (равномерного) к о да оказалась равной нулю. Пусть теперь вероятности появления в тексте различ ных букв будут ра з ными (та бл. 2). Табл и ца 2 А Б В Г Д Е Ж З Ра =0.6 Рб =0.2 Рв =0.1 Рг =0.04 Рд =0.025 Ре =0.015 Рж =0.01 Рз =0.01 Энтропия источника в этом случае, естественно, будет меньшей и составит = 1.781. Среднее число символов на одно сообщение при испо льзовании того же ра в н омерного трехразрядного кода Избыточность кода в этом случае будет , или довольно значительной величиной (в среднем 4 симв ола из 10 не несут никакой инфо р мации). В связи с тем, что при кодировании не равновероятных сообщений равн о мерные коды обладают большой избыточностью , было предложено испол ь зовать неравномерные коды, длительнос ть кодовых комбинаций которых была бы согласована с вероятностью выпад ения различных букв . Такое кодирование называется статистическим. Неравномерный код при статист и ческом кодировании выбирают так, чтобы более вероятные буквы передавались с помощью более коротких ко м бинаций кода, менее вероятные - с помощью более длинных . В результате уменьшается с редняя длина кодовой группы в сравнении со случаем равномерного код и рования. Один из способов такого кодирования предложен Хаффменом. Постро е ние кодового дерева неравномерно го кода Хаффмена для передачи одн о го из восьми сообщений i с различными вероятностями иллюстрируется табл. 3. Таблица 3 Бу к ва Вероя т ность Р i Кодовое дер е во Код n i n i P i А Б В Г Д Е Ж З 0.6 0.2 0.1 0.04 0.025 0.015 0.01 0.01 1 01 001 0001 00001 000001 0000001 00000001 1 2 3 4 5 6 7 8 0.6 0.4 0.3 0.16 0.125 0.08 0.07 0.08 Среднее число символ ов для такого кода составит а избыточность кода т.е. на порядок меньше, чем при равномерном кодирова нии. Другим простейшим способом статистического кодирования является коди рование по методу Шеннона-Фано. Кодирование в соответствии с этим алгори т мом производится так: - сначала вс е буквы из алфавита сообщения записывают в порядке убывания их вер о ятностей; - затем всю с овокупность букв разбивают на две примерно равные по сумме вероятносте й группы; одной из них (в груп пе может быть любое число символов, в том числе – один) присваивают симво л “1”, др у гой - “ 0”; - каждую из э тих групп снова разбивают (если это возможно) на две ча с ти и каждой из частей присваиваю т “ 1” и “0” и т.д. Процедура кодирования по методу Шеннона-Фано иллюстрируется табл. 4. Таблица 4 Бу к ва Р( i ) I II III IV V K од n i P i А 0.6 1 1 0.6 Б 0.2 0 1 1 011 0.6 В 0.1 0 010 0.3 Г 0.04 0 1 001 0.12 Д 0.025 0 1 0001 0.1 Е 0.015 0 00001 0.075 Ж 0.01 1 000001 0.06 З 0.01 0 000000 0.06 Для полученного таким образом кода среднее число двоичных символов, п риход я щихся на одну букву , равно , а избыточность кода составит то есть также существенно меньшую величину, нежел и для равномерного кода. Обратим вн имание на тот факт, что как для кода Хаффмена, так и для к о да Шеннона-Фано среднее количест во двоичных символов, приходящееся на символ источника, приближается к э нтропии источника, но не равно ей. Данный результат пре д ставляет собой следствие теоремы кодирования без шума для источника (первой т еоремы Ше н нона), которая утверждает: Любой источник можно закодировать двоичной после довательностью при среднем количестве двоичных символов на символ ист очн и ка i , сколь угодно близком к энтропии, и невозможно добиться средн ей длины кода, меньшей, чем энтропия H( л ). Значение этой теоремы для современной радиотехни ки трудно переоц е нить – она устанавливает те границы в компактности представления информации, которых мо ж но достичь при правильном ее кодировании. ЛИТЕРАТУРА 1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с. 2. Метрология и радиоизмерения в теле коммуникационных системах. Учебник для вузов. / В.И. Нефед ов, В.И. Халкин, Е.В . Федоров и др. – М .: высша я школа, 2001 г. – 383с. 3. Цапенко М . П . измерительные ин формационные системы. – М.: Э нерго атом издат, 2005. - 440с. 4. Зюко А.Г. , Кловский Д .Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г . – 368 с. 5. Б. Скля р. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е , испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Только в России особо крупные размеры хищений считаются смягчающим обстоятельством.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Основы экономного кодирования", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru