Генератор нелинейных двоичных последовательностей максимальной длины Советский патент 1987 года по МПК G06F1/02 

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

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

Поставленная цель доет игается за счет того, что предлагаемое устройство генерирует нелинейшзШ: двоичные последовательности длины 2 (циклы де Брейка, в которьпс встречаются все п-мерные двоичные векторы) пз тем объединения циклов, длины которых не превосходят По Такую совокупность циклов (обозначим ее R) при различ- ных начальных состояниях регистра поро дает циклический п-разрядный регистр сдвига, у которого выход первого разряда подключен к входу последнего (). Объединение хщклоБ осутцест- вляется посредством перехода от одного цикла к другому с пo aoш;ыo пар сопряженных векторов (сцй), опреде- ляемьЕЧ как

01 ( «-,5,

.«г

где (2)5 « а. © - суъта по модулю 2 Для осуществления подобных переходов сопряженные векторы а и & принадлежать различным циклам Число циклов совокупности дхгань которых являются делителями п определяется выражением

iR.i -™ 2:4(d)

где ц функция Эйлера с Вес вектора а ( а., , а,,. . . г а,) определяется как

W 2. «i

i

цикла из R

Очевидно, веса векторов

одинаковы, Следоваталь- ноJ любой из векторов произБольного цикла из может сллшить в кггчестве представителя сопряженной пары векторов для объединения его с другим дик- noMf так как сопрял енный к этому вектору отличается от него по весу на 1 и. находится вне рассгадтриваемогэ цикла,

Для объединения циклов совокупности RH в цикл длины 2 с помощью

пар сопряженных векторов достаточно в каждом.цикле в качестве представителя сопряженной пары выбрать произвольный вектор й ( 5 . ) при произвольном фиксированном значении с/ Справедливость сказанного следует из того факта, что при указанном выборе представителей сопряженных пар циклы с весами векторов i( . о . 5П-1 при и 1 1525.,. J о . эП при 0) будут объединяться с циклами с весами векторов i+1 при или с циклами с весами векторов i-l при (, исчерпывая совокупность Число переходов по сопряженным парам при генерации цикла де Брейна равно поскольку только один цикл, состоящий из единственного вектора (15 S , . , 1) при или (О 5 О 5. ,, . :, . эО) при не содержит вектора а ( S S о „ 5 ч,), Зо время перехода от одного цикла к другому происходит изменение веса w, Вектор следующий за представителем сопряженной пары, отличается от него по весу на 1, В каждом цикле с весами векторов w имеется w векторовj у которых и соответственно n-w векторов, у которых , Ч :-1Сло L различных вариантов выбора векторов о (о з « 5 «, 5, ,. , о . 5 d,) по одному в ка/эдом цикле оценивается выра ением

L 7, П (n-w)

,Ln- CM

()

где L X J обознач:ает наибольшее целое числоS не превосходящее х. Равенство в выражении (1) достигаетсяj напрИ мер5, когда п - простое число. Выбор представителей сопряженных пар при генерации цкрсла де Брейна осуществля ется следуюш;1- М образом. Пусть а. - экстремальный по значению вектор (минимальный при или максимальный а. прИ1/ ) в каждом цикле. Представителем сопряженной пары выбирается вектор являющийся k-м ци1слическим сдвигом а.. . При этом учитываются лишь те сдвиги, в результате которых символ с(с . Число k мо- жет быть„постоянным для всех циклов R ,, а может задаваться в виде функции - о т U р X t

k f() ™)« 2 где ) при с 1 и при . Приведение по модулю m осуществляются с целью сокраш.ения времени поиска пред ставителей сопряженных пар. Область

313222А54

значений функции f зависит от веса Например, можно предложить, следующее W. Для различных значений w можно задание линейных функций для случая задавать различные функции )

Oj если ,n-l,n; Г 5.

ieQ с(к2,...,п-2)

w

мин)

я, ,п-1, если ,2,,..,п-3; Г. 5,

ieR(l,2,... ,U/2J)

S- , , n-l, если .

задание функций для

О, если ,1,п;

ieQwS(U2,...,n-2)

ysj W макс/

q, , n-l, если ,4,...n-l; (4)

r,..

i6R(l,2Ln/2a)

