Книги по разным темам Pages:     | 1 |   ...   | 4 | 5 | 6 | 7 |

Доказательство. Пусть ' = ''. Тогда, очевидно, слово b не будет неприводимым, поскольку при выкидывании отрезка между ' и '', вместе с любым из этих слов, получим снова две различные расшифровки этого слова (проверьте). Лемма доказана.

Таким образом, все 1, 2, Е, m разные. Тогда число слов второго класса не превосходит числа непустых начал элементарных кодов, то есть не превосходит (l1 - 1) + (l2 - 1) + Е + (lr - 1) = L - r.

Слова из второго класса разбивают слово не более чем на L - r + 1 кусков. Рассмотрим пары соседних кусков. Тогда согласно одному разбиению в одной половинке уложится не более одного кодового слова, а в другой Ч не более W (согласно второму разбиению ситуация симметрична). Всего пар кусков не больше, чем L-r +1 L-r +, 2 а в каждом из них укладывается слов не более чем W + 1. Отсюда число кодовых слов в люL-r+бом разбиении не превосходит (W +1), а поскольку число целое, то не превосходит и цеW +1)(L-r + 2) лой части. Теорема доказана.

( з29. Неравенство Макмиллана.

Теорема 2 (неравенство Макмиллана). Пусть задано кодирование : ai Bi (i = 1, 2, Е, r) и пусть в кодирующем алфавите B Ч q букв и длина (Bi) = li (i = 1, 2, Е, r). Тогда если взаимно однозначно, то r 1.

i ql i=r Доказательство. Положим x =. Тогда для любого натурального n i ql i=r r r r r r 1 1 1 xn = = Еql +li2 +Е+lin.

i1 i2 in iql ql ql i1=1 i2=1 in =1 i1=1 i2=1 in= nlmax ck Обозначая lmax = maxli, получим, что эта сумма равна.

1ir qk k =Лемма. ck qk (k).

Доказательство. За ck обозначено, очевидно, число наборов (i1, Е, in) (1 ij r), для которых li + li +Е+ li = k. Но такой сумме соответствует слово Bi Bi ЕBi и 1 2 n 1 2 n длина(Bi Bi ЕBi )= li + li +Е+ li = k.

1 2 n 1 2 n В силу того, что кодирование взаимно однозначно, различным наборам, соответствуют различные сообщения, а различных сообщений длины k в алфавите из q букв не более qk ck qk (k).

емма доказана.

nlmax nlmax ck n Согласно лемме xn = = nlmax x nlmax,n. Устремляя n к бесконечности, qk k =1 k =получаем x 1. Теорема доказана.

з30. Существование префиксного кода с заданными длинами кодовых слов.

Теорема 3. Если |B| = q и натуральные числа l1, l2, Е, lr удовлетворяют неравенству r 1, i ql i=то существует префиксный код B1, B2, Е, Br (в алфавите B) такой, что длина(Bi) = li (i = 1, 2, Е, r).

r Доказательство. Пусть 1 и для любого k существует ровно dk таких i, что li = k, i ql i=lmax dk то есть 1. Тогда надо построить префиксный код, в котором ровно d1 слов длины 1, d qk k =m dk слов длины 2, и т. д., dl слов длины lmax. Имеем m (1 m lmax) 1, или, что то же max qk k =самое, d1 d2 dm-1 dm + +Е+ + 1 dm qm -(d1qm-1 + d2qm-2 +Е+ dm-1q).

q q2 qm-1 qm Рассмотрим это неравенство для m = 1: d1 q. Для слов длины 1 всего предоставляется возможностей в алфавите мощности q Ч ровно q вариантов. После выбора d1 слов длины 1 рассмотрим неравенство для m = 2: d2 q2 - d1q. Всего слов длины 2 Ч q2, однако все они могут начинаться лишь с тех букв, которые не были выбраны в качестве слов длины 1, следовательно, остаётся ровно q2 - d1q возможностей выбрать слова длины 2, что удовлетворяет условию d2 q2 - d1q. Пусть уже выбраны d1 слов длины 1, d2 слов длины 2, и т. д., dm - 1 слов длины m - 1. Тогда для слов длины m разрешено возможностей не меньше, чем qm - dm - 1q - dm - 2q2 - Е - d2qm - 2 - d1qm - 1, что удовлетворяет условию. Теорема доказана.

Следствие. Если существует взаимно однозначное кодирование со спектром длин слов l1, l2, Е, lr в алфавите B, то в B существует префиксный код с тем же спектром длин слов.

з31. Оптимальные коды, их свойства.

Будем рассматривать кодирование A* {0, 1}*. Пусть известны некоторые частоты p1, p2, Е, pk появления символов кодируемого алфавита в тексте:

p1 - a1 B1 - lp2 - a2 B2 - l, lj Ч длина j-го кодового слова, p1 + p2 + Е + pk = 1, pj > 0.

pk - ak Bk - lk Определение 1. Ценой (стоимостью, избыточностью) кодирования называется k функция c()= pili. При кодировании текста длины N его длина становится примерно i=равной k k pili.

(Np )li = N i i=1 i=Определение 2. Взаимно однозначное кодирование называется оптимальным, если на нём достигается -взаимно однозначноес().

inf Утверждение 4. Если существует оптимальный код, то существует оптимальный префиксный код с тем же спектром длин слов.

емма 1. Если Ч оптимальное кодирование и pi > pj, то li lj.

Доказательство. Допустим, что pi > pj и li > lj. Рассмотрим кодирование и рассмотрим ai Bi ai Bj кодирование ', в котором переставим кодовые слова Bi и Bj: :

a Bj, : a Bi.

j j Тогда c () - c (') = (pili + pjlj) - (pilj + pjli) = (pi - pj)(li - lj) > 0 c (') < c () не является оптимальным Ч противоречие.

емма доказана.

емма 2. Если Ч оптимальное префиксное кодирование и lmax = maxli, длина(Bj) = 1ik = lmax, Bj = Bj', где {0, 1}, то в коде существует слово Br такое, что Br = Bj.

Доказательство. Допустим, что в нет слова Bj. Тогда заменим в Bj' на Bj'. Получим код ', который является префиксным, но c()- c( )= pjдл(Bj)- pjдл(Bj)= pj c( )< c(), следовательно, не является оптимальным Ч противоречие. Лемма доказана.

емма 3. Если Ч оптимальное префиксное кодирование и p1 p2 Е pkЦ1 pk, то можно так переставить слова в коде, что получится оптимальное префиксное кодирование -' такое, что слова Bk и Bk в нём будут различаться только в последнем разряде.

Доказательство. Пусть p1 p2 Е pkЦ1 pk. По лемме 2 в коде есть слова B0 и Bмаксимальной длины. Поменяем их местами с BkЦ1 и Bk. Так как pkЦ1 pi и pk pi для 1 i k - 2, то цена кодирования не увеличится и код останется оптимальным (префиксным).

емма доказана.

p1, p2,Е, pk p1, p2,Е, pk-1, p, p Лемма 4. Рассмотрим кодирования : и :, B1, B2,Е, Bk B1, B2,Е, Bk-1, Bk 0, Bkгде p' + p'' = pk. Если один из этих наборов префиксный, то второй также префиксный и c(') = c() + pk.

Доказательство. Рассмотрим c(') - c() = p' дл(Bk0) + p'' дл(Bk1) - pk дл(Bk) = p'(lk + 1) + p''(lk + 1) - pklk = = (p' + p'')lk + (p' + p'') - pklk = pk.

емма доказана.

з32. Теорема редукции.

Теорема 4 (теорема редукции). Пусть заданы 2 набора частот и 2 набора слов:

p1, p2,Е, pk p1, p2,Е, pk-1, p, p : и :.

B1, B2,Е, Bk B1, B2,Е, Bk-1, Bk 0, Bk1) Тогда если Ч оптимальное префиксное кодирование, то и Ч оптимальное префиксное кодирование.

2) Если же Ч оптимальное префиксное кодирование и p1 p2 Е pkЦ1 p p, то Ч также оптимальное префиксное кодирование.

Доказательство. 1) Очевидно, из префиксности следует префиксность. Допустим, что не оптимально. Тогда существует префиксный код 1: c(1) < c() для тех же распредеp1, p2,Е, pk лений частот. Пусть 1 :. Рассмотрим новое кодирование D1, D2,Е, Dk p1, p2,Е, pk-1, p, p 1 :.

D1, D2,Е, Dk-1, Dk 0, DkОчевидно, кодирование 1 также является префиксным и c( )= c()+ pk {c(1)< c()} c(1)= c(1)+ pk < c()+ pk = c( ).

c c(1)+ pk (1)= Следовательно, не является оптимальным кодированием, что противоречит условию. Остаётся предположить, что оптимально.

