Постоянное ассоциативное запоминающее устройство

 

ПОСТОЯННОЕ АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее дешифратор, матрицу элементов И, распределитель импульсов и индикаторы совпадения хранимой и признаковой информации, причем первые входы элементов И каждого столбца матрицы объединены и подключены к выходам распределителя импульсов, вторые входы и выходы элементов И каждой строки мат . рицы, кроме последнего элемента И, объединены и подключены к выходам дешиф ратора и к первым входам индикаторов совпадения хранимой и признаковой инфорг мации, вторые входы которых объединены и являются одним из управляющих входов устройства, информационными входами которого являются входы дешифратора, отличающееся тем, что, с целью повышения помехоустойчивости и расширения области применения устройства за счет возможности хранения слов переменной длины, в него введены элемент И и группа элементов И, первые входы которых соединены с первыми входами индикаторов совпадения хранимой и признаковой информации, причем вторые входы элементов И группы и последних элементов И каждой строки матрицы объеди (Л нены и подключены к выходам индикаторов совпадения хранимой и признаковой информации, третьи входы которых соединены с выходом элемента И, выходы элементов И группы и первый вход элемента И объединены и являются первым управляющим входом устройства, второй 4± вход .элемента И является другим управСО (О ляющим входом устройства, выходы последних элементов И каждой строки матрицы объединены и являются вторым управ ел ляющим входом устройства.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК айаг «г>

3(59 G 11 С 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3470085/18-24 (22) 08,07.82 (46) 23.10.83. Бюл. No. 39 (72) О. Г. Кокаев, И. А, Магомецов, Т. Э. Темирханов и А. В. Яковлев (71) Ленинграцский орцена Ленина электротехнический институт им. В. И..Ульянова (Ленина) (53) 681.327(088.8)

Ъ (56) 1. Авторское свицетельство СССР

М 402944, кл. Q 11 С 15/00, 1973, 2. Ли С. К., Стародубцев Э. В. Постоянное ассоциативное запоминаюшее усг ройство цля распознавания образов.Известия ВУЗов, "Приборостроение", 1970, Ж 1, с. 80-84 (прототип). (54) (57) ПОСТОЯННОЕ ACCOUHATHBHOE ЗАПОМИНАЮШЕЕ УСТРОЙСТВО, соцержашее дешифратор, матрицу элементов И, распрецелитель импульсов и инци каторы совпацения хранимой и признако вой информации, причем первые входы элементов И кажцого столбца матрицы обьецинены и поцключены к выхоцам распрецелителя импульсов, вторые вхоцы и выхоцы элементов И кажцой строки матрицы, кроме послецнего элемента И, обьецинены и поцключены к выхоцам цешиф» ратора и к первым вхоцам инцикаторов совпацения хранимой и признаковой инфор . мании, вторые вхоцы которых" обьецинены и являются оцним из управляющих вхоцов устройства, информационными вхоцами которого являются вхоцы цешифратора, о тл и ч а ю щ е е с я тем, что, с целью повышения помехоустойчивости и расши рения области применения устройства за счет возможности хранения слов переменной цлины, в него ввецены. элемент И и группа элементов И, первые вхоцы которых соецинены с первыми вхоцами инцикаторов совпацения хранимой и признаковой информации, причем вторые вхоцы элементов И группы и послецних элемен- Е

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

1 1049975,3

35

45

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

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

Нецостатком этого устройства являет . ся ограниченность области применения.

Наиболее близким к изобретению по технической сущности является постоянное ассоциативное запоминающее устройство, содержащее входной пешифратор, распределитель, ассоциативную матрицу и блок детекторов совпацения, причем первые вхоцы элементов матрицы соединены с выходами пешифратора, вторые входы соецинены с BbLxoäeìè распрецелителя, выхоцы элементов матрицы объецинены по схеме ИЛИ и соецинены с первыми вхоцами цетектора совпапения,элементы ассоциативной матрицы препсгавляют собой элементы И 27.

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

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

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

Устройство соцержит дешифратор 1, распрецелитель 2 импульсов, матрицу 3 элементов И, 4, управляющие входы 5 и 6 устройства, инпикаторы 7 совпацения хранимой и признаковой информации, группу элементов И 8 и элемент И 9, первый 10 и второй 11 управляющие выхоцы и информационные вхопы 12 устройства. Распределигель может быть выполнен как сцвиговый регистр с

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

Перед началом работы произвопится установка в "1" всех индикаторов 7 и первого разряца распределителя 2; Анализируемый набор символов посгупае г послецовательно во времени коц за коцом на входы 12 цешифратора l, который произвопит преобразование символов из

1049975

3 параллельного кода в унитарный, т.е, каждому вхоцному символу соответствует оцин из выходов дешифратора 1. Кажждому элементу эталонных наборов симво» лов, запоминаемых в матрице 3, соо 1 ветствует оцин элемент И 4, Одному эталонному набору символов, запоминаемому в устройстве, соответствует оцна строка матрицы 3. Номер выхода распрецелителя 2 совпацает с поряцковым номером элементе в наборе символов.

При поступлении кода символа анализируемого набора возбуждается. соответствуюший выход цешифратора 1. На вы» хоцах элементов И 4, на входы которых одновременно поступают сигналы от Q8 шифратора 1 и распрецелителя 2, появ ляются сигналы, которые поступают на элементы И 8 и на первые входы инцикаторов 7.

На первом такте работы устройства все элементы индикаторов 7 устанавли- ваются в 1" и все элементы И 8 открываются. Если есть хотя бы оцин сиг нал с элементов И 4 матрицы 3, формируется сигнал на выхоце 10, при наличии которого производится установка новых значений инцикаторов 7 по сигналу на входе 6. Если есть сигнал на первом входе инцикатора 7,.он остается в состоянии "1 ", если сигнала нет, этот индикатор 7 сбрасывается в "0". Если ес1ь сигнал на выхоце 10, одновременно с установкой индикаторов 7 производится перевод распределителя 2 в следуюшее сос тоян ие. личию искажения в анализируемом наборе символов. В этом случае запре;дается установка новых значений индикаторов 7, что npeaoTapamaer сброс их всех в 0 ..

Таким образом, в индикаторах 7 фиксируется состояние процесса сравнения наборов символов на момент появления помехи в анализируемом наборе символов.

Все типы помех в наборах символов раэцеляются на три группьп появление некоторого числа дополнительных символов в основном наборе, т.е. "Вставка ложного текста"; исчезновение нескольких символов в основном наборе (" Пропуск основного текста ); искажение нескольких символов .набора (" Замена основного текста ").

Устранение указанных искажений наборов символов может быть произведено при последовательном сравнении анализируемых символов с эталонными наборами с помошью очной из трех процедур коррекции: пропуск в точке сбоя цо пер» вого совпадения такого же числа в анализируемом наборе символов при вставке ложного текста; пропуск, начиная с точки сбоя цо первого совпадения, символов в эталонных наборах, запомненных в матрице 3, при пропуске основного текста; оцновременный Пропуск, начиная с точки сбоя цо первого совпацения, символов в эталонных и анализируемой послецовательностях символов при заме не основного текста. Палее в зависимости от принятой стратегии может быть запушена любая из трех процедур корНа слецуюшем шаге работы на вхоцы 12 поступает очередной символ анализируемой послецовательности и фон мируются сигналы на выходах матри-, цы 3. При этом сигналы на выхоцах элементов И 8 появляются только по тем строкам матрицы 3, соответствуюшие которым инцикаторы 7 остались в состоянии "1".

При наличии сигнала на входе 10 проиэвоцится установка новых значений инцикаторов 7. И так до тех пор, пока не будет сформирован сигнал на выхо -"ае 1l являюшийся признаком оконча-ния сравнения анализируемого и эталонного символов, или пока на очерецном шаге сравнения символов анализируемого набора с эталонным не будет отсутствовать сигнал на выхоце 10. Отсутствие сигнала на выходе 10 соответствует несовпадению анализируемого на бора символов с эталонными, т.у, на40

55 рекции. Если выясняется, что в анализируемой послецовательности символов есть помеха типа "Вставка ложного текста", то без изменения состояния распределителя 2 и индикаторов 7 на входы 12 устройства последовательно подаются анализируемые символы до появления сигнала на выходе 10, который соответствует окончанию помехи "Встав» ка ложного текста" и совпадению анализируемого символа с текушим символом одного из эталонных наборов. Если счи-, тается, что на входах 12 присутствует помеха типа "Пропуск основного теквта то без изменения состояния инцикаторов 7 и анализируемой:. последовательности символов произвоцится сцвиг распрецелителя 2 в послецуюшие состояния цо появления сигналов на выходе 10 или на выхоце 11, Если обнаруживается помеха типа

"Замена основного текста, без измене1049975 ння состояния ийцикаторов 7 производится сдвиг распрецелителя 2 s после« дующие состояния и анализ следующих символов цо появления сигналов на выхо цах 10 или 11. При появлении сигнала на выхоце 10 считается,. что коррекция закончена и сравнение набора символов с axoaos 12 с эталонными наборами символов продолжается по основному алго ритму. Появление сигнала на выхоце 11 соответствует окончанию эталонного на бора символов, с которым произошло совпадение анализируемого набора и, следовательно, окончанию процесса сравнения. Результат сравнения фиксируется в инцикаторе 7.

Предлагаемое устройство позволяет обрабатывать наборы символов, соцержаI щие, по сравнению с эталонными, поме хи (искажения) типа "Вставка ложного текста", "Пропуск основного текста и Замена основного текста, и позволяет опрецелять конец эталонного набора символов, что дает возможность хра нить, а следовательно, и обрабатывать наборы символов разной цлины.

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

l 04 :1 г) 75

1049975 t

Сос,тавитель Т. Зайцева

Рецактор О. Черниченко Техрец Т.Маточка Корректор Т. Вашкович

Заказ 8436/49 Тираж 594 Поцписное

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

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

Филиал ППП "Патент", г. Ужгороц, ул. Проектная, 4