Устройство для редактирования списка

Устройство для редактирования списка

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при аппаратной реализации языков программирования и операционных систем. Цель изобретения - повышение быстродействия устройства за счет параллельной распределенной обработки информации. Для достижения поставленной цели в устройство, содержащее информационную ячейку 8 и управляющую линейку 9, введены 3N-1 информационных ячеек 8 (N-длина списка), организованных в блок 1 ключей (N ячеек), блок 2 ссылок назад (N ячеек), блок 3 ссылок вперед N-1 управляющих ячеек 9, образующих блок 4 управления, соответствующие им связи. 2 з.п. ф-лы, 4 ил.

.СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 5 С 06 F 15/38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21 ) 4363847 /24-24 (22) 11 . 11 .87 (46) 30.01.90. Бюл. У 4 (72) Г.В.Дворецкий (53) 681. 3 (088.8) (56). Авторское свидетельство СССР

9 1200806, кл. G 06 F 15/38, 1984.

Авторское свидетельство СССР

9 1206806, кл. G 06 F 15/38, ) 984, (54) УСТРОЙСТВО ДЛЯ РЕДАКТИРОВАНИЯ

СПИСКА (57) Изобретение относится к вычислительной технике и может быть использовано при аппаратной реализации язы„„SU„„1539795 А 1

2 ков программирования и операционных систем. Цель изобретения — повышение быстродействия устройства за счет организации параллельной распределенной обработки информации, Для достижения поставленной цели в устройство, содержащее информационную ячейку 8 и управляющую ячейку 9, введены 30+1 информационных ячеек 8 (N — длина списка), организованных в блок 1 ключей (N ячеек), блок 2 ссылок назад (N ячеек) и блок 3 ссылок вперед, и

N-1 управляющих ячеек 9, образующих блок 4 управления. 2 з.п. ф-лы, 4 ил.! 539795

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

Цель изобретения — повьппение быстродействия устройства за счет применения параллельной распределительной обработки информации. !О

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

Устройство для редактирования списка содержит блок ключей, блок

2 ссылок назад, блок 3 ссылок вперед, блок 4 управления, информационные 20 входы 5, 5 и 5, информационные выходы 6,, 6 и 6, выход 7 состояний, информационные 8 и управляющие 9 ячейки.

Каждая информационная ячейка со- 25 держит информационный вход 10, информационный выход 11, первый 12, второй

13 и третий 14 управляющие входы, управляющий выход 15, первый 16 и второй !7 регистры, схему 18 сравнения, группу 19 элементов И и элемент НЕ 20, Каждая управляющая ячейка 9 содержит первый 21, второй 22 и третий 23 входы, первый 24 и второй 25 выходы, элемент ИЛИ 26, первый 27 и второй

28 элементы И, триггер 29 и элемент

HE 30 °

Синхронизация работы устройства осуществляется тактовым входом 31.

В начальном состоянии на входы 14 40 ячеек 8 блоков 2 и 3 подан логический ноль, в регистры 17 ячеек 8 блока записаны ключи элементов списка, в регистры 17 ячеек 8 блоков 2и 3 - порядковые номере элементов списка,в регист- 45 ры !6 ячеек 8 блока 2- номера предьдущих элементов списка, а в регистры 16 ячеек 8 блока 3 - номера следующих элементов списка. Порядковые. номера элементов списка начинаются с единицы, номер предьдущего элемента для первого элемента списка и номер сле- . дующего элемента для последнего элемента списка равны нулю, на входы 5 и 5 подан логический ноль.

Йс ользуется следующий алгоритм удаления элементов as списка.

1. Отыскивается но ключу удаляемый элемент списка.

2. Находятся его предьдущий и следующий элем ен ты.

3. В предьдущем элементе значение поля ссыпки на следующий заменяется значением поля ссылки на следующий из удаленного элемента.

4. В следующем элементе значение поля ссылки на предьдущий заменяется значением поля ссылки на предьдущий из удаляемого элемента.

5. Обнуляется ключ удаляемого элемента.

Устройство работает следующим образом.

На вход 5 подается значение клю1 ча удаляемых элементов списка. Найденные с использованием схем !8 сравнения ячеек 8 блока 1 элементы списка, имеющие требуемое значение ключа в регистрах 17, устанавливают на входах

22 ячеек 9 блока 4 единичные потенциалы. Тактовьм импульсом на входах

23 ячеек 9 блока 4 эти значения записываются в триггеры 29. На элементах

26, 27 и 30 ячеек 9 блока 4 производится вьделение первого по порядку (i-ro) ненулевого значения триггеров

29, которое с выхода 25 i-й ячейки 9 поступает на вход 1.4 i-й ячейки 8 блока 1, обнуляя значение ключа в этой ячейке, на вход 12 1-х ячеек блоков 2 и 3, формируя сигналы чтения номеров соответственно предыдущего и следующего элементов из регистров 16 ячеек. 8 блоков 2 и 3 и закрывая группы 19 элементов И этих ячеек.

Считанные из регистров 16 значения с проходят по всем ячейкам блоков 2 и 3, обеспечивая срабатывание схем

18 сравнения ячеек 8 предьдущего (блок 2) и следующего (блок 3) элементов списка. Единичные значения с выходов схем 18 сравнения, поступая (через выход 15 ячеек 8) иа вход 13 соответствующих ячеек, производят запись значения регистров 16 удаляемого элемента списка B регистры 16 предыдущего и следующего элементов списка.

Нри этом сигналы записи следующего элемента .(блок 3) формируются на схемах 18 сравнения ячеек 8 блока 2, а сигналы записи предыдущего (блок 2) на схемах 18 сравнения ячеек 8 блока 3, тем самым обеспечивая выполнение п.З и п.4 алгоритма удаления элементов из списка.

В дальнейшем устройство работает аналогично описанному. Hs списка уда

1539795 ляются все элементы, имеющие единичное значение триггера 29. Конец работы наступает тогда, когда на выходе 7 устройства устанавливается нулевой

5 потенциал (все триггеры 29 имеют нулевое значение на выходе и .нет элементов с заданным значением ключа) .

После этого значение ключа с входа 5

f снимается, 10

Формула изобретения

1. Устройство для редактирования списка, содержащее ячейку управления и информационную ячейку, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия за счет организации параллельной обработки информации, в него введены 3N+1 инфор- 20 мационных ячеек, (N — максимальное число элементов списка), которые образуют блок ключей, блок ссыпок назад и блок ссылок вперед, по N информационных ячеек в каждом блоке и 11-1 25 управляющих ячеек, все управляющие ячейки образуют блок управления, каждый i-й уровень обработки информации (i - 1,N) содержит одну.информационную ячейку блока ключей, одну управляннцую ячейку блока ссылок назад и одну информационную ячейку блока ссылок вперед, управляющий выход которой соединен с вторым управляющим входом информационной ячейки блока ссылок назад i-го уровня., первый управляющий вход которой соединен с первым управляющим входом информационной ячейки блока ссылок назад i-го уровня, третьим управляющим входом информационной ячейки блока ключей i-го уровня и вторым управляющим выходом ячейки управления i-ro уровня, первый управляющий выход которой соединен с первым управляющим входом управляющий 45 ячейки (i+1)-го уровня, управляющий выход информационной ячейки i-го уровня блока ключей соединен с вторым управляющим входом управляющей ячейки

i-ro уровня, первый управляющий вход 50 которой соединен с первым управляющим входом управляющей ячейки (i-1)-ro уровня, информационные входы управляющих ячеек i-ro уровня блоков ключей, ссылок назад, ссылок вперед сое- 55 динены соответственно с информационными входами информационных ячеек (i+1)-ro уровня блоков ключей, ссылок назад и ссыпок вперед, первый и второй управляющие входы информационной ячейки i-ro уровня блока ключей и третий управляющий вход информационной ячейки i-го уровня блоков ссыпки назад и ссылки вперед соединены с входом логического нуля устройства, информационный выход информационной ячейки N-го уровня блоков ссылки назад и ссыпки вперед соединен соответственно с информационным входом информационной ячейки первого уровня блоков ссылки назад и ссыпки вперед, информационный выход информационной ячейки N-го уровня блока ключей соединен с информационными выходами устройства, информационный вход информационной ячейки первого уровня блока ключей соединен с информационным входом устройства, первый управляющий вход управляющей ячейки первого уровня соединен с входом логического нуля устройства, управлянхций:.выход управляющей ячейки N-ro уровня соединен с выходом состояния устройства, тактовый вход которого соединен с тактовыми входами с первой по Н-ю управляющих ячеек.

2. Устройство по п.l, о т л и— ч а ю щ е е с я тем, что информационная ячейка содержит два регистра, схему сравнения, группу элементов И и элемент НЕ, вход которого соединен с первым управляющим входом ячейки и входом записи первого регистра, выход которого соединен с информационным выходом ячейки, выходом группы элементов И, информационным входом первого регистра и первым входом схемы сравнения, выход которой соединен с управляющим выходом ячейки, информационный вход которой соединен с выходом группы элементов И, вход управления которой соединен с выходом элемента НЕ, второй управляющий вход ячейки соединен с входом чтения первого регистра, третий управляющий вход ячейки соединен с входами сброса первого и второго регистров, выход второго регистра соединен с вторым входом схемы сравнения.

3. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что управляющая ячейка содержит элемент ИЛИ, два элемента И, триггер и элемент НЕ, первый управляющий вход ячейки соединен с первым. входом элемента ИЛИ и входом элемента НЕ, выход которого соединен с первым входом первого элемента И, 1539795

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

Редактор A,Лепнина Техред А.Кравчук, Корректор НЛороль

Заказ 221 Тираж 553 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 выход элемента ИЛИ соединен с первым управляющим выходом ячейки и вторым входом первого элемента И, выход ко торого соединен с вторым управляющим выходом ячейки, второй управляющий вход которой соединен с первым входом второго элемента И, выход котороFo соединен с установочным входом триггера; выход которого соединен с

5 вторым входом элемента ИЛИ, тактовый вход ячейки соединен с вторым входом второго элемента И.