Всем доброго дня.
Не подскажет ли кто, где взять хорошие функции Уолша с большим кол-вом элементов (ну там 1024, 2048, и более). Под хорошими понимаю практически нулевую корреляцию между функциями. Длинные потому, что нужно их много - порядка 1000. Вообще это реально?

MATLAB

hadamard(1024)

Вроде бы функции Уолша в явном виде не генерят, а используют алгоритм в виде бабочки (Быстрое Преобразование Уолша), где в определенных местах уже стоят нужные знаки сложения и вычитания. На плюс на +1 и -1, конечно же, никто не множит. Ну, а после того, как log₂N этапов будут пройдены, в массиве накопится то, что должно получиться.

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

генерят. Пусть нужен i-ый бит j-ой последовательности Уолша-Аадамара длины 2^N:

b = parity(j AND i). parity рассчитывает mod2 сумму N-1 бит аргумента. информация например здесь. Вероятно, есть и лучшая ссылка, но на ум она не приходит в 3 часа ночи :-). Ключевые слова: walch sequence generation with counter

Вот мой код на с++, может станет понятнее:

//generates single i-th bit of walch-hadamard sequence of length N

template<int N>
class WalchSequence
{
//log2 of sequence length
static_assert(N > 0, "WalchSequence: N shall not be negative.");
static_assert((1<<(misc::SignificantBits<N-1>::n)) == N, "WalchSequence: N shall be power of 2.");

template<int L>
friend typename std::enable_if<L!=1, bool>::type get_walch_element(unsigned int ix, unsigned int i)
{
const int l2 = misc::SignificantBits<L-1>::n;
return (compute_parity<l2>(ix & i) != 0);
}


template<int L>
friend typename std::enable_if<L==1, bool>::type get_walch_element(unsigned int ix, unsigned int i)
{
return false;
}

public:
bool operator()(int seq_ix, int ix) const {return get_walch_element<N>(seq_ix,ix);}
};


Сообщение отредактировал andyp - Jul 18 2013, 23:31

Спасибо всем за ответы!

Правильно ли я понимаю, что если я сгенерю тем же матлабом



тысячу разных кодов длиной 4096, просуммирую, например, 998 из них, то корреляцией однозначно (и достаточно достоверно) смогу определить, каких двух функций из 1000 в этой сумме нет?

Так они же взаимно ортогональны, зачем суммировать? Просто берете любую интересующую вас функцию из базиса Уолша и определяете ее корреляцию с вашими данными (сумму поэлементных произведений). Если нуль получится, то своего вклада эта функция не дает. А если надо найти все отсутствующие, то придется этим же способом все функции базиса Уолша по очереди тестировать.

Это легко проверить в том же матлабе

hadamard(8)*hadamard(8)'/8

получим единичную матрицу

еye(8)

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



да, так и хотел сделать, только не все, а те, которые задумал использовать.

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

Чтоб было понятно, хочу использовать длинные функции для связи в радиоканале (аля CDMA), только скорость каждого канала очень низкая (длинные последовательности) и каналов надо порядка 1000.

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

Ну а если я на каждый отсчет последовательности буду делать скажем 8..16 выборок входного сигнала, синхронизация я так понимаю не нужна?

Это не влияет, малейший сдвиг по времени, частоте между последовательностями ведёт к потере ортогональности.

Ну как не влияет? Можно ведь и 1000 сэмплов на отсчет последовательности сделать... Всяко должно зависеть. Ну и полная ортогональность мне вообще-то без надобности, лишь бы значительно отличалась КФ при наличии и при отсутствии функции уолша.