Содержание к диссертации
Введение
ГЛАВА 1. Применение функционального диагностирования в системах автоматического и автоматизированногоуправления на транспорте 21
1.1 Методы повышения отказоустойчивости и безопасного поведения при отказах устройств автоматики 21
1.2 Методы функционального диагностирования в современных логических устройств автоматики и вычислительной техники .
1.2.1 Особенности систем функционального диагностирования логических устройств 23
1.2.2 Характеристики систем функционального диагностирования 25
1.2.3 Модифицированная структурная схема системы функционального диагностирования на основе логического дополнения 37
1.2.4 Разделимые коды в системах функционального диагностирования 38
1.2.5 Использование свойств разделимых кодов и особенных классов функций алгебры логики при построении систем функционального диагностирования 1.3 Классификация методов организации системы функционального диагностирования 49
1.4 Выводы по главе 51
ГЛАВА 2. Характеристики ошибок на рабочих выходах систем функционального диагностирования
2.1 Виды неисправностей в структурах комбинационных логических устройств 53
2.2 Классификация ошибок на рабочих выходах систем функционального диагностирования 54
2.3 Особенности различных видов ошибок на рабочих выходах систем диагностирования 65
2.4 Выводы по главе 73
ГЛАВА 3. Свойства кодов с суммированием единичных информационных разрядов в системах функционального диагностирования 75
3.1 Обнаружение ошибок на рабочих выходах систем функционального диагностирования различными разделимыми кодами 75
3.2 Классические и модульные коды с суммированием в системах функционального диагностирования 76
3.3 Оптимальные по критерию минимума общего количества необнаруживаемых ошибок разделимые коды для систем функционального диагностирования 87
3.4 Модифицированные и модульно модифицированные коды с суммированием единичных информационных разрядов в системах функционального диагностирования 95
3.5 Выводы по главе 113
ГЛАВА 4. Коды с суммированием взвешенных информационных разрядов в системах функционального диагностирования 115
4.1 Принципы построения кодов с суммированием взвешенных информационных разрядов 115
4.2 Коды с одним взвешенным разрядом 118
4.3 Код с последовательностью весовых коэффициентов, образующей натуральный ряд чисел 131
4.4 Коды с фиксированным количеством разрядов в контрольных векторах 138
4.5 Модифицированные и модульно модифицированные коды с суммированием взвешенных информационных разрядов в системах функционального диагностирования 141
4.6 Коды с суммированием без переносов двоичных эквивалентов весовых коэффициентов разрядов 156
4.7 Выводы по главе 160
ГЛАВА 5. Коды с суммированием взвешенных переходов между информационными разрядами в системах функционального диагностирования
5.1 Принципы построения кодов с суммированием взвешенных переходов между информационными разрядами 162
5.2 Коды со взвешенным переходом между двумя информационными разрядами 167
5.3 Классические и модульные коды с суммированием взвешенных переходов 170
5.4 Коды с фиксированным количеством разрядов в контрольных векторах 183
5.5 Коды с суммированием, полученные путем перестановки суммарных весовых коэффициентов модифицированных кодов с суммированием взвешенных переходов 191
5.6 Выводы по главе 203
ГЛАВА 6. Синтез тестеров кодов с суммированием
6.1 Характеристики тестеров кодов с суммированием 205
6.2 Универсальная структура генераторов кодов с суммированием 207
6.3 Базовый метод синтеза генераторов кодов с суммированием 209
6.4 Синтез генераторов модульных кодов с суммированием 216
6.5 Синтез генераторов модифицированных и модульно модифицированных кодов с суммированием 221
6.6 Выводы по главе 223
ГЛАВА 7. Синтез систем функционального диагностирования с обнаружением любых одиночных неисправностей
7.1 Методы построения систем функционального диагностирования со 100%-ным обнаружением одиночных неисправностей 224
7.2 Метод контроля логических схем на основе выделения групп выходов, допускающих как монотонное, так и асимметричное искажение 227
7.3 Условия применения для контроля логических схем различных кодов с суммированием 247
7.4 Синтез систем функционального диагностирования со 100%-ным обнаружением неисправностей с использованием характеристик кодов с суммированием без модификации структуры контролируемого устройства 250
7.5 К вопросу классификации кодов с суммированием 257
7.6 Алгоритм организации системы функционального диагностирования 261
7.7 Выводы по главе 264
ГЛАВА 8. Совершенствование систем функционального диагностирования и мониторинга устройств железнодорожной автоматики и телемеханики 265
8.1 Системы функционального диагностирования и мониторинга устройств железнодорожной автоматики и телемеханики 265
8.2 Метод автоматизации анализа диагностической информации в системах функционального диагностирования и мониторинга объектов железнодорожной автоматики 267 8.3 Об экономической эффективности систем мониторинга устройств железнодорожной инфраструктуры 285
8.4 Выводы по главе 286
Заключение 288
Список использованных источников
- Характеристики систем функционального диагностирования
- Классификация ошибок на рабочих выходах систем функционального диагностирования
- Классические и модульные коды с суммированием в системах функционального диагностирования
- Модифицированные и модульно модифицированные коды с суммированием взвешенных информационных разрядов в системах функционального диагностирования
Введение к работе
Актуальность темы диссертационного исследования обусловлена
высокими темпами развития микроэлектронной и микропроцессорной
техники, используемой в качестве элементной базы для современных
систем автоматического управления и контроля, к которым относятся, в
том числе, и средства железнодорожной автоматики и телемеханики
(ЖАТ), а также необходимостью их непрерывного мониторинга.
Усложнение микроэлектронной и микропроцессорной техники идет по
пути повышения плотности интеграции транзисторов и размещения как
можно большего их количества на кристалле. Плотность интеграции
элементов с каждым годом возрастает, увеличивается быстродействие
элементов, а также расширяются функциональные возможности
синтезируемых на их основе систем. Однако усложнение систем обостряет
проблему надежности и безопасности функционирования
микроэлектронных и микропроцессорных элементов.
Важными мерами обеспечения надежности и безопасности
функционирования современных систем автоматического управления и
контроля являются использование высоконадежной элементной базы с
низкими значениями интенсивностей отказов, применение методов
резервирования и технического диагностирования, использование
самопроверяемых логических схем встроенного контроля и т.д. С развитием элементной базы систем управления и контроля активно развиваются и методы определения текущего технического состояния и прогнозирования дальнейших изменений в блоках различной физической природы, реализующих разнообразные логические функции. От того, какой будет архитектура управляющего объекта, и от методов его тестирования будет зависеть своевременность фиксации сбоев и устойчивых отказов, в том числе, работа средств парирования опасных отказов.
В настоящее время многие устройства управления и контроля
снабжаются развитым диагностическим обеспечением. Оно входит как в
сами блоки управления в виде средств самодиагностирования (встроенные
средства диагностирования), так и реализуются подключением
специализированных измерительных датчиков, позволяющих в режиме реального времени фиксировать ключевые параметры устройств управления (внешние средства диагностирования).
Таким образом, развитие методов диагностирования – это некоторая объективная тенденция, сопровождающая научно-технический прогресс в области микроэлектронной и микропроцессорной техники.
В диссертационном исследовании развиваются теория и методы
функционального диагностирования на основе применения
помехоустойчивых кодов с высокой кодовой скоростью. При этом полученные решения основываются на свойствах обнаружения ошибок кодами. Это обусловлено следующими причинами: во-первых, от избыточности кода зависит сложность технической реализации системы функционального диагностирования, а значит, стоимость ее разработки и эксплуатации; во-вторых, коррекция ошибок при возникновении сбоев зачастую просто не требуется – достаточно отключить выходы, неверно вычисляющие управляющие функции, от объектов управления (более того, исправление ошибки на аппаратном уровне реализации приведет к накоплению неисправностей).
Из всего вышесказанного следует сделать заключение об актуальности темы диссертационного исследования, направленной на развитие теории и методов функционального диагностирования логических устройств автоматики и вычислительной техники, в том числе, в области ЖАТ.
Степень разработанности темы исследования. Техническая диагностика – как отдельное направление технической кибернетики и теории автоматического управления развивается с середины XX века по настоящее время. В области технической диагностики дискретных систем
работали и работают такие отечественные ученые как Г. П. Аксенова,
В. А. Ведешенков, А. В. Дрозд, А. Д. Закревский, М. Ф. Каравай,
И. С. Левин, А. Ю. Матросова, О. Ф. Немолочнов, П. П. Пархоменко,
Вал. В. Сапожников, Вл. В. Сапожников, Ю. А. Скобцов, Е. В. Слабаков,
Е. С. Согомонян, Д. В. Сперанский, В. А. Твердохлебов, В. С. Харченко,
В. И. Хаханов, В. Н. Ярмолик и многие другие. В области диагностики
непрерывных дискретных систем известны такие ученые как
Д. В. Гаскаров, Н. В. Евтушенко, В. П. Калявин, Н. Г. Кушик, А. В. Мозгалевский, С. Г. Мосин и многие другие. Вопросами технической диагностики за рубежом занимались и занимаются такие известные ученые как M. S. Abadir, M. Abramovici, V. K. Agarwal, L. Anghel, A. A. Aviienis, M. Bayoumi, B. Becker, R. Bennets, V. Champac, M. Gssel, D. Das, S. Davidson, E. Fujiiwara, R. Kapur, P. K. Lala, X. Li, E. J. Marinissen, E. J. McCluskey, Z. Navabi, M. Nicolaidis, V. Piuri, D. K. Pradhan, P. Prinetto, M. Renovell, J. Roth, F. F. Sellers, A. Singh, V. Singh, S. Shoukourian, N. A. Touba, R. Ubar, J. F. Wakerly, H.-J. Wunderlich, Y. Zorian и многие другие.
Вопросами функционального диагностирования логических схем автоматики и вычислительной техники в СССР и в Российской Федерации занимались и занимаются многие ученые, в том числе, четырех крупных научных школ. Следует выделить работы ученых лаборатории технической диагностики и отказоустойчивости Института проблем управления им. В. А. Трапезникова Российской академии наук Г. П. Аксеновой, М. Ф. Каравая, П. П. Пархоменко, Е. В. Слабакова, Е. С. Согомоняна и др. Известна научная школа кафедры автоматики и телемеханики на железных дорогах Ленинградского института инженеров железнодорожного транспорта (ныне Петербургского государственного университета путей сообщения Императора Александра I), возглавляемая братьями Вал. В. Сапожниковым и Вл. В. Сапожниковым, в трудах которых можно найти большое количество материалов на тему применения свойств избыточных кодов при синтезе надежных дискретных
систем. Следует также выделить научную школу проф. А. Д. Закревского,
ставшего родоначальником многих направлений в теории дискретных
устройств и оптимизации логических схем в Томском государственном
университете и в Белорусской академии наук (г. Минск). Нельзя обойти
вниманием и томскую научную школу диагностики, занимающуюся
вопросами тестирования логических схем автоматики, которую
возглавляет А. Ю. Матросова, а исследованиями под ее началом
занимаются такие ученые как В. В. Андреева, Н. Б. Буторина, С. А. Останин и другие.
Большой вклад в развитие теории надежности и диагностики в транспортной отрасли постсоветского пространства внесли такие ученые как Д. В. Гавзов, В. И. Королев, Ю. А. Кравцов, В. М. Лисенков, С. А. Никищенков, Е. Н. Розенберг, Вал. В. Сапожников, Вл. В. Сапожников, В. С. Харченко, В. И. Шаманов и др.
Несмотря на большое количество работ ученых в области технической диагностики, они не полностью охватывают теорию и методы функционального диагностирования логических схем автоматики и вычислительной техники, в особенности, в области ЖАТ.
Тема диссертации соответствует паспорту специальности
05.13.06 «Автоматизация и управление технологическими процессами и производствами (транспорт)» по пунктам:
п. 8. Формализованные методы анализа, синтеза, исследования и оптимизация модульных структур систем сбора и обработки данных в АСУТП, АСУП, АСПТП и др.;
п. 13. Теоретические основы и прикладные методы анализа и повышения эффективности, надежности и живучести АСУ на этапах их разработки, внедрения и эксплуатации;
п. 14. Теоретические основы, методы и алгоритмы диагностирования
(определения работоспособности, поиск неисправностей и
прогнозирования), АСУТП, АСУП, АС ТПП и др.
Цели и задачи диссертации. Основной целью диссертационного
исследования является разработка теории и методов функционального
диагностирования логических устройств автоматики и вычислительной
техники на основе использования помехоустойчивых кодов с
суммированием.
Для достижения указанной цели ставятся и решаются следующие задачи:
-
Обобщение научных результатов в области функционального диагностирования с указанием места использования при их организации кодов с суммированием.
-
Разработка классификации ошибок на выходах контролируемых устройств (в информационных векторах), а также определение основных зависимостей между различными видами ошибок в информационных векторах заданной длины.
-
Анализ характеристик обнаружения ошибок в информационных векторах классическими и модульными кодами с суммированием единичных информационных разрядов, а также разработка алгоритмов построения кодов с суммированием с улучшенными характеристиками обнаружения ошибок в информационных векторах при малой длине контрольных векторов.
-
Исследование влияния взвешивания разрядов и переходов между разрядами, занимающими соседние позиции в информационных векторах, на свойства обнаружения ошибок кодами с суммированием.
-
Разработка кодов с суммированием с минимальным общим количеством необнаруживаемых ошибок в информационных векторах с заданными длинами контрольных векторов.
-
Разработка универсальных методов синтеза контрольного оборудования систем функционального диагностирования.
-
Разработка способов построения систем функционального диагностирования с максимальной эффективностью обнаружения ошибок
в контролируемых объектах при минимальной сложности их технической реализации.
8. Практическое применение разработанных кодов с
суммированием и способов построения систем функционального диагностирования в устройствах непрерывного мониторинга объектов железнодорожной инфраструктуры, в том числе, автоматики и телемеханики.
Объектом исследования являются системы функционального диагностирования, базирующиеся на использовании помехоустойчивых кодов с высокой кодовой скоростью, а предметом – характеристики известных и вновь разрабатываемых кодов для систем функционального диагностирования логических устройств автоматики и вычислительной техники, а также методы анализа и синтеза структур систем функционального диагностирования с обеспечением заданных свойств.
Научная новизна диссертационного исследования заключается в следующем:
-
Выявлены новые свойства классических и модульных кодов с суммированием единичных информационных разрядов по обнаружению ошибок различных видов и кратностей в системах функционального диагностирования логических устройств.
-
Предложены алгоритмы модификации кодов с суммированием единичных разрядов, позволяющие получать новые коды с небольшой избыточностью и улучшенными свойствами обнаружения ошибок в информационных векторах.
-
Проанализировано влияние взвешивания разрядов и переходов между разрядами, занимающими соседние позиции в информационных векторах, на свойства обнаружения ошибок различных видов в информационных векторах кодов с суммированием.
-
Разработаны алгоритмы построения кодов с суммированием, имеющих наименьшее общее количество необнаруживаемых ошибок при заданных длинах информационных и контрольных векторов.
-
Предложены способы построения кодов с суммированием, идентифицирующих 100% ошибок определенных видов (монотонных, симметричных или асимметричных) в информационных векторах.
-
Разработан универсальный метод синтеза генераторов кодов с суммированием (устройств, формирующих значения разрядов контрольных векторов по значениям разрядов информационных векторов), учитывающий различные модификации кодов, а также возможность взвешивания разрядов или переходов между разрядами, занимающими соседние позиции в информационных векторах.
-
Разработаны алгоритмы и методы модификации структур логических схем в контролепригодные структуры на основе установленных в диссертационном исследовании новых свойств кодов с суммированием.
-
Предложены методы совершенствования технологии мониторинга устройств железнодорожной инфраструктуры, в том числе ЖАТ, на основе разработанных в диссертационном исследовании кодов с суммированием.
Теоретическая значимость работы заключается в разработке
основных положений теории функционального диагностирования
логических устройств автоматики и вычислительной техники, основанных на выявленных в диссертации новых свойствах двоичных кодов с суммированием.
Практическая значимость работы связана с возможностью
использования ее результатов для обоснованного выбора кода с
суммированием при организации системы функционального
диагностирования конкретного логического устройства с известными свойствами его топологии, а также в приложении разработанных модифицированных кодов с суммированием в задачах организации средств самодиагностирования объектов управления и контроля и средств внешнего непрерывного мониторинга их технического состояния.
Методология и методы исследования. Использованы методы булевой алгебры, теории чисел, теории дискретных устройств, технической диагностики и комбинаторного анализа.
Положения, выносимые на защиту:
-
Классификация известных методов функционального диагностирования логических устройств автоматики и вычислительной техники с указанием особенностей ошибок, возникающих на выходах объектов диагностирования.
-
Результаты теоретических исследований классических и модульных кодов с суммированием единичных разрядов в информационных векторах.
-
Алгоритмы модификации кодов с суммированием, позволяющие повышать количество обнаруживаемых ими ошибок в информационных векторах по сравнению с классическими и модульными кодами с суммированием.
-
Результаты теоретических исследований взвешенных кодов с суммированием и их модификаций в системах функционального диагностирования.
-
Универсальный метод синтеза генераторов кодов с суммированием.
-
Метод модификации логических схем автоматики в схемы с контролепригодными структурами с уменьшенной избыточностью по сравнению с использованием для этих целей предложенных ранее подходов.
-
Технические предложения по совершенствованию технологии непрерывного мониторинга устройств железнодорожной инфраструктуры, в том числе, ЖАТ.
Степень достоверности результатов подтверждается корректным использованием математического аппарата теории дискретных устройств, технической диагностики и комбинаторики, а также строгими математическими доказательствами, корректными вычислениями и
экспериментальными исследованиями с системами контрольных логических схем.
Апробация результатов. Результаты диссертационной работы докладывались и обсуждались на 25 международных конференциях и научно-практических семинарах. Список включает в себя:
- международную конференцию, посвященную вопросам
проектирования и тестирования логических устройств, «IEEE East-West
Design & Test Symposium»:
о в 2012 году (г. Харьков, Украина);
о в 2013 году (г. Ростов-на-Дону, Российская Федерация);
о в 2014 году (г. Киев, Украина);
о в 2015 году (г. Батуми, Грузия);
о в 2016 году (г. Ереван, Армения);
Санкт-Петербургскую международную конференцию
«Региональная информатика» в 2012, 2014 и 2016 гг. (г. Санкт-Петербург, Российская Федерация);
- международную научно-практическую конференцию «Новые
информационные технологии в исследовании сложных структур»:
о в 2014 году (п. Катунь, респ. Алтай, Российская Федерация); о в 2016 году (г. Екатеринбург, Российская Федерация);
- международную научно-практическую конференцию
«ИнтеллектТранс» в 2012, 2013, 2014 и 2015 гг. (г. Санкт-Петербург,
Российская Федерация);
всероссийскую конференцию «Информационные технологии в управлении» в 2012 г. (г. Санкт-Петербург, Российская Федерация);
международную конференцию имени А. Ф. Терпугова «Информационные технологии и математическое моделирование» в 2015 г. (г. Анжеро-Судженск, Кемеровская обл., Российская Федерация);
международную конференцию «Информационные технологии в науке, образовании и управлении» в 2016 г. (п. Гурзуф, респ. Крым, Российская Федерация);
три доклада на семинарах в лаборатории №27 (технической диагностики и отказоустойчивости) Института проблем управления Российской академии наук им. В. А. Трапезникова (15.12.2014, 09.11.2015 и 14.11.2016) под руководством члена-корреспондента РАН П. П. Пархоменко и д-ра техн. наук М. Ф. Каравая (г. Москва, Российская Федерация);
- семинары «Автоматика и дискретная математика» на кафедре «Автоматика и телемеханика на железных дорогах» Петербургского государственного университета путей сообщения Императора Александра I в период с 2012 по 2017 гг. (г. Санкт-Петербург, Российская Федерация).
Основные научные и практические результаты
диссертационного исследования внедрены в аппаратно-программные комплексы функционального диагностирования и непрерывного мониторинга устройств ЖАТ на пространстве железных дорог Российской Федерации, а также использованы при организации универсального беспроводного тракта передачи диагностической информации для систем непрерывного мониторинга объектов железнодорожной инфраструктуры на Октябрьской ж.д.
Публикации. По теме диссертационного исследования опубликовано 160 печатных работ. Основные результаты диссертационного исследования опубликованы в 43 работах, в том числе, в 22 публикациях в изданиях, включенных в Перечень ВАК РФ, в 14 академических публикациях, в 14 публикациях, индексированных в международной базе цитируемости SCOPUS, и в 1 монографии. Полный список опубликованных работ представлен в Приложении А к диссертации.
Структура и объем диссертации. Основное содержание работы изложено на 316 страницах машинописного текста, включая 118 рисунков и 55 таблиц. Диссертация состоит из введения, восьми глав основного текста, заключения и 8 приложений, опубликованных отдельным томом; библиографический список включает в себя 301 наименование.
Характеристики систем функционального диагностирования
Центральной проблемой при разработке, проектировании и конструировании систем автоматического и автоматизированного управления как на транспорте, так и в промышленности, является обеспечение приемлемых характеристик надежности и безопасности функционирования [11, 69, 70, 79]. В силу развития научно-технического прогресса и повсеместного внедрения в качестве элементной базы микроэлектронных и микропроцессорных компонентов, имеющих несимметричную характеристику отказов, низкие пороги срабатывания, подверженные электромагнитному воздействию и т.д., активно развиваются и направления, связанные с прогнозированием отказов и их парированием в случае возникновения [57, 118, 291, 292, 298–300]. Все эти мероприятия связаны с внесением в структуру технического объекта существенной избыточности (как на аппаратном, так и на программном уровне).
Широкого распространения в технике (и не только железнодорожной автоматики и телемеханики) получили такие безопасные структуры управляющих комплексов, как системы «2 из 2» (дублирование), «2 из 3» (троирование с мажоритированием) и «2 по 2 из 2» (дублирование двухканальных систем) [289]. При построении данных структур используются схемы, позволяющие идентифицировать отказавший узел, и просигнализировать об этом техническому персоналу, без отключения самого управляющего комплекса от управляемых объектов.
В ЖАТ система управления «подключается» к объектам управления, расположенным в зоне движения поездов: к рельсовым цепям, стрелкам, светофорам, переездной автоматике и пр. [289]. Это и является причиной наличия подавляющего количества отказов в объектах автоматики, удаленных от поста управления (поста электрической централизации) – отказы данных средств составляют свыше 75% всех отказов устройств ЖАТ [29]. Актуальным в этой связи является использование не только мероприятий по ручному техническому обслуживанию, но и использование технических средств функционального диагностирования.
На уровне архитектуры системы управления к средствам функционального диагностирования относятся самопроверяемые схемы встроенного контроля (ССВК), или системы функционального диагностирования [97]. Вопросам их синтеза посвящена не одна публикация, например, [4, 12, 123, 145], а сама задача построения систем функционального диагностирования, отвечающих заданным требованиям по характеристикам обнаружения ошибок, структурной избыточности, контролепригодности, энергопотребления и т. д. – до сих пор актуальна! На уровне периодического контроля к средствам функционального диагностирования следует отнести средства непрерывного мониторинга технического состояния [45, 78, 149]. Системы мониторинга активно развиваются во всех областях транспорта и промышленности, не исключая и систем обеспечения движения поездов. Системы непрерывного мониторинга на железнодорожном транспорте активно развиваются с конца 80-х гг. прошлого столетия и сегодня достигли высокого уровня развития. Их использование позволяет не только в автоматизированном (а в некоторых случаях – и в автоматическом) режиме измерять ответственные параметры устройств и систем управления, но и реализовывать главную стратегию обеспечения отказоустойчивости – прогнозировать техническое состояние. Использование средств функционального диагностирования как на уровне архитектуры системы управления, так и на уровне периодического контроля, позволяет обеспечивать надежную и безопасную реализацию ответственных технологических процессов.
Использование элементов с несимметричными отказами Внутренний контроль Безопасное кодирование внутренних состояний Тестирование отдельных блоков и узлов Резервирование блоков и узлов Техническое обслуживание Использование самопроверяемых схем встроенного контроля Непрерывный мониторинг технического состояния Т Функциональное диагностирование Рис. 1.1. Классификация методов обеспечения отказоустойчивости и безопасного поведения при отказах 1.2 Методы функционального диагностирование в современных логических устройств автоматики и вычислительной техники
При построении отказоустойчивых систем автоматики и вычислительной техники часто используют устройства с обнаружением и исправлением возникающих неисправностей. Наличие подобного свойства у устройства связано с внесением избыточности в его структуру – резервированием. Для идентификации отказавших блоков и узлов используют самопроверяемые схемы встроенного контроля, безопасные схемы сравнения, безопасные мажоритарные элементы и т.п. Такие объекты в составе систем управления должны обнаруживать 100% одиночных неисправностей на выходах логических элементов внутренней структуры контролируемых устройств, а также любые собственные неисправности.
В логических схемах автоматики и вычислительной техники, как правило, могут быть выделены два типа узлов: комбинационные составляющие и регистры памяти. Для тестирования регистров памяти, к примеру, применяют методы сканирования [56, 118]. Для комбинационных составляющих схем автоматики используют развитые методы тестового и функционального диагностирования (concurrent error detection systems – CED systems) [9, 62, 121, 151].
Система функционального диагностирования комбинационного логического устройства организуется с целью оценки его технического состояния на рабочих входных воздействиях. В процессе работы комбинационного устройства возникают одиночные неисправности на выходах внутренних логических элементов, которые могут проявляться в виде искажений вычисляемых устройством функций. Диагноз о техническом состоянии комбинационного устройства ставится на основании оценки правильности вычисления им своих функций [23].
Снабжение логического устройства свойством обнаружения ошибок является действенным способом, так как при наличии сбоев неверно вычисленные данные могут быть заблокированы, что в системах автоматики не приведет к возникновению неправильных результатов вычислений функций управления.
Концепция функционального диагностирования может быть сформулирована следующим образом. Функциональное диагностирование – это способ организации системы обнаружения ошибок в объекте диагностирования, основанный на косвенном контроле результатов вычислений им своих функций в процессе эксплуатации.
Классификация ошибок на рабочих выходах систем функционального диагностирования
Этот пример показывает определяющую роль характеристик обнаружения ошибок (m,k)-кодами на процедуру синтеза системы функционального диагностирования с обнаружением любых одиночных неисправностей в контролируемых устройствах.
Изучая свойства систематического кода по обнаружению ошибок в информационных векторах, можно изучать общие закономерности в обнаружении ошибок в системах функционального контроля без привязки к топологии контролируемого объекта, а также вырабатывать общие рекомендации к построению контролепригодных дискретных сис тем. Одной из первых работ по анализу характеристик кодов Бергера является [33], где отмечена данная связь. Впервые полностью характеристики обнаружения ошибок кодами Бергера изучены автором данного диссертационного исследования в [38, 43]. Наиболее значимые результаты освещены в третьей главе диссертационной работы.
Помимо кодов Бергера широкого распространения при построении систем технического ди агностирования достигли так называемые модульные коды с суммированием (их также назы вают остаточными кодами). Данные коды являются наиболее простой модификацией кодов Бергера и образуются путем вычисления наименьшего неотрицательного вычета веса информа ционного вектора и записью в контрольные векторы двоичных эквивалентов полученных чисел [137, 177]. Наилучшими характеристиками, как отмечается в большом количестве работ, на пример, в [267], обладают коды с установленными модулями К4 где максимальное значение модуля определяется как модуль-степень числа два, ближайший к мо дулю кода Бергера. Данные коды могут быть получены путем «отбрасывания» части старших контрольных разрядов в коде Бергера. Наверное, самыми известными из модульных кодов с суммированием, являются коды Боуза-Лина - коды с модулями М=4 и М=8 [ 177]. Тем не менее, при построении систем функционального контроля могут быть использованы и коды с другими значениями модулей [73, 74, 273].
Вопросы синтеза генераторов модульных кодов с суммированием также изучены в большом количестве работ большого количества авторов, в том числе, таких ученых, как S. J. Piestrak, V. V. Saposhnikov, Vl. V. Saposhnikov. В ряде работ, например, в [106, 132, 267], предложены универсальные структуры синтеза генераторов модульных кодов с суммированием, как счетчиков единиц по заданному модулю М.
Вопросы применения как классических (кодов Бергера), так и модульных кодов с суммированием для организации систем функционального диагностирования логических устройств автоматики и вычислительной техники затронуты в [8, 26, 120, 133, 156, 191, 231, 230, 250, 271]. Исследованиями в данном направлении занимались многие ученые в области компьютерных наук, а именно: M. Goessel, I. Levin, J.-C. Lo, A. Yu. Matrosova, S. Mitra, E. J. McCluskey, M. Nicolaidis, V. V. Saposhnikov, Vl. V. Saposhnikov, E. V. Slabakov, E. S. Sogomonyan, S. Thanawastien, N. A. Touba, Y. Zorian и др.
Классические и модульные коды с суммированием, как отмечается в [39], обладают не оптимальными характеристиками обнаружения ошибок в информационных векторах при своих параметрах длин информационных и контрольных векторов. По этой причине до настоящего времени разрабатываются различные модификации кодов с суммированием, использующие разнообразные операции со значениями разрядов информационных векторов. Некоторые правила по 43 строения модифицированных кодов с суммированием принадлежат таким ученым как M. Blaum, D. Das, H. Dong, N. Touba, V. V. Saposhnikov, Vl. V. Saposhnikov и др. Интересным и важным с точки зрения практических приложений является (т,к)-код, полученный путем подсчета модифицированного веса информационного вектора по формуле [7, 100]: W = r(mod М) + ссМ, (15) где r(modA/j представляет собой наименьший неотрицательный вычет веса информационного вектора по модулю М (в качестве данного модуля может выступать модуль 2 log2 т [100] или меньшее значение степени числа два [85]), - специальный поправочный коэффициент, вычисляемый как сумма по модулю два заранее установленных разрядов информационного вектора.
Впервые подобный алгоритм был опубликован в [7]. В нем «жестко» фиксировались значения Ми :М=2 og2 т+ 1 и а = fm fm-1 ... fm-k+2 fm-h+1 ( – сумма по модулю два т–к разрядов, занимающих старшие позиции в информационном векторе). Эффективность такой модификации была показана авторами на кодах с малой длиной информационного вектора т6. В той же работе предложены некоторые способы синтеза генераторов данных кодов.
Указанная модификация хорошо изучена в [6, 53], в том числе, с участием автора данного диссертационного исследования вариации со значениями Ми были расширены и предложено сначала семейство модифицированных кодов Бергера [100, 258], а затем - модульных модифицированных кодов с суммированием [85]. Синтезу генераторов данных кодов посвящены работы [6, 175]. Некоторые результаты в этой области [40] принадлежат автору данной диссертации.
В [100] получен модифицированный код Бергера, характеристики обнаружения ошибок которым почти вдвое улучшены по сравнению с классическим кодом. Однако, как показано в этой же работе, не был достигнут «предел улучшения», но были сформулированы условия его достижения - критерии оптимума.
Максимально эффективные коды с позиции обнаружения ошибок в информационных векторах могут быть построены путем установления неравноправия между разрядами в информационных векторах приписыванием разрядам, занимающим различные позиции в информационных векторах, различных весовых коэффициентов и последующих операциях с ними [19, 21, 24, 49, 65-68, 82, 86, 105, 108, 111, 115, 134, 200, 260, 286, 294]. Данное решение впервые опубликовано в четвертом разделе той же статьи Джея Бергера [172, 173]. Вопросам же синтеза систем функционального диагностирования с применением взвешенных кодов с суммированием посвящены работы [190, 192]. Характеристики же взвешенных кодов при различных соотношениях весовых коэффициентов разрядов информационных векторов изучены в настоящей работе, в том числе, изучены как модульные, так и модифицированные взвешенные коды с суммированием.
Интересным способом построения кодов является взвешивание не разрядов, а переходов между разрядами, занимающими соседние позиции в информационных векторах [274]. Такой способ построения кодов с суммированием впервые предложен в 1999 году V. V. Saposhnikov и Vl. V. Saposhnikov, а некоторые модификации - рассмотрены в [20, 66, 67, 251] ими и их учениками. В данной работе детально изучены характеристики кодов с суммированием взвешенных переходов с различными последовательностями весовых коэффициентов переходов, в том числе, и модификаций данных кодов.
Следует также отметить, что в технической диагностике часто используются равновесные коды [204]. Вопросы их применения, а также синтеза контрольного оборудования рассмотрены в большом количестве работ, например, в [63, 127, 131, 138, 164, 166, 179, 180, 193, 263]. Известны способы модификации равновесных кодов, а также модификации, связанные с использованием операции конкатенации контрольных векторов различных кодов при образовании новых кодов с заданными свойствами [174, 176, 267, 287]. Такие коды, например, описаны в работах J. M. Borden и J. E. Smith.
Классические и модульные коды с суммированием в системах функционального диагностирования
Как отмечалось ранее (см. главу 2), свойства обнаружения ошибок в информационных векторах (да,)-кодами и правила вычисления значений разрядов их контрольных векторов напрямую определяют ключевые характеристики систем функционального диагностирования комбинационных устройств. Существует два диаметрально противоположных подхода к организации систем функционального диагностирования: использование системы дублирования, в основу которой положен код с повторением, и применение в качестве основы системы функционального диагностирования - кода паритета. В общем случае система дублирования обладает максимальной структурной избыточностью при максимальных значениях характеристик обнаружения ошибок в контролируемых устройствах. Система паритета, наоборот, имеет минимальную структурную избыточность и, соответственно, максимально «слабые» из существующих возможности идентификации неисправностей в контролируемых устройствах. Тем не менее, коды паритета получили широкое распространение в задачах организации надежных дискретных систем. Известны [2] необходимые и достаточные условия синтеза систем функционального диагностирования со 100%-ным обнаружением ошибок в контролируемых устройствах на основе кодов паритета. При организации системы дублирования используется (т,к)-код с длиной контрольного вектора к=т, а при организации системы контроля по паритету - код с длиной контрольного вектора к=1. Существует большое разнообразие (да,)-кодов с длинами контрольных векторов к Є 2;3;...;т — 1, которые могут быть применены в задаче организации системы функционального диагностирования комбинационного устройства. Эти коды обладают различными по сложности вычисления функциями, соответствующими разрядам контрольных векторов (да,)-кодов, а также различными характеристиками обнаружения ошибок в информационных векторах. При этом ключевым свойством (да,)-кода в рассматриваемом вопросе является свойство именно обнаружения (а не исправления!) ошибок. Для обнаружения ошибок в информационных векторах кодов требуется меньшая избыточность самого кода, чем для исправления ошибок.
В данной главе диссертационного исследования приводятся результаты анализа свойств обнаружения ошибок в информационных векторах известными (да,)-кодами. В том числе, приводятся некоторые существенные для теории функционального диагностирования положения. Формулируются алгоритмы модификации (да,)-кодов с заданными значениями длин информационных и контрольных векторов в коды с улучшенными свойствами обнаружения ошибок по различным критериям (например, в коды с минимальным общим количеством ошибок в информационных векторах или в коды с сохранением свойства 100%-ного обнаружения монотонных ошибок и т.д.).
Часто при организации систем функционального диагностирования используют классические коды с суммированием. Их контрольные векторы получаются по следующим правилам.
Определяется сумма единичных разрядов информационного вектора - вес г информаци онного вектора. Число г представляется в двоичном виде и записывается в разряды контрольного вектора. В контрольных векторах таких кодов записываются двоичные числа, равные количеству единичных разрядов в информационных векторах (равные весу г информационного вектора). В таком случае длина контрольного вектора определяется величиной к = log2( + 1) , (3.1) где запись ... обозначает целое сверху от вычисляемого значения.
Классические коды с суммированием впервые описаны в работе Джея Бергера (IBM) [173] и впоследствии получили его имя. Коды Бергера, далее будем обозначать их как S(m,Щ-коды, обладают важной особенностью, на которой базируется множество алгоритмов построения кон-тролепригодных дискретных систем, - ими обнаруживается 100% монотонных ошибок в информационных векторах. Данное свойство часто используется при построении надежных дискретных систем. Известны также модификации кодов, ориентированные на 100%-ное обнаружение монотонных ошибок любой или определенной кратностью [187, 197, 201, 218-220, 229, 253, 256, 262].
Утверждение 3.1. Ошибка в информационном векторе любого (m,k)-кода будет необнару-живаемой тогда, и только тогда, когда будет переводить информационный вектор с одним контрольным вектором в информационный вектор с таким же контрольным вектором.
В S(m,k)-коде всем информационным векторам с одинаковым весом соответствуют одинаковые контрольные векторы. Таким образом, ошибка будет необнаруживаемой, если при ее возникновении не нарушится вес информационного вектора. Это возможно только при одинаковом количестве искажений единичных и нулевых разрядов в информационных векторах. Этой особенностью кодов с суммированием и объясняется отсутствие в классе необнаруживаемых монотонных ошибок в информационных векторах. Более того, справедливо следующее свойство любого S(m,k)-кода.
Утверждение 3.2. Любым S(m,k)-кодом не обнаруживается 100% симметричных ошибок, все остальные виды ошибок ими обнаруживаются.
Свойства систематических кодов удобно анализировать по табличной форме их задания, в которой в столбцах даются распределения информационных векторов между всеми контрольными векторами – распределения информационных векторов на контрольные группы. Для приведенного выше примера S(4,3)-кода такая таблица имеет вид, показанный в табл. 3.2. По данной таблице легко устанавливается справедливость формулировки утверждения 3.2. Симметричная ошибка – это любая ошибка в контрольной группе кода Бергера, а необнаруживаемыми являются только те ошибки, которые происходят при возникновении искажений, переводящих информационные векторы одной контрольной группы друг в друга.
Модифицированные и модульно модифицированные коды с суммированием взвешенных информационных разрядов в системах функционального диагностирования
Ранее рассматривались только коды с суммированием единичных разрядов в информационных векторах. Построение (т,к)-кодов с различными характеристиками обнаружения ошибок в информационных векторах возможно также за счет реализации идеи установления неравноправия между разрядами в информационном векторе путем приписывания им весовых коэффициентов Wj, где / - номер разряда в информационном векторе. Вес информационного вектора определяется путем подсчета суммы весовых коэффициентов единичных разрядов в информационном векторе. Впервые подобная идея была описана в классической работе Джея Бергера [173]. Примеры же применения взвешенных кодов с суммированием в системах технического диагностирования даны в [ 190, 192].
Вычисление значений разрядов контрольных векторов взвешенных кодов с суммированием. 1. Устанавливается последовательность весовых коэффициентов, приписываемых разрядам информационного вектора: [Wj] = [wm; wm–1; …; w2; w1]. 2. Определяется сумма весовых коэффициентов единичных разрядов информационного вектора - вес W информационного вектора: W = wifi. (4.1) /=1 3. Число W представляется в двоичном виде и записывается в разряды контрольного векто ра. Коды с суммированием, получаемые по алгоритму 4.1, будем называть кодами с суммированием взвешенных разрядов информационных векторов и обозначать как WS(m,k)-коды. Свойства Ж?(да,А:)-кодов напрямую зависят от того, какие весовые коэффициенты приписаны тем или иным разрядам информационного вектора. В том числе, значения весовых коэффициентов напрямую определяют количество разрядов в контрольном векторе кода: к = log2 V max + 1)1 = flog 2 + W2 + ...+ т + 1). (4.2) В табл. 4.1 приводятся векторы WS(m ,К)-кода с установленной последовательностью весовых коэффициентов информационного вектора [1; 1; 2; 3], а в табл. 4.2 - распределение информационных векторов данного кода на контрольные группы.
Контрольные группы 000 001 010 011 100 Информационные векторы 101 110 111 0000 0100 1000 0010 1100 0001 0110 1010 0101 1001 1110 0011 1101 0111 1011 1111 Ж5 (4,3)-код с последовательностью весовых коэффициентов [1; 1; 2; 3] имеет к=3 разрядов в контрольных векторах, так как для него Wmax=7. Данный код можно сравнить с классическим (4,3)-кодом. Из табл. 4.2 следует, что у рассматриваемого взвешенного кода информационные
векторы занимают все 2 =2 =8 контрольные группы, но, тем не менее, распределены между ними неравномерно. Ж?(4,3)-код с последовательностью весовых коэффициентов [1; 1; 2; 3] не обнаруживает 20 ошибок в информационных векторах (для сравнения, (4,3)-код не обнаруживает 54 ошибки в информационных векторах), тогда как оптимальный (т,к)-код при указанных длинах информационных и контрольных векторов - 16. Таким образом, коэффициент эффективности для Ж?(4,3)-кода дт = 80%, что, естественно, больше, чем у (4,3)-кода. Однако Ж?(4,3)-код, как и любые WS(m,к)-коды, получаемые по алгоритму 4.1, не являются оптимальными (да,)-кодами.
Утверждение 4.1. WS(m,&)-коды не являются оптимальными вне зависимости от значений весовых коэффициентов разрядов информационных векторов.
Данное положение следует из таких соображений. В контрольных группах с номерами 0 и Wmax при любых значениях весовых коэффициентов разрядов информационных векторов будет всегда находиться только по одному информационному вектору. Единственным вариантом оптимального кода, в таком разе, является размещение в каждой контрольной группе по одному информационному вектору. В соответствии с выражением (4.19) получаем общее количество необнаруживаемых ошибок в таком взвешенном (т,к)-коде: Т = 2І2«-1)=0. Таким образом, дт = 0 %. А описываемый (т,к)-код будет являться кодом с повторением. Все остальные WS(m,к)-коды будут иметь в двух контрольных группах по одному вектору и хотя бы в одной из остальных групп ни одного или более одного информационного вектора.
Отмети также, что рассматриваемый WS(m,k)-код с установленной последовательностью весовых коэффициентов информационного вектора [1; 1; 2; 3] является некоторым «удачным» кодом. Для такого кода значение Wmax 2 —1. (4.3) WS(m,k)-код, удовлетворяющий условию (4.50), будет иметь такое же количество разрядов в контрольных векторах, как и S(m,k)-код. Нарушение условия (4.3) приводит к увеличению количества разрядов в контрольных векторах, и соответственно, к снижению значения коэффициента gm к.
Например, если рассмотреть WS(m,k)-код при т=4 с последовательностью весовых коэффициентов разрядов информационного вектора [1; 1; 2; 4], то можно отметить, что им не обнаруживается только 14 ошибок в информационных векторах, что, однако, больше, чем у кода с повторением. Коэффициент эффективности для данного кода дт = 0 %. Для организации функционального диагностирования комбинационной схемы логичнее использовать структуру дублирования.
Рассмотрим некоторые особенности WS(m,k)-кодов в системах функционального диагностирования.
Наиболее простым классом WS(m,к)-кодов является класс кодов с суммированием единичных и одного взвешенного разрядов информационного вектора. Такие коды, по сути, относятся к «сдвиговым» кодам, получаемых по алгоритму 4.6, а вес взвешенного разряда определяет «диапазон» сдвига: S = W-1, (4.4) где w - это значение весового коэффициента взвешенного разряда в информационном векторе.
Поскольку при рассмотрении всех 2 информационных векторов на величину S сдвигается вправо в таблице распределения информационных векторов на контрольные группы ровно половина информационных векторов, нетрудно найти граничные условия «максимально эффективного сдвига».
Утверждение 4.2. Коды с суммированием единичных и одного взвешенного разрядов информационного вектора имеют минимальное общее количество необнаруживаемых ошибок в информационных векторах среди всего семейства данного класса кодов с одинаковым значением т при выполнении соотношения: w m. (4.5) Справедливость утверждения 4.2 объясняется тем, что информационные векторы с истинным значением веса г заполняют контрольные группы 0rmax, где гmax=т, если значение взвешенного разряда равно 1. В случае, если значение взвешенного разряда м 1, осуществляется «сдвиг» векторов с истинным весом на величину г + S = Г + т — 1. Вектор 00…0 не сдвигается и всегда располагается в контрольной группе, соответствующей весу г=0. Вектор 11… 1 сдвигается в контрольную группу W = 2т —Векторы остальных контрольных групп с Y Є 1;2;...;т —1 последовательно заполняют контрольные группы с весами WE {т;т + 1;...2т-2\.
Для примера на рис. 4.1 показан процесс «сдвига» векторов WS(m,k)-кода при т=4 с последовательностью весовых коэффициентов разрядов информационного вектора [1; 1; 1; 4] по отношению к классическому коду Бергера.
Взвешивание одного информационного разряда весом W т позволяет сдвинуть в пустующие контрольные группы ровно половину информационных векторов (табл. 4.3). Это дает возможность сохранения ключевых свойств классических кодов Бергера для данного класса кодов.