Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Презентации / Передача данных по каналу связи. Однозначное декодирование (условие Фано; расстояние Хемминга). Подготовка к ЕГЭ
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

Передача данных по каналу связи. Однозначное декодирование (условие Фано; расстояние Хемминга). Подготовка к ЕГЭ

библиотека
материалов
Передача данных по каналу связи Однозначное декодирование В. И. Долженкова по...
Задача №1 По каналу связи передаются сообщения, содержащие только 4 буквы П,...
Условие Фано •	закодированное сообщение можно однозначно декодировать с начал...
Рассмотрим букву О (закодировано «0») Условие Фано выполняется для ряда данны...
Рассмотрим в качестве кодового слова «1» (длина в один символ) Не может быть...
Рассмотрим в качестве кодового слова длиной в два символа 10 и 11 (см. граф)...
Рассмотрим в качестве кодового слова длиной в три символа варианты (см. граф)...
Задача №2 Для кодирования некоторой последовательности, состоящей из букв А,...
Рассмортим А (кодируется «0») «прямое» и «обратное» условие Фано выполняется...
Рассмотрим варианты ответа: 4) для буквы Б – 10 Нельзя использовать, т.к. код...
Рассмотрим варианты ответа: 3) для буквы В – 010 Нельзя использовать, т.к. ко...
Рассмотрим варианты ответа: для буквы В – 101 Можно использовать, т.к код бук...
Задача №3 По каналу связи передаются сообщения, содержащие только 4 буквы: А,...
Рассмотрим варианты ответа: А – 0, И – 1, С – 00, Т – 11 	 2) С – 1, И – 0, А...
Фрагмент условия: «… В любом сообщении больше всего букв А, следующая по част...
Задача №4 По каналу связи передаются сообщения, содержащие только 4 буквы: Е,...
Расстояние Хэмминга Расстояние Хэмминга — число позиций, в которых соответств...
Рассмотрим варианты ответов: 1) 11111 		 проверяем расстояние между известным...
Рассмотрим варианты ответов: 2) 11100	 для второго ответа 11100 получаем мини...
Рассмотрим варианты ответов: 3) 00011	 для третьего ответа 00011 получаем мин...
20 1

Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Описание презентации по отдельным слайдам:

№ слайда 1 Передача данных по каналу связи Однозначное декодирование В. И. Долженкова по
Описание слайда:

Передача данных по каналу связи Однозначное декодирование В. И. Долженкова по материалам сайта К. Полякова http://kpolyakov.spb.ru/school/ppt.htm и Д. Гущина http://inf.reshuege.ru/

№ слайда 2 Задача №1 По каналу связи передаются сообщения, содержащие только 4 буквы П,
Описание слайда:

Задача №1 По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

№ слайда 3 Условие Фано •	закодированное сообщение можно однозначно декодировать с начал
Описание слайда:

Условие Фано • закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова; • закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова; • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

№ слайда 4 Рассмотрим букву О (закодировано «0») Условие Фано выполняется для ряда данны
Описание слайда:

Рассмотрим букву О (закодировано «0») Условие Фано выполняется для ряда данных, так как ни одно значение более не начинается и не заканчивается на 0.

№ слайда 5 Рассмотрим в качестве кодового слова «1» (длина в один символ) Не может быть
Описание слайда:

Рассмотрим в качестве кодового слова «1» (длина в один символ) Не может быть использовано, т.к. код Т – 111, а код П – 100 Нарушается условие Фано

№ слайда 6 Рассмотрим в качестве кодового слова длиной в два символа 10 и 11 (см. граф)
Описание слайда:

Рассмотрим в качестве кодового слова длиной в два символа 10 и 11 (см. граф) П - 100 Т – 111 Вывод: не подходит! 1 0 1

№ слайда 7 Рассмотрим в качестве кодового слова длиной в три символа варианты (см. граф)
Описание слайда:

Рассмотрим в качестве кодового слова длиной в три символа варианты (см. граф) Варианты: 100, 101,110,111 Уже заняты трехбуквенные коды для Т – 111 и для П – 100 Кратчайшее кодовое слово для С будет 101! 101<110 (см. условие задачи) ОТВЕТ: 101 1 0 1 0 0 1 1

№ слайда 8 Задача №2 Для кодирования некоторой последовательности, состоящей из букв А,
Описание слайда:

Задача №2 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать? 1) для буквы В – 101 2) это невозможно 3) для буквы В – 010 4) для буквы Б – 10

№ слайда 9 Рассмортим А (кодируется «0») «прямое» и «обратное» условие Фано выполняется
Описание слайда:

Рассмортим А (кодируется «0») «прямое» и «обратное» условие Фано выполняется для кодов остальных букв: Б – 100 В – 1010 Г – 111 Сократить нужно так, чтоб выполнялись оба условий Фано

№ слайда 10 Рассмотрим варианты ответа: 4) для буквы Б – 10 Нельзя использовать, т.к. код
Описание слайда:

Рассмотрим варианты ответа: 4) для буквы Б – 10 Нельзя использовать, т.к. код буквы В начинается с 10 – нового кода буквы Б Нельзя использовать, т.к. код буквы Б начинается с 10 – нового кода буквы В (если бы был такой вариант ответа)

