WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 4 | 5 || 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 запрещено точек не больше, чем k·S2r (n), то есть, если k·S2r (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 || 7 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.