5.8. Изменяющиеся во времени сверточные коды в каналах с межсимвольной интерференцией

Завершим эту главу описанием применения методов анализа средней по ансамблю вероятности ошибки к изучению класса изменяющихся во времени сверточных кодов в каналах с межсимвольной интерференцией (КМСИ), описанных и анализировавшихся в § 4.9 и 4.10. На рис. 5.7 приведены для иллюстрации аналоговая модель и ее цифровой эквивалент канала с межсимвольной интерференцией, аналогичные тем, что изображены на рис. 4.20 и 4.21, но с предшествующим каналу сверточным кодером со скоростью В § 4.10 было показано, что комбинированный демодулятор — декодер максимального правдоподобия — может быть реализован на базе алгоритма Витерби размерности решетчатая диаграмма для которого получается объединением сверточного кодера и линейного фильтра КМСИ в одно устройство. В этом параграфе всегда будем предполагать, что используется такой демодулятор-декодер максимального правдоподобия.

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

Пусть совокупность символов канала или —1) для правильного пути и совокупность символов канала для пути, который ответвляется от правильного пути и вновь сливается с ним впервые за сегментом из символов канала. Здесь

Рис. 5.7. Модели МСИ канала с кодированием: а аналоговая; б - цифровой эквивалент

Полагая из (4.9.18) получаем

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

или, что то же самое,

Усреднение по этому ансамблю дает

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

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

Рис. 5.8 Генератор метрики ребер диаграммы состояний ошибок (среднее по ансамблю)

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

Воспользовавшись линейностью сверточного кода, можно найти вектор

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

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

только по ансамблю кодов, но и по информационным последовательностям и. Так как может быть любой двоичной последовательностью, не зависящей от и, то последовательность х оказывается не зависящей от последовательности даже если два показанных на рисунке генератора идентичны. Каждая компонента х с равной вероятностью может быть равна +1 и —1. Следовательно, каждая компонента последовательности ошибок принимает значения 0, +1 и —1 с вероятностями 1/2, 1/4 и 1/4 соответственно, что подтверждает правильность выбора весов в (5.8.4).

Та часть рис. 5.8, на которой представлен генератор метрик ребер, аналогична соответствующим частям рис. 4.22 в и 4.23 в, если не считать того, что на рис. 5.8 взвешивание осуществляется с дополнительным множителем 1/2, отражающим усреднение по ансамблю кодов. Ниже представим в матричных обозначениях рассматривавшуюся в § 5.1 границу вероятности ошибки на бит при сверточном кодировании, модифицировав ее для канала с межсимвольной интерференцией.

