Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Кодирование в информатике:представление памяти в памяти комп., защита информации от несанкционированного доступа, сжатие информации.
Кодирование – это некоторое преобразование 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) Контролирующие разряды ставятся по степеням двойки.
Дата публикования: 2015-02-03; Прочитано: 257 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!