RUS ENG

Исследование представления булевых функций в виде идеалов над булевыми кольцами в задачах символьной верификации

А.Д. Комягин, руководитель - проф Ю.Г. Карпов

 В символьной верификации для представления характеристических функций множеств используются бинарные решающие диаграммы (BDD). Они позволяют компактно и эффективно представлять характеристические функции больших множеств. Однако, существуют функции, представление которых в BDD всегда экспоненциально. Данная работа содержит исследование возможности использования альтернативного представления булевых функций – идеалов над булевыми кольцами – предложенного в статье Q.Tran и M.Vardi. Результаты данной работы показывают, что для некоторых классов задач альтернативное представление позволяет проводить верификацию с линейной сложностью, в то время как с BDD эта сложность экспоненциальна. Также в работе предложен алгоритм декомпозиции отношения переходов в стуктуре Крипке, позволяющий повысить эффективность верификации с использованием идеалов над булевыми кольцами в 5-10 раз.

Комбинаторно-алгебраические методы декодирования кодов исправляющих ошибки

В.Д. Милославская, руководитель - доц. П.В. Трифонов

Рассматриваются методы построения, кодирования, декодирования и анализа корректирующей способности кодов БЧХ и основанных на них каскадных кодов. В частности, рассмотрена задача быстрого мягкого декодирования кодов Рида-Соломона. Предложены усовершенствования метода Кёттера-Варди, направленные на снижение его сложности и повышение корректирующей способности. В работе представлено обобщение двоичного интерполяционного алгоритма на случай корней переменной кратности, обеспечивающее значительное упрощение наиболее трудоемкого шага метода Кёттера-Варди. Кроме того, показано, что его корректирующая способность может быть повышена за счет независимой обработки наименее надежных символов принятой последовательности. Разработан метод построения полярных кодов с ядром БЧХ для двоичного стирающего канала. Разработан быстрый алгортм систематического кодирования двоичных полярных кодов с ядром приводимым в нижнетреугольному виду.Разработаны быстрые алгоритмы мягкого декодирования, а также декодирования с исправлением стираний для двоичных полярных кодов.Получена верхняя граница для вероятности ошибки декодирования полярного кода. Представлены численные результаты, характеризующие эффективность предложенных методов.