takya.ru страница 1
скачать файл

УДК 519.216.1/2

В.В. Сюзев, А.Я. Савельев, Д.Ю. Гудзенко

МЕТОДЫ ПРЕДСТАВЛЕНИЯ И ПРЕОБРАЗВАНИЯ СИГНАЛОВ В БАЗИСЕ ОБОБЩЕННЫХ ФУНКЦИЙ КРЕСТЕНСОНА
Рассмотрены методы синтеза и основные свойства различных дискретных базисных систем обобщенных функций Крестенсона в многоосновных системах счисления, а так же оригинальный скалярный способ построения быстрых алгоритмов анализа спектра в этих базисах. Теоретические результаты проиллюстрированы конкретными примерами.

E – mail: v.suzev @ bmstu.ru

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



Вычислительная и функциональная эффективность решения многих задач цифровой обработки сигналов спектральными методами существенно зависит от используемых систем базисных функций [1]. Поскольку ортогональных систем базисных функций существует неограниченное множество, то выбор рационального базиса является сложной теоретической и прикладной проблемой. В этих условиях особенно полезными могут оказаться параметрические базисные функции, содержащие в своей структуре один или несколько изменяемых параметров, влияющих на их свойства. Известным и важным примером таких базисов служит класс комплексных экспоненциальных функций Виленкина-Крестенсона [2], управление свойствами которых осуществляется с помощью вариации основания используемой системы счисления. Обобщение этих функций на многоосновную систему счисления (систему счисления с переменным основанием) и применение дополнительных способов их переупорядочения значительно расширяет ассортимент возможных базисных систем, среди которых можно искать базис, в наибольшей степени удовлетворяющий условию решаемой задачи обработки. В данной статье рассмотрены известные и новые методы формирования таких базисных систем и их основные свойства, а также оригинальные скалярные алгоритмы быстрого преобразования Фурье на их основе.

Пусть есть целые положительные числа, принятые в качестве оснований системы счисления, и целые числа k и i, задающие номер и аргумент обобщенной функции Крестенсона (ОФК) W(k, i), на интервале записаны в виде

(1)
где , а и являются m-ми разрядами позиционного представления чисел i и k ( и - младшие разряды) и лежат в диапазоне .

Тогда ОФК можно представить следующим выражением [3]:



(2)

где . Эти функции можно выразить и через произведение дискретных комплексных экспоненциальных функций (ДЭФ) :



(3)

где принято

Записанные таким образом ОФК обладают рядом интересных свойств. Приведем основные из них.

1. ОФК являются комплексными функциями с единичным модулем и фазой . Вычитая из фазы целое число , можно получить ОФК с минимальными фазами.

2. В ОФК переменные k и i равноправны, поэтому, если поменять их местами, функция не изменится, т.е.

(4)

В этом проявляется свойство двойственности ОФК относительно своих аргументов, которое приводит к симметричности матрицы значений ОФК.

3. Среднее значение любой ОФК, кроме нулевой, равно нулю, т.е.

(5)

Действительно,



. (6)

Но при



поэтому при , когда хотя бы один разряд , все произведение (6) будет равно нулю. Следовательно, выражение (5) справедливо.

Среднее значение нулевой ОФК равно единице, т.к. и

4. Произведение двух любых ОФК дает другую ОФК:



(7)

где


(8)

а произведение двух любых ОФК, одна из которых является комплексно-сопряженной, так же принадлежит ОФК:



(9)

где


(10)

В выражениях (8) и (10) и означают операции поразрядного модулярного сложения и вычитания, выполняемые по правилам:



(11)

Доказательство первого утверждения вытекает из следующих соотношений:





Вывод второго утверждения можно получить аналогичным образом, если учесть, что



Данное свойство отражает мультипликативность ОФК. В силу своей двойственности ОФК обладают мультипликативностью как по индексу k, так и по индексу i, т.е. являются дважды мультипликативными функциями.

5. Мощность любой ОФК равна 1:

(12)

Действительно, и поэтому формула (12) справедлива.

6. ОФК являются ортогональными функциями, т.к.

(13)

Для доказательства этого свойства сначала воспользуемся свойством мультипликативности в виде (9) и запишем сумму в (13) так:



