УСТРОЙСТВО ДЛЯ ДЕКОМПРЕССИИ ДАННЫХ Российский патент 2019 года по МПК H03M7/30 

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

Известен способ сжатия восстановления данных без потерь (RU №2403677 С1, МПК Н03М 7/30, заявлено 09.02.2009, опубликовано 10.11.2010, Бюл. №31), в котором используется сжатие данных, ранее подвергнутых сжатию. В сжимаемом потоке данных считают количество нулей n₀ и количество единиц n₁, выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из n₀ нулей и n₁ единиц и нахождения соответствующей перестановки, которой присваивают цифровой код N_c, считают общее количество кодов n_c, определяют значения d₁=n₀+n₁-n_c и d₂=(n₀+n₁)/2, а для восстановления потока данных выполняют обратные операции и в соответствии с выбранным алгоритмом по значениям n₀, n₁, N_c находят конкретную перестановку с повторениями из n₀ нулей и n₁ единиц, которая соответствует исходному потоку данных.

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

Известно устройство для сжатия данных (RU №2622878 С1, МПК Н03М 7/30, заявлено 01.08.2016, опубликовано 20.06.2017, Бюл. №17), содержащее N входных символов D1, D2, …, DN по k разрядов соединенных с входным регистром данных 1, группу из L анализаторов символов 2₁, 2₂, …, 2_L, каждый из которых содержит первую группу из w элементов ИЛИ 3, первую группу из w элементов И 4 и блок счета количества единиц 5 (L - количество групп по w символов из k разрядов, причем N=L*w), группу из (L-1) сумматоров 6₁, 6₂, …, 6_L-1, группу из (L-1) схем сравнения 7₁, 7₂, …, 7_L-1, группу из (L-1) D-триггеров 8₁, 8₂, …, 8_L-1 с входом разрешения работы СЕ, асинхронным CLR и синхронным R входами установки в нулевое состояние, вторую группу из (L-1) элементов И 9₁, 9₂, …, 9_L-1, третий элемент И 10, четвертый элемент И 11, второй элемент ИЛИ 12, многовыходной блок приоритета 13, блок коммутаторов данных 14, выходной буфер 15, внешние входы задания количества символов w в группе 16, внешний вход EN разрешения работы 17, внешний вход С синхронизации 18, внешний вход CLR установки в нулевое состояние 19, внешние выходы устройства Q 20, а также внутреннюю шину данных DD из N символов по к разрядов, внутреннюю N разрядную шину маски символов М, внутреннюю L разрядную шину указателей групп символов U, причем многовыходной блок приоритета 13 содержит w групп выходов, все N разрядов внутренней шины маски М соединены с входами многовыходного блока приоритета 13, внешний вход синхронизации 18 соединен с входами синхронизации С входного регистра 1 и выходного буфера 15.

Недостатком данного устройства является отсутствие средств для восстановления сжатых данных.

Наиболее близким устройством к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для распаковки данных (RU №2658147 С1, МПК Н03М 7/30, заявлено 05.10.2017, опубликовано 19.06.2018, Бюл. №17), содержащее шину входных данных 1 соединенную с входным регистром данных 2, выходной буфер 6, выходы которого содержат N выходных символов Q1, Q2, …, QN по k разрядов и являются внешними выходами устройства 13, многовыходной блок приоритета 3, который содержит w групп выходов S1, S2, …, Sw по N разрядов, группу из N коммутаторов данных 4₁, 4₂, …, 4_N, группу из L регистров 5₁, 5₂, …, 5_L с синхронным входом R установки в нулевое состояние, элемент ИЛИ-НЕ 7, первый элемент ИЛИ 8, второй элемент ИЛИ 9, D-триггер 10 с синхронным входом R установки в нулевое состояние,

а также содержащее внешний вход С синхронизации 11, внешний вход R синхронной установки в нулевое состояние 12, внутреннюю шину данных D из w символов по k разрядов, внутреннюю N разрядную шину маски символов М, внутреннюю L разрядную шину указателей групп символов U (L - количество групп по w символов из k разрядов, причем N=L*w),

причем внешний вход синхронизации 11 соединен с входами синхронизации С входного регистра данных 2, группы регистров 5, выходного буфера 6 и D-триггера 10, а внешний вход 12 синхронной установки в нулевое состояние соединен с входами R синхронной установки в нулевое состояние входного регистра 2, выходного буфера 6 и D-триггера 10, а выход D-триггера 10 соединен с входом СЕ разрешения работы выходного буфера 6,

причем шина входных данных 1 содержит группу входных разрядов данных ID из w символов по k разрядов, группу входных N разрядов маски символов IM, группу входных L разрядов указателей групп символов IU, при этом выходы входного регистра 2 являются соответствующими w*k разрядами внутренней шины данных D и соответствующими N разрядами внутренней шины маски символов М и соответствующими L разрядами внутренней шины указателей групп символов U,

причем все N разрядов внутренней шины маски М соединены с входами многовыходного блока приоритета 3, а все w*k разрядов внутренней шины данных D соединены с информационными входами каждого коммутатора данных группы из N коммутаторов данных 4₁, 4₂, …, 4_N, управляющие входы выборки которых соединены с соответствующими одноименными разрядами w групп выходов S1, S2, …, Sw многовыходного блока приоритета 3,

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

Причиной препятствующей достижению, ниже приведенному техническому результату, являются прием и обработка значений входных L разрядов указателей групп ненулевых символов IU, а также хранение L разрядов указателей групп в памяти после компрессии данных, и невозможность объединения во входные группы данных ID, содержащих по w ненулевых символов, отдельных символов из соседних групп, при суммарном количестве ненулевых символов в соседних группах больше w.

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для декомпрессии данных содержащее шину входных данных 1 соединенную с входным регистром данных 2, выходной буфер 6, выходы которого содержат N выходных символов Q1, Q2, …, QN по k разрядов и являются внешними выходами устройства 13, многовыходной блок приоритета 3, который содержит w групп выходов S1, S2, …, Sw по N разрядов, группу из N коммутаторов данных 4₁, 4₂, …, 4_N, группу регистров 5 с синхронным входом R установки в нулевое состояние, элемент ИЛИ-НЕ 7, D-триггер 10 с синхронным входом R установки в нулевое состояние,

а также содержащее внешний вход С синхронизации 11, внешний вход R синхронной установки в нулевое состояние 12, внутреннюю шину данных D из w символов по k разрядов, внутреннюю N разрядную первую шину маски символов М,

причем внешний вход синхронизации 11 соединен с входами синхронизации С входного регистра данных 2, группы регистров 5, выходного буфера 6 и D-триггера 10, а внешний вход 12 синхронной установки в нулевое состояние соединен с входами R синхронной установки в нулевое состояние входного регистра 2, выходного буфера 6 и D-триггера 10, а выход D-триггера 10 соединен с входом СЕ разрешения работы выходного буфера 6,

причем шина входных данных 1 содержит группу входных разрядов данных ID из w символов по k разрядов, группу входных N разрядов маски символов IM, при этом выходы входного регистра 2 являются соответствующими w*k разрядами внутренней шины данных D и соответствующими N разрядами внутренней первой шины маски символов М,

причем все N разрядов внутренней первой шины маски символов М соединены с входами многовыходного блока приоритета 3, а все w*k разрядов внутренней шины данных D соединены с информационными входами каждого коммутатора данных группы из N коммутаторов данных 4₁, 4₂, …, 4_N, управляющие входы выборки которых соединены с соответствующими одноименными разрядами w групп выходов S1, S2, …, Sw многовыходного блока приоритета 3,

дополнительно введены N групп 8₁, 8₂, …, 8_N по k элементов 2И, регистр маски 9, а группа регистров 5 содержит N регистров 5₁, 5₂, …, 5_N по k разрядов,

а также введены внутренняя (N-w) разрядная шина приоритета MS, которая является группой вторых выходов многовыходного блока приоритета 3, внутренняя N разрядная вторая шины маски символов QM, которая является группой выходов регистра маски 9, и флаг нуля FZ,

причем выходы группы из N коммутаторов данных 4₁, 4₂, …, 4_N соединены с соответствующими информационными входами D одноименных регистров группы из N регистров 5₁, 5₂, …, 5_N, у которых входы R синхронной установки в нулевое состояние соединены с внешним входом 12 синхронной установки в нулевое состояние, а управляющие входы СЕ разрешения работы соединены с одноименными разрядами внутренней N разрядной первой шины маски символов М, а выходы QB1, QB2, …, QBN всех N регистров 5₁, 5₂, …, 5_N соединены по группам с соответствующими первыми входами элементов 2И одноименных N групп 8₁, 8₂, …, 8_N, выходы которых соединены с соответствующими группами информационных входов IQ1, IQ2, …, IQN выходного буфера 6, а вторые входы элементов 2И из N групп 8₁, 8₂, …, 8_N по группам соединены между собой и подключены к соответствующим одноименным разрядам внутренней N разрядной второй шины маски QM,

кроме того (N-w) разрядов внутренней шины приоритета MS соединены с входами элемента ИЛИ-НЕ 7, выход которого является флагом нуля FZ и соединен с информационным D-входом D-триггера 10, выход которого также соединен с входом СЕ разрешения работы регистра маски 9, у которого вход синхронизации С соединен с внешним входом С синхронизации 11, вход R синхронной установки в нулевое состояние соединен с внешним входом 12 синхронной установки в нулевое состояние, а группа информационных D-входов соединены с N разрядами внутренней первой шины маски символов М.

На фиг. 1 представлена схема предлагаемого устройства для декомпрессии данных. На фиг. 2 приведен формат входных данных DD до компрессии. На фиг. 3 приведен формат входных данных на шине 1. На фиг. 4 приведен формат выходных данных. На фиг. 5 приведена потактовая временная диаграмма.

В устройстве и на фиг. 1-5 приняты следующие обозначения:

С - вход синхронизации,

СЕ - вход разрешения работы,

D - внутренняя шина данных из w символов по k разрядов,

DD - данные до компрессии (сжатия),

FZ - флаг нуля,

ID - входные разряды данных - w символов по k разрядов,

IM - входные N разрядов маски символов,

IQ1, IQ2, …, IQN - N входов символов выходного буфера 6,

IU - входные L разрядов указателей групп символов в прототипе,

k - разрядность символов,

L - количество групп по w символов в прототипе, причем N=L*w,

М - внутренняя N разрядная первая шина маски символов,

MS - внутренняя (N-w) разрядная шина приоритета,

N - количество выходных символов,

Q1, Q2, …, QN - N выходных символов по k разрядов после декомпрессии (восстановления),

QB1, QB2, QBN - N символов с выходов группы регистров 5₁, 5₂, …, 5_N,

QM - внутренняя N разрядная вторая шина маски символов,

R - вход синхронной установки в нулевое состояние,

S1, S2, …, Sw - w групп N разрядных указателей старшей единицы в коде «1 из N»,

U - внутренняя L разрядная шина указателей групп символов в прототипе,

V - количество ненулевых символов в данных DD,

w - количество символов во входных данных ID,.

Z - максимальное количество элементов входной последовательности, причем Z=] N/w [(большее целое) когда количество V ненулевых символов больше (N-w+1),

1 - шина входных данных,

2 - входной регистр данных,

3 - многовыходной блок приоритета,

4₁, 4₂, …, 4_N - группа из N коммутаторов данных,

5₁, 5₂, …, 5_N - группа из N регистров с синхронным входом R установки в нулевое состояние,

6 - выходной буфер,

7 - элемент ИЛИ-НЕ,

8₁, 8₂, …, 8_N - N групп по k элементов 2И,

9 - регистр маски,

10 - D-триггер с синхронным входом R установки в нулевое состояние,

11 - внешний вход синхронизации,

12 - внешний вход синхронной установки в нулевое состояние,

13 - внешние выходы.

Предлагаемое устройство содержит входной регистр данных 2, многовыходной блок приоритета 3, группу из N коммутаторов данных 4₁, 4₂, …, 4_N, группу из N регистров 5₁, 5₂, …, 5_N, выходной буфер 6, элемент ИЛИ-НЕ 7, N групп 8₁, 8₂, …, 8_N по k элементов 2И, регистр маски 9, D-триггер 10, а также шину входных данных 1, внешний вход синхронизации 11, внешний вход синхронной установки нулевое состояние 12, внешние выходы 13, внутренние шину данных D, первую шину маски символов М, вторую шину маски символов QM, шину приоритета MS и w групп N разрядных указателей старшей единицы S1, S2, …, Sw.

Шина входных данных 1 содержит группу входных разрядов данных ID, которые состоят из w символов по k разрядов, и группу входных N разрядов маски символов IM, и подключена к входному регистру данных 2.

Входной регистр данных 2 предназначен для хранения значений текущей группы данных ID из w символов по k разрядов и соответствующего этой группе кода маски символов IM. При этом выходы входного регистра данных 2 являются соответствующими разрядами внутренних шины данных D и первой шины маски символов М.

Входной регистр данных 2, регистры 5₁, 5₂, …, 5_N, выходной буфер 6, регистр маски 9 и D-триггер 10 содержат вход синхронизации С и вход синхронной установки в нулевое состояние R.

Внешний вход синхронизации 11 соединен с входами синхронизации С входного регистра 2, регистров 5₁, 5₂, …, 5_N, выходного буфера 6, регистра маски 9 и D-триггера 10.

Внешний вход 12 синхронной установки в нулевое состояние соединен с входами R синхронной установки в нулевое состояние входного регистра 2, регистров 5₁, 5₂, …, 5_N, выходного буфера 6, регистра маски 9 и D-триггера 10.

Все N разрядов внутренней первой шины маски символов М соединены с входами многовыходного блока приоритета 3, а все w*k разрядов внутренней шины данных D соединены с информационными входами каждого коммутатора данных группы из N коммутаторов данных 4₁, 4₂, …, 4_N, управляющие входы выборки которых соединены с соответствующими одноименными разрядами w групп выходов S1, S2, …, Sw многовыходного блока приоритета 3.

Многовыходной блок приоритета 3 формирует на выходах каждой из w групп из N разрядов унитарный код «1 из N», которые соответствуют значению кода на внутренней первой шине маски М и формируются в порядке старшинства приоритетов. Коммутаторы данных 4₁, 4₂, …, 4_N предназначены для выделения из w символов по k разрядов с внутренней шины данных D одного из символов разрешенного в соответствии с унитарным кодом «1 из N» установленным на выходах w групп N разрядных указателей старшей единицы S1, S2, …, Sw.

Выходы группы из N коммутаторов данных 4₁, 4₂, …, 4_N соединены с соответствующими информационными входами D одноименных регистров группы из N регистров 5₁, 5₂, …, 5_N, у которых управляющие входы СЕ разрешения работы соединены с одноименными разрядами внутренней N разрядной первой шины маски символов М.

Группа из N регистров 5₁, 5₂, …, 5_N предназначена для записи на каждом такте до w ненулевых символов по k разрядов входных данных ID, в соответствии с кодом, установленным на внутренней N разрядной первой шине маски символов М.

Выходы QB1, QB2, …, QBN всех N регистров 5₁, 5₂, …, 5_N соединены по группам с соответствующими первыми входами элементов 2И одноименных N групп 8₁, 8₂, …, 8_N, выходы которых соединены с соответствующими группами информационных входов IQ1, IQ2, …, IQN выходного буфера 6, который предназначен для хранения восстановленных значений после декомпрессии данных.

Вторые входы элементов 2И из N групп 8₁, 8₂, …, 8_N по группам соединены между собой и подключены к соответствующим одноименным разрядам внутренней N разрядной второй шины маски QM, которая является выходами регистра маски 9, у которого группа информационных D-входов соединены с N разрядами внутренней первой шины маски символов М. Регистр маски 9 предназначен для хранения значений первичного кода маски для всех V ненулевых символов во входных данных DD до компрессии, содержащих N символов. Разряды второй шины маски QM разрешают передачу ненулевых символов после восстановления с выходов QB1, QB2, …, QBN всех N регистров 5₁, 5₂, …, 5_N по группам через элементы 2И из N групп 8₁, 8₂, …, 8_N на группы входов IQ1, IQ2, …, IQN символов выходного буфера 6.

Внутренняя (N-w) разрядная шина приоритета MS, которая является группой вторых выходов многовыходного блока приоритета 3, соединена с входами элемента ИЛИ-НЕ 7, выход которого является флагом нуля FZ и соединен с информационным D-входом D-триггера 10, выход которого соединен с входами СЕ разрешения работы выходного буфера 6 и регистра маски 9.

Единичное значение флага нуля FZ=1 формируется если нулевые значения установлены во всех разрядах шины приоритета MS. D-триггер 10 предназначен для управления записью в выходной буфер 6 и регистр маски 9.

Выходы выходного буфера 6 содержат N выходных символов Q1, Q2, …, QN по k разрядов и являются внешними выходами устройства 13.

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

После компрессии (сжатия) данных DD, содержащих N символов по k разрядов (фиг. 2), формируется последовательность сжатых данных, элементы которой состоят из группы ID, содержащей до w ненулевых символов по k разрядов данных, и группы маски символов IM (фиг. 3). Максимальное количество элементов входной последовательности составляет Z=] N/w [(большее целое) когда количество V ненулевых символов больше (N-w+1).

На шину входных данных 1 предлагаемого устройства поступает входная последовательность сжатых данных, начиная со старших символов, содержащая входные разряды данных ID, которые состоят из w символов по k разрядов, и соответствующие им входные N разрядов маски символов IM (фиг. 3), которые принимаются во входной регистр данных 2. При этом единичное значение разряда маски символов IM соответствует ненулевому символу в исходных данных DD до сжатия.

Многовыходной блок приоритета 3 определяет не только сигнал с наивысшим приоритетом, но также определяет сигналы со вторым, третьим, …, w-м по старшинству приоритетами. В соответствии с кодом маски М на выходах многовыходного блока приоритета 3 формируются w групп приоритета S1, S2, …, Sw в порядке старшинства приоритета. При этом каждому из N разрядов маски символов М присваивается фиксированный приоритет. В устройстве старший приоритет присвоен старшему N-му разряду из N разрядов маски символов М, а далее приоритет уменьшается от разряда к разряду с уменьшением номера разряда. Младший приоритет задан для младшего 1-го разряда маски символов М. Среди выходных w групп S1, S2, …, Sw многовыходного блока приоритета 3 наивысший приоритет присвоен младшей первой группе S1, а далее приоритет уменьшается от группы к группе с увеличением номера группы. Младший приоритет задан для группы со старшим номером Sw. На выходах каждой из w групп приоритета S1, S2, …, Sw вырабатывается результат в виде унитарного кода «1 из N» - единичный сигнал будет установлен только на одном выходе соответствующем высшему (старшему) приоритету. Старший приоритет в каждой из w групп приоритета S1, S2, …, Sw присвоен разряду со старшим номером.

Далее в соответствии со значениями w групп приоритета S1, S2, …, Sw на выходы группы из N коммутаторов данных 4₁, 4₂, …, 4_N передаются не более w соответствующих ненулевых символов входных данных ID с внутренней шины данных D.

На следующем такте в соответствии с единичными значениями N разрядов текущего кода с внутренней первой шины маски символов М проводится запись с внутренней шины данных D до w входных ненулевых символов по k разрядов, соответствующие w единичным значениям, начиная со старших разрядов текущей маски символов М, и нулевые значения символов, соответствующие единичным значениям, превышающим w, начиная со старших разрядов текущей маски символов М, в соответствующие регистры 5₁, 5₂, …, 5_N.

Одновременно с шины входных данных 1 проводится прием следующих значений элементов сжатой последовательности данных во входной регистр данных 2. Далее аналогично проводится восстановление данных и осуществляется прием до w следующих входных ненулевых символов по k разрядов в соответствующие регистры 5₁, 5₂, …, 5_N, в соответствии со значениями разрядов текущей маски символов М.

Если на текущем такте обработаны все единичные значении разрядов текущей маски символов М, то нулевые значения устанавливаются во всех разрядах внутренней шины приоритета MS на выходах многовыходного блока приоритета 3, формируется единичное значение флага нуля FZ=1 и на следующем такте единичное значение устанавливается на выходе D-триггера 10.

Кроме того, для каждых новых входных данных DD на первом такте первичное значение маски символов М, соответствующее всем V ненулевым символам из N входных символов до компрессии, записывается в регистр маски 9 при единичном значении на выходе D-триггера 10.

В каждом такте, в соответствии с единичными значениями разрядов регистра маски 9, на выходы N групп по k элементов 2И 8₁, 8₂, …, 8_N передаются значения символов QB1, QB2, …, QBN с выходов соответствующих регистров 5₁, 5₂, …, 5_N, или формируются нулевые символы соответствующие нулевым значениям разрядов регистра маски 9. Значения с выходов N групп по k элементов 2И 8₁, 8₂, …, 8_N поступают на входы символов IQ1, IQ2, …, IQN выходного буфера 6, которые, при единичном значении на выходе D-триггера 10, на следующем такте записываются в выходной буфер 6 и поступают на внешние выходы 13 устройства. При этом N выходных символов по k разрядов восстановленных данных Q1, Q2, …, QN (фиг. 4) соответствуют данным DD до компрессии (сжатия) без потери информации.

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

При подаче единичного сигнала на вход R синхронной установки в нулевое состояние 12 по тактовому сигналу С на внешнем входе 11 в нулевое состояние устанавливаются входной регистр данных 1, группа из N регистров 5₁, 5₂, …, 5_N, D-триггер 10, регистр маски 9 и выходной буфер 6. При этом нулевые значения также устанавливаются во всех разрядах внутренней шины приоритета MS на выходах многовыходного блока приоритета 3 и формируется единичное значение флага нуля FZ=1 на выходе элемента ИЛИ-НЕ 7.

По следующему тактовому импульсу С осуществляется прием входных данных ID и маски символов IM во входной регистр 2 с шины входных данных 1. При этом прием в регистры 5₁, 5₂, …, 5_N, и выходной буфер 6 не выполняется, так как у них на входах разрешения СЕ установлены нулевые сигналы которые поступают с выхода D-триггера 10. Одновременно в единичное состояние устанавливается D-триггер 10, так как установлено единичное значение флага нуля FZ=1.

Далее в соответствии с кодом маски М на выходах многовыходного блока приоритета 3 формируются w групп приоритета S1, S2, …, Sw в порядке старшинства приоритета. На выходах каждой из w групп приоритета S1, S2, …, Sw вырабатывается результат в виде унитарного кода «1 из N» - единичный сигнал будет установлен только на одном выходе соответствующем высшему (старшему) приоритету. В соответствии с единичными значениями сигналов приоритета S1, S2, …, Sw в группе из N коммутаторов данных 4₁, 4₂, …, 4_N на выходы передаются не более w соответствующих символов данных D, а на остальных выходах коммутаторов данных 4₁, 4₂, …, 4_N устанавливаются значения нулевых символов. Одновременно разряды кода маски М передаются на соответствующие одноименные входы СЕ разрешения работы регистров 5₁, 5₂, …, 5_N и на информационные входы регистра маски 9, у которого на входе СЕ разрешения работы установлено единичное значение с выхода D-триггера 10. Кроме того, если на текущем такте обработаны все единичные значении разрядов текущей маски символов М или если все разряды входной маски М имеют нулевые значения, то нулевые значения устанавливаются во всех разрядах внутренней шины приоритета MS на выходах многовыходного блока приоритета 3 и на выходе элемента ИЛИ-НЕ 7 формируется единичное значение флага нуля FZ=1, а при наличии не обработанных единичных разрядов текущей маски символов М формируется нулевое значение флага нуля FZ=0.

По следующему тактовому импульсу С в соответствии с единичными значениями разрядов кода маски М проводится запись в соответствующие регистры 5₁, 5₂, …, 5_N до w входных ненулевых символов по k разрядов с шины D и нулевые значения символов, соответствующие единичным значениям, превышающим w, начиная со старших разрядов текущей маски символов М. При этом также осуществляется запись в регистр маски 9 первого значения кода маски М, единичные значения которого соответствуют всем ненулевым символам из N входных символов до компрессии, если единичное значение установлено на входе СЕ разрешения работы регистра маски 9 с выхода D-триггера 10. Кроме того соответствующее значение флага нуля FZ принимается в D-триггер 10. Одновременно осуществляется прием во входной регистр 2 следующих данных ID и маски символов IM с шины входных данных 1.

Далее аналогично, как в предыдущем такте, проводится анализ следующих разрядов кода маски М и в группе из N коммутаторов данных 4₁, 4₂, …, 4_N на выходы передаются соответствующие следующие w ненулевых символов входных данных ID.

Одновременно на каждом такте в соответствии с единичными значениями разрядов второй маски шины QM с выходов регистра маски 9, на выходы N групп по k элементов 2И 8₁, 8₂, …, 8_N передаются значения символов QB1, QB2, …, QBN с выходов соответствующих регистров 5₁, 5₂, …, 5_N, или формируются нулевые символы соответствующие нулевым значениям разрядов регистра маски 9. Значения с выходов N групп по k элементов 2И 8₁, 8₂, …, 8_N поступают на входы символов IQ1, IQ2, …, IQN выходного буфера 6, которые при единичном значении на выходе D-триггера 10 на следующем такте записываются в выходной буфер 6 и поступают на внешние выходы 13 устройства. При этом N выходных символов по k разрядов восстановленных данных Q1, Q2, …, QN соответствуют данным DD до компрессии (сжатия) без потери информации.

В потактовой временной диаграмме на фиг. 5 приведен пример для последовательности входных данных DD1, …, DD7, элементы последовательности данных на входе устройства после компрессии ID и IM и восстановление сжатых данных в предлагаемом устройстве, при количестве входных символов N=16 по k=4 разрядов и количестве символов w=4 во входных данных ID. На фиг. 5 в скобках указана форма представления данных - двоичная (2) или шестнадцатеричная (16).

В такте 1 шестнадцать символов первых данных DD1 до компрессии содержат четыре ненулевых символа (F, А, 5, 3), которые далее сжимаются и поступают по шине 1 в предлагаемое устройство на входные разряды данных ID11=FA53 и на соответствующие входные N разрядов маски символов IM11=4214, которые принимаются во входной регистр 2 в такте 2. Одновременно на такте 2 в соответствии со значениями кода на внутренней первой шине маски М=4214 проводится восстановление данных в группе из N=16 коммутаторов данных 4₁, 4₂, …, 4₁₆, а затем результаты восстановления в такте 3 записываются во все N=16 регистры 5₁, 5₂, …, 5₁₆ (QB1, QB2, …, QB16). При этом также код маски символов М=4214 записывается регистр маски 9 (QM=4214), на входе СЕ разрешения работы которого установлено единичное значение с выхода D-триггера 10, и также вновь в единичное состояние устанавливается D-триггер 10, так как нулевые значения установлены во всех разрядах внутренней шины приоритета MS и установлено единичное значение флага нуля FZ=1.

Далее в соответствии с единичными значениями разрядов QM=4214 регистра маски 9, на выходы N групп по k элементов 2И 8₁, 8₂, …, 8₁₆ передаются значения символов QB1, QB2, …, QB16 с выходов соответствующих регистров 5₁, 5₂, …, 5₁₆, которые поступают на входы IQ1, IQ2, …, IQ16 выходного буфера 6 и восстановленные данные (F, А, 5, 3) записываются на следующем такте 4 в выходной буфер 6 и поступают на внешние выходы 13 соответствующих выходных символов Q1, Q2, …, Q16 (QD1 на фиг. 5), при единичном значении на выходе D-триггера 10. Таким образом, декомпрессия входных данных DDI, содержащих четыре ненулевых символа и поступивших на такте 1, проведена за три такта.

В такте 2 вторые данные DD2 содержат восемь ненулевых символов (1, В, 9, 8, 7, 6, 5, 2), которые сжимаются и первые старшие четыре символа (1, В, 9, 8) поступают на входные разряды данных ID21=1B98, а также формируется значение кода маски с единичными значениями для ненулевых символов IM21=45F2 в N=16 входных символах, которые в такте 3 принимаются во входной регистр 2 - D=1B98 и M=45F2. Одновременно в такте 3 сжимаются следующие вторые четыре символа (7, 6, 5, 2), которые поступают на входы данных ID22=7652, и формируется значение кода маски IM22=0072, в котором установлены в нулевое состояние разряды соответствующие первым старшим четырем ненулевым символам, принятые во входной регистр 2 на такте 2. На такте 3 на внутренней шине приоритета MS формируется ненулевое значение (MS=0072) и соответственно нулевое значение флага нуля FZ=0, которое на такте 4 записывается в D-триггер 10. Одновременно на такте 4 первое значение кода маски M=45F2 для вторых данных DD2 записывается в регистр маски 9 (QM=45F2), на входе СЕ разрешения работы которого установлено единичное значение, а также записываются только четыре ненулевых символа (1, В, 9, 8) в соответствующие регистры 5₁, 5₂, …, 5₁₆, и сохраняются значения в остальных регистрах. В такте 5 запись в регистр маски 9 не проводится, так как на входе СЕ разрешения работы которого установлено нулевое значение с выхода D-триггер 10, а также записываются только следующие четыре ненулевых символа (7, 6, 5, 2) в соответствующие регистры 5₁, 5₂, …, 5₁₆. Одновременно на такте 4 на выходы N групп по k элементов 2И 8₁, 8₂, …, 8₁₆ и далее на входы IQ1, IQ2, …, IQ16 выходного буфера 6 передаются только четыре ненулевых символа (1, В, 9, 8), а на такте 5 уже передаются восемь ненулевых символов (1, В, 9, 8, 7, 6, 5, 2), которые на следующем такте 6 записываются в выходной буфер 6 и поступают на внешние выходы 13 соответствующих выходных символов Q1, Q2, …, Q16 (QD2 на фиг. 5). Таким образом, декомпрессия входных данных DD2, содержащих восемь ненулевых символов и поступивших на такте 2, проведена за четыре такта.

В такте 4 третьи данные DD3 содержат все нулевые символы ID31=0000, для которых формируются нулевые разряды маски IM31=0000. В такте 5 входные данные записываются во входной регистр 2 - D=0000 и М=0000 и формируется единичное значение флага нуля FZ=1. В такте 6 не проводится запись в регистры 5₁, 5₂, …, 5₁₆, в которых сохраняется предыдущая информация, но проводится запись в регистр маски 9 нулевого кода QM=0000, поэтому на входах IQ1, IQ2, …, IQ16 выходного буфера 6 также формируются нулевые значения, которые записываются в такте 7 (QD3 на фиг. 5). Таким образом, декомпрессия входных данных DD3, содержащих только нулевые символы и поступивших на такте 4, проведена за три такта.

В такте 5 четвертые данные DD4 содержат четыре ненулевых символа (4, 3, 1, А), которые на такте 6 и соответствующий код маски принимаются во входной регистр 2 - D=431A и М=8580. Далее аналогично декомпрессии для первых данных DD1, которые также содержат только четыре ненулевых символа, проводится восстановление для данных DD4. При этом на такте 7 проводится запись только четырех символов (4, 3, 1, А) в соответствующие регистры 5₁, 5₂, …, 5₁₆, в соответствии с кодом маски М=8580, и сохраняются значения в остальных регистрах. Одновременно в такте 7 на выходе D-триггера 10 сохраняется единичное значение. Поэтому на такте 8 осуществляется запись результата QD4 в выходной регистр 6 (QD4 на фиг. 5). Таким образом, декомпрессия входных данных DD4, содержащих четыре ненулевых символа и поступивших на такте 5, проведена за три такта.

В такте 6 пятые данные DD5 содержат десять ненулевых символов, которые сжимаются и первые четыре символа (A, F, С, 7) поступают на входные разряды данных ID51=AFC7, а также формируется значение кода маски ненулевых символов IM51=В3Е5 для всех N=16 входных символов, которые в такте 7 принимаются во входной регистр 2 - D=AFC7 и М=В3Е5. Одновременно в такте 7 сжимаются следующие вторые четыре символа (В, 1, 2, 3), которые поступают на входы данных ID52=В123, и формируется значение кода маски IM52=01Е5, в котором установлены в нулевое состояние разряды соответствующие первым старшим четырем ненулевым символам. Далее в такте 8 сжимаются младшие два ненулевых символа (Е, А), которые поступают на входы данных ID53=EA00, и формируется значение кода маски IM53=0005, в котором установлены в нулевое состояние разряды соответствующие старшим восьми ненулевым символам. Одновременно в такте 7, при единичном значении на выходе D-триггера 10, первое значение кода маски М=В3Е5 для пятых данных DD5 записывается в регистр маски 9 (QM=В3Е5), а также на внутренней шине приоритета MS формируется не нулевое значение (MS=01E5) и соответственно нулевое значение флага нуля FZ=0, которое на такте 8 записывается в D-триггер 10. Аналогично в такте 8 на внутренней шине приоритета MS формируется не нулевое значение (MS=0005) и соответственно нулевое значение флага нуля FZ=0, которое на такте 9 сохраняется в D-триггере 10. Далее в такте 9 на внутренней шине приоритета MS формируется нулевое значение (MS=0000) и соответственно единичное значение флага нуля FZ=1, которое на такте 10 принимается в D-триггер 10. Одновременно на тактах 8, 9, 10, аналогично вышеприведенному восстановлению для вторых данных DD2, на входы IQ1, IQ2, …, IQ16 выходного буфера 6 передаются соответственно четыре, затем восемь и далее десять ненулевых символов соответствующих пятым данным DD5, которые на следующем такте 11 записываются в выходной буфер 6, так как в такте 10 D-триггер 10 был установлен в единичное состояние, и поступают на внешние выходы 13 соответствующих выходных символов Q1, Q2, …, Q16 (QD5 на фиг. 5). Таким образом, декомпрессия входных данных DD5, содержащих десять ненулевых символов и поступивших на такте 6, проведена за пять тактов.

В такте 9 шестые данные DD6 содержат четыре ненулевых символа (С, В, А, 9), которые на такте 10 и соответствующий код маски принимаются во входной регистр 2 - D=CBA9 и M=0F00. Далее аналогично декомпрессии для первых данных DD1 или четвертых данных DD4, которые также содержат по четыре ненулевых символа, проводится восстановление для данных DD6. При этом на такте 11 проводится запись только четырех символов (С, В, А, 9) в соответствующие регистры 5₁, 5₂, …, 5₁₆, в соответствии с кодом маски M=0F00. Запись результата QD6 в выходной регистр 6 осуществляется на такте 12 (QD6 на фиг. 5). Таким образом, декомпрессия входных данных DD6, содержащих четыре ненулевых символа и поступивших на такте 9, проведена за три такта.

Таким образом, вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство решает поставленную задачу по декомпрессии данных без потери информации. При этом N выходных символов по k разрядов восстановленных данных Q1, Q2, …, QN соответствуют данным DD до компрессии (сжатия) без потери информации.

В сравнении с прототипом в предлагаемом устройстве сокращается разрядность входных данных за счет исключения внутренней L разрядной шины указателей групп символов U. В прототипе и предлагаемом устройстве, когда входные данные из N символов содержат до w ненулевых символов или только нулевые символы, восстановленные данные передаются на выходы Q1, Q2, …, QN через три такта. В предлагаемом устройстве для входной последовательности, содержащей V ненулевых символах, восстановленные данные передаются на выходы Q1, Q2, …, QN через (] V/w [+2) такта (где] [большее целое) независимо от распределения ненулевых символов во входных данных DD, а в прототипе, при включении во входные группы ID из w ненулевых символов отдельных символов из соседних групп, суммарное количество ненулевых символов в соседних группах не должно превышать w, что требует дополнительных тактов для передачи данных. Поэтому в прототипе количество тактов зависит не только от количества ненулевых символов, но и от их расположения в данных до компрессии. Например, для вторых данных DD2, содержащих восемь ненулевых символов (такт 2 на фиг. 5), в предлагаемом устройстве восстановленные данные поступают на выходы Q1, Q2, …, QN через четыре такта на такте 6, а в прототипе для восстановления данных необходимо пять тактов, так как входная последовательность в прототипе будет содержать три группы ненулевых символов (1, В, 9, 8), (8, 7, 6, 5), (2). Аналогично для пятых данных DD5, содержащих десять ненулевых символов (такт 6 на фиг. 5), в предлагаемом устройстве требуется пять тактов (восстановленные данные передаются на такте 11), а в прототипе необходимо шесть тактов, так как ненулевые символы (7, В) и (Е, А) невозможно объединить во входные группы ID с ненулевыми символами (A, F, С) (1, 2, 3) соседних групп. Следовательно, в предлагаемом устройстве необходимо меньшее количество тактов для декомпрессии данных, и, кроме того, сокращается объем памяти для хранения данных после компрессии.

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

Изобретение относится к области вычислительной техники и предназначено для использования в системах обработки информации, а также может быть применено в блоках сжатия и распаковки данных без потерь в системах для рационального использования устройств хранения и передачи данных, обработки данных физических экспериментов. Техническим результатом изобретения является повышение быстродействия за счет сокращения разрядности входных данных. Устройство содержит входной регистр данных 2, многовыходной блок приоритета 3, группу из N коммутаторов данных 4₁, 4₂, …, 4_N, группу из N регистров 5₁, 5₂, …, 5_N, выходной буфер 6, элемент ИЛИ-НЕ 7, N групп 8₁, 8₂, …, 8_N по k элементов 2И, регистр маски 9, D-триггер 10, а также шину входных данных 1, внешний вход синхронизации 11, внешний вход синхронной установки нулевое состояние 12, внешние выходы 13, внутренние шину данных D, первую шину маски символов М, вторую шину маски символов QM, шину приоритета MS и w групп N разрядных указателей старшей единицы S1, S2, …, Sw. Причем шина входных данных 1 содержит группу входных разрядов данных ID, которые состоят из w символов по k разрядов, и группу входных N разрядов маски символов IM. 5 ил.

Устройство для декомпрессии данных, содержащее шину входных данных 1, соединенную с входным регистром данных 2, выходной буфер 6, выходы которого содержат N выходных символов Q1, Q2, …, QN по k разрядов и являются внешними выходами устройства 13, многовыходной блок приоритета 3, который содержит w групп выходов S1, S2, …, Sw по N разрядов, группу из N коммутаторов данных 4₁, 4₂, …, 4_N, группу регистров 5 с синхронным входом R установки в нулевое состояние, элемент ИЛИ-НЕ 7, D-триггер 10 с синхронным входом R установки в нулевое состояние,

а также содержащее внешний вход С синхронизации 11, внешний вход R синхронной установки в нулевое состояние 12, внутреннюю шину данных D из w символов по к разрядов, внутреннюю N разрядную первую шину маски символов М,

причем внешний вход синхронизации 11 соединен с входами синхронизации С входного регистра данных 2, группы регистров 5, выходного буфера 6 и D-триггера 10, а внешний вход 12 синхронной установки в нулевое состояние соединен с входами R синхронной установки в нулевое состояние входного регистра 2, выходного буфера 6 и D-триггера 10, а выход D-триггера 10 соединен с входом СЕ разрешения работы выходного буфера 6,

причем шина входных данных 1 содержит группу входных разрядов данных ID из w символов по k разрядов, группу входных N разрядов маски символов IM, при этом выходы входного регистра 2 являются соответствующими w*k разрядами внутренней шины данных D и соответствующими N разрядами внутренней первой шины маски символов М,

причем все N разрядов внутренней первой шины маски символов М соединены с входами многовыходного блока приоритета 3, а все w*k разрядов внутренней шины данных D соединены с информационными входами каждого коммутатора данных группы из N коммутаторов данных 4₁, 4₂, …, 4_N, управляющие входы выборки которых соединены с соответствующими одноименными разрядами w групп выходов S1, S2, …, Sw многовыходного блока приоритета 3,

отличающееся тем, что в него дополнительно введены N групп 8₁, 8₂, …, 8_N по k элементов 2И, регистр маски 9, а группа регистров 5 содержит N регистров 5₁, 5₂, …, 5_N по k разрядов,

а также введены внутренняя (N-w) разрядная шина приоритета MS, которая является группой вторых выходов многовыходного блока приоритета 3, внутренняя N разрядная вторая шины маски символов QM, которая является группой выходов регистра маски 9, и флаг нуля FZ,

причем выходы группы из N коммутаторов данных 4₁, 4₂, …, 4_N соединены с соответствующими информационными входами D одноименных регистров группы из N регистров 5₁, 5₂, …, 5_N, у которых входы R синхронной установки в нулевое состояние соединены с внешним входом 12 синхронной установки в нулевое состояние, а управляющие входы СЕ разрешения работы соединены с одноименными разрядами внутренней N разрядной первой шины маски символов М, а выходы QB1, QB2, …, QBN всех N регистров 5₁, 5₂, …, 5_N соединены по группам с соответствующими первыми входами элементов 2И одноименных N групп 8₁, 8₂, …, 8_N, выходы которых соединены с соответствующими группами информационных входов IQ1, IQ2, …, IQN выходного буфера 6, а вторые входы элементов 2И из N групп 8₁, 8₂, …, 8_N по группам соединены между собой и подключены к соответствующим одноименным разрядам внутренней N разрядной второй шины маски QM,

кроме того, (N-w) разрядов внутренней шины приоритета MS соединены с входами элемента ИЛИ-НЕ 7, выход которого является флагом нуля FZ и соединен с информационным D-входом D-триггера 10, выход которого также соединен с входом СЕ разрешения работы регистра маски 9, у которого вход синхронизации С соединен с внешним входом С синхронизации 11, вход R синхронной установки в нулевое состояние соединен с внешним входом 12 синхронной установки в нулевое состояние, а группа информационных D-входов соединены с N разрядами внутренней первой шины маски символов М.