БПФ с векторным основанием. алгоритм

Алгоритм векторно-основанного БПФ - это алгоритм многомерного быстрого преобразования Фурье (БПФ), который является обобщением обычного алгоритма БПФ Кули – Тьюки, который делит размеры преобразования произвольными основами. Он разбивает многомерное (MD) дискретное преобразование Фурье (DFT) на последовательно меньшие MD DFT до тех пор, пока, в конечном итоге, не потребуется оценивать только тривиальные MD DFT.

Наиболее распространенные многомерные Алгоритм БПФ - это алгоритм строки-столбца, который означает преобразование массива сначала в один индекс, а затем в другой, подробнее см. В БПФ. Затем было разработано прямое двумерное БПФ с основанием 2, которое позволяет исключить 25% умножений по сравнению с традиционным методом «строка-столбец». И этот алгоритм был расширен до прямоугольных массивов и произвольных оснований, что является общим алгоритмом векторной системы счисления.

Алгоритм вектор-основание БПФ может значительно уменьшить количество сложных умножений по сравнению с алгоритмом вектор-строка. Например, для элементной матрицы $NM\; \{\backslash \; displaystyle\; N\; ^\; \{M\}\}$(размеры M и размер N для каждого измерения), количество комплексных кратных векторно-основному алгоритму БПФ для основание системы счисления 2 равно $2\; M\; -\; 1\; 2\; MNM\; log\; 2\; \; N\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{2\; ^\; \{M\}\; -1\}\; \{2\; ^\; \{M\}\}\}\; N\; ^\; \{M\}\; \backslash \; log\; \_\; \{2\; \}\; N\}$, в то время как для алгоритма строка-столбец это $MNM\; 2\; log\; 2\; \; N\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{MN\; ^\; \{M\}\}\; \{2\}\}\; \backslash \; log\; \_\; \{\; 2\}\; N\}$. И, как правило, достигается еще большая экономия на умножениях, когда этот алгоритм работает с большими основами и с массивами более высокой размерности.

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

• 1 Случай 2-DIT
• 2 2 -D DIF case
• 3 Другие подходы
• 4 Ссылки

Как и в случае алгоритма Кули – Тьюки, двумерное векторно-основанное БПФ является получается путем разложения обычного 2-ДПФ на суммы меньших ДПФ, умноженных на множитель "твидла".

Алгоритм прореживания во времени (DIT ) означает, что разложение основано на временной области $x\; \{\backslash \; displaystyle\; x\}$, подробнее см. Алгоритм БПФ Кули – Тьюки.

Мы предполагаем, что двумерное ДПФ

$X\; (k\; 1,\; k\; 2)\; =\; \sum \; n\; 1\; =\; 0\; N\; 1\; -\; 1\; \sum \; n\; 2\; =\; 0\; N\; 2\; -\; 1\; x\; [n\; 1,\; n\; 2]\; \cdot \; WN\; 1\; К\; 1\; N\; 1\; WN\; 2\; К\; 2\; N\; 2,\; \{\backslash \; displaystyle\; X\; (k\_\; \{1\},\; k\_\; \{2\})\; =\; \backslash \; sum\; \_\; \{n\_\; \{1\}\; =\; 0\}\; ^\; \{N\_\; \{\; 1\}\; -1\}\; \backslash \; sum\; \_\; \{n\_\; \{2\}\; =\; 0\}\; ^\; \{N\_\; \{2\}\; -1\}\; x\; [n\_\; \{1\},\; n\_\; \{2\}]\; \backslash \; cdot\; W\_\; \{N\_\; \{1\}\}\; ^\; \{k\_\; \{\; 1\}\; n\_\; \{1\}\}\; W\_\; \{N\_\; \{2\}\}\; ^\; \{k\_\; \{2\}\; n\_\; \{2\}\},\}$