Из этого выражения следует, что взаимная мощность двух ОФК с номерами k и λ равна среднему значению ОФК с номером α, определяемым соотношением (10). Но при номер не равен нулю и среднее значение такой ОФК будет равно нулю (см. (5)).

7. Система из N ОФК будет полной системой на интервале [0, N). Это следует из того, что в этом случае к системе нельзя будет добавить ни одной новой функции, которая была бы ортогональной одновременно ко всем остальным функциям системы.

Таким образом, N ОФК образуют полную ортонормированную мультипликативную комплексную дискретную базисную систему , пригодную для спектрального представления любых решетчатых сигналов ограниченной мощности. Пара ДПФ в базисе ОФК



(14)

а равенство Парсеваля



(15)

где - комплексно-сопряженная к величина.

Так как ОФК являются дважды мультипликативными функциями, то для их спектров справедливы все общие свойства, приведенные в работе [2]. В частности, выполняются теоремы о модуляции, сдвиге, свертке, корреляции и умножении сигналов. При этом, поскольку операция мультипликативности совпадает с операцией поразрядного сложения или вычитания по переменным модулям, то и операция обобщенного сдвига в этом базисе понимается в этом же смысле. Такие же операции должны быть использованы здесь и при записи обобщенных сверток и корреляций. Энергетические спектры в базисе ОФК инвариантны к такому обобщенному сдвигу.

ДПФ в базисе ОФК можно записать и в матричной форме.



,

,

где матрицы прямых () и комплексно спряженных () значений ОФК имеют вид:



Эти матрицы значений ОФК являются матрицами с полными фазами. Вычитая в них из степеней W числа, кратные , получим матрицы значений с минимальными фазами. Матрицы значений ОФК и будут симметрическими и унитарными. Они содержат действительные и комплексные элементы, причем комплексные попарно сопряжены. Нулевая строка и нулевой столбец этих матриц состоят только из единичных элементов.

Для ОФК по аналогии с функциями Виленкина-Крестенсона (ВКФ) и функциями Уолша [2] можно вести понятие ранга R, равного числу ненулевых разрядов кода номера функции k. Номер k функции или спектра ранга r можно тогда обозначить в виде . При r =1 в разложении k будет только один значащий разряд. Совокупность таких номеров можно записать так:

Так как здесь используется только одна переменная с индексом, то ее можно заменить на простую переменную µ и тем самым упростить запись:



Если значение µ (или km) равно 1, то номер и принадлежит следующему множеству значений: . Соответствующие ему функции



(16)

и зависят только от значения своего аргумента. Таким свойством обладали обычные функции Радемахера в системах Уолша и обобщенные функции Радемахера в системах ВКФ [2]. По аналогии эти функции так же можно считать обобщенными функциями Радемахера для системы счисления с переменным основанием. Тогда

. (17)

При введении обозначения функции Радемахера учтено, что с увеличением ее номера число точек изменения ее значений должно возрастать. Очевидно, что в полной системе ОФК (2) содержится только n обобщенных функций Радемахера и любая ОФК (2) может быть выражена через их произведение:



(18)

Пример 1. Построить систему ОФК для N=6 прямым методом и с помощью функций Радемахера.

Решение. В этом случае . Поэтому примем а . Тогда числа k и i запишутся в виде и , где , а . Значения i и k в десятичной системе и системе с основаниями 2 и 3 сведем в табл. 1.

Таблица 1





0

1

2

3

4

5



00

01

10

11

20

21

В соответствии с формулой (3) ОФК в этом случае записываются следующим образом:



Подставляя сюда все значения разрядов, получим систему из шести ОФК, которую представим в виде следующей матрицы значений с минимальными фазами:



(19)

Элементы и имеют следующие значения:



Теперь вычислим ОФК с помощью функций Радемахера. В соответствии с выражением (18) они будут равны:





После этого, пользуясь формулой (18), выразим все ОФК через эти функции:





Вычисление по этим формулам приводит к той же матрице значений ОФК (19).

_______________ . _______________

Возможен еще один способ вычисления приведенных ОФК. Он следует из матричной интерпретации выражения (3) в виде кронекеровского произведения соответствующих матриц ДЭФ:



, (20)

