Синтез и анализ логической схемы при кубическом задании булевой функции (стр. 4 из 4)
Синтезировать контрольный тест для логической схемы – найти множество кубов, которые позволяют выявлять неисправности схемы. Если в схеме нет неисправностей, то на каждом кубе получается так называемая эталонная реакция схемы. Множество кубов порождает множество эталонных реакций схемы.
При наличии неисправности в схеме реакция хотя бы на одном кубе должна измениться. В итоге множество реальных реакций не совпадает с множеством эталонных реакций. Это будет говорить о том, что неисправность выявляется. Если тест позволяет выявлять любую неисправность, то он обладает 100-процентной полнотой. Однако, это не всегда бывает так. Обычно тест не обеспечивает выявление всех неисправностей, его полнота менее 100%.
В данной курсовой работе рассматривается ограниченный класс неисправностей:
1). Выход элемента тождественно равен 0,
2). Выход элемента тождественно равен 1.
Считается, что в данный момент времени в схеме может быть только одна неисправность. Это означает, что схема является высоконадежной.
Синтез теста осуществляется по методу активизации пути. Сущность этого метода заключается в том, что, задав какую-либо неисправность на выбранном входе схемы, нужно обеспечить условия для беспрепятственного прохождения сигнала, связанного с заданной неисправностью, на выход схемы. Это означает, что при прохождении указанного сигнала через элемент ИЛИ-НЕ на всех других его входах надо обеспечить нули. В свою очередь обеспечение таких входных сигналов связано с выбором подходящей строки покрытия элемента, с которого снимается нужный сигнал.
Рис. 3
Процесс активизации путей схемы (рис.3) отображен в табл. 16. Всего оказалось 20 путей.
Контролирующий тест Таблица 16
| 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 | 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | Пути |
| 1 0 0 0 1 1 0 | 0’1 1 1 0 0 1 | 1 0 1 0 0 0 1’ 0 1 0 0’ 0 0 0 1 0 1’ 0’ | 1, 8,21, 25, 31,32 |
| 1 0 1 1 0 1 0 | 0’1 0 0 1 0 1 | 0 1 1 0 0 1 0 0 1 0 0 1’ 0 1 0 0 0’ 1’ | 1, 8, 26, 31,32 |
| 1 1 0 0 1 0 1 | 0 0 1 1 0 1 0 | 1 0 0 1 0’ 0 1’ 0 1’ 1 0’ 0 0’ 0 1’ 0’ 1’ 0’ | 1, 19, 23, 27, 29, 30, 31, 32 |
| 1 1 1 0 0 1 0 | 0 0 0 1 1 0 1 | 1 0 1 0 0 0 0 1 1 0 0’ 0 0 1 0 0 1’ 0’ | 2, 25, 31, 32 |
| 1 1 1 0 0 1 0 | 0 0’ 0 1 1 0 1 | 1 0 1 0 0 0 0 1’ 1 0 0 0’ 0 1 0 0 1’ 0’ | 2, 9, 22,26, 31,32 |
| 0 1 1 0 1 0 1 | 1 0 0 1 0 1 0 | 1 0 0 1 0’ 0 0 0 1’ 1 0 0 0’ 0 1’ 0’ 1’ 0’ | 3, 19, 23, 27, 29, 30, 31, 32 |
| 0 1 1 0 1 1 0 | 1 0 0’ 1 0 0 1 | 1 0 1 0 0’ 0 0’ 1 1’ 0 0’ 0 0’ 1 0’ 1’ 0’ 1’ | 3, 10, 28, 29, 30, 31, 32 |
| 1 0 1 1 0 1 0 | 0 1 0’ 0 1 0 1 | 0 1 1 0 0 1 0 0 1 0 0 1’ 0 1 0 0 0’ 1’ | 3, 10, 26, 31, 32 |
| 0 1 0 1 1 0 1 | 1 0 1 0 0 1 0 | 0’ 1’ 0 1 0’ 0 0 0 1’ 1 0 0 0 0 1’ 0’ 1’ 0’ | 4, 15, 16, 19, 23, 29, 30, 31,32 |
| 1 0 0 1 0 1 0 | 0 1 1 0 1 0 1 | 0’ 1’ 1 0 0 1 0 0 1 0 0’ 0 0 0 1 0 1’ 0’ | 4, 15,16,25,31,32 |
| 0 0 1 1 1 1 0 | 1 1 0 0’ 0 0 1 | 0 1 1 0 0 1’ 0 0 1 0’ 0 0 0 1’ 0’ 1’ 0’ 1’ | 4, 11, 20, 24, 28, 29, 30, 31, 32 |
| 1 0 0 0 1 1 0 | 0 1 1 1 0’ 0 1 | 1 0 1 0 0 0 1’ 0 1 0 0’ 0 0 0 1 0 1’ 0’ | 5,12,21,25, 31,32 |
| 0 0 1 1 1 1 0 | 1 1 0 0 0’ 0 1 | 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1’ 0’ 1’ | 5, 12, 30, 31, 32 |
| 0 1 0 0 1 1 1 | 1 0 1 1 0 0 0 | 1 0 0 1 0’ 0 0 0 1’ 1 0 0 0’ 0 1’ 0’ 1’ 0’ | 6,19,23,27,29,30,31,32 |
| 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 | 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | Пути |
| 0 0 1 1 0 1 1 | 1 1 0 0 1 0’ 0 | 0 1 0 1 0 1’ 0 0 1 0’ 0 0 0 1’ 0’ 1’ 0’ 1’ | 6, 13, 20, 24, 28, 29, 30, 31, 32 |
| 1 0 1 1 0 1 0 | 0 1 0 0 1 0’ 1 | 0 1 1 0 0 1 0 0 1 0 0 1’ 0 1 0 0 0’ 1’ | 6, 13, 26, 31, 32 |
| 1 1 1 0 0 1 1 | 0 0 0 1 1 0 0 | 1 0 0’ 0’ 0 0 0 0’ 1 1 0 1’ 0 0 1 0 0’ 1’ | 7, 17, 18, 22, 26, 31, 32 |
| 0 0 1 0 1 1 1 | 1 1 0 1 0 0 0 | 1 0 0’ 1’ 0 0 0 0 1 1 0’ 0 0 0 1 0 1’ 0’ | 7,17,18,25,31,32 |
| 0 0 1 0 1 0 1 | 1 1 0 1 0 1 0’ | 1 0 0 1 0 0 0 0 1 1’ 0 0 0 0’ 1’ 0’ 1’ 0’ | 7, 14, 24, 28, 29, 30, 31, 32 |
| 0 1 0 0 1 0 1 | 1 0 1 1 0 1 0’ | 1 0 1 0 1 0 0 0 0 1 0 0 1’ 0 0’ 1’ 0’ 1’ | 7, 14, 27, 29, 30, 31, 32 |
После заполнения всех строк таблицы из нее следует выписать наборы входных переменных с соответствующими реакциями. При этом один набор с переменной 1’ распадается на два набора, в одном из них 1’ дает 1, а в другом – 0. В общей системе наборов обычно получаются одинаковые наборы. Лишние нужно удалить. Оставшиеся ( табл. 17 ) наборы с эталонными реакциями и являются тестом.
Таблица 17
| Реакция | Наборы | Реакция | Наборы |
| 0 | 0 0 1 1 0 1 1 | 0 | 0 0 1 0 1 1 1 |
| 1 | 1 0 1 1 0 1 0 | 0 | 0 0 1 0 1 0 1 |
| 0 | 1 1 0 0 1 0 1 | 1 | 0 1 0 0 1 0 1 |
| 0 | 1 1 1 0 0 1 0 | 1 | 0 0 0 0 1 1 0 |
| 0 | 0 1 1 0 1 0 1 | 0 | 0 0 1 1 0 1 0 |
| 1 | 0 1 1 0 1 1 0 | 1 | 1 0 1 0 0 1 0 |
| 0 | 0 1 0 1 1 0 1 | 1 | 1 0 0 0 0 1 0 |
| 0 | 1 0 0 1 0 1 0 | 0 | 0 0 1 1 0 0 1 |
| 1 | 0 0 1 1 1 1 0 | 0 | 1 0 1 1 0 0 0 |
| 0 | 0 1 0 0 1 1 1 | 1 | 0 0 1 0 1 1 0 |
| 1 | 0 0 1 1 0 1 1 | 1 | 0 0 1 0 1 0 0 |
| 1 | 1 1 1 0 0 1 1 | 0 | 0 1 0 0 1 0 0 |
Всего получилось 24 набора.
Чтобы проверить схему, надо задать три неисправности: одна касается какого-либо элемента ближе ко входам схемы, другая – к середине схемы, третья – к выходу схемы.
Надлежит установить, обнаруживается или нет каждая заданная неисправность тестом. При этом нужно брать те тестовые наборы, которые как раз и предназначены для обнаружения заданной неисправности.
Проверка схемы проведена в табл. 18. В соответствующем столбце фиксируется ошибка, сведения для столбцов, расположенных левее, берутся из табл.16, остальные заполняются самостоятельно с учетом введенной ошибки. Полученная реакция сравнивается с эталонной. Таким образом устанавливается, обнаруживается или нет заданная неисправность.
Проверка логической схемы контролирующим тестом Таблица 18
| № набора | 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 | 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | Эталонная реакция | Пути |
| 7 | 0 1 1 0 1 1 0 | 1 0 1 1 0 0 1 | Выход 10 = 11 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 | 1 | 3, 10, 28, 29, 30, 31, 32 |
| 9 | 0 1 0 1 1 0 1 | 1 0 1 0 0 1 0 | Выход 19 = 10 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 | 0 | 4, 15, 16, 19, 23, 27, 29, 30, 31,32 |
| 11 | 0 0 1 1 1 1 0 | 1 1 0 0 0 0 1 | Выход 28 = 00 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 | 1 | 4, 11, 20, 24, 28, 29, 30, 31, 32 |
ЗАКЛЮЧЕНИЕ
В данной работе я выполнил синтез логической схемы по заданному в кубической форме покрытию. При этом мною предварительно была проведена минимизация и факторизация покрытия. Первоначальная стоимость покрытия была равна 48, после нахождения множества простых импликант она увеличилась на 5 (что составило 10,4% от первоначальной стоимости), после нахождения множества L-экстремалей стоимость уменьшилась на 17 (32%), а после проведения факторизации покрытия еще на 6 (16,7%). Итоговая стоимость покрытия получилась равной 30. Синтез схемы осуществлялся мною последовательно: сначала была построена схема в булевом базисе, затем по этой схеме была построена схема в универсальном базисе ИЛИ-НЕ (при этом использовались соответствия между элементами булевого и универсального базисов). После составления схемы в универсальном базисе была проведена проверка схемы путем нахождения единичного покрытия. Так как в ходе проверки были найдены все кубы множества L-экстремалей, то схема была признана правильной. И наконец, была составлена схема с учетом реально имеющихся ограничений, а именно: Квх и Кр. Обычно эта схема получается довольно громоздкой (до 50 и более элементов), но в моем случае Квх был равен 4, из-за чего схема увеличилась лишь незначительно: если в схеме в универсальном базисе было 19 элементов, то в конечной схеме их было только 32. Напоследок мною был синтезирован контролирующий тест и проведена проверка схемы тестом, которая показала, что заданная неисправность успешно обнаруживается тестом.
ЛИТЕРАТУРА
1. Триханов А.В. Синтез логических схем. Учебное пособие.-Томск,2007.
2. Майоров С.А. и др. Проектирование ЦВМ. – М.:ВШ,2006.
3. Миллер Р. Теория переключательных схем. Том 1. – М.:Наука,2006.
4. Триханов А.В. Алгоритмизация и микропрограммирование операций ЭВМ (множества, графы, кубы, кубические покрытия). Учебное пособие. – Томск: Изд-во ТПУ,2005.