Многомерный статистический анализатор

 

О П И С А Н И Е ()976449

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистические

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 19. 08. 80(21) 2993145/18-24. с присоединением заявки М (23) Приоритет

Опубликовано 23.11.82. Бюллетень М 43

Дата опубликования описания 23.11.82 (5l)N. Кд.

G 06 F 15/36

Гооудерстеенный комитет

СССР но делам изобретений н открытий (53) УДК 681.3 (088.8) H П. Вашкевич, H. Н. Коннов, А. В. Ку -ин и И;,"В;",111т.а1в1пзв

- "-1;!(Hg y

t

/ (72.) Авторы изобретения

Пензенский политехнический институт (71) Заявитель (54 ) ИНОГОМЕРНЫЙ СТАТИСТИЧЕСКИЙ АНАЛИЗАТОР

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

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

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

Наиболее близким к предлагаемому по технической сущности является многомерный статистический анализатор, содержащий регистр адреса, запоминающее устройство, устройство управления, регистр 1 арифметического устройства, выходное устройство и предварительное запоминающее устройство, информационные входы которого соединены с выходами источников реализации случайного процесса, а выход - с входом регистра адреса, выход которого соединен с адресным входом запоминающего устройства, управляющие вход и выход которого соединены соответственно с выходом и входом устройства управления, а информационные вход и выход - с первым информационным выходом и информационным входом регистра 1 арифметического устройства, второй информационный выход ко976449 т;:рого соединен со входом выходного устройства (2).

Недостатками да нного а нализа тора являются неэффективное использование памяти и, вследствие этого, 5 сложность и низкое быстродействие при анализе многомерных коррелированных процессов, Неэффективное использование памяти анализатора обусловлено тем; что 16 здесь поступающий информационный код служит адресом ячейки запоминающего устройства, в которой хранится соответствующий данному коду элемент гистограммы. Если же 1$ параметры анализируемого случайного процесса связаны между собой корреляционными зависимостями, то количество различных кодов, поступивших в ходе эксперимента на вход анализа- щ тора, будет намного меньше теоретически возможного. 8следствие этого значительная часть ячеек запоминающего устройства останется неиспользуемой. 25

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

Цель изобретения - упрощение анализатора и повышение быстродействия

Поставленная цель достигается тем, ф) что в многомерный статистический анализатор, содержащий предварительное запоминающее устройство, информационные входы которого являются соответствующими входами анализатора, регист адреса, выход которого соединен с адресным входом блока памяти, управляющие вход и выход которого подключены соответственно к первым управляющим выходу и входу блока управления, первые информационные вход и выход блока памяти соединены соответственно с первыми ин-. формационными выходом и входом регистра, управляющий вход которого подключен к второму управляющему выходу блока управления, второй информационный выход регистра соединен с блоком вывода результата, а третий информационный выход - с первым разрядным входом регистра адреса, введены блок разрешения коллизий и блок преобразования "ключа" в адрес, выход которого соединен с вторым разрядным входом регистра адреса, а вход блока преобразования "ключа" в адрес объединен с вторым информационным входом блока памяти, первым информационным входом блока разрешения коллизий и соединен с выходом предварительного запоминающего устройства, управляющий вход которого подключен к третьему управляющему выходу блока управления, четвертый управляющий выход которого соединен с управляющим входом регистра адреса,а пятый управляющий выход -с первым управляю— щим входом блока разрешения коллизий, управляющий выход которого подключен к второму управляющему входу блока управления, второй информационный вход и первый и второй информационные выходы блока разрешения коллизий соединены соответственно с пер вым информационным выходом блока памяти, с третьим разрядным входом регистра адреса и с вторым информационным входом регистра, Блок разрешения коллизий может состоять из схемы сравнения и регистра адреса переполнения, первый и второй выходы которого являются первым и вторым информационными выходами блока, третий выход регистра адреса riepenoxt esws coeqaeee с первым информационным входом схемы сравнения, второй и третий входы которой являются соответственно первым и вторым информационными входами блока, выход схемы сравнения является управляющим выходом блока, а управляющий вход схемы сравнения объединен с управляющим входом регистра адреса переполнения и является управляющим вхо- дам блока.

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

49 6

Блок 3 разрешения коллизий предлагаемого анализатора может содержать регистр 9 адреса переполнения, первый и второй выходы которого являются первым и вторым информационными выходами блока 3, и схему 10 сравнения, первый информационный вход которой соединен с третьим выходом регистра 9 адреса переполнения, а второй и третий входя являются соответственно первым и вторым информационными входами блока выход схемы 10 сравнения является управляющим входом блока 3, а управляющий вход схемы 10 сравнения объединен с управляющим входом регистра

