Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Властивості роздільних кодів






Розглянемо схему алфавітного кодування σ і різні слова, складені з елементарних кодів. Схему σ називають роздільною, якщо з рівності

випливає, що k=l та it=jt для кожного t =1, …, k, тобто будь-яке слово, складене з елементарних кодів, єдиним способом розкладається на елементарні коди. Очевидно, що алфавітне кодування з розділь­ною схемою допускає однозначне декодування.

Схему σ називають пефіксною, якщо для будь яких i та j (I, j= 1, …, r, i≠ j) елементарний код i не є префіксом елементарного коду j.

Теорема 7.1. Префіксна схема є роздільною.

Доведення. Від протилежного. Оскільки схема σ є префіксною, то всі елементарні коди в σ попарно різні, тобто i j, якщо i≠ j. Нехай кодування зі схемою σ не є роздільним. Тоді існує слово B*, яке допускає два розклади на елементарні коди

= i 1 ik, = j 1 jl.

Нехай ­, але .Утакому разі одне із слів i 1, j 1 є префіксаміншого, а цесуперечить тому, що схема префіксна. ▲

Властивість префікеності є достатньою, але не є необхідною умо­вою роздільності схеми.

Приклад 7.1. Нехай А={а, b}, B = {0, 1}, схема σ: а→ 0, b → 01. Ця схема не префіксна, але роздільна. Справді, перед кожним вход­женням 1 у слові 2, безпосередньо є 0. Це дає змогу виділити всі пари (01). Частина слова, що залишиться, складатиметься із сим­волів 0. ▲

Нехай - слово з В*. Позначимо через ͠ β слово, яке одержують оберненням слова , тобто .Позначимо ͠ σ схему вигляду

α 1 ͠ β 1

α 2

α r ͠ β r.

Приклад 7.2. Візьмемо схему σ із прикладу 7.1. Тоді ͠ σ вигляда­тиме так: а→ 0, b→ 10. Тут схема ͠ σ є префіксною і за теоремою 7.1 - роздільною. ▲

Зауваження. Схеми σ та ͠ σ обидві або є роздільними, або ні. ▲

Це зауваження дає змогу посилити теорему 7.1.

Теорема 7.2. Якщо або схема σ, або схема ͠ σ є префіксною, то обидві схеми σ та ͠ σ є роздільними. ▲

Можна навести приклад роздільної схеми σ такої, що ні σ, ні ͠ σ не є префіксними. Отже, теорема 7.2 також дає достатню, але не необхідну умову роздільності схеми.

Для того, щоб схема алфавітного кодування була роздільною, необхідно, щоб довжини елементарних кодів задовольняли нерів­ність Макміллана (В. McMillan).

Теорема 7.3 (нерівність Макміллана). Якщо схема алфавітного кодування σ роздільна, то

Доведення. Позначимо L=mах{ l 1, l 2,..., lr }. Запишемо n -й степінь лівої частини нерівності

Розкривши дужки, отримаємо суму

де (i1, ..., іn)- різні набори номерів елементарних кодів. Позначимо як v (n, m) кількість доданків вигляду 1/2m, які входять у цю суму; тут . Для деяких m може бути v (n, m)=0. Зведемо подібні члени й отримаємо суму

Кожному доданку вигляду можна однозначно зіста­вити код (слово в алфавіті В) вигляду . Це слово складається з n елементарних кодів і має довжинуm. Отже, v (n, m) - це кількість деяких слів вигляду таких, що . Оскільки схема σ роздільна, то v (n, m) ≤ 2т. Справді, якщо припустити v (n, m)> 2 m, то за принципом коробок Діріхле існує два однакових слова , які допускають різний розклад. Можемо записати

Отже, для кожного n виконується нерівність

тобто звідки

Зауваження. У теоремі 7.3 розглянуто нерівність Макміллана для двійкового кодування. Для загального випадку q -кового коду­вання вона виглядає так:

Розглянемо ще один важливий факт.

Теорема 7.4. Якщо числа l1, …, ln задовольняють нерівність

то існує префіксна схема алфавітного кодування σ:

α 1→ β 1

α r→ β r

де l1=l(β 1), …, lr=l(β r)

Доведення. Без зменшення загальності можна вважати, що l 1l 2≤ …≤ lr. Розіб'ємо множину чисел { l 1,..., lr } на класи еквіва­лентності так: li та lj належать одному класу тоді й лише тоді, коли li = lj. Нехай μ (1≤ μ ≤ r) - кількість класів, а λ 1, …, λ μ та v 1,..., v μ позна­чають, відповідно, представників та потужності класів. Можна також уважати, що λ 1< λ 2< …< λ μ .

Тоді нерівність Макміллана можна переписати у вигляді

Ця нерівність породжує серію допоміжних нерівностей:

1, звідки ;

……………………………………………………………

Розглянемо слова довжини λ 1, у двійковому алфавіті В. Оскіль­ки , то можемо вибрати з них v 1р ізних слів β 1,..., β v 1 довжини λ 1. Виключимо з подальшого розгляду всі слова з В*, які почина­ються зі слів β 1,..., β v 1. Далі розглянемо множину слів в алфавіті В, які мають довжину λ 2 і не починаються зі слів β 1,..., β v 1. Таких слів, очевидно, є . Оскільки , то із цієї множини можна вибрати v 2різних слів. Позначимо їх через . Виключимо слова з В*, які починаються з , з подальшого розгляду. Продовжимо цей процес, вико­ристовуючи поступово допоміжні нерівності. У результаті побудуємо слова , де

Якщо взяти ці слова як елемен­тарні коди, то отримаємо деяку схему алфавітного кодування σ. Ця схема, очевидно, є префіксною. Крім того, l1)= l 1, …, lr)= lr. ▲

Наслідок 1. Нерівність Макміллана є необхідною й достатньою умовою існування алфавітного кодування із префіксною схемою й довжинами елементарних кодів, що дорівнюють l 1,..., lr. ▲

Наслідок 2. Якщо існує роздільна схема алфавітного кодування із заданими довжинами елементарних кодів, то існує також і пре­фікс на схема з тими самими довжинами елементарних кодів.

Для доведення потрібно спочатку застосувати теорему 7.3, а потім - теорему 7.4. ▲






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.