Synchronization of M-sequences based on fast Нadamard transform

Full Text

ВВЕДЕНИЕ

В настоящее время М-последовательности (МП) используются для формирования периодических шумоподобных сложных сигналов (СлС), применяемых в различных наземных и спутниковых радиосистемах [1–10]. На основе обработки таких СлС могут решаться задачи синхронизации по времени и частоте в каналах передачи информации [1, 11–13], позиционирования в системах радионавигации [3–5, 14], суммирования сигналов при их многолучевом распространении или излучении разнесенными ретрансляторами, включая спутниковые [1, 2, 5, 12, 15], выявления всех наземных станций, использующих спутниковую группировку, с целью контроля частотного ресурса [6, 7] и т.д. Во всех вышеперечисленных случаях ключевым этапом обработки СлС является синхронизация МП на основе многократного выполнения операции ее дискретной свертки на длительности времени одного, многих периодов ее повторения, либо ее сегмента значительной длины, порядка 2⁹…2¹⁷ и более [1, 3, 6, 16–18]. Это объясняется как требованиями к разрешающей способности при обнаружении-различении совокупности шумоподобных СлС, рассогласованных по частоте и временной задержке [7, 15], так и, как правило, низким отношением сигнал/помеха на входе приемника, когда помеха может превосходить полезный сигнал по мощности в сотни, тысячи, или десятки тысяч раз [6]. При этом ограничение по длительности времени обработки СлС в настоящее время связано только с высокой вычислительной сложностью алгоритма дискретной свертки соответствующих псевдослучайных последовательностей (ПСП), поскольку проблема нестабильности тактовых генераторов последних решается при повторной дискретизации входного СлС со сдвигом по времени на половину длительности его элементарного импульса [13, 19, 20], а нестабильность его несущей частоты приводит лишь к необходимости многократных повторных вычислений дискретной свертки ПСП [8, 19].

Значительные успехи в области использования быстрых спектральных преобразований в базисе функций Виленкина–Крестенсона и, в частности, Уолша–Адамара, при обработке дискретных сигналов были достигнуты в работах [4, 14, 21–28]. В [21] впервые предложены групповые дискретные мультипликативные сигналы, выявлена их связь с групповыми кодами и показано, что в основе оптимального правила их распознавания лежит спектральный анализ, при реализации которого можно использовать быстрые спектральные преобразования. В работах [22–27] развиты методы использования этих преобразований в теории помехоустойчивого кодирования. Применительно к задаче декодирования p-ичных кодов максимальной длины использование быстрых спектральных преобразований в дискретном базисе функций Виленкина–Крестенсона рассматривалось в работе [28], а непосредственно для синхронизации псевдослучайных кодов, в том числе и МП, в работах [4, 6, 14].

Также в [4] указывается на взаимосвязь задач поиска (синхронизации) СлС при их обработке в приемнике и декодирования блоковых кодов, построенных на основе циклических сдвигов их слов. В данной работе рассматривается задача синхронизации МП, чтобы подчеркнуть взаимосвязь решаемой задачи с синхронизацией периодического СлС при его обработке в приемнике. Под синхронизацией МП понимается определение ее циклического сдвига, начиная с момента начала наблюдения СлС, на основе которой он сформирован. Вопросы, связанные с выделением МП из этого СлС, не рассматриваются.

При быстром декодировании кода на основе быстрых спектральных преобразований необходимо знать способ преобразования его слов к дискретным функциям Виленкина–Крестенсона или, при использовании двоичных кодов, – к функциям Уолша [21]. В случае решения задачи синхронизации кода любой его циклический сдвиг должен преобразовываться к этим функциям [4, 14]. Но в [4, 6, 14, 28] не выявлено многообразие вариантов преобразования циклических сдвигов МП к дискретным функциями Уолша, вызванное как разнообразием мультипликативных групп расширенного поля Галуа, так и использованием их циклических сдвигов при таком приведении. Знание о таком многообразии делает алгоритм синхронизации МП более гибким и позволяет снизить его вычислительную сложность в определенных ситуациях, на которые указывается в данной статье. Кроме того, при решении задачи синхронизации МП с большими периодами повторения важное значение приобретает способ выявления соответствия номеров строк матрицы Уолша–Адамара и начальных блоков циклических сдвигов МП, т.е. в матричной интерпретации данной задачи – строкам матрицы-циркулянта МП, которая может быть построена разными способами, что не рассматривается в этих работах.

