Изменения

|definition ='''Унарное представление числа <tex>n </tex> ''' (англ. ''unary code'') {{---}} <tex>n </tex> подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: <tex>n </tex> нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.}}Например, унарный код нуля {{---}} <tex>0</tex>, единицы {{---}} <tex>10</tex>, двойки {{---}} <tex>110 </tex> и т. д.

1. Выделить из целого числа старший значащий бит (самую большую степень <tex>2</tex>, которую число включает — 2N<tex>2\timesN</tex>) и младшие <tex>N </tex> бит;

2. Записать <tex>N </tex> в унарном коде, то есть <tex>N </tex> нулей, за которыми следует единица;

3. Дописать <tex>N </tex> младших двоичных цифр числа следом за этим унарным кодом.

1. Считать все нули, встречающиеся до первой <tex>1</tex>. Пусть <tex>N </tex> — количество этих нулей;

2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением <tex>2^N</tex>, считать оставшиеся <tex>N </tex> цифр целого числа.

''' Пример кодирования числа <tex>15 </tex> '''

1. Записать число <tex>15 </tex> в двоичном представлении <tex>1111_2</tex>;

2. Дописать перед числом три нуля '''<tex>0001111</tex>'''.

''' Пример декодирования последовательности битов <tex>000010001 </tex> '''

1. Считываем нули до первой единицы, <tex>N = 4</tex>;

2. Считываем единицу и <tex>N = 4 </tex> бит. Получаем <tex>2^4</tex> + <tex>0001_2</tex> = '''<tex>17</tex>'''.

Гамма-код Элиаса не подходит для кодирования нулевых значений или отрицательных чисел. Для того, чтобы закодировать ноль нужно прибавить к нему <tex>1 </tex> до кодирования и отнять после декодирования. Чтобы закодировать все целые числа можно установить биекцию (соответствие), отображая целые числа из <tex>(0, 1, −1, 2, −2, 3, −3, …) </tex> в <tex>(1, 2, 3, 4, 5, 6, 7, …)</tex>.

1. Сосчитать <tex>L </tex> {{---}} количество значащих битов в двоичном представлении числа <tex>N</tex>;

2. Сосчитать <tex>M </tex> {{---}} количество значащих битов в двоичном представлении числа <tex>L</tex>;

3. Записать <tex>M </tex> {{---}} <tex>1 </tex> нулей и одну единицу;

4. С правой стороны дописать биты числа <tex>L </tex> без старшей единицы;

5. С правой стороны дописать биты числа <tex>N </tex> без старшей единицы (<tex>N_2</tex>).

1. Сосчитать <tex>L </tex> {{---}} количество значащих битов в двоичном представлении числа <tex>N</tex>;

2. Закодировать <tex>L </tex> с помощью гамма-кода Элиаса;

3. Дописать к <tex>L </tex> справа двоичное представление числа <tex>N </tex> без старшей единицы.

1. Сосчитать <tex>M </tex> {{---}} количество нулей во входном потоке до первой единицы;

2. Не включая единицу считать <tex>M </tex> битов. Считанное число в сумме с <tex>2^M</tex> дает <tex>L</tex>;

3. Далее идут <tex>L {{---}} 1 </tex> младших битов числа <tex>N</tex>. Считать их и к считанному числу прибавить <tex>2^{L-1}</tex>.

'''Пример кодирования числа <tex>10</tex>'''

1. В двоичном представлении числа <tex>N = 10 = <tex>1010_24</tex> 4 значащих бита <tex>(L = 4)</tex>;

2. В двоичном представлении числа <tex>L = 4 = <tex>100_23</tex> 3 значащих бита <tex>(M = 3)</tex>;

3. Пишем <tex>M {{---}} 1 </tex> ноль и одну единицу <tex>001</tex>;

4. Дописываем справа биты числа <tex>L </tex> без старшей единицы <tex>00100</tex>;

5. Дописываем с правой стороны биты числа <tex>N </tex> без старшей единицы '''<tex>00100010</tex>'''.

'''Пример декодирования последовательности битов <tex>00100010</tex>'''

1. Считаем количество нулей до первой единицы во входном потоке <tex>(M = 2);<tex>

2. Читаем из потока следующие <tex>M </tex> бит <tex>(00)</tex>. Это дает нам L = <tex>L = 2^M</tex> + <tex>00_2</tex> = 4;

3. Читаем из потока следующие <tex>L {{---}} 1 </tex> бит <tex>(010)</tex>. N = <tex>N = 2^{L- 1}</tex> + <tex>010_2</tex> = '''10'''</tex>.

Для диапазона [<tex>[2^K</tex>,<tex>2^{K+1}- 1]</tex>- 1 ] коды формируются следующим образом:

'''Гамма-код''': <tex>00..(К </tex> раз<tex>)..01x..(К </tex> раз<tex>)..x</tex>; длина <tex>2\times{K} + 1</tex> бит;

'''Дельта-код''': <tex>n...(<tex>2\times{L}+1</tex> раз<tex>)...nx..(K </tex> раз<tex>)..x</tex>; длина: <tex>2\times{L}+K+1</tex> бит, где L = <tex>L = [\log_2{(K+1)}]</tex> - целая часть логарифма числа <tex>(K+1) </tex> по основанию <tex>2</tex>; <tex>n </tex> - биты, относящиеся к записи экспоненты дельта-кода, их число <tex>2\times{L} + 1</tex>.

Можно видеть, что для чисел <tex>2, 3, 8…15 </tex> дельта-код длиннее гамма-кода, для чисел <tex>1, 4…7, 16…31 </tex> длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода.

Данные коды состоят из последовательности групп длинной <tex>L_1, L_2, L_3, …, L_m</tex> бит, которые начинаются (слева) с бита <tex>1</tex>. В конце последовательности (справа) всегда <tex>0</tex>. Длина каждой следующей <tex>(n+1)</tex>-й группы задается значением битов предыдущей <tex>n</tex>-й группы.

В омега-кодах Элиаса длина первой группы — {{---}} <tex>2 </tex> бита. Длина следующей группы на единицу больше значения предыдущей. Первое значение задается отдельно.

1. В конец представления записать <tex>0</tex>;

2. Если число не единица <tex>(N <> 1)</tex>, слева от построенной последовательности добавить его двоичное представление;

3. В <tex>N </tex> записать новое значение - количество только что записанных цифр(бит), минус один;

1. Записываем в переменную <tex>N </tex> единицу;

2. Считываем первый слева бит. Если он равен единице, то считываем группу бит длиной <tex>(N + 1)</tex>. Записываем в <tex>N </tex> число, двоичное представление которого равно этой группе бит. Если он равен нулю, то <tex>N </tex> и есть наше число;

'''Пример кодирования числа <tex>N = 12</tex>'''

1. Записываем <tex>0</tex>;

2. Добавляем справа от нуля двоичное представление <tex>12 (1100 0)</tex>;

3. <tex>N = 4 - 1 = 3 </tex> (длина последовательности <tex>1100 </tex> минус <tex>1</tex>);

4. Добавляем справа двоичное представление <tex>N (11 1100 0)</tex>;

5. <tex>N = 1</tex>, значит <tex>12 </tex> кодирует последовательность '''<tex>11 1100 0</tex>'''.

'''Пример декодирования последовательности <tex>10 100 10001 0</tex>'''

1. <tex>N = 1</tex>;

2. Считываем группу <tex>10. N = 2</tex>;

3. Считываем группу <tex>100. N = 4</tex>;

4. Считываем группу <tex>10001. N = 17</tex>;

5. Следующий бит <tex>= 0</tex>, поэтому закодированное число {{---}} '''<tex>17</tex>'''.

1. для <tex>1 </tex> будет <tex>0 </tex> групп;

2. <tex>2 ... 3 (<tex>2^1 ... 2^2</tex> − 1) {{---}} 1 </tex> группа;

3. <tex>4 ... 15 (<tex>2^2 ... 2^{2^2}</tex> − 1) — {{---}} 2 <tex> группы;

4. <tex>16 ... 65536 (<tex>2^{2^2} ... 2^{2^{2^2}}− 1) {{---}} 3</tex> − 1) — 3 группы;

5. <tex>65536 ... <tex>2\times10^{19728} (2^{2^{2^2}} ... 2^{2^{2^{2^2}}} − 1) {{---}}</tex> − 1) — всего <tex>4 </tex> группы.