где


(21)
Поскольку такая система ОФК может быть выражена с помощью кронекеровского произведения, то ее можно назвать системой ОФК-Кронекера. В частном случае, при она переходит в систему ВКФ-Адамара [2].

Пример 2. Вычислить матрицу ОФК кронекеровским способом для условия предыдущего примера.

Решение. В этом случае

где

Поэтому

(22)

Матрицы (19) и (22) совпадают.

_______________ . _______________

Кронекеровская система является только одной из возможных полных базисных систем, использующих ОФК. На основе функций можно построить целое семейство базисов с симметрическими и унитарными матрицами, число которых зависит от конкретной величины N. Причем возможностей для организации базисных систем здесь больше, чем в ВКФ.

Можно отметить, кроме рассмотренных, по меньшей мере еще два способа построения таких базисов. Первый способ основывается на использовании формул (2), (18) или (20) для всех возможных комбинаций сомножителей в произведении для N. Если все сомножители разные, то он позволяет получить n! различных базисных систем ОФК-Кронекера.

Пример 3. Построить все системы ОФК-Кронекера для N=6.

Решение. В этом случае возможны два варианта разложения N=6 на множители: и . Для первого варианта система ОФК-Кронекера получена и приведена в предыдущих примерах. Для второго варианта имеем

.

Поэтому


(23)

Полученная матрица (23) отличается от матрицы (22).

_______________ . _______________

Второй способ формирования базисных ОФК-систем состоит в перестановке строк и столбцов любой матрицы ОФК-Кронекера, полученной первым способом, по закону определенной замкнутой операции над индексами k и i ОФК (напомним, что замкнутой считается такая операция над индексом, результат которой, изменяя порядок следования значений индекса, не меняет самого диапазона его изменения, т.е. результирующий индекс пробегает те же значения, что и исходный, но в другой последовательности). Такими операциями являются, например, инверсия кода индекса и кодирование Грея индекса, обобщенные на случай многоосновной системы счисления. Рассмотрим эти операции.

Если число k в многоосновной системе счисления представляется выражением (1), то инверсное ему число в этой же системе счисления записывается следующим образом:

(24)

где


Обобщенная инверсия, как и двоичная, и p-ичная инверсии, сводится к записи разрядов кода числа k в обратном порядке. Однако веса разрядов в многоосновной системе, где диапазоны изменения разрядов в общем случае не совпадают, должны быть изменены по закону (24). При обобщенная инверсия переходит в p-ичную инверсию и инверсное число имеет более привычный вид записи:



.

Пример 4. Найти инверсные значения целочисленного индекса, принадлежащего диапазону [0,6).

Решение. В этом случае 6=2· 3, поэтому а . В системе счисления с основаниями 2 и 3 числа k и будут иметь следующий вид: , . Их значения в различных формах записи приведены в табл. 2.

Таблица 2



k

0

1

2

3

4

5



00

01

10

11

20

21



00

10

01

11

02

12



0

3

1

4

2

5



00

01

11

10

20

21



0

1

3

2

4

5

_______________ . _______________

Код Грея числа k в многоосновной системе счисления вычисляется по следующему алгоритму: , который отличается от соответствующего алгоритма в системе счисления с одним основанием только использованием различных модулей при формировании разрядов кода.

Пример 5. Найти значения кода Грея для индекса k предыдущего примера.

Решение. Так как в этом случае , то а

. Результаты расчетов по этим формулам приведены в

табл. 2.


______________ . _______________

Рассмотренные операции позволяют получить новые полные ортонормированные мультипликативные системы ОФК. Для этого необходимо в матрице любой известной системы ОФК осуществить сначала перестановку строк, а затем – столбцов (можно и наоборот) по закону этих операций. В результате будут получены новые симметрические и унитарные матрицы ОФК. Перестановка только строк или только столбцов исходной матрицы приводит к несимметрическим результирующим матрицам.

Продемонстрируем процесс формирования симметрических матриц на конкретных примерах.

Пример 6. Построить матрицу ОФК из матрицы ОФК-Кронекера (19) с использованием операции обобщенной инверсии индексов.

