Головна

Нерівність Мак Миллана

  1. А) нерівність у розподілі доходів різних верств населення
  2. Питання №20 Нерівність в розподілі доходів і спосіб його зміни. Крива Лоренца. Індекс Джині.
  3. Нерівність у праці малопрестижного працю
  4. Нерівність доходів в ринкових умовах.
  5. Нерівність доходів і економічні заходи соціальної підтримки.
  6. Нерівність і сім'я: аналіз з позиції соціального конфлікту
  7. нерівність Єнсена

приклад: 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) 1, P) (*). V1 - Префіксний код.  - Спектр V0. По прямій теоремі про спектрі вільного коду ?  ? [По зворотної теоремі про спектрі вільного коду] ? Існує префіксний код  зі спектром  . Отже, ?  . Отримали протиріччя з нерівністю (*).

Властивості префіксних кодів | Властивості оптимальних префіксних кодів

© 2016-2022  um.co.ua - учбові матеріали та реферати