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

 

1. УСТРОЙСТВО ДЛЯ СЖАТИЯ И,ВОССТАНОВЛЕНИЯ ИНФОРМАЦИИ, содержащее блок управления, первый выход которого подключен к первому входу первого регистра, второй выход блока управления подключен к первому входу блока памяти, второй и третий регистры, первый блок сравнения, блок элементов ИЛИ, отличающееся тем, что, с целью повышения пропускной способности устройства , в него введены блоки регистров, четвертый регистр, блок вычитания, блоки элементов И, блок элементов НЕ, второй блок сравнения, узел формирования вектора, узел формирования входной последовательности, дешифратор, первбй вход первого блока регистров является информационным входом устройства, второй вход которого подключен к третьему выходу блока управления, выходы первого блока регистров подключены к первым нходпм учла формирования вектора и к первьм входам блока вычитания, выход которого подключен к первому входу второго блока регистров, второй вход которого .подключен к четвертому выходу блока управления, выход второго блока регистров подключен к первому входу первого блока, элементов И и через блок элементов Н& к первому входу второго блока элементов И, второй вход которого подключен к пятому выходу блока управления , выход второго блока элементов И подключен через дешифратор к первому входу блока управления, шестой выход которого подключен к второму входу первого блока элементов И, выход которого подключен к первому (Л входу третьего блока регистров, второй вход которого подключен к седьмому выходу блока управления, выходы третьего блока регистров подключены через узел формирования входной последовательности к входу четвертого блока регистров, первый и второй вхо4 СО Ю QD ды которого подключены соответственно к восьмому и девятому выходам блока управления, выход четвертого блока регистров подключен к первому % входу третьего блока элементов И, сл второй вход которого подключен к десятому выходу блока управления, выход третьего блока элементов И подключен к первому входу блока элементов ИЛИ, выход которого подключен к второму входу блока памяти, третий вход которого подключен к одиннадцатому выходу блока управления , двенадцатый выход которого подключен к первому входу счетчика, выход счетчика подключен к четвертому входу блока памяти, первому входу

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

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

РЕСПУБЛИК (39) (!!) 4(5)) С 08 С 15 06

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

К АВТОРСИОМ,Ф СВИДЕТЕЛЪС ГВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbtTMA (21) 3665914/24-24 (22) 28.1.1 83 (46) 07.04.85. Бюл. )) 13 (72) Н.П. Вайда, В.П.Семеренко, Г.К. Сироцинский и В.Т.Шпилевой (71) Винницкий политехнический институт и Специальное проектно-конструкторское и технологическое бюро реле и автоматики (53) 621.398(088.8) (56) 1. Авторское свидетельство СССР 431532, кл. G 08 С 19/16, 1975.

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

)) 934523, кл. С 08 С 15/06, 1982 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛЯ СЖАТИЯ

И,ВОССТАНОВЛЕНИЯ ИНФОРМАЦИИ, содерL жащее блок управления, первый выход которого подключен к первому входу первого регистра, второй выход блока управления подключен к первому входу блока памяти, второй и третий регистры, первый блок сравнения, блок элементов ИЛИ, о т л и ч а ющ е е с я тем, что, с целью повышения пропускной способности устройства, в него введены блоки регистров, четвертый регистр, блок вычитания, блоки элементов И, блок элементов

HF., второй блок сравнения, узел формирования вектора, узел формирования входной последовательности, дешифратор, первый вход первого блока регистров является информационным входом устройства, второй вход которого подключен к третьему выходу блока управления, выходы первого блока регистров подключены к первым нходам учла Формирования вектора и к первым входам блока вычитания, выход которого подключен к первому входу второго блока регистров, второй вход которого подключен к четвертому выходу блока управления, выход второго блока регистров подключен к первому входу первого блока, элементов И и через блок элементов НЕ. к первому входу второго блока элементов И, второй вход которого подключен к пятому выходу блока управления, выход второго блока элементов И подключен через дешифратор к первому входу блока управления, шестой выход которого подключен к второму входу первого блока элементов И, выход которого подключен к первому входу третьего блока регистров, второй вход которого подключен к седьмому выходу блока управления, выходы третьего блока регистров подключены через узел формирования входной последовательности к входу четвертого блока регистров, первый и второй входы которого подключены соответственно к восьмому и девятому выходам блока управления, выход четвертого блока регистров подключен к первому входу третьего блока элементов И, второй вхбд которого подключен к десятому выходу блока управления, выход третьего блока элементов И подключен к первому входу блока элементов ИЛИ, выход которого подключен к второму входу блока памяти, третий вход которого подключен к одиннадцатому выходу блока управления, двенадцатый выход которого подключен к первому входу счетчика, выход счетчика подключен к четвертому входу блока памяти, первому входу

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

2. Устройство но п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит распределители импуль. сов, регистры, генератор импульсов, триггеры, элемент задержки, счетчик, элементы ИЛИ и элементы И, выход генератора импульсов подключен к первым входам первого — шестого элемен-, тов И, выходы первого — четвертого элементов И подключены к входам соответствующих распределителей импульсов, первые выходы первого и второго распределителей импульсов подключены к первым входам соответственно седьмого и восьмого элементов И, выходы которых подключены к первому и второму входам первого элемента ИЛИ, выход первого элемента ИЛИ подключен к входу первого регистра, выходы которого подключены к вторым входам соответственно четвертого — первого элементов И, первый выход четвертого распределителя импульсов подключен к первому входу второго элемента ИЛИ, второй выход четвертого распределителя импульсов подключен к первому входу счетчика, третий выход четвертого распределителя импульсов подключен к первому входу третьего элемента

ИЛИ и первому входу четвертого элемента ИЛИ, выход которого подключен к первому входу первого триггера, второй вход которого подключен к выходу пятого элемента ИЛИ, второй выход первого распределителя импульсов и первый выход третьего распределителя импульсов подключены соответственно к третьему и четвертому входам первого элемента ИЛИ, третий выход первого и второй выход третьего распределителей импульсов подключены соответственно к второму и третьему входам второго элемента

ИЛИ, четвертый вход которого подключен к четвертому выходу первого распределителя импульсов, пятый выход первого распределителя импульсов и третий выход третьего распределителя импульсов подключены соответственно к первому и второму входам пятого элемента ИЛИ и к второму и третьему входам третьего элемента ИЛИ, выход которого подключен к первому входу шестого элемента ИЛИ и входу элемента задержки, шестой выход первого распределителя импульсов подключен к четвертому входу третьего элемента ИЛИ и второму входу четвертого элемента ИЛИ, седьмой выход первого и четвертый выход третьего распределителей импульсов подключены соответственно к первому и второму входам седьмого элемента

ИЛИ, второй выход второго распреде1149295 лителя импульсов подключен к третьему входу седьмого элемента ИЛИ и второму входу счетчика, выход которого подключен к третьему входу первого элемента ИЛИ, восьмой выход первого распределителя импульсов подключен к первому входу восьмого элемента

ИЛИ, выход которого подключен к первому входу второго триггера,,второй вход которого подключен к пятому выходу третьего распределителя импульсов, девятый выход первого распределителя импульсов и третий выход второго распределителя подключены соответственно к первому и второму входам девятого элемента

ИЛИ, десятый выход первого распределителя импульсов подключен к первому входу десятого элемента ИЛИ и первым входам второго и третьего регистров, вторые входы которых подключены к четвертому выходу второго распределителя импульсов, второй вход десятого элемента ИЛИ подключен к первому входу пятого распределителя импульсов,,второй выход которого подключен к второму входу восьмого элемента ИПИ, третий выход которого йодключен к первым входам третьего и четвертого триггеров, выход третьего триггера подключен к второму входу пятого элемента И, выход которого подключен к входу пятого распределителя .импульсов, выход четвертого триггера подключен к второму входу шестого элемента И, выход которого подключен к входу шестого распределителя импульсов, первый и второй выходы которого подключены к второму и четвертому входам соответственно шестого и седьмого элементов ИЛИ, третий выход шестого распределителя импульсов подключен к первым входам пя.ого и шестого триггеров, выход пятого триггера подключен к первому входу девятого элемента И, второй вход которого подключен к четвертому выходу шестого распределителя импульсов, объединенные вторые входы седьмого и восьмого элементов И, второй вход четвертого триггера, вторые входы пятого и шестого триггеров, шестой вход первого элемента ИЛИ и второй вход третьего триггера являются соответственно первым - пятым входами блока управления, выход элемента задержки, выход второго элемента ИЛИ, одиннадцатый выход первого распределителя импульсов, выход девятого элемента ИЛИ, выход третьего регистра, выход второго регистра, пятый выход второго распределителя импульсов, второй выход четвертого распределителя импульсов, шестой выход второго распределителя импульсов, первый выход первого триггера, пятый выход шестого распределителя импульсов, выход деся-, того элемента ИЛИ, шестой выход шестого распределителя импульсов, второй выход первого триггера, выход шестого триггера, выход шестого элемента ИЛИ, выход седьмого элемента

ИЛИ, выходы второго триггера, седьмой выход шестого распределителя импульсов и выход девятого элемента

И являются соответственно первым— двадцатым выходами блока управления.

3. Устройство по и. 1, о т л ичающая с я тем, что узел формирования вектора содержит блоки элементов И, блок элементов ИЛИ, блок регистров, блоки сумматоров, элементы И и элемент ИЛИ, выход первого блока элементов И подключен к первому входу блока элементов ИЛИ, выходы которого подключены к соответствующим первым входам блока регистров, выход первого элемента И подключен к первому входу элемента

ИЛИ, выход которого подключен к второму входу блока регистров, первый выход блока регистров подключен к первому входу второго блока элементов И и первому входу первого блока сумматоров, выход каждого блока сумматоров подключен к первому входу последующего блока сумматоров, группа выходов блока регистров подключена к вторым входам соответствующих блоков сумматоров, кроме последнего, группа выходов блока регистров, кроме последнего выхода группы, подключена к вторым входам второго блока элементов И, выход которого подключен к второму входу блока элементов ИЛИ, выход последнего блока сумматоров подключен к первому входу второго элемента И, выход которого подключен к второму входу элемента ИЛИ, первый вход первого блока элементов И и первый вход первого элемента И, второй вход последнего блока сумматора, третий и четвертые входы блока регистров и вторые объе1149295

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

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

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

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

Недостаток этого устройства сос" тоит в невозможности восстановления сжатой информации.

Наиболее близким к предлагаемому является устройство для сжатия и восстановления информации, содер4 жащее блок памяти устройства, первый выход которого соединен с первым выходом устройства, блок сравнения информационных комбинаций, регистр формирователя обратного кода группы, первый вход первого блока сумматоров первой группы объединен с входом первого формирователя обратного кода группы, выход каждого формирователя обратного кода группы подключен к первому входу соответствующего блока сумматоров второй группы, вторые входы блоков сумматоров вто рой группы кроме последнего, объединены с вторыми входами соответствующих блоков сумматоров первой группы, первый вход первого блока сумматора первой группы, вторые входы каждого блока сумматора первой группы и второй вход последнего блока сумматора второй группы являются входами узла формирования входной последовательности, вход первого формирователя обратного кода группы и выход каждого .блока сумматора второй группы являются выходами узла формирования входной последовательнос ти. комбинаций, регистр памяти постоянных информационных комбинаций, регистр памяти единиц, блок управления, блок элементов ИЛИ, формирователь пакетов первичной информации, формирователь информационных комбинаций

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

