LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Уніфіковані засоби виконання швидких алгоритмів зсунутих косинусних та синусних перетворень

усовершенствованно прямые и косвенные методы синтеза быстрых алгоритмов сдвинутых косинусных и синусных преобразований второго - четвертого видов. Раскрыта взаимная связь между преобразованиями второго и четвертого видов, на основе которой синтезированы прямые быстрые алгоритмы косинусного и синусного преобразований четвертого вида. Показано, что они сокращают на 10-20% вычислительные затраты по сравнению с известными аналогичными алгоритмами и выгодно отличаются от последних простотой структуры – имеют простой граф, подобный алгоритму БПФ Кули-Тьюки по основанию два, и упрощенную базовую операцию, состоящую из одного умножения и двух сложений. Полученные быстрые алгоритмы косинусного и синусного преобразований четвертого вида отличаются от известных прямых алгоритмов быстрого косинусного преобразования второго вида тем, что содержат два дополнительных шага – умножения преобразуемой последовательности на фазовые множители и суммирования спектральной последовательности. При этом последний шаг имеет структуру, совпадающую с этапом суммирования алгоритмов второго вида, что обеспечивает простоту построения унифицированных средств выполнения сдвинутых преобразований.

Усовершенствован метод построения быстрых косвенных алгоритмов вычисления косинусных и синусных преобразований второго - четвертого видов. На основе формул разложения известных алгоритмов косинусных и синусных преобразований первого вида получены косвенные унифицированные алгоритмы сдвинутых косинусных и синусных преобразований с наименьшими вычислительными затратами среди известных алгоритмов данного класса. Показано, что алгоритмы БПФ, быстрого преобразования Хартли (БПХ) и быстрые косвенные алгоритмы косинусных синусных преобразований состоят из трех обобщенных шагов: перестановки данных, выполнения БПХ и выполнения операций поворотов вектора. При этом БПХ без потерь в количестве операций можно заменить парой быстрых алгоритмов косинусного-синусного преобразования первого вида. Таким образом, разработаны унифицированные быстрые алгоритмы выполнения БПФ, БПХ, а также БКП и БСП всех четырех видов.

С целью унификации средств ЦОС при выборе БКП как базового преобразования показано, что оно обеспечивает эффективное выполнение процедур фильтрации и корреляции сигналов по классической схеме: прямое БКП + модифицированное умножение спектров + обратное БКП.

Рассмотрены вопросы построения унифицированных средств выполнения ОТП. Установлено, что для расширения функциональных возможностей итерационного процессора БПФ-БПХ в направлении обеспечения возможности выполнения сдвинутых БКП и БСП второго, третьего и четвертого видов необходимо добавить в его базовое операционное устройство только один или два коммутатора (в зависимости от основания реализуемого алгоритма) и сигналы управления ими.

Поточные процессоры выполнения ОТП целесообразно строить на основе прямых быстрых алгоритмов. Установлено, что для расширения функциональных возможностей известного поточного процессора БКП второго вида с целью обеспечения выполнения преобразований четвертого вида достаточно дополнительно ввести в нем один умножитель и память констант (для умножения преобразуемой последовательности), одного сумматора (для шага суммирования), а также двух коммутаторов и сигналов управления ними.

Показано, что при реализации на сигнальном процессоре TMS320C50 косвенные быстрые алгоритмы косинусного и синусного преобразований имеют преимущество во времени выполнения по сравнению с прямыми алгоритмами. Они, алгоритмы, сокращают время выполнения на 18% и их целесообразно использовать в качестве основных при реализации на сигнальных процессорах. Время выполнения преобразований на универсальных ПЭОМ с помощью универсальной программы, разработанной на основе полученных в работе алгоритмов, практически совпадает с временем выполнения специализированной программы.

Ключевые слова: ЦОС, унификация, быстрые алгоритмы, ортогональные преобразования, специализированные процессоры.


ABSTRACT


Al-Hamarsheh Qadri Jamal. Unified means of fulfillment of fast algorithms of shifted cosine and sine transformations. - Manuscript.

Thesis on competition of a scientific degree of the candidate of engineering science on a speciality 05.13.13 - computers, system and web. - State university “ Lviv polytechnic ”, Lviv, 2000.

The thesis deals with development of unified means of fulfillment of fast algorithms of orthogonal angular transformations, including cosine and sine transformations shifted in temporary and frequent areas.

Direct and indirect methods of synthesis of fast algorithms of shifted cosine and sine transformations (DCT and DST) of second - fourth kinds for unified means of digital signal processing are improved. On their basis the number of fast algorithms is synthesized . These favourably differ from known algorithms by structural complexity and reduced computing costs. Particularly, the new fast DCT and DST algorithms of the fourth kind are obtained which have a simple structure and compared to known algorithms reduce of additions and Multiplication for given of point transformation.

It is detected, that DCT of the second kind and it's fast algorithms allow to calculate a convolution and correlation under the scheme: direct transformation + multiplication of spectra + inverse transformation. Therefore they can be used as base in DSP means' construction.

It is shown, that the synthesized algorithms allow to develop unified iterative, matrix and data-flow processors for fulfillment of orthogonal angular transformations - Fourier, Hartley, shifted cosine and sine - without essential increase of amount of the equipment and losses in productivity compared to one-transform oriented processors. Particularly, the extension of functionalities of iterative processors for fast Fourier-Hartley algorithms is attained at the expense of additional introduction one or two switches into it's base operational device (depending on the algorithm basis).

Key words: DSP, unification, fast algorithms, orthogonal transformations, specialized processors.

















Підписано до друку 23.10.2000р.


Формат 60х84 1/16. Папір офсетний.

Друк на різографі. Умовн. арук. арк. 1,4. Обл.-видав. арк. 0,9.

Тираж 100 прим. Зам. 440,


Поліграфічний центр

Видавництва Національного університету „Львівська політехніка”

вул. Ф.Колеси, 2, 79000, Львів