Синтез самопроверяемых комбинационных устройств на основе кодов с эффективным обнаружением симметричных ошибок
Ключевые слова:
логические устройства автоматики, контролепригодная структура, техническая диагностика, диагностирование, контроль технического состояния, равномерный блочный код, код Бергера, коды с суммированием, обнаружение ошибок.Аннотация
При создании надежных и безопасных компонентов систем автоматического управления часто используются методы помехоустойчивого кодирования — как при передаче данных между узлами системы, так и на уровне архитектуры аппаратных и программных средств. Широко применяется избыточное кодирование при организации контроля комбинационных логических устройств. При этом используются коды, ориентированные именно на обнаружение, а не исправление ошибок. Такие особенности кодов позволяют реализовывать контролепригодные системы автоматики с приемлемой избыточностью, не превышающей избыточности при использовании дублирования. В статье освещается метод синтеза самопроверяемых комбинационных устройств, позволяющий учитывать при решении задачи синтеза технических средств диагностирования особенности архитектуры исходных устройств, а также свойства обнаружения ошибок избыточными кодами. Даются базовые сведения из теории синтеза контролепригодных дискретных систем на основе избыточных кодов с суммированием. Определены ключевые этапы анализа топологий объектов диагностирования с выделением специальных групп выходов — групп структурно и функционально симметрично независимых выходов устройств. Приводятся формулы, позволяющие установить наличие или отсутствие симметричной зависимости выходов объекта диагностирования. Дается пример, иллюстрирующий процесс вычислений. Сформулированы основные этапы анализа применения избыточных кодов при выявлении ошибок на функционально симметрично зависимых выходах. Дан алгоритм синтеза самопроверяемых логических устройств с учетом особенностей структуры объекта диагностирования и свойств избыточных кодов.Литература
1. Сапожников В.В., Сапожников Вл.В., Христов Х.А., Гавзов Д.В. Методы построения безопасных микроэлектронных систем железнодорожной автоматики / под ред. Вл.В. Сапожникова // М.: Транспорт. 1995. 272 с.
2. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source) // New York: IGI Global. 2011. 578 p.
3. Drozd A. et al. The use of natural resources for increasing a checkability of the digital components in safety-critical systems // Proceedings of 11th IEEE East-West Design & Test Symposium (EWDTS`2013). 2013. pp. 1–6.
4. 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.
5. Sklyar V., Kharchenko V., Bardis N.G. Assurance case for green IT applications: proof of compliance with power consumption claims // Proceedings of 4th International Conference on Mathematics and Computers in Sciences and in Industry (MCSI). 2017. pp. 124–127.
6. Аксёнова Г.П. Локализация кратных неисправностей при групповом контроле в дискретном устройстве // Автоматика и телемеханика. 2017. № 12. С. 118–130.
7. Drozd O., Nikul V., Antoniuk V., Drozd M. hidden faults in FPGA-built digital components of safety-related systems // Proceedings of 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET). 2018 pp. 805–809.
8. Shah T., Matrosova A., Singh V. Test pattern generation to detect multiple faults in ROBDD based combinational circuits // Proceedings of IEEE 23rd International Symposium on On-Line Testing and Robust System Design (IOLTS). 2017. pp. 211–2012.
9. Mosin S. Automated simulation of faults in analog circuits based on parallel paradigm // Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS`2017). 2017. pp. 73–78.
10. Аксёнова Г.П. Матричный способ локализации неисправностей в ПЛИС // Автоматика и телемеханика. 2013. № 9. С. 119–124.
11. Dautov R., Mosin S. A Technique to aggregate classes of analog fault diagnostic data based on association rule mining // Proceedings of 19th International Symposium on Quality Electronic Design (ISQED). 2018. pp. 238–243.
12. Бибило П.Н. и др. Автоматизация логического синтеза КМОП схем с пониженным энергопотреблением // Программная инженерия. 2013. № 8. С. 35–41.
13. Черемисинова Л.Д. Логический синтез комбинационных КМОП схем с учетом рассеивания мощности // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2014. № 3. C. 89–98.
14. Поттосин Ю.В. Энергосберегающее противогоночное кодирование состояний асинхронного автомата // Прикладная дискретная математика. Приложение. 2015. № 8. С. 120–123.
15. Степченков Ю.А., Каменских А.Н., Тюрин С.Ф., Рождественский Ю.В. Модели отказоустойчивых самосинхронных схем // Системы и средства информатики. 2016. Том 26. № 4. С. 19–30.
16. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы // М.: Радио и связь. 1989. 208 с.
17. Nicolaidis M., Zorian Y. On-Line Testing for VLSI – А Compendium of Ap-proaches // Journal of Electronic Testing: Theory and Applications. 1998. vol. 12. pp. 7–20.
18. Матросова А.Ю., Останин С.А., Паршина Н.А. К синтезу контролепригод-ных комбинационных устройств // Автоматика и телемеханика. 1999. № 2. C. 129–137.
19. Nicolaidis M. On-Line Testing for VLSI: State of the Art and Trends // Integration, the VLSI Journal. 1998. vol. 26. Issue 1-2. pp. 197–209.
20. 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.
21. Mitra S., McCluskey E.J. Which concurrent error detection scheme to сhoose? // Proceedings of International Test Conference. 2000. pp. 985–994.
22. Kubalík P., Kubátová H. Parity Codes Used for On-Line Testing in FPGA // Acta Polytechnika. 2005. vol. 45. no. 6. pp. 53–59.
23. Butorina N. Self-testing checker design for incomplete m-out-of-n codes // Proceedings of 12th IEEE East-West Design & Test Symposium (EWDTS`2014). 2014. pp. 258–261.
24. Сапожников В.В., Сапожников Вл.В. Самопроверяемые дискретные устройства // СПб: Энергоатомиздат. 1992. 224 с.
25. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes // Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej. 1995. 111 p.
26. 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.
27. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications // New Jersey: John Wiley & Sons. 2006. 720 p.
28. Borecký J., Kohlík M., Kubátová H. Parity Driven Reconfigurable Duplex System // Microprocessors and Microsystems. 2017. vol. 52. pp. 251–260.
29. Бибило П.Н., Романов В.И. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний // Минск: Беларус. навука. 2011. 279 с.
30. Sogomonyan E.S., Gössel M. Design of Self-Testing and On-Line Fault Detection Combinational Circuits with Weakly Independent Outputs // Journal of Electronic Testing: Theory and Applications. 1993. vol. 4. Issue 4. pp. 267–281.
31. Гессель М., Морозов А.А., Сапожников В.В., Сапожников Вл.В. Исследование комбинационных самопроверяемых устройств с независимыми и монотонно независимыми выходами // Автоматика и телемеханика. 1997. № 2. С. 180–193.
32. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking: Edition 1 // Springer Netherlands. 2008. 184 p.
33. Berger J.M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. vol. 4. Issue 1. pp. 68–73.
34. Freiman C.V. Optimal Error Detection Codes for Completely Asymmetric Binary Channels // Information and Control. 1962. vol. 5. Issue 1. pp. 64–71.
35. 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. vol. 5. Issue 1. pp. 19–28.
36. Saposhnikov V.V., Morosov A., Saposhnikov Vl.V., Göessel M. A New Design Method for Self-Checking Unidirectional Combinational Circuits // Journal of Electronic Testing: Theory and Applications. 1998. vol. 12. Issue 1-2. pp. 41–53.
37. Morosow A., Sapozhnikov V.V., Sapozhnikov Vl.V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. 1998. vol. 5. Issue 4. pp. 333–345.
38. Матросова А.Ю., Останин С.А., Сингх В. Обнаружение несущественных путей логических схем на основе совместного анализа И-ИЛИ деревьев и SSBDD-графов // Автоматика и телемеханика. 2013. № 7. C. 126–142.
39. Ostanin S. Self-checking synchronous FSM network design for path delay faults // Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS`2017). 2017. pp. 696–699.
40. Matrosova A., Andreeva V., Tomkov V. Fully delay and multiple stuck-at faults testable fsm design // Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS`2015). 2015. pp. 212–215.
41. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Классификация ошибок в информационных векторах систематических кодов // Известия вузов. Приборостроение. 2015. Том 58. № 5. С. 333–343.
42. Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generalized algorithm of building summation codes for the tasks of technical diagnostics of discrete systems // Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS`2017). 2017. pp. 365–371.
43. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Условия обнаружения неисправности логического элемента в комбинационном устройстве при функциональном контроле на основе кода Бергера // Автоматика и телемеханика. 2017. № 5. С. 152–165.
44. Das D., Touba N.A. Weight-based codes and their application to concurrent error detection of multilevel circuits // Proceedings of 17th IEEE Test Symposium. 1999. pp. 370–376.
45. Das D., Touba N.A., Seuring M., Goessel M. Low cost concurrent error detection based on modulo weight-based codes // Proceedings of IEEE 6th International On-Line Testing Workshop (IOLTW). 2000. pp. 171–176.
46. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Коды с суммированием, обнаруживающие любые симметричные ошибки // Электронное моделирование. 2017. Том 39. № 3. С. 47–60.
47. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Two-Modulus Codes with Summation of One-Data Bits for Technical Diagnostics of Discrete Systems // Automatic Control and Computer Sciences. 2018. vol. 52. Issue 1. pp. 1–12.
48. Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generic two-modulus sum codes for technical diagnostics of discrete systems problems // Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS`2016). 2016. pp. 256–260.
49. Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О кодах с суммированием единичных разрядов в системах функционального контроля // Автоматика и телемеханика. 2014. № 8. С. 131–145.
50. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Взвешенные коды с суммированием для организации контроля логических устройств // Электронное моделирование. 2014. Том 36. № 1. С. 59–80.
2. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source) // New York: IGI Global. 2011. 578 p.
3. Drozd A. et al. The use of natural resources for increasing a checkability of the digital components in safety-critical systems // Proceedings of 11th IEEE East-West Design & Test Symposium (EWDTS`2013). 2013. pp. 1–6.
4. 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.
5. Sklyar V., Kharchenko V., Bardis N.G. Assurance case for green IT applications: proof of compliance with power consumption claims // Proceedings of 4th International Conference on Mathematics and Computers in Sciences and in Industry (MCSI). 2017. pp. 124–127.
6. Аксёнова Г.П. Локализация кратных неисправностей при групповом контроле в дискретном устройстве // Автоматика и телемеханика. 2017. № 12. С. 118–130.
7. Drozd O., Nikul V., Antoniuk V., Drozd M. hidden faults in FPGA-built digital components of safety-related systems // Proceedings of 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET). 2018 pp. 805–809.
8. Shah T., Matrosova A., Singh V. Test pattern generation to detect multiple faults in ROBDD based combinational circuits // Proceedings of IEEE 23rd International Symposium on On-Line Testing and Robust System Design (IOLTS). 2017. pp. 211–2012.
9. Mosin S. Automated simulation of faults in analog circuits based on parallel paradigm // Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS`2017). 2017. pp. 73–78.
10. Аксёнова Г.П. Матричный способ локализации неисправностей в ПЛИС // Автоматика и телемеханика. 2013. № 9. С. 119–124.
11. Dautov R., Mosin S. A Technique to aggregate classes of analog fault diagnostic data based on association rule mining // Proceedings of 19th International Symposium on Quality Electronic Design (ISQED). 2018. pp. 238–243.
12. Бибило П.Н. и др. Автоматизация логического синтеза КМОП схем с пониженным энергопотреблением // Программная инженерия. 2013. № 8. С. 35–41.
13. Черемисинова Л.Д. Логический синтез комбинационных КМОП схем с учетом рассеивания мощности // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2014. № 3. C. 89–98.
14. Поттосин Ю.В. Энергосберегающее противогоночное кодирование состояний асинхронного автомата // Прикладная дискретная математика. Приложение. 2015. № 8. С. 120–123.
15. Степченков Ю.А., Каменских А.Н., Тюрин С.Ф., Рождественский Ю.В. Модели отказоустойчивых самосинхронных схем // Системы и средства информатики. 2016. Том 26. № 4. С. 19–30.
16. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы // М.: Радио и связь. 1989. 208 с.
17. Nicolaidis M., Zorian Y. On-Line Testing for VLSI – А Compendium of Ap-proaches // Journal of Electronic Testing: Theory and Applications. 1998. vol. 12. pp. 7–20.
18. Матросова А.Ю., Останин С.А., Паршина Н.А. К синтезу контролепригод-ных комбинационных устройств // Автоматика и телемеханика. 1999. № 2. C. 129–137.
19. Nicolaidis M. On-Line Testing for VLSI: State of the Art and Trends // Integration, the VLSI Journal. 1998. vol. 26. Issue 1-2. pp. 197–209.
20. 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.
21. Mitra S., McCluskey E.J. Which concurrent error detection scheme to сhoose? // Proceedings of International Test Conference. 2000. pp. 985–994.
22. Kubalík P., Kubátová H. Parity Codes Used for On-Line Testing in FPGA // Acta Polytechnika. 2005. vol. 45. no. 6. pp. 53–59.
23. Butorina N. Self-testing checker design for incomplete m-out-of-n codes // Proceedings of 12th IEEE East-West Design & Test Symposium (EWDTS`2014). 2014. pp. 258–261.
24. Сапожников В.В., Сапожников Вл.В. Самопроверяемые дискретные устройства // СПб: Энергоатомиздат. 1992. 224 с.
25. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes // Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej. 1995. 111 p.
26. 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.
27. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications // New Jersey: John Wiley & Sons. 2006. 720 p.
28. Borecký J., Kohlík M., Kubátová H. Parity Driven Reconfigurable Duplex System // Microprocessors and Microsystems. 2017. vol. 52. pp. 251–260.
29. Бибило П.Н., Романов В.И. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний // Минск: Беларус. навука. 2011. 279 с.
30. Sogomonyan E.S., Gössel M. Design of Self-Testing and On-Line Fault Detection Combinational Circuits with Weakly Independent Outputs // Journal of Electronic Testing: Theory and Applications. 1993. vol. 4. Issue 4. pp. 267–281.
31. Гессель М., Морозов А.А., Сапожников В.В., Сапожников Вл.В. Исследование комбинационных самопроверяемых устройств с независимыми и монотонно независимыми выходами // Автоматика и телемеханика. 1997. № 2. С. 180–193.
32. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking: Edition 1 // Springer Netherlands. 2008. 184 p.
33. Berger J.M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. vol. 4. Issue 1. pp. 68–73.
34. Freiman C.V. Optimal Error Detection Codes for Completely Asymmetric Binary Channels // Information and Control. 1962. vol. 5. Issue 1. pp. 64–71.
35. 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. vol. 5. Issue 1. pp. 19–28.
36. Saposhnikov V.V., Morosov A., Saposhnikov Vl.V., Göessel M. A New Design Method for Self-Checking Unidirectional Combinational Circuits // Journal of Electronic Testing: Theory and Applications. 1998. vol. 12. Issue 1-2. pp. 41–53.
37. Morosow A., Sapozhnikov V.V., Sapozhnikov Vl.V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. 1998. vol. 5. Issue 4. pp. 333–345.
38. Матросова А.Ю., Останин С.А., Сингх В. Обнаружение несущественных путей логических схем на основе совместного анализа И-ИЛИ деревьев и SSBDD-графов // Автоматика и телемеханика. 2013. № 7. C. 126–142.
39. Ostanin S. Self-checking synchronous FSM network design for path delay faults // Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS`2017). 2017. pp. 696–699.
40. Matrosova A., Andreeva V., Tomkov V. Fully delay and multiple stuck-at faults testable fsm design // Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS`2015). 2015. pp. 212–215.
41. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Классификация ошибок в информационных векторах систематических кодов // Известия вузов. Приборостроение. 2015. Том 58. № 5. С. 333–343.
42. Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generalized algorithm of building summation codes for the tasks of technical diagnostics of discrete systems // Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS`2017). 2017. pp. 365–371.
43. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Условия обнаружения неисправности логического элемента в комбинационном устройстве при функциональном контроле на основе кода Бергера // Автоматика и телемеханика. 2017. № 5. С. 152–165.
44. Das D., Touba N.A. Weight-based codes and their application to concurrent error detection of multilevel circuits // Proceedings of 17th IEEE Test Symposium. 1999. pp. 370–376.
45. Das D., Touba N.A., Seuring M., Goessel M. Low cost concurrent error detection based on modulo weight-based codes // Proceedings of IEEE 6th International On-Line Testing Workshop (IOLTW). 2000. pp. 171–176.
46. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Коды с суммированием, обнаруживающие любые симметричные ошибки // Электронное моделирование. 2017. Том 39. № 3. С. 47–60.
47. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Two-Modulus Codes with Summation of One-Data Bits for Technical Diagnostics of Discrete Systems // Automatic Control and Computer Sciences. 2018. vol. 52. Issue 1. pp. 1–12.
48. Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generic two-modulus sum codes for technical diagnostics of discrete systems problems // Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS`2016). 2016. pp. 256–260.
49. Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О кодах с суммированием единичных разрядов в системах функционального контроля // Автоматика и телемеханика. 2014. № 8. С. 131–145.
50. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Взвешенные коды с суммированием для организации контроля логических устройств // Электронное моделирование. 2014. Том 36. № 1. С. 59–80.
Опубликован
2018-08-01
Как цитировать
Ефанов, Д. В. (2018). Синтез самопроверяемых комбинационных устройств на основе кодов с эффективным обнаружением симметричных ошибок. Труды СПИИРАН, 4(59), 62-91. https://doi.org/10.15622/sp.59.3
Раздел
Информационная безопасность
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
