СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ДАННЫХ БЕЗ ПОТЕРЬ Российский патент 2010 года по МПК H03M7/30 H03M7/42 

Описание патента на изобретение RU2382492C1

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

Основы теории информации были заложены К.Шенноном в 1948 году в своей пионерской работе по теории информации (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004, стр.25), в которой он ввел понятие энтропии источника. Фундаментально значение этой величины состоит в том, что она задает нижнюю границу возможного сжатия (Д.Сэломон «Сжатие данных, изображений и звука», Москва, Техносфера, 2004, стр.8). К этой границе можно приближаться сколь угодно близко с помощью подходящего способа кодирования источника. Под энтропией символа а, имеющего вероятность Р, подразумевается количество информации, содержащейся в а, которая равна -P·log2(P). (Д.Сэломон «Сжатие данных, изображений и звука», Москва, Техносфера, 2004, стр.25).

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

Известен способ сжатия и восстановления данных без потерь с использованием кодов переменной длины (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004 г., стр.26), включающий, выбор алфавита - набора символов от a1 до an, сбор статистики - вероятностей каждого символа алфавита в сжимаемом потоке данных, составление кодов переменной длины и замену исходных символов кодами переменной длины. Для восстановления первоначального потока данных в соответствии с построенными кодами переменной длины заменяют коды переменной длины на исходные символы алфавита.

Недостатком известного способа является:

- низкая скорость операций сжатия и восстановления;

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

Известен также способ сжатия и восстановления данных без потерь методом Хаффмана (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004 г., стр.30; М.Вернер "Основы кодирования", Москва, Техносфера, 2004 г., стр.29), включающий для выбранного алфавита

- составление списка символов алфавита в порядке убывания их вероятностей;

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

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

Для восстановления необходимо в соответствии с построенными кодами Хаффмана преобразовать сжатый поток к первоначальному виду (Д.Сэломон "Сжатие данных, изображений и звука", Москва, Техносфера, 2004 г., стр.38.; М.Вернер "Основы кодирования", Москва, Техносфера, 2004 г., стр.29). Для этого начинают с исходного узла построенного кодового дерева и двигаются в зависимости от считанного символа вверх или вниз до конечного узла.

Недостатками известного способа являются:

- низкая скорость операций сжатия и восстановления данных;

- максимальное сжатие достигается, если вероятности символов равны отрицательным степеням числа 2;

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

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

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

Способ осуществляют следующим образом.

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

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

Пример конкретного выполнения способа.

Выбирают равные длины отрезков, на которые затем разбивают поток сжимаемых данных. Обозначают эту длину через n бит, например 4 бит (см. табл.1). Затем подсчитывают вероятности каждого из чисел длины 4 бит во всем сжимаемом потоке данных (табл.1, графа 3). После этого числа объединяют в префиксные группы и обозначают эти группы префиксными кодами (см. табл.2). В первую группу помещают числа с наибольшими вероятностями и присваивают данной префиксной группе самый короткий префиксный код. Так в первую префиксную группу объединены числа 0001, 0010, 0100, 1000 и этой группе присвоен префиксный код 0. В следующую группу также помещают числа с наибольшими вероятностями из тех чисел, которые не были помещены в предыдущую группу. Это числа 0111, 1011, 1101, 1110. Этой группе присваивают префиксный код 10. Всего префиксных групп сформировано 4. После чего в каждой префиксной группе все числа нумеруют по порядку начиная с нуля и получают порядковый номер числа в префиксной группе (таблица 2, графа 4).

Таблица 1 Все числа от 0 до 24-1 (в двоичном виде) Количество чисел в сжимаемой последовательности Вероятности чисел в сжимаемом потоке данных 1 2 3 0000 100 100/3200 0001 300 300/3200 0010 300 300/3200 0011 100 100/3200 0100 300 300/3200 0101 100 100/3200 0110 100 100/3200 0111 300 300/3200 1000 300 300/3200 1001 100 100/3200 1010 100 100/3200 1011 300 300/3200 1100 100 100/3200 1101 300 300/3200 1110 300 300/3200 1111 100 100/3200

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

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

Таблица 2 Все числа от 0 до 24-1 (в двоичном виде) Количество в сжимаемом потоке данных Префиксные коды групп Порядковый номер числа в префиксной группе 1 2 3 4 0000 100 111 00 0001 300 0 00 0010 300 0 01 0011 100 110 00 0100 300 0 10 0101 100 110 01 0110 100 110 10 0111 300 10 00 1000 300 0 11 1001 100 110 11 1010 100 111 01 1011 300 10 01 1100 100 111 10 1101 300 10 10 1110 300 10 11 1111 100 111 11

Таким образом, для записи любого числа, которое отнесено к первой префиксной группе потребуется 3 бит. При этом выигрыш от такого преобразования составит один бит на каждое число длиной 4 бит.

Все числа от нуля до 24-1, префиксные коды, порядковые номера чисел в префиксных группах заносят в таблицу 3 и сохраняют ее.

Таблица 3 Все числа от 0 до 24-1 (в двоичном виде) Префиксные коды групп Порядковый номер числа в префиксной группе 1 2 3 0000 111 00 0001 0 00 0010 0 01 0011 110 00 0100 0 10 0101 110 01 0110 110 10 0111 10 00 1000 0 11 1001 110 11 1010 111 01 1011 10 01 1100 111 10 1101 10 10 1110 10 11 1111 111 11

Все вышеперечисленные действия предшествуют преобразованию потока данных.

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

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

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

Размер всего потока данных до сжатия составлял: 4 бит*3200=12800 бит.

Размер данных после сжатия составил 12400 бит.

Заявляемый способ позволяет достичь

- более высокого коэффициента сжатия данных по сравнению с методом сжатия данных Хаффмана для данных с высокой энтропией;

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

Таблица 4 Все числа от 0 до 24-1 (в двоичном виде) Количество чисел в сжимаемом потоке (в десятичном виде) Запись числа после преобразования (код группы и порядковый номер в группе) Количество бит, которое занимает сжатое число (в десятичном виде) Количество бит, необходимое для сжатия всех чисел: графу 2×графу 4 (в десятичном виде) 1 2 3 4 5 0000 100 111 00 5 500 0001 300 0 00 3 900 0010 300 0 01 3 900 0011 100 110 00 5 500 0100 300 0 10 3 900 0101 100 110 01 5 500 0110 100 110 10 5 500 0111 300 10 00 4 1200 1000 300 0 11 3 900 1001 100 110 11 5 500 1010 100 111 01 5 500 1011 300 10 01 4 1200 1100 100 111 10 5 500 1101 300 10 10 4 1200 1110 300 10 11 4 1200 1111 100 111 11 5 500 Итого: 3200 12400

- заявляемый способ может быть использован для отрезков различной длины;

- способ прост в реализации.

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

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

Похожие патенты RU2382492C1

название год авторы номер документа
СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ДАННЫХ БЕЗ ПОТЕРЬ 2009
  • Муллов Сергей Борисович
RU2403677C1
СПОСОБ КОМПРЕССИИ-ДЕКОМПРЕССИИ ДАННЫХ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ 2011
  • Леонович Георгий Иванович
  • Токмак Петр Львович
  • Гончаров Антон Константинович
  • Мелентьев Владимир Сергеевич
RU2488960C2
СПОСОБ КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ, УСТРОЙСТВО КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ, СПОСОБ ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ И УСТРОЙСТВО ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ 2012
  • Сасаи Хисао
  • Терада Кенго
  • Ниси Такахиро
  • Сибахара Йоудзи
  • Сугио Тосиясу
  • Таникава Киоко
  • Мацунобу Тору
RU2714377C2
СПОСОБ КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ, УСТРОЙСТВО КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ, СПОСОБ ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ И УСТРОЙСТВО ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ 2012
  • Сасаи Хисао
  • Ниси Такахиро
  • Сибахара Йоудзи
  • Сугио Тосиясу
  • Таникава Киоко
  • Мацунобу Тору
  • Терада Кенго
RU2610249C2
ДЕКОДЕР С ПОВЫШЕННОЙ КОРРЕКТИРУЮЩЕЙ СПОСОБНОСТЬЮ 2010
  • Егоров Юрий Петрович
  • Гладких Анатолий Афанасьевич
  • Пятаков Анатолий Иванович
  • Кальников Владимир Викторович
  • Бородина Екатерина Сергеевна
RU2438252C1
СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ЦИФРОВОЙ ИНФОРМАЦИИ В ВИДЕ УЛЬТРАСЖАТОГО НАНОБАР-КОДА (ВАРИАНТЫ) 2013
  • Пряхин Евгений Иванович
  • Ларионова Екатерина Владимировна
  • Захаренко Евгений Анатольевич
RU2656734C2
Способ передачи и приема сигналов в режиме псевдослучайной перестройки рабочей частоты 2021
  • Дворников Сергей Викторович
  • Пшеничников Александр Викторович
  • Манаенко Сергей Сергеевич
  • Левин Яков Яковлевич
RU2762376C1
ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ 2008
  • Агеев Сергей Александрович
  • Гладких Анатолий Афанасьевич
  • Кержнер Дмитрий Алексеевич
  • Кулешов Игорь Александрович
  • Петров Валерий Владимирович
  • Репин Геннадий Александрович
  • Служивый Максим Николаевич
RU2379841C1
ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ 2007
  • Гладких Анатолий Афанасьевич
  • Черторийский Сергей Юрьевич
  • Тетерко Вадим Владимирович
  • Шакуров Радик Шамильевич
  • Закирова Лилия Рэстемовна
RU2344556C1
СПОСОБ ФОРМИРОВАНИЯ И ПРОВЕРКИ ЗАВЕРЕННОГО ЦИФРОВЫМ ВОДЯНЫМ ЗНАКОМ ЭЛЕКТРОННОГО ИЗОБРАЖЕНИЯ 2010
  • Оков Игорь Николаевич
  • Сухов Тимофей Михайлович
  • Цветков Василий Валерьевич
RU2450354C1

Реферат патента 2010 года СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ДАННЫХ БЕЗ ПОТЕРЬ

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

Формула изобретения RU 2 382 492 C1

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

Документы, цитированные в отчете о поиске Патент 2010 года RU2382492C1

СПОСОБ ДЕКОДИРОВАНИЯ ПРЕФИКСНЫХ КОДОВ ПЕРЕМЕННОЙ ДЛИНЫ 2003
  • Желтов Сергей Николаевич
  • Братанов Станислав Викторович
RU2321169C2
RU 2005104018 A, 20.07.2006
Аппарат для очищения воды при помощи химических реактивов 1917
  • Гордон И.Д.
SU2A1
СИСТЕМА КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ БЕЗ ПОТЕРЬ 1999
  • Хео Дзае-Хоон
RU2158057C1
US 6008745 А, 28.12.1999.

RU 2 382 492 C1

Авторы

Муллов Сергей Борисович

Даты

2010-02-20Публикация

2008-07-24Подача