ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИМПУЛЬСОВ НА ОДНОРОДНОЙ СРЕДЕ С ПРОГРАММНО МЕНЯЮЩЕЙСЯ СТРУКТУРОЙ Российский патент 2008 года по МПК G06F7/58 H03K3/84 

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

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

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

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

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

Указанный технический результат достигается тем, что в генератор, включающий в себя формирователь тактовых импульсов (ФТИ), блок управления и настройки (БУиН), введена в качестве блока формирования однородная среда с программно меняющейся структурой, состоящая из n - последовательно соединенных однородных ячеек (Я₁-Я_n). Генератор образует псевдослучайные числа путем формирования серии двоичных символов, состоящей из n-последовательностей - элементов этой серии, максимальное число таких последовательностей 2ⁿ-1. Порядок следования n-последовательностей в серии зависит от структуры обратных связей между однородными ячейками. Если через n*(2ⁿ-1) тактов работы ГППИ производить изменения структуры обратных связей путем изменения кода настройки и число этих изменений "m", то длина серии ГППИ увеличится в "m"-раз и будет равна m*n*2ⁿ.

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

Генератор псевдослучайных последовательностей импульсов (ГППИ) на однородной среде с программно меняющейся структурой, содержащий формирователь тактовых импульсов (ФТИ), блок управления и настройки (БУиН), отличающийся тем, что введены n последовательно соединенных однородных ячеек, которые образуют формирователь импульсных последовательностей генератора, ФТИ предназначен для синхронизации работы всех устройств ГППИ и соединен линией тактирования с БУиН и со всеми однородными ячейками по входу тактирования ячеек (19), БУиН соединен шиной адреса со всеми однородными ячейками по адресным входам ячеек, шиной управления записью по входам управления записью ячеек, линией сброса по входам сброса ячеек, шиной кода настройки по управляющим входам настройки однородных ячеек (1-8), первый информационный вход (9) первой ячейки соединен с информационным выходом БУиН и предназначен для последовательного ввода и установки начального состояния однородных ячеек и задания первой последовательности импульсов, формируемых ГППИ, первый информационный выход (12) каждой предыдущей ячейки соединен с первым информационным входом (9) последующей ячейки для организации прохождения информации без преобразования, второй информационный выход (13) каждой ячейки соединен со вторым информационным входом (10) последующей ячейки для организации неуправляемого переноса информации между ячейками, а второй информационной выход (13) последней «n»-ой ячейки среды является последовательным выходом ГППИ, на который поступает сформированная последовательность импульсов, третьи информационные выходы (14) всех ячеек образуют шину данных (ШД), которая дает возможность параллельно считывать информацию, ШД подключена к БУиН,

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

Ячейка однородной среды состоит из двух элементов 2-2И-2ИЛИ (1, 11), триггера 8, сумматора по модулю два 7, трех элементов НЕ (2, 14 и 15), восьми элементов И (3, 4, 5, 6, 9, 16, 17, 18), трех элементов ИЛИ (10, 12, 13), регистра кода настройки (27), группы из семи элементов суммирования по модулю два (19-26), имеет четыре информационных входа (9, 10, 11, 18), восемь входов управления настройкой (1-8), четыре информационных выхода (12-15), тактовый вход (19), вход адреса однородной ячейки (16), вход управления записью в регистр кода настройки (17), вход сброса регистра кода настройки (20).

Описание работы однородной ячейки

Ячейка однородной среды состоит из двух элементов 2-2И-2ИЛИ (1, 11), триггера 8, сумматора по модулю два 7, трех элементов НЕ (2, 14 и 15), восьми элементов И (3, 4, 5, 6, 9, 16, 17, 18), трех элементов ИЛИ (10, 12, 13), регистра кода настройки (27), группы из семи элементов суммирования по модулю два (19-26), имеет четыре информационных входа (9, 10, 11, 18), восемь входов управления настройкой (1-8), четыре информационных выхода (12-15), тактовый вход (19), вход адреса однородной ячейки (16), вход управления записью в регистр кода настройки (17), вход сброса регистра кода настройки (20). Логическая единица на управляющем входе 2 обеспечивает информационную связь ячейки по первому информационному входу (9), что может быть использовано при параллельной записи информации в ячейку; логическая единица на управляющем входе 1 "замыкает" цепь обратной связи с первым информационным выходом ячейки (12), образуя внутреннюю обратную связь, и через третий информационный вход ячейки (11), внешнюю, что может быть использовано при охвате цепью обратной связи ячеек, работающих в режиме формирования псевдослучайной последовательности; логическая единица на управляющем входе 3, обеспечивает участие переменных на первом (9) или третьем (11) информационных входах в суммировании по модулю два с переменной на четвертом (18) информационном входе, что имеет место при работе ячейки в режиме формирования псевдослучайной последовательности; логическая единица на управляющем входе 4 обеспечивает прохождение информации с четвертого информационного входа (18) на второй информационный выход (13), без преобразования, что может быть использовано для обхода ячейки при ее неисправности; логическая единица на управляющем входе 6 обеспечивает тактирование записи и считывания информации в ячейке, определяет ячейки, участвующие в преобразовании информации; логическая единица на управляющих входах 5 и 7 определяет считывание информации с выхода триггера 8 или непосредственно с выхода сумматора 7 и что при работе данной ячейки в среде, она выбрана последней ячейкой в структуре формирователя; управляющий сигнал на входе 8 обеспечивает прохождение сигнала на четвертый информационный выход ячейки (15) со второго информационного входа ячейки (10) и используется для организации неуправляемого информационного переноса через ячейку при отсутствии кода настройки в регистре 27.

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

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

Описание работы ГППИ по фигуре 1.

На фигуре 1 приведена структурная схема ГППИ. Генератор содержит формирователь тактовых импульсов (ФТИ), блок управления и настройки (БУиН) и однородную среду 3, состоящую из n - последовательно соединенных однородных ячеек (Я₁-Я_n). БУиН задает частоту тактовых импульсов, формируемых ФТИ, и управляет настройкой ячеек однородной среды и процессом формирования псевдослучайных последовательностей.

Настройка блока однородных ячеек, образующих однородную среду с программно меняющейся структурой, осуществляется блоком БУиН в следующей последовательности:

1. Сброс регистров кода настройки ячеек, подачей на входы 20 всех ячеек сигнала сброса.

2. Установка на шине кода настройки (ШКН) управляющего слова - кода настройки.

3. Установка на шине адреса (ША) адреса программируемой ячейки (или ячеек).

4. Подача по шине управления (ШУ) сигнала записи в регистр кода настройки ячейки (или ячеек).

Адреса ячеек и коды настройки формируются блоком БУиН.

Настройка элементов формирователя генератора производится в двух режимах: последовательном (каждая ячейка отдельно) или параллельном (несколько ячеек одновременно). Последовательный режим рассмотрен выше. При настройке элементов среды в параллельном режиме программируется не отдельная ячейка среды, а одновременно программируются отдельные одноименные разряды нескольких или всех ячеек, входящих в формирователь. На ША блоком БУиН формируется кодовое слово, в соответствующих программируемым ячейкам разрядах которого установлены уровни логической "1", на ШКН формируется слово, в "программируемых" разрядах которой установлены уровни логической "1", по ШУ он подается, сигнал записи управляющего слова в регистр кода настройки. В этом случае время программирования зависит не от количества ячеек в среде, а от разрядности управляющего слова.

При построении ГППИ может быть предусмотрена возможность изменения числа элементов в формирующей среде, когда количество однородных ячеек в блоке формирования импульсных последовательностей - N, больше, чем разрядность двоичной серии n (N>n), которую требуется сформировать на выходе генератора. В этом случае n-я ячейка выбирается программно последней в структуре генератора, по соответствующему входу настройки, в регистр кода настройки n-ой ячейки, записывается уровень логического "0" и осуществляется неуправляемый перенос информации с выхода 14 n-ой ячейки на входы 10 последующих ячеек среды. Неиспользованные ячейки - элементы однородной среды могут быть программно использованы для увеличения длины формируемой последовательности или использованы в качестве структурного скользящего резерва формирователя, что позволит повысить ее структурную надежность.

Перед запуском генератора формирователь должен быть установлен в начальное состояние. Ввод последовательности установки формирователя генератора в начальное состояние может осуществляться в двух режимах: последовательном и параллельном.

Последовательный ввод осуществляется по входу 9 первой ячейки блока 3 в режиме сдвигового регистра, путем тактирования записи сигнала, установленного на выходе блока 2 во все выбранные настройкой ячейки. Запись осуществляется при следующих значениях сигналов настройки ячеек: Z₁=0, Z₄=0, Z₅=1,

сквозной перенос (через остальные ячейки) информации при Z₁=0, Z₄=1, Z₅=0 (индексы переменной Z указывают номера выходов регистров кода настройки 27).

Параллельный ввод информации производится по входам 9 ячеек, при этом на шину данных выставляется начальное состояние формирователя генератора, при следующих значениях управляющих сигналов на выходах регистров: Z₁=1, Z₃=1, Z₄=1, Z₅=1, записанных в регистр кода настройки ячеек, входящих в состав формирователя.

Алгоритм формирования последовательности генератором зависит от способа вывода информации. При параллельном выводе информации алгоритм включает:

1. настройку среды на ввод начальной последовательности;

2. загрузку начальной последовательности;

3. настройку среды на формирование;

4. формирование последовательности.

Формируемые последовательности снимаются одновременно со всех выходов 15 элементов формирователя.

При последовательном выводе информации алгоритм функционирования отличается добавлением:

5. настройки среды на последовательный вывод информации;

6. вывод сформированной последовательности с выхода 14 последней из используемых элементов - ячеек среды формирователя, с одновременным вводом ее с выхода 15 последней ячейки на вход 9 первой ячейки среды для сохранения текущего состояния формирователя. Цепь обратной связи при этом разомкнута;