Определим последовательность состояний как содержимое (Последних разрядов генератора метрики ребер

и матрицу размера

и соотношение сдвига

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

При этом (5.8.6) можно записать в виде

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

а величины указаны на рис. 5.9 a, который представляет собой диаграмму состояний в рассматриваемом случае. Заметим, что в границе (5.8.13) представлено множество всех путей длины начинающихся в начальном состоянии, Они могут заканчиваться в любом состоянии, но так как поглощение кодового пути гарантирует только то, что то вектор состояний хранящийся в регистре, изображенном на рис. 5.8, может быть произвольным. Это объясняет также тот факт, что первым множителем в правой части (5.8.13) является вектор .

Рис. 5.9. Диаграмма состояний ошибок (средняя по ансамблю) для КМСИ с кодированием и а — диаграмма состояний; б - упрощенная диаграмма состояний;

В силу симметрии множество всех путей, заканчивающихся в состоянии —1, совпадает с множеством путей, заканчивающихся в состоянии 1. Следовательно, при (см. задачу 5.11 для

Соответствующая упрощенная диаграмма состояний приведена на рис. 5.96. В общем случае при длине памяти матрица А размера соответствует диаграмме состояний, ненулевых состояний которой могут быть разбиты на пары состояний, имеющих одно и то же множество путей на диаграмме, которые приводят в данное состояние из нулевого за N переходов. Следовательно, всегда можно построить упрощенную диаграмму состояний и соответствующую ей квадратную матрицу А порядка такую, что (5.8.13) может быть представлено в виде

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

Напомним, что (5.8.13) — это усредненная по ансамблю сверточных кодов граница вероятности того, что путь, ответвляющийся от правильного пути и вновь сливающийся с ним через N символов канала (на решетке сверточного кода), приводит к ошибочному событию. Если сегмент, на котором эти два пути не совпадают, имеет длину ребер, то При этом усредненная по ансамблю кодов вероятность двоичной ошибки, обусловленной этим ошибочным событием, ограничена сверху неравенством (см. § 5.1)

где Подставляя (5.8.13) в (5.8.15), видим, что

Матрица А является неотрицательной и неразложимой. Теорема Перрона—Фробениуса например, Гантмахер (1959]) утверждает, что такая матрица имеет вещественное максимальное собственное число и соответствующий ему левый собственный вектор с положительными компонентами. Определяя как отношение наибольшей компоненты левого собственного вектора к его наименьшей компоненте, получаем следующие неравенства (см. задачу 5.12):

Используя их, можно привести (5.8.16) к виду

До сих пор рассматривались лишь ошибочные события, порождаемые путями, которые на решетке сверточного кода ответвляются от правильного пути и вновь сливаются с ним только один раз на сегменте, соответствующем сегменту несовпадения общей решетки кода и КМСИ. Вновь рассмотрим переданную кодовую последовательность соответствующую ошибочному событию и удовлетворяющую условию (5.8.1), но уже в предположении, что на решетке сверточного кода соответствующие им «пути сливаются с правильный дважды, т. е. что в точке они сливаются, а в точке вновь расходятся, где

Это означает, что кодовые пути разветвляются вторично до того, как регистр последовательности в, приведенный на рис. 5.8, успевает очиститься, что возможно лишь при условии Таким образом, в дополнение к (5.8.1), имеем

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

Рис. 5.10. Типичный путь, дважды сливающийся с кодовым путем на решетке КМСИ с кодированием

Для ансамбля меняющихся во времени сверточных кодов с мультипликативной мерой, задаваемой формулой (5.8.3), последовательность в имеет меру

При таких последовательностях ошибок неравенство (5.8.2) принимает вид

и после усреднения по ансамблю переходит в следующее:

где означает -мерный вектор-столбец с символами 1 на позициях, соответствующих состоянию и символами 0 на остальных позициях. Неравенство, аналогичное (5.8.17), применимо и здесь (см. задачу 5.12). Оно приводит к границе

Эта граница устраняет зависимость от состояния и позволяет разделить два сегмента решетки кода, приводящих к единственному ошибочному событию на общей решетке кода и КМСИ. Она позволяет воспользоваться формулами (5.8.13), (5.8.17) и (5.8.25) для дальнейшей оценки сверху правой части (5.8.24). В результате получаем

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

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

Границы вероятностей ошибочных событий с двойным слиянием кодовых, путей легко обобщаются на ошибочные события, приводящие к I слияниям путей на решетке сверточного кода на одном сегменте несовпадения общей решетки кода и КМСИ. Для любого целого I соответствующая усредненная по ансамблю кодов граница вероятности двоичных ошибок, обусловленных такими ошибочными исходами, имеет вид

Просуммировав границы по всем ошибочным событиям, получим следующую границу для средней по ансамблю вероятности ошибки на бит:

Таким образом, доказана следующая теорема.

Теорема 5.8.1. Для КМСИ с аддитивным гауссовским шумом и ненулевыми коэффициентами существует меняющийся во времени сверточный код с длиной кодового ограничения К и скоростью для которого вероятность ошибки на бит при демодуляции декодировании по максимуму правдоподобия ограничена неравенством

X — максимальное собственное число матрицы переходов А канала с межсимвольной интерференцией, отношение наибольшей компоненты положительного левого собственного вектора, соответствующего этому К, к его наименьшей компоненте ?.

Максимальное собственное число X и отношение компонент его собственного вектора а одинаковы как для матрицы переходов А, так и для матрицы переходов А упрощенной диаграммы состояний (см. задачу 5.12). Для спаренной двоичной МСИ, для которой максимальное собственное число

отношение где

На рис. 5.11 приведены графики как функции для этого специального случая, а также для АБГШ канала без межсимвольной интерференции (когда для которого единственным ненулевым собственным числом является число Интересно отметить, что кодирование со скоростью 1/2 в сочетании со спаренной двоичной цифровой линейной фильтрацией приводит к тому, что спектр сигнала не изменяется; при этом ухудшение характеристик при скорости 1/2, как следует из рис. 5.11 и (5.8.32), меньше Конечно, в данном случае уже используются три, а не два уровня сигнала.

Рис. 5.11. Максимальное собственное число для спаренной двоичной МСИ