3 11492 с вторым входом формирователя пакетов первичной информации, объединенными вторым и третьим входами регистра памяти адреса и признака информационных комбинаций, вторым входом преобразователя пакетов неупорядоченной информации в коды, вторым входом блока памяти информации и объединенными первыми входами регистра памяти постоянных информационных комбинаций и регистра памяти единиц, вторые входы которых соединены с вторым и третьим входами устройства, выходы которых соединены с соответствующими входами формирователя информационных комбинаций, выход которого соединен с первым входом блока выдачи информации и вторым входом блока сравнения информационных комбинаций, выход .блока срав- 0 нения информационных комбинаций соединен с четвертым входом регистра памяти адреса и признака информационных комбинаций и через блок элемента ИЛК с объединенными вторым д5 входом блока управления и пятым входом регистра памяти адреса и признака информационных комбинаций, выход которого соединен r третьими входами формирователя пакетов первичной информации и блока памяти информации, второй, третий и четвертый выходы блока памяти информации соединены соответственно с объединенныки третьим входом блока управления и четвертым входом формирователя пакетов первичной информации,.вторым входом блока выдачи информации и третьим входом преобразователя пакетов неупорядо40 ченной информации в коды, первый а и второй выходы которого соединены с четвеРтым входом блока памяти информации и третьим входом блока выдачи информации, первый, второй и третий. выходы которого соединены 45 соответственно с пятым входом формирователя пакетов первичной информации, пятым входом блока памяти информации и вторым выходом устройства (21 .

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

95 4

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

Поставленная цель достигается тем, что в устройство, содержащее блок управления, первый выход которого подключен к первому входу первого регистра, второй выход блока управления подключен к первому входу блока памяти, второй и третий регистры, первый блок сравнения, блок элементов ИЛИ, введены, блоки регистров, четвертый регистр, блок вычитания, блоки элементов И, блок элементов НЕ, второй блок сравнения т узел формирования вектора, узел фор-, нрования входной последовательности, дешифратор, первый вход первого блока регистров является информационным входом устройства, второй вход которого подключен к третвему выходу блока управления, выходы первого блока регистров подключены к первым входам узла формирования вектора н к первым входам блока вычитания, выход которого подключен к первому входу второго блока регистров, второй вход которого подключен к четвертому выходу блока управления, выход второго блока per.èñòðoâ подключен к первому входу первого блока элементов И и через блок элементов НŠ— к первому входу второго блока элементов И, второй вход которого подключен к пятому выходу блока управления, выход второго блока элементов И подключен через дешифратор к первому входу блока управления, шестой выход которого подключен к второму входу первого блока элементов И, выход которого подключен к первому входу третьего блока регистров, второй вход которого подключен к седьмому выходу блока управления, выходы третьего блока регистров подключены через узел формирования входной последовательности к входу четвертого блока реги1 стров, первый и второй входы которого подключены соответственно к вось" мому и девятому выходам блока управления, выход четвертого блока регистров подключен к первому входу третьего блока элементов И, второй вход которого подключен к десятому выходу блока .управления, выход третьего блока элементов И подключен к первому входу блока элементов ИЛИ, I149295 выход которого подключен к второму входу блока памяти, третий вход которого подключен к одиннадцатому выходу блока управления, двенадцатый, выход которого подключен к первому 5 входу счетчика, выход счетчика подключен к четвертому входу блока памяти, первому входу первого блока сравнения и второму входу первого регистра, выход которого подключен к-второму входу первого блока сравнения, выход которого подключен к второму входу блока управления, выход блока памяти подключен к первому входу второго регистра, второй 15 вход которого подключен к тринадцатому выходу блока управления, выход второго регистра подключен к первому входу второго блока сравнения и первому входу четвертого 20 блока элементов И, выход второго блока сравнения подключен к третьему входу блока управления, второй вход второго блока сравнения подключен к выходу третьего регистра и 25 первому входу пятого блока элементов И, второй вход которого подключен к четырнадцатому выходу блока управления, выход пятого блока элементов И подключен к второму входу зО блока элементов ИЛИ, второй вход четвертого блока элементов И подключен к пятнадцатому выходу блока управления, выход четвертого блока элементов И подключен к второму

35 входу узла формирования вектора, третий вход которого подключен к шестнадцатому выходу блока управления и второму входу счетчика, четвертый и пятый входы узла формирова- 4> ния вектора подключены соответственно к семнадцатому и восемнадцатым выходам блока управления, выходы узла формирования вектора подключены к вторым входам блока вычи- . 4 тания и первым входам четвертого регистра, второй вход которого подключен к девятнадцатому выходу блока управления, выход четвертого регистра подключен к первому входу шес- 50 того блока элементов И, второй вход которого подключен к двадцатому выходу блока управления, четвертый и пятый входы которого являются соответственно первым и вторым управляющими входами устройства, выход шестого блока элементов И является ин" формационным выходомустройства.

Кроме того, в блок управления введены распределители импульсов, регистры, генератор импульсов, триггеры, элемент задержки, счетчик, элементы ИЛИ и элементы И, выход генератора импульсов подключен к первым входам первого — шестого элементов И, выходы первого — четвертого элементов И подключены к входам соответствующих распределителей импульсов, первые выходы первого и второго распределителей импульсов подключены к первым входам соответственно седьмого и восьмого элементов И, выходы которых.подключены к первому и второму входам первого элемента ИЛИ, выход .первого элемента ИЛИ подключен к входу первого регистра, выходы которого подключены к вторым входам соответственно четвертого — первого элементов И, первый выход четвертого распределителя импульсов подключен к первому входу второго элемента ИЛИ, второй выход четвертого распределителя импульсов подключен к первому входу счетчика, третий выход четвертого распределителя импульсов подключен к первому входу третьего элемента ИЛИ и первому входу четвертого элемента ИЛИ, выход которого подключен к первому входу первого триггера, второй вход которого подключен к выходу пятого элемента ИЛИ, второй выход первого распределителя импульсов и первый выход третьего распределителя импульсов подключены соответственно к третьему и четвертому входам первого элемента ИЛИ, третий выход первого и второй выход третьего распределителей импульсов подключены соответственно к второму и третьему входам второго элемента ИЛИ, четвертый вход которого подключен к четвертому выходу первого распределителя импульсов, пятый выход первого распределителя импульсов и третий выход третьего распределителя импульсов подключены соответственно к первому и второму входам пятого элемента ИЛИ и к второму и третьему входам третьего элемента ИЛИ, выход которого подключен к первому входу шестого элемента ИЛИ и входу элемента задержки, шестой выход первого распределителя импульсов подключен к четвертому входу третьего элемента ИЛИ и второму входу четвер1149295 того элемента ИЛИ, седьмой выход первого и четвертый выход третьего распределителей импульсов подключены соответственно к первому и второму входам седьмого элемента ИЛИ, вто- 5 рой .выход второго распределителя импульсов подключен к третьему входу седьмого элемента ИЛИ н второму входу счетчика, выход которого подключен к третьему входу первого элемента ИЛИ, восьмой выход первого распределителя импульсов подключен к первому входу восьмого элемента ИЛИ, выход которого подключен к первому входу второго триггера, второй вход 15 которого подключен к пятому выходу третьего распределителя импульсов, девятый выход первого распределителя . импульсов и третий выход второго распределителя подключены соответствен- 20 но к первому и второму входам девятого элемента ИЛИ, десятый выход первого распределителя импульсов подключен к первому входу десятого элемента ИЛИ и первым. входам второго и третьего регистров, вторые входы .которых подключены к четвертому выходу второго распределителя импульсов, второй вход десятого элемента ИЛИ. подключен к первому входу пятого 5О распределителя импульсов, второй выход которого подключен к второму . входу восьмого элемента ИЛИ, третий выход которого подключен к первым входам третьего и четвертого тригге- >> р в, выход третьего триггера подключен к второму входу пятого элемента И, выход которого подключен к входу пятого распределителя импульсов, выход четвертого триггера подключен к второму входу шестого элемента И, выход которого подключен к входу шестого распределителя импульсов, первый и второй выходы которого подключены к второму и четвертому

45 входам соответственно шестого и седьмого элементов ИЛИ, третий выход шестого распределителя импульсов подключен к первым входам пятого и шестого триггеров, выход пятого

50 триггера подключен к первому входу девятого элемента И, второй вход которого подключен к четвертому выходу шестого распределителя импульсов, объединенные вторые входы седьмого и восьмого элементов И, второй вход четвертого триггера, вторые входы пятого и шестого триггеров, шестой вход первого элемента ИЛИ и . второй вход третьего триггера явля- ются соответственно первым — пятым входами блока управления, выход элемента задержки, выход второго элемента ИЛИ, одиннадцатый выход первого распределителя импульсов, выход девятого элемента ИЛИ, выход третьего регистра, выход второго регистра, пятый выход второго распределителя импульсов, второй выход четвертогб распределителя импульсов, шестой выход второго распределйтеля импульсов, первый выход первого триггера, пятый выход шестого распределителя импульсов, выход десятого элемента ИПИ, шестой выход шестого распределителя импульсов, второй выход первого триггера, выход шестого триггера, выход шестого элемента ИЛИ, выход седьмого элемента ИЛИ, выходы второго триггера, седьмой выход шестого распределителя импульсов и выход девятого элемента И являются соответственно первым — двадцатым выходами блока управления.

Кроме того, в узел формирования вектора введены блоки элементов И, блок элементов ИЛИ, блок регистров блоки сумматоров, элементы И и элемент ИЛИ, выход первого блока

:элементов И подключен к первому входу блока элементов ИЛИ, выходы которого подключены к соответствуюt щим первым входам блока регистров

В выход первого элемента И подключен к первому входу элемента ИЛИ, выход которого подключен к второму входу блока регистров, первый выход блока регистров подключен к первому входу второго блока элементов И и первому входу первого блока сумматоров, выход каждого блока сумматоров подключен к первому входу последующего блока сумматоров, группа выходов блока регистров подключена к вторым входам соответствующих блоков сумматоров, кроме последнего, -группа выходов блока регистров, кроме последнего выхода группы, подключена к вторым входам второго блока элементов И, выход которого подключен к второму входу блока элементов ИЛИ, выход последнего блока сумматоров подключен к первому входу второго элемента И, выход которого подключен к второму входу элемента

ИЛИ, первый вход первого блока эле1149295 I0 ментов И и первый вход первого элемента И, второй вход последнего блока сумматора, третий и четвертые входы блока регистров и вторые объединенные входы первого элемента И и первого блока элементов И и объединенные второй вход второго элемента И и третий вход второго блока элементов

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

Кроме того, в узел формирования 15 входной последовательности введены группа формирователей обратного кода и группы блоков сумматоров, выход каждого, кроме последнего блока сумматора первой группы, под- 20 ключен к первому входу последующего блока сумматора первой группы и входу соответствующего формирователя обратного кода группы, вьиод последнего блока сумматоров первой группы 25 подключен к входу последнего.форми,рователя обратного кода группы, ервый вход первого блока сумматоов первой группы объединен с входом ервого формирователя обратного ко- щ а группы, выход каждого формирователя обратного коДа группы подключен к первому входу соответствующего блока сумматоров второй группы, вторые входы блоков сумматоров второй группы, кроме последнего, объединены с вторыми входами соответствующих блоков сумматоров первой группы, первый вход первого блока сумматора первой группы, вторые входы каждого блока сумматора первой группы и второй вход последнего блока сумматора второй группы являются входами узла формирования входной последоватЕльности, вход первого формирова- щ теля обратного кода группы и выход каждого блока сумматора второй группы являются выходами узла формирова ния входной последовательности.

На фиг. 1 изображена структурная S0 схема устройства для сжатия и восстановления информации, на фиг. 2 — схема узла формирования вектора, на фиг. 3 — схема блока сумматора по модулю ш.в прямых кодах, на фиг. 4 - 5S схема узла формирования входной последовательности; на фиг. 5 — схема формирования обратного кода, на фиг. 6 — схема блока сумматора по модулю m в обратных кодах, на фиг. 7 — схема блока вычитания, на фиг. 8 — схема блока элементов И, на фиг. 9 — схема блока управления на фиг. 10 — .последовательность изменения состояний выходов первого регистра блока управления, на фиг.11последовательность изменения состояний выходов второго регистра блока управления.

Устройство для сжатия и восстановления-информации содержит блок 1 памяти, узел 2 формирования вектора, узел 3 формирования входной последовательности, блок 4 вычитания, счетчик 5, блоки 6 и 7 сравнения, блоки 8 — 11 регистров, регистры

12 — 15, блоки 16 — 21 элементов И, блок 22 элементов ИЛИ, блок 23 элементов НЕ, дешифратор 24, блок 25 управления, информационный вход 26 устройства, управляющий вход 27 и 28 устройства, информационный выход 29 устройства, блоки 30 и 31 элементов

И, элементы И 32 и 33, блок 34 элементов ИЛИ, элемент ИЛИ 35, блок

36 регистров, блок 37 сумматоров, сумматоры 38 и 39, регистр 40, элемент ИЛИ 41. Триггер 42, элементы И

43 и 44, элементы ИЛИ 45, блок 46 сумматоров, формирователь 47 обратного кода, блок 48 сумматоров, дешифратор 49, дешифратор 50, сумматоры 51 и 52, формирователи 53 и 54 обратного кода, регистр 55, элементы ИЛИ 56,и 57, триггер 58, дешифратор 59, элементы И 60 — 63, формирователь 64 обратного кода, сумматоры 65, элементы И 66 — 75, элементы ИЛИ 76 — 85, генератор 86 импульсов, регистры 87 — 89, счетчик

90, триггеры 91 — 96, элемент 97 задержки, распределители 98 — 103 импульсов.

Блок 1 памяти предназначен для приема, хранения и выдачи сжатой информации, узел 2 формирования вектора преобразует двоично-кодированный р-разрядный вектор входного информационного массива в двоичнокодированный р-разрядный вектор S(t) состояния линейной последовательностной схемы.

Узел 3 формирования входной последовательности преобразует двоично-кодированный р-разрядный вектор в двоично-кодированный вектор U(t) 295

49 12 сы другим блокам устройства. Блок

36 регистров предназначен для приема и хранения р-разрядного двоично-кодированного вектора.

Формирователи 47 обратного кода содержат (и-1) элементарных форми рователей обратного кода, каждый из которых предназначен для получения

ОбратнОгО КОда (Г),в = 3,, /„ h pB3"

10 рядной двоично-коднрованчой цифры — где g — дополне" нне до числа (m — 1), m — основание системы счисления, в которой представлена цифра G (i 1,...,h).

15 устройство работает следующим образом, От внешних источников на информационный вход 26 периодически поступают векторы из входного информацион. рп ного массива V.

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

25 х = 0,1,2,...,m-1

ll входной последовательности линейнойпоследовательностной схемы, который имеет разрядность h.

Блок 4 вычитания выполняет опе.— рации вычитания по модулю m над двоично-кодированными р-разрядными векторами. Счетчик 5 формирует адреса ячеек блока 1 памяти, в которые записывается сжатая информация.

Блок 6 сравнения предназначен для сравнения содержимого счетчика

5 с содержимым регистра 15, блок 7 сравнения — для сравнения вектора, считанного из блока 1, с вектором маркера, блок 8 регистров — для.приема и хранения в п регистрах двоичнокодированных р-разрядных векторов входной информации, блоки 9 — 10 регистров — для приема и хранения в п регистрах двоично-крдированньм р-разрядных вектОров.

Блок 11 регистров предназначен для приема в и сдвиговых регистрах. двоично-коднрованного вектора U(t) разрядности h,2h, hn и выдачи на

i-ом такте сдвига h-разрядного кода с младшего регистра (i1,2,...,n}.

Регистр 12 предназначен для,хра-. нения р разрядного вектора воспроизведенной информации, регистр 13 — для5р для хранения h-разрядного вектора .маркера, регистр 14 — для хранения

Ь-разрядного вектора информации, считанного из блока 1 памяти, регистр 15 — для хранения r-разрядного

Э5 еса последней ячейки блока 1 пам ти, куда записана сжатая информация °

Блоки 16-17 элементов И разрешают передачу на входы соответствующих 4р блоков двоично-кодированных векторов разрядности h,2h,...,nh,áëîê 18 элементов И разрешает передачу на информационный выход 29 р-разрядного двоично-кодированного вектора. 45

Блоки 19-21 элементов И предназначены для разрешения передачи на вьмоды соответствующих блоков h-разрядных двоичных векторов, блок 22 элементов ИЛИ выполняет операции

ИЛИ над h-разрядными двоичными векторами, блок 23 элементов НŠ— логическую операцию НЕ над р-разрядными двоично-кодированными векторами. Де" шифратор 24 формирует на выходе 55 сигнал логической единицы при поступлении на вход р единиц. Блок 25 управления формирует управляющие импульгде m — целое положительное число.

В устройстве векторы входной информации интерпретируются как числовые векторы, представленные в позиционной системе счисления с основанием m.

Векторы входной информации перед поступлением на информационный вход

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

h > log m.

Например, двоично-кодированное представление десятичной цифры состоит из четырех двоичных цифр (m = 10, h = --4).

Входной информационный массив И в двоично-кодированном виде содержит

r p-.ðàçðÿäíûõ (p = h n) векторов

О; (2 1,...,г).

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

Блок 25 управления вырабатывает сигнал разрешения записи вектораИ; в блок 8 регистров, а затем в узел формирования вектора.

1149295

Блоки узла 2 формирования вектора образуют линейную последовательностную схему (ЛПС), которая описывается линейной системой уравнений состояний и линейной системой 5 уравнений выходов, которые в матричной форме имеют следующий вид:

S(t+1) AS(t)a В U(t) () = S(t), 10 где А,  — характеристические матрицы ЛПС

S(t) — вектор состояния"ЛПС. в момент t, S(t+1) — вектор состояния ЛПС в момент (t + 1), Y(t) - вектор выхода ЛПС в момент и символ О означает операщпо сложения по модулю ш.

Матрицы А, В и векторы S(t), S(t+1), Y(t), U(t)-содрржат символы из алфавита (О, 1, 2,...,n), причем каждый символ представляется в двоично-кодированном виде из Ь цифр.

Под воздействием последовательности L векторов U (t), поступающей. на вход ЛПС, происходит последователь- ная смена ее внутренних состояний (i-- 1, 2, ...).

ЗО

Множество векторов внутренних состояний ЛПС однозначно определяется последовательностью Ь, поэтому пос. ледовательность L является отображенйем (" входной сигнатурой") мно- 35 жества векторов внутренних состояний ЛПС.

В данном случае множество Я интерпретируется как входной информационный массив M. 40

Поскольку "входная сигнатура" занимает объем памяти меньший, чем соответствующее множество, поэтому переход от входного информационного массива М к "входной сигнатуре" означает переход к. сокращенной форме записи исходной информации.

Отношение объема U1 входного информационногв массива V к объему Ч

"входной сигнатуры" есть коэффициейт 50 сжатия информации

1=

Ч

Ч

Последовательность L состоит из совокупности векторов V; (с), переводящих и-разрядную ЛПС из заданного состояния Sj в заданное состояние

S (i =О, 1... т-1, jii).

Состояния S„ S соответствуют двум соседним векторам д; и р;„входного информационного массива М

S = и;,S =И;, i = 1,2,...,г-1.

В начале работы устройства ЛПС находится в начальном состоянии S0, представляющем, например, р-разрядный набор единиц. Перевод ЛПС из состояния S в состояние S осуществляет1 3 ся в общем случае через (g, -1) промежуточных состояний, т.е., j o i + 1 (i = 1 ° 2,..., 1 g; g n).

В двоично-кодированном представлении последовательность L содержит

Z h-разрядных наборов, а вектор U>(t) содержит я; Ъ-разрядных наборов (х -0,1,.., г-1).

Тогда

1 - 3

Е .2 .- 7„, 1 фпе

Вектор U;(t) может быть представ.лен следующим образом:, (t) (;(t)

Поскольку векторы U, (t) являют,ся векторами переменной длины (от до a) Й записываются в блок 1 памяти последовательно, для их различения вводится специальный маркер. Этот маркер представляет собой Ь-разрядный набор, который не используется при двоично-кодированном представлении входнбй информации. Например, при двоично-кодированном представлении десятичных цифр в качестве маркера может быть выбран любой из следующих наборов

011

1101

1 1 1

Значение вектора U;(t) определяется путем решения известного из теории ЛПС уравнения

s, о A" s; = L„v;(t), (1) к где А — степень k матрицы А, операция вычитания по модулю ш,"

L<-(ðõð) — матрица ранга р вида

1к = IA В, Л" В,...ABBt (2) 1149295

10 х Далее в счетчик 5 добавляется еще одна. единица и по очередному адресу в следующую ячейку блока 1 памяти из регистра 13 через олок 20

:элементов И и блок 22 элементов ИЛИ

45 записывается маркер. На этом заканчивается цикл работы устройства.

Х

Если вектор (3) н равен нулю, тогда содержимое первого регистра блока 9 регистров через блок 16 элементов И записывается в и-й регистр блока 10 регистров. Указанная запись информации в блок 10 регистров осуществляется при наличии на входах блока 16 элементов И соответствующей комбинации разрешающих сигналов, кото. рые поступают с блока 25 управления.

Минимальное значение Кщ „ коэффициента k, прн котором уравнение (1) имеет непротиворечивое решение, определяет минимальную длину g t вектора u;(e) 5

1. = К,„.

С поступлением в блок 8 регистров первого вектора Я, ЛПС устанавливается в начальное состояние

S . Далее в узле 2 формирования

Р вектора получается произведение

А S . На выходе блока 4 вычитания по. о

I лучается вектор S, S = 8, 9 AS (3)

Вектор S, записывается в блок 9

Ъ регистров. Таким образом, получается левая часть уравнения (1) при k 1.

Если вектор (3) равен нулю, тогда на выходе дешифратора 24 появляется признак, указывающий, что при

1х= 1 получено непротиворечивое решение уравнения (1), которое равно 25 ц (с) и, <с) -ао...о

Далее в счетчик 5 на счетный вход поступает один импульс, который формирует адрес первой ячейки Зр в блоке 1 памяти, куда будет записан полученный вектор 6,(й). Затем в регистр 15 записывается содержимое счетчика 5.

По сигналу разрешения записи в

6лок 1 памяти информация, состоящая из h нулей,,из первого регистра блока 11, регистров через блок 19 элементов И и блок 22 элементов ИЛИ записывается в блок 1 памяти.

Затем содержимое блока 10 регистров поступает на узел 3 формирования входной последовательности на выходе которого формируется правая часть уравнения (1) при k = 1, т.е.

1,Ц,(). {Ч)

Результат (4) записывается в блок

11 регистров.

От блока 25 управления поступает комбинация сигналов, которая разрешает прохождение через блок 17 элементов И информации с выходов всех регистров, кроме первого, блока 9 регистров.

Если содержимое всех регистров, кроме первого блока 9 регистров, равно нулю, тогда на выходе дешифратора 24 появляется признак, указывающий, что при k = 1 получено непротиворечивое решение уравнения (1), которое содержится в первом регистре блока 11 регистров. Полученное решение затем из блока 11 регистров записывается в блок 1 памяти по адресу первой ячейки. Далее в счетчик

5 добавляется еще одна единица и по очередному адресу в следующую ячейку блока 1 памяти записывается маркер. На этом также заканчивается цикл работы устройства.

Если содержимое всех регистров,, кроме первого блока 9 регистров, не равно нулю, тогда ищется непротиворечивое решение уравнения (1) при k = 2, З,...,п.

С этой целью с помощью узла 2 формирования вектора периодически формируются произведения А" $ и в .блок 9 регистров записывается век тор 8 равный

Х

Х

Я = SЭ А S 1с = 23,...tl.

В -м цикле по управлякяцнм выходам блока 25 управления поступает комбинация сигналов, которая разрешает прохождение через блок 17 элементов И информации с выходов всех регистров,. кроме младших 1 регистров, блока 9 регистров. В а -м цикле также по выходам блока 25 поступает . комбинация сигналов, которая разрешает прохождение через блок 16 элементов И информации с выходов

1 — k младших регистров блока 9 регистров соответственно на входы : старших п — (и — k ) регистров блока 10 регистров.

1149295

55

Если в -м цикле содержимое всех регистров, кроме младших регистров блока 9 регистров, равно нулю, тогда на выходе дешифратора 24 появляется признак, указывающий, что получено непротиворечивое решение уравнения (1), которое содержится в младших k регистрах блока 11 регистров.

Затем содержимое k младших регистров блока 11 регистров, т.е. вектор Б,(t) = 11 (t) 11 (t),...,U,(t) в течение k тактов записывается

h-разрядными наборами в блок 1 памяти. Адреса ячеек, куда записывается вектор 01(t) формируются счетчиком 5. После окончания записи вектора UC(t) в блок 1 памяти также записывается маркер.

Таким образом, определяется вектор U,(t), переводящий ЛПИ из состояния S в состояние, которое соответствует вектору Q,, После определения вектора UC,(t) в узел 2 формирования вектора записывается вектор Gl,, а в блок 8 регистров принимается новый векторЯ2 входной информации.

Далее аналогичным.. образом определяются векторы U2(t), U (t), u,(t) .

По окончании процесса сжатия информации в счетчике 5 и в регистре

15 содержится адрес ячейки, в которую записан маркер после векто-,. ра U (t).

Процесс восстановления информации осуществляется следующим образом.

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

Вначале происходит установка ЛПС узла 2 формирования вектора в на"-. чальное состояние S0, а счетчика 5в нулевое состояние.

В счетчик 5 на счетный вход поступает один импульс; который формирует адрес первой ячейки области памяти в блоке 1 памяти, куда записана сжатая информация.

Из блока 1 памяти считывается первый Ь-разрядный набор UC(t) векI тора И (й) и записывается в регистр

14. Поскольку набор U<(t) отличается от маркера, поэтому блок 7 сравнения разрешает передачу информации из регистра 14 через блок 21 элемен тов И в узел 2 формирования вектора, в котором выполняется преобразование информации, в входе которой получается вектор 81 согласно следующей формуле

$ = А Бо + Bui (t), (5) I

Полученный вектор 8 записывается в регистр 12. На этом заканчивается один цикл восстановления информации.

Далее содержимое счетчика 5 снова увеличивается на единицу и по полученному адресу из блока 1 памяти считывается следующий Ь-разрядный набор н записывается в регистр 14. Если укаэанный h-разрядный набор является маркером, тогда блок 7 сравнения запретит передачу содержимого регистра. 14 в узел 2 формирования вектора и разрешит передачу содержимого иэ регистра 12 через блок 18. элементов И на информационный выход ! 29, Тем самым будет получен первый вектор И, входного информационного массива W.

Если вектор UC(t) содержит более одного h-разрядного набора, т.е. в регистр 14 после набора U (t) заC

2 писывается набор u,(t), тогда полученный вектор (5) является проме жуточным состоянием ЛПС узла 2 формирования вектора. В этом случае блок 7 разрешает передачу,содержимого регистра 14 в узел 2 формирования вектора и запрещает выдачу информации из регистра 12. Тем самым запрещается выдача промежуточного состояния ЛПС узла 2 формирования вектора на информационный выход 29.

С помощью узла 2 формирования вектора получается вектор S< который записывается в регистр 12 вместо вектора Я .

Далее работа устройства продолжается аналогичным образом до тех пор, пока íà (j + 1)-м цикле восстановления в регистр 14 не будет записан маркер. Тогда блок 7 сравнення разрешит выдачу из регистра 12 вектора S>, который и будет являться вектором a)c входного информационного массива W.

Далее аналогичным образом получаются все векторы входного информационного массива W.

При равенстве содержимого счетчика 5 и содержимого регистра 15

1)49295 20

36 регистров.. Если в j A строке имеется 9 (6 = 2,...,п) символ б то это означает, что входы j-го регистра связаны с выходами 8 регистров блока 36 регистров через (9 — 1) последовательно соединенных

h-входных сумматоров по модулю m.

Символ (б) в j-й строке в (6) означает наличие (отсутствие) логической связи между выходом блока

21 элементов И и входами j-горегистра блока 36 регистров. например, при сжатии массива, состоящего из пятиразрядных деся 15 тичных чисел (n = 5, m = 10, h = 4) характеристические матрицы А и В имеют вид:

19 (6) г д

555 ...

54> ° ° °

119 Э ..- sQ9 9 9 ... 753 в=

1 1 f f 1

000 О

00100

В

00010

I 0001

0001 0001

0000 0000

0000 0000

0001 0001 0001

0001 0000 0000

ОООО 0001 0000

0000

0000

А= °

0000

0000 0000 0001 0000 000

0000 0001 000

0000 0000, 0000

P блок 6 сравнения формирует признак окончания процесса восстановления.

Узел 2 формирования вектора работает следующим образом.

Блоки узла 2 формирования вектора образуют ЛПС, которая описывается характеристической (рхр) матрицей

