авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


ЭЛЕКТРОНИКА инфо

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

ИНТЕЛЛЕКТУЛЬНАЯ ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНАЯ

СИСТЕМА НА ОСНОВЕ LABVIEW ДЛЯ ЛАБОРАТОРНЫХ

ПРАКТИКУМОВ ПО РАДИОЭЛЕКТРОНИКЕ

УДК 621.382. С.В. Здоровцев, И.Г. Круглов, А.Г. Петрович,

ОАО «МНИПИ», г. Минск

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

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

Введение В настоящее время быстрыми тем пами осуществляется развитие техни ческих и программных средств создания учебных стендов и экспериментальных установок, используемых в учебных процессах и лабораторных практикумах многих ведущих университетов. При этом обычно применяются программ ные средства LabVIEW и встраиваемые дорогостоящие измерительные модули фирмы National Instruments, что пре пятствует широкому использованию информационных технологий в учебном процессе. Высокая стоимость виртуаль ных приборов National Instruments обу словлена затратами на реализацию PCI- Рисунок 1 – Структурная схема ИИИС интерфейса для встраиваемых модулей.

В настоящее время рядом фирм выпускаются виртуальные Измерительный блок был построен на базе двух моду измерительные приборы с USB-интерфейсом [1], которые лей: функционального USB-генератора сигналов и двух позволяют создать интеллектуальные средства измерений канального цифрового USB-осциллографа. Такой выбор с расширенными функциональными возможностями. обусловлен широкими возможностями интеллектуальных Применение интеллектуальных измерительных измерительных USB-приборов, использующих постоянно устройств позволяет снизить требования к центральным увеличивающиеся вычислительные возможности и гиб управляющим компьютерам, а также сократить номенкла- кость ПК, основными достоинствами которых являются:

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

вании и производстве. Следует также отметить специфику – настраиваемый интерфейс пользователя;

программных средств, используемых при создании архи- – возможность функционального расширения и на тектуры интеллектуальных измерительных устройств [2]. ращивания;

– запись времени и комментариев вместе с данными;

Основная часть – автоматизация процесса измерений;

Предлагаемая ИИИС структурно состоит из трех – встроенные в измерительные процедуры возможности функциональных групп. Первая группа включает радио- мультимедиа;

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

тельный (БИ), включающий комплект интеллектуальных При этом автоматизированные средства разработ измерительных USB-приборов с соответствующим про- ки прикладных приложений, например, LabVIEW или граммным обеспечением. Третья группа представляет LabWindows/CVI, делает простым процесс создания как 28 №4- ЭЛЕКТРОНИКА инфо ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ специализированных устройств, так и универсальных, – Square Function. VI – формирователь прямоугольного комбинирующих возможности нескольких приборов. импульса.

В качестве основного критерия, определяющего техни- Для функционирования ИИИС разработан протокол ин ческие требования, предъявляемые к USB-приборам, был формационного взаимодействия узлов и подсистем, и орга выбран критерий соответствия параметров модуля генератора низована синхронизация процессов измерений различных сигналов (форма сигнала, амплитуда, диапазон задаваемой параметров радиоэлектронных блоков. В среде LabVIEW частоты) и характеристик осциллографического модуля (ко- было реализовано управление интеллектуальными изме личество входных каналов, диапазоны разверток амплитуды рительными приборами (генератор сигналов, цифровой и времени) параметрам и характеристикам исследуемых ра- осциллограф), а также управление как отдельными функ диоэлектронных модулей первичной обработки информации. циональными узлами ИИИС, так и всей системы в целом.

При разработке программной части компьютерной На рисунке 2 представлена блок-диаграмма программы информационно-измерительной системы были использо- USB-генератора сигналов.

ваны следующие виртуальные инструменты LabVIEW : Графический интерфейс пользователя реализован – Interpolate 1D.VI – программный интерполятор;

в виде графических образов панелей управления приборов.

– Harmonic Distortion Analyzer.VI – измеритель нели- На рисунке 3 показан пример рабочего окна информаци нейных искажений;

онного дисплея в одном из режимов работы ИИИС при из – Measure_for_1chan(SubVI).VI – измеритель параме- мерении параметров радиоэлектронного модуля в соответ тров сигнала;

ствии с методическими материалами [3]. В представленном – Basic Averaged DC-RMS. VI – измеритель постоянного рабочем окне отображается анализируемая электрическая напряжения;

схема радиоэлектронного модуля, виртуальные панели измерительных приборов (ге нератор сигналов, цифровой осциллограф), параметры и ха рактеристики исследуемого модуля в выбранном режиме ИИИС. В представленном ра бочем окне отображен режим исследования амплитудно частотной характеристики (АЧХ) исследуемого радиоэ лектронного модуля.

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

Блок управления связан с ПК через мост RS-232/USB, что позволяет упростить обмен дан ными путем использования меха низма виртуальных COM-портов.

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

Рисунок 3 – Рабочее окно информационного дисплея ИИИС №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо Заключение 3. Крушев, В.Т. Лабораторный практикум по курсу Разработанная интеллектуальная информационно- Аналоговые электронные устройства для студентов спец.

«Радиотехника», «Радиотехнические системы» и «Радио измерительная система представляет интерес при решении измерительных задач, требующих автоматизации процессов информатика» всех форм обучения / В.Т. Крушев, Э.Г. По измерения, хранения, анализа измерительной информации, пов. – Минск: БГУИР, 2004. – 58 с.

а также для реализации инновационных методов подготовки Abstract технических специалистов различного уровня на основе интеллектуальных аппаратно-программных средств в соот- The article describes an effective solution for the ветствии с современными образовательными программами. implementation of laboratory-based research in radioelectronics involving intelligent information-measuring system based on Литература: LabVIEW universal graphical programming environment.

1. Афонский, А.А., Суханов, Е.В. LabVIEW в USB лабо- The proposed solution creates a set of hardware and software ратории. Контрольно-измерительные приборы и системы. offering the best system operation mode selection, collection, 2. Раннев, Г.Г. Интеллектуальные средства измерений: processing and storage of measurement data with the учебник для студ. высш. учеб. заведений / Г.Г. Раннев. – М.: subsequent creation of electronic reports.

Издательский центр «Академия», 2010. – 272 с. Поступила в редакцию 19.03.2013 г.

НОВОСТИ ST ВО ФРАНЦИИ пРЕдЛАГАЕТ МЭМС НА МуЛьТИпРОЕКТНЫХ пЛАСТИНАХ альный слой для микрогироскопов и акселерометров) STMicroelectronics стала партнером CMP (Circuits совмещает изменяемые толстые и тонкие слои для Multi Projects) во Франции для создания производствен структур и соединений. Правила и инструменты про ного процесса THELMA MEMS, который уже доступен ектирования для процесса THELMA доступны для уни для изготовления опытных образцов в университетах, верситетов и компаний микроэлектроники по первому исследовательских лабораториях и проектных компа- СВЕТОТЕХНИКА запросу.

ниях с помощью технологии мультипроектных пластин.

Производство мультипроектных пластин компании подложки FD-SOI CMP позволяет получать небольшие количества, как (полностью обедненный КнИ) правило, от нескольких десятков до нескольких сотен ST уже сотрудничает с CMP для того, чтобы предо экземпляров полупроводниковых устройств, изготов ставить университетам и проектным фирмам доступ ленных по тем же техпроцессам, что были бы исполь к производственным полупроводниковым процессам зованы в крупносерийном производстве.

