Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.3. Расчет характеристик

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

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

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

1.3.1. Точное вычисление вероятности ошибки

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

Рис. 1.6. Обобщенная таблица декодирования блокового -кода

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

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

событие A: для передачи выбрано кодовое слово; событие В: принятое слово соответствует исправляемой части столбца (верхняя часть столбца);

событие С: принятое слово соответствует обнаруживаемой части таблицы на рис. 1.6.

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

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

где

а можно легко найти из (1.15) — (1.17).

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

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

Равенства (1.15) — (1.18) можно использовать лишь для очень малых значений К счастью, они сильно упрощаются, если блоковый код является групповым. Чтобы произвести это упрощение, нужно использовать пока не рассматриваемые свойства групповых кодов. Мы надеемся, что читатель поверит в наличие этих свойств, которые будут обоснованы в гл. 2.

Здесь потребуются следующие свойства групповых кодов:

1) сумма любых двух кодовых слов по модулю 2 также является кодовым словом;

2) групповой код всегда содержит кодовое слово, состоящее целиком из нулей;

3) если сложить (по модулю 2) фиксированное кодовое слово со всеми кодовыми словами, то снова получится множество всех кодовых слов, расположенных, быть может, в другом порядке.

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

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

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

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

Далее, замечая, что

сразу получаем

Наконец, еще одно упрощение формулы (1.21) можно сделать, когда декодер исправляет все комбинации из I или менее ошибок. В этом случае все кодовые слова можно разбить на множества в соответствии с весом кодового слова. Затем суммирование в (1.21) можно выполнить так: сначала произвести суммирование по всем словам веса 1, затем по всем словам веса 2 и т. д. Введем следующие обозначения:

событие B - принятое слово совпадает с одним из слов, расположенным в исправляемой части таблицы под некоторым кодовым словом веса

— число кодовых слов веса (спектр кода);

среднее число ненулевых информационных символов, соответствующих кодовому слову веса

Равенство (1.20) можно теперь записать в виде

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

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

Отсюда вероятность обнаружения ошибочной последовательности

Наконец, для определения средней вероятности ошибочного бита перепишем (1.21) в виде

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

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

Если представить в виде то это выражение является, как можно видеть, главным членом в (1.26).

<< Предыдущий параграф Следующий параграф >>
Оглавление