漸化式を用いたハードウェア・アルゴリズムの設計について

若林 真一  菊野 亨  吉田 典可  

誌名
電子情報通信学会論文誌 D   Vol.J67-D   No.8   pp.861-868
発行日: 1984/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(601.6KB)>>
論文を購入




あらまし: 
VLSI技術の進歩に伴い,各種のアルゴリズムをVLSIのチップ上で直接ハードウェアとして実現しようとするハードウェア・アルゴリズムが注目を集めている.しかし,ハードウェア・アルゴリズムの体系化や,その設計方法については未だ十分な成果は見られない.本稿では漸化式を用いた新たなハードウェア・アルゴリズムの設計方法の提案を試みる.先ず,2変数のある漸化式で定義される問題のクラスCを導入する.この問題のクラスにはストリング・マッチング問題など実用上重要な問題が多く含まれる.問題のサイズをmとするとき,クラスCに属する任意の問題に対し,それをOm)の手数で解くハードウェア・アルゴリズムが常に構成できることを示す.次に,漸化式にある制限を加えることにより,問題のクラスCのサブクラスC1を定義し,サブクラスC1に対してはO(logmm/logm)の手数のハードウェア・アルゴリズムが構成できることを示す.最後に,クラスCの拡張について議論し,クラスCより広い漸化式の1つのクラスに対しても,クラスCに対するアルゴリズムが,若干の変更を行うことにより適用可能であることを示す.