3次元ベクトルのユークリッドノルム計算のハードウェアアルゴリズム A hardware algorithm for computing the Euclidean norm of a 3-D vector

3次元コンピュータグラフィクス等において、3次元ベクトルの正規化等に用いられるベクトルのユークリッドノルムの計算のためのハードウェアアルゴリズムを提案する。通常の計算に必要な三つの平方計算のうちの一つを不要とし、他の二つと加算を平方根計算と重畳させることにより、高速計算を実現する。用いる基数や桁集合、剰余の表現法、桁選択関数等により、さまざまなバージョンを設計できる。これらはいずれも、順序回路あるいは組合せ回路として実現できる。また、パイプライン化も可能である。回路は規則正しい配列構造をもち、VLSI実現に適している。

A hardware algorithm for computing the Euclidean norm of a 3-dimensional (3-D) vector which often appears in 3-D Computer Graphics is proposed. One of the three squarings required for the usual computation is removed and the other two squarings as well as the two additions are overlapped with the square rooting. Different specific versions of the algorithm are possible, depending on the radix, the redundancy factor of the digit set, the type of representation of the residual, and the digit selection function. Any version of the algorithm can be imlemented as a sequential (folded) circuit or a combinational (unfolded) circuit. Pipelining can also be used. The implementations have a regular cellular array structure suitable for VLSI realization.