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

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

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

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

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

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

Классическими примерами неравномерного кода являются код Морзе, широко применяемый в телеграфии, и код Хафмена, применяемый для компрессии информации (факсимильная связь, ЭВМ).

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

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

В неразделимых кодах деление на информационные и проверочные символы отсутствует. К таким кодам относятся, в частности, коды с постоянным весом, так называемые равновесные коды. Например, Международным Консультативным Комитетом по телеграфии и телефонии (МККТТ) рекомендован для использования телеграфный код № 3 - семиразрядный код с постоянным весом, т.е. с числом единиц в каждой кодовой комбинации, равным 3 (W = 3).

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

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

Эти коды получили наибольшее применение в системах передачи дискретной информации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Страницы: 1, 2, 3, 4, 5, 6