Устройство для непрерывного экспресс-анализа потоков случайных чисел Советский патент 1984 года по МПК G06F17/18 

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

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

УСТРОЙСТВО ДЛЯ НЕПРЕРЫВНОГО ЭКСПРЕСС-АНАЛИЗА ПОТОКОВ СЛУЧАЙНЫХ ЧИСЕЛ, содержащее приемный регистр, схему сравнения, блок памяти, блок управления, состоящий из регистра сдвига, элемента И и элемента ИЛИ, первый вход которого соединен с первым выходом регистра сдвига, второй выход которого подключбгг к второму входу элемента ИЛИ и к первому входу элемента И, второй вход которого объединен со сдвиговым входом регистра сдвига, генератор тактовых импульсов и счетчик адреса, отличающееся тем, что, с целью повышения точности при обеспечении непрерывности режимов анализа и вывода результатов, в него введены |соммутаторы, накопительные счетчики, счетчик интервалов, блок адаптации и счетчики объема выборки, вход первого из которых объединен с входом синхронизации приемного регистра, входом стробирования схемы сравнения и является входом синхронизации устройства, выход первого счетчика объема выборки подключен к информационному входу первого коммутатора, вькод которого через второй счетчик объема выборкисоединен со сдвиговым входом регистра сдвига блока управления, вход синхронизации регистра сдвига соединен с выходом генератора тактовых импульсов, а третий выход регистра сдвига блока управления соединен с входами установки в О первого и второго накопительных счетчиков, информационньш вход приемного регистра является информационным входом устройства, а выход соединен с первым информационным входом схемы сравнения, (Л выход которой соединен со счетным входом первого накопительного счетчика, а второй вход объединен с первым информационным входом второго коммутатора и подключен к информационному выходу счетчика интервалов , вход которого объединен с первым входом записи блока памяти и подключен к выходу элемента И блока управления, выход элемента ИЛИ которого эо подключен к управляющему входу вто00 рого коммутатора, выход которого соединен с адресным входом блока памяти, второй вход записи которого подключен к выходу второго накопительного счетчика, информационный вход которого соединен с выходом третьего коммутатора, информационный вход которого соединен с выходом первого накопительного счетчика, выход счетчика адреса соединен с вторым информационным входом второго коммутатора и является управляющим выходом устройства, при этом выходы переполнения

Изобретение относится к вычислительной технике и предназначено для определения вида функций плотности вероятности (гистограммы), последовательности случайных чисел, например в качестве статистического моделирования, ориентировано для проведения оперативного непрерывног контроля законов распределения пара метров формируемого процесса и выво да гистограммы на координатное устройство визуального отображения (осциллограф, самописец, газоразряд ная панель и др.). Известны устройства для анализа функций плотности вероятности. Из этих устройств выделяется большо класс аналоговых средств анализа, ориентированных на анализ непрерывных процессов. Зачастую непрерывный исследуемый сигнал оцифровывают а дальнейшую его обработку выполняю цифровыми средствами (аналого-цифро выми анализаторами). Естественноэ что цифровые последовательности про ще анализировать цифровыми анализаторами. Сохраняя известные принципы анализа, цифровые анализаторы строятся зачастую по известным решениям цифровой части аналого-цифровых анализ торов. Точность анализа в них определяется разрядностью и объемом выборок анализируемых кодов. Однако конкретные задачи зачастую требуют новых качеств, что приводит к новым техническим решениям. Цифровые анализаторы плотности вероятности (как и аналоговые) содержат собственно анализатор и средства вьшода результатов. Средства вьшода не всегда описываются при описании структуры анализатора, хотя такие средства должнь всегда присутствовать. Известно устройство для анализа распределений случайных процессов, содержащее аналого-цифровой преобразователь, блок памяти, комбинационньй сумматор, блок управления fij , Недостатком устройства является то, что для обеспечения его работы блок управления должен содержать большое количество оборудования, кроме того, сложно обеспечить непрерывный вывод результатов анализа. Известен анализатор амплитудных распределений, содержащий аналогоцифровой преобразователь, адресный дешифратор, блок выбора оценки, запоминающее устройство, сумматор, блок элементов 2И-ИЛИ, счетчик адреса утечек, триггер управления адресом, регистр сдвига и ключ, В устройстве применен оригинальный метод стохастической аппроксимации оценки (экспоненциальное сглаживание) ff . Однако в данном устройстве нельзя организовать непрерьшный режим работы, так как для вывода результатов анализ нужно останавливать , Наиболее близким по технической сущности к изобретению является устройство для построения амплитудных гистограмм, содержащее измерительное устройство сравнения, преобразователь код - аналог, регистр адреса, генератор тактовых импульсов. 3. устройство управления, запоминающее устройство, арифметический регистр з. Однако известное устройство с точки зрения использования его дл целей экспресс-анализа потоков случайных чисел не обеспечивает требуе мой оперативности получения (отобра жения) результатов анализа, имеет аппаратурную избыточность. Кроме того, известное устройство не позво ляет адаптировать алгоритм работы к характеру, ввиду закона распределения исследуемого процесса и, тем самым, повысить точность анализа в ходе самого анализа. Точность анализа зависит от зако на распределения анализируемого про цесса. В ряде случаев это позволяет повысить точность анализа без дополнительных аппаратурных затрат. Устройства (или части устройств) анализирующие поступающую последовательность случайных кодов, по при ципу анализа можно разбить на два класса: устройство последовательног и устройства параллельного анализа. В анализаторах последовательного типа уровень дифференциального кори дора анализа изменяется последовательно по области существования процесса. В анализаторах параллельного типа область существования измеряемого случайного параметра разбита на число равномерных интервалов, количество которых равно количеству квантилей анализа при постро нии гистограммы. Поступающие случайные числа попа дают в соответствующие интервалы, выборки в которых накапливаются параллельно. Иногда парал:ельные анализаторы называют многоканальными, так как использование параллельного анализатора эквивалентно использованию п последовательных анализаторов , каждый на свой уровень (интервал, канал) , для достижения аналогичного быстродействия, где п - число квантилей анализа. Несмотря на то, что параллельные анализаторы плотности вероятности имеют в п раз более высокое быстродействие, аппаратурные затраты на и реализацию не на много выше, так ка в качестве селектора уровней можно применить параллельный дешифратор. 94 а в качестве накопительных элементов - блок памяти. По,какому принципу строить анализатор определяется из требований к быстродействию, аппаратурным затратам, дополнительным возможностям. В то же время точность анализа определяется не принципом анализа, а объемом выборки в квантили, шириной квантили (дифференциального коридора анализа) и видом закона распределения анализируемого параметра. Причем среднеквадратичная по- . грешность матожидания в квантили °rriz n г 9 где Z - случайный процесс х, N - объем выборки; X,, - коэффициент изменчивости случайного процесса z. Оптимальная, с точки зрения минимума суммарной погрешности, ширина интервала (дифференциального коридора) анализа Ali iAbLL где х - нормированный случайный процесс; 4(Vv,)- функция плотности вероятности кормированного случайного процесса. Отсюда видно, что погрешность анализа в значительной степени определяется видом функции плотности вероятности, а для получения равных погрешностей при измерении разных законов распределения требуются разные объемы выборки. Для получения нормированной гистограммы общепринятым является соблюдение соотношения Nt р N max где N - объем выборки в квантили; . N.,- емкость накопительного элемента в квантили анализа. Максимально измеряемая вероятность попадания в квантиль таким образом равна единице, что гарантирует отсутствие искажений гистограммы (из-за переполнений накопительного элемента, например счетчика), если даже все отсчеты измеряемого параметра попадут в один интервал

При этом

14 1

где trig, - матожидание в i-м интервале анализа; к - количество интервалов анализа.

Результаты анализа хорошо отражают ocHOBHi ie соотношения теории вероятностей. Точность анализа можно увеличить, если изменить форму представления результата.

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

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

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

5 выходу второго накопительного счетчика, информационный вход которого соединен с выходом третьего коммутатора, информационный вход котороIo соединен с выходом первого нако0 пительного счетчика, выход счетчика адреса соединен с вторым информационным входом второго коммутатора и является управляющим выходом устройства, при этом выходы пере5 полнения второго накопительного

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

5 и первого коммутаторов устройства.

На фиг. 1 представлена схема предлагаемого устройства; на фиг.2блок адаптации; на фиг. 3 - гистограмма .

Устройство (фиг. 1) содержит приемный регистр 1, схему 2 сравнения, блок 3 памяти, блок 4 адаптации, блок 5 управления, генератор 6 тактовых импульсов, счетчик 7 адреса, коммутатор 8, накопительньм счетчик 9, коммутатор 10, накопительный счетчик 11, счетчик 12 объема выборки, коммутатор 13, счет1чик 14 объема выборки, счетчик 15 интервалов. Блок 5 управления содержит сдвигающий регистр 16, элемент ИЛИ 17, элемент И 18. Причем приемный регистр 1, схема 2 сравнения, счетчик 9, коммутатор 10, счетчик 11, блок 3 памяти соединены последовательно, первый вход приемного регис ра является входом анализируемых кодов, второй вход соединен с треть им входом схемы 2 сравнения, с первым входом счетчика 12 объема выбор ки и является входом синхронизации устройства, счетчик 12 объема выбор ки, коммутатор 13, счетчик 14 объем выборки, блок 5 управления соединен последовательно, вторые входы счетчиков 9 и 11 соединены с одним выходом блока 5 управления, другой выход которого соединен с вторым вх дом блока 3 памяти и первым входом коммутатора 8, третий - со счетчиком 15 интервалов и с третьим входом блока 3 памяти, первый выход счетчика 15 интервалов соединен с вторым входом схемы 2 сравнения и с третьим входом коммутатора 8, вто рой - с BTOpbiM входом блока 4 адаптации, второй выход счетчика 11 сое динен с первым входом блока 4, первый выход которого соединен с вторым входом коммутатора 10, второй - с входом коммутатора 13, выхо генератора 6 тактовых импульсов сое динен с вторым входом блока 5 управ ления и входом счетчика 7 адреса, выход которого соединен с вторым вх дом коммутатора 8 и является выходом устройства, выход коммутатора 8 соединен с адресным входом блока 3 памяти, выход которого является выходом устройства. Кроме того, первы вход блока 5 управления соединен с входом сдвигающего регистра 16 и с вторым входом элемента И 18, второй вход блока 5 управления соединен с другим входом сдвигающего регистра 16, первый выход которого соединен с первым входом элемента ИЛИ 17 второй - с первым входом элемента И 18, и с вторым входом элемента ИЛИ 17, третий является первым выходом блока 5 управления, выход элемента ИЛИ 17 является вторым, а выход элемента И 18 - третьим выходами блока 5 управления. 98 Блок 4 адаптации выполняет функцию адаптации алгоритма работы устройства к характеру анализируемого процесса. Одна из возможных его реализайий показана на фиг. 2. Возможны как более сложные варианты построения блока 4, так и простейшие. Самым простым является вариант внешнего управления, когда на вторые входы второго 10 и третьего 13 коммутаторов подаются коды либо из управляющих регистров, доступных ЭВМ, либо из наборных регистров при ручном управлении. В любом случае сигналом к стробированию блок-а регулирования будет сигнал переполнения на втором выходе счетчика 11, который может запоминаться триггером, а далее индицироваться на панели управления. Особенностью данного устройства является представление результата анализа (гистограммы) с переменным показателем максимально измеряемой вероятности Р. На примере анализа равномерного закона распределения покажем как это влияет на точность измерений. Если - 1 , где N - объем выборки в квантили (интервале анализа); NH - емкость накопительного элемента и число интервалов анализа равно щестнадцати, гистограмма будет иметь вид, показанный на фиг. За. Для восприятия, особенно для идентификации разбаланса вероятности попадания в интервал такое представление неудобно. Изменив соотношение |- 0.5 или |- 0,Т25 мы получим результат (гистограмму) в виде, показанном на фиг. 35, Б , и Ь , 1 соответственно. Дальнейшее уменьшение до NU 1 N Тб приводит к тому, что возникают искажения гистограммы фиг. 32, из-за переполнения емкости накопительного элемента. При анализе потоков равномерно-распределенных чисел такой режим оказывается полезным, так как по устойчивому высокому или низкому положению столбца гистограммы можно более точно судить об отклонении соответствующего двоичного разряда от равновероятности. Оптимальным следует считать минимальное значение из ряда , , 0,5; 0,25; 0,125... не приводящее к искажению гистограммы. Выбирать это значение можно как вручную, так и автоматически. Изменять РПЮ к можно: уменьшением N при постоянном N, тогда при том же объеме выборки (вре мени анализа) изменится лишь представление результата, что однако позволяет.повысить субъективную томность восприятия результатов при их выводе на отображающее устройство; увеличением N при постоянном N, что увеличит время анализа, а главное принесет положительный эффект, выраженный в уменьшении среднеквадратичной погрешности (1) результатов анализа, а также одновременном увели чении размеров гистограммы при выводе на отображающее устройство, что повьшает эффективность использования площади экрана отображения и точност восприятия результата; ., согласованным изменением --, позволяет при оптимальном использова нии экрана отображающего устройства изменять объем выборки, тем самым изменять время анализа и его состоятельность. Повышение точности (состоятельности или снижения величины среднеквадратичной погрешности) анализа в полном соответствии с теорией оценок (1) получается путем увеличения объема выборки N, но в отличие от известных решений, во-первых, в предложенном устройстве снижаются аппаратурные затраты, так как при накопительного элеразрядностьмента (счетчика) и блоков реализующих вывод результатов может быть меньше разрядности элемента (счетчика) задающего объем выборки при той же точности анализа, во-вторых, повышается субъективная точность восприятия результатов анализа путем оп тимального использования экрана отоб ражающего устройства. Процесс работы устройства можно условно разделить на три цикла. Цикл накопления статистики в заданном интервале анализа (цикл анализа) цикл перезаписи накопленной статистики с выхода накопительных счетчиков в блок памяти; непрерывный цикли ческий вывод содержимого блока памяти на средства отображения или интерпретации результата. Причем накопление статистик и вывод результатов происходит непрерывно и параллельно во времени. Номер интервала, в котором производится накопление статистики, определяется состоянием счетчика 15 интервалов. Накопление происходит следующим образом. Анализируемые коды поступают на первый вход приемного регистра 1, в которьпд они -записываются фронтом сопровождающего синхроимпульса, приходящего на второй вход. Принятое в регистр число схемой 2 сравнения сравнивается с состоянием счетчика 15 интервалов и при их совпадении, на выходе схемь 2 сравнения, стробируемой сопровождающим синхроимпульсом, отработается импульс, который затем увеличивает состояние первого счетчика 9 на единицу. Выходы старших разрядов счетчика 9 заведены на входы коммутатора 10 который в зависимости от управляющего кода На втором входе, один из этих разрядов подключает к первому (счетному) входу счетчика 11 (фиг. 2), содержимое которого после цикла накопления и определяет величину статистики в интервале анализа. Количество сопровождающих синхроимпульсов подсчитывается первым и вторым счетчиками 12 и 14 объема выборки, причем величина объема выборки определяется емкостью составного счетчика, образованного счетчиками 12 и 14 и коммутатором 13. Окончание цикла анализа и начало цикла перезаписи происходит при появлении сигнала логической единицы на выходе переноса счетчика 14. В ходе цикла перезаписи содержимое счетчика 11 записывается в блок 3 памяти по адресу, определяемому состоянием счетчика 15 интервалов. То есть вместостатистики, накопленной в предыдущем цикле для данного интервала анализа, в блок 3 памяти записывается новая. Осуществляется это следующим образом. Сигнал переноса с выхода счетчика 14 поступает на первьй вход блока 5 управления, а в нем на вход сдвига регистра 16 сдвига. Далее импульсами генератора 6 тактовых импульсов, приходящими на второй вход блока 5 управления, а в нем на вход синхронизации сдвига регистра 16, в котопервьйом единица, поступающая на вход, сдвигается в сторону младших разрядов. В процессе сдвига единицы по разрядам регистра на выходе блока 5 управления формирутотся управляю щие сигналы: на третьем выходе блока управления - сигналы записи, на второи выходе блока управления управляющий сигнал, который одновременно увеличивает состояние счетчика 15 интервалов на единицу, на пер,вом - сигнал установки в О первого и второго накопительных счетчиков. Причем запись в блок памяти осуществ ляется по адресу, который по сигналу подготовки на первом входе коммутатора 8 передается с выхода счетчика 15 интервалов через коммутатор 8 на четвертьм (адресный) вход блока 3 памяти. При отсутствии сигнала с вто рого выхода блока 5 управления, вход адреса блока 3 памяти подключен к выходу счетчика 7 адреса. В ходе цик ла перезаписи за три периода генератора 6, необходимых для сдвига единицы в регистре 16 блока 5 управления на три разряда, содержимое счетчика 11 переписывается в блок 3 памяти. Кроме того, увеличением состоя ние счетчика 15 интервалов на единицу, устанавливается новый интервал анализа. Счетчики 9 и 11 обнуляются импульсом с первого выхода блока 5 управления, а счетчики 12 и 14 объема выборки после переполнения обнуляются автоматичбски, так как после комбинации Все единицы в счетчике следует комбинация Все нули. Вывод результата, как и накопление интервальных статистик, происходит непрерывно и прерывается только на три такта генератора 7 для записи результата очередного цикла анализа в блок 3 памяти. Для реализации непрерывного вывода в устройство введены счетчик 7 адреса и коммутатор 8 Счетчик 7 адреса работает в режиме непрерывного счета импульсов генератора 6 тактовых импульсов, его выходы через коммутатор 8 заведены на адресные входы блока 3 памяти. По линейно-циклическим изменяющимся адресам, формируемым счетчиком 7, происходит непрерывное, циклическое считывание содержимого блока 3 памяти. Используя выходы счетчика 7 адреса для управления разверткой по оси X, а выходы блока памяти - по оси У, легко осуществить вывод гист граммы на любое кординатное устройство отображения, при Необходимости выходные коды можно преобразовать в аналоговьпТ: сигнала с помощью преобразователей код - аналог (в простейшем случае сеток R-2R). Управление величиной Р, т.е. величиной и отношением емкости составных накопительного Сгетчика и счетчика объема выборки, осуществляется кодами с выходов блока 4 сядаптации, подаваемыми на управляю11ие входы коммутаторов 10 и 13. Одна из возможных реализаций блока 4 адаптации представлена на фиг. 2. В данном варианте он состоит из триггера 19, элемента И 20, счетчика 21 и регистра 22. Начальное значение предположительно минимальное определяется кодами, занесенными в регистр 22, причем код, управляющий коммутатором 10, предварительно заносится в счетчик 21, если априорное представление о процессе не верно и возникло переполнение счетчика 11, то сигнал переполнения поступит на первьй вход блока 4 и установит триггер 19 в единицу. В этом случае по окончании анализа всей области существования анализируемого потока, импульс переполнения с выхода счетчика 15 интервалов придет на второй вход блока 4 адаптации, пройдет через элемент И 20 (на втором входе которого уровень логичес- кой единшда с выхода триггера 19), увеличит содержимое счетчика 21 на единицу, установит триггер 19 в О. Так как код с выхода счетчика 21 управляет коммутатором fO, то по входу счетчика 11 теперь будет подключен следующий старший разряд счетчика 9 и суммарная емкость составного счетчика-накопителя увеличится и величина соответственно увеличится вдвое. Если переполнение счетчика 11 отсутствует, то увеличение состояния счетчика 21 не происходит. Возможны другие, как более простые 5 так и более сложные варианты реализации блока регулирования. Повьшение точности анализа законов распределения достигается за счет адаптации анализатора к виду распределения анализируемых кодов путем выбора оптимального значения величины Р|пс() Наибольший эффект достигается при анализе потоков равно131101

мерно распределенных чисел. Причем повышение точности имеет как объективную сторону - величина объема выборки может быть больше величины емкости накопительньгх счетчиков, что i повышает состоятельность анализа (1) для ряда законов распределения, так и субъективную - относительные изменения измеряемой вероятности в квантилях становятся более заметными, что ю для экспресс-анализа, часто визуаль83

14

ного, тоже весьма важно, так как более эффективно используется блок памяти и экран отображающего устройства

Предлагаемое устройство используется в качестве компактного встроенного средства экспресс-анализа в генераторе случайных импульсных процессов ПОТОК-3, предназначенного для работы в системе электрических испы-, таний.

аг. 1

Р(

,tZ5

Р--0,5

.f-

Фиг.З