Форум программистов, компьютерный форум, киберфорум
Наши страницы
Цифровая обработка сигналов
Войти
Регистрация
Восстановить пароль
 
alexelite34
0 / 0 / 0
Регистрация: 21.06.2018
Сообщений: 3
1

БПВ Алгортим из википедии

21.06.2018, 17:27. Просмотров 156. Ответов 4
Метки нет (Все метки)

ссылка

Подскажите этот код может использоваться если отчетов больше 16384. И объясните пожалуйста что значат коээфициенты Rcoef и откуда они берутся?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//_________________________________________________________________________________________
//_________________________________________________________________________________________
//
// NAME:          FFT.
// PURPOSE:       Быстрое преобразование Фурье: Комплексный сигнал в комплексный спектр и обратно.
//                В случае действительного сигнала в мнимую часть (Idat) записываются нули.
//                Количество отсчетов - кратно 2**К - т.е. 2, 4, 8, 16, ... (см. комментарии ниже).
//                
//              
// PARAMETERS:  
//
//    float *Rdat    [in, out] - Real part of Input and Output Data (Signal or Spectrum)
//    float *Idat    [in, out] - Imaginary part of Input and Output Data (Signal or Spectrum)
//    int    N       [in]      - Input and Output Data length (Number of samples in arrays)
//    int    LogN    [in]      - Logarithm2(N)
//    int    Ft_Flag [in]      - Ft_Flag = FT_ERR_DIRECT  (i.e. -1) - Direct  FFT  (Signal to Spectrum)
//                       Ft_Flag = FT_ERR_INVERSE (i.e.  1) - Inverse FFT  (Spectrum to Signal)
//
// RETURN VALUE:  false on parameter error, true on success.
//_________________________________________________________________________________________
//
// NOTE: In this algorithm N and LogN can be only:
//       N    = 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384;
//       LogN = 2, 3,  4,  5,  6,   7,   8,   9,   10,   11,   12,   13,    14;
//_________________________________________________________________________________________
//_________________________________________________________________________________________
 
 
#define  NUMBER_IS_2_POW_K(x)   ((!((x)&((x)-1)))&&((x)>1))  // x is pow(2, k), k=1,2, ...
#define  FT_DIRECT        -1    // Direct transform.
#define  FT_INVERSE        1    // Inverse transform.
 
bool  FFT(float *Rdat, float *Idat, int N, int LogN, int Ft_Flag)
{
  // parameters error check:
  if((Rdat == NULL) || (Idat == NULL))                  return false;
  if((N > 16384) || (N < 1))                            return false;
  if(!NUMBER_IS_2_POW_K(N))                             return false;
  if((LogN < 2) || (LogN > 14))                         return false;
  if((Ft_Flag != FT_DIRECT) && (Ft_Flag != FT_INVERSE)) return false;
 
  register int  i, j, n, k, io, ie, in, nn;
  float         ru, iu, rtp, itp, rtq, itq, rw, iw, sr;
  
  static const float Rcoef[14] =
  {  -1.0000000000000000F,  0.0000000000000000F,  0.7071067811865475F,
      0.9238795325112867F,  0.9807852804032304F,  0.9951847266721969F,
      0.9987954562051724F,  0.9996988186962042F,  0.9999247018391445F,
      0.9999811752826011F,  0.9999952938095761F,  0.9999988234517018F,
      0.9999997058628822F,  0.9999999264657178F
  };
  static const float Icoef[14] =
  {   0.0000000000000000F, -1.0000000000000000F, -0.7071067811865474F,
     -0.3826834323650897F, -0.1950903220161282F, -0.0980171403295606F,
     -0.0490676743274180F, -0.0245412285229122F, -0.0122715382857199F,
     -0.0061358846491544F, -0.0030679567629659F, -0.0015339801862847F,
     -0.0007669903187427F, -0.0003834951875714F
  };
  
  nn = N >> 1;
  ie = N;
  for(n=1; n<=LogN; n++)
  {
    rw = Rcoef[LogN - n];
    iw = Icoef[LogN - n];
    if(Ft_Flag == FT_INVERSE) iw = -iw;
    in = ie >> 1;
    ru = 1.0F;
    iu = 0.0F;
    for(j=0; j<in; j++)
    {
      for(i=j; i<N; i+=ie)
      {
        io       = i + in;
        rtp      = Rdat[i]  + Rdat[io];
        itp      = Idat[i]  + Idat[io];
        rtq      = Rdat[i]  - Rdat[io];
        itq      = Idat[i]  - Idat[io];
        Rdat[io] = rtq * ru - itq * iu;
        Idat[io] = itq * ru + rtq * iu;
        Rdat[i]  = rtp;
        Idat[i]  = itp;
      }
 
      sr = ru;
      ru = ru * rw - iu * iw;
      iu = iu * rw + sr * iw;
    }
 
    ie >>= 1;
  }
 
  for(j=i=1; i<N; i++)
  {
    if(i < j)
    {
      io       = i - 1;
      in       = j - 1;
      rtp      = Rdat[in];
      itp      = Idat[in];
      Rdat[in] = Rdat[io];
      Idat[in] = Idat[io];
      Rdat[io] = rtp;
      Idat[io] = itp;
    }
 
    k = nn;
 
    while(k < j)
    {
      j   = j - k;
      k >>= 1;
    }
 
    j = j + k;
  }
 
  if(Ft_Flag == FT_DIRECT) return true;
 
  rw = 1.0F / N;
 
  for(i=0; i<N; i++)
  {
    Rdat[i] *= rw;
    Idat[i] *= rw;
  }
 
  return true;
}
 
 
// Пример вычисления БПФ от одного периода косинусного
// действительного сигнала
 
