Элементы теории кодирования

         Число Х₁₀ называется нормализованным, если оно представлено в виде

Х₁₀=±М₁₀ ·10^{± k},  где 0,1 < М₁₀ < 1, k –  целое положительное  число.

М₁₀ –   мантисса нормализованного числа, k –  порядок нормализованного числа. Очевидно, что первая значащая цифра мантиссы всегда ненулевая

Задача. Представить в нормализованном виде числа: 1234, 0,03456

Решение и ответ: 1234 = 0,1234·10; 0,03456 = 0,3456·10².

Понятие нормализованного числа следует  отличать от понятия числа в  нормальной форме; часто используется при записи чисел в математике, физике, технических дисциплинах и отличается от нормализованного представления тем, что мантисса лежит в интервале 1 < М₁₀ < 10, например Х = 1,38 - 10²³.

При нормализации происходит установление его составляющих элементов:

1. Определение знака числа
2. Выделение мантиссы
3. Установление знака порядка
4. Вычисление числового значения порядка

Аналогично  нормализации десятичного числа  можно в нормализованной форме  представить и число в произвольной системе счисления q:

Х_q = ±М_q ·10^{± k} или Х_q = ±(М ·10^{± k})_q,  где мантиссы лежат в интервале (q^{- 1};1) (т.е. первая значащая цифра мантиссы всегда ненулевая), а показатель степени k – коэффициент  представляется в заданной системе q.  
 
 
 
 
 
 
 
 
 
 
 
 

§ 5. Решение практических задач

      Тема «Алфавитное  кодирование»

Задача 1. Задано алфавитное кодирование, для которого  А = {a₁, a₂}; B = {b₁, b₂} и схема ∑ задана таблицей

 

Выясните, обладает ли эта схема кодирования свойством однозначности.

Решение. Процесс декодирования осуществляется следующим образом: код β слова α разбивается на элементарные коды. Для этого в слове β последовательно находятся все буквы b₂ и затем выделяются пары bb₂, каждая такая пара соответствует букве a₂. Оставшиеся буквы b₁ соответствуют букве a₁.

       Так код β = b₁b₁b₁b₂b₁b₂b₁b₂b₁b₁b₂ разбивается однозначно на элементарные коды β = (b₁)(b)(b₁b₂)(b₁b₂)(b₁b₂)(b₁)(b₁b₂).

      Следовательно, исходное сообщение есть слово α = а₁а₁а₂а₂а₂а₁а₂.

Задача 2. Пусть схема ∑ задана следующей таблицей

Покажите, что эта схема не обладает свойством  однозначности.

Решение. Рассмотрим слово β = b₁b₁b₂b₁b₁b₂b₁b₁.

       Это слово допускает два декодирования.

β = (b₁b₁)(b₂b₁b₁)(b₂b₁b₁), β = (b₁b₁b₂)(b₁b₁b₂)(b₁b₁),

тогда α = а₁а₂а₂; α = а₃а₃а₁.

       Следовательно, схема ∑ не  обладает свойством однозначности.

Задача 3. Схема алфавитного кодирования задана таблицей

Покажите, что ни ∑, ни ∑^-1 не обладают свойством префикса, но тем ни менее алфавитное кодирование, задаваемое этой семой, является взаимно-однозначным.

Решение. Схема ∑ не обладает свойством префикса, так как b₁ является префиксом слова b₁ b₂ . С другой стороны, в схеме С(∑^-1) = {b₁,b₂ ,b₁,b₁,b₃} b₁ является префиксом слова b₁ b₃ .

        По коду β любого слова α ϵ А*, А = {a₁, a₂, a₃}, однозначно восстанавливается следующий:

1. В кодовом слове β находим все буквы b₂ и выделяем все пары b₁ b₂ .
2. Находим в кодовом слове β все буквы b₂ и выделяем все пары b₃ b₁ .
3. Каждую пару b₁ b₂ заменяем букой a₂, пару b₃ b₁ заменяем буквой a₃ ,

оставшиеся  буквы  b₁  заменяем на a₁ . В результате получим исходное сообщение (слово) α.

        Действительно пусть 

                                           β = b₁b₁b₂b₃b₁b₁b₁b₁b₂b₁b₃b₁,

                                           β = (b₁)(b₁b₂)(b₃b₁)(b₁)(b₁)(b₁b₂)(b₁)(b₃b₁),

                                           α = а₁а₂а₃а₁а₁а₂а₁а₃.

Задача 4. Алфавитное кодирование задано схемой ∑ в виде таблицы

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

Решение. Алгоритм решения.

1. Выпишем все нетривиальные разложения каждого элементарного кода:

β₁ = (b₁)(b₂),

β₂ = (b₁)(b₃b₂) = (b₁b₃)(b₂),

β₃ =(b₂)(b₃),

β₄ =(b₁)(b₂b₁b₃) =(b₁ b₂)(b₁b₃) = (b₁ b₂b₁)(b₃),

β₅ = (b₂)(b₁b₂)(b₂b₃) =(b₂ b₁)(b₂ b₂b₃) =(b₂ b₁b₂ b₂)b₃.

2. Выписываем множество М₁ , состоящее из слов, входящих в качестве начал в нетривиальные разложения элементарных кодов.

М₁ = {b₁;b₁b₃;b₂;b₁b₂;b₁b₂b₁;b₂b₁;b₂b₁b₂b₂}.

3. Выписываем  множество М₂ , состоящее из слов, которые являются окончанием нетривиальных разложений элементарных кодов:

М₂ = {b₂;b₃b₂;b₃;b₂b₁ b₃;b₁b₃;b₂b₃;b₂b₂b₃}.

4. Составляем множество М = М₁ ∩ М₂ U {˄}.

                                       М = {˄,b₂ ,b₁b₃}.

5. Выписываем все разложения элементарных кодов, связанных с элементами множества М.

β₂ = (b₁b₃) ˄ (b₂),

β₄ = (b₁ b₂)(b₁b₃) =˄β₁ (b₁ b₃),

β₅ = (b₂)(b₁b₂)(b₂b₃) = b₂β₁β₃ ˄ .

6. По полученным разложениям строим ориентированный граф: вершины графа – элементы множества М = {˄,b₂ ,b₁b₃}. Пара вершин соединяется ориентированными ребрами в том случае, если существует разложение, где вершины графа входят в разложение в качестве начала и конца.

 

   β₁                  β₁β₃

     ˄ 

7. В графе G_∑ присутствует ориентированный цикл, проходящий через вершину ˄, следовательно, согласно теореме Маркова, алфавитное кодирование с заданной схемой не является взаимно- однозначным.
8. Выписывая слова, приписанные вершинам и дугам ориентирован ного графа G_∑, получаем слово декодируемое неоднозначно:

                                           β = b₁b₂b₁b₃b₂b₁b₂b₂b₃,

                                           β₁ = (b₁b₂)(b₁b₃b₂)(b₁b₂)(b₁)(b₂b₃),

                                           α₁ = а₁а₂а₁а₃,

                                           β₂ = (b₁b₂b₁b₃)(b₂b₁b₂b₂b₃),

                                           α₂ = а₄а₅. 
 

Задача 5. Схема алфавитного кодирования задана таблицей