Синтез контролепригодных программируемых логических матриц и проверяющих тестов тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Новиков, Яков Андреевич

• Новиков, Яков Андреевич
• кандидат технических наук
• 1984

Оглавление диссертации кандидат технических наук Новиков, Яков Андреевич

ВВЕДЕНИЕ.

Глава I. СОСТОЯНИЕ ИССЛЕДОВАНИЙ В ОБЛАСТИ ТЕСТОВОГО

ДИАГНОСТИРОВАНИЯ ПЛМ.

§ I.I. Математические модели исправных и неисправных ПЛМ.

§ 1.2. Краткий обзор методов построения проверяющих тестов для одиночных неисправностей ПЛМ.

§ 1.3. Анализ подходов к диагностированию кратных неисправностей ПЛМ.

- § 1.4. Выводы к главе 1.

Глава II. СИНТЕЗ КОНТРОЛЕПРИГОДНЫХ ПЛМ ПЕРВОГО РОДА.

§ 2.1. Постановка задачи.

§ 2.2. Компенсация неисправностей и устранение компенсации.

§ 2.3. Построение ПЛМ с ( к , 7)-свойством при 7 1,2,3,4}.

§ 2.4. Синтез ПЛМ, чувствительных ко всем одиночным коммутационным неисправностям.

Введение диссертации (часть автореферата) на тему «Синтез контролепригодных программируемых логических матриц и проверяющих тестов»

Совершенствование вычислительной техники и ее элементной базы" является одним из основных направлений социального и экономического развития СССР на I98I-I985 годы и на период до 1990 года.

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

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

Математическими моделями дефектов дискретных устройств являются неисправности, которые могут быть одиночными или кратными, состоящими из нескольких одиночных. Характерной особенностью современных БИС и, в частности, №1 является необходимость проверки кратных неисправностей, возникающих как на этапе изготовления БИС, так и в период их эксплуатации.

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

Целью работы является, во-первых, создание методов синтеза контролепригодных ПЛМ, обладающих коротким и легко конструируемым тестом, проверяющим одиночные и кратные коммутационные неисправности из заданного множества; во-вторых, разработка методов для нахождения таких тестов для синтезированных ПЛМ.

Задачи работы. Коммутационные неисправности можно разбить на четыре типа в зависимости от места их возникновения в структуре ПЛМ. В большинстве опубликованных научных работ, посвященных вопросам обеспечения проверки кратных неисправностей ПЛМ, рассматриваются контролепригодные ПЛМ двух видов. Для контролепригодных ПЛМ первого рода любой тест для одиночных коммутационных неисправностей заданных типов проверяет и все кратные неисправности, составленные из к. или менее таких одиночных. Контролепригодные ПЛМ второго рода обладают коротким и легко конструируемым полным тестом, проверяющим все возможные одиночные и кратные коммутационные неисправности.

К настоящему времени выделены некоторые классы контролепригодных ПЛМ первого рода, однако вопросы синтеза таких схем остаются малоизученными. Существует два подхода к построению контролепригодных ПЛМ второго рода. Первый подход, разрабатываемый, в основном, зарубежными специалистами, ориентирован на модификацию ПЛМ для облегчения контроля и использует известные приемы контро-лепригодного синтеза. Пока с его помощью не удалось добиться полной проверки модифицированной ПЛМ в целом. Второй подход, начало которому положил А.Д.Закревский, не связан с модификацией ПЛМ, а направлен на развитие теории дизъюнктивных нормальных форм (ДНФ). Он позволит полностью проверять ПЛМ. Для этого необходимо разработать метод синтеза контролепригодных IUIIvI второго рода и метод построения для них коротких полных тестов. Первый и второй подходы развиваются независимо друг от друга.

В диссертационной работе решаются следующие задачи:

1) выделить классы контролепригодных ПЛМ первого рода, отличающиеся от известных классов более высокой кратностью к-коммутационных неисправностей, составленных из одиночных неисправностей заданных типов и проверяемых любым тестом для этих одиночных неисправностей; разработать методы реализации произвольной системы булевых функций с помощью схемы из любого выделенного и из любого известного классов;

2) развивая второй подход выделить класс контролепригодных ПЖ второго рода; разработать метод синтеза ПЛМ из выделенного класса и метод построения для них коротких полных тестов;

3) совместно рассмотреть оба подхода к синтезу контролепри-4 годных ПЖ второго рода с целью построения модифицированных ПЖ, сочетающих достоинства тех схем, которые получаются при применении этих подходов по отдельности.

Научная новизна. Все полученные в диссертационной работе научные результаты являются новыми. На защиту выносятся следующие основные результаты:

1) выделенные классы контролепригодных ПЖ первого рода, отличающиеся от известных классов более высокой кратностью ^ неисправностей, составленных из одиночных неисправностей заданных типов и проверяемых любым тестом для этих одиночных неисправностей; для известных классов к = 3, в то время как для одних из выделенных классов к равно числу всех одиночных неисправностей рессматриваемых типов, а для других к £ { 5,7^;

2) методы реализации произвольной системы булевых функций с помощью контролепригодных ПЖ первого рода из любого выделенного и из любого известного классов;

3) выделенный класс контролепригодных ПЛМ второго рода и верхняя оценка для длины полного теста, которым обладает схема из этого класса;

4) метод преобразования произвольной ПЛМ в схему из выделенного класса и верхняя оценка для числа дополнительных полюсов, достаточных для такого преобразования;

5)способ построения в разновидности ПЛМ с памятью — синхронизированной ПЛМ с "окном" - переключателя состояний, позволяющего элементы памяти ПЛМ перевести в любое заданное состояние с помощью одного установочного набора;

6) метод преобразования синхронизированной ПЛМ с "окном" к контролепригодному виду и построения для полученной ГШМ полного теста; верхние оценки для длины конструируемого теста, для суммарного числа дополнительных входных и выходных полюсов и для числа незадействованных промежуточных шин, достаточных для такого преобразования;

7) методы построения универсальных и индивидуальных полных тестов для ПЛМ, не содержащей входного буфера из дешифраторов;

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

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

Новые практические результаты работы составляют программы, которые реализуют предложенные в диссертации методы построения контролепригодных ПЛМ первого рода (осуществляющие устранение не-обнаружимых неисправностей в ПЛМ ) и метод нахождения проверяющих тестов для Ш1М с "окном", содержащей переключатель состояний. Программы написаны в языке программирования ЛЯПАС-М для ЕС ЭВМ.

Практическая ценность результатов работы. Результаты работы: методы, программы и способы модификации ШШ, - разработаны с учетом существующих потребностей современной практики проектирования дискретных устройств. Созданные программы работают в пакетном и в диалоговом режимах. Общение с машиной в диалоговом режиме ведется в простой и удобной для проектировщика форме. Разработанные программы обладают высоким быстродействием и дают результаты высокого качества. Например, программа повышения контролепригодности Ш1М позволяет устранять необнаружимые неисправности в ШШ реальных размеров ценой добавления всего лишь одного, двух дополнительных входных полюсов и не более двух дополнительных выходных полюсов.

Все это подтверждается результатами статистических испытании программ и результатами их использования в практике проектирования.

Внедрение результатов работы. Разработанные программы, реализующие предложенные в диссертации методы повышения контролепригодности ШШ, внедрены на одном из предприятий г. Москвы в составе системы ТЕЛУР (система построения проверяющих тестов и повышения контролепригодности Ш1М на основе решения логических уравнений) и на одном из предприятий г. Чебоксары в составе системы Синтез ШШ (система реализации дискретных устройств в базисе Ш1М). Обе системы разработаны в Институте технической кибернетики АН БССР. Рассчетный экономический эффект от внедрения программы повышения контролепригодности Ш1М составляет около 24,2 тыс. рублей. Соответствующие справки о внедрении приложены в диссертационной работе.

Адробация диссертации. Материалы диссертации заслушивались на III Международном симпозиуме ТК "Техническая диагностика" ИМЕКО (Москва, октябрь, 1983), на УТ Международной конференции "Диагностическое обеспечение цифровых систем" ( Брно, ЧССР, сентябрь, 1983), на Всесоюзной конференции "Проблемы теоретической кибернетики" ( Саратов, июнь, 1983), на Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем" (Ереван, сентябрь, 1983), на Республиканской конференции "Автоматизированное техническое проектирование электронной аппаратуры" (Каунас, июнь, 1982), на школе-семинаре "Автоматизация логического проектирования" (Севастополь, сентябрь, 1982), на Межвузовской научно-технической конференции ( Москва, МИРЭА, май, 1983), на конференциях молодых ученых и специалистов (Минск, 1981, 1982), на Общемосковском городском семинаре по технической диагностике (Москва, ИПУ, май, 1983) и неоднократно на семинаре "Теория дискретных автоматов" ( Минск, ИТК АН БССР, 19811984).

Публикации. По теме диссертации опубликовано 14 работ [I-I43, в том числе 10 статей и 4 тезисов докладов. Все работы выполнены без соавторов.

Структура и объем диссертации, диссертация содержит введение, четыре главы с выводами, заключение, библиографию из 144 наименований и приложения. Основное содержание диссертации изложено на 140 страницах, приложения - на 36 страницах. В диссертацию включено 10 рисунков и 4 таблицы.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Новиков, Яков Андреевич

4.3.2. Выводы к главе ГУ.

1. Совместное рассмотрение существующих подходов к синтезу контролепригодных ПЛМ второго рода весьма перспективно.

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

ЗА1ШЧЕНИЕ

Новые научные результаты, полученные в диссертационной работу.

1. Выделены классы контролепригодных ПЛМ первого рода, отличающиеся от известных классов более высокой кратностью коммутационных неисправностей заданных типов, проверяемых любым тестом для одиночных неисправностей этих типов. Для известных классов k - 3, в то время как для одних из выделенных классов L равно числу всех одиночных неисправностей заданных типов, а для других & 5,7J".

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

3. Выделен класс контролепригодных ПЛМ второго рода, обладающих полным тестом Г .длины не больше, чем (с^ /Z )((<%- 1) где т. - число входных полюсов, а £ - число промежуточных шин ПЛМ.

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

Г"* . Дана верхняя оченка Я ^ , где ^ ' ДЛЛ ЧИ°~ ла дополнительных полюсов, достаточных для такого преобразования. Точные значения Я ^ приведены в таблице I. 1

5. Предложен метод преобразования разновидности ПЛМ с памятью - синхронизированной ПЛМ с "окном" - к такому виду, когда все ее элементы памяти можно перевести в любое заданное состояние с помощью одного установочного набора. Преобразование требует одного дополнительного входного полюса и )} дополнительных промежуточных шин, где V - число линий обратной связи.

6. Предложен метод контролепригодного синтеза ПЛМ с "окном" и метод построения для нее полного теста. Даны верхние оценки для длины полного теста, для числа дополнительных входных и выходных полюсов и для числа дополнительных промежуточных шин, используемых при преобразовании произвольной ПЛМ с "окном" к контролепригодному виду.

7. Предложены методы построения универсальных и индивидуальных полных тестов для ПЛМ, не содержащей входного буфера из дешифраторов.

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

Быводы к диссертационной работе.

1. Все контролепригодные ILffiil первого рода, принадлежащие выделенным и известным классам, оказываются чувствительными ко всем одиночным коммутационным неисправностям заданных типов, т.е. согласно принятой в диссертационной работе терминологии, -7 - чувствительными, где 7 - множество заданных типов неисправностей. При синтезе J- чувствительных схем для {1,2] £ 7 или (1,3,4) £ 7 в общем случае неизбежно увеличение сложности ПЛМ по числу входных или выходных полюсов, поскольку существуют такие системы F булевых функций, которые нельзя реализовать 7-чувствительной ПЛМ с тем же числом входных и выходных полюсов, сколько аргументов и функций имеет система F .

2. Увеличение числа входных или выходных полюсов при синтезе контролепригодных ПЛМ второго рода является необходимой платой за неумение эффективно решать /V/3-полную задачу построения кратчайшей системы ДНФ для произвольной системы булевых функций.

3. Верхняя оценка для числа дополнительных входных и выходных полюсов, которые используются предложенным методом для синтеза контролепригодных ПЖ второго рода с числом промежуточных шин - ^ , совпадает с установленной в диссертационной работе аналогичной оценкой для числа дополнительных полюсов, достаточных для построения любой контролепригодной ШИЛ первого рода, содержащей ^ промежуточных шин и обладающей коротким тестом всего лишь для неисправностей кратности 3 и менее. Это свидетельствует об эффективности предложенного метода синтеза контролепригодных ПЖ второго рода.

4. Впервые предпринятое в диссертационной работе совместное рассмотрение двух существующих подходов к синтезу контролепригодных ПЖ второго рода весьма перспективно.

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

6. Эффективность предложенных в диссертационной работе методов повышения контролепригодности ПЛМ подтверждается данными экспериментального исследования программных реализаций этих методов и результатами внедрения программ на предприятиях страны.

Список литературы диссертационного исследования кандидат технических наук Новиков, Яков Андреевич, 1984 год

1. Новиков Я.А. К проверке кратных неисправностей ПЛМ. — В кн.: Вычислительная техника. Тезисы докладов республиканской конференции. Каунас, 1982, с.136.

2. Новиков Я.А. Об одной задаче обнаружения неисправностей в программируемой логической матрице. В кн.: Автоматизация технической подготовки производства. Минск: Ин-т техн.кибернетики АН БССР, 1982, вып.З, с.117-124.

3. Новиков Я.А. К достижению безызбыточности ПЛМ. В кн.: Алгоритмы логического проектирования. Минск: Ин-т техн.кибернетики АН БССР, 1983, с.97-105.

4. Новиков Я.А. Об одной задаче программирования логических матриц. — В кн.: Современные вычислительные и автоматизированные системы. Минск: ЕГУ,1980, с.112-129.

5. Новиков Я.А. Об одном подходе к обеспечению проверки кратных неисправностей ПЛМ. Автоматика и вычислительная техника, 1983, № 3, с.33-39.

6. Новиков Я.А. Необходимые условия существования корней некоторых типов в матричном логическом уравнении Xх Y = С. Известия АН БССР, сер. физ-матем.наук, 1984, № I, с.112.

7. Новиков Я.А. Построение кратчайшей системы ДНФ по заданному множеству элементарных конъюнкций. В кн.: Автоматизация процессов проектирования. Минск: Ин-т техн.кибернетики АН БССР, 1983, вып. I, с.50-56.

8. Novikov Ya.A. Design and check of completely tested PLA's.-Digest of papers. Technical diagnostics Third IJUEKO Internatoinal Symposium. Moscow. October, 198J, pp. 121-123.

9. Новиков Я.А. Построение контролепригодной ПЛМ и полного теста. В кн.: Труды конференции "Diagnostika a zabezpeceni cislicovych systemu (FTSD)", Brno, 1983, c. 200-206.

10. Новиков Я.А. К полной проверке программируемых логических матриц. I. Автоматика и телемеханика, 1984, £ 6, с.146-153.

11. Новиков Я.А. К полной проверке программируемых логических матриц.II. Автоматика и телемеханика, 1984, №7, с. 137-146.

12. Новиков Я.А, Построение полных тестов для двухъярусных транзисторных схем. В кн.: Тезисы докладов всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем". Ч. II, Ереван, 1983, с. I2I-I22.

13. Новиков Я.А. К тестовой проверке ПЛМ» Микроэлектроника, 1984, том. 13, вып. 5, с. 432-438.

14. X5#Ramanatha K.S., Biswas N.N. A design for complete testability of programmable logic arrays. IEEE Test Conference. Digest of papers, 1у82, pp. 67-74.

15. Баранов С.И., Синев В.Н. Программируемые логические матрицы в цифровых системах. Зарубежная радиоэлектроника, 1979, 12, с. 65-81.

16. Баранов С.И., Бакралов А.А. Применение программируемых логических матриц в цифровой технике. Зарубежная радиоэлектроника, 1982, Jfc 6, с. 67-79.

17. Закревский А.Д. Логический синтез каскадных схем, М.: Наука, 1981, 416 е.

18. Скляров В.А. Синтез автоматов на матричных БИС. Минск: Наука и техника, 1984, 287 с. .

19. Muroga S. Design and switching theory. New York: John Wiley & Song, 1979, 617 p.

20. Timrn V. Im. Blickpunkt: ROM, PROIvl and PLA's. -Elektronic, 1976, H. 5, s. 38-47.

21. Закревский А.Д. Алгоритмы синтеза диеретных автоматов. М.: Наука, 197I, 512 е.

22. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1974.363 е.

23. Проектирование цифровых вычислительных машин. Под.ред. С.А.Майорова, М.: Высшая школа, 1972. 344 е.

24. Закревский А.Д. и др. Синтез асинхронных автоматов на ЭВМ. Минск: Наука и техника, 1975, 184 е.

25. Уткин А.А. Анализ логических сетей и техника булевых вычислений. Минск: Наука и техника, 1979, 152 е.

26. Ostapko D.L., Hong S.J. Fault analysis and test generation for programmable logic arrays (PLA's). IEEE Transact, on Computers, 1979, Vol. c.-28, No. 9, pp. 617-627.

27. Уткин А.А. Построение проверяющих тестов для программируемых логических матриц. В кн.: Алгоритмы логического проектирования. Шнек: Ин-т техн.кибернетики АН БССР, 1983, с.83-96.

28. Закревский А.Д. Диагностика неисправностей ПЛМ В кн.: Труды конференции " Diagnostika a zabezpeceni cislicovych systemu

29. FTSD)» Брно, 1979, c.211-218.-15431. Удалов В.И. Разработка методов анализа функциональных возможностей и тестового диагностирования настраиваемых логичес-: ких структур. Дис. на соиск. учен.степ.канд.техн.наук. Рига, 1981, 227 е.

30. Баранов С.И., Синев В.Н. Автоматы и программируемые матрицы. Минск: Высшая школа, I960, 136 с.

31. Скляревич А.Н., Удалов В.И. Общая модель логической неисправности дискретных устройств. В кн.: Процессы и устройства управления в сетях связи. АН СССР ИЛИ, М.: Наука, 1982, с.32-39.

32. Карибский В.В., Пархоменко П.П., Согомонян Е.С., Халчев В.Ф. Под ред. П.П.Пархоменко. Основы технической диагностики. М.: Энергия, 1976, 464 с.

33. Гольдман Р.С., Чипулис В.II. Техническая диагностика цифровых устройств. М.: Энергия, 1976, 224 е.

34. Скляревич А.Н. Реккуррентный синтез тестов проверки комбинационных автоматов. Рига: Зинатне, 1981, 186 е.

35. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем. Труды Математического института им.В.А.Стеклова, 1958, т.50, с.270-360.

36. Вейцман И.Н., Жук В.Е., Флеров А.Б. Вероятностная система синтеза контролирующих тестов на логические схемы. Вопросы радиоэлектроники, Сер. ЭВТ, 197I, вып.6, с.22-26.

37. Балашов В.В., Муллина Н.Ш., Никитина Л.В. и др. Автоматизированная система построения тестов функционального и диагностического контроля логических схем. М.: ИТМ и ВТ, 1976.

38. Биргер А.Г., Бояршинов А.В., Гурвич Е.Т. и др. Автоматизированная система контроля и диагностики цифровых ячеек. — Обмен опытом в радиопромышленности, 1978, вып.4-5, с.40-46.

39. Гробман Д.М., Сергеев Б.Г., Филинов Е.И. Автоматизированная система контроля цифровых схем. Тезисы докладов 7 Всесоюзного совещания по проблемам управления, Шнек, 1977. - Минск,1977,т.2, с.320-323.

40. Smith J.E. Detection of faults in programmable logic arrays. IEEE 'Transact, on Computers, 1979, Vol. c.-28, No. 11, pp. 845-853.

41. Muchldorf E.I., Savkar A.D. LSI logic testing an overview. - IEEE Transact, on Computers, 1981, Vol. c.-pO, No. 1, pp. 1-17.

42. Seshu S., Freeman D.N. The diagnosis of asynchronous seqwential switching systems. IRE Transact, on electron. Computers, 1962, EC-11, No. 4, pp. 459-465.

43. Seshu S. On an improved diagnosis programm. IEEE Transact. on Electron. Computers, 1965» SC-14, No. 1, pp. 76-79.

44. Armstrong D.B. A deductiv method for simulating faults in logic circuits. IEEE Transact, on Computers, 1972, Vol.с.-21, No. 5» PP. 464-471.

45. Автоматизированное проектирование цифровых устройств. Под ред. Бадулина С.С. М.: Радио и связь, 1981, 240 е.

46. Голыничев В.П., Звягин В.Ф., Немолочнов О.Ф. Регулярный метод синтеза тестовых последовательностей. Установочная последовательность. Автоматика и телемеханика, 1981, № 9, с.162-172.

47. Roth J.P. Diagnosis of automata failures: a calculus and a method. IBM Journ. of Research and Development, 1966, Vol. 10, No. 4, pp. 278-291.

48. Roth J.P., Bouricius W.G., Schneider P.R. Programmed algorithms to compute tests to detect and distinguish between failures in logic circuits. IEEE Transact, on Electronic Computers, 1967, EC-16, No. 5, pp. 567-580.

49. Armstrong D.B. On finding a nearly minimal set of fault detection tests for combinational logic nets. IEEE Transact, on Electronic Computers, 1966, EC-15, No. 1, pp. 66-73.

50. Sellers Р.Е., Hsiao M.Y., Bearnson L.W. Analyzing errors with the Boolean difference. IEEE Transact, on Computers, 1968, Vol. с.-17, No. 7, PP. 676-683.

51. Chiang A.C.L., Seed I.S., Banes A.V. Path sesitization, partial Boolean difference, and automated fault diagnosis. IEEE Transact, on Computers, Vol. с.-21, 1972, No. 2, pp. 189-195.

52. Reed I.S. Boolean difference calculus and fault finding.-SIAM Journ. on Appl. Math., 1973, Vol. 24, No. 1.

53. Бессонов А.А., Стешкович H.T., Турчина Е.Д. Автоматизация проектирования контролирующих тестов. Л.: Энергия, 1976,222 С • •

54. Халчев В.Ф. Повышение контролепригодности дискретных устройств. Состояние проблемы. Измерения, контроль, автоматизация, I960, № 1,2.

55. Люлькин А.Е., Павлова Т.Г. Синтез тестов для программируемых логических матриц. Микроэлектроника, 1983, том 12, вып.4, с.299-305.

56. Somenzi Б1., Silvano G, Mezzalama М., Prinetta P. Fault PIA's testing based on a partitioning algorithm. Digest of papers FTCS-13 June 28-30, 1983, Milano, pp. 430-433.

57. Eichelberger E.B., Lindbloom E.L. A heuristic test-pattern generator for programmable logic arrays. IBM Journ. of Research and Development, 1980, Vol. 24, No. 1, pp. 13-22.

58. Закревский А.Д. Логические уравнения. Мн.: Наука и техника, 1975, 96 е.

59. Убар P.P. Анализ диагностических тестов для комбинационных логических схем методом обратного прослеживания неисправностей. Автоматика и телемеханика, 1977, f 8, с.168-176.

60. Волынский М.Б., Новоселов В.Г. Обнаружение и поиск неисправностей программируемых логических матриц. Микроэлектроника,1983, т.12, вып.4, с.306-312.

61. Ramanatha K.S., Biswas N.N. An on-line algorithm for the location of crosspoint faults in programmable logic arrays. -IEEE Transact, on Computers, 1983, Vol. С.-32, No. 5, pp. 438-444.

62. Slidhar Т., Hayes J.P. Design of easily testable bit-sliced systems. IEEE Transact, on Computers, 1981, Vol. c.-30, No. 11, pp. 842-854.

63. Painke H. LSI Test - schom beim 1С - Desing terucksichtigt. - Elektronic, 1980, H. 26, s. 69-74.

64. Agarwal V.K., Fung A.S.F. Multiple fault testing of large circuits by single fault test sets. IEEE Transact, on Computers, 1981, Vol. с.-ЗО, No. 11, pp. 855-865.

65. Биргер А.Г., Гурвич E.T., Кузнецов С.С. Проверка кратных неисправностей комбинационных устройств. Автоматика и телемеханика, 1975, № 8, с.II3-I2I.

66. Каравай М.Ф. Алгоритм построения проверяющего теста для кратных неисправностей по структуре комбинационного устройства. -Автоматика и телемеханика, 1975, № I, с.162-170.

67. Коган И.В. 0 построении проверяющих и диагностических тестов для комбинационных устройств. Автоматика и вычислительная техника, 1974, W I, с.37-42.

68. Биргер А.Г. О проверке исправности многовыходного комбинационного устройства. Автоматика и телемеханика, 1977, F- 5, с.140-146.

69. Чжен Г., Мэннинг Е., Метц Г. Диагностика отказов цифровых вычислительных систем. М.: Мир, 1972, 232 с.

70. Миллер Р. Теория переключательных схем. T.I, М.: Наука, 1970.

71. Пархоменко П.П. Основные задачи технической диагностики.-В кн.: Техническая диагностика. М.: Наука, 1972, с.7-21.

72. Fujiwara Н., Kinoshita К. Design of diagnosable sequential machines utilizing extra outputs. IEEE Transact, on Computers, 197^, Vol. C.-23, No. 2, pp. 138-145.

73. Friedman A.D. Fault detection in redundant circuits. -IEEE Transact, on Computers, 1967, EC-16, No. 2, pp. 99100.

74. Schertz P.R., Metze G. On the design of multiple fault diagnosable networks. IEEE Transact, on Computers, 1971, Vol. с.-20, No. 11, pp. 1361-1364.

75. Palit A., Sen Gupta A., Basu M.S., Choudhury A.K. On design of fault diagnostis networks for combinational logic circuits. Electronics, 1975, vol. 39, No. 1, pp. 25-32.

76. Richards D.L. Efficient exercising of swithing elements in nets of identical gates. Journ. of ACM, 1973, Vol. 20, No. 1, pp. 88-111.

77. Williams T.W., Parker K.P. Design for testabilitya survey. IEEE Transact, on Computers, 1982, Vol. с.-31, No. 1, pp. 2-17.

78. Hayes J.P. , Friedman A.D. Test point placement to symplify fault detection. IEEE Transact, on Computers, 1974, Vol. с.-23, No. 7, PP. 727-733.

79. Saluja K., Reddy S.M. On minimally testable logic networks. IEEE Transact, on Computers, 1974, Vol. c. - 23, No. 5, pp. 332-334.

80. Sutton J.C., Bredeson J.G. Minimal redundant logic for high reliability and irredundant testability. IEEE Transact, on Computers, 1980, Vol. C.-29, No. 7, pp. 648-637.

81. Fujiwara H., Nagao Y., Sasao Т., Kinoshita K. Easily testable sequential machines with, extra inputs. IEEE Transact, on Computers, 1973, Vol. c.-24, No. 8, pp. 821-826.

82. Bhattacharyya A. On a novel approach of fault detection in an easily testable sequential machine with extra inputs and outputs.- IEEE Transact, on Computers, 1983, Vol. C.-32, No. 3, pp. 323-323.

83. Pradheh D.K. Sequential netwok design using extra inputs for fault detection. IEEE Transact, on Computers, 1983, vol. C.-32, No. 3, PP. 319-323.

84. Ramamoorthy C.V., Chang L.C. System segmentation for the parallel diagnosis of computers. IEEE Transact, on Computers, 1971, Vol. c.-20, No. 3, pp. 261-271.

85. Akers S.B. Partitionong for testability. J. Deign Automat fault-tolerant comput., 1977, Vol. 1, No. 2.

86. Матросова А.Ю. Построение полного теста для схем, синтезированных методом факторизации. Автоматика и вычислительная техника, 1978, № 5, с.42-46.

87. Паршина Н.А. Синтез легко диагностируемых схем методом факторизации тупиковых ДНФ. Автоматика и вычислительная техника, 1980, № 4, с.68-74.

88. Гольдман Р.С., Майоров С.А., Чипулис В.В. Тестовая проверка бесповторных комбинационных схем. В сб.: Дискретный анализ. М.: Наука, 1968, вып.12, с.3-21.

89. Каравай М.Ф. Диагноз кратных неисправностей древовидных схем произвольного базиса. Автоматика и телемеханика, 1973, № I, с.173-181.

90. Халчев В.Ф. Обнаружение неисправностей в древовидной логической сети с памятью. Автоматика и телемеханика, 1975, 8, с.143-149.

91. Berger I., Kohavi Z. Fault detection in fanout-free combinational networks. IEEE Transact, on Computers, 1975» Vol. с.-22, No. 10, pp. 908-914.

92. Fantauzzi G., Marsella A. Multiple-fault detection and location in fan-out free combinational circuits. IEEE Transact, on Computers, 1974, Vol. c.-25, No. 1, pp. 48-55*

93. El-Zig Y.M., Stephen Y.H.Su. Fault diagnosis of MOS combinational networks. IEEE Transact, on Computers, 1982, Vol. с.-51, No. 2, pp. 129-159.

94. Reddy S.M. Easily testable realization for logic functions. IEEE Transact, on Computers, 1972, Vol. C.-21, No. 11, pp. 1185-1188.

95. Betancourt К. Derivation of minimum test sets for unate logical circuits. IEEE Transact, on Computers, 1971, Vol. c. -20, No. 11, pp. 1264-1269.

96. Reddy S.M. Complete test sets for logic functions. -IEEE Transact, on Computers, 1973, Vol. c.-22, No. 11,pp. 1016-1020.

97. Akers S.B. Universal test sets for logic networks. -IEEE Transact, on Computers, 1973, Vol. c.-22, No. 9, PP« 835-839.

98. Зандере JI.Я. Синтез легко диагностируемых комбинационных схем относительно одного класса константных неисправностей.-Автоматика и вычислительная техника, I9d3, № I, с.36-40.

99. Горяшко А.П. 0 синтезе схем с минимальной трудоемкостью тестирования. Автоматика и телемеханика, 1981, № I, с.145-153.

100. Асафьев Ю.В., Бойкевич A.M., Волчек В.А., Горяшко А.П. Синтез контролепригодных схем направление, продиктованное интегральной технологией. - Известия АН СССР. Техническая кибернетика, 1981, № 4, с.146-154.

101. Горяшко А.П. Некоторые результаты теории синтеза легко тестируемых схем. Известия АН СССР. Техническая кибернетика, 1932, Щ 2, с.139-150.

102. ПО. Eichelherger Е.В. Method of level sensitive testing a functional system. U.S. Patent 3761695, Sept. 25, 1973.

103. Смирнов Н.И., Стручков А.А., Судовцев П.А. Диагностика неисправностей в цифровой радиоаппаратуре на БИС. Зарубежная радиоэлектроника, № I, 1979, с.53-60.

104. Erohwerk p.A. Signature analysis: A new digital field service method. Hewlett-Packard J., 1977» May, pp. 28.

105. Smith J.E. Measure of the effectiveness of fault signature analysis. IEEE Transact, on Computers, 1980, Vol. c.29, No. 6, pp. 510-514.

