ГЕНЕРАТОР ПРОИЗВОДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Российский патент 2008 года по МПК G06F1/02 

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

Известен генератор функций Уолша, содержащий задающий генератор, регистр сдвига, регистр номера функции, элемент НЕ, элемент И и триггер, причем выход регистра номера функции подключен к параллельному информационному входу регистра сдвига, выход задающего генератора подключен к тактовому входу регистра сдвига и к входу элемента НЕ, выход элемента НЕ и последовательный выход регистра сдвига через элемент И подключены к счетному входу триггера (см. авторское свидетельство СССР №1076892, кл. G06F 1/02, 1982 г.).

Однако этот генератор обладает существенной сложностью, обусловленной большим числом разрядов в используемом регистре сдвига (2n-1 при 2n генерируемых функциях Уолша), поскольку каждый разряд регистра сдвига представляет собой триггер.

Наиболее близким по технической сущности к заявляемому изобретению является генератор функций Уолша, содержащий задающий генератор, элемент НЕ, регистр сдвига, регистр номера функции, элемент И, триггер, n-разрядный счетчик и дополнительный элемент И (см. патент РФ №2275683, кл. G06G 7/26, 2006 г.).

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

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

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

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

Улучшения автокорреляционных свойств последовательностей Уолша можно достичь путем формирования на их основе производных последовательностей. Для этого последовательности Уолша одного ансамбля должны быть посимвольно сложены с производящей последовательностью, одинаковой по длительности с последовательностями Уолша, но обладающей лучшими автокорреляционными свойствами. Указанным свойствам производящих последовательностей соответствуют характеристические дискретные последовательности (ХДП) (см.: Свердлик М.Б. Оптимальные дискретные сигналы. М., «Советское радио», 1975).

Сравнительная характеристика максимальных выбросов периодической (ПАКФ) и апериодической (ААКФ) корреляционных функций последовательностей Уолша длительностью l=16 и последовательностей, сформированных на основе объединения последовательностей Уолша и ХДП, приведена в таблице 1.

Вид КФПоследовательности УолшаПроизводные последовательностиR_max(m)R_min(m)m(x)R_max(m)R_min(m)m(x)ПАКФ1-1-0,0390,5330-0,333-0,0710,02ААКФ0,866-0,944-0,0710,2780,311-0,421-0,0040,071

Из таблицы видно, что и по размерам максимальных выбросов R_max(m) корреляционных функций и по величине дисперсии выбросов боковых лепестков корреляционных функций производные последовательности значительно превосходят соответствующие им последовательности Уолша.

Для формирования характеристических дискретных последовательностей в предлагаемом генераторе используется следующий алгоритм:

1. Исходными данными для формирования ХДП является модуль p, равный требуемой длительности последовательности, являющийся простым целым положительным числом, а также первообразный элемент θ над полем GF(p).

2. Пошагово формируются два массива чисел: М(1) размерностью р и М(2) размерностью (р-1). Формирование массива М(1) заключается в определении на каждом шаге номера элемента массива путем вычисления значения (А+1) mod р (где А=(А'×θ) mod р, А' - значение числа А, полученное на предыдущем шаге вычислений, причем на первом шаге А=1) и присвоении данному элементу значения, равного номеру шага вычисления. Первому элементу массива М(1) присваивается значение «1». Формирование массива М(2) заключается в присвоении i-му элементу массива (i - номер шага вычислений) значения (А+1) mod p, полученного на данном шаге вычисления.

3. По завершении формирования обоих массивов на их основе пошагово формируется ХДП в соответствии со следующим правилом:

Н_i=(М(1)_j) mod 2, где j=(М(2)_i)+1) mod p,

где i - номер шага вычисления

Пример

Пусть р=7, θ=5. В этом случае необходимо произвести (р-1)=6 шагов вычислений по формированию массивов М(1) и М(2). На каждом шаге должно быть вычислено значение А=(А'*θ) mod p. Так как на первом шаге вычисления А=1, то на втором А=(1*5) mod 7=5, на третьем A=(5*5) mod 7=4, на четвертом А=6, на пятом А=2, на шестом А=3. Таким образом, второй элемент массива М(1) примет значение 1, шестой - 2, пятый - 3, седьмой - 4, третий - 5, четвертый - 6. Первый элемент массива М(2) примет значение (A+1)=2, второй - 6, третий - 5, четвертый - 0, пятый - 3, шестой - 4.

Таким образом, по завершении формирования массивы М(1) и М(2) будут иметь следующий вид:

М1=[1 1 5 6 3 2 4], М2=[2 6 5 0 3 4].

Далее, в соответствии с пунктом 3 алгоритма формируется искомая числовая последовательность. Первым элементом последовательности H₁=(M(1)_(M(2)1)+1) mod 2=(М(1)₃) mod 2=(5) mod 2=1. Второй элемент последовательности H₁=(4) mod 2=0. Аналогично формируются остальные элементы последовательности.

Таким образом, результирующая последовательность будет иметь вид:

Н=1 0 0 1 0 1.

После формирования производящей последовательности она посимвольно складывается по модулю 2 с последовательностями Уолша. Результатом сложения будут являться искомые производные последовательности.

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

Генератор производных последовательностей состоит из генератора 1 тактовых импульсов, блока 2 формирования производящей последовательности, ключа 3, элемента НЕ 4, n-разрядного счетчика 5, первого элемента И 6, регистра сдвига 7, регистра номера функции 8, второго элемента И 9, триггера 10, сумматора 11 по модулю 2.

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

В исходном положении ключ 3 разомкнут, а на первый и второй входы устройства соответственно подаются значения первообразного элемента θ и модуля р. Старший разряд n-разрядного счетчика 5 установлен в единичное состояние, а остальные разряды - в нулевое состояние, триггер 10 установлен в единичное состояние.

Перед началом работы кодовая комбинация, представляющая собой усеченный код номера последовательности Уолша, переписывается из регистра 8 номера функции в регистр 7 сдвига.

Двоичный код номера последовательности Уолша, который должен быть записан в регистре 7 сдвига, определяется следующими таблицами:

а) для N=4 (где N - объем системы последовательностей Уолша)

Таблица 1Десятичный номер последовательности УолшаДвоичный номер последовательности УолшаДвоичный код номера последовательности Уолша0001012
310
11 Комбинации, записываемые в регистр 7 сдвига

б) для N=8

Таблица 2Десятичный номер последовательности УолшаДвоичный номер последовательности УолшаДвоичный код номера последовательности Уолша0000100120103011410051016
7110
111 Комбинации, записываемые в регистр 7 сдвига

в) для N=16

Таблица 3Десятичный номер последовательности УолшаДвоичный номер последовательности УолшаДвоичный код номера последовательности Уолша0000010001200103ООН40100501016011070111810009100110101011101112110013110114
151110
1111 Комбинации, записываемые в регистр 7 сдвига

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

Блок 2 формирования производящей последовательности (фиг.2) содержит блок 12 контроля, ключ 13, блок 14 управления, умножитель 15 по модулю, элемент ИЛИ 16, счетчик 17, первое ПЗУ 18, блок 19 формирования остатка, первый сумматор 20, блок 21 коммутации, второе ПЗУ 22, блок 23 формирования остатка по модулю 2, второй сумматор 24.

В исходном положении на первый и второй входы блока 12 контроля подаются соответственно значения первообразного элемента θ и модуля p, причем данные входы отключены от соответствующих выходов блока. Третий выход блока 12 контроля служит для передачи в блок управления информации о значении модуля и об изменении значений модуля и первообразного элемента.

Процесс формирования производящей последовательности начинается с момента появления первого единичного тактового импульса на входе ключа 13 и первом входе блока 14 управления. В исходном положении вход ключа 13 подключен на первый выход, поэтому единичный символ с первого выхода ключа 13 поступает на первый вход умножителя 15 по модулю. Так как на первом такте работы на остальные входы умножителя 15 по модулю данные не подаются, единичный импульс подается на младший разряд выхода умножителя, с которого в виде двоичного кода числа «1» поступает на вход первого сумматора 20, а также в цепь обратной связи. В первом сумматоре 20 поступающее на его вход значение увеличивается на один путем добавления единицы в младший разряд двоичного кода числа. С выхода первого сумматора 20 полученный код числа «2» поступает на первый вход блока 21 коммутации, на второй вход которого поступает значение с выхода счетчика 17. Так как с первого выхода ключа 13 тактовый импульс через элемент ИЛИ 16 поступает также на счетный вход счетчика 17, то на выходе счетчика на первом такте будет сформировано значение «1». Учитывая, что на первом такте на первый вход блока 21 коммутации поступает значение числа «2», значение числа «1» будет записано во вторую ячейку второго ПЗУ 22. Первая ячейка второго ПЗУ 22 постоянно имеет значение «1».

С выхода первого сумматора 20 полученный код числа также поступает на первый вход блока 19 формирования остатков. Так как на первом такте работы на второй вход блока 19 формирования остатков код модуля не подается, значение числа «2» с выхода блока 19 формирования остатков подается на вход первого ПЗУ 18, где записывается в первую ячейку.

