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

Описание патента на изобретение RU2427885C1

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

Известно устройство генерации случайных последовательностей бит (см. патент US №07583155, МПК G06F 7/58). Устройство состоит из осциллирующего блока, который генерирует случайную последовательность бит при подаче на него шумового сигнала. Устройство также включает интегральную схему, обеспечивающую формирование случайной последовательности бит.

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

Известен генератор n-значной псевдослучайной последовательности (см. Авторское свидетельство №2081450, МПК G06F 7/58), содержащий n элементов И, блок управления, снабженный n выходами, первые входы которых соединены с соответствующими выходами блока управления, n сумматоров по модулю два и n регистров сдвига, причем выходы j-го (где ) и i-го разрядов первого регистра сдвига подключены соответственно к первому и второму входам первого сумматора по модулю два, выход k-го и (i+1)-го (где )разрядов 1-го регистра сдвига подключены соответственно к первому и второму входам 1-го сумматора по модулю два, выход первого сумматора по модулю два соединен с информационным входом одноименного регистра сдвига и с одноименным выходом блока управления, выход каждого регистра сдвига подключен к второму входу одноименного элемента И, выходы элементов И являются выходами генератора.

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

Известен генератор случайных чисел для электронных приложений (см. патент US №05871400, МПК A63F 9/21). Устройство содержит генератор на сдвиговых регистрах, в котором используются коэффициенты примитивного полинома порядка k для генерации случайных чисел, и второй генератор для формирования индекса случайного числа, хранящегося в массиве случайных чисел, полученных от генератора на сдвиговых регистрах.

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

Известны генераторы случайных перестановок и сочетаний, описанные в монографии Курейчика В.М. и др. «Комбинаторные аппаратные модели и алгоритмы в САПР»/ М.: «Радио и связь». 1990. C.185-203. Недостатками описанных генераторов являются относительно медленный спад автокорреляционных функций, генерируемых сочетаний и перестановок, низкое быстродействие при генерации некоррелированных случайных сочетаний и перестановок, возможность генерации ошибочных сочетаний, достаточно сложная конструкция при большой длине формируемых сочетаний и перестановок.

Наиболее близким к предлагаемому решению является генератор случайных чисел (см. патент РФ №2340931, МПК G06F 7/58), содержащий генератор псевдослучайной последовательности на сдвиговом регистре длиной n с линейными обратными связями, выход которого соединен с блоком управления, аналоговый генератор шума и формирователь импульсов, один выход формирователя подключен к тактовому входу генератора псевдослучайной последовательности, а второй - к блоку управления, дополнительный сдвиговый регистр хранения перестановок чисел длиной n, выход данных, тактовый вход и вход данных которого соединены с блоком управления, интерфейс - с контроллером энергонезависимой памяти, вход и выход которого соединены с блоком управления.

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

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

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

Поставленная задача решается тем, что быстродействующий генератор случайных перестановок и сочетаний состоит из блока регистров данных, выполненного с возможностью параллельной и последовательной загрузки данных q-разрядных двоичных чисел, и коммутационной матрицы, генератор имеет n q-разрядных выходов данных, образованных параллельными выходами блока регистров данных, m бинарных входов управляющих сигналов для подачи случайных сигналов от внешних источников, вход последовательной загрузки начальной строки перестанавливаемых данных, образованный входом последовательной загрузки блока регистров данных, бинарный вход управления последовательной и параллельной записью данных в блок регистров данных, вход тактовых импульсов блока регистров данных, причем параллельные q-разрядные выходы блока регистров данных электрически соединены с q-разрядными входами коммутационной матрицы, выходы коммутационной матрицы электрически соединены с параллельными q-разрядными входами блока регистров данных, коммутационная матрица имеет n q-разрядных входов, n q-разрядных выходов и состоит из переключателей, расположенных в матричном порядке по n/2 линиям и k=log2n уровням, каждый переключатель имеет два q-разрядных входа X1, X2, два q-разрядных выхода Y1, Y2 и бинарный вход управляющего сигнала, переключатели реализуют логическую функцию бинарные входы управляющих сигналов переключателей матрицы образуют m бинарных входов управляющих сигналов генератора, каждый переключатель матрицы j-го уровня, где , расположенный на линии с номером i, электрически соединен одним выходом с входом переключателя j+1 уровня, расположенного на линии с номером

а другим выходом с входом переключателя j+1 уровня матрицы, расположенного на линии с номером

,

где INT - функция вычисления целой части от аргумента, каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j, входы переключателей первого уровня являются входами матрицы, выходы переключателей k-го уровня являются выходами матрицы.

Изобретение поясняется чертежами, на фиг.1 приведена блок-схема генератора, на фиг.2 представлена диаграмма орграфа коммутационной матрицы генератора для случая n=16, на фиг.3 представлена схема генератора для случая n=16, на фиг.4 представлена схема блока регистров данных генератора для случая n=8, где

1 - блок регистров данных;

2 - коммутационная матрица с топологией baseline;

- D1 - Dn - параллельные q-разрядные входы блока регистра данных и выходы коммутационной матрицы;

- Q1 - Qn - параллельные q-разрядные выходы блока регистров данных и выходы генератора;

- S1 - Sn - q-разрядные входы коммутационной матрицы;

- C1 - Cm - бинарные входы генератора для подачи управляющих сигналов от внешних источников случайных сигналов;

- A1 - An - начальная строка q-разрядных данных, загружаемая в блок регистров данных;

- - переключатели коммутационной матрицы;

- PE - бинарный вход управления последовательной и параллельной записью данных;

S - последовательный q-разрядный вход блока регистров данных для записи элементов начальной строки данных A1-An;

- clk - вход тактовых импульсов.

Предлагаемый генератор состоит из блока регистров данных 1, выполненного с возможностью параллельной и последовательной загрузки данных, и коммутационной матрицы с топологией baseline 2. Генератор имеет n выходов данных, образованных выходами блока регистров данных, m бинарных входов управляющих сигналов, на которые подаются случайные сигналы от внешних источников, вход S последовательной загрузки начальной строки перестанавливаемых данных A1-An, образованный входом последовательной загрузки блока регистров данных, бинарный вход управления последовательной и параллельной записью данных в блок регистров данных PE, вход тактовых импульсов блока регистров данных clk. Параллельные q-разрядные выходы блока регистров данных электрически соединены с q-разрядными входами коммутационной матрицы, выходы коммутационной матрицы электрически соединены с параллельными q-разрядными входами блока регистров данных. Элементы начальной строки A1-An представляют собой бинарные строки длиной q и могут рассматриваться как двоичные числа разрядности q. Коммутационная матрица имеет n q-разрядных входов, n q-разрядных выходов и состоит из переключателей, расположенных в матричном порядке по n/2 линиям и k=log2n уровням. Каждый переключатель имеет 2 q-разрядных входа X1, X2, 2 q-разрядных выхода Y1, Y2 и бинарный вход управляющего сигнала C. Переключатели реализуют логическую функцию Входы управляющих сигналов переключателей матрицы образуют m бинарных входов управляющих сигналов генератора. Выходы переключателей предыдущего уровня соединены с входами переключателей следующего уровня в соответствии с топологией сети baseline. Данная топология описана, например, в патенте US №5175539, МПК H04J 3/00. В соответствии с этой топологией каждый переключатель матрицы j-го уровня, где , расположенный на линии с номером i, электрически соединен одним выходом с входом переключателя j+1 уровня, расположенного на линии с номером

а другим выходом с входом переключателя j+1 уровня матрицы, расположенного на линии с номером

где INT - функция вычисления целой части от аргумента. Каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j. Входы переключателей первого уровня являются входами матрицы, выходы переключателей k-го уровня являются выходами матрицы.

Устройство работает следующим образом.

Перед началом работы внешняя управляющая ЭВМ устанавливает высокий логический уровень на входе управления параллельной и последовательной записью блока регистров данных PE и по отрицательным перепадам тактовых импульсов на входе clk последовательно записывает элементы начальной строки данных A1-An в регистры данных. После этого управляющая ЭВМ устанавливает низкий логический уровень на входе управления параллельной и последовательной записью блока регистров данных PE и по отрицательным перепадам тактовых импульсов на входе clk блока регистров данных генератор формирует на своих выходах случайные перестановки элементов начальной строки данных A1-An. При этом с приходом каждого нового тактового импульса на вход clk на входы управляющих сигналов генератора C1-Cm подаются новые бинарные случайные числа 0 или 1.

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

