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

Литература

Алгебраическая теория кодирования Автор: Берлекэмп Э. Издательство: Мир Год: 1971
Теория кодов,

Кодирование информации

Кодирование источника – устранение «лишней», сжатие информации
Кодирование канала – добавление

Шум

Может произойти из-за магнитной бури, молнии, метеоритного дождя, случайного искажения звука

Канал

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

Методы борьбы со случайными ошибками

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

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

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

Модель ошибки

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

Другие модели

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

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

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

Передача по зашумленному каналу
Пример: в результате шума сообщение 00000 искажается в 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. Простой способ

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

Другие модели каналов

0
1

0 (light on)
1 (light off)

p
1-p

X Y

P(X=0) = P0

0
1

0
E
1

1-e
e
e
1-e

P(X=0)

BER – bit error rate

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

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

Исправление ошибки за счет избыточности (FEC –

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

Помехоустойчивое кодирование – области применения

Хранение информации с высокой плотностью записи –CD-ROM,

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

Пример.

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

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

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

10.
1. Расстояние Хэмминга d(000, 011) есть 2 :

Пример

2. Расстояние Хэмминга

Декодирование – исправление ошибки, если она произошла

Множество кодовых слов {00000,01101,10110,11011}
Если полученное