автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Автоматизация проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки

На правах рукописи

СОБОЛЕВ Сергей Сергеевич

005010182

АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ СПЕЦИАЛИЗИРОВАННЫХ УСТРОЙСТВ ГЕНЕРАЦИИ ПОЛНЫХ КОМБИНАТОРНЫХ ПЕРЕСТАНОВОК ЭЛЕМЕНТОВ СИМВОЛЬНОЙ СТРОКИ

Специальность 05.13.12 - Системы автоматизации проектирования

АВТОРЕФЕРАТ

диссертации на соисканне ученой степени кандидата технических наук

Научный руководитель д.т.н., проф. В.К. Зольников

1 С ОЕЗ 2012

Воронеж 2012

005010182

Работа выполнена в ФГБОУ ВПО «Воронежская государственная лесотехническая академия»

Научный руководитель:

доктор технических наук, профессор Зольников Владимир Константинович

Официальные оппоненты:

доктор технических наук, профессор Стародубцев Виктор Сергеевич

доктор технический наук Барабанов Юрий Федорович

Ведущая организация:

Федеральное государственное унитарное предприятие «Научно-исследовательский институт электронной техники»

Защита состоится 2 марта 2012 г. в 10:00 на заседании диссертационного совета Д212.034.03 при ФГБОУ ВПО «Воронежская государственная лесотехническая академия» по адресу: 394087, г. Воронеж, ул. Тимирязева, 8, ауд. 14.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО «Воронежская государственная лесотехническая академия»

Автореферат разослан 30 января 2012 г.

Ученый секретарь диссертационного совета:

В.И.Анциферова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

^ Актуальность проблемы. Современное развитие полупроводниковых технологий, характеризующееся повышением сложности электронных устройств, изменением проектных норм, разделением труда проектировщиков и образованием кремниевых фабрик, предопределило изменения в методологии проектирования сверхбольших интегральных схем (СБИС). При наблюдаемом общем росте ресурсоемкости процесса разработки эффективным является применение методологии нисходящего проектирования на основе многоуровневого иерархического представления устройств и перехода в процессе проектирования от общего описания системы к детальному описанию составляющих ее компонентов - сложных функциональных блоков, или IP-блоков (от англ. Intellectual Property).

Наряду с изменениями стандартных методов разработки СБИС, необходимо отметить развитие методологии проектирования в соответствии с классом целевых интегральных схем. Учет специфики конкретного класса СБИС позволяет принять во внимание его особенности уже на ранних этапах проектирования и обеспечить более эффективную адаптацию архитектуры на конкретную задачу по сравнению со стандартными средствами, ориентированными на широкую область применения. Примерами таких классов микросхем являются схемы памяти, схемы программируемой логики (ПЛИС), характеризующиеся регулярной структурой. В настоящее время на мировом рынке существует множество фирм, специализирующихся на проектировании конкретного класса СБИС, например, крупнейшими производителями ПЛИС являются компании Altera и Xilinx.

Одним из специфических классов СБИС являются специализированные устройства генерации полных комбинаторных перестановок символьной строки, используемых главным образом в системах защиты информации ЭВМ. Основными особенностями таких устройств являются переменная разрядность символьной строки и наличие ограничений на требуемое множество генерируемых комбинаторных перестановок в некоторых приложениях. Например, в системах динамического преобразования форматов на основе транспозиционных преобразований, некоторые из перестановок являются недопустимыми и могут быть непригодными для формирования использующихся в этих системах дескрипторов формата, а значит, должны быть исключены из рассмотрения. В этом прослеживается аналогия со слабыми ключами в современных шифрах, например, DES. В рассматриваемом случае, перестановка является недопустимой, если она содержит одну или несколько неподвижных точек и/или инволюций.

Применение стандартных средств проектирования при разработке рассматриваемых специализированных СБИС связано с рядом проблем. Современная методология проектирования предполагает разбиение маршрута проектирования на несколько этапов проектных процедур. Первые два этапа составляют проектирование на системном уровне и на уровне регистровых передач (RTL-уровень). На верхнем структурном уровне, называемом также системным, разрабатывается и верифицируется обобщенная модель блока для проверки работоспособности взятого за основу математического алгоритма генерации перестановок. В качестве языка описания чаще всего используется язык SystemC. На RTL-уровне разрабатывается функциональное описание блока на уровне регистровых передач с использованием одного из языков описания аппаратуры (HDL-языков). Такое описание осуществляется чаще всего вручную, путем графического или текстового ввода, что, во-первых, увеличивает трудоемкость и требует недопустимо больших затрат времени, а во-вторых, влечет за собой разрыв между алгоритмическим описани-

ем на Бу^етС и ЯТЫшисанием. Аналогичный разрыв наблюдается и при разработке тестов для верификации блоков на системном и ЯТЬ уровнях.

Обозначенные проблемы, а также многообразие входных параметров генерации комбинаторных перестановок и увеличение сложности схемы блока генерации с ростом длины символьной строки, повышают риск субъективных ошибок и, таким образом, увеличивают влияние «человеческого фактора» на качество всего проекта. В результате, использование традиционной методологии в процессе проектирования рассматриваемых устройств представляется затруднительным. В этой связи, актуальной задачей представляется разработка средств автоматизации проектирования специализированных устройств генерации комбинаторных перестановок элементов символьной строки, обеспечивающих высокое качество целевых устройств и позволяющих максимально автоматизировать процесс проектирования и верификации на системном и 1ПЪ-уровнях.

Диссертационная работа выполнена в рамках госбюджетной НИР кафедры вычислительной техники и информационных систем ВГЛТА «Автоматизация проектных работ при создании изделий микроэлектроники и лесного комплекса», ГР №01.2.00609244, код ГРНТИ 68.47.01; 50.49.

Объектом исследования является средства автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, предназначенных для обеспечения конфиденциальности данных в рамках СУБД.

Предметом исследования являются модели, алгоритмы и методы проектирования и моделирования в САПР устройств генерации полных комбинаторных перестановок с отсевом недопустимых перестановок, содержащих неподвижные точки и обратимые пары.

Целью исследования является разработка средств проектирования: методики, моделей, методов и алгоритмов для специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки.

В соответствии с поставленной целью в диссертационной работе необходимо решить следующие задачи:

• провести анализ современного состояния средств автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, выделить направления их текущего развития;

• разработать методику проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки, позволяющую обеспечить наиболее эффективное проектирование устройств генерации полных комбинаторных перестановок;

• разработать модели, алгоритмы и методы, позволяющие учесть особенности проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки переменной разрядности с возможностью отсеивания недопустимых перестановок, которые могут снизить качество проекта;

• разработать алгоритмическую основу синтеза тестовой последовательности, учитывающей особенности проектирования устройств генерации полных комбинаторных перестановок на системном уровне и уровне регистровых передач (ЯТЬ);

• разработать программное обеспечение подсистемы генерации функциональных блоков для формирования множества полных комбинаторных перестановок элементов символьных строк, верификации и синтеза тестовой последовательности, внедрить разработанные средства в единую среду сквозного проектирования дизайн-центра.

Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы элементы теории автоматизированного

проектирования, множеств, дискретной математики, методы и средства структурнофункционального моделирования, технологии объектно-ориентированного и событийно-ориентированного программирования, а также метапрограммирования.

Научная новизна результатов, полученных при решении вышеперечисленных задач исследования, состоит в следующем:

• методика проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки, отличающаяся встроенными средства проектирования специальных микросхем, что позволяет обеспечить более высокое качество и сокращение цикла проектирования устройств генерации полных комбинаторных перестановок;

• метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности, отличающийся наиболее полной автоматизацией процесса проектирования на системном уровне и уровне регистровых передач;

• метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности, отличающийся возможностью отсеивания неподвижных точек и инволюций в процессе реализации, что позволяет исключать недопустимые перестановки на этапе комбинаторной генерации множества возможных перестановок;

• алгоритм генерации функциональных блоков для формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности, отличающийся использованием в нем предложенных методов аппаратной генерации перестановок с отсеиванием неподвижных точек и инволюций и генерации соответствующих функциональных блоков;

• алгоритм синтеза тестов для верификации функциональных блоков на системном уровне и уровне регистровых передач, отличающийся учетом особенностей проектирования устройств генерации полных комбинаторных перестановок.

Практическая значимость и результаты внедрения. Практическая значимость работы заключается в улучшении качества проектных работ и сокращении жизненного цикла проектирования специализированных устройств генерации полных комбинаторных перестановок за счет внедрения аппаратно-программных средств.

На основе предложенных методов, математических моделей и алгоритмов разработано программное обеспечение. Оно внедрено в ЗАО НПП «Реляционные экспертные системы» (г. Воронеж) с экономическим эффектом 405 тыс. рублей и в учебный процесс ФГБОУ ВПО «Воронежская государственная лесотехническая академия» (в учебно-методические материалы дисциплин «Системы автоматизации проектирования», «Схемотехническое и функциональное проектирование электронной компонентной базы в САПР», «Методы проектирования микроэлектронных устройств» для подготовки студентов ВГЛТА по направлению «Информационные системы и технологии», а также аспирантов и докторантов по специальности 05.13.12 - Системы автоматизации проектирования).

Полученные средства позволяют снизить трудоемкость, сократить время разработки и минимизировать риск субъективных ошибок при проектировании специализированных устройств генерации комбинаторных перестановок элементов символьной строки.

Выносятся на защиту:

- методика проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки;

- метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности;

- метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности;

- алгоритм генерации функциональных блоков для формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности;

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

Соответствие паспорту специальности. Согласно паспорту специальности 05.13.12 - Системы автоматизации проектирования, задачи, рассмотренные в диссертации, соответствуют областям исследований, соответствующим пунктам:

1. методология автоматизированного проектирования в технике, включающая постановку, формализацию и типизацию проектных процедур и процессов проектирования, вопросы выбора методов и средств для применения в САПР;

3. разработка научных основ построения средств САПР, разработка и исследование моделей, алгоритмов и методов для синтеза и анализа проектных решений, включая конструкторские и технологические решения в САПР и АСТПП.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Международной научной конференции «Проблемы управления, передачи и обработки информации» (Саратов, 2009), Международной научнопрактической конференции «Молодежь и наука: реальность и будущее» (Невинно-мыск, 2010), Всероссийской конференции с элементами научной школы для молодежи «Математическое моделирование в технике и технологии» (Воронеж, 2011), Международной научно-практической конференции «Современные проблемы гуманитарных и естественных наук» (2011).

Публикации результатов работы. По теме диссертации опубликовано 17 работ, в том числе 6 статей в изданиях Перечня, определенного ВАК Минобрнауки России, 1 монография, получено 1 свидетельство об официальной регистрации программ для ЭВМ.

Личное участие заключается в определении цели и задач работы [1-3, 12-13], в выполнении научно-технических исследований [9-10], разработке и анализе моделей [4, 5,14, 16, 18], разработке алгоритмов [9-11], разработке методики проектирования [6, 7,

15, 17], программной реализации [8].

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, изложенных на 116 страницах, включающих в себя список литературы из 104 наименований, 23 рисунка и 12 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы исследования, определены цели и задачи работы, методы решения поставленных задач, отмечены основные результаты исследования, выносимые на защиту; определена их научная новизна и практическая значимость; приведены сведения об апробации и внедрении результатов работы.

В первой главе проведен анализ современного состояния средств автоматизированного проектирования устройств генерации комбинаторных перестановок элементов символьной строки, выделены направления и проблемы их текущего развития, обозначены сферы практического применения и исследованы особенности этих устройств.

Проведен анализ устройств генерации полных комбинаторных перестановок элементов символьной строки. Исследована их область применения, которая показала

достаточно широкий спектр использования в следующих приложениях: в устройствах аппаратной поддержки технологий систем автоматизированного проектирования радиоэлектронной аппаратуры; в системах защиты информации, где применяются различные шифры на основе перестановок; в системах аппаратного обеспечения динамического преобразования форматов данных в реляционных СУБД.

Определены особенности устройств генерации полных комбинаторных перестановок элементов символьной строки и методы проектирования. Показано, что за счет их особенностей средства проектирования могут быть дополнены специальными средствами, которые значительно сократят время проектирования. Кроме того за счет увеличения автоматизации процесса проектирования будет обеспечена бездефектность процесса проектирования.

На основании проведенного анализа и обозначенных проблем сформулированы цели и определены задачи диссертационного исследования.

Во второй главе предложена методика проектирования специализированных устройств генерации полных комбинаторных перестановок, метод генерации функциональных блоков для рассматриваемых устройств, а также приводятся алгоритмы генерации перестановок с отсевом перестановок, содержащих неподвижные точки и/или инволюции, и соответствующего набора верификационных тестов.

Специфика устройств генерации полных комбинаторных перестановок элементов символьной строки с отсевом недопустимых перестановок связана с их следующими особенностями:

1. Длина символьной строки, а также разрядность одного элемента символьной строки, для которой производится генерация комбинаторных перестановок, является переменной величиной.

2. Максимально допустимое количество неподвижных точек и/или инволюций является переменной величиной.

Учитывая данную специфику, в рамках проектирования на системном уровне предложено:

• в качества языка описания поведенческой модели использовать 8уз1егпС - язык проектирования и верификации моделей системного уровня;

• генерировать данную поведенческую модель с помощью программного модуля, реализованного на высокоуровневом языке С++, на основе следующих входных параметров:

а) с1 — разрядность одного элемента символьной строки, для которой производится генерация комбинаторных перестановок;

б) п - длина данной символьной строки, или мощность множества, для которого формируются перестановки;

в) Мтах - количество неподвижных точек в каждой из сгенерированных перестановок, достаточное для ее отсеивания;

г) Ктах ~ количество инволюций в каждой из сгенерированных перестановок, достаточное для ее отсеивания;

• генерировать тесты для верификации поведенческой модели также с помощью с помощью программного модуля на С++ с тем же множеством входных параметров.

8у51етС представляет собой надстройку стандартного языка программирования С++, реализованную в виде отдельных библиотек специальных классов. Данные библиотеки содержат в себе конструкции, позволяющие создавать эффективные и точные модели программных алгоритмов, аппаратных архитектур, интерфейсов и схем на системном уровне.

На этапе разработки функционального описания блока на уровне регистровых передач (ЯТЬ) создается синтезируемая ЯТЬ-модель блока на одном из языков описания аппаратуры. В рамках проектирования рассматриваемых устройств генерации перестановок в качестве такого языка предложен язык УНОЬ. Данный этап выполняется в автоматическом режиме, предполагающем генерацию УНОЬ-кода с помощью программного модуля на языке С++. Тесты для верификации на ЯТЬ-уровне генерируются также с помощью програсммного модуля на языке С++. Учитывая специфику блока генерации полных комбинаторных перестановок элементов символьной строки, оба модуля принимают на вход то же множество входных параметров, что и для автоматизированного формирования 8уз1ешС модели и тестов на системном уровне (л, (I, /Утах,

^тах)•

Общий маршрут проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки при использовании предложенной методики проектирования изображен на рис. 1 (элементы, отличающиеся новизной, отмечены серой заливкой).

Генерация описания модели на 5у51етС

С-н-

||

а |

Генерация тестов для

поведенческой С++ —*

модели

*

о

X

2

Генерация описания ЯТЬ-модели на УГОЬ Ой-

Генерация тестов для ИТЬ-модели бн-

Статический временной анализ

Создание поведенческой модели Бу^етС

Системная верификация вувеетС

Создание КТЬ-модели УНОЬ

Моделирование и верификация ЯТЬ-модели УНМ,

■ •

Логический синтез

>

Логическое моделирование и верификация

Физический синтез и верификация топологий

С=э Библиотека

8у$1етС

С=>

Рис. 1. Маршрут проектирования устройств генерации полных комбинаторных, перестановок элементов символьной строки

Преимущество предложенной методики состоит в автоматизации процесса аппаратного описания, создания тестов и верификации на системном и ЯТЬ уровнях. Это позволяет существенно сократить цикл проектирования рассматриваемых специализированных устройств за счет исключения процесса ручного описания, традиционного

для стандартных средств проектирования. Кроме того, данная методика позволяет минимизировать общее количество проектных ошибок и, как следствие, обеспечивает более высокое качество специализированных устройств генерации перестановок.

Предложенный метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности заключается в следующем. Для обеспечения гибкости системной и ЯТЬ-моделей генератора перестановок используется множество входных параметров, позволяющих по требованию модифицировать основные характеристики устройства. На основе этих параметров генерируются программные 1Р-блоки на ЗуБ^тС и \ZHDL, отвечающие всем входным аргументам.

Генерация функциональных блоков может происходить в двух режимах (общая схема представлена на рис. 2).

Множество входных параметров системной модели

Режим /

lz

Чтение входных данных

Генерация кода SystemC

Генерация кода VHDL

Режим U I

Набор процедур

source_gen(d: 3; п: 8; sync: 1);

Лексический анализ

Синтаксический анализ

Генерация кода 5у$1етС

Генерация кода УНОЬ

<г

25

Функциональные блоки для устройств генерации перестановок

Программные блоки на SystemC (системная модель)

Программные блоки на VHDL _________(RTL-модель)_________

Рис. 2. Схема генерации функциональных блоков для устройств формирования множества комбинаторных перестановок.

При использовании первого режима, блоки на SystemC и VHDL генерируются напрямую с использованием входных параметров блока генерации: d,n, Nmax,Rmax.

Второй режим позволяет тонко конфигурировать модели и обеспечивает возможность трансформации системы с минимальной затратой ресурсов. Режим предусматривает процесс генерации блоков в несколько этапов. Первый этап — это формирование набора процедур, каждая из которых может принимать в качестве входных аргументов один или несколько вышеприведенных параметров, а также ряд других опциональных параметров (например, тактируемость блока, наличие порта асинхронного сброса RESET). Каждая процедура позволяет настраивать отдельные части моделей и регулировать взаимодействия между ними.

Второй этап заключается в синтаксическом разборе списка процедур и генерации кода конечных моделей на SystemC и VDHL. Эти действия осуществляет программный модуль на языке C++. Программный модуль включает в себя:

• лексический и синтаксический анализатор;

• шаблоны модулей, сигналов 5у51етС, необходимые для описания поведенческой модели генерации перестановок; шаблоны объектов, сигналов УЬГОЬ, необходимые для описания ЛТЬ-модели генерации перестановок;

• генератор кода 8у51етС/УНОЬ с использованием этих шаблонов.

Общая схема предложенного алгоритма генерации комбинаторных перестановок с возможностью отсева недопустимых перестановок для длины символьной строки п = 3 представлена на рис. 3.

Полезная длина строки к = 1

Полезная длина строки к = 2

Циклических сдвигов: 1, перестановок: 2

Фильтрация перестановок, содержащих количество неподвижных точек, превышающих максимально допустимое )

Ж

Фильтрация перестановок, содержащих количество инволюций, превышающих максимально допустимое )

о ~ -*г

Результирующее множество перестановок

Рис. 3. Схема алгоритма генерации перестановок для п = 3.

Заметим, что рассматриваемый алгоритм представляет собой комбинацию следующих последовательно применяемых элементарных операций: добавление нового символа в строку (увеличение полезной длины строки) и циклический сдвиг строки. Подобная структура делает данный алгоритм очень удобным для аппаратной реализации на основе регистров циклического сдвига.

В качестве множества упорядоченных элементов X, на основе которого осуществляется генерация, берется исходная строку Б длины п, заполненная уникальными символами, т.е.

п

*=и$. (1)

1=1

где - символ, находящийся на /'-ой позиции в строке 5, причем V/, у I =£ ] ^ 5у.

Множество всех перестановок обозначим Р:

-и

(2)

| Pi-

i=1

Неподвижной точкой перестановки p является неподвижная точка отображения р:Х -* X, т.е. элемент множества N(p) = {дг 6 X: р(х) = л:}.

Инволюцией перестановки р является такая пара элементов (х,у) 6 X X X, что выполняются условия:

р(х) = у,р(у) = х,х Ф у. (3)

Предложим следующее разбиение множества Р на (n -I-1) подмножеств:

п

(4)

-и*

где Р; = {р е Р: |Л/(л')| = £}•

Две перестановки входят в одно подмножество только в том случае, если количество неподвижных точек у них одинаково. Введем для фиксированного п набор функций, возвращающих количество перестановок из множества Р с определенным числом неподвижных точек и с числом неподвижных точек, не меньшим определенного числа:

/„■40 = 1*1.1 = м.

п я

(5)

/ЛО = £|Р,| = ]Г/,Г(/).і = о.п.

]=1 ]=1

Общее количество перестановок с I неподвижными точками на множестве мощности п вычисляется по следующей формуле:

/ЛО = С‘-!(п-6.« = 0Я (6)

Формула для общего количества перестановок с числом неподвижных точек, не меньшим I, на множестве мощности п выглядит следующим образом:

П

V)

/=*

где ! к - это субфакториал числа к, или количество перестановок порядка к без неподвижных точек.

Значения функций /„2(0 возрастают экспоненциально с ростом п. При больших п процентная доля перестановок с числом неподвижных точек, не меньшим I, становится постоянной величиной. При Ытах = 0 (в случае фильтрации перестановок, содержащих хотя бы одну неподвижную точку) относительное количество отсеиваемых перестановок (составляющих множество Рнед0п) составляет:

| Рт

■= Urn ~ 0,632. (g)

П-»со \ ПІ/

\р\

В третьей главе предложен метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности, описываются архитектурные модели (системная и ІІТЬ-модель) соответствующих устройств.

Общая структура подсистемы генерации полных комбинаторных перестановок представлена на рис. 4. Она включает в себя несколько блоков, каждый из которых имеет свою функциональность.

Формирователь Формирователь

исходной > очередной

символьной уникальной

строки перестановки

Блок подсчета количества неподвижных точек

Блок подсчета количества инволюции

фильтрации Блок

недопустимых приема

перестановок перестановок

Блок проверки корректности перестановки

Рис. 4. Общая структура СлОка генерации полных комбинаторных перестановок с отсевом недопустимых перестановок

Задача формирователя исходной символьной строки — сформировать символьную строку 50 фиксированной длины п, множество элементов которой представляет собой упорядоченный набор целых чисел от 0 до п — 1. Таким образом, элементами исходной символьной строки 50 являются элементы множества

Х0 = { Г; е Ъ. XI = £, I = 0, п - 1}, (9)

где п - наперед заданное количество элементов.

Формирователь очередной уникальной перестановки принимает на вход сформированную предыдущим блоком символьную строку Яд и на её основе формирует выходную символьную строку $1, элементы которой образуют уникальную перестановку р£.

Задачей следующих четырех блоков является подсчитать количество неподвижных точек и инволюций в очередной сформированной перестановке, проверить корректность текущей перестановки и отсеять недопустимые перестановки (которые либо сформированы некорректно, либо содержат количество неподвижных точек или инволюций, превышающее наперед заданное критическое значение Л/тахили /?тах соответственно). В случае успешной проверки перестановки, она передается на вход блока приема перестановок, формирующего результирующее множество сгенерированных перестановок.

Для моделирования и верификации на системном уровне использовался язык Був-1етС. Каждому блоку на рис. 4 соответствует отдельный модуль (или класс, в терминах объектно-ориентированного программирования) в системной модели 8уз1етС.

Модуль формирования очередной уникальной перестановки включает в себя п — 1 модулей циклического сдвига ап — 1 вспомогательных модулей управления. Модули циклического сдвига соединены последовательно и имеют уровень от 2 до п в соответствии с увеличением полезной длины символьной строки согласно алгоритму на основе циклического сдвига.

Каждый модуль циклического сдвига обладает портами управления Ь и & При высоком логическом уровне сигнала на входе £ значения элементов символьной строки считываются с входных портов и тут же передаются на выходные порты (либо на следующий уровень т + 1, либо в качестве результирующей перестановки), без циклического сдвига. При высоком логическом уровне сигнала на входе -V, происходит циклический сдвиг строки, хранящейся во внутреннем массиве модуля, и её передача на выходные порты. Значения сигналов на портах Ь и 5 вычисляются согласно значениям функций £ = Цс. т, п) и 5 = Б(с,т,п), где т — уровень модуля, а с — внутренний

счетчик вспомогательного модуля управления, увеличивающийся с каждым тактовым импульсом-

Разработка ЯТЪ-описания блока генерации комбинаторных перестановок осуществлялась с применением языка описания аппаратуры УНЭЬ. Базовым элементом любого проекта на УЬГОЬ является объект. Блок генерации перестановок представляет собой совокупность моделируемых объектов УКШЦ каждый из которых соответствует отдельному блоку на общей схеме, изображенной на рис. 4.

Соединяющие объекты сигналы могут быть единичными или множественными (векторами). Каждый передаваемый элемент перестановки моделируется на ШЪ-уровне в виде -разрядного вектора, а вся перестановка - в виде (п • ^-разрядного вектора.

Формирователь исходной символьной строки представляет собой (п • <!)-разрядный регистр с параллельным вводом и выводом. Регистр хранит в себе элементы исходного упорядоченного множества Хо, на основе которого осуществляется генерация перестановок. Каждый регистр представляет собой отдельный объект УНОЬ.

Формирователь очередной уникальной перестановки представляет собой набор регистров циклического сдвига с параллельным вводом и выводом, работа которых координируется вспомогательными объектами управления. Всего объект формирования уникальной перестановки содержит й • (п — 1) регистров (п — 1 групп по d регистров) сдвига и п - 1 вспомогательных объектов управления. Ширина регистров в каждой группе ступенчато увеличивается от 2 до п бит с шагом 1 в соответствии с увеличением полезной длины символьной строки согласно алгоритму на основе циклического сдвига. Каждый вспомогательный объект управления координирует работу своей группы из (I регистров с помощью сигналов управления, поступающих на входные управляющие порты регистров.

Для управления элементами перестановки, всякий регистр, помимо информационных портов, также обладает и двумя входными портами управления Ь и 5. В соответствии со значениями сигналов на портах £ и 5, регистр либо зачитывает соответствующие биты элементов перестановки с входных информационных портов, либо осуществляет циклический сдвиг на 1 бит.

Вспомогательный объект управления включает в себя два счетчика: счетчик по модулю М-1 и счетчик по модулю М2. Счетчики устроены таким образом, что каждый из них по достижении своего максимального значения подает на выход высокий уровень сигнала, в противном случае - низкий уровень. Внутреннее состояние счетчика увеличивается при подаче очередного тактирующего импульса на входной порт тактирующего сигнала и сбрасывается по достижении максимального значения. Согласно значениям сигналов на выходе обоих счетчиков рассчитываются уровни управляющих сигналов £ и Б. Значения М1 и М2 вычисляются по формулам:

п А. 1=п

"'‘О1' ипП<'<”' (П>

и=(+1

где I - разрядность соответствующего управляемого регистра.

В четвертой главе рассматриваются вопросы, связанные с практической реализацией предложенной подсистемы автоматизации проектирования устройств генерации полных комбинаторных перестановок.

Для автоматизации проектирования семейства генераторов полных комбинаторных перестановок разработан комплекс проблемно-ориентированного программного обеспечения, внедренный в общий маршрут проектирования данных устройств. Общая структура комплекса изображена на рис. 5.

Рис. 5. Структура программного комплекса автоматизации проектирования семейства генераторов полных комбинаторных перестановок.

В рамках данного программного комплекса реализованы модели, методы и алгоритмы для формирования множества комбинаторных перестановок элементов символьной строки с возможностью отсева недопустимых перестановок, содержащих неподвижные точки и/или инволюции. Программное обеспечение включает в себя набор инструментальных средств для решения задачи автоматизации проектирования целевых устройств генерации перестановок на системном (поведенческом) уровне и уровне регистровых передач (RTL-уровне).

Для ввода требуемых параметров для блоков генерации комбинаторных перестановок, используется программный модуль интерфейса пользователя, пример которого изображен на рис. 6.

Модули генерации функциональных блоков и соответствующих тестов реализованы на языке высокого уровня C++. Результатом их работы являются программные IP-блоки (soft IP cores) системного уровня моделирования в виде классов (модулей) Sys-temC, программные IP-блоки RTL-уровня моделирования в виде объектов VHDL, тесты окружения для обоих типов блоков, упаковщики IP-блоков для облегчения процесса их интеграции в проект. Программный модуль подсистемы верификации предоставляет возможность автоматической верификации IP-блоков посредством итерационного процесса прохождения тестов. Модуль реализован на языке высокого уровня C++.

Настройка выходных ІР-блоков Имя проекта:

Выходная директория:

кк> 2010'Рго)ес&'.Іе5ІЗ_аиг’' і обз Іуї 5у$1етС: генерировать бломі и тестовое окружение Ш УМХ: генерировать блоки н тестовое окружение

Параметры генерации перестановок Длина символьной строки п: 8 »

разрядность элемента символьной строки 6 (в битах):

ЩІ Добавить блок проверки количества неподвижных точек Максимальное количество И_тах: 0 '

у : Добавить блок проверки количества инеолюачй Максимальное количество й_шах; <? .

О Добавить блок проверки корректности перестановки

Условная схема результирующих блоков

\ Запуск і | Отмена |

Рис. 6. Интерфейс пользователя для ввода параметров генерации 1Р-блокое.

Результирующие 1Р-блоки предназначены для использования в маршруте проектирования специализированных устройств генерации комбинаторных перестановок элементов символьной строки, применяемых в устройствах аппаратной поддержки технологий систем автоматизированного проектирования радиоэлектронной аппаратуры, в системах защиты информации, а также в системах аппаратного обеспечения динамического преобразования форматов данных в ЭВМ. Генерация полных комбинаторных перестановок производится в символьной строке переменной длины я, таким образом, целевые устройства образуют семейство аппаратных генераторов перестановок с дополнительной возможностью отсеивания неподвижных точек и инволюций.

Для оценки эффективности разработанных средств, определена сложность логической схемы каждого из семейства аппаратных генераторов перестановок путем подсчета общего количества логических вентилей и строк УНОЬ-кода для соответствующих устройств. В соответствии с полученными результатами произведена оценка временных затрат проектирования с учетом средней скорости разработки 100 вентилей в день (эта оценка является стандартной и неизменной на протяжении последних пяти лет). Результаты представлены в таблице 1.

Таблица 1

Сложность логических схем устройств генерации комбинаторных перестановок и оценка временных затрат проектирования

Длина символьной строки п

п = 16 п = 24 п = 32

Количество логических вентилей 3200 7400 13300

Количество строк УШЭЬ-кода 1120 2180 3780

Временные затраты, в человеко-днях (стандартная методика) 32 74 133

Временные затраты, в человеко-днях (предложенная методика) 1 1 1

Автоматизация процессов аппаратного описания и верификации на системном и RTL уровнях позволяет существенно сократить цикл проектирования за счет исключения процесса ручного описания на одном из HDL-языков. Как отражено в таблице 1, этот процесс обладает значительной трудоемкостью, возрастающей в квадратичной зависимости с увеличением длины строки п.

Кроме того, использование разработанных средств повышают эффективность проектирования за счет минимизации общего количества проектных ошибок и обеспечения бездефектности специализированных устройств генерации перестановок.

Разработка модулей программного обеспечения, реализующих предложенные модели, методы и алгоритмы для автоматизации проектирования семейства генераторов, осуществлена с использованием языка программирования C++ в среде Visual Studio

2010. Для симуляции моделей на SystemC использовались библиотеки SystemC версии 2.2.0. Разработка RTL-моделей на языке VHDL и их симуляция осуществлялась в среде ModelSimSE 6.5b, логический синтез проводился с помощью программного комплекса Synplicity Synplify Pro.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведен анализ современного состояния средств автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, определены направления их текущего развития.

2. Разработана методика проектирования специализированных устройств, решающих задачу генерации полных комбинаторных перестановок с функцией фильтрации недопустимых перестановок.

3. Разработаны и исследованы модели, алгоритмы и методы, позволяющие учесть особенности проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки переменной разрядности с возможностью отсеивания недопустимых перестановок.

4. Разработаны алгоритмы синтеза тестовой последовательности, учитывающие особенности проектирования устройств генерации комбинаторных перестановок.

5. Разработаны программные средства, реализующие подсистему автоматической генерации функциональных блоков дня формирования множества полных комбинаторных перестановок на системном и RTL уровнях проектирования.

6. Разработаны программные средства, реализующие автоматическую генерацию тестов для функциональных блоков генерации комбинаторных перестановок.

7. Разработаны программные средства подсистемы верификации, предоставляющие возможность автоматизировать процесс верификации функциональных блоков генерации полных комбинаторных перестановок.

8. Подсчитаны трудоемкость и временные затраты проектирования каждого из семейства устройств генерации комбинаторных перестановок и произведена оценка эффективности разработанных средств автоматизации проектирования данных устройств.

9. Разработанные программные средства внедрены в единую среду сквозного проектирования специализированных устройств генерации перестановок в рамках дизайн-центра (ЗАО НПП «Реляционные экспертные системы», г. Воронеж) с полученным экономическим эффектом в размере 405 тыс. рублей и в учебный процесс Воронежской государственной лесотехнической академии.

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях Перечня, определенного ВАК Минобрнауки России

1. Соболев, С.С. Динамическое форматирование структурных объектов хранилищ данных [Текст] / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. - 2008. - №4. - С. 28-33.

2. Сотов, Л.С. Кросс-кластерная коммутационная матрица для аппаратной поддержки управляемой перестановки данных в криптографических системах [Текст] / Л.С. Сотов, С.С. Соболев, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. — 2009. —№4. - С. 56-63.

3. Соболев, С.С. Модели устройств кросс-кластерных перестановок данных в ЭВМ [Текст] / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Вестник компьютерных и информационных технологий. - 2009. - №12. - С.51-55.

4. Соболев, С.С. Алгоритм работы и модель функционального генератора перестановок [Текст] / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Информационные технологии. -2010,-№4.-С. 41-46.

5. Соболев, С.С. Модель генератора перестановок на основе управляемого циклического сдвига [Текст] / С.С. Соболев, В.К. Зольников // Гетеромагнитная микроэлектроника : сб. науч. тр. / под ред. проф. А. В. Ляшенко. - Саратов : Изд-во Сарат. ун-та,

2011. - Вып. И : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. - С. 44-57.

6. Соболев, С.С. Автоматизация проектирования устройств генерации комбинаторных перестановок / С.С. Соболев, В.К. Зольников // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета (Научный журнал КубГАУ). - Краснодар: КубГАУ, 2012. (принята к публикации и включена во второй номер журнала 2012 года).

Монографии

7. Зольников, В.К Автоматизация проектирования специализированных устройств генерации полных комбинаторных элементов символьной строк [Текст] /

В.К.Зольников, С.С.Соболев. - Воронеж: ВГЛТА, 2011. - 124 с.

Патенты и регистрация программ

8. Программа моделирования комбинаторных преобразований форматов представления данных в ЭВМ (D_MATRIX). Свидетельство об официальной регистрации программ для ЭВМ / Л.С. Сотов, С.С. Соболев, В.Н. Харин. - № 2010612449 от 07.04.2010.

Депонированные рукописи

9. Соболев, С. С. Локализация неподвижных точек при комбинаторной генерации перестановок с применением циклического сдвига [Текст] / С. С. Соболев, В. Н. Харин, Л. С. Сотов; Федеральное агентство по образованию, ГОУ ВПО «Воронежская государственная лесотехническая академия». - Воронеж, 2010. - 8 с. : ил. - Библиогр.: с. 8. - Рус. - Деп. в ВИНИТИ РАН 02.08.2010 №479-В2010.

10. Соболев, С. С. Алгоритм генерации полных комбинаторных перестановок с применением циклического сдвига [Текст] / С. С. Соболев, В. Н. Харин, Л. С. Сотов; Федеральное агентство по образованию, ГОУ ВПО «Воронежская государственная лесотехническая академия». — Воронеж, 2010. — 6с.: ил. — Библиогр.: с. 6. — Рус. — Деп. в ВИНИТИ РАН 02.08.2010 №480-В2010.

11. Соболев, С. С. Локализация обратимых пар при комбинаторной генерации перестановок с применением циклического сдвига [Текст] / С. С. Соболев, В. Н. Ха-рин, Л. С. Сотов; Федеральное агентство по образованию, ГОУ В ПО «Воронежская государственная лесотехническая академия». - Воронеж, 2010. - 9 с.: ил. - Библиогр.: с. 9. - Рус. - Деп. в ВИНИТИ РАН 02.08.2010 №481-В2010.

Статьи и материалы конференций

12. Соболев, С.С. Динамическое форматирование данных в распределенных ин-формационно-управляющих системах [Текст] / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Материалы Международной научной конференции «Проблемы управления, передачи и обработки информации» (АТМ-ТКИ-50) СГТУ 16-18 сентября 2009 г. - 2 с.

13. Sobolew, S.S. Anwendung der Datenlagertechnologien fur die Sammlung and Analyse des Datenverkehrs von Korporationsnetzen [Текст] / S.S. Sobolew // Молодежь и наука: реальность и будущее: Материалы III Международной научно-практической конференции: в 6 томах. - Невинномыск: НИУЭП, 2010. - Том V. Естественные и прикладные науки. - С. 413-414. - Яз. нем.

14. Соболев, С.С. Устройство функционального генератора перестановок [Текст]

/ С.С. Соболев, Л.С. Сотов, В.Н. Харин // Моделирование систем и процессов - 2011

- №1-2.-С. 59-64. ' '

15. Соболев, С.С. Методология проектирования специализированных устройств

генерации перестановок [Текст] / С.С. Соболев // Моделирование систем и процессов -2011,-№3.-С. 42-46. '

16. Соболев, С.С. Генератор перестановок на основе управляемого циклического сдвига [Текст] / С.С. Соболев // Моделирование систем и процессов. - 2011. - №3-4. -С. 47”51.

17. Соболев, С.С. Маршрут проектирования акселераторов генерации комбинаторных перестановок [Текст] / С.С. Соболев, В.К. Зольников // Математическое моделирование в технике и технологии: материалы Всероссийской конференции с элементами научной школы для молодежи. - Воронеж: ИПЦ «Научная книга», 2011. - С. 286-291.

18. Соболев, С.С. RTL-модель генератора комбинаторного беспорядка [Текст] /

С.С. Соболев // Современные проблемы гуманитарных и естественных наук: Материалы VIII Международной научно-практической конференции 26-27 сентября 2011 г Том 1. - Москва, 2011. - С. 62-67.

Просим Ваши отзывы на автореферат в двух экземплярах с подписями, заверенными гербовой печатью, направлять по адресу: 394087, г.Воронеж, ул.Тимирязева, 8, ВГЛТА, ученому секретарю.

Тел / Факс (4732)-53-67-05.

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

Подписано к печати 24.01.12.

Формат 60x90 1/16. Объём 1,25 п.л. Уел. печ. л. 1,16. Тираж 120 экз. Заказ 42 Отпечатано в УОП ФГБОУ ВПО «ВГЛТА»

394087, г. Воронеж, ул. Докучаева, 10

Введение.

1. Анализ средств автоматизированного проектирования устройств генерации полных комбинаторных и возможности их применения для обеспечения безопасности распределенных СУБД.

1.1. Современное состояние и развитие микрокомпонентной базы устройств генерации комбинаторных перестановок.

1.2. Проектирование устройств генерации комбинаторных перестановок на основе функциональных блоков.

1.3. Применение генерации полных комбинаторных перестановок в сфере информационной безопасности. Постановка задачи.

2. Методика проектирования и математическое обеспечение моделирования генерации полных комбинаторных перестановок с отсевом недопустимых перестановок.

2.1. Методика проектирования специализированных устройств генерации полных комбинаторных перестановок.

2.2. Метод генерации поведенческого описания, ЯТЬ-описания и тестового окружения для блока генерации перестановок.!.

2.3. Математическое обеспечение генерации полных комбинаторных перестановок.

2.3.1. Алгоритм генерации полных комбинаторных перестановок с применением циклического сдвига.

2.3.2. Локализация неподвижных точек и алгоритм их отсева при комбинаторной генерации перестановок.

2.3.3. Локализация инволюций и алгоритм их отсева при комбинаторной генерации перестановок.

3. Моделирование генерации перестановок на системном уровне и ЯТЬ-уровне.

3.1. Моделирование генерации перестановок на системном уровне.

3.2. Моделирование генерации перестановок на ЯТЬ-уровне.

4. Структура и функциональность программного комплекса и оценка эффективности.

4.1. Особенности разработанного программного обеспечения и его внедрения в САПР специализированных устройств генерации комбинаторных перестановок.:.

4.2. Оценка эффективности разработанного программного комплекса.

Основные результаты работы.

Актуальность проблемы. Современное развитие полупроводниковых технологий, характеризующееся повышением сложности электронных устройств, изменением проектных норм, разделением труда проектировщиков и образованием кремниевых фабрик, предопределило изменения в методологии проектирования сверхбольших интегральных схем (СБИС). При наблюдаемом общем росте ресурсоемкости процесса разработки эффективным является применение методологии нисходящего проектирования на основе многоуровневого иерархического представления устройств и перехода в процессе проектирования от общего описания системы к детальному описанию составляющих ее компонентов - сложных функциональных блоков, или IP-блоков (от англ. Intellectual Property).

Наряду с изменениями стандартных методов разработки СБИС, необходимо отметить развитие методологии проектирования в соответствии с классом целевых интегральных схем. Учет специфики конкретного класса СБИС позволяет принять во внимание его особенности уже на ранних этапах проектирования и обеспечить более эффективную адаптацию архитектуры на конкретную задачу по сравнению со стандартными средствами, ориентированными на широкую область применения. Примерами таких классов микросхем являются схемы памяти, схемы программируемой логики (ПЛИС), характеризующиеся регулярной структурой. В настоящее время на мировом рынке существует множество фирм, специализирующихся на проектировании конкретного класса СБИС, например, крупнейшими производителями ПЛИС являются компании Altera и Xilinx.

Одним из специфических классов СБИС являются специализированные устройства генерации полных комбинаторных перестановок символьной строки, используемых главным образом в системах защиты информации ЭВМ. Основными особенностями таких устройств являются переменная разрядность символьной строки и наличие ограничений на требуемое множество генерируемых комбинаторных перестановок в некоторых приложениях. Например, в системах динамического преобразования форматов на основе транспозиционных преобразований, некоторые из перестановок являются недопустимыми и могут быть непригодными для формирования использующихся в этих системах дескрипторов формата, а значит, должны быть исключены из рассмотрения. В этом прослеживается аналогия со слабыми ключами в современных шифрах, например, DES. В рассматриваемом случае, перестановка является недопустимой, если она содержит одну или несколько неподвижных точек и/или инволюций.

Применение стандартных средств проектирования при разработке рассматриваемых специализированных СБИС связано с рядом проблем. Современная методология проектирования предполагает разбиение маршрута проектирования на несколько этапов проектных процедур. Первые два этапа составляют проектирование на системном уровне и на уровне регистровых передач (RTL-уровень). На верхнем структурном уровне, называемом также системным, разрабатывается и верифицируется обобщенная модель блока для проверки работоспособности взятого за основу математического алгоритма генерации перестановок. В качестве языка описания чаще всего используется язык SystemC. На RTL-уровне разрабатывается функциональное описание блока на уровне регистровых передач с использованием одного из языков описания аппаратуры (HDL-языков). Такое описание осуществляется чаще всего вручную, путем графического или текстового ввода, что, во-первых, увеличивает трудоемкость и требует недопустимо больших затрат времени, а во-вторых, влечет за собой разрыв между алгоритмическим описанием на SystemC и RTL-описанием. Аналогичный разрыв наблюдается и при разработке тестов для верификации блоков на системном и RTL-уровнях.

Обозначенные проблемы, а также многообразие входных параметров генерации комбинаторных перестановок и увеличение сложности схемы блока генерации с ростом длины символьной строки, повышают риск субъективных ошибок и, таким образом, увеличивают влияние «человеческого фактора» на качество всего проекта. В результате, использование традиционной методологии в процессе проектирования рассматриваемых устройств представляется затруднительным. В этой связи, актуальной задачей представляется разработка средств автоматизации проектирования специализированных устройств генерации комбинаторных перестановок элементов символьной строки, обеспечивающих высокое качество целевых устройств и позволяющих максимально автоматизировать процесс проектирования и верификации на системном и ИЛЬ-уровнях.

Диссертационная работа выполнена в рамках госбюджетной НИР кафедры вычислительной техники и информационных систем ВГЛТА «Автоматизация проектных работ при создании изделий микроэлектроники и лесного комплекса», ГР №01.2.00609244, код ГРНТИ 68.47.01; 50.49.

Объектом исследования является средства автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, предназначенных для обеспечения конфиденциальности данных в рамках СУБД.

Предметом исследования являются модели, алгоритмы и методы проектирования и моделирования в САПР устройств генерации полных комбинаторных перестановок с отсевом недопустимых перестановок, содержащих неподвижные точки и обратимые пары.

Целью исследования является разработка средств проектирования: методики, моделей, методов и алгоритмов для специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки.

В соответствии с поставленной целью в диссертационной работе необходимо решить следующие задачи:

1. провести анализ современного состояния средств автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, выделить направления их текущего развития;

2. разработать методику проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки, позволяющую обеспечить наиболее эффективное проектирование устройств генерации полных комбинаторных перестановок;

3. разработать модели, алгоритмы и методы, позволяющие учесть особенности проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки переменной разрядности' с возможностью отсеивания недопустимых перестановок, которые могут снизить качество проекта;

4. разработать алгоритмическую основу формирования множества комбинаторных перестановок, учитывающей особенности проектирования устройств генерации полных комбинаторных перестановок на системном уровне и уровне регистровых передач (RTL);

5. разработать программное обеспечение подсистемы генерации функциональных блоков для формирования множества полных комбинаторных перестановок элементов символьных строк, верификации и синтеза тестовой последовательности, внедрить разработанные средства в единую среду сквозного проектирования дизайн-центра.

Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы элементы теории автоматизированного проектирования, множеств, дискретной математики, методы и средства структурно-функционального моделирования, технологии объектно-ориентированного и событийно-ориентированного программирования, а также мета-программирования.

Научная новизна результатов, полученных при решении вышеперечисленных задач исследования, состоит в следующем:

- методика проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки, отличающаяся встроенными средствами проектирования специальных микросхем, что позволяет обеспечить более высокое качество и сокращениё цикла проектирования устройств генерации полных комбинаторных перестановок;

- метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности, а также тестов для их верификации, отличающийся наиболее полной автоматизацией процесса проектирования на системном уровне и уровне регистровых передач;

- метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности, отличающийся возможностью исключать недопустимые перестановки на этапе комбинаторной генерации множества возможных перестановок и обеспечивающий эффективность проектных процедур на системном уровне и уровне регистровых передач;

- алгоритм формирования множества полных комбинаторных перестановок элементов символьной строки переменной разрядности, отличающийся учетом особенностей проектирования устройств генерации полных комбинаторных перестановок с возможностью отсеивания неподвижных точек и инволюций в процессе реализации.

Практическая значимость и результаты внедрения. Практическая значимость работы заключается в улучшении качества проектных работ и сокращении жизненного цикла проектирования специализированных устройств генерации полных комбинаторных перестановок за счет внедрения аппаратно-программных средств.

На основе предложенных методов, математических моделей и алгоритмов разработано программное обеспечение. Оно внедрено в ЗАО НПП «РЕЛЭКС» (г. Воронеж) с экономическим эффектом 405 тыс. рублей и в учебный процесс ФГБОУ ВПО «Воронежская государственная лесотехническая академия» (в учебно-методические материалы дисциплин «Системы автоматизации проектирования», «Схемотехническое и функциональное проектирование электронной компонентной базы в САПР», «Методы проектирования микроэлектронных устройств» для подготовки студентов ВГЛТА по направлению «Информационные системы и технологии», а также аспирантов и докторантов по специальности 05.13.12 - Системы автоматизации проектирования).

Полученные средства позволяют снизить трудоемкость, сократить время разработки и минимизировать риск субъективных ошибок при проектировании специализированных устройств генерации комбинаторных перестановок элементов символьной строки.

Выносятся на защиту:

- методика проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки;

- метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности;

- метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности;

- алгоритм формирования множества полных комбинаторных перестановок элементов символьной строки переменной разрядности.

Соответствие паспорту специальности. Согласно паспорту специальности 05.13.12 - Системы автоматизации проектирования, задачи, рассмотренные в диссертации, соответствуют областям исследований:

1. методология автоматизированного проектирования в технике, включающая постановку, формализацию и типизацию проектных процедур и процессов проектирования, вопросы выбора методов и средств для применения в САПР;

3. разработка научных основ построения средств САПР, разработка и исследование моделей, алгоритмов и методов для синтеза и анализа проектных решений, включая конструкторские и технологические решения в САПР и АСТПП.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Международной научной конференции

Проблемы управления, передачи и обработки информации» (Саратов,'2009), Международной научно-практической конференции «Молодежь и наука: реальность и будущее» (Невинномыск, 2010), Всероссийской конференции с элементами научной школы для молодежи «Математическое моделирование в технике и технологии» (Воронеж, 2011), Международной научно-практической конференции «Современные проблемы гуманитарных и естественных наук» (2011).

Публикации результатов работы. По теме диссертации опубликовано 20 работ, в том числе 6 статей в изданиях Перечня, определенного ВАК Ми-нобрнауки России, 1 монография, 1 свидетельство об официальной регистрации программ для ЭВМ, а также 1 патент на изобретение.

Личное участие заключается в определении цели и задач работы [1-3, 13-14], в выполнении научно-технических исследований [10-11], разработке и анализе моделей [4, 5, 15, 18, 19], разработке алгоритмов [10-12], разработке методики проектирования [6, 7, 16, 17, 20], программной реализации [9] и аппаратной реализации [8].

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, изложенных на 129 страницах, включающих в себя список литературы из 104 наименований, 30 рисунков и 13 таблиц.

Основные результаты работы

1. Проведен анализ современного состояния средств автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, определены направления их текущего развития.

2. Разработана методика проектирования специализированных устройств, решающих задачу генерации полных комбинаторных перестановок с функцией фильтрации недопустимых перестановок.

3. Разработаны и исследованы модели, алгоритмы и методы, позволяющие учесть особенности проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки переменной разрядности с возможностью отсеивания недопустимых перестановок.

4. Разработаны алгоритмы формирования множества комбинаторных перестановок, учитывающие особенности проектирования устройств генерации комбинаторных перестановок.

5. Разработано программное обеспечение подсистемы автоматизации проектирования устройств генерации комбинаторных перестановок, включающее в себя:

- программные средства, реализующие подсистему автоматической генерации функциональных блоков для формирования множества полных комбинаторных перестановок на системном и ЯТЬ-уровнях проектирования;

- программные средства, реализующие автоматическую генерацию тестов для функциональных блоков генерации комбинаторных перестановок;

- программные средства подсистемы верификации, предоставляющие возможность автоматизировать процесс верификации функциональных блоков генерации полных комбинаторных перестановок.

6. Подсчитаны трудоемкость и временные затраты проектирования каждого из семейства устройств генерации комбинаторных перестановок и произведена оценка эффективности разработанных средств автоматизации проектирования данных устройств.

7. Разработанные программные средства внедрены в единую среду сквозного проектирования специализированных устройств генерации перестановок в рамках дизайн-центра (ЗАО НПП «РЕЛЭКС», г. Воронеж) с полученным экономическим эффектом в размере 405 тыс. рублей и в учебный процесс Воронежской государственной лесотехнической академии.

1. Адамов, Ю.Ф. Проектирование систем на кристалле Электронный ресурс. / Ю.Ф. Адамов. Электрон, дан. - [Б. м.], [200-?]. - Режим доступа: http://bmstu-sm5.narod.ru/puchkov/puchkovlec.pdf. - Загл. с экрана. -Яз. рус.

2. Адигеев, М.Г. Введение в криптографию. Часть 1. Основные понятия, задачи и методы криптографии Текст. / М.Г. Адигеев. Ростов-на-Дону: Ростовский гос. ун-т, 2002. - 35 с.

3. Атре, Ш. Структурный подход к организации баз данных Текст. / Ш. Атре. М.: Финансы и статистика, 1983. - 320 с.

4. Бадин, М. Платформенный принцип проектирования СБИС и ПЛИС. Часть 1 Текст. / М. Бадин, Д. Воронков, А. Руткевич, М. Сенченко, В. Стешенко, Г. Шишкин // Электронные компоненты. 2008. - №1.

5. Байбурин, В.А. Имитационное моделирования анализа стойкости криптографических систем Текст. / М.О. Оболонский, М.Б. Бровкова // Информационная безопасность регионов. 1 (2). - 2008. - С. 24-32.

6. Бибило, П.Н. Основы языка VHDL Текст. / П.Н. Бибило. М.: СО-ЛОН-Р, 2002. - 224 с.

7. Бибило, П.Н. Системы моделирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum Текст. / П.Н. Бибило. М.: СОЛОН Пресс, 2005. - 384 с.

8. Голицына, О.Л. Базы данных: учебное пособие Текст. / О.Л. Голицына, Н.В. Максимов, И.И. Попов. М.: ФОРУМ: ИНФРА-М, 2007. - 400.

9. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. Текст. М.: Госстандарт СССР. - 1989.

10. Дейт, К. Введение в системы баз данных, 8-е издание Текст.: Пер. с англ. / К. Дейт. — М.: Издательский дом "Вильяме", 2005. — 1328 с.

11. Диго, С.М. Проектирование и использование баз данных Текст. / С.М. Диго. М.: Финансы и статистика, 1995. - 208 с.

12. Дуброво, И.Г. Распределенные базы данных Текст. / И.Г. Дуброво, В.А. Танюшкина. -М.: МИСИ, 1981.-68 с.

13. Евтушенко, Н.Д. Методология проектирования систем на кристалле: Основные принципы, методы, программные средства Текст. / Н. Д. Евтушенко, В. Г. Немудров, И. А. Сырцов // Электроника: наука, технология, бизнес. 2003. - N 6. - С. 7-11

14. Змитрович, А.И. Базы данных Текст. / А.И. Змитрович. Мн.: Университетское, 1991.-271 с.

15. Зольников, В.К. Создание отечественной проектной среды разработки микроэлектронных систем Текст. / В.К. Зольников, В.Н. Ачкасов, П.Р. Машевич, И.П. Потапов // Вестник ВГТУ. Системы автоматизации проектирования, 2006, вып. 2. №3. - С.9-11.

16. Зольников, В.К Автоматизация проектирования специализированных устройств генерации полных комбинаторных элементов символьной строк Текст. / В.К.Зольников, С.С.Соболев. Воронеж: ВГЛТА, 2011. -124 с.

17. Ключев, А.О. Программное обеспечение встроенных вычислительных систем: Учебное пособие Текст. / А.О.Ключев, П.В.Кустарев, Д.Р.Ковязина, Е.В.Петров. СПб.: СПбГУ ИТМО. - 2009. - 212 с.

18. Кнут, Д. Искусство программирования, том 4, выпуск 2. Генерация всех кортежей и перестановок Текст. : Пер. с англ. / Д. Кнут. М.: ООО "И.Д. Вильяме", 2008. - 160 с.

19. Краковик, А. Базы данных Текст. / А. Краковик. М.: Мир, 1988. - 246 с.

20. Кривченко, И. Конфигурируемая система на кристалле Е5 первое знакомство Текст. / И. Кривченко, Р. Золотухо // Компоненты и технологии. - 2001. - №1. - С. 26-29.

21. Кривченко, И. Системы на кристалле: общее представление и тенденции развития Текст. / И. Кривченко // Компоненты и технологии. -2001.- №6.

22. Курейчик, В.М. Комбинаторные аппаратные модели и алгоритмы в САПР Текст. / В.М.Курейчик, В.М.Глушань, Л.И.Щербаков М.: Изд. «Радио и связь». - 1990. - 216 с.

23. Мартин, Д. Организация баз данных в вычислительных системах Текст. / Д. Мартин. М.: 1980. - 602 с.

24. Машевич, П.Р. Инструментальные средства автоматизации проектирования дизайн центра Текст.: монография / П.Р. Машевич, В.К. Зольников; ВГУ. Воронеж, 2006. - 284 с.

25. Машевич, П.Р. Создание отечественной промышленной технологии автоматизации разработки и изготовления СБИС Текст. / П.Р. Машевич, Ю.К. Фортинский // Информационные технологии моделирования и управления. 2005. - №2(20). - С.301-306.

26. Мейер, Д. Теория реляционных баз данных Текст. / Д. Мейер. М.: Мир, 1987.-608 с.

27. Метечко, В.И. Системы распределенных баз данных Текст. / В.И. Ме-течко. М.: МИФИ, 1987. - 66 с.

28. Молдовян, A.A. Криптография Текст. / A.A. Молдовян, H.A. Молдо-вян, Б.Я. Советов. СПб.: Издательство «Лань», 2001. - 224 с.

29. Молодченко, Ж.А. Математические модели транспозиционных преобразований Текст. / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. Москва, 2007. -№12, том 5.-С. 58-60.

30. Нагао, М. Структуры и базы данных Текст. / М. Нагао, Т. Катаяма, С. Уэмура. М.: Мир, 1986. - 197 с.

31. Немудров, В. Системы-на-кристалле. Проектирование. Проектирование и развитие Текст. / В. Немудров., Г. Мартин. Москва: Техносфера, 2004.-216 с.

32. Новиков, Ф.А. Дискретная математика для программистов Текст. / Ф.А. Новиков. СПб.: Питер, 2003. - 304 с.

33. Норенков, И.П. Системы автоматизированного проектрования электронной и вычислительной аппаратуры Текст. / И.П. Норенков, В.Б. Маничев. М.: Высшая школа, 1983. - 272 с.

34. Озкарахан, Э. Машины баз данных и управление базами данных Текст. / Э. Озкарахан. М: Мир, 1989. - 695 с.

35. Пат. на изобретение RU №2320000 С1, МПК G06F 7/76 (2006.01), G06F 12/14 (2006.01). Дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ Текст. / Молодченко Ж.

36. A., Сотов Л.С., Харин В. Н. (Россия). №2007105175/09; заявл. 13.02.2007; опубл. 20.03.2008. - Бюл. №8. - 6 с.

37. Пат. на изобретение RU №2419174 G11C 19/00 (2006.01) Устройство управляемого циклического сдвига Текст. / Сотов Л.С., Харин В.Н., Соболев С.С. (Россия). №2009134344/08; заявл. 14.09.2009; опубл. 20.05.2011.-Бюл. №14. - Юс.

38. Программа моделирования комбинаторных преобразований форматов представления данных в ЭВМ (DMATRIX). Свидетельство об официальной регистрации программ для ЭВМ / Л.С. Сотов, С.С. Соболев,

39. B.Н. Харин. -№ 2010612449 от 07.04.2010.

40. Ревунков, Г.И. Базы и банки данных и знаний Текст. / Г.И. Ревунков, Э.Н. Самохвалов, В.В. Чистов. М.: Высш. шк., 1992. - 392 с.

41. Саймон, А.Р. Стратегические технологии баз данных Текст. / А.Р. Саймон. М.: Знание, 1982. - 254 с.

42. Сергиенко, A.M. VHDL для проектирования вычислительных устройств Текст. / A.M. Сергиенко. К.: ЧП «Корнейчук», ООО «ТИД «ДС», 2003.-208 с.

43. Соболев, С.С. Автоматизация проектирования устройств генерации комбинаторных перестановок / С.С. Соболев, В.К. Зольников // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета (Научный журнал КубГАУ).

44. Краснодар: КубГАУ, 2012. (принята к публикации и включена во второй номер журнала 2012 года).

45. Соболев, С.С. Алгоритм работы и модель функционального генератора перестановок Текст. / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Информационные технологии. 2010. - №4. - С. 41-46.

46. Соболев, С.С. Динамическое форматирование структурных объектов хранилищ данных Текст. / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. -2008,-№4.-С. 28-33.

47. Соболев, С.С. Локализация обратимых пар при комбинаторной генерации перестановок с применением циклического сдвига Текст. / С. С.

48. Соболев, С.С. Методика, модели и алгоритмы проектирования устройств генерации комбинаторных перестановок Текст. / С.С. Соболев,

49. B.К. Зольников // Моделирование систем и процессов. 2011. - №4.1. C. 23-29.

50. Соболев, С.С. Модели устройств кросс-кластерных перестановок данных в ЭВМ Текст. / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Вестник компьютерных и информационных технологий. 2009. - №12. - С.51-55.

51. Соболев, С.С. Устройство функционального генератора перестановок Текст. / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Моделирование систем и процессов. 2011. - №1-2. - С. 59-64.

52. Стенли, Р. Перечислительная комбинаторика Текст.: пер. с англ. / Р. Стенли. М.: Мир, 1990. - 440 с.

53. Страуструп, Б. Язык программирования С++ Текст.: Пер. с англ. / Б. Страуструп. 3-е спец. изд. - М.: Бином, 2003. - 1104 с.

54. Суворова, Е.А. Проектирование цифровых систем на УНОЬ Текст. / Е.А. Суворова, Ю.Е. Шейнин. СПб.: БХВ-Петербург, 2003. - 576 с.

55. Тарасов, И.Е. Разработка цифровых устройств на основе ПЛИС ХШпх с применением языка УНБЬ Текст. / И.Е. Тарасов. М.: Горячая линия - Телеком, 2005. - 252 с.

56. Тиори Т., Фрей Дж. Проектирование структур баз данных. В 2 кн. Текст. / Т. Тиори, Дж. Фрей. М: Мир, 1985.

57. Угрюмов, Е.П. Цифровая схемотехника Текст. / Е.П. Угрюмов. СПб.: БХВ-Петербург, 2000. - 528 с.

58. Ульман, Д. Основы систем баз данных Текст. / Д. Ульман. М.: Финансы и статистика, 1983. - 334 с.

59. Цегелик, Г.С. Системы распределенных баз данных Текст. / Г.С. Цеге-лик, Г.С. Львов: Свит, 1990. - 167 с.

60. Шагурин, И. Системы на кристалле. Особенности реализации и перспективы применения / И. Шагурин // Электронные компоненты. -2009.-№1.

61. Шнайер, Б. Практическая криптография Текст. : Перевод с англ. / Б.Шнайер, Н.Фергюсон. М.: Вильяме. - 2005. - 424 с.

62. Announcing the ADVANCED ENCRYPTION STANDARD (AES) Текст. / Federal Information Processing Standards Publication 197. November 26. -2001.-51 pp.

63. Bell, D. Distributed Database Systems Текст. / D. Bell, J. Grimson. Ad-dison-Wesley Publishing Company, Inc., 1992. -410 c.

64. Black, D.C. SystemC: From the Ground Up Текст. / D.C. Black, J. Donovan. Kluwer Academic Publishers, Boston, 2004. - 244 c.

65. Catapult С Synthesis Overview Электронный ресурс. / Mentor Graphics. All rights reserved. Электрон, текстовые и граф. дан. - [Б. м.], [200-?]. - Режим доступа: http://www.mentor.com/esl/catapult/overview. - Загл. с экрана. - Яз. англ.

66. Chu, Pong P. FPGA Prototyping by VHDL Examples Текст. / Pong P. Chu. John Wiley & Sons, Inc., 2008. - 468 c.

67. Data Encryption Standard (DES) Текст. / Federal Information Processing Standard Publication. FIPS PUB 46-3, National Bureau of Standards, 1977.-26 pp.

68. Ferguson, N. Cryptography Engineering: Design Principles and Practical Applications Текст. / N. Ferguson, B. Schneier, T. Kohno. Wiley Publishing. Inc., Indianapolis, Indiana, 2010. - 353 c.

69. Ghosal, P. Hardware Implementation of TDES Crypto Текст. / P. Ghosal, Mai. Biswas, Man. Biswas // Journal of telecommunications . V.l - ISS. 1. -FEB. 2010. - P. 113-117.

70. Grotker, T. System Design with SystemC Текст. / Т. Grotker, G.Martin, S. Liao, S. Swan. Kluwer Academic Publishers, Boston, 2002. - 240 c.

71. IEEE Std 1076-2008 VHDL Language Reference Manual Текст. / The Institute of Electrical and Electronics Engineers, Inc. 3 Park Avenue, New York, NY 10016-5997, USA. 2009.

72. IEEE Std 1666-2005 SystemC Language Reference Manual / The Institute of Electrical and Electronics Engineers, Inc. 3 Park Avenue, New York, NY 10016-5997, USA.-2008.

73. ISO/IEC 14882:2003. Information Technology Текст. Programming Languages. - С++. - 2nd edition. - ISO/IEC, 2003. - 757 c.

74. Keating, M. Reuse Methodology Manual, Third Edition Текст. / Michael Keating, Pierre Bricaud. Kluwer Academic Publishers. - Bos-ton/Dordrech/London. - 2002.

75. Kimball, R. The Data warehouse lifecycle toolkit: expert methods for designing, developing, and deploying data warehouses Текст. / R. Kimball, L.Reeves, M.Ross, W.Thornthwaite. John Wiley & Sons, Inc., 1998. - 780 c.

76. Matsui, M. Linear cryptanalysis method for DES cipher Текст. / M. Matsui //Workshop on the theory and application of cryptographic techniques on Advances in cryptology. Springer-Verlag. - 1994. - pp. 386-397.

77. Maxfield, С. The Design Warrior's Guide to FPGAs Текст. / С. Maxfield. -Newnes, 2004.-542 c.

78. Moldovyan, A.N. New Class of Cryptographic Primitives and Cipher Design for Networks Security Текст. / A.A.Moldovyan, M. A. Eremeev, N. Sklavos // International Journal of Network Security, 2006. Mar. - Vol.2. - No.2. -pp. 114-125.

79. Network on Chip (NoC) Internet Technology for SoCs Электронный ресурс. / Arteris. The Network-on-Chip Company. Электрон, текстовые и граф. дан. - [Б. м.], [2011?]. - Режим доступа: http://www.arteris.com/technology.php. - Загл. с экрана. - Яз. англ.

80. OCP-IP запускает тесты "сетей-на-чипе" Электронный ресурс. / IXBT. Электрон, текстовые и граф. дан. - [Б. м.], [2007?]. - Режим доступа: http://www.ixbt.com/news/hard/index.shtml707/92/27. - Загл. с экрана. -Яз. рус.

81. Pasham, V. High-Speed DES and Triple DES Encryptor/Decryptor Текст. : Xilinx Application Note: Virtex-E Family and Virtex-II Series / Vikram Pa-sham and Steve Trimberger. XAPP270 (vl.O), August 03.-2001.

82. Ritter, T. Transposition Cipher with Pseudo-Random Shuffling: The Dynamic Transposition Combiner Текст. / T.Ritter // Cryptologia. 1991. V. 15 (l).-P. 1-17.

83. Sklavos, N. Encryption and data dependent permutations: implementation cost and performance evaluation Текст. / N. Sklavos // Proceedings of the International Workshop. Springer-Verlag. - 2003. - LCNS 2776. - pp. 337-348.

84. Synplify Pro 7.7 Release Notes Электронный ресурс. / Synopsis, Inc. -Электрон, текстовые и граф. дан. [Б. м.], [200-?]. - Режим доступа: http://www.synopsis.com. - Загл. с экрана. - Яз. англ.

85. SystemC Version 2.0 User's Guide Электронный ресурс. / Open SystemC Initiative. Электрон, дан. - [Б. м.], [200-?]. - Режим доступа: http://www.systemc.org/downloads/standards. - Загл. с экрана. - Яз. англ.

86. U. S. Pat. No. 5,734,721 B1 H04L9/00 Anti-spoof without error extension (ANSWER)/Clark James Monroe Текст. March 31, 1998.

87. Vahid, F. Digital Design with RTL Design, VHDL and Verilog Текст. : 2nd edition / F. Vahid. John Wiley and Sons Publishers, 2010. - 592 c.

88. Visual Studio 2010 Электронный ресурс. / Microsoft. All rights reserved. Электрон, текстовые и граф. дан. - [Б. м.], [201-?]. - Режим доступа: http://msdn.microsoft.com/en-us/library/dd831853.aspx. - Загл. с экрана. -Яз. англ.

89. Соболева Сергея Сергеевича на тему «Автоматизация проектирования специализированных устройств генерации полных комбинаторныхперестановок элементов символьной строки» (специальность 05.13.12 Системы автоматизации проектирования)

90. Разработанный комплекс программного обеспечения был внедрен в единый маршрут проектирования устройств генерации перестановок, используемых в системах аппаратной поддержки технологий шифрования конфиденциальной информации в современных реляционных СУБД.

91. Общее сокращение временных затрат проектирования при применении разработанной системы составило 32 человеко-дня для устройств генерации

92. УТВЕРЖДАЮ» Ректор ФГБОУ ВПО «Воронежская государ" ^ственная лесотехничептгаа яхгатгст/г1ха\\1. Бугаков

93. Внедрения результатов исследования в учебный процесс позволило оценить эффективность разработанных средств за счет устранения субъективных рисков проектирования данных устройств.

94. Заведующий кафедрой вычислительной техники и информационных системд.т.н., профессор —■ Зольников В.К.