c(., , n-l, если .

Очевидно, что функция f может быть также нелинейной.

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

2(п-1)(2

n-Ln(aj

п-з

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

45

.2)П (n-rn/w1-l) . -1

элементов 1ШИ, блоки 13 и 14 логических элементов из (п-1) элементов И, блок 15 логических элементов из п элементов И, блок 16 логических элементов из 2п элементов И, логи- фиг. 3 - импульсная диаграмма работы , ческий элемент ИЛИ 17, логические узла управления. элементы И 18 и 19.

Устройство (фиг. 1) содержит гене- Узел 5 управления (фиг. 2) содер- ратор 1 импульсов, п-разрядный регистр 2 сдвига, сумматор 3 по mod 2, формирователь 4, узел 5 управления, , два п-гразрядных циклических регистра 6 и 7 сдвига, компаратор 8, счетчик 9, дешифратор 10, делитель 11,

жит триггеры 20-25 и счетчик 26, а также логические элементы ИЛИ 27-30 и логические элементы И 31-40.

Из импульсной диаграммы (фнг. 3) видно, что частота тактовых импульсов t формирователя 4 в Зп раза пре- вьшает частоту импульсов ГИ генератоблок 12 логических элементов из п

(3)

последовательности одного множества соответствует инверсная к ней после- 5 довательность другого множества, а мопцюсть обоих множеств одинакова и оценивается выражением (1). Количество циклов де Брейна, порождаемых с применением функции (3) или (4) оценивается величиной

40

45

,

Узел 5 управления (фиг. 2) содер-

жит триггеры 20-25 и счетчик 26, а также логические элементы ИЛИ 27-30 и логические элементы И 31-40.

Из импульсной диаграммы (фнг. 3) видно, что частота тактовых импульсов t формирователя 4 в Зп раза пре- вьшает частоту импульсов ГИ генератоpa 1, Логические схемы срйбатызают передним фронтом поступ. кмпуль са (переход с низкого уровня на 1зы- сокий)5 а триггеры перекидываются задним фронтом (переход с высокого уровня на низкий). Все импульсы,, перекидывающие триггеры (кроме установочных ГИ)5 поступают на их счет- jHbse входы.

Задание функции (2) для генерации азличных носледовательностей ствляется депшфратором Юр который имеет п-1 входов и выходов.

В дальнейшем излолсении для опре-- деленности примем , а блоки 8 ,,10 и 11 срабатывают за период одного тактового импульса.

Устройство (фиг, 1) работает следук1щим образоМо Импульс ГИ на вь:- коде генератора поступает пэ тактовый вход п-разрядного регистра 2;. осуществляя сдвиг влево кв. один: разряд с занесением в разряд 2.,, символа с выхода сумматора 3 и выдачей с лы хода разряда 2 очередпогс символа поСочедовательности на вькод застрой- ства и нгг первый вход суь«-.атора 3, на установочный вход счетчика. 9,, через вход узла 5 у.правления (фиг, 2) на установО Гнъш в.ходы триггеров 20-2.5 и счетч.ч:ка 26. устанав-- лив.ая триггеры в исходное состояние (при котором схеь-Пз И 31 и 32 откра- Tbs для прохожде.ния с):- гнала5 а схемы И 33-38 заперты) и зап.исывая в счат- чиках 9 и 26 чиапо п. Пос.пе у станов- . кк схемы импульс ГК своиь задним фро том запускает формирователь 4э выра- батываю1 1 1Й тактовые импульсы, поступающие на вход, 5,| узла 5 з правления На выходе 5„ узла управлещ- я гюяв.ггя-- ется первый импульс г, (сотгг. 3).j который производит перезапись гистра 2 двоичного вектора (о: а, « ., cXj) , ие включающего символ (разряд 2), в соответствующие разря ды регистров б и 7 через логические блоки 12 и 13 (для регистра б) и 14 (для регистра 7), а также устаиав-- ливает О в разрядах 6, (через схему 52) и 7.. В обоих регистрах уста

навливается вектор л (О, а,, ,,. „ Далее определяется минимальный п.о значению вектор oi,,,. среды циклических сдвигов с/. Импульс T.J с выхода 54 узла управления поступает на тактовый вход регистра 7„ осуплествляя циклический сдви:г влево на один разряд в результате которого в регистре 7 устанавливается вектор а (« , , , , ,м, jO) , Одновременно импульс t поступает на счетный вход счетчика 26 узла 52 где текущее число становится равным п-1. Следхтощий импульс

появляется на выходах 5 и 5

g

С выхода 5 импульс поступает на входы логических элементов блока 16 а также на тактовый вход компаратора 8j который по переднему фронту i-2, производит сравнение векторов а аи с1 поразрядно поступающих с регистров б и 7 на компаратор через элементы логического блока 16, С вь:хода 5 импульс ь , поступает на вход J

элемента. И 1 9 „ ие разряда 1

В случае., если значе регистра 7 равно j

импульс t проходит через элементы

0 И 19 и ИЛИ 17 на счетнь5Й вход счетчика 95 делая его текущее значение равным п-1 , Одновременно импульс i проходит на выход .КО (конец операции) компаратора 8 поступая на вход

i 5 узла. 5s а таклсе на выход (d ),

ecjTH вектор регистра 6 равен вектору регистра 7 и поступает на вход 5 узла 5 или на выход (о 7 о ), ес- ;ЛИ удовлетворяется указанное нера30 земствоS производя своим задним фронтом через блоки логических элементов 15 и 12 перезапись содерлсимого регистра 7 в регистр 6, Далее с появлением импульса 1 J который с выхода 5, ла управления поступает на тактовый :зход регистра 7, осуществляя цик- л::1 ческий сдвиг влево на разряд (а в узле 5 Т поступает на счетчик .26, де.лая текущее число равным п-2)5 описапный процесс повторяется еще П--2 раза,. В результате чего в регист™ ре 6 устанавливается вектор СУМИНЕ а в счетчике 9 - число (w вес вектора ) 3 которое одновременно устанавливается в блоке 1I в качестве делителя,, На следующем этапе опреде- ;11я:ется величина k - число циклических сдвигов вектора с ,,,, j после ко- Topbix в регистре 6 устанавливается 5::ско ий представитель сопряженной пары векторов; При зтом величина k учитывает лишь те с,цвиги, в результате которых в разряде 6 регистра 6 устанавливается ноль. На тактовый :ij ВХОД регистра 7 с выхода 5, а также на вход счетчика 26 узла 5 поступает п-й по счету импульс tjf, , кото- рый устанавливая в регистре 7 первоначальный вектор У (0 , , , , , ,, OfJ ,

::(

li

а в счетчике 26 - ноль, с выхода 5 поступает н-а тактовый вход дешифратора 0. При этом на выходе дешифратора 10 появляется число г, которое устанавливается в блоке 11 в качест- ве делимого.

Следующий импульс с 2п --г выхода Sg узла управления поступает на тактовый вход делителя 11, который вычисляет значение k г(mod m) и про-, изводит запись вычисленного значения k в счетчик 9 Импульс появляется на выходе КО блока 11 и поступает на вход узла управления,- Он же появляется на выходе КО счетчика 9 и поступает на вход 5 узла управления j если , В этом случае искомым представителем сопряженной пары является минимальный вектор d . регистра 6 5 который на следующем этапе-- сравнивается с вектором -oi регистра 7 с появлением на выходе 5-, узла управления тактового импульса (в данном случае j). Если же k О то на выходе КО счетчика 9 появляет- ся по счету импульс, поступивший на его счетный вход. Это происходит следующим образом, С выхода 5 узла управления на тактовый вход регистра 65 а также на вход элемента И 18 поступает следуюп;ая последовательность импульсов: . « - 2 4-3 9 + i+i которые осуществляют j циклических сдвигов влево регистра 6 и проходят через схемы И 18 и МИ 17 на счетньш вход счетчика 9, если при очередном Появлении тактового и шyль- са значение разряда 6. регистра 6 равно О о Очевидно, что k j и 16 . j . Таким образом, импульс выхода КО счетчика 9 поступает на вход 5 узла управления„ Следующий импульс i.j с выхода 5 поступает на.входы логических элементов блока 165 а также на тактовый вход компаратора 8j который осуществляет сравнение векторов и и а. Он же с выхода КО компаратора 8 поступает на вход узла управления и с выхода 5 узла управления на второй вход формирователя 4$ приостанавливая своим задним фронтом подачу тактовых импульсов. Если а « j

то импульс ,4l f-2

появляется на выходе () компаратора 8 и посту- пает ла вход 5 узла управления, а также на выходе 52 узла управления и поступает на второй вход сумматора 3 по модулю 2. На выходе сумматора

устанавливается символ а, ®1 (и, - символ разряда 2 регистра 2). Б противном случае, -если а ф У: , импульс t, . на выход () не проходит и соответственно на сумматор 3 не поступает, в результате чего на выходе сумматора 3 устанавливается символ .

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

Формула изобретения

1, Генератор нелинейных двоичных последовательностей максимальной длины, содержащий генератор импульсов, сумматор по модулю два н п-разрядный регистр сдвига, причем выход первого разряда регистра сдвига подключен к первому входу сумматора по модулю два, выход которого подключен к входу п-го разряда регистра сдвига, к тактовому входу которого подключен выход генератора импульсов, выход первого разряда регистра сдвига под- ключен к выходу генератора, отличающийся тем, ЧТО, с целью расширения класса порождаемьпс нелинейных последовательностей максимальной длины, в него введены два элемента И, счетчик, элемент ИЛИ, делитель, дещифратор, компаратор, два п-разрядных циклических регистра сдвига, блок из п элементов ИЛИ, два блока из (п-1) элементов И, блок из п элементов И, блок из 2п элементов И, формирователь тактовых импульсов и узел управления, причем тактовый вход узла управления подключен к выходу формирователя тактовых импульсов, первый вход которого подключен к выходу останова узла управления, . вход установки которого, установочный вход счетчика и второй вход формирователя импульсов подключены к выходу генератора импульсов, выходы признаков готовности счетчика, делителя и компаратора подключены к входам признаков конца операции счета,конца операции деления и конца операции сравнения узла управления, вход признака Равно которого подключен к выходу признака Равно компаратора, выход раз- рещения суммирования узла управления подключен к второму входу сумматора по модулю два, первый выход управлеНИЛ сдпигом узла упра, подключен к TaKTOBOJ-fy вхсдз петжсг о а-раз-- рядного циклического регистра сдрига и первому входу первого элемента И, второй вход которого подк.п очет- к ян-- версиому второго разряда первого а-разрядного ци :лического регистра сдвига5 второй вылад управле- .ния c /i Bi-iroM узла управ, подключен к тактовому входу второго п-разряг - (Ного 1тиклического регистра сдвига,, выход разрешения дешифраци - узла управления подключен к тaктoиo гy входу дешифратора.; выход которого подключен к входу Делимого делителяj вкод Делителя подключен к выходу счетчик вход установки исла сдвигоп KOTOJIOTO подключен к выкоду денителя, тактовый вход которого подключен к пыходу ра.:;:- решепкя деления уэна. упра1злеиия. ход разрелшния сраппения к:оторого по,|;гклк) 5еи к такт овому Kxoj/y компара-- тора к первым входам элe iг::U -oл И блока КЗ 2п элементов Р1;, зыхо;д nepeii;-.cri: узла управления подклто ек к пепгым входам элементов И первого и второго блоков из (п--1) элемеуггов И, к входу первого разряда второго п-раэуяднсго juncj H4ocKoro рег мстру сдвига и к перном первого элемента И. блока и;; п. элементов ИЛИ, пыход у .;оавлеккя счс- тон узла управления гуодклкг зн к iioiiy :;оду зторого зле К:Нта И„ вьгход KsjTOjioro подключен к ;jep}3OMy входу йлеме}1та ИЛИ, второй ко -орого подкчто ея к выходу зтег-кзого олеметгга И, выход элемента HJlii но;:гкл:ачеп к счетному входу счетчикар оыходы с второго по п-й ;5а.:.рядов региетаа сдвига подключепь; к вторым зходаь: злемеь;выходы элементов И пер лого блока из (n-l) элементов И подключен : к входам элемечтоп ИЛИ с второго по п-й блок из п злс;-1ентох7 ИЛИ „ зто-- рЫЕ входы злемет-ов iJffl которого по,; - ключены к выходa.:i элел е:;тов Р блока пэлемен ,гов И, выхо/у- эле -гегггоз ЕПИ блока из п элементов ИЛ1: подклю-- чены к ттнформациотгным ихода ; циклического регистра сднигт,, иьчсо-- ды которого подключены к птсфым вхо-- дам элеЬ ентоз И с первого не n-ii ка из 2и элементов И,, втооь е входы злементов И с (п--)-го по которого и пйрБые входы злеметгт ов И бло ca из п элементов П п опк.ггю- ег Ы к вь:-- второго пккл(ческого рестгстра

510

с-двига выход первого разряда которого подключен к втором, входу второго элемента И вход дешифратора подключен к выходам с второго по п-й первого циклического регистра сдвига5 вторые входы элементов PI блока из п элементов И подключены к выходу Больше компаратора, вход первого операнда которого подключен к выходам элементов И с первого по блока из 2п элементов И, выходы элементов И с (п+)-го по 2п-й которого подключены к входу второго операнда компаратора выходы элементов И второго блока и.з (п-1) элементов И подключены к входам с второго по п-й второго циклического регистра сдвига.

2, Генератор по п,

о т л и ч: а ю щ и и с я тем. что узел управления содерлс т шесть триггеров j счетчик, четыре элемента РШИ десять злементов И, п-рнче: установки :icex триггеров и установочньгй вход счетчика объединены и подключены к входу з- становки узлЯз тактовый вход которого подключен к первым входам первого5 ВТОРОГО;, третьего5 четвер- и пятого элементов И прямой выход первого триггера подключен к вто- року входу первого элемента И, выход которого подключен к информационному входу первого триггера и выходу перезаписи узла.;инверсный выход первого тк;итгера подключен к второму входу второго элемента HjTpeTHU вход которого .1.;одключен к прямому выходу второго триггера,, инверсный выход, которого подключен к второму входу третьего элоэмента Hj. третий вход которого и четверть й вход второго элемента И подключены к прямому выходу третьего триг герар информационный вход которо- го подключен к выходу первого элемен- га ПЛИ J первьЕй вход, которого объеди- пя); с первым входом второго элемента iiK выходом и является 1 ь ходом разрешения дешифрации узла, второй вход первого элемента ИЛИ и 1: ерсный вход шестого элемента И прямой вход седьмого элемента И и информационный вход четвертого триггера подключены к входу признака ксзнца операции счета узла, второй 1зход второго элемента ШШ, прямой зход шестого элемента И и инверсный - ХОД седьмого элемента И объединены и подключены к входу признака Конец

операции деления узла, вход признака Конец операции сравнения которого подключен к первому входу восьмого элемента И и первому входу третьего элемента ИЛИ, второй вход которогоj счетньзй вход счетчика и второй выход управления сдвигом узла подключены к выходу второго элемента И,пятый вход которого и первый вход девятого элемента И подключены к прямому выходу четвертого триггера, инверсный выход которого подключен к второму входу восьмого элемента И и первому входу десятого элемента И второй вход которого подключен к входу признака Равно узпа выход третьего элемента ИЛИ подключен к информационному входу второго триггера 5 выход второго элемента ИЛИ подключен к информационному зходу пятого триггера,, инверсный выход которого подключен к

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

Изобретение относится к вычислительной технике и может использо- ваться в схемах кодирования, идентификации, кольцевого тестирования дискретных устройств, защиты информации от несанкционированного использования в качестве генератора псевдослучайной последовательности. Цель изобретения - расширение класса порождаемых нелинейных двоичных последовательностей максимальной длины. Устройство содержит генератор 1 импульсов, п-разрядный регистр 2 сдвига, сумматор 3 по mod 2, формирователь 4, узел 5 управления, два п-разрядных циклических регистра 6,7 сдвига компаратор 8, счетчик 9, дешифратор 10, делитель 11, блок 12 логических элементов из п элементов ИЛИ, блоки 13, 14 логических элементов из п-1 элементов И, блок 15 логических элементов из п элементов И, блок 16 логических элементов из 2п элементов И, логический элемент ИЛИ 17, логические элементы И 18и 19. 1 з.п. ф-лы, 3 ил. i сл fu.i () КО в

СЧ1

C4J

fjsj

ГО

Составитель С, Курош Редактор А. Вррович Техред А.КравчукКорректор Л, Пилипенко

Заказ 2864/44Тираж 672 .Подписное

,ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4

J

Cvj

P3

o: «3