void Test_FFT()
{
  static float Re[8];
  static float Im[8];
  float  p = 2 * 3.141592653589 / 8; // будет 8 отсчетов на период
 
  int i;
  // формируем сигнал
  for(i=0; i<8; i++)
  {
    Re[i] = cos(p * i);  // заполняем действительную часть сигнала
    Im[i] = 0.0;         // заполняем мнимую часть сигнала
  }
 
  FFT(Re, Im, 8, 3, FT_DIRECT); // вычисляем прямое БПФ
  
  // выводим действительную и мнимую части спектра и спектр мощности
  FILE *f = fopen("spectrum.txt", "w");
  for(i=0; i<8; i++)
  {
    fprintf(f, "%10.6f  %10.6f  %10.6f\n", Re[i], Im[i], Re[i]*Re[i]+Im[i]*Im[i]);
  }
  fclose(f);
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2018, 17:27
Ответы с готовыми решениями:

Задача на С++ ( нужно обьяснить логику и алгортим)
Вот собсна ТЗ: С клавиатуры вводится натуральное число N // нужна блок схема ...

Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n)
Доброго времени суток) Необходимо реализовать алгоритм Полларда (алгортим...

Парсинг википедии
Здравствуйте, знатоки! Помогите со следующим заданием, пожалуйста! Дана...

Парсинг википедии
Написать программу, которая бы обращалась к русской Википедии по адресу...

Парсинг Википедии
Здравствуйте. Выручайте! нужно сделать парсинг, т.е. я ввожу слово и его...

4
ValeryS
Модератор
7401 / 5599 / 710
Регистрация: 14.02.2011
Сообщений: 19,047
Завершенные тесты: 1
21.06.2018, 19:36 2
Цитата Сообщение от alexelite34 Посмотреть сообщение
что значат коээфициенты Rcoef
значения синуса\ косинуса в определенных точках
чем больше точек тем больше значений
1
alexelite34
0 / 0 / 0
Регистрация: 21.06.2018
Сообщений: 3
22.06.2018, 11:54  [ТС] 3
Значений всего 14 Rcoef, 2 в степени 14 = 16384 значений, Если я подам на вход допустим массив 131072 значение и степень 17 сработает ли этот алгоритмм?
0
ValeryS
Модератор
7401 / 5599 / 710
Регистрация: 14.02.2011
Сообщений: 19,047
Завершенные тесты: 1
22.06.2018, 12:52 4
Цитата Сообщение от alexelite34 Посмотреть сообщение
подам на вход допустим массив 131072 значение
17 значений синуса и 17 косинуса а 131072 это количество отсчетов 217=131072
попробуй для начала с простого 2 отсчета 4 ... тогда поймешь как формируются эти таблицы
рекомендую поискать книгу "Руководство программиста по работе со звуком" Кинтцель Тим
там это Фурье, и не только, объяснено буквально на пальцах
1
alexelite34
0 / 0 / 0
Регистрация: 21.06.2018
Сообщений: 3
25.06.2018, 09:51  [ТС] 5
Спасибо, обязательно почитаю, но тем не менее вопрос остался в описании говорится
NOTE: In this algorithm N and LogN can be only:
// N = 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384;
// LogN = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14;
а если мне надо подать больше отсчетов 2^17=131072 отсчетов я могу его вызвать bool FFT(float *Rdat, float *Idat, 131072 , 17, int Ft_Flag) ?? Иои нужно модифицировать код алгоритма? И как? Спасибо.
0
25.06.2018, 09:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2018, 09:51

Выборка из википедии во внутреннюю БД
Нужно написать систему, делающую выборку (копирование статей) из wikipedia во...

Ссылки как в википедии
Добрый день, друзья. Интересует следующий вопрос. Как реализовать на этом...

Новогодний логотип для Википедии
Друзья, каждый год в честь Нового года Русская Википедия меняет свой логотип на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru