DT-Fourier.HTM
Арифметики     ▲ Выше     ЧП Ферма

Фурье-подобные преобразования
в конечных числовых полях


            T-1
y[k]= x[t] h[k-tT]
          t=0
    k = 0,1,..,T-1

 
 
           T-1
S[w]= x[t] εwt
           t=0
    w = 0,1,..,T-1


Сколько их! куда их гонят?..

Александр Пушкин
"Бесы", 1830.


Таблица Фурье-подобных преобразований
Классификация Фурье-подобных преобразований
Фурье-подобные преобразования над полем C
Фурье-подобные преобразования над полем GF(M)
Свёртка и Фурье-подобные преобразования
   Свёртка двух сигналов
   История быстрых алгоритмов ЦОС
   Связь между ТЧП, ПП и ДПФ
    ПП и вычисление свёрток
    ТЧП и вычисление свёрток
    Вычисление комплексных свёрток с помощью ЧП Ферма
    Резюме сравнения ТЧП, ПП и ДПФ




Таблица Фурье-подобных преобразований


 
Помнишь, мы вместе
                  грызли, как мыши,
непрозрачное время?
                  Сим победиши!
                               Велемир Хлебников
                          "Алёше Кручёных", 1920

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

Пусть непрерывный сигнал x(t) задан на абелевой группе H вещественных чисел. Тогда его можно подвергнуть интегральному преобразованию:

X(ω) = H x(t) W(ω,t) dt ;     
x(t) = H X(ω) W1(ω,t) dω ,
где X(ω) — спектр (образ) сигнала x(t), который принимает значения в поле или хотя бы в кольце с единицей; W(ω,t) и W1(ω,t) — ядра прямого и обратного преобразований. При этом предполагается, что эти интегралы сходятся.

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

εχw(t) = εwt ,
такая, что выполняются условия изоморфизма
εχw(t1+t2) = εχw(t1) · εχw(t2) ,
εχw(0) = 1 .

Например, над полем комплексных чисел C характерами являются:

*

H
 
для бесконечной непрерывной (континуальной) абелевой группы вещественных чисел R — это пара комплексных экспонент
exp(j)χω(t) = W(ω,t) = exp(−ω·t) = eω·t ,
exp(j)χω1(t) = W1(ω,t) = exp(+j·ω·t) = eω·t ;  
*

H
 
для бесконечной, но счетной абелевой группы целых чисел Z — это пара дискретных комплексных экспонент при w,n=...,2,1,0,1,2,...
exp(j)χω(n) = W(ω,n) = exp(−ω·n) , где ω=2π·w ;
exp(j)χω1(n) = W1(ω,n) = exp(+j·ω·n) ;                    
*

 

HN
для конечной циклической группы порядка N — это пара (условных) КОРНЕЙ N-й степени из 1, т.е.
ε = N1 = exp(−j·2π·N1) ,    ε1 = (N1)1 = exp(+j·2π·N1) ,
при w,n=0,1,...,N-1 имеем характеры
εχw(n) = W(w,n) = εwn .

Преобразования с подобным выбором характеров, в качестве базисных функций, являются ортогональными. Подставляя в исходное интегральное выражение вместо ядер W(ω,t) и W1(ω,t) соответственно exp(−ω·t) и exp(j·ω·t) получим известную пару одномерных интегральных преобразований Фурье:

Группа, сигнал, спектр
L ( tcon, H , R ) , C
                      +
F(ω) = (2π )1 f(t) exp(−ω·t) dt ;
                     
                    +
f(t) = (2π )1 F(ω) exp(j·ω·t) dω .
                   

причём
          +
D(ω) = f(t) exp(−ω·t) dt = E(ω/2π) = E(w) ;
         
          +
E(w) = f(t) exp(−j·2π·w·t) dt ;
         

ω = 2π·w




Если двусторонний бесконечный интервал (-,+) заменить на односторонний бесконечный [ 0,+ ), то получим интегральное преобразование Лапласа, обеспечивающее сходимость интеграла для более широкого класса функций:

Группа, сигнал, спектр
L ( tcon, H , R ) , C
          +
F(α) = f(t) exp(−α·t) dt , где α=j·ω .
          0

Подставляя здесь дискретную экспоненту exp(−j·2π·w·n) и заменяя интеграл знаком суммы, а следовательно, непрерывное время t дискретным n·Δt, получим дискретное преобразование Лапаласа (ДП-Л):

Группа, сигнал, спектр
L ( ndis, H , R ) , C
         +
X(ν) = x(n·Δt) exp(−ν·n), где ν=j·2π·w, w=0,1,...
         n=0

или z-преобразование (ряд Лорана)

Группа, сигнал, спектр
L ( ndis, H , R ) , C
         +
X(z) = x(n·Δt) zn , где z=exp(j·2π·w), w=0,1,... .
          n=0

Аналогично, используя характер

ε = exp(±j·2π·(N1)) = N1
конечной циклической группы порядка N получим выражения для дискретного (прямого и обратного) преобразований Фурье (ДПФ и оДПФ) над полем комплексных чисел C:

Группа, сигнал, спектр
L ( ndis, HN , C ) , C
X(w·Δω) = x(n·Δt) εn , где n,w = 0,...,N-1 ,

x(n·Δt) = N1 X(w·Δω) εn , где w,n = 0,...,N-1 .


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

N=2 , N=4 .

Матрица "бабочки"
F2 =



1  +1
1  −1



.
Матрица "бабочки"
F4 =








1    1    1    1  
1  +j  −1  −j  
1  −1 +1  −
1  −j  −1  +j  








.

И так, мы рассмотрели преобразования на бесконечных и конечных циклических абелевых группах H . Особый класс составляют преобразования на конечных абелевых группах, представимых в виде прямой (или тензорной) суммы абелевых групп меньшего порядка

H = H1 H2 ...

Прямой (тензорной) суммой абелевых групп A и B называется группа С, образованная декартовым произведением (множеств)

С=AхB ,
где С — это всевозможные пары элементов из двух множеств.

Если конечные абелевы группы A и B имеют порядки TA и TB, где TA и TB взаимно простые натуральные числа, т.е. (TA,TB)=1 , то их прямая сумма A B также является абелевой группой порядка TС = TA·TB.

Особое значение имеет утверждение, что прямая сумма двух циклических групп с порядками TA и TB, где TA и TB взаимно простые натуральные числа, является тоже циклической группой с порядком TС = TA·TB и, наоборот, если порядок конечной циклической группы разлагается в произведение взаимно простых чисел то эта группа представима в виде прямой суммы этих циклических групп.

Если порядок T циклической группы является степенью простого числа p, т.е. T=pm, где T — натуральное число, то она называется примарной по числу p. Любая конечная циклическая группа разлагается в прямую сумму примарных циклических групп (по разным простым числам), в то время как примарные циклические группы неразложимы.


 
Девушки, те что шагают
сапогами чёрных глаз
по цветам моего сердца.
Девушки, опустившие копья
на озера своих ресниц.
Девушки, моющие ноги
в озере моих слов.
                  Велемир Хлебников
                               1921

Фурье-подобные преобразования над полем C.

Классификация дискретных преобразований
на конечных абелевых группах GN порядка N
со значением в поле комплексных чисел C .
Группа G Дискретное
преобразование
Ядро преобразования ( характеры χ )
Порядок Тип
N Циклическая
GN
Фурье
( ДПФ )
χw(n)=exp(−j·2π·(N1)·w·n)
N=2m Пряморазложимая
G2 .. G2
Уолша
( ДП-У )
χw(n) = εB = (-1)B,
 B = wknk ; εB=√1=(-1)
k=1,...,m
N=pm Пряморазложимая
Gp .. Gp
Крестенсона
( ДП-К ) ,
p > 2, p-простое число
χw(n)=exp(−j·2π·(p1)wknk),
k=1,...,m
N=rm Пряморазложимая
Gr .. Gr
Виленкина-Крестенсона
( ДП-ВК ) ,
r — целое
положительное число
χw(n)=exp(−j·2π·(r1)wknk),
k=1,...,m
 m
