Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
имеющая следующее простое описание в виде алгоритма декодирования: слово
у на выходе декодируется в кодовое слово х., если IQ(y/jc.) < d. Если
существует несколько кодовых слов,
удовлетворяющих этому условию, то происходит ошибка декодирования. Удобно
исключить параметр d из этого алгоритма, применяя каноническое
декодирование: слово у декодируется в кодовое слово х., для которого
10(у/х.) минимально. Поскольку
уу" = /"-/<; + уу*.),
то каноническое декодирование равносильно декодированию по минимуму
IQ(x./y).
Разницу между решающей схемой теоремы 1.2 и канонической решающей схемой
показывает рис. 1:
Теорема 1.4. Существует код, для которого мощность и ошибка канонического
декодирования связаны неравенством
N > 2е е. Х
26
Доказательство. Рассмотрим .ансамбль {D^,. ?>2, ... ..., DM} всех кодов
мощности N. Ясно, что этот ансамбль состоит из
(\U I М = п { N
элементов. Обозначим через ё ошибку, осредненную по всему
ср
ансамблю. Таким образом, если е1-средняя ошибка канонической решающей
схемы для /-го кода, то
м
= - У
м Zj е-
е - " ср М
/=1
Каждое допустимое слово х (?> у, х G Un, yGV^x), назовем допустимым
ребром (рис. 2):
Рис. 2
I (х (r) у)
Ясно, что всего существует = 11/М • 1 V^,I =2°
таких ребер. Пусть {Bty, i = 1, ..., N,-каноническая решающая
схема для /-го кода ансамбля. Допустимое ребро (х, у) назовем
регулярным для кода D., если х = х. G D., у ? BJ.. Из
определения И следует, что
1 \в!.\ л м N .
1 - ^ = ЬУ TUV. 1-" = 7717П7Т У У
" IV.r ср MN\V.\ *-> *-> I
d d j=i ,=i
Величина
N
к. = У \В{\
1 А '
равна числу регулярных ребер для /-го кода, а
м
2! */ = *
/=1
совпадает с общим числом ребер, регулярных для кодов ансамбля. Если к.
трудно подсчитать-эта величина различна для разных
кодов, то к уже можно легко вычислить.
27
Действительно, пусть т-число кодов ансамбля, для которых оказывается
регулярным фиксированное допустимое ребро (дс, у). Ребро (jc, у)
регулярно для некоторого кода, если шар Vd,(y) не
содержит никакой кодовой точки, кроме х (по определению канонической
решающей схемы). Поэтому
т
IUJ - \\vd,\
пи I ( \
1
Ясно, что
Имеем
1-е -
ср
k = IU \W.\m. п d
IU
I и \W.\m =
MNIV.I п d N М
Wn^Wn[~ Wd'[~ 1)-('?V- Wd,\-N+2)N\
N\Un\(\Un\- \) ...({Un\-N+i)(N - 1)!
1 -
I V.,l - 1\
a
it/1 -1
1 -
IF.,I - 1 d
IU I - 2
I V., I - 1 d
\Un\ -(N- 1)
1 -
I vd,\ - 1
\U I - (N - 1)
Таким образом,
1 - (N - 1)
IF.,I - 1
a
IUn\ -(N-iy
ecp ~ !Un\ -(N- 1)'
и найдется код из ансамбля, для которого
1 Vd'1 ~ 1 е < (N- 1) ш ! _ (N_
что равносильно неравенству N > 1 + е
I U I
п
IV.,I -(1 -е)
I U I It/'
^ - п - п
> е ~гт;-г = е
\vd,\
'vd'
В доказательстве использовано неравенство
(1 - *)" > 1 - пх.
Приведем для полноты вывод этого неравенства.
Лемм а. Оценка (1 - х)п > 1 - п хсправедлива при четном целом
положительном п для всех вещественных х, а при нечетном п-для всех х < 2.
1
28
Доказательство. Рассмотрим функцию Дх) = (1 - х)" - (1 - их). Вычислим
производные:
f(x) = п[ 1 - (1 - X)"-1], /"(X) = п(п - 1)(1 - х)"-2.
Первая производная обращается в 0 в единственной точке х = 0, если п'
четно. При этом /"(0) > 0, ДО) = 0. Таким образом, в точке х = 0
достигается миниМук Дх) и Дх) > 0 для всех х.
Если же п нечетно, то появляется еще одна стационарная точка х = 2. При
этом /''(2) < 0, Д2) = 2(п - 1) > 0. Следовательно, этой точке
соответствует максимум и отрицательные значения Дх) может принимать лишь
при х > 2.
При доказательстве теоремы 1.4 мы всегда можем предполагать, что N - 1
четно, так как все оценки рассматриваются с точностью до округления.
1.13. Асимптотическое поведение информации. Энтропия
При больших длинах п вычисление 0-информации слова становится громоздким,
поэтому интерес представляют приближенные асимптотические выражения.
Приближения основаны на известной формуле Стирлинга для факториалов.
Лемма (формула Стирлинга)
Для произвольного слова х длины п с композицией (т{, ..., тк) определим
энтропию слова Н(х) посредством формулы
считая, что 0 • log 0 = 0.
Применяя формулу Стирлинга к выражению для /0(х),
получаем
Пре дложение 1.10. Для любого слова х длины п в алфавите из q букв
справедливо
п\ = V2лп ппе ", V2лп ппе "exp ^п+ 1 < < ^^ЛП п"ехр Yin'
т
т
29
Всюду в дальнейшем для вычисления 7q(jc) мы будем считать,
что
/0(х) = пН(х), даже при небольших длинах п. Поскольку Н(х) = lira
^/<,(*)>
п -* 00 п
энтропия обладает всеми доказанными ранее свойствами 0-информации,
которые, в свою очередь, являются следствиями элементарной теории групп.
Асимптотическое выражение для условной информации получается следующим
образом. С каждой парой слов х и у свяжем, как и ранее, матрицу (т")
(число переходов г-й буквы слова х
в у'-ю букву слова у):
а Ь Сумма в строке
а тп т,2 т1 к т1
b т21 т22 т2 к т2
тП тг2 тгк тг
Сумма в столбце п1 п2 пк п
Здесь (mj, ..., т^)-композиция слова х, (п^ п^)-композиция
слова у и
2 mt = 2 ni = п-
i j
Пусть X.-i-я строка матрицы. Тоща
