WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 | 4 |

Рассматривается STG (State Transition Graph)-описание, позволяющее более компактно (по сравнению с таблицами переходов-выходов) представлять поведение дискретного автомата. В этом описании (таблица 1) символы входного и выходного алфавитов уже закодированы.

Таблица 1 Таблица x1x2x3 q q y1y2y3y4y5 x1x2x3 z1z2z3z4 z1z2z3z4 y1y2y3y4y0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 2 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 2 2 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 2 3 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 1 0 3 3 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 3 4 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 3 4 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 4 4 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 4 1 1 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 Здесь x1, x2, x3 – входные переменные, у1,…,y5 – выходные переменные, в столбце q указаны состояния, относящиеся к моменту времени t, а в столбце q – состояния, относящиеся к моменту времени t+1.

Выполнив кодирование состояний для такого описания, получим систему F(X)частичных булевых функций (таблица 2). Строка таблицы 2 представляет допустимый интервал (u, h)i этой системы. Интервал ui задается первыми двумя столбцами таблицы, а его характеристика hi –оставшимися столбцами. Единичные компоненты вектора hi перечисляют функции, которые принимают единичное значение на всех элементах интервала ui.

Теорема 1. Интервал (u, h)i является допустимым для системы F(X) частичных булевых функций.

Теорема 2. Интервал (u, h)i системы F(X) частичных булевых функций имеет максимальную характеристику.

Обозначим через W множество всех допустимых интервалов (u, h)i, W = {(u, h)i}.

Одним из подходов к обеспечению свойств самопроверяемости синхронных последовательностных схем является кодирование символов состояний автомата и символов его выходного алфавита неупорядоченными кодами. Такое кодирование позволяет обнаруживать монотонно проявляющиеся неисправности на наблюдаемых полюсах комбинационной составляющей синхронного автомата (на выходах автомата и линиях его обратных связей). Проявление неисправностей заключается в замене в ее присутствии кодового слова на некодовое.

Определение 10. Векторы 1, 2 сравнимы, если один из них предшествует другому, иначе они не сравнимы. Например, векторы 0100110, 1110110 сравнимы, а векторы 0100110, 1100001 не сравнимы.

Определение 11. Множество векторов одной и той же размерности образуют неупорядоченный код, если любые два вектора этого множества не сравнимы.

При кодировании символов состояний (символов выходного алфавита) словами неупорядоченного кода используют либо равновесный код, либо код Бергера.

Определение 12. Булевы векторы являются инверсно 2-ортогональными, если в одном из них i-я компонента принимает значение 1, а в другом – i-я компонента принимает значение 0, в то время как j-я компонента первого вектора принимает значение 0, а j-я компонента второго вектора принимает значение 1.

Несравнимые векторы инверсно 2-ортогональны.

Вернемся к STG-описанию поведения синхронного автомата (таблица 2). В ней состояния таблицы 1 закодированы равновесными кодами, а коды выходных символов не являются ни равновесными, ни кодами Бергера. Добавим две переменные y6, y7, сделав коды выходных символов автомата равновесными. В результате получаем таблицу 3.

Таблица x1x2x3 z1z2z3z4 z1z2z3z4 y1y2y3y4y5y6yТаблица 3 представляет 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 систему частичных функций 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 F(X), соответствующее ей мно1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 жество W, W = {(u, h)i} является 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 реализацией системы, то есть 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 множество W можно рассматри0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 вать как задание на синтез са 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 мопроверяемого синхронного 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 последовательностного устрой 1 0 0 0 1 1 0 0 0 1 1 0 0 1 0 ства. Его монотонно проявляющиеся неисправности будут обнаружены детектором равновесных кодов, подключенным к выходам и линиям обратных связей устройства (рис.1).

y1 ym xxn y ДК m+К y s zzp ddp Рисунок 1 – Самопроверяемое синхронное последовательностное устройство в условиях наблюдения его выходов и линий обратных связей Здесь К – комбинационная составляющая самопроверяемого последовательностного синхронного устройства, d1, …, dp, d-триггеры, включенные в линии обратных связей, ДК – детектор кодов, подключенный к выходам и линиям обратных связей.

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

Воспользуемся свойством неупорядоченных кодов – их по парной инверсной 2-ортогональностью. Заменив все нули в кодах состояний на символ, получим следующую таблицу.

