Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лекция 4 Экономичное кодирование информации
Содержание
- 1. Лекция 4 Экономичное кодирование информации
- 2. План лекции: Основные определения теории кодированияОсновные задачи теории кодированияМетоды экономичного кодированияДекодирование неравномерных кодов
- 3. 1. Основные определения теории кодирования
- 4. Алфавит - набор знаков, в котором установлен порядок их следования
- 5. Первичный алфавит - алфавит, с помощью которого
- 6. Код - правило, описывающее соответствие
- 7. Кодирование - перевод информации, представленной
- 8. Равномерный код –
- 9. Пример 1 :Построить равномерный код для алфавита
- 10. Неравномерный код – код, формирующий кодовые комбинации разной длины Код Морзе
- 11. Виды кодирования: Алфавитное кодирование – коды
- 12. При двоичном кодировании для формирования сообщения используются
- 13. Обратимость кодирования Операции кодирования и декодирования
- 14. 2. Основные задачи теории кодирования
- 15. Основные задачи, решаемые теорией кодирования: Обеспечение экономичности
- 16. Защита от помехТехнические методы:экранирование электрических линий связейулучшение
- 17. 3. Методы экономичного кодирования
- 18. Избыточность — использование для кодирования
- 19. Оптимальный код — код, избыточность
- 20. Первая теорема Шеннона (основная теорема о кодирования
- 21. Значение первой теоремы ШеннонаШеннон доказал теоретическую возможность
- 22. Слайд 22
- 23. Идея экономичного кода При экономичном кодировании
- 24. Экономичный код должен учитывать частоту
- 25. Метод экономичного кодирования Хаффмана Строится кодовое дерево1.
- 26. Код ХаффманаПример 2 Построить код
- 27. 4. Декодирование неравномерных кодов
- 28. Пример 3. Построим неравномерный код, учитывающий частоту
- 29. Можно ли однозначно декодировать код,
- 30. Закодированные неравномерным кодом сообщения могут декодироваться только
- 31. Закодируем и декодируем текст bcd кодом Хаффмана из примера 2
- 32. Вопрос При использовании префиксного кодирования, если имеется код 1010, какой код нельзя использовать?00011011
- 33. Вывод: алгоритмы экономичного кодирования должны:1. учитывать частоту
- 34. Недостаток неравномерного кодированияЕсли в процессе передачи сообщения
- 35. Семинар
- 36. Упражнение 1 В алфавите 5 символов:
- 37. Упражнение 2 Закодировать кодом Хаффмана текст «миру-мир»
- 38. Найти избыточность кодов, построенных в упражнениях 1-2Упражнение 3
- 39. Исходный алфавит содержит восемь
- 40. Пусть имеется следующая таблица префиксных кодов:Требуется декодировать
- 41. Задачи ЕГЭ
- 42. Задание 1Для кодирования букв А, Б, В,
- 43. Задание 2Для кодирования некоторой последовательности, состоящей из
- 44. Задание 3По каналу связи передаются сообщения, содержащие
- 45. Задание 4По каналу связи передаются сообщения, содержащие
- 46. Задание 5 В сообщении встречается 40
- 47. Задание 6По каналу связи передаются сообщения, содержащие
- 48. Слайд 48
- 49. Слайд 49
- 50. Скачать презентанцию
План лекции: Основные определения теории кодированияОсновные задачи теории кодированияМетоды экономичного кодированияДекодирование неравномерных кодов
Слайды и текст этой презентации
Слайд 2План лекции:
Основные определения теории кодирования
Основные задачи теории кодирования
Методы экономичного
кодирования
Слайд 5
Первичный алфавит - алфавит, с помощью которого представляется информация до
преобразования
Вторичный алфавит - алфавит, с помощью которого представляется информация после
преобразования
Слайд 6
Код - правило, описывающее соответствие знаков или их
сочетаний одного алфавита знакам или их сочетаниям другого алфавита.
Слайд 7 Кодирование - перевод информации, представленной посредством первичного алфавита,
в последовательность кодов
Декодирование - восстановление информации в первичном алфавите по
полученной последовательности кодов. 
Слайд 8
Равномерный код – код, формирующий для
всех символов первичного алфавита кодовые комбинации одинаковой длины
Слайд 11Виды кодирования:
Алфавитное кодирование – коды строятся для каждого
знака первичного алфавита.
Блочное кодирование – коды строятся для комбинаций знаков
первичного алфавита
Слайд 12При двоичном кодировании для формирования сообщения используются только два типа
сигналов (обозначаются 0 и 1)
Двоичное кодирование
Слайд 13Обратимость кодирования
Операции кодирования и декодирования называются обратимыми, если
их последовательное применение обеспечивает возврат к исходной информации без каких-либо
ее потерь
Слайд 15Основные задачи, решаемые теорией кодирования:
Обеспечение экономичности передачи информации посредством устранения
избыточности
Обеспечение надежности (помехоустойчивости) передачи информации
Слайд 16Защита от помех
Технические методы:
экранирование электрических линий связей
улучшение избирательности приемного устройства
и
т.д.
Методы предлагаемые теорией информации:
учет соответствия характеристик источника сообщений и
характеристик канала связииспользование специальных методов кодирования информации
Слайд 18
Избыточность — использование для кодирования сообщения большего количества
символов, чем это минимально необходимо для его однозначного декодирования
Слайд 19 Оптимальный код — код, избыточность которого минимальна для
источника с данными характеристиками
Двоичный код будет иметь нулевую
избыточность, если средняя длина кодовой комбинации будет равна энтропии источника
Слайд 20Первая теорема Шеннона (основная теорема о кодирования для линии связи без
помех)
При отсутствии помех передачи всегда возможен такой вариант кодирования
сообщения, при котором избыточность кода будет сколь угодно близкой к нулю (средняя длина двоичного кода будет сколь угодно близкой к энтропии источника).Первая теорема Шеннона утверждает принципиальную возможность создания оптимального кода, но не указывает метод создания такого кода
Слайд 21Значение первой теоремы Шеннона
Шеннон доказал теоретическую возможность существования кода с
избыточностью сколь угодно близкой к нулю.
Экономичность кода (снижение избыточности) достигается
за счет учета характеристик источника (частоты появления отдельных символов в сообщении)
Слайд 23Идея экономичного кода
При экономичном кодировании для кодирования символов
исходного алфавита используют неравномерные коды, учитывающие частоту появления символов:
«» -
0О – 01
….
Ф - 111111
Слайд 24 Экономичный код должен учитывать частоту появления символов первичного
алфавита в сообщении
чем больше частота символа, тем короче его код
Слайд 25Метод экономичного кодирования Хаффмана
Строится кодовое дерево
1. Вероятности символов выписывают
слева направо в порядке убывания (висячие вершины)
2. Просматривая вершины справа
налево, выбирают 2 с минимальными весами и объединяют (вес новой вершины = сумме весов объединенных)3. Левое ребро получает метку 0, правое – 1
4. Повторяют шаги 2 и 3, пока не останется одна вершина. Ее вес =1.
Чтобы получить код символа, нужно спустится к нему от корня дерева, выписывая метки на ребрах.
Слайд 26Код Хаффмана
Пример 2
Построить код Хаффмана для
алфавита из Примера 1 и оценить его избыточность
Слайд 28Пример 3. Построим неравномерный код, учитывающий частоту символов
e – 0
a
– 1
b – 00
c – 01
d - 11
Слайд 29 Можно ли однозначно декодировать код, полученный в примере
3?
Пусть этим кодом закодировано сообщение
b c d
- 000111Декодируем: eeeaaa
Слайд 30Закодированные неравномерным кодом сообщения могут декодироваться только если коды обладают
свойством префиксности:
ни одна кодовая комбинация не является началом другой
кодовой комбинации Данное свойство еще называют критерием различимости Фано
Слайд 32 Вопрос
При использовании префиксного кодирования, если имеется
код 1010, какой код нельзя использовать?
00
01
10
11
Слайд 33Вывод: алгоритмы экономичного кодирования должны:
1. учитывать частоту появления символов первичного
алфавита в сообщении
2. формировать префиксные коды
Слайд 34Недостаток неравномерного кодирования
Если в процессе передачи сообщения произойдет хотя бы
одна ошибка, то станет невозможным декодирование всего дальнейшего текста
Для
равномерного алфавитного кода ошибка приведет к невозможности декодировать только один символ алфавита и не распространится далее
Слайд 36Упражнение 1
В алфавите 5 символов: м, и, р,
у,-
Закодировать текст «миру-мир», записанный с помощью символов данного
алфавита равномерным кодом
Слайд 39
Исходный алфавит содержит восемь символов, которые могут
появляться в сообщениях с вероятностями:
р1=0,22
р2=р3=0,16
р4=р5=0,10
р6=0,04
р7= 0,20
р8=0,02
Построить код Хаффмана для
этого алфавитаУпражнение 4
Слайд 40Пусть имеется следующая таблица префиксных кодов:
Требуется декодировать сообщение: 00100010000111010101110000110
Сможем ли
мы декодировать это сообщение, если помеха исказит 3й символ?
Упражнение 5
Слайд 42Задание 1
Для кодирования букв А, Б, В, Г решили использовать
двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если
таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится1) 4B(16) 2) 411(16) 3)BACD(16) 4) 1023(16)
Слайд 43Задание 2
Для кодирования некоторой последовательности, состоящей из букв А, Б,
В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно
декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны.Каким из указанных способов это можно сделать?
1) для буквы В – 101 2) это невозможно
3) для буквы В – 010 4) для буквы Б – 10
Слайд 44Задание 3
По каналу связи передаются сообщения, содержащие только 4 буквы:
Л, Е,Т, О; для передачи используется двоичный код, допускающий однозначное
декодирование. Для букв Т, О, Л используются такие кодовые слова: Т – 101, О – 01, Л – 11. Укажите такое кодовое слово для буквы Е, при котором код будет допускать однозначное декодирование, при этом его длина должна быть наименьшей.
Слайд 45Задание 4
По каналу связи передаются сообщения, содержащие только шесть букв:
А, B, C, D, E, F. Для передачи используется неравномерный
двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 00, B – 010, C – 1. Какова наименьшая возможная суммарная длина всех кодовых слов?
Слайд 46Задание 5
В сообщении встречается 40 букв А, 15
букв Б, 18 букв В и по 10 букв Г
и Д.При его передаче использован неравномерный двоичный префиксный код, который позволил получить минимальную длину закодированного сообщения. Какова она в битах?
Слайд 47Задание 6
По каналу связи передаются сообщения, содержащие только 4 буквы:
А, И, С, Т.
В любом сообщении больше всего букв
А, следующая по частоте буква – С, затем – И. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?А – 0, И – 1, С – 00, Т – 11
С – 1, И – 0, А – 01, Т – 10
А – 1, И – 01, С – 001, Т – 000
С – 0, И – 11, А – 101, Т – 100
