Метод Петрика
Алгоритм минимизации для булевой алгебры

В булевой алгебре метод Петрика [1] (также известный как функция Петрика [2] или метод ветвей и границ ) — это метод, описанный Стэнли Р. Петриком (1931–2006) [3] [4] в 1956 году [5] [6] для определения всех решений минимальной суммы произведений из простой импликантной карты . [7] Метод Петрика очень утомителен для больших карт, но его легко реализовать на компьютере. [7] Метод был усовершенствован Инсли Б. Пайном и Эдвардом Джозефом МакКласки в 1962 году. [8] [9]

Алгоритм

  1. Сократите таблицу основных импликантов, исключив существенные строки основных импликантов и соответствующие столбцы. [7]
  2. Обозначьте строки приведенной первичной импликантной диаграммы , , , , и т.д. [7] П 1 {\displaystyle P_{1}} П 2 {\displaystyle P_{2}} П 3 {\displaystyle P_{3}} П 4 {\displaystyle P_{4}}
  3. Сформируйте логическую функцию , которая истинна, когда покрыты все столбцы. P состоит из произведения сумм, где каждый член суммы имеет форму , где каждый представляет строку, покрывающую столбец . [7] П {\displaystyle P} ( П я 0 + П я 1 + {\displaystyle (P_{i0}+P_{i1}+} ⋯ {\displaystyle \cdots} + П я Н ) {\displaystyle +P_{iN})} П я дж {\displaystyle P_{ij}} я {\displaystyle я}
  4. Применить законы Де Моргана для расширения в сумму произведений [примечание 1] и минимизировать, применив закон поглощения . [7] П {\displaystyle P} Х + Х И = Х {\displaystyle X+XY=X}
  5. Каждый термин в результате представляет решение, то есть набор строк, который охватывает все минтермы в таблице. Чтобы определить минимальные решения, сначала найдите те термины, которые содержат минимальное количество простых импликантов. [7]
  6. Далее, для каждого из терминов, найденных на пятом шаге, подсчитайте количество литералов в каждой простой импликанте и найдите общее количество литералов. [7]
  7. Выберите термин или термины, состоящие из минимального общего числа литералов, и выпишите соответствующие суммы простых импликантов. [7]

Пример метода Петрика

Ниже приведена функция, которую мы хотим уменьшить: [10]

