Многомерный статистический анализатор Советский патент 1982 года по МПК G06F17/18 

с S ) МНОГОМЕРНЫЙ СТАТИСТИЧЕСКИЙ АНАЛИЗАТОР

Изобретение относится к вычислительной и измерительной технике и мо жет быть использовано при проведении экспериментальных исследований, связанных с многомерным статистическим анализом коррелированных многомерных случайных процессов. Известна схема многомерного ассоциативного анализатора, работа которого основана на том, что вначале проводится предварительный эксперимент, в котором выявляются и записывдются в катйлог наиболее вероятные события, а затем основной эксперимент, когда с помощью ассоциативного запоминающего устройства происходит накопление статистической информаци об отобранных в предварительном эксперименте событиях С 1J. Данный анализатор характеризуется относительно низким быстрбдействием, так как время анализа возрастает за счет проведения предварительного эксперимента. Наиболее близким к предлагаемому по технической сущности является многомерный статистический анализатор, содержащий регистр адреса, запоминающее устройство, устройство управления, регистр 1 арифметического устройства, выходное устройство и предварительное запоминающее устройство, информационные входы которого соединены с выходами источников реализации случайного процесса, а выход с входом регистра адреса, выход которого соединен с адресным входом запоминающего устройства, управляющие вход и выход которого соединены соответственно с выходом и входом устройства управления, а информационные вход и выход - с пероым информационным выходом и информационным входом регистра 1 арифметического устройства, второй информационный выход котг..рого соединен со входом выходного устройства 2 , Недостатками данного анализатора являются неэффективное использов ние памяти и, вследствие этого, сложность и низкое быстродействие при анализе многомерных коррелированных процессов. Неэффективное использование памя ти анализатора обусловлено тем что здесь поступающий информационный код служит адресом ячейки запоминающего устройства, в которой хранится соответствующий данному коду элемент гистограммы. Если же параметры анализируемого случайного процесса связаны между собой корреляционными зависимостями, то количество различных кодов, поступивших в ходе эксперимента на вход анализа тора, будет намного меньше теоретически возможного. Вследствие этого значительная часть ячеек запоминающего устройства останется неиспользуемой . Кроме того, повышение размерности анализа ведет к резкому увеличению объема исходной информации, что делает невозможным применение быстродействующих оперативных запом нающих устройств для хранения статистической информации. Использование запоминающих устройств большой емкости, но с низким временем доступа к данным резко усложняет анали затор и снижает его быстродействие. Цель изобретения - упрощение ана лизатора и повышение быстродействия Поставленная цель достигается те что в многомерный статистический анализатор, содержащий предварительное запоминающее устройство, ин формационные входы которого являются соответствующими входами анализатора, регист адреса, выход которо соединен с адресным входом блока памяти, управляющие вход и выход ко рого подключены соответственно к пе вым управляющим выходу и входу блока управления , первые информационные вход и выход блока памяти соединены соответственно с первыми ин формационными выходом и входом регистра, управляющий вход которого подключен к второму управляющему вы ходу блока управления, второй инфор мационный выход регистра соединен с блоком вывода результата, а третий формационный выход - с первым разрядным входом регистра адреса, введены блок разрешения коллизий и блок преобразования ключа в адрес, выход которого соединен с вторым разрядным входом регистра адреса, а вход блока преобразования ключа в адрес объединен с вторым информационным входом блока памяти, первым информационным входом блока разрешения коллизий и соединен с выходом предварительного запоминающего устройства, управляющий вход которого подКлючен к третьему управляющему выходу блока управления , четвертый управляющий выход которого соединен с управляющим входом регистра адреса,а пятый управляющий выход -с первым управляю щим входом блока разрешения коллизий, управляющий выход которого подключён к второму управляющему входу блока управления, второй информационный вход и первый и второй информационные выходы блока разрешения коллизий соединены соответственно с перЬым информационным выходом блока памяти, с третьим разрядным входом регистра адреса и с вторым информационным входом регистра, Блок разрешения колЛизий может состоять из схемы сравнения и регистра адреса переполнения, первый и второй выходы которого являются первым и вторым информационными выходами блока, третий выход регистра адреса переполнения соединен с первым информационным .входом схемы сравнения, второй и третий входы которой являются соответственно первым и вторым информационными входами блока, выход схемы сравнения является управляющим выходом блока, а управляющий вход схемы сравнения объединен с управляющим входом регистра адреса переполнения и является управляющим входам блока. Блок преобразования ключа в адрес может быть выполнен в виде многовходового сумматора и состоять из цепочки последовательно соединенного запоминающего устройства, сумматора и регистра адреса, при этом вход запоминающего устройства является входом блока, а выход регистра адреса является выходом блока. Блок управления может состоять из цепочки последовательно соединенных генератора, счетчика и дешифратора, управляющие входы которого являются 537 соответственно первым и вторым управляющими входами блока, а выходы дешифратора являются соответственно управляющими выходами блока. На фиг. 1 изображен предлагаемый многомерный статистический анализатор: на фиг.2 - блок-схема, поясняющая принцип работы анализатора; на фиг. 3 пример реализации блока уп- равления; на фиг. 4 - пример возможной реализации блока преобразования ключа в адрес, когда ключ разбивается из три группы разрядов; на фиг. 5-9.- временные диаграммы, поясняющие работу блока управления. Анализатор содержит предварительное запоминающее устройство 1, информационные входы которого являются соответствующими входами анализатора, а выход соединен с входом блока 2 преобразования ключа в адрес и первым информационным входом блока 3 разрешения коллизий, выход блока 2 преобразования ключа в адрес соединен с вторым разрядным входом регистра адреса, выход которого соединен с адресным входом блока 5 памяти, управляющие вход и выход которого подключены соответственно к первым управляющим выходу и входу блока 6 .управления, второй управляющий выход которого подключен к управляющему вхо ду регистра 7, первые информационные выход и вход которого соединены соответственно с первыми информационными входом и выходом блока 5 памяти, а второй и третий информационные выходы - соответственно с блоком 8 вывода результата и первым разрядным входом регистра адреса, управляющий вход которого соединен с четвертым управляющим выходом блока 6 управления, третий управляющий выход которого подклйчен к управляющему входу предварительного запоминающего устройства 1, выход которого соединен с вторым информационным входом блока 5 памяти, первый информационный выход которого соединен о вторым информационным входом блока 3 разрешения колли зий, первый и второй информационные выходы которого соединены соответственно с третьим разрядным входом реги стра А адреса и вторым информационным входом регистра 7, а управляющие вход и выход - соответственно с пятым управляющим выходом и вторым уп равляющим входом блока 6 управления. Блок 3 разрешения коллизий предлагаемого анализатора может содержать регистр 9 адреса переполнения, первый и второй выходы которого являются первым и вторым информационными выходами блока 3, и схему 10 сравнения, первый информационный вход которой соединен с третьим выходом регистра 9 адреса переполнения, а второй и третий входя являются соответственно первым и вторым информационными входами блока 3. выход схемы 10 сравнения является управляющим входом блока 3, а управляющий вход схемы 10 сравнения объединен с управляющим входом регистра 9 адреса переполнения и является управляющим входом блока 3. Блок 2 преобразования ключа в адрес может быть выполнен в виде многовходового сумматора и состоять из цепочки последовательно соединенных запоминающего устройства 1, сумматора 2 и регистра k адреса, при этом вход запоминающего устройства 1 является входом блока, а вь1ход регистра А адреса является выходом блока. Кроме того, блок 6 управления может быть выполнен в виде цепочки последовательно соединенных генератора 11, счетчики 12 и дешифратора 13, управляющие входы которого являются соответственно первым и вторым управляющими входами блока, а выходы дешифратора 13 являются соответственно управляющими выходами блока 6. Принцип работы предлагаемого многомерного статистического анализатора основан на использовании некоторой нелинейной функции,формующей адреса ячеек блока памяти в заданном диапазоне В зависимости от исходного Под ключом понимается числовой код. представляющий собой одну реализацию случайного процесса. Из ключа, поступающего на вход анализатора, с помощью нелинейной функции -формируется адрес ячейки блока памяти, соответствующий данному ключу. Есл эта ячейка свободна, то в нее записывается ключ. Ячейка с адресом . отводится для построения гистограммы ключа, т.е. ее содержание увеличивается на единицу. На этом обработка данного ключа заканчивается. Если ячейка с адресом А - оказывается занятой, выполняется анализ на равенс -во текущего ключа и ключа, ранее записанного в эту ячейку. При их совпадении дост7раивается гистограмма по адресу А обработка текущего значения ключа завершается. При несовпадении - колл зии , когда различные ключи адресу ются к одной и той же ячейке, специальмая схема формирует новое значение а реса А для текущего ключа, после чего повторяется анализ содержимого ячейки с адресом А, Эта процедура повторяется до тех пор, пока не будет найдена ячейка, хранящая данный ключ либо свободная/В среднем, для размеще ния любого ключа требуется 1-2 сра нения. По окончании эксперимента,либ по заполнении памяти осуществляется вывод результатов на внешний носител Многомерный статистический анализ тор работает следующим образом. Сигнал, формируемый на третьем управляющем выходе блока 6 управлени разрешает записать числовой код, пос тупивший на вход, анализатора от внешних источников реализаций, в пре варительное запоминающее устройство разрядность которого зависит от размерности анализируемого процесса (фиг. 5)- Блок 2 преобразования клю ма в адрес путем нелинейного преоб ключа.формирует адрес разования ячейки блика 5 памяти,, в которой дол жен храниться данный ключ. Работа блока 2 преобразования ключа в адрес может проходить следующим образом. Ключ, представляющий собой цифровой двоичный код, поступает в пре варительное запоминающее устройство которое может быть выполнено в виде регистра. Выходы предварительного запоминающего устройства, 1 разбиваются на группы по п разрядов, где п определяется размером основной области памяти равным 2, в которую происходит первоначальная адресация ключей. Сумматор 2 выполняет операцию сложения соответствующих разрядов различных групп выходов предварительного запоминающего устройства 1 и результат запоминается в регистре адреса, разрядность которого равна п. Если общее число разрядов предварительного запоминающего устройства 1 не кратно п, то последняя группа с количеством разрядов меньше п, условно дополняется до п нулями и участвует в операции сложения нарчвне с остальными группами разрядов. Сигнал четвертом 9 управляющем выходе блока 6 управления разрешает запись адреса, сформированного блоком 2 преобразования ключа в адрес, в регистр k адреса по второму разрядному входу. Разрядность регистра k адреса меньше разрядности предварительного запоминающего устройства 1 и соответствует размерам основной области памяти, в которой хранится статистическая информация. Затем блок 6 управления формирует сигналы на первом и пятом управляющих выходах. При этом происходит обращение к-блоку 5 памяти по адресу, хранящемуся на регистре k адреса, и в схеме сравнения ТО блока 3 разрешения коллизий осуществляется анализ содержимого данной ячейки, поступающего на второй информационный вход схемы 10 сравнения. Если ячейка свободна, то схема 10 сравнения формирует на выходе сигнал, поступающий на второй управляющий вход блока 6 управления , который в свою очередь формирует сигналы на первом и третьем управляющем выходах, разрешая тем самым перепись текущего ключа в данную ячейку блока 5 памяти по второму информационному входу. В следующем такте работы сигнал на четвертом управляющем выходе блока 6 управления увеличивает на единицу содержимое регистра k адреса. Затем содержимое ячейки, имеющей вновь сформированный адрес, с подачей разрешающих, сигналов по первому и второму управляющим выходам блока 6 управления переписывается в регистр 7, в следующем такте увеличивается на единицу и затем вновь запоминается в блоке 5 памяти по тому же адресу. Таким образом, осуществляется , построение гистограммы для данного ключа. Обработка на этом закончена и анализатор готов к приему следующего ключа. Если в результате анализа в блоке 3 азрешения коллизий оказывается, что чейка занята, т.е. на четвертом таке сигнал на втором упра.вляющем входе лока 6 управления отсутствует (фиг.6), о в следующем такте блок 6 управления ормирует сигналы на первом, третьем пятом управляющих выходах. При этом ключ, хранящийся в данной ячейке, потупает на второй информационный вход хемы 10 сравнения, на первый инфорационный вход которой с выходе предварительного запоминающего устройства 1 поступает текущий ключ. При совпадении этих ключей схема 10 сравне ния на выходе формирует сигнал, посту пающий на второй управляющий вход бло ка 6 управления. Начиная с седьмого такта, обработка аналогична описанному выше случаю: содержимое регист ра 4 адреса увеличивается на единицу и т.д. Если последняя проверка выявляет неравенство ключей, т.е. сигнал на втором управляющем входе блока 6 управления в шестом такте от сутствует (фиг. 7) , то адрес ячейки блока 5 памяти, отводимой для хра нения текущего ключа, формируется блоком 3 разрешения коллизий. Это может быть реализовано следующим образом. Каждый элемент гистограммы содержит три ячейки: первая хранит ключ вторая- соответственно гистограмму данного ключа, третья - адрес ячей ки, к которой следует обратиться дл размещения текущего ключа при воз- никновении коллизии. В этом случае работа происходит следующим образом. 1 -. Блок 6 управления формирует подряд два сигнала на четвертом управляющем выходе, которые увеличивают на два содержимое регистра адреса. Затем, при наличии сигналов на первом и втором управляющих выходах блока 6 управ ления, на регистр 7 по первому информационному входу переписывается содержимое ячейки с вновь сформированным адресом, которое в свою очередь является адресом, .к которому следует обратиться для размещения текущего ключа при коллизии. В следующем такте этот адрес анализируется в схеме 10 сравнения. Если он отличен от нуля, это значит, что ранее в данной ячейке возникала коллизия. В этом слу чае схема 10 сравнения в одиннадцатом такте формирует сигнал на втором управляющем входе блока 6 управления, по которому он затем выставляет сигналы на втором и четвертом управляющих выходах, что вызывает пере пись содержимого регистра 7 в регистр k адреса.Затем блок 6 управления разрешает схеме 10 сравнения сравнить между собой текущий ключ, поступающий на первый информационный вход, и ключ хранимый в ячейке с вновь сформирова ным адресом, поступающим из блока 5 памяти на второй информационный вход Дальнейшая работа аналогично описанной выше, начиная с шестого такта. Если адрес, извлеченный на десятом шаге, оказывается равным нулю, т.е. сигнал на втором управляющем входе блока 6 управления отсутствует в одиннадцатом такте (фиг. 8), это значит, что ранее коллизий в данной ячейке не возникло и размещение текущего ключа в памяти анализатора возлагается на блок 3 разрешения коллизий. Это может происходить следующим образом, Ключ адресуется к дополнительной области памяти, начинающейся с некоторого заранее определенного адреса. Размеры этой дополнительной области составляют от основной области памяти. Блок 6 управления формирует сигналы на втором и пятом управляющем выходах, что вызывает перепись адреса первой свободной ячейки дополнительной области памяти, хранящегося в регистре 9 адреса переполнения, в регистр 7. Затем этот адрес по сигналам на первом и втором управляющих выходах блока 6 управления запоминается в ячейке блока 5 памяти, адрес которой в данный момент хранится в регистре адреса. Таким образом, организуется связь между ключами, которые были адресованы в одну и ту же ячейку. В следующем такте содержимое регистра 9 адреса переполнения по третьему разрядному входу поступает в регистр 4 адреса и по этому новому адресу в блок 5 памяти записывается ключ из предвари тельного запоминающего устройст-. ва 1 . Затем адрес в регистре t адреса сигналом на четвертом выходе блока 6 управления увеличивается на единицу. После этого достраивается гистограммы, для чего содержимое ячейки с вновь сформированным адресом извлекается на регистр 7 сигналом на втором управляющем выходе блока 6 управления увеличивается на единицу и затем вновь запоминается в блоке 5 памяти по тому же адресу. На следующем шаге для обеспечения эффективного размещения вновл поступающих ключей необходимо сформировать адрес первой свободной ячейки в дополнительной области памяти, где мог быть размещен вновь поступри возникновении коллизии.С этой целью содержимое реги стра 9 адреса переполнения сигналами на втором управляющем выходе блока 6 управления увеличивается на три. При выходе за пределы разрядной сетки регистра 9 адреса переполнения на вто|эом управляющем входе блока 6 управления формируется.-.сигн который говорит о том, что дополнительная область памяти полностью за нята и никакие новые , т.е. ранее не встречавшиеся, ключи размещать ся больше не могут. При этом можно либо прекратить эксперимент, либо продолжить накопление статистическо информации об уже поступивших ключах. По окончании эксперимента для вы вода результатов оператору блок 6 у равления последовательно формирует в предварительном запоминающем устройстве 1 коды всех возможных ключей (фиг. 9) . Из них блок 2 преобразования ключа в адрес формиру ет адреса ячеек блока 5 памяти, в которых хранятся соответствующие элементы гистограммы. Эта информация извлекается на регистр 7, откуда поступает на блок 8 вывода резул тата. Таким образом, эффективное исполь зование памяти позволяет упростить И повысить быстродействие анализатора . Формула изобретения 1.Многомерный статистический анализатор, содержащий предварительное запоминающее устройство, информацион ные входы кдторого являются соответствующими входами анализатора, регистр адреса, выход которого соединен с адресным входом блока памяти, управляющие вход и выход которого подключены соответственно к первым управляющим выходу и входу блока уп равления, первые информационные вход и выход блока памяти соединены соответственно с первыми информационными выходом и входом регистра, управляющий вход которого подключен к второму управляющему выходу блока управления, второй информационный выход регистра соединен с блоком вывода результат, а третий информационный выход - с первым разрядным входом регистра адреса, отличающийся тем, что, с целью упрощения анализатора и повышения быстродействия, в него введены блок разрешения коллизий и блок преобра,/ зования ключа в адрес, выход которого соединен с вторым разрядным входом регистра адреса, а вход блока преобразования ключа в адрес объединен с вторым информационным входом блока памяти, первым информаЦ1«знным входом блока разрешения коллизий и соединен с выходом предварительного запоминающего устройства, управляющий вход которого подключен к третьему управляющему выходу блока управления, четвертый управляющий выход которого соединен с управляющим входом регистра адреса, а пятый управляющий выход - с первым управляющим входом блока разрешения коллизий, управляющий выход которого подк/точен к второму управляющему входу блока управления, вто|эой информационный вход и первый и второй информационные выходы блока разрешения коллизий соединены соответственно с.первьи информационным выходом блока памяти, с третьим разрядным входом регистра адреса и с вторым информационным входом регистра.. 2.Анализатор по п. 1, о т л и чающийся тем, что, блок разрешения коллизий состоит из схемы .сравнения и регистра адреса переполнения, первый и второй выходы которого являются первым и вторым информационными выходами блока, третий выход регистра адреса переполнения соединен с первым информационным входом схемы сравнения, второй и третий входы которой являются соответственно первым и вторым информационными входами блока, выход схемы сравнения является управляющим выходом блока, а управляющий вход схемы сравнения объединен с управляющим входом регистра адреса переполнения и является управляадим входом блока. 3.Анализатор по п. 1, о т л и ч а ю .щ :й и с я тем, что блок преобразования ключа в адрес выполнен в виде многовходового сумjMaTopa и состоит из цепочки последовательно соединенных запоминающего устройства, сумматора и регистра адреса, при этом вход запоминающего устройства является входом блока, а выход регистра адреса является выходом блока. k. Анализатор по п. 1, о т л и «дающийся тем, что блок управления состоит из цепочки последовательно соединенных генератора, счетчика и дешифратора, управляющие входы которого являются соответственно.

И

Ю

Фи2./ 9 первым и вторым управляющими входами блока, а выходы дешифратора являются соответственно управляющими выходами блока. Источники информации, принятые во внимание при экспертизе 1.Курочкин С. С. Многомерные статистические анализаторы. М., Атомиздат, 1968, с. ЗП. 2.Там же. с. 11 (прототип).

Фиг. 2

Г Конец J

I тCt3u.S

2n

ФигЛ

1 8 9 10 f 2

физ. б

tN4

Ǥ

ОТ) еч

О CV4

I

I