DSP - การคำนวณในสถานที่
การใช้หน่วยความจำอย่างมีประสิทธิภาพนี้เป็นสิ่งสำคัญสำหรับการออกแบบฮาร์ดแวร์ที่รวดเร็วเพื่อคำนวณ FFT คำว่าการคำนวณแบบแทนที่ใช้เพื่ออธิบายการใช้หน่วยความจำนี้
การลดลงตามลำดับเวลา
ในโครงสร้างนี้เราแสดงจุดทั้งหมดในรูปแบบไบนารีเช่นใน 0 และ 1 จากนั้นเราจะย้อนกลับโครงสร้างเหล่านั้น ลำดับที่เราได้รับหลังจากนั้นเรียกว่าลำดับการกลับรายการบิต สิ่งนี้เรียกอีกอย่างว่าการสลายตัวตามลำดับเวลา การคำนวณแบบแทนที่ของ DFT แปดจุดจะแสดงในรูปแบบตารางดังที่แสดงด้านล่าง -
คะแนน | รูปแบบไบนารี | REVERSAL | คะแนนเทียบเท่า |
---|---|---|---|
0 | 000 | 000 | 0 |
1 | 001 | 100 | 4 |
2 | 010 | 010 | 2 |
3 | 011 | 110 | 6 |
4 | 100 | 001 | 1 |
5 | 101 | 101 | 5 |
6 | 110 | 011 | 3 |
7 | 111 | 111 | 7 |
การลดลงในลำดับความถี่
นอกเหนือจากลำดับเวลาแล้วยังสามารถแสดงลำดับจุด N เป็นความถี่ได้อีกด้วย ให้เราใช้ลำดับสี่จุดเพื่อทำความเข้าใจให้ดีขึ้น
ให้ลำดับเป็น $ x [0], x [1], x [2], x [3], x [4], x [5], x [6], x [7] $ เราจะจับกลุ่มสองจุดเป็นกลุ่มเดียวในตอนแรก ในทางคณิตศาสตร์ลำดับนี้สามารถเขียนเป็น;
$$ x [k] = \ sum_ {n = 0} ^ {N-1} x [n] W_N ^ {nk} $$ตอนนี้ให้เราสร้างกลุ่มของลำดับหมายเลข 0 ถึง 3 กลุ่มหนึ่งและอีกกลุ่มของลำดับที่ 4 ถึง 7 ตอนนี้ในทางคณิตศาสตร์สามารถแสดงได้ดังนี้
$$ \ displaystyle \ sum \ LIMIT_ {n = 0} ^ {\ frac {N} {2} -1} x [n] W_N ^ {nk} + \ displaystyle \ sum \ LIMIT_ {n = N / 2} ^ {N-1} x [n] W_N ^ {nk} $$ให้เราแทนที่ n ด้วย r โดยที่ r = 0, 1, 2 …. (N / 2-1) ในทางคณิตศาสตร์
$$ \ displaystyle \ sum \ LIMIT_ {n = 0} ^ {\ frac {N} {2} -1} x [r] W_ {N / 2} ^ {nr} $$เรานำสี่จุดแรก (x [0], x [1], x [2], x [3]) ในตอนแรกและพยายามแทนค่าทางคณิตศาสตร์ดังนี้ -
$ \ sum_ {n = 0} ^ 3x [n] W_8 ^ {nk} + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {(n + 4) k} $
$ = \ lbrace \ sum_ {n = 0} ^ 3x [n] + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {(4) k} \ rbrace \ times W_8 ^ {nk} $
ตอนนี้$ X [0] = \ sum_ {n = 0} ^ 3 (X [n] + X [n + 4]) $
$ X [1] = \ sum_ {n = 0} ^ 3 (X [n] + X [n + 4]) W_8 ^ {nk} $
$ = [X [0] -X [4] + (X [1] -X [5]) W_8 ^ 1 + (X [2] -X [6]) W_8 ^ 2 + (X [3] -X [7]) W_8 ^ 3 $
เราสามารถแบ่งมันออกเป็นสองส่วนได้อีกซึ่งหมายความว่าแทนที่จะแบ่งเป็นลำดับ 4 จุดเราสามารถแบ่งมันออกเป็นลำดับ 2 จุดได้