Разработка алгоритмического и программного обеспечения стандарта IEEE 1500 для тестирования гибкой автоматизированной системы в пакете кристаллов (стр. 6 из 7)
Эквивалентные преобразования позволили упростить достаточно сложную конструкцию – КНФ – с получением минимального множества всех решений, число которых, в данном случае, равно шести. Подмножество минимальных решений определяется тремя конъюнктивными термами, каждый из которых содержит 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. Преобразование КНФ к ДНФ.
Данное преобразование даёт возможность увидеть все решения задачи покрытия. Для этого к КНФ необходимо применить операцию логического умножения и правила минимизации (поглощения) для получения ДНФ:
Здесь представлена обобщенная запись ДНФ, где в пределе число термов равно
, n – число строк в обобщенном множестве (C, R) или количество переменных Х в матрице Y, на множестве которых формируются все решения – покрытия дефектов резервными компонентами; если 
при 
принимает значение нуля, то переменная превращается в несущественную.4. Выбор минимальных и точных решений задачи покрытия.
Данный выбор связан с определением конъюнкций минимальной длины в полученной ДНФ. Последующее преобразование к строкам и столбцам матрицы памяти, на основе использования ранее введенного соответствия, даёт возможность записать минимальное покрытие или их совокупность в двумерной метрике строк и столбцов, отвечающие условиям (ограничениям) функции цели на количество резервных компонентов.
Далее предлагается иллюстрация модели процесса восстановления работоспособности матрицы памяти в части определения минимального числа резервных компонентов, покрывающих все дефекты. Матрица памяти с дефектами и резервом [11] представлена на рис. 2.3.
Матрица имеет ограничения на возможность диагностирования и восстановление работоспособности десяти дефектных ячеек, которые определяются двумя строками и пятью столбцами. В соответствии с пунктом 1 модели процесса определения минимального числа резервных компонентов, покрывающих все обнаруженные дефекты в матрице памяти, строится таблица покрытия десяти дефектов
одиннадцатью строками, представленными в виде конкатенации подмножеств С и R, находящихся во взаимно-однозначном соответствии с вектором переменных Х: 
Далее, в соответствии с таблицей покрытия выполняется построение КНФ, термы которой записаны по единичным значениям столбцов.
Последующие преобразования, связанные с получением ДНФ основываются на применении законов и тождеств булевой алгебры, которые позволяют выполнить логическое перемножение всех десяти сомножителей, последующую минимизацию термов ДНФ путем применения оператора сограней, аксиом поглощения, исключения одинаковых термов. Опустив промежуточные вычисления, окончательный результат представим в следующем виде:
Выбор термов минимальной длины, содержащих 5 переменных, формирует множество оптимальных (минимальных) решений, имеющих вид:
(2.41)Трансформирование полученной функции к покрытию, содержащему обозначения переменных в виде строк и столбцов матрицы памяти, позволяет представить решения в следующей форме:
(2.41)Все полученные минимальные решения удовлетворяют требованиям по ограничениям на число резервных компонентов, определенных числами:
(2.42)Другие решения, определенные в ДНФ, не представляют интереса, поскольку они имеют неоптимальное покрытие дефектных ячеек, определяемое числом переменных (строки + столбцы) в термах более пяти. Последующая технология встроенного ремонта дефектных ячеек заключается в электрическом перепрограммировании дешифратора адреса столбца или строки матрицы памяти. Применительно к памяти, изображенной на рис. 2.3, процедура записи или считывания информации при обращении к любой ячейке столбца 2 будет переадресована к резервному столбцу 11. Соответственно последнему полученному решению в виде первого терма ДНФ функции Y, будут заменены и другие дефектные столбцы на исправные из резерва памяти: 3 – на 12; 5 – на 13; 7 – на 14, 8 – на 15.
Вычислительная сложность АЛМ восстановления работоспособности в части решения задачи покрытия определяется следующим выражением:
(2.43)где
– затраты, связанные с синтезом ДНФ путем логического перемножения исключительно двухкомпонентных дизъюнкций (координата дефекта определяется номером строки и столбца), число которых равно количеству дефектных ячеек; 
– верхняя граница вычислительных затрат, необходимых для минимизации полученной ДНФ на предельном множестве переменных, равном суммарному числу строк и столбцов 
В худшем случае, когда координаты всех дефектных ячеек по строкам и столбцам не коррелированы, – уникальны, например, диагональные дефекты, вычислительная сложность матричного метода становится зависимой только от числа дефектных ячеек, а ее аналитическая запись трансформируется к следующему виду: