Устройство для сжатия и развертывания данных Советский патент 1987 года по МПК G08C19/28 

13

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

Целью изобретения является повышение информативности устройства.

На фиг.1 представлена структурная схема устройства для сжатия и развертывания данных, на фиг.2 - функ- циональная схема блока управления, на фиг.З - блок-схема микропрограммы работы блока управления.

Устройство для сжатия и развертывания данных содержит (фиг.1) пер- вый- третий и пятый регистры 1-4, первой и второй блоки 5 и 6 сравнения, третий мультиплексор 7, первый блок 8 памяти, первый мультиплексор 9, шину 10 данных, первый - третий счетчики 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 обозначены блоки микропрограммы работы блока управления .

Блок 77 постоянной памяти предназначен для хранения микропрограммы Регистр 75 состоит из полей ,, служащих соответственно для задания кода микрооперации, кода проверяемо- го условия, адреса перехода при нулевом значении проверяемого условия и

12

адреса перехода при единичном значении проверяемого условия.

Устройство работает под управлением ЭВМ (например, микро-ЭВМ СМ-1800) с трехшинной архитектурой. Теоретическое обоснование работы устройства следующее.

Каждая сжимаемая фраза состоит из трех цепочек: цепочки левых символов, повторяющейся в базовой фразе, цепочки средних символов, не повто ряющейся в базовой фразе, и цепочки правых пробелов. Путем посимвольного сравнения сжимаемой фразы Ф- с базовой фразой Ф или Ф;.) определяют длину 1 цепочки повторякнцихся символов. Оставшаяся цепочка, состоящая из 1 существенных символов фразы ф (без учета цепочки правых пробелов), рас- сматриваётсй как сжатая форма ф, фразы ф. . Таким образом, в результате сжатия из каждой фразы отбрасывается цепочка левых символов, повторяющаяся в базовой для нее фразе, и цепочка правых пробелов. Однако для- последующего восстановления необходимо сохранить не только Ф , но и 1.; и 1.

Поэтому в результате сжатия массива фраз формируются таблица L 1,, последовательность F

Ф,., где N - число сжатьк фраз.

В таблице показан пример сжатия и развертывания данных, состоящих из 15 фраз. В качестве базовой для nepf- вой фразы принята фраза ф , состоящая только из пробелов (пробелы изображены точками).

42 символов)

Посимвольное сравнение первой фразы Ф с нулевой фразой ф показывает, что ф, не имеет цепочку совпа- дающих левых .символов и поэтому 1 0. Все шесть существенных символов рассматриваются как сжатая форма фразы и поэтому 1 6, ф° М -6000 ф -образует первые шесть символов последовательности F. Затем фраза Ф сравнивается с фразой ф.и устанавливается, что ф имеет цепочку М- сов- падающих,символов и поэтому . Оставшаяся, цепочка четырех сз -щественных символов фразы ф принимается как ее сжатая форма, т.е. Ф2 70007 образует следующие четыре символа по- следовательности. Таким же образом сжимаются все остальные фразы, в результате чего формируются таблица L и последовательность F,

Развертывание производится следую- щим образом. В качестве базовой для фразы ф принимается такая же фраза Ф„, как и при сжатии (в рассматривае омом примере цепочка пробелов).

Для развертывания первой фразы Ф используются 1 и 1. Так как 1 0, то Ф,не имеет никаких символов, содержащихся в базовой фразе, а 1j 6 показывает, что шесть первых символов последовательности F принадлежат фразе ф,, т.е. ф, М-бООО,.

Для развертывания второй фразы Ф„

О о

используются 1 1 и 1 J. Тд.к как 1 ., , то первые, два символа фразы

Продолжение TaG;iiiiibi

совпадают с аналогичны ш символами фразы ф, , т.е. Ф 5- М- . Поскольку

1,4, то последующие четыре символа

фразы ф содержатся в последователь6. о 0

5

0

5

ности F. Этими символаьп являются Ф2 7000, Следовательно,

ф- ( -2 г

К - 7000), Таким образом развертываются все остальные фразы.

Устройство работает в трех режимах: сжатие, коррекция, развертывание .

Режим работы устройства задается : ЭВМ передачей трехразрядного унитарного кода режима в регистр 14 (фиг.1), выходы которого соединены с соответствующими входами блока 16 управления (фиг.1 и 2).

Блок 16 управления вырабатывает последовательность сигналов,в соответствии с микропрограммой,- блок-схема которой приведена на фиг.З. Формат икpoкoмaнд и назначение их отдельных полей полностью совпадают с форматом и назначением полей регистра 75 микрокоманды. Так как текущая микрокоманда хранится в регистре 75, то поля 75 будут рассматриваться как части регистра 75, если речь идет о нем, или как части текущей микрокоманды, если речь идет о ней.

В микропрограмме используются микрокоманды двух-типов.

Микрокоманда условного перехода содержит код пустой микрооперации в поле 75-) , по ней деашфратор 73 не

5 135979

возбуждается. Поэтому при описании такой микрокоманды поле 75, и депшф- ратор 73 упоминаться не будут.

Микрокоманда безусловного перехода содержцт код пустого условия в поле 75, по ней дешифратор 74 не возбуждается. Кроме того, из-за единственности возможной следующей микрокоманды одно из полей адреса та- ю кой микрокоманды-не используется.

На фиг.2 это поле 75,, Поэтому при выполнении такой микрокоманды ни один из элементов И 62-71, а также элемент ИЛИ 72 не срабатывают, а срабатывает только элемент НЕ 76, который соединяет поле 75. регистра 75 с адресным входом блока 77 памяти. Таким образом, при выполнении микрокоманды безусловного перехода в качестве адреса следующей микрокоманды всегда выбирается содержимое поля 75 perj гистра 75. Поэтому при описании такой микрокоманды поля 75 и 75-,дешифратор 74 и цепи выбора адреса следующей микрокоманды упоминаться не буду

Работа устройства задается микропрограммой, блок-схема которой представлена на фиг.З. Блоки 80 и 93 являются соответственно началом и концом микропрограммы, а блок 81 содержит три микрокоманды условного перехода:

если сжатие, то переход к блоку 82 если коррекция, то переход к блоку 94;

если развертывание, то переход к блоку 95;

иначе возврат к блоку 81. В исходном состоянии регистр 75 микрокоманды находится в нулевом состоянии (код пустой микрооперации в поле 75, код пустого условия в поле 752, нулевые адреса в полях 75j и 754). Блок памяти содержит микропрограмму работы устройства в режимах сжатие, коррекция, развертьгаание (микропрограмма размещается начиная с нулевой ячейки).

Сигналом Пуск триггер 78 устанавливается в единичное состояние и разрешает прохождение тактовых символов через элемент И 79 в блок 77 памяти.

Первый тактовьй сигнал считывает первую микрокоманду блока 81 (фиг.З) с нулевой ячейки блока 77 в регистр 75. Эта микрокоманда условного перехода содержит в поле 75 код условия

5

в

сжатия, в поле 75j адрес первой микрокоманды блока 82, в поле 75 адрес второй микрокоманды блока 81. При этом возбуждается первьй выход дешифратора 74, соединенный с первым входом элемента И 62, второй вход которого соединен с выходом сжатия регистра 14 режима. Если выход Сжатие регистра 14 возбужден, то срабатывают элементы И 62, ИЛИ 72, выходной сигнал последнего передает содержимое поля 75j регистра 75 на адресный вход блока 77 памяти.

В противном случае элементы И 62 ИЛИ 72 не срабатывают и выходной сигнал элемента НЕ 76 передает содержимое поля 754 регистра 75 на адресный вход блока 77.

Второй тактовый сигнал считьгоает из блока 77 в регистр 75 первую микрокоманду блока 82 (начало сжатия) или вторую микрокоманду блока 81 в зависимости от того, адрес какой из указанных микрокоманд бьш передан на адресный вход блока 77 памяти.

Вторая микрокоманда блока 81 содержит в поляк 75J- 754 соответственно код условия Коррекция, адрес 0 первой микрокоманды блока 94 и адрес третьей микрокоманды блока -81. При этом дешифратор 74 возбуждает свой второй выход, соединенный с первым входом элемента И 63, второй вход которого соединен с вькодом Коррекция регистра 14. Если выход Коррекция регистра 14 возбужден, то срабатывают элементы И 63, ИЛИ 72, на адресный вход блока 77 передается содержимое

0

5

5

поля 755 регистра 75. В противном случае сигнал с выхода элемента НЕ 76 передает на адресный вход блока 77 содержимое поля 75 регистра 75.

Третий тактовый сигнал считывает из блока 77 в регистр 75 первую микрокоманду блока 94 (начало коррекции) или третью микрокоманду блока 81.

Третья микрокоманда блока 81 содержит в полях 75 j- 75 4 соответственно код условия Развертыпание, адрес первой микрокоманды блока 95 и адрес первой микрокоманды блока 81. При этом дешифратор 74 возбуждает свой- третий выход, соединенный с первым входом элемента И 64, второй вход ко торого соединен с выходом Ра верты- вание регистра 14. Если этот выход возбужден, то срабатывают элементы И 64, ИПИ 72, на адресный вход блока

77 передается содержимое поля 75. регистра 75. В противном случае сигнал с выхода элемента НЕ 76 передаёт на адресный вход блока 77 содержимое , поля 754. регистра 75.

Таким образом, блок 16 управления реализует блок 81 микропрограммы, циклически опрашивая выходы регистра ,14 режима, и при обнаружении единич- ,ного сигнала на одном из них перехо- дит к реализащ1и соответствующей нет ви микропрограммы (фиг.З).

В режиме сжатия ЭВМ загружает в

блок 8 памяти массив фраз, подлежащих 15 та И 65, второй вход которого соеди- сжатию, в регистр 1 - базовую фразу.

вен с выходом блока 5 сравнения. Ее ли содержимые старишх байтов регистров 1 и 2 совпадают, то срабатывают блок 5 сравнения, элемент -И 65 и элемент ИЛИ 72, в результате чего на .адресный вход блока 77 передается содержимое поля 75 регистра 75, в противном случае срабатывает только элемент НЕ 76 и на адресньш вход блока 77 поступает содержимое поля 75 регистра 75. Таким образом, после блока 84 выполняется блок 88 или 85.

в регистр 4 - пробел, в счетчик 13 - количество фраз в блоке 8 памяти, в регистр 14 - код режима сжатия.

Блок 16 управления, получив от ре-20 гистра 14 сигнал о режиме сжатия, приступает к реализации блоков 82-92 микропрограмм работы устройства.

Блок 82 (начало реализагдии режима Сжатие) состоит из одной микроко- 25 манды безусловного перехода, в поле 75 которой содержится код микрооперации записи данных (в байтах) регистра 3 в счетчик 11, в поле 75 ,- адрес первой микрокоманды блока 83. 30

Первьш тактовый сигнал, (с момента начала режима сжатия) считывает эту микрокоманду из блока 77 в регистр 75, после чего начинается ее реализация. 35

При этом возбуждается первый выход дешифратора 73, сигнал с которого записывает в счетчик 11 код длины регистра 3.

