Ячейка памяти ассоциативной запоминающей матрицы

 

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

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

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

РЕСПУБЛИН (51)5 G 11 С 15/00

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

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

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

flO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4448660/24-24 (22) 27.06.88 (46) 28.02.90. Вюл. № 8 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.И. Корнейчук, А.П. Марковский, В.П. Сидоренко и Р.В. Яблуновский (53) 681.327 (088.8) (56) Авторское свидетельство СССР

¹ 978196, кл. С 11 С 15/00, 1981.

Авторское свидетельство СССР № 1275546, кл. G 11 С 15/00, 1985. (54) ЯЧЕЙКА ПАМЯТИ АССОЦИАТИВНОЙ ЗА ПОМИНАЮЩЕЙ И АТ РИЦЫ (57) Изобретение относится к вычисли„.SU„„154 029 А1

2 тельной технике, в частности к устройствам хранения информации, и может быть использовано в цифровых системах обработки информации. Цель изобретения — повышение быстродействия ячейки памяти при поиске чисел по критерию кодового подобия достигается за счет распараллеливания процесса поиска в .группах разрядов строки матрицы путем введения блоков приоритета. Ячейка памяти ассоциативной запоминающей матрицы cogppKHT

m групп из k запоминающих элементов 1, где m uk выбираются от 1 до и (п — количество запоминающих элементов 1 ячейки матрицы), m элементов И 2 и

m блоков 3 приоритета. 2 ил.

1547029

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

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

На фиг.1 изображена функциональная схема предлагаемой ячейки памяти; на фиг.2 — функциональная схема sanoминающего элемента ячейки памяти.

Ячейка памяти содержит m групп из

k запоминающих элементов 1, где m u

k выбирают от 1 до n (n = m k - ко15 личество.запоминающих элементов в ячейке памяти матрицы) в зависимости от требуемого критерия качества, определяемого отношением быстродействия к аппаратурным затратам, m элемен- 0 тов И 2 и m блоков 3 приоритета, причем управляющие входы 4 нсех запоминающих элементов 1 объединены и являются управляющим входом 5 ячейки памяти, установочные входы 6 запоминающих элементов 1 каждой группы сое-, динены с выходами 7 соответствующего блока 3 приоритета, а выходы 8, кроме k-го запоминающего элемента 1 группы, связаны с информационными входами 9 соответствующего блока 3 приоритета.

Выход m-ro элемента И 2 является выходом "Результат поиска" 10.

Входы синхронизации всех блоков

3 приоритета объединены и являются входом 11 синхронизации ячейки памяти (прямые и инверсные входы признака поиска ячейки не показаны). .Запоминающий элемент 1 ячейки па- 40 мяти содержит элемент 12 памяти, первый 13, второй 14 и третий 15 элементы И-НЕ и первый 16 и второй 17 элементы развязки,. выполненные, например в виде Резисторов Первые 45 входы первого 13 и второго 14 элементов И-НЕ явпяются соответственно инверсным 18 и прямым 19 входами признака поиска запоминающего элемента 1, а вторые входы объединены посредством МОНТАЖНОГО И и связаны с выходом третьего элемента И-НЕ 15, с первьм элементом 16 развязки и являются установочным входом 6 запоминающего -элемента 1, первый вход 4 которого подключен к первому входу

55 третьего элемента И-НЕ 15, второй вход которого является выходом 8 sano" минающего элемента 1 и соединен с

Г выходом первого 13 и второго 14 элемента И-НЕ и со вторым элементом

17 развязки посредством МОНТАЖНОГО И, причем первый 16 и второй 17 элементы развязки связаны с источником

20 питания.

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

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

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

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

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

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

В первом случае на управляющий вход 5 каждой из строк матрицы (данные входы отдельных строк матрицы могут быть объединены в общую шину либо могут быть раздельньми, с целью возможности наращивания по разрядам) подается сигнал единичного уровня. При этом, если хранимое в какой-либо строке матрицы информационное слово полностью совпадает незамаскированными разрядамн с признаком поиска, то на выходе 10 соответствующей строки формируется единичный сигнал. Иначе на выходе 10 будет поддерживаться потенциал логического нуля ° поиска всех больших (меньших) границы расстояния Хэммннга; поиска ближайшего большего (меньшего) границы расстояния Хэммннга поиска равного границе расстояния

Хэмминга; поиска в интервале (вне интервала) границ расстояния Хэмминга.

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

5 15470

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

5 строки матрицы, на вход 11 синхронизации строки матрицы выдается серия синхроимпульсов. В каждом такте работы матрицы одним из блоков 3 приоритета строки выделяется первый слева (или справа) нулевой сиг» нал, т.е. сигнал несовпадения содержимого соответствующего элемента

t2 памяти и разряда признака поиска.

При этом на вход 6 данного запоми-. нающего элемента 1 с выхода 7 блока

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

И-НЕ 13-15 триггера "защелки", сброс 25 которого происходит при подаче на вход 4 запоминающего элемента 1 нулевого сигнала, после окончания про-. цесса поиска ° Заметим, что за один такт в каждой строке матрицы происходит переключение (из "несовпадения" в "совпадение") только одного запоминающего элемента 1. Таким образом, первым единичным сигналом с выхода

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

Следует отметить, что применяя предлагаемую матрицу с выходными схе". мами обработки (не показаны) информацииу Возможно с достаточно высокой 45 скоростью проведение не только поиска ближайшего по критерию кодового подобия, но и других видов поиска:

Ячейка памяти ассоциативной запоминающей матрицы, содержащей m групп

k запоминающих элементов (rye mik— разрядность числа, хранимого в ячейке), управляющие входы которых объединены и являются управляющим входом ячейки, прямые и инверсные входы признака поиска запоминающих элементов являются одноименньии входами ячейки, отличающаяся тем, что, с целью повышения быстродействия ассоциативной запоминающей матрицы, в нее введены m блоков приоритета и

m элементов И, причем установочные входы запоминающих элементов каждой группы соединены с выходами соответствующего блока приоритета, выходы запоминающих элементов, кроме k-ro, каждой группы подключены к информационным входам соответствующего блока приоритета, выход х-го элемента И (i = 1, m — 1) соединен с управляющим входом (i+1)-го блока приоритета и первым входом (i+1) го элемента И, выход m-го элемента И является выходом "Результат поиска" ячейки, первый вход первого элемента

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

1547029

N 19 _#_

Ю08.2

Составитель В. Рудаков

Техред М,Ходанич Корректор Т. Палий

Редактор А. Ревин

Тираж 484

Заказ 83

Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101