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

11-6

3212

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

Сотов Леонид Сергеевич

КОМБИНАТОРНЫЕ УСТРОЙСТВА ФОРМИРОВАНИЯ ИЗОМОРФНЫХ ПРЕДСТАВЛЕНИЙ ДАННЫХ, ПОВЫШАЮЩИЕ ПРОИЗВОДИТЕЛЬНОСТЬ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

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

Саратов-2011

Работа выполнена в НИУ ВПО «Саратовский государственный университет им. Н.Г. Чернышевского» и в ГОУ ВПО «Воронежский государственный технический университет».

Научный консультант: доктор технических наук, профессор

Антимиров Владимир Михайлович

Официальные оппоненты: доктор технических наук, профессор

Хетагуров Ярослав Афанасьевич

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

доктор физико-математических наук, профессор Безручко Борис Петрович

Ведущая организация: ОАО «Институт электронных управляющих машин

им. И.С. Брука», г. Москва

Защита состоится 22 декабря 2011 года в 13.00 часов на заседании диссертационного совета Д. 212.242.08 при ГОУ ВПО «Саратовский государственный технический университет» по адресу: 410054, г. Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, корп. 1, ауд. 319.

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

Автореферат размещён на сайте ВАК РФ 17 октября 2011 г. Автореферат разослан 18 ноября 2011 г.

Ученый секретарь л і

диссертационного совета /I ------A.A. Терентьев

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

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

С расширением области применения средств вычислительной техники все чаще возникают задачи, связанные с формированием изоморфных представлений или битовых перестановок машинного слова. В число таких задач входят обработка морфологии изображений, сортировка, моделирование и тестирование цифровых устройств, задачи биоинформатики, расчет контрольных сумм и коррекция ошибок, стеганография, сжатие и развертывание информации, выполнение криптографических примитивов, обработка сигналов в системах RPMA (random permutation-based multiple access) для передачи данных с использованием технологий расширения спектра, преобразование данных для передачи в текстовом формате и т.п. При этом затраты машинного времени на битовые преобразования данных составляют от 30 до 90% времени выполнения задач.

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

В работах R.B. Lee, Y. Hilewitz, Z. Shi, H. Liao, Z. Wu, Y. Xiao, С. Dimitrakopoulos, C. Mavrokefalidis и др. для ускорения осуществления битовых перестановок предлагается расширение архитектуры процессоров. В основе ряда предлагаемых решений лежат многоуровневые коммутационные сети, теория которых была заложена в работах Клоза, Бенеша и развита в работах ряда авторов: М. Н. Ackroyd, D. P. Agrawal, D. G. Cantor, F. К. Hwang, С. P. Kruskal и др. Для ускорения битовых перестановок R.B. Lee с соавторами были предложены новые инструкции bfly (Butterfly), ibfly (Inverse Butterfly), grp (Grop), разработаны устройства для их реализации. Последовательное использование инструкций bfly и ibfly даёт возможность осуществить любую перестановку, но её выполнение может занимать значительное время. Инструкция grp является альтернативным подходом, но существующие аппаратурные решения не обладают необходимым быстродействием и сложны.

Для увеличения производительности в платформах: IA-32 (Intel Architecture, 32-bit), AMD64 , Itanium ISA, POWER (Performance Optimization With Enhanced RISC), кроме указанных базовых инструкций, вводится поддержка специализированных команд для манипуляций с битами данных. Однако при этом теряется универсальность.

В ряде отмеченных ранее задач требуются перечисление и формирование

перестановок битов данных в случайном порядке. Для этого обычно используются последовательные, достаточно медленные алгоритмы Фишера-Йетса (Fisher - Yates), Саттоло (Saltóla).

В работах В. М. Курейчика, В. М. Глушань, J1. И. Щербакова, Г.С. Цира-муа, В.А. Богатырева, В.М. Полищука, В.И. Чабана, Р.В. Дмитришина и др. исследуются детерминированные и вероятностные формирователи перестановок, сочетаний и размещений. Однако предлагаемые устройства являются специализированными, их аппаратурная сложность составляет 0(пг) и быстро растет с увеличением л, где п - длина формируемого блока данных.

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

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

Тематика диссертационной работы соответствует научной программе кафедры общей физики Саратовского государственного университета им. Н. Г. Чернышевского и кафедры систем автоматизированного проектирования и информационных систем Воронежского государственного технического университета.

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

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

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

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

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

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

техники при решении задач перечисления и формирования в случайном порядке представлений данных.

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

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

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

Научная новизна работы:

1. На основе предложенных базовых преобразований, включающих упорядоченные и неупорядоченные разбиения блока данных длиной п, обоснованы принципы создания и разработаны алгоритмы структурного синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных. Показано, что при использовании разработанных устройств вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах ЯРМА, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма \J\JE преобразования данных для передачи в текстовом формате.

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

- параллельного формирования упорядоченных и неупорядоченных разбиений блоков данных длиной п=2к на т кластеров по 2" элементов с <7 = 21о£2(и)-и-1 уровнями преобразования и аппаратурной сложностью не более чем п ■ (1об2(п) -и/2-1) +1 логических элементов матрицы формирователя, где ¿-положительное целое число, а и=0,...,Ы;

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

- параллельного формирования перестановок с заданной структурой циклов, аппаратурной сложностью О (log2 (п)) и числом уровней преобразования q = 4log2(«);

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

<V);

- перечисления упорядоченных разбиений множества чисел (0,1,2,...,и-1) на блоки по 2" элементов, выполненных на базе матриц, формирующих упорядоченные разбиения входных данных длиной п, л/2, л/4, ..., 2и+| на два подмножества.

3. Обоснованы теоретические положения, включающие теоремы о композиции формирователей упорядоченных разбиений, о формировании сигналов управления переключателями, о декодировании битов управления, обеспечивающие создание универсального устройства преобразования форматов данных, выполняющего две новые инструкции bsn и grpm. Доказано, что разработанное устройство характеризуется более высокой скоростью выполнения и простотой аппаратурной реализации по сравнению с существующими решениями. На основании проведенных исследований разработаны варианты структурно-функциональной организации модулей, осуществляющих инструкции bsn, grpm, grp, рех. v, pdep. v, pex, pdep, rotate, shift.

4. Разработаны и обоснованы принципы построения высокопроизводительных вероятностных формирователей упорядоченных разбиений блоков данных длиной п с произвольной и заданной структурой циклов, характеризующиеся равномерным распределением вероятностей формируемых последовательностей. Разработанные вероятностные формирователи выполнены на базе предложенных устройств, осуществляющих упорядоченные и неупорядоченные разбиения. Доказано, что информационная энтропия вероятностного распределения выходных данных достигает значения более 50% от максимального за время, определяемое задержкой используемого формирователя, что обеспечивает увеличение производительности вычислительного устройства в п раз по сравнению с его производительностью при реализации алгоритмов Фишера-Йетса (Fisher - Yates) или Саттоло (Sattolo).

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

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

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

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

В диссертации показано, что общий вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз. Использование разработанных детерминированных и вероятностных формирователей упорядоченных разбиений блоков данных длиной п обеспечивает увеличение производительности вычислительного устройства примерно в п раз по сравнению с его производительностью при реализации алгоритмов Фишера-Йетса (Fisher - Yates), Сагголо (Sattolo).

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

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

Реализация и внедрение результатов работы.

Результаты работы внедрены в ОАО «Тантал», г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от нелицензионного копирования.

Материалы диссертации были использованы при разработке устройств высокоскоростного преобразования форматов данных, разработанных в НИР «Исследование нелинейных физических процессов в сложных системах, включая наноструктуры», шифр «Синдикат - 3», проводимой в ОМФ НИИЕН по заданию Федерального агентства по образованию.

Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс кафедры «Общая физика» Саратовского государственного университета и использованы при проведении занятий по дисциплинам «Моделирование полупроводниковых приборов и устройств на их основе» и «Технические средства защиты информации», в дипломном проектировании, при подготовке магистерских и двух кандидатских диссертаций. Материалы диссертации были использованы в учебно-методическом пособии «Имитационные модели физических систем с дискретным временем» (Изд-во Сарат. ун-та, 2009. ISBN 978-5-292-03916-7, 56 е.), в котором рассматриваются вопросы имитационного моделирования матричных преобразователей форматов данных.

Внедрения подтверждены соответствующими актами.

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

По результатам работы в ФГУ ФИПС зарегистрированы 3 программы, получены 12 патентов РФ на изобретения.

Основные положения и результаты, выносимые на защиту:

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

2. Универсальное устройство преобразования форматов данных на базе многоуровневой коммутационной сети baseline обеспечивает произвольное преобразование форматов данных с использованием двух инструкций bsn и выполнение специализированных инструкций манипуляций с битами данных grpm, grp, pex.v, pdep.v, pex, pdep, инструкций логического и циклического сдвига данных.

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

4. Формирователь импульсов случайной длительности и случайных бинарных кодов состоит только из цифровых элементов и при соотношениях частот задающих генераторов / 1/2/21/22,/^ удовлетворяющих выражениям

/,(/.+/-г) 1 1 1 ,

—--->2;—------ = —, имеет равномерную функцию распределе-

/¡1/22 /1/2: /2/21 ft

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

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

6. Разработанные 64-разрядные устройства преобразования форматов данных имеют время преобразования от 12f, до 301„ где t2 - максимальная задержка сигнала на одном инверторе, нагруженном на четыре входа, что обеспечивает увеличение производительности вычислительной системы от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA. биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи и тскстомом формате.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на Международной научной конференции «Проблемы управления, передачи и обработки информации» (АТМ-ТКИ-50) (Саратов, 2009), Международных симпозиумах «Надежность и качество» (Пенза 2006, 2007), Всероссийской научно-практической конференции «Проблемы защиты информации ограниченного доступа от утечки по техническим каналам» (Саратов, РАД «Тантал», 2003), Международной технической конференции «Перспективы развития электроники и вакуумной техники на период 2001-2006 гг.» (Саратов, ГНПП «Контакт», 2001), научно-технической конференции «Электронные приборы и устройства СВЧ» (Саратов, 2001), Международной научно-технической конференции «Физика и технические приложения волновых процессов» (Самара, 2001).

Основное содержание работы изложено в 22 публикациях в изданиях, рекомендованных ВАК РФ, а также в трудах международных конференций, симпозиумов, регистрации 3 программ для ЭВМ в реестре ФИПС. Оригинальность технических решений защищена 12 патентами РФ на изобретения. Всего по материалам диссертации опубликовано 57 работ.

Личный вклад автора. Основные результаты, представленные в диссертации, получены лично соискателем. Вклад автора был определяющим при выборе направлений, объектов и методов исследования, а также при написании статей, докладов и одиннадцати изобретений. Большинство работ написаны в соавторстве с первым научным консультантом Валерием Николаевичем Хариным], который принимал активное участие в обсуждении содержания статей и заявок на изобретения.

В работах, опубликованных в изданиях, рекомендованных ВАК РФ, в соавторстве и приведенных в конце автореферата, лично соискателем разработаны: в [1-3,6,7,11-13,15,22] - структура и принципы функционирования детерминированных и вероятностных устройств формирования изоморфных представлений данных; в [6,11,12] - методы структурного синтеза и модели устройств базовых преобразований форматов данных; в [7,15,21] - принципы построения и функционирования устройства преобразования форматов данных на основе параллельного формирователя упорядоченных разбиений блоков данных на два подмножества; в [17] - принципы построения и модели высокопроизводительных вероятностных формирователей разбиений с произвольной и заданной структурой циклов; в [5,9,10] - принципы построения, условия вычислительной непредсказуемости и модель формирователя импульсов случайной длительности и случайных бинарных кодов; в [14,16] - принципы построения, функционирования и модели встраиваемых в устройство детекторов режимов функционирования генераторов случайных сигналов.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, изложенных на 350 страницах, списка литературы из 255 наименований; содержит 117 рисунков, 38 таблиц.

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

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

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

Исследованы проблемы и возможности использования устройств, осуществляющих преобразования форматов данных для ускорения процедур сортировки, распознавания геометрических образов и символов на бинарных изображениях, обработки морфологии изображений, медианной фильтрации для устранения шумов на изображениях, операций преобразования представлений генетических последовательностей в биоинформатике, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, преобразования данных для передачи в текстовом формате, обработки сигналов в системах ЯРМА для передачи с использованием технологий расширения спектра и т.п. На основе проведенных исследований показано, что затраты машинного времени на преобразования форматов данных в исследованных задачах составляют от 30 до 90%. Наиболее критичной к скорости выполнения битовых манипуляций является обработка данных в системах ЯРМА. В этих системах передаваемые и принимаемые данные подвергаются обработке, связанной со случайными перестановками. Каждый элемент Хк входного набора данных X = (X1....,Хп) разделяется на Р блоков Хк = .....). Формируется случайная перестановка 7Г,

которая используется для преобразования набора входных данных X. Принимаемые данные подвергаются обратному преобразованию 7Г-1.

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

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

В табл. 1, 2 приведены данные, характеризующие объем вычислений, приходящихся на преобразование форматов данных при решении приведенных задач. В этих таблицах в процентах приведены результаты расчета отношения затрат машинного времени 7}, приходящихся на преобразование форматов данных, к общим затратам машинного времени Т на выполнение задач с использованием 64 разрядного процессора.

Детерминированные и вероятностные устройства преобразования форматов данных

Устройства, выполняющие инструкции 1 манипуляций с битами денных а I процессорах

Устройство опларатной поддержки формирования

случайных разбиений, перестановок и сочетаний элементоо данных

; Генераторы шуми и 1 | устроПстна контроля I режимом ик функції- I I оимроікінии I

ТТ~

: і S

I s І І

І! І

.... іііі* *|ЕІ

J

І

! 5

¡il, llfji

t!l

Si в

Iі fil

S s\l

іш hs

■

І ¥ X 5

I

^isl

il S ; S.' v

Iі s

ï1 g -e.

І ! і.!

і II

"ІЗ

" s , ¡il:

з

il

І! S*

ЯІ 5 ï

= I 4> T X

je X

І: I

S ;

_____ij

і

Л.

і e ! £■

I__'

і ï

> с

і «

1 S

Рис. 1. Структура устройств преобразования форматов данных

Результаты расчета Т//Т*100% в задаче сортировки N т-разрядных подслов данных

Таблица I

N 128 256 512 1024 2048 4096 8192 16384 32768 4194304

т=4 86 76 67 61 55 50 48 42 42 29

т=8 88 77 69 62 56 52 46 42 42 29

т=16 92 80 71 64 60 55 48 45 41 31

Таблица 2

Результаты расчета 7} /Т

Виды обработки информации Т//Т*т%

Медианная фильтрация изображений 78

Распознавание геометрических образов и символов на бинарных изображениях 50

Коррекция морфологии изображений 48

Упаковка и распаковка данных 60

LSB стеганография Прямое преобразование 45

Обратное преобразование 53

UUE (Uuencode) Прямое преобразование 59

Обратное преобразование 62

Биоинформатика (операция трансляции) 59

Формирование последовательностей перестановок в системах RPMA 91

Обработка данных в системах RPMA 90

Криптографический алгоритм DES 57

Криптографический алгоритм RC5 59

Защита файлов мультимедиа от нелицензионного копирования 91

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

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

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

В настоящем изложении принят ряд терминов, смысл которых интерпретируется следующим образом:

под «транспозицией» понимается отображение элемента Ь, вектора А, определенного в 1-й позиции исходной бинарной строки 5, в у'-ю позицию результирующей строки Д или обратное представление;

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

Будем обозначать Л5 - представление компонент бинарного вектора А в исходной строке и А° - их образ в результирующей строке.

Конкретный вид отображения (. А^ —> А^) определяется в декартовом произведении множеств А3 и А° : (Л5 X А°).

Теоретико-множественная модель представлений структурных элементов данных, определяющая прямое преобразование исходного формата, имеет вид Р ={А5,А°,АБ ХА°). (1)

Для обратного преобразования формата

Р"1 = {А°.А5,А° хЛ5}. (2)

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

- скорость преобразования;

- размер дескрипторов формата;

- число логических вентилей преобразователя.

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

1. В общем случае мощность множества форматов представлений вектора А = (*>,,й2,...,6л) определяется числом возможных перестановок его компонент и составляет и!. С увеличением п быстро возрастает размер дескрипторов формата, поэтому для сокращения ресурсов, отводимых под описание операции, необходимо использовать более простые форматирующие преобразования.

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

3. Произвольная перестановка компонент вектора Л является частным случаем упорядоченного разбиения, когда множество [bitb2,...,b„) разбивается на п непустых подмножеств.

Глава 3 посвящена разработке и обоснованию теоретических положений, обеспечивающих структурный синтез устройств базовых форматирующих преобразований. В главе исследованы способы построения ряда устройств последовательного и параллельного преобразования формата данных, имеющих аппаратурную сложность О(н), 0(n\og2n), 0(n(log2>i)2)> 0(н2). Проведена сравнительная оценка их производительности. Точные данные, характеризующие производительность предлагаемых устройств, получены на основе анализа имитационных моделей устройств и приведены в шестой главе.

Предложена и обоснована модель ВСТА1 устройства последовательного формирования упорядоченных разбиений. Устройство осуществляет упорядоченные разбиения компонент вектора данных А = (¿>,,6,,...,/>„) на 2к~и подмножеств мощности 2й, где п=2к, ы=0,1,2,...,£-1, к - положительное целое число. Аппаратурная сложность устройств последовательного действия составляет Тв = л/2" — 1. Для параллельной обработки в модели ВСТАР используется п устройств последовательного действия. Задержка выполнения преобразования определяется числом последовательно соединенных уровней дешифратора устройства и имеет значение 2(log2/t-w)/j, где - задержка на одном логическом инверторе, нагруженном на четыре входа. Аппаратурная сложность при этом составляет ТРБ = п(п/2и - 1) и быстро возрастает с увеличением п.

Для упрощения формирователя упорядоченных и неупорядоченных разбиений в диссертации предложены и обоснованы теоретические положения, обеспечивающие структурный синтез коммутационной матрицы, формирующей упорядоченные и неупорядоченные разбиения компонент вектора данных Л = (Л,,/>2,...,/>„) на 2fc-u подмножеств мощности 2" , где и=2*, м=0,1,2,...,А:-1. На базе данной матрицы разработана имитационная модель устройства ВСТАМ.

Соединения переключателей коммутационной матрицы устройства

ВСТАМ можно представить в виде орграфа G"t{S,T,V,D,A), где S = -

множество входных вершин, Т- множество промежуточных вершин входной

1 Uil Cluster Transposition Accelerator

части орграфа, У — множество промежуточных вершин выходной части орграфа, £> = (</,,<1г,...,<!„)- множество выходных вершин, а А - множество дуг орграфа. Согласно теореме о композиции переключателей для осуществления упорядоченных и неупорядоченных разбиений данных промежуточные вершины графа можно представить в виде матрицы с и/2 линиями (строками) и 21о%гп-и-1 уровнями (столбцами), причем ^2/1-1 уровень образован вершинами множества Г, а \0g2n-u уровень образован вершинами множества V. Каждая вершина Т1т е Т уровня т = (1,Аг - 2) входной части является смежной вершинам Ткт,и Тр,тн уровня т+\. Каждая вершина У1т е V уровня т = (\,к — и-\) выходной части является смежной вершинам Уи,т+и Ур.т-и уровня /и+1. Причем на отношение смежности накладываются ограничения

2*--1 ¡шГ-^г! +и < 2к~т~1 ¡тГ-^т +1

1 2*~т~' ) 12

2*~m_l int

(i+2k~m~l -l^modw^

2k-m-1

/

-\<p<2

k-m-1

(i + 2*"m_1 -l^modn^

mt .

4 v

k-m-1

2

\

+ 1

(3)

где int - функция выделения целой части, (I+ 2 т -ljmodw - операция вы-

i + 2k'm'] -1

числения остатка от частного-.

п

Промежуточные вершины интерпретируются как переключатели коммутационной матрицы. Каждый переключатель имеет два входа, два выхода данных и бинарный вход управляющего кода с е {0,1}. Данные на входах переставляются местами (при значении управляющего кода £7=1), либо не переставляются (при с=0). Множество ребер графа описывает соединения между переключателями. Коды управления переключателями являются битовыми атрибутами промежуточных вершин орграфа. В зависимости от их значений формируются разрешенные пути прохождения вершин графа.

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

На рис. 2 приведена диаграмма орграфа одного из вариантов коммутационной матрицы устройства ЕСТ AM для случая п= 16, «= 1. Вершины входной части орграфа образуют уровни F/, F?t F3, вершины выходной части орграфа образуют уровни С/, G2, G}.

Число переключателей коммутационной матрицы устройства ВСТАМ составляет и - (log2(/i) — м/2 — 1) +1 и растет практически линейно с ростом и, что делает технически возможной реализацию функционального формирователя разбиений при больших значениях п. Быстродействие устройства определяется числом последовательно соединенных уровней коммутационной матрицы устройства и составляет не более 2(2log2n-i<-l){.„ так как задержка на уровне составляет 2i3.

Рис. 2. Диаграмма орграфа одного из вариантов матрицы формирователя разбиений

для случая л=16, и= 1

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

Для ускорения настройки устройства формирования упорядоченных разбиений при смене дескрипторов формата в диссертации предложен способ структурного синтеза формирователей перестановок и упорядоченных разбиений на основе топологии сортирующей сети. Если дескриптор формата задан в виде перестановки л(\2,...,;>), а Р - преобразование, осуществляемое сортирующей сетью, при подаче на ее входы перестановки тг(1,2,...,«), то справедливо выражение: ;г(1,2,...,и) = />~'(1,2,3,...,и), где Р"1 - преобразование, обратное Р. Для выполнения обратного преобразования у преобразователя, реализующего перестановку Р достаточно поменять выходы и входы. Поэтому, если на сортирующую сеть Р наложить сеть Р'1с аналогичной топологией, у которой входы заменены на выходы, получим устройство, реализующее заданную перестановку я-(0,1,2,...,и). Имитационная модель разработанного устройства получила название ВСТАБ. В диссертации показано, что с использованием топологии сортирующей среды нетрудно построить преобразователь, осуществляющий обратное преобразование л--1 (0,1,2,...,«). Аппаратурная сложность

предложенного устройства составляет о|ик^2 л)"), что хуже, чем у модели ВСТАМ. При этом скорость настройки переключателей коммутационной матрицы значительно выше и определяется числом последовательно соединенных

компараторов используемой сортирующей сети. Число двоичных разрядов чисел, сравниваемых компараторами, составляет log2w. При использовании компараторов с пирамидальной структурой оценка задержки выполнения преобразований составляет 4(log2n)2f3, где í3 - задержка на одном логическом инверторе, нагруженном на четыре входа. Недостатком устройства BCTAS является низкая производительность осуществления фиксированных преобразований форматов данных, время выполнения которых в устройствах ВСТАМ составляет не более (41og2n) tj.

В связи с этим на базе устройства ВСТАМ, формирующего упорядоченные разбиения входных данных на два подмножества, были разработаны принципы построения и функционирования универсального устройства, осуществляющего статические и динамические преобразования форматов данных. Разработанные принципы включают теоремы о композиции формирователей упорядоченных разбиений, о формировании сигналов управления переключателями формирователей, о декодировании битов управления. Теоремы о композиции формирователей упорядоченных разбиений обеспечивает ряд способов структурного синтеза матрицы устройства. На основе теорем о формировании сигналов управления переключателями матрицы и о декодировании битов управления показано, что наиболее перспективным решением является коммутационная матрица на базе сети baseline, которая удовлетворяет уравнению (3). В результате было разработано устройство, осуществляющее две новые инструкции: bsn r\=r2, ar.b\, ar.bi, аг.Ьъ и grpm r¡ =г2, Гц, где г2 - регистр входных данных, Г\ - регистр выходных данных, ar.b\, ar.b2, ar.by, /-3- регистры, хранящие код управления перестановкой.

На рис. 3 приведена диаграмма, иллюстрирующая преобразования, осуществляемые с использованием инструкций bsn, grp, grpm для случая п=8, где в верхней части рисунков расположены регистр управляющих кодов г3 и регистр входных данных гъ а в нижней части рисунков изображен регистр выходных данных г|. Отличие инструкции grpm от grp заключается в том, что при использовании инструкции grp сгруппированные данные сохраняют свой первичный порядок, а при использовании инструкции grpm порядок данных, выбранных с использованием битов управления с низким логическим уровнем, меняется на обратный. Инструкция bsn предназначена для статического преобразования форматов данных, а инструкция grpm - для динамического, так как настройка коммутационной матрицы при использовании этой инструкции выполняется значительно быстрее с использованием разработанных средств аппаратурной поддержки. В диссертации показано, что произвольное преобразование форматов данных формируется с использованием последовательно log2n инструкций grpm или двух инструкций bsn, которые осуществляют преобразование входной и выходной частей коммутационной матрицы модели ВСТАМ.

bsn n =n,or. hi.cir.b:,ar./»

Я'Р '■!=)■:, n

grpm ri=r:,n

ri \a\b\c\cl\i'\i \u\h~' r, | в 11 i | n | i | i | о | о |о | r.< f»]T| ГЩХШа! ° i

ir.b, ТинПа Q У У r: n

) nlll/l {\{\j

HyMcpuiiiiM pajpN/iOH

fWl г, Й1Й7Ш1Е

0-7

0-7

рсгшлра - ' ' 0-7

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

grpm, grp

На рис. 4 представлена структурно-функциональная схема разработанного устройства GRPM-64, выполняющего преобразования данных длиной п=64 бит с использованием инструкций grpm и bsn. Коммутационная матрица устройства включает 6 уровней преобразования bsnrbsn6. В зависимости выполняемой инструкции bsn или grpm блок FP осуществляет одну из двух фиксированных перестановок.

I Ш32_

аг.Ь

! ШзТ"'

Ж

bsm

"Ш5Г

: Ш32

I

bsm bsm

Jffij6(

-i

4ШВ

ar.bt j------

! "Ш32 I

[Ш32

_ J_"

Г ar.bi j

! CJZL...

: TS32

bsn bsm

bsm

~f'P

"1Г

Декодеру Ш64| /5 ;

v 1ИВ

j 32Ш1

-I ып/ !

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

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

Предложены и обоснованы способы синтеза сумматоров декодера. Согласно одному способу сумматоры образуют пирамидальную структуру. Число сумматоров в декодере определяется выражением 3/2«. Задержка преобразования составляет 2rslog2w, где ts - задержка, создаваемая сумматором. Исследована возможность использования в декодере структур параллельных префиксных сумматоров Ладнера-Фишера (Ladner-Fischer), Кога-Стоуна (Kogge-Stone), Брента-Кунга (Brent-Kung), Хана-Карлсона (Han-Carlson). С их использованием удалось сократить общую задержку выполнения инструкции grpm до 28 задержек на инверторе, нагруженном на четыре входа.

Устройство GRPM-64 позволило объединить преимущества быстрого выполнения статических преобразований форматов данных с использованием модели ВСТАМ и обеспечения динамического преобразования форматов данных в модели BCTAS. При этом аппаратурная сложность устройства составляет 0(/jlog2").

Доказаны следующие утверждения:

- любые параллельные инструкции рех выделения и группировки с сохранением начального порядка бит данных могут быть осуществлены с использованием наложения битовой маски на входные данные и однократного преобразования упорядоченного разбиения входных данных на два подмножества с использованием устройства ВСТАМ-,

- любые параллельные инструкции deposit размещения бит данных в заданных позициях машинного слова могут быть осуществлены с использованием однократного преобразования, обратного упорядоченному разбиению входных данных, на два подмножества с использованием устройства ВСТАМ и наложения битовой маски на выходные данные;

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

- инструкции логического сдвига могут быть осуществлены путем однократного преобразования упорядоченного разбиения входных данных на дна подмножества с использованием устройства ВСТАМ.

На основании проведенных исследований разработаны варианты структурно-функциональной организации и модели устройств, осуществляющих инструкции bsn, grpm, grp, pex.v, pdep.v, рех, pdep, rotate, shift. Показано, что для реализации перечисленных инструкций устройство ВСТАМ следует выполнять на базе многоуровневой коммутационной сети baseline. Возможно также использование любых коммутационных сетей, изоморфных baseline.

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

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

(к к к с^с.,2 ...С^5), где у - количество различных длин циклов в циклической записи перестановки, с, длина /'-го цикла, а количество циклов длины с,, входящих в перестановку. В диссертации показано, что для формирования перестановки с заданной цикловой структурой перестановки тт.тт'1 можно представить в виде произведения двух перестановок я = лгпс, тт'1 = тт"1?:"1, где ттг, тт'1 - прямая и обратная перестановки, формирующие неупорядоченные разбиения входных данных на подмножества С],..,С„ тт^п'1 - перестановки с фиксированной неподвижной точкой, которые осуществляют полноцикловые преобразования подмножеств .....•

На основе проведенных исследований в данной главе представлены результаты разработки аппаратурных формирователей перестановок с заданной цикловой структурой. Синтез матриц формирователей перестановок я,., л"1, яг,я~г осуществлен с использованием переключателей, осуществляющих прямое и обратное преобразования одновременно. Показано, что аппаратурная сложность разработанных устройств составляет 0(л1о£2»)> а задержка формирования перестановки с заданной цикловой структурой не превосходит (8^2«)/,, что вдвое больше, чем в моделях ВСТАМ, так как в данных устройствах последовательно выполняются прямая и обратная перестановки. Для увеличения производительности формирования перестановок с заданной цикловой структурой предложено использовать устройства ВСТАР, имеющие аппаратурную сложность 0(и2). Разработаны и обоснованы модели устройств, осуществляющих прямые и обратные перестановки под управлением одинаковых кодов. Показано, что в этом случае время формирования перестановки составляет не более (2к^2п)Л„ так как задержка определяется временем работы дешифраторов, одновременно используемых для формирования прямой и обратной перестановок.

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

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

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

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

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

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

На рис. 5 приведена структурная схема вероятностного формирователя упорядоченных разбиений, для случая и=16, м=0. Устройство состоит из блока регистров данных и многоуровневой коммутационной сети baseline, где D\ - Ц, -параллельные q разрядные входы блока регистра данных и выходы коммутационной матрицы; Q\ - Q„- параллельные q разрядные выходы блока регистров данных и выходы формирователя; S\ - Sn- q разрядные входы коммутационной матрицы; С\ - Ст - бинарные входы формирователя для подачи управляющих сигналов от внешних источников случайных сигналов; А\ - А,, - начальная строка q разрядных данных, загружаемая в блок регистров данных; Vt j - переключатели коммутационной матрицы; РЕ - бинарный вход управления последовательной и параллельной записью данных; S - последовательный q разрядный вход блока регистров данных для записи элементов начальном строки данных А, - А„; elk - вход тактовых импульсов.

Рис. 5. Структурная схема стохастического формирователя дескрипторов формата упорядоченных разбиений для случая п= 1 б, и=О

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

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

(ПгПг-.П,),,, ■■чЧ,)\р.}1> где матрица |]р,у|[ оказывается дважды стохасти-

ческой с отсутствием нулевых элементов, что приводит к быстрой экспоненциальной сходимости последовательности (т}1,т12...,т}г)1 к равновероятному распределению г], =г}2 =... = 77,.Основными компонентами разработанных вероятностных устройств являются физические генераторы случайных сигналов (ГСС). В качестве источников случайных сигналов предложено использовать генераторы динамического хаоса. В диссертации сформулированы и обоснованы условия непредсказуемости используемых генераторов. Предложена модель хаотического формирователя случайных чисел и временных интервалов, удовлетворяющего сформулированным условиям. Предложенный в диссертации метод построения ГСС обеспечивает построение формирователей импульсов случайной длительности и случайных бинарных кодов с равномерной функцией распределения вероятностей, устойчивых к внешним воздействиям. Возможность исполнения разработанных ГСС в виде интегральной микросхемы с использованием только стандартных цифровых элементов позволяет без дополнительных исследований использовать при их производстве различные технологические процессы, а также реализовать ГСС на ПЛИС. Перечисленные свойства являются очень важными для практических применений.

Согласно модели функционирования ГСС по запросу системы в некоторые моменты времени т, на основе внутреннего состояния Х(Т:) генератора формируется цифровой сигнал . Система определяет состояние Х(Т.) с погрешностью 5, таким образом, (£>£)г генерируется на основе любого значения X из «У-окрестности Х(Т.) в' фазовом пространстве системы <£}. Цифровой сигнал {£>5)г генерируется системой по

известному наблюдателю алгоритму 5 для УХ(Т.)е {Х)'1,3(Х(Т<))-> {ОЯ}, . ГСС будет непредсказуемым, если наблюдатель не сможет определить его состояние с погрешностью, не превышающей <5 в требуемые моменты времени Т, даже в том случае, если некоторые значения из последовательности Х(Т,) ему известны.

Утверждение. Генератор динамического хаоса вычислительно непредсказуем, если погрешность определения его состояния Хп экспоненциально возрастает при моделировании в прямом и обратном времени.

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

Генератор динамического хаоса на базе отображения Х„+1 = Р(ХП) вычислительно непредсказуем, если в спектре собственных значений матрицы [.4 (х } х [а (х „) ] присутствуют два собственных значения Хи . X ъ . одно из которых Х\, > ' > а другое Хг, < 1 < '"Дс 1л(А'„)] - матрица Якоби для Р(ХГ).

Генератор динамического хаоса на базе потоковой системы — = Р(Х) вычислительно непредсказуем, если в каждой точке фазовой траектории ГСС в спектре собственных значений х, матрицы (у] = [л]г[/4] присутствуют положительные и отрицательные значения, где [а]- матрица Якоби Р(Х).

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

Выход

mod(2*),

(4)

Рис. 6. Структурно-функциональная схема генератора случайных временных интервалов

Его работа описывается двухмерным отображением

Г/ /1

/п'Аг

4/21 fnJ

где - частоты задающих генераторов в, С11, в 12, 021, 022. Таким образом, частоты задающих генераторов являются параметрами управления в модели предложенного формирователя.

■ц*1 т

л+1 /

И

Для обеспечения вычислительной непредсказуемости необходимо, чтобы отображение (4) было гиперболического типа, что выполняется при

/,(/;,+/„)i___!_=j_

/11/22 /11/22 f'.ifi\ ft

Формирователь состоит из шести ^-разрядных двоичных счетчиков: АН, А12, А21, А22, X, Y и пяти задающих генераторов. В состав формирователя входит также логический блок ВС, пропускающий импульсы от соответствующих генераторов Gil, G21 при обнулении счетчиков А12 и А22 соответственно. Данную схему можно реализовать только на цифровых элементах, используя в качестве G, Gil, G12, G21, G22 быстродействующие автогенераторы, частота колебаний которых определяется инерционными свойствами используемых логических элементов.

В начальный момент времени счетчики X, Y обнуляются, в All, А21 заносится начальное значение к0, а в счетчики А12, А22 заносится значение щ. После этого тактовые импульсы от генераторов G, G12, G22 подаются на соответствующие счетчики X, Y,A12, А22, причем А12, А22 осуществляют реверсивный счет, а Хп+1, Yn+1 - прямой. После обнуления счетчиков А12, А22, тактовые импульсы от генераторов G11, G21 через логические схемы Б1 поступают на счетчики All, А21, осуществляющие реверсивный счет. Цикл завершается в момент обнуления этих счетчиков. Для осуществления следующего цикла содержимое счетчиков X, Y записывается в А11, А21 и А12, А22 соответственно.

Учитывая флуктуации частоты колебаний генераторов G, G11, G12, G21, G22, числа кп,тп являются случайными величинами,

В качестве задающих генераторов G, Gil, G12, G21, G22 предложено использовать разработанные в пятой главе магнитоэлектронные генераторы, достоинствами которых являются широкая спектральная полоса генерируемых колебаний, возможность исполнения в интегральном виде, широкий диапазон рабочих частот. На рис. 7 приведена микрофотография разработанного магнито-электронного генератора, а на рис. 8 - спектр генерируемых им колебаний. Ширина спектральной линии по уровню -ЗдБ составляет около 5 кГц.

Рис. 7. Микрофотография магииттлск- Рис. 8. Спектр сигнала

тронного генератора в квазнмоноли шпм магннтоэлектронного генератора

исполнении

На рис. 9 представлена микрофотография кристалла гибридной микросхемы формирователя импульсов случайной длительности. Кристалл изготовлен на фабрике ЭИТегга (Малайзия) с использованием технологического процесса КМОП 0,18 мкм. Размеры кристалла: 3,021 х 1,809 мм.

Рис. 9. Микрофотография кристалла ГСС

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

Структурно-функциональная схема спектрального детектора режимов приведена на рис. 10, где ГСС - контролируемый генератор случайных сигналов, ГКЧ -генератор качающейся частоты, СМ - смеситель, ФПЧ - фильтр промежуточной частоты, У О - усилитель-ограничитель, Д - амплитудный детектор, ИУ - интегрирующий усилитель, ИНД - устройство индикации и сигнализации.

1 I "..........! ! "" '

I гсс см | »; фмч \ - У о |-

'Г

I

I

!

имя

Рис. 10. Структурно-функциональная схема спектрального детектора хаотических колебаний

На выходе интегрирующего усилителя будет сигнал:

и,1У =-!-Т\АпКшКфтКуоКаио\н(Цг, Н<*)тойпрр, ¿1 0

где Дм>« - - полоса пропускания ФПЧ, м>р = м>1р - - полоса контролируемых детектором частот, Кси - коэффициент преобразования смесителя. КФП,ч - модуль коэффициента передачи ФПЧ, Кд - коэффициент передачи

25

детектора, Куо коэффициент передачи усилителя-ограничителя, H(w)~ Фурье образ сигнала ГСС U(t), U0 - амплитуда сигнала гетеродина.

Блок УО ограничивает амплитуду сигналов и

^AwKCMK<bmKyoKaU0\H(wlp +(ar/)modvi';,)|= Ау™, и в случае случайных

колебаний на выходе интегрирующего усилителя будет сигнал U^y = Ауд . В случае периодических колебаний с числом гармоник N, попадающих в

ч __п A™*NAw ^ Aw ,

диапазон (w2 w, ): и ИУ = —-. Так как-« 1, при смене режима кор р

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

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

Если случайный сигнал формируется динамической системой, то фазовая траектория X(t) будет устойчивой по Пуассону в том случае, если обладает свойством возвращаться в сколь угодно малую окрестность каждой своей точки бесконечное число раз. Возврат Пуанкаре - это возврат траектории в е-окрестностъ произвольно выбранной на ней начальной точки. Пусть Т], Т2...Т„ последовательность периодов возврата. Если колебания периодические, то Г, = Т2 = ... = Тп = Т. Если колебания квазипериодические, то =Т2 = ... -Тп= Т(е) - результат, аналогичный случаю периодических колебаний, но время возврата будет возрастать с уменьшением е: lim Т{е) = <х>. В

г-»0

случае хаотических колебаний Tt,Т2...Тп - случайные величины с некоторым распределением. В диссертации разработаны методика построения и модель устройства, контролирующего значения Ti,T1...Tn.

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

На базе предложенных в диссертации методов построения генераторов случайных сигналов и стохастических комбинаторных формирователей в ОАО «Тантал» была разработан многофункциональный программируемый формирователь случайных последовательностей и сигналов с контролем режима функционирования. Устройство предназначено для использования в системах защиты информации, вычислительных методах Монте-Карло, процедурах тестирования аппаратуры и т.п. Отличительными особенностями разработанных фор-

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

В классе 16-разрядных архитектур был разработан модуль формирования упорядоченных разбиений, обеспечивающий приемлемое сочетание функциональности и сложности реализации. Модуль был реализован на базе FPGA (field-programmable gate array) серии APEX 20К фирмы Altera с использованием платы APEX PCI Development board.

На рис. 11 представлена фотография модуля ВСТАМ16X256, предназначенного для формирования упорядоченных разбиений блоков данных длиной 256 бит. Задержка преобразования данных составляет около 10 не, что обеспечивает пиковую скорость преобразования до 25,6 Гб/с. При этом производительность устройства определяется пропускной способностью используемой шины PCI-X. Данный формирователь использовался для защиты файлов изображений от несанкционированного копирования.

Рис. 11. Внешний вид модуля ВСТАМ16X256

Результаты исследований, полученные в диссертации, позволили создать новый высокоскоростной и эффективный в аппаратурном исполнении модуль GRPM-64B для манипуляций с битами данных, осуществляющий инструкций grp, pex.v,pdep.v, рех, pdep, shift, rotate и новые инструкции bsn vi grpm. Используя две инструкции bsn, можно выполнить произвольную перестановку входных данных. Время выполнения инструкций составляло от 12 до 22í, без организации конвейерной обработки.

В шестой главе рассмотрен ряд часто решаемых средствами вычислительной техники задач, на которых показана эффективность использования разработанного модуля. Ускорение выполнения алгоритмов обусловлено параллельной обработкой нескольких групп бит данных, находящихся в регистре процессора. Кроме этого, инструкции grp и grpm оказываются очень эффективными в случаях, когда результат перестановки зависит от входных данных. При проведении исследований использовалась система моделирования SimpleScalar. Задержка выполнения инструкций grpm, pex.v, pdep.v составляла два цикла процессора. Остальные параметры Simplescalar были аналогичны параметрам, используемым Y. Hilewitz и R. Lee.

В таблица 3 представлены результаты ускорения сортировки 64 элементов данных различного размера с использованием модели GRPM-64B. При этом сортируемые элементы представлялись четырехразрядными, восьмиразрядными и шестнадцатиразрядными подсловами. Минимальное ускорение по сравнению с алгоритмом сортировки слиянием составляет более 12 раз.

Таблица З

Ускорение сортировки 64 полслов данных с использованием модели GRPM-64В

Размер подслов, бит 4 8 16

Пузырьковая сортировка 408.3 128.9 43.7

Сортировка выбором 272.7 86.1 29.2

Сортировка слиянием 104.4 32.8 12.1

При сортировке большого числа элементов использование инструкций %грт также приводит к существенному ускорению. При этом для сортировки больших фрагментов могут использоваться стандартные алгоритмы сортировки слиянием, а небольшие фрагменты сортируются с использованием инструкций &грт. В таблица 4 представлены результаты увеличения скорости сортировки слиянием строки данных длиной N подслов данных размером т бит с использованием модели йЯРМ-64В.

Таблица 4

Ускорение сортировки jV m-разрядных подслов данных с использованием модели GRPM- 64 В

N 128 256 512 1024 2048 4096 8192 16384 32768 4194304

т=4 6,9 4,0 3,0 2,5 2,2 2,0 1,9 1.7 1,7 1,4

т=8 6,8 3,9 3,0 2,5 2,2 2,0 1,8 1,7 1,7 1,4

т-16 6,4 3,8 2,9 2,4 2,2 2,0 1,8 1,7 1,6 1,4

С увеличением N эффективность использования инструкций grpm уменьшается, так как все большая часть программы выполняется с использованием стандартной процедуры сортировки слиянием. Тем не менее при длине сортируемой последовательности более четырех миллионов увеличение производительности за счет использования инструкции grpm составляет 1,4 раза.

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

Таблица 5

Ускорение выполнения алгоритмов с использованием модели GRPM-64В

Виды обработки информации Ускорение работы алгоритма, разы

Медианная фильтрация изображений 4,5

Распознавание геометрических образов и символов на бинарных изображениях 2,0

Коррекция морфологии изображений 1,9

Упаковка и распаковка данных 2,5

LSB стеганография Прямое преобразование 1.8

Обратное преобразование 2,1

UUE (Uuencode) Прямое преобразование 2,4

Обратное преобразование 2,6

Биоинформатика (операция трансляции) 2,4

Формирование последовательностей перестановок в системах RPMA 10,7

Обработка данных в системах RPMA 9,5

Криптографический алгоритм DES 2,4

Алгоритм DES, генерация ключей 15,5

Криптографический алгоритм RC5 2,3

Защита файлов мультимедиа от нелицензионного копирования 10,2

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

Для использования в системах управления передатчиками помех KB, УКВ и ДЦВ диапазонов серии «Кентавр» и аналогичных, с использованием разработанной в диссертации методики были разработаны устройства для контроля режимов функционирования генераторов случайных сигналов. Использование данного устройства в составе контроллеров генераторов помех является крайне важным, т.к. позволяет исключить возможность возникновения последствий, связанных с поломкой и изменением режимов функционирования используемых генераторов.

Результаты, полученные в диссертации, обеспечили возможность реализации в ОАО «Тантал» проекта расширения архитектуры RISC процессора для ускорения выполнения преобразований на уровне битов и подслов данных. Данный процессор используется, в частности, для обработки данных в системе RPMA. Разработанная теория структурного синтеза формирователей упорядоченных разбиений и устройств управления ими обеспечила возможность построения универсального модуля для реализации инструкций grp и инструкций, аналогичных bfly, ibfly. Причем две инструкции bfly и ibfly заменены одной bsn. Предложенное решение апробировалось на базе процессора OpenRISC 1 ООО и в настоящее время является наиболее эффективным с точки зрения быстродействия и простоты аппаратурного исполнения.

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

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

При проведении исследований получены следующие научные и практические результаты:

1. На основе сформулированных в диссертации положений использования упорядоченных разбиений в качестве базовых преобразований входных данных разработана и обоснована структура комплекса новых детерминированных и вероятностных устройств формирования изоморфных представлений данных. Доказано, что использование разработанных устройств приводит к увеличению производительности вычислительной системы на базе 64 разрядного процессора от 2 до 10 раз для задач сортировки, распознавания геометрических образов и символов на бинарных изображениях, обработки морфологии изображений, медианной фильтрации для устранения шумов на изображениях, операций преобразования представлений генетических последовательностей в биоинформатике, обработки данных в системах RPMA, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.

2. Разработаны теоретические положения, обеспечивающие структурный синтез и принципы функционирования устройств, формирующих упорядоченные разбиения входных слов данных длиной п на подмножества с произвольной и заданной структурой циклов. На базе многоуровневых коммутационных и сортирующих сетей и матричных коммутаторов предложены устройства, имеющие аппаратурную сложность О(и), 0(«log2«), 0(/í(log2«)2), 0(/j2). Проведена сравнительная оценка их производительности и разработаны рекомендации к применению.

3. Разработанные положения структурного синтеза формирователей упорядоченных разбиений и блоков управления ими обеспечили создание универсального устройства для поддержки новых инструкций bsn и grpm, осуществляющих динамическое и статическое преобразования форматов данных. Показана эффективность предложенного решения для осуществления манипуляций с битами и полсловами данных, реализуемых с использованием специализированных инструкций, таких как pex.v, pdep.v, рех, pdep, shift, rotate. Проведенный сравнительный анализ свидетельствует о том, что предложенное устройство в настоящее время является наиболее эффективным с точки зрения производительности и простоты аппаратурной реализации.

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

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

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

7. Разработанные IP блоки, методики расчета и синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных в ЭВМ внедрены в ОАО «Тантал», г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от нелицензионного копирования. Научные основы создания, принципы функционирования, математические и имитационные модели комбинаторных устройств формирования изоморфных представлений данных в ЭВМ внедрены при организации обучения специалистов студентов НИУ ВПО «Саратовский государственный университет им. Н.Г. Чернышевского». По результатам работы в ФГУ ФИПС зарегистрированы 3 программы и получены 12 патентов РФ на изобретения.

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

Публикации в изданиях, рекомендованных ВАК РФ

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

2. Сотов Л.С. О формировании доверенной среды серверных систем управления базами данных / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2008. №3. С. 23-27.

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

4. Сотов Л.С. Экспериментальные исследования гибридного интегрального магнитоуправляемого генератора / А.Л. Хвалин, Л.С. Сотов, C.B. Овчинников, В.П. Кобякин // Приборы и системы. Управление, контроль, диагностика. 2009. №11. С. 42-44.

5. Сотов Л.С. Использование генераторов динамического хаоса в системах информационной безопасности / Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2009. №2. С. 32-37.

6. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2009. Т. 7. № 10. С. 78-85.

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

8. Сотов Л.С. Сложная динамика генераторов на диоде Ганна с низкочастотным контуром / Г.Н. Коростелев, Л.С. Сотов // Изв. вузов. Радиотехника и электроника. 1989. Т. 34. №9. С. 1925-1929.

9. Сотов Л.С. Цифровой генератор подкачки энтропии на базе отображения Арнольда / Л.С. Сотов, В.Н. Харин // Известия вузов. Прикладная нелинейная динамика. 2009. Т. 17. № 6. С. 57-66.

10.Сотов Л.С. Квазишумовые режимы магнитоэлектронных генераторов / А.Л. Хвалин, Л.С. Сотов // Вопросы электромеханики. 2009. Т. 113. №6. С. 55-59.

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

12.Сотов Л.С. Модель инволютивного транспозиционного преобразователя / Л.С. Сотов, A.A. Солопов, A.B. Фарафонова // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С. 34-46.

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

14.Сотов Л.С. Детекторы режимов функционирования генераторов случайных сигналов / Л.С. Сотов, В.Н. Харин, A.JI. Хвалин //Автоматика и телемеханика. 2010. № 5. С. 166-170.

15. Сотов Л.С. Формирователи перестановок с управляемой цикловой структурой / Л. С. Сотов // Гетеромагнитная микроэлектроника. 2011. Вып. 9. С. 43-55.

16.Сотов Л.С. Встроенные средства контроля генераторов случайных сигналов / Л.С. Сотов, В.Н. Харин, А.Л. Хвалин // Приборы и системы. Управление, контроль, диагностика. 2010. №7. С. 30-33.

17.Сотов Л.С. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии / A.B. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С. 57-71.

18.Сотов Л. С. Комбинаторная модель функционального формирователя разбиений бинарного множества / Л. С. Сотов // Информационные технологии. 2010. №10. С. 46-52.

19.Сотов Л.С. Расчёт характеристик интегрального магнитоуправляемого генератора / А.Л. Хвалин, Л.С. Сотов, A.B. Васильев // Приборы и системы. Управление, контроль, диагностика. 2010. № 11. С. 47-49.

20.Сотов Л.С. Аппаратные устройства формирования прямых и обратных перестановок данных / Л. С. Сотов // Гетеромагнитная микроэлектроника. 2011. Вып. 9. С. 61-77.

21.Сотов Л.С. Методы синтеза устройств, выполняющих инструкции перестановки битов данных / Л. С. Сотов // Гетеромагнитная микроэлектроника. 2011. Вып. 10. С. 25-50.

22.Сотов Л.С. Об эффективности использования специальных команд преобразования форматов данных в вычислительной технике / Л. С. Сотов // Гетеромагнитная микроэлектроника. 2011. Вып. 10. С. 61-80.

Публикации в других изданиях

23.Сотов Л.С. Динамическое форматирование представлений объектов реляционных СУБД на основе кластерных транспозиций/ Ж. А. Молодчен-ко, Л.С. Сотов, В. Н. Харин // Естественные и технические науки. 2007. № 6 (32). С. 224-226.

24.Сотов Л.С. Алгоритм создания диверсификационного метода битовых преобразований/ Ж.А. Молодченко, Л.С. Сотов, В. Н. Харин // Естественные и технические науки. 2007. № 6 (32). С. 220-223.

25.Сотов Л.С. Модуль генерации форматирующих сред в распределенных реляционных СУБД/ Ж.А. Молодченко, Л.С. Сотов, В. Н. Харин // Надежность и качество: труды Междунар. симпозиума / под ред. U.K. Юркова. Пенза: Изд-во Пенз. гос. ун-та, 2006. Т. 1. С. 179-182.

26.Сотов Л.С. Простой матричный формирователь г-выборок / A.B. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С. 47-56.

27.Сотов Л.С. Модуль сервера форматирования в распределенных реляционных СУБД с повышенным уровнем ИБ / Ж.А. Молодченко, Л.С. Сотов,

В.Н. Харин // Надежность и качество: труды Междунар. симпозиума / под ред. Н.К. Юркова. Пенза: Изд-во Пенз. гос. ун-та, 2006. Т. 1.С. 182-184.

28.Сотов J1.C. К вопросу об архитектуре аналого-цифровых систем генерации случайных сигналов / Ж.А. Молодченко, Л.С. Сотов, В. Н. Харин // Надежность и качество: труды Междунар. симпозиума / под ред. Н.К. Юркова. Пенза: Изд-во Пенз. гос. ун-та, 2007. С. 85-87.

29.Сотов J1.C. Аппаратный акселератор сервера форматирования данных / Ж. А. Молодченко, Л.С. Сотов, В. Н. Харин // Надежность и качество: труды Междунар. симпозиума / под ред. Н.К. Юркова. Пенза: Изд-во Пенз. гос. ун-та, 2007. С. 134-136.

30.Сотов JI.C. Эффективный прямошумовой генератор / Л.С. Сотов, Д.В. Ту-гушов, A.A. Игнатьев, А.Г. Передумов, A.B. Безруков // Физика и технические приложения волновых процессов: тез. докл. и сообщений 1 Междунар. науч.-техн. конф. 10-16 сентября 2001 г. Самара: Самар. кн. изд-во, 2001. Т. 1.С. 148.

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

32.Сотов Л.С. Концепция ГСЗ-платформы для распределенных информационно вычислительных систем специального назначения / Л.С. Сотов,

B.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Са-рат. ун-та, 2008. Вып. 3. С. 66-72.

33.Сотов Л.С. Моделирование архитектуры акселератора битовых перестановок с использованием САПР SYSTEM STUDIO фирмы SYNOPSYS / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та. 2008. Вып. 3. С. 60-66.

34.Сотов Л.С. Модели аппаратурных акселераторов перестановок бинарных множеств / Ж.А. Молодченко, C.B. Овчинников, Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 4. С. 11-22.

35.Сотов Л.С. Математические модели стохастического формирования изоморфных представлений структурных элементов данных в ЭВМ / Ж.А. Молодченко, Л.С. Сотов, В.Н Харин // Гетеромагнитная микроэлектроника». 2008. Вып.4. С. 29-41.

36.Сотов Л.С. Средства разработки и исследования архитектурных моделей в САПР System Studio. Использование инструментов System Studio при моделировании матричного генератора перестановок / Л.С. Сотов, А.Л. Хвалин // Гетеромагнитная микроэлектроника. 2008. Вып. 5. С. 112-121.

37.Сотов Л.С. Средства разработки и исследования архитектурных моделей в САПР System Studio. Основные объекты SystemC и их использование / Л.С. Сотов, А.Л. Хвалин // Гетеромагнитная микроэлектроника. Вып. 5.

C. 121-146.

38.Сотов J1.C. Матричные акселераторы транспозиционных преобразований форматов данных в ЭВМ / Ж.А. Молодченко, JI.C. Сотов, A.A. Солопов, В.Н. Харин // Гетеромагнитная микроэлектроника. Вып. 6. С. 91-107.

39.Сотов JI.C. Архитектура генераторов комбинаторных дескрипторов формата/ Ж.А. Молодченко, JI.C. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. 2009. Вып. 6. С. 108-119.

40.Сотов J1.C. Первичный преобразователь на основе ЖИГ-генератора для измерения сильных магнитных полей / A.J1. Хвалин, С.В. Овчинников, Л.С. Сотов, В.Н. Самолданов // Датчики и системы. 2009. №10. С. 57-58.

41.Сотов Л.С. Генераторы случайных импульсов на базе модельного отображения «сдвиг Бернулли» / А.Л. Блинов, Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. 2009. Вып. 6. С. 120130.

42.Сотов Л.С. Структура подсистемы стохастической генерации дескрипторов форматов / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин //Аспирант и соискатель. 2009. № 4. С. 86-88.

Патенты и зарегистрированные программы

43.Пат. на изобретение RU № 2320000 С1, МПК G06F 7/76 (2006.01), G06F 12/14 (2006.01). Дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия). № 2007105175/09; заявл. 13.02.2007; опубл. 20.03.2008, Бюл. №8, 6 с.

