JPH06511588A - ブール関数に関連する確率の自動決定方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 プール関数に関連する確率の自動決定方法技術分野 本発明は、プール関数に関連する確率を情報処理装置を使って自動的に決定する ための方法に関する。

従来技術 プール関数は様々な分野で使用されている。例を挙げると、電子回路の合成及び 最適化、システム障害解析などでプール関数を使用することができる。

したがって、例えば、障害解析では障害を引き起こし得る外部イベントの関数と しての障害の発生を、プール関数を使用して解析することができる。

より一般的に言えば、システム全体で、基準イベント、あるいは同時に発生する １つまたは複数のイベントの関数であって付随イベントとも呼ばれる動作の発生 などを解析することができる。したがって、各付随イベントはその関数の変数に なる。

以下の内容を理解できるように、プール関数についての基礎知識および定義、専 門用語を再確認しておく必要がある。

プール関数ｆが数式ｆ＝ｘｌｘ２°＋ｘｌ”　ｘ２ｘ３によって定義されるもの とする。この式は命題式と呼ばれ、ｘｌ、ｘ２．ｘ３は、ｆで表され、上述の式 によって与えられる基準イベントを発生させ得る原子イベントに対応する命題変 数である。

すなわち、システム障害の解析においては、原子イベントは障害の原因であり、 基準イベントは一定の方式で互いに組み合わさった原因に関連する個々の障害で ある。

上述の式における項ｒｘｌＪ　ｒｘ２Ｊ　ｒｘ３Ｊおよび「ｘ１′″Ｊ　ｒｘ２ ”Ｊ　ｒｘ３°」は、命題変数ｘ１、ｘ２、ｘ３に対応しているリテラルである 。リテラルとは、命題変数が関数の中でどのように作用するか、すなわち関連す るイベントの発生あるいは非発生が決定的なものかそれとも重要でないものかを 表すものである。ｘｌｘ２°およびｘｉ”　ｘ２ｘ３はリテラルの積である。従 って、積は変数および変数の否定の論理積である。

第１の積ｘｌｘ２”は、第３の変数ｘ３の有無がどうでもよいものか否かを示す 。

この式は、第１の原子イベントｘ１が発生する（ｘｌ＝１）それと同時に第２の イベントが発生しない（ｘ　２　＝　０）時、あるいは第１のイベントｘ１が発 生せずそれと同時に第２および第３のイベントｘ２およびｘ３が発生する時に、 基準イベントが発生する（ｆ＝１）か否かを示す。

実際には、このような式はブａトタイブに対するシミュレーションまたは解析か ら得られる。

システム（機能あるいは障害）解析の際、このような式は通常はこの関数の様々 な積を示すテーブルの形で示される。したがって、与えられた関数に関連するテ ーブルは、例えば積ｘ１ｘ２°およびｘ１°Ｘ２Ｘ３を含むことになる。

このようなテーブルはシステム障害解析の分野では障害ツリーと呼ばれている。

より一般的には、イベントツリーと呼ばれる。

このようなツリーは、システムの挙動に関する様々な解析や計算を実行するため に利用できる。具体的に言えば、基準イベントの発生の確率を各原子イベントの 確率の関数として計算することが考えられる。

この目的のため、テーブルは関数の発生に寄与する積だけでなく各原子イベント の発生の確率も与える。この確率は例えばシミュレーションや解析の際に決めら れている。

しかしながら、障害などの各基準イベントの確率の計算はこの解析あるいはシミ ュレーションより後で実行しなければならない。テーブルには極めて多数の積が 含まれ、あるいは多数の基準イベントを解析する必要があるので、この計算は自 動的に行われなければならない。

ところで、これまで既知の方法では滴定できるものは得られていない。すなわち 、これらの方法は近似式から出発し、したがって関数の前提を計算することが必 要である。

関数の前提はこの関数を含意する積であることに留意されたい。またＰがＰ′　 を「含意するＪ　（Ｐ＝＞Ｐ’　と書く）関係が真であれば、第１の積Ｐは第２ の積Ｐ′を「含む」。要するに、第１前提はそれを含む他の前提がないというよ うな前提なのである。

近似式を使用しても正確な結果を得ることはできない。反面、これらの前提を計 算して記憶しなければならないばかりか、最終結果を得るために後でこの前提あ るいは中間結果を組み合わせるために先の前提に基づく近似計算によって得られ た前提の数も計算して記憶しなければならないため、この近似計算には大きな計 算能力と記憶容量を有する処理装置が必要である。

したがって、本発明の目的は、大きな記憶容量がなくても基準イベントの正確な 確率を自動的に得られるような方法を得ることにある。

発明の開示 本発明によれば、それぞれ発生確率が予め分かっている互いに組み合わされた原 子イベントに依存する基準イベントの確率をデータ処理装置を使って自動的に決 定するための方法は、基準イベントを示す関数に対応する２値判定図を生成する ステップと、この図を反復して辿って、式Ｐ（ｆ）＝（１−ｐ（ｘｉ））、ｐ（ Ｌ）＋ｐ　（ｘｉ）、ｐ（Ｈ）（ここで、ｐ（ｘｌ）は予め分かっている図の根 イベントの確率、ｐ（Ｌ）およびｐ（ｆ（）はそれぞれ２値判定図を反復して辿 って得られるツリーの負の枝および正の枝の確率）の適用により基準イベントの 確率Ｐ　（ｆ）を得るステップとからなることを特徴とする。

周知のように、グラフすなわち２値判定図は、枝によって互いに接続された、い くつかのラベル（名札とも呼ばれる）からなる。各ラベルはその関数の決められ た変数を表し、そこから２つの枝が出ている。ラベルすなわち変数とそこから出 ている２つの枝とから構成される集合が、節点を構成し、これは時には頂点とも 呼ばれる。各校は、値「０」まだは「１」の末端葉に達する末端技、あるいは他 の節点のラベルに達する中間技である。ラベルから出る枝の一方は低層または負 の枝と呼ばれ、（上述の規約を使用して）関連する変数の値が「０」の時に起こ るものを示し、他方の枝は高層または正の枝と呼ばれ、変数の値が「１」の時に 起こるものを示す。実際、このツリーは根と呼ばれる固有の種変数（ラベル）か ら始まり、２本の枝がそこから出て、それに他の節点や葉が次々に接続される。

根から値が１の末端葉までツリーを辿る際、その関数の値が１になるリテラルの 組み合わせを決定する。すなわち、示された基準イベントを出現させる変数の組 み合わせ（積）を再構成する。その結果、根から値が１の各末端葉まで辿るごと に、基準イベントを出現させる変数の各組み合わせを決定することになる。

したがって、このような図すなわちグラフを使って、極めて完全かつ簡単に関数 の変数の組み合わせの集合を目に見えるようにすることができる。使用される記 憶域がテーブルに比べて小さく、２値判定グラフの形で表される関数を処理する ための時間が大幅に短縮される。

２値判定図の他の手法も考えられている。すなわち、ｒｌＥＥＥ　Ｔｒａｎｓａ ｃｔｉｏｎｓ　ｏｎ　ＣｏｍｐｕｔｅｒｓＪ、Ｃ−３５巻、第８号、１９８６年 ８月所載の、ＲａｎｄａｌＥ、　Ｂｒｙａｎｔの論文は、極めてコンパクトでは あるが関数内に現れる変数の様々な組み合わせを完璧に示すグラフを得るために 、変数、したがって節点をどのように並べることができるかを示している。

第１図に、３つの命題変数ｘ１、ｘ２、ｘ３を含むプール関数の２値判定図を示 す。

第１図に示す例では、ラベルｘ１によって識別される第１の変数はグラフの根で ある。この変数から、２本の枝すなわち左下の第１の枝と右下の第２の枝が出て いる。左側の枝は低層の枝と呼ばれ、右側の枝は高層の枝と呼ばれる。したがっ て、低層の枝と高層の枝からなる根の集合が、図の第１の節点を構成する。

低層および高層の枝はそれぞれラベルｘ２によって識別される第２の変数に達す る。この第２の変数も同様に低層および高層の枝からなり、他の節点を構成して いる。

枝のラベル、他の変数の低層の枝に関連する葉のラベル（すなわち変数）の集合 は、この変数のして表される以下で低層部と呼ぶものを構成し、変数の高層の枝 に関連する集合は、この変数のＨで表される高層部を構成している。

また、変数ｘ１の高層部は変数ｘ１を根とする節点から始まり、その節点の低層 部は葉ｏ１高層部は値が１の葉である。

根から始めて値「１」の葉の方向にツリーの枝を辿る際、−ｘ２が０であると同 時にｘｌも０である、あるいは；−ｘｌが０であると同時にｘ２は１であり、ｘ ３も１である時に関数が１になると決定できる。

以上のことは、根ｘ１に関連する低層の枝を辿ることから推論できる。

一方、根ｘ１に関連する高層部からは、ｘｌとｘ２の値が同時に１である時、関 数も１になると推論できる。

以上の結果、関数はｆ＝ｘｌ°ｘ２°＋ｘ１′″ｘ２ｘ３＋ｘ１ｘ２で表すこと ができる。

第１図に示したような２値判定図の構成は、既知の決められた算法に沿ったもの であり、本発明の目的ではない。これは上述のＲａｎｄａｌ　Ｅ、Ｂｒｙａｎｔ の論文に記述されている。

したがって、本発明は、図の高層（正）あるいは低層（負）の枝の各々が、それ 自体、高層および低層の枝を有する下位図を構成することを、極めて有用な形で 利用するものである。

要するに、各校の確率を決定するのに、この枝に直接接続された各校の確率を記 憶するだけでよい。したがって、反復して辿る際、下位の各校の確率を決定する ために値を２つ記憶するだけで十分であり、図の集合では最大４つの値を記憶す るだけでよい。

本発明の他の特徴および利点については、以下の第１図および第２図を参照した 説明によって明らかになろう。

図面の簡単な説明 第１図は、プール関数（ｆ）の２値判定図を示す概略図である。

第２図は、第１図に示す図の代表的な情報を格納するために処理装置のメモリを 編成する方法を示す図である。

発明を実施するための最良の形態 第１図およびこれを利用する方法は、プリアンプル部分においてすでに述べた通 りである。

既知のようにまた先に指摘したように、第１図に示す図は、図示しないテーブル すなわちイベントツリーから得られる。このテーブルから図をめる方法は、本発 明の目的ではないが、ラベルと枝の数をできるだけ少なくして図の大きさを最適 化できるような形で実行される。

要するに、この図によって示され、そこから展開される式がｆ＝ｘｌ”　ｘ２° ＋ｘｌ°Ｘ２Ｘ３＋ＸｌＸ２となる関数ｆは、従来から認められている規約を使 用してｆ＝ｘｌ°Ｌ＋ｘｌＨと書けることが確認できる。

本発明はこの確認から出発して、このような関数に関連する確率を正確に計算す るモードがＰ　（ｆ）＝　（ｐ　（ｘｉ））。

Ｐ　（Ｌ）　＋Ｐ　（ｘｉ）　、Ｐ　（Ｉ（）　（ここで、Ｐ　（ａ）はイベン トａに関連する確率）であることを有利な形で利用したものである。この式は、 最終的に、Ｐ　（ａ　ｆ）　−［（１−ｐ　（ｘｉ）　）、Ｐ　（Ｌ）＋Ｐ　（ ｘｉ）、Ｐ　（Ｈ）］　と書くことができる。

ところで、Ｌおよび■］は変数ｘ２および／またはｘ３が存在する下位図である 。したがって、各付随イベントに関連する確率ｐ　（ｘｉ）　、ｐ　（ｘ２）　 、ｐ　（ｘ３）が予め分かっていると、実際には図を反復して辿ることにより、 基準イベントの全体的確率を得ることができる。

第２図は、第１図に示す関数の２値判定図を構成する情報を格納するコンピュー タのメモリを編成する方法を示すが、これは限定的なものではない。

処理システムが関数の確率を計算できるのは、このメモリ内の情報による。

既知のように、メモリはワードで編成されており、各ワードはその絶対アドレス または相対ＡＤｎによって決定される。

２値判定図を表現するために、各ワードを例えば少なくとも５つのフィールド、 すなわち第１のフィールドＶＡＲ，第２のフィールドＩＮＤＬ、第３のフィール ドｒＮＤ、、第４のフィールドＧＥＳＴ、最後に第５のフィールドＰＲＯＢＡに 分けることができる。

ワードの第１のフィールドＭＡＲは、例えばＸ、など関数の命題変数の性質と範 囲とを示す情報を有する。

第２のフィールドＩ　ＮＤＬは、変数の低層の枝が節点または葉に達するか否か を示す。

第３のフィールドＩ　ＮＤ、ｌは、変数の高層の枝が節点または葉に達するか否 かを示す。

第４のフィールドＧＥＳＴは、例えば異なるアドレス間を辿る時にメモリを利用 するのに必要な管理パラメータを有する。

より詳細にいえば、第２および第３のフィールドは以下のようにして完成するこ とができる。すなわち、第２図に示すように、命題変数に関連する低層の枝が葉 に達するワードを含む場合には、第２のフィールドにこの葉の値である指示ｒＶ ａ　１０」または「Ｖａｌ　ＩＪが含まれる。

それに対して、命題変数に関連する低層の枝が節点に達する場合には、この第２ のフィールドＩ　Ｎ　Ｄ　Ｌはこの節点が書き込まれるワードのメモリアドレス の値を含む。

第３のフィールドＩＮＤ、は、第２のフィールドの場合と同様に、変数に関連す る高層の枝が節点あるいは葉に達するかどうか、その場合にはアドレスすなわち 値を有するかどうかを示す。

第４のフィールドＧＥＳＴは、すでに実行された辿り道を示ｔＶ理パラメータ、 あるいはこのメモリに対する利用管理に必要な全く別の種類の情報を有する。

最後に、第５のフィールドＰＲＯＢＡは、第１のフィールドＶＡＲに示される、 対応する変数ｘ、に関連する確率の予め分かっている値を有する。

また、アドレスＡＤ、にあるワードから始めて、メモリの集合を辿ることにより 、処理システムは関数が「１」になるように積を再構成することができる。した がって、判定図およびその様々な節点を再構成することができる。

各校または各下位技に関連する確率を決定することにより、システムは２値判定 図中にある節点を分解することができる。

規約により、以下の説明では、Ｎｄ　（ｘ、Ｌ、Ｈ）＝Ｙの形式が節点ｙを根に 分解する、すなわち、変数Ｘをその左側すなわち低層の枝りと右側すなわち高層 の枝Ｈとに分解する。

その関数ｆが２値判定図によって表されるイベントの確率の値は、以下に示すス テップを実施するｒＧＥＴ　ＰＲＯＢＡ（ｆ）」などの特定のアルゴリズムを使 用して決定することができる。

まず、関数の性質を決定するためにテストを実施する。

ｆ＝ｏならば、ＧＥＴＰＲＯＢＡ　（ｆ）＝０、ｆ＝１ならば、ＧＥＴＰＲＯＢ Ａ　（ｆ）＝１　。

ｆが０でも１でもなく、根Ｘｋと低層の枝りと高層の枝Ｈを有するｆが節点の形 で提示されることを意味する場合、この節点の分解を実行する。次に、関数ｒＧ 　Ｅ　Ｔ　Ｐ　ＲＯＢ　ＡＪは、以下の命令を実行する。

ＧＥＴＰＲＯＢＡ雷（１−ＧＥ置ＥＭＥＮＴＡＲＹＰＲＯＢＡ　（ｘｉ　））　 ・ＧＥＴＰＲＯＢＡ　（Ｌ）＋ＧＥ置ＥＭＥＮＴＡＲＹＰＲＯＢＡ　（：ｃ−） 　・ＧＥＴＰＲＯＢＡ　（Ｈ）ここで、ＧＥ置ＥＭＥＮＴＡＲＹＰＲＯＢＡ　（ ｘ、）は、変数（Ｘ、）に関連する確率値を第５のフィールドｒＰＲＯＢＡ」に 書き込み、これを計算に組み入れることをめる命令である。

ただし、命令ｒＧＥＴＰＲＯＢＡＪは、それ自体を実行する際に低層りおよび高 層Ｈの枝に関連する確率の計算を必要とする反復的なものであることが確認でき る。その結果、計算は常に、ツリーの末端の節点から、すなわちその低層および 高層の枝が値０および１を有する末端の葉に達する節点から始まり、逆もまたし かりである。

一方、従来技術とは対照的に、ここで使用するアルゴリズムでは計算の際に簡素 化も近似も必要でないため、このアルゴリズムを使用すれば決められたイベント に関連する確率の値を正確にめることができることが確認できる。

ただし、メモリ容量は最小限ですむ。反復ごとにその内容が変更され、ラベルに 関連する確率を計算する際に、このラベルに接続された低層および高層の各校の 関数ｒＧ　Ｅ　Ｔ　Ｐ　ＲＯＢ　ＡＪを使用して得られた確率を格納する、バッ ファメモリを処理装置のメモリ内に設けるだけで十分である。

Claims (8)

【特許請求の範囲】
1. １．それぞれ予め分かっている発生の確率を有する互いに組み合わされた原子イ ベントに依存する基準イベントの確率をデータ処理装置を使って自動的に決定す るための方法であって、基準イベントを表すプール関数に対応する２値判定図（ ｆ）を作成するステップと、式Ｐ（ｆ）＝（１−Ｐ（ｘ１））・Ｐ（Ｌ）＋ｐ（ ｘ１）・ｐ（Ｈ）（ここで、ｐ（ｘ１）は予め分かっている図の根イベントの確 率、ｐ（Ｌ）およびｐ（Ｈ）はそれぞれ２値判定図を回帰的に辿って得られるツ リーの負の枝および正の枝の確率）の適用によって基準イベントの確率Ｐ（ｆ） を得るためにこの図を回帰的に辿るステップとからなることを特徴とする方法。
2. ２．イベント（ｆ）の確率Ｐ（ｆ）が、イベント（ｆ）が有限値（０または１） を有するか、あるいは節点Ｎｄ（ｘｋ，Ｌ，Ｈ）を構成するか（ここで、ｘｋは 原子イベントを表す根ラベルすなわち根変数、ＬおよびＨはそれぞれこのラベル に関連する低層および高層の枝）を判断するテスト段階を含む、関数（ＧＥＴ　 ＰＲＯＢＡ（ｆ））の実施によって得られることを特徴とする請求の範囲第１項 記載の方法。
3. ３．関数（ＧＥＴＰＲＯＢＡ（ｆ））が、ｆの値が１であると決定された場合に 、この関数によって返される関連する確率Ｐ（ｆ）の値も１になるようなもので あることを特徴とする請求の範囲第２項記載の方法。
4. ４．関数（ＧＥＴＰＲＯＢＡ（ｆ））が、ｆの値が０であると決定された場合に 、この関数によって返される関連する確率Ｐ（ｆ）の値も０になるようなもので あることを特徴とする請求の範囲第２項記載の方法。
5. ５．イベント（ｆ）が節点を構成すると決定された場合に、関数（ＧＥＴＰＲＯ ＢＡ（ｆ））が、この節点をラベル（ｘｋ）と低層の枝（Ｌ）と高層の技（Ｈ） に分解し、結果としてＰ（ｆ）＝（１−ＧＥＴＥＬＥＭＥＮＴＡＲＹＰＲＯＢＡ （ｘｋ）×ＧＥＴＰＲＯＢＡ（Ｌ）＋ＧＥＴＥＬＥＭＥＮＴＡＲＹＰＲＯＢＡ（ ｘｋ）＊ＧＥＴＰＲＯＢＡ（Ｈ）（ここで、ＧＥＴＥＬＥＭＥＮＴＡＲＹＰＲＯ ＢＡ（ｘｋ）は、ラベル８ｋの予め分かっている関連する確率の値Ｐ（ｘｋ）を 再発見できるようにする関数）を戻すことを特徴とする請求の範囲第２項記載の 方法。
6. ６．原子イベント（ｘｋ）の確率Ｐ（ｘｋ）が、２値判定図を作成するために使 用されたイベントツリーから得られることを特徴とする請求の範囲第１項から第 ５項のいずれか一項に記載の方法。
7. ７．２値判定図を作成する際に、各原子イベントの確率（Ｐ（ｘｋ））が、この 図に関してイベントツリーから出発して、記憶されることを特徴とする請求の範 囲第６項記載の方法。
8. ８．請求の範囲第１項から第７項のいずれか一項に記載の方法のシステム障害解 析における確率計算への適用。