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

, 21 ат, 37181154897/18-24) Заявлено ОЗ.Ч.1967с присоединением явкиМГ 1 К 6 11 с 7 оритет Комитет ео делам зобретеиий и открыти при Совете Миииотро СССРК 681,327.6 (088.8) Опубликовано 06.Х,1970. Бюллетень3 Дата опубликовани описания 7.Х 11.1970 Авторизобретения Б, И, Перельман Институт электронных управляющих машиаявитель ОСОБ ЗАПИСИ, СЧИТЬ 1 ВАНИЯ И ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ 2 Известны способы записи, считывания и преобразования информации в двумерной форме с помощью электронных вычислительных машин, связанные с многократными переборами массива информации.Эти способы во многих случаях чрезвычайно сложны.Описываемый способ отличается тем, что попеременно подают сигналы, применяемые для записи, считывания, преобразования,информации и управления, в выбранные ячейки для хранения и преобразования столбцов и строк двумерной информации, а также сигналы управления на ячейки координатных преобразователей, причем выходные сигналы с преобразователей подают по шипам записи, считывания и управления в ячейки для хранения двумерной информации. Это позволяет увеличить быстродействие записи, считывание и преобразование двумерной информации при экономии оборудования,На фиг. 1 изображена блок-схема устройства для решения логических задач (УРЛЗ), в,котором реализуется предложенный способ; на фиг. 2 - контур, выделения которого из множества других контуров выполняется предложенным способом,Устройство для решения логических задач (УРЛЗ) содержит матричное логическое запоминающее устройство 1 г генераторами записп и считывания 2 и матрицами 8, которое допускает:а) выполнение логических операций прн записи обращении непосредственно в матрицах;5 б) равную возможность обращения к матрицам по двум координатам;в) независимое заполнение отдельных матриц и наложение матриц с выполнением прп этом логических операций (сложения, умно жения, пмпликацпи, сдвига, инвертированияи т. и.).Устройство содержит также выходные индикаторы 4, дешифратор управления 5, регистры 6, координатные преобразователи 7, 5 выполняющие функцию координатной логики,объединенные входы управления ячеек которых соединены с выходными цепями дешпфратора 5, а сигнальные поразрядные входы преобразователей связаны с соответствующп- О ми выходами индикаторов 4.Цепи 8 соединяют УРЛЗ с устройством управления; цепи 9, 10 и 9, 11 - выходные цепи УРЛЗ. Цепь 8 подключена ко входу дешифратора 5, выходные шины которого соединены 5 цепями 12 - 15 с шинами управления преобразователя 7, цепями 16 и 17 - со входамп управления генераторов 2, цепями 18 и 19 - со входами управления регистров 6, цепями 12, 20, 14, 21 - со входамп управлепия пцди- О т оол 450 55 60 65 Цепи 9, 10 и 9, 11 подключены ко входам регистров б, выходы последних цепями 22 - к сигнальным входам генераторов 2, а их выходы цепями 23 связаны с соответствующими шинами матриц 3.Выходные шины матриц соединены цепями 24 с индикаторами 4, а выходы последних - цепями 2 б с вертикальными и горизонтальными координатными преобразователями 7, где в зависимости от команды происходит логическая обработка данных, полученных с матриц 3. Выходные цепи 2 б и 27 соединены с выходами устройства цепями 28 и 29 и цепями 30 - 33 - со входами регистров б. В дальнейшем рассмотрении картина означает информацию на матрице, элементы памяти которой, соответствующие точкам картины, находятся в состоянии единица или нуль. Контур - это множество точек па матрице, каждая из которых имеет две и только две смежные точки, располагающие. ся по вертикали и горизонтали,Множество операций, реализуемых в ячейках матриц УРЛЗ,1, 2, 3, 4. Логическое сложение, умножение, импликация, инвертирование информации в соответствующих ячейках матриц, а также информация в матрицах и вновь записываемых данных.5, Операция несоответствия для информации в координатных преобразователях и в матрицах, а также информации в двух матрицах УРЛЗ.б. Сдвиги информации вправо, влево, вверх, вниз.7. Сдвиги, при которых смещаемая информация логически складывается с исходной,8. Непрерывный сдвиг из ячеек в первой матрице 3, содержащих единицу, до границ, определяемых ячейками во второй матрице 3, содержащими единицу, в одном или нескольких направлениях. Возможно логическое сложение исходной и сдвигаемой информации.9. Логическое сложение информации во всех ячейках строк (столбцов) матриц.10. Передача информации на один дискрет из каждой ячейки строки, содержащей единицу, в смежную слева, если в той - нуль, и сохранение состояния первой ячейки, если в смежной слева - единица (аналогично для столбцов).11. Непрерывная передача, отличающаяся от предыдущей тем, что она заканчивается тогда, когда единицы на матрице заполнят без интервалов верхние строки. При этом последняя строка может оказаться неполной.12. Распространение по контуру (дискретное или непрерывное), т, е, сдвиг информации из заданных точек (ячеек) матрицы в те и только те из четырех смежных ячеек, которым соответствуют ячейки матрицы, содержащие единицу и логическое сложение исходной и сдвигаемой инфор м а ции. 5 10 15 20 25 30 35 40 45 4Множество операций, реализуемых в координатных преобразователях.В ячейках координатных преобразователей происходят те же операции, что и в ячейках матриц, и, кроме того, следующие:1. Проставление отметок, т. е. запись единиц в разряды преобразователей, соответствующие столбцу или строке с заданными признаками.2. Распространение признаков единиц, т. е. запись единиц во все разряды преобразователей, соответствующие строкам или столбцам, расположенным в заданных или определяемых пределах.3. Исключение разрядов, т. е, невыполнение в них операций, реализуемых в остальных ячейках,4. Получение информации о количестве и местонахождении исключенных разрядов.5. Распространение признаков двоек от заданной точки (разряда) до ближайшей граничной отметки и проставление признака только в разряде с граничной отметкой.б. То же, с проставлением признаков только в разряде на единицу меньше (больше) разряда с проставленной отметкой.7. Операция распространения с циклическим переносом из первого разряда преобразователеи в последнии.8. Формирование информации о выполненных операциях с циклическим переносом.9. Формирование информации о количестве отметок в ячейках преобразователей.Рассмотрим реализацию предложенного способа с помощью УРЛЗ на примере решения задачи Выделение очередного контура произвольной формы из множества контуров, записанных на матрице,В ходе рассмотрения проекцией контура в матрице на вертикальную либо горизонтальную ось названа логическая сумма информации во всех строках или столбцах матрицы, записанная в соответствующие разряды вертикального либо горизонтального координатного преобразователя. Сечением назван код, получаемый при считывании информации с какой-либо строки (столбца) матрицы и записанный в координатный преобразователь. Сущность предлагаемого способа заключается в следующем:находят точку контура, для которой одна проекция, например горизонтальная находится ближе других к заданному углу матрицы;определяют сечения контуров на матрице по строке, проходящей через указанную точку;находят горизонтальную проекцию сечения; находят проекцию на вертикальную ось, соответствующую проекции на горизонтальную ось, затем - проекцию на горизонтальную ось, соответствующую проекции на вертикальную;сравнивают две последние проекции на горизонтальную ось;если проекции совпадают, исключают из рассмотрения строки и столбцы вне границпроекций, Полученные проекции принадлежатвыделяемому контуру;если проекции пе совпадают, повторяютпоследние операции,Последовательность операций, необходимых для реализации рассматриваемого спо 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(а) сечения картиныстроками 1 - в 2 и выполняют операцию 5.10. По шипам записи в столбцах г 1 - г 2 подают сигналы записи из горизонтального преобразователя в строку матрицы, отведеннуюдля записи проекций, Ранее находившуюсятам информацию переписывают в дополнительную строку признаков и повторяют операции, указанн в пп, 6 - 10, если этп операции выполнялись один раз.11. Подают сигналы чтения из основногои дополнительного столбцов признаков исравнивают коды в них. Если коды совпадают,формируют сигнал управления, исключающийиз рассмотрения все строки за пределамипроекции, Для этого формируют сигнал распространения от начальной точки проекции в 1до ее конечной точки вк .и сигнал управления,выключающий ячейки остальных разрядовпреобразователя (операция исключение разрядов) .12. Преобразуют сигналы на разрядных выходах ячеек преобразователя в разрядах в 1 -вк (после очередной операции распространения) в сигналы записи, а сигналы записи подают по шипам записи в соответствующийстолбец признаков.13, Формируют сигналы исключения из операций для столбцов находящихся за границами горизонтальной проекции.14. Если коды, указанные в п. 10, не сов,падают, повторяют операции, указанные в пп.6 - 9.Рассмотренный способ пригоден для контуров произвольной формы, записанных, например, на матрице в произвольном порядке. Однако для упрощения примера здесь разобранслучай когда между проекциями соседнихконтуров на матрице при записи ооеспеченыпробелы (интервалы).Решение задачи рассмотренным способомдостигается с помощью 15 - 20 операций. Решение этой задачи на ЭВМ с поочередныманализом строк картины приводит к необходимости перебора всех точек информации,причем для анализа каждой точки требуетсявыполнить 10 - 30 операций. Таким образом,общее число операций достигает несколькихсот тысяч. Следовательно, при использованиипредложенного способа быстродействия увеличивается на несколько порядков,5 10 15 20 25 30 35 40 45 50 55 60 65 Предмет изобретенияСпособ записи, считывания и преобразования информации при обращении к ячейкам вычислительных устройств, предназначенных для обраоотки двумерной информации, содержащих координатные преобразователи, отличаюи 1 ийся тем, что, с целью повышения быст283311 БЯа д тР,г г оставитель А. А. СоколТехред Л, Я, Ле:ии Редактор лещук рректор Н. Л. Бронеа Заказ 3533/4 Тира:и 480ЦИИИПИ Комппета по делам наооретении н открьпий прнМосква, Ж, Раушская нао., д. 4/5 Подписное вос Министров СССРТипография, пр. Сапунова,родействия записи, считывания и преобразования информации, а также с целью экономии оборудования, попеременно подают сигналы, применяемые для записи, считывания, преобразования и управления, в выбранные ячейки для хранления и преобразования столбцов и строк двумерной информации, а также сиг палы управления на ячейки координатны: преобразователей, причем выходные оигналь с преобразователей подают по шипам записи 5 считывания и управления в ячейки для хранения двумерной информации.