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

Презентация:



Advertisements
Похожие презентации
Помехоустойчивое кодирование Вероятность ошибочного декодирования.
Advertisements

Помехоустойчивое кодирование Линейные коды. Некоторые предположения Блоковый код- код, в котором все слова имеют одинаковую длину. Кодовое слово – слово.
Помехоустойчивое кодирование Циклические коды – подкласс линейных кодов.
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ Презентация лекции по курсу «Общая теория связи» © Д.т.н., проф. Васюков В.Н., Новосибирский государственный.
Практическая работа 1 4 Теория информации. Теоретическая подготовка Подготовьте ответы на вопросы: В чём заключается сущность помехоустойчивого кодирования?
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ Федеральное государственное образовательное учреждение Среднего профессионального образования по Владимирской области «Гусевский.
Применение теории кодирования в криптографии Лось Антон Васильевич.
Исходная информация Информация и искажениями Сообщение с искажениями Сообщение Кодирование Шум Канал связи Декодирование.
§1 МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ 1.1 Матрицы и их свойства Матрицей размера m n называется совокупность mn чисел, расположенных в виде таблицы из m строк и n.
Системы линейных уравнений.. Системой m линейных уравнений с n неизвестными х 1, х 2, …, х n называется система вида a ij - коэффициенты системы, i=1,…,m;
Задача декодирования линейных кодов и некоторые применения помехоустойчивого кодирования.
Практическая 1-6 Циклические коды Теория информации.
Прямая в пространстве Каноническое уравнение прямой Параметрическое уравнение прямой Уравнение прямой, как линии пересечения двух плоскостей Угол между.
ГЛАВА 3 ЭЛЕМЕНТЫ АНАЛИТИЧЕСКОЙ ГЕОМЕТРИИ. §1. Прямая на плоскости. Различные виды уравнений прямой на плоскости. Пусть имеется прямоугольная система координат.
Литература Апатенок Р.Ф., Маркина А.М., Попова Н.В., Хейнман В.Б. Элементы линейной алгебра и аналитической геометрии Ильин В.А., Позняк Э.Г. Линейная.
Линейной комбинацией векторов называется вектор где - любые действительные числа.
Параллельное проектирование Таким образом, каждой точке A пространства сопоставляется ее проекция A' на плоскость π. Это соответствие называется параллельным.
Помехоустойчивое кодирование Основные идеи. Литература Алгебраическая теория кодирования Автор: Берлекэмп Э. Издательство: Мир Год: 1971 Теория кодов,
ГБОУ Гимназия 1505 «Московская городская педагогическая гимназия – лаборатория» автор: Редченко Дмитрий, 10 класс «Б» руководитель: Г.А.Пяткина 2013 г.
Содержание 1. Определение 2. Свойства модуля 3. Уравнение вида |f(x)| = a 4. Уравнение вида |f(x)| = g(x) 5. Уравнение вида |f(x)| = |g(x)| 6. Метод замены.
Транксрипт:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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