Й и характеристической (hxp) матри.цей В следующего вида:

Символ 6(9) на пересечении i-го столбца и j-й строки в (6) означа- ет наличие (отсутствие) связи между выходами i-ro регистра и соответствующими входами j-ro регистра в блоке 36 регистров. Если в j и строке имеется символ А только в одном i-м столбце, то это означает непосредственную связь между выходами i-го регистра и соответствующими входами j-го регистра в блоке

Код внутреннего состояния ЛПС сов-: пйдает с р-разрядным кодом на выходе

" блока 36 регистров и является выходным кодом ЛПС. Входом ЛПС явля» ется h-разрядный выход блока 21 эле-

40 ментов И.

В режиме сжатия информации на выход блока 21 элементов И подаются сигналы логического нуля.

С приходом сигнала с блока 25 управления все регистры блока 36

45 регистров устанавливаются в единичное состояние, что соответствует начальному состоянию S ЛПС.

В исходном состоянии с блока 25

50 управления поступают сигналы, ко". торые разрешают (запрещайл.) про,хождение информации через блок 31 элементов И и элемент И 33 (блок

30 элементов И и элемент И 32).

Блок 37 сумматоров осуществляет суммирование по модулю ш р-разрядного кода, поступающего с выходов блока 36 регистров. ,или в двоично-кодированном виде: езультат указанного суммирования через элемент И 33 и элемент

