Генератор псевдослучайных последовательностей

 

Изобретение относится к импульсной технике и может быть использовано в радиотехнике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет формирования производных последовательностей - достигается введением элемента И 2, группы блоков 3 формирования адреса и группы блоков 4 формирования производных последовательностей. Устройство содержит также генератор 1 тактовых импульсов и блок памяти 5. Сущность изобретения заключается в том, что производные последовательности формируются путем перемножения опорных последовательностей и их циклических сдвижек. 3 з.п. ф-лы, 3 ил., 2 табл.

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

Известен генератор псевдослучайных последовательностей (авт. св. СССР N 1406739, кл. H 03 K 3/84, 1988), содержащий два счетчика, генератор тактовых импульсов, регистр, блок управления, сумматор и блок памяти с соответствующими связями, выбранный в качестве прототипа. Устройство-прототип позволяет генерировать псевдослучайные последовательности (ПСП) длины N и их циклические сдвижки. Однако указанный генератор не позволяет генерировать проводные ПСП, которые используются при тестировании различных видов информационно-управляющих систем.

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

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

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

Кроме того, блок формирования производных последовательностей в точках пересечения выходов сформированных опорных l_i и l_j (i ≠ j) последовательностей, являющихся информационными входами блока, содержит элементы 2И, входы которых являются входами подачи l_i и l_jпоследовательностей соответственно, выходы элементов являются выходами производных последовательностей и информационными выходами блока.

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

Сущность изобретения заключается в следующем. Известно, что производными называются последовательности, формируемые путем перемножения символов с выходов нескольких генераторов последовательностей. С целью сохранения основных характеристик опорных последовательностей, формирование производных последовательностей в предлагаемом устройстве осуществляется чередованием символов опорных последовательностей и их циклических сдвижек. При этом длины всех опорных последовательностей l₁...l_k должны быть взаимно простыми числами. Тогда очевидно, что длительность производной последовательности, образованной перемножением символов i-й и j-й опорных последовательностей (i ≠ j): L_ij = l_i²l_j² (1) Квадраты в формуле (1) объясняются тем, что для формирования производной последовательности используются как опорные последовательности, так и все их циклические сдвижки, поэтому величина периода повторения каждой последовательности будет достигать l_i². Очевидно, что l_i² и l_j² при i ≠ j являются также взаимно простыми числами.

Тогда общее количестве формируемых последовательностей при объеме памяти, равном l_i, где k - количество опорных последовательностей, равно k+ i, k из которых являются опорными последовательностями и их циклически сдвижками длительности l_i (i = ), a i являются производными последовательностями с длительностью, определяемой формулой (1), образованными из k опорных последовательностей и их циклических сдвижек.

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

Генератор псевдослучайных последовательностей содержит (фиг. 1) генератор 1 тактовых импульсов, элемент И 2, блоки 3 формирования адреса, блоки 4 формирования производных последовательностей, а также блок 5 памяти, состоящий из ячеек 6 памяти. Вход 7 является входом разрешения работы, а выходы 8 - информационными выходами устройства.

Каждый блок 3 формирования адреса (фиг. 2) содержит первую 9 и вторую 10 схемы сравнения, первый 11 и второй 12 счетчики, а также сумматор 13 по модулю. Вход 14 является входом подачи тактовых импульсов, поступающих с выхода элемента И 2.

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

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

В исходном состоянии счетчики 11 и 12 блоков 3 обнулены, в каждой l_i-й ячейке 6 блока 5 памяти, содержащей l_i элементов памяти, записаны и хранятся базовые (опорные) ПСП, причем величины длительностей l_i (i = ) всех базовых ПСП являются взаимно простыми числами.

Начало работы устройства определяется моментом подачи на его вход 7 управления единичного потенциала, который удерживается в течение всего времени работы генератора. Этот потенциал поступает на первый вход элемента И 2, чем разрешается прохождение тактовых импульсов с выхода генератора 1 на входы блоков 3 формирования адресов, а также на входы разрешения чтения ячеек 6 блока 5 памяти. Импульсы, поступающие на входы блоков 3, формируют адреса в следующей последовательности: 0, 1, 2, ... i-1, 1, 2, ..., i-1, 0, 2, 3, ... i-1, 0, 1, 3, ... (2) Сформированные блоками 3 адреса поступают каждый на свою ячейку 6 памяти блока 5 памяти. В каждой ячейке 6 памяти записано l_i элементов, являющихся элементами базовых ПСП. Поэтому на выходе каждой ячейки 6 памяти формируются в соответствии с формулой (2) опорные ПСП и все их циклические сдвижки, которые поступают на вход блоков 4 формирования производных последовательностей. Блок 4 формирует на своих 1...k выходах k опорных ПСП длительностью l_i (i = ) и все циклические сдвижки опорных ПСП, а на k+i выходах - производные ПСП длительностью (1).

