Методы синтеза самопроверяемых дискретных систем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Никитин, Константин Владимирович

• Никитин, Константин Владимирович
• кандидат технических наук
• 2003

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

ВВЕДЕНИЕ.

1. ОСНОВНЫЕ ПОНЯТИЯ.

1.1. Булевы функции, конечные автоматы, логические схемы.

1.2. Программируемые логические элементы.

1.3. Методы тестового и функционального диагностирования.

1.4. Обзор методов проектирования дискретных систем.

1.4.1. Методы проектирования самопроверяемых схем.

1.4.2. Обзор методов проектирования детекторов кодов.

1.5. Выводы по главе.

2. ПРОЕКТИРОВАНИЕ САМОПРОРВЕРЯЕМЫХ СХЕМ.

2.1. Однонаправленные неисправности самопроверяемой синхронной последовательностной схемы.

2.2. Получение интервального описания.

2.3. Монотонные и частично-монотонные системы.

2.4. ПЛБ реализация синхронной последовательностной схемы, представленной системой BDD - графов.

2.5. Однонаправленное проявление неисправностей класса W в комбинационной схеме.

2.6 Результаты экспериментов.

2.7. Выводы по главе.

3. ПРОЕКТИРОВАНИЕ САМОТЕСТИРУЕМОГО ДЕТЕКТОРА (M,N)-КОДОВ.

3.1. Метод разложения множества кодовых слов (т,п) - кода.

3.2. Реализация самотестируемого детектора кодовых слов (т,п) - кода для т> 1.

3.3. Обоснование самотестируемости схемы С.

3.4. Реализация (1,п)-детекторов.

3.5. Результаты сравнения с другими известными реализациями детекторов т,п) -кодов.

3.6. Выводы по главе.

4. ОЦЕНКА СЛОЖНОСТИ ДЕТЕКТОРА.

4.1. Подсчет числа ПЛБ.

4.2. Неупорядоченные коды.

4.2.1. Построение детекторов неупорядоченных кодов.

4.2.2. Обсуждение свойства самотестируемости детектора.

4.3. Сокращение дерева формулы А.

4.4. Выводы по главе.

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

Актуальность проблемы.

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

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

Разработка методов проектирования самопроверяемых дискретных систем, ориентированных на использование новой элементной базы является, безусловно, актуальной.

Целью настоящей работы является разработка методов проектирования полностью самопроверяемых дискретных систем, ориентированных на использование программируемых логических блоков (ПЛБ). Для ее достижения решены две задачи.

1. Выполнено исследование известного метода логического синтеза комбинационной составляющей несамопроверяемого синхронного последовательностного устройства на возможность его применения к синтезу комбинационной составляющей самопроверяемого синхронного последовательностного устройства. Метод основан на покрытии системы BDD-графов, представляющей функции переходов-выходов синтезируемого синхронного автомата, программируемыми логическими блоками (ПЛБ). Его применение при синтезе самопроверяемых устройств требует кодирование неупорядоченными кодами (в частности, равновесными) символов выходного алфавита и состояний автомата и наблюдения выходов синхронного самопроверяемого устройства и его линий обратных связей.

2. Разработан метод синтеза самотестируемых комбинационных детекторов равновесных кодов.

Поставленные задачи решаются в предположении, что каждый ПЛБ реализует либо одну (любую) булеву функцию от к+\ переменной, либо две (любые) булевы функции от к переменных.

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

Научную новизну полученных в работе результатов определяют:

- Обоснование возможности применения метода логического синтеза комбинационной составляющей несамопроверяемого синхронного последовательностного устройства к синтезу комбинационной составляющей самопроверяемого синхронного последовательного устройства. Речь идет о методе, основанном на покрытии системы BDD-графов, представляющей функции переходов-выходов автомата, программируемыми логическими блоками (ПЛБ). Его применение при синтезе самопроверяемых устройств требует кодирования символов выходного алфавита автомата и его состояний неупорядоченными кодами (например, равновесными) и наблюдения выходов самопроверяемого устройства и его линий обратных связей.

- Декомпозиционный метод проектирования самотестируемых комбинационных детекторов равновесных кодов в базисе ПЛБ. Детектор кодов является самотестируемым относительно кратных константных неисправностей на полюсах ПЛБ. Проблема синтеза самотестируемых детекторов в базисе ПЛБ исследуется впервые.

- Алгоритмы сокращения числа допустимых кодовых слов на входах самотестируемых детекторов.

- Формула оценки сложности детектора кодов, то есть числа ПЛБ, необходимых для реализации детектора.

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

Практическая значимость работы.

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

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

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

Реализация полученных результатов.

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

1. Госбюджетная тема Сибирского физико-технического института при ТГУ, программа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем", 1995-2000 гг., раздел "Разработка методик и аппаратуры исследований".

2. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95 1 21 и №59-1-7 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

3. Научный проект Минобразования России «Решение логических уравнений на BDD-графах в задачах диагностики».

Результаты работы также используются в курсе лекций "Диагностика дискретных устройств" на факультете прикладной математики и кибернетики Томского государственного университета (ТГУ).

Апробация работы и публикации.

Научные результаты, составляющие основу данной работы, по мере их получения обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования, кафедры защиты информации факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ.

Результаты работы представлялись на следующих научных конференциях:

1. Третья всероссийская конференция с международным участием «Новые информационные технологии в исследовании дискретных структур» (Россия, Томск 2000);

