Digital devices synthesized with the use of different binary logic bases could have different complexity depending on the component base technology. The Post-Yablonsky theorem defi nes which elementary boolean functions form basis. But there is a task to determine the common number of not redundant bases, i. e. bases which lose their functionally completeness if any function was removed. This problem is interesting not from mathematical point of view only, but from the side of developer too - he could choose the most acceptable way of implementation. The task of enumeration of all not redundant bases of classical binary logic is considered. Authors adduce formulas of correspondence between primary basis {AND; OR; NOT} and functions of stated bases. Also authors adduce an example of implementation of not redundant bases for logical circuit design.
boolean function, functionally complete system, basis, special class of functions
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. Sogomonyan E. S. Samoproveryaemye ustroystva i otkazoustoychivye sistemy / E. S. Sogomonyan, E. V. Slabakov. - M. : Radio i svyaz', 1989. - 208 s.
3. Sapozhnikov Val. V. Samoproveryaemye diskretnye ustroystva / Val. V. Sapozhnikov, Vl. V. Sapozhnikov. - SPb. : Energoatomizdat, 1992. - 224 s.
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. Proektirovanie i verifikaciya cifrovyh sistem na kristallah. Verilog & System Verilog / V. I. Hahanov, I. V. Hahanova, E. I. Litvinova, O. A. Guz'. - Har'kov : Novoe slovo, 2010. - 528 s.
9. Harris D. M. Digital Design and Computer Architecture / D. M. Harris, S. L. Har ris. - N. Y. : Morgan Kaufman, 2013. - 569 p.
10. Sapozhnikov Val. V. Teoriya diskretnyh ustroystv zheleznodorozhnoy avtomatiki, telemehaniki i svyazi : uchebnik dlya vuzov zh.-d. transporta / Val. V. Sapozhnikov, Yu. A. Kravcov, Vl. V. Sapozhnikov ; pod red. V. V. Sapozhnikova. - M. : UMK MPS, 2001. - 312 s.
11. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku : ucheb. posobie dlya vuzov / S. V. Yablonskiy ; pod red. V. A. Sadovnicheva. - 4-e izd., ster. - M. : Vysshaya shkola, 2003. - 384 s.
12. Belousov A. I. Diskretnaya matematika : uchebnik dlya vuzov / A. I. Belousov, S. B. Tkachev ; pod red. V. S. Zarubina, A. P. Krischenko. - 3-e izd., ster. - M. : Izd-vo MGTU im. N. E. Baumana, 2004. - 744 s.
13. Pospelov D. A. Logicheskie metody analiza i sinteza shem / D. A. Pospelov. - 3-e izd., pererab. i dop. - M. : Energiya, 1974. - 368 s.
14. Dmitriev V. V. Sintez triggerov na baze teorii konechnyh avtomatov / V. V. Dmitriev, K. S. Kononov, A. S. Perskiy // Avtomatika na transporte. - 2015. - № 1. - S. 73-83.
15. Gessel' M. Postroenie kombinacionnyh samoproveryaemyh ustroystv s monotonno nezavisimymi vyhodami / M. Gessel', A. A. Morozov, Val. V. Sapozhnikov, Vl. V. Sapozhnikov // Avtomatika i telemehanika. - 1994. - № 7. - S. 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. - Rp. 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. - Rp. 162-168. Teoreticheskie voprosy avtomatiki i informatiki 413 Avtomatika na transporte № 4, tom 1, dekabr' 2015
20. Gessel' M. Issledovanie kombinacionnyh samoproveryaemyh ustroystv s nezavisimymi i monotonno nezavisimymi vyhodami / M. Gessel', A. A. Morozov, Val. V. Sapozhnikov, Vl. V. Sapozhnikov // Avtomatika i telemehanika. - 1997. - № 2. - S. 180-193.
21. Sapozhnikov Val. V. Metod postroeniya kombinacionnyh samoproveryaemyh ustroystv s obnaruzheniem vseh odinochnyh neispravnostey / Val. V. Sapozhnikov, Vl. V. Sapozhnikov, M. Gessel', A. A. Morozov // Elektronnoe modelirovanie. - 1998. - T. 20. - № 6. - S. 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. Sapozhnikov Val. V. Samodvoystvennye diskretnye ustroystva / Val. V. Sapozhnikov, Vl. V. Sapozhnikov, M. Gessel'. - SPb. : Energoatomizdat, Sankt- Peterburgskoe otdelenie, 2001. - 331 s.
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. Gessel' M. Logicheskoe dopolnenie - novyy metod kontrolya kombinacionnyh shem / M. Gessel', A. V. Morozov, Val. V. Sapozhnikov, Vl. V. Sapozhnikov // Avtomatika i telemehanika. - 2003. - № 1. - S. 167-176.
28. Sapozhnikov Val. V. Osnovy tehnicheskoy diagnostiki : ucheb. posobie dlya vuzov zh.-d. transporta / Val. V. Sapozhnikov, Vl. V. Sapozhnikov. - M. : Marshrut, 2004. - 318 s.
29. Sapozhnikov Val. V. Sintez samodvoystvennyh diskretnyh sistem / Val. V. Sapozhnikov, Vl. V. Sapozhnikov, R. Sh. Valiev. - SPb. : Elmor, 2006. - 224 s.
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. Zakrevskiy A. D. Logicheskie osnovy proektirovaniya diskretnyh ustroystv / A. D. Zakrevskiy, Yu. V. Pottosin, L. D. Cheremisinova. - M. : Fizmatlit, 2007. - 592 s.
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 // Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tehnika i informatika. - 2012. - № 2. - S. 112-120.
34. Bennets R. Dzh. Proektirovanie testoprigodnyh logicheskih shem / R. Dzh. Bennets. - M.: Radio i svyaz', 1990. - 176 s.
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. Bibilo P. N. Logicheskoe proektirovanie diskretnyh ustroystv s ispol'zovaniem produkcionno-freymovoy modeli predstavleniya znaniy / P. N. Bibilo, V. I. Romanov. - Minsk : Belarus. navuka, 2011. - 279 s.
