автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Способы быстрого преобразования Фурье последовательностей произвольного размера

Державний університет “Львівська політехніка” Процько Ігор Омелянович

од

фсВ 1999 УДК 621.372

ЗАСОБИ ШВИДКОГО ПЕРЕТВОРЕННЯ ФУР’Є ПОСЛІДОВНОСТЕЙ ДОВІЛЬНОГО ОБСЯГУ

Спеціальність 05.13.05 - елементи та пристрої обчислювальної техніки та систем керування

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

Львів - 1998

Дисертацією є рукопис

Робота виконана у Державному університеті “Львівська політехніка” Міністерства освіти України.

Науковий керівник: доктор технічних наук,

старший науковий співробітник Луцик Ярослав Теодорович ДУ “Львівська політехніка”

Офіційні опоненти:

1) доктор технічних наук, професор Чабан Василь Йосипович, ДУ “Львівська політехніка”, кафедра “Теоретична та загальна електротехніка”;

2) кандидат технічних наук, старший науковий співробітник Паленичка Роман Мирославович, зав. лабораторією “Автоматизація наукових досліджень” Фізико-механічний інститут НАН України.

Провідна установа: Вінницький державний технічний університе кафедра обчислювальної техніки, м. Вінниця.

Захист відбудеться “ 2 б “ ______ 1999 р. о ^ & годині.

на засіданні спеціалізованої вченої ради Д 35.052.08 у Державному університеті “Львівська політехніка” в ауд. 226 головного корпусу (290646, Львів-13, вул. С. Бандери,12)

З дисертацією можна ознайомитись в бібліотеці Державного університету “Львівська політехніка”

(290646, Львів-13, вул. Професорська, 1)

Автореферат розісланий “ £ “ О4 1999р.

В. о. вченого секретаря Бичківський Р.В

спеціалізованої вченої ради,. ^ д.т.н., професор

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Проведення цифрового спектрального шалізу сигналів на основі ефективних методів обчислення дискретного іеретворення Фур’є (ДПФ) використовується для визначення значення гнергетичних спектрів сигналу, крос-спектральних густин, згорток, кореляційних функцій, оцінення похибки відтворення корисного :игналу, розпізнавання та ідентифікації образів, проведення ііагностики системи, знаходження дефектів об’єкту, кодування нформації та в багатьох інших прикладних задачах. Ріст загального зівня динамічних досліджень обумовлює необхідність розвитку і утворення нових алгоритмічних, програмних та апаратних засобів лвидкого перетворення Фур'є (ШПФ) цифрових сигналів, що зідповідають сучасним задачам і вимогам, а саме :

можливості вибору необхідного значення роздільної здатності шектру, що визначається ефективним інтервалом концентрації енергії :игналу;

забезпеченню проведення спектрального аналізу з певного моменту іасу сигналу з довільним обсягом послідовності;

використання відповідних алгоритмічних, програмних, апаратних іасобів ШПФ пов’язаних з особливістю проведення спектрального іналізу.

Тому актуальним є подальший розвиток узагальнених підходів їфективного обчислення ДПФ послідовностей довільних обсягів та юзробки нових алгоритмів та структур спеціалізованих засобів.

Зв'язок з науковими програмами, планами, темами. Робота шконувалась згідно напрямку Державної науково-технічної програми ‘Перспективні засоби обчислювальної техніки. Аналітичне іриладобудування. Телекомунікації” Міністерства освіти України у :правах науки і технологій, 1997р. Окремі результати отримані.в іроцесі виконання науково-дослідних робіт ДБ ШМ, № 6415.

Мета і задачі дослідження. Аналіз і розробка алгоритмічних ■а спеціалізованих апаратних засобів швидкого обчислення дискретного іеретворення Фур’є послідовностей довільного обсягу на основі іроведення декомпозиції базису дискретних експоненціальних функцій ІПФ на матрицю показників степені та матриці знаків.

Наукова новизна одержаних результатів. Запропоновано ювий підхід до проведення синтезу структури швидкого обчислення іискретного перетворення Фур’є послідовностей довільного обсягу на •снові декомпозиції експоненціального базису (ЕБ) ДПФ за допомогою іатриці показників степені та матриць знаків.

Виділено з множини натурального ряду підмножини, ще визначають особливості формування матриць показників ЕБ ДП<І послідовностей довільного обсягу.

Сформовано матриці показників експоненціального базису з; допомогою циклічного розкладу підстановок для ДПФ послідовностеі довільного обсягу.

Доведено, що квадратні матриці показників степені і знакії косинусу, синусу ЕБ ДПФ послідовності довільного обсягу мают лівоциркулянтні еквівалентно-матричні структури. При цьом; обчислення ДПФ зводиться до обчислень на основі швидки: алгоритмів циклічної згортки над матрицями або підматрицями функції косинусу, синусу ЕБ.

Запропоновано узагальнений підхід до організації швидког обчислення дискретного перетворення Фур’є послідовностей довільног обсягу і створення на його основі спеціалізованих обчислювальни засобів.

Практичне значення отриманих результатів. На підстаї одержаних теоретичних викладок та експериментальних досліджен запропоновано алгоритмічну модель ефективного обчислення ДПФ дл створення в пакетах прикладних програм функцій ШПФ довільни обсягів та розробки структур спеціалізованих обчислювальних засобі швидкого перетворення Фур’є послідовностей довільного обсягу.

Отримані результати е основою для створення спеціалізовани програмних та апаратних засобів проведення цифрового спектральног аналізу.

Особистий внесок. Основні теоретичні, розрахункові т експериментальні результати з формулюванням відповідних висновкі отримані автором самостійно, зокрема:

- запропоновано підхід до проведення декомпозиції і аналіз екпоненціального базису ДПФ за допомогою матриці показник) степенів та матриць знаків;

- досліджено процедуру формування матриці показників ЕБ ДПФ і синтез ефективного обчислення ДПФ послідовностей довільної обсягу;

- розроблено структури елементів апаратних засобів на ба запропонованого підходу обчислення ШПФ послідовностей довільног обсягу.

Окремі результати експериментальних досліджень та розробк спеціалізованих пристроїв отримані в співавторстві згідно наведеної списку використаних джерел.

Апробація результатів дисертації. Latvian Signal Processin International Conference “LSPIC-90”, April 1990, Riga.

International Conference Image Analysis and Pattern Recognition iTIAPR'90”, October 1990, Lviv.

Друга Українська конференція з автоматичного керування 'Автоматика-95", вересень 1995, Львів.

Міжнародна конференція “Комп’ютерні технології друкарства. Алгоритми, сигнали, системи ’’Друкотехн - 96”, жовтень 1996, Львів.

Третя Всеукраїнська міжнародна конференція “Оброблення сигналів і зображень та розпізнавання образів - "Укробраз-96", листопад 1996, Київ.

Науково-технічна конференція “Фізичні методи та засоби контролю матеріалів та виробів “Леотест-98”, лютий 1998, Славське Львівської області.

Публікації. Основні результати дисертації опубліковані в 14 друкованих роботах.

Структура та обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних джерел (107 найменувань), додатку. Повний обсяг -145 стор., текст -129 стор., рисунків -12, таблиць -16, додатків -2.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обгрунтовано актуальність проблеми, сформульована мета та задачі досліджень, показана наукова новизна та практичне значення отриманих результатів.

У першому розділі проаналізовано важливість забезпечення засобами обчислення ДПФ проведення цифрового спектрального аналізу пов’язаного з обсягом послідовності дискретного сигналу.

Розглянуто розвиток методів ефективного обчислення ДПФ та підкреслено актуальність подальших досліджень по створенню універсальних процедур швидкого обчислення дискретного

перетворення Фур’є для послідовностей довільного обсягу.

У другому розділі запропоновано підхід до аналізу ДПФ на основі матриці показників і матриць знаків експоненціального базису. Для ДПФ в матричній формі запису:

[Х(к)] = [^1 [х(к)], (1)

де N - ціле довільне значення обсягу перетворення; [Х(к)1, [х(к)| -вектор стовпці порядку (Ых1); \У=ехр(-] 27г/Ы); г,к=0(і)!Ч-1;

І=(-1)1/2; [Шм г*к] - квадратна матриця порядку (ШГ\1),

показано, що матрицю показників дискретного експоненціального базису \УП‘, де 1=1(1)Г>И, можна повністю визначити для 1=0(1)]М/4, при цілих значеннях N кратних 4-ом і для парних значень N. що є дільниками 360,

V =[у(г,к) тосі (N/4)], де г,к=1(1)(]Ч/4), (2)

а для решти значень N. (непарних, парних не кратних 4 і парних не множників 360) визначаєм при 1=0(і){М/2}; { } -береться ціла частинг від ділення,

V =[у(г,к) тосі (N/2)], де г,к=1(і){Н/2}, (3)

доповнюючи матрицями знаків 7.$ синуса і косинуса при відповідна межах зміни 1=0( і ){ГчГ/2}

Г +1, якщо у(г,к)< N/2 гБІг.к] = і (4)

І -1, якщо у(г,к)> N/2 ;

Г +1, якщо ЗІ^/4<у(г,к)<М/4 2с[г,к] = ■{ (5)

1-1, якщо М/4<у(г,к)<ЗІ^/4 ,

де у(г,к)=(г*к) тосі И; г,к=1(1){М/4} для (2) і г,к=1(і){ІМ/2} для (3).

На основі властивостей періодичності, симетричності базису дискретних експоненціальних функцій ДПФ та аналізу одержаний матриць показників степені (2,3) визначаємо розбитт5 ср={51,52,53,54,55,56} множини натуральних чисел на шісті підмножин:

- Б1, що містить всі непарні елементи натурального ряду, тобто, И=р де р -просте число, крім двійки, та складене М=р,хр2х...хрп, де рі прості, крім двійки;

- 52,' що містить елементи рівні 52={2хд}, де я-непарні дільники 36( {Ч=3,5,9,15,45};

- БЗ, що містить елементи рівні 53={2хр}\52, де р -непарні елементі масиву БІ, крім 1, та крім елементів підмножини Б2;

- 54, що містить елементи рівні 54={4хр}, де р-непарні елементі масиву Б1 крім 1;

- Б5, що містить елементи, рівні цілій степені два, 55={2П}, де п-ціле число;

- Б6, що містить елементи рівні 56={8хп}\55, де п-ціле число.

Для елементів підмножин Б1, БЗ матрицю показників достатньо визначити для порядку п={М/2}, для парних рядків БЗ існує симетрія відносно вертикалі {N/4}. Для елементів підмножин 52,54,55,56 матриця показників матиме порядок п={М/4} рядків, а для парних рядків існує симетрія відносно вертикалі {N/8}, крім елементів підмножини 52. Дане розбиття охоплює всі можливі випадки обсягів послідовностей ДПФ.

Одержані матриці показників ЕБ ДПФ для випадків простого значення обсягу N є нормалізованими латинськими квадратами. Для інших цілих N необхідно виділити квадратні підматриці, що при відповідному переіменуванні елементів підматриць в елементи натурального ряду відповідатимуть нормалізованим латинським квадратам, симетричним відносно головної діагоналі.

Обчислення кожен раз матриць показників ЕБ за формулами (2,3), у випадку ДПФ довільного обсягу послідовності, вимагає значних об’ємів пам’яті та затрат часу. Тому формування матриць показників за допомогою переставлення елементів для кожного наступного рядка матриць, що є латинськими квадратами, вимагало знаходження спільної підстановки. В роботі запропоновано рішення по формуванню рядків матриць показників ЕБ ДПФ за допомогою підстановки Р, що визначається елементами перших двох рядків квадратної матриці (2,3). Тобто, квадратна матриця показників формується послідовно для кожного наступного рядка за підстановками Р на основі попереднього рядка. Одержана підстановка описується циклічним розкладом підстановки Р(г)=(21)(г2)...(25) з числом циклів б відповідно для кожного довільного значення обсягу перетворення ДПФ.

У третьому розділі розглянуто процедуру проведення ефективного обчислення ДПФ на основі аналізу структур матриць показників степені Ур ЕБ ДПФ послідовностей довільного обсягу та відповідних матриць знаків синуса і 2’с косинуса, сформованих за одержаним циклічним розкладом підстановки.

Для елементів підмножини 51 з числом циклів підстановки рівним одиниці б=1 квадратні матриці показників Ур порядку п=(М-1)/2 містять рівні між собою елементи, що розміщені по діагоналях паралельних бічній діагоналі (у[і^']=у[к,і] при і+]=к+1, де і,і,к,1 є{і,2,..., п}; у[і,і] єУр). Тобто, матриці є Ганкелевими (Напкеї), що повністю визначаються своїм першим рядком та останнім стовпчиком. Окрім того, Ганкелеві матриці Ур є ліво-циркулянтними або циклічними зліва, що формуються послідовним зсувом вліво першого

рядка. Ганкелеві лівоциркулянтні матриці Ур парного порядки п=(>Н)/2 за структурою відповідають блочній матриці другог< порядку:

А В

Ур =

В А

(6)

Для елементів підмножини Б1 з числом циклів підстановок циклічногі розкладу більше одного б>1 квадратні матриці показників Ур матимут: відповідну структуру. Наприклад, для N=31, з=3, Ур складається . трьох підматриць по горизонталі та вертикалі (7), а для N=73 з числог циклів підстановки 5=4, сформована матриця показників Ур матим< структуру (8):

Ур =

— —1 “ А в С V

А В С В А’ В’ с

В С’ А’ (7) Ур = С 0’ В’ А”

С А’ В’ ) С’ А’ В’

(8)

Матриці Ур (7,8) не є ліво-циркулянтними, але містить ліве циркулянтні квадратні підматриці А, В, С, О, А’, В’, С’, Б’. Підматрии А’, А” (В’, С’, О’) містять ті ж рядки, що відповідні підматриці А (В, С О) тільки розміщені в іншій послідовності, що не порушує циклічніст зліва. Для непарних складених елементів підмножини Б1, наприкла;: для N=25 з 5=2, сформована матриця показників матиме структур (9), та для N=51 з 5=5 структура матриці (10), де Ь, с, сі, ї, т, п підматриці що містять дільник N і йому кратні елементи, а 0 - нульові

Ур =

- ьт-ьт

А ьт ьт ьт

ь ь ь ь ь о

(9) Ур =

А В с сі ґ

с сі ґ

В А’ сі’ с’ гт (10)

сі’ с’ ґ

с сі’ сі’ сі с” 0

а с’ с’ с” а” 0

і [ і 0 0

випадку в циклах розклад

підстановки Р(г) існують два цикли підстановок гь що містять окрем непарні і парні елементи. Елементи БЗ з числом циклів підстановк б=2 матимуть матрицю Ур, що складається з підматриць Уо,Уе :

УР =

Уо Уе Уе Уе

(11)

Матриця показників V (3) для парних рядків симетрична, тому датриця Ур містить в нижній частині дві підматриці Уе. Верхня іастина матриці Ур, що відповідає непарним рядкам, розбита на іідматриці Уо та Уе. Для елементів БЗ з числом циклів підстановки йвне $>2 ліво-циркулянтні квадратні підматриці Уе, Уо мають блочно-латричну структуру. Наприклад, для N=42, з=$, Р(г)= (1 5 17)(11 13 19)(3 15 9)(7)(2 10 8)(4 20 16)(6 12 18)( 14) одержимо матрицю Ур, що складається з підматриць Уо, Уе (12):

А В с К т пТ

В А’ с’ Сіт Уе = V К ш’ пт

с с’ с’ 0 т т ”т’0

сі сі 0 > п п 0

Для виконання дискретного перетворення Фур’є з шкористанням елементів декомпозиції ЕБ ДПФ аналогічні дії по іереставленню рядків і стовпців в матриці Ур виконаємо над латрицями знаків 2$ синуса і 2с косинуса. За структурою одержана латриця знаку косинуса 2’с еквівалентна матриці Ур. Еквівалентно-структурними матрицями називаються матриці одного порядку з вдинаковими властивостями, що складаються з різних елементів, і містять відповідні підматриці з одинаковими порядками та іластивостями.

Теорема. Для квадратних матриць показників степені (3) і інаків косинусу (5) порядку {М/2}х{Н/2}, обчисленних на основі іеріодичності та симетричності ЕБ ДПФ з переставленням рядків і стовпців за допомогою підстановок з циклічного розкладу, існує еквівалентність структур для довільного обсягу N послідовності ДПФ.

Наслідок. Матриця показників степені (3) експоненціального 5азису ДПФ послідовностей довільного обсягу і відповідна матриця інаку синуса (4) порядку ^хЫ} мають еквівалентні матричні структури при переставленні рядків і стовпців за допомогою іідстановок з циклічного розкладу.

Отже, сформовані за циклічним розкладом підстановки матриця юказників степені Ур ЕБ ДПФ послідовностей довільного обсягу і идповідна матриця знаку 2’с, 2’ъ, розбиваються на еквівалентні ілочно-матричні структури, що визначають проведення обчислення щскретного перетворення Фур’є.

На початку обчислення об’єднуємо вхідні дані х°[і] (і=0(і)М-1) іа формулами:

хк [і]=хк'І[і]+хк‘1[{Г'і/2к‘1}-і]

(13)

хк[{Ы/2к}+!]=хкШ - хк'1[{ІМ/2к'1}-і],

(14)

хк[Ы/2+П=хкЧЫ/24ч]+хкЧЫ/2+Ш/2к1Н] , (15)

хк[Н/2ч^2к}+іІ=хк[К/2+і]-хк-ЧН/24^/2к,}-іІ, (16)

- для першого етапу к=1 об’єднання включає послідовне обчислення за формулами (13,14), де і=1,2,...,{М/2};

- для другого етапу к=2 об’єднання виконуються обчислення за формулами (13-16), де і=1,2,...,{М/4}; х’ІО^х^ОІ+х'ЧМ/^]; хЧИ/г] = х°[0] - х°[Ы/2];

- для елементів підмножин 52,54,55,86 третій етап к=3 об’єднання включає послідовне обчислення за формулами (13-16), де і= 1,2,... ,{Ы / 8}.

Процедура отримання добутку значень синуса, косинуса експоненціального базису на матрицю стовпець одержаних об’єднаних значень визначається структурою матриці показників Ур. Розглянемо ДПФ послідовностей для обсягів, що належать елементам підмножинк Б1 з числом циклів підстановки 5=1. У випадку парного порядку п, де п=(Ы-1)/2 матриці Ур, матимемо еквівалентно-блочну матрицю Ур другого порядку (6). За теоремою еквівалентності структур матриць матриця Ур порядку {IV/2}х{М/2}, за структурою відповідає матриц знаку косинуса І'с. Тому для значень косинуса експоненціальною базису ДПФ обчислення добутку можемо проводити з використання?, блочно-циклічної структури другого порядку.

М1= (А+В)/2х(х0+х1), Хо=М! +М2, (17)

М2= (А-В)/2х(хо-х,), Х,=М! - М2 , (18)

де Хо, X! - підматриці стовпці об’єднаних вхідних значень (13-16); Хо X! - підматриці стовпці вихідних значень.

• Тобто, для обчислення добутків підматриць значень косинус; експоненціального базису на матрицю стовпець об’єднаних вхіднш значень використовуєм блочно-матричну структуру та швидк алгоритми згорток для обсягів п=(Ы-1)/4 або п=(>М)/2.

