Информационная система "Конференции"

Тезисы докладов

Информационные технологии

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

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

В этом случае схему сжатия эталонных реакций на тестовые последовательности можно построить как умножение выходного вектора на транспонированную проверочную матрицу линейного кода, пересечение которого с матрицей ошибок E пусто [1]. Т.к. мы хотим обеспечить максимально возможное сжатие информации, то возникает задача построения проверочной матрицы с описанным выше свойством, число строк которой минимально.

Для матрицы ошибок E подмножество π столбцов назовем столбцовым покрытием матрицы, если для любой строки существует столбец в π, который содержит единицу на пересечении с данной строкой.

Теорема. Пусть π - столбцовое покрытие матрицы ошибок E. Матрица H, в которой каждому столбцу из π соответствует строка, содержащая единственную единицу в данном столбце, есть проверочная матрица линейного кода, пересечение которого с множеством строк матрицы ошибок пусто.

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

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

1. Ю. Л. Сагалович "Алгебра, коды, диагностика". Издательство "МЦНТИ", Москва 1993.

Дополнительные материалы:

HTML

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

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:47:01)