После завершения первого тактового импульса блок 14 управления на первом своем выходе формирует сигнал на перекоммутацию входа ключа 13 с первого на второй выход, а на втором выходе - сигнал на подключение входов записи кода первообразного элемента и модуля на соответственно первый и второй выходы блока 12 контроля. На втором и последующих тактах работы импульсы тактового чтения подаются на тактовый вход умножителя 15 по модулю, а также через элемент ИЛИ 16 на счетный вход счетчика 17. На каждом такте в умножителе 15 по модулю происходит умножение по модулю (значение которого поступает на четвертый вход умножителя) значения, сформированного в данном блоке на предыдущем такте и поступающего по цепи обратной связи на второй вход умножителя, на значение первообразного элемента, поступающее на третий вход умножителя.

Полученное значение с выхода умножителя 15 поступает в цепь обратной связи и на вход первого сумматора 20. После увеличения на единицу полученное значение с выхода первого сумматора 20 поступает на первый вход блока 21 коммутации, где определяет адрес ячейки второго ПЗУ 22, в которую запишется значение, поступающее со счетчика 17, а также на первый вход блока 19 формирования остатков, на второй вход которого поступает значение модуля. С выхода блока 19 формирования остатков полученное значение поступает на вход первого ПЗУ 18, где записывается в i-ю ячейку (i-номер такта).

Таким образом, на каждом такте, начиная со второго, в первом ПЗУ 18 поочередно в каждую ячейку, начиная со второй, будет записано значение остатка по модулю p от значения числа А, сформированного в умножителе 15 по модулю и увеличенного на единицу, то есть (А+1) mod p, а в (А+1)-ю ячейку второго ПЗУ 22 будет записано значение i (i - номер такта).

По завершении (p-1)-го такта (p - модуль) блок 14 управления на первом выходе сформирует сигнал на подключение входа ключа 13 на третий выход данного блока, а на втором выходе - сигнал на отключение первого и второго выходов блока 12 контроля. На третьем выходе блока 14 управления будет сформирован сигнал на включение ключа 3 и подачи тактовых импульсов на элементы генератора, отвечающие за формирование последовательностей Уолша.

Под воздействием тактовых импульсов, поступающих с выхода ключа 3 на тактовый вход регистра 7 сдвига, информация, записанная в нем, сдвигается и поступает на один из входов второго элемента И 9, на второй вход которого поступает инвертированный тактовый импульс. Информация с выхода регистра 7 сдвига поступает также на один из входов первого элемента И 6, на второй вход которого поступает единичный потенциал с выхода старшего разряда счетчика 5. Информация с выхода первого элемента И 6 будет поступать на вход регистра 7 сдвига до тех пор, пока старший разряд счетчика 5 будет находиться в единичном состоянии. Поскольку счетчик 5 имеет n разрядов, причем перед началом его работы в его старшем разряде была записана «1», то это произойдет через 2^n-1 тактов работы генератора 1. Таким образом, в регистр 7 сдвига по цепи обратной связи запишутся (2^n-1-1) символов, вышедших из него, и, следовательно, они повторно поступят на вход второго элемента И 9, то есть на вход второго элемента И 9 в итоге поступит не усеченный, а полный код номера последовательности Уолша.

Напряжение на выходе второго элемента И 9 оказывается стробированным, причем на каждый двоичный интервал минимальной длительности приходится по одному стробу, а длительность каждого строба равна половине длительности тактового интервала. Сигналы с входа второго элемента И 9 поступают на счетный вход триггера 10, предварительно установленного в одиночное состояние. Моменты появления логических единиц на выходе второго элемента И 9 соответствуют моментам перемен знака генерируемой последовательности Уолша, поэтому на выходе триггера 10 оказывается сформированной соответствующая последовательность Уолша. Элементы последовательности Уолша с выхода триггера 10 поступают на первый вход сумматора 11 по модулю 2.

Одновременно в блоке 2 формирования производящей последовательности тактовые импульсы с третьего выхода ключа 13 будут поступать на тактовые входы обоих ПЗУ. Под их действием значение каждой ячейки первого ПЗУ 18 поочередно, начиная с первой ячейки, будет подаваться на выход первого ПЗУ 18, увеличиваться на единицу во втором сумматоре 24 и поступать на второй вход второго ПЗУ 22, где будет определять адрес ячейки, значение которой на данном такте должно поступить на выход второго ПЗУ 22. Данное значение поступит на вход блока 23 формирования остатков по модулю 2. С выхода данного блока, являющегося вторым выходом блока 2 формирования производящей последовательности, символы «1» или «0» будут поступать на второй вход сумматора 11, где по модулю 2 будут складываться с символами последовательности Уолша. На выходе сумматора 11 по модулю 2 будут формироваться элементы производной последовательности.

