priborИзвестия высших учебных заведений. ПриборостроениеJournal of Instrument Engineering0021-34542500-0381Национальный исследовательский университет ИТМО10.17586/0021-3454-2022-65-5-307-322pribor-243Research ArticleИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКАINFORMATION TECHNOLOGIES AND SYSTEMS, COMPUTER TECHNIQUEТроичные модульные коды с суммированием для синтеза цифровых самопроверяемых устройствTernary modular codes with summation for the synthesis of digital self-testing devicesЕфановД. В.EfanovD. V.

Дмитрий Викторович Ефанов —д-р техн. наук, доцент; РУТ, кафедра автоматики, телемеханики и связи на железнодорожном транспорте; Санкт-Петербургский ПУ Петра Великого; Высшая школа транспорта Института машиностроения, материалов и транспорта; профессор.

Москва, Санкт-Петербург

Dmitry V. Efanov — Dr. Sci., Associate Professor; RUT, Department of Automation, Remote Control, and Communications on Railway Transport; Peter the Great St. Petersburg PU, Higher School of Transport of the Institute of Machinery, Materials, and Transport; Professor.

Moscow, St. Petersburg

TrES-4b@yandex.ruРоссийский университет транспорта; Санкт-Петербургский политехнический университет Петра ВеликогоRussian University of Transport; Peter the Great St. Petersburg Polytechnic University202201122024655307322Copyright © Национальный исследовательский университет ИТМО, 20242024Национальный исследовательский университет ИТМОНациональный исследовательский университет ИТМОhttps://pribor.ifmo.ru/jour/about/submissions#copyrightNoticehttps://pribor.ifmo.ru/jour/article/view/243

Рассматриваются троичные коды с суммированием, предназначенные для синтеза цифровых самопроверяемых схем, функционирующих в троичной логике и обладающих свойством обнаружения любых не композиционных (при которых число символов каждого вида сохраняется) ошибок в информационных векторах. Приводятся правила построения троичных кодов с суммированием, которые по своим свойствам схожи с бинарным кодом Бергера. Рассматриваются две модификации троичного кода с суммированием — коды с суммированием в кольце вычетов по модулям μ=3 и μ=9 — и некоторые характеристики обнаружения ошибок этими кодами. Показано, что доля необнаруживаемых троичными кодами с суммированием ошибок кратностью d от общего числа ошибок данной кратностью является постоянной величиной, не зависящей от длины информационного вектора.

Ternary summation codes with simple construction rules, suitable for the digital self-checking circuits synthesis operating in ternary logic and able of detecting any non-compositional errors in information vectors (when the number of characters of each type is preserved), are considered. Rules for constructing the ternary sum codes, similar in its properties to the Berger binary code, are given. Two modifications of the ternary sum code are described – sum codes in the residues modulo μ=3 and μ=9 ring. Several characteristics of error detection by the codes are described. It is shown that the proportion of errors of multiplicity d, undetectable by binary summation codes, of the total number of errors of the given multiplicity, is a constant value independent of the information vector length.

