Устройство для редактирования списка Советский патент 1990 года по МПК G06F17/24 

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

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

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

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

Каждая информационная ячейка со- держит информационный вход 10, информационный выход П, первый 12, второй 13 и третий 14 управляющие входы, управляющий выход 15, первый 16 и второй 17 регистры, схему 18 сравнения, группу 19 элементов И и элемент НЕ 20 Каждая управляющая ячейка 9 содержит первый 21, второй 22 и третий 23 входы, первый 24 и второй 25 выходы, элемент ИЛИ 26, первый 27 и второй 28 элементы И, триггер 29 и элемент НЕ 30.

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

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

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

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

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

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

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

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

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

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

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

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

Считанные из регистров 16 значения

ъ

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

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

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

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

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

5 ячейки N-ro уровня блока ключей соединен с информационными выходами устройства , информационный вход информационной ячейки первого уровня блока ключей соединен с информационным вхо0 Дом устройства, первый управляющий вход управляющей ячейки первого уровня соединен с входом логического нуля устройства, управляющий выход управляющей ячейки N-ro уровня соединен с

5 выходом состояния устройства, тактовый вход которого соединен с тактовыми входами с первой по N-ю управляющих ячеек.

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

5 входом записи первого регистра, выход которого соединен с информационным выходом ячейки, выходом группы элементов И, информационным входом первого регистра и первым входом схемы

О сравнения, выход которой соединен с управляющим выходом ячейки, информационный вход которой соединен с выходом группы элементов И, вход управления которой соединен с выходом эле5 мента НЕ, второй управляющий вход ячейки соединен с входом чтения первого регистра, третий управляющий вход ячейки соединен с входами сбро- с-а первого и второго регистров, выход

0 второго регистра соединен с вторым входом схемы сравнения.

3.Устройство поп.1, о т л и - ча ющееся тем, что управляющая ячейка содержит элемент ИЛИ, два эле

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

чей, ссылок назад, ссылок вперед сое- 55 мента И, триггер и элемент НЕ, первый динены соответственно с информацион-управляющий вход ячейки соединен с

ными входами информационных ячеекпервым входом элемента ИЛИ и входом

{i+1 )-го уровня блоков ключей, ссылок элемента НЕ, выход которого соединен назад и ссылок вперед, первый и вто-с первым входом первого элеме нта И,

выход элемента ИЛИ соединен с первым управляющим выходом ячейки и вторым входом первого элемента И, выход кот1 торого соединен с вторым управляющим выходом ячейки, второй управляющий вход которой соединен с первым вхоII«

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

UL.

Фм.З

Т™