вполне очевидно, так как кодирование и декодирование в непрерывном канале являются более общими процедурами, чем в дискретном,
Далее можно снова обратиться к достаточному условию (6.4) для убывания вероятности ошибки к нулю при использовании ортогональных сигналов, которое было получено ранее. Этому случаю соответствует непрерывный канал связи с бесконечной полосой пропускания, для которого пропускная способность определяется выражением (6.S4V Поэтому необходимое и достаточное условие обеспечения высокой надёжности передачи в таком канале в действительности будет иметь вид
v< 1,44/V/V,,                                                    (6.S8)
Сравнение (6.4) и (6.86) показывает, что простой вывод достаточного условия (6.4) дает в 2 раза меньшую скорость, чем действительно достижимая скорость передачи-
Для непрерывного канала остается справедливой также и основная теорема Шеннона, если в ней понимать под С' пропускную способность непрерывного канала.
Для канала с пропускной способностью С', на вход которого подключен непрерывный источник, обладаюшии е-производительностью //^(^'). К. Шснногз доклад следующую теорему [27f. если при заданна критерии эк^ванентностн сообщений источника s'i его е-^извйдитйпьность ^(.Т) меньше пропускнои способности канала С . то сущестцует способ коанробання и декодирования {преобразования сообщения б канальный сигнал и обратно - канального сигнала в сообщение}, при котором неточность воспроизведения с^онь угодно блпзкс к ^. Прг Н'^} > С' такого способа пе существует,

Формула Шеннона (6,83) может быть использована для оценки потенциальных возможностей непрерывного канала связи не только относительно его энергетики, но и занимаемого им спектра,
Действительно, используем два важнейших показателя системы связи, ко-
гирое уже определены в ^ 5,8: энергетический параметр S^=PJ[N^R\ и частотную эффективность у = R^/F .
^ Рлэумеетси, что, удовлетворяя нераненство ^ц < ^д можно иметь различные; величины для длительности сигнила Т,, и времени использонания канал,! 7^ при варИЕШИН другнл пирЕшет-рпв,
253

В соответствии с теоремой Шенноня, полагая При оптимальном согласона-нии дискретного источника и непрерывного гауссовского канала /^ = С\ из t6.S3} имеем

т.е. минимально необходимая битовая энергия экспоненциально возрастает при возрастании спектральной эффективности.
Если говорить о реальных системах связи, то, используя, например, ///-ичный ортогональные сигналы (ЧМ) для т = S, 16, 32, можно получить при вероятности ошибки на бит р^ = 10~5 ру-номограммы, соответствующие точкам,
указанным на рис, 1 LI (у < 0 дБ). Чтобы в этой области приблизиться к предельной кривой, необходимо использовать помехоустойчивое кодирование, которое описано в следующей главе.
Что же касается области ру-номограмм при у > 0 и вблизи предельной кривой, то она оказывается весьма трудно достижимой для реальных систем связи. Даже для того, чтобы получить у> (2-4) и ^<(10-12) [д&], приходится использовать комбинированные методы многократной фазовой и амплитудной модуляции. Дальнейшее же приближение к предельной кривой в данной области возможно только при совмешении кодирования и модуляции, т.е. в так называемых системах связи с кодированной модуляцией. О принципах их построения говорится в гл. 7 и 11.
6.3.4. ПОТЕНЦИАЛЬНЫЕ ВОЗМОЖНОСТИ КАНАЛОВ СО МНОГИМИ ПОЛЬЗОВАТЕЛЯМИ
В предыдущем разделе данной главы рассматривалась модель системы связи, и которой имеется один HCTO'tHEiK и один получатель, а передача сообщений производится по единому каигшу связи,
В последнее время значительное внимание уделяется так называемым сетям связи, реализующим обмен информацией между большим количеством абонентов, которые соединены между собой при помощи множества раздслённщ или общих каналои сиязн. Обшая структуры такой системы со многими пользователями показана на рис. 6,6- Здесь имеется: множество источников сообщений ИС|, НС^ .., ИС/^ множество передающих устройств пу|, „., ПУ^, множество приемных устройств ПрУ|, .., ПрУ/,, множество получателей П|, ... П^ н сеть ка-
254

налои, соединяю шик передающие и приемные устройст-на. В общем случае каждому источнику доступно некоторое подмножество    передающих устройств, у получателям сообщен ий ДОСТУПНЫ' ВЫХОДЫ
некоторого     подмножества приемных устройств. Основная задача передачи сообщений в такой системе связи ос

тается прежней - необходимо максимизировать скорости передачи сообщении при-сколь угодно высокой верности приема, Однако a отличие от случаи с одним источником и получателем здесь но^никаст множество допустимых скорости передачи между определенными источниками и получателями. Такая постаноика задачи приводит к понятию области допустимых скоростей передачи, приводящих к надежной передаче сообщений.
Каиболее частыми случаями такой системы сия:аи является канал с миожсствгичым доступом, когда один и тот же канал сиязи используется для передачи сообщений от нескольких нсгочников к одному и тому же получателю, и так называемый широк(т^щатеиьный канал. когда одно и то же сообщение передаётся нескольким лолу|атслям.
В fl6| рассмотрено обобщение теоретико-информационных понятии дл<1 данной системы сш^и и доксйаны теоремы кодировании, определяющие области достижимых скоростей передачи при сколь угодно малых вероятностях ошибок.
Существует и иная постанонка задачи, когда один из получателей является нЕдрулссствеч-иым (иначе гоноря, он еоотпетствуст каналу подслушинания}- Тогда згщача кодирова|ЩЯ состоит в минимизации ко-личества иг [формации, поступающей к недружественному пияу»ателю П|)И максимизации ско|юсти передачи информации для ^ружеситгтюго получате;1Я.
В настоящее время достаточно разработаны и кон структи иные методы кодирования и декодирования для каналов со многими пользователями, однако изложение этого материала иьгходит 'Kt рамки даннот учеоника.
ВЫВОДЫ
I- Сообщения источника с избыточностью могут быть "сжаты", т.е. закодированы более экономно посредством согласования алфавитов источника и канала связи. Предельные возможности сжагия определяются такой характеристикой источника сообщений, как энтропия, зависящая от статистических свойств сообщений.
?- Потенциальные возможности по скорости для передачи достоверной информации по ка-на^чам связи с помехами определяются пропускной способностью каналов сич^и- Эта характеристика ^анисит от распределений помех и параметроЕ каналов суя^и.
3. Пропускная способность 2СК без памяти зависит только от вероятности ошибки символа р в к,шале связи. Она максим-шьна при р = 0 или /' = 1 и раина нулю при р =- 1/2. когда наступает обрыи канала свя^и.
4. Пропускная способность непрерывного гауссовского к-щала связи зависит от отношения сигнал-шум и полосы частот канала. При неограниченном расширении полосы частот канала пропускная способность стремится к конечной келичинс.
ВОПРОСЫ, ЗАДАЧИ И УПРАЖНЕНИЯ
G.]   Если и /п-ичнои системе свизи с ортогональными сигналами средняя мощность сигналов и спектральная плотность шума постоянны, то что нужно сделать, чтобы обеспечить стрсм-чиние к нулю иероятности ошибки при сохранении постоянной информационной скорости передачи?
6.2. Что такое кодиронание и декодирование а дискретном и непрерывном каналах связи? Что у них общего и чем они отличаются друг от друга?
6.3. Какие виды модуляции-демодуляции приводят к модели двоичного симметричного канала, ,1 какие к модели несимметричного капала?
255

6.4. Что изменится, если при определении всех информационных понятий изменить основание логарифма? Повлияет ли это на основные результаты, которые даст теория информации?
6-S. Свойства энтропии, условной энтропии, количества информации могут быть пояснены интуитивно- Однако если бы это было не так» то сохранились ли бы основные результаты теории информации?
6.6. Чем хорош или плох источник информации, обладающий большой энтропией?
6.7. Во сколько раз можно сжать русский текст, передаваемый заглавными буквами (А'=32), если считать, что энтропия источника, ныдаюшего этот текст, Я{Л) = 1,5 бит/символ.
ЬЯ- Модно ли при помощи взаимной информации !{Х, У} измерять степень зависимости случайных величин Хи У? Если это так, то чем это лучше оценки степени зависимости при помощи коэффициента корреляции?
6.9. Энтропия дискретного источника на входе канала Я(А) = 5 бит/символ, потери в дискретном канале без памяти ВД'|Г) ^ 0,2 бит/символ. Найдите энтропию шума в канале, если энтропия символов на выходе канала ЩУ') =• 5,5 Йит/символ-
6.10. Имеет ли смысл понятие пропускной способности канала без его использования и теоремах кодирования?
й-11 Докажите, что для двоичного по в^оду стирающего канала с вероятностями псрсходоь (6.6) пропускная способность (бит на символ) С = (1 - рц)
6.12. Поясните наглядно смысл того факта, что при одном и том же значении рс = р пропускная способность 2СК без памяти будет всегда меньше, чем пропускная способность диоичного по входу стирающею канала.
6.13. Каково назначение кодирования в канале без помех?
6.14- Соотношение (6.46) выполняется как и теореме 1, так и в теореме 2 для каналов без помех- В чем состоит отличие выполнения этого соотношения в данных теоремах?
6-15. Какое практическое значение имеет теорема кодирования и канале с помехами? Можно ли, используя доказательство этой теоремы, строить реальные схемы кодирования и де-кодиронания?
6-16. Во сколько раз уменьшается дифференциальная энтропия равномерно распределённой случайной величины (е нулевым МО) по сравнению со случаем гауссодского распределения, если фиксироцана дисперсия случайной величины?
и 17. Является ли гаусеовская помеха наихудшей (и если да, то il каком смысле) среди псех аддитивных помех одинаковой мощности?
6.1В. И'! графика рис. 6-4 следует, что при расширении полосы частот канала связи пропускная способность нсегда остается меньше, чем С' . Имеет ли тогда практический смысл
расширять полосу частот линий связи (например, кабельные) сверх такого значения fq, лри котором C'(/^)sC' ?
256

ГЛАВА 7. КОДИРОВАНИЕ ИСТОЧНИКОВ И КАНАЛОВ СВЯЗИ
В предыдущей главе были установлены потенциальные возможности кодирования источников и каналов, которые определялись теоремами кодирования Шеннона- Однако ни формулировки, ни доказательства этих теорем не указывали прямо на способы кодирования и декодирования, которые обеспечивают эти потенциальные возможности. (Исключением было лишь кодирование в непрерывном канале с неограниченной полосой частот, когда постоянная скорость передачи при сколь угодно малой вероятности ошибок могла быть обеспечена при выборе ортогональных сигналов).
Хотя исторически некоторые способы кодирования источников и каналов появились даже раньше теории Шеннона, она явилась мощным стимулом для поиска многих других, более эффективных методов, приближающихся к потенциально возможным. Это обстоятельство вызвало большой поток работ, посвящённых тематике конструктивных методов кодирования. В данной главе будут описаны основные подходы к кодированию источников и каналов связи, причём в отличие от математической теории кодирования мы остановимся здесь не столько на деталях доказательств различных свойств кодов, сколько на демонстрации энергетических, скоростных или спектральных выигрышей, которые обеспечивают данные методы по сравнению с "некодированной" передачей сообщений,
Под кодированием б широком смысле понимают отображение сообщения в сигнал для передачи его по каналу.
Под кодированием в узком смысле понимают преобразование сообщении дискретного источника для передачи их по дискретному каналу. Если иное не указано, под словом кодирование далее будет подразумеваться кодирование в узком смысле.
Реализация кодирования на передающей стороне всегда предполагает применение обратной процедуры — декодирования — для восстановления принятого сообщения. Устройства, осуществляющие кодирование и декодирование, называются соответственно кодер и декодер. Вместе их называют к-одеком.
7.1. КЛАССИФИКАЦИЯ МЕТОДОВ КОДИРОВАНИЯ
Классификация рассматриваемых в данной главе методов кодирования приведена на рис, 7.1. Эта классификация не является исчерпывающей. В нее включены лишь некоторые методы, которые широко используются в современных системах связи. По своему назначению кодирование подразделяется на примитивное, экономное и помехоустойчивое.
Примитивное^ или безызбыточное, кодирование применяется для согласования алфавита источника и алфавита канала,
Пример, приведённый в табл. 7.1, показывает, как сообщения дискретного источника с объёмом алфавита K=1 4 могут быть преобразованы для передачи по дискретному двоичному каналу. Отличительное свойство примитивного кодирования состоит в том, что избыточность дискретного источника, образованного выходом примитивного кодера, равна избыточности источника на входе кодера,
257

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

Экопомное кодирование, или сжатие банных, применяется для уменьшения времени передачи информации или требуемого объёма памяти при ее хранении. Отличительное свойство экономного кодирования состоит в том, что избыточность источника, образованного выходом кодера, меньше, чем избыточность источника на входе кодера- Экономное кодирование применяется в ЭВМ. Так, последние версии операционных систем обязательно содержат в своём составе программы сжатия данных (динамические компрессоры и архиваторы), а нобый стандарт V,42bis на модемы для связи между ЭВМ по телефонным сетям общего пользования включает сжатие в число процедур обработки данных.
Помехоустойчивое, или избыточное, кодирование применяется для обнаружения и(или) исправления ошибок, возникающих при передаче по дискретному каналу. Отличительное свойство помехоустойчивого копирования состоит в том, что избыточность источника, образованного выходом кодера, больше, чем избыточность источника на входе кодера. Помехоустойчивое кодирование используется в различных системах связи, при хранении и передаче данных
258

в сетях ЭВМ, в бытовой и профессиональной аудио- и видеотехнике, основанной на цифровой записи.
7.2. КОНСТРУКТИВНЫЕ МЕТОДЫ КОДИРОВАНИЯ ИСТОЧНИКОВ СООБЩЕНИЙ
Существует множество способов кодировании источников сообщений, Многие способы реализованы на практике, особенно для сжатия сообщений с большой избыточностью, например факсимильных и телевизионных, где они позволяют увеличить скорость передачи сообщений в десятки раз (см.глЛ!). В данном параграфе мы рассмотрим сначала кодирование источников с известной статистикой сообщений. Общая идеч построения такого кода подсказывается теоремой кодирования 1 для каналов без помех. Поскольку минимизируется средняя длина кодовой последовательности, то коп должен быть неравномерным. Очевидно, что средняя длина неравномерного кода будет минимизироваться тогда, когда с более вероятными сообщениями источника будут сопоставляться более короткие комбинации канальных символов. Проблема, однако, состоит в том, что у неравномерного кода на приёмной стороне оказываются неизвестными границы атих комбинаций. Если же мы попытаемся их выделить, используя известный способ кодирования, то декодирование может оказаться неоднозначным. (Действительно, если, например, с буквой А сопоставлена комбинация 0, с буквой Б - 1, а с буквой С — 10, то невозможно определить по принятой комбинации 10, передавались ли буква С или пара букв Л и Б), Для того чтобы используемый код обладал свойством однозначной де-кодируемости, он, очевидно, должен удовлетворять некоторым условиям. Однозначное декодирование будет обеспечено, если ни одно кодовое слово не является началом другого кодового слова. Такие коды называются префиксными,

259

Эта система неравенств и определяет способ построения кода с данным наоором кодовых длин. Сначала выберем \v\ слон длиной 1. используя для этого различные буквы из алфавита объёма ffl- Остается m - w^ не использованных символов, и поэтому мы можем построить {in - ivi)w 1:лов длиной 2. добавляя к ним по символу из алфавита объема т. Из этих слов
длины 2 выберем и^ произвольных слов» что составляет m2 ~w^m-w^ "свободных" префиксов
длины 2- Добавляя к этим префиксам разные символы алфавита, получаем {т -w^n-\v^}w
слои длиной 3, ич которых выберем щ произвольных слов и т.д. Продолжая таким образом, мы построим префиксный код, длина комбинации которого удовлетворяет неравенству Краф-
та (7.1).-
Рассмотрим теперь некоторый источник дискретные сообщений без памяти, который согласно § 6.1 однозначно определяется своим алфавитом А объёма /^ и вероятностями появления символов До;), 1=0, 1, ..^ К— 1- Тогда если последовательности символов, выдаваемые этим источником, разбить на блоки длины п, то каждый из таких блоков можно рассматривать как символ нового источника с укрупнённым алфавитом Ау объёма Ку=К" и вероятностями появления символов Р(^У i = 0, 1, „,, Ку- I, определяемыми как произведение
вероятностей первичных символов, входящих в данные блоки. Определим длины блоков а н&рав номерного кода, описанного в теореме 7>1, следующим образом-

и поэтому по теореме 7.1 можно символами источника с укрупненным алфавитом сопоставить последовательности символов т-ичного канала бе^ помех, имеющие длины ^. Тогда для средней длины такой последовательности

Учитывая тот факт, что для источника без памяти Я(Ау) = /i/^(A) и, кроме того. относя эту величину к одному символу источника, получаем

260

Фактически мы доказали теорему кодирования для каналов без помех и источнике! без памяти. Более того, было доказано, что предельное 'шачение средней длины я/и может быть получено при копировании при помощи неравномерного префиксного кода с длинами последовательностей, выбранными в со-отнетствии с (7.4), Остаётся показать, кок может быть построен такой префиксный код. Существует несколько алгоритмов построения неравномерных кодов с префиксным свойством. Среди них оптимальным, т.е. позволяющим сколь угодно приближаться к пределу (7.5), является алгоритм Хаффмена [8|. Однако рассмотрим здесь более простой алгоритм Шеннона-фано, который и большинстве случаев приводит к тем же результатам.
Алгоритм Шеннона-Фано заключается в следующем. Символы алфавита источника (первичного или укрупнённого) записываются н порядке не возрастающих вероятностей. Затем они разделяются на дне части так, чтобы суммы вероятностей символов, входящих в каждую из таких частей, были примерно одинаковыми. Всем символам первой части приписывается н качестве первого символа комбинации неравномерного кода ноль, а символам втором части — единица. Затем каждая из этих частей (если она содержит более одного сообщения) делится в свою очередь на две, по возможности равновероятные части и к ним применяется то же самое правило кодирования. Этот процесс повторяется до тек пор, пока в каждой из полученных частей не останется по одному сообщению.

Заметим, что хотя деление на части с "примерно равными вероятностями" не является однозначной процедурой, но при увеличении длин блоков п укрупнеНЕЮго источника сообщений эти погрешности будут сглаживаться, а средняя длина п/п приближаться к предельному значению (7.5).
ПераВНОМСрНОС ПрсфНКСНОС КЛДЧрОВ;1НИС устраняет «убыточность истотнчки, иьп1^1нцую неодинаковой иероятносп^ю сообщении. Если источник имеет память, то псроятность пояьлсЕШя очередного сообщен и ч 'клиент от того. к.жое сообщение появилось перед ним-

H-i ПСрЛОМ УТ.1ПС уСТрЯНСНИЯ И^быТОЧНОС-т ДИеКрСТНОГО ИСТОЧНИК;! С: ii.im^itlk) ИИДИННЫН
источник вменяют экий валентным источником бел п^1М>1ТИ с помощью .мстодч укрупнения
^Лф.ПШТЧ. прсдст^внм. Н.ШрНМСр, ДНеКрСТПЫ К ИСТОЧНИК С ;Ц1ф,1ИЦТГ»^ {|Т,[,Г^О.З. h,lK IIOULin
источник с ;1лф,1Еитол1 {f|,a,}, j. j= 0.5, т л. » качестве одного укрупненного сообщения n;i иы-
хпдс источнику теперь psiecM отрицается ди;! последовательных сообщения. ec-'hi источник не 261

нании для ноього источника с укрупнен ним алфавитом. При такой схеме кодирования остается неучтенной статистическая зависимость ме?кду укрупненными сообщениями. Поэтому алфавит необходимо укрупнять до тех пор, пока избыточность, вызванная статистическими спаями между укрупнёнными сообщениями, не станет достаточно малой.
Более реалистичной является» конечно, ситуация, когда о некотором избыточном птичнике известен лишь его алфаипт А, но не известно рас пределе! та иероятностсй последовательностей симиолов этого источника. Например, необходимо сконструировать диоичный префиксный код для передачи текста на различных языкам, имеющих общий алфавит, Казалось бы, эта задача является неразрешимой, но в де Нети ительн ости удаётся сконструировать некоторый у ни нереальны и сжимающий код.
Рассмотрим кратко метод сжатия подобного типа, известный как алгоритм Зшш-Лсмпсл.э и широко применяемы!! и ЭВМ для архиниродания файлои. Обшая идея данного метода состоит II том, что последовательность символов источника разбивается h.i кратчайшие различимые цепочки, которые не встречались раньше, ;i затем эти цепочки кодируютии ргпжомер-hljm кодом. Нппримср, если последовательность имела вид 101 КНОЮШЮ, то она будет разби-т;1 на цепочки следующим образом. 1, 0, I], 01, ОЕО, 00. Ifl. При таком способе разбиения нес префиксы данной цепочки могут находиться лишь слева от нес, В частности, цепочка, которая отличается от данной лишь и последнем симиолс (бите), всегда будет рае пол агаты:» cnciiii. Если с{ц} означает число различных цепочек разбиения для данной последовательности длины л, то необходимо log^cfrt) бит, чтобы закодировать номер префикса к данной цепочке и
ещё один бит для описания последнего элемента этой цепочки. Так, для рассмотрен но л выше по следовлтель нести и её разбиении мы" получим следующий равномерный код' (000, 1) «ЮО, «) (001, I) [010. I» (Ull, 0) (010, 0) (001, 0). где перкыс три бита определяют номер префикса к очередной цепочке, а последний бит д.ьёт значение последнего символа этой цепочки. Очецидно. что декодирование такого кода производится однозначным образом.
Рассмотренный пример даст фактически не сжатие, а "растяжение" сообщений, поскольку иместо U исходных бит мы получаем 2Й бит. Однако для длинных последовательностей сообщений эффективность .щгоритма увеличивается, и к асимптотике, т.е. при и -> ю, сжатие сообщений приближается к предельно возможному, определяемому теорЕмой кодиронання в Kiinane Ge'i помех, а именно доказывается» что для любого стационарного эр годи ч ее кого ис-го'1ника сообщений

Заметим, что фактически для сжатия файлов используется модифицированный алгоритм, называемый алгоритмом сжатия Зива-Лсмпела-Велча. на осноне этого алгоритм;! построены наиболее эффективные программы архивирования файлов такие как PKAR.C, PKZIF, 1CE и
ди.
7.3. ПОМЕХОУСТОЙЧИВОЕ (КАНАЛЬНОЕ) КОДИРОВАНИЕ
Если экономное кодирование сокращает избыточность источника ссюбще-нми, то помехоустойчивое кодирование, напротив, состоит в целенаправленном введении избыточности для того, чтобы появилась возможность обнаруживать и(или) исправлять ошибки, возникающие при передаче по каналу сйячи,
В   дальнейшем   будем   рассматривать  только   чисто   канальное (помехоустойчивое) кодирование, хотя общий подход также возможен и, более того, даёт весьма значительный эффект, особенно при передаче преобразованных к дискретному виду непрерывных сигналов (см. гл, 8),
Переходим к изложению общей теории блоковых кодов. Будем называть канальным (помехоустойчивым) блоковым кодом ^любое множество из М различных последовательностей (комбинаций, слов) \i, х;, х^, --, хд/ длины /т,
262

Очевидно, избыточные коды имеют R < 1, а для примитивного кода R = }. ТсоремЕ! копирования Шенмона, показанная в предыдущей главе, утверждает, что существует такая последовательность блоковых избыточных кодов с фиксированной скоростью R < C/bg^n, где С - пропускная способность дискретного кЕщала связи, что при неограниченном увеличении длин этия блоков // вероятность ошибки после оптимального декодирования в заданном канале будет стремиться к нулю. Однако в данной главе мы имеем дело с неасимлто-тически.ч случаем, т.е. с кодами фиксированной длины п, и поэтому возникает ряд новых проблем, которые имеют важное практическое значение:
1. Выразить вероятность ошибки при использовании наилучшего кода и оптимального декодирования как функцию длины кодового блока п. скорости кода R и распределения вероятностей ошибок, определяемых каналом сня:ж^
2. Найти оптимальный алгоритм декодировали.я с исправлением или обнаружением ошибок для заданного кода и канала.
3. Найти метод выбора наилучшего кода при оптимальном декодировании в заданном канале.
4. Разработать практически реализуемые алгоритмы кодирования и декодирования.
До сих пор речь шла только о блоковых кодах, для которых передаваемая jjo каналу связи последовательность символов может быть разделена на одинаковые отрезки (блоки), формируемые кодирующим устройством независимо друг от друга. тежой способ является не единственно возможным- Поатому во второй части этой главы будут описаны так называемые непрерывные (сверточныс) коды. В конце первой части, посвящённой исключительно блоковым кодам, будет пояснено, почему и когда именно непрерывные коды могут иметь определённые преимущества перед блоковыми-
7.3.1. ВЕРОЯТНОСТЬ ОШИБКИ ОПТИМАЛЬНОГО ДЕКОДИРОВАНИЯ ДЛЯ КОДОВ С ФИКСИРОВАННОЙ ДЛИНОЙ БЛОКОВ (ЭКСПОНЕНТЫ ВЕРОЯТНОСТЕЙ ОШИБОК)
Пусть имеется некоторый канал связи, который описывается условными переходными вероятностями ?(у\\), хеХ", yeV, где Х и Y - его входной и выходной Ешфавиты, а X" и Y" означают всевозможные по следователь мости
длины и из алфавитов Х и Y соответственно. Обозначим через p^(^S] вероятность ошибочного декодирования в таком канале при использовании некоторого кода V, состоящего из М комбинации, и алгоритма декодирования по максимуму правдоподобия, если передаётся сообщение S, 1 < S < М. Достаточно общая верхняя граница для po^(V,S) при наилучшем выборе кода V была получена Р. Галлагсром [8|. Сформулируем ее в виде теоремы.
263

Доказательство теоремы. Верхняя граница {/-и/ выводится с помощью рассмотрения i;ik называемого «псамбла кодов, а не одного 'Хорошего" код,!. Алсамйль блоковых кодов задастся следующим образом. Определим скачала произвольное распределение вероятностен Q{\) h;i всех блокад длины и, составленные из входных символов канала связи, и будем считать, что псе кодовые слова выбираются независимо друг от друга с этими вероятностями. Таким о&ра-дом, иероятность лыбора некоторого частного кода х^А;,-,Яд в этом ансамбле равна
я T\Q{^.)- Каждый код из ансамбл» »мект свою иероятность ошибочного декодирования при
i=]
дскодиронании по максимуму правдоподобия. Если рассчитать среднюю по нссму ансамблю кодов вероятносгь ошибочного декодирования, ти она даст исрхнюю границу /'„д для ииилуч-шсго копа (те. кода с минимальной величиной р^}.
Среднюю по ансамблю кодов величину р^) при передаче S-ro сообщения мо^кно тогда
опислслить следующим обоазом:

где Р)од|5',1я. у] - иероятность ошибочного декодирования при условии, что, во-перных,
передастся сообшение S, во-вторыд, что для передачи этого сообщения была случайно выбрана комбинация кода х^, в-третьих, что была принята поел едонательн ость у Суммироцание в
{7J2} производится по всем входным и выходным последовательностям длины и.
При заданных S, д.^ у определим событие А^ для каждого S' Ф S как событие, состоящее
в том, что избирается такое кодовое слово ^з- ^ соответстиуюшсс сообщению .5" . д-ия которого

264

Если ь (7.13) имеет место строгое нерЕНюнстио, то декодер макс нм;1ль него прито подобия примет решение о псреддчс сообщения S' ? Л', т.е. сделает ошибку. (При наличии рлвснстна в
(7.13) ошибка произойдет не обязательно.) Поэтому, испольууп лемму, получаем

Используем неравенство (7.8) для оценки р (S) в дискретных каналах без
памяти, описываемых переходными вероятностями р[у rJ, где у^ еУ, -^ (=Х -Определим в этом случае вероятность случайного выбора кодового слова х как

где / и т — объёмы алфавитов входа и выхода канала соответственно.
Границу (7.19) можно представить в экспоненциальной форме, заменив р^{5) на среднюю по сообщениям вероятность ошибки ^.при произвольном наборе вероятностей этих сообщений;
265

Чтобы нЕ1Йти наилучшую верхнюю границу, необходимо максимизировать

Решение ,)той задачи для произвольных дискретных каналов представляе-определенныс трудности. Однако для 2СК без памяти с вероятностью ошибка символа п получается решение в замкнутом виде

Неравенство (7^21) позволяет сделать важный вывод, что при R < С (£{R) > 0) вероятность ошибки при выборе наилучшего кода не только убывает к нулю при п -> со. но убывает и как экспонента от п. Именно поэтому границы подобного типа называются экспонентами вероятностей ошибок. Это фактически доказывает прямую часть теоремы копирования Шеннона,
Д,1гл диклэ.ггельстн;! обратной части теоремы коаирои.иэия, очевидно, необходимо пслоль-^oiriTb нижнюю Гранину р,^ д;]м наилучшего коди. Этот вопрос нс будем чдесь о6|-ужд^ть, поскольку нижняя граница hi; имеет большого прикладного .[начсншг
Экспонемты вероятностей (7.20), (7,21) позволяют рассчитать энергетический выигрыш от применения кодирования (ЭВК) как функцию заданной верности /^. скорости кода R и длины кодового блока /l Однако в отличие от
асимптотического случая здесь возникает одна дополнительная сложность-Пусть, например, два кода с одинаковыми скоростями R, длинами // ^ 10 и // = ККЮО имеют одинаковые вероятности р^. Можно ли считать, что в обоих
случаях обеспечивается действительно одинаковая верность передачи сообщений? Интуиция подсказывает нам, что во втором случае надежность передачи будет, наверное, больше, чем в первом. Постараемся облечь теперь наши интуитивные ощущения в более строгую форму. Пусть передается информация такого типа, что количество ошибок на сеансе связи, состоящем из N информационных бит, не играет существенной роли для оценивания качества передачи, Критерием верности тогда служит вероятность 0(/V) абсолютно правильного приёма всех элементов. Очевидно, что при использовании двоичного кода
266

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

icneph ясно, что если два кода имеют одинаковые скорости, но разные длины, то код с большей длиной блока будет иметь большее число кодовых комбинаций М и поэтому для него Q(/V) оказывается больше при равных значениях N и р^. (Для канала с памятью можно при р^ «1 использовать аддитивную границу

для которой сделанный выше вывод также оказывается справедливым.)
Дли того чтобы сравнивать коды различной мощности, воспользуемся понятием з^ивсшептной вероятности ошибки д, Напомним читателю (см.
и 1-11), что р^ - это такая вероятность ошибки символа в 2СК без памяти, с постоянными параметрами и при отсутствии кодирования, которая обеспечивает ту же вероятность правильного приёма g(/V) информационных символов, что и данный код в данном канале. Очевидно, что можно написать

Величину р^ (соответственно р-^) для наилучшего кода можно найти из (7.21),
Расчёт энергетического выигрыша одной дискретной системы передачи над другой (ЭВС) можно в общем случае вычислить при д= const. по формуле
(5,108), ЭВК для заданного кода можно находить при заданной вероятности Рл=- Рэ и по формуле (6.61),
Предположение о том, что получатель сообщений не является критичным к количеству ошибок, типично для передачи данных, но вряд ли оправдано для таких сообщений, как оцифрованная речь, печатный текст или факсимильные сообщения. Для этих источников более естественно оценивать качество передачи сообщений средним числом ошибочных бит или средним числом ошибочных передач некоторых элементов сообщений,
Экспоненты вероятностей ошибок являются значительным продвижением в теории кодирования по сравнению с теоремами кодирования, поскольку они определяют верхнюю границу для наилучшего кода как функцию длины кодового блока. Однако это верно лишь для наилучшего копа, тогда как способ его построения является пока неизвестным. Можно, правда, попытаться действительно случайно выбрать некоторый код и зафиксировать его для работы по данному каналу связи, (При неудачном выборе можно повторить эксперимент,
267

проверяя эффективность кода при помощи расчета реализуемой им частости ошибочного декодирования.) Однако, как будет показано в дальнейшем, сложность алгоритма декодирована для случайно выбранного кола также экспоненциально возрастает с ростом длины кодового блока и поэтому целесообразно указать некоторый регулярный выбор если не наилучшего кода, то по крайней мере кода, гарантирующего определённую величину /?од в заданном канале связи. Такие классы кодов рассматриваются в следующем разделе.
7.3.2. КОДЫ С ГАРАНТИРОВАННЫМ ОБНАРУЖЕНИЕМ И ИСПРАВЛЕНИЕМ ОШИБОК
Пусть задан некоторый блоковый код длины и, состоящий из М комбинаций (блоков, слов, векторов) х\, х^, „,, х,у- Для упрощения определений и доказательств будем всюду считать, что входной Х^ выходной У алфавиты канала совпадают. В обшем случае канал может иметь память и задаваться вероятностями /'(х|у) переходов входных блоков х в выходные у,

Рцнсе ь гл. 2 Были сформулированы аксиомы, которым должно удовлетворят!, абстрактное определение понятия расстояния il (рункниональных пространствах сигналов. Покажем» что расстояние Хэммшгга удовлетворяет этим аксиомам ни пространств т-ичных послсдовп-
тельностеи прои-шольнои длины п. Псриыс требования: pfi, у}> 0,р(л, \} = О, р('(, у)= fi[y, s]
удовлетворяются оченпдным обрузом. Остаатсм проверить лишь справедлииост|| "нсраиснстни треугольника":

Определение 3. Весом Хэмминга [х блока (вектора) х (аналогично для у и е) будем называть число ненулевых символов этих блоков.
Определение 4, Кратностью образца ошибки е (или короче — кратностью ошибки) будем называть его вес Хэмминга е|, (По существу ^то число ошибок, которое произошло при передаче блока х.)
Декодирование в заданном канале связи по максимуму правдоподобии - ато принятие решения о передаче такого кодового блока х, '-.V , для которого условная вероятность /Чу!:^) максимальна, где у - принятый блок- Это правило получения оценки можно записать в следующей компактной форме:
268

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

(По существу, правило (7.32) означает, что считается переданной та кодовая комбинация, которая отличается т- принятой в наименьшем числе позиции.)
Покажем, что для wCK. без памяти правила (7,31) и (7,32) совпадают, т.е, декодирование по минимуму расстояния Хэмминга совпадает с декодированием по максимуму правдоподобия. Действительно, в соответствии с определением тСК. без памяти

где п - длина блоков у и х- Легко убедиться, что (7,33) является монотонно
убывающей функцией р(у,х,) при р^——, что и доказывает акви валентность
•               т
(7Л) и (7J2) для данного канала связи.
В случае использования произвольного канала с:ия:эи, например несимметричною или с памятью, декодировании по минимуму расстояния Хамминга не обязательно будет оптимальной процедурой, однако ввиду простоты (7.32) этот алгоритм часто используется и л данны.ч
случаях.
Если канал симметричен, но имеет память» то он может быть прсобраэонан в wCK 5e'i памяти, а следовательно, для него окажется оптимальным дэмминговскии алгоритм декоднро-Н.1ННЯ после следующего преобрази пан ия канала сая^и, который называют игремгж^иисм спм-вомй или декорреняциеи. Как покачано на рис. 7.2, кодовые блоки, содержащие и символов номера которых отмечены верхними индексами Г, 2, -, L, после их формиронания предилрн-тельно заносятся в буферную память. После окончания формиронания последнего L-го блока начинается передача символов эт\!К блоков в канял снязи "по столбцам" матрицы, и входящий-cя    и    буферной    памяти,    т.с     последовательно    передаютсн    символы \^\s. I121, -.., 1'^, 2Ч1. „.. У-\ ,,,, п^, ,., п^. На приеме ^ти символы запоминаются в виде последовательных строк матрицы. После заполнения всех таких строк начинается дскодироьа-Епте по столбцам последовательных кодовых блоков с номерами (J), (2). ..., {L), Видно, что каждая пара смежных симцолов в снобом из коловых блоков Пйредается ь канале связи с разнесением но времени LTf,. где 7^ — длительность канального симиола. Если параметр L выбран достаточно большим, а зависимость между ошибками (память канала) убывает при разнесении передаваемых симколов, то после такой процедуры можно практически полностью устранить память \\ канале связи.

269

Определение 6. Минимальным {содовым расстоянием d для заданного кода V будем называть минимальное расстояние по Хэммингу между всеми парами его несовпадающих кодовых комбинаций, т.е-

Избыточный код У может использоваться в канале связи с помехами не только для декодирования (распознавания) действительно передававшихся со-обшсний, т.е. фактически для исправления ошибок, но и длл обнаружения ошибок. Естественным алгоритмом декодирования с обнаружением ошибок является принятие решения об отсутствии ошибок, когда принятая комбинация у совпадает с одной из разрешённых кодовых комбинациях, т.е. у-^-еГ, и обнаружение ошибок, если ут-х, для всех \,<е У . Очевидно, что в этом случае возможны ошибки декодирования, а именно принятие решения об отсутствии ошибки, в то время как они в действительности имеют место. Будем называть это событие необнаруженной ошибкой^ а его вероятность — вероятностью необнаруженной ошибки, обозначая её через /?но или PnoW для сданного кода У, При рассмотренном выше алгоритме обнаружения ошибок необнаруженная ошибка может появиться тогда, и только тогда, когда передаваемая по каналу связи кодовая комбинация под воздействием помех перейдёт на выходе в какую-либо другую кодовую (разрешённую) комбинацию. Поэтому при равновероятном выборе кодовых комбинаций

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

270

(Неравенство в (7.37) возникает потому, что код с минимальным расстоянием if может, вообще говоря, обнаруживать ошибки и кратности большей, чем
d— 1.) Подставляя (7.36) в (7,37), получаем, что для ///СК (в частном случае 2 С К) без памяти

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

Теорема 7.4 позволяет построить верхнюю границу вероятности ошибочного декодирования при использовании алгоритма Хэмминга в произнольном канале свюи:

Определение 9. Будем называть алгоритмом совместного исправления ошибок кратности до ^ и обнаружения ошибок при использовании кода Ус минимальным расстоянием ^2;,+1 алгоритм, который по принятому слову у декодирует кодовое слово х/, если р(у,х,)</„, и обнаруживает наличие ошибки, если
pty^,)^, Для всех кодовых слов х/, /= I, 2, .-,, М-
Свойства кода с заданными параметрами d и /„ по совместному исправлению и обнаружению ошибок определяются следующей теоремой,
271

Теорема 7.5. Если код имеет минимальное расстояние д/^ 2/^+1, то использование алгоритма совместного исправления ошибок кратности до /ц включительно if обнаружения ошибок, обеспечивает гарантированное исправление ошибок кратности fie больше /[, и обнаруживает число ошибок кратности не более d — 1 — 1^.
Доказательство утверждения о гарантированном исправлении ошибок очевидно, а доказательство утверждения о гарантированном обнаружении ошибок производится аналогично доказательству теорем 7.3 и 7.4.
Теорема 7.5 позволяет получить верхнюю границу для вероятности необнаруженной ошибки р,,^,^,}, и нижнюю границу для вероятности правильного
декодирования рпд^л) п?^ использовании кодов с данным алгоритмом совместного исправления и обнаружения ошибок

(Подставляя (7.36) в эти неравенства, получаем соответствующие границы для частного случая канала тСК без памяти.)
В некоторых случаях на выходе канала могут появляться дополнительные пометки о ненадёжности принятых символов, что приводит к их стиранию. Это может происходить из-за низкого отношения сигнал-шум, соответствующего данному тактовому интервалу.
В качестве признак,! отсутствия стирания симиола н,1 /-м тактовом Интернете при опти-м;дл1.ном когерентном приёме противоположных сигнсшои {л'(^),—^/)| на фоне белого шум;1 можно испол1|3оват1, превышение некоторого порога абсолютным значением корреляцион-
JT
ного интсгриля (г(/),у(()(/< i где ^S) — принимаемый непрерывный сигнал. :i Т— длительность
('--Df элемента сигнала (так-гоныи интарв,1Л. ем. гл. 5},
Определение 10. Будем называть алгоритмом исправления стираний и ошибок такой метод декодирования, который измеряет расстояние Х:-»мминга между принятым блоком у и всеми кодовыми словами в нестёртых позициях и декодирует то кодовое слово, для которого это расстояние минимально.
Исправляющая способность алгоритма совместного исправления стираний и ошибок определяется теоремой.
Теорема 7.6. Если код имеет минимальное расстояние d, то он может одновременно исправить tc стираний и /и ошибок при выполнении следующего условия:

Доказательство производится совершенно аналогично доказательству теоремы 7-4 с учетом того очевидного факта, что код ^ с длиной блоков д — д,
образованный из комбинаций исходного кода V при вычеркивании ^ стёртых позиций, имеет минимальное расстояние не менее, чем d — s.
Зная совместные функции кратности ошибок и стираний в канале связи,
можно рассчитать верхнюю границу для /^(^цЛ)' используя ("Л 44).
272

Заметим, что алгоритм исгф.шлсния ошибок и стираний является промежуточны м вариантом между так натыкаемым жёстким av кодирован нем {в дискретном канале) и мягким декодированием (в полу непрерывном каигше). Более подробно эта проблема обсуждается и
ii.7.3.i().
Полученные границы дня р^( V} и /^д( ^ показывают, что желательно иметь код с наибольшим возможным значением минимального расстояния d. Однако интуиция подсказывает нам, что мы можем добиться увеличения d при фиксированной длине блока и, только уменьшая скорость кода R. Хотелось бы иметь точные формулы, определяющие d как функцию R и п или хотя бы верхние и нижние границы для этого параметра. Кроме того, для обеспечения р„ -^0,
чти было обещано теоремой кодирования Шеннона, придется увеличивать и длины кодовых блоков и, но при этом количество комбинаций кода М экспоненциально возрастает. Это неизбежно вызовет большие трудности при реализации процедур кодирования и декодирована (Действительно, при кодировании нужно запомнить Л/комбинаций и извлекать из памяти каждый раз новую комбинацию, соответствующую поступившему сообщению, а при декодировании вычислить М хэмминговских расстояний и находить среди ник минимальное,) Поэтому мы нуждаемся в более конструктивном (регулярном) задании кода, чем его описание таблицей кодовых комбинаций. Эту проблему удастся решить при переходе к специальному классу так называемых линейных кодов, который описан в следующем разделе.
Однако, прежде чем псрент-п к его рассмотрению, сделаем еще одно ^мсч.щис. CpuiiHC-нле границ (7.37) и (7.40) показывает. что ь любых кангша?; связи и для любых кодо!1, /'ini(^ ^ PwW- причём что неравенство справедливо не только для границ, но и для точных •точений соопил-спэуюшик кероятЕЮстен ошибок. одеэвко этот фак-г еще не означает.. что лссгда цслсео об разно иепользов.ш. обнаружение ошибок, -л не их исправлсши;. Децстцитсль-его, после обнаружения ошноок е блоке он оказывается стср^'ы,м, -л ел сдо ^гельно, не может EihiTb ьид^н получателю. Обычно его доставка о^уше^твлястся при помощи повторно» леред;!-'iii. что требует затрат до иолнитсле. но го времени.
К вопросим получения более точных оценок для р^{У} и p^W. е| токже к сравийнмю
систем е обнаружен и ем и испр.шлснисм ошибок mi.i еще исрнемся в следующем р;1здсле,
7.3.3. ЛИНЕЙНЫЕ ДВОИЧНЫЕ КОДЫ ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБОК
Здесь мы ограничимся описанием только двоичных кодов, поскольку это не потребует пока использования в качестве математического аппарата такого достаточно сложного раздела соврсм&нмой алгебры, как теория конечных полей. Мы отметим, однако, в конце главы, как все определённые здесь понятия и свойства могут быть распространены на случай w-ичных кодов,
Определение 11. Линейным блочным двоичным кодом длины п называется любое множество двоичных последовательностей длины п, которое содержит чисто нулевую последовательность, и для каждой пары последовательностей, принадлежащих этому множеству, их поразрядная сумма no mod 2 также является элементом этого множества. (Последнее свойство можно назвать замкнутостью относительно поразрядного сложения по mod2,)
Пример- Множество последовитсльностси длины 5: 00000, 11Г01, ОЮШ, ИПП, образует лннийныи код, что проверяется непосредственно. Поразрядная сумма по i[iod2 2-й к 3-си комбинации дует 4-ю комбинацию, сумма 3 и 4 даст 2-ю. u сумм? 2 и 4 дает 3-ю комбинацию.
273

C'lCPiLiHo, что лннсмныП код удои;1с:Г1Юрист определению линейного nd-inpocTpLiHCTR.t V для
прогтрансты! V" \\сех лпсипных последсп^тел^ностеи дгшны п. (Или ин;1чс — это подгрупп;! для группы iiccx д|Ю[1'|ны'< ч- по ^лсдои;1тсль ногтей огноситсльею групповой опсрпинк поря^-
рядного сло^кенч" по mod 2. Поэтому двоичные линейные коды ii,i3biii:no7<;!i также и группе^
<!Ш'Ч.)
Из алгебры известно, что всякое ^-мерное линейное подпространство /;-мерного пространства, состочщего из конечного числа (2") элементов, содер-
ж.нт базис, т.е, совокупность k линейно независимых элементен, n:i которых путем поразрядного суммирования по mod 2 можно образовать любые элементы данного подпространства, т.е. в данном случае комбинации линейного кода, Докрывается, что все базисы такого подпространства состоят из одного м того же числа элементов k, которое и определяет размерность подпространства. Общее число комбинаций линейного кода М = 2й. поскольку таким будет общее число возможных поразрядных сумм из k элементов базиса, причём среди них не может найтись днух одинаковых сумм ввиду линейной независимости элементов базиса,
Совокупность элементов базиса- записанная в виде линейно независимых строк, образует k х п двоичную матрицу G, которая называется порождающей матрицей кода:

Множество всех кодовых слов, порождённых G, может быть представлено как

где х — вектор-строка кодовой комбинации размерности п\ Ь — вектор-строка информационных символов длины k. В (7.46) выполняетсп умножение вектора на матрицу, а все действия осуществлены no mod 3, Очевидно, что в качестве вектора Ь можно использовать k последовательных элементов сообщения, выдаваемых двоичным источником. Переход от избыточных кодов общего вида к линейным кодам практически решает проблему сложности кодирования. Действительно. вместо запоминания М = 2й комбинаций; длины п, т-е, пТ^ бит в общем случае, нам достаточно запомнить лишь порождающую матрицу, состоящую из nk =/;Jug^ М бит. Сама же процедура кодирования потребует выполнения не более чем Ikn элементарных операций.
Переход к линейным кодам значительно упрощает анализ (а следовательно, и задание) их обнаруживающей и исправляющей способности. Действительно,
пусть У- линейный двоичный код, содержащий комбинации^, х,, ..., \, _), где ^ — нулевая комбинация. Тогда по свойству замкнутости линейного кода для любой пары ненулевых комбинаций (х,, х^) расстояние Хэмминга между
ними р(х;.х^)= х^Фх,? будет равно весу Хзмминга х^ некоторой третьей комбинации, принадлежащей этому же коду, кроме нулевой. Поэтому получаем важный вывод, что для любого линейного кода минимальное кодовое
274

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

Таким образом, для всех линейных кодов изучение списка хэмминговских расстояний между ларами комбинаций эквивалентно изучению списка хэм-минговских весов, что, очевидно, значительно проще,
Для любого линейного кода, заданного некоторой порождающем матрицей G, очевидно также следующее свойство: любые перестановки столбцов и элементарные преобразования строк, заключающиеся в их перестановках или в суммировании друг с другом, не изменяют список весов данного кода, С другой стороны, мо?кно показать, что при помощи таких преобразований любая [k >. п) двоичная матрица G с линейно-независимыми строками может быть приведена к каноническому виду

№ {pij} ~ некоторые двоичные элементы; 1^ — единичная k < k матрица (с единицами на главной диагонали и нулями в других местах); Р - матриц;] k у (п - k}, состоящая; ii:i двоичных алементов; (А[В) означает последовательную запись матриц А и В.

Из выражений (7,49) и (7.50) следует, что процедура кодирования линеп-ным кодом, определённым канонической матрицей вида (7,4Й), сводится к формированию кодового слова, состоящего из двух последовательных подслов. причём первое подслово совпадает с информационной последовательностью длины А, выданной источником сообщений, а второе образовано путем линейной комбинации строк матрицы ¥.
Определение 12, Линейные коды, слова которых представить! в виде (7.49), н аз ыв аются сиап ем am и ческ им и.
Мы фактически показали ранее, что всякий линейный код эквиаи-че/аиеп некоторому систематическому в смысле сохранения списка весов, а следовательно, и расстояний Хэмминга. Первые k символов кодовых слов, совпадающих с символами источника, называются информационными, а последние п — k символов — проверочными. Скорость кода R, определённая ранее как \og^M/n, для линейного кода будет равна k/n, т.е, для систематического — отнощ^гию числа информационны?; символов k к длине кодового блока п. Систематические коды с длиной блока п и с числом информационных символов k будем кратко называть (//, /:)-кодами. Иногда такой код обозначают тремя параметрами (ft, k, fl}, где d — минимальное кодовое расстояние.
•275

В линейной алгебре существует понятие ортогонального пространства или нуль-пространства для заданного линейного пространства У. Это по определению такое множество V векторов х" дгжны п, для которых (х', х) = 0 при любом хеК, где (, ) означает скалярное произведение соответствующих векторов. (В нашем случае все операции производятся по mod2). Доказывается, что это множество всегда является линейным пространством^ причём если код У имеет размерность k, то код Сбудет иметь размерность п - fc, т.е, содержать 2"~^ комбинаций. Код V, совпадающий с ортогональным пространством, называется дуальпш к коду V. Он, очевидно, также может быть задан своей порождающей матрицей G'=H размерностью {и - k} х п. Тогда комбинации исходного кода Смогут быть определены как решения векторно-матричного уравнения

где Т означает символ транспонирования матрицы Н, т.е. взаимную замену строк и столбцов- Матрица Н, которая является порождающей для кода У", называется проверочной матрицей для исходного кода У. Матрица Н так же. как и G, может быть представлена в канонической форме, причём можно показать 1211, что

где Г — та же самая матрица, что и в представлении (/лв;.
В теории линейных кодов найдены границы для минимального расстояния d.

Доказит&гьаиао, Пусть Н - происрочния матрица кода У. Тогда ш (7,51) следую, что для любого слоне! х £[•' хэмминговского nGc.i д = с& существует tlikoh набор из id столбцов матрицы Н. элементы которой при покоординатном сложении по mod 2 дадут нулевой столбец:. Верно и обратное, а именно, что если для некоторой проверочной матрицы Н любые d - 1 и меньшее число столбцов всегда является линейно независимым (т.е. в сумме не дают нулевых столбцов), то соотистст^ующий ей линейны» код имеет минимальное расстояние, самое •ьюньшес d. Построим проверочную матрицу, обладающую таким свойством. В качестве её перьою столбца возьмем любой диоичныи HEifiop длины i-= п - k. Затем почьмем т.жжс любой диоичныи набор длины /', не сои падающий с первым. л.шсе — третий набор, не ривный И!< сумме и так дадите до столбца длиной г, который не является суммой t/ - 2 и меньшего чи^л.) прсдыдуших столбцов Очевидно, что очередной столбси может быть присоединен к мчтрищ;
ь том случае, если совокупность всех сумм ид d -1 или меньшего числа предыдущих столб-цои матрицы не исчерпьжает пье^ наборов длины г, В наихудшем cn^iae псе т-.нсис суммы бу-д^т различными. Поскольку общее число таких сумм при иыборе из общего чис-'ni j — 1 столб-
tt-2
цоц ранно y^C^i , а число различных тц-s центов двоичных ненулевых столбцов длины г р.^вио
2' - ], то достаточное условие сущестиоцания код^ е длиной блока _/, имеющего ceimog большее г проверочных симиолои, принимает вид
276

hu pill:. 7,3 ПОСТроеНЫ КрПНЫГ, ^ООТИСТСТВуЮЩН!; 1";Р''НеИ Гр^НННС ГЬюТКИНа 11 ИЧЖНСИ
границе Варшамова-Г[1Л1/бер-т, кик функции скорости код;! R=k.//i от .ьргумснта d/ln, В отличие от границы Плоткина 1раница В ар и 1.1 у она-Гильберта означает, что всегда сущсетиукуг коды. которые имеют скорость, ледащую на соотиетствующеи кривоп, ;i возможно, и иышс этом кржюи.
Заметим, что леркнми г]1Е»1ИЦа строилусь по ^оотношсиию, определяемому геор&мой 7.7 при достаточно большие (/, когда вторым и третьим слдтемым в выражении дли оценка числа проверочных символов можно было пренебречь. Нижняя граници была nonyicH.i из соотно-шснш! (7.55), где также в качестве аргумента функции не польз овьюсь d/n, что верно для больших я. Параметры наилучших рсгишзусмык кодов могут лежать только и аа штрихе и-ж но и области медузу верхней и нижней границами. (В псистиитсльиости получен и целый ряд дру-пгх границ, которые уточняют значение ci, т.е. сужают данную область при некоторых значениях аргументе п.)
Заметим, что хот» теорема 7J и описывает, казались оы» конструктивный метод построс-Htiii кода с заданной величиной el, однако его практическое использование окаэьшается невозможным, поскольку при больших значениях ч ч г требуется перебор огромною количестиа возможных нариантов столбцон проверочной матрицы Н.
Нижняя граница R а ршамо па-Гильберт;! позиоляет оценить асимптотические возможности линейных дпончиых кодои по не правлению ошибок гарантиронанной кратности. Дсистии-те^ыю. срЁДНес число ошибок в блоке длин1,| и для ЗСК без памяти судет равно up, где р -вероятность ошибки символа и данном канале. Дл^1 того чтобы после ei с пользе на ни я кода 1пп"„=0, очевидно, необходимо, чтобы код имел d не меньше, чем Ifip, и тогда при
J Чл\,                                             •                        •               •г ip-ЮТ
277

больших d получаем ti/ii^l/.-. л неравенство (7.55) можно переписать в следующей форме. R-^t-li(2p}.
Интересно сопоставить нижнюю границу Вар шамова-Гильберта R^=\~^^2p) с верхней
1'раиицсн  для   скорости   кода,   установленной   теоремой   Шеннона  для   2СК' Q/^ =i — //(/')J Ясно, что при /? = 0 зти границы совпадают. При р >. 0,25 нижняя граница Ва р ш а мова-Гильберта Дц, = 0, в то время как верхняя граница Шеннона C(p}>G (см,
рис. 63). R области р > 1U'"2 граница Шеннона существенно пыше, чем граница Варшамова-Гнльберта. Эта разница объясняется тем, что нижняя Гранина Варщ а мона-Гильберта соответствует алгоритму исправления ошибок только гарантир овинной кратности, и то время как границ,) Шеннона определена при оптимальном, сколь угодно сложном декодировании. Однако, хотя скорость кода Д. получаемая из Гранины Вар шамо во-Гильберта.. меньше, чем значение.. следующее ил теоремы оптимального кодирования, она является гарантированной и реально достижимой.
Исследование лииениык кодов позволяет также упростит!, алгоритм декодирования но минимуму расстояния Хэмминга, расчет /?n.ii лля этого алгоритма н ближе подойти к проблеме оптимизации выбора кодов.- Для чтого рассмотрим конструкцию, которая называется cfw-дартным р^спиложспис.ч по заданному коду V В качестве нерпой строки такою расположения (таблицы) выберем кодовые комбинации я, самого кода V, Далее нозьмём произвольное дио-
ичнос слово gj длины и, которое не принадлежит коду У, и образуем М = 1^ слов следующей строки по правилу у|^»,©й|^ ^=1, 2. ..., 2*, где Ф означает поразрядное суммироцание по mod 2. Затем ночьмем лиончное слово g? длины и так, чтобы ^^х,, уз^у,,. 1=1. 2, .... 21', и построим третью строку у;| = х;©&;, и так далее вплоть до исчерпания всех двоичных векто-
рон длины ^i не входящих в предыдушие строки- Легко npoiiepHTi,, '[to и к.икдоп строке матрицы будут содержался лишь различные слова и в строк,^ не будет содержать повторении слов. Данная таблица будет содержать все 3" дноичных слои длины и. Поэтому число строк
т'
таблицы псегда il точности — = 2"~*. а число столбцов 2^. Можно убедиться также в справсд-2-
ливости следующих свойств для данной р.юстановки: поразрядная сумма но inod 2 любой пары слои, находящихся is одной строке, всегда даст кодовое слово, -л лежащих в разных строкам — слово ц некоторой строке, отличной or взятых, но ле принадлежащих первой строке (т.с, коду). Замсн.1 слова g/, ^юрмируюЩЁГо ;-ю строку, на какое-либо слово в чтой же строке не наменяет потюн совокутнюсти слов, образующих данную строку, а прончнодит лишь их псре-станоику il строке. В алгебре такие строки, полученные по некоторой группе (коду), низыьа-ююя с-мсжчымч классами, а слова g, ..g л-i ггаэываются образующими или зидсралт cmc^-hi.ix
классов. После построения стандартного рае положения по некоторому коду ^определим способ декодирования, соответстпующий этой таблице, следующим образом, если принято некоторое слово у, то декодируется кодовое слово \„ находящееся н том исе столБцс, что и у. Тогда вероятность переход,! /^ylx,) для любого двоичного канала саязи с аддитивным шумом
^удст равна вероятности появления образца ошибки е, совпадающего с лидером смежного класС|| g, к которому принадлежит у. Поэтому для того, чтобы сделать декодирование оптимальным по критерию максимума правдоподобия, достаточно выбрать в качестве лидеров об-рачцы ошибок, имеющие максимальные вероятности и к^ъждон смежном классе. (Если несколько слов имеют в некотором смежном классе одинаковые вероятности, то можно и качестве лидера выбрать любое из них.)
Определение 13- Синдромом по коду У для любого принятого на выходе канала связи двоичного слова у длины п будем называть двоичный вектор-строку длчны п - k'.
s=yH7,                                                   (7.56)
где Н — пронерочмая матрица кода К
Легко убедиться, что для всех слов. принадлежащих одному и тому же смежному классу кода У, синдромы оказываются одинаковыми, а для
278

различных смежных классов синдромы различны. Поэтому с каждым смежным классом можно сопоставить один. и только один синдром. Оптимальное декодирование в 2СК без памяти можно тогда производить, отыскивая слово минимального веса, синдром которого совладает с синдромом, полученным по принятому слову. Такой алгоритм декодирования называется сиядромьы.м. Табличный способ снндромного декодирования состоит в запоминании таблицы, связывающей различные синдромы с лидерами соответствующих им смежных классов.
Схемы кодирования и вычисления синдрома для произвольного линейного кода приведены на рис. 7.4 и рис. 7,5. Элемент порождающей матрицы /^ определяет характер связи /-и ячейки регистра с j-м сумматором: если р^= I — связь есть, если р^ 0 — свя^ь отсутствует. Кодирование происходит следующим образом, вектор b записывается в регистр, после чего с выходов сумматоров считывается вектор с. Для кодирования систематического кода необходимо лишь n-k сумматоров, связи которых с регистром задаются матрицей Р. При этом вектор х образуется из вектора b и выходов n-k сумматоров (вектора с). На рис. 7.5 элемент проверочной матрицы h,. определяет характер связи /-и
ячейки регистра cj-м сумматором: если h, ^=\ — связь есть, если /т,, =0 — связь
отсутствует. Для вычисления синдрома вектор у записывается в регистр, после чего с выходов сумматоров считывается s.
При использовании линейных кодов выраженная числом двоичных сложений сложность процедуры кодирования и процедуры вычисления синдрома (декодирование с обнаружением ошибок) не превышает )?. Это значительно меньше, чем при табличном кодировании и декодировании.
Для конкретизации алгоритма де кодирования с исправлением ошибок учтем, что принятый вектор у можно записать в виде у-:хфе, где е — вектор
ошибок в канале (размерностью я). Если конкретная реализация е имеет вес ш (а ненулевых компонент) и с& меньше ^ для заданного кода, то ошибки в у могут быть исправлены- Вектор е входит в выражение для синдрома (7.56), и с учётом (7.54)

Вероятность рсщ правильного декодирования кодового слова в любом канале сщии npit неполно Ran ни табличного способа снндромного де кодирования (по алгоритму максимального правдоподобия) будет определяться следующим соотношением.
279

где go - означает нулеиое слобо, и, следовательно, Де =. go) ^ответствует вероятности безошибочного приема кодового слова. (Очевидно, что р^= 1 - рщц- Для 2CK без памяти с'тан-д.фгуос расположение дает правило декодирования по максимуму пра-идо подобия, если к,1Ж-дый лидер выбирается как слово минимального веса в своём смежном классе. Тогда для вероятности правильного декодирования получаем следующую точную формулу

где с&г — минимальный нес слова в /-м смежном класьс.
К сожалению, использование (7,59} для мощных кодов оказ^настся затруднительным, поскольку требует построения необходимой таблицы стандартного расположения или энани^ Т.1К называемого спгк-тра смежных классов, т.ц. распределения весои Хэммингс! для слов, входящих в каждый из смсжнык классов коду, что удастся сделать лишь для некоторых частных
случагь.
Соотношение (7.59) показывает, что некоторый {и, ^)-код будет оптимальным is 2CK без
памяти, т.е. обеспечит максим.шьную величину р^, если ксе его лидеры минимального веса совпадут с набором образцов ошибок от 0 до некоторой кратности /, Поскольку полное числе
г таких образцов ошибок равно ус^,, а число смежных классов равно 2"Л то это требует вы-
г=о пол не ни я условия

где / - некоторое целое число. Очевидно, соотношение (7.60) выполняется не для всех (п, й)-кодов. Напротив, его выполнение - это редчайший случай. Коды, которые удовлетворяют этому условию, назыиаются совершенными. Известно лишь два нетривиальных диоичных ("> А)-кода с параметрами, удовлетворяюшими (7.60), - это код Хамминг,! и код Голея (23,13). (Они Будут определены несколько позже.) Максимум н (7.59) может обеспечить и так называемый квазисовсрш^пныи код, среди образующих смежных классов которого при некотором / содержатся нее последовательности веса / или меньше, часть последовательностей веса l + 1 и нет ни одной последовательности большого веса. К сожалению, квазисове ршенныс коды также встречаются достаточно редко-
Даже если некоторый линейный код имеет известное значение (/, расчёт р^{У) или р^(У) в 2CK без памяти по границам (7J8), (7.41) или (7.43) может привести к достаточно грубым оценкам. Это особенно относится к расчету обнаруживающей способности кода для больших вероятностей ошибок р- Поскольку для линейных кодов необнаруженная ошибка происходит тогда, и только тогда, когда образец ошибки совпадает с одним из ненулевых кодовых слов, то можно привести точную формулу для расчёта р^о(У) в 2CK без памяти.

где i\j— число слов кода веса ;, т.е. так называемый весовой спектр кооа.
Если, в частности, положить в (7.61) р = 1/2, то для любого (я, k) кода по-
21 -1                                           1 " -лучаем р '-—„—, что, как правило, значительно меньше, чем ~^С'„, полу-
""2                                                                                    '- ,=j
чаемую по (7.38) для этого же значения вероятности ошибки символа в канале связи. (Заметим, что ситуация, соответствующая случаю "обрыва канала", является отнюдь не бессмысленной для обнаружения ошибок, поскольку канал
280

может лишь временно перейти в состояние обрыва и мы должны обеспечить практическое отсутствие ошибок у получателя и в таком состоянии.)
Можно доказать, что при любой вероятности ошибки р, 0 < р ^ i/2. в 2СК (это иерно и для любых двоичныя каналов с памятью) существует такой (л, й)-код У, что

Однако Eie обязательно для всех (//, А} сборов существует один и тот же (fl, А)-код, который обеспсчшшЁТ выполнение (7.62) для всех 0<р^.}/2. Если такой код существует, то он
ндчывастся хорошим кодом. Неравенство (7.й2) может быть обеспечено в любом канале связи, если (л, А)-код используется совместно со стохастическими преобразованиями карала на передаче и приеме. Эти преобразования сохраняют вероятности безошибочного приёма //-блока и делают равновероятными псе другие образцы ошибок- Однако такой подход требует обеспс-тиння синхронизации между приемом и передачей для выполнения ^аимообратных преобра-эоланий, что делает им в действительности пссвдо слуга иным и,
Известные спектры имеют достаточно редкие K^accbJ линейных кодов, однако часто уда-стен р точности рассчитать эти спектры путём перебора всех З* комбинаций данного У кода нлл 2'г~'• комбинаций дуального к нему кода. Действительно, согласно лемме Мак Вильнма
WFw{^) может быть рассчитана по спектру дуального кода Л^ следующим обрачом:

Если нас интересует не безошибочная передача всего сообщения, а среднее число ошибочных информационных символов после декодирования, то в общем случае это требует весьма громоздких расчетов. При малой вероятности ошибки символа для средней битовой ошибки ph получено для симметричного канала без памяти приближённое выражение |13|
281

Дс11стиш\-лы10, если код с расстоянием d=1t + 1 исгюльзустси для исправления c.iiy'liili-пых ошибок, то 11|Ч|большую [юль будет чгруть ней с пру плен пая ошибка, еоответстиукпцая
КимбИИЦЦИН / -+- 1 ОШИбОЧНЫХ СИМ1Ю;10В. В •Л-ОМ СЛуЧИС ПРИ рСЕинтЦКИ Еии-ОрИ-ГМ:! декодирования liLiHOCHTC^i ошибочное решение о том. что принятое слопо содержит / ошибок и чти S снмиолсж меняются, т.1к чю послсдователшость будет содержат!. Is т \ = d ошибочных ciin-вотюн. Поскольку этк ошибки могут поянпться в люйуч местак последонитсльности длиной л, ьсрогэтность ошибочного бит-с! при услонии, что последонатсльЕЮСть содержит ошибки, p;iUEia r//n. ,\ вероитность средней битовой ошибки определяется {7,67}. Заметим, 'это р-, -.)К]иИ1;1Лснтн^ перонтиосгъ ошибки согласно (7.28) д,1ст рс^ультчг, блилкии к (767).
Полученные формулы (7.б1)-(7.бб) могут оказаться значительно более точными, чем (7.38), (7.41), (7.43) при расчёте р^ или р^. Однако остается открытым вопрос о построении кодов с достаточно бо.1ьшим значением минимального расстояния d, поскольку и в этих формулах данный параметр имеет весьма важное значение, а граница 6 ар шамова" Гильберта является неконструктивной. Для решения данной проблемы необходимо обратиться к некоторым подклассам линейных систематических кодов.
7.3.4. ВАЖНЫЕ ПОДКЛАССЫ ЛИНЕЙНЫХ ДВОИЧНЫХ КОДОВ
1. Коды с общей проверкой на чётность. Это класс копоь с параметрами (/?, AW^+], k), k = 1. 2, „., когда имеется лишь один проверочный символ, который образуется как сумма по mod 2 всех информационных символов. Очевидно, что минимальное расстояние d для данных кодов всегда равно 2 и поэтому они могут гарантированно обнаруживать лишь одну ошибку. Комбинации данного кода имеют лишь чётные веса,
2.   Коды   Хэмминга,   Данный   класс   кодов   имеет  параметры
{n,k}-\T -\Т—Л-з\з - целое. Он определяется проверочной матрицей Н, которая должна содержать все Т' - 1 ненулевых двоичных векторов. Используя подход, изложенный в доказательстве теоремы 7,7, легко видеть, что данный класс кодов имеет при любых s минимальное кодовое расстояние, равное 3. Это пример совершенного кода, исправляющего все однократные ошибки и ничего более. Коды Хзмминга могут гарантированно обнаруживать ошибки
кратности \ и 1.
Число кодовых слов веса / (спектр кода Хэмминга длины //) можно найти как коэффициент при D1 следующего многочлена:

Если к кодам Хэмминга добавить еще один проверочный символ (путем общем проверки на чётность), то получатся коды с параметрами |2\ 2''— s], у которых d = 4, а спектр их определяется многочленом

3. М-последовательности. Это класс кодов с параметрами (n,k) = (2' -1, s), s -целое, которые определяются как дуальные к кодам Хэмминга той же самой
282

длины. Данный класс кодов может быть определен также иначе, как совокупность выходных последовательностей при различных начальных заполнениях линейного регистра длины s со связями, выбранными так, чтобы период выходной последовательности оказался равным Г-1. ГТодтому они получили название последовательностей максимальной длины или М-последоватеяыюстсй-Все комбинации данного копа. кроме нулевой, имеют одинаковый вес Т'' и,
следовательно,  для  такого  кода  d = 2'"'.  Коды  Хэмминга  и  А/после дова'1 ел ьн ости являются крайними случаями кодов с малой и большой величиной минимального кодового расстояния. Они не всегда удобны для практического использования, поскольку исправление только однократных ошибок обычно оказывается недостаточным для обеспечения высокой верности передачи, а высокая исправляющая способность М- последовательно сто и покупается за счёт их весьма низкой кодовой скорости R. Поэтому необходимо иметь класс кодов с промежуточными значениями R. Это может быть достигнуто при переходе к определённым подклассам циклических кодов.
Полиномиальные коды. Циклические коды. Коды Боуза-Чоудхури-Хоквннгема (БЧХ). Кодовые слова двоичного линейного кода могут быть представлены в виде полиномов х{0)=-\^ +-\-,P+^D2^ ,.+x^D"~1 степени и-\ от некоторой формальной переменной D, причём двоичные коэффициенты д:, задают символы кодового слова. Полиномиальный код определяется как множество полиномов (кодовых слов) степени п-{. получаемых умножением инфор-мациоЕшого полинома b(D) степени k-\ на порождающий полином кода g{D)
степени fs-k'

Уравнение (7.63) задаёт процедуру кодирования полиномиального кода. сообщение дискретного источника кодируется примитивным кодом длины А, символы примитивного кода становятся коэффициентами информационного

определяются п коэффициентов полинома v\u}, являющихся символами кодового слова.
Из уравнения (7.68) видно, что любой из полиномов -r(D). соответствующих кодовым словам полиномиального кода, должен делиться без остатка на порождающий полином g(D}, Остаток от деления полинома y(D), соответствующего принятой из канала комбинации, на порождающий полином кода g(D) называется сиидромпым полиномом s{D). Если синдромный полином равен
нулю (те. деление произошло без остатка), то принятая комбинация является кодовым словом. В противном случае принятая комбинации не является кодовым словом. Таким образом, для полиномиальных кодов процедура обнаружения ошибок (вычисление синдрома) состоит в делении принятой комбинации на порождающий многочлен.
На практике находят применение циклические коды. являющиеся частным случаем полиномиальных кодов.
Пусть х^(л=о, a|. ..., х^ — произвольный двоичный блок длины //. Будем называть циклическим сдвигом S, /траво данного блока преобразование следующего вида:
2S3

Определение 14, Линейный двоичный (и, А)-код ^ называется циклическим кодом, если в результате циклического сдвига любой ю его комбш^аций полученная комбинация снов^ принадлежит коду, т.е. S^ eF, если к eF,
Теорема 7.9. Дгя л/о^ой» двоичного циклического (ti, ^-кода существует такой многочлен g[D) степени r^n-k с двоичными коэффициентами, который делит без остатка многочлен D'-H, и при этом любое кодовое с.гово может быть представлено каш многочлен x(D} степени п — 1 следующего вида. x(D) = g0)b(D),
где b(D) - произвольный многочлен с двоичными коэффициентами степени не выше k- I |21|.
Многочлен g(D), о котором идет речь в данной теореме, называется порождающим многочленом циклического кода. Многочлен h[D)={D" +l)/^(D) называется проверочным многочленом. Можно доказать, что многочлен h{D) является порождающим многочленом для дуального кода.
Циклические коды значительно упрощают описание линейного кода, поскольку для них вместо задания k у- {п — 1с) элементов двоичной матрицы Р в представлении (7.48) требуется задать («-А:+1) двоичные коэффициентов многочлена g(D). Кроме того, они упрощают процедуру кодирования и декодирования для обнаружения ошибок. Действительно, для осуществления кодирования достаточно выполнить перемножение полиномов, что реализуется с помощью линейного регистра, содержащего k ячеек памяти и имеющего обратные связи, соответствующие многочлену h(D) |2|], Для обнаружения ошибок достаточно разделить многочлен, соответствующий принятому слову y(D), hei порождающий многочлен g{D) и проверить, будет ли остаток от деления равен нулю. Эта процедура также осуществляется на линейных сдвиговых регистрах с обратными связями. Однако более важное преимущество циклических кодов состоит в том, что они могут быть сконструированы как коды с некоторым гарантированным значением минимального кодового расстояния. Для этого необходимо определённым образом выбрать порождающий многочлен кода g{D). Циклические коды, которые имеют порождающий многочлен, заданный своими определенными корнями, называются кодами Боуза-Чоудхури-Хокьингема (кратко БЧХ-кодами). Однако корни этого многочлена ищутся не среди вещественных или комплексных чисел, а как элементы так называемых конечных полей Галуа,
Для того чтобы ПОЯ1-Н11Т1, методы построения таких кодон н е дальнейшем рассмптрии^ть ^онс-груктиьныс методы исправления ошибок при помощи данных кодор, н;1м необходимо RKpiiiiic рассмотреть осноны теории конечных полсн.
Полем -7{не обязательно конечным) нунывастся множество ^лемснто^ для которого иы-полняются следующие с во истин:
1. Для любой пары элсмснт-он поля а е -У, Ь f= .Ропредслсиы опср,шии а + ii и их *, н^ынуе-
мые, соотиетствснно, сложением и умножсннам, отображающие пару (д, Ь) в какой-либо элемент поля Ж
2. Поле содержит нулевой элемант 0 и единичный 1, т^клс что и + С) = и, их} = а для любого и £ '?.
3. Для любого а е У существует прогиноположный (аддитивно обратный} элемент -а т,1ко1]. что (-д) + а ^ 0, и для любого л е -V, и •? О, сушс-стнует мультипликативно обратный элемент Д"! Т.1КОЙ, ЧТО t/a"1 = 1.
284

4. Для операции с :).'и; мента мл поля .F выполняются законы.
а) ассоциативный а Л [Ь + с) = {а + h} ч- с-'; и{Ьс} = {ah}c;
б) коммутативный и + Ь = Ь + л: ^ = /^,
й) ДИеГрибуТИИНЫИ О'(й + с} == 0/f -I- Ж.'.
Поль! назынастея коттиы.м (или полем Галуа. II, память об открытием его французском ученом), уели они состоит из конечного числа •элементов. Число элементов поля q называется его порядком, а само поле обозначается как GF{q).
Из определения поля нидно. что фактически дли любых пар элементов о Пред ел с h.i также " операция иычитания: <i - Ь = а - I-/?), ;i для пар д, /? ^ 0 - и операция деления ;;//? = ой~1. Докаэыиается, что в поле существует единстпснныи элемент и и единственный элемент 1. В алгебре доказывается парная теорема о том, что порядок поля q Gcern.i ПЕлнетсч степенью простого числа р, т.е. q = р1', гас i - натуральное число. Если и = 1, то поле СР(^) = ОР(р) пизынается ириачьш. Для каждого допустимого .течения q правила сложения и умножения, удонл створяющие дидянным грейоцаниям, можно определить только одним способом. Все элементы простого поли могут быть ^,цшны как множссгцо чисел (0, 1, -, у - 1), я операции над ними - клк дсиспии] по модулю р (mod р), т.е. как числа, равные остатку от деления ня р.
В качестве пример;! в табл. 7.3 даны праьила умножения и сложения для поля GF<5). Таблиц,! умножения полюляет находить обратные элементы, так, 4-' =4, поскольку 4-4=1, Таблица сложения позволит определить обратный элемент -а на пересечении в и 0. При вычитании или делении необходимо, используя таблицы, найти обратный элемент для вычитаемого [ijih делителя, а ^атем выполнить сложение или умножение обычным образом.
Например, 3-4=3 + (-4)=3 + 1=4, 3/4=3.4~' =3-4=2.

Определим операции и расширенном поле GHp"), которые не задаются уже как операции по mod р".
Поле GV{q} при ц = /?" н // = 1 называете!! расширением поля <?F(^), а поля такого i![im;i — расширенными нотами. Все элементы расширенного поля ^Г^) можно представит!, как исс-позможные плелсдоиательнлети длины и с :1Л^ментамц n'i поля GF(p). Напри мер, поле 6Т'(21} состоит нз элементов. 01)0, 00!, 010, 011, 1СЮ, 10Е. ПО, ] II.
Определение, Многочлен p{D} с коэффициентами ил пиля GFtq) налывастея непрпноли-мым над этим полем, сели он не может быть прсдетаьлсн как произведение диух и Еюлес многочленов с коэффициентами из этого поля, когда степени этих многочленов больше нуля. При проверке этого услоиня действия над коэффициентами многочленов должны производиться и поле GP{q).
Пример. Многочлен х2 + 1 приводим над <?Р[3). т.ж как х1 + I = (д + 1)(д- -г Г), многочлен ^ + х + ] нс приводим над GF{2}. так как его нельзя представить как произведение каких-либо ip следутощих многочленов степени меньше 3, но больше нуля над полем (7F(2). ,с, х + 1, х2, х^ + 1, х2 + х, х1 + у + I.
Разработаны регулярные методы гсисриронания неприиодимых многочлене и. В литературе (см., например, |21|) имеются таблицы некоторые непринодимых многочленов различных степеней. (В дснствительности имеетсч много н е при поди мых многочленов любой степени.)
Теперь мы можем описать операции над элементами конечного поля Gi''{p"} k.jk операции над последовательностями длины и н,1Д полем GF{p} Прежде псего отметим, что л^Бую тлкую
последовательность      Ь=(^, h„ ... />„_i).     Ь, е (7F(/?).     / = 0, I, .... и   I,     можно
285

прсдстанить полиномом степени п — 1 с коэффициентами над нолем f7F(/?) как
Fi—1
Л(^) = Zl^01 • тогд:1 ^У^му двух элементов поля а -г h можно получить как сумму соответст-
r=U
нукицих им многочленов, -л произведение ab — как произиеденис соотвцтстнующих многочленов по модулю неприводимого полтюлш y(D} степени п.
Пример,    а =010.    b= 111,   А^) = Л   /bW = ^ + D + 1,    у{0) = ^ + D - 1, аЬ-^(/?)А(Д) = О-1 ^ Д1 + £>(mod ^^з+0-гl)=(.03-;-^+0)..^+^^+ l(riiod Д3 + D т 1) =
- У -+ i ' 101
Поскольку существует несколько неприводимых многочленов степени л, то. кааалоо, бы, могут сущестпонать различные операции умножения для поля GPW, однако в алгебре |21[ до ка.э шлется важная теорем,! о том, что вес конечные поля (TF(^), простые или расширенные. мшигются nJOMffJfs/nn.rMii, Это ознячаст, что они фактически тождественны с точностио до псрео5тнЕ1ЧСИн^1 элементов. Поэтому пс имеет значения, кукои именно неприводимый многочлен y{D} степени и с коэффициентами из (7F(/?) был выбран для задания non^i GV[p1'}.
Определение. Элемент ое ffF(^) назывистея примшпианы.м, если йсе его степени и'. / = 0, 1, ... q — 2 рузли-чны и дают все элементы конечного поля <7F(i/), кроме нулевого. Доказынчется |211. что в любом конечном поле всегда существует прнмитииный элемент. (В деИстинтельноеги \\ кахлом поле имсс1ья несколько примитивнык элементов.) Использование понятия примитиьного элемент,! ^нучительно упрощает описание таблицы умножения элементов поля. Действительно, если ^а', Ii=ol, то {ih^a'ai = а1'''', Легко опрсдсляютем и обратные элементы, поскольку е^лн а = с^. то и"' =a'l~\~< (Однако таблица сложении не упрощается при неполно пани и лримитиыюго элемента.)
Пусл^ имеется некоторый многочлен j{D} степени я с козффициеЕП^ми и^ конечного поля G^(ff). Согласно оеноинои теореме алгебры этот многочлен может иметь в поле GF[p} не более чем /i корней, но он может не иметь н одного корня.
Определение, Неприводимый многочлен степени ч нуд полем GF(p) наущается иримитиб-/ihw мио^очленчл^ сс^и дотя бы один из его корней является примитивным элементом поли GW}
Можно доказать |31], что у примитниного многочлена вей корни являются примитиины-
мн элементами, причем если о. - один из корнсц лтого многочлене!, то u. a'', i-r'11', .., n^~i
обрачуют сонокупноеть i^cex корней этого многочлена, (В дсистиитсльности последнее сшист-ио спрдьедливо для люйого иепринодимого многочлена.) Существует и другое (экви^шентнос) определение примитивного многочлена — это такой нспринолимый многочлен степени и, что
он делит многочлен ^^"'-1 и не делит многочлены вид;1 D"'-l, сели ч1 < р"-\. В литературе
прпиодмтся таблицы прнмитииных элементов |21f. Число прими-Еинных многочленои /^(д) степени 'i определяется по формуле

где У'(/) - функция Эйлера, которая определяется как количество чисел рада 0, 1. ,,., /- I, нзаимно простых е /. Если 2" - 1 - простое число, то ^{г - \\= 2"-2 ,
Рассмотрим чаетныи случай блоковых циклических кодоп, поз ноля ющ их гарантировать
определенную величину минимального кодоиого расстояния н рсализо^ть конструктииныи алгоритм исправления ошибок гарант про пан но и кратиости-
Oiiffc^r.wnnc.: Диоичный цикличсскин код длины 2'- 1, где / - неотрицательное целое число, называемое кодом Еоуза-Чоудхури-Хоквиигсм^ (или сокращенно БЧХ-кодом) в узком смысле, если слово х принадлежит коду тогда, и тол1.ко тогда, когда а, а2,..., с2', где а - примитивный элемент ноля ОТ^), яиляются корнями MHoro'-L'icHJ f^D'}-
Э"го определение эквивалентно следующему матричному уравнению:
^'=0,                                                            (7^Уа)
286

Поскольку il пр^вш! 'тети {7.69} стоит определитель Ван-дср-Монда. то он псегда будет от.-ипсн ит нуля, и, с:лсдое;п^-][,но, не существует линейно заиисчмых комбиниций ш 2/ или меньшею чи^ла столбца матрицы Н. Поэтому 4налогнчно выводу границы Варш.ьмов,!-Гшьбсрта получим, что код, опр<-дслцемыи ур.щнешюм (?.№). будет иметь минимальной ко-
ДОНОЁ p!iC(JI'Ci51HHC//= 2/+ 1.
Можно док;13.1ть |31|. ч-ю степень порождающего многочлены g{D} такого циклического ^оди не превосходит // и поэтому -[;iKoii код содержит не более чем i! npojsep очных символик. Эгот фчкт может быть сформулиро1тн в виде следующей тьоремы.
Георсмл 7,1П. Вс^да можно /iwrnpfif/iib д^оичаыи БЧХ-код с длиной б-'iOKfi и = 2' - 1 (/ - .im-
дои натуральная числи}, который имеет k > ч - If информационных символов {s < 2;-1 - nansypcf.u-linc час-'io} и sapannwpoiiaiino исправия^т ошибки кратности не меньше, чем !.
^>гог код в отлнчнс от 1 гс кон структурного метода, который мы исполь^оиали npir иынопс границы BapuiiiMo 11,1 -Гильберта, bc^lm.i просто опрсдсля^тьн crohm порогкдающим уногочлс-ио.ч g{D}, Имскггся до^гаточно под|юбныс тублииы, которые даюг алн всевозможных наборо!;
<^fc) виды порождЕ1Юшнх мяогачлснов и соотвст^-гиующис \ш значения минимальных кодовых р;1сстоян[и1 d.
7.3.5. КОНСТРУКТИВНЫЕ АЛГОРИТМЫ ИСПРАВЛЕНИЯ ОШИБОК ЛИНЕЙНЫМИ КОДАМИ
Подытоживая сказанное ранее, можно сделать вывод, что переход к линейным кодам и к их частным случаям - циклическим и БЧХ-кодам практически полмостью решаег проблему кодирования-декодирования с обнаружением ошибок и построения кодов с большим минимальным расстоянием. Однако проблема исправления ошибок по-прежнему остаётся открытой. Действительно, даже при наиболее экономном способе синдромного декодирования необходимо произвести запоминание таблицы, содержащей 2""' различных синдромов и поиск по утой таблице. (Сложность декодирования экспоненциально зависит от А или от и - k.} Переход к циклическим кодам лишь несколько упрощает вычисление самого синдрома, но не исключает необходимость запоминания 2"~ векторов, В современной теории кодирование разработан ряд конструктивных методов декодирования, которые позволяют перейти от экспоненциальной сложности декодирования к полиномиальной. Это прежде всего:
1. Алгебраические методы декодирования для БЧХ- и родственных им кодов.
2. Мажоритарные методы декодирования-
287

При втором подходе выбираются специальные подклассы линейных кодов, имеющих так называемые "разделённые проверки". Каждый из символов блока такого кода входит только в одну из проверок для любого символа блока. Например, для кода (7, 3), дуального к коду Хэмминга, первый символ х/ блока связан проверочными соотношениями х^ = х^ Ф х^ = х^ © x-j = х^ Ф х^. После приёма кодового блока можно вычислить все эти проверки, включая и тривиальную х - Х[, и принять решение о том, равен х^ нулю или единице в зависимости от того, оказывается ли больше среди данных проверок нулей или единиц. Такой метод декодирования называется мажоритарным. Он обобщается и на другие циклические коды, хотя возможен далеко не для всех из них.
Мажоритарная процедура декодирования допускает итеративное обобщение, когда на первой итерации с использованием проверочных соотношений вычисляются апостериорные вероятности символен кодового блока в предположении, что априорные вероятности всех сим1юло[! имеют равномерное распределение. Затем на второй итерации вычисляются новые апостериорные вероятности в предположении, что априорными вероятностями в этом случае оказываются апостериорные вероятности, полученные на 1-й итерации, и ъд. При определенных условиям итеративная процедура сходится к действительно передававшемуся кодовому слову, т.е. происходит исправление ошибок,

288

Система уравнений (7-77) является линейной, и поэтому если ее решение существует, то оно может быть легко найдено. Доказывается I2i|, что если число действительно проиэощед-шнк ошибок но превосходит /, то систему (7.77} имеет решение. После нахождения неизвестных т,,..., о^ можно по (7.74) вычислить многочлен локаторов ошибок- Затем находятся
корнн этого многочлена е,, е;,..., ^ и. наконец, локаторы ошибок ^=е^. Очевидно, что нахождение локаторор ошибок позволяет найти положения самик ошибок <?, на кодовом блоке, т,е. произвести исправление ошибок,
Как видно, при использовании алгебраических методов декодирования процедура исправления ошибок имеет полиномиальную сложность в зависимости от числа ошибок ю, чем она существенно отличается от экспоненциально сложной процедуры декодирования методом перебора всех образцов ошибок. "Платой" за это преимущество является сужение класса всех линейных кодов до БЧХ. Кроме того, доказывается, что достаточно тинные БЧХ-коды имеют минимальное кодовое расстояние значительно худшее, чем то, которое гарантируется границей В аршамова-Гильберта. Впрочем, существуют такие классы кодов, как, например, коды Гоппы1^ обладающие как хорошим d, так и конструктивным алгебраическим алгоритмом декодирования.
7.3.6. ОБОБЩЕНИЕ ТЕОРИИ КОДИРОВАНИЯ НА НЕДВОИЧНЫЕ КОДЫ
До сид пор мы рассматривали только диоичныс линейные коды. Одн.жо это делалось лишь для простоты. На самом деле теория линейные кодов обычно излагается сразу для т-
ччных кодон, где т = р1, р - простое число, / - натуральное число, т.е. для случая, когда символы кода образуют конечное поле Галуа G^{q) и над ними moot быть осущсстялены вес арифметические действия, которые существуют над вещсстиенными или комплексными числами. Для таких т-ичиых кодов могут быть определены исе понятия и доказаны нее свойства, полученные ранее для двоичные кодов, л именно - порождающая и проверочная матрицы, систематические кодь;, дуальные коды, границы минимальных расстояний, стандартные расположения, синдромы, весовые спектры и границы для р^ и р^, циклические и БЧХ-коды,
алгебраические и мажоритарные алгоритмы декодиронания. Наиболее важным классом т-ичньд кодон являются коды Рида-Соломона (кратко PC-коды). Они могут быть построены как систематические циклические (п, А)-коды при и = // - 1, fs - ft = З/, / - число исправляема ошибок. Коды PC являются частью стандарта цифровой записи на компакт-диски.
11 Мак Вильяме Ф. Дж, Слоэн Н. Дж. Теория кодов, исправляющих ошибки/ Пер. с англ,;
[Год ред. Л.А, Бассалыго - NL: Связь, 1979.
2S9

Как   видно   из   определения   pc-код,!,   он   является   частным   случаем "/-ччных БЧХ-кодов.. и согласно доказанному ранее, минимальное кодовое расстояние таких кодов будет к точности райно d = п - k + I.
Легко показать, что никакой линейный систематический w-ичный {т > 2) код не может иметь d > fi — k + I, Действительно, если выбрать значения k минус одного информационного символа равными нулю, то это даст ненулевое кодовое слово веса не более чем и -k -V 1, чю по свойству линейного кода и определяет верхнюю границу для d как /) - k + 1 Поскольку PC-код реализует верхнюю границу для минимального кодового расстояния, то он оказывается оптимальным среди исех т-ичных (п, А:)-кодов в смысле исправления и обнаружения ошибок гарантированной кратности,
Можно дать простые описания РС-кодд а несистематическом представлении. Тогда кодо-иый вектор определяется как

Выбор длины кода is •s q - 1 является достаточно сильным ограничением, особенно при Большом порядке поля. Поэтому можно строить так называемые укорочинт.^ коды PC, имеющие произвольную длину и <, q - \. Их можно получить из полных PC кодов, имеющих длину л •= q - 1, если положить часть информационных символов рапными нулю и выбросить их из кодовых блоков. Легко видеть, что укорочение кода не может уменьшит!, минимального кодового расстояния, и поэтому [п. А)-код при и ^ q - 1 будет по-прежнему иметь d=n - А+ i.
Коды PC, являясь частным случаем БЧХ кодов, имеют алгебраический алгоритм исправления ошибок с полиномиальной сложностью. Коды т могут быть использованы совместно с двоичными кодами для построения так называемых каскадных кодов.
7.3.7 ИТЕРАТИВНЫЕ И КАСКАДНЫЕ КОДЫ
Мощные коды (т.е. коды с длинными блоками и большим кодовым расстоянием d} при сравнительно простой процедуре декодирования можно строить, объединяя несколько коротких кодов. Так строится, например, итератииный код из двух линейных систематических ко-дои [я,, k\) и (л^, ^} - см. табл. 7.4. Вначале сообщение кодируется кодом 1-й ступени (Д|, а]). Пуст!. ^ блоков кода 1-й ступени записаны ц виде строк матрица Ее столбцы содержат no А-? символов которые будем считать информационными для кода 2-й ступени (^A:) и подпишем к ним /^ - ^ проверочных символов. В результате получится блок (матрица til ? fi-^, содержащий /Г|^ символов, из которых а|^ Я|[лиютсч информационными. Процесс построения кода можно продолжить к 3-м измерении и т,д,
При декодировании каждого блока 1-й ступени обнаружинают и исправляют ошибки. После того как принят весь двумерный блок, вновь исправляют ошибки и стчрания, но уже по столбцам, кодом 2-й ступени, причём приходится исправлять только те ошибки, которые не были исправлены (или были ложно "исправлены") кодом 1-й ступени. Легко убедиться, что минимальное кодовое расстояние для двумерного итеративного кода d= d\d^ где d^ и д^ -соответственно минимальные кодовые расстояния для кодов 1-й и 2-й ступени.
Весьма эффективная разновидность мощных кодов - каскадные коды. Двухкаскадный код (рис. 7.6) строится следующим образом: сначала а| двоичных символов источника

290

рассматриваются как укрупненный символ ^ногопоэиционного код,! с оснонанисм п/=2*1. Затем к последовательности из Ад тутах укрупненных символов добавляется м? — ^ проьероч-иьп симиола м-ичного кода (к,эжд|.ш пропарочный символ это последо нагель но сть ш а| двоичных символов). На этом завершается образование внешнего кода. После этого формируется ish утренний код с кодовым расстоянием ^: к каждым k\ элементарным двоичном симво^адг внешнего кода прибавляется и\ — k\ проверочных двоичных символа. Результирующая кодо-ьая комбинация содержит ti|//^ диои'шых еи.шюля, из которых k\k^ яиляются информацион-Hiii,\in. Этим каскадный код похож н,1 итеративный. Однако декодирование к,1(-1адного коди 1^ыполн<[стся следующим обрачом; сначала последовательно осуществляется декодирование iiccx бтзокои ин^пюннсго кода (с обнаружением нлн исприиленисм ошибок), затем декодируется блок внешнего w-ичного кода (^, А^), причём нспраиляются ошиБки и стирания, octjii-ицшсй после декодирований инутренисго кода. Внутренний код обычно рассчитан на исправление одиночных ошибок, цнешини на исправление пачек ошибок (которые являются одиночными ошибками а укрупненных ?//-нчных символах^ (рис. 7.6). В качестве внешнего кода иг пол дуется обычно 'л-ичный код Рнда-Соломона (см, выше), обеспечиваю щи и наибольшее ночлежное t/; при заданный ^начснняч '^ л ^, сс-'ni ^ < ">•
Построенный кагк^щныи код экдивалсптен линсГпгому двоичному коду с минимальным p.ic стоянием d > d\d-^, Фактичеик.и рассмотренный выше алгоритм декодирования каскадного кода скрывается более эффектниным и npocTiiiM, чем алгоритм декодирования диоичного ко-д;| l эквивйлсичным минимальным расстоянием (/-
Исполь^овянис каскадных кодои и 2СК бе^ памяти поаноляст обсепечит^ экспониициаль-eioc убывание вероятности ошибочного декодирования при увеличенЕш полной длины блока
I 1 'г = ii\fb, при •этом скорость передачи R=—— может быть сделана екол|, угодно близкой к
"i"^
пропускной способности канала, ,1 сложность де код и ров.э и ия полиномиально занисит от пол-нон длины Блок;1 п. Еще более эффективным оказывается применение каскндных кодов и ка-н;|ла\ с памятью (см. ниже)'^ Процесс наращивания ступеней каск-шного кода можно про-лп^житъ^ Каскадные кодь] во многих случаях наиболее перспективны среди известных бдоко-шх помехоустойчивых кодов.
7.3.8. КОДИРОВАНИЕ В КАНАЛАХ С ПАМЯТЬЮ

Как было отмечено н ^ 6.2, память увеличивает пропускную способность каналов связи. Однако это не означает, что использование одних и тех же кодов в каналах с памчтыо и без памяти дает меньшую вероятность ошибочного декодирования для каналов с памятью. Более того, даже наилучшие коды для каНЕШОВ с памятью могут оказаться •значительно хуже, чем посредственные ко-дм в каналах без памяти,
^ Обойщсиныс каскадные коды» находящие применение в КЕшалах сити с ограниченной «ю-лосон ч.ютот, рЕЮСМО^фены в монографии: Блох Э .Л., Зяблов В.В. Линейные кускадные коды. - М.= Наука, 1982. - 229с.
291

Реальные физические каналы связи обладают, как правило, памятью, что может объясняться корреляцией случайных помех и параметров каналов связи. Типичными примерами каналов с памятью являются каналы с замираниями (см. § 5.7), Универсальным методом сведения каналов с памятью к каналам без памяти являются, как отмечено в g 7.3 (см, рис. 7-2), перемежение символов на передаче и их д е пер ем ежен и е на приеме. После перемежения символов можно использовать алгоритмы исправления ошибок для каналов без памяти. Платой за данное преимущество являются задержки декодирования, дополнительная память, а также упомянутое ранее уменьшение пропускной способности канала связи. Последнее обстоятельство может быть "смягчено" переходом к алгоритму кодирования-декодирования с перемежением и оценкой вероятности ошибок. В этом случае память канала используется для оценки вероятностей ошибок символов в кодовых блоках, которые затем учитываются при исправлении ошибок (см- ниже § 7,3,10 "Мягкое декодирование").
Если память канала проянпуетсл и появлении четко ныраженнык пачек ошибок, т.е. группы подряд следующих друг за другом ошибочных символов, то можно использовать спсци-;iribHLie коды, ориентированнее на испраипение ошибок именно такой конфигурации, а не независимых ошибок (см. более подробно коды Файра в |21[). Эффективными оказываются в каналах с памятью и каскадные коцы, если внутренние коды в них используются в основном для обнаружении пачек ошибок и стирания блоков, на которых эти пачки обнаружены, .1 инешний код используется для исправления стертых блоков,
В последнее время обсуждаются возможности использования в каналах с памятью метода адаптивного кодирование (де код пропан ни), когда при отсутствии псремсжсния символов иа перед-пе декодер в режиме исправления па'[ек ошибок запускается лишь тогда, когда зафиксировано группирование ошибок в канале. В остальное время декодер работает в режиме исправления одиночных ошибок. Метод адаптианого кодирования (декодирования) существенно уменьшает задержку il принятии решения по сраиненню с методом перемеженин символен на передаче и их дспсрсмсжсния на приеме.
7.3.9. СИСТЕМЫ С ОБРАТНОЙ СВЯЗЬЮ
При обнаружении ошибки в принятом блоке он может быть, вообще говоря, передан получателю с пометкой о ненадёжности, но чаще всего при нали-^ чип дуплексного канала связи используется другой подход. По обратному каналу свя:1И посылается запрос на данный блок, и тогда он передается повторно. Так продолжается до тех пор, пока данный блок не будет принят без обнаруженной ошибки. Такая система называется системой с решающей обратной связью (РОС), поскольку решение о приёме блока или о его повторной передаче производится на приёмной стороне,
Возможен и другой подход, при котором решение об этом производится на передающей стороне. Признаком, требующим повторной передачи, может быть несовпадение ретранслированного с приёмной стороны по обратному KartEiny информационного блока с действительно передававшимися или несовпадение проверочных символов кода, сформированных по переданным информационным на приёмной стороне и переданных на передающую сторону, с истинными проверочными символами. Такая система называется системой с информационной обратной связью (ИОС),
Поскольку наибольшее распространение получила система РОС, то рассмотрим да^ес кратко лишь ее характеристики. Описанный алгоритм функционирования РОС относится к так называемой системе с ожиданием, когда каждая последующая комбинация начинает пе-реданаться только после отсутствия запроса на предыдущую комбинацию. Такой протокол
292

обмен;! даннымя яиляется неэффсктнунум, поскольку канал связи не используется дпч передачи информации, пока ожидается запрос i^h подтверждение на даннук> переданную комбинацию. Наиболее эффективным является протокол с непрерывной передачей кодовых блоков, снабженных адресами, "по позволяет повторять ранее переданные блоки с теми адресами, которые были переданы по обратному каналу как адреса блоков с обнаруженными ошибками. Система с обратной связью может достаточно полно \арактери копаться двуми величина-
мл.
- остаточной иероятностью ошибки р^., которая определяется как предел отношения числа
блоков с необнаруже иными ошибками к общему числу блоков, принятому получателем при неограниченном унеличении числа переданных блокон,
- сквозной эффективностью т\. которая опрсделяс-п;» ка»; предел отношения числа принятых информационных символен к полному числу симнолов. переданных по каналу связи для обеспечения их приема при неограниченном увеличении числа переданных блоков.
Для так называемой ид^альяои адресной системы, когда не учитывается избыточность. ниосимая адресами и возможность переполнения буферных запоминающих устройств, которые всегда необходимы для запоминания ранее переданных и ранее принятых блоков, эти величины при дуплексной передаче no 2CK бм памяти с одинаковыми вероятностями ошибок симцолов могут быть рассчитаны по следующим формулам:

те р^[У} ~~ вероятность необнаруАИвасмои ошибки при использовании (я, А)-кода. V. р -вероятность ошибочного приема символа в 2СК. Э юн и валентная вероятность ошибки /э, может быть при р^ <•: 1 рассчитана как р., ^ p^-Jk , л Р^} может быть оценена по одной из
формул, приведенных в 7,3.2 и 7,3.3. (При бесшумном обратном канале и формуле (7Я1) показатель степени 2л должен быть изменен на п.) При: практической реализации протокол с адресным подтверждением требует значительные усложнений для исключения истувок и ныла-дсний блокон при ошибкам il обратном канале связи;. особенно если время распространенна сигналов fl канале связи не является в точности известным. Тогда используется менее эффективны!], но более устойчивый протокол системы РОС. который называется протоколом с био-KupuffKW. Сущность такого протокола состоит в том. что при обнаружении ошибки в блоке или приеме сигнала "з-апрое" приёмной устройство закрывается [блокируется) на время, соответствующее передуче L блоков, а на передаче осуществляются посылке! сигнала "запрос" и порториая передача L блоков, предше ответви шик текущему передаваемому блоку. Такой iinro-рптм обеспечивает отсутешие встайок л выпадении с иероятностчмн порока P^{V} и требует
W выбора /, только знания рерхньи границы ирсмсни запаэдыиания сигналов в к-шале связи. Для 2СК без памяти при одинаковых вероятностях ошибок символол it прямом и обратном каналах можно получить следующую формулу w» расчет сквозной эффективности при ис-
лользонанни данного протокола.

Видно, что в частном случае L ^ 1 (7.82) совпадает с (7.81). Для расчёта р^ в системе с
блокировкой можно испольэоиать формулу (7.80).
Помимо описанных здесь трёх основных протоколов функционирования системы РОС
существует тдкже много другид вариантов^.
Заметим, что важным положительным свойством систем с обратной связью является их адаптивность. Действительно, как это следует из (7-62), ЯиМ м0' жет быть сделана весьма малой для любых состояний канала в отличие от
'1 Kloev Т., KoJsllik V. Бггог deteclii^ codes. Klifwer Academic Publ. - 1995, - 25(1 p,
293

р^,(У) при использовании лишь исправления ошибок. Поэтому если состояние канала связи (например, р в 2СК) изменяется, причём иногда вплоть до обрыва (р - 1/2), то р^{У} всё равно оказывается достаточно малой, а скорость передачи будет значительно изменяться в соответствии с (7.81) или (7.й2), подстраиваясь (адаптируясь) к состоянию канала и обеспечивав достаточно высокую среднюю скорость передачи, В системах с обратной связью можло использовать также и частичное исправление ошибок, что может существенно увеличить сквозную эффективность, но приведёт к неизбежному усложнению аппаратного или программного обеспечения.
7.3.10. ЗАКЛЮЧЕНИЕ ПО § 7.3. ОБЪЕДИНЕНИЕ ОПЕРАЦИЙ ДЕМОДУЛЯЦИИ И ДЕКОДИРОВАНИЯ. ДЕКОДИРОВАНИЕ С МЯГКИМ РЕШЕНИЕМ
Подводя итоги $ 7.3, можно сделать вывод, что изложенные в нем результаты позволяют в значительной мере решить проблемы I — 4, сформулированные в начале этого раздела для 2СК или тСК без памяти или в случае произвольных каналов, но при использовании случайного перемежеиия символов на передаче и обратного их деперемежения на приёме или использовании стохастических преобразований каналов^. (В теории кодирования изучаются также коды. которые специально ориентированы на исправление ошибок в виде пачек, т.е. конфигураций, вероятность появления которых зависит лишь от протяженности участка кодового блока, поражённого ошибками, но не зависит от числа ошибок на этом участке.)
Однако мы не рассмотрели еще случай, когда в системе связи используются некоторые помехоустойчивые (например линейные блоковые) коды и для декодирования используются не значения дискретных символов, полученные после демодулятора, а значения •элементов непрерывных сигналов, соответствующих переданным символам, или адекватные им достаточные статистики, например отсчёты на выходах согласованных фильтров (см. гл, 5),
Разделение операций демодуляции и декодиротшния ни приемной стороне носит услои-ный характер. Действительно, при использовании помехоустойчивого двоичного блочного ко-д;| с длиной блок,! // можно рассматривать и последовательных канальных сигналов [которые не янлякугся независимыми и раиноиероятными, так как они связаны проверочными соотношениями кода) как один "составной" или "сложный" сигнал длительностью дГ .
Таким обраэом, получим систему, в которой для передичи 2* сообщении используется 2' "сложнык" сигналов длительностью пТ каждый. Для указанных сигналоп .можно построить оптимальный приемник (как описано \\ r-'i. 5), который обеспечивает минимально почможную вероятность ошибочного приёма сообщения, совмещая в себе функции демодулятора и декодер;! (объединял операции демодуляции и декодирования). Он отображает каждую реализацию длитсльнос-п.ю иТ ни выходе канала и одно из 2* сообщений.. т,с. реализует firкпди/юиц -am-' и тираним смысле. Точно так же можно последо петель но иклютсиныс кодер и г^олулятор
заменить одним устройством, которое будс-г с каждым из 2* сообщений сопостаплять сложный сигнал для передачи по кангшу. Такое устройство ныгю-1нясг кодирование и широком смыс-
ItV,
Рассмотрим алгоритм работы оптим.шьного приемника кодиронанных сигналов. Будем считать, что элементарные двоичные сипгалы на передаче противоположны и имеется klih.ui i;
постоянными параметрами и БГШ, Тогда учитывая, что энергии лсед ^ сложных спп^шов одинаковы, получ.изм (см.(5.28))
11 Коржик В,И, Финк Л.М. Помехоустойчивое кодирование дискретных сообщений в каннах со случайной,етруктурой. - М. Сиязь. - )975. - 271 с.
294

где д/(/), /^[0, /??'], /=0.,.. 2^-1, - сложный сигнал, соошетствующий/-и кодовой комбинации, -^(/)=Д^(/-/Т)./еГ/7\(/'-|-Е)Г]. 1=Г, .,, ff, - один из двух противоположны? сигналов,
передаваемый в составе j-го сложного сигнала на /-и позиции и определяемый /-м кодовым
символом -с^. л^ е{-], ]}; s(s) задан на интервале длительностью Т. В соответствии е пред-
стаиленной формулой сначала по 2^) вычисляегся вектор ^=(^о, .., )"^_i). компоненты кото-jioro могут быгь полугсны как отсчёты (в моменты, кратные 7) с выхода фильтру, согласо-пунного с элементарным сигналом .<(/): затем иычисллстся скалярное прои:жеденнс вектора ^
с каждым возможным кодовым вектором с^=(^;, .,,, х,^} и принимается решение и пользу
того кодового вектора, который обеспечицает максим;1льное значение скалярного прои.щеде-ню|, Ск.1лнрное прои^веденш: (xj, Д.) может быть найдено с помощью цифрового фильтра гсм. гл, 10), как показано на рис. 7.7.
Таким образом, оптимальный приемник кодированных сигнале^ [которой использует информацию о входном непрерынном сигнале) можно редставить как последовательное соединение демодулйтора с мягким решением и декодера 4- мягким решением,
Из рис, 7,8 видно, что разница между декодированием с мягким решением и декодирова-

295

нисм с жёстким решением состоит в. том, что жёстк-ии декодер рлботяст тол1.ко с вектором У=(Уо. •••^ y„-ij\ ^г=sl^n(^^)' я л^яг^я/ декодер использует дополнительную информацию и
надежности компонент лектора у, которую можно получить на основе анализа неличин '>., . чем больше величина ^|, тем нцдйжнср принятое в выходном блоке демодулятора жёсткое решение у,- Демодулятор, выдающий на выкод дополнительную информацию о надёжности своих решений, называется демодуляторам с мягким решением {выходим}, рис. 7.К-
Дскодирование с мягки м-р еще ни ем устраняет потери, связанный е принятием промежуточного решения и выходном блоке демодулятора (т.е. с •заменой I, на у,}. Оптимальным по
помехоустойчивости алгоритмом мягкого декодирования является объединение операции демодуляции и декодирования (см. рус-7-7). С другой стороны, сложность декодера рис. 7.7 .иэачитсльнЕ!, поэтому предложено много алгоритмов декодирование с более простои рсалича-цчсн, способных в той или иной мере учитывать информацию о надёжности решений, принимаемых демодулятором.
Поскольку при мягком декодировании используется более полная информация о принятых символах, то следует ожидать получения меньших вероятностей ошибок для того же самого кода, чем при жёстком декодировании. Очевидно, что для рассмотренной выше модели постоянного канала с аддитивной помехой в виде БГШ мы получаем алгоритм максимума правдоподобия, эквивалентный декодированию по минимуму евклидова расстояния. Причём если при передаче двоичных противоположных сигналов в таком канале связи оптимизация кода по-прежнему будет соответствовать максимизации минимального расстояния d, то для т-ичных кодов требуется максимизация минимального евклидова расстояния, что необязательно будет адекватно максимизации d.
Д-ич мягкого декодирования также существуют экспоненты нероятностеи ошибок и rp.i-ницы ошибок при и^йсетном спектре кодов- В последнем случае дли двоичных противоположных сигналои в не искажающем канале l. БГШ оптимальный алгоритм мягкого дскодиро-и;1Н[]я мо^е-г о&еспечить следующую-границу для вероятности ошибки.

/з V
где II =^,— - отношение энергии элементи снгнЕ1ла к спектральной плотности белого шума '•и
il к.шалс связи, [n,\ — спектр иссов кода.
^ Для мягкого декодирования также можно рассчитать ЭВК от применения кодирования, который будет, очевидно, превосходить ЭВК для жесткого декодирования, причем для каналов с постоянными параметрами типичный выигрыш имеет порядок 2 дБ.
Для конструктивной реализации мягкого декодирования невозможно в чистом виде использовать алгебраические методы, хотя имеются некоторые их модификации приемлемые в этом случае, такие, например, как декодирование по минимуму обобщённого расстояния или мажоритарное декодирований. Наиболее перспективным для реализации мягкого декодирования (совместной демодуляции-декодирования), в том числе и для каналов с памятью, оказалось применение сверточных кодов, которые допускают использование оптимального, но вместе с тем практически реализуемого алгоритма Витерби. Этот подход изложен в следующем параграфе данной главы.
1} Блей\у1 Р. Теория и практика кодов, контролирующих ошибки / Пер. с е!нгл. Под ред. К. III. Зншнгирова. - М- Мир. - 1986, - 576 с,
296

7.4. СВЁРТОЧНЫЕ (РЕШЁТЧАТЫЕ) КОДЫ
Выше рассматривались блоковые коды, когде! значения элементов, входящих в различные блоки, оказывались независимыми друг от друга.
Для систематических двоичных блоковых {п, А)-кодов последовательность информационные символов источника разбивается на блоки длиной k бит и затем в кодере к каждому такому блоку добавляется г = п - k проверочных символов, после чего блоки длиной // символов передаются в канал свлзи. Декодирование блоков также производится независимо друг от друга,
Однако возможен и другой, пепрерыеньш принцип кодирования и декодирования, когда на вход кодера поступает непрерывная последовательность информационных символов источника, а с выхода кодера также снимается непрерывная последовательность символов, являющихся функцией входных символов и структуры кодера. В декодере такого типа на вход поступает непрерывная последовательность символов из канала связи (возможно, искажёниая ошибками), а на выходе восстанавливается (возможете, с ошибками, но, как правило, меньшими чем канальные) последовательность информационных символов. Наиболее распространенным классом непрерывных кодов являются так называемые свёрточпые коды, для которых операция формирования выходной последовательности по задаимой входной последовательности является линейной. Свсрточные коды были впервые открыты Л. Финко.ч и П. Элайесом, вскоре Во^енкрафт разработал метод последовательного декодирования свёр-точного кода [13], В 1967 г. появился алгоритм Витерби для оптимального декодирования свёрточных кодов [б].

Структуру двоичною снёрточного куца со скоростью R=— покачана на рис- 7.9 Свер-
ч
точный кодер состоит из едвиюного регистра, включающего v -пеек памяти, блока сумматором по т<х12, входы каищого из которых связаны с некоторыми нынодамл ячеек памяти регистра, onpi- • |яемшМ|] коэффициентами h,. ^(0. I). Вшоды сумм.гюрон считынаютс^ при по-
мощн коммуг,1тор>1 К н подаются ь KaH,Li с]8яэи. Таким обрсиом, на каждом тиктс в р1;пи:гр сди»т иоследонательно пси;тупает очередной блок и.1 k. информ-шионных симвилоь источника II одновременно он освобождается от k символен, содержа шихся е его крсшних правых ячейках памяти. На •d-гом же тпкт^ формируются п выходнык ^имиолон. котщэые последовательно считываются и кзнал связи. t;iioim обрапом, если ^ц — скорость поступления симиолоь и кодер, то для отсутствия растущих зидсржск во нремени скорость передачи симиолон по к-iHiviy
Ч                                                                                          г .           -
сшгзи должна быть не меньше чем у( =—Гщ откуда нидно, что отношение к./п дсистиитсл].нп я
определяет скорость свсрточноШ кода. Величина v (или длина регистр;!) обычно на-зынаетси длиной кидойого ограничен tsu.'^

(Возможно и другое, более общее представление сиерточного кодера в ииде схемы с k регистрами сдвига е кодоными ограниченичми у| (/ =•• 1, 2, .-, k.) На вход каждого [гз них подается одни информационный символ за врем^ одного такта |13]-)
На рис. 7^1U показан частный случай евирточного кода со скоростью 1/2 и
Ji В некоторых работах длина кодового ограничения определяется числом ячеек гднигого ре-
niCTpil минус I.
297

длиной КЛД01ЮГО ограничения г= 3. При нулевой информационной последовательности выходная кодовая последовательности также равна нулю. В табл. 7.5 приведен пример формирования выходной послсдовлгельности для кодера, показанного на рис. 7.10. Выходная по^юдо-пательно^гь кодера мо^ет быть представлена как цифропая свертка входной информационной
последоцатсльноети и импульсного отклика кодеру (отсюда начнунис кодов - с^рточпые}.

Сверточнын код характеризуется следующими параметрами: отпостт^ьноя скоростью кода R^kjn 11 избыточностью ж= 1-R, где k и л - число информационные и кодовых символен,
соответствующих одному такту работы кодера (для кодера рис. 7.10 rt=1/2): е^тюи юидово^
ограничения г (длина регистра кодера), порождающим musiitiawM коДт- коэффициенты которых описывают связи сумматоров с ячейками регистра кодера (для верхнего сумматора
^[1] = 1.1-У+L»2, для нижнего сумматора g^^l^y2). Полиномы обычно записывают сокращенно, обозначая каждые три слюда (двоичных коэффициента) как одну восьмеричную цифру (код рис. 7.10 обозначается (7»5))-
К-ромс перечисленных выше параметрои еьсрточный код характеризуется свободном рас-^пацпигм d | под которым понимают русстозжие по Хсммингу между двумя полуб^скоисч-
ними кодовыми послсдоиатслы-ЕОСТями- Если две одинаконьи: информационные последоц,!-тсльнос-ш кодироват!! с помощью кодер,!, изображённого не! рис. 7.10, то соответствующие: им кодоные последовательности будут совпадать друг с другом. Если и некоторый момент и одной информационной последовательности окажется символ 0, - в другой I, то с этого момента кодовые поеледовател1.ности будут отличаться друг от друш независимо от дальнейшего содержания информационных по следоиательн остей- Минимальное расстояние по Хенмынгу между любыми двумя полубсеконечными кодовыми последоиатсльн остами с того момента, как соответствующие им информационные последовательности начинают различаться, называется свободном расстоянием свёргпочк^го юоди </^ '
Свободное расстояние d^ характеризует помехозащитные сиойетва оберточного кода (аналогично тому как минимальное расстояние а характеризует помехозащитные свойства блочных кодоб), Оно показывает, какое наименьшее число ошибок должно пеэоизоити и канале для того, чтобы одни кодовая последовательность перешла в другую и ошибки не были об-наружен!,]. Дли кода, приведенного и нашем примере, снободное расстояние d^ =5 ,
Поиск хороших еверточных кодов (с наибольшим d^ при заданных R и г) обычно оеу-
шсетвляетси методом перебора веек порождающих полиномов на ЭВМ, Таблиш.! хороших ко-дои приведены в 113|-
Свёрточные коды являются частным случаем (линейной реализацией) так называемых решётчатых кодов. Можно также полагать, что решётка является просто другим (иногда более удобным) способом предстайления и обычных свёрточных кодов,
Решеткой называется ориентированный граф с периодически повторяющейся структурой "ячеек". Каждая ячейка содержит колонки из одинакового числа вершин (узлов), соединённых ребрами- Между процедурой кодирования сверточным кодом и решёткой имеется взаимно однозначное соответствие, которое задастся

следующими правилами [6|:
298

- каждая вершина (узел) соответствует внутреннему состоянию кодер;!;
- ребро, исходящее из каждой вершины, соответствует одному из возможных символов источника (для двоичного источника из каждой вершины выходит два ребра ~ верхнее для 0 и нижнее для I),
- над каждым ребром отмечены значения символов, передаваемых в канал связи, если кодер находился в состоянии, соответствующем данной вершине и источник выдал символ, соответствующий думному ребру;
- последовательность ребер (путь на решётке) — это последовательность символов, выданных источником.
Так, если под состоянием кодера понимать содержимое двух последних ячеек памяти (2, 3) в регистре сдвига на рис. 7JO, то решетка с четырьмя состояниями, соответствующая данному кодеру. будет иметь вид, показанный на рис. 7.11 (решетка может отражать и нелинейный кодер, когда выходные символы не являются линейной функцией входных), teik же как и блоковые коды, свёрточные допускают представление в виде полу-бес ко печные порождающих или проверочных матриц, однако представление н виде решетки оказывается более удобным для описания алгоритмов декодар о рання.

Свёрточные коды имеют следующие основные преимущества перед блоковыми при их использовании для исправления ошибок.
1. Они не требуют синхронизации по блокам, а лишь синхронизации коммутаторов /С (на передаче и приёме),
2. Если кодовое ограничение v выбрать равным длине блокового кода, то исправляющая способность свёрточного кода оказывается больше, тем исправляющая способность такого блоковою кода (при наилучшем выборе обоих
кодов),
3. Алгоритм декодирования свёрточных кодоц допускает простое обобщение на случай мягкого декодирования, что обеспечивает дополнительный анергети-ческий выигрыш.
4. Свёрточные коды допускают простое объединение кодирования и модуляции (так называемая кодированная модуляция или сиг: tdJiwo-кодовые конструкции), чгп особенно важно при построении энергетически эффективных систем связи для каналов с ограниченной полосой частот, Для оптимального декодирования свёрточных кодов в каналах без памяти часто используется рекуррентный алгоритм декодирования Витерби (АВ). Рассмотрим его на примере мягкого декодирования в постоянном канале с аддитивным белым гауссовским шумом.
Поскольку принимаемый сигнал на k-м тактовом интервале нам известен, то можно вычислить евклидовы (или гильбертовы) расстояния между принятым сигналом и всеми возможными сигналами:

299

где ^°(/) — ожидаемый в месте приема сигнал, соответствующий /-му символу (для двоичных сигналов / = 0,1), z^{l) — сигнал, принятый на k-м тактовом интервале,
Теперь можно каждому ребру решетки последовательно приписывать на k-\ её ^йеньях значения Ду, Оптимальное по правилу максимального правдоподо-бия декодирование будет тогда соответствовать выбору такого пути на решётке
(т,е, последовательности непрерывно продолжающихся ребер), что ^Л^- ока-i
жегся минимальной. Казалось бы, для решетки длины п (т.е. для последовательности переданных символов длиной п) нужно для этого перебрать 2" возможных вариантов, но в действительности это не так. Ключевой момент АВ состоит в том, что для каждой вершин на данном шаге (такте) имеется множество метрик, соответствующих соединённым с ней ребрами вершинам на предыдущем шаге можно оставить только одно ребро, которое минимизирует сумму метрик на всех предыдущих шагах.
Проще всего можно пояснить данный ,ц|горитм на простом примере. Пусть решетка имс-бт чсёго лпа состояния и структуру, показанную на рис. 7.12, где над ребрами подписаны соответствующие метрики. по-нушсм, что первый информационный симиол 0. Тогд,! пути, ос-таилениыс ("выжившие") на различных шагах, показаны на рис. 7.13. Видно, что на 4-м шаге получаем пыжнеший путь, который s услоинпх наших обозначений (ориентация ребра чниз — 1, вверх - 0} соотт^етстйу^г информационной по ел едо стельности ОЦЮ.
Сложность АВ определяется на каждом шаге числом сравнений метрик, соединяющих есе вершины, и оно ограничено величиной М2, гле М— число состояний решетки. Поскольку из схемы сверточного кодера получаем, что
М=2''', где v "- число ччеек памяти регистра сдвига кодера, то видим, что сложность ДВ экспоненциально зависит от длины кодовых ограничений, но линейно зависит от длины передаваемой последовательности. Поэтому длина кодовых ограничений v при использовании АВ в качестве алгоритма декодирования обычно выбирается не более |0„Л5, что, впрочем, оказывается вполне достаточным для получения большого энергетического выигрыша, ЛВ требует обработки всей последовательности сигналов для оптимального декодирования даже первого информационного символа. Такая процедура требует значитель-

300