Как получить квадратный корень для 32-битного ввода только за один такт?

Я хочу создать синтезируемый модуль в Verilog, который займет всего один цикл вычисления квадратного корня из заданного входа 32 бит.

[Edit1] отремонтированный код

Недавно были найдены результаты, когда даже если тесты определяют, все было в порядке, поэтому я копаю глубже и узнал, что у меня была глупая ошибка в моем уравнении, и из-за конфликтов имен с моей средой pgm тесты получили ложные срабатывания, поэтому я забыл об этом раньше. Теперь он работает во всех случаях, как должен.

Лучшее, что я могу придумать (кроме аппроксимации или большого LUT ), это двоичный поиск без умножения, здесь код C ++ :

 //--------------------------------------------------------------------------- WORD u32_sqrt(DWORD xx) // 16 T { DWORD x,m,a0,a1,i; const DWORD lut[16]= { // m*m 0x40000000, 0x10000000, 0x04000000, 0x01000000, 0x00400000, 0x00100000, 0x00040000, 0x00010000, 0x00004000, 0x00001000, 0x00000400, 0x00000100, 0x00000040, 0x00000010, 0x00000004, 0x00000001, }; for (x=0,a0=0,m=0x8000,i=0;m;m>>=1,i++) { a1=a0+lut[i]+(x<<(16-i)); if (a1<=xx) { a0=a1; x|=m; } } return x; } //--------------------------------------------------------------------------- 

Стандартный бинарный поиск sqrt(xx) устанавливает биты x из MSB в LSB, так что результат x*x <= xx . К счастью, мы можем избежать умножения, просто перепишем вещь как увеличивающий множитель ... на каждой итерации более старый x*x результат можно использовать следующим образом:

 x1 = x0+m x1*x1 = (x0+m)*(x0+m) = (x0*x0) + (2*m*x0) + (m*m) 

Где x0 - значение x от последней итерации, а x1 - фактическое значение. m - вес фактического обработанного бита. (2*m) и (m*m) являются постоянными и могут использоваться как LUT и бит-сдвиг, поэтому не нужно умножать. Необходимо только дополнение. К сожалению, итерация связана с последовательным вычислением, запрещающим паралелизацию, поэтому результат в лучшем случае составляет 16 т.

В коде a0 представляет последние x*x и a1 представляет собой фактический итерированный x*x

Как вы можете видеть, sqrt выполняется в 16 x (BitShiftLeft,BitShiftRight,OR,Plus,Compare) где бит-сдвиг и LUT могут быть жестко привязаны.

Если у вас есть сверхбыстрые ворота для этого по сравнению с остальными, вы можете умножить входные тактовые сигналы на 16 и использовать это как внутреннее время для модуля SQRT . Что-то похожее на старые времена, когда в MC были часы MC, как разделение исходных тактовых импульсов процессора CPU / MCU s ... Таким образом, вы можете получить 1T синхронизацию (или несколько из них зависит от коэффициента умножения).

Я получил код здесь

  module sqrt( input[31:0]a, output[15:0]out ); reg [31:0]temp; reg[14:0]x; [email protected](a) begin if(a<257)x=4; if(a>256 && a<65537)x=80; if(a>65536 && a<16777217)x=1000; if(a>16777216 && a<=4294967295)x=20000; temp=(x+(a/x))/2; temp=(temp+(a/temp))/2; temp=(temp+(a/temp))/2; temp=(temp+(a/temp))/2; temp=(temp+(a/temp))/2; temp=(temp+(a/temp))/2; temp=(temp+(a/temp))/2; end assign out=temp; endmodule 

Обычным способом сделать это в аппаратных средствах является использование CORDIC . Общая реализация позволяет вычислять множество трансцендентных функций (cos / sin / tan) и … квадратных корней в зависимости от того, как вы инициализируете и управляете CORDIC.

Это итеративный алгоритм, поэтому для этого в один цикл вы разворачиваете цикл на столько итераций, сколько требуется для вашей желаемой точности, и объединяйте экземпляры вместе.

В частности, если вы управляете CORDIC в режиме векторизации, инициализируйте его с помощью [x, 0] и поверните на 45 gradleусов, конечный выход [x, y] будет мультипликативной. т.е. sqrt (x) = x ‘* sqrt (2) * K

Существует преобразование в логарифм, сокращение пополам и преобразование назад.
Для представления о том, как реализовать «комбинаторный» журнал и антилог , см . Статью EDN Майкла Данна, показывающую приоритетный кодер, таблицу баррелей и таблицу поиска, с тремя вариантами журнала в System Verilog для загрузки.
(Priority encoder, barrel shifter & lookup table выглядят многообещающими для «one-step-Babylonian / Heron / Newton / -Raphson». Но для этого, вероятно, потребуется таблица поиска по 128 бит на 9 бит).

Показывая «verilog»,
Толе Сутично: «Оптимизированный квадратный корневой алгоритм для реализации в аппаратном обеспечении FPGA» показывает комбинаторную реализацию модифицированного (двоичного) алгоритма с цифрами по цифре.

  • Как вы проверяете двоичное дерево поиска?
  • Найти 2 числа в несортированном массиве, равном заданной сумме
  • LINQ, чтобы найти ряд последовательных чисел
  • Как я могу эффективно определить, является ли многоугольник выпуклым, невыпуклым или сложным?
  • Подключить 4 проверить для алгоритма выигрыша
  • Как создать комбинации нескольких векторов без контуров жесткого кодирования в C ++?
  • Обратный алгоритм Фибоначчи?
  • Какое распределение вы получаете от этой случайной случайной перетасовки?
  • Произвольное генерирование букв в соответствии с их частотой использования?
  • Самый простой алгоритм построения Вороного?
  • Реализация алгоритма Хой Шамоса с помощью C #
  • Давайте будем гением компьютера.