Quine-McCluskey 알고리즘

Quine–McCluskey algorithm
3개 변수에 대한 알고리즘의 검색 그래프의 Hasse 다이어그램. Given e.g. the subset of the bottom-level nodes (light green), the algorithm computes a minimal set of nodes (here: S을를 정확하게 포함하는 {a}\}, .

주요 내연제의 방법으로도 알려져 있는 Quine-McCluskey 알고리즘(QMC)은 윌러드 V가 개발한 부울 함수의 최소화에 사용되는 방법이다. 1952년[1][2] 퀘인, 1956년 에드워드 J. 매클러스키에 의해 확장되었다.[3] 일반적인 원칙으로서 이 접근법은 1878년 논리학자 휴 맥콜에 의해 이미 증명되었고,[4][5][6] 1937년 아치 블레이크에 의해 증명되었으며,[7][8][9][6] 에드워드 W. 샘슨과 버튼 E에 의해 재발견되었다. 1954년[10][6] 밀스, 1955년 레이먼드 J. 넬슨에 의해 제작되었다.[11][6] 또한 1955년에는 알버트 A뿐만 아니라 폴 W. 에이브럼스와 존 G. 노달도[12] 알버트 A. 멀린과 웨인 G. 켈너는[13][14][15][16] 이 방법의 십진수 변형을 제안했다.[17][14][15][16][18][19][20][21]

Quine-McCluskey 알고리즘은 기능적으로는 Karnaugh mapping과 동일하지만 표 형태는 컴퓨터 알고리즘에 사용하기 더 효율적이며, 부울 함수의 최소 형태에 도달했는지 확인할 수 있는 결정론적 방법을 제공한다. 이것을 표법이라고 부르기도 한다.

이 방법에는 다음 두 단계가 포함된다.

  1. 함수의 주요 내연성 물질을 모두 찾는 중.
  2. 주요 내연성 차트에 있는 주요 내연성 물질과 그 기능을 다루는 데 필요한 다른 주요 내연성 물질을 찾으려면 해당 내연성 물질을 사용한다.

복잡성

4개 이상의 변수를 다룰 때 Karnaugh mapping보다 실용적이긴 하지만, Quine-McCluskey 알고리즘은 해결되는 문제가 NP-완전이기 때문에 사용 범위도 제한적이다.[22][23][24] Quine-McCluskey 알고리즘의 실행 시간은 변수 수에 따라 기하급수적으로 증가한다. n 변수의 함수인 경우 주요 내연물질의 수는 최대 / n 3[25] 예를 들어 32개 변수의 경우 534 × 10개12 이상의 주요 내연물질일 수 있다. 변수가 많은 기능은 잠재적으로 최적화되지 않은 경험적 경험적 접근법으로 최소화해야 하는데, 그 중 에스프레소 경험적 접근법 최소화가 1995년 사실상의 표준이었다.[needs update][26]

알고리즘의 2단계는 설정된 커버 문제를 해결하는 것과 같다.[27] 이 문제의 NP-hard 인스턴스는 이 알고리즘 단계에서 발생할 수 있다.[28][29]

예

입력

In this example, the input is a Boolean function in four variables, which evaluates to on the values and , evaluates to an unknown value on }및 {\displaystyle , 그리고 다른 모든 에서 0 0에 대해(여기서 이러한 정수는 표기법 간결성을 f 에 대한 입력을 위해 이진 형태로 해석된다). 까지 평가하는 입력을 'minterms'라고 한다. 우리는 이 모든 정보를 글로써 암호화한다.

이 표현식은 출력함수 f가 minterms ,8, 및 m' 항으로 표시됨)에 대해 1이 되며, 및 14' 항으로 표시됨에 대한 출력은 상관하지 않는다는 것이다.

1단계: 주요 내연성 물질 찾기

첫째, 함수를 표로 쓴다('x'는 don't care:

A B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 x
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 x
m15 1 1 1 1 1

함수가 평가하는 최소 조건(관심하지 않는 조건)을 합하면 이 표에서 제품 표현의 표준 합계를 쉽게 구성할 수 있다.

fA,B,C,D = A'BC'D' + ABC'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

최소한은 아니잖아 그래서 최적화하기 위해, 1까지 평가하는 모든 Minterm은 먼저 Minterm 테이블에 배치된다. Don't-care 용어는 또한 이 표( 괄호 안의 이름)에 추가되므로 다음과 같이 작은 문자와 결합할 수 있다.

숫자
1분의 1의		 민기 이진수
표현
1 m4 0100
m8 1000
2 (m9) 1001
m10 1010
m12 1100
3 m11 1011
(m14) 1110
4 m15 1111

이 때, 사람들은 미니어처와 다른 미니어처들을 결합하기 시작할 수 있다. 두 항이 한 자릿수만 다를 경우 해당 숫자를 숫자가 중요하지 않음을 나타내는 대시(dash)로 대체할 수 있다. 더 이상 결합할 수 없는 항은 별표(*)로 표시된다. 예를 들어. 1000 그리고 1001 합쳐서 줄 수 있다 100-, 두 음소거 모두 첫 번째 숫자가 1 그리고 다음 두 사람은 0.

숫자
1분의 1의		 민기 0-큐브 사이즈 2 내연제
1 m4 0100 m(4,12) -100*
m8 1000 m(8,9) 100-
— — m(8,10) 10-0
— — m(8,12) 1-00
2 m9 1001 m(9,11) 10-1
m10 1010 m(10,11) 101-
— — m(10,14) 1-10
m12 1100 m(12,14) 11-0
3 m11 1011 m(11,15) 1-11
m14 1110 m(14,15) 111-
4 m15 1111 —

사이즈 2에서 사이즈 4로 변경 시 처리 - 3비트 값으로 예를 들어. -110 그리고 -100 합쳐서 줄 수 있다 -1-0, 할 수 있는 대로 -110 그리고 -11- 주다 -11-그렇지만 -110 그리고 011- 때문에 할 수 없다 -110 은연중에 있다 1110 하는 동안에 011- 그렇지 않다. (Trick: Match up the world) - 첫 번째).

숫자
1분의 1의		 민기 0-큐브 사이즈 2 내연제 사이즈 4 내연제
1 m4 0100 m(4,12) -100* m(8,9,10,11) 10--*
m8 1000 m(8,9) 100- m(8,10,12,14) 1--0*
— — m(8,10) 10-0 —
— — m(8,12) 1-00 —
2 m9 1001 m(9,11) 10-1 m(10,11,14,15) 1-1-*
m10 1010 m(10,11) 101- —
— — m(10,14) 1-10 —
m12 1100 m(12,14) 11-0 —
3 m11 1011 m(11,15) 1-11 —
m14 1110 m(14,15) 111- —
4 m15 1111 — —

참고: 이 예에서, 크기 4 내포제 표의 어떤 용어도 더 이상 결합할 수 없다. 일반적으로 이 과정은 더 이상 용어를 조합할 수 없을 때까지 계속되어야 한다(사이즈 8, 16 등).

2단계: 주요 내연성 차트

그 어떤 조건도 이것보다 더 이상 결합할 수 없기 때문에, 이 시점에서 우리는 본질적인 주요 내연성 표를 구축한다. 옆면을 따라 방금 생성된 주요 내연성 물질이 나오고, 윗부분을 따라 앞서 지정한 미니어처가 나온다. 상관 없음 용어는 상단에 배치되지 않는다. 필요한 입력 사항이 아니기 때문에 이 절에서 생략한다.

4 8 10 11 12 15 ⇒ A B C D
m(4,12)* ✓ ✓ ⇒ — 1 0 0
m(8,9,10,11) ✓ ✓ ✓ ⇒ 1 0 — —
m(8,10,12,14) ✓ ✓ ✓ ⇒ 1 — — 0
m(10,11,14,15)* ✓ ✓ ✓ ⇒ 1 — 1 —

중요한 내연자들을 찾기 위해 우리는 맨 위 줄에 따라 달린다. "✓"가 한 개뿐인 칼럼을 찾아야 한다. 한 열에 하나의 "✓"만 있는 경우, 이는 최소 용어는 하나의 주요 내연성 물질에 의해서만 커버될 수 있음을 의미한다. 이 주요 내성제는 필수적이다.

예를 들어, 첫 번째 열에서 최소 4항과 함께 "✓"는 하나만 있다. m(4,12)이 필수라는 뜻이다. 그래서 우리는 그 옆에 별을 배치한다. 민기 15도 ' "'가 1개뿐이어서 m(10,11,14,15)도 필수다. 이제 하나의 "✓"가 있는 모든 컬럼이 커버된다.

두 번째 주요 내연제는 세 번째와 네 번째에 의해 '덮어진다'고 할 수 있고, 세 번째 내연제는 두 번째와 첫 번째에 '덮어진다'고 할 수 있으며, 따라서 둘 다 필수적인 것은 아니다. 예상한 대로 주요 내연제가 필요한 경우 최소화된 부울 방정식에 포함시킬 필요가 있다. 일부의 경우 필수적 주요 내연성 제안자가 모든 세부사항을 포함하지 않으며, 이 경우 차트 축소를 위한 추가 절차를 사용할 수 있다. 가장 간단한 "추가 시술"은 시행착오지만 보다 체계적인 방법은 페트릭의 방법이다. 현재의 예에서 본질적인 주요 내연제는 모든 민어를 취급하지 않기 때문에 이 경우 필수 내연제는 두 개의 비 필수 내연제 중 하나와 결합하여 다음과 같은 하나의 방정식을 산출할 수 있다.

fA,B,C,D = BC'D' + AB' + AC[30]

또는

fA,B,C,D = BC'D' + AD' + AC

이 두 최종 방정식은 모두 기능적으로 원래의 장황한 방정식과 동일하다.

fA,B,C,D = A'BC'D' + ABC'D' + ABC'D + AB'D'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

참고 항목

참조

  1. ^ Quine, Willard Van Orman (October 1952). "The Problem of Simplifying Truth Functions". The American Mathematical Monthly. 59 (8): 521–531. doi:10.2307/2308219. JSTOR 2308219.
  2. ^ Quine, Willard Van Orman (November 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627–631. doi:10.2307/2307285. hdl:10338.dmlcz/142789. JSTOR 2307285.
  3. ^ McCluskey, Jr., Edward Joseph (November 1956). "Minimization of Boolean Functions". Bell System Technical Journal. 35 (6): 1417–1444. doi:10.1002/j.1538-7305.1956.tb03835.x. hdl:10338.dmlcz/102933. Retrieved 2014-08-24.
  4. ^ McColl, Hugh (1878-11-14). "The Calculus of Equivalent Statements (Third Paper)". Proceedings of the London Mathematical Society. s1-10 (1): 16–28. doi:10.1112/plms/s1-10.1.16.
  5. ^ Ladd, Christine (1883). "On the algebra of logic". In Peirce, Charles Sanders (ed.). Studies in Logic. Boston, USA: Little, Brown & Company. pp. 17–71. p. 23: [...] If the reduction [of an expression to simplest form] is not evident, it may be facilitated by taking the negative of the expression, reducing it, and then restoring it to the positive form. [...]
  6. ^ a b c d e Brown, Frank Markham (November 2010) [2010-10-27]. "McColl and Minimization". History and Philosophy of Logic. Taylor & Francis. 31 (4): 337–348. doi:10.1080/01445340.2010.517387. ISSN 1464-5149. Archived from the original on 2020-04-15. Retrieved 2020-04-15.
  7. ^ a b 블레이크, 아치[1937년](1938년).정규 표현 Boolean대수학(Dissertation)(Lithographed 교육.)에서.일리노이 주, 시카고 미국:시카고 대학 도서관의. p. 36. 페이지의 주 36:[...]이 메서드가 알려 진 퍼스와 그의 학생들[...]그것은 언급된에서 여러곳에 연구에 논리, 당원들의 존스 홉킨스 대학, 1883년[...](ii+60 페이지).
  8. ^ Blake, Archie (November 1932). "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805.
  9. ^ Blake, Archie (June 1938). "Corrections to Canonical Expressions in Boolean Algebra". The Journal of Symbolic Logic. Association for Symbolic Logic. 3 (2): 112–113. doi:10.2307/2267595. ISSN 0022-4812. JSTOR 2267595.
  10. ^ Samson, Edward Walter; Mills, Burton E. (April 1954). Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions. Bedford, Massachusetts, USA: Air Force Cambridge Research Center. Technical Report AFCRC TR 54-21.
  11. ^ Nelson, Raymond J. (June 1955). "Simplest Normal Truth Functions". The Journal of Symbolic Logic. Association for Symbolic Logic. 20 (2): 105–108. doi:10.2307/2266893. JSTOR 2266893. (4페이지)
  12. ^ "Welcome to the memorial page for John "Jack" G Nordahl June 14, 1933 ~ November 20, 2017 (age 84)". Jellison Funeral Home and Cremation Services. Archived from the original on 2020-05-05. Retrieved 2020-05-05.
  13. ^ 뮬린 알버트 Alkins, Kellner, 웨인 G.(1958년).일리노이 대학, 어바나 주, 미국 그리고 전기 공학부, 매사추세츠 공과 대학교, 매사추세츠, 미국."A유수 시험에서 상속됨 기능을"(PDF)에서 복사되거나 쓰여진다면일리노이 주립 아카데미 과학의 거래는 반드시(양해 각서를 가르치는 것).일리노이 주 스프링필드 미국 51(3–4):14–19.S2CID 125171479.그 2020-05-05에 원래에서Archived(PDF).2020-05-05 Retrieved.그의 책에서 11월 1955년까지 교육 양해 각서로[1](6페이지)(NB, 콜드웰 날짜 이. 멀린은 1958년까지의 작품과 1955년 11월 아브라함스/노르달의 수업 각서 역시 날짜가 적혀있기 때문에, 이것은 카피 에러가 될 수 있다.)
  14. ^ a b 콜드웰, 새뮤얼 호크[2월 1958년](1958-12-01)."5.8항에 운영이 Decimal기호 사용".매사추세츠 주, 미국에서. 전기 회로 및 논리적 설계 전환.5일 인쇄 1963년 9월(1일 교육.).미국 뉴욕:JohnWiley도&SonsInc를 대신하여 서명함. 162–169.아이 에스비엔 0-47112969-0. LCCN 58-7896. 페이지의 주 166:[...]그것은 있다는 것을 기쁘게 이 치료법 두명의 학생들의 작품에 그들은 메사추세츠 공과 대학교의 전기 회로 전환 공부하고 있었다. 그 기간 동안 기초한다 녹화합니다.그들은 독립적으로 다음 수업을 양해 각서:P.W. 아브라함과 J.G.Nordahl(xviii+686 페이지)(NB. 십진법의 이 책 중 중요한 논문을 예로 들자면, 가끔"콜드웰의 십진 제표"로 알려져 있다.)[...]준비하고 공동으로 메서드를 논의했다.
  15. ^ a b 뮬린 알버트 Alkins[1959-09-19](1960-03-15).일리노이 대학교, 어바나 주, 미국 피셔, 하비입니다;Ekblaw, 조지 E., 그린, F.O, 존스, 리스, Kruidenier, 프랜시스 맥, 존은 실바, 폴, 톰슨, 밀턴(eds.)에 쓰여진."초등번 이론의 두 응용 프로그램"(PDF).일리노이 주립 아카데미 과학의 거래.일리노이 주 스프링필드 미국 52(3–4):102–103.그 2020-05-05에 원래에서Archived(PDF).2020-05-05 Retrieved.[2][3][4](2페이지)
  16. ^ a b McCluskey, Jr., 에드워드 조셉(6월 1960년)."알버트 A.Mullin과 웨인 G.Kellner.부울 함수에 대한 잔류성 시험.일리노이 주립 아카데미 과학의 거래 51nos. 3,4(1958년),를 대신하여 서명함. 14–19" vol..그 저널의 상징성 로직(리뷰)의.25(2):185.doi:10.2307/2964263. JSTOR 2964263. 페이지의 주 185:[...]이 종이의 결과 S.H.Caldwell[...]에 의해 좀 더 쉽게 사용 가능한 책에서 제시되어 있다.이 책에는 작가 Mullin과 Kellner에 조작의 10진 숫자와 함께 개발.(1페이지)신뢰를 준다.
  17. ^ Abrahams, Paul William; Nordahl, John "Jack" G. (November 1955). The Modified Quine–McCluskey Reduction Procedure (Class memorandum). Electrical Engineering Department, Massachusetts Institute of Technology, Massachusetts, USA. (4페이지) (NB. 일부 출처에서는 저자를 "P"로 나열한다. W. Abraham과 "I. G. Nordahl"이라는 명칭도 "수정된 McCluskey-Quine 감소 절차"로 인용된다.
  18. ^ Fielder, Daniel C. (December 1966). "Classroom Reduction of Boolean Functions". IEEE Transactions on Education. IEEE. 9 (4): 202–205. Bibcode:1966ITEdu...9..202F. doi:10.1109/TE.1966.4321989. eISSN 1557-9638. ISSN 0018-9359.
  19. ^ Kämmerer, 빌헬름(5월 1969년)."I.12. Theorie:Minimierung Boolescher Funktionen".예나, 독일에서 쓰여진.Frühauf, 한스, Kämmerer, 빌헬름, 슈뢰더, 커즈!;빙클러, 헬무트(eds.)에서.Digitale Automaten Theorie, 식물의 구조, Technik, Programmieren –.Elektronisches Rechnen 운트 Regeln(독일어로).Vol5(1판).베를린 독일:Akademie-Verlag 회사.를 대신하여 서명함. 98, 103–104.면허증 번호 202-100/416/69.주문 번호 4666 줄기 20K3. 페이지의 주 98:[...]Verfahren 죽auf 1955년 wurde 다쓰 bequemeredezimale Schreibweise umgestellt(P.W. 아브라함[콜드웰]에 나 G.Nordahl 운트).[...](NB다.두번째 판 1973년.)존재한다.
  20. ^ Holdsworth, Brian; Woods, Clive (2002). "3.17 Decimal approach to Quine–McCluskey simplification of Boolean algebra". Digital Logic Design (4 ed.). Newnes Books / Elsevier Science. pp. 65–67. ISBN 0-7506-4588-2. Retrieved 2020-04-19.{{cite book}}: CS1 maint : ISBN 오류 무시 (링크) (519페이지) [5]
  21. ^ Majumder, Alak, 초두리, Barnali, 몬달은, Abir J., 자이나교도, Kunj(2015-01-30)[2015-01-09].콰인 McCluskey 방법:Decimal정보의 교환을 기반 소설적 접근에 Boolean기능. 2015년 국제 회의 전자 디자인, 컴퓨터 네트워크 &amp에 자동 검증(EDCAV), 실롱, 인도(회의 종이)의 초고층을 탐구부서 전자 및, 통신, 공학 국립 공과 대학의 아루나찰프라데시주 Yupia, 인도.를 대신하여 서명함. 18–22. doi:10.1109/EDCAV.2015.7060531.그 2020-05-08에 원래에서 Archived.2020-05-08 Retrieved.[6](NB다. 이 저작은 십진법에 대한 선행기술은 인용하지 않는다.)(5쪽)
  22. ^ Masek, William J. (1979). Some NP-complete set covering problems. unpublished.
  23. ^ Czort, Sebastian Lukas Arne (1999). The complexity of minimizing disjunctive normal form formulas (Master's thesis). University of Aarhus.
  24. ^ Umans, Christopher; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (2006-06-05). "Complexity of two-level logic minimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 25 (7): 1230–1246. doi:10.1109/TCAD.2005.855944. S2CID 10187481.
  25. ^ Chandra, Ashok K.; Markowsky, George (1978). "On the number of prime implicants". Discrete Mathematics. 24 (1): 7–11. doi:10.1016/0012-365X(78)90168-1.
  26. ^ Nelson, Victor P.; Nagle, H. Troy; Carroll, Bill D.; Irwin, J. David (1995). Digital Logic Circuit Analysis and Design (2 ed.). Prentice Hall. p. 234. ISBN 978-0-13463894-2. Retrieved 2014-08-26.
  27. ^ Feldman, Vitaly (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries". Journal of Computer and System Sciences. 75: 13–25 [13–14]. doi:10.1016/j.jcss.2008.07.007.
  28. ^ Gimpel, James F. (1965). "A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table". IEEE Transactions on Computers. 14: 485–488. doi:10.1109/PGEC.1965.264175.
  29. ^ Paul, Wolfgang Jakob (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615. S2CID 35973949.
  30. ^ 로직 프라이데이 프로그램

추가 읽기

외부 링크