퀸-매클러스키 알고리즘

위키백과 ― 우리 모두의 백과사전.

이 문서는 en:Quine-McCluskey algorithm에서 한국어로 번역 중입니다. 원문은 글 안에 주석 처리되어 있습니다. 같이 번역해 주세요.

퀸-매클러스키 알고리즘(Quine-McCluskey algorithm)은 논리식을 최소화하는 알고리즘이다. 내부적으로는 카노 맵과 동일하지만, 그림을 그려서 맞추는 카노 맵과 달리 표를 사용하기 때문에 컴퓨터에서 쉽게 돌릴 수 있다. 또한 논리함수의 최소 형태를 결정론적으로 구할 수 있다.

알고리즘은 다음 두 단계로 구성된다.

  1. 주어진 함수의 prime implicant를 모두 구한다.
  2. prime implicants들을 이용해서 prime implicant chart에서 essential prime implicant를 구한다.

[편집] 복잡도

카노 맵과 달리, 퀸-매클러스키 알고리즘을 사용하면 변수가 4개를 넘더라도 효율적으로 논리 최적화할 수 있다. 그러나 논리 최적화 문제가 기본적으로 NP-완전이므로, 퀸-매클러스키 알고리즘은 변수의 개수가 제한된 경우에만 효율적으로 실행할 수 있다. 퀸-매클러스키 알고리즘의 실제 실행시간은 입력에 대해 지수적으로 증가한다. n 개의 변수가 있을 때, prime implicant 개수의 상한은 3n/n임을 보일 수 있다. n = 32이면 6.1 * 1014, 즉 617조 개의 prime implicants가 존재한다. 변수의 개수가 많을 때는 heuristic한 방법으로 문제를 풀어야 한다.

[편집] 바깥고리

다른 언어