Диссертация (1150736), страница 15
Текст из файла (страница 15)
Из последнего равенства, в частности, следует, что ( ⊗ ) ⊗ℓ = ⊗ ℓ и ⊗ (ℓ ⊗ ) = ℓ ⊗ .Пусть , — натуральные числа и = . Набор векторов (, ⊗ , )при 0 ≤ < , 0 ≤ < составляет стандартный базис в R .Введём обозначение для матрицы перестановки и для диагональнойматрицы порядка , определяемых формулами (, ⊗ , ) = , ⊗ , ,0 ≤ < , (, ⊗ , ) = (, ⊗ , ),0 ≤ < ,0 ≤ < ,0 ≤ < .Перестановка осуществляет следующее преобразование индексов: : + → + ,0 ≤ < ,0 ≤ < .Из определения следует, что для любых векторов ∈ R и ∈ R : ( ⊗) = ⊗ .84Матрица может быть также явно представлена в виде⎛⎞⎛ 0( )( )0⎜⎟⎜......⎟, = ⎜ = ⎜⎝⎠⎝( )−1( )−1⎞⎟⎟.⎠Эти матрицы обладают следующими свойствами.Лемма 5 Пусть = . Тогда = ( )−1 = ( ) , = .Доказательство.
Утверждения непосредственно следует из определений.Произведение Кронекера некоммутативно. Перестановка и ℱ в произведении Кронекера осуществляется при помощи матриц перестановок .Лемма 6 Пусть = . Тогда ( ⊗ ℱ ) = ℱ ⊗ .Доказательство. Пусть 0 ≤ < и 0 ≤ < . Тогда ( ⊗ ℱ ) (, ⊗ , ) = (, ⊗ (ℱ , )) = (ℱ , ) ⊗ ,= (ℱ ⊗ )(, ⊗ , ),что доказывает утверждение леммы.Алгоритмы быстрого преобразования Фурье (БПФ) основаны на факторизации матрицы ДПФ при помощи расщепляющего правила, сформулированного в следующем утверждении.Лемма 7 Пусть = , где , — натуральные числа.
Тогдаℱ = ( ⊗ ℱ ) (ℱ ⊗ ).85Доказательство. Пусть 0 ≤ < , 0 ≤ < . Тогда (ℱ ⊗ )(, ⊗ , ) = ((ℱ , ) ⊗ , ) = (( )−1=0 ⊗ , ).Поскольку ( ) = , то при 0 ≤ < , 0 ≤ < аналогично получаем,что(︂)︂ (︂)︂(, ⊗ , ) ( ⊗ ℱ ) = ( ⊗ ℱ) (, ⊗ , )= (, ⊗ ℱ, ) .Отсюда(, ⊗, ) ( ⊗ℱ ) (ℱ ⊗ )(, ⊗, ) = (, ℱ , ) = ++ .Из определения следует, что = 1. Поэтому++ = (+)(+)− = (, ⊗ , )ℱ (, ⊗ , ),что доказывает утверждение леммы.Следствие 2 Пусть = , где , — натуральные числа. Тогдаℱ = ( ⊗ ℱ ) ( ⊗ ℱ ) .Доказательство.
Формула получается из леммы 7 при помощи подстановки утверждения леммы 6.3.1.3Инверсия индексовОбщая формула алгоритма БПФ получается итерированием расщепляющего правила из следствия 2. Эта формула включает отображение, порождённоеинверсией мультииндексов, которое определяется ниже.Пусть = ( , −1 , . .
. , 0 ) — некоторый упорядоченный набор нату∏︀ральных чисел, называемый далее мультииндексом, и = =0 . Каждое целое число от 0 до − 1 единственным образом представляется всистеме счисления, порождённой мультииндексом , в виде мультииндекса = ( , . . . , 0 ) из условия = 0 +0 (1 +· · ·+−2 (−1 +−1 ) · · · ),860 ≤ < ,0 ≤ ≤ .В этом случае связь между мультииндексом и числом обозначается следующим образом: = , = . Мультииндекс будем называть порождающим систему счисления, а мультииндекс — согласованным с этой системой.Количество кодируемых чисел обозначим = ||.Из определения сразу следует, что для любых порождающих мультииндексов , и для любых согласованных с ними мультииндексов , , соответственно, ,|| ⊗ ,|| = (,)(,) ,|| || .Инверсией мультииндекса = ( , .
. . , 0 ) назовём тот же набор компонент, но в обратном порядке: ⋆ = (0 , . . . , ). Мультииндекс ⋆ =(0 , . . . , ) также порождает нумерацию чисел от 0 до − 1. Перестановкой инверсии мультииндекса назовём перестановку чисел от 0 до − 1,определяемую правилом(︂)︂ + (−1 +· · ·+2 (1 +1 0 ) · · · ) = 0 +0 (1 +· · ·+−2 (−1 +−1 ) · ·при 0 ≤ < , 0 ≤ ≤ . Это же правило можно записать в виде = ((⋆ )⋆ ) .
Таким образом, перестановка отображает числа от 0 до|| − 1, записанные в системе счисления, порождённой мультииндексом ⋆ ,в числа с инвертированным цифровым представлением в системе счисления,порождённой мультииндексом .Перестановка порождает линейное отображение в R , которое будемобозначать . Оно полностью характеризуется значениями , = ,при 0 ≤ < .Из определения матрицы перестановки следует, что если = (, )имеет только две компоненты, то = .Лемма 8 Пусть — мультииндекс и = ||. Пусть > 0 и = (, ) —расширенный мультииндекс. Тогда(,) = ( ⊗ ) ,(, ) = ( ⊗ ).Доказательство. Пусть 0 ≤ < и 0 ≤ < .
Для доказательства первого равенства введём обозначение для мультииндекса = (, ). Выполним87вспомогательные преобразования: + = (, (⋆ )⋆ )(,) = [(⋆ , )⋆ ] = [(( +) ⋆ )⋆ ] = (+ ).Подставим это равенство в следующем преобразовании:( ⊗ ) (, ⊗ , ) = ( ⊗ )(, ⊗ , ) = , ⊗ ( , )= , ⊗ , = + , = (+ ) = +, = (, ⊗ , ),что равносильно первому утверждению леммы 8.Аналогично доказывается второе утверждение. Обозначим = (, ).Тогда + = ((⋆ )⋆ , )(, ) = [(, ⋆ )⋆ ] = [(( + ) ⋆ )⋆ ] = ( + ).Подставим это равенство в следующем преобразовании: ( ⊗ )(, ⊗ , ) = (, ⊗ , ) = (, ⊗ , )= , ⊗ , = +, = ( +) = +, = (, ⊗ , ),что равносильно второму утверждению леммы 8.3.1.4Формула БПФ произвольной размерности во временной областиИспользуем расщепляющее правило для приведения алгоритма БПФ к виду, пригодному для реализации на архитектурном шаблоне рис.
3.2.Пусть размерность ДПФ можно разложить на множители: =∏︀=0 .Тогда алгоритм расчёта ДПФ может содержать только бабочки длиной0 , . . . . На этом свойстве основан алгоритм БПФ, который обычно применяется для размерностей , равных степени числа 2. В следующем утверждении это свойство доказывается для произвольных размерностей 0 , . . . , .Теорема 4 Пусть = ( , . . .
, 0 ) — набор натуральных чисел и =∏︀∏︀.Длякаждого=0,...,определим==0=0 . Тогда(︃ )︃∏︁ℱ =, ,=088где в произведении матриц , матрицы с меньшими индексами стоят справа,̂︁, = −1 (/ ⊗ ℱ ) ,0 ≤ ≤ ,̂︁ определяются раматрицы перестановок и диагональные матрицы венствами = / ⊗ ,̂︁ = / ⊗ .Доказательство. Докажем теорему по индукции. Пусть = 0. Тогда =0 . По определению, 00 = 0 и поэтому 0 = . Кроме того, 00 = 0 , и̂︁0 = . Заключение теоремы становится тождеством: ℱ = ℱ .поэтому 0Докажем индукционный шаг. Пусть утверждение доказано для − 1 ≥ 0.Докажем для . Применим следствие 2 при = , = −1 , = : ℱ = −1 (−1 ⊗ ℱ ) ( ⊗ ℱ−1 )−1 .−1По определению, = и по лемме 5: = −1 . Поэтомуℱ = , ( ⊗ ℱ−1 )−1 .Пусть −1 = (−1 , .
. . , 0 ). Из индукционного предположения и из свойствапроизведений Кронекера следует, что(︃−1)︃∏︁ℱ−1 =,−1 −1 .=0Отсюда(︃−1)︃∏︁=( ⊗ ,−1 ) ( ⊗ −1 )−1 .( ⊗ ℱ−1 )−1=1По лемме 8( ⊗ −1 )−1 = .По свойствам произведения Кронекера ⊗ (−1 ⊗ ) = ⊗ = ,−1 ⊗ (−1 ⊗ −1 ) = ⊗ −1 = ,̂︁ , ⊗ (⊗ ) = ⊗ = −1891 ≤ ≤ − 1.Поэтому ⊗ ,−1 = , ,1 ≤ ≤ − 1.Подстановка этих выражений приводит к формуле(︃−1)︃∏︁( ⊗ ℱ−1 ), ,−1 ==1что доказывает индукционный шаг.Все матрицы в условии теоремы имеют структуру / ⊗, что позволяетположить всю цепочку операций для одной бабочки ℱ на одну итерацию архитектурного шаблона.
При этом одна стадия БПФ , будет соответствоватьодной инструкции архитектурного шаблона.Цифровое представление индексов входного сигнала БПФ, согласованное салгоритмом из теоремы 4, определяется мультииндексом ⋆ = (0 , . . . , ) состаршими разрядами, соответствующими основанию 0 . Результат БПФ получается с цифровым представлением индексов, записанным в системе счисления, порождённой мультииндексом . Стадии БПФ , в алгоритме теоремы4 начинаются с обработки младших разрядов.Матрицы перестановок из теоремы 4 можно интерпретировать в терминах системы счисления. Матрица = (−1 , ) осуществляет перестановкуиндекса в конец мультииндекса, что сформулировано в следующей лемме9.Для произвольного мультииндекса = ( , .
. . , 0 ) и произвольного целого числа от 0 до определим мультииндекс ¯ равенством¯ = ( , . . . , +1 , −1 , . . . , 0 , ).Поскольку || = |¯ |, то оба мультииндекса порождают системы счисления наодном и том же множестве целых чисел от 0 до = || − 1. Преобразованиемультииндексов обозначим = ( , . . . , 0 )→¯ = ( , .
. . , +1 , −1 , . . . , 0 , ).Лемма 9 Пусть при 1 ≤ ≤ — матрицы из формулировки теоремы 4.Для каждого = 0, . . . , введём мультииндекс = ( , −1 , . . . , +1 , 0 , 1 , . . . , ).90Тогда при = 1, . . . , : = (−1 ) и матрица осуществляет следующую перестановку : = −1→ = (¯ ) ,0 ≤ ≤ || − 1.Доказательство. Пусть 1 ≤ ≤ .
Равенство = (−1 ) следует изопределения операции над мультииндексами ¯ и из определения мультииндексов при 0 ≤ ≤ . По определению, = / ⊗ = / ⊗ (−1 , ) .Пусть = ( , . . . , , 0 , 1 . . . , −1 ) — мультииндекс в системе счисления,порождённой −1 и = −1 — значение индекса. Тогда , = ,/ ⊗ ( ,−1 ) ℓ, ,где = ( , .
. . +1 )( ,...,+1 ) ,ℓ = ( , 0 , . . . −1 )( ,0 ,...,−1 ) = ( , )( ,−1 ) , = (0 , . . . −1 )(0 ,...,−1 ) .Поэтому(−1 , ) ℓ, = (−1 , ) ( , ⊗ ,−1 ) = ,−1 ⊗ , = (, )(−1 , ) ,и(, )(−1 , ) = (0 , . . . )(0 ,..., ) .Таким образом, , = ,/ ⊗ (0 ,... )(0 ,..., ) , = (¯ ) , ,что доказывает утверждение леммы 9.3.1.5Формула БПФ произвольной размерности в частотнойобластиАлгоритм расчёта ДПФ, описанный в формуле теоремы 4, принято относить к реализации БПФ во временной области. Особенностью этого алгоритма91является перестановка входного вектора и умножение на комплексные корни из единицы перед бабочкой.Двойственное утверждение обычно относят к реализации БПФ в частотнойобласти. В нём перестановка инвертирования индексов осуществляется послевсех бабочек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