44.Пат. на изобретение RU № 2334272 С1, МПК G06F 21/22 (2006.01), G06F 12/14 (2006.01). Устройство защиты от несанкционированного доступа к информации / Молодченко Ж.А., Сотов Л.С., Харин В.Н. (Россия). № 2007105177/09; заявл. 13.02.2007; опубл. 20.09.2008, Бюл. № 26, 8 с.

45.Пат. на изобретение RU № 2340931 С1, МПК G06F 7/58 (2006.01) НОЖ 3/84 (2006.01). Генератор случайных чисел / Молодченко Ж.А., Сотов Л.С., Харин В.Н. (Россия). № 2007111405/09; заявл. 28.03.2007; опубл. 10.12.2008, Бюл. №34, 5 с.

46.Пат. на изобретение RU № 2390049 С1, МПК G06F 7/00 (2006.01). Параллельный дешифратор управляемой транспозиции информации, хранимой в персональной ЭВМ / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия). № 2008139529/09; заявл. 07.10.2008; опубл. 20.05.2010, Бюл. № 14,8 с.

47.Пат. на изобретение RU № 2390052 С2, МПК G06F 7/76 (2006.01). Дешифратор управляемой перестановки информации, хранимой в персональной ЭВМ / Молодченко Ж.А., Сотов Л.С., Харин В.Н. (Россия). № 2008132009/09; заявл. 06.08.2008; опубл. 20.05.2010, Бюл. № 14, 8 с.

48.Пат. на изобретение RU № 2393594 С1, МПК НО 1Р1/20 (2006.01). Полосовой ферритовый фильтр сверхвысоких частот / Хвалин А. Л., Сотов Л.С. (Россия). № 2009117566/09; заявл. 12.05.2009; опубл. 27.06.2010, Бюл. № 18,6 с.

49.Пат. на изобретение RU № 2395834 С1, МПК G06F 7/58 (2006.01). Генератор случайных перестановок / Сотов Л.С., Харин В. Н., Xпалии

А.Л. (Россия). № 2009104555/09; заявл. 12.02.2009; опубл. 27.07.2010, Бюл. № 21, 8 с.

50.Пат. на изобретение 1Ш № 2405187 С1 МПК С06Р7/24(2006.01). Устройство управляемой перестановки информации, хранимой в ЭВМ / Сотов Л.С., Харин В.Н. (Россия). № 2009111245/08; заявл. 30.03.2009; опубл.

27.11.2010. Бюл. №33. 8 с.

51.Пат. на изобретение 1Ш № 2408059 С2 МПК СОбИ 7/58 (2006.01) Генератор импульсов случайной длительности / Сотов Л.С., Харин В.Н., Хвалин А.Л. (Россия). № 2009104553/08; заявл. 12.02.2009; опубл. 27.12.2010. Бюл. № 36. 7 с.

52.Пат. на изобретение 1Ш 2409842 С1 МПК С06Р 12/14 (2006.01) СОбИ 17/20 (2006.01). Устройство кросс-кластерной управляемой перестановки информации, хранимой в персональной ЭВМ / Сотов Л.С., Харин В.Н., Соболев С.С. (Россия). № 2009115317/08; заявл. 23.04.2009; опубл.

20.01.2011.Бюл.№2. 8 с.

53. Пат. на изобретение 1Ш 2417402 С06Р7/00 (2006.01). Кросс-кластерная коммутационная матрица / Сотов Л.С. (Россия). № 2009133507; заявл. 07.09.2009; опубл. 27.04.2011. Бюл. №12. 13 с.

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

55.Свидетельство об официальной регистрации программы для ЭВМ №2004610988 (РФ). Программа расчета параметров модели Матерка полевого транзистора / Сотов Л.С. и др. Заявка № 2004610416. Зарегистрировано 21.04.2004.

56.Свидетельство об официальной регистрации программы для ЭВМ №2004610989 (РФ). Программа расчета параметров модели Гумеля-Пуна биполярного транзистора / Сотов Л.С. и др. Заявка № 2004610417, зарегистрировано 21.04.2004 г.

57.Свидетельство о государственной регистрации программы для ЭВМ №2010612449 (РФ). Программа моделирования комбинаторных преобразователей форматов представления данных в ЭВМ (ЭМАТИХ) / Сотов Л.С. и др. Заявка № 2010610690, зарегистрировано 7.04.2010 г.

'4 - 257 3 5

■ у . ■

Подписано в печать 31.10.11 Формат 60x84 1/16

Бум. офсет. Усл. печ. л. 2,0 Уч.-иэд. л. 2,0

Тираж 100 экз. Заказ 275 Бесплатно

Саратовский государственный технический университет

410054, Саратов, Политехническая ул., 77 Отпечатано в Издательстве СГТУ. 410054, Саратов, Политехническая ул., 77 Тел.: 24-95-70; 99-87-39, c-mail: izdal@sstu.ru

2011248882

Введение.

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

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

1.2. Использование преобразований форматов данных в системах защиты информации.

1.3. Инструкции обработки битов и подслов данных.

1.4. Проблемы использования аппаратурных средств преобразования форматов данных.

1.5. Основные результаты главы 1.

Глава 2. Концепция разработки и внедрения семейства устройств форматирования данных.

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

2.2. Формализация задачи формирования изоморфных представлений данных.

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

2.4. Декомпозиция процедуры формирования упорядоченного разбиения.

2.5. Классификация базовых форматирующих преобразований бинарных векторов данных.

2.6. Основные результаты главы 2.

Глава 3. Структурный синтез и модели устройств базовых форматирующих преобразований.

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

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

3.3. Параллельный формирователь упорядоченных разбиений ВСТАР.

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

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

3.6. Универсальное устройство преобразования форматов данных.

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

3.8. Формирователи перестановок и упорядоченных разбиений на базе топологий сортирующих сетей.

3.9. Синтез формирователей перестановок с заданной структурой циклов.

3.10. Инволютивный матричный преобразователь ВСТА1.

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

3.12. Основные результаты главы 3.

Глава 4. Методы построения и модели устройств перечисления множеств дескрипторов формата.

4.1. Модели и методы устройств комбинаторного формирования дескрипторов формата.

4.2. Комбинаторный генератор сочетаний элементов бинарных множеств.

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

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

4.5. Основные результаты главы 4.

Глава 5. Модели и методы структурного синтеза устройств стохастической генерации дескрипторов формата.

5.1. Вероятностные комбинаторные генераторы.

5.2. Устройство последовательного стохастического формирования дескрипторов формата SPRG.

5.3. Синхронный стохастический формирователь перестановок, модель SSPRG.

5.4. Вероятностные генераторы неупорядоченных г-выборок с быстрым ростом энтропии и равномерным распределением.

5.5. Стохастический формирователь упорядоченных разбиений конечных множеств MRPG.

5.6. Структурный синтез вероятностных формирователей классов сопряженных перестановок.

5.7. Использование генераторов динамического хаоса в подсистеме стохастического формирования дескрипторов формата.

5.8. Цифровой формирователь случайных чисел и временных интервалов.

5.9. Цифровой формирователь случайных чисел на базе сдвиговых регистров.

5.10. Квазишумовые режимы задающего генератора формирователя случайных чисел на базе отображения Аносова.

5.11. Встроенные средства контроля режимов функционирования генераторов случайных сигналов.

5.12. Сравнительный анализ устройств формирования и способов представления дескрипторов формата.

5.13. Основные результаты главы 5.

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

6.1. Инфраструктура средств осуществления динамического форматирования данных в вычислительной технике.

6.2. Универсальный модуль манипуляции битами данных в микропроцессорах.

6.3. Модуль защиты файлов изображений от несанкционированного копирования.

6.4. Исследование производительности модели формирователя перестановок ОКРМ64.

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

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

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

С расширением области применения средств вычислительной техники все чаще возникают задачи, связанные с формированием изоморфных представлений или битовых перестановок машинного слова. В число таких задач входят обработка морфологии изображений, сортировка, моделирование и тестирование цифровых устройств, задачи биоинформатики, расчет контрольных сумм и коррекция ошибок, стеганография, сжатие и развертывание информации, выполнение криптографических примитивов, обработка сигналов в системах RPMA {random permutation-based multiple access) для передачи данных с использованием технологий расширения спектра, преобразование данных для передачи в текстовом формате и т.п. При этом затраты машинного времени на битовые преобразования данных составляют от 30 до 90% времени выполнения задач.

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

В работах R.B. Lee, Y. Hilewitz, Z. Shi, H. Liao, Z. Wu, Y. Xiao, G. Dimitrakopoulos, C. Mavrokefalidis и др. для ускорения осуществления битовых перестановок предлагается расширение архитектуры процессоров. В основе ряда предлагаемых решений лежат многоуровневые коммутационные сети, теория которых была заложена в работах Клоза, Бенеша и развита в работах ряда авторов: М. Н. Ackroyd, D. P. Agrawal, D. G. Cantor, F. К. Hwang, С. P. Kruskal и др. Для ускорения битовых перестановок R.B. Lee с соавторами были предложены новые инструкции bfly {Butterfly), ibfly {Inverse Butterfly), grp {Grop), разработаны устройства для их реализации. Последовательное использование инструкций bfly и ibfly даёт возможность осуществить любую перестановку, но её выполнение может занимать значительное время. Инструкция grp является альтернативным подходом, но существующие аппаратурные решения не обладают необходимым быстродействием и сложны.

Для увеличения производительности в платформах: IA-32 {Intel Architecture, 32-bit), AMD64 , Itanium ISA, POWER {Performance Optimization With Enhanced RISC), кроме указанных базовых инструкций, вводится поддержка специализированных команд для манипуляций с битами данных. Однако при этом теряется универсальность.

В ряде отмеченных ранее задач требуется перечисление и формирование перестановок битов данных в случайном порядке. Для этого обычно используются последовательные, достаточно медленные алгоритмы Фишера-Йетса {Fisher-Yates), Саттоло {Sattolo).

В работах В. М. Курейчика, В. М. Глушань, JI. И. Щербакова, Г.С. Цирамуа, В.А. Богатырева, В.М. Полищука, В.И. Чабана, Р.В. Дмитришина и др. исследуются детерминированные и вероятностные формирователи перестановок, сочетаний и размещений. Однако предлагаемые устройства являются специализированными, их аппаратурная сложность составляет 0(п2) и быстро растет с увеличением п, где п - длина формируемого блока данных.

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

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

Тематика диссертационной работы соответствует научной программе кафедры общей физики Саратовского государственного университета им. Н.Г. Чернышевского и кафедры систем автоматизированного проектирования и информационных систем Воронежского государственного технического университета.

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

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

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

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

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

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

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

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

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

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

Научная новизна работы: 1. На основе предложенных базовых преобразований, включающих упорядоченные и неупорядоченные разбиения блока данных длиной п, обоснованы принципы создания и разработаны алгоритмы структурного и синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных. Показано, что при использовании разработанных устройств вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.

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

- параллельного формирования упорядоченных и неупорядоченных разбиений блоков данных длиной п=2к на т кластеров по 2" элементов с q = 2 log2 (п)-и-1 уровнями преобразования и аппаратурной сложностью не более чем п • (log2(п) -и/2-1) +1 логических элементов матрицы формирователя, где ^-положительное целое число, а

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

- параллельного формирования перестановок с заданной структурой циклов, аппаратурной сложностью О (log2 (ft)) и числом уровней преобразования q = 41о^(я);

- параллельного формирования прямых и обратных преобразований упорядоченных разбиений блоков данных длиной п=2к на т кластеров по 2" элементов в классе матричных устройств с аппаратурной сложностью О(п2);

- перечисления упорядоченных разбиений множества чисел (0,1,2,1) на блоки по 2й элементов, выполненных на базе матриц, формирующих упорядоченные разбиения входных данных длиной п, п!2, «/4, ., 2"+1 на два подмножества.

3. Обоснованы теоретические положения, включающие теоремы о композиции формирователей упорядоченных разбиений, о формировании сигналов управления переключателями, о декодировании битов управления, обеспечивающие создание универсального устройства преобразования форматов данных, выполняющего две новые инструкции bsn и grpm. Доказано, что разработанное устройство характеризуется более высокой скоростью выполнения и простотой аппаратурной реализации по сравнению с существующими решениями. На основании проведенных исследований разработаны варианты структурно-функциональной организации модулей, осуществляющих инструкции bsn, grpm, grp,pex.v,pdep.v,pex,pdep, rotate, shift.

4. Разработаны и обоснованы принципы построения высокопроизводительных вероятностных формирователей упорядоченных разбиений блоков данных длиной п с произвольной и заданной структурой циклов, характеризующиеся равномерным распределением вероятностей формируемых последовательностей. Разработанные вероятностные формирователи выполнены на базе предложенных устройств, осуществляющих упорядоченные и неупорядоченные разбиения. Доказано, что информационная энтропия вероятностного распределения выходных данных достигает значения более 50% от максимального за время, определяемое задержкой используемого формирователя, что обеспечивает увеличение производительности вычислительного устройства в п раз по сравнению с его производительностью при реализации алгоритмов Фишера-Иетса {Fisher-Yates) или Саттоло (Sattolo).

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

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

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

В диссертации показано, что общий вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз. Использование разработанных детерминированных и вероятностных формирователей упорядоченных разбиений блоков данных длиной п обеспечивает увеличение производительности вычислительного устройства примерно в п раз по сравнению с его производительностью при реализации алгоритмов Фишера-Йетса (.Fisher-Yates), Саттоло (Sattolo).

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

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

Реализация и внедрение результатов работы.

Результаты работы внедрены в ОАО «Тантал», г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от нелицензионного копирования.

Материалы диссертации были использованы при разработке устройств высокоскоростного преобразования форматов данных, разработанных в НИР «Исследование нелинейных физических процессов в сложных системах, включая наноструктуры», шифр «Синдикат - 3», проводимой в ОМФ НИИЕН по заданию Федерального агентства по образованию.

Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс кафедры «Общая физика» Саратовского государственного университета и использованы при проведении занятий по дисциплинам «Моделирование полупроводниковых приборов и устройств на их основе» и «Технические средства защиты информации», в дипломном проектировании, при подготовке магистерских и двух кандидатских диссертаций. Материалы диссертации были использованы в учебно-методическом пособии «Имитационные модели физических систем с дискретным временем» (Изд-во Сарат. ун-та, 2009. ISBN 978-5-292-03916-7, 56 е.), в котором рассматриваются вопросы имитационного моделирования матричных преобразователей форматов данных.

Внедрения подтверждены соответствующими актами.

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

По результатам работы в ФГУ ФИПС зарегистрированы 3 программы, получены 12 патентов РФ на изобретения.

Основные положения и результаты, выносимые на защиту:

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

2. Универсальное устройство преобразования форматов данных на базе многоуровневой коммутационной сети baseline обеспечивает произвольное преобразование форматов данных с использованием двух инструкций Ьбп и выполнение специализированных инструкций манипуляций с битами данных рт, ^р, рех. v, рйер.у, рех, рс1ер, инструкций логического и циклического сдвига данных.

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

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

8(/п + /22) > 2-—\---3:— = ~ 5 имеет равномерную функцию распределения

У11/22 /и/22 /2/21 • вероятностей формируемых бинарных последовательностей и описывается двухмерным дискретным отображением с хаотической динамикой в прямом и обратном времени.

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

6. Разработанные 64-разрядные устройства преобразования форматов данных имеют время преобразования от 12?3 до З0г3, где ^ - максимальная задержка сигнала на одном инверторе, нагруженном на четыре входа, что обеспечивает увеличение производительности вычислительной системы от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах КРМА, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на Международной научной конференции «Проблемы управления, передачи и обработки информации» (АТМ-ТКИ-50), Саратов, 2009, Международных симпозиумах «Надежность и качество», Пенза 2006, 2007, Всероссийской научно-практической конференции «Проблемы защиты информации ограниченного доступа от утечки по техническим каналам» Саратов, РАЦ «Тантал», 2003 г., Международной технической конференции «Перспективы развития электроники и вакуумной техники на период 1001-2006 гг.» ГШ ill «Контакт», Саратов, 2001, научно-технической конференции «Электронные приборы и устройства СВЧ», Саратов, 2001, Международной научно-технической конференции «Физика и технические приложения волновых процессов», Самара, 2001.

Основное содержание работы изложено в 22 публикациях в изданиях, рекомендованных ВАК РФ, а также в трудах международных конференций, симпозиумов, регистрации 3 программ для ЭВМ в реестре ФИПС. Оригинальность технических решений защищена 12 патентами РФ на изобретения. Всего по материалам диссертации опубликовано 57 работ.

5.13. Основные результаты главы 5

В данной главе предложены эффективные стохастические формирователи упорядоченных разбиений и сочетаний исходных множеств. Высокая производительность достигается благодаря использованию специальных топологий многоуровневых коммутационных сетей (ШЫ).

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

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

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

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

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

6.1. Инфраструктура средств осуществления динамического форматирования данных в вычислительной технике

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

Устройства осуществления базовых преобразований

Формирователи дескрипторов формата

Последовательн ого действия

Матричные параллельного действия

Модель ВСТА

Вероятностные (стохастические)

Комбинаторные (детерминирован ные)

На базе различных топологий М1И Модели семейства ВСТАМ.

На базе сортирующих сетей Модель ВСТАБ

Модель ВСТАК с конвейерной обработкой

Последовате льного действия Модель

БЯРв

Матричные параллельного действия

Безопасные генераторы случайных сигналов Модели ОйА, СО

Перечисл

Матричные Псевдосл ение и параллельного учайные стох действия Модель рассеяние

Модель МКРв РЯРв Модель

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

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

6.2. Универсальный модуль манипуляции битами данных в микропроцессорах

Существует много важных приложений, таких как криптография, обработка изображений, кодирование, распознавание образов, проектирование аппаратуры, моделирование и др., где манипуляции с битами данных занимают значительную часть общего объёма вычислений. При этом можно выделить несколько команд, выполнение которых требуется особенно часто: это команда извлечения группы бит данных pex{parallel extract), команда размещения битов в заданных позициях машинного слова pdep {parallel deposit), команда осуществления произвольной перестановки битов машинного слова и команды логического и циклического сдвигов битов машинного слова. Логический и циклический сдвиги могут осуществлять большинство микропроцессоров. Но этого не достаточно для обеспечения высокопроизводительной обработки на битовом уровне.

В работе [225] был предложен способ структурного синтеза устройств разбиения строки входных данных для реализации инструкций группировки grp (group), выборки рех (parallel extract), размещения pdep (parallel deposit).

Показано, что используя предложенный подход построения универсального устройства для манипуляций с битами данных, можно осуществить инструкции логического и циклического сдвига данных. Проблемой, возникающей при разработке устройства, выполняющего команду grp, является достаточно высокая аппаратурная сложность блока декодирования битов управления переключателями. Аналогичная проблема возникает и при других подходах к разработке устройства, основанных, например, на использовании многоуровневой коммутационной сети butterfly [46]. В работе [226] показано, что при осуществлении логических и циклических сдвигов битов данных на базе обратной топологии сети butterfly удается существенно упростить декодер бит управления и увеличить его быстродействие. При этом для построения универсального модуля манипуляции битами требуется две сети butterfly и /butterfly, реализующие прямые и обратные преобразования.

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

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

С\,\-Сп!2,к

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

ЗАКЛЮЧЕНИЕ

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

При проведении исследований получены следующие научные и практические результаты:

1. На основе сформулированных в диссертации положений использования упорядоченных разбиений в качестве базовых преобразований входных данных разработана и обоснована структура комплекса новых детерминированных и вероятностных устройств формирования изоморфных представлений данных. Доказано, что использование разработанных устройств приводит к увеличению производительности вычислительной системы на базе 64 разрядного процессора от 2 до 10 раз для задач сортировки, распознавания геометрических образов и символов на бинарных изображениях, обработки морфологии изображений, медианной фильтрации для устранения шумов на изображениях, операций преобразования представлений генетических последовательностей в биоинформатике, обработки данных в системах КРМА, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.

2. Разработаны теоретические положения, обеспечивающие структурный синтез и принципы функционирования устройств, формирующих упорядоченные разбиения входных слов данных длиной п на подмножества с произвольной и заданной структурой циклов. На базе многоуровневых коммутационных и сортирующих сетей и матричных коммутаторов предложены устройства, имеющие аппаратурную сложность О(п), 0(nlog2n), 0(«(log2«)2), О(п2). Проведена сравнительная оценка их производительности и разработаны рекомендации к применению.

3. Разработанные положения структурного синтеза формирователей упорядоченных разбиений и блоков управления ими обеспечили создание универсального устройства для поддержки новых инструкций bsn и grpm, осуществляющих динамическое и статическое преобразования форматов данных. Показана эффективность предложенного решения для осуществления манипуляций с битами и подсловами данных, реализуемых с использованием специализированных инструкций, таких как рех.v, pdep.v, рех, pdep, shift, rotate. Проведенный сравнительный анализ свидетельствует о том, что предложенное устройство в настоящее время является наиболее эффективным с точки зрения производительности и простоты аппаратурной реализации.

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

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

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

7. Разработанные IP блоки, методики расчета и синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных в ЭВМ внедрены в ОАО «Тантал», г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от не лицензионного копирования. Научные основы создания, принципы функционирования, математические и имитационные модели комбинаторных устройств формирования изоморфных представлений данных в ЭВМ внедрены при организации обучения специалистов студентов ГОУ ВПО «Саратовский государственный университет им. Н.Г. Чернышевского». По результатам работы в ФГУ ФИПС зарегистрированы 3 программы и получены 12 патентов РФ на изобретения.

1. Шапиро Л., Стокман Дж. Компьютерное зрение, изд. М.: БИНОМ. Лаборатория знаний, 2006. 752 с.

2. Shi Z., Lee R.B.Subword Sorting with Versatile Permutation Instructions // Proceedings of the International Conference on Computer Design, 2002. P. 234-241.

3. Hilewitz Y., Lee R.B. Fast Bit Gather, Bit Scatter and Bit Permutation Instructions for Commodity Microprocessors // Journal of Signal Processing Systems, 2008. Vol. 53, № 1-2. P. 145-169.

4. The Mathworks, Inc., Image processing toolbox user's guide. URL: http://www.mathworks.com/help/pdfdoc/images/imagestb.pdf (дата последнего обращения 24.01.2011).

5. Hilewitz Y. Advanced bit manipulation instructions: architecture, implementation and applications // A dissertation presented to the faculty of princeton university in candidacy for the degree of doctor of philosophy. 2008. 161 p.

6. Lee R. Accelerating Multimedia with Enhanced Micro-processors // IEEE Micro, 1995. Vol. 15, № 2. P. 22-32.

7. Paver N., Aldrich B, Khan M. ITT-L4.3: INTEL® WIRELESS MMX(TM) TECHNOLOGY: A 64-BIT SIMD. II 305. Architecture for Mobile Multimedia // IEEE International Conference on Acoustics, Speech, and Signal Processing -ICASSP, 2003. Vol. II. P. 305-308.

8. Материал из Википедии: UUE http://ru.wikipedia.org/wiki/UUE (дата последнего обращения 24.01.2011).

9. UUE кодирование, http://algolist.manual.ru/compress/standard/uue.php (дата последнего обращения 21.01.2011).

10. Rivest R.L. The RC5 encryption algorithm // Fast Software Encryption: Second International Workshop, Lecture Notes in Computer Science, 1994. Vol. 1008. P. 86-96.

11. Lacaze В., Roviras D. Effect of random permutations applied to random sequences and related applications // Signal Processing Journal, 2002. Vol. 82. P. 821-831.

12. Coulon M., Roviras D. Adaptive Joint Detection for a Random Permutation-Based Multiple-Access System on Unknown Time-Varying Frequency-Selective Channels // 14th European Signal Processing Conference (EUSIPCO 2006), Florence, Italy. 2006.

13. Pat. 7281188 US, H03M 13/00 (20060101). Method and system for detecting and correcting data errors using data permutations.

14. Henry S.,Warren Jr. Hacker's Delight // Addison-Wesley Professional, 2002. 320 c.

15. Moldovyan A.N., Moldovyan A.A., Eremeev M.A., Sklavos N. New Class of Cryptographic Primitives and Cipher Design for Networks Security // International Journal of Network Security, 2006. Mar. Vol. 2. № 2. P. 114-125.

16. Sklavos N. et al. Encryption and data dependent permutations: implementation cost and performance evaluation // Proceedings of the International Workshop. Springer-Verlag. 2003. LCNS 2776. P. 337-348.

17. Goots N.D., Izotov B.V., Moldovyan A.A., Moldovyan A.N. Fast Ciphers for Cheap Hardware: Differential Analysis of SPECTR-H64, Springer-Verlag LNCS 2776 (2003) P. 449-452.

18. Гуц Н.Д., Молдовян A.A., Молдовян H.A. Построение управляемых блоков перестановок с заданными свойствами // Вопросы защиты информации. 1999. N.4. С.39-49.

19. Молдовян H.A., Молдовян A.A., Алексеев JI.E., Молдовян H.A., Молдовян A.A., Алексеев JI.E. Перспективы разработки скоростных шифров на основе управляемых перестановок // Вопросы защиты информации, 1999, № 1, С. 41-47.

20. Chen H.C., Guo J.I., Huang L.C., Yen J.C. Design and realization of a new signal security system for multimedia data transmission//Applied Signal Processing. 2003. №13. P.1291-1305.

21. Uehara Т., Safavi-Naini R., Ogunbona P. Securing wavelet compression with random permutations // IEEE Pacific-Rim Conference on Multimedia (IEEE-PCM'2000). 2000. P. 332-335.

22. Zeng W., Lei S. Efficient frequency domain selective scrambling of digital video // IEEE Trans. Multimedia 2003. 5(1). P. 118-129.

23. Mao Y., Wu M. A joint signal processing and cryptographic approach to multimedia encryption // IEEE Trans. Image Processing 2006. 15(7). P. 2061-2075.

24. Socek D. Permutation-based transformations for digital multimedia encryption and steganography / Ph.D. dissertation, Department of Computer Science and Engineering, Florida Atlantic University, 2006. 148 p.

25. Brown L. Comparing the security of pay-TV systems for use in Australia // Australian Telecommunication Research. 1990. Vol. 24. № 2 P. 1-8.

26. Сотов JI.C. Концепция ГС2?-платформы для распределенных информационно вычислительных систем специального назначения / JI.C. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 3. С.66-72.

27. Сотов JI.C. О формировании доверенной среды серверных систем управления базами данных / Ж.А. Молодченко, JI.C. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2008. .№3. С.23-27.

28. Сотов JI.C. Модуль генерации форматирующих сред в распределенных реляционных СУБД/ Ж.А. Молодченко, JI.C. Сотов, В. Н.

29. Харин // Труды международного симпозиума НАДЕЖНОСТЬ И КАЧЕСТВО Том 1/Под ред.Н.К.Юркова Пенза: Изд-во Пенз.гос.ун-та, 2006. С. 179-182.

30. Armonk N.Y. AltiVec Extensions to PowerPC" Instruction Set Architecture Specification// Motorola Corporation, May 1998. 114 p.

31. Intel Corporation, Intel 64 and IA-32 Architectures Software Developer's Manual, 2008. Vol. 1-2. 143 p.

32. Intel Corporation, Intel Itanium Architecture Software Developer's Manual, 2006. Vol. 1-3, Rev. 2.2. 210 p.

33. Lee R.B., Shi Z., Yang X. Efficient Permutation Instructions for Fast Software Cryptography//IEEE Micro, 2001. Vol. 21, № 6. P. 56-69.

34. Shi Z., Lee R.B. Bit Permutation Instructions for Accelerating Software Cryptography // Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors (ASAP 2000), 2000. P. 138-148.

35. Lee R. Precision Architecture // IEEE Computer. 1989. Vol. 22, № 1, P. 78-91.

36. Lee R. Subword Parallelism in MAX-2// IEEE Micro, 1996. Vol. 16. № 4, P. 51-59.

37. IA-64 Application Developer's Architecture Guide // Intel Corporation, May 1999. 130 p.

38. Shi Z., Yang X., Lee R.B. Arbitrary bit permutations in one or two cycles. Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP), 2003. P. 237-247.

39. Lee R.B., Yang X., Shi Z.J. Single-cycle bit permutations with MOMR execution. Journal of Computer Science and Technology, 2005. 20(5). P. 577-585.

40. Benes V.E. Mathematical Theory of Connecting Networks and Telephone Trafic. N.Y. Academic Press, 1965. 333 p.

41. Lee C.Y., Oruc A.Y. Fast Parallel Algorithm for Routing Unicast Assignments in Benes Networks // IEEE Transactions On Parallel And Distributed Systems. March 1995. Vol. 6., № 3. P. 329-334.

42. Pat. 6.922.472 US, МПК 380/37 Method and system for performing permutations using permutation instructions based on butterfly networks.

43. Giorgos Dimitrakopoulos, Christos Mavrokefalidis, Sorter Based Permutation Units for Media-Enhanced Microprocessors//IEEE transactions on very large scale integration (VLSI) systems, 2007. Vol. 15, № 6. P. 711-715.

44. Hilewitz Y., Shi Z.J., Lee R.B. Comparing Fast Implementations of Bit Permutation Instruction // Proceedings of the 38th Annual Asilomar Conference on Signals, Systems, and Computers, 2004. P. 1856-1863.

45. Советов Б. Я., В. В. Цехановский, Чертовский В. Д. Базы данных. Теория и практика. М : Высшая школа, 2005. 464 с.

46. Васюкевич В. О. Элементы асинхронной логики. Венъюнкция и секвенция / 2009. 123с. URL: http://asynlog.balticom.lv/Content/Files/ru.pdf. (дата последнего обращения 24.01.2011)

47. Молодченко Ж. А., Сотов Л.С., Харин В. Н. Стохастическое кластерное моделирование картезиана двудольного графа в рамках наложенных ограничений Воронеж, гос. лесотехн. акад. Воронеж, 2006. 10 с: 3 ил., Библиог. 5 назв. Рус- Деп. в ВИНИТИ.

48. Abramowitz М., Stegun I.A. Handbook of Mathematical Functions. US Department of Commerce, National Bureau of Stanards. 1970. 430 p.

49. Носов В.А. Комбинаторика и теория графов. М.:МГУ. 1999.112 С.

50. Czumaj A., Kanarek P., Kutylowski М., Lorys К. Fast Generation of Random Permutations Via Networks Simulation // Algorithmica. 1998. V.21. № 1. P.2-20.

51. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2009. Т.7. №10. С.78-85.

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

53. Риордан Дж. Введение в комбинаторный анализ. М.: Изд-во иностранной литературы, 1963. 289 с.

54. Стенли Р. Перечислительная комбинаторика: Пер. с англ. М. Мир. 1990. 440 с.

55. IEEE Standard SystemC® Language Reference Manual Version 2.2 ISBN 0-7381-4871-7 SH95505.

56. Hawang F.K., Hwang F. The Mathematical Theory of Nonblocking Switching Networks. NJ.: World Scientific Publishing Company, 2004. 200 p.

57. Сотов JI. С. Комбинаторная модель функционального формирователя разбиений бинарного множества // Информационные технологии. 2010. №10. С. 46-52.

58. US № 6,952,478, МПК 380/37 Method and system for performing permutations using permutation instructions based on modified omega and flip stages/ Lee; Ruby B. (Princeton, NJ), Yang; Xiao (Princeton, NJ). October 4, 2005 Appl.No.: 09/850,238.

59. Сотов Л.С., Соболев C.C., Харин B.H. Кросс кластерная коммутационная матрица для аппаратной поддержки управляемойперестановки данных в криптографических системах // Проблемы информационной безопасности. Компьютерные системы. 2009. №4. С. 56-63.

60. Сотов Л.С., Солопов А.А., Фарафонова А. Модель инволютивного транспозиционного преобразователя // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.38-48.

61. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2009. Т.7. №10. С.78-85.

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

63. Pat. 5175539 US, 340/2.21 Interconnecting network. / Richter; Harald.-December 29, 1992.

64. Сотов Л.С. Простой матричный формирователь г-выборок / А.В. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.47-56.

