Modified codes with weighted-transitions summation in concurrent error detection systems of combinational circuits
https://doi.org/10.15514/ISPRAS-2017-29(5)-3
Abstract
A method for constructing modified codes with summation of weighted transitions between bits in data vectors occupying neighboring positions is proposed. New codes with summation have the same number of check bits as the classic Berger codes, but they detect more errors in data vectors. Modified codes with summation of weighted transitions in comparison with Berger codes also have improved error detection characteristics in the area of small multiplicity. In addition, for some values of the lengths of information vectors codes can be constructed with the detection of any twofold and any triple errors. The authors developed a method for synthesizing concurrent error detection systems of combinational circuits, based on the analysis of the topology of the object of diagnosis with the selection of groups of checkable outputs, taking into account the properties of error detection by modified codes with summation of weighted transitions. An algorithm for the synthesis of a concurrent error detection systems has been developed.
About the Authors
V. V. Sapozhnikov
Emperor Alexandex I St. Petersburg state transport university
Russian Federation
Russian Federation
Vl. V. Sapozhnikov
Emperor Alexandex I St. Petersburg state transport university
Russian Federation
Russian Federation
D. V. Efanov
Emperor Alexandex I St. Petersburg state transport university
Russian Federation
Russian Federation
References
1. McCluskey E.J. Logic Design Principles: With Emphasis on Testable Semicustom Circuits. N.J., Prentice Hall PTR, 1986, 549 p.
2. Sogomonjan E.S., Slabakov E.V. [Self-checking devices and fault-tolerant systems]. Moscow: Radio i svjaz', 1989, 207 p. (in Russian).
3. Goessel M., Graf S. Error Detection Circuits. London: McGraw-Hill, 1994, 261 p.
4. Mitra S., McCluskey E.J. Which Concurrent Error Detection Scheme to Сhoose? Proceedings of International Test Conference, 2000, USA, Atlantic City, NJ, 03-05 October 2000, pp. 985-994, doi: 10.1109/TEST.2000.894311.
5. Berger J.M. A Note on Error Detection Codes for Asymmetric Channels. Information and Control, 1961, Vol. 4, Issue 1, pp. 68-73, doi: 10.1016/S0019-9958(61)80037-5.
6. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995, 111 p.
7. Das D., Touba N.A. Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes. Journal of Electronic Testing: Theory and Applications, 1999, Vol. 15, Issue 1-2, pp. 145-155, doi: 10.1023/A:1008344603814.
8. Bljudov A.A., Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. On Codes with Summation of Unit Bits In Concurrent Error Detection Systems. Automation and remote control, 2014, Vol. 75, Issue 8, pp. 1460-1470, doi: 10.1134/S0005117914080098.
9. Freiman C.V. Optimal Error Detection Codes for Completely Asymmetric Binary Channels. Information and Control. 1962, Vol. 5, Iissue 1, pp. 64-71, doi: 10.1016/S0019-9958(62)90223-1.
10. Burkatovskaya Yu.B., Butorina N.B., Matrosova A.Yu. Self-Testing Checker Design for Arbitrary Number of Code Words of (m,n) code. Proceedings of the 10th International Baltic Electronic Conference (BEC`2006), Tallinn, Estonia, October 2-4, 2006, pp. 183-186, doi: 10.1109/BEC.2006.311093.
11. Slabakov E.V., Sogomonjan E.S. Self-check computing devices and systems (survey). Automation and remote control, 1981, Vol. 42, Issue 11, pp. 1551-1566.
12. Nicolaidis M., Zorian Y. On-Line Testing for VLSI - А Compendium of Approaches. Journal of Electronic Testing: Theory and Applications, 1998, №12, pp. 7-20, doi: 10.1023/A:1008244815697.
13. Matrosova A.Yu., Levin I., Ostanin S.A. Self-Checking Synchronous FSM Network Design with Low Overhead. VLSI Design, 2000, Vol. 11, Issue 1, pp. 47-58, doi: 10.1155/2000/46578.
14. Tshagharyan G., Harutyunyan G., Shoukourian S., Zorian Y. Experimental Study on Hamming and Hsiao Codes in the Context of Embedded Applications. Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS`2017), Novi Sad, Serbia, September 29 - October 2, 2017, pp. 1-4.
15. Aksjonova G.P. Necessary and sufficient conditions for design of completely checkable modulo 2 convolution circuits. Automation and remote control, 1979, Vol. 40, Issue 9, pp. 1362-1369.
16. Gessel' M., Sogomonjan E.S. Design of self-testing and self-checking combinational circuits with weakly independent outputs. Automation and remote control, 1992, Vol. 53, Issue 8, pp. 1264-1272.
17. Busaba F.Y., Lala P.K. Self-Checking Combinational Circuit Design for Single and Unidirectional Multibit Errors. Journal of Electronic Testing: Theory and Applications, 1994, Issue 1, pp. 19-28, doi: 10.1007/BF00971960.
18. Morosow A, Saposhnikov V.V., Saposhnikov Vl.V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs. VLSI Design, 1998, Vol. 5, Issue 4, pp. 333-345, doi: 10.1155/1998/20389.
19. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking: Edition 1. Dordrecht: Springer Science+Business Media B.V., 2008, 184 p.
20. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Conditions for Detecting a Logical Element Fault in a Combination Device under Concurrent Checking Based on Berger`s Code. Automation and remote control, 2017, Vol. 78, Issue 5, pp. 892-902, doi: 10.1134/S0005117917040113.
21. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V., Dmitriev V.V. New Structures of the Concurrent Error Detection Systems for Logic Circuits, Automation and remote control, 2017, Vol. 78, Issue 2, pp. 300-313, doi: 10.1134/S0005117917020096.
22. Mehov V.B., Sapozhnikov V.V., Sapozhnikov Vl.V. Checking of combinational circuits basing on modification sum codes. Automation and remote control, 2008, Vol. 69, Issue 8, pp. 1411-1422.
23. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. On Summation Code Properties In Functional Control Circuits. Automation and remote control, 2010, Vol. 71, Issue 6, pp. 1117-1123, doi: 10.1134/S0005117910060123.
24. Bljudov A.A., Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Formation of the Berger Modified Code with Minimum Number of Undetectable Errors of Informational Bits. Jelektronnoe modelirovanie [Electronic Modeling], 2012, Vol. 34, Issue 6, pp. 17-29. (in Russian).
25. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Modulo weighted codes with summation with minimum number of undetectable errors in data vectors. Jelektronnoe modelirovanie [Electronic Modeling], 2017, Vol. 39, Issue 4 (in Russian).
26. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V., Kotenko A.G. Modulo Codes with Summation of Weighted Transitions With Natural Number Sequence of Weights. SPIIRAS Proceedings, 2017, Issue 1, pp. 137-164, doi: 10.15622/SP.50.6.
27. Lala P.K. Self-Checking and Fault-Tolerant Digital Design. San Francisco: Morgan Kaufmann Publishers, 2001, 216 p.
28. Hamming R.W. Error Detecting and Correcting Codes. Bell System Technical Journal, 1950, 29 (2), pp. 147-160, MR0035935.
29. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. Weighted Sum Code Without Carries - is an Optimum Code with Detection of Any Double Errors in Data Vectors. Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS`2016), Yerevan, Armenia, October 14-17, 2016, pp. 134-141, doi: 10.1109/EWDTS.2016.7807686.
30. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. New Sum Code for Effective Detection of Double Errors in Data Vectors. Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS`2015), Batumi, Georgia, September 26-29, 2015, pp. 154-159, doi: 10.1109/EWDTS.2015.7493123.
31. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V., Dmitriev V.V. Code with summation of weighted data bits without transitions within concurrent error detection systems. Avtomatika na transporte [Automation on transport], 2017, Vol. 3, Issue 3, pp. 414-433 (in Russian).
32. Ghosh S., Basu S., Touba N.A. Synthesis of Low Power CED Circuits Based on Parity Codes, Proceedings of 23rd IEEE VLSI Test Symposium (VTS'05), 2005, pp. 315-320.
33. Aksjonova G.P. On functional diagnosis of discrete devices under imperfect data processing conditions. Problemy upravlenija [Control Sciences], 2008, Issue 5, pp. 62-66 (in Russian).
Review
For citations:
Sapozhnikov V.V., Sapozhnikov V.V., Efanov D.V. Modified codes with weighted-transitions summation in concurrent error detection systems of combinational circuits. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(5):39-60. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(5)-3
Email this article 