Лекция: Кодирование инф. Эфф-ть, помехоуст-ть кодирования, сущ-ие декод-я. Методы Фано, Хаффмена.

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

Кодирование – это некоторое преобразование F множества сообщений в алфавите А во множество сообщений алфавита В. А={α1….αk} В={β1….βm}

а–сообщение кот-е мы хотим закодировать

А*–множество всех сообщений к-е можно записать в алфавит а

F(a)=b, b принадлежит В* – закодированое

В*–множество всех сообщений в алфавите b

Если алфавит В имеет мощность |В|=m то кодирование наз-ся m-ичным. В={0,1}–двоичное.

Преобразование обратное кодированию F наз-ся декодирование.

Св-ва кодирования:

1.Существование декодирования.Алфавитное(побуквенное) кодирование задается схемой или таблицей кодов <αi → βi>, где

Кодовое слово βi наз-ся элементарным кодом. Кодирование наз-ся равномерным если все элементарные коды имеют одинаковую длину li= |βi|=l

В неравномерном кодировании разные коды могут иметь разные длины.

Схема кодирования наз-ся разделимой если любое слово составленное из элементарных кодов единственным образом разделяется на элементарные коды.

Теорема1: Алфавитное кодирование с разделимой схемой имеет однозначное декодирование.

Схема кодирования наз-ся префиксной если никакой элементарный код не является началом другого элементарного кода.

Теорема2: Если схема кодирования префиксная, то она является разделимой.

Схема кодирования разделима тогда и только тогда когда выполняется неравенство Крафта

2.Эффективность(оптимальность) код-ия.

Для практики важно чтобы коды сообщений имели по возможности наименьшую длину чтобы кодирование было оптимальным. Чтобы сделать код оптимальным(эфективным), необходимо иметь информацию об алфавите А и множестве А*.Н-р: вероятность появления каждой буквы алфавита А в сообщении.

Минимизация длины кода в сообщении. Длина кода всего сообщения зависит от состава букв в сообщении и от длины элементарных кодов этих букв. Если дано конкретное сообщение и схема кодирования, то можно подобрать такую перестановку элементарных кодов при которой длина кода в сообщении будет минимальной. Для этого нужно отсортировать буквы αi в порядке убывания их вероятности появления в сообщении. А элементы кода βi отсортировать по возрастанию длин и назначить коды βi для букв αi в таком порядке: <αi → βi>, i=1..n, li= |βi|.

Пусть известны вероятности появления букв αi, тогда длина или стоимость кодирования – сумма c=l1*p1+…+ln*pn Средняя длина кодир-ия слова – стоимость кодирования.

3.Надежность (помехоустойчивое) кодирования.

S – мн-во переданных сообщений; S/ — мн-во полученных сообщений; C – канал связи, он ищет источник помех. Передача сообщения: S→К→К/→ S/.(над первой стрелкой F, над 2-C, над 3 – F-1)/ Кодирование наз-ся помехоустойчивым(самокорректирующимся, кодир-ие с исправлением ошибок), если для любого сообщения из мн-ва S: (АS э S) (E-1(C(F(S)))=S) (гдеА-перевернутая, значит любое, Е- знак существует)

Помехоустойчивость связана с понятием ошибки. Ошибки: 1).Замещение разряда; 2).Выпадение разряда; 3).Вставка разряда.

Код Фано: 1.Постановка задачи: Дан алфавит из n букв с помощью кот-х записано сообщение, известна частота появлении, т.е. вероятность каждой буквы алфавита в сообщении р1, р2….рn :

При этом:1); 2)Вероятность появления буквы аi на любом месте сообщения одна и та же в не зависимости от того какие буквы стоят перед. 3)Вероятности упорядочены.(по убыванию).2.Идея кода Фано (показать на примере)Буквы алфавита требуется разбить на 2 группы, чтобы суммы обоих групп были по возможности ближе друг к другу. Для букв 1-й группы в качестве кодового символа используем 0, а во 2-й – 1.Процесс продолжаем до тех пор пока каждая группа не будет состоять из одной буквы.(Схема префиксная, разделимая, существует однозначное декодирование).

Код Хаффмана: (оптимальное кодирование):1. Постановка задачи Основан на жадном выборе, он строит оптимальные коды символов исходя из частоты их использования в тексте, этот метод используется в архиваторах. 2.Идея этого кода (показать на примере) часто встречающиеся символы кодируются короткими последовательностями битов, а редко встречающиеся длинными. Хаффман разработал алгоритм к-й строит оптимальный префиксный код. Жадный алгоритм – это алг-м к-й на каждом шаге делает локально-оптимальный выбор в надежде что полученое таким образом итоговое решение тоже окажется оптимальным.

Надежность (помехоустойчивость кодирования). Кодирование по методу Хемминга.

Надежность (помехоустойчивое) кодирования.

При передачи инф-ии помехи обычное дело (треск в трубке телефона, разговор при ветре на расстоянии). Часто эти помехи м преодолеть в силу избыточности естественного языка. Избыточность могла бы использоваться и при передаче закодированных сообщ. В техических системах каждый фрагмент текста передается трижды и прав-м считается тот у которого больше совпаденй. Это влечет за собой большие затраты времени и емкостные затраты при передаче и хранении инф-ии.

S – мн-во переданных сообщений; S/ — мн-во полученных сообщений; C – канал связи, он ищет источник помех. Передача сообщения: S→К→К/→ S/.(над первой стрелкой F, над 2-C, над 3 – F-1)/ Кодирование наз-ся помехоустойчивым(самокорректирующимся, кодир-ие с исправлением ошибок), если для любого сообщения из мн-ва S: (АS э S) (E-1(C(F(S)))=S) (гдеА-перевернутая, значит любое, Е- знак существует)

Помехоустойчивость связана с понятием ошибки. Ошибки: 1).Замещение разряда; 2).Выпадение разряда; 3).Вставка разряда.

Код Хемминга(Показывать на примере)

1)Ищем кол-во информационных разрядов по мощности алфавита.(M=30)

2m>=М, m=?(=5)

2)Ищем кол-во контролирующих разрядов по кол-ву информационных. 2к>=m+к+1, n=m+к. (к=4)

3) Контролирующие разряды ставятся по степеням двойки.