Кодирование информации

     Среднее число символов для такого кода составит

     а избыточность кода

     т.е. на порядок меньше, чем при равномерном  кодировании. [3; c 55]

     Другим  простейшим способом статистического  кодирования является кодирование  по методу Шеннона-Фано. Кодирование  в соответствии с этим алгоритмом производится так:

• сначала все буквы из алфавита сообщения записывают в порядке убывания их вероятностей;
• затем всю совокупность букв разбивают на две примерно равные по сумме вероятностей группы; одной из них (в группе может быть любое число символов, в том числе – один) присваивают символ “1”, другой - “0”;
• каждую из этих групп снова разбивают (если это возможно) на две части и каждой из частей присваивают “1” и “0” и т.д.

     Процедура кодирования по методу Шеннона-Фано иллюстрируется табл. 4. 

     Таблица 4

     Для полученного таким образом кода среднее число двоичных символов, приходящихся на одну букву, равно

      ,

а избыточность кода составит

то есть также существенно меньшую величину, нежели для равномерного кода.

     Обратим внимание на тот факт, что как  для кода Хаффмена, так и для кода Шеннона-Фано среднее количество двоичных символов, приходящееся на символ источника, приближается к энтропии источника, но не равно ей. Данный результат представляет собой следствие теоремы кодирования без шума для источника (первой теоремы Шеннона), которая утверждает:

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

1.3 Помехоустойчивое кодирование

     Хотя  существующие на данный момент системы  передачи данных отвечают всем основным стандартам и требованиям, они все  же не являются совершенными. Причин тому влияние помех в канале связи. При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Естественный язык обладает большой избыточностью (в европейских языках — до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством. Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, больная избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении.

     Одним из средств решения подобных несоответствий в системах передачи цифровой информации, является применение помехоустойчивых кодов, лежащих в основе устройств кодирования/декодирования. Высокоэффективным средством решения данной проблемы является применение помехоустойчивого кодирования, основанного на введении искусственной избыточности в передаваемое сообщение. Помехоустойчивое кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки. [2; 223]

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

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

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

     В 50-е-70-е годы было разработано большое  количество алгебраических кодов с  исправлением ошибок, среди которых  наиболее востребованными стали  коды Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Соломона (РС), Рида-Малера, Адамара, Юстенсена, Гоппы, циклические коды, сверточные коды с разными алгоритмами декодирования (последовательное декодирование, алгоритм Витерби), арифметические коды.

     Однако  на практике применяется относительно небольшая группа алгебраических помехоустойчивых кодов: БЧХ, Рида-Соломона и сверхточные коды. Наиболее широко применяются циклические коды с обнаружением ошибок в стандартных протоколах HDLC, Х.25/2 (LAP-B, LAP-M). Коды Рида-Соломона с исправлением ошибок находят применение в каналах радиосвязи. В каналах спутниковой связи, характеризующихся независимым характером ошибок, широко применяются сверхточные коды .

     Помехоустойчивое  кодирование передаваемой информации позволяет в приемной части системы  обнаруживать и исправлять ошибки. Коды, применяемые при помехоустойчивом кодировании, называются корректирующими кодами. Как правило, корректирующий код может исправлять меньше ошибок, чем обнаруживать. Число ошибок, которые корректирующий код может исправить в определенном интервале последовательности двоичных символов, например, в одной кодовой комбинации, называется исправляющей способностью кода. [6; c. 267]

     Основной  характеристикой интенсивности  помех в канале является параметр шума — p. Это число от 0 до 1, равное вероятности инвертирования бита, при условии что, он был передан по каналу и получен на другом конце.

     Следующий параметр — p2. Это вероятность того же события, но при условии, что предыдущий бит также был инвертирован.

     Этими двумя параметрами вполне можно  ограничиться при построении теории. Но, в принципе, можно было бы учитывать аналогичные вероятности для исчезновения бита, а также использовать полную информацию о пространственной корреляции ошибок, — то есть корреляции соседних ошибок, разделённых одним, двумя или более битами.

     У групповых ошибок есть свои плюсы  и минусы. Плюсы заключаются в следующем. Пусть данные передаются блоками по 1000 бит, а уровень ошибки 0,001 на бит. Если ошибки изолированные и независимые, то 63% блоков будут содержать ошибки. Если же они возникают группами по 100 сразу, то ошибки будут содержать 1% блоков.

     Зато, если ошибки не группируются, то в каждом кадре они невелики, и есть возможность  их исправить. Групповые ошибки портят кадр безвозвратно. Требуется его  повторная пересылка, но в некоторых  системах это в принципе невозможно, — например, в телефонных системах, использующие цифровое кодирование, возникает эффект пропадания слов/слогов.

     Для надёжной передачи кодов было предложено два основных метода.

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

     Второй  — внести избыточность настолько, чтобы, анализируя полученные данные, можно  не только замечать ошибки, но и указать, где именно возникли искажения. Это коды, исправляющие ошибки. [6,c. 269]

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

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

     Непрерывные или рекуррентные коды образуют последовательность символов, не разделяемую на отдельные кодовые комбинации. Кодирование и декодирование непрерывно совершаются над последовательностью элементов без деления их на блоки. Формирование проверочных символов ведётся по рекуррентным (возвратным) правилам, поэтому непрерывные коды часто называют рекуррентными или цепными.

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

     Блочные коды делятся на равномерные и неравномерные. В равномерных кодах, в отличие от неравномерных, все кодовые комбинации содержат одинаковое число n - символов (разрядов) с постоянной длительностью τ0 импульсов символов кода. Равномерные коды в основном и применяются в системах связи, так как это упрощает технику передачи и приёма. [2; c. 227]

     Классическими примерами неравномерного кода являются код Морзе, широко применяемый в  телеграфии, и код Хафмена, применяемый  для компрессии информации (факсимильная связь, ЭВМ).

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

     Почти все блочные корректирующие коды принадлежат к разделимым кодам, в которых кодовые комбинации состоят из двух частей: информационной и проверочной. Их символы всегда занимают одни и те же позиции, т.е. располагаются на определённых местах. Как правило, в таких кодах, все кодовые комбинации которых содержат n символов, первые k символов являются информационными, а за ними располагаются (n - k) проверочных символов. В соответствии с этим разделимые коды получили условное обозначение – (n , k) - коды.

     В неразделимых кодах деление на информационные и проверочные символы отсутствует. К таким кодам относятся, в частности, коды с постоянным весом, так называемые равновесные коды. Например, Международным Консультативным Комитетом по телеграфии и телефонии (МККТТ) рекомендован для использования телеграфный код № 3 - семиразрядный код с постоянным весом, т.е. с числом единиц в каждой кодовой комбинации, равным 3 (W = 3). [ 6; c. 273]