Для значень синуса експоненціального базису ДПФ проведенш обчислення за матрицею знаків синусу 2’б і матрицею показників V] для порядку (Ых]\0 виконується за співвідношеннями (17,18), : врахуванням рівності В = -А блочних елементів.

Аналогічно, для елементів обсягу N. що належать підмножинар 52,53,54,55,56, ефективне обчислення добутку підматриць значень

Хо А в Хо

х, В А Хі

юсинуса, синуса експоненціального базису на підматрицю стовпець >б’єднаних вхідних значень забезпечується блочно-матричною структурою та швидкими алгоритмами згорток.

На завершальному етапі, об’єднуючи з попередніх етапів щержані накопичені добутки і компонуючи дійсні та уявні частини, іроводим формування вихідних значень дискретних коефіцієнтів Фур’є.

Приблизна кількість дійсних операцій М, А запропонованого узагальненого підходу обчислення ДПФ дійсних послідовностей іовільного обсягу визначається з окремими синусними -{N1 і сосинусними частинами -{N/2} і складає

М и ( ІЦі +11^ ) ад + ( +ІкіЩ ) {м/2}, (19)

І і І і *е М -кількість дійсних множень; р.; - кількість множень при виконанні диклічної згортки обсягу П; або (п;/2); к; - кількість підматриць пі (ратних елементів; - кількість множень при виконанні циклічної згортки обсягу Пі або (п,/2) і-ої періодичної підматриці,

А » 314/2 + (2аі+Екіаі+ 2!рі+£1п;){м)+ і і і і

+ (2^+1к;а;+2р1+11П;){М/2), (20)

і і і і

це А -кількість дійсних додавань; а, - кількість додавань при виконанні циклічної згортки обсягу п; або Ц/2}; к; - кількість підматриць п, кратних елементів; а( - кількість додавань при виконанні циклічної згортки обсягу П; або {п,/2}; р, - кількість додавань для підматриць п: кратних елементів; ІПі- кількість об’єднань підматриць обсягів Пі.

По суті, запропоноване ШПФ послідовностей довільного обсягу звелось до проведення обчислення циклічних згорток над косинусними і синусними частинами експоненціального базису ДПФ послідовностей повільного обсягу N. В роботах Ч. Рейдера, Ш. Винограда розглянуто ефективне обчислення ДПФ на основі циклічних згорток для обсягів, рівних простому числу, степені простого числа, добутку взаємно-простих чисел. Так, проведення обчислення ДПФ за Рейдером для простих значень обсягу за допомогою циклічної згортки використовує переставлення за допомогою первісного кореня і=(^) тосИМ. Тобто, ], і індекси переставленої і вхідної послідовності, де і=0( 1)1Ч-2, §^'’=1, ^1 (0<к<Ы-1). Алгоритм Винограда використовує для кожного обсягу конкретні обчислення і модифікації з використанням китайської теореми про залишки, властивостей прямого добутку матриць та алгоритмів циклічної згортки.

В основу запропонованого автором обчислення ДПФ покладено новий підхід до проведення процедури обчислення на базі декомпозиції на матрицю показників і матриці знаків експоненціального базису ДПФ для послідовностей довільного обсягу, що розширило значення обсягів перетворень ДПФ за єдиною схемою, і є подальшим розвитком в теорії швидких алгоритмів обчислення ДПФ.

В роботі показано, як на основі переставлення елементів вхідної послідовності, що визначається за підстановкою на основі перших двох рядків матриці показників (2,3), можливе обчислення ДПФ різного обсягу. Визначення переставлення при цьому не потребує спеціальних обчислень і для обсягів N. N/2 -простих чисел може формуватись елементарним відбором зростаючої з одиниці послідовності чисел (рис.2, табл.2).

Відмінність одержаного обчислення порівняно з алгоритмами Рейдера, Винограда, де розглядаєтья матриця порядку (НхИ), полягає в тому, що в даному алгоритмі розглядається квадратна матриця в два рази меншого порядку, а це вимагає відповідно меншого об’єму пам’яті та кількості елементів аналізу. Крім того, в загальному випадку в даному алгоритмі в основу приведення до блочної структури матриці показників експоненціального базису запропоновано переставлення за допомогою циклічного розкладу Р(г), що приводить до однотиповогс підходу організації обчислення ДПФ послідовностей довільного обсягу.

Виконання даного підходу окремо для косинусної і синусної частин експоненціального базису дає можливість обчислювати не тільки ДПФ дійсних і комплексних вхідних послідовностей, але і дискретне перетворення Хартлі послідовностей довільного обсягу. Окреме проведення обчислень забезпечує спрощення розробка програмних засобів, дозволяє розпаралелювати процес обчислення тг гнучко використовувати даний підхід в різних типах обчислювальних структур.

Кількість дійсних арифметичних операцій множення М. додавання А та їх суми необхідних при виконанні запропонованогс підходу обчислення ДПФ дійсної послідовності невеликих обсягів N де двадцяти відліків, подано в таблиці і.

Таблиця 1.

Кількість операцій необхідних для виконання ДПФ

N 5 6 7 8 9 10 11 12

М 5 4 8 2 11 9 20 8

А 17 16 35 26 52 43 83 42

Сума 22 20 43 28 63 52 103 50

и

_____ продовження таблиці і.

N 13 14 15 16 17 18 19 20

М 20 24 24 10 56 20 38 16

А 117 107 103 72 133 104 185 112

Сума 137 131 127 82 189 114 223 128

У четвертому розділі розглянуто алгоритмічні і апаратні засоби та їх окремі елементи необхідні для виконання ефективного обчислення ДПФ послідовностей довільного обсягу. В узагальненій :хемі (рис.1) обчислення ДПФ послідовностей довільного обсягу на зснові декомпозиції ЕБ ДПФ можна виділити два етапи: генерації і зиконання. Етапи можуть виконуватись паралельно. На етапі генерації зиконується підготовка даних, вибір структури для конкретного обсягу N1, попереднє обчислення коефіцієнтів, що приймають участь в операціях множення, а на етапі виконання безпосередньо проводиться іроцедура швидкого перетворення.

Рис.1. Схема обчислення ДПФ послідовностей довільного обсягу.

Узагальнену схему ефективно застосовувати з використання; алгоритмів швидких згорток Винограда, зводячи поставлену задач обчислення перетворення Фур’є за допомогою більш коротших наборі даних.

Системні проробки, що включають алгоритмічні, програми апаратні рішення, входять в можливе розмаїття варіантів реалізап обчислювачів швидкого перетворення Фур’є послідовностей довільног обсягу. При цьому важливе значення надається організації процес виконання ШПФ. Генерація логічно пов’язаної послідовності адрес з допомогою формувачів визначає складність структури обчислювача. Н рис.2 подано схему елемента формувача адрес для обсягу прости значень послідовностей (табл.2).

Рис. 2. Схема формувача адрес Ф1:

ЗП1, ЗП2 -запам’ятовуючі пристрої; ЛІ, Л2 -лічильники; МІ, М2 мультиплексори; БП -блок пам’яті; ША -шифратор адреси; ІБ -імпульснк блок; ПД -подільник; ПК -пристрій керування; N -вхід обсягу перетворенні ТІ -вхід тактових імпульсів; Адр, Адр’ -адресні виходи.

Формувач генерує послідовність адрес для считування значеь косинусних, синусних функцій при обчисленні накопичення добутків об’єднаними значеннями. У випадку кількості циклів розкладу э> шифратор адресу ША аналізує закінчення формування послідовнос лінійок і змінює адресу блоку пам’яті БП для считування ще одн< лінійки адрес. Переставлення стовпців в таблиці 2 у відповідності д послідовності рядків утворює циклічні зліва матриці показникі експоненціального базису ДПФ.

Таблиця 2.

Формування послідовності рядків для елементів підмножини Б1

N=19, б=1 N=17, б=2

123456789 246897531 487315962 835629174 369741258 671582493 752934816 594168327 918273645 12 3 4 5 6 7 8 2 4 6 8 7 5 3 1 4 8 5 13 7 6 2 8 17 2 6 3 5 4 3 6 8 5 2 14 7 6 5 17 4 2 8 3 5 7 2 3 8 4 16 7 3 4 6 18 2 5

Важливим елементом виконання обчислення ДПФ юслідовностей довільного обсягу є канонічний розклад обсягу юслідовності на множники. Визначення номерів кратних обсягу іеретворення проводиться фунціональним блоком канонічного розкладу ібсягу перетворення вхід N на множники к[і] (рис.З).

Рис.З. Схема канонічного розкладу числа на множники СРМ: -шифратор адресу; 2 -блок пам’яті залишків; 3 -суматор-накопичувач; 4 -Ілок порівняння; 5 -блок керування; 6 -регістр зсуву; 7 -елементи “і”; 8 -іультиплексор; 9 -блок пам’яті простих множників; N -вхід обсягу іеретворення; ТІ -вхід тактових імпульсів.

Канонічний розклад базується на використанні залишків ;ожного вагового коефіцієнта числа для послідовності простих чисел Лі та їх степенів, накопичене значення яких по вибраній вазі в ипадку кратності дорівнює простому числу Мі.

У додатку подано приклади обчислення ДПФ дійсни послідовностей на основі запропонованої декомпозиц експоненціального базису для N=5,14,15,20.

ОСНОВНІ ВИСНОВКИ РОБОТИ

1. Запропоновано новий підхід до аналізу і синтезу ефективни процедур обчислення ДПФ на основі декомпозиції експоненціальног базису ДПФ на матрицю показників і матриці знаків, що дал можливість виконання швидкого перетворення Фур’є послідовносте довільного обсягу.

2. Досліджено та проаналізовано матриці показникі експоненціального базису ДПФ, що для послідовностей обсягу рівном значенню простого числа є нормалізованим латинськими квадратамі Для інших обсягів можна виділити квадратні підматриці, в яких пр відповідному переіменуванні елементів підматриць в елемент натурального ряду одержимо нормалізовані латинські квадрат симетричні відносно головної діагоналі.

3. Виділено в залежності від значення обсягу послідовнос ДПФ шість підмножин з множини натурального ряду, що визначают порядок і структуру матриць показників степені експоненціальної базису ДПФ та узагальнюють їх особливості.

4. Запропоновано формування блочно-матричних структу матриці показників степені експоненціального базису ДПФ : допомогою циклічного розкладу підстановки, при цьому одержав блоки ганкелевих лівоциркулянтних квадратних підматриць.

5. Доведено еквівалентність структур відповідних порядк квадратних матриць показників степені і матриць знаків косинус синусу експоненціального базису ДПФ для послідовностей довільної обсягу, що дозволяє для косинусних і синусних частин застосовуваї процедури швидких циклічних згорток в процесі обчислення ДП« послідовностей довільного обсягу.

6. Розглянуто спільні етапи проведення об’єднання вхідні' значень, виконання згорток для окремих косинусних, синусних часть експоненціального базису ДПФ та формування вихідних значень ці обчислення дискретних коефіцієнтів Фур’є або дискретних коефіцієнт Хартлі.

7. Розроблено алгоритмічні, апаратні функціональні елемент проведення організації процесу обчислення дискретного перетворена класу Фур’є послідовностей довільного обсягу на основі елемент декомпозиції дискретного експоненціального базису ДПФ.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ . ЗА ТЕМОЮ ДИСЕРТАЦІЇ

. Процько І.О. Загальновизнаний приладний інтерфейс. - Львів: Край,

997. -28с.

!. Процько И.Е. Схема быстрого преобразования Фурье. //Контрольно-ізмерительная техника. -1989. -Вып.46. С. 100-104.

I. Луцик Я. Т., Процько I.O., Формування латинських квадратів на •снові показників степені експоненціального базису ДТФ. /Автоматика, вимірювання та керування. Вісник ДУ “ЛП”, №324.

998. С. 162-165.

L Процько І.О., Микитин І.П. Програмований пульт наладки цифрових іристроїв. //Технічні засоби автоматизації вимірів та керування іауковими дослідженнями. Вісник ЛПІ, №267. 1992. С.76-78.

>. Процько 1.0., Обчислення найпростіших коефіцієнтів Фур’є. /Контрольно-вимірювальна техніка. -1993. - Вып.50. С.84-86.

3. Патент 19531А Україна, G06F7/04. Пристрій канонічного розкладу шсла на множники. /Процько І.О., Рашкевич Ю.М. (Україна) /Заявл. ІЗ.02.96; Опубл. 02.12.97, Бюл. №6.

7. Патент 25782А Україна, G06F15/332, G01R23/16. Пристрій формування значень тригонометричних функцій для цифрового шалізатора спектра. / Процько І.О., Рашкевич Ю.М. (Україна) / Заявл. Ї5.12.96; Опубл. 30.10.98 , Бюл. №5. '

5. Патент 25783А Україна, G06F7/04. Пристрій для формування і іідбору переставлень. /Процько І.О., Рашкевич Ю.М. (Україна) /Заявл. >4.12.96; Опубл. 30.10.98, Бюл. №5.

). Prots'ko I.E. An algorithm for computing the discrete Fourier ransform. //Proceedings of LSPIC-90.-Riga, April 22-26,-1990.P. 123-127. 10. Protsko I.E. An Algorithm of an Odd Discrete Fourier Transform. /Proceedings of ITIAPR'90, -Lviv, October 22-28, -1990. v.2, P.75-77.

