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

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 5Следующая ⇒

Етап_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

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

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

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

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

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

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

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

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

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

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

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии