演算アルゴリズムのストリング・グラフ表現
スポンサーリンク
概要
- 論文の詳細を見る
コンピュータ・グラフィックス分野が急激に発展してきたので,32ないし64ビットの浮動小数点演算がごく普通に要求されるようになってきた.このように処理桁数が増加してくると,桁上げ伝播による遅延が問題になり,桁上げ伝播のない演算方式が注目されている.従来,桁上げ保存加算器が主として桁上げ伝播のない演藻方式に利用されていた.しかし,最近,{-1,0,+1}で表現する冗長2進加算器を利用する方が,相性がよく,すぐれた規則性をもち,加減乗除,開平などの高速演算アルゴリズムを導出できることがわかってきた.本論文では,これらの演算アルゴリズムをストリング・グラフと呼ぶ表現によって視覚化または形式化することを提案する.そして,このストリング・グラフ表現を使って,演算アルゴリズムの解析や証明が容易にできることを示す.まず,Boothのアルゴリズムをストリング・グラフ表現することから試みる.次に,正準リコード・アルゴリズムのストリング・グラフ表現を得るために,グラフを高階化する方法を示す.そして,この高階グラフ表現を用いて冗長2進加算アルゴリズムのストリング・グラフ表現を導出するさらに,冗長2進加算アルゴリズムのストリング・グラフ表現が,除算アルゴリズムを導出するときの証明に利用できることをしめす.
- 一般社団法人情報処理学会の論文
- 1990-08-15
著者
関連論文
- ブロックソート圧縮アルゴリズムを用いたプログラム・コード圧縮
- ブロックソート圧縮データの検索法
- 2ブロック分割対を用いた非同期式順序回路の合成
- 桁上げ保存型対符号付き数型加算回路 : 乗算器を中心に
- 桁上げ保存型対符号付き数型加算回路 : 基数2と4の除算器を中心に
- 高速離散コサイン変換ディジタル回路
- 効率的な基数2の除算器
- 高速設計基準による順序回路の最適状態割当て法
- 演算アルゴリズムのストリング・グラフ表現
- 冗長2進数表現による繰返し乗算方式
- 順序回路の論理段数最小・最適状態割当て法
- 演算アルゴリズムのストリング・グラフ表現