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

 

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

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

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

РЕСПУБЛИН

/28 (5D 4

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3951830/24-24 (22) 26,07.85 (46) 15.12.87. В|оп. ¹ 46 (71) Азербайджанский политехнический институт им. Ч. Ильдрыма (72) Т.M. Аскеров, Ш.Ш. Гахраманов, Ч.Д. Абидов и M.M, Дамадаев (53) 621.398(088.8) (56) Авторское свидетельство СССР № 934523, кл. G 08 С 15/06, 1980.

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

¹- 991471, кл, G 08 С 15/06, 1981. (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ И РАЗВЕРТЫВАНИЯ ДАННЫХ (57) Изобретение относится к вычислительной технике и может использо„.,SU,» 1359791 А1 ваться в системах хранения, поиска и обработки данных,. Изобретение позволяет повысить информативность устройства. Устройство работает в режимах сжатия данных, развертывания данных и коррекции. Код режима записывается внешней ЭВМ в регистр 14.

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

16 управления. 3 ил. 1 табл.

11 " 1 т 2

М-600070004

0300ЕС-1020

230355060НА

ИРИ-3-124

M-6000...

M-7000...

М-4030 ° ..

М-400. ° ..

ЕС-1020 ..

ЕС-1022..

0 (последовательность

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

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

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

Устройство для сжатия и развертывания данных содержит (фиг.1) пер- . 15 вый - третий и пятый регистры 1-4, первИй и второй блоки 5 и 6 сравнения, третий мультиплексор 7, первый блок 8 памяти, первый мультиплексор

9, шину 10 данных, первый — третий 20 счетчики 11-13, четвертый регистр 14 режима, дешифратор 15, блок 16 управления, четвертый и пятый счетчики, 17 и 18, второй табличный блок 19 памяти, второй мультиплексор 20, вы- 25 ходы 21-49 и входы 50-61 блока управления.

Блок управления содержит (фиг.2) элементы И 62-71, элемент ИЛИ 72, дешифраторы 73 и 74, регистр 75, эле- 30 мент НЕ 76, блок 77 постоянной памяти, триггер 78 и элемент И 79. На

Фиг.3 позициями 80-105 обозначены

l блоки микропрограммы работы блока управления, 35

Блок 77 постоянной памяти предназначен для хранения микропрограммы.

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

Устройство работает под управлением 3ВМ (например, микро-3ВМ

CM-1800) с трехшинной архитектурой.

Теоретическое обоснование работы устройства следующее.

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

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

= (Ф;)„.;„, где И вЂ” число сжатых

Фраз .

В таблице показан пример сжатия и развертывания данных, состоящих из

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

1359791

Продолжение таблицы

ЕС-1030 ..

ЕС-1033..

ЕС-1035..

ЕС-1050., ЕС-1060

НАИРИ вЂ ..

НАИРИ-3-1

НАИРИ-3-2

13

6 1

8 байтов 8 байтов

НАИРИ-4 ..

135 байтов

42 байта

Всего

Посимвольное сравнение первой 25 фразы Ф„с нулевой фразой ф показывает, что ф не имеет цепочку совпа1

1 дающих левых символов и поэтому 1

=О. Все шесть существенных символов ф рассматриваются как сжатая Йорма др ! о фразы и поэтому 1" =6, ф „=<"<"1 -60007, фсобразует первые шесть символов последовательности У, Зятем фраза Ф сравнивается с фразой ф.и устанавливается, что Ф имеет цепочку - 11- > сов- З5 падающих символов и поэтому 1 =2. Ос—

1 тавшаяся. цепочка четырех существенных символов фразы принимается как ее сжатая форма, т.е. Ф =(7000 7 образует следующие четыре символа по- 4p следовательности. Таким же образом сжимаются все остальные фразы, в результате чего формируются таблица

L и последовательность F.

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

1 ф, как и при сжатии (в рассматриваемом примере цепочка пробелов).

Для развертывания первой фразы 5р ф„используются 1 и 1 . Так как 1 =

1

=О, то ф,не имеет никаких символов, содержащихся в базовой фразе, а 1"=

=6 показывает, что шесть первых символов последовательности F принадлежат фразе Ф,, т.е, Ф, = И-6000?, Для развертывания второй фразы > используются 1 „ и 1 . Тдк как 1

2 1 2

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

1 =4, то последующие четыре символа фразы ф содержатся в последовательности F. Этими символами являются

Ф =<7000 >. Следовательно, Ф,. = ф, 4 =

=

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

Режим работы устройства задается

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

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

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

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

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

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

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

MHKpoI

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

В исходном состоянии регистр 75 40 микрокоманды находится в нулевом состоянии (код пустой микрооперации в поле 75„, код пустого условия в поле

75, нулевые адреса в полях 75 и

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

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

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

75. Эта микрокоманда условного перехода содержит в поле 75 g код условия

1 е сжатия, в поле 75 адрес первой микрокоманды блока 82, в поле 75 адрес второй микрокоманды блока 8!. При этом возбуждается первый выход дешифратора 74, соединенный с первым входом элемента И 62, второй вход которого соединен с выходом сжатия регистра 14 режима. Если выход

"Сжатие" регистра 14 возбужден, то срабатывают элементы И 62, ИЛИ 72, выходной сигнал последнего передает содержимое поля 75> регистра 75 на адресный вход блока 77 памяти.

В противном случае элементы И 62

ИЛИ 72 не срабатывают и выходной сигнал элемента НЕ 76 передает содержимое поля 75д регистра 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, на адресный вход блока

1359791

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

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

В режиме сжатия ЭВМ загружает в блок 8 памяти массив фраз, подлежащих 15 сжатию, в регистр 1 — базовую фразу, в регистр 4 — пробел, в счетчик 13 количество фраз в блоке 8 памяти, в регистр 14 — код режима сжатия.

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

Блок 82 (начало реализации режима

"Сжатие" ) состоит из одной микроко- 25 манды безусловного перехода, в поле

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

Первый тактовый сигнал (с момента начала режима сжатия) считывает эту микрокоманду из блока 77 в регистр

75, после чего начинается ее реализация. 35

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

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

Первая, вторая, третья и четвертая микрокоманды блока 83 содержат в по- 5р ле 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 и

9

135979 на адресный вход блока 77 поступает, содержимое поля 75 . Следовательно, если регистр 2 не пуст, то следующим тактовым сигналом считывается из блоФ 5 ка 77 в регистр 75 вторая микрокоманда блока 85. Она содержит в поле 75 2 код условия обнуления счетчика 11, в полях 75 и 75„ — соответственно адреса первых микрокоманд блоков 86 1ð и 87. По этой микрокоманде возбужцается шестой выход дешифратора 74, соединенный с первым входом элемента И 67, второй вход которого соединен с выходом счетчика 11. Если содержимое счетчика 11 равно нулю, то срабатывают элементы И 67, ИЛИ 72, в результате чего содержимое поля 75 регистра 75 передается на адресный вход блока 77. В противном случае срабатывает элемент НЕ 76 и на адрес-, ный вход блока 77 поступает содержимое поля 754.

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

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

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

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

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

2 на один байт влево с приемом содержимого мультиплексора 7, сдвиг со1

10 держимого регистра 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.

Каждый цикл реализации блоков 84

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

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

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

91 и 90.

Когда блок 89 получает управление, очередной тактовый сигнал считывает 4О указанную микрокоманду из блока 77 в регистр 75. При этом возбуждается седьмой выход дешифратора 74, который соединен с первым входом элемента

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

Блок 90 состоит из трех микрокоманд безусловного перехода, в поле

75 каждой из которых содержится ад- о рес следующей за ней микрокоманды.

Очередные три тактовых сигнала (после передачи управления блоку 90) после91

12 довательно считывают эти микрокоманды из блока 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.

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

13

1359791

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

75< каждой из которых содержится адрес следующей за ней микрокоманды. 10

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

75„ код микрооперации "Останов" а в поле 75 < — адрес нулевой ячейки блока 77 (адрес первой микрокоманды блока 81 микропрограммы) . Последний тактовый сигнал считывает эту микрокоманду из блока 77 в регистр 75.

При этом возбуждается двадцать первый выход дешифратора 73, сигнал с которого сбрасывает триггер 78, и тем самым прекращается поступление тактовых сигналов в блок 77. 35

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

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

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

В

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

75< этой микрокоманды содержится код условия обнуления счетчика 11, а в полях 75З и 75 — соответственно адреса первых микрокоманд первой и второй групп микрокоманд безусловного перехода блока 94. Реализация этой микрокоманды аналогична второй микрокоманде блока 79. Если содержимое счетчика 11 обнулено, то следующие три тактовых сигнала последовательно считывают из блока 77 в регистр 75 микрокоманды первой группы блока 94, в поле 75 каждой из которых содер4 жится адрес следующей за ней микрокоманды. Первая, вторая, третья микрокоманды этой группы содержат в поле

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 управления, получив сигнал "РазверIt

5 тывание от регистра 14, начинает реализовать блоки 95-105 микропро-. граммы.

Блок 95 состоит из трех микрокоманд безусловного перехода, в поле 1р

75 каждой из которых содержится ад4 рес следующей за ней микрокоманды.

Первые три тактовых сигнала (считая с начала режима развертывания) последовательно считывают микрокоманды 15 блока 95 из блока 77 в регистр 75.

Эти микрокоманды содержат в поле 75„ коды, по которым возбуждаются соответственно четвертый, двадцать второй и первый выходы дешифратора 73, 2О сигналы с которых вызывают соответственно чтение одной сжатой фразы из блока 8 памяти, прием этой фразы в регистр 3 и запись в счетчик 11 длины регистра 3. После блока 95 выпол- 25 няется блок 96, состоящий из трех микрокоманд безусловного перехода, в поле 75 д каждой из которых содержится адрес следующей за ней микрокоманды. Четвертый — шестой тактовые сиг- 30 налы последовательно считывают эти микрокоманды из блока 77 в регистр

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

96 выполняется блок 97, состоящий из одной микрокоманды условного перехода. Седьмой тактовый сигнал считы- 45 вает эту микрокоманду из блока 77 в регистр 75. Она содержит в поле 75 код условия равенства нулю содержи-! мого счетчика 17 (условие отсутствия левой цепочки символов, содержащихся БО в базовой фразе), в полях 75> и 75— соответственно адреса первых микрокоманд блоков 92 и 93. При выполнении ,этой микрокоманды возбуждается девя.тый выход дешифратора 74, соединенный с первым входом элемента И 70, второй вход -которого соединен с выходом счетчика 17. Если содержимое счетчика 17 равно нулю, то срабатывают

91

16 элементы И 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 д соответственно адреса первой микрокоманды блока 102 и второй микрокоманды блока 99. Очередной тактовый сигнал считывает эту микрокоманду из блока 77 в регистр 75.

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

18. Если содержимое счетчика 18 рав-. но нулю, то срабатывают элементы

И 71, ИЛИ 72 и на адресный вход блока 77 поступает содержимое поля 75, В противном случае срабатывает эле19

1359791

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

1 через мультиплексор 9 в блок 8 памяти и уменьшение содержимого счетчика 13 на единицу.

Иикрокоманда условного перехода 1р блока 92 содержит в полях 75<- 75

Ф соответственно код условия обнуления счетчика 13 (условие развертывания всех фраз), адрес первой микрокоманды блока 105 и адрес первой микроко- 15 манды блока 96. Она реализуется таким же образом, как и последняя микрокоманда блока 91. Следовательно, если содержимое счетчика 13 не равно нулю, то осуществляется возврат к 20 блоку 96 (начало развертывания следующей фразы), в противном случае— к блоку 105.

Блок 105 состоит иэ двух микрокоманд безусловного перехода, в поле 15

754 каждой Hs которых содержится адрес следующей за ней микрокоманды.

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

После блока 99 осуществляется переход к блоку 93 (рассмотрен выше). 4о

ЭВМ, получив сигналы прерывания, разгружает блок 8 памяти. Поля ре- У гистра 75 должны иметь длины: поле в

75,— 5 бит для кодирования 29 управ- P лянФщих сигналов ° Одной пустой микро 45 операции и сигнала "Останов", поле

75 — 4 бита для кодирования одного д и пустого условия и десяти обяэательв ных условий, поля 75 и 75 — по 7 битов для кодирования адресов 72 раз- M в личных микрокоманд. Следовательно, У длина регистра 75 каздой микрокоманды составляет 23 разряда., д

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

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

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

ый выходы блока управления соединеы соответственно с управляющим вхоом первого счетчика, первым — четертым управляннцимн входами третьего мультиплексора, третьим управляющим ходом первого блока памяти, третьим правляющнм входом второго блока памяти, суммирующим и вычнтающим вхоами четвертого счетчика, суммирующим и вычитающнм входами пятого счетб5 чика, входом установки в "0" четвеРтого регистра, счетным входом третьего счетчика и являются первым, вторым и третьим выходами устройства, двадцать пятый выход блока управле21

22

1359791 ния соединен с вторым управляющим входом первого мультиплексора и четвертым управляющим входом первого блока памяти, двадцать шестой выход блока управления соединен с третьим управляющим входом первого мультиплексора и пятым управляющим входом первого блока памяти, двадцать седь" мой выход блока управления соединен о с вторым управляющим входом второго мультиплексора и четвертым управляющим входом второго блока памяти, двадцать восьмой выход блока управления соединен с входами установки 15 в "0 четвертого и пятого счетчиков, . двадцать девятый выход блока управления соединен с управляющими входами четвертого и пятого счетчиков, выход третьего счетчика, второй и 20 третий выходы четвертого регистра, первый выход четвертого счетчика, первый выход пятого счетчика, выход первого блока сравнения, выход второго блока сравнения и выход второго счетчика соединены соответственно с пятым — двенадцатым входами блока управления, первые информационные входы первого регистра, первого мультиплексора, второго мультиплексора, информационные входы четвертого регистра, пятого регистра, тре- тьего счетчика, первые выходы первого блока памяти и первые выходы второго блока памяти объединены соответ- 35 ственно и подключены к шине данных, псрвые выходы йервого регистра подключены к соответствующим первым входам первого блока сравнения и первым информационньм входам третье- 40 го мультиплексора, первые выходы второго регистра соединены с соответствующими вторыми входами первого блока сравнения, первыми, входами второго блока сравнения и вторыми информационными входами третьего мультиплексора, вторые выходы второго регистра, первые выходы третьего регистра и выходы пятого регистра соединены соответственно с соответству-. ющими вторыми входами второго блока сравнения, третьими и четвертыми информационными входами третьего мультиплексора, выходы третьего мульти-. плексора. соединены с соответствующими вторыми информационными входами первого регистра и первыми информационными входами второго и третьего регистров, вторые выходы первого и третьего регистров соединены соответственно с соответствующими вторыми и третьими информационными входами первого мультиплексора, выходы которого соединены с соответствующими информационными входами первого блока памяти, вторые выходы которого соединены с соответствующими вторыми информационными входами второго и третьего регистров, выходы четвертого и пятого счетчиков соединены с соответствующими вторыми информационными входами второго мультиплексора, выходы которого соединены с соответствующими инфо рма ционньии входами второго блока памяти, вторые выходы которого соединены с соответствующими информацианньми входами четвертого и пятого счетчиков .

1359791

1359791

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

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

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

Заказ e154/50 Тираж 544 Подпис ное

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

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

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