Алгоритми мінімального покриття графу.

Етап_1:

Розглядають і-ту вершину, і визначають сумісну j-ту вершину. Номер якої є максимальними серед номерів сумісних вершин.

(і є {1, N-1} (інферт.)), де N –кількість вершин графа.

Етап_2:

Розглядають дугу (Vi, Vj), якщо d вих. (Vi)>1, і d вх (Vj)>1, то дугу q (Vi, Vj) виключають з цього графу.

Якщо dвих (Vi)>1, i d вх (Vj)=1, то дугу h (Vi, Vj) залишають.

Етап_3:

d вих (Vi)=1, то на шляху немає дуги типу q, то дугу виключають, а також дугу типу h, що була відмічені на етапі_2.

Етап_4:

i=j, то повторюють етапи від 1 до 3, до того часу поки j не дорівнюватиме кінцевій вершині. Шляхи фіксують у вигляді послідовностей j.

Етап_5:

Повторюються етапи з 1 по 4 доти, поки в побудованому шляху не залишуться дуги типу q i h.

Вираз на обчислюванні вхідних даних, що дають змогу реалізувати і-тий шлях яка забезпечує переключанню в потрібному напрямку.

Моделі цифрових пристроїв та їх несправності.

Дві області моделювання.

Різні рівні проектування для кожної області.

Рівні	області
	Поведінкова	Структурна	Фізична
Системний	Систематичні специфікацвї	Блоки	Кристал
МРП	Специфікацій мов регістрових передач	Регістри	Мікрокомірки
Логічний	Булеві функції	Логічні вентелі	Стандартні комірки
Схемний	Диференціальні рівняння	Транзистори	Маски

При побудові моделей цифрових пристроїв розрізняють три підходи:

1) Функціональний

2) Структурний

3) Мови опису алгоритму

Функціональні моделі

Модель комбінаційних схем.

В якості моделі комбінаційних схем використовуються систему мулевих функцій.

Zm=fm (x1,…Xm), де x =(X1,…Xn)

Z= (Z1,…Zm). Вхідні змінні, які приймають двійкові значення B2={0,1}

Дана система описує комбінаційний пристрій, який має n-входів, m-виходів.

 

x1

x2

x3

…..

Xn

Кожна булева функція pi (X1,…Xn)

Моделі послідовних схем

В якості цієї моделі використовується абстрактний цифровий автомат, який являє собою сукупність об’єктів

A = (Y,X,Z, , ),

де X,Y,Z – кінцеві множини вхідних і вихідних сигналів. , YXX прямує до У – функція переходів, які визначають наступні етапи автомата.

 

Ϭ:Yxx→Z – функція виходу

Розрізняють два типи автоматів:

- Нейлі і мура

Автомат нейлі:

I(t+1)=ϭ(y(t), x(t));

Z(t+1)=λ(y(t), x(t));

Y(t+1)= ϭ(y(t), x(t));

Z(t+1)=)=λ(y(t)).

Альтернативні графи

Множину вершин розбивають на три підмножини:

1) Внутрішні вузли;

2) Листя

3) Корінь.

Логічне значення 0 або 1, що приймає булева функція відповідають системі діаграми. Внутрішні зв’язки відповідають змінним мулевої функції. Шлях на графі від кореневої вершини до листя визначають в залежності від значень змішаної функції.

Бінарна діаграма мулевих функцій. Наприклад булева функція f=ȧbȧ+ac.

Nn треба обчислити значення мулевої функція з допомогою змінних а=0, в=0, с=1

F=0, при а=0, в=1, f=ċ

 

Cтруктурна модель

Структурні моделі просто використовують правильну логічну систему. Правильна – логічна система у якої входи 2х елементів ще з’єднані разом і кожна функція виходу пристрою може бути представлена, як функція виходу яка реалізована на виході. Основну систему складають логічні елементи 2х типів:

1) Елементи, функціонування яких описують мулевими функціями.

2) Елементи пам’яті, функціонування яких описують моделлю:

Для дослідження властивості структурної моделі схеми використовують методи теорії графа.

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

- відповідає вершині із зв’язками. Рівень логічних елементів в комбінаційній схемі вузли, як міра відстані цього елемента від зовнішніх входів. При цьому зовнішнім входом присвоюється рівень рівний 0

 

Дані рівень L(i)=1+maxL(kj)

Монтажна логіка

При монтажній логіці виходи логічних елементів з’єднуються і в місці зєднання реалізується логічна функція «і» чи «або». Такий елемент наув. «монтажний і; чи монтажний або». Для того щоб такі ситуації могли оброблятися в процесі логічного моделювання логічний елемент «і», чи «або».

Моделювання монтажної логіки фіктивними елементами

При конкретному моделюванні після обчислювального значення виходу фіктивног елемента його потрібно присвоїти обом входам А і R.

Моделі рівня мов регістрових передач

МРП поділяють на дві категорії:

- процедурні

- Не процедурні

Типові моделі несправності

Рівень опису визначає моделі несправності і методи обчислення тестів.

Несправності можуть бути одиничними і кратними

Найбільш розповсюдженими моделями несправності є:

- Замикання

- Контактні

- Транзисторні

- Часові затримки

Контактні несправності

Такі несправності моделюють постійний шум або 1 на входах або виходах схеми і подають відповідно константна несправність «0» 0/0, константна несправність»1»0/1

Замикання

Число простих замикань в системі має м-лінійний, які рівні . Модель короткого замикання виникає при введення додаткової схеми:

 

a d

b f b g

c c

d

d e h

e h f

f

 

 

входи	виходи
A	b	c	d	e	f	g	h
								виправлені
								невиправлені

 

Транзисторні несправності

Пробій транзистора, найбільш розповсюдженими являються стійкий обрив транзистора, коротке замикання транзистора, між витоками стоком, затвором стоком, витоком і затвором.

Часові затримки

Крім тестування цієї несправності знаходження правильного функціонування схеми на високих тактів робочих частотах

Використовують два типи затримок:

- Затримка (несправний логічний елемент)

- Затримка шляху (загальна затримка розповсюдження сигналу від зовнішнього входу)

Тестування затримок проводиться подаванням на схему пар вхідних сигналів на певній швидкості і спостереження для кожного виходу швидкого його переключення.

Короткочасні відбуваються, коли сигнали змінюють своє значення в наслідок циклів

Збої являються однією з причин відмов