Помехоустойчивое кодирование Основные идеи. Литература Алгебраическая теория кодирования Автор: Берлекэмп Э. Издательство: Мир Год: 1971 Теория кодов, - презентация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23 Другие модели каналов (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)

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

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

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

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

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

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

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

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

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

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