Цель данной работы – исследование вариантов построения матриц-циркулянтов МП на основе мультипликативных групп расширенного поля Галуа по модулю неприводимого примитивного полинома, а также вариантов приведения этих матриц к полной или усеченной матрице Адамара для разработки ускоренных алгоритмов синхронизации МП при обработке шумоподобных сложных сигналов.

1. ПОСТРОЕНИЕ МАТРИЦ-ЦИРКУЛЯНТОВ МП НА ОСНОВЕ МУЛЬТИПЛИКАТИВНЫХ ГРУПП ПОЛЯ ГАЛУА

Представим любую МП с элементами (0,1), сформированную на основе неприводимого примитивного полинома f_m (x), в виде вектора-строки

${}_{l_i}{}^n\Im _i=\left[x_{i,k}, k=\mathrm{0,}\dots ,N-1\right],$

где i = 0,...,m–1 – номер циклического сдвига МП на $l_i\in \left\{\mathrm{0,1}\dots ,N-1\right\}$ символов относительно МП  ${}_0{}^n\Im _0$с условно нулевым циклическим сдвигом, N = 2^m–1 – длина (период) МП, m – порядок f_m (x), n – номер выбранного способа упорядочения МП по их циклическим сдвигам [1, 29–32].

Как известно, можно выбрать такой способ упорядочения любых m МП, описанных выше, при котором столбцы

${\mathit{\alpha }}^k={\left[x_{i,k}, i=\mathrm{0,}\dots ,m-1\right]}^T, k=\mathrm{0,}\dots ,N-\mathrm{1,}$

образуют мультипликативную группу расширенного поля Галуа GF(2^m) построенного по модулю f_m (x), где k – номер элемента группы, ${\left[\cdot \right]}^{\mathit{T}}$ – обозначение транспонированной матрицы [21, 29, 30]. Такая группа имеет циклическую структуру и состоит из максимально возможного числа N несовпадающих ненулевых элементов, являющихся степенями первообразного элемента ${\mathbf{\alpha }}^0$ поля, причем ${\mathit{\alpha }}^k={\mathbf{Н}}_n{\mathit{\alpha }}^{k-1}$, где H_n – сопровождающая матрица f_m (x) [30]. Обычно рассматривают четыре типа таких матриц [28]:

$$\begin{gathered} {\mathbf{Н}}_1=\left[\begin{array}{ccccc}0& 0& ...& 0& {а}_0\\ 1& 0& ...& 0& {а}_1\\ .& .& .& .& .\\ 0& 0& ...& 0& {а}_{m-2}\\ 0& 0& ...& 1& a_{m-1}\end{array}\right], \\ {\mathbf{Н}}_2=\left[\begin{array}{ccccc}0& 1& ...& 0& 0\\ 0& 0& ...& 0& 0\\ .& .& .& .& .\\ 0& 0& ...& 0& 1\\ {а}_0& {а}_1& ...& {а}_{m-2}& a_{m-1}\end{array}\right], \\ {\mathbf{Н}}_3=\left[\begin{array}{ccccc}{a}_{m-1}& 1& ...& 0& 0\\ {а}_{m-2}& 0& ...& 0& 0\\ .& .& .& .& .\\ {а}_1& 0& ...& 0& 1\\ {а}_0& 0& ...& 0& 0\end{array}\right], \\ {\mathbf{Н}}_4=\left[\begin{array}{ccccc}{a}_{m-1}& {а}_{m-2}& ...& {а}_1& {а}_0\\ 1& 0& ...& 0& 0\\ .& .& .& .& .\\ 0& 0& ...& 0& 0\\ 0& 0& ...& 1& 0\end{array}\right], \end{gathered}$$ (1)

где $a_0, a_1, \dots , a_{m-2}, a_{m-1}$ – коэффициенты полинома f_m (x), принадлежащие множеству {0, 1}; таким образом, размерность этих матриц будет m × m. Важным является свойство цикличности группы, т.е. α⁰ = α^N, α¹ = α^N+1, ... Кроме того, в качестве α⁰ можно выбрать любой ее элемент. Таким образом, m циклических сдвигов МП на l_i ее символов относительно ${}_0{}^n\Im _0$ с некоторым сдвигом, условно считающимся нулевым (l₀ = 0), можно представить в виде матрицы:

$$\begin{gathered} {\Im }_{m,n}=\left[\begin{array}{c}{}_0{}^n\Im _0\\ {}_{l_i}{}^n\Im _1\\ ...\\ {}_{l_{m-1}}{}^n\Im _{m-1}\end{array}\right]=\left[\begin{array}{cccc}{\mathbf{\alpha }}^0& {\mathbf{\alpha }}^1& ...& {\mathbf{\alpha }}^{N-1}\end{array}\right], \\ {\mathbf{\alpha }}^k={\mathbf{H}}_n{\mathbf{\alpha }}^{k-1}\mathbf{.} \end{gathered}$$ (2)

где столбцы α^k могут быть получены любым из возможных способов, т.е. при выборе матрицы H_n, что определяет значения циклических сдвигов МП l_i (i = 0,...,m–1) относительно МП ${}_0{}^n\Im _0$ при выбранном α⁰. В качестве примера в табл. 1 приведены значения элементов четырех максимальных мультипликативных групп поля Галуа, полученных на основе полинома $f_5\left(x\right)=x^5+x^3+1$ и представленных в десятичной системе счисления. Такое их представление в дальнейшем обозначаем как ${\left[{\mathbf{\alpha }}^k\right]}_{10}$. Был выбран первообразный элемент α⁰ =[1 0 0 0 0]^m, так что во всех случаях ${\left[{\mathbf{\alpha }}^0\right]}_{10}=16.$

Таблица 1. Максимальные мультипликативные группы поля Галуа по модулю полинома f₅ (x) = x⁵+x³+1

Таким образом, например, для матрицы H₁ элементы мультипликативной группы поля Галуа можно вычислить по формуле

${\mathit{\alpha }}^{k+1}=\left[\begin{array}{c}{x}_{0,k+1}\\ x_{1,k+1}\\ ...\\ x_{m-1,k+1}\end{array}\right]=\left[\begin{array}{ccccc}0& 0& ...& 0& {а}_0\\ 1& 0& ...& 0& {а}_1\\ .& .& .& .& .\\ 0& 0& ...& 0& {а}_{m-2}\\ 0& 0& ...& 1& a_{m-1}\end{array}\right]\left[\begin{array}{c}{x}_{0,k}\\ x_{1,k}\\ ...\\ x_{m-2}\\ x_{m-1}\end{array}\right],$ (3)

причем m циклических сдвигов порождаемой МП (т.е. на l₀, l₁,…, l_m−1 символов относительно ${}_0{}^1\Im _0$) располагаются в строках матрицы ${\Im }_{m,1}$ [30], соответствующей H₁:

${\Im }_{m\mathrm{,1}}=\left[\begin{array}{cccc}{x}_{\mathrm{0,0}}& x_{\mathrm{0,1}}& \dots & x_{\mathrm{0,}N-1}\\ x_{\mathrm{1,0}}& x_{\mathrm{1,1}}& \dots & x_{\mathrm{1,}N-1}\\ \cdot & \cdot & \cdot & \cdot \\ x_{m-\mathrm{1,0}}& x_{m-\mathrm{1,1}}& \dots & x_{m-\mathrm{1,}N-1}\end{array}\right].$ (4)

Ее столбцы представляют собой элементы мультипликативной группы поля Галуа по модулю  f_m (x) с коэффициентами $a_0, a_1, \dots , a_{m-2}, a_{m-1}$.

В качестве примера в табл. 2 приводятся элементы матрицы ${\Im }_{5,1}$ для полинома f₅ (x) = x⁵+x⁴+x²+x+1, а в табл. 3 – для двойственного полинома f₅ (x) = x⁵+x⁴+x³+x+1.