ST – от 130-нм КМОП, введенном в 2003 году, до 28-нм ST заявила, что она запускает этот техпроцесс для FD-SOI, запущенном в опытное производство в конце третьих лиц как опытное и foundry-производство, что 2012 года.

бы вдохновить на новые разработки в приложениях «Доступность мелкосерийного производства для определения движения для потребительского, автомо нашего передового МЭМС-процесса вместе с КМОП бильного, промышленного рынков и здравоохранения.

технологиями, включая FD-SOI, дополненного широ Поверхностный 0,8-мкм процесс микромашинных кими производственными возможностями CMP, пред устройств THELMA (Thick Epitaxial Layer for Micro лагает беспрецедентный доступ к современнейшему gyroscopes and Accelerometers – толстый эпитакси микроэлектронному производству для стартапов и ис следовательских лабораторий, желающих проектиро вать интеллектуальные системы датчиков», – сказал Бенедетто Вигна (Benedetto Vigna), генеральный дирек тор группы аналоговой электроники, МЭМС и датчиков в компании STMicroelectronics.

Перспективы интеллектуальных систем для «Интер нета вещей» были представлены Бенедетто Вигна во вступительном докладе-приветствии на конференции DATE (Design, Automation & test in Europe) в Гренобле (Франция).

Напомним, что зеленоградский «Микрон» с сере дины прошлого года также присматривается к МЭМС технологиям своего давнего технологического партнера ST, однако о каких-либо конкретных подвижках в этом направлении до сих пор официально не сообщалось.

ElectronicsWeekly.com 30 №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо КОМПОНЕНТ УПРАВЛЕНИЯ ДОСТУПОМ СИСТЕМЫ УПРАВЛЕНИЯ ДОКУМЕНТАМИ УДК 621.391 М.В. Стержанов, БГУИР, г. Минск Аннотация пользователями с различным уровнем доступа. Одним В статье рассматриваются вопросы построения из важнейших принципов разработки системы управ компонента управления доступом в системе управления ления техническими документами (СУД) Stagirites документами. Описывается общая функциональность является обеспечение защиты информации от несанк системы, приводятся основные сущности модели базы ционированного доступа. Несанкционированный до данных системы, рассматривается процедура проверки ступ к информации (НСД) – это доступ к информации, прав доступа пользователя на элемент контента. нарушающий правила разграничения доступа с исполь зованием штатных средств, предоставляемых средства Введение ми вычислительной техники или автоматизированными Одним из современных направлений развития системами. Защита от НСД – это предотвращение или системы конструкторско-проектных работ является существенное затруднение несанкционированного до интеграция информационных технологий в процесс ступа [1].

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

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

ется система управления техническими документами каталога, панели инструментов и области просмотра (СУД) Stagirites, автоматизирующая процессы ввода, и редактирования. Каталог предназначен для структу модификации, хранения и преобразования информации. ризации и краткого описания ресурсов, размещающихся Любая система управления документами является в репозитории. Панель инструментов позволяет выпол многопользовательской системой. Она позволяет раз- нять над содержимым системы операции преобразова делять редактирование контента между несколькими ния и редактирования. Область просмотра и редакти Рисунок 1 – Основные элементы системы №4- ЭЛЕКТРОНИКА инфо ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Рисунок 2 – Таблицы БД, описывающие основные сущности системы рования отображает текущие пять записей и позволяет раций над узлами (добавление, удаление, копирование, вносить в текст активного документа изменения. перемещение) реализована операция «повторного ис Система представляет контент в виде множества от- пользования» контента, которая помогает ликвидиро дельных записей. Записи упорядочиваются в каталоге вать дублирование информации и позволяет строить с помощью иерархической древовидной структуры, на- новые узлы контента по уже имеющимся. При этом зываемой деревом публикаций. Выбор такой структуры информация репозитория разделяется между узлами представления данных является не случайным. Одним дерева. Данный принцип аналогичен концепции сим из центральных принципов работы с информацией яв- вольной ссылки в UNIX.

ляется принцип модульности. В соответствии с этим Основные сущности модели БД системы представ принципом контент структурируется в виде отдельных лены на рисунке 2.

блоков (публикаций и заголовков). Текстовые записи Для каждого объекта в системе существует запись бывают трех типов: публикация, заголовок, статья. в таблице toc_record, которая служит для хранения де Запись, соответствующая корневому узлу дерева, на- скриптора объекта и имени записи, отображаемой в дереве зывается публикацией. Каждая публикация содержит публикаций. При помощи внешнего ключа на таблицу набор логически сгруппированных документов и может toc_record_type можно узнать тип записи (элемент дерева представлять отдельный проект, дело, книгу и т.п. Не- публикаций, системный тег) и определить таблицу, со корневые записи-контейнеры называются заголовками. держащую непосредственно данные записей этого типа.

Заголовками являются структурные элементы проектной Данное отношение имеет вид «один к одному» и реали документации, описывающие отдельные разделы. Статьи зуется посредством миграции первичного ключа id та являются листьями дерева публикаций и хранят в себе блицы toc_record в качестве внешнего первичного ключа текст, таблицы, изображения. Каждая запись содержит в другие таблицы. Например, текст публикаций хранится следующую метаинформацию: дату создания, имя созда- в таблице record_publication, текст заголовков – в таблице теля, дату последней модификации и имя пользователя, record_branch, текст статей – в таблице record_article (кон который осуществил последнюю модификацию записи. тент хранится в формате XHTML).

На рисунке 1 показано главное окно системы. Таблица toc_node служит для структуризации объ Дерево публикаций обеспечивает целостность ектов системы и представления связей между записями представления информации. Дерево является гибкой таблицы toc_record в виде отношения «родитель структурой, содержание каждого проекта может легко потомок». Иерархия узлов дерева публикаций хранится дополняться или изменяться. Помимо очевидных опе- именно в этой таблице. Каждый узел имеет уникальный 32 №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо идентификатор, связь с родителем (parent_id), а также жат для указания стандартных прав, единых для всех порядковый номер, соответствующий позиции по от- объектов;

ношению к смежным узлам. – биты 24–27 являются зарезервированными;

Таблица toc_relation позволяет задать для каждого – биты 28–31служат для указания стандартных прав типа узла разрешенные типы дочерних объектов. Напри- доступа: 28 – полный доступ, 29 – разрешение на вы мер, для публикации в качестве дочерних узлов могут полнение, 30 – разрешение на запись, 31 – разрешение выступать только заголовки и статьи. С помощью та- на чтение.

блицы toc_filter можно разрешить отображение в дереве Тип записи ACE определяет отношение записи публикаций только записей определенного типа. Напри- к списку разрешающих или запрещающих прав. Маска мер, компонент, представляющий дерево публикаций, наследования является битовым массивом разрядности может быть использован для отображения не только 32. На данный момент поддерживаются следующие структуры документов, но и конфигурационных параме- значения маски наследования:

тров системы. Данные два представления должны быть – 1. ACE наследуется для подконтейнеров;

доступны разным пользователям. Поэтому для каждого – 2. ACE наследуется для подобъектов;

пользователя дерево будет строиться с применением – 4. ACE наследуется только для непосредственных необходимого фильтра. потомков;

– 8. ACE наследуется для подобъектов, однако, не Ограничение доступа к элементам контента применяется для данного объекта.

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

минимальное количество ресурсов;

Опишем процедуру проверки прав доступа пользо – независимость. Необходимо минимизировать за- вателя на элемент контента.

висимости между компонентом прав доступа и другими Шаг 1. Пользователь запрашивает требуемые права объектами для того, чтобы компонент можно было от- доступа для данного узла.

Шаг 2. Система выбирает список объектов ACE L, ключить или при необходимости заменить;

– гибкость. Функциональность компонента должна относящихся к данному узлу и применимых: к пользо быть расширяемой. Компонент должен поддерживать вателю;

к группам, в которые он входит;

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

стей различных групп пользователей. Шаг 3. На основании запрашиваемой маски доступа и списка L принимается решение о разрешении или за Права на элементы контента выдаются абстрактной сущности «Опекун», в качестве которой может высту- прете доступа:

– если в списке L имеется хотя бы один объект, запре пать пользователь системы, группа, системная учетная запись. Общая информация об «Опекуне» представлена щающий любое действие, указанное в запрашиваемой в таблице toc_record в виде имени и идентификатора маске, то в доступе отказывается;

объекта. Информация о конкретных типах «Опекунов» – если конъюнкция масок прав всех объектов списка L содержит все запрашиваемые права, то доступ раз хранится в таблицах usr_account, usr_group, usr_system.

Избирательное управление доступом реализовано решается.

с использованием списка контроля доступа. Таблица Ограничение доступа к модулям системы ACE (Access Control Entry) служит для указания прав «Опекуна» на элементы контента. Объект системы пред- Помимо доступа к элементам контента требуется ставляется идентификатором узла в дереве контента, разграничить доступ пользователей к различным вспо «Опекун» представляется своим идентификатором могательным модулям, входящих в состав СУД (напри (toc_record.record_id).

Помимо этих иденти фикаторов, каждая за пись ACE содержит маску прав, тип, маску наследования. Маска прав представляет со бой 32-битный массив, в котором:

– биты 0–15 служат для указания специаль ных прав, специфич ных для каждого типа объекта;

Рисунок 3 – Структура роли – биты 16–23 слу №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо мер: «Загрузка данных», «Преобразование данных», элементам контента, что в совокупности с механиз «Управление пользователями»). Все пользователи си- мом настройки ролей позволяет оперативно создавать стемы в ходе своей работы явно или неявно обращаются специфические автоматизированные рабочие места к различным данным. В качестве таких данных могут без привлечения разработчиков системы. Механизм выступать элементы контента, конфигурации систе- настройки ролей отображает полную картину разделе мы, а также файлы, используемые в процессе работы ния прав в системе, облегчает понимание и контроль системы. Данные логически объединяются и хранятся сфер ответственности каждого пользователя, позволяет в контейнере, называемом группой данных (ГД). По- администратору гибко и прозрачно модифицировать мимо обращения к данным, пользователь выполняет права доступа.

над данными различные операции. В качестве таких Благодарности операций можно выделить: изменение содержания, удаление, создание новых объектов данных. Набор Данная работа выполнялась при поддержке гранта логически связанных операций называется группой Ф11-М210 Белорусского республиканского фонда фун операций (ГО). Для получения одновременного доступа даментальных исследований.

к ГД и ГО введено понятие роли. Роль является сово Литература:

купностью некоторых возможностей пользователя в системе. Обладание ролью дает право доступа ко всем 1. Защита от несанкционированного доступа к инфор объектам данных и операций, входящих в ГД и ГО, от- мации. Термины и определения / Утверждено решением носящихся к этой роли. председателя Гостехкомиссии России от 30 марта 1992 г.

При назначении роли определяется период действия, Abstract т.е. доступ к некоторому модулю системы устанавли вается на определенный период времени (возможно, Access control component for DMS is detailed. General неограниченный). functionality, DB design and rights check algorithm is Заключение discussed.

Описанный подход к разграничению прав в системе Поступила в редакцию 23.10.2012 г.

Stagirites позволяет управлять доступом к конкретным ПРОИЗВОДСТВО ПЕЧАТНЫХ ПЛАТ ОАО «МПОВТ»

1978.

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

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

Если Вы нуждаетесь в высококачественных печатных платах, твердосплавном инструменте для их обработки, изделий из твердого сплава – производство печатных плат к Вашим услугам!

Республика Беларусь Тел.: (+375 17) 253 65 04 e-mail: contact@mpovt.by ОАО «МпОВТ»

220140, г. Минск, (+375 17) 253 74 32 mpovt.by производство печатных плат Ул. Притыцкого, 62 Факс: (+375 17) 253 60 Технические характеристики изготавливаемых печатных плат: • Обработка контура ПП: фрезерование (ЧПУ), вырубка, • Максимальные габариты плат: 460510 мм;

скрайбирование;

• Количество слоев – 122;

• Маркировка – сеткографическая.

• Соотношение толщины платы к диаметру отверстия – 6:1;

• Минимальный диаметр металлизированного отверстия – 0,3 мм;

• Минимальная ширина проводников – 0,1 мм;

Приемка плат осуществляется по ГОСТ 23752-79 и в • Гальваническое покрытие КПК: Ni 6;

соответствии с техническими требованиями заказчика.

• Минимальное расстояние между проводниками – 0,12 мм;

Возможно изготовление печатных плат с приемкой «5»

• Покрытие под пайку: HALS;

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

жидкая фотоформируемая;

34 №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо ГЕНЕРИРОВАНИЕ И ФУНКЦИОНАЛЬНО-СТРУКТУРНАЯ ОПТИМИЗАЦИЯ БАЗОВОГО КОМПЛЕКТА ТАБЛИЦ ДЛЯ МУЛЬТИПЛИКАТИВНОЙ МИМА-СХЕМЫ МОНТГОМЕРИ А.А. Коляда, А.Ф. Чернявский, Е.В. Шабинская, БГУ, г. Минск УДК 681.3.06(082) Аннотация Значительное упрощение алгоритмов умножения по Для базовых модулярных систем счисления (МСС) большим модулям на основе модулярной схемы Монт схемы Монтгомери для умножения по большим модулям гомери достигается при использовании минимально разработаны методы и компьютерные алгоритмы генериро- избыточной МА (МИМА) [57], которая отличается от вания комплекта таблиц. В частности, синтезированы про- неизбыточной МА существенно большей эффективностью цедуры формирования таблиц для суммирования вычетов немодульных процедур. В настоящей статье представлены по основаниям МСС аккумулятивно-табличным методом, методологические и алгоритмические средства табличной а также таблиц для расчета интервально-индексных харак- реализации МИМА-схемы типа Монтгомери для умноже теристик и расширения кодов. Представленный комплекс ния по большим модулям, позволяющие минимизировать методологических и алгоритмических средств дает широ- временные затраты на выполнение немодульной компо кие возможности для разгрузки процесса умножения по ненты схемы.

большим модулям, осуществляемого в реальном времени, 1 Базовые обозначения и терминология от расчетов, которые могут быть выполнены предвари 1.1. Z – множество целых чисел (ЦЧ).

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

Введение 1.3. Zm = {0, 1, …, m-1} и = {– [m/2], – [m/2]+1,..., В спектре многочисленных современных приложений [m/2] – 1} – множества (кольца) наименьших неотрицатель модулярной вычислительной технологии (МВТ) разработ- ных и абсолютно наименьших вычетов по натуральному ки в области защиты информации занимают особое место. модулю m1 соответственно.

1.4. |х|m – элемент множества Z m, сравнимый с x К разряду наиболее эффективных и успешных приложений данного класса, в первую очередь, следует отнести вы- (в общем случае рациональной величиной) по модулю m.

сокоскоростные реализации с применением арифметики 1.5. НОД(m, n) – наибольший общий делитель нату МСС – модулярной арифметики (МА) процедур умноже- ральных чисел m и n.

ния и возведения в степень по большим модулям [15], 1.6. (m) функция Эйлера, ставящая в соответствие модулю m число вычетов кольца Zm взаимно простых c m составляющих, как известно, основу криптографических преобразований. Кодовый параллелизм МСС, обусловив- (удовлетворяющих условию НОД(, m)=1).

ший отсутствие межразрядных связей в арифметических 1.7. g = gm – первообразный корень по модулю m, операциях, дает модулярным вычислительным структурам определяемый как элемент множества Gm, такой, что НОД(g, m)=1 и min{ | |g|m=1 (0)} = (m).

гораздо большие возможности в сравнении с позиционны 1.8. indg – индекс вычета € Zm(=0) по модулю m ми структурами для проведения быстрых, точных расчетов, особенно на диапазонах больших чисел. и основанию g (g первообразный корень), определяемый Говоря о МВТ-приложениях, прежде всего, отметим, равенством.

что подлежащие реализации в МСС целевые функции 1.9. Mn=, Mi,n=, где m1, m2, …, решаемых задач обычно сводятся к модели, которая со mn – натуральные модули (n1).

стоит, главным образом, из модульных сегментов. При 1.10. код МСС с основания этом, используемый динамический диапазон должен ми m1, m2, …, mk (k1) или модулярный код (МК) ЦЧ включать конечные результаты счета на всех сегментах.

X по базису M={ m1, m2, …, mk}.

Корректность такого режима вычислений достигается 1.11. TIndi и TAIndi – таблицы индексов и анти при помощи операций масштабирования. С обозначен индексов по модулю m i, определяемые для соот ной моделью идеально согласуется мультипликативная ветственно по правилам МА-схема Монтгомери. Применяемый в ней целочис ленный масштаб требует предельно простой операции масштабирования частного вида – деления нацело, т.е.

операции. Важнейшим фактором в данном случае является то обстоятельство, что для результата масштабирования – произведения Монтгомери всегда можно обеспечить принадлежность к диапазону операндов. Это позволяет и осуществлять модульное возведение в степень без кор рекции произведений. Отмеченные реализационные до TAIndi[j] = ( ), стоинства мультипликативной МА-схемы Монтгомери обусловили повышенный интерес к ней специалистов по m_max – верхний ограничительный порог для основа криптографической защите информации. ний МСС.

№4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо 1.12. GTMpl_Const_Mod(m, n, c, TM) процедура, осуществляющая формирование таблицы TM[]=|c| m (c€{1, 2,..., m1}, ), (6) где m и n – некоторые модули [8].

(mk 2m0+kl2, m0 kl2);

1.13. EC(X;

M1, M2) и EC(X;

M2, M1) – операции рас ширения МК числа X по базисам M1 = {m1, m2, …, ml} и M2 = {ml+1, ml+2, …, mk} (1lk) на основания базисов (7) = ;

M2 и M1 соответственно [8].

1.14. p – рабочий модуль (большое ЦЧ) для мультипли кативных операций.

, 2 Применение индексного метода модульного умножения для расчета констант мультипликативной МИМА-схемы Монтгомери Пусть A и B – операнды, подлежащей выполнению (8).

операции умножения по некоторому большому модулю p, и пусть A, B, p заданы кодами МСС с базисом M: Входящие в состав интервально-модулярной формы (ИМФ) (2), (5) и, как следствие, в расчетные соотношения (3), (4), (6)(8) для интервально-индексных характеристик и расширения МК коэффициенты являются произведения ми оснований МСС и/или содержат мультипликативные По методу Монтгомери в качестве искомого произведе- инверсии ЦЧ по модулям. Это относится и к другим опе ния операндов A и B принимается ЦЧ =. рациям схемы (1). В свете сказанного, свойства рассмо При этом, как показано в [57], результирующая мульти- тренного в [8] индексного метода модульного умножения пликативная схема Монтгомери, базирующаяся на МИМА, для таблично-сумматорной технологии синтеза компью сводится к операционной последовательности: терных МИМА-процедур Монтгомери на основе муль ‹C=AB=( )( );

типликативной схемы (1) представляют особую важность.

Особенности применения индексного метода модульного D= умножения ниже демонстрируются на примере алгоритма расчета коэффициентов ИМФ ЦЧ в форме, адаптированной к базовым немодульным процедурам мультипликативной МИМА-схемы (1). Синтезированный алгоритм состоит в нижеследующем.

Входные данные алгоритма: основания m, m2,..., mk МСС.

Выходные данные: коэффициенты ИМФ, отвечающие ›. (1) базисам {m, m2,..., ml} и {ml+1, ml+2,..., mk} усеченных МСС, Фигурирующие в (1) процедуры расширения кодов а также МК (,,..., ) масштаби и ) реализуются по расчет- рующего множителя для схемы (1).