106. Халчев В.Ф. Преобразование структурного автомата с памятью к виду, удобному для контроля. Автоматика и телемеханика, 1975, № 6, с.189-197.

107. Konemann В., Mucha J., Zmiehoff G. Built-in logic block observation technique. IEEE J. Solid-State Circuits, 1980, Vol. SC-15, No. 6.

108. Mc.Clyskey E.J., Bozorgui-Nesbat S. Design for autonomous test. IEEE Transact, on Computers, 1981, Vol. c.30, No. 11, pp. 866-875.

109. Закревский А.Д. Диагностика неисправностей регулярных технологических структур. В кн.: Труды конференции "Diagnost. zabezp. cisl. systemu"}BpHO, 1981, с.6-14.

110. Закревский А.Д. К построению проверяющих тестов для ПЛМ. Автоматика и вычислительная техника, 1982, № 2, с.73-76.

111. Волынский М.Б., Новоселов В.Г. Метод построения проверяющего теста для программируемых логических матриц. Микроэлектроника, 1983, т.12, вылЛ, с.55-64.

112. Agarwal V.K. Multiple fault detection in programmable logic arrays. IEEE Transact, on Computers, 1980, Vol. С.-29, No. 6, pp. 518-523.

113. Ramanatha K.S., Biswas N.N. Testability of undetectable cross-point faults in programmable logic arrays. IEEE Transact, on Computers, 1983, Vol. c.-32, No. 6, pp. 551-557.

114. Fujiwara H., Kinoshita K., Hiroshi 0. Universal test sets for programmable logic arrays. Digest of papers FTCS-10, October 1-3, 1980, Kyoto Japan, pp. 137-142.

115. Hong S.J., Ostapko D.L. FITPLA: A programmable logic arrays for function independent testing. Digest of papers FTCS-10, October 1-3, 1980, Kyoto Japan, pp. 131-136.

116. Hong S.J., Ostapko D.L. Logic array with testing circuitry. U.S. Patent 3958110, May, 1976.

117. Daesh W., Mucha J. A hardware approach to self-testing of lage logic arrays. IEEE Transact, on Computers, 1981,

118. Vol. С.-30, No. 11, pp. 829-833.

119. Saluja K.K., Kinoshita K., Fujiwara H. A multiple fault testable design of programmable logic arrays. Digest of papers FTCS-11 June 24-26, 1982, Portland, pp. 44-47.

120. Горяшко A.II. Синтез программируемых- логических матриц с малой трудоемкостью тестового диагностирования. Известия АН СССР. Техническая кибернетика, 1984, Jfc I, с. 201-206.

121. Brad К. P.L.A. logic checking. New Electron, 1982, Vol. 15, No. 4, pp. 54-57.

122. Кук С.А. Сложность процедур вывода теорем. В кн.: Кибернетический сборник. М.: Мир, 1975, вып. 12, с. 5-Г5.

123. Уткин А.А. Универсальный подход к построению проверяющих тестов. В кн.: Автоматизация анализа и моделирования логических сетей. Минск: Ин-т техн. кибернетики АН БССР, 1981, с.5-16.

124. Шнейдер А.А. Экспериментальное исследование алгоритмов раскраски вершин графа. В кн.: Автоматизация логического проектирования дискретных устройств. Шнек: Ин-т техн. кибернетики АН БССР, 1980, вып. 2, с. 86-94.

125. Шнейдер А.А. Классификация и экспериментальное сравнение алгоритмов раскраски вершин графа. В кн.: Автоматизация технической подготовки производства. Минск: Ин-т техн. кибернетики АН БССР, 1982, вып. 3, с. 94-107.

126. Каулиньш Д.Я. Полнота проблемы нахождения кратчайшей д.н.ф. булевой функции. В кн.: Теория конечных автоматов и ее приложения. Рига: Зинатне, 1978, вып. 9, с. 33-38.

127. Коробков В.И. О монотонных функциях алгебры логики, -В кн.: Проблемы кибернетики, М., 1965, вып. 13, с. 5-28.

128. Оре 0. Теория графов. М.: Наука, 1980, 336 с.

129. Берж К. Теория графов и ее приложения. М.: Иностранная литература, 1962, 319 с.

130. Уилсон Р. Введение в теорию графов. М.: Мир, 1977, 207 с.

131. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978, 631 с.

132. Шнейдер А.А. Алгоритмы раскраски вершин графа. В кн.:

133. Алгоритмы решения логико-комбинаторных задач. Минск: Ин-т техн. кибернетики АН БССР, 1980, с. 31-36.