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

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

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

(V.3.1)

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

(V.3.2)

Можно полагать, что подмножество содержит относительно мало сигналов, для которых условие (V.3.1) будет выполняться, а неравенство (V.3.2) окажется нарушенным. Поэтому следует ожидать, что разбиение окажется достаточно близким к оптимальному, если в каждое подмножество включить все сигналы , такие, что

(V.3.3)

Декодирование по критерию отношения правдоподобия с критическим уровнем гарантирует включение

в подмножество сигналов с наибольшими вероятностями и наименьшими вероятностями , причем для любого k и вероятность меньше, чем вероятность получить любой сигнал , принадлежащий подмножеству . Указанные свойства сигналов подмножества являются необходимыми условиями как для того, чтобы при ограниченной сверху вероятности вероятность была максимальна, так и для того, чтобы при ограниченной снизу вероятности вероятность была минимальна. Эти обстоятельства являются косвенным подтверждением близости алгоритма (V.3.3) к оптимальному.

Найдем конструктивные алгоритмы декодирования для ряда конкретных матриц . Пусть канал симметричен

, тогда из неравенства (V.3.3) получим

(V.3.4)

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

(V.3.5)

где

(V.3.6)

Следствие 1 (теоремы V.2). Процедура декодирования (V.3.6) обладает определенной устойчивостью (инвариантностью) относительно значений и .

Следствие 2 (теоремы V.2). Изменение величины осуществляется скачкообразно при некоторых критических значениях .

Эти обстоятельства непосредственно вытекают из того, что в (V.3.5) разность может принимать целочисленные значения: 0, 1, 2,...

Как следует из (V.3.5),(V.3.6) при множество оказывается пустым (система типа М+1 вырождается в систему типа М). Если , то подмножество будет содержать только комбинации , удовлетворяющие условию и т.д. При каждое подмножество включает в себя только одну комбинацию, а именно . Наконец, в случае, когда , все подмножества окажутся пустыми, а скорость передачи окажется равной нулю. При возникновении последней ситуации мы будем говорить, что система связи -разомкнута.

Следствие 3 (теоремы V.2). Для каждого заданного и фиксированного кода можно указать два таких отношения , что в первом случае система типа окажется -разомкнутой , а во втором — выродится в систему типа .

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

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

(V.3.7)

Заметим, что вероятность при фиксированном v тем больше, чем больше d. В то же самое время вероятность того, что при передаче сигнала будет принято решение , равна

(V.3.8)

Вероятность является нижней оценкой вероятности обнаружения ошибки декодирования.

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

(V.3.9)

Заметим, что значение у по-прежнему определяется формулой (V.3.6) при замене в ней на . Оно оказывается меньше, чем в предыдущем случае (введение интервала стирания уменьшает отношение ).

Формулы для расчета вероятностей и оценки вероятности системах с симметричными стирающими каналами имеют вид:

(V.3.10)

(V.3.11)

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

В случае, когда канал является симметрическим с двумя градациями верности , из неравенства (v.3.3) следует:

(V.3.12)

где L определяется формулой (IV.8.13), а — формулой (V.3.6) после замены в ней на .

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

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

(V.3.13)

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

(V.3.14)

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

(V.3.15)

Заметим, что для формула не имеет

смысла, и, следовательно, система окажется -разомкнутой уже при .

Таким образом, процесс декодирования начинается с определения числа . Если окажется, что

(V.3.16)

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

Во всех остальных случаях принимается решение . Вероятность правильного опознания переданного сообщения при фиксированном (V.3.16)

(V.3.17)

где , если , и , если .

Вероятность неправильного опознания сообщения при тех же условиях

(V.3.18)

где если , и , если .

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

(V.3.19)

(V.3.20)

Средняя вероятность правильного и неправильного опознания сообщения

(V.3.21)

(V.3.22)

где — число используемых алгоритмов декодирования.

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

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

Справедливость этого утверждения вытекает из непосредственного анализа соответствующих выражений. Таким образом, для простых систем типа весьма актуальной оказывается задача поиска кодов, оптимальных в смысле максимума d, а не в смысле максимума , как это было в случае систем топа М. Но, как и прежде, такие коды обеспечивают лишь экстремум верхней и нижней границ интересующих нас величин. Другими словами, среди кодов с одинаковыми d можно отобрать коды, которые будут несколько «лучше» остальных. Однако, как правило, все коды с максимальным значением d обеспечивают практически одни и те же значения и .

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

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

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

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

(V.3.23)

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

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