Помехоустойчивое кодирование Основные идеи

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

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

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

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

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

Ошибка в одном разряде

Пакет ошибок длины 8

Модель ошибки Ошибка – замена в двоичном сообщении 0 на 1 и\или наоборот, замена 1 на 0 Пример: ИСХОДНОЕ СЛОВО: ОШИБОЧНЫЕ СЛОВА: , ,

Другие модели Стирающий канал Канал со вставками

Структура кодера и декодера

Передача по зашумленному каналу

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

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

Метод борьбы с шумом Избыточность 0 кодируется как 00000, а 1 кодируется как

Пример(1) Сообщение Алисы: NNWNNWWSSWWNNNNWWN

Пример(2) Сообщение Алисы: NNWNNWWSSWWNNNNWWN Исходное множество символов: {E,W.S,N} Множество кодовых слов {00,01,10,11} – любая ошибка приводит к катастрофе

Пример(3) Сообщение Алисы: NNWNNWWSSWWNNNNWWN Исходное множество символов: {E,W.S,N} Множество кодовых слов {000,011,101,110} – обнаружение любой ошибки

Пример(4) Сообщение Алисы: NNWNNWWSSWWNNNNWWN Исходное множество символов: {E,W.S,N} Множество кодовых слов {00000,01101,10110,11011} – локализация ошибки – возможно ее исправление

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

ДСК – двоичный симметричный канал

двоичный : (0,1) симметричный: p( 0 1) =p(1 0)

Другие модели каналов (light on) 1 (light off) p 1-p X Y P(X=0) = P E10E1 1-e e 1-e P(X=0) = P 0 Z-канал (оптический) Стирающий канал(MAC)

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

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

Блоковые коды

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

Кодирование – замена информационного слова на кодовое Пример. Информационное слово Кодовое слово

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

Расстояние Хэмминга между двумя словами есть число разрядов, в которых эти слова различаются

Расстояние Хэмминга d(000, 011) есть 2 : Пример 2. Расстояние Хэмминга d(10101, 11110) равно 3

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

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