Способ формирования случайных двоичных чисел



Способ формирования случайных двоичных чисел
Способ формирования случайных двоичных чисел
Способ формирования случайных двоичных чисел
Способ формирования случайных двоичных чисел
Способ формирования случайных двоичных чисел
Способ формирования случайных двоичных чисел
Способ формирования случайных двоичных чисел
Способ формирования случайных двоичных чисел

 


Владельцы патента RU 2409836:

Федеральное государственное учреждение 24 Центральный научно-исследовательский институт Министерства обороны РФ (RU)

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

 

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

В настоящее время известно много способов получения синхронных случайных чисел. А.С. СССР №14342, патент США №374850, патент ФРГ №1189582, 1765031.

Известен способ вероятностного преобразования потока чисел (прототип) [Гилл А. «Синтез вероятностных преобразователей». Кибернетический сборник, 1964 г. №8].

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

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

- вероятность сбоев генераторов гаммы неприменимо для этих целей;

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

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

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

Известно [В.Феллер. Введение в теорию вероятностей и ее приложение. «Мир», М.: 1964 г.], что нулевой выигрыш в этой игре представляет маловероятное событие, а гораздо более вероятно, что один из игроков в серии розыгрышей будет впереди, смена лидеров внутри серии также представляет маловероятное событие. Таким образом, последовательность из нулей и единиц преобразуется в единицу, если число единиц больше числа нулей, в противном случае в «нуль». Чтобы исключить неопредедленность в решении при первом исходе число импульсов в последовательности берется негативным, а разность в серии между числом единиц и нулей показывает, какое число ошибок можно получить данным способом.

Структурная схема, реализующая предлагаемый способ, показана на Фиг.1.

Она содержит:

1 - регистр сдвига емкостью 2к;

2 - счетчик тактовых импульсов емкостью 2m+1;

3 - генератор случайных чисел;

4 - вход единиц регистра сдвига;

5 - вход нулей регистра сдвига;

6 - блок формирования двоичного числа;

7 - выход единиц регистра сдвига;

8 - выход нулей регистра сдвига;

9 - блок записи двоичных чисел.

В исходном положении в регистре сдвига 1 нет записанной единицы. С началом работы счетчик тактовых импульсов 2 записывает в первую ячейку правой или левой половины регистра сдвига <<единицу>> в зависимости от того, какой импульс «0» или «1» поступит в него от генератора случайных чисел 2. В дальнейшем регистр сдвига 1 управляется генератором случайных чисел 3 по двум входам: входу единиц и входу нулей. Записанная от счетчика тактовых импульсов 2 единица под воздействием «1» и «0», приходящих от генератора случайных чисел 3, совершает случайное блуждение: «1» перемещает записанную единицу вправо на одну ячейку, «0»

- влево на одну ячейку. Как только счетчик тактовых импульсов 2 отсчитает n=2m+1 тактовых импульсов, на блок формирования двоичного числа 6 от счетчика тактовых импульсов 2 подается импульс, и блок формирования двоичного числа 6 производит следующие операции:

- опрос выходов регистра сдвига 7, 8;

- запись «0» или «1» в зависимости от того, в какой части регистра - левой или правой находится записанная первоначально «1», совершившая случайное блуждание, т.е. на каком выходе оно находится на момент опроса;

- стирает эту единицу после записи числа, т.е. возвращает схему в исходное положение.

С блока формирование двоичного числа 6 двоичное число поступает в блок записи двоичных чисел 9, и далее цикл повторяется.

Временная диаграмма движения (траектория) записанной единицы в течение одного цикла n=64, смоделированная с помощью таблицы случайных чисел [Митропольский А.К. «Техника статистических вычислений». «Наука». М.: 1971].

На Фиг.2 изображена временная диаграмма возможного движения «блуждающей» единицы по ячейкам схемы случайного блуждания при n=64. Из нее видно, что при модулировании четного числа давали «0», нечетные «1». Из Фиг.2 также видно, что разность между нулями и единицами в конце цикла достигает 12, т.е. в данном случае можно исправить 12 ошибок типа единица заменена на ноль.

Траектория движения единицы по ячейкам реверсивного регистра сдвига, изображенная на Фиг.2, обладает двумя особенностями:

- записанная единица пребывает все время в одной половине регистра;

- максимум отклонения от центра регистра, т.е. максимум разности между нулями и единицами достигается в конце цикла.

Эти особенности процесса являются устойчивыми, они хорошо изучены и достаточно широко освещены в литературе по теории вероятности и случайным процессам [С.Карлин. Основы теории случайных процессов. «Мир», М.: 1971 г.; Ю.В.Прохоров, Ю.А.Розанов. Теория вероятности». «Наука», М.: 1967 г.].

В частности доказано, что доля времени, проведенного (в нашем толковании) «единицей» в одном половине регистра, чаще всего оказывается близкой к 0 или 1, а для разности нулей и единиц существует смысловая тенденция к расположению максимумов вблизи начальной и конечной точки цикла.

Обе эти особенности подчиняются закону арксинус, и Фиг.3 иллюстрирует сказанное. На Фиг.3 показан график функции плотности вероятностей времени пребывания «блуждающей» единицы в одном из блоков схемы случайного блуждания.

Здесь n - общее число тактовых импульсов;

P - число тактов, в течение которых записанная единица находится в одной правой

половине (например, в блоке единиц);

- доля времени, проведенного записанным единицей M в блоке n «единиц».

0≤α≤1

Аналитическое выражение для плотности вероятности имеет вид

при 0≤α≤1

Интегральная функция распределения имеет вид

0≤α≤1

Закон арксинуса - это предельное соотношение, т.е. при n→∞, однако он хорошо выполняется уже при n=20. На Фиг.3 график дан для n=64.

На Фиг.4в показан график функции плотности вероятности положения максимума траектории импульса, здесь

0≤β≤1

На Фиг.4а, б, в n - номер тактового импульса, при котором траектория записанной единицы принимает наибольшее положительное значение номером ячеек блока «нулей 2 присвоен отрицательный знак. В случае, когда n располагается в начале и конце цикла приведены для иллюстрации на Фиг.4б и 4а соответственно.

На Фиг.5 показан график функции отношения вероятности ошибки в формируемой последовательности к вероятности ошибки в исходной последовательности в зависимости от длительности цикла n.

Из графика видно, что независимо от исходной ошибки Pe предлагаемым способом можно снизить вероятность выходной ошибки PΣ на порядок при n=64.

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



 

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к связи, более конкретно к технологиям для формирования последовательностей скремблирования и дескремблирования в системе связи

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

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

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