사상재배치가 고장수목의 BDD 변환에 미치는 영향
Effect of Event Relocation on BDD Conversion from Fault Tree
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
이진결정도는 고장수목해석에서 기존의 부울대수를 이용한 방법의 잘 알려진 대체수단이다. 이진결정도의 규모는 변환과정에서 고장수목의 변수 순서에 영향을 받는다고 알려져 있다. 이진결정도의 규모가 작을수록 단절집합과 최소단절집합을 짧은 시간 내에 계산하기가 유리하기 때문에 작은 규모의 이진결정도가 선호된다. 고장로직의 변화 없이 게이트 아래의 사상들을 재배치하면 이진결정도의 구조와 규모를 변화시킬 수 있다. 주어진 고장수목에 대해 두 종류의 사상재배치를 정의하고 그 효과를 점검하였다. 좌사행 및 우사행 사상재비치를 정의하여 주어진 원래의 고장수목과 고장경로의 수를 비교하였다. 사상재배치가 이진결정도에 미치는 영향은 고장수목의 구조와 중복사상의 영향을 받는다. 어떤 고장수목의 경우는 좌사행 재배치일 경우가 이진결정도의 규모가 작고, 어떤 경우에는 우사행 재배치의 경우가 이진결정도의 규모가 작게 된다. 이런 계산 결과를 근거로 작은 이진결정도로 변환시키기 위해 고장수목의 사상재배치를 하는 것이 유리하다.
Abstract
BDD is a well-known alternative to the conventional Boolean logic method in fault tree analysis. It is known that the size of BDD is affected by variable orders of fault tree during BDD conversion procedure. As the smaller BDD size is better for the calculation of cut set and minimal cut set in short run time, the conversion for smaller BDD is preferred. The relocation of events under gates without any change of failure logic can affect the structure and size of BDD. For a given original fault tree, two kinds of event relocation are defined and the effect of event relocation is checked. The left and right skewed relocations are defined and for each case the numbers of failure path in BDD are compared with that of the original fault tree. The effect of event relocation on BDD size depends on the structure of fault tree and repeated events. In a certain fault tree, the left skewed relocation results in smaller BDD size and, in other cases, the right skewed relocation induces the smaller BDD size. Based on this result, it is better to change the fault tree structure before BDD conversion in order to get a smaller BDD size.
참고문헌 (11)
- R. Bryant, "Graph-based algorithms for Boolean function manipulation, IEEE Transaction On Computers", IEEE Transaction On Computers, C-35(8), pp.677~691 (1986)
- A. Rauzy, "New algorithms for fault tree analysis", Reliability Engineering System Safety, 40(3), pp.203~211 (1993)
- K. Reay, "Efficient Fault Tree Analysis Using Decision Diagrams", Ph.D, pp.2003
- N. Limnios, "Fault Trees", ISTE, 42~44 (2007)
- A Fault Tree Analysis Using Binary Decision Diagrams, "K. Reay", Loughborough University, 2~5 (2003)
- B. Bollig, "Improving the variable ordering of OBDDs is NP complete", IEEE Trans. Comput, 45, pp.993~1002 (1996)
- S. J. Friedman, "Finding the Optimal Variable Ordering for Binary Decision Diagrams", IEEE Trans. Comput., C-39(5), pp.710~713 (1990)
- F. Somenzi, "CUDD : CU Decision Diagram Package", University of Colorado, 4~39 (2013)
- 조병호, "BDD를 이용한 사고수목 정상사상확률 계산", 한국정보통신학회논문지, 20(3), pp.654~662 (2016), 한국정보통신학회[DOI]
- R. Tarjan, "Depth-First Search and Linear Graph Algorithms", SIAM J. Comput., 1(2), pp.146~160 (1972)
- L. Xing, "Binary Decision Diagrams and Extensions for System Reliability Analysis", pp.30~31 (2015), Scrivener Publishing Wiley