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

Распределение весов W(С) = {A_i ,0 ≤ i ≤ n} кода С, исправляющего ошибки, определено как совокупность п + 1 целых A_i где A_i — количество кодовых слов Хеммингова веса i.

В следующем ниже разделе выводится оценка вероятности необнаруженной ошибки линейного кода в ДСК. Заметим, прежде всего, что вес wt(v) слова v равен Хеммингову расстоянию до нулевого слова, т.е. wt(v) = d_H(v,0). Напомним также, что Хеммингово расстояние между кодовыми словами v₁ и v₂ равно весу их разности,

где из линейности кода следует, что v₃ С

Вероятность необнаруженной ошибки P_U(C) равна вероятности того, что принятое из канала связи слово отличается от переданного, но имеет нулевой синдром, т.е.

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

В ДСК вектор ошибок веса i возникает с вероятностью, равной вероятности того, что i символов приняты с ошибкой, а остальные n-i приняты правильно. Обозначим вероятность этого события через Р(е,i). Тогда

Для того чтобы возникла необнаруженная ошибка, вектор ошибок должен быть ненулевым кодовым словом. Имеется А_i кодовых слов веса i в кодовом множестве С. Следовательно,

(1.26)

Формула (1.26) дает точное значение Р_и(С) в ДСК. К сожалению, для большинства кодов, имеющих практическое значение, распределение весов неизвестно. В таких случаях, можно использовать тот факт, что число кодовых слов веса i меньше (или равно) общего числа слов веса i в двоичном векторном пространстве V₂. Следовательно, справедлива следующая верхняя граница:

(1.27)

Примечание На самом деле допустима и более сильная оценка:

В уравнении еН^т = 0 матрица Н имеет ранг p=d_min-1 и, по меньшей мере, р неизвестных элементов любого вектора ошибок е определяются однозначно. Следовательно, средняя вероятность того, что произвольный вектор ошибок совпадает с некоторым кодовым словом, не превосходит 2^-p.

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

Рис. 6. Точное значение и верхняя граница вероятности необнаруженной ошибки для двоичного линейного (4,2,2) кода в ДСК.

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

Пример 8. Для двоичного линейного (4,2,2) кода из Примера 4 W(C)=( 1,0,1,2,0). С помощью (1.26) находим

На Рисунке 6 показана зависимость Р_и(С) вместе с правой частью границы (1.27).

1.4.2. Границы вероятности ошибки в дск, каналах с абгш и с замираниями

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

Модель ДСК

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

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

(1.28)

где это максимальный вес лидера смежного класса е. Для совершенных кодов = t,

и из границы Хемминга (1.24) следует, что

В общем случае для двоичных кодов выражение (1.28) дает нижнюю границу P_C(C), так как существует хотя бы один лидер смежного класса веса более t.

Вероятность неправильного декодирования или вероятность ошибки декодирования равна вероятности того, что вектор ошибок принадлежит дополнению множества исправляемых ошибок, т.е. P_e(C) = 1 - P_C(C). Из (1.28) получаем,

(1-29)

Наконец, учитывая обсуждение оценки (1.28), получаем верхнюю границу

(1.30)

которую можно записать и в следующем виде

(1.31)

Рис. 7. Вероятность ошибки декодирования для двоичного (3,1,3) кода.

Эти границы удовлетворяются с равенством только для совершенных кодов (когда и граница Хемминга удовлетворяется с равенством).

Пример 9. На Рисунке 7 показана зависимость Р_е(С) по оценке (1.31) от переходной вероятности ДСК p для двоичного (совершенного) кода-повторения (3,1,3).

Модель канала с АБГШ Пожалуй, наиболее важной моделью для систем цифровой связи является модель канала с аддитивным белым гауссовым шумом (АБГШ - additive white Gaussian noise (AWGN)). В этом разделе выводятся оценки вероятности ошибки декодирования и вероятности ошибки на бит для линейных кодов в канале с АБГШ. Хотя аналогичные выражения оказываются справедливыми и для сверточных кодов, они будут выведены в последующих разделах, вместе с обсуждением декодирования с «мягким решением» по алгоритму Витерби. Следующие ниже результаты содержат необходимые инструменты для оценки помехоустойчивости двоичных систем кодирования в гауссовом канале.

Рассмотрим двоичную систему передачи сигналов, в которой кодовые символы {0,1} отображаются в действительные числа {+1,-1}, соответственно, как показано на Рисунке 8. В дальнейшем, вектора имеют размерность п и обозначение х = (x₀, x₁, …, x_n-1). Условная функция плотности вероятности (ф.п.в.) последовательности у на выходе канала при условии, что на его входе передавалась последовательность х, равна

(1-32)

где р_п(п) есть ф.п.в. п статистически независимых и одинаково распределенных (i.i.d.) отсчетов шума, каждый из которых имеет Гауссово распределение с нулевым средним и дисперсией, равной N₀/2. Величина N₀ называется односторонней спектральной плотностью мощности шума. Легко показать, что декодирование по максимуму правдоподобия (м.п.) линейного кода в таком канале соответствует выбору последовательности х', минимизирующей квадрат Евклидова расстояния между принятой последовательностью у и х', т.е.

(1.33)

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

Рис. 8. Система двоичной передачи с кодированием по каналу с АБГШ.

Рис. 9. Вероятность ошибки декодирования для жесткого декодирования (Pt(3,l,3)_HDD) и мягкого декодирования (Pe(3,l,3)_SDD) двоичного (3,1,3) кода при передаче двоичных сигналов в канале с АБГШ.

Вероятность ошибки для МП декодирования, Р_е(С), равна вероятности того, что при передаче последовательности х вектор шума оказался таким, что принятая последовательность у = х + n ближе к другой кодовой последовательности х" С, х" ≠ х. Для линейного кода можно предположить, что передается нулевое кодовое слово. Тогда вероятность Р_е(С) может быть ограничена сверху с помощью границы объединения и распределения весов W(C) следующим образом:

(1-34)

где R = k/n скорость кода, Е_ь/N₀ отношение энергии сигнала на бит к мощности шума или (SNR на бит) и Q(x) определено в (1.2).

На Рисунке 9 показаны оценки вероятности ошибки для жесткого декодирования (1.30) и для мягкого декодирования (1.34) для двоичного (3,1,3) кода. Декодирование с жестким решением (или жесткое декодирование) означает, что декодер для ДСК использует выход двоичного демодулятора. Эквивалентный ДСК имеет переходную вероятность равную

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

Показано, что для вероятности ошибки на бит, обозначаемой P_b(C) двоичного систематического кода при передаче двоичных сигналов по каналу с АБГШ, справедлива следующая верхняя граница:

(1.35)

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

Пример 10. Рассмотрим двоичный линейный (6,3,3) код с порождающей и проверочной матрицами

Рис. 10. Моделирование и границы объединения для двоичного (6,3,3) кода при передаче двоичных сигналов в канале с АБГШ.

соответственно. Распределение весов этого кода равно W(C) = {1,0,0,4,3,0,0}, которое может быть проверено непосредственным вычислением для всех кодовых слов v = (u,v_p):

u	vp
000	000
001	101
010	011
011	110
100	110
101	011
110	101
111	000

В этом частном случае, МП декодирование состоит в вычислении квадрата Евклидова расстояния по формуле (1.33) между принятым словом и каждым из восьми возможных кодовых слов. В качестве решения выбирается слово с наименьшим расстоянием. На Рисунке 10 показаны результаты моделирования и границы объединения для жесткого и мягкого декодирования по максимуму правдоподобия для передачи двоичных сигналов в канале с АБГШ.

Модель канала с общими Релеевскими замираниями.

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

Модель канала с покомпонентными мультипликативными искажениями показана на Рисунке 11. Мультипликативные искажения представлены случайным вектором α размерности п, компоненты которого являются независимыми, одинаково распределенными случайными величинами (i.i.d.), имеющими плотность вероятности Релея,

(1.36)

При такой плотности вероятностей множителей среднее значение отношения сигнал-шум (SNR) на бит равно E_b/N₀ (как и для АБГШ без замираний), так как второй момент коэффициентов замирания равен E{a²_i} = 1.

Рис. 11 Передача двоичных кодированных сообщений в канале с гладкими Релеевскими замираниями

Рис. 12. Двоичная передача по Релеевскому каналу. Результаты моделирования (SIM), оценка границы объединения методом Монте-Карло (Р_е(3,1,3)_МС) и граница Чернова (Р_е(3,1,3)_ЕХР) для двоичного (3,1,3) кода.

Оценки эффективности двоичных линейных кодов в канале с общими Релеевскими замираниями находятся из оценок условной вероятности ошибки декодирования, Р_е(С\α), или условной вероятности ошибки на бит, Р_ь(С\α). Безусловные вероятности ошибки находятся интегрированием условных вероятностей с весами α_i, имеющими плотность вероятности (1.36).

Условные вероятности ошибки идентичны безусловным в канале с АБГШ. Существенное различие имеется только в аргументах функции Q(x), которые теперь взвешены на коэффициенты замирания α_i,. Рассматривая передачу двоичных кодированных сообщений при отсутствии (внешней) информации о состоянии канала, находим, что

(1.37)

где

(1.38)

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

(1.39)

Известны несколько методов оценивания выражения (1.39). Один из них состоит в применении метода Монте-Карло численного интегрирования с использованием следующей аппроксимации:

(1.40)

где равно сумме квадратов w независимых одинаково распределенных (i.i.d.) случайных величин с Релеевской плотностью вероятностей (1.38), выданных на -ом обращении к компьютерной программе генерации, и N достаточно большое целое число, зависящее от ожидаемого диапазона значений Р_е(С). Хорошим правилом, которое следует запомнить, является следующее: величина N должна быть, по меньшей мере, в 100 раз больше обратной величины P_e(C).

Другим методом является экспоненциальная аппроксимация сверху функции Q, которая позволяет проинтегрировать выражение или воспользоваться границей Чернова. Этот подход хоть и несколько ухудшает результат, зато дает замкнутое выражение:

(1.41)

Рис. 13. Двоичная передача по Релеевскому каналу. Результаты моделирования (SIM_(6,3,3)),°neHKa границы объединения методом Монте-Карло (Р_е(6,3,3)_МС) и граница Чернова (Р_е(6,3,3)_ЕХР) для двоичного (6,3,3) кода.

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

Пример 11. На Рисунке 12 показаны результаты компьютерного моделирования двоичного (3,1,3) кода в канале с общими Релеевскими замираниями. Заметим, что интегрирование методом Монте-Карло дает точное значение помехоустойчивости кода, так как граница (1.40) содержит только один член. Заметим также, что граница Чернова дает результат, смещенный почти на 2дБ, относительно результата моделирования при отношении сигнал-шум на бит Е_ь/N₀>18 дБ,

Пример 12. На Рисунке 13 показаны результаты компьютерного моделирования двоичного (6,3,3) кода из примера 10 в Релеевском канале. В этом случае граница объединения теряет точность при малых значениях E_b/N₀ из-за присутствия дополнительных членов в формуле (1.40). Как и раньше, граница Чернова проигрывает около 2 дБ в отношении сигнал - шум на бит при E_b/N₀> 18 дБ.

Рис. 14. Общая структура жесткого декодера для линейных блоковых кодов для ДСК.

Вопросы для самоконтроля: