Разработка и отладка программного обеспечения микропроцессорных систем обработки информации

Для решения этой задачи применяются так называемые неравномерные блочные коды. Основная идея такого кодирования заключается в том, что более вероятные сообщения кодируются более короткими блоками, а менее вероятные - более длинными. Таким образом, средняя длина кодовой комбинации уменьшается по срав­ нению со средней длиной равномерного блочного кода и тем самым снижается первоначальная избыточность источника. Среди эффек­ тивных кодов широко применяется код Шеннона - Фано. Он позво ляет сократить среднюю длину кодовой комбинации по сравнению с равномерным кодом. Нижняя граница средней длины кодовой комбинации определяется на основе теоремы кодирования, согласно которой Vk/vc>=ff(A), где V)t ~ количество символов кода на одно сообщение Vc - количество символов в сообщении; Я(А) - энтропия источника. Если это неравенство не выполняется, то такой код невозможно однозначно декодировать. Таким образом, допустимый минимум средней длины кодовой комбинации определяется энтропией источника сообщения. Средняя длина кода Шеннона-Фано превышает этот минимум всего на 2-4%. Кодирование по методу Шеннона - Фано производится в следующем порядке: все сообщения источника записываются в порядке убывания их вероятностей. Затем вся совокупность сообщений разбивается на две примерно равновероятные группы (по суммарным вероятностям). Группы разбиваются так, чтобы суммарные вероятности сообщений в группах как можно меньше отличались друг от друга. Всем символам первой группы приписывается кодовый символ «1»,а символам второй группы - • кодовый символ «О». Каждая группа разбивается аналогич на подгруппы с одинаковыми по возможности вероятностями 149