От сути БПФ переходим к реализации на 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, который теперь можно улучшить при помощи приведения операции сдвига к делению для отрицательных чисел.
Ранее, когда я рассматривал ДПФ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, который теперь можно улучшить при помощи приведения операции сдвига к делению для отрицательных чисел.
Комментариев нет:
Отправить комментарий