Размещено на http://allbest.ru

Преобразования цифровых сигналов

1. Дискретное преобразование Фурье

преобразование фурье сигнал радиолокация

Дискретное преобразование Фурье устанавливает связь между временным и частотным представлениями сигнала при разложении его по гармоническим дискретно-экспоненциальным функциям.

Дискретные прямое и обратное преобразования Фурье по базисам из идеальных отсчетных функций

и

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

, k=0,…,N-1 (33)

и

, n=0,…,N-1 (34)

где {x[n]}- последовательность отсчетов сигнала

;

{X(k)} - последовательность спектральных коэффициентов

;

и - интервалы дискретизации сигнала x(t) и его спектра Фурье X(f); .

Соотношения (33) и (34) называются прямым и обратным дискретным преобразованием Фурье (ДПФ) последовательности {x[n]}-.

1.1 Дискретные экспоненциальные функции

В дискретных преобразованиях Фурье используется система дискретных экспоненциальных функций (ДЭФ), определяемых как

. (35)

Переменные k и n принимают целочисленные значения (0,1,…,N-1). Переменную k отождествляют с номером функции, а переменную n - с номером отсчета.

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

Образуем матрицу

, (36)

строки которой нумеруются переменной k, столбцы переменной n, а на пересечении k-й строки и n-го столбца записана величина .

Прямое и обратное ДПФ имеет следующую матричную форму записи:

; , (37)

где - вектор отсчетов сигнала, - вектор коэффициентов спектра ДПФ; T - оператор транспонирования .

Заметим, что для поворачивающего множителя справедливы следующие соотношения:

и, следовательно, , т.е. поворачивающий множитель первой степени является корнем N-й степени из единицы;

; .

Для любого N матрица F_N обладает следующими свойствами:

Матрица F_N ортогональна и унитарна:

;

I_N- единичная диагональная матрица.

Матрица F_N- симметрична: .

, где Q_N- симметричная матрица перестановок

.

Сопряженная матрица имеет вид .

Обратная матрица имеет вид

.

Для формирования обратной матрицы необходимо прочесть в обратном порядке элементы с отличными от нуля степенями (kn 0) строк матрицы F_N .

Например:

.

Мультипликативность

;

.

При умножении любых двух строк (столбцов) матрицы ДЭФ получается строка (столбец) той же матрицы. Номер строки (столбца) равен сумме номеров сомножителей.

Факторизуемость. Для любого N, разложимого в произведение отличных от 1 чисел N₁ и N₂, матрица функций ДЭФ порядка N представима в виде



или в виде

,

где и - матрицы перестановок, отвечающие транспонированию прямоугольных матриц соответственно размеров (N₁N₂) и (N₂N₁); - диагональная матрица, образованная последовательностью поворачивающих множителей

1.2 Свойства ДПФ

2. Цикличность. Последовательность коэффициентов ДПФ является периодической последовательностью

.

Последовательность отсчетов сигнала, полученная обратным ДПФ (ОДПФ) из ее коэффициентов также периодична

. (38)

Это свойство следует из периодичности ядра преобразования .

3. Симметрия.

;

;

. (39)

Эти соотношения показывают, что понятия симметрии четности и нечетности для последовательностей, порождаемых ДПФ, в отличие от непрерывных сигналов определены не относительно точки ноль, а относительно точки с номером (N/2). В силу целочисленности номеров элементов последовательности смысл четности и нечетности зависит от того, является количество элементов последовательности N четным или нечетным.

Варианты симметрий для одномерных ДПФ показаны на рис. 5 .

N - четное N - нечетное

Рис. 5

4. Теорема сдвига (инвариантность относительно сдвига во времени и частоте).

Пусть - последовательность, образованная из последовательности циклическим сдвигом на отсчетов. Тогда справедливо соотношение

. (40)

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

Аналогичное свойство справедливо и для частотной области

. (41)

5. Интерполяция. Спектр последовательности, полученный раздвиганием и дополнением нулями элементов некоторой исходной последовательности, образуется с помощью интерполяции отсчетов ДПФ исходной последовательности.

Рассмотрим последовательность g[n], состоящую из MN отсчетов, из них ( M--1) отсчетов являются нулевыми и расположены между отсчетами исходной последовательности x[n]:

Спектр такой последовательности, с учетом только ненулевых компонент, имеет вид

(42)

и представляет повторенный M раз спектр исходной последовательности X(k).

Пример. Зададим {x[n]} = {7, 5, 6, 9}. Спектр ДПФ такой последовательности имеет вид {X(k)}= {27, (1+j4), -1, (1-j4)}. Разреженная нулями последовательность {g [n]} ={7,0,5,0,6,0,9,0} имеет спектр ДПФ в виде периодического (повторенного 2 раза) спектра исходной последовательности: G ={27, (1+j4), -1, (1-j4), 27, (1+j4), -1, (1-j4)}. Образуем удлиненную последовательность {x₁[n]}=(7,5,6,9,0,0,0,0), дополнив исходную последовательность x[n] N нулями. Спектр ДПФ удлиненной последовательности будет иметь в своем составе компоненты спектра исходной последовательности:

{X₁(k)}= {X₁(0)=27; X₁(1)=(4,14-j15,9); X₁(2)=(1+j4); X₁(3)= (9,83-

-j3,89); X₁(4)=-1, X₁(5)=(9,83+j3,89); X₁(6)=(1-j4); X₁(7)=(4,14+j15,9)}.

Четные компоненты спектра удлиненной последовательности совпадают с аналогичными значениями спектра исходной последовательности. Нечетные компоненты спектра удлиненной последовательности можно рассматривать как результат интерполяции.

6. Теорема отсчетов. Периодическое M кратное повторение исходной последовательности приводит к увеличению в M раз значений спектральных компонент её ДПФ, размещению их с шагом M и дополнением остальных позиций спектра нулями:

,(43)

где - символ Кронекера.

Пример. Периодически продолжим исходную последовательность {x[n]}=(7,5,6,9), образуя последовательность {x₂[l]}=(7,5,6,9,7,5,6,9). Спектр ДПФ такой последовательности имеет вид

{X₂(k)}= (2[27,0,(1+j4),0,-1,0,(1-j4),0]).

Аналогично для периодически продолженного спектра ДПФ получаем

. (44)

7. Децимация. Пусть {X_NM(k)} - множество коэффициентов спектра ДПФ последовательности {x[n]; n=0,1,…,NM-1}:

,

m = 0,1,…,M-1; n = 0,1,…,N-1. (45)

Рассмотрим N отсчетов, взятые с шагом M, децимированной последовательности x'[n], полученной через обратное ДПФ. Для m=0 получим:

Отсюда можно получить выражение для спектра децимированной последовательности

. (46)

8. Теорема о перестановках. Если P не имеет общих делителей с N, то

, (47)

где . Эта теорема является аналогом теоремы о масштабах интегрального преобразования Фурье. Но если изменение масштаба сигнала, например, растяжение сигнала по координате в P раз, приводит к сжатию его спектра Фурье в P раз, то для дискретных последовательностей и их ДПФ это соответствует перестановкам элементов последовательностей.

9. Линейность. Пусть даны две последовательности и , для которых ДПФ равны соответственно и . Спектр взвешенной суммы последовательностей a + b= равен аналогичной взвешенной сумме спектров:

= a + b. (48)

10. Теорема о свертке. Спектр свертки двух последовательностей и равен произведению спектров и сворачиваемых последовательностей:

. (49)

Теорема позволяет вычислить циклическую свертку y[l] при помощи ДПФ по формуле

{y[l]} = ДПФ^-1(ДПФ{x[n]} ДПФ{h[n]}).

11. ДПФ вещественной последовательности. Пусть {x[n]} - вещественная последовательность. ДПФ такой последовательности имеет следующие особенности:

Спектральные коэффициенты комплексно сопряжены относительно N/2

,

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

Если x[n] - четная последовательность, т.е. x[n]=x[-n], то спектр ДПФ {X(k)} также представляет собой вещественную последовательность.

Если x[n] - нечетная последовательность, т.е. x[n]=-x[-n], то {X(k)} представляет собой чисто мнимую последовательность.

Данное свойство позволяет при помощи одного преобразования вычислить ДПФ двух действительных последовательностей, либо использовать N/2 -точечное преобразование для вычисления спектра N точечной последовательности.

1.3 Разновидности ДПФ

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

, (50)

где w[n] - весовая последовательность. КПФ зависит от двух параметров: целочисленного временного индекса n и значения непрерывной частоты . КПФ является периодической функцией с периодом 2. Модуль часто называют спектрограммой.

Дискретизация КПФ в частотной области в точках приводит к дискретному кратковременному преобразованию Фурье, которое можно трактовать как R-точечное ДПФ функции (x[n-m]w[m]), N R:

,

, . (51)

При равенстве размеров ДПФ и массива анализируемых данных N = R получаем взвешенное ДПФ

. (52)

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

,

,

где - диагональная матрица.

Пример. Рассмотрим обратное, двумерное ДПФ - точечной последовательности, заданной соотношением

, .

Последовательность выражается следующим образом

2. Алгоритмы вычисления дискретного преобразования Фурье

Существует два класса алгоритмов вычисления преобразований Фурье: обычное дискретное преобразование Фурье (ДПФ) и быстрое дискретное преобразование Фурье (БПФ).

Дискретным преобразованием Фурье условно называют непосредственное вычисление формул (33, 34). При этом допускают все известные способы распараллеливания векторно-матричных операций. Если пользоваться обычным правилом умножения матрицы на вектор, то вычисления векторов x и X требуют N ² операций комплексного умножения и N(N - 1) операций комплексного сложения.

2. Быстрое преобразование Фурье включает набор эффективных алгоритмов, предназначенных для вычисления ДПФ. В основе алгоритмов лежит стратегия divide et impera (разделяй и властвуй). Идея БПФ по своей природе является алгебраической и заключается в следующем. Величина N, определяющая длину входной последовательности отсчетов, раскладывается на сомножители, затем вычисляются отдельные ДПФ меньших длин, чем N, из которых потом формируется выходная последовательность. Происходит так называемое расщепление исходного алгоритма на комбинацию подобных алгоритмов меньшего размера.

Положим, что для N-точечной последовательности нужно вычислить ее ДПФ и что N представляет собой составное число

,

