Компрессионный накопитель данных и устройство для его осуществления

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

 

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

Область техники.

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

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

Уровень техники.

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

Способ сжатия данных (RU №2386210), в котором сжатие данных осуществляется с помощью кодера. В первом блоке памяти кодера хранятся предварительно записанные кодовые комбинации (КК₁) с числом разрядов n, где n=2, 3, 4, …, представляющие собой полный набор возможных входных кодовых комбинаций (КК). Во втором блоке памяти кодера хранятся предварительно записанные кодовые комбинации КК₂, однозначно соответствующие KK₁, с числом разрядов, меньшим или таким же, как в КК₁. Входной поток данных разделяют на КК с одинаковым числом разрядов n. КК последовательно вводят в кодер, идентифицируют путем сравнения с КК₁, отображают соответствующий выходной кодовой комбинацией КК₂. КК₂ представляют собой последовательность групп с одинаковым числом разрядов n в каждой. Совокупное число кодовых комбинаций КК₂-mⁿ, где m=2, 3, 4, …, n=1, 2, 3, …. Число последовательных групп КК определяют как m^n-1, m^n-2, …. Разрядность КК2 в группе выравнивают за счет добавления незначащего нуля перед кодовой комбинацией.

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

Так же, известен способ сжатия и восстановления данных без потерь (RU №2403677), в котором используется сжатие данных, ранее подвергнутых сжатию. В сжимаемом потоке данных считают количество нулей n₀ и количество единиц n₁, выбирают алгоритм присвоения неповторяющихся цифровых кодов всем возможным перестановкам с повторениями из по нулей и m единиц и нахождения соответствующей перестановки, которой присваивают цифровой код N_c, считают общее количество кодов n_c, определяют значения d₁=n₀+n₁-n_c и d₂=(n₀+n₁)/2, а для восстановления потока данных выполняют обратные операции.

Еще известно устройство (RU №153302), содержащее входной регистр, анализатор разрядов, блок управления ключами, блок ключей, ПЗУ, блок мультиплексоров, выходной регистр, а также тактовый генератор, делитель частоты, счетчик и выходной регистр со следующими соединениями: выход входного регистра 1-n соединен с входами анализатора разрядов и с блоком управления ключами, выходы 1-n² анализатора соединены с информационными входами блока ключей, а выходы 1-n² - с управляющими входами этого блока, выходы которого 1-n² соединены с входами ПЗУ, а выходы 1-2n ПЗУ соединены с информационными входами блока мультиплексора, выходы которого 1-n являются выходами маркера устройства; выходы 3-8 входного регистра соединены с выходным регистром, выходы которого являются выходами информационных разрядов устройства; выход тактового генератора через счетчик соединен с управляющими входами блока мультиплексоров, а через делитель частоты - с управляющими входами: через выход 1 входного регистра, через выход 2 с блоком управления ключами, а через выход 3 с выходным регистром.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является способ сжатия данных без потерь (RU №2450441), который заключается в том, что в память целевого устройства записывают промежуточные сжатые данные, извлекают данные из памяти целевого устройства для последующей распаковки, при этом данные принимают и отдают 128-битными блоками, используют 16 независимых блоков памяти для хранения кэшированных кодирующих структур размером 15-байтной длины и конфигурируют размер кэш-таблицы посредством задания числа ячеек числами, равными степени 2 в пределах от 16 до 4096, при этом выполняют следующие операции: предсказывают кодирующие структуры с использованием двух связных буферов упреждающей выборки для построения словаря; кодируют от двух до пятнадцати байт входного потока в один упакованный символ за один такт; используют количество упакованных байт в качестве обратной связи для логики, отвечающей за сдвиг входного потока; выбирают кодирующую структуру за один такт путем поиска кэшированной строки с наиболее длинной совпадающей с входной строкой последовательностью символов; упаковывают данные в 32-байтные группы, выровненные по два байта; упаковывают совпадающие строки в 2-байтный кодирующий символ, состоящий из длины строки, номера блока памяти и значения хэш-функции, определяющего адрес этой строки в блоке памяти.

Существенным общим недостатком описанных выше способов является низкий коэффициент сжатия данных.

Сущность изобретения

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

Величина коэффициента сжатия данных определяется как отношение исходного объема данных к полученному в результате компрессии объему и в компрессионном накопителе находится в прямой зависимости от количества циклов компрессии и исходного объема массива данных. При этом коэффициент сжатия составляет 10³ для массива данных длинной 1 Мбайт и растет вместе с увеличением массива входных данных при постоянном размере файла результата компрессии равном 961 бит.

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

Коммутатор (1) входных данных, предназначением которого является деление входного массива данных на два потока (нечетные и четные пакеты данных по 160 бит в каждом), которые поочередно записываются в регистры 1 и 2 (2 и 3) соответственно.

Регистры 1 и 2 (2, 3) представляют собой регистры сдвига на 160 разрядов. В регистрах пакеты данных, представленные последовательным кодом, преобразуется в параллельный 160 разрядный код. Далее преобразованные в параллельный 160 разрядный код данные поступает в ячейки арифметико-логического преобразователя 1 или 2 (5 и 6) в зависимости от номера пакета данных (нечетный, четный).

Блок управления (4) компрессионным накопителем данных представляет собой устройство управляющее управление основными операциями компрессора данных и реализующее соответствующий алгоритм работы компрессионного накопителя данных.

Арифметико-логический преобразователь (5, 6) представляет собой устройство, содержащее квадратную матрицу из 31х31 логических ячеек выходы которых объединяются 181 сумматором-шифратором строк, столбцов и диагоналей. Каждая ячейка содержит логическую схему фиг. 2 и имеет два входа и четыре выхода. Каждый из четырех выходов 961 ячейки соединен с соответствующими входом 181 сумматора-шифратора строк фиг. 3, столбцов фиг. 4, диагонали ЛП фиг. 5 и диагонали ПЛ фиг. 6 арифметико-логического преобразователя.

На вход ячеек арифметико-логического преобразователя данные поступают от регистра 1 или 2 и накопителя 2 или 1 в виде «0» и «1». Данные хранятся в триггерах, входящих в состав каждой ячейки фиг. 2. При этом данные записываются в строго определенные алгоритмом компрессии ячейки.

В логических схемах непосредственно сумматоров-шифраторов строк фиг. 7, столбцов, фиг. 8, диагонали ЛП фиг. 9 и диагонали ПЛ фиг. 10 производится подсчет количества ячеек арифметико-логического преобразователя, находящихся в состоянии «1». Подсчет «1» производится отдельно по каждой строке, столбцу и диагоналям ЛП и ПЛ. Полученная на выходе каждого сумматора-шифратора сумма «1» в виде двоичной пятиразрядной комбинации записывается в накопитель 1 (7) в соответствующие алгоритму компрессии ячейки.

Накопитель 1 и 2 (7 и 8) представляют собой элементы памяти, состоящие из 801 триггера с раздельными входами и выходами и предназначены для промежуточного хранения преобразованных в арифметико-логическом преобразователе данных.

Из накопителя 1 преобразованные данные переносятся в арифметико-логический преобразователь 2 (6) в ячейки с 001 по 801. Параллельно эти данные записываются в блок результата циклов компрессии (9) для формирования, в случае завершения работы компрессора накопителя данных, итогового файла результатов компрессии.

Одновременно с перезаписью итога цикла компрессии в арифметико-логический преобразователь 2 (6) в ячейки с 802 по 961 поступает новый пакет данных из регистра 2 (3). Записанные в ячейки арифметико-логического преобразователя 2 (6) данные в сумматорах-шифраторах строк, столбцов и диагоналей преобразуются в двоичные пятиразрядные комбинации, которые записываются в накопитель 2 (3) и параллельно в блок результата циклов компрессии (9) поверх результатов предыдущего цикла компрессии.

Далее процесс преобразования циклически повторяется с каждым новым пакетом данных.

Один цикл компрессии производится за 32 такта. При этом запись пакета данных в регистр 1 или 2 занимает 160 тактов и таким образом за время записи очередного пакета данных в регистр 1 или 2 может быть произведено до 4 циклов компрессии.

Алгоритм работы компрессора данных представлен на фиг. 11 и содержит в себе последовательность следующих действий:

1. Устанавливается исходное состояние компрессора накопителя данных - все элементы памяти, регистры, накопители, ячейки арифметико-логического преобразователя приводятся в состояние «0», счетчик времени устанавливается на «0».

2. Производится ввод массива данных.

3. Входной массив данных делится на пакеты данных длиной по 160 бит каждый. Одновременно производится подсчет количества пакетов.

4. Запускается счетчик времени работы компрессора данных.

5. Производится запись в входной сдвиговый регистр 1 первого нечетного пакета данных длиной 160 бит и преобразование его в параллельную кодовую последовательность.

6. Параллельная кодовая последовательность записывается в ячейки с 802 по 961 арифметико-логического преобразователя 1.

7. Преобразование в сумматорах-шифраторах арифметико-логического преобразователя 1 сумм «1» по строкам, столбцам, диагонали ЛП и диагонали ПЛ в двоичный пятиразрядный код и запись его в накопитель 1.

8. Перезапись преобразованных данных из накопителя 1 в арифметико-логический преобразователь 2 в ячейки с 001 по 801 и блок результата цикла компрессии.

9. Одновременно производится запись в входной сдвиговый регистр 2 четного пакета данных длиной 160 бит и преобразование его в параллельную кодовую последовательность и запись ее в ячейки с 802 по 961 арифметико-логического преобразователя 2.

10. Параллельное преобразование в сумматорах-шифраторах арифметико-логического преобразователя 2 сумм «1» по строкам, столбцам, диагонали ЛП и диагонали ПЛ в двоичный пятиразрядный код и запись его в накопитель 2.

11. Перезапись преобразованных данных из накопителя 2 в арифметико-логический преобразователь 1 в ячейки с 001 по 801 и блок результата цикла компрессии поверх записанных ранее данных.

12. Далее действия описанные в пунктах с 5 по 11 повторяются до момента завершения массива данных (или ручной подачи команды «стоп»).

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

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

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

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

Декомпрессия данных, сжатых в компрессоре накопителе, рассматривается в отдельной заявке на изобретение: «Декомпрессор данных и устройство для его осуществления».

Фиг. 1.	Структурная схема компрессионного накопителя данных.
Фиг. 2.	Логическая схема ячейки N арифметико-логического преобразователя.
Фиг. 3.	Схема (фрагмент) преобразователя суммы «1» по строкам.
Фиг. 4.	Схема (фрагмент) преобразователя суммы «1» по столбцам.
Фиг. 5.	Схема (фрагмент для диагонали 30) преобразователя суммы «1» по диагоналям ЛП.
Фиг. 6.	Схема (фрагмент для диагонали 30) преобразователя суммы «1» по диагоналям ПЛ.
Фиг. 7.	Логическая схема сумматора-шифратора строк (фрагмент схемы для одной строки) арифметико-логического преобразователя.
Фиг. 8.	Логическая схема сумматора-шифратора столбцов (фрагмент схемы для одного столбца) арифметико-логического преобразователя.
Фиг. 9.	Логическая схема сумматора-шифратора диагонали ЛП (фрагмент схемы для диагонали ЛП 31) арифметико-логического преобразователя.
Фиг. 10.	Логическая схема сумматора-шифратора диагонали ПЛ (фрагмент схемы для диагонали ПЛ 31) арифметико-логического преобразователя.
Фиг. 11.	Алгоритм работы компрессионного накопителя данных.

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