Коррекция ошибок при передаче данных 10 класс семакин презентация

Слайд 1

Коррекция ошибок при передаче данных

Слайд 2

Символ Двоичный код Кодовое слово 0 1 2 3 4 5 6 7 8 9 Помехоустойчивый код Хемминга основные понятия – кодовое слово

Слайд 3

Символ Двоичный код Кодовое слово 0 0000 0000 1 0001 0001 2 0010 0010 3 0011 0011 4 0100 0100 5 0101 0101 6 0110 0110 7 0111 0111 8 1000 1000 9 1001 1001 Код Хемминга основные понятия – кодовое слово

Слайд 4

Символ Двоичный код Кодовое слово 0 0000 0000 000 1 0001 0001 111 2 0010 0010 110 3 0011 0011 001 4 0100 0100 101 5 0101 0101 010 6 0110 0110 011 7 0111 0111 100 8 1000 1000 011 9 1001 1001 100 Код Хемминга основные понятия – кодовое слово

Слайд 5

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 ? 4 0100 0100 101 ? 5 0101 0101 010 3 6 0110 0110 011 ? 7 0111 0111 100 ? 8 1000 1000 011 4 9 1001 1001 100

Слайд 6

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 4 4 0100 0100 101 4 5 0101 0101 010 3 6 0110 0110 011 ? 7 0111 0111 100 ? 8 1000 1000 011 4 9 1001 1001 100

Слайд 7

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 4 4 0100 0100 101 4 5 0101 0101 010 3 6 0110 0110 011 4 7 0111 0111 100 7 8 1000 1000 011 4 9 1001 1001 100

Слайд 8

АЛГОРИТМ ПОИСКА ПОМЕХ Разделить полученное сообщение на 7-битовые слова 1000011 1001111 0110010 0100101 Сравниваем каждую группу с кодовым словом из кода Хемминга

Слайд 9

1000011 Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 10

1001111 Если в таблице есть слово, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 11

0110010 Если в таблице есть слова, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 12

0100101 Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 13

Следовательно, передано сообщение: 8164. Если в таблице есть слова, расстояние от которого до полученного равно 2, тогда слово исправить нельзя.

Слайд 14

Практическая часть Реализуйте программу Hemming в системе программирования на Паскале (смотрите стр. 93 — 96). Выполните описанные тесты. ДОМАШНЕЕ ЗАДАНИЕ. § 1.5.3

Проверка четности. Контрольная сумма. Блочные и древовидные коды. Вес и расстояние Хэмминга между двоичными словами.

Коды делятся на два больших класса

Коды с исправлением ошибок  

Цель восстановить с вероятностью, близкой к единице, посланное сообщение.

Коды с обнаружением ошибок  

Цель выявить с вероятностью, близкой к единице, наличие ошибок.

Коды с обнаружением ошибок в передаче

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

Например,

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

Разрешенные кодовые комбинации

Запрещенные кодовые комбинации

Коды с обнаружением ошибок в передаче

В результате контроля четности оди-ночная ошибка в любом разряде, изменившая число единиц в комбинации кода на нечетное, будет обнаружена.

Минимально возможное число позиций кода, на которых символы одной комбинации кода отличаются от любой другой его комбинации, называется его кодовым (хэмминговым) расстоянием .

Оно находится путем сложения по модулю 2 всех комбинаций кода:

d ij

Разрешенные кодовые комбинации

Запрещенные кодовые комбинации

Виды корректирующих кодов

Коды с исправлением ошибок в передаче

Коды, которые позволяют не только обнаружить ошибку, но и определить номер искаженного символа (позиции), называются кодами с исправлением ошибок .

Для исправления одиночной ошибки придется увеличить кодовое расстояние минимум до 3, двухкратной до 4 и т. п.

В блоковых (блочных) кодах входная непрерывная последовательность информационных символов разбивается на блоки, содержащие k сим — волов.

k . Этот набор, называемый кодовым словом , передается по каналу связи, искажается шумами и помехами, а затем декодируется независимо от всех других кодовых слов. Величина n называется длиной канального кода или длиной канального блока . Каждое сообщение в этом случае передаётся собственным кодовым словом. Кодовые слова могут объединяться в группы – кодовые предложения или фразы, объединённые некоторой общностью, например, способом защиты от помех кодовых слов, входящих в блок, и т. п. » width=»640″

Все дальнейшие операции в кодере производятся над каждым блоком отдельно и независимо от других блоков.

Каждому информационному блоку из k символов ставится в соответствие набор из n символов кода канала передачи сообщений, где n k . Этот набор, называемый кодовым словом , передается по каналу связи, искажается шумами и помехами, а затем декодируется независимо от всех других кодовых слов.

