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

Безызбыточные коды или коды с малой избыточностью, рассмотренные выше в качестве оптимальных, обладают большой чувствительностью к помехам. Достаточно помехам исказить хотя бы один символ при приеме кодированного сигнала, чтобы вместо переданной кодовой комбинации при приеме была воспроизведена совсем другая кодовая комбинация. Например, если при приеме комбинации 0100 произойдет ошибка в первой позиции, то принятой окажется комбинация 1100.

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

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

Простейшим примером корректирующего кода является код с проверкой на четность. Такой код строят следующим образом. К кодовым комбинациям безызбыточного первичного двоичного L-разрядного кода добавляется дополнительный разряд (позиция), называемый проверочным, или контрольным. Если число символов 1 в исходной кодовой комбинации четное, то в дополнительном разряде формируют контрольный символ 0, если число символов 1 нечетное, то в дополнительном разряде формируют контрольный символ 1. В результате общее число символов 1 в любой кодовой комбинации всегда должно быть четным.

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

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

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

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

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

При использовании блочных кодов информация передается в виде кодовых комбинаций (блоков) одинаковой длины. Кодирование и декодирование каждого блока производится независимо друг от друга.

Почти все блочные коды относятся к разделимым кодам, т. е. таким, кодовые комбинации которых состоят из двух различающихся частей: информационной и проверочной. Информационные и проверочные разряды во всех кодовых комбинациях разделимого кода всегда занимают одни и те же позиции. Разделимые коды обычно условно обозначают в виде (п,k), гдепуказывает общую значность кода (общее число позиции в блоке),k– число информационных позиций. Иными словами, величинапопределяет общее число символов в блоке,ak– только число информационных символов. Таким образом, число проверочных символов в разделимых кодах равноr=n–k.

Среди разделимых кодов различают систематические и несистематические коды.

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

Систематические коды обстоятельно изучены. Наиболее известны среди них циклические коды. Важными представителями циклических кодов являются коды Хэмминга, которые исторически появились раньше многих других кодов и сыграли большую роль в развитии теории корректирующих кодов, а также коды Боуза-Чоудхури-Хоквингема. Для таких кодов найдены сравнительно простые методы их реализации. Исследования показали, что эти коды имеют особенно важны для приложений. Основное свойство циклических кодов сострит в том, что циклический сдвиг любой разрешенной кодовой комбинаций также является разрешенной комбинацией. Циклические коды обладают хорошими корректирующими свойствами, а реализация кодирующих и декодирующих устройств для таких кодов оказывается проще, чем для других систематических кодов.

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

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

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

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

Избыточностью корректирующего кода называют величину

.

Из следует, что

.

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

,

поскольку в кодированной последовательности из каждых псимволов толькоkсимволов являются информационными.

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

При изучении корректирующих кодов очень полезно понятие о кодовом расстоянии или расстоянии Хэмминга. Расстоянием dмежду двумя кодовыми комбинациями называют число позиций, в которых эти комбинации имеют разные символы. Например, расстояние между комбинациями 0001101 и 1001010, равно четырем (d=4). Расстояние между различными комбинациями некоторого конкретного кода может быть различным. Так, в частности, в безызбыточном первичном натуральном коде это расстояние для различных комбинаций может различаться от единицы до величиныт, равной значности кода. Особую важность для характеристики корректирующих свойств кода имеет минимальное расстояниеd_minмежду кодовыми комбинациями. Это растояние называют кодовым, или хэмминговым.

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

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

,

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

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

/

Чтобы можно было исправить все ошибки кратностью аи менее, необходимо иметь минимальное расстояние, удовлетворяющее условию

.

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

.

Корректирующие коды можно одновременно использовать и для обнаружения и для исправления ошибок. Минимальное расстояние, при котором можно исправить все ошибки кратностью а или меньше и одновременно обнаружить все ошибки кратностью bили меньше, определяется условием

,

где, в свою очередь, всегда должно выполняться условие b>а.

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

Нижняя граница Варшамова-Гильберта. Для больших значений nуказанная граница определяется асимптотическим соотношением

.

где .

Из следует, что

,

.

Условия и позволяют оценить необходимое количество проверочных символов rи относительную скорость кодапри заданных (или выбранных) значенияхnиd_min.

Верхнюю границу Хэмминга для двоичного корректирующего кода можно представить в виде

.

Отсюда следуют выражения для оценки числа проверочных символов и относительной скорости передачи:

,

.

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

,

которое справедливо, если . Для значенийразница между границей Хэмминга и границей Плоткина сравнительно невелика.

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

,

.

Систематические коды с d_min=3 и 4 в литературе обычно называют кодами Хэмминга.

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

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

В теории помехоустойчивого кодирования принято различать два вида основных ошибок: статистически независимые, т. е. некоррелированные ошибки; статистически зависимые, т. е. коррелированные ошибки (ошибки типа пачек или пакетов).

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

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

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

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

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