APPLICATION OF THE HAMMING CODE IN THE PROBLEM OF INCREASING FAULT TOLERANCE OF LOGIC CIRCUITS
Abstract
Currently, when designing integrated circuits, developers have to take into account a very
large number of dissimilar factors that are associated with ensuring the necessary performance
characteristics, occupied area, energy efficiency, yield, convenience of subsequent testing, requirements
for universality, autonomy, and so on. One of the main factors is the reliability of operation.
This criterion comes to the fore for critical applications, as well as for devices operating
under the influence of destabilizing factors. To provide increased reliability, different methods and
approaches are used at different levels of abstraction. Some of them can be applied at the design
stage. One of the main methods for improving the reliability of integrated circuits at the design
stage is the use of tools from the theory of error-correcting coding.The traditional field of application
of error-correcting codes is the control of the integrity of stored and transmitted information.
Combinational logic circuits, on the other hand, change information and do not have storage elements.
Combinational logic circuits implement look-up tables at the gate level, which unambiguously
assign a certain output value to each input action. Nevertheless, the use of error-correcting
codes for constructing error-tolerant combinational circuits turns out to be very effective. This
requires the introduction of additional combinational blocks into the circuit, which provide coding,
decoding, control, and in some cases correction of errors arising in the circuit. The paper
investigates the efficiency of using Hamming codes in relation to the construction of fault-tolerant
combinational circuits. The paper considered classical Hamming code and his main modification -
weighted code with summation without carries for the implementation of fault-tolerant combinational
circuits. Means have been developed for the automated synthesis of fault-tolerant circuits
based on these codes. Structural redundancy and reliability characteristics of the resulting circuits
are investigated. Comparison with traditional method triple modular redundancy is carried out.
Estimating functions are derived for redundancy and the probability of missing an error.
References
[Formalization of the task of debugging digital systems projects], Informatsionnye tekhnologii
[Information Technologies], 2014, No. 9, pp. 3-10.
2. Ivannikov A.D., Stempkovskiy A.L. Matematicheskaya model' otladki proektov slozhnykh
tsifrovykh skhem i mikrosistem na osnove predstavleniya poslednikh v vide semeystva
statsionarnykh dinamicheskikh sistem [Mathematical model of debugging projects of complex
digital circuits and microsystems based on the representation of the latter in the form of a family
of stationary dynamic systems], Problemy razrabotki perspektivnykh mikro- i
nanoelektronnykh sistem (MES) [Problems of development of promising micro- and
nanoelectronic systems (MES)], 2014, No. 2, pp. 123-128.
3. Gavrilov S.V., Telpukhov D.V. Automated Evolutionary Design of Fault-Tolerant Logic Circuits,
Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem (MES) [Problems
of development of promising micro- and nanoelectronic systems (MES)], 2019, No. 1, pp. 2-6.
4. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Sintez samoproveryaemykh skhem
vstroennogo kontrolya na osnove logicheskogo dopolneniya do ravnovesnogo koda "2 iz 5“
[Synthesis of self-testable integrated control schemes based on the logical complement to the
equilibrium code "2 out of 5“], Izvestiya vysshikh uchebnykh zavedeniy. Priborostroenie
[News of higher educational institutions. Instrumentation], 2021, Vol. 64, No. 3, pp. 163-175.
5. Mitra S., McCluskey E.J. Which Concurrent Error Detection Scheme to Choose?, Proc. International
Test Conference, 2000, pp. 985-994.
6. Gessel' M., Morozov A.V., Sapozhnikov V.V., Sapozhnikov V.V. Logicheskoe dopolnenie -
novyy metod kontrolya kombinatsionnykh skhem [Logical addition - a new method of control
of combinational circuits], Avtomatika i telemekhanika [Automation and telemechanics], 2003,
No. 1, pp. 167-176.
7. Pivovarov D.V. Postroenie sistem funktsional'nogo kontrolya mnogovykhodnykh
kombinatsionnykh skhem metodom logicheskogo dopolneniya po ravnovesnym kodam [Construction
of systems of functional control of multi-output combinational circuits by the method
of logical addition according to equilibrium codes], Avtomatika na transporte [Automation in
transport], 2018, Vol. 4, No. 1, pp. 131-149.
8. Khetagurov Ya.A., Rudnev Yu.P. Povyshenie nadezhnosti tsifrovykh ustroystv metodami
izbytochnogo kodirovaniya [Improving the reliability of digital devices by redundant coding
methods]. Moscow: Energiya, 1974, 270 p.
9. Touba N.A., McCluskey E.J. Logic Synthesis of Multilevel Circuits with Concurrent Error
Detection, IEEE Trans. CAD, July 1997, Vol. 16, pp. 783-789. DOI: 10.1109/43.644041.
10. Jha N.K., Wang S.J. Design and Synthesis of Self-Checking VLSI circuits, IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, July 1993, Vol. 12, No. 6,
pp. 878-887. DOI: 10.1109/43.229762.
11. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John
Wiley & Sons, 2006, 720 p.
12. Sogomonyan E.S., Slabakov E.V. Samoproveryaemye ustroystva i otkazoustoychivye sistemy
[Self-testing devices and fault-tolerant systems]. Moscow: Radio i svyaz', 1989, 208 p.
13. Efanov D., Sapozhnikov V., Blyudov A., Sapozhnikov Vl. On the Problem of Selection of Code
with Summation for Combinational Circuit Test Organization, Proceedings of IEEE East-West
Design and Test Symposium, EWDTS 2013, 2013, pp. 6673133.
14. Stempkovskiy A.L., Tel'pukhov D.V., Demeneva A.I., Zhukova T.D. Marshrut proektirovaniya
skhem funktsional'nogo kontrolya kombinatsionnykh ustroystv [The route of designing
schemes of functional control of combinational devices], Vestnik Ryazanskogo
gosudarstvennogo radiotekhnicheskogo universiteta [Bulletin of the Ryazan State Radio Engineering
University], 2018, pp. 92-98.
15. Zhukova T.D. Razrabotka sistemy avtomatizirovannogo proektirovaniya SFK na osnove
metodov izbytochnogo kodirovaniya [Development of a computer-aided design system based
on redundant coding methods], Problemy razrabotki perspektivnykh mikro- nanoelektronnykh
sistem (MES) [Problems of development of promising micro-nanoelectronic systems (MES)],
2020, pp. 51-57. DOI: 10.31114/2078-7707-2020-4-51-57.
16. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody Khemminga v sistemakh
funktsional'nogo kontrolya logicheskikh ustroystv [Hamming codes in systems of functional
control of logical devices]. St. Petersburg.: Nauka, 2018, 151 p.
17. Tel'pukhov D.V., Demeneva A.I., Zhukova T.D., Khrushchev N.S. Issledovanie i razrabotka
sistem avtomatizirovannogo proektirovaniya skhem funktsional'nogo kontrolya
kombinatsionnykh logicheskikh ustroystv [Research and development of computer-aided design
systems for functional control circuits of combinational logic devices], Elektronnaya
tekhnika. Seriya 3: Mikroelektronika [Electronic engineering. Series 3: Microelectronics],
2018, No. 1 (169), pp. 15-22.
18. Stempkovsky A.L., Zhukova T.D., Telpukhov D.V. and Gurov S.I. CICADA: A New Tool to Design
Circuits with Correction and Detection Abilities, 2021 International Siberian Conference on Control
and Communications (SIBCON), 2021, pp. 1-5. DOI: 10.1109/SIBCON50419.2021.9438900.
19. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Vzveshennyy kod s summirovaniem bez
operatsiy perenosa dlya resheniya zadach tekhnicheskoy diagnostiki diskretnykh sistem
[Weighted code with summation without transfer operations for solving problems of technical
diagnostics of discrete systems], Priborostroenie [Instrumentation], 2018, No. 4.
20. Available at: https://ddd.fit.cvut.cz/www/prj/Benchmarks/ (accessed 16 August 2021).
21. Clifford Wolf, «Yosys Open SYnthesis Suite». Available: http://www.clifford.at/
yosys/about.html.
