D.V. Efanov
Èlektron. model. 2019, 41(6):49-64
https://doi.org/10.15407/emodel.41.06.049
ABSTRACT
In the article, the author the use of redundant coding in the construction of automation and computer technology devices and systems. The prospects for the application of Borden codes in the construction of discrete systems with fault detection are determined. The features of er-ror detection by Borden codes are analyzed. The code building rules and examples of these codes are given. A formula is given for calculating the total errors undetected number by Bor-den codes. Some features of error detection by Borden codes are described, which allow char-acterizing them when choosing discrete systems with fault detection at the construction stage.
KEYWORDS
discrete system with fault detection, checkability circuit, constant-weight co-des, Borden codes, unidirectional errors-detection.
REFERENCES
1. Bennetts, R.G. (1984), Design of Testable Logic Circuits, Addison-Wesley Publishers Limited, London, UK.
2. Ubar, R., Raik, J. and Vierhaus, H.-T. (2011), Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source), Information Science Reference, IGI Global, New York, USA.
https://doi.org/10.4018/978-1-60960-212-3
3. Hahanov, V. (2018), Cyber Physical Computing for IoT-driven Services, Springer Interna-tional Publishing AG, New York, USA.
https://doi.org/10.1007/978-3-319-54825-8
4. Sogomonyan, E.S. and Slabakov, E.V. (1989), Samoproverjaemyje ustrojstva i otkazous-tojchivyje sistemy [Self-checking devices and failover systems], Radio & Svjaz`, Moscow, USSR.
5. Gavrilov, M.A., Ostianu, V.M., and Potekhin, A.I. (1969, 1970), “Reliability of discrete systems”, Itogi nauki i tekhniki. Ser. “Teoriya veroyatnostej. Matematicheskaya statistika. Teoreticheskaya kibernetika”, pp. 7-104.
6. Sagalovitch, Yu.L., and Scherbakov, N.S. (1984) “The Choice of Coding System to Protect Memory Devices from Errors”, Problemy peredachi informacii, Vol. 20, Issue. 1, pp. 19-27.
7. Fujiwara, E. (2006), Code Design for Dependable Systems: Theory and Practical Applica-tions, John Wiley & Sons, New Jersey, USA.
https://doi.org/10.1002/0471792748
8. Lala, P.K. (2007), Principles of Modern Digital Design, John Wiley & Sons, New Jersey, USA.
https://doi.org/10.1002/0470125217
9. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2018), Kody Hemminga v sistemah funkcional'nogo kontrolya logicheskih ustrojstv [Hamming codes in concurrent error detection systems of logic devices], Nauka, St. Petersburg, Russia.
10. Morosow, A., Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Goessel, M. (1998), “Self-Checking Combinational Circuits with Unidirectionally Independent Outputs”, VLSI Design, Vol. 5, Issue 4, pp. 333-345.
https://doi.org/10.1155/1998/20389
11. Matrosova, A.Yu., Levin, I., Ostanin, S.A. (2000), “Self-Checking Synchronous FSM Network Design with Low Overhead”, VLSI Design, Vol. 11, Issue. 1, pp. 47-58.
https://doi.org/10.1155/2000/46578
12. Göessel, M., Ocheretny, V., Sogomonyan, E. and Marienfeld, D. (2008), New Methods of Concurrent Checking: Edition 1, Springer Science+Business Media B.V, Dordrecht, Ne-derland.
13. Ostanin, S. (2017), “Self-Checking Synchronous FSM Network Design for Path Delay Faults”, Proceeding of the 15th IEEE East-West Design & Test Symposium (EWDTS`2017), Novi Sad, Serbia, 2017, September 29 - October 2, pp. 696-699.
https://doi.org/10.1109/EWDTS.2017.8110129
14. Berger, J.M. (1961), “A Note on Error Detection Codes for Asymmetric Channels”, Information and Control, Vol. 4, Issue. 1, pp. 68-73.
https://doi.org/10.1016/S0019-9958(61)80037-5
15. Freiman, C.V. (1962), “Optimal Error Detection Codes for Completely Asymmetric Binary Channels”, Ibid, Vol. 5, Issue. 1, pp. 64-71.
https://doi.org/10.1016/S0019-9958(62)90223-1
16. Lin, D.J. and Bose, B. (1988), “Theory and Design of t-error Correcting and d(d>t)-unidirectional Error Detecting (t-EC d-UED) Codes”, IEEE Transaction on Computers, Vol. 37, Issue. 4, pp. 433-439.
https://doi.org/10.1109/12.2187
17. Piestrak, S.J. (1995), Design of Self-Testing Checkers for Unidirectional Error Detecting Codes, Oficyna Wydawnicza Politechniki Wrocłavskiej, Wrocław, Poland.
18. Efanov, D., Sapozhnikov, V., Sapozhnikov, Vl. (2017), “Generalized Algorithm of Build-ing Summation Codes for the Tasks of Technical Diagnostics of Discrete Systems”, Pro-ceeding of the 15th IEEE East-West Design & Test Symposium (EWDTS`2017), Novi Sad, Serbia, September 29 – October 2, 2017, pp. 365-371.
https://doi.org/10.1109/EWDTS.2017.8110126
19. Efanov, D.V., Sapozhnikov, V.V., and Sapozhnikov, Vl.V. (2019), “Codes with Summa-tion with Fixed Multiplicities of Detected Unidirectional and Asymmetric Errors for Tech-nical Diagnostic Systems”, Avtomatika i telemekhanika, Issue 6, pp. 121-141.
20. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Gossel', M. (2001), Samodvojstvennye diskretnye ustrojstva [Self-Dual Discrete Devices], Energoatomizdat, St. Petersburg, Russia.
21. Borden, J.M. (1982), “Optimal Asymmetric Error Detecting Codes”, Information and Control, Vol. 53, Issue. 1-2, pp. 66-73.
https://doi.org/10.1016/S0019-9958(82)91125-1
22. Berezyuk, N.T., Andrushchenko, A.G. and Moshchickij, S.S. (1978), Kodirovanie informacii (dvoichnye kody) [Information Encoding (Binary Codes)], Vishcha shkola, Kharkov, USSR.
23. Jha, N.K. (1989), “A Totally Self-Checking Checker for Borden's Code”, IEEE Transac-tions on Computer-Aided Design for Integrated Circuits and Systems, Vol. 8, pp. 731-736.
https://doi.org/10.1109/43.31530
24. Haniotakis, Th., Nikolos, D., Paschalis, A. and Gizopoulos, D. (1994), “Totally Self-Checking Checkers for Borden Codes”, International Journal of Electronics, Vol. 76, Is-sue. 1, pp. 57-64.
https://doi.org/10.1080/00207219408925905
25. Piestrak, S.J. (1996), “Design of Self-Testing Checkers for Borden Codes”, IEEE Transactions on Computers, Vol. 45, Issue. 4, pp. 461-469.
https://doi.org/10.1109/12.494103
26. Tarnick, S. (2006), “Embedded Borden 2-UED Code Checkers”, Proceeding of the 12th IEEE International On-Line Testing Symposium (IOLTS'06), Lake Como, Italy, pp. 1-3.
https://doi.org/10.1109/IOLTS.2006.27
27. Efanov, D.V., Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Pivovarov, D.V. (2018), “The Self-Checking Integrated Control Circuits Synthesis Based on the Boolean Complement Method to "2-Out-Of-4" Constant-Weight Code”, Informatika, Vol. 15, Issue 4, pp. 71-85.
28. 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.
https://doi.org/10.17586/0021-3454-2015-58-5-333-343
29. Efanov, D.V. (2019), “Some Features of Error Detection by Uniform Indivisible Codes”, Ebid, Vol. 62, no. 7, pp. 621-631.
https://doi.org/10.17586/0021-3454-2019-62-7-621-631
30. Dmitriev, V.V., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2018), “Sum Codes with Efficient Detection of Twofold Errors for Organization of Concurrent Error-Detection Systems of Logical Devices”, Avtomatika i telemekhanika, no. 4, pp. 105-122.
https://doi.org/10.1134/S0005117918040082
2. Ubar, R., Raik, J. and Vierhaus, H.-T. (2011), Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source), Information Science Reference, IGI Global, New York, USA.
https://doi.org/10.4018/978-1-60960-212-3
3. Hahanov, V. (2018), Cyber Physical Computing for IoT-driven Services, Springer Interna-tional Publishing AG, New York, USA.
https://doi.org/10.1007/978-3-319-54825-8
4. Sogomonyan, E.S. and Slabakov, E.V. (1989), Samoproverjaemyje ustrojstva i otkazous-tojchivyje sistemy [Self-checking devices and failover systems], Radio & Svjaz`, Moscow, USSR.
5. Gavrilov, M.A., Ostianu, V.M., and Potekhin, A.I. (1969, 1970), “Reliability of discrete systems”, Itogi nauki i tekhniki. Ser. “Teoriya veroyatnostej. Matematicheskaya statistika. Teoreticheskaya kibernetika”, pp. 7-104.
6. Sagalovitch, Yu.L., and Scherbakov, N.S. (1984) “The Choice of Coding System to Protect Memory Devices from Errors”, Problemy peredachi informacii, Vol. 20, Issue. 1, pp. 19-27.
7. Fujiwara, E. (2006), Code Design for Dependable Systems: Theory and Practical Applica-tions, John Wiley & Sons, New Jersey, USA.
https://doi.org/10.1002/0471792748
8. Lala, P.K. (2007), Principles of Modern Digital Design, John Wiley & Sons, New Jersey, USA.
https://doi.org/10.1002/0470125217
9. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2018), Kody Hemminga v sistemah funkcional'nogo kontrolya logicheskih ustrojstv [Hamming codes in concurrent error detection systems of logic devices], Nauka, St. Petersburg, Russia.
10. Morosow, A., Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Goessel, M. (1998), “Self-Checking Combinational Circuits with Unidirectionally Independent Outputs”, VLSI Design, Vol. 5, Issue 4, pp. 333-345.
https://doi.org/10.1155/1998/20389
11. Matrosova, A.Yu., Levin, I., Ostanin, S.A. (2000), “Self-Checking Synchronous FSM Network Design with Low Overhead”, VLSI Design, Vol. 11, Issue. 1, pp. 47-58.
https://doi.org/10.1155/2000/46578
12. Göessel, M., Ocheretny, V., Sogomonyan, E. and Marienfeld, D. (2008), New Methods of Concurrent Checking: Edition 1, Springer Science+Business Media B.V, Dordrecht, Ne-derland.
13. Ostanin, S. (2017), “Self-Checking Synchronous FSM Network Design for Path Delay Faults”, Proceeding of the 15th IEEE East-West Design & Test Symposium (EWDTS`2017), Novi Sad, Serbia, 2017, September 29 - October 2, pp. 696-699.
https://doi.org/10.1109/EWDTS.2017.8110129
14. Berger, J.M. (1961), “A Note on Error Detection Codes for Asymmetric Channels”, Information and Control, Vol. 4, Issue. 1, pp. 68-73.
https://doi.org/10.1016/S0019-9958(61)80037-5
15. Freiman, C.V. (1962), “Optimal Error Detection Codes for Completely Asymmetric Binary Channels”, Ibid, Vol. 5, Issue. 1, pp. 64-71.
https://doi.org/10.1016/S0019-9958(62)90223-1
16. Lin, D.J. and Bose, B. (1988), “Theory and Design of t-error Correcting and d(d>t)-unidirectional Error Detecting (t-EC d-UED) Codes”, IEEE Transaction on Computers, Vol. 37, Issue. 4, pp. 433-439.
https://doi.org/10.1109/12.2187
17. Piestrak, S.J. (1995), Design of Self-Testing Checkers for Unidirectional Error Detecting Codes, Oficyna Wydawnicza Politechniki Wrocłavskiej, Wrocław, Poland.
18. Efanov, D., Sapozhnikov, V., Sapozhnikov, Vl. (2017), “Generalized Algorithm of Build-ing Summation Codes for the Tasks of Technical Diagnostics of Discrete Systems”, Pro-ceeding of the 15th IEEE East-West Design & Test Symposium (EWDTS`2017), Novi Sad, Serbia, September 29 – October 2, 2017, pp. 365-371.
https://doi.org/10.1109/EWDTS.2017.8110126
19. Efanov, D.V., Sapozhnikov, V.V., and Sapozhnikov, Vl.V. (2019), “Codes with Summa-tion with Fixed Multiplicities of Detected Unidirectional and Asymmetric Errors for Tech-nical Diagnostic Systems”, Avtomatika i telemekhanika, Issue 6, pp. 121-141.
20. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Gossel', M. (2001), Samodvojstvennye diskretnye ustrojstva [Self-Dual Discrete Devices], Energoatomizdat, St. Petersburg, Russia.
21. Borden, J.M. (1982), “Optimal Asymmetric Error Detecting Codes”, Information and Control, Vol. 53, Issue. 1-2, pp. 66-73.
https://doi.org/10.1016/S0019-9958(82)91125-1
22. Berezyuk, N.T., Andrushchenko, A.G. and Moshchickij, S.S. (1978), Kodirovanie informacii (dvoichnye kody) [Information Encoding (Binary Codes)], Vishcha shkola, Kharkov, USSR.
23. Jha, N.K. (1989), “A Totally Self-Checking Checker for Borden's Code”, IEEE Transac-tions on Computer-Aided Design for Integrated Circuits and Systems, Vol. 8, pp. 731-736.
https://doi.org/10.1109/43.31530
24. Haniotakis, Th., Nikolos, D., Paschalis, A. and Gizopoulos, D. (1994), “Totally Self-Checking Checkers for Borden Codes”, International Journal of Electronics, Vol. 76, Is-sue. 1, pp. 57-64.
https://doi.org/10.1080/00207219408925905
25. Piestrak, S.J. (1996), “Design of Self-Testing Checkers for Borden Codes”, IEEE Transactions on Computers, Vol. 45, Issue. 4, pp. 461-469.
https://doi.org/10.1109/12.494103
26. Tarnick, S. (2006), “Embedded Borden 2-UED Code Checkers”, Proceeding of the 12th IEEE International On-Line Testing Symposium (IOLTS'06), Lake Como, Italy, pp. 1-3.
https://doi.org/10.1109/IOLTS.2006.27
27. Efanov, D.V., Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Pivovarov, D.V. (2018), “The Self-Checking Integrated Control Circuits Synthesis Based on the Boolean Complement Method to "2-Out-Of-4" Constant-Weight Code”, Informatika, Vol. 15, Issue 4, pp. 71-85.
28. 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.
https://doi.org/10.17586/0021-3454-2015-58-5-333-343
29. Efanov, D.V. (2019), “Some Features of Error Detection by Uniform Indivisible Codes”, Ebid, Vol. 62, no. 7, pp. 621-631.
https://doi.org/10.17586/0021-3454-2019-62-7-621-631
30. Dmitriev, V.V., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2018), “Sum Codes with Efficient Detection of Twofold Errors for Organization of Concurrent Error-Detection Systems of Logical Devices”, Avtomatika i telemekhanika, no. 4, pp. 105-122.
https://doi.org/10.1134/S0005117918040082