В случае изменения длительности производящей последовательности (модуля р) или порядка ее формирования (первообразного элемента θ) на третьем выходе блока 12 контроля сформируется сигнал, который поступит на второй вход блока 14 контроля. При этом блок 14 на первом входе сформирует сигнал на подключение входа ключа 13 на первый выход, на третьем входе - сигнал на выключение ключа 3, на четвертом выходе - сигнал на обнуление счетчика 17, после чего происходит формирование производной последовательности в соответствии с вышеприведенным алгоритмом.

Генератор производных последовательностей относится к вычислительной технике, в частности к генераторам дискретных последовательностей, и может быть использован в цифровых вычислительных устройствах, телевидении, телекоммуникационных системах при формировании ортогональных адресных последовательностей, а также в системах защиты информации. Техническим результатом является расширение функциональных возможностей генератора функций Уолша за счет обеспечения возможности формирования производных последовательностей. Генератор производных последовательностей состоит из генератора тактовых импульсов, элемента НЕ, n-разрядного счетчика, двух элементов И, регистра сдвига, регистра номера функции и триггера. В него введены блок формирования производящей последовательности, ключ, сумматор по модулю 2. 1 з.п. ф-лы, 2 ил., 3 табл.

1. Генератор производных последовательностей, содержащий генератор тактовых импульсов, элемент НЕ, n-разрядный счетчик, первый и второй элемент И, регистр сдвига, регистр номера функции, триггер, причем выход регистра номера функции подключен к параллельному информационному входу регистра сдвига, выход элемента НЕ и последовательный выход регистра сдвига через элемент И подключены к счетному входу триггера, регистр сдвига замкнут в кольцо цепью обратной связи через элемент И, второй вход которого подключен к выходу старшего разряда счетчика, отличающийся тем, что в него введены блок формирования производящей последовательности, ключ и сумматор по модулю 2, причем выход генератора тактовых импульсов подключен ко входу ключа, а также к третьему входу блока формирования производящей последовательности, первый выход которого подключен к управляющему входу ключа, второй выход - ко второму входу сумматора по модулю 2, выход ключа подключен к тактовому входу регистра сдвига, к входу элемента НЕ и к счетному входу счетчика, первый вход блока формирования производящей последовательности подключен к входу записи кода первообразного элемента, второй вход блока формирования производящей последовательности подключен ко входу записи кода модуля, выход триггера подключен к первому входу сумматора по модулю 2, выход которого является выходом генератора.2. Устройство по п.1, отличающееся тем, что блок формирования производящей последовательности содержит блок контроля, ключ, блок управления, умножитель по модулю, элемент ИЛИ, счетчик, первое и второе ПЗУ, блок формирования остатка, первый и второй сумматор, блок коммутации, блок формирования остатка по модулю 2, причем первый вход блока формирования производящей последовательности подключен к первому входу блока контроля, второй вход блока формирования производящей последовательности подключен ко второму входу блока контроля, третий вход блока формирования производящей последовательности подключен ко входу ключа и первому входу блока управления, ко второму входу которого подключен третий выход блока контроля, первый выход блока контроля подключен к третьему входу умножителя по модулю, второй выход блока контроля подключен к четвертому входу умножителя по модулю и ко второму входу блока формирования остатков, первый выход блока управления подключен к управляющему входу ключа, второй выход блока управления подключен к третьему входу блока контроля, третий выход блока управления является первым выходом блока формирования производящей последовательности, четвертый выход блока управления подключен к входу обнуления счетчика, первый выход ключа подключен к первому входу умножителя по модулю и к первому входу элемента ИЛИ, второй выход ключа подключен к тактовому входу умножителя по модулю и ко второму входу элемента ИЛИ, выход которого подключен к счетному входу счетчика, третий выход ключа подключен к тактовым входам обоих ПЗУ, выход умножителя по модулю подключен к входу первого сумматора и ко второму входу умножителя по модулю, выход первого сумматора подключен к первому входу блока коммутации, ко второму входу которого подключен выход счетчика, а также к первому входу блока формирования остатков, выход блока коммутации подключен к первому входу второго ПЗУ, выход блока формирования остатков подключен ко входу первого ПЗУ, выход первого ПЗУ подключен ко входу второго сумматора, выход второго сумматора подключен ко второму входу второго ПЗУ, выход второго ПЗУ подключен ко входу блока формирования остатка по модулю 2, выход данного блока является вторым выходом блока формирования производящей последовательности.