Коды уолша. Функции Уолша. Основные определения. Способы упорядочения функций Уолша. Адрессация базовых станций

Сжатие навигационых таблиц в базисе Уолша C.B. Пашенцев

Судоводительский факультет МГТУ, кафедра судовождения

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

Abstract. A possibility of the using of the Wolsh-Paly functional base for the linear and rectangular tables compression has been considered in the work. All the formulas, necessary for it, are given and the actual effect of information compression has been shown on some examples. The method can be used both for preliminary compression of information, and by its processing in a real time scale.

1. Введение

В многих автоматических и автоматизированных устройствах, связанных с судовождением, используются табличные данные, занесенные в память решающих устройств и выбираемые из нее по мере надобности. При этом расходуется важнейший ресурс - память, а выборка из нее потребляет и еще более важный ресурс - время, влияя на быстродействие всей системы обработки информации. Поэтому важны любые методы, позволяющие уменьшать объем хранения. Одним из таких методов может быть метод сжатия табличной информации за счет ее спектрального разложения в некотором функциональном базисе. В момент потребления значение функции восстанавливается обратным преобразованием. По сравнению с разложением Фурье, более выгодным является использование для разложения базиса Уолша, так как для гладких функций коэффициенты разложения Уолша быстрее стремятся к нулю. Это допускает большую степень сжатия информации в базисе Уолша. Кроме того, при восстановлении табличных значений в базисе Уолша требуется меньшее время. Связано это с более простым вычислением функций Уолша сравнительно с вычислениями тригонометрических функций. Ести же эти функции генерируются аппаратно, то выгода от применения функций Уолша еще больше, так как их возможные значения +1 и -1 легко реализуются вычислительными устройствами. В работе на численных примерах показаны преимущества применения базиса Уолша для некоторых типов гладких функций и табличных данных. Вычислительный процесс строится на программах быстрых преобразований Фурье и Уолша, написанных автором, и сравнении получаемых спектров.

2. Теоретические основания сжатия

Общие теоретические положения, на основании которых производится преобразование в выбранном функциональном базисе, хорошо известны (Голд, Райдер, 1993; Трахтман А., Трахтман В., 1978). Следует выделить дискретные преобразования при конечности исходного числового ряда. Поскольку речь идет о сжатии таблиц, т.е. о принципиально конечном ряде чисел, то далее будем говорить только о дискретных преобразованиях. Если задан ряд из N чисел

X2, Xk, , XN (1)

то и функциональный базис следует выбрать из конечного набора N функций

Фа(Х), а= 1, 2,„., N, (2)

существующих на совокупности точек Xk. Тогда дискретное преобразование в этом базисе даст ровно N коэффициентов Ca, Koropbie находятся с помощью формального суммирования:

C„ = ЪкХк Фа(Хк), а= 1, 2,„„ N. (3)

Совокупность N коэффициентов Ca и составляет дискретное представление ряда чисел (1) в

функциональном базисе (2). Часто эту совокупность чисел Ca называют линейчатым спектром в выбранном базисе. Другой интерпретацией разложения (3) является рассмотрение его как линейного преобразования исходной системы координат Хк. Коэффициенты Ca становятся тогда координатами в новой координатной системе 0JX). Если спектр (набор коэффициентов Ca) известен, то породивший его ряд чисел можно восстановить с точностью до погрешностей вычислений с помощью обратного дискретного преобразования

Xk = (1/N) T.aCa0JXk), k = 1, 2,..., N. (4)

Для справедливости простых и почти симметричных преобразований (3) и (4) необходимо, чтобы набор функций базиса обладал свойствами ортогональности и определенной нормировки. Условие ортогональности выглядит как совокупность равенств

Zk Фр(Хк) Ф(Хк) = 0, р Ф q, (5)

а условия нормировки - как совокупность равенств

Zk ФрХк) Фр(Хк) = Ек Фр\Хк) = 1. (6)

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

Очевидно, что при такой постановке вопроса никакого сжатия не происходит, так как количество членов исходного ряда и количество спектральных коэффициентов одинаково. Возможность сжатия информации появляется, если число коэффициентов спектра можно сделать меньше числа N. Например, когда часть коэффициентов спектра равна нулю или близка к нему. Тогда этими коэффициентами можно пренебречь, и полученный спектр окажется короче. В первом случае, когда мы пренебрегаем только нулевыми коэффициентами спектра, исходный ряд чисел будет восстановлен с точностью до погрешностей вычислений. Если же мы пренебрежем коэффициентами спектра, в указанной степени близкими к нулю, то восстановленные значения исходного ряда будут включать в себя не только погрешности вычислений, но и погрешности от неточного представления спектра. Чем большую погрешность восстановления членов исходного ряда мы flonyœaeM, TeM большим числом коэффициентов спектра можно пренебречь.

Если обозначить через n число коэффициентов спектра, которыми мы пренебрегли, то отношение в процентах

sq = (n / N) -100 % (7)

можно назвать степенью сжатия исходной информации. Ведь в этом случае мы представляем ее N-n коэффициентами спектра вместо N значений исходного ряда. При sq = 0 сжатие вообще не происходит, а при sq = 100 % оно достигает предельной гипотетической величины. Реальные случаи лежат в пределах от 0 % до 100 %.

Практическая сторона реализации этой идеи несколько сложнее. Если нулевыми или малыми в указанной степени являются конечные (финальные) спектральные коэффициенты, то не составляет труда отбросить n из них и тем самым добиться сжатия sq.

Если же среди коэффициентов спектра имеются нулевые или близкие к нулю в заданной степени, но они не являются финальными, то возникает сложность в представлении такого спектра с позиций сжатия информации. В этом случае надо либо приводить все коэффициенты спектра, включая нулевые и близкие к ним, и тогда сжатия не происходит. Либо задавать группы нулевых спектральных коэффициентов номером начального элемента в группе и количеством элементов группы. Это, естественно, уменьшает степень сжатия исходного ряда чисел. Если нулевые элементы спектра не являются финальными или не составляют группы, а их номера не обнаруживают простой закономерности, то сжатие информации этим путем не достигается.

Итак, возможность сжатия информации и степень ее сжатия зависят как от самого ряда чисел (1), так и от набора функций (2), составляющих базис спектрального разложения Ca. Поскольку ряд чисел Хк нам задан, то управлять степенью сжатия мы можем, изменяя базис спектрального разложения. Но при выбранном базисе Ф(х) характер заданной информации будет сказываться как на самой

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

sin(2nax) и со s(2n«x), (7)

или соответствующий экспоненциальный базис в комплексной форме:

exp(-j 2nax). (8)

В этом случае спектр коэффициентов Ca является спектром в его обычном физическом смысле как совокупности амплитуд некоторого набора частот ограниченного диапазона и определенного частотного разрешения. Поскольку в этом случае базис уже выбран, то возможности сжатия теперь связаны только с характером исходной информации. Если она адекватна по характеру выбранному базису (8), т.е. состоит из линейной комбинации конечного числа периодических функций, то спектр будет содержать лишь конечное число отличных от нуля коэффициентов, и возникает возможность сжатия информации.

3. Система функций Уолша-Пэли

Если же исходная информация имеет другой характер, например, изменяется по степенному, показательному или логарифмическому закону, то в спектре все его коэффициенты не являются достаточно малыми, и сжатие либо невозможно, либо степень сжатия мала. В этих случаях разумно использовать другой функциональный базис. Поскольку для других базисов нет отчетливого физического представления спектра, то можно интерпретировать (2) как формулы перехода от координатной системы Xk к другой координатной системе Фа(Х). Равенство нулю части коэффициентов означает, что вектор, заданный координатами в виде исходного ряда чисел, в новой системе координат располагается в координатной гиперплоскости размерности N-n. Среди существующих возможностей имеются несколько базисов, порождаемых функциями Радемахера при Z е (0,1):

R0(z) = 1, Rk(z) = sign (sin (2k nz)), k = 1,2,..., (9)

которые в соответствии с входящей в них функцией sign() принимают только два значения: +1 или -1.

Система функций (9) ортогональная и нормированная, но не является полной. К ней можно добавить функции вида sign(cos2knz), которые также ортогональны к функциям системы (9). Поэтому на базе представлений (9) формируют иные полные системы, используя произведения функций Радемахера и внося в получаемые таким образом новые функции определенное упорядочивание.

Наиболее интересной для навигационных применений в плане сжатия информации является система функций Уолша-Пэли. Образование этой системы тесно связано с двоичными номерами составляющих ее функций. Конкретно, функция Уолша-Пэли с номером а есть произведение функций Радемахера с номерами тех двоичных разрядов а, в которых расположены 1. Если записать номер а в двоичном представлении с n = log N разрядами

а = Zk 2k-1 ak, (10)

то функции системы Уолша-Пэли можно представить так:

Wa(z) = Пк М. Сам номер } можно представлять подобно (12) в двоичной форме:

} = Ек 2к-1]к. (15)

Тогда система функций Уолша-Пэли окончательно представится в виде

ЯГа}/Щ = WJ {а/К) = (-1)"как1""к + \ (16)

который используется во всех последующих вычислениях. Программная функция WolshPaly() на языке Паскаль для генерации функций Уолша-Пэли с помощью формул (16) приведена ниже. Для N = 8 значения функций Уолша-Пэли №(/) даны в табл. 1.

Таблица 1. Значения функций Уолша-Пэли для N = 8

] 0 1 2 3 4 5 6 7

0 1 1 1 1 1 1 1 1

Не обсуждая детали, просто упомянем о существовании систем функций Адамара и Хармута, которые отличаются от подробно рассмотренной системы функций Уолша-Пэли только способом упорядочивания одних и тех же функций. Именно порядок функций Уолша-Пэли обеспечивает наибольшее число финальных коэффициентов спектра, нулевых или близких к нулю в заданной степени.

4. Сходимость рядов Уолша-Пэли

Функции Уолша обладают рядом полезных свойств, среди которых приведем используемое в вычислениях свойство симметрии:

Щ (а/Щ. (17)

Двоичное представление номеров функций Уолша с п = logN разрядами определяет порядок р и ранг г функции. Порядком называется наибольший номер двоичного разряда, который равен 1. Рангом Я функции называется число ненулевых двоичных разрядов, например, функция Уолша с номером а = 9 для N = 16 и п = 4 представляется в двоичной форме как 1001, и, следовательно, ее ранг г = 2 (два

ненулевых разряда) и порядок р = 3 (старший ненулевой разряд - третий, т. к. счет идет от нуля). Если функция с номером а имеет ранг г, то ее номер можно представить в виде:

а (Я = г) = 2М1 + 21"2 + ... + 2Мг, (18)

где цк (к = 1, 2,..., г) - номера ненулевых разрядов двоичного представления номера а. Например, номер 9 можно представить как 23 + 20, учитывая двоичное представление 1001. Непосредственно для проблемы сжатия исходной информации важна скорость убывания коэффициентов Са разложения в базисе Уолша при росте номера а. Если функция, представляемая рядом (1), обладает непрерывной производной до даго порядка, и максимальное значение модуля производной |А"(т)| есть М, то коэффициенты спектра с номерами а, ранг которых не меньше порядка производной (г > да), удовлетворяет неравенству (Проектирование специализированных..., 1984):

| Са(г>ш) | < М/ 2ш(ш+3)/2. (19)

Именно это важное неравенство гарантирует быструю сходимость спектральных коэффициентов Са с ростом номера а и открывает перспективы сжатия табличной информации. Действительно, ранг г функции Уолша увеличивается с ростом номера функции а так, что условие г > ш выполняется для больших номеров а. Это значит, что оценка (19) действует для финальных коэффициентов разложения.

Таблица 2. Коэффициенты спектрального разложения степенных функций в базисе Уолша

ПОРЯДОК РАНГ СТЕПЕНЬ ФУНКЦИИ

0 0 4.68 3.03 2.20 1.37

1 0 -2.50 -2.34 -1.96 -1.34

2 1 -1.25 -1.17 -1.10 -0.95

3 1 0 0.63 0.88 0.92

4 2 -0.63 -0.59 -0.56 -0.52

5 2 0 0.31 0.44 0.49

6 2 0 0.16 0.22 0.31

7 3 0 0 -0.12 -0.29

8 3 -0.31 -0.29 -0.28 -0.26

9 3 0 0.16 0.22 0.25

10 3 0 0.08 0.11 0.15

11 3 0 0 -0.06 -0.15

12 3 0 0.04 0.05 0.08

13 3 0 0 -0.03 -0.07

14 3 0 0 -0.01 -0.04

15 3 0 0 0 -0.03

од % 43.8 18.8 6.3 0

Если к тому же функция имеет конечное число отличных от нуля производных (например, степенная функция), то все коэффициенты с номерами, чьи ранги больше этой степени, тождественно равны нулю. Но для этого необходимо, чтобы число N было достаточно велико, и ранг "успел" стать больше номера старшей производной. В качестве примера рассмотрим спектральное разложение степенной функции, представленной рядом (1), с числом отсчетов, равным 16 ^ = 16, п = 4). Малое число отсчетов выбрано только для обозримости результатов примера. Выше в табл. 2 приведены с округлением до двух знаков спектральные коэффициенты разложения для различных степенных функций: линейной, квадратической, кубической и пятой степени - с одновременным указанием номера а спектра и его ранга г.

На этом примере видно, что чем меньше степень функции, которая порождает ряд чисел (1), тем большей степени сжатия од можно достичь при разложении. Если ряд короткий, а степень велика, то сжатие вообще не достигается, как это происходит при пятой степени функции. Если при той же степени функции увеличивать число членов ряда и, следовательно, число коэффициентов спектра, то степень

сжатия растет. Так, при N = 64 sq = 7.8 %, при N = 128 sq = 18.0 %, при N = 256 sq = 23.8 %.

Заметим попутно, что в случае спектра Фурье ни в одном из приведенных случаев никакого сжатия не достигается - налицо неадекватность тригонометрического базиса степенным функциям.

4. Основные формулы дискретного преобразования Уолша-Пэли

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

Итак, мы выберем в качестве функционального базиса систему функций Уолша-Пэли (16) и приведем для этой системы основные формулы, выражающие свойства ортогональности и нормировки функций в этой системе, и формулы преобразования для нее:

Формула прямого дискретного преобразования Уолша для получения спектра

Са = (1/N) ZkXkWa(k/N).

Формула обратного дискретного преобразования Уолша для восстановления исходного ряда значений

Xk = EaCaWa (k/N).

Условие ортогональности и нормировки функций Уолша на дискретном множестве точек

No = (1/N)Zk Wp(k/N) W(k/N) = 0, если p Ф q и No = 1, если p = q. Равенство Парсеваля

(1/N) ZkXk2= ЪаСа,

которое представляет собой равенство квадрата модуля вектора в исходной Xk и новой Са системах координат.

5. Элементы программной реализации

Именно этот набор формул был положен автором в основу при составлении программы на языке Паскаль для сравнительного анализа результатов дискретных преобразований Фурье и Уолша (свидетельство на программный продукт РОСАПО № 950347 от 02.10.1995). При этом дискретные преобразования были реализованы как быстрые преобразования Фурье (БПФ) и Уолша (БПУ) с основанием 2 и прореживанием по времени (Рабиндер, Голд, 1978). Это не имеет значения для сжатия табличной информации, так как преобразование в этом случае производится один раз, но очень важно при обработке информации в реальном масштабе времени для возможности прогонки большего числа различных числовых рядов (таблиц, функций) за минимальное время. Подобная программа практически без изменений была с успехом применена при оперативном спектральном анализе на борту летающей лаборатории ИЛ18-ДОРР ПИНРО. Два основных фрагмента этой программы приведены ниже. Это процедура быстрого преобразования Уолша и функция вычисления значения функции Уолша по заданному номеру и аргументу. Вся программа занимает слишком много места и потому здесь не приводится.

Function WolshPaly(Alf, l: integer) : integer; var J, K, x, y, w, maskl, mask2: integer; begin

w:=l; mask1:=l; mask2:=N div 2; for K:=0 to N-l do begin

if (Alf and mask2)<>0 and (I and mask1)<>0 then w:=-w; mask1:=mask1*2; mask2:=mask2 div 2; end;

WolshPaly:=w; end;

Эта функция принимает два параметра - номер Alf и аргумент I функции Уолша и возвращает само значение функции Уолша.

Procedure FastWolshTrans(var ml, m2, m3, m4: masdat); var L, LE, LE1, I, J, IP: integer; T1,T2: real;

begin LE:=1; for L:=1 to M do begin LE1:=LE; LE:=LE*2;

for J:=1 to LE1 do begin I:=J; repeat IP:=I+LEl; T1:=m1; T2:=m2;

If L=M then begin

m3:=m1[I]-T1; m4:=m2[I]-T2; m3[I]:=m1[I]+T1; m4[I]:=m2[I]+T2;

m1:=m1[I]-T1; m2:=m2[I]-T2; m1[I]:= m1[I]+T1; m2[I]:=m2[I]+T2;

I:=I+LE; until I>N; end; end;

/* "D" - знак прямого преобразования */

if TIP="D" then begin for L:=1 to N do begin m3[L]:=m3[L]/N; m4[L]:=m4[L]/N; end;

Процедура производит быстрое преобразование Уолша данных, которые передаются процедуре в массивах ml и m2. Результат преобразования - спектр Уолша возвращается процедурой в массивах m3 и m4. Если данные передаются процедуре в обычном порядке следования, то результат возвращается в двоично-инвертированном порядке. Если же мы хотим получить обычный порядок коэффициентов спектра, то исходные данные для обработки следует двоично инвертировать. Двоичным инвертированием номера считается номер, в котором порядок его двоичных разрядов изменен на обратный, например, инверсия числа 6 = 110 есть 3 = 011. Для инверсии любых номеров предлагается процедура на языке Pascal:

Procedure MASINVERSION(sw: integer; var m1, m2: masdat); var I, J, K, NV2: integer; T: real; begin NV2:=N div 2;

for I:=1 to N-1 do begin

if I

else begin K:=NV2; while K

6. Сжатие таблиц с двумя аргументами

Выше были рассмотрены преобразования и сжатие одномерных, линейных таблиц. Но большинство применяемых в судовождении таблиц являются двумерными - прямоугольными матрицами. Вопрос об их сжатии можно решить двумя путями. Первый путь - преобразование таблицы как линейной, считая, что она образована последовательным размещением строк таблицы-матрицы, начиная с первой строки. Этот путь вполне обычен, ведь именно так хранится двумерный массив в линейно организованной памяти ЭВМ. Преимущество такого способа состоит в том, что размер такой линейной таблицы будет достаточно большим, и можно надеяться на эффективность сжатия. Но в нем скрыты и возможные неприятности. После выстраивания в линию строк матрицы мы наверняка получим скачки функции при переходе от конца одной строки к началу следующей. Эту трудность можно обойти изменением порядка элементов в каждой четной строке - инвертированием этой строки. Соответственно, изменится и порядок спектральных коэффициентов. Но это не усложнит, а только изменит порядок номеров при восстановлении значений самой функции. Так, если номер значения восстанавливаемой функции был Npq = (р - 1) М + q, где р - номер строки с числом М элементов в ней, а q - номер столбца, то после инвертирования для четных строк этот номер станет равным (р - 1) М + (М- q + 1).

Второй путь - сначала спектральное преобразование строк таблицы, а затем преобразование полученного промежуточного спектра по столбцам. Недостатком этого способа можно считать малую степень сжатия из-за малой длины строк и столбцов. Правда, эффект сжатия усиливается за счет двойного преобразования и строк, и столбцов. Например, при сжатии строк и столбцов всего на 10 % общий эффект сжатия будет равен 1 - 0.9x0.9 = 0.19 = 19 %. Если, например, строки таблицы изменяются по квадратическому закону, а столбцы по кубическому, то общий эффект сжатия по данным табл. 2 равен 1-(1-0.188)х(1-0.63) = 0.24 = 24 %.

В качестве конкретного примера приведем результаты преобразования таблицы интегральной функции Лапласа (Кондрашихин, 1969), которую применяют в судовождении при оценке надежности мореплавания. Здесь она представлена в виде матрицы 30x10, т.е. состоит из 30 строк и 10 столбцов. Преобразовывать ее как двумерную нет никакого смысла: слишком мало (10) элементов в строках. Поэтому преобразуем ее как линейную таблицу из 300 значений. В примере будем считать, что значений 256 = 28. Но можно было бы дополнить таблицу нулями и считать число значений 512 = 29. Ив том, и в другом случаях получен одинаковый результат: финальное число нулей с степенью близости к нулю порядка 0.01 % от максимального коэффициента составляет 46.5 %. Восстановление функции по сжатой до 53.5 % совокупности коэффициентов спектра дало погрешности: среднюю квадратическую в 0.005 и максимальную в 0.057. Пример показывает эффективность проведенного преобразования таблицы.

7. Заключение

Проведенные исследования, связанные с выбором функционального базиса Уолша-Пэли, показывают, что этот функциональный базис может успешно применяться в различных системах обработки информации, не носящей выраженного периодического характера. В этом случае преимущества такого функционального базиса перед базисом Фурье очевидны. Кроме того, базис Уолша-Пэли дает хороший эффект при сжатии информации. Это показано на примере характерной для задач надежности навигации таблицы интегральной функции Лапласа, где эффект сжатия достиг 53.5 %.

Литература

Голд Б., Рейдер Ч. Цифровая обработка сигналов. М., Сов.радио, 367 е., 1993. Кондрашихин В.Т. Теория ошибок. М., Транспорт, 256 е., 1969.

Проектирование специализированных информационно-вычислительных систем. Под ред.

Смирнова Ю.Н. М., Высшая школа, 359 е., 1984. Рабиндер Л., Голд Б. Теория и приложения цифровой обработки сигналов. М., Мир, 528 е., 1978. Трахтман А.Н., Трахтман В.А. Введение в общую спектральную теорию сигналов. М., Сов.радио, 312 е., 1978.

Функциями Уолша называется семейство функций, образующих ортогональную систему , принимающих значения только 1 и -1 на всей области определения.

В принципе, функции Уолша могут быть представлены в непрерывной форме, но чаще их определяют как дискретные последовательности из $2^n$ элементов. Группа из $2^n$ функций Уолша образует матрицу Адамара .

Функции Уолша получили широкое распространение в радиосвязи, где с их помощью осуществляется кодовое разделение каналов (CDMA), например, в таких стандартах сотовой связи, как IS-95, CDMA2000 или UMTS .

Система функций Уолша является ортонормированным базисом и, как следствие, позволяет раскладывать сигналы произвольной формы в обобщённый ряд Фурье .

Обобщением функций Уолша на случай более чем двух значений являются функции функции Виленкина - Крестенсона .

Обозначение

Пусть функция Уолша определена на интервале ; за пределами этого интервала функция периодически повторяется. Введём безразмерное время $\backslash theta\; =\; t\; /\; T$. Тогда функция Уолша под номером k обозначается как $wal(k,\backslash theta)$. Нумерация функций зависит от метода упорядочения функций. Существует упорядочение по Уолшу - в этом случае функции обозначаются так, как описано выше. Также распространены упорядочения по Пэли ($pal(p,\backslash theta)$) и по Адамару ($had(h,\backslash theta)$).

Относительно момента $\backslash theta\; =\; 0$ функции Уолша можно разделить на чётные и нечётные. Они обозначаются как $cal(k,\backslash theta)$ и $sal(k,\backslash theta)$ соответственно. Эти функции аналогичны тригонометрическим синусам и косинусам. Связь между этими функциями выражается следующим образом:

$cal(k,\backslash theta)\; =\; wal(2k,\backslash theta)$ $sal(k,\backslash theta)\; =\; wal(2k-1,\backslash theta)$

Формирование

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

$H\_\{2^n\}\; =\; \backslash begin\{bmatrix\}$

H_{2^{n-1}} & H_{2^{n-1}} \\ H_{2^{n-1}} & -H_{2^{n-1}} \end{bmatrix}

Так может быть сформирована матрица Адамара длины $2^n$:

$H\_1\; =\; \backslash begin\{bmatrix\}$

1 \end{bmatrix}

$H\_2\; =\; \backslash begin\{bmatrix\}$

1 & 1 \\ 1 & -1 \end{bmatrix}

$H\_4\; =\; \backslash begin\{bmatrix\}$

1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix}

Каждая строка Матрицы Адамара и является функцией Уолша.

В данном случае функции упорядочены по Адамару. Номер функции по Уолшу вычисляется из номера функции по Адамару путём перестановки бит в двоичной записи номера в обратном порядке с последующим преобразованием результата из кода Грея .

Пример

В итоге получается матрица Уолша, в которой функции упорядочены по Уолшу:

$W\_4\; =\; \backslash begin\{bmatrix\}$

1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \end{bmatrix}

Свойства

1. Ортогональность

Напишите отзыв о статье "Функция Уолша"

Литература

• Баскаков С. И. Радиотехнические цепи и сигналы. - М.:Высшая школа, 2005 - ISBN 5-06-003843-2
• Голубов Б. И., Ефимов А. В., Скворцов В. А. Ряды и преобразования Уолша: теория и применения. - М.:Наука, 1987
• Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. - М.: Наука, 1989 - ISBN 5-02-014094-5

См. также

Примечания

Отрывок, характеризующий Функция Уолша

– Видно, еще не все ушли, князь, – сказал Багратион. – До завтрашнего утра, завтра всё узнаем.
– На горе пикет, ваше сиятельство, всё там же, где был с вечера, – доложил Ростов, нагибаясь вперед, держа руку у козырька и не в силах удержать улыбку веселья, вызванного в нем его поездкой и, главное, звуками пуль.
– Хорошо, хорошо, – сказал Багратион, – благодарю вас, г. офицер.
– Ваше сиятельство, – сказал Ростов, – позвольте вас просить.
– Что такое?
– Завтра эскадрон наш назначен в резервы; позвольте вас просить прикомандировать меня к 1 му эскадрону.
– Как фамилия?
– Граф Ростов.
– А, хорошо. Оставайся при мне ординарцем.
– Ильи Андреича сын? – сказал Долгоруков.
Но Ростов не отвечал ему.
– Так я буду надеяться, ваше сиятельство.
– Я прикажу.
«Завтра, очень может быть, пошлют с каким нибудь приказанием к государю, – подумал он. – Слава Богу».

Крики и огни в неприятельской армии происходили оттого, что в то время, как по войскам читали приказ Наполеона, сам император верхом объезжал свои бивуаки. Солдаты, увидав императора, зажигали пуки соломы и с криками: vive l"empereur! бежали за ним. Приказ Наполеона был следующий:
«Солдаты! Русская армия выходит против вас, чтобы отмстить за австрийскую, ульмскую армию. Это те же баталионы, которые вы разбили при Голлабрунне и которые вы с тех пор преследовали постоянно до этого места. Позиции, которые мы занимаем, – могущественны, и пока они будут итти, чтоб обойти меня справа, они выставят мне фланг! Солдаты! Я сам буду руководить вашими баталионами. Я буду держаться далеко от огня, если вы, с вашей обычной храбростью, внесете в ряды неприятельские беспорядок и смятение; но если победа будет хоть одну минуту сомнительна, вы увидите вашего императора, подвергающегося первым ударам неприятеля, потому что не может быть колебания в победе, особенно в тот день, в который идет речь о чести французской пехоты, которая так необходима для чести своей нации.
Под предлогом увода раненых не расстроивать ряда! Каждый да будет вполне проникнут мыслию, что надо победить этих наемников Англии, воодушевленных такою ненавистью против нашей нации. Эта победа окончит наш поход, и мы можем возвратиться на зимние квартиры, где застанут нас новые французские войска, которые формируются во Франции; и тогда мир, который я заключу, будет достоин моего народа, вас и меня.
Наполеон».

В 5 часов утра еще было совсем темно. Войска центра, резервов и правый фланг Багратиона стояли еще неподвижно; но на левом фланге колонны пехоты, кавалерии и артиллерии, долженствовавшие первые спуститься с высот, для того чтобы атаковать французский правый фланг и отбросить его, по диспозиции, в Богемские горы, уже зашевелились и начали подниматься с своих ночлегов. Дым от костров, в которые бросали всё лишнее, ел глаза. Было холодно и темно. Офицеры торопливо пили чай и завтракали, солдаты пережевывали сухари, отбивали ногами дробь, согреваясь, и стекались против огней, бросая в дрова остатки балаганов, стулья, столы, колеса, кадушки, всё лишнее, что нельзя было увезти с собою. Австрийские колонновожатые сновали между русскими войсками и служили предвестниками выступления. Как только показывался австрийский офицер около стоянки полкового командира, полк начинал шевелиться: солдаты сбегались от костров, прятали в голенища трубочки, мешочки в повозки, разбирали ружья и строились. Офицеры застегивались, надевали шпаги и ранцы и, покрикивая, обходили ряды; обозные и денщики запрягали, укладывали и увязывали повозки. Адъютанты, батальонные и полковые командиры садились верхами, крестились, отдавали последние приказания, наставления и поручения остающимся обозным, и звучал однообразный топот тысячей ног. Колонны двигались, не зная куда и не видя от окружавших людей, от дыма и от усиливающегося тумана ни той местности, из которой они выходили, ни той, в которую они вступали.
Солдат в движении так же окружен, ограничен и влеком своим полком, как моряк кораблем, на котором он находится. Как бы далеко он ни прошел, в какие бы странные, неведомые и опасные широты ни вступил он, вокруг него – как для моряка всегда и везде те же палубы, мачты, канаты своего корабля – всегда и везде те же товарищи, те же ряды, тот же фельдфебель Иван Митрич, та же ротная собака Жучка, то же начальство. Солдат редко желает знать те широты, в которых находится весь корабль его; но в день сражения, Бог знает как и откуда, в нравственном мире войска слышится одна для всех строгая нота, которая звучит приближением чего то решительного и торжественного и вызывает их на несвойственное им любопытство. Солдаты в дни сражений возбужденно стараются выйти из интересов своего полка, прислушиваются, приглядываются и жадно расспрашивают о том, что делается вокруг них.
Туман стал так силен, что, несмотря на то, что рассветало, не видно было в десяти шагах перед собою. Кусты казались громадными деревьями, ровные места – обрывами и скатами. Везде, со всех сторон, можно было столкнуться с невидимым в десяти шагах неприятелем. Но долго шли колонны всё в том же тумане, спускаясь и поднимаясь на горы, минуя сады и ограды, по новой, непонятной местности, нигде не сталкиваясь с неприятелем. Напротив того, то впереди, то сзади, со всех сторон, солдаты узнавали, что идут по тому же направлению наши русские колонны. Каждому солдату приятно становилось на душе оттого, что он знал, что туда же, куда он идет, то есть неизвестно куда, идет еще много, много наших.
– Ишь ты, и курские прошли, – говорили в рядах.
– Страсть, братец ты мой, что войски нашей собралось! Вечор посмотрел, как огни разложили, конца краю не видать. Москва, – одно слово!
Хотя никто из колонных начальников не подъезжал к рядам и не говорил с солдатами (колонные начальники, как мы видели на военном совете, были не в духе и недовольны предпринимаемым делом и потому только исполняли приказания и не заботились о том, чтобы повеселить солдат), несмотря на то, солдаты шли весело, как и всегда, идя в дело, в особенности в наступательное. Но, пройдя около часу всё в густом тумане, большая часть войска должна была остановиться, и по рядам пронеслось неприятное сознание совершающегося беспорядка и бестолковщины. Каким образом передается это сознание, – весьма трудно определить; но несомненно то, что оно передается необыкновенно верно и быстро разливается, незаметно и неудержимо, как вода по лощине. Ежели бы русское войско было одно, без союзников, то, может быть, еще прошло бы много времени, пока это сознание беспорядка сделалось бы общею уверенностью; но теперь, с особенным удовольствием и естественностью относя причину беспорядков к бестолковым немцам, все убедились в том, что происходит вредная путаница, которую наделали колбасники.

Лекция 17. Функции Уолша и их применение

Функции Уолша. Основные определения. Способы упорядочения функций Уолша

Функции Уолща являются естественным расширением системы функций Радемахера, получены Уолшем в 1923 г. и представляют полную систему ортонормированных прямоугольных функций.

Множество функций Уолша, упорядоченных по частости, обычно обозначают следующим образом:

Функции Уолша, упорядоченные по частости, аналогично тригонометрическим функциям можно подразделить на четные cal(i,t) и нечетные sal(i,t)

На рисунке 17.1 показаны первые восемь функций wal w (i,t).

Рисунок 17.1

При этом видно, что частость каждой последующей функции Уолша больше или равняется частости предыдущей функции Уолша и имеет на одно пересечение нулевого уровня больше в открытом интервале t. Отсюда и следует название «упорядочение по частости».

Дискретизация функций Уолша, показанных на рисунке 17.1а, в восьми равноотстоящих точках приводит к матрице (8х8), показанной на рисунке 17.1б. Эту матрицу обозначают H w (n) где n=log 2 N и матрица будет иметь размер NxN.

Функции Уолша при упорядочении по частости в общем случае можно получать из функций Радемахера r k (x) по формуле:

где w номер функции Уолша; k – номер функции Радемахера;
показатель степени функции Радемахера, который принимает значение 0 или 1 в результате суммирования по модулю два, т.е. по правилу: 11=00=0; 10=01=1 разрядов двоичного числа w . Например для шестой функции Уолша (w =6), входящей в систему размером N=2 3 =8 произведение (17.4) состоит из трех сомножителей вида: при k=1
при k=2
при k=3
. Число в двоичной системе записывается совокупностью нулей и единиц. В нашем случае значение w и его разрядов показаны в таблице 17.1

Таблица 17.1

					r 1 (x)  r 2 (x)  r 3 (x) = wal(w ,x)
					r 1 0 (x)  r 2 0 (x)  r 3 0 (x) = wal(0,x)
					r 1 1 (x)  r 2 0 (x)  r 3 0 (x) = wal(1,x)
					r 1 1 (x)  r 2 1 (x)  r 3 0 (x) = wal(2,x)
					r 1 0 (x)  r 2 1 (x)  r 3 0 (x) = wal(3,x)
					r 1 0 (x)  r 2 1 (x)  r 3 1 (x) = wal(4,x)
					r 1 1 (x)  r 2 1 (x)  r 3 1 (x) = wal(5,x)
					r 1 1 (x)  r 2 0 (x)  r 3 1 (x) = wal(6,x)
					r 1 0 (x)  r 2 0 (x)  r 3 1 (x) = wal(7,x)

w 0 – старший разряд числа, w 3 – младший разряд числа w .

Показатели степени функций Радемахера получаются равными:
;
;
и следовательно,

wal(6,x)=r 1 1 (x)r 2 0 (x)r 3 1 (x)=r 1 (x)r 3 (x)

Правило получения показателей степеней для функции Радемахера схематически показано в таблице 17.1, где стрелками указаны суммируемые разряды числа w и функции Радемахера, к которым относится полученный показатель степени. Из рисунка 17.1 видно, что четные номера функций Уолша относятся к четным функциям, а нечетные к нечетным функциям. Другим способом упорядочения являются упорядочение по Пэли. При упорядочении по Пэли, аналитическая запись функции Уолша имеет вид:

p 1 – младший разряд двоичного числа, р n – старший разряд двоичного числа. При упорядочении по Пэли для формирования функций Уолша необходимо взять произведение возведенных в степень функций Радемахера, номера которых совпадают с номерами соответствующих разрядов двоихного представления числа р, а показатель степени каждой функции равен содержимому соответствующего разряда, т.е. 0 или 1. Причем младшей функции Радемахера соответствует младший разряд двоичной комбинации числа р. В соответствии с этим правилом в таблице 17.2 приведены значения функций Уолша упорядоченных по Пэли.

Таблица 17.2

				r 1 (x)  r 2 (x)  r 3 (x)	wal p (i,x) = wal w (j,x)
				r 1 0 (x)  r 2 0 (x)  r 3 0 (x)	wal p (0,x) = wal w (0,x)
				r 1 1 (x)  r 2 0 (x)  r 3 0 (x)	wal p (1,x) = wal w (1,x)
				r 1 0 (x)  r 2 1 (x)  r 3 0 (x)	wal p (2,x) = wal w (3,x)
				r 1 1 (x)  r 2 1 (x)  r 3 0 (x)	wal p (3,x) = wal w (2,x)
				r 1 0 (x)  r 2 0 (x)  r 3 1 (x)	wal p (4,x) = wal w (7,x)
				r 1 1 (x)  r 2 0 (x)  r 3 1 (x)	wal p (5,x) = wal w (6,x)
				r 1 0 (x)  r 2 1 (x)  r 3 1 (x)	wal p (6,x) = wal w (4,x)
				r 1 1 (x)  r 2 1 (x)  r 3 1 (x)	wal p (7,x) = wal w (5,x)

Функции Радемахера в таблице показаны в форме:
. Сравнение произведений и степеней функций Радемахера, записанных в таблицах 17.1 и 17.2 показывает., что между функциями Уолша, упорядоченными по Пэли и по Уолшу существует соответствие, которое отражено в последнем столбце таблицы 17.2. В соответсвии с функциями Уолша упорядоченными по Пэли также может быть построена матрица отсчетов H p (n), аналогичная показанной на рисунке 17.1б.

Следующим распространенным способом упорядочения является упорядочение по Адамару. Функции Адамара har(h,x) формируют с помощью матриц Адамара. Матрицей Адамара H N порядка N=2 n называется квадратная матрица с размерами NxN и элементами 1, обладающая свойством

Например начиная с Н 1 =1 находим:

Сравнивая полученную матрицу Н 8 с матрицей отсчетов для функции Уолша, Упорядоченных по Уолшу (рисунок 17.1б) видим, что между первыми восемью функциями упорядоченными по Уолшу и Адамару существует следующее соответствие:

и может служить базисом для спектрального представления сигналов. Любую интегрируемую на интервале 0х1 функцию являющуюся математической моделью электрического сигнала, можно представить рядом Фурье по системе функций Уолша

где
- безразмерное время, нормированное к произвольному интервалу Т.

Функции Уолша, как и функции Радемахера, принимают только два значения: -1 и 1. Для любого m – wal 2 (m,x)=wal(0,x)=1.

Функции Уолша являются периодическими функциями с периодом равным 1.

Функции Уолша обладают свойством мультипликативности, перемножение любых двух функций Уолша является также функцией Уолша:

Среднее значение функции Уолша wal(i,x), при i0 равно нулю.

Система функций Уолша является составной системой и сотоит из четных и нечетных функций, обозначаемых соответственно:

Относительная погрешность аппроксимации сигнала f(x) конечным числом функций Уолша определяется по формуле

где
- энергия сигнала на единичном нормированном интервале.

Вопросы для самостоятельной подготовки

Найдите выражения для функций Уолша через функции Радемахера wal(7,x), wal(9,x), wal(13,x) при упорядочении по Уолшу, Пэли и Адамару.

Перечислите и объясните основные свойства функций Уолша.

Разложите в ряд Уолша, ограничиваясь первыми восемью функциями Уолша функций sinx , cosx и постройте их.

Охарактеризуйте достоинства и недостатки каждого из рассмотренных способов упорядочения функций Уолша.

Рассчитайте значения первых 8 коэффициентов разложения в ряд Фурье – Уолша следующих сигналов:

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

Базовые понятия

Кодовые последовательности, используемые в CDMA-системах для передачи сигнала, состоят из N элементарных символов (чипов). Каждый информационный символ сигнала складывается с одной N-символьной последовательностью, которая называется «расширяющей» (spreading sequence), поскольку «результирующий» сигнал излучается в эфир с преднамеренно расширенным спектром. Выигрыш в качестве связи зависит как от числа символов (длины) последовательности, так и от характеристик совокупности сигналов, в первую очередь – их взаимокорреляционных свойств и способа модуляции.

Длина последовательности. В отечественной литературе сигналы, база которых существенно больше единицы (B=TF>>1, где T – длительность элемента сигнала, F – полоса частот), обычно называются сложными. По отношению к исходному (информационному) сложный сигнал представляет собой шум с практически одинаковой спектральной плотностью мощности.

Известно, что чем сильнее «растянут» спектр сигнала в эфире, тем меньше его спектральная плотность. Благодаря этому свойству сигналы с большой базой могут применяться в «чужой» (уже занятой) полосе частот «на вторичной основе», оказывая на работающую там систему сколь угодно малое воздействие.

Характеристики. Вся совокупность кодовых последовательностей, используемых в CDMA, делится на два основных класса: ортогональные (квазиортогональные) и псевдослучайные последовательности (ПСП) с малым уровнем взаимной корреляции (рис. 1).

В оптимальном CDMA-приемнике поступающие на его вход сигналы, которые, по сути, представляют собой аддитивный белый гауссовский шум, всегда обрабатываются с помощью корреляционных методов. Поэтому процедура поиска сводится к нахождению сигнала, максимально коррелированного с индивидуальным кодом абонента. Корреляция между двумя последовательностями {x(t)} и {y(t)} осуществляется путем перемножения одной последовательности на сдвинутую во времени копию другой. В зависимости от вида последовательности в CDMA-системах применяются различные способы корреляции:

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

Дабы получить выигрыш в качестве связи при использовании любого из способов корреляционной обработки, необходимо, чтобы ансамбль сигналов обладал «хорошими» автокорреляционными свойствами. Желательно, чтобы сигналы имели единственный автокорреляционный пик, иначе возможна ложная синхронизация по боковому лепестку автокорреляционной функции (АКФ). Заметим, что чем шире спектр излучаемых сигналов, тем уже центральный пик (основной лепесток) АКФ.

Пары кодовых последовательностей подбираются так, чтобы взаимная корреляционная функция (ВКФ) имела минимальное значение при их попарной корреляции. Это гарантирует минимальный уровень взаимных помех.

Следовательно, выбор оптимального ансамбля сигналов в CDMA сводится к поиску такой структуры кодовых последовательностей, в которой центральный пик АКФ имеет наибольший уровень, а боковые лепестки АКФ и максимальные выбросы ВКФ по возможности минимальны.

Ортогональные коды

В зависимости от способа формирования и статистических свойств ортогональные кодовые последовательности разделяются на собственно ортогональные и квазиортогональные. Отличительный признак последовательности – коэффициент взаимной корреляции pij, который в общем случае изменяется от -1 до +1.

В теории сигналов доказано, что предельно достижимое значение коэффициента взаимной корреляции определяется из условия

Минимальное значение ВКФ обеспечивает коды, у которых коэффициенты корреляции для любых пар последовательностей являются отрицательными (трансортогональные коды ). Коэффициент взаимной корреляции ортогональных последовательностей, по определению, равен нулю, т.е. о? ij =0. При больших значениях N различием между коэффициентами корреляции ортогональных и трансортогональных кодов практически можно пренебречь.

Существует несколько способов генерации ортогональных кодов. Наиболее распространенный – с помощью последовательностей Уолша длиной 2 n , которые образуются на основе строк матрицы Адамара

Многократное повторение процедуры позволяет сформировать матрицу любого размера, для которой характерна взаимная ортогональность всех строк и столбцов.

Такой способ формирования сигналов реализован в стандарте IS-95, где длина последовательностей Уолша выбрана равной 64. Заметим, что различие между строками матрицы Адамара и последовательностями Уолша состоит лишь в том, что в последних используются униполяные сигналы вида {1,0}.

На примере матрицы Адамара легко проиллюстрировать и принцип построения трансортогональных кодов. Так, можно убедиться, что если из матрицы вычеркнуть первый столбец, состоящий из одних единиц, то ортогональные коды Уолша трансформируются в трансортогональные, у которых для любых двух последовательностей число несовпадений символов превышает число совпадений ровно на единицу, т.е. о? ij = -1/(N-1).

Другая важная разновидность ортогональных кодов – биортогональный код, который формируется из ортогонального кода и его инверсии. Главное достоинство биортогональных кодов по сравнению с ортогональными – возможность передачи сигнала во вдвое меньшей полосе частот. Скажем, биортогональный блочный код (32,6), используемый в WCDMA, позволяет передавать сигнал транспортного формата TFI.

Отметим, что ортогональным кодам присущи два принципиальных недостатка.

1. Максимальное число возможных кодов ограничено их длиной (в стандарте IS-95 число кодов равно 64), а соответственно, они имеют ограниченное адресное пространство.

Для расширения ансамбля сигналов наряду с ортогональными используются квазиортогональные последовательности. Так, в проекте стандарта cdma2000 предложен метод генерации квазиортогональных кодов путем умножения последовательностей Уолша на специальную маскирующую функцию. Этот метод позволяет с помощью одной такой функции получить набор квазиортогональных последовательностей Quasi-Orthogonal Function Set (QOFS). С помощью m маскирующих функций и ансамбля кодов Уолша длиной 2 n можно создать (m+1) 2 n QOF-последовательностей.

2. Еще один недостаток ортогональных кодов (не исключение – и применяемые в стандарте IS-95) заключается в том, что функция взаимной корреляции равна нулю лишь «в точке», т.е. при отсутствии временного сдвига между кодами. Поэтому такие сигналы используются лишь в синхронных системах и преимущественно в прямых каналах (от базовой станции к абоненту).

Возможность адаптации системы CDMA к различным скоростям передачи обеспечивается за счет использования специальных ортогональных последовательностей с переменным коэффициентом расширения спектра (OVSF, Orthogonal Variable Spreading Factor), называемых кодами переменной длины . При передаче CDMA-сигнала, который создавался с помощью такой последовательности, чиповая скорость остается постоянной, а информационная скорость изменяется кратно двум. В стандартах 3-го поколения предлагается использовать в качестве OVSF-кодов ортогональные коды Голда с кратными скоростями передачи (multirate). Принцип их образования достаточно прост; его поясняет рис. 3, где приведено кодовое дерево, позволяющее строить коды разной длины.

Каждый уровень кодового дерева определяет длину кодовых слов (коэффициент расширения спектра, SF), причем на каждом последующем уровне возможное число кодов удваивается. Так, если на уровне 2 может быть образовано только два кода (SF=2), то на уровне 3 генерируются уже четыре кодовых слова (SF=4) и т.д. Полное кодовое дерево содержит восемь уровней, что соответствует коэффициенту SF=256 (на рисунке показаны лишь три нижних уровня).

Таким образом, ансамбль OVSF-кодов не является фиксированным: он зависит от коэффициента расширения SF, т.е. фактически – от скорости канала.

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

Псевдослучайные последовательности

Наряду с ортогональными кодами ключевую роль в CDMA-системах играют ПСП, которые хотя и генерируются детерминированным образом, обладают всеми свойствами случайных сигналов. Однако они выгодно отличаются от ортогональных последовательностей инвариантностью к временному сдвигу. Существует несколько видов ПСП, обладающих разными характеристиками. Говоря попросту, сегодня появились технические средства, способные «вывести» любой ансамбль последовательностей с заданными свойствами.

m-последовательности

Одно из наиболее простых и чрезвычайно эффективных средств генерации двоичных детерминированных последовательностей – использование регистра сдвига (РС). Последовательность на выходе n-разрядного РС с обратной связью всегда периодична, причем ее период n (число тактов, через которое схема возвращается в исходное состояние) не превышает 2 n .

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

Функция автокорреляции m-последовательности является периодической и двузначной:

Уровень побочных максимумов автокорреляционной функции (рис. 4) не превышает значения

Коды Голда формируются путем посимвольного сложения по модулю 2 двух m-последовательностей (рис. 5). В проекте WCDMA специфицированы три типа кодов Голда: первичный и вторичный ортогональные коды Голда (оба длиной 256 бит) и длинный код.

Ортогональные коды Голда создаются на основе m-последовательности длиной 255 бит с добавлением одного избыточного символа. Первичный синхрокод имеет апериодическую автокорреляционную функцию и используется для первоначального вхождения в синхронизм. Вторичный синхрокод представляет собой немодулированный ортогональный код Голда, который передается параллельно с первичным синхрокодом. Каждый вторичный синхрокод выбирается из 17 различных кодов Голда {C1,...,C17}.

Длинный код для прямого канала представляет собой фрагменты кода Голда длиной 40 960 чипов. Система связи на базе WCDMA асинхронна, и соседние базовые станции используют различные коды Голда (всего их 512), повторяемые каждые 10 мс. Асинхронный принцип работы базовых станций делает их независимыми от внешних источников синхронизации. Предполагается применять длинный код и в обратном канале, однако только в тех сотах, где не задействуется режим многопользовательского детектирования.

Семейство кодов Касами содержит 2 к последовательностей с периодом 2 n-1 . Они считаются оптимальными в том смысле, что для любой «предпочтительной» пары обеспечивается максимальное значение автокорреляционной функции, равное (1+2 к).

Кодовые последовательности Касами реализуются с помощью трех последовательно включенных регистров сдвига (u, v и w) с различными обратными связями (рис. 6), каждый из которых формирует свою m-последовательность. Чтобы получить кодовые последовательности Касами с заданными свойствами, последовательности v и w должны иметь различные сдвиги.

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

Последовательности Баркера

Псевдослучайные последовательности с малым значением апериодической АКФ способны обеспечить синхронизацию передаваемых и принимаемых сигналов за достаточно короткий промежуток времени, обычно равный длине самой последовательности. Наибольшую известность получили последовательности Баркера (см. таблицу).

Эффективность последовательностей с апериодической АКФ принято оценивать показателем качества F, который определяется как отношение квадратов синфазных составляющих сигнала к сумме квадратов его расфазированных составляющих. Таким образом, мерой эффективности апериодической корреляции двоичной последовательности является показатель качества.

При решении многих задач анализа сложный сигнал удобно представить в виде совокупности элементарных сигналов. На практике наибольшее применение нашло представление сигнала s(t), заданного на интервале , в виде линейной комбинации некоторых элементарных функций (p t (t ), / = 0,1,2,..., называемых базисными

- норма базисной функции.

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

или систему комплексных экспоненциальных функций

Однако по мере развития цифровых методов передачи и обработки сигналов в последние годы в качестве базисных функций начинают использовать дискретные ортогональные последовательности в виде функций Радемахера, Уолша, Хаара и др.

Введем безразмерное время 0 = t / Т . Функции Радемахера образуются из синусоидальных функций с помощью соотношения

Иначе говоря, функции Радемахера, принимающие значения ±1, можно трактовать как функции «прямоугольного синуса». Графики первых четырех функций Радемахера имеют вид, представленный на рисунке 4.12.

Система функций Радемахера r k (0) является ортонормированной на интервале 0

Система функций Уолша является расширением системы функций Радемахера до полной системы и определяется как

где kf - значение j -го разряда в записи числа к в коде Грея. Например,

так как 5=>101 2 =>111 г. Графики первых четырех функций Уолша показаны на рисунке 4.13.

Рис. 4.13.

Функции Уолша обладают следующими свойствами:

• 1. wal k (®) = ± 1.
• 2. | wal k (0)| = 1, 2 = 1.
• 3. Функции Уолша являются периодическими wal k (©) = wal k (0 +1).
• 4. Функции Уолша являются ортогональными

5. Умножение функций Уолша дает функцию Уолша, но другого порядка wal k (0) wal n (0) = walj (0), j = к ® n ,

wal k (0 2) wal k (0 2) = wal k (0 3), 0 3 = 0j ® 0 2 , где © - сложение по модулю два.

В некоторых случаях используют функции Уолша вида

При использовании в качестве базисных функций системы функций Уолша сигнал можно представить в виде

Совокупность коэффициентов Уолша-Фурье {q} или {а к ф к } и совокупность порядковых номеров функций образуют спектр сигнала в базисе Уолша, который для краткости иногда называют S-спектром.

Например, сигнал, представляющий собой периодическую последовательность прямоугольных импульсов (рис. 4.14), имеет S-спектр, определяемый по выражению (4.39).

Рис. 4.14.

прямоугольных импульсов

Пусть п= 3, тогда получим S-спектр для данного случая, показанный на рисунке 4.15.

Рис. 4.15.

Таким образом, в отличие от обычного частотного спектра S-спектр последовательности прямоугольных импульсов оказывается конечным. Следует отметить, что сдвиг импульсов во времени приводит к изменению структуры S- спектра. В частности, появляются новые составляющие. Например, для последовательности из п= 3 импульсов, сдвинутой на 0=1/16, S-спектр имеет вид, как на рисунке 4.16, в то время как при использовании тригонометрической системы функций сдвиг во времени изменяет только фазовый спектр.

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

Рис. 4.16.

сдвинутых на 0=1/16

Система функций Хаара состоит из кусочно-постоянных функций har k (0), задаваемых на интервале 0

где т - номер старшего ненулевого разряда в двоичном представлении числа

к mod2 w - величина к по модулю 2 т, это наименьший остаток от деления числа к на 2 т . Графики нескольких функций Хаара даны на рисунке 4.17.

Рис. 4.17.

Если рассматривать спектр сигнала в базисе Хаара, то, как и в случае S- спектра, при сдвиге сигнала во времени меняется структура его спектра.

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