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

«124

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

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

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

Анализатор содержит предварительное запоминающее устройство (ЗУ) , входы которого являются соответствующими входами анализатора, первый блок 2 преобразования ключа в адрес, выход которого соединен с информационным входом первого регистра 3 адреса, второй блок 4 преобразования ключа в адрес, выход которого соединен с информационным входом второго регистра 5 адреса, вьгА:од которого соединен с вторым входом коммутатора 6, выход которого соединен с адресным входом блока 7 памяти, первые управляющие вход и выход которого соединены соответственно с первыми управляющими выходами и входом бло-- ка 8, управления, вторые управляющие вход и выход которого соединены соответственно с выходом и управляющим входом схемы 9 сравнения, первый информационный вход которой объединен с информационным входом регистра IО и соединен с информационным выходом блока 7 памяти, первый информационный вход которого соединен с первым информационным выходом регистра 10, второй информационный выход которого соединен с входом блока 11 вывода результата, а управляющий вход - с шестым управляющим выходом блока 8 управления, пятый управляющий выход которого соединен с управляющим входом коммутатора 6, первый информационный вход которого соединен с выходом первого регистра 3 адреса, управляющий вход которого объединен с управляющим входом второго регистра 5 адреса и соединен с четвертым уп- равляющ}1М выходом блока 8 управления,.

третий управляющий выход которого со2592

единен с управляющим входом предва- рительного ЗУ 1, выход которого соединен с входами блоков 2 и 4 преобразования ключа в адрес и вторыми входами схемы 9 сравнения и блока 7 памяти .

Второй блок 4 преобразования ключа в адрес (фиг.2) может состоять из группы 12 элементов ИСКЛЮЧАЮЩЕЕ

0 ИЛИ, входы которых соединены с соответствующими разрядами предварительного ЗУ i, а выходы , являются соответствующими выходами блока 4.

Коммутатор 6 (фиг.З) может содер5 жать группу 13 элементов 2И-ИЛИ и элемент НЕ 4, вход которого объединен с первыми входами элементов 2И-ИЛИ и является управляющим входом коммутатора 6, выход элемента НЕ 14

0 соединен с вторыми входами элементов 13 2И--ИЛИ, третьи и четвертые входы которых являются соответствен - но первым и вторым информационным11 входами коммутатора 6, а выходы эле5 ментов 2И--ИЛИ 13 являются выходами коммутатора 6.

Блок 8 управления (фиг.4) может состоять из генератора I5, счетчика 16, дешифратора 17, регистра 18,

-.. элемента 2И-ИЛИ 19 и группы 20 мультиплексоров, выходы которых являются управляющими выходами блока 8, а информационные входы объединены с первыми входами элемента 2И-ИЛИ 19 и соединены с выходами регистра 18,

информационные входы которого объединены между собой и являются вторым управляющим входом блока 8, а входы синхронизации регистра 18 объединены с вторыми входами элемента 2И- ИЛИ 19 и соединены с выходами дешифратора 17, вход которого объединен с адресными входами мультиплексоров 20 и соединен с выходом счетчика 16, информационный вход которого соединен с выходом генератора 15, вход сброса соединен с выходом элемента 19 2И-ИЛИ, а вход синхронизации являетсяпервым управляющим входом блока 8.

5 Работа анализатора основана на следующем способе размещения ключей.

Область памяти, отводимая для хранения данных, разбивается на две непересекающиеся подтаблицы так, 55 чтобы количество адресов в каждой из них Ml и М2 были равны между собой. Формируется адрес А1 для подтаб лицы 1. Если при обращении по этому

5

312

адресу коллизии не возникает, то для текущего ключа достраивается гистограмма. Если коллизия возникает, происходит обращение к подтаблице 2 по адресу А2, вычисляемому независимо от А1. Если и здесь возникает коллизия, выполняется повторное обращение к подтаблице 1, но уже по адресу А2. Наконец, если и здесь происходит коллизия, осуществляется обращение к подтаблице 2 по адресу Л

В результате преобразования ключа в адрес получают равномерное распределение адресов. Тогда (N - число ключей, М - количество ;адресов) вероятность того, что число ключей, адресуемых к данной ячейке, равно К подчиняется биномиальному закону и определяется выражением:

Р(К) . q

N-K

где р 1/М - вероятность попадания любого ключа в а-й адрес (а,2, ..., М);

q I - 1/М - вероятность попадания любого ключа в адрес, отличный от а.

Так как N достаточно велико, а произведение N-p имеет один порядок с количеством ключей, которые могут разместиться по одному адресу, можно воспользоваться пуассоновским приближением для биномиального распределения:

-.

Р/к/ е

К

где и N P.

Отсюда можно вычислить среднее число ключей, приходящихся на один адрес

N

h(m,5 lIn-P(S4-)i) n (

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

/ с (1.21 то g(m,S) 100,

m

где - коэффициент загрузки

ключей;

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

2594

с помощью описанного алгоритма, оп- оределяется, следующим выражением:

(m 1,2) + g(m 2,2) - )

Too

(1)

10

где ml N/Ml;

„2 1192-1-е1ш Ь21) N .

100.M2

15

1

1

й(

. N - m Ш ----- .

0

0

5

Как показывают расчеты по формуQ ле (1) применение описанного алгоритма позволяет разместить все 100% поступающих ключей в памяти (при m 1) без указания адресов связей. Многомерный статистический ана5 лизатор работает следующим образом.

Сигнал, формируемьй на третьем управляющем выходе блока 8 управления разрешает записать.числовой код, поступивший на вход анализатора от внешних источников реализаций, в -. предварительное ЗУ I, разрядность которого зависит от размерности анализируемого процесса. Блоки 2 и 4 преобразования ключа в адрес формируют независимо друг от друга адреса

ячеек блока 7 памяти в задайном диапазоне.

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

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

- Блок 2 преобразования ключа в адрес, реализованный в виде сумматора, выполняет операцию сложения соответствующих разрядов различных групп выходов предварительного ЗУ I и результат запоминается в первом регистре 3 адреса, разрядность которого равна п. Если обшее число разрядов предварительного ЗУ 1 не кратно

5

$12/+I2

, то последняя группа с количеством азрядов меньше n условно дополняетя до n нулями и участвует в операии сложения наравне с остальными руппами разрядов.с

Второй блок 4 преобразования клюа в адрес может быть выполнен в вие группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ,, каждый из которых реализует операцию слажения по модулю 2, При этом ю входы каждого элемента ИСЮБОЧАЮЩЕЕ ИЛИ 12 соединены с выходами соответствующих разрядов различных групп выходов, предварительного ЗУ 1 .

Сигнал на четвертом управляющем 5 выходе блока 8 управления разрешает записать адреса, сформирова1П1ые первым и вторым- блоками 2 и 4 преобразования кдюча в адрес, соответственно в первый и второй регистры 3 о и 5 адреса.

Старшие разряды регистров 3 и 5 могут быть выполнены в виде Т-триг - геров, начальное состояние которых равно соответственно 1 и О. Это 25 сделано для того, чтобы иметь возможность адресоваться поочередно к первой (диапазон изменения адресов от 1 до ) и второй (диапазон изменения адресов от 2 + 1 до ) половинам отведенной для хранения данных области памяти. Таким образом достигается разбиение памяти на две непересекающиеся подтаблицы. Работа при этом происходит следующим образом .

Появление сиг нала на четвертом управляющем входе блока 8 управления (фиг.4) заставляет старшие разряды первого и второго регистров 3 и 5 переключить соответственно в состояние О и 1. Затем с подачей разрешающих сигналов из блока 8 управления адрес из первого регистра 3 адреса через коммутатор 6 поступает на адресные входы блока памяти .

Коммутатор 6 работает следуюпшм образом.

Единичный сигнал па пятом управляющем выходе блока 8 управления разрешает прохождение адреса с первого регистра 3 адреса через первые информационные входы элементов 2И-ИЛИ 13 на выход коммутатора 6. При этом низкий уровень на выходе элемента НЕ 14 запрещает прохождение адреса с второго регистра 5 адреса через вторые информационные вхо

30

35

40

45

50

55

596

ды элементов 2И-Ш 1И 13. Низкий уровень :а пятом управляюишм .выходе блока 8 правления разрешает прохожд-е- ние на выход коммутатора 6 адреса с второго регистра 5 адреса, в то время как выходы первого регистра 3 адреса блокируются.

После установления адреса на адресных входах блока 7 памяти содержимое ячейки с данным адресом извлекается на регистр 10 и на схему 9 сравнения, где происходит сравнение содержимого этой ячейки с нулем. Память при этом может быть организована TaKj чтобы каждая запоминающая ячейка хранила и ключ, и гистограмму (например, для храпения ключа выделяются определенные разряды ячейки). Тогда на схему 9 сравнения поступает группа разрядов, соответствующая ключу, а на регистр 10 - группа разрядов ячейки, соответствующая гистограмме. Если схема 9 сравнения обнаруживает, что данная ячейка свободна, т.е. ее содержимое равно нулю, она вырабатывает сигнал, который поступает на второй управляющий вход блока 8 управления. Блок 8 управления увеличивает содержимое регистра 10, осуществляя тем самым достраивание г истограммы, и разрешает затем запись ключа из -предварительного ЗУ 1 и гистограммы из регистра 10 в блок 7 памяти.по адресу, храня цемуся на первом регистре 3 адреса. Обработка ключа завершена.

Если в результате проверки в схеме 9 сравнения оказалось, что дан- пая ячейка уже.занята, т.е. ее содержимое не равпо нулю (фиг.5), блок В управления вырабатывает сигналы на первом, втором, третьем и пятом управляющих выходах. Содержимое а/фесуемой ячейки (разряды, соответствующие ключу) поступает па первый информационный вход схемы 9 сравнения, на второй информацион- ньш вход которой поступает ключ из предварительного ЗУ 1 и происходит их сравнение. Если проверяемые ключи совпадают, схема 9 сравнения вырабатывает сигнал, который поступает на второй управляюп1ИЙ вход блока 8 управления. Блок 8 управления сигналом на шестом управляющем выходе увеличивает на единицу содержимое регистра 10 (достраивается гистограмма), которое в следующем

V

такте работы запоминается в соответствующей ячейке блока 7 памяти Обработка данного ключа завершена.

Если в результате анапиза адресуемой ячейки оказалось, что она занята ключом, отличным от вновь поступившего, т.е. в шестом такте сигнал на втором управляющем входе блока 8 управления отсутствует (фиг.6), происходит обращение к второй половине адресуемой области памяти (диапазон адр.есов от 2 +1 до ). С этой целью блок 8 управления устанавливает на пятом управляющем выходе низкий уровень, разрешая тем самь1м прохождение на адресные входы блока 7 памяти.через коммутатор адреса 6, хранящегося на втором регистре 5 адреса (старший разряд второго регистра 5 адреса хранит единичный уровень). Происходит обращение к блоку 7 памяти, содержимое адресуемой ячейки извле- 1са1ется на регистр 10 и разряды, со- ответствуюшде ключу, поступают на схему 9 сравнения, где сравниваются с-нулем. Если проверяемая ячейка свободна, схема 9 сравнения вырабатывает на выходе единичный сигнал, блок 8 управления увеличивает содержимое регистра 10 а единицу(достраивается гистограмма), ключ из предварительного ЗУ 1 и гистограмма из регистра 10 переписывается в ячейку памяти. Обработка ключа завершена.

Если анализируемая ячейка занята сравниваются ключи из предваритель - ного ЗУ 1 и .данной ячейки. Е сли ключи совпадают, достраивается гистограмма и обработка заканчивается. Если ключи не совпадают (фиг.7), выполняется обращение к второй половине памяти (адреса от 2 +1 до 2 ) по адресу, хранящемуся на первом регистре 3 адреса. С этой целью блок 8 управления вырабатывает на первом, втором, четвертом, пятом и шестом управляющих выходах единичные сигналы. При этом триггеры в старших разрядах первого и второго регистров 3 и 5 адреса переходят соответственно в состояние 1 и О и разрешается обращение к блоку 7 памяти по Здресу, хранящемуся на первом регистре 3 адреса. После этого повторяется анализ содержимого адресуемой .ячейки аналогично описанному вьше.

412598

Если и данная ячейка оказалась занятой ключом, отличным от вновь поступившего, происходит обращение . к первой половине памяти (адреса 5 от 1 до 2) по адресу, хранящемуся на втором регистре 5 адреса. Для это го -блок 8 управления устанавливает на четвертом управляющем выходе низкий уровень, разрешая прохождение to на адресные входы блока 7 памяти адреса из второго регистра 5 адреса. Затем повторяется анализ содержимого адресуемой ячейки аналогично описанному . -.

)5 Если в результате работы описанного алгоритма оказывается, что вновь поступивший ключ нельзя разместить в основной памяти, необходимо или отбросить данный ключ (как малове- 2Q роятный), и либо выделить небольшого размера дополнительную память, где такого типа ключи размещены последовательно .

По окончании эксперимента блок 8 25 управления может последовательно сформировать в предварительном ЗУ 1 коды возможных ключей, из которых блоки 2 и 4 преобразования ключа в адрес формируют адреса ячеек блока

7памяти, в которых хранятся соответствующие элементы гистограммы. Эта информация извлекается на регистр 10, откуда поступает на блок 11 вывода результата.

Блок 8 управления координирует 35 (работу всех узлов анализатора. Работа самого блока 8 может быть представлена следующим образом.

Генератор 15 формирует тактовые импульсы, которые поступают на счет- О Р1ЫЙ вход счетчика 16. Выходы счетчика

16соединены с входами дешифратора

17и адресными входами мультиплексо- - , ров 20.

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

8определенные моменты времени состояние второго управляющего входа блока 8 управления фиксируется на

.регистре 18 под управлением дешиф- 55 ратора 17, В зависимости от информа- ции, занесенной на регистр 18, группа 20 мультиплексоров формирует на выходе блока 8 управления последовн

ельность управляющих сигналов в оответствии с.временными диаграмами на фиг. . Сброс- счетчика 6 осуществляется по первому управяющему входу блока 8 управления ри заполнении памяти, и элементом И-ИЛИ 9 при завершении обработки онкретного ключа.

В качестве блока 11 вывода реультата может быть использовано юбое стандартное периферийное-обоудование, например, алфавитно- ифровое печатающее устройство, исплей, пишущая машинка, внещнее апоминающее устройство и т.д.

ормула и :з обретения

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

йен с выход

10

15

20

25

30

35

40

45

регис блока котор входо онным низир пятым рой у динен отл с цел и рас в нег блок вход перво в адр второ перво подкл и вто комму с адр блок держи групп из ко с пер управ сора входо входы нены та 2И но к управ котор являю блока блока групп ключе дешиф соеди котор счетч с упр ров г

10

йен с выход

0

5

0

5

0

5

ВХОДОМ синхронизации регистра, которого подключен к входу регистратора и второму входу з агмси блока памяти, информационный выход которого соединен с информационным входом регистра -и вторым информационным входом схемы сравнения, синхронизирующий вход которой соединен с пятым выходом блока управления, второй управляющий вход которого соединен с выходом схемы сравнения, отличающийся тем, что, с целью повыщения быстродействия и расширения класса решаемых задач, в него введены коммутатор и второй блок преобразования ключа в адрес, вход которого объединен с входом первого блока- преобразования ключа в адрес, а выход подключен к входу второго-регистра адреса, выходы первого и второго регистров адреса подключены соответственно к первому и второму информационным входам коммутатора, выход которого соединен с адресным входом блока памяти, а блок управления дополнительно содержит регистр, элемент 2И-ИЛИ и группу мультиплексоров, выходы пяти из которых являются соответственно с первого по пятый выходами блока управления, выход шестого мультиплексора группы соединен с управляющим входом коммутатора, информационные входы мультиплексоров группы объединены с первой группой входов элемента 2И-ИЛИ и подключены соответственно к выходам регистра памяти блока управления, информационные входы которого поразрядно объединены и являются вторым управляющим входом блока управления, а входы регистра блока упра вления объединены с второй группой входов элемента 2И-Ш1И и подключены к соответствующим выходам дешифратора, вы:ход элемента 2И-ИЛИ соединен с входом счетчика, выход которого соединен с входом сброса счетчика,, выход которого соединен : с управляющими входами мультиплексоров группы.

n

1

f

ГГ 1

2n

2n f

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

. 8

W

ГГ5 1

J

Фиг. 5

Фиг. 6

(. S

Редактор Л.Пчелинская

Составитель Э .Сечина Техред ОоГортвай

Заказ 3784Тираж 6/1Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д.4/5

Производственно-попиграфическое предприятие, г.Ужгород, ул. Проектная,4

(Pus. 7

IE

IS

iff

Корректор Л.Патай