УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ РАСТРОВЫХ СИСТЕМ ПРОДУКЦИЙ Российский патент 2000 года по МПК G06F17/27 

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

Известны устройства, аппаратно поддерживающие продукционную парадигму программирования: "Устройство для реализации подстановок слов" (а.с. N 1688253, 1991 г., Бюл. N40), реализующее продукции А.А.Маркова, и "Устройство для реализации подстановок слов" (а.с. N1635192, 1991 г., Бюл. N10), реализующее двухбуквенный универсальный класс систем, базированных на правилах.

В качестве прототипа выбрано "Устройство для реализации продукций" (Патент N 2039375, 1995 г., Бюл. N 19), которое позволяет обрабатывать данные символьного типа на основе ассоциативной функциональной памяти с помощью универсального класса продукционных систем с образцами и модификаторами переменной длины. Это устройство ориентировано в основном на ускорение процесса обработки текстовой информации, т.е. информации, представленной в виде одномерной цепочки букв, и не обрабатывает графические объекты растровых продукционных систем.

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

Решение задачи осуществляется тем, что в устройство, содержащее блок управления БУ, блок памяти слов БПС, узел сравнения УС, дополнительно введены арифметико-логическое устройство АЛУ, два регистра адреса клетки PrAK (PrXk и PrYk), регистр признака активной клетки PrПАК, логическая схема "ИЛИ", регистр подстановки PrП, регистр следующей активной клетки PrСАК, триггеры состояния ТС, яркости ТЯ и признака первой клетки ТП, которые в совокупности образуют функционально полную вычислительную ячейку (ФПВЯ), соединенную с другими аналогичными по структуре ФПВЯ, образующими вместе решающий массив РМ, соединенный с дополнительно введенными устройствами предварительной обработки данных УПОД и управления системой УУС, причем первый управляющий вход блока управления подключен к первому управляющему входу ФПВЯ, второй управляющий вход блока управления подключен к второму управляющему входу ФПВЯ, третий управляющий вход блока управления соединен с первым управляющем выходом арифметико-логического устройства, первый управляющий вход которого подключается к второму управляющему выходу блока управления, четвертый управляющий вход которого соединен с вторым управляющем выходом арифметико-логического устройства, второй управляющий вход которого подключен к третьему управляющему выходу блока управления, пятый управляющий вход которого подключен к третьему управляющему выходу арифметико-логического устройства, третий управляющий вход которого подключен к четвертому управляющему выходу блока управления, шестой управляющий вход которого подключен к четвертому управляющему выходу арифметико-логического устройства, четвертый управляющий вход которого подключен к пятому выходу блока управления, седьмой управляющий вход которого подключен к пятому управляющему выходу арифметико-логического устройства, пятый управляющий вход которого подключен к шестому управляющему выходу блока управления, восьмой управляющий вход которого подключен к шестому управляющему выходу арифметико-логического устройства, шестой управляющий вход которого подключен к седьмому управляющему выходу блока управления, восьмой управляющий выход которого подключен к управляющему входу триггера состояния, информационный выход которого подключен к первому информационному входу блока управления, девятый управляющий выход которого подключен к управляющему входу триггера первой клетки, информационный выход которого подключен к первому информационному выходу ФПВЯ, десятый управляющий выход блока управления подключен к управляющему входу триггера яркости, информационный выход которого подключен к второму информационному выходу ФПВЯ, одиннадцатый управляющий выход блока управления подключен к управляющему входу блока памяти слов, первый информационный выход блока управления подключен к третьему информационному выходу ФПВЯ, первый информационный вход которой подключен к второму информационному входу блока управления, информационный выход регистра адреса клетки подключен к первому информационному входу арифметико-логического устройства, второй и третий информационные входы которого подключены к второму и третьему информационным входам ФПВЯ соответственно, четвертый информационный вход которой подключен к информационному входу регистра признака активной клетки, информационный выход которого подключен к информационным входам логической схемы "ИЛИ", информационный выход которой подключен к четвертому информационному входу арифметико-логического устройства, на пятый информационный вход которого подключен информационный выход регистра подстановки, информационный вход которого подключен к первому информационному выходу устройства сравнения, информационный вход которого подключен к первому информационному выходу блока памяти слов, разряды 10...45 первого информационного входа которого подключены к первому информационному выходу арифметико-логического устройства, на шестой информационный вход которого подключены разряды 1...9 второго информационного выхода блока памяти слов, на разряды 1...9 второго информационного входа которого подключен пятый информационный вход ФПВЯ, второй информационный выход арифметико-логического устройства подключен к информационному входу регистра следующей активной клетки, информационный выход которого подключен к четвертому информационному выходу ФПВЯ, первые управляющие входы каждой ФПВЯ подключены к первому управляющему выходу устройства управления системой, на первый информационный вход которого подключены третьи информационные выходы ФПВЯ, первые информационные выходы которых подключены к второму информационному входу устройства управления системой, первые информационные выходы которого подключены к первым информационным входам ФПВЯ, вторые информационные выходы которых подключены к третьему информационному входу устройства управления системой, второй управляющий выход которого подключен к первому управляющему входу устройства предварительной обработки данных, первый управляющий выход которого подключен к первому управляющему входу устройства управления системой, третий управляющий выход которого подключен к второму управляющему входу устройства предварительной обработки данных, второй управляющий выход которого подключен к вторым управляющим входам ФПВЯ, третьи информационные входы которых подключены к первому информационному выходу устройства предварительной обработки данных, второй информационный выход которого подключен к вторым информационным входам ФПВЯ и к четвертому информационному входу устройства управления системой, четвертый управляющий выход которого подключен к третьему управляющему входу устройства предварительной обработки данных, первый информационный вход которого является внешним информационным входом системы, ФПВЯ решающего массива представляют собой однородную структуру, в которой четвертый информационный выход ФПВЯ с координатами (i, j) подключен на четвертые информационные входы ФПВЯ с координатами (i, j+1), (i+1, j+1), (i+1, j), (i+1, j-1), (i, j-1), вторые информационные выходы ФПВЯ с координатами (i, j+1), (i-1, j+1), (i-1, j), (i-1, j-1), (i, j-1) подключены к пятому информационному входу ФПВЯ с координатами (i, j), в устройстве предварительной обработки данных первый управляющий вход подключен к первому управляющему входу блока управления устройством, первый управляющий выход которого подключен к первому управляющему выходу устройства предварительной обработки данных, второй управляющий вход которого подключен к второму управляющему входу блока управления устройством, третий управляющий вход которого подключен к третьему управляющему входу устройства предварительной обработки данных, на второй управляющий выход которого подключен информационный выход триггера, управляющий вход которого подключен к второму управляющему выходу блока управления устройством, третий управляющий выход которого подключен к первому управляющему входу решающего коммутатора, первый управляющий выход которого подключен к четвертому управляющему входу блока управления устройством, четвертый управляющий выход которого подключен к первому управляющему входу специализированного коммутатора для выполнения предварительной обработки координат отрезка, первый управляющий выход которого подключен к пятому управляющему входу блока управления устройством, пятый управляющий выход которого подключен к первому управляющему входу входного буфера, первый управляющий выход которого подключен к шестому управляющему входу блока управления устройством, информационный вход устройства предварительной обработки данных подключен к первому информационному входу входного буфера, второй информационный вход/выход которого подключен к первому информационному входу/выходу специализированного коммутатора для выполнения предварительной обработки координат отрезка, второй информационный вход/выход которого подключен к информационному входу/выходу вспомогательного регистра, а третий информационный выход подключен к информационному входу памяти координат концов отрезка, информационный выход которой подключен к второму информационному выходу устройства предварительной обработки данных и к информационному входу решающего коммутатора, информационный выход которого подключен к информационному входу выходного буфера, информационный выход которого подключен к первому информационному выходу устройства предварительной обработки данных, сигналы управления синхронизацией и начальной установки подаются на соответствующие входы блоков устройства для реализации растровых систем продукций.

Данное устройство ориентировано на использование в системах символьной обработки информации в качестве подсистемы обработки графических данных для акселерирования процессов построения изображений. Авторы при разработке устройства используют подход, в котором любое изображение описывается в виде конструктивных объектов, что позволяет представить изображение в виде набора символов определенного алфавита и работать с изображением как с текстовой информацией. Символ представляется совокупностью клеток (матрица 3 х 3 элемента) и "штрих"-клеток, где клетка физически представляет собой пиксель и ассоциируется с ФПВЯ, а "штрих"-клетка - точку пересечения сетки растра, соединяющей два соседних пикселя, с идеальной линией графического примитива. В качестве графического примитива в данном устройстве используется прямая линия, которую необходимо отобразить на экране монитора под любым углом. Назовем клетку, задействованную в отображении графического примитива в текущий момент времени, активной, а незадействованную - пассивной. Тогда алгоритм определения новых активных клеток будет сводиться к анализу уже активных клеток и расположению относительно них "штрих"-клеток.

Сущность изобретения поясняется чертежами, где на фиг. 1 представлено устройство для реализации растровых систем продукций, на фиг. 2 представлена структурная схема устройства предварительной обработки данных, на фиг. 3 представлена структурная схема ФПВЯ 3, на фиг. 4 представлен алгоритм работы устройства управления системой, на фиг. 5 представлен алгоритм работы специализированного коммутатора для выполнения предварительной обработки координат отрезка устройства предварительной обработки данных, на фиг. 6 представлен алгоритм работы решающего коммутатора, на фиг. 7 представлен алгоритм работы блока управления устройства предварительной обработки данных, на фиг.8 представлена схема соединения ФПВЯ с соседними ФПВЯ, на фиг. 9 приводится пример кодирования клеточного образа в блоке памяти слов, на фиг. 10 показан пример кодирования признаков клеточного образа в блоке памяти слов, на фиг. 11 представлен алгоритм вычисления признаков клеточных образов, на фиг. 12 представлена процедура Алг01, на фиг. 13 представлена процедура Алг02, на фиг. 14 представлена процедура Алг03, на фиг. 15 представлена процедура Алг04, на фиг. 16 представлена процедура Алг03, на фиг. 17 представлена процедура Алг06, на фиг. 18 представлен алгоритм определения адреса следующей активной клетки, на фиг. 19 представлен алгорифм растеризации отрезка, на фиг. 20 представлены клеточные образы символов продукционной системы, а на фиг. 21 представлен алгоритм работы блока управления ФПВЯ.