II. Процько I.О. Алгоритм швидкого перетворення Фур'є для різних іначень кількості відліків. //Праці другої Української конференції з івтоматичного керування "Автоматика-95". -Львів. -1995, -Том 1, С.41.

12. Процько І.О., Рашкевич Ю.М. Кодування мовних сигналів часовими іереставленнями в тональному каналі зв’язку. //Праці Міжнародної сонференції “Комп’ютерні технології друкарства. Алгоритми, сигнали, ;истеми -’’Друкотехн - 96”, -Львів. -1996. С. 110.

13. Процько І., Рашкевич Ю. Схема швидкого обчислення іеретворення Фур'є для змінної величини перетворень. //Праці сонференції "УКРОБРАЗ-96". -Київ, -1996. С.223-224 .

14. Процько І.О., Струк І.О., Швидке трансформування класу Фур’ для гармонічного аналізу акустичних сигналів. //Матеріали наукове технічної конференції “Фізичні методи та засоби контролю матеріалі та виробів “Леотест-98”. Славське Львівс. обл., лютий 1998. С. 130-132

АНОТАЦІЯ

Процько 1.0. Засоби швидкого перетворення Фур’є послідовносте довільного обсягу. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних нау за спеціальністью 05.13.05 - елементи та пристрої обчислювальної техніки т систем керування. Державний університет “Львівська політехніка”, Львії 1998.

Дисертація присвячена аналізу та розробці алгоритмічних т спеціалізованих апаратних засобів швидкого обчислення дискретног перетворення Фур’є послідовностей довільного обсягу на основі проведенн декомпозиції експоненціального базису ДПФ на показники степенів т матриці знаків. В роботі проаналізовано та одержано ганкелеві ліве циркулянтні матриці показників експоненціального базису ДПФ, доведено, щ матриці показників степені і знаків косинусу, синусу мають еквіваленті структури, приведено узагальнену схему обчислення ШПФ, розглянут спеціалізовані засоби та фунціональні блоки для виконання ДП< послідовностей довільного обсягу.

Ключові слова: дискретне перетворення Фур’є, швидке перетворенн Фур’є, матриця показників експоненціального базису, послідовніст довільного обсягу, спеціалізовані засоби.

Процько И.Е. Средства быстрого преобразования Фурь последовательностей произвольного размера. - Рукопись.

Диссертация на соискание ученой степени кандидата технически наук по специальности 05.13.05 - елементы и устройства вычислительно техники и систем управления. Государственный университет “Львівськ політехніка”, Львив, 1998.

Диссертация посвящена анализу и разработке алгоритмических специализированных аппаратных средств быстрого вычисления дискретног преобразования Фурье последовательностей произвольного размера н основании декомпозиции экспоненциального базиса ДПФ на матриці показателей степени и матрицы знаков. В работе получено ганкелевые леве циркулянтные матрицы показателей степени экспоненциального базиса ДП4 доказано, что матрицы показателей степени и знаков косинуса, синуса имею эквивалентные структуры, приведено обобщенную схему вычисления БП<І рассмотрено специализированые средства и фунциональные блоки дл выполнения ДПФ последовательностей произвольного размера.

