Система многозначных алфавитов и функций

В основе многозначных алфавитов, используемых в логическом моделировании и генерации тестов, лежит классический двоичный алфавит $$\{0,1\}$$, образующий вместе с базисными логическими функциями булеву алгебру $$B_2$$ (далее, для простоты, двоичный алфавит и булеву алгебру будем обозначать как $$B_2$$). В данном алфавите достаточно хорошо моделируется статическое поведение логических схем для установившихся значений сигналов. Он используется в методах моделирования и генерации тестов, основанных на использовании конечных автоматов, некоторых ранних методах построения тестов, основанных на построении различающей функции и т.п. Однако двоичные модели не учитывают переходные процессы, возникающие при изменении значений входных сигналов и обусловленные временными характеристиками элементов. Кроме того, их использование вынуждает рассматривать отдельно исправную и неисправную схемы. В силу этого получили распространение алфавиты большей значности, некоторые из которых были рассмотрены в лекции 4.

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

Как было показано выше в лекции 4, моделирование в различных многозначных алфавитах, например, $$E_3$$и $$E_5$$требует разработки различных многозначных моделей логических элементов. То есть для каждого алфавита (и даже способа его кодирования) надо иметь свои модели логических элементов. Если мы хотим в системе иметь программы моделирования в различных алфавитах, то при таком подходе мы должны разработать для каждого алфавита свои модели всех логических элементов. Это создает серьезные проблемы при разработке систем моделирования и генерации тестов. Поэтому желательно построить единую систему многозначных моделей, которая позволяла бы проводить моделирование и генерацию тестов в основных многозначных алфавитах.

Универсальный 16-значный алфавит

Здесь используется более совершенная единая система многозначных алфавитов и функций, основанная на универсальной 16-значной логике $$B_{16}$$. В , на основе синтеза систематического подхода к построению многозначных логик и 16-значной логической системы, предложенной в , разработан единый подход, позволяющий на базе двоичного алфавита $$B_2 \lbrace 0,1\rbrace$$ получить основные многозначные логики, применяемые в методах построения тестов и моделирования.

Пусть $$A= \lbrace a_1,a_2,…,a_k\rbrace$$ - произвольный k-значный алфавит; $$F=(f_1,f_2,…,f_m)$$ - множество k-значных функций $$n$$ переменных, где $$f_i$$ для $$i=1,2,...,m$$ является отображением $$f_i:A^n\to A.$$ Совокупность $$A$$ и $$F$$ образует k-значную логику. Предложено два способа получения новой многозначной логики путем расширения некоторой исходной логики $$(A,F)$$ до более мощной по значности логики $$(\tilde{A},\tilde{F})$$. При первом способе новый алфавит $$\tilde{A}$$ получается как подмножество некоторого декартового произведения исходного алфавита $$A:\tilde{A}\subseteq A\times A\times…\times A.$$ Например, таким образом 4-значный алфавит $$B_4$$, получен из двоичного алфавита $$B_2: B_4=B_2\times B_2=\lbrace 00,01,10,11\rbrace =\lbrace 0,D^\prime,D,1\rbrace.$$ Второй способ заключается в том, что новый алфавит $$\tilde{A}$$ является некоторым множеством подмножеств элементов исходного алфавита: $$\tilde{A}\subseteq 2^A.$$ Произвольный элемент $$\tilde{a_i}$$ алфавита $$\tilde{A}$$ образуется как неупорядоченное подмножество элементов алфавита $$A:\tilde{a_i}=a_{i1}\cup a_{i2}\cup…\cup a_{il}$$, где $$a_{ij}\in A.$$ Например, таким способом 5-значный алфавит $$E_5=\lbrace 0,1,E,H,u \rbrace$$ получается из рассмотренного выше 4-значного алфавита $$B_4=\lbrace 0,D^\prime,D,1\rbrace.$$ При этом $$0=\{0\}$$ - статический ноль, $$1=\{1\}$$ - статическая единица, $$E=\lbrace 0\cup D^\prime \cup 1\rbrace$$ - изменение сигнала из $$0$$ в $$1$$, $$H=\lbrace 0\cup D\cup 1\rbrace$$ - изменение сигнала из $$1$$ в $$0$$, $$u=\lbrace 0\cup D^\prime \cup D\cup 1\rbrace$$ - неопределенное значение сигнала.

В качестве базового алфавита принимается 4-значный алфавит $$B_4=\lbrace 0,D^\prime,D,1\rbrace.$$ На его основе с помощью описанных выше методов строятся остальные многозначные алфавиты (причем не только большей значноcти). Элементы алфавита $$B_4$$имеют следующую интерпретацию: $$0(1)=00(11)$$ – значения сигналов равны; $$D^\prime(D)=01(10)$$ – значения сигналов различны в разных технических состояниях ДУ или в различные моменты времени. Таким образом, на основе алфавита $$B_4$$ строится вторым способом 16-значный алфавит $$B_{16}$$ (таблица 7.1). Данный алфавит является множеством всех подмножеств алфавита $$B_4:B_{16}=2^{B_4}.$$ 16-значный алфавит является базовым для задач построения тестов и моделирования в логических схемах, так как его элементы отображают все основные возможные ситуации, возникающие на линиях схемы.

Важнейшей компонентой является способ кодирования элементов многозначных алфавитов. Символы алфавита $$B_{16}$$ кодируются при помощи четырех двоичных переменных $$x^0,x^{D^\prime},x^D,x^1$$ (таблица 7.1). При этом каждому элементу алфавита $$B_{16}$$ ставится в соответствие упорядоченная совокупность переменных $$(x^0,x^{D^\prime},x^D,x^1)$$, являющаяся его кодом.

Значение	Элемент	Подмножество $$B_4$$	Кодирование
			$$x^0$$	$$x^{D^\prime}$$	$$x^D$$	$$x^1$$
0	$$\varnothing$$	$$\lbrace \varnothing \rbrace$$	0	0	0	0
1	1	{1}	0	0	0	1
2	D	{D}	0	0	1	0
3	G1	$$\lbrace D\cup 1 \rbrace$$	0	0	1	1
4	$$D^\prime$$	$$\lbrace D^\prime \rbrace$$	0	1	0	0
5	F1	$$\lbrace D^\prime\cup 1 \rbrace$$	0	1	0	1
6	$$D^*$$	$$\lbrace D^\prime\cup D \rbrace$$	0	1	1	0
7	D1	$$\lbrace D^\prime\cup D \cup 1\rbrace$$	0	1	1	1
8	0	{0}	1	0	0	0
9	C	$$\lbrace 0\cup 1 \rbrace$$	1	0	0	1
10	F0	$$\lbrace 0\cup D \rbrace$$	1	0	1	0
11	H	$$\lbrace 0\cup D \cup 1 \rbrace$$}	1	0	1	1
12	G0	$$\lbrace 0\cup D^\prime\rbrace$$	1	1	0	0
13	E	$$\lbrace 0\cup D^\prime\cup 1\rbrace$$	1	1	0	1
14	D0	$$\lbrace 0\cup D^\prime\cup D\rbrace$$	1	1	1	0
15	u	$$\lbrace 0\cup D^\prime\cup D \cup 1\rbrace$$	1	1	1	1

Любая из четырех переменных является признаком присутствия на линии соответствующего ей значения. Например, если переменная $$x^{D^\prime}=1$$ то линия $$x$$ может принимать значение $$D^\prime$$, в противном случае - $$x^{D^\prime}=0$$ - не может. Поэтому эти переменные называют характеристическими переменными. Отсюда следует, что код произвольного элемента алфавита $$B_16$$ является характеристическим вектором $$x=(x^0,x^{D^\prime},x^D,x^1).$$ Следует отметить, что данный способ кодирования многозначных алфавитов является обобщением дизъюнктивного метода кодирования троичного алфавита, представленного табл.4.6-4.7 в лекции 4.

Многозначные функции