2) Пусть Ч оптимальное префиксное кодирование и p1 p2 Е pkЦ1 p p. Допустим, что не оптимально. Тогда для частот p1, p2, Е, pkЦ1, p, p существует оптимальное префиксное кодирование 1: D1, Е, DkЦ1, Dk0, Dk1 и c(1) < c(). Тогда для частот p1, p2, Е, pk рассмотрим кодирование 1: D1, Е, DkЦ1, Dk. Получим c(1) = c(1) - pk < c() - pk = c() c(1) < c() и не оптимально, что противоречит условию. Теорема доказана.

з33. Коды с исправлением r ошибок. Оценка функции Mr (n).

Будем рассматривать равномерные коды, длины всех слов, равные n, и ошибки типа замещения, то есть вида 0 1 и 1 0.

Определение 1. Код называется исправляющим r ошибок, если при наличии в любом кодовом слове не более r ошибок типа замещения можно восстановить исходное кодовое слово.

Определение 2. Расстоянием Хэмминга (между 2 наборами длины n) называется число разрядов, в которых эти наборы различаются.

~ Определение 3. Шаром (сферой) радиуса r с центром в точке = (1,Е,n) называет~ ся множество всех наборов длины n, расстояние от которых до не превосходит r (в точности равно r).

Определение 4. Кодовым расстоянием называется расстояние по Хэммингу ~ ~ min = min (i, ).

j ~ ~ i, из кода, i j j ~ ~ ~ Утверждение 1. Код K = {1,2,Е,m} исправляет r ошибок тогда и только тогда, когда min(K) 2r +1.

Доказательство. Заметим, что условие утверждения эквивалентно тому, что расстояние между центрами шаров радиуса r (кодовыми словами) не меньше, чем 2r + 1, что эквивалентно тому, что эти шары не пересекаются. Таким образом, на выходе получится слово, принадлежащее единственному однозначно определённому шару (если в слове не более r ошибок), что позволяет точно восстановить слово, так как известен центр этого шара. Утверждение доказано.

Определение 5. Код обнаруживает r ошибок, если при наличии в нём не более r ошибок типа замещения можно сказать, были ошибки, или их не было.

~ ~ ~ Утверждение 2. Код K = {1,2,Е,m} обнаруживает r ошибок тогда и только тогда, когда min (K) r + 1.

Доказательство. Условие утверждения эквивалентно тому, что ни один из центров шаров (кодовое слово) не содержится в каком-либо другом шаре, то есть если произошло не более r ошибок, можно в точности установить, что полученное на выходе слово не совпадает с центром одного из шаров. Утверждение доказано.

Определение 6. Функция Mr (n) есть максимальное число слов длины n, образующих код, исправляющий r ошибок. Sr (n) Ч число точек (наборов длины n) в шаре радиуса r.

n n n Утверждение 3. Sr(n)= 1+ + +Е+.

2 r Доказательство. Точки шара радиуса r Ч это его центр, множество наборов, отличаюn щихся от центра в одной координате Ч, множество наборов, отличающихся от центра в n 2 координатах Ч, и т. д. Получаем утверждение.

2n 2n Теорема 5. Mr(n) S2r(n) Sr(n).

~ ~ ~ Доказательство. Рассмотрим произвольный код K = {1,2,Е,m}, исправляющий r ошибок. Из утверждения 1 следует, что шары радиуса r не могут пересекаться, следовательно, число всех точек всех шаров не превосходит числа точек n-мерного куба и 2n 2n m Sr(n) 2n m Mr(n).

Sr(n) Sr(n) ~ ~ ~ Теперь будем строить код K = {1,2,Е}. Выберем произвольно точку 1. Для выбора ~ точки 2 запрещено S2r(n) точек, так как запрещены все точки одного шара и все точки, расположенные от любой граничной точки на расстояние, не больше, чем r, то есть все точки ~ ~ ~ шара радиуса 2r с центром в точке 1. Пусть уже выбраны наборы 1,Е,k. Для выбора на~ бора k+1 запрещено точек не больше, чем kS2r (n), то есть, если kS2r (n) < 2n, то можно вы~ брать k+1. Тупик наступит при выборе m-го набора, когда 2n 2n m S2r(n) 2n m S2r(n) Mr(n) S2r(n).

Теорема доказана.

з34. Коды Хэмминга. Оценка функции M1 (n).

Рассмотрим коды, исправляющие одну ошибку типа замещения в словах длины n. Выберем натуральное k таким, что k log2 n + 2k-1 n 2k -1 = (n k log2(n +1) k = log n +1 log +1).

2 Разобьём номера всех разрядов исходного слова на k классов:

Di = {m | m = (mkЦ1mkЦ2Еm0)2, mi = 1}, 1 m n.

так, например, D0 = {1, 3, 5, 7, Е}, D1 = {2, 3, 6, 7, Е}, D2 = {4, Е}.

Определение. Кодом Хэмминга порядка n называется множество наборов k ~ = (1,2,Е,n) E2, удовлетворяющих системе уравнений (суммы по модулю 2):

= j jD = jD1 j.

= jDk j -Теорема 6. Код Хэмминга порядка n содержит 2n - k наборов, где k = n log +1 и исправляет одну ошибку.

Доказательство. Рассмотрим систему уравнений из определения кода Хэмминга 1 (3 Е)= 2 (Е)=.

2 (Е)= k - Задаём произвольно j, кроме 1,2,4,Е,2. Это можно сделать 2n - k способами. Так как k -1,2,4,Е,2 в скобках не встречаются, то они однозначно определяются из системы.

k -~ Пусть передано кодовое слово = (12 Еn), ошибка произошла в d-ом разряде и ~ пусть d = (kЦ1kЦ2Е10)2. Пусть на выходе получено слово = (12Еn), при этом i = i при i d, d = d 1. Обозначим 0 =,1 =,Е,k-1 =.

j j j jD0 jD1 jDk-Утверждение. (kЦ1kЦ2Е10)2 = d.

Доказательство. Пусть i = 0 d Di, тогда =, следовательно, i = 0 и i = i.

j j jDi jDi Пусть теперь i = 1 и d Di. Тогда = 1 = 1 i = 1 i =.

i i i jDi jDi Утверждение доказано.

Теорема доказана.

Замечание. Обычно разряды с номерами 1, 2, 4, 8, Е, 2kЦ1 называют проверочными (или контрольными), остальные Ч информационными.

2n 2n Теорема 7. M1(n).

2n n +2n 2n Доказательство. Имеем S2r(n) Mr(n) Sr(n). Правое неравенство следует из того, что S1 (n) = n + 1. Заметим предварительно, что аналогично нельзя получить и левое неравенство, так как n n(n -1) nS2(n)= 1+ n + = 1+ n + ~.

2 2 Всего различных слов в коде, исправляющем одну ошибку Ч m = 2nЦk. Поскольку k = n log +1, имеем 2n 2n k log2 n +1 m 2n-log n-1 = M1(n) m.

2n 2n Теорема доказана.

Глава V. Основы теории конечных автоматов з35. Понятие ограниченно детерминированных (автоматных) функций, их представление диаграммой Мура. Единичная задержка.

Пусть даны A = {a1, a2, Е, ar} Ч входной алфавит и B = {b1, b2, Е, bm} Ч выходной алфавит. Определим множества A и B как множества всевозможных последовательностей в алфавитах A и B соответственно.

Определение 1. Отображение : A B называется детерминированной функцией (д.-функцией), если b(t) для любого t = 1, 2, Е однозначно определяется по a(1), a(2), Е, a(t).

a1(1)Еa1(t)Е b1(1)Еb1(t)Е Обозначать д.-функции будем так: :, причём, a2(1)Еa2(t)Е b2(1)Еb2(t)Е если a1 (1) = a2 (1), то b1 (1) = b2 (1);

a1(1)= a2(1) a a2(2), то b (2)= если (t) = b2(t).

a1(t)= a2(t) Определение 2. Пусть задана д.-функция : A B. Рассмотрим произвольное слово a = a1a2 Еak A*. Определим функцию a следующим образом: пусть a(1), a(2), Е, a(t)Е Ч произвольная входная последовательность. Рассмотрим (a1a2Еaka(1)a(2)Еa(t)Е) = b1b2Еbkb(1)b(2)Еb(t)Е.

Тогда положим a (a(1)a(2)Еa(t)Е)= b(1)b(2)Еb(t)Е. a при этом называется остаточной функцией для по слову a A.

Определение 3. Детерминированная функция : AB называется ограниченно детерминированной, если у неё имеется лишь конечное число различных остаточных функций.

Определение 4. Автоматом (инициальным) называется любая шестёрка (A, B, Q, G, F, q0), где A, B, Q Ч конечные алфавиты, G: A Q Q, F: A Q B, q0 Q Ч начальное состояние.

Входом автомата служит последовательность a(1)a(2)a(3)Е, a(t)Е A* (конечная или бесконечная), выходом автомата служит последовательность z(t), при этом автомат задаётся системой канонических уравнений z(t)= F(x(t),q(t -1)), q G(x(t),q(t -1)), (t)= q(0)= q0.

Определение 5. Отображение : A B называется автоматной функцией, если существует автомат, который реализует это отображение.

Pages:     | 1 |   ...   | 4 | 5 | 6 | 7 |    Книги по разным темам