Some properties of the discrete Fourier transform in the field of complex numbers and in the fields of finite characteri.pdf Дискретное преобразование Фурье - это один из видов ортонормированного преобразованиявекторов [1, 2]. Для конечной последовательности элементов {s 0, s1, ..., Sn-1}дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности{S0, S1, ..., SN-1}, элементы которой вычисляются по формуле (прямое преобразование)N-1 ________Sk = Е Sn ■ WNn; k = 0,N - 1, (1)n=0где Wn -примитивный корень степени N из единицы [1, 3]. В предположении, чтоэлемент N-1 = 1/n существует, для обратного преобразования можно записать выражение1 N-1 ________Sn = ^ Е Sk ■ W - kn; n = 0, N - 1. (2)N k=0Считается, что вектор s = (s0, s1, ..., Sn- 1) является представлением данных вовременной области, а вектор S = (S0, S1, ..., SN-1) -в частотной (спектральной).Векторы s и S можно задать с помощью соответствующих многочленов s (X )и S (X )s (X ) = S0 + S1X + ... + Sn-1X N 1; (3)S (X ) = S0 + S1X + ... + S n -1X N-1. (4)Если конечная последовательность{sn = s[nT] = s(t), n = 0, N - 1; t = nT} (5)получена в результате дискретизации действительной (комплексной) функции s(t), то,в предположении T = 1, s(t) соответствует преобразование ФурьеN-1S (еш) = Е sne-iwn, (6)n=0где S (вш) -непрерывная 2п-периодическая функция, i = \J -1.Согласно теореме Котельникова [4, 5], в частотной области функция S (взш) полностьюопределяется последовательностью своих равноотстоящих отсчетов{S(e /N) = Sk; k = 0, N - 1}, взятых с интервалом Аш = 2n/N , что соответству-_i2nет применению в (1), (2) Wn = e /N . Это позволяет вычислять значения функцииS(eiW) различными методами. Например:1. В любых точках с помощь интерполяционной формулы [4]S(eiW) = -N-1^ Sin[(^N - 2nk)/2] _ e- i[(N- l )/2](u-2Kk/N) k = 0 N - 1 (7)S (e ) N kt 0 Sk sin[(wN - 2nk/N)/2] e , k 0,N 1 (7)которая позволяет вычислить значение спектра для любого ш.2. Методом подбора значения Np ^ N , дополнением вектора s = (s0,s 1,...sN-1)нулевыми значениями до длины Np и вычислением (1) для k = 0, Np - 1.В поле комплексных чисел C лежат корни из 1 для любого натурального N ; таким_i 2побразом, в (1), (2) N может принимать любое натуральное значение, и Wn = e /Nявляется примитивным корнем степени N из 1.Величина WNn периодична по k и n с периодом N :wNn = wNk+AN )(n+BN), (8)где A, B - любые целые. Для четных n и N имеет место равенствоWNn = WN/2, где n = 2 r. (9)Используя (9), для четного N выражение (1) можно переписать в видеN/2-1 N/2-1Sk = Е s2r ■ WNr/2 + Wik ^ s2r+1 ■ WN/2; r = 0, N/2 - 1. (10)r=0 r=0Таким образом можно построить быстрые алгоритмы вычисления ДПФ (БПФ) длялюбого составного N . Оценка сложности выполнения алгоритма БПФ носит логарифмическийхарактер, и для N = 2м эта оценка равна O(NM) [6].Особенности строения поля C позволяют построить алгоритмы БПФ логарифмическойсложности для любого, в том числе простого N [7]. Это достигается дополнениемвектора s = (s0,s 1, ...,sn-1) нулевыми значениями до длины Np = 2м , ближайшейк 2N (метод 2). Например, для N = 1 3 получим Np = 32. При этом всегда Np < 4N.В поле C алгоритмы БПФ позволяют определять свойства анализируемых данных,эффективно проводить вычисления сверток и многое другое. Свойства данныхисследуются путем определения спектральных максимумов и минимумов в амплитуднойхарактеристике (6), разрывов в фазовой характеристике, при этом нахождениеточных значений корней многочленов (3), (4), как правило, не требуется [4, 5].В конечном поле Галуа GF(q) [1, 3] N в (1), (2) уже не может принимать произвольноезначение, так как порядок элемента WN должен быть кратен порядку мультипликативнойгруппы GF(q), равному q - 1. В частности, корни из 1 степени 2мпринадлежат GF(q), где q - простое, если q = c2M + 1, где с - натуральное. В этомслучае можно использовать (10) с максимальной эффективностью.Многие свойства ДПФ переносятся на случай конечных полей, но с учетом сформулированноговыше ограничения. Произвольное дополнение вектора s = (s0, s1, ..., Sn- 1)нулевыми значениями с целью построения алгоритмов БПФ с максимальным быстродействиемневозможно. Для GF(q) справедливы следующие утверждения.Утверждение 1. Спектральная координата Sk вектора S равна 0 тогда и толькотогда, когда WN является корнем многочлена s (X ) (3).Утверждение 2. Координата sn вектора s равна 0 тогда и только тогда, когдаW - n является корнем многочлена S (X ) (4).Доказательства утверждений 1, 2 очевидны, так какs(WN) = s0 + s1WN + ... + s N-1WN ) = Sk;S (W^n) = S0 + S1W^n + ... + S n -1W -n(N-1) = Sn.Элементы GF(pm), где p - простое, могут быть представлены в надполе GF(pmK)или расширении поля GF(pm) [1, 3]. При этом корни и спектральные нули исходногополя GF(pm) будут «видны» во всех этих расширениях.Например, пусть G1 = GF(pm) = GF(26), N = 26 - 1 = 63. Возможные расширенияполя G1: G2 = GF(p2m) = GF(212) и G3 = GF(p3m) = GF(218) содержат элементыполя G1, и корни многочлена s(W^) = 0 над G1 могут быть найдены и в G2, и в G3.Это свойство позволяет по спектральным нулям в максимально возможном для исследованияполе строить предположения о возможных подполях, в которых эти нулитакже проявятся.

Скачать электронную версию публикации