65. Pat. US 6381690 G06F 7/76 (20060101); 712/223 ; Processor for performing subword permutations and combinations/Lee; Ruby B. April 30, 2002 . T. Appl. No.: 08/509,867 Filed: August 1, 1995.

66. Hilewitz Y., Lee R. A. New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations // IEEE Transactions on Computing. 2009. Vol. 58, № 8. P. 1035-1048.

67. Shi Z.J., Lee R.B. Implementation Complexity of Bit Permutation Instructions/Proceedings of the 37th Annual Asilomar Conference on Signals, Systems, and Computers, 2003. P.879-886.

68. Hilewitz Y., Shi Z. J., Lee R. B. Comparing Fast Implementations of Bit Permutation Instruction // Proceedings of the 38th Annual Asilomar Conference on Signals, Systems,and Computers. Pacific Grove, California, USA, Nov. 7-10, 2004. P.1856-1863.

69. Batcher К. E. Sorting Networks and Their Applications.// Proceedings of 1968 Spring Joint Computer Conference, pp. 307-314, 1968.

70. Pat/ US 5319788 G06F 7/22 (20060101); 712/300 ; Modified batcher network for sorting N unsorted input signals in log.sub.2 N sequential passes/Canfield; Earl R., Williamson; Stanley G. June 7, 1994 . T. Appl. No.:07/677,222 Filed:March 29, 1991.

71. Алексеев JI. Е., Белкин Т. Г., Гуц Н. Д., Изотов Б. В. Управляемые операции: повышение стойкости к дифференциальному криптоанализу// Безопасность информационных технологий. 2000. № 2. С. 81-82.

72. Белкин Т.Г., Гуц Н.Д., Молдовян А.А. Молдовян Н.А. Способ скоростного шифрования на базе управляемых операций. Управляющие системы и машины. 1999. №б. С. 78-87.

73. Молдовян А. А., Молдовян Н. А. Скоростные шифры на базе нового криптографического примитива // Безопасность информационных технологий. 1999. № 1. С. 82-88.

74. Монахов, В. С. Введение в теорию конечных групп и их классов : учеб. пособие для физико-математических спец. вузов / В. С. Монахов. Мн. : Вышэйшая школа, 2006. - 207 с.

75. Naor M.,Reingold О. Constructing Pseudo-Random Permutations with a Prescribed Structure//Journal of Cryptology. 2002. №15. P.97-102.

76. Tsaban В. Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation.//Journal of Algorithms,V.47. Issue 2. July 2003. P.104-121.

77. Clos C. A study of nonblocking switching networks // Bell System Technical Journal, Vol 32, 1953, S.406-424.

78. Сотов JI.С., Хвалин A.JI. Средства разработки и исследования архитектурных моделей в САПР System Studio. Часть 2. Основные объекты SystemC и их использование // Гетеромагнитная микроэлектроника, 2008. Вып. 5. С.121-146.

79. Хамахер К., Вранешич 3., Заки С. Организация ЭВМ. 5-е изд. СПб.: Питер; Киев: Изд. группа BHV, 2003. С. 668-675.

80. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М., 1990. 216 с.

81. Бассалыго Л. А., Пинскер М. С. О сложности оптимальной неблокирующей коммутационной схемы без перестроения.//Пробл. передачи информ., 1973, 9:1, 84-87.

82. Enrique С.А., Gregory W. D. A Comparison of Circuits for On-Chip Programmable Crossbar Switches//10th NASA Symposium on VLSI Design, Albuquerque, NM, March 20-21, 2002. .

83. Martel C. , Nguyen V. Designing networks for low weight, small routing diameter and low congestion// in: 25th Conference of the IEEE Communications Society, INFOCOM, 2006.

84. Hamza, Haitham S. Optimizing complexity in Benes-type WDM switching networks.//Photonic Network Communication vol.17 no.3.-2009.-Page 277 291.

85. A. c. 643883 СССР, G06F 15/20. Устройство для перебора сочетаний, размещений и перестановок/Г. Я Левин. — Опубл. 1979, Бюл. № 10.

86. А. с. 957215 СССР, МКИЗ G06F 15/20. Устройство для перебора перестановок/Г А. Ерошко, Н. Н. Шубина. —Опубл. 1982, Бюл. № 33.

87. А. с. 1383381 СССР, МКИЗ G06F 15/20. Устройство для перебора перест новок/В. М. Глушань, И. Г. Ефремов, М. И. Пупков. — Опубл. \1989.-Бюл. №11.

88. А. с. 1124319 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний и перестановок/В. М. Глушань и др. — Опубл. 1984, Бюл № 42.

89. А. с. 1190388 СССР, МКИЗ G06F 15/20. Устройство для перебора пер становок/В. М. Глушань и др.— Опубл. 1985, Бюл. № 41.

90. А. с. 1397933 СССР, МКИЗ G06F 15/20. Устройство для перебора перест новок/В. М. Глушань и др.—Опубл. 1988, Бюл. № 19.

91. А. с. 1397933 СССР, МКИЗ G06F 15/20. Устройство для перебора перест новок/В. М. Глушань и др.—Опубл. 1988, Бюл. № 19.

92. А. с. 995093 СССР, МКИЗ GOGF 15/20. Устройство для перебора перест новок/Н И. Крылов — Опубл. 1983, Бюл. № 5.

93. А. с. 1513467 СССР, МКИЗ G06F15/20. Функциональный генератор п рестановок/В. М. Глушань, И. Г. Ефремов, С. Ю. Ермаков. — Опубл. 1987 Бюл. №37.

94. Рейнгольд. Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ./Под ред. В.Б. Алексеева.-М.: Мир, 1980.-476 С.

95. Глушань В. М., Пупков М. И., Щербаков Л. И. Алгоритмы формирования упорядоченных г-выборок//Кибернетика. 1988. № 1. С. 129—131.

96. Тимошевская Н.Е. О нумерации перестановок и сочетаний для организации параллельных вычислений в задачах проектирования управляющих систем // Известия Томского политехнического университета, 2004. Т.307. №6. С. 18-20.

97. Portz М., Aachen R. On the Use of Interconnection Networks in Cryptography ./Springer, D.W. Davies (Ed.): Advances in Cryptology EUROCRYPT '91, LNCS 547, pp. 302-315, 1991.

98. William J.D., Brian T. Principles and practices of interconnection networks/Morgan Kaufmann Publishers Inc. San Francisco, CA, USA- 2003.- 550 p.

99. CEES J.A. JANSEN . On the Construction of Run Permuted Sequences/Springer, Damgard I.B. (Ed.): Advances in Cryptology EUROCRYPT '90, LNCS 473, pp. 196-203, 1991.

100. Reif J. H. An optimal parallel algorithm for integer sorting./ In 26th Symposium on Foundations of Computer Science, 1985.-P. 496-503.

101. Alonso L., Schott R. A parallel algorithm for the generation of permutation and applications// Theoretical Computer Science. 1996. 159(1). P.15-28.

102. Anderson R. Parallel algorithms for generating random permutations on a shared memory machine./ In Proc. SPAA'90. 1990. P. 95-102.

103. Lassous I.Guerin, Thierry E. Generating Random Permutations in the Framework of Parallel Coarse Grained Models./Rapport de recherche, N 3896.- Mars 2000.-P.1-14.

104. Dehne F., Fabri A., and Rau-Chaplin A. Scalable parallel computational geometry for coarse grained multicomputers.// International Journal on Computational Geometry, Vol. 6(No. 3):pp. 379-400, 1996.

105. Valiant L. A bridging model for parallel computation. Communications of the ACM, Vol.33(8):103-lll, 1990.

106. Молодченко Ж.А., Сотов JI.C., Харин B.H. Архитектура генераторов комбинаторных дескрипторов формата // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2009. Вып. 6. С. 108-119.

107. Молодченко Ж.А., Сотов Л.С., Харин В.Н. Моделирование архитектуры акселератора битовых перестановок с использованием САПР SYSTEM STUDIO фирмы SYNOPSYS.// «Гетеромагнитная микроэлектроника». Саратов: Изд-во Сарат. ун-та. 2008. - Вып.З. С. 60 - 66.

108. А. с. 525948 СССР, МКИЗ G06F7/00. Устройство для перебора сочетаний/ В. В. Епихин, Опубл. 1976, Бюл. № 31.

109. А. с. 512472 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний/В. В. Епихин. — Опубл. 1976, Бюл. № 16.

110. А. с. 514295 СССР, МКИЗ G06F15/20. Устройство для перебора сочет ний /В. В. Енихин. — Опубл. 1976, Бюл. № 18.

111. А. с. 634285 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний/ Г. С. Цирамуа, В. А. Богатырев. — Опубл. 1978, Бюл. № 43.

112. А. с. 1370655 СССР, МКИЗ G06F 15/31. Устройство для перебора сочет ний/В. М. Глушань, А. В. Пришибской.— Опубл. 1988, Бюл. № 4.

113. А. с. 1397934 СССР, МКИЗ G06F 15/31. Устройство для перебора сочет ний/В. М. Глушань, А. В. Пришибской.—Опубл. 1988, Бюл. № 19.

114. А. с. 1008750 СССР, МКИЗ G06F 15/31. Устройство для перебора сочетаний/С. П. Присяжнюк и др.— Опубл. 1983, Бюл. № 12.

115. А. с. 1264195 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний/В. М. Глушань и др. — Опубл. 1986, Бюл. № 38.

116. А. с. 1305702 СССР, МКИ2 G06F 15/20. Устройство для перебора сочетаний/В. М. Глушань, М. В. Рыбальченко. — Опубл. 1987, Бюл. № 15.

117. Майоров С. А., Новиков Г. И.@ Структура ЭВМ. 2-е изд., перераб. и д полн. —JL: Машиностроение, 1979. — 384 с.

118. Борисенко A.A., Протасова Е. А. Цифровой автомат для перебора композиций//Вюник СумДУ. Техшчш науки",№2.-2007.-С.123-126.

119. Борисенко A.A. Биномиальные автоматы./Сумы: СумГУ, 2005.-120 с.

120. А. с. 1077054 МПК Н03К23/00. Счетчик импульсов / А. А. Борисенко. И. Д. Пузько. JI. А. Стеценко. Заявка: 3479062, 27.07.1982. Опубликовано: 28.02.1984.

121. Alan Tucker. Applied Conbinatorics.NEW YORK:John Wiley & Sons, INC, Third Edition. 1995. 462 p.

122. Молодченко Ж.А., Сотов JI.C., Солопов A.A., Харин B.H. Матричные акселераторы транспозиционных преобразований форматов данных в ЭВМ //Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2009. Вып. 6. С.91-107.

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

124. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2009. Т.7. №10. С.78-85.

125. Сотов Л.С. Модели аппаратурных акселераторов перестановок бинарных множеств / Ж.А. Молодченко , C.B. Овчинников, Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 4. С. 11-22.

126. Amirfathi M., Holtmann U., Ramachandran L. et al. CoCentric System Studio Synthesizable SystemC RTL Code Generation. Synopsys, July. 2001. 210 p.

127. А. с. 903891 СССР, МКИЗ G06F 15/31. Устройство для перебора сочетанш /В. М. Полищук. — Опубл. 1982, Бюл. № 5.

128. А. с. 1262520 СССР, МКИЗ G06F 15/20. Устройство для перебора сочет ний/В. М. Глушань и др.— Опубл. 1986, Бюл. № 37.

129. Сотов Л.С., Хвалин А.Л. Средства разработки и исследования архитектурных моделей в САПР System Studio. Часть 2. Основные объекты SystemC и их использование // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 5. С.121-146.

130. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. М., 2003. 240 с.

131. Байбурин В.А., Мантуров А.О. Перспективные методы защиты информации при её передаче по открытому каналу связи // Информационная безопасность регионов. 1(2). 2008. С.33-37.

132. Andrew С. Yao. Theory and application of trapdoor functions// In Proceedings of the 23rd IEEE Symposium on Fundation of Computer Science New York, IEEE. 1982. P. 80-91.

133. Blum M., Micali S. How to generate cryptographically strong sequences of pseudo-random bits // SIAM Journal on Computing, 1984. №13. P. 850-864.

134. Levin L. A. One-way function and pseudorandom generators // In Proceedings of the 17th ACM Symposium on Theory of Computing, New York, 1985. ACM. p. 363-365

135. Шнайер Б. Прикладная криптография // Протоколы, алгоритмы, исходные тексты на языке Си. М., 2002. 610 с.

136. Goldreich О., Goldwasser S., Micali S. How to construct random functions.// Journal of the ACM, Vol. 33, No. 4, Oct. 1986, P. 792-807.

137. Luby M., Rackoff C. "Pseudo-random permutation generators and cryptographic composition // Proceedings of the 18th ACM Symposium on the Theory of Computing, ACM, 1986, P. 356-363.

138. Luby VI. and Rackoff C. How to construct pseudorandom permutations and pseudorandom functions// SIAM J. Compute vol. 17, 1988, pp. 373-386.

139. Mauier U. A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators // Abstracts of Eurocrypt '92, Balatonfiired, Hungary, 1992. P. 614-621.

140. Zheng Y., Matsumoto T. and Imai H. Impossiblility and optimally results on con-strucbng pseudorandom permutations// Abstract of EUROCRYPT'89, Houthalen, Belgium, April 1989, P. 412-421.

141. Patarin J. How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function. Springer-Verlag GmbH. Lecture Notes in Computer Science. 1993. V.658 P.256-267.

142. Patarin J. New results on pseudorandom permutation generators based on the DES Scheme// Abstracts of Crypto'91. P. 72 -77.

143. Sadeghiyan В. and Pieprzyk J. On necessary and sufficient conditions for the construction of super pseudorandom permutations // Abstracts of Asiacrypt'91, November 1991. P. 117-123.

144. Pieprzyk J. How to Construct Pseudorandom Permutations from Single Pseudorandom Functions // Abstracts of Asiacrypt'91, November 1991. P. 219-223.

145. Schnorr C.P. On the construction of random number generators and random function generators // In Proc. of Eurocrypt SSt Lecture Notes in Computer Science, Springer Verlag, New York, 1988. P. 372 -377.

146. Rueppel R.A. On the security of Schnorr's pseudo random generator // Astracts of EUROCBYPT'89, Houtkalen, Belgium, April 1989.

147. Zheng Y., Matsumoto Т., Imai H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses //Astracts of CRYPTO'89, Santa Barbara, CA, July 1989.

148. Portz M.A. Generalised Description of DES-based and Benes-based Permutation Generators // Springer-Verlag London Lecture Notes In Computer Science. 1992. Vol. 718. P. 397-409.

149. Clos C. A study of nonblocking switching networks.// Bell System Technical Journal, 1953. Vol 32. P.406-424.

150. A. c. 1101820 СССР, МКИЗ G06F7/58. Датчик случайных последовательностей.

