如何理解离散傅里叶变换求周期的结果？

Question

我正在学习如何使用离散傅立叶变换（DFT）来找到关于

a^x mod(N)

的周期，其中

是一个正整数，

是任何素数，

是两个素数的乘积因素

和

。

例如，

2^x mod(15)

的周期为4，

>>> for x in range(8):
...     print(2**x % 15)
...

Output: 1 2 4 8 1 2 4 8
                ^-- the next period

DFT的结果如下，

（引自O'Reilly 编程量子计算机第 12 章）

有 4 个尖峰，间距为 4 个单位，我认为后 4 个意味着周期为 4。

但是，当

为 35 且周期为 12 时

>>> for x in range(16):
...     print(2**x % 35)
...

Output: 1 2 4 8 16 32 29 23 11 22 9 18 1 2 4 8
                                       ^-- the next period

在本例中，有 8 个大于 100 的尖峰，其位置分别为 0、5、6、11、32、53、58、59。

位置顺序是否暗示着神奇的数字12？如何理解右图中的“12 个均匀分布的尖峰”？

（引自O'Reilly 编程量子计算机第 12 章）

Answer 1

请参阅如何计算离散傅立叶变换？以及所有子链接，尤其是如何获取 FFT 中每个值的频率？.

如您所见，DFT 结果的第

元素（包括从

到

n-1

计数）代表 Niquist 频率

f(i) = i * fsampling / n

DFT 结果仅使用那些正弦频率。因此，如果您的信号确实具有不同的信号（即使频率或形状略有不同），就会出现混叠。

混叠正弦曲线在 DFT 输出中创建 2 个频率，一个频率较高，一个频率较低。

任何尖锐边缘都会转换为许多频率（通常是连续频谱，如上一个示例）

f(0)

没有频率，代表直流偏移。

最重要的是，如果您的 DFT 的输入是实数域，那么 DFT 结果是对称的，这意味着您只能使用结果的前半部分，因为第二部分只是镜像（不包括 f(0)）这是有道理的，因为您无法在实域数据中表示大于 fsampling/2 的频率。

结论：

您无法获得 DFT 使用的信号频率，因为计算此类信号的方法有无数种。 DFT 正在使用正弦波重建信号，而您的信号肯定不是正弦波，因此结果将与您的想法不符。

将尼奎斯特频率与您的频率相匹配是通过正确选择 DFT 的

n

来完成的，但是如果不知道前面的频率，您就无法执行此操作...

可以从其 2 个别名计算奇异正弦波频率，但是您的信号不是正弦波，因此无论如何这不适用于您的情况。

我会使用不同的方法来确定整数数字信号的频率：

计算信号直方图

数一下每个数字有多少个
测试可能的频率
您可以暴力破解所有可能的信号周期并测试后续周期是否相同，但是对于大数据来说这不是最佳选择... 我们可以使用直方图来加快速度。因此，如果您从直方图中查看频率为
cnt(ix)
的周期信号和大小为
f
的数据中的周期
```
T
```
的计数
```
n
```
，那么信号周期应该是所有计数的公约数
T = n/f k*f = GCD(all non zero cnt[i])
其中
k
```
 除 GCD 结果。然而，如果 
```
n
不是
```
T
```
的精确倍数，或者信号中存在噪声或轻微偏差，则这将不起作用。然而，我们至少可以估计 GCD 并测试周围的所有频率，这些频率仍然比蛮力更快。
因此，对于每个计数（不考虑噪声），它应该符合以下条件：
cnt(ix) = ~ n/(f*k) k = { 1,2,3,4,...,n/f}

所以：
```
f = ~ n/(cnt(ix)*k)
```
所以如果你收到这样的信号：
```
1,1,1,2,2,2,2,3,3,1,1,1,2,2,2,2,3,3,1
```
那么直方图将是
cnt[]={0,7,8,4,0,0,0,0,...}
```
 和 
```
n=19
，因此针对每个使用的元素以每个
```
f
```
的周期计算
```
n
```
会导致：
f(ix) = n/(cnt(ix)*k) f(1) = 19/(7*k) = ~ 2.714/k f(2) = 19/(8*k) = ~ 2.375/k f(3) = 19/(4*k) = ~ 4.750/k
现在实际频率应该是结果的共同除数（CD），因此将最大和最小计数向上和向下舍入（忽略噪声）会导致以下选项：
```
f = CD(2,4) = 2
f = CD(3,4) = none
f = CD(2,5) = none
f = CD(3,5) = none
```
所以现在测试频率（幸运的是，在这种情况下只有一个有效）每 19 个样本 2 个周期意味着
T = ~ 9.5
```
 所以测试向上和向下舍入...
```
signal(t+ 0)=1,1,1,2,2,2,2,3,3,1,1,1,2,2,2,2,3,3,1 signal(t+ 9)=1,1,1,2,2,2,2,3,3,1 // check 9 elements signal(t+10)=1,1,2,2,2,2,3,3,1,? // check 10 elements
如您所见，
signal(t...t+9)==signal(t+9...t+9+9)
```
表示周期为
```
T=9
。
```
    
```

如何理解离散傅里叶变换求周期的结果？

问题描述投票：0回答：2

2个回答

最新问题

如何理解离散傅里叶变换求周期的结果？

问题描述 投票：0回答：2

2个回答

最新问题

问题描述投票：0回答：2