Методическое пособие 640

проверочных символов. В соответствии с этим разделимые коды получили условноеобозначение - (n , k) - коды.

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

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

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

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

151

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

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

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

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

лом.

Наиболее известны среди систематических кодов коды Хемминга, которые исторически были найдены раньше многих других кодов и сыграли большую роль в развитии теории кор-

152

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

Расширенные коды Хэмминга строятся в результате до-

полнения кодов с dmin = 3 общей проверкой каждой из кодовых комбинаций на чётность, т.е. ещё одним проверочным символом. Это позволяет увеличить минимальное кодовое расстояние до dmin = 4.

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

новидности полиномиальных кодов.

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

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

Отметим, что коды Хэмминга также можно получить по алгоритмам формирования циклических кодов [4].

153

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

БЧХ-коды являются обобщением кодов Хэмминга на случай исправления нескольких независимых ошибок. Частными случаями БЧХ-кодов являются коды Файра, предназначенные для обнаружения и исправления серийных ошибок («пачек» ошибок); код Голея – код, исправляющий одиночные, двойные

итройные ошибки (dmin = 7); коды Рида-Соломона (РС-коды), у которых символами кода являются многоразрядные двоичные числа.

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

ипростых способов их реализации.

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

7.3. Общие принципы построения помехоустойчивых кодов

Предположим, что на вход кодирующего устройства поступает последовательность из k (соответствующих кодируемому знаку) информационных символов, которые преобразуются в кодовую комбинацию из n символов, причем n > k. Всего возможно для двоичных кодов 2k различных входных и 2n выходных последовательностей (для кодов с основанием q – соответственно qk и qn). Среди указанных выходных последо-

154

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

1)2k случаев безошибочной (неискаженной) передачи;

2)2k (2п - 2k) случаев, когда разрешенные комбинации помехой трансформируются в запрещенные, но обнаруживаемые;

3)2k (2k - 1) случаев перехода в другие разрешенные ком-

бинации. Такие ошибки не могут быть обнаружены. Поскольку всего случаев передачи 2k · 2п, относительное

число обнаруживаемых ошибок (вероятность обнаружения ошибки) составит

Нетрудно заметить, что при п → ∞ вероятность обнаружения ошибки стремится к единице. Из соображений простоты реализации число п - k проверочных разрядов, характеризую-

щих избыточность кода, ограничивают.

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

ными.

7.4. Линейные коды

Линейные коды были придуманы для того, чтобы исправлять ошибки в каналах связи с шумом. Предположим, что имеется телеграфная линия из Москвы в Санкт-Петербург, по которой можно посылать 0 и 1. Обычно при посылке 0 принимается также 0, но иногда 0 может быть принят как 1 или 1 принята как 0. Будем считать, что в среднем один из каждых 100 символов будет ошибочным. Это означает, что для каждо-

155

го символа имеется вероятность р = 1/100 того, что в канале произойдет ошибка. Описанная модель называется двоичным симметричным каналом (см. раздел 5.1).

По этой телеграфной линии передается много важных сообщений, ошибки р и эти сообщения должны передаваться как можно быстрее и надежнее. Сообщения записаны в виде последовательности из 0 и 1.

Мы хотим закодировать эти сообщения, чтобы как-то защитить их от ошибок в канале. Блок из k символов сообщения u = u1 u2 ... uk ( ui = 0 или 1) будет кодироваться в кодовое слово х = х1 х2 ... хп ( хi = 0 или 1), где n ≥ k (рис. 7.3); эти кодо-

вые словаобразуют код.

Рис. 7.3. Кодирование сообщения

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

х1 – u1 ; х2 – u2 ; … ; хk – uk ,

за которым следуют n—k проверочных символов хk+1,... ,хп. Проверочные символы выбраны так, чтобы кодовые слова удовлетворяли следующему уравнению

где ((n—k) x n) — матрица Н, называемая проверочной матрицей кода, имеет вид

156

Здесь А - некоторая фиксированная ((n—k)x k) - матрица из 0 и 1, а

