카르노프 맵(Karnaugh Map) 링크드 리스트로 구현

소개

이 프로그램은 Linux( Kernel 2.6.22-14-generic #1 )에서 프로그래밍을 했으며, 컴파일러는 gcc( GCC 4.1.3 20070929 )로 하였습니다. 사용언어는 C++이며, 대부분은 C Language Style로 코딩했습니다. 입력변수값은 1변수부터 4변수까지 모두 다 출력이 가능하고 그 이상의 것은 결과가 나오지 않게 만들었습니다.
Karnaugh Map Minimize Program(이상 : KMap 프로그램)은 다음과 같은 과정을 지켜서 구동되어 결과값을 출력합니다.
1) 입력에서 주어진 각 Minterm(값이 1인 Minterm과 Don’tCare)에 대한 이진형태
2) 위의 Minterm값을 K-Map과 그 리스트에 Plot을 합니다.
3) K-Map의 리스트에서 Prime Implicant를 찾습니다.
4) 위에서 찾은 Prime Implicant에서 Essential Prime Implicant를 찾습니다.
5) 마지막으로 EPI와 PI들의 조합으로 최소화된 Minterm의 항을 찾아서 출력합니다.
이 프로그램의 자료구조의 기본은 링크드 리스트가 되며 특히 K-Map은 단일 링크드 리스트이고 나머지 Minterm이나 Prime같은 자료는 스택 링크드 리스트에 저장하여 처리하도록 설계하였습니다.

컴파일 실행환경

gcc 4.1.3, linux

참고자료

· Fundamentals of Logic Design, Charles H. Roth, Jr