Разработка алгоритмического и программного обеспечения стандарта IEEE 1500 для тестирования гибкой автоматизированной системы в пакете кристаллов

(2.28)

Пусть задана матрица Y, имеющая вид :

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

ой как конъюнкция дизъюнкций по конституентам единиц, соответствующих столбцам приведенной выше матрицы:

В данном случае аналитическая запись в виде булевой функции, представленной в виде КНФ, есть исходная модель, содержащая полное множество решений задачи покрытия, которая решается путем нахождения ДНФ. Для этого выполняется процедура преобразования КНФ в ДНФ путем перемножения всех термов. В результате эквивалентных преобразований, выполненных по правилам алгебры логики, получается булева функция, содержащая все возможные покрытия неисправностей, описанные с помощью четырех вариантов комбинаций строк:

Минимальное решение задачи покрытия содержит всего три резервных строки, с помощью которых покрывается 8 дефектов в матрице памяти:

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

Для примера (рис. 2.4), где имеется 5 дефектных ячеек, покрываемых тремя столбцами и четверкой строк.

Рисунок 2.4 – Матрица памяти с дефектными ячейками

Преобразование трансформирует матрицу памяти к таблице покрытия, где левый столбец задает взаимно-однозначное соответствие между координатами дефекта, в номерах строк и столбцов матрицы памяти и строками покрытия неисправностей:

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

Последующая запись булевой функции формирует логическое произведение дизъюнкций, записанных по конституентам единиц, соответствующих столбцам упомянутой выше матрицы :

Эквивалентные преобразования позволили упростить достаточно сложную конструкцию – КНФ – с получением минимального множества всех решений, число которых, в данном случае, равно шести. Подмножество минимальных решений определяется тремя конъюнктивными термами, каждый из которых содержит 3 резервных элемента для восстановления работоспособности матрицы памяти:

2.7 Формализация АЛМ ремонта памяти

Функция цели определяется как минимизация резервных компонентов матрицы памяти (S – spare), необходимых для восстановления ее работоспособности в процессе функционирования цифровой системы на кристалле путем синтеза ДНФ покрытия дефектных элементов с последующим выбором минимального конъюнктивного терма , удовлетворяющего ограничениям по числу резервных строк и столбцов , входящих в состав логического произведения:

где каждый результирующий конъюнктивный терм функции Y составлен из идентификаторов строк и столбцов , покрывающих все дефекты в матрице памяти. Лучшее решение есть терм минимальной длины по Квайну, в котором содержатся как строки, так и столбцы, покрывающие все дефекты. В частности, решение может не содержать строк (столбцов), когда для ремонта памяти достаточно только существующих столбцов (строк) из резерва матрицы памяти. Модель процесса определения минимального числа резервных компонентов, покрывающих все обнаруженные дефекты в матрице памяти, сводится к следующим пунктам:

1. Преобразование двумерной модели дефектов матрицы памяти в таблицу покрытия дефектов резервными строками и столбцами матрицы.

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

(2.34)

Здесь координата матрицы отмечается 1, если функция исправного поведения ячейки на тесте дает единичное значение, то координата идентифицируется дефектной. После фиксации всех дефектов выполняется построение таблицы покрытия дефектов, где столбцы соответствуют множеству установленных дефектов m, а строки есть номера столбцов и строк матрицы памяти, которые имеют дефекты:

(2.35)

Вместо компонентов двумерной метрики C и R используется одномерный вектор, сконкатенированный из двух последовательностей C и R, мощность которого равна n = p + q:

При этом между элементами исходных наборов (C, R) и результирующим вектором Х существует взаимно однозначное соответствие, установленное в первом столбце матрицы Y. Следует заметить, что преобразование X = C * R выполняется лишь для удобства рассмотрения и последующего построения ДНФ в рамках единообразия переменных, формирующих булеву функцию. Если данную процедуру не выполнять, то функция будет определена на двух типах переменных, содержащих столбцы и строки матрицы памяти.

2. Построение КНФ для аналитического, полного и точного решения задачи покрытия.

После формирования матрицы покрытия, содержащей нулевые и единичные координаты, выполняется синтез аналитической формы покрытия путем записи КНФ по столбцам. Здесь число конъюнктивных термов, равно количеству столбцов таблицы, а каждая дизъюнкция записывается по единичным значениям рассматриваемого столбца:

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

3. Преобразование КНФ к ДНФ.

Данное преобразование даёт возможность увидеть все решения задачи покрытия. Для этого к КНФ необходимо применить операцию логического умножения и правила минимизации (поглощения) для получения ДНФ:

 Скачать реферат