1

=1

1

- единичная матрица размера (n—k) x (n—k). Все операции в уравнении (7.1) выполняются по mod 2, т. е. 0+1=1; 1+1=0; -1=+1. Мы будем называть это двоичной арифметикой.

Пример. Код # 1

Проверочная матрица

х1 = u1 ; х2 = u2 ; х3 = u3 ,

апоследующих три проверочных символа х4х5х6 выбираются так, чтобы выполнялось уравнение Н·хТ = 0, т. е.

рочные символы легко определяются:

х4=-1-1=1+1=2=0;

157

х5 = -1=1;

х6 =-1=1.

Врезультате мы получим кодовое слово х = 011011.

Уравнения (7.3) называются уравнениями проверки на

четность или проверками на четность для кода. Первое урав-

нение проверки на четность говорит, что 2, 3 и 4-й символы каждого кодового слова должны в сумме давать 0 по модулю 2, т. е. их сумма должна быть четной (откуда и название!).

Так как каждый из трех символов сообщения u1u2u3 равен 0 или 1, то в этом коде имеется всего 23 = 8 кодовых слов. Эти слова:

В коде в общем случае имеется 2k кодовых слов.

Как мы увидим, код # 1 может исправлять одиночную ошибку в канале (в любом одном из шести символов), и применение этого кода уменьшает среднюю вероятность ошибки на символ от р=0,01 до р=0,00215. Это достигается ценой посылки шести символов, только три из которых являются символами самого сообщения.

Определение. Пусть Н - любая двоичная матрица. Ли-

нейный код с проверочной матрицей Н состоит из всех векто-

ров х таких, что НхТ=0 (всеоперации производятся по mod 2). Первые k символов каждого кодового слова являются символами сообщения, или информационными символами, а

последние r = n - k символов - проверочными.

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

7.4.1. Код с повторением

Данный код обозначается как (n,1) код и содержит кодовые слова вида U (a1,b1,b2, ,bn 1), т.е. состоит из одного

158

информационного и n 1 проверочных символов, которые повторяют значение информационного символа, т.е. b1 b2 bn 1 a1, что и объясняет название кода.

Порождающая матрица состоит из одной строки и имеет

вид

G 11 1 ,

так что код с повторением состоит всего из двух слов: одно содержит только одни нули, а второе – единицы. Очевидно, что кодовое расстояние d n, и он может исправлять ошибки кратности t (n 1)/2 и обнаруживать ошибки кратности t n 1. В свою очередь проверочная матрица состоит из n 1 строк и n столбцов и представима как

и указывает, что сумма первого и любого другого символа кодового слова равняется нулю.

При нечетном значении n код не исправляет ни одного сочетания ошибок кратности, большей t (n 1)/2, следовательно, он является совершенным. Если же n – четно, то при ошибке кратности n/2 принять решение о передаваемых данных не представляется возможным.

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

159

Пример. Код #2, код с повторением.

Код с k = 1, п = 5 и с проверочной матрицей

Каждое кодовое слово содержит только один символ сообщения u. Проверочные уравнения имеют вид

x1 + x2 = 0; x1 + x3 = 0; x1 + x4 = 0; x1 + x5 = 0,

т. е. x1= x2= x3= x4= x5= и. Таким образом, имеются всего два кодовых слова: 00000 и 11111. Передаваемый символ просто повторяется 5 раз; поэтому такой код называется кодом с повторением.

7.4.2. Код с простой проверкой на четность

Данный код содержит слова лишь с одним проверочным символом, так что обозначается как (n,n 1) код, слова которого представимы в виде

U (a1,a2, ,an 1,b),

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

b (a1 a2 an 1)mod2.

Очевидно, что b 1, если число единиц в информационной комбинации нечетно, и b 0 в противном случае. Таким образом, наличие подобного проверочного символа позволяет придать всем кодовым словам общий признак: четность числа единиц в кодовом слове.

Порождающая матрица данного кода имеет размерность (n 1) n и представима в виде

160