Гамма-, дельта- и омега-код Элиаса — различия между версиями
Анна (обсуждение | вклад) (→Разделение мантисс и экспонент) |
Анна (обсуждение | вклад) (→Разделение мантисс и экспонент) |
||
Строка 11: | Строка 11: | ||
Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту" <tex>E_i</tex>) и отдельно {{---}} значащие цифры значения ("мантиссу" <tex>M_i</tex>). | Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту" <tex>E_i</tex>) и отдельно {{---}} значащие цифры значения ("мантиссу" <tex>M_i</tex>). | ||
− | Значащие цифры начинаются со старшей ненулевой цифры: например, в числе <tex>000001101_2</tex>= <tex>1\times2^0+0\times2^1+1\times2^2+1\times2^3+0\times2^4+0\times...</tex> = 13 это последние 4 цифры. | + | Значащие цифры начинаются со старшей ненулевой цифры: например, в числе <tex>000001101_2</tex> = <tex>1\times2^0+0\times2^1+1\times2^2+1\times2^3+0\times2^4+0\times...</tex> = 13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем. |
+ | |||
+ | Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов. | ||
+ | |||
+ | В самом простом случае под запись экспонент и мантисс отводится фиксированное число битов: Е и М. Причем <tex>Е \geqslant 1</tex>, М >= 1, E + M=R, где R - число битов в записи исходного числа. |
Версия 23:40, 26 ноября 2014
Коды без памяти
Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.
К примеру, множество двоичных слов
= является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций ( , ) из , то видно, что никогда не явится префиксом (или началом) . С другой стороны, множество = не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества — 001. Соответственно, множество может быть множеством кодовых слов для вектора данных в коде без памяти, а — нет.Разделение мантисс и экспонент
Английское название метода - Separate Exponents and Mantissas (SEM).
Цель — сжатие потока R-битовых элементов.
Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту"
) и отдельно — значащие цифры значения ("мантиссу" ).Значащие цифры начинаются со старшей ненулевой цифры: например, в числе
= = 13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем.Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов.
В самом простом случае под запись экспонент и мантисс отводится фиксированное число битов: Е и М. Причем
, М >= 1, E + M=R, где R - число битов в записи исходного числа.