Отклонение распределения длительностей полученных кодовых комбинаций от оптимального закона (8.1) будет тем меньше, чем более равными оказывались суммарные вероятности подгрупп символов при каждом разбиении. В случае равенства суммарных вероятностей подгрупп при всех разбиениях код Шеннона-Фано обеспечивает оптимальное статистическое кодирование.

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

8.5. Общая характеристика задачи помехоустойчивого кодирования

Рассмотрим общую постановку задачи помехоустойчивого кодирования при ограниченной длительности кодируемых сообщений. От источника сообщений поступают последовательности символов Ьи Ь2 которые называются информационными последовательностями. При кодировании каждой информационной последовательности Ь\уЬг ... приводится во взаимно-однозначное соответствие передаваемое сообщение (кодовая последовательность) Рь Рг ... В результате действия помех на выходе канала будет принято сообщение Р'ь Р'2 ... часть символов которого может отличаться от символов передаваемого сообщения: Pv * Pv- Если при приеме каждый символ обязательно идентифицируется с одним из символов алфавита канала В (канал без стирания), т.е. всегда PveJ3, то единственной формой ошибки может быть трансформация символов. Если же по некоторым из принятых символов решение об их идентификации с определенным символом алфавита В не принимается и они оказываются вовсе не опознанными (канал со стиранием), то могут иметь место два вида ошибок: трансформация символов и неопознание (стирание) символа. Неопознанные (стираемые) символы обозначим Ф, где Фёй.

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

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

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

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

По способу кодирования различают блочные и непрерывные коды. При блочном кодировании информационная последовательность разбивается на блоки символов (Ьи Ь2,bk) фиксированной длины к, каждому из

которых ставится в соответствие определенная комбинация символов алфавита канала (рь Р2, Р ), называемая кодовым словом. Код при блочном кодировании определяет закон формирования кодового слова, отвечающего данному блоку информационных символов. Для цифровой информации в качестве таких блоков удобно использовать передаваемые числа. В случае систематического блочного кода кодовое слово, отвечающее блоку информационных символов (bhb2, может быть представлено в виде (Ьи Ь2,Ьь р*+ь рл), где p*+i.....Р„ - избыточные

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

информации, что и соответствующий блок информационных символов. При безызбыточности входного сообщения блок из к информационных символов (а значит, и кодовое слово) несет количество информации Н = k\og2 m, где т - объем алфавита источника.

Максимальное количество информации, которое может содержать слово из п символов канала при том же объеме алфавита т, равно

#max=nlOg2m.

Поэтому избыточность кода (л, к)

п 1 Н 1 к\о%2т п-к г гя ~.

Е 1 - - ~т (83)

где г = п - к - число избыточных символов, вносимых при кодировании.

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

соответствующими символами информационной последовательности:

5-1 I

(mod m), у = 0.1...../-1 . (8.4)

v=-<7 J

Значение правой части (8.4) определяется по модулю /я , что означает, что после проведения обычных вычислений удерживается лишь остаток от деления полученной величины на основание кода т (например, 9 по модулю 4 дает 1). Осуществление вычислений в (8.4) по модулю т необходимо для того, чтобы полученные значения символов Р/, принадлежали алфавиту канала, т.е. принимали одно из значений 0,1, т -1.

Рекуррентное соотношение (8.4) на /-м шаге кодирования группе символов входной последовательности bq ... bt... bi+s-i ставит в соответствие / символов кодовой последовательности р,о, .Р/,/-ь на (/+1)-м шаге группе символов fe/+i, смещенной на одну позицию, ста-

вит в соответствие следующие / символов кодовой последовательности Р/+и<ъ Pi+u-i и т.д. Таким образом, каждому символу имформационной последовательности на очередном шаге кодирования по формуле (8.4) приводится в соответствие / символов передаваемой кодовой последовательности, что соответствует избыточности кода ри = (/ - 1) . Правые части рекуррентных соотношений (8.4) представляют как бы свертку соответствующего участка информационной последовательности, поэтому коды и называются сверточными.

Непрерывные (сверточные) коды могут быть как систематическими, так и несистематическими. Систематические сверточные коды получаются в частном случае, когда для одного из значений индекса j (например j = 0) коэффициенты в формуле (8.4) принимают значения

0 при V * 0,

J приУ = 0

и соответственно Рю = Ь,. В этом случае передаваемая кодовая последовательность имеет вид ... Ьи Рл,Pu-ь £/+ь Р*и.ь Р/+и-ь и содержит очередной символ информационной последовательности и / - 1 избыточных символов.

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

Глава 9

БЛОЧНЫЕ КОРРЕКТИРУЮЩИЕ КОДЫ

9.1. Основные характеристики и корректирующие свойства блочных кодов

В блочных корректирующих кодах (л, к) любому блоку информационных символов фи Ьг,Ьк) длиною к ставится в соответствие кодовое слово Ъ = (ро, Рь Pn-i), содержащее п символов алфавита канала. Будем считать, что символы информационной последовательности и кодового слова принадлежат одному и тому же алфавиту объема т и могут принимать значения 0,1.....т-1.Из общего количества кодовых слов данной

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

В случае, когда искажения отдельных символов кодового слова могут рассматриваться как случайные независимые события, вероятность соответствующих искажений кодового слова уменьшается с увеличением кратности ошибок (числа искаженных символов в слове). При этом вероятность трансформации одного кодового слова в другое тем меньше, чем большим числом символов они различаются. Это оправдывает использование для отбора множества Вр разрешенных кодовых слов метрики Хэм-минга, согласно которой расстояние dy между кодовыми словами b{i) и Ьф определяется числом позиций с несовпадающими символами. Например, коды 100111 и 110110, отличающиеся символами в двух разрядах, имеют расстояние по Хэммингу, равное двум.

Минимальное из расстояний dy между разрешенными кодовыми словами

dmin = min{d0}, Ь®ЬфеВр,

Глава 9. Блочные корректирующие коды

называется кодовым расстоянием. Расстояние между переданным (Ь) и опознанным (Ь') кодовыми словами при использовании метрики Хэммин-га определяется числом искаженных символов.

Для исправления ошибок при случайном независимом характере искажений отдельных символов рационально использовать следующее правило декодирования: из всех разрешенных кодовых слов Ь(1)еВр в качество оценки принятого слова Ь' выбирается то, которое минимизирует расстояние d (b\ b{l)). Минимальному расстоянию d (b\ bU)) соответствует минимум искажений переданного слова Ь{1\ Поэтому при приеме слова V гипотеза о том, что передавалось слово является наиболее вероятной. Таким образом, сформулированное правило декодирования соответствует критерию максимального правдоподобия (см. § 3.2).

В случае, когда распознавание отдельных символов ведется без учета корреляционных связей между ними (так называемый посимвольный прием), а распознавание кодовых слов (декодирование) производится без учета корреляционных связей между отдельными словами, составляющими сообщение, это правило может считаться оптимальным. Однако при реализации приема сообщения в целом, когда принятие решения производится с учетом не только условных вероятностей искажений отдельных разрешенных кодовых слов, приводящих к их трансформации в принятое слово Ь\ но и априорных вероятностей тех или иных реализаций сообщения в целом, оптимальное правило декодирования должно основываться на критерии максимума апостериорной вероятности сообщения. Естественно, что прием в целом, когда при декодировании учитываются все статистические свойства источника сообщений, обеспечивает более высокую достоверность. Например, при чтении неразборчивой рукописи, используя для распознавания отдельных слов контекст, человек эвристически реализует прием в целом . В £вязи с технической трудностью реализации приема в целом в практике связи в настоящее время наиболее часто используется посимвольный прием и декодирование по критерию максимального правдоподобия. Правда, за последнее время все большее внимание привлекают так называемые методы последовательного декодирования, позволяющие реализовать прием в целом для участков сообщения заданной длительности (см. § 10.3). В дальнейшем всюду (кроме специально отмеченных случаев) будет подразумеваться посимвольный прием.

В канале без стирания, когда каждый символ на выходе канала обязательно идентифицируется с одним из символов алфавита, максимальное число ошибок иШХ9 при котором факт искажения кодового слова достоверно обнаруживается, определяется равенством

max = dmin - 1 . (9.1)

При числе ошибок 1 искаженное кодовое слово не может сов-

пасть ни с одним из разрешенных слов и факт искажения обнаруживается всегда. Могут быть случаи обнаружения факта наличия ошибок и при u>dmin- 1, но не всегда (а значит, недостоверно). Максимальное число достоверно исправляемых ошибок W определяется неравенством

W<№un-l)/2 (9.2)

