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

ОБЛАСТЬ ТЕХНИКИ

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

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

Известен способ сжатия данных (RU №2386210 С2, МПК Н03М 7/40, Н03М 7/46, заявлено 04.08.2006, опубликовано 10.04.2010, Бюл. №10), в котором сжатие данных осуществляется с помощью кодера. В первом блоке памяти кодера хранятся предварительно записанные кодовые комбинации (КК1) с числом разрядов 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₁)/2, а для восстановления потока данных выполняют обратные операции.

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

Известно устройство для сжатия данных (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 и временные затраты при формировании и передаче сжатых групп, когда сумма ненулевых символов в трех соседних группах менее двойной размерности групп w, а в двух соседних группах превышает размерность групп w, например, когда в соседних группах содержится два, три и два ненулевых символа при размерности групп w=4, то требуется передача трех групп сжатых символов.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип устройство для компрессии данных (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 входных символов D1, D2, …, DN по k разрядов соединенных с входным регистром данных 1, первую группу из N элементов ИЛИ 2₁, 2₂, …, 2_N, первую группу из N элементов И 3₁, 3₂, …, 3_N, многовыходной блок приоритета 4, элемент ИЛИ-НЕ 8, блок коммутаторов данных 11, выходной буфер 12, внешний вход С синхронизации 15, внешний вход CLR асинхронной установки в нулевое состояние 14, внешние выходы Q устройства 16, а также внутреннюю шину данных DD из N символов по k разрядов, группу из W внутренних шин указателей старших символов U1, U2, …, UW и внутреннюю N разрядную шину маски символов М,

причем блок коммутатора данных содержит 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), а также каждый i-й каскад 4_i содержит группу из (N+1-i) входов запроса в i-й каскад A_i1, A_i2, …, A_i(N+1-i), шину Ui из (N+1-i) разрядов выходов указателей старших символов i-го ранга (1-й ранг имеет высший приоритет, а старший разряд имеет старший приоритет) и группу из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад,

причем внешний вход CLR асинхронной установки в нулевое состояние 14 соединен с входами CLR асинхронной установки в нулевое состояние входного регистра 1 и выходного буфера 12,

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

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

причем разряды внутренней шины маски символов М также соединены с соответствующими входами запроса A₁₁, А₁₂, …, A_1N первого каскада 4₁, а в первых (W-1) каскадах 4₁, 4₂, …, 4_(W-1), кроме последнего W-го каскада 4_W, (N-i) выходов запроса в следующий каскад 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) из группы элементов ИЛИ, причем вторые входы (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-1) из группы элементов И соединены с выходами соответствующих (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-го каскада 4_W соединены с входами элемента ИЛИ-НЕ 8, выход которого является флагом нулевых символов FZ и соединен с входом разрешения работы СЕ входного регистра данных 1,

информационные входы всех W коммутаторов W, 11₁, 11₂, …, 11_W соединены с внутренней шиной данных DD, а управляющие входы каждого i-го коммутатора 11_i соединены с соответствующей одноименной i-ой внутренней шиной Ui указателей старших символов, выходы всех W коммутаторов 11₁, 11₂, …, 11_W соединены с соответствующими W группами входов из k разрядов, начиная со второй группы входов, выходного буфера 12, выходы Q которого являются внешними выходами устройства 16,

дополнительно введены синхронный D-триггер 9 с инверсным входом D, с инверсным выходом, с асинхронным CLR и синхронным R входами установки в нулевое состояние, (N-W) разрядный регистр 10 с инверсными входами D, с инверсными выходами, с асинхронным CLR и синхронным R входами установки в нулевое состояние, а также введена внутренняя N разрядная шина BR,

причем выходы запроса S_w1, S_w2, …, S_w(N-i) в следующий (i+1)-й каскад последнего W-го каскада 4_W также соединены с соответствующими одноименными инверсными D входами регистра 10, а на инверсный D вход синхронного D-триггера подано значение логического нуля «0»,

внешний вход CLR асинхронной установки в нулевое состояние 14 также соединен с входами CLR асинхронной установки в нулевое состояние синхронного D-триггера 9 и регистра 10,

внешний вход С синхронизации 15 соединен с входами синхронизации С синхронного D-триггера 9 и регистра 10,

выход элемента ИЛИ-НЕ 8 также соединен с синхронными входами R установки в нулевое состояние синхронного D-триггера 9 и регистра 10,

инверсные (N-W) выходов регистра 10 являются соответствующими одноименными (N-W) разрядами внутренней N разрядной шины BR, а инверсный выход синхронного D-триггера 9 соединен с (N-W+1)-го до N-го разрядами внутренней N разрядной шины BR, все разряды которой поразрядно соединены с первыми входами соответствующих одноименных элементов И первой группы из N элементов И 3₁, 3₂, …, 3_N.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

На фиг. 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) многовыходного блока приоритета,

BR - внутренняя N разрядная шина выходов триггера 9 и регистра 10,

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

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

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

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

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

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

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

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

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

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

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

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

RG - регистр,

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

Т - триггер,

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

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

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

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

3₁, 3₂, …, 3_N - первая группа из 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 - синхронный D-триггер с инверсным входом D, с инверсным выходом, с асинхронным CLR и синхронным R входами установки в нулевое состояние,

10 - (N-W) разрядный регистр с инверсными входами D, с инверсными выходами, с асинхронным CLR и синхронным R входами установки в нулевое состояние,

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, синхронный D-триггер 9, (N-W) разрядный регистр 10, блок коммутаторов данных 11, выходной буфер 12, а также введены внешний вход С синхронизации 15, внешний вход CLR асинхронной установки в нулевое состояние 14, внешние выходы Q устройства 16, а также внутреннюю шину данных DD из N символов по k разрядов, группу из W внутренних шин указателей старших символов U1, U2, …, UW, внутреннюю N разрядную шину маски символов М и внутреннюю N разрядную шину BR, причем в блок коммутатора данных введены 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.

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

Синхронный D-триггер 9 и (N-W) разрядный регистр 10 содержат инверсные входы D, инверсные выходы, асинхронные CLR и синхронные R входы установки в нулевое состояние.

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

Внешний вход С синхронизации 15 соединен с входами синхронизации С входного регистра 1, синхронного D-триггера 9, регистра 10 и входного регистра 1.

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

Каждый i-й каскад 4_i многовыходного блока приоритета содержит группу из (N+1-i) входов запроса в i-й каскад A_i1, A_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₁₁, А₁₂, …, 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)-го каскада А_(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) из группы элементов ИЛИ.

Причем вторые входы (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-м каскаде 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-го каскада 4_W соединены с входами элемента ИЛИ-НЕ 8, выход которого является флагом нулевых символов FZ и соединен с входом разрешения работы СЕ входного регистра данных 1, а также соединен с синхронными входами R установки в нулевое состояние синхронного D-триггера 9 и регистра 10. Причем выходы запроса S_w1, S_w2, …, S_w(N-i) в следующий (i+1)-й каскад последнего W-го каскада 4_W также соединены с соответствующими одноименными инверсными D входами регистра 10, а на инверсный D вход синхронного D-триггера подано значение логического нуля «0».

Инверсные (N-W) выходов регистра 10 являются соответствующими одноименными (N-W) разрядами внутренней N разрядной шины BR, а инверсный выход синхронного D-триггера 9 соединен с (N-W+1)-го до N-го разрядами внутренней N разрядной шины BR, все разряды которой поразрядно соединены с первыми входами соответствующих одноименных элементов И первой группы из 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 разрядов. Каждый разряд маски символов М принимает единичное значение, если соответствующий символ ненулевой, или нулевое значение, если соответствующий символ нулевой, а также в зависимости от значения разряда внутренней шины BR соответствующего одноименного символ. Перед началом работы во всех разрядах внутренней шины BR установлены единичные значения.

Далее по значениям разрядов маски символов М в 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 выполняется по тактовому сигналу С.

Одновременно на выходах S_W1, S_W2, …, S_W(N-i) запроса в следующий каскад W-го каскада UW формируются единичные значения, соответствующие ненулевым символам входных данных не выбранным и не переданным в выходной буфер 12 и нулевые значения для нулевых символов входных данных или уже выбранных и переданных в выходной буфер 12 ненулевых символов входных данных. Далее значения с выходов S_W1, S_W2, …, S_W(N-i) запроса в следующий каскад W-го каскада UW поступают на инверсные D входы регистра 10, которые по тактовому сигналу С записываются в регистр 10. Кроме того по тактовому сигналу С значение логического нуля «0» с инверсного D входа триггера 9 устанавливается на инверсном выходе триггера 9. Данное нулевое значение соответствует W старшим символам входных данных D1, D2, …, DN, которые передаются в выходной буфер на первом такте.

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

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

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

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

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

По тактовому сигналу С на внешнем входе 15 проводится запись первых входных данных D1, D2, …, DN во входной регистр 1, выходы которого образуют внутреннюю шину данных DD, к которой подключены по символам соответствующие входы одноименных элементов из первой группы элементов ИЛИ 2₁, 2₂, …, 2_N. Далее на выходах первой группы элементов ИЛИ 2₁, 2₂, …, 2_N будут установлены единичные значения для ненулевых символов, и так как во всех разрядах внутренней шины BR также установлены единичные значения, то на внутренней шине маски М сформируются единичные значения соответствующие всем ненулевым символам входного массива (на выходах первой группы из 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₁ (фиг. 1). В первом каскаде 4₁ на выходах группы элементов ИЛИ 5₁₁, 5₁₂, …, 5₁₄ (5_1(N-2)), объединенных в цепочку, входной код запросов преобразуется в код «00…011…1», где левая (старшая) единица соответствует высшему приоритету (старшему ненулевому символу). Далее на выходе только одного элемента запрета И с одним инверсным входом 6₁₁, 6₁₂, …, 6₁₅ (6_1(N-1)), на входы которого поданы значения «01», формируется единичное значение, указывающее на запрос с высшим приоритетом (старший ненулевой символ), а на остальных выходах будет установлено нулевое значение. Если установлен запрос с высшим приоритетом A₁₆ (A_1N), то единичное значение устанавливается на выходе старшего указателя U₁₆ (U_1N). Таким образом, на выходах U₁₁, U₁₂, …, U₁₆ будет установлено значение в единичном кодировании в виде унитарного кода «1 из N» соответствующее запросу с наивысшим приоритетом (первому старшему ненулевому символу).

Далее так как на первые входы элементов И 7₁₁, 7₁₂, …, 7₁₅ с выходов элементов ИЛИ 5₁₁, 5₁₂, …, 5₁₄ и старшего запроса A₁₆ поступает код «00…011…1», а на вторые входы входные сигналы запроса А₁₁, А₁₂, …, А₁₅, кроме старшего запроса 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.

Одновременно значения с выходов S_W1, S_W2, …, S_W(N-i) запроса в следующий каскад W-го каскада UW поступают на инверсные D входы регистра 10. Кроме того по тактовому сигналу С значение логического нуля «0» с инверсного D входа триггера 9 устанавливается на инверсном выходе триггера 9.

По следующему тактовому сигналу С проводится запись выбранных W ненулевых символов в выходной буфер 12 и выдача на внешние выходы Q устройства, а также запись в синхронный D-триггер 9 и регистр 10 и передача значений на внутреннюю шину BR. При этом на внутренней шине BR единичные значения будут соответствовать «новой» (следующей) маске не выбранных ненулевых символов входных данных.

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

Далее аналогично по каждому тактовому сигналу С проводится запись выбранных очередных W ненулевых символов в выходной буфер 12, а также изменение значений разрядов на внутренней шине BR.

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

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

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

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

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

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

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

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

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

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