Переключательные функции (логика высказываний)

Анализ и синтез комбинационных автоматов основан на применении аппарата логики высказываний, позволяющего описывать функционирование комбинационных автоматов с помощью булевых функций [1,2,3,5,6}].

Дизъюнктивной нормальной формой (ДНФ)булевой функции называется представление функции в виде дизъюнкции некоторого числа элементарных конъюнкций, причем под элементарной конъюнкцией понимается логическое произведение любого числа неодинаковых независимых переменных с отрицанием или без него.

Пример. f(x₁,x₂,x₃)= x₁x₂vx₁x₂x₃vx₁x₂x₃.

В данном примере элементарными конъюнкциями являются x₁x₂, x₁x₂x₃, x₁x₂x₃.

Каждая элементарная конъюнкция обеспечивает истинность переключательной функции f(x₁,x₂,…,x_n) на некотором числе наборов x₁x₂,…,x_n независимых переменных. Например, для функции f(x₁,x₂,x₃), приведенной в предыдущем примере, элементарная конъюнкция x₁x₂ обеспечивает истинность переключательной функции на наборах 000 и 001.

Рангом ч элементарной конъюнкции называется число переменных, ее составляющих.

В общем случае для функции от n независимых переменных элементарная конъюнкция ранга ч обеспечивает истинность функции на 2^n-ч наборах аргументов.

Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется ее представление в виде дизъюнкции конституент единицы, т.е. таких элементарных конъюнкций, ранг которых ч равен числу независимых переменных функции n.

Любая булева функция, не равная тождественно нулю, может быть представлена в СДНФ, причем единственным образом. Поэтому СДНФ называют канонической формой.

Пример: функция из предыдущего примера может быть представлена в СДНФ:

f(x₁,x₂,x₃)=x₁x₂x₃vx₁x₂x₃vx₁x₂x₃vx₁x₂x₃.

Переключательные функции применяют для описания логики работы автоматов с одним внутренним состоянием, поэтому таблицы истинности переключательной функции называют также автоматными таблицами.

Пусть задана автоматная таблица (табл. 22):

Таблица 22

X1	X2	X3	f(X1,x2,x3)
			x x

В этой таблице приняты следующие обозначения:

X₁ – сигнал наличия пасажиров в кабине лифта;

X₂ – сигнал перегрузки лифта;

X₃ – сигнал о том, что двери лифта закрыты;

f(X₁,X₂,X₃) – сигнал, разрешающий включение электромотора лифта.

Знаком «X» в табл. 22 отмечены выходы для таких наборов входных сигналов X₁ X₂ и X₃, которые практически не возможны. Можно считать, что переключательная функция f(X₁,X₂,X₃) на этих наборах не определена. Как правило, в этих случаях переключательную доопределяют таким образом, чтобы ее практическая реализация была по возможности проще.

Доопределим f(X₁,X₂,X₃) таким образом, чтобы автоматная таблица имела вид (табл. 23):

Таблица 23

X1	X2	X3	f(X1,x2,x3)

Эта таблица полностью определяет переключательную функцию f(X₁,X₂,X₃).

Для построения СДНФ в соответствии с общей формулой

f(x₁,x₂,…,x_n)=Vx₁^b1x₂^b2…x_n^bn,

f(b₁,b₂,…,b_n)

x_i, если b_i=1;

где x_i^bi=

x_i, если b_i=0,

Выписываем конституенты единицы, соответствующие каждому набору аргументов, на котором функция равна 1, и соединяем их знаками дизъюнкции:

f(X₁,X₂,X₃)=x₁⁰x₂⁰x₃¹Vx₄⁴x₂⁰x₃⁴=x₁x₂x₃vx₁x₂x₃

СДНФ функции применяется как исходная форма при решении задачи упрощения (минимизации) формы переключательной функции.

В случае, когда переключательная функция задана в виде логической формулы, включающей любые логические связи (импликации, эквивалентности и т.д.), целесообразно сначала привести ее к ДНФ с помощью формул:

A→B=AVB (импликация);

A∞B=ABVAB (эквивалентность);

A↓B=AVB (операция Пирса);

A/B=A*B (операция Шеффера);

AÅB=A*BVA*B (неравнозначность);

A∆B=A*B (запрет),

а также основных законов алгебры логики, включая законы де Моргана:

AVB=A*B, A*B=AVB.

Пример.

f(X₁,X₂,X₃)=(x₁→x₂)∞x₃=(x₁Vx₂) ∞x₃=(x₄Vx₂)x₃V(x₁Vx₂)x₃=x₁x₂x₃Vx₁x₃Vx₂x₃.

Для того чтобы ДНФ функции преобразовать в СДНФ, каждую элементарную конъюнкцию ДНФ ранга ч<n следует представить в виде логической суммы 2^n-ч конституент единицы, добавляя отсутствующие в данной конъюнкции логические перемены по правилу

C=x_i*CVx_iC

Пример. f(X₁,X₂,X₃)=x₁x₂x₃Vx₁x₂Vx₂x₃=x₁x₂x₃Vx₁x₂x₃Vx₁x₂x₃Vx₁x₂x_3.

Переключательная функция может быть задана также в виде перечия номеров наборов аргументов, на которых функция принимает единичные значения, что эквивалентно заданию функции в СДНФ.

Пример. f(X₁,X₂,X₃)=V(0,2,5,6)=x₁x₂x₃Vx₁x₂x₃Vx₁x₂x₃Vx₁x₂x₃.

Конъюнктивной нормальной формой (КНФ) булевой функции называется представление функции в виде конъюнкции некоторого числа элементарных дизъюнкций, причем под элементарной дизъюнкцией понимается логическая сумма любого числа неодинаковых независимых переменных с отрицанием или без него.

Пример. f(X₁,X₂,X₃)=V(0,2,5,6)=(x₁Vx₂)Ù(x₁Vx₂Vx₃)Ù(x₁Vx₂Vx₃)

В данном случае дизъюнкциями являются

x₁Vx_2, x₁Vx₂Vx_3, x₁Vx₂Vx₃

Свойства и правила преобразования конъюнктивных нормальных форм в силу законов де Моргана (законов двойственности) подобны свойствам и правилам преобразования дизъюнктивных нормальных форм.

Рангом ч элементарной дизъюнкции называется число переменных, ее составляющих. Элементарная дизъюнкция ранга ч обеспечивает нулевое значение функции от n аргументов на 2_n-ч наборах. В предыдущем примере элементарная дизъюнкция x₁Vx₂ обеспечивает нулевое значение функции f(X₁,X₂,X₃) на наборах 010 и 011.

Конституентой нуля называется элементарная дизъюнкция ранга ч=n. Совершенной конъюнктивной нормальной формой (СКНФ) переключательной функции называется представление функции в виде КНФ, все элементарные дизъюнкции которой являются конституентами нуля. Например:

f(X₁,X₂,X₃)= (x₁Vx₂Vx₃) (x₁Vx₂Vx₃) (x₁Vx₂Vx₃).

Любая переключательная функция, не равная тождественно единице, может быть представлена в СКНФ, причем единственным образом в соответствие с формулой.

f(x₁,x₂,…,x_n)=Л (x₁^b1Vx₂^b2V…Vx_n^bn).

f(b₁,b₂,…,b_n)=0

Для построения СКНФ переключательной функции, заданной в виде таблицы истинности, необходимо выбирать наборы аргументов, на которых функция равна нулю, и составить логическое произведение конституент нуля, соответствующих этим наборам, согласно вышеприведенной формуле.

Например. Пусть переключательная функция задана таблицей истинности (табл. 24)

Таблица 24

X1	X2	X3	f(X1,x2,x3)

Тогда СКНФ этой функции

f(X₁,X₂,X₃)= (x₁Vx₂Vx₃) (x₁Vx₂Vx₃) (x₁Vx₂Vx₃).

Выбор конъюнктивной канонической формы функции выгоден в том случае, когда число нулевых значений функции меньше, чем число единичных значений. В этом случае СКНФ функции имеет меньше членов чем СДНФ этой же функции, что уменьшает трудоемкость минимизации.

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

f(X₁,X₂,X₃)=(x₁↓x₂)→x₃=x₁Vx₂→x₃=(x₁Vx₂) →x₃=x₁Vx₂Vx₃=x₁x₂Vx₃=(x₁Vx₃)(x₂Vx₃)=(x₁Vx₂Vx₃) (x₁Vx₂Vx₃) (x₁Vx₂Vx₃)

5.3 МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ

Целью минимизации СДНФ булевой функции является получение формы, эквивалентной исходной СДНФ, но содержащей минимальное число букв.

Импликантом функции f(x₁,x₂,…,x_n) называется такая элементарная конъюнкция I, что истинность I влечет истинность f, т.е.

I→ f(x₁,x₂,…,x_n)=1,

Любая элементарная конъюнкция произвольной ДНФ является Импликантом функции, представленной этой формой. Например для ДНФ

f(X₁,X₂,X₃)=x₁x₂Vx₁x₃Vx₁x₂x₃

импликантом является элементарная конъюнкция x₁x₂x₃ истинность которой на наборе логических переменных 001 влечет истинность функции на этом же наборе.

Простым импликантом функции f(x₁,x₂,…,x_n) называется импликант I, если удаление любой буквы из I превращает I в элементарную конъюнкцию, не являющуюся импликантом f. В пред идущем примере импликант x₁x₂x₃ не является простым, поскольку удаление X₂ превращает импликант x₁x₂x₃ в элементарную конъюнкцию x₁x₃, являющуюся импликантом функции f. Импликант x₁x₃ простой, поскольку удаление x₁ дает элементарную конъюнкцию x₃ истинную на наборах 001,011,101,111, в то время как функция f ложна на наборах 101 и 111.

Представление булевой функции в виде дизъюнкции всех простых импликантов этой функции называется сокращенной ДНФ булевой функции.

Исходной формой для получения сокращенной ДНФ является СДНФ булевой функции Применяя операции склеивания всевозможных соседний конъюнкций ранга n на первом этапе, ранга n-1 – на втором этапе и т.д., получим ДНФ, не имеющую ни одной пары соседних конъюнкций C и D ранга ч называются соседними, если возможно ич представление в виде

C=x_i*P, D=x_i * P

Где Р – элементарная конъюнкция ранга ч-1

Операция склеивания U и V дает элементарную конъюнкцию на основе формулы P=CVD=x₁x₂x₃.

Пример. Пусть

C=x₁x₂x₃x₄ , D=x₁x₂x₃x₄

Тогда

P=CVD= x₁x₂x₃

Тупиковый ДНФ булевой функции f(x₁,x₂,…,x_n) называется представление f в форме ДНФ, составленной из простых импликантов

f таким образом, что удаление любого простого импликанта из этой ДНФ нарушает правильность представления функции f.

Пример: Пусть f(X₁,X₂,X₃)=x₁x₂Vx₄x₃

Эта форма является тупиковой, поскольку, во – первых, x₁x₂ и x₄x₃ – простые импликанты f и во – вторых, отбрасывание любого из двух имликантов нарушает таблицу истиности, соответствиемую функции f.

В общем случае булева функция f(x₁,x₂,…,x_n) может иметь несколько тупиковых форм, одна или несколько из которых являются минимальными.

Простой импликант I_k называется ядерным (входит в ядро f(x₁,x₂,…,x_n)=V_j1^m I_j), если существует набор логически переменных b, на котором I_k(b)=1 а все остальные I_j(b)=0 (j≠k, j=1,…,m).

Пример:Сокращеная ДНФ некоторой функции имеет вид:

f(X₁,X₂,X₃,X₄)=X₁X₃X₄V X₂X₃X₄V X₁X₂X₃V X₁X₂X₄V X₁X₃X₄.

Ядерными являются импликанты X₁X₂X₃ и X₁X₂X₄ , поскольку импликант X₁X₂X₄ – истинность в наборе 1001.

Простой импликант I_k входит во все тупиковые днф функции f(x₁,x₂,…,x_n) тогда и только тогда, когда I_k входит в ядро f. Среди не ядерных импликантов f могут существовать такие, которые не входят ни в одну тупиковую форму. Импликант I_j не ни в одну тупиковую форму функции f, если

_jm

I_j → V I_j^m=1

^j1

где I₁^m,…,I_n^m – простые имликанты, состовляющие ядро f.

Для минимизации сднф функции f(x₁,x₂,…,x_n) необчодимо сделать следующие шаги:

1. Получить сокращеную ДНФ функции

^2. Выявить ядро функции

^3. Среди не ядерных имликантов выявить также, которые ни входят ни в одну тупиковую форму и исключить их из дальнейшего рассмотрения

^4. Выявить возможные вариантыудаления неядерных импликантов оставшихся после выполнения пункта 3, с целью получения соответствующей тупиковой формы

5.4. Метод Квайна

Для минимизации функции по методу Квайна необходимо сначала представить эту функцию в СДНФ. Получение сокращенной ДНФ путем склеивания соседних коньюнкций, т.е. первый шаг минимизации, осуществляется с помощью специальной таблицы. Шаги второй, третий и четвертый осуществляется с помощью так называемой импликантной матрицы.

Пример: Требуется минимизировать функцию

f(X₁,X₂,X₃,X₄)= X₁,X₂,X₃,X₄ V X₁,X₂,X₃,X₄ V X₁,X₂,X₃,X₄ V X₁,X₂,X₃,X₄ V VX₁,X₂,X₃,X₄ VX₁,X₂,X₃,X₄ V X₁,X₂,X₃,X₄ V X₁,X₂,X₃,X₄ V X₁,X₂,X₃,X₄ V VX₁,X₂,X₃,X₄

Для получения сокращенной ДНФ данной функции (первый шаг минимизации) заполним табл. 25. В графе 1 этой таблицы приведены десятичные номера и двоичные наборы аргументов, соответствующие единичным значениям функции, т.е. по сути дела, члены СДНФ функции.

Таблица 25

Члены СДНФ	При меча ние	Элементарные Конъюнкции 3 – го ранга	При меча ние	Элементарные Конъюнкции 2 – го ранга	Приме чание
0=0000 2=0010 3=0011 7=0111 8=1000 10=1010 12=1100 13=1101 14=1110 15=1111	+ + + + + + + + + +	00X0 – 0.2 X000 – 0.8 001X – 2.3 X010 – 2.10 0X11 – 3.7 X111 – 7.15 10X0 – 8.10 1X00 – 8.12 1X10 – 10.14 110X – 12.13 11X0 – 12.14 11X1 – 13.15 111X – 14.15	+ + ПИ-1 + ПИ-2 ПИ-3 + + + + + + +	X0X0 – 0,2,8,10 X0X0 – 0,8,2,10 1XX0 – 8,12,10,14 11XX – 12,13,14,15 11XX – 12,14,13,15	а – ПИ-4 а b – ПИ-5 с – ПИ-6 с

В графе 3 записаны элементарные конъюнкции 3 – го ранга, полученые в результате склеивания конъюнкции из графы 1. Для заполнения графы 3 сравниваем первый по порядку элемент графы 1 со вторым, третьим и так далее элементами этой графы. Затем второй элемент графы 1 сравниваем с третьим, четвертым и так далее элементами. Процесс продолжается до тех пор, пока не будут проверены все возможные попарные сочетания графы 1. Если две конъюнкции оказываются соседними, то они склеиваются в графе 3.

Например конъюнкции 0000 и 0010, с номерами 0 и 2 соответственно, в результате склеивания дают конъюнкцию 00X0 где знаком X обозначено место переменной, по которой осуществляется склеивание. В традиционной записи это означает конъюнкцию X₁X₂X₃X₄ и X₁X₂X₃X₄ на одну конъюнкцию X₁X₃X₄ .

В графе 2 отмечается значком + фак участия соответствующей конюнкции из графы 1 в одном из склеиваний. Как видим в нашем примере ни одна из элементарных конюнкций из СДНФ не является изолированой.

После заполнения графы 3 переходим к склеиванию конъюнкций, записаных в этой графе, причем результаты записываем в графе 5.

В графе 4 при помощи меток ПИ1, ПИ2 и ПИ3 отмечаем простые импликанты, соответствующие изолированным конъюнкциям 3 – го ранга 001X, 0X11 и X111 соответственно.

В графе 6 одинаковыми буквами помечены одинаковые конюнкции 2 – го ранга. Кроме того, видно что все три различающиеся конъюнкции 2 – ранга являются простыми импликантами, обозначеными как ПИ4, ПИ5 и ПИ6.

Таким образом, дальнейшее склеивание не возможно и, следовательно, совокупность простых импликантов ПИ1 – ПИ6 определяет сокращеную ДНФ минимизируемой функции:

f(X₁,X₂,X₃,X₄)= X₁,X₂,X₃ VX₁,X₃,X₄ VX₁,X₃,X₄ VX₂,X₄ VX₁,X₄ VX₁,X₃ .

Импликантную матрицу строим в виде табл. 26. Просматривая строку, соответствующую каждому простому импликанту, отмечаем все члены СДНФ, склеивание которых породило данный простой импликант.

Выявление ядра функции т.е. шаг второй минимизации, заключается в отыскание столбцов табл. 26, в которых встречается только одна метка, и в выписавынием соответствующих этим меткам простых импликантов (Горизонтальные линии 1 и 2 табл. 26.). В нашем случае ядро функции состоит из X0X0 и 11XX.

Шаг третий минимизации, т.е. отыскание неядерных импликантов, не входящих в тупиковые формы, заключается в отметке всех членов СДНФ, покрытых ядром функции (вертикальные линии 3 – 10 в табл. 26). В результате этих действий видим, что один простой импликант1XX0 не входит ни в одну тупиковую форму, так как метки, соответствующие этому импликанту, уже зачеркнуты вертикальными линиями 5, 6, 7, 9.

Таблица 26

Прост Импли кант	Члены СДНФ
0000 0010 0011 0111 1000 1010 1100 1101 1110 1111
001X 0X11 X111 X0X0 1XX0 11XX	V V V V 11 V V V V V V 1 V V V V V V V V 2 3 4 5 6 7 8 9 10

Следовательно, импликант 1XX0 исключается из дальнешего рассмотрения.

Шаг четвертый минимизации заключается в выборе минимального покрытия времени покрытия членов СДНФ 0011 и 0111 – импликантами 001X, 0X11 и X111.

Перебор всех возможных вариантов показывает, что лучшим является [0XX1]; это отмечено горизонтальной линией 11.

Таким образом, тупиковая форма

f(X₁,X₂,X₃,X₄)= X₁,X₃,X₄ VX2,X₄ V X₁,X₂

Является минимальной.

Метод Мак – Класки

Метод Мак – Класки – это усовершенствование метода квайна. Он отличается выполнением первого шага минимизации. Поскольку соседними являются элементарные конюнкции, отличающиеся только знаком инверсии над одной переменной, можно сгрупировать все члены СДНФ минимизируетфункции по количеству инверсий.

Пример. В предидущем примере члены СДНФ должны быть сгрупированы следующим образом:

0 – я группа – 0000;

1 – я группа – 0010, 1000;

2 – я группа – 0011, 1010, 1100;

3 – я группа – 0111, 1101, 1110;

4 – я группа – 1111.

Склеивание возможно только между элементами соседних групп.

Врезультате получаются группы:

0 – 1 – я группы – 00X0, X000

1 – 2 – я группы – 001X, X010, 10X0, 1X00

2 – 3 – я группы – 0X11, 1X10, 110X, 11X0

3 – 4 – я группы – X111, 11X1, 111X

Для полученных групп также справедливо утверждение о том, что склеивание возможно только между элементами соседних групп. Это обстаятельство используется при построении таблицы, аналогичной табл. 25. В остальном процедура минимизации совподает с методом Квайна.

6. Структурный синтез теории автоматов

6.1. Синтез на основе минимальных нормальных форм [1, 11]

Рассмотрим синтез комбинированых автоматов на основе представления переключательных функций в ДНФ и КНФ.

Метод Карио – Вейча

Все шаги минимизации осуществляются с помощью специальной таблицы. Например, для функции четырех переменных, принимающей истиное значение на двоичных наборах с десятичными номерами 0, 2, 3, 7, 8, 10, 12, 13, 14, 15 можно построить табл. 27. Номера конституент единицы рассматриваемой функции обведены кружками. Номера соседних конституент размещаются в соседних клетках таблицы. Кроме того, считается, что линия AB совподает с линией CD, а линии AC с линией BD, поэтому, например, клетки 0 и 2 также считаются соседними.

Все этапы минимизации, т.е. склеивание соседних конюнкций и выбор минимального покрытия заданной булевой функции простыми импликантами, осуществляется визуально с помощью табл. 27.

Таблица 27.

X₃X₄ X₃X₄ X₃X₄ X₃X₄

А B

X₁X₂ 0 1 3 2

X₁X₂ 4 5 7 6

X₁X₂ 12 13 15 14

X₁X₂ 8 9 11 10

C D

В рассматриваемом примере склеивание клеток 12, 13, 15 и 14 дает импликант X₁X₂ , склеивание клеток 0, 2, 8 и 10 → X₂X₄ и склеивание клеток 3 и 7 - X₁X₃ X₄ .

Таким образом минимальная ДНФ

f(X₁,X₂,X₃,X₄)= X₁,X₂VX₂,X₄ V X₁,X₃ X₄

Мнимизация совершенной коньюктивной нормальной формы булевой функции.

Целью минимизации СКНФ булевой функции является получение формы, эквивалентной исходной СКНФ, но содержащей минимальное число букв.

Все методы минимизации СДНФ применимы для минимизации СКНФ.

Пример. Минимизировать булеву функцию, принимающую ложные значения на наборах с номерами 3, 7, 8, 10, 11, 14, 15.

Запишем двоичные номера конституент нуля:

3 – 0011

7 – 0111

8 – 1000

10 – 1010

11 – 1011

14 – 1110

15 – 1111

Осуществим процедуру минимизации данной совокупности наборов формально одним из методов минимизации СДНФ и получаем минимальное покрытие в виде [10X0. XX11, 1X1X], т.е. минимальная КНФ имеет вид: f(X₁,X₂,X₃,X₄)= (X₁VX₂VX₄)(X₁VX₄)(X₁VX₃)

6.2. Синтез с учетом коэфицента объединения по входу

При синтезе комбинированых схем из реальных элементов на основе нормальных форм используются элементы типа И, НЕ, ИЛИ, И – НЕ, ИЛИ – НЕ.

При этом необходимо учитывать такие параметры элементов как

1. Количество входов называемое коэфицентом объединения по выходу;

2. Нагрузочную способность элементов;

3. Время задержки сигналов и другие.

Мы ограничемся только учетом коэфициента объединения по входу. Синтез в любом элементном базисе основан на представление требуемой булевой функции в виде композицииопераций выбраного элементного базиса.

Синтез на основе ДНФ

Рассмотрим пример синтеза для функции

f(X₁,X₂,X₃,X₄ X₅)= X₄ X₅VX₂X₅VX₁ X₄

Предпологается, что входные переменные как в прямом так и в инвентированом виде. Если имеется двухвходовые и трехвходовые элементы И и ИЛИ, тогда схема, реализуя эту функцию, строится непосредственно по формуле и выглядит так, как показано на рис 31а

а) б)

X₄ X₄ f

X₅ X₅

X₂ f X₂

X₅ X₃

X₁ X₁

X₄ X₄

Рис 31

Если имеются только двухвходовые элементы, то схема принимает вид рис 31.б

При синтезе на основе ДНФ можно использовать также элементы И – НЕ. Для этого ДНФ функция преобразуется в логическое представление на основе операции шеффера(/). Для рассмотреного выше примера преобразование в базис Шеффера можно получить следующим образом:

f(X₁,X₂,X₃,X₄ X₅)= X₄ X₅VX₂X₅VX₁ X₄ = X₄ X₅VX₂X₅VX₁ X₄= X₄ X₅&X₂X₅&X₁ X₄=

=(X₄/X₅)/ (X₂/X₅)/ (X₁/X₄)

Схемная реализация по полученой формуле на двух~ и трехкодовых элементов И – НЕ представлена на рис. 32, б. Отметим, что в любом случае для любого пути от входа к выходу число инвертирований сигнала должно быть четным.

а) б)

X₄ X₄ f

X₅ X₅

X₂ f X₂

X₅ X₃

X₁ X₁

X₄ X₄

Рис 32

Синтез на основе КНФ анологичны приемам для ДНФ в силу двойственности ДНФ и КНФ. Рассмотрим пример синтеза для функции

f(X₁,X₂,X₃,X₄)= (X₁VX₂VX₄)(X₁VX₄)(X₁VX₃)

а) б)

X₁ X₁

X₂ X₂

X₄ X₄

X₂ f X₂ f

X₄ X₄

X₁ X₁

X₃ X₃

Рис 33

В базисе 1 (И, ИЛИ, НЕ) эта функция реализуется схемой на рис 33, а. Эту функцию также удобно реализовать на элементах ИЛИ – НЕ. Для этого представим рассматриваемую функцию в базисе Пирса:

f(X₁,X₂,X₃,X₄)= (X₁VX₂VX₄)(X₁VX₄)(X₁VX₃)= (X₁VX₂VX₄)V(X₁VX₄)V(X₁VX₃)= (X₁↓X₂↓X₄)(X₁↓X₄)(X₁↓X₃)

Схема реализующая полученую формулу, приведена на рис. 33,б.

6.3. Синтез на мультиплексорах

Для синтеза комбинированных автоматов на мультиплексорах используется разложение булевой функции от n переменных по m переменным (m<n), где m – число адресных входов мультиплексора:

X_i, при b_i=0

гдеX_i^bi =

X_i, при b_i=1

Будена функция должна быть представлена в виде минимально ДНФ. В качестве адресных следует брать переменные, которые чаще всего встречаются в формуле, выражающей функцию: в этом случае остаточные функции f(b₁,b₂,…b_m,X_m,…,X_n)

Получаются наиболее простыми.

Рассмотрим пример синтеза для функции

f(X₁,X₂,X₃,X₄)= X₁,X₃ VX₁,X₂,X₄ VX₁,X₂,X₄ VX₁,X₃ X₄

Предположим, что используется мультиплексор с двумя адресными входами, т.е. m=2. В качестве адресных возьмем переменные X₁ и X₄ , т.е. a₁ = X₁ , a₂ = X₄ . Разложение формулы функций по этим переменным

f(X₁,X₂,X₃,X₄)= X₁X₄ f₀₀V X₁X₄ f₀₁V X₁X₄ f₁₀V X₁X₄ f₁₁ ,

где f₀₀=f(0, X_2,X₃,0)= X₂VX₃

f₀₁=f(0, X_2,X₃,1)= X₂VX₃

f₀₀=f(1, X_2,X₃,0)= 1

f₀₀=f(1, X_2,X₃,1)= 0

Каждая остаточная функция f a₁a₂ подается на информационный вход с адресом a₁a_{2 (}рис. 34)

A0 A1   A2   A3	MS

X₂

X₂

Рис.34

6.4. Троичное моделирования комбинированых автоматов

Задержки сигналов, возникающие в реальных логических элементах, вызывают задержку выходных сигналов комбиниционного автомата, а также являются причиной таких явлений, как статический и динамический риск сбоя.

Возможность появления ложного сигнала f(a) на выходе комбинационного автомата в результате мгновенной замене набора входных сигналов A набором B, причем f(A)=f(B), называется статическим риском сбоя.

Возможность многократных изменений сигнала на выходе комбинационного автомата и результате мгновенной замене набора входных сигналов A набором B, причем f(B)=f(A), называется динамическим риском сбоя. Динамический риск является следствием статического риска сбоя, поэтому задача выявления статического риска является актуальной.

Для обнаружения статического риска сбоя применяют троичное моделирование работы комбиниционного автомата. Для представления неопределенного, промежуточного значения двоичного сигнала, получающегося во время переходного процесса в схеме, берут число ½. Таким образом, от двоичного алфавита мы переходим к троичному алфавиту. Логические операции И, ИЛИ, НЕ при этом заменяются следующим образом:

aÙb=min (a, b) aVb=max (а, b)

a= a – 1

Пусть входной набор А=(а1,...,an) переходит в набор B=(b1,...,bn). Сформируем переходный набор А/B=(а1/b1,...,an/bn) где a1b1=ai если ai=bi ai/bi=1/2, если a1=b1. Тогда если выходной сигнал комбинированого автомата f(A)=f(B), a f(A/B)=1/2, то имеет место статистический риск сбоя при переходе от набора А к набору В.

Приводим алгоритм, выявляющем все троичные наборы сигналов, дающие f=1/2 на выходе схемы;

1. A:=(0,….,0)

2. Если A:=(1,….,1) то конец вычислений

3. A:=А+1/2

4. Если набор А не содержит координаты ½, то перейти к п.2

5. Вычислить f(A)

6. Если f(A)≠1/2 то перейти к п.3.

7. Отпечатать А и перейти к п.2

Выполнение п. 3 приведенного выше алгоритма осуществляется следующей процедурой:

1. i:=1

2. S:=a1+1/2

3. Если S<1+1/2, то ai:=S и конец работы процедуры

4. а1:=0

5. i:=1+1

6. Если 1<n то перейти к п. 2.

7. Конец работы процедуры

При программировании п.5 необходимо все элементы комбинированого автомата разбить на уровнях срабатывания: сначала выходные сигналы первого уровня, затем второго и т.д. до элементов последнего уровня.

6.5. Тестирование комбинационных автоматов

Для контроля и диагностики комбинационных автоматов применяют специальные тесты. Контролем устройства называют обнаружение неисправности в работе устройства.

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

В исправном состоянии комбинационный автомат реализует переключательную функцию f определенную на множестве входных воздействий X. Пусть G – много возможных неисправностей автомата, функцией неисправности k€G автомата называется функция f_k выполненная автоматом при наличии неисправности k. Функция неисправности f_k отличается от функции f исправного устройства.

Подмножество входных воздействий ТдÌX называется диагностическим тестом автомата, если для каждой пары неисправности b€G, для которой f≠fb найдется воздействие е€ТК, для которого f(e)≠ fb(e).

Подмножество ТдÌX называется диагностическим тестом автомата, если для каждой пары неисправностей n,b€G для которой fb≠ fk, найдется воздействие е€ТК для которого fb(е)≠ fk(е). Тест Т называется полным, если он локализует неисправности любой кратности в противном случае тест называется неполным.

Тест Т называется неизбыточным, если удаление из него любого воздействия е дает подмножество Т(е), не являющееся тестом.

Существует два подхода к построению тестов:

1. Для каждой неисправности b€G строится множество воздействий (е)b, проверяя эту неисправность.

2. Случайным образом генерируется множество воздействий S. Для каждого воздействия e€S, где SÌX, определяется множество

неисправностей (g)e, проверяемых воздействием е. Если S не является тестом, то в S добавляются новые воздействия до тех пор, пока S не станет тестом.

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

Применение второго подхода связано с анализом работы автомата при наличии некоторой неисправности g, если на его вход поступает некоторое воздействие е. Рассмотрим комбинационный автомат на рис. 35.

Введем обозначения s1,…, s6 переключательных функций на выходах логических элементов в узлах 1,…, 6 соответственно. Будем рассматривать только одиночные отказы логического типа. При одиночном отказе элемента 1 в узле 1 фиксируется устойчивое логическое значение «0» или «1», не зависящее от значений входных переменных х1, х2, х3, х4. Введем обозначение g01 для отказа в узле 1 типа «0» и g11 для отказа типа «1». Таким образом, нас интересует множество отказов

G=(g01, g02, g03, g0, g05, g06,

g11, g12, g13, g14, g15, g16).

Работа автомата может быть описана системой булевых функций: {s1=x2\/x3, s2=x2&s2, s3=s2\/s4\/s5, s4=s1&x4, s5=s6&x3, s6=x2\/x4}, причем функция автомата f(x1,x2,x3,x4)=s3.

Определим все неисправности, обнаруживаемые набором значений 1111 входных переменных х1, х2, х3, х4. Для этого составим таблицу.

Таблица 28

№	х1х2х3х4	s1 s2 s3 s4 s5 s6	f=s3
		1 1 1 0 0 1 «0»0 0 0 0 1 1 «0» 0 0 0 1 1 1 «0»0 0 1 1 1 1 «1»0 1 1 1 1 0 «1»1 1 1 1 0 0 «0»

Строчка 0 таблицы отражает логические значения в узлах исправного автомата, строчки 1,…, 6 – логические значения, получающиеся при фиксации каждого из узлов 1,…, 6 в состоянии, противоположном логическому значению для исправного автомата. Из табл. 28 видно, что воздействие е1=1111 обнаруживает подмножество неисправностей G1=(g01, g02, g03), поскольку при этих неисправностях выходное значение s3=f=0 отличается от значения s3=f=1 для исправного автомата.

Аналогичным способом можно установить, что воздействие е2=0001 обнаруживает подмножество неисправностей G2=(g11, g12, g13, g14, g15, g16), воздействие е3=0110 – подмножество G3=(g02, g03, g04), воздействие е4=1000 – подмножество G4=(g03, g05, g06).

Поскольку G1 U G2 U G3 U G4 = G, набор воздействий (е1, е2, е3, е4) является тестом. Этот тест – контролирующий.

7. СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТОВ С ПАМЯТЬЮ,

Дата добавления: 2015-10-23