Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » N = 17 Winograd FFT module

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This module is included in aLens by: Digital Scholarship at Rice UniversityAs a part of collection: "Large DFT Modules: 11, 13, 16, 17, 19, and 25. Revised ECE Technical Report 8105 "

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Large DFT Modules: 11, 13, 16, 17, 19, and 25. Revised ECE Technical Report 8105 "

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.
 

N = 17 Winograd FFT module

Module by: Howard Johnson, C. Sidney Burrus. E-mail the authors

Summary: A very efficient length N = 17 FFT module that can be use alone or with the PFA or the WFTA. Designed by Howard Johnson in 1981.

N=17 FFT module

A FORTRAN implementation of a length-17 FFT module to be used in a Prime Factor Algorithm program. Errors discovered by Yuri Reznik have been corrected (8/17/11).

C
C-------------------WFTA N=17----------------------------
C
C 314 ADDS; 70 MPYS
C DATA FOR LENGTH 17 DFT
DATA C1701  /    -.0426028491177360 /
DATA C1702  /     .2049796502326218 /
DATA C1703  /    1.0451835201736758 /
DATA C1704  /    1.7645848660222969 /
DATA C1705  /    -.7234079772860566 /
DATA C1706  /    -.0890555916206064 /
DATA C1707  /   -1.0625000000000000 /
DATA C1708  /     .2576941016011038 /
DATA C1709  /     .7798026078948376 /
DATA C1710  /     .5438931846457058 /
DATA C1711  /     .4201019349705270 /
DATA C1712  /    1.2810929434228074 /
DATA C1713  /     .4408890734817534 /
DATA C1714  /     .3171761928327251 /
DATA C1715  /    -.9013831864801668 /
DATA C1716  /    -.4324875636007231 /
DATA C1717  /     .6669353750404450 /
DATA C1718  /    -.6038900431251697 /
DATA C1719  /    -.3692487319858255 /
DATA C1720  /     .4865693875554976 /
DATA C1721  /     .2381371213676061 /
DATA C1722  /   -1.5573820617422459 /
DATA C1723  /     .6596224701873199 /
DATA C1724  /    -.1431696156986624 /
DATA C1725  /     .2390346995986077 /
DATA C1726  /    -.0479325419499726 /
DATA C1727  /   -2.3188014856550064 /
DATA C1728  /     .7891456841920625 /
DATA C1729  /    3.8484572871179504 /
DATA C1730  /   -1.3003804568801376 /
DATA C1731  /    4.0814769046889033 /
DATA C1732  /   -1.4807159909286282 /
DATA C1733  /    -.0133324703635514 /
DATA C1734  /    -.3713977869055763 /
DATA C1735  /     .1923651286345638 /
C
C-----------------WFTA N=17--------------------------
C 
R100=X(I(2))+X(I(17))
R108=X(I(2))-X(I(17))
R101=X(I(4))+X(I(15))
R109=X(I(4))-X(I(15))
R102=X(I(10))+X(I(9))
R110=X(I(10))-X(I(9))
R103=X(I(11))+X(I(8))
R111=X(I(11))-X(I(8))
R104=X(I(14))+X(I(5))
R112=X(I(14))-X(I(5))
R105=X(I(6))+X(I(13))
R113=X(I(6))-X(I(13))
R106=X(I(16))+X(I(3))
R114=X(I(16))-X(I(3))
R107=X(I(12))+X(I(7))
R115=X(I(12))-X(I(7))
R200=R100+R104
R201=R101+R105
R202=R102+R106
R203=R103+R107
R204=R200+R202
R205=R201+R203
R31=R100-R104
R32=R101-R105
R33=R102-R106
R34=R103-R107
R35=R200-R202
R36=R201-R203
R37=R204+R205
R38=R204-R205
R39=R32+R34
R310=R31+R33
R311=R310-R39
R312=R33-R34
R313=R31-R32
R314=R35+R36
R210=R108+R110
R211=R109+R111
R212=R108-R110
R213=R115-R113
R214=R112+R114
R215=R113+R115
R216=R112-R114
R217=R109-R111
R315=R210+R211
R316=R214+R215
R317=R315+R316
R318=R210-R211
R319=R214-R215
R320=R318+R319
R321=R212+R213
R322=R216+R217
R323=R321+R322
R324=R212-R213
R325=R216-R217
R326=R324+R325
R327=R108+R112
R328=R108
R329=R112
R330=R111+R115
R331=R111
R332=R115
R333=R322-R316+R108-R330
R334=R315-R321+R111+R112-R115
R335=R333+R334
X(I(1))=X(I(1))+R37
T11=R31*C1701
T12=R32*C1702
T13=R33*C1703
T14=R34*C1704
T15=R35*C1705
T16=R36*C1706
T17=R37*C1707
T18=R38*C1708
T19=R39*C1709
T110=R310*C1710
T111=R311*C1711
T112=R312*C1712
T113=R313*C1713
T114=R314*C1714
T115=R315*C1715
T116=R316*C1716
T117=R317*C1717
T118=R318*C1718
T119=R319*C1719
T120=R320*C1720
T121=R321*C1721
T122=R322*C1722
T123=R323*C1723
T124=R324*C1724
T125=R325*C1725
T126=R326*C1726
T127=R327*C1727
T128=R328*C1728
T129=R329*C1729
T130=R330*C1730
T131=R331*C1731
T132=R332*C1732
T133=R333*C1733
T134=R334*C1734
T135=R335*C1735
T17=T17+X(I(1))
T200=T19+T111
T201=T110-T111
T202=T14+T112
T203=T112-T13
T204=T12+T113
T205=T11-T113
T206=T114-T16
T207=T114+T15
T208=T18+T17
T209=T17-T18
T210=T200-T202
T211=T206+T208
T212=T201+T203
T213=T207+T209
T214=T200+T204
T215=-T206+T208
T216=T201+T205
T217=-T207+T209
T32=T210+T211
T37=T212+T213
T33=T214+T215
T36=T216+T217
T35=-T210+T211
T38=-T212+T213
T39=-T214+T215
T34=-T216+T217
T220=T115+T117
T221=T116+T117
T222=T118+T120
T223=T119+T120
T224=T121+T123
T225=T122+T123
T226=T124+T126
T227=T125+T126
T228=T135+T134
T229=T127+T228
T230=T229+T128
T231=T220+T222
T232=T220-T222
T233=T221+T223
T234=T221-T223
T235=T224+T226
T236=T224-T226
T237=T225+T227
T238=T225-T227
T239=T133-T134
T240=T229+T129
T241=T239+T239
T242=T130-T241
T243=T242+T131
T244=-T242-T132
T245=T228+T228
T246=T245+T245
T247=T239+T245
T310=T233+T237+T240
T315=T232-T238+T243
T311=T231-T235+T245
T314=-T232-T238-T247
T313=T231+T235+T230+T239
T316=-T234-T236+T244+T246
T317=-T233+T237+T241+T245
T312=T234-T236-T239
S100=Y(I(2))+Y(I(17))
S108=Y(I(2))-Y(I(17))
S101=Y(I(4))+Y(I(15))
S109=Y(I(4))-Y(I(15))
S102=Y(I(10))+Y(I(9))
S110=Y(I(10))-Y(I(9))
S103=Y(I(11))+Y(I(8))
S111=Y(I(11))-Y(I(8))
S104=Y(I(14))+Y(I(5))
S112=Y(I(14))-Y(I(5))
S105=Y(I(6))+Y(I(13))
S113=Y(I(6))-Y(I(13))
S106=Y(I(16))+Y(I(3))
S114=Y(I(16))-Y(I(3))
S107=Y(I(12))+Y(I(7))
S115=Y(I(12))-Y(I(7))
S200=S100+S104
S201=S101+S105
S202=S102+S106
S203=S103+S107
S204=S200+S202
S205=S201+S203
S31=S100-S104
S32=S101-S105
S33=S102-S106
S34=S103-S107
S35=S200-S202
S36=S201-S203
S37=S204+S205
S38=S204-S205
S39=S32+S34
S310=S31+S33
S311=S310-S39
S312=S33-S34
S313=S31-S32
S314=S35+S36
S210=S108+S110
S211=S109+S111
S212=S108-S110
S213=S115-S113
S214=S112+S114
S215=S113+S115
S216=S112-S114
S217=S109-S111
S315=S210+S211
S316=S214+S215
S317=S315+S316
S318=S210-S211
S319=S214-S215
S320=S318+S319
S321=S212+S213
S322=S216+S217
S323=S321+S322
S324=S212-S213
S325=S216-S217
S326=S324+S325
S327=S108+S112
S328=S108
S329=S112
S330=S111+S115
S331=S111
S332=S115
S333=S322-S316+S108-S330
S334=S315-S321+S111+S112-S115
S335=S333+S334
Y(I(1))=Y(I(1))+S37
U11=S31*C1701
U12=S32*C1702
U13=S33*C1703
U14=S34*C1704
U15=S35*C1705
U16=S36*C1706
U17=S37*C1707
U18=S38*C1708
U19=S39*C1709
U110=S310*C1710
U111=S311*C1711
U112=S312*C1712
U113=S313*C1713
U114=S314*C1714
U115=S315*C1715
U116=S316*C1716
U117=S317*C1717
U118=S318*C1718
U119=S319*C1719
U120=S320*C1720
U121=S321*C1721
U122=S322*C1722
U123=S323*C1723
U124=S324*C1724
U125=S325*C1725
U126=S326*C1726
U127=S327*C1727
U128=S328*C1728
U129=S329*C1729
U130=S330*C1730
U131=S331*C1731
U132=S332*C1732
U133=S333*C1733
U134=S334*C1734
U135=S335*C1735
U17=U17+Y(I(1))
U200=U19+U111
U201=U110-U111
U202=U14+U112
U203=U112-U13
U204=U12+U113
U205=U11-U113
U206=U114-U16
U207=U114+U15
U208=U18+U17
U209=U17-U18
U210=U200-U202
U211=U206+U208
U212=U201+U203
U213=U207+U209
U214=U200+U204
U215=-U206+U208
U216=U201+U205
U217=-U207+U209
U32=U210+U211
U37=U212+U213
U33=U214+U215
U36=U216+U217
U35=-U210+U211
U38=-U212+U213
U39=-U214+U215
U34=-U216+U217
U220=U115+U117
U221=U116+U117
U222=U118+U120
U223=U119+U120
U224=U121+U123
U225=U122+U123
U226=U124+U126
U227=U125+U126
U228=U135+U134
U229=U127+U228
U230=U229+U128
U231=U220+U222
U232=U220-U222
U233=U221+U223
U234=U221-U223
U235=U224+U226
U236=U224-U226
U237=U225+U227
U238=U225-U227
U239=U133-U134
U240=U229+U129
U241=U239+U239
U242=U130-U241
U243=U242+U131
U244=-U242-U132
U245=U228+U228
U246=U245+U245
U247=U239+U245
U310=U233+U237+U240
U315=U232-U238+U243
U311=U231-U235+U245
U314=-U232-U238-U247
U313=U231+U235+U230+U239
U316=-U234-U236+U244+U246
U317=-U233+U237+U241+U245
U312=U234-U236-U239
X(I(2))=T32-U310
X(I(17))=T32+U310
Y(I(2))=T310+U32
Y(I(17))=-T310+U32
X(I(3))=T33-U311
X(I(16))=T33+U311
Y(I(3))=T311+U33
Y(I(16))=-T311+U33
X(I(4))=T34-U312
X(I(15))=T34+U312
Y(I(4))=T312+U34
Y(I(15))=-T312+U34
X(I(5))=T35-U313
X(I(14))=T35+U313
Y(I(5))=T313+U35
Y(I(14))=-T313+U35
X(I(6))=T36-U314
X(I(13))=T36+U314
Y(I(6))=T314+U36
Y(I(13))=-T314+U36
X(I(7))=T37-U315
X(I(12))=T37+U315
Y(I(7))=T315+U37
Y(I(12))=-T315+U37
X(I(8))=T38-U316
X(I(11))=T38+U316
Y(I(8))=T316+U38
Y(I(11))=-T316+U38
X(I(9))=T39-U317
X(I(10))=T39+U317
Y(I(9))=T317+U39
Y(I(10))=-T317+U39
C
    GOTO 20
C
 
Figure.  Length-17 FFT Module

References

    Content actions

    Download module as:

    Add module to:

    My Favorites (?)

    'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

    | A lens I own (?)

    Definition of a lens

    Lenses

    A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

    What is in a lens?

    Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

    Who can create a lens?

    Any individual member, a community, or a respected organization.

    What are tags? tag icon

    Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

    | External bookmarks