где {r_i } - это набор множителей числа N, которые не обязательно являются простыми. Алгоритм расщепления для вычисления такого ДПФ через комбинацию преобразований меньших размеров потребуют число операций, пропорциональное . Такие алгоритмы называются алгоритмами быстрого преобразования Фурье . Наиболее важный частный случай имеет место, когда . Для БПФ число операций в этом случае пропорционально .

Разберем возможность сокращения числа операций при вычислении ДПФ на примере двух сомножителей N = N₁ N₂.

2.1 БПФ по смешанному основанию

ДПФ последовательности, N = N₁ N₂ запишется в виде

.

Представим входные n и выходные k индексы в смешанной системе счисления с основаниями N₁ N₂:

; , где , .

Последовательности входных и выходных отсчетов преобразуются в двумерные массивы:

,, ;

,, .

После подстановки алгоритм ДПФ представляется в виде

 (53)

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

Для всех строк матрицы вычисляются N₂ точечные ДПФ.

Каждый элемент полученной матрицы умножается на фазовый множитель .

Для всех столбцов матрицы, полученной на втором этапе, вычисляются N₁ точечные ДПФ.

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

Вычислительные затраты при таком способе вычисления ДПФ равны: количество операций умножения равно ; сложений .

Если числа N₁ и N₂ являются составными, то алгоритм БПФ применяется рекурсивно. При этом на каждом шаге рекурсии БПФ сокращает число операций.

Пример. Пусть N = 6 = 23, N₁ = 2, N₂ = 3. Входная последовательность имеет вид

{x[n]; n = 0,..,5} = [1,1,1,-1,-1,-1]. Требуется вычислить ДПФ по смешанному основанию.

Элемент матрицы двумерного массива в этом случае равен

d[n₁,n₂] = x[2n₂ +n₁], n₁=0,1; n₂ = 0,1,2.

Сама матрица имеет вид

.

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

.

После умножения элементов этой матрицы на поворачивающие множители , k₂ = 0,1,2, получаем матрицу

.

Применение двухточечного ДПФ к столбцам матрицы, полученной на втором этапе, приводит к следующему результату

Спектр ДПФ равен

.

Описанный алгоритм предпочтительнее непосредственного прямого вычисления ДПФ, поскольку при этом требуется меньше арифметических операций. Действительно, сложность алгоритма ДПФ по смешанному основанию определяется сложностью вычислений N₁ ДПФ размера N₂ , N₂ ДПФ размера N₁ и N₁ N₂ умножений на фазовые множители. Вычислительные затраты при таком способе вычисления ДПФ равны: количество операций умножения равно ; сложений . Прямое вычисление ДПФ потребовало бы N² операций комплексного умножения и N(N-1 ) операций комплексного сложения.

Если числа N₁ и N₂ являются составными, то алгоритм БПФ применяется рекурсивно. При этом на каждом шаге рекурсии БПФ сокращает число операций.

2.2 Алгоритм Гуд-Томаса

Рассмотрим случай, когда необходимо вычислить N-точечное ДПФ, причем N=N₁N₂ и числа N₁ и N₂ являются взаимно простыми, т.е. НОД(N₁N₂)=1. В этом случае применим алгоритм Гуд-Томаса (ГТ) с использованием простых делителей. Используется отображение обрабатываемой последовательности в двумерную таблицу, позволяющая использовать двумерное преобразование Фурье. Отобразим последовательности входных x[n] и выходных X(k) отсчетов в двумерные массивы



по следующим правилам:

- для индексов входного сигнала

; (54)

-для индексов выходного сигнала

. (55)

Обоснованность применения такого отображения доказывается следующим образом. Согласно китайской теоремы об остатках [ 1 ] существуют такие целые m₁ и m₂, что выполняется равенство , где . С другой стороны, для индексов выходного сигнала справедливо равенство

,

где Q₁ целая часть, дополняющая k₁ до k; Q₂-целая часть, дополняющая k₂ до k.

ДПФ двумерного массива данных запишется как

 (56)

С учетом того, что и получаем

и

.

Теперь видно, что ДПФ двумерного массива входных данных можно вычислить с помощью двумерного ДПФ

. (57)

Элементы и являются простыми корнями из единицы степеней N₁ и N₂ , задающие соответственно N₁ -точечное и N₂-точечное преобразования Фурье.

Вычислительная сложность алгоритма оценивается как N(N₁ + N₂) операций умножений и сложений.

Пример. Необходимо вычислить ДПФ последовательности {x[n]; n=0,…,5} = (1,1,1,-1,-1,-1) с использованием алгоритма ГТ.

Длину обрабатываемых отсчетов N можно разложить на два взаимно простых множителя множителя

N = 23 = N₁N₂, N₁ = 2, N₂ = 3; НОД (N₁,N₂) = 1.

Алгоритм ГТ запишется как

,

n₁ = 0,…,N₁ , n₂ = 0,…,N₂ ; k₁ = 0,…,N₁ , k₂ = 0,…,N₂

Перестановка входных данных имеет вид:

n = n₁ m₂ N₂ + n₂ m₁ N₁ = n₁ m₂ 3 + n₂ m₁ 2,

где коэффициенты m₁ и m₂ определяются из решения диофантового уравнения

m₂ N₂ + m₁N₁ = 1 m₂ 3 + m₁2 = 1

Для решения диофантового уравнения применим алгоритм Евклида

3 = 21 + 1 или 1 = (1)3 + (-1)2,