где $k\; 1\; =\; 0,\dots ,\; N\; 1\; -\; 1\; \{\backslash \; displaystyle\; k\_\; \{\; 1\}\; =\; 0,\; \backslash \; точки,\; N\_\; \{1\}\; -1\}$и $k\; 2\; =\; 0,\dots ,\; N\; 2\; -\; 1\; \{\backslash \; displaystyle\; k\_\; \{2\}\; =\; 0,\; \backslash \; dots,\; N\_\; \{2\}\; -1\}$и $x\; [n\; 1,\; n\; 2]\; \{\backslash \; displaystyle\; x\; [n\_\; \{1\},\; n\_\; \{2\}]\}$является $N\; 1\; \times \; N\; 2\; \{\backslash \; displaystyle\; N\_\; \{1\}\; \backslash \; times\; N\_\; \{2\}\}$матрица и $WN\; =\; exp\; \; (-\; j\; 2\; \pi \; /\; N)\; \{\backslash \; displaystyle\; W\_\; \{N\}\; =\; \backslash \; exp\; (-j2\; \backslash \; pi\; /\; N)\}$.

Для простоты предположим, что $N\; 1\; =\; N\; 2\; =\; N\; \{\backslash \; displaystyle\; N\_\; \{1\}\; =\; N\_\; \{2\}\; =\; N\}$и система счисления- $(r\; \times \; r)\; \{\backslash \; displaystyle\; (r\; \backslash \; times\; r)\}$($N\; /\; r\; \{\backslash \; displaystyle\; N\; /\; r\}$- целые числа).

Использование замены переменных:

• $ni\; =\; rpi\; +\; qi\; \{\backslash \; displaystyle\; n\_\; \{i\}\; =\; rp\_\; \{i\}\; +\; q\_\; \{i\}\}$, где $pi\; =\; 0,\dots ,\; (N\; /\; r)\; -\; 1;\; q\; i\; =\; 0,\dots ,\; r\; -\; 1;\; \{\backslash \; displaystyle\; p\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; (N\; /\; r)\; -1;\; q\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; r-1;\}$
• $ki\; =\; ui\; +\; vi\; N\; /\; r\; \{\backslash \; displaystyle\; k\_\; \{i\}\; =\; u\_\; \{i\}\; +\; v\_\; \{i\}\; N\; /\; r\}$, где $ui\; =\; 0,\dots ,\; (N\; /\; r)\; -\; 1;\; v\; i\; =\; 0,\dots ,\; r\; -\; 1;\; \{\backslash \; displaystyle\; u\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; (N\; /\; r)\; -1;\; v\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; r-1;\}$

где $i\; =\; 1\; \{\backslash \; displaystyle\; i\; =\; 1\}$или $2\; \{\backslash \; displaystyle\; 2\}$, тогда двумерное ДПФ можно записать как:

$X\; (u\; 1\; +\; v\; 1\; N\; /\; r,\; u\; 2\; +\; v\; 2\; N\; /\; r)\; =\; \sum \; q\; 1\; =\; 0\; r\; -\; 1\; \sum \; q\; 2\; =\; 0\; r\; -\; 1\; [\sum \; p\; 1\; =\; 0\; N\; /\; r\; -\; 1\; \sum \; p\; 2\; =\; 0\; N\; /\; r\; -\; 1\; x\; [rp\; 1\; +\; q\; 1,\; rp\; 1\; +\; q\; 1]\; WN\; /\; rp\; 1\; u\; 1\; WN\; /\; rp\; 2\; u\; 2]\; \cdot \; WN\; q\; 1\; u\; 1\; +\; q\; 2\; u\; 2\; W\; rq\; 1\; v\; 1\; W\; rq\; 2\; v\; 2,\; \{\backslash \; displaystyle\; X\; (u\_\; \{1\}\; +\; v\_\; \{1\}\; N\; /\; r,\; u\_\; \{2\}\; +\; v\_\; \{2\}\; N\; /\; r)\; =\; \backslash \; sum\; \_\; \{q\_\; \{1\}\; =\; 0\}\; ^\; \{r-1\}\; \backslash \; sum\; \_\; \{q\_\; \{2\}\; =\; 0\}\; ^\; \{r-1\}\; \backslash \; left\; [\backslash \; sum\; \_\; \{p\_\; \{1\}\; =\; 0\}\; ^\; \{N\; /\; r-1\}\; \backslash \; sum\; \_\; \{p\_\; \{2\}\; =\; 0\}\; ^\; \{N\; /\; r\; -1\}\; x\; [rp\_\; \{1\}\; +\; q\_\; \{1\},\; rp\_\; \{1\}\; +\; q\_\; \{1\}]\; W\_\; \{N\; /\; r\}\; ^\; \{p\_\; \{1\}\; u\_\; \{1\}\}\; W\_\; \{N\; /\; r\}\; ^\; \{\; p\_\; \{2\}\; u\_\; \{2\}\}\; \backslash \; right]\; \backslash \; cdot\; W\_\; \{N\}\; ^\; \{q\_\; \{1\}\; u\_\; \{1\}\; +\; q\_\; \{2\}\; u\_\; \{2\}\}\; W\_\; \{r\}\; ^\; \{q\_\; \{1\}\; v\_\; \{\; 1\}\}\; W\_\; \{r\}\; ^\; \{q\_\; \{2\}\; v\_\; \{2\}\},\}$

