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

Реферат

Кодирование

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

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

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

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

Тема реферату: " КОДИРОВАНИЕ " 1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕ ОРИИ КОДИРОВАНИЯ Оптимальным статистическим (экономным) кодированием назыв а ется кодирование, при котором обеспечи вается распределение времени на передачу отдельных символов алфавита в зависимости от априорных вероятн о стей их появления: ; (1) где C п - пропускная способность канала; p i - априорная вероятность i – й кодовой комбинации; t i -длительность i-й кодо вой комбин а ции. Оптимальными неравномерными кодами (ОНК) - называются коды, в к оторых символы алфавита кодируются кодовыми словами мин и ма-льной средней длины. Принципы построения о птимальных кодов: 1. Каждая кодовая комбинация должна содержать максимальное количество и нформации, что обеспечивает максимальную скорость передачи да н ных. 2. Символам первичного алфавита, имеющим наибольшую вероя т ность появлени я в сообщении, присваиваются более короткие кодовые слова, при этом, сред няя длина кодовых комбинаций имеет минимал ь но-возможную дл ину. При таком кодировании избыточность кода, которая вызвана нера в ной вероятност ью символов алфавита, сводится к минимуму (практ и чески к нулю). Оптимальные код ы являются неравномерными бло ч ными кодами, при их построении необходимо обесп ечить однозна ч ность декодирования. Префиксным (неприводимым)- наз ывается код, в котором ни одна кодовая комбинация не является началом др угой. Для обеспечения этого свойства кодовые комбинации должны запис ы ваться от корня кодового дерева. Возможность однозначного декодирования неравномерного кода обеспечи вается выполнением требования разделимости (префиксн о сти) кодовых ком б и наций. При неравномерном кодировании производится сжатие данных. Сжатие данн ых используется как при хранении данных в памяти, так и при их п е редаче. Оптимал ьное кодирование можно использовать только в каналах без помех или в слу чае низкой требовательности к достоверности перед а ваемой информа ции. Существует много методов оптимального, статистического кодирования. Н аиболее часто используют оптимальное кодирование по мет о ду Шеннона - Фано и Хаффмена. 2. КОД ШЕННОНА-Ф АНО Кодирование по методу Шеннона - Фано осуществляется сл едующим образом: 1. Множество символов, и з которых формируются сообщения, записываются в порядке уб ы вания их априорных вероятностей. 2. Дальнейшее построение кода производится методом последовательн о го деления пополам. Символы сообщен ия разбиваются на две группы с примерно равными вероятностями (т. к. при от сутствии ст а тистической связи между символами скорость передачи максимальна при условии ра в ной вероятности передачи символов). Есл и равной вероятности в подгруппах достичь нельзя, то желательно чтобы су мма р ная вероятность нижней под группы была больше верхней. 3. Всем символам верхней группы приписывается кодовый символ 1, а символам нижней - 0. Можно наоборот, т. к. для кодовой реализации безразлично 0 или 1, но с точки зрения мощности, лучше, если в кодовой ко м бинации меньше единиц. 4. Затем каждая подгруппа аналогичным образом разбивается на подгруппы п о возможности с одинаковыми вероятностями. Разбиение осуществляется д о тех пор, пока в каждой подгруппе останется по одному си м волу. Пример построения кода приведен в таблице 1. Таблица 1 a i p i Разбиение Кодовая комбин а ция Длина a 1 a 2 a 3 a 4 1/2 1/4 1/8 1/8 1 0 1 0 1 0 1 01 001 000 2 3 3 Построенный код является префиксным. Например: полученная кодовая последовательность 11100001 однозна ч но декодируется как: 1 1 1 000 1 01 => a 1 a 1 a 1 a 4 a 1 a 2 . a 1 a 1 a 1 a 4 a 1 a 2 Применяя статистическое кодирование мож но получить результат, близкий к идеальному кодированию по Шеннону. Средняя длина кодовой комбинации, при использовании д воичного кода в качестве вторичного, равна , (2) где l i - длина i-й комбинации; N -основание первичного кода. Эффективность ОНК мак симальна при ; . (3) Коэффициент относительной эффективности (коэффицие нт использов а ния пропускной сп особности) равен . (4) Коэффициент статистического сжатия (уменьшение коли чества двоичных разрядов на символ сообщения при использовании статис тического кодирования по сравнению с обычным кодированием) р а вен . (5) Для рассмотренного примера при длительности символа кодовой комб и нации (0 или 1) равной средняя длина и средняя длительность кодовой комбинации, соответственно равны: Энтропия источника равна При этом: К оэ = 1,75/1,75 = 1; К cc = 2/1,75 = 1,14. Скорость передачи информации , (6) т. е. коэффициент использования пропускной способност и канала р а вен 1, а значит, имеет м есто идеальное использование канала (оптимальное ст а тистическое кодирование). Если подгруппы имеют не одинаковую суммарную вероятность, то к о эффициент меньше 1. Для равномерного код а , при этом . Недостаток кода ОНК - низкая помехоустойчивость, т. к. по теря о д ного разряда может означ ать потерю символа. 3. КО Д ХАФФМЕНА Кодирование по методу Хаффмена осуществляется следу ющим об-разом: 1. Все подлежащие кодированию символы записываются в по рядке убыв а ния их априорных вер оятностей. Если некоторые символы имеют одинак о вые вероятности, то их располагают рядом в произвольно м порядке. 2. Выбирают символы с минимальными вероятностями по 2 и о дному пр и писывают 0, а другому 1. 3. Выбранные символы объединяют в промежуточные символы с сумма р ной вероятностью. 4. Снова находят пару символов с наименьшими вероятностями и пост у пают аналогично. В таблице 2 приведен пример кодирования по методу Хаффмена для источника сообщений с заданными вероятностями символов алфав и та: x 1 = 0,4; x 2 = x 5 = 0,2; x 3 = 0,1; x 4 = x 6 = 0,05. Таблица 2 Символ p i Граф кода Хаффмена Код x 1 x 2 x 5 x 3 x 4 x 6 0,4 0,2 0,2 0,1 0,05 0,05 1 (1,0) 1 0 (0,6) 1 0 (0,4) 1 0 (0,2) 1 0 (0,1) 0 1 01 001 0001 00001 00000 Энтропия источника равна Средняя длина кодовой комбинации данн ого кода Длина кодовой комбинации примитивного кода определяется соотнош е ние м (7) Округляя до ближайшего целого в большую ст орону, п о л учим l = 3. Эффективность ОНК максимальна, если . Коэффициент относительной эффективности равен . Коэффициент статистического сжатия р а вен . Неравномерный код можно передавать блоками заданной длины, а на приемно й стороне декодировать всю последов а тельность. Пример 1. Построить оптимальные неравномерные коды (ОНК) по методу Шеннона-Фано и по методу Хаффмена для передачи сообщений, в к о торых вероятности символов первичного алфавита равны : p(a 1 ) =0,1; p(a 2 ) =0,07; p(a 3 ) =0,02; p(a 4 ) =0,17; p(a 5 ) =0,42; p(a 6 ) =0,09; p(a 7 ) =0,08; p(a 8 ) =0,05. Оценить эффективность каждого кода, т. е. насколько они близки к о п тимальным. Определит ь емкость (пропускную способность) канала связи для каждого кода, если ск орость передачи двоичных символов (V = 1/ ) равна 1000 симв/с, т.е. время передачи одного символа вторичного алфав и та (двоичного символа) равна = 0,001с = 1мкс. Решение: Построим код по методу Шеннона-Фано, используя сле-дующий алгор итм: 1. Симво лы сообщения располагаем в порядке убывания их априо р ных вероятностей. 2. Исходный ансамбль кодируемых символов разбиваем на две группы с приме рно равными вероятностями (лучше, если суммарная вероятность верхней гр уппы меньше). 3. Верхней группе присваиваем символ 1, а нижней 0. 4. Процесс деления повторяем до тех пор, пока в каждой подгруппе о с танется по одному символу. Процесс построения кода приведем в таблице 3. Таблица 3 a i p(a i ) Разбиение Код l i p i l i a 5 a 4 a 1 a 6 a 7 a 2 a 8 a 3 0,42 0,17 0,10 0,09 0,08 0,07 0,05 0,02 0 1 0 0 1 1 0 0 1 1 0 0 1 0 100 101 110 0 11 0 1 1110 111 1 0 11111 1 3 3 4 4 4 5 5 0,4 2 0, 51 0,3 0, 36 0,32 0,28 0,2 5 0, 1 . . Могут быть и другие варианты построения кода, но l ср при эт ом не меняется. Определим энтропию источника сообщений: = -(0,42 log 2 0,42+0,17 log 2 0,17+0,1 log 2 0,1+0,09 log 2 0,09+0,08 log 2 0,08+ +0,07 log 2 0,07+0,05 log 2 0,05+0,02 log 2 0,02) = 0,5256+0,4346+0,3322+ +0,3126+0,2915+0,2686+0,2161+0,1129 = 2,49 бит/симв. Оценим эффективность построенного кода, которая опре деляется коэффициентами относительной эффективности и статистическо го сж а тия. Коэффициент относительной эффективн ости равен Коэффициент статисти ческого сжатия равен . Необходимая пропускная способность канала связи для передачи соо б щений оптимальны ми кодами вычисляется по формуле . Для полученного кода она равна С = 10 3 2,54 = 2,54 Кбит/с. Построим код по методу Хаффмена, используя следующий алгоритм: 1. Символы первичного алфавита распола гаем в порядке убывания их в е роя тностей. 2. Последние два символа объединя ем в один, с суммарной вероятно стью. 3. Упорядочиваем символы с учетом вновь образованных и после д ние два сим вола объединяем в один с суммарной вероятностью. Эту пр о цедуру повторяем до тех пор, пока не оста нется два символа. 4. Строим кодовое дерево, вершиной которого является 1 (су ммарная в е роятность всех симво лов сообщения). При построении дерева символы, в принц ипе, можно не упорядоч и вать. Процесс построения кода приведен в та блице 4. Коэффициент статистического сжатия равен . Коэффициент относительной эффективности . Необходимая пропускная способность канала связи Кбит/c. Tаблица 4 а i p(a i ) Кодовое дерево Код l i p i l i a 5 a 4 a 1 a 6 a 7 a 2 a 8 a 3 0,42 0,17 0,10 0,09 0,08 0,07 0,05 0,02 1 (1,0) 1 1 0 (0,34) (0,58) 0 1 0 (0,24) 1 0 (0,17) 0 1 (0,14) 1 0 (0,7) 0 1 011 001 0101 0100 0001 00001 00000 1 3 3 4 4 4 5 5 0,42 0,51 0,3 0,36 0,32 0,28 0,25 0,1 . . Построенные коды Шеннона – Фано и Хаффмена равноценны, т. к. они имеют оди наковые показатели эффективности. Оба кода отлич а ются от оптимального на 2%. 4. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ Помехоустойчивость- способность системы осуществля ть прием и н формации в условиях н аличия помех в линии связи и искажений во внутри аппаратных трактах. Пом ехоустойчивость обеспечивает надежность и до с товерность передаваемой информации (данных). Мы будем в основн ом рассматривать двоичные коды. Двоичные (коды) данные передаются между вычислительными терми налами, летательными аппаратами, спу т никами и т. д. Передача данных в вычислительных системах чувствительна к малой доле ошибке, т. к. одиночная ошибка может сущест венно нарушить пр о цесс вычислений. Наиболее часто ошибки появляются в УВВ, шинах, устройствах памяти. УВВ содержат б ольшое количество элементов, ошибки обусла в ливаются старением элементов, ухудшением качества электри ческих соединений, расфазировкой сигналов. Значительная часть ошибок приходится на ОП, вследствие отказа отдел ьных ИС либо всей ИС, ошибок связанных с флу к туацией напряжения питания и т. д. В системах со многими пользователями и р азделением по времени длинные двоичные сообщения разделяются на пакет ы. Сообщения, представленные длинными пос ледовательностями б и тов, обычн о разбиваются на более короткие последо вательности битов, называемые пакетами. Пакеты можно передать по сети ка к независимые объе к ты и собират ь из них сообщение на конечном пункте. Пакет, снабженный именем и управляющими б итами в начале и в конце, называется кадром. Управление линией передачи данных ос у ществляется по специальному алгоритм у, называемому протоколом. Наличие помех ставит дополнительные требования к методам кодиров а ния. Для защиты информации от помех н еобходимо вводить в том или ином виде избыточность: повышение мощности с игнала; повторение с о общений; увеличение длинны кодовой комбинации и т. д. Увеличение мощности сигналов приводит к усложнению и удорож а нию аппаратуры, кроме того, в некоторых с истемах передачи информации им е ется ограничение на передаваемую мощность, например, спутнико вая связь. Повторная передача сообщений требует наличия буферов для хранения инф ормации и наличия обратной связи для подтверждения достоверности пере данной информации. При этом, значительно падает скорость передачи инфор мации, кроме того этот метод не всегда м. б. и с пользован, например, в система реального времени. Одним из наиболее эффективных методов повышения достоверности и надеж ности передачи данных является помехоустойчивое кодиров а ние, позволяющее за счет внесения допол нительной избыточности (увеличение минимального кодового расстояния) в кодовых комбинациях передава е мых сообщений обеспечить возм ожность обнаружения и исправления одиночных, кратных и групповых ошибо к. Минимальное кодовое расстояние характеризует помехоустойч и вость и избыточность сообщений. В завис имости от величины минимального к о дового расстояния существуют коды, обнаруживающие и исправляющие ошибки. Кодовое расстояние - d определяется как к оличество единиц в результ а те с уммирования по модулю два двух кодовых комбинаций. Минимальное кодовое расстояние d 0 - минимальное из кодов ых расстояний всех возмо ж ных ко довых комбинаций. Для обнаружения r ошибок минимальное кодовое расстояние равно: d 0 r+1. (8) Для обнаружения r ошибок и исправления s ошибок минимальное код о вое расстояние равно: d 0 r+s+1. (9) Только для исправления ошибок минимальное кодовое расстояние равно: d 0 2s+1. (10) 5. ОБНАРУЖИВА ЮЩИЕ КОДЫ Обнаруживающие коды - это коды, позволяющ ие обнаружить оши б ку, но не испр авить ее. Простейший способ обнаружения ошибки это добавл е ние к последовательности битов данных еще одного бита-бита проверки на четност ь (нечетность) значение, которого равно с умме по модулю два исходной последовательности битов. Ча ще организуется проверка на нечетность. В символьном коде ASCII к семи битам кода добавляется восьмой бит проверки н а четность - k 1 . S 1 S 2 S 3 S 4 S 5 S 6 S 7 K 1 1 1 0 1 1 0 1 1 Однобитовая проверка позволяет обнаружить любую единичную о шибку, две ошибки обнаружить нельзя, в общем случае обнаруживается л ю бое нечетное количество ошибок. Внесение избыточности за счет увеличения длины кодовой комбин а ции приводит к снижению скорости перед ачи информации. Если скорость идеально и с польз ует канал, то . (11) Если кодовая комбинация длиной n содержит k информ ационных и m ко нтрольных разрядов (n = k + m), то . Для кода ASCII n = 8 и k = 7 , т. е. введения одного избыточного разряда приводит к уменьшению пр о пускной способности к анала связи на 12,5%. Чаще всего шумы (молнии, разрыв и т.д.) порождают длинные пакеты ошибок и вероятность четного и нечетного числа ошибок один а кова, а значит и однобитовая проверка не эффективна. Проверка на четность по вертикали и горизонтали. При этом последовательность битов данных пер естраивается в двухмерный массив, и в ы числяются биты на четность, как для каждой строки, так и для кажд ого столбца. При этом можно обнаружить несколько ошибок, если они не распол а гаются в одинаковых строках и столбцах. Чаще всего используется при передаче данных кода ASCII; ка ж дый символ можно считать строк ой массива. Такая проверка может не тол ь ко устано вить факт ошибки, но и обнаружить ее место, а значит, есть принципиальная возможность ее исправления, хотя это пра к тически не используется. 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 После обнаружения оши бок иногда можно повторить передачу соо б щений, иногда после обнаружения ошибки предп ринимается вторая и даже третья попытка передачи сообщения. Проверка на четность широко используется на ЭВМ, как на апп а ратном, так и на программном уровне. Например, при считывании с магнитной ленты в случае, когда условие на четно сть не выполняется, то производится повторное считыв а ние, т. е. если произошла малая потеря намагниченности, то после второй попытки может быть считывание произ ойдет правильно. Пример 1. Символы алфавита источника кодируются семиразрядным двоичным кодом с весом кодовых векторов (количеством единиц в код о вой комбинации) w = 3. Определить необходим ую мощность кода и его и з быточно сть. Решение: Мощнос ть семиразрядного кода равна N = 2 7 = 128. Так как для кодирования используются только кодовые вектора с весом три , то количество таких векторов в сем и разрядном коде равно Избыточность кода равна R = 1 – log 2 K/ log 2 N = 0,265. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПб ГИТМО (ТУ), 2001; 2. Мастрюков Д. Алгоритмы сжатия ин формации. Ч. 1. Сжатие по Хаффм е ну //Монитор, 1993. – № 7 – 8 – С. 14 – 20; 3. Мастрюков Д. Алгоритмы сжатия ин формации. Ч. 2. Арифметическое к о дирование //Монитор, 1994 – № 1 – С. 20 – 23; 4. Ф.Дж.Мак-Вил ьямс, Н.Дж.А.Слоэн, Теория кодов, исправляющих ошибки, Москва, “Связь”, 1979. 5. .Лидл, Г.Нидеррайтер, Конечные по ля, Т. 1,2, Москва, “Мир”, 1988. 6. Т.Касами, Н.Токура, Е.Ивадари, Я.Ина гаки, Теория кодирования, М о сква, “Мир”, 1978. 7. У.Петерсон, Э.Уэлдон, Коды, исправ ляющие ошибки, Москва, “Мир”, 1976. 8. Э.Берлекэмп, Алгебраическая тео рия кодирования, Москва, “Мир”, 1971. 9. Дискретная математика и матема тические вопросы кибернетики. Т.1. /Ю.Л. Васильев, Ф. Я. Ветухновский, В. В. Глаг олев, Ю. И. Журавлев, В. И. Левенштейн, С. В. Яблонский. Под общей редакцией С. В. Я блонск о го и О. Б. Лупанова. – М.: Главная редакция физико – математической л и тературы изд– ва «Наука», 1974 10. Лидовский В. В. Теория информаци и: Учебное пособие. — М.: Компания Спутник+, 2004
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