9 адреса переполнения и является управляющим входом блока 3.

Блок 2 преобразования "ключа" в адрес может быть выполнен в виде многовходового сумматора и состоять из цепочки последователь -о соединенных запоминающего устройства 1, сумматора 2 и регистра 4 адреса, при этом вход запоминающего устройства 1 является входом блока, а выход регистра 4 адреса является выходом блока.

Кроме того, блок 6 управления может быть выполнен в виде цепочки последовательно соединенных генератора

11, счетчики 12 и дешифратора 13, управляющие входы которого являются соответственно первым и вторым управляющими входами блока, а выходы дешифратора 13 являются соответственно управляющими выходами блока 6.

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

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

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

Ячейка с адресом А„+„отводится для построения гистограммы "ключа", т.е. ее содержание увеличивается на единицу. На этом обработка данного "ключа" заканчивается, Если ячейка с адресом А „. оказывается занятой, выполняется анализ на равенс во текущего

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

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

"ключа" в адрес, когда "ключ" разбивается на три группы разрядов; на фиг. 5-9 — временные диаграммы, поясняющие работу блока управления. 15

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

3 разрешения коллизий, выход блока

2 преобразования "ключа в адрес соединен с вторым разрядным входом 25 регистра 4 адреса, выход которого соединен с адресным входом блока 5 памяти, управляющие вход и выход которого подключены соответственно к первым управляющим выходу и входу блока 6 .управления, второй управляющий выход которого подключен к управляющему вхо ду регистра 7, первые информационные выход и вход которого соединены соответственно с первыми информационными входом и выходом блока 5 памяти, а второй и третий информационные выходы — соответственно с блоком 8 вывода результата и первым разрядным входом регистра 4 адреса, управляющий вход которого соединен с четвертым управляющим выходом блока 6 управления, третий управляющий выход которого подключен к управляющему входу предварительного запоминающего устройства 1, выход которого соединен с вторым информационным входом блока

5 памяти, первый информационный выход которого соединен а вторым информационным входом блока 3 разрешения колли50 зий, первый и второй информационные выходы которого соединены соответственно с третьим разрядным входом регистра 4 адреса и вторым информационным входом регистра 7, а управляющие

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

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

Затем блок 6 управления формирует сигналы на первом и пятом управляющих выходах. При этом происходит обращение к блоку 5 памяти по адресу, хранящемуся на регистре 4 адреса, и в схеме сравнения !О блока 3 разрешения коллизий осуществляется анализ содержимого данной ячейки, поступающего на второй информационный вход схемы 10 сравнения. Если ячейка свободна, то схема 1О сравнения формирует на выходе сигнал, поступающий на второй управляющий вход блока 6 управления, который в свою очередь формирует сигналы на первом и третьем управляющем выходах, разрешая тем самым перепись текущего

"ключа" в данную ячейку блока 5 памяти по второму информационному входу. В следующем такте работы сигнал на четвертом управляющем выходе блока 6 управления увеличивает на единицу содержимое регистра 4 адреса. Затем содержимое ячейки, имеющей вновь сформированный адрес, с подачей разрешающих. сигналов по первому и второму управляющим выходам блока 6 управления переписывается в

;регистр 7, в следующем такте увели;чивается на единицу и затем вновь запоминается в блоке 5 памяти по тому же адресу. Таким образом, осуществляется . построение гистограммы для данного "ключа". Обработка на этом закончена и анализатор готов к приему следующего "ключа".

Если в результате анализа в блоке 3 разрешения коллизий оказывается, что ячейка занята, т.е. на четвертом такте сигнал на втором управляющем входе блока 6 управления отсутствует (фиг.6), то в следующем такте блок 6 управления формирует сигналы на первом, третьем и пятом управляющих выходах. При этом

"ключ", хранящийся в данной ячейке, поступает на второй информационный вход схемы 10 сравнения, на первый информационный вход которой с выхфдв пред7 976449 8 раивается гистограмма по адресу А„+„ и обработка текущего значения "ключа" завершается, При несовпадении - коллизии, когда различные "ключи" адресуются к одной и той же ячейке, специальная схема формирует новое значение адреса A„. для текущего "ключа", после чего повторяется анализ содержимого ячейки с адресом А„ „. Зта процедура повторяется до тех пор, пока не будет 10 найдена ячейка, хранящая данный "ключ" . либо свободная. В среднем, для размеще.ния любого "ключа" требуется 1-2 сравнения. По окончании эксперимента, либо по заполнении памяти осуществляется 1 вывод результатов на внешний носитель.

Многомерный статистический анализа. тор работает следующим образом.

Сигнал, формируемый на третьем управляющем выходе блока 6 управления,20 разрешает записать числовой код, поступивший на вход, анализатора от внешних источников реализа.ций, в предварительное запоминающее устройство 1, разрядность которого зависит от размерности анализируемого процесса (фиг. 5). Блок 2 преобразования "ключа" в адрес путем нелинейного преобразования "ключа" формирует адрес ячейки блОка 5 памяти,, в которой дол- 30 жен храниться данный "ключ".

Работа блока 2 преобразования

"ключа" в адрес может проходить следующим образом.

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

40 запоминающего устройства, 1 разбиваются на группы по и разрядов,,где n . определяется размером основной области памяти; равным 2, в которую и происходит первоначаль на я адреса4S ция "ключей", Сумматор 2 выполняет операцию сложения соответствующих разрядов различных групп выходов предварительного запоминающего устройства 1 и результат запоминается в регистре 4 адреса, разрядность которого равна и. Если общее число разрядов предварительного запоминающего устройства 1 не кратно и, то последняя группа с количеством разрядов меньше и, условно дополняется

SS до и нулями и участвует в операции сложения наравне с остальными группами разрядов, Сигнал на четгертом

976449 10 варительного запоминающего устройства

1 поступает текущий "ключ". При совпадении этих "ключей" схема 10 сравнения на выходе формирует сигнал, поступающий на второй управляющий вход бло-5 ка 6 управления. Начиная с седьмого такта, обработка аналогична описанному выше случаю: содержимое регист-. ра 4 адреса увеличивается на единицу и т.д. Если последняя проверка вы- 1О являет неравенство "ключей", т.е. сигнал на втором управляющем входе блока 6 управления в шестом такте отсутствует (фиг. 7), то адрес ячейки блока 5 памяти, отводимой для хра- 15 нения текущего "ключа", формируется блоком 3 разрешения коллизий. Это может быть реализовано следующим образ ом, Каждый элемент гистограммы содер- 20 жит три ячейки: первая хранит "ключ", вторая- соответственно гистограмму данного "ключа", третья — адрес ячейки, к которой следует обратиться для размещения текущего "ключа" при воз в 25 никновении коллизии. В этом случае работа происходит следующим образом. ! . а .

Блок 6 управления формирует подряд два сигнала на четвертом управляющем выходе, которые увеличивают на два содержимое регистра 4 адреса. Затем, при наличии сигналов на первом и втором управляющих выходах блока 6 управления, на регистр 7 по первому информационному входу переписывается со35 держимое ячейки с вновь сформированным адресом, которое в свою очередь является адресом, .к которому следует обратиться для размещения текуще40 го "ключа" при коллизии. B следующем такте этот адрес анализируется в схеме 10 сравнения. Если он отличен от нуля, это значит, что ранее в данной . ячейке возникала коллизия. B этом случае схема 10 сравнения в одиннадца45 том такте формирует сигнал на втором управляющем входе блока 6 управления, по которому он затем выставляет сигналы на втором и четвертом управляющих выходах, что вызывает пере- 5

50 пись содержимого регистра 7 в регистр

4 адреса.Затем блок 6 управления разрешает схеме 10 сравнения сравнить между собой текущий "ключ", поступающий на

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

Дальнейшая работа аналогично описанной выше, начиная с шестого такта.

Если адрес, извлеченный на десятом шаге, оказывается равным нулю, т.е, сигнал на втором управляющем входе блока 6 управления отсутствует в одиннадцатом такте (фиг. 8), это значит, что ранее коллизий в данной ячейке не возникло и размещение текущего "ключа" в памяти анализатора возлагается на блок 3 разрешения коллизий. Это может происходить следующим образом.

"Ключ" адресуется к дополнительной области памяти, начинающейся с некоторого заранее определенного адреса. Размеры этой дополнительной области составляют 3-74 от основчой области памяти. Блок 6 управления формирует сигналы на втором и пятом управляющем выходах, что вызывает перепись адреса первой свободной ячейки дополнительной области памяти, хранящегося в регистре 9 адреса переполнения, в регистр 7, Затем этот адрес по сигналам на первом и втором управляющих выходах блока 6 управления запоминается в ячейке блока