Таблица 2. Элементы мультипликативной группы поля Галуа на основе сопровождающей матрицы H₁ полинома f₅ (x) = x⁵+x⁴+x²+x+1

Таблица 3. Элементы мультипликативной группы поля Галуа на основе сопровождающей матрицы H₁ полинома f₅ (x) = x⁵+x⁴+x³+x+1

Матрицу-циркулянт МП ${\Im }_{m,n,ц}$ с элементами (0,1), содержащую ее циклические сдвиги на l₀, l₁,…, l_m−1 символов, а также все остальные сдвиги, не совпадающие с ними, сформируем в соответствии с правилом

${\mathit{\Im }}_{m,n,ц}=\left[\begin{array}{c}{\mathit{\Im }}_{m,n}\\ {{\mathbf{H}}_{\mathrm{n}}}^{\mathit{m}}{\mathfrak{I}}_{\mathrm{m},\mathrm{n}}\\ {{\mathbf{H}}_{\mathrm{n}}}^{2m}{\mathfrak{I}}_{\mathit{m}\mathit{,}\mathit{n}}\\ ...\\ {{\mathbf{H}}_n}^{C\mathit{\left(}\mathit{N}\mathit{\right)}m}{\mathfrak{I}}_{\mathit{m}\mathit{,}\mathit{n}}\end{array}\right],$ (5)

где $C\left(N\right)=\left(\frac{A\left(N\right)}{m}\right)-1$, A(N) – число, максимально близкое к N, делящееся нацело на m и удовлетворяющее неравенству A(N)>N. Таким образом, $\frac{A\left(N\right)}{m}$ – это общее число блоков в матрице ${\Im }_{m,n,ц}$, содержащих матрицу ${\Im }_{m,n}$или ее преобразование вида ${{\mathbf{H}}_{\mathrm{n}}}^x{\mathfrak{I}}_{\mathrm{m},\mathrm{n}}$. Размерность каждого блока составит m × (N–1). Таким образом, размерность матрицы ${\Im }_{m,n,ц}$ будет A(N)×(N–1), в результате чего последний блок ${\Im }_{m,n,ц}$ в своих A(N)–N строках будет содержать МП, циклические сдвиги которых совпадают со сдвигами МП первого блока.

В качестве примера элементы ${\Im }_{5,1,ц}$, сформированной на основе f₅ (x) = x⁵+x³+1 и H₁, приведены в табл. 4. Из анализа данных табл. 4 следует, что последовательность l₀, l₁,…, l34, расположенная в последнем столбце, выглядит случайной, хотя второй блок ${\Im }_{5,1,ц}$ из m=5 ее строк сдвинут относительно первого блока из такого же количества строк на пять символов МП, третий блок сдвинут относительно него на десять символов и т.д. Кроме того, столбцы ${\Im }_{5,1,ц}$ не являются МП.

Таблица 4. Матрица ${\mathit{\Im }}_{\mathbf{5}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{ц}}$, сформированная на основе f₅ (x) = x⁵+x³+1

Совершенно другую структуру имеет ${\Im }_{5,2,ц}$, сформированная на основе того же полинома  f₅ (x) = x⁵+x³+1 и H₂ и приведенная в табл. 5, поскольку в ее строках располагаются циклические сдвиги МП, смещенные вправо на один символ друг относительно друга. Кроме того, в ее столбцах содержатся циклические сдвиги той же МП, причем в каждом последующем столбце МП сдвинута циклически на один символ, по сравнению с предыдущим столбцом. Очевидно, что данное свойство характерно для всех ${\Im }_{m,2,ц}$, построенных на основе H₂ и оно не свойственно${\Im }_{m,1,ц}, {\Im }_{m,3,ц}, {\Im }_{m,4,ц}$, сформированным на основе H₁, H_{3 и} H₄ соответственно. Будем называть все матрицы-циркулянты H₂, упорядоченными по циклическим сдвигам или просто упорядоченными.

Таблица 5. Матрица ${\mathit{\Im }}_{\mathbf{5}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{ц}}$, сформированная на основе f₅ (x) = x⁵+x³+1