ф ( А , Б , С ) = ∑ м ( 0 , 1 , 2 , 5 , 6 , 7 ) = А ′ Б ′ С ′ + А ′ Б ′ С + А ′ Б С ′ + А Б ′ С + А Б С ′ + А Б С {\displaystyle f(A,B,C)=\sum m(0,1,2,5,6,7)=A'B'C'+A'B'C+A'BC'+AB'C+ABC'+ABC}

Основная импликантная диаграмма алгоритма Куайна-Маккласки выглядит следующим образом:

012567⇒АБС
К = м(0,1)✓✓⇒00—
L = м(0,2)✓✓⇒0—0
М = м(1,5)✓✓⇒—01
N = m(2,6)✓✓⇒—10
Р = м(5,7)✓✓⇒1—1
Q = м(6,7)✓✓⇒11—

На основе знаков ✓ в таблице выше постройте произведение сумм строк. Каждый столбец таблицы создает термин произведения, который складывает строки, имеющие знак ✓ в этом столбце:

(К+Л)(К+М)(Л+Н)(М+П)(Н+К)(П+К)

Используйте распределительный закон, чтобы превратить это выражение в сумму произведений. Также используйте следующие эквивалентности, чтобы упростить окончательное выражение: X + XY = X и XX = X и X + X = X

= (К+Л)(К+М)(Л+Н)(М+П)(Н+К)(П+К) = (К+ЛМ)(Н+ЛК)(П+МК) = (КН+КЛК+ЛМН+ЛМК)(П+МК) = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ

Теперь снова воспользуемся следующей эквивалентностью, чтобы еще больше сократить уравнение: X + XY = X

= KNP + KLPQ + LMNP + LMQ + KMNQ

Выберите продукты с наименьшим количеством терминов. В этом примере есть два продукта с тремя терминами:

КНП ЛМК

Ссылаясь на таблицу основных импликантов, преобразуйте каждое произведение, заменив основные импликанты их выражением в виде булевых переменных, и подставьте сумму для произведения. Затем выберите результат, который содержит наименьшее количество общих литералов (булевых переменных и их дополнений). Ссылаясь на наш пример:

KNP расширяется до A'B' + BC' + AC, где K преобразуется в A'B', N преобразуется в BC' и т. д.LMQ расширяется до A'C' + B'C + AB

Оба продукта расширяются до шести литералов каждый, так что можно использовать любой из них. В общем, применение метода Петрика утомительно для больших диаграмм, но его легко реализовать на компьютере. [7]

Примечания

  1. ^ Это приводит к экспоненциальному росту числа столбцов: разложение произведения сумм, содержащих члены, обычно приводит к сумме с членами. к {\displaystyle к} н 1 , н 2 , . . . , н к {\displaystyle n_{1},n_{2},...,n_{k}} н 1 н 2 . . . н к {\displaystyle n_{1}n_{2}...n_{k}}

Ссылки

  1. ^ Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977-04-01). "2.3.6. Выбор требуемых простых импликантов". Анализ и проектирование последовательных цифровых систем. Электротехника и электроника (1-е изд.). Лондон и Бейзингсток, Великобритания: The Macmillan Press Ltd. стр. 19, 77. doi :10.1007/978-1-349-15757-0. ISBN 0-333-19266-4. Архивировано из оригинала 2020-04-30 . Получено 2020-04-30 .(4+viii+146+6 страниц)
  2. ^ Свобода, Антонин ; Уайт, Доннамайе Э. (2016) [2012, 1985, 1979-08-01]. "9.9. Решение функции Петрика для минимальной ΣΠ-формы y" (PDF) . Advanced Logical Circuit Design Techniques (PDF) (перепечатанное электронное переиздание). Garland STPM Press (оригинальный выпуск) / WhitePubs Enterprises, Inc. (переиздание). стр. 148–150. ISBN 978-0-8240-7014-4. LCCN  78-31384. Архивировано (PDF) из оригинала 2017-04-14 . Получено 2017-04-15 .[1] [2]
  3. ^ "Биографическая справка". Архивировано из оригинала 2017-04-13 . Получено 2017-04-12 . Стэнли Р. Петрик родился в Сидар-Рапидс, штат Айова, 16 августа 1931 года. Он учился в средней школе Рузвельта и получил степень бакалавра наук по математике в Университете штата Айова в 1953 году. С 1953 по 1955 год он учился в Массачусетском технологическом институте, находясь на действительной службе в качестве офицера ВВС, и получил степень магистра наук на кафедре электротехники в 1955 году. Он был избран в Sigma Xi в 1955 году. Г-н Петрик был связан с Советом по прикладной математике Лаборатории наук о данных в Кембриджских исследовательских лабораториях ВВС с 1955 года, и его последние исследования в MIT частично финансировались AFCRL. В 1959–1962 годах он занимал должность преподавателя математики в вечернем аспирантском отделении Северо-Восточного университета . В настоящее время г-н Петрик является членом Лингвистического общества Америки , Лингвистического кружка Нью-Йорка , Американской математической ассоциации , Ассоциации вычислительной техники и Ассоциации машинного перевода и компьютерной лингвистики .

  4. ^ "Некрологи - Сидар-Рапидс - Стэнли Р. Петрик". The Gazette . 2006-08-05. стр. 16. Архивировано из оригинала 2017-04-13 . Получено 2017-04-12 . [...] СИДАР-РАПИДС Стэнли Р. Петрик, 74 года, ранее проживавший в Сидар-Рапидс, умер 27 июля 2006 года в пресвитерианской больнице Св. Луки в Денвере, штат Колорадо, после 13-летней борьбы с лейкемией. Панихида состоится 14 августа в Объединенной пресвитерианской церкви в Ларами, штат Вайоминг, где он прожил много лет. [...] Стэн Петрик родился в Сидар-Рапидс 6 августа 1931 года в семье Кэтрин Хант Петрик и Фреда Петрика. Он окончил среднюю школу Рузвельта в 1949 году и получил степень бакалавра наук по математике в Университете штата Айова . Стэн женился на Мэри Этель Бакстон в 1953 году. Он присоединился к ВВС США и был направлен в качестве офицера-стажера, изучающего цифровые вычисления в Массачусетском технологическом институте , где получил степень магистра. Затем он был направлен в отделение прикладной математики исследовательской лаборатории ВВС в Кембридже и там получил степень доктора философии по лингвистике. Он провел 20 лет в группе теоретической и вычислительной лингвистики кафедры математических наук в исследовательском центре TJ Watson компании IBM , проводя исследования в области формальной теории языка. Он занимал должность помощника директора кафедры математических наук, председателя специальной группы по символическим и алгебраическим манипуляциям Ассоциации вычислительной техники и президента Ассоциации вычислительной лингвистики . Он является автором множества технических публикаций. Он преподавал три года в Северо-Восточном университете и 13 лет в Институте Пратта. Доктор Петрик присоединился к Университету Вайоминга в 1987 году, где он сыграл важную роль в разработке и внедрении программы Ph.D. на кафедре и был научным руководителем многих аспирантов. Он вышел на пенсию в 1995 году. [...]


    (Примечание. Включает фотографию Стэнли Р. Петрика.)
  5. ^ Петрик, Стэнли Р. (1956-04-10). Прямое определение неизбыточных форм булевой функции из набора простых импликантов . Бедфорд, Кембридж, Массачусетс, США: Исследовательский центр ВВС Кембриджа . Технический отчет AFCRC TR-56-110.
  6. ^ Левин, Дуглас (1974) [1968]. Логическое проектирование функций переключения (1981 7-е переиздание 2-го изд.). Thomas Nelson and Sons Ltd / Van Nostrand Reinhold Co., Ltd. стр. 60. ISBN 0-442-30747-0. ISBN 0-17-771044-6 . НКН 420-5805-4. 
  7. ^ abcdefghij Рот, младший, Чарльз Х. (1992). Основы логического проектирования (4-е изд.). West Publishing Company. ISBN 0-31492218-0.
  8. ^ Pyne, Insley B.; McCluskey, Jr., Edward Joseph (1962). «Сокращение избыточности при решении таблиц простых импликант». IRE Transactions on Electronic Computers . EC-11 (4): 473–482.
  9. ^ Чоудхури, Арун К. (февраль 1968 г.). "IB Pyne и EJ McCluskey Jr., Сокращение избыточности при решении таблиц простых импликант. Транзакции IRE на электронных компьютерах, т. EC-11 (1962), стр. 473–482". Журнал символической логики . Обзоры. 32 (4). Ассоциация символической логики (ASL): 540–541. doi :10.2307/2270229. JSTOR  2270229. S2CID  57871609.
  10. ^ Frenzel, James "Jim" F. (2007). "Lecture #10: Petrick's Method". ECE 349 – Background Study in Digital Computer Fundamentals . Москва, Айдахо, США: Department of Electrical and Computer Engineering, University of Idaho . Архивировано из оригинала 2017-04-12 . Получено 2019-08-08 .[3]

Дальнейшее чтение

  • Крамбек, Дональд (2016-02-17). "Упрощение первичного импликанта с использованием метода Петрика". Все о схемах . EETech Media, LLC. Архивировано из оригинала 2017-04-12 . Получено 2020-04-03 .
  • Петрик, Стэнли Р. (1965). Процедура распознавания трансформационных грамматик (диссертация на степень доктора философии). Массачусетский технологический институт .
  • Bolton, Martin (1990). "4. Минимизация". Написано в Университете Бристоля, Бристоль, Великобритания. В Dagless, Erik L. (ред.). Проектирование цифровых систем с программируемой логикой. Серия «Электронные системы» (1-е изд.). Wokingham, Великобритания: Addison-Wesley Publishers Ltd. стр. 100–101, 115. ISBN 0-201-14545-6. LCCN  90000007. ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r . Получено 17.04.2021 . (xiv+379+1 страницы)
  • Учебное пособие по методу Куайна-Маккласки и Петрика
  • Реализация Petrick C++ на основе приведенного выше руководства
Взято с "https://en.wikipedia.org/w/index.php?title=Petrick%27s_method&oldid=1248200475"