Модификатор энтропии и способ его использования
ENTROPY MODIFIER AND METHOD TO USE IT

ОБЛАСТЬ ТЕХНИКИ
Настоящее изобретение относится к области техники, связанной с модификаторами энтропии, которые принимают входные данные и генерируют соответствующие выходные данные, уровень энтропии которых изменен по отношению к входным данным, например, с целью сжатия и/или декомпрессии данных; при этом модификаторы энтропии реализуются с использованием электронного оборудования и/или программного обеспечения, хранимого на машиночитаемом носителе информации и исполняемого вычислительным устройством. Кроме того, настоящее изобретение также относится к способам модификации энтропии входных данных с целью генерации соответствующих выходных данных с модифицированным уровнем энтропии относительно входных данных. Помимо этого, настоящее изобретение относится к программным изделиям, которые записаны на машиночитаемом носителе информации и исполняются вычислительным устройством для реализации указанных выше способов. Модификаторы энтропии используются, например, в качестве компонентов систем передачи данных и систем поставки данных, таких как системы поставки мультимедийной информации.
ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ
В общем случае в теории информации под энтропией понимается мера неопределенности случайной переменной, относящаяся к физическим непрерывным системам, например к термодинамическим системам, а также к информационным системам, например к системам передачи данных. Кроме того, в контексте систем передачи данных более правильно называть энтропию шенноновской энтропией в честь Клода Шеннона, написавшего в 1948 году научную статью "Математическая теория связи", которая включена в настоящую заявку посредством ссылки. Шенноновская энтропия используется для количественного определения ожидаемой величины информации, содержащейся в заданном сообщении. Кроме того, шенноновская энтропия выражается в таких единицах, как наты, баны, а также биты.
Шенноновская энтропия определяет абсолютный предел в отношении наилучшего кодирования или сжатия любых передаваемых данных без потерь с учетом того, что заданный сеанс связи представляется как последовательность независимых и идентично распределенных случайных величин. Кроме того, согласно теории Шеннона утверждается, что средняя длина L кратчайшего возможного представления для кодирования заданного сообщения в заданном алфавите равна его энтропии E, деленной на логарифм количества символов N, содержащихся в алфавите, то есть вычисляется по формуле 1.
Таким образом, энтропия E является мерой неопределенности или количеством информации. В соответствии со способом сжатия данных без потерь, сжатые выходные данные, генерируемые путем применения способа сжатия к соответствующим входным данным, характеризуются таким же количеством информации, что и входные данные, но содержат меньшее количество битов, чем входные данные. Следовательно, сжатые выходные данные являются более непредсказуемыми, поскольку информация, содержащаяся в них, менее избыточна.
Теория Шеннона учитывается при разработке известных устройств кодирования данных. Например, в опубликованной международной заявке WO 2010/050157 A1 (PCT/JP 2009/005548, "Image encoding apparatus, image encoding method, and image encoding program" (устройство, способ и программа кодирования образов), заявитель - Thomson Licensing), описывается устройство, способ и программа кодирования образов, которые функционируют для гомогенизирования качества образов в целом без уменьшения эффективности кодирования, работают на высокой скорости и способны уменьшить объем схемотехники путем перестановки макроблоков без изменения структуры массива данных. Кроме того, предлагается устройство кодирования образов, содержащее:
(i) блок перестановки, который накапливает и переставляет множество макроблоков, составляющих данные образа, из соответствующих позиций в пределах образа;
(ii) блок кодирования, который выполняет пространственно-частотное преобразование и энтропийное кодирование множества макроблоков, накопленных и переставленных блоком перестановки; и
(iii) блок регулирования скорости, который управляет блоком кодирования с целью настройки скорости передачи множества макроблоков после выполнения кодирования.
Для данных, независимо от их типа, требуется пространство на носителе информации, а также полоса пропускания, выделяемая из общей пропускной способности сети связи, при перемещении от одного пространственного расположения к другому. Такая полоса пропускания в реальных условиях связана с вложениями в инфраструктуру связи и с использованием энергии. Поскольку объем данных, подлежащих передаче, планируется так, чтобы имелась возможность его увеличения в будущем, возникает необходимость в большем пространстве на носителе информации и в большей пропускной способности системы связи, а также часто требуется больший уровень энергии. В современной сети Интернет хранится огромный объем данных, часто в виде множества копий. В связи с этим любой подход, позволяющий сжимать данные, особенно если при этом не теряется информация, потенциально приносит значительные технические и экономические преимущества. На современном уровне техники существуют несколько известных способов уменьшения энтропии в наборах данных с целью их сжатия. Кроме того, существуют известные способы модификации энтропии в наборах данных, например дельта-кодирование и кодирование длин серий (RLE, Run-Length-Encoding), однако все еще требуются новые способы, которые обеспечат более эффективное сжатие данных.
Так, существует множество различных способов сжатия конкретных данных путем уменьшения энтропии, присутствующей в этих данных, например отмеченное выше кодирование RLE, кодирование VLC, кодирование методом Хаффмана, дельта-кодирование, арифметическое кодирование и интервальное кодирование. Эти способы обычно разрабатываются для сжатия символов, чисел, байтов и слов. Однако такие способы не практичны для сжатия отдельных битов, и по этой причине они не идеальны для сжатия данных, которые могут изменяться побитовым образом, например для потоков битов данных.
В процессе стандартного кодирования RLE сохраняется либо заданное значение, то есть бит, либо два значения, то есть бит, после которого следует ряд аналогичных значений, то есть битов. RLE может применяться избирательно, например, этот способ кодирования может быть зарезервирован исключительно для кодирования последовательностей, содержащих известное количество битов для ряда аналогичных значений. Такое избирательное применение RLE требует, чтобы одинаковое значение размещалось один раз или дважды в заданном потоке данных с каждой новой последовательностью. Однако в настоящее время требуются улучшенные подходы к сжатию данных, которые бы уменьшали энтропию в наборах данных, независимо от их типа.
СУЩНОСТЬ ИЗОБРЕТЕНИЯ
Первой целью настоящего изобретения является реализация улучшенного модификатора энтропии, например, для усовершенствования процедуры сжатия данных.
Второй целью настоящего изобретения является реализация улучшенного способа модификации энтропии, например, для усовершенствования процедуры сжатия данных.
В соответствии с первым аспектом настоящего изобретения предлагается модификатор энтропии согласно п. 1 прилагаемой формулы изобретения, а именно: предлагается модификатор энтропии, выполненный с возможностью побитового кодирования потока битов входных данных (D1), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D2) с модифицированной энтропией, характеризующихся второй величиной энтропии, при этом
(a) модификатор энтропии выполнен с возможностью побитовой генерации выходных данных (D2), включающих информацию о первом бите, которая используется в качестве опорного значения для последующих данных, включаемых в выходные данные (D2);
(b) в состав выходных данных (D2) также входят данные, указывающие длины последовательностей одинаковых битов, представленных во входных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности (MaxRun); и
(c) одно или более появлений длин последовательностей во входных данных (D1), по существу превышающих значение максимальной длины последовательности (MaxRun), отмечают по меньшей мере одним управляющим кодом (escape code), включаемым в выходные данные (D2).
Преимущество настоящего изобретения состоит в том, что избирательное использование представления длины последовательности данных позволяет реализовать улучшенный процесс модификации энтропии, например улучшенный процесс сжатия данных.
Опционально, модификатор энтропии реализуется таким образом, чтобы одна или более максимальных длин последовательностей (MaxRun) групп одинаковых битов управлялась множеством управляющих кодов.
В одном из решений в качестве управляющего кода используется значение максимальной длины последовательности и индикация того, что количество одинаковых битов не исчерпано. Согласно этому решению, все символы могут быть кодированы в виде одного потока данных. Другой вид управляющего кода позволяет использовать множество различных решений, отдельно от кодированных символов, и представляет количество следующих друг за другом одинаковых битов, которое превышает значение максимальной длины последовательности. Согласно этому решению могут обрабатываться два отдельных потока, или может быть разработано решение, в соответствии с которым любое количественное значение не превышает максимальную последовательность, вследствие чего они могут также кодироваться с таким же потоком других символов. Кроме того, могут использоваться другие способы формирования управляющего кода.
Опционально, модификатор энтропии выполнен с возможностью реализации по меньшей мере одного управляющего кода в выходных данных (D2) посредством величины "0" в данных.
Опционально, модификатор энтропии выполнен с возможностью обработки потоков битов входных данных (D1) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D1).
Опционально, модификатор энтропии выполнен с возможностью функционирования в качестве препроцессора данных для переформатирования входных данных (D1) в выходные данные (D2) с целью последующего сжатия в рамках одной или более схем кодирования для генерации сжатых данных (D3).
Опционально, к одной или более схемам кодирования могут относиться одна или более следующих схем: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, модификатор энтропии выполнен с возможностью обработки потока битов входных данных (D1) в множестве отдельно обрабатываемых частей. В частности, модификатор энтропии выполнен с возможностью обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, модификатор энтропии выполнен с возможностью обработки множества частей с использованием значений максимальной длины последовательностей (MaxRun), которые взаимно отличаются для одной или более частей.
Следует учитывать, что информация о первом бите может кодироваться в собственный поток данных или в тот же поток данных с информацией о длине последовательности, или информация о первом бите может включаться в информацию об используемом способе кодирования.
Опционально, модификатор энтропии реализуется для функционирования в качестве кодера, сжимающего поток входных данных (D1) с целью генерации выходных данных (D2 или D3) с модифицированной энтропией.
Опционально, модификатор энтропии выполнен с возможностью участия в процессе преобразования битовой строки входных данных (D1) в символы выходных данных (D2 или D3) с модифицированной энтропией.
Опционально, модификатор энтропии содержит вычислительное оборудование, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D1) с целью генерации выходных данных (D2).
В соответствии со вторым аспектом настоящего изобретения предлагается модификатор энтропии, выполненный с возможностью декодирования потока битов входных данных (D3 или D4), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D5) с модифицированной энтропией, характеризующихся второй величиной энтропии, при этом
(a) модификатор энтропии выполнен с возможностью побитовой обработки входных данных (D3 или D4) с использованием информации о первом бите этих данных, которая применяется в качестве опорного значения для последующих данных, включенных во входные данные (D3 или D4);
(b) модификатор энтропии выполнен с возможностью обработки данных, присутствующих в составе входных данных (D3 или D4) и указывающих длины последовательностей одинаковых битов, представленных в исходных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности {MaxRun); и
(c) модификатор энтропии выполнен с возможностью обнаружения одного или более появлений длин последовательностей в исходных данных (D1), по существу превышающих значение максимальной длины последовательности и отмеченных по меньшей мере одним управляющим кодом, включенным во входные данные (D3 или D4).
Опционально, модификатор энтропии выполнен с возможностью обработки одной или более максимальных длин последовательностей (MaxRun) групп одинаковых битов с помощью по меньшей мере одного управляющего кода. В частности, модификатор энтропии реализуется таким образом, чтобы одна или более максимальных длин последовательностей (MaxRun) групп одинаковых битов обрабатывалась с использованием множества управляющих кодов.
Опционально, по меньшей мере один управляющий код представляет собой значение "0" во входных данных (D3 или D4).
В одном из решений в качестве управляющего кода используется значение максимальной длины последовательности и индикация того, что количество одинаковых битов не исчерпано. Согласно этому решению, все символы могут быть кодированы в виде одного потока данных и сходным образом могут декодироваться в виде одного потока данных. Другой вид управляющего кода позволяет использовать множество различных решений, отдельно от кодированных символов, и представляет количество следующих друг за другом одинаковых битов, которое больше значения максимальной длины последовательности. Согласно этому решению, могут обрабатываться два отдельных потока, или может быть разработано решение, в соответствии с которым любое количественное значение не превышает максимальную последовательность, вследствие чего они могут также кодироваться с таким же потоком других символов. Кроме того, могут использоваться другие способы формирования управляющего кода.
Опционально, модификатор энтропии выполнен с возможностью управления потоком битов входных данных (D3 или D4) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D3 или D4).
Опционально, модификатор энтропии выполнен с возможностью обработки информации о значении первого бита в потоке битов входных данных (D3 или D4) отдельно от последовательности битов данных. В частности, модификатор энтропии выполнен с возможностью обработки значения первого бита в виде отдельно кодированной информации по отношению к последовательности значений данных, представляющих количество следующих друг за другом одинаковых битов.
Опционально, модификатор энтропии выполнен с возможностью декодирования элементов данных, присутствующих во входных данных (D3 или D4), и применения обратной модификации энтропии для генерации выходных данных (D5) в виде декодированного потока битов.
Опционально, модификатор энтропии используется для постобработки совместно с одной или более схем кодирования с целью обработки потока битов входных данных (D3 или D4), при этом применяется одна или более следующих схем кодирования: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, модификатор энтропии выполнен с возможностью обработки потока битов входных данных (D3 или D4) в множестве отдельно кодируемых или декодируемых частей. В частности, модификатор энтропии выполнен с возможностью обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, модификатор энтропии выполнен с возможностью обработки множества частей с использованием значений максимальной длины последовательностей (MaxRun), которые взаимно отличаются для одной или более частей.
Опционально, модификатор энтропии реализуется для функционирования в качестве декодера для декомпрессии входных данных (D3 или D4) с целью генерации выходных данных (D5) с модифицированной энтропией.
Опционально, модификатор энтропии выполнен с возможностью участия в процессе преобразования символов во входных данных (D3 или D4) в битовую строку, представленную в выходных данных (D5).
Опционально, модификатор энтропии содержит вычислительное оборудование, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D3 или D4) с целью генерации выходных данных (D5).
В соответствии с третьим аспектом настоящего изобретения предлагается способ использования модификатора энтропии, позволяющий выполнять побитовое кодирование потока битов входных данных (D1), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D2) с модифицированной энтропией, характеризующихся второй величиной энтропии, при этом способ включает:
(a) использование модификатора энтропии для побитовой генерации выходных данных (D2) включающих информацию о первом бите, которая используется в качестве опорного значения для последующих данных, включаемых в выходные данные (D2);
(b) включение в состав выходных данных (D2) также данных, указывающих длины последовательностей одинаковых битов, представленных во входных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности (MaxRun); и
(c) отметку одного или более появлений длин последовательностей во входных данных (D1), по существу превышающих максимальную величину последовательности, по меньшей мере одним управляющим кодом, включаемым в выходные данные (D2).
Опционально, способ включает использование множества управляющих кодов для управления одной или более максимальных длин последовательностей (MaxRun) групп одинаковых битов. В частности, способ включает применение модификатора энтропии для обработки потока битов входных данных (D1) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D1).
Опционально, способ включает реализацию по меньшей мере одного управляющего кода в выходных данных (D2) посредством значения «0» в данных.
Опционально, способ включает использование модификатора энтропии для функционирования в качестве препроцессора данных для переформатирования входных данных (D1) в выходные данные (D2) с целью последующего сжатия в рамках одной или более схем (20) кодирования для генерации сжатых данных (D3). Опционально, к одной или более схемам кодирования могут относиться одна или более следующих схем: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, способ включает использование модификатора энтропии для обработки потока битов входных данных (D1) в множестве отдельно обрабатываемых частей. В частности, способ включает использование модификатора энтропии для обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, способ включает применение модификатора энтропии для обработки множества частей с использованием значений максимальной длины последовательностей (MaxRun), которые взаимно отличаются для одной или более частей.
Опционально, способ включает реализацию модификатора энтропии для функционирования в качестве кодера, сжимающего поток входных данных (D1) с целью генерации выходных данных (D2 или D3) с модифицированной энтропией. В частности, способ включает использование модификатора энтропии в процессе преобразования битовой строки входных данных (D1) в символы выходных данных (D2 или D3) с модифицированной энтропией.
Опционально, способ включает реализацию модификатора энтропии с использованием вычислительного оборудования, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D1) с целью генерации выходных данных (D2).
В соответствии с четвертым аспектом настоящего изобретения предлагается способ использования модификатора энтропии, позволяющий декодировать поток битов входных данных (D3 или D4), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D5) с модифицированной энтропией, характеризующихся второй величиной энтропии, при этом способ включает:
(a) использование модификатора энтропии для побитовой обработки входных данных (D3 или D4) с использованием информации о первом бите этих данных, которая применяется в качестве опорного значения для последующих данных, включенных во входные данные (D3 или D4);
(b) использование модификатора энтропии для обработки данных, присутствующих во входных данных (D3 или D4) и указывающих длины последовательностей одинаковых битов, представленных в исходных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности (MaxRun); и
(c) использование модификатора энтропии для обнаружения одного или более появлений длин последовательностей в исходных данных (D1), по существу превышающих значение максимальной длины последовательности и отмеченных по меньшей мере одним управляющим кодом, включенным во входные данные (D3 или D4).
Опционально, способ включает использование модификатора энтропии для обработки одной или более максимальных длин последовательностей (MaxRun) групп одинаковых битов с помощью по меньшей мере одного управляющего кода. В частности, способ включает обработку одной или более максимальных длин последовательностей (MaxRun) групп одинаковых битов с помощью множества управляющих кодов.
Опционально, способ включает реализацию по меньшей мере одного управляющего кода посредством значения «0» во входных данных (D3 или D4).
Опционально, способ включает применение модификатора энтропии для обработки потока битов входных данных (D3 или D4) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D3 или D4).
Опционально, способ включает применение модификатора энтропии для обработки информации о значении первого бита в потоке битов входных данных (D3 или D4) отдельно от последовательности битов данных. В частности, способ включает использование модификатора энтропии для обработки первого бита в виде отдельно кодированной информации по отношению к последовательности значений данных, представляющих количество следующих друг за другом одинаковых битов.
Опционально, способ включает использование модификатора энтропии для декодирования элементов данных, присутствующих во входных данных (D3 или D4), и применения обратной модификации энтропии для генерации выходных данных (D5) в виде декодированного потока битов.
Опционально, способ включает использование модификатора энтропии для постобработки совместно с одной или более схем кодирования с целью обработки потока битов входных данных (D3 или D4), при этом применяется одна или более следующих схем кодирования: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, способ включает использование модификатора энтропии для обработки потока битов входных данных (D3 или D4) в множестве отдельно обрабатываемых частей. В частности, способ включает использование модификатора энтропии для обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, способ включает применение модификатора энтропии для обработки множества частей с использованием значений максимальной длины последовательностей {MaxRun), которые взаимно отличаются для одной или более частей.
Следует учитывать, что декодер получает информацию о значении первого бита из собственного потока данных или из того же потока данных с информацией о длинах последовательностей, или эта информация может включаться в информацию об используемой схеме(-ах) кодирования.
Опционально, способ включает использование модификатора энтропии для функционирования в качестве декодера для декомпрессии входных данных (D3 или D4) с целью генерации выходных данных (D5) с модифицированной энтропией.
Опционально, способ включает использование модификатора энтропии в процессе преобразования символов входных данных (D3 или D4) в битовую строку, представленную в выходных данных (D5).
Опционально, способ включает реализацию модификатора энтропии с использованием вычислительного оборудования, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D3 или D4) с целью генерации выходных данных (D5).
В соответствии с пятым аспектом настоящего изобретения предлагается программное изделие, записанное на машиночитаемом носителе информации и выполняемое вычислительным оборудованием для осуществления способа согласно третьему аспекту настоящего изобретения.
В соответствии с шестым аспектом настоящего изобретения предлагается программное изделие, записанное на машиночитаемом носителе информации и выполняемое вычислительным оборудованием для осуществления способа согласно четвертому аспекту настоящего изобретения.
Дополнительные аспекты, преимущества, признаки и цели настоящего изобретения станут очевидными после ознакомления с чертежами и подробным описанием примеров осуществления, приведенным ниже совместно с прилагаемой формулой изобретения.
Следует принимать во внимание, что признаки настоящего изобретения допускается комбинировать в различных сочетаниях без нарушения объема настоящего изобретения, определенного прилагаемой формулой изобретения.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Варианты осуществления настоящего изобретения описываются ниже только в качестве примеров со ссылкой на прилагаемый чертеж, а именно:
фиг. 1, на котором показан пример системы кодека, содержащего модификаторы энтропии в соответствии с вариантами осуществления настоящего изобретения.
На прилагаемых чертежах подчеркнутые числа используются для обозначения элементов, над которыми или рядом с которыми находятся эти числа. Неподчеркнутые числа относятся к элементам, идентифицируемым линией, которая соединяет их с неподчеркнутым числом.
ПОДРОБНОЕ ОПИСАНИЕ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ
В соответствии с первым аспектом вариантов осуществления настоящего изобретения предлагается модификатор энтропии, выполненный с возможностью побитового кодирования потока битов входных данных (D1), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D2) с модифицированной энтропией, характеризующихся второй величиной энтропии, при этом
(a) модификатор энтропии выполнен с возможностью побитовой генерации выходных данных (D2) включающих информацию о первом бите, которая используется в качестве опорного значения для последующих данных, включаемых в выходные данные (D2);
(b) в состав выходных данных (D2) также входят данные, указывающие длины последовательностей одинаковых битов, представленных во входных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности (MaxRun); и
(c) одно или более появлений длин последовательностей во входных данных (D1), по существу превышающих максимальное значение длины последовательности (MaxRun), отмечаются по меньшей мере одним управляющим кодом, включаемым в выходные данные (D2).
Преимущество настоящего изобретения состоит в том, что избирательное использование представления длины последовательности данных позволяет реализовать улучшенный процесс модификации энтропии, например улучшенный процесс сжатия данных.
Опционально, модификатор энтропии реализуется таким образом, чтобы одна или более максимальных длин последовательностей (MaxRun) групп одинаковых битов управлялась множеством управляющих кодов.
В одном из решений в качестве управляющего кода используется значение максимальной длины последовательности и индикация того, что количество одинаковых битов не исчерпано. Согласно этому решению, все символы могут быть кодированы в виде одного потока данных. Другой вид управляющего кода позволяет использовать множество различных решений, отдельно от кодированных символов, и представляет количество следующих друг за другом одинаковых битов, которое больше значения максимальной длины последовательности. Согласно этому решению, могут обрабатываться два отдельных потока, или может быть разработано решение, в соответствии с которым любое количественное значение не превышает максимальную последовательность, вследствие чего они могут также кодироваться с таким же потоком других символов. Кроме того, могут использоваться другие способы формирования управляющего кода.
Опционально, модификатор энтропии выполнен с возможностью реализации по меньшей мере одного управляющего кода в выходных данных (D2) посредством величины «0» в данных.
Опционально, модификатор энтропии выполнен с возможностью обработки потоков битов входных данных (D1) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D1).
Опционально, модификатор энтропии выполнен с возможностью функционирования в качестве препроцессора данных для переформатирования входных данных (D1) в выходные данные (D2) с целью последующего сжатия в рамках одной или более схем кодирования для генерации сжатых данных (D3).
Опционально, к одной или более схемам кодирования могут относиться одна или более следующих схем: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, модификатор энтропии выполнен с возможностью обработки потока битов входных данных (D1) в множестве отдельно обрабатываемых частей. В частности, модификатор энтропии выполнен с возможностью обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, модификатор энтропии выполнен с возможностью обработки множества частей с использованием значений максимальной длины последовательностей (MaxRun), которые взаимно отличаются для одной или более частей.
Следует учитывать, что информация о первом бите может кодироваться в собственный поток данных или в тот же поток данных с информацией о длине последовательности, или информация о первом бите может включаться в информацию об используемом способе кодирования.
Опционально, модификатор энтропии реализуется для функционирования в качестве кодера, сжимающего поток входных данных (D1) с целью генерации выходных данных (D2 или D3) с модифицированной энтропией.
Опционально, модификатор энтропии выполнен с возможностью участия в процессе преобразования битовой строки входных данных (D1) в символы выходных данных (D2 или D3) с модифицированной энтропией.
Опционально, модификатор энтропии содержит вычислительное оборудование, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D1) с целью генерации выходных данных (D2).
В соответствии со вторым аспектом вариантов осуществления настоящего изобретения предлагается модификатор энтропии, выполненный с возможностью декодирования потока битов входных данных (D3 или D4), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D5) с модифицированной энтропией, при этом
(a) модификатор энтропии служит для побитовой обработки входных данных (D3 или D4) с использованием информации о первом бите этих данных, которая применяется в качестве опорного значения для последующих данных, включенных во входные данные (D3 или D4);
(b) модификатор энтропии выполнен с возможностью обработки данных, присутствующих в составе входных данных (D3 или D4) и указывающих длины последовательностей одинаковых битов, представленных в исходных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности (MaxRun); и
(c) модификатор энтропии выполнен с возможностью обнаружения одного или более появлений длин последовательностей в исходных данных (D1), по существу превышающих значение максимальной длины последовательности и отмеченных по меньшей мере одним управляющим кодом, включенным во входные данные (D3 или D4).
Опционально, модификатор энтропии выполнен с возможностью обработки одной или более максимальных длин последовательности (MaxRun) групп одинаковых битов с помощью по меньшей мере одного управляющего кода. В частности, модификатор энтропии реализуется таким образом, чтобы одна или более максимальных длин последовательности (MaxRun) групп одинаковых битов обрабатывалась с использованием множества управляющих кодов.
Опционально, по меньшей мере один управляющий код представляет собой значение «0» во входных данных (D3 или D4).
В одном из решений в качестве управляющего кода используется значение максимальной длины последовательности и индикация того, что количество одинаковых битов не исчерпано. Согласно этому решению, все символы могут быть кодированы в виде одного потока данных и аналогичным образом могут декодироваться в виде одного потока данных. Другой вид управляющего кода позволяет использовать множество различных решений, отдельных от кодированных символов, и представляет количество следующих друг за другом одинаковых битов, которое больше значения максимальной длины последовательности. Согласно этому решению могут обрабатываться два отдельных потока, или может быть разработано решение, в соответствии с которым любое количественное значение не превышает максимальную последовательность, вследствие чего они могут также кодироваться с этим же потоком других символов. Кроме того, могут использоваться другие способы формирования управляющего кода.
Опционально, модификатор энтропии выполнен с возможностью управления потоком битов входных данных (D3 или D4) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D3 или D4).
Опционально, модификатор энтропии выполнен с возможностью обработки информации о значении первого бита в потоке битов входных данных (D3 или D4) отдельно от последовательности битов данных. В частности, модификатор энтропии выполнен с возможностью обработки значения первого бита в виде отдельно кодированной информации по отношению к последовательности значений данных, представляющих количество следующих друг за другом одинаковых битов.
Опционально, модификатор энтропии выполнен с возможностью декодирования элементов данных, присутствующих во входных данных (D3 или D4), и применения обратной модификации энтропии для генерации выходных данных (D5) в виде декодированного потока битов.
Опционально, модификатор энтропии используется для постобработки совместно с одной или более схем кодирования с целью обработки потока битов входных данных (D3 или D4), при этом применяется одна или более следующих схем кодирования: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, модификатор энтропии выполнен с возможностью обработки потока битов входных данных (D3 или D4) в множестве отдельно кодируемых или декодируемых частей. В частности, модификатор энтропии выполнен с возможностью обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, модификатор энтропии выполнен с возможностью обработки множества частей с использованием значений максимальной длины последовательностей (MaxRun), которые взаимно отличаются для одной или более частей.
Опционально, модификатор энтропии реализуется для функционирования в качестве декодера для декомпрессии входных данных (D3 или D4) с целью генерации выходных данных (D5) с модифицированной энтропией.
Опционально, модификатор энтропии выполнен с возможностью участия в процессе преобразования символов входных данных (D3 или D4) в битовую строку, представленную в выходных данных (D5).
Опционально, модификатор энтропии содержит вычислительное оборудование, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D3 или D4) с целью генерации выходных данных (D5).
В соответствии с третьим аспектом вариантов осуществления настоящего изобретения предлагается способ использования модификатора энтропии, позволяющий выполнять побитовое кодирование потока битов входных данных (D1), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D2) с модифицированной энтропией, характеризующихся второй величиной энтропии, при этом способ включает:
(a) использование модификатора энтропии для побитовой генерации выходных данных (D2) включающих информацию о первом бите, которая используется в качестве опорного значения для последующих данных, включаемых в выходные данные (D2);
(b) включение в состав выходных данных (D2) также данных, указывающих длины последовательностей одинаковых битов, представленных во входных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности (MaxRun); и
(c) отметку одного или более появлений длин последовательностей во входных данных (D1), по существу превышающих максимальную величину последовательности, по меньшей мере одним управляющим кодом, включаемым в выходные данные (D2).
Опционально, способ включает использование множества управляющих кодов для управления одной или более максимальных длин последовательностей (MaxRun) групп одинаковых битов. В частности, способ включает применение модификатора энтропии для обработки потока битов входных данных (D1) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D1).
Опционально, способ включает реализацию по меньшей мере одного управляющего кода в выходных данных (D2) посредством значения «0» в данных.
Опционально, способ включает использование модификатора энтропии для функционирования в качестве препроцессора данных для переформатирования входных данных (D1) в выходные данные (D2) с целью последующего сжатия посредством одной или более схем (20) кодирования для генерации сжатых данных (D3). Опционально, к одной или более схем кодирования могут относиться одна или более следующих схем: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, способ включает использование модификатора энтропии для обработки потока битов входных данных (D1) в множестве отдельно обрабатываемых частей. В частности, способ включает использование модификатора энтропии для обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, способ включает применение модификатора энтропии для обработки множества частей с использованием значений максимальной длины последовательностей (MaxRun), которые взаимно отличаются для одной или более частей.
Опционально, способ включает реализацию модификатора энтропии для функционирования в качестве кодера, сжимающего поток входных данных (D1) с целью генерации выходных данных (D2 или D3) с модифицированной энтропией. В частности, способ включает использование модификатора энтропии в процессе преобразования битовой строки во входных данных (D1) в символы выходных данных (D2 или D3) с модифицированной энтропией.
Опционально, способ включает реализацию модификатора энтропии с использованием вычислительного оборудования, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D1) с целью генерации выходных данных (D2).
В соответствии с четвертым аспектом вариантов осуществления настоящего изобретения предлагается способ использования модификатора энтропии, позволяющий декодировать поток битов входных данных (D3 или D4), характеризующихся первой величиной энтропии, для генерации соответствующих выходных данных (D5) с модифицированной энтропией, характеризующихся второй величиной энтропии, при этом способ включает:
(a) использование модификатора энтропии для побитовой обработки входных данных (D3 или D4) с использованием информации о первом бите этих данных, которая применяется в качестве опорного значения для последующих данных, включенных во входные данные (D3 или D4);
(b) использование модификатора энтропии для обработки данных, присутствующих в составе входных данных (D3 или D4) и указывающих длины последовательностей одинаковых битов, представленных в исходных данных (D1), при этом длины последовательностей одинаковых битов ограничены в размере по существу так, чтобы не превышалось значение максимальной длины последовательности (MaxRun); и
(c) использование модификатора энтропии для обнаружения одного или более появлений длин последовательностей в исходных данных (D1), по существу превышающих значение максимальной длины последовательности и отмеченных по меньшей мере одним управляющим кодом, включенным во входные данные (D3 или D4).
Опционально, способ включает использование модификатора энтропии для обработки одной или более максимальных длин последовательностей (MaxRun) групп одинаковых битов с помощью по меньшей мере одного управляющего кода. В частности, способ включает обработку одной или более максимальных длин последовательностей (MaxRun) групп одинаковых битов с помощью множества управляющих кодов.
Опционально, способ включает реализацию по меньшей мере одного управляющего кода посредством значения «0» во входных данных (D3 или D4).
Опционально, способ включает применение модификатора энтропии для обработки потока битов входных данных (D3 или D4) с использованием значения максимальной длины последовательности (MaxRun) динамически изменяющимся способом в виде функции от характера потока битов входных данных (D3 или D4).
Опционально, способ включает применение модификатора энтропии для обработки информации о значении первого бита в потоке битов входных данных (D3 или D4) отдельно от последовательности битов данных. В частности, способ включает использование модификатора энтропии для обработки первого бита в виде отдельно кодированной информации по отношению к последовательности значений данных, представляющих количество следующих друг за другом одинаковых битов.
Опционально, способ включает использование модификатора энтропии для декодирования элементов данных, присутствующих во входных данных (D3 или D4), и применения обратной модификации энтропии для генерации выходных данных (D5) в виде декодированного потока битов.
Опционально, способ включает использование модификатора энтропии для постобработки совместно с одной или более схем кодирования с целью обработки потока битов входных данных (D3 или D4), при этом применяется одна или более следующих схем кодирования: кодер ODelta, кодер RLE, кодер VLC, кодер Хаффмана, дельта-кодер, арифметический кодер, интервальный кодер.
Опционально, способ включает использование модификатора энтропии для обработки потока битов входных данных (D3 или D4) в множестве отдельно обрабатываемых частей. В частности, способ включает использование модификатора энтропии для обработки множества частей параллельно во времени, то есть посредством параллельного выполнения. В частности, способ включает применение модификатора энтропии для обработки множества частей с использованием значений максимальной длины последовательностей (MaxRun), которые взаимно отличаются для одной или более частей.
Следует учитывать, что декодер получает информацию о значении первого бита из собственного потока данных или из аналогичного потока данных с информацией о длине последовательности, или эта информация может включаться в информацию об используемой схеме(-ах) кодирования.
Опционально, способ включает использование модификатора энтропии для функционирования в качестве декодера для декомпрессии входных данных (D3 или D4) с целью генерации выходных данных (D5) с модифицированной энтропией.
Опционально, способ включает использование модификатора энтропии в процессе преобразования символов входных данных (D3 или D4) в битовую строку, представленную в выходных данных (D5).
Опционально, способ включает реализацию модификатора энтропии с использованием вычислительного оборудования, которое выполняет одну или более программ, записанных на машиночитаемом носителе информации, для обработки потока битов входных данных (D3 или D4) с целью генерации выходных данных (D5).
В соответствии с пятым аспектом вариантов осуществления настоящего изобретения предлагается программное изделие, записанное на машиночитаемом носителе информации и выполняемое под управлением вычислительного оборудования для осуществления способа согласно третьему аспекту раскрытия настоящего изобретения.
В соответствии с шестым аспектом вариантов осуществления настоящего изобретения предлагается программное изделие, записанное на машиночитаемом носителе информации и выполняемое под управлением вычислительного оборудования для осуществления способа согласно четвертому аспекту раскрытия настоящего изобретения.
Далее со ссылкой на чертеж описываются варианты раскрытия настоящего изобретения.
В целом настоящее изобретение относится к модификатору энтропии. На фиг. 1 показано, что входные данные (D1) подаются на первый модификатор 10 энтропии, который преобразует входные данные (D1) для генерации соответствующих преобразованных данных (D2); размер преобразованных данных (D2) в частном случае отличается от размера входных данных (D1) и зависит от характера преобразования, выполняемого в первом модификаторе 10 энтропии, причем уровень энтропии этих данных по отношению к энтропии входных данных (D1) уменьшается. Опционально, преобразованные данные (D2) далее кодируют с помощью каскада 20 для генерации окончательных кодированных выходных данных (D3), однако если каскад 20 кодирования не применяется, то преобразованные данные (D2) и выходные данные (D3) совпадают. Кодированные выходные данные (D3) сохраняются в памяти 30 для хранения данных и/или передаются по сети 40 связи. Кроме того, выходные данные (D3) непосредственно передаются во второй модификатор 60 энтропии или, если применяется указанный выше каскад 20 кодирования, выходные данные дополнительно, через каскад 50 декодирования, передаются в модификатор 60 энтропии, так что по существу данные (D4) аналогичны данным (D2). Второй модификатор 60 энтропии генерирует выходные декодированные данные (D5), которые по существу аналогичны входным данным (D1). Таким образом, первый модификатор 10 энтропии и второй модификатор 60 энтропии выполняют взаимно обратные операции модификации энтропии, например, как в конфигурации кодека.
Опционально, первый (10) и второй (60) модификаторы энтропии выполнены с возможностью обработки пропускаемых через них данных в виде множества параллельных потоков данных для ускорения процесса модификации энтропии, например, для ускорения кодирования и/или декодирования. Такой ускоренный процесс обработки с использованием множества параллельных потоков данных предпочтителен при обработке больших объемов данных, например, при обработке потокового видеоконтента, поступающего из серверов хранения данных, таких как Интернет-серверы, предоставляющие услуги кабельного телевидения.
Таким образом, первый модификатор 10 энтропии принимает поток битов, содержащихся во входных данных (D1), и создает из него элементы данных, энтропия которых ниже по сравнению с энтропией входных данных (D1). Эти элементы модифицированных данных дополнительно кодируются в каскаде 20 кодирования путем применения таких способов, как кодирование с переменной длиной слова (VLC, Variable-Length-Coding), кодирование методом Хаффмана, арифметическое кодирование, интервальное кодирование, кодирование длин серий (RLC, Run-Length-Encoding) и т.п. Процесс модификации энтропии, выполняемый в первом модификаторе 10 энтропии, обратим и отличается отсутствием потерь, и с соответствующими изменениями также реализован в модификаторе 60 энтропии. Кроме того, в ходе выполнения процесса модификации энтропии в первом модификаторе 10 энтропии по меньшей мере сохраняется новый элемент данных, содержащий количество следующих друг за другом одинаковых битов после каждого изменения значения бита.
При уменьшении энтропии, как указано выше, должна обеспечиваться индикация первого бита в любой заданной последовательности. Кроме того, необходимо ввести управляющий код, позволяющий для представления элементов данных применять ограниченное количество кодов, то есть задавать значение максимальной длины последовательности (MaxRun), при необходимости сжатия элементов данных. В одном из вариантов управляющий код представлен цифрой "0"; при этом управляющий код отмечает наибольшее значение, которое может представлять элемент данных, то есть значение максимальной длины последовательности (MaxRun), и дополнительно сообщает о том, что далее значение бита не изменяется. Предпочтительно при реализации вариантов осуществления настоящего изобретения один или более кодов, соответствующих максимальной последовательности битов, изменяется в зависимости от данных и их свойств; другими словами, один или более кодов, соответствующих максимальной последовательности, адаптивно изменяются в зависимости от сжимаемых данных. Опционально, модификаторы 10, 60 энтропии используют способы предварительной обработки и/или постобработки, например оператор ODelta, который производит операции с 1-битовыми данными. Однако модификаторами 10, 60 энтропии могут обрабатываться данные любых типов, например изображения, видеоинформация, звуковая информация, ссылочные данные, маски, биты разделения, знаковые биты и сжатые данные, то есть любые типы данных, которые могут подвергаться побитовой обработке. Опционально, байты или слова любых данных могут включаться в поток битов и обрабатываться модификаторами 10, 60 энтропии. Далее "модификатор энтропии" и "обратный модификатор энтропии" обозначаются, соответственно, как ЕМ и IEM при описании процессов сжатия и декомпрессии данных, выполняемых первым модификатором 10 энтропии и вторым модификатором 60 энтропии.
Модификаторы 10, 60 энтропии в одном из вариантов реализуются с использованием вычислительного оборудования (CPU, центрального процессора) 70, которое выполнено с возможностью исполнения одной или более программ 80, записанных на машиночитаемом носителе 90 информации, для осуществления способа согласно настоящему изобретению.
Ниже более подробно описываются варианты осуществления настоящего изобретения. Модификаторы 10, 60 энтропии применяют один параметр, определяющий максимальное количество нулей или единиц в последовательности, присутствующей, например, в потоке данных. Кроме того, модификаторы 10, 60 энтропии применяют управляющий элемент, который используется в том случае, если последовательность битов в потоке битов превышает максимальную последовательность в этом потоке. Предпочтительно, максимальная длина L последовательности устанавливается равной одному или более значений из следующего ряда:
где n - целое число, принимающее значения 2, 3, …
Это соответствует ряду L=3, 7, 15, 31, …, однако предпочтительно использовать любое число большее 1. Предпочтительно в качестве значения управляющего элемента выбирать "0", поскольку в реализации настоящего изобретения наличие множества нулевых одинаковых битов не представляется возможным. Следует принимать во внимание, что если число одинаковых битов уменьшается на одно указанное выше количество, то управляющий элемент предпочтительно представляет собой максимальную последовательность. При необходимости сжатия потока битов модификатору 10 энтропии требуется информация о первом бите в потоке, для того чтобы впоследствии можно было декодировать, то есть декомпрессировать, в модификаторе 60 энтропии соответствующий сжатый поток битов.
Далее описывается пример для последующего разъяснения вариантов осуществления настоящего изобретения. Ниже представлен первый пример способа энтропийного кодирования, соответствующего функциям настоящего изобретения, для случая, когда максимальная длина последовательности составляет 3 бита, а в качестве управляющего кода используется значение "0".
Исходный поток битов выглядит следующим образом:
и содержит всего двадцать шесть битов в потоке, включая шестнадцать единиц ("1") и десять нулей ("0").
Энтропия E, связанная с этим исходным потоком битов, вычисляется следующим образом:
B
Из формулы 3 следует, что минимальное количество M битов, требуемых для кодирования исходного потока битов, характеризующегося связанной с ним энтропией E, вычисляется с помощью теоремы кодирования источника по следующей формуле:
Упомянутый выше исходный поток битов кодируется путем применения описанного ниже способа генерации соответствующей последовательности кодов согласно настоящему изобретению.
Значение первого бита равно «0», и количество следующих друг за другом одинаковых битов (= символов с модифицированной энтропией) составляет:
Если в качестве управляющего символа используется «0» для ограничения количества различных символов 4 значениями - от 0 (управляющий символ) до 3 (максимальная длина последовательности), и в качестве первого символа в поток также включается значение первого бита, то формируется следующая последовательность:
,
которая содержит всего тринадцать кодов в потоке, включая пять значений «0», четыре значения "1", два значения "2" и два значения "3".
Энтропия E, связанная с этим потоком кодов, вычисляется следующим образом:
B
Из этой формулы следует, что минимальное количество битов M для представления такой энтропии E без потерь вычисляется следующим образом:
Из этого примера следует, что энтропия последовательности кодов меньше энтропии исходного потока битов, и для представления последовательности кодов требуется меньшее количество битов. В одном из вариантов последовательность кодов с модифицированной энтропией генерируется таким образом, как это показано в таблице 1.
Таблица 1 приводится только в качестве примера и варианты осуществления настоящего изобретения могут быть реализованы в соответствии с множеством альтернативных примеров. Например, могут применяться другие значения максимальной длины последовательности и другие управляющие коды. Кроме того, в одном из вариантов первый бит вставляется отдельно и в какой-либо значительной степени не влияет на фактические применяемые коды и связанное с ними сжатие.
Опционально, модификаторы 10, 60 энтропии выполнены с возможностью в определенных обстоятельствах увеличивать энтропию, и, таким образом, выходные данные из модификаторов 10, 60 энтропии контролируются, например, с использованием схемы контроля сигналов для определения, обеспечивает ли применяемый режим кодирования требуемый уровень сжатия данных. В случае увеличения энтропии для заданного типа передаваемых данных схема контроля сигналов может применяться для выполнения операции адаптивного управления модификаторами 10, 60 энтропии с целью обеспечения в процессе функционирования требуемой модификации энтропии. Например, для заданного типа данных желательно, чтобы модификатор 10 энтропии использовался в одном или более режимах тестового кодирования при инициализации кодирования потока данных, для того чтобы найти оптимальное значение максимальной последовательности с целью получения оптимального уровня сжатия данных; при этом максимальная последовательность может оказывать наибольшее влияние на энтропию E. Кроме того, энтропия E, связанная со значением первого бита в заданном потоке данных, оказывает основное влияние на энтропию E, если длина заданного потока данных относительно невелика; например, значение первого бита предпочтительно передается отдельно от других кодовых слов, используемых для представления заданного потока данных.
Как показано на фиг. 1, предпочтительно, чтобы модификаторы 10, 60 энтропии использовались совместно со средствами реализации способов энтропийного кодирования, такими как кодирование с переменной длиной слова (VLC), кодирование методом Хаффмана, кодирование длин серий (RLE), арифметическое кодирование и интервальное кодирование. В альтернативном варианте совместно с указанными способами предпочтительно применяются модификаторы энтропии других типов, например, предназначенные для дельта-кодирования. Такие способы энтропийного кодирования предпочтительно применяются после обработки данных модификатором 10 энтропии и перед обработкой данных модификатором 60 энтропии; в альтернативном варианте или дополнительно такие способы энтропийного кодирования предпочтительно применяются перед обработкой данных модификатором 10 энтропии и после обработки данных модификатором 60 энтропии, например, в том случае если исходные данные, подлежащие кодированию, представляют собой алфавитно-цифровые символы, числа, байты или слова, то эти данные эффективно кодируются с помощью дополнительных способов, как указано в таблице 2.
Опционально, модификаторы 10, 60 энтропии используются рекурсивно.
Как было указано выше, модификаторы энтропии, соответствующие настоящему изобретению, предпочтительно используются совместно с другими модификаторами энтропии известных типов. Например, к таким известным типам относится дельта-кодирование. Обычно дельта-кодирование применяется для обработки численных значений, представленных в виде байтов или слов. В качестве примера далее в соответствии с вариантами осуществления настоящего изобретения описывается модификатор энтропии, применяемый совместно со средствами дельта-кодирования.
Для последующего разъяснения настоящего изобретения описываются два примера, в одном из которых не используется модификатор энтропии, соответствующий настоящему изобретению, а в другом такой модификатор используется. В этом примере максимальная длина последовательности составляет 7 битов, а связанный с ней управляющий код равен «0». При использовании 1-битового оператора типа ODelta первый бит в кодированной последовательности совпадает с соответствующим битом исходных данных, присутствующим в потоке исходных данных, подлежащем кодированию. Кроме того, 1-битовая операция ODelta может выполняться рекурсивно.
Пример 1
В исходном потоке битов данных содержится в целом тридцать семь битов, включая семнадцать единиц ("1") и двадцать нулей («0»):
0 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1,
при этом соответствующая энтропия E, связанная с этим потоком, вычисляется согласно приведенной ниже формуле:
B
что, как показано выше, соответствует вычисляемому значению M, равному 36.82 битов, то есть фактически 37 битам. Следует учитывать, что формула 7 соответствует количеству битов в исходном потоке битов.
Ниже показан эквивалентный код с модифицированной энтропией (ЕМ), полученный с помощью способа, в целом сходного с тем, который применялся для генерации кода, представленного в таблице 1:
при этом соответствующая энтропия E, связанная с этим потоком, вычисляется согласно приведенной ниже формуле:
Следует учитывать, что формула 8 соответствует количеству битов, полученному после модификации энтропии. Кроме того, следует учитывать, что это количество битов меньше того, которое вычисляется на основе формулы 7.
Однако, если к исходному потоку битов, указанному выше, применяется операция ODelta, генерируется соответствующий модифицированный поток, содержащий тридцать семь битов, включая тринадцать единиц ("1") и двадцать четыре нуля («0»):
при этом соответствующая энтропия E вычисляется согласно приведенной ниже формуле:
то есть это значение меньше энтропии E, связанной с исходным потоком битов (см. формулу 7). Если в приведенном выше потоке битов данных, обработанных посредством операции ODelta, модифицируется энтропия согласно настоящему изобретению, то получается следующая соответствующая кодированная последовательность кодов:
при этом соответствующая энтропия E вычисляется согласно приведенной ниже формуле:
из которой следует, что энтропия E меньше энтропии E исходного потока (см. формулу 7) битов данных, содержащего в целом 37 битов. Кроме того, следует учитывать, что это количество битов меньше того, что вычисляется на основе формулы 8 или формулы 9.
Этот пример иллюстрирует возможность эффективного сжатия исходного потока битов данных, если исходный поток данных вначале сжимается с использованием 1-битового оператора ODelta, после чего в соответствии с настоящим изобретением применяется модификатор энтропии.
Пример 2
Указанный выше в примере 1 исходный поток битов разделяется на две части, и преимущества модификации энтропии согласно настоящему изобретению увеличиваются благодаря выбору наилучшей комбинации из этих двух результирующих потоков данных. Значение первого бита модификатора энтропии передается отдельно и не включается в результирующую последовательность кодов с уменьшенной энтропией. Результат выполнения первого процесса модификации энтропии, подобен тому, что получен в примере 1, при этом первый бит также устанавливается в виде кодового слова "1". Применяется аналогичная максимальная последовательность из семи битов, и «0» используется в качестве управляющего кода, как показано в таблице 3.
Из таблицы 3 следует, что достигается уменьшение энтропии, эффект от которого увеличивается в случае сжатия данных. Наибольшая степень сжатия данных достигается, если первая часть потока данных энтропийно кодируется на основе данных, сгенерированных из исходного потока данных с модифицированной энтропией, а именно: эта часть представлена 13,49 битами, а во второй части энтропия модифицируется с использованием 1-битового ODelta-кодирования, а именно: эта часть представлена 5,80 битами, в результате требуется 19,29 битов по сравнению с исходными 37 битами, что говорит о высоком уровне сжатия данных. Если второй поток данных кодируется, то значение первого бита передавать не требуется, поскольку оно может быть получено на основе первого потока данных. По этой причине в таблице 3 показаны два различных значения, разделенные знаком 7"; первое значение указано для ситуации продолжения (то есть значение первого бита не передается), а второе - для случая, когда поток данных начинается с этого вида комбинации битов. Следует принимать во внимание, что, хотя в этом примере ODelta-кодирование само по себе уменьшает энтропию данных, а именно, в основном для второй части данных, полезное уменьшение энтропии также обеспечивается в совокупности с применением модификаторов 10, 60 энтропии. В данном случае исходные данные с модифицированной энтропией характеризуются меньшей энтропией, чем данные с модифицированной энтропией, которые вначале обрабатываются с помощью ODelta-кодирования, а именно: 6,00 битов < 9,61 битов. В практических решениях по кодированию исходные данные с модифицированной энтропией дополнительно сжимаются более эффективно, чем данные, к которым применяется ODelta-кодирование, хотя энтропия в последнем случае меньше, а именно: 5,80 битов < 6,00 битов; 1-битовые данные не так практичны для реализаций энтропийных кодеров, хотя арифметическое кодирование, среди прочих способов, также успешно применяется для сжатия 1-битовых данных. Опционально, исходный поток битов разделяется более чем на две части перед выполнением процессов модификации энтропии для осуществления сжатия данных.
Опционально, разделение исходного потока битов данных на один или более потоков, то есть на части, может выполняться автоматически с помощью способа, включающего:
(a) анализ энтропии, связанной с исходным потоком битов данных;
(b) разделение исходного потока данных на две или более части в зависимости от функции проанализированной энтропии исходного потока битов данных;
(c) применение одной или более операций модификации энтропии к двум или более частям для генерации одной или более соответствующих частей с модифицированной энтропией и
(d) объединение одной или более частей с модифицированной энтропией для генерации сжатых кодированных выходных данных.
Настоящее изобретение также относится к способу декодирования кодированных выходных данных, при выполнении которого операции (a)-(d) выполняются в обратном порядке. Опционально, способ включает разделение или объединение блоков данных, представленных в исходном потоке битов, для повышения эффективности кодирования, например, для достижения улучшенного коэффициента сжатия и/или для выполнения сжатия без существенных потерь.
Опционально шаг (b) реализуется грубым образом, то есть просто путем разделения исходного потока битов данных, если в нем встречается множество секций длинных последовательностей, а именно: после или между областями исходного потока битов данных, в которых существует достаточно большая область, в которой биты данных последовательно и быстро изменяются.
Опционально, для генерации кодированного потока битов в соответствии с настоящим изобретением исходный поток битов данных обрабатывается для формирования промежуточных кодированных данных, например, с помощью применения VLC, арифметического или интервального кодирования и/или RLE, после чего выполняется модификация энтропии этих данных в соответствии с настоящим изобретением для генерации сжатых выходных кодированных данных с уменьшенным уровнем энтропии, таким образом, как это показано на фиг. 1. Таким образом, достигается значительная оптимизация скорости сжатия данных, что способствует уменьшению необходимой вычислительной мощности при реализации настоящего изобретения с помощью одного или более программных изделий, записанных на машиночитаемом носителе информации и выполняемых под управлением вычислительного оборудования для реализации кодера, модифицирующего энтропию, и, с необходимыми изменениями, декодера, модифицирующего энтропию. Опционально, способы оптимизации энтропии реализуются таким образом, чтобы исходный бит, алфавитно-цифровой символ, число, байт, слово, содержащиеся в исходном потоке битов данных, вначале кодировались с использованием некоторого другого способа, а затем для генерации кодированных выходных данных применялся способ модификации энтропии в соответствии с настоящим изобретением.
Согласно известным в настоящее время способам кодирования длин серий (RLE) генерируется определенное значение, а затем - соответствующие данные, указывающие количество появлений этого значения перед тем, как за ним последует другое значение. Такой способ RLE выполняется до тех пор, пока доступны входные данные, подлежащие кодированию, то есть значения последовательно кодируются одно за другим. С другой стороны, настоящее изобретение основано на том факте, что если используются только 1-битовые значения, то нет необходимости добавлять значения данных «0» и "1" в поток подлежащих кодированию данных, поскольку они появляются попеременно в свою очередь, и, таким образом, достаточно отразить только первое значение в заданной последовательности при передаче кодированных данных. Таким образом, настоящее изобретение сходно со способом кодирования RLE, но, как упоминалось выше, согласно его реализации применяется 1-битовый поток данных.
При реализации вариантов раскрытия настоящего изобретения также дополнительно применяется управляющий код, который позволяет более эффективно использовать на практике способы кодирования. Предпочтительно, в вариантах осуществления настоящего изобретения выполняется передача одной или более таблиц кодирования из кодера в соответствующий декодер для содействия в процессе декодирования кодированных данных, переданных из кодера и принятых в декодере. Некоторые весьма выгодные способы доставки таких таблиц кодирования раскрыты, например, в заявке на патент GB 1403039.9, поданной заявителем 20 февраля 2014 года и включенной в настоящую заявку посредством ссылки. Другие способы, объединяющие энтропийное кодирование и доставку таблиц кодирования, раскрыты в заявке на патент GB 1403038.1, поданной заявителем 20 февраля 2014 года и включенной в настоящую заявку посредством ссылки. Оба вышеупомянутых раскрытых способа хорошо подходят для использования совместно с настоящим изобретением и помогают минимизировать объем дополнительных данных кодирования, требуемых для энтропийного кодирования.
Управляющие коды, которые применяются для реализации вариантов осуществления настоящего изобретения, могут формироваться несколькими различными способами. Например, в случае символа или цифры длины последовательности, за которым следует значение "0", достигается удовлетворительный уровень кодирования. Однако потенциально возникают ситуации, когда эти количественные значения малы, в то время как, с другой стороны, иногда могут появиться очень большие значения, и в этих ситуациях управляющий код предпочтительно устанавливается в виде следующего, еще не использованного значения, или выделяется для использования в качестве кодового слова. Например, если максимальная применяемая длина последовательности составляет семь битов или элементов и управляющий код равен "0", то кодовое слово "8" используется в процессе генерации кодированного потока данных, причем этот новый управляющий код добавляет только одно новое кодовое слово, и после этого фактическое количество символов выражается с помощью любого из способов, например, с помощью 1, 2 и/или 3 байтов или полубайтов. Опционально, фактическое количество символов при передаче не сжимается. Опционально, фактическое количество символов объединяется со значением максимальной  длины последовательности, а затем сжимается совместно с другими значениями данных в устройстве энтропийного сжатия, а именно - в модификаторе энтропии.
При выборе подходящего управляющего значения для использования в вариантах осуществления настоящего изобретения предпочтительно сразу представить общее количество соседних элементов, и, таким образом, после активизации этого управляющего значения тот же самый бит впоследствии не повторяется, что не противоречит использованию управляющего значения. С помощью такой новой формы завершения последовательности обеспечивается управляющий код, то есть кодовое слово, дополнительно используемое с упомянутым выше способом определения управляющего кода для продолжающейся последовательности; в альтернативном варианте такой новый управляющий код используется только в качестве одного из возможных способов, и в этом случае соответствующее ему кодовое слово предпочтительно устанавливается равным значению «0». Таким же образом, если заданное значение этого кода завершения часто мало, но иногда бывает большим, предпочтительно следует выражать число последовательных одинаковых символов, присутствующих в данных, с помощью чередующегося количества байтов или полубайтов. Один бит такого байта, например младший бит (LSB, least significant bit) или старший бит (MSB, most significant bit), предпочтительно резервируется для указания завершения числа, например строки битов, и, таким образом, предпочтительно его кодовое слово устанавливается равным значению «0» или "1" при окончании значении, в других случаях значение продолжается.
Для разъяснения предшествующего описания, ниже приводится пример функционирования управляющего кода в том случае, если применяются оба типа управляющего кода. Согласно этому примеру максимальная длина последовательности составляет 14 элементов с кодовым словом для продолжающейся последовательности, обозначаемым числом 15, в то время как кодовое слово для завершения последовательности равно 0. Кроме того, значения последовательных одинаковых символов или битов представляют собой следующий ряд:
9, 1024, 16, 9, 12, 2000, 7, 20, 21, 6, 8, 120, 12, …
Кроме того, в этом примере используются полубайты, в которых старшему биту (MSB) присваивается значение "1" для указания на завершение числа, то есть строки битов. Предпочтительно, если применяется управляющий код для завершения последовательности, то возможно выполнить следующую операцию вычитания из числа, то есть битового потока:
Например:
1+8(завершение) 7 6 1). Таким образом, согласно этому примеру последовательность может быть кодирована следующим образом:
В этом примере модификаторам 10, 60 энтропии требуется интерпретировать кодовые слова в диапазоне значений от 0 до 15. В реальной ситуации этот пример может быть представлен с помощью только одного управляющего кода, при этом кодовое слово "0" соответствует управляющему коду, который также указывает на завершение последовательности; в таком альтернативном примере управляющего кода одного типа управляющий код для продолжения последовательности не используется, а применяются другие параметры в соответствии с указанной выше последовательностью, а именно:
при этом модификаторы энтропии 10, 60 требуются для распознавания слов в диапазоне от 0 до 14. В этом альтернативном примере используется только управляющий код для продолжения последовательности, выраженный кодовым словом "0", и применяется максимальная длина последовательности, равная 14, в результате чего формируется следующая последовательность кодов:
Наилучшее решение для кодирования можно выбрать на основе энтропии, рассчитываемой отдельно для каждого из трех решений.
Далее описываются варианты осуществления настоящего изобретения для реализации модификации энтропии (ЕМ, entropy modification) и обратной модификации энтропии (IEM, inverse entropy modification). Однако также возможны другие варианты осуществления в пределах объема настоящего изобретения, например, соответствующие модификаторам энтропии, выполненным в виде цифрового оборудования, такого как машины с переменным количеством состояний, ASIC и т.п. Инструкции "GetBit", "SetBit" и "ClearBit" в следующих примерах функций всегда используются для обновления значений "HeaderBits". Кроме того, значение "HeaderIndex" также обновляется при достижении следующего бита в следующем байте. В приведенных ниже в качестве примера программах первый бит сохраняется в виде одного кода. Опционально, для улучшения варианта реализации значение первого бита отделяется от упомянутых выше кодов, например, указанных в таблице 3. Соответствующий декодер предпочтительно оптимизируется путем совместной записи нескольких битов в целевой байт, предназначенный для декодированных выходных данных. Следует учитывать, что в следующих примерах вариантов осуществления величина "MaxRun" равна максимальной длине последовательности + 1, например, если максимальная длина последовательности составляет 7 битов, то в приведенных ниже вариантах осуществления значение "AMaxRun", передаваемое в качестве параметра функции, должно равняться 8.
Хотя с помощью способа энтропийного кодирования, например VLC, кодирования методом Хаффмана, арифметического кодирования, интервального кодирования, RLE и т.п., невозможно сжать данные до размера, меньшего того, что позволяет уровень энтропии, без использования некоторых форм предсказания или любой другой дополнительной информации, то есть без потери информации, это не означает, что на практике во всех случаях значительное сжатие данных соответствует наименьшей энтропии; другими словами, на практике энтропия и сжатие данных не представляют собой в точности идентичные концепции. Декодирование кодированных данных для получения их исходного вида всегда требует некоторой дополнительной информации, передача которой иногда приводит к необходимости формирования нежелательного объема специальной информации совместно с фактическими сжимаемыми данными. Если должен обрабатываться большой объем данных, то наименьшая энтропия обычно соответствует наилучшему уровню сжатия данных, однако при необходимости обработки малых объемов данных, такая прямая зависимость в процессе сжатия не всегда соблюдается; например, 1-битовые данные обычно трудно сжать эффективно, и, таким образом, модификаторы 10, 60 энтропии, выполненные с возможностью обработки 1-битовой информации, потенциально являются очень выгодным с коммерческой точки зрения изобретением. Кроме того, обработка данных в формате, который проще поддается сжатию, часто приводит к уменьшению энтропии отформатированных данных по сравнению с соответствующими исходными данными, существовавшими перед применяемыми процессами форматирования.
Как упоминалось выше, часто бывает эффективно передавать значение первого бита в последовательности кодовых слов, представляющих кодированные данные, отдельно от тех значений, которые указывают количество последовательных символов или битов. Однако такая раздельная передача не обязательно должна соответствовать полностью раздельной связи. В последующих примерах, несмотря на раздельную обработку первого бита, все еще остается необходимость добавлять величину первого бита к общему количеству последовательных элементов, поскольку в противном случае было бы невозможно различить приведенные ниже примеры:
и  или
и ,
без обнуления первого элемента, что нежелательно при реализации указанного выше управляющего кода, то есть для использования в том случае, если количество последовательных одинаковых сигналов превышает максимальную длину последовательности в этих примерах.
На фиг. 1 размер данных D2 не обязательно меньше размера данных D1, однако энтропия этих данных меньше, хотя в состав данных D1 и D2 входит одинаковая информация. Размер данных D2 зависит от применяемых длин последовательностей. Например, в составе данных D1 размер элементов данных составляет 1 бит, в то время как размер данных D2 зависит от размера применяемой длины последовательности. Например, если размер данных D1 составляет 104 бита, и энтропия Е=80, то данные D1 могут быть преобразованы модификатором 10 энтропии с использованием максимальной длины последовательности, составляющей 7 элементов, в данные D2, которые содержат 40 элементов, то есть 3-битовых элементов со значением в диапазоне от 0 до 7, с энтропией Е=50; таким образом, объем данных D2 составляет 40*3 бита=120 битов; и в этом примере объем данных D2 больше объема данных D1. В каскаде 20 кодирования предпочтительно используются процессы преобразования VLC, с помощью которых можно сжать данные D2 до 52 битов для формирования данных D3. Таким образом, следует учитывать, что модификаторы 10, 60 энтропии не всегда обеспечивают соответственно сжатие и декомпрессию данных, но способны выполнять эти процессы совместно с другими каскадами кодирования.
Варианты осуществления настоящего изобретения, помимо прочего, предпочтительно реализуются в виде составных частей систем связи, аудиовизуальных потребительских изделий, научного оборудования обработки изображений, вычислительных устройств, беспроводных устройств связи, таких как смартфоны, цифровые камеры, цифровое оборудование наблюдения, интерактивные игровые устройства и т.п. Более высокая степень сжатия данных позволяет уменьшить требуемое пространство на носителях информации, объем потребляемой электроэнергии, а также повысить скорость связи, и все эти факторы следует рассматривать в качестве положительных технических эффектов, например, применимых в указанной области техники. Кроме того, варианты осуществления настоящего изобретения реализуются в виде программных изделий, аппаратуры или любых комбинаций этих средств. Программные изделия могут загружаться в виде прикладных программ, то есть "приложений".
Различные изменения в варианты осуществления настоящего изобретения, описанные выше, могут вноситься в рамках объема настоящего изобретения, определенного прилагаемой формулой изобретения. Такие термины как "включающий", "содержащий", "встроенный", "состоящий из", "имеющий", "представляет собой", используемые в описании и формуле настоящего изобретения, не должны толковаться как исключающие использование блоков, компонентов или элементов, явно не описанных выше. Ссылка на компонент, указанный в единственном числе, также должна допускать толкование, связанное с множеством компонентов. Числовые значения, заключенные в скобки в прилагающейся формуле изобретения, помогают разобраться в пунктах формулы изобретения и никоим образом не должны трактоваться в качестве ограничения предмета изобретения, заявленного посредством этой формулы.