演算アルゴリズムのストリング・グラフ表現

IPSJ

Bibliographic Information

Other Title
  • String Graph Representations for Arithmetic Algorithms
  • ハードウェアアルゴリズム

Search this article

Abstract

コンピュータ・グラフィックス分野が急激に発展してきたので 32ないし64ビットの浮動小数点演算がごく普通に要求されるようになってきた.このように処理桁数が増加してくると 桁上げ伝播による遅延が問題になり 桁上げ伝播のない演算方式が注目されている.従来 桁上げ保存加算器が主として桁上げ伝播のない演藻方式に利用されていた.しかし 最近 ｛-1 0 +1｝で表現する冗長2進加算器を利用する方が 相性がよく すぐれた規則性をもち 加減乗除 開平などの高速演算アルゴリズムを導出できることがわかってきた.本論文では これらの演算アルゴリズムをストリング・グラフと呼ぶ表現によって視覚化または形式化することを提案する.そして このストリング・グラフ表現を使って 演算アルゴリズムの解析や証明が容易にできることを示す.まず Boothのアルゴリズムをストリング・グラフ表現することから試みる.次に 正準リコード・アルゴリズムのストリング・グラフ表現を得るために グラフを高階化する方法を示す.そして この高階グラフ表現を用いて冗長2進加算アルゴリズムのストリング・グラフ表現を導出するさらに 冗長2進加算アルゴリズムのストリング・グラフ表現が 除算アルゴリズムを導出するときの証明に利用できることをしめす.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top