Способ записи, считывания и преобразованияинформации

Способ записи, считывания и преобразованияинформации

Иллюстрации

Показать все

Реферат

 

Сава Сое

Сециалиотичеокиз

Реоптбаиа

2833И

Зависимое от авт. свидетельства ¹

Заявлено ОЗ.Ч.1967 (№ 1154897/18-24) с присоединением заявки №

Приоритет

Опубликовано 06.Х.1970. Бюллетень № 31

Дата опубликования описания 7.XII.1970

Кл. 21ат, 37/82

МПК б 11с 7/00

УДК 681,327.6 (088.8) Комитет оо делам изобретений и открытий при Совете Миииотроа

СССР

Автор изобретения

Б, И. Перельман

Институт электронных управляющих машин

Заявитель

СПОСОБ ЗАПИСИ, СЧИТЫВАНИЯ И ПРЕОБРАЗОВАНИЯ

ИНФОРМАЦИИ

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

Эти способы во многих случаях черезвычайно сложны.

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

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

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

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

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

Цепи 8 соединяют УРЛЗ с устройством управления; цепи 9, 10 и 9, 11 — выходные цепи

УРЛЗ. Цепь 8 подключена «о входу дешифратора 5, выходные шины которого соединены

25 цепями 12 — 15 с шинами управления преобразователя 7, цепями 16 и 17 — со входами управления генераторов 2, цепями 18 и 19— со входами управления регистров 6, цепями

12, 20, 14, 21 — со входами управлепия ипдп3п T(3 Горов 4.

283311

Цепи 9, 10 и 9, 11 подключены ко входам регистров б, выходы последних цепями 22— к сигнальным входам генераторов 2, а их выходы цепями 28 связаны с соответствующими шинами матриц 8.

Выходные ш ины матриц соединены цепями

24 с индикаторами 4, а выходы последних— цепями 25 с вертикальными и горизонтальными координатными преобразо вателями 7, где в зависимости от команды происходит логическая обработка данных, полученных с матр иц 8. Выходные цепи 2б и 27 соединены с выходами устройства цепями 28 и 29 и цепями

80 — 88 — со входами регистров б.

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

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

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

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

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

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

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

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

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

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

4

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

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

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

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

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

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

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

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

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

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

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

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

2833ll

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

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

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

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

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

4. Формируют сигналы распространения от

;первого (нижнего) разряда горизонтального преобразователя до первой граничной отметки г1.

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

1 — г2.

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

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

9. Под:пот сигналы ассоциативного чтения ,по строкам 1 — в2. Сигналы на выходных шинах столбцов, содержащих информацию в строках 1 — в2, используют для записи в горизонтальный преобразователь проекции г1 — г2, г1(а) — г2(а).... сечения картины строкaìn 1 — в2 и выполняют операцию 5.

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

11. Подают сигналы чтения из основного и дополнительного столбцов «признаков» и сравнивают коды в них. Если коды совпадают, формируют сигнал управления, исключающий из рассмотрения все строки за пределами проекции, Для этого формируют сигнал распространения от начальной точки проекции в1 до ее конечной точки вк .и сигнал управления, выключающий ячейки остальных разрядов преобразователя (операция «исключение разрядов») .

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

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

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

6 — 9.

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

1 контуров на матрице при записи ооеспечены пробелы (интервалы).

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

Способ записи, считывания и преобразования информации при обращении к ячейкам вычислительных устройств, предназначенных для обраоотки двумерной информации, содержащих координатные преобразователи, отличаюи„ийся тем, что, с целью повышения быст283311 (, Я БЬ Р А 7 7

Р,г г

Составитель А. А. Соколов

Редактор В. Ф. Полещук Техред Л. Я. Ле=ииа Корректор Н. Л. Броис:.ая

Заказ 3533/4 Тира.:. 480 Подписное

ЦНИИПИ Комппета по делам паооретеиии и открьпий lip!I Совеlc,Министров СССР

Москва, К-35, Раушская пао., д. 4j5

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