Содержание к диссертации
Введение
1 Ассоциативные среды для реализации операций клеточной логики 12
1.1 Предпосылки выбора логики клеточных автоматов как метода обработки информации в ассоциативных средах 13
1.2 Основные понятия и определения 16
1.3 Разработка ассоциативных сред для реализации операций клеточной логики 18
1.3.1 Ассоциативная среда 18
1.3.2 Состав микроопераций ассоциативной среды 23
1.3.3 Сравнение быстродействия ассоциативных сред и
ОКЗУ 26
1.4 Разработка и реализация конвейерного принципа обработки данных в ассоциативных средах 28
1.4.1 Ассоциативная среда для реализации конвейерной обработки данных 28
1.4.2 Метод обработки информации в ассоциативных средах с конвейерной организацией 31
1.4.3 Сравнительные характеристики ОКЗУ, АС с локальными связями и АС с конвейерной организацией. 32
1.5 Выводы 35
2 Ассоциативные среды с командным управлением 37
2.1 Разработка ассоциативной среды с командным управлением 37
2.1.1 Универсальные микрооперации, реализуемые средой 40
2.1.2 Режимы работы накопителя ассоциативной среды . 44
2.2 Разработка ассоциативной среды с командным управлением для обработки изображений 48
2.2.1 Структура ассоциативной среды для обработки изображений 49
2.2.2 Структура и режимы работы накопителя Р[0] . 51
2.2.3 Структура и режимы работы накопителя Р[1] . 58
2.3 Выводы 61
Разработка набора операций для обработки изображений в ассоциативной среде с командным управлением 62
3.1 Определение набора операций для обработки изображений. 63
3.2 Разработка и реализация набора микроопераций 66
3.2.1 Операция адресной записи 77
3.2.2 Операция адресного чтения 79
3.2.3 Операции ассоциативного сравнения 81
3.2.4 Операции фильтрации шума и заполнения пустот . 83
3.2.5 Операция выделения связного объекта 85
3.3 Примеры алгоритмов обработки информации с использо
ванием ассоциативных сред с командным управлением 90
3.3.1 Дискретное преобразование Фурье 90
3.3.2 Вычисление коэффициентов преобразования Уолша. 103
3.4 Выводы 112
Ассоциативные осцилляторные среды 113
4.1 Неоднородные клеточные автоматы 113
4.2 Основные понятия и определения 114
4.3 Клеточные ансамбли 117
4.3.1 Клеточный ансамбль «Проводник» 118
4.3.2 Клеточный ансамбль «Узел» 119
4.3.3 Клеточный ансамбль «Сумматор» 120
4.3.4 Клеточный ансамбль «Умножитель» 121
4.3.5 Клеточный ансамбль «Инвертор» 122
4.3.6 Клеточный ансамбль «Блок» 123
4.3.7 Клеточный ансамбль «Дифференциальный блок» . 124
4.3.8 Клеточный ансамбль «Замкнутый осциллятор» . 125
4.3.9 Клеточный ансамбль «Накапливающий осциллятор» 127
4.3.10 Клеточный ансамбль «Вычитающий осциллятор» . 131
4.3.11 Клеточный ансамбль «Дифференциальный осциллятор» 133
4.3.12 Клеточный ансамбль «Дифференциал» 146
4.4 Применение метода осцилляторов 149
4.4.1 Реализация преобразования Уолша в ассоциативных средах с фиксацией кода микрооперации . 149
4.4.2 Нечеткий ассоциативный поиск 153
4.5 Разработка ассоциативной среды с фиксацией кода микроопераций . 160
4.6 Выводы 163
Заключение 165
Литература
- Разработка ассоциативных сред для реализации операций клеточной логики
- Режимы работы накопителя ассоциативной среды
- Разработка и реализация набора микроопераций
- Основные понятия и определения
Введение к работе
Актуальность темы. Развитие вычислительной техники в наше время ведется, в основном, экстенсивными методами: увеличивается частота работы процессора, объем оперативной памяти, размер кэш-памяти, скорость обмена и число процессоров в многопроцессорных системах.
Одним из «узких мест» при повышении производительности ЭВМ классической архитектуры является обмен данными между процессором и оперативной памятью. Тактовая частота работы процессора в несколько раз превосходит частоту работы памяти, и этот разрыв постоянно растет.
Существует несколько путей сокращения разрыва, например, применение кэш-памяти, работающей на частоте процессора, однако, остается неизменным классический принцип обработки информации, заключающийся в последовательном чтении данных из памяти, обработке в центральном процессоре и помещении в память результатов обработки.
Вместе с тем, становится все более очевидным, что возможности современной элементной базы, аппаратных средств и ЭВМ классической архитектуры по производительности и быстродействию приближаются к физическим пределам, выход за которые возможен только при реализации новых идей, как в архитектуре ЭВМ, так и в области аппаратных и программных средств.
Искусственный интеллект, как наука, развивается уже более 30-ти лет, однако качественный скачок в исследованиях произошел в 80-е годы, когда сформировалась новая отрасль индустрии — производство интеллектуальных систем. Имеется обширный класс задач, эффективное решение которых возможно только при использовании интеллектуальных систем. К ним, в первую очередь, относятся: обработка символьной
информации, решение логических задач, в том числе нечеткого логического вывода; работа с базами данных и знаний; распознавание и синтез речи; анализ, обработка и распознавание изображений.
Отличительной особенностью задач искусственного интеллекта является огромный объем данных для обработки. Время обработки этих данных растет с ростом их объема, и зависит от числа обращений к памяти, поэтому одним из важнейших вопросов при разработке интеллектуальных систем является способ доступа к данным и возможность обработки информации без изъятия ее из памяти.
Существуют два основных способа доступа к информации в запоминающих устройствах (ЗУ) ЭВМ: адресный и ассоциативный. При адресном способе искомая информация жестко задана адресом - местом ее расположения в запоминающей среде, и в каждый момент времени возможно обращение только к одной ячейке ЗУ, независимо от информационной емкости ЗУ. Ассоциативный способ основан на установлении некоторого соответствия, ассоциации между хранимой в ЗУ информации и поисковыми аргументами. Запоминающие устройства, в которых использован такой способ доступа, получили название ассоциативных ЗУ (АЗУ).
АЗУ характеризуются двумя основными признаками:
доступ к хранимой информации в АЗУ осуществляется исходя из ее содержания;
при каждом обращении к АЗУ возможен одновременный и параллельный доступ ко всей хранящейся информации.
Эти два признака обосновывают свойства «интеллектуальности» АЗУ. Первый из них определяет возможность обработки данных непосредственно в логико-запоминающей среде АЗУ, а второй обеспечивает возможность коллективной обработки информации.
АЗУ, реализующие помимо стандартных операций ассоциативной
обработки информации функции преобразования многомерной информации, называют многокоординатным АЗУ (МКАЗУ) [1]. МКАЗУ являются перспективным направлением в развитии интеллектуальных ЗУ. Они позволяют производить более эффективное, по сравнению с традиционными АЗУ, выполнение локальных и глобальных вычислений, линейных и нелинейных вычислений, интенсивное использование логико-запоминающей среды АЗУ, объекно- и координатно- ориентированных вычислений, символьных вычислений и вычислений на элементах, контекстно свободных и контекстно зависимых вычислений.
Дальнейшее развитие идей, реализованных в МКАЗУ, воплощено в ассоциативных средах (АС), отличительными особенностями которых является возможность обмена информацией между ячейками [2]. АС широко представлены разнообразием форм обмена-информацией, организацией накопителей и ячеек в них .однако, алгоритмы обработки информации, способы их представления и записи исследованы недостаточно. Можно сказать, что число видов и типов АС значительно превосходит число конкретных реализаций алгоритмов и программ для них. Таким образом, существует разрыв между возможностями АС умноженными на число их видов и числом алгоритмов обработки информации. Наличие данного разрыва объясняется в основном отсутствием аппарата, позволяющего описывать алгоритмы и программы для АС, недостаточной проработкой вопроса о месте АС в вычислительной системе и сравнительной новизной самих АС.
Данная работа предназначена для сокращения этого разрыва путем разработки общих направлений и методов обработки информации в ассоциативных средах, разработки алгоритмов обработки информации на примерах базовых алгоритмов обработки изображений и служит дальнейшим развитием работ, проводимых на кафедре Вычислительной Техники Московского Энергетического Института под руководством профессора Огнева И. В.
Цель работы состоит в разработке и исследовании новых типов ассоциативных сред, методов и алгоритмов обработки информации на их основе.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
разработка концепции построения вычислителя на основе ассоциативной среды;
разработка и исследование ассоциативных сред для обработки информации методами клеточной логики;
разработка методов и алгоритмов обработки информации на примере обработки изображений;
разработка методов и алгоритмов обработки нечеткой информации в АС на примере нечеткого ассоциативного поиска.
Объектом исследований являются многокоординатные ассоциативные среды, средства описания таких сред, а также алгоритмы обработки информации, построенные на их основе.
Методы исследования базируются на теориях арифметических и логических основ вычислительной техники, системного анализа, теории оптимальных ассоциативных преобразований, функционального анализа, математического анализа, методах клеточной логики. Экспериментальные исследования, для подтверждения полученных в ходе диссертационной работы результатов, проводились на основе имитационного моделирования на ЭВМ.
Научная новизна работы заключается в следующем:
разработаны и исследованы ассоциативные среды нового типа - с
локальными связями между ячейками в пределах одного накопите
ля для обработки информации методами клеточной логики;
разработан метод конвейерной обработки изображений методами клеточной логики, который реализован на многомерной ассоциативной среде для быстрой потоковой обработки больших объемов данных;
разработан метод командного управления ассоциативными накопителями, построенный на концепции представления ассоциативной среды, как операционного устройства, для повышения функциональности и гибкости управления ассоциативными ячейками;
разработаны методики реализации алгоритмов обработки изображений в ассоциативных средах для применения их в задачах распознавания образов;
разработана методика вычисления коэффициентов разложения в ряд Фурье и Уолша для рализации алгоритмов распознавания изображений, инвариантно к сдвигам в ассоциативных средах;
разработан и исследован потоково-осцилляторный метод для обработки информации в ассоциативных средах;
разработаны и исследованы ассоциативные среды с фиксацией в ячейках кода микрооперации для реализации потоково-осцилляторного метода;
разработаны и исследованы типовые клеточные ансамбли неоднородной клеточной логики для применения их в схемах обработки информации потоково-осцилляторным методом;
разработаны и исследованы методы представления нечеткой информации и нечеткий ассоциативный поиск в ассоциативных средах.
Практическая ценность.
Работа выполнялась в соответствии с планами Российского фонда фундаментальных исследований и гранта Президента Российской Феде-
рации №01-15-99556 ( проект «Ассоциативные системы и среды хранения и обработки информации: теория и прикладные разработки»). Практическая ценность работы состоит в следующем:
разработана схема ассоциативной ячейки и структурная схема ассоциативной среды с локальными связями для проектирования и создания СБИС на их основе;
разработаны схемы ассоциативной среды и схемы ассоциативных ячеек с командным управлением для проектирования и создания СБИС на их основе;
разработана схема ассоциативной среды с фиксацией кода микрооперации для проектирования и создания СБИС на их основе;
предложенные схемы, алгоритмы и информационные модели являются основой для построения различных устройств обработки, хранения и передачи информации.
Достоверность научных положений, выводов и практических рекомендаций, сформулированных в диссертации, подтверждается вычислительными экспериментами и данными, полученными при имитационном моделировании, апробацией работы в международных и региональных конференциях.
Апробация работы. Основные результаты работы докладывались на: Международном форуме информатизации МФИ-2001 «Информационные средства и технологии» ( Москва 2001 ); Международной конференции «Системы компьютерной математики и их приложения» ( Смоленск 2001 ) ; Международной научной конференции «Математические методы в интеллектуальных информационных системах - 2002» ( Смоленск 2002 ).
Публикации. Основные результаты диссертации опубликованы в 5-ти печатных работах.
Структура и объем диссертационной работы. Диссертация состоит
из введения, четырех глав, заключения, списка литературы из на-
именований и приложения. Работа содержит страниц текста, рисунков, таблиц,' страниц библиографии.
Основные научные положения, выносимые на защиту:
ассоциативные среды с локальными связями для проведения операций клеточной логики;
метод конвейерных вычислений для реализации операций клеточной логики с использованием ассоциативных сред;
алгоритмы вычисления коэффициентов разложения в ряд Фурье и Уолша с использованием базовых операций сравнения и сдвига в ассоциативных средах;
потоково-осцилляторный метод обработки информации в ассоциативных средах;
ассоциативные среды с фиксацией в ячейках кода микрооперации;
методы представления информации и клеточные ансамбли для обработки информации в АС потоково-осцилляторным методом.
Разработка ассоциативных сред для реализации операций клеточной логики
Одним из главных достоинств АС для обработки информации является совмещение функций хранения и обработки данных в них [2]. Ассоциативная среда в этой концепции является операционным устройством, так как она осуществляет непосредственную обработку данных. Обработка осуществляется под воздействием управляющего автомата, который в соответствии с алгоритмом обработки данных формирует последовательность управляющих сигналов и анализирует состояние сигналов обратной связи, формирующихся в АС.
Элементарное действие, производимое ассоциативной средой под воздействием определенного набора сигналов, будем называть микрооперацией. Время выполнения микрооперации будем называть тактом, в течение которого значение всех управляющих сигналов в АС остается постоянным. Обработка информации в АС связана с изменением состо-яни ассоциативных ячеек и выходных сигналов обратной связи. Будем считать, что подобное изменение происходит по границе тактов. Таким образом, микрооперация характеризуется определенным набором управляющих сигналов, под воздействием которых ассоциативная ячейка (АЯ) производит обработку данных и по окончании такта изменяет свое состояние и формирует набор выходных сигналов.
Множество микроопераций, производимых ассоциативной средой, определяет ее функциональность. Функциональность АС зависит от функциональности ассоциативных ячеек, от связей ячеек друг с другом и с внешней средой, от размерности и конфигурации ассоциативных накопителей.
Последовательность микроопераций, составляющая логически законченное действие над данными, назовем операцией. Операция состоит из одной и более микроопераций, число и порядок следования которых определяется логикой операции. Формат и способ задания операции и операндов в управляющем автомате определяют его интерфейс, который в данной работе затрагивается лишь в отдельных случаях. Основное внимание уделяется операционному автомату, наборам микроопераций и их реализации с помощью ассоциативных сред.
Предлагаемое определение АС как операционного автомата позволяет обозначить ее место в вычислительной системе, описать структурную схему подобной системы, ввести понятия: микрооперация, операция, алгоритм.
Закон изменения состояния одной, отдельно взятой АЯ в зависимости от состояния соседних АЯ будем называть функцией клеточной логики (ФКЛ). Изменение состояний элементов (вычисление ФКЛ) происходит одновременно для всего массива данных [5].
Под операцией клеточной логики (ОКЛ) в АС будем понимать процесс вычисления определенной ФКЛ для всего массива данных. Операндом для вычисления ОКЛ служит ортогональный ассоциативный накопитель, состояние множества ячеек которого образует массив данных.
Способы обработки данных в ассоциативной памяти методами логики клеточных автоматов были предложены в работах [2] и [12]. Для их реализации ранее применялись ортокоординатные ассоциативные запоминающие устройства (ОКЗУ) [1]. Методика основывалась на последовательном вычислении ФКЛ для каждой ячейки в управляющем автомате. Последовательный характер вычисления ФКЛ резко увеличивает время вычисления нового состояния для всей матрицы, которое можно оценить как 2пт тактов, где т и п - число элементов в двумерной матрице [12].
В данной работе предложена ассоциативная среда (рис. 1.1), отличительной особенностью которой являются локальные связи между ячейками, что позволяет перенести вычисление функции клеточной логики внутрь ячейки и добиться, тем самым, параллельного вычисление этих функций для всех ячеек среды.
Рассмотрим организацию и работу разработанной двумерной ассоциативной среды для реализации операций клеточной логики [13] (рис. 1.1). В ее состав входит: два одномерных накопителя Р[0] и Р[1]; двумерный накопитель Р (рис. 1.1) с числом ячеек 771 X п, состоящий из АЯ связанных локальными связями L}j... Lfj где г є [1... п] и j є [l...m]; шины ассоциативных сигналов: чтения (RD), записи (WR), выбора ячейки (ADR), ассоциативного сравнения (АСО, АС1), данных столбца (DX), данных строки (DY), шина результата ассоциативного поиска (AR) и сигнала синхронизации (CLK).
Режимы работы накопителя ассоциативной среды
В режиме чтения бита по умолчанию j-й строки, на проводник RDj подается логическая единица, множество проводников шины ADR устанавливается в состояние логической единицы, это множество определяет множество столбцов, из которых будет производится чтение. Все другие сигналы находятся в состоянии логического нуля. Все АЯ строки , для которых сигнал выбора столбца находится в логической единице, переходят в состояние чтения, при котором на выход ячейки подается состояние триггера по умолчанию . На выходы других ячеек столбца і подается логический ноль, поэтому на проводнике DXi, в соответствии с (2.2), формируется сигнал, значение которого равно значению бита V выбранной ячейки. Конъюнкция и дизъюнкция по столбцам происходит при выборе нескольких строк с помощью проводников шины RD. В этом режиме для каждого из столбцов, выбранных с помощью сигналов на шине ADR, на ячейки которых поданы сигналы шины RD, производятся операции конъюнкции и дизъюнкции, выдача результата происходит по Л шинам DX и AR соответственно.
В режиме записи столбца, необходимые для записи биты выбираются установкой соответствующих проводников шины WR. Столбцы для записи выбираются с помощью установки единиц на проводниках шины ADR, соответствующих записываемым столбцам. На шину DY подается записываемое слово. Множество АЯ, выбранное с помощью этих сигналов, переходит в режим адресной записи, и по фронту тактового сигнала CLK фиксируют слово, подаваемое по шине DY в триггере V.
В режиме ассоциативного сравнения по столбцам с битом по умолчанию с помощью шин АСО и АСІ формируется аргумент сравнения, причем для каждого j-то бита в соответствии с табл. 1.1 устанавливается режим сравнения: сравнение с нулем, сравнение с единицей, маскирование сравнения. В случае совпадения состояния триггера V данной АЯ и режима сравнения или маскирования сравнения на выходе данной ячейки выдается логическая единица, в противном случае ноль. Значения выходов ячеек г -го столбца анализируются с помощью многовходовых элементов «И» и «ИЛИ» этого столбца и результат выдается на г-й проводник шин DXi и ARi соответственно, после чего логический ноль на проводнике DXi говорит об отсутствии отклика для столбца і (поисковый аргумент не совпал ни с одной ячейкой столбца), а логическая единица на проводнике ARj говорит о полном совпадении поискового аргумента (с учетом маскирования определенных строк) и содержимого столбца.
В режиме выполнения микрооперации на шину ОРС подается код микрооперации, который поступает на вход ОРС всех ячеек накопителя Р. Логическая единица на проводниках шин выбора строки RD и WR совместно с логической единицей на шине выбора столбца ADR определяет совокупность ячеек (рис. 2.3) которые выполняют данную микрооперацию.
Выбранное таким образом множество ячеек переходит в режим выполнения микрооперации, заданной своим кодом, в котором каждая ячейка выполняет микрооперацию, которая должна завершиться за время такта. Аргументами для вычисления данной микрооперации являются: состояние триггеров V и S, состояние соседних ячеек, подаваемое на данную АЯ с помощью входов Li-L$, состояние входов АСО, АСІ, DY.
Данные сигналы должны быть установлены в начале и не меняться в течение такта. Последнее условие легко достижимо, так как эти сигналы устанавливаются управляющим автоматом.
Сигналы L\-L% являются выходными сигналами соседних ячеек, вырабатывающимися в ответ на получение кода операции по шине ОРС и сигналов WR, RD и ADR, поэтому они формируются с некоторым отставанием tb, связанным с задержкой распространения сигнала на блоках ассоциативной ячейки АОУ, ФС и БП (рис. 2.4).
По мере поступления сигналов Ь\-Ь% значение сигнала на выходе ОУ, отвечающего за данную микрооперацию, будет нестабильно в течение времени td, зависимом от разброса задержки распространения ti соседних АЯ. Подобное поведение накладывает ограничение на организацию ОУ, в качестве которых можно использовать цифровые автоматы без памяти. В случае возникновения необходимости реализовывать более сложные алгоритмы микроопераций с применением цифровых автоматов с памятью требуется ввести отдельный синхронизирующий сигнал, подаваемый на все ОУ ячеек и применять двухфазную синхронизацию.
Разработка и реализация набора микроопераций
Получение изображения может происходить различными способами: сканирование, фото-видео съемка, телевизионный прием, считывание с ленты — все эти способы основаны на взаимодействии электромагнитного излучения с датчиками, преобразующими его сначала в аналоговый, а затем в цифровой сигнал. Никакая система ввода изображения не обеспечивает идеального качества изображения исследуемых объектов. Изображения, в процессе формирования их изображающими системами (фотографическими, голографическими, телевизионными), обычно подвергаются воздействию различных случайных помех или шумов. В отличие от так называемых детерминированных искажений, которые часто описываются поэлементными функциональными преобразованиями исходного изображения, для описания случайных воздействий используют модели аддитивного, импульсного и мультипликативного шумов [20].
Наиболее распространенным видом помех является случайный аддитивный шум, статистически независимый от видеосигнала. Модель аддитивного шума используется тогда, когда сигнал, на выходе изображающей системы или на каком-нибудь промежуточном этапе преобразования, может рассматриваться как сумма полезного сигнала и некоторого случайного сигнала (шума). Модель аддитивного шума хорошо описывает действие зернистости фотопленки, флуктуационный шум в радиотехнических системах, шум квантования в аналого-цифровых преобразователях и т.п.
Если действие шума сказывается не по всей протяженности поля изображения, а только в случайно расположенных точках, в которых значения функции яркости заменяются случайными величинами, то шум называют импульсным. На изображении такие помехи выглядят изолированными контрастными точками. Будем считать, что искаженные точки равномерно распределены по всему полю изображения, а яркость искаженных точек имеет равномерное распределение в некотором диапазоне. Импульсный шум характерен для систем передачи изображений по ра 65 диоканалам с использованием нелинейных методов модуляции, а также для цифровых систем передачи и хранения изображений. В частности, импульсный шум присущ устройствам ввода изображений с телевизионной камеры.
Таким образом, ввод изображения связан с появлением шумов, микроразрывов, искажения формы и краев объектов. Для упрощения распознавания и выделения объектов сцены применяются различные методики уменьшения шумов, заполнения микроразрывов и сглаживания формы краев объектов.
На этапе выделения объектов сцены важно определить набор связных областей, которые могут представлять собой объекты для распознавания. Например, это могут быть буквы русского алфавита ( кроме буквы «ы», которая не является связным объектом ). Для выделения связных областей необходимо выделить критерии первоочередного отбора объектов. В большинстве случаев этими критериями могут быть размеры объекта. Например, для задач анализа сцены в реальном времени движущимся роботом, очень важно выделить наиболее значимые по размерам объекты, которые могут быть препятствием или преградой. С другой стороны при анализе сцены положение объекта может быть примерно определено, например в системах автоматического контроля качества проводников печатных плат, поэтому другим важным критерием является геометрическое место. Все это накладывает ряд требований на операцию выделения связного объекта: минимальное время выполнения операции; выделение одного и только одного объекта; возможность выбора критерия первоочередного отбора объектов по их размерам и по положению; осуществлять пометку пикселей, принадлежащих выделенному объекту, таким образом, чтобы обеспечить простой и быстрый доступ ко всему объекту в целом с учетом его реальной геометрии.
Таким образом, целесообразно выделить следующий набор операций для получения (ввода) изображения: операции адресного чтения и адресной записи; для предварительной обработки растра: фильтрация и заполнение пустот; для выделения и доступа к связному объекту; операция выделения связного объекта с различными критериями; групповой доступ к пикселям связного объекта.
Основные понятия и определения
Операция адресного чтения используется для извлечения данных из накопителя Р. Выбор строк для чтения осуществляется с помощью сигналов шины RD. В зависимости от количества выбранных строк и микрооперации, которую выполняет накопитель Р[0] чтение может проходить с выполнением операции конъюнкции над считываемым столбцом, дизъюнкции над считываемым столбцом и чтение строки, как частный случай дизъюнкции. Операция адресного чтения может вестись как с дизъюнкцией по строкам, с помощью шины DO, так и с применением микрооперации «управление чтением с фиксацией в триггер М» накопителя Р[0]. Для выбора столбца могут быть использованы микрооперации: запись в триггер D, сдвиг 1 и сдвиг 2 накопителя Р[1]. Кроме того, операция адресного чтения в любой ее вышеописанной модификации может осуществляться как с триггером V, так и с триггером S.
Рассмотрим наиболее общий случай — дизъюнктивное чтение по строкам и столбцам. Данная операция состоит из следующих микроопераций: запись в триггеры D накопителя Р[0] битовой маски, логические единицы которой активизируют чтение соответствующих строк, запись битовой маски в триггеры D накопителя Р[1] для управления выбором множества столбцов для записи, одновременная активизация микрооперации «управление чтением с фиксацией в триггер М» Р[0], «фиксация результата DX» Р[1] и «адресное чтение строки» Р. Микрооперации записи битовой маски подробно рассматривались в предыдущем разделе, остановимся поподробней на адресном чтении.
На накопитель Р[0] подается код микрооперации «управление чтением с фиксацией в триггер М», по которой на выходную шину RD подается состояние триггера D, а на накопитель Р[1] подается код микрооперации «фиксация результата DX», по которой на выходную шину ADR подается состояние триггера D. Под воздействием сигналов на шинах RD и ADR множество АЯ, находящееся на пересечении тех проводников шин потенциал которых установлен в единицу, переходит в режим адресного чтения. В этом режиме на выход ячейки выдается состояние триггера V которое с помощью операций дизъюнкции по строкам подается на выходную шину DO и, с помощью дизъюнкции по столбцам, на выходную шину DX. По фронту сигнала CLK ячейки накопителя Р[0] и Р[1] фиксируют в триггерах М состояние проводников шин DO и DX.
Для исключения дизъюнкции при чтении строки выбирают одну строку, при чтении столбца — один столбец.
Если необходимо сохранить значение триггера М накопителя Р[0] в последнем такте, используют микрооперацию «управление чтением», которая не фиксирует отклик по строкам в этом триггере.
Если необходимо осуществлять последовательное чтение строк или столбцов, целесообразно использовать микрооперацию сдвига накопителя Р[0] или Р[1], соответственно, и, хотя это не уменьшает числа микроопераций в операции чтения, но существенно упрощает управление записью с помощью управляющего автомата.
Операция ассоциативного сравнения используется для поиска в накопителе Р слов, расположенных по столбцам этого накопителя [2]. Аргумент для ассоциативного сравнения заносится в триггеры D накопителя Р[0]. Маска — в триггеры М. Единица в триггере М маскирует данную строку, т.е. исключает ее из сравнения. В процессе сравнения каждая АЯ накопителя Р формирует отклик: единица — значение триггера V совпадает со значением поискового аргумента или замаскировано, ноль — значение не совпадает. Проводники шины ADR выбирают совокупность столбцов для проведения операции. За управление этой шиной отвечает накопитель Р[1], который по коду микрооперации «адресация» выдает на шину ADR состояние триггера D.
На проводниках выходных шинах DX и AR накопителя Р на основании откликов ячеек столбца по формулам (2.2) и (2.3) формируются отклики столбца на поисковый аргумент. Логическая единица на проводнике шины AR говорит о полном совпадении ( с учетом маски ) поискового аргумента и данных в ячейках соответствующего столбца; логический ноль на проводнике шины DX говорит о наличии полного несовпадения поискового аргумента и данных в ячейках соответствующего столбца.
Для проведения операции необходимо иметь поисковый аргумент, который находится в триггерах D накопителя Р[0], маску — триггер М накопителя Р[0], множество столбцов для выполнения микрооперации определяемое триггерами D накопителя Р[\\ и регистр фиксации реакции [1], состоящий из триггеров М накопителя Р[1].