ным соотношениям: Предварительно полученные данные: таблицы TIndi индексов и TAIndi антииндексов по модулям mi ( ) (см. 1.11).

Тело алгоритма (2) ;

Расчет коэффициентов ИМФ нижнего (внутреннего) уровня для первой усеченной МСС.

(3) ;

РК.1. Переменной i цикла присвоить начальное зна чение i=1.

( ), РК.2. Вычислить сумму.

(4) ;

РК.3. Получить константу.

РК.4. Если il1, то i увеличить на 1 (ii+1) и перейти к РК.2.

(5) ;

РК.5. Найти.

36 №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо РК.6. Определить константу.

.

Расчет коэффициентов ИМФ верхнего (внешнего) РК.19. Если jl, то увеличить j на 1 (j=j+1) и перейти уровня для первой усеченной МСС.

к РК.18. По достижении равенства j=l завершить работу РК.7. Положить j=l+1. алгоритма.

3 Генерирование базового комплекта таблиц для РК.8. Вычислить.

мультипликативной МИМА-схемы Монтгомери РК.9. Найти индексы Таблично-сумматорная технология синтеза и ком пьютерной реализации мультипликативных процедур по большим модулям p, базирующихся на МИМА-схеме.

и Монтгомери (1) предполагает использование не только та блиц TIndi, TAIndi, TRes_UPi, TResi ( ) умножения и свертки двоичных кодов (приведения к остаткам) ЦЧ по основаниям mi МСС [8], но и таблиц, которые предназна ( ). чены для расчета интервально-индексных характеристик и расширения кодов. Из расчетных соотношений (2), (3), (4), РК.10. Определить масштабирующий множитель для (5), (7), (8) этих операций видно, что ключевая роль в про схемы (1) по модулю mj: цедурах генерирования базового комплекта таблиц (КТ) должна быть отведена таблицам TRes_Normi ( ). и _TRes_Normi ( ) нормированных остатков по модулям mi соответственно базисов {m, m2,..., ml} РК.11. Если jk, то j увеличить на 1 (j=j+1) и перейти и {ml+1, ml+2,..., mk}. Указанные таблицы формируются по к РК.8. правилам:

Расчет коэффициентов ИМФ нижнего уровня TRes_Normi[]= (коэффициентов нормировки цифр МК), (9) отвечающих базису второй усеченной МСС. ( ;

);

РК.12. Переменной i цикла присвоить значение i=l+1.

_TRes_Normi[]= РК.13. Получить сумму.

(10) ( ;

).

РК.14. Определить константу Операция нормировки применяется также и при. получении согласно (1), МК ( ) ЦЧ.

Для табулирования цифр данного МК будем использо РК.15. Если ik1, то увеличить i на 1 (i=i+1) и перейти вать таблицы.

к РК.13.

_TMpli[x]= РК.16. Вычислить сумму.

(11) ;

).

и получить коэффициент Генерирование таблиц (9)(11) осуществляется проце дурами GTMpl_Const_Mod(mi, mi,, TRes_Normi).

), GTMpl_Const_Mod(mi, mi, (, Расчет коэффициентов ИМФ верхнего уровня, _TRes_Normi) ( ), GTMpl_Const_Mod(mi, отвечающих базису второй усеченной МСС.

2mi1,, _TMpli) ( ). Требуемые для ука РК.17. Положить j=1. занных процедур системные константы:, и вычисляются в рамках алго РК.18. Определить ритма РК.1РК.19.

и найти индексы:

Таблицы (9) и (10) нормированных цифр МК вы полняют вспомогательную роль. Они служат основой, №4- ЭЛЕКТРОНИКА инфо ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ для генерирования таблиц интервальных индексов (ИИ) ГТИИ.6. Согласно (13) с помощью процедуры и расширения кодов. В таблицах ИИ (присвоим им имена GTMpl_Const_Mod(ml, ml,, TIIl), реализуемой по TIIi (i = 1, l), _TIIi (i = l + 1, k)) хранятся вычеты типа (4) алгоритму ТК.1ТК.5, сформировать искомое содержимое и (8), используемые для вычисления компьютерных ИИ ЦЧ таблицы TIIl.

в первой и второй усеченных МСС. Таблицы расширения Генерирование таблиц ИИ, отвечающих базису {ml+, кодов – TEi_j (i = 1, l);

j = l + 1, k) и _TEi_j (i = l + 1, k;

ml+2,..., mk} j = 1,l) предназначены для хранения слагаемых расчетных ГТИИ.7. Переменной i цикла присвоить начальное соотношений (2) и (5). Ниже приводятся алгоритмы гене- значение i=l+1.

