Устройство и способ для кодирования и декодирования исходных данных

Устройство и способ для кодирования и декодирования исходных данных

Иллюстрации

Показать все

Реферат

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

Раскрытие настоящего изобретения относится к способам кодирования данных (D1) для генерации соответствующих кодированных данных (Е2). Кроме того, раскрытие настоящего изобретения также относится к способам декодирования указанных выше кодированных данных (Е2) для генерации соответствующих декодированных данных (D3) и/или перекодированной версии декодированных данных (D3). Помимо этого, раскрытие настоящего изобретения также относится к кодерам и декодерам, которые способны реализовать указанные выше способы и совместно образуют кодеки. Дополнительно раскрытие настоящего изобретения относится к компьютерным программным изделиям, содержащим машиночитаемый носитель информации, на котором хранятся машиночитаемые инструкции, исполняемые вычислительным устройством для выполнения указанных выше способов.

ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ

На обзорной схеме, показанной на фиг. 1, известные кодеру 20 способы кодирования входных данных (D1) 10 для генерации соответствующих кодированных выходных данных (Е2) 30 задействуют один или более процессов 40а, 40b преобразования, применяемых к входным данным (D1) 10, для генерации соответствующих кодированных преобразованных данных 50, которые связаны с данными 60 кодовых таблиц, определяющих одну или более кодовых таблиц, задающих один или более используемых процессов преобразования. Кодированные преобразованные данные 50 и данные 60 кодовых таблиц, в комбинации образующие кодированные выходные данные (Е2) 30, часто с помощью носителя данных и/или через сеть передачи данных передаются в один или более декодеров 80, которые способны декодировать кодированные выходные данные (Е2) 30 с целью генерации соответствующих декодированных данных (D3) 90. Дополнительно декодированные данные (D3) представляют собой восстановленную версию данных (D1), однако не ограничены только этой версией, например, если выполняется перекодирование в одном или более декодеров 80. Во многих случаях желательно, чтобы кодированные выходные данные (Е2) 30 сжимались относительно входных данных (D1) 10. Кроме того, желательно, чтобы кодированные выходные данные (Е2) 30 сжимались по существу без потерь, так чтобы декодированные данные (D3) 90 как можно точнее воспроизводили входные данные D1 (10). Достижимая степень сжатия кодированных выходных данных (Е2) 30 относительно входных данных (D1) 10 потенциально недостаточна, если данные 60 таблиц кодирования занимают значительный объем по отношению к кодированным преобразованным данным 50, то есть данные 60 таблиц кодирования соответствуют значительному объему служебных данных. В определенных известных реализациях кодера 20 в состав данных 60 кодовых таблиц входит информация, указывающая частоты, вероятности или диапазоны кодированных "символов", присутствующих в кодированных преобразованных данных 50, которые являлись исходными символами во входных данных (D1) 10. Данные 60 кодовых таблиц не ограничены только этими перечисленными данными. Дополнительно данные 60 кодовых таблиц также содержат информацию, относящуюся к используемым способам преобразования и их параметрам.

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

Базовая реализация интервального (диапазонного) кодека описывается, например, на сайте Википедии, на странице, посвященной интервальному (диапазонному) кодированию [Интервальное кодирование - Википедия, свободная энциклопедия (по состоянию на 13 декабря 2013 года), URL: http://en.wikipedia.org/wiki/Ranqe encoding]. В этой базовой реализации используется по меньшей мере один символ <EOM> (End-Of-Message, конец сообщения). Арифметическое кодирование, URL: http://en.wikipedia.org/wiki/Arithmetic coding, очень напоминает интервальное кодирование, однако в этом варианте кодирования используется одно число с плавающей запятой [0,1] и символ <EOD> (End-Of-Data, конец данных). Кроме того, интервальное кодирование широко используется в тех приложениях, в которых требуется сжатие данных, таких как кодирование видеосигналов и изображений. Оно очень эффективно при кодировании наборов данных большого объема, если известны вероятности различных возможных символов. Однако если характер данных, подлежащих кодированию, таков, что вероятности символов заранее неизвестны в одном или более декодерах 80, то необходимо передавать вероятности символов совместно с кодированными данными (Е2) 30. В противном случае эффективность сжатия при интервальном кодировании значительно снижается.

Доставка значений частоты, вероятности или диапазона требует включения дополнительных данных, то есть "расходования данных", что влияет на общую эффективность сжатия, достижимую в кодере 20. Кроме того, повышенная эффективность сжатия при интервальном кодировании достигается, если передаются более точные значения частот, вероятностей или диапазона символов. Однако передача очень точных значений частот, вероятностей или диапазона требует большего объема данных. Другими словами, должен соблюдаться компромисс между передачей точных значений частот, вероятностей или диапазона для символов и достижением максимально возможной эффективности сжатия в кодированных данных (Е2).

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

В ранее опубликованном европейском патентном документе ЕР 0166607 А2 (King Reginald Alfred) описывается способ, согласно которому сжатие в сеансах передачи выборок (звуковых) данных, в частности символов с временным кодированием (TES, Time Encoded Symbol), потенциально улучшается путем представления битов нелинейным образом (в виде кодов переменной длины) вместо линейного представления (в виде кодов фиксированной длины). Способ использует первичные коды для доставки из кодера в декодер порядка вероятности появлений элементов. То есть, согласно этому способу по мере поступления элементов передаются не сами вероятности, а только их порядок.

В более раннем патенте США №6650996 В1 (Garmin Ltd.) описываются системы, устройства и способы, применяющие структуру данных, в которой используются первое поле данных, определяющее структуру декодирования данных, кодированных с помощью канонического способа Хаффмана, и второе поле данных, определяющее таблицу символов. Кроме того, таблица символов адаптируется для предоставления символа, связанного с низкочастотным индексом.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

Настоящее изобретение также направлено на реализацию усовершенствованного кодера, выполняющего указанный выше усовершенствованный способ.

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

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

Далее более подробно объясняется предшествующее выражение "включена ли информация, указывающая…"

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

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

Кроме того, усовершенствованный способ, соответствующий первому аспекту, может использоваться с применением или без применения одного или более символов <EOM>, которые служат для указания "конца сообщения'". Во всех примерах вариантов осуществления настоящего изобретения, описываемых далее, один или более символов <EOM> не используются, однако один или более символов <EOM> могут дополнительно включаться во все примеры осуществления путем применения для них, например, значения 1 вероятности с последующим вычитанием 1 из любого другого значения вероятности. Такое решение не требует доставки нового значения вероятности, поскольку значение вероятности уже известно. Вероятность символа <EOM> также может дополнительно вычисляться на основе количества символов данных. Если вероятность вычисляется, символ <EOM> добавляется в таблицу вероятностей и ему присваивается значение 1 частоты. Сумма частот также увеличивается на 1, и это влияет на вероятности всех символов. Для этого также требуется, чтобы дополнительное значение вероятности доставлялось для символа <EOM>.

Усовершенствованный способ, соответствующий первому аспекту, может использоваться для кодирования данных любого типа, поэтому он характеризуется широкой областью потенциального применения; к таким "данным любого типа", подлежащим кодированию, дополнительно относятся, помимо прочего, данные одного или более следующих типов: данные генетических последовательностей, данные последовательностей ДНК, данные последовательностей РНК, захваченные звуковые сигналы, захваченные видеосигналы, захваченные изображения, текстовые данные, сейсмографические данные, сигналы датчиков, данные, преобразованные из аналоговой в цифровую форму (ADC, Analog-To-Digital), данные биомедицинского сигнала, календарные данные, экономические данные, математические данные, двоичные данные. Согласно усовершенствованному способу другой способ модификации вероятностей заключается в использовании адаптивных вероятностей и диапазонов при кодировании данных для генерации соответствующих кодированных данных. Адаптивные вероятности удобно применять для кодирования больших по объему потоков данных, в особенности, если вероятности символов изменяются переменным образом, но медленно, в различных частях потока данных. Однако адаптивные вероятности менее удобны для меньших потоков данных, поскольку для адаптации вероятностей с целью согласования с корректными вероятностями символов в потоке данных требуются дополнительные вычислительные ресурсы и время.

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

Дополнительно в декодере выполняется перекодирование для переформатирования декодированных в нем данных, например, с целью предоставления совместимых данных устройству визуализации декодера или устройству хранения данных декодера. Согласно усовершенствованному способу используется битовая информация в виде 0 и 1 для описания, требуется ли доставка значения диапазона, значения вероятности или значения частоты для различных символов, которые могут присутствовать среди символов потока данных. Этот усовершенствованный способ дополнительно также использует одно или более пороговых значений вероятности для определения, какие символы требуют своего собственного доставляемого значения вероятности, то есть бит 1, и для каких символов вероятность может быть пропущена, например, с использованием бита 0. Дополнительно для всех символов данных с пропускаемой вероятностью может использоваться значение 1 вероятности в кодере и в декодере. В альтернативном варианте все те символы данных, для которых не требуется свое собственное значение частоты или вероятности, то есть диапазона, дополнительно поставляются с управляющим символом (escape symbol), то есть диапазоном, в схеме интервального кодирования. Кроме того, все значения символов с пропускаемой вероятностью дополнительно доставляются, например, в виде исходных несжатых значений.

Далее более подробно разъясняются следующие концепции (i)-(iii):

(i) "кодируемый символ известен", или

(ii) в кодере: "включается ли информация, указывающая частоту, вероятность или диапазон для по меньшей мере одного символа из одного или более символов, включенных в кодированные данные", или

(iii) в декодере: "какие символы кодированные в кодированных данных должны декодироваться с использованием информации о частоте, вероятности или диапазоне".

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

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

4, 3, 0, 1, 0, 4, 3, 4

Фактический максимальный индекс равен 4 (а минимальный индекс равен 0), это означает, что в данных может содержаться 5 (максимальное значение - минимальное значение + 1=4-0+1) различных символов (0, 1, 2, 3, 4). С учетом того, что в данных D1 в действительности существуют только четыре различных символа (0, 1, 3, 4), таблица также может доставляться с использованием значения '3' в качестве максимального индекса, а именно: количества доступных различных символов, вместо 4 возможных различных символов. Если значение '3' использовано в качестве максимального значения индекса таблицы, то некоторый другой механизм дополнительно применяется для доставки информации о том, какие символы используются для каждого из индексов таблицы.

Эти способы более подробно разъясняются в других частях раскрытия настоящего изобретения. Если символы упорядочены, то одной из возможностей является доставка фактического максимального индекса (4) и битов доступности, (например, 11011 в данном случае). В результате такого вида доставки выполняется преобразование вида "индекс 0 таблицы = символ 0", который называется индексом, и связанная пара символов равна (0, 0). Таким же образом, оставшиеся пары индексов и символов представляют собой следующую последовательность: (1, 1), (2, 3) и (3, 4). Кроме того, можно использовать пары индексов и символов непосредственно с целью определения используемых индексов для различных индексов таблицы и затем доставлять максимальный индекс таблицы, равный 3, или количество различных пар индексов и символов, равное 4. При использовании такого способа индексы кодовой таблицы обычно упорядочены, и необходимо доставлять только символы. Такой способ в значительной степени предпочтительно применять, если символы в доставляемой таблице отсортированы на основе своих частот.

Например, в этом случае пары индексов и символов могут представлять собой следующую последовательность: (0, 4), (1, 0), (2, 3) и (3, 1), и в определенном порядке доставляются только значения 4, 0, 3, 1. В некоторых ситуациях:

(a) эти используемые пары индексов и символов определены предварительно;

(b) иногда доставляется индекс таблицы пар используемых символов и индексов, в других случаях доставляются пары индексов и символов совместно с кодированными данными;

(c) в некоторых других случаях декодер может извлечь пары используемых символов и индексов из известного местоположения, и

(d) в иных ситуациях декодер может извлечь пары используемых индексов и символов из местоположения, информация о котором доставляется с кодированными данными.

Частоты частей данных, подлежащих кодированию в кодере, применяющем указанный выше усовершенствованный способ, соответствующий первому аспекту, часто взаимно различны, и часто их относительная энтропия данных также взаимно различна, по этой причине при кодировании полезно разделять, то есть подразделять, данные на множество частей для генерации кодированных данных (Е2). Преимущественно для различных частей используются различные кодовые таблицы. Усовершенствованный способ позволяет, например, один большой фрагмент данных более эффективно разделить на меньшие части, то есть на меньшие фрагменты данных, поскольку при этом оптимизируется доставка кодовой или таблицы частот. Такое разделение данных, подлежащих кодированию, позволяет получить значительные преимущества в том, что касается энтропии данных (D1), подлежащих кодированию, и, таким образом, при разделении возможно обеспечить боле высокую степень сжатия кодированных данных (Е2) по отношению к соответствующим некодированным данным (D1).

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

Дополнительно в кодере информация, указывающая частоту, вероятность или диапазон одного или более символов, представленных в кодированных данных (Е2), динамически изменяется кодером как функция от характера, то есть характеристик данных (D1), подлежащих кодированию; к таким характеристикам дополнительно относятся следующие характеристики: структура данных (D1), размер данных (D1), диапазон значений, представленных в данных (D1), размер элементов, представленных в данных (D1), метаданные, связанные с данными (D1). Кроме того, такие характеристики относятся, например, к типу данных (D1), содержимому данных (D1) и/или к статистическим показателям данных (D1). Кроме того, дополнительно кодер способен подразделять эти подлежащие кодированию данные (D1) на множество частей и генерировать индивидуально для каждой части соответствующую дополнительную информацию о том, включена ли в кодированные данные (Е2) информация, указывающая частоту, вероятность или диапазон для по меньшей мере одного из одного или более символов.

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

В соответствии со вторым аспектом предлагается способ кодирования данных (D1) в кодере для генерации соответствующих кодированных данных (Е2), содержащих информацию, указывающую частоту, вероятность или диапазон одного или более символов, представленных в кодированных данных (Е2), при этом способ включает:

(a) использование кодера для включения в кодированные данные (Е2) дополнительной информации о том, включена ли в кодированные данные (Е2) информация, указывающая частоту, вероятность или диапазон для по меньшей мере одного символа из одного или более символов.

Дополнительно способ также включает:

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

Кроме того, способ дополнительно также включает:

(c) использование кодера для сообщения о включении информации, указывающей на наличие в кодированных данных (Е2) информации о частоте, вероятности или диапазоне, путем использования одного битового значения "1" доступности и сообщения о том, что информация о частоте, вероятности или диапазоне в кодированных данных (Е2) отсутствует, путем использования одного битового значения "0" доступности. Дополнительно для указания такой информации о доступности или недоступности значения "0" и "1" могут использоваться наоборот.

Дополнительно способ включает использование кодера для динамического изменения информации, указывающей частоту, вероятность или диапазон одного или более символов, представленных в кодированных данных (Е2), в зависимости от характера, то есть одной или более характеристик данных (D1), подлежащих кодированию. Предшествующая ссылка в данном случае относится к определению "характера" и "характеристик" как технических терминов.

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

Дополнительно способ включает кодирование данных (D1), соответствующих по меньшей мере одному из следующих типов: данные генетических последовательностей, захваченные звуковые сигналы, захваченные видеосигналы, захваченные изображения, текстовые данные, сигналы датчиков, без ограничения приведенными примерами. Данные генетических последовательностей при генерации прибором для электрофореза из биологических образцов часто занимают значительный объем, достигающий порядка 1 терабайта данных, определяющих гетероциклические основания нуклеиновой кислоты и/или аминокислоты. Обработка и передача таких данных представляет собой в настоящее время существенную техническую проблему.

В соответствии с третьим аспектом предлагается декодер для декодирования кодированных данных (Е2), генерированных кодером, соответствующим первому аспекту.

В соответствии с четвертым аспектом предлагается способ декодирования кодированных данных (Е2) в декодере, включающий выполнение инверсии шагов способа, соответствующего второму аспекту.

Дополнительно способ включает:

(a) прием сигнала доступности;

(b) прием переданных частот, вероятностей или таблицы диапазонов в кодированных данных (Е2);

(c) построение полной таблицы частот, таблицы вероятностей или таблицы диапазонов на основе данных, полученных на шагах (а) и (b); и

(d) использование полной таблицы частот, таблицы вероятностей или таблицы диапазонов для интервального декодирования кодированных данных (Е2) с целью генерации декодированных выходных данных (D3).

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

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

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

Согласно пятому аспекту предлагается кодек, содержащий по меньшей мере один кодер, соответствующий первому аспекту, и по меньшей мере один декодер, соответствующий третьему аспекту.

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

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

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

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

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

на фиг. 1 показана схема кодера, способного кодировать входные данные (D1) для генерации соответствующих кодированных выходных данных (Е2), и соответствующего декодера, способного декодировать кодированные данные (Е2) для генерации соответствующих декодированных данных (D3);

на фиг. 2 показан алгоритм способа кодирования данных, соответствующий раскрытию настоящего изобретения; и

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

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

ОПИСАНИЕ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ

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

Если в кодере реализовано интервальное кодирование, то индекс таблицы частот, индекс таблицы вероятностей или индекс таблицы диапазонов, или значения частот, вероятностей или диапазонов передаются в кодированных данных (Е2), генерированных кодером, с использованием некоторой заданной точности, если эти значения не известны в соответствующем кодере заранее; дополнительно кодер способен динамически переключаться между использованием индекса таблицы частот, индекса таблицы вероятности, индекса таблицы диапазонов, значениями частот, значениями вероятностей и значениями диапазона в зависимости от взаимно различных частей данных (D1), подлежащих кодированию. Например, если в интервальном кодеке кодируются восьмибитовые данные, то потенциально формируются 2⁸ символов, то есть 256 символов. Если для передачи каждого значения частоты, вероятности или диапазона используется восемь бит, то есть один байт, то для передачи всех значений частот, вероятностей или диапазонов потребуется 256 байт. В некоторых случаях значение 256 байт потенциально превышает объем сжатых данных, полученных из интервального кодера, следовательно, существует ярко выраженная необходимость использования меньшего количества битов для доставки значений частот, вероятностей или диапазона; другими словами, при доставке из кодера в декодер значений частот, вероятностей или диапазона задействованы избыточные данные, объем которых потенциально больше размера данных, подлежащих кодированию, что соответствует низкому уровню коэффициента сжатия.

Способы кодирования данных (D1), соответствующие раскрытию настоящего изобретения, отличаются от известных способов тем, что помимо значений частот, вероятностей или диапазона символов также передается сигнал доступности, например один бит доступности для каждого символа. Преимущественно этому биту доступности присваивается значение "один" то есть "1" для всех символов, представленных в кодированных данных (Е2) и имеющих достаточно высокую вероятность, и присваивается значение "ноль" то есть "0" для всех символов, не представленных в кодированных данных (Е2), а также для всех символов, представленных в кодированных данных (Е2), но имеющих относительно низкую вероятность.

Согласно способам кодирования данных (D1), соответствующим раскрытию настоящего изобретения, осуществляется проверка, достаточно ли мала вероятность символа, например, путем сравнения вероятности символа с пороговым значением или, дополнительно, с несколькими пороговыми значениями. При кодировании символам, отсутствующим в кодированных данных (Е2), или символам с вероятностью, меньшей порогового значения, назначается вероятность 'ноль' (используется управляющий код, и для символа диапазон не предусматривается) или 'один' (то есть, маловероятные символы доставляются с наименьшим возможным диапазоном), то есть '0' или '1' независимо от размера всего диапазона, используемого для кодирования входных данных (D1) 10, предоставляемых кодеру 20 для генерации кодированных данных (Е2) 30; то же относится к ситуации, когда кодер 20 и один или более декодеров 80 применяют усовершенствованный способ (Т) и обратный ему способ ("М), соответственно. Объем А (в битах) кодированных данных, требуемый для передачи частот, вероятностей или диапазонов и сигнала доступности (например, битов доступности в этом примере), составляет количество Ns символов, присутствующих или доступных в кодированных данных (Е2), с достаточно высокой вероятностью, умноженное на количество N_B битов, используемое для каждого значения частоты, вероятности или диапазона, плюс один бит доступности для всех символов O_s; другими словами:

Следующий пример усовершенствованного способа, соответствующего раскрытию настоящего изобретения, применяется в кодере 20 для кодирования значений набора данных, представленных в виде входных данных (D1) 10, для генерации соответствующих кодированных данных (Е2) 30. В этом примере поток кодируемых данных (D1) содержит 150 значений данных, которые могут содержать 20 символов (= значений), а именно: от 0 до 19, но только 8 из этих 20 возможных значений данных, а именно: минимальное значение =2 и максимальное значение =19, фактически представлены в текущем потоке данных. Эти минимальное и максимальное значения дополнительно также доставляются в соответствии, например, со способом ODelta-кодирования, раскрытым в заявке на патент GB1303661.1, поданной Gurulogic Microsystems Оу 1-го марта 2013 года; "ODelta-кодирование" относится к способу дельта-кодирования с использованием вычислений со смещением и циклическим переходом для обеспечения в особенности эффективного кодирования данных. Этот способ позволяет сократить некоторое количество битов, требуемых для доставки сигнала доступности. Кроме того, в этом случае также уменьшается диапазон данных значений возможно доступных символов при использовании некоторого способа модификации энтропии, такого, например, как ODelta-кодирование, перед применением интервального кодирования. Основное преимущество, связанное с доставкой минимального и максимального значений, достигается, если все способы кодирования с модификацией энтропии и интервального кодирования используют одинаковую информацию, которая доставляется из кодера в соответствующий декодер только один раз. Ниже в Табл. 1 показан пример частот и вероятностей символов. Вероятность вычисляется путем деления частоты на общее количество значений данных.

В Табл. 1 существует пара символов с очень низкой вероятностью появления. В случае использования 7 бит для доставки вероятностей, если бы применялось одинаковое количество битов для описания каждой вероятности, то потребовалось бы 20*7=140 бит для представления всех вероятностей. Если наличие символов в потоке, то есть в кодированных данных (Е2) 30, выражается путем передачи, например, одного бита доступности для символа, то требуется еще 8*7+20*1=76 бит для представления всех вероятностей.

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