ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.02.2021
Просмотров: 218
Скачиваний: 1
е
1
= 0 + 1 + 1 + 0 = 0
mod 2
е
2
=
1 + 1 + 1 + 0 = 1
mod 2
Набор
значений
е
2
е
1
е
0
= 1 0 1
является
двоичной
записью
числа
"
пять
",
т
.
е
.
указывает
именно
на
пятую
позицию
(
на
символ
β
5
),
где
,
собственно
,
и
произошла
ошибка
.
Приведенная
схема
Р
.
Хэмминга
по
конструированию
кода
,
обнару
-
живающего
и
исправляющего
одиночную
ошибку
,
универсальна
,
и
аналогичный
код
может
быть
построен
для
произвольной
пары
значений
т
и
х
,
удовлетворяющих
уравнению
m
x
x
=
−
−
1
2
(4.16)
Заметим
также
,
что
вовсе
не
обязательно
,
чтобы
набор
из
т
информационных
символов
представлял
собой
код
какой
-
то
определенной
буквы
,
как
это
имело
место
в
только
что
рассмотренном
примере
.
На
практике
сначала
можно
осуществить
оптимальное
(
или
близкое
к
оптимальному
)
кодирование
текста
.
Затем
уже
закодированный
текст
можно
делить
на
блоки
по
т
двоичных
символов
в
каждом
,
причем
из
возможных
значений
1
2
−
−
=
x
m
x
(
х
=
3, 4, ...)
его
конкретное
значение
следует
выбирать
исходя
из
эксплуатационной
необходимости
.
При
прочих
равных
условиях
значение
т
должно
быть
тем
меньшим
,
чем
больше
значимость
информации
и
чем
больше
уровень
помех
.
После
выбора
конкретного
значения
т
каждый
блок
из
т
информационных
символов
следует
наращивать
х
=
х
(
т
)
контрольными
символами
,
пред
-
назначенными
для
обнаружения
и
исправления
одиночных
ошибок
в
рамках
данного
блока
.
А
теперь
вернемся
к
рассмотрению
вопроса
о
том
,
почему
Р
.
Хэмминг
в
качестве
контрольных
берет
именно
символы
,
индексы
которых
равны
целым
степеням
двойки
,
т
.
е
. 1, 2, 4, 8, 16,....
Во
-
первых
,
как
уже
об
этом
говорилось
выше
,
при
таком
выборе
контрольная
матрица
всегда
оказывается
равной
единице
,
т
.
е
.
фактически
снимается
вопрос
решения
системы
(4.8
б
) -:- (4.10
б
)
относительно
контрольных
символов
,
так
как
ее
"
решение
"
сводится
к
простому
переписыванию
соответствующих
уравнений
.
Но
это
не
главное
,
так
как
систему
(4.8
б
) -:- (4.10
б
)
приходится
решать
только
один
раз
и
далее
при
каждом
акте
кодирования
мы
пользуемся
лишь
системой
(4.5
а
) -:- (4.7
а
) -
решением
системы
(4.8
б
) -:- (4.10
б
)
относительно
контрольных
символов
.
При
реализации
процедур
кодирования
и
декодирования
на
ЭВМ
сам
факт
,
что
контрольные
символы
разобщены
(
не
следуют
подряд
друг
за
другом
),
создает
определенные
неудобства
при
каждом
акте
кодирования
и
декодирования
.
Естественно
поэтому
желание
выбрать
контрольные
символы
таковыми
,
чтобы
они
следовали
подряд
друг
за
другом
,
пусть
даже
ценою
того
,
чтобы
один
раз
решить
систему
(4.8
б
) -:- (4.10
б
).
Именно
так
поступали
мы
,
когда
вопреки
рекомендации
Р
.
Хэмминга
взять
в
качестве
контрольных
символы
β
β
β
4
2
1
,
,
взяли
в
качестве
таковых
символы
β
β
β
7
6
5
,
,
.
Хотя
это
и
вынудило
нас
решить
систему
(4.8
в
) -:- (4.10
в
)
относительно
переменных
β
β
β
7
6
5
,
,
,
но
зато
при
каждом
акте
кодирования
и
декодирования
мы
смогли
оперировать
"
пачками
"
контрольных
символов
,
а
не
"
выковыривать
"
их
среди
информационных
символов
.
Возникает
вопрос
:
а
всегда
ли
,
при
любом
числе
информационных
символов
мы
смогли
бы
поступать
аналогичным
образом
?
Нет
,
не
смогли
бы
,
если
по
-
прежнему
хотим
,
чтобы
двоичный
набор
символов
е
x-1
,
е
x-2
,…
е
0
указывал
на
адрес
ошибки
.
Потому
что
уже
когда
число
контрольных
символов
больше
трех
,
мы
не
имеем
права
взять
в
качестве
контрольных
последние
х
символов
.
Легко
убедиться
,
что
при
этом
контрольная
матрица
непременно
оказалась
бы
вырожденной
,
т
.
е
.
значение
ее
детерминанта
оказалась
бы
равным
нулю
.
Более
того
,
даже
в
рассмотренном
нами
случае
,
когда
число
контрольных
символов
равно
трем
,
мы
не
смогли
бы
в
качестве
контрольных
взять
,
например
,
первые
три
символа
.
Во
всех
этих
случаях
определители
контрольных
матриц
(
вспомним
,
что
столбцы
этой
матрицы
суть
двоичные
записи
номеров
выбранных
нами
контрольных
символов
)
оказываются
равными
нулю
.
Пусть
,
например
,
мы
выбрали
в
качестве
контрольных
не
пачку
символов
β
β
β
7
6
5
,
,
,
а
символы
β
β
β
3
2
1
,
,
.
Тогда
нам
пришлось
бы
иметь
дело
с
квадратной
матрицей
третьего
порядка
,
столбцы
которой
являются
двоичными
формами
записи
чисел
1, 2
и
3:
0
0
0
1
1
0
1
0
1
=
C
Равенство
нулю
детерминанта
этой
матрицы
свидетельствует
о
том
,
что
систему
(4.86) -:- (4.106)
нельзя
решить
относительно
переменных
β
β
β
3
2
1
,
,
.
Таким
образом
,
при
выборе
среди
т
+
х
символов
х
контрольных
следует
заботиться
о
том
,
чтобы
определитель
контрольной
матрицы
порядка
х
,
столбцы
которой
представляют
собой
двоичные
записи
номеров
выбранных
символов
,
не
оказался
равным
нулю
.
Именно
чтобы
избавиться
от
этих
забот
,
Р
.
Хэмминг
рекомендует
в
качестве
контрольных
взять
символы
с
индексами
1, 2, 4,
8
и
т
.
д
.
Легко
обнаружить
,
что
при
таком
выборе
контрольных
символов
мы
всегда
(
независимо
от
их
числа
)
будем
иметь
дело
с
единичной
матрицей
.
Кроме
зависимости
(4.1
а
),
на
рис
. 1
приведена
также
зависимость
относительной
избыточности
(
l
ср
/
δ
). 100%
от
т
.
Легко
заметить
,
что
с
увеличением
т
требуемый
процент
избыточности
для
обнаружения
и
исправления
одиночной
ошибки
резко
уменьшается
.
Столь
неестественный
результат
является
следствием
искусственного
,
далекого
от
реальности
допущения
,
что
в
рамках
каждого
кодового
набора
независимо
от
его
длины
т
+
х
может
произойти
не
более
одной
ошибки
.
Если
же
допустить
возможность
двух
и
более
ошибок
,
то
задача
их
обнаружения
,
и
тем
более
исправления
усложняется
.
Построить
для
этих
случаев
коды
столь
же
элегантные
,
как
код
Р
.
Хэмминга
для
одиночной
ошибки
,
пока
не
удалось
.
Геометрический
подход
Выше
был
представлен
алгебраический
подход
к
кодам
с
исправлением
ошибок
.
Другой
,
эквивалентный
подход
использует
n
-
мерную
геометрию
.
В
этой
модели
последовательность
из
нулей
и
единиц
рассматривается
как
точка
n
-
мерного
пространства
.
Каждый
символ
задает
значение
соответствующей
координаты
в
n
-
мерном
пространстве
, (
предполагается
,
что
длина
закодированного
сообщения
в
точности
равна
п
.
битам
).
Таким
образом
,
имеется
куб
в
n
-
мерном
пространстве
,
каждая
вершина
которого
представлена
последовательностью
из
n
нулей
и
единиц
.
Пространство
состоит
только
из
2n
вершин
и
,
кроме
них
,
в
пространстве
всех
возможных
сообщений
ничего
нет
.
Это
пространство
иногда
называют
векторным
.
Каждая
вершина
является
возможным
принятым
сообщением
;
однако
лишь
некоторые
выбранные
вершины
—
это
посылаемые
сообщения
.
Одиночная
ошибка
в
сообщении
передвигает
точку
,
соответствующую
сообщению
,
вдоль
ребра
воображаемого
куба
в
соседнюю
вершину
.
Если
потребовать
,
чтобы
любое
посылаемое
сообщение
находилось
на
расстоянии
,
по
крайней
мере
,
двух
ребер
от
любого
другого
возможного
сообщения
,
то
ясно
,
что
любая
одиночная
ошибка
сдвинет
сообщение
вдоль
ребра
и
принятое
сообщение
выйдет
из
множества
посылаемых
сообщений
.
Если
минимальное
расстояние
между
посылаемыми
сообщениями
равно
трем
ребрам
куба
,
то
любая
одиночная
ошибка
оставит
принятое
сообщение
ближе
к
посланному
,
чем
к
любому
другому
посылаемому
сообщению
,
так
что
код
будет
исправлять
одиночные
ошибки
.
Фактически
введено
расстояние
,
равное
минимальному
числу
ребер
куба
,
по
которым
нужно
пройти
,
чтобы
дойти
от
одной
точки
до
другой
.
Это
расстояние
равно
также
числу
бит
,
которыми
отличаются
последовательности
,
соответствующие
двум
вершинам
.
Таким
образом
,
расстояние
можно
рассматривать
как
логическую
сумму
двоичных
символов
двух
точек
.
Эта
величина
действительно
является
расстоянием
,
поскольку
она
обладает
следующими
тремя
свойствами
.
1.
Расстояние
от
любой
точки
до
самой
себя
равно
0
.
2.
Расстояние
от
точки
х
до
отличной
от
нее
точки
у
совпадает
с
расстоянием
от
точки
у
до
точки
х
и
является
положительным
числом
.
3.
Выполнено
неравенство
треугольника
,
т
.
е
.
сумма
длин
двух
сторон
треугольника
(
расстояние
от
а
до
с
плюс
расстояние
от
c
до
b)
не
меньше
длины
третьей
стороны
(
расстояние
от
а
до
b).
Это
расстояние
обычно
называется
расстоянием
Хэмминга
.
Оно
приспособлено
для
двоичного
белого
шума
.
Используя
это
расстояние
,
можно
определить
различные
объекты
в
пространстве
.
В
частности
,
поверхность
сферы
,
с
центром
в
некоторой
точке
представляет
собой
множество
точек
,
находящихся
на
заданном
расстоянии
от
центра
.
Поверхность
сферы
радиуса
1
с
центром
(
0, 0, ..., 0
) —
это
множество
всех
вершин
пространства
,
находящихся
на
расстоянии
1
,
т
.
е
.
множество
всех
вершин
,
имеющих
только
один
символ
1
в
координатной
записи
(
рис
. 4.1).
Число
таких
точек
равно
С
(n, 1).
Минимальное
расстояние
между
вершинами
множества
посылаемых
сообщений
можно
выразить
в
терминах
корректирующих
свойств
.
Для
однозначности
кода
минимальное
расстояние
должно
быть
,
по
меньшей
мере
,
равно
1
(
табл
.
4
.
1
).
Минимальное
расстояние
2
дает
обнаружение
одиночных
ошибок
.
Минимальное
расстояние
3
дает
исправление
одиночных
ошибок
;
каждая
одиночная
ошибка
оставляет
точку
,
расположенную
ближе
к
первоначальному
положению
,
чем
к
любому
другому
посылаемому
сообщению
.
Ясно
,
что
код
с
этим
минимальным
расстоянием
может
использоваться
также
для
обнаружения
двойных
ошибок
.
Минимальное
расстояние
4
дает
исправление
одиночных
ошибок
,
а
также
обнаружение
двойных
ошибок
.
Минимальное
расстояние
5
дает
исправление
двойных
ошибок
.
Обратно
,
для
того
чтобы
обнаруживать
или
исправлять
ошибки
соответствующей
кратности
,
код
должен
иметь
соответствующее
минимальное
расстояние
.
Таблица
4.1.
Смысл
минимального
расстояния
Минимальное
расстояние
Интерпретация
1
2
3
4
5
Однозначность
Обнаружение
одиночных
ошибок
Исправление
одиночных
ошибок
(
или
обнаружение
двойных
ошибок
)
Исправление
одиночных
ошибок
дополнительно
к
этому
,
обнаружение
двойных
ошибок
(
или
вместо
всего
этого
обнаружение
тройных
ошибок
)
Исправление
двойных
ошибок
.
Рис
. 4.1.
При
исправлении
одиночной
ошибки
(
минимальное
расстояние
3)
каждое
сообщение
можно
окружить
единичной
сферой
,
и
эти
сферы
не
перекрываются
.
Шар
радиуса
1
состоит
из
центра
и
n
точек
,
по
одной
для
каждой
измененной
координаты
;
таким
o6p
азом
,
объем
шара
равен
1+n
.
Объем
всего
n
-
мерного
пространства
,
т
.
е
.
число
всех
точек
в
нем
,
равен
,
очевидно
,
2n
.
Поскольку
шары
не
пересекаются
,
максимальное
число
посылаемых
сообщений
должно
удовлетворять
условию
сфер
число
е
минимально
ва
пространст
всего
объем
сферы
объем
≥
(0,1,1)
(1,1,1)
(1,1,0)
(1,0,1)
(0,1,0)
(1,0,0)
(0,0,0)
(0,0,1)
или
2
1
2
k
n
n
≥
+
(4.2)
Поскольку
n=m+k
,
то
)
1
(
2
2
+
⋅
≥
+
n
k
k
m
или
1
2
+
≥
n
m
.
Именно
это
неравенство
было
получено
при
использовании
алгебраического
подхода
.
Можно
доказать
,
что
двоичный
код
C
с
минимальным
кодовым
расстоянием
d
min
может
исправлять
все
комбинации
от
1
до
t
ошибок
и
может
обнаруживать
все
комбинации
от
t+1
до
t+s
ошибок
тогда
и
только
тогда
,
когда
s
t
d
+
⋅
≥
2
min
При
прочих
равных
условиях
,
чем
больше
избыточность
текста
,
тем
легче
осуществить
его
несанкционированное
декодирование
,
точнее
дешифровку
.
В
этом
смысле
оптимально
закодированные
тексты
характеризуются
большей
защищенностью
.
В
то
же
время
эти
тексты
абсолютно
беззащитны
к
случайным
и
/
или
умышленно
введенным
ошибкам
-
достаточно
хоть
одной
ошибки
на
уровне
какого
-
либо
двоичного
символа
оптимально
закодированного
текста
,
и
уже
не
только
"
противник
",
но
и
"
свой
"
адресат
лишится
возможности
декодировать
-
восстановить
исходный
текст
.
Чтобы
предоставить
адресату
хоть
какую
-
то
возможность
обнаружить
,
а
тем
более
исправить
имеющие
место
ошибки
,
приходится
отказаться
от
предельного
сжатия
текста
и
ввести
некоторую
избыточность
.
Но
эта
избыточность
должна
быть
специально
сконструирована
,
т
.
е
.
она
должна
быть
нацелена
на
обнаружение
,
а
если
это
возможно
,
то
и
исправление
ошибок
.