рирования таблиц ИИ и расширения кодов. ГТИИ.8. Получить индекс ik = по модулю mk.

вычета Алгоритм генерирования таблиц ИИ ГТИИ.9. Положить TIIi[0]=0.

Входные данные алгоритма: основания m, m2,..., mk МСС. ГТИИ.10. Для всех = 1, mi – 1 выполнить _TIIi[]= =TAIndk[ik+ +TIndk[_TRes_Normi[]]].

Выходные данные: таблицы ИИ, которые в соответ ГТИИ.11. Если ik1, то увеличить i на 1 (i=i+1) ствии с (4) и (8) формируются по правилам:

и перейти к шагу ГТИИ.8.

TIIi[]= ГТИИ.12. В соответствии с (15) при помощи про цедуры GTMpl_Const_Mod(mk, mk,, _TIIk) сформировать содержимое таблицы _TIIlk и завершить (12) ;

работу алгоритма.

TIIl[]= Алгоритм генерирования таблиц расширения кодов Входные данные алгоритма: основания m, m2,..., mk, (13) ;

а также вспомогательный модуль m0, удовлетворяющий TIIi[]= условиям m0 kl2=_l2, mk 2m0+_l2 и вычисляемый по формуле m0 = (mk – (k – l) + 2) / 2 = (mk –_l + 2) / 2.

Выходные данные: таблицы расширения кодов – TEi_j (14) ;

и _TEi_j, которые в соответствии с (2), (5), (6), (9), (10), фор мируются по правилам:

_TIIk[]= TEi_j[]= (15) ;

;

(16) Предварительно полученные данные: таблицы норми рованных остатков TRes_Normi (i = 1, l – 1), _TRes_Normi TEl_j[]= (i = l + 1, k – 1), определяемые по формулам (9), (10), таблицы индексов и антииндексов – TIndl, TIndk, TAIndl, (17) ;

TAIndk, формируемые в рамках алгоритма ТИА.1ТИА. и системные константы:,, исполь _TEi_j[]= зуемые в (13), (15) и вычисляемые процедурой РК.1РК.19.

Тело алгоритма Генерирование таблиц ИИ, отвечающих базису {m, m2,..., ml} ;

(18) ГТИИ.1. Переменной i цикла присвоить начальное значение i=1.

ГТИИ.2. Найти индекс il по модулю ml величины == по формуле _TEk_j[]= il = (см. (44)).

(19) ;

ГТИИ.3. В таблицу TIIi записать нулевой элемент:

TIIi[0]=0.

В рамках рассматриваемого алгоритма соотношения ГТИИ.4. Для = 1, m i –1 выполнить операции (16)(19) реализуются с помощью индексного метода TIIi[]=TAIndl[il+ +TIndl[TRes_Normi[]]]. модульного умножения.

ГТИИ.5. Если il1, то инкрементировать i (i=i+1) Предварительно полученные данные: таблицы и перейти к ГТИИ.2. индексов и антииндексов – TIndi, TAIndi (i = 1, k), рас считываемые согласно п. 1.11, таблицы нормированных 38 №4- ЭЛЕКТРОНИКА инфо ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ остатков TRes_Normi (i = 1, l –1), _TRes_Normi (i = l + 1, Представленный комплекс методологических и алго k – 1), определяемые по формулам (9), (10), а также сис- ритмических средств, составляющий базовое математи темные константы и ческое обеспечение таблично-сумматорной технологии реализации мультипликативной МИМА-схемы Монтгоме вычетов Ci,j и C'i,j по ри (1), дает широкие возможности для разгрузки процесса модулям mj из (16)(19), вычисляемые в рамках алгоритма умножения по большому модулю p, осуществляемого РК.1РК.19 (см. РК.9, РК.18). в реальном времени от расчетов, которые могут быть выполнены предварительно. Это обусловлено тем, что Тело алгоритма генерирования таблиц расширения генерирование таблиц происходит именно на этапе пред кодов варительных вычислений. В рамках таблично-сумматорной Генерирование таблиц расширения кода ЦЧ по основа- реализационной технологии наибольшая производитель ниям первой усеченной МСС на основания базиса второй ность, естественно, достигается при использовании макси усеченной МСС мального базового КТ:

ГТР.1. Переменной j цикла присвоить начальное зна чение j=l+1.

ГТР.2. Переменной i цикла присвоить значение i=1. ;

ГТР.3. Положить TEi_j [0]=0 и для = 1, mj – 1 выпол TRes1TResk;

TIIi(i = 1, l);

_TIIi(i = l + 1, k);

нить операции:, TEi_j(i = 1, l;

j = l + 1, k);

TEi_j []= _TEi_j(i = l + 1, k;

j = 1, l;

) (20) _TMpli i = l + 1, k.

ГТР.4. Если il-1, то увеличить i на 1 (i=i+1) и перей Отметим, что в комплект (20) не включены таблицы ти к ГТР.3.

TRes_Normi(i = 1, l – 1) и _TRes_Normi(i = l + 1, k – 1) ГТР.5. В таблицу TEl_j поместить набор вычетов по нормированных цифр МК. Эти таблицы выполняют вспо модулю mj согласно правилам: TEl_j [0]=0, TEl_j []=0, могательную роль. Они используются при формировании TAIndj[cl,j+ TIndj[]] ( = 1, mj – 1), причем в случае mjml таблиц ИИ и расширения кодов (см. (12), (14), (16), (18)) осуществить коррекцию: TEl_j [mj]=0.

и после реализации процедур ГТИИ.1ГТИИ.12, ГТР. ГТР.6. Усли jk, то инкрементировать j (j=j+1) и перей ГТР.12 могут быть удалены из оперативной памяти.

ти к ГТР.2.

Суммарное количество таблиц максимального КТ (20) составляет Генерирование таблиц расширения кода МИМСС (21) NT, max = 2l_l+5k+1.

с основаниями ml+1, ml+2,..., mk на модули m, m2,..., ml ГТР.7. Переменной j присвоить начальное значение j= 1. на i-е основание приходится ГТР.8. Положить i=l+1.

ГТР.9. В таблицу _TEi_j поместить нулевой элемент:

_TEi_j [0]=0 и для всех = 1, mi – 1 реализовать операции:

NT, max, i =, _TEi_j []= таблиц, которые содержат ГТР.10. Если ik1, то i увеличить на 1 (i=i+1) и перей- NЭТ, max, i = ти к ГТР.9.

ГТР.11. В соответствии с (19) сформировать искомое содержимое таблицы TEk_j, выполняя последовательность действий:

а) положить _TEk_j [0]=0, _TEk_j []=TAIndj[c'k,j + +TIndj[]] ( = 1, m0 – 1);

б) переменной =m0;

в) получить величину x = mj – mk + ;

г) если x0, то увеличить x на mj (x=x+mj);

д) в таблицу _TEk_j записать очередной элемент _TEk_j[]=TAIndj[c'k,j + +TIndj[x]];

(22) е) при mk1 инкрементировать (=+1) и перей ти к б).

ГТР.12. Если jl, то увеличить j на 1 (j=j+1) и перейти элементов разрядностью bi = log2 mj бит. Напомним, к ГТР.8. По достижении равенства j=l завершить работу что фигурирующие в (22) параметры E_0=2b_0 и E_0=2b_ алгоритма. представляют собой мощности соответственно диапазонов №4- ЭЛЕКТРОНИКА инфо ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ изменения (p_0)- и (p_1)-битовых частей (младших и стар- табличной памяти для мультипликативной схемы (1). Для ших), накапливаемых согласно аккумулятивно-табличному реализации обозначенного подхода удобно использовать методу сумм вычетов из кольца Zmj;

b_0 + b_1 = bcум;

минимальный КТ вида:

E_0 mi. Как показано в разделе 4.3, разрядность bсум вы числяемых модульных сумм практически не превышает ;

бита. Исходя из этого, положим b_0 = b_1 = 12 бит.

Из (22) следует, что максимальный КТ (20) в общей TRes1TResk;

TRes_Normi(i = 1, l – 1);

сложности занимает память объемом _TRes_Normi(i = l +1, k – 1);

TIIi(i = 1, l);

_TIIi(i = l + 1, k);

MТ, max = (26) _TEk_j(j = 1, l);

_TMpli(i = l + 1, k).

Общее количество таблиц, отвечающее КТ (26), вклю чая таблицы системных констант, рассчитываемых в рам ках алгоритма РК.1РК.19, составляет (23) (27) NT,min = 8k.

байтов. Из (23) с учетом (21) для MТ, max получаем верхнюю Суммарный объем памяти, требуемый для размещения оценку:

КТ (26), а также таблиц констант определяется формулой:

MТ, max. 2k 213+8k216+4_l 216+2(l+1)_l216+2l(_l+1)216= = k214+(_l+(4k+_l+(l+1)_l+l(_l+1)))217 = MТ, min·= (24) = k214+(_l+NТ, max) байт.

(28) В таблице 1 приведены значения характеристик NТ, max· и MТ, max·, рассчитанные по (21) и (24) для случаев, когда раз байтов. При m_max=216, E_0 = E_1 = 212 и основаниях рядность модуля p ограничена сверху порогами 1024 и m, m2,..., mk, выбираемых по методике, изложенной бита. Мощности l и _l базисов {m, m2,..., ml} и {ml+1, ml+2, в [8], компьютерные расчеты по (27), (28) для моду..., mk} получены с помощью ПЭВМ согласно методике, лей p разрядностью 1024 и 2462 бита соответствен разработанной в [8].

но дают NТ,min = 8130 =1040 таблиц, MТ, min = 153 Мб В максимальном КТ (20) наиболее значимая часть (по и NТ,min = 8310 = 2480 таблиц, MТ, min·= 362 Мб.

размеру занимаемой памяти) приходится на таблицы TEi_j Из таблицы 1 следует, что при p разрядностью и _TEi_j, суммарное число которых определяется формулой и 2462 бита максимальный КТ занимает больше памяти, NТ,Р = 2l_l. В соответствии с (21) в КТ (20) таблицы рас чем минимальный соответственно в (1155,78/153)7, ширения кодов составляют долю:

и (6243,59/362)17,25 раз. Вместе с тем, как показы вают алгоритмы ГТИИ.1ГТИИ.12 и ГТР.1ГТР.12, продемонстри-рованная в них вычислительная техноло (25).

гия с применением таблиц индексов и антииндексов и, в частности, типовой операции вида TAind[c+TInd[]] Если l =_l = 65 (см. таблицу 1), то отношение (25) при (cZm1;

{1, 2,..., m_max1};

m{m1, m2,..., mk}) по нимает значение NТ,Р /NТ,max 0,922, а в случае l =_l = зволяет весьма эффективно производить расчет слагаемых величина NТ,Р /NТ,max 0,966. С ростом l и _l, что имеет модульных сумм (5) и (2). Таким образом, использование место при увеличении разрядности модуля p, доля таблиц минимального КТ (26) для реализации мультипликативной расширения кодов в максимальном КТ приближается к 1.

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

ной памяти таблиц TEi_j и _TEi_j (полностью или частич но) позволяет значительно сократить объем необходимой Таблица 1 – Оценки затрат памяти для максимального и минимального КТ Параметры базовой мультипликативной Затраты табличной схемы и МСС памяти Разновидность КТ Число Суммарный объем l log2 m_max log2p _l k таблиц памяти (в Мб) CT_max 1024 16 65 65 130 9165 1155, CT_max 2465 16 155 155 310 49755 6243, CT_min 1024 16 65 65 130 1040 153, CT_min 2462 16 155 155 310 2480 362, 40 №4- ЭЛЕКТРОНИКА инфо ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Заключение быточной модулярной арифметики / А.Ф. Чернявский, Основные результаты представленной разработки А.А. Коляда, Н.А. Коляда, Е.В. Шабинская: материалы по проблеме создания табличной реализационной базы Всерос. науч. конф. с элементами научной школы для моло мультипликативных МИМА-процедур типа Монтгомери дежи «Параллельная компьютерная алгебра», Ставрополь, состоят в нижеследующем. 1115 окт. 2010 г. / Ставрополь. гос. у-т // Нейрокомпьюте 1. На примере задачи расчета системных констант ры: разработка, применение. – 2010. № 9. С. 38.

