Упрощение Prime Implicant с использованием метода Петрика
Что такое метод Петрика "// www.encyclopedia.com/topic/Boolean_algebra.aspx" target = "_ blank"> Булева алгебра - метод упрощения, используемый для сложных схем. Иллюстрированный в таблице 1.1 пример, который имеет два минимальных решения. Если число переменных увеличивается в заданной функции, число основных импликантов и сложность первичной диаграммы может резко возрастать. В этих типах случаев проб и ошибок может быть лучшим выбором для поиска всех минимальных решений. Метод, упомянутый в предыдущей статье, был хорошим способом найти все минимальные решения из диаграммы, но метод Петрика имеет гораздо лучший системный подход. Прежде чем пытаться выполнить метод Петрика, все существенные основные импликанты; а также используемые им минтарии должны быть взяты из диаграммы основных импликантов.
Таблица 1.1.
Чтобы полностью понять эту концепцию, таблица 1.1 будет использоваться для иллюстрации метода Петрика. Чтобы начать, каждая строка таблицы (P 1, P 2, P 3) должна быть помечена. Будет сформирована логическая функция P, которая сохраняется, когда все minterms были закрыты. Это позволяет P 1 быть логической переменной, которая истинна, если основные импликанты в строке P 1 включены в решение. P 2 также должна быть логической переменной, которая истинна, когда простые импликанты в строке P 2 включены в решение и т. Д. Рассматривая столбец 0, кажется, что этот столбец имеет X в строках P 1 и P 2; поэтому строки P 1 и P 2 должны быть выбраны для покрытия minterm 0. Теперь, чтобы покрыть следующий minterm, minterm 1, должны быть выбраны строки P 3 или P 1; поэтому (P 1 + P 3) должно быть истинным. Аналогично, чтобы покрыть minterm 2, (P 2 и P 4) также должны быть справедливыми. Чтобы легко покрыть minterms 5, 6 и 7, выражение (P 3 + P 5), (P 4 + P 6) и (P 5 + P 6) должно быть истинным. Поскольку все минтайны должны быть покрыты, чтобы применить метод Петрика, функция, приведенная ниже, должна выполняться:
P = (P 1 + P 2) (P 1 + P 3) (P 2 + P 4) (P 3 + P 5) (P 4 + P 6) (P 5 + P 6) = 1, что означает что строки P 1 или P 2 должны быть выбраны, а строки P 1 или P 3 и строки P 2 или P 4 и др.
Затем P необходимо полностью свести к минимуму SOP. Это относительно легко из-за того, что выражения не выражаются. После умножения, используя правило булевой алгебры (X + Y) (X + Z) = X + YZ, а также дистрибутивный закон, нижеследующая функция выглядит следующим образом:
P = (P 1 + P 2 P 3) (P 4 + P 2 P 6) (P 5 + P 3 P 6)
= (P 1 P 4 + P 1 P 2 P 6 + P 2 P 3 P 4 + P 2 P 3 P 6) (P 5 + P 3 P 6)
= P 1 P 4 P 5 + P 1 P 2 P 5 P 6 + P 2 P 3 P 4 P 5 + P 2 P 3 P 5 P 6 + P 1 P 3 P 4 P 6 + P 1 P 2 P 3 P 6 + P 2 P 3 P 4 P 6 + P 2 P 3 P 6
После этого, используя X + XY = X для удаления избыточных членов из логической функции P, создается следующая функция:
P = P 1 P 4 P 5 + P 1 P 2 P 5 P 6 + P 2 P 3 P 4 P 5 + P 1 P 3 P 4 P 6 + P 2 P 3 P 6
Теперь, поскольку P должен иметь значение true (или P = 1) для покрытия каждого minterm, эту функцию можно описать следующим образом. Чтобы полностью покрыть каждый minterm, должны быть выбраны строки P 1 и P 4 и P 5 или строки P 1 и P 2 и P 5 и P 6, или строки P 2 и P 3 и P 6. Несмотря на то, что существует всего пять решений, для которых минимальное количество простых импликантов может быть получено, единственными двумя выбранными решениями являются строки P 1, P 4 и P 5 или строки P 2, P 3 и P 6. Выбор первого набора дает F = a'b ' + bc' + ac, а второй - F = a'c ' + b'c + ab, которые записываются в виде двух минимальных SOP-решений.
Метод Петрика обобщен, выглядит следующим образом:
- Начните с сокращения диаграммы основных импликантов; это можно сделать, удалив любую строку основных импликантов и соответствующие столбцы.
- Каждая строка, которая была уменьшена в диаграмме основных импликантов, должна быть помечена как P 1, P 2, P 3 и др.
- Формируется логическая функция P, которая выполняется, когда все столбцы покрыты. Эта функция состоит из произведения суммарных членов, где каждый суммарный член имеет вид (P i0 + P i1 + …), где P i0, P i1 … указывают строки, которые покрывают столбец i.
- Логическая функция P должна быть сведена к минимальной сумме произведений умножением на внешность и применением правила булевой алгебры X + XY = X.
- Каждый термин в результирующей функции представляет собой решение или набор строк, которые охватывают все minterms в диаграмме основных импликантов. Чтобы определить, каковы минимальные решения, выбираются термины, содержащие минимальное число переменных. Каждое из этих выражений представляет собой решение с минимальным числом простых импликантов.
- Для каждого найденного термина подсчитывается и отмечается количество литералов в каждой первичной импликанте. Выбираются термины (термины), которые соответствуют минимальному числу литералов, а затем соответствующие суммы простых импликантов записываются соответственно.
Этот метод очень утомительный для довольно больших диаграмм, но, с другой стороны, он легко реализуется на персональном компьютере.
Упрощение методом Куин-МакКлюкки
При представлении функции, которая не полностью определена, правильное присвоение значений условиям не-ухода необходимо, если требуется получить минимальную форму для функции. Ниже, метод Quine-McCluskey будет изменен и использован для получения минимального решения, если существуют какие-либо условия отсутствия ухода. Во время процесса, условия не-ухода, если они присутствуют, будут рассматриваться так, как если бы они требовали minterms. Таким образом, они могут объединяться вместе с дополнительными minterms для удаления литералов, если они доступны. Экстра-первичный импликатор (ы) может генерироваться из не заботятся, это нормально, потому что дополнительный первичный импликант (ы) будет удален на следующем этапе процесса. При составлении главной диаграммы импликантов, не-заботы не написаны наверху. Это делается для обеспечения того, чтобы все требуемые minterms полностью покрывались одним из выбранных основных импликантов при решении графика. Тем не менее, условия не-ухода не включены в решение в конце, если они уже не использовались в процессе формирования выбранного первичного импликанта. Показано, что пример упрощения функции, которая не полностью определена, обеспечивает лучшее понимание того, что только что было объяснено.
$$ F (A, B, C, D) = \ sum m (2, 3, 7, 9, 11, 13) + \ sum d (1, 10, 15) $$
(Суммирование d и его членов не являются условиями ухода)
Теперь, чтобы найти основные импликанты:
Столбцы, которые не имеют условий ухода, удаляются при создании следующей диаграммы:
* обозначает существенный первичный импликант
F = B'C + CD + AD
Отметив, что, хотя исходная функция задана не полностью определена, это окончательное выражение для F упрощается и определяется для всех возможных значений для A, B, C и D, поэтому полностью определено. Благодаря этому методу значения автоматически присваивались невнимательности в таблице истинности для F, которая была первоначально предоставлена. Заменяя каждый член в конечном выражении для F (показанный выше) с соответствующей суммой minterms, выражение может быть записано следующим образом:
F = (m 2 + m 3 + m 10 + m 11) + (m 3 + m 7 + m 11 + m 15) + (m 9 + m 11 + m 13 + m 15)
Когда m 10 и m 15 появляются в этом выражении, а m 1 - нет, это указывает на то, что условия не-ухода в таблице истинности, первоначально заданные для F, были обозначены следующим образом:
для ABCD = 0001; F = 0; для 1010, F = 1; для 1111, F = 1
Прибытие
На данный момент у вас должно быть понимание того, что такое метод Петрика, как его применять и как упростить неполностью определенные функции с помощью метода Quine-McCluskey. Метод Quine-McCluskey может использоваться с цифровым компьютером для упрощения функций с 15 или более переменными. Далее, для ввода минимального SOP-выражения данной функции будет использоваться метод введенных в карту переменных.