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

(51) 5 С 06 Р 15/ ОСУДАРСТВЕННЫО ИЗОБРЕТЕНИЯМРИ ГКНТ СССР КОМИТЕТ ОТКРЫТИЯМ САНИЕ ИЗОБРЕТЕН 2программирования и операционных ем, Цель изобретения - повышение родействия устройства за счет орзации параллельной распределенной ботки информации, Для достижения авленной цели в устройство, соащее информационную ячейку 8 и вляющую ячейку 9, введены 30+1 рмационных ячеек 8 (1)1 - длина ка), организованных в блок 1 клю- (Н ячеек), блок 2 ссылок назад чеек) и блок 3 ссылок вперед, и управляющих ячеек 9, образующих 4 управления. 2 з.п. ф-лы, 4 ил. ов ис быст гани о СССР 1984. СССР 1984. ОВАНИЯпост ль ств15/38ство15/38ДАК ТИР рж ра инфо писей ится т бы вычислиис поль еализации язы 1 АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ РЕСПИСКА(57) Изобретение отностельной технике и можезовано при аппаратной 539795 АИзобретение относится к автоматике и вычислительной технике и можетбыть использовано при аппаратной реализации языков программирования иоперационных систем,Цель изобретения - повьппение быстродействия устройства за счет применения параллельной распределительнойобработки информации. ОНа Фиг. 1 из об раже на струк турнаясхема предлагаемого устройства; нафиг. 2 - функциональная схема информационной ячейки; на фиг. 3 - схемауправляющей ячейки; на фиг. 4 - схема одного элемента списка.Устройство для редактированиясписка содержит блок 1 ключей, блок2 ссылок назад, блок 3 ссылок вперед,блок 4 управления, информационные 20входы 5 , 5 и 5 , информационные выходы 6 6 и 6, выход 7 состояний,информационные 8 и управляющие 9ячейки.Каждая информационная ячейка содержит информационный вход 10, информационный выход 11, первый 12, второй13 и третий 14 управляющие входы, управляющий выход 15, первый 16 и второй 7 регистры, схему 18 сравнения, 30группу 19 элементов И и элемент НЕ 20.Каждая управляющая ячейка 9 содержит первый 21, второй 22 и третий 23входы, первый 24 и второй 25 выходы,элемент ИДИ 26, первый 27 и второй28 элементы И, триггер 29 и элементНЕ 30Синхронизация работы устройстваосуществляется тактовым входом 31.В начальном состоянии на входы 14 40ячеек 8 блоков 2 и 3 подан логическийноль, в регистры 17 ячеек 8 блоказаписаныключи элементов списка, врегистры 7 ячеек 8 блоков 2 и 3 - порядковые номере элементов списка,в регистры 16 ячеек 8 блока 2 - номера предыдущихэлементов списка, а в регистры 16ячеек 8 блока 3 - номера следующихэлементов списка. Порядковые. номераэлементов списка начинаются с единицы, номер предыдущего элемента дляпервого элемента списка и номер сле" .дующего элемента для последнего элемента списка равны нулю,на входы 5и 5 подан логический ноль.Йспольэуется следующий алгоритмудаления элементов иэ списка.1. Отыскивается но ключу удаляемый элемент списка. 2. Находятся его предыдущий и следующий элементы,3. В предыдущем элементе значениеполя ссылки на следующий заменяетсязначением поля ссылки на следующийиз удаленного элемента.4. В следующем элементе значениеполя ссылки на предыдущий заменяетсязначением поля ссылки на предыдущийиз удаляемого элемента,5. Обнуляется ключ удаляемого элемента,Устройство работает следующим образом.На вход 5 подается значение клю 1ча удаляемых элементов списка. Найденные с использованием схем 8 сравнения ячеек 8 блока 1 элементы списка,имеющие требуемое значение ключа врегистрах 17, устанавливают на входах22 ячеек 9 блока 4 единичные потенциалы. Тактовым импульсом на входах23 ячеек 9 блока 4 эти значения записываются в триггеры 29, На элементах26, 27 и 30 ячеек 9 блока 4 производится выделение первого по порядку(-го) ненулевого значения триггеров29, которое с выхода 25 -й ячейки 9поступает на вход 1.4 1-й ячейки 8блока 1, обнуляя значение ключа вэтой ячейке, на вход 12 -х ячеекблоков 2 и 3, Формируя сигналы чтенияномеров соответственно предыдущего иследующего элементов из регистров 16ячеек. 8 блоков 2 и 3 и закрывая группы 19 элементов И этих ячеек.Считанные из регистров 16 значенияЪпроходят по всем ячейкам блоков 2и 3, обеспечивая срабатывание схем18 сравнения ячеек 8 предыдущего(блок 2) и следующего (блок 3) элементов списка. Единичные значения свыходов схем 18 сравнения, поступая(через выход 15 ячеек 8) иа вход 13соответствующих ячеек, производят запись значения регистров 16 удаляемогоэлемента списка в регистры 16 предыдущего и следующего элементов списка,Нри этом сигналы записи следующегоэлемента (блок 3) формируются на схемах 8 сравнения ячеек 8 блока 2, асигналы записи предыдущего (блок 2)на схемах 18 сравнения ячеек 8 блока 3, тем самым обеспечивая выполнение п.З и п.4 алгоритма удаления элементов из списка.В дальнейшем устройство работаетаналогично описанному. Из списка удаляются все элементы, имеющие единичное значение триггера 29, Конец работы наступает тогда, когда на выходе 7 устройства устанавливается нулевой5 потенциал (все триггеры 29 имеют нулевое значение на выходе и .нет элементов с заданным значением ключа) .После этого значение ключа с входа 5Ф снимается, 10 формула изобретения 30 1, Устройство для редактирования списка, содержащее ячейку управления и информационную ячейку, о т л и - ч а ю щ е е с я тем, что, с целью повышения быстродействия за счет организации параллельной обработки информации, в него введены ЗЯ+ инфор мационных ячеек, (Н - максимальное число элементов списка), которые образуют блок ключей, блок ссыпок назад и блок ссылок вперед, по К информационных ячеек в каждом блоке и 11-1 25 управляющих ячеек, все управлаощие ячейки образуют блок управления, каждый -й уровень обработки информации (1,) содержит одну.информационную ячейку блока ключей, одну управляннцую ячейку блока ссылок назад и одну информационную ячейку блока ссылок вперед, управляющий выход которой соединен с вторым управляющим входом информационной ячейки блока ссылок назад -го уровня., первый управляющий вход которой соединен с первым управляющим входом информационной ячейки блока ссылок назад -го уровня, третьим управляющим входом информационной ячейки блока ключей д-го уровня и вторым управляющим выходом ячейки управления д-го уровня, первый управляющий выход которой соединен с первым управляющим входом управляющий 45 ячейки (+1)-го уровня, управляющий выход информационной ячейки д-го уровня блока ключей соединен с вторым управляющим входом управляющей ячейки д-го уровня, первый управлаощий вход 50 которой соединен с первым управляющим входом управляющей ячейки (д)-го уровня, информационные входы управлаощих ячеек -го уровня блоков ключей, ссылок назад, ссылок вперед сое динены соответственно с информационными входами информационных ячеек (д+1)-го уровня блоков ключей, ссылок назад и ссыпок вперед, первый и второй управляющие входы информационнойячейки д-го уровня блока ключей итретий управляющий вход информационной ячейки -го уровня блоков ссыпкиназад и ссылки вперед соединены свходом логического нуля устройства,информационный выход информационнойячейки И-го уровня блоков ссылки назад и ссыпки вперед соединен соответственно с информационным входом информационной ячейки первого уровняблоков ссылки назад и ссыпки вперед,информационный выход информационнойячейки Ю-го уровня блока ключей соединен с информационными выходами устройства, информационный вход информационной ячейки первого уровня блокаключей соединен с информационным входом устройства, первый управляющийвход управляющей ячейки первого уровня соединен с входом логического нуляустройства, управлянзций: выход управляющей ячейки Н-го уровня соединен свыходом состояния устройства, тактовый вход которого соединен с тактовыми входами с первой по Н-ю управляющих ячеек,2. Устройство по п.1, о т л и -ч а ю щ е е с я тем, что информационная ячейка содержит два регистра,схему сравнения, группу элементов Ии элемент НЕ, вход которого соединенс первым управляющим входом ячейки ивходом записи первого регистра, выходкоторого соединен с информационнымвыходом ячейки, выходом группы элементов И, информационным входом первого регистра и первым входом схемысравнения, выход которой соединен суправляющим выходом ячейки, информационный вход которой соединен с выходом группы элементов И, вход управления которой соединен с выходом элемента НЕ, второй управляющий входячейки соединен с входом чтения первого регистра, третий управляющийвход ячейки соединен с входами сброса первого и второго регистров, выходвторого регистра соединен с вторымвходом схемы сравнения.3. Устройство по п,1, о т л и -ч а ю щ е е с я тем, что управляющаяячейка содержит элемент ИЛИ, два элемента И, триггер и элемент НЕ, первыйуправляющий вход ячейки соединен спервым. входом элемента ИЛИ и входомэлемента НЕ, выход которого соединенс первым входом первого элемента И,1539795 Составитель А.Богословскедактор А.Леанина Техред А.Кравчук,рректор Н,король аказ 221 Тираж 553 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Рауюская наб д. 4/5 оизводственно-издательский комбинат "Патент", г. Ужгор Гагарина, 10 выход элемента ИЛИ соединен с первымуправляющим выходом ячейки и вторымвходом первого элемента И, выход которого соединен с вторым управляющимвыходом ячейки, второй управляющийвход которой соединен с первым вхо" дом второго элемента И, выход которого соединен с установочным входом триггера; выход которого соединен с 5вторым входом элемента ИЛИ, тактовый вход ячейки соединен с вторым входом второго элемента И,