Одноступенчатая «бабочка» для DIT-векторной системы счисления 2x2 FFT

Уравнение выше определяет базовую структуру двумерного DIT radix- $(r\; \times \; r)\; \{\backslash \; displaystyle\; (r\; \backslash \; times\; r)\}$"бабочка". (См. 1-D «бабочка» в Алгоритме БПФ Кули – Тьюки )

Когда $r\; =\; 2\; \{\backslash \; displaystyle\; r\; =\; 2\}$, уравнение можно разбить на четыре суммы: один по тем выборкам x, для которых оба $n\; 1\; \{\backslash \; displaystyle\; n\_\; \{1\}\}$и $n\; 2\; \{\backslash \; displaystyle\; n\_\; \{2\}\}$являются четными, для которого $n\; 1\; \{\backslash \; displaystyle\; n\_\; \{1\}\}$четно, а $n\; 2\; \{\backslash \; displaystyle\; n\_\; \{2\}\}$нечетно, один из который $n\; 1\; \{\backslash \; displaystyle\; n\_\; \{1\}\}$нечетный, а $n\; 2\; \{\backslash \; displaystyle\; n\_\; \{2\}\}$четный, и один, для которого оба $n\; 1\; \{\backslash \; displaystyle\; n\_\; \{1\}\}$и $n\; 2\; \{\backslash \; displaystyle\; n\_\; \{2\}\}$нечетные, и это приводит к:

