Программная модель помехоустойчивого кодирования

    Таким образом, декодер Витерби последовательно обрабатывает кадр за кадром, двигаясь по решетке, аналогичной используемой кодером. В каждый момент времени декодер не знает, в каком узле находится кодер, и не пытается его декодировать. Вместо этого декодер по принятой последовательности определяет наиболее правдоподобный путь к каждому узлу и определяет расстояние между каждым таким путем и принятой последовательностью. Это расстояние называется мерой расходимости пути. В качестве оценки принятой последовательности выбирается сегмент, имеющий наименьшую меру расходимости. Путь с наименьшей мерой расходимости называется выжившим путем.

    Рассмотрим  работу декодера Витерби на простом  примере. Полагаем, что кодирование  производится с использованием сверточного (6,3)-кода (схема кодера приведена на  рис. 2.5, решетчатая диаграмма, соответствующая этому кодеру, – на рис. 2.7).

    Пользуясь решетчатой диаграммой кодера, попытаемся, приняв некоторый сегмент r,  проследить наиболее вероятный путь кодера. При этом для  каждого сечения решетчатой диаграммы  будем отмечать меру расходимости пути к каждому ее узлу.

    Предположим,   что    передана    кодовая    последовательность        U = = ( 0000000…), а принятая последовательность имеет вид r = (10001000 00...), то есть в первом и в третьем кадрах кодового слова возникли ошибки. Как мы уже убедились, процедура и результат декодирования не зависят от передаваемого кодового слова и определяются только ошибкой, содержащейся в принятой последовательности. Поэтому проще всего считать, что передана нулевая последовательность, то есть  U = (0000000…).

    Приняв  первую пару символов (10), определим меру расходимости для первого сечения решетки (см. рис. 2.7), приняв следующую пару символов  (00), — для второго сечения и т.д. При этом из входящих в каждый узел путей оставляем путь с меньшей расходимостью, поскольку путь с большей на данный момент расходимостью уже не сможет стать в дальнейшем короче.

    Заметим, что для рассматриваемого примера начиная с четвертого уровня метрика (или мера расходимости) нулевого пути меньше любой другой метрики. Поскольку ошибок в канале больше не было, ясно, что в конце концов в качестве ответа будет выбран именно этот путь. Из этого примера также видно, что выжившие пути могут достаточно долго отличаться друг от друга.

    Однако  на шестом - седьмом уровне  первые семь ребер всех выживших путей совпадут друг с другом. В этот момент согласно алгоритму Витерби и принимается  решение о переданных символах, так как все выжившие пути выходят из одной вершины, т.е. соответствуют одному информационному символу.

    Процедура декодирования последовательности с двумя ошибками иллюстрируется последовательностью, представленной на рис. 2.8.

Рис. 2.8 

    Глубина, на которой происходит слияние выживших путей, не может быть вычислена заранее; она является случайной величиной, зависящей от кратности и вероятности возникающих в канале ошибок. Поэтому на практике обычно не ждут слияния путей, а устанавливают фиксированную глубину декодирования.

    Из  рис. 2.8 видно, что уже на уровне Е степень различия метрик правильного и неправильного путей достаточно велика ( d_пр = 2, d_ош = 4), то есть в данном случае можно было бы ограничить глубину декодирования величиной b ≤ 6.  Но иногда более длинный к данному сечению путь может оказаться в конечном итоге самым коротким, поэтому особенно увлекаться уменьшением размера окна декодирования b  с целью упрощения работы декодера не стоит.

    На  практике  глубину  декодирования  обычно выбирают  в диапазоне  n  <  b ≤ n  + l  , где l - число исправляемых данным кодом ошибок.

    Из  рис. 2.8  видно также, что, несмотря на наличие в принятом фрагменте  двух ошибок, его декодирование произошло  без ошибки и в качестве ответа будет принята переданная нулевая  последовательность.[16]  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Глава 2

   2.1 Коды Шеннона – Фано.

   Для удобства расположим все имеющиеся  п букв в один столбик в порядке убывания вероятностей. Затем все эти буквы следует разбить на две группы – верхнюю и нижнюю – так, чтобы суммарная вероятность первой группы была наиболее близка к суммарной вероятности второй группы. Для букв первой группы в качестве первой цифры кодового обозначения используется цифра 1, а для букв второй группы – цифра 0. Далее, каждую из двух групп подобным образом снова надо разделить на две части и в качестве второй цифры кодового обозначения мы будем использовать цифру 1 или 0 в зависимости от того, принадлежит ли наша группа к первой или ко второй из этих подгрупп. Затем, каждая из содержащих более одной буквы групп снова делится на две части возможно более близкой суммарной вероятности и т.д.; процесс повторяется до тех пор, пока мы не придем к группам, каждая из которых содержит по одной единственной букве. [6]

   Такой метод кодирования сообщений  был впервые предложен в 1948 – 1949 гг. независимо друг от друга Р. Фано и К. Шенноном; поэтому соответствующий код обычно называется кодом Шеннона – Фано. Так, например, если наш алфавит содержит всего шесть букв, вероятность которых (в порядке убывания) равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05, то на первом этапе деления букв на группы мы отщепим лишь одну первую букву (1-я группа), оставив во второй группе все остальные. Далее, вторая буква составит 1-ю подгруппу 2-й группы; 2-я же подгруппа той же группы, состоящая из оставшихся четырех букв, будет и далее последовательно делиться на части так, что каждый раз 1-я часть будет состоять лишь из одной буквы.

    
          Табл.1

   Аналогично  предыдущему примеру разобран случай «алфавита», включающего 18 букв, имеющих  следующие вероятности: 0,3; 0,2; 0,1 (2 буквы); 0,05; 0,03 (5 букв); 0,02(2 буквы); 0,01 (6 букв). (Табл. 2) 
 

                                                               Табл.2

   Основной  принцип, положенный в основу кодирования  по методу Шеннона – Фано, заключается  в том, что при выборе каждой цифры  кодового обозначения мы стараемся, чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы  независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения 0 и 1 по возможности с одинаковой вероятностью. Разумеется, количество цифр в различных обозначениях при этом оказывается различным (в частности, во втором из разобранных примеров он меняется от двух до семи), т. е. код Шеннона – Фано является неравномерным. Нетрудно понять, однако, что никакое кодовое обозначение здесь не может оказаться началом другого, более длинного обозначения; поэтому закодированное сообщение всегда может быть однозначно декодировано. В результате,  среднее значение длины такого обозначения все же оказывается лишь немногим большим минимального значения Н, допускаемого соображениями сохранения количества информации при кодировании. Так, для рассмотренного выше примера 6-буквенного алфавита наилучший равномерный код состоит из трехзначных кодовых обозначений (ибо 2² < 6 < 2³), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона – Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно

     Это значение заметно меньше, чем 3, и не очень далеко от  энтропии 

   Аналогично  этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 2⁴ < 18 < 2⁵); в случае же кода Шеннона – Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно

   Последнее значение заметно меньше, чем 5, - и  уже не намного отличается от величины

         Особенно выгодно  бывает кодировать по методу Шеннона  – Фано не отдельные буквы, а сразу  целые блоки из нескольких букв. Правда, при этом все равно невозможно превзойти предельное значение Н двоичных знаков на одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда

   H = - 0,7 log0,7 – 0,3 log0,3 = 0,881…

   Применение  метода Шеннона – Фано к исходному  двухбуквенному алфавиту здесь оказывается  бесцельным: оно приводит нас лишь к простейшему равномерному коду

   требующему  для передачи каждой буквы одного двоичного знака – на 12% больше минимального достижимого значения 0,881 дв.зн./букву. Применяя же метод Шеннона  – Фано к кодированию всевозможных двухбуквенных комбинаций (вероятность  которых определяется правилом умножения вероятностей для независимых событий), мы придем к следующему коду:

   Среднее значение длины кодового обозначения  здесь равно

    ,

так что на одну букву алфавита здесь  приходится в среднем  двоичных знаков – лишь на 3% больше значения 0,881 дв.зн./букву. Еще лучше результаты мы получим, применив метод Шеннона – Фано к кодированию трехбуквенной комбинации; при этом мы придем к следующему коду: