Архив статей журнала
Статья продолжает цикл публикаций по разработке и верификации управляющих программ на основе LTL-спецификаций специального вида. Ранее для описания строго детерминированного поведения программ была предложена декларативная LTL-спецификация, проработаны способы её верификации и трансляции: для верификации используется инструмент проверки модели nuXmv, трансляция осуществляется в императивный язык программирования ST для программируемых логических контроллеров. При верификации декларативной LTL-спецификации поведения программ может возникнуть необходимость в моделировании поведения её окружения. В общем случае требуется обеспечить возможность построения замкнутых систем «программа-окружение». В настоящей работе для описания поведения окружения программ логического управления предложена LTL-спецификация ограниченно недетерминированного поведения булевой переменной. Данная спецификация позволяет задавать поведение булевых сигналов обратной связи, а также условия справедливости для исключения нереалистичных сценариев поведения. В статье предлагается подход к разработке и верификации программ логического управления, в рамках которого модель поведения окружения программы описывается в виде ограничений на поведение её входных сигналов, что позволяет избежать отдельного детального представления процессов функционирования окружения. В результате полученная модель поведения замкнутой системы «программа-окружение» даёт ряд преимуществ: упрощение процесса моделирования, сокращение пространства состояний проверяемой модели, снижение времени верификации. При невозможности сведения поведения окружения к поведению имеющихся входных сигналов данный подход предполагает применение «мнимых» датчиков - дополнительных булевых переменных, использующихся как вспомогательное средство для описания поведения входных сигналов. Цель введения мнимых датчиков состоит в компенсации недостающих датчиков для отслеживания специфического поведения отдельных элементов окружения, которое необходимо учесть при задании реалистичного поведения входов программы логического управления. Предложенный подход к разработке и верификации программ с учётом поведения окружения (объекта управления) демонстрируется на примере промышленной установки для литья пластмасс.
Безопасность движения на железнодорожном транспорте требует регулярной проверки состояния рельсов для отслеживания и своевременного устранения возникающих на них дефектов. Вихретоковая дефектоскопия - один из популярных методов проведения неразрушающего контроля рельсов. Данные (дефектограммы), поступающие от вихретоковых дефектоскопов при тестировании рельсов, характеризуются большим объёмом и нуждаются в эффективном автоматическом анализе. Под анализом понимается процесс определения по дефектограммам наличия дефектных участков наряду с выявлением конструктивных элементов рельсового пути с учётом шума и возможных помех разной природы. Для выделения полезных сигналов (от дефектов и конструктивных элементов) находится пороговый уровень шума, значение которого может быть искажено накладывающимися на сигналы электромагнитными помехами, обладающими выраженной низкочастотностью и периодичностью. Указанные помехи завышают пороговый уровень шума, осложняя выявление полезных сигналов. В связи с этим возникает необходимость в подавлении помех описанного типа. В данной работе в качестве метода устранения помех на вихретоковых дефектограммах используется спектральное вычитание. Функция помех определяется как сумма низкочастотных гармоник дискретного преобразования Фурье исходных сигналов. Очищенные от помех сигналы получаются вычитанием гармоник низкочастотного диапазона. Правая граница этого диапазона названа частотой пороговой гармоники. Она находится с помощью минимизации расстояния между автокорреляционной функцией сигналов и ожидаемой автокорреляцией. Предложены два вида ожидаемой автокорреляции: автокорреляция гауссовского шума и эталонная автокорреляция. Оба подхода позволяют определить частоту пороговой гармоники, при которой периодические помехи будут подавляться наилучшим образом. Метод, основанный на автокорреляции гауссовского шума, является в некотором роде универсальным для вихретоковых дефектограмм. Эталонная автокорреляция привязана к конкретным данным и пишущему оборудованию. Для рассматриваемых данных вихретоковых дефектограмм найдена наиболее подходящая частота пороговой гармоники. Описанные подходы к подавлению периодических низкочастотных помех помимо вихретоковой дефектоскопии могут успешно применяться и в других областях.
Статья продолжает цикл трудов по разработке и верификации управляющих программ на основе LTL-спецификаций специального вида. Ранее была предложена декларативная LTL-спецификация, позволяющая описывать поведение управляющих программ и выполнять построение по ней программного кода на императивном языке ST для программируемых логических контроллеров. Данная LTL-спецификация может быть непосредственно верифицирована на предмет соответствия заданным темпоральным свойствам методом проверки модели (model checking) с помощью инструмента символьной верификации nuXmv. При этом не требуется переводить LTL-формулы спецификации в другой формализм - SMV-спецификацию (код на входном языке инструмента nuXmv). Цель настоящей работы состоит в исследовании альтернативных способов представления модели поведения программы, соответствующей декларативной LTL-спецификации, при её верификации в рамках инструментального средства nuXmv. В статье выполняются преобразования декларативной LTL-спецификации в различные SMV-спецификации с сопутствующими изменениями постановки задачи верификации, что приводит к значительному снижению временных затрат при проверке темпоральных свойств с использованием инструмента nuXmv. Ускорение верификации обусловлено сокращением пространства состояний проверяемой модели. Полученные в результате предложенных преобразований SMV-спецификации задают одинаковые или бисимуляционно эквивалентные системы переходов, обеспечивая неизменность результатов верификации при замене одной SMV-спецификации на другую.
Настоящая работа продолжает цикл статей по разработке и верификации управляющих программ на основе LTL“=спецификации. Суть подхода заключается в описании поведения программ с помощью формул линейной темпоральной логики LTL специального вида. Полученная LTL“=спецификация может быть непосредственно верифицирована с помощью инструмента проверки модели. Далее по LTL“=спецификации однозначно строится код программы на императивном языке программирования. Перевод спецификации в программу осуществляется по шаблону. Новизна работы состоит в предложении двух LTL“=спецификаций нового вида - декларативной и императивной, а также в более строгом формальном обосновании данного подхода к разработке и верификации программ. Выполнен переход на более современный инструмент верификации конечных и бесконечных систем - nuXmv. Предлагается описывать поведение управляющих программ в декларативном стиле. Для этого предназначена декларативная LTL“=спецификация, которая задаёт размеченную систему переходов как формальную модель поведения программы. Данный способ описания поведения является достаточно выразительным - доказана теорема о Тьюринг“=полноте декларативной LTL“=спецификации. Далее для построения кода программы на императивном языке декларативная LTL“=спецификация преобразуется в эквивалентную императивную LTL“=спецификацию. Доказана теорема об эквивалентности, которая гарантирует, что обе спецификации задают одно и то же поведение. Императивная LTL“=спецификация транслируется в императивный код программы по представленному шаблону. Декларативная LTL“=спецификация, которая подвергается верификации, и построенная по ней управляющая программа гарантированно задают одно и то же поведение в виде соответствующей системы переходов. Таким образом, при верификации используется модель, адекватная реальному поведению управляющей программы.
Среди полных систем булевых функций особый интерес представляют самодостаточные операторы. Они обладают широкой областью применимости и не ограничиваются двухместным случаем. В данной работе формулируются условия, накладываемые на коэффициенты полинома Жегалкина, необходимые и достаточные для того, чтобы полином соответствовал самодостаточному оператору. Рассмотрено полиномиальное представление булевых функций, сохраняющих константу. Показано, что свойства монотонности и линейности не требуют специального рассмотрения при описании самодостаточного оператора. Вводится понятие полинома двойственного остатка, значение которого позволяет определить самодвойственность булевой функции. Доказано, что сохраняющая 0 и 1 или не сохраняющая ни 0, ни 1 булева функция является самодвойственной тогда и только тогда, когда двойственный остаток соответствующего ей полинома Жегалкина равен 0 для любых наборов значений переменных функции. На основании этого факта получена система ведущих коэффициентов. Решение данной системы позволило сформулировать критерий самодвойственности булевой функции, представленной полиномом Жегалкина, накладывающий необходимые и достаточные условия на коэффициенты полинома. Таким образом, показано, что полиномы Жегалкина являются достаточно удобным инструментом при исследовании предполных классов булевых функций.