Hello, A survey of the literature on the net shows people showing how it could be done using the Cordic algorithm using cordic processing elements, where in each processing element calculates the cosine, sine of the angles required for the process. Some other papers showed how this could be done using distributed arithmetic methods where the cosine values are stored in lookup tables. Why if we can store the cosine values in lookup tables do people use cordic processing elements implemented in hardware to calculate things like the DCT? Does this have any advantages? Thanks for the help Warm Regards Johnsy
Various methods for implementing the DCT
Started by ●November 8, 2004
Reply by ●November 10, 20042004-11-10
On some processor architectures, memory can be expensive, so a LUT cannot be done. On the other hand, implementing CORDIC in specialized hardware can be very fast. So it really depends on the particular application - and the environment - what method is best for calculating the DCT (or any other transform). -- Stephan M. Bernsee http://www.dspdimension.com
Reply by ●November 10, 20042004-11-10
Stephan M. Bernsee <spam@dspdimension.com> wrote in message news:<2veib9F2l8l0cU1@uni-berlin.de>...> On some processor architectures, memory can be expensive, so a LUT > cannot be done. On the other hand, implementing CORDIC in specialized > hardware can be very fast. > > So it really depends on the particular application - and the > environment - what method is best for calculating the DCT (or any other > transform).If implemented in software polynomial approximations may also be used. One standard method for this is Horner's algorithm but i was wondering if any kind of polynomial approach is used in hardware implementation as well...? -Nithin
Reply by ●November 10, 20042004-11-10
Nithin wrote:> Stephan M. Bernsee <spam@dspdimension.com> wrote in message news:<2veib9F2l8l0cU1@uni-berlin.de>... > >>On some processor architectures, memory can be expensive, so a LUT >>cannot be done. On the other hand, implementing CORDIC in specialized >>hardware can be very fast. >> >>So it really depends on the particular application - and the >>environment - what method is best for calculating the DCT (or any other >>transform). > > > If implemented in software polynomial approximations may also be used. > One standard method for this is Horner's algorithm but i was wondering > if any kind of polynomial approach is used in hardware implementation > as well...?Horner's method finds roots. How is it used to find trig functions? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●November 11, 20042004-11-11
>>>>> "Jerry" == Jerry Avins <jya@ieee.org> writes:Jerry> Nithin wrote: >> Stephan M. Bernsee <spam@dspdimension.com> wrote in message news:<2veib9F2l8l0cU1@uni-berlin.de>... >> >>> On some processor architectures, memory can be expensive, so a LUT >>> cannot be done. On the other hand, implementing CORDIC in specialized >>> hardware can be very fast. >>> >>> So it really depends on the particular application - and the >>> environment - what method is best for calculating the DCT (or any other >>> transform). >> >> >> If implemented in software polynomial approximations may also be used. >> One standard method for this is Horner's algorithm but i was wondering >> if any kind of polynomial approach is used in hardware implementation >> as well...? Jerry> Horner's method finds roots. How is it used to find trig functions? It's also a method of evaluating polynomials. You know, instead of x^2+a*x+b directly, you evaluate (x + a)*x + b. Ray
Reply by ●November 11, 20042004-11-11
Raymond Toy wrote:>>>>>>"Jerry" == Jerry Avins <jya@ieee.org> writes: > > > Jerry> Nithin wrote: > >> Stephan M. Bernsee <spam@dspdimension.com> wrote in message news:<2veib9F2l8l0cU1@uni-berlin.de>... > >> > >>> On some processor architectures, memory can be expensive, so a LUT > >>> cannot be done. On the other hand, implementing CORDIC in specialized > >>> hardware can be very fast. > >>> > >>> So it really depends on the particular application - and the > >>> environment - what method is best for calculating the DCT (or any other > >>> transform). > >> > >> > >> If implemented in software polynomial approximations may also be used. > >> One standard method for this is Horner's algorithm but i was wondering > >> if any kind of polynomial approach is used in hardware implementation > >> as well...? > > Jerry> Horner's method finds roots. How is it used to find trig functions? > > It's also a method of evaluating polynomials. You know, instead of > x^2+a*x+b directly, you evaluate (x + a)*x + b.Evaluating [(x + a)*x + b]x + c with Horner's method needs less computation than working it out directly when x is known? I don't see it. I'll look again. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●November 11, 20042004-11-11
"Jerry Avins" <jya@ieee.org> wrote in message news:2vhgfeF2k0m36U1@uni-berlin.de...> Raymond Toy wrote: > > > It's also a method of evaluating polynomials. You know, instead of > > x^2+a*x+b directly, you evaluate (x + a)*x + b. > > Evaluating [(x + a)*x + b]x + c with Horner's method needs less > computation than working it out directly when x is known? I don't see > it. I'll look again.Compared with the "direct method", Horner's method trades multiplies for adds and additionally is computationally more efficient for higher degrees. In the case of a quadratic, there is no computational efficiency gain in an architecture where adds and multiplies cost the same (Horner = 3 adds, 2 multiplies, direct = 2 adds, 3 multiplies). But for a cubic equation, the direct method requires 2 more multiplies and 1 more add, whereas Horner requires only one more multiply and one more add. For higher degrees, the savings is even more pronounced. Also, it may be a bit simpler to implement the Horner method because of the regular structure of the computations. (Don't know if that is an advantage or not.)
Reply by ●November 11, 20042004-11-11
Jerry Avins <jya@ieee.org> wrote in message news:<2vhgfeF2k0m36U1@uni-berlin.de>...> Raymond Toy wrote: > > >>>>>>"Jerry" == Jerry Avins <jya@ieee.org> writes: > > > > > > Jerry> Nithin wrote: > > >> Stephan M. Bernsee <spam@dspdimension.com> wrote in message news:<2veib9F2l8l0cU1@uni-berlin.de>... > > >> > > >>> On some processor architectures, memory can be expensive, so a LUT > > >>> cannot be done. On the other hand, implementing CORDIC in specialized > > >>> hardware can be very fast. > > >>> > > >>> So it really depends on the particular application - and the > > >>> environment - what method is best for calculating the DCT (or any other > > >>> transform). > > >> > > >> > > >> If implemented in software polynomial approximations may also be used. > > >> One standard method for this is Horner's algorithm but i was wondering > > >> if any kind of polynomial approach is used in hardware implementation > > >> as well...? > > > > Jerry> Horner's method finds roots. How is it used to find trig functions? > > > > It's also a method of evaluating polynomials. You know, instead of > > x^2+a*x+b directly, you evaluate (x + a)*x + b. > > Evaluating [(x + a)*x + b]x + c with Horner's method needs less > computation than working it out directly when x is known? I don't see > it. I'll look again. > > JerryHi, I guess you can approximate a trigonometric function with say a least squares polynomial and then evaluate the polynomial to find the value of the trig. function. Nithin
Reply by ●November 12, 20042004-11-12
>>>>> "Nithin" == Nithin <nitin_hsn@yahoo.com> writes:Nithin> Jerry Avins <jya@ieee.org> wrote in message news:<2vhgfeF2k0m36U1@uni-berlin.de>... >> Raymond Toy wrote: >> >> >>>>>>"Jerry" == Jerry Avins <jya@ieee.org> writes: >> > >> > >> > Jerry> Horner's method finds roots. How is it used to find trig functions? >> > >> > It's also a method of evaluating polynomials. You know, instead of >> > x^2+a*x+b directly, you evaluate (x + a)*x + b. >> >> Evaluating [(x + a)*x + b]x + c with Horner's method needs less >> computation than working it out directly when x is known? I don't see >> it. I'll look again. >> >> Jerry Nithin> Hi, Nithin> I guess you can approximate a trigonometric function with say a least Nithin> squares polynomial and then evaluate the polynomial to find the value Nithin> of the trig. function. Yes, that can be done, but typically, it's a minimax polynomial or minimax rational function. You normally want to know what the max error of the approximation will be. Ray
Reply by ●November 12, 20042004-11-12
>>>>> "Jon" == Jon Harris <goldentully@hotmail.com> writes:Jon> "Jerry Avins" <jya@ieee.org> wrote in message Jon> news:2vhgfeF2k0m36U1@uni-berlin.de... >> Raymond Toy wrote: >> >> > It's also a method of evaluating polynomials. You know, instead of >> > x^2+a*x+b directly, you evaluate (x + a)*x + b. >> >> Evaluating [(x + a)*x + b]x + c with Horner's method needs less >> computation than working it out directly when x is known? I don't see >> it. I'll look again. Jon> Compared with the "direct method", Horner's method trades multiplies for adds Jon> and additionally is computationally more efficient for higher degrees. In the Jon> case of a quadratic, there is no computational efficiency gain in an Jon> architecture where adds and multiplies cost the same (Horner = 3 adds, 2 Jon> multiplies, direct = 2 adds, 3 multiplies). But for a cubic equation, the Jon> direct method requires 2 more multiplies and 1 more add, whereas Horner requires Jon> only one more multiply and one more add. For higher degrees, the savings is Jon> even more pronounced. It also typically has much better numerical stability so round-off won't hurt as much. Ray
