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

Содержание

• 
  Слайд 1

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

  Основные идеи

• 
  Слайд 2

  Литература

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

• 
  Слайд 3

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

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

• 
  Слайд 4

  Шум

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

• 
  Слайд 5

  Канал

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

• 
  Слайд 6

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

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

• 
  Слайд 7
  

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

• 
  Слайд 8
  

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

• 
  Слайд 9

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

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

• 
  Слайд 10

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

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

• 
  Слайд 11
  

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

• 
  Слайд 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)

• 
  Слайд 26
  

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

• 
  Слайд 27

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

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

• 
  Слайд 28

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

  Пример.

• 
  Слайд 29
  

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

• 
  Слайд 30
  

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

• 
  Слайд 31
  

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

• 
  Слайд 32

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

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

• 
  Слайд 33

  Выводы

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