Common Expression Extraction Using Spectral Method
Oh-Hyeong Kwon · Journal of the Korea Academia-Industrial cooperation Society · 2021
여러 논리식에 존재하는 공통식을 찾아 반복 사용을 줄여서 전체 논리식에 사용된 리터럴 개수를 줄이기 위한 공통식 추출 방법에 대한 방안을 제안한 것이다. 특히 XOR 연산자를 이용할 경우 논리식이 간략화 될 수 있으며 또한 2개 입력 XOR 게이트는 3개의 트랜지스터만으로 구현이 될 수 있는 장점이 있기 때문에 XOR 연산자를 활용한 논리식을 산출하도록 고안하였다. XOR 연산자를 포함한 논리식을 산출하는 데는 하다마드 행렬을 이용한 스펙트럴 방식을 이용하며, 산출된 논리식은 AND, OR, XOR, NOT 연산자들이 사용된 배타식을 산출한다. 공통식이 될 수 있는 배타식 후보군을 찾기 위한 선험 방법을 또한 제안하였으며, 이 선험 방법을 적용한 알고리즘을 제안하였다. 벤치마크 회로를 대상으로 수행 시간과 산출된 리터럴 개수를 대상으로 타 방법들과 제안한 방법을 비교하였다. 실험결과 여러 벤치마크 회로에 대하여 제안한 방법이 기존 논리식 방법들보다 리터럴 개수를 줄일 수 있음을 보였으며 특히 기존의 스펙트럴 방식보다 약 7% 정도의 리터럴 개수를 줄이는 효과를 얻었다.