V.V. Sapozhnikov, Dr Sc. (Eng.), Vl.V. Sapozhnikov, Dr Sc. (Eng.),D. V. Efanov, Cand. Sc. (Eng.),
Emperor Alexander State University of Communication Means of St.-Petersburg
9 Moskovsky Ave, St.-Petersburg, 190031, Russian Federation, e-mail:
Èlektron. model. 2018, 40(2):43-70
https://doi.org/10.15407/emodel.40.02.043
ABSTRACT
A method for formation of a code with summation that effectively detects errors of small multiplicity is described. The method is based on weighting the transitions between the bits occupying neighboring positions in data vectors, the weight coefficients from the natural number of numbers, the subsequent calculation of the modified weight of the data vector, and also by applying a series of special permutations of the resulting weights between the data vectors. The check functions of the resulting «permutation» code are linear and are described only using the addition operation modulo two. The properties of error detection of various types andmultiplicities by new codes are analyzed, and a comparison with known codes revealing double errors is made. It is established that the new code detects any twofold errors in data vectors with data vector lengths m <10. It is shown that the permutation code has the advantage over any known codes detecting double errors,with data vectors lengthsm=8 andm= 9. Experimentswith benchmarks have allowed to confirm the theoretical results, aswell as to evaluate the effectiveness of the application of the new code in the concurrent error detection systems by the indicators of structural redundancy.
KEYWORDS
technical diagnostics of discrete systems, summation code, Berger code, Hamming code, modified weighted code, detection of double errors, structural redundancy.
REFERENCES
1. Parkhomenko, P.P. and Sogomonyan, E.S. (1981), Osnovy tekhnicheskoy diagnostiki (optimizatsiya algoritmov diagnostirovaniya, apparaturnye sredstva) [Basics of technical diagnostics (optimization of diagnostic algorithms and equipment)], Energoatomizdat, Moscow, USSR.
2. McCluskey, E.J. (1986), Logic design principles: with emphasis on testable semicustom circuits, Prentice Hall PTR, New Jersey, USA.
3. Sogomonyan, E.S. and Slabakov, E.V. (1989), Samoproveryaemye ustroystva i otkazoustoychivye sistemy [Self-checking devices and failover systems], Radio i svyaz, Moscow, USSR.
4. Goessel, M. and Graf, S. (1994), Error detection circuits, McGraw-Hill, London, UK.
5. Abramovici, M., Breuer, M.A. and Friedman, A.D. (1998), Digital system testing and testable design, Computer Science Press.
6. Fujiwara, E. (2006), Code design for dependable systems: theory and practical applications, John Wiley & Sons, New Jersey, USA.
https://doi.org/10.1002/0471792748
7. Freiman, C.V. (1962), Optimal error detection codes for completely asymmetric binary channels, Information and Control, Vol. 5, Iss. 1, pp. 64-71. DOI: 10.1016/S0019-9958(62) 90223-1.
8. Berger, J.M. (1961), A note on error detecting codes for asymmetric channels, Information and Control, Vol. 4, Iss. 1, pp. 68-73. DOI: 10.1016/S0019-9958(61)80037-5.
https://doi.org/10.1016/S0019-9958(61)80037-5
9. Borden, J.M. (1982), Optimal asymmetric error detecting codes, Information and Control, Vol. 53, Iss. 1-2, pp. 66-73. DOI: 10.1016/S0019-9958(82)91125-1.
https://doi.org/10.1016/S0019-9958(82)91125-1
10. Dong, H. (1984), Modified Berger codes for detection of unidirectional errors, IEEE Transactions on Computers, Vol. C-33, June 1984, pp. 572-575.
https://doi.org/10.1109/TC.1984.1676484
11. Blaum, M. (1988), On systematic burst unidirectional error detecting codes, IEEE Transactions on Computers, Vol. 37, Iss. 4, pp. 453-457. DOI 10.1109/12.2190.
https://doi.org/10.1109/12.2190
12. Parhami, B. (1991), New class of unidirectional error-detection codes, Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, October 14-16, 1991 (ICCD ‘9), Cambridge, MA, USA, pp. 574-577.
13. Das, D. and Touba, N.A. (1999), Weight-based codes and their application to concurrent error detection of multilevel circuits, Proceedings of 17th IEEE Test Symposium, USA, California, pp. 370-376.
https://doi.org/10.1109/VTEST.1999.766691
14. Göessel, M., Ocheretny, V., Sogomonyan, E. and Marienfeld, D. (2008), New methods of concurrent checking: Edition 1, Springer Science+Business Media B.V., Dodrecht, Netherlands.
15. Sogomonyan, E.S. (1974), “Design of inbuilt test self-checking circuits for combinational devices”, Avtomatika i telemekhanika, no. 2, pp. 121-133.
16. Slabakov, E.V. and Sogomonyan, E.S. (1981), “Self-checking computing devices and systems (review)”, Avtomatika i telemekhanika, no. 11, pp. 147-167.
17. Ghosh, S., Basu, S. and Touba, N.A. (2005), Synthesis of low power CED circuits based on parity codes, Proceedings of the 23rd IEEE VLSI Test Symposium (VTS’05), pp. 315-320.
https://doi.org/10.1109/VTS.2005.80
18. Aksyonova, G.P. (2008), “On functional diagnosis of discrete devices under imperfect data processing conditions”, Problemy upravleniya, no. 5, pp. 62-66.
19. Busaba, F.Y. and Lala, P.K. (1994), Self-checking combinational circuit design for single and unidirectional multibit errors, Journal of Electronic Testing: Theory and Applications, Iss. 5, pp. 19-28. DOI: 10.1007/BF00971960.
https://doi.org/10.1007/BF00971960
20. Matrosova, A.Yu., Levin, I. and Ostanin, S.A. (2000), Self-checking synchronous FSM network design with low overhead, VLSI Design, Vol. 11, Iss. 1, ðp. 47-58. DOI: 10.1155/2000/46578.
https://doi.org/10.1155/2000/46578
21. Morosow, A., Saposhnikov, V.V., Saposhnikov, Vl.V. and Goessel, M. (1998), Self-checking combinational circuits with unidirectionally independent outputs, VLSI Design, Vol. 5, Iss. 4, pp. 333-345. DOI: 10.1155/1998/20389.
https://doi.org/10.1155/1998/20389
22. Saposhnikov, V.V., Morosov, A., Saposhnikov, Vl.V. and Göessel, M. (1998), A new design method for self-checking unidirectional combinational circuits, Journal of Electronic Testing: Theory and Applications, Vol. 12, Iss. 1-2, pp. 41-53. DOI: 10.1023/A:1008257118423.
https://doi.org/10.1023/A:1008257118423
23. Piestrak, S.J. (1995), Design of self-testing checkers for unidirectional error detecting codes, Oficyna Wydawnicza Politechniki Wroclavskiej, Wroclaw, Poland.
24. Mitra, S. and McCluskey, E.J. (2000), Which concurrent error detection scheme to choose?, Proceedings of International Test Conference, USA, Atlantic City, NJ, October 03-05, 2000, pp. 985-994. DOI: 10.1109/TEST.2000.894311.
https://doi.org/10.1109/TEST.2000.894311
25. Sapozhnikov, V., Sapozhnikov, Vl., Efanov, D. and Dmitriev, V. (2017), Method of combinational circuits testing by dividing its outputs into groups and using codes that effectively detect double errors, Proceedings of the 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, September 29-October 2, 2017, pp. 129-136. DOI: 10.1109/EWDTS.2017.8110123.
https://doi.org/10.1109/EWDTS.2017.8110123
26. Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2010), “On sum code properties in concurrent error detection systems”, Avtomatika i telemekhanika, no. 6, pp. 155-162.
27. Sapozhnikov, V., Sapozhnikov, Vl., Efanov, D. and Nikitin, D. (2014), Combinational circuits che- cking on the base of sum codes with one weighted data bit, Procedings of the 12th IEEE East-West Design & Test Symposium (EWDTS`2014), Kyiv, Ukraine, September 26-29, 2014, pp. 126-136. DOI:10.1109/EWDTS.2014.7027064.
28. Hamming, R.W. (1950), Error detecting and correcting codes, Bell System Technical Journal, 29 (2), pp. 147-160. MR0035935.
29. Mehov, V., Sapozhnikov, V., Sapozhnikov, Vl. and Urganskov, D. (2007), Concurrent error detection based on new code with modulo weighted transitions between information bits, Proceedings Test of 7thI EEE East-West Design &Workshop (EWDTW`2007), Erevan, Armenia, September 25-30, 2007, pp. 21-26.
30. Mekhov, V.B., Sapozhnikov, V.V., Sapozhnikov, Vl.V. (2008) “Control of combinational circuits based on modification sum codes”, Avtomatika i telemekhanika, no. 8, pp. 153-165.
31. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Dmitriev, V.V. (2017), “New structures of the concurrent error detection systems for logic circuits”, Avtomatika i telemekhanika, no. 2, pp. 127-143.
https://doi.org/10.1134/S0005117917020096
32. Sapozhnikov, V., Sapozhnikov, Vl., Efanov, D. and Dmitriev, V. (2015), New sum code for effective detection of double errors in data vectors, Proceedings of the 13th IEEE East-West Design &Test Symposium (EWDTS`2015), Batumi, Georgia, September 26-29, 2015, pp. 154-159. DOI:10.1109/EWDTS.2015.7493123.
https://doi.org/10.1109/EWDTS.2015.7493123
33. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Dmitriev, V.V. (2016), “On one modification of a code with summation of weighted transition between data vectors”, Izvestiya vysshikh uchebnykh zavedeniy. Fizika, Vol. 59, no. 8/2, pp. 89-92.
34. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2015), “Errors classification in information vectors of systematic codes”, Izvestiya vysshikh uchebnykh zavedeniy. Priborostroenie, Vol. 58, no. 5, pp. 333-343. DOI 10.17586/0021-3454-2015-58-5-333-343.
https://doi.org/10.17586/0021-3454-2015-58-5-333-343
35. Blyudov, A.A., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2012), “Formation of the Berger modified code with minimum number of undetectable errors of data bits”, Elektronnoe modelirovanie, Vol. 34, no. 6, pp. 17-29.
36. Sapozhnikov, V., Sapozhnikov, Vl., Efanov, D. and Dmitriev, V. (2016), Weighted sum code without carries – is an optimum code with detection of any double errors in data vectors, Proceedings of the 14th IEEE East-West Design & Test Symposium (EWDTS`2016), Yerevan, Armenia, October 14-17, 2016, pp. 134-141. DOI:10.1109/EWDTS.2016. 7807686.
37. Collection of design Benchmarks, available at: http://ddd.fit.cvut.cz/prj/Benchmarks/.
38. Sentovich, E. M., Singh, K.J., Lavagno, K., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P.R., Brayton, R. and Sangiovanni-Vincentelli, K.A. (1992), SIS: A system for sequential circuit synthesis, Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkeley, USA.