2. The Fourth International Conference on Computer-added Design of Discrete Devices (CAD DD'2001) (Minsk, Republic of Belarus, November 14-16,2001);

3. Международная конференция «Компьютерные науки и информационные технологии» (Россия, Саратов 14-18 мая 2002г.). iL

4. 7 IEEE International On-Line Testing Workshop (Taormina, Italy,

July 9-11,2001); th

5. 9 IEEE International On-Line Testing Workshop, Greece, Kos, July 79, 2003.

По результатам выполненных исследований опубликовано 7 печатных работ.

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 33 рисунка и 14 таблиц. Объем диссертации составляет 115 стр., в том числе: титульный лист - 1 стр., оглавление - 2 стр., основной текст - 104 стр., библиография из 90 наименования - 8 стр.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Никитин, Константин Владимирович

4.4. Выводы по главе

1. Получены формулы для подсчета числа ПЛБ для некоторых частных случаев детекторов. Формулы позволяют оценить сложность самотестируемых детекторов для произвольных (т,п)-кодов.

2. Установлено, что сложность детекторов, реализуемых предложенным в работе декомпозиционным методом, растет пропорционально квадрату длины п (т,и)-кода.

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

ЗАКЛЮЧЕНИЕ

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

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

Предложен подход к синтезу самопроверяемых синхронных последовательных схем, основанный на покрытии системы BDD-графов программируемыми логическими блоками (ПЛБ). Данный подход допускает различные модификации, ориентированные на оптимизацию структуры синхронной последовательностной схемы. Множество неисправностей W, включает в себя одиночные константные неисправности на входных полюсах синхронной последовательностной схемы, одиночные константные неисправности на ее выходных линиях и линиях обратных связей и одиночные функциональные неисправности ПЛБ. Доказано, что покрытие системы BDD - графов, представляющее функции переходов-выходов синхронной схемы, состояния и выходы которой закодированы неупорядоченными кодами (в частности равновесными), обеспечивает однонаправленное проявление неисправностей из рассматриваемого множества, то есть доказана самопроверяемость синхронной последовательностной схемы относительно множества неисправностей W в условиях наблюдения ее выходов и линий обратных связей.

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

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

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

Предложен метод подсчета числа ПЛБ, необходимых для реализации самотестируемого детектора (т,п)-кодов. Получены формулы для подсчета числа ПЛБ для некоторых частных случаев детекторов. Формулы позволяют оценить сложность самотестируемых детекторов для произвольных (т,п)-кодов.

Установлено, что сложность детекторов, реализуемых предложенным в работе декомпозиционным методом, растет пропорционально квадрату длины п (т,я)-кода.

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

Список литературы диссертационного исследования кандидат технических наук Никитин, Константин Владимирович, 2003 год

1. В.В. Соловьев. Проектирование функциональных узлов цифровых схем на программируемых логических устройствах // ПК ООО «Бестпринт». Минск-1996.

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

3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979. — 272 с.

4. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Элементы теории автоматов // Учебное пособие. — М.: Изд-во Минск. Ун-та, 1978. 216 с.

5. Г.П. Агибапов, A.M. Оранов. Лекции по теории конечных автоматов // Изд-во Томского Ун-та. Томск, 1984. -185 с.

6. ACT™ Family FPGA Data Book // Actel Corporation. Sunny vale, California.-1992.

7. FPGA Data Book and Design Guide // Ibid. 1993.

8. XILIX. The Programmable Logic Data Book // San Jose, California. 1996.

9. Component Selector Guide. Altera Corporation. San Jose, California. -1995.

10. Согомонян E. С., Слабаков E. В. Самопроверяемые схемы и системы защищенные от неисправностей // М.: Радио и связь, 1989. -158 с.

11. McCluskey Е. J. Verification Testing-A Pseudo-Exhausted Test Technique // IEEE Tran. on Computers. Vol.C-33, - №6.-1984.-P. 541-546.

12. Tang D. Т., Chen C. L. Iterative Exhaustive Pattern Generation for Logic Testing // IBM J. Res. Develop. Vol. 28, - №2. -1984. - P. 212-219.

13. Min Y., Li Z. Pseudo-Exhausted Testing Strategy for Large Combinational Circuits // Computer Systems Science and Engineering. Vol. 1, - №4. -1986.-P. 213-220.

14. Furuya K. A Probabilistic Approach to Locally Exhaustive Testing // Tran. of the IEICE. Vol. E-72. - 1989. - P. 656-660.

15. Hellebrand S. Sythese vollstanding testbarer Schaltungen // VDI Verlag. Reihe 10,-№177.-1991.

16. Rajski J., Tyszer J. Recursive Pseudo-Exhaustive Test Pattern Generator // IEEE Tran. on Computers. Vol. 42, -№12. - 1993. - P. 1517-1521

17. Wunderlich H. J. Self Test Using Uniquiprobable Random Patterns // Proc. IEEE Int. Symposium on Fault Tolerant Computing. 1987. - P. 258-263.

18. Wunderlich H. J. Multiple Distributions for Biased Random Test Patterns // Proc. IEEE Int. Test Conference. -1988. P. 236-244.

19. Hartmann J. The Random Testability of the n-Input AND Gate // Proc. 8th Annual Symposium on Theoretical Aspects of Computer Science. 1991. - P. 488-498.

20. Hartmann J. On Numerical Weight Optimization for Random Testing // Proc. EDAC-EUROASIC. 1993. - P. 223-230.

21. Pateras S., Rajski J. Generation of Correlated Random Patterns for the Complete Testing of Synthesized Multi-Level Circuits // Proc. 28th Design Automation Conference. 1991. - P. 347-352.

22. Pateras S., Rajski J. Cube-Contained Random Patterns and their Application to the Complete Testing of Synthesized Multi-Level Circuits // Proc. IEEE Int. Test Conference. 1991. - P. 473-482.

23. McCluskey E. J. Built-in Self-Test Structures // IEEE Design & Test of Computers.-April 1985.-P. 29-36.

24. McCluskey E. J. Built-in Self-Test Techniques // IEEE Design & Test of Computers. April 1985. - P. 21-28.

25. Bardell P. H., McAnney W. H., Savir J. Built-in Test for VLSI. Pseudorandom Techniques. New York: John Wiley&Sons Inc. -1987.

26. Abramovici M. A., Breuer M. A., and Friedman A. D. Digital Systems Testing and Testable Design. New York: W. H. Freeman and Company. -1990.

27. Wunderlich H. J. Hochintegrierte Schaltungen: Prufgerechter Entwurf und Test // Berlin: Springer Verlag. - 1991.

28. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part1: Principles // IEEE Design & Test of Computers. Vol.10, -№1. - 1993. -P. 73-82.

29. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part 2: Applications // IEEE Design & Test of Computers. Vol.10, - №2. - 1993. -P. 69-77.

30. Savir J., Bardell P. H. Built-in-Self-Test: Milestones and Challenges // VLSI design. Vol. 1, - №1. - 1993. - P. 23-44.

31. Parag K. Lala. Self-Checking and Fault-Tollerant Digital Design // University of Arkansas.

32. W. K. Fuchs, J. A. Abraham. A Unified Ap-proach to Concurrent Error Detection in Highly Structured Logic Arrays // Proc. Of 1984 Int. Test Conference P. 4-9.

33. H. Fujiwara. A New PLA Design for Universal Testability // IEEE Transaction on Computers. Vol. C-33, No. 8 - August 1984 - P. 745-750.

34. К. C. Wei, J. J. Sheu and B. D. Liu. Low Over-head Design for Programmable Logic Array with Testability // Int. J. Electronics 1994 - vol. 77, No. 2 - P. 241-250.

35. Levin and M. Karpovsky. On-Line Self-Checking of Microprogram Control Unit // 4th IEEE Intl. On-Line Testing Workshop Capri, Italy - July 1998 -P. 152-156.

36. Yu. Matrosova, S. A. Ostanin. Self-Checking Synchronous FSM Network Design // 4th IEEE Intl. On-Line Testing Workshop Capri, Italy - July 1998 -P. 162-166.

37. Levin and V. Sinelnikov. Self-Checking of FPGA-based Control Units // Proceedings of 9th Great Lakes Symposium on VLSI Ann Arbor, Michigan - March 4-6 -1999 IEEE - P. 292-295.

38. Levin, A. Yu. Matrosova, V. Sinelnikov, S. A. Ostanin. Totally Self-Checking FPGA based FSM // 5th IEEE Intl. On-Line Testing Workshop Rhodes, Greece- July 1999- P. 5.

39. Fadi Y. Busaba and Parag K. Lala. Self-Checking Combinational Circuit

40. Design for Single and Unidirectional Multibit Error // JETTA, 5 1994 - P. 19-28.

41. Bryant R.E. Graph-Based Algorithms for Boo-lean Function Manipulation // IEEE Trans, on Corp. Vol. C-35, № 8 - 1986 - P. 677-691.

42. Пархоменко П. П., Согомонян Е. С. Основы технической диагностики. — М.: Энергоиздат, 1981. 320с.

43. Согомонян Е. С. Построение дискретных устройств с диагностикой в процессе функционирования // Автоматика и телемеханика. -№11 1970 -С. 153-160.

44. Аксенова Г. П., Согомонян Е. С. Синтез схем встроенного контроля для автоматов с памятью // Автоматика и телемеханика. №9 - 1971 — С. 170-179.

45. Carter W. С., Schneider P. R. Design of Dynamically Checked Computers // JFIP Congress. 1968 - P. 878-883.

46. Horwarth J. Checking Sequential Logic Circuits // US PS 4556976, G06F 11/00.-1985.

47. Reinert D. Entwurf und Diagnose komplexer digitaler Systeme. Berlin. VEB Verlag Technik. -1983.

48. Siewiorek D. P., Schwarz R. S. The Theory and Practice of Reliable System Design. Bedford: Digital Press. -1982.

49. Sellers F. F., Hsiao M. J., Bearnson L. W. Error Detecting Logic for Digital

50. Computers. New York: McGraw-Hill. - 1968.

51. Minero R. H., Anello A. J., Furey R. G., Palounek L. R. Checking by pseudoduplication//US PS 3660646, G06F 11/00.-1972.

52. Murayama N. Matrix Collating System // US PS 3548376, НОЗК 13/34. -1970.

53. Betrand J. C., Gambiasi N., Mercier J. J. Totally Self-Checking Sequential Circuits // Proc. Int. Sympos. «Discrete Systems». Riga: Zinatne. - Bd. 2. -1974-P. 36-44.

54. V.V. Dimakopoulos et al., On TSC Checkers for m-out-of-n Codes // IEEE Trans. Comput.-Vol. 44-Aug. 1995 -P. 1055-1059.

55. C. Efstathiou and C. Halatsis. Efficient Modular Design of m-out-of-2m TSC Checkers, for m=2K-l, K>2 // Electron. Lett., Vol. 21 Nov. 1985 - P. 10821084.

56. Paschalis Efficient Structured Design of Totally Self-Checking M-out-of-N Code Checkers with N>2M and M=2K-1 // Int. J. Electronics Vol. 77 - Aug. 1994-P. 251-257.

57. A.M. Paschalis, D. Nicolos, and C. Halatsis. Efficient Modular Design of TSC Checkers for m-out-of-n Codes // IEEE Trans. Comput., Vol. C-37 — March 1988- P. 301-309.

58. D.A. Anderson and G. Metze. Design of Totally Self-Checking Check Circuits for m-out-of-n Codes // IEEE Trans. Comput., Vol. C-22 — March 1973- P. 263-269.

59. S.J. Piestrak. The Minimal Test Set for Sorting Networks and the Use of Sorting Networks in Self-Testing Checkers for Unordered Codes // Dig.Pap.FTCS-20, Newcastle upon Tyne, Uk. June 1990 - P. 457-464.

60. S.J. Piestrak. Design Method of Totally Self-Checking Checkers for m-out-of-n Codes//Dig. Pap. FTCS-13, Milan, Italy- Junel983 P. 162-168.

61. S.J. Piestrak. Design of Fast Self-Testing Checkers for m-out-of-2m and m-out-of-(2m±l) Codes // Int. J. Electronics, Vol. 74 Feb. 1993 - P. 177199.

62. S.J. Piestrak. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes // Scientific Papers of Inst, of Techn. Cybern. of Techn. Univ. of Wroclaw, No. 92, Ser.: Monographs No. 24, Oficyna Wyd. Polit. Wroct., Wroclaw 1995 - P. 112.

63. V.V. Sapozhnikov and VI.V. Sapozhnikov. Universal Algorithm for Synthesizing Self-Checking Testers for Constant-Weight Codes // Probl. Inf. Transm., Vol. 20, No. 2 1984 -P. 128-137.

64. V.V. Sapozhnikov and Vl.V. Sapozhnikov. Self-Checking Checkers for Balanced Codes // Autom. Remove Control, Vol. 53 March 1992 - P. 321348.

65. J.E. Smith. The Design of Totally Self-Checking Check Circuits for a Class of Unordered Codes // J. Des. Autom. Fault-Tolerant Comput., Vol. 2 — Oct. 1977-P. 321-342

66. C.Y. Lee. Representation of switching circuits by binary-decision programs // Beil. Syst. Tech. J., vol. 38 July 1959 - P. 985-999.

67. S. B. Akers. Binary decision diagrams // IEEE Trans. Comput., vol. C-27 -June 1978-P. 509-516

68. M.R. Garey and D.S. Johnson. Computers and Intractability. A Guid to the Theory of NP-Completeness. New York: Freeman, 1979.

69. F.J. Hill and G.R. Peterson. Introduction to Switching Theory and Logical Design. New York: Wiley, 1974.

70. J.P. Roth, Computer Logic, testing, and Verification. Rockville, MD: Computer Science Press, 1980.

71. R. Brayton. Fast recursive Boolean function manipulation // in Proc. Int. Symp. Circuits and Syst., IEEE. Rome, Italy May 1982 - P. 58-62.

72. B.M.E. Moret. Decision trees and diagrams // Ass. Comput. Mach., Comput. Surv., vol. 14-Dec. 1982-P. 593-623.

73. S. Fortune, J. Hopcroft and E.M. Sehmidt. The complexity of aquivalence and containment for tree single variable program schemes // in Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 62,

74. Goos. Hartmannis, Ausiello and Boehni. Eds. Berlin: Springer-Verlag. 1978 -P. 227-240.

75. R.W. Payne. Reticulation and other methods of reducing the size of printed diagnostic keys // J. Gen. Microbiol., vol. 98 -1977 P. 595-597.

76. R. Brayton et al., Logic manipulation Algorithms for VLSI Synthesis, Hingham, MA: Kluver, 1984.

77. C.E. Shannon. A symbolic analysis of relay and switching circuits // Trans. AIEE, vol. 57-P. 713-723.

78. C.S. Wallace. A suggestion for s fast multiplier // IEEE Trans. Electron. Comput., vol. EC-13 Jan. 1964-P. 14-17.

79. A.V. Aho, J.E. Hoperolt and J.D. Ullman. The Design and analysis of Computer Algorithms. Reading. M.A.: Addition-Wesley, 1974.

80. J.S. Jephson, R.P. McQuarrie and R.E. Vogelsberg. A three-level design verification system // IBM Syst. J., vol. 8, no. 3 1969 - P. 178-188.

81. TTL Data Book, Texas Instruments, Dallas, TX, 1976.

82. M. Rowan-Robinson, Cosmology. London: Oxford University Press, 1977.

83. S.B. Akers. Functional testing with binary decision diagrams // in Proc. Sth. Ann. IEEE Conf. Fault-Tolerant Comput. 1978 - P. 75-82.

84. R.P. Brent and H.T. Kung. The aria-time complexity of binary multiplication // J. Ass. Comput., Mach., vol. 28 July 1981 - P. 521-534

85. H. Abelson and P. Andreae. Information transfer and aria-time tradeoffs for VLSI multiplication // Commun. Ass. Comput. Mach., vol. 23 Jan. 1980 — P. 20-23.

86. Матросова А.Ю., Никитин K.B. Проектирование самотестируемого детектора неупорядоченных кодов // Докл. Международной конференции Компьютерные науки и информационные технологии. Саратов, 2002. с. 44-45.

87. К.В. Никитин. Об оценке сложности комбинационного детектора равновесных кодов // Третья всероссийская конференция с международным участием Новые информационные технологии висследовании дискретных структур, Томск, 2000 — С. 252-256.

88. Матросова А.Ю., Никитин К.В. Синтез самопроверяемого детектора равновесных кодов // Вестник Томского государственного университета №271-2000.-С. 101-105.

89. A. Matrosova, К. Nikitin, О. Goloubeva. Totally self-checking FSM design based on multilevel synthesis methods and FPGA implementation // 7th IEEE International On-Line Testing Workshop, Taormina, Italy July 9-11, 2001 -P. 144.

90. А.Ю. Матросова, К.В.Никитин. Синтез самотестируемого детектора (m,n) кодов на программируемых логических блоках // Вестник Томского государственного университета. Приложение. №6. 2003. — С. 124-136.

91. A. Matrosova, V. Ostrovsky, I. Levin, К. Nikitin. Designing FPGA based Self-Testing Checkers for m-out-of-n Codes // 9th IEEE International On-Line Testing Workshop, Greece, Kos. July 7-9,2003 - P. 49-53.