DCT/IDCT implementation in software/hardware

Hi,

I came across the following in the book "H.264 and MPEG 4 Video
Compression" by Iain E.G. Richardson:

"Flowgraph" algorithms are very popular for software CODECS where (in
most cases) the best performance is achieved by minimizing the number
of computationally expensive multiply operations. For a hardware
implementation, "regular data flow" may be more important than the
number of operations & so a different approach may be required.
Popular hardware architectures for the FDCT/IDCT include those based
on parallel multiplier arrays and distributed arithmetic.

I would be obliged if someone explains me the definitions of
"flowgraph" and "regular data flow".

Regards,
Nalin Pithwa

I'll take a stab at it.

Flowgraph - A model of the structure of the system's [program's] behavior, i.e.,
functionality. (from
http://www.computerdictionary.info/computer-term-details/Transaction-Flowgraph)
See also http://www.scism.sbu.ac.uk/law/Section5/chap3/s5c3p1.html for more
detail.

Regular data flow - Sometimes algorithms have a lot of decisions or branching.
On standard processors, this tends to work just fine.  However, hardware (and to
some extent DSPs) is simpler and more efficient if it can just "crunch numbers"
rather than having to go through a bunch of conditionals.  Some times,
algorithms can be changed to do more "crunching" and less "branching".  The less
branching there is, the more regular the data flow.
Here is a really simple example to illustrate the difference.  Consider a
mute/off control on an audio signal.  A "branching" algorithm might be: if Mute
= true, output = 0, else output = input.  This could be changed into a more
hardware-friendly "crunching" algorithm by introducing a variable muteVal that
is 0 when muted and 1 otherwise. Then, the algorithm is simply: output = input *
muteVal.  You trade a decision for a multiply, which is almost always a good
tradeoff when you have a fast multiplier at your disposal (i.e. in DSP or
dedicated hardware).

"nkpithwa" <nkpithwa@rediffmail.com> wrote in message
news:438f798e.0408311046.727be164@posting.google.com...
> Hi,
>
> I came across the following in the book "H.264 and MPEG 4 Video
> Compression" by Iain E.G. Richardson:
>
> "Flowgraph" algorithms are very popular for software CODECS where (in
> most cases) the best performance is achieved by minimizing the number
> of computationally expensive multiply operations. For a hardware
> implementation, "regular data flow" may be more important than the
> number of operations & so a different approach may be required.
> Popular hardware architectures for the FDCT/IDCT include those based
> on parallel multiplier arrays and distributed arithmetic.
>
> I would be obliged if someone explains me the definitions of
> "flowgraph" and "regular data flow".
>
> Regards,
> Nalin Pithwa