Извлечение квадратного корня из INT

Покажу простенький алгоритм извлечения квадратного корня из числа. В Verilog нативный тип данных - integer, поэтому рассказываю только про него, а вообще алгоритм нормально "ляжет" и на плавающую точку. Рассмотрим в качестве примера квадратный корень из 189. 189 в десятичной система == 1011 1101 в двоичной. Запишем число в двоичной форме и, начиная со старшего разряда, выделим участки, кратные двум битам.

Получившиеся участки обозначены красными номерами 1,2,3,4. Если извлекается корень из числа длиной 8 бит, то искомое число будет занимать 4 бита, потому что при умножении двух чисел их длина будет равна сумме длин каждого слова. В нашем случае искомое число будет иметь длину 4. Дальше буду говорить о числах в двоичной форме. 

Возьмем первый участок числа из двух бит, равный 10. Какое число, умноженное на себя будет меньше или равно 10? Очевидно, что это 1: 1*1 == 01. Так как 01 < 10 запишем в искомое число 1.

Дальше берем второй участок, равный 1011. В искомом слове уже есть 1 и к ней в конец мы приписываем еще одну 1, получается 11. 11*11 == 1001 < 1011. Значит искомое число остается равным 11.

Третий участок: 101111. Дописываем в конец искомое числа 1, получается 111 и 111*111 == 110001 > 101111 (sic!). Так как число получилось больше, чем на третьем участке, вместо 1 в конец искомого числа поставим 0. Искомое число тогда станет 110.

Четвертый участок. В конец искомого числа ставим 1, получается 1101, 1101*1101 == 10101001 < 10111101 => искомое число == 1101. 

Примерно тоже самое делает функция на Си. Только для числа 189 четыре действия будут выглядеть так:

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

#include <iostream> #include <math.h> #include <limits.h> using namespace std; short sqrt(short x) { short ans = 0; short tmp = 0; short local_mask = 0b11; short mask = 0; for(int i = 3; i>=0; i--) { mask |= local_mask << (2*i); tmp = x & mask; ans ^= 1 << i; if(tmp < ans*ans) ans ^= 1 << i; } return ans; } int main () { short x = 189; cout << sqrt(x); return 0; }

Вывод: 13 (1101)

Мне кажется более естественным в этом случае использовать конвейер, потому что все четыре действия однотипные и нам в любом случае использовать умножитель 4*4.
Первый вариант: когда нам надо просто посчитать корень из числа, при этом у нас гарантированно есть в запасе 4 такта. Пусть не будет входа en, выхода busy, просто код:

module test( input wire clk, input wire [ 7 : 0 ] din, output wire [ 3 : 0 ] sqrt ); reg signed [ 7 : 0 ] r_mask = 8'b0; wire [ 7 : 0 ] w_tmp = din & r_mask; reg [ 3 : 0 ] r_ans_mask = 4'b0; reg [ 3 : 0 ] r_ans = 4'b0; wire [ 7 : 0 ] w_ans2 = r_ans * r_ans; reg [ 1 : 0 ] cnt = 2'b00; reg [ 3 : 0 ] r_out = 4'b0; always@(posedge clk) begin cnt <= cnt + 1'b1; case(cnt) 2'b0: begin if(w_ans2 > w_tmp) r_out <= r_ans ^ r_ans_mask; else r_out <= r_ans; r_mask <= 8'b1100_0000; r_ans <= 4'b1000; r_ans_mask <= 4'b1000; end default: begin if(w_ans2 > w_tmp) r_ans <= r_ans ^ (r_ans_mask >> 1) ^ r_ans_mask; else r_ans <= r_ans ^ (r_ans_mask >> 1); r_mask <= r_mask >>> 2; r_ans_mask <= r_ans_mask >> 1; end endcase end assign sqrt = r_out; endmodule

Остановлюсь подробнее на этом варианте.
+ Относительно мало задействовано регистров и логики.
+ Достаточно просто отлаживать из-за малого количества сигналов.
- Выходное значение появляется с задержкой в 4 такта, за которые значение на входе не должно меняться. Из этого следует, что такую схему можно использовать при частоте clk минимум в 4 раза чаще частоты входных данных. В случае множителя "4" все не так плохо, но если нужно извлечь корень из 32 битного слова, то множитель уже будет "16", соответственно задержка (latency) тоже станет равна 16.

