平方根を求める開平演算には各種のアルゴリズムが知られていますが、ここでは古くから知られているアルゴリズムに基づいて論理を作成することにします。このアルゴリズムの解説につきましては、他のウェブページをご参照ください。
32ビット整数を開平するためには、2桁開平演算モジュールを16段接続する必要があります。ここでは2桁開平演算モジュールを4段接続した8桁開平演算モジュールを準備し、中間結果をレジスタに格納しながら同じモジュールで4回の処理を行う、ステートマシン構成としました。こうすることで、クロック周波数を上げ、ロジックエレメント数を節約することができます。
この論理をVerilog-2001で記述したソースコードを以下に示します。
module sqrt(
input [31:0] in,
output reg [15:0] result,
output [15:0] checker,
input clock);
assign checker = {r[11:0], r4};
reg [45:0] s;
wire [45:0] s4;
reg [15:0] t, r;
wire [15:0] t4;
wire [3:0] r4;
sq4 u1 (.s(s), .t(t), .ss(s4), .tt(t4), .r4(r4));
reg [1:0] state;
always@(posedge clock) begin
state <= state + 2'h1;
case(state)
2'h0: begin
s <= {14'h0, in};
t <= 16'h0;
result <= {r[11:0], r4};
end
default: begin
s <= s4;
t <= t4;
r <= {r[11:0], r4};
end
endcase
end
endmodule
module sq4 (
input [45:0] s,
input [15:0] t,
output [45:0] ss,
output [15:0] tt,
output [3:0] r4);
wire [45:0] ws;
wire [15:0] wt;
sq2 u1(.s(s), .t(t), .ss(ws), .tt(wt), .r2(r4[3:2]));
sq2 u2(.s(ws), .t(wt), .ss(ss), .tt(tt), .r2(r4[1:0]));
endmodule
module sq2 (
input [45:0] s,
input [15:0] t,
output [45:0] ss,
output [15:0] tt,
output [1:0] r2);
wire [45:0] ws;
wire [15:0] wt;
sq1 u1(.s(s), .t(t), .ss(ws), .tt(wt), .r1(r2[1]));
sq1 u2(.s(ws), .t(wt), .ss(ss), .tt(tt), .r1(r2[0]));
endmodule
module sq1 (
input [45:0] s,
input [15:0] t,
output [45:0] ss,
output [15:0] tt,
output r1);
wire [16:0] d = s[45:30] - {t[14:0], 1'b1};
assign ss = d[16] ? {s[43:0], 2'b0} : {d[13:0], s[29:0], 2'b0};
assign tt = d[16] ? {t[14:0], 1'b0} : {t[14:0], 1'b1} + 16'h1;
assign r1 = ~d[16];
endmodule
生成された論理ブロックは次のようになります。
上図は最上位のモジュールで、左上のレジスタが2ビットのステートカウンタで、0から3までの4つのステートを形成します。
ステート0で、入力信号inの上位を0で拡張したものをレジスタsに設定し、レジスタtをクリアします。中央部の薄緑の部分が8桁開平演算モジュール“sq4”です。ステート1〜3では、sq4の出力がレジスタsおよびtに書き込まれ、再度sq4に供給されます。
モジュールsq4およびその内部で使用しているモジュールsq2の構成を下図に示します。
8桁開平モジュールsq4は4桁開平モジュールsq2を二段接続し、sq2は2桁開平モジュールsq1を二段接続しています。
2桁開平モジュールsq1の構成を下図に示します。
このモジュールは二組の加減算器とマルチプレクサで構成され、古くから知られたアルゴリズムによる開平演算を2桁分実行します。
この論理の動作を、Qualtus II付属のシミュレータでテストした結果を下図に示します。上の図は小さな値を開平した結果を10進で表示しています。
このモジュールは、4状態をとるステートマシンとして構成されていますので、クロック信号clockの立ち上がりに同期して入力信号を取り込んだ後、4クロック後に出力に入力信号の平方根が現れます。
上のシミュレーション結果を見ますと、1の平方根は1、16の平方根は4、121の平方根は11、256の平方根は16、65,536の平方根は256、640,000の平方根は800、6,4000,000の平方根は8,000と正しく計算されています。
上の図は大きな値をチェックしたシミュレーション結果で、こちらは数値を16進で示しています。これをみますと、FFFEの二乗であるFFFC0004の平方根までは正しく計算されていますが、FFFFの二乗であるFFFE0001の平方根はFFFCと、入力信号に許される最大値付近で多少の誤差が生じています。これは信号処理に使用する際の実用上は大きな問題ではないかもしれませんが、数値演算モジュールとしては不完全であり、このバグの修正は今後の課題です。