Общие сведения о помехоустойчивых кодах
При передаче данных по каналам связи существует вероятность появления ошибок. Причины могут быть самыми разными, но результатом является искажение данных и невозможность их использования для дальнейшей обработки. Как правило, вероятность искажения бита в потоке передаваемой информации на уровне физического канала находится в пределах 10-2…10-6. В то же время со стороны пользователей и многих прикладных процессов часто выдвигается требование к вероятности ошибок в принимаемых данных не хуже 10-6 …10-12. Борьба с возникающими ошибками ведется на разных уровнях семиуровневой модели OSI (в основном на физическом, канальном, сетевом и транспортном уровнях). Известно много способов защиты информации от ошибок. Одним из путей решения данной задачи является использование специальных процедур, основанных на применении помехоустойчивых кодов.
Помехоустойчивыми кодами называются коды, позволяющие обнаруживать и (или) исправлять ошибки в кодовых словах, которые возникают при передаче информации по каналам связи. Для удобства ориентации в корректирующих кодах на рисунке дана их классификация.
Помехоустойчивый код называется блоковым, если каждая его комбинация имеет ограниченную длину, и непрерывным, если его комбинация имеет неограниченную, а точнее, полубесконечную длину. Различия блоковых и непрерывных кодов связано с принципиально отличными способами их образования. В случае блоковых кодов процедура кодирования заключается в сопоставлении каждой букве сообщения (или последовательности из k символов, соответствующей этой букве) блока из n символов. В операциях по преобразованию принимают участие только указанные k символов, и выходная последовательность не зависит от других символов в передаваемом сообщении. При образовании непрерывного кода устанавливается взаимнооднозначное соответствие между достаточно длинными последовательностями информационных символов (без их деления на отрезки) и другими более длинными последовательностями, которые и передаются по каналу. В случае непрерывных кодов введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделения ее на независимые блоки. И блоковые, и непрерывные коды делятся на разделимые и
неразделимые. Разделимыми называются коды, в каждой кодовой комбинации которых (ограниченной или неограниченной) можно указать позиции, занимаемые информационными и проверочными символами. Неразделимыми называются коды, в комбинациях которых символы нельзя разделить на информационные и проверочные.
Среди составных кодов особое значение имеют каскадные коды и коды произведения. Каскадный код, как правило, состоит из двух ступеней (каскадов): внутренней и внешней. По линии связи сигналы передают внутренним кодом nвт, символьные слова которого являются символами внешнего кода длины nвш . Основание внешнего кода равно qkвт. При формировании каскадного кода входную информационную последовательность символов разбивают на блоки по kвт символов в каждом, каждый блок сопоставляют с информационным символом внешнего кода из алфавита, содержащего qkвт значений символов. Затем kвш информационных символов внешнего кода преобразуют в блоки из nвш символов внешнего кода и, наконец, блоки из kвт информационных символов внутреннего кода преобразуют в блоки из nвт символов внутреннего кода. Возможны различные варианты: внешний и внутренний коды – блочные; внешний – блочный, а внутренний – сверточный; внешний – сверточный, а внутренний – блочный; внешний и внутренний – сверточные. Коды произведения строят в виде матрицы, в которой строки суть слова одного кода, а столбцы – того же или другого кода. Один из наиболее распространенных методов формирования кода произведения заключается в последовательной записи по k1 символов входной информационной последовательности в k2 строк матрицы, добавлении избыточных символов по n1-k1 в каждую строку и по n2-k2 в каждый столбец, после чего последовательность символов кода считывают по строкам или столбцам из матрицы.
Производные коды строят на основе некоторого исходного кода, к которому либо добавляют символы (расширенный код), либо сокращают часть информационных символов (укороченный код), либо выбрасывают (выкалывают) некоторые символы (перфорированный код).
Формально деление кодов на двоичные и недвоичные носит искусственный характер. По аналогии следует выделять троичные, четверичные и другие коды большего основания. Оправдывается такое деление усложнением алгоритмов построения, кодирования и декодирования недвоичных кодов.
Линейные коды отличаются от нелинейных замкнутостью кодового множества относительно некоторого линейного оператора, например сложения или умножения слов кода. Линейность кода упрощает его построение и реализацию. Как линейные, так и нелинейные коды образуют обширные классы. Среди линейных блочных кодов наибольшее значение имеют коды с одной проверкой на четность, М-коды, ортогональные, биортогональные, Хэмминга, Боуза-Чоудхури-Хоквингема, Голея, квадратично-вычетные, Рида-Соломона. К нелинейным относят коды с контрольной суммой, инверсные, Нордстрома-Робинсона, с постоянным весом.
При прочих равных условиях желательно, чтобы информационные и избыточные символы располагались отдельно. В систематических кодах это условие выполняется. В несистематических кодах это условие невыполняется.
В циклических кодах каждое слово содержит все свои циклические перестановки, то есть если (xn-1, xn-2, … , x1, x0) – слово кода, то и (xn-2, … , x1, x0 , xn-1), … , (x0, xn-1, xn-2, … , x1) – слова кода. Все n циклических перестановок образуют цикл. В квазициклических кодах цикл образуется на числе символов n-1 или n-2.
Ошибки в каналах связи имеют самое различное распределение, однако для выбора помехоустойчивого кода целесообразно разделить все возможные конфигурации ошибок на независимые (некоррелированные) и пакеты (коррелированные). Под корреляционными подразумевают коды, обладающие хорошими корреляционными свойствами, важными при передаче сигналов, для повышения защищенности от некоторых типов помех.
Особый класс образуют частотно-компактные коды, предназначенные для сосредоточения энергии сигнала в возможно более узкой полосе частот. Построение частотно-компактных кодов существенно зависит от метода модуляции.
Арифметические коды служат для борьбы с ошибками при выполнении арифметических операций в процессоре ЭВМ.