Достоинства и недостатки эффективных кодов.

а) Достоинства оптимальных эффективных кодов:

1) при эффективном кодировании, учитывающем вероятности появления букв алфавита источника сообщений, удается построить коды с максимальной удельной энтропией на символ;

2) обеспечивается преобразование сообщения в сигнал с меньшей, чем у сообщения избыточностью (в пределе – без избыточности);

3) на передачу сообщения затрачивается минимальное количество символов;

4) решается задача согласования источника сообщений с каналом связи, в результате чего скорость передачи информации может быть приближена к пропускной способности канала;

5) не требуется введения специальных разделительных символов (маркеров), как, например, в коде Морзе, для отделения одной кодовой комбинации от другой, так как ни одна комбинация эффективного кода не совпадает с началом другой, более длинной. Такое свойство кода называется «неприводимостью», и коды называются префиксными, или кодами без запятой.

б) Недостатки эффективных кодов:

1) эффективные коды являются неравномерными, т.е. кодовые комбинации имеют различное количество символов. Если линия связи работает с постоянной скоростью передачи, то на выходе кодера необходимо буферное запоминающее устройство («упругая задержка») для записи в него «пульсирующих» по длительности кодовых групп и последующего считывания в канал символов с постоянной скоростью. Аналогичная «упругая задержка» должна быть и на стороне приёма;

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

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

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

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

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

3.2.1. Методы повышения достоверности

Общепринятым критерием оценки качества передачи в дискретных каналах является нормированная на знак или символ (бит) допустимая вероятность ошибки для данного вида сообщений. Так, допустимая вероятность ошибки при телеграфной связи может составлять 10^-3 (на знак), а при передаче данных – не более 10^-6 (на бит). Для обеспечения таких значений вероятностей одного улучшения только качественных показателей канала связи может оказаться недостаточно. Поэтому задача повышения достоверности передаваемой информации решается путём применения специальных методов, общая классификация которых приведена на рис. 3.2.

Рис. 3.2. Методы повышения достоверности

К первой группе относятся методы увеличения помехоустойчивости приёма единичных элементов (символов) дискретной информации, связанные с выбором уровня сигнала, ОСП (энергетические характеристики), ширина полосы канала, методов приёма и т.д.

Ко второй группе относятся методы обнаружения и исправления ошибок, основанные на искусственном введении избыточности в передаваемое сообщение.

Для повышения качества приёма, как правило, идут по пути увеличения времени передачи и используют следующие основные способы:

1) многократная передача кодовых комбинаций (метод повторения);

2) одновременная передача кодовой комбинации по нескольким параллельно работающим каналам;

3) помехоустойчивое (корректирующее) кодирование, т.е. использование кодов, исправляющих ошибки.

Применяются также комбинации этих способов.

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

Наиболее целесообразно избыточность используется при применении помехоустойчивых (корректирующих) кодов. Внесение избыточности при использовании помехоустойчивых кодов обязательно связано с увеличением n – числа разрядов (длины) кодовой комбинации. Таким образом, все множество N = 2ⁿ комбинаций разбивается на два подмножества: подмножество разрешенных комбинаций, обладающих определенными признаками, и подмножество запрещенных комбинаций, этими признаками не обладающих. При этом в канал передаются не все кодовые комбинации N, которые можно сформировать из имеющегося числа разрядов n, а только их часть N_k, которая составляет подмножество разрешенных комбинаций. Если при приёме выясняется, что кодовая комбинация принадлежит к запрещенным, то это свидетельствует о наличии ошибок в комбинации, т.е. таким образом решается задача обнаружения или обнаружения и исправления ошибок. В связи с этим помехоустойчивые коды называют корректирующими кодами. Корректирующие свойства избыточных кодов зависят от правила их построения, определяющих структуру кода, и параметров кода (длительности символов, числа разрядов, избыточности и т.п.).

3.2.2. Классификация помехоустойчивых кодов

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

На практике степень достоверности и эффективности ограничивается двумя факторами:

1) размером и стоимостью кодеков;