вен с выходом блока 5 сравнения. Е ли содержимые старишх байтов регис ров 1 и 2 совпадают, то срабатываю блок 5 сравнения, элемент -И 65 и э мент ИЛИ 72, в результате чего на .адресный вход блока 77 передается содержимое поля 75 регистра 75, в противном случае срабатывает тольк элемент НЕ 76 и на адресньш вход блока 77 поступает содержимое поля 75 регистра 75. Таким образом, по ле блока 84 выполняется блок 88 или 85.

Все следующие блоки микропрограм мы получают управление условными п реходами (непосредственно или косве но) . В связи с этим закреплять за конкретным блоком конкретные тактов сигналы невозможно. Поэтому дапее будем пользоваться выражениями очередной тактовый сигнал, cлeдyющIiй тактовый сигнал.

Блок 85 состоит из двух микрокоманд УСЛОВНОГО перехода. Если блок

Блок 83 представляет собой после-о 40 получает управление от блока 84

довательность из четырех микрокоманд безусловного перехода, в поле 75 каждой из них содерлсится адрес еле-, дующей за ней микрокоманды. Второй - пятый тактовые сигналы считьшают в - последовательном порядке соответственно первую- четвертую микрокоманды блока 83.

Первая, вторая, третья и четвертая микрокоманды блока 83 содержат в по- ле 75 коды, пр которым возбуждаются соответственно второй, третий, четвертый и пятый выходы дещифратора 73, сигналы которых вызывают сброс счетчиков 17 и 18, запись в счетчик 12 длины регистров 1 и 2, чтение из блока 8-памяти очередной (первой в начале) фразы и прием этой фразы в ре гистр 2.

979,1

После блока 83 следует блок 84, состоящий из одной микрокоманды условного перехода. Эта микрокоманда считывается из блока 77 в регистр 75 шестым тактовым сигналом. Она содержит в поле 75 2 код условия совпадения старших байтов регистров 1 и 2, а в полях 753 и 75 - адреса первых микрокоманд блоков 88 и 85 соответственно.

По этой, микрокоманде возбуждается четвертый выход дешифратора 74, который соединен с первым входом элемен5

10

та И 65, второй вход которого соеди-

вен с выходом блока 5 сравнения. Еели содержимые старишх байтов регистров 1 и 2 совпадают, то срабатывают блок 5 сравнения, элемент -И 65 и элемент ИЛИ 72, в результате чего на .адресный вход блока 77 передается содержимое поля 75 регистра 75, в противном случае срабатывает только элемент НЕ 76 и на адресньш вход блока 77 поступает содержимое поля 75 регистра 75. Таким образом, после блока 84 выполняется блок 88 или 85.

Все следующие блоки микропрограммы получают управление условными переходами (непосредственно или косвенно) . В связи с этим закреплять за конкретным блоком конкретные тактовы сигналы невозможно. Поэтому дапее будем пользоваться выражениями очередной тактовый сигнал, cлeдyющIiй тактовый сигнал.

Блок 85 состоит из двух микрокоманд УСЛОВНОГО перехода. Если блок

или 87, то очередной тактовый сигнал считывает из блока 77 в регистр 75 его первую микрокоманду, в поле 752 которой содержится код условия Ре4g гистр 2 пуст, в поле 75 - адрес первой микрокоманды блока 89, в поле адрес второй микрокоманды блока 85 о

По этой микрокоманде возбуждается

gQ пятый выход дешифратора 74, которьй соединен с первым входом элемента И 66, второй вход которого соединен с выходом блока 6 сравнения. Если регистр 2 пуст, то срабатывают блок 6

gg сравнения, элемент И 66 и элемент

в ИЛИ 72, в результате чего на адресньй

вход блока 77 передается содержимое

поля 753 регистра 75. В противном

случае срабатывает элемент НЕ 76 и

135

на адресный вход блока 77 поступает соде ржпмое поля 75. Следовательно, если регистр 2 ,не пуст, то следующим

тактовым Ьигналом считывается из бло

ка /7 в регистр 75 вторая микрокоманда блока 85. Она содержит в поле 75 код условия обнуления счетчика 11, в полях 75,и 75. - соответственно адреса первых микрокоманд блоков 86 и 87, По этой микрокоманде возбуткда- ется шестой выход дешифратора 74, соединенньш с первым входом элемента И 67, второй вход которого соединен с выходом счетчика 11„ Если со- держимое счетчика 11 равно нулю, то срабатывают элементы И 67, РШИ 72, в результате чего содержимое поля 75 регистра 75 передается на адресный вход блока 77. В противном случае срабатывает элемент НЕ 76 и на адресный вход блока 77 поступает содержимое поля 75 4.

Таким образом, каждый цикл реали зации блоков 85 и 87 приводит к пер сылке одного неизбыточного символа сжимаемой фразы из регистра 2 в ре гистры 1 и 3. В результате этого сжатая форма сжимаемой фразы парал лельно накапливается в регистрах 1 и 2. При этом содержимое регистра вместе с цепочкой избыточных симво лов сжимаемой фразы (формируется

Блок 86 предназначен для разгрузки регистра 3, когда он полностью запол- 25 блоками 84,88) рассматривается как нен и требуется место для нового сим- новая базовая фраза, а содержимое вола.

Блок 86 состоит из двух микрокоманд безусловного перехода в поле 75, в каждой из которых содержится адрес Q следующей за ней микрокоманды. Очередные два тактовых сигнала (после передачи блоку 86 управления) последовательно считывают из блока 77 в регистр 75 первую и вторую микрокоманды этого блока, содержащие в поле 75 соответственно коды, возбуждающие шестой и первый выходы дешифратора 73, сигналы с которых соответст-i

35

регистра 3 рассматривается как оче редная цепочка символов, сформиро- ванная в результате сжатия фраз.

