4.2. Декомпозиционные генераторы последовательностей GMW
В 1977г. было получено авторское свидетельство на устройство для генерации псевдослучайных последовательностей двоичных сигналов [21], соответствующих всем изоморфным в своих классах эквивалентности GMW разностным множествам с параметрами (2.13), строящихся на основе зингеровского класса базисных разностных множеств с параметрами (2.17).
В основе построения генераторов декомпозиционного типа лежит идея воссоздания декомпозиционной таблицы в порядке следования в ней элементов последовательности GMW. Для этой цели предварительно вычисляются значения 2N"m сдвигов ненулевых строк декомпозиционной таблицы соответствующей т-последовательности относительно первой строки с их порядковыми номерами, а также расположение є-2Нт ее нулевых строк. Полученная информация составляет основу программного устройства, с помощью которого выполняется построение декомпозиционой таблицы последовательности GMW. При этом по определенной циклической программе производится автоматическое, изменение задержки генерируемой базисной т-последовательности длины 2т-1. Согласно этой программе первые є двоичные символы генерируемой последовательности GMW определяются первыми двоичными символами формируемой совокупности из сдвинутых копий базисной последовательности и нулевых последовательностей длины 2т-1.Следующие є двоичных символов определяются всеми вторыми двоичными символами этой совокупности и т.д. В результате в генераторе формируются все 2N-1 символов последовательности GMW.На рис.4.1 представлена функциональная схема устройства для генерации двоичных последовательностей GMW, на основе базисных m-последовательностей. Устройство содержит генератор 1 тактовых импульсов, делитель 2 с коэффициентом деления є, генератор 3 m-последовательности в виде т-разрядного регистра сдвига с линейной обратной связью через сумматор по модулю два, m-входовый сумматор 4 по модулю два, m схем совпадения 5 и программное устройство 6, состоящего из m Е-разрядных циклических регистров сдвига 7.
Генератор 1 тактовых импульсов подключен к входу делителя 2 и к m входам цепей продвигающих импульсов циклических регистров сдвига 7-1,7- т. Выходы циклических регистров сдвига 7 соединены с первыми входами схем совпадения 5, вторые входы этих схем подключены к выходам соответствующих разрядов формирующего регистра генератора m-последовательности. Тактовые импульсы сдвига генератора 3 снимаются с выхода делителя 2. Все m выходов схем совпадения 5 подключены к m входам сумматора по модулю два 4. Устройство работает следующим образом. Вырабатьшаемые генератором 1 тактовые импульсы частоты fp осуществляют последовательное продвижение113
записанной в циклических регистрах сдвига 7 двоичной информации, при этом каждое поразрядное двоичное число, находящееся в течение периода T=l/fr генератора 1 в m выходных разрядов этого регистра, определяет величину сдвига m-последовательности генератора 3. Схемы совпадения в зависимости от состояний выходов циклических регистров сдвига 7 открыты или закрыты и в соответствии с этим пропускают или не пропускают двоичные сигналы разрядов регистра сдвига генератора 3 m-последовательности на входы сумматора 4. В результате на выходе сумматора 4 появляются двоичные сигналы формируемой последовательности GMW. Импульсы с выхода делителя 2 с частотой следования fr/є поступают на тактовый вход регистра сдвига генератора 3 , изменяя состояние разрядов этого регистра в соответствии с уравнением обратной связи. Таким образом, за длительность периода m-последовательности генератора 3 на выходе сумматора 4 появятся сигналы всех 2N-1 двоичных символов генерируемой последовательности GMW.
Для лучшего понимания работы устройства рассмотрим генерацию класса последовательностей GMW длины 63. В этом случае N=6, m=3, к=2 и є=9. В силу этого коэффициент деления делителя 2 равен 9. Генератор базисной m-последовательности состоит из 3-х разрядного регистра сдвига с обратными связями, описываемыми уравнениями D°y=Dy+D3y и D°y=Dy+D3y, где D - оператор сдвига, соответствующими примитивным полиномам степени 3 над GF(2) fi(x)=x3+x +1 и f2(x)=x3+x2 +1.
Программное устройство 6 состоит из 3-х 9-ти разрядных циклических регистров сдвига 7. Необходимые для его загрузки данные находятся с помощью декомпозиции исходной т-последовательности. Отметим, что теоретически данный генератор позволяет также формировать и шесть m-последовательностей длины 63, хотя, конечно, на практике это делать не следует.Почти одновременно с данным генератором было предложено устройство для генерации всех последовательностей GMW, строящихся на основе всех возможных базисных последовательностей [22]. На Рис.4.2 представлена функциональная схема этого устройства.
Оно состоит из генератора 1 тактовых импульсов, делителя 2 с коэффициентом деления є, генератора 3 базисной последовательности на 2т-1 -разрядном регистре циклическом регистре сдвига, элемента ИЛИ 4 на 2ш-1 входов, 2т-1 схем совпадения 5, программного устройства 6, состоящего в свою очередь из m е-разрядных циклических регистров сдвига 7 и дешифратора 8. Генератор 1 тактовых импульсов подключен к входу делителя 2 и к m входам цепей продвигающих импульсов регистров 7-1, 7-2,. ..7-ш.
В соответствии с алгоритмом построения программное устройство задает необходимую для генерации последовательности GMW совокупность из є m-разрядных двоичных чисел, ненулевые значения которых соответствуют сдвигам базисной последовательности, а нули - нулевым последовательностям. Устройство работает следующим образом. Тактовые импульсы генератора 1 осуществляют последовательное продвижение записанной в циклических регистрах сдвига 7 двоичной информации, при этом каждое m-разрядное двоичное число, находящееся в течение периода генератора I в выходных разрядах этих регистров, является двоичным кодом номера соответствующего разряда регистра генератора 3 базисной ПСП и, следовательно, определяет величину сдвига базисной ПСП. Появляющийся на одном из выходов дешифратора соответствующий этому коду сигнал открывает одну из схем совпадения 5 и пропускает двоичный сигнал с выхода соответствующего разряда регистра генератора 3 на вход элемента ИЛИ 4.
В результате циклических сдвигов информации в программном устройстве 6 на выходе элемента ИЛИ 4 появляются є двоичных сигналов формируемой ПСП.Импульсы с выхода делителя 2, поступая с частотой fr/є на тактовый вход генератора 3, осуществляют циклический сдвиг базисной ПСП. Поэтому за 2т-1 сдвигов последовательности в генераторе 3 на выходе элемента ИЛИ 4 появятся сигналы всех 2N-1 двоичных символов генерируемой последовательности.
Рис. 4.2
Генератор ПСП GMW на основе всех базисных последовательностей
При этом так называемая нулевая последовательность кодируется в программном устройстве 6 в виде двоичного числа из одних нулей, а дешифратор декодирует все числа от 1 до 2т-1. Поэтому при появлении кода нулевой последовательности в последних разрядах регистров 7 на всех выходах дешифратора появятся сигналы логического нуля, которые, закрывая схемы совпадения 5, создадут нулевой сигнал на выходе элемента ИЛИ 4.
Проведенный анализ показывает, что устройство целесообразно использовать для генерации последовательностей Гордона, Милза, Велча, начиная с N=10. Так, например, в случае N=14=7x2 предлагаемое устройство позволяет генерировать 59724 новых псевдослучайных последовательностей вместо 12852 генерируемых пг^дьідущим устройством. В случаях N<10 те же самые последовательности GMW могут быть получены с помощью генератора [21], обладающего несколько меньшей сложностью. Однако, когда нет необходимости в генерации всех существующих форм ПСП GMW и можно остановиться на одной или нескольких из них, выбранных в соответствии с определенными критериями (например, по минимаксному), использования схем [21,22] в силу их функциональной избыточности и сложности становится не целесообразным.
Рассматриваемое ниже устройство формирования двоичных ПСП GMW позволяет получить одну или несколько форм ПСП при значительно меньших технических затратах, что можно рассматривать, как своего рода компенсацию за проигрыш в числе генерируемых форм [63].
На рис.4.3 представлена структурная схема предлагаемого устройства для генерации псевдослучайных последовательностей.
Поступающие с генератора 1 тактовые импульсы с частотой fT продвигают записанную в регистре распределителя 2 "единицу", которая, проходя через ту или иную схему ИЛИ коммутатора 6, открывает связанную с ней схему совпадения 5, тем самым, пропуская двоичный сигнал с выхода соответствующего разряда регистра генератора 3 базисной последовательности на вход ИЛИ 4. Выходные импульсы распределителя 2 с частотой fr/e поступают на тактовый вход регистра сдвига
Рис.4.3
Блок-схема генератора нескольких форм ПСП GMW
генератора 3, осуществляя циклический сдвиг информации в этом регистре. Таким образом, за длительность периода базисной последовательности на выходе элемента ИЛИ 4 появятся сигналы всех 2N-1 двоичных символов генерируемой устройством последовательности.
При этом в соответствии с особенностями структуры ПСП GMW коммутатор 6 производит разбиение выходов разрядов регистра распределителя на определенные группы, соответствующие различным разрядам регистра генератора базисной последовательности, а, следовательно, и различным сдвигам базисной последовательности, что обеспечивает формирование совокупности из є последовательностей из сдвигов базисной и нулевой.
Первые є двоичных символов генерируемой последовательности совпадают со всеми первыми двоичными символами сформированной совокупности. Следующие є двоичных символов - со всеми вторыми двоичными символами той же совокупности и т. д. В результате такой циклической процедуры в устройстве формируются все 2N-l=eco двоичных символов ПСП GMW.
Чтобы понять работу устройства, рассмотрим генерацию ПСП GMW эначности 63 [63]. Эта последовательность имеет вид:
1010001101011001101000111010001000000011110111001111010010011011 и соответствует GMW разностному множеству с параметрами v=63, к=32Д=16 и образующим полиномом Q (х)з 1+х2 у6+хУ +х4у4 +*У +х6 +х7у6+жУ mod х63-1, где у=х9. В общем случае члены полинома Q(x) содержат всю информацию о структуре коммутатора 6 устройства, а именно:
1) члены с разными степенями у соответствуют разным элементам ИЛИ коммутатора 6;
члены с одинаковыми степенями у соответствуют входам одного элемента ИЛИ коммутатора 6;
выход определенного разряда распределителя 2 соединяется с определенным входом одного из элементов ИЛИ коммутатора 6 таким образом, что выход разряда с
номером, на единицу большим показателя степени х, соединяется с входом элемента ИЛИ, соответствующего степени у в члене, содержащем эту степень х;
4) выход каждого элемента ИЛИ подключается к входу схемы совпадения с номером, на единицу большим величины показателя соответствующей степени у.
При этом следует иметь в виду, что одновходовые элементы ИЛИ, предполагаемые данным описанием коммутатора 6, на самом деле отсутствуют.
Поэтому разряды распределителя 2, соответствующие этим одновходовым элементам ИЛИ, подключаются непосредственно к входам схем совпадения 5. Каждая схема совпадения (а число таких схем, как следует из описания коммутатора, может быть меньше о>) соединяется по входу с выходом одноименного разряда регистра сдвига генератора 3 базисной последовательности.В соответствии с этим устройство для генерации ПСП ГМВ змачности 63 (рис.4.4) содержит генератор тактовых импульсов 1, коммутатор 6, состоящий из трех элементов ИЛИ: двух двухвходовых (7-1,7-2) и одного трехвходового (7-3), распределитель 2 ипульсов на 9-разрядном циклическом регистре сдвига, генератор 3 базисной последовательности на 7-разрядном циклическом регистре сдвига, четыре схемы совпадения 5-1, 5-2,5-3, 5-4, четырехвходовой элемент ИЛИ 4.
Рассматриваемый генератор содержит один е-разрядный циклический регистр сдвига, выполняющий функции делителя тактовых импульсов и распределителя импульсов для коммутатора, в то время как генератор, описываемый в работе [22], содержит m циклических регистров сдвига разряда е, входящих в состав его программного устройства.
Сложность обоих генераторов при больших значениях N определяется числом регистров, поэтому технико-экономический эффект, получаемый в результате применения предложенного в данной статье, равен приблизительно т.
Рис.4.4
Функциональная схема генератора ПСП GMW длины 63
Общее число генерируемых этим устройством ПСП равно числу существующих базисных последовательностей, причем эти последовательности принадлежат различным классам ПСП GMW. Так, например, для N=14 устройство генерирует 80 ПСП из различных классов.
Описанный генератор имеет следующую особенность: если регистры распределителя импульсов и генератора базисной последовательности формирователя сделать реверсивными, то число генерируемых ПСП может быть увеличено вдвое. При этом если сдвиг информации в указанных регистрах происходит вправо, устройство генерирует одни псевдослучайные последовательности, а при сдвиге влево генерирует другие ПСП, "обратные" к первым.
Возможность генерации "обратных" копий ПСП GMW без какого-то либо изменения в информации, находящейся в регистрах этого устройства, обусловлена свойством ПСП, строящихся на основе разностных множеств. В соответствие с этим свойством преобразование, меняющее порядок следования всех элементов исходной ПСП, кроме первого, на противоположный, приводит к образованию ПСП из того же класса, но отличной от исходной. Таким образом, для рассматриваемого выше случая N=14 реверс регистров приводит к получению дополнительно еще 80 форм последовательностей.