Величина n называется длиной канального кода или длиной канального блока . Каждое сообщение в этом случае передаётся собственным кодовым словом.

Кодовые слова могут объединяться в группы – кодовые предложения или фразы, объединённые некоторой общностью, например, способом защиты от помех кодовых слов, входящих в блок, и т. п.

К онтрольная сумма — это некоторое значение, вычисленное по определённой схеме на основе кодируемого сообщения.

Проверочная информация при  систематическом кодировании  приписывается к передаваемым данным.

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

Без контрольной суммы, передавать данные опасно, так как помехи присутствуют везде и всегда, весь вопрос только в их вероятности возникновения и вызываемых ими побочных эффектах.

В зависимости от условий и выбирается алгоритм выявления ошибок и количество данных в контрольной сумме.

Чем сложнее алгоритм, и больше контрольная сумма, тем меньше не распознанных ошибок.

Все алгебраические коды можно разделить на два больших класса:

Блочные (блоковые)

Непрерывные

(древовидные)

Блочные коды представляют собой совокупность кодовых символов, состоящих из отдельных комбинаций (блоков) элементов символов кода, которые кодируются и декодируются независимо. 

Непрерывные (древовидные) коды представляют собой непрерывную последовательность кодовых символов, причем введение проверочных элементов производится непрерывно, без разделения ее на независимые блоки.

В древовидных (непрерывных) кодах информационная последовательность подвергается обработке без предварительного разбиения на независимые блоки. Длинной, полубесконечной информационной последовательности ставится в соответствие кодовая последовательность, состоящая из большего числа символов.

Непрерывными эти коды называются потому, что операции кодирования и декодирования в них совершаются непрерывно. Они способны исправлять пакетные ошибки при сравнительно простых алгоритмах кодирования и декодирования .

Свойства кодов с исправлением ошибок в передаче

Кодированный цифровой сигнал приобретает свойства обнаружения, а иногда и исправления ошибок, возникающих в процессе передачи и приёма сообщений, т. е. свойство помехозащищенности .

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

Первыми появились блоковые коды, они же также лучше теоретически исследованы. Из древовидных кодов проще всего с точки зрения реализации свёрточные и цепные коды .

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

Расстоя́ние и вес Хэ́мминга

Пусть  u =( u 1 ,  u 2 ,  … ,  u n ) – двоичная последовательность длиной  n .

Число единиц в этой последовательности называется   весом Хэмминга   вектор а   u   и обозначается как   w(u).

Например:  u =( 1 0 0 1 0 1 1 ), тогда  w ( u )= 4 .

Пусть  u   и   v  – двоичные слова длиной   n .

Число разрядов, в которых эти слова различаются, называется   расстоянием Хэмминга   между  u  и  v и обозначается как   d(u, v) .

Например:  u =( 1 0 0 1 0 1 1 ),  v =( 0 1 0 0 0 1 1 ), тогда  d ( u ,  v )= 3 .

Самостоятельно

Найти вес и кодовое расстояние для двоичных слов

• a=011011100
• b=100111001

Решение:  Вес для двоичных слов  w(a)=5    ;  w(b)=  5 .

Кодовое расстояние d(A,B) = 6.

1.

2.

Контроль ошибок состоит в обнаружении и исправлении ошибок в
данных при их записи и воспроизведении или передаче по линиям связи.
В системах связи возможны несколько стратегий борьбы с ошибками:
• Обнаружение ошибок в блоках данных и автоматический запрос повторной
передачи повреждённых
• Обнаружение ошибок в блоках данных и отбрасывание повреждённых
блоков (такой подход иногда применяется в системах потокового
мультимедиа, где важна задержка передачи и нет времени на повторную
передачу)
• Упреждающая коррекция ошибок добавляет к передаваемой информации
такие дополнительные данные, которые позволяют исправить ошибки без
дополнительного запроса.

3.

Стратегии исправления ошибок.
Упреждающая коррекция ошибок (также прямая коррекция
ошибок, англ. Forward Error Correction, FEC) — техника
помехоустойчивого кодирования и декодирования, позволяющая
исправлять ошибки методом упреждения. Применяется для
исправления сбоев и ошибок при передаче данных путём
передачи избыточной служебной информации, на основе
которой может быть восстановлено первоначальное содержание.
На практике широко используется в сетях передачи данных в
телекоммуникационных технологиях.

4.

