Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 17
Текст из файла (страница 17)
Таким образом, объем требуемыхресурсов напрямую зависит от длины вектора значений локальной функции связи, которая, в свою очередь, экспоненциально зависит от числа ееаргументов.При программной реализации длина вектора не играет существеннойроли, поскольку значения ячеек вычисляются последовательно и можетиспользоваться единственная таблица сопоставления. Тем не менее, времявычисления индекса в таблице сопоставления линейно зависит от количества аргументов локальной функции связи, т.
е. от мощности окрестностиячейки: чем меньше аргументов, тем быстрее может быть вычислен индекс.В предлагаемых генераторах на выход клеточного автомата подаютсязначения некоторого подмножества его ячеек. Увеличение числа.ячеек памяти позволяет повысить быстродействие аппаратной реализации (за счетпараллельности вычислений) ценой линейного увеличения объема требуемых ресурсов. При программной реализации-увеличение количества ячеекне оказывает влияния на быстродействие, а возрастание требований* к объему памяти является несущественным. Также следует учитывать, что увеличение числа ячеек оказывает негативное влияние на лавинный эффектв клеточных автоматах.Таким образом, можно сделать вывод, что наиболее эффективной-реализацией обладают клеточные автоматы с локальной функцией связи отнебольшого числа аргументов, а количество ячеек в автомате должно определяться заданным быстродействием и требуемыми характеристиками лавинного эффекта.3.2.БАЗОВЫЕГЕНЕРАТОРЫВ< структуру базового генератора на основе клеточных автоматов входят (см.
рис. 3.1):'- двоичный клеточный автомат С;- регистр сдвига с линейными обратными связями R длины 63.Выходная последовательность J3 регистра сдвига прибавляется по модулю 2 к значению одной из ячеек клеточного автомата и, таким образом,обеспечивает заданный период последовательности внутренних состояний-112-Клеточный автомат СРСЛОСЯ'Рис. 3.1. Структура базового генератора псевдослучайных последовательностей на основе клеточных автоматовавтомата. «Подмешивание» выхода РСЛОС сдвига к внутреннему состоянию генератора является достаточно распространенным приемом обеспечения заданного периода выходной последовательности и также использовалось, например, авторами поточного шифра Grain [35].Каждый член выходной последовательности ос базового генератора является 256-разрядным двоичным набором (т.е.
элементом множестваZ^ 56 )и формируется из значений определенного подмножества ячеек клеточногоавтомата С.3.2.1. Б А З О В Ы Й Г Е Н Е Р А Т О Р НА О С Н О В Е К Л А С С И Ч Е С К И Х К Л Е Т О Ч Н Ы ХАВТОМАТОВВ базовом генераторе на основе классических клеточных автоматов Симеет вид C(Z2,37 х П , ^ ? , / ) , т.е. является двумерным булевым клеточным автоматом с решеткой размера 37 х 11 и квазиполной окрестностьюрадиуса 1.
Для формирования выходной последовательности а генератораиспользуются значения ячеек, лежащих в определенной области решетки.3.2.1.1. О Б О С Н О В А Н И Е В Ы Б О Р А Р А З М Е Р Н О С Т И Р Е Ш Е Т К ИИТИПАОКРЕСТНОСТИВ качестве основного элемента базового генератора псевдослучайныхпоследовательностей используется двумерный клеточный автомат с квазиполной окрестностью "Ч/j радиуса г — 1.Одномерные клеточные автоматы были исследованы Стефаном Вольфрамом (см. разделы 2.1.1.1 и 2.1.2, а также [81-85]), не представляютсерьезного практического интереса и потому не рассматриваются.-113При увеличении размерности решетки мощность окрестности 4fr и,соответственно, число аргументов локальной функции связи / растет экспоненциально. Из табл. 4 видно, что длина вектора значений в клеточныхавтоматах с трехмерной решеткой превосходит 60 000 000 и не подходитдля аппаратной реализации, поэтому наибольший интерес представляютдвумерные клеточные автоматы.Значения.количества аргументов и длины вектора значений локальнойфункции / в двумерных клеточных автоматах в зависимости от радиусаг и типа окрестности также приведены в табл.
4. При г > 1 длина вектора значений / превышает 10000000, что делает реализацию клеточногоавтомата непрактичной.Как было показано в разделах 2.1.4 и 2.1.5, клеточные автоматы снеполными окрестностями обладают существенными недостатками, такими как слабо выраженный лавинный эффект и^ повышенная вероятностьвозникновения пространственных периодов. Свойства же автоматов с квазиполными и полными окрестностями практически не различаются, поэтому в целях повышения эффективности реализации используются квазиполные'окрестности W®.Таким образом, использование клеточных автоматов с двумернымирешетками ячеек памяти и квазиполными окрестностями Wi радиуса г = 1является, на наш взгляд, наиболее предпочтительным.3.2.1.2.
О Б О С Н О В А Н И Е В Ы Б О Р Р А З М Е Р А Р Е Ш Е Т К И И СПОСОБА ФОРМИРОВАНИЯВЫХОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИРазмер решетки двумерных клеточных автоматов выбран равным37 х 11 ячеек. Использование простых чисел в качестве линейных размеровпозволяет снизить вероятность возникновения пространственных периодов(см. раздел 2.1.5). Для хранения внутреннего состояния клеточного автомата в таком случае требуется 407 бит памяти, а максимальный период последовательности внутренних состояний составляет Ттах — 2 4 0 7 и 3,3 • 10 1 2 2 .Для формирования выходной последовательности клеточного автомата используются значения ячеек подрешетки размера 32 х 8 (см.
рис. 3.2),т.е. ячеек с координатами (х,у), удовлетворяющими условиям 0 ^ х < 32Таблица 4.Зависимость длины вектора значений локальной функции связи от размерности решетки, типа и радиусаокрестностиРазмерностьрешеткиРадиусокрестностиТипокрестностиКоличествоаргументов функцииДлина векторазначений1квазиполная8256512полнаяквазиполная241,7 • 10 7полная253,4 • 10 7квазиполная482,8 • 10 1 4полная495,6 • 10 1 4квазиполная266,7 • 107полная271,3 • 108квазиполная1242,1-10,37полная125,374,2 • 10квазиполная3429,0-10 102полная3431,8-10 103i-1150Ш,ШAAAУ//шА/А///А/wV/Vi31•••1AAA'/уУ/АAAA///'AAs AAA AAAAAA y/y AAA /A/AAA/ / / AAA/A/ vvv '///.
"AAA/AAAAAA7//A'A/ / / s'ШУ/у///yA,A / A .A /AШШJ'-%,%.I* A/ fШ%A,* s A/AjA/sA A /%П%'iLУАА AAA///,УУ. 'AAAA/ A'/// AAA,A A/' / // Ш '/У/,AAA/,Ал/УЛАА А у••• 36mzy ш /A '//A,'•///\32m•It,/AA°oу1*'/A A'As•—<-•1''1r•fL;„;132'\37.4* •Р и с . 3.2. Формирование выходной последовательности двумерного клеточного автомата (штриховкой обозначена область решетки, скоторой осуществляется съем значений ячеек)и 0 ^ у < 8. Каждый член <xt выходной последовательности клеточногоавтомата является 256-элементным двоичным вектором из множестваZ^ 56 ,значение которого определяется следующим образом:m<** = [Щ0,0),П (lfl),t>тт• • • ( З Д , г > (0,1),Ь • • • ""1(31,7),*])где m{x,y),t — значение ячейки клеточного автомата с координатами (ж, у) вмомент времени £.Такой выбор размера решетки и способа формирования выхода является на наш взгляд оптимальным и обеспечивает выработку клеточнымавтоматом 256 бит выхода за один такт работы.
Дальнейшее увеличениескорости работы путем наращивания размеров решетки создает проблемы при аппаратной реализации, поскольку требует применения шины данных большой разрядности. Уменьшение же размера приводит к снижениюбыстродействия и является неоправданным.- 116Использование в качестве выхода значений только части ячеек решетки клеточного автомата позволяет затруднить восстановление внутреннего состояния генератора по известной выходной последовательности: съемзначений не осуществляется со 151 из 407 ячеек памяти, а для восстановления их значений методом перебора требуется 2 1 5 1 ^ 1,8 • 10 4 7 опробований.3.2.1.3.ОБОСНОВАНИЕ ВЫБОРА ЛОКАЛЬНОЙ ФУНКЦИИ СВЯЗИВ разделе 2.1.3 было показано, что равновероятное распределение значений'ячеек памяти и, следовательно, хорошие свойства выходной последовательности достигаются только при'условии равновесности локальнойфункции связи /.
Для повышения линейной сложности выходной последовательности и улучшения ее статистических характеристик локальнаяфункция связи также должна являться нелинейной.Мы используем в качестве локальных функций связи равновесные булевы функции, вектор значений которых был получен случайным образом (при помощи некоторого генератора псевдослучайных чисел). Возможность применения конкретной функции / в качестве локальной функциисвязи клеточных автоматов определяется эмпирически по результатам статистического тестирования генератора (см. главу 4).3.2.1.4.ОБОСНОВАНИЕ ВЫБОРА ПАРАМЕТРОВХОДНОЙРСЛОСИ ПЕРИОДА ВЫПОСЛЕДОВАТЕЛЬНОСТИОдной из основных проблем при использовании клеточных автоматов в составе генераторов псевдослучайных последовательностей являетсянепредсказуемость их периода, связанная с нелинейным характером локальной функции связи /.Для обеспечения минимального гарантированного периода выходнойпоследовательности генератора мы вводим в схему регистр сдвига с линейными обратными связями.
Выход регистра сдвига на каждом такте работы прибавляется по модулю 2 к значению ячейки клеточного автомата скоординатами (34,9) (см. рис. 3.3). Выбор ячейки обусловлен ее расположением на максимальном расстоянии от ячеек, с которых осуществляетсясъем выходной последовательности. Таким образом, выход регистра сдвига не фигурирует в чистом виде на выходе генератора, что существенно-117-У/У.У/ УУУ '/У/ У/УУУ/ У//У/У/Уу/уУУ/ УУУ'УУ/' У У у/УУ<•'' У У .•УУУ/УУ У/У/ УУУУi " '1*s/sУУ// УууууУУУ' У У/ ' У У УУ{i-//ууУ У у//У/ //у-ЯJ1'-?Ш•'У'У'у-У SУУУШ/ШУ/УУУУУ •ужш,У У У . ууууУУУ/УУ / / / . <У/У/УУ' У У / У/У/УУУ $'УУ/У/у?S™Ф*J *Г'f:1у"У,'/У,У/У/у //.У/У, '.У У Уу' //УУ/ /УУ У// /у/у/ /у/..УлшУ/У.' //У У У/у у/ ///7/У/У,УУУ,/УУУУУУ/У.
'УУ/ У/Ут щш шУ//34У У У ' S ' .'•£L"ОГ^ТТГЛГ*Рис. 3.3. Сложение выхода РСЛОС со значением ячейки клеточного автомата' .затрудняет восстановление значений ячеек регистра по известной последовательности а .Выходная, последовательность (3 регистра R является периодическойс некоторым периодом TR. Наличие лавинного эффекта в клеточных автоматах него характеристики (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
