Результат интеллектуальной деятельности: УСТРОЙСТВО ДЛЯ КОМПРЕССИИ ДАННЫХ

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

Известен способ сжатия данных (RU №2386210 С2, МПК Н03М 7/40, Н03М 7/46, заявлено 04.08.2006, опубликовано 10.04.2010, Бюл. №10), в котором сжатие данных осуществляется с помощью кодера. В первом блоке памяти кодера хранятся предварительно записанные кодовые комбинации (КК₁) с числом разрядов n, где n=2, 3, 4, …, представляющие собой полный набор возможных входных кодовых комбинаций (КК). Во втором блоке памяти кодера хранятся предварительно записанные кодовые комбинации КК₂, однозначно соответствующие КК₁, с числом разрядов, меньшим или таким же, как в КК₁. Входной поток данных разделяют на КК с одинаковым числом разрядов n. КК последовательно вводят в кодер, идентифицируют путем сравнения с KK₁, отображают соответствующий выходной кодовой комбинацией КК₂. КК₂ представляют собой последовательность групп с одинаковым числом разрядов 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_с, определяют значения d₁=n₀+n₁-n_c и d₂=(n₀+n₁)/2, а для восстановления потока данных выполняют обратные операции.

Известно эффективное по использованию памяти адаптивное блочное кодирование (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, причем внешний вход CLR установки в нулевое состояние 19 соединен с входами установки в нулевое состояние входного регистра 1 и выходного буфера 15, а также входами CLR асинхронной установки в нулевое состояние всех триггеров 8₁, 8₂, …, 8_L-1, внешний вход синхронизации 18 соединен с входами синхронизации С триггеров 8₁, 8₂, …, 8_L-1, входного регистра 1 и выходного буфера 15, внешний вход EN разрешения работы 17 соединен с входами разрешения работы СЕ триггеров 8₁, 8₂, …, 8_L-1 и выходного буфера 15, причем выходы входного регистра данных 1 соединены с внутренней шиной данных DD, из которой группами по w символов из k разрядов соединены с соответствующими входами первых групп из w элементов ИЛИ 3 анализаторов символов 2₁, 2₂, …, 2_L, в каждом из которых выходы первых групп из w элементов ИЛИ 3 соединены со вторыми входами соответствующих первых групп из w элементов И 4, выходы которых являются внутренней шиной маски символов М и соединены с входами блока счета количества единиц 5, выходы которых являются выходами анализаторов символов 2₁, 2₂, …, 2_L, выход первого анализатора символов 2₁ соединен с первой группой входов первого сумматора 6₁, выходы анализаторов символов, начиная со второго 2₂ до последнего 2_L анализатора, соединены со вторыми группами входов соответствующих сумматоров 6₁, 6₂, …, 6_L-1, выходы сумматоров, начиная в первого 2₁ до предпоследнего 6_L-2 сумматора, соединены с первой группой входов последующего сумматора, начиная со второго 2₂ до последнего 2_L сумматора, а также выходы (L-1) сумматоров 6₁, 6₂, …, 6_L-1 соединены со вторыми группами входов соответствующих (L-1) схем сравнения 7₁, 7₂, …, 7_L-1, первые группы входов которых соединены между собой и подключены к внешним входам 16 задания количества символов w в группе, выходы схем сравнения, начиная с первой 7₁ до предпоследней 7_L-2 схемы сравнения, соединены с информационными входами D соответствующих триггеров, начиная со второго 8₂ до последнего 8_L-1 триггера, и с первыми входами соответствующих элементов И второй группы, начиная со второго 9₂ до предпоследнего 9_L-2 элемента И, а информационный вход D первого триггера 8₁ соединен с первым входом первого элемента 9₁ из второй группы элементов И и подключен к логической единице, инверсные выходы NT₁, NT₂, …, NT_L-1 триггеров 8₁, 8₂, …, 8_L-1 соединены с первыми входами первых групп из w элементов И 4 соответствующих (L-1) первых анализаторов символов 2₁, 2₂, …, 2_L-1 и вторыми входами соответствующих элементов И второй группы 9₁, 9₂, …, 9_L-1, первые входы первой группы из w элементов И 4 последнего анализатора символов 2_L соединены с выходом последней схемы сравнения 7_L-1, который также соединен с первым входом третьего элемента И 10 и со вторым входом четвертого элемента И 11, выход которого соединен с входом разрешения работы СЕ входного регистра 1, третьи входы всех элементов второй группы элементов И 9₁, 9₂, …, 9_L-1 соединены между собой, соединены со вторым входом третьего элемента И 10 и подключены к выходу третьего элемента ИЛИ 12, входы которого соединены со всеми N разрядами внутренней шины маски символов М, которые также соединены со второй группой входов выходного буфера 15 и с входами многовыходного блока приоритета 13, у которого w групп выходов соединены с управляющими входами блока коммутаторов данных 14, информационные входы которого соединены с внутренней шиной данных DD, а выходы блока коммутаторов данных 14 соединены с третьей группой входов выходного буфера 15, выходы второй группы элементов И 9₁, 9₂, …, 9_L-1 и выход третьего элемента И 10 являются внутренней шиной указателей групп символов U и соединены с первой группой входов выходного буфера 15, выходы Q которого являются внешними выходами устройства 20.

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

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

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

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

N входных символов D1, D2, …, DN по k разрядов соединенных с входным регистром данных 1, первую группу из N элементов ИЛИ 2₁, 2₂, …, 2_N, первую группу из N элементов И 3₁, 3₂, …, 3_N, группу из N синхронных D-триггеров 10₁, 10₂, …, 10_N с входом разрешения работы СЕ, асинхронным CLR и синхронным R входами установки в нулевое состояние, многовыходной блок приоритета 4, блок коммутаторов данных 11, выходной буфер 12, внешний вход С синхронизации 15, внешний вход CLR асинхронной установки в нулевое состояние 14, внешние выходы Q устройства 16, а также внутреннюю шину данных DD из N символов по k разрядов и внутреннюю N разрядную шину маски символов М,

причем внешний вход 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,

дополнительно введены элемент ИЛИ-НЕ 8, вторая группа из (N-1) элементов ИЛИ 9₁, 9₂, …, 9_(N-1), а также введены внутренняя N разрядная шина выходов триггеров Т и группа из W внутренних шин указателей старших символов U1, U2, …, UW, в блок коммутатора данных введены W коммутаторов 11₁, 11₂, …, 11_W, а в многовыходной блок приоритета введены W каскадов 4₁, 4₂, …, 4_W, причем каждый i-й каскад 4_i (i=1, 2, …, W, где W количество выходных символов) содержит группу из (N-1-i) элементов ИЛИ 5_i1, 5_i2, …, 5_i(N-i-1), группу из (N-i) элементов запрета И с одним инверсным входом 6_i1, 6_i2, 6_i(N-1) и группу из (N-i) элементов И 7_i1, 7_i2, …, 7_i(N-i), а также каждый i-й каскад 4_i содержит группу из (N+1-i) входов запроса в i-й каскад А_i1, А_i2, …, A_i(N+1-i), шину Ui из (N+1-i) разрядов выходов указателей старших символов i-го ранга (1-й ранг имеет высший приоритет, а старший разряд имеет старший приоритет) и группу из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад,

причем разряды внутренней шины маски символов М соединены с соответствующими входами запроса A₁₁, А₁₂, …, А_1N первого каскада 4₁, а в первых (W-1) каскадах 4₁, 4₂, …, 4_(W-1), кроме последнего W-го каскада 4_W, (N-i) выходов запроса в следующий (i+1)-й каскад S_i1, S_i2, …, S_i(N-i) соединены с соответствующими (N-i) входами запроса следующего (i+1)-го каскада A_(i+1)1, A_(i+1)2, …, A_(i+1)(N-i),

в многовыходном блоке приоритета 4 в каждом i-м каскаде 4_i первые (N-i) входов A_i1, A_i2, …, A_i(N-i) из группы входов запроса, кроме последнего входа запроса A_i(N-i+1), соединены с первыми прямыми входами соответствующих элементов 6_i1, 6_i2, …, 6_i(N-i) из группы элементов запрета И с одним инверсным входом, выходы всех элементов группы из (N-i-1) элементов ИЛИ 5_i1, 5_i2, …, 5_i(N-i-1) соединены со вторыми инверсными входами соответствующих первых (N-i-1) элементов 6_i1, 6_i2, …, 6_i(N-i-1) группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 6_i(N-i), у которого второй инверсный вход соединен с последним (N-i+1) входом A_i(N-i+1) группы запроса i-го каскада и вторым входом последнего элемента 5_i(N-i-1) из группы элементов ИЛИ, кроме того в каждом i-м каскаде 4_i первые входы (N-i-1) элементов 5_i1, 5_i2, …, 5_i(N-i-1) из группы элементов ИЛИ соединены с соответствующими (N-i-1) входами A_i2, A_i2, …, A_i(N-i) запроса в i-й каскад, начиная со второго входа запроса, кроме последнего входа запроса A_i(N-i+1), а вторые входы первых (N-i-2) элементов 5_i1, 5_i2, …, 5_i(N-i-2) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 5_i2, 5_i3, …, 5_i(N-i-2) из группы элементов ИЛИ, причем в первых (W-1) каскадах, кроме последнего W-го каскада, вторые входы (N-i) элементов 7_i1, 7_i2, …, 7_i(N-i) из группы элементов И соединены с соответствующими первыми (N-i) входами запроса в i-й каскад А_i1, А_i2, …, А_i(N-i), кроме последнего входа запроса A_i(N-i+1), первые входы первых (N-i-1) элементов 7_i1, 7_i2, …, 7_i(N-i) из группы элементов И соединены с выходами соответствующих (N-i-1) элементов 5_i1, 5_i2, …, 5_i(N-i-1) из группы элементов ИЛИ, первый вход последнего элемента 7_i(N-i) из группы элементов И соединен с последним входом запроса A_i(N-i+1), а выходы (N-i) элементов 7_i1, 7_i2, …, 7_i(N-i) из группы элементов И являются группой из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад, кроме того, в каждом i-м каскаде 4_i выходы (N-i) элементов 6_i1, 6_i2, …, 6_i(N-i) из группы элементов запрета И с одним инверсным входом являются первыми (N-i) разрядами соответствующей внутренней шины i-го ранга U_i1, U_i2, …, U_i(N-i) из W внутренних шин указателей старших символов, а последний (N-i+1) разряд U_i(N+1-i) соединен с последним (N-i+1) входом запроса в i-й каскад A_i(N-i+1),

выходы запроса S_w1, S_w2, …, S_w(N-i) в следующий (i+1)-й каскад последнего W-го каскада 4w соединены с входами элемента ИЛИ-НЕ 8, выход которого соединен с синхронными входами установки в нулевое состояние 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.

На фиг. 1 представлена схема предлагаемого устройства для компрессии данных при N=6 входных символов по k разрядов и количестве выходных символов W=3 по k разрядов. На фиг. 2 приведены форматы входных данных и внутренней шины маски М. На фиг. 3 приведен формат выходных данных.

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

A_i1, A_i2, …, A_i(N+1-i) - группа из (N+1-i) входов запроса в i-й каскад (i=1, 2, …, W) многовыходного блока приоритета,

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

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

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

D1, D2, …, D6 (DN) - N входных символов по k разрядов,

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

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

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

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

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

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

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

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

S_i1, S_i2, …, S_i(N-i) - группа из (N-i) выходов запроса в следующий (i+1)-й каскад,

Т - внутренняя N разрядная шина выходов триггеров,

U1, U2, …, UW - группа из W внутренних шин указателей старших символов по (N-i+1) разрядов,

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

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

2₁, 2₂, …, 2_N - первая группа из N элементов ИЛИ,

3₁, 3₂, …, 3_B - первая группа из N элементов И,

4₁, 4₂, …, 4_W - W каскадов многовыходного блока приоритета,

5_i1, 5_i2, …, 5_i(N-i-1) - группа из (N-i-1) элементов ИЛИ каждого i-го каскада многовыходного блока приоритета,

6_i1, 6_i2, …, 6_i(N-i) - группа из (N-i) элементов запрета И с одним инверсным входом каждого i-го каскада многовыходного блока приоритета,

7_i1, 7_i2, …, 7_i(N-i) - группа из (N-i) элементов И каждого i-го каскада многовыходного блока приоритета,

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

9_i1, 9_i2, …, 5_(N-1) - вторая группа из (N-1) элементов ИЛИ,

10₁, 10₂, …, 10_N - группа из N синхронных D-триггеров с входом разрешения работы СЕ, асинхронным и синхронным входами установки в нулевое состояние,

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

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

13 - внешние входы данных D1, D2, …, D6 (DN),

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

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

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

Устройство для компрессии данных содержит 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, причем каждый i-й каскад 4_i (i=1, 2, …, W, где W количество выходных символов), содержит группу из (N-1-i) элементов ИЛИ 5_i1, 5_i2, …, 5_i(N-i-1), группу из (N-i) элементов запрета И с одним инверсным входом 6_i1, 6_i2, …, 6_i(N-i) и группу из (N-i) элементов И 7_i1, 7_i2, …, 7_i(N-i).

Входной регистр данных 1 содержит N*k информационных разрядов и предназначен для хранения текущего массива N входных символов D1, D2, DN по k разрядов, а также содержит вход разрешения записи СЕ, вход синхронизации С и вход установки в нулевое состояние CLR. Выходы входного регистра данных 1 являются внутренней шиной данных DD.

В группе из N синхронных D-триггерах 10₁, 10₂, …, 10_N каждый триггер также содержит вход синхронизации С, вход разрешения работы СЕ, асинхронный CLR и синхронный R входы установки в нулевое состояние.

Выходной буфер 12 содержит (W+1) группу информационных входов, вход синхронизации С и вход установки в нулевое состояние CLR.

Внешний вход CLR установки в нулевое состояние 14 соединен с входами установки в нулевое состояние входного регистра 1 и выходного буфера 12, а также входами CLR асинхронной установки в нулевое состояние всех триггеров 10₁, 10₂, …, 10.

Внешний вход С синхронизации 15 соединен с входами синхронизации С всех триггеров 10₁, 10₂, …, 10, входного регистра 1 и выходного буфера 12.

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

Каждый i-й каскад 4_i многовыходного блока приоритета содержит группу из (N+1-i) входов запроса в i-й каскад A_i1, А_i2, …, A_i(N+1-i), шину Ui из (N+1-i) разрядов выходов указателей старших символов i-го ранга (1-й ранг имеет высший приоритет, а старший разряд имеет старший приоритет) и группу из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад.

Разряды внутренней шины маски символов М соединены с соответствующими входами запроса A₁₁, А₁₂, …, А_1N первого каскада 4₁, а в первых (W-1) каскадах 4₁, 4₂, …, 4_(W-1), кроме последнего W-го каскада 4_W, (N-i) выходов запроса в следующий (i+1)-й каскад S_i1, S_i2, …, S_i(N-1) соединены с соответствующими (N-i) входами запроса следующего (i+1)-го каскада A_(i+1)1, A_(i+1)2, …, A_(i+1)(N-i).

В многовыходном блоке приоритета 4 в каждом i-м каскаде 4_i первые (N-i) входов А_i1, A_i2, …, A_i(N-i) из группы входов запроса, кроме последнего входа запроса A_i(N-i+1), соединены с первыми прямыми входами соответствующих элементов 6_i1, 6_i2, …, 6_i(N-i) из группы элементов запрета И с одним инверсным входом. Выходы всех элементов группы из (N-i-1) элементов ИЛИ 5_i1, 5_i2, …, 5_i(N-i-1) соединены со вторыми инверсными входами соответствующих первых (N-i-1) элементов 6_i1, 6_i2, …, 6_i(N-i-1) группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 6_i(N-i), у которого второй инверсный вход соединен с последним (N-i+1) входом A_i(N-i+1) группы запроса i-го каскада и вторым входом последнего элемента 5_i(N-i-1) из группы элементов ИЛИ. Кроме того, в каждом i-м каскаде 4_i первые входы (N-i-1) элементов 5_i1, 5_i2, …, 5_i(N-i-1) из группы элементов ИЛИ соединены с соответствующими (N-i-1) входами A_i1, A_i2, …, A_i(N-i) запроса в i-й каскад, начиная со второго входа запроса, кроме последнего входа запроса A_i(N-i+1), а вторые входы первых (N-i-2) элементов 5_i1, 5_i2, …, 5_i(N-i-2) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 5_i2, 5_i3, …, 5_i(N-i-2) из группы элементов ИЛИ. Причем в первых (W-1) каскадах, кроме последнего W-го каскада, вторые входы (N-i) элементов 7_i1, 7_i2, …, 7_i(N-i) из группы элементов И соединены с соответствующими первыми (N-i) входами запроса в i-й каскад A_i1, A_i2, …, A_i(N-i), кроме последнего входа запроса A_i(N-i+1), первые входы первых (N-i-1) элементов 7_i1, 7_i2, …, 7_i(N-i), из группы элементов И соединены с выходами соответствующих (N-i-1) элементов 5_i1, 5_i2, …, 5_i(N-i-1) из группы элементов ИЛИ, первый вход последнего элемента 7_i(N-i) из группы элементов И соединен с последним входом запроса A_i(N-i+1). Выходы (N-i) элементов 7_i1, 7_i2, …, 7_i(N-i) из группы элементов И являются группой из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад. Кроме того, в каждом i-м каскаде 4i выходы (N-i) элементов 6_i1, 6_i2, …, 6_i(N-i) из группы элементов запрета И с одним инверсным входом являются первыми (N-i) разрядами соответствующей внутренней шины i-го ранга U_i1, U_i2, …, U_i(N-i) из W внутренних шин указателей старших символов, а последний (N-i+1) разряд U_i(N+1-i) соединен с последним (N-i+1) входом запроса в i-й каскад A_i(N-i+1).

Выходы запроса S_w1, S_w2, …, S_w(N-i) в следующий (i+1)-й каскад последнего W-го каскада 4_W соединены с входами элемента ИЛИ-НЕ 8, выход которого соединен с синхронными входами установки в нулевое состояние R всех триггеров 10₁, 10₂, …, 10_N и входом разрешения работы СЕ входного регистра данных 1.

Причем соответствующие одноименные разряды группы из W внутренних шин указателей старших символов U1, U2, …, UW соединены с соответствующими входами одноименных элементов из второй группы из (N-1) элементов ИЛИ 9₁, 9₂, …, 9_i(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.

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

Входной массив данных D1, D2, …, DN содержит N символов по k разрядов (фиг. 2). Определяют ненулевые символы (в первой группе из N элементов ИЛИ 2₁, 2₂, …, 2_N) и формируют маску символов М из N разрядов. Каждый разряд маски символов М принимает единичное значение, если соответствующий символ ненулевой, или нулевое значение, если соответствующий символ нулевой, а также в зависимости от состояния соответствующего одноименного символу D-триггера из группы 10₁, 10₂, …, 10_N (в первой группе из N элементов И 3₁, 3₂, …, 3_N).

Далее по значениям разрядов маски символов М в W каскадах 4₁, 4₂, …, 4_W многовыходного блока приоритета формируются W групп соответствующего ранга приоритета (группа с меньшим номером имеет высший приоритет, а старший разряд в группе имеет старший приоритет), которые поступают на разряды группы из W внутренних шин указателей старших символов U1, U2, …, UW по (N-i+1) разрядов. На каждой шине Ui указателей старших символов устанавливается значение в единичном кодировании в коде «1 из N». В соответствии с приоритетом W коммутаторов блока коммутаторов данных 11₁, 11₂, …, 11_W передают не более W соответствующих старших ненулевых символов входных данных D1, D2, …, DN на соответствующие группы входов выходного буфера 12 (ненулевые символы поступают в обратном порядке - старший ненулевой символ поступает на младшую группу входов), на первую группу входов которого поступают также значения маски символов М (фиг. 3). Запись в выходной буфер 12 выполняется по тактовому сигналу С.

Одновременно, в соответствии с единичными значениями разрядов внутренних шин U1, U2, …, UW указателей старших символов, на выходах второй группы из (N-1) элементов ИЛИ 9₁, 9₂, …, 9_(N-1) формируются единичные значения, соответствующие выбранным ненулевым символам, которые поступают на входы разрешения СЕ синхронных D-триггеров 10₁, 10₂, …, 10_N, которые по тактовому сигналу С переключаются в единичное состояние, при единичном значении СЕ=1, или сохраняют состояние при нулевом значении СЕ=0. При этом по нулевым значениям на выходах триггеров 10₁, 10₂, …, 10_N на следующем шаге блокируются выбранные и переданные символы - обнуляются соответствующие разряды в маске символов М (в первой группе из N элементов И 3₁, 3₂, …, 3_N) и проводится выборка следующих W ненулевых символов для передачи в выходной буфер 12.

Если на выходах S_W1, S_W2, …, S_W(N-i) запроса в следующий каскад W-го каскада UW будут установлены нулевые значения, что соответствует отсутствию не выбранных ненулевых символов, то на выходе элемента ИЛИ-НЕ 8 будет сформировано единичное значение флага нуля (флаг нулевых символов) FZ=1, по которому по тактовому сигналу С проводится синхронная установка в нулевое состояние всех триггеров 10₁, 10₂, …, 10_N и разрешается прием следующего массива входных данных D1, D2, …, DN во входной регистр 1.

При всех нулевых символах входных данных D1, D2, …, DN в устройстве также на всех разрядах указателей старших символов U1, U2, …, UW формируются нулевые значения, формируется флаг нуля FZ=1 на выходе элемента ИЛИ-НЕ 8 и также разрешается прием следующего массива входных данных D1, D2, …, DN во входной регистр 1.

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

При подаче единичного сигнала CLR на вход начальной установки устройства 14 в нулевое состояние устанавливаются входной регистр 1, группа из D-триггеров 10₁, 10₂, …, 10_N и выходной буфер 12. При этом на инверсных выходах триггеров 10₁, 10₂, …, 10_N будут установлены единичные значения, на выходах регистра 1 будут установлены нулевые значения, на всех разрядах внутренней шины маски символов М и на всех разрядах указателей старших символов U1, U2, …, UW также будут сформированы нулевые значения, а флаг нуля примет единичное значение FZ=1.

По тактовому сигналу С на внешнем входе 15 проводится запись первых входных данных D1, D2, …, DN в регистр 1, выходы которого образуют внутреннюю шину данных DD, к которой подключены по символам соответствующие входы первой группы элементов ИЛИ 2₁, 2₂, …, 2_N. Далее на выходах первой группы элементов ИЛИ 2₁, 2₂, …, 2_N будут установлены единичные значения для ненулевых символов, и так как инверсных выходах триггеров 10₁, 10₂, …, 10_N также установлены единичные значения, то на внутренней шине маски М сформируются единичные значения соответствующие всем ненулевым символам входного массива (на выходах первой группы из N элементов И 3₁, 3₂, …, 3_N).

Сигналы с выходов внутренней шины маски М являются входами запросов для многовыходного блока приоритета 4, который позволяет определить среди N входов запроса не только сигнал с наивысшим приоритетом, но также определить сигналы со вторым, третьим, W-м по старшинству приоритетами.

В соответствии со значениями N разрядов маски символов М в W каскадах 4₁, 4₂, …, 4_W многовыходного блока приоритета формируются W групп соответствующего ранга приоритета на W внутренних шинах указателей старших символов U1, U2, …, UW по (N-i+1) разрядов в каждой i-ой шине Ui. При этом в каждой шине Ui будет установлено значение в единичном кодировании в виде унитарного кода «1 из N» в соответствии с приоритетом ненулевых символов, начиная со старших символов. Выходы группы с меньшим номером имеют высший приоритет, а старший разряд в группе имеет старший приоритет.

Сигналы с внутренней шины маски символов М поступают на входы запроса A₁₁, А₁₂, …, A₁₆ (А_1N) первого каскада 4₁. В первом каскаде 4₁ на выходах группы элементов ИЛИ 5₁₁, 5₁₂, …, 5₁₄ (5_1(N-2)), объединенных в цепочку, входной код запросов преобразуется в код «00…011..1», где левая (старшая) единица соответствует высшему приоритету (старшему ненулевому символу). Далее на выходе только одного элемента запрета И с одним инверсным входом 6₁₁, 6₁₂, …, 6₁₅ (6_1(N-1)), на входы которого поданы значения «01», формируется единичное значение, указывающее на запрос с высшим приоритетом (старший ненулевой символ), а на остальных выходах будет установлено нулевое значение. Если установлен запрос с высшим приоритетом A₁₆ (А_1N), то единичное значение устанавливается на выходе старшего указателя U₁₆ (U_1N). Таким образом, на выходах U₁₁, U₁₂, …, U₁₆ будет установлено значение в единичном кодировании в виде унитарного кода «1 из N» соответствующее запросу с наивысшим приоритетом (первому старшему ненулевому символу).

Далее так как на первые входы элементов И 7₁₁, 7₁₂, …, 7₁₅ с выходов элементов ИЛИ 5₁₁, 5₁₂, …, 5₁₄ и старшего запроса A₁₆ поступает код «00…011..1», а на вторые входы входные сигналы запроса A₁₁, А₁₂, …, А₁₅, кроме старшего запроса A₁₆, то выходах S₁₁, S₁₂, …, S₁₅ запроса в следующий второй каскад 4₂ будут установлены запросы с «исключенным» запросом с высшим приоритетом. Далее сигналы запросов S₁₁, S₁₂, …, S₁₅ поступают на входы запроса А₂₁, А₂₂, …, А₂₅ второго каскада 4₂, в котором аналогично на выходах U₂₁, U₂₂, …, U₂₅ будет установлено значение в единичном кодировании в виде унитарного кода «1 из N» соответствующее запросу со вторым приоритетом (второму старшему ненулевому символу). Затем формируется результат в виде унитарного кода «1 из N» в третьем, четвертом, W-м каскадах, соответствующих следующим ненулевым символам в порядке старшинства.

Далее в соответствии с приоритетами на W внутренних шинах U1, U2, …, UW указателей старших символов W коммутаторов блока коммутаторов данных 11₁, 11₂, …, 11_W выбирают до W ненулевых символов по k разрядов и передают их на входы выходного буфера 12.

Одновременно на выходах второй группы из (N-1) элементов ИЛИ 9₁, 9₂, …, 9_(N-1) формируются единичные значения соответствующие выбранным ненулевым символам, которые поступают на входы разрешения СЕ синхронных D-триггеров 10₁, 10₂, …, 10_N.

По следующему тактовому сигналу С проводится запись выбранных W ненулевых символов в выходной буфер 12 и выдача на внешние выходы Q устройства, а также изменение состояния D-триггеров 10₁, 10₂, …, 10_N на единичное значение при соответствующем единичном сигнале разрешения работы СЕ=1.

Далее по нулевым значениям на выходах триггеров 10₁, 10₂, …, 10_N блокируются выбранные и переданные символы - обнуляются соответствующие разряды в маске символов М (в первой группе из N элементов И 3₁, 3₂, …, 3_N) и аналогично проводится выборка следующих W ненулевых символов для передачи в выходной буфер 12 и выдача на внешние выходы Q устройства.

Далее аналогично по каждому тактовому сигналу С проводится запись выбранных очередных W ненулевых символов в выходной буфер 12, а также изменение состояния D-тригтеров 10₁, 10₂, …, 10_N на единичное значение при соответствующем единичном сигнале разрешения работы СЕ=1.

Одновременно в зависимости от наличия не выбранных ненулевых символов или их отсутствия формируется флаг нуля соответственно FZ=0 или FZ=1 (на выходе элемента ИЛИ-НЕ 8). При отсутствии не выбранных ненулевых символов и сформированном единичном значении флага нуля FZ=1 проводится синхронная установка в нулевое состояние всех триггеров 10₁, 10₂, …, 10_N и по следующему тактовому сигналу С проводится запись следующего «нового» массива входных данных D1, D2, …, DN во входной регистр 1.

Далее проводится формирование групп по W ненулевых символов по k разрядов в соответствии с рассмотренным выше алгоритмом работы для «нового» массива данных.

Формирование групп по W ненулевых k разрядных символов и соответствующих значений N разрядной маски М, запись в выходной буфер 12 и выдача на внешние выходы Q устройства проводится за количество тактов кратное количеству W ненулевых символов в массиве входных данных.

Таким образом, в канал передачи на внешние выходы устройства 16 поступают:

- N разрядов маски символов QM,

- разряды данных выбранных приоритетных W ненулевых символов по k разрядов QD.

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

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

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

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