깊이우선 검색을 이용한 논리 추출 알고리즘 = Logic extraction algorithm based on depth first search

국문 초록 (Abstract)

본 논문은 깊이우선 검색(depth first search)을 이용하여 CMOSVLSI 회로로 부터 등가 논리레벨의 회로로 변환하는 효율적인 논리 추출 알고리듬에 관한것이다.
제안하는 방법에 있어서 논리 추출은 두 단계의 절차에 의해서 수행된다. 우선 트랜지스터 레벨의 회로를 인접 그래프(adjacent graph)로 변환하고, 논리회로를 구성하는 가장 기본적인 논리기능(logic function) 블럭으로 나눈다. 다음에 각각의 기능 블럭을 직병렬 그래프(series-parallel graph)로 표현하여 직병렬 분해(series-parall reduction)를 수행한 후, 동형성(isomorphic) 판정 과정을 거쳐서 게이트 레벨의 회로를 추출한다.

다국어 초록 (Multilingual Abstract)

This paper describes about an efficient logic extraction algorithm based on the depth first search which can extract gate-level logic description from CMOS transistor level description.
The proposed heuristic series-parallel reduction algorithm extracts primitive logic gates from the given series-parallel graph. The time complexity for performing this algorithm requirs O(m + n), where m and n represent edge and node of the given graph.

목차 (Table of Contents)

• 요약
• Ⅰ. 서론
• Ⅱ. 트랜지스터의 그래프 표현
• Ⅲ. CMOS 회로의 논리 추출
• 1. 데이타 구조
• 2. 트랜지스터 회로의 분할
• 3. 논리 추출 알고리듬
• Ⅳ. 실험 결과 및 고찰
• Ⅴ. 결론
• 참고문헌
• ABSTRACT