AR# 8652

4.1i CORE Generator - Square Root コアのインプリメンテーション (XC4000 および Virtex)

説明

キーワード : square root, implementation, algorithm, インプリメンテーション, アルゴリズム

重要度 : 標準

概要 : このアンサーでは、Square Root コアのインプリメンテーションに関する情報を提供します。

ソリューション

コアのインプリメンテーションは、次のような 121 (10 進数) の平方根を使用した例で表すことができます。

121 を 2 進数で表すと、01111001 になります。

1. この 2 進数の値を 2 桁ずつに区切ると、01 11 10 01 になります。

2. 左から 2 桁の数字 (MSB) と等しい平方根を探します。 この場合は、01 に等しい平方根は 1 ですから、1 が出力の MSB となります。

3. この最初の 2 桁から 1 を差し引いて、次の 2 桁と合わせると、 011 になります。

4. この値の第 2 ビットは、次の条件を満たす必要があります。 10n x n <= 011 (「10n」の「10」は、Square Root モジュールの出力の MSB を取って、それを左にシフトし、0 を追加した値です)

この例では、n = 0 : 100 x 0 = 0 <= 011.

(n = 1 では、101 x 1 = 101 となり 011 より大きくなってしまいます)

これで、出力の第 2 ビットが 0 となり、MSB から 第 2 桁までの出力値は 10 であることが計算されました。

5. n は 0 なので、011 から 0 x 100=000 を差し引き、次の 2 桁、10 を追加します。 これで、01110 になります。

6. この値の第 3 ビットは、条件 100n x n <= 01110 を満たす必要があります。 この 100 は、先の計算で得た 10 を左にシフトして、0 を追加したものです。

この例では、1001 x 1 = 1001 <= 01110 であるので、n = 1 となります。

これで、出力の第 3 ビットが 1 となり、MSB から 第 3 桁までの出力値は 101 であることが計算されました。

7. 01110 (01110 - 01001 = 00101) から 1001 を差し引き、最後の 2 桁、01 を追加すると、 010101 になります。

8. この値の第 4 ビットは、条件 1010n x n <= 010101 を満たす必要があります。 この 101 は、先の計算で得た値を左にシフトして、0 を追加したものです。

この例では、n=1: 10101 x 1 = 10101 <= 010101 になります。これで、出力の第 4 ビットが 0 となり、MSB から 第 4 桁までの出力値は 1011 であることが計算されました。

9. 010101 から 10101 を差し引きます。差し引いた値が 0 になるので、最終的に 1011 (10 進法で 11) になり、121 の平方根 = 11 になります。

ステップ 9 の減算で得られる値が 0 にならない場合は、0 が得られるまで、0 を繰り越します。 出力値がどれだけ正確に得られるかは、出力に要求されるビット数によって異なります。
AR# 8652
日付 12/13/2006
ステータス アーカイブ
種類 一般