Дискретные устройства, синтезированные с использованием различных базисов двоичной логики, могут иметь различную сложность технической реализации в зависимости от технологии изготовления элементной базы. Какие из элементарных функций алгебры логики образуют базис, определяет теорема Поста - Яблонского. Однако возникает задача определения общего количества неизбыточных базисов, т. е. таких базисов, удаление из которых хотя бы одной функции нарушает их функциональную полноту. Эта задача интересна не только с математической точки зрения, но и с точки зрения разработчика - он может выбрать наиболее приемлемый способ технической реализации дискретного устройства из существующих способов. В данной работе рассматривается задача перечисления неизбыточных базисов классической двоичной логики. Приводятся формулы, определяющие соответствие между функциями основного базиса {И; ИЛИ; НЕ} и функциями неизбыточных базисов. Дается пример практического использования неизбыточных базисов для построения логических устройств автоматики.
булева функция, функционально полная система, базис, особенный класс функций
1. McCluskey E. J. Logic Design Principles : With Emphasis on Testable Semicustom Circuits / E. J. McCluskey. - N. Y. : Prentice Hall PTR, 1986. - 549 p.
2. Согомонян Е. С. Самопроверяемые устройства и отказоустойчивые системы / Е. С. Согомонян, Е. В. Слабаков. - М. : Радио и связь, 1989. - 208 с.
3. Сапожников Вал. В. Самопроверяемые дискретные устройства / Вал. В. Сапожников, Вл. В. Сапожников. - СПб. : Энергоатомиздат, 1992. - 224 с.
4. Goessel M. Error Detection Circuits / M. Goessel, S. Graf. - L. : McGraw-Hill, 1994. - 261 p.
5. Abramovici M. Digital System Testing and Testable Design / M. Abramovici, M. A. Breuer, A. D. Friedman. - Comp. Sc. Press, 1998. - 652 p.
6. Fujiwara E. Code Design for Dependable Systems : Theory and Practical Applications / E. Fujiwara. - John Wiley & Sons, 2006. - 720 p.
7. Wang L-T. System-on-Chip Test Architectures : Nanometer Design for Testa bility / L.-T. Wang, C. E. Stroud, N. A. Touba. - Morgan Kaufmann Publishers, 2008. - 856 p.
8. Проектирование и верификация цифровых систем на кристаллах. Verilog & System Verilog / В. И. Хаханов, И. В. Хаханова, Е. И. Литвинова, О. А. Гузь. - Харьков : Новое слово, 2010. - 528 с.
9. Harris D. M. Digital Design and Computer Architecture / D. M. Harris, S. L. Har ris. - N. Y. : Morgan Kaufman, 2013. - 569 p.
10. Сапожников Вал. В. Теория дискретных устройств железнодорожной автоматики, телемеханики и связи : учебник для вузов ж.-д. транспорта / Вал. В. Сапожников, Ю. А. Кравцов, Вл. В. Сапожников ; под ред. В. В. Сапожникова. - М. : УМК МПС, 2001. - 312 с.
11. Яблонский С. В. Введение в дискретную математику : учеб. пособие для вузов / С. В. Яблонский ; под ред. В. А. Садовничева. - 4-е изд., стер. - М. : Высшая школа, 2003. - 384 с.
12. Белоусов А. И. Дискретная математика : учебник для вузов / А. И. Белоусов, С. Б. Ткачев ; под ред. В. С. Зарубина, А. П. Крищенко. - 3-е изд., стер. - М. : Изд-во МГТУ им. Н. Э. Баумана, 2004. - 744 с.
13. Поспелов Д. А. Логические методы анализа и синтеза схем / Д. А. Поспелов. - 3-е изд., перераб. и доп. - М. : Энергия, 1974. - 368 с.
14. Дмитриев В. В. Синтез триггеров на базе теории конечных автоматов / В. В. Дмитриев, К. С. Кононов, А. С. Перский // Автоматика на транспорте. - 2015. - № 1. - С. 73-83.
15. Гессель М. Построение комбинационных самопроверяемых устройств с монотонно независимыми выходами / М. Гессель, А. А. Морозов, Вал. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. - 1994. - № 7. - С. 148-160.
16. Busaba F. Y. Self-Checking Combinational Circuit Design for Single and Unidirectional Multibit Errors / F. Y. Busaba, P. K. Lala // Journal of Electronic Testing: Theory and Application. - 1994. - Issue 5. - Pp. 19-28.
17. Piestrak S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes / S. J. Piestrak. - Wrocław : Ofi cyna Wydawnicza Politechniki Wrocłavskiej, 1995. - 111 p.
18. Saposhnikov Val. V. Design of Self-Checking Unidirectional Combinational Circuits with Low Area Overhead / Val. V. Saposhnikov, Vl. V. Saposhnikov, A. Morosov, M. Göessel // Proc. IEEE Int. On-Line Testing Workshop (IOLTW). - Biarritz, France, 1996. - Рp. 56-67.
19. Saposhnikov Vl. V. Self-Dual Parity Checking - A New Method for On-Line Testing / Vl. V. Saposhnikov, A. Dmitriev, M. Goessel, Val. V. Saposhnikov // 14th IEEE VLSI Test Symposium, Princeton, New Jersey, USA, April 28 - May 1, 1996. - Рp. 162-168. Теоретические вопросы автоматики и информатики 413 Автоматика на транспорте № 4, том 1, декабрь 2015
20. Гессель М. Исследование комбинационных самопроверяемых устройств с независимыми и монотонно независимыми выходами / М. Гессель, А. А. Морозов, Вал. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. - 1997. - № 2. - С. 180-193.
21. Сапожников Вал. В. Метод построения комбинационных самопроверяемых устройств с обнаружением всех одиночных неисправностей / Вал. В. Сапожников, Вл. В. Сапожников, М. Гессель, А. А. Морозов // Электронное моделирование. - 1998. - Т. 20. - № 6. - С. 70-80.
22. Morosov A. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs / A. Morosov, Val. V. Saposhnikov, Vl. V. Saposhnikov, M. Goessel // VLSI Design. - 1998. - Vol. 5. - Issue 4. - Pp. 333-345.
23. Saposhnikov Val. V. A New Design Method for Self-Checking Unidirectional Combinational Circuits / Val. V. Saposhnikov, A. Morosov, Vl. V. Saposhnikov, M. Göessel // Journal of Electronic Testing: Theory and Application. - 1998. - Vol. 12. - Issue 1-2 (February / April). - Pp. 41-53.
24. Matrosova A.Yu. Self-Checking Synchronous FSM Network Design with Low Overhead / A.Yu. Matrosova, I. Levin, S. A. Ostanin // VLSI Design. - 2000. - Vol. 11. - Issue 1. - Pp. 47-58.
25. Сапожников Вал. В. Самодвойственные дискретные устройства / Вал. В. Сапожников, Вл. В. Сапожников, М. Гёссель. - СПб. : Энергоатомиздат, Санкт- Петербургское отделение, 2001. - 331 с.
26. Matrosova A. Survivable Self-Checking Sequential Circuits / A. Matrosova, I. Levin, S. Ostanin // Proc. of 2001 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT 2001), Oct. 24-26, San Francisco, CA, 2001. - Pp. 395-402.
27. Гессель М. Логическое дополнение - новый метод контроля комбинационных схем / М. Гессель, А. В. Морозов, Вал. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. - 2003. - № 1. - С. 167-176.
28. Сапожников Вал. В. Основы технической диагностики : учеб. пособие для вузов ж.-д. транспорта / Вал. В. Сапожников, Вл. В. Сапожников. - М. : Маршрут, 2004. - 318 с.
29. Сапожников Вал. В. Синтез самодвойственных дискретных систем / Вал. В. Сапожников, Вл. В. Сапожников, Р. Ш. Валиев. - СПб. : Элмор, 2006. - 224 с.
30. Göessel M. New Methods of Concurrent Checking: Edition 1 / M. Göessel, V. Ocheretny, E. Sogomonyan, D. Marienfeld. - Dordrecht: Springer Science+Business Media B. V., 2008. - 184 p.
31. Lala P. K. An Introduction to Logic Circuit Testing / P. K. Lala. - USA, Arkansas, Texarkana : Morgan & Claypool Publishers, 2009. - 99 p.
32. Закревский А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. - М. : Физматлит, 2007. - 592 с.
33. Matrosova A.Yu. Selection of the flip-flops for partial enhanced scan techniques / A.Yu. Matrosova, A. V. Melnikov, R. V. Mukhamedov, S. A. Ostanin, V. Singh // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2012. - № 2. - С. 112-120.
34. Беннетс Р. Дж. Проектирование тестопригодных логических схем / Р. Дж. Беннетс. - М.: Радио и связь, 1990. - 176 с.
35. Sentovich E. M. SIS: A System for Sequential Circuit Synthesis / E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, A. Sangiovanni-Vincentelli // Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkeley, 4 May 1992. - 45 p.
36. Gopalakrishan P. Direct Transistor-Level Layout for Digital Blocks / P. Gopalakrishan, R. A. Rutenbar. - Boston : Kluwer Academic Pubishers, 2004. - 125 p.
37. Бибило П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. - Минск : Беларус. навука, 2011. - 279 с.
