This thesis describes a system which extracts the circuit information from MOS/LSI mask artwork geometry. The recognizable circuit elements are polysilicon gate MOS transistors. The output format of circuit information extracted by the system is the same as SPICE2 input syntax.
We have developed an algorithm solving the "rectangle intersection reporting" problem, which is the most important one to be solved to realize efficient circuit extracting system. The worst case time complexity of our algorithm is O(nlogn + K), space complexity O(n), where n is the number of rectangles and K is the number of intersecting pairs. It also solves the rectangle enclosure problem which is not solved by the known edge-based algorithms.
본 논문에서는 LSI mask artwork pattern을 검사하는 system을 개발하였다. 이 system은 MOS/LSI mask artwork pattern을 읽어서 mask로부터 제조될 회로의 부품간의 연결 상태와 부품의 종류 및 크기를 알아낸다. 이것은 SPICE2의 입력문과 같은 format으로 출력되므로 설계된 chip의 성능을 LSI mask artwork로부터 직접 test할 수 있다.
이 system의 개발을 위하여 새로운 rectangle intersection pair reporting 알고리즘을 개발 적용하였다. 이 알고리즘의 time complexity는 O(n logn + k)이며 space complexity는 O(n)이다. 여기서 n은 사각형의 갯수, k는 intersection pair의 갯수를 나타낸다.