Решение. В соответствии с данными табл. 2 произведем следующее переупорядочение матрицы (19): первую строку перемещаем на место второй, а вторую – на место четвертой, третью – на место первой, четвертую – на место третьей, а нулевую и пятую строки оставляем на своих местах. В результате получается следующая промежуточная матрица:

Эта матрица несимметрическая. Для получения из нее симметрической матрицы необходимо выполнить аналогичные перестановки её столбцов. Тогда будет получена следующая итоговая матрица:



(25)

Эта матрица ОФК является симметрической и отличается от исходной.

_______________ . _______________

Пример 7. Построить матрицу ОФК из той же матрицы ОФК-Кронекера (19) с использованием кодирования Грея.

Решение. В соответствии с данными табл. 2 в этом случае процедура перестановок существенно проще: нулевые, первые, четвертые и пятые строки и столбцы остаются на месте, а вторые и третьи меняются местами. В итоге получается следующая матрица ОФК:

(26)

Эта матрица так же симметрическая и по структуре не совпадает ни с матрицей (19), ни с матрицей (25).

_______________ . _______________

Результаты приведенных примеров показывают, что все матрицы, полученные различными способами, отличаются друг от друга по структуре, хотя и обладают одинаковыми общими свойствами. Это говорит о том, что рассмотренные способы не подменяют друг друга и являются инструментом для построения новых полных ортонормированных и мультипликативных базисных систем.

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

Остановимся сначала на случае представления числа отсчетов сигнала в виде произведения двух сомножителей: , где и являются целыми положительными числами. Преобразуем одномерный массив в двумерную таблицу с помощью подстановки . Эта подстановка соответствует представлению величины в позиционной системе счисления с основаниями и при числе разрядов . Тогда прямые ДПФ в базисе ОФК (14) без нормирующего множителя можно записать так:



Рассмотрим спектральные составляющие с номерами, изменяющимися по такому же закону, что и номера отсчетов, т.е. с



(27)

Используя свойства позиционных кодов в системе с переменным основанием, можно записать, что



(28)

где является, как и ранее в выражении (8), обозначением операции поразрядного суммирования по переменному модулю. Тогда в соответствии со свойствами мультипликативности и двойственности ОФК выражение (27) можно преобразовать к виду



Дальнейшее упрощение этого выражения зависит от значений приведенных в нем ОФК. Чтобы их получить, воспользуемся записью ОФК в виде формулы (2). Тогда имеем









Учитывая эти соотношения, получим следующую запись общего спектра сигнала:



(29)

Полученное выражение представляет собой алгоритм БПК для случая разложения N на два множителя.

Его можно записать в более удобной для вычислений форме, если обозначить внутреннюю сумму в выражении (29) в виде двумерной величины

. (30)

Тогда полный спектр будет равен



. (31)

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

Для БПК (29) число комплексных сложений и умножений равно:

, (32)

. (33)

В последней оценке числа умножений учтено, что умножения на единичные значения элементов матрицы ДЭФ, расположенные в её нулевой строке и нулевом столбце, являются тривиальными. Исключение из алгоритма умножений на другие тривиальные значения ДЭФ приводит к оптимизированным вариантам БПК. Для них оценка числа умножений еще более уменьшается.

Пример 8. Записать алгоритм БПК-Кронекера для .

Решение. Пусть и . Тогда массив сигнала превращается в таблицу

Алгоритм вычисления двумерного спектра в соответствии с общим алгоритмом (29) будет выглядеть так:



где учтено, что Промежуточные величины



и алгоритм БПК:



Дальнейшую последовательность действий можно представить в виде следующих двух этапов.



Этап 1. Расчет промежуточных величин:



Принимая получим



,



Таблица этих промежуточных величин будет иметь следующий вид:





Этап 2. Расчет искомого спектра:



поэтому при







Этим значениям соответствуют итоговые таблицы



В алгоритме выполняются 18 сложений и 8 умножений. Расчет по формулам (32), (33) дает 18 сложений и 11 умножений. Меньшее число реальных умножений связано с тем, что используемое в данном примере 2-точечное ДПФ выполняется без умножений. Сигнальный граф этого алгоритма приведен на рис. 1а.



Рис. 1. Сигнальный граф полного БПК-Кронекера

первого (а) и второго (б) типа для N=9