мультипликативной МИМА-схемы Монтгомери, а также 7. Каленик, А.Н. Компьютерно-арифметическая и реа таблиц ИИ и расширения кодов показана высокая эф- лизационная база быстрых процедур умножения по боль фективность табличного индексного метода модульного шим модулям на основе модифицированной модулярной умножения. Он применим не только для вычисления схемы Монтгомери / А.Н. Каленик, А.А. Коляда, Н.А. Ко произведений, но и для получения мультипликативных ляда и др. // Электроника инфо. – 2012. – № 7. – С. 94 100.

инверсий ЦЧ по модулям МСС, причем с использованием 8. Чернявский, А.Ф. Интервально-индексная техно только аддитивных операций. Благодаря введенной из- логия расширения модулярного кода / А.Ф. Чернявский, быточности в базовые таблицы индексов и антииндексов, А.А. Коляда, Н.А. Коляда, Е.В. Шабинская // Электроника предложенная конфигурация метода позволяет исключить инфо. – 2010. – № 6. – С. 7277.

преобразования вычетов при переходе от одних оснований Abstract МСС к другим.

2. Создан комплекс методологических и алгоритми- Methods and computer algorithms of generating of the ческих средств, составляющий базовое математическое complete set of tables for base modular number systems (MNS) обеспечение таблично-сумматорной технологии реали- of the Montgomery's scheme for multiplication on the big зации мультипликативной МИМА-схемы Монтгомери. modules are devel-oped. In particular procedures of formation Применяемая технология дает гибкий инструментарий of tables for summation of deductions on bases MNS by an для разгрузки процесса умножения по большим модулям, accumulatively-tabular method, and also tables for calculation осуществляемого в реальном времени, от трудоемких of intervally-index characteristics and ex-pansion of codes are расчетов, которые могут быть выполнены предваритель- synthesized. The presented complex of methodological and но. Это приводит к значительному повышению скорости algorithmic means gives ample opportunities for unloading реализации криптографических преобразований рассма- of process of multiplication on the big modules, carried out in триваемого класса. real time from calculations which can be executed preliminary.

3. В целях оптимизации режима распределения вы- For generated complete sets of tables estimations of necessary числений по этапам предварительных расчетов и расчетов, memory are resulted.

Поступила в редакцию 12.11.2012 г.

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

Литература:

1. Kawamura, S. Cox-Rower architecture for fast parallel Montgomery multiplication / Shinichi Kawamura, Masanobu Koike, Fumihiko Sano, Atsushi Shimbo // Eurocrypt 2000, LNCS. – Vol. 1807. – Berlin, 2000. – P. 523–538.

2. Nozaki, H. Implementation of RSA Algorithm Based on RNS Montgomery Multiplication / H. Nozaki, M. Motoyama, A. Shimbo, S. Kawamura // Proc. Cryptographic Hardware and Embedded Sys-tems (CHES 2001). – Sept., 2001. – P. 364–376.

3. Bajard, J.-C. A Full RNS Implementation of RSA / J.-C. Bajard, L. Imbert // IEEE Trans. Comp. – 2004. – Vol. 53, № 6. – P. 769–774.

4. Lim, Z. An RNS-Enhanced microprocessor implementation of public key cryptography / Z. Lim, B.J. Phillips // Signals, Systems and Computers. – 2007. – ACSSC 2007. Conf. Rec. of the forte-first Asilomar Conf. – 4–7 nov., 2007. – P. 145–1434.

5. Коляда, А.А. Умножение по большим модулям с ис пользованием минимально избыточной модулярной схемы Монтгомери / А.А. Коляда, А.Ф. Чернявский // Информа тика. – 2010. – № 3. – С. 3148.

6. Чернявский, А.Ф. Умножение по большим модулям методом Монтгомери с применением минимально из №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо ПОСТРОЕНИЕ ОТКАЗОУСТОЙЧИВЫХ ПРОГРАММИРУЕМЫХ ЦИФРОВЫХ УСТРОЙСТВ НА ОСНОВЕ ПРОГРАММНЫХ И АППАРАТУРНО-ПРОГРАММНЫХ СРЕДСТВ САМОВОССТАНОВЛЕНИЯ УДК 681.518.54 Н.А. Коротаев, В.И. Попечиц, БГУ, г. Минск Аннотация когда последствия ошибки успели отразиться на таком Рассмотрены вопросы построения отказоустойчивых количестве информации, что восстановление путем по цифровых устройств на программируемых логических вторения отдельных операций невозможно или не имеет интегральных схемах (ПЛИС) на основе программных смысла. При этом контрольная точка используется в каче и аппаратурно-программных средств самовосстановления. стве исходной при условии, что все результаты в данной Приведена упрощенная структурная модель отказоустойчивой точке сохранены и не содержат ошибок. Повторение про СБИС на ПЛИС с аппаратурно-программными средствами граммы применяется тогда, когда в результате действий самовосстановления, предназначенная для исследования ошибок разрушено такое количество информации, что отказоустойчивости и выбора наиболее эффективной струк- восстановление путем повторного выполнения фраг туры. Дана оценка значения выхода годных СБИС на ПЛИС ментов программы невозможно или нецелесообразно.

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

Введение Средства дублирования представляют собой про Необходимость обеспечения отказоустойчивости циф- граммную избыточность, которая применяется на различ ровых устройств, построенных на новой элементной базе – ных уровнях: системном, модульном, операции данных программируемых логических интегральных схемах (ПЛИС) с целью восстановления работоспособности цифрового [1], обусловлена высокими требованиями к их быстродей- устройства при обнаружении ошибки, проявляющейся ствию, точности, надежности и безотказности [2, 3]. Одним в виде отказа. Самовосстановление на системном уровне из перспективных путей обеспечения отказоустойчивости организуется за счет избыточности процесса в мультипро цифровых устройств на ПЛИС является использование при граммной или мультипроцессорной среде (т.к. различные их построении встроенных средств самовосстановления. комбинации процессов создают различную среду для Обеспечение отказоустойчивости программируемых логи- системы). Избыточность на модульном уровне позволяет ческих интегральных схем на основе встроенных аппаратур- самовосстанавливать функционирование устройства пу ных средств самовосстановления рассмотрено в работе [4]. тем выполнения автоматической реконфигурации, которая Принципов построения отказоустойчивых программируемых состоит в замене отказавшего модуля его исправной копи цифровых устройств на основе программных и аппаратурно- ей и возобновлении вычислительного процесса, начиная программных средств самовосстановления в известных с определенной контрольной точки. Восстановление на работах авторами не найдено, поэтому в данной работе мы уровне операций осуществляется с помощью использо предлагаем использовать при построении отказоустойчивых вания средств защиты или избыточной информации, хра программируемых цифровых устройств программные или нимой в программе, или сохранения копии. Применение аппаратурно-программные средства самовосстановления. избыточности на уровне данных позволяет восстанавли вать данные, испорченные в результате действия ошибок, Построение отказоустойчивых и обеспечивать защиту целостности данных.

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