Очевидно, что при определении новой многозначной логики $$(\tilde{A},\tilde{F}$$ основной проблемой является построение системы многозначных функций $$\tilde{F}$$ в новом алфавите $$\tilde{A}.$$ В том случае, если построенная система функций замкнута относительно $$\tilde{A}$$, то в совокупности с алфавитом она образует новую многозначную логику $$(\tilde{A},\tilde{F}.$$

Логические функции в алфавите $$B_{16}$$ обычно описываются двумя способами. Первый способ - табличный. Он применяется для описания функционирования простых логических вентилей. Например, для вентилей $$И, НЕ$$ табличные модели представлены в таблица 7.2). Табличные модели для других простых вентилей имеют аналогичную форму. Например, таблица 7.4 представляет многозначную модель элемента $$y=a\oplus b.$$

Второй способ, как было показано в лекции 4, заключается в задании многозначной функции с помощью нескольких двоичных компонент. Многозначная модель на основе кодирования 16-значного алфавита, которая использует 4-компонентное представление. Показано, что поведение многозначной функции $$f(X)(X=(x_1,x_2,…,x_n)),x_i=(x_i^0,x_i^{D^\prime},x_i^D,x_i^1))$$ для $$i=\overline{1,n}$$ может быть описано с помощью четырех булевых функций $$f^0(X^0,X^{D^\prime},X^D,X^1), f^{D\prime}(X^0,X^{D^\prime},X^D,X^1), f^D(X^0,X^{D^\prime},X^D,X^1), f^1(X^0,X^{D^\prime},X^D,X^1),.$$ Данные функции являются компонентами характеристического вектора $$f=(f^0,f^{D^\prime},f^D,f^1$$, соответствующего коду значения многозначной функции $$f(X).$$ Характеристические функции $$f^0,f^{D^\prime},f^D,f^1$$ для базисных вентилей $$И, ИЛИ, НЕ$$ представлены в табл.7.5. Для произвольной логической функции они могут быть получены с помощью ориентированных булевых дифференциалов.

И	B	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
a		$$\varnothing$$	1	D	G1	$$D^\prime$$	F1	$$D^*$$	D1	0	C	F0	H	G0	E	D0	u
0	$$\varnothing$$	0	0	0	0	0	0	0	0	8	8	8	8	8	8	8	8
1	1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	D	0	2	2	2	8	10	10	10	8	10	10	10	8	10	10	10
3	G1	0	3	2	3	12	15	14	15	8	11	10	11	12	15	14	15
4	$$D^\prime$$	0	4	8	12	4	4	12	12	8	12	8	12	12	12	12	12
5	F1	0	5	10	15	4	5	14	15	8	13	10	15	12	13	14	15
6	$$D^*$$	0	6	10	14	12	14	14	14	8	14	10	14	12	14	14	14
7	D1	0	7	10	15	12	15	14	15	8	15	10	15	12	15	14	15
8	0	8	8	8	8	8	8	8	8	8	8	8	8	8	8	8	8
9	C	8	9	10	11	12	13	14	15	8	9	10	11	12	13	14	15
10	F0	8	10	10	10	8	10	10	10	8	10	10	10	8	10	10	10
11	H	8	11	10	11	12	15	15	14	8	11	10	11	12	15	14	15
12	G0	8	12	8	12	12	12	12	12	8	12	8	12	12	12	12	12
13	E	8	13	10	15	12	13	14	15	8	13	10	15	12	11	14	15
14	D0	8	14	10	14	12	14	14	14	8	14	10	14	12	14	14	14
15	U	8	15	10	15	12	15	14	15	8	15	10	15	12	15	14	15

НЕ	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
a	$$\varnothing$$	1	D	G1	$$D^\prime$$	F1	$$D^*$$	D1	0	C	F0	H	G0	E	D0	u
$$\overline{a}$$	0	8	4	12	2	10	6	14	1	9	5	13	3	11	7	15

Кроме прямых многозначных функций, описанных выше, в диагностике ДУ (прежде всего в генерации тестов) применяются также обратные многозначные функции. Обратные функции позволяют вычислить значение аргумента по заданным значениям функции и второго аргумента (как правило, их определяют для функций двух переменных). Для них, как и для прямых функций, существует две формы описания: табличная и покомпонентная. Пример табличной модели приведен в табл.7.6, где задана обратная функция для вентиля $$И: f =ab.$$ В табл.7.7 представлены обратные характеристические функции основных вентилей $$И, ИЛИ, НЕ.$$

В силу симметричности обратные функции для аргумента $$b$$ имеют идентичный вид и получаются заменой переменных $$b$$ на $$a.$$ Пример использования обратных многозначных функций в генерации тестов представлен в лекции 20.

$$y=a\oplus b$$		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
		$$\varnothing$$	1	D	G1	$$D^\prime$$	F1	$$D^*$$	D1	0	C	F0	H	G0	E	D0	u
0	$$\varnothing$$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	0	8	4	12	2	10	6	14	1	9	5	13	3	11	7	15
2	D	0	4	8	12	1	5	9	13	2	6	10	14	3	7	11	15
3	G1	0	12	12	12	3	15	15	15	3	15	15	15	3	15	15	15
4	$$D^\prime$$	0	2	1	3	8	10	9	11	4	6	5	7	12	14	13	15
5	F1	0	10	5	15	10	10	15	15	5	15	5	15	15	15	15	15
6	$$D^*$$	0	6	9	15	9	15	9	15	6	6	15	15	15	15	15	15
7	D1	0	14	13	15	11	15	15	15	7	8	15	15	15	15	15	15
8	0	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
9	C	0	9	6	15	6	15	6	15	9	9	15	15	15	15	15	15
10	F0	0	5	10	15	5	5	15	15	10	15	10	15	15	15	15	15
11	H	0	13	14	15	7	15	15	15	11	15	15	15	15	15	15	15
12	G0	0	3	3	3	12	15	15	15	12	15	15	15	15	15	15	15
13	E	0	11	7	15	14	15	15	15	13	15	15	15	15	15	15	15
14	D0	0	7	11	15	13	15	15	15	14	15	15	15	15	15	15	15
15	u	0	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15

f	$$f^0$$	$$f^{D\prime}$$	$$f^D$$	$$f^1$$
ab	$$a^0\vee b^0 \vee a^{D^\prime}b^D\vee a^Db^{D^\prime}$$	$$a^{D^\prime}b^1\vee a^1b^{D^\prime}\vee a^{D^\prime}b^{D^\prime}$$	$$a^Db^1\vee a^{1bD} \vee a^Db^D$$	$$a^1b^1$$
$$a\vee b$$	$$a^0b^0$$a0b 0	$$a^{D^\prime}b^0 \vee a^0b^{D^\prime}\vee a^{D^\prime}b^{D^\prime}$$	$$a^Db^0\vee a^{0bD} \vee a^Db^D$$	$$a^1\vee b^1\vee a^{D^\prime}b^D \vee a^Db^{D^\prime}$$
$$\overline{a}$$	$$a^1$$	$$a^D$$	$$a^{D^\prime}$$	$$a^0$$

И	F	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
A		$$\varnothing$$	1	D	G1	$$D^\prime$$	F1	$$D^*$$	D1	0	C	F0	H	G0	E	D0	u
0	$$\varnothing$$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	D	0	0	3	3	0	0	3	3	12	12	15	15	12	12	15	15
3	G1	0	1	3	3	4	5	7	7	12	13	15	15	12	13	15	15
4	$$D^\prime$$	0	0	0	0	5	5	5	5	10	10	10	10	15	15	15	15
5	F1	0	1	2	3	5	5	7	7	10	11	10	11	15	15	15	15
6	$$D^*$$	0	0	3	3	5	5	7	7	14	14	15	15	15	15	15	15
7	D1	0	1	3	3	5	5	7	7	14	15	15	15	15	15	15	15
8	0	0	0	0	0	0	0	0	0	15	15	15	15	15	15	15	15
9	C	0	1	2	3	4	5	6	7	15	15	15	15	15	15	15	15
10	F0	0	0	3	3	0	0	3	3	15	15	15	15	15	15	15	15
11	H	0	1	3	3	4	5	7	7	15	15	15	15	15	15	15	15
12	G0	0	0	0	0	5	5	5	5	15	15	15	15	15	15	15	15
13	E	0	1	2	3	5	5	7	7	15	15	15	15	15	15	15	15
14	D0	0	0	3	3	5	5	7	7	15	15	15	15	15	15	15	15
15	u	0	1	3	3	5	5	7	7	15	15	15	15	15	15	15	15

F	$$a^0$$	$$a^{D\prime}$$	$$a^D$$	$$a^1$$
ab	$$f^0(b^0\vee b^{D^\prime} \vee b^D\vee b^1$$	$$f^0(b^0\vee b^D)\vee f^{D^\prime}(b^{D^\prime}\vee b^1)$$	$$f^0(b^0\vee b^{D^\prime}\vee f^D(b^D\vee b^1)$$	$$f^0b^0\vee f^{D^prime}b^{D^\prime}\vee f^Db^D\vee f^1b^1$$
$$a\vee b$$	$$f^0b^0\vee f^{D^\prime}b^{^D\prime}\vee f^Db^D\vee f^1b^1$$	$$ f^{D^\prime}(b^0\vee b^{D^\prime})\vee f^1(b^D\vee b^1)$$	$$f^D(b^0\vee b^D)\vee f^1(b^{D^\prime}\vee b^1$$	$$f^1(b^0 b^{D^\prime}\vee b^D\vee b^1)$$
$$\overline a$$	$$f^1$$	$$f^D$$	$$f^{D^\prime}$$	$$f^0$$

Основные многозначные алфавиты как подмножества универсального 16-значного алфавита

Наиболее широко применяемый на практике алфавит $$E_3$$ образует следующее подмножество алфавита $$B_{16}:0=\lbrace 0\rbrace (\text{код }1000), 1=\lbrace 1\rbrace (\text{код }0001), u=\lbrace 0\cup D^\prime \cup D \cup 1\rbrace (\text{код }1111).$$ Рассмотрим пример вычисления функции $$f=a \vee b$$ в троичном алфавите, используя характеристические функции, приведенные в Табл.7.5.

Пусть $$a=1:a^0=0, a^{D^\prime}=0,a^D=0,a^1=1$$, и $$b=0:b^0=1, b^{D^\prime}=0,b^D=0,b^1=0$$, тогда получаем

$$f^0=0\cdot 1=0\\ f^{D^\prime}=0\cdot 1 \vee 0 \cdot 0 \vee 0 \cdot 0=0\\f^D=0 \cdot 1 \vee 0 \cdot 0 \vee 0 \cdot 0 =0\\f^1=1 \vee 0 \vee 0 \cdot 0 \vee 0 \cdot 0 =1$$

Таким образом, согласно кодированию алфавита $$B_{16}$$ (Табл.7.1) код $$f^0=0, f^{D^\prime}=0,f^D=0,f^1=1$$ определяет значение $$f=1$$, что соответствует таблице истинности функции $$ИЛИ$$ в троичном алфавите.

Алфавит $$E_5$$, являющийся расширением алфавита E3, определяется следующим подмножеством 16-значного алфавита:

$$0=\lbrace 0\rbrace (\text{код }1000), 1=\lbrace 1\rbrace (\text{код }0001),E=\lbrace 0 \cup D^\prime \cup 1 \rbrace (\text{код }1101),\\H=\lbrace 0 \cup D \cup 1 \rbrace (\text{код }1011), u=\lbrace 0\cup D^\prime \cup D \cup 1\rbrace (\text{код }1111)$$

Рассмотрим пример вычисления функции $$f=a \vee b$$ в 5-значном алфавите, используя характеристические функции, приведенные в Табл.7.5.

Пусть $$a=0:a^0=1, a^{D^\prime}=0,a^D=0,a^1=0$$, и $$b=E:b^0=1, b^{D^\prime}=1,b^D=0,b^1=1$$, тогда получаем

$$ f^0=1 \cdot 1=1\\ f^{D^\prime}=0 \cdot 1 \vee 1 \cdot 1 \vee 0 \cdot 1=1\\ f^D=0 \cdot 1 \vee 1 \cdot 0 \vee 0 \cdot 0 =0\\ f^1=0 \vee 1 \vee 0 \cdot 1 \vee 0 \cdot 0 =1$$

То есть, согласно кодированию алфавита $$B_{16}$$ код $$f^0=1, f^{D^\prime}=1,f^D=0,f^1=1$$ определяет значение $$f=E,$$ что соответствует таблице истинности функции $$ИЛИ$$ в 5-значном алфавите.

На рис.7.2 представлена алгебраическая структура алфавитов $$E_3$$ и $$E_5.$$ В силу построения рассмотренные алфавиты являются частично упорядоченными подмножествами и образуют структуры типа верхняя полурешетка

Элементы	Интерпретация
$$0 \times 0 \times 0$$	Статический $$0$$
$$1 \times 1 \times 1 $$	Статическая $$1$$
$$0 \times u \times 1$$	Переход $$0 \to 1$$
$$1 \times u \times 0$$	Переход $$1 \to 0$$
$$0 \times u \times 0$$	Статическое $$0$$-состязание
$$1 \times u \times 1$$	Статическое $$1$$-состязание

Элементы	Интерпретация
$$0 \times 0 \times 0$$	Статический $$0$$
$$1 \times 1 \times 1 $$	Статическая $$1$$
$$0 \times E \times 1$$	Переход $$0 \to 1$$
$$1 \times H \times 0$$	Переход $$1 \to 0$$
$$0 \times u \times 0$$	Статическое $$0$$-состязание
$$1 \times u \times 1$$	Статическое $$1$$-состязание
$$0 \times H \times 1$$	Динамическое $$1$$-состязание
$$1 \times E \times 0$$	Динамическое $$0$$-состязание

Отметим, что 6-значный и 8-значный алфавиты $$H_6$$ и $$H_8$$ соответственно, используемые в методах анализа состязаний сигналов также могут быть получены из алфавита $$B_{16}$$, так как определяются следующими подмножествами: $$H_6 \subseteq B_2 \times E_3 \times B_2, H_8 \subseteq B_2 \times E_5 \times B_2.$$ При этом, как было показано в разделе 2.9.2, моделирование с анализом на состязания выполняется на трех наборах: текущем основном в алфавите $$B_2$$, на промежуточном наборе: при использовании $$H_6$$ - в алфавите $$E_3$$ (при использовании $$H_8$$ - в алфавите $$E_5$$) следующем основном наборе в алфавите $$B_2.$$ Такой способ моделирования с использованием трех наборов соответствует математической структуре алфавитов $$H_6$$ и $$H_8.$$ Результаты моделирования интерпретируются в соответствии с таблицами 7.8 и 7.9 соответственно. Отметим, что алфавит $$H_8$$ позволяет обнаруживать динамические состязания. В алгоритмах анализа состязаний иногда используется также алфавит $$H_9$$, содержащий все элементы алфавита $$H_8$$и элемент $$u \times u \times u$$, соответствующий неопределенному состоянию.

Алфавит $$T_6$$, наиболее широко применяемый в методах генерации тестов (он будет дальше использоваться в лекции является подмножеством 16-значного алфавита:

$$\varnothing=\lbrace \varnothing \rbrace (\text{код }0000), 0=\lbrace 0\rbrace (\text{код }1000), 1=\lbrace 1\rbrace (\text{код }0001),\\ D=\lbrace D \rbrace (\text{код }0010),D^\prime=\lbrace D^\prime \rbrace (\text{код }0100), u=\lbrace 0\cup D^\prime \cup D \cup 1\rbrace (\text{код }1111)$$

Рассмотрим пример вычисления функции $$f=a \vee b$$ в 6-значном алфавите, используя характеристические функции, приведенные в Табл.7.5. Пусть $$a=D:a^0=0, a^{D^\prime}=0,a^D=1,a^1=0$$, и $$b= D^\prime:b^0=0, b^{D^\prime}=1,b^D=0,b^1=0$$, тогда получаем

$$ f^0=0 \cdot 0=0\\ f^{D^\prime}=0 \cdot 0 \vee 0 \cdot 1 \vee 0 \cdot 1=0\\ f^D=1 \cdot 0 \vee 0 \cdot 0 \vee 1 \cdot 0 =0\\ f^1=0 \vee 0 \vee 1 \cdot 1 \vee 0 \cdot 0 =1$$

То есть, согласно кодированию алфавита $$B_{16}$$ (Табл.7.1) код $$f^0=0, f^{D^\prime}=0,f^D=0,f^1=1$$ определяет значение $$f=1$$, что соответствует таблице истинности функции $$ИЛИ$$ в алфавите $$T_6.$$

Широкое применение в методах генерации тестов находит также алфавит $$T_{10}$$, являющийся подмножеством 16-значного алфавита. Он определяется следующим его подмножеством:

$$\varnothing=\lbrace \varnothing \rbrace (\text{код }0000), 0=\lbrace 0\rbrace (\text{код }1000), 1=\lbrace 1\rbrace (\text{код }0001),\\ D=\lbrace D \rbrace (\text{код }0010),D^\prime=\lbrace D^\prime \rbrace (\text{код }0100), G0=\lbrace 0 \cup D^\prime \rbrace (\text{код }1100), \\ F0=\lbrace 0 \cup D \rbrace (\text{код }0101), G1=\lbrace D \cup 1 \rbrace (\text{код }0011), F1=\lbrace D^\prime \cup 1 \rbrace (\text{код }1010), \\ u=\lbrace 0\cup D^\prime \cup D \cup 1\rbrace (\text{код }1111)$$

Рассмотрим пример вычисления функции $$f=a \vee b$$ в 10-значном алфавите, используя характеристические функции, приведенные в Табл.7.5. Пусть $$a=D:a^0=0, a^{D^\prime}=0,a^D=1,a^1=0$$, и $$b= G1:b^0=0, b^{D^\prime}=0,b^D=1,b^1=0$$, тогда получаем

$$ f^0=0 \cdot 0=0\\ f^{D^\prime}=0 \cdot 0 \vee 0 \cdot 0 \vee 0 \cdot 0=0\\ f^D=1 \cdot 0 \vee 0 \cdot 1 \vee 1 \cdot 1 =1\\ f^1=0 \vee 1 \vee 1 \cdot 0 \vee 0 \cdot 1 =1$$

Тогда, согласно кодированию алфавита $$B_{16}$$(Табл.7.1), код $$f^0=0, f^{D^\prime}=0,f^D=1,f^1=1$$ определяет значение $$f=G1$$, что соответствует таблице истинности функции $$ИЛИ$$ в алфавите $$T_{10}.$$ В генерации тестов используется также и 12-значный $$T_{12}=\lbrace \varnothing, 0,1,D^\prime,D,F0,F1,G0,G1,D^*,C,u \rbrace $$ алфавит, также являющиеся расширением алфавита $$T_6.$$

Из выше сказанного можно сделать заключение, что при методе кодирования, используемом в алфавите $$B_{12}$$, описание поведения многозначных функций с помощью упорядоченного множества характеристических функций $$f^0, f^{D^\prime},f^D,f^1$$ может быть использовано в методах генерации тестов и моделирования логических схем, базирующихся на применении основных многозначных алфавитов. С этой точки зрения описанная 16-значная логика $$(B_{16}(f^0, f^{D^\prime},f^D,f^1))$$ является универсальной математической моделью для методов генерации тестов и моделирования.

Алгебраическая структура многозначных алфавитов

Показано, что рассмотренный 16-значный алфавит $$B_{16}$$образует булеву алгебру, представленную на Рис.7.1. Используемый метод построения позволяет утверждать, что основные многозначные алфавиты, применяемые в методах генерации проверяющих тестов и моделирования ДУ, являются частично упорядоченными подмножествами $$B_{16}.$$ Так, например, алфавиты $$E_3$$и $$E_5$$образуют структуры типа верхняя полурешетка, которые не содержат наименьший элемент. Эти структуры представлены на рис.7.2а и рис.7.2б. Если к алфавиту $$E_3$$добавить наименьший элемент $$\varnothing$$, то получим алфавит $$C_4$$, также представленный на рис.7.2в, который используется при моделировании шинных структур. Знание алгебраической структуры основных многозначных алфавитов позволяет строить с помощью алгебраических операций новые алфавиты, необходимые при моделировании или генерации тестов схем, выполненных по какой либо новой технологии. Например, на рис.7.2г, рис.7.2д представлены алфавиты $$L_1$$ и $$L_2$$, которые получены из алфавита $$C_4$$и широко используются при моделировании шинных структур.

(рис 7.1) Алгебраическая структура B_16 (рис 7.2) Алгебраическая структура многозначных алфавитов

Моделирование шинных структур

Моделирование схем, содержащих тристабильные элементы, представляет особый интерес. Корректное моделирование таких схем даже в статике требует 3-значного алфавита $$C_3=\lbrace \varnothing,0,1 \rbrace$$, где $$\varnothing$$-представляет состояние высокого импеданса. При моделировании переходных процессов используют, как минимум, 4-значный алфавит $$C_4=\lbrace \varnothing,0,1,u \rbrace$$, где $$u$$ интерпретируется как неопределенное значение ($$0$$ или $$1$$ или $$0$$). Наибольшие трудности вызывает, как правило, моделирование шинных структур, одна из которых представлена на рис.7.3.

(рис 7.3) Шинная структура.

Таблица 7.10

C/X	$$\varnothing$$	0	1	u
$$\varnothing$$	u	$$\varnothing$$	$$\varnothing$$	u
0	u	$$\varnothing$$	0	u
1	u	$$\varnothing$$	1	u
u	u	$$\varnothing$$	u	u

Таблица 7.11

a/b	$$\varnothing$$	0	1	U
$$\varnothing$$	$$\varnothing$$	0	1	U
0	0	0	u	U
1	1	u	1	U
u	u	u	u	U

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

Поставим в соответствие символу $$\varnothing$$ в принятом нами методе кодирования код-$$0000.$$ Тогда 4-значный алфавит $$C_4=\lbrace \varnothing,0,1u\rbrace$$ образует следующее подмножество

$$B_{16}:\varnothing=\lbrace \varnothing \rbrace (\text{код }0000), 0=\lbrace 00\rbrace (\text{код }1000),\\ 1=\lbrace 11\rbrace (\text{код }0001), u=\lbrace 00\cup 01 \cup 10 \cup 11\rbrace.$$

На основании табл.7.10 с учетом принятого метода кодирования получены функции $$f^0, f^{D^\prime},f^D,f^1$$ для тристабильного элемента, которые приведены в табл.7.12.

	$$f^0$$	$$f^{D^\prime}$$
Тристабильный элемент	$$ \overline{c^0}\, \overline{c^{D^\prime}}\,\overline{c^D}c^{1x0} \vee c^0 c^{D^\prime}c^{Dc1} \vee \overline{c^0} \,\overline{c^{D^\prime}}\,\overline{c^D}\,\overline{c^1}$$	$$ \overline{c^0}\, \overline{c^{D^\prime}} \,\overline{c^D}c^{1x0} x^{D^\prime}x^{Dx1} \vee c^0 c^{D^\prime}c^{Dc1} \vee \overline{c^0} \,\overline{c^{D^\prime}}\,\overline{c^D}\,\overline{c^1}$$
Шина	$$a^0 (\overline{a^{D^\prime}}\, \overline{a^D}\, \overline{a^1} \vee a^{D^\prime}a^Da^1) \vee \overline{a^0}\, \overline{a^{D^\prime}}\, \overline{a^D}\, b^0 $$	$$ \overline{a^0}\, \overline{a^{D^\prime}} \,\overline{a^D}a^{1b0} \vee a^0a^{D^\prime}a^{Da1b1} \vee a^0 a^{D^\prime}a^{Da1} \vee \overline{a^0} \,\overline{a^{D^\prime}}\,\overline{a^D}\,\overline{a^1} \vee b^0b^{D^\prime}b^Db^1$$
	$$f^D$$	$$f^1$$
Тристабильный элемент	$$ \overline{c^0}\, \overline{c^{D^\prime}} \,\overline{c^D}c^{1x0} x^{D^\prime}x^{Dx1} \vee c^0 c^{D^\prime}c^{Dc1} \vee \overline{c^0} \,\overline{c^{D^\prime}}\,\overline{c^D}\,\overline{c^1}$$	$$ \overline{c^0}\, \overline{c^{D^\prime}}\,\overline{c^D}c^{1x1} \vee c^0 c^{D^\prime}c^{Dc1} \vee \overline{c^0} \,\overline{c^{D^\prime}}\,\overline{c^D}\,\overline{c^1}$$
Шина	$$ a^0\, \overline{a^{D^\prime}} \,\overline{a^D}a^{1b1} \vee \overline{a^0}\, \overline{a^{D^\prime}} \, \overline{a^D}a^{1b0} \vee a^0 a^{D^\prime}a^{Da1} \vee \overline{a^0} \, \overline{a^{D^\prime}} \, \overline{a^D} \, \overline{a^1} b^0b^{D^\prime}b^Db^1$$	$$a^1 (\overline{a^0}\,\overline{a^{D^\prime}}\, \overline{a^D}\, \vee a^0a^Da^1) \vee \overline{a^{D^\prime}}\, \overline{a^D}\, \overline{a^1} b^1 $$

Как уже отмечалось, выходы тристабильных элементов обычно подключаются к шине, модель которой в алфавите $$C_4$$представлена в табл.7.11. Если все устройства отключены, то согласно этой таблице шина находится в состоянии высокого импеданса. Это не всегда соответствует действительности, так как при некоторых технологиях в таком случае шина сохраняет предыдущее значение. То есть в этом случае значение $$\varnothing$$ на шине скорее является признаком сохранения предыдущего значения. На основании табл.7.11 для принятого метода кодирования получены функции $$f^0, f^{D^\prime},f^D,f^1$$, которые представлены в табл.7.12.

Моделирование МОП-схем требует введения специальных приоритетов ("сил"). При этом с линией схемы обычно связывается два параметра $$(v,s)$$, где $$v \in C_4$$ соответствует напряжению, а "сила" $$s\in S_n=\lbrace 0,1,2,…,n\rbrace$$ соответствует току или заряду [53]. Введение "силы" позволяет корректно моделировать на логическом уровне специальные элементы (типа "сборка" и т.п.), которые традиционно моделировались на уровне электронных схем. Следуя , в этом случае алфавит моделирования можно представить в виде $$L_n=L_0^\prime \uparrow L_1^\prime \uparrow … L_n^\prime$$, где $$ L_i^\prime =C_4 \times i$$ и $$\uparrow$$ представляет операцию конкатенации, при которой элементы в алфавите $$\lbrace \varnothing,i \rbrace \in C_4 \times i$$ и $$\lbrace u,i+1 \rbrace \in C_4 \times (i+1)$$ "стягиваются" в $$(u,1+1).$$ На рис.7.2 д представлены диаграммы Хассе $$L_n$$ для $$n=0,1,2.$$ В настоящее время наиболее распространенными являются алфавиты типа $$L_2.$$ При этом высший приоритет ($$s=0$$) соответствует линиям схемы, связанным с питанием или землей. Выходам логических элементов обычно присваивается следующий приоритет ($$s=1$$). И самый низкий приоритет ($$s=2$$) имеют элементы, у которых сигналы хранятся на емкостях. Как правило, наибольшие трудности вызывает моделирование специальных элементов типа "сборка". Математически моделирование "сборки" сводится к операции $$\#$$ - нахождению наименьшей верхней грани в $$L_n$$. Например, $$(v,s)=\#((1,1),(\varnothing,2),(\varnothing,2))=(1,1).$$

Функции $$f^0, f^{D^\prime},f^D,f^1$$ используются при моделировании логических элементов для вычисления параметра $$v.$$ "Сила" $$s$$ определяется типом элемента и применяемой технологией. Существуют различные модификации многозначных алфавитов, являющихся подмножествами $$L_2.$$ Интересным и важным для практики представляется 9-значный алфавит. Этот алфавит получается из $$L_2$$удалением элемента $$(0,2)$$ и имеет структуру несколько отличную от $$L_2$$, которая обусловлена технологией производства рассматриваемых схем.

Представленные выше модели тристабильного элемента и шины используют четыре компоненты $$f^0, f^{D^\prime},f^D,f^1.$$ Но при моделировании в алфавитах $$C_4,L_n$$ достаточно использовать только две компоненты и не все термы $$f^0,f^1.$$ При этом модели тристабильного элемента и шины существенно упрощаются. Для тристабильного элемента в этом случае получаем $$f^0=\overline{c^0}c^{1x0} \vee c^{0c1} \vee c^0c^1$$ и $$f^1=\overline{c^0}c^1 \vee x^1 \vee c^{0c1} \vee \overline{c^0}\, \overline{c^1}.$$ Аналогично для шины имеем $$f^0=a^0 \vee b^0,f^1=a^1 \vee b^1.$$

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

Ключевые термины:

Многозначный алфавит – множество символов, отражающих распределение сигналов в схеме.

Многозначная функция – определяется на произвольном $$k$$-значном алфавите $$A=\lbrace a_1,a_2,…,a_k \rbrace$$ как отображение $$f_i:A^n \to A$$, где $$n$$ –число аргументов функции.

Краткие итоги

Данная лекция посвящена проблемам моделирования логических схем в многозначных алфавитах.

В разделе 7.1 на основе двоичного алфавита вводится универсальный 16-значный алфавит, который включает в себя основные многозначные алфавиты, используемые в логическом моделировании и генерации тестов. Рассмотрен два основных способа построения алфавитов большей значности :

как подмножество некоторого декартова произведения исходного алфавита;

как множество подмножеств исходного алфавита.

В разделе 7.2 рассмотрено построение многозначных функций на базе:

табличных моделей;

компонентных двоичных моделей.

В разделе 7.3 показано, что основные многозначные алфавиты, используемые в логическом моделировании и генерации тестов, являются подмножествами универсального 16-значного алфавита.

Раздел 7.4 посвящен исследованию алгебраической структуры основных многозначных алфавитов.

В разделе 7.5 описывается моделирование шинных структур с использованием4-значного алфавита.

Вопросы и упражнения

Где и почему используются многозначные алфавиты ?

Какие два основных способа построения алфавитов большей значности из исходного алфавита вы знаете?

Опишите физический смысл символов универсального 16-значного алфавита.

Зачем нужны многозначные функции?

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

Опишите табличное представление многозначной функции.

Опишите компонентное представление многозначной функции.

Каким образом получаются основные многозначные алфавиты, используемые при моделировании и генерации тестов, из универсального 16-значного алфавита?

Опишите алгебраическую структуру основных многозначных алфавитов.

Какой алфавит используется для моделирования шинных структур?

Опишите табличные многозначные модели элементов шинных структур.

Опишите компонентные модели элементов шинных структур.