Генератор псевдовипадкових двійкових послідовностей

Генератор псевдовипадкових двійкових послідовностей, який містить першу, другу та третю групи регістрів зсуву, з'єднаних з входами двовходових елементів "І", виходи яких з'єднані з відповідними входами суматорів по модулю два, C2 2 (13) 1 3 вдання початкового стану та шину "Установка". Виходи m n - входових та n m - входових суматорів по модулю два з'єднані з першими входами відповідних регістрів зсуву. Вихід генератора тактових імпульсів з'єднані з другими входами регістра зсуву. Перші входи двовходових елементів "І" групи з n×m двовходових елементів з'єднані з відповідними виходами регістрів зсуву. Другі входи двовходових елементів "І" групи з n×m двовходових елементів з'єднані з відповідними виходами першої групи виходів блока керування, друга група виходів якого з'єднана з відповідними першими виходами елементів "І" m груп по n двовходових елементів. Третя група виходів блока керування з'єднана з відповідними першими входами елементів "І" n груп по m двовходових елементів. Виходи відповідних розрядів регістрів зсуву з'єднані з відповідними другими входами елементів "І" груп по n та m двоходових елементів "І" відповідно, виходи елементів "І" яких з'єднані з відповідними m n - входових та n m - входових суматорів по модулю два. Відомий генератор дозволяє одночасно генерувати псевдовипадкові числа різних числових послідовностей і матриць та керувати параметрами послідовностей, що генеруються. Кількість різних числових послідовностей одного періоду, що генеруються відомим генератором, зумовлена обмеженою кількістю початкових станів, внаслідок завдання початкових станів тільки на елементах головної діагоналі матриці початкових станів. В основу винаходу поставлена задача створення генератора псевдовипадкових послідовностей, у якому з'єднання блоку завдання початкового стану з кожним з елементів регістрів зсуву та нове конструктивне виконання регістру зсуву забезпечують збільшення кількості різних послідовностей одного періоду, що генеруються. Поставлена задача вирішується тим, що в генераторі псевдовипадкових послідовностей, який містить першу, другу та третю групи регістрів зсуву, з'єднаних з входами двохвходових елементів "І", виходи яких з'єднані з відповідними входами суматорів по модулю два, які з'єднані з входами відповідних регістрів зсуву, генератор тактових імпульсів з'єднаний із синхровходами регістрів зсуву, шину "Установка", з'єднану з блоком завдання початкового стану, виходи якого з'єднані з елементами регістрів зсуву, двовходові елементи "І" групи з двовходових елементів, перші входи яких з'єднані з відповідними виходами регістрів зсуву, другі входи яких з'єднані з відповідними виходами першої групи виходів блока керування, друга група виходів якого з'єднана з відповідними першими виходами елементів "І", згідно винаходу, перша, друга та третя групи регістрів зсуву складаються з n-1, 1, n-1 регістрів зсуву відповідно, n двовходових елементів "І" об'єднані в n груп, виходи блоку завдання початкового стану з'єднані зі всіма елементами регістрів зсуву, при цьому елемент регістру зсуву складається з суматора по модулю два, до входів якого підключені виходи елемента "І" та D тригера, до того ж елемент регістру зсуву має три 86401 4 входи, два з яких є входами елемента "І", а третій - входом D-тригера, та один вихід, що є виходом суматора по модулю два. З'єднання у відомому генераторі блоку завдання початкового стану генератора псевдовипадкових послідовностей з кожним з елементів регістрів зсуву дозволяє завдавати початковий стан на всіх елементах матриці початкових станів. З'єднання блоку керування з входами n груп по n двовходових елементів "І" забезпечує завдання значень коефіцієнтів. Виконання елементу регістру зсуву дозволяє реалізувати зсув елементів матриці, що приводить до збільшення кількості різних послідовностей одного періоду, що генеруються. Суть винаходу пояснюється кресленнями, на яких подано: Фіг.1 - схема генератора псевдовипадкових двійкових послідовностей; Фіг.2 - схема регістру зсуву генератора псевдовипадкових послідовностей; Фіг.3 - елемент регістра зсуву; Фіг.4 - фрагмент регістру зсуву генератора псевдовипадкових двійкових послідовностей; Фіг.5 - приклад виконання генератора псевдовипадкових двійкових послідовностей, де n=3; Фіг.6 - часові діаграми роботи генератора псевдовипадкових двійкових послідовностей за Фіг.5. Генератор псевдовипадкових двійкових послідовностей (Фіг.1) містить першу (I), другу (II) та третю (III) групи регістрів (1) зсуву по n-1, 1, n-1 регістрів зсуву відповідно, n груп (2) по n двовходових елементів "І", n×n - входових суматорів (3) по модулю два, генератор (4) тактових імпульсів, блок (5) керування, блок (6) завдання початкового стану, шину (7) "Установка" та групу (8) з n×n двовходових елементів "І". Виходи регістрів 1 зсуву з'єднані з відповідними входами відповідних елементів "І" групи 2, крім того виходи першої групи регістрів 1 зсуву з'єднані з входами третьої групи регістрів 1 зсуву, виходи елементів "І" групи 2 з'єднані з відповідними входами суматорів 3 по модулю два, які з'єднані з входами відповідних регістрів 1 зсуву, вихід генератора 4 тактових імпульсів з'єднаний із синхровходами регістрів 1 зсуву, виходи блоку 6 завдання початкового стану з'єднані зі всіма елементами регістрів 1 зсуву, шина 7 "Установка" з'єднана з блоком 6 завдання початкового стану, виходи регістрів 1 зсуву з'єднані з групою. Перші входи двовходових елементів "І" групи 8 з n×n двовходових елементів з'єднані з відповідними виходами регістрів зсуву. Другі входи двовходових елементів "І" групи 8 з n×n двовходових елементів з'єднані з відповідними виходами першої групи виходів блока 5 керування, друга група виходів якого з'єднана з відповідними першими виходами елементів "І" n групи 2. Вихід j-ого розряду і-ого регістра зсуву (j=1,2,…, і; і=1,2,...,n-1) першої групи i-розрядних регістрів зсуву (i=1,2,...,n-1) з'єднаний з j-им входом n груп по n двовходових елементів "І", вихід k-ого розряду n-ого регістра зсуву (k-1,2,...,n ) 5 86401 другої групи n - розрядних регістрів зсуву з'єднаний з k-им входом n груп 2 по n двовходових елементів "І", вихід q-ого розряду l-ого регістра зсуву (q=1,2,...,р; р=2n-l) третьої групи р - розрядних регістрів зсуву з'єднаний з q -им входом n груп 2 по n двовходових елементів "І", виходи n груп 2 по n двовходових елементів "І" з'єднані з відповідними входами відповідних n - входових суматорів 3 по модулю два. Генератор містить у якості елемента регістра зсуву елемент (Фіг. 3), що має три входи, два з яких (1, 3) є входами елемента "І", а третій (2) входом D-тригера, та один вихід суматора по модулю два, з'єднаних у такий спосіб, що виходи D-тригера та елемента "І" є входами суматора по модулю два: éan-1 an - 2 an- 3 ê 0 0 ê 1 S[i + 1] = ê 0 1 0 ê ... ... ê ... ê 0 0 0 ë é n ê å an-k × Skn êk =1 ê S1n ê =ê S2n ê S3n ê ê ... ê Snn ê ë ... a1 a0 ù éS11[i] ú ê 0 0 ú êS21[i] ... 0 0 ú × êS31[i] ú ê ... ... ... ú ê ... ... 0 0 ú ê Sn1[i] û ë ... Таким чином, регістр зсуву складається з послідовно з'єднаних елементів (Фіг.4), що являють собою діагоналі структурної матриці. Генератор псевдовипадкових двійкових послідовностей працює таким чином. За допомогою блока 6 завдається початковий стан кожного елемента регістрів зсуву. Потім за допомогою блоку 5 керування задаються значення коефіцієнтів, які надходять до відповідних входів n груп по n двовходових елементів 2 "І". Імпульси з тактового генератора 4 потрапляють на синхровходи регістрів 1 зсуву. Генерація псевдовипадкових двійкових послідовностей відбувається у відповідності з матрицею S[i + 1] = А • S[i] • А-1, тобто S12 [i] S13 [i] ... S1n [i] ù é 0 1 0 ú ê S22 [i] S 23 [i] ... S2n [i]ú ê 0 0 1 S32 [i] S33 [i] ... S3n [i]ú × ê 0 0 0 ú ê ... ... ... ... ú ê... ... ... Sn2 [i] Sn3 [i] ... Snn [i]ú ê 1 an-1 an - 2 û ë n k =1 n n k =1 n 6 å an-k × Sk1 + an-1× å an-k × Skn å an-k × Sk2 + an -2 × å an-k × Skn k =1 S11 + an -1 × S1n S21 + an -1 × S2n k =1 ... ... 0 ... 0 ... 0 ... ... ... a2 0ù ú 0ú 0ú = ú ... ú a1ú û n n k =1 k =1 S12 + an- 2 × S1n S12 + an- 2 × S1n ... ... S31 + an -1 × S3n S12 + an- 2 × S1n ... ... ... ... ... Sn-1,1 + an-1 × Sn -1,n Sn-1,2 + an- 2 × Sn-1,n ... Sn-1,n-1 + a1 × Sn-1,n де матриця А - супровідна матриця, що містить у явному виді коефіцієнти свого характеристичного полінома f(X)=Xn+an-1Xn-1+ ... +a1X+a0 , матриця А-1 - матриця, зворотна матриці А; коефіцієнти {а0, а1, …, аn-1} яких задаються за допомогою блоку 5 керування, знак суми відповідає підсумовуванню по модулю два. Очевидно, що при переході від ;-ого стану генератора до (і+1)стану інформація в матриці становища генератора S зсувається по діагоналях зверху вниз, а елементи першого рядка і першого стовпця обчислюються як лінійні комбінації деяких елементів матриці S, обумовлені структурою зворотного зв'язку генератора. ù å an -k × Sk,n-1 + a1× å an-k × Skn ú ú S1,n-1 + a1 × S1n S1,n-1 + a1 × S1n S1,n-1 + a1 × S1n ú ú ú ú ú ú ú ú û При кожному такті інформація в регістрах 1 зсувається на один розряд вправо, що відповідає зсуву інформації в матриці S на один розряд по діагоналі. У перші розряди всіх регістрів 1 зсуву записуються сигнали, значення яких обумовлюються в ланцюгах зворотного зв'язку n n - входових суматорів 3 по модулю два , n груп по n двовходових елементів 2 "І", що відповідає заповненню першого стовпця і першого рядка матриці S, причому послідовність станів будьякого елемента матриці S генератора являє собою псевдовипадкову двійкову послідовність. Таким чином, винахід що заявляється, дозволяє збільшити кількість різних послідовностей одного періоду, що генеруються. 7 86401 8 9 86401 10 11 Комп’ютерна верстка Н. Лисенко 86401 Підписне 12 Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601