1CORDIC ALGORITHM AND IMPLEMENTATIONS• CORDIC METHOD• ROTATION AND VECTORING MODE• CONVERGENCE, PRECISION AND RANGE• SCALING FACTOR AND COMPENSATION• IMPLEMENTATIONS: word-serial and pipelined• EXTENSION TO HYPERBOLIC AND LINEAR COORDINATES• UNIFIED DESCRIPTION• REDUNDANT ADDITION AND HIGH RADIXDigital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC2MAIN USES• REALIZATION OF ROTATIONS• CALCULATION OF TRIGONOMETRIC FUNCTIONS• CALCULATION OF INVERSE TRIGONOMETRIC FUNCTION tan−1(a/b)• CALCULATION OF√a2+ b2, etc.• EXTENDED TO HYPERBOLIC FUNCTIONS• DIVISION AND MULTIPLICATION• CALCULATION OF SQRT, LOG, AND EXP• FOR LINEAR TRANSFORMS, DIGITAL FILTERS, AND SOLVING LIN. SYS-TEMS• MAIN APPLICATIONS: DSP, IMAGE PROCESSING, 3D GRAPHICS, ROBOTICS.Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC3CORDIC ALGORITHM• CIRCULAR COORDINATE SYSTEM• PERFECT ROTATION:xR= Mincos(β + θ) = xincos θ − yinsin θyR= Minsin(β + θ) = xinsin θ + yincos θ• Min– THE MODULUS OF THE VECTOR• β – THE INITIAL ANGLE• IN MATRIX FORM:xRyR=cos θ −sin θsin θ cos θxinyin= ROT (θ)xinyinDigital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC4yx(xin, yin )(xR, yR )ΘβMinFigure 11.1: VECTOR ROTATIONDigital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC5MICRO-ROTATIONS• USE ELEMENTARY ROTATION ANGLES αj• DECOMPOSE THE ANGLE θ:θ =∞Xj=0αjSO THATROT (θ) =∞Yj=0ROT (αj)• THEN ROT (αj):xR[j + 1] = xR[j] cos(αj) − yR[j] sin(αj)yR[j + 1] = xR[j] sin(αj) + yR[j] cos(αj)Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC6SIMPLIFYING MICRO-ROTATIONS• HOW TO AVOID MULTIPLICATIONS?1. DECOMPOSE ROTATION INTO:SCALING OPERATION AND ROTATION-EXTENSIONxR[j + 1] = cos(αj)(xR[j] − yR[j] tan(αj))yR[j + 1] = cos(αj)(yR[j] + xR[j] tan(αj))2. CHOOSE ELEMENTARY ANGLESαj= tan−1(σj(2−j)) = σjtan−1(2−j)WITH σj∈ {−1, 1}RESULTS IN ROTATION-EXTENSION RECURRENCE WITHOUT MPYsx[j + 1] = x[j] − σj2−jy[j]y[j + 1] = y[j] + σj2−jx[j]=⇒ONLY ADDITIONS AND SHIFTSDigital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC7ROTATION-EXTENSION (cont.)• ROTATION-EXTENSION SCALES MODULUS M[j]M[j+1] = K[j]M[j] =1cos αjM[j] = (1+σ2j2−2j)1/2M[j] = (1+2−2j)1/2M[j]• TOTAL SCALING FACTORK =∞Yj=0(1 + 2−2j)1/2≈ 1.6468CONSTANT, INDEPENDENT OF THE ANGLE• RECURRENCE FOR DECOMPOSITION/ACCUMULATION OF ANGLE:z[j + 1] = z[j] − αj= z[j] − σjtan−1(2−j)Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC8IMPLEMENTATION OF CORDIC ITERATIONCORDIC MICROROTATIONx[j + 1] = x[j] − σj2−jy[j]y[j + 1] = y[j] + σj2−jx[j]z[j + 1] = z[j] − σjtan−1(2−j)Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC9ADD/SUBσjX[j]X[j+1]SHIFTERjADD/SUBY[j]Y[j+1]SHIFTERjZ[j]Z[j+1]αjADD/SUBTABLEjσjσjσj+1 = {sign(Y[j+1]) in vectoringsign(Z[j+1]) in rotationADD/SUB module includes conditional complementersign(Y)sign(Z)MUXFigure 11.2: IMPLEMENTATION OF ONE ITERATION.Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC10ROTATION MODE• ROTATE AN INITIAL VECTOR (xin, yin) BY θ• DECOMPOSE THE ANGLEz[j + 1] = z[j] − σjtan−1(2−j)z[0] = θ x[0] = xiny[0] = yinσj=1 if z[j] ≥ 0−1 if z[j] < 0• PERFORM MICRO-ROTATIONS• FINAL VALUESxf= K(xincos θ − yinsin θ)yf= K(xinsin θ + yincos θ)zf= 0Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC11yx(xin, yin )Θ(x1,y1)(x2,y2)(x3,y3)(xf,, yf)primitive anglesFigure 11.3: Rotating a vector using microrotations.Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC12EXAMPLE OF ROTATIONROTATE (xin, yin) BY 67◦USING n = 12 MICRO-ROTATIONSINITIAL COORDINATES: xin= 1, yin= 0.125FINAL COORDINATES: xR= 0.2756, yR= 0.9693j z[j] σjx[j] y[j]0 1.1693 1 1.0 0.1251 0.3839 1 0.875 1.1252 -0.0796 -1 0.3125 1.15623 0.1653 1 0.7031 1.48434 0.0409 1 0.5175 1.57225 -0.0214 -1 0.4193 1.60466 0.0097 1 0.4694 1.59157 -0.0058 -1 0.4445 1.59888 0.0019 1 0.4570 1.59539 -0.0019 -1 0.4508 1.597110 0.0000 1 0.4539 1.596211 -0.0009 -1 0.4524 1.596712 -0.0004 -1 0.4531 1.596513 0.4535 1.5963Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC13EXAMPLE 11.1 (cont.)• AFTER COMPENSATION OF SCALING FACTOR K = 1.64676COORDINATES ARE x[13]/K = 0.2753 and y[13]/K = 0.9693• ERRORS < 2−12Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC14SPECIAL CASES• TO COMPUTE cos θ AND sin θMAKE INITIAL CONDITION x[0] = 1/K AND y[0] = 0• IN GENERAL, FOR a AND b CONSTANTSa cos θ − b sin θa sin θ + b cos θCOMPUTED BY SETTING x[0] = a/K AND y[0] = b/KDigital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC15VECTORING MODE• ROTATE INITIAL VECTOR (xin, yin) UNTIL y = 0• FOR INITIAL VECTOR IN THE FIRST QUADRANT:σj=1 if y[j] < 0−1 if y[j] ≥ 0• ACCUMULATE ROTATION ANGLE IN z• FOR x[0] = xin, y[0] = yinand z[0] = zin, THE FINAL VALUES ARExf= K(x2in+ y2in)1/2yf= 0zf= zin+ tan−1(yinxin)Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC16EXAMPLE OF VECTORING• INITIAL VECTOR (xin= 0.75, yin= 0.43)• y FORCED TO ZERO IN n = 12 MICRO-ROTATIONS• ROTATED VECTOR: xR=rx2in+ y2in= 0.8645, yR= 0.0• ROTATED ANGLE zf= tan−1(0.430.75) = 0.5205Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC17j y[j] σjx[j] z[j]0 0.43 -1 0.75 0.01 -0.32 1 1.18 0.78532 0.27 -1 1.34 0.32173 -0.065 1 1.4075 0.56674 0.1109 -1 1.4156 0.44235 0.0224 -1 1.4225 0.50476 -0.0219 1 1.4232 0.53607 0.0002 -1 1.4236 0.52048 -0.0108 1 1.4236 0.52829 -0.0053 1 1.4236 0.524310 -0.0025 1 1.4236 0.522311 -0.0011 1 1.4236 0.521312 -0.0004 1 1.4236 0.520813 1.4236 0.5206Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC18EXAMPLE 11.2 (cont.)• ACCUMULATED ANGLE z[13] = 0.5206• AFTER PERFORMING COMPENSATION OF K = 1.64676,x[13]/K = 0.864• ERRORS < 2−12Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC19CONVERGENCE, PRECISION, AND RANGE• ROTATION MODE• CONVERGENCE|z[i]| ≤∞Xj=itan−1(2−j)θmax= z[0]max=∞Xj=0tan−1(2−j) ≈ 1.7429 (99.88o)FOR THIS ANGLE ALL σj= 1 and z[j] > 0.• CONSIDER θ < θmax|z[i]| ≤ tan−1(2−(i−1))• CONSEQUENTLYtan−1(2−i−1) ≤∞Xj=itan−1(2−j)ORtan−1(2−i) ≤∞Xj=i+1tan−1(2−j)SATISFIED FOR ALL iDigital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC20yxαi-2αi-1αiFigure 11.4: CONVERGENCE CONDITION: THE MAXIMUM NEGATIVE CASE.Digital Arithmetic - Ercegovac/Lang 2003 11 – CORDIC21PRECISION AND RANGE FOR n ITERATIONS• n