Algorithm for optimal symbol-by-symbol reception of digital signals with reduced implementation complexity

Full Text

Введение

Для обеспечения требуемых информационных скоростей передачи при ограниченной частотной полосе используется класс информационно-емких цифровых сигналов [1–3]. Их основными характеристиками являются частотная эффективность $m$, которая определяется объемом $M=2^m$ соответствующих сигнальных «созвездий», и средняя вероятность ошибки на символ «созвездия» $P_c$ [2]. Частный класс данных сигналов представляется цифровыми сигналами с многофазовой манипуляцией (ФМ–М), интенсивно используемыми в приложениях различного назначения [2].

При увеличении объема «созвездий» (при увеличении параметра $m$) наблюдается деградация помехоустойчивости передачи информации (увеличивается вероятность ошибки $P_c$) при фиксированной энергии сигналов на бит $E_{б}$ [2, 3]. Это обусловливает требование к повышению помехоустойчивости передачи информации по каналам с шумами и с искажениями с использованием этого класса цифровых сигналов [2, 4, 5].

Перспективное направление решения данной проблемы представляет использование сигнальных конструкций на основе рассматриваемого класса сигналов и корректирующего кодирования в недвоичных полях Галуа с размерностью, совпадающей с объемом «созвездий», в сочетании с алгоритмами посимвольного приема [6–9]. При реализации алгоритмов посимвольного приема минимизируется средняя вероятность ошибочного приема $P_c$ в отличие от алгоритмов приема максимального правдоподобия, минимизирующих вероятность ошибки на кодовое слово (на дискретное сообщение).

В работах [8–10] приведено описание разработанного алгоритма оптимального посимвольного приема. Результаты исследований показывают сложность его реализации из-за высокой требуемой разрядности представления чисел при вычислениях [11].

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

1. Постановка задачи

Введем обозначение $\overrightarrow{A}=(a_i;0\le i\le k-1)$ — последовательность $k$ информационных символов как элементов поля Галуа $GF\left(2^m\right)$, формируемого по модулю неприводимого примитивного многочлена $\gamma \left(x\right)$ степени $m$. Элементы поля $a_i$ представляются многочленами $a_i=\sum _{p=0}^{m-1}{\alpha }_p\left(a_i\right)x^p$, ${\alpha }_p\left(a_i\right)\in GF\left(2\right)$ [1, 12]. Соответствующее кодовое слово корректирующего кода в поле $GF\left(2^m\right)$ задается как $\overrightarrow{B}=\overrightarrow{A}\cdot H$; $H$ — порождающая матрица кода с размером $n\times k$; $n$ — длина кодовых слов;  $r=n-k$— параметр избыточности кода (количество проверочных символов); арифметические вычисления исполняются в используемом поле Галуа [12]. Для корректирующих кодов в систематическом виде выполняются условия $b_i=a_i$, $i=\mathrm{0,...,}k-1$.

Символы $b_i$ ($0\le i\le n-1$) кодового слова $\overrightarrow{B}$ сопоставляются цифровым сигналам с «созвездием» объемом $2^m$, передаваемым по каналам передачи.

На вход приемника поступает реализация $\overrightarrow{Y}=({\dot{y}}_l;0\le l\le n-1)$, где  ${\dot{y}}_l$— комплексные отсчеты с выхода демодулятора сигналов. При выполнении оптимального посимвольного приема принимается решение относительно символов ${\widehat{b}}_i$ с использованием правила [10]

${\widehat{b}}_i=\underset{\beta \in GF\left(2^m\right)}{\max }\left(\mathrm{Pr}\right(b_i=\beta \left|\overrightarrow{Y})\right.)$, (1)

 $\mathrm{Pr}(b_i=\beta \left|\overrightarrow{Y})\right.$— апостериорные вероятности передаваемых символов.

В работах [8–10] приведено описание разработанного алгоритма вычисления $\mathrm{Pr}(b_i=\beta \left|\overrightarrow{Y})\right.$, дан анализ его свойств. Значимым ограничением при реализации алгоритма является требование представления чисел высокого порядка при вычислениях, который зависит от ряда параметров: от отношения сигнал/помеха, от длины кодовых слов $n$, от объема «созвездия» используемых сигналов. При моделировании алгоритма ограничивался диапазон значений чисел, что снижало помехоустойчивость алгоритма приема [11].

Цель работы — модификация рассматриваемого алгоритма оптимального посимвольного приема с пониженной сложностью реализации за счет снятия ограничения на диапазон значений чисел при вычислении и исследование помехоустойчивости результирующего алгоритма для ряда информационно-емких цифровых сигналов ФМ–М.

2. Алгоритм оптимального посимвольного приема цифровых сигналов в полях $\mathbf{GF}\mathbf{\left(}{\mathbf{2}}^{\mathbf{m}}\mathbf{\right)}$

Одной из основных характеристик цифровых сигналов $s\left(t\right)$ является коэффициент их частотной эффективности $m={\log }_{2}M$ (бит/с/Гц), определяющий максимальную информационную скорость передачи без корректирующего кодирования $R=m\Delta F$ (бит/с) для канала с частотной полосой $\Delta F$ [2].

Рассматриваемые сигналы $s\left(t\right)$ задаются соотношением [2]

$s\left(t\right)=\sum _{i=0}^{n-1}{A}_{i}U\left(t\right)\cos (2\pi ft+{\varphi }_i)$, (2)

$f$ — центральная частота; $U\left(t\right)=1$ при $iT\le t<(i+1)T$, иначе $U\left(t\right)=0$; $A_i$,  ${\varphi }_i$— амплитуда и фаза радиоимпульсов $s_i\left(t\right)$ в составе $s\left(t\right)$, задающие «созвездия»;  $T$— длительность $s_i\left(t\right)$.

Цифровые сигналы (2) формируются, отображая $m$ двоичных символов ${\alpha }_p\left(b_i\right)$ ($p=\mathrm{0,1,...,}m-1$) в символы комплексных огибающих ${\dot{V}}_i=A_i\exp \left(j{\varphi }_i\right)$ «созвездия» [2]. На рис. 1 приведен пример сигнального «созвездия» цифровых сигналов ФМ-16, даны правила отображения $m$ двоичных символов в символы комплексных огибающих «созвездий».

Выражение для апостериорных вероятностей $\mathrm{Pr}(b_j=\beta \left|\overrightarrow{Y}\right.)$ имеет вид [10]:

$\mathrm{Pr}(b_j=\beta \left|\overrightarrow{Y}\right.)=\sum _{\overrightarrow{B}:b_j=\beta }\mathrm{Pr}(\overrightarrow{B}\left|\overrightarrow{Y})\right.=\sum _{\overrightarrow{B}:b_j=\beta }\frac{\mathrm{Pr}\left(\overrightarrow{B}\right)}{p\left(\overrightarrow{Y}\right)}p(\overrightarrow{Y}\left|\overrightarrow{B})\right.$. (3)

Здесь  $\mathrm{Pr}(\overrightarrow{B}\left|\overrightarrow{Y})\right.$— условная вероятность кодового слова $\overrightarrow{B}$ для реализации $\overrightarrow{Y}$.

Для канала без памяти выполняется условие $p(\overrightarrow{Y}\left|\overrightarrow{B})\right.=\prod _{j=0}^{n-1}p({\dot{y}}_j\left|b_j)\right.$. Сообщения $\overrightarrow{B}$ полагаются равновероятными $Pr\left(\overrightarrow{B}\right)=2^{-mk}$.

Сложность вычисления $\mathrm{Pr}(b_i=\beta \left|\overrightarrow{Y})\right.$ с использованием (3) определяется требуемым объемом вычислительных операций $P_1\approx 2^{mk}$ и даже для малых значений $m,k$ представляет трудоемкую задачу.

