米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 二次元DCT演算装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−200539
公開日 平成7年(1995)8月4日
出願番号 特願平5−352558
出願日 平成5年(1993)12月28日
代理人 【弁理士】
【氏名又は名称】中島 司朗
発明者 鶴田 英世
要約 目的
従来より規模の小さい回路構成で二次元DCT/IDCTを計算する。

構成
一段目の一次元DCT器と中間バッファと二段目の一次元DCT器により構成され、この三つの部分がパイプライン動作する。8×8画素ブロック行列を第0,7,1,6,2,5,3,4行及び第0,7,1,6,2,5,3,4列の順に外部から読み込む。DCT係数を書き込む際にも簡単なアドレス変換により順番を入れ替える。また従来分布アリスメティック法によっていた一次元DCTをROMを利用した定数乗算器と累算器により構成する。これにより中間バッファが四分の一に削減され、演算器の構成が簡単になる。
特許請求の範囲
【請求項1】 二段の一次元DCT演算手段を備え、N×N個の成分を有するデータ行列に対して二次元離散余弦変換(DCT(Discrete Cosine Transform)と略す)を演算し、変換結果の行列の各成分を外部メモリに書き込む二次元DCT演算装置であって、二次元DCTの対象となるデータ行列を、(数1)に示す読み出し番号順に対応する成分を一成分ずつ読み出す読み出し手段と、【数1】

前記読み出し手段によって読み出された二成分ずつに対して第一段目の一次元DCTを行い、変換結果を一列分ずつ生成する第一の一次元DCT演算手段と、前記第一の一次元DCT演算手段が生成した二列分のそれぞれの成分を、行順に二成分ずつ読み出してゆく第二の読み出し手段と、前記第二の読み出し手段によって読み出された二成分に第二段目の一次元DCTを行い、変換結果の行列を生成する第二の一次元DCT演算手段と、前記第二の一次元DCT演算手段が生成した変換結果の行列を一成分ずつ外部メモリに書き込む書き込み手段と、を備えることを特徴とする二次元DCT演算装置。
【請求項2】 前記第一の一次元DCT手段は、第一の加減算手段と、第一の定数乗算手段と、第一の累算手段とを有し、第一の加減算手段は、読み出し手段によって読み出された二成分同士の加算及び減算を行い、第一の定数乗算手段は、第一段目の一次元DCTにおける一行×一列の積和計算において、第一の加減算手段による加算結果及び減算結果を乗数とする部分積を全て求め、第一の累算手段は、加減算結果一列分の第一の定数乗算手段の部分積の累算値を求めて、求めた累算値を第二の読み出し手段に出力し、前記第二の一次元DCT手段は、第二の加減算手段と、第二の定数乗算手段と、第二の累算手段とを有し、第二の加減算手段は、第二の読み出し手段によって読み出された二成分同士の加算及び減算を行い、第二の定数乗算手段は、第二段目の一次元DCTにおける一行×一列の積和計算において、第二の加減算手段による加算結果及び減算結果を乗数とする部分積を全て求めて、第二の累算手段は、加減算結果一行分の第一の定数乗算手段の部分積の累算値を求めて、求めた累算値を書き込み手段に出力することを特徴とする請求項1記載の二次元DCT演算装置。
【請求項3】 前記第一の加減算手段は、二段のシフトレジスタと、第一の入力バッファと、第二の入力バッファと、第一の加減算器とを有し、二段のシフトレジスタは、一成分ずつシフトして、読み出し手段によって読み出された入力信号系列の二成分を保持し、第一の入力バッファは、二段のシフトレジスタが二回シフトする度に前段の保持する一成分を受け取り、第二の入力バッファは、二段のシフトレジスタが二回シフトする度に後段の保持する一成分を受け取り、第一の加減算器は、第一の入力バッファ及び第二の入力バッファ内の二成分同士の加算及び減算を交互に行い、第一の定数乗算手段は、前記第一の加減算器に接続されるN/2個の第一の定数乗算器を有し、各々の第一の定数乗算器は、第一段目の一次元DCTにおける一行×一列の積和計算において、第一の加減算器による加算結果及び減算結果を乗数とし、所定の行列の一成分を被乗数とする部分積を求めて、前記第一の累算手段は、前記N/2個の定数乗算器のそれぞれに対応して接続されるN/2個の第一の加算器と、当該N/2個の第一の加算器のそれぞれに対応して接続されるN/2個の二段のシフトレジスタとを有し、各々の第一の加算器は、第一の定数乗算器が出力した積と、二段のシフトレジスタの後段から出力される成分とを加算し、各々の二段のシフトレジスタは、第一の加算器が出力した成分をシフトしながら二成分保持し、保持した二成分を一成分ずつシフトすることで後段の出力を第一の加算器にフィードバックして、N×2回シフトした後に、当該一列中の二成分を一度に第二の読み出し手段に出力することを特徴とする請求項2記載の二次元DCT演算装置。
【請求項4】 前記第二の読み出し手段は、一列バッファと、第一のN段の並列/直列変換用のシフトレジスタと、第二のN段の並列/直列変換用のシフトレジスタとを有し、一列バッファは、第一の一次元DCT演算手段によって順次生成される一列分の成分を、一列おきに受け取って保持し、保持している成分の次の列の成分が第一の一次元DCT演算手段から出力されると、それまで保持していた一列分の成分を第一のN段の並列/直列変換用のシフトレジスタに一度に出力し、第一のN段の並列/直列変換用のシフトレジスタは、前記一列バッファが出力した一列分の成分を保持し、保持した一列分の成分のシフトを一成分ずつ行い、当該一列分の成分を一成分ずつ第二の一次元DCT演算手段に出力してゆき、第二のN段の並列/直列変換用のシフトレジスタは、第一の一次元DCT演算手段が出力した一列分の成分で、一列バッファが受け取らなかったものを保持し、保持した一列分の成分のシフトを一成分ずつ行い、当該一列分の成分を一成分ずつ第二の一次元DCT演算手段に出力してゆくことを特徴とする請求項3記載の二次元DCT演算装置。
【請求項5】 前記第二の加減算手段は、第二の読み出し手段が出力した二成分同士の加算及び減算を交互に行い、前記第二の定数乗算手段は、前記第二の加減算手段と接続されるN/2個の第二の定数乗算器を有し、各々の第二の定数乗算器は、第二段目の一次元DCTにおける一行×一列の積和計算において、第二の加減算手段による加算結果及び減算結果を乗数とし、所定の行列の一行中の一成分を被乗数とする部分積を求めて、前記第二の累算手段は、前記N/2個の第二の定数乗算器のそれぞれに対応して接続されるN/2個の第二の加算器と、当該N/2個の第二の加算器に対応して接続されるN/2個のN×2段のシフトレジスタとを有し、各々の第二の加算器は、第二の定数乗算器が出力した積と、N×2段のシフトレジスタの最終段から出力される成分とを加算し、各々のN×2段のシフトレジスタは、第二の加算器が出力した成分をシフトしながら二列分保持し、保持した成分を一成分ずつシフトすることで最終段の出力を第二の加算器にフィードバックして、N×N回シフトした後に、当該二列分の成分を一成分ずつ書き込み手段に出力することを特徴とする請求項4記載の二次元DCT演算装置。
【請求項6】 前記累算手段は、更にN/2個のN×2段のシフトレジスタのうち、所定の一個を除くN/2-1個の最終段に接続されるN/2-1個の出力バッファと、出力選択器とを有し、N/2-1個の出力バッファは、N×2段のシフトレジスタからなり、接続されるシフトレジスタから一成分ずつ出力される二列分の成分をシフトを行いながら保持し、保持している成分を一成分ずつ順次出力選択器に出力してゆき、出力選択器は、それぞれのN×2段のシフトレジスタ及びN/2-1個の出力バッファの出力を選択して出力することを特徴とする請求項5記載の二次元DCT演算装置。
【請求項7】 前記定数乗算器は、所定の行列の成分の倍数を予め格納しているROMを有していることを特徴とする請求項3から6記載の何れかの二次元DCT演算装置。
【請求項8】 前記定数乗算器は、所定の行列として第一段目及び第二段目の一次元DCTに用いられる定数行列の成分及び/又は第一段目及び第二段目の離散余弦逆変換(IDCT(Inverse Discrete Cosine Transform)と略す)に用いられる定数行列の成分を予め格納していることを特徴とする請求項7記載の二次元DCT演算装置。
【請求項9】 前記読み出し手段は、読み出し列生成手段と、読み出し行生成手段と、読み出しアドレス生成手段とを備え、読み出し列生成手段は、読み出すべき成分の、N×Nの成分を持つデータ行列における列番号を指定し、読み出し行生成手段は、読み出し列生成手段が指定した列における読み出しを行う成分の行番号を指定する読み出しアドレス生成手段は、読み出し列生成手段が生成した列番号と、読み出し行生成手段が生成した行番号とから、読み出すべき成分の外部メモリ中のアドレスを生成することを特徴とする二次元DCT演算装置。
【請求項10】 前記書き込み手段は、書き込み列生成手段と、書き込み行生手段と、書き込みアドレス生成手段とを有し、書き込み列生成手段は、演算結果の行列の成分のうち、書き込みを行うものの列番号を生成し、書き込み行生成手段は、書き込み列生成手段が生成した列番号の列における、書き込みを行う成分の行番号を生成し、書き込みアドレス生成手段は、書き込み行生成手段が生成した行番号と、書き込み列生成手段が生成した列番号とから、演算行列の各成分を書き込むための外部メモリ中のアドレスを生成することを特徴とする請求項1から9記載の何れかの二次元DCT演算装置。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、信号処理装置において二次元離散余弦変換(DCT(Discrete CosineTransform)と略す)と離散余弦逆変換(IDCT(Inverse Discrete Cosine Transform)と略す)との何れかを演算する演算装置に関する。
【0002】
【従来の技術】画像や音声の圧縮/伸長など多くの信号処理分野において高速なDCT演算が求められている。DCTは処理演算量が膨大であるため、これを実時間で処理するために大きな回路規模が必要である。従来の二次元DCT演算装置は、例えば公告特許平5-26229号公報、米国特許第 4791598号(1988年12月13日)及びM.T.Sun,L.Wu,and M.L. Liou,"A Concurrent Architecture for VLSI Implementation of Discrete Cosine Transform," IEEETrans. on Circuits and Systems,Vol. CAS-34,No.8,pp.992-994,Aug. 1987、及びM.T. Sun,T.C. Chen,A. Gottlieb,L. Wu,and M.L. Liou,"A 16x16 Discrete Cosine Transform Chip," Visual Commun. and Image Process. II,SPIE,Vol. 845,pp. 13-18,Oct. 1987、及びM.T. Sun,T.C. Chen,and A. M. Gottlieb,"VLSI Implementation of a 16×16 Discrete Cosine Transform," IEEE Trans. Circuits and Systems,Vol. CAS-36,pp. 610-617,Apr. 1989、及びT.C. Chen,M.T. Sun,and A. M. Gottlieb,"VLSI Implementation of a 16x16 DCT," ICASSP 88,Intl. Conf. Acoust.,Speech, and Signal Process.,pp. 1973-1976,Apr. 1988に示されている。
【0003】(図10),(図11),(図12)は従来例の構成図を示す。従来例はN×Nの二次元DCTについて述べているが、ここでは簡単のために8×8の場合に限定する。また画素データ,内部数値表現及びDCT係数は16ビットから8ビット程度の固定小数点数であるとする。(図10)において、203は第一の列N×1 DCTプロセサである。205はN×N変換メモリである。207は第二の行N×1 DCTプロセサである。209はタイミング及び制御信号発生器である。211,212はタイミング及び制御信号である。216は読み取り/書き込みアドレス及び制御回路である。214は読み取り/書き込みアドレス及び制御信号である。(図11)において、313は入力レジスタである。315はホールディングレジスタである。381と383はそれぞれN/2個の直列加算器と直列減算器である。317はRAC(ROM and accumulator)である。319は出力レジスタである。385,387はN/2ビットバスである。445,447は16ワードROMである。449は加算器である。451は加算/減算器である。453はシフトレジスタである。
【0004】従来例では、8×8のDCTに対して4ビットのRACを用いるとしているが、16ビット画素データを処理するためには直列加算器381,直列減算器383,RAC317などがシフトレジスタなど他の部分の倍の周波数で動作せねばならない(詳細については上記論文に記載されている。)。全体に同一の周波数が供給される場合、(図12)に示す8ビットのRACが必要である。
【0005】
【発明が解決しようとする課題】しかしながら上記従来技術の二次元DCT演算装置は、二つの一次元DCT演算装置とN×N語の行-列転置用の変換メモリを必要とするため、これらハードウェアが費やす素子数,回路面積,消費電力は大きいという問題点があった。また上記従来技術の二次元DCT演算装置は、分布アリスメティック(distributed arithmetic)法を用いてビット直列にDCT演算を行うため、多数の内部バッファとシフトレジスタが必要であるという問題点があった。
【0006】本発明は、上記問題点に鑑み、従来の二次元DCT演算装置と同等の性能を保ちながらより少ないハードウェアで構成される新規の二次元DCT演算装置を提供することを目的とする。
【0007】
【課題を解決するための手段】上記課題を解決するために本発明の二次元DCT演算装置は、二段の一次元DCT演算手段を備え、N×N個の成分を有するデータ行列に対して二次元離散余弦変換を演算し、変換結果の行列の各成分を外部メモリに書き込む二次元DCT演算装置であって、二次元DCTの対象となるデータ行列を、(数1)に示す読み出し番号順に対応する成分を一成分ずつ読み出す読み出し手段と、前記読み出し手段によって読み出された二成分ずつに対して第一段目の一次元DCTを行い、変換結果を一列分ずつ生成する第一の一次元DCT演算手段と、前記第一の一次元DCT演算手段が生成した二列分のそれぞれの成分を、行順に二成分ずつ読み出してゆく第二の読み出し手段と、前記第二の読み出し手段によって読み出された二成分に第二段目の一次元DCTを行い、変換結果の行列を生成する第二の一次元DCT演算手段と、前記第二の一次元DCT演算手段が生成した変換結果の行列を一成分ずつ外部メモリに書き込む書き込み手段とを備えている。
【0008】また、前記第一の一次元DCT手段は、第一の加減算手段と、第一の定数乗算手段と、第一の累算手段とを有し、第一の加減算手段は、読み出し手段によって読み出された二成分同士の加算及び減算を行い、第一の定数乗算手段は、第一段目の一次元DCTにおける一行×一列の積和計算において、第一の加減算手段による加算結果及び減算結果を乗数とする部分積を全て求め、第一の累算手段は、加減算結果一列分の第一の定数乗算手段の部分積の累算値を求めて、求めた累算値を第二の読み出し手段に出力し、前記第二の一次元DCT手段は、第二の加減算手段と、第二の定数乗算手段と、第二の累算手段とを有し、第二の加減算手段は、第二の読み出し手段によって読み出された二成分同士の加算及び減算を行い、第二の定数乗算手段は、第二段目の一次元DCTにおける一行×一列の積和計算において、第二の加減算手段による加算結果及び減算結果を乗数とする部分積を全て求めて、第二の累算手段は、加減算結果一行分の第一の定数乗算手段の部分積の累算値を求めて、求めた累算値を書き込み手段に出力してもよい。
【0009】また、前記第一の加減算手段は、二段のシフトレジスタと、第一の入力バッファと、第二の入力バッファと、第一の加減算器とを有し、二段のシフトレジスタは、一成分ずつシフトして、読み出し手段によって読み出された入力信号系列の二成分を保持し、第一の入力バッファは、二段のシフトレジスタが二回シフトする度に前段の保持する一成分を受け取り、第二の入力バッファは、二段のシフトレジスタが二回シフトする度に後段の保持する一成分を受け取り、第一の加減算器は、第一の入力バッファ及び第二の入力バッファ内の二成分同士の加算及び減算を交互に行い、第一の定数乗算手段は、前記第一の加減算器に接続されるN/2個の第一の定数乗算器を有し、各々の第一の定数乗算器は、第一段目の一次元DCTにおける一行×一列の積和計算において、第一の加減算器による加算結果及び減算結果を乗数とし、所定の行列の一成分を被乗数とする部分積を求めて、前記第一の累算手段は、前記N/2個の定数乗算器のそれぞれに対応して接続されるN/2個の第一の加算器と、当該N/2個の第一の加算器のそれぞれに対応して接続されるN/2個の二段のシフトレジスタとを有し、各々の第一の加算器は、第一の定数乗算器が出力した積と、二段のシフトレジスタの後段から出力される成分とを加算し、各々の二段のシフトレジスタは、第一の加算器が出力した成分をシフトしながら二成分保持し、保持した二成分を一成分ずつシフトすることで後段の出力を第一の加算器にフィードバックして、N×2回シフトした後に、当該一列中の二成分を一度に第二の読み出し手段に出力してもよい。
【0010】また、前記第二の読み出し手段は、一列バッファと、第一のN段の並列/直列変換用のシフトレジスタと、第二のN段の並列/直列変換用のシフトレジスタとを有し、一列バッファは、第一の一次元DCT演算手段によって順次生成される一列分の成分を、一列おきに受け取って保持し、保持している成分の次の列の成分が第一の一次元DCT演算手段から出力されると、それまで保持していた一列分の成分を第一のN段の並列/直列変換用のシフトレジスタに一度に出力し、第一のN段の並列/直列変換用のシフトレジスタは、前記一列バッファが出力した一列分の成分を保持し、保持した一列分の成分のシフトを一成分ずつ行い、当該一列分の成分を一成分ずつ第二の一次元DCT演算手段に出力してゆき、第二のN段の並列/直列変換用のシフトレジスタは、第一の一次元DCT演算手段が出力した一列分の成分で、一列バッファが受け取らなかったものを保持し、保持した一列分の成分のシフトを一成分ずつ行い、当該一列分の成分を一成分ずつ第二の一次元DCT演算手段に出力してもよい。
【0011】また、前記第二の加減算手段は、第二の読み出し手段が出力した二成分同士の加算及び減算を交互に行い、前記第二の定数乗算手段は、前記第二の加減算手段と接続されるN/2個の第二の定数乗算器を有し、各々の第二の定数乗算器は、第二段目の一次元DCTにおける一行×一列の積和計算において、第二の加減算手段による加算結果及び減算結果を乗数とし、所定の行列の一行中の一成分を被乗数とする部分積を求めて、前記第二の累算手段は、前記N/2個の第二の定数乗算器のそれぞれに対応して接続されるN/2個の第二の加算器と、当該N/2個の第二の加算器に対応して接続されるN/2個のN×2段のシフトレジスタとを有し、各々の第二の加算器は、第二の定数乗算器が出力した積と、N×2段のシフトレジスタの最終段から出力される成分とを加算し、各々のN×2段のシフトレジスタは、第二の加算器が出力した成分をシフトしながら二列分保持し、保持した成分を一成分ずつシフトすることで最終段の出力を第二の加算器にフィードバックして、N×N回シフトした後に、当該二列分の成分を一成分ずつ書き込み手段に出力してもよい。
【0012】また、前記累算手段は、更にN/2個のN×2段のシフトレジスタのうち、所定の一個を除くN/2-1個の最終段に接続されるN/2-1個の出力バッファと、出力選択器とを有し、N/2-1個の出力バッファは、N×2段のシフトレジスタからなり、接続されるシフトレジスタから一成分ずつ出力される二列分の成分をシフトを行いながら保持し、保持している成分を一成分ずつ順次出力選択器に出力してゆき、出力選択器は、それぞれのN×2段のシフトレジスタ及びN/2-1個の出力バッファの出力を選択して出力してもよい。
【0013】また、前記定数乗算器は、所定の行列の成分の倍数を予め格納しているROMを有していてもよい。また、前記定数乗算器は、所定の行列として第一段目及び第二段目の一次元DCTに用いられる定数行列の成分及び/又は第一段目及び第二段目の離散余弦逆変換に用いられる定数行列の成分を予め格納していることを特徴としてもよい。
【0014】前記読み出し手段は、読み出し列生成手段と、読み出し行生成手段と、読み出しアドレス生成手段とを備え、読み出し列生成手段は、読み出すべき成分の、N×Nの成分を持つデータ行列における列番号を指定し、読み出し行生成手段は、読み出し列生成手段が指定した列における読み出しを行う成分の行番号を指定し、読み出しアドレス生成手段は、読み出し列生成手段が生成した列番号と、読み出し行生成手段が生成した行番号とから、読み出すべき成分の外部メモリ中のアドレスを生成してもよい。
【0015】前記書き込み手段は、書き込み列生成手段と、書き込み行生手段と、書き込みアドレス生成手段とを有し、書き込み列生成手段は、演算結果の行列の成分のうち、書き込みを行うものの列番号を生成し、書き込み行生成手段は、書き込み列生成手段が生成した列番号の列における、書き込みを行う成分の行番号を生成し、書き込みアドレス生成手段は、書き込み行生成手段が生成した行番号と、書き込み列生成手段が生成した列番号とから、演算行列の各成分を書き込むための外部メモリ中のアドレスを生成してもよい。
【0016】
【作用】上記の手段により本発明の二次元DCT演算装置において、読み出し手段によって二次元DCTの対象となるデータ行列が(数1)に示す読み出し番号順に一成分ずつ読み出される。読み出し手段によって読み出された二成分ずつに対して第一の一次元DCT演算手段が作動し、第一段目の一次元DCTが行われ、変換結果が一列分ずつ生成される。前記第一の一次元DCT演算手段が生成した二列分のそれぞれの成分が第二の読み出し手段によって行順に二成分ずつ読み出されてゆく。前記第二の読み出し手段によって読み出された二成分に、第二の一次元DCT演算手段によって第二段目の一次元DCTが行われ、変換結果の行列が生成される。前記第二の一次元DCT演算手段が生成した変換結果の行列が、書き込み手段によって一成分ずつ外部メモリに書き込まれる。
【0017】また、上記手段により本発明の第一の一次元DCT手段は、第一の加減算手段と、第一の定数乗算手段と、第一の累算手段とを有し、読み出し手段によって読み出された二成分同士の加算及び減算が、第一の加減算手段によって行われ、第一段目の一次元DCTにおける一行×一列の積和計算における第一の加減算手段による加算結果及び減算結果を乗数とする部分積が第一の定数乗算手段によって全て求められる。加減算結果一列分の第一の定数乗算手段の部分積の累算値が第一の累算手段によって求められ、求められた累算値が第二の読み出し手段に出力される。
【0018】また、上記手段により本発明の第二の一次元DCT手段は、第二の加減算手段と、第二の定数乗算手段と、第二の累算手段とを有し、第二の読み出し手段によって読み出された二成分同士の加算及び減算が、第二の加減算手段によって行われ、第二段目の一次元DCTにおける一行×一列の積和計算における第二の加減算手段による加算結果及び減算結果を乗数とする部分積が第二の定数乗算手段によって全て求められ、加減算結果一行分の第一の定数乗算手段の部分積の累算値が第二の累算手段によって求められ、求められた累算値が書き込み手段に出力される。
【0019】また、前記第一の加減算手段は、二段のシフトレジスタと、第一の入力バッファと、第二の入力バッファと、第一の加減算器とを有し、二段のシフトレジスタが一成分ずつシフトすることにより、読み出し手段によって読み出された入力信号系列の二成分が保持される。二段のシフトレジスタが二回シフトする度に前段の保持する一成分が、第一の入力バッファによって受け取られる。二段のシフトレジスタが二回シフトする度に後段の保持する一成分が、第二の入力バッファによって受け取られ、第一の入力バッファ及び第二の入力バッファ内の二成分同士の加算及び減算が、第一の加減算器によって交互に行われる。
【0020】また、上記手段により本発明の第一の定数乗算手段は、前記第一の加減算器に接続されるN/2個の第一の定数乗算器を有し、第一の加減算器による加算結果及び減算結果を乗数とし、所定の行列の一成分を被乗数とする第一段目の一次元DCTにおける一行×一列の積和計算における部分積が各々の第一の定数乗算器によって求められる。
【0021】また、上記手段により本発明の第一の累算手段は、前記N/2個の定数乗算器のそれぞれに対応して接続されるN/2個の第一の加算器と、当該N/2個の第一の加算器のそれぞれに対応して接続されるN/2個の二段のシフトレジスタとを有し、第一の定数乗算器が出力した積と、二段のシフトレジスタの後段から出力される成分との加算が、各々の第一の加算器によって行われる。第一の加算器が出力した成分が各々の二段のシフトレジスタによってシフトしながら二成分保持され、保持された二成分が一成分ずつシフトされることで後段の出力が第一の加算器にフィードバックされ、N×2回シフトした後に、当該一列中の二成分が一度に第二の読み出し手段に出力される。
【0022】また、上記手段により本発明の第二の読み出し手段は、一列バッファと、第一のN段の並列/直列変換用のシフトレジスタと、第二のN段の並列/直列変換用のシフトレジスタとを有し、一列バッファは、第一の一次元DCT演算手段によって順次生成される一列分の成分を、一列おきに受け取って保持し、保持している成分の次の列の成分が第一の一次元DCT演算手段から出力されると、それまで保持していた一列分の成分が第一のN段の並列/直列変換用のシフトレジスタに一度に出力され、第一のN段の並列/直列変換用のシフトレジスタは、前記一列バッファが出力した一列分の成分を保持し、保持した一列分の成分のシフトを一成分ずつ行い、当該一列分の成分が一成分ずつ第二の一次元DCT演算手段に出力してゆき、第二のN段の並列/直列変換用のシフトレジスタは、第一の一次元DCT演算手段が出力した一列分の成分で、一列バッファが受け取らなかったものを保持し、保持した一列分の成分のシフトを一成分ずつ行い、当該一列分の成分が一成分ずつ第二の一次元DCT演算手段に出力され、前記第二の加減算手段によって、第二の読み出し手段が出力した二成分同士の加算及び減算が交互に行われる。
【0023】また、上記手段により本発明の第二の定数乗算手段は、前記第二の加減算手段と接続されるN/2個の第二の定数乗算器を有し、各々の第二の定数乗算器によって第二の加減算手段による加算結果及び減算結果を乗数とし、所定の行列の一行中の一成分を被乗数とする第二段目の一次元DCTにおける一行×一列の積和計算における部分積が求められる。
【0024】また、上記手段により本発明の第二の累算手段は、前記N/2個の第二の定数乗算器のそれぞれに対応して接続されるN/2個の第二の加算器と、当該N/2個の第二の加算器に対応して接続されるN/2個のN×2段のシフトレジスタとを有し、第二の定数乗算器が出力した積と、N×2段のシフトレジスタの最終段から出力される成分とが各々の第二の加算器によって加算され、第二の加算器が出力した成分が各々のN×2段のシフトレジスタによって二列分保持され、保持された成分は、一成分ずつシフトすることで最終段の出力を第二の加算器にフィードバックされる。N×N回シフトした後に、当該二列分の成分が一成分ずつ書き込み手段に出力される。
【0025】また、上記手段により本発明の累算手段は、更にN/2個のN×2段のシフトレジスタのうち、所定の一個を除くN/2-1個の最終段に接続されるN/2-1個の出力バッファと、出力選択器とを有し、接続されるシフトレジスタから一成分ずつ出力される二列分の成分が、N/2-1個の出力バッファによってシフトを行いながら保持され、保持される成分が一成分ずつ順次出力選択器に出力される。
【0026】
【実施例】以下にDCTについての詳細な説明を行う。IDCTに対しては、同様に処理が可能であり、同等の演算装置により計算できるので、IDCTの記述を省略する。以下の説明中で、入力される信号系列をfijまたはf(i,j)で、fijの一次元DCTをhmnまたはh(m,n)で、fijの二次元DCTをguvまたはg(u,v)で表す。本発明はN×Nの二次元DCTに関するが、8×8の場合について以下に説明を行う。また画素データ,内部数値表現及びDCT係数は16ビット以下の固定小数点数であるとする。
【0027】DCTに対して幾つかの定義式が与えられるが、ここでは典型的にMPEGやJPEGなどの画像符号化国際標準で規定された定義式を参照する。即ち、8×8の二次元DCTは次式で定義される。
【0028】
【数2】

【0029】
【数3】

【0030】
【数4】

【0031】
【数5】

【0032】
【数6】

【0033】
【数7】

【0034】
【数8】

【0035】
【数9】

【0036】
【数10】

【0037】
【数11】

【0038】
【数12】

【0039】
【数13】

(図1)は、上記の演算を行えるように構成された本発明の実施例における二次元DCT演算装置の構成を示す図である。二次元DCT演算装置は、第一のDCT演算部100と、中間バッファ110と、第二のDCT演算部120と、アドレス生成部130とで構成される。
【0040】アドレス生成部130は、線形読み出しアドレス生成部131と、線形書き込みアドレス生成部135とで構成される。線形読み出しアドレス生成部131は、列読み出しアドレスと行読み出しアドレスに基づき、外部線形メモリ中のN×Nの行列成分データ(本実施例ではN=8)の線形アドレスを計算して、計算した線形アドレスの成分を一成分ずつ第一のDCT演算部100に読み出す。
【0041】(図2)は、線形読み出しアドレス生成部131の構成を示す図である。線形読み出しアドレス生成部131は、log2N×2ビットカウンタ132と、行読み出しアドレス生成部133と、列読み出しアドレス生成部134とで構成される。log2N×2ビットカウンタ132は、クロックパルスを入力する入力端子と、log2N×2個の出力端子とが備えられ、クロックパルスが入力される度にN×N回カウントを行う。本実施例においてN=8であるから、log2N×2ビットカウンタ132は、r0〜r5の出力端子を備えており、0〜63の数値をr0〜r5の出力端子に発生する。
【0042】行読み出しアドレス生成部133は、log2N×2ビットカウンタ132が発生した数値の下位3ビットを入力し、log2N×2ビットカウンタ132にクロックパルスが入力される度に行読み出しアドレスを発生する。log2N×2ビットカウンタ132が発生した数値の下位3ビットが0,1,2,3,4,5,6,7の順に増加すれば、行読み出しアドレス生成部133は、一つの列の第0,7,1,6,2,5,3,4行を読み出すための読み出しアドレスを発生させる。
【0043】列読み出しアドレス生成部134は、log2N×2ビットカウンタ132が発生した数値の上位3ビットを入力し、この上位3ビットがカウントアップする度に列読み出しアドレスを発生する。log2N×2ビットカウンタ132の出力端子の上位3ビットが0,1,2,3,4,5,6,7をカウントすれば、列読み出しアドレス生成部134は、第0,7,1,6,2,5,3,4列を読み出すための読み出しアドレスを発生させる。
【0044】行読み出しアドレス生成部133,列読み出しアドレス生成部134がこのようにして読み出しアドレスを発生させると、読む順序は列単位に、第0,7,1,6,2,5,3,4列の順に、列の中では第0,7,1,6,2,5,3,4行の順となる即ち、下の表に示す通りとなる。
1 17 33 49 57 41 25 93 19 35 51 59 43 27 115 21 37 53 61 45 29 137 23 39 55 63 47 31 158 24 40 56 64 48 32 166 22 38 54 62 46 30 144 20 36 52 60 44 28 122 18 34 50 58 42 26 10第一のDCT演算部100は、(数12)に示す第一段目の一次元DCT演算を64サイクルで行う。第一のDCT演算部100が行列Hの各成分の計算を行う順序を(図3)に示す。図中のh00の下に記されている"1+3+5+7"とは、h00は、1サイクル目に乗算を行い、3,5,7サイクル目に乗算及び累算を行うことで計算されることを意味する。h67の下に記されている"57+59+61+63"とは、h67は、57サイクル目に乗算を行い、59,61,63サイクル目に乗算及び累算を行うことで計算されることを意味する。このような順序で計算が行えるように第一のDCT演算部100は構成される。
【0045】第一のDCT演算部100は、入力シフトレジスタ101,入力バッファ102,第一の加減算器103,第一の定数乗算器104,第一の累算器105,及び累算シフトレジスタ106で構成される。入力シフトレジスタ101は二成分のデータをシフトしながら格納する二段のシフトレジスタで構成される。具体的には、入力シフトレジスタ101は、線形読み出しアドレス生成部131によって外部線形メモリから読み出された一成分のデータを第一段目のレジスタに保持させる。線形読み出しアドレス生成部131によって次の成分が読み出されると、それまで保持していた内容を次段のレジスタにシフトする。その結果、入力シフトレジスタ101には、2サイクルで二成分が充填される。充填されると同時に入力シフトレジスタ101は、それまで保持していた二成分分のデータを一度に入力バッファ102に転送する。
【0046】入力バッファ102は、入力シフトレジスタ101が転送した二成分分のデータを、入力シフトレジスタ101に次の二成分のデータが読み出されるまで保持する(この保持は2サイクルの間行われる。)。次の二成分分のデータが入力シフトレジスタ101に読み出されると、入力バッファ102は、それまで保持していた二成分分のデータを第一の加減算器103に転送する。
【0047】第一の加減算器103は、(数12)の右辺第一項の行列の各成分(f0j+f7j,f0j−f7j,f1j+f6j,f1j−f6j,f2j+f5j,f2j−f5j,f3j+f4j,f3j−f4jj=0,・・・・・,7)の計算を行う。具体的には、第一の加減算器103は入力バッファ102が転送した二成分分のデータを受け取り、受け取った時点でこれらの二成分のデータの加算を1サイクルで行い、加算結果を第一の定数乗算器104のそれぞれの段の定数乗算器に出力する。出力後、第一の加減算器103は、二成分分のデータの減算を1サイクルで行い、減算結果を第一の定数乗算器104のそれぞれの定数乗算器に出力する。このように第一の加減算器103は、それぞれの二成分分のデータに対して加算と減算を交互に繰り返す。j列データに対する演算はサイクル順にf0j+f7j,f0j−f7j,f1j+f6j,f1j−f6j,f2j+f5j,f2j−f5j,f3j+f4j,f3j−f4jであり、これを順に第0,7,1,6,2,5,3,4列について繰り返す。
【0048】第一の定数乗算器104は、N/2個(四つ)のROMより構成される。これらのROMには、(数12)の右辺第二項の行列成分と、(数12)の右辺第一項の行列成分との乗算値が予め格納されている。定数乗算器104を構成するN/2個のROMは、第一の加減算器103から出力される加算,減算結果を受け取り、格納している乗算値のうち、第一の加減算器103から出力される(数12)の右辺第二項の行列成分を被乗数とするものを取り出して、第一の累算器105のN/2個のそれぞれの加算器に出力する。
【0049】第一の累算器105は、N/2個の加算器から構成される。第一の累算器105は、第一の定数乗算器104が出力したN/2の積と、累算シフトレジスタ106を経てフィードバックされるN/2の累算中の中間値とを加算する。累算シフトレジスタ106は、N/2個の二段のシフトレジスタから構成される。
【0050】累算シフトレジスタ106は、行列Hの成分の中間値を保持し、一列中の奇数,偶数行に対応するN/2個の累算が一サイクル毎に交互に行われるようにシフト動作を行い、累算途中の中間値を第一の累算器105へフィードバックする。このシフト動作をNサイクル繰り返すことにより、累算シフトレジスタ106に行列Hの一列分の成分が充填され、充填された時点で累算シフトレジスタ106は、一列分の全ての成分を中間バッファ110に順次転送する。尚、図中のセルに書かれている数字は、それぞれのレジスタに充填されている成分が、一列中のどの行の成分であるかを示す。
【0051】中間バッファ110は、一列バッファ111と、二列シフトレジスタ112とで構成される。一列バッファ111は、累算シフトレジスタ106が順次転送する一列分のN個の成分を、一列おきに受け取り、行列Hの次の一列分の成分が累算シフトレジスタ106に計算されるまで、一列バッファ111は受け取った一列分の成分を保持する。保持している一列分の次の一列分の成分が累算シフトレジスタ106に計算されると、一列バッファ111は、保持している一列分の成分を二列シフトレジスタ112に一度に転送する。
【0052】二列シフトレジスタ112は、N段の並列/直列変換用のシフトレジスタが二列分並べられて構成される。二列シフトレジスタ112を構成する二列分のシフトレジスタは、累算シフトレジスタ106及び一列バッファ111から転送される二列分の値を受け取る。次に上記の二列分のシフトレジスタは、1サイクル毎にシフトを行い、これらの成分を二成分ずつ第二のDCT演算部120に転送してゆく。8サイクルで二列分の全ての成分を第二のDCT演算部120に転送し終えると、二列シフトレジスタ112は、次の二列分の成分を累算シフトレジスタ106,一列バッファ111から受け取る。
【0053】第二のDCT演算部120は、(数13)に示す第二段目の一次元DCT演算を64サイクルで行う。第二のDCT演算部100が行列Gの各成分の計算を行う順序を(図4)に示す。図中のg00の下に記されている"1+17+33+49"とは、g00は、1サイクル目に乗算を行い、17,33,49サイクル目に乗算及び累算を行うことで計算されることを意味する。g67の下に記されている"14+30+46+62"とは、g67は、14サイクル目に乗算を行い、30,46,62サイクル目に乗算及び累算を行うことで計算されることを意味する。このような順序で計算が行えるように第二のDCT演算部120は構成される。
【0054】第二のDCT演算部120は、第二の加減算器121,第二の定数乗算器122,第二の累算器123,二列シフトレジスタ124a,124b,124c,124d,二列出力バッファ125b,125c,125dで構成される。第二の加減算器121は、(数13)の右辺第一項の行列の各成分hm,0+hm,7,hm,0−hm,7,hm,1+hm,6,hm,1−hm,6,hm,2+hm,5,hm,2−hm,5,hm,3+hm,4,hm,3−hm,4(m=0,・・・・,7)の計算を行う。具体的には、第二の加減算器121は二列シフトレジスタ112が転送した二成分を受け取り、受け取った時点でこれらの二成分の加算を1サイクルで行い、加算結果を第一の第二の定数乗算器122に出力する。出力後、第二の加減算器121は、二成分の減算を1サイクルで行い、減算結果を第二の定数乗算器122のそれぞれの定数乗算器に出力する。
【0055】第二の定数乗算器122は、N/2個(四つ)のROMより構成される。これらのROMは、(数13)の右辺第二項の行列成分と、(数13)の右辺第一項の行列成分との乗算値を予め格納している。第二の定数乗算器122を構成するN/2個のROMは第二の加減算器121から出力される加算,減算結果を受け取り、格納している乗算値のうち、第二の加減算器121から出力される(数13)の右辺第二項の行列成分を被乗数とするものを全て取り出して、第二の累算器123のN/2個のそれぞれの加算器に出力する。
【0056】第二の累算器123は、N/2個の加算器から構成される。第二の累算器123は、第二の定数乗算器122が出力したN/2の積と、二列シフトレジスタ124a,124b,124c,124dを経てフィードバックされるN/2の累算中の中間値とを加算する。二列シフトレジスタ124aは、N×2段のシフトレジスタで構成される。二列シフトレジスタ124aは、行列Gの成分の中間値を保持し、二列分の成分を求めるための累算が、g0v,g0,v+1,g1v,g1,v+1,g2v,g2,v+1,g3v,g3,v+1,g4v,g4,v+1,g5v,g5,v+1,g6v,g6,v+1,g7v,g7,v+1 (v=0,2,4,6)の順に交互に行われるようにシフト動作を行い、累算途中の中間値を第二の累算器123へフィードバックする。このシフト動作を64サイクル繰り返すことにより、二列シフトレジスタ124aに行列Gの二列分の成分が充填される。充填された時点で二列シフトレジスタ124aはシフト動作を行い、二列分の成分を、1サイクル毎に1つずつ出力選択器126に出力してゆき、N×2サイクルで、二列分の成分を全て出力選択器126に出力する。尚、図中のセルに書かれている数字は、それぞれのレジスタに充填されている成分が、一列中のどの成分であるかを示す。二列シフトレジスタ124b,124c,124dは、二列シフトレジスタ124aと同様の動作を行う。異なるのは、二列シフトレジスタ124b,124c,124dは、出力を二列出力バッファ125b,125c,125dに対して行う点である。尚、図中のセルに書かれている数字は、それぞれのレジスタに充填されている成分が、一列中のどの成分であるかを示す。
【0057】二列出力バッファ125b,125c,125dは、二列シフトレジスタ124b,124c,124dから出力される二列分の成分を一成分ずつ受け取り、シフトを行いながら、N×2サイクルでこれらの成分を全て格納する。二列シフトレジスタ124aがN×2サイクルをかけて二列分の成分を全て出力選択器126に出力した後に、二列出力バッファ125b,125c,125dは、N×2サイクルをかけて、二列分の成分を出力選択器126に順序出力してゆく。尚、図中のセルに書かれている数字は、それぞれのレジスタに充填されている成分が、一列中のどの成分であるかを示す。
【0058】出力選択器126は、二列シフトレジスタ124a,二列出力バッファ125b,125c,125dから出力される行列Gの各成分を、外部線形メモリに選択出力する。線形書き込みアドレス生成部135は、出力選択器126から出力される行列Gの各成分を外部線形メモリに書き込むための、行書き込みアドレス及び列書き込みアドレスを生成する。(図5)に、線形書き込みアドレス生成部135の構成を示す。線形書き込みアドレス生成部135には、log2N×2ビットカウンタ136が含まれており、log2N×2ビットカウンタ136の出力端子の順序が入れ替えられて外部に出力されている。
【0059】log2N×2ビットカウンタ136は、log2N×2個の出力端子が備えられ、出力選択器126から行列Gの各成分を受け取る毎にN×N回カウントを行う。本実施例においてN=8であるから、log2N×2ビットカウンタ136は、0〜63の数値を出力端子u0〜u5に発生する。log2N×2ビットカウンタ136が偶数値をカウントする度に、行書き込みアドレスがインクリメントし、log2N×2ビットカウンタ136が奇数値をカウントする度に列書き込みアドレスがインクリメントする。アドレスを行書き込みアドレス,列書き込みアドレスを生成することにより、行列Gの成分が以下に示す順序で外部線形メモリに書き込まれる。
1 2 17 18 33 34 49 503 4 19 20 35 36 51 525 6 21 22 37 38 53 547 8 23 24 39 40 55 569 10 25 26 41 42 57 5811 12 27 28 43 44 59 6013 14 29 30 45 46 61 6215 16 31 32 47 48 63 64(図6)は、(図1)の第一の定数乗算器104,第二の定数乗算器122と第一の累算器105,第二の累算器123とを構成する各定数乗算器、加算器の詳細図である。以下に定数乗算器104及び第一の定数累算器105の構成の詳細について説明する。
【0060】同図において、ROM501は四つの8×16語の定数ROMからなり、(図1)の定数乗算器104,122に相当する。ROM501に被乗数biと定数との積の値はあらかじめ計算されて格納されている。更に詳しくは、16ビット長の被乗数は4ビット毎に四つに区切られ、この4ビット分と定数との積、つまり、定数の0〜15の倍数が上記の定数ROMに格納されている(このように格納することでROM501の容量は小さくなる。)。また、(数12)よりわかるように定数行列の半分の成分は0(ゼロ)であり、一回の乗算で、被乗数biには四つの定数が乗ぜられるので、これらの四つの定数は共通のアドレスに格納され、被乗数biが入力されると、これらの四つの定数が取り出される。上記の一区切りの4ビットと定数16ビットとの積は20ビット長であり、上記の四つの定数が同一のアドレスに格納されるので、20×4=80ビット長が一語のビット長となる。更にROMに格納される定数行列の成分の半分は0であるので、ROM501には、8×24=128語が格納される。第一の加減算器103から出力される(数12)の右辺第一項の行列の各成分を上記のアドレス指定に用いることで、ROM501から16個の20ビット長の部分積が同時に取り出される。
【0061】第一の累算器105は、5入力を二つの部分和に桁上げ伝播なしに足し合わせるN/2個の桁上げ保存加算器(以下CSA(carry save adder)と略す)及びN/2個の桁上げ伝播加算器(以下CPA(carry propagate adder)と略す)で構成される。図中のCSA502は、5入力を二つの部分和に桁上げ伝播なしに足し合わせる桁上げ保存加算器である。(図7)に示すように、CSA502は三段のCSAで構成される。ROM501から出力される20×4ビットの積のそれぞれ20ビットを、下位のものから順にm0,m1,m2,m3とすると、第一段目のCSAは、m0と累算値とを加算する。第二段目のCSAは、第一段目のCSAの加算結果と、m1を4ビット上位にずらしたものとを加算する。第三、四段目のCSAは、第二、三段目のCSAの加算結果と、m2,m3を8ビット、12ビット上位にずらしたものを加算する。尚、CSA502が行う以上の加算は、桁上げを保存したまま行われる。
【0062】図中のCPA503は、CSA502から出力される加算出力(S)と桁上げ出力(C)とを加算する。加算結果は、適当なビット幅に丸められ、累算シフトレジスタ106に出力される。(図8)は、(図1)の二列シフトレジスタ124a及び二列出力バッファ125b,125c,125dのシフト制御信号のタイミングを表わす図である。同図において、右方向に実行サイクル数、即ち時間を表わす。縦軸に0または1のシフト制御信号の論理値を表わす。シフト制御信号が0の間二列出力バッファ125b,125c,125dは成分を保持し、シフト制御信号が1の間、二列シフトレジスタ124a及び二列出力バッファ125b,125c,125dはシフト動作を行い、二成分ずつ出力選択器126に出力してゆく。
【0063】以上のように構成された本実施例の二次元DCT演算装置の動作を以下に説明する。本実施例の二次元DCT演算装置は、外部線形メモリに対して読み出しを行い、読み出しによって生成する8×8の行列ブロックからなる入力信号系列fijを受け取り、受け取った入力信号系列に対してDCT演算を多段のパイプライン処理を施し、結果のDCT係数系列を外部線形メモリに出力する。
(1) 行読み出しアドレス生成部133が行読み出しアドレスを発生させる。列読み出しアドレス生成部133による読み出し列の指定は一データを読み込む度に第0,7,1,6,2,5,3,4行の順に変わり、これを繰り返す。
(2) 列読み出しアドレス生成部133が一列中の行番号を全て発生すれば、列読み出しアドレス生成部134が列読み出しアドレスを発生させる。列読み出しアドレスによる読み出し列の指定は、一データを一列分読み込む度に第0,7,1,6,2,5,3,4列の順に変わり、これを繰り返す。
(3) 列読み出しアドレスと行読み出しアドレスに基づき、外部線形メモリ中の行列成分データの線形アドレスが計算される。
(4) 線形読み出しアドレス生成部131によって一サイクル毎に8×8行列が、一成分ずつ読み出され、入力信号系列が一成分ずつ生成する。この入力信号系列を入力シフトレジスタ101はシフトしながら読み込む。読む順序は列単位に、第0,7,1,6,2,5,3,4列の順に、列の中では第0,7,1,6,2,5,3,4行の順である。
1 17 33 49 57 41 25 93 19 35 51 59 43 27 115 21 37 53 61 45 29 137 23 39 55 63 47 31 158 24 40 56 64 48 32 166 22 38 54 62 46 30 144 20 36 52 60 44 28 122 18 34 50 58 42 26 10(5) 入力シフトレジスタ101は、読み込んだ二成分分のデータを入力バッファ102に一度に転送する。入力バッファ102は2サイクルの間このデータを保持する。
(6) 第一の加減算器103は最初に加算を行い、次に減算を行う。以降加算と減算を交互に繰り返す。j列データに対する演算はサイクル順にf0j+f7j,f0j−f7j,f1j+f6j,f1j−f6j,f2j+f5j,f2j−f5j,f3j+f4j,f3j−f4jであり、これを順に第0,7,1,6,2,5,3,4列について繰り返す。
(7) 第一の定数乗算器104は、(数12)に基づいて行列各成分の積を出力する。出力された積は、第一の累算器105によって順次累積加算される。累算中の中間値は、累算シフトレジスタ106に保持される。
(8) 累算シフトレジスタ106はシフトを行い、保持している中間値を第一の累算器105にフィードバックする。上記積および累算のステップを4回繰り返せば一列分の中間値が求められる。この中間値とは一次元DCT係数である。一つの列中で第0,2,4,6行,第1,3,5,7行に関する累算が交互に繰り返される。このようなシフトを64サイクル繰り返せば、8×8行列の積が計算される。
(9) 累算シフトレジスタ106に二成分分の中間値が格納されれば、これらを一列分の中間値として一列バッファ111に転送する。
(10) 累算シフトレジスタ106と一列バッファ111とに二列分の中間値が格納されれば、二列シフトレジスタ112に二列分の内容を一度に転送する。
(11) 二列シフトレジスタ112は、行番号0〜7の順にシフトしながら、二成分のデータを第二の加減算器121に出力する。第二の加減算器121は、それらの和または差を計算する。第二の加減算器121は最初に加算を行い、次に減算を行う。以降加算と減算を交互に繰り返す。m行データに対する演算は、サイクル毎に順にhm,0+hm,7,hm,0−hm,7,hm,1+hm,6,hm,1−hm,6,hm,2+hm,5,hm,2−hm,5,hm,3+hm,4,hm,3−hm,4(m=0,・・・・,7)の計算を行う。
(12) 第二の定数乗算器122は、(数13)に基づき行列各成分の積を求め、求めた値を累算中の中間和に順次累積加算する。
(13) 第二の累算器123で加算した結果を二列シフトレジスタ124に出力する。二列シフトレジスタ124は、加算結果を順次シフトしながら保持する。最初のサイクルで四つの二列シフトレジスタ124a,124b,124c,124dそれぞれに第0,2,4,6列の第0行の中間値が、次のサイクルで第1,3,5,7列の第0行の中間値が保持され、以下これが交互に繰り返され行番号がインクリメントしてゆく。最初の16サイクルで行列の各成分と計算される順番との関係を下の表に示す。同じ番号の成分は同時に計算される。
1 2 1 2 1 2 1 23 4 3 4 3 4 3 45 6 5 6 5 6 5 67 8 7 8 7 8 7 89 10 9 10 9 10 9 1011 12 11 12 11 12 11 1213 14 13 14 13 14 13 1415 16 15 16 15 16 15 16上記16サイクルが四回繰り返されれば二次元DCTの演算が完了する。各成分の位置に対し四回累算が行われる。
(14) 三つの二列出力バッファ125b,125c,125dへそれぞれ三つの二列シフトレジスタ124b,124c,124dは、保持している成分をシフトしながら出力する。二列シフトレジスタ124aは上記の出力バッファを介さずに出力選択器126に二成分を出力してゆく。
(15) 線形書き込みアドレス生成部136で行書き込みアドレス及び列書き込みアドレスを発生させる。行書き込みアドレスは、二データを書き込む度に第0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7行の順に変わり、この二列分の指定を4回繰り返す。列書き込みアドレスは二データを書き込む度に第0,1列の順に増加する。次の二列で第2,3列を繰り返し、以後二列毎に第4,5列,第6,7列を指定する。
(16) 列書き込みアドレスと行書き込みアドレスに基づき、線形書き込みアドレス生成部136で外部線形メモリ中の行列成分データの線形アドレスを計算する。
(17)(図8)に示すように、出力選択器126は最初の16サイクルで二列シフトレジスタ124a中に計算された二次元DCT係数を選択出力し、この間に三つの二列シフトレジスタ124b,124c,124dの内容は三つの二列出力バッファ125b,125c,125dへシフトしながら転送される。以後三つの二列出力バッファ125b,125c,125dの内容が順次出力選択器126で選択出力される。上記書き込みアドレスで制御されるように、二次元DCT係数行列の中で書き込む順序は下の表に示す通り。
1 2 17 18 33 34 49 503 4 19 20 35 36 51 525 6 21 22 37 38 53 547 8 23 24 39 40 55 569 10 25 26 41 42 57 5811 12 27 28 43 44 59 6013 14 29 30 45 46 61 6215 16 31 32 47 48 63 64以上のパイプライン処理のタイミングチャートを(図9)に示す。尚、図中の1stDCTとは一段目の一次元DCT を意味し、2nd DCT とは二段目の一次元DCT を意味する。上の多段のパイプライン処理は大きく次の三つの処理部に分かれると見なせる。
第一段‥‥第一段目の一次元DCT演算部‥‥上の説明中(1)〜(8)に相当第二段‥‥中間バッファ‥‥上の説明中(9)〜(10)に相当第三段‥‥第二段目の一次元DCT演算部‥‥上の説明中(11)〜(18)に相当なお本実施例では8×8のDCTに関し記述したが、同じ算法を用いて16×16などへ容易に拡張できる。またビット幅や数表現も16ビット,固定小数点数だけでなく、32ビット浮動小数点数などへ応用できる。また本実施例では、説明の便宜上列方向に読み出しを行うように述べたが、定数行列Cを転置することにより上記の行と列に関する記載を入れ替えた構成も実現できることはいうまでもない。
【0064】
【発明の効果】以上のように本発明の二次元DCT演算装置によれば、N×N画素ブロックの中でデータの入出力順序を最適に入れ替えることにより、より少ない回路規模で同等の性能を発揮できる。画素ブロック単位で成分データの入出力順を入れ替えることはシステム構成上容易に実現できる。また内部のシフトレジスタや中間バッファが削減されるため、DCT演算の潜伏時間(latency)が小さくなる。更に従来の二次元DCT演算装置をより少ないコストで実現し、且つデータを入力してから演算結果を得るまでの潜伏時間を短縮するのでその実用的効果は大きい。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013