JPH06230930A - 同期式順序回路の状態割当て装置 - Google Patents

Abstract

(57)【要約】 【目的】 所要面積がより小さい同期式順序回路を提供
する。 【構成】 与えられた状態遷移表14に含まれる状態の数
から状態コード長を求める状態コード長算出手段11と、
与えられた状態遷移表14から評価関数を計算する評価関
数算出手段12と、状態コード長算出手段11及び評価関数
算出手段12に接続されており状態コード長算出手段11で
算出された状態コード長から評価関数算出手段12で算出
された評価関数の値に基づいて所定のコードを決定する
コード決定手段13とを備えており、評価関数全体の変数
の数が最も削減されるように所定のコ−ドを割当てる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、同期式順序回路に関
し、特に、同期式順序回路の状態割当て装置に関する。

【０００２】

【従来の技術】従来の同期式順序回路の一構成例を図３
に示す。

【０００３】図３の従来の同期式順序回路30は、出力回
路31、次状態回路32、次状態回路32に接続された状態信
号記憶部（以下、レジスタと称する）33によって構成さ
れている。

【０００４】次に、図３の従来の同期式順序回路の動作
を説明する。

【０００５】レジスタ33は、コード化（２値信号の値の
組）された状態を記憶する。

【０００６】出力回路31は、ある時刻でそのときの外部
からの入力信号とレジスタ33に記憶されている状態コー
ドに基いて出力を計算して外部に出力信号を出力する。

【０００７】次状態回路32は、次状態コードを計算す
る。

【０００８】クロック信号が加えられたとき、次状態コ
ードがレジスタ33に記憶されて新たな出力及び新たな次
状態が計算される。

【０００９】上述したように同期式順序回路は、クロッ
ク信号に同期して状態を変化させる（状態を遷移する）
と共に、そのときの状態と外部からの入力信号に基いて
外部に出力信号を出力する。

【００１０】同期式順序回路を設計する過程において、
外部からの入力信号、記号表現された状態、記号表現さ
れた次状態、外部への出力信号の関係（状態遷移表）
が、同期式順序機械の仕様として与えられる。そこで、
状態コードの長さを決め、また、各記号表現された状態
をコード化しなければならない。

【００１１】このとき、コードの長さは、 log₂ （状態
数）以上の整数であれば順序回路を実現可能であるが、
可能な限り小さい値にした方がレジスタの回路の面積を
小さく実現できる。

【００１２】また、状態コードは、任意の２状態を区別
することができれば、どのようにコード割当てを行って
も順序回路を実現可能であるが、何らかの工夫を行うこ
とによって、次状態回路や出力回路の面積を小さく実現
できる場合がある。

【００１３】更に、次状態回路や出力回路の面積を小さ
するためのコード割当て方法が、情報処理ハンドブック
（ (社) 情報処理学会編、1989年）、特公平3-171373号
公報、及び特公平3-216763号公報、及び特願平4-126505
号に報告されている。

【００１４】

【表１】

【００１５】表１は、状態を記号表現した状態遷移表の
一例を示す。

【００１６】

【表２】

【００１７】表２は、表１の状態遷移表の記号表現され
た状態に、上述した図３の従来の同期式順序回路を用い
て状態割当てを行なって得られた真理値表の一例を示
す。

【００１８】また、図４は、表２の真理値表を論理合成
して得られる従来の次状態回路及び出力回路の一構成例
を示す。

【００１９】

【発明が解決しようとする課題】しかしながら、上記情
報処理ハンドブック及び特公平3-171373号公報に記載さ
れている方法では、次状態回路や出力回路の論理（次状
態関数、出力関数）を表す論理式から括りだして減らせ
る変数の数のみに着目しており、論理式に含まれる変数
の数自体は考慮されていないので、論理式に表れる変数
の総数を十分削減できず、その結果、次状態回路や出力
回路の面積を十分削減できないという問題があった。

【００２０】また、上記特公平3-216763号公報に記載さ
れている方法では、次状態回路や出力回路の面積を削減
できる半面、状態コードの長さを状態数と同じにしなけ
ればならないという制約があり、そのためレジスタの回
路の面積が大きくなってしまい、順序回路全体としての
面積を必ずしも削減できない場合があるという問題があ
った。

【００２１】更に、上記特願平4-126505号に記載されて
いる同期順序回路の状態割当て装置では、次状態回路の
面積削減に大きな効果はあるが、出力回路の面積削減に
ついての配慮がないので、次状態回路と出力回路を併せ
た順序回路全体としての面積をより効率良く削減できな
い場合があるという問題があった。

【００２２】本発明の目的は、上述した従来の同期式順
序回路における問題点に鑑み、従来の状態割当ての手法
で割当てるより、次状態回路と出力回路を併せた面積が
より小さい同期式順序回路の状態割り当て装置を提供す
ることにある。

【００２３】

【課題を解決するための手段】本発明は、与えられた状
態遷移表に含まれる状態の数から状態コード長を求める
手段と、与えられた状態遷移表から評価関数を計算する
手段と、状態コード長算出手段及び評価関数算出手段に
接続されており状態コード長算出手段で算出された状態
コード長から評価関数算出手段で算出された評価関数の
値に基づいて所定のコードを決定する手段とを備えてお
り、評価関数全体の変数の数が最も削減されるように所
定のコ−ドを割当てる同期式順序回路の状態割当て装置
によって達成される。

【００２４】

【作用】本発明の同期式順序回路の状態割当て装置で
は、与えられた状態遷移表に含まれる状態の数から状態
コード長を求め、与えられた状態遷移表から評価関数を
計算し、算出された状態コード長から算出された評価関
数の値に基づいて所定のコードを決定し、評価関数全体
の変数の数が最も削減されるように所定のコ−ドを割当
てる。

【００２５】

【実施例】以下、図面を参照して、本発明の同期式順序
回路の状態割当て装置の実施例を説明する。

【００２６】図１は、本発明の同期式順序回路の状態割
当て装置（以下、状態割当て装置と称する）の一実施例
の構成を示すブロック図である。

【００２７】図に示すように、本実施例の状態割当て装
置10は、与えられた状態遷移表に含まれる状態の数から
状態コード長を求める状態コード長算出手段11、与えら
れた状態遷移表から評価関数を計算する評価関数算出手
段12、状態コード長算出手段11及び評価関数算出手段12
に接続されており状態コード長算出手段11で算出された
状態コード長から評価関数算出手段12で算出された評価
関数の値に基づいて所定のコードを決定するコード決定
手段13、及び状態遷移表14によって構成されている。

【００２８】次に、図１の状態割当て装置の動作、特に
同期式順序回路での状態割当ての手順を説明する。

【００２９】まず、各状態へ遷移の起る条件を、状態変
数と入力変数からなる論理式で表す。ここでは仮に、状
態ｉへ遷移の起る条件式を式ｉ、状態ｊへ遷移の起る条
件式を式ｊとおく。

【００３０】次に、以下の２つの評価関数を立て、この
値を各ｉ、ｊについて求める。

【００３１】評価関数Ｆ（ｉ，ｊ）＝（ある状態へ遷移
の起る条件式の変数の数の平均値）×２−（（式ｉの変
数の数）＋（式ｊの変数の数）−（式ｉと式ｊから括り
だして減らせる変数の数）） 評価関数Ｇ（ｉ，ｊ）＝出力関数全体で状態ｉと状態ｊ
のコードの１ビット分が一致した場合に括りだして減ら
せる状態変数の数 そして、 評価関数Ｈ（ｉ，ｊ）＝Ｆ（ｉ，ｊ）＋Ｇ（ｉ，ｊ） とおいた上で、評価関数Ｈ（ｉ，ｊ）と評価関数Ｇ
（ｉ，ｊ）の値を比較し、評価関数Ｈ（ｉ，ｊ）がより
大きい場合に状態ｉと状態ｊのコードの同じ桁に１が、
評価関数Ｇ（ｉ，ｊ）がより大きい場合に状態ｉと状態
ｊのコードの同じ桁に０が割り当てられる様に状態コー
ドを割り当てる。

【００３２】次状態関数は、状態コードの各々のビット
に対応している。状態コードのｋビット目に対応する次
状態関数の論理式は、状態コードのｋビット目が１に割
当てられている状態へ遷移の起る条件式の論理和であ
る。

【００３３】例えば、状態ｉの状態コードのｋビット目
が１に割当てられていれば、状態コードのｋビット目に
対応する次状態関数の論理式に、状態ｉへ遷移の起る条
件式が含まれる。同様に、状態ｉと状態ｊの状態コード
のｋビット目が共に１に割当てられていれば、状態コー
ドのｋビット目に対応する次状態関数の論理式に、状態
ｉへ遷移の起る条件式と状態ｊへ遷移の起る条件式が共
に含まれる。

【００３４】評価関数Ｆ（ｉ，ｊ）は、状態ｉと状態ｊ
のコードの同じ１つのビットに１を割り当てた時に次状
態関数中で何個の変数が減ることが期待できるかを表し
ている。

【００３５】一方、評価関数Ｇ（ｉ，ｊ）は、状態ｉと
状態ｊのコードの同じ１つのビットに同じ値（１どうし
でも０どうしでも良い）を割り当てた時に、出力関数中
で何個の変数が減ることが期待できるかを表している。

【００３６】そこで、評価関数Ｈ（ｉ，ｊ）＝評価関数
Ｆ（ｉ，ｊ）＋評価関数Ｇ（ｉ，ｊ）とおき、次状態関
数と出力関数を併せた関数全体で考えると、評価関数Ｈ
（ｉ，ｊ）は状態ｉと状態ｊのコードの同じ１つのビッ
トに１を割り当てたとき、評価関数Ｇ（ｉ，ｊ）は状態
ｉと状態ｊのコードの同じ１つのビットに０を割り当て
たときに、次状態関数及び出力関数中で何個の変数が減
ることが期待できるかを表していると言える。

【００３７】従って、評価関数Ｈ（ｉ，ｊ）、評価関数
Ｇ（ｉ，ｊ）を併せて大小関係を見て、評価関数Ｈ
（ｉ，ｊ）がより大きい場合に状態ｉと状態ｊのコード
のより多くの同じ桁に１を、評価関数Ｇ（ｉ，ｊ）がよ
り大きい場合に状態ｉと状態ｊのコードのより多くの同
じ桁に０を割当てることで、次状態関数と出力関数を併
せた論理式全体に含まれる変数の数を減らせる。その結
果、論理式を論理回路で置き換えた際にも、より面積の
小さな回路として実現できる。

【００３８】同期式順序回路での状態割当て手順は、 (1) 与えられた状態遷移表に含まれる状態の数から状態
コード長を求める。

【００３９】（ log₂ （状態数）以上の最小の整数を状
態コード長とする） (2) 与えられた状態遷移表から評価関数を計算する。

【００４０】(3) 評価関数の値に基づいてコードを決定
する。

【００４１】の各処理によって構成されている。

【００４２】表１は、状態を記号表現した状態遷移表の
一例を示す。

【００４３】まず、上記(1) の処理について述べる。

【００４４】表１では、状態数が４であることから状態
コード長は２として求まる。

【００４５】続いて、上記(2) の処理を説明する。

【００４６】各状態へ遷移の起る条件を、状態変数と入
力変数からなる論理式で表す。

【００４７】状態数が２の冪乗個でない場合、仮の状態
を追加して状態数が２の冪乗個あるものと見做す（仮の
状態へ遷移の起る条件式に含まれる変数の数は、０であ
る）。 次に、表１の現状態が状態１、状態２、状態
３、状態４であることをＳ１、Ｓ２、Ｓ３、Ｓ４でそれ
ぞれ表すと状態２へ遷移の起る条件は、