При выполнении условия (9.2) ближайшим по метрике Хэмминга к принятому обязательно будет переданное кодовое слово и сформулированное правило декодирования обеспечит правильное исправление ошибок.

Следует иметь ввиду, что исправление ошибок приводит к повышению вероятности имитации противником разрешенных кодовых слов при организации помех (понижению имитостойкости канала). Понижение имитостойкости будет тем большим, чем выше корректирующая способность исправляющего ошибки кода. При полном использовании корректирующей способности такого кода, когда любое принятое кодовое слово идентифицируется с одним из разрешенных слов, для создания имитационной помехи достаточно воспроизводить в любой последовательности символы алфавита канала без учета структуры кода. Поэтому не всегда имеет смысл полностью реализовывать корректирующую способность кода при исправлении ошибок. В высоконадежных каналах с относительно малой вероятностью искажения отдельных символов для повышения имитостойкости целесообразно искусственно ограничивать число исправляемых ошибок t значением, меньшим (d-l)/2, отождествляя принятые кодовые слова с одним из разрешенных только в случае, если расстояние между ними не более и В этом случае, исправляя до t ошибок, можно достоверно обнаружить факт искажения кодового слова при числе ошибок, большем t, но не превышающем величину итах, удовлетворяющую условию:

max = 4nin - t - 1; Г < (dmin - 1)/2 . (9.3)

При большем числе ошибок принятое слово может оказаться на расстоянии, не превосходящем t от другого (непередаваемого) слова, и будет с ним идентифицировано. Таким образом, в рассматриваемом случае при

числе ошибок ut они достоверно исправляются, при числе ошибок t<ud - t - I достоверно обнаруживается факт искажения переданного кодового слова, а при t>u>d - t - \ может иметь место неверное исправление принятого слова.

В каналах со стиранием достоверное восстановление переданного кодового слова при отсутствии трансформированных символов обеспечивается при числе стертых символов s, удовлетворяющем условию:

J <U-1 . (9.4)

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

max = rfmin 5 - 1 ; (9.5)

максимальным числом достоверно исправляемых ошибок, в соответствии с (9.2) равным

<(4тп-*-1)/2; (9.6)

максимальным числом достоверно обнаруживаемых ошибок при исправлении t ошибок, в соответствии с (9.3) равным

max = 4тйп-S-- U t< (dnfo - S - 1 j/2 . (9.7)

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

называемые простые или примитивные коды), ближайшие разрешенные кодовые слова отличаются всего одним символов (dmin= 1) и такие коды не обладают корректирующей способностью. Кодовое расстояние будет тем большим, чем большей будет избыточность кода и чем равномернее будут расстояния между разрешенными кодовыми словами. Коды, у которых заданная корректирующая способность достигается при минимальной избыточности Ритш, называются оптимальными. Коды, которые исправляют все ошибки заданного вида, и при этом множества Вр разрешенных и Ви искаженных заданными ошибками кодовых слов исчерпывают все возможные кодовые слова (при заданных длине и основании кода), называются совершенными. Оптимальный код может не быть совершенным.

Рядом авторов получены соотношения, определяющие связь между избыточностью и кодовым расстоянием для оптимальных кодов. Так, граница Плоткина дает верхнюю границу кодового расстояния rfmin при заданных основании кода т, числе элементов кода п и числе информационных символов k [26]:

4йп (тк-тптк-\т-~ 1). (9.8)

Граница Варламова-Гилберта дает нижнюю границу для числа избыточных символов г, необходимого для обеспечения кодового расстояния dmin [26]:

m>l+X CWm-iy, (9.9)

где CVi - число сочетаний из п - 1 элемента по i элементов. В частности, в случае двоичного кода (га = 2) неравенство (9.9) принимает вид

Если случайные независимые искажения отдельных символов кодового слова характеризуются вероятностью Ре, то вероятность неправильного опознавания слова при простом коде, содержащем п символов,

pJSri-a-ft) . (9Л1)

Вероятность ошибки при использовании исправляющего корректирующего кода с кодовым расстоянием d an не превышает вероятности появ-

ГлаваЯ. Блочные корректирующие коды

ления ошибок с кратностью, больше /,ив соответствии с (2.7) удовлетворяет условию

Pcl CD>=Sl-SciлPЛ-/>e),- (4*-1У2. (9-12)

Вероятность PM , как видно из сравнения (9.11) и (9.12), меньше вероятности ошибки для простого кода на величину

XC P((l-Pt) -.

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

Pcli-lc.a-p,)-, (9.13)

/=о

т.е. еще меньше.

Из проведенного рассмотрения общих свойств блочных корректирующих кодов следует, что и по своему характеру, и по результатам задачи оптимального помехоустойчивого кодирования последовательностей символов ограниченной длительности принципиально отличается от задачи оптимального кодирования по Шеннону бесконечно длинных последовательностей. Прежде всего такие понятия, как обнаружение факта наличия ошибок, число обнаруженных и исправляемых ошибок имеют смысл только при рассмотрении кодов ограниченной длины. При рассмотрении бесконечно длинных кодовых слов эти понятия лишены смысла: в типичных последовательностях бесконечной длительности при заданной ненадежности канала наличие ошибок обязательно, а число ошибок каждого вида определено статистическими характеристиками канала. Что касается результатов оптимального кодирования, то при кодировании бесконечно длинных последовательностей символов по Шеннону обеспечивается сколь угодно малая вероятность ошибки при минимальной избыточности кода, определяемой соотношением (7.35):

p tf(5fl)/log2m,

где Н {B\l¥) - ненадежность канала; т - объем алфавита канала. При кодировании же блоков символов ограниченной длительности вероятность ошибочного опознавания сообщения, как следует из (9.12), хотя и может быть сделана весьма малой, но остается конечной, избыточность же существенно больше минимально необходимой по Шеннону.

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

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

Рассмотрим некоторые классы регулярных блочных корректирующих кодов.

9.2. Линейные корректирующие коды. Коды Хэмминга

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

При использовании теории линейных векторных пространств кодовое слово Ь длиной п рассматривается как вектор в линейном п-мерном

пространстве кодовых слов Rn, а символы b0,bu bn-X - как его компоненты.

Линейным называется блочный равномерный код, для которого любая линейная композиция кодовых слов (двух или более), принадлежащих множеству разрешенных слов Вр, дает разрешенное кодовое слово, т.е. для любых векторов Ь(0, ЪфеВр и любых значений символов A , XJ9 принадлежащих алфавиту канала, справедливо условие

Ь^АД + А^еЯр. (9.14)

Следует уточнить операции умножения и суммирования символов при линейных преобразованиях кодовых слов. Для того чтобы компоненты результирующего вектора Ь(*} состояли только из символов канала О, 1, т - 1 (а это необходимо для того, чтобы Ъ^к)еВр)9 операции умножения и сложения компонент векторов Ь(,) и Ь0) при линейном преобразовании (9.14) определяются по модулю т. Например, при операциях с троичными символами 0,1,2 получим:

(2 + 1) (mod 3) = 0; (2 + 2) (mod 3) = 1; (2-2) (mod 3) =1.

