2024-03-29T15:51:08Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001238692023-11-17T02:17:36Z06504:08032:08041
素子制限のある論理回路を等価変換するための基本操作集合についてA complete set of basic operations to transform between equivalent switching circuits of NAND gatesjpnhttp://id.nii.ac.jp/1001/00124049/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=123869&item_no=1&attribute_id=1&file_no=1九州大学工学部九州大学工学部九州大学工学部日野, 健介岩間, 一雄澤田, 直論理回路の自動設計は近年その重要性を増々大きなものにしている.数多くの手法や考え方が提案されているが,その代表的なものは,まず何らかの方法で初期回路を設計し,段階的により性質の良い回路に変形していくというものである.また,最近注目を集めているアルゴリズムの効率を実験的に評価するためのテスト例題の生成では,逆に性質の良い回路(アルゴリズムが導き出すべき答)から悪い回路(アルゴリズムの入力とする)に変形できる必要がある.いずれの場合も,論理回路の等価変換(回路が実現する論理関数を変えることなく変形する)が鍵になる.我々はこれまでの研究で,論理回路としては,AND,OR,NOT素子が使える組合せ回路を対象として,任意の論理回路から任意の等価な論理回路へ変換するための完全な基本操作規則の集合を提案した.ここで,"変換"は1回の操作が多項式時間で実行できる"基本操作"の列で定義している.本稿では,使える素子をNANDのみに制限した組合せ回路を対象とする.NANDをANDとNOTの組合せとみれば,NANDに制限された回路を素子制限のない通常のAND,OR,NOTの回路の部分集合とみなせる.従って,上記の規則を適用すれば,任意のNAND回路f_1から任意のNAND回路f_2へ変換することは可能である.しかし,この場合,f_1からf_2への変換の過程で,NAND素子のみでない回路を経由しなくてはならない.本稿の立場は,常にNAND回路という制限を犯すことなく変換を進めていることに注意されたい.いわゆる変換公式についても,AND,OR,NOTの場合に比べて,あまり知られてないようにみえる.NANDという論理はゲートの重要な電子回路実現に本質的に関係しているため,一般にシステムの回路はNAND(あるいはNOR)ゲートを使用して設計されることが多く,実用的な面でも重要である.AN00349328全国大会講演論文集第46回ハードウェア1231241993-03-012015-01-20