Метод p- алгоритма

При анализе комбинационных схем методом p-алгоритма определяются наборы входных переменных, обеспечивающих заданное значение выходного сигнала КС. Наборы, обеспечивающие на выходе КС логическую 1, образуют так называемое единичное покрытие . Аналогично входные наборы, обеспечивающие на выходе КС логический 0, образуют нулевое покрытие . Рассмотрим покрытия и для простейшего логического элемента 2И, выполняющего функцию Y=X₁X₂. Таблица истинности для этой функции и условное обозначение элемента 2И приведены на рисунке 3.5.

Как видно из приведенной таблицы только при единственном наборе X₁=1 и X₂=1 на выходе ЛЭ будет 1, т.е. единичное покрытие включает только один набор ={1 1}. На выходе ЛЭ будет 0 при трех наборах, образующих нулевое покрытие:

.

Это покрытие можно упростить, заметив, что первый набор склеивается со вторым и третьим, т.е.

Таким образом, для ЛЭ 2И можно сказать, что 1 на его выходе будет только при обеих единицах на входах, а для обеспечения 0 на выходе достаточно подать хотя бы на один вход 0. Рассуждая аналогично, получим таблицу покрытий и для основных ЛЭ, представленных ниже в таблице 3.1.

Таблица 3.1

ЛЭ

НЕ 2И 2И – НЕ 2ИЛИ 2ИЛИ–НЕ ИСК. ИЛИ 3И – НЕ

X X₁ X₂ X₁ X₂ X₁ X₂ X₁ X₂ X₁ X₂ X₁ X₂ X₃

1 0 X 1 1 0 0 1 X 0 0 1 1 1

X 0 X 1 1 1

0 1 1 0 X 1 X 0 0 0 1 0 X X

X 0 X 1 1 0 X 0 X

X X 0

При анализе схемы методом p -алгоритма, задавшись определенным значением сигнала на выходе, заменяют его соответствующим покрытием элемента, формирующего выходной сигнал. В результате этого определяется, какие сигналы должны быть на выходах элементов, подключенных к выходному ЛЭ. В свою очередь, сигналы на выходах этих элементов можно заменить соответствующими покрытиями, т.е. определить значения выходных сигналов для других ЛЭ и т.д. Этот процесс продолжается до тех пор, пока не получатся покрытия, состоящие только из входных переменных, называемых опорными. Совокупность таких покрытий и дает соответствующее покрытие схемы.

Пример анализа комбинационной схемы (рисунок 3.4) методом p - алгоритма представлен в таблицах 3.2 и 3.3. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии для обеспечения заданного значения выходного сигнала. Поэтому, при замене одного из значений в строке соответствующим покрытием, все остальные значения для других переменных в этой строке должны присутствовать совместно с этим покрытием.

На основании полученного единичного покрытия можно записать логическую функцию, реализуемую схемой:

В дальнейшем можно сравнить полученную логическую функцию с той,

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

данный путь является тупиковым и его необходимо исключить из дальнейшего рассмотрения. Если ни при одной комбинации входных переменных не обеспечивается значение 1(0) на выходе, то это означает, что схема реализует константу 0(1) соответственно.

Таблица 3.2

а) Получение единичного покрытия

Таблица 3.3

б) Получение нулевого покрытия