Осуществление операций умножения и сложения символов кода по моду- лю т придает им свойство замкнутости: в результате этих операций получаются символы принадлежащие исходному множеству. Операции умножения и сложения по модулю m сохраняют свойства ассоциативности, дистрибутивности и коммутативности, присущие обычным операциям умножения и сложения. В линейной алгебре множество, удовлетворяющее условию замкнутости по отношению к двум заданным операциям, обладающим свойствами ассоциативности, дистрибутивности и коммутативности, называется полем Галуа и обозначается GF (т). Тот факт, что по отношению к используемым в преобразовании (9.14) операциям символы кода образуют поле Галуа, позволяет говорить (в терминах линейной алгебры), что линейное пространство векторов кодовых слов Rn строится над полем Галуа GF (т).

В пространстве Rn кодовых слов вводится также скалярное произведение векторов а и Ь:

(аЬ) =

(modm). (9.15)

Векторы (кодовые слова), для который (ab) = 0, называются ортогональными.

Представление передаваемых и опознанных кодовых слов в линейном векторном пространстве R позволяет математически описать искажения кодовых слов вектором ее/? , удовлетворяющим условию

b = b + e, (9.16)

где b и Ь' - вектора передаваемого и опознанного кодовых слов.

Для задания линейного кода можно воспользоваться одним из следующих его свойств:

1. Код, содержащий М-т кодовых слов в разрешенном наборе, может быть задан к линейно-независимыми векторами Ь(0, / = 1,2,к, составляющими базисную матрицу L размером кхп*:

ь(,п ь(*>1

Ро(,) pi(1)... P,i(l)

(9.17)

Множество разрешенных кодовых слов, определяемое базисной матрицей L, обозначим В1. Любое кодовое слово из разрешенного набора В1, определяемого матрицей (9.17), может быть представлено в виде линейной композиции входящих в нее векторов:

к

= £ Xfi® XeGF(m). (9.18)

Нетрудно видеть, что общее число разрешенных кодовых слов, образуемых по закону (9.18), равно числу различных комбинаций из к коэффициентов Xt, принимающих одно из значений 0,1, т- 1 т.е. закон (9.18) обеспечивает образование заданного числа Ы-т различных кодовых слов длиной п. Таким образом, базисная матрица размером кхп задает линейный код (п, к).

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

2. Множеству разрешенных кодовых слов В1, определяемому матрицей L, отвечает некоторое множество В** кодовых слов, ортогональных кодовым словам разрешенного набора: если b(0eZ, a befi , то (bb) = 0. Множество В может быть задано п - к линейно-независимыми векторами, составляющими матрицу Н размером (п - к)хп:

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

Матрица Н называется проверочной. Множество В1* содержит m{n~k) кодовых слов, отвечающих всем возможным линейным композициям векторов, составляющих матрицу Н. Свойства множеств BL и В взаимны: множество В*1 также представляет линейный код, для которого матрица Н является базисной, а матрица L - проверочной.

Проверочная матрица Н так же, как и базисная матрица L, полностью определяет линейный код. Она позволяет представить линейный код (и, к) в систематической форме:

b(0 = (W0, h®, ... W\ Р*(0, - Р„-.(0) (9.19)

где первые к символов bol\ bi(l\ ... Ьк.\1) - информационные, а последние п-к символов Ьк.\1\ р/°, ... p i0) - избыточные, обеспечивающие возможность обнаружения и исправления ошибок (их называют проверочными символами).

Проверочные символы разрешенного кодового слова Ь0) при заданных информационных символах b0{l\ Ь\{1\ ... Ьклх) могут быть определены из п - к линейных уравнений, определяемых условиями ортогональности разрешенного кодового слова кодовым словам проверочной матрицы Н:

Sv = (b(¥+v)) = 0, v = .1, 2, п - к. (9.20)

Уравнения (9.20) можно переписать в виде:

ЪГ%(°=1Ь1%1\ v = 1.2f.(9.21)

Разрешая систему п-к уравнений (9.21) относительно п - к проверочных символов р/°, получим для них линейные выражения вида

Р/° = 1/°> 7 = М+1....,л-1. (9.22)

Формула (9.22) позволяет определить п-к проверочных символов Рь Р*+ь ... Рл-ь разрешенного кодового слова по известным к информационным символам (коэффициенты сц определяющие закон формирования проверочных символов, выражаются через элементы b/*+v) проверочной матрицы Я).

Формула (9.22) является весьма удобной формой задания регулярного линейного кода (л, к), широко используемой в практике связи. При этом для образования разрешенных кодовых слов по известным информационным символам достаточно хранить в памяти к (л - к) значений коэффициентов с/у, водящих в (9.22). Поскольку при задании кода с основанием m для каждого из этих коэффициентов может быть выбрано одно из т значений, то всегда можно выбрать тКп'к) вариантов коэффициентов в (9.22) и построить тКп'к) различных линейный кодов (л, к). Задача заключается в том, чтобы выбрать оптимальный вариант кода.

Критерием наличия ошибок в принятом слове У является нарушение условий его ортогональности векторам b(*+v) проверочной матрицы. Результаты проверки соблюдения условий ортогональности дают л - к значений скалярных произведений.

5У = (ЬЪ(*+У))=Х^>/ У = 1,2,...,л-*, (9.23)

которые могут рассматриваться в качестве компонент некоторого вектора 5, называемого синдромом проверки. Для неискаженных кодовых слов разрешенного набора, удовлетворяющих условиях ортогональности векторам b +v),

Sv = 0, v = l,2, ...,л-*, (9.24)

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

Для двоичных кодов скалярные произведения (9.23) вырождаются в так называемые контрольные суммы, представляющие суммы по модулю 2 символов двоичного кода Ь', отвечающих ненулевым позициям v-й строки проверочной матрицы. При этом равенство нулю синдрома обеспечивается в случае четного числа единиц в коде Ь' на позициях, входящих в каждую из контрольных сумм. Поэтому для двоичного кода проверку на ортогональность (9.23) называют проверкой на четность.

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

Формула (9.25) является частным случаем формулы (9.22) при т = 2, к = л - 1 и суц = 1, \1 = 0,1,л - 2. Единственной контрольной суммой этого кода является сумма по модулю 2 всех символов, включая проверочный:

2>y + ft-i (mod2) = 0. (9.26)

Формула (9.26) является частным случаем формулы (9.21), когда к = л - 1, а все составляющие единственного вектора, входящего в проверочную матрицу, равны единице: Ь(п) = 1 j = 0,1, л - 1. Очевидно, что при отсутствии искажений в канале контрольная сумма (9.26) для опознанного кодового слова равна нулю, а при любом одиночном искажении (или нечетном числе искаженных символов) равна единице. Отличие от нуля контрольной суммы обнаруживает факт (но не место) одиночного или нечетного числа искажений символов принятого кодового слова. При четном числе искажений последние не обнаруживаются. Таким образом, данный код достоверно обнаруживает лишь одиночные ошибки. Кратные ошибки обнаруживаются при нечетном их числе. Обнаруживающий ошибки код Хэмминга обладает кодовым расстоянием d = 2, так как ближайшее к передаваемому разрешенное кодовое слово, отличающееся одним информационным символом, обязательно отличается и значением проверочного символа. Расстояние dn = 2 до ближайшего разрешенного кодового слова имеет место для любого передаваемого слова, что соответствует максимально возможному при данном кодовом расстоянии набору разрешенных кодовых слов. Поэтому код Хэмминга, обнаруживающий одиночные ошибки, является оптимальным. Одновременно он является и совершенным кодом для обнаружения одиночных ошибок, поскольку все возможные кодовые слова либо принадлежат разрешенному набору, либо соответствуют случаю искажения одного символа разрешенного слова.

В исправляющем коде Хэмминга двоичное число, составленное из контрольных сумм (синдром кода) должно определять порядковый номер искаженного разряда кодового слова. Для этого контрольные суммы составляются так, чтобы в сумму 5, входили символы кодового слова, имеющие единицу в ;-м разряде в двоичной записи их порядкового номера. Нетрудно видеть, что при этом символы, порядковый номер которых в двоичной записи выражается единицей у-го разряда, т.е. равен Vx, j - 1, 2, 3,войдут только в одну контрольную сумму Sj. Именно на этих позициях (1-й, 2-й, 4-й, 8-й и т.д.) в коде Хэмминга и располагаются проверочные символы рь р2, Р< . Ре Соответствующим их выбором все

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

Для наглядности двоичная запись номеров разрядов кодового слова сведена в табл. 9.1 (таблица приведена для 15-разрядных кодов).

Таблица 9.1

Порядковый номер

Значение разрядов двоичной записи порядкового номера разрядов кода

Для 15-разрядного кода в соответствии с табл. 9.1 контрольные суммы имеют вид:

52 = p2®b3®b6®b1®bi0®bn®bu®bl5,

53 = P4©fc5©&6©&7©fcl2©fcl3®fcl4©bl5 >

54 = fc®b9®blQ®bn®bl2®bi3®bu®bl5,

(9.27)

где bi - значения информационных символов кода; рь р2, Р4, Ре - значения проверочных символов; Ф - знак суммирования по модулю два.

Значения проверочных символов р/, обращающие в нуль контрольные суммы (9.27), равны

Pi = £3®65®b7®fc9©6ll®fcl3®fcl5 .

Р2 = 3©&6©7©10©11©14©15 > /9 28)

р4 = b5®b6®b1®bn®bn®bi4®bi5, Ps = b9®bio®bn®bi2®bn®bu®bi5.

Процедура формирования исправляющего кода Хэмминга включает, таким образом, следующие операции:

1) расположение информационных символов в порядке возрастания разрядов с сохранением незанятыми разрядов с номерами 21 1, т.е. 1-го, 2-го, 4-го, 8-го и т.д.;

2) вычисление проверочных символов, занимающих разряды с номерами 2м, по формулам (9.28).

Процедура определения передаваемого информационного кода при использовании исправляющего кода Хэмминга включает:

1) вычисление контрольных сумм по формулам (9.27);

2) определение порядкового номера искаженного символа, если не все контрольные суммы равны нулю, и исправление его на другой двоичный символ;

3) выделение информационного кода исключением разрядов с номерами 2м, /= 1, 2,... .

Например, если информационный код имеет вид 10001101 (всюду будем пользоваться записью двоичных чисел в порядке убывания номеров разрядов слева направо), то его символы располагаются в коде Хэмминга в следующей последовательности: lOOpgl lOfMfbPi-Определив по формулам (9.28) значения проверочных символов Рь fb, Рз fU получим следующий код Хэмминга 10011100101 (проверочные символы выделены жирным шрифтом). Еслц, например, при приеме 5-й разряд этого кода ошибочно будет принят как единица, то, вычисляя контрольные суммы, получим Si = 1; S2 = 0; S3 = 1; S4 = 0. Значение синдрома, определяющего номер искаженного разряда в двоичной записи, равно S4S3S2S1 = 0101, т.е. для исправления ошибки требуется изменить символ в 5-м разряде.

Правильное исправление кодового слова при использовании кода Хэмминга имеет место для одиночных ошибок, что находится в полном соответствии с кодовым расстоянием, которое в данном случае равно трем. Действительно, если в кодовом слове изменить информационный символ, двоичная запись порядкового номера которого содержит минимальное число единиц, а именно, две единицы (одну единицу в двоичной записи имеет лишь порядковый номер контрольного символа), то одновременно изменятся два контрольных символа, входящие в те же контрольные суммы. Таким образом, ближайшее к каждому передаваемому слову разрешенное кодовое слово отличается тремя символами. Поэтому исправляющий код Хэмминга, обеспечивая максимальный набор разрешенных кодовых слов при rfmin = 3 является оптимальным. Заметим, что

этот код, если его использовать не в качестве исправляющего, а в качестве обнаруживающего ошибки, как и положено при dm\n = 3, достоверно обнаруживает и 2 ошибки. Действительно, номера двух искаженных символов в двоичной записи отличаются хотя бы одним разрядом, а это значит, что хотя бы в одну контрольную сумму войдет только один из искаженных символов и она изменится.

Нетрудно видеть, что для образования исправляющего кода Хэмминга уже при одном информационном символе требуются два проверочных символа (в двух младших разрядах); при числе информационных символов от 2 до 4 - три проверочных символа (в 1, 2 4-м разрядах); при числе информационных символов от 5 до 11 - четыре проверочных символа (в 1,2,4 и 8-м разрядах) и т.д.

Помимо рассмотренных обнаруживающего и исправляющего кодов Хэмминга, можно использовать комбинированный код, исправляющий одиночные ошибки и достоверно обнаруживающий двойные ошибки. Для этого исправляющий код Хэмминга дополняется еще одним младшим разрядом, равным сумме (по модулю два) всех его разрядов. В этом случае при приеме составляются контрольные суммы исправляющего кода без учета младшего разряда и, кроме того, сумма всех разрядов принятого кода (по модулю два). Если часть контрольных сумм равна единице, то исправление принятого слова по приведенным правилам производится только при условии, что сумма всех символов также равна единице.если же сумма всех символов равна нулю, что свидетельствует о наличии двух или четного числа ошибок, то кодовое слово не исправляется (ибо правильно исправляются только одиночные ошибки), а лишь устанавливается факт наличия двух (или четного числа) ошибок. Таким образом, при числе ошибок не более двух рассмотренный код достоверно исправляет одиночные и обнаруживает двукратные ошибки (при большей кратности возможны пропуск или неверное исправление ошибок). Нетрудно показать, что кодовое расстояние для этого кода равно четырем. Действительно, как было показано, без учета младшего разряда разрешенные кодовые слова отличаются не менее чем тремя символами. Но кодовые слова, отличающиеся в остальных разрядах тремя символами, обязательно (по условию четности) отличаются и младшими разрядами, т.е. разрешенные кодовые слова в целом отличаются не менее чем четырьмя символами. Таким образом^ в этом случае имеет место предельная корректирующая способность (исправление одной и обнаружение двух ошибок), соответствующая кодовому расстоянию dmin = 4. Код обеспечивает максимальный набор разрешенных кодовых слов при d an = 4 и является оптимальным.

9.3. Циклические коды

Формирование циклических кодов основано на отображении кодовых слов элементами алгебры полиномов. Это позволяет помимо операций суммирования кодовых слов и умножения их на символ X, использовавшихся в алгебре векторов, дополнительно ввести операции умножения и деления кодовых слов и получить за счет этого дополнительные признаки разрешенных кодовых слов. Кодовое слово, длиною п9 описывается полиномом степени л - 1, коэффициентами которого являются символы кодового слова:

Ь = Ро + Pi* + Р2Я2 + ... + ря1;сл1. (9.29)

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

1) действия над коэффициентами полиномов (сложение, вычитание, умножение на символ X) должны производиться по модулю га; 2) умножение полиномов должно производиться по модулю х*-1, т.е. за результат умножения должен приниматься остаток от деления обычного произведения полиномов на двучлен хп-\. Первое условие необходимо для того, чтобы коэффициенты получаемых полиномов принадлежали алфавиту канала, а второе - чтобы степень этих полиномов соответствовала длине данного кода л.

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

полиномов по модулю т - символом ©, а разность - символом в.

Циклический код обычно задается порождающим полиномом F(x). Разрешенные кодовые слова циклического кода соответствуют полиномам, кратным порождающему полиному F{x). При этом порождающий полином должен удовлетворять двум условиям: 1) быть неприводимым, т.е. не делиться ни на какой другой полином; 2) на него должен делиться без остатка двучлен вида хп-\ (в данном случае имеется ввиду обычная операция деления).

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