В качестве источника случайных бинарных сигналов, подаваемых на входы управляющих сигналов C1-Cm, могут использоваться генераторы, описанные в книге Иванова М.А., Чугункова И.В. «Теория, применение и оценка качества генераторов псевдослучайных последовательностей». Например, при использовании генератора псевдослучайной последовательности на сдвиговом регистре с линейными обратными связями данные разрядов сдвигового регистра подаются на входы C1-Cm. При этом тактовые импульсы clk используются для тактирования генератора на сдвиговом регистре, обеспечивая, таким образом, синхронизацию с предлагаемым генератором перестановок и сочетаний.

Блок регистров состоит из q последовательно-параллельных регистров длиной n. При этом могут быть использованы, например, регистры К155ИР1, описанные в справочнике В.Л.Шило «Популярные цифровые микросхемы» М.: Радио и связь. 1989. с.107-110. Для получения регистра необходимой длины n используется несколько регистров К155ИР1. При этом параллельный выход последнего разряда первого регистра соединяется с последовательным входом следующего регистра и т.д. Если числа A1-An имеют несколько разрядов (q>1), в блок объединяются несколько n-разрядных регистров параллельно. При этом тактовые входы этих регистров блока соединяются между собой. Входы разрешения параллельной загрузки РЕ этих регистров также соединяются между собой. Первый разряд чисел A1-An поступает на последовательный вход первого регистра, второй - на последовательный вход второго регистра и т.д., разряд q поступает на последовательный вход регистра с номером q. Вход S, выходы Q1-Qn, входы D1-Dn блока регистров имеют q разрядов. При этом первый разряд берется с первого регистра, второй - со второго и т.д. На фиг.4 приведена возможна схема соединения шести регистров К155ИР1 блока регистров данных для хранения чисел A1-A8, имеющих q=3 разряда.

Таким образом, в зависимости от внешних источников управляющих сигналов предлагаемый генератор обеспечивает формирование псевдослучайных или случайных перестановок и сочетаний исходной строки из n=2k чисел A1-An. Перестановки и сочетания на выходе генератора имеют равномерное распределение. Генератор обладает высоким быстродействием, поскольку преобразования выполняются параллельно. Для получения любой случайной перестановки или сочетания из числа возможных достаточно подать 2 импульса на вход clk, так как последовательное соединение двух коммутационных сетей с топологией baseline обеспечивает формирование на выходе любой перестановки входных данных. Аппаратная сложность предлагаемого генератора растет практически линейно с ростом n, что дает возможность получения случайных перестановок и сочетаний элементов строк большой длины.

Похожие патенты RU2427885C1

название год авторы номер документа
УСТРОЙСТВО УПРАВЛЯЕМОГО ЦИКЛИЧЕСКОГО СДВИГА 2009
  • Сотов Леонид Сергеевич
  • Харин Валерий Николаевич
  • Соболев Сергей Сергеевич
RU2419174C1
ПРИЕМНИК ПОСЛЕДОВАТЕЛЬНЫХ МНОГОЧАСТОТНЫХ СИГНАЛОВ 1999
  • Ишмухаметов Б.Г.
  • Пусь В.В.
  • Семенов И.И.
RU2169993C1
ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ 2007
  • Молодченко Жанна Анатольевна
  • Сотов Леонид Сергеевич
  • Харин Валерий Николаевич
RU2340931C1
УСТРОЙСТВО УПРАВЛЯЕМОЙ ПЕРЕСТАНОВКИ БИТОВ БИНАРНОЙ СТРОКИ 2009
  • Молодченко Жанна Анатольевна
  • Сотов Леонид Сергеевич
  • Харин Валерий Николаевич
RU2439662C2
УСТРОЙСТВО ПЕРЕСТАНОВОК И СДВИГОВ БИТОВ ДАННЫХ В МИКРОПРОЦЕССОРАХ 2011
  • Сотов Леонид Сергеевич
RU2488161C1
МАТРИЦА ФОРМИРОВАТЕЛЯ ИНВОЛЮТИВНЫХ ПЕРЕСТАНОВОК 2010
  • Сотов Леонид Сергеевич
RU2448358C1
УСТРОЙСТВО ДЛЯ МУЛЬТИПРОГРАММИРОВАНИЯ КОНВЕЙЕРНЫХ СИСТЕМ 1996
  • Новиков А.Н.
  • Новиков В.А.
RU2127898C1
ГЕНЕРАТОР СЛУЧАЙНЫХ ПЕРЕСТАНОВОК 2009
  • Сотов Леонид Сергеевич
  • Харин Валерий Николаевич
  • Хвалин Александр Львович
RU2395834C1
Генератор случайного марковского процесса 1987
  • Гремальский Анатолий Александрович
  • Андроник Сергей Михайлович
SU1481755A1
Перестраиваемый цифровой фильтр с программируемой структурой 2016
  • Белоногов Виктор Дмитриевич
RU2631976C2

Иллюстрации к изобретению RU 2 427 885 C1

Реферат патента 2011 года БЫСТРОДЕЙСТВУЮЩИЙ ГЕНЕРАТОР СЛУЧАЙНЫХ ПЕРЕСТАНОВОК И СОЧЕТАНИЙ

Устройство относится к вычислительной, информационно-измерительной радиотехнике и может быть использовано в системах защиты информации от несанкционированного доступа. Техническим результатом является повышение быстродействия устройства. Устройство содержит блок регистров данных, выполненный с возможностью параллельной и последовательной загрузки данных, и коммутационную матрицу с топологией baseline. Устройство имеет n выходов данных, образованных выходами блока регистров данных, m бинарных входов управляющих сигналов, на которые подаются случайные сигналы от внешних источников, вход S последовательной загрузки начальной строки перестанавливаемых данных A1-An, образованный входом последовательной загрузки блока регистров данных, бинарный вход управления последовательной и параллельной записью данных в блок регистров данных РЕ, вход тактовых импульсов блока регистров данных clk. Параллельные q разрядные выходы блока регистров данных электрически соединены с q разрядными входами коммутационной матрицы, выходы коммутационной матрицы электрически соединены с параллельными q разрядными входами блока регистров данных. 4 ил.

Формула изобретения RU 2 427 885 C1

Быстродействующий генератор случайных перестановок и сочетаний, характеризующийся тем, что состоит из блока регистров данных, выполненного с возможностью параллельной и последовательной загрузки данных q-разрядных двоичных чисел, и коммутационной матрицы, генератор имеет n q-разрядных выходов данных, образованных параллельными выходами блока регистров данных, m бинарных входов управляющих сигналов для подачи случайных сигналов от внешних источников, вход последовательной загрузки начальной строки перестанавливаемых данных, образованный входом последовательной загрузки блока регистров данных, бинарный вход управления последовательной и параллельной записью данных в блок регистров данных, вход тактовых импульсов блока регистров данных, причем параллельные q-разрядные выходы блока регистров данных электрически соединены с q-разрядными входами коммутационной матрицы, выходы коммутационной матрицы электрически соединены с параллельными q-разрядными входами блока регистров данных, коммутационная матрица имеет n q-разрядных входов, n q-разрядных выходов и состоит из переключателей, расположенных в матричном порядке по n/2 линиям и k=log2n уровням, каждый переключатель имеет два q-разрядных входа X1, Х2, два q-разрядных выхода Y1, Y2 и бинарный вход управляющего сигнала, переключатели реализуют логическую функцию бинарные входы управляющих сигналов переключателей матрицы образуют m бинарных входов управляющих сигналов генератора, каждый переключатель матрицы j-го уровня, где расположенный на линии с номером i, электрически соединен одним выходом с входом переключателя (j+1)-го уровня, расположенного на линии с номером , а другим выходом с входом переключателя (j+1)-го уровня матрицы, расположенного на линии с номером , где INT - функция вычисления целой части от аргумента, каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j, входы переключателей первого уровня являются входами матрицы, выходы переключателей k-го уровня являются выходами матрицы.

Документы, цитированные в отчете о поиске Патент 2011 года RU2427885C1

ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ 2007
  • Молодченко Жанна Анатольевна
  • Сотов Леонид Сергеевич
  • Харин Валерий Николаевич
RU2340931C1
Устройство для случайного перебора перестановок 1989
  • Абдрашитов Булат Малихович
  • Гармонов Александр Алексеевич
SU1644137A1
US 5175539 A, 29.12.1992
СПОСОБ ИСПЫТАНИЯ ГРУНТОВ НА СЖИМАЕМОСТЬ СТАТИЧЕСКИМИ НАГРУЗКАМИ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ 2008
  • Хрусталёв Евгений Николаевич
  • Хрусталёва Татьяна Михайловна
  • Хрусталёва Ирина Евгеньевна
RU2419706C2
JP 2003150373 A, 23.05.2003.

RU 2 427 885 C1

Авторы

Сотов Леонид Сергеевич

Даты

2011-08-27Публикация

2010-01-25Подача