ИЛИ 35 поступает на младший h-разрядный регистр блока 36 регистров.

На входы остальных (и-1) регистров блока 36 регистров через блок 31 эле ментов И и блок 34 элементов ИЛИ поступает h (n-1)-разрядный код соответственно с выходов мпадших (и-1) регистров блока 36 регистров.

С приходом управляющего сигнала с блока 25 управления информация, имеющаяся на входах блока 36 регистров, записывается в блок 36 регистров.

Тем самым в блоке 36 регистров осуществляется сдвиг информации на

h разрядов в сторону старшего n-ro регистра, а .в младший первый регистр записывается результат суммирования с выхода блока 37 сумматоров.

В результате указанного преобразования информации на выходе блока

36 регистров появляется новый р-раз

1)49295

2l f0!

4 Ь о о

24 2! о о

3 8 о о

844 843 о о о о гг г! о о.. эг. й! о о

4г 4! о о

00 0 1

000 1

000.1 (7) О 0 О 1

0 000 гг Бгг

Б гг 82! г Ф, Бгг S51 ! Ф

4г 4!

e !!

4 гг 1

824 S23 ! г1, я !

4Ф 4!

Б! 8!

0001

000 1

О 001

°

Число S (S," ) в (7) равно значению на j-м вйходе i-го регистра блока 36 регистров до преобразования (после преобразования).

При подаче с блока 25 управления k управляющих сигналов произойдет k сдвигов информации в блоке 36 регистров, что эквивалентно следующему преобразованию

Бк A ь °

После определения вектора U"(г.) с блока 25 управления поступает 40 управляющий сигнал, который paspe" шает прохождение р-разрядного кода из блока 8 регистров через блок

30 элементов И, элемент И 33 и блок.

34 элементов ИЛИ, элемент 35.ИЛИ на 4 входы блока 36 регистров. Одновременно с блока 25 управления поступает управляющий сигнал, который запрещает прохождение информации через блок 31 элементов И и элемент

И 33.

С приходом управляющего сигнала с блока 25 управления происходит запись указанной информации в блок

36 регистров, что эквивалентно установке ЛПС в новое состояние.

После этого внввь разрешается прохождение информации через блок

30 формация на входах блока 36 регистров

35 следующим образом.

55 рядный код, соответствующий следующему состоянию Я ЛПС, Аналитически укаэанное преобразование информации описывается следующим образом:

S = АБр.

Например, при сжатии массива, состоящего из четырехразрядных десятичных чисел (n = 4, m 10„

Н 4) блок 36 регистров содержит четыре четырехразрядных регистра и значения векторов Я,г и 8 равны:

31 элементов И и элемент И 33 и запрещается прохождение информацни через блок 30 элементов И и элемент И 32.

Тем самым узел 2 формирования вектора подготавливается к работе по определению следующего вектора и. (е), В режиме восстановления сжатой информации с блока 21 элементов И подаются h-разрядные наборы вектора U;(t) (i 1,2,...,Z).

Блоки 37 сумматоров осуществляют суммирование по модулю m поступившего грбора U,, (t) (j1....,8.)

Вектора U (t) с р-разрядным кодом, поступающим с выходов блока 36 регистров. Результат укаэанного суммирования через элемент И 33 и элемент. И.35 поступает на младший региотр блока 36 регистров. На входы остальных (n-1) регистров блока

Зб регистров через блок 31 элементов И и блок 34 элемеггтов ИЛИ поступает h (и-1)-разрядный код соответственно с выходов младших (пт1) регистров блока 36 регистров.

С приходом управляющего сигнала с блока 25 управления имеющаяся инзаписывается в блок 36 регистров.

Если ранее ЛПС находилась в сост тоянии Зг, тогда в результате указанного.:.преобразования информации

ЛНС переходит s состояние 3;, что аналитически описывается следующим образом:

8 )Ж eB U (t). (8)

