Лекции по дискретна математика


Категория на документа: Математика


Доказателство:
нека  е префиксен код; да допуснем, че  не е разделим;
тогава съществува дума   B+, която се декодира поне по два различни начина: , ;
нека k е такова, че 1  k  min (r, s) и

= , …, = ,  ; тогава  ( ) и  ( ) започват от едно и също място в  и  ( )   ( ), тъй като  ; единствената възможност е d ( ( ))  d ( ( ));
ако d ( ( )) < d ( ( )), тогава  ( ) е префикс на  ( ) – противоречие;
ако d ( ( )) > d ( ( )), тогава  ( ) е префикс на  ( ) – противоречие;
така всеки префиксен код е разделим;

обратното твърдение не е вярно – например, нека
A = { a, b, c}, B = { 0, 1}, a = 01, b = 00, c = 0111; този код не е префиксен, но е разделим;

Теорема (неравенство на МакМилан-Крафт): Нека
 : A  B+ е разделим код, |A| = n, |B| = m, d ( (ai)) = li;
тогава  1;
Доказателство: нека C = ; нека t  N, t > 0;
тогава ;
да означим M = max (l1, l2, …, ln); тогава
за всеки i1, i2, …, it  { 1, 2, …, n} имаме t   M.t, тъй като
за всяко i = 1, 2, …, n, 1  li  M;
да означим с N (t, r) броят на всички кодирани съобщения
 ( ) ( )… ( ) с дължина r;
ще покажем, че N (t, r)  mr; да допуснем противното, т.е.
N (t, r) > mr; тъй като всички думи с дължина r над B са точно mr на брой, то от принципа на Дирихле получаваме, че има две съобщения, които се кодират еднакво – противоречие с разделимостта на кода;
преобразуваме горната сума:

 ;
така за всяко t  N, t > 0 имаме Ct = (M-1).t + 1;
това е възможно единствено при C  1, тъй като показателната функция расте по-бързо от линейната; така  1;

Теорема: За всеки разделим код  : A  B+, |A| = n, |B| = m с дължини на кодовите думи l1  l2  … ln, съществува префиксен код
, така че d ( (a1)) = l1, d ( (a2)) = l2, …, d ( (an)) = ln;
Доказателство:
ще считаме, че B = { 0, 1, …, m-1};
всяко дробно число q, 0  q < 1 има единствено (евентуално безкрайно) m-ично представяне;
нека
q1 = 0
q2 =

qi =

qn =
очевидно за всяко i, qi  0 за всяко i, също qi < 1 от неравенството на МакМилан-Крафт, приложимо за разделимия код  (последният член не присъства, за това неравенството е строго); от самия вид на числата qi е ясно, че m-ичното им представяне е крайно;
за i < j имаме: qj – qi = и тъй като li  li+1  … lj-1 първата различна от 0 цифра в m-ичното представяне на qj – qi ще се появи на позиция li или по-наляво от нея (считано от m-ичната точка);
образуваме новият код  по следния начин:
 (ai) са първите li цифри в m-ичното представяне на qi;
очевидно d ( (a1)) = l1, d ( (a2)) = l2, …, d ( (an)) = ln; ще покажем, че
 е префиксен; да допуснем противното, т.е. съществуват индекси
i < j, такива че  (ai) е префикс на  (aj), т.е. първите li букви
на  (aj) съвпадат с буквите на  (ai); тогава първите li цифри в



Сподели линка с приятел:





Яндекс.Метрика
Лекции по дискретна математика 9 out of 10 based on 2 ratings. 2 user reviews.