СПОСОБ ЗАПИСИ, СЧИТЫВАНИЯ И ПРЕОБРАЗОВАНИЯИНФОРМАЦИИ Советский патент 1970 года по МПК G11C7/00 

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

Эти способы во МНОГИХ случаях чрезвычайно сложны.

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

На фИг. 1 изображена блок-схема устройства для решения логических задач (УРЛЗ), в котором реализуется предложенный способ; на фиг. 2 - контур, выделения которого из м.нол :ества других контуров выполняется предложенным способом.

ииси и считывания 2 и матрицами 3, которое допускает:

а)выполнение логических операций прп записи обращепии непосредственно в матрицах;

б)равную возможность обращения к .матрицам по двум координатам;

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

Устройство содержит также выходные индикаторы 4, дешифратор управления 5, регистры 6, координатные преобразователи 7, выполняющие функцню координатной логн.ки, объединенные входы управления ячеек которых соединены с выходными цепями дешифратора 5, а сигнальные норазрядные входы преобразователей связаны с соответствующнМ1И выходами индикаторов 4.

Цепи 8 соединяют УРЛЗ с устройством управления; цепи 9, УОИ 9, 11 - выходные цепи УРЛЗ. Цепь 8 подключена ко входу дешифратора 5, выходные шииы которого соединены цепями 12-15 с шинами управления преобразователя 7, цепями 16 и 17 - со входами управления генераторов 2, цеиями /8 и 19 - со входами управлен1ня регистров 6, цепями 12, 20, 14, 21 - со входами управления ппдпкято)ов 4.

Цепи 9, 10 и Я 11 подключены ко входам регнстров 6, выходы последних цепями 22 - к сигнальным входам геиераторов 2, а их выходы цепями 23 связаны с соответствующими шинами матриц 5.

Выходные шины матриц соединены ценями 24 с индикаторами 4, а выходы последних - цепями 25 с вертикальными и горизонтальными .координатными преобразощателями 7, где в зависимости от команды происходит логическая обработка данных, полученных с матриц 3. Выходные цепи 26 н 27 соединены с выходами устройства цепями 28 и 29 и цепями 30-33 - со входами регистров 6.

В дальнейшел рассмотрении «картина означает информацию на матрице, элементы памяти которой, соответствующие точкам картины, находятся в состоянии «единица или «нуль. «КОИтур - это множество точек па матрице, каждая из которых имеет две и только две смежные точки, располагающиеся по вертикали и горизонтали.

Множество операций, реализуемых в ячейках матриц УРЛЗ.

1, 2, 3, 4. Логическое сложение, умнолсение, импликация, инвертирование информации в соответствующих ячейках матриц, а также информация в матрицах и вновь записываемых данных.

5.Операция несоответствия для информации в координатных преобразователях и в матрицах, а также информации в двух матрицах УРЛЗ.

6.Сдвиги информации вправо, влево, вверх, вниз.

7.Сдвиги, при которых смещаемая информация логически складывается с исходной.

8.«Непрерывный сдвиг из ячеек в первой матрице 3, содержащих единицу, до границ, определяемых ячейками во второй матрице 3, содержащими единицу, в одном или нескольких направлениях. Возможно логическое сложение исходной и сдвигаемой информации.

9.Логическое сложение информации во всех ячейках строк (столбцов) матриц.

10.«Передача информации на один дискрет из каждой ячейки строки, содержащей единицу, в смежную слева, если в той-нуль, и сохранение состояния первой ячейки, если

в смежной слева - единица (аналогично для столбцов).

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

12. «Распространение по контуру (дискретное или непрерывное), т. е. сдвиг информации из заданных точек (ячеек) матрицы в те и только те из четырех смежных ячеек, которым соответствуют ячейки матрицы, содержащие единицу и логическое сложение исходной и сдвигаемой информации.

Множество операций, реализуемых в координатных преобразователях.

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

1.«Проставление отметок, т. е. запись единиц в разряды преобразователей, соответствующие столбцу или строке с заданными признаками.

2.«Распространение признаков единиц, т. е. запись единиц во все разряды преобразователей, соответствующие строкам или столбцам, расположенным в заданных или определяемых пределах.

3.«Исключение разрядов, т. е. певыполнепие в них операций, реализуемых в остальных ячейках.

4.Получение информации о количестве и местонахождении исключенных разрядов.

5.«Распространение признаков двоек от заданной точки (разряда) до ближайшей граничной отметки и проставление признака только в разряде с граничной отметкой.

6.То же, с проставлением признаков только в разряде на единицу меньше (больше) разряда с проставленной отметкой.

7.Операция распространения с циклическим переносом из первого разряда преобразователей в последний.

8.Формирование информации о выполненных операциях с циклическим переносом.

9.Формирование информации о количестве отметок в ячейках преобразователей.

Рассмотрим реализацию предложенного способа с помощью УРЛЗ на примере решения задачи «Выделение очередного контура произвольной формы из множества контуров, записанных на матрице.

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

Сущность предлагаемого способа заключается в следующем:

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

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

находят горизонтальную проекцию сечения;

находят проекцию на вертикальную ось, соответствующую проекции па горизонтальную ось, затем - проекцию на горизонтальную ось, соответствующую проекции на вертикальную;

проекций. Полученные проекции принадлежат выделяемому контуру;

если проекции пе совпадают, повторяют последние операции.

Последовательность операций, необходимых для реализации рассматриваемого способа.

1.Подают сигналы, соответствующие нулям, для ассоциативного чтения с матрицы УРЛЗ по шинам ассоциативного опроса всех разрядов матр11цы и получают импульсы на выходных шинах тех строк, в которых записана хотя бы одиа единица. С помощью полученных сигналов записывают в вертикальном преобразователе 7 «граиичные отметки, т. е. включают в нем триггеры граничных отметок в разрядах иреобразователя, соответствующих указанным строкам.

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

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

4.Формируют сигналы раонространения от первого (нижнего) разряда горизонтального преобразователя до первой граничной отметки г1.

5.На ячейки горизонтального преобразователя нодают сигнал управления или преобразования. Преобразование заключается в выполнении операции распространения от ячейки, соответствующей точке г, через все следующие за ней ячейки, в которых содержится единица (т. е. до точки г2). Остальные точки стираются.

6.Подают сигналы ассоцнативного чтения но столбцам 1-г2. Сигналы на выходных шинах строк, содержащих информацию в столбцах /-г2, используют для занисн в вертикальный преобразователь проекции , в (а)-в2(а).... сечения картины столбцами .

7.На ячейкИ вертикального преобразователя /подают сигналы улравления, обесиечивающие распространение в .нем от нервого разряда до точки в2. Все остальные точки стираются.

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

9.Подают сигналы ассоцнатнвного чтения ло строкам }-в2. Сигиалы на выходных щинах столбцов, содерл ащих информацию в строках /-в2, иоиользуют для записи в го5 ризонтальный преобразователь проекции г -г2, г (а)-г2(а).... сечения картины строками 1-02 И выполняют онерацию 5.

10.По шинам записи в столбцах г -г2 подают сигналы записи из горизонтального нре10 образо1вателя в строку матрицы, отведенную для заш1Сн проекций. Ранее находившуюся там информацию иереписывают в доиолннтельную строку «признаков и повторяют онерации, указаииые в пп. 6-10, если этн опе15 рации выполнялись один раз.

11.Подают снгналы чтения из основного И дополнительного столбцов «нризнаков и сравнивают коды в них. ЕСЛИ коды совнадают, формируют сигнал управления, исключающий

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

5 преобразователя (операцня «исключенне разрядов) .

12.Преобразуют сигналы на разрядных выходах ячеек иреобразователя в разрядах вк (после очередной операции распростране0 кия) в снгналы заниси, а снгналы записи подают по шинам заннои в соответствующий столбец нризнаков.

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

14.Если коды, указанные в н. 10, не совпадают, повторяют операции, указанные в пп. 6-9.

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

5 пробелы (интервалы).

Решение задачи рассмотренным способом достигается с помощью 15-20 операций. Решенне этой задачи на ЭВМ с поочередным анализом строк картины нриводит к необходимости неребора всех точек информации, причем для анализа каждой точки требуется выполнить 10-30 операций. Таким образом, общее число операций достигает нескольких сот тысяч. Следовательно, ири использовании

5 предложенного способа быстродействия увеличивается на несколько порядков.

Предмет изобретения

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

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

..

rjjfij /7/7 /Tn