151. А. с. 845154 СССР, МКИЗ G06F 1/02. Генератор равномерно распределенных случайных интервалов времени.

152. А. с. 1228103 СССР, МКИЗ G06F7/58. Генератор случайных сочетаний.

153. А. с. 879755 СССР, МКИЗ НОЗк 3/84. Датчик случайных равновероятных временных интервалов.

154. А. с. 1034034 СССР, МКИЗ G06F7/58. Датчик случайных равновероятных временных интервалов.

155. Глушань В. М., Прихоженко Б. Ю., Щербаков JI. И. Способ генерирования импульсов случайной двоичной последовательности сравновероятным законом распределения интервалов // Изв. СК НЦВШ Техн. науки. 1984. №2. С. 38-41.

156. А. с. 1319027 СССР, МКИЗ G06F7/58. Генератор случайных сочетаний.

157. Пат. на изобретение RU № 2395834 С1, МПК G06F 7/58 (2006.01). Генератор случайных перестановок/Сотов JI.C., Харин В. Н., Хвалин A.JI. (Россия). № 2009104555/09; заявл. 12.02.2009; опубл. 27.07.2010. Бюл. № 21. 8 с.

158. Пат. на изобретение RU № 2340931 С1, МПК G06F 7/58 (2006.01) Н03К 3/84 (2006.01). Генератор случайных чисел /Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия), заявл. 28.03.2007; опубл. 10.12.2008, Бюл. № 34, 5 с.

159. Fisher R.A., Yates F. Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. 1948. P. 26-27.

160. Durstenfeld R. Algorithm 235: Random permutation//Communications of the ACM, 1964. V.7 № 7. P.420.

161. Кнут Д.Э. Искусство программирования. Сортировка и поиск. М.-.Вильяме. 2009. Т. 3. 824 с.

162. Коростелев Г.Н., Сотов Л.С. Сложная динамика генераторов на диоде Ганна с низкочастотным контуром // Изв. вузов. Радиотехника и электроника.-1989.-1Ч9.-Т.34.-С. 1925-1929.

163. Шеннон К. Теория связи в секретных системах. М.: Изд. иностр. лит.,Сб. Работы по теории информации и кибернетике. 1963. 830 с.

164. US 6934388 В1 380/47. Method and apparatus for generating random permutations.

165. Сотов Л.С., Харин В.Н. Использование генераторов динамического хаоса в системах информационной безопасности // Проблемы информационной безопасности. Компьютерные системы. 2009. №2. С. 32-37.

166. Осипенко Г.С. и др. Построение инвариантных мер динамических систем // Дифференциальные уравнения и процессы управления. 2007. № 4. с. 27-51.

167. А. с. 1269128 СССР, МКИЗ G06F7/58. Устройство для случайного перебора перестановок.

168. Кофман А. Введение в прикладную комбинаторику. М., 1975. 480 с.

169. Ritter Т. Transposition Cipher with Pseudo-Random Shuffling: The Dynamic Transposition Combiner// Cryptologia. 1991. Vol. 15(1). P. 1-17.

170. Сотов JI.C. Динамическое форматирование представлений объектов реляционных СУБД на основе кластерных транспозиций/ Ж. А. Молодченко, Л.С. Сотов, В. Н. Харин //Естественные и технические науки. 2007. № 6 (32). С.224-226.

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

172. Гантмахер Ф.Р. Теория матриц. М., 1966. 576 с.

173. Феллер В. Введение в теорию вероятностей и ее приложения. М., 1964. Т. 1.2-е изд. 499 с.

174. Thorsten G., Stan L., Grant M., Stuart S. System Design with SystemC. -Boston; Dordrech; London, 2002. 240 p.

175. US 7583155 МПК G06F7/58 Random sequence generator.

176. US №05871400, МПК A63F9/21. Random number generator for electronic applications.

177. Пат. на изобретение RU № 2340931 CI, МПК G06F 7/58 (2006.01) H03K 3/84 (2006.01). Генератор случайных чисел / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия). № 2007111405/09; заявл. 28.03.2007; опубл. 10.12.2008, Бюл. № 34, 5 с.

178. Портенко Н.И., Скороход А.В., Шуренков В.М. Марковские процессы. М., 1989. 248 с.

179. Шило В.Л. Популярные цифровые микросхемы. М., 1989. С. 107110.

180. Sattolo S. An algorithm to generate a random cyclic permutation // Information Processing Letters. 1986. V. 22. P. 315-317.

181. Prodinger H. On the analysis of an algorithm to generate a random cyclic permutation // Ars Combinatoria. 2002. V. 65. P. 75-78.

182. Mahmoud H.M. Mixed distributions in sattolo's algorithm for cyclic permutations via randomization and derandomization // Journal of Applied Probability. V. 40. 2003. P. 790-796.

183. Wilson M.C. Overview of Sattolo's Algorithm // Algorithms Seminar 2002-2004. INRIA Research Report. 2005. P. 105-108.

184. Сотов JI.C. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии / А.В. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.57-71.

185. Сотов Л.С., Харин В.Н. Цифровой генератор подкачки энтропии на базе отображения Арнольда // Известия вузов. Прикладная нелинейная динамика. 2009. Т. 17. № 6. С.57-66.

186. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography CRC, 1997. P.39-41.

187. Фергюсон H., Шнайер Б. Практическая криптография. Пер. с англ. М.: Издательский дом "Вильяме", 2005. С. 178-209.

188. Куприянов A.M. Основы зашиты информации : учеб. пособие для студ. высш. учеб. заведений / А.И.Куприянов, А.В.Сахаров, В. А. Шевцов. М.: Издательский центр «Академия», 2006. С.48.

189. Agnew G. В. Random Sources for Cryptographic Systems// Advances in Crvptology EUROCRYPT'8 7 Proceedings. Springer-Verlag. 1988. P 77-81.

190. Fairfield R. C., Moileiison R. I., Koullhan K.B. "An VSI Random Number Generator'VAdvances in Crypiology: Proceedings of CRYPTO 84, Springer Verlag, 1985. pp. 203-230.

191. T7001 Random Number Generator. AT&T, Dala Sheet, Aug. 1986.

192. Блинов А.Л., Молодченко Ж.А., Сотов Л.С., Харин В.Н. Генераторы случайных импульсов на базе модельного отображения «сдвиг Бернулли» // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2009. -Вып. 6. С.120-130.

193. Каток А. Б. , Хасселблат Б. Введение в современную теорию динамических систем с обзором последних достижений / пер. с англ. под ред. А.С.Городецкого. М.: МЦНМО, 2005. 464 с.

194. Кузнецов С. П. Динамический хаос. М.: ФИЗМАТЛИТ, 2001. 296 с.

195. Евтушенко Н. Д., Немудров В. Г., Сырцов И. А. Методология проектирования систем на кристалле. Основные принципы, методы, программные средства // «Электроника». 2003. №3. С.35-42.

196. Опадчий Ю. Ф., Глудкин О. П., Гуров А. И. Аналоговая и цифровая электроника. М.:«Горячая Линия — Телеком». 2000. 768 с.

197. Шустер Г. Детерминированный хаос: Введение. М.: Мир, 1988. С.115.

198. Хвалин A.JI., Овчинников C.B., Сотов JI.C., Самолданов В.Н. Первичный преобразователь на основе ЖИГ генератора для измерения сильных магнитных полей//«Датчики и системы», 2009. №10. С. 57-58.

199. Хвалин А.Л., Сотов Л.С., Овчинников C.B., Кобякин В.П. Экспериментальные исследования гибридного интегрального магнитоуправляемого генератора // Приборы и системы. Управление, контроль, диагностика, 2009. №11.

200. Хвалин А.Л., Игнатьев A.A., Сотов Л.С. Квазишумовые режимы магнитоэлектронных генераторов//Вопросы электромеханики. Том 113. №6. 2009. С.55-59.

201. Молодченко Ж. А., Сотов Л.С., Харин В. Н. Модуль генерации форматирующих сред в распределенных реляционных СУБД. Труды международного симпозиума НАДЕЖНОСТЬ И КАЧЕСТВО. Пенза:Изд-во Пенз.гос.ун-та, 2006. Том 1. С. 179-182.

202. Свидетельство об официальной регистрации программы для ЭВМ № 2004610988 (РФ). Программа расчета параметров модели Матерка полевого транзистора / Сотов Л.С. и др. Заявка № 2004610416. Зарегистрировано 21.04.2004.

203. Гуревич А.Г., Мелхов Г.А. Магнитные колебания и волны. М.: Фирма «Физ.-мат. литературы», 1994 г. С.574.

204. Свидетельство об официальной регистрации программы для ЭВМ № 2004610989 (РФ). Программа расчета параметров модели Гумеля-Пуна биполярного транзистора / Сотов JI.C. и др. Заявка № 2004610417, зарегистрировано 21.04.2004.

205. Сотов JI.C., Харин В.Н., Хвалин A.JI. Детекторы режимов функционирования генераторов случайных сигналов // Автоматика и телемеханика. 2010. №5. С. 166-170.

206. Мирский Г. Я. Электронные измерения. 4-е изд., перераб. и доп. М.: Радио и связь, 1986. С. 225.

207. Packard N. Н., Crutchfield J. P., Farmer J. D., Shaw R. S. Geometry from a time series // Phys. Rev. Lett. 1980. V. 45. P. 712-716.

208. Takens F. Detecting strange attractors in turbulence. Dynamical Systems and Turbulence / Eds D. A. Rand, L.-S. Young. Berlin: Springer, 1981. P. 366-381.

209. Sotov L.S., Kharin V.N., Khvalin A.L. Operation Mode Detectors for Random Signal Generators // Automation and Remote Control, 2010. Vol. 71. No. 5. P.876-880.

210. Сотов JI.C. Методы синтеза устройств, выполняющих инструкции перестановки битов данных // Гетеромагнитная микроэлектроника. 2011. Вып. 10. С.25-50.

211. Hilewitz Y., Lee R. A. New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations // IEEE Transactions on Computing. 2009. Vol. 58, № 8. P. 1035-1048.

212. Lee R.B., Rivest R.L., Robshaw M.J., Shi Z.J., Yin Y.L. "On Permutation Operations in Cipher Design/Proceedings of the International Conference on Information Technology (ITCC), 2004. V.2. P.569-577.

213. Shi Z. J. Bit Permutation Instructions: Architecture, Implementation and Cryptographic Properties, Phd., Princeton University, 2004.

214. OpenRISC 1000 architecture, http://opencores.org/openrisc,architecture (дата последнего обращения 21.01.2011).

215. USB Function IP Core Rev. 1.5/ Rudolf Usselmann. January. 27. 2002.

216. DDR Memory Overview, Development Cycle, and Challenges // Agilent Technologies. № 5990-3180EN, Printed in USA, December 19, 2008.

217. Брассар Ж. Современная криптология: Пер. с англ. — М., Издательско-полиграфическая фирма ПОЛИМЕД, 1999. С. 32-34.

218. Молодченко Ж. А., Сотов Л.С., Харин В. Н. К вопросу об архитектуре аналого-цифровых систем генерации случайных сигналов // Труды международного симпозиума НАДЕЖНОСТЬ И КАЧЕСТВО Пенза:Изд-во Пенз. гос. ун-та, 2007. С. 85-87.

219. Виноградов, А. С. Диодный генератор шума для радиометрической системы/ А. С. Виноградов, А. Н. Сычев // Электронные средства и системы управления. Опыт инновационного развития / Томск: В-Спектр, 2007. С.171-173.

220. Кушнир Ф.В. Электрорадиоизмерения / Энергоатомиздат. 1983. 320с.

221. Анищенко B.C., Т.Е. Вадивасова, В.В. Астахов. Нелинейная динамика хаотических и стохастических систем. Фундаментальные основы и избранные проблемы. Саратов: Изд-во Сарат. Ун-та, 1990. 368с.

222. Шеннон К. Математическая теория связи. М.: Изд. иностр. лит., Сб. Работы по теории информации и кибернетике. 1963. 830 с.

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

224. Prasun Ghosal, Malabika Biswas, Manish Biswas Hardware Implementation of TDES Crypto System with On Chip Verification in FPGA // Journal Of Telecommunications, Volume 1, Issue 1, February 2010. P. 113-117.

225. Kaps, J., Paar, C.: Fast DES implementations for FPGAs and its application to a Universal key-search machine. In: Proc. 5th Annual Workshop on selected areas in cryptography Sac' 98, Ontario, Canada, Springer-Verlag, 1998. P. 234-247.

226. McLoone, M., McCanny, J.: High-performance FPGA implementation of DES using a novel method for implementing the key schedule. IEEE Proc.: Circuits, Devices & Systems 150, 2003 P.373-378.

227. Wilcox, D., Pierson, L., Robertson, P., Witzke, E.L., Gass, K.: A DES asic suitable for network encryption at 10 Gbs and beyond. In: CHESS 99, LNCS 1717, 1999. P. 37^18.

228. Patterson, C.: High Performance DES Encryption in Virtex FPGAs using Jbits. In: Field-programmable custom computing machines, FCCM' 00, Napa Valley, CA, USA, IEEE Computer. Soc., CA, USA, 2000, 2000. P. 113-120.

229. Vishwanath P., Joshi R. C., Saxena A. K. "Fpga Implementation Of Des Using Pipelining Concept With Skew Core Key-Scheduling"//Journal of Theoretical and Applied Information Technology,March 2009,Vol. 5. No.3 P. 113-117.

230. Vikram Pasham and Steve Trimberger, "High-Speed DES and Triple DES Encryptor/Decryptor", Xilinx Application Note: Virtex-E Family and Virtex-II Series, XAPP270 (vl.0) August 03, 2001.

231. Ravi Budruk, Don Anderson, Tom Shanley PCI Express System Architecture. Addison-Wesley Professional. 2004. 1120 p.

232. Архангельский C.B. Информационный анализ цифровых сигналов. Из-во Саратовского университета, 1991. С.22-32.

233. Грушо А.А. Тимонина Е.Е. Теоретические основы защиты информации. Издательство Агентства "Яхтсмен". 1996. 245 с.1. С.

234. Wong, К., Wark, М., Dawson, Е.: A SingleChip FPGA Implementation of the Data Encryption Standard (des) Algorithm. In: IEEE Globecom Communication Conf., Sydney, Australia, 1998. 827-832.

235. URL: http://www.okbsapr.ru/akk55.html (дата обращения 15.09.2010).

236. US №7519795, МПК G06F9/30 Method and system for performing permutations with bit permutation instructions.

237. Pat. US 6952478 G06F 7/76 (20060101); 380/37 ; Method and system for performing permutations using permutation instructions based on modified omega and flip stages.

238. Жан M. Рабаи, Ананта Чандракасан, Боривож Николич. Цифровые интегральные схемы. Методология проектирования. М.:Вильямс, 2007. 912 с.