คุณสมบัติอนุพันธ์ DFT?
มันมีไหม? ตัวแปรต่อเนื่องทำ$f'(t) \rightarrow j \omega F(\omega)$ - แต่ $jkX[k]$ แน่นอนว่าไม่ใช่สำหรับ DFT
ในการค้นหาจะต้องมีการทำให้เข้าใจง่ายขึ้น $\text{DFT}(x[n] - x[n-1])$, ที่ไหน $x[n] = \sum_{k=0}^{N-1} X[k] e^{j2\pi kn/N}$ในขณะที่บัญชีสำหรับตัวอย่างที่ตกหล่น ( x[0]) - และฉันไม่เห็นการทำให้เข้าใจง่ายเช่นนี้
หมายเหตุ :$x[n] = ...$ด้านบนเป็นคำจำกัดความของ IDFT ที่ฉันใช้แทนที่จะเป็นที่มาของสัญญาณ สัญญาณควรได้รับการสันนิษฐานโดยทั่วไปมากที่สุด ไม่ใช่คาบอาจซับซ้อนหรือจริงก็ได้ แต่ต้องมีข้อ จำกัด
หมายเหตุ 2 : ดูคำตอบของฉันสำหรับคำเตือนที่สำคัญบางประการ (และขัดแย้งโดยตรงกับ) คำตอบที่ยอมรับและเลือกที่จะอภิปรายความคิดเห็นด้านล่างคำตอบ ขอบคุณ @CedronDawg สำหรับการสนทนาโดยละเอียด
Note3 : "derivative" = ความแตกต่าง จำกัด (เพื่อประโยชน์ของคำถามนี้)
คำตอบ
เพื่อให้ได้คำตอบโดยละเอียดตามบรรทัดของสิ่งที่คุณเสนอเราต้องระมัดระวังเกี่ยวกับการทำให้เป็นมาตรฐานที่ใช้ในการแปลงฟูริเยร์แบบไม่ต่อเนื่อง (DFT) และการแปลงฟูริเยร์แบบไม่ต่อเนื่องผกผัน (IDFT):
$$\text{DFT: }\quad X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2\pi kn/N}\tag{1}$$ $$\text{IDFT: }\quad x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j 2 \pi k n / N}\tag{2}$$
สิ่งเหล่านี้มีการทำให้เป็นมาตรฐานที่เข้ากันได้โดยตรงกับfftและifftจาก MATLAB, Octave, NumPy และ SciPy ดัชนี$k$ และ $n$ วิ่งจาก $0$ ถึง $N-1$. (MATLAB และ Octave มีรูปแบบการจัดทำดัชนีที่แตกต่างกัน$1$ ถึง $N$.) จากนั้น:
$$\begin{array}{c}y[n] = x[n] - x[\operatorname{mod}(n-1, N)]\\ \begin{align}\\ Y &= \operatorname{DFT}\big(y\big)\\ &= \operatorname{DFT}(x*[1, -1, 0, 0, \ldots])\\ &= \operatorname{DFT}(x)\times\operatorname{DFT}([1, -1, 0, 0, \ldots])\\ &= X\times\operatorname{DFT}([1, -1, 0, 0, \ldots])\end{align}\end{array}\tag{3}$$ $$\Rightarrow Y[k]= X[k]\left(1 - e^{-j2\pi k/N}\right),\tag{4}$$
ที่ไหน $\operatorname{mod}$ ให้ส่วนที่เหลือที่ไม่ได้ลงนามตัวอย่างเช่น $\operatorname{mod}(-1, N) = N - 1$, สัญลักษณ์ $*$ หมายถึงความยาว -$N$ การหมุนเวียนแบบวงกลมและ $\times$ หมายถึงการคูณและลำดับทั้งหมดมีความยาว $N$.
Circular Convolution ในโดเมนเวลาไม่ต่อเนื่องเทียบเท่ากับการคูณในโดเมนความถี่ไม่ต่อเนื่องเมื่อ DFT และ IDFT ถูกใช้เพื่อเปลี่ยนลำดับระหว่างโดเมน ดูตัวอย่างCircular บิด - MIT OpenCourseWare สำหรับการแปลงลำดับแบบไม่ต่อเนื่องแบบ "เชิงเส้น" ไม่มีการดำเนินการเทียบเท่าคู่ที่สง่างามเช่นนี้ซึ่งทำให้ฉันคิดว่าไม่มีนิพจน์ใดที่เสนอเป็นคำตอบสำหรับคำถามที่น่าพอใจ
พิจารณาสัญญาณอินพุตที่ขยายไปทางซ้ายของช่วงเอาต์พุต $0 \le n < N$ของ IDFT การคำนวณความแตกต่างย้อนหลังโดยใช้การจัดทำดัชนีโมดูโลจะมีเงื่อนไขเท่ากับการคำนวณโดยไม่มี:
$$x[n] - x[\operatorname{mod}(n-1, N)] = x[n] - x[n-1]\quad\text{conditionally}\tag{5}$$
ภายใต้เงื่อนไขที่คุณคำนวณสำหรับดัชนีบางตัวเท่านั้น:
$$0 < n < N,\tag{6}$$
หรือสำหรับ $0 \le n < N$ ภายใต้เงื่อนไขที่มีคำใบ้เป็นระยะในสัญญาณ:
$$x[-1] = x[N-1].\tag{7}$$
เงื่อนไขที่เพียงพอ แต่ไม่จำเป็นที่เป็นไปตาม Eq 7 นั่นคือ$x$ คือ $N$- เป็นระยะซึ่งถูกห้ามโดยสัญญาณที่กำหนดไว้ในคำถาม ตัวอย่างของเงื่อนไขอื่นที่เป็นไปตาม Eq 7 คือ$x[-1] = x[N-1] = 0$.
คำตอบแรกของ @ CedronDawgให้สูตรที่แก้ไขข้อผิดพลาดใน Eq ในโดเมนความถี่ 5 หากไม่เป็นไปตามเงื่อนไข:$Y[k] = X[k]\left( 1 - e^{-j2\pi k/N} \right) - x[-1] + x[N-1]$. ในฐานะที่เป็นแหล่งกำเนิดทางเลือกในความยาว -$N$ โดเมนเวลาการแก้ไขเป็นแรงกระตุ้น:
$$\begin{align}&\big[x[0] - x[−1] - \big(x[0] - x[N-1]\big),\, 0,\, 0,\, \ldots\big]\\ = &\big[x[N-1] - x[-1],\, 0,\, 0,\, \ldots\big],\end{align}\tag{8}$$
ซึ่งในโดเมนความถี่เป็นค่าคงที่ (ดูDFT Pairs and Properties : pair row 2, property linearity):
$$x[N-1] - x[-1],\tag{9}$$
ที่จะเพิ่มลงในองค์ประกอบทั้งหมดของ $Y$คำนวณโดย Eq. 4.
สำหรับคนทั่วไป $x$, สภาพของ Eq. 6 สำหรับ Eq. 5 ช่วยให้สามารถใช้ความยาวได้$N+1$DFT และ IFT เพื่อคำนวณความแตกต่างย้อนหลังโดยเลื่อนอินพุตไปที่ DFT ไปทางขวาหนึ่งขั้นและสุดท้ายโดยการเลื่อนเอาต์พุตจาก IDFT ไปทางซ้ายหนึ่งขั้น พร้อมส่งต่อความแตกต่าง$x[n + 1] - x[n]$การกะจะไม่จำเป็นและฉันคิดว่าสิ่งนี้ตรงกับการทิ้งตัวอย่างที่ 0 ของคุณ สำหรับการดำเนินการ Convolution แบบวงกลมตามลำดับที่ จำกัด การใช้การแปลงที่ยาวขึ้นเป็นเคล็ดลับทั่วไปเพื่อหลีกเลี่ยงเอฟเฟกต์แบบวงกลมในส่วนที่ใหญ่พอของเอาต์พุตของ IDFT สำหรับการได้รับ DFT ของเอาต์พุต IDFT บางส่วนโดยเฉพาะอย่างยิ่งอันที่สั้นกว่าฉันไม่คิดว่าจะมีทางลัดใด ๆ
บางทีเราอาจจะแสดงคำถามอีกครั้งว่า DFT ของความยาวคืออะไร $N-1$ ส่งต่อความแตกต่างของ $x$ ความยาว $N$ให้ $x$ และ $X_{N-1} = \operatorname{DFT}(x_{N-1})$, ความยาว $N-1$ DFT ของลำดับบางส่วน $x_{N-1} = \big[x[0], x[1], \ldots, x[N-2]\big]$เหรอ? คล้ายคลึงกับ Eq 4 เรามี:
$$y_{N-1} = x_{N-1}*[-1, 0, 0, \ldots, 0, 0, 1]\tag{10.1}$$ $$\Leftrightarrow Y_{N-1} = X_{N-1}\times\operatorname{DFT}([-1, 0, 0, \ldots, 0, 0, 1])\tag{10.2}$$ $$\Rightarrow Y_{N-1}[k] = X_{N-1}[k]\big(e^{j2\pi k / (N - 1)} - 1\big),\tag{10.3}$$
โดยที่แต่ละลำดับมีความยาว $N-1$. ความแตกต่างไปข้างหน้าที่ต้องการ$f_{N-1}$ คือ:
$$f_{N-1} = \big[x[1] - x[0],\, x[2] - x[1],\, \ldots,\, x[N-1] - x[N-2]\big].\tag{11}$$
Eq. 10.1 สามารถขยายเป็น:
$$y_{N-1} = \big[x[1] - x[0],\, x[2] - x[1],\, \ldots,\, x[0] - x[N-2]\big].\tag{12}$$
โดยการเปรียบเทียบ Eqs. 11 และ 12 จะเห็นได้ว่า:
$$f_{N-1} = y_{N-1} + \big[\ldots,\, 0,\, 0,\, x[N-1] - x[0]\big],\tag{13}$$
โดยที่ลำดับในวงเล็บมีความยาว $N-1$. การ DFT ของทั้งสองด้านของ Eq. 13 และใช้ Eq. 10.3 ให้คำตอบ:
$$\begin{align}F_{N-1}[k] &= Y_{N-1}[k] + (x[N-1] - x[0])e^{j2\pi k/(N-1)}\\ &=X_{N-1}[k]\big(e^{j2\pi k / (N - 1)} - 1\big) + (x[N-1] - x[0])e^{j2\pi k/(N-1)}.\end{align}\tag{14}$$
นี่คือความยาว $N-1$ DFT ของความยาว $N-1$ ส่งต่อความแตกต่างของ $x$ ความยาว $N$.
หรือคุณอาจสนใจอนุพันธ์ของสัญญาณ จำกัด วงที่แสดงโดยตัวอย่าง
[แก้ไข: คำตอบนี้อ้างอิงจาก x [n] เป็นสัญญาณอินพุต (น่าจะสุ่มตัวอย่างจากฟังก์ชันที่แตกต่างอย่างต่อเนื่อง) ซึ่งเป็นการตีความคำถามของ OP ผิดพลาดและสิ่งที่ถูกค้นหาคือการแปลงจากสเปกตรัมของอินพุต ส่งสัญญาณไปยังสเปกตรัมของความแตกต่างแรกเชิงเส้น หากใครต้องการสเปกตรัมของความแตกต่างแรกของวงกลมภายในกรอบการวิเคราะห์ก็ไม่จำเป็นต้องมีระยะความชัน นอกจากนี้ยังสามารถเห็นได้อย่างชัดเจนจากสูตรที่ว่า DC bin ของสเปกตรัมความแตกต่างของวงแหวนจะเป็นศูนย์]
นี่เป็นแนวทางที่แตกต่างจากที่ Olli ทำตรงจากคำจำกัดความและไม่ถือว่าเป็นสัญญาณ N เป็นระยะ
$$ \begin{aligned} Y[k] &= \text{DFT}(x[n] - x[n-1]) \\ &= \text{DFT}(x[n]) - \text{DFT}(x[n-1]) \\ &= X[k] - \text{DFT}(x[n-1]) \\ &= X[k] - \sum_{n=0}^{N-1} x[n-1] e^{-i\frac{2\pi}{N}kn } \\ &= X[k] - \sum_{m=-1}^{N-2} x[m] e^{-i\frac{2\pi}{N}k(m+1)} \\ &= X[k] - e^{-i\frac{2\pi}{N}k} \sum_{m=-1}^{N-2} x[m] e^{-i\frac{2\pi}{N}km} \\ &= X[k] - e^{-i\frac{2\pi}{N}k}\left[ \sum_{m=0}^{N-1} x[m] e^{-i\frac{2\pi}{N}km} + x[-1]e^{i\frac{2\pi}{N}k} - x[N-1] e^{-i\frac{2\pi}{N}k(N-1)} \right] \\ &= X[k] - e^{-i\frac{2\pi}{N}k}\left[ X[k] + x[-1] e^{i\frac{2\pi}{N}k} - x[N-1] e^{-i\frac{2\pi}{N}k(N-1)} \right] \\ &= X[k]\left( 1 - e^{-i\frac{2\pi}{N}k} \right) - \left[ x[-1] - x[N-1] e^{-i\frac{2\pi}{N}k(N-1)}e^{-i\frac{2\pi}{N}k} \right] \\ &= X[k]\left( 1 - e^{-i\frac{2\pi}{N}k} \right) - x[-1] + x[N-1] \\ \end{aligned} $$
สำหรับสัญญาณ N เป็นระยะ $x[-1] = x[N-1] $ ดังนั้นผลลัพธ์จะกลายเป็น:
$$ Y[k] = X[k]\left( 1 - e^{-i\frac{2\pi}{N}k} \right) $$
การพิจารณานอร์มัลไลเซชันเป็นสิ่งสำคัญ ฉันใช้นิยาม DFT ข้างหน้าแบบผิดปกติธรรมดา การใช้การทำให้เป็นมาตรฐาน 1 / N (เหมาะสมมากขึ้น IMO) ตามนัยโดยคำจำกัดความของ OP ของ DFT ผกผันนิพจน์จะกลายเป็น:
$$ Y[k] = X[k]\left( 1 - e^{-i\frac{2\pi}{N}k} \right) + \frac{x[N-1]-x[-1]}{N} $$
ระยะสุดท้ายกลายเป็นการคำนวณความชันอย่างชัดเจน
เพื่อตอบสนองต่อความคิดเห็นของ OverLordGoldDragon ใช้การทำให้เป็นมาตรฐานทั่วไป:
$$ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i \frac{2\pi}{N} nk } $$
มาทำให้ต่อเนื่องกันเถอะ
$$ x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i \frac{2\pi}{N} nk } $$
หาอนุพันธ์เทียบกับ n
$$ \begin{aligned} \frac{dx}{dn} (n) &= \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i \frac{2\pi}{N} nk } \left(i \frac{2\pi}{N} k \right) \\ &= \frac{2\pi}{N^2} \sum_{k=0}^{N-1} i k X[k] e^{i \frac{2\pi}{N} nk } \\ \end{aligned} $$
ดังนั้นการยืนยันครั้งแรกของคุณจึงไม่ถูกต้องมันใช้กับ DFT สำหรับอนุพันธ์ต่อเนื่อง
ตามกฎลูกโซ่:
$$ \frac{dx}{dt} = \frac{dx}{dn} \cdot \frac{dn}{dt} $$
ความแตกต่างที่คุณใช้สำหรับการประมาณสำหรับอนุพันธ์ไม่ใช่ค่าที่ดีที่สุดเนื่องจากมีการเปลี่ยนตัวอย่างครึ่งหนึ่ง โดยทั่วไปคุณต้องการ$(x[n+1]-x[n-1])/2$. ซึ่งจะอยู่ตรงกลางและไม่ "ขยายสัญญาณรบกวน" ในช่วงความถี่ที่สูงขึ้น
คอมเม้นก็ออกน้อยด้วย $$ \begin{aligned} \left( 1 - e^{-i\frac{2\pi}{N}k} \right) &= e^{-i\frac{\pi}{N}k} \left( e^{i\frac{\pi}{N}k} - e^{-i\frac{\pi}{N}k} \right) \\ &= e^{-i\frac{\pi}{N} k} 2i \sin\left( \frac{\pi}{N}k \right) \\ &= e^{-i\frac{\pi}{N} k} 2 e^{i \frac{\pi}{2} } \sin\left( \frac{\pi}{N}k \right) \\ &= e^{-i\left( \frac{\pi}{N} k - \frac{\pi}{2} \right) } 2 \sin\left( \frac{\pi}{N}k \right) \\ \end{aligned} $$
ดังนั้น
$$ \left| \left( 1 - e^{-i\frac{2\pi}{N}k} \right) \right| = 2 \sin\left( \frac{\pi}{N}k \right) $$
และ
$$ \arg \left( 1 - e^{-i\frac{2\pi}{N}k} \right) = -\frac{\pi}{N} k + \frac{\pi}{2} = - \frac{\pi}{2} \left( 1 - \frac{2k}{N} \right) $$
การเปลี่ยนเกียร์โปรดทราบว่าสำหรับ $k=0$
$$ Y[0] = \frac{x[N-1]-x[-1]}{N} $$
ดังนั้นองค์ประกอบ DC ของส่วนต่างของคุณคือความชันเฉลี่ยเหนือเฟรมของคุณตามที่คาดไว้
ฉันไม่อ่านหนังสือเรียนดังนั้นฉันจึงไม่สามารถพูดถึงเรื่องนั้นได้ ความน่าสนใจไม่ได้ตรงกันกับประโยชน์เสมอไป
ฉันเรียนด้วยตัวเองจากนั้นฉันก็ทำการค้นคว้าออนไลน์เพื่อยืนยันสิ่งที่ฉันค้นพบ สิ่งที่น่าแปลกใจสำหรับฉันคือสูตรความถี่ของฉันซึ่งเป็นสูตรแรกที่บรรลุความเที่ยงตรงยังไม่อยู่ในหลักสูตรด้วย
ไขปริศนาแล้ว Duh.
เว้นแต่คุณจะอยู่กึ่งกลางรอบศูนย์ดังนั้นคุณกำลังใช้ $k=-1$ แทน $k=N-1$อนุพันธ์จะเป็นของการแก้ไขความถี่ที่สูงขึ้น (เทียบเท่ากับอนุพันธ์ของ DTFT ณ จุดนั้น)
ซึ่งจะคล้ายกับกรณี "Fluffy Cloud" ที่นี่: จะหาค่าสัมประสิทธิ์ฟูริเยร์เพื่อวาดรูปร่างโดยใช้ DFT ได้อย่างไร?
ฉันคิดว่าส่วนหนึ่งของความสับสนของฉันคือคุณกำลังใช้ (เมื่ออ่านซ้ำ) DFT ผกผันที่ขยายเป็น x [n] ดังนั้นจึงสามารถคำนวณ x [-1] ได้และจะจับคู่ x [N-1] ในขณะที่คุณสร้างรหัส สัญญาณ x [n] ตั้งแต่เริ่มต้น
กำหนด
$$ y[n] = x[n] - x[n-1] $$
และ
$$ Y[k] = DFT(y[n]) $$
รหัสของคุณ "ลดตัวอย่าง" ในขณะที่ Olli และคำตอบของฉันใช้ x [-1] คำตอบของ Olli ถือว่าเป็นระยะ (ยอมรับมัน) ของฉันไม่ได้ (คิดว่าคุณกำลังทำงานกับสัญญาณดิบ) ฉันคิดว่ามันไม่เหมาะสมที่จะ "วางตัวอย่าง" เหมือนที่ np.diff เรียก หากคุณทำเช่นนั้นคุณควรจัดกรอบปัญหาใหม่ในโดเมนของ 1 ถึง N-1 โดยให้เป็น 0 ถึง M-1 โดยที่ M = N-1 คุณจะมีสถานการณ์เทียบเท่ากับการไม่ทิ้งตัวอย่าง
เมื่อ "วางตัวอย่าง" ของคุณจะเปลี่ยนคำจำกัดความ DFT ทำให้สองบรรทัดแรกของฉันไม่ถูกต้อง
อดทนหน่อยแล้วฉันจะชี้แจงคำพูดปริศนา
โดยไม่ต้องมีคำอธิบายมากมายนี่คือ "ปริศนาไขปริศนา" โปรดสังเกตว่าถ้า x ถูกสอดแทรกโดยใช้ค่า k ตัวบนเป็นความถี่บวกจะมีการสั่นระหว่างจุดที่ลงจุดไว้มากมาย ดังนั้น Y.
การปรับขนาดใหม่ถูกทำให้สับสนโดยไฟล์ $ 2\pi $ ปัจจัยของ t และ $\frac{dn}{dt}$ ดังนั้นฉันจึงไม่ต้องกังวลกับการทำให้โค้ดยุ่งเหยิงเพราะมันไม่ได้สำคัญกับปัญหาที่อยู่ในมือ
นำเข้า numpy เป็น np
นำเข้า matplotlib.pyplot เป็น plt
# ================================================= ========
def หลัก ():
N = 128
t = np.linspace (0, 1, N, เท็จ)
x = np.cos (2 * np.pi * เสื้อ)
X = np.fft.fft (x)
plt.plot (x)
plt.show ()
Y = np.zeros (N, dtype = 'ซับซ้อน')
สำหรับ k ในช่วง (N):
Y [k] = X [k] * 1j * k
y = np.fft.ifft (Y)
plt.plot (y.real)
plt.plot (y.imag)
plt.show ()
Z = np.zeros (N, dtype = 'ซับซ้อน')
H = N >> 1
สำหรับ k ในช่วง (-H, H):
ถ้า k> = 0:
Z [k] = X [k] * 1j * k
อื่น:
Z [k + N] = X [k + N] * 1j * k
z = np.fft.ifft (Z)
plt.plot (z.real)
plt.plot (z.imag)
plt.show ()
# ================================================= ========
หลัก()
นี่คือพล็อตสุดท้าย:
นี่คือโปรแกรมทดสอบสำหรับสูตร:
นำเข้า numpy เป็น np
# ================================================= ============================
def หลัก ():
L = 10000 # ความยาวของสัญญาณ
F = 100 # ตำแหน่งเฟรม
N = 16 # ขนาดเฟรม = จำนวนตัวอย่าง DFT
P = np.zeros (L) # ตำแหน่ง
D = np.zeros (L) # ความแตกต่าง
สำหรับ n ในช่วง (L):
P [n] = 1.2 + 0.3 * n + 0.045 * n * น
สำหรับ n ในช่วง (1, L):
D [n] = P [n] - P [n-1]
x = P [F: F + N]
y = D [F: F + N]
X = np.fft.fft (x) / น
Y = np.fft.fft (y) / N
Z = np.zeros (N, dtype = ซับซ้อน)
C = (x [N-1] - P [F-1]) / น
สำหรับ k ในช่วง (N):
Z [k] = X [k] * (1 - np.exp (-1j * (2.0 * np.pi / N) * k)) + C
สำหรับ n ในช่วง (N):
พิมพ์ ("% 2d% 10.6f% 10.6f% 10.6f% 10.6f"% \
(n, Y [n] .real, Y [n] .imag, Z [n] .real, Z [n] .imag))
# ================================================= ============================
หลัก()
นี่คือผลลัพธ์:
0 9.930000 0.000000 9.930000 0.000000 1 -0.045000 0.226230 -0.045000 0.226230 2 -0.045000 0.108640 -0.045000 0.108640 3 -0.045000 0.067347 -0.045000 0.067347 4 -0.045000 0.045000 -0.045000 0.045000 5 -0.045000 0.030068 -0.045000 0.030068 6 -0.045000 0.018640 -0.045000 0.018640 7 -0.045000 0.008951 -0.045000 0.008951 8 -0.045000 0.000000 -0.045000 -0.000000 9 -0.045000 -0.008951 -0.045000 -0.008951 10 -0.045000 -0.018640 -0.045000 -0.018640 11 -0.045000 -0.030068 -0.045000 -0.030068 12 -0.045000 -0.045000 -0.045000 -0.045000 13 -0.045000 -0.067347 -0.045000 -0.067347 14 -0.045000 -0.108640 -0.045000 -0.108640 15 -0.045000 -0.226230 -0.045000 -0.226230
ตอบกลับความคิดเห็นของ RB-J ภายใต้คำตอบอื่นของฉัน:
"DFT periodicity denier ทำอะไรกับ x [−1]"
"จะเกิดอะไรขึ้นถ้าคุณคูณ DFT ของ x [n] (ซึ่งเราเรียกว่า" X [k] ") ด้วยej2πdk / N (โดยที่ d คือจำนวนเต็ม) คุณจะพบว่า DFT ให้ความสำคัญกับคาบมาก -"
และคล้ายกันจากการสร้างหน่วยของ PSD ที่คำนวณในเชิงวิเคราะห์สอดคล้องกับหน่วยของ FFT
"// DFT ไม่ได้พิจารณาว่าสัญญาณอยู่นอกเฟรมอะไร // ... ไม่เคย --- เอาล่ะ @CedronDawg DFT" พิจารณา "อะไรเมื่อคุณคูณ X [k] ด้วยej2πdk / N โดยที่d∈ Z? (X [k] ทั้งหมดสำหรับ0≤k <N.) - robert bristow-johnson 4 ชั่วโมงที่ผ่านมา "
เอาล่ะเริ่มด้วยสัญญาณที่มีตัวอย่างมากมาย สมมติว่าฉันต้องการวิเคราะห์ส่วนหนึ่งของมันโดยมีตัวอย่าง N อยู่ในนั้น ในการทำเช่นนั้นฉันจะสร้างกรอบการวิเคราะห์ ซึ่งหมายถึงการจัดทำดัชนีตัวอย่างใหม่เพื่อให้ตัวอย่างแรกของกรอบการวิเคราะห์ของฉันอยู่ที่ดัชนี 0 เนื่องจากฉันตั้งใจจะใช้ DFT ในส่วนนี้ฉันจึงเรียกมันว่าเฟรม DFT ได้
นี่ไม่ใช่สิ่งเดียวกับ "windowing" ฉันยังสามารถกำหนดฟังก์ชันหน้าต่างสี่เหลี่ยมผืนผ้าที่มีฟังก์ชันสำหรับตัวอย่างทั้งหมดในส่วนของฉันและศูนย์ทุกที่ ฟังก์ชั่นหน้าต่างถูกจัดทำดัชนีในการจัดทำดัชนีพื้นฐานจะไม่สร้างกรอบการสร้างดัชนีใหม่
หากต้องการฉันสามารถกำหนดฟังก์ชันหน้าต่างที่สัมพันธ์กับกรอบการวิเคราะห์ของฉันได้ หน้าต่างสี่เหลี่ยมผืนผ้าที่ทอดกรอบของฉันจะเฉื่อย / ไม่พอใจในแง่ของการรับ DFT คุณสามารถพิจารณานิยาม DFT ว่ามีหน้าต่างโดยปริยายเช่นนี้ แต่ไม่ได้เป็นส่วนหนึ่งของนิยาม หากเป็นคำจำกัดความที่ผิดปกติจะเป็น:
$$ X[k] = \sum_{n=0}^{N-1} 1 \cdot x[n] \cdot e^{-i \frac{2\pi}{N} kn } $$
ดังนั้นหากส่วนนั้นไม่ได้อยู่ที่จุดเริ่มต้นของสัญญาณ $x[-1]$จะอ้างถึงตัวอย่างก่อนกรอบการวิเคราะห์ของฉัน หากส่วนนั้นอยู่ที่จุดเริ่มต้นของสัญญาณคำตอบที่ถูกต้องจะเป็นเช่นนั้น$x[-1]$ไม่ได้กำหนด หากต้องตั้งสมมติฐานเกี่ยวกับเรื่องนี้คำตอบที่สมเหตุสมผลที่สุดจะเป็นค่าศูนย์
ตอนนี้สมมติว่าเราใช้ DFT ของส่วนนี้ซึ่งให้ผล $ X[k] $ ค่าสำหรับ $ 0 <= k < N $. ค่าที่อยู่นอกช่วงนี้ยังสามารถประเมินได้โดยการกำหนดและจะส่งผลให้เกิดสเปกตรัมเป็นระยะโดยมีช่วงเวลา N ซึ่งอาจไม่ใช่ช่วงเวลาพื้นฐาน แต่ไม่เกี่ยวข้องกับการสนทนานี้
ตอนนี้เราอยู่ที่จุดเริ่มต้นของคำถามของ OP (สิ่งที่ฉันเข้าใจผิดในตอนแรก)
ระบุค่าของ $X[k]$ เราสามารถใช้ DFT ผกผันและสร้างไฟล์ $x[n]$ ค่าสำหรับ $ 0 <= n < N $ตัวอย่างภายในกรอบการวิเคราะห์ เช่นเดียวกับสเปกตรัมสามารถประเมินสูตรได้เช่นกัน$n$ค่านอกกรอบการวิเคราะห์ ในทำนองเดียวกันค่าที่ได้จะสร้างลำดับเป็นระยะโดยมีจุด N ไม่มีเหตุผลอย่างแน่นอนที่จะสันนิษฐานยืนยันหรือกำหนดว่าค่าที่ขยายเหล่านี้ควรตรงกับค่าสัญญาณดั้งเดิมนอกกรอบการวิเคราะห์ ถ้าจะติดป้ายว่าปฏิเสธก็ดี ....
นอกจากนี้ยังเป็นไปไม่ได้เนื่องจากมีเพียงไฟล์ $X[k]$ ค่าเพื่อกำหนดสิ่งที่เป็นต้นฉบับ $x[-1]$มูลค่าคือ. ค่าที่ได้จากการขยาย DFT ผกผันจะเหมือนกับ$x[N-1]$. อีกครั้งไม่มีรากฐานที่จะกำหนดสมมติยืนยันรักษาหรือประกาศว่าสิ่งนี้ตรงกับค่าสัญญาณดั้งเดิม
สมมติว่าตอนนี้ฉันคูณ / บิดขึ้น / ปรับสเปกตรัมโดยใช้ตัวประกอบของ $ e^{i \frac{2\pi}{N} dk } $. เอาล่ะมาทำคณิตศาสตร์กัน
$$ Z[k] = X[k] \cdot e^{i \frac{2\pi}{N} dk } $$
ใช้ DFT ผกผัน:
$$ \begin{aligned} z[n] &= \frac{1}{N} \sum_{k=0}^{N-1} Z[k] \cdot e^{ i \frac{2\pi}{N} nk } \\ &= \frac{1}{N} \sum_{k=0}^{N-1} X[k] \cdot e^{i \frac{2\pi}{N} dk } \cdot e^{ i \frac{2\pi}{N} nk } \\ &= \frac{1}{N} \sum_{k=0}^{N-1} X[k] \cdot e^{ i \frac{2\pi}{N} (n+d)k } \\ \end{aligned} $$
ปล่อย $ m = n + d $ ดังนั้น $ n = m - d $.
$$ z[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] \cdot e^{ i \frac{2\pi}{N} mk } = x[m \text{ mod } N] = x[ ( n + d ) \text{ mod } N] $$
ผลลัพธ์สุดท้ายคือตัวอย่างในกรอบการวิเคราะห์ถูกหมุนโดย $d$ ตัวอย่าง
ข้างต้น $z[n]$สามารถขยายได้โดยใช้นิยาม DFT ผกผันนอกกรอบการวิเคราะห์ที่สร้างลำดับ N เป็นระยะ มีเหตุผลน้อยกว่าที่จะสันนิษฐานว่าค่าเหล่านั้นจะตรงกับสัญญาณดั้งเดิม
คำถามของ OP คือสมมติว่า $ y[n] = x[n]-x[n-1] $คุณสามารถหา $Y[k]$ จาก $X[k]$ โดยไม่ต้องใช้ DFT ผกผันรับผลต่างจากนั้นจึงรับ DFT
OP ระบุว่า $x[n]$ มาจาก DFT ผกผันของ $X[k]$ในขณะที่ฉันเข้าใจผิดว่าเป็นต้นฉบับ $x[n]$ เป็นที่รู้จัก
จากนั้น Olli ได้รับคำตอบอย่างสง่างาม และมาจากนิยามในคำตอบของฉัน มีเงื่อนไขว่า$x[-1]= x[N-1]$ เป็นไปตามสัญญาณที่สร้างขึ้นใหม่
ดังนั้นจึงพูดปฏิเสธเป็นระยะนี้
การเติมเต็มและขึ้นอยู่กับคำตอบของ C. Dawg การละทิ้งการเพิ่มความชันผลกระทบต่อขนาดและเฟสคือ
$$ \begin{aligned} |X[k]| & \rightarrow M|X[k]| \\ \angle{(X[k])} & \rightarrow \phi + \angle{(X[k])} \\ \end{aligned} $$
ที่ไหน
$$ \begin{aligned} M &= 2 \left| \sin{\left( \pi \frac{k}{N} \right)} \right| \\ \phi &= \frac{\pi}{N}(k\ \text{mod}\ N- N/2) \cdot \lceil k\ \text{mod}\ N \rceil \end{aligned} $$
$\lceil k\ \text{mod}\ N \rceil$ ชุด $\phi$ ถึง 0 เมื่อ $k$ เป็นผลคูณของ $N$โดยใช้อนุสัญญา $\angle(0 + 0i)=0$. กราฟิก
โปรดทราบว่าไฟล์ $\phi$ เป็นเส้นตรงดังนั้นเอฟเฟกต์โดเมนเวลาคือการเปลี่ยนเวลา
iDFT : ดัชนีควรวิ่งจาก1ไปยังN - 1เนื่องจากความแตกต่าง จำกัด ลดลงตัวอย่าง นอกจากนี้การเพิ่มความลาดชันยังซ้ำซ้อน DFT ผกผันจะขยายสัญญาณดั้งเดิม N เป็นระยะดังนั้นจึงเป็นศูนย์
การใช้งาน Python ด้านล่าง; ทดสอบด้วยสัญญาณรบกวนปกติแบบสุ่มซึ่งเป็นสัญญาณที่ "ไม่ดีที่สุด" ซึ่งหมายความว่าข้อผิดพลาดสัมบูรณ์คือ1e-16ข้อผิดพลาดแบบลอย
def d_idft(coef):
N = len(coef)
coef = coef * (1 - np.exp(-1j * 2 * np.pi / N * np.arange(N)))
return np.fft.ifft(coef)[1:]
ภาคผนวก : ด้านล่างนี้เป็นความคิดเห็นของฉันตัดทอนจากการสนทนาด้านล่างคำตอบสรุปประเด็นสำคัญ / คำเตือนและขัดแย้งกับคำตอบที่ยอมรับ ไม่ได้รวมลำโพงอื่น ๆ ไว้เพราะจะใช้เวลานานมาก แต่ข้อความที่ตัดตอนมาที่แสดงควรบอกใบ้ถึงสิ่งที่ตอบสนอง
ระยะลาด :
"อนุพันธ์ที่ไม่ต่อเนื่องไม่มีความหมาย" - นี่ไม่ได้เกี่ยวกับอนุพันธ์แบบไม่ต่อเนื่อง แต่เกี่ยวกับ x [n] - x [n-1] ไม่ว่าจะตีความอย่างไร บางครั้งมันก็ดีพอ ๆ กับอนุพันธ์ในบางครั้งมันก็ถูกต้องในแง่ของการเลิกทำ cumsum แต่บางครั้งก็แทบจะไร้ประโยชน์ แต่ประเด็นก็คือการเปลี่ยนแปลงโดเมนเวลาซึ่งมีความถี่เทียบเท่ากับโดเมนที่เราต้องการ
เกี่ยวกับการได้มาที่ไม่ต่อเนื่องของคุณ เนื่องจากไม่มี x [-1] ให้เริ่มต้นทางเลือกเดียวคือผกผันซึ่งเท่ากับ x [N-1] ดังนั้นจึงลดลงอีกครั้ง
มันเป็นตัวแทนที่สมบูรณ์เกินไป ในการเข้ารหัสอนุพันธ์จุด N-1 จำเป็นต้องมีข้อมูล N + 1 (ค่าสัมประสิทธิ์ N เดิมบวก x [-1]) DFT เป็นการเข้ารหัสที่สมบูรณ์ เราสามารถแปลงกลับและแยกความแตกต่างในโดเมนเวลาโดยไม่จำเป็นต้องใช้ x [-1] ดังนั้นสิ่งเดียวกันจะต้องเป็นไปได้ที่จะทำงานในโดเมนความถี่เท่านั้น
พิจารณาตัวอย่างตอบโต้ สมมติว่าเราไม่เอา x [-1] มาจากการผกผัน มันจะต้องเป็นสัญญาณดั้งเดิมซึ่งเราจัดเฟรมไว้ แต่ที่ x [-1] มีอยู่ สมมติว่า x [0] ถึง x [N-1] เป็นศูนย์ทั้งหมดและ x [-1] = 100 ^ 100 ...
"DFT ถือว่าอินพุตเป็นช่วง"
ฉันบอกว่าการผกผันเมื่อขยายออกไปเป็นระยะ DTF อธิบายเฉพาะส่วนของสัญญาณดั้งเดิมที่ถูกป้อน - ไม่มากไม่น้อย เราสามารถขยายโดเมนเวลาเพื่อวิเคราะห์นามแฝงเป็นต้น แต่ไม่สามารถให้คำอธิบายใด ๆ เกี่ยวกับสัญญาณดั้งเดิมนอกเฟรมได้
รากเหง้าของการอภิปรายคือการไม่มีคำจำกัดความที่เพียงพอกล่าวคือสิ่งที่ "ถือว่า" ยังหมายถึง; คุณและฉันเห็นว่ามันไม่ได้เป็นพื้นฐานของการเปลี่ยนแปลง แต่เราก็เห็นด้วยกับบริบท / การดำเนินงานบางอย่างที่ต้องใช้เป็นระยะ
การหามาอย่างต่อเนื่อง ($x(n)$)
การแปลงไปข้างหน้า "กลับด้าน" ผกผันและการแปลงไปข้างหน้าของสัญญาณต่อเนื่องจะมี $N=\infty$. DTFT: การเข้ารหัสจะแทรกข้อมูลมากที่สุด (เช่นω) ตามที่ถอดรหัส (กลับด้าน) และสามารถแยกออกได้โดยพลการ ในทางตรงกันข้าม DFT ของสัญญาณต้องการค่าสัมประสิทธิ์จำนวนมากพอ ๆ กับจำนวนจุดในสัญญาณในขณะที่ผกผันของคุณถือว่ามีค่า จำกัด (หรือแตกต่างกันเพียงเล็กน้อย) N ดังนั้นจึงไม่ถอดรหัสสิ่งที่เข้ารหัส
มันแสดงถึงความสามารถในการบีบอัดที่ไม่มีที่สิ้นสุดอย่างไร้เหตุผลในขณะที่คุณกำลังคืนค่า x (n) ที่ไม่มีที่สิ้นสุดจากสัมประสิทธิ์ จำกัด ของ N
แต่จะเกิดอะไรขึ้นถ้าเราแยกความแตกต่างออกไป $x'(n)\rightarrow x'[n]$เหรอ? จากนั้นอาร์กิวเมนต์การบีบอัดจะตก นิพจน์ของคุณจัดการเสียงประสานเชิงเส้นได้ค่อนข้างดีในแง่ของรูปร่างเมื่อเทียบกับ np.diff และเนื่องจากอันหลังไม่ใช่อนุพันธ์ "จริง" จึงไม่ชัดเจนว่าข้อใด "ถูกต้องกว่า" มีงานทางคณิตศาสตร์ที่ต้องทำเพื่อปรับความแตกต่างอย่างต่อเนื่องแล้วแยกความแตกต่างอีกครั้ง แต่อาจทำได้ในภายหลัง
แก้ไข 2020/01/10 : จริงมันสามารถทำได้และมีการตีความว่าเป็นdiscretized (ไม่ต่อเนื่อง ) ที่มาของการแก้ไขตรีโกณมิติของ$x[n]$( ไม่ใช่ของ$x(n)$) และการแก้ไขที่ 'ดีกว่า' นั้นพอดี $x[n]$อนุพันธ์ที่แม่นยำยิ่งขึ้น คนแปลกหน้ายัง discretized FT และ DFT สามารถทำงานร่วมกันในบางครั้ง
อย่างไรก็ตามการมาของ Cedron ยังคงทำให้เป็นปกติอย่างไม่ถูกต้อง (แต่รหัสของเขาถูกต้อง); แปลก$x'[n]$พบว่าผ่านไม่ต่อเนื่อง IFT (iDFT) ของdiscretized FT อนุพันธ์ดังนั้นพิเศษ$2\pi / N$ไม่ได้เป็นของ ... หรืออาจจะอยู่ภายใต้สมมติฐานที่แตกต่างกัน แต่ฉันยังไม่เจอ
ผู้ชนะ : วิธีแก้ปัญหาของ Olli:
$$ F_{N-1}[k] = X_{N-1}[k]\big(e^{j2\pi k / (N - 1)} - 1\big) + (x[N-1] - x[0])e^{j2\pi k/(N-1)} $$
รหัส + การสาธิต :
def dft(x):
return np.fft.fft(x[:-1])
def d_idft(coef, x):
M = len(x) - 1 # N - 1
exp = np.exp(1j * (2 * np.pi / M) * np.arange(M))
coef = coef * (exp - 1) + (x[-1] - x[0]) * exp
return np.fft.ifft(coef)
แม้ว่าปัญหายังไม่สามารถแก้ไขได้ทั้งหมด คุณสมบัติทั้งหมด 1 & 2 พบการสูญเสียการสร้างใหม่เล็กน้อยและค่าสัมประสิทธิ์ที่คำนวณโดยตรงDFT(DIFF(x))และวิธีนี้แตกต่างกันเล็กน้อย "เล็กมาก" 1e-12ซึ่งอาจเป็นข้อผิดพลาดในการลอยของ FFT - รหัสเปรียบเทียบ
- ต้องการความสัมพันธ์ในแง่ของ $X_N=\text{FFT}(x)$ไม่ใช่ $X_{N−1}=\text{FFT}(x[\text{:-1}])$
- ไม่จำเป็นต้องใช้สัญญาณต้นฉบับเป็นอินพุตเพื่อคำนวณ $F_{N−1}$ (ไม่สามารถกู้คืนได้จาก $X_{N−1}$).
เนื่องจาก Olli สร้างนิพจน์ที่มีค่าสัมประสิทธิ์น้อยกว่า 1 ($X_{N−1}$) ในวิธีการแก้ปัญหาที่ยากขึ้นดังนั้นวิธีแก้ปัญหาสำหรับ (1) และ (2) จึงดูเหมือนจะเป็นไปได้
คำตอบนี้มีจุดมุ่งหมายเพื่อปรับแต่งปัญหาเพิ่มเติมทดสอบวิธีแก้ปัญหาที่เสนอและอธิบายข้อบกพร่องในคำตอบอื่น ๆ เพื่อเป็นแนวทางในการแก้ปัญหา
ระยะลาด : จำเป็นหรือไม่$x$เป็นระยะ ๆ หรือไม่ ปราศจากมัน,$Y[0] \neq \sum_{n=1}^{N-1} (x[n] - x[n-1])$. มันค่อนข้างเกี่ยวข้องกับทฤษฎีพื้นฐานของแคลคูลัส ถ้าความแตกต่าง จำกัด เป็นอนุพันธ์แล้ว$x[n]$ คือฤทธิ์ต้านการทำงานของฟังก์ชันที่เป็นผลต่าง จำกัด ดังนั้นผลรวมของ $Y[0]$ ค่อนข้างเรียบง่าย $x[N-1]-x[0]$ - [$\int_a^b f'(x)dx=f(b)-f(a)$].
อย่างแม่นยำมากขึ้น, $x[n-1]-x[0]$เท่ากับผลต่าง จำกัด สุทธิในช่วงเวลา พยายามบังคับให้ค่านี้เป็นอย่างอื่นโดยไม่เปลี่ยนจุดสิ้นสุด - คุณจะทำไม่ได้
คุณสมบัติคำตอบ - สิ่งที่นิพจน์ผลลัพธ์ต้องเป็นไปตาม:
len(Y) == N - 1; ความแตกต่าง จำกัด ใช้น้อยกว่า 1 เทอมx- $Y[0] = \sum_{n=1}^{N-1} (x[n] - x[n-1])$
- $Y$ แสดงในรูปของ $X$, $j$, $n$, $N$และอาจเป็นดัชนีของตัวเอง - ไม่มีพารามิเตอร์อื่น $x$ ดีตราบเท่าที่ภายใน $[0, N-1]$ซึ่งสามารถกู้คืนได้จาก $X$.
เหตุผลคุณสมบัติ :
คำตอบของ Olliแนะนำให้เปลี่ยนด้วย a N+1-point DFT & IDFT; สิ่งนี้ไม่ถูกต้องดังนั้นจึงเป็นความพยายามใด ๆ ที่จะไม่ทิ้งตัวอย่าง อาจพิสูจน์ได้ว่ามีประโยชน์ในบางแอปพลิเคชัน แต่มีข้อบกพร่องโดยพื้นฐานและด้วยเหตุนี้จึงไม่ใช่วัตถุประสงค์ทั่วไป นี่คือเหตุผล
จำ $+C$เมื่อรวม? เรื่องเดียวกัน: ความแตกต่างของการสูญเสียข้อมูล ปล่อย$x'[n] = x[n] - x[n-1]$. เราไม่สามารถเรียกคืนได้$x[n]$ จาก $x'[n]$มีเพียงรูปร่างเท่านั้น DC offsetจะหายไป หากเรารู้จักตัวอย่างต้นฉบับชิ้นใดชิ้นหนึ่ง$x[h]$เราสามารถกู้คืนสัญญาณทั้งหมดจาก $x'[n]$เนื่องจากเรารู้ $x[N-1]-x[0] = \sum x'[n]$แล้วเราจะพบ $x[n-1]$ ผ่านผลรวมสะสมเริ่มต้นที่ $x[h]$. คล้ายกับปัญหาค่าเริ่มต้น
ผลขิดโรฯ ,
$$ Y[k] = X[k]\left( 1 - e^{-i\frac{2\pi}{N}k} \right) + (x[N-1]-x[-1]), $$
ตรงตามคุณสมบัติใด ๆ เลยแต่เห็นได้ชัดว่าก้าวไปในทิศทางที่ถูกต้อง
ผลลัพธ์ของ Cedron + mod ทดสอบแล้ว (mod =$x[0]$ แทน $x[-1]$):
สเปกตรัมขนาดและเฟสที่แตกต่างกันอย่างมีนัยสำคัญทั้งสามแบบจะแปลงกลับด้านให้เป็นสัญญาณเดียวกันเกือบทั้งหมด ข้อผิดพลาดใด ๆ ที่ดูเหมือนว่าเป็นสาเหตุของความไม่แม่นยำ สีเขียวนี่คือ "ความจริงพื้นดิน" - รหัส .
จะเกิดอะไรขึ้นถ้าเราแก้ไขd_idftตามเหตุผลข้างต้น? กล่าวคือลดลงcoef[0]ระยะ DC:
def d_idft(coef, x, slope=True):
M = len(coef) - 1
coef = coef[1:] * (1 - np.exp(-1j * 2 * np.pi / M * np.arange(M)))
coef += (x[-1] - x[0])
return np.fft.ifft(coef)
ข้อผิดพลาดเพิ่มขึ้นอย่างมีนัยสำคัญ - ไม่ดี นอกจากนี้โปรดทราบว่าฉันผ่านxเป็นอินพุตเพื่อความสะดวกเท่านั้น
ถ้าสิ่งที่เรามีอยู่แล้วทำไมต้องดูต่อไป? (เช่น MAE ภายใน float64) - เพราะมันผิดและเพียงเพราะฉันไม่พบสัญญาณที่มี MAE ที่มีนัยสำคัญไม่ได้หมายความว่าไม่มีอยู่จริงหรือไม่มีผลกระทบที่ร้ายแรงในทางปฏิบัติ
สคริปต์ทดสอบ : คุณรู้ว่าโซลูชันของคุณใช้งานได้หากผ่านสคริปต์นี้