Курс: Теорія інформації та кодування
Тема: двійковий-ортогональної системи Базисні функції
Зміст
Введення
1. ФУНКЦІЇ Радемахер
2. Функцій Уолша
3. Перетворень Уолша
4. Дискретне перетворення Уолш
Список літератури
Введення
Широке використання спектрально-частотного представлення процесів при дослідженні сигналів і систем (перетворення Фур'є) пов'язано з тим, що при гармонічних впливах коливання зберігають свою форму при проходженні через лінійні ланцюги (системи) і відрізняються від вхідних тільки амплітудою і фазою. Це властивість використовують ряд методів дослідження систем (наприклад, частотні методи).
Але при реалізації алгоритмів, що використовують перетворення Фур'є на ЕОМ, необхідно виконувати велику кількість операцій множення (мільйони і мільярди), що займає велику кількість машинного часу.
У зв'язку з розвитком засобів обчислювальної техніки і застосування їх для обробки сигналів широко використовуються перетворення, що містять як ортогонального базису кусково-постійні, знакозмінні функції. Ці функції легко реалізуються за допомогою засобів обчислювальної техніки (апаратно або програмно) та їх використання дозволяє звести до мінімуму час машинної обробки (за рахунок виключення операції множення).
До числа таких перетворень можна віднести перетворення Уолша і Хаара, які широко використовуються в галузі управління та зв'язку. В області комп'ютерної техніки ці перетворення використовуються при аналізі і синтезі пристроїв логічного типу, комбінаційних схем особливо використовують великі і надвеликі інтегральні схеми (ВІС і НВІС), що містять сотні тисяч елементів, що виконують різні логічні функції. Перетворення Уолша і Хаара використовують кусково-постійні функції Уолша, Радемахер, та ін, що приймають значення ± 1, або Хаара, що приймають значення ± 1 і 0 на інтервалі визначення [-0,5, 0,5] або [0, 1] .
Всі ці системи взаємопов'язані і кожну з них можна отримати як лінійну комбінацію з іншої (наприклад: система Радемахер-складова частина системи Уолша). Позначення функцій пов'язаних з авторами цих функцій:
Уолша - Walsh - wal (n, Q),
Хаара-Haar-har (l, n, Q),
Радемахер - Rademacher - rad (m, Q),
Адамара - Hadamard - had (h, Q),
Співали - Paley - pal (p, Q).
Всі ці системи функції представляють собою системи двійково-ортогональних базисних функцій.
1. Функції Радемахер
Функції Радемахер можна визначити за формулою:
rad (m, Q) = sign [sin (2 m p Q)], (1)
де 0 £ Q <1 - інтервал визначення; m - номер функції; m = 0, 1, 2, ...
Для m = 0 функція Радемахер rad (0, Q) = 1.
Знакова функція sign (x) визначається співвідношенням
Функції Радемахер це періодичні функції з періодом 1, т. е.
rad (m, Q) = rad (m, Q +1).
Перші чотири функції Радемахер показані на рис. 1.
1
0 rad (0, Q)
-1
1
0 rad (1, Q)
-1
1
0 rad (2, Q)
-1
1 rad (3, Q)
0
-1
Q
0 0.51
Рис. 1. Функції Радемахер
Дискретні функції Радемахер визначаються дискретними значеннями Q в точках відліку. Наприклад: Rad (2, Q) = 1, 1, -1, -1, 1, 1, -1, -1.
Функції Радемахер ортогональні, ортонормованих (3) але є непарними, а значить, не утворюють повну систему функцій, оскільки існують і інші функції ортогональні функцій Радемахер (наприклад: rad (m, Q) = sign [cos (2 m p Q )]) тому їх застосування обмежене.
Повними двійково-ортогональними системами базисних функцій є системи функцій Уолша і Хаара.
2. Функції Уолша
Функції Уолша представляють собою повну систему ортогональних, ортонормованих функцій. Позначення: wal (n, Q), де n - номер функції, при цьому: n = 0, 1, ... N-1; N = 2 i; i = 1, 2, ....
Перші 8 функцій Уолша наведено на рис. 2.
1
0 wal (0, Q)
-1
1
0 wal (1, Q)
-1
1
0 wal (2, Q)
-1
1
0 wal (3, Q)
-1
1
0 wal (4, Q)
-1
1 wal (5, Q)
0
-1
1wal (6, Q)
0
-1
1 wal (7, Q)
0
-1
Q
0 0.5 1
Рис. 2. Функції Уолша
Функція Уолша має ранг і порядок. Ранг-число одиниць у двійковому поданні n. Порядок - максимальний з містять одиницю номер розряду двійкового подання. Наприклад, функція wal (5, Q) має ранг-2 а порядок -3 (n = 5 Þ 101).
Функції Уолша мають властивість мультипликативности. Це означає, що твір будь-яких двох функцій Уолша також є функцією Уолша: wal (k, Q) wal (l, Q) = wal (p, Q), де p = k Å l. У зв'язку з можливістю застосування до функцій Уолша логічних операцій, вони широко використовуються в багатоканального зв'язку з поділом за формою (використовується також тимчасове, частотне, фазовий і т. д. поділ), а також апаратурі формування та перетворення сигналів на базі мікропроцесорної техніки.
Функції Уолша можна отримати як добуток функцій РАДЕМА-хера, номер яких відповідає коду Грея номери функції Уолша. Відповідності для перших 8 функцій Уолша наведено в табл. 1.
Таблиця 1
Існують різні способи впорядкування функцій Уолша: за Уолшу (природне), по Пелі, по Адамара. Нумерація функцій Уолша при різних способах упорядкування (n - по Уолшу; p - по Пелі; h - по Адамара) наведена в табл. 2.
При впорядкування по Пелі номер функції визначається, як номер двійкового коду Грея прочитаний, як звичайний двійковий код. Таке впорядкування називається диадических.
При впорядкування по Адамара номер функції визначається, як двійкове представлення номера функції Уолша системи Співали, прочитане в зворотному порядку таке впорядкування називається природним.
Таблиця 2
Як видно з таблиці, різні системи використовують одні й ті ж функції Уолша в різній послідовності, які рівнозначні для подання сигналів, але відрізняються тільки властивості розкладання (наприклад, функції Уолша - Пелі сходяться швидше). При цьому, кожному виду упорядкування відповідають певні формули.
3. Перетворення Уолша
Розглянемо спектральне подання сигналів з використанням базису Уолша. Аналогічно з рядом Фур'є ряд Уолша має вигляд:
де спектр Уолша
Для перевірки правильності розрахунку спектральних коефіцієнтів може бути використано рівність Парсеваля
Якщо обмежитися N членами в розкладанні, то отримаємо усічений ряд Уолша:
де t Î [0, T]; N = T / D t; t = a D t при t ® ¥ a ® ¥, a - зрушення по осі;
Для практичних розрахунків можна використовувати формулу:
де:
r - ранг спектрального коефіцієнта з номером a (число двійкових розрядів числа a в яких є 1).
i - номер подинтервала визначення функції x (t);
При цьому Г i приймає значення ± 1 або 0 залежно від того чи міняє W a (i / N) в точці i / N знак з "+" на "-", c "-" на "+" або знак не змінюється.
Приклад 1. Розкласти функцію x (t) = at в ряд по упорядкованим за Пелі функцій Уолша при N = 8, T = 1, a = 1.
Рішення: Визначимо Ф (t):
Визначимо спектральні коефіцієнти з урахуванням функцій Уолша упорядкованим за Пелі за формулою (7)
C 0 = aT / 2;
C 1 =-aT / 2 + 0 +0 + 0 +2 (aT / 4) + 0 + 0 + 0 =-aT / 4;
C 2 =-aT / 2 + 0 + 4aT/64) + 0 - 16aT/64 + 0 +36 aT/64 +0 =- aT / 8;
C 3 = aT / 2 + 0 + 4aT/64) + 0 + 0 + 0 - 36aT/64 +0 = 0;
C 4 =- aT / 2 + aT/64 - 4aT/64 + 9aT/64 - 16aT/64 + 25aT/64 -
- 36aT/64 + 49aT/64 =- aT/16;
C 5 = C 6 = C 7 = 0.
Ряд Уолша - Пелі має вигляд:
Апроксимація функції x (t) = at при а = 1 і t = 1 отриманим поруч наведена на рис. 3.
X
1
0 1 t
Рис. 3. Апроксимація функції x (t) = at поруч Уолша - Пелі
4. Дискретне перетворення Уолша
Дискретне перетворення Уолша (ДПУ) проводиться при використанні дискретних функцій Уолша W a (i / N) Þ Wal (n, Q) і виконується над гратчастими сигналами x (i), при цьому число відліків N повинне бути двійково-раціональним, тобто . N = 2 n, де n = 1, 2, ... , I - визначає номер точки дискретного інтервалу визначення a = 0, 1 ,..., N-1.
Формули дискретного ряду Уолша мають вигляд:
де дискретний спектр Уолша
Для перевірки правильності розрахунку спектральних коефіцієнтів може бути використано рівність Парсеваля:
Графік дискретної функції Уолша, упорядкованих за Співали наведено на рис.
W 0
0 1 2 3 4 5 6 7i
W 1
W 2
W 3
W 4
W 5
W 6
W 7
Рис. 4 Графік дискретної функції Уолша
Для прискорення дискретних перетворень Уолша використовуються алгоритми швидкого перетворення Уолша (БПУ) аналогічного ШПФ.
БПУ також проводиться проріджуванням за часом і частоті.
Застосування перетворень Уолша. Перетворення Уолша знаходять широке застосування при:
- Побудові цифрових фільтрів;
- Дослідженні систем автоматичного управління (моделюванні, оптимізації, ідентифікації і т. д.);
- Формуванні сигналів;
- Аналізі та синтезі логічних пристроїв (в теорії цифрових автоматів).
Приклад 2. Знайти спектр Уолша - Пелі для дискретного сигналу
x (i) = i, N = 8, i = 0, 1, ..., 7.
Використовуючи формулу для C a при N = 8, у відповідності з графіком дискретної функції Уолша, наведеної на рис. 4, можна знайти спектр Уолша (таб. 3).
Таблиця 3
Список літератури
1. Коганов А.В. Векторні міри складності, ентропії, інформації. "Математика. Комп'ютер. Освіта ". Вип. 7, ч. 2, "Прогрес-Традиція", М., 2000, с. 540 - 546
2. Гольдштейн А.Л. Теорія прийняття рішень. Завдання і методи дослідження операцій і прийняття рішень: Учеб. посібник для вузів. - Перм: Вид-во ПДТУ, 2004.-360 с.
3. Абдулгамідов А.Р., "Про системи Хаара, Радемахер і Уолша функцій багатьох змінних", Функціональний аналіз і теорія функцій. 6, Учений. зап. Казан. держ. ун-ту, 129, № 3, Вид-во Казанського ун-та, Казань, 1969, 53-59
4. Малоземов В.М., Машарскій С.М. Основи дискретного гармонійного аналізу. Частина друга. СПб.: НІІММ, 2003. 100 с.
5. Львович А.А., Кузьмін Б.Д. Аналітичний вираз для спектрів функцій Уолша / / Радіотехніка. 1980. Т. 35. № 1. С. 33-39.
6. Зеленков А.В. Швидке перетворення спектру сигналу з базису Уолша в базис дискретних експоненціальних функцій / / Радіотехніка та електроніка. 1977. Т. 27. № 3. С. 552-565.
7. Пойда В.М. Спектральний аналіз в дискретних ортогональних базисах. Мінськ: Наука і техніка, 1978. 136 с.
Тема: двійковий-ортогональної системи Базисні функції
Зміст
Введення
1. ФУНКЦІЇ Радемахер
2. Функцій Уолша
3. Перетворень Уолша
4. Дискретне перетворення Уолш
Список літератури
Введення
Широке використання спектрально-частотного представлення процесів при дослідженні сигналів і систем (перетворення Фур'є) пов'язано з тим, що при гармонічних впливах коливання зберігають свою форму при проходженні через лінійні ланцюги (системи) і відрізняються від вхідних тільки амплітудою і фазою. Це властивість використовують ряд методів дослідження систем (наприклад, частотні методи).
Але при реалізації алгоритмів, що використовують перетворення Фур'є на ЕОМ, необхідно виконувати велику кількість операцій множення (мільйони і мільярди), що займає велику кількість машинного часу.
У зв'язку з розвитком засобів обчислювальної техніки і застосування їх для обробки сигналів широко використовуються перетворення, що містять як ортогонального базису кусково-постійні, знакозмінні функції. Ці функції легко реалізуються за допомогою засобів обчислювальної техніки (апаратно або програмно) та їх використання дозволяє звести до мінімуму час машинної обробки (за рахунок виключення операції множення).
До числа таких перетворень можна віднести перетворення Уолша і Хаара, які широко використовуються в галузі управління та зв'язку. В області комп'ютерної техніки ці перетворення використовуються при аналізі і синтезі пристроїв логічного типу, комбінаційних схем особливо використовують великі і надвеликі інтегральні схеми (ВІС і НВІС), що містять сотні тисяч елементів, що виконують різні логічні функції. Перетворення Уолша і Хаара використовують кусково-постійні функції Уолша, Радемахер, та ін, що приймають значення ± 1, або Хаара, що приймають значення ± 1 і 0 на інтервалі визначення [-0,5, 0,5] або [0, 1] .
Всі ці системи взаємопов'язані і кожну з них можна отримати як лінійну комбінацію з іншої (наприклад: система Радемахер-складова частина системи Уолша). Позначення функцій пов'язаних з авторами цих функцій:
Уолша - Walsh - wal (n, Q),
Хаара-Haar-har (l, n, Q),
Радемахер - Rademacher - rad (m, Q),
Адамара - Hadamard - had (h, Q),
Співали - Paley - pal (p, Q).
Всі ці системи функції представляють собою системи двійково-ортогональних базисних функцій.
1. Функції Радемахер
Функції Радемахер можна визначити за формулою:
rad (m, Q) = sign [sin (2 m p Q)], (1)
де 0 £ Q <1 - інтервал визначення; m - номер функції; m = 0, 1, 2, ...
Для m = 0 функція Радемахер rad (0, Q) = 1.
Знакова функція sign (x) визначається співвідношенням
Функції Радемахер це періодичні функції з періодом 1, т. е.
rad (m, Q) = rad (m, Q +1).
Перші чотири функції Радемахер показані на рис. 1.
1
0 rad (0, Q)
-1
1
0 rad (1, Q)
-1
1
0 rad (2, Q)
-1
1 rad (3, Q)
0
-1
Q
0 0.51
Рис. 1. Функції Радемахер
Дискретні функції Радемахер визначаються дискретними значеннями Q в точках відліку. Наприклад: Rad (2, Q) = 1, 1, -1, -1, 1, 1, -1, -1.
Функції Радемахер ортогональні, ортонормованих (3) але є непарними, а значить, не утворюють повну систему функцій, оскільки існують і інші функції ортогональні функцій Радемахер (наприклад: rad (m, Q) = sign [cos (2 m p Q )]) тому їх застосування обмежене.
Повними двійково-ортогональними системами базисних функцій є системи функцій Уолша і Хаара.
2. Функції Уолша
Функції Уолша представляють собою повну систему ортогональних, ортонормованих функцій. Позначення: wal (n, Q), де n - номер функції, при цьому: n = 0, 1, ... N-1; N = 2 i; i = 1, 2, ....
Перші 8 функцій Уолша наведено на рис. 2.
0 wal (0, Q)
-1
1
0 wal (1, Q)
-1
1
0 wal (2, Q)
-1
1
0 wal (3, Q)
-1
1
0 wal (4, Q)
-1
1 wal (5, Q)
0
-1
1wal (6, Q)
0
-1
1 wal (7, Q)
0
-1
Q
0 0.5 1
Рис. 2. Функції Уолша
Функція Уолша має ранг і порядок. Ранг-число одиниць у двійковому поданні n. Порядок - максимальний з містять одиницю номер розряду двійкового подання. Наприклад, функція wal (5, Q) має ранг-2 а порядок -3 (n = 5 Þ 101).
Функції Уолша мають властивість мультипликативности. Це означає, що твір будь-яких двох функцій Уолша також є функцією Уолша: wal (k, Q) wal (l, Q) = wal (p, Q), де p = k Å l. У зв'язку з можливістю застосування до функцій Уолша логічних операцій, вони широко використовуються в багатоканального зв'язку з поділом за формою (використовується також тимчасове, частотне, фазовий і т. д. поділ), а також апаратурі формування та перетворення сигналів на базі мікропроцесорної техніки.
Функції Уолша можна отримати як добуток функцій РАДЕМА-хера, номер яких відповідає коду Грея номери функції Уолша. Відповідності для перших 8 функцій Уолша наведено в табл. 1.
Таблиця 1
| N | Двійковий код n | Код Грея | Співвідношення |
| 0 | 000 | 000 | wal (0, Q) = 1 |
| 1 | 001 | 001 | wal (1, Q) = rad (1, Q) |
| 2 | 010 | 011 | wal (2, Q) = rad (1, Q) × rad (2, Q) |
| 3 | 011 | 010 | wal (3, Q) = rad (2, Q) |
| 4 | 100 | 110 | wal (4, Q) = rad (2, Q) × rad (3, Q) |
| 5 | 101 | 111 | wal (5, Q) = rad (1, Q) × rad (2, Q) × rad (3, Q) |
| 6 | 110 | 101 | wal (6, Q) = rad (1, Q) × rad (3, Q) |
| 7 | 111 | 100 | wal (7, Q) = rad (3, Q) |
Існують різні способи впорядкування функцій Уолша: за Уолшу (природне), по Пелі, по Адамара. Нумерація функцій Уолша при різних способах упорядкування (n - по Уолшу; p - по Пелі; h - по Адамара) наведена в табл. 2.
При впорядкування по Пелі номер функції визначається, як номер двійкового коду Грея прочитаний, як звичайний двійковий код. Таке впорядкування називається диадических.
При впорядкування по Адамара номер функції визначається, як двійкове представлення номера функції Уолша системи Співали, прочитане в зворотному порядку таке впорядкування називається природним.
Таблиця 2
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| p | 0 | 1 | 3 | 2 | 6 | 7 | 5 | 4 |
| h | 0 | 4 | 6 | 2 | 3 | 7 | 5 | 1 |
3. Перетворення Уолша
Розглянемо спектральне подання сигналів з використанням базису Уолша. Аналогічно з рядом Фур'є ряд Уолша має вигляд:
де спектр Уолша
Для перевірки правильності розрахунку спектральних коефіцієнтів може бути використано рівність Парсеваля
Якщо обмежитися N членами в розкладанні, то отримаємо усічений ряд Уолша:
де t Î [0, T]; N = T / D t; t = a D t при t ® ¥ a ® ¥, a - зрушення по осі;
Для практичних розрахунків можна використовувати формулу:
де:
r - ранг спектрального коефіцієнта з номером a (число двійкових розрядів числа a в яких є 1).
i - номер подинтервала визначення функції x (t);
При цьому Г i приймає значення ± 1 або 0 залежно від того чи міняє W a (i / N) в точці i / N знак з "+" на "-", c "-" на "+" або знак не змінюється.
Приклад 1. Розкласти функцію x (t) = at в ряд по упорядкованим за Пелі функцій Уолша при N = 8, T = 1, a = 1.
Рішення: Визначимо Ф (t):
Визначимо спектральні коефіцієнти з урахуванням функцій Уолша упорядкованим за Пелі за формулою (7)
C 0 = aT / 2;
C 1 =-aT / 2 + 0 +0 + 0 +2 (aT / 4) + 0 + 0 + 0 =-aT / 4;
C 2 =-aT / 2 + 0 + 4aT/64) + 0 - 16aT/64 + 0 +36 aT/64 +0 =- aT / 8;
C 3 = aT / 2 + 0 + 4aT/64) + 0 + 0 + 0 - 36aT/64 +0 = 0;
C 4 =- aT / 2 + aT/64 - 4aT/64 + 9aT/64 - 16aT/64 + 25aT/64 -
- 36aT/64 + 49aT/64 =- aT/16;
C 5 = C 6 = C 7 = 0.
Ряд Уолша - Пелі має вигляд:
Апроксимація функції x (t) = at при а = 1 і t = 1 отриманим поруч наведена на рис. 3.
X
0 1 t
Рис. 3. Апроксимація функції x (t) = at поруч Уолша - Пелі
4. Дискретне перетворення Уолша
Дискретне перетворення Уолша (ДПУ) проводиться при використанні дискретних функцій Уолша W a (i / N) Þ Wal (n, Q) і виконується над гратчастими сигналами x (i), при цьому число відліків N повинне бути двійково-раціональним, тобто . N = 2 n, де n = 1, 2, ... , I - визначає номер точки дискретного інтервалу визначення a = 0, 1 ,..., N-1.
Формули дискретного ряду Уолша мають вигляд:
де дискретний спектр Уолша
Для перевірки правильності розрахунку спектральних коефіцієнтів може бути використано рівність Парсеваля:
Графік дискретної функції Уолша, упорядкованих за Співали наведено на рис.
W 7
Рис. 4 Графік дискретної функції Уолша
Для прискорення дискретних перетворень Уолша використовуються алгоритми швидкого перетворення Уолша (БПУ) аналогічного ШПФ.
БПУ також проводиться проріджуванням за часом і частоті.
Застосування перетворень Уолша. Перетворення Уолша знаходять широке застосування при:
- Побудові цифрових фільтрів;
- Дослідженні систем автоматичного управління (моделюванні, оптимізації, ідентифікації і т. д.);
- Формуванні сигналів;
- Аналізі та синтезі логічних пристроїв (в теорії цифрових автоматів).
Приклад 2. Знайти спектр Уолша - Пелі для дискретного сигналу
x (i) = i, N = 8, i = 0, 1, ..., 7.
Використовуючи формулу для C a при N = 8, у відповідності з графіком дискретної функції Уолша, наведеної на рис. 4, можна знайти спектр Уолша (таб. 3).
Таблиця 3
| Значення функцій і спектральних коеф. при значеннях індексів i і a | |||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| x (i) = i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| C a | 3,5 | -2 | -1 | 0 | -0,5 | 0 | 0 | 0 | |
Список літератури
1. Коганов А.В. Векторні міри складності, ентропії, інформації. "Математика. Комп'ютер. Освіта ". Вип. 7, ч. 2, "Прогрес-Традиція", М., 2000, с. 540 - 546
2. Гольдштейн А.Л. Теорія прийняття рішень. Завдання і методи дослідження операцій і прийняття рішень: Учеб. посібник для вузів. - Перм: Вид-во ПДТУ, 2004.-360 с.
3. Абдулгамідов А.Р., "Про системи Хаара, Радемахер і Уолша функцій багатьох змінних", Функціональний аналіз і теорія функцій. 6, Учений. зап. Казан. держ. ун-ту, 129, № 3, Вид-во Казанського ун-та, Казань, 1969, 53-59
4. Малоземов В.М., Машарскій С.М. Основи дискретного гармонійного аналізу. Частина друга. СПб.: НІІММ, 2003. 100 с.
5. Львович А.А., Кузьмін Б.Д. Аналітичний вираз для спектрів функцій Уолша / / Радіотехніка. 1980. Т. 35. № 1. С. 33-39.
6. Зеленков А.В. Швидке перетворення спектру сигналу з базису Уолша в базис дискретних експоненціальних функцій / / Радіотехніка та електроніка. 1977. Т. 27. № 3. С. 552-565.
7. Пойда В.М. Спектральний аналіз в дискретних ортогональних базисах. Мінськ: Наука і техніка, 1978. 136 с.