Практические занятия Прикладная теория цифровых автоматов
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Занятие 9. Построение полного минимального теста схем

Цель занятия – изучение еще одного свойства схем – наличие неисправностей. Изучается классический метод Чегиса – Яблонского.

Теоретические положения и пример. Неисправности в схемах наиболее ожидаемый характер их работы.

Мы ограничимся характерными неисправностями – появлением тождественного 0 или 1 на входах и выходах всех элементов в схеме, более того ограничимся однократными неисправностями. Классический метод Чегиса и Яблонского основан на построении функций однократных неисправностей на всех наборах схемы, а затем на основе этих функций построение и решение таблицы покрытий с точностью хотя бы одного кратчайшего покрытия. Таким образом, удается построить минимальный тест – множество входных наборов, проверяющих наличие хотя бы одной неисправности в схеме.

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

Утверждение 1. Неисправности 1 на входах элементе верхнего яруса схемы приводят к исчезновению интервала, поданного на этот вход.

Утверждение 2. Неисправности 1 на входах элементов второго уровня приводят к расширению интервала по переменной, поданной на этот вход.

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

Рисунок 41. Простая функция и схема для построения проверяющего теста.

Элементы, начиная от головного, пронумерованы – 1.2.3.4. Таблицу функций неисправностей начинаем строить с головного элемента, перебираем неисправности. Варианты перебора обозначаем так: i, j, σ, где i – номер рассматриваемого элемента, j –номер его входа-выхода, σ – тип неисправности( σ { 0, 1}. Выход элемента получает номер 0. входы – номера 1,2,…,к, где к – число входов.

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 42. Неисправность i,2,0.

     

1

2

3

4

5

6

7

 

X1x2x3

F

1,0,0

1,0,1

1,1,1

1,2,1

2,1,1

2,2,1

3,1,1

A

0 0 0

0

0

▀1

0

0

▀1

0

0

B

0 0 1

0

0

▀1

0

0

0

0

0

C

0 1 1

0

0

▀1

0

0

0

0

▀1

D

0 1 0

0

0

▀1

0

0

▀1

0

▀1

E

1 1 0

1

▀0

1

1

1

1

1

1

F

1 1 1

1

▀0

1

1

▀0

1

1

1

G

1 0 1

0

0

▀1

0

0

0

▀1

0

H

1 0 0

1

▀0

1

▀0

1

0

1

1

       

1,1,0

1,2,0

2,0,0

3,0,0

2,0,1

2,1,0

2,2,0

4,0,0

4,1,1

3,0,1

3,1,0

3,2,0

 

3,2,1

4,0,1

4,1,0

 

Сначала заполняем столбец F, в нем три 1, наборы!00, 110 и 111. Затем – перебор одиночных неисправностей, начиная с головного элемента. 1,0,0 – выход схемы, неисправность 0. Заполняем столбец 2. 1,0,1 – снова выход схемы неисправность 1. Отмечаем значком ▀ наборы, на которых значения выхода схемы отличаются от исправных. Неисправности тождественные 0 на входах головного элемента(1,1,0 и 1,2,0) приводят к тождественной 1 на выходе схемы, т. е. не отличаются от уже перечисленной неисправности 1,0,1. Остаются неисправности 1,1,1 и 1,2,1. Как уже отмечалось, эти неисправности приводят к исчезновению интервалов, поданных на соответствующие входы. 1,1,1 – исчезает интервал х1х3. Это приводит к исчезновению одного набора – 100. Второй набор интервала по-прежнему покрывается остающимся интервалом. 1,2,1 – исчезает набор 111, второй набор интервала покрывается оставшимся интервалом. Все 6 неисправностей головного элемента просмотрены. Неисправности 0 и 1 на выходе элемента 2 аналогичны неисправностям 0 и 1 на входном полюсе головного элемента 1. Неисправности 0 на входах элемента 2 приводят к появлению 1 на выходе элемента 2. Для этого элемента остались только неисправности (2,1,1)и (2,2,1). Как уже отмечалось, появление неисправности 1 на входе элемента второго уровня вызывает расширение интервала по переменной, поданной на этот вход. Неисправность (2,1,1) означает расширение интервала х1х3, реализованного элементом 2, по переменной х1 до интервала х3. Последний покрывает наборы 000 и 010, на которых вместо 0 появляется 1. Неисправность (2,2,1) означает расширение того же интервала по переменной х3 до интервала х1, что означает покрытие элемента 101. Вместо 0 появляется лишняя 1. Аналогично, неисправности (3,0,0) и (3,0,1) вызывают уже рассмотренные функции неисправности (1,2,0) и (1,2,1) соответственно. Неисправности 0 на входах элемента 3 приводят к уже рассмотренной функции неисправности (3,0,1). Неисправность 1 на входе 3,1 приводит к расширению интервала х1х2 до х2 что вызывает покрытие наборов 010 и 011, на которых вместо 0 реализуется 1. неисправность 1 на входе 3,2 приводит к реализации уже рассмотренной функции неисправности (2,2,1). Остался элемент 4, это инвертор. Его неисправности приводят к уже полученным функциям (2,2,0) и (2,2,1).Все возможные функции неисправностей построены, их оказалось 7. Нумеруем столбцы цифрами 1,2,…,7, строки латинскими буквами A, B,…,H и строим новую таблицу из 7 столбцов и 8 строк, заполняя ее элементы: FΘFнеиспр, т. е. 1 отмечаются элементы, где исправная функция отличается от неисправной.

 

1

2

3

4

5

6

7

A

 

1

   

1

   

B

 

1

         

C

 

1

       

1

D

 

1

   

1

 

1

E

1

           

F

1

   

1

     

G

 

1

     

1

 

H

1

1

       

По этой таблице мы строим кратчайшее покрытие – множество наборов, проверяющих наличие в схеме хотя бы одной неисправности – минимальный проверяющий тест – D, F,G, H.

Домашнее задание. Построить минимальный проверяющий тест для схемы, построенной по функции fi из задания [1, 181]

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство