Устройство для уплотнения информации

 

УСТРОЙСТВО ДЛЯ УПЛОТНЕНИЯ ИНФОРМАЦИИ, содержащее 2 первых коммутирующих ячеек, информационные входы и выхода которых являются сдответственно информационными входами и выходами устройства, о т л ичающееся тем, что, с целью .упрощения устройства, в него введены и коммутирующих ячеек и 2(и-1) мультиплексоров, входы мультиплексоров являются соответственно первыми управляющими входамиустройства , выходы мультиплексоров объединены попарно и подключены соответственно к первым входам и- 1 вторых коммутирующих ячеек, первый вход третьей коммутирующей ячейки является вторым управляющим входом устройства, вторые входы вторых и третьей коммутирующих ячеек являются соответственно третьими управляющими входами устройства, выходы вторых и третьей коммутирующих ячеек соединены соответственно с управлякадими входами первых коммути (О рующих ячеек. (Л

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

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

РЕСПУБЛИК (19) (11) 3(51) G 06 F 7/00

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3418208/18-24 (22) 05.04.82 (4b) 30.07.83. Бюл. )) 28 (72) М.С.Белков и E.À. Братальский (53) 621. 398 (088. 8) (56) 1. Авторское свидетельство СССР

)) 613320, кл. G 06 F 7/00, 1976.

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

Р 439017, кл. G 06 F 7/38, 1973 (прототип). (54 ) (57) УСТРОЙСТВО ДЛЯ УШ1ОТНБНИЯ

ИНФОРМАЦИИ, содержащее 2 " первых коммутирующих ячеек, информационные входы и выходы которых являются соответственно информационными входами и выходами устройства, о т л ич а ю щ е е с я тем, что, с целью .Упрощения устройства, в него введены и коммутирующих ячеек и 2 (и-1) мультиплексоров, входы мультиплексоров являются соответственно первыми управляющими входами устройства, выходы мультиплексоров объединены попарно и подключены соответственно к первым входам и — 1 вторых коммутирующих ячеек, первый вход третьей коммутирующей ячейки является вторым управляющим входом устройства, вторые входы вторых и третьей коммутирующих ячеек являются соответственно третьими управляющими входами устройства, выходы вторых и третьей коммутирующих ячеек соединены соответственно с управляющими входами первых коммутирующих ячеек.

1032450

Р2 РЗ БО

1 1 0

I

Н-Б4-;-7Р1

1 1 (Б4 Б5 Б6 Б7

Р4 Р5

1 1

0 1

О 1

0 О

О 1

1 О

1 1

0 О

1 О

О- О

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

Известно устройство для уплотнения информации, содержащее входной и выходной регистры и узлы сдвига на 2,4,8,...,2" входов из коммутирующих ячеек $1).

Это устройство производит уплотнение информации к (левому)краю, Но не обеспечивает кольцевого сдвига.

Отсутствие кольцевого сдвига требует введения отдельного кольцевого сдвигателя.

Наиболее близким к предлагаемому 15 яВляется устройство для уплотнения информации, содержащее первый регистр вход которого является первым вхо/

moM устройства, выход первого регистра подключен к первому входу блока 20 коммутирующих ячеек, вход второго регистра является вторым входом устройства, выход второго регистра через блок сдвига соединен с вторым входом блока коммутирующих ячеек, выход которого является выходом устройства 2).

Известное устройство позволяет реализовать одновременное уплотнение и кольцевой сдвиг информации, однако требует для управления большого количества кодов, и в случае аппаратной реализации цепей управления требует сложного узла управления. Так, для управления уплотнением восьми байтов информации требуется восемь групп по три разряда, всего 24 разряда кодов управления, причем каждый разряд является функцией нескольких (до восьми) переменных 40

В общем случае для уплотнения

И элементов исходного массива нужно (1о9 и раэрядов для управления одним элементом ) всего ИОО иразрядов.

Целью изобретения — уйрощение 45 устройства управления устройством), а именно организация одновременного выполнения уплотнения с управлением от маски и кольцевого сдвига с управлением от кода сдвига.

Маской называется двоичный коц, где единицами отмечены те байты, которые подлежат уплотнению. Таким образом,для управления уплотнением требуется всего один разряд(бит) кода упр авления, длина кода сдви ra очень мала(ф И разрядов)).

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

2(И- 1) мультиплексоров, входы мУльтнплексоров являются соответственно первыми управляющими входами устройства, выходы мультиплексоров объединены попарно и подключены соответственно к первым входам И вЂ” 1 вторых коммутирующих ячеек, первый вход третьей коммутирующей ячейки является вторым управляющим входом устройства, вторые входы вторых и третьей коммутирующих ячеек являются соответственно третьими управляющими входами устройства, выходы вторых и третьей коммутирующих ячеек соединены соответственно с управляющими входами первых коммутирующих ячеек.

На фиг. 1 представлена блок-схема устройства для уплотнения информации (восемь байтов ); на фиг. 2 функциональная схема коммутирующей ячейки типа "8В8", на фиг. 3 — пример реализации узлов управления.

Устройство содержит информационные входы 1 и выходы 2, коммутирующие ячейки 3 — 39, первую и вторую группы управляющих входов 4 и 5, четыре узла 6-9 управления и три коммутирующих ячейки 10 — 10> управления.

Коммутирующие ячейки содержат восемь мультиплексоров типа "8В1" kфиг.2).

Узлы 6-9 управления формируют коды уплотнения к центру, имеющие смысл

"откуда взять". Эти узлы могут быть реализованы известными методами логического синтеза в соответствии с табл. 1-4 истинности. На третью группу управляющих входов подается код 00001111.

Т а б л и ц а 1(Узел 6) М-Р2, 3 Н- БО4«3 Р 1

Б1 Б2 БЗ

О 0 1 1 О О

0 1 1 0 О 1

0 1 0 0 1

Т а б л и ц а 2 (узел7) /

1032450

М-Р 1+3

Н-БО.а-З P 2

Р1 Р2 PÇ

БО Б1 Б2 БЗ

Н-Б4+7Р2

М-Р4+6

Р4 Р5 Рб

Б4 Б5 Бб Б7

О О О

О О 1

О 1 О

О 1 1

1 О О

1 О 1

1 1 О

1 1 1

1 О 1 О

О 1 1 О

1 1 О О

1 О 1 О

О 1 О 1

О О 1 1

0 1 1 О

О 1 О 1

Т а б л и цаЗ(узел8) О О О 1 О 1 О

О О 1 О 1 О 1

О 1 О 1 1 О О

О 1. 1 1 О О 1

1 О О 1 О О 1

1 О 1 О. О 1 1

1 1 О 1 О 1 О

1 1 1 О 1 О 1

Та бл ица4(узел9 е ™

В табл. 1-4 обозначены:

М-РО 7 — маска, разряды О -7;

H-Б0в7Р1,2 — номера разрядов маски, байты 0+7 разряды 1,2.

Из табл. 1-4 видно, что все разряды кодов управления зависят от малого числа переменных (1-3 переменных)и их реализация не вызывает трудностей.

Пример реализации узлов 6-9 с помощью мультиплексоров приведен на фиг. 3.

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

45 сива на два плотных подмассива, под управлением единиц и нулей маски.

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

B исходном состоянии на входы 1 подаются коды информации А-БО 7Р0 8 (восемь байтов БО- -7 по девять разрядов P0 8, на входы 4,5 — коды управления: маска уплотнения M-РО-з-7 и код сдвига СД-Р0 2. Сначала на выходах узлов 6-9 и ячеек 10л — 10 формируются коды У-Г07 Р02, которые поступают на входы коммутирующих ячеек Зл — 3 q, затем ячейки 3 в Зу выполняют требуемую коммутацию и выдают уплотненные коды В-БО 7РО+8.

Поясним подробней работу узлов управления. Уплотнение заключ ется в плотном, без зазоров, расположении элементов информации (байтов), отмеченных единицами маски, с сохранением исходного порядка следования.

Сдвиг производится влево по кольцу с переходом от первой позиции к последней. Уплотнение и сдвиг производятся одновременно путем формирования обобщенных управляющих кодов У-ГО-;7РО+-2.

В узлах 6-9 производится формирова— ние вспомогательных управляющих кодов, которые обеспечивают уплотнение всех байтов H-БОз-7Р1, 2, к цент-. ру, т.е. для байтов ВО 3 слева направо, к позиции 3, для байтов Б4-в-7 справа налево, к позиции 4. Уплотнение в каждой половине производится независимо, поэтому формирование этих кодов существенно упрощается. Далее коды Н-БОм-7Р1, 2, сдвигаются с помощью ячеек 10л — 10 под управлением кода сдвига СД-РО+-2. При этом к ним добавляется старший разряд

Н-EO+7P0=00001111. В результате формируются обобщенные управляющие коды У-ГОь7РО-ь2, которые обеспечивают одновременное уплотнение с кольцевым сдвигом, одинаковое для всех разрядов. На выходах ячеек

З вЂ” З под действием этих кодов формируется результирующий код

В-БОе.7РОе-8.

Работа устройства поясняется следующим примером.

Пусть подан код маски М-РО+7

01010011 и код сдвига СД-РО 2

=010.

На выходе узлов 6-9 формируются коды в соответствии с табл. 1-4.

Н-БО-е-7Р1=10011100, Н-Б0- -7Р2=00110110.

На выходе ячеек,10л — 10 форми3 руются коды

У-ГО.а7Р0=00111100, У-ГО@-7Р1=01110010, У-ГОе-7Р2=11011000, т.е. У-ГО+-7PO+2$001 011,110, 111, 101, 100, 010, 000 . Ha выходе уст1032450

У-БО+ 7%Я ройства В-БО ь7Р0-8=А-Б1, 3, 6, 7, 5, 4, 2, 0Р0-8.

Таким образом, произведено уплотнение к левому краю всех байтов, помеченных единицами маски. Одновременно пройэведено уплотнение к правому краю всех байтов, помеченных нулями маски. Аналогично может быть организовано уплотнение к любой границе °

В частности, возможна организация кольцевого сдвига без уплотнения, для этого достаточно подать код сдвига и маску "все 1". При подаче кода маски "все О" на выходе устройства также выдается код

Ивсе О и °

Следует отметить допол ни тель ные воэможности устройства. Устройство может осуществлять оцифровку единиц маски, т.е. выдачу плотного массива номеров всех ее единиц. Для этой цели следует на информационные входы устройства подать двоичные коды позиций маски: О, 1, 2,. ° .,7. Эта операция представляет значительный интерес в устройствах одновременной обработки нескольких запросов в устройствах прерывания.

Иэ рассмотренных примеров следует правильность функционирования устройства, т.е. воэможность выполнения одновременного уплотнения и кольцевого сдвига под действием маски и. кода сдвига. В устройстве удалось существенно уменьшить количество разрядов кодов управления примерно до одного разряда на элемент информации (байт) . Каждый разряд кода управления формируется как функция не более чем трех переменных (раэря10 дов маски). Затраты аппаратуры на реализации узлов управления сравнительно невелики. Устройство имеет высокое быстродействие. Управляющие коды формируются эа время, равное 5 задержке двух каскадов логических элементов, коммутация информации производится за время, равное задержке одного каскада логики.

Таким образом, достигнута цель упрощение управления устройства.

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

10 32450

Р2

0,1 — логический нояь, единица

Фиа. 3

ВНИИПИ Заказ 5401/52 Тираж 706 Подписное

Филиал ППП "Патент", г,ужгород,ул.Проектная,4