Слайд 2
Литература
Алгебраическая теория кодирования Автор: Берлекэмп Э. Издательство: Мир
Год: 1971
Теория кодов, исправляющих ошибки
Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А.
Издательство: Связь Год: 1979
Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Морелос-Сарагоса Р..: Издательство: Техносфера, Год: 2006.
Слайд 3
Кодирование информации
Кодирование источника – устранение «лишней», сжатие информации
Кодирование
канала – добавление избыточности для обнаружения и/или исправления ошибок
(в результате шума) – защита от случайных воздействий
Слайд 4
Шум
Может произойти из-за магнитной бури, молнии, метеоритного дождя,
случайного искажения звука в радиопередаче, плохой печати изображения или
текста, плохой слышимости …
В результате шума сообщение может исказиться
Слайд 5
Канал
Например, телефонная линия или атмосфера
Слайд 6
Методы борьбы со случайными ошибками
Введение избыточности
Цели: обнаружение и\или
исправление ошибок
Слайд 9
Модель ошибки
Ошибка – замена в двоичном сообщении 0
на 1 и\или наоборот, замена 1 на 0
Пример: ИСХОДНОЕ
СЛОВО: 00010100
ОШИБОЧНЫЕ СЛОВА: 00110100, 00000100, 00101100
Слайд 10
Другие модели
Стирающий канал
Канал со вставками
Слайд 12
Передача по зашумленному каналу
Слайд 13
Передача по зашумленному каналу
Пример:
в результате шума сообщение 00000
искажается в 01001
Слайд 14
Продолжение примера
Кодирование:
Код – множество кодовых слов:
Слайд 15
Метод борьбы с шумом
Избыточность
0 кодируется как 00000,
а
1 кодируется как 11111.
Слайд 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
Другие модели каналов
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) = P0
Z-канал (оптический)
Стирающий канал(MAC)
Слайд 24
BER – bit error rate
Это средняя вероятность ошибки
одного бита передаваемой информации
Слайд 25
Помехоустойчивое кодирование – две стратегии
Исправление ошибки за счет
избыточности (FEC – forward error correction)
Обнаружение ошибок с последующим
запросом на повторную передачу ошибочно принятой информации ( ARR – automatic repeat request)
Слайд 27
Помехоустойчивое кодирование – области применения
Хранение информации с высокой
плотностью записи –CD-ROM, DVD
Передача данных при ограниченной мощности сигнала
–спутниковая и мобильная связь
Передача информации по сильно зашумленным каналам – высокоскоростные проводные линии связи, мобильная связь
Передача данных по каналам связи с повышенными требованиями к надежности информации – вычислительные сети, линии передачи со сжатием
Слайд 28
Кодирование – замена информационного слова на кодовое
Пример.
Слайд 29
Кодирование – замена информационного слова на кодовое
В общем
случае: B={0,1}
Двоичное кодирование:
Слайд 30
Расстояние Хэмминга между двумя словами есть число разрядов,
в которых эти слова различаются
Слайд 31
10.
1. Расстояние Хэмминга d(000, 011) есть 2 :
Пример
2. Расстояние Хэмминга d(10101, 11110) равно 3
Слайд 32
Декодирование – исправление ошибки, если она произошла
Множество кодовых
слов {00000,01101,10110,11011}
Если полученное слово 10000, то декодируем в «ближайшее»
слово 00000
Если полученное слово 11000 – то только обнаружение, так как два варианта: 11000 – в 00000 или 11000 – в 11011