$X\; (k\; 1,\; k\; 2)\; =\; S\; 00\; (k\; 1,\; k\; 2)\; +\; S\; 01\; (k\; 1,\; k\; 2)\; WN\; k\; 2\; +\; S\; 10\; (k\; 1,\; k\; 2)\; WN\; k\; 1\; +\; S\; 11\; (k\; 1,\; k\; 2)\; WN\; k\; 1\; +\; k\; 2,\; \{\backslash \; displaystyle\; X\; (k\_\; \{1\},\; k\_\; \{2\})\; =\; S\_\; \{00\}\; (k\_\; \{1\},\; k\_\; \{2\})\; +\; S\_\; \{01\}\; (k\_\; \{\; 1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{k\_\; \{2\}\}\; +\; S\_\; \{10\}\; (k\_\; \{1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{k\_\; \{1\}\}\; +\; S\_\; \{11\; \}\; (k\_\; \{1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{k\_\; \{1\}\; +\; k\_\; \{2\}\},\}$

где $S\; ij\; (k\; 1,\; k\; 2)\; =\; \sum \; n\; 1\; =\; 0\; Н\; /\; 2\; -\; 1\; \sum \; n\; 2\; =\; 0\; N\; /\; 2\; -\; 1\; x\; [2\; n\; 1\; +\; i,\; 2\; n\; 2\; +\; j]\; \cdot \; W\; N\; /\; 2\; n\; 1\; k\; 1\; W\; N\; /\; 2\; n\; 2\; k\; 2.\; \{\backslash \; displaystyle\; S\_\; \{ij\}\; (k\_\; \{1\},\; k\_\; \{2\})\; =\; \backslash \; sum\; \_\; \{n\_\; \{1\}\; =\; 0\}\; ^\; \{N\; /\; 2-1\}\; \backslash \; sum\; \_\; \{n\_\; \{2\}\; =\; 0\}\; ^\; \{N\; /\; 2-1\}\; x\; [2n\_\; \{1\}\; +\; i,\; 2n\_\; \{2\}\; +\; j]\; \backslash \; cdot\; W\_\; \{N\; /\; 2\}\; ^\; \{n\_\; \{1\}\; k\_\; \{1\}\}\; W\_\; \{N\; /\; 2\}\; ^\; \{\; n\_\; \{2\}\; k\_\; \{2\}\}.\}$

Аналогично, децимация по частоте (DIF, также называемая алгоритмом Сэнде – Тьюки) алгоритм означает, что разложение основано на частотной области $X\; \{\backslash \; displaystyle\; X\}$, подробнее см. Алгоритм БПФ Кули – Тьюки.

Использование замены переменных:

• $ni\; =\; пи\; +\; ци\; N\; /\; r\; \{\backslash \; displaystyle\; n\_\; \{i\}\; =\; p\_\; \{i\}\; +\; q\_\; \{i\}\; N\; /\; r\}$, где $pi\; =\; 0,\dots ,\; (N\; /\; r)\; -\; 1;\; q\; i\; =\; 0,\dots ,\; r\; -\; 1;\; \{\backslash \; displaystyle\; p\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; (N\; /\; r)\; -1;\; q\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; r-1;\}$
• $ki\; =\; rui\; +\; vi\; \{\backslash \; displaystyle\; k\_\; \{i\; \}\; =\; ru\_\; \{i\}\; +\; v\_\; \{i\}\}$, где $ui\; =\; 0,\dots ,\; (N\; /\; r)\; -\; 1;\; v\; i\; =\; 0,\dots ,\; r\; -\; 1;\; \{\backslash \; displaystyle\; u\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; (N\; /\; r)\; -1;\; v\_\; \{i\}\; =\; 0,\; \backslash \; ldots,\; r-1;\}$

где $i\; =\; 1\; \{\backslash \; displaystyle\; i\; =\; 1\}$или $2\; \{\backslash \; displaystyle\; 2\}$, а уравнение ДПФ можно записать как:

$X\; (ru\; 1\; +\; v\; 1,\; ru\; 2\; +\; v\; 2)\; =\; \sum \; p\; 1\; =\; 0\; N\; /\; r\; -\; 1\; \sum \; p\; 2\; =\; 0\; N\; /\; r\; -\; 1\; [\sum \; q\; 1\; =\; 0\; r\; -\; 1\; \sum \; q\; 2\; =\; 0\; r\; -\; 1\; x\; [p\; 1\; +\; q\; 1\; N\; /\; r,\; п\; 1\; +\; q\; 1\; N\; /\; r]\; W\; rq\; 1\; v\; 1\; W\; rq\; 2\; v\; 2]\; \cdot \; WN\; p\; 1\; v\; 1\; +\; p\; 2\; v\; 2\; WN\; /\; rp\; 1\; u\; 1\; WN\; /\; rp\; 2\; u\; 2,\; \{\backslash \; displaystyle\; X\; (\; ru\_\; \{1\}\; +\; v\_\; \{1\},\; ru\_\; \{2\}\; +\; v\_\; \{2\})\; =\; \backslash \; sum\; \_\; \{p\_\; \{1\}\; =\; 0\}\; ^\; \{N\; /\; r-1\}\; \backslash \; sum\; \_\; \{p\_\; \{2\}\; =\; 0\; \}\; ^\; \{N\; /\; r-1\}\; \backslash \; left\; [\backslash \; sum\; \_\; \{q\_\; \{1\}\; =\; 0\}\; ^\; \{r-1\}\; \backslash \; sum\; \_\; \{q\_\; \{2\}\; =\; 0\}\; ^\; \{r-1\}\; x\; [p\_\; \{\; 1\}\; +\; q\_\; \{1\}\; N\; /\; r,\; p\_\; \{1\}\; +\; q\_\; \{1\}\; N\; /\; r]\; W\_\; \{r\}\; ^\; \{q\_\; \{1\}\; v\_\; \{1\}\}\; W\_\; \{r\}\; ^\; \{q\_\; \{2\}\; v\_\; \{2\}\}\; \backslash \; right]\; \backslash \; cdot\; W\_\; \{N\}\; ^\; \{p\_\; \{1\}\; v\_\; \{1\}\; +\; p\_\; \{2\}\; v\_\; \{2\}\}\; W\_\; \{N\; /\; r\}\; ^\; \{p\_\; \{1\}\; u\_\; \{1\}\}\; W\_\; \{N\; /\; r\}\; ^\; \{p\_\; \{2\}\; u\_\; \{2\}\},\}$

Алгоритм БПФ с разделением оснований оказался полезным методом для 1-DFT. И этот метод был применен к векторно-основному БПФ для получения разделенного векторно-основанного БПФ.

В обычном двумерном векторно-основном алгоритме мы разлагаем индексы $k\; 1,\; k\; 2\; \{\; \backslash \; displaystyle\; k\_\; \{1\},\; k\_\; \{2\}\}$на 4 группы:

$X\; (2\; k\; 1,\; 2\; k\; 2):\; четно-четное\; X\; (2\; k\; 1,\; 2\; k\; 2\; +\; 1):\; четно-нечетное\; X\; (2\; k\; 1\; +\; 1,\; 2\; k\; 2):\; нечетное-четное\; X\; (2\; k\; 1\; +\; 1,\; 2\; k\; 2\; +\; 1):\; нечетно-нечетное\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{lcl\; \}\; X\; (2k\_\; \{1\},\; 2k\_\; \{2\})\; :\; \{\backslash \; text\; \{even-even\}\}\; \backslash \backslash \; X\; (2k\_\; \{1\},\; 2k\_\; \{2\}\; +1)\; :\; \{\backslash \; text\; \{even-\; odd\}\}\; \backslash \backslash \; X\; (2k\_\; \{1\}\; +\; 1,2k\_\; \{2\})\; :\; \{\backslash \; text\; \{odd-even\}\}\; \backslash \backslash \; X\; (2k\_\; \{1\}\; +\; 1,2k\_\; \{2\}\; +1)\; :\; \{\backslash \; text\; \{odd-odd\}\}\; \backslash \; end\; \{array\}\}\}$

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

$X\; (2\; k\; 1,\; 2\; k\; 2):\; четно-четное\; X\; (2\; k\; 1,\; 2\; k\; 2\; +\; 1):\; четно-нечетное\; X\; (2\; k\; 1\; +\; 1,\; 2\; k\; 2):\; нечетно-четное\; X\; (4\; k\; 1\; +\; 1,\; 4\; k\; 2\; +\; 1):\; нечетное-нечетное\; X\; (4\; k\; 1\; +\; 1,\; 4\; k\; 2\; +\; 3):\; нечетное-нечетное\; X\; (4\; k\; 1\; +\; 3,\; 4\; k\; 2\; +\; 1):\; нечетно-нечетное\; X\; (\; 4\; к\; 1\; +\; 3,\; 4\; к\; 2\; +\; 3):\; нечетно-нечетное\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{lcl\}\; X\; (2k\_\; \{1\},\; 2k\_\; \{2\})\; :\; \{\backslash \; text\; \{четное-четное\; \}\}\; \backslash \backslash \; X\; (2k\_\; \{1\},\; 2k\_\; \{2\}\; +1)\; :\; \{\backslash \; text\; \{четно-нечетное\}\}\; \backslash \backslash \; X\; (2k\_\; \{1\}\; +\; 1,2k\_\; \{2\})\; :\; \{\; \backslash \; text\; \{odd-even\}\}\; \backslash \backslash \; X\; (4k\_\; \{1\}\; +\; 1,4k\_\; \{2\}\; +1)\; :\; \{\backslash \; text\; \{odd-odd\}\}\; \backslash \backslash \; X\; (4k\_\; \{1\}\; +\; 1,4k\_\; \{2\}\; +3)\; :\; \{\backslash \; text\; \{odd-odd\}\}\; \backslash \backslash \; X\; (4k\_\; \{1\}\; +\; 3,4k\_\; \{2\}\; +1)\; :\; \{\backslash \; text\; \{odd-odd\}\}\; \backslash \backslash \; X\; (4k\_\; \{1\}\; +\; 3,4k\_\; \{2\}\; +3)\; :\; \{\backslash \; text\; \{odd-odd\}\}\; \backslash \; end\; \{array\}\}\}$

Это означает четвертый член в системе счисления 2-DIT - $(2\; \times \; 2)\; \{\backslash \; displaystyle\; (2\; \backslash \; times\; 2)\}$уравнение, $S\; 11\; (k\; 1,\; k\; 2)\; WN\; k\; 1\; +\; k\; 2\; \{\backslash \; displaystyle\; S\_\; \{11\; \}\; (k\_\; \{1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{k\_\; \{1\}\; +\; k\_\; \{2\}\}\}$становится:

$A\; 11\; (k\; 1,\; k\; 2)\; WN\; k\; 1\; +\; k\; 2\; +\; A\; 13\; (k\; 1,\; k\; 2)\; WN\; k\; 1\; +\; 3\; k\; 2\; +\; A\; 31\; (k\; 1,\; k\; 2)\; WN\; 3\; k\; 1\; +\; k\; 2\; +\; A\; 33\; (k\; 1,\; k\; 2)\; WN\; 3\; (к\; 1\; +\; к\; 2),\; \{\backslash \; displaystyle\; A\_\; \{11\}\; (k\_\; \{1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{k\_\; \{1\}\; +\; k\_\; \{2\}\}\; +\; A\_\; \{13\}\; (k\_\; \{1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{k\_\; \{1\}\; +\; 3k\_\; \{2\}\}\; +\; A\_\; \{31\}\; (k\_\; \{1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{3k\_\; \{1\; \}\; +\; k\_\; \{2\}\}\; +\; A\_\; \{33\}\; (k\_\; \{1\},\; k\_\; \{2\})\; W\_\; \{N\}\; ^\; \{3\; (k\_\; \{1\}\; +\; k\_\; \{2\})\},\}$

где $A\; ij\; (k\; 1,\; k\; 2)\; =\; \sum \; n\; 1\; =\; 0\; N\; /\; 4\; -\; 1\; \sum \; n\; 2\; =\; 0\; N\; /\; 4\; -\; 1\; x\; [4\; n\; 1\; +\; я,\; 4\; n\; 2\; +\; j]\; \cdot \; WN\; /\; 4\; n\; 1\; К\; 1\; WN\; /\; 4\; n\; 2\; K\; 2\; \{\backslash \; displaystyle\; A\_\; \{ij\}\; (k\_\; \{1\},\; k\_\; \{2\})\; =\; \backslash \; sum\; \_\; \{n\_\; \{1\}\; =\; 0\}\; ^\; \{N\; /\; 4-1\}\; \backslash \; sum\; \_\; \{n\_\; \{2\}\; =\; 0\}\; ^\; \{N\; /\; 4-1\}\; x\; [4n\_\; \{1\}\; +\; i,\; 4n\_\; \{2\}\; +\; j]\; \backslash \; cdot\; W\_\; \{N\; /\; 4\}\; ^\; \{n\_\; \{1\}\; k\_\; \{1\}\}\; W\_\; \{N\; /\; 4\}\; ^\; \{n\_\; \{2\}\; k\_\; \{2\}\}\}$

Затем 2-DN на N DFT получается последовательное использование указанного выше разложения, вплоть до последней стадии.

Было показано, что алгоритм системы счисления разбиения вектора сохранил около 30% сложных умножений и примерно такое же количество сложных сложений для типичного $1024\; \times \; 1024\; \{\backslash \; displaystyle\; 1024\; \backslash \; times\; 1024\}$массив в сравнении с алгоритмом векторной системы счисления.