2.9. Методы сравнения корректирующих кодов

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

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

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

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

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

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

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

,

или согласно (2.23)

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

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

Довольно часто, особенно в теоретических работах, при рассмотрении блочных кодов мерой верности считают вероятность правильного декодирования блока (кодовой комбинации). Мы также пользовались этой мерой в § 2.5 при отыскании асимптотических значений при увеличении длины блока. Однако для сравнения различных кодов с различной длиной кодовой комбинации и различной избыточностью такая мера не адекватна, не говоря уж о том, что она не применима для непрерывных кодов. Так, например, если в одном коде блок содержит 5 информационных символов и правильно декодируется с вероятностью 0,999, а в другом коде блок содержит 200 информационных символов и правильно декодируется (в том же канале) с вероятностью 0,99, то было бы опрометчиво считать, что первый код обеспечивает более высокую верность, нежели второй. Действительно, если нужно передать сообщение, состоящее, скажем, из 400 информационных символов, то при использовании первого кода это сообщение займет 80 кодовых комбинаций и вероятность того, что сообщение будет принято правильно равна. Если же применить второй код, то все сообщение уложится в 2 кодовые комбинации и будет принято верно с вероятностью . Таким образом, вероятность правильно принять сообщение при втором коде больше, чем при первом, хотя вероятность правильного декодирования кодовой комбинации для первого кода выше, чем для второго.

Более разумной мерой верности, с которой часто приходится встречаться (например, [24]), является вероятность правильного приема символа после исправления ошибок (или после представления декодированного сообщения примитивным кодом). Обычно удобнее пользоваться не вероятностью правильного приема после исправления, а её дополнением до единицы — вероятностью неисправленной ошибки. Такая мера позволяет сравнивать коды с различной длиной кодовых комбинаций и даже непрерывные коды. Она достаточно объективна и вполне пригодна для таких систем связи, в которых некоторое количество неисправленных ошибок в принятом сообщении допустимо, по желательно, чтобы их было меньше. Чаще всего это происходит, когда само сообщение имеет некоторую избыточность и отдельные ошибки не искажают его смысла и могут быть исправлены получателем. Примером служит телеграфная связь при передаче осмысленного текста.

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

Для иллюстрации сказанного вернемся к рассмотренному выше примеру и вычислим вероятность неисправленной ошибки для двух конкурирующих кодов. Предположим при этом, что по структуре кодов в случае ошибочного декодирования кодовой комбинации в среднем половина информационных символов оказывается искаженной. При первом коде в среднем на 1000 комбинаций (т. е. на 5 000 информационных символов) ошибочно декодируется одна комбинация. Это значит, что в среднем на 5 000 информационных символов приходится 2,5 неисправленной ошибки, т. е. вероятность неисправленной ошибки равна . Для второго кода ошибочно декодируется одна комбинация из ста, т. е. на 20000 информационных символов приходится 100 неисправленных, или вероятность неисправленной ошибки равна . Таким образом, вероятность неисправленной ошибки для второго кода в 10 раз больше, чем для первою, тогда как вероятность ошибочного приема сообщения из 400 информационных символов, как было показано выше, для первого кода почти втрое больше, чем для второго.

Это кажущееся противоречие объясняется тем, что при использовании второго кода неисправленные ошибки группируются более тесно, чем для первого. Поэтому, хотя во втором коде вероятность неисправленной ошибки больше, чем в первом, вес же имеется больше шансов избежать образования пачки ошибок при передаче одного сообщения. Заметим еще, если паше сообщение, содержащее 400 информационных символов, декодировано неверно, то при использовании первого кода оно будет, вероятнее всего, содержать 2—3 ошибочно принятых символа, тогда как при втором коде количество ошибочно принятых символов будет близко к 100. Отсюда можно заключить, что при телеграфной передаче осмысленного текста лучше применять первый код, тогда как в тех системах связи, где любые ошибки одинаково недопустимы, второй код имеет явное преимущество.

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

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

                         (2.62)

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

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

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

Формула (2.62) справедлива и дли примитивного кодирования, когда число символов  в кодовой комбинации совпадает с числом информационных символов . Для двоичного постоянного симметричного канала при примитивном кодировании  и  и, следовательно,

                        (2.63)

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

                          (2.64)

Здесь индексы 1 и 2 относятся к сравниваемым системам. Отсюда вытекает возможность характеризовать любую систему связи с любым кодом с помощью вероятности ошибки в эквивалентной ей двоичной системе связи с примитивным кодом. Назовем эквивалентной вероятностью ошибки  системы связи величину вероятности ошибки в постоянном симметричном двоичном канале, в котором система с примитивным кодированием оказывается эквивалентной рассматриваемой системе [31].

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

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

откуда

       (2.65)

где  — вероятность  ошибочного   декодирования кодовой комбинации.

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

При

                                             (2.66)

Аналогичная величина, названная относительной вероятностью ошибки декодирования, была введена также в работе В. И. Сифорова [32].

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

                               (2.67)

где  — вероятность   ошибочного   приема   сообщения, содержащего  двоичных единиц информации.

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

(приближенное   равенство  справедливо при ), откуда

                                                 (2.68)

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

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

Здесь первый член представляет вероятность того, что все символы приняты верно, а второй член — вероятность того, что искажен один символ из семи. Эквивалентная вероятность правильного приема равна

При  это выражение можно приближенно записать, пренебрегая высокими степенями , так:

откуда эквивалентная вероятность ошибок равна

                                      (2.69)

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

откуда с учетом  (2.66)  непосредственно следует  (2.69).

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

                               (2.70)

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

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

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

                       (2.71)

Из полученных выражений видно, что эффективность корректирующих кодов тем выше, чем меньше вероятность ошибки  в стационарном симметричном канале. Так, например, при  эквивалентная вероятность ошибки для кода (7,4) согласно (2.69) приблизительно равна 0,05, т. е. всего лишь в два раза меньше, чем при примитивном кодировании, тогда как при  эквивалентная вероятность ошибки оказывается порядка , т. е. в этом случае повышение верности оказывается весьма существенным.

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