본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

OPKFDD 최소화를 위한 노드의 확장형 결정
Decision of the Node Decomposition Type for the Minimization of OPKFDDs

정미경   (전남대학교 대학원 전산통계학과UU0001112  ); 황민   (전남대학교 대학원 전산통계학과UU0001112  ); 이귀상   (전남대학교 정보통신연구소 전산학과UU0001112  ); 김영철   (전남대학교 전자공학과UU0001112  );
  • 초록

    OPKFDD(Ordered Pseudo-Kronecker Functional Decision Diagram)는 각 노드에서 다양한 확장방법(decomposition)을 취할 수 있는 Ordered-DD(Decision Diagram)의 한 종류로서 각 노드마다 Shannon, positive Davio, 그리고 negative Davio 확장중의 하나를 사용하도록 하며 다른 종류의 DD와 비교해서 작은 수의 노드로 함수를 표현할 수 있다. 그러나 각 노드마다 각기 다른 확장 방법을 선택할 수 있는 특징 때문에 입력 노드에 대한 확장 방법의 결정에 의해서 OPKFDD의 크기가 좌우되며 최소의 노드 수를 갖는 OPKFDD의 구성은 매우 어려운 문제로 알려져 있다. 본 논문에서는 DD 크기의 기준을 노드 수로 하여 기존의 OBDD(Ordered Binary Decision Diagram) 자료구조에서 각 노드의 확장방법을 결정하는 직관적(heuristic)인 방법을 제시하고, 주어진 입력변수 순서에 대해서 각 노드의 확장 방법을 결정하는 알고리즘을 제안하고 실험 결과를 제시한다.


    OPKFDD (Ordered Pseudo-Kronecker Functional Decision Diagram) is one of ordered-DDs (Decision Diagrams) in which each node can take one of three decomposition types : Shannon, positive Davio and negative Davio decompositions. Whereas OBDD (Ordered Binary Decision Diagram) uses only the Shannon decomposition in each node, OPKFDD uses the three decompositions and generates representations of functions with smaller number of nodes than other DDs. However, this leads to the extreme difficulty of getting an optimal solution for the minimization of OPKFDD. Since an appropriate decomposition type has to be chosen for each node, the size of the representation is decided by the selection of the decomposition type. We propose a heuristic method to generate OPKFDD efficiently from the OBDD of the given function and the algorithm of the decision of decomposition type for a given variable ordering. Experimental results demonstrate the performance of the algorithm.


  • 주제어

    확장방법.  

  • 참고문헌 (15)

    1. P. Lindgren, R. Drechsler, B. Becker, 'Look-up Table FPGA Synthesis from Minimized Multi-Valued Pseudo Kronecker Expressions,' IEEE International Symposium on Multiple-Valued Logic, pp.95-100, 1998 
    2. T. Sasao, AND-EXOR Expression and Their Optimization, Kluwer Academic Publisher, 1993 
    3. R. Rudell, 'Dynamic Variable Ordering for Ordered Binary Decision Diagrams,' In IEEE International Conference on Computer-Aided Design, pp.42-47, 1993 
    4. R. Drechsler, personal communication, 1999 
    5. T. Sasao and J. T. Butler, 'A Design Method for Look-up Table Type FPGA by Pseudo-Kronecker Expansion,' In Proceedings International Symposium on Multipe-Valued logic, pp.97-106, 1994 
    6. M. A. Perkowski, M. Chrzanowska-Jeske, A. Sarabi and I. Schafer, 'Multi-Level Logic Synthesis Based on Kronecker and Boolean Ternary Decision Diagrams for Incompletely Specified Functions,' In VLSI Design, 3(3), pp.301-313, 1995 
    7. R. Drechsler, 'Pseudo Kronecker Expressions for Symmetric Functions,' International Conference on VLSI Design, pp.511-513, 1997 
    8. P. Lindgren, R. Drechsler, B. Becker, 'Improved Minimization Methods of Pseudo Kronecker Expressions for Multiple Output Functions,' ISCAS Proceedings of the IEEE International Symposium, Vol.6, pp.187-190, 1998 
    9. B. R. Becker and R. Drechsler, 'OKFDD's versus OBDD's and OFDD's,' Proceedings of ICALP, LNCS 944, pp.475-486, 1995 
    10. R. Drechsler, B. Becker, A. Sarabi, M. Theobald and M. A. Perkowski, 'Efficient Representation and Manipulation of Switching functions Based on Ordered Kronecker Functional Decision Diagrams,' Proceeding of DAC, pp.415-419, 1994 
    11. R. Drechsler, B. Becker and N. Drechsler, 'Minimization of OKFDDs by Genetic Algorithms,' International Symposium on Soft Computing, Reading, Vol.B, pp.528-263, 1996 
    12. R. Drechsler, and B. Becker, 'On Variable Ordering and Decomposition Type Choice in OKFDDs,' IEEE Tran.on Computer, pp.1398-1403, Nov., 1998 
    13. T. Sasao and M. Fujita, Representations of Discrete Functions, Kluwer Academic Publishers, 1996 
    14. R. E. Bryant, 'Graph-based algorithms for Boolean function manipulation,' IEEE Trans. on Computer, pp.677-691, 1986 
    15. B. Becker, R. Drechsler, and M. Theobald, 'On the Implementation of a Package for Efficient Representation and Manipulation of Functional Decision Diagrams,' IFIP Workshop on the Applications on the Reed Muller Expansions, pp.162-169, 1993 

 저자의 다른 논문

  • 정미경 (7)

    1. 1999 "OPKFDD를 이용한 불리안 함수 표현의 최적화" 정보처리논문지 = The transactions of the Korea Information Processing Society 6 (3): 781~791    
    2. 2000 "내부 Dont't care를 이용한 이차원 셀 배열의 새로운 합성 방법" 전기학회논문지. The transactions of the Korean Institute of Electrical Engineers. D / D, 시스템 및 제어부문 49 (2): 81~87    
    3. 2000 "Complex term을 이용한 OPKFDD의 입력변수 순서 방법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (9): 759~767    
    4. 2000 "유전자 알고리즘을 이용한 OPKFDD의 최적화" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (12): 941~950    
    5. 2000 "저전력설계를 위한 공통 표현의 추출" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (1): 109~115    
    6. 2004 "TDS 기법을 이용한 움직임 벡터 추정" 정보처리학회논문지. The KIPS transactions. Part B. Part B b11 (3): 309~316    
    7. 2009 "H.264/AVC에서 효율적인 정화소.부화소 움직임 추정" 정보처리학회논문지. The KIPS transactions. Part B. Part B b16 (2): 123~130    
  • 황민 (2)

  • 이귀상 (56)

  • Kim, Young Cheol (53)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기