Спасибо за обратную связь! Честно говоря, давно не касался этой темы, но могу предположить, что в кодах Рида-Соломона разработчиков систем все-таки смущает довольно долгое плато в BER характеристике. Возможно, есть еще какие-то глубинные проблемы, замеры BER иногда не дают прямого ответа, соглашусь. Кстати, тренд на замещение RS на LDPC - это тренд, в том числе, и космической связи (см. DVB-S2) - может быть, какие-то более детальные исследования есть в этом русле.
Раньше это считали неизбежным злом технологии и все мечтали, что когда-нибудь в Wi‑Fi появится OFDM (ортогональное частотное разделение спектра), при использовании которого жёсткой очереди нет.
Наверное, вы все-таки имели в виду OFDMA (Orthogonal Frequency-Division Multiple Access). OFDM на физическом уровне в IEEE 802.11 был почти всегда.
В качестве развития темы: в общем-то, в питоновской heapq.heapify тоже заявлена O(N) ("linear time"). И судя по исходным кодам (поправьте если ошибаюсь), как раз обсуждаемый нами алгоритм (heapify хотя и использует функцию _sifup, сама _siftup внутри использует в конечном итоге _siftdown).
Сложнее определить время работы алгоритма. Чтобы построить исходную кучу, ему приходится прибавлять каждый элемент к растущей куче. Всякий раз он размещает его в конце дерева и просматривает структуру данных до самого верха, чтобы убедиться, что она является кучей. Поскольку дерево полностью бинарное, количество его уровней равно O(log N). Таким образом, передвижение элемента вверх по дереву может занять максимум O(log N) шагов. Алгоритм осуществляет шаг, при котором добавляется элемент и восстанавливается свойство кучи, N раз, поэтому общее время построения исходной кучи составит O(N log N).
Для завершения сортировки алгоритм удаляет каждый элемент из кучи, а затем восстанавливает ее свойства. Для этого он меняет местами последний элемент кучи и корневой узел, а затем передвигает новый корень вниз по дереву. Дерево имеет высоту O(log N) уровней, поэтому процесс может занять O(log N) времени. Алгоритм повторяет такой шаг N раз, отсюда общее количество нужных шагов — O(N log N).
Суммирование времени, необходимого для построения исходной кучи и окончания сортировки, дает следующее: O(N log N) + O(N log N) = O(N log N).
[Стивенс, Р., 2016. Алгоритмы. Разработка и применение. М.: Издательство "Э". - С. 148]
и Вирта:
[Вирт Н. АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ. М.Мир 1989 - С. 112]
как-то даже не возвращался к вопросу, спасибо за уточнение!
Соглашусь, что нужно было добавить "в худшем случае".
Могу посоветовать освежить в памяти следующие темы:
— Импульсная характеристика (link);
— Дискретное преобразование Фурье (ссылка);
— Теорема Парсеваля (ссылка).
Доброго времени суток! Сейчас работаю инженером-программистом по смежным с беспроводной связью проектам и учусь в аспирантуре. Раньше работал в одном из операторов связи.
Что означает «оценка частот суммы комплексных экспонент»? Значит ли это, как в преобразовании Фурье, мы хотим найти частоты, которые составляют исходный сигнал?
— да, MUSIC — это один из методов спектрального анализа. По этому поводу могу посоветовать почитать Hayes M. H. Statistical digital signal processing and modeling. – John Wiley & Sons, 2009. глава 8 "SPECTRUM ESTIMATION".
А можете порекомендовать какой-нибудь материал, где, собственно разжевывается почему и как из исходной ковариационной матрицы с помощью собственных значений(или собственного подпространства) мы получаем подпространство сигнала и шума в частном случае?
Доброго времени суток! Да, вы правы, связаны: многолучевое распространение, например, ведет к возникновению, так называемой, межсимвольной интерференции (ISI — Intersymbol Interference) , а это и есть наши быстрые замирания, ведущие к частотной селективности канала.
Небольшой ответный комментарий:
По поводу RootMUSIC я и не предполагал «сэкономить» на вычислениях собственных векторов — основная разница между MUSIC и RootMUSIC, насколько я понимаю, состоит в способе нахождения оных.
Haykin S. S., Liu K. J. R. Handbook on array processing and sensor networks. – New York: Wiley, 2009. – c. 51-52.
Да, это в большей степени вопрос теории; на практике, как вы правильно, отметили достаточно найти пики (максимумы), а уж спект перед нами или псевдоспектр — дело не самое важное. Поправьте, если я не прав — честно признаюсь, с RootMUSIC я знаком шапочно.
Спасибо за обратную связь! Честно говоря, давно не касался этой темы, но могу предположить, что в кодах Рида-Соломона разработчиков систем все-таки смущает довольно долгое плато в BER характеристике. Возможно, есть еще какие-то глубинные проблемы, замеры BER иногда не дают прямого ответа, соглашусь. Кстати, тренд на замещение RS на LDPC - это тренд, в том числе, и космической связи (см. DVB-S2) - может быть, какие-то более детальные исследования есть в этом русле.
Добрый день! Спасибо за статью!
Наверное, вы все-таки имели в виду OFDMA (Orthogonal Frequency-Division Multiple Access). OFDM на физическом уровне в IEEE 802.11 был почти всегда.
Срезали, принимается :)
В качестве развития темы: в общем-то, в питоновской heapq.heapify тоже заявлена O(N) ("linear time"). И судя по исходным кодам (поправьте если ошибаюсь), как раз обсуждаемый нами алгоритм (heapify хотя и использует функцию _sifup, сама _siftup внутри использует в конечном итоге _siftdown).
Думаю, что-то похожее сделали и в NumPy.
Хм, после Стивенса:
[Стивенс, Р., 2016. Алгоритмы. Разработка и применение. М.: Издательство "Э". - С. 148]
и Вирта:
[Вирт Н. АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ. М.Мир 1989 - С. 112]
как-то даже не возвращался к вопросу, спасибо за уточнение!
Соглашусь, что нужно было добавить "в худшем случае".
Спасибо за замечание, учту!
(поправил ссылку)
— Импульсная характеристика (link);
— Дискретное преобразование Фурье (ссылка);
— Теорема Парсеваля (ссылка).
— да, MUSIC — это один из методов спектрального анализа. По этому поводу могу посоветовать почитать Hayes M. H. Statistical digital signal processing and modeling. – John Wiley & Sons, 2009. глава 8 "SPECTRUM ESTIMATION".
— хм, чтобы разжевывали, честно говоря, даже не знаю… Но в целом, это напрямую относится к свойствам сингулярного разложения (см. Range, null space and rank и Relation to eigenvalue decomposition ).
Небольшой ответный комментарий:
По поводу RootMUSIC я и не предполагал «сэкономить» на вычислениях собственных векторов — основная разница между MUSIC и RootMUSIC, насколько я понимаю, состоит в способе нахождения оных.
Haykin S. S., Liu K. J. R. Handbook on array processing and sensor networks. – New York: Wiley, 2009. – c. 51-52.
Да, это в большей степени вопрос теории; на практике, как вы правильно, отметили достаточно найти пики (максимумы), а уж спект перед нами или псевдоспектр — дело не самое важное. Поправьте, если я не прав — честно признаюсь, с RootMUSIC я знаком шапочно.