CDMA: сигналы и их свойства. Многостанционный доступ с кодовым разделением и сети CDMA Разложение сигналов по функциям уолша
Курс: Теория информации и кодирования
Тема: ДВОИЧНО-ОРТОГОНАЛЬНЫЕ СИСТЕМЫ БАЗИСНЫХ ФУНКЦИЙ
Введение
1. ФУНКЦИИ РАДЕМАХЕРА
2. ФУНКЦИИ УОЛША
3. ПРЕОБРАЗОВАНИЕ УОЛША
4. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ УОЛША
Список литературы
Введение
Широкое использование спектрально-частотного представления процессов при исследовании сигналов и систем (преобразование Фурье) связанно с тем, что при гармонических воздействиях колебания сохраняют свою форму при прохождении через линейные цепи (системы) и отличаются от входных только амплитудой и фазой. Это свойство используют ряд методов исследования систем (например, частотные методы).
Но при реализации алгоритмов, использующих преобразование Фурье на ЭВМ, необходимо выполнять большое количество операций умножения (миллионы и миллиарды), что занимает большое количество машинного времени.
В связи с развитием средств вычислительной техники и применения их для обработки сигналов широко используются преобразования, содержащие в качестве ортогонального базиса кусочно-постоянные, знакопеременные функции. Эти функции легко реализуются с помощью средств вычислительной техники (аппаратно или программно) и их использование позволяет свести к минимуму время машинной обработки (за счет исключения операции умножения).
К числу таких преобразований можно отнести преобразования Уолша и Хаара, которые широко используются в области управления и связи. В области компьютерной технике эти преобразования используются при анализе и синтезе устройств логического типа, комбинационных схем особенно использующих большие и сверхбольшие интегральные схемы (БИС и СБИС), содержащие сотни тысяч элементов, выполняющих различные логические функции. Преобразования Уолша и Хаара используют кусочно-постоянные функции Уолша, Радемахера, и др., принимающие значения ±1, либо Хаара, принимающие значения ±1 и 0 на интервале определения [-0,5, 0,5] либо .
Все эти системы взаимосвязаны и каждую из них можно получить как линейную комбинацию из другой (например: система Радемахера- составная часть системы Уолша). Обозначение функций связанных с авторами этих функций:
Уолша - Walsh - wal(n, Q),
Хаара- Haar- har(l, n ,Q),
Радемахера - Rademacher - rad(m, Q),
Адамара - Hadamard - had(h, Q),
Пели - Paley - pal(p, Q).
Все эти системы функции представляют собой системы двоично–ортогональных базисных функций.
1. Функции Радемахера
Функции Радемахера можно определить по формуле:
rad(m,Q) = sign, (1)
где 0 £ Q < 1 - интервал определения; m - номер функции; m = 0, 1, 2, ...
Для m = 0 функция Радемахера rad(0,Q) = 1.
Знаковая функция sign(x) определяется соотношением
Функции Радемахера это периодические функции с периодом 1, т. е.
rad(m,Q) = rad(m,Q+1) .
Первые четыре функции Радемахера показаны на рис. 1.
Рис. 1. Функции Радемахера
Дискретные функции Радемахера определяются дискретными значениями Q в точках отсчета. Например: Rad(2,Q) = 1, 1, -1, -1, 1, 1, -1, -1.
Функции Радемахера ортогональные, ортонормированные (3) но являются нечетными, а значит, не образуют полную систему функций, т. к. существуют и другие функции ортогональные функциям Радемахера (например: rad(m,Q) = sign) поэтому их применение ограничено.
(3)
Полными двоично-ортогональными системами базисных функций являются системы функций Уолша и Хаара.
2. Функции Уолша
Функции Уолша представляют собой полную систему ортогональных, ортонормированных функций. Обозначение: wal(n, Q) , где n - номер функции, при этом: n = 0, 1,... N-1; N = 2 i ; i = 1, 2,… .
Первые 8 функций Уолша приведены на рис. 2.
1
Рис. 2. Функции Уолша
Функция Уолша имеет ранг и порядок. Ранг –число единиц в двоичном представлении n. Порядок - максимальный из содержащих единицу номер разряда двоичного представления. Например, функция wal(5,Q) имеет ранг- 2 а порядок –3 (n = 5 Þ 101).
Функции Уолша обладают свойством мультипликативности. Это значит, что произведение любых двух функций Уолша также является функцией Уолша: wal(k,Q)wal(l,Q)= wal(p,Q), где p = k Å l. В связи с возможностью применения к функциям Уолша логических операций, они широко используются в многоканальной связи с разделением по форме (используется также временное, частотное, фазовое и т. д. разделение), а также аппаратуре формирования и преобразования сигналов на базе микропроцессорной техники.
Функции Уолша можно получить как произведение функций Радема-хера, номер которых соответствует коду Грея номера функции Уолша. Соответствия для первых 8 функций Уолша приведены в табл. 1.
Таблица 1
| N | Двоичный | Соотношения | |
| 0 | 000 | 000 | wal(0,Q)=1 |
| 1 | 001 | 001 | wal(1,Q)=rad(1,Q) |
| 2 | 010 | 011 | wal(2,Q)=rad(1,Q)×rad(2,Q) |
| 3 | 011 | 010 | wal(3,Q)=rad(2,Q) |
| 4 | 100 | 110 | wal(4,Q)=rad(2,Q)×rad(3,Q) |
| 5 | 101 | 111 | wal(5,Q)=rad(1,Q)×rad(2,Q)×rad(3,Q) |
| 6 | 110 | 101 | wal(6,Q)=rad(1,Q)×rad(3,Q) |
| 7 | 111 | 100 | wal(7,Q)=rad(3,Q) |
Существуют различные способы упорядочения функций Уолша: по Уолшу (естественное), по Пэли, по Адамару. Нумерация функций Уолша при различных способах упорядочения (n - по Уолшу; p - по Пэли; h - по Адамару) приведена в табл. 2.
При упорядочение по Пэли номер функции определяется, как номер двоичного кода Грея прочитанный, как обычный двоичный код. Такое упорядочение называется диадическим.
При упорядочение по Адамару номер функции определяется, как двоичное представление номера функции Уолша системы Пели, прочитанное в обратном порядке такое упорядочение называется естественным.
Таблица 2
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| p | 0 | 1 | 3 | 2 | 6 | 7 | 5 | 4 |
| h | 0 | 4 | 6 | 2 | 3 | 7 | 5 | 1 |
Как видно из таблицы, различные системы используют одни и те же функции Уолша в различной последовательности, которые равнозначны для представления сигналов, но отличаются только свойства разложения (например, функции Уолша - Пэли сходятся быстрее). При этом, каждому виду упорядочений соответствуют определенные формулы.
3. Преобразование Уолша
Рассмотрим спектральное представление сигналов с использованием базиса Уолша. Аналогично с рядом Фурье ряд Уолша имеет вид:
, (4)
где спектр Уолша
. (5)
Для проверки правильности расчета спектральных коэффициентов может быть использовано равенство Парсеваля
.
Если ограничиться N членами в разложении, то получим усеченный ряд Уолша:
,(6)
где t Î ; N=T/ D t; t = a D t при t ® ¥ a ® ¥ , a - сдвиг по оси;
wal(n,Q) после преобразования аргументов.
Для практических расчетов можно использовать формулу:
.
где: 
; (7)
r - ранг спектрального коэффициента с номером a (число двоичных разрядов числа a в которых имеются 1).
i - номер подынтервала определения функции x(t) ;
При этом Г i принимает значение ±1 или 0 в зависимости от того меняет ли W a (i/N) в точке i/N знак с "+" на "-",c "-" на " +" или знак не меняется.
Пример 1. Разложить функцию x(t) = at в ряд по упорядоченным по Пэли функциям Уолша при N=8, T=1, a=1.
Решение: Определим Ф(t):
.
Определим спектральные коэффициенты с учетом функций Уолша упорядоченным по Пэли по формуле (7)
C 0 = aT/2;
C 1 = -aT/2 + 0 +0 + 0 +2(aT/4) + 0 + 0 + 0 = -aT/4;
C 2 = -aT/2 + 0 + 4aT/64) + 0 - 16aT/64 + 0 +36aT/64 +0 =-aT/8;
C 3 = aT/2 + 0 + 4aT/64) + 0 + 0 + 0 - 36aT/64 +0 = 0;
C 4 =-aT/2 + aT/64 - 4aT/64 + 9aT/64 - 16aT/64 + 25aT/64 –
- 36aT/64 + 49aT/64 =-aT/16;
C 5 =C 6 =C 7 =0.
Ряд Уолша - Пэли имеет вид:
.
Аппроксимация функции x(t) = at при а=1 и t=1 полученным рядом приведена на рис. 3.
Рис. 3. Аппроксимация функции x(t)=at рядом Уолша – Пэли
4. Дискретное преобразование Уолша
Дискретное преобразование Уолша (ДПУ) производится при использовании дискретных функций Уолша W a (i/N) Þ Wal(n, Q) и выполняется над решетчатыми сигналами x(i) , при этом число отсчетов N должно быть двоично -рациональным, т. е. N = 2 n , где n = 1, 2,... , i - определяет номер точки дискретного интервала определения a = 0, 1,..., N-1 .
Формулы дискретного ряда Уолша имеют вид:
,(9)
где дискретный спектр Уолша
. (10)
Для проверки правильности расчета спектральных коэффициентов может быть использовано равенство Парсеваля:
(11)
График дискретной функции Уолша, упорядоченных по Пели приведен на рис.
Как было сказано выше, для объединения нескольких каналов при кодовом разделении каналов необходимо, чтобы псевдослучайные коды были разделимы с помощью корреляционного фильтра. Для этого они должны достаточно различаться. Степень подобия (похожести) функций в математике отображается с помощью корреляции. Различаются взаимная корреляция - сравнение двух функций, ортогональная корреляция - при полной независимости двух функций и автокорреляция - сравнение функции с собой при сдвиге во времени.
Для дискретных функций интегрирование можно заменить суммированием.
В системах многостанционного доступа с кодовым разделением каналов применяются ортогональные функции Уолша. Одним из необходимых (но не достаточных) свойств такого кода является его сбалансированность, т. е. одинаковое число нулей и единиц.
Заметим, что при кодировании обычно символ 0 заменяется на +1, а 1 на –1.
Рассмотрим пример вычисления ортогональности полученных функций. Разберем взаимную корреляцию (без сдвига) функций 
и 
.
Согласно полученному результату эти две функции ортогональны.
Однако ортогональные функции Уолша имеют недостатки. Система должна быть синхронизирована. При сдвиге синхронизации функции корреляция увеличивается.
Для сдвинутых по времени и несинхронизированных сигналов взаимная корреляция может быть не равна нулю. Они могут интерферировать друг с другом. Вот почему кодирование с помощью функций Уолша может применяться только при синхронном CDMA .
3.1.3. Неортогональные псевдослучайные функции
Неортогональные (асинхронные) псевдослучайные функции могут быть сгенерированы с применением сдвиговых регистров , сумматоров (сложение по модулю 2) и контуров обратной связи. Рис. 3.4 иллюстрирует такой принцип.
Рис. 3.4.
Максимальная длина последовательности определяется длиной регистра и конфигурацией цепи обратной связи (на рис. 3.4 цепи обратной связи обозначены , ). Регистр длиной битов может порождать свыше различных комбинаций нулей и единиц. Так как цепь обратной связи выполняет линейные операции, то если все регистры будут иметь нулевое значение, выход цепи обратной связи также будет нулевой. Поэтому, если установить все разряды на нуль, то цепь обратной связи будет всегда давать нулевой выход для всех последующих тактовых циклов, так что необходимо исключить эту комбинацию из возможных последовательностей. Таким образом, максимальная длина любой последовательности равна . Генерируемые последовательности называются последовательностями максимальной длины , или m-последовательностями . Основное свойство таких последовательностей: автокорреляционная функция m-последовательности имеет пик при нулевом сдвиге и малый уровень боковых выбросов в остальных случаях. Это позволяет более четко выделять каналы. Конфигурации обратной связи для m-последовательности сведены в таблицу и могут быть найдены в .
Последовательности, порождаемые регистрами сдвига , имеют еще много вариантов. В частности, известны последовательности Голда, порождаемые совокупностью двух регистров, последовательности Касами, порождаемые тремя регистрами, и т. д. [ , ].
Инженеры выбирали сигналы, применение которых должно улучшить основные характеристики систем (качество связи, помехоустойчивость), полагаясь лишь на свою интуицию. Поворотным моментом стало создание теории формирования, обработки и передачи сигналов. Она позволяет определить эффективность использования конкретного ансамбля (множества) сигналов, базируясь лишь на знании их авто- и взаимокорреляционных характеристик.
Базовые понятия
Кодовые последовательности, используемые в 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, который определяется как отношение квадратов синфазных составляющих сигнала к сумме квадратов его расфазированных составляющих. Таким образом, мерой эффективности апериодической корреляции двоичной последовательности является показатель качества.
М. Ю. Васильева, Ф. В. Коннов, И. И. Исмагилов
ИССЛЕДОВАНИЕ НОВЫХ УПОРЯДОЧЕНИЙ ДИСКРЕТНЫХ ФУНКЦИЙ УОЛША
И ИХ ПРИМЕНЕНИЕ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ УПРАВЛЕНИЯ
Ключевые слова: дискретные функций Уолша, разностно-упорядоченная система, обработка и передача данных,
автоматизированные системы управления.
Предлагается новый метод упорядочения систем дискретных функций Уолша, представлены свойства новых упорядочений, рассмотрена возможность применения синтезированных упорядочений дискретных функций Уолша в автоматизированных системах управления.
Keywords: discrete Walsh functions, difference-ordered system, processing and transfer data, automated control systems.
A new method of ordering systems of discrete Walsh functions, shows the properties of new orderings, possibility of application of the synthesized discrete orderings of Walsh functions in automatic control systems.
Введение
Повсеместное развитие информационных сетей и систем, включая автоматизированные системы управления (АСУ) различных уровней, вычислительные сети, системы автоматизированного проектирования, сбора и обработки данных, автоматизации эксперимента, массового
обслуживания, телеметрические комплексы, информационно-справочные системы, сети связи и др., привело к существенному росту информационных потоков между территориально распределенными источниками и получателями сообщений и хранению все возрастающих объемов информации различного вида в базах данных . Для повышения эффективности использования коммуникационных и информационно-вычислительных ресурсов указанных систем применяются различные методы и средства .
Среди них весьма важную роль играют методы сокращения избыточности данных, обеспечивающие сжатие объемов передаваемой или запоминаемой информации. Это позволяет значительно разгрузить каналы связи и системы обработки и хранения данных за счет исключения ненужных или дублирующихся сведений, что эквивалентно повышению пропускных способностей систем сбора, передачи и обработки данных или увеличению емкости запоминающих устройств.
Среди существующих методов сокращения избыточности данных особое место занимают методы сжатия, применяющие различные математические преобразования. Наиболее часто применяемыми при сокращении и передаче данных в автоматизированных системах управления производством и технологическими процессами являются
преобразования Фурье, Уолша и Хаара . Каждое из которых обладает рядом преимуществ, например, применение преобразований Уолша и Хаара позволяет значительно упростить и ускорить обработку информации.
Широкое использование ряда преобразований в прикладных задачах, заключается в возможности их вычисления посредством быстрых алгоритмов, которые обладают существенно меньшей
вычислительной сложностью по сравнению с классическими алгоритмами преобразований .
В статье рассматривается комплекс вопросов, связанных с применением преобразований Уолша: приводится построение новых упорядочений функций Уолша, исследование их свойств, рассматривается применение функций Уолша при выполнении преобразований.
Краткий обзор дискретных функций Уолша и их упорядочений
Ортонормированная, полная система прямоугольных функций была введена Уолшом. В отличие от тригонометрических гармоник, по которым функция раскладывается в классический ряд Фурье, функции Уолша представляют собой прямоугольные волны, которые во многих задачах обработки сигналов предпочтительнее
синусоидальных волн. В большей степени это связано с простым видом функций Уолша, каждая из которых принимает всего два значения (+1 и -1), что намного упрощает их реализации на ЭВМ.
Дискретные преобразования Уолша (ДПУ) основываются на дискретных функциях Уолша (ДФУ), которые образуются равномерными выборками непрерывных функций Уолша. Общее количество отчетов в ДФУ должно быть N = 2п, где п - любое целое положительное число.
В цифровой обработке сигналов используются преобразования в различных
упорядочениях систем ДФУ. К наиболее известным упорядочениям в практике обработки сигналов ДФУ в системе относятся следующие: секвентивное упорядочение (Уолша-Качмажа); диадическое
упорядочение (Уолша-Пэли); упорядочение в
соответствии с расположением строк в матрице
Адамара (Уолша-Адамара).
Беря за основу системы непрерывных функций Уолша с различным порядком следования функции, получаем соответственно матрицы ДПУК (дискретные преобразования Уолша-Качмажа), ДПУП (дискретные преобразования Уолша-Пэли) и ДПУА (дискретные преобразования Уолша-Адамара).
ДФУ можно описать аналитически, выразив их через дискретные функции Радемахера. Пусть
j = £ ік2 - номер функции в системе, а і = £ ік2 к=0 к к=0 К
Номер отсчета, тогда упомянутые выше матрицы преобразований имеют вид:
Матрица ДПУК
матрица ДПУП
(- 1)к £ 0ік^к(і)
(- 1)к£ 0ікіп-к
матрица ДПУА
(- 1)к£ 0ікік
где -т= - нормировочный коэффициент; л/И
РоШ = Ь = ^п-к+1 ф-!п-к’ к =1,2 п,
где ® - знак сложения по модулю 2.
Отметим, что двоичные комбинации вида
Ч0(-).Ч1С-)...Рп(-) или Рп(-),Рп-1(-), -,Р0(-)
называют соответственно кодом Грея, или инверсным кодом Грея числа -
Для матриц Уолша-Адамара справедливо следующее разбиение на подматрицы вид
Реккурентную формулу (4) можно также выразить в виде кронекеровского произведения матриц:
НАР к = НАР 0 НАР к 1 . 2к 2 2к-1
Матрицы (1-2) можно получить переупорядочением строк матрицы Уолша-Адамара, так как между упорядочениями дискретной системы Уолша размерности N существуют определенные зависимости, которые в матричной форме имеют следующий вид:
РАЬм = Б^НАР^
WALN = Б^РАІ.
матрица двоично-инверсных перестановок;
Матрица перестановки по обратному двоичному коду Грея.
Приведем в краткой форме основные свойства ДФУ. Для ДФУ справедливы следующие свойства, присущие непрерывным функциям Уолша:
1. Ортогональность. Функции Уолша
ортогональны на интервале , и наоборот.
6. Мультипликативность. Произведение двух функций Уолша равно новой функции Уолша из этой же системы.
7. Порядок и ранг функций Уолша. Функции Уолша удобно характеризовать двумя параметрами, связанными с двоичным представлением их номеров. Первый из них определяет максимальный номер ненулевого двоичного разряда числа - и называется порядком р; второй - ранг функции Уолша г - показывает число двоичных разрядов, в которых число Ш имеет единицы. Номер функции Уолша г-го ранга условно обозначают в виде -(г) и записывают в десятичной системе счисления:
где ^к (к = 1,2,...,г) - номер разряда двоичного кода Ш, содержащий единицу. Область изменения всех ^к в (8) должна удовлетворять следующей системе равенств:
М1 = 0,1,..., п - г -1;
М 2 = И + 1, . ., п _ г;
Для ранга и порядка функций Уолша справедливо следующее свойство: ранг
произведения функций Уолша не превосходит суммы их рангов; порядок произведения не превышает максимальный из порядков сомножителей. Справедливость этого свойства следует из свойств суммирования по модулю 2.
В системы ДФУ отнесены к классу моноразностных дискретных ортогональных базисов. При изучении ряда свойств базисов этого класса весьма полезны их параметры и характеристики, подробно рассмотренные в данной работе. Подход к их введению основан на том, что любой коэффициент преобразования в рассматриваемом классе базисов может быть представлен в виде взвешенной суммы конечных разностей соответствующих порядков
преобразуемого вектора £
р(і)= £ і = 0,М -1,
где Р(I) - I -ый коэффициент преобразования; Дк -оператор конечной разности к-го порядка;
ы(|,-) = ы(|,Ы-1 -^ -Ш) - 1-я весовая функция; d| -
некоторое целое число.
В этом случае базисные векторы моноразностных дискретных базисов формируются последовательностями операторов конечной разности соответствующих порядков. В дальнейшем в работе будем оперировать параметром, названным дифференциальным порядком базисной функции d|,
под которым будем подразумевать порядок операторов конечной разности, формирующих эту функцию.
Отметим, что дифференциальный порядок конкретной функции Уолша связан с ее структурными свойствами и не зависит от места расположения в системе, то есть от упорядочения базисных функций.
Важными являются также следующие свойства:
8. Для систем ДФУ, упорядоченных по Адамару и Пэли, дифференциальные порядки функций равны
Следовательно,
их рангам: количество
С = гкі, і = 0,М-1.
(к = 0,п) чк
дифференциального порядка равно величине Сп -числу сочетаний из п по к.
9. Известное свойство разложений дискретных степенных полиномов по системе Уолша-Пэли , которое можно переформулировать следующим
образом: спектр дискретного полинома к-ой (к = 0,п) степени содержит компоненты, соответствующие базисным функциям не выше к-ого
дифференциального порядка. Отметим, что аналогичное утверждение будет справедливо и для разложений по системе Уолша-Адамара.
10. Спектральные коэффициенты сигналов, достаточно хорошо описываемых дискретными степенными полиномами невысоких порядков, в пределах групп, соответствующих базисным функциям Уолша-Пэли одного дифференциального порядка, убывают по абсолютной величине с ростом их порядковых номеров.
Синтез разностно-упорядоченной системы дискретных функций Уолша
Предлагаемый метод упорядочения систем
ДФУ размерности N = 2п заключается в следующем. Строится разбиение множества порядковых номеров функций Уолша исходной системы I = {0,1 N -1}
на (п +1) подмножеств, каждое из которых включает номера функций с одинаковыми дифференциальными порядками.
|(0) = {0}, і = 0 ,
І(і) = {2М + 2М2 +... + 2М: м1 = 0,п - і,
^2 - +1,п - I +1,...^| - ^| 1 +1,п - 1}, I - 1,п - 1,
1(п) - {2п - 1}, I - п.
Затем сформированные подмножества располагают в порядке увеличения дифференциальных порядков соответствующих функций, то есть в итоге получаем множество Л - ЦЛ^.-Лп}, для которого
справедливы следующие соотношения: Л п и: - 0 и Л - Сп,1 - 0,п.
Очевидно, что множество и определяет перестановку функций Уолша в системе |0 1 ... N - 1]
Полученная в результате этой перестановки система ДФУ будет характеризоваться тем, что функции в ней располагаются группами в порядке возрастания их дифференциальных порядков. По этой причине назовем эту систему ДФУ разностноупорядоченной.
Для вектора перестановочной
последовательности будем придерживаться
обозначения Рп = (Р0,Р1....Рм-1) , где
р| - ш|,1 - 0^-1. Перестановку с использованием
этого вектора назовем перестановкой по дифференциальным порядкам базисных функций (кратко Б-перестановкой).
Рассмотрим упорядочение системы Уолша-Пэли с использованием предложенного метода. Анализ дифференциальных порядков функций Уолша-Пэли показал, что вектор Рп может быть представлен в виде объединения ряда подвекторов:
Рп - (рп0),рп1),рп2),.,рпп)) , (13)
Рп,к = 1,п-1, - подвекторы,
рекуррентными соотношениями: Рі(к)= |(2і -1), і=к,
Рі(і) = (2і - 1),і = 1, п;
определяемые
^(Р-к), 2і-1 + Р,- 1)),і = к +1, п,
Векторы Рп размерности N - 2п,п -1,5 , соответствующие перестановочным
последовательностям, представлены в табл. 1.
Сверху подчеркнуты группы
коэффициентов четных, а снизу - нечетных дифференциальных порядков.
Таблица 1 - Векторы значений перестановочной последовательности
п Вектор Рп
3 {0,1,2,4,3,5,6,7}
4 {0,1,2,4,8,3,5,6,9,10,12,7,11,13,14,15}
5 {0,1,2,4,8,16,3,5,6,9,10,12,17,18,20,24, 7,11,13,14,19,21,22,25,26,28,15,23,27,29,30,31}
С учетом введенного вектора значений перестановочной последовательности разностно-
упорядоченную систему ДФУ {РЦ^0)}(=о можно описать так:
pldN(i) = palN(pj), i = 0,N
где раі^(і) - і-я функция Уолша-Пэли.
S^PAL ^ , (І6)
Матрица D-перестановок,
элементы которой формируются так:
[о, в остальных случаях.
Следует отметить, что представленное выше упорядочение системы ДФУ получено на основе системы Уолша-Пэли. Выбор в качестве базисной системы Уолша-Пэли обусловлен легкостью
получения аналитического описания для перестановочной последовательности и матричного соотношения, формирующего предложенное упорядочение системы ДФУ.
Различные варианты разностно-
упорядоченных систем могут быть получены при выборе в качестве базисной других систем Уолша. Анализ дифференциальных порядков функций Уолша-Адамара и Уолша-Пэли показал, что вектор значений перестановочной последовательности Рр при выборе в качестве опорных матриц Уолша-Адамара также может быть представлен в виде объединения ряда подвекторов (13-14) - (табл. 2).
На основе полученного вектора значений перестановочной последовательности разностно-
описать так:
упорядоченные системы ДФУ
hddN ()= hadN (pj)i = 0,N -1
где hadN (0 - соответственно 1-е функции Уолша-Адамара.
Таблица 2 - Группы дифференциальных порядков систем Уолша-Пэли и Уолша-Адамара при N=8
j hadn,j PALn,j di pj pldn ,j di
О ООО ООО О О ООО О
І ООІ ІОО І 4 ІОО І
2 ОІО ОІО І 2 ОІО І
3 ОІІ ІІО 2 І ООІ І
4 ІОО ООІ І 6 ІІО 2
З ІОІ ІОІ 2 З ІОІ 2
6 ІІО ОІІ 2 3 ОІІ 2
7 ІІІ ІІІ 3 7 ІІІ 3
Матричная запись для введенной системы ДФУ имеет следующий вид:
Например, явный вид матрицы HDDN для N = 2 имеет следующий вид:
11 1 1 1 1 1 1 0
1 -1 1 -1 1 -1 1 -1 1
11 -1 -1 1 1 -1 1
1 1 1 1 -1 -1 -1 1
1 -1 -1 1 1 -1 1 2
1 -1 1 -1 -1 1 1 2
1 -1 -1 1 1 -1 1 2
1 -1 -1 1 -1 1 1 -1 3
дифференциальный порядок базисной функции, расположенной в соответствующей строке матрицы.
Точная оценка М общего числа разностноупорядоченных систем ДФУ при условии, что группы базисных функций будут располагаться в порядке повышения их дифференциальных порядков, может быть определена по следующей формуле:
М =П (СП!). (18)
В работе рассмотрена возможность получения матричной записи другого варианта разностно-упорядоченной системы ДФУ. При этом используется послойно-кронекеровское
произведение матриц.
Остановимся на вопросе нумерации разностно-упорядоченных ДФУ в системе. Здесь в ряде случаев удобнее оперировать двухзначной индексацией базисных функций. Например, для рассмотренных в работе систем ДФУ она вводится следующим образом:
pld2n(i) = pld2n(l,j), i = 0,N -1, i = bnl-1 + j, l є {0,1,..., n) j є{,1,...,сП -1}.
Очевидно, что индекс l равен дифференциальному порядку базисного вектора, а индекс j - его порядковому номеру в соответствующей группе. Соотношение, описывающее зависимость между двумя видами индексации, не зависит от варианта разностноупорядоченной системы ДФУ.
Заметим, что матрицы PAL^, и DOWN
совпадают для N=2,4, а PLD^ = DOWN для N=8.
Свойства разностно-упорядоченных систем дискретных функций Уолша
свойства
отдельные введенным упорядочениям
Рассмотрим преобразований по систем ДФУ.
1. Для разностно-упорядоченных систем ДФУ
справедливы свойства ДФУ 1-7.
2. Известное свойство 8 (разложение дискретных
степенных полиномов по системе Уолша-Пэли и Уолша-Адамара) применительно к рассматриваемым разностно-упорядоченным системам ДФУ можно
сформулировать следующим образом: спектр
дискретного полинома к-ой (к = 0,П) степени разлагается по базисным функциям не выше к-ой группы.
Рассматриваемое свойство в случае
упорядочения функций Уолша-Пэли можно записать в виде следующего соотношения:
р(|,|) = 0,1> к, (20)
где Р(и)= £ 10(,и)
3. Немаловажным является свойство 9, которое
также справедливо для разностно-упорядоченных систем ДФУ: спектральные коэффициенты сигналов, достаточно хорошо описываемых дискретными
степенными полиномами невысоких порядков, в пределах групп, соответствующих базисным функциям одного дифференциального порядка, убывают по абсолютной величине с ростом их порядковых номеров.
Полученные при этих упорядочениях матрицы функций Уолша являются несимметрическими,
исключением являются тривиальные случаи матриц для порядков N = 2, 4.
4. Отметим следующее свойство, спектры
дискретных степенных полиномов низких порядков в базисах разностно-упорядоченных ДФУ
характеризуются большей степенью локализации ненулевых компонент в их начальных участках
Проиллюстрируем характер распределения ненулевых компонент спектров дискретных степенных полиномов 1(1) к-ой (к = 1,2) степени для N=16 в
базисах различных систем ДФУ.
Предварительно введем индикаторный вектор спектра Б = (зо^...^^-), определяя его элементы так
Б| = |0, р(|)=о, (21)
где Р(1) - ьый коэффициент преобразования. Одномерные дискетные степенные полиномы 10) определяются функциями вида
f(j) = Е аі]", ] = 0,Ы-1, к є г,
1 = {0,1, ... ,м -1}.
При выборе моделей сигналов часто ограничиваются полиномиальной моделью малых степеней (к є г 5). Это обусловлено тем, что ею
может быть эффективно описан широкий класс реальных сигналов на конечных интервалах.
Формулы расчета коэффициентов преобразования Р(і) одномерного полиномиального сигнала в матричном виде будут иметь следующий вид:
где - матрица ДПУ в используемом упорядочении ДФУ;
1 = |г(|), | = оТы -1} - вектор исходных данных;
Р = р(1), I = 0^ -11 - вектор спектральных
коэффициентов, Т - знак транспонирования.
Индикаторные векторы спектров в базисе Уолша-Адамара, Уолша-Качмажа, Уолша-Пэли и разностно-упорядоченных ДФУ для полиномов степени к=1 и к=2 имеют вид:
(1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0) - для базиса Уолша-Адамара;
(1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1) - для базиса Уолша-Качмажа;
(1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0) - для базиса Уолша-Пэли;
(1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0) - для базиса
разностно-упорядоченных ДФУ.
(1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,0) - для базиса Уолша-Адамара;
(1,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1) - для базиса Уолша-Качмажа;
(1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,0) - для базиса Уолша-Пэли;
(1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0) - для базиса
разностно-упорядоченных ДФУ.
Проиллюстрируем характер распределения ненулевых компонент спектров дискретных степенных двумерных полиномов 1(1, ] к-ой (к = 1,2) степени для N1* N2=8x8 в базисах ДФУ. Двумерные дискретные степенные полиномы, определяют функциями вида
Ш) = X X араір]а,
где I = 0,^ -1,] = 0,^ -1, к е 2^1,
^ -1 = {о,1, ^ - 1} .
При этом ограничимся двумерными полиномиальными моделями низких степеней ввиду того, что они являются основой ряда алгоритмов цифровой обработки сигналов.
Приведем формулы прямого
преобразования двумерного полиномиального сигнала в векторно-матричной форме:
Р = HNTfHN, (25)
где 1 = {1(1,]), I = 0,^ -1,] = 0,^ -1} - матрица
исходных данных;
Р = "Р(И),1 = 0,^ -1, ] = 0^2 -1} - матрица
спектральных коэффициентов.
Индикаторные векторы спектров для рассматриваемых случаев при к=1 показаны на рис. 1,
1 I 1 I о I 1 I □ I □ I □ I 1
00000000 1 0 0 0 0 0 0 0
00000000 1 0 0 0 0 0 0 0
Рис. 1 - Индикаторные векторы спектров при к=1 в базисе: Уолша-Адамара, Уолша-Качмажа
00000000 00000000 00000000 00000000
Рис. 2 - Индикаторные векторы спектров при к=1 в базисе: Уолша-Пэли, разностно-упорядоченных
Индикаторные векторы спектров для рассматриваемых случаев при к=2 показаны на рис. 3,
11111110 1110 10 0 0 1110 10 0 0 1 0 0 0 0 0 0 0 1110 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 00000000
Рис. 3 - Индикаторные векторы спектров при к=2 в базисе: Уолша-Адамара, Уолша-Качмажа
1 I 1 I 1 I 1 I 1 I 1 I 1 I о
Рис. 4 - Индикаторные векторы спектров при к=2 в базисе: Уолша-Пэли, разностно-упорядоченных
Из этих примеров видно, что спектры дискретных степенных полиномов низких порядков в базисах разностно-упорядоченных ДФУ
характеризуются большей степенью локализации ненулевых компонент в их начальных участках. Полученные свойства преобразований по разностноупорядоченным системам ДФУ имеют важное значение для их приложений в системах управления и системах связи.
1 0 □ 0 0 0 0 0
1 0 0 □ 0 0 □ 0
□ 0 0 □ 0 0 □ 0
Применение синтезированных упорядочений дискретных функций Уолша в АСУ
Успешному использованию преобразований Уолша в области управления и связи способствовало изучение следующих вопросов: свойства функций Уолша; свойства спектров Уолша; общие вопросы применения функций Уолша при выполнении преобразований; алгоритмы быстрого преобразования Уолша; вычисление корреляционных функций и выполнение сверток на базе функций Уолша; применение функций Уолша для исследования случайных процессов; использование функций Уолша при построении цифровых фильтров.
Благодаря общим свойствам 1-7 с известными ДФУ (в упорядочениях Уолша-Качмажа, Уолша-Пэли, Уолща-Адамара) синтезированные разностно-упорядоченные
системы ДФУ могут найти эффективное применение в области автоматического управления технологическими процессами. Например, является актуальным применение преобразований Уолша при анализе динамики линейных и нелинейных систем, разработке систем оптимального управления, моделировании процессов, идентификации объектов, разработке ряда специальных устройств автоматики .
Практически важным для АСУ является предоженное X. Хармутом использование функций Уолша для формирования сигналов, передаваемых по линиям радиосвязи . Функции Уолша применены при разработке многоканальных систем связи, в которых одновременно передаются различные сигналы по каждому каналу связи. Использование разностно-упорядоченных систем ДФУ (свойство 2) позволит обеспечить многопотоковую обработку данных, при этом каждый поток будет включать элементы группы трансформант соответствующего
дифференциального порядка, что значительно ускорить обработку данных.
В настоящее время для решения многих задач в АСУ технологическими процессами и производством применяется вейвлет-
преобразование. Например, в ОАО "Татнефть" вейвлет-преобразование испольуется для подавления шумов и сжатия массивов данных с глубинных манометров , или при передаче динамограмм полученных с датчиков динамометрирования на диспетчерский пункт . Во многих случаях недостаточная степень сжатия данных при выполнении ДПУ сдерживает широкое применение данных преобразований. Свойство 2 полученное для разностно-упорядоченных систем ДФУ позволит значительно увеличить степень сжатия данных и способствует применению в перечисленных выше задачах.
Одной из важных задач в АСУ является задача передачи данных по каналам связи. При этом широкое распространение получили 8СЛЭЛ-
системы. Известны также решения, в которых функции 8СЛЭЛ-системы реализованы с помощью интернет-программирования, в ОАО «Газ-Сервис» (Республика Башкортостан) внедрены в эксплуатацию несколько автоматизированных систем дистанционного мониторинга оборудования газораспределительной сети . Для передачи данных по сети эффективное применение могут найти разностно-упорядоченные системы ДФУ (свойство 4).
В работе авторами были предложены алгоритмы с использованием преобразований Уолша и сравнительный анализ их эффективности. Использование в представленных алгоритмах для передачи данных разностно-упорядоченных систем ДФУ позволит обеспечить последовательную передачу потоков выходных данных при высокой скорости обработки и передачи данных по сети.
Полученные свойства новых упорядоченний дискретных функций Уолша имеют важное значение для их приложений в системах управления и системах связи. Синтезированные разностно-упорядоченные
Пол Фейерабенд (р. 1924).
Томас Кун (р. 1922).
Имре Лакатош (1921–1974).
Функции Уолща являются естественным расширением системы функций Радемахера, получены Уолшем в 1923 г. и представляют полную систему ортонормированных прямоугольных функций.
Множество функций Уолша, упорядоченных по частости, обычно обозначают следующим образом:
Функции Уолша, упорядоченные по частости, аналогично тригонометрическим функциям можно подразделить на четные cal(i,t) и нечетные sal(i,t)
| (17.3) |
На рисунке 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) по формуле:
| (17.4) |
где 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
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
| р | р 1 | р 2 | р 3 | 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б.
| wal h (0,x)=wal w (0,x); wal h (2,x)=wal w (3,x); wal h (4,x)=wal w (1,x); wal h (6,x)=wal w (2,x); | wal h (1,x)=wal w (7,x); wal h (3,x)=wal w (4,x); wal h (5,x)=wal w (6,x); wal h (7,x)=wal w (5,x). | (17.9) |