Функції Уолша періодична якщо. Багатостанційний доступ з кодовим поділом і мережі CDMA. Питання для самостійної підготовки
Курс: Теорія інформації та кодування
Тема: двійкову-ортогональній системі БАЗИСНИХ ФУНКЦІЙ
Вступ
1. Функції Радемахер
2. функцій Уолша
3. ПЕРЕТВОРЕННЯ Уолш
4. дискретного перетворення Уолша
Список літератури
Вступ
Широке використання спектрально-частотного представлення процесів при дослідженні сигналів і систем (перетворення Фур'є) пов'язано з тим, що при гармонійних впливах коливання зберігають свою форму при проходженні через лінійні ланцюги (системи) і відрізняються від вхідних тільки амплітудою і фазою. Це властивість використовують ряд методів дослідження систем (наприклад, частотні методи).
Але при реалізації алгоритмів, що використовують перетворення Фур'є на ЕОМ, необхідно виконувати велика кількістьоперацій множення (мільйони і мільярди), що займає велику кількість машинного часу.
У зв'язку з розвитком засобів обчислювальної техніки і застосування їх для обробки сигналів широко використовуються перетворення, що містять в якості ортогонального базису кусочно-постійні, знакозмінні функції. Ці функції легко реалізуються за допомогою засобів обчислювальної техніки (апаратно або програмно) і їх використання дозволяє звести до мінімуму час машинної обробки (за рахунок виключення операції множення).
До числа таких перетворень можна віднести перетворення Уолша і Хаара, які широко використовуються в галузі управління та зв'язку. В області комп'ютерної техніки ці перетворення використовуються при аналізі і синтезі пристроїв логічного типу, комбінаційних схем особливо використовують великі і надвеликі інтегральні схеми (ВІС і НВІС), що містять сотні тисяч елементів, що виконують різні логічні функції. Перетворення Уолша і Хаара використовують кусково-постійні функції Уолша, Радемахера, і ін., Що приймають значення ± 1, або Хаара, що приймають значення ± 1 і 0 на інтервалі визначення [-0,5, 0,5] або.
Всі ці системи взаємопов'язані і кожну з них можна отримати як лінійну комбінацію з іншого (наприклад: система Радемахера- складова частинасистеми Уолша). Позначення функцій пов'язаних з авторами цих функцій:
Уолша - 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, (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. Функції Радемахера
Дискретні функції Радемахера визначаються дискретними значеннями Qв точках відліку. наприклад: Rad (2, Q) = 1, 1, -1, -1, 1, 1, -1, -1.
Функції Радемахера ортогональні, ортонормированном (3) але є непарними, а значить, не утворюють повну систему функцій, т. К. Існують і інші функції ортогональні функцій Радемахера (наприклад: rad (m, Q) = sign)тому їх застосування обмежене.
(3)
Повними двійковій-ортогональними системами базисних функцій є системи функцій Уолша і Хаара.
2. Функції Уолша
Функції Уолша є повною систему ортогональних, ортонормованих функцій. позначення: wal (n, Q), де n- номер функції, при цьому: n = 0, 1, ... N-1; N = 2 i; i = 1, 2, ....
Перші 8 функцій Уолша наведені на рис. 2.
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 | двійковий | співвідношення | |
| 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. Перетворення Уолша
Розглянемо спектральне подання сигналів з використанням базису Уолша. Аналогічно з рядом Фур'є ряд Уолша має вигляд:
, (4)
де спектр Уолша
. (5)
Для перевірки правильності розрахунку спектральних коефіцієнтів може бути використано рівність Парсеваля
.
якщо обмежитися Nчленами в розкладанні, то отримаємо усічений ряд Уолша:
,(6)
де tÎ ; N = T /Dt; t =a Dtпри t® ¥ a® ¥ , a- зрушення по осі;
wal (n, Q)після перетворення аргументів.
Для практичних розрахунків можна використовувати формулу:
.
де: 
; (7)
r- ранг спектрального коефіцієнта з номером a (число двійкових розрядів числа a в яких є 1).
i- номер подинтервала визначення функції x (t);
при цьому Г iприймає значення ± 1 або 0 в залежності від того чи міняє Wa(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 + 36aT / 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.
Мал. 3. Апроксимація функції x (t) = atпоруч Уолша - Пелі
4. Дискретне перетворення Уолша
Дискретне перетворення Уолша (ДПУ) проводиться при використанні дискретних функцій Уолша Wa(I / N)Þ Wal (n, Q)і виконується над гратчастими сигналами x (i), При цьому число відліків Nмає бути двійковій -раціонально, т. е. N = 2 n, де n = 1, 2, ..., i- визначає номер точки дискретного інтервалу визначення a= 0, 1, ..., N-1.
Формули дискретного ряду Уолша мають вигляд:
,(9)
де дискретний спектр Уолша
. (10)
Для перевірки правильності розрахунку спектральних коефіцієнтів може бути використано рівність Парсеваля:
(11)
Графік дискретної функції Уолша, упорядкованих по Співали наведено на рис.
М. Ю. Васильєва, Ф. В. Коннов, І. І. Ісмагілов
ДОСЛІДЖЕННЯ НОВИХ впорядкованості ДИСКРЕТНИХ функцій Уолша
ТА ЇХ ЗАСТОСУВАННЯ В АВТОМАТИЗОВАНИХ СИСТЕМАХ УПРАВЛІННЯ
Ключові слова: Дискретні функцій Уолша, разностно-впорядкована система, обробка та передача даних,
автоматизовані системи управління.
Пропонується новий метод упорядкування систем дискретних функцій Уолша, представлені властивості нових упорядкування, розглянута можливість застосування синтезованих упорядкування дискретних функцій Уолша в автоматизованих системах управління.
Keywords: discrete Walsh functions, difference-ordered system, processing and transfer data, automated control systems.
A new method of ordering systems of discrete Walsh functions, shows the properties of new orderings, possibility of application of the synthesized discrete orderings of Walsh functions in automatic control systems.
Вступ
Повсюдне розвиток інформаційних мереж і систем, включаючи автоматизовані системи управління (АСУ) різних рівнів, обчислювальні мережі, системи автоматизованого проектування, збору і обробки даних, автоматизації експерименту, масового
обслуговування, телеметричні комплекси, інформаційно-довідкові системи, мережі зв'язку та ін., привело до істотного зростання інформаційних потоків між територіально розподіленими джерелами і одержувачами повідомлень і пильнувати про все зростаючих обсягів інформації різного видув базах даних. Для підвищення ефективності використання комунікаційних та інформаційно-обчислювальних ресурсів зазначених систем застосовуються різні методи і засоби.
Серед них досить важливу роль відіграють методи скорочення надмірності даних, що забезпечують стиснення обсягів переданої або запам'ятовувати інформацію. Це дозволяє значно розвантажити канали зв'язку і системи обробки і зберігання даних за рахунок виключення непотрібних або дублюються відомостей, що еквівалентно підвищенню пропускних спроможностей систем збору, передачі та обробки даних або збільшення ємності запам'ятовуючих пристроїв.
серед існуючих методівскорочення надмірності даних особливе місце займають методи стиснення, які застосовують різні математичні перетворення. Найбільш часто вживаними при скороченні і передачі даних в автоматизованих системах управління виробництвом і технологічними процесами є
перетворення Фур'є, Уолша і Хаара. Кожне з яких має ряд переваг, наприклад, застосування перетворень Уолша і Хаара дозволяє значно спростити і прискорити обробку інформації.
Широке використання ряду перетворень в прикладних задачах, полягає в можливості їх обчислення за допомогою швидких алгоритмів, які мають значно меншою
обчислювальною складністю в порівнянні з класичними алгоритмами перетворень.
У статті розглядається комплекс питань, пов'язаних із застосуванням перетворень Уолша: наводиться побудову нових упорядкування функцій Уолша, дослідження їх властивостей, розглядається застосування функцій Уолша при виконанні перетворень.
Короткий огляд дискретних функцій Уолша і їх упорядкування
Ортонормированном, повна система прямокутних функцій була введена Уолш. На відміну від тригонометричних гармонік, за якими функція розкладається в класичний ряд Фур'є, функції Уолша є прямокутні хвилі, які в багатьох задачах обробки сигналів переважно
синусоїдальних хвиль. Більшою мірою це пов'язано з найпростішим видомфункцій Уолша, кожна з яких бере всього два значення (+1 і -1), що набагато спрощує їх реалізації на ЕОМ.
Дискретні перетворення Уолша (ДПУ) грунтуються на дискретних функціях Уолша (ДФУ), які утворюються рівномірними вибірками безперервних функцій Уолша. Загальна кількість звітів в ДФУ має бути N = 2п, де п - будь-яке ціле позитивне число.
У цифровій обробці сигналів використовуються перетворення в різних
впорядковану систему ДФУ. До найбільш відомих впорядкованості в практиці обробки сигналів ДФУ в системі відносяться наступні: секвентівное впорядкування (Уолша-Качмажа); диадического
впорядкування (Уолша-Пелі); впорядкування в
відповідно до розташування рядків в матриці
Адамара (Уолша-Адамара).
Беручи за основу системи безперервних функцій Уолша з різним порядком проходження функції, отримуємо відповідно матриці ДПУК (дискретні перетворення Уолша-Качмажа), ДПУП (дискретні перетворення Уолша-Пелі) і ДПУА (дискретні перетворення Уолша-Адамара).
ДФУ можна описати аналітично, висловивши їх через дискретні функції Радемахера. нехай
j = £ ік2 - номер функції в системі, а і = £ ік2 к = 0 до к = 0 До
Номер відліку, тоді згадані вище матриці перетворень мають вигляд:
матриця ДПУК
матриця ДПУП
(- 1) до £ 0ік ^ до (і)
(- 1) до £ 0ікіп-к
матриця ДПУА
(- 1) до £ 0ікік
де -т = - нормувальний коефіцієнт; л / І
Рош = Ь = ^ п-к + 1 ф-! П-к 'к = 1,2 п,
де ® - знак додавання за модулем 2.
Відзначимо, що виконавчі комбінації виду
Ч0 (-). Ч1С -) ... Рп (-) або Рп (-), Рп-1 (-), -, Р0 (-)
називають відповідно кодом Грея, або інверсним кодом Грея числа -
Для матриць Уолша-Адамара справедливо наступне розбиття на подматріци вид
Реккурентное формулу (4) можна також висловити у вигляді кронекеровского твори матриць:
НАР к = НАР 0 НАР до 1. 2к 2 2 к-1
Матриці (1-2) можна отримати переупорядочение рядків матриці Уолша-Адамара, так як між впорядкованістю дискретної системи Уолша розмірності N існують певні залежності, які в матричної формі мають такий вигляд:
РАЬм = Б ^ НАР ^
WALN = Б ^ РАІ.
матриця двійковій-інверсних перестановок;
Матриця перестановки по зворотному двійкового коду Грея.
Наведемо в короткій формі основні властивості ДФУ. Для ДФУ справедливі такі властивості, притаманні неперервним функціям Уолша:
1. Ортогональность. функції Уолша
ортогональні на інтервалі, і навпаки.
6. мультиплікативний. Твір двох функцій Уолша одно нової функції Уолша з цієї ж системи.
7. Порядок і ранг функцій Уолша. Функції Уолша зручно характеризувати двома параметрами, пов'язаними з двійковим поданням їх номерів. Перший з них визначає максимальний номер ненульового довічного розряду числа - і називається порядком р; другий - ранг функції Уолша г - показує число двійкових розрядів, в яких число Ш має одиниці. Номер функції Уолша г-го рангу умовно позначають у вигляді - (г) і записують в десятковій системі числення:
де ^ до (к = 1,2, ..., г) - номер розряду двійкового коду Ш, що містить одиницю. Область зміни всіх ^ до в (8) повинна задовольняти наступній системі рівності:
М1 = 0,1, ..., п - г -1;
М 2 = І + 1,. ., П _ г;
Для рангу і порядку функцій Уолша справедливо наступне властивість: ранг
твори функцій Уолша не перевищує суми їх рангів; порядок твори не перевищує максимальний з порядків співмножників. Справедливість цієї властивості випливає з властивостей підсумовування по модулю 2.
В системи ДФУ віднесені до класу моноразностних дискретних ортогональних базисів. При вивченні ряду властивостей базисів цього класу вельми корисні їх параметри і характеристики, детально розглянуті в даній роботі. Підхід до їх введення заснований на тому, що будь-який коефіцієнт перетворення в розглянутому класі базисів може бути представлений у вигляді зваженої суми кінцевих різниць відповідних порядків
преутвореного вектора £
р (і) = £ і = 0, М -1,
де Р (I) - I -ий коефіцієнт перетворення; Дк-оператор кінцевої різниці к-го порядку;
и (|, -) = и (|, И-1 - ^ -Ш) - 1-я вагова функція; d | -
деяке ціле число.
В цьому випадку базисні вектори моноразностних дискретних базисів формуються послідовностями операторів кінцевої різниці відповідних порядків. Надалі в роботі будемо оперувати параметром, названим диференціальним порядком базисної функції d |,
під яким будемо мати на увазі порядок операторів кінцевої різниці, які формують цю функцію.
Відзначимо, що диференційний порядок конкретної функції Уолша пов'язаний з її структурними властивостями і не залежить від місця розташування в системі, тобто від упорядкування базисних функцій.
Важливими є також такі властивості:
8. Для систем ДФУ, упорядкованих по Адамара і Пелі, диференціальні порядки функцій рівні
отже,
їх рангах: кількість
С = гкі, і = 0, М-1.
(К = 0, п) чк
диференціального порядку дорівнює величині Сп-число поєднань з п по к.
9. Відоме властивість розкладів дискретних статечних поліномів по системі Уолша-Пелі, яке можна переформулювати наступним
чином: спектр дискретного полінома к-ой (к = 0, п) ступеня містить компоненти, що відповідають базисним функціям не вище к-ого
диференціального порядку. Відзначимо, що аналогічне твердження буде справедливо і для розкладів по системі Уолша-Адамара.
10. Спектральні коефіцієнти сигналів, досить добре описуються дискретними статечними полиномами невисоких порядків, в межах груп, відповідних базисних функціях Уолша-Пелі одного диференціального порядку, зменшуються за абсолютною величиною зі зростанням їх порядкових номерів.
Синтез разностно-впорядкованої системи дискретних функцій Уолша
Пропонований метод упорядкування систем
ДФУ розмірності N = 2п полягає в наступному. Будується розбиття множини порядкових номерів функцій Уолша вихідної системи I = (0,1 N -1)
на (п +1) підмножин, кожне з яких включає номери функцій з однаковими диференціальними порядками.
| (0) = (0), і = 0,
І (і) = (2М + 2М2 + ... + 2М: м1 = 0, п - І,
^ 2 - + 1, п - I +1, ... ^ | - ^ | 1 + 1, п - 1), I - 1, п - 1,
1 (п) - (2п - 1), I - п.
Потім сформовані підмножини розташовують в порядку збільшення диференціальних порядків відповідних функцій, тобто в результаті отримуємо безліч Л - ЦЛ ^ .- ЛП), для якого
справедливі наступні співвідношення: Л п і: - 0 і Л - Сп, 1 - 0, п.
Очевидно, що безліч і визначає перестановку функцій Уолша в системі | 0 1 ... N - 1]
Отримана в результаті цієї перестановки система ДФУ буде характеризуватися тим, що функції в ній розташовуються групами в порядку зростання їх диференціальних порядків. З цієї причини назвемо цю систему ДФУ разностноупорядоченной.
Для вектора перестановною
послідовності будемо дотримуватися
позначення Рп = (Р0, Р1 .... Рм-1), де
р | - ш |, 1 - 0 ^ -1. Перестановку з використанням
цього вектора назвемо перестановкою з диференціальних порядків базисних функцій (коротко Б-перестановкою).
Розглянемо впорядкування системи Уолша-Пелі з використанням запропонованого методу. Аналіз диференціальних порядків функцій Уолша-Пелі показав, що вектор Рп може бути представлений у вигляді об'єднання ряду підвектора:
Рп - (РП0), рп1), рп2),., РПП)), (13)
Рп, к = 1, п-1, - підвектора,
рекурентними співвідношеннями: Рі (к) = | (2і -1), і = до,
Рі (і) = (2і - 1), і = 1, п;
визначаються
^ (Р-к), 2і-1 + Р, - 1)), і = до +1, п,
Вектори Рп розмірності N - 2п, п -1,5, відповідні перестановки
послідовностям, представлені в табл. 1.
Зверху підкреслені групи
коефіцієнтів парних, а знизу - непарних диференціальних порядків.
Таблиця 1 - Вектори значень перестановною послідовності
п Вектор Рп
3 {0,1,2,4,3,5,6,7}
4 {0,1,2,4,8,3,5,6,9,10,12,7,11,13,14,15}
5 {0,1,2,4,8,16,3,5,6,9,10,12,17,18,20,24, 7,11,13,14,19,21,22,25,26,28,15,23,27,29,30,31}
З урахуванням введеного вектора значень перестановною послідовності разностно-
впорядковану систему ДФУ (РЦ ^ 0)) (= о можна описати так:
pldN (i) = palN (pj), i = 0, N
де РАІ ^ (і) - і-я функція Уолша-Пелі.
S ^ PAL ^, (І6)
Матриця D-перестановок,
елементи якої формуються так:
[О, в інших випадках.
Слід зазначити, що представлений вище впорядкування системи ДФУ отримано на основі системи Уолша-Пелі. Вибір в якості базисної системи Уолша-Пелі обумовлений легкістю
отримання аналітичного опису для перестановною послідовності і матричного співвідношення, що формує запропоноване впорядкування системи ДФУ.
Різні варіанти разностно-
упорядкованих систем можуть бути отримані при виборі в якості базисної інших систем Уолша. Аналіз диференціальних порядків функцій Уолша-Адамара і Уолша-Пелі показав, що вектор значень перестановною послідовності Рр при виборі в якості опорних матриць Уолша-Адамара також може бути представлений у вигляді об'єднання ряду підвектора (13-14) - (табл. 2).
На основі отриманого вектора значень перестановною послідовності разностно-
описати так:
впорядковані системи ДФУ
hddN () = hadN (pj) i = 0, N -1
де hadN (0 - відповідно 1-е функції Уолша-Адамара.
Таблиця 2 - Групи диференціальних порядків систем Уолша-Пелі і Уолша-Адамара при N = 8
j hadn, j PALn, j di pj pldn, j di
Про ТОВ ТОВ Про Про ТОВ Про
І ООІ ІОО І 4 ІОО І
2 ОІО ОІО І 2 ОІО І
3 ОІІ ІІО 2 І ООІ І
4 ІОО ООІ І 6 ІІО 2
З ІОІ ІОІ 2 З ІОІ 2
6 ІІО ОІІ 2 3 ОІІ 2
7 ІІІ ІІІ 3 7 ІІІ 3
Матрична запис для введеної системи ДФУ має наступний вигляд:
Наприклад, явний вигляд матриці HDDN для N = 2 має наступний вигляд:
11 1 1 1 1 1 1 0
1 -1 1 -1 1 -1 1 -1 1
11 -1 -1 1 1 -1 1
1 1 1 1 -1 -1 -1 1
1 -1 -1 1 1 -1 1 2
1 -1 1 -1 -1 1 1 2
1 -1 -1 1 1 -1 1 2
1 -1 -1 1 -1 1 1 -1 3
диференційний порядок базисної функції, розташованої у відповідному рядку матриці.
Точна оцінка М загального числа разностноупорядоченних систем ДФУ за умови, що групи базисних функцій будуть розташовуватися в порядку підвищення їх диференціальних порядків, може бути визначена за такою формулою:
М = П (СП!). (18)
В роботі розглянута можливість отримання матричної записи іншого варіанту разностно-впорядкованої системи ДФУ. При цьому використовується пошарово-кронекеровское
твір матриць.
Зупинимося на питанні нумерації разностно-впорядкованих ДФУ в системі. Тут в ряді випадків зручніше оперувати двухзначной індексацією базисних функцій. Наприклад, для розглянутих в роботі систем ДФУ вона вводиться наступним чином:
pld2n (i) = pld2n (l, j), i = 0, N -1, i = bnl-1 + j, l є (0,1, ..., n) j є (, 1, ... , сп -1).
Очевидно, що індекс l дорівнює диференціального порядку базисного вектора, а індекс j - його порядковому номеру у відповідній групі. Співвідношення, що описує залежність між двома видами індексації, не залежить від варіанту разностноупорядоченной системи ДФУ.
Зауважимо, що матриці PAL ^, і DOWN
збігаються для N = 2,4, а PLD ^ = DOWN для N = 8.
Властивості разностно-впорядкованих систем дискретних функцій Уолша
властивості
окремі введеним впорядкованості
Розглянемо перетворень по систем ДФУ.
1. Для разностно-впорядкованих систем ДФУ
справедливі властивості ДФУ 1-7.
2. Відоме властивість 8 (розкладання дискретних
статечних поліномів по системі Уолша-Пелі і Уолша-Адамара) стосовно до досліджуваних разностно-впорядкованим систем ДФУ можна
сформулювати наступним чином: спектр
дискретного полінома к-ой (к = 0, П) мірою розкладається по базисних функціях не вище к-ої групи.
Розглядається властивість в разі
упорядкування функцій Уолша-Пелі можна записати у вигляді наступного співвідношення:
р (|, |) = 0,1> до, (20)
де Р (і) = £ 10 (, і)
3. Важливим є властивість 9, яке
також справедливо для разностно-впорядкованих систем ДФУ: спектральні коефіцієнти сигналів, досить добре описуються дискретними
статечними полиномами невисоких порядків, в межах груп, відповідних базисних функціях одного диференціального порядку, зменшуються за абсолютною величиною зі зростанням їх порядкових номерів.
Отримані при цих впорядкованості матриці функцій Уолша є несиметричні,
винятком є тривіальні випадки матриць для порядків N = 2, 4.
4. Відзначимо наступне властивість, спектри
дискретних статечних поліномів низьких порядків в базисах разностно-впорядкованих ДФУ
характеризуються більшим ступенем локалізації ненульових компонент в їх початкових ділянках
Проілюструємо характер розподілу ненульових компонент спектрів дискретних статечних поліномів 1 (1) до другої (к = 1,2) ступеня для N = 16 в
базисах різних систем ДФУ.
Попередньо введемо індикаторний вектор спектра Б = (зо ^ ... ^^ -), визначаючи його елементи так
Б | = | 0, р (|) = о, (21)
де Р (1) - ьий коефіцієнт перетворення. Одномірні діскетной статечні поліноми 10) визначаються функціями виду
f (j) = Е аі] ",] = 0, И-1, к є г,
1 = (0,1, ..., м -1).
При виборі моделей сигналів часто обмежуються полиномиальной моделлю малих ступенів (к є г 5). Це обумовлено тим, що нею
може бути ефективно описаний широкий клас реальних сигналів на кінцевих інтервалах.
Формули розрахунку коефіцієнтів перетворення Р (і) одновимірного полиномиального сигналу в матричному вигляді будуть мати такий вигляд:
де - матриця ДПУ в використовуваному впорядкування ДФУ;
1 = | г (|), | = Оти -1) - вектор вихідних даних;
Р = р (1), I = 0 ^ -11 - вектор спектральних
коефіцієнтів, Т - знак транспонування.
Індикаторні вектори спектрів в базисі Уолша-Адамара, Уолша-Качмажа, Уолша-Пелі і разностно-впорядкованих ДФУ для поліномів ступеня к = 1 і к = 2 мають вигляд:
(1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0) - для базису Уолша-Адамара;
(1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1) - для базису Уолша-Качмажа;
(1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0) - для базису Уолша-Пелі;
(1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0) - для базису
разностно-впорядкованих ДФУ.
(1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,0) - для базису Уолша-Адамара;
(1,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1) - для базису Уолша-Качмажа;
(1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,0) - для базису Уолша-Пелі;
(1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0) - для базису
разностно-впорядкованих ДФУ.
Проілюструємо характер розподілу ненульових компонент спектрів дискретних статечних двовимірних поліномів 1 (1,] до другій (к = 1,2) ступеня для N1 * N2 = 8x8 в базисах ДФУ. Двовимірні дискретні статечні поліноми, визначають функціями виду
Ш) = X X араір] а,
де I = 0, ^ -1,] = 0, ^ -1, до е 2 ^ 1,
^ -1 = (о, 1, ^ - 1).
При цьому обмежимося двовимірними поліноміальними моделями низьких ступенів з огляду на те, що вони є основою ряду алгоритмів цифрової обробки сигналів.
Наведемо формули прямого
перетворення двовимірного полиномиального сигналу в векторно-матричної формі:
Р = HNTfHN, (25)
де 1 = (1 (1,]), I = 0, ^ -1,] = 0, ^ -1) - матриця
вихідних даних;
Р = "Р (І), 1 = 0, ^ -1,] = 0 ^ 2 -1) - матриця
спектральних коефіцієнтів.
Індикаторні вектори спектрів для розглянутих випадків при к = 1 показані на рис. 1,
1 I 1 I про I 1 I □ I □ I □ I 1
00000000 1 0 0 0 0 0 0 0
00000000 1 0 0 0 0 0 0 0
Мал. 1 - Індикаторні вектори спектрів при к = 1 в базисі: Уолша-Адамара, Уолша-Качмажа
00000000 00000000 00000000 00000000
Мал. 2 - Індикаторні вектори спектрів при к = 1 в базисі: Уолша-Пелі, разностно-упорядкованих
Індикаторні вектори спектрів для розглянутих випадків при к = 2 показані на рис. 3,
11111110 1110 10 0 0 1110 10 0 0 1 0 0 0 0 0 0 0 1110 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 00000000
Мал. 3 - Індикаторні вектори спектрів при к = 2 в базисі: Уолша-Адамара, Уолша-Качмажа
1 I 1 I 1 I 1 I 1 I 1 I 1 I про
Мал. 4 - Індикаторні вектори спектрів при к = 2 в базисі: Уолша-Пелі, разностно-упорядкованих
З цих прикладів видно, що спектри дискретних статечних поліномів низьких порядків в базисах разностно-впорядкованих ДФУ
характеризуються більшим ступенем локалізації ненульових компонент в їх початкових ділянках. Отримані властивості перетворень по разностноупорядоченним системам ДФУ мають важливе значення для їх додатків в системах управління і системах зв'язку.
1 0 □ 0 0 0 0 0
1 0 0 □ 0 0 □ 0
□ 0 0 □ 0 0 □ 0
Застосування синтезованих упорядкування дискретних функцій Уолша в АСУ
Успішному використанню перетворень Уолша в галузі управління та зв'язку сприяло вивчення наступних питань: властивості функцій Уолша; властивості спектрів Уолша; загальні питання застосування функцій Уолша при виконанні перетворень; алгоритми швидкого перетворення Уолша; обчислення кореляційних функцій і виконання згорток на базі функцій Уолша; застосування функцій Уолша для дослідження випадкових процесів; використання функцій Уолша при побудові цифрових фільтрів.
Завдяки спільним властивостями 1-7 з відомими ДФУ (в упорядкованому Уолша-Качмажа, Уолша-Пелі, Уолща-Адамара) синтезовані разностно-впорядковані
системи ДФУ можуть знайти ефективне застосування в області автоматичного управління технологічними процесами. Наприклад, є актуальним застосування перетворень Уолша при аналізі динаміки лінійних і нелінійних систем, розробці систем оптимального управління, моделюванні процесів, ідентифікації об'єктів, розробці ряду спеціальних пристроїв автоматики.
Практично важливим для АСУ є Предожения X. Хармут використання функцій Уолша для формування сигналів, які передаються по лініях радіозв'язку. Функції Уолша застосовані при розробці багатоканальних систем зв'язку, в яких одночасно передаються різні сигнали по кожному каналу зв'язку. Використання разностно-впорядкованих систем ДФУ (властивість 2) дозволить забезпечити многопотоковую обробку даних, при цьому кожен потік буде включати елементи групи трансформант відповідного
диференціального порядку, що значно прискорити обробку даних.
В даний час для вирішення багатьох завдань в АСУ технологічними процесами і виробництвом застосовується вейвлет
перетворення. Наприклад, в ВАТ "Татнефть" вейвлет-перетворення наспіл для придушення шумів і стиснення масивів даних з глибинних манометрів, або при передачі дінамограмми отриманих з датчиків динамометруванні на диспетчерський пункт. У багатьох випадках недостатня ступінь стиснення даних при виконанні ДПУ стримує широке застосування даних перетворень. Властивість 2 отримане для разностно-впорядкованих систем ДФУ дозволить значно збільшити ступінь стиснення даних і сприяє застосуванню в перерахованих вище задачах.
Однією з важливих задач в АСУ є завдання передачі даних по каналах зв'язку. При цьому широке поширення отримали 8СЛЕЛ-
системи. Відомі також рішення, в яких функції 8СЛЕЛ-системи реалізовані за допомогою інтернет-програмування, в ВАТ «Газ-Сервіс» (Республіка Башкортостан) впроваджені в експлуатацію кілька автоматизованих систем дистанційного моніторингу обладнання газорозподільної мережі. Для передачі даних по мережі ефективне застосування можуть знайти разностно-впорядковані системи ДФУ (властивість 4).
У роботі авторами були запропоновані алгоритми з використанням перетворень Уолша і порівняльний аналіз їх ефективності. Використання в представлених алгоритмах для передачі даних разностно-впорядкованих систем ДФУ дозволить забезпечити послідовну передачу потоків вихідних даних при високій швидкості обробки і передачі даних по мережі.
Отримані властивості нових впорядкованості дискретних функцій Уолша мають важливе значення для їх додатків в системах управління і системах зв'язку. Синтезовані разностно-впорядковані
При вирішенні багатьох завдань аналізу складний сигнал зручно представити у вигляді сукупності елементарних сигналів. На практиці найбільше застосування знайшло уявлення сигналу s (t),заданого на інтервалі, у вигляді лінійної комбінації деяких елементарних функцій (P t (t), / = 0,1,2, ..., званих засадничими
- норма базисної функції.
Подання сигналу в такому вигляді називається узагальненим рядом Фур'є. Часто в якості базисних функцій використовують систему тригонометричних функцій
або систему комплексних експоненційних функцій
Однак у міру розвитку цифрових методів передачі та обробки сигналів в останні рокив якості базисних функцій починають використовувати дискретні ортогональні послідовності у вигляді функцій Радемахера, Уолша, Хаара і ін.
Введемо безрозмірний час 0 = t / Т . функції Радемахераутворюються з синусоїдальних функцій за допомогою співвідношення
Інакше кажучи, функції Радемахера, що приймають значення ± 1, можна трактувати як функції «прямокутного синуса». Графіки перших чотирьох функцій Радемахера мають вигляд, представлений на малюнку 4.12.
Система функцій Радемахера r k(0) є ортонормованій на інтервалі 0
Система функцій Уолшає розширенням системи функцій Радемахера до повної системи і визначається як
де kf- значення j-го розряду в запису числа дов коді Грея. наприклад,
так як 5 => 101 2 => 111 м Графіки перших чотирьох функцій Уолша показані на малюнку 4.13.
Мал. 4.13.
Функції Уолша мають наступні властивості:
- 1. wal k (®) = ± 1.
- 2. | wal k (0)| = 1, 2 = 1.
- 3. Функції Уолша є періодичними wal k (©) = wal k (0 +1).
- 4. Функції Уолша є ортогональними
5. Множення функцій Уолша дає функцію Уолша, але іншого порядку wal k (0) wal n (0) = walj (0), j = до ® n,
wal k (0 2) wal k (0 2) = wal k(0 3), 0 3 = 0j ® 0 2, де © - додавання по модулю два.
У деяких випадках використовують функції Уолша виду
При використанні в якості базисних функцій системи функцій Уолша сигнал можна представити у вигляді
Сукупність коефіцієнтів Уолша-Фур'є (q) або (А до ф к)і сукупність порядкових номерів функцій утворюють спектр сигналу в базисі Уолша, який для стислості іноді називають S-спектром.
Наприклад, сигнал, що представляє собою періодичну послідовність прямокутних імпульсів (рис. 4.14), має S-спектр, який визначається за виразом (4.39).
Мал. 4.14.
прямокутних імпульсів
нехай п = 3, тоді отримаємо S-спектр для даного випадку, показаний на малюнку 4.15.
Мал. 4.15.
Таким чином, на відміну від звичайного частотного спектра S-спектр послідовності прямокутних імпульсів виявляється кінцевим. Слід зазначити, що зрушення імпульсів у часі призводить до зміни структури S- спектра. Зокрема, з'являються нові складові. Наприклад, для послідовності з п = 3 імпульсів, зрушеною на 0 = 1/16, S-спектр має вигляд, як на малюнку 4.16, в той час як при використанні геодезичної системи функцій зрушення в часі змінює тільки фазовий спектр.
У зв'язку з можливістю застосування до функцій Уолша логічних операцій вони знаходять застосування при розробці механізмів формування та перетворення сигналів на базі мікропроцесорної техніки. Сигнали на основі функцій Уолша використовуються в цифрових багатоканальних системах передачі інформації.
Мал. 4.16.
зсунутих на 0 = 1/16
Система функцій Хаараскладається з кусочно-постійних функцій har k(0), що задаються на інтервалі 0
де т- номер старшого ненульового розряду в двійковому поданні числа
до mod2 w - величина допо модулю 2 т,це найменший залишок від ділення числа дона 2 т. Графіки декількох функцій Хаара дані на малюнку 4.17.
Мал. 4.17.
Якщо розглядати спектр сигналу в базисі Хаара, то, як і в разі S- спектра, при зсуві сигналу в часі змінюється структура його спектра.
Функції Хаара знаходять застосування в системах управління і зв'язку, при розробці цифрових фільтрів, при стисненні інформації - це, наприклад, різні методи стиснення чорно-білих фотографій на основі функцій Хаара для подальшої передачі стислих зображень по каналах зв'язку або їх архівування.
Стиснення навігаційних таблиць в базисі Уолша C.B. Пашенцев
Водіїв суден факультет МГТУ, кафедра судноводіння
Анотація. В роботі розглянута можливість використання функціонального базису Уолша-Пелі для стиснення лінійних і прямокутних таблиць. Наведено всі необхідні для цього формули і на деяких прикладах продемонстровано реальний ефект стиснення інформації. Метод може використовуватися як для попереднього стиснення інформації, так і при її обробці в реальному масштабі часу.
Abstract. A possibility of the using of the Wolsh-Paly functional base for the linear and rectangular tables compression has been considered in the work. All the formulas, necessary for it, are given and the actual effect of information compression has been shown on some examples. The method can be used both for preliminary compression of information, and by its processing in a real time scale.
1. Введення
У багатьох автоматичних і автоматизованих пристроях, пов'язаних з судноводіння, використовуються табличні дані, занесені в пам'ять обчислювальних пристроїв і обрані з неї в міру потреби. При цьому витрачається найважливіший ресурс - пам'ять, а вибірка з неї споживає і ще більш важливий ресурс - час, впливаючи на швидкодію всієї системи обробки інформації. Тому важливі будь-які методи, що дозволяють зменшувати обсяг зберігання. Одним з таких методів може бути метод стиснення табличній інформації за рахунок її спектрального розкладання в деякому функціональному базисі. У момент споживання значення функції відновлюється зворотним перетворенням. У порівнянні з розкладанням Фур'є, більш вигідним є використання для розкладання базису Уолша, так як для гладких функцій коефіцієнти розкладання Уолша швидше прагнуть до нуля. Це допускає велику ступінь стиснення інформації в базисі Уолша. Крім того, при відновленні табличних значень в базисі Уолша потрібна менша час. Пов'язано це з більш простим обчисленням функцій Уолша порівняно з обчисленнями тригонометричних функцій. Ести ж ці функції генеруються апаратно, то вигода від застосування функцій Уолша ще більше, так як їх можливі значення +1 і -1 легко реалізуються обчислювальними пристроями. В роботі на численних прикладах показані переваги застосування базису Уолша для деяких типів гладких функцій і табличних даних. Обчислювальний процес будується на програмах швидких перетворень Фур'є і Уолша, написаних автором, і порівнянні отриманих спектрів.
2. Теоретичні основи стиснення
Загальні теоретичні положення, на підставі яких проводиться перетворення в обраному функціональному базисі, добре відомі (Голд, Райдер, 1993; Трахтман А., Трахтман В., 1978). Слід виділити дискретні перетворення при кінцівки вихідного числового ряду. Оскільки мова йде про стиснення таблиць, тобто про принципово кінцевому ряді чисел, то далі будемо говорити тільки про дискретних перетвореннях. Якщо заданий ряд з N чисел
X2, Xk,, XN (1)
то і функціональний базис слід вибрати з кінцевого набору N функцій
Фа (Х), а = 1, 2, "., N, (2)
існуючих на сукупності точок Xk. Тоді дискретне перетворення в цьому базисі дасть рівно N коефіцієнтів Ca, Koropbie знаходяться за допомогою формального підсумовування:
C "='кХк Фа (Хк), а = 1, 2," "N. (3)
Сукупність N коефіцієнтів Ca і становить дискретне уявлення ряду чисел (1) в
функціональному базисі (2). Часто цю сукупність чисел Ca називають лінійчатим спектром в обраному базисі. Інший інтерпретацією розкладання (3) є розгляд його як лінійного перетвореннявихідної системи координат Хк. Коефіцієнти Ca стають тоді координатами в новій системі координат 0JX). Якщо спектр (набір коефіцієнтів Ca) відомий, то що породив його ряд чисел можна відновити з точністю до похибок обчислень за допомогою зворотного дискретного перетворення
Xk = (1 / N) T.aCa0JXk), k = 1, 2, ..., N. (4)
Для справедливості простих і майже симетричних перетворень (3) і (4) необхідно, щоб набір функцій базису володів властивостями ортогональності і певної нормування. Умова ортогональності виглядає як сукупність рівностей
Zk Фр (Хк) Ф (Хк) = 0, р Ф q, (5)
а умови нормування - як сукупність рівностей
Zk ФрХк) Фр (Хк) = Ек Фр \ Хк) = 1. (6)
Крім того, система базисних функцій називається повною, якщо неможливо вказати більш жодної функції, яка ортогональна до всіх функцій базису.
Очевидно, що при такій постановці питання ніякого стиснення не відбувається, так як кількість членів вихідного ряду і кількість спектральних коефіцієнтів однаково. Можливість стиснення інформації з'являється, якщо число коефіцієнтів спектра можна зробити менше числа N. Наприклад, коли частина коефіцієнтів спектра дорівнює нулю або близька до нього. Тоді цими коефіцієнтами можна знехтувати, і отриманий спектр виявиться коротше. У першому випадку, коли ми нехтуємо тільки нульовими коефіцієнтами спектра, вихідний ряд чисел буде відновлений з точністю до похибок обчислень. Якщо ж ми пренебрежем коефіцієнтами спектра, у зазначеній ступеня близькими до нуля, то відновлені значення вихідного ряду будуть включати в себе не тільки похибки обчислень, але і похибки від неточного уявлення спектра. Чим більшу погрішність відновлення членів вихідного ряду ми flonyœaeM, TeM великим числом коефіцієнтів спектра можна знехтувати.
Якщо позначити через n число коефіцієнтів спектра, якими ми знехтували, то ставлення у відсотках
sq = (n / N) -100% (7)
можна назвати ступенем стиснення вихідної інформації. Адже в цьому випадку ми представляємо її N-n коефіцієнтамиспектра замість N значень вихідного ряду. При sq = 0 стиснення взагалі не відбувається, а при sq = 100% воно досягає граничної гіпотетичної величини. Реальні випадки лежать в межах від 0% до 100%.
Практична сторона реалізації цієї ідеї дещо складніше. Якщо нульовими або малими у зазначеній мірі є кінцеві (фінальні) спектральні коефіцієнти, то не складає труднощів відкинути n з них і тим самим домогтися стиснення sq.
Якщо ж серед коефіцієнтів спектра є нульові або близькі до нуля в заданій ступеня, але вони не є фінальними, то виникає складність в поданні такого спектра з позицій стиснення інформації. В цьому випадку треба або приводити все коефіцієнти спектру, включаючи нульові і близькі до них, і тоді стиснення не відбувається. Або ставити групи нульових спектральних коефіцієнтів номером початкового елемента в групі і кількістю елементів групи. Це, природно, зменшує ступінь стиснення вихідного ряду чисел. Якщо нульові елементи спектра не є фінальними або Не є групи, а їх номери не виявляють простий закономірності, то стиснення інформації цим шляхом не досягається.
Отже, можливість стиснення інформації та ступінь її стиснення залежать як від самого ряду чисел (1), так і від набору функцій (2), що складають базис спектрального розкладання Ca. Оскільки ряд чисел Хк нам заданий, то управляти ступенем стиснення ми можемо, змінюючи базис спектрального розкладання. Але при обраному базисі Ф (х) характер заданої інформації буде позначатися як на самій
можливості стиснення, так і на ступеня її стиснення. Існує досить багато функціональних базисів, які успішно використовуються для різних завдань представлення інформації. Серед найбільш відомих назвемо базиси статечних функції і їх поліноміальні варіанти у вигляді поліномів Чебишева і Лежандра, а також базиси Кравчука, Шарлье і Мейснера. Але найбільш знайомим нам є базис тригонометричних функцій:
sin (2nax) і зі s (2n «x), (7)
або відповідний експонентний базис в комплексній формі:
exp (-j 2nax). (8)
В цьому випадку спектр коефіцієнтів Ca є спектром в його звичайному фізичному сенсі як сукупності амплітуд деякого набору частот обмеженого діапазону і певного частотного дозволу. Оскільки в цьому випадку базис вже обраний, то можливості стиснення тепер пов'язані тільки з характером вихідної інформації. Якщо вона адекватна за характером заданої базису (8), тобто складається з лінійної комбінації кінцевого числа періодичних функцій, то спектр буде містити лише кінцеве число відмінних від нуля коефіцієнтів, і виникає можливість стиснення інформації.
3. Система функцій Уолша-Пелі
Якщо ж вихідна інформація має інший характер, наприклад, змінюється за степеневим, показовому або логарифмічною закону, то в спектрі все його коефіцієнти не є достатньо малими, і стиснення або неможливо, або ступінь стиснення мала. У цих випадках розумно використовувати інший функціональний базис. Оскільки для інших базисів немає чіткого фізичного представлення спектра, то можна інтерпретувати (2) як формули переходу від координатної системи Xk до іншої координатної системі Фа (Х). Рівність нулю частини коефіцієнтів означає, що вектор, заданий координатами у вигляді вихідного ряду чисел, в новій системі координат розташовується в координатної гиперплоскости розмірності N-n. Серед існуючих можливостей є кілька базисів, породжуваних функціями Радемахера при Z е (0,1):
R0 (z) = 1, Rk (z) = sign (sin (2k nz)), k = 1,2, ..., (9)
які відповідно до вхідної в них функцією sign () приймають тільки два значення: +1 або -1.
Система функцій (9) ортогональна і нормована, але не є повною. До неї можна додати функції виду sign (cos2knz), які також ортогональні до функцій системи (9). Тому на базі уявлень (9) формують інші повні системи, використовуючи твори функцій Радемахера і вносячи в одержувані в такий спосіб нові функції певне упорядкування.
Найцікавішою для навігаційних застосувань в плані стиснення інформації є система функцій Уолша-Пелі. Утворення цієї системи тісно пов'язане з двійковими номерами складових її функцій. Конкретно, функція Уолша-Пелі з номером а є твір функцій Радемахера з номерами тих двійкових розрядів а, в яких розташовані 1. Якщо записати номер а в двійковому поданні з n = log N розрядами
а = Zk 2k-1 ak, (10)
то функції системи Уолша-Пелі можна змалювати таку картину:
Wa (z) = Пк М. Сам номер) можна представляти подібно (12) в двійковій формі:
) = Ек 2 к-1] к. (15)
Тоді система функцій Уолша-Пелі остаточно випаде у вигляді
Яга) / Щ = WJ (а / К) = (-1) "как1" "до + \ (16)
який використовується у всіх наступних обчисленнях. Програмна функція WolshPaly () на мові Паскаль для генерації функцій Уолша-Пелі за допомогою формул (16) наведена нижче. Для N = 8 значення функцій Уолша-Пелі № (/) наведено в табл. 1.
Таблиця 1. Значення функцій Уолша-Пелі для N = 8
] 0 1 2 3 4 5 6 7
0 1 1 1 1 1 1 1 1
Чи не обговорюючи деталі, просто згадаємо про існування систем функцій Адамара і Хармут, які відрізняються від докладно розглянутої системи функцій Уолша-Пелі тільки способом упорядкування одних і тих же функцій. Саме порядок функцій Уолша-Пелі забезпечує найбільшу кількість фінальних коефіцієнтів спектра, нульових або близьких до нуля в заданій ступеня.
4. Відповідність рядів Уолша-Пелі
Функції Уолша мають ряд корисних властивостей, Серед яких наведемо використовується в обчисленнях властивість симетрії:
Щ (а / Щ. (17)
Двійкове подання номерів функцій Уолша з п = logN розрядами визначає порядок р і ранг г функції. Порядком називається найбільший номер двійкового розряду, що дорівнює 1. Рангом Я функції називається число ненульових двійкових розрядів, наприклад, функція Уолша з номером а = 9 для N = 16 і п = 4 представляється в двійковій формі як 1001, і, отже, її ранг г = 2 (два
ненульових розряду) і порядок р = 3 (старший ненульовий розряд - третій, т. к. лік охочих іде від нуля). Якщо функція з номером а має ранг г, то її номер можна представити у вигляді:
а (Я = г) = 2М1 + 21 "2 + ... + 2 мг, (18)
де цк (к = 1, 2, ..., г) - номера ненульових розрядів двійкового представлення номера а. Наприклад, номер 9 можна представити як 23 + 20, з огляду на двійкове подання 1001. Безпосередньо для проблеми стиснення вихідної інформації важлива швидкість убування коефіцієнтів Са розкладання в базисі Уолша при зростанні номера а. Якщо функція, яка надається поруч (1), володіє безперервної похідної до даго порядку, і максимальне значеннямодуля похідної | А "(т) | є М, то коефіцієнти спектру з номерами а, ранг яких не менше порядку похідної (г> да), задовольняє нерівності (Проектування спеціалізованих ..., 1984):
| Са (г> ш) |< М/ 2ш(ш+3)/2. (19)
Саме це важливе нерівність гарантує швидку збіжність спектральних коефіцієнтів Са з ростом номера а й відкриває перспективи стиснення табличній інформації. Дійсно, ранг г функції Уолша збільшується з ростом номера функції а так, що умова г> ш виконується для великих номерів а. Це означає, що оцінка (19) діє для фінальних коефіцієнтів розкладання.
Таблиця 2. Коефіцієнти спектрального розкладання статечних функцій в базисі Уолша
ПОРЯДОК РАНГ РІВЕНЬ ФУНКЦІЇ
0 0 4.68 3.03 2.20 1.37
1 0 -2.50 -2.34 -1.96 -1.34
2 1 -1.25 -1.17 -1.10 -0.95
3 1 0 0.63 0.88 0.92
4 2 -0.63 -0.59 -0.56 -0.52
5 2 0 0.31 0.44 0.49
6 2 0 0.16 0.22 0.31
7 3 0 0 -0.12 -0.29
8 3 -0.31 -0.29 -0.28 -0.26
9 3 0 0.16 0.22 0.25
10 3 0 0.08 0.11 0.15
11 3 0 0 -0.06 -0.15
12 3 0 0.04 0.05 0.08
13 3 0 0 -0.03 -0.07
14 3 0 0 -0.01 -0.04
15 3 0 0 0 -0.03
од% 43.8 18.8 6.3 0
Якщо до того ж функція має кінцеве число відмінних від нуля похідних (наприклад, статечна функція), то всі коефіцієнти з номерами, чиї ранги більше цього ступеня, тотожно рівні нулю. Але для цього необхідно, щоб число N було досить велике, і ранг "встиг" побільшати номера старшої похідної. Як приклад розглянемо спектральне розкладання статечної функції, представленої поруч (1), з числом відліків, рівним 16 ^ = 16, п = 4). Мале число відліків вибрано тільки для видимості результатів прикладу. Вище в табл. 2 наведені з округленням до двох знаків спектральні коефіцієнти розкладання для різних статечних функцій: лінійної, квадратичної, кубічної і п'ятого ступеня - з одночасною вказівкою номера а спектру і його рангу р
На цьому прикладі видно, що чим менше ступінь функції, яка породжує ряд чисел (1), тим більшою мірою стиснення од можна досягти при розкладанні. Якщо ряд короткий, а ступінь велика, то стиснення взагалі не досягається, як це відбувається при п'ятого ступеня функції. Якщо при тій же мірі функції збільшувати число членів ряду і, отже, число коефіцієнтів спектра, то ступінь
стиснення зростає. Так, при N = 64 sq = 7.8%, при N = 128 sq = 18.0%, при N = 256 sq = 23.8%.
Зауважимо принагідно, що в разі спектра Фур'є ні в одному з наведених випадків ніякого стиснення не досягається - у наявності неадекватність тригонометричного базису статечним функцій.
4. Основні формули дискретного перетворення Уолша-Пелі
Зазвичай йдеться про подання заданої функціїв обраному базисі, але, працюючи з дискретним спектральним перетворенням, ми маємо справу з набором її дискретних значень. Ці дискретні значення представлені рядом чисел (1).
Отже, ми виберемо в якості функціонального базису систему функцій Уолша-Пелі (16) і наведемо для цієї системи основні формули, які виражають властивості ортогональності і нормування функцій в цій системі, і формули перетворення для неї:
Формула прямого дискретного перетворення Уолша для отримання спектра
Са = (1 / N) ZkXkWa (k / N).
Формула зворотного дискретного перетворення Уолша для відновлення вихідного ряду значень
Xk = EaCaWa (k / N).
Умова ортогональності і нормування функцій Уолша на дискретній множині точок
No = (1 / N) Zk Wp (k / N) W (k / N) = 0, якщо p Ф q і No = 1, якщо p = q. рівність Парсеваля
(1 / N) ZkXk2 ='аСа,
яке являє собою рівність квадрата модуля вектора в вихідної Xk і нової Са системах координат.
5. Елементи програмної реалізації
Саме цей набір формул був покладений автором в основу при складанні програми на мові Паскаль для порівняльного аналізу результатів дискретних перетворень Фур'є і Уолша (свідоцтво на програмний продукт РосАПО № 950347 від 02.10.1995). При цьому дискретні перетворення були реалізовані як швидкі перетворення Фур'є (ШПФ) і Уолша (БПУ) з основою 2 і проріджуванням за часом (Рабіндер, Голд, 1978). Це не має значення для стиснення табличній інформації, так як перетворення в цьому випадку проводиться один раз, але дуже важливо при обробці інформації в реальному масштабі часу для можливості прогонки більшого числа різних числових рядів (таблиць, функцій) за мінімальний час. Подібна програма практично без змін була з успіхом застосована при оперативному спектральному аналізі на борту літаючої лабораторії Іл-18-Дорріт ПІНРО. Два основних фрагмента цієї програми наведені нижче. Це процедура швидкого перетворення Уолша і функція обчислення значення функції Уолша по заданому номеру і аргументу. Вся програма займає надто багато місця і тому тут не наводиться.
Function WolshPaly (Alf, l: integer): integer; var J, K, x, y, w, maskl, mask2: integer; begin
w: = l; mask1: = l; mask2: = N div 2; for K: = 0 to N-l do begin
if (Alf and mask2)<>0 and (I and mask1)<>0 then w: = - w; mask1: = mask1 * 2; mask2: = mask2 div 2; end;
WolshPaly: = w; end;
Ця функція приймає два параметри - номер Alf і аргумент I функції Уолша і повертає саме значення функції Уолша.
Procedure FastWolshTrans (var ml, m2, m3, m4: masdat); var L, LE, LE1, I, J, IP: integer; T1, T2: real;
begin LE: = 1; for L: = 1 to M do begin LE1: = LE; LE: = LE * 2;
for J: = 1 to LE1 do begin I: = J; repeat IP: = I + LEl; T1: = m1; T2: = m2;
If L = M then begin
m3: = m1 [I] -T1; m4: = m2 [I] -T2; m3 [I]: = m1 [I] + T1; m4 [I]: = m2 [I] + T2;
m1: = m1 [I] -T1; m2: = m2 [I] -T2; m1 [I]: = m1 [I] + T1; m2 [I]: = m2 [I] + T2;
I: = I + LE; until I> N; end; end;
/ * "D" - знак прямого перетворення * /
if TIP = "D" then begin for L: = 1 to N do begin m3 [L]: = m3 [L] / N; m4 [L]: = m4 [L] / N; end;
Процедура виробляє швидке перетворення Уолша даних, які передаються процедурі в масивах ml і m2. Результат перетворення - спектр Уолша повертається процедурою в масивах m3 і m4. Якщо дані передаються процедурі в звичайному порядку проходження, то результат повертається в двійковій-інвертованому порядку. Якщо ж ми хочемо отримати звичайний порядок коефіцієнтів спектра, то вихідні дані для обробки слід двійковій інвертувати. Двійковим інвертуванням номера вважається номер, в якому порядок його двійкових розрядів змінений на зворотний, наприклад, інверсія числа 6 = 110 є 3 = 011. Для інверсії будь-яких номерів пропонується процедура на мові Pascal:
Procedure MASINVERSION (sw: integer; var m1, m2: masdat); var I, J, K, NV2: integer; T: real; begin NV2: = N div 2;
for I: = 1 to N-1 do begin
if I else begin K: = NV2; while K 6. Стиснення таблиць з двома аргументами Вище були розглянуті перетворення і стиснення одновимірних, лінійних таблиць. Але більшість застосовуваних в судноводінні таблиць є двовимірними - прямокутними матрицями. Питання про їх стисненні можна вирішити двома шляхами. Перший шлях - перетворення таблиці як лінійної, вважаючи, що вона утворена послідовним розміщенням рядків таблиці-матриці, починаючи з першого рядка. Цей шлях цілком звичайний, адже саме так зберігається двовимірний масив в лінійно організованою пам'яті ЕОМ. Перевага такого способу полягає в тому, що розмір такої лінійної таблиці буде досить великим, і можна сподіватися на ефективність стиснення. Але в ньому приховані і можливі неприємності. Після вибудовування в лінію рядків матриці ми напевно одержимо скачки функції при переході від кінця одного рядка до початку наступного. Ці труднощі можна обійти зміною порядку елементів у кожній парній рядку - інвертуванням цього рядка. Відповідно, зміниться і порядок спектральних коефіцієнтів. Але це не ускладнить, а тільки змінить порядок номерів при відновленні значень самої функції. Так, якщо номер значення відновлюваної функції був Npq = (р - 1) М + q, де р - номер рядка з числом М елементів в ній, а q - номер стовпця, то після інвертування для парних рядків цей номер стане рівним (р - 1) М + (М- q + 1). Другий шлях - спочатку спектральне перетворення рядків таблиці, а потім перетворення отриманого проміжного спектра за стовпцями. Недоліком цього способу можна вважати малу ступінь стиснення через малу довжину рядків і стовпців. Правда, ефект стиснення посилюється за рахунок подвійного перетворення і рядків, і стовпців. Наприклад, при стисненні рядків і стовпців всього на 10% загальний ефект стиснення буде рівний 1 - 0.9x0.9 = 0.19 = 19%. Якщо, наприклад, рядки таблиці змінюються в квадратичного закону, а стовпці по кубічному, то загальний ефект стиснення за даними табл. 2 дорівнює 1 (1-0.188) х (1-0.63) = 0.24 = 24%. Як конкретний приклад наведемо результати перетворення таблиці інтегральної функції Лапласа (Кондрашіхін, 1969), яку застосовують в судноводінні при оцінці надійності мореплавання. Тут вона представлена у вигляді матриці 30x10, тобто складається з 30 рядків і 10 стовпців. Перетворювати її як двовимірну немає ніякого сенсу: занадто мало (10) елементів в рядках. Тому перетворимо її як лінійну таблицю з 300 значень. У прикладі будемо вважати, що значень 256 = 28. Але можна було б доповнити таблицю нулями і вважати число значень 512 = 29. Ів тому, і в іншому випадках отримано однаковий результат: фінальне число нулів з ступенем близькості до нуля порядку 0.01% від максимального коефіцієнта становить 46.5%. Відновлення функції по стислій до 53.5% сукупності коефіцієнтів спектра дало похибки: середню квадратичну в 0.005 і максимальну в 0.057. Приклад показує ефективність проведеного перетворення таблиці. 7. Висновок Проведені дослідження, пов'язані з вибором функціонального базису Уолша-Пелі, показують, що цей функціональний базис може успішно застосовуватися в різних системах обробки інформації, що не носить вираженого періодичного характеру. В цьому випадку переваги такого функціонального базису перед базисом Фур'є очевидні. Крім того, базис Уолша-Пелі дає хороший ефект при стисненні інформації. Це показано на прикладі характерною для задач надійності навігації таблиці інтегральної функції Лапласа, де ефект стиснення досяг 53.5%. література Голд Б., Рейдер Ч. Цифрова обробка сигналів. М., Сов.радіо, 367 е., 1993. Кондрашіхін В.Т. Теорія помилок. М., Транспорт, 256 е., 1969. Проектування спеціалізованих інформаційно-обчислювальних систем. Під ред. Смирнова Ю.М. М., Вища школа, 359 е., 1984. Рабіндер Л., Голд Б. Теорія і додатки цифрової обробки сигналів. М., Мир, 528 е., 1978. Трахтман А.Н., Трахтман В.А. Введення в загальну спектральну теорію сигналів. М., Сов.радіо, 312 е., 1978. Пол Фейєрабенд (р. 1924). Томас Кун (р. 1922). Імре Лакатош (1921-1974). Функції Уолща є природним розширенням системи функцій Радемахера, отримані Уолшем в 1923 р і представляють повну систему ортонормованих прямокутних функцій. Безліч функцій Уолша, упорядкованих по частості, зазвичай позначають у такий спосіб: Функції Уолша, впорядковані по частості, аналогічно тригонометричним функціям можна поділити на парні cal (i, t) і непарні sal (i, t) На малюнку 17.1 показані перші вісім функцій wal w(I, t). малюнок 17.1 При цьому видно, що частость кожної наступної функції Уолша більше або дорівнює частости попередньої функції Уолша і має на одне перетинання нульового рівня більше у відкритому інтервалі tÎ. Звідси і випливає назва «впорядкування по частості». Дискретизація функцій Уолша, показаних на малюнку 17.1а, в восьми рівновіддалених точках призводить до матриці (8х8), показаної на малюнку 17.1б. Цю матрицю позначають H w(N) де n = log 2 N і матриця буде мати розмір NxN. Функції Уолша при упорядкуванні по частості в загальному випадку можна отримувати з функцій Радемахера r k (x) за формулою: де w номер функції Уолша; k - номер функції Радемахера; показник ступеня функції Радемахера, який приймає значення 0 або 1 в результаті підсумовування за модулем два, тобто за правилом: 1Å1 = 0Å0 = 0; 1Å0 = 0Å1 = 1 розрядів двійкового числа w. Наприклад для шостий функції Уолша ( w= 6), що входить в систему розміром N = 2 3 = 8 твір (17.4) складається з трьох співмножників виду: при k = 1 при k = 2 при k = 3. Число в двійковій системі записується сукупністю нулів і одиниць. У нашому випадку значення wі його розрядів показані в таблиці 17.1 Таблиця 17.1 w 0 - старший розряд числа, w 3 - молодший розряд числа w. Показники ступеня функцій Радемахера виходять рівними:; ; і, отже, wal (6, x) = r 1 + 1 (x) × r 2 0 (x) × r 3 1 (x) = r 1 (x) r 3 (x) Правило отримання показників ступенів для функції Радемахера схематично показано в таблиці 17.1, де стрілками вказані підсумовувані розряди числа wі функції Радемахера, до яких відноситься отриманий показник ступеня. З малюнка 17.1 видно, що парні номери функцій Уолша відносяться до парних функцій, а непарні до непарних функцій. Іншим способом упорядкування є впорядкування по Пелі. При упорядкуванні по Пелі, аналітична запис функції Уолша має вигляд: p 1 - молодший розряд двійкового числа, р n - старший розряд двійкового числа. При упорядкуванні по Пелі для формування функцій Уолша необхідно взяти твір зведених до рівня функцій Радемахера, номери яких збігаються з номерами відповідних розрядів двоіхного уявлення числа р, а показник ступеня кожної функції дорівнює вмісту відповідного розряду, тобто 0 або 1. Причому молодшої функції Радемахера відповідає молодший розряд двійковій комбінації числа р. Відповідно до цього правила в таблиці 17.2 наведені значення функцій Уолша упорядкованих по Пелі. Таблиця 17.2 Функції Радемахера в таблиці показані в формі:. Порівняння творів і ступенів функцій Радемахера, записаних в таблицях 17.1 і 17.2 показує., Що між функціями Уолша, впорядкованими по Пелі і по Уолшу існує відповідність, яке відображено в останньому стовпчику таблиці 17.2. У відповідності з функціями Уолша впорядкованими по Пелі також може бути побудована матриця відліків H p (n), аналогічна показаної на малюнку 17.1б.
(17.3)
а)
б)
(17.4)
р р 1 р 2 р 3 r 1 (x) × r 2 (x) × r 3 (x) wal p (i, x) = wal w(J, x)
r 1 0 (x) × r 2 0 (x) × r 3 0 (x) wal p (0, x) = wal w(0, x)
r 1 + 1 (x) × r 2 0 (x) × r 3 0 (x) wal p (1, x) = wal w(1, x)
r 1 0 (x) × r 2 1 (x) × r 3 0 (x) wal p (2, x) = wal w(3, x)
r 1 + 1 (x) × r 2 1 (x) × r 3 0 (x) wal p (3, x) = wal w(2, x)
r 1 0 (x) × r 2 0 (x) × r 3 1 (x) wal p (4, x) = wal w(7, x)
r 1 + 1 (x) × r 2 0 (x) × r 3 1 (x) wal p (5, x) = wal w(6, x)
r 1 0 (x) × r 2 1 (x) × r 3 1 (x) wal p (6, x) = wal w(4, x)
r 1 + 1 (x) × r 2 1 (x) × r 3 1 (x) wal p (7, x) = wal w(5, x)
wal h (0, x) = wal w(0, x); wal h (2, x) = wal w(3, x); wal h (4, x) = wal w(1, x); wal h (6, x) = wal w(2, x); wal h (1, x) = wal w(7, x); wal h (3, x) = wal w(4, x); wal h (5, x) = wal w(6, x); wal h (7, x) = wal w(5, x).
(17.9)
