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

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

Известен способ сжатия данных (RU №2386210 С2, МПК Н03М 7/40, Н03М 7/46, заявлено 04.08.2006, опубликовано 10.04.2010, Бюл. №10), в котором сжатие данных осуществляется с помощью кодера. В первом блоке памяти кодера хранятся предварительно записанные кодовые комбинации (КК₁) с числом разрядов n, где n=2, 3, 4, …, представляющие собой полный набор возможных входных кодовых комбинаций (КК). Во втором блоке памяти кодера хранятся предварительно записанные кодовые комбинации КК₂, однозначно соответствующие КК₁, с числом разрядов, меньшим или таким же, как в КК₁. Входной поток данных разделяют на КК с одинаковым числом разрядов n. КК последовательно вводят в кодер, идентифицируют путем сравнения с КК₁, отображают соответствующий выходной кодовой комбинацией КК₂. КК₂ представляют собой последовательность групп с одинаковым числом разрядов n в каждой. Совокупное число кодовых комбинаций КК₂-mⁿ, где m=2, 3, 4, …, n=1, 2, 3, …. Число последовательных групп КК определяют как m^n-1, m^n-2, …. Разрядность КК2 в группе выравнивают за счет добавления незначащего нуля перед кодовой комбинацией.

Известен способ сжатия восстановления данных без потерь (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₁)/₂, а для восстановления потока данных выполняют обратные операции.

Известно эффективное по использованию памяти адаптивное блочное кодирование (RU №2413360 С1, МПК Н03М 7/40, заявлено 14.11.2007, опубликовано 27.02.2011, Бюл. №6), в котором используется кодирование переменной длины (VLC) с низкой сложностью данных. Структура кода определяет группы кодовых слов в кодовом дереве, причем каждая из групп включает в себя кодовые слова, представляющие значения, имеющие одинаковые весовые коэффициенты, и кодовые слова упорядочиваются лексикографически относительно значений, представленных посредством кодовых слов. Кроме того, структура кода определяет первую и вторую подгруппу кодовых слов в каждой из групп, при этом первая подгруппа включает в себя кодовые слова, имеющие первую длину, а вторая подгруппа - вторую длину, отличную от первой длины. Затем формируют результат кодирования переменной длины, по меньшей мере, для одного из сохранений в запоминающем устройстве, передачи в устройство или представлении пользователю.

Известно кодирующее устройство (RU №153302 U1, МПК Н03М 7/30, заявлено 17.06.2014, опубликовано 10.07.2015, Бюл. №19), содержащее входной регистр, анализатор разрядов, блок управления ключами, блок ключей, ПЗУ, блок мультиплексоров, выходной регистр, а также тактовый генератор, делитель частоты, счетчик и выходной регистр со следующими соединениями: выход входного регистра 1-n соединен с входами анализатора разрядов и с блоком управления ключами, выходы 1-n² анализатора соединены с информационными входами блока ключей, а выходы 1-n² - с управляющими входами этого блока, выходы которого 1-n² соединены с входами ПЗУ, а выходы 1-2n ПЗУ соединены с информационными входами блока мультиплексора, выходы которого 1-n являются выходами маркера устройства; выходы 3-8 входного регистра соединены с выходным регистром, выходы которого являются выходами информационных разрядов устройства; выход тактового генератора через счетчик соединен с управляющими входами блока мультиплексоров, а через делитель частоты - с управляющими входами: через выход 1 входного регистра, через выход 2 с блоком управления ключами, а через выход 3 с выходным регистром.

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