5 памяти, адрес которой в данный момент хранится в регистре 4 адреса. Таким образом, организуется связь между "ключами", которые были адресованы в одну и ту же ячейку. В следующем такте содержимое регистра 9 адреса переполнения по третьему разрядному входу поступает в регистр 4 адреса и по этому новому адресу в блок 5 памяти записывается "ключ" из предвари тельного запоминающего устройст-. ва 1. Затем адрес в регистре 4 адреса сигналом на четвертом выходе блока 6 управления увеличивается на единицу. После этого достраивается гистограммы, для чего содержимое ячейки с вновь сформированным адресом извлекается на регистр 7, сигналом на втс эом управляющем выходе блока 6 управления увеличивается на единицу и затем вновь запоминается в блоке 5 памяти по тому же адресу. На следующем шаге для обеспечения эффективного размещения вновь поступающих "ключейн необходимо сформировать адрес первой свободной ячейки в дополнительной области памяти, где мог быть размещен вновь поступивший "ключ при возникновении кол11 97 лизии.С этой целью содержимое регистра 9 адреса переполнения сигналами на втором управляющем выходе блока б управления увеличивается на три.

При выходе эа пределы разрядной сетки регистра 9 адреса переполнения на втором управляющем входе блока 6 управления формируется ..сигнал который говорит о том, что дополнительная область памяти полностью занята и никакие "новые", т.е. ранее не встречавшиеся, "ключи" размещаться больше не могут . При этом можно либо прекратить эксперимент, либо продолжить накопление статистической информации об уже поступивших "ключах", По окончании эксперимента для вывода результатов оператору блок 6 уп- 20 равления последовательно формирует в предварительном запоминающем устройстве 1 коды всех возможных "ключей" (фиг. 9) . Из них блок 2 преобразования "ключа" в,адрес формиру- И ет адреса ячеек блока 5 памяти., в которых хранятся соответствующие элементы гистограммы. Эта информация извлекается на регистр 7, откуда поступает на блок 8 вывода резуль.- 30 тата.

6449 12

10

Таким образом, эффективное исполь эование памяти позволяет упростить и повысить быстродействие анализатора. формула изобретения

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

43

S0

И мационный выход - с первым разрядным входом регистра адреса, о т л ич а ю щ и и с, я тем, что, с целью упрощения анализатора и повышения быстродействия, в него введены блок разрешения коллизий и блок преобра . эования "ключа" в адрес, выход которого соединен с вторым разрядным входом регистра адреса, а вход блока преобразования "ключа" в адрес объединен с вторым информационным входом блока памяти, первым информационным входом блока разрешения коллизий и соединен с выходом предварительного запоминающего устройства, управляющий вход которого подключен к третьему управляющему выходу блока управления, четвертый управляющий выход которогд соединен с управляющим входом регистра адреса, а пятый управляющий выход - с первым управляющим входом блока разрешения коллизий; управляющий выход которого подключен к второму управляющему входу блока управления, второй информационный вход и первый и второй информационные выходы блока разрешения коллизий соединены соответственно с.ïåðâûì информационным выходом блока памяти, с третьим разрядным входом регистра адреса и с вторым информационным входом регистра.

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

3. Анализатор по и. 1, о т л ич а:ю щ .и и с я тем, что блок преобразования "ключа" в адрес выполнен в виде многовходового сум.матора и состоит из цепочки последовательно соединенных эапоминающе13 976449 14 го устройства, сумматора и регист- первым и вторым управляющими входами ра адреса, при этом вход запоминаю", блока, а. выходы дешифратора являютщего устройства является входом ся соответственно управляющими выблока, а выход регистра адреса явля- ходами блока. ется выходом блока.

4. Анализатор по n, l, о т л и Источники информации, ч а ю шийся тем, что блок управ- принятые во внимание при экспертизе, ления состоит из цепочки последова- 1. Курочкин С. С. Многомерные стательно соединенных генератора, счет- тистические анализаторы, М., Атомчика и дешифратора, управляющие вхо- lo издат 1968, с. 311. ды которого являются соответственно, 2. Там же. с. 11 (прототип).

Фиг./

976449

М»

И к ф о ъ 3 щ» "» »:» 0 % сц

Составитель Э, Сечина

Техред И.Гергель КорректорГ. Решетник

Редактор Т. Кугрышева филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Заказ 9005/76 Тираж 731 Подписное

8НИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Иосква, Ж-35, Раушская наб., д. 4/5