Реферат: Основные параметры помехоустойчивого кодирования. Основные параметры помехоустойчивых кодов

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

Существует много хороших конструктивных методов кодирования, позволяющих исправлять кратные ошибки и приводящих к заметному уменьшению частоты появления ошибочных символов. Эти коды легко строятся и с помощью современных полупроводниковых устройств относительно просто декодируются. Например, существует блоковый код длиной 40, содержащий 50% избыточных символов и позволяющий исправлять четыре случайные ошибки. На рис. 1 показано, что при Р_e =0,01 этот код имеет вероятность ошибки блока, меньшую 10^-4 . Если этого недостаточно, разработчик увеличивает избыточность, чтобы исправлять большее число ошибок, или переходит к кодам с большей длиной блока и получает выигрыш за счет большего усреднения. В каждом случае нужно принимать во внимание возникающие дополнительные затраты. Однако обе указанные возможности допустимы и могут представлять практически приемлемые альтернативы. Прежде чем идти дальше, сделаем небольшое отступление, которое не имеет большого практического значения, но привлекает внимание специалистов по теории кодирования в течение многих лет. Форма кривых, изображенных на рис. 1, позволяет предположить, что если имеется схема, исправляющая фиксированную долю t/n ошибочных символов в блоке (в нашем случае t/n незначительно превышает 0,01), то, выбирая длину блока достаточно большой, можно сделать долю ошибок сколь угодно малой. К сожалению, это оказывается очень трудной задачей. Большинство конструктивных процедур может обеспечить постоянное отношение t/n лишь при возрастающей доле избыточных символов (другими словами, R->0 при n->oo). Таким образом, потеря эффективности возникает из-за того, что доля полезных сообщений становится очень малой при большой длине блока. Частично эта задача была решена Юстесеном в 1972 г. Юстесен показал, что можно построить класс асимптотически хороших (в указанном здесь смысле) кодов и указать для них процедуру декодирования. Однако, насколько известно, эти коды не применялись ни в одной из существующих систем связи.

Основные параметры помехоустойчивых кодов

Проблема повышения верности обусловлена не соответствием между требованиями, предъявляемыми при передачи данных и качеством реальных каналов связи. В сетях передачи данных требуется обеспечить верность не хуже 10^-6 - 10^-9 , а при использовании реальных каналов связи и простого (первичного) кода указанная верность не превышает 10^-2 - 10^-5 .

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

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

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

Задача кодирования заключается в получении при передаче для каждой k - элементной комбинации из множества q^k соответствующего ей кодового слова длиною n из множества qⁿ .

Задача декодирования состоит в получении k - элементной комбинации из принятого n - разрядного кодового слова при одновременном обнаружении или исправлении ошибок.

Основные параметры помехоустойчивых кодов:

Длина кода - n;

Длина информационной последовательности - k;

Длина проверочной последовательности - r=n-k;

Кодовое расстояние кода - d₀ ;

Скорость кода - R=k/n;

Избыточность кода - R;

Вероятность обнаружения ошибки (искажения) - Р_ОО ;

Вероятность не обнаружения ошибки (искажения) - Р_НО .

Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) - это число позиций, в которых они отличаются друг от друга.

Кодовое расстояние кода - это наименьшее расстояние Хэмминга между различными парами кодовых слов.

Основные зависимости между кратностью обнаруживаемых ошибок t₀ , исправляемых ошибок t_u , исправлением стираний t_c и кодовым расстоянием d₀ кода:

Стиранием называется "потеря" значения передаваемого символа в некоторой позиции кодового слова, которая известна.

Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим.

Граничные соотношения между параметрами помехоустойчивых кодов

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

Существуют граничные оценки, связывающие d₀ , n и k.

Граница Хэмминга, которая близка к оптимальной для высоко скоростных кодов, определяется соотношениями:

для q-ного кода

для двоичного кода