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

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

Иллюстрации

Показать все

Реферат

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

В настоящее время известно много способов получения синхронных случайных чисел. А.С. СССР №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.

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

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