Известно устройство для сжатия данных (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 символов по k разрядов, внутреннюю N разрядную шину маски символов М, внутреннюю L разрядную шину указателей групп символов U.

Недостатками данного устройства являются схемная сложность, связанная с реализацией L блоков счета количества единиц 5 (L - количество групп по w символов из k разрядов, причем N=L*w), группы из (L-1) сумматоров 6₁, 6₂, …, 6_L-1, группы из (L-1) схем сравнения 7₁, 7₂, …, 7_L-1, аппаратные затраты на хранение указателей групп символов U и временные затраты при формировании и передаче сжатых групп.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип устройство для компрессии данных (RU №2672625 С1, МПК Н03М 7/30, заявлено 11.12.2017, опубликовано 16.11.2018, Бюл. №32), содержащее N входных символов D1, D2, …, DN по k разрядов соединенных с входным регистром данных 1, первую группу из N элементов ИЛИ 2₁, 2₂, …, 2_N, первую группу из N элементов И 3₁, 3₂, …, 3_N, многовыходной блок приоритета 4, элемент ИЛИ-НЕ 8, вторую группу из (N-1) элементов ИЛИ 9₁, 9₂, …, 9_(N-1), группу из N синхронных D-триггеров 10₁, 10₂, …, 10_N, блок коммутаторов данных 11, выходной буфер 12, а также введены внешний вход С синхронизации 15, внешний вход CLR асинхронной установки в нулевое состояние 14, внешние выходы Q устройства 16, внутренняя шина данных DD из N символов по k разрядов, внутренняя N разрядная шина маски символов М, внутренняя N разрядная шина выходов триггеров Т и группа из W внутренних шин указателей старших символов U1, U2, …, UW, причем в блок коммутатора данных введены W коммутаторов 11₁, 11₂, …, 11_W, а в многовыходной блок приоритета введены W каскадов 4₁, 4₂, …, 4_W, причем внешний вход CLR асинхронной установки в нулевое состояние 14 соединен с входами CLR асинхронной установки в нулевое состояние входного регистра 1 и выходного буфера 12, а также входами CLR асинхронной установки в нулевое состояние всех триггеров 10₁, 10₂, …, 10_N, внешний вход С синхронизации 15 соединен с входами синхронизации С всех триггеров 10₁, 10₂, …, 10_N, входного регистра 1 и выходного буфера 12, выходы входного регистра данных 1 соединены с внутренней шиной данных DD, из которой группами из k разрядов по символам соединены с соответствующими входами одноименных символам элементам первой группы из N элементов ИЛИ 2₁, 2₂, …, 2_N, выходы которых соединены со вторыми входами одноименных элементов первой группы элементов И 3₁, 3₂, …, 3_N, выходы которых являются разрядами внутренней шины маски символов М, которые также соединены с первой группой входов выходного буфера 12, в многовыходном блоке приоритета 4 выходы w каскадов являются соответствующими разрядами одноименных внутренних шин указателей старших символов из группы U1, U2, …, Uw, причем первая шина U1 имеет высший ранг приоритета, а старший разряд в каждой шине U1, U2, …, Uw имеет старший приоритет, а вторая группа выходов запроса в следующий каскад последнего w-го каскада многовыходного блока приоритета 6 соединена с входами элемента ИЛИ-НЕ 8, выход которого является флагом нулевых символов FZ и соединен с синхронными входами установки в нулевое состояние R всех триггеров 10₁, 10₂, …, 10_N и входом разрешения работы СЕ входного регистра данных 1, причем соответствующие одноименные разряды группы из W внутренних шин указателей старших символов U1, U2, …, UW соединены с соответствующими входами одноименных элементов из второй группы из (N-1) элементов ИЛИ 9₁, 9₂, …, 9_(N-1), выходы которых соединены с входами разрешения работы СЕ соответствующих одноименных триггеров 10₁, 10₂, …, 10_(N-1), а вход разрешения работы СЕ последнего N-го триггера 10_N соединен с последним старшим разрядом U_1N первой внутренней шины U1 указателей старших символов, инверсные выходы всех триггеров 10₁, 10₂, …, 10_N соединены с информационными входами D соответствующих одноименных триггеров 10₁, 10₂, …, 10_N, а также являются разрядами внутренней N разрядной шины выходов триггеров Т, которая поразрядно соединена с первыми входами соответствующих одноименных элементов И первой группы из N элементов И 3₁, 3₂, …, 3_N, информационные входы всех W коммутаторов 11₁, 11₂, …, 11_W соединены с внутренней шиной данных DD, а управляющие входы каждого i-го коммутатора 11_i соединены с соответствующей i-ой внутренней шиной Ui указателей старших символов, выходы всех W коммутаторов 11₁, 11₂, …, 11_W соединены с соответствующими W группами входов из k разрядов, начиная со второй группы входов, выходного буфера 12, выходы Q которого являются внешними выходами устройства 16.

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для упаковки данных содержащее N входных символов ID1, ID2, …, IDN по k разрядов соединенных с входным регистром данных 2, формирователь маски 3, содержащий группу из N элементов ИЛИ, многовыходной блок приоритета 6, содержащий w каскадов, блок коммутаторов данных 7, содержащий w коммутаторов 7₁, 7₂, …, 7_W, выходной буфер 9, элемент ИЛИ-НЕ 10, внешний вход С синхронизации 12, внешний вход R синхронной установки в нулевое состояние 13, внешние выходы Q устройства 14, содержащие w символов по k разрядов, а также внутреннюю шину данных DD из N символов по k разрядов, внутреннюю N разрядную шину маски символов М, группу из w внутренних шин указателей старших символов U1, U2, …, Uw (где w количество выходных символов), внутреннюю шину остаточной маски MS и флаг нулевых символов (флаг нуля) FZ,

причем внешний вход R синхронной установки в нулевое состояние 13 соединен с входами R синхронной установки в нулевое состояние входного регистра 2 и выходного буфера 9,

внешний вход С синхронизации 12 соединен с входами синхронизации С входного регистра 2 и выходного буфера 9,

выходы входного регистра данных 2 соединены с внутренней шиной данных DD, из которой группами из k разрядов по символам соединены с соответствующими входами одноименных символам элементов группы из N элементов ИЛИ формирователя маски 3,

в многовыходном блоке приоритета 6 выходы w каскадов являются соответствующими разрядами одноименных внутренних шин указателей старших символов из группы U1, U2, …, Uw, причем первая шина U1 имеет высший ранг приоритета, а старший разряд в каждой шине U1, U2, …, Uw имеет старший приоритет, а вторая группа выходов запроса в следующий каскад последнего w-го каскада многовыходного блока приоритета 6 является внутренней шиной остаточной маски MS,

кроме того информационные входы всех w коммутаторов 7₁, 7₂, …, 7_W соединены с внутренней шиной данных DD, а управляющие входы каждого коммутатора 7₁, 7₂, …, 7_W соединены с разрядами соответствующей одноименной внутренней шины U1, U2, …, Uw указателей старших символов, а выход элемента ИЛИ-НЕ 10 соединен с входом разрешения работы СЕ входного регистра данных 2 и является флагом нулевых символов FZ, выходы 14 выходного буфера 9 являются внешними выходами Q устройства, дополнительно введены коммутатор маски 4, регистр маски 5, коммутатор маски-данных 8 и синхронный D-триггер 11, а в выходной буфер 9 введены L разрядов (где L≥max (N, w*k)),

причем внешний вход R синхронной установки в нулевое состояние 13 также соединен с входами R синхронной установки в нулевое состояние регистра маски 5 и синхронного D-триггера 11, а внешний вход С синхронизации 12 также соединен с входами синхронизации С регистра маски 5 и синхронного D-триггера 11,

выходы элементов группы из N элементов ИЛИ формирователя маски 3 являются соответствующими разрядами внутренней шины маски символов М, которая соединена с соответствующими разрядами первых групп информационных входов коммутатора маски 4 и коммутатора маски-данных 8,

кроме того внутренняя шина остаточной маски MS соединена с соответствующими разрядами нулевой группы информационных входов коммутатора маски 4, выходы которого соединены с информационными входами регистра маски 5 и с входами элемента ИЛИ-НЕ 10, выход которого также соединен с информационным входом D-триггера, у которого выход ТСЕ соединен с управляющими входами коммутатора маски 4 и коммутатора маски-данных 8,

кроме того разряды выходов всех w коммутаторов 7₁, 7₂, …, 7_W соединены с соответствующими разрядами нулевой группы коммутатора маски-данных 8, выходы которого соединены с соответствующими информационными входами выходного буфера 9.

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

В устройстве приняты следующие обозначения:

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

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

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

D - информационный вход триггера,

DG - входная группа данных,

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

FM - формирователь маски, содержащий группу из N элементов ИЛИ,

FU - многовыходной блок приоритета, содержащий w каскадов,

FZ - флаг нулевых символов (флаг нуля),

ID1, ID2, …, IDN - N входных символов по k разрядов,

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

KD - коммутатор данных,

KM - коммутатор маски,

KMD - коммутатор маски-данных,

L - разрядность выходного буфера, где L≥max (N, w*k),

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

MS - внутренняя шина остаточной маски,

N - количество входных символов по k разрядов

ТСЕ - выход триггера,

Q - выходная шина разрядностью w*k,

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

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

RG - регистр,

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

U1, U2, …, Uw - группа из w внутренних шин указателей старших символов,

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

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

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

1 - внешние входы данных ID1, ID2, …, IDN,

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

3 - формирователь маски FM,

4 - коммутатор маски КМ,

5 - регистр маски RM,

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

7₁, 7₂, …, 7_W - w коммутаторов блока коммутаторов данных KD,

8 - коммутатор маски-данных KMD,

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

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

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

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

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

14 - внешние выходы Q.

Устройство для упаковки данных содержит N входных символов ID1, ID2, …, IDN по k разрядов соединенных с входным регистром данных 2, формирователь маски 3, содержащий группу из N элементов ИЛИ, коммутатор маски 4, регистр маски 5, многовыходной блок приоритета 6, содержащий w каскадов, блок коммутаторов данных 7, содержащий w коммутаторов 7₁, 7₂, …, 7_W, коммутатор маски-данных 8, выходной буфер 9, элемент ИЛИ-НЕ 10, синхронный D-триггер 11, внешний вход С синхронизации 12, внешний вход R синхронной установки в нулевое состояние 13, внешние выходы Q устройства 14, содержащие w символов по k разрядов, а также внутреннюю шину данных DD из N символов по k разрядов, внутреннюю N разрядную шину маски символов М, группу из w внутренних шин указателей старших символов U1, U2, …, Uw (где w - количество выходных символов), внутреннюю шину остаточной маски MS и флаг нулевых символов (флаг нуля) FZ.

Входной регистр данных 2 содержит N*k информационных разрядов и предназначен для хранения текущего массива N входных символов ID1, ID2, …, IDN по k разрядов, а также содержит вход разрешения записи СЕ, вход синхронизации С и вход синхронной установки в нулевое состояние R. Выходы входного регистра данных 2 являются внутренней шиной данных DD.

Выходной BQ буфер 9 содержит L разрядов, где L≥max (N, w*k) и предназначен для хранения выходных последовательностей упакованных значений маски и ненулевых символов.

Регистр маски 5, выходной буфер 9 и синхронный D-триггер 11 содержат вход синхронизации С и вход синхронной установки в нулевое состояние R.

Коммутатор маски 4, коммутатор маски-данных 8 и каждый w коммутаторов 7₁, 7₂, …, 7_W содержат двухвходовые мультиплексоры с одним управляющим (адресным) входом.

Внешний вход R синхронной установки в нулевое состояние 13 соединен с входами R синхронной установки в нулевое состояние входного регистра 2, регистра маски 5, выходного буфера 9 и синхронного D-триггера 11.

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

Разряды внутренней шины данных DD группами из k разрядов по символам соединены с соответствующими входами одноименных символам элементов группы из N элементов ИЛИ формирователя маски 3, выходы которых являются N разрядами внутренней шины маски символов М.

В многовыходном блоке приоритета 6 выходы w каскадов являются соответствующими разрядами одноименных внутренних шин указателей старших символов из группы U1, U2, …, Uw, причем первая шина U1 имеет высший ранг приоритета, а старший разряд в каждой шине U1, U2, …, Uw имеет старший приоритет, а вторая группа выходов запроса в следующий каскад последнего w-го каскада многовыходного блока приоритета 6 является внутренней шиной остаточной маски MS.

Информационные входы всех w коммутаторов 7₁, 7₂, …, 7_W соединены с внутренней шиной данных DD, а управляющие входы каждого коммутатора 7₁, 7₂, …, 7_W соединены с разрядами соответствующей одноименной внутренней шины U1, U2, Uw указателей старших символов.

Внутренняя шина маски символов М соединена с соответствующими разрядами первых групп информационных входов коммутатора маски 4 и коммутатора маски-данных 8.

Внутренняя шина остаточной маски MS соединена с соответствующими разрядами нулевой группы информационных входов коммутатора маски 4, выходы которого соединены с информационными входами регистра маски 5 и с входами элемента ИЛИ-НЕ 10, выход которого является флагом нулевых символов FZ, а также соединен с входом разрешения работы СЕ входного регистра данных 2 и с информационным входом D-триггера, у которого выход ТСЕ соединен с управляющими входами коммутатора маски 4 и коммутатора маски-данных 8.

Разряды выходов всех w коммутаторов 7₁, 7₂, …, 7_W соединены с соответствующими разрядами нулевой группы коммутатора маски-данных 8, выходы которого соединены с соответствующими информационными входами выходного буфера 9. Выходы 14 выходного буфера 12 являются внешними выходами Q устройства.

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

Для входной группы данных DG содержащей N символов по k разрядов ID1, ID2, …, IDN формируется N разрядный код маски М, который записывается в регистр RM маски 5 и в выходной BQ буфер 9. Далее, в соответствии с единичными значениями разрядов маски М, которые соответствуют ненулевым символам входной группы данных DG,, многовыходной блок FU приоритета 6 формирует w кодов указателей приоритета в единичном кодировании в коде «1 из N», по которым блок KD коммутатора данных 7₁, 7₂, …, 7_W выбирает w старших входных ненулевых символов, которые записываются в выходной BQ буфер 9. Далее соответствующие выбранным символам единичные значения разрядов маски обнуляются, и полученный код маски поступает на внутреннюю шину MS остаточной маски и записывается в регистр RM маски 5. Затем аналогично выбираются следующие w старших входных ненулевых символов, пока не будут переданы все ненулевые символы. При нулевых значениях всех разрядов кода маски М или внутренней шины MS остаточной маски, которые выбираются коммутатором КМ маски 4, формируется единичное значение флага нулевых символов FZ=1, по которому во входной регистр RD данных 2 записывается код следующих входных данных ID1, ID2, …, IDN.

Перед началом работы, при единичном значении на внешнем входе R синхронной установки в нулевое состояние 13, при подаче синхросигнала С на входе 12 устанавливаются в начальное нулевое состояние входной регистр RD данных 2, регистр RM маски 5, выходной BQ буфер 9 и D-триггер 11. При этом формируется нулевое значение на выходе ТСЕ=0 синхронного D-триггера 11 и устанавливается единичное значение флага нулевых символов FZ=1.

На следующем такте сигнала С, при значении флага нулевых символов FZ=1, входная группа данных DG1, содержащая символы D1, ID2, …, IDN, с внешних входов 1 (фиг. 2) записывается во входной регистр RD данных 2 и поступает на внутреннюю шину DD данных из N символов по k разрядов.

В группе из N элементов ИЛИ формирователя FM маски 3 определяют ненулевые символы и формируют маску символов М из N разрядов. Каждый разряд маски символов М принимает единичное значение, если соответствующий символ ненулевой, или нулевое значение, если соответствующий символ нулевой.

Значение кода маски М передается через первые группы информационных входов коммутатора КМ маски 4 и коммутатора KMD маски-данных 8 и на следующем такте сигнала С записывается соответственно в регистр RM маски 5 и в выходной BQ буфер 9.

Одновременно значение кода маски М с выходов коммутатора КМ маски 4 поступает на входы элемента ИЛИ-НЕ 10, на выходе которого формируется единичное значение флага нулевых символов FZ=1 при отсутствии ненулевых символов (все разряды маски М имеют нулевые значения) или нулевое значение флага нулевых символов FZ=0, если имеются ненулевые разряды маски М. При этом значение флага нулевых символов FZ записывается на следующем такте сигнала С в синхронный D-триггер 11.

Далее с выходов регистра RM маски 5, в соответствии со значениями разрядов маски символов М, в w каскадах многовыходного блока FU приоритета 6 формируются значения w групп соответствующего ранга приоритета, которые поступают на соответствующие разряды группы из w внутренних шин указателей старших символов U1, U2, …, Uw (причем первая шина U1 имеет высший ранг приоритета, а старший разряд в каждой шине U1, U2, …, Uw имеет старший приоритет). На каждой шине U1, U2, …, Uw указателей старших символов устанавливается значение в единичном кодировании в коде «1 из N».

В соответствии с приоритетом w коммутаторов 7₁, 7₂, …, 7_W блока коммутаторов данных KD передают не более w соответствующих старших ненулевых символов с шины данных DD на соответствующие группы входов символов выходного BQ буфера 9, при нулевом значении на выходе ТСЕ=0 синхронного D-триггера 11 (фиг. 3). Запись в выходной BQ буфер 9 выполняется по тактовому сигналу С

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

При наличии единичных значений в разрядах остаточной маски MS (при наличии необработанных ненулевых символов) формируется нулевое значение флага нулевых символов FZ=0, которое записывается в синхронный D-триггер 11 и устанавливается нулевое значение на выходе ТСЕ=0, по которому в коммутаторе КМ маски 4 и коммутаторе KMD маски-данных 8 на выходы передаются нулевые группы информационных входов - соответственно значения разрядов остаточной маски MS и значения выбранных ненулевых символов с выходов w коммутаторов 7₁, 7₂, …, 7_W блока коммутаторов данных KD.

При нулевых значениях всех разрядов остаточной маски MS (при отсутствии необработанных ненулевых символов) формируется единичное значение флага нулевых символов FZ=1, по которому на следующем такте С следующая новая входная группа данных DG содержащая символы ID1, ID2, …, IDN (фиг. 2) записывается с внешних входов 1 во входной регистр RD данных 2. При этом единичное значение флага нулевых символов FZ=1 также записывается в синхронный D-триггер 11 и новое значение маски М, для новой входной группы данных DG, с первой группы входов коммутатора КМ маски 4 передается на входы регистра RM маски 5.

При нулевых значениях всех разрядов начальной маски М (при отсутствии ненулевых входных символов), нулевой код маски также записывается в выходной BQ буфер 9, а также формируется единичное значение флага нулевых символов FZ=1, по которому на следующем такте С во входной регистр RD данных 2 записывается следующая новая входная группа данных DG содержащая символы ID1, ID2, …, IDN с внешних входов 1.

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

В потактовой временной диаграмме на фиг. 4 приведены примеры для входных групп данных DG1, DG2, …, DG6 содержащих символы данных ID1, ID2, …, ID16 (IDN) на внешних входах 1 и упаковка данных в предлагаемом устройстве, при количестве входных символов N=16 по k=4 разряда и количестве символов w=4 по k=4 разряда в выходных данных Q. На фиг. 4 в скобках указана форма представления данных - двоичная (2) или шестнадцатеричная (16).

При единичном значении на внешнем входе R синхронной установки в нулевое состояние 13 по синхросигналу С на входе 12 устанавливаются в начальное нулевое состояние входной регистр RD данных 2, регистр RM маски 5, выходной BQ буфер 9 и D-триггер 11. При этом формируется нулевое значение на выходе ТСЕ=0 синхронного D-триггера 11 и устанавливается единичное значение флага нулевых символов FZ=1 (такт 1 на фиг. 4).

Одновременно на такте 1 (фиг. 4) на внешние входы данных 1 поступает первая группа входных данных DG1 из символов ID1, ID2, …, ID16 (IDN), содержащий четыре ненулевых символа (В, А, 5,2)₁₆.

По следующему тактовому сигналу С на внешнем входе 12 (такт 2) входные символы ID1, ID2, …, ID16 (IDN) с внешних входов 1 записываются во входной регистр RD данных 2, на входе разрешения СЕ которого установлено единичное значение СЕ=1, которое передается с флага нулевых символов FZ=1. Одновременно единичное значение флага нулевых символов FZ=1 записывается в синхронный D-триггер 11 и устанавливается единичное значение на выходе ТСЕ=1. С выхода регистра RD данных 2 коды N символов данных передаются на соответствующие разряды внутренней шины DD данных из N символов по k разрядов.

Для каждого из N символов k разрядов поступают на входы соответствующего одноименного элемента ИЛИ группы из N элементов ИЛИ формирователя FM маски, определяют ненулевые символы и формируют маску символов М из N разрядов (в такте 2 для четырех ненулевых символов формируется маска М1=0С24). Каждый разряд маски символов М принимает единичное значение, если соответствующий символ ненулевой, или нулевое значение, если соответствующий символ нулевой.

При единичном значении на выходе ТСЕ=1 синхронного D-триггера 11 код маски M1 передается через первые группы информационных входов на выходы коммутатора КМ маски 4 и коммутатора KMD маски-данных 8 и на следующем такте 3 сигнала С записывается соответственно в регистр RM маски 5 и в выходной BQ буфер 9. Одновременно, так как значение маски М1=0С24 не равно нулю и установлено нулевое значение флага нулевых символов FZ=0, то в такте 3 в синхронном D-триггере 11 на выходе устанавливается нулевое значение ТСЕ=0.

Далее на такте 3 с выходов регистра RM маски 5 в соответствии со значениями разрядов кода маски символов М1=0С24 в w каскадах многовыходного блока FU приоритета 6 формируются значения w групп соответствующего ранга приоритета, которые поступают на соответствующие разряды группы из w внутренних шин указателей старших символов (U1=0800, U2=0400, U3=0020, U4=0004). В соответствии с приоритетом w коммутаторов 7₁, 7₂, …, 7_W блока коммутаторов данных KD передают с шины DD соответствующие четыре ненулевые символа (В, А, 5, 2)₁₆ на нулевые группы коммутатора KMD маски-данных 8, которые при нулевом значении выхода ТСЕ=0 передаются на соответствующие w групп входов символов выходного BQ буфера 9, запись в который проводится на следующем такте 4 (выходные данные Q11=BA52₁₆) и выдача на внешние выходы Q устройства.

Одновременно на такте 3, со второй группы выходов многовыходного блока FU приоритета 6, на всех разрядах внутренней шины MS остаточной маски устанавливаются нулевые значения MS11=0000, которые передаются на нулевые информационные входы коммутатора КМ маски 4 и при нулевом значении выхода ТСЕ=0 передаются на входы элемента ИЛИ-НЕ 10, на выходе которого формируется единичное значение флага нулевых символов FZ=1, так как все ненулевые символы первой группы данных DG1 из символов ID1, ID2, …, ID16 (IDN) обработаны и переданы в выходной BQ буфер 9.

Кроме того, на такте 3 на внешние входы данных 1 поступает вторая группа входных данных DG2 из символов ID1, ID2, …, ID16 (IDN), содержащая только нулевые символы, которые на следующем такте 4 записываются во входной регистр RD данных 2, на входе разрешения СЕ которого установлено единичное значение СЕ=1, которое передается с флага нулевых символов FZ=1.

Далее на такте 4 формируется маска символов М2=0000, так как все символы нулевые, и при единичном значение на выходе ТСЕ=1 синхронного D-триггера 11 код маски М2 передается через первые группы информационных входов коммутатора КМ маски 4 и коммутатора KMD маски-данных 8. На следующем такте 5 сигнала С код маски М2=0000 записывается соответственно в регистр RM маски 5 и в выходной BQ буфер 9. При этом также формируется единичное значение флага нулевых символов FZ=1.

Поэтому на такте 5, третья группа входных данных DG3 из символов ID1, ID2, …, ID16 (IDN), содержащая восемь ненулевых символов (Е, В, 9, 8, 7, 6, 3, 1)₁₆, записывается во входной регистр RD данных 2, на входе разрешения СЕ которого установлено единичное значение СЕ=1. При этом в формирователе FM маски 3 формируется маска символов М3=4В6А, содержащая единичные значения в восьми разрядах, соответствующих ненулевым символам.

Далее на такте 6 код маски М3=4В6А передается через первые группы информационных входов коммутатора КМ маски 4 и коммутатора KMD маски-данных 8 и записывается соответственно в регистр RM маски 5 и в выходной BQ буфер 9. Одновременно также в w каскадах многовыходного блока FU приоритета 6 формируются значения w=4 групп соответствующего ранга приоритета, для старших ненулевых символов, которые поступают на соответствующие разряды группы из w внутренних шин указателей старших символов (U1=4000, U2=0800, U3=0200, U4=0100). В соответствии с данными приоритетами w коммутаторов 7₁, 7₂, …, 7_W блока коммутаторов данных KD передают соответствующие старшие четыре ненулевые символа (Е, В, 9, 8)₁₆ на нулевые группы коммутатора KMD маски-данных 8, и далее, при нулевом значении выхода ТСЕ=0, передаются на соответствующие w групп входов символов выходного BQ буфера 9, запись в который проводится на следующем такте 7 (Q31=EB98₁₆).

Кроме того на такте 6, со второй группы выходов многовыходного блока FU приоритета 6, на разрядах внутренней шины MS остаточной маски устанавливаются значения MS31=006А, которые передаются на нулевые информационные входы коммутатора КМ маски 4 и при нулевом значении выхода ТСЕ=0 передаются на входы элемента ИЛИ-НЕ 10, на выходе которого формируется нулевое значение флага нулевых символов FZ=0, так как обработаны не все ненулевые символы третьей входной группы данных DG3 из символов ID1, ID2, …, ID16 (IDN).

Далее на такте 7 код остаточной маски MS31=006A записывается в регистр RM маски 5 и запрещена запись с внешних входов 1 во входной регистр RD данных 2, так как установлено нулевое значение флага нулевых символов FZ=0. Далее аналогично формируются указатели старших символов (U1=0040, U2=0020, U3=0008, U4=0002) и коммутаторами 7₁, 7₂, …, 7_W блока коммутаторов данных KD передаются следующие четыре ненулевых символа (7, 6, 3, 1)₁₆ на соответствующие w групп входов символов выходного BQ буфера 9, запись в который проводится на следующем такте 8 (Q32=7631₁₆).

Одновременно на такте 7 (фиг. 4) на внешние входы данных 1 поступает четвертая группа входных данных DG4 из символов ID1, ID2, …, ID16 (IDN) содержащая четыре ненулевых символа (А, С, F, 4)₁₆. Далее на тактах 8-10 группа входных данных DG4 обрабатывается аналогично рассмотренному выше алгоритму работы при обработке первой группы входных данных DG1. При этом формируется маска символов М4=1610, которая записывается в выходной BQ буфер 9 (такт 9), а на такте 10 проводится запись упакованных данных (Q41=ACF4₁₆) в выходной BQ буфер 9 и выдача на внешние выходы Q устройства.

На тактах 9 и 10 на внешние входы данных 1 поступают пятая и шестая группы входных данных DG5 и DG6, содержащие только нулевые символы ID1, ID2, …, ID16 (IDN), для которых нулевые маски М5=0000 и М6=0000 записываются в выходной BQ буфер 9 на тактах 11 и 12 и выдача на внешние выходы Q устройства.

Выходной BQ буфер 9 может быть реализован как регистр или как буфер FIFO. Блок коммутаторов KD данных 7 может быть реализован на двухвходовых мультиплексорах.

Таким образом, для групп входных данных DG в канал передачи на внешние выходы Q устройства 14 последовательно поступают: N разрядов маски символов М и Z групп разрядов QZ, выбранных приоритетных данных из w ненулевых символов по k разрядов (фиг. 3), где Z - максимальное количество групп выходной последовательности ненулевых символов, причем Z=] N/w [(большее целое) когда количество V ненулевых символов больше (N-w+1).

Формирование значений N разрядной маски М для групп входных данных DG и групп по w ненулевых k разрядных символов, запись в выходной BQ буфер 9 и выдача на внешние Q выходы 14 устройства проводится за количество тактов Z+1.

В предлагаемом устройстве для хранения групп входных данных DG из N символов по k разрядов ID1, ID2, …, IDN, содержащих V ненулевых символов, упакованных на выходе по w символов из k разрядов, необходим объем памяти (Z+1)*(макс(Nмаски, w*k)бит. В устройстве прототипе для аналогичных групп входных данных DG из N символов по k разрядов необходим объем памяти Z*(Nмаски + w*k)бит. При группах входных данных DG из N=16 символов по k=4 разряда, выходных данных w=4 по k=4 разряда и количестве входных ненулевых символов 4<V≤8 в прототипе необходимо 64 бита, а в предлагаемом устройстве - 48 бит. При группах входных данных DG из N=32 символов по k=8 разрядов, w=4 по k=8 разрядов и количестве ненулевых символов 4<V≤8 в прототипе необходимо 128 бит, а в предлагаемом устройстве - 96 бит; а при количестве ненулевых символов 8<V≤12 в прототипе необходимо 192 бит, а в предлагаемом устройстве - 128 бит, при этом для передачи данных без упаковки необходимо N*k=256 бит.

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

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

Изобретение относится к области вычислительной техники и предназначено для использования в системах обработки информации. Технический результат заключается в повышении эффективности упаковки данных за счет сокращения необходимого объема памяти для хранения последовательности групп входных данных двоичных символов. Устройство содержит N входных символов ID1, ID2, …, IDN по k разрядов, соединенных с входным регистром данных 2, формирователь маски 3, содержащий группу из N элементов ИЛИ, коммутатор маски 4, регистр маски 5, многовыходной блок приоритета 6, содержащий w каскадов, блок коммутаторов данных 7, содержащий w коммутаторов 7₁, 7₂, …, 7_W, коммутатор маски-данных 8, выходной буфер 9, элемент ИЛИ-НЕ 10, синхронный D-триггер 11, внешний вход С синхронизации 12, внешний вход R синхронной установки в нулевое состояние 13, внешние выходы Q устройства 14, содержащие w символов по k разрядов, а также внутреннюю шину данных DD из N символов по k разрядов, внутреннюю N разрядную шину маски символов М, группу из w внутренних шин указателей старших символов U1, U2, …, Uw (где w - количество выходных символов), внутреннюю шину остаточной маски MS и флаг нулевых символов (флаг нуля) FZ. 4 ил.

Устройство для упаковки данных содержащее N входных символов ID1, ID2, …, IDN по k разрядов соединенных с входным регистром данных 2, формирователь маски 3, содержащий группу из N элементов ИЛИ, многовыходной блок приоритета 6, содержащий w каскадов, блок коммутаторов данных 7, содержащий w коммутаторов 7₁, 7₂, …, 7_W, выходной буфер 9, элемент ИЛИ-НЕ 10, внешний вход С синхронизации 12, внешний вход R синхронной установки в нулевое состояние 13, внешние выходы Q устройства 14, содержащие w символов по k разрядов, а также внутреннюю шину данных DD из N символов по k разрядов, внутреннюю N разрядную шину маски символов М, группу из w внутренних шин указателей старших символов U1, U2, …, Uw (где w - количество выходных символов), внутреннюю шину остаточной маски MS и флаг нулевых символов (флаг нуля) FZ, причем внешний вход R синхронной установки в нулевое состояние 13 соединен с входами R синхронной установки в нулевое состояние входного регистра 2 и выходного буфера 9, внешний вход С синхронизации 12 соединен с входами синхронизации С входного регистра 2 и выходного буфера 9, выходы входного регистра данных 2 соединены с внутренней шиной данных DD, из которой группами из k разрядов по символам соединены с соответствующими входами одноименных символам элементов группы из N элементов ИЛИ формирователя маски 3, в многовыходном блоке приоритета 6 выходы w каскадов являются соответствующими разрядами одноименных внутренних шин указателей старших символов из группы U1, U2, …, Uw, причем первая шина U1 имеет высший ранг приоритета, а старший разряд в каждой шине U1, U2, …, Uw имеет старший приоритет, а вторая группа выходов запроса в следующий каскад последнего w-го каскада многовыходного блока приоритета 6 является внутренней шиной остаточной маски MS, кроме того информационные входы всех w коммутаторов 7₁, 7₂, …, 7_W соединены с внутренней шиной данных DD, а управляющие входы каждого коммутатора 7₁, 7₂, …, 7_W соединены с разрядами соответствующей одноименной внутренней шины U1, U2, …, Uw указателей старших символов, а выход элемента ИЛИ-НЕ 10 соединен с входом разрешения работы СЕ входного регистра данных 2 и является флагом нулевых символов FZ, выходы 14 выходного буфера 9 являются внешними выходами Q устройства, отличающееся тем, что в него дополнительно введены коммутатор маски 4, регистр маски 5, коммутатор маски-данных 8 и синхронный D-триггер 11, а в выходной буфер 9 введены L разрядов (где L≥max (N, w*k)), причем внешний вход R синхронной установки в нулевое состояние 13 также соединен с входами R синхронной установки в нулевое состояние регистра маски 5 и синхронного D-триггера 11, а внешний вход С синхронизации 12 также соединен с входами синхронизации С регистра маски 5 и синхронного D-триггера 11, выходы элементов группы из N элементов ИЛИ формирователя маски 3 являются соответствующими разрядами внутренней шины маски символов М, которая соединена с соответствующими разрядами первых групп информационных входов коммутатора маски 4 и коммутатора маски-данных 8, кроме того, внутренняя шина остаточной маски MS соединена с соответствующими разрядами нулевой группы информационных входов коммутатора маски 4, выходы которого соединены с информационными входами регистра маски 5 и с входами элемента ИЛИ-НЕ 10, выход которого также соединен с информационным входом D-триггера, у которого выход ТСЕ соединен с управляющими входами коммутатора маски 4 и коммутатора маски-данных 8, кроме того, разряды выходов всех w коммутаторов 7₁, 7₂, …, 7_W соединены с соответствующими разрядами нулевой группы коммутатора маски-данных 8, выходы которого соединены с соответствующими информационными входами выходного буфера 9.