N=rk,
 k=1
Пряморазложимая
Gr1 .. Grm
Понтрягина-Виленкина-
Крестенсона
( ДП-ПВК ) ,
rk — целое
положительное число
χw(n) = εrk(wknk) ,
k=1,...,m ,
εrk = exp(−j·2π·(rk1))
Примечание: m — количество групп ; G2, Gp, Gr, Grk — абелевы группы порядков 2, p, r, rk ;
j=√-1 — мнимая единица ; — символ прямой суммы групп.

Вид характера
χw(n) = εwn , где w,n=0,1,...,N-1 ,
группы GN определяется множителями её порядка N .

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

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

 
Хотите ли вы
стать для меня род тетивы
из ваших кос кручёных?
На лук ресниц, в концах печёный,
меня стрелою нате,
и я умчусь грозы пернатей.
                          Велемир Хлебников
                    "Самострел любви", 1921

Фурье-подобные преобразования над полем GF(M).

NB. Основное достоинство Фурье-подобные ДП над конечными полями Галуа GF(M) — это абсолютная точность вычислений, т.к. деление в конечных полях (в отличие от бесконечного поля комплексных чисел C) всегда выполняется точно, хотя требуется такая организация вычислений (т.е. выбор модуля M), чтобы исходные и конечные результаты находились в согласованном "динамическом" диапазоне.

Дискретные преобразование Фурье над полями Галуа или над кольцом (с единицей) принято называть теоретико-числовыми преобразованиями (ТЧП).

ТЧП Лапласа-Галуа, предложенное Цыпкиным и Фараджевым, используется при исследовании цифровых автоматов, состояния которых описываются сигналами, заданными в областях целых чисел (в дискретные моменты времени) и принимающими значения в конечном поле GF(M)

ТЧП Мерсена и ТЧП Ферма (их ещё называют просто ЧП Мерсена и ЧП Ферма) выполняются в конечных полях и в кольцах по модулю соответственно чисел Мерсена

Mp = 2p-1 ,
где p — простое число, и чисел Ферма
Fn = 22n+1 , = 2b+1 ,
где b=2n , n - целое число. В полях и кольцах по модулю чисел Мерсена и Ферма сравнительно просто выполняется операция приведения по модулю. Так, операция приведение по модулю числа Мерсена эквивалентна циклическому сдвигу (по сути — это арифметика в обратном двоичном коде) . Ещё одно достоинство использования подобных ТЧП — возможность формирования матрицы преобразования только из чисел, являющихся степенью двойки, умножения на которые эквивалентны обычному сдвигу, что позволяет вычислять преобразование без умножения. Однако, в практике кодирования телеинформации с контролем ошибок ЧП Мерсена и ЧП Ферма пока распространения не получили.

Однако, в 1986 году Д.В.Чудновский, Г.В.Чудновский, М.М.Денно (M.M.Denneau) и С.Г.Юнис (S.G.Younis) сконструировали необычный компьютер общего назначения, названный Маленьким Ферма (Little Fermat), который мог быстро умножать большие числа. Компьютер был оснащен аппаратными средствами быстрого выполнения арифметических операций по модулю числа Ферма F8 = 2256+1 над 257-битными словами. Поскольку можно вычислять свертки из 256 слов при помощи 256 умножений и 3-х дискретных преобразований по модулю числа Ферма, требующих только операций сложения и сдвига, то этот компьютер позволил перемножать два 106-битовых числа меньше чем за 0.1 с.

ТЧП Фурье-Мэттсона-Соломона играет особую роль в теории помехо-устойчивого кодирования.



Свёртка и Фурье-подобные преобразования


 

Три дела, однажды начавши, трудно кончить:
1) вкушать хорошую пищу;
2) беседовать с другом, возвратившимся из похода
 и
3) чесать, где чешется.
                                  Козьма Прутков
                           "Мысли и афоризмы",45.

Арифметики     ▲ В начало текущей     ЧП Ферма






Последнее обновление 16.09.2013

© 2005 г., Александр Тимофеев, г.Харьков, Украина, eMail: atimopheyev@yahoo.com