Таблица x1x2x3 z1z2z3z4 z1z2z3z4 y1y2y3y4y5y6yКаждой строке таблицы со0 1 1 0 0 0 0 0 0 1 0 1 поставим интервал (u, h)i*. Еди 0 1 1 0 0 0 0 0 0 1 0 1 ничные компоненты вектора hi* 1 1 1 0 1 0 0 1 0 0 1 0 1 перечисляют функции, которые 0 1 0 1 0 0 0 0 1 1 0 1 принимают значение 1 на всех 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 1 элементах интервала ui*.

0 1 0 0 0 1 1 1 0 0 0 1 Теорема 3. Интервал (u, h)i* 1 1 0 0 0 1 1 1 0 0 0 1 является допустимым для системы 0 1 0 0 0 1 0 1 0 0 1 1 F(X) частичных булевых функций, 1 1 1 0 0 0 1 1 0 0 1 0 полученной кодированием состояний неупорядоченными кодами.

Теорема 4. Интервал (u, h)i*-допустимый интервал системы F(X) с максимальной характеристикой.

Пусть W* = {(u, h)i*}.

Теорема 5. W* является реализацией системы F(X).

Будем иметь в виду, что рассматриваемая реализация является частично монотонной по переменным z1,…, zp, сопоставляемым линиям обратных связей.

Определение 13. Длиной реализации системы F(X) будем называть число интервалов реализации.

Определение 14. Кратчайшей реализацией системы F(X) будем называть реализацию из максимальных интервалов наименьшей длины.

Алгоритм построения кратчайшей частично монотонной реализации из максимальных интервалов с максимальными характеристиками Вход: Система F(X) частичных булевых функций, допускающих частично монотонную реализацию.

Выход: Кратчайшая частично монотонная реализация из максимальных интервалов с максимальными характеристиками.

Ш.1. Строим всевозможные расширения интервалов множества W* без изменения их характеристик. В результате для каждого интервала из W* получаем звезду максимальных интервалов. Множество всех максимальных ~ * интервалов обозначаем W.

~ * Ш.2. Разбиваем множествоW на подмножества максимальных интер~ валов (hi) с одинаковыми характеристиками.

W* Ш.3. Находим кратчайшую реализацию подсистемы F(X), представленной интервалами с одной и той же характеристикой hi, используя интер~ * валы множества W (hi). Обозначаем множество интервалов полученной реа~* лизации через W (hi).

Ш.4. Объединяем полученные для каждой характеристики hi реализа~* ции W (hi), находим кратчайшую реализацию Wкр*.

На практике построение кратчайших реализаций оказывается неприемлемым из-за большого объема вычислений. Приходится ограничиваться безызбыточными реализациями из максимальных интервалов с максимальными характеристиками.

Предложенные алгоритмы получения кратчайшей и безызбыточной реализаций ориентированы на минимизацию системы частичных булевых функций, допускающей частично монотонные реализации, именно такие реализации необходимы для синтеза самопроверяемых схем. Целесообразность предложенного алгоритма обусловлена тем, что, во-первых, известные алгоритмы минимизации систем частичных булевых функций (в частности алгоритм Закревского А.Д.), не ориентированны на поиск частично монотонных реализаций, а, во вторых, тем, что для рассматриваемой системы частичных булевых функций, в силу ее специфических свойств одна из монотонных реализаций известна и представляется множеством интервалов с максимальными характеристиками, как правило, довольно низких рангов. Предложенный нами алгоритм ориентирован на ее использование с целью получения лучших частично монотонных реализаций.

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

Об этом свидетельствуют результаты экспериментов (они приведены в тексте диссертации), проведенных с использованием алгоритма Закревского А.Д., так что его применение гарантировало получение частично монотонной реализации. Этим алгоритмом строились интервалы, в основном, с не максимальными характеристиками, что ухудшало качество реализаций рассматриваемых нами систем частичных булевых функций.

Использование частично монотонных безызбыточных реализаций в качестве задания на синтез самопроверяемых синхронных автоматов позволяет сократить аппаратурные затраты на синтез самопроверяемых схем.

Известно, что чем проще система ДНФ, тем, как правило, проще схема, ее реализующая. Переход к частично монотонным системам с последующей минимизацией позволяет существенно сократить ранги конъюнкций и их число, о чем свидетельствуют результаты экспериментов, выполненные на контрольных примерах.

Таблица В таблице 5 ввеЧастично монотонные системы дены следующие обоКП i o W* W*б W*б значения: КП – конP L P L P L трольные примеры: 1 – beecount, 2 – bbsse, 3 – 1 9 10 28 152 19 76 20 bbara, 4 – cse, 5 – 2 13 16 56 249 38 197 41 donfile, 6 – planet, 7 – 3 10 9 60 350 47 208 50 ex1, 8 – scf, 9 – sand; i – 4 13 16 91 540 78 452 89 число входов; o – число 5 9 8 96 576 94 464 112 выходов; W*– частично 6 15 36 115 653 115 634 123 монотонная реализация;

W*б – безызбыточная 7 15 34 138 947 119 760 131 частично монотонная 8 37 79 166 1145 166 941 191 реализация, построен9 19 22 184 1439 121 660 127 ная предложенным алгоритмом; W*б– безызбыточная частично монотонная реализация, построенная алгоритмом А.Д. Закревского; P – число конъюнкций в системе F(X); L – число букв в системе F(X).

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

Одиночные константные неисправности на входах синхронного последовательностного устройства при использовании частично монотонных реализаций и тех же методов синтеза могут не проявляться монотонно. Для обеспечения их монотонного проявления необходимо расширить множество входов последовательностного устройства. В работе Matrosova A. Yu., Levin I., Ostanin S. A. «Self-Checking Synchronous FSM Network Design with Low Overhead» (Journal of VLSI Design. – 2000. – Vol. 11, № 1. – Р. 47-58) предлагается ввести дополнительные входы, так что интервалы с различными характеристиками и не отличающиеся по значениям внутренних переменных становятся инверсно 2-ортогональными. В этом случае задание на синтез самопроверяемого последовательностного устройства может быть представлено полностью монотонной реализацией. Теоретические результаты и алгоритм минимизации частичных систем булевых функций в классе частично монотонных реализаций распространяются в диссертационной работе на полностью монотонные реализации.

Одним из этапов построения реализации из максимальных интервалов с максимальными характеристиками является построение максимальных расширений интервалов. С ростом размерности задачи зачастую нет возможности построить все максимальные расширения (звезду максимальных интервалов), и поэтому в диссертационной работе предлагаются эвристические алгоритмы, позволяющие найти либо одно максимальное расширение, либо некоторые из них, по возможности меньших рангов, с тем, чтобы затем построить из них безызбыточную реализацию.

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

Третья глава посвящена построению проверяющего теста, обнаруживающего одиночные неисправности отдельной безызбыточной ДНФ (БДНФ) и системы БДНФ. Алгоритм ориентирован на сокращение длины теста. Проверяющий тест для таких неисправностей является одновременно проверяющим тестом для кратных константных неисправностей на полюсах логических элементов схемы, построенной по системе БДНФ методами факторизационного синтеза, сохраняющими систему БДНФ.

Пусть ДНФ D = K1, …, Ks состоит из простых импликант.

Определение 15. ДНФ D, в которой нельзя удалить ни одну конъюнкцию Ki, называется безызбыточной ДНФ.

Определение 16. Система ДНФ называется системой БДНФ, если каждая ДНФ Di системы есть БДНФ.

Рассмотрим модели неисправностей БДНФ D, введенные в работе I.

Kohavi, Z. Kohavi. «Detection of multiple faults in combinational logic networks», IEEE Trans. Comput.1975. VC-20. №6. P. 556-568. В ней выделены два типа неисправностей: a-неисправности и b-неисправности. Исчезновение некоторой конъюнкции из D называется а-неисправностью, исчезновение некоторой буквы из некоторой конъюнкции называется b-неисправностью.

Наборы, обнаруживающие такие неисправности, будем называть a,bтестовыми наборами, соответственно.

В работе «А.Ю. Матросова. «Построение полного теста для схем, синтезированных методом факторизации», Автоматика и вычислительная техника 1978 №5 С. 42-46, предложены специальные алгоритмы построения a,bтестовых наборов. Для их описания введем ряд определений.

Определение 17. Конъюнкцию K*(xi), полученную из K путем замены знака переменной xi на инверсный, будем называть дополнением конъюнкции K по переменной xi.

Определение 18. Фиксированием значений некоторых переменных ДНФ D относительно конъюнкции K является вычеркивание всех конъюнкций, ортогональных K, а также вычеркивание всех букв из оставшихся конъюнкций ДНФ D, которые присутствуют в K. Результат фиксирования представляется ДНФ, которую будем обозначать D(K).

Pages:     | 1 || 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»