Блок 88 может следовать только после блока 84 и служит для сокращ ния избыточных символов сжимаемой фразы. Он состоит из шести микроко манд безусловного перехода, в поле 75 каждой из .которых содержится адрес следующей за ней микрокоманд Очередные шесть тактовых сигналов (после передачи блоку 88 управлени

венно вызывают запись содерлгамого ре- Q последовательно считывают из блока

гистра 3 через мультиплексор 9 в блок 8 памяти и запись в счетчик 11 кода длины регистра 3.

За блоком 86 следует блок 87, состоящий из восьми микрокоманд безусловного перехода, в поле 75 каждого из которых содержится адрес следующей за ней.микрокоманды. Очередные восемь тактовых сигналов последовательно считывают из блока 77 в регистр 75 первую - восьмую микрокоманды блока 87 содержащие в поле- 75 коды, возбуждающие соответственно седьмой - четьф- надцатьй выходы дешифратора 73, сиг- налы с которых вызывают передачу старшего байта регистра 2 в мультиплексор 7, сдвиг содержимого регистра 2 на один байт влево с приемом содержимого мультиплексора 7, сдвиг со77 в регистр 75 первую - шестую ьшкр команды этого блока, в поле 75 кот рых содержатся коды, возбуждающие соответственно пятнадцатьм, восьмой

45 шестнадцатый, двенадцатый, тринадцатый и четырнадцатью выходы дешифр тора 73, сигналы с которых вызывают соответственно передачу старшего ба та регистра 1 в мультиплексор 7,

gQ сдвиг содержимого регистра 1 на оди байт влево с приемом содержимого Ь1ультиплексора 7, увеличение на еди ницу содержимого счетчика 17, передачу содержимого регистра 4 в мульgg типлексор 7, сдвиг содержимого регистра 2 на один байт влево s приемом содержимого мультиплексора 7, уменьшение на единицу содержимого счетчика 12.

10

держимого регистра 3 влево и прием содержимого мультиплексора7, уменьшение на единицу содержимого счетчика 11, увеличение содержимого счет- шка 18 на единицу, передачу содержимого регистра 4 на мультиплексор 7, сдвиг содержимого регистра 2 влево с приемом содержимого мультиплексора 7, уменьшение содержимого счетчика 12 на единицу.

Последняя микрокоманда блока 87 осуществляет переход (возврат) к блоку 85.

Таким образом, каждый цикл реализации блоков 85 и 87 приводит к пере сылке одного неизбыточного символа сжимаемой фразы из регистра 2 в регистры 1 и 3. В результате этого сжатая форма сжимаемой фразы параллельно накапливается в регистрах 1 и 2. При этом содержимое регистра 1 вместе с цепочкой избыточных символов сжимаемой фразы (формируется

блоками 84,88) рассматривается как новая базовая фраза, а содержимое

блоками 84,88) рассматривается как новая базовая фраза, а содержимое

регистра 3 рассматривается как очередная цепочка символов, сформиро- ванная в результате сжатия фраз.

Блок 88 может следовать только после блока 84 и служит для сокращения избыточных символов сжимаемой фразы. Он состоит из шести микрокоманд безусловного перехода, в поле 75 каждой из .которых содержится адрес следующей за ней микрокоманды. Очередные шесть тактовых сигналов (после передачи блоку 88 управления)

77 в регистр 75 первую - шестую ьшкро- команды этого блока, в поле 75 которых содержатся коды, возбуждающие соответственно пятнадцатьм, восьмой,

45 шестнадцатый, двенадцатый, тринадцатый и четырнадцатью выходы дешифратора 73, сигналы с которых вызывают соответственно передачу старшего байта регистра 1 в мультиплексор 7,

gQ сдвиг содержимого регистра 1 на один байт влево с приемом содержимого Ь1ультиплексора 7, увеличение на единицу содержимого счетчика 17, передачу содержимого регистра 4 в мульgg типлексор 7, сдвиг содержимого регистра 2 на один байт влево s приемом содержимого мультиплексора 7, уменьшение на единицу содержимого счетчика 12.

11

Последняя микрокоманда блока 88 осуществляет передачу (возврат) к блоку 84.

Каждый цикл реализации блоков 84 и 88 приводит к выталкиванию одного избыточного символа сжимаемой фразы из регистра 2 в регистр 1, тем самым происходит сокращение одного символа сжимаемой фразы и накопление одного символа цепочки избыточных символов этой же фразы в регистре 1, которая, соединяясь затем со сжатой формой сжимаемой фразы (формируется блоками 85 и 87), образует новую базовую фразу.

Блок 89 получает управление от блока 85 и предназначен для определения необходимости корректировки положения новой базовой фразы в регистре 1. Ввод данного блока в микропрограмму вызван тем, что когда фактическая длина (без учета цепочки правых пробелов) 1 сжимаемой фразы меньше, чем длина п регистра 1, то новая базовая фраза, бывшая в текущем цикле сжимаемой, -занимает 1 правых байтов регистра 1, а п-1 левых байтов регистра 1 занимаются младшими символами старой базовой фразы.

Блок 89 состоит из одной микрокоманды условного перехода, в поле 75,2 которой содержится код условия равенства нулю содержимого счетчика 12, в полях 75J и 754 - соответственно адреса первых микрокоманд блоков 91 и 90.

Когда блок 89 получает управление очередной тактовый сигнал считьшает указанную микрокоманду из блока 77 в регистр 75. При этом возбуждается седьмой выход дешифратора 74, которы соединен с первым входом элемента И 68, второй вход которого соединен с выходом счетчика 12. Если содержимое счетчика 12 равно нулю, то срабатывают элементы И 68, ИПИ 72 и содержимое поля 75; поступает на адресный вход блока 77. В противном случае срабатывает элемент НЕ 76, выходной сигнал которого передает на адресньй вход блока 77 содержимое поля 75 .

Блок 90 состоит из трех микрокоманд безусловного перехода, в поле 754 каждой из которых содержится ад- рее следующей за ней микрокоманды. Очередные три тактовых сигнала (посл передачи управления блоку 90) по.сле

1359791

довательно считывают эти микрокоманды из блока 77 в регистр 75. Эти микрр0

5

0

Q 5 0

g о

0

команды в поле 75 содержат коды, возбуждающие соответственно двенадцатью, восьмой и четьфнадцатый выходы дешифратора 73, выходные сигналы которых вызывают соответственно передачу содержимого регистра 4 в мультиплексор 7, сдвиг содержимого регистра 1 в мультиплексор 7, сдвиг содержимого регистра 1 на один байт влево с приемом содержимого мультиплексора 7 и уменьшение содержимого счетчика

12на единицу. Каждый цикл реализации блоков 89 и 90 приводит к коррекции положения новой базовой фразы

в регистре 1 на одну позицию.

Блок 91 включает две микрокоманды безусловного перехода и одну микрокоманду условного перехода. из первых двух микрокоманд содержит в поле 754 адрес следующей за ней микрокоманды. Когда блок 91 получает управ- 5 ление, очередные два.тактовых сигнала последовательно считывают эти микрокоманды из блока 77 в регистр 75. Указанные микрокоманды содержат в поле 75 коды, возбуждающие соответственно семнадцатый и восемнадцатый выходы дешифратора 73, сигналы с которых вызывают соответственно запись содержимых счетчиков 17 и 18 через мультиплексор 20 в табличный блок 19 и уменьшение содержимого счетчика

13на единицу.

Последняя микрокоманда (условньй переход) блока 91 служит для определения конца процесса сжатия. Она содержит в поле 752 к°Д условия равенства нулю содержимого счетчика 13, а в полях 75J, 75 - соответственно адреса первых микрокоманд блоков 83 и 92.

Следующий тактовый сигнал считывает эту микрокоманду из блока 77 в регистр 75. При этом возбуждается восьмой выход дешифратора 74, который соединен с первым управляющим входом элемента И 69, второй вход которого соединен с выходом счетчика 13. Если счетчик 13 обнулен, то срабатывают элементы И 69, ОТИ 72 и на адресный вход блока 77 поступает содержимое поля 75 3 ре гистра 75. В противном случае срабатывает элемент НЕ 76 и на адресный вход блока 77 поступает содержимое поля 75+,

5

313

Таким образом, если счетчик 13 не ббнулеи, т.е. если еще остаются несжатые фразы, то блок 91 возвращает управление к блоку 83 и начинается цикл с. очередной фразы.

Блок 92 состоит из двух микрокоманд безусловного перехода, в поле 75 ка ящой из которых содержится адрес следующей за ней микрокоманды,

Очередные два тактовых сигнала последовательно считывают эти ьшкроко- манды из блока 77 в регистр,75, Они содержат в поле 75 коды, возбуждающие соответственно девятнадцатый и двадцатый выходы дешифратора 73, сигналы с которых поступа от соответственно в ЭВМ как запрос на прерывание, извещающий об окончании процесс сжатия, и на регистр 14 для обнуле- Гшя его содерлшмого. После блока 92 выполняется блок 93, состоящий из одной микрокоманды безусловного перехода ; Эта микрокоманда содерйап в поле 75 код микрооперации Останов а в

поле 75 , - адрес нулевой ячейки бло- ка 77 (адрес первой микрокоманды блока 81 микропрограммы). Последний тактовый сигнал считывает эту Ь Мкро- команду из блока 77 в регистр 75. При этом возбулсдается двадцать первый выход дешифратора 73, сигнал с которого сбрасывает триггер 78, и тем самым прекращается поступление тактовых сигналов в блок 77.

Режим Коррекция предусмотрен в связи с тем, что обьр.1но после сжатия массива фраз регистр 3 бывает заполие.нкьгм пеполностью, и его стар- Ш1е байты занимают пробелы. Так как развертывание начинается со старшего байта регистра 3, то содерзкимое регистра 3 необходимо сдвинуть . влево до полного исчезновения цепочки указанных пробелов,

В режиме Коррекция ЭВМ передает на регистр 14 код режима коррекции и блок 16 управления, получив от регистра 14 сигнал о коррекции, переходит к выполнению блока 94 микропрограммы.

Блок 94 состоит из одной микрокоманды условного перехода и двух груп микрокоманд безусловного перехода, включающих по три микрокоманды.

Очередной тактовый сигнал (после получения .блоком 94 управления) считывает- из блока 77 в регистр 75 пер

14

5 0

5

0 5

0

50

вую микрокоманду блока 94. В поле 752 этой микрокоманды содержится код условия обнуления счетчика 11, а в полях 75j и 75 - соответственно адреса первых микрокоманд первой и второй групп микрокоманд безусловного перехода блока 94. Реализация этой микрокоманды аналогична второй микрокоманде блока 79. Если содержимое счетчика 11 обнулено, то следующие три тактовых сигнала последовательно считывают из блока 77 в регистр 75 микрокоманды первой группы блока 94, в поле 75 каждой из которых содержится адрес следующей за ней микрокоманды. Первая, вторая, третья микрокоманды этой группы содержат в поле 75, коды, по которым соответственно возбуждаются, шестой, двадцатый и двадцать первый выходы дешифратора 73, сигналы с которых соответственно вызывают запись содержимого регистра 3 через мультиплексор 9 в блок 8 памяти, сброс регистра 14 и запрос к прерыванию, поступающий в ЭВМ как извещение об окончании коррекции. Если при выполне:нии первой микрокоманды блока 94 содержимое счетчика 11 не равно нулю, то следующие (после выполнения указанной микрокоманды) три тактовых сигнала последовательно считывают из блока 77 в ре- . гистр 75 Mi-псрокоманды второй группы блока 94, в поле 75 каждой из которых содержится адрес следующей за ней микрокоманды. Первая, вторая и третья микрокоманды этой группы со-. держат в поле 75. коды, по которым возбуждаются соответственно двенадцатый, девятый и десятый выходы депшф- ратора 73, сигналы с которых вызывают соответственно передачу содержи- мого регистра 4 в мультиплекссэр 7, сдвиг содерзкимого регистра 3 на один байт влево с приемом содерлшмого мультиплексора 7 PI уменьшение содер- JKiiMoro счетчика 11 на единицу.

После блока 94 вьтолняется блок 93 (рассмотрен выше). ЭВМ, получив сигнал прерывания, разгружает блок 8 памяти и табличный блс-к 19,

В режиме развертывания ЭВМ загружает в блок 8 памяти массив сжатых фраз, в табличный блок 19 - массив кодов количества сокращенных и не сокращенных символов фраз, в регистр 1- базовую фразу, в регистр 4 - пробел,

в счетчик 13 - количество фраз, под лежащих развертыванию, в ре гистр 14 код режима Развертывание. Блок 16 управления, получив сигнал Развертывание от регистра 14, начинает реализовать блоки 95-105 микропрограммы.

Блок 95 состоит из трех микрокоманд безусловного перехода, в поле 75 . каждой из которых содержится адрес следующей за ней микрокоманды. Первые три тактовых сигнала (считая с начала режима развертывания) последовательно считывают микрокоманды блока 95 из блока 77 в регистр 75. Эти микрокоманды содержат в поле 75 коды, по которым возбуждаются соответственно четвертый, двадцать второй и первый выходы дешифратора 73, сигналы с которых вызывают соответственно чтение одной сжатой фразы из блока 8 памяти, прием этой фразы в регистр 3 и запись в счетчик 11 длины регистра 3. После блока 95 выполняется блок 96, состоящий из трех микрокоманд безусловного перехода, в поле 75 4 каждой из которых содер25 в мультиплексор 7 старшего байта регистра 1, сдвиг содержимого регистра 1 на один байт влево с приемом содер жимого мультиплексора 7, уменьшение содержимого счетчика 17 на единицу

жится адрес следующей за ней микрокоманды. Четвертый - шестой тактовые сиг-30 и уменьшение содержимого счетчика налы последовательно считывают эти .12 на единицу. Последняя микрокоман- микрокоманды из блока 77 в регистр да блока 98 возвращает управление 75. Первая, вторая и третья микроко- к блоку 97. Таким образом, цикличес- манды содержат в поле 75., коды, по кое вьшолнение блоков 97 и 98 до обнуления счетчика 17 обеспечивает восстановление в регистре 1 левой цепочки сокращенных символов развертываемой фразы, после чего управление получает блок 99;

35

которым возбуждаются соответственно двадцать третий, двадцать четвертый и третий выходы дешифратора 73, сигналы с которых вызывают соответственно чтение из табличного блока 19 одного слова, прием этого слова в счет- 40 чики 18 и запись в счетчик 12 длины регистров 1 и 2. После блока 96 выполняется блок 97, состоящий из одной микрокоманды условного перенуления счетчика 17 обеспечивает восстановление в регистре 1 левой цепочки сокращенных символов развертываемой фразы, после чего управление получает блок 99;

Блок 99 состоит из двух микрокоманд условного перехода. Первая микрокоманда содержит в поле 75 2 код условия равенства содержимого счет чика 18 (условия полного восстановв регистр 75. Она содержит в поле 75 код условия равенства нулю содержи мого счетчика 17 (условие отсутствия левой цепочки символов, содержащихся в базовой фразе), в полях 75 и соответственно адреса первых микрокоманд блоков 92 и 93. При вьтолнении

,этой микрокоманды возбуждается девя50

хода. Седьмой тактовый сигнал считы- 45 ения развертываемой фразы), а в по- вает эту микрокоманду из блока 77 лях 75j и 75 соответственно адреса

первой микрокоманды блока 102 и второй микрокоманды блока 99. Очередной тактовый сигнал считывает эту микрокоманду из блока 77 в регистр 75. При этом возбуждается десятый выход дешифратора 74, соединенный с первым входом элемента И 71, второй вход которого соединен с выходом счетчика .тый выход дешифратора 74, соединенный gg 18. Если содержимое счетчика 18 рав- с первым входом элемента И 70, второй но нулю, то срабатывают элементы вход-которого соединен с выходом И 71, ИЛИ 72 и на адресный вход бло- счетчика 17. Если содержимое счетчи- ка 77 поступает содержимое поля 75, ка 17 равно нулю, то срабатывают . В противном случае срабатывает элеэлементы И 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 до оби уменьшение содержимого счетчика 12 на единицу. Последняя микрокоман- да блока 98 возвращает управление к блоку 97. Таким образом, цикличес- кое вьшолнение блоков 97 и 98 до об

нуления счетчика 17 обеспечивает восстановление в регистре 1 левой цепочки сокращенных символов развертываемой фразы, после чего управление получает блок 99;

