ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.02.2021
Просмотров: 217
Скачиваний: 1
Защита
информации
от
случайных
помех
.
Помехоустойчивое
кодирование
.
Говоря
об
оптимальном
(
в
смысле
максимального
сжатия
)
кодировании
текстов
,
мы
имели
в
виду
достижение
условия
l
=
Н
.
Если
же
это
условие
не
было
достигнуто
,
то
говорили
,
что
имеет
место
неоптимальное
,
т
.
е
.
избыточное
кодирование
.
Количественно
избыточность
можно
оценить
,
например
,
разностью
S
=
l
-
Н
или
,
в
процентах
, (
S
/
l
) *100%.
Достижение
условия
l
=
Н
обеспечивает
максимально
возможное
сжатие
исходных
текстов
(
избыточность
нулевая
).
При
этом
закодированный
текст
оказывается
предельно
сжатым
и
поэтому
абсолютно
беззащитным
к
случайным
ошибкам
.
Если
на
уровне
хоть
одного
двоичного
символа
оптимально
закодированного
текста
произошла
ошибка
,
то
мы
оказываемся
теоретически
лишенными
возможости
как
-
то
обнаружить
ее
,
а
тем
более
исправить
.
Интуитивно
ясно
,
что
наличие
некоторой
избыточности
создало
бы
принципиальную
возможность
обнаруживать
(
обнаруживающие
коды
),
а
в
некоторых
случаях
и
исправлять
(
исправляющие
коды
)
ошибки
.
Сказанное
,
однако
,
не
означает
,
что
сам
факт
наличия
некоторой
избыточности
уже
является
достаточным
для
обнаружения
или
исправления
ошибок
.
Наличие
избыточности
создает
лишь
теоретическую
,
принципиальную
возможность
обнаружения
или
исправления
ошибок
.
Для
того
же
,
чтобы
она
"
работала
на
нас
",
всецело
была
направлена
на
обнаружение
и
исправление
ошибок
предполагаемого
характера
,
эту
избыточность
следует
специально
"
конструировать
",
что
,
собственно
,
и
является
предметом
изучения
раздела
прикладной
математики
,
занимающегося
конструированием
кодов
,
обнаруживающих
и
исправляющих
ошибки
.
Там
же
устанавливаются
количественные
оценки
того
,
на
что
именно
мы
вправе
рассчитывать
(
обнаружение
одной
,
двух
и
т
.
д
.
ошибок
,
их
исправление
)
при
том
или
ином
уровне
избыточности
.
Рассмотрим
пример
.
Пусть
нам
предстоит
закодировать
текст
,
записанный
на
некотором
языке
,
таком
,
что
число
букв
в
алфавите
этого
языка
п
= 2
m
(
т
целое
число
),
а
появление
в
тексте
тех
или
иных
букв
алфавита
равновероятно
и
не
зависит
от
того
,
какие
буквы
им
предшествовали
.
Тогда
имеем
p(i) = p(j)
=
n
1
;
Н
=
Н
1
=
log
2
п
=
т
.
Условия
задачи
таковы
,
что
достичь
оптимального
кодирования
можно
самым
незатейливым
методом
кодирования
-
побуквенным
кодированием
с
постоянной
длиной
(
l
=
т
)
кодовых
наборов
.
При
этом
,
однако
,
мы
оказались
бы
лишенными
какой
-
либо
возможности
обнаруживать
,
а
тем
более
исправлять
ошибки
.
Чтобы
такая
возможность
появилась
,
необходимо
отказаться
от
оптимальности
кода
,
"
раскошелиться
"
на
несколько
дополнительных
двоичных
символов
на
букву
,
т
.
е
.
умышленно
ввести
некоторую
избыточность
,
которая
смогла
бы
помочь
нам
обнаружить
или
исправить
ошибки
.
Необходимое
число
дополнительно
вводимых
двоичных
символов
на
одну
букву
обозначим
через
х
,
и
тогда
длина
кодового
набора
станет
равной
l =
т
+
х
.
Примем
,
что
в
результате
помех
(
случайных
или
преднамеренных
)
лишь
один
или
вовсе
никакой
из
т
+
х
двоичных
символов
может
превращаться
из
единицы
в
нуль
или
,
наоборот
,
из
нуля
в
единицу
.
Примем
далее
,
что
1 +
т
+
х
событий
,
заключающиеся
в
том
,
что
ошибка
вообще
не
произойдет
,
произойдет
на
уровне
первого
,
второго
, ...,
(
т
+ x
)-
го
символа
кодового
набора
,
равновероятны
.
Энтропию
угадывания
того
,
какое
именно
из
этих
1 +
m
+
x
событий
будет
иметь
место
,
в
силу
равновероятности
этих
событий
она
получается
равной
Н
=
log
2
(1 +
т
+
х
)
бит
.
Таким
образом
,
для
обнаружения
самого
факта
наличия
одиночной
ошибки
и
установления
ее
позиции
необходимо
заполучить
информацию
в
количестве
не
менее
Н
=
log
2
(1+
т
+
х
)
бит
.
Источником
этой
информации
служат
лишь
дополнительно
Рис
. 4.1
.
Характер
зависимости
наименьшего
допустимого
значения
параметра
х
от
аргумента
т
(
сплошная
линия
).
Характер
зависимости
параметра
(
l
ср
/
δ
). 100%
от
аргумента
т
(
пунктирная
линия
)
введенные
x
двоичных
символов
,
так
как
остальные
т
символов
из
-
за
оптимальности
кодирования
до
предела
заняты
описанием
самого
текста
.
Выше
уже
говорилось
о
том
,
что
x
двоичных
символов
в
лучшем
случае
могут
содержать
информацию
в
количестве
x
бит
.
Таким
образом
,
при
конструировании
кода
,
обнаруживающего
и
исправляющего
одиночную
ошибку
,
следует
учесть
,
что
этого
можно
добиться
лишь
при
значениях
x
,
удовлетворяющих
неравенству
,
)
1
(
log
2
x
m
x
+
+
≥
(4.1)
или
m
x
x
≥
−
−
1
2
(4.1a)
На
рис
. 4.1
приведена
кривая
,
устанавливающая
зависимость
нижней
границы
допустимых
значений
x
от
т
.
Р
.
Хэмминг
разработал
конкретную
конструкцию
кода
[7],
которая
обеспечивает
весьма
элегантное
обнаружение
и
исправление
одиночных
ошибок
при
минимально
возможном
числе
дополнительно
вводимых
двоичных
символов
,
т
.
е
.
при
знаке
равенства
в
(4.1).
Проследим
за
построением
этого
кода
,
когда
т
=
4.
Из
рис
. 4.1
следует
,
что
при
этом
допустимое
значение
x
равно
трем
,
т
.
е
.
при
числе
основных
(
информационных
)
двоичных
символов
т
=
4,
число
дополнительно
введенных
,
т
.
е
.
контрольных
символов
должно
быть
не
менее
трех
.
Примем
,
что
нам
удалось
"
обойтись
"
именно
тремя
дополнительными
символами
,
т
.
е
.
удалось
сконструировать
такой
код
,
при
котором
каждый
из
дополнительно
введенных
трех
символов
дает
нам
максимально
возможное
количество
информации
,
т
.
е
.
по
одному
биту
.
Тогда
в
расширенном
кодовом
наборе
окажутся
семь
двоичных
символов
:
β
β
β
β
4
3
2
1
β
β
β
7
6
5
(
информационные
символы
) (
контрольные
символы
)
Поскольку
символы
β
β
4
1
÷
заняты
кодированием
собственно
текста
,
то
управлять
их
значениями
нам
не
дано
.
Что
же
касается
символов
β
β
7
5
÷
,
то
они
предназначены
именно
для
обнаружения
и
исправления
ошибок
и
поэтому
их
значения
мы
можем
увязать
со
значениями
информационных
символов
произвольными
тремя
функциями
от
аргументов
β
β
4
1
÷
),
4
1
5
5
(
β
β
β
β
÷
=
(4.2)
),
4
1
6
6
(
β
β
β
β
÷
=
(4.3)
)
4
1
7
7
(
β
β
β
β
÷
=
(4.4)
такими
,
чтобы
в
последующем
с
помощью
трех
других
функций
от
аргументов
β
β
7
1
÷
),
7
1
0
0
(
β
β
÷
=
e
e
(4.5)
),
7
1
1
1
(
β
β
÷
=
e
e
(4.6)
)
7
1
2
2
(
β
β
÷
=
e
e
(4.7)
определить
значения
е
0
,
е
1
,
е
2
,
содержащие
информацию
о
том
,
произошла
ли
ошибка
вообще
и
если
да
,
то
на
уровне
какого
именно
из
семи
символов
.
Очевидно
,
имеется
множество
различных
вариантов
при
выборе
функций
(4.2) -:-
(4.7).
Р
.
Хэмминг
поставил
перед
собой
задачу
выбора
именно
такой
совокупности
функций
(4.2) -:- (4.7),
чтобы
набор
значений
е
2
е
1
е
0
оказался
двоичной
записью
позиции
,
где
произошла
ошибка
.
В
случае
же
,
когда
ошибка
не
имела
места
,
набор
значений
е
2
е
1
е
0
должен
указать
на
"
нулевую
"
позицию
,
т
.
е
.
на
несуществующий
символ
β
0
.
Из
двоичной
записи
этих
позиций
0 0 0 (0)
1 0 0 (4)
0 0 1 (1)
1 0 1 (5)
0 1 0 (2)
1 1 0 (6)
0 1 1 (3)
1 1 1 (7)
легко
заметить
,
что
значение
е
0
"
несет
ответственность
"
за
позиции
β
β
β
β
7
5
3
1
,
,
,
и
поэтому
в
качестве
функции
(4.5)
берется
зависимость
2
mod
7
5
3
1
0
β
β
β
β
+
+
+
=
e
(4.8
а
)
Аналогично
,
обращая
внимание
на
то
,
что
значения
е
1
и
е
2
отвечают
за
позиции
соответственно
β
β
β
β
7
6
3
2
,
,
,
и
β
β
β
β
7
6
5
4
,
,
,
,
получим
2
mod
7
6
3
2
1
β
β
β
β
+
+
+
=
e
(4.9
а
)
2
mod
7
6
5
4
2
β
β
β
β
+
+
+
=
e
(4.10
а
)
Обратим
внимание
,
что
систему
(4.8
а
) -:- (4.10
а
)
можно
рассматривать
как
развернутую
запись
матричного
уравнения
β
β
β
β
β
β
β
7
6
5
4
3
2
1
2
1
0
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1
1
0
1
0
1
⋅
=
e
e
e
или
V
e
= A * V
a
где
V
е
-
вектор
ошибки
,
указывающий
на
се
месторасположение
;
А
-
основная
матрица
,
столбцы
которой
суть
двоичные
записи
чисел
от
одного
до
семи
.
Операция
сложения
во
всех
трех
уравнениях
(4.8
а
) -:- (4.10
а
)
осуществляется
по
модулю
два
.
Подставляя
в
систему
уравнений
(4.8
а
) -:- (4.10
а
)
е
0
=
е
1
=
е
2
= 0,
получим
систему
из
трех
уравнений
2
mod
0
7
5
3
1
=
+
+
+
β
β
β
β
(4.8
б
)
2
mod
0
7
6
3
2
=
+
+
+
β
β
β
β
(4.9
б
)
2
mod
0
7
6
5
4
=
+
+
+
β
β
β
β
(4.10
б
)
Приняв
в
качестве
неизвестных
величины
β
β
β
7
6
5
,
,
,
получим
систему
из
трех
уравнений
с
тремя
неизвестными
:
2
mod
3
1
7
5
β
β
β
β
+
=
+
(4.8
в
)
2
mod
3
2
7
6
β
β
β
β
+
=
+
(4.9
в
)
2
mod
4
7
6
5
β
β
β
β
=
+
+
(4.10
в
)
Эта
система
эквивалентна
одному
матричному
уравнению
β
β
β
β
β
β
β
4
3
2
1
7
6
5
1
0
0
0
0
0
1
1
0
1
0
1
1
1
1
1
1
0
1
0
1
⋅
=
⋅
(4.11)
или
C*V
с
= I*V
i
,
(4.11a)
где
V
с
и
V
i
,
векторы
-
столбцы
,
координаты
которых
представлены
соответственно
контрольными
и
информационными
разрядами
;
С
и
I
-
так
называемые
контрольная
и
информационная
матрицы
.
Столбцы
этих
матриц
суть
двоичные
записи
номеров
соответственно
контрольных
и
информационных
разрядов
.
Решение
системы
(4.8
в
) -:- (4.10
в
),
или
,
что
то
же
самое
,
матричного
уравнения
(4.11)
относительно
β
β
β
7
6
5
,
,
приводит
к
конкретным
выражениям
для
функций
(4.2.2) -:- (4.2.4):
2
mod
4
3
2
5
β
β
β
β
+
+
=
(4.2
в
)
2
mod
4
3
1
6
β
β
β
β
+
+
=
(4.3
в
)
2
mod
4
2
1
7
β
β
β
β
+
+
=
(4.4
в
)
Заметим
,
что
сам
Р
.
Хэмминг
в
качестве
контрольного
берет
не
набор
символов
β
β
β
x
m
m
m
+
+
+
,...,
,
2
1
,
а
набор
символов
,
индексы
которых
представляют
целые
степени
двойки
.
В
случае
,
когда
число
контрольных
символов
равно
трем
,
эти
индексы
равны
2
0
= 1, 2
1
= 2
и
2
2
= 4,
т
.
е
.
речь
идет
о
наборе
символов
β
β
β
4
2
1
,
,
относительно
которых
решение
системы
(4.8
б
) -:- (4.10
б
)
чрезвычайно
упрощается
:
2
mod
7
5
3
1
β
β
β
β
+
+
=
2
mod
7
6
3
2
β
β
β
β
+
+
=
2
mod
7
6
5
4
β
β
β
β
+
+
=
Это
и
естественно
,
поскольку
в
данном
случае
вместо
(4.11)
мы
имеем
дело
с
матричным
уравнением
β
β
β
β
β
β
β
7
6
5
3
4
2
1
1
1
1
1
1
0
1
0
1
0
1
1
1
0
0
0
1
0
0
0
1
⋅
=
⋅
где
контрольная
матрица
С
всегда
равна
единичной
матрице
.
Отметив
,
что
при
указанной
рекомендации
Р
.
Хэмминга
контрольная
матрица
всегда
(
независимо
от
т
и
х
)
оказывается
равной
единице
,
подробное
обсуждение
этой
рекомендации
оставим
на
потом
,
продолжая
рассматривать
в
качестве
контрольных
β
β
β
7
6
5
,
,
,
а
в
качестве
информационных
-
β
β
β
β
4
3
2
1
,
,
,
.
Рассмотрим
,
к
примеру
,
набор
информационных
символов
1011
4
3
2
1
=
β
β
β
β
.
С
помощью
зависимостей
(4.5
а
) -:- (4.7
а
)
определим
набор
контрольных
(
дополнительно
введенных
,
избыточных
)
символов
010
7
6
5
=
β
β
β
.
Пусть
ошибка
произошла
на
уровне
символа
β
5
,
т
.
е
.
вместо
истинного
расширенного
кодового
набора
1 0 1 1 (0) 1 0
получен
код
1 0 1 1 (1) 1 0.
Тогда
с
помощью
зависимостей
(4.8
а
) -:- (4.10
а
)
найдем
e
0
= 1 + 1 + 1 + 0 = 1
mod 2