БПФ8 на verilog

От сути БПФ переходим к реализации на Verilog. Я буду писать ДПФ8 с двумя 4-точечными бабочками. Реализация будет полностью параллельной и считать будем за один такт:

Ранее, когда я рассматривал ДПФ4 на примере, была выведена формула для 4-точечной бабочки. Комбинаторная реализация выглядит так:
BF4_comb.v
И тут есть о чем поговорить. Когда рассматривался CORDIC на verilog, вылезла проблема: отрицательные числа и операция сдвига для них. Простой пример, который можно повторить в любом калькуляторе: int(-5) / 2 = -2, int(-5) >> 1 = -3, int(5) / 2 =2, int(5) >> 1 = 2. Результаты по модулю отличаются на единицу в случае сдвига и равны при делении. Как сделать операцию сдвига эквивалентной делению. Прибавить единицу нельзя, потому что int(-5) / 2 = -2, (int(-5) >> 1)  + 1= -2, но int(-4) / 2 = -2 и int(-4) >> 1 = -2. То есть для четных чисел прибавка единицы дает неверный ответ. Ответ оказывается достаточно очевидным: прибавить половину, но половину чего и куда? Половину делителя к исходному числу. Проверка:
Делитель a: 2;
Половина делителя b = a/2;
Сдвиг с = log2(a);
Делимое d = -5;
x = d+b >> c = -5+1 >> 1 = -4 >> 1 = -2. Если подставить любые числа, но равенство не нарушится.
Вопрос: как отразятся изменения на положительные числа? 5 >> 1 = (5 + 1) >> 1  = 3. А это получается округление. Как в школе учили: 2,5 это 3, а 2,2 это 2.

Если посмотреть картинку сверху, то в ней будет одна неточность: чтобы размеры входных данных соответствовали размерам выходных - надо добавить множитель 1/N, то есть по сути усреднить результат. Отсюда сдвиг на 2 вправо для реальной части на четных выходах и по 1 вправо для реальной и мнимой части нечетных выходов.

Раз уж заговорили о размерах входных данных и прочего. Входные данные представлены размерностью 15:0, но по факту данные должны быть 14 битные. Это видно в топовом файле:
FFT8.v
input wire [ 13 : 0 ] din,
Почему так сделано? Во-первых все из-за пресловутых отрицательных чисел. Мы не можем без переполнения умножить максимальное отрицательное числа на -1. Поэтому нужно либо ограничивать входной диапазон от максимального положительного числа до минус максимального положительного, либо на один бит расширять представление числа. Почему я все же расширил представление? Потому что в процессе сложения/умножения мы можем получить число с переполнением, поэтому запаса даже в 1 бит хватит, чтобы в процессе отладки найти проблемное место. Ну и последняя и самая важная причина: выше показано, что мы считаем теперь с округлением, а не отсечением дробной части.

Файл length.v нам уже знаком и служит для вычисления длины гипотенузы. С ним разобрались давно. Вот он считает с отсечением дробной части, что будет видно на результатах тестов.

Осталось только рассмотреть модуль восстановления БПФ8 из ДПФ4. То есть переходим к рассмотрению арифметических операций над комплексными числами. Начнем с умножения: complex_mult.v. Формулу для умножения двух комплексных чисел вспомнит любой, почему прибавляю 512? Потому что потом сдвигаю на 10, или делю на 1024. Почему такая размерность? Я выбрал 12 битные поворачивающие коэффициенты, то есть они могут лежать в диапазоне -2048..2047. Здесь опять же есть вариант ограничить диапазон симметрично -2047..2047, но смысла в этом нет. Дело в том, что модуль поворачивающий множителя всегда равен единице, то есть реальная и мнимая часть лежать в диапазоне -1..1. Чему в целочисленных равна единица? 2047. А чему равен cos(45) ? 1447. Как умножить число на cos(45) в целочисленных? X*1447/2047. Всплыла операция деления. Я хочу изменить деление на сдвиг, потому что делить за один такт сложно. Для этого достаточно диапазон поворачивающих коэффициентов ограничить -1024..1024. Тогда cos(45) = 724, а выражение X*724/1024 можно заменить на X*724 >>> 10.
Сложение комплексных чисел complex_sum.v: все просто и очевидно. Складываем два числа, делим на два, чтобы размерность на выходе была равна размерности числе на входе.
Ну и завершает это все топовый модуль для восстановления БПФ8 block_FFT8.v. В нем задействовано 4 умножителя и 8 сумматоров. По факту мы получим реализацию формулы ДПФ,  деленную на N, где N - количество точек в БПФ.

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

от ДПФ к БПФ

Прежде чем начать разбираться в БПФ, введем понятия поворачивающего множителя W:

Важно запомнить, что комплексная экспонента со знаком минус, то есть в тригонометрическом виде будет присутствовать cos и -sin, которые будут храниться в памяти. 

Рассмотрим свойства W. Для примера возьмем N = 4. При этом m = 0..N-1.

Получили, что для расчета N коэффициентов W, достаточно посчитать первые N/2 коэффициентов. Это правило справедливо для любого N.

Теперь выведем формулу БПФ с использованием поворачивающего множителя W. Для этого на первом шаге разобьем сумму на две части, выделив четные и нечетные отчеты в две отдельные последовательности.

Получили, что для вычисления N точечного ДПФ достаточно посчитать два N/2 точечных ДПФ из четных и нечетных слагаемых и объединить их. Пользуясь свойствами поворачивающего множителя, можно показать, что для вычисление X(m+N/2) не нужно считать W для него:

Для вычисления X(m+N/2) не нужно ничего считать: достаточно поменять знак поворачивающего множителя  и использовать две суммы, полученные для X(m). 

Итого: для вычисления 8 точечного ДПФ нужно посчитать два 4 точечных ДПФ. Так же можно продолжить и вычислить 4 точечное ДПФ через два 2 точечных.

Далее будем переносить алгоритм на verilog и разбираться во всех тонкостях.