В устройство, содержащее блок управления 12, блок памяти слов 21, узел сравнения 22, дополнительно введены арифметико- логическое устройство 14, регистры адреса клетки 13, регистр признака активной клетки 20, логическая схема "ИЛИ" 19, регистр подстановки 23, регистр следующей активной клетки 18, триггеры состояния 15, яркости 16 и признака первой клетки 17, которые в совокупности образуют функционально полную вычислительную ячейку (ФПВЯ) 3, соединенную с другими аналогичными по структуре ФПВЯ, образующими вместе решающий массив РМ, соединенный с дополнительно введенными устройствами предварительной обработки данных 2 и управления системой 1, причем первый управляющий вход блока управления 12 подключен к первому управляющему входу ФПВЯ 3, второй управляющий вход блока управления 12 подключен к второму управляющему входу ФПВЯ 3, третий управляющий вход блока управления 12 соединен с первым управляющим выходом арифметико-логического устройства 14, первый управляющий вход которого подключается к второму управляющему выходу блока управления 12, четвертый управляющий вход которого соединен с вторым управляющим выходом арифметико-логического устройства 14, второй управляющий вход которого подключен к третьему управляющему выходу блока управления 12, пятый управляющий вход которого подключен к третьему управляющему выходу арифметико-логического устройства 14, третий управляющий вход которого подключен к четвертому управляющему выходу блока управления 12, шестой управляющий вход которого подключен к четвертому управляющему выходу арифметико-логического устройства 14, четвертый управляющий вход которого подключен к пятому выходу блока управления 12, седьмой управляющий вход которого подключен к пятому управляющему выходу арифметико-логического устройства 14, пятый управляющий вход которого подключен к шестому управляющему выходу блока управления 12, восьмой управляющий вход которого подключен к шестому управляющему выходу арифметико-логического устройства 14, шестой управляющий вход которого подключен к седьмому управляющему выходу блока управления 12, восьмой управляющий выход которого подключен к управляющему входу триггера состояния 15, информационный выход которого подключен к первому информационному входу блока управления 12, девятый управляющий выход которого подключен к управляющему входу триггера первой клетки 17, информационный выход которого подключен к первому информационному выходу ФПВЯ 3, десятый управляющий выход блока управления 12 подключен к управляющему входу триггера яркости 16, информационный выход которого подключен к второму информационному выходу ФПВЯ 3, одиннадцатый управляющий выход блока управления 12 подключен к управляющему входу блока памяти слов 21, первый информационный выход блока управления 12 подключен к третьему информационному выходу ФПВЯ 3, первый информационный вход которой подключен к второму информационному входу блока управления 12, информационный выход регистра адреса клетки 13 подключен к первому информационному входу арифметико-логического устройства 14, второй и третий информационные входы которого подключены к второму и третьему информационным входам ФПВЯ 3 соответственно, четвертый информационный вход которой подключен к информационному входу регистра признака активной клетки 20, информационный выход которого подключен к информационным входам логической схемы <ИЛИ> 19, информационный выход которой подключен к четвертому информационному входу арифметико-логического устройства 14, на пятый информационный вход которого подключен информационный выход регистра подстановки 23, информационный вход которого подключен к первому информационному выходу устройства сравнения 22, информационный вход которого подключен к первому информационному выходу блока памяти слов 21, разряды 10...45 первого информационного входа которого подключены к первому информационному выходу арифметико-логического устройства 14, на шестой информационный вход которого подключены разряды 1. ..9 второго информационного выхода блока памяти слов 21, на разряды 1...9 второго информационного входа которого подключен пятый информационный вход ФПВЯ 3, второй информационный выход арифметико-логического устройства 14 подключен к информационному входу регистра следующей активной клетки 18, информационный выход которого подключен к четвертому информационному выходу ФПВЯ 3, первые управляющие входы каждой ФПВЯ 3 подключены к первому управляющему выходу устройства управления системой 1, на первый информационный вход которого подключены третьи информационные выходы ФПВЯ 3, первые информационные выходы которых подключены к второму информационному входу устройства управления системой 1, первые информационные выходы которого подключены к первым информационным входам ФПВЯ 3, вторые информационные выходы которых подключены к третьему информационному входу устройства управления системой 1, второй управляющий выход которого подключен к первому управляющему входу устройства предварительной обработки данных 2, первый управляющий выход которого подключен к первому управляющему входу устройства управления системой 1, третий управляющий выход которого подключен к второму управляющему входу устройства предварительной обработки данных 2, второй управляющий выход которого подключен к вторым управляющим входам ФПВЯ 3, третьи информационные входы которых подключены к первому информационному выходу устройства предварительной обработки данных 2, второй информационный выход которого подключен к вторым информационным входам ФПВЯ 3 и к четвертому информационному входу устройства управления системой 1, четвертый управляющий выход которого подключен к третьему управляющему входу устройства предварительной обработки данных 2, первый информационный вход которого является внешним информационным входом системы, ФПВЯ 3 решающего массива представляют собой однородную структуру размерностью n х m, в которой четвертый информационный выход ФПВЯ 3 с координатами (i, j) подключен на четвертые информационные входы ФПВЯ 3 с координатами (i, j+1), (i+1, j+1), (i+1, j), (i+1, j-1), (i, j-1), вторые информационные выходы ФПВЯ 3 с координатами (i, j+1), (i-1, j+1), (i-1, j), (i-1, j-1), (i, j-1) подключены к пятому информационному входу ФПВЯ 3 с координатами (i, j), в устройстве предварительной обработки данных 2 первый управляющий вход подключен к первому управляющему входу блока управления устройством 4, первый управляющий выход которого подключен к первому управляющему выходу устройства предварительной обработки данных 2, второй управляющий вход которого подключен к второму управляющему входу блока управления устройством 4, третий управляющий вход которого подключен к третьему управляющему входу устройства предварительной обработки данных 2, на второй управляющий выход которого подключен информационный выход триггера 8, управляющий вход которого подключен к второму управляющему выходу блока управления устройством 4, третий управляющий выход которого подключен к первому управляющему входу решающего коммутатора 10, первый управляющий выход которого подключен к четвертому управляющему входу блока управления устройством 4, четвертый управляющий выход которого подключен к первому управляющему входу специализированного коммутатора для выполнения предварительной обработки координат отрезка 6, первый управляющий выход которого подключен к пятому управляющему входу блока управления устройством 4, пятый управляющий выход которого подключен к первому управляющему входу входного буфера 5, первый управляющий выход которого подключен к шестому управляющему входу блока управления устройством 4, информационный вход устройства предварительной обработки данных 2 подключен к первому информационному входу входного буфера 5, второй информационный вход/выход которого подключен к первому информационному входу/выходу специализированного коммутатора для выполнения предварительной обработки координат отрезка 6, второй информационный вход/выход которого подключен к информационному входу/выходу вспомогательного регистра 7, а третий информационный выход подключен к информационному входу памяти координат концов отрезка 9, информационный выход которой подключен к второму информационному выходу устройства предварительной обработки данных 2 и к информационному входу решающего коммутатора 10, информационный выход которого подключен к информационному входу выходного буфера 11, информационный выход которого подключен к первому информационному выходу устройства предварительной обработки данных 2, сигналы управления синхронизацией и начальной установки поданы на соответствующие входы блоков устройства для реализации растровых систем продукций.

Работа рассматриваемого устройства начинается при поступлении в устройство управления системой активного сигнала "Старт". Алгоритм работы устройства управления системой приведен на фиг. 4. Для описания алгоритма используются следующие идентификаторы:
- Упр1 - команда инициализации блоков устройства предварительной обработки данных
- Упр2 - команда инициализации блоков решающего массива
- Отв1 - сигнал о результатах процесса инициализации устройства предварительной обработки данных
- {Отв2} - множество сигналов о результатах процесса инициализации решающего массива
- Упр3 - команда начала растеризации
- { ПК} - множество сигналов от триггеров ТП признаков первой клетки клеток решающего массива
- ПКУ - сигнал об обработке первой точки примитива
- КРМ - память образа решающего массива
- Упр4 - команда окончания растеризации
- Готов - сигнал о выполнении растеризации.

Работа устройства заключается в следующем. При поступлении сигнала "Старт"=1 устройство управления системы подает команды установки в начальное состояние блоков устройства предварительной обработки информации и решающего массива. При поступлении от них сигналов готовности к работе (Отв1=1, {Отв2} = {1}) устройство управления системой инициирует процесс растеризации, выставляя сигнал Упр3=1. При поступлении хотя бы от одного из элементов сигнала ПК=1 устройство управления системой устанавливает сигнал ПКУ=1, сообщающий о том, что начальный пиксель разлагаемого в растр отрезка определен. После этого устройство управления системой переходит в ждущий режим, анализируя состояние элементов решающего массива по его образу, хранящемуся в памяти карты решающего массива (КРМ), представляющей собой двумерную матрицу размерностью, совпадающей с разрешающей способностью дисплея. При поступлении информации о том, что был вычислен конечный пиксель разлагаемого в растр отрезка, устройство управления системой выставляет сигнал об окончании процесса растеризации Упр4=1 и сигнал Готов=1 для внешнего устройства, инициировавшего вычислительный процесс.

Рассмотрим устройство и работу отдельных модулей системы.

Структурная схема устройства предварительной обработки информации представлена на фиг. 2. Входной буфер ВхБуф1 устройства предварительной обработки данных состоит из четырех регистров Рг1, Рг2, Рг3, Рг4. Выходной буфер ВыхБуф1 представлен двумя регистрами РгАкт1, РгАкт2. Память координат концов отрезка образована четырьмя регистрами PгX1, PгY1, РгХ2, PгY2. Специализированный коммутатор для выполнения предварительной обработки координат отрезка служит для предварительной обработки координат отрезка по алгоритму, представленному на фиг. 5. Для описания алгоритма использованы следующие идентификаторы:
- Рг1, Рг2, Рг3, Рг4 - регистры входного буфера
- PгX1, PгY1, РгХ2, PгY2 - регистры памяти координат концов отрезка
- РгСК - внутренний регистр специализированного коммутатора для выполнения предварительной обработки координат отрезка для временного хранения данных
- КОВ - сигнал об окончании обработки координат, записанных во входной буфер.

Решающий коммутатор выполняет запись в выходной буфер устройства предварительной обработки данных согласно алгоритма, приведенного на фиг. 6. Для описания алгоритма использованы следующие идентификаторы:
- PгX1, PгY1, РгХ2, PгY2 - регистры памяти координат концов отрезка
- РгАкт1, РгАкт2 - регистры выходного буфера
- АВКВ - сигнал об окончании вычисления адреса второй активной клетки.

Алгоритм работы блока управления устройства приведен на фиг. 7. Для описания алгоритма использованы следующие идентификаторы:
- ВхИУ - команда инициализации
- ВыхИУ - сигнал об окончании инициализации
- ВхНР - команда начала растеризации
- Зп1- команда записи во входной буфер
- РЗп1 - сигнал подтверждения записи во входной буфер
- ВКО - команда переопределения координат отрезка
- КОВ - сигнал подтверждения выполнения переопределения координат отрезка
- ВАВК - команда вычисления координат второй активной клетки
- АВКВ - сигнал подтверждения вычисления координат второй активной клетки
- Q(T1) - выходной сигнал триггера Т1
- ВхКР - команда окончания растеризации.

Работа устройства предварительной обработки данных происходит следующим образом. При поступлении на первый управляющий вход блока управления устройством сигнала ВхИ=1 выполняется инициализация внутренних блоков устройства предварительной обработки данных, а именно регистры входного буфера ВхБуф1, выходного буфера ВыхБуф1, вспомогательный регистр РгСК и триггер Т1 (выход Q) обнуляются, затем с первого информационного выхода устройству управления системой подается сигнал ВыхИУ=1, сообщающий об окончании процесса инициализации. При поступлении на второй управляющий вход блока управления устройством сигнала ВхНР=1 в устройстве предварительной обработке данных происходит следующее. По сигналу Зп1=1 в входной буфер считываются с первого информационного входа данные - координаты отрезка. После записи данных входной буфер выставляет сигнал РЗп1=1. При получении сигнала РЗп1=1 блок управления устройством устанавливает сигнал ВКО=1. Специализированный коммутатор для выполнения предварительной обработки координат отрезка, получив сигнал ВКО= 1, выполняет анализ входных координат в соответствии с алгоритмом, представленным на фиг. 5, результат обработки записывает в память координат концов отрезка и выставляет сигнал КОВ=1. Блок управлением устройством, получив сигнал КОВ=1, выставляет в решающий коммутатор сигнал ВАВК=1, получив который, решающий коммутатор определяет адрес второй активной клетки решающего массива согласно алгоритма, приведенного на фиг. 6, записывает полученный адрес в выходной буфер и устанавливает сигнал АВКВ=1. Блок управления устройством, получив АВКВ= 1, устанавливает триггер Т1 (выход Q) в единичное состояние и переходит в режим ожидания сигнала ВхКР=1, при получении которого сбрасывает триггер Т1 в нулевое состояние.

Структурная схема ФПВЯ показана на фиг. 3. Регистр адреса клетки состоит из двух слов - РгХк и РгYк, в которых хранится адрес ФПВЯ исходя из двумерной структуры решающего массива. Пятиразрядные регистры признака активной клетки и следующей активной клетки соединены с ближайшими соседними ФПВЯ, как показано на фиг. 8. Блок памяти слов - это сорокапятиразрядный регистр, логически состоящий из трех слов: первого - девятибитного, представляющего собой карту клеточного образа, и двух восемнадцатибитных, представляющих собой карты признаков клеточной области по уровню абсцисс и ординат соответственно. Принцип кодирования блока памяти слов показан на фиг. 9, 10. Фиг. 9 демонстрирует принцип кодирования клеточной области. Получившая управление ФПВЯ, имеет координаты (i, j). В этом случае в блок памяти слов поступают информационные сигналы с триггеров яркости соседних ФПВЯ, имеющих координаты: (i, j+1), (i-1, j+1), (i-1, j), (i-1, j-1), (i, j-1) (как показано на фиг. 8). Состояние ФПВЯ с координатами (i+1, j+1), (i+1, j), (i+1, j-1) безразлично в данной ситуации и, поэтому, в соответствующие разряды блока памяти слов занесены нулевые значения, а в пятый разряд блока памяти слов устанавливается единичное значение. Карта признаков клеточной области заполняется аналогично карты клеточного образа. Отличия заключаются в следующем:
- для описания каждой клетки отводятся два разряда;
- вычисление значений для карты признаков клеточной области по уровню абсцисс выполняется в соответствии с уравнением

где

i, j - координаты ФПВЯ, выполняющей вычисления,
(x₁, y₁) - координаты начала отрезка,
(x2, y2) - координаты конца отрезка;
- вычисление значений для карты признаков клеточной области по уровню ординат выполняется в соответствии с уравнением

где
i, j - координаты ФПВЯ, выполняющей вычисления,
(x₁, y₂) - координаты начала отрезка,
(x₂, y₂) - координаты конца отрезка;
- значения признаков клеточной области вычисляются для текущей ФПВЯ и ФПВЯ, передавшей управление текущей.

Девятиразрядный регистр подстановки имеет структуру, аналогичную первому слову блока памяти слов (первые девять разрядов), и его содержимое определяет новое состояние карты клеточного образа. Арифметико-логическое устройство, кроме стандартного набора операций (сложение, вычитание, умножение, деление, сравнение), на аппаратном уровне должно поддерживать ряд специальных алгоритмов, представленных на фиг. 11-18. Для описания указанных алгоритмов использованы следующие идентификаторы:
- БПС [n] - n-ый разряд блока памяти слов;
- Алг01 - процедура, представленная на фиг. 12;
- Алг02 - процедура, представленная на фиг. 13;
- Алг03 - процедура, представленная на фиг. 14;
- Алг04 - процедура, представленная на фиг. 15;
- Алг05 - процедура, представленная на фиг. 16;
- Алг06 - процедура, представленная на фиг. 17;
- РППАК - сигнал об окончании выполнения алгоритма вычисления признаков клеточного образа;
- GetX₀(A) - функция с параметром А, вычисляющая значение вспомогательной переменной РгХ0 согласно выражения

где РгХ1, РгХ2, PгY1, PгY2 - координаты концов обрабатываемого отрезка;
- GetYo(A) - функция с параметром А, вычисляющая значение вспомогательной переменной PгY0 согласно выражения

где РгХ1, РгХ2, PгY1, PгY2 - координаты концов обрабатываемого отрезка;
- РгХ0, PгY0 - вспомогательные переменные;
- РгХк, РгYк - слова регистра адреса клетки;
- РгСАК[n] - n-ый разряд регистра следующей активной клетки.

Алгоритм работы ФПВЯ представлен на фиг. 21. Для описания алгоритма использованы следующие идентификаторы:
- ВхИ - сигнал о начале инициализации блоков ФПВЯ;
- ВыхИ - сигнал о готовности ФПВЯ к работе;
- Q2(TC) - выход триггера состояния ФПВЯ;
- Вх1 - сигнал о начале растеризации;
- Ср1 - команда сравнения координаты начала отрезка с координатами текущей ФПВЯ;
- PCp1 - сигнал результата выполнения команды Ср1;
- Q1(ТЯ) - выход триггера яркости ФПВЯ;
- ВхПК - сигнал об окончании обработки первой координаты отрезка;
- Ср2 - команда сравнения координат текущей ФПВЯ с второй координатой отрезка;
- РСр2 - сигнал результата выполнения команды Ср2;
- Зп1 - команда записи в блок памяти слов первых девяти разрядов;
- ППАК - команда "Вычислить признаки активной клетки";
- РППАК - сигнал об окончании выполнения команды ППАК;
- ПАСК - команда "Вычислить адрес следующей активной клетки";
- РПАСК - сигнал об окончании выполнения команды ПАСК;
- Ср3 - команда определения получения флага активности от соседних ФПВЯ;
- РСр3 - результат выполнения команды Ср3;
- Ср4 - команда сравнения координат текущей ФПВЯ с координатами конца отрезка;
- РСр4 - результат выполнения команды Ср4.

Работа ФПВЯ заключается в следующем. При поступлении сигнала ВхИ=1 блок управления инициализирует устройства ФПВЯ, а именно в регистры признака активной клетки, следующей активной клетки, подстановки, блок памяти слов, триггеры состояния, яркости и первой клетки записываются нулевые значения; в регистре адреса клетки всегда содержится индивидуальный адрес ФПВЯ, исходя из ее положения в двумерной среде решающего массива. После выполнения инициализации блок управления выставляет флаг окончания инициализации ВыхИ=1. При поступлении сигнала Вх1=1 блок управления проверяет состояние триггера ТС состояния клетки: если на выходе триггера Q2(TC) установлен единичный сигнал, то ФПВЯ прекращает работу, в противном случае - блок управления вырабатывает команду Ср1=1 арифметико-логическому устройству, которое вырабатывает сигнал PCpl исходя из следующей ситуации:

где РгХк, РгYк - содержимое слов регистра адреса клетки;
PгX1, PгY1 - содержимое регистров памяти координат концов отрезка.

Если адрес ФПВЯ совпал с адресом начального пикселя отрезка (РСр=1), то блок управления присваивает триггерам яркости, состояния и первой клетки единичные значения (Q1(ТЯ): 1, Q2(TC):=1, Q3(ТП):=1), в противном случае - ФПВЯ переходит в ждущий режим. При поступлении сигнала ВхПК=1 блок управления вырабатывает команду Ср2=1 арифметико-логическому устройству, которое в ответ выставляет сигнал РСр2 в соответствии со следующим выражением:

где РгХк, РгYк - содержимое слов регистра адреса клетки;
- РгАкт1, РгАкт2 - содержимое регистров выходного буфера устройства предварительной обработки данных.

Если адрес второго пикселя отрезка совпадает с адресом ФПВЯ (РСр2=1), то блок управления вырабатывает сигнал Зп1= 1, по которому в первые девять разрядов блока памяти слов записываются значения с пятого информационного входа ФПВЯ; затем блок управления выставляет команду ППАК=1, по которой арифметико-логическое устройство определяет признаки клеточного образа, записывает их в блок памяти слов (разряды 10-45) и сообщает блоку управления об окончании обработки посредством сигнала РППАК=1 (фиг. 11-17). Блок управления, получив сигнал РППАК=1, активизирует процесс алгорифмической обработки, который будет заключаться в выполнении алгорифма, приведенного на фиг. 19. Клеточные образы, соответствующие символам, используемым в выше указанном алгорифме, приведены на фиг. 20. Кодирование символов в устройстве сравнения аналогично принятому для блока памяти слов и поясняется на фиг. 9, 10. Результат обработки записывается в регистр подстановки. Блок управления, через некоторое время задержки, величина которого определяется временем однократного полного прохождения алгорифма плюс время записи в регистр подстановки, дает команду ПАСК=1 арифметико-логическому устройству на определение адреса следующей активной клетки. Арифметико-логическое устройство, получив команду ПАСК=1, вычисляет адрес следующей активной клетки в соответствии с алгоритмом, приведенным на фиг. 18. Блок управления, получив сигнал от арифметико-логического устройства об окончании выполнения команды ПАСК, присваивает триггерам яркости и состояния единичные значения (Q1(ТЯ):=1, Q2(TC):=1) и прекращает работу ФПВЯ.

Если адрес второго пикселя отрезка не совпал с адресом ФПВЯ (РСр2=0), то блок управления вырабатывает команду Ср3= 1 арифметико-логическому устройству, которое, в свою очередь, анализирует состояние своего четвертого информационного входа и вырабатывает сигнал РСр3 в соответствии с правилом: если на четвертом информационном входе присутствует сигнал логической единицы, то РСр3:=1, иначе - РСр3:=0. Блок управления, получив сигнал РСр3=0, прекращает работу ФПВЯ. Если же, РСр3=1, то блок управления вырабатывает команду Ср4= 1 арифметико-логическому устройству, которое в ответ вырабатывает сигнал РСр4 в соответствии с правилом

где РгХк, РгYк - содержимое слов регистра адреса клетки;
РгХ2, PгY2 - содержимое регистров памяти координат концов отрезка.

Если координаты концов отрезка не совпадают с адресом ФПВЯ (РСр4=0), то блок управления вырабатывает сигнал Зп1= 1, по которому в первые девять разрядов блока памяти слов записываются значения с пятого информационного входа ФПВЯ; затем блок управления выставляет команду ППАК=1, по которой арифметико-логическое устройство определяет признаки клеточного образа, записывает их в блок памяти слов (разряды 10-45) и сообщает блоку управления об окончании обработки посредством сигнала РППАК=1 (фиг. 11-17). Блок управления, получив сигнал РППАК=1, активизирует процесс алгорифмической обработки, который будет заключаться в выполнении алгорифма, приведенного на фиг. 19. Клеточные образы, соответствующие символам, используемым в выше указанном алгорифме, приведены на фиг. 20. Кодирование символов в устройстве сравнения аналогично принятому для блока памяти слов и поясняется на фиг. 9, 10. Результат обработки записывается в регистр подстановки. Блок управления, через некоторое время задержки, величина которого определяется временем однократного полного прохождения алгорифма плюс время записи в регистр подстановки, дает команду ПАСК=1 арифметико-логическому устройству на определение адреса следующей активной клетки. Арифметико-логическое устройство, получив команду ПАСК=1, вычисляет адрес следующей активной клетки в соответствии с алгоритмом, приведенным на фиг. 18. Блок управления, получив сигнал от арифметико-логического устройства об окончании выполнения команды ПАСК, присваивает триггерам яркости и состояния единичные значения (Q1(ТЯ):= 1, Q2(TC):=1) и прекращает работу ФПВЯ.

Если координаты концов отрезка совпадают с адресом ФПВЯ (РСр4=1), то блок управления присваивает триггерам яркости и состояния единичные значения (Q1(ТЯ):=1, Q2(TC):=1) и прекращает работу ФПВЯ.

Изобретение относится к вычислительной технике. Его использование для решения задач обработки графической информации позволяет получить технический результат в виде обеспечения высокоскоростного процесса растровой развертки отрезков переменной длины и произвольной ориентации при использовании однородных систем обработки данных. Устройство содержит блок управления, блок памяти слов и узел сравнения. Технический результат достигается благодаря тому, что дополнительно введены арифметико-логическое устройство, регистры адреса клетки, регистр признака активной клетки, логическая схема ИЛИ, регистр подстановки, регистр следующей активной клетки, триггеры состояния, яркости и признака первой клетки, которые в совокупности образуют функционально полную вычислительную ячейку (ФПВЯ), соединенную с другими аналогичными по структуре ФПВЯ, образующими вместе решающий массив, соединенный с дополнительно введенными устройствами предварительной обработки данных и управления системой. 21 ил.