В режиме восстановления информации разрешается прохождение информации через блок 31 элементов И и элемент 33 и запрещается прохождение информации через блок 30 элементов И и элемент И 32.

Полученный вектор (8) записывается в регистр 12.

h-Разрядный блок 37 сумматора по модулю m в прямых кодах работает

Перед началом работы устройства в регистр 40 заносится h-разрядный десятичный код числа Q 2" — m которое служит для коррекции резуль. тата. суммирования.

Сумматоры 38 производят суммирование по правилам двоичной арифметики прямых кодов двух h-разряд1149295

23

4 2 1 1

2 1 I 0

1 1 О О

1 0 0 О ных двоичных чисел. Сумматоры 39 производят суммирование по правилам двоичной"арифметики содержимого ре-гистра 40 и результата суммирования сумматоров 38, При появлении сигналов переноса из старшего одноразрядного сумматора 38 или из старшего одноразрядного сумматора 39 триггера 42 устанавливается в единичное значение и разрешает прохождение информации из сумматоров 39 через элементы И 43 и элементы ИЛИ 45 на выход блока 37 сумматора по модулю m в прямь}х кодах.

При отсутствии сигналов переноса из старших одноразрядных сумматоров

38 и 39 триггер.-. 42 устанавливается в нулевое состояние и разрешает прохождение информации иэ сумматоров 38 через элементы. И 44 и элемен- 20 ты ИЛИ 45 иа выход блока 37 сумматора iIo модулю m в прямых кодах.

Узел 3 формирования вхрдной рследовательности работает следующим образом. И

В Iã. -м цикле работы устройства определяется нахолдение неизвестной величины U (t) следукицего уравФ пения

Ь4 =

,- (е)

; (t)

;(t) S„!

$»

$»

I . ° . У !!

° ° ° 2 х

1}

1х n}--и

4 ". ! и (12) ЗО

Операция вычитания по модулю m заменяется операцией сложения по модулю ш в обратных крах чисел.

Для получения обратных кодов чисел предназначены . формирователи 47 обратного кода.

В первом цикле работы устройства

40 со старшего n-ro регистра блока.

10 регистров h-разрядный набор S, который согласно (12) равен набору

V;(t). Поэтому указанный набор S„ ! без преобразований поступает на вход

4 блока 11 регистров.

Ф

В 1! -м (= 2,..., n) цикле работы устройства со старших 1 регистров блока 10 регистров поступает Ыц-разрядный набор вектора $„:

° бе Х(К

Мн е ° ° 1!!.

Ь М ... Х .. 11 1}!

}! " л

4к если если

i+jе и

i+j а+1 (10) где I = 2" }

I}

2; 1

Х О !

$х

$» к

$к

I к

° $ х если i+j n+q

Ь„0 ;(t)S„, k 1,. и. (9)

Вектор S поступает от блока 10 регистров, а полученное значение

U-(t) поступает на вход блока 11

l регистров. . В 1! -м цикле работы устройства вйкторы S» и U (t) являются Ь k "разрядными векторами.

Структура узла 3 формирования входной последовательности определяется видом мат !ицы L, По выбранным характеристическим матрицам

А и В (б) матрица Ь согласно (2) имеет вид1

Например, при сжатии массива, состоящего из четырехразрядных де,сятичных чисел, матрица Ь„ будет-! иметь вид

/ или в двоично-кодированном виде:

0100 0010 0001 0001

0010 0001 0001 0000

0001 0001 0000 0000

OOO1 OOOO ОООО ОООО

Решение уравнения (9) сводится к решению следующей системы уравнений1

Для матрицы L!; вида (10) решение системы уравнений (11) следунящее:

v ;.(t) - s, v, (t) s", e s„"

1. ....... - - е

0"; = $„е$„о„е$„", k =1,2,...n

На выходах первых (k-1) блоков

46 по модулю m в прямых кодах сумма торов согласно (12) получаются разряды вектора V;(t), 1149295

В итоге на вход блока 11 регистров поступает вектбр U;(t), равный

П; (t) и; (t)= U; (t) v; (t) Фо м ователь 47 об

Hp ратного кода работает следующим образом, t

Дешифратор 49 преобразует h- ðàçрядный,двоичный позиционный код набора 5 в (m-1)-разрядный унитарный .Х код (i = 1,..., n). Шифратор 50 преобразует (m-1)-разрядный унитарный

15 код в h-разрядный двоичный позиционный код, который является обратным кодом набора, Я (i = 1,...,n) .

i х

Ь-Разрядный блок 48 сумматора по модулю m в обратных кодах работает

20 следующим образом.

Перед началом работы устройства в регистр 55 заносится h-раэрядный двоичный код числа д = 2 6 — ш, которое служит для коррекции результа25 та суммирования.

Сумматоры 51 производят суммирование по правилам двоичной арифметики обратных кодов двух h-разрядных двоичных чисел вместе с их знаками, причем сигнал переноса с (h + 1)-ro знакового одноразрядного накапливающего двоичного сумматора поступает на вход младшего одноразрядного двоичного сумматора. Поскольку на входы сумматоров 51 всегда пос"35 тупают числа с противоположными знаками, перед началом суммирования знаковый сумматор заносится логическая единица.

Сумматоры 52 производят суммирование по правилам двоичной арифмет п<и содержимого регистра 55 и результата суммирования сумматоров 51 вместе с их знаками, причем сигнал переноса с (и+1)-го знакового одно- 45 разрядного накапливающего двоичного сумматора поступает на вход младmего одноразрядного двоичного сумматора.

Возникающий в процессе суммиро" вания сигнал переноса со знаковых сумматоров 51 и 52 запоминается в триггере 58.

После окончания процесса сумми" рования на выходе элемента ИЛИ 56 55 устанавливается постоянное значение логического нуля или логической единицы в соответствии со значениями на,выходах -знаковых сумматоров 51 и 52.

Если на выходе элемента ИЛИ 56 имеI ется значение логического нуля (логической единицы) при нулевом значении на выходе триггера 58, тогда дешифратор 59 разрешает прохождение на выход блока 48 сумматора по модулю m в обратных кодах прямого (обратного) кода результата суммирования в сумматорах 51. Если на выходе элемента ИЛИ 56 имеется значение логического нуля (логической единицы) при единичном значении на выходе триггера 58, тогда дешифратор разрешает прохождение на выход блока

48 сумматора по модулю m в обратных кодах прямого(обратного) кода результата суммирования в сумматорах 52.

Во всех укаэанных случаях на выход блока 48 сумматора по модулю

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

Блок 4 вычитания работает следующим образом.

В блоке 4 вычиТания операция вычитания по модулю m заменяется операцией сложения по модулю m в обратных кодах чисел. Поскольку с блока 8 регистров поступает положительное уменьшаемое число, поэтому указанное число поступает непосредственно на входы сумматоров 65.

Поскольку с узла 2 формирования вектора поступает положительное вычитаемое число, поэтому с помощью формирователей 64 обратного кода получаются обратные коды цифр указанного числа, которое затем поступает на входы сумматоров 65. В итоге на выход блока 4 вычитания поступает прямой код положь.ельного или отрицательного числа без знака.

Блок 25 управления работает следующим образом.

В исходном состоянии триггеры

91 — 96 находятся в нулевом состоянии, регистры 87-88 находятся в состоянии 00...00, регистр 89 находится в состоянии 11...11.

При поступлении на управляющий вход 27 сигнала, блок 25 управления начинает работать в режиме сжатия информации.

На первом выходе регистра 87 появляется единичный сигнал, который разрешает прохождение импульсов

28

27 от генератора 86 импульсов на вход распределителя 98 импульсов. Распределитель 98 импульсов последовательно формирует управляющие импульсы. Импульс с третьего выхода рас- 5 пределителя 98 импульсов устанавлиl вает в единичное состояние триггер

91, что приводит к появлению разрешающего сигнала на одном из входов узла 2 формирования вектора. При появлении импульса на шестом выходе распределителя 98 импульсов и наличии сигнала на выходе дешифратора

24 на выходе элемента ИЛИ 76 формируется импульс, по которому происхо- 15 дит сдвиг единицы в регистре 87. В . результате запрещается поступление импульсов от генератора 86 импульсов на вход распределителя 98 импульсов и разрешается поступление импульсов 20 от генератора 86 импульсов на вход распределителя 99 импульсов.

При отсутствии сигнала с выхода дешифратора 24 распределитель 98 импульсов продолжает работать. Им" 25 пульс с седьмого выхода распределителя 98 импульсов устанавливает в единичное состояние триггер. 92, что приводит к появлению разрешающего сигнала на входе блока 19 элемен- gp тов И. Импульс с девятого выхода распределителя 98 импульсов устанавливает в нулевое состояние триггер 92, что приводит к появлению разрешающего сигнала на входе блока 20 элементов И. Импульс с одиннадцатого выхода распределителя (98 импульсов через элемент HJIH 76 вызывает сдвиг единицы в регистре 87, В результате запрещается поступле- 4о нне импульсов от генератора 86 импульсов на вход распреДелителя 98 импульсов и разрешается поступление импульсов от генератора 86 импульсов на вход распределителя 99 45 импульсов.

Распределитель 99 импульсов работает в кольцевом режиме. Импульс со второго выхода распределителя 99 импульсов в каждом цикле работы при- 50 водит к сдвигу информации в регистрах 88 и 89. Изменение состояний регистров 88 и 89 происходит в том порядке, как приведено соответственно на фиг. 10 и на фиг. 11. Им" пульс с четвертого выхода распределителя 99 импульсов в каждом цикле работы увеличивает содержимое счетчика 90 на единицу. При появлении импульса на шестом выходе распределителя 99 импульсов и наличии сигнала с выхода дешифратора 24 на выходе элемента ИЛИ 76 формируется импульс, по которому происходит сдвиг единицы в регистре 87. В результате запрещается поступление импульсов от генератора 86 импульсов на вход распределителя 99 импульсов и разрешается поступление импульсов от генератора 86 импульсов на вход распределйтеля 100 импульсов.

Распределитель 100 импульсов работает в кольцевом режиме. Импульс с первого выхода распределителя 100 импульсов устанавливает триггер 92 в единичное состояние. Импульс с третьего выхода распределителя 100 импульсов в каждом цикле работы умень. шает содержимое счетчика 90 на единицу. При достижении нулевого состояния счетчика 90 импульс переноса с его выхода через элемент ИЛИ 76 вызывает сдвиг единицы в регистре

87. В результате запрещается пос"тупление импульсов от генератора 86 импульсов на вход распределителя 100 импульсов и разрешается поступление импульсов от генератора 86 импульсов на вход распределителя 101 импульсов.

Распределитель 101 импульсов последовательно формирует управляющие импульсы. Импульс с первого ! выхода распределителя 101 импульсов

I устанавливает в; нулевое состояние триггер 92, Импульс с третьего выхоца распределителя 101 импульсов устанавливает в нулевое состояние триггер 91, что приводит к появлению разрешающего сигнала на входе узла 2 формирования вектора. Импульс с пятого выхода распределителя 101 импульсов через элемент ИЛИ 76 вызывает сдвиг единицы в регистре 87.

В результате за:трещается поступление импульсов от генератора 86 импульсов на вход распределителя 101 импульсов.

На этом заканчивается работа устройства по определению вектора

U;(t) и записи его в блок 1 памяти (1 = 1,2,..., Е).

При поступлении на управляющий вход 27 очередного управляющего сигнала блок 25 управления снова начинает формировать управчян щие импульсы, необходимые цлл о релvлc30 выхода распределителя 103 импульсов в конце каждого цикла устанавливает триггеры 95 и 9 в нулевое состояние.

Распределитель 103 импульсов работает до тех пор, пока не появится сигнал с выхода блока 6 сравнения, который установит триггер 94 в нулевое состояние. В результате запрещается поступление импульсов от генератора 86 импульсов на вход распределителя 103 импульсов.

Предлагаемое устройство имеет следующие преимущества по сравнению с известными устройствами.

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

20 универсальный характер сжатия информации.

Коэффициент g сжатия информации не зависит от наличия определенных закономерностей в сжимаемой инфор25 мации и находится в следующих пределах

Максимальная эффективность сжатия

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

В предлагаемом, устройстве можно сжимать дискретную информацию, представленную в произвольном целочисленном алфавите х =(О, 1,2,...m-1), где ш — целое положительное число.

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

29 1149295 ния вектора 0,(й) и записи его в блок 1 памяти (i = 2,3,...,Е).

При поступлении на управляющий вход 28 управляющего сигнала блок

25 управления начинает работать в режиме восстановления информации. В этом случае триггер 93 устанавливается н единичное состояние и разрешает поступление импульсов от. генератора 86 импульсов на вход распределителя. 102 импульсов.

Распределитель 102 импульсов последовательно формирует управляющие импульсы. Импульс с второго выхода распределителя 102 импульсов устанавливает в единичное состояние триггер 91. Импульс с третьего выхода распределителя 102 импульсов устанавливает триггер 93 в нулевое состояние, а триггер 94— в единичное. В результате запрещается поступление импульсов от генератора 86 импульсов на вход распределителя 102 импульсов и разрешается поступление импульсов ат генератора 86 импульсов на вход распределителя 103 импульсов.

Распределитель 103 импульсов работает в кольцевом режиме. В первом цикле работы распределителя 103 импульсов триггер 96 запрещает поступление импульса с пятого выхода распределителя 103 импульсов на вход блока 18 элементов И. В последующих циклах работы после появления импульса на третьем выходе распределителя 103 импульсов может появиться импульс.с блока 7, сравнения, который установит в единичное состояние триггеры 95 и 96.

В результате появится разрешающий сигнал на входе блока 21 элементов И и будет разрешено прохождение импульса с пятого выхода распределителя 103 импульсов на вход блока

18 элементов И. Импульс с седьмого

1i49295

1!49295

1149295! I49295

1149)95

)149295

1 149295

yuan. 7

1149295

ll49295

l 1 ><>, )cp Риг. Ю!!49295

Заказ 1903/36 Тираж 611

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

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

Подписное

В

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

Составитель В. Черединцев

Редактор С. Патрушева Техред М.Гергель Корректор И. Муска