Блок формирования адреса работает следующим образом. На вход блока воздействует двоичный код величины l_i длительности i-й опорной ПСП и тактовые импульсы, поступающие далее на счетный вход счетчика 11. Последний подсчитывает тактовые импульсы и результат выдает на вход сумматора 13 по модулю l_i. В результате на выходе сумматора 13 появляется та же последовательность чисел, что и на его первом входе, так как счетчик 12 находится в нулевом состоянии и на второй вход сумматора 13 воздействует код нуля. Как только счетчик 11 сосчитает l_iимпульсов, сработает схема 9 сравнения, которая обнулит счетчик 11 и запишет к содержимому счетчика 12 дополнительную единицу. В результате на выходе сумматора 13 будет образовываться последовательность чисел, увеличенная на единицу, по сравнению с последовательностью, формируемой счетчиком 11, и т.д., т.е. на входе блока 5 формируется последовательность чисел вида (2) с периодом l_i². После того как будет сформировано l_i² адресов, сработает схема 10 сравнения, обнулит счетчик 12, и весь процесс формирования последовательности адресов вида (2) начинается заново.

Блок 4 формирования производных последовательностей работает следующим образом. Поступающие на его 1...k входы опорные последовательности проходят без изменения на его 1...k выходы, а также поступают на схемы формирования производных последовательностей. Схемы формирования производных последовательностей представляют собой элементы 2И, входы которых подключены один к i-му, а второй к j-му (i ≠ j) входам блока. В результате на выходе схем 2И формируются производные последовательности, которые поступают на k+1... k+i выходы блока 4. Выходы k+1...k+i предыдущего блока 4 являются входами последующего блока 4. Число блоков 4 определяется необходимым соотношением единиц и нулей производных последовательностей.

Рассмотрим на примере работу блока 4 формирования производных последовательностей. Пусть k = 4, l₁ = 5, l₂ = 9, l₃ = 11, l₄ = 16. Тогда на первом выходе блока 4 формируется опорная ПСП длительностью, равной 5, и ее четыре циклические сдвижки с той же длительностью, на втором соответственно - опорная ПСП с длительностью 9 и восемь сдвижек и т.д. Правила формирования производных последовательностей сведем в табл. 1.

Количество производных последовательностей равно i = 6, которые будут формироваться на 5...10 выходах блока 4.

Период каждой составной последовательности L_ij в соответствии с табл. 1 и выражением (1) сведем в табл. 2.

Итак, предлагаемое устройство позволяет генерировать ПСП с большим периодом и произвольной периодичности.

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

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

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

1. ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащий генератор тактовых импульсов, блок памяти, отличающийся тем, что, с целью расширения функциональных возможностей путем обеспечения формирования производных псевдослучайных последовательностей, в него введены элемент И, группа блоков формирования адреса и группа блоков формирования производных последовательностей, причем первый вход элемента И является управляющим входом устройства и соединен с входом разрешения чтения блока памяти, второй вход соединен с выходом генератора тактовых импульсов, а выход - с тактовыми входами группы блоков формирования адреса, управляющий вход каждого блока формирования адреса подключен к шине кода длины соответствующей последовательности, а выходы соединены с входами блока памяти, информационные выходы которого соединены с входами первого блока формирования производных последовательностей, выходы предыдущего блока формирования производных последовательностей соединены с входами последующего блока формирования производных последовательностей и являются информационными выходами устройства.

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

3. Генератор по п.1, отличающийся тем, что блок формирования производных последовательностей в точках пересечения выходов сформированных опорных l_i и l_j(i = j) последовательностей, являющихся информационными входами блока, содержит элементы 2И, входы которых являются входами подачи l_i и l_j последовательностей соответственно, выходы элементов являются выходами производных последовательностей и являются информационными выходами блока.

4. Генератор по п.1, отличающийся тем, что блок памяти содержит K ячеек памяти, причем каждая i-я ячейка памяти содержит l_i элементов памяти, входы разрешения чтения ячеек памяти объединены и являются управляющими входами блока, информационные входы ячеек памяти являются информационными входами, а информационные выходы ячеек - информационными выходами блока.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4