Устройство для реализации растровых систем продукций, содержащее блок управления, блок памяти слов, узел сравнения, отличающееся тем, что дополнительно введены арифметико-логическое устройство, регистры адреса клетки, регистр признака активной клетки, логическая схема ИЛИ, регистр подстановки, регистр следующей активной клетки, триггеры состояния, яркости и признака первой клетки, которые в совокупности образуют функционально полную вычислительную ячейку (ФПВЯ), соединенную с другими аналогичными по структуре ФПВЯ, образующими вместе решающий массив, соединенный с дополнительно введенными устройствами предварительной обработки данных и управления системой, причем первый управляющий вход блока управления подключен к первому управляющему входу ФПВЯ, второй управляющий вход блока управления подключен к второму управляющему входу ФПВЯ, третий управляющий вход блока управления соединен с первым управляющим выходом арифметико-логического устройства, первый управляющий вход которого подключается к второму управляющему выходу блока управления, четвертый управляющий вход которого соединен с вторым управляющим выходом арифметико-логического устройства, второй управляющий вход которого подключен к третьему управляющему выходу блока управления, пятый управляющий вход которого подключен к третьему управляющему выходу арифметико-логического устройства, третий управляющий вход которого подключен к четвертому управляющему выходу блока управления, шестой управляющий вход которого подключен к четвертому управляющему выходу арифметико-логического устройства, четвертый управляющий вход которого подключен к пятому выходу блока управления, седьмой управляющий вход которого подключен к пятому управляющему выходу арифметико-логического устройства, пятый управляющий вход которого подключен к шестому управляющему выходу блока управления, восьмой управляющий вход которого подключен к шестому управляющему выходу арифметико-логического устройства, шестой управляющий вход которого подключен к седьмому управляющему выходу блока управления, восьмой управляющий выход которого подключен к управляющему входу триггера состояния, информационный выход которого подключен к первому информационному входу блока управления, девятый управляющий выход которого подключен к управляющему входу триггера первой клетки, информационный выход которого подключен к первому информационному выходу ФПВЯ, десятый управляющий выход блока управления подключен к управляющему входу триггера яркости, информационный выход которого подключен к второму информационному выходу ФПВЯ, одиннадцатый управляющий выход блока управления подключен к управляющему входу блока памяти слов, первый информационный выход блока управления подключен к третьему информационному выходу ФПВЯ, первый информационный вход которой подключен к второму информационному входу блока управления, информационный выход регистра адреса клетки подключен к первому информационному входу арифметико-логического устройства, второй и третий информационные входы которого подключены к второму и третьему информационным входам ФПВЯ соответственно, четвертый информационный вход которой подключен к информационному входу регистра признака активной клетки, информационный выход которого подключен к информационным входам логической схемы ИЛИ, информационный выход которой подключен к четвертому информационному входу арифметико-логического устройства, на пятый информационный вход которого подключен информационный выход регистра подстановки, информационный вход которого подключен к первому информационному выходу устройства сравнения, информационный вход которого подключен к первому информационному выходу блока памяти слов, разряды 10 ... 45 первого информационного входа которого подключены к первому информационному выходу арифметико-логического устройства, на шестой информационный вход которого подключены разряды 1 ... 9 второго информационного выхода блока памяти слов, на разряды 1 ... 9 второго информационного входа которого подключен пятый информационный вход ФПВЯ, второй информационный выход арифметико-логического устройства подключен к информационному входу регистра следующей активной клетки, информационный выход которого подключен к четвертому информационному выходу ФПВЯ, первые управляющие входы каждой ФПВЯ подключены к первому управляющему выходу устройства управления системой, на первый информационный вход которого подключены третьи информационные выходы ФПВЯ, первые информационные выходы которых подключены к второму информационному входу устройства управления системой, первые информационные выходы которого подключены к первым информационным входам ФПВЯ, вторые информационные выходы которых подключены к третьему информационному входу устройства управления системой, второй управляющий выход которого подключен к первому управляющему входу устройства предварительной обработки данных, первый управляющий выход которого подключен к первому управляющему входу устройства управления системой, третий управляющий выход которого подключен к второму управляющему входу устройства предварительной обработки данных, второй управляющий выход которого подключен к вторым управляющим входам ФПВЯ, третьи информационные входы которых подключены к первому информационному выходу устройства предварительной обработки данных, второй информационный выход которого подключен к вторым информационным входам ФПВЯ и к четвертому информационному входу устройства управления системой, четвертый управляющий выход которого подключен к третьему управляющему входу устройства предварительной обработки данных, первый информационный вход которого является внешним информационным входом системы, ФПВЯ решающего массива представляют собой однородную структуру размерностью m х n, в которой четвертый информационный выход ФПВЯ с координатами (i, j) подключен на четвертые информационные входы ФПВЯ с координатами (i, j + 1), (i + 1, j + 1), (i + 1, j), (i + 1, j - 1), (i, j - 1), вторые информационные выходы ФПВЯ с координатами (i, j + 1), (i - 1, j + 1), (i - 1, j), (i - 1, j - 1), (i, j - 1) подключены к пятому информационному входу ФПВЯ с координатами (i, j), в устройстве предварительной обработки данных первый управляющий вход подключен к первому управляющему входу блока управления устройством, первый управляющий выход которого подключен к первому управляющему выходу устройства предварительной обработки данных, второй управляющий вход которого подключен к второму управляющему входу блока управления устройством, третий управляющий вход которого подключен к третьему управляющему входу устройства предварительной обработки данных, на второй управляющий выход которого подключен информационный выход триггера, управляющий вход которого подключен к второму управляющему выходу блока управления устройством, третий управляющий выход которого подключен к первому управляющему входу решающего коммутатора, первый управляющий выход которого подключен к четвертому управляющему входу блока управления устройством, четвертый управляющий выход которого подключен к первому управляющему входу специализированного коммутатора для выполнения предварительной обработки координат отрезка, первый управляющий выход которого подключен к пятому управляющему входу блока управления устройством, пятый управляющий выход которого подключен к первому управляющему входу входного буфера, первый управляющий выход которого подключен к шестому управляющему входу блока управления устройством, информационный вход устройства предварительной обработки данных подключен к первому информационному входу входного буфера, второй информационный вход/выход которого подключен к первому информационному входу/выходу специализированного коммутатора для выполнения предварительной обработки координат отрезка, второй информационный вход/выход которого подключен к информационному входу/выходу вспомогательного регистра, а третий информационный выход подключен к информационному входу памяти координат концов отрезка, информационный выход которой подключен к второму информационному выходу устройства предварительной обработки данных и к информационному входу решающего коммутатора, информационный выход которого подключен к информационному входу выходного буфера, информационный выход которого подключен к первому информационному выходу устройства предварительной обработки данных.