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

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

 

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

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

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

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

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

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

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

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

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

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

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

На фиг.1 изображена структура генератора псевдослучайных последовательностей, на которой представлены основные блоки: блок 1 формирования тактовых импульсов, блок 2 управления и настройки, блок 4 генерации псевдослучайных последовательностей, блок 3 задания структуры обратных связей и начального состояния регистра блока генерации, блок 5 программного задания кода структуры выходных последовательностей, блок 7 анализа структуры выходной последовательности, блок 6 сравнения кодов и формирования сигнала воздействия на блок генерации для изменения порядка следования состояний выхода генератора.

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

Код структуры обратных связей действует на входах блока генерации 4 в течение всего процесса генерации, код начального состояния этого блока по сигналу от блока управления 2 вводится в регистровую среду и устанавливает регистры блока 4 в начальное состояние. После установки регистров блока 4 в начальное состояние на входы тактирования блока 4 подаются с выхода блока 1 тактовые импульсы, с приходом каждого из которых блок генерации 4 переходит в новое состояние, формируя на выходе псевдослучайные двоичные последовательности. Сформированные последовательности подаются на вход блока анализа 7, в котором выполняются над ними операции, заданные программно, код результата выполнения этих операций сравнивается в блоке 6 с кодом, заданными в блоке 5, и определяет моменты формирования сигнала, вводимого в блок генерации 4, меняющего текущее его состояние и ход последовательности следования выходных состояний, этот же сигнал подается в блок 2 управления и настройки, который устанавливает блоки 6 и 7 в начальное состояние, подготавливая блоки к повторному выполнению операций анализа, сравнения и изменений порядка следования состояний. Например, если функциональная зависимость хода процесса генерации предполагает изменения хода процесса генерации при каждом появлении на выходе блока генерации 4 заданного числа импульсов, соответствующих двоичным символам 1, блок 7 будет осуществлять подсчет числа сигналов, соответствующих символу 1, сравнивать в блоке 6 с числом, записанным в блоке 5, при совпадении кодов чисел формировать на выходе сигнал изменения хода процесса генерации. Прекращение процесса генерации сводится к прекращению подачи на входы блока генерации 4 тактовых импульсов от блока 1, останов может быть организован сигналом, формируемым автономно блоком 2, либо по сигналу от внешнего устройства.

На фиг.2 в качестве примера изображена структура генератора, в котором в качестве кода структуры выходной последовательности задан код числа импульсов, соответствующих символом 1, на выходе блока генерации 4. Код, соответствующий заданному числу импульсов на выходе блока генерации 4, после поступления которых будет сформирован сигнал изменения хода процесса формирования последовательностей, записывается от внешнего устройства в регистр кода 5, сигналы с выхода блока генерации 4 подаются на вход блока анализа 7, представляющего собой двоичный счетчик, подсчитывающий число символов 1 на выходе блока генерации 4, состояние выходов счетчика подается в схему сравнения кодов 6, состояние выходов счетчика сравнивается в блоке сравнения кодов 6 с кодом на выходе регистра кода 5, при совпадении кодов блоком сравнения кодов формируется сигнал, который подается на вход блока генерации 4, меняя текущее состояние регистра этого блока, и вход блок управления и настройки 2, на выходе которого формируется сигнал сброса двоичного счетчика в начальное состояние. После обнуления счетчика начинается новый отсчет, и процесс внесения изменений в порядок следования состояний выхода генератора продолжается каждый раз при формировании на выходе блока генерации последовательности, в структуре которой имеется заданное программно число символов 1.

Литература

1. Кадиев П.А. Омаров Г. Генератор псевдослучайных последовательностей импульсов на однородной среде с программно меняющейся структурой. Патент на изобретение №2331915. Бюл.№23, 2008 г.

2. Кадиев И.П., Кадиев П.А. Однородная регистровая среда с программируемой структурой. Патент на изобретение №2449347 Бюл. №12, 2012 г.

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