Метод Петрика - Petricks method - Wikipedia

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

Алгоритм

  1. Уменьшите импликантную диаграмму простых чисел, удалив основные импликантные строки и соответствующие столбцы.[7]
  2. Обозначьте строки уменьшенной простой импликантной диаграммы , , , , так далее.[7]
  3. Сформировать логическую функцию что верно, когда все столбцы покрыты. п состоит из произведения сумм, где каждый член суммы имеет вид , где каждый представляет собой столбец, покрывающий строку .[7]
  4. Уменьшать к минимальной сумме произведений путем умножения[nb 1] и применяя закон поглощения .[7]
  5. Каждый член в результате представляет решение, то есть набор строк, охватывающий все термины в таблице. Чтобы определить минимальные решения, сначала найдите те члены, которые содержат минимальное количество простых импликантов.[7]
  6. Затем для каждого термина, найденного на пятом шаге, подсчитайте количество литералов в каждой простой импликанте и найдите общее количество литералов.[7]
  7. Выберите термин или термины, состоящие из минимального общего числа литералов, и выпишите соответствующие суммы простых импликант.[7]

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

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

Простая импликантная диаграмма из Алгоритм Куайна-Маккласки как следует:

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

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

 (K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)

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

 = (K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q) = (K + LM) (N + LQ) (P + MQ) = (KN + KLQ + LMN + LMQ) (P + MQ) = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ

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

 = KNP + KLPQ + LMNP + LMQ + KMNQ

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

 KNP LMQ

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

KNP расширяется до a'b '+ bc' + acLMQ расширяется до a'c '+ b'c + ab

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

Примечания

  1. ^ Это вызывает экспоненциальный рост количества столбцов.

Рекомендации

  1. ^ Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977-04-01). «2.3.6. Выбор необходимых первичных импликант». Анализ и дизайн последовательных цифровых систем. Электротехника и электроника (1-е изд.). Лондон и Бейзингсток, Великобритания: Macmillan Press Ltd. С. 19, 77. Дои:10.1007/978-1-349-15757-0. ISBN  0-333-19266-4. В архиве из оригинала на 30.04.2020. Получено 2020-04-30. (4 + viii + 146 + 6 страниц)
  2. ^ Свобода, Антонин; White, Donnamaie E. (2016) [2012, 1985, 1979-08-01]. «9.9. Решение функции Петрика для минимальной ΣΠ-формы y» (PDF). Расширенные методы проектирования логических схем (PDF) (перепечатанное электронное переиздание ред.). Гирлянда 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 году степень магистра электротехники на факультете электротехники. Сигма Си в 1955 г.
    Г-н Петрик был связан с Советом прикладной математики Лаборатории наук о данных в Кембриджские исследовательские лаборатории ВВС США с 1955 года и его недавние исследования в Массачусетском технологическом институте частично поддерживаются AFCRL. В 1959–1962 гг. Он занимал должность преподавателя математики в вечернем отделении аспирантуры. Северо-Восточный университет.
    Г-н Петрик в настоящее время является членом Лингвистическое общество Америки, Лингвистический круг Нью-Йорка, Американская математическая ассоциация, Ассоциация вычислительной техники, а Ассоциация машинного перевода и компьютерной лингвистики.
  4. ^ «Некрологи - Сидар-Рапидс - Стэнли Р. Петрик». Газета. 2006-08-05. п. 16. В архиве из оригинала на 2017-04-13. Получено 2017-04-12. […] CEDAR RAPIDS 74-летний Стэнли Р. Петрик, ранее работавший в Cedar Rapids, умер 27 июля 2006 года в пресвитерианском районе / Св. Luke's Hospital, Денвер, Колорадо, после 13-летней борьбы с лейкемией. Поминальная служба состоится 14 августа в Объединенной пресвитерианской церкви в Ларами, штат Вайоминг, где он прожил много лет. […] Стэн Петрик родился в Сидар-Рапидс 6 августа 1931 года в семье Кэтрин Хант Петрик и Фреда Петрика. Он окончил среднюю школу Рузвельта в 1949 году и получил степень бакалавра наук. степень по математике от Государственный университет Айовы. Стэн женился на Мэри Этель Бакстон в 1953 году.
    Он присоединился к ВВС США и был назначен студентом, изучавшим цифровые вычисления в Массачусетский технологический институт, где он получил степень магистра наук. степень. Затем он был назначен на отделение прикладной математики Кембриджская исследовательская лаборатория ВВС США и пока там получил докторскую степень. в лингвистике.
    20 лет проработал в группе теоретической и компьютерной лингвистики факультета математических наук IBM с Исследовательский центр Т. Дж. Уотсона, проведение исследований в области теории формального языка. Он работал заместителем директора Департамента математических наук, председателем Специальной группы по символьным и алгебраическим манипуляциям Ассоциация вычислительной техники и президент Ассоциация компьютерной лингвистики. Он является автором множества технических публикаций.
    Он преподавал три года в Северо-Восточный университет и 13 лет в Институте Пратта. Доктор Петрик присоединился к Университет Вайоминга в 1987 году, где он сыграл важную роль в разработке и внедрении докторской степени. программа на кафедре и служила руководителем диссертаций для многих аспирантов. Он вышел на пенсию в 1995 году. […]     (NB. Включает фотографию Стэнли Р. Петрика.)
  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. NCN 420-5805-4.
  7. ^ а б c d е ж грамм час я j Рот младший, Чарльз Х. (1992). Основы логического дизайна (4-е изд.). ISBN  0-31492218-0.
  8. ^ Pyne, Insley B .; Маккласки младший, Эдвард Джозеф (1962). «Уменьшение избыточности при решении простых импликантных таблиц». I.R.E. Сделки на электронных компьютерах. ИС-11 (4): 473–482.
  9. ^ Чоудхури, Арун К. (февраль 1968 г.). "И. Б. Пайн и Э. Дж. Маккласки-младший, Уменьшение избыточности при решении простых импликантных таблиц. Операции IRE на электронных компьютерах, том EC-11 (1962), стр. 473–482". Журнал символической логики. Отзывы. Ассоциация символической логики (ASL). 32 (4): 540–541. Дои:10.2307/2270229. JSTOR  2270229.
  10. ^ Френзель, Джеймс «Джим» Ф. (2007). «Лекция № 10: Метод Петрика». ECE 349 - Базовое исследование основ цифровых компьютеров. Москва, Айдахо, США: Департамент электротехники и вычислительной техники, Университет Айдахо. В архиве из оригинала на 2017-04-12. Получено 2019-08-08. [3]

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

внешняя ссылка