Помехоустойчивое кодирование Свойства линейных кодов. - презентация

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

2 Расстояние и вес Хэмминга Пусть заданы двоичные слова Расстояние Хэмминга Вес Хэмминга

3 Расстояние Хэмминга Пусть - линейный код и Тогда и их поразрядная сумма Обозначим Получим Расстояние Хэмминга

4 Минимальное расстояние Хэмминга минимальный вес кода

5 Модель ошибки Замена В линейном пространстве n-разрядных двоичных столбцов это равносильно преобразованию кодового слова: - вектор ошибки

6 Модель ошибки Если в кодовом слове произошло t ошибок, то ошибочное слово находится на расстоянии t от кодового. Или вес вектора ошибки равен t:

7 Синдромное декодирование линейного кода

8 Корректирующая способность линейного кода – геометрическая иллюстрация Шар с центром в кодовом слове – кодовое слово + ошибочные слова из столбца при синдромном декодировании

9 Модель ошибки – геометрическая интерпретация Центры шара – кодовые слова Шар – кодовое слово и всевозможные ошибочные слова, полученные из кодового слова

10 Корректирующая способность линейного кода Случай 1. Распознаваемая и исправляемая ошибка( Случай 1. Распознаваемая и исправляемая ошибка ( ошибочное слово находится внутри «своей» сферы)

11 Корректирующая способность линейного кода Случай 2. Распознаваемая ошибка (ошибочное слово – вне «своей» сферы)

12 Случай 3. Необнаруженная ошибка (ошибочное слово совпадает с некоторым кодовым словом)

13 Случай 4. Отказ от декодирования(ошибочное слово не принадлежит ни однму из шаров)

14 Модель ошибки – геометрическая интерпретация Ошибка распознается и исправляется, если шары не пересекаются и ошибочные слова - внутри сферы.

15 Пример – систематический (7,4)-код Хэмминга - проверочная матрица

16 Пример – систематический (7,4)-код Хэмминга d=3, t=1 Кодовые слова: , , ,……..

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

18 Совершенный код

19 Совершенные коды Коды, в которых непересекающиеся сферические области декодирования покрывают все пространство двоичных слов, называются совершенными или плотноупакованными. Пусть дан (n,k)–код, исправляющий t ошибок. Тогда каждый шар содержит ровно слов (объем шара) Всего кодовых слов (всего шаров) -

20 Совершенный код Отсюда Или

21 Граница Хэмминга Отсюда Или Для совершенных кодов