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

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

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

Недостатками аналога являются низкая точность и узкие функциональные возможности.

Аналогом предлагаемых устройств также является генератор случайных равновероятных двоичных чисел /2/, содержащий генератор случайных импульсов, триггер, генератор тактовых импульсов, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, генератор прямоугольных импульсов.

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

Прототипом предлагаемых устройств является датчик случайных чисел с равномерным распределением повышенной точности /3/, содержащий генератор прямоугольных импульсов, первый и второй счетчики, регистр, первый и второй блоки памяти, первую и вторую группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы ИЛИ и И, резистор, кнопку.

Недостатком прототипа является недостаточно высокое качество моделирования при формировании потока равномерно распределенных двоичных случайных чисел.

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

Указанная техническая задача (в первом варианте реализации датчика) решается тем, что в датчик случайных чисел с равномерным распределением повышенной точности, содержащий переключатель, резистор, генератор прямоугольных импульсов, регистр, две группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы последней из которых соединены с информационными входами регистра, выход которого является выходом датчика, а вход записи подключен к выходу генератора прямоугольных импульсов, шина нулевого потенциала соединена с первым выводом переключателя, а шина единичного потенциала соединена с первым выводом резистора, вторые выводы резистора и переключателя соединены между собой, дополнительно введены n=2^k (где k=1... - число каскадов выравнивания вероятностей двоичных случайных чисел исходных последовательностей) датчиков исходных последовательностей двоичных случайных чисел и пирамидальная матрица, элементами которой являются n-1 групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, четные и нечетные входы которых в j-том (где j=2...k) столбце матрицы подключены соответственно к выходам четных и нечетных элементов (j-1)-го столбца, а входы элементов матрицы первого столбца подключены аналогичным образом к выходам датчиков исходных последовательностей двоичных случайных чисел, тактовые входы которых объединены между собой и подключены к выходу генератора прямоугольных импульсов, а входы установки нуля объединены между собой и подключены к объединенным вторым выводам резистора и переключателя; в основном варианте датчик исходной последовательности двоичных случайных чисел содержит первый и второй элементы И-НЕ, счетчик, блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля - с первым входом первого элемента И-НЕ, выход которого соединен со входом установки нуля счетчика, выходы которого соединены с адресным входом блока памяти и входами второго элемента И-НЕ, выход которого соединен со вторым входом первого элемента И-НЕ; в одном из вариантов датчик исходной последовательности двоичных случайных чисел содержит элемент НЕ, счетчик и блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля через элемент НЕ - со входом установки нуля счетчика, выход которого соединен с адресным входом блока памяти.

Указанная техническая задача (во втором варианте реализации датчика) решается тем, что в датчик случайных чисел с равномерным распределением повышенной точности, содержащий переключатель, резистор, генератор прямоугольных импульсов, регистр, две группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы последней из которых соединены с информационными входами регистра, выход которого является выходом датчика, а вход записи подключен к выходу генератора прямоугольных импульсов, шина нулевого потенциала соединена с первым выводом переключателя, а шина единичного потенциала соединена с первым выводом резистора, вторые выводы резистора и переключателя соединены между собой, дополнительно введены n=k+1 (где k=1... - число каскадов выравнивания вероятностей двоичных случайных чисел исходных последовательностей) датчиков исходных последовательностей двоичных случайных чисел и матрица конвейерного типа, элементами которой являются n-1 групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, четные входы которых в j-том (где j=2...k) столбце матрицы подключены соответственно к выходам датчика исходной последовательности двоичных случайных чисел (j+1)-й строки, а нечетные входы - соответственно к выходам элемента матрицы (j-1)-го столбца, а четные и нечетные входы элемента матрицы первого столбца подключены соответственно к выходам датчиков исходных последовательностей двоичных случайных чисел второй и первой строки, тактовые входы датчиков исходных последовательностей двоичных случайных чисел всех строк объединены между собой и подключены к выходу генератора прямоугольных импульсов, а входы установки нуля объединены между собой и подключены к объединенным вторым выводам резистора и переключателя; в основном варианте датчик исходной последовательности двоичных случайных чисел содержит первый и второй элементы И-НЕ, счетчик, блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля - с первым входом первого элемента И-НЕ, выход которого соединен со входом установки нуля счетчика, выходы которого соединены с адресным входом блока памяти и входами второго элемента И-НЕ, выход которого соединен со вторым входом первого элемента И-НЕ; в одном из вариантов датчик исходной последовательности двоичных случайных чисел содержит элемент НЕ, счетчик и блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля через элемент НЕ - со входом установки нуля счетчика, выход которого соединен с адресным входом блока памяти.

Существенными отличиями предлагаемого технического решения являются: 1) в первом варианте реализации датчика - введение дополнительных n=2^k датчиков исходных последовательностей двоичных случайных чисел и пирамидальной матрицы, элементами которой являются n-1 групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ; 2) во втором варианте реализации датчика - введение дополнительных n=k+1 датчиков исходных последовательностей двоичных случайных чисел и матрицы конвейерного типа, элементами которой являются п-1 групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ. Эти существенные отличия обеспечивают достижение положительного эффекта - повышение качества моделирования при формировании потока равномерно распределенных двоичных случайных чисел за счет выравнивания их вероятности и снижения корреляционной взаимосвязи.

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

Схема первого варианта датчика (фиг. 1) содержит генератор 1 прямоугольных импульсов (ГПИ), выход которого соединен с объединенными между собой тактовыми входами n= 2 датчиков 2-5 исходных последовательностей двоичных случайных чисел (ДИПДСЧ), а также со входом записи регистра 6, информационный выход которого является выходом датчика, пирамидальную матрицу, элементами которой являются n-1 групп 7-9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, четные и нечетные входы которых в j-том (где j=2...k) столбце матрицы подключены соответственно к выходам четных и нечетных элементов (j-l)-го столбца, а входы групп 7-8 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого столбца подключены аналогичным образом к выходам ДИПДСЧ 2-5, входы установки нуля которых объединены между собой и подключены к объединенным вторым выводам переключателя 10 и резистора 11, первые выводы которых соединены соответственно с шинами нулевого и единичного потенциала, выходы последней группы 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, соответствующей вершине пирамидальной матрицы, соединены с информационными входами регистра 6.

Схема второго варианта датчика (фиг. 2) содержит генератор 1 прямоугольных импульсов (ГПИ), выход которого соединен с объединенными между собой тактовыми входами n=k+1 датчиков 2-5 исходных последовательностей двоичных случайных чисел (ДИПДСЧ), а также со входом записи регистра 6, информационный выход которого является выходом датчика, матрицу конвейерного типа, элементами которой являются n-1 групп 7-9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, четные входы которых в j-том (где j=2...k) столбце матрицы подключены соответственно к выходам ДИПДСЧ (j+1)-й строки, а нечетные входы - соответственно к выходам элемента матрицы (j-1)-го столбца, а четные и нечетные входы группы 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого столбца подключены соответственно к выходам ДИПДСЧ 3 и 2 второй и первой строки матрицы, входы установки нуля ДИПДСЧ 2-5 объединены между собой и подключены к объединенным вторым выводам переключателя 10 и резистора 11, первые выводы которых соединены соответственно с шинами нулевого и единичного потенциала, выходы последней группы 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ матрицы соединены с информационными входами регистра 6.

В основном варианте ДИПДСЧ 2-5 (на примере ДИПДСЧ 3, изображенного на фиг.3) содержат счетчик 12, блок 13 памяти (БП), выход которого является выходом ДИПДСЧ 3, первый 14 и второй 15 элементы И-НЕ, тактовый вход ДИПДСЧ 3 соединен с тактовым входом счетчика 12, а вход установки нуля - с первым входом первого элемента И-НЕ 14, выход которого соединен со входом установки нуля счетчика 12, выходы которого соединены с адресным входом БП 13 и входами второго элемента И-НЕ 15, выход которого соединен со вторым входом первого элемента И-НЕ 14.

В одном из вариантов ДИПДСЧ 2-5 (на примере ДИПДСЧ 2, изображенного на фиг. 4) содержит счетчик 12 и блок 13 памяти (БП), выход которого является выходом ДИПДСЧ 2, тактовый вход которого соединен с тактовым входом счетчика 12, а вход установки нуля через элемент НЕ 14 - со входом установки нуля счетчика 12, выход которого соединен с адресным входом БП 13.

В ДИПДСЧ 2-5 используются двоичные счетчики 12, например 8-разрядные. В БП 13 предварительно заносятся двоичные многоразрядные числа, например 8-разрядные, распределенные по равномерному закону.

Первый вариант датчика (фиг.1) работает следующим образом.

При замыкании контактов переключателя 10 на входах установки нуля счетчиков 12 всех ДИПДСЧ 2-5 появляется единичное напряжение, что приводит к их установке в нулевое состояние. Выходной код счетчиков 12, соответственно, ко входам БП 13 - в результате на их выходах появляются двоичные 8-разрядные числа А, В, С, D, хранящиеся в ячейках с адресом 00000000. Эти числа прикладываются, соответственно, к первым и вторым входам первого столбца пирамидальной матрицы групп 7-8 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ. На выходе последних появляются двоичные 8-разрядные числа Е и F, получающиеся как результат сложения по модулю два поданных попарно с выходов ДИПДСЧ 2-5 чисел А, В, С, D. Этот результат пропускается последней группой 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, соответствующей вершине пирамидальной матрицы, на вход регистра 6. По переднему фронту первого импульса с выхода ГПИ 1 результат суммы G с выхода группы 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ записывается в регистр 6. В результате в первом такте на выходе датчика появляется число G, получающееся как результат двойного попарного сложения по модулю два четырех многоразрядных чисел A, B, C, D, хранящихся в ячейках БП 13 с адресом 00000000 ДИПДСЧ 2-5.

По заднему фронту первого импульса с выхода ГПИ 1 содержимое счетчиков 12 всех ДИПДСЧ 2-5 становится равным 00000001. При этом на выходах ДИПДСЧ 2-5 появляются, соответственно, новые числа, хранящиеся в ячейках БП 13 с адресом 00000001. Новое значение числа G записывается в регистр 6 по переднему фронту следующего импульса с выхода ГПИ 1.

В следующих тактах датчик работает аналогично.

После окончания 251-го такта ГПИ 1 содержимое счетчиков 12 ДИПДСЧ 5 становится равным 11111011. При этом все входные сигналы элемента И-НЕ 15 ДИПДСЧ 5 (который используется в 7-входовом исполнении, причем его входы подключены к 1, 2, 4-8 разрядам выхода счетчика 12 ДИПДСЧ 5) становятся единичными, на его выходе появляется нулевое напряжение, которое, проходя через элемент И-НЕ 14, преобразуется в единичное напряжение и обнуляет содержимое счетчика 12 ДИПДСЧ 5. В результате в 252-м такте на выходе БП 13 ДИПДСЧ 5 появляется число, хранящееся в его первой ячейке с адресом 00000000. При этом содержимое счетчиков 12 ДИПДСЧ 2-4 продолжает увеличиваться.

Аналогичным образом путем использования 7-входового элемента И-НЕ 15, подключаемого к 1, 3-8 разрядам выхода счетчика 12, длительность периода работы (и, соответственно, количество заложенных в БП 13 двоичных случайных чисел исходной последовательности) ДИПДСЧ 4 задается равной 253 тактам ГПИ 1.

Аналогичным образом путем использования 8-входового элемента И-НЕ 15, подключаемого к 1-8 разрядам выхода счетчика 12, длительность периода работы ДИПДСЧ 3 задается равной 255 тактам ГПИ 1.

В качестве ДИПДСЧ 2 используется вариант его реализации, изображенный на фиг.3. В этом случае длительность периода работы ДИПДСЧ 2 оказывается равной 256.

Использование ДИПДСЧ 2-5 с длительностями периодов их работы, выражаемыми взаимно простыми числами, позволяет генерировать на выходе датчика последовательность случайных чисел, длительность периода которых равняется произведению длительностей исходных последовательностей, т.е. в рассматриваемом примере 256•255•253•251=4145475840.

Таким образом, благодаря тщательному "перемешиванию" чисел из БП 13 ДИПДСЧ 2-5 (путем их последовательного попарного сложения по модулю два каждым столбцом пирамидальной матрицы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 7-9 со сдвижкой адресов ячеек БП 13 на единицу через цикл работы счетчика 12 в каждом ДИПДСЧ 2-5) на выходе датчика формируется последовательность равномерно распределенных слабокоррелированных случайных двоичных чисел.

Второй вариант датчика (фиг.2) работает следующим образом.

Динамика работы первого и второго вариантов датчика одинакова. Разница заключается лишь в получаемых в каждом j-том столбце матрицы числах. В частности, на выходе элемента первого столбца матрицы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 7 появляется число Е как результат сложения по модулю два чисел А и В исходных последовательностей, так же, как и в первом варианте датчика.

Однако на выходе элемента второго столбца матрицы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 8 появляется уже число Н как результат сложения по модулю два чисел Е и С - здесь уже наблюдается отличие от первого варианта датчика.

На выходе третьего столбца матрицы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 9 появляется число М как результат сложения по модулю два чисел Н и D и т.д.

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

Преимуществами предлагаемых технических решений по сравнению с известными являются повышение качества моделирования при формировании потока равномерно распределенных случайных двоичных чисел за счет выравнивания их вероятности и снижения корреляционной взаимосвязи - доказательство указанных преимуществ для случая k=1 приведено в /4/. Схемы первого и второго вариантов датчика легко реализуются на широко распространенных интегральных микросхемах отечественного производства.

Список источников информации, принятых во внимание при составлении описания заявки
1. А.с. 285344 СССР, МКИ G 06 F 7/58, 1969.

2. А.с. 1374221 СССР, МКИ G 06 F 7/58, 1986.

3. А.с. 2103726 РФ, МПК G 06 F 7/58, 1998 (прототип).

4. Ермаков В.Ф., Гудзовская В.А. Сравнительный анализ аппаратурного моделирования равномерно распределенных случайных двоичных чисел // Изв. вузов. Сев.-Кавк. регион. Техн. науки. - 1994. - 3-4. - С.18-28.

Изобретения относятся к вычислительной технике и могут быть использованы для статистических исследований. Техническим результатом является расширение функциональных возможностей. Датчики содержат переключатель, резистор, генератор прямоугольных импульсов, регистр, две группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ. Первый вариант датчика содержит датчики исходных последовательностей двоичных случайных чисел, пирамидальную матрицу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, а второй вариант датчика содержит матрицу конвейерного типа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ. 2 с. и 4 з.п.ф-лы, 4 ил.

1. Датчик случайных двоичных чисел с многокаскадным выравниванием (первый вариант), содержащий переключатель, резистор, генератор прямоугольных импульсов, регистр, две группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы последней из которых соединены с информационными входами регистра, выход которого является выходом датчика, а вход записи подключен к выходу генератора прямоугольных импульсов, шина нулевого потенциала соединена с первым выводом переключателя, а шина единичного потенциала соединена с первым выводом резистора, вторые выводы резистора и переключателя соединены между собой, отличающийся тем, что в него введены n=2^k (где k=1,...- число каскадов выравнивания вероятностей двоичных случайных чисел исходных последовательностей) датчиков исходных последовательностей двоичных случайных чисел и пирамидальная матрица, элементами которой являются n-1 групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, четные и нечетные входы которых в j-м (где j=2,..., k) столбце матрицы подключены соответственно к выходам четных и нечетных элементов (j-1)-го столбца, четные и нечетные входы элементов матрицы первого столбца подключены соответственно к выходам четных и нечетных датчиков исходных последовательностей двоичных случайных чисел, тактовые входы которых объединены между собой и подключены к выходу генератора прямоугольных импульсов, а входы установки нуля объединены между собой и подключены к объединенным вторым выводам резистора и переключателя. 2. Датчик по п.1, отличающийся тем, что в основном варианте датчик исходной последовательности двоичных случайных чисел содержит первый и второй элементы И-НЕ, счетчик, блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля - с первым входом первого элемента И-НЕ, выход которого соединен со входом установки нуля счетчика, выходы которого соединены с адресным входом блока памяти и входами второго элемента И-НЕ, выход которого соединен со вторым входом первого элемента И-НЕ. 3. Датчик по п.1, отличающийся тем, что в одном из вариантов датчик исходной последовательности двоичных случайных чисел содержит элемент НЕ, счетчик и блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля через элемент НЕ - со входом установки нуля счетчика, выход которого соединен с адресным входом блока памяти. 4. Датчик случайных двоичных чисел с многокаскадным выравниванием (второй вариант), содержащий переключатель, резистор, генератор прямоугольных импульсов, регистр, две группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы последней из которых соединены с информационными входами регистра, выход которого является выходом датчика, а вход записи подключен к выходу генератора прямоугольных импульсов, шина нулевого потенциала соединена с первым выводом переключателя, а шина единичного потенциала соединена с первым выводом резистора, вторые выводы резистора и переключателя соединены между собой, отличающийся тем, что в него введены n=k+1 датчиков исходных последовательностей двоичных случайных чисел и матрица конвейерного типа, элементами которой являются n-1 групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, четные входы которых в j-ом (где j=2,..., k) столбце матрицы подключены соответственно к выходам датчика исходной последовательности двоичных случайных чисел (j+1)-й строки, а нечетные входы - соответственно к выходам элемента матрицы (j-1)-гo столбца (j-1)-й строки, четные и нечетные входы элемента матрицы первого столбца подключены соответственно к выходам датчиков исходных последовательностей двоичных случайных чисел второй и первой строк, тактовые входы датчиков исходных последовательностей двоичных случайных чисел всех строк объединены между собой и подключены к выходу генератора прямоугольных импульсов, а входы установки нуля объединены между собой и подключены к объединенным вторым выводам резистора и переключателя. 5. Датчик по п.4, отличающийся тем, что в основном варианте датчик исходной последовательности двоичных случайных чисел содержит первый и второй элементы И-НЕ, счетчик, блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля - с первым входом первого элемента И-НЕ, выход которого соединен со входом установки нуля счетчика, выходы которого соединены с адресным входом блока памяти и входами второго элемента И-НЕ, выход которого соединен со вторым входом первого элемента И-НЕ. 6. Датчик по п.4, отличающийся тем, что в одном из вариантов датчик исходной последовательности двоичных случайных чисел содержит элемент НЕ, счетчик и блок памяти, выход которого является выходом датчика исходной последовательности двоичных случайных чисел, тактовый вход которого соединен с тактовым входом счетчика, а вход установки нуля через элемент НЕ - со входом установки нуля счетчика, выход которого соединен с адресным входом блока памяти.