Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
Такую пару слов будем называть сильно независимой. Ясно, что в этом
случае переходная матрица состоит из единиц и нулей.
1.12. Канал с шумом. Теоремы кодирования Шеннона
Когда говорят о канале с шумом, то имеют в виду пары слов х и у, х е Хп,
у е У". При этом X называют входным алфавитом, а У-алфавитом на выходе
канала.
Канал связи преобразует последовательности символов на входе в выходные
последовательности. Преобразование слова х в слово у управляется
переходной матрицей
а Ь с
а тп т12 т\
Ь т2\ т22 т2
А = с
п1 п2
каждый элемент которой указывает на число переходов i-й буквы слова х в
/-ю букву слова у.
22
Матрица А однозначно определяет композицию (т}, т^)
входного слова и композицию (п^ п^) выходного слова
Тем самым определена некоторая орбита Uп на входе (0-источник на входе) и
орбита U'n на выходе (0-источник на выходе). -Кроме того, определена
условная информация IQ(yQ/x0) = d,
которая характеризует уровень помех в канале, и взаимная информация С =
I0(xQ:y0), которую назовем пропускной способностью канала.
Пару х <8> у, х & Uп, у G U'n, назовем допустимой, если переходная
матрица для этих слов совпадает с матрицей А. В этом случае I0(y/x) = d.
Для фиксированного слова * все допустимые
слова у (назовем это множество шаром радиуса d) составляют условную
орбиту G^ = VJ\X)- Действительно, если слова х (r) у
и х <8> и допустимы, то эти слова имеют одну и ту же композицию, так' что
х <8> у = о(х <8> и). Но ах = х, поэтому о е Gx.
Таким образом, слово х воспринимается на выходе как некоторое слово шара
Описанная математическая модель (назовем ее алгебраическим каналом)
является идеализацией реальных каналов связи. В дальнейшем мы обобщим эту
модель, приближая ее к реальности, но основные идеи и методы
помехоустойчивого кодирования удобно анализировать на этой модели,
поскольку она допускает алгеб-раизацию с помощью групп подстановок.
Под кодом будем понимать любое подмножество D С Uп,
D = {jCj, ..., jc^}. Предполагается, что по каналу передаются лишь
кодовые слова. Величину N назовем мощностью кода.
Если шары Vrf(jcp и ^(*у) с центрами в кодовых словах
пересекаются, то возникает неоднозначность декодирования. Выберем для
каждого х. множество В. С У^(х.) так, чтобы все В.
не пересекались. Систему {В.}, i = 1, ..., N, назовем решающей
схемой для кода.
Каждое слово у G В. декодируется в кодовое слово х.. Ясно,
что величина е. = 1 - IВ.I /1I характеризует ошибку декодирования, если
было передано слово х.. Точнее говоря, когда .у 6 Vd - В., наступает
отказ от декодирования, который мы будем
трактовать как ошибку декодирования.
Величину е = Мах е. назовем максимальной ошибкой решающей схемы, а
величину
23
средней ошибкой решающей схемы.
Введем нормированную меру ц(х, у) на U х U'n следующим
образом:
ц(х) = ! j, для всех х G Un, п
ц{у/х) =
TjTT- если >> G Vd,
О, если у ? V .
Ясно, что для любого множества М Q
fi(M/х) = 2 М>'/*) = 1Л/ П Vrf(*)l/IVrfl.
уем
В частности, е. = 1 - ц(В./х.). Далее, если у G V^(x), то /0(>'/х) = (1.
Поскольку
У*) + 70(>'/х) = У>') + Ух/>')>
то
/"<*/,) = </' = /"-/' + rf.
т. е. * е
Другими словами, с каждым каналом связан двойственный канал, матрица
которого получается транспонированием матрицы А. Поэтому у G У^(х)
равносильно х G для двойствен-
ного канала. Поскольку ILMIV^I = It/41VI, имеем
I V I ,
л"Су) = 2 =
Наконец,
- It/ IIV .1 It/'l
xet/ п d п
Mvd(x)) = it/-)'
n
Теорема 1.2. Существует код мощности N и решающая схема с максимальной
ошибкой е, для которых справедливо неравенство
Доказательство. Выберем х{ G Uп в качестве первого кодового слова и
множество в качестве В{. Если для
некоторой точки х2 выполняется неравенство
iV/X0 П ЧХ2>' 5 elVd1'
ТО Х2 включим в код и положим
в2 = Чхг> - W П W*
На N-м шаге включаем точку в код, если
при этом полагаем
вн " W - W л (*"'зд
Ясно, что при таком расширении кода будем всегда получать
е. < е.
i
Процесс расширения заканчивается, как только U становится больше е.
N
Действительно, пусть М = i/J - U Vrf(jc). Если /г(-М) > 1 - е,
/=1
то, поскольку
_ " 1МПВД1
КЩ = х ФМм/х) = J - \v~\ wT"'
x?U d "
найдется такая точка, что
1МП Frf(x)l
'V
и эту точку можно было бы включить в код.
Таким образом, для максимального кода выполняется неравенство
е < А и, w s ^(W) = w
v/=1 / л
Вспоминая, что IV^I = 2 a I i/jl = 2 °^, получаем
25
Т е о р е м а 1.3. Для любого кода и любой решающей схемы выполняется
неравенство
N < 27(1 - е) < 27(1 - е). Доказательство. Заметим прежде всего, что
1 N 1 " ~е = -гЧГТТт У \В.\.
I VAN I d /= i
Поскольку все В. не пересекаются, то
,, N
2 0 = It/'l > I U 5.1 = У 15.1 = NI V.l (1 - ё).
п ii-ii a v '
i=l
Остается заметить, что i < е.
Построенная в процессе доказательства теоремы 1.2 решающая схема имеет
достаточно сложную структуру, так что приходится хранить в памяти все
множества {В}. В то же время для любого
кода существует каноническая решающая схема
в, ' w- wn (^W))'