Ключевые слова: дискретное преобразование Фурье, быстро

преобразование Фурье, матрица показателей экспоненциального базисг последовательность произвольного размера, специализированные средства.

Ihor Protsko, Means of the fast Fourier transform of series with arbitrary dimension.

The thesis is presented for the Ph.D. science degree competition in speciality 05.13.05 - elements and units of computer technique and control systems. State University “Lvivska Polytechnika”, Lviv, 1998.

The thesis is devoted to analysis and synthesis of algorithmic and special-purpose structural means of the fast DFT of series with arbitrary dimension. Many efficient algorithms have been designed for composite transform sizes, such as the Cooley-Tukey FFT algorithm, the Good-Thomas prime factor algorithm, etc. The Good-Tomas prime factor algorithm decomposes the computation of the FFT into small-size FFT’s. However, this algorithms use the library of different small-size FFT. The general scheme of the fast calculation DFT of series with arbitrary dimension is derived in this work. The synthesis of FFT algorithm is based on the decomposition of the matrix of powers of discrete exponential basis of the DFT with adding matrices of signs sine and cosine functions. Matrices of powers of exponential basis of the DFT are analysed and a set of natural numbers of transform dimensions is broken into six subsets. Hankel circular matrices of powers of discrete exponential basis of the DFT for cycles from the cycle decomposition of substitution are formed. The substitution is determined by the first two rows of matrix of powers. The equivalence of the block-structures matrix of powers of square matrix of exponential basis of the DFT and the accordance matrices of signs cosine and sine function is proved. In the results, the DFT of series with arbitrary dimension are computed as circular convolutions for sine and cosine parts of discrete exponential basis of the DFT. Algorithms of Rader and Winograd use circular convolutions also. Its derivation is complicated data indexing, especialy Winograd algorithms. The proposed algorithm uses the indexing permutation for the cycle decomposition of substitution. This simplifies the data indexing for series with twice less dimensions and the designing fast algorithms oT the discrete Fourier transform and discrete Hartley transform of series with arbitrary dimension. Operational counts for a first twenty transform sizes of real values data samples with using Winograd small-size cyclic convolutions is given. The proposed FFT algorithm for prime transform dimensions produce algorithms with minimum multiplicative complexity. In the Appendix, the algorithms for 5,14,15,20 sizes of real-valued series are given as examples. The subclass of the generalized small-size FFT algorithms can be used for prime factor algorithm (PFA) and for others large-size algorithms. The sequence of stages in the general scheme of the fast calculation of the DFT and special-purpose structural means to perform of the proposed FFT of series with arbitrary dimension are described.

Key words: algorithm, discrete Fourier transform (DFT), fast Fourier transform (FFT), discrete Hartley transform (DHT), matrix of powers of discrete exponential basis, series with arbitrary dimension, special-purpose means.

Підписано до друку 27.11.98р. Формат 60x90/16. Тир. 100. Львів. ДУ “Львівська політехніка ”