Учебное пособие: Дискретная мат-ка_УП
96
тора
if
основной процедуры Huffman. Рекурсивная часть алго-
ритма в точности следует доказательству теоремы предыдущего
подраздела. С помощью функции Up в исходном упорядоченном
массиве
Р
отбрасываются две последние (наименьшие) вероятно-
сти, и их сумма вставляется в массив
Р
, так чтобы массив (на
единицу меньшей длины) остался упорядоченным. Заметим, что
при этом место вставки сохраняется в локальной переменной j.
Так происходит до тех пор, пока не останется массив из двух
элементов, для которого оптимальный код известен. После этого
в обратном порядке строятся оптимальные коды для трех, четы-
рех и т. д. элементов. Заметим, что при этом массив вероятностей
Р
уже не нужен – нужна только последовательность номеров ко-
дов, которые должны быть изъяты из массива кодов и продубли-
рованы в конце с добавлением разряда. А эта последовательность
хранится в экземплярах локальной переменной j, соответствую-
щих рекурсивным вызовам процедуры Huffman.
Пример
Построение оптимального кода Хаффмена для n = 7. В ле-
вой части таблицы показано изменение массива
Р
, а в правой
части – массива
С
. Позиция, соответствующая текущему значе-
нию переменной j, выделена полужирным начертанием.
0.20 0.20
0.23 0.37 0.40 0.60 0 1 00
01
10 10
0.20 0.20 0.20 0.23 0.37 0.40 1 00 01 10 11 11
0.19 0.19 0.20 0.20 0.23.
01 10 11 000 000
0.12
0.18
0.19 0.20 11
000
001
010
0.11 0.12 0.18
001 010 011
0.09 0.11
011 0100
0.09
0011
Цена кодирования составляет
0.20 х 2 + 0.20 х 2 + 0.19 х 3 + 0.12 х 3 + 0.11 х 3 + 0.09 х 4 +
+0.09 х 4 = 2.78, что несколько лучше, чем в кодировании, полу-
ченном алгоритмом Фано.
97
8.3
Помехоустойчивое
кодирование
Надежность электронных устройств по мере их совершенст-
вования все время возрастает, но, тем не менее, в их работе воз-
можны ошибки, как систематические, так и случайные. Сигнал в
канале связи может быть искажен помехой, поверхность магнит-
ного носителя может быть повреждена, в разъеме может быть по-
терян контакт. Ошибки аппаратуры ведут к искажению или поте-
ре передаваемых или хранимых данных. При определенных ус-
ловиях, некоторые из которых рассматриваются в этом разделе,
можно применять методы кодирования, позволяющие правильно
декодировать исходное сообщение, несмотря на ошибки в дан-
ных кода. В качестве исследуемой модели достаточно рассмот-
реть канал связи с помехами, потому что к этому случаю легко
сводятся остальные. Например, запись на диск можно рассматри-
вать как передачу данных в канал, а чтение с диска – как прием
данных из канала.
Кодирование с исправлением ошибок
Пусть имеется канал связи
С
, содержащий источник помех:
*
'
*,
'
B
S
A
S
S
S
C
∈
∈
⎯→
⎯
,
где
S
– множество переданных, а S’ – соответствующее множест-
во принятых по каналу сообщений. Кодирование
F,
обладающее
таким свойством, что
( )
(
)
(
)
s
s
F
C
F
S
s
S
K
K
S
F
C
F
=
∈
∀
⎯
⎯ →
⎯
⎯→
⎯
⎯→
⎯
−
−
1
,
,
'
1
,
называется
помехоустойчивым,
или
самокорректирующимся,
или кодированием
с исправлением ошибок.
Без ограничения общности можно считать, что
А = В
=
={0,1}, и что содержательное кодирование выполняется на уст-
ройстве, свободном от помех.
Классификация ошибок
Ошибки в канале могут быть следующих типов:
●
0
→
1, 1
→
0 – ошибка типа замещения разряда;
●
0
→
Λ
, 1
→
Λ
– ошибка типа выпадения разряда;
98
●
Λ
→
1,
Λ
→
0 – ошибка типа вставки разряда.
Канал характеризуется верхними оценками количества
ошибок каждого типа, которые возможны при передаче через ка-
нал сообщения определенной длины. Общая характеристика
ошибок канала (то есть их количество и типы) обозначается
δ.
Пример
Допустим, что имеется канал с характеристикой
δ
= <1,0,0>,
то есть в канале возможна одна ошибка типа замещения разряда
при передаче сообщения длины
n
. Рассмотрим следующее коди-
рование:
F
(
a
):
= ааа
(то есть каждый разряд в сообщении утраи-
вается) и декодирование
F
–1
(
abc
)
:
= a + b + c >
1
(то есть разряд
восстанавливается методом «голосования»). Это кодирование
кажется помехоустойчивым для данного канала, однако на самом
деле это не так. Дело в том, что при передаче сообщения длины
3
n
возможно не более 3 ошибок типа замещения разряда, но мес-
та этих ошибок совершенно не обязательно распределены равно-
мерно по всему сообщению. Ошибки замещения могут произойти
в соседних разрядах, и метод голосования восстановит разряд не-
верно.
Возможность исправления всех ошибок
Пусть
δ
s
E
–
множество слов, которые могут быть получены
из слова
s
в результате всех возможных комбинаций допустимых
в канале ошибок
δ
,
то есть
s
∈
S
⊂
A*,
δ
s
E
⊂ B
*. Если s'
∈
δ
s
E ,
то
та конкретная последовательность ошибок, которая позволяет
получить из слова
s
слово
s
', обозначается
E
δ
<s,s'>.
Если тип
возможных ошибок в канале подразумевается, то индекс
δ
не
указывается.
ТЕОРЕМА. Чтобы существовало помехоустойчивое коди-
рование с исправлением всех ошибок, необходимо и достаточно,
чтобы
∀
s
l
,
s
2
∈
S
E
S1
∩
E
S2
=
∅, то есть необходимо и доста-
точно, чтобы существовало разбиение множества В* на мно-
жества B
s
(
∪В
s
= В*,
∩
B
s
=
∅
)
, такое что
∀
s
∈ S Е
s
⊂
В
s
.
99
Пример
Рассмотрим канал, в котором в любом передаваемом разря-
де происходит ошибка типа замещения с вероятностью
р
(0 <
р <
1/2), причем замещения различных разрядов статистически неза-
висимы. Такой канал называется
двоичным симметричным.
В
этом случае любое слово s
∈
δ
2
E
может быть преобразовано в
любое другое слово
s
'
∈
δ
2
E
замещениями разрядов. Таким обра-
зом,
∀s
E
s
=
δ
2
E ,
и исправить все ошибки в двоичном симметрич-
ном канале невозможно.
Кодовое расстояние
Неотрицательная функция
d
(
x, у
):
М
×
М
→
R
+
называется
расстоянием
(или
метрикой)
на множестве
М,
если выполнены
следующие условия (аксиомы метрики):
1.
d
(
x, y
)
= 0
⇔
х = у;
2.
d
(
x, y
)
= d
(
y, x
);
3.
d
(
x, у
)
≤
d
(
x, z
)
+ d
(
y, z
)
.
Пусть
(
)
{
}
⎪⎩
⎪
⎨
⎧
∉
∞
+
∈
=
.
'
'
,
'
'
,
'
'
,
'
min
:
'
'
,
'
'
'
''
,'
δ
β
δ
β
δ
β
β
δ
β
β
β
β
β
β
δ
E
E
E
d
E
Эта
функция
называется
расстоянием Хэмминга.
В
данном
случае
рассматриваем
симметричные
ошибки
,
то
есть
,
если
в
канале
допустима
ошибка
0
→ 1,
то
допустима
и
ошибка
1
→ 0.
Введенная
функция
dg
является
расстоянием
.
Действитель
-
но
:
1. d
δ
(
β
’,
β
’’) = 0
⇔
β
’=
β
’’,
поскольку
ошибки
симметричны
,
и
из
последовательности
Е<
β
’,
β
’’>
можно
получить
последова
-
тельность
Е<
β
’’,
β
’>,
применяя
обратные
ошибки
в
обратном
по
-
рядке
.
2. d
δ
(
β
’,
β
’’) = d
δ
(
β
’’,
β
’)
по
той
же
причине
.
3. d
δ
(
β
’,
β
’’)
≤
d
δ
(
β
’,
β
’’’) + d
δ
(
β
’’,
β
’’),
поскольку
Е<
β
’,
β
’’> U
Е<
β
’’’,
β
’’>
является
некоторой
последовательностью
,
преобра
-
.
100
зующей
β
’
в
β
’’, a d
δ
(
β
’,
β
’’)
является
кратчайшей
из
таких
после
-
довательностей
.
Пусть
n
i
i
i
a
1
=
→
=
β
σ
–
схема
некоторого
алфавитного
ко
-
дирования
, a d –
некоторая
метрика
на
B*.
Тогда
минимальное
расстояние
между
элементарными
кодами
(
)
j
i
d
n
j
i
d
β
β
σ
,
1
min
:
)
(
≤
≤
≤
=
называется
кодовым расстоянием
схемы
σ.
ТЕОРЕМА.
Алфавитное
кодирование
со
схемой
n
i
i
i
a
1
=
→
=
β
σ
и с кодовым расстоянием
(
)
''
,
'
''
,
'
min
:
)
(
β
β
β
β
σ
δ
δ
d
V
d
∈
=
является кодированием с исправлением р ошибок типа
δ
тогда и
только тогда, когда d
δ
(
σ
) > 2р.
Пример
Расстояние
Хэмминга
в
(
)
∑
=
≠
=
n
i
i
i
n
d
E
1
2
''
'
:
)
''
,
'
(
:
β
β
β
β
.
Код Хэмминга для исправления одного замещения
Рассмотрим
построение
кода Хэмминга,
который
позволяет
исправлять
одиночные
ошибки
типа
замещения
.
Очевидно
,
что
для
исправления
ошибки
вместе
с
основным
сообщением
нужно
передавать
какую
-
то
дополнительную
ин
-
формацию
.
Пусть
сообщение
а = a
1
… а
т
кодируется
словом
β
= b
1
... b
n
,
n > т.
Обозначим
k: = п – т.
Пусть
канал
допускает
не
более
од
-
ной
ошибки
типа
замещения
в
слове
длины
п.
Рассматриваемый
случай
простейший
,
но
одновременно
практически
очень
важный
.
Таким
свойством
,
как
правило
,
обла
-
дают
внутренние
шины
передачи
данных
в
современных
компь
-
ютерах
.