Математическая логика и теория алгоритмов. Стенюшкина В.А. - 86 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

Относительная
частота
0,45 0,13 0,12 0,16 0,09 0,05
Равномерный
код
000 001 010 011 100 101
Неравномерный
код
0 101 100 111 1101 1100
0 1 0 1
0 1 0 a 0 1
0 1 0 1 0 1 0 1 0 1
a b c d e f c b 0 1 d
f e
Рисунок 4.6
4.6.2 Префиксные коды
Коды, в которые из двух последовательностей битов, представляющих
различные символы, ни одна не является префиксом другой, называются пре-
фиксными кодами. Известно, что для любого кода, допускающего однозначное
восстановление информации, существует не худший его префиксный код. По-
этому, в принципе, можно ограничиться префиксными кодами.
При кодировании каждый символ заменяется на свой код. Например, для
рассматриваемого неравномерного кода строка abc запишется как 0101100. Для
префиксного кода декодирование однозначно (что следует из его определения)
и выполняется слева направо. Первый символ текста, закодированного префик-
сным кодом, определяется однозначно, так как кодирующая его последователь-
ность не может быть началом кода какого-то символа. Найдя этот первый
символ и отбросив кодирующую его последовательность битов, повторяем
процесс для оставшихся битов, и так далее. В частности строка 001011101 в
5 2
8
1
1
100
11 14 0 0
0 0
1 1 1 1
32
5
100
4
Относительная 0,45                           0,13                     0,12       0,16              0,09             0,05
частота
Равномерный   000                            001                      010        011               100              101
код
Неравномерный 0                              101                      100        111               1101             1100
код


                                            100                                            100



                            0                                     1          0                             1

                    8                                                  1     4                             5

        0                       1                     0                      a             0                        1

            5                   2                         1                                2                        3

0               1       0           1       0                 1                  0             1           0            1

    4           1           1       1             0               0                  1             1           1            1

    a           b           c           d         e               f                    c           b           01           d
                                                                                                       0                0

                                                                                                       f                e
                                                          Рисунок 4.6

                                            4.6.2 Префиксные коды

      Коды, в которые из двух последовательностей битов, представляющих
различные символы, ни одна не является префиксом другой, называются пре-
фиксными кодами. Известно, что для любого кода, допускающего однозначное
восстановление информации, существует не худший его префиксный код. По-
этому, в принципе, можно ограничиться префиксными кодами.
      При кодировании каждый символ заменяется на свой код. Например, для
рассматриваемого неравномерного кода строка abc запишется как 0101100. Для
префиксного кода декодирование однозначно (что следует из его определения)
и выполняется слева направо. Первый символ текста, закодированного префик-
сным кодом, определяется однозначно, так как кодирующая его последователь-
ность не может быть началом кода какого-то символа. Найдя этот первый
символ и отбросив кодирующую его последовательность битов, повторяем
процесс для оставшихся битов, и так далее. В частности строка 001011101 в

Страницы