7. переход к п.4 и перевод формирователя в следующее состояние.

Структура формируемой последовательности, порядок следования состояний выхода зависит от структуры обратных связей однородной среды - блока однородных ячеек. Сменой структуры обратных связей обеспечивается изменение порядка следования состояний от одной серии к другой. Число вариантов настройки структуры обратных связей равно m, которое равно сумме числа сочетаний С^j _n-1 из (n-2) ячеек, j меняется от 1 до (n-2) и есть число ячеек, подключенных к цепи обратной связи в среде однородных ячеек блока формирователя в составе генератора. Длина псевдослучайной серии, формируемой генератором с перестройкой структуры обратных связей в однородной среде - формирователе при этом определяется как n*m*2ⁿ=n*2ⁿΣC^j _n-1.

Описание ячейки однородной среды формирователя по фиг.2.

Ячейки однородной среды состоят из двух элементов 2-2И-2ИЛИ (1, 11), триггера (8), сумматора по модулю два (7), трех элементов НЕ (2, 14 и 15), восьми элементов И (3, 4, 5, 6, 9, 16, 17, 18), трех элементов ИЛИ (10, 12, 13), регистра кода настройки (27), группы из семи элементов суммирования по модулю два (19-26), имеет четыре информационных входа (9, 10, 11, 18), восемь входов управления настройкой (1-8), четыре информационных выхода (12-15), тактовый вход (19), вход адреса однородной ячейки (16), вход управления записью в регистр кода настройки (17), вход сброса регистра кода настройки (20). Логическая единица на управляющем входе 2 обеспечивает информационную связь ячейки по первому информационному входу (9), что может быть использовано при параллельной записи информации в ячейку; логическая единица на управляющем входе 1 "замыкает" цепь обратной связи с первым информационным выходом ячейки (12), образуя внутреннюю обратную связь, и через третий информационный вход ячейки (11), внешнюю, что может быть использовано при охвате цепью обратной связи ячеек, работающих в режиме формирования псевдослучайной последовательности; логическая единица на управляющем входе 3 обеспечивает участие переменных на первом (9) или третьем (11) информационных входах в суммировании по модулю два с переменной на четвертом (18) информационном входе, что имеет место при работе ячейки в режиме формирования псевдослучайной последовательности; логическая единица на управляющем входе 4 обеспечивает прохождение информации с четвертого информационного входа (18) на второй информационный выход (13), без преобразования, что может быть использовано для обхода ячейки при ее неисправности; логическая единица на управляющем входе 6 обеспечивает тактирование записи и считывания информации в ячейке, определяет ячейки, участвующие в преобразовании информации; логическая единица на управляющих входах 5 и 7 определяет считывание информации с выхода триггера 8 или непосредственно с выхода сумматора 7 и что при работе данной ячейки в среде, она выбрана последней ячейкой в структуре формирователя; управляющий сигнал на входе 8 обеспечивает прохождение сигнала на четвертый информационный выход ячейки (15) со второго информационного входа ячейки (10) и используется для организации неуправляемого информационного переноса через ячейку при отсутствии кода настройки в регистре 27.

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

Библиографические данные

1. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А., Теория кодов, исправляющих ошибки. - М.: Связь, 1979 г.

2. Авторское свидетельство СССР №978147, кл. G06F 7/58, 1982 г.

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

Генератор псевдослучайных последовательностей импульсов (ГППИ) на однородной среде с программно меняющейся структурой, содержащий формирователь тактовых импульсов (ФТИ), блок управления и настройки (БУиН), отличающийся тем, что введены n-последовательно соединенных однородных ячеек, ФТИ предназначен для синхронизации работы всех устройств ГППИ и соединен линией тактирования с БУиН и со всеми однородными ячейками по входу тактирования ячеек, БУиН соединен шиной адреса со всеми однородными ячейками по адресным входам ячеек, шиной управления записью по входам управления записью ячеек, линией сброса по входам сброса ячеек, шиной кода настройки по управляющим входам настройки функционирования ячеек, первый информационный вход первой ячейки соединен с информационным выходом БУиН и предназначен для последовательного ввода начальной последовательности импульсов, первый информационный выход каждой предыдущей ячейки соединен с первым информационным входом последующей ячейки для организации прохождения информации без преобразования, второй информационный выход каждой предыдущей ячейки соединен со вторым информационным входом последующей ячейки для организации неуправляемого переноса информации между ячейками, а второй информационный выход последней n-й ячейки среды является последовательным выходом ГППИ, на который поступает сформированная последовательность импульсов, третьи информационные выходы и третьи информационные входы всех ячеек образуют шину данных (ШД), которая дает возможность параллельно вводить в ячейки среды информацию о начальном состоянии ГППИ и параллельно считывать с него информацию, ШД подключена к БУиН, четвертый информационный вход каждой предыдущей ячейки соединен с четвертым информационным выходом последующей ячейки, образуя обратную связь между ячейками среды для передачи информации с любой последующей ячейки на любую предыдущую, в зависимости от настройки.