【００４８】

【数１】

【００４９】状態３へ遷移の起る条件は、

【００５０】

【数２】

【００５１】また、出力関数（本実施例では１つのみ）
は、

【００５２】

【数３】

【００５３】という論理式で表される（ここで、式中、
・は論理積、＋は論理和をそれぞれ表す演算子であ
る）。

【００５４】次に、評価関数Ｆ（ｉ，ｊ）を求める。

【００５５】式に含まれる“現状態が某であること”
は、状態コード長分の変数で構成されていると見做す。

【００５６】式の立て方から評価関数Ｆ（ｉ，ｊ）＝評
価関数Ｆ（ｊ，ｉ）であるから、ここでは、評価関数Ｆ
（１，２）、評価関数Ｆ（１，３）、評価関数Ｆ（１，
４）、評価関数Ｆ（２，３）、評価関数Ｆ（２，４）、
評価関数Ｆ（３，４）、の６つを計算する必要がある。

【００５７】例えば、評価関数Ｆ（２，３）を求めてみ
る。

【００５８】Ｓ１、Ｓ２等は、状態コード長分、即ち２
つの変数から構成されていると見做せるから、状態２へ
遷移の起る条件式の変数の数は１２、状態３へ遷移の起
る条件式の変数の数は４、加えて状態１へ遷移の起る条
件式の変数の数は３６、状態４へ遷移の起る条件式の変
数の数は１２だから、ある状態へへ遷移の起る条件式の
変数の数の平均値は１６と求まる。

【００５９】また、両式について、前式の積項（３個）
と後式の積項（１個）を比較すると、Ｘは２ヶ所に存在
するので変数１個分減らせる、また、

【００６０】

【数４】

【００６１】は、２ヶ所に存在するので、変数を１個分
減らすことができ、また、Ｙは２ヶ所に存在するので、
変数を１個分減らすことができる。更に、

【００６２】

【数５】

【００６３】は、２ヶ所に存在するので、変数を１個分
減らすことができる。

【００６４】また、Ｓ１は２ヶ所に存在するので、変数
を２個分減らすことができ、Ｓ２は２ヶ所に存在するの
で、変数を２個分減らすことできるので、両式から括り
だして減らせる変数の数は８として求まる。

【００６５】結局、評価関数Ｆ（２，３）の値は、１６
×−（１２＋４−８）＝２４と求まる。また、他の評価
関数Ｆも全て計算すると、評価関数Ｆ（１，２）＝２
０、評価関数Ｆ（１，３）＝２０、評価関数Ｆ（１，
４）＝２０、評価関数Ｆ（２，３）＝２４、評価関数Ｆ
（２，４）＝２０、評価関数Ｆ（３，４）＝２２、と求
まる。

【００６６】次に、評価関数Ｇ（ｉ，ｊ）を求める。こ
れも評価関数Ｆ（ｉ，ｊ）と同様に６つを計算する必要
がある。

【００６７】表１では、出力関数にはＳ３とＳ４が１つ
ずつ含まれるだけだから、状態３と状態４のコ−ドの１
ビット分が一致した場合には、変数１つ分が減らせるの
で、評価関数Ｇ（３，４）のみ値１を取り、他の評価関
数Ｇは値０である。

【００６８】上記(3) 評価関数の値に基づいてコードを
決定する処理を説明する。

【００６９】異なる状態に同じコ−ドを割り当てないよ
うに、状態コ−ドの各ビット毎に、既決定のコードが同
じ状態に対して、半数に１を、残りの半数に０を割り当
てるという条件のもとに、評価関数Ｇ及び評価関数Ｈの
できるだけ大きい順にコ−ドを決定して行く。

【００７０】表１では、結局 評価関数Ｆ（１，２）＝２０、評価関数Ｆ（１，３）＝
２０、評価関数Ｆ（１，４）＝２０、評価関数Ｆ（２，
３）＝２４、評価関数Ｆ（２，４）＝２０、評価関数Ｆ
（３，４）＝２２、評価関数Ｇ（１，２）＝０、評価関
数Ｇ（１，３）＝０、評価関数Ｇ（１，４）＝０、評価
関数Ｇ（２，３）＝０、評価関数Ｇ（２，４）＝０、評
価関数Ｇ（３，４）＝１、評価関数Ｈ（１，４）＝２
０、評価関数Ｈ（１，３）＝２０、評価関数Ｈ（１，
４）＝２０、評価関数Ｈ（２，３）＝２４、評価関数Ｈ
（２，４）＝２０、評価関数Ｈ（３，４）＝２３、と求
まる。

【００７１】コードの１ビット目を決めるには、評価関
数Ｇ、評価関数Ｈの中で、評価関数Ｈ（２，３）の評価
値が最大であることから、状態２と状態３の１ビット目
に１が割当てられ、残りの状態１と状態４の１ビット目
に０がそれぞれ割当てられる。

【００７２】コードの２ビット目を決めるには、条件か
ら、状態２と状態３では一方に１、他方に０、状態１と
状態４でも一方に１、他方に０がそれぞれ割り当てられ
なければならない。その上で評価関数Ｇ及び評価関数Ｈ
を見ると、評価関数Ｈ（２，３）の評価値に次いで、評
価関数Ｈ（３，４）の評価値が大きいことから、状態３
と状態４の２ビット目に１が割当てられ、残りの状態１
と状態２の２ビット目に０が割当てられる。このよう
に、状態１にコード00が、状態２にコード10が、状態３
にコード11が、状態４にコード01が割り当てられる。

【００７３】

【表３】

【００７４】表３は、表１の状態遷移表の記号表現され
た状態に、上述した手順に基づいて状態割当てを行って
得られる真理値表を示す。

【００７５】図２は、表３の真理値表を論理合成して得
られる次状態回路及び出力回路の一構成例を示す。

【００７６】図２の次状態回路16は、否定（ＮＯＴ）論
理回路素子17〜20、論理和（ＯＲ）回路素子21〜23、論
理積（ＡＮＤ）回路素子24〜27によって構成されてい
る。

【００７７】また、図２の出力回路は、論理積（ＡＮ
Ｄ）回路素子28によって構成されている。

【００７８】次に、図２の次状態回路16の動作を説明す
る。

【００７９】ＡＮＤ回路素子24は、ＮＯＴ論理回路素子
17を介して出力される入力Ｙの否定（ＮＯＴ Ｙ）、Ｎ
ＯＴ論理回路素子18を介して出力される現状態Ｓ２の否
定（ＮＯＴ Ｓ２）、及び現状態Ｓ１をそれぞれ入力し
て論理積を算出する。

【００８０】ＯＲ回路素子21は、入力Ｓ１及びＳ２を入
力して論理和を算出する。

【００８１】ＡＮＤ回路素子25は、入力Ｙ、及びＮＯＴ
論理回路素子20を介してＯＲ回路素子21から出力された
論理和の否定を入力して論理積を算出する。

【００８２】ＡＮＤ回路素子26は、ＯＲ回路素子21から
出力された論理和、ＮＯＴ論理回路素子17を介して出力
される入力Ｙの否定（ＮＯＴ Ｙ）、及び入力Ｘの論理
積を算出する。

【００８３】ＡＮＤ回路素子27は、現状態Ｓ１、現状態
Ｓ２、入力Ｙ、及びＮＯＴ論理回路素子19を介して出力
される入力Ｘの否定（ＮＯＴ Ｘ）の論理積を算出す
る。

【００８４】ＯＲ回路素子22は、ＡＮＤ回路素子24から
の出力とＡＮＤ回路素子25からの出力を入力して論理和
を実行し、次状態Ｓ１′を出力する。

【００８５】ＯＲ回路素子23は、ＡＮＤ回路素子26から
の出力とＡＮＤ回路素子27からの出力を入力して論理和
を実行し、次状態Ｓ２′を出力する。

【００８６】図２の出力回路を構成しているＡＮＤ回路
素子28の動作を説明する。

【００８７】ＡＮＤ回路素子28は、入力Ｘ、入力Ｙ、及
び現状態Ｓ２を入力して、それらの論理積を算出して、
論理積の結果Ｚを出力する。

【００８８】上述したように、次状態関数は、状態コー
ドの各々のビットに対応している。状態コードのｋビッ
ト目に対応する次状態関数の論理式は、状態コードのｋ
ビット目が１に割当てられている状態へ遷移の起る条件
式の論理和である。

【００８９】例えば、条件ｉの状態コードのｋビット目
が１に割当てられていれば、状態コードのｋビット目に
対応する次状態関数の論理式に、状態ｉへ遷移の起る条
件式が含まれる。同様に、状態ｉと状態ｊの状態コード
のｋビット目が共に１に割当てられていれば、状態コー
ドのｋビット目に対応する次状態関数の論理式に、状態
ｉへ遷移の起る条件式と状態ｊへ遷移の起る条件式が共
に含まれる。

【００９０】さて、本発明の評価関数は、ある状態へ遷
移の起る条件式のうち、任意の２式の論理和をとったと
きに、式中に含まれる変数の数を表している。

【００９１】この評価関数がより小さい状態の対につい
て、より多く、状態コードの同じ桁に１を割当てること
で、次状態関数の論理式に含まれる変数の数を減らせ
る。

【００９２】従って、本発明の同期式順序回路の状態割
当て装置は、出力関数に含まれる状態変数から括りだせ
る変数の個数から、コード割当てに伴う出力関数の変数
の個数の増減を計って、次状態関数と出力関数を併せた
関数全体の変数の個数が最も削減されるように状態コー
ドを割当てる。

【００９３】その結果、次状態回路をより面積の小さな
回路で実現でき、順序回路全体としてもより面積の小さ
な回路で実現できる。

【００９４】

【発明の効果】本発明の同期式順序回路の状態割当て装
置は、与えられた状態遷移表に含まれる状態の数から状
態コード長を求める手段と、与えられた状態遷移表から
評価関数を計算する手段と、状態コード長算出手段及び
評価関数算出手段に接続されており状態コード長算出手
段で算出された状態コード長から評価関数算出手段で算
出された評価関数の値に基づいて所定のコードを決定す
る手段とを備えており、評価関数全体の変数の数が最も
削減されるように所定のコ−ドを割当てるので、順序回
路の所要面積を削減でき、同期式順序回路の設計工程の
省力化、設計品質の向上が得られる。

【図面の簡単な説明】

【図１】本発明の同期式順序回路の状態割当て装置の一
実施例の構成を示すブロック図である。

【図２】表３の真理値表を論理合成して得られる次状態
回路及び出力回路の一構成例を示すブロック図である。

【図３】従来の同期式順序回路の一構成例を示すブロッ
ク図である。

【図４】表２の真理値表を論理合成して得られる従来の
次状態回路及び出力回路の一構成例を示すブロック図で
ある。

【符号の説明】

10 同期式順序回路の状態割当て装置 11 状態コ−ド長算出手段 12 評価関数算出手段 13 コ−ド決定手段 14 状態遷移表

Claims (1)

【特許請求の範囲】
1. 【請求項１】 与えられた状態遷移表に含まれる状態の
   数から状態コード長を求める手段と、該与えられた状態
   遷移表から評価関数を計算する手段と、該状態コード長
   算出手段及び該評価関数算出手段に接続されており該状
   態コード長算出手段で算出された該状態コード長から該
   評価関数算出手段で算出された該評価関数の値に基づい
   て所定のコードを決定する手段とを備えており、該評価
   関数全体の変数の数が最も削減されるように該所定のコ
   −ドを割当てることを特徴とする同期式順序回路の状態
   割当て装置。