Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #3169

Re: How many additions in fastest DCT ?

Show all headers | View raw

Thomas Richter <thor@math.tu-berlin.de> wrote:
> On 14.09.2015 10:54, James Dow Allen wrote:
>> Reminiscing, I recall a little "nitpick" from almost 25 years ago, and 
>> got curious.  I wonder if anyone here is involved enough in DCT fast 
>> procedures to research something for me.
 
(snip)

> Question here is: What do you mean by a "pure DCT"? After all, all
> (actually, almost all) DCT implementations are approximations because
> they use limited precision arithmetic. There are some works that
> implement the DCT as a field-extension and hence are mathematically
> precise in that sense, except that the output samples are then
> necessarily vectorial and not scalar (i.e. 8 vectorial outputs instead
> of eight scalar outputs for a DCT of a length 8).

Well, first of all, "pure DCT" would tend to imply the O(N**2)
version, instead of the FFT derived one that would be called FCT
that is O(N logN). 

Once you get to the FCT form, then there are more questions.
Fixed or floating point, and how many bits? If you do fixed point,
and add one bit for each (power of two) stage, there is no precision
loss, though there might be rounding. Easy in hardware, not always
so easy in software.

But in the early days, add was enough faster than multiply that
there wasn't so much reason to count add. As multiply gets faster,
add is more important.  But then again, on many processors multiply
(and maybe add) times depend on the operands. Some values mutliply
faster than others.
 
> If you're looking specifically at 8x8 DCTs, the (probably) most
> elaborate research in finding least-complex DCTs with given error bounds
> is by Yurij Reznik and and Arianne Hinds. You'll find the paper on
> Yurij's side:
 
> http://www.reznik.org/software.html

-- glen

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-14 08:54 +0000
  Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-14 11:30 +0200
    Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-14 11:40 +0000
      Re: How many additions in fastest DCT ? jdallen2000@yahoo.com - 2015-09-14 05:53 -0700
      Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-14 21:29 +0200
        Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-15 07:08 +0000
          Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-15 11:08 +0200
          Re: How many additions in fastest DCT ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-15 14:17 +0000
    Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-14 10:05 -0500
      Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-15 07:22 +0000
        Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-15 11:14 +0200
          Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-15 09:16 -0500
        Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-15 08:41 -0500
    Re: How many additions in fastest DCT ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-14 20:59 +0000
  Re: How many additions in fastest DCT ? Phil Carmody <pc+usenet@asdf.org> - 2015-11-18 21:51 +0200

csiph-web