Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод Хаффмана побудови оптимального коду.
|
|
Метод побудови оптимальної схеми алфавітного кодування. Спочатку здійснюють послідовні стиснення алфавіту А до отримання алфавіту із двох букв, оптимальна схема кодування для якого очевидна: першу букву кодують символом 0, другу – символом 1, після цього використовують послідовні розщеплення отриманої схеми. Очевидно, що отримана схема є префіксною. Описаний метод кодування запропоновано 1532 року американським математиком Хаффманом і названий його ім’ям.
Ґрунтуючись на алгоритмі Хаффмана, можна безпосередньо побудувати кодове дерево оптимального коду. Це дерево називають деревом Хаффмана.
За алгоритмом Хаффмана бінарне дерево, яке відповідає оптимальному коду, будують знизу вверх, починаючи з |А|=r листків, у цьому разі виконують (r-1) злиття. Злиття полягає в побудові нового дерева із двох наявних дерев (або листків) з найменшими ймовірностями. Причому листок або дерево з більшою ймовірністю – ліве піддерево, а сума ймовірностей лівого і правого піддерев дорівнює ймовірності отриманого дерева. (Її записують у корінь). Помішають 0 на ребро до лівого піддерева, а 1 – на ребро до правого піддерева. Список ймовірностей перед кожним злиттям упорядковують за спаданням.
24. Коди, стійкі до перешкод. Загальна теорія.
Розглянемо схему рівномірного кодування σ k, n іщ параметрами k, n:
…
Де 
- слова довжини, відповідно, k та n (n> k). Кажуть, що схема σ k, n визначена кодом 
.
Нормою ||α || двійкового вектора α =а1а2…аn називають число, яке дорівнює кількості його одиничних компонент. Отже,
||α ||= 
Припустимо, що в каналі зв’язку діє джерело адитивних перешкод, яке описують множиною P(n, t). Елементи цієї множини – двійкові вектори-помилки x1x2…xs, у яких норма будь якого фрагмента 
не більша, ніж t, якщо довжина фрагмента l< =n. Це означає, що якщо на вході каналу зв’язку передано повідомлення α, то на виході може бути отримано будь-яке слово із множини 
.
Оскільки проблема локалізації інформації (розділення закодованого повідомлення на елементарні коди) у моделі рівномірного кодування тривіальна, то виявлення помилок полягає в знаходженні незбігу локалізованої групи n символів з жодним елементарним кодом. Якщо внаслідок помилки елементарний код перейде в інший елементарний код, то помилку не буде виявлено. Іноді можливе виправлення помилки.
Канал зв’язку називають надійним, якщо будь-які помилки виявляються або виправляються відповідно до заданої мети декодування.
25. Коди, стійкі до перешкод: коди Хемінга.
Р. Хемінг 1950 р. запропонував коди для виявлення й виправлення помилок у разі t=1. Коди Хемінга лінійні та мають найменшу надлишковість, можливу для даного k.
Коди Хемінга 
для виявлення помилок у каналі зв’язку із джерелом перешкод P(n, 1) визначені для будь-якого n:
.
Код - лінійний. Справді, якщо X, Y є , то
Тобто X 
Y є . За співвідношенням 
ρ ()=2, тому, будь-яка помилка в каналі з джерелом перешкод P(n, 1) виявляється. Як інформаційні розряди для коду можна взяти будь-які n-1 розрядів, оскільки значення в довільному розряді слова 
однозначно визначається за значеннями в інших розрядах із рівняння 
. Маємо 
Як одну з породжувальних матриць можна взяти
Якщо вибрати I={1, 2, j, n-1}, то отримаємо відповідну схему рівномірного кодування 
:
, де 
. Надлишковість у разі використання становить 
.
У цьому коді Хемінга найбільш явно використана ідея перевірки на парність. Коди Хемінга для виправлення помилок у каналі зв’язку з джерелом перешкод P(n, 1) будують для значень 
. Код зручно задавати перевірочною матрицею, яка має s рядків та 
стовпців. Стопцями є всеможливі ненульові двійкові набори довжини s. Їх зручно розташувати так, щоб і-тий зліва стовпчик hi був двійковим розкладом числа і (старші розряди зверху):
0 0 0 … 1 1
0 0 0 … 1 1
……………… = H()
0 1 1 … 1 1
1 0 1 … 0 1
Таке розташування стовпців перевірочної матриці зумовлено вибором як контрольних тих розрядів, у яких номери є степенями двійки.
26. Булеві функції. Означення, задання таблицями і формулами, істотні і неістотні змінні.
Булевою називають функцію f(x1, …, xn), область значень якої складається з 0 та 1, яка залежить від змінних x1, …, xn, що приймають також лише ці 2 значення. Множину всіх булевих функцій позначають Р2. Булеві функції широко застосовують у математичній і технічній кібернетиці, зокрема, для конструювання мікропроцесорів. Булеву функцію від n змінний називають n-місною. Областю її визначення є множина 
усіх можливих n-місних наборів значень змінних. Ці набори називають двійковими наборами, або просто наборами. Отже, область визначення n-місної булевої функції є скінченною і складається з 2n наборів значень змінних. Для набору (а1, …, аn) використовують позначення аn або а.
Т-ма. К-сть р2(n) всіх функцій з Р2, які залежать від n змінних x1, …, xn, дорівнює 
Множину наборів значень змінних, на яких булева функція f(x1, …, xn) приймає значення 1, позначають Nf:
Nf={an|anє 
, f(an)=1}. Множина Nf, очевидно повністю визначає функцію f.
Змінну хі функції f(x1, …, xi-1, xi, xi+1, …, xn) називають істотною, якщо існує такий набір (а1, …, аi-1, аi+1, …, аn) значень решти змінних, що f(а1, …, аi-1, 0, аi+1, …, аn)≠ f(а1, …, аi-1, 1, аi+1, …, аn).
Змінну, яка істотною не є, називають неістотною, або фіктивною. Отже, змінна хі функції f(x1, …, xi-1, xi, xi+1, …, xn) неістотна (фіктивна), якщо f(x1, …, xi-1, 0, xi+1, …, xn)= f(x1, …, xi-1, 1, xi+1, …, xn).
Визначення елементарних функції за допомогою таблиці:
| х1 х2 | х1х2 | х1vх2 | х1  х2
| х1  х2
| х1+х2 | х1|х2 | х1  х2
|
| 0 0 | |||||||
| 0 1 | |||||||
| 1 0 | |||||||
| 1 1 |
За допомогою елементарних функцій можна зобразити будь-яку булеву функцію у вигляді формули. Для булевих функції можливі будь-які підстановки одних функцій замість змінних в інші функції, можливі буль-які перейменування змінних.
27. Диз’юктивні нормальні форми.
Елементарною кон`юнкцією називають вираз ……….., де хіj – змінні з множини Х, причому всі хіj різні. Число r називають рангом кон`юнкції. Якщо r=0, кон`юнкцію називають порожньою та вважають такою, що дорівнює 1.
Елементарну кон., яка містить усі змінні з множини Х, називають конституентою одиниці. Інакше кажучи, конституента одиниці – це елементарна кон. з рангом n.
Диз`юктивною нормальною формою називають диз. D=k1 v k2 v..v ks елементарних кон. kj, у якій kj попарно різні.
Є алгоритм, який дає змогу для будь-якої формули булевої алгебри на основі тотожних перетворень знайти рівносильну до неї ДНФ. На першому його етапі формулу перетворюють у рівносильну, побудовану зі змінних та їх заперечень за допомогою самих лише диз. та кон. Для цього використовують закони де Моргана та закон подвійного заперечення. На другому етапі домагаються, щоб усі кон. виконувались раніше, ніж диз., для чого розкривають дужки на підставі дистрибутивного закону для кон. (XvY)Z=XZvYZ або тотожності (XvY)(ZvU)=XZvYZvXUvYU. Далі з використанням співвідношень для констант і закону суперечності вилучають нулі та, виходячи із законів ідемпотентності, об`єднують рівні члени. На цьому процес отримання ДНФ закінчують.
Досконалою ДНФ називають ДНФ, у якої кожна елементарна кон. kj(j=1,.., s) – конституента одиниці.
Т. Будь-яку булеву функцію f(x1,.., xn)≠ 0 можна єдиним способом подати в ДДНФ.
Для функції, заданої таблицею, ДДНФ будують так: для кожного набору, на якому функція приймає значення 1, знаходять відповідну йому конституенту одиниці; диз. Всіх цих конституент – це ДДНФ даної функції.
28. Кон'юктивні нормальні форми.
Елементарною диз. називають вираз …….., у якому всі xij різні xij є X. Число r називають рангом диз. Якщо r=0, диз. називають порожньою та вважають такою, що дорівнює 0.
Кон. нормальною формою називають кон. d1^d2^…^ds елементарних диз. dj, у якій всі di різні.
Є алгоритм, який дає змогу для будь-якої формули булевої алгебри знайти тотожну до неї КНФ. На першому його етапі формулу перетворюють у рівносильну, побудовану зі змінних та їх заперечень за допомогою самих лише диз. та кон. Для цього використовують закони де Моргана та закон подвійного заперечення. На другому етапі домагаються, щоб усі диз. виконувались раніше кон. Для цього потрібно скористатися дистрибутивним законом XvYZ=(XvY)(XvZ) або наслідком із нього XYvZU=(XvY)(XvU)(YvZ)(YvU). Потім на підставі співвідношень для констант і закону виключеного третього вилучають одиниці та на підставі законів ідемпотентності об`єднують рівні члени.
Елементарну диз`юнкцію, яка містить усі змінні з множини Х, називають конституентою нуля. Інакше кажучи, конституента нуля – це елементарна диз. з рангом n.
Досконалою КНФ називають КНФ, у якої кожна елементарна диз. dj (j=1, …., s) – конституента нуля.
ДКНФ за таблицею булевої функції f будують так: виділяють набори, на яких функція набуває значення 0, і для кожного з них записують відповідну конституенту нуля. Кон`юнкція цих конституент нуля являє собою ДКНФ функції f.
29. Поліном Жегалкіна
Елементарну кон. називають монотонною, якщо вона не містить заперечень змінних. Наприклад: X1X2X3, X1, 1 – монотонні кон. Формулу P(xn)=K1+K2+….+Ks, де K1+K2+….+Ks - попарно різні монотонні кон. змінних із множини X={x1, x2, …, xn}, називають поліномом Жегалкіна. Найбільший із рангів елементарних кон., що входять в поліном, називають степенем полінома. За окремим означенням 0 також уважатимемо поліномом Жегалкіна.
Т. Будь-яку булеву функцію можна єдиним способом подати поліномом Жегалкіна.
Методи побудови поліному Жегалкіна:
Метод невизначених коефіцієнтів: Для ф-ії f(x1, …, xn) записують найбільш загальний вигляд полінома Жегалкіна P(x1, …, xn) з невизначеними коефіцієнтами (їх 2n). Зокрема, поліном від двох змінних має загальний вигляд:
P(x, y)=C0+C1x+C2y+C3xy
Для кожного двійкового набору (a1, …, an) значень змінних записують рівняння f(a1, …, an)=P(a1, …., an). Таких рівнянь буде 2n, розв`язавши їх, отримують коефіцієнти полінома P(x1, ….xn).
Побудова полінома Жегалкіна на основі рівносильних перетворень: Один із способів побудови полінома Жегалкіна полягає в наступному. Спочатку будують рівносильну формулу, у якій є лише операції кон. та запаречення, а потім замінюють всюди (не)Х на 1+х. Після цього тривіальними перетвореннями отримують поліном Жегалкіна.
Т. Усі змінні булевої функції, які входять у її поліном Жегалкіна, істотні.
30. Алгебри булевих функцій
Множину P2 всіх булевих функцій разом з уведеною на ній системою операцій називають алгеброю булевих функцій. Алгебру (P2; ˥, v, ^) з операціями заперечення, кон. та диз. називають алгеброю Буля. Формули цієї алгебри будують зі знаків операцій, круглих дужок, букв x, y, z…і констант 0 та 1. Букви позначають довільні булеві функції, при цьому булеві змінні розглядають як окремий випадок булевих функцій. Знак кон. ^ у формулах зазвичай не пишуть. Якщо немає дужок, пріоритет операцій у булевій алгебрі такий: заперечення, кон., диз.. У булевій алгебрі як дужки в разі заперечення виразів використовують сам символ заперечення.
Закони алгебри Буля:
Ø Асоціативності (XY)Z=X(YZ)=XYZ, (XvY)vZ=Xv(YvZ)=XvYvZ;
Ø Комутативності XY=YX, XvY=YvX;
Ø Дистрибутивності (XvY)Z=XZvYZ, XYvZ=(XvZ)(YvZ);
Ø Подвійного заперечення (˥ ˥ X)=X;
Ø Де Моргана ˥ (XY)= ˥ Xv˥ Y, ˥ (XvY)= ˥ X ˥ Y;
Ø Ідемпотентності XX=X, XvX=X;
Ø Поглинання XvXY=X, X(Xvy)=X;
Ø Співвіднош. для констант ˥ 1=0, ˥ 0 =1, 1X=X, 0X=0, 1vX=1, 0vX=X;
Ø Виключення третього Xv˥ X=1;
Ø Протиріччя X˥ X=0;
31. Алгебра Жегалкіна
Множину P2 всіх булевих функцій разом з уведеною на ній системою операцій називають алгеброю булевих функцій. Алгебру (P2; ^, +) з операціями кон. та додавання за mod2 називають алгеброю Жегалкіна.
Формули цієї алгебри будують зі знаків операцій, круглих дужок, букв x, y, z…і констант 0 та 1. Букви позначають довільні булеві функції, при цьому булеві змінні розглядають як окремий випадок булевих функцій. Знак кон. ^ у формулах зазвичай не пишуть. Якщо немає дужок, пріоритет операцій в алгебрі Жегалкіна такий: спочатку виконується кон., а потім – додавання за mod2. За наявності дужок спочатку виконуються операції всередині їх.
Закони алгебри Жегалкіна:
Ø Асоціативності (XY)Z=X(YZ)=XYZ, (X+Y)+Z=X+(Y+Z)=X+Y+Z;
Ø Комутативності XY=YX, X+Y=Y+X;
Ø Дистрибутивності (X+Y)Z=XZ+YZ;
Ø Ідемпотентності XX=X;
Ø Співвіднош. для констант 1Х=Х, 0Х =0, Х+0=X;
Ø Зведення подібних членів у разі додавання за mod2 X+X=0
32. Замкнені класи булевих функцій.
Класи T0 та T1 Множину К булевих функцій називають замкненим класом, якщо довільна суперпозиція функцій із К також належить К. Будь-яка система Q булевих функцій породжує якийсь замкнений клас. Цей клас складається з усіх функцій, які можна одержати суперпозиціями функцій із Q, його називають замиканням Q.
Існує 5 найважливіших замкнених класів:
ü Клас T0 функцій, що зберігають 0;
ü Клас Т1 функцій, що зберігають 1;
ü Клас S самодвоїстих функцій;
ü Клас M монотонних функцій;
ü Клас L лінійних функцій;
Клас Т0 функцій, що зберігають 0. Булеву функцію f(x1, …, xn) називають функцією, яка зберігає 0, якщо f(0, …, 0)=0.
Наприклад, функції 0, x, xy, XvY, X+Y зберігають 0, тобто належать класу Т0, а функції 1, ˥ X, X→ Y – не зберігають, тобто не належать класу Т0. Таблиця значень функції з класу Т0 містить 0 у першому рядку. Отже у класі Т0 є ½ *22^n булевих функцій, що залежить від n змінних.
Т. Т0 – замкнений клас. Інакше кажучи, із функцій, що зберігають 0, суперпозицією можна одержати лише функції, які зберігають 0.
Д. Клас Т0 містить тотожну функцію. Отже, досить показати, що функція F(x1, …., xn) = f(f1(x1, …, xn), ……, fm(x1, …., xn)) зберігає 0, якщо функції f, f1, f2, …, fm зберігають 0. Справді, f(f1(0, …, 0), f2(0, …, 0), …, fm(0, …, 0))=f(0, …, 0)=0.
Н. Повна система функцій має містити хоча б одну функцію, яка не зберігає 0.
Клас T1 функцій, що зберігають 1. Булеву функцію f(x1, …., xn) називають функцією, яка зберігає 1, якщо f(1, …, 1)=1.
Наприклад, функції 1, X, XY, XvY, X-> Y належать класу T1, а ф-ії 0, ˥ Х, X+Y – ні.
Т. Т1 - замкнений клас
Д. Т1 містить тотожну функцію. Отже, досить довести, що функція F(x1, …, xn)=f(f1(x1, …, xn), …., fm(x1, …, xn)) зберігає 1, якщо функції f, f1, …., fm зберігають 1. Справді, f(f1(1, …, 1), …., fm(1, …, 1))=f(1, …, 1)=1.
Н. Повна система функцій має містити хоча б одну функцію, яка не зберігає 1.
33. Клас S. Лема про несамодвоїсту функцію.
Булеву функцію f(x1, …., xn) називають самодвоїстою, якщо вона набуває протилежних значень на протилежних наборах значень змінних: f(x1, x2, …, xn)= ˥ f(˥ x1, ˥ x2, …, ˥ xn).
Самодвоїсті: x, ˥ x, x1+x2+x3. Несамодвоїсті: x1x2, x1 v x2, x1-> x2
Т-ма. Клас S самодвоїстих ф-цій замкнений.
Н. Повна система булевих ф-цій повинна містити хоча б одну несамодвоїсту функцію.
Л. Із несамодвоїстої функції f(x1, …, xn) підстановкою функцій x та ˥ х можна отримати несамодвоїсту функцію однієї змінної, тобто константу.
Д. Нехай f(x1, ….xn) не належить S. Отже існує хоча б один набір an=(a1, …, an) значень змінних такий, що f(a1, …., an)=f(˥ a1,.., ˥ an). За набором аn=(a1, …, an) визначимо допоміжні функції ϕ і (х), і=1….n:
Х, якщо аі=0
Φ i= ˥ Х, якщо аi=1
Легко переконатись, що ці функції мають властивість ϕ і(0)=аі , ϕ і(1)= ˥ аі (і=1….n). Розглянемо функцію φ (x)=f(ϕ 1(x)….ϕ n(x)). Її отримано з функції f(x1…xn) підстановкою х та ˥ х. Функція φ (х) – константа, бо φ (0)=f(ϕ 1(0)….ϕ n(0))=f(a1, …, an)=f(˥ a1,.., ˥ an)=f(ϕ 1(1), …, ϕ n(1))=φ (1).
34. Клас M. Лема про немонотонну функцію.
Функцію f(xn)=f(x1, …, xn) називають монотонною, якщо для будь-яких двійкових наборів an і bn із того, що an≤ bn, випливає, що f(an)≤ f(bn).
Монотонні: 0, 1, х, х1х2, x1 v x2
Немонотонні: x1+x2, x1-> x2, ˥ x
Т. Клас М монотонних функцій замкнений.
Н. Повна система булевих функцій повинна містити хоча б одну немонотонну функцію.
Л. Із немонотонної функції підстановкою констант 0, 1, і функції X можна отримати функцію ˥ Х.
Д. Нехай f(xn) не належить M. Отже, існують такі два набори an=(a1, …, an). bn=(b1, …, bn) значень змінних x1, …, xn, що an≤ bn але f(an)> f(bn), тобто f(an)=1, f(bn)=0.
Якщо an та bn відрізняються k компонентами, то в цих компонента у наборі an є нулі, а в наборі bn – одиниці. Підставимо у функцію f(xn) замість змінних, яким у наборах an та bn відповідають однакові значення, просто ці значення, а на місце решти k змінних – функцію х. Тоді отримаємо функцію однієї змінної g(x). З урахуванням того, що f(an)=1, f(bn)=0, одержимо, що g(0)=f(an)=1, g(1)=f(bn)=0. Отже g(x)= ˥ x.
35. Клас L. Лема про нелінійну функцію.
Булеву функцію f(xn)=f(x1, …, xn) називають лінійною, якщо її поліном Жегалкіна має вигляд f(xn)=C0+С1х1+С2х2+….+Сnxn.
Це поліном першого степеня, або лінійний поліном. Він не має багатомісних кон’юнкцій. Коефіцієнти лінійного полінома утворюють довільний набір значень із n+1 одиниць та нулів.
Т. Клас L лінійних функцій замкнений.
Лінійні: 0, 1, х, х у, ˥ х
Нелінійні: x-> y, x v y
Н. Повна система булевих функцій повинна мати хоча б одну нелінійну функцію.
Л. Якщо функція f(xn) нелінійна, то кон`юнкцію двох змінних можна подати як суперпозицію констант 0, 1 та функцій ˥ Х і f(xn).
Д. Нехай функція f не належить L. Тоді поліном Жегалкіна функції f містить кон`юнкції змінних. Виберемо серед них кон`юнкцію з найменшим рангом r≥ 2, нехай це буде k=xi1xi2…xir r≥ 2.
Надамо значення xi3=….=xi1=1, а всім змінним xj які не входять у кон. k, надамо значення xj=0. Підстановка цих констант у поліном перетворить кон. k на xi1, xi2, а решту кон. – на 0. При цьому функція f набере вигляду ϕ (xi1, xi2)=xi1xi2+α xi1+β xi2 +γ, де α, β, γ – коефіцієнти, що дорівнюють 0 чи 1залежно від конкретної функції f(xn).