이단계 리드뮬러 회로의 최소화를 위한 BDD의 응용 = An Application of BDD for Minimization of Two level Reed Muller Circuits

국문 초록 (Abstract)

본 논문에서는 논리함수를 BDD(Binary Decision Diagrams)로 표현하고 이를 이용하여 이단계 리드뮬러 회로를 최소화하는 BDD Expand 방법을 제시한다. BDD의 탐색을 통하여 이독을 구하고, BDD의 SOP 큐브들을 각각 확장하여 이득이 가장 큰 큐브를 구하는 방법이다. 리드뮬러 회로를 최소화하는 기존의 Xlinking 방법과 큐브선택 방법은 소규모 회로에 대해 잘 동작하나, SOP 형태나 진리표 형태의 함수 표현 형식을 사용할 때 지수적인 시간과 공간이 필요하게 되는 단점을 갖고 있다. 이와는 달리 BDD는 간단한 함수 표현을 제공하므로 시간과 공간 문제를 한꺼번에 해결할 수 있는 장점이 있다. 실험 결과, 대규모 회로를 합성하는데 효과적인 방법임을 알 수 있다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. BDD (Binary Decision Diagrams)
• 3. 큐브 확장(expand)를 이용한 최소화 방법
• 4. 실험결과
• 5. 결론
• 참고문헌