Автоматический запрос повторной передачи
Распространены следующие методы автоматического запроса:
Запрос ARQ с остановками (англ. stop-and-wait ARQ)
Передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных
перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой,
приемник передает отрицательное подтверждение и передатчик повторяет передачу блока. Его
недостатком является низкая скорость из-за высоких накладных расходов на ожидание.
Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)
Передача данных от передатчика к приемнику производится одновременно. В случае ошибки
передача возобновляется, начиная с ошибочного блока (то есть передается ошибочный блок и все
последующие). Осуществляется передача только ошибочно принятых блоков данных.

5.

Корректирующий код (также помехоустойчивый код) — код,
предназначенный для обнаружения и исправления ошибок.
Коды обнаружения ошибок — могут только установить факт ошибки.
Применяются в сетевых протоколах.
Коды, исправляющие ошибки — могут установить факт ошибки и исправить ее
(при этом он будет способен обнаружить бо́льшее число ошибок, чем был
способен исправить).
Применяются в системах цифровой связи, в том числе: спутниковой,
радиорелейной, сотовой, передаче данных по телефонным каналам, а также в
системах хранения информации, в том числе магнитных и оптических.

6.

По способу работы с данными коды, исправляющие ошибки, бывают:
Блоковые
Делят информацию на фрагменты постоянной длины и обрабатывают каждый
из них в отдельности. Блоковые коды делятся на:
— Линейные коды общего вида (Коды Хэмминга)
— Линейные циклические коды (Коды CRC, Коды БЧХ)
Свёрточные
Работают с данными как с непрерывным потоком.
Кодирование производится с помощью регистра сдвига
Декодирование производится по алгоритму Витерби

7.

Методы защиты информации при передаче
по каналам
Распространены следующие
методысвязи
автоматического запроса:
Криптогра́фия — наука о методах обеспечения конфиденциальности
(невозможности прочтения информации посторонним), целостности данных
(невозможности незаметного изменения информации), аутентификации
(проверки подлинности авторства или иных свойств объекта), шифрования
(кодировка данных).
Известные криптографические методы защиты информации можно разбить
на два класса:
1) Шифрование — обработка информации путем замены и перемещения букв,
при котором объем данных не меняется
2) Кодирование — сжатие информации с помощью замены отдельных
сочетаний букв, слов или фраз.

8.

Требования алгоритмам шифрования
• Высокий уровень защиты данных против дешифрования и возможной
модификации;
• Защищенность информации должна основываться только на знании ключа
и не зависеть от того, известен алгоритм или нет (правило Киркхоффа)
• Малое изменение исходного текста или ключа должно приводить к
значительному изменению шифрованного текста (эффект «обвала»)
• Область значений ключа должна исключать возможность дешифрования
данных путем перебора значений ключа
• Экономичность реализации алгоритма при достаточном быстродействии
• Стоимость дешифрования данных без знания ключа должна превышать
стоимость данных

9.

Современные алгоритмы
шифрования
Симметричное шифрование
Стандарт ГОСТ 28147-89
Стандарт AES
Асимметричное шифрование
Алгоритм RSA

10.

.
Стеганография
Способ передачи или хранения информации с учётом сохранения
в тайне самого факта такой передачи (хранения).
В отличие от криптографии, которая скрывает содержимое
тайного сообщения, стеганография скрывает сам факт его
существования.

11.

.
Классификация стеганографии
Классическая
Компьютерная
Цифровая

12.

.
Классическая стеганография
• Использование симпатических (невидимых) чернил
• Запись на боковой стороне колоды карт, расположенных в условленном
порядке
• Запись внутри варёного яйца
• «Жаргонные шифры», где слова имеют другое обусловленное значение;
• Геометрическая форма — метод, в котором отправитель старается скрыть
ценную информацию, поместив её в сообщение так, чтобы важные слова
расположились в нужных местах или в узлах пересечения геометрического
рисунка
• Семаграммы — секретные сообщения, в которых в качестве шифра
используются различные знаки, за исключением букв и цифр
• Узелки на нитках

13.

.
Компьютерная стеганография
Использование зарезервированных полей компьютерных форматов файлов (часть
поля расширений, не заполненная информацией о расширении, по умолчанию заполняется
нулями. Соответственно мы можем использовать эту «нулевую» часть для записи своих
данных.)
Недостаток: низкая степень скрытности и малый объём передаваемой информации.
Метод скрытия информации в неиспользуемых местах гибких дисков (информация
записывается в неиспользуемые части диска)
Недостатки: маленькая производительность, передача небольших по объёму сообщений.
Метод использования особых свойств полей форматов, которые не отображаются на
экране основан на специальных «невидимых» полях для получения сносок, указателей. К
примеру, написание чёрным шрифтом на чёрном фоне.
Недостатки: маленькая производительность, небольшой объём передаваемой информации.

14.

.
Цифровая стеганография
Направление классической стеганографии, основанное на сокрытии или
внедрении дополнительной информации в цифровые объекты, вызывая при
этом некоторые искажения этих объектов.
Данные объекты являются мультимедиа-объектами и внесение искажений,
которые находятся ниже порога чувствительности среднестатистического
человека, не приводит к заметным изменениям этих объектов.
В оцифрованных объектах, изначально имеющих аналоговую природу, всегда
присутствует шум квантования; далее, при воспроизведении этих объектов
появляется дополнительный аналоговый шум и нелинейные искажения
аппаратуры, все это способствует большей незаметности сокрытой информации.

1


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер Тема: «Передача информации» Вы узнаете: Модель К.Шеннона передачи информации по техническим каналам связи. Количественные характеристики передачи информации. Вы научитесь: Рассчитывать объем информации, передаваемый по каналам связи, при известной скорости передачи 10 класс

2


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер Справка Клод Элвуд Шеннон (Claude Elwood Shannon, 1916, учился в Мичигане, защитил диссертацию в MIT по применению булевой алгебры для оптимизации работы реле, с 1956 года преподавал в MIT, работал как математик- исследователь в телефонной компании Белла с 1941 по 1972 год. В 1948 году вышла в свет его Математическая Теория Связи (A Mathematical Theory of Communication), что ознаменовало создание общей теории передачи и обработки информации. Он предложил линейную схематическую модель системы коммуникации и дал метод анализа ошибок в сигнале. В 1966 году награжден Национальной медалью науки.

3


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер Модель передачи информации по техническим каналам связи (автор Клод Шеннон) Источник информации Кодирующее устройство Канал связи Декодирующее устройство Приемник информации Защита от шума Шум Кодирование – любое преобразование информации, идущей от источника, в форму, пригодную для ее передачи по каналу связи. Модем Интернет

4


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер Пример Схема передачи информации по сотовой связи в форме SMS-сообщения

5


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер Пропускная способность канала – это максимально возможная скорость передачи информации Единицы измерения: бит/с (биты в секунду), Кбиты/с (килобиты в секунду), Мбиты/с (мегабиты в секунду) Средства связиПропускная способность телефонные линииДесятки и сотни Кбит/с электрическая кабельная связьДесятки и сотни Мбит/с оптоволоконная кабельная связьДесятки и сотни Мбит/с радиосвязьДесятки и сотни Мбит/с Пропускная способность канала зависит от средства связи, способа кодирования информации, шума

6


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер Шум – это разного рода помехи, искажающие передаваемый сигнал и приводящие к потере информации Причины: Плохое качество линий связи Незащищенность друг от друга различных потоков информации, передаваемых по одним и тем же каналам

7


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер Способы защиты от шума Использование экранированного кабеля вместо «голого» провода Применение фильтров Кодирование с оптимально-избыточным кодом

8


© Машенкова Н.А., 2011 по материалам УМК «Информатика и ИКТ» классы, авторы И.Г.Семакин, Е.К.Хеннер СХЕМА КЛОДА ШЕННОНА Источник информации Приемник информации Защита от шума (технические способы защиты каналов связи + избыточный код) Шум (помехи) ДКДУ – декодирующее устройствоКДУ – кодирующее устройство КДУДКДУ Канал связи В первую очередь применяются технические способы защиты каналов связи от воздействия шумов (экранирование проводов, применение фильтров)..Клодом Шенноном была разработана специальная теория кодирования, дающая методы борьбы с шумом. Одна их важных идей этой теории состоит в том, что передаваемый по линии связи код должен быть избыточным. Однако нельзя делать избыточность слишком большой. Это приведет к задержкам и удорожанию связи. Теория кодирования К. Шеннона дает возможность получить оптимальный код (избыточность кода минимально возможная, а достоверность принятой информации – максимально возможная). В современных системах цифровой связи часто применяется следующий прием борьбы с шумом. Все сообщение разбивается на порции (пакеты). Для каждого пакета вычисляется контрольная сумма, которая передается вместе с данным пакетом. В р, пока исходная и конечная контрольные суммы не совпадут. КОДИРОВАНИЕ – это преобразование информации, поступающей от источника в форму, пригодную для передачи ее по каналу связи. ДЕКОДИРОВАНИЕ – преобразование информации к форме, пригодной для восприятия приемником.