Skip to content Skip to navigation

OpenStax-CNX

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

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

N = 17 Winograd FFT module in C

Module by: C. Sidney Burrus, Yuriy Reznik. E-mail the authorsTranslated By: Yuriy Reznik

Summary: A length-17 Winograd FFT translated from Fortran to C by Y. Reznik

N = 17 Winograd FFT module in C

N = 17 FFT C-code

typedef double real;
typedef struct {real r,i;} complex;

/*
 * Winograd's fast 17-point DFT: 
 *  x = input vector, y = DFT output 
 */
void Winograd_17pt_dft(complex *x, complex *y) 
{
  static real C1701 = -0.0426028491177360, C1702 = 0.2049796502326218;
  static real C1703 = 1.0451835201736758, C1704 = 1.7645848660222969;
  static real C1705 = -0.7234079772860566, C1706 = -0.0890555916206064;
  static real C1707 = -1.062500000000000, C1708 = 0.2576941016011038;
  static real C1709 = 0.7798026078948376, C1710 = 0.5438931846457058;
  static real C1711 = 0.4201019349705270, C1712 = 1.2810929434228074;
  static real C1713 = 0.4408890734817534, C1714 = 0.3171761928327251;
  static real C1715 = -0.9013831864801668, C1716 = -0.4324875636007231;
  static real C1717 = 0.6669353750404450, C1718 = -0.6038900431251697;
  static real C1719 = -0.3692487319858255, C1720 = 0.4865693875554976;
  static real C1721 = 0.2381371213676061, C1722 = -1.5573820617422459;
  static real C1723 = 0.6596224701873199, C1724 = -0.1431696156986624;
  static real C1725 = 0.2390346995986077, C1726 = -0.0479325419499726;
  static real C1727 = -2.3188014856550064, C1728 = 0.7891456841920625;
  static real C1729 = 3.8484572871179504, C1730 = -1.3003804568801376;
  static real C1731 = 4.0814769046889033, C1732 = -1.4807159909286282;
  static real C1733 = -0.0133324703635514, C1734 = -0.3713977869055763;
  static real C1735 = 0.1923651286345638; 

  real r100,r101,r102,r103,r104,r105,r106,r107,r108,r109,r110,r111,r112,r113,r114,r115;
  real r200,r201,r202,r203,r204,r205,r210,r211,r212,r213,r214,r215,r216,r217;
  real r31,r32,r33,r34,r35,r36,r37,r38,r39,r310,r311,r312,r313,r314,r315,r316,r317,r318,r319;
  real r320,r321,r322,r323,r324,r325,r326,r327,r328,r329,r330,r331,r332,r333,r334,r335;
  real t11,t12,t13,t14,t15,t16,t17,t18,t19,t110,t111,t112,t113,t114,t115,t116,t117,t118,t119;
  real t120,t121,t122,t123,t124,t125,t126,t127,t128,t129,t130,t131,t132,t133,t134,t135;
  real t200,t201,t202,t203,t204,t205,t206,t207,t208,t209,t210,t211,t212,t213,t214,t215,t216,t217;
  real t220,t221,t222,t223,t224,t225,t226,t227,t228,t229,t230,t231,t232,t233,t234,t235,t236,t237;
  real t238,t239,t240,t241,t242,t243,t244,t245,t246,t247;
  real t32,t33,t34,t35,t36,t37,t38,t39,t310,t311,t312,t313,t314,t315,t316,t317;

  real s100,s101,s102,s103,s104,s105,s106,s107,s108,s109,s110,s111,s112,s113,s114,s115;
  real s200,s201,s202,s203,s204,s205,s210,s211,s212,s213,s214,s215,s216,s217;
  real s31,s32,s33,s34,s35,s36,s37,s38,s39,s310,s311,s312,s313,s314,s315,s316,s317,s318,s319;
  real s320,s321,s322,s323,s324,s325,s326,s327,s328,s329,s330,s331,s332,s333,s334,s335;
  real u11,u12,u13,u14,u15,u16,u17,u18,u19,u110,u111,u112,u113,u114,u115,u116,u117,u118,u119;
  real u120,u121,u122,u123,u124,u125,u126,u127,u128,u129,u130,u131,u132,u133,u134,u135;
  real u200,u201,u202,u203,u204,u205,u206,u207,u208,u209,u210,u211,u212,u213,u214,u215,u216,u217;
  real u220,u221,u222,u223,u224,u225,u226,u227,u228,u229,u230,u231,u232,u233,u234,u235,u236,u237;
  real u238,u239,u240,u241,u242,u243,u244,u245,u246,u247;
  real u32,u33,u34,u35,u36,u37,u38,u39,u310,u311,u312,u313,u314,u315,u316,u317;

  // real part:
  r100 = x[1].r + x[16].r;
  r108 = x[1].r - x[16].r;
  r101 = x[3].r + x[14].r;
  r109 = x[3].r - x[14].r;
  r102 = x[9].r + x[8].r;
  r110 = x[9].r - x[8].r;
  r103 = x[10].r + x[7].r;
  r111 = x[10].r - x[7].r;
  r104 = x[13].r + x[4].r;
  r112 = x[13].r - x[4].r;
  r105 = x[5].r + x[12].r;
  r113 = x[5].r - x[12].r;
  r106 = x[15].r + x[2].r;
  r114 = x[15].r - x[2].r;
  r107 = x[11].r + x[6].r;
  r115 = x[11].r - x[6].r;

  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;
  y[0].r = x[0].r + 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 + y[0].r;
  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;

  // imaginary part:
  s100 = x[1].i + x[16].i;
  s108 = x[1].i - x[16].i;
  s101 = x[3].i + x[14].i;
  s109 = x[3].i - x[14].i;
  s102 = x[9].i + x[8].i;
  s110 = x[9].i - x[8].i;
  s103 = x[10].i + x[7].i;
  s111 = x[10].i - x[7].i;
  s104 = x[13].i + x[4].i;
  s112 = x[13].i - x[4].i;
  s105 = x[5].i + x[12].i;
  s113 = x[5].i - x[12].i;
  s106 = x[15].i + x[2].i;
  s114 = x[15].i - x[2].i;
  s107 = x[11].i + x[6].i;
  s115 = x[11].i - x[6].i;

  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[0].i = x[0].i + 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[0].i;
  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;

  // mix and output:
  y[1].r  = t32  - u310;
  y[16].r = t32  + u310;
  y[1].i  = t310 + u32;
  y[16].i =-t310 + u32;
  y[2].r  = t33  - u311;
  y[15].r = t33  + u311;
  y[2].i  = t311 + u33;
  y[15].i =-t311 + u33;
  y[3].r  = t34  - u312;
  y[14].r = t34  + u312;
  y[3].i  = t312 + u34;
  y[14].i =-t312 + u34;
  y[4].r  = t35  - u313;
  y[13].r = t35  + u313;
  y[4].i  = t313 + u35;
  y[13].i =-t313 + u35;
  y[5].r  = t36  - u314;
  y[12].r = t36  + u314;
  y[5].i  = t314 + u36;
  y[12].i =-t314 + u36;
  y[6].r  = t37  - u315;
  y[11].r = t37  + u315;
  y[6].i  = t315 + u37;
  y[11].i =-t315 + u37;
  y[7].r  = t38  - u316;
  y[10].r = t38  + u316;
  y[7].i  = t316 + u38;
  y[10].i =-t316 + u38;
  y[8].r  = t39  - u317;
  y[9].r  = t39  + u317;
  y[8].i  = t317 + u39;
  y[9].i  =-t317 + u39;
}

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