____________ . _______________


Если в свою очередь один из сомножителей или также раскладывается на два множителя, то приведенный алгоритм рекурсивно можно применить и для быстрого вычисления -точечных или -точечных ДПФ. Это повлечет за собой дополнительное прореживание сигнала и спектра и, в конечном итоге, к дополнительному сокращению объема вычислений. В общем случае при

,

одномерные массивы и с помощью подстановок



(34)

где , преобразуются в многомерные таблицы и , связь между которыми устанавливает следующее аналитическое выражение:



(35)

Это и есть полный алгоритм БПК-Кронекера с прореженным порядком следования отсчетов сигнала и спектра, содержащий уровней прореживания.

Реализация полного алгоритма БПК потребует выполнения

(36)

сложений и умножений. Некоторые из этих умножений могут оказаться тривиальными. Их исключение из алгоритма позволяет еще больше оптимизировать его.

В алгоритмах БПК-Кронекера (29) и (35) можно поменять последовательность суммирования и порядок следования индексов, в результате чего будут получены другие модификации БПК, обладающие такими же реализационными характеристиками. В частности, если порядок следования индексов и сумм изменить на обратный, что приведет к обработке транспонированных таблиц сигнала и спектра, то можно получить второй тип алгоритма БПК-Кронекера с естественным порядком следования отсчетов сигнала и спектра. Для такой алгоритм имеет следующий вид:

, (37)

а для он представляется следующим образом:



(38)




Пример 9. Записать алгоритм БПК-Кронекера второго типа для N=6.

Решение.Примем.Таблица сигнала

имеет следующий вид

а алгоритм БПК выглядит так:




где



Этап 1. Расчет промежуточных величин











Они образуют таблицу





Этап 2 . Расчет спектра





Результирующие таблицы имеют вид:



Сигнальный граф этого алгоритма приведен на рис. 1б. По сложности он совпадает с алгоритмом первого типа.

_______________ . _______________

В выражении для N порядок сомножителей можно изменить. Это приводит к БПК для других систем ОФК, отличных от систем Кронекера.



Таким образом, полученные результаты, включая методы формирования различных базисных систем на основе обобщенных функций Крестенсона в системах счисления с переменными основаниями, их свойства и быстрые алгоритмы вычисления спектра, составляют теоретическую основу для решения проблемы выбора оптимального базиса для широкого круга задач обработки сигналов (фильтрации, распознавания, сжатия, кодирования и т.п.) в условиях действия жестких ограничений на вычислительную сложность алгоритмов обработки. Особенно перспективным может оказаться применение этих базисов для исследования -линейных систем и -стационарных случайных процессов, использующих обобщенный временной сдвиг в виде поразрядного модулярного сложения с различными модулями.
СПИСОК ЛИТЕРАТУРЫ

  1. Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. – М.: Наука, 1989. – 496 с.

  2. Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. – М.: Сов. радио, 1975.- 208 с.

  3. Власенко В.А., Лаппа Ю.М., Ярославский Л.П. Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов. - М.: Наука, 1990. - 180с.


скачать файл



Смотрите также:
Методы представления и преобразвания сигналов в базисе обобщенных функций крестенсона
187.67kb.
Кафедра «Компьютерные технологии и системы» Дисциплина «управление в социальных и экономических системах» Отчётная работа
318.71kb.
Лабораторная работа №1 «Вычисление значений функций» студент 304 гр д/о Иванов Иван Иванович
23kb.
5 Даны векторы а(2;4;1), b(1;3;6), c(5;3;1) и d
17.84kb.
Сеточные методы для краевых задач и
112.3kb.
Дайте определение частично рекурсивных функций
389.08kb.
" ппос сигналов для вещания и радиоуправления " по курсу "Прием и обработка сигналов"
115.61kb.
Методы и приемы обучения иностранному языку на начальном этапе
61.83kb.
К вопросу об искажениях при электроакустическом преобразовании
41.28kb.
Минимизация системы булевых функций
103.13kb.
Практикум на языке программирования Лисп (4-й курс, осень 2013 г.) Задание Программирование вспомогательных функций Реализовать с помощью
26.08kb.
1. Право: понятие и признаки. Функции права
517.43kb.