MATHEMATICAL FORMALIZATION OF ALGORITHM FOR DEMODULATION BY RULE OF MAXIMUM OF A POSTERIOR PROBABILITY THAT MINIMIZES PROBABILITY OF ERROR PER DIGIT

Full Text

Введение Алгоритм Витерби (АВ), рассмотренный в [1-2], минимизирует вероятность ошибки на блок информационных символов, в котором производится поиск кратчайшей траектории на решетке дискретных альтернатив. Алгоритм Кловского-Николаева (АКН) минимизирует вероятность ошибки на бит при минимально возможной задержке принятия решения. Оба алгоритма работают с текущим потоком данных и в рамках своих возможностей непосредственно выдают решения или группу решений. АКН выдает решения на каждом тактовом интервале. При этом, задержка принятия решения постоянна и равна максимально возможной величине памяти канала. АВ в условиях оптимальной работы решение выдает по мере того, как происходит схождение траекторий по решетке Витерби. Это означает, что задержка в принятии решения может быть произвольной величиной, но также, как и у АКН, не меньше величины, соответствующей памяти канала. В [1] приведена формула, по которой можно определять задержку принятия решения для АВ. Фиксация задержки принятия решения в АВ позволяет получить субоптимальный алгоритм, который удобен в практической реализации. Алгоритм максимума апостериорной вероятности (МАВ), в отличие от рассмотренных выше, работает с блоком информационных символов, который должен быть окружен (в начале и конце) известными информационными символами. При описании алгоритма МАВ [3] такими символами обычно являются «нулевые» из двоичного алфавита. В данной статье МАВ рассмотрен для любой возможной позиционности символов, а также для ситуаций, когда анализируемый блок окружают как известные символы, так и неизвестные символы соседних блоков. Такая задача рассматривается в рамках блочного моделирования радиотехнических устройств [3], позволяя универсально использовать алгоритм МАВ, например, в задачах демодуляции сигналов. Постановка задачи Для анализа алгоритма применим теорию дискретного марковского процесса. Пусть процесс протекает в дискретном времени с постоянным шагом. Для моделирования канала с памятью воспользуемся сдвигающим регистром с длиной (первая ячейка регистра содержит текущий информационный символ), на вход которого поступают информационные символы блока некоторой детерминированной функции , (1) и на выходе функции добавим идеальный канал без памяти с белым гауссовским шумом (рис. 1). В условиях МСИ параметр Q обозначает относительную память канала [1; 4]. Значения элементов входной последовательности . выбираются независимо согласно некоторому распределению вероятностей, и каждый элемент может принимать одно из m значений на входе модулятора. Рис. 1. Упрощенная модель канала с памятью в дискретном времени на основе регистра сдвига При этом обязательно выполняется равенство . На выходе блока детерминированной функции (1) каждый элемент последовательности определяется новым входным значением , поступившим во входную ячейку сдвигающего регистра, и значениями в других ячейках сдвигового регистра , которые были перезаписаны туда после операции сдвига. Каждый элемент наблюдаемой последовательности на выходе канала , где - отсчёты белого гауссовского шума. Таким образом, рассматривается m-ичный марковский процесс v-го порядка. Для предложенной модели со сдвиговым регистром введены [2] определения состояния и перехода . Состояния образуют пространство X. Число состояний в этом пространстве . Переходы образуют множество с числом элементов . Для модели, показанной на рис. 1, введено [1] определение комбинации . Комбинация полностью определяет переход. Будем считать, что дискретное время k может принимать как положительные, так и отрицательные значения. В интервале производится передача блока информационных символов . Вне этого интервала могут передаваться как известные, так и неизвестные символы. Известные символы могут быть произвольными из используемого алфавита размером m и принимать значения от 0 до . Кроме того, алфавит дополнен ещё одним символом с номером m. Это дополнение означает, что каждая ячейка регистра сдвига характеризуется состоянием. Символ с номером m означает начальное «пустое» состояние, соответствующее «физическому нулю» для сигнала. Неизвестные символы могут быть информационными и принадлежать другому информационному блоку. Неизвестные символы, находящиеся вне диапазона , не входят в задачу определения их информационного содержания. Число элементов последовательности составит , то есть . Таким образом, постановка задачи заключается в следующем: имеется последовательность наблюдений дискретного по времени марковского процесса с конечным числом состояний (или комбинаций , Q - память канала; m - позиционность символов ), наблюдаемого на выходе идеального канала с белым гауссовским шумом. В каждый k-ый момент времени требуется найти наиболее вероятный элемент входной последовательности , для которого апостериорная вероятность максимальна, что соответствует критерию МАВ. Описание алгоритма Символ представлен как переменная, принимающая значения . Тогда и условную плотность вероятности (ПВ) для каждого символа можно представить как . В сдвигающем регистре (см. рис. 1) входные символы заходят слева направо. Мысленно развернем регистр так, чтобы данные в него заходили справа налево. Тогда состояния в момент времени k обозначим как , где - порядковый номер состояния, совпадающий с числом в m-ичной системе счисления, образованным содержимым в таком сдвигающем регистре при условии, что рассматриваются только Q последних ячеек. При решении поставленной задачи для заданной последовательности наблюдений любому символу ставят в соответствие величину (метрику), пропорциональную , где - совместная вероятность того, что символ примет заданное значение, а сигнал , как точка в многомерном пространстве сигналов, попадёт внутрь некоторого элементарного объёма , часто обозначаемого [4-5] как . Учитывая, что , то поиск максимума соответствует поиску максимума , что дает в итоге решение поставленной задачи максимизации для поиска наиболее вероятного символа . Здесь - многомерная ПВ распределения последовательности сигналов, объединённых в вектор . Используя байесовский подход, можно перейти к другим вероятностям . Здесь - ПВ распределения при условии передачи символа , - апостериорная вероятность передачи символа . Отсюда , и максимум апостериорной вероятности соответствует максимуму произведения . Наиболее вероятный символ следует искать исходя из введенных понятий состояния и перехода. Переход из состояния в связывает два момента времени k и и предполагает появление во входной ячейке сдвигового регистра символа . Совокупность состояния (или последовательности символов) и символа образует комбинацию в сдвиговом регистре, из которой формируется сигнал , и, в конечном итоге, сигнал на выходе канала . Аналогично, совокупность состояния и символа образует комбинацию , что в итоге формирует сигнал . Однако в комбинацию входит последовательность . Обозначим ее как . Таким образом, последовательность имеет место при формировании сигналов и , и содержит передаваемый искомый символ . В этом случае можно ввести пятимерную (при рассмотрении квадратурных компонент сигнала) совместную ПВ , которую можно связать с пятимерной ПВ как . (2) При этом ПВ можно представить состоящей из ПВ и . Рассмотрим вопрос о факторизации ПВ , то есть представления ее через произведение этих двух ПВ. В формировании сигнала участвует комбинация . СПВ распределения сигнала и наличия в сдвиговом регистре последовательности . (3) В формировании сигнала участвует комбинация . Совместная ПВ распределения сигнала и наличия в сдвиговом регистре той же самой последовательности . (4) В выражении (3) ПВ соответствует произведению ПВ распределения сигнала при условии передачи символа и нахождении системы со сдвиговым регистром в состоянии , на вероятность передачи этого символа и на вероятность нахождения этой системы в состоянии . . (5) Аналогично в выражении (4) для ПВ имеет место (6) Вероятность нахождения системы в соответствующем состоянии будет определяться соответствующей нормировкой ПВ, чтобы выполнялось условие : ; (7) . (8) Выражение (7) показывает, что в (3) определяется в итоге через , а выражение (8) показывает, что в (4) определяется через . Это означает, что будет определяться по цепочке очередными предыдущими во времени выражениями, а - выражениями, которые следуют по времени позже. Обозначим все зависимости, уходящие в прошлое, значком , а уходящие в будущее - . В силу независимости отсчетов шума и с учетом новых обозначений можно записать , (9) что соответствует предположению о факторизации ПВ . Параметры и в (9) соответствуют функциям вероятности, обозначенным также в [3]. Подставляя (3)-(6) в (9), получим (10) В выражении (10) каждое слагаемое суммы содержит состояние . Это состояние в своей последовательности содержит всегда один и тот же искомый символ . То есть каждое слагаемое умножается на одну и ту же вероятность . Вынесем эту вероятность за знак суммы. (11) Тогда с учетом (2) (12) В выражении (12) вероятность вычисляется по цепочке, уходя в прошлое до момента времени . В момент времени определяются вероятности начальных состояний до начала блока элементов последовательности . Вероятность также вычисляется по цепочке, уходя в будущее до момента времени . В момент времени также будут определены вероятности начальных состояний после этого блока. Формула ПВ (12) будет определять достаточную статистику для использования ее в решении задачи максимизации произведения . Из (12) можно заметить, что множитель справа от как раз и представляет собой ПВ , где в сумме имеются составляющие, рекуррентно связанные между собой на всём протяжении блока элементов последовательности . Найдем все эти рекуррентные зависимости с учетом того, что комбинации и состояния образуют числа в m-ичной системе счисления: (13) (14) (15) (16) (17) (18) Произведение согласно (9) примет вид (19) Определим слагаемые в сумме (2). Количество состояний , содержащих конкретное значение символа , в m раз меньше общего количества состояний в этот момент времени, и равно , тогда (20) ПВ может быть использована в определении как «жесткого» решения (21) так и «мягкого» решения, которое используется при декодировании помехоустойчивых кодов. Такое «мягкое» решение может быть определено как вероятность (22) На рис. 2 схематически показаны две соседние комбинации и а также состояние, которое содержит последовательность символов, входящую в обе комбинации . В этой последовательности имеется символ в пользу которого будет принято решение. Рис. 2. Принятие решения в пользу символа на фоне комбинаций и состояния Рассмотрим функции ПВ и , приведённые в выражениях (5) и (6). Обе функции эквивалентны. К ожидаемому сигналу , полученному некоторой комбинацией символов в сдвиговом регистре размером элементов (рис. 1), добавляется вектор шума, и на входе приёмника фиксируется отсчет сигнала . При условии, что шум является белым гауссовским, ПВ распределения сигнала равна [6]: (23) Здесь - дисперсия белого гауссовского шума, - ожидаемый сигнал, который получается как сумма отдельных i-ых составляющих среза (см. рис. 3) импульсных характеристик канала, умноженных комплексно на значение сигнала . Каждое такое умножение соответствует символу , находящемуся в сдвиговом регистре, а вся последовательность символов, ограниченная данной суммой, будет представлять комбинацию . Рис. 3. Срез импульсных характеристик При компьютерном моделировании важно правильно учитывать отношение «сигнал-шум» , которое обозначается как [7]. Можно расписать его через мощность сигнала и шума , здесь - энергия ненулевого сигнала, соответствующего информационному элементу; - спектральная плотность мощности шума; T - величина тактового интервала, в течение которого передается сигнал, соответствующий информационному элементу - частота дискретизации; а F - шумовая полоса частот, обычно совпадающая с верхней частотой сигнала. В [7] исследовано, как рассчитывать дисперсию шума для различных вариантов отношения сигнал-шум и разных вариантах многолучевости в канале связи при компьютерном моделировании. Переходя к отсчетам сигнала и шума, можно записать ; , где R - число рабочих отсчётов сигнала на интервале T. При моделировании удобно нормировать мощность сигнала на передаче , для расчета параметра , или на приёме для расчета параметра . Кроме того, можно не учитывать множитель , а при вычислениях использовать логарифмы от ПВ и вероятностей. При решении задачи уменьшения вычислительной сложности нормирование согласно (15) и (18) может быть проигнорировано, и вместо вероятностей могут использоваться соответствующие ПВ. При рекуррентных вычислениях оба направления, согласно обозначениям и , рассматриваются независимо друг от друга. Но в обоих случаях выражение вычисляется одинаково. Поэтому, прежде чем приступать к рекуррентным вычислениям, можно сформировать двумерный массив данных, соответствующий значениям выражения для всех вариантов и , и для всех . Выражения (3)-(8) показывают зависимость совместных ПВ и вероятности нахождения системы в соответствующем состоянии, с одной стороны, от предшествующих элементов, и с другой стороны - от последующих. При передаче двоичных символов для памяти взаимосвязи между рассмотренными функциями ПВ и вероятностями показаны на рис. 4. Если в передаваемом сообщении информационный блок окружен известными символами, то можно определить так называемые стартовые моменты времени. Это означает, что в сдвиговом регистре могут находиться известные информационные символы. Стартовый момент времени необходим для установки начальных значений в приведtнных зависимостях. Самый ранний стартовый момент времени . Поздний стартовый момент времени для обратного направления зависит от памяти канала и равен . В [3] момент времени обозначен как . Начальные значения и , , определяются исходя из содержимого сдвигового регистра в указанные моменты времени. Если в сдвиговом регистре все символы известны, то вероятность состояния с номером, который образуют символы в сдвиговом регистре, равна единице. Вероятность других состояний равна нулю. Если некоторые символы все-таки неизвестны, то стартовые вероятности состояний (24) Здесь Выводы Математическое описание алгоритмов как в [1], так и в данной статье создает единую основу и возможность описания их уникальных реализаций для дальнейшего синтеза и анализа, а также дополняет материал к общему взгляду на рассмотренные алгоритмы АВ и АКН. Любая граничная группа символов до начала информационного блока и после него позволяет однозначно реализовывать данный способ демодуляции. Единая запись для демодуляции m-позиционного сигнала позволяет анализировать произвольные линейные виды модуляций, в том числе и с основанием . Приведенное математическое описание алгоритмов позволяет быстро и эффективно переходить к их программированию на любой платформе. Рис. 4. Взаимосвязи между функциями ПВ и вероятностями при ;

About the authors

Yuri Vitalevich Alyshev

Povolzhskiy State University of Telecommunications and Informatics

Email: alise-17@mail.ru

References

Supplementary files