Устройство для сжатия и развертывания данных

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИН о) Я ИСАНИЕ ИЗОБРЕТ ническ манов,няССР 198 54) УСТРОЙСТВ ЫВАНИЯ ДАННЫХ 57) Изобретен ительной техн ычис- льзоотносится ке и может ис ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельств9 934523, кл. С 08 С 15/06,Авторское свидетельствоУ 991471, кл, С 08 С 15/06,0 ДЛЯ СЖАТИЯ И РАЗВЕ ься в системах хранения, поиска и обработки данных Изобретение позволяет повысить информативность устройства. Устройство работает в режимах сжатия данных, развертывания данных и коррекции. Код режима записывается внешней ЭВМ в регистр 14. Управление работой устройства осуществляется по микропрограмме, хра щейся в блоке 21 управления. Устроиство для сжатия и развертывания данных содержит регистры 1-4, 14, блоки 5,6 сравнения, мультиплексоры 7, 9,20, блоки 8, 19 памяти, иптну 10 данных, счетчики 11-13, 17, 18, дешифратор 15 и блок 16 управления. 3 ил. 1 табл.18 17 1359мент НЕ 7 б и на адресный вход блока77 поступает содержимое поля 754 регистра 75,Следовательно, если содержимоесчетчика 18 не равно нулю, то перваямикрокоманда блока 99 передает управление его второй микрокоманде, которая содержит в полях 75 - 75 соотгветственно код условия равенствасодержимого счетчика 11 нулю, адреспервой микрокоманды блока 100 и адрес первой микрокоманды блока 101.Следующий тактовый сигнал считывает эту микрокоманду из блока 77 в регистр 75, она реализуется точно также, как и вторая микрокоманда бло. -ка 85.Блок 100 служит для занесения врегистр 3 очередной сжатой фразы иполучает управление от второй микрокоманды блока 99. Он состоит из трехмикрокоманд безусловного перехода,в поле 75 каждой из которых содержится адрес следующей за ней микрокоманды. Очередные три тактовых сигнала последовательно считывают этимнкрокоманды из блока 77 в регистр75. Первая, вторая и третья микрокоманды блока 100 содержат в поле 75,коды, по которым возбуждаются соответственно четвертый, двадцать вто.рой и первый выходы дешифратора 73,сигналы с которых вызывают соответственно чтение однойсжатой фразыиз блока 8 памяти, прием этойфразыв регистр 3 и запись в счетчик 11длины регистра 3.После блока 100 следует блок 101,состоящий из семи микрокоманд безусловного перехода, в поле 75каядойиз которых содержится адрес следующейза ней микрокоманды. Блок 101 служитдля восстановления одного несокращенного символа развертываемой фразы,Очередпые семь тактовых сигналов.последовательно считывают первую -седьмую микрокоманды блока 101 изблока 77 в регистр 75. Эти микрокоманды содержат в поле 75, коды, покоторым возбуждаются соответственнодвадцать шестой, восьмой, четырнадцатый, двадцать седьмой, двенадцатый,девятый и десятый выходы дешйфратора73, сигналы с которых соответственно,вызывают передачу в мультиплексор 7старшего байта регистра 3, сдвиг содержимого регистра 1 на один байтвлево с приемом содержимого мульти 791 плексора 7, уменьшение содержимого счетчика 12 на единицу, уменьшениесодержимого счетчика 18 на единицу,5передачу в мультиплексор 7 содержимого регистра 4, сдвиг содержимогорегистра 3 на один байт влево с приемом содержимого мультиплексора 7 иуменьшение содержимого счетчика 11 .на единицу.Последняя микрокоманда блока 101возвращает управление к первой микрокоманде блока 99. Таким образом, врезультате циклического выполнения15 блоков 99 и 100 в регистре 1 восстанавливается сжатая форма развертываемой фразы, что совместно с восстанов"ленной блоками 97 и 98 левой цепочкой, сокращенных символов образует развер 20 нутую фразу,Однако как и при сжатии, когдадлина 1 развернутой фразы меньше,чем длина и регистра 1, пстаршихбайтов регистра 1 занимаются пробела 25 ми, т,е. развернутая фраза занимаетнеправильное положение в регистре 1.Так как каждая развернутая фраза является базовой для следующей фразы,подлежащей развертыванию, то коррекЗО тировка ее положения является необходимой, Для этого используются блоки 102 и 103, Блок 102 состоит изодной микрокоманды условного перехода, в полях 75, 75, 75 4 которойсодержатся код условия обнулениясчетчика 12 адрес первой микрокоманды блока 104 и адрес первой микрокоманды блока 103. Она реализуетсятаким же образом, как и блок 89. Блбк103 аналогичен блоку 90, его последняя микрокоманда возвращает управление блоку 89. Таким образом, циклическое выполнение блоков 89 и 90 дообнуления счетчика 12 приводит к то 5 му, что Развернутая фраза занимаетправильное положение в регистре 1.Блок 104 получает управление отблока 102 в том случае, если содержимое счетчика 12 равно нулю. Он содер5 О жит две микрокоманды безусловногоперехода и одну микрокоманду условного перехода.Каждая из первых двух микрокомайдблока 102 в поле 754 содержит адрес55 следующей за ней микрокоманды Очередные два тактовых сигнала последовательно считывают эти микрокомандыиз блока 77 в регистр 75. Первая ивторая микрокоманды содержат в поле19135979175 коды, по которым возбуждаютсясоответственно двадцать восьмой ивосемнадцатый выходы дешифратора 73, . сигналы с которых вызываютсоответ 5ственно запись содержимого регистра1 через мультиплексор 9 в блок 8 памяти и уменьшение содержимого счетчика 13 на единицу.Иикрокоманда условного перехода 10 блока 92 содержит в полях 75- 75Ф соответственно код условия обнуления счетчика 13 (условие развертывания всех фраз), адрес первой микрокомандц блока 105 и адрес первой микроко" 15 манды блока 96. Она реализуется таким же образом, как и последняя микрокоманда блока 91. Следовательно, если содержимое счетчика 13 не равно нулю, то осуществляется возврат к 20 блоку 96 (начало развертывания следующей фразы), в противном случае - к блоку 105.Блок 105 состоит иэ двух микрокоманд безусловного перехода, в поле 15 75 каждой из которых содержится адрес следующей за ней микрокоманды. Очередные.два тактовых сигнапа после- в довательно считывают эти микрокоман- у ды из блока 77 в регистр 75. Первая .ЗО и вторая микрокоманды содержат в по- ч ле 75, коды,по которым соответствен- с но воэбуждаются двадцатый и двадцать девятый выходы дешифратора 73, сигна- с лы с которых вызывают соответственно сброс регистра 14 режима и запрос к б прерыванию, поступающий в ЭВИ как д извещение об окончании развертывания. с После блока 99 осуществляется переход к блоку 93 (рассмотрен выше). 40 чЭВМ, получив сигналы прерывания, разгружает блок 8 памяти. Поля ре- Угистра 75 должны иметь длины: полев 75, - 5 бит для кодирования 29 управ- р ляющих сигналовр Одной пустой микро 4 операции и сигнала "Останов", поле н 75 - 4 бита для кодирования одного дФпустого условия и десяти обяэательв ных условий, поля 75 и 75 - по 7 битов для кодирования адресов 72 раз в личных микрокоманд, Следовательно, У длина регистра 75 каздой микрокоманды составляет 23 разряда. , д 20 Формула изобретения Устройство для сжатия и развертывания данных, содержащее блок управления, первый - восьмой выходы которого соединены соответственно сосчетным входом первого счетчика,счетным управляющим входом второгосчетчика, первым управляющим входомпервого регистра, первым н вторым управляющими входами второго регистра,первым и вторым управляющими входамитретьего регистра, четвертый регистр,первый выход которого и выход первого счетчика соединены соответственнос первым и вторым вхопами блока управления, и первый блок памяти, о т"л и ч а ю щ е е с я тем, что,с целью повышения информативности устройства, в него введены пятый регистр,мультиплексоры, второй блок памяти,третий - пятый счетчики, блоки сравнения, шина данных и дешифратор, адресные, первый и второй управляющиевходы дешифратора являются соответственно адресными, первым и вторым управляющими входами устройства, первыйи второй выходы дешифратора соединены соответственно с вторым управляющим входом первого регистра н управляющим входом пятого регистра, третийыход дешифратора соединен с первымиправляющими входами первого мультиплексора и первого блока памяти,етвертый выход дешифратора соединенвторым управляющим входом первого блока памяти, пятый выход дешифратораоединен с первыми управляющими вхоами второго мультиплексора и второголока памяти, шестой - восьмой выходыешифратора соединены соответственновторым управляющим входом второго блока памяти и управляющими входамиетвертого регистра и третьего счетчика, третий и четвертый входы блокаправления являются соответственноходом пуск и тактовым входом устойства, девятый - двадцать четверый выходы блока управления соедннеы соответственно с управляющим вхо"ом первого счетчика, первым - четертым управляннцимн входами третьего мультиплексора, третьим управляющимходом первого блока памяти, третьимправляющнм входом второго блока памяти, суммирующим и вычнтающим вхоами четвертого счетчика, суммирующим и вычитающнм входами пятого счетчика, входом установки в "0" четвертого регистра, счетным входом третьего счетчика и являются первым, вторым и третьим выходами устройства, двадцать пятый выход блока управле 21221359791ния соединен с вторым управляющимвходом первого мультиплексора и четвертым управляющим входом первогоблока памяти, двадцать шестой выходблока управления соединен с третьимуправляющим входом первого мультиплексора и пятым управляющим входомпервого блока памяти, двадцать седь"мой выход блока управления соединен 10с вторым управляющим входом второгомультиплексора и четвертым управляющим входом второго блока памяти,двадцать восьмой выход блока управления соединен с входами установки 15в "0" четвертого и пятого счетчиков, .двадцать девятый выход блока управления соединен с управляющими входами четвертого и пятого счетчиков,выход третьего счетчика, второй и 20третий выходы четвертого регистра,первый выход четвертого счетчика,первый выход пятого счетчика, выходпервого блока сравнения, выход второго блока сравнения и выход второгосчетчика соединены соответственно спятым - двенадцатым входами блокауправления, первые информационныевходы первого регистра, первогомультиплексора, второго мультиплек- З 0сора, информационные входы четвертого регистра, пятого регистра, тре-тьего счетчика, первые выходы перво"го блока памяти и первые выходывторого блока памяти объединены соответственно и подключены к шине данных,псрвые выходы йервого регистра подключены к соответствующим первымвходам первого блока сравнения ипервым информационньщ входам третье го мультиплексора, первые выходывторого регистра соединены с соответствующими вторыми входами первогоблока сравнения, первыми, входами второго блока сравнения и вторыми информационными входами третьего мультиплексора, вторые выходы второго регистра, первые выходы третьего регистра и выходы пятого регистра соединены соответственно с соответству",ющими вторыми входами второго блокасравнения, третьими и четвертыми информационными входами третьего мультиплексора, выходы третьего мульти-.плексора соединены с соответствующими вторыми информационными входамипервого регистра и первыми информационными входами второго и третьегорегистров, вторые выходы первого итретьего регистров соединены соответственно с соответствующими вторымии третьими информационными входамипервого мультиплексора, выходы которого соединены с соответствующимиинформационными входами первого блокапамяти, вторые выходы которого соединены с соответствующими вторыми информационными входами второго и третьего регистров, выходы четвертогои пятого счетчиков соединены с соответствующими вторыми информационнымивходами второго мультиплексора, выходы которого соединены с соответствующими информационньии входамивторого блока памяти, вторыевыходы которого соединены с соответствующими информацианньми входами четвертого и пятого счетчиков,1359791 ЩРР аказ 6154/50 Тираж 544 Подпис ное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5(последовательность42 символов) 13597Изобретение относится к вычислительной технике н может испольэовать"ся в системах хранения, поиска и обработки данных,Целью изобретения является повышение информативности устройства.На Фиг.1 представлена структурнаясхема устройства для сжатия и развертывания данных; на Фиг.2 - Функциональная схема блока управления,"на фиг.З - блок-схема микропрограммыработы блока управления.Устройство для сжатия и развертывания данных содержит (фиг,1) первый - третий и пятый регистры 1-4,первИй и второй блоки 5 и 6 сравнения, третий мультиплексор 7, первыйблок 8 памяти, первый мультиплексор9, шину 10 данных, первый - третий 20счетчики 11-13, четвертый регистр 14режима, дешифратор 15, блок 16 управления, четвертый и пятый счетчики,17 и 18, второй табличный блок 19памяти, второй мультиплексор 20, выходы 21-49 и входы 50-61 блока управления.Блок управления содержит (фиг.2)элементы И 62-71, элемент ИЛИ 72,дешифраторы 73 и 74, регистр 75, элемент НЕ 76, блок 77 постоянной памяти, триггер 78 и элемент И 79. НаФиг.З позициями 80-105 обозначеныблоки микропрограммы работы блока управления, 35Блок 77 постоянной памяти предназначен для хранения микропрограммы.Регистр 75 состоит из полей 5-75,служащих соответственно для заданиякода микрооперации, кода проверяемого условия, адреса перехода при нулевом значении проверяемого условия и адреса перехода при единичном значении проверяемого условия.Устройство работает под управлением ЭВМ (например, микро-ЭВМСМ) с трехшинной архитектурой. Теоретическое обоснование работы устройства следующее.Каждая сжимаемая фраза состоит из трех цепочек: цепочки левых символов, повторяющейся в базовой фразе, цепочки средних символов, не повторяющейся в базовой фразе, и цепочки правых пробелов, Путем посимвольного сравнения сжимаемой фразы ф; с базовой фразой(ф;, или ф, )определяют длину 1, цепочки повторяющихся символов. Оставшаяся цепочка, состоящая из 1 существенных символов фразы ф; (без учета цепочки правых пробелов), рассматривается как сжатая Форма ф Фразы ф , Таким образом, в реэульта 1те сжатия из каждой Фразы отбрасывается цепочка левых символов, повторяющаяся в базовой для нее фразе, и цепочка правых пробелов. Однако для последующего восстановления необс ходимо сохранить не только ф , но и 1., и 1.Поэтому в результате сжатия массива Фраз формируются таблица Ь = (1 1);, в , и последовательность Р = = ( ф;) ;, где И - число сжатых Фраз. В таблице показан пример сжатия и развертывания данных, состоящих из 15 Фраз. В качестве базовой для пер- вой фразы принята фраза ф, состоящая только из пробелов (пробелы изображены точками).1359791 Продолжение таблицы Ь ЕСО ЕС., ЕСЕСЕСО 6 О НАИРИ вНАИРИ-1 НАИРИ-2 1 О 13 14 68 байтов 8 байтов НАИРИ, .135 байтов 42 байта Всего Посимвольное сравнение первой 25фразы Ф с нулевой фразой ф показывает, что Ф не имеет цепочку совпа 11дающих левых символов и поэтому 1=О. Все шесть существенных символовф рассматриваются как сжатая формаофразы и поэтому 1 " =6, Ф =(М -6000 ),фсобразует первые шесть символов последовательности У, Зятем фраза фсравнивается с фразой ф.и устанавливается, что Ф имеет цепочку "М- ) сов- З 5падающих символов и поэтому 1 =2. Ос 21тавшаяся. цепочка четырех существенныхсимволов фразы фгпринимается какее сжатаЯ фоРма, т.е. Фг =(7000 ) образует следующие четыре символа по-40следовательности. Таким же образомсжимаются все остальные фразы, в результате чего формируются таблицаЬ и последовательность Р,Развертывание производится следующим образом. В качестве базовой дляфразы ф принимается такая же фраза1ф, как и при сжатии (в рассматриваемом примере цепочка пробелов).Для развертывания первой фразы 5 Офиспользуются 1 и 1. Так как 1г=6 показывает, что шесть первых символов последовательности Е принадлежат фразе Ф т.е, ф, =М).Для развертывания второй фразы ггиспользуются 1 1 и 1 , ТДК как 1гг=2, то первые два символа фразы фг совпадают с аналогичными символами фразы ф т.е, Фг(М-), Поскольку 1 г =4, то последующие четыре символа фразы ф содержатся в последовательности Г, Этими символами являются Ф =(7000 ). Следовательно, Фг = ф". Ф= =(М - 7000), Таким образом развертываются все остальные фразы.Устройство работает в трех режимах: сжатие, коррекция, развертывание. Режим работы устройства задаетсяЭВМ перецачей трехразрядного унитарного кода режима в регистр 14 (фиг.1),выходы которого соединены с соответствующими входами блока 16 управления (фиг. 1 и 2) .Блок 16 управления вырабатываетпоследовательность сигналов в соответствии с микропрограммой, блок-схема которой приведена на фиг,3. Формат микрокоманд и назначение их отдельных полей полностью совпадают сформатом и назначением полей регистра75 микрокоманды. Так как текущаямикрокоманда хранится в регистре 75,то поля 75, - 754 будут рассматриваться как части регистра 75, если речьидет о нем, или как части текущеймикрокоманды, если речь идет с ней,В микропрограмме используются микрокоманды двух -типов,Микрокоманда условного переходасодержит код пустой микрооперации вполе 75,1, по ней дешифратор 73 не5 135979 возбуждается. Поэтому при описании такой микрокоманды поле 75, и дешифратор 73 упоминаться не будут.Мцкрокоманда безусловного перехо 5. да содержит код пустого условия в поле 75 , по ней дешифратор 74 не возбуждается. Кроме того, из-за единственности возможной следующей микрокоманды одно из полей адреса та кой микрокоманды-не используется.На фиг.2 это поле 75 , Поэтому при выполнении такой микрокоманды ни один из элементов И 62-71, а также элемент ИЛИ 72 не срабатывают, а сраба тывает только элемент НЕ 76, который соединяет поле 75 регистра 75 с адресным входом блока 77 памяти. Таким образом, при выполнении микрокоманды безусловного перехода в качестве ад" реса следующей микрокоманды всегда выбирается содержимое поля 75 ре" гистра 75, Поэтому при описанйи такой микрокоманды поля 75 и 75 ,дешифратор 74 и цепи выбора адреса следую щей микрокоманды упоминаться не будут.Работа устройства задается микропрограммой, блок-схема которой представлена на фиг3. Блоки 80 и 93 являются соответственно началом и кон- ЗО цом микропрограммы, а блок 81 содержит три микрокоманды условного перехода:если сжатие, то переход к блоку 82;если коррекция, то переход к блоку 94;если развертывание, то переход кблоку 95;иначе возврат к блоку 81.В исходном состоянии регистр 75 4 О микрокоманды находится в нулевом состоянии (код пустой микрооперации в поле 75, код пустого условия в поле75 , нулевые адреса в полях 75 и75 4), Блок памяти содержит микропрограмму работы устройства в режимахсжатие, коррекция, развертывание(микропрограмма размещается начинаяс нулевой ячейки).Сигналом "Пуск" триггер 78 устанавливается в единичное состояниеи разрешает прохождение тактовых символов через элемент И 79 в блок 77памяти.Первый тактовый сигнал считываетпервую микрокоманду блока 81 (фиг.3)с нулевой ячейки блока 77 в регистр75. Эта микрокоманда условного перехода содержит в поле 75код условия есжатия, в поле 75 адрес первой микрокоманды блока 82, в поле 75 адрес второй микрокоманды блока 81, При этом возбуждается первый выход дешифратора 74, соединенный с первым входом элемента И 62, второй вход которого соединен с выходом сжатиярегистра 14 режима. Если выход "Сжатие" регистра 14 возбужден, то срабатывают элементы И 62, ИЛИ 72, выходной сигнал последнего передает содержимое поля 75 регистра 75 на адресный вход блока 77 памяти,В противном случае элементы И 62 ИЛИ 72 не срабатывают и выходной сигнал элемента НЕ 76 передает содержимое поля 754 регистра 75 на адресный вход блока 77.Второй тактовый сигнал считывает из блока 77 в регистр 75 первую микрокоманду блока 82 (начало сжатия) или вторую микрокоманду блока 81 в зависимости от того, адрес какой из указанных микрокоманд бып передан на адресный вход блока 77 памяти.Вторая микрокоманда блока 8 1 содержит в полях 75 - 75соответственно код условия Коррекция", адрес . первой микрокоманды блока 94 и адрес третьей микрокоманды блока 81. При этом дешифратор 74 возбуждает свой второй выход, соединенный с первым входом элемента И 63, второй вход которого соединен с выходом "Коррекция" регистра 14. Если выход "Коррекция" регистра 14 возбужден, то срабатывают элементы И 63, ИЛИ 72, на адресный вход блока 77 передается содержимое поля 75 з регистра 75. В противном случае сигнал с выхода элемента НЕ 76 передает на адресный вход блока 77 содержимое поля 75 регистра 75.Третий тактовый сигнал считывает из блока 77 в регистр 75 первую микрокоманду блока 94 (начало коррекции) или третью микрокоманду блока 81.Третья микрокоманда блока 81 содержит в полях 75- 75 соответственно код условия "Развертыгание", адрес первой микрокоманды блока 95 и адрес первой микрокоманды блока 81. При этом дешифратор 74 возбуждает свой третий выход, соединенный с, первым входом элемента И 64, второй вход ко торого соединен с выходом "Рарвертывание" регистра 14Если этот выход возбужден, то срабатывают элементы И 64, ИЛИ 72, на адресный вход блока77 передается содержимое поля 75 ре 3 гистра 75, В противном случае сигнал с выхода элемента НЕ 76 передает на адресный вход блока 77 содержимое ,поля 754. регистра 75.Таким образом, блок 16 управления реализует блок 81 микропрограммы, циклически опрашивая выходы регистра 14 режима, и при обнаружении единич ного сигнала на одном из них переходит к реализации соответствующей вет-. ви микропрограммы (фиг,3).В режиме сжатия ЭВМ загружает в блок 8 памяти массив фраз, подлежащих 15 сжатию, в регистр 1 - базовую фразу, в регистр 4 - пробел, в счетчик 13 количество фраз в блоке 8 памяти, в регистр 14 - код режима сжатия.Блок 16 управления, получив от ре О гистра 14 сигнал о режиме сжатия, приступает к реализации блоков 82-92 микропрограмм работы устройства.Блок 82 (начало реализации режима "Сжатие" ) состоит из одной микроко манды безусловного перехода, в поле 75 которой содержится код микрооперации записи данных (в байтах) регистра 3 в счетчик 11, в поле 75 адрес первой микрокоманды блока 83. 30Первый тактовый сигнал (с момента начала режима сжатия) считывает эту микрокоманду из блока 77 в регистр 75, после чего начинается ее реализация. 35При этом возбуждается первый выход дешифратора 73, сигнал с которого записывает в счетчик 11 код длины регистра 3.Блок 83 представляет собой после-о 4 О довательность из четырех микрокоманд безусловного перехода, в поле 75каждой из них содержится адрес следующей за ней микрокоманды. Второй - пятый тактовые сигналы считывают в 45последовательном порядке соответственно первую - четвертуюмикрокоманды блока 83.Первая, вторая, третья и четвертая микрокоманды блока 83 содержат в по О ле 75 коды, по, которым возбуждаются соответственно второй, третий, четвертый и пятый выходы дешифратора 73, сигналы которых вызывают сброс счетчиков 17 и 18, запись в счетчик 12 длины регистров 1 и 2, чтение иэ блока 8.памяти очередной (первой в начале) фразы и прием этой фразы в ре-.гистр 2. После блока 83 следует блок 84, состоящий из одной микрокоманды условного перехода, Эта микрокоманда считывается из блока 77 в регистр 75 шестым тактовым сигналом, Она содержит в поле 75код условия совпадения старших байтов регистров 1 и 2, а в полях 75 и 75 - адреса первых микрокоманд блоков 88 и 85 соответственно.По этой микрокоманде возбуждается четвертый выход дешифратора 74, который соединен с первым входом элемента И 65, второй вход которого соединен с выходом блока 5 сравнения. Ес- ли содержимые старших байтов регистров 1 и 2 совпадают, то срабатывают блок 5 сравнения, элемент И 65 и элемент ИЛИ 72, в результате чего на адресный вход блока 77 передается содержимое поля 75 з регистра 75, впротивном случае срабатывает только элемент НЕ 76 и на адресный вход блока 77 поступает содержимое поля 75регистра 75, Таким образом, после блока 84 выполняется блок 88 или 85.Все следующие блоки микропрограммы получают управление условными переходами (непосредственно или косвенно). В связи с этим закреплять за конкретным блоком конкретные тактовые сигналы невозможно. Поэтому далее будем пользоваться выражениями очередной тактовый сигнал, следующий тактовый сигнал.Блок 85 состоит из двух микрокоманд условного перехода. Если блок 85 получает управление от блока 84 или 87, то очередной тактовый сигнал считывает из блока 77 в регистр 75 его первую микрокоманду, в поле 75 которой содержится код условия Регистр 2 пуст", в поле 75 з - адрес первой микрокоманды блока 89, в поле 75- адрес второй микрокоманды блока 85.По этой микрокоманде возбуждается пятый выход дешифратора 74, который соединен с первым входом элемента И 66, второй вход которого соединен с выходом блока 6 сравнения. Если регистр 2 пуст, то срабатывают блок 6 сравнения, элемент И 66 и элемент ИЛИ 72, в результате чего на адресный вход блока 77 передается содержимое поля 75регистра 75. В противном случае срабатывает элемент НЕ 76 и55 9135979 на адресный вход блока 77 поступает, содержимое поля 75 . Следовательно, если регистр 2 не пуст, то следующим тактовым сигналом считывается из блоФ 5 ка 77 в регистр 75 вторая микрокоманда блока 85. Она содержит в поле 75код условия обнуления счетчика 11, в полях 75 и 75 - соответственно адреса первых микрокоманд блоков 86 1 О и 87. По этой микрокоманде возбужцается шестой выход дешифратора 74, соединенный с первым входом элемента И 67, второй вход которого соединен с выходом счетчика 11, Если со Б держимое счетчика 11 равно нулю, то срабатывают элементы И 67, ИЛИ 72, в результате чего содержимое поля 75 з регистра 75 передается на адресный вход блока 77. В противном случае срабатывает элемент НЕ 76 и на адрес-, ный вход блока 77 поступает содержимое поля 75 4.Блок 86 предназначен для разгрузкирегистра 3, когда он полностью запол Б нен и требуется место для нового символа.Блок 86 состоит из двух микрокоманд безусловного перехода в поле 75, в каждой из которых содержится адрес следующей за ней микрокоманды, Очередные два тактовых сигнала (после передачи блоку 86 управления) последовательно считывают из блока 77 в регистр 75 первую и вторую микроко 35 манды этого блока, содержащие в поле 75 соответственно коды, возбуждающие шестой и первый выходы дешифратора 73, сигналы с которых соответст- венно вызывают запись содержимого Ре О гистра 3 через мультиплексор 9 в блок 8 памяти и запись в счетчик 11 кода длины регистра 3.За блоком 86 следует блок 87, состоящий из восьми микрокоманд безусловного перехода, в поле 75каждого из которых содержится ацрес следующей за ней микрокоманды, Очередные восемь тактовых сигналов последовательно . считывают иэ блока 77 в регистр 75 первую - восьмую микрокоманды блока 87 содержащие в поле 75 коды, возбуждающие соответственно седьмой в четырнадцатый выходы дешифратора 73, сиг налы с которых вызывают передачу старшего байта регистра 2 в мультиплексор 7, сдвиг содержимого регистра 2 на один байт влево с приемом содержимого мультиплексора 7, сдвиг со 11 Одержимого регистра 3 влево и приемсодержимого мультиплексора 7, умень"шение на единицу содержимого счетчика 11, увеличение содержимого счетчика 18 на единицу, передачу содержимого регистра 4 на мультиплексор 7,Фсдвиг содержимого регистра 2 влевос приемом содержимого мультиплексора7, уменьшение содержимого счетчика12 на единицу,Последняя микрокоманда блока 87осуществляет переход (возврат) к блоку 85,Таким образом, каждый цикл реализации блоков 85 и 87 приводит к пересылке одного неизбыточного символасжимаемой фразы из регистра 2 в регистры 1 и 3, В результате этогосжатая форма сжимаемой фразы параллельно накапливается в регистрах 1и 2, При этом содержимое регистра 1вместе с цепочкой избыточных символов сжимаемой фразы (формируетсяблоками 84,88) рассматривается какновая базовая фраза, а содержимоерегистра 3 рассматривается как очередная цепочка символов, сформированная в результате сжатия фраз. Блок 88 может следовать толькопосле блока 84 и служит для сокращения избыточных символов сжимаемойфразы. Он состоит из шести микрокоманд безусловного перехода, в поле75 каждой из,которых содержитсяадрес следующей за ней микрокоманды.Очередные шесть тактовых сигналов(после передачи блоку 88 управления)последовательно считывают из блока77 в регистр 75 первую - шестуюмикрокоманды этого блока, в поле 75 которых содержатся коды, возбуждающиесоответственно пятнадцатый, восьмой,шестнадцатый, двенадцатый, тринадцатый и четырнадцатый выходы дешифратора 73, сигналы с которых вызываютсоответственно передачу старшего байта регистра 1 в мультиплексор 7,сдвиг содержимого регистра 1 на одинбайт влево с приемом содержимого .мультиплексора 7, увеличение на единицу содержимого счетчика 17, передачу содержимого регистра 4 в мультиплексор 7, сдвиг содержимого регистра 2 на один байт влево е приемом содержимого мультиплексора 7,уменьшение на единицу содержимогосчетчика 12, 13597Последняя микрокоманда блока 88 осуществляет передачу (возврат) к блоку 84.Каждый цикл реализации блоков 845 и 88 приводит к выталкиванию одного избыточного символа сжимаемой Фразы из регистра 2 в регистр 1, тем самым происходит сокращение одного символа сжимаемой фразы и накопление одного 10 символа цепочки избыточных символов этой же Фразы в регистре 1, которая, соединяясь затем со сжатой формой сжимаемой Фразы (формируется блоками 85 и 87), образует новую базовую 15 Фразу.Блок 89 получает управление от блока 85 и предназначен для определения необходимости корректировки положения новой базовой Фразы в ре гистре 1. Ввод данного блока в микропрограмму вызван тем, что когда фактическая длина (без учета цепочки правых пробелов) 1 сжимаемой фразы меньше, чем длина п регистра 1, 25 то новая базовая фраза, бывшая в тео кущем цикле сжимаемой, занимает 1 правых байтов регистра 1, а илевых байтов регистра 1 занимаются младшими символами старой базовой ЗО фразы.Блок 89 состоит из одной микроко- . манды условного перехода, в поле 75 которой содержится код условия равенства нулю содержимого счетчика 12, в полях 75и 75 4 - соответственно адреса первых микрокоманд блоков 91 и 90.Когда блок 89 получает управление, очередной тактовый сигнал считывает о 4 О указанную микрокоманду из блока 77 в регистр 75, При этом возбуждается седьмой выход дешифратора 74, который соединен с первым входом элемента И 68, второй вход которого соединен 45 с выходом счетчика 12. Если содержимое счетчика 12 равно нулю, то срабатывают элементы И 68, ИЛИ 72 и содержимое поля 75 поступает на адресный вход блока 77. В противном случае срабатывает элемент НЕ 76, выходной сигнал которого передает на адресный вход блока 77 содержимое поля 75 4.Блок 90 состоит из трех микрокоманд безусловногоперехода, в поле 75каждой из которых содержится ад- о рес следующей за ней микрокоманды. Очередные три тактовых сигнала (после передачи управления блоку 90) после 1291довательно считывают эти микрокомандыиз блока 77 в регистр 75. Зти микрокоманды в поле 75 содержат коды,возбуждающие соответственно двенадцатый, восьмой и четырнадцатый выходыдешифратора 73, выходные сигналы которых вызывают соответственно передачу содержимого регистра 4 в мультиплексор 7, сдвиг содержимого регистра1 в мультиплексор 7, сдвиг содержимого регистра 1 на один байт влево сприемом содержимого мультиплексора7 и уменьшение содержимого очетчика12 на единицу. Каждый цикл реализации блоков 89 и 90 приводит к коррек- .ции положения новой базовой фразыв регистре 1 на одну позицию,Блок 91 включает две микрокомандыбезусловного перехода и одну микрокоманду условного перехода. Каждаяиз первых двух микрокоманд содержит вполе 75 адрес следующей за ней микрокоманды, Когда блок 91 получает управление, очередные два тактовых сигнала последовательно считывают эти микрокоманды из блока 77 в регистр 75.Указанные микрокоманды содержат в поле 75 коды, возбуждающие соответственно семнадцатый и восемнадцатыйвыходы дешифратора 73, сигналы с которых вызывают соответственно записьсодержимых счетчиков 17 и 18 черезмультиплексор 20 в табличный блок 19и уменьшение содержимого счетчика13 на единицу,Последняя микрокоманда (условныйпереход) блока 91 служит для определения конца процесса сжатия. Она содержит в поле 75 код условия равенства нулю содержимого счетчика 13,а в полях 75 з, 75 - соответственноадреса первых микрокоманд блоков83 и 92,1Следующий тактовый сигнал считывает эту микрокоманду из блока 77 в регистр 75, При этом возбуждается восьмой выход дешифратора 74, который соединен с первым управляющим входом элемента И 69, второй вход которого соединен с выходом счетчика 13, Если счетчик 13 обнулен, то срабатывают элементы И 69, ИЛИ 72 и на адресный вход блока 77 поступает содержимое поля 75 з регистра 75. В противном случае срабатывает элемент НЕ 76 и на адресный вход блока 77 поступает содержимое поля 75, 1413135979130 Таким образом, если счетчик 13не Обнулен, т.е, если еще остаютсянесжатые фразы, то блок 91 возвращает управление к блоку 83 и начинается 5цикл сжаться очередной фразы,Блок 92 состоит из двух микрокоманд безусловного перехода, в поле754 каждой из которых содержится адрес следующей за ней микрокоманды. 10Очередные два тактовых сигнала последовательно считывают эти микрокоманды из блока 77 в регистр:75. Онисодержат в поле 75 коды, возбуждающие соответственно девятнадцатый 15и двадцатый выходы дешифратора 73,сигналы с которьгх поступают соответственно в ЭВМ как запрос на прерывание, извещающий об окончании процессасжатия, и на регистр 14 для обнулейия его содержимого. После блока 92выполняется блок 93, состоящий из одной микрокомапды безусловного перехода; Эта микрокоманда содержит в поле2575 код микрооперации "Останов" а вполе 75- адрес нулевой ячейки блока 77 (адрес первой микрокоманды блока 81 микропрограммы) . Последнийтактовый сигнал считывает эту микрокоманду из блока 77 в регистр 75.При этом возбуждается двадцать первый выход дешифратора 73, сигнал скоторого сбрасывает триггер 78, итем самым прекращается поступлениетактовых сигналов в блок 7735Режим "Коррекция" предусмотренв связи с тем, что обычно после сжатия массива фраз регистр 3 бываетзаполненным неполностью, и его старшие байты занимают пробелы, Так как 40развертывание начинается со старшего байта регистра 3, то содержимоерегистра 3 необходимо сдвинуть .влево до полного исчезновения цепочки указанных пробелов,В режиме Коррекция" ЭВМ передаетна регистр 14 код режима коррекциии блок 3 б управления, получив от регистра 14 сигнал о коррекции, переходит к выполнению блока 94 микро 50программы.Блок 94 состоит из одной микрокоманды условного перехода и двух группмикрокоманд безусловного перехода,включающих по три микрокоманды.551Очередной тактовый сигнал (послеполучения, блоком 94 управления) считывает из блока 77 в регистр 75 первую микрокоманду блока 94. В поле 75 этой микрокоманды содержится код условия обнуления счетчика 11, а в полях 75 З и 75 - соответственно адреса первых микрокоманд первой и второй групп микрокоманд безусловного перехода блока 94, Реализация этой микрокоманды аналогична второй микрокоманде блока 79. Если содержимое счетчика 11 обнулено, то следующие три тактовых сигнала последовательно считывают из блока 77 в регистр 75 микрокоманды первой группы блока 94, в поле 75 каждой из которых содерфжится адрес следующей за ней микро- команды. Первая, вторая, третья микрокоманды этой группы содержат в поле 75, коды, по которым соответственно возбуждаются, шестой, двадцатый идвадцать первый выходы дешифратора 73, сигналы с которых соответственно вызывают запись содержимого регистра 3 через мультиплексор 9 в блок 8 памяти, сброс регистра 14 и запрос к прерыванию, поступающий в ЭВМ как извещение об окончании коррекции. Если при выполнении первой микрокоманды блока 94 содержимое счетчика 11 не равно нулю, то следующие (после выполнения указанной микрокоманды) три тактовых сигнала последовательно считывают из блока 77 в ре-. гистр 75 микрокоманды второй группы блока 94, в поле 75 каждой из которых содержится адрес следующей за ней микрокоманды, Первая, вторая и третья микрокомапды этой группы со-, держат в поле 75 коды, по которым1возбуждаются соответственно двенадцатый, девятый и десятый выходы дешифратора 73, сигналы с которых вызывают соответственно передачу содержимого регистра 4 в мультиплексор 7, сдвиг содержимого регистра 3 на один байт влево с приемом содержимого мультиплексора 7 и уменьшение содержимого счетчика 11 на единицу.После блока 94 выполняется блок 93 (рассмотрен выше). ЭВМ, получив сигнал прерывания, разгружает блок 8 памяти и табличный блск 19.В режиме развертывания ЭВМ загружает в блок 8 памяти массив сжатых фраз, в табличный блок 19 - массив кодов количества сокращенных и не со-, кращенных символов фраз, в регистр 1 - базовую Фразу, в регистр 4 - пробел,15 13597в счетчик 13 - количество фраз, подлежащих развертыванию, в регистр 14код режима "Развертывание". Блок 16управления, получив сигнал "Развери5тывание от регистра 14, начинаетреализовать блоки 95-105 микропрограммы.Блок 95 состоит из трех микрокоманд безусловного перехода, в поле 1075 каждой из которых содержится адфрес следующей за ней микрокоманды,Первые три тактовых сигнала (считаяс начала режима развертывания) последовательно считывают микрокоманды 15блока 95 из блока 77 в регистр 75.Эти микрокоманды содержат в поле 75коды, по которым возбуждаются соответственно четвертый, двадцать второй и первый выходы дешиАратора 73, 20сигналы с которых вызывают соответственно чтениеодной сжатой Аразы изблока 8 памяти, прием этой Аразы врегистр 3 и запись в счетчик 11 длины регистра 3. После блока 95 выполняется блок 96, состоящий из трехмикрокоманд безусловного перехода,в поле 75 д каждой из которых содержится адрес следующей за ней микрокоманды. Четвертый - шестой тактовые сигналы последовательно считывают этимикрокоманды из блока 77 в регистр75, Первая, вторая и третья микрокоманды содержат в поле 75 коды, покоторым возбуждаются соответственнодвадцать третий, двадцать четвертыйи третий выходы дешифратора 73, сигналы с которых вызывают соответственно чтение из табличного блока 19 одного слова, прием этого слова в счетчики 17 и 18 и запись в счетчик 12 длины регистров 1 и 2. После блока96 выполняется блок 97, состоящий из одной микрокоманды условного перехода. Седьмой тактовый сигнал считы вает эту микрокоманду из блока 77 в регистр 75. Она содержит в поле 75код условия равенства нулю содержи мого счетчика 17 (условие отсутствия левой цепочки символов, содержащихся 50 в базовой Аразе), в полях 75 и 75 -соответственно адреса первых микрокоманд блоков 92 и 93. При выполнении ,этой микрокоманды возбуждается девя,тый выход дешиАратора 74, соединенный с первым входом элемента И 70, второй вход которого соединен с выходом счетчика 17. Если содержимое счетчика 17 равно нулю, то срабатывают 9116элементы И 70, ИЛИ 72 и на адресный вход блока 77 поступает содержимое поля 75 З регистра 75, в противном случае срабатывает элемент НЕ 76 и его выходной сигнал подает на адрес" ный вход блока 77 содержимое поля 75Блок 98 предназначен для восстановления одного символа сокращенной левой цепочки развертываемой фразы.Он состоит из четырех микрокоманд безусловного перехода, в поле 75каждой из которых содержится адрес следующей за ней микрокоманды. Когда блок 98 получает управление, очередные четыре тактовых сигнала последовательно считывают его четыре микро- команды из блока 77 в регистр 75, Эти микрокоманды содержат в поле 75 коды, по которым возбуждаются соответственно пятнадцатый, восьмой, двадцать пятый и четырнадцатый выходы дешиАратора 73, сигналы с которых вызывают соответственно передачу в мультиплексор 7 старшего байта регистра 1, сдвиг содержимого регистра 1 на один байт влево с приемом содержимого мультиплексора 7, уменьшение содержимого счетчика 17 на единицу и уменьшение содержимого счетчика 12 на единицу, Последняя микрокоманда блока 98 возвращает управление к блоку 97. Таким образом, циклическое выполнение блоков 97 и 98 до обнуления счетчика 17 обеспечивает восстановление в регистре 1 левой цепочки сокращенных символов развертываемой Аразы, после чего управление получает блок 99.Блок 99 состоит из двух микрокоманд условного перехода. Первая мик-. рокоманда содержит в поле 75код условия равенства содержимого счетчика 18 (условия полного восстановления развертываемой фразы), а в полях 75 и 75 4 соответственно адреса первой микрокоманды блока 102 и второй микрокоманды блока 99. Очередной тактовый сигнал считывает эту микро- команду из блока 77 в регистр 75, При этом возбуждается десятый выход дешифратора 74, соединенный с первым входом элемента И 71, второй вход которого соединен с выходом счетчика 18. Если содержимое счетчика 18 рав-. но нулю, то срабатывают элементы И 71, ИЛИ 72 и на адресный вход блока 77 поступает содержимое поля 75, В противном случае срабатывает эле