№ слайда 11 Рассмотрим варианты ответа: 3) для буквы В – 010 Нельзя использовать, т.к. ко
Описание слайда:

Рассмотрим варианты ответа: 3) для буквы В – 010 Нельзя использовать, т.к. код буквы А начинается с 0 – нового кода буквы В

№ слайда 12 Рассмотрим варианты ответа: для буквы В – 101 Можно использовать, т.к код бук
Описание слайда:

Рассмотрим варианты ответа: для буквы В – 101 Можно использовать, т.к код буквы В становится уникальным для данного ряда закодированных букв и «прямое» и «обратное» условие Фано соблюдается

№ слайда 13 Задача №3 По каналу связи передаются сообщения, содержащие только 4 буквы: А,
Описание слайда:

Задача №3 По каналу связи передаются сообщения, содержащие только 4 буквы: А, И, С, Т. В любом сообщении больше всего букв А, следующая по частоте буква – С, затем – И. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать? 1) А–0, И–1, С–00, Т–11 2) С–1, И–0, А–01, Т–10 3) А–1, И–01, С–001, Т–000 4) С–0, И–11, А–101, Т–100

№ слайда 14 Рассмотрим варианты ответа: А – 0, И – 1, С – 00, Т – 11 	 2) С – 1, И – 0, А
Описание слайда:

Рассмотрим варианты ответа: А – 0, И – 1, С – 00, Т – 11 2) С – 1, И – 0, А – 01, Т – 10 3) А – 1, И – 01, С – 001, Т – 000 4) С – 0, И – 11, А – 101, Т – 100 Варианты 1 и 2 не подходят! Не соблюдается условие Фано, поэтому, к рассмотрению принимаются только варианты 3 и 4

№ слайда 15 Фрагмент условия: «… В любом сообщении больше всего букв А, следующая по част
Описание слайда:

Фрагмент условия: «… В любом сообщении больше всего букв А, следующая по частоте буква – С, затем – И. Буква Т встречается реже, чем любая другая…» Для подобного рода условий действует правило: «чем чаще встречается буква, тем короче её код»! 3) А – 1, И – 01, С – 001, Т – 000 4) С – 0, И – 11, А – 101, Т – 100 Фрагмент условия: «…Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче…» Какой код более экономичный? ОТВЕТ: 3

№ слайда 16 Задача №4 По каналу связи передаются сообщения, содержащие только 4 буквы: Е,
Описание слайда:

Задача №4 По каналу связи передаются сообщения, содержащие только 4 буквы: Е, Н, О, Т. Для кодирования букв Е, Н, О используются 5-битовые кодовые слова: Е - 00000, Н - 00111, О - 11011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Т, чтобы указанное свойство выполнялось для всех четырёх кодовых слов? 11111 2) 11100 3) 00011 4) не подходит ни одно из указанных выше слов

№ слайда 17 Расстояние Хэмминга Расстояние Хэмминга — число позиций, в которых соответств
Описание слайда:

Расстояние Хэмминга Расстояние Хэмминга — число позиций, в которых соответствующие символы двух слов одинаковой длины различны Из условия задачи: «…Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях…» легко проверить, что для заданного кода (Е - 00000, Н - 00111, О - 11011) расстояние Хэмминга равно 3; в таблице выделены отличающиеся биты, их по три в парах Е-Н и Н-О и четыре в паре Е-О: Е – 00000 Е – 00000 Н – 00111 Н – 00111 О – 11011 О – 11011

№ слайда 18 Рассмотрим варианты ответов: 1) 11111 		 проверяем расстояние между известным
Описание слайда:

Рассмотрим варианты ответов: 1) 11111 проверяем расстояние между известными кодами и вариантами ответа; для первого ответа 11111 получаем минимальное расстояние 1 (в паре О-Т), этот вариант не подходит: Е – 00000 Н – 00111 О – 11011 Т - 11111 Т - 11111 Т - 11111

№ слайда 19 Рассмотрим варианты ответов: 2) 11100	 для второго ответа 11100 получаем мини
Описание слайда:

Рассмотрим варианты ответов: 2) 11100 для второго ответа 11100 получаем минимальное расстояние 3 (в парах Е-Т и О-Т): Е – 00000 Н – 00111 О – 11011 Т - 11100 Т - 11100 Т - 11100

№ слайда 20 Рассмотрим варианты ответов: 3) 00011	 для третьего ответа 00011 получаем мин
Описание слайда:

Рассмотрим варианты ответов: 3) 00011 для третьего ответа 00011 получаем минимальное расстояние 1 (в паре Н-Т) , этот вариант не подходит: Е – 00000 Н – 00111 О – 11011 Т - 00011 Т – 00011 Т - 00011 таким образом, расстояние Хэмминга, равное 3, сохраняется только для ответа 2 Ответ: 2.


Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 14.03.2016
Раздел Информатика
Подраздел Презентации
Просмотров912
Номер материала ДВ-527804
Получить свидетельство о публикации
Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх