乗算不要な離散コサイン変換アルゴリズム...理解できませんでした

MPEG4をはじめとするデジタル動画像圧縮技術に必ず使われている離散コサイン変換 wikipedia:DCT の回路技術を見ていると，日経BP社主宰のLSI IP アワード, http://techon.nikkeibp.co.jp/award/ ,の応募原稿から，テクノマセマティカル社の"乗算が不要な"DCT変換アルゴリズムが目にとまった．

離散コサイン変換はCOS関数との相関を求める処理だから，回数の多少こそあれ係数の積和演算は不可欠である．応募原稿, http://techon.nikkeibp.co.jp/award/papers/2002_co3.pdf ,をみると，8x82次元DCT処理に必要な演算は加減算416回のみで乗算は不要とある．

DCTで処理負荷(回路化するなら面積)が大きい乗算が不要にできれば，スペック向上に大きなインパクトがある．DCTのアルゴリズムはもう数十年に渡り検討されてきているのだからこれまでに誰から発明してそうなものだと，半ば疑問を感じつつ，しかし，その道の専門家が審査員をしているアワードに選ばれているのだから正しいアルゴリズムなのだろうと思い，これは一体どんなアルゴリズムなのだろうかと興味を引いた．

DCTのアルゴリズムで公開されている資料には，先ほどのLSI IPデザインアワード応募原稿以外に，特許出願公開番号 特開2003-30174 発明名称 DCT行列分解方法及びDCT装置 がある．http://www.ultra-patent.jp/Search/Search+.aspxからPDFファイルを入手して読んでみたのだが，肝心の乗算が不要になる理屈が理解できなかった．

特許をみると，まずDCT処理を行列式で表して，次に行列を対角成分以外の係数が0になるように変形する，つまり因数分解して演算をシンプルにしていくという内容である．
最初に書かれている行列演算の簡単化は，有名なChenらのアルゴリズムにあるバタフライ演算そのものである．次にバタフライ演算の回転因子をさらに部分行列にしていくと書かれているのだが，その肝心の部分の説明が，係数が0もしくは+-1のみの行列に分解できるとしか書かれていない．

他の特許で，乗算回路を使わないDCT演算には，特許出願公開番号 特開平9-223124 発明名称 データ圧縮伸長装置における離散余弦変換及び逆離散余弦変換方法及び装置 がある．これは三角関数を求めるアルゴリズムとしてよく使われる CORDIC を用いたものである．これは余弦の値を都度CORDICアルゴリズムで求めているだけだから，乗算処理を加減算に展開しているわけで，乗算処理が不要なわけではない．これの内容なら理解できる．

だが，先ほどの特許はCORDICを使うものでもない．仮にCORDICを使っていたとすると，1回の回転変換に(入力値のビット幅x2回)の加減算が必要になるから，先の特許で例に挙げられていた4x4DCTでも入力8ビットとして32回の加減算が必要になるはず．
どうやれば余弦変換を，8x8の2次元DCTでたった416回の加減算だけで，できるのだろうか．

MPEG4で使われる離散アダマール変換(discreate hadamard transform) http://pagesperso-orange.fr/polyvalens/clemens/transforms/hadamard/hadamard.html は振幅が+-1の値しかとらない矩形関数を基底関数に使うから，この変換ならば加減算だけでできるのは，もともとのアルゴリズムから自明だ．もしかしたら私がこの変換とDCTを勘違いして読んでいたのかと思ってもみたのだが，やはり特許はDCTのものだし．

....むー，数値テーブルも使わず2次元8x8DCTを416回の加減算だけでなぜ処理できるのだろうか．少なくとも，どうやれば入力値の加減算だけでの係数を掛けたのと同じ処理ができているのか，そこだけでも知りたい．

気になるのに，理解できなくて背中がむず痒い...