отказоустойчивые и самопроверяемые цифровые устройства и системыпомехоустойчивое и помехозащищенное кодированиетроичные коды с суммированиемтроичные модульные коды с суммированиемобнаружение ошибок в информационных векторахнеобнаруживаемая ошибкаfault-tolerant and self-testing digital devices and systemsnoise-resistant and noise-proof codingternary codes with summationerror detection in information vectorsundetectable errorReferencesГаврилов М. А., Остиану В. М., Потехин А. И. Надежность дискретных систем // Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. 1970. C. 7—104.Gavrilov M.A., Ostianu V.M., Potekhin A.I. Itogi nauki i tekhniki. Seriya „Teoriya veroyatnostey. Matematicheskaya statistika. Teoreticheskaya kibernetika“ (Results of Science and Technology. Series „Probability Theory. Math Statistics. Theoretical Cybernetics“), 1969, 1970, рр. 7–104. (in Russ.)Согомонян Е. С., Слабаков Е. В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989, 208 с.Sogomonyan E.S., Slabakov E.V. Samoproveryaemye ustroystva i otkazoustoychivye sistemy (The Self-Checked Devices and Failure-Safe Systems), Moscow, 1989, 208 р. (in Russ.)Дрозд А. В., Харченко В. С., Антощук С. Г., Дрозд Ю. В., Дрозд М. А., Сулима Ю. Ю. Рабочее диагностирование безопасных информационно-управляющих систем / Под ред. А. В. Дрозда и В. С. Харченко. Харьков: Нац. аэрокосм. ун-т им. Н. Е. Жуковского „ХАИ“, 2012. 614 с.Drozd A.V., Kharchenko V.S., Antoshchuk S.G., Drozd Yu.V., Drozd M.A., Sulima Yu.Yu. Rabocheye diagnostirovaniye bezopasnykh informatsionno-upravlyayushchikh sistem (Working Diagnostics of Safe Information and Control Systems), Khar’kov, 2012, 614 р. (in Russ.)Kharchenko V., Kondratenko Yu., Kacprzyk J. Green IT Engineering: Concepts, Models, Complex Systems Architectures // Springer Book Series „Studies in Systems, Decision and Control“. 2017. Vol. 74. 305 p. DOI: 10.1007/978-3-319-44162-7.Kharchenko V., Kondratenko Yu., Kacprzyk J. Green IT Engineering: Concepts, Models, Complex Systems Architectures, Springer Book series "Studies in Systems, Decision and Control", 2017, vol. 74, 305 p., DOI: 10.1007/978-3-319-44162-7.Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John Wiley & Sons, 2006. 720 p.Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications, John Wiley & Sons, 2006, 720 p.Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking. Dordrecht: Springer Science+Business Media B.V., 2008. 184 p.Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking, Dordrecht: Springer Science+Business Media B.V., 2008, 184 p.Сагалович Ю. Л. Введение в алгебраические коды. М.: Ин-т проблем передачи информации им. А. А. Харкевича РАН, 2010. 302 с.Sagalovich Yu.L. Vvedeniye v algebraicheskiye kody (Introduction to Algebraic Codes) Moscow, 2010, 302 р. (in Russ.)Сапожников В. В., Сапожников Вл. В., Христов Х. А., Гавзов Д. В. Методы построения безопасных микроэлектронных систем железнодорожной автоматики / Под ред. Вл. В. Сапожникова. М.: Транспорт, 1995. 272 с.Sapozhnikov V.V., Sapozhnikov Vl.V., Khristov Kh.A., Gavzov D.V. Metody postroyeniya bezopasnykh mikroelektronnykh sistem zheleznodorozhnoy avtomatiki (Methods of Construction of Safe Microelectronic Systems of Railway Automation), Moscow, 1995, 272 р. (in Russ.)Hahanov V. Cyber Physical Computing for IoT-driven Services. N. Y.: Springer International Publishing AG, 2018. 279 p.Hahanov V. Cyber Physical Computing for IoT-driven Services, NY, Springer International Publishing AG, 2018, 279 p.Kosky P., Balmer R.T., Keat W.D., Wise G. Exploring Engineering: An Introduction to Engineering and Design. Academic Press, 2020. 656 p. DOI: 10.1016/C2017-0-01871-2.Kosky P., Balmer R.T., Keat W.D., Wise G. Exploring Engineering: An Introduction to Engineering and Design, Academic Press, 2020, 656 p., https://doi.org/10.1016/C2017-0-01871-2.Zhuo Y., Li X.-L., Sun Y.-B., Li X.-J., Shi Y.-L., Chen S.-M., Hu S.-J., Guo A. Statistical Variability Analysis in Vertically Stacked Gate All Around FETs at 7 nm Technology // 14th IEEE Intern. Conf. on Solid-State and Integrated Circuit Technology (ICSICT), Qingdao, China, 31 Oct. — 3 Nov. 2018. DOI: 10.1109/ICSICT.2018.8565797.Zhuo Y., Li X.-L., Sun Y.-B., Li X.-J., Shi Y.-L., Chen S.-M., Hu S.-J., Guo A. 2018 14th IEEE International Conference on Solid-State and Integrated Circuit Technology (ICSICT), 31 Oct.–3 Nov. 2018, Qingdao, China, DOI: 10.1109/ICSICT.2018.8565797.Yoon J.-S., Lee S., Lee J., Jeong J., Yun H., Baek R.-H. Reduction of Process Variations for Sub-5-nm Node Fin and Nanosheet FETs Using Novel Process Scheme // IEEE Trans. on Electron Devices. 2020. Vol. 67, iss. 7. P. 2732—2737. DOI: 10.1109/TED.2020.2995340.Yoon J.-S., Lee S., Lee J., Jeong J., Yun H., Baek R.-H. IEEE Transactions on Electron Devices, 2020, no. 7(67), pp. 2732–2737, DOI: 10.1109/TED.2020.2995340.Kumar O., Kaur M. Single Electron Transistor: Applications & Problems // Intern. Journal of VLSI Design & Communication Systems. 2010. Vol. 1, iss. 4. P. 240—29. DOI: 10.5121/vlsic.2010.1403.Kumar O., Kaur M. International Journal of VLSI Design & Communication Systems, 2010, no. 4(1), pp. 240–249, DOI: 10.5121/vlsic.2010.1403.Cambou B., Flikkema P.G., Palmer J., Telesca D., Philabaum C. Can Ternary Computing Improve Information Assurance? // Cryptography. 2018. Vol. 2, iss. 1 P. 1—16. DOI: 10.3390/cryptography2010006.Cambou B., Flikkema P.G., Palmer J., Telesca D., Philabaum C. Cryptography, 2018, no. 1(2), pp. 1–16, DOI: 10.3390/cryptography2010006.Wu J. Ternary Logic Circuit for Error Detection and Error Correction // Proc. of the 19th Intern. Symp. on MultipleValued Logic, Guangzhou, China, 29—31 May, 1989. P. 94—99. DOI: 10.1109/ISMVL.1989.37766.Wu J. Proceedings of 19th International Symposium on Multiple-Valued Logic, 29–31 May 1989, Guangzhou, China, pp. 94–99, DOI: 10.1109/ISMVL.1989.37766.Брусенцов Н. П., Маслов С. П., Рамиль Альварес Х. Микрокомпьютерная система обучения „Наставник“. М.: Наука, 1990. 223 с.Brusentsov N.P., Maslov S.P., Ramil' Al'vares Kh. Mikrokomp'yuternaya sistema obucheniya „Nastavnik“ (Microcomputer Training System "Mentor"), Moscow, 1990, 223 р. (in Russ.)Connely J. Ternary Computing Testbed 3-Trit Computer Architecture / California Polytechnic State University of San Luis Obispo, Aug. 2008. 184 p.Connely J. Ternary Computing Testbed 3-Trit Computer Architecture, California Polytechnic State University of San Luis Obispo, August 29th, 2008, 184 p.Kim S., Lim T., Kang S. An Optimal Gate Design for the Synthesis of Ternary Logic Circuits // 23rd Asia and South Pacific Design Automation Conf. (ASP-DAC), Jeju, South Korea, 22—25 Jan. 2018. P. 476—481. DOI: 10.1109/ASPDAC.2018.8297369.Kim S., Lim T., Kang S. 23rd Asia and South Pacific Design Automation Conference (ASP-DAC), 22–25 January 2018, Jeju, South Korea, pp. 476–481, DOI: 10.1109/ASPDAC.2018.8297369.Gulliver T. A., Ostergard P. R. J. Improved Bounds for Ternary Linear Codes of Dimension 7 // IEEE Trans. On Information Theory. 1997. Vol. 43, iss. 4. P. 1377—1381. DOI: 10.1109/18.605613.Gulliver T.A., Ostergard P.R.J. IEEE Transactions on Information Theory, 1997, no. 4(43), pp. 1377–1381, DOI: 10.1109/18.605613.Bitouze N., Graell i Amat A., Rosnes E. Error Correcting Coding for a Nonsymmetric Ternary Channel // IEEE Trans. on Information Theory. 2010. Vol. 56, iss. 11. P. 5715—5729. DOI: 10.1109/TIT.2010.2069211.Bitouze N., Graell i Amat A., Rosnes E. IEEE Transactions on Information Theory, 2010, no. 11(56), pp. 5715–5729, DOI: 10.1109/TIT.2010.2069211.Laaksonen A., Östergård P. R. J. New Lower Bounds on Error-Correcting Ternary, Quaternary and Quinary Codes // Lecture Notes in Computer Science 10495, Springer: Coding Theory and Applications; 5th Intern. Castle Meeting, ICMCTA 2017, Vihula, Estonia, Aug. 28—31, 2017. P. 228—237.Laaksonen A., Östergård P.R.J. Lecture Notes in Computer Science 10495, Springer: Coding Theory and Applications, 5th International Castle Meeting, ICMCTA 2017, Vihula, Estonia, August 28–31, 2017, pp. 228–237.Кодирование информации (двоичные коды) / Н. Т. Березюк, А. Г. Андрущенко, С. С. Мощицкий, В. И. Глушков, М. М. Бенеша, В. А. Гаврилов; Под ред. Н. Т. Березюка. Харьков: Вища школа, 1978. 252 с.Berezyuk N.T., Andrushchenko A.G., Moshchitskiy S.S., Glushkov V.I., Benesha M.M., Gavrilov V.A. Kodirovaniye informatsii (dvoichnyye kody) (Information Coding (Binary Codes)), Khar'kov, 1978, 252 р. (in Russ.)Svanström M. A Lower Bound for Ternary Constant Weight Codes // IEEE Trans. on Information Theory. 1997. Vol. 43. P. 1630—1632.Svanström M. IEEE Transactions on Information Theory, 1997, vol. 43, pp. 1630–1632.Svanström M., Östergård P. R. J., Bogdanova G. T. Bounds and Constructions for Ternary Constant-Composition Codes // IEEE Trans. on Information Theory. 2002. Vol. 48. P. 101—111.Svanström M., Östergård P.R.J., Bogdanova G.T. IEEE Transactions on Information Theory, 2002, vol. 48, pp. 101–111.Ефанов Д. В. Троичные коды с суммированием и их модификации // Проблемы разработки перспективных микрои наноэлектронных систем (МЭС). 2020. № 1. С. 119—125. DOI: 10.31114/2078-7707-2020-1-119-125.Efanov D.V. Problemy razrabotki perspektivnykh mikroi nanoelektronnykh sistem (MES), 2020, no. 1, pp. 119–125, DOI: 10.31114/2078-7707-2020-1-119-125. (in Russ.)Ефанов Д. В. Троичные коды с суммированием для контроля цифровых схем // Проблемы управления. 2020. № 4. С. 63—71. DOI: 10.25728/pu.2020.4.6.Efanov D.V. Control sciences, 2020, no. 4, pp. 63–71, DOI: 10.25728/pu.2020.4.6. (in Russ.)Efanov D. Ternary Sum Codes // Proc. of the 18th IEEE East-West Design & Test Symp. (EWDTS’2020), Varna, Bulgaria, Sept. 4—7, 2020. P. 92—99. DOI: 10.1109/EWDTS50664.2020.9225033.Efanov D. Proceedings of 18th IEEE East-West Design & Test Symposium (EWDTS’2020), Varna, Bulgaria, September 4–7, 2020, pp. 92–99, DOI: 10.1109/EWDTS50664.2020.9225033.Ефанов Д. В. Ошибки в троичных кодовых векторах, их классификация и обнаружение с помощью помехозащищенного кодирования // Изв. вузов. Приборостроение. 2020. Т. 63, № 5. С. 391—404. DOI: 10.17586/0021-3454-2020-63-5-391-404.Efanov D.V. Journal of Instrument Engineering, 2020, no. 5(63), pp. 391–404, DOI: 10.17586/0021-3454-2020-63-5-391-404.Efanov D. Classification of Errors in Ternary Code Vectors from the Standpoint of Their Use in the Synthesis of Self-Checking Digital Systems // Proc. of the 18th IEEE East-West Design & Test Symp. (EWDTS’2020), Varna, Bulgaria, Sept. 4-7, 2020. P. 40—46. DOI: 10.1109/EWDTS50664.2020.9224826.Efanov D. Proceedings of 18th IEEE East-West Design & Test Symposium (EWDTS’2020), Varna, Bulgaria, September 4–7, 2020, pp. 40–46, DOI: 10.1109/EWDTS50664.2020.9224826.Поспелов Д. А. Логические методы анализа и синтеза схем. М.: Энергия, 1974. 368 с.Pospelov D.A. Logicheskiye metody analiza i sinteza skhem (Logical Methods of Analysis and Synthesis of Circuits), Moscow, 1974, 368 р. (in Russ.)Ефанов Д. В., Сапожников В. В., Сапожников Вл. В. О свойствах кода с суммированием в схемах функционального контроля // Автоматика и телемеханика. 2010. № 6. С. 155—162.Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Automation and Remote Control, 2010, no. 6, pp. 1117–1123.Ефанов Д. В., Сапожников В. В., Сапожников Вл. В. Применение модульных кодов с суммированием для построения систем функционального контроля комбинационных логических схем // Автоматика и телемеханика. 2015. № 10. С. 152—169.Efanov D.V., Sapozhnikov V.V. Automation and Remote Control, 2015, no. 10, pp. 1834–1848.Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды с суммированием для систем технического диагностирования. Т. 1. Классические коды Бергера и их модификации. М.: Наука, 2020. 383 с.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniyem dlya sistem tekhnicheskogo diagnostirovaniya. T. 1. Klassicheskiye kody Bergera i ikh modifikatsii (Summed Codes for Technical Diagnostic Systems. Vol. 1. Classical Berger Codes and Their Modifications), Moscow, 2020, 383 р. (in Russ.).Ефанов Д. В. Троичный код паритета в системах рабочего диагностирования устройств автоматики и вычислительной техники // Информационные технологии. 2019. Т. 25, № 7. С. 426—434. DOI: 10.17587/it.25.426-434.Efanov D.V. Information Technologies, 2019, no. 7(25), pp. 426–434, DOI: 10.17587/it.25.426-434. (in Russ.)Efanov D. V. Ternary Parity Codes: Features // Proc. of the 17th IEEE East-West Design & Test Symp. (EWDTS’2019), Batumi, Georgia, Sept. 13—16, 2019. P. 315—319. DOI: 10.1109/EWDTS.2019.8884414.Efanov D.V. Proceedings of 17th IEEE East-West Design & Test Symposium (EWDTS’2019), Batumi, Georgia, September 13–16, 2019, pp. 315–319, DOI: 10.1109/EWDTS.2019.8884414.Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды с суммированием для систем технического диагностирования. Т. 2. Взвешенные коды с суммированием. М.: Наука, 2021. 455 с.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniyem dlya sistem tekhnicheskogo diagnostirovaniya. T. 2. Vzveshennyye kody s summirovaniyem (Summed Codes for Technical Diagnostic Systems. Vol. 2. Weighted Codes with Summation), Moscow, 2021, 455 р. (in Russ.)

The authors declare that there are no conflicts of interest present.