Jump to content

    
Rst7

Последовательности с хорошей АКФ длины 2^N

Recommended Posts

Доброго времени суток.

Допустим, есть LFSR. АКФ его выходной последовательности в некотором смысле хороша - она содержит только один пик.

Однако ее длина 2^N-1.

И теперь вопрос. Как создать последовательность с хорошей АКФ (в описанном выше смысле), но при этом чтобы ее длина была 2^N. Понятное дело, что можно, например, просто добавить один нолик в последовательность. Да, АКФ ухудшится, появятся боковые лепестки. Но может быть есть научно правильный способ добавления этого нолика с лучшим результатом? Или вообще другой способ генерации такой последовательности?

Share this post


Link to post
Share on other sites
36 minutes ago, Rst7 said:

Как создать последовательность с хорошей АКФ (в описанном выше смысле), но при этом чтобы ее длина была 2^N.

А у Голея 32, 64, 128 вроде один пик в Матлабе, правда не знаю АКФ ли при этом...

 

wlanGolaySequence

Share this post


Link to post
Share on other sites
16 hours ago, _4afc_ said:

А у Голея 32, 64, 128 вроде один пик в Матлабе, правда не знаю АКФ ли при этом...

Там хитро. Там у суммы АКФ двух последовательностей хорошее поведение. Но это не совсем то, что мне нужно.

1 hour ago, Cianid said:

Из LFSR не сделать период больше чем 2^N-1. Мы ведь не можем в качестве seed использовать 0. 

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

Но может быть есть какой-то более толковый способ?

Share this post


Link to post
Share on other sites
1 час назад, Rst7 сказал:

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

За давностью лет уже забылось, по-моему, в стандарте IS-95 было прямо написано, что надо добавлять один ноль к максимальной последовательности нулей. Генератор длинного кода имел полином 42 степени, после 41 нуля вставлялся ещё один. С генераторами I и Q то же самое.

Share this post


Link to post
Share on other sites
1 hour ago, Rst7 said:

Но может быть есть какой-то более толковый способ?

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

Share this post


Link to post
Share on other sites
3 hours ago, soldat_shveyk said:

LFSR удобен тем, что можно не хранить последовательность, а генерить по известному закону. 

И не только этим. :)

 

Wiki:

Quote

Периодическая АКФ любой М-последовательности имеет постоянный уровень боковых лепестков, равный -1/N.

 

Кон и Лемпель (1977) обнаружили взаимоотношение между М-последовательностями и преобразованием Адамара, благодаря чему стало возможным вычисление автокорреляционной функции М-последовательности с помощью быстрого алгоритма наподобие БПФ.

 

Share this post


Link to post
Share on other sites
15.06.2021 в 19:49, _4afc_ сказал:

А у Голея 32, 64, 128 вроде один пик в Матлабе, правда не знаю АКФ ли при этом...

Там АКФ все верно:)

wlanGolaySequence

 

 

Edited by GrishaRezn

Share this post


Link to post
Share on other sites
1 hour ago, GrishaRezn said:

Там АКФ все верно:)

АКФ, но не совсем последовательности.

	[Ga,Gb] = wlanGolaySequence(32);
	figure stem(xcorr(Ga)+xcorr(Gb))
	

 

И даже подписано, что The sum of the autocorrelations is a dirac delta function.

Share this post


Link to post
Share on other sites
7 minutes ago, Rst7 said:

АКФ, но не совсем последовательности.

 


	[Ga,Gb] = wlanGolaySequence(32);
	figure stem(xcorr(Ga)+xcorr(Gb))
	

 

 

И даже подписано, что The sum of the autocorrelations is a dirac delta function.

Почему нельзя пропустить через канал только Ga или [ Ga Gb ] ?

Share this post


Link to post
Share on other sites
5 minutes ago, _4afc_ said:

Почему нельзя пропустить через канал только Ga или [ Ga Gb ] ?

Только Ga (или только Gb) не сильно отличается по критерию от m-последовательности с добавленным нулем. Кажется с нулем даже лучше выходит, но я перепроверю.

А идея пропустить [ Ga Gb ] - это в смысле последовательно?

7 hours ago, soldat_shveyk said:

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

Представляете себе объем вычислений хотя бы для 2^7? Ну в смысле полного перебора, случайно получить хорошую последовательность - очень малая вероятность.

Share this post


Link to post
Share on other sites
29 minutes ago, _4afc_ said:

Да. А что нельзя?

Надо попробовать, что там с АКФ такой последовательности получится, интересно.

Share this post


Link to post
Share on other sites
21 час назад, Rst7 сказал:

Надо попробовать, что там с АКФ такой последовательности получится, интересно.

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

Edited by GrishaRezn

Share this post


Link to post
Share on other sites

@Rst7 а вам обязательно нужна последовательность с алфавитом {-1, 1}? Существуют полифазные последовательности с идеальной периодической АКФ и довольно хорошей апериодической АКФ. Например, те же последовательности Задова-Чу: https://en.m.wikipedia.org/wiki/Zadoff–Chu_sequence

https://www.ieee802.org/16//tge/contrib/C80216e-04_241r1.pdf

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.