Библиотека
Собственная публикация №1
Нахождение тестового вектора методом трассировки критических путей
Довганич Е.В., Зинченко Ю.Е.
Донецкий национальный технический университет
Інформатика та комп'ютерні технології — 2008 / Матеріали IV науково-технічної конференції студентів, аспірантів та молодих учених. — Донецьк, ДонНТУ — 2008, с. 228-230.
Данный метод трассировки критических путей (далее метод критических путей – МКП) представляет собой метод исследования комбинационных схем, с помощью которого возможно построение тестового вектора для данной схемы. Тестовый вектор включает в себя набор тестов, т.е. набор начальных значений первичных входов схемы, которые дают возможность найти максимальное количество обнаруживаемых константных неисправностей (КН).
МКП принадлежит к разделу диагностики интегральных схем, где наиболее распространённым методом диагностики является метод полного перебора входных значений, который нашёл широкое практическое применение ввиду простоты своей программной реализации и технического исполнения. Однако, метод полного перебора требует значительных аппаратных затрат, а главное – большого количества машинного времени, т.к. при увеличении количества первичных входов на одну единицу, длина тестового вектора увеличивается в два раза (количество тестов в векторе). Т.о. при диагностике больших и сверхбольших интегральных схем практическое применение метода полного перебора становится затруднительным или невозможным (при решении задач, критичных по времени). При использовании МКП каждый тест строится из расчёта максимального покрытия ещё необнаруженных КН, тем самым достигается минимальная длина тестового вектора.
Также, МКП даёт возможность оценки полноты теста (вектора), т.е. можно оценить, какое количество КН покрывает данный тест. Следовательно, данный метод не требует использования дополнительных алгоритмов оценки полноты тестов.
Для определения обнаруживаемых КН выполняется моделирование исправной схемы, в ходе которого рассчитываются значения сигналов для критических путей. Этот расчёт выполняется от первичных выходов к первичным входам. Построение критических путей основано на теории кубов логических элементов (ЛЭ). Всю теорию кубов ЛЭ можно свести к анализу вырожденных покрытий (ВП) различных ЛЭ. Для данного анализа необходимо составить нулевые и единичные вырожденные покрытия вышеперечисленных логических элементов. [3]
Обобщённый алгоритм МКП будет выглядеть следующим образом (рис. 1):
- находятся первичные выходы схемы;
- для всех первичных выходов составляются наборы всех возможных критических значений, т.е. для схемы с двумя первичными выходами это будет набор – 0*0*, 0*1*, 1*0* и 1*1*; с одним – 0* и 1*;
- находится ЛЭ, значение выхода которого было получено на предыдущем шаге, и в соответствии с его выходным значением определяется ВП данного ЛЭ;
- если значения этого ВП не конфликтуют со значениями, полученными на предыдущих шагах, то входам ЛЭ присваиваются соответствующие ВП логические значения. В случае определения значений всех первичных входов, эти значения будут представлять собой тест, который помещается в вектор. После этого, или если произошёл конфликт значений, выбирается следующий набор входных значений последнего обработанного ЛЭ. После обработки последнего набора текущего ЛЭ выполняется переход к предыдущему ЛЭ, т.е. на один уровень назад и т.д.;
- после перебора всех возможных наборов критических значений первичных выходов, получаем тестовый вектор для обнаруживаемых КН и его полноту.
Таким образом, мы получаем набор тестов, который образует тестовый вектор. Этот вектор покрывают определённую часть КН схемы. Тестовый вектор считается удовлетворительным, если его покрытие составляет 80% и более от общего числа КН. Это называется оценкой полноты теста. Поэтому необходимо при построении очередного теста (бесконфликтного полного прохода от первичных выходов к первичным входам), сразу добавлять в список обнаруженные данным тестом неисправности. КН х (stuck-at-x) считается обнаруженной, если в одном из критических путей содержится критическая линия со значением ‘x (НЕ x).
Однако, применение выше описанного, так называемого, классического МКП на практике не даёт должного результата. Это происходит из-за того, что, учитывая правила построения кубов ЛЭ, не всегда поиск оптимального набора входных значений вентиля даёт возможность перебора всех существующих вариантов значений. Другими словами, при наличии критического значения на выходе вентиля происходит перебор его входных значений из соответствующего ВП. Но ВП не содержит полного набора возможных значений, а только группы значений, отвечающих условиям критичности. Следовательно, при трассировке схемы необходимо после анализа группы значений для входов вентиля из соответствующего ВП, анализировать и все оставшиеся варианты, не присутствующие в ВП. Однако, выборку осуществлять сначала нужно всё же из ВП ЛЭ.
К этим выводам я пришёл, применяя классический МКП для схемы одного разряда сумматора с черезразрядной инверсией переноса. Результатом классического метода будет вектор, состоящий из одного теста – 1*1*1*. Этот вектор из 24 КН (с учётом эквивалентности) обнаруживает только 5, что составляет 21%. Для того, чтобы вектор можно было считать удовлетворительным, он должен как минимум покрывать 80% всех КН. Очевидно, что данный вектор таковым назвать нельзя. Применение усовершенствованного МКП увеличивает процент покрытия до 100%.
В заключение добавлю, что данный метод диагностики ИС способен в значительной мере сократить время моделирования и диагностики печатных плат, а также при совместном использовании с другими методами (как, в прочем, и при одиночном использовании) даёт высокие показатели полноты покрытия КН и не требует больших аппаратных затрат при его практической реализации.
Литература:
1. M. Abramovici, P. R. Menon and D. T. Miller. "Critical path tracing - an alternative to fault simulation", IEEE Design and test, Feb. 1984, pp. 83-92.
2. Статья "Using VHDL Critical Path Tracing Models for Pseudo Random Test Generation", Massoud Shadfar, Armita Paymandoust, Zainalabedin Navabi. Electrical and Computer Engineering Department.
3. А.С. Барашко, Ю.А. Скобцов, Д.В. Сперанский. Моделирование и тестирование дискретных устройств. – К., Наукова думка, 1992 г.