В работах [8–10] приведено описание производительного алгоритма вычисления $\mathrm{Pr}(b_i=\beta \left|\overrightarrow{Y})\right.$, не требующего вычисления полного множества $P_1\approx 2^{mk}$ условных вероятностей $\mathrm{Pr}(\overrightarrow{B}\left|\overrightarrow{Y})\right.$. Для пояснения алгоритма приема рассматриваемого класса цифровых сигналов, включающего три шага вычислений [10], ниже дано его описание.

Шаг 1. Вычисляется множество спектральных составляющих $C_l\left(r\right)$ в базисе Уолша-Адамара для последовательностей $p({\dot{y}}_l\left|{\dot{V}}_i)\right.$

$C_l\left(r\right)=\sum _{i={\mathrm{0...2}}^m-1}p\left({\dot{y}}_l\left|{\dot{V}}_i)\right.w_i\right(r)$, $r\in GF\left(2^m\right)$, (4)

где $i={\mathrm{0,1,...,2}}^m-1$; $l=\mathrm{0,1,...,}n-1$ — номера символов в составе кодового слова; $w_i\left(r\right)$ — базисные функции Уолша-Адамара с перемежением номеров $i$.

Шаг 2. Вычисляется множество $T_l\left(\lambda \right)$ с использованием $C_l\left(r\right)$

$T_l\left(\lambda \right)=\frac{{\displaystyle \sum _{r_p:R\in C_H}{C}_l(r_l-\lambda )\prod _{\begin{array}{l}p=0\\ p\ne l\end{array}}^{n-1}{C}_p\left(r_p\right)}}{{\displaystyle \sum _{r_p:R\in C_H}\prod _{p=0}^{n-1}{C}_p\left(r_p\right)}}$. (5)

Здесь  $R$— множество кодовых слов кода $C_H$ с параметрами ($n,n-k$), дуального к используемому корректирующему коду; обозначение $r_p:R\in C_H$ в (5) определяет операции для символов $r_p$ в составе кодового слова $R$  кода ${С}_H$.

Шаг 3. Вычисляются апостериорные вероятности $\mathrm{Pr}(b_l=\beta \left|\overrightarrow{Y})\right.$с использованием спектрального преобразования в базисе Уолша-Адамара размерностью $2^m$ над множеством $T_l\left(\lambda \right)$

$\mathrm{Pr}(b_l=\beta \left|\overrightarrow{Y})\right.=\sum _{\lambda ={\mathrm{0...2}}^m-1}{T}_l\left(\lambda \right)w_{\beta }\left(\lambda \right)$. (6)

Решение относительно символов кодового слова $\overrightarrow{B}$ принимается на основе вычисленных значений $\mathrm{Pr}(b_l=\beta \left|\overrightarrow{Y})\right.$ в соответствии с правилом (1).

Сложность вычисления соотношений (4-6) оценивается как $P_2\cong 2^{m(n-k)}$, для значений $n-k\ll k$ (для корректирующих кодов с низкой избыточностью) выполняется условие $P_2<<P_1$.

3. Анализ сложности реализации алгоритма оптимального посимвольного приема

$p({\dot{y}}_l\left|{\dot{V}}_i)\right.$Ниже приведены результаты сложности реализации алгоритма оптимального посимвольного приема (4-6) для канала с аддитивным белым гауссовским шумом без памяти со спектральной плотностью мощности $N_0$  (АБГШ канал). В этом случае нормированные отсчеты ${\dot{y}}_l$ для $Re{(}_{\text{i}})$, $Im{(}_{\text{i}})$ с выхода демодулятора представляют случайные величины со средними $\sqrt{\frac{2m{E}_i}{N_0}}cos\left({\varphi }_i\right)$, $\sqrt{\frac{2m{E}_i}{N_0}}sin\left({\varphi }_i\right)$ и с единичной дисперсией,  $E_i$— энергии символов «созвездия», удовлетворяющие условию $E_{б}=\frac{1}{M}\sum _{i=0}^{M-1}{E}_i$;  $E_{б}$— средняя энергия на бит; плотности вероятности $p({\dot{y}}_l\left|{\dot{V}}_i)\right.$ при вычислении спектральных составляющих $C_l\left(r\right)$ задаются как [8]

$p({\dot{y}}_l\left|{\dot{V}}_i)\right.=K\exp \left(-{||{\dot{y}}_l-\mu {\dot{V}}_i||}^2/2\right)$, (7)

где  $||x||$— Евклидова метрика;  $K$— коэффициент нормировки; $\mu$ — коэффициент передачи канала.

Для рассматриваемого канала значения ${||{\dot{y}}_l||}^2$ в (7) можно не учитывать подобно правилу приема максимального правдоподобия [2]

$p({\dot{y}}_l\left|{\dot{V}}_i)\right.=K_1\exp \left(\left(\mathrm{Re}\right({\dot{y}}_l\left)A_i\cos \right({\varphi }_i)+\mathrm{Im}({\dot{y}}_l\left)A_i\sin \right({\varphi }_i\left)\right)-{||{\dot{V}}_i||}^2/2\right)$. (8)

Вычисление $T_l\left(\lambda \right)$ (5) с использованием $C_l\left(r\right)$ на основе $p({\dot{y}}_l\left|{\dot{V}}_i)\right.$ требует соответствующей точности представления чисел, критичность точности обусловлена вычислением произведений в соотношении (5). Для форматов чисел float (32 разряда для порядка и мантиссы) или double (64 разряда для порядка и мантиссы) результирующие значения произведений могут превышать или быть меньшими предельных значений ($\approx {10}^{\pm 38}$ для формата float, $\approx {10}^{308}$ для формата double). Это приводит к ограничению диапазона значений (к обнулению результатов вычислений) и к деградации вероятностных характеристик $P_c$ при приеме [11].

Для решения этой проблемы при вычислении $p({\dot{y}}_l\left|{\dot{V}}_i)\right.$ с использованием соотношения (8) в работе [11] приведена и исследована методика ограничения диапазона значений путем нелинейной нормализации в виде ${\left(p({\dot{y}}_l\left|{\dot{V}}_i)\right.\right)}^{1/\alpha }$, где $\alpha$— коэффициент нормализации, значения которого зависят от отношений сигнал/помеха $E_{\text{б}}/N_0$, от типа «сигнального «созвездия», от длины кодовых слов $n$ (при моделировании задавались значения $\alpha =\mathrm{1.5....8.0}$). В этом случае требовался формат представления чисел double.

 

Рис. 1. Вид сигнального «созвездия» ФМ-16.

 

Альтернатива по отношению к данному методу адаптивного ограничения диапазона значений чисел основана на использовании соотношения (7) при вычислении $p({\dot{y}}_l\left|{\dot{V}}_i)\right.$. В этом случае слагаемое ${\dot{y}}_l$ компенсирует требуемое увеличение диапазона значений аргумента в соотношении (8), что дает возможность использования формата экономичного представления чисел float без потери информативности. Этот подход существенно упрощает выполнение рассматриваемого алгоритма приема.

Ниже приведены результаты моделирования алгоритма оптимального посимвольного приема для ряда сигналов ФМ–М с использованием данного метода ограничения диапазона значений чисел.

4. Результаты моделирования

Наиболее простым является алгоритм оптимального посимвольного приема для сигнальных конструкций на основе цифровых сигналов с объемом «созвездий» $2^m$ и корректирующего кода с проверкой на четность в недвоичном поле $GF\left(2^m\right)$ [8, 12–14]. В этом случае кодовые векторы $R$ кода $C_H$ представляют собой последовательность длительностью $k+1$ одинаковых элементов поля, избыточность кода $r=1$ [3, 8].

При моделировании алгоритма оптимального посимвольного приема задавалась передаваемая по каналу АБГШ с известным коэффициентом передачи канала $\mu$ случайная информационная последовательность объемом ≈50 битов, значения $k$ равны соответственно 25, 16 и 12 для рассматриваемых сигнальных «созвездий» ФМ-4, ФМ-8 и ФМ-16 c частотной эффективностью 2, 3 и 4 бит/с/Гц [2]. Анализируемые сигнальные конструкции соответствовали корректирующему коду с проверкой на четность в полях $GF\left(2^2\right)$, $GF\left(2^3\right)$, $GF\left(2^4\right)$, их порождаемые многочлены $\gamma \left(x\right)$ приведены в табл. 1 [12].

 

Таблица 1. Порождающие многочлены $\mathbf{\gamma }\mathbf{\left(}\mathbf{x}\mathbf{\right)}$ для полей $\mathbf{GF}\mathbf{\left(}{\mathbf{2}}^{\mathbf{2}}\mathbf{\right)}$, $\mathbf{GF}\mathbf{\left(}{\mathbf{2}}^{\mathbf{3}}\mathbf{\right)}$, $\mathbf{GF}\mathbf{\left(}{\mathbf{2}}^{\mathbf{4}}\mathbf{\right)}$

Многочлены	$GF\left(2^2\right)$	$GF\left(2^3\right)$	$GF\left(2^4\right)$
$\gamma \left(x\right)$	$x^2+x+1$	$x^3+x+1$	$x^4+x+1$

 

При выполнении моделирования производилась интервальная оценка вероятности $P_{\text{б}}$ путем вычисления параметра $w=x/u$, где  $x$— число ошибочных решений в последовательности испытаний $u$. Требуемое количество экспериментов $u$ определяется размером доверительного интервала, вероятностью $P_{\text{с}}$ и доверительной вероятностью $P_{\text{дов}}$ [15]. Например, для значения $P_{\text{с}}={10}^{-5}$, доверительного интервала [$0.5P_{\text{c}}\mathrm{,1.5}{P}_{\text{c}}$] и $P_{\text{дов}}=0.95$ требуемое количество экспериментов оценивается значением 1500000.

 

Рис. 2. Вероятности ошибки при приеме сигнальной конструкции на основе сигналов ФМ-4: 1 — без кодирования; 2 — с использованием корректирующего кода в поле $\mathbf{GF}\mathbf{\left(}{\mathbf{2}}^{\mathbf{2}}\mathbf{\right)}$.

 

Рис. 3. Вероятности ошибки при приеме сигнальной конструкции на основе сигналов ФМ-8: 1 — без кодирования; 2 — с использованием корректирующего кода в поле $\mathbf{GF}\mathbf{\left(}{\mathbf{2}}^{\mathbf{3}}\mathbf{\right)}$.

 

Рис. 4. Вероятности ошибки при приеме сигнальной конструкции на основе сигналов ФМ-16: 1 — без кодирования; 2 — с использованием корректирующего кода в поле $\mathbf{GF}\mathbf{\left(}{\mathbf{2}}^{\mathbf{4}}\mathbf{\right)}$.

 

На рис. 2-4 приведены вероятностные кривые при приеме сигнальных конструкций на основе «созвездий» ФМ-4, ФМ-8, ФМ-16, кривые 2 соответствуют использованию рассматриваемого корректирующего кода в полях $GF\left(2^2\right)$, $GF\left(2^3\right)$, $GF\left(2^4\right)$ соответственно, кривые 1 — без кодирования. Видно, что для сигнальной конструкции на основе ФМ-4 (рис. 2) вероятность ошибки $P_{\text{с}}={10}^{-5}$ достигается при отношении сигнал/помеха $E_{\text{б}}/N_0$, равном 8.0 дБ с кодированием и 9.5 дБ без кодирования, энергетический выигрыш $\Delta E$ достигает 1.5 дБ. Подобные оценки энергетических выигрышей для сигнальных конструкций $\Delta E$ вычисляются с использованием вероятностных кривых на рис. 3 и рис. 4. В табл. 2 приведены соответствующие значения $E_{\text{б}}/N_0$ и значения энергетических выигрышей $\Delta E$, требуемые для достижения вероятности ошибки $P_{\text{с}}={10}^{-5}$ без корректирующего кодирования и с кодированием.

Из табл. 2 следует, что энергетические выигрыши $\Delta E$ при использовании алгоритма оптимального посимвольного приема анализируемых сигнальных конструкций зависят от типа и объемов $2^m$ сигнальных «созвездий» (от объемов полей Галуа $GF\left(2^m\right)$) — для $P_{\text{с}}={10}^{-5}$ значения $\Delta E$ при использовании рассматриваемой простой схемы кодирования достигают значимых величин 1.5, 2.0, 2.5 дБ.

Таблица 2. Значения сигнал/помеха ${\mathbf{E}}_{\mathbf{\text{б}}}\mathbf{/}{\mathbf{N}}_{\mathbf{0}}$ для достижения ${\mathbf{P}}_{\mathbf{\text{с}}}\mathbf{=}{\mathbf{10}}^{\mathbf{-}\mathbf{5}}$ ( ${\mathbf{E}}_{\mathbf{б}}^{\mathbf{\left(}\mathbf{1}\mathbf{\right)}}\mathbf{/}{\mathbf{N}}_{\mathbf{0}}$— без кодирования;  ${\mathbf{E}}_{\mathbf{б}}^{\mathbf{\left(}\mathbf{2}\mathbf{\right)}}\mathbf{/}{\mathbf{N}}_{\mathbf{0}}$— с кодированием,  $\mathbf{\Delta E}$— энергетический выигрыш)

Энергетические характеристики	ФМ-4	ФМ-8	ФМ-16
$E_{б}^{\left(1\right)}/N_0$, дБ	9.5	13.25	18.0
$E_{б}^{\left(2\right)}/N_0$, дБ	8.0	11.25	15.5
$\Delta E$, дБ	1.5	2.0	2.5

 

Заключение

Дано описание алгоритма оптимального посимвольного приема информационно-емких цифровых сигналов с пониженной сложностью программной реализации. Выполнение алгоритма основано на использовании экономичного представления чисел в формате float, что снимает ограничение на динамический диапазон параметра сигнал/помеха, на длину кодовых слов и на тип сигнальных «созвездий». Приведены результаты исследований помехоустойчивости рассматриваемого модифицированного алгоритма оптимального посимвольного приема сигнальных конструкций на основе цифровых сигналов с многофазовой манипуляцией ФМ-4, ФМ-8, ФМ-16, интенсивно используемых в приложениях, и простого корректирующего кода с проверкой на четность в недвоичных полях Галуа $GF\left(2^m\right)$.

Путем компьютерного моделирования показано, что для вероятности ошибочного приема на символ $P_{\text{с}}={10}^{-5}$ применение модифицированного алгоритма оптимального посимвольного приема обеспечивает значимый энергетический выигрыш до 1.5, 2.0 и 2.5 дБ соответственно для рассматриваемых сигнальных конструкций по отношению к передаче исследуемого ряда цифровых сигналов без кодирования.

Работа выполнена в рамках государственного задания ИРЭ им. В.А. Котельникова РАН.

About the authors

L. E. Nazarov

Fryazino Branch of the Kotelnikov Institute of Radioengineering and Electronics of the Russian Academy of Sciences

Author for correspondence.
Email: levnaz2018@mail.ru

д. ф.-м.н., гл. научный сотрудник

Russian Federation, Moscow

V. V. Batanov

Fryazino Branch of the Kotelnikov Institute of Radioengineering and Electronics of the Russian Academy of Sciences

Email: levnaz2018@mail.ru

вед. инженер

Russian Federation, Moscow

References

Supplementary files