2) временем задержки передаваемого сообщения.

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

Известно большое число помехоустойчивых кодов, отличающихся по структуре, принципу построения, исправляющей способности. На рис. 3.3 приведена упрощенная их классификация.

Рис. 3.3. Классификация помехоустойчивых кодов

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

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

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

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

К непрерывным относятся свёрточные коды, в которых каждый информационный символ, поступающий на вход кодирующего устройства, вызывает появление на его выходе ряда проверочных символов, образованных суммированием по модулю 2 данного символа и k-1 предыдущих информационных символов. Рекуррентные коды позволяют исправлять групповые ошибки(«пачки») в каналах связи.

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

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

В неразделимых кодах деление на информационные и проверочные символы отсутствует.

Разделимые коды делятся на линейные (систематические) и нелинейные (несистематические). Линейными (систематическими) называются блочные разделимые (n, k) коды, в которых проверочные элементы представляют собой линейные комбинации информационных элементов. Кроме того, любая разрешенная кодовая комбинация может быть получена в результате линейной операции над набором k ненулевых линейно независимых кодовых комбинаций. В частности, суммирование по модулю 2 двух и более разрешенных комбинаций также дает разрешенную кодовую комбинацию. Поскольку теоретической основой получения таких комбинаций является математический аппарат линейной алгебры, то коды и называют линейными, а, учитывая, что проверочные символы формируются по определенной системе (правилам), блочные равномерные разделимые линейные коды получили название систематических. Использование аппарата линейной алгебры, в которой важное значение имеет понятие «группа», породило и другое название этих кодов – групповые. Эти коды получили наибольшее применение в системах передачи дискретной информации.

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

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

К комбинационным кодам можно отнести также антифединговые коды, предназначенные для обнаружения и исправления ошибок в каналах с замираниями (федингом) сигналов. Для таких каналов с группированием ошибок применяют метод перемежения символов, или декорреляции ошибок. Он заключается в том, что символы, входящие в одну кодовую комбинацию, передаются не непосредственно друг за другом, а перемежаются символами других кодовых комбинаций исходного систематического или любого другого кода. Если интервал между символами, входящими в одну кодовую комбинацию, сделать длиннее «памяти» (интервала корреляции) канала с замираниями, то в пределах длительности одной исходной кодовой комбинации группирования ошибок не будет. На приёме после обратной «расфасовки» в кодовых комбинациях можно производить декодирование с обнаружением и исправлением ошибок.

В систематических кодах различают два метода формирования проверочной группы символов: поэлементный и в целом.

Наиболее известны среди систематических кодов коды Хемминга, которые исторически найдены раньше многих других кодов и сыграли большую роль в развитии теории корректирующих кодов. В этих кодах используется принцип проверки на чётность определенного ряда информационных символов. Проверочная группа из r символов формируется поэлементно по соответствующему алгоритму. Коды Хемминга, имеющие d_min = 3, позволяют исправить одну ошибку.

Расширенные коды Хемминга строятся в результате дополнения кодов с d_min = 3 общей проверкой каждой из кодовых комбинаций на чётность, т.е. еще одним проверочным символом. Это позволяет увеличить минимальное кодовое расстояние до d_min = 4.

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

Среди циклических кодов особое место занимают циклические избыточные CRC-коды (Cyclic redundancy code) и класс кодов, предложенных Боузом и Рой-Чоудхури и независимо от них Хоквингемом. Коды Боуза-Чоудхури-Хоквингема получили сокращенное наименование БЧХ - коды и отличаются специальным выбором порождающего (образующего) циклический код полинома, что приводит к простой процедуре декодирования.

В циклических кодах r проверочных символов, добавляемых к исходным k информационным, могут быть получены сразу, т.е. в целом, в результате умножения исходной подлежащей передаче кодовой комбинации Q(x) простого кода на одночлен x^r и добавлением к этому произведению остатка R(x), полученного в результате деления произведения на порождающий полином P(x).

По алгоритмам формирования циклических кодов можно также получить коды Хемминга.