Презентация на тему: Помехоустойчивое кодирование

Алгебраическая теория кодирования Автор: Берлекэмп Э. Издательство: Мир Год: 1971 Алгебраическая теория кодирования Автор: Берлекэмп Э. Издательство: Мир Год: 1971 Теория кодов, исправляющих ошибки Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Издательство: Связь Год: 1979 Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Морелос-Сарагоса Р..: Издательство: Техносфера, Год: 2006.

Кодирование источника – устранение «лишней», сжатие информации Кодирование источника – устранение «лишней», сжатие информации Кодирование канала – добавление избыточности для обнаружения и/или исправления ошибок (в результате шума) – защита от случайных воздействий

Может произойти из-за магнитной бури, молнии, метеоритного дождя, случайного искажения звука в радиопередаче, плохой печати изображения или текста, плохой слышимости … Может произойти из-за магнитной бури, молнии, метеоритного дождя, случайного искажения звука в радиопередаче, плохой печати изображения или текста, плохой слышимости … В результате шума сообщение может исказиться

Например, телефонная линия или атмосфера Например, телефонная линия или атмосфера

Введение избыточности Введение избыточности Цели: обнаружение и\или исправление ошибок

Ошибка – замена в двоичном сообщении 0 на 1 и\или наоборот, замена 1 на 0 Ошибка – замена в двоичном сообщении 0 на 1 и\или наоборот, замена 1 на 0

Стирающий канал Стирающий канал Канал со вставками

Пример: в результате шума сообщение 00000 искажается в 01001

Кодирование: Кодирование: Код – множество кодовых слов:

Избыточность

1. Быстрое кодирование информации. 1. Быстрое кодирование информации. 2. Простой способ передачи закодированного сообщения. 3. Быстрое декодирование полученной информации. 4. Надежная очистка от шума. 5. Передача максимального объема информации в единицу времени.

Это средняя вероятность ошибки одного бита передаваемой информации Это средняя вероятность ошибки одного бита передаваемой информации

Исправление ошибки за счет избыточности (FEC – forward error correction) Исправление ошибки за счет избыточности (FEC – forward error correction) Обнаружение ошибок с последующим запросом на повторную передачу ошибочно принятой информации ( ARR – automatic repeat request)

Хранение информации с высокой плотностью записи –CD-ROM, DVD Хранение информации с высокой плотностью записи –CD-ROM, DVD Передача данных при ограниченной мощности сигнала –спутниковая и мобильная связь Передача информации по сильно зашумленным каналам – высокоскоростные проводные линии связи, мобильная связь Передача данных по каналам связи с повышенными требованиями к надежности информации – вычислительные сети, линии передачи со сжатием

Пример. Пример.

В общем случае: B={0,1} В общем случае: B={0,1} Двоичное кодирование:

Множество кодовых слов {00000,01101,10110,11011} Множество кодовых слов {00000,01101,10110,11011} Если полученное слово 10000, то декодируем в «ближайшее» слово 00000 Если полученное слово 11000 – то только обнаружение, так как два варианта: 11000 – в 00000 или 11000 – в 11011

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