Если частота поступления данных приближается к частоте clk, то тут есть 2 варианта. Первый - параллелить расчет корня. Второй - делать конвейер с памятью. Об этом подробнее.
Пусть каждый clk защелкиваются входные данные. По идее нам нужно 4 такта на расчет. Но если сделать сдвиговый регистр на четыре значения, то входное слово будет доступно четыре такта, за которые мы сможем вычислить корень. При этом промежуточные значения расчетов нужно так же помещать в сдвиговый регистр такой же длины, чтобы каждая новая ступень конвейера знала что с чем считать. Использовать такой вариант имеет смысл только при частоте входных данных == частоте clk && нужно экономить логические элементы. При этом получается максимальная производительность, потому что между триггерами минимум логики, следовательно меньше задержки, следовательно выше возможная частота. Выглядит это примерно так:

module test( input wire clk, input wire [ 7 : 0 ] din, output wire [ 3 : 0 ] sqrt ); reg [ 7 : 0 ] r_din [ 0 : 3 ]; reg [ 7 : 0 ] r_mask[ 0 : 3 ]; initial begin r_mask[0] = 8'b1100_0000; r_mask[1] = 8'b1111_0000; r_mask[2] = 8'b1111_1100; r_mask[3] = 8'b1111_1111; end wire [ 7 : 0 ] w_tmp[ 0 : 3 ]; assign w_tmp[0] = r_din[0] & r_mask[0]; assign w_tmp[1] = r_din[1] & r_mask[1]; assign w_tmp[2] = r_din[2] & r_mask[2]; assign w_tmp[3] = r_din[3] & r_mask[3]; reg [ 3 : 0 ] r_ans_mask [ 0 : 3 ]; initial begin r_ans_mask[0] = 4'b1000; r_ans_mask[1] = 4'b0100; r_ans_mask[2] = 4'b0010; r_ans_mask[3] = 4'b0001; end reg [ 3 : 0 ] r_ans[ 0 : 3 ]; wire [ 7 : 0 ] w_ans[ 0 : 3 ]; assign w_ans[0] = r_ans[0] * r_ans[0]; assign w_ans[1] = r_ans[1] * r_ans[1]; assign w_ans[2] = r_ans[2] * r_ans[2]; assign w_ans[3] = r_ans[3] * r_ans[3]; integer i; reg [ 3 : 0 ] r_out ; always@(posedge clk) begin r_din[0] <= din; r_din[1] <= r_din[0]; r_din[2] <= r_din[1]; r_din[3] <= r_din[2]; r_ans[0] <= 4'b1000; for(i = 0; i < 3; i = i + 1) begin if(w_ans[i] > w_tmp[i]) r_ans[i+1] <= r_ans[i] ^ r_ans_mask[i+1] ^ r_ans_mask[i]; else r_ans[i+1] <= r_ans[i] ^ r_ans_mask[i+1]; end if(w_ans[3] > w_tmp[3]) r_out <= r_ans[3] ^ r_ans_mask[3]; else r_out <= r_ans[3]; end assign sqrt = r_out; endmodule

Еще мне нравится в этом случае использовать цикл for, который надо избегать в принципе.
Ну и напоследок полностью на логике вариант. Прелесть ПЛИС в том, что можно "выдергивать" отдельные биты числа без лишних затрат, что по сути аналогично в Си взятию маски со сдвигом. Поэтому алгоритм, который я показал вначале можно на Verilog записать так:

module test( input wire clk, input wire [ 7 : 0 ] din, output wire [ 3 : 0 ] sqrt ); assign sqrt[3] = din[7:6] == 2'b00 ? 1'b0 : 1'b1; assign sqrt[2] = din[7:4] < {sqrt[3], 1'b1} * {sqrt[3], 1'b1} ? 1'b0 : 1'b1; assign sqrt[1] = din[7:2] < {sqrt[3:2], 1'b1} * {sqrt[3:2], 1'b1} ? 1'b0 : 1'b1; assign sqrt[0] = din[7:0] < {sqrt[3:1], 1'b1} * {sqrt[3:1], 1'b1} ? 1'b0 : 1'b1; endmodule