Блок 99 состоит из двух микрокоманд условного перехода. Первая микрокоманда содержит в поле 75 2 код условия равенства содержимого счет чика 18 (условия полного восстанов171359791

мент НЕ, 76 и на адресный вход блока 77 поступает содержимое поля 75 регистра 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 коды, по KOTopbw возбуждаются соответственно двадцать шестой, восьмой, четырнадцатый, двадцать седьмой, двенадцатый девятый и десятьй выходы Дешифратора 73, сигналы с которых соответственно .вызывают передачу в мультиплексор 7 старшего байта регистра 3, сдвиг содержимого-регистра 1 на один байт влево с приемом содержимого мульти

5

0

5

18

плексора 7, уменьшение содержимого счетчика 12 на единицу, уменьшение содержимого счетчика 18 на единицу, передачу в мультиплексор 7 содержимого регистра 4, сдвиг содержимого регистра 3 на один байт влево с приемом содержимого мультиплексора 7 и уменьшение содержимого счетчика 11 на единицу.

Последняя микрокоманда блока 101 возвращает управление к первой микрокоманде блока 99. Таким образом, в результате циклического выполнения блоков 99 и 100 в регистре 1 восстанавливается сжатая форма развертываемой фразы, что совместно с восстановленной блоками 97 и 98 левой цепочкой сокращенных символов образует развернутую фразу.

Однако как и при сжатии, когда длина 1 развернутой фразы меньше, чем длина п регистра 1, п-1 старших байтов регистра 1 занимаются пробелами, т.е, развернутая фраза занимает неправильное положение в регистре 1. Так как каждая развернутая фраза является базовой для следующей фразы, подлежащей развертыванию, то корректировка ее положения является необходимой. Для этого используются блоки 102 и 103. Блок 102 состоит из одной микрокоманды условного перехода, в полях 75., 75„, 75 которой содержатся код условия обнуления счетчика 12, адрес первой микрокоманды блока 104 и адрес первой микрокоманды блока 103. Она реализуется таким же образом, блок 89. Блик 103 аналогичен блоку 90, его последняя микрокоманда возвращает управление блоку 89. Таким образом, циклическое вьшолнение блоков 89 и 90 до обнуления счетчика 12 приводит к тому, что развернутая фраза занимает правильное положение в регистре 1. Блок 104 получает управление от блока 102 в том случае, если содержимое счетчика 12 равно нулю. Он содержит две микрокоманды безусловного перехода и одну микрокоманду условного перехода.

Каждая из первых двух микрокоманд блока 102 в поле 75 содержит адрес gg следующей за ней микрокоманды. Очередные два тактовых сигнала последовательно счнтьшают эти микpqкoмaнды из блока 77 в регистр 75. Первая и вторая микрокоманды содержат в поле

0

5

0

5

50

19

75 коды, по которым зозбутщаются соответственно двадцать восьмой и восемнадцатый выходы дешифратора 73, сигналы с которых вызывают соответственно запись содержимого регистра 1 через мультиплексор 9 в блок 8 памяти и уменьшение содержимого счетчика 13 на единицу.

6Iкpoкoмaндa условного перехода блока 92 содержит в полях 75 соответственно код условия обнуления счетчика 13 (условие развертывания всех фраз), адрес первой микрокоманды блока 105 и адрес первой микроко- манды блока 96. Она реализуется таким же образсж, как и последняя мик- рокомацда блока 91. Следовательно, если содержимое счетчика 13 не равно нулю, то осуществляется возврат к блоку 96 (начало развертывания следующей фразы), в противном случае - к блоку 105.

Блок 105 состоит из двух микрокоманд безусловного перехода, в поле 75 каждой из которых содержится адрес следующей за ней микрокоманды. Очередныедва тактовых сигнала последовательно считывают эти микрокоманды из блока 77 в регистр 75. Первая и вторая микрокоманды содержат в поле 75 коды, по которым соответственно возбуяздаются двадцатый и двадцать девятый выходы дешифратора 73, сигналы с которых вызывают соответственно сброс регистра 14 режима и запрос к прерыванию, поступающий в ЭШ как извещение об окончании развертывания После блока 99 осуществляется переход к блоку 93 (рассмотрен выше).

ЭВМ, получив сигналы прерывания, разгружает блок 8 памяти. Поля регистра 75 должны иметь длины: поле 5 бит для кодирования 29 управляющих сигналов, одной пустой мякро- операции и сигнала Останов, поле 75. - 4 бита для кодирования одного пустого условия и десяти обязательсчетным входом первого счетчика, счетным управлякнцим входом второго счетчика, первым управляющим входом первого регистра, первым и вторым уп равляющими входами второго регистра, первым и вторым управлякмцими входами третьего регистра, четвертый регистр первый выход которого и выход первого счетчика соединены соответственно с первым и вторым входами блока управления, и первый блок памяти, о т личающееся тем, что,с целью 11овышения информативности устрой ства, в него введены пятый регистр, мультиплексоры, второй блок памяти, третий - пятый счетчики, блоки сравнения, шина данных и дешифратор, адрес ные, первый и второй управляющие входы дешифратора являются соответст венно адресными, первым и вторым управляющими входами устройства, первы и второй выходы дешифратора соединен ны соответственно с вторым управляющим входом первого регистра и управляющим входом пятого регистра, трети выход дешифратора соединен с первыми управляющими входами первого мультиплексора и первого блока памяти, четвертый выход дешифратора соединен с вторым управляющим входом первого блока памяти, пятый выход дешифратор соединен с первыми управляющими входами второго мультиплексора и второго блока памяти, шестой - восьмой выходы дешифратора соединены соответственно с вторым управляю1цим входом второго блока памяти и управляющими входами четвертого регистра и третьего счетчика, третий и четвертый входы блока управления являются соответственно входом пуск и тактовым входом устройства, девятый - двадцать четвер- тый выходы блока управления соединены соответственно с управляющим входом первого счетчика, первым - четвертым управлякицими входами третьего мультиплексора, третьим управляющим

ных условий, поля 75 и 75 - по 7

битов для кодирования адресов 72 раз- gQ входом первого блока памяти, третьим

личных микрокоманд. Следовательно длина регистра 75 каждой микрокоманды составляет 23 разряда. /

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

Устройство для сжатия и развертывания данных, содержащее блок управления, первый - восьмой выходы котог

55

управляю1цим входом второго блока памяти, суммирукицим и вычитающим входами четвертого счетчика, суммирующим и вычитающим входами пятого счетчика, входом установки в О четвертого регистра, счетным входом третьего счетчика и являются первым, вторым и третьим выходами устройства, двадцать пятый выход блока управле2°

соединены соответственно со

счетным входом первого счетчика, счетным управлякнцим входом второго счетчика, первым управляющим входом первого регистра, первым и вторым управляющими входами второго регистра, первым и вторым управлякмцими входами третьего регистра, четвертый регистр, первый выход которого и выход первого счетчика соединены соответственно с первым и вторым входами блока управления, и первый блок памяти, о т- личающееся тем, что,с целью 11овышения информативности устройства, в него введены пятый регистр, мультиплексоры, второй блок памяти, третий - пятый счетчики, блоки сравне ния, шина данных и дешифратор, адресные, первый и второй управляющие входы дешифратора являются соответственно адресными, первым и вторым управляющими входами устройства, первый и второй выходы дешифратора соединен ны соответственно с вторым управляющим входом первого регистра и управляющим входом пятого регистра, третий выход дешифратора соединен с первыми управляющими входами первого мультиплексора и первого блока памяти, четвертый выход дешифратора соединен с вторым управляющим входом первого блока памяти, пятый выход дешифратора соединен с первыми управляющими входами второго мультиплексора и второго блока памяти, шестой - восьмой выходы дешифратора соединены соответственно с вторым управляю1цим входом второго блока памяти и управляющими входами четвертого регистра и третьего счетчика, третий и четвертый входы блока управления являются соответственно входом пуск и тактовым входом устройства, девятый - двадцать четвер- тый выходы блока управления соединены соответственно с управляющим входом первого счетчика, первым - четвертым управлякицими входами третьего мультиплексора, третьим управляющим

gQ входом первого блока памяти, третьим

55

управляю1цим входом второго блока памяти, суммирукицим и вычитающим входами четвертого счетчика, суммирующим и вычитающим входами пятого счетчика, входом установки в О четвертого регистра, счетным входом третьего счетчика и являются первым, вторым и третьим выходами устройства, двадцать пятый выход блока управле2113

ния соединен с вторым управляющим входом первого мультиплексора и четвертым управляющим входом первого блока памяти, двадцать шестой выход блока управления соединен с третьим управляющим входом первого мультиплексора и пятым управляющим входом первого блока памяти, двадцать седь мой выход блока управления соединен с вторым управляющим входом второго мультиплексора и четвертым управляющим входом второго блока памяти, двадцать восьмой выход блока управления соединен с входами установки в О четвертого и пятого счетчиков, двадцать девятьй выход блока управления соединен с управляющхми входами четвертого и пятого счетчиков, выход третьего счетчика, второй и третий выходы четвертого регистра, первый выход четвертого счетчика, первьй выход пятого счетчика, выход первого блока сравнения, выход второго блока сравнения и выход второго счетчика соединены соответственно с пятым - двенадцатым входами блока управления, первые информационные . входы первого регистра, первого мультиплексора, второго мультиплек- сора, информационные вх-оды четвертого регистра, пятого регистра, тре- тьего счетчика, первые выходы первого блока памяти и первые выходы второго блока памяти объединены соответ ственно и подключены к шине данных, первые выходы первого регистра подключены к соответствующим первым входам первого блока сравнения .и первым информационным входам третье-

22

0 5 0

5

го мультиплексора, первые выходы второго регистра соединены с соответствующими вторыми входами первого блока сравнения, первыми .входами второго блока сравнения и вторыми информационными входами третьего мульти- Цлексора, вторые выходы второго регистра, первые выходы третьего регистра и выходы пятого регистра соединены соответственно с соответству-. ющими вторыми входами второго блока сравнения, третьими и четвертыми информационными входами третьего мультиплексора, выходы треть его мультиплексора, соединены с соответствующими вторыми информационными входами первого регистра и первыми информационными входами второго и третьего регистров, вторые выходы первого и третьего регистров соединены соответственно с соответствующими вторьпда и третьими информационными входами первого мультиплексора, выходы которого соединены с соответствующими информационными входами первого блока памяти, вторые вькоды которого соединены с соответствующими вторыми информационными входами второго и третьего регистров, выходы четвертого и пятого счетчиков соединены с соответствующими вторыми информационными входами второго мультиплексора, выходы которого соединены с соответствующими информационными входами второго блока памяти, вторые выходы которого соединены с соответствующими информационными входами четвертого и пятого счетчиков .

21 гз Z6 77

TtrllfT

28 30 3Z 34

MM

55 37 39 «/

M-M

2 «« 6

Mttft

45

.

73

74

50 51 52

I 75/ { 73г 75y 75

7

H

I

77

-c/a

Редактор A. Лежнина

Составитель М. Никуленков

Техред М.Ходанич Корректор А. Зимокосов

Заказ 6154/50 Тираж 544 Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открьггий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

fpusS

Изобретение относится к вычислительной технике и может использо- $$ 5В ваться в системах хранения, поиска и обработки данных,. Изобретение поз-, воляет повысить информативность устройства. Устройство работает в режимах сжатия данных, развертывания данных и коррекщш. Код режима записывается внешней ЭВМ в регистр 14. Управление работой устройства осуществляется по микропрограмме, хранящейся в блоке 21 управления. Устройство для сжатия и развертывания данных содержит регистры 1-4, 14, блоки 5,6 сравнения, мультиплексоры 7, 9,20, блоки 8, 19 памяти, иш- чу 10 данных, счетчики 11-13, 17, 18, депифратор 15 и блок 16 управления. 3 ил. 1 табл. ю СО ел со со фиг