Основы теории информации и криптографии
Вид материала | Учебное пособие |
СодержаниеМатричное кодирование 9. Лекция: Групповые коды |
- «Основы криптографической защиты информации», 173.19kb.
- О спектральных свойствах дискретного преобразования фурье, 34.99kb.
- Задача надежной защиты информации от несанкционированного доступа является одной, 269.92kb.
- Методические указания по изучению теоретической части Чебоксары 2009, 330.7kb.
- Программа дисциплины теоретические основы информатики (дпп. Ф. 08) для специальности, 125.07kb.
- Рабочей программы учебной дисциплины (модуля) Основы математической обработки информации, 44.43kb.
- Темы курсовых работ по дисциплине «Криптографические методы защиты информации», 14.86kb.
- Примерная программа наименование дисциплины: «Теоретико-числовые методы в криптографии», 222.72kb.
- «Основы обработки графической информации с помощью пк. Графический редактор Paint», 95.66kb.
- Учебная программа по дисциплине криптографические методы защиты информации федосеев, 33.76kb.
Матричное кодирование
Ранее каждая схема кодирования описывалась таблицами, задающими кодовое слово длины




Гораздо меньшего объема памяти требует матричное кодирование. Пусть









Пример. Рассмотрим следующую


Тогда кодирование задается такими отображениями:








Рассмотренный пример показывает преимущества матричного кодирования: достаточно запомнить


Кодирование не должно приписывать одно и то же кодовое слово разным исходным сообщениям. Простой способ добиться этого состоит в том, чтобы


Матричные коды называют также линейными кодами. Для линейных





Упражнение 39 Вычислить минимальную оценку по Плоткину количества дополнительных разрядов


^ 9. Лекция: Групповые коды
Объясняется, какой блочный код называется групповым. Математическое обоснование выводов. Упражнения для самопроверки. Совершенные и квазисовершенные коды. Их свойства. Полиномиальные коды. Частный случай полиномиальных кодов – циклические коды. Очень хорошее и доходчивое объяснение материала характерно для данной лекции
Множество всех двоичных слов


Пусть






Предположим, что






т.е.



Блочный код называется групповым, если его кодовые слова образуют группу.
Если код является групповым, то наименьшее расстояние между двумя кодовыми словами равно наименьшему весу ненулевого слова.
Это следует из соотношения

В предыдущем примере наименьший вес ненулевого слова равен 3. Следовательно, этот код способен исправлять однократную ошибку или обнаруживать однократную и двойную.
При использовании группового кода незамеченными остаются те и только те ошибки, которые отвечают строкам ошибок, в точности равным кодовым словам.
Такие строки ошибок переводят одно кодовое слово в другое.
Следовательно, вероятность того, что ошибка останется необнаруженной, равна сумме вероятностей всех строк ошибок, равных кодовым словам.
В рассмотренном примере вероятность ошибки равна

Рассмотрим задачу оптимизации декодирования группового кода с двоичной матрицей кодирования


Схема декодирования состоит из группы
















Лидером каждого из таких построенных смежных классов называется слово минимального веса.
Каждый элемент





Множество классов смежности группы образуют фактор-группу, которая есть фактор-множество множества


Если в рассматриваемой таблице в первом столбце записать лидеры, то полученная таблица называется таблицей декодирования. Она имеет вид:

То, что строк будет





Декодирование слова



Для


Первая строка в ней - это строка кодовых слов, а первый столбец - это лидеры.
Чтобы декодировать слово

Например, если принято слово 110011 (2-я строка, 3-й столбец таблицы), то считается, что было передано слово 010011; аналогично, если принято слово 100101 (3-я строка, 4-й столбец таблицы), переданным считается слово 110101, и т.д.
Групповое кодирование со схемой декодирования посредством лидеров исправляет все ошибки, строки которых совпадают с лидерами. Следовательно, вероятность правильного декодирования переданного по двоичному симметричному каналу кода равна сумме вероятностей всех лидеров, включая нулевой.
В рассмотренной схеме вероятность правильной передачи слова будет

Кодовое слово любого столбца таблицы декодирования является ближайшим кодовым словом ко всем прочим словам данного столбца.
Пусть переданное слово









Доказано, при схеме декодирования лидерами по полученному слову берется ближайшее к нему кодовое.
Упражнение 40 Для кодирующих матриц

,

- Построить соответственно
-код и
-код.
- Найти основные характеристики полученных кодов: минимальное расстояние между словами кода; вероятность необнаружения ошибки; максимальную кратность ошибок, до которой включительно они все исправляются или обнаруживаются.
- Построить таблицы декодирования.
- Уточнить характеристики полученных кодов, при использовании их для исправления ошибок, т.е. найти вероятность правильной передачи и описать ошибки, исправляемые этими кодами.
- Во что будут декодированы слова: 10001, 01110, 10101, 1001, 0110, 1101?