Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
— нетривиальное разложение элементарного кода Ви т. е. разложение, отличное от разложения
причем [Г и Р" отличны от элементарных кодов.
Параметр и> может быть целым числом, большим или равным нулю.
Соотношение (1) означает, что в элементарном коде Ві можно отбросить некое начало Р' и некий конец р" так, что оставшаяся часть разбивается на элементарные коды (см. рпс. 3).
Очевидно, что для каждого Ві число разложений вида (1) конечно. Обозпачим через IV максимум чисел и?у взятый по всем разложениям Ві и но всем г, т. е.
Яг &1&2, Яз Ь3Ьі.
(2)
Пусть
(1)
Ві = Ві (Р' = Р"=Л)'
XV = шах и).
-х. Л. > . ±ЯЛЛГ*ХП пиди^исАШШ
Пример 5. Рассмотрим алфавитное кодирование с & = {«,, аа, аэ, а4, аь}, © = (г?!, Ь2, ЬЛ и схемой
А, &1&2,
Яа
Я| Ьг^1,
А* —
Так как 6 > и > 2, то ТУ < 3. С другой стороны,
Въ — Ъ2ЬхЪгЪгЬй — Ъ2ВхВи
поэтому ТУ *= 2.
Обозпачим, наконец, через ?^(51) множество всех пе-пустых слов в алфавите 51, имеющих длину, не превосходящую N. Ясно, что —конечное
множество, его мощность равна
N
2 Л *=1
Рис. 3 Сформулируем теперь крите-
рий взаимной однозначности алфавитного кодирования.
Теорема 3 (Марков Ал. А. [22, 23]). Для всякого алфавитного кодирования со схемой 2 существует такое А0,
у.<Г-е±ЩЬ=?±3-].
что проблема взаимной однозначности алфавитного кодирования сводится к аналогичной проблеме для кодиро-
Лт
вания конечного множества ?* °(§1).
Доказательство. Если в алфавитном кодировании нарушена взаимная однозначность, то найдется такое слово В, которое допускает по крайней мере две различные расшифровки А' и А". Для доказательства теоремы достаточно установить, что можно найти также такое слово В, что для его расшифровок А' и А" имеют место неравенства
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
265
Слово В, допускающее не менее двух расшифровок, называется неприводимым, если каждое слово Вполучающееся из В путем выбрасывания непустого куска, допускает не более одной расшифровки.
Ясно, что с самого начала можно предполагать, что слово В — неприводимо. Рассмотрим его две расшифров-
Рис. 4
ки А' и А". Очевидно, что с ними связаны два разбиения слова В на элементарные коды — верхнее Тх и нижнее Тг (см. рис. 4).
Возьмем произведение Т этих разбиений, т. е. разбиение, которое получается путем одновременного разбиения 2\ и Т2. Слова этого нового разбиения Т разделим на два класса: к первому классу отнесем слова, являющиеся элементарными кодами, ко второму — все остальные слова. Ясно, что слова из первого класса входят каждое ровно в одно разбиение, а слова второго класса (на рис. 4 изображены жирными отрезками) являются одновременно непустыми началами и концами элементарных кодов из разных разбиений и отличны от элементарных кодов, так как слово В неприводимо. Покажем, что каждые два слова и р" из второго класса различны, т. е. р'.^ р", Положим противное: р' *= р " = р, Тогда
В = В’$'В"$"В'"- В'$В"$В'\
Утверждается, что слово получающееся из В
путем выбрасывания куска допускает по крайней
мере две расшифровки. Для расположения слов р' и р" возможны 4 случая, которые изображены на ряс. 5. Нетрудно видеть, что случай в) сводится к случаю а), случай г) —к случаю б). Для этого в в) и г) нужно поменять ролями разбиения Тх и Тг.
В случае а) при выбрасывании куска В"р" и сдвигании кусков В'$' я В'" верхнее разбиение получается из склейки частей верхнего разбиения, нижпее — из склейки частей нижиего разбиения,
266
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
В случае 6) верхнее разбиепие получается из склейки части верхнего разбиения для куска В'р' и нижнего разбиения для В'", нижнее разбиепие — путем склейки нижнего разбиения для куска В'$' и верхпего — для куска В"'.
Итак, для слова В'$'В'" во всех случаях мы получа-
В' Ї
Р” 8'
ем по крайней мере две расшифровки, что противоречит тому, что исходное слово неприводимо.
Число р слов второго класса не превосходит числа непустых собственных начал элементарных кодов, т. е. р^(/(В|)-1) +
... + (г(?г)— !}=?- г.
Слова из второго класса ‘ разбивают слово В не более чем на Ь — г + 1 кусков, некоторые из них могут быть пустыми (см. рис. 6).
Пусть р° = рр+1=Л. Рассмотрим один из кусков, рас* положенный между словами р' и рт {/ = 0, ..., р);
р
В этом куске все словаВ^ принадлежат одному
и тому, же разбиению слова В, например Ти а слово
В
Рис. 6
№* ...ОД
І + 1
Ві
принадлежит другому разбиению— Тг. При этом IV ^ IV. Поэтому с каждым куском связаны и) элементарных кодов одного разбиения и один элементарный код другого разбиения.
Если взять теперь два соседних куска
$В, ...В, |У+3?? „ ... В » (3^
*1 й
то элементарные коды
В ,, .. #1 В і , ві№ = Р,+15 *... В* р
ію/ І!
И-а
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
207
входят б одно разбиение, а
в * В" > В? = рв, ... В ,
*1* ’ -1 ' й
— в другое разбиение (см. рис. 7).
Следовательно, кускам разбиения Т между словами ^ и ^+‘ для одной и той же четности / соответствуют
Я* 8г А' в,' 8Г Вг А-„ /5^2
{" I/ /г 1В>! 1} 1г . I(Ц-Г
?ч
Рис. 7
элементарные коды В{ исходного разбиения (например Г1) и группы элементарных кодов В1го того же
