Изменения
Перейти к навигации
Перейти к поиску
Строка 6:
Строка 6: − + − + Строка 14:
Строка 14: − + − + − + Строка 31:
Строка 31: − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + Строка 79:
Строка 79: − + − +
оформление
# Сосчитать <math>M</math> — количество значащих битов в двоичном представлении числа <math>L</math>.
# Сосчитать <math>M</math> — количество значащих битов в двоичном представлении числа <math>L</math>.
# Записать <math>M - 1</math> нулей и одну единицу.
# Записать <math>M - 1</math> нулей и одну единицу.
# Дописать L<sub>2</sub> — <math>M - 1</math> младших битов двоичного представления числа <math>L</math> без старшей единицы (<math>2^{M-1}</math>).
# Дописать <math>L_2</math> — <math>M - 1</math> младших битов двоичного представления числа <math>L</math> без старшей единицы (<math>2^{M-1}</math>).
# Дописать N<sub>2</sub> — <math>L - 1</math> младших битов двоичного представления числа <math>N</math> без старшей единицы (<math>2^{L-1}</math>).
# Дописать <math>N_2</math> — <math>L - 1</math> младших битов двоичного представления числа <math>N</math> без старшей единицы (<math>2^{L-1}</math>).
Иначе этот алгоритм можно описать так:
Иначе этот алгоритм можно описать так:
# Дописать двоичное представление числа <math>N</math> без старшей единицы.
# Дописать двоичное представление числа <math>N</math> без старшей единицы.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты L (разрядности числа — количества значащих битов) и мантиссы N<sub>2</sub> (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты <math>L</math> (разрядности числа — количества значащих битов) и мантиссы <math>N_2</math> (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
Пример кодирования числа 10:
Пример кодирования числа 10:
# В двоичном представлении числа <math>N = 10</math> (1010<sub>2</sub>) 4 значащих бита (<math>L = 4</math>).
# В двоичном представлении числа <math>N = 10 = 1010_2</math> 4 значащих бита (<math>L = 4</math>).
# В двоичном представлении числа <math>L = 4</math> (100<sub>2</sub>) 3 значащих бита (<math>M = 3</math>).
# В двоичном представлении числа <math>L = 4 = 100_2</math> 3 значащих бита (<math>M = 3</math>).
# Записываем <math>M-1 = 2</math> нуля и одну единицу → <code>001</code>.
# Записываем <math>M-1 = 2</math> нуля и одну единицу → <code>001</code>.
# Дописывем биты числа <math>L</math> без старшей единицы → <code>00</code>.
# Дописывем биты числа <math>L</math> без старшей единицы → <code>00</code>.
!colspan="2" rowspan="2"| N ||colspan="2" rowspan="2"| L ||rowspan="2"| M ||colspan="2"| Дельта-код ||rowspan="2"| Длина,<br />бит ||rowspan="2"| Предполагаемая<br />вероятность ||colspan="2"| Гамма-код ||rowspan="2"| Длина,<br />бит
!colspan="2" rowspan="2"| N ||colspan="2" rowspan="2"| L ||rowspan="2"| M ||colspan="2"| Дельта-код ||rowspan="2"| Длина,<br />бит ||rowspan="2"| Предполагаемая<br />вероятность ||colspan="2"| Гамма-код ||rowspan="2"| Длина,<br />бит
|-align="center"
|-align="center"
! γ(L) || N<sub>2</sub> || L || N<sub>2</sub>
! γ(L) || <math>N_2</math> || <math>L</math> || <math>N_2</math>
|-
|-
| 1 || 1<sub>2</sub> || 1 || 1<sub>2</sub> || 1 || 1 ||align="left"| || 1 || 1/2 || 1 ||align="left"| || 1
| 1 || <math>1_2</math> || 1 || <math>1_2</math> || 1 || 1 ||align="left"| || 1 || 1/2 || 1 ||align="left"| || 1
|-
|-
| 2 || 10<sub>2</sub> || 2 || 10<sub>2</sub> || 2 || 01 0 ||align="left"| 0 || 4 || 1/16 || 01 ||align="left"| 0 || 3
| 2 || <math>10_2</math> || 2 || <math>10_2</math> || 2 || 01 0 ||align="left"| 0 || 4 || 1/16 || 01 ||align="left"| 0 || 3
|-
|-
| 3 || 11<sub>2</sub> || 2 || 10<sub>2</sub> || 2 || 01 0 ||align="left"| 1 || 4 || 1/16 || 01 ||align="left"| 1 || 3
| 3 || <math>11_2</math> || 2 || <math>10_2</math> || 2 || 01 0 ||align="left"| 1 || 4 || 1/16 || 01 ||align="left"| 1 || 3
|-
|-
| 4 || 100<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 00 || 5 || 1/32 || 001 ||align="left"| 00 || 5
| 4 || <math>100_2</math> || 3 || <math>11_2</math> || 2 || 01 1 ||align="left"| 00 || 5 || 1/32 || 001 ||align="left"| 00 || 5
|-
|-
| 5 || 101<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 01 || 5 || 1/32 || 001 ||align="left"| 01 || 5
| 5 || <math>101_2</math> || 3 || <math>11_2</math> || 2 || 01 1 ||align="left"| 01 || 5 || 1/32 || 001 ||align="left"| 01 || 5
|-
|-
| 6 || 110<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 10 || 5 || 1/32 || 001 ||align="left"| 10 || 5
| 6 || <math>110_2</math> || 3 || <math>11_2</math> || 2 || 01 1 ||align="left"| 10 || 5 || 1/32 || 001 ||align="left"| 10 || 5
|-
|-
| 7 || 111<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 11 || 5 || 1/32 || 001 ||align="left"| 11 || 5
| 7 || <math>111_2</math> || 3 || <math>11_2</math> || 2 || 01 1 ||align="left"| 11 || 5 || 1/32 || 001 ||align="left"| 11 || 5
|-
|-
| 8 || 1000<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 000 || 8 || 1/256 || 0001 ||align="left"| 000 || 7
| 8 || <math>1000_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 000 || 8 || 1/256 || 0001 ||align="left"| 000 || 7
|-
|-
| 9 || 1001<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 001 || 8 || 1/256 || 0001 ||align="left"| 001 || 7
| 9 || <math>1001_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 001 || 8 || 1/256 || 0001 ||align="left"| 001 || 7
|-
|-
| 10 || 1010<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 010 || 8 || 1/256 || 0001 ||align="left"| 010 || 7
| 10 || <math>1010_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 010 || 8 || 1/256 || 0001 ||align="left"| 010 || 7
|-
|-
| 11 || 1011<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 011 || 8 || 1/256 || 0001 ||align="left"| 011 || 7
| 11 || <math>1011_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 011 || 8 || 1/256 || 0001 ||align="left"| 011 || 7
|-
|-
| 12 || 1100<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 100 || 8 || 1/256 || 0001 ||align="left"| 100 || 7
| 12 || <math>1100_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 100 || 8 || 1/256 || 0001 ||align="left"| 100 || 7
|-
|-
| 13 || 1101<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 101 || 8 || 1/256 || 0001 ||align="left"| 101 || 7
| 13 || <math>1101_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 101 || 8 || 1/256 || 0001 ||align="left"| 101 || 7
|-
|-
| 14 || 1110<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 110 || 8 || 1/256 || 0001 ||align="left"| 110 || 7
| 14 || <math>1110_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 110 || 8 || 1/256 || 0001 ||align="left"| 110 || 7
|-
|-
| 15 || 1111<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 111 || 8 || 1/256 || 0001 ||align="left"| 111 || 7
| 15 || <math>1111_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 111 || 8 || 1/256 || 0001 ||align="left"| 111 || 7
|-
|-
| 16 || 10000<sub>2</sub> || 5 || 101<sub>2</sub> || 3 || 001 01 ||align="left"| 0000 || 9 || 1/512 || 00001 ||align="left"| 0000 || 9
| 16 || <math>10000_2</math> || 5 || <math>101_2</math> || 3 || 001 01 ||align="left"| 0000 || 9 || 1/512 || 00001 ||align="left"| 0000 || 9
|-
|-
| 17 || 10001<sub>2</sub> || 5 || 101<sub>2</sub> || 3 || 001 01 ||align="left"| 0001 || 9 || 1/512 || 00001 ||align="left"| 0001 || 9
| 17 || <math>10001_2</math> || 5 || <math>101_2</math> || 3 || 001 01 ||align="left"| 0001 || 9 || 1/512 || 00001 ||align="left"| 0001 || 9
|}
|}
# Прочитать из потока <tt>001</tt> и определить, что в начале 2 ведущих нуля (<math>M = 2</math>).
# Прочитать из потока <tt>001</tt> и определить, что в начале 2 ведущих нуля (<math>M = 2</math>).
# Прочитать из потока следующие <math>M = 2</math> бита → <tt>01</tt>; это даёт <math>L = 2^M +</math> 01<sub>2</sub> <math>= 4 + 1 = 5</math>.
# Прочитать из потока следующие <math>M = 2</math> бита → <tt>01</tt>; это даёт <math>L = 2^M + 01_2 = 4 + 1 = 5</math>.
# Прочитать из потока следующие <math>L-1 = 4</math> бита → <tt>0001</tt>; это даёт <math>N = 2^{L-1}</math> + 0001<sub>2</sub> <math>= 16 + 1 = 17</math>.
# Прочитать из потока следующие <math>L-1 = 4</math> бита → <tt>0001</tt>; это даёт <math>N = 2^{L-1} + 0001_2 = 16 + 1 = 17</math>.
== Эффективность ==
== Эффективность ==