Непрерывные коды не разбиваются на блоки

Непрерывные коды не разбиваются на блоки

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

К числу основных характеристик кода относятся длина кода n, его основание m, мощность N (число разрешенных кодовых комбинаций), полное число кодовых комбинаций N0, число информационных символов k, число проверочных символов r = N — k, вес кодовой комбинации (число единиц в комбинации), избыточность кода и кодовое расстояние. Избыточность кода определяется выражением:

Непрерывные коды не разбиваются на блоки

Наименьшее расстояние Хемминга для данного кода называется кодовым расстоянием d.

При независимых ошибках в канале через кодовое расстояние удобно выражается корректирующая способность кода. Если код имеет d = 1, то две кодовые комбинации отличаются минимум в одном символе. Искажение одного символа сразу трансформирует кодовую комбинацию в другую разрешенную, т.е. код с d = 1 не способен корректировать ошибки. Чтобы код мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, можно получить, что для обнаружения всех ошибок кратности l требуется код с расстоянием:

Непрерывные коды не разбиваются на блоки

Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, нежели для их обнаружения. Если кратность исправляемых ошибок равна l, то кодовое расстояние должно удовлетворять условию:

Непрерывные коды не разбиваются на блоки

Линейные и нелинейные коды

Линейные и нелинейные коды

Среди разделимых кодов выделяются коды линейные и нелинейные. К линейным относятся коды, в которых поразрядная сумма по модулю 2 любых двух разрешенных кодовых слов также является разрешенным кодовым словом. Линейный код называется систематическим, если первые k символов любой его кодовой комбинации являются информационными, а остальные (n — k) символов — проверочными.

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

Вероятность необнаруженной ошибки в первом приближении можно определить как вероятность искажения двух символов:

Линейные и нелинейные коды

style="display:block; text-align:center;"
data-ad-format="fluid"
data-ad-layout="in-article"
data-ad-client="ca-pub-6007240224880862"
data-ad-slot="8925203109">

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

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

Например, таким является код: 00000; 00101; 01001; 01110; 10001; 11010, 11111. Коды Бергера применяются, как правило, в асимметричных каналах. В симметричных каналах они обнаруживают рее одиночные ошибки и некоторую часть многократных.

Блочные коды

Блочные коды

Блочные коды бывают разделимыми и неразделимыми. К разделимым относятся коды, в которых каждый из символов может быть отнесен к одной из двух непересекающихся групп: информационные символы, несущие сообщение, и проверочные, служащие исключительно для обнаружения и исправления ошибок. Такие коды принято обозначать парой чисел (n, k:), где n — длина кода; k — число информационных символов.

Число разрешенных комбинаций в коде (n, k) не превышает 2k неразделимым относятся коды, у которых нельзя выделить информационные и проверочные символы. Неразделимые коды — это, например, коды с постоянным весом и коды на основе матриц Адамара. Коды с постоянным весом характеризуются тем, что все их кодовые комбинации содержат одинаковое число единиц. Примером такого кода является стандартный телеграфный код, у которого в каждой кодовой комбинации по три единицы и четыре нуля (код «3 из 7»: (7,3)).

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

Блочные коды

Код можно задать таблицей

Код можно задать таблицей

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

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

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

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

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

Искажения помехами

Искажения помехами

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

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

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

При построении корректирующих кодов из N0 возможных комбинаций по n символов применяется лишь некоторая часть N<N0. Используемые при передаче N комбинаций символов обычно называются разрешенными кодовыми комбинациями, а остальные N0 — N — запрещенными. Если под действием помехи передаваемая кодовая комбинация трансформируется в запрещенную, то при некоторых условиях такую ошибку можно обнаружить и даже исправить.

Страница 2 из 212
Яндекс.Метрика