Аналіз (розробка) блок-схеми виконання алгоритму ШПФ на заданому типі процесора

Алгоритм базової операції ШПФ за основою 4 і проріджування за часом можна представити так:

А'₁ = А₁ + A₂W₁ + A₃W₂ + A₄W₃ = (А₁ + A₃W₂) + (A₂W₁ + A₄W₃),

A'₂ = A₁ jA₂W₁ – A₃W₂ ± jA₄W₃ = (A₁ – A₃W₂ ) j(A₂W₁ - A₄W₃ ),

A'₃ = A1 - A₂W₁ + A₃W₂ - A₄W₃ = (A₁ + A₃W₂) - (A₂W₁ + A₄W₃),

A'₄ = A₁ ± jA₂W₁ – A₃W₂ jA₄W₃ = (A₁ - A₃W₂) ± j(A₂W₁ - A₄W₃),

де A'₁, A'₂, А'з, А'₄ - результати базової операції; А₁, А₂, А₃, А₄ - вхідні відліки; W₁, W₂, W₃ - комплексні коефіцієнти; j - уявна одиниця, верхній знак перед j відповідає прямому, нижній - оберненому ШПФ.

ReA'₁ = [ReА₁ + (ReA₂*ReW₂ - ІmA₃*ImW₂)] + [(ReA₂*ReW₁ - ImA₂*ImW₁) + (ReA₄ *ReW₃ – ImA4*ImW3)],

ІмA'₁ = [Іm A₁ + (Re A₃*Im W₂ + ImA₃*Re W₂)] + [(ReA₂*ImW₁ + ІmA₂*ReW₁) + (ReA₄*ImW₃ + ImA₄*Re W₃)],

RеA'₂ = [ReA₁ - (ReA₃*ReW₂ - ImA₃*ImW₂)] ± [(ReA₂*ImW₁ + ImA₂*ReW₁) – (ReA₄*ІmW₃ + ImA₄*ReW₃)],

ImA'₂ = [ImA₁ - (ReA₃*ІmW₂ + ImA₃*ReW₂)] [(ReA₂*ReW₁ - ImA₂*ImW₁) - (ReA₄*ReW₃ - ImA₄*ImW₃)],

ReA'₃ = [ReA₁ + (ReA₃*ReW₂ - ImA₃*ImW₂)] - [(ReA₂*ReW₁ - ImA₂*ImW₁) + (ReA₄*ReW₃ - ImA₄*ImW₃)],

ІmA'₃ = [ІmA₁ + (ReA₃*ImW₂ + ImA₃*ReW₂)] - [(ReA₂*ImW₁ + ImA₂*ReW₁) +(ReA₄*lmW₃ + ImA₄*ReW₃)],

ReA'₄ = [ReA₁ - (ReA₃*ReW₂ – ImA₃*ImW₂)] [(ReA₂*ImW₁ + ImА₂*ReW₁) - (ReA4*ReW3 -ImA₄*ReW₃)],

ImA'₄ = [ImA₃ - (ReA₃*ImW₂ + ImA₃*ReW₂)] ± [(ReA₂*ReW₁ - ImA₂*Im W₁) - (ReA4*ReW3 – ImA₄*ImW₃)]

Для виконання базової операції вимагається виконати 12 операцій множення і 22 додавання.

Табл.5. Порядок слідування відліків для кожного ярусу

I	II	III	IV
…

 

Рис.5.3. Блок-схема 64-точкового перетворення за основою 4