Головна |
приклад: V = {1, 10, 01, 11} - невільний. l1 = l2 = l3 = l4 = 2; q = 2; {0, 1} = B; k = 4. Нерівність Мак Миллана не виконується.
Введемо додаткове позначення Vn = {a | a = a1a2... an, Де ai I V для будь-яких i = 1, 2, ..., n} - безліч всіх слів, представлених у вигляді твору.
приклад. V = {1, 0110 1001}; q = 2; l1 = 1, l2 = l3 = 4; k = 3. , , .
Лемма. Якщо безліч V складається зі слів довжини ? L, то w (V) ? L.
Доведення: V = V1 E V2 E ... E VL, Де V1 - Безліч слів довжини 1. [Щодо визначення w (a)] [Щодо визначення w (a)]
Розглянемо | Vi| ? qi, Vi - Число слів з i-букв. I-ю букву в слові вибираємо q способами. Тоді кожний доданок ? 1. Отже:
Теорема (Пряма теорема про спектрі вільного коду)
Спектр будь-якого вільного коду задовольняє нерівності Мак Миллана.
Доведення:
Візьмемо довільне n I N (як завгодно велике). (W (V))n = [Щодо визначення w (V)] = =
=
Розглянемо li1 + ... + Lin = [Сума довжин кодових слів] = | Vi1| + ... + | Vin| = - Для будь-якого слова, яке розглядається за творами слів коду V.
= [По Лемме] = w (Vn) ? nL - для кожного доданка з цієї суми є єдине доданок з попередньої суми, значить ці дві суми рівні.
Отже ми отримали: і при n ® ? ми отримуємо w (V) ? 1, тобто нерівність Мак Миллана виконується.
Теорема (Зворотній теорема про спектрі вільного коду)
якщо набір натуральних чисел задовольняє нерівності Мак Миллана , То існує префіксний код зі спектром .
(Лекція 16)
Доведення: (Методом математичної індукції)
l1 ? l2 ? ... ? lp. Індукція по р (1 ? р ? k)
1 крок. Нехай р = 1 ? l1 = | V1| ? Код {V1} - Префіксний.
2 крок. нехай l1 = | V1|, ..., Lp-1 = | Vp-1|. Припустимо, що код Vp-1 = {V1, ..., Vp-1} - Префіксний. Доведемо, що існує таке слово Vp, Довжина якого | Vp| = lp і код Vp = {V1, ..., Vp} Буде префіксним для будь-яких p = 1, 2, ..., n. Розглянемо всі слова довжини lp. Їх кількість дорівнює . Щоб код був префіксним, виключимо всі слова, які не можна додати в код Vp-1 (Інакше він стане префіксним), тобто над виключити слова з префіксами. Решта слова - це ті, які можна додати в код Vp-1. Порахуємо, скільки слів викинемо.
Якщо до слова довжини lp-l1 додати префікс V1, То код Vр буде префіксним. Але додавати не можна. Тому викинемо все слова довжини lp-l1. їх кількість . З аналогічної причини викинемо все слова довжини lp-l2. їх кількість ... Викинемо все слова довжини lp-lр-1. їх кількість . Всього викинуто слів: . Доведемо, що залишиться слів . . Так як 1 ? р ? k, то . Помноживши обидві частини на , отримаємо .
приклад: задовольняє нерівності Мак-Миллана. Нехай q = 2, B = {a, b} ? V1 = A, V2 = Ba, V3 = Bbaa, V4 = Bbab ? Код префіксний, так як .
Доведення еквівалентності задач I і II (методом від противного):
Якщо знайдеться вільний код V0, Який не є префіксним, такий, що С (V0) = Min (краще префіксного). Нехай С (V0, P)
Властивості префіксних кодів | Властивості оптимальних префіксних кодів