результат, если ошибка проявляется в виде сбоя, т.е. Таким образом, программные средства самовосста является случайной (такая ошибка исчезает в процессе новления, представляя собой программную избыточ восстановления). Если обнаружена ошибка в отдельной ность, увеличивают стоимость системы, т.к. требуют операции, то повторяется выполнение этой операции до дополнительных аппаратурных средств (память, про восстановления правильного вычислительного процесса. цессор и т.д.). Однако этот недостаток компенсируется Повторное выполнение фрагмента программы, т.е. возвра- тем, что рассматриваемые средства самовосстановления щение к контрольной точке осуществляется в том случае, существенно улучшают показатели функционирования 42 №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо и надежности СБИС ПЛИС, которые имеют тенденцию уменьшения стоимости аппарату ры и повышения ее быстродействия.

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

Эти средства подразделяются на статические и динамические.

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

Модель содержит: средства управления (СУ) процессом ляющим программным (аппаратурным) средством, либо с помощью программных (аппаратурных) управляющих самовосстановления;

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

объект самовосстановления (ОС), включающий работоспособ действий микропроцессоров).

Динамические аппаратурно-программные средства ные ПЛИС (РПЛИС), запасные ПЛИС (ЗПЛИС) и отказавшие самовосстановления применяются во время решения ПЛИС (ОПЛИС) с самопроверяемыми схемами встроенного основных задач, т.е., когда цифровое устройство при- контроля (ССВК);

средства реконфигурации (СР) с ССВК.

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

Неисправная ПЛИС средствами реконфигурации исключа количеством и сложностью логических схем и экономи ется из исходной структуры и заменяется на запасную ПЛИС, ческими показателями.

Самовосстанавливаемые цифровые устройства долж- а отказавшая ПЛИС включается в число ОПЛИС, подлежащих восстановлению. Средства самовосстановления возобновляют ны обладать следующими свойствами:

– обнаружение неисправности в момент времени ее правильное функционирование СБИС. При этом в случае вос первого проявления (данное свойство реализуется с по- становления отказавшей ПЛИС, она пополняет число ЗПЛИС.

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

– локализация неисправности с заданной глубиной структуры СБИС без замены ОПЛИС на ЗПЛИС. В этом (свойство реализуется путем применения встроенных случае наблюдается деградация системы, т.е. понижение ее вычислительных способностей. Однако деградация будет средств самотестирования);

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

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

аппаратурно-программными средствами).

№4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо Данная структурная модель позволяет предста вить различные структуры программируемого циф рового устройства с аппаратурно-программными средствами самовосстановления, моделирование которых на компьютере дает возможность срав нения надежностных характеристик исследуемых отказоустойчивых структур [4], оценки параметров различных топологий, определения оптимальных значений вносимой избыточности и выбора эф фективной структуры. Для оценки эффективности отказоустойчивой структуры важным является ана лиз достигаемого улучшения выхода годных СБИС ПЛИС в зависимости от определенных параметров.

Расчеты значения выхода годных (У) СБИС ПЛИС (типа ПЛМ – программируемая логическая матрица) в зависимости от среднего числа дефектов () на кри- Рисунок 3 – Графики выхода годных структур в зависимости от количества сталле, коэффициента группирования дефектов () резервных элементов и увеличения коэффициента группирования дефектов при постоянном среднем числе дефектов (=7) и числа резервных элементов (Кр), выполненные на основе формул (1–3) [5], позволили получить следующие результаты (рисунки 2, 3, 4):

(1) где – уровень потока дефектов (обычно прини мается =1);

Ув – выход восстановимой площади, в которой можно устранить до S дефектов, вы числяется по формуле (2):

(2) Унв – выход невосстановимой площади, в которой Рисунок 4 – Графики выхода годных структур в зависимости от количества число устранимых дефектов S=0, вычисляется резервных элементов и увеличения среднего числа дефектов при постоянном с помощью формулы (3): коэффициенте группирования дефектов (=2) (3) Графики (рисунок 3) показывают, что увеличение А – исходная площадь, Кр – дополнительная площадь (число коэффициента группирования дефектов при постоянном резервных элементов), Г – гамма-функция. среднем числе дефектов незначительно влияет на выход годных схем, а увеличение числа резервных эле ментов существенно увеличивает выход годных кристаллов.

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

Заключение Предложены программные и аппаратурно программные средства самовосстановления для обеспечения отказоустойчивости цифровых устройств на программируемых логических интегральных схемах. На основе анализа вычис ленных значений надежностных характеристик аппаратурных, программных и аппаратурно Рисунок 2 – График выхода годных структур в зависимости от среднего числа дефектов программных средств самовосстановления можно сделать вывод о том, что лучшими в обе График (рисунок 2) показывает, что увеличение сред- спечении отказоустойчивости работы СБИС на ПЛИС него числа дефектов в структуре СБИС ПЛИС уменьшает являются аппаратурно-программные средства самовос выход годных структур. становления.

44 №4- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЭЛЕКТРОНИКА инфо Приведена упрощенная структурная модель отказоу- систем высокого быстродействия / В.И. Виноградов // стойчивой СБИС на ПЛИС с аппаратурно-программными Электроника инфо. – 2007. – № 9. – С. 44–46.

средствами самовосстановления, моделирование которой на 3. Согомонян, Е.С. Самопроверяемые устройства и компьютере позволяет исследовать отказоустойчивость раз- отказоустойчивые системы / Е.С. Согомонян, Е.В. Слаба личных программируемых устройств и выбрать эффективную ков. – М.: Радио и связь, 1989. – 208 с.

структуру устройства. 4. Коротаев, Н.А. Обеспечение отказоустойчивости про Вычислены значения выхода годных СБИС на ПЛИС (типа граммируемых логических интегральных схем на основе ПЛМ) с аппаратурно-программными средствами самовосста- самовосстановления / Н.А. Коротаев, В.И. Попечиц // новления в зависимости от среднего числа дефектов, коэффи- Электроника инфо. – 2012. – № 1. – С. 99–102.

циента группирования дефектов и числа резервных элементов. 5. На, D.S. On the design of high – yield reconfigurable Аналогично могут быть вычислены и проанализирова- PLA’s / D.S. Ha, Y.P. Kumar // IEEE Trans. Comput. – 1990. – ны надежностные характеристики для программируемых Vol. ED – 39, № 4. – Р. 470–479.

цифровых устройств на ПЛИС других типов (программи Abstract руемых пользователем вентильных матриц, программируе Questions of creation of failure-safe digital devices on мых запоминающих устройств, программируемых матриц programmed logic integrated schemes (PLIS) on the basis of логики и сложных логических устройств).

program and equipment-program softwares of self-restoration are Актуальность и важность рассматриваемой задачи в обла considered. The simplified structural model of failure-safe SBIS сти построения отказоустойчивых программируемых цифро on PLIS with equipment-program softwares of self-restoration вых устройств на основе аппаратурно-программных средств intended for research of fault tolerance and a choice of the most самовосстановления требует дальнейших исследований.

effective structure is given. The assessment of value of an yield Литература: of suitable SBIS on PLIS with equipment-program softwares of 1. Соловьев, В.В. Проектирование цифровых систем self-restoration depending on average of defects, factor of grouping на основе программируемых логических интегральных of defects and number of reserve elements is given.

Поступила в редакцию 20.11.2012 г.

схем / В.В. Соловьев. – М.: Горячая линия – Телеком, 2001. – 636 с.

2. Виноградов, В.И. Микро- и наноэлектронные тех нологии компактных и масштабируемых компьютерных №4-

 




 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.