откуда получаем, что m₁= -1 и m₂ = 1.

Матрица данных после перестановки имеет вид

Матрица внутреннего ДПФ равна

, k₂ = 0,…,N₂, n₂ = 0,…,N₂.

Вычисление внутреннего ДПФ приводит к результату

Матрица внешнего ДПФ равна

, k₁ = 0,…,N₁, n₁ = 0,…,N₁.

В результате вычисления внешнего ДПФ получаем

Связь выходных отсчетов преобразования ГТ {X(k₁,k₂)} и отсчетов прямого ДПФ {X(k)} определяется исходя из соотношения

k = k₁ N₂ + k₂ N₁ mod N

и имеет вид

.

Откуда получаем значения спектральных коэффициентов прямого ДПФ

.

2.3 Алгоритмы БПФ по основанию два

Наибольшее распространение в цифровой обработке сигналов получили алгоритмы БПФ по основанию 2. Известны два способа организации вычислений в алгоритмах БПФ по основанию 2: метод прореживания по времени и метод прореживания по частоте.

Алгоритм БПФ с прореживанием по времени. Обрабатывается исходная последовательность ,,

На первом шаге алгоритма исходная последовательность разбивается на две последовательности длиной N/2, соответствующие четным и нечетным отсчетам

,

, .

Вычисление N-точечного ДПФ в этом случае сводится к двум N/2- точечным ДПФ N/2 умножениям на поворачивающие фазовые множители и N операций сложения:



. (58)

Использую свойства:

и ,

Получаем

. (59)

Для имеем (рис. 6)

(60)

На втором шаге данная процедура применяется для замены двух N/2-точечных ДПФ на четыре N/4- точечные ДПФ, N/2 умножений на W^k и N сложений и т.д. Эта процедура продолжается до тех пор, пока не останутся только двухточечные ДПФ. Заметим, что на каждом шаге происходит разделение данных на четные и нечетные последовательности. В итоге это приводит к тому, что отсчеты исходной последовательности должны быть предварительно переставлены по закону инверсии двоичного кода индекса.

Граф алгоритма БПФ с прореживанием по времени для N=8 показан на рис. 7 .

Матричная интерпретация алгоритма, учитывающая свойство факторизации матрицы ДЭФ имеет вид

X = Ф₃Ф₂Ф₁Рx,

где слабозаполненные матрицы Ф₃Ф₂Ф₁ и оператор перестановки P равны

,,

Рис. 6



Рис. 7

Таким образом последовательное применение метода к вычислению N-точечных ДПФ, N=2^m, приводит к m = log N шагам, на каждом из которых 2ⁱ2^m-i -точечных ДПФ сводятся к 2ⁱ⁺¹2^m-i-1-точечным ДПФ, N сложениям и N/2 умножениям на поворачивающие множители. Следовательно, сложность N-точечного ДПФ методом прореживания по времени составляет (N/2)log N операций комплексного умножения и (N log N) операций комплексного сложения. Если учесть все тривиальные умножения на поворачивающие множители, то вычислительные затраты будут еще меньше.

Алгоритм БПФ с прореживанием по частоте. В алгоритме прореживания по частоте исходная последовательность разбивается на две: одна состоит из всех первых N/2 отсчетов, другая - из N/2 последних отсчетов. Выражение для ДПФ принимает вид

(61)

Для четных k = 2k` и нечетных k = 2k`+1, k`=0,…, N/2 -1 индексов коэффициентов преобразования получаем

(62)

для четных k и

(63)

для нечетных k.

На втором шаге данная процедура применяется для замены двух N/2-точечных ДПФ на четыре N/4- точечные ДПФ, N/2 умножений на W^k и N сложений и т.д. Процедура расщепления продолжается до тех пор, пока не останутся только двухточечные ДПФ. На каждом шаге происходит разделение данных на две части, содержащих соответственно первую и последнюю половинки обрабатываемой части. В итоге это приводит к тому, что отсчеты выходной последовательности спектральных коэффициентов будут переставлены по закону инверсии двоичного кода индекса.

Вычислительная сложность алгоритмы такая же как и у алгоритма с прореживанием по времени.

Граф алгоритма БПФ с прореживанием по частоте для N=8 показан на рис. 8 . Метод с прореживанием по частоте не требует предварительной перестаноки входных отсчетов. Эта особенность может быть использована для организации конвейерной обработки данных, что особенно удобно для спектральной обработки сигналов в реальном масштабе времени.

2.4 БПФ для N-простое число

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

Свойство периодичности экспоненциальных функций с точки зрения модульных операций можно представить следующим образом

Рис. 8



Рис. 9

. (64)

Для любого целого числа a принимающего значения из множества (1,2,…, N-1), N-простое число, справедлива теорема Ферма .

Тогда . Отсюда следует периодичность элемента с периодом N-1:

.

Простое целое число N позволяет определить конечное поле GF(N). Определим в этом поле примитивный первообразный элемент . Тогда, для любого целого m, множество чисел является перестановкой множества (1,2,…, N-1).

Рассмотрим ДПФ

Выделим отдельно нулевой спектральный коэффициент . Остальные коэффициенты преобразования представим в виде

. (65)

Представим фазовые поворачивающие множители W^f в виде множества {f}, отражающего значения степени поворачивающего множителя. Матрица множества индексов поворачивающих множителей [f] является матрицей циркулянтом. Тогда ДПФ последовательности запишется как

.

Определим перестановку

. (66)

Применим такую перестановку к элементам последовательности обрабатываемых отсчетов , образуя новую последовательность

.

Вычислим ДПФ последовательности h

. (67)

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

. (68)

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

H= ОДПФ_N-1{ДПФ_N-1{h} ДПФ_N-1{g}}. (69)

Пример. Пусть N=5, . Определим первообразный элемент . Из соотношения следует, что перестановка имеет вид

Последовательности h и g соответственно равны

, .

ДПФ последовательности h представляется как

В данном примере для вычисления циклической свертки можно использовать БПФ для N=4. Полный спектр ДПФ определится как

Схема вычисление ДПФ через свертку для простого N представлена на рис. 9 и носит название схемы Рейдера.

2.5 ДПФ на основе алгоритма ЛЧМ-Z фильтрации

Покажем возможность вычисления ДПФ цифрового сигнала через операцию свертки, используя свойства подобия дискретных экспоненциальных функций и ЛЧМ сигналов. Рассмотрим выражение

.

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

. (70)

Подставим в формулу для ДПФ полученное выражение

. (71)

В полученном выражении сумма может быть вычислена через операцию свертки

. (72)

Соответственно выражение для полного спектра с использованием оператора свертки имеет вид

. (73)

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

Часто такой алгоритм называют алгоритмом ЛЧМ-Z преобразования, подразумевая, что с его помощью можно эффективно вычислить Z-преобразование последовательности {x[n]}. Действительно, пусть N-точечная последовательность {x[n]} имеет образ Z-преобразования

По определению ДПФ заданной последовательности связано с Z выражением

. (74)

Зададим контур преобразования более общего вида

, (75)

где M-произвольное целое число (необязательно равное N), а A и W- произвольные комплексные числа. Обозначим через X_k искомые значения Z-преобразования при z = z_k

.

Подстановка в эту формулу выражения для произведения nk дает

или

, где . (76)

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

Дискретные ортогональные преобразования на конечных абелевых группах

Значительный интерес для цифровой обработки сигналов представляют Фурье-подобные преобразования в пространстве всех функций, заданных на конечной абелевой группе и принимающих значения в конечном коммутативном кольце или некотором поле K. Это пространство обозначим как . Определим в пространстве функции аналоги ДЭФ . Заметим, что экспонента является решением функционального уравнения над полем комплексных чисел с начальным значением . Решениями подобного уравнения над кольцом K дает функции, которые называются характерами и обозначаются . Каждый характер является гомоморфным отображением группы H в кольцо K. Если будем считать что размер группы , - простое число, и введем понятие как первообразного корня в степени в поле или кольце , тогда характер можно определить как:

,

где x принадлежит числовой циклической группе .

Классификация основных Фурье подобных преобразований

	Множество (Абелева группа)	Множество Фурье (поле, кольцо)
		Бесконечное поле комплексных чисел	Конечное поле комплексных чисел
			Поле Галуа	Модулярное кольцо
Бесконечное	Действительные числа	Интегральные преобразования	____	____
	Счетное множество целые числа	Z-преобразование, ДПЛ	Преобразования Лапласа-Галуа	___
Конечное	Циклическая группа	ДПФ в бесконечном поле	Теоретико- числовые преобразования (ТЧП)	ТЧП (модулярных групп)
	Прямо разложимая группа	Преобразования Уолша; Виленкина-Крестенсона; Виленкина-Крестенсона-Понтрягина (ВКП)	Преобразование ВКП, Уолша-Галуа)	ТЧП (модулярных групп)

Таблица 2. Классификация дискретных преобразований

Группа	Дискретное преобразование	Ядро преобразования (характер )
Порядок	Тип
	Циклическая	Фурье
		Уолша-Адамара
		Крестенсона - простое число
		Виленкина-Крестенсона (r - целое положительное число)
		Виленкина-Крестенсона-Потрягина

- декартово произведение множеств.

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

где .

Произвольный элемент представим как сумма

.

Следовательно, для всех возможных характеров группы справедливо равенство

где i = 1, 2, …, n - характеры подгрупп и следовательно все характеры исчерпываются функциями вида:

,

где ; .

Свойства характеров.

Инвариантность относительно группового сдвига:

.

Мультипликативность:

.

Симметричность:

.

.

Множество характеров , образуют ортонормированные базисы в пространствах и , относительно скалярных произведений

и

.

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

Условие существование корней N₁, N₂, … , N_n -й степени из единицы в конечных кольцах. Пусть и , тогда каждый корень q-ой степени является корнем N_i-й степени. Поэтому достаточно потребовать существование корня q -й степени из 1 в K, чтобы имелись все корни степеней N₁, N₂, … , N_n.

Пример. Пусть абелева группа . Тогда элементы этой группы отобразятся в отрезок [0,7] следующим образом:

Так как , то . Получим характеры

, образующие систему функций Адамара-Уолша

Пример. Пусть , . Элементы этой группы погружаются в отрезок [0,5] следующим образом ,

 , , .

Характеры группы определяются как

.

Придавая значения индексам x_i и _i из области их определения, получим

Обозначим и . Тогда, систему функций можно получить, используя операцию кронекеровского перемножения матриц.



Классификация Фурье подобных преобразований. В основу классификации преобразований удобно положить следующий принцип, введенный Понтрягиным Л. С. по инвариантному преобразованию функций. На множестве А значений аргументов ( в области определения функции) задается бинарная операция, причем такая, что А по этой операции является абелевой группой G. На множестве Ф значений функций задается пара таких бинарных операций, что Ф образует поле или в более общем случае - кольцо с единицей.

Базисные функции, определяющие ядра преобразований, могут быть выбраны различными способами. В основе Фурье-подобных преобразований лежит идея использовать характеры абелевой группы, соответствующей множеству А отсчетов заданной функции. Над полем комплексных чисел С характерами являются:

для бесконечной непрерывной (континуальной) абелевой группы вещественных чисел - комплексные экспоненты ;

- для бесконечной, но счетной, абелевой группы целых чисел - дискретные экспоненты ;

для конечной циклической группы порядка N - корень N -й степени из единицы, т.е. .

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

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

;

,

где - изображение (спектр) сигнала ; и ядра прямого и обратного преобразований.

Подставляя в выражения для интегральных преобразований комплексные экспоненты, получаем пару одномерных интегральных преобразований Фурье. Используя подстановку дискретной экспоненты и заменяя интеграл знаком суммы, а следовательно непрерывное время t дискретным , получим дискретное преобразование Лапласа (ДПЛ) или Z преобразование (преобразование Лорана). Используя характер конечной циклической группы порядка N, получим выражения для дискретного (прямого и обратного) преобразования Фурье (ДПФ) над полем комплексных чисел. В табл. 1 представлена классификация основных Фурье-подобных преобразований. В табл. 2 представлена классификация рассматриваемых преобразований и приведены их ядра в зависимости от порядка и типа абелевой группы G. Взаимосвязь спектров. Для линейных ортогональных преобразований возможен переход из одного ортогонального базиса в другой с помощью специальных алгоритмов перечета (вычисление ядра Фурье).

Рассмотрим взаимосвязь спектров Фурье и Уолша. Преобразование Фурье имеет вид:

.

Преобразование Уолша-Адамара запишется как

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

Пример. Вычислим ядро Фурье для

.

Сложнее определить взаимосвязь преобразований цифрового сигнала в полях комплексных чисел С и конечных полях Галуа GF(p). Предположим, что группа G_N определяет системы базисных функций над полями C и GF(p), т.е. определяет -преобразования в пространствах L₁(G_N, C) L₂(G_N, GF(p)). Обозначим спектральные коэффициенты, а также первообразные корни этих преобразований соответственно как X_F(k), _F и X_GF(k), _GF. Тогда взаимосвязь спектров можно определить через равенство

где - матрица преобразований значений спектрального коэффициента X_F в множество действительных чисел R;

.

При этом должны выполняться следующие соотношения относительно первообразных элементов

.

Если имеем дело с простым полем GF(p), то соотношения упрощаются

,

а оператор определяется из равенства ; , .

3. Преобразования Уолша - Адамара

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

Функции Уолша - Адамара

Исторически сложилось так, что в основе функций Уолша - Адамара лежат ортогональные бинарные матрицы Адамара H_N, которые определяются по простому правилу:

,

, и т.д.

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

; ,

где - оператор кронекеровского произведения матриц.

Рассматривая элемента матриц Адамара как отсчеты непрерывных меандровых сигналов, можно получить в функции Уолша - Адамара .

Матрица дискретных функций Уолша - Адамара , t = nt примет вид

=

Введем двоичное представление номера функции

и двоичное представление номера отсчета

.

Тогда функции Уолша - Адамара можно определить как

где - скалярное произведение векторов кодов номеров функции и отсчета, соответственно.

Например, пусть , , тогда и элемент матрица с координатами (3,2) равен had(2,3)=.

В зависимости от упорядочивания номера функций различают следующие системы ортогональных функций: система Адамара , система Пэли , система Уолша . Система функций Пэли имеет двоичную инверсию кода номера функции k. Номера функций Уолша изменяются по закону двоичной инверсии кода Грея. Например, для N = 8 имеем

Свойства функций Уолша-Адамара.

Ортогональность

Например, функции

и

ортогональны. Действительно

Функции Адамара-Уолша это равновесные функции с равным числом 1 и-1.

Симметричность

, ,

Мультипликативность

- по номеру функций:

;

-по номеру отсчета:

.

Любая функция Уолша может быть получена путем произведения меандровых функций Радемахера rad(k,n), которые являются базисные функциями для системы Уолша-Адамара. Так, для N=8, n=0,1,…,N-1, имеем следующие функции Радемахера:

rad(0,n)= 1 1 1 1 1 1 1 1; rad(1,n)=1 1 1 1-1-1-1-1; rad(2,n)=1 1 -1-1 1 1-1-1 и rad(3,n)=1-1 1-1 1-1 1-1.

Соответственно

Had(1,n)=rad(3,n); had(3,n)=rad(3,n)rad(2,n) и т.д.

Связь матриц Адамара с конечными полями Галуа GF(q). Усеченная матрица Адамара изоморфна с точностью до перестановки матрице циклических сдвигов псевдослучайной последовательности.

Определим усеченную матрицу Адамара ,размером (N-1)(N-1) полученную из исходной матрицы путем усечения на первый столбец:

.

Определим псевдослучайную линейную рекуррентную последовательность {s[n]; n = 0, 1,…, N - 2}, полученную из элементов конечного поля Галуа GF(q^m) {по правилу

,

где след элемента в поле , -примитивный элемент поля .

Например, для поля , построенному по полиному ,



получаем следующую последовательность:

.

Матрица циклических сдвигов последовательности имеет вид

,

знак «точка» - соответствует начальной фазе (задержки) сигнала.

Определим перестановку символов псевдослучайной последовательности как

.

Для рассматриваемого примера перестановка имеет вид

.

Применение такой перестановки к строкам матрицы-циркулянт псевдослучайной последовательности, отображает последнюю в усеченную матрицу Адамара. Для рассматриваемого примера имеем

.

Нетрудно заметить, что если к полученной матрице добавить единичные верхнюю строку и левый столбец, то получим полную матрицу Адамара с переставленными строками. Если мы имеем дело с многоуровневыми сигналами (кодами), тогда подобная перестановка справедлива для функций Виленкина-Крестенсона.

3.1 Преобразование Уолша-Адамара

Для вектора отсчетов , можно определить преобразование Уолша-Адамара (ПУ-А) следующим образом

,

- прямое преобразование Уолша-Адамара.

,

обратное преобразование Уолша-Адамара (ОПУ-А).

Свойства ПУ-А

Линейность

Если есть последовательность и , то

Инвариантность к диадному сдвигу

Определим для вектора диадный сдвиг . Оператор диадного сдвига переставляет отсчеты исходной последовательности по правилу: .

Спектра Уолша -Адамара диадного сдвига запишется как

.

Из полученного выражения видно, что диадный сдвиг не меняет модуль спектрального коэффициента, а изменяется только знак коэффициента. Доказательство основывается на свойстве функции Адамара:

Теорема о свертке и корреляции

Диадная свертка или диадная корреляция определяется выражением:

или

Заметим, что понятие диадной корреляции совпадает с корреляционной характеристикой булевых функций, что позволяет использовать преобразования Уолша при анализе и синтезе логических функций.

Определение. Булева функция f(v₁,…,v_l) называется максимально-нелинейной, если все коэффициенты ее преобразования Уолша-Адамара равны . Например, функция f(v₁, v₂, v₃,,v₄) = v₁ v₂ + v₃ v₄ - относится к классу максимально-нелинейных.

Энергетический спектр сигнала в базисе функций Уолша. Упорядочение функций по Уолшу имеет определенный физический смысл. На рис. 10 изображены восемь функций Уолша и пунктирными линиями показаны для сравнения тригонометрические функции базиса Фурье.

В связи со сходством сходство между функциями, упорядоченными по Уолшу и тригонометрическими функциями для первых из них иногда применяют обозначения и , называя их соответственно синусный Уолша и косинусный Уолша. Значения l отражают величину так называемой частости, которая определяется по количеству пересечения с линией нулевого уровня в заданном интервале значений . Если не имеется пересечений, то считается, что = 0. При четном числе w пересечений принимается = w/2, при нечетном числе принимается = (w+1)/2. Отсюда следует, что коэффициенты спектра в базисе функций, упорядоченных по Уолша

, k = 0 ,…, N - 1,

несут информацию о частостях обрабатываемого сигнала.

Можно определить энергетический спектр по Уолшу P_W( l ) как



3.2 Быстрое преобразование Уолша (БПУ)

В основе лежит БПУ лежит свойство расщепления матрицы Адамара.

.

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

Для БПУ справедливы графы БПФ с отсутствием множителя .Например, граф БПУ с прореживанием по времени для N = 8 имеет вид

Быстрое преобразование Уолша обладает минимальной вычислительной сложностью, которая оценивается в операций сложения. Многоканальная корреляционная обработка псевдослучайных последовательностей. Рассмотрим возможность применения БПУ для многоканальной корреляционной обработки кодовой псевдослучайной последовательности. В задачах радиолокации и систем передачи информации часто возникает необходимость оценить задержку (фазу) периодически повторяющейся псевдослучайной последовательности, принимаемой на фоне аддитивного шума. Цифровая система обработки в этом случае должна вычислять все значения взаимнокорреляционной функции сигнала и его опорной копии, т.е. поддерживать многоканальный корреляционный прием сигнала. При больших длинах сигнала число каналов становится значительным, и прямые методы вычисления корреляционной функции потребуют больших вычислительных затрат (~N). Покажем, что, используя связь структуры псевдослучайного кода с матрицами Уолша-Адамара, вычислительную сложность можно значительно понизить. Действительно, если отсчеты пседослучайной последовательности длины N = 2^m - 1 переставить с помощью оператора P_M, то любой циклический сдвиг сигнала отобразиться в усеченную на первый символ функцию Уолша. Если на месте усеченного символа искусственно разместить ноль, то мы получим последовательность из N=2^m отсчетов, размерность которой совпадает с размерности быстрого преобразования Уолша. Значения спектра Уолша-Адамара такой последовательности будут полностью эквивалентны значениям корреляционной функции обрабатываемого сигнала.

Пример. Пусть принимается кодовая последовательность вида

.

Автокорреляционная функция такого сигнала вычисляется по формуле

и принимает значения R(0) = N, R(l 0) = -1.

Перестановка последовательности по ранее рассмотренному правилу дает

P_M : {s[n]} = -1,1-1,1,-1,1,-1.

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

{x[n]}=0, -1, 1, -1, 1, -1, 1, -1.

Спектр Уолш-Адамара такой последовательности равен

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

3.3 Теоретико-числовые преобразования (ТЧП)

ДПФ в поле комплексных чисел использует, как правило, приближенное представление числа и характеризуется погрешностью вычисления. В ряде задач обработки сигналов, связанных с вычисление сверток, необходимы точные преобразования инвариантные к циклическому сдвигу. Указанным требованиям удовлетворяют преобразования, осуществляющие модульную обработку в кольце целых чисел. Такие преобразования называются теоретико-числовыми (ТЧП).

Прямое и обратное ТЧП задаются формулами

mod M

mod M, (93)

где - целое число такое, что ; N^-1 - число, обратное N по модулю M.

ТЧП имеет ту же структуру, что и ДПФ. Иными словами, ТЧП - это дискретные преобразования Фурье, определенные в кольце чисел по модулю M. ТЧП обладают свойством цикличности свертки и в ряде случаев могут вычисляться с использованием только операций сложения и сдвига (). Свойства ТЧП и их применение в существенной степени зависят от параметров преобразования: модуля M, корня и длины N преобразуемой последовательности. Отсчеты входных данных для ТЧП обязательно должны быть промасштабированы, в частности должно выполняться условие .

Для того, чтобы выполнялось обратное ТЧП необходимо, чтобы существовали обратные числа N^-1 и . Это условие выполняется если и N взаимно простые с M. С точки зрения теории чисел обратные числа существуют если

и

или

, . (94)

Обычно определение ТЧП начинается с выбора модуля M, а затем исследуются возможные значения N. В качестве модуля чаще всего используют числа Мерсенна и Ферма. Соответственно различают ТЧП Мерсенна (ТЧПМ) и ТЧП ферма (ТЧПФ).

ТЧП - Мерсена

Числа Мерсенна определяются выражением, где - простое число. ТЧПМ существует, если N делит все числа вида (q_i - 1), где q_i- составные множители из разложения числа Мерсенна

.

Для простых чисел Мерсенна длину преобразуемой последовательности получают из условия, что число N делит число т.е.

Из теории чисел известно, что если , то делится на , и Кроме того число 2 является делителем числа . Следовательно, можно определить -точечные ТЧПМ.

Рассмотрим вопрос определения . Если простое, то корнем порядка является 2 так как . Если составное число то, 2 тоже является корнем, но необходимо чтобы имело обратное число, а это условие выполняется в том случае если

.

Таким образом, можно определить прямое и обратное точечное преобразование Мерсена.

и

, (95)

где .

Для 2p точечного преобразования корнем является так как и степени корня представляют собой разные числа отличные от нуля.



Для составного M_p необходимо выполнить проверку на взаимную простоту чисел:

для .

Для то получаем:

.

Следовательно, можно определить 2p-точечное ТЧПМ

,

, (96)

где .

Для преобразования осуществляются без операций умножения. Возможно ТЧПМ другого размера с , но в этом случае появляются операция умножения.

Пример. Пусть ,

 ,

Матрица ТЧП строится так же как матрица преобразований Фурье с одним отличием: место поворачивающего множителя занимает число

Определим

,

используя алгоритм Евклида:

, .

Обратное ТЧПМ имеет вид

.

Недостаток преобразования Мерсенна состоит в том, что для него отсутствуют алгоритмы быстрого вычисления, так как числа p и 2p не разлагаются на большое количество сомножителей. Этого недостатка лишены преобразования Ферма (ТЧПФ).

ТЧП Ферма

ТЧПФ в качестве корня использует двойки и степени двойки. Это позволяет получить удобную арифметику, N кратную степени двойки.

Числа Ферма имеют вид , где . Например .Первые пять чисел - это простые числа остальные числа составные., где - простое число. Если - простое число, то размер выборки определяется из условия: .

Если - составное число, то простой множитель имеет вид.

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

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

ТЧПФ имеет вид

mod

, (97)

где .

Возможны следующие виды «удобных» корней:

корень, является корнем порядка по ;

корень является корнем порядка: по ;

корень,, .

ТЧПФ имеет длины преобразований, которые выражаются составными числами. Это позволяет для их вычисления воспользоваться алгоритмами типа БПФ. - Так, если длина равна степени двойки, то возможны быстрые алгоритмы преобразований, структура которых аналогично БПФ с прореживанием по частоте и по времени за исключением того, что операционный умножитель на поворачивающий множитель заменяется операцией умножения на степень двойки, то есть сдвигами:

. (98)

Вычислительная сложность быстрого ТЧПФ составит - операций сложения и - операций сдвига.

Пример. Пусть ; . Тогда для . Для .

Выберем тогда:



.

Основные применения ТЧП - это вычисление точных значений свертки.

Пример. Предположим, необходимо вычислить циклическую свертку двух последовательностей и . Выберем ТЧПФ с параметрами . Спектры последовательностей равны:

и .

Произведение одноименных спектральных коэффициентов дает следующий результат . Обратное число . Значения циклической свертки равны: