(57)【特許請求の範囲】
【請求項１】
以下の関係
【数１】
0003577325.tif 000011
に従ってＮ×Ｎ個のデータｆ（ｘ，ｙ）のデータ表とＮ×Ｎ個の係数Ｆ（ｕ，ｖ）の係数表との間に対応を生じさせる離散余弦変換（ＤＣＴ）データ処理回路におけるデータ処理方法であって、ここで
Ｋは２の定数ベキであり、
ｘ，ｙはデータ表の中のデータの座標を示し、
ｕ，ｖは係数表の中の係数の座標を示し、
ｐ（ｘ，ｕ）＝ｃ（ｕ）．ｃｏｓ［（２ｘ＋１）ｕπ／２Ｎ］、
ｐ（ｙ，ｖ）＝ｃ（ｖ）．ｃｏｓ［（２ｙ＋１）ｖπ／２Ｎ］であり、
ｃ（ｕ），ｃ（ｖ）はｕ，ｖ＝０に対して１／√２であり、ｕ，ｖ≠０に対して１であり、前記方法は以下のステップを達成することによって１対の座標ｕ，ｖに対する各係数Ｆ（ｕ，ｖ）を順次決定することからなり、そのステップは、
データ表の中心軸に対して対称的な値の組によって配列される位置に対応する４つの対（ｘ，ｙ）、（ｘ，ｙ’）、（ｘ’，ｙ）、および（ｘ’，ｙ’）に対して、積Ｐ（ｘ，ｕ，ｙ，ｖ）＝ｐ（ｘ，ｕ）．ｐ（ｙ，ｖ）の絶対値を表でサーチするステップと、
これら４つの対に対応するｆ（ｘ，ｙ）、ｆ（ｘ，ｙ’）、ｆ（ｘ’，ｙ）、およびｆ（ｘ’，ｙ’）の値を演算によって組合わせるステップとを含み、前記演算は、加算および／または減算であって、前記演算の種類は、ｕとｖが奇数か偶数かで決定され、
前記組合された値と前記サーチされた積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値とを乗算するステップと、
前記乗算の結果をアキュムレータ（１７）に導入するステップと、
さらに対ｘ，ｙのすべての値に対して上記ステップを再開するステップとを含み、ｘおよびｙは０から（Ｎ／２）−１の範囲である、離散余弦変換（ＤＣＴ）データ処理回路に
おけるデータ処理方法。
【請求項２】
前記データ処理方法は、
ｐ（ｘ，ｕ）＝Ｓｇｎ［ｐ（ｘ，ｕ）］．｜ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］｜、
ｐ（ｙ，ｖ）＝Ｓｇｎ［ｐ（ｙ，ｖ）］．｜ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］｜であり、ここでｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）は１からＮ−１の範囲の整数であり、積Ｐ（ｘ，ｕ，ｙ，ｖ）＝ｐ（ｘ，ｕ）．ｐ（ｙ，ｖ）であり、
前記データ表をデータ表メモリ（１）に予めストアするステップと、
前記積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値の表を積メモリ（３）に予めストアするステップと、
前記積メモリ（３）をアドレス指定するためのｎ（ｘ，ｕ）の値およびｐ（ｘ，ｕ）の符号を定めた表を予めメモリ（７）にストアするステップと、
前記積メモリ（３）をアドレス指定するためのｎ（ｙ，ｖ）の値およびｐ（ｙ，ｖ）の符号を定めた表を予めメモリ（９）に予めストアするステップとをさらに含み、
前記再開するステップは、値対（ｕ，ｖ）、および各対（ｕ，ｖ）に対して、対（ｘ、ｙ）のすべての値を順次与え、
前記データ処理方法は、さらに、
前記データ表メモリ（１）に、前記再開するステップで与えられた（ｘ，ｙ）に対応するｆ（ｘ，ｙ）、ｆ（ｘ，ｙ’）、ｆ（ｘ’，ｙ）、およびｆ（ｘ’，ｙ’）を与えさせるステップと、
前記メモリ（７）に、前記再開するステップで与えられた（ｘ，ｕ）に対応するｐ（ｘ，ｕ）の符号と、ｎ（ｘ，ｕ）の値を与えさせるステップと、
前記メモリ（９）に、前記再開するステップで与えられた（ｙ，ｖ）に対応するｐ（ｙ，ｖ）の符号と、ｎ（ｙ，ｖ）の値を与えさせるステップとを含み、
前記サーチするステップは、前記与えられたｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）の値を使用して、前記積メモリ（３）に、前記再開するステップで与えられた（ｘ，ｙ，ｕ，ｖ）に対応する積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値を与えさせ、
前記組合わせるステップは、前記与えられたｆ（ｘ，ｙ）、ｆ（ｘ，ｙ’）、ｆ（ｘ’，ｙ）、およびｆ（ｘ’，ｙ’）の値を演算によって組合わせ、
前記乗算するステップは、前記組合された値と、前記与えられた積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値とを乗算し、
前記導入するステップは、前記与えられたｐ（ｘ，ｕ）の符号およびｐ（ｙ，ｖ）の符号の関数で、前記乗算の結果を前の結果から減算するか、またはそれに加算する、請求項１記載のデータ処理方法。
【請求項３】
以下の関係
【数２】
0003577325.tif 000012
に従ってＮ×Ｎ個のデータｆ（ｘ，ｙ）のデータ表とＮ×Ｎ個の係数Ｆ（ｕ，ｖ）の係数表との間に対応を生じさせる離散余弦変換（ＤＣＴ）データ処理回路であって、ここで、
Ｋは２の定数ベキであり、
ｘ，ｙはデータ表のデータの座標を示し、
ｕ，ｖは係数表の係数の座標を示し、
ｐ（ｘ，ｕ）＝ｃ（ｕ）．ｃｏｓ［（２ｘ＋１）ｕπ／２Ｎ］、
ｐ（ｙ，ｖ）＝ｃ（ｖ）．ｃｏｓ［（２ｙ＋１）ｖπ／２Ｎ］であり、
ｃ（ｕ），ｃ（ｖ）はｕ，ｖ＝０に対して１／√２であり、ｕ，ｖ≠０に対して１であ
り、前記離散余弦変換（ＤＣＴ）データ処理回路は、以下の手段によって１対の座標ｕ，ｖに対する各係数Ｆ（ｕ，ｖ）を順次決定し、その手段は、
データ表の中心軸に対して対称的な値の組によって配列される位置に対応する４つの対（ｘ，ｙ）、（ｘ，ｙ’）、（ｘ’，ｙ）、および（ｘ’，ｙ’）に対して、積Ｐ（ｘ，ｕ，ｙ，ｖ）＝ｐ（ｘ，ｕ）．ｐ（ｙ，ｖ）の絶対値を表でサーチする手段と、
これら４つの対に対応するｆ（ｘ，ｙ）、ｆ（ｘ，ｙ’）、ｆ（ｘ’，ｙ）、およびｆ（ｘ’，ｙ’）の値を演算によって組合せる手段とを含み、前記演算は、加算および／または減算であって、前記演算の種類は、ｕとｖが奇数か偶数かで決定され、
前記組合された値と前記サーチされた積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値とを乗算する手段と、
前記乗算の結果をアキュムレータ（１７）に導入する手段と、
さらに対ｘ，ｙのすべての値に対して上記ステップを再開する手段とを含み、ｘおよびｙは０から（Ｎ／２）−１の範囲である、離散余弦変換（ＤＣＴ）データ処理回路。
【請求項４】
前記離散余弦変換（ＤＣＴ）データ処理回路は、
ｐ（ｘ，ｕ）＝Ｓｇｎ［ｐ（ｘ，ｕ）］．｜ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］｜、
ｐ（ｙ，ｖ）＝Ｓｇｎ［ｐ（ｙ，ｖ）］．｜ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］｜であり、ここでｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）は１からＮ−１の範囲の整数であり、積Ｐ（ｘ，ｕ，ｙ，ｖ）＝ｐ（ｘ，ｕ）．ｐ（ｙ，ｖ）であり、
前記データ表を記憶するデータ表メモリ（１）と、
前記積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値の表を記憶する積メモリ（３）と、
前記積メモリ（３）をアドレス指定するためのｎ（ｘ，ｕ）の値およびｐ（ｘ，ｕ）の符号を定めた表を記憶するメモリ（７）と、
前記積メモリ（３）をアドレス指定するためのｎ（ｙ，ｖ）の値およびｐ（ｙ，ｖ）の符号を定めた表を記憶するメモリ（９）とをさらに備え、
前記再開する手段は、値対（ｕ，ｖ）、および各対（ｕ，ｖ）に対して、対（ｘ、ｙ）のすべての値を順次与える座標発生器（５）であり、
前記データ表メモリ（１）は、前記座標発生器（５）で与えられた（ｘ，ｙ）に対応するｆ（ｘ，ｙ）、ｆ（ｘ，ｙ’）、ｆ（ｘ’，ｙ）、およびｆ（ｘ’，ｙ’）を与え、
前記メモリ（７）は、前記座標発生器（５）で与えられた（ｘ，ｕ）に対応するｐ（ｘ，ｕ）の符号と、ｎ（ｘ，ｕ）の値を与え、
前記メモリ（９）は、前記座標発生器（５）で与えられた（ｙ，ｖ）に対応するｐ（ｙ，ｖ）の符号と、ｎ（ｙ，ｖ）の値を与え、
前記サーチする手段は、前記与えられたｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）の値を使用して、前記積メモリ（３）に、前記座標発生器（５）で与えられた（ｘ，ｙ，ｕ，ｖ）に対応する積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値を与えさせ、
前記組合わせる手段は、前記与えられたｆ（ｘ，ｙ）、ｆ（ｘ，ｙ’）、ｆ（ｘ’，ｙ）、およびｆ（ｘ’，ｙ’）の値を演算によって組合わせ、
前記乗算する手段は、前記組合された値と、前記与えられた積Ｐ（ｘ，ｕ，ｙ，ｖ）の絶対値とを乗算する乗算器（１１）であり、
前記導入する手段は、前記与えられたｐ（ｘ，ｕ）の符号およびｐ（ｙ，ｖ）の符号の関数で、前記乗算の結果を前の結果から減算するか、またはそれに加算するトータライザ（１３）である、請求項３記載の離散余弦（ＤＣＴ）データ処理回路。
【請求項５】
前記組合わせる手段は、
｛ｆ（ｘ，ｙ）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ）＋ｐａｒ（ｖ）［（ｆ（ｘ，ｙ′）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ′）］｝
を生成し、ここで
ｘ′＝Ｎ−１−ｘであり、
ｙ′＝Ｎ−１−ｙであり、
ｐａｒ（ｕ）およびｐａｒ（ｖ）は、ｕまたはｖが偶数であるか奇数であるかに依存して＋１または−１である、請求項４に記載の離散余弦（ＤＣＴ）データ処理回路。
【請求項６】
前記組合わせる手段は、
ｆ（ｘ，ｙ）、ｆ（ｘ′，ｙ）およびｐａｒ（ｕ）を受けて、ｆ（ｘ，ｙ）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ）を与える第１の加算器／減算器（２３）と、
ｆ（ｘ，ｙ′）、ｆ（ｘ′，ｙ′）およびｐａｒ（ｕ）を受けて、ｆ（ｘ，ｙ′）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ′）を与える第２の加算器／減算器（２４）と、
前記第１の加算器／減算器（２３）により与えられたｆ（ｘ，ｙ）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ）、前記第２の加算器／減算器（２４）により与えられたｆ（ｘ，ｙ′）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ′）、およびｐａｒ（ｖ）を受けて、ｆ（ｘ，ｙ）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ）＋ｐａｒ（ｖ）［ｆ（ｘ，ｙ′）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ′）］を与える第３の加算器／減算器（２５）とを含む、請求項５に記載の離散余弦（ＤＣＴ）データ処理回路。
【請求項７】
以下の関係
【数３】
0003577325.tif 000013
に従ってＮ×Ｎ個の係数Ｆ（ｕ，ｖ）の係数表とＮ×Ｎ個のデータｆ（ｘ，ｙ）のデータ表との間に対応を生じさせる逆離散余弦変換によってデータを処理するための回路であって、ここで
Ｋは２の定数ベキであり、
ｘ，ｙはデータ表のデータの座標を示し、
ｕ，ｖは係数表の係数の座標を示し、
ｃ（ｕ），ｃ（ｖ）はｕ，ｖ＝０に対して１／√２であり、かつｕ，ｖ≠０に対して１であり、前記回路は、
前記係数表を記憶する係数表メモリ（１）と、
積Ｐ（ｘ、ｕ、ｙ、ｖ）＝ｃｏｓ［ｎ（ｘ，ｙ）π／２Ｎ］×ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］の絶対値の表を記憶する積メモリ（３）とを含み、ここでｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）は１からＮ−１の範囲の整数であり、
ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］の符号とｎ（ｘ，ｕ）の値を定めた表を記憶するメモリ（７）と、
ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］の符号とｎ（ｙ，ｖ）の値を定めた表を記憶するメモリ（９）と、
データ表の第１の象限に対応する値の対（ｘ，ｙ）と、各対（ｘ，ｙ）に対して、対（ｕ、ｖ）のすべての値と、ｕおよびｖが偶数であるか奇数であるかに依存して＋１または−１に等しい信号ｐａｒ（ｕ）およびｐａｒ（ｖ）を順次与える座標発生器（５）と、
前記積メモリ（３）内の表によって与えられる積Ｐ（ｘ、ｕ、ｙ、ｖ）の絶対値と、前記係数表メモリ（１）内の係数表によって与えられるＦ（ｕ、ｖ）との積を計算する乗算器（１１）と、
前記メモリ（７）内の表によって与えられるｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］の符号、前記メモリ（９）内の表によって与えられるｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］の符号、ｐａｒ（ｕ）の値、およびｐａｒ（ｖ）の値の関数で、前の結果から乗算の結果を減算して、または前の結果に乗算の結果を加算して、それぞれｆ（ｘ，ｙ）、ｆ（ｘ′，ｙ）、ｆ（ｘ，ｙ′）およびｆ（ｘ′，ｙ′）を与える４つのトータライザ（１３）とを含み、ここで
ｘ′＝Ｎ−１−ｘであり、かつ
ｙ′＝Ｎ−１−ｙである、回路。
【請求項８】
前記係数表メモリ（１）は非ゼロ係数のみを含み、前記メモリの各ワードは前記係数の座標ｕ，ｖが後に続く非ゼロ係数値を含む、請求項７に記載の回路。
【発明の詳細な説明】
【０００１】
【技術分野】
この発明は、いわゆる「離散余弦変換」（ＤＣＴ）を達成するためのディジタル信号処理のための方法および回路に関する。
【０００２】
【背景技術】
この型の変換はディジタル出力値または係数のマトリックス（またはブロック）と、ディジタル入力値のマトリックスとの間に対応を生じさせる。この変換はもし対応する信号が変換なしに伝送されれば可能であろう速度より速い速度で伝送されるように画像を圧縮するために特に有用である。
【０００３】
余弦変換はそれ自体は何らデータ圧縮を達成することはなく、この圧縮は変換回路の下流に位置決めされたエンコーダによって行なわれる。しかしながら、変換回路は容易に圧縮され得る入力データをエンコーダで与えることによって圧縮をより容易にする。この変換回路は黒および白または色画像のディジタル伝送に非常によく使用され、この例を参照することによってこの発明を説明することにする。したがって、ディジタル入力値のマトリックスはピクセルマトリックスに対応するであろう。余弦変換を達成するために、伝送されるべき画像または枠はｎ行およびｎ列のブロックに配列され、各ブロック点はディジタル値、たとえば、８−ビットの符号化された値によって表わされるピクセルに対応する。この値は、たとえばピクセルの輝度またはクロミナンス成分に対応する。
【０００４】
余弦変換はｎｘｎピクセルのブロックとｎｘｎ係数のブロックとの間に対応を生じさせる。ブロックの座標ｘおよびｙを有するピクセルの値をｆ（ｘ，ｙ）と呼ぶ。Ｆ（ｕ，ｖ）は余弦変換に従って計算され、かつ変換されたブロックにおいて線ｕと列ｖとの交点に位置決めされる係数を示す。最も一般的な場合において、ｎ＝８ならびにｘ、ｙ、ｕおよびｖは０から７の範囲であろう。
【０００５】
以下の説明では、８ｘ８ピクセルブロックのこの具体例のみを考慮することにする。当業者はｎｘｎピクセルブロックに対する対応する公式を容易に計算するまたは専門文献で見つけることが可能であろう。このように、考慮される具体例において、余弦変換は以下の関係によって示される。
【０００６】
【数５】
0003577325.tif 000002
【０００７】
この公式において、
Ｋは２の積分ベキとして表わされる標準化係数であり、
ｘ、ｙは開始ブロックのピクセルの空間座標であり、
ｕおよびｖは変換されたブロックの係数の空間座標であり、
ｆ（ｘ，ｙ）は開始ブロックのピクセルの値であり、
Ｆ（ｕ，ｖ）は余弦変換の係数の値であり、
ｃ（ｕ）、ｃ（ｖ）はｕ，ｖ＝０に対して１／√２であり、ｕ，ｖ≠０に対して１である。
【０００８】
達成されるべきＤＣＴ作用素の計算ベキは秒当たりの処理されるべきブロックの数に依存する。従来のまたは高品位テレビ画像のために、数１００キロブロックが秒当たり処理されなければならず、この目的を達成するために、ビヨン・ジー・リー（Ｂｙｏｎｇ  Ｇｉ  Ｌｅｅ）アルゴリズムのような複素アルゴリズム関数を実現化する専用集積回路に頼るものもある。これらの回路は非常に速い処理動作を達成するが、様々な動作を同時に達成するために数多くの構成要素を必要とし、それゆえに集積回路上の大きな表面を占有するという欠点を有する。
【０００９】
かかる回路はまた解決するべき問題がより単純であり、かつ秒あたり少数のブロックしか処理する必要がない、たとえばビデオホン型の画像を処理する場合にもよく使用され、この場合約１０キロブロック／秒の処理が十分であるように思われる。
【００１０】
このように、この発明の目的は小型の集積回路の形で達成され得る離散余弦変換によってデータを処理するための方法および回路を提供することである。
【００１１】
【発明の概要】
この目的を達成するために、この発明は、以下の関係に従ってＮ×Ｎデータの表ｆ（ｘ，ｙ）とＮ×Ｎ係数の表Ｆ（ｕ，ｖ）との間に対応を生じさせるＤＣＴデータ処理方法を提供し、
【００１２】
【数６】
0003577325.tif 000003
【００１３】
ここでＫは２の定数ベキであり、
ｘ，ｙはデータ表のデータの座標を示し、
ｕ，ｖは係数表の係数の座標を示し、
ｐ（ｘ，ｕ）＝ｃ（ｕ）．ｃｏｓ［（２ｘ＋１）ｕπ／２Ｎ］
ｐ（ｙ，ｖ）＝ｃ（ｖ）．ｃｏｓ［（２ｙ＋１）ｖπ／２Ｎ］
であり、
ｃ（ｕ）、ｃ（ｖ）はｕ，ｖ＝０に対して１／√２であり、ｕ，ｖ≠０に対して１である。
この方法は以下のステップを達成することによって１対の座標ｕ，ｖに対する各係数Ｆ（ｕ，ｖ）を順次決定することからなり、そのステップは第１の対ｘ，ｙに対して、係数Ｐ＝ｐ（ｘ，ｕ）．ｐ（ｙ，ｖ）の絶対値および符号を表でサーチするステップと、ｐの絶対値にｆ（ｘ，ｙ）を乗算するステップと、加算または減算によってその乗算の結果を符号の関数でアキュムレータに導入するステップと、さらに対ｘ，ｙのすべての値に対してこの動作を再開し、かつアキュムレータによって与えられた結果を抽出するステップとである。
【００１４】
この発明の一実施例に従って、表でサーチするステップは以下のように達成される、つまり、ｘおよびｕによってアドレス指定された第１の表で、ｐ（ｘ，ｕ）の符号および項ｎ（ｘ，ｕ）（１からＮ−１の範囲である）をサーチするステップを含み、ｐ（ｘ，ｕ）＝Ｓｇｎ［ｐ（ｘ，ｕ）］．｜ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］｜であり、ｙおよびｖによってアドレス指定された第２の表で、ｐ（ｙ，ｖ）の符号および項ｎ（ｙ，ｖ）（１からｎ−１の範囲である）をサーチするステップを含み、ｐ（ｙ，ｖ）＝Ｓｇｎ［ｐ（ｙ，ｖ）］．｜ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］｜であり、さらにｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）によってアドレス指定された第３の表で、係数Ｐの絶対値をサーチするステップとで達成される。
【００１５】
この方法の他の局面は以下のステップを達成することによって１対の座標ｕ，ｖに対する各係数Ｆ（ｕ，ｖ）を順次決定することであり、そのステップはデータ表の中心軸に対して組毎に対称的な位置に対応する４つの対ｘ，ｙに対して、係数Ｐ＝ｐ（ｘ，ｕ）．ｐ（ｙ，ｖ）の絶対値を表でサーチするステップと、これらの４つの対に対する加算および／または減算によって対応するデータの値を結合するステップとを含み、各動作の符号は４つのデータの相対的な位置の関数で決定され、結合された値に係数Ｐの値を乗算するステップと、その乗算の結果をアキュムレータに導入するステップと、さらに対ｘ，ｙのすべての値に対してその動作を再開するステップとを含み、ｘおよびｙは０から（Ｎ／２）−１の範囲である。
【００１６】
他のアプローチに従って、この発明はブロックの各ケースが座標ｘ，ｙに対応するメモリにストアされたＮ×Ｎデータのブロックのデータ（ｆ（ｘ，ｙ））をＤＣＴ処理して、係数のブロックの係数（Ｆ（ｕ，ｖ））を与えるための方法を提供し、この方法はメモリのケースをアドレス指定するステップと、そのケースの内容を乗算器の第１の入力に与えるステップと、第１の表に、１からＮ−１の範囲のパラメータｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）のすべての値に対して
Ｐ＝ｃｏｓ［ｎ（ｘ，ｙ）π／２Ｎ］．ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］
の値をストアするステップと、第２の表に、一方でｕとｘ、他方でｖとｙの値の関数で余弦関数の符号の値、およびｎ（ｘ，ｙ）とｎ（ｙ，ｖ）の値をストアし、かつこれらの値を第１の表をアドレス指定するために使用するステップと、各クロックパルスでデータブロックのケースの値に第１の表の値を乗算するステップと、さらにｘおよびｙのすべての値に対して第２の表によって決定された符号の関数で加算または減算によってその乗算の結果を累積するステップとを含む。
【００１７】
この発明はさらにＮ×Ｎデータの表ｆ（ｘ，ｙ）とＮ×Ｎ係数の表Ｆ（ｕ，ｖ）との間に対応を生じさせるＤＣＴデータ処理回路を提供し、データ処理回路はデータ表メモリと、積
Ｐ＝｜ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］．ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］｜のメモリとを含み、
ｐ（ｘ，ｕ）＝Ｓｇｎ［ｐ（ｘ，ｕ）］．｜ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］｜
ｐ（ｙ，ｖ）＝Ｓｇｎ［ｐ（ｙ，ｖ）］．｜ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］｜であり、
ここでｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）は１からＮ−１の範囲の整数であり、積メモリをアドレス指定するｐ（ｘ，ｕ）およびｐ（ｙ，ｖ）の符号ならびにｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）の値の表と、値対（ｕ，ｖ）、および各対（ｕ，ｖ）に対して、対のすべての値（ｘ，ｙ）を順次与える座標発生器と、Ｐのデータメモリのデータ組合せとの積を計算する乗算器と、さらに符号表によって与えられる符号の関数でその乗算の結果を以前の結果で減算するまたは加算するトータライザとを含む。
【００１８】
相互的に、この発明は以下の関係に従ってＮ×Ｎ係数（Ｆ（ｕ，ｖ））の表とＮ×Ｎデータ（ｆ（ｘ，ｙ））の表との間に対応を生じさせる逆離散余弦変換によって係数を処理するための回路を提供し、
【００１９】
【数７】
0003577325.tif 000004
【００２０】
ここでＫは２の定数ベキであり、
ｘ，ｙはデータ表のデータの座標を示し、
ｕ，ｖは係数表の係数の座標を示し、
ｃ（ｕ）、ｃ（ｖ）はｕ，ｖ＝０に対して１／√２であり、ｕ，ｖ≠０に対して１である。
【００２１】
この回路は係数表のメモリと、積
Ｐ＝ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］．ｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］
のメモリとを含み、ここでｎ（ｘ，ｕ）およびｎ（ｕ，ｖ）は１から（Ｎ／２）−１の範囲の整数であり、ｃｏｓ［ｎ（ｘ，ｕ）π／２Ｎ］およびｃｏｓ［ｎ（ｙ，ｖ）π／２Ｎ］ならびにｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）の符号の表と、データ表の第１の象限およびｕとｖとが偶数であるか奇数であるかに依存して＋１または−１に等しい信号ｐａｒ（ｕ）およびｐａｒ（ｖ）に対応する値の対（ｘ，ｙ）、ならびに各対（ｘ，ｙ）に対して対のすべての値（ｕ，ｖ）を順次与える座標発生器と、ｐの係数メモリの係数組合せとの積を計算する乗算器と、さらに符号表ならびにｐａｒ（ｕ）およびｐａｒ（ｖ）の値によって与えられる符号の関数で、以前の結果からその乗算の結果を減算して、または以前の結果にその乗算の結果を加算して、それぞれｆ（ｘ，ｙ）、ｆ（ｘ′，ｙ）、ｆ（ｘ，ｙ′）およびｆ（ｘ′，ｙ′）を与える４つのトータライザとを含み、ここでｘ′＝Ｎ−１−ｘおよびｙ′＝Ｎ−１−ｙである。
【００２２】
この発明の前述および他の目的、特徴、局面および利点は添付の図面に関連して考えられるこの発明の以下の詳細な説明から明らかになるであろう。
【００２３】
【発明を実行するためのベストモード】
この発明は上述のＤＣＴ公式（１）の分析に基づく。先行技術において、これらの方法を実現化するために使用される方法および回路は、本質的に益々多くなる電子構成要素の数を犠牲にして、最大可能数の動作を同時に達成することを目標としているが、この発明の目的は可能な最も単純な方法で一連にこれらの機能を達成し、かつ可能な限り少ない電子構成要素を使用する一方で、秒当たり約２、３０キロブロックの画像シーケンスを処理するために十分な計算力を与えることである。
【００２４】
上の公式（１）は以下のように書直すことが可能であり、
【００２５】
【数８】
0003577325.tif 000005
【００２６】
ここで
Ｐ（ｘ，ｕ，ｙ，ｖ）＝ｐ（ｘ，ｕ）ｐ（ｙ，ｖ）
であり、
0003577325.tif 000006
であり、かつ
0003577325.tif 000007
であり、ここで
ｎ（ｘ，ｕ）またはｎ（ｙ，ｖ）＝１ないし７であり、さらに
Ｓｇｎ［ｐ（ｘ，ｕ）］またはＳｇｎ［ｐ（ｙ，ｖ）］＝±１はｐの符号を示す。
【００２７】
これらの公式において、
もしｕ＝０であれば、余弦は１に等しく、かつ
ｐ（ｘ，ｕ）＝ｃ（ｕ）＝１／√２＝ｃｏｓ４π／１６であり、
もしｕ≠０であれば、ｃ（ｕ）＝１であり、かつ
ｐ（ｘ，ｕ）＝ｃｏｓ［（２ｘ＋１）ｕπ／１６］である。
【００２８】
同一の計算がｃ（ｖ）およびｐ（ｙ，ｖ）に当てはまる。
これはｐ（ｘ，ｕ）またはｐ（ｙ，ｖ）が正または負の符号を有するπ／１６の第１の象限倍数の弧の余弦の絶対値に常に等しいことを意味する。したがって、Ｆ（ｕ，ｖ）の各値はｆ（ｘ，ｙ）の正または負の符号を有する型｜ｃｏｓ［ｎ（ｘ，ｕ）π／１６］．ｃｏｓ［ｎ（ｙ，ｖ）π／１６］｜の係数Ｐとの６４の積の和に対応する。一方、｜Ｐ｜は４９の異なる値をとる。
【００２９】
このように、この発明はＤＣＴ処理のための基礎となるべき各積ｃｏｓ［ｎ（ｘ，ｕ）π／１６］．ｃｏｓ［ｎ（ｙ，ｖ）π／１６］の一方で符号および他方で絶対値を表にストアすることを提供する。より特定的に、この発明は第１のメモリで２つの表を使用することを提供し、そのうちの一方はｘおよびｕの現在値を受け、かつｎ（ｘ，ｕ）およびＳｇｎ（ｘ，ｕ）を与え、第２の表はｙおよびｖの現在値を受け、かつｎ（ｙ，ｖ）およびＳｇｎ（ｙ，ｖ）を与える。ｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）の値は双方ともＰの絶対値（余弦積）を含む第２のメモリのためのアドレスして機能する。上の公式に戻って、８ｘ８のブロックの具体例において、表は相対的に小さなサイズ（第１の表の各々に対して６４の４−ビットワード、および第２のメモリに対して典型的に１２のビットの４９のワード）を有することが認められるであろう。
【００３０】
図１はこの発明に従う第１のＤＣＴ回路実施例を表わすブロック図である。
処理されるべきブロックｘ，ｙのピクセルは処理されるべき８ｘ８のブロックの６４のピクセルを最初に含むメモリ１にストアされる。実務において、次のブロックの記憶の間の時間の浪費を回避するために、メモリのサイズを二倍にし、かつそれに二重接続ポートを与えることが賢明である。１つのブロックが処理されている間に、次のブロックが先行技術に従って同時に獲得されるであろう。
【００３１】
リードオンリメモリ（ＲＯＭ）３はすべての積
Ｐ＝｜Ｐ（ｘ，ｕ，ｙ，ｖ）｜＝｜ｃｏｓ［ｎ（ｘ，ｕ）π／１６］．ｃｏｓ［ｎ（ｙ，ｖ）π／１６］｜、
つまり４９の係数を含む。座標発生器ｙ、ｘ、ｕ、ｖはｕおよびｖの値の６４の組合せを与え、かつ各対（ｕ，ｖ）に対して、６４のクロックパルス内でｘ，ｙの６４の可能性のある値、つまりブロック１の６４のメモリピクセルを走査する。座標ｘ，ｙはランダムに走査されるが、対（ｕ，ｖ）の走査順序は回路出力で入手されるべき順序の関数で選択されることが認められるであろう。たとえば、もしＣＣＩＴＴ  Ｈ２６１標準要求に応じる出力を与えることが所望されれば、マトリックスｕ，ｖの走査はジグザグ型で達成されるであろう。
【００３２】
表７は各対（ｘ，ｕ）に対してｐ（ｘ，ｕ）の符号の対応する値（以下Ｓｇｎ［ｐ（ｘ，ｕ）］またはより単純にＳｇｎ（ｘ，ｕ）と呼ぶ）を与える。この表はまたメモリ３のアドレスの半割りｎ（ｘ，ｕ）を与える。表９はｙおよびｖに対して類似の機能を達成する。
【００３３】
各対ｘ，ｙに対して、乗算器１１は現在のピクセルの値ｆ（ｘ，ｙ）のＰとの積を与える。この積はトータライザ１３に与えられ、トータライザは６４のクロックパルス毎に対ｕ，ｖに対して対応する係数Ｆ（ｕ，ｖ）の値を与える。トータライザ１３は加算器−減算器１５およびアキュムレータ１７を含む。アキュムレータ１７は６４のクロックパルスの間加算器１５の出力の代数和をストアする。加算器は第１の入力でアキュムレータ１７に累積された部分結果を受け、かつその第２の入力で表７および表９の出力で入手されたＳｇｎ（ｘ，ｕ）およびＳｇｎ（ｙ，ｖ）の代数積を与える符号判別回路１９の出力に依存する符号（＋）または（−）を有する現在積Ｐ．ｆ（ｘ，ｙ）を受ける。
【００３４】
図１の回路を使って、６４のクロックパルスは各係数Ｆ（ｕ，ｖ）を計算するために必要であり、かつ故にブロックの６４のＤＣＴ係数を計算するために６４．６４＝４０９６クロックパルスが必要である。図１の回路で最も遅い動作速度を有する要素は乗算器１１である。１６−ＭＨｚクロックパルス内で１つの乗算を行なうことを可能にする技術は４キロブロック／秒の計算ベキを可能にする。
【００３５】
一方、図１の回路の大きさのより正確な近似値を有するために、８ｘ８ブロックに対して座標発生器は３ビットで各座標を与え、かつもしブロックメモリのピクセルが鮮明度を損なわないように８ビットで規定されれば、Ｐの値は１２ビットで実質的に規定されなければならないことが認められるであろう。
【００３６】
この発明の第２の実施例において、係数Ｆ（ｕ，ｖ）が１６−ＭＨｚクロックパルス内で１１−ビット数に１２−ビット数を乗算する単一の乗算器を使用することによって伝えられる速度を増大することが工夫される。この目的を達成するために、係数ｐのより正確な分析が考慮に入れられる。したがって、これらの係数が以下の特徴を満たすことを認めることが可能である。
【００３７】
もしｘ′＝７−ｘであれば、
それならもしｕが偶数であればｐ（ｘ′，ｕ）＝＋ｐ（ｘ，ｕ）であり、
もしｕが奇数であればｐ（ｘ′，ｕ）＝−ｐ（ｘ，ｕ）である。
【００３８】
ｕのパリティを示すために表記ｐａｒ（ｕ）を使用することによって、この式は以下のように書くことが可能であり、
ｐ（ｘ′，ｕ）＝ｐａｒ（ｕ）．ｐ（ｘ，ｕ）
ここで、ｐａｒ（ｕ）はもしｕが偶数であれば＋１であり、もしｕが奇数であれば−１である。
【００３９】
このように上の式（１）に戻って、かつ前の見解を考慮に入れることによって、以下のように書くことが可能である。
【００４０】
【数９】
0003577325.tif 000008
【００４１】
図２に示されるように、この式はピクセルｘ，ｙの表の中心軸に対して対称的な４組のピクセル、つまりピクセル（ｘ，ｙ）（ｘ′，ｙ）（ｘ，ｙ′）（ｘ′，ｙ′）に対して、乗算係数Ｐはピクセルに対応するデータがその位置の関数で正または負の符号を与えられるとすれば同一であろうことを意味する。しかしながら、二重和は上に示されたように、８ｘ８＝６４の代わりに４ｘ４＝１６項のみに関する。２つの結論が引出される、つまり一方で図１のメモリ７および９のサイズは減少されることが可能であり、他方で係数Ｆ（ｕ，ｖ）は６４の代わりにわずか１６のクロックパルス内で計算することが可能である。このように、計算速度は４倍速くなりかつ約１６キロブロック／秒の速度、つまり上に示したようにビデオホンデータを処理するのに十分速い速度を与える。
【００４２】
図３はこの発明の第２の実施例を実現化する回路を概略的に示す。図１の回路と同様に、図３の回路はブロックメモリ１、係数Ｐのメモリ３、データ発生器５、ＲＯＭ３をアドレス指定するためにそれぞれ値ｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）を与え、かつまたＰの符号を与える回路１９にｐ（ｘ，ｕ）およびｐ（ｙ，ｖ）の符号を与える表７および９を含む。Ｐの絶対値は乗算器１１に与えられ、その出力は周期的に連続値Ｆ（ｕ，ｖ）を与えるトータライザ１３に接続される。
【００４３】
図１の回路との主要な違いは座標発生器５がメモリ１の４つのピクセル、つまりピクセルｆ（ｘ，ｙ）、ｆ（ｘ′，ｙ）、ｆ（ｘ，ｙ′）およびｆ（ｘ′，ｙ′）を同時にアドレス指定することである。総和回路２１は、
ｆ（ｘ，ｙ）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ）＋ｐａｒ（ｖ）［（ｆ（ｘ，ｙ′）＋ｐａｒ（ｕ）ｆ（ｘ′，ｙ′）］
の値を与える。
【００４４】
回路２１の出力は乗算器１１の第２の入力に与えられる。
説明された実施例において、総和回路２１は３つの加算器／減算器を含む。第１のもの２３はｆ（ｘ，ｙ）＋ｐａｒ（ｕ）．ｆ（ｘ′，ｙ）を与え、かつ座標発生器５から入力ｐａｒ（ｕ）を受ける。  同様に、第２のもの２４はｆ（ｘ，ｙ′）＋ｐａｒ（ｕ）．ｆ（ｘ′，ｙ′）を与え、かつ座標発生器５から入力ｐａｒ（ｕ）を受ける。第３のもの２５は最終結果を与え、かつ座標発生器５から信号ｐａｒ（ｖ）を受ける。
【００４５】
この実施例において、各対の値ｕ，ｖに対して、ｙの４つの値およびｘの４つの値のみが走査され、それは上述のように総和回路２１を付加することを犠牲にして動作持続期間を減少させる。回路２１のみが加算器を含むので、それは製造するのが特に単純でありかつ集積回路上の小さな表面を占有するであろう。
【００４６】
この発明をよりよく理解するために、図４はｕの８つの値およびｘの４つの走査された値の各々に対応するｎ（ｘ，ｕ）およびＳｇｎ（ｘ，ｕ）の値の表を示す（ｎは公式（２）および（３）で規定されたことが思い出されなければならない）。
【００４７】
【逆離散余弦変換】
逆離散余弦変換８ｘ８は以下のように書かれる。
【００４８】
【数１０】
0003577325.tif 000009
【００４９】
この等式は直接ＤＣＴを決定するための等式（１）と同一の形式を有する。したがって、図１の回路は修正することなくｆ（ｘ，ｙ）およびＦ（ｕ，ｖ）を交換することによって逆ＤＣＴを計算することが可能である。
【００５０】
しかしながら、係数Ｐの因数分解を利用する図３の回路は可逆的ではない。しかし、図１の回路に対して回路の動作を因数４だけ加速するための対応する構造は逆ＤＣＴの計算に適合可能である。
【００５１】
実際、同一の積
Ｆ（ｕ，ｖ）．ｐ（ｘ，ｕ）．ｐ（ｙ，ｖ）
はその符号を除いては４つのピクセルの和の計算に含まれることが認められる。言換えれば、逆離散余弦変換の作用素は直接ＤＣＴ計算機と同一の性能を有するように、６４のクロックパルス内で４つのピクセルを同時に計算することが可能である。前のようにｘ′＝７−ｘおよびｙ′＝７−ｙを考慮すると、以下の関係（５）が得られる。
【００５２】
【数１１】
0003577325.tif 000010
【００５３】
これらの関係を利用する回路は図５に示される。
図５において、前の図面の要素に類似する要素は同一の参照番号で示される。この回路はブロックメモリ１を含むが、ピクセルｆ（ｘ，ｙ）のブロックの代わりに、それらはここで係数Ｆ（ｕ，ｖ）のブロックである。前のように、ＲＯＭ３はＰの値、つまりｃｏｓ（ｎπ１６）の積の絶対値を含み、かつ座標発生器５ならびに項ｎ（ｘ，ｕ）およびｎ（ｙ，ｖ）の値を決定する表７および９に関連する。乗算器１１は一方でブロックメモリ１から値Ｆ（ｕ，ｖ）を直接受け、かつ他方でＲＯＭ３から値Ｐを受ける。乗算の結果は４つのトータライザ３１、３２、３３、３４に同時に与えられ、それらに対して加算または減算選択が回路１９からの出力Ｓｇｎ、および座標発生器５の出力で供給されるようなｕおよびｖのパリティ値の関数で決定される。４つのトータライザの出力は同時に与えられるので、それらは適当な速度で出力線４０に与えられる前にレジスタ３５、３６、３７、３８で一時的にストアされる。
【００５４】
しかしながら、線４０上のピクセル出力は等式（５）の要求によって課せられたシーケンスで与えられる。つまり、ピクセルマトリックスの中心軸に対して対称的な組に配列された４つの位置に対応するピクセルは順次与えられる。これはピクセルマトリックスの所望の走査シーケンスに一般に対応しない。したがって、出力４２上の所望の順序でピクセルを再配列するために出力順列回路４１を与えることが時として必要であろう。
【００５５】
付加的に、逆ＤＣＴの計算に関して、ＤＣＴ動作は最も高い振幅を有する係数のみを伝送するように係数を後に定量化するために一般に達成されることが認められるであろう。したがって、逆変換動作が行なわれなればならないとき、項の大半がゼロである係数Ｆ（ｕ，ｖ）のマトリックスが一般に入手される。したがって、様々な方法が図１または図５に示されるような回路による計算サイクルにゼロ係数をさらすことを回避するために使用され得る。これはたとえばブロックメモリおよび座標発生器を以下のように修正することによって達成され得る。
【００５６】
−  ブロックメモリは係数リストを含むメモリになる。同一のブロックの非ゼロ係数は変数長のリストの形式で連続メモリアドレスでそこにストアされる。このメモリの各ワードは一方でＦ（ｕ，ｖ）、つまり係数の値を、かつ他方でこの係数（各３ビット）の座標ｕ，ｖを含み、最後にリスト終端ビットｆｂを含む。
【００５７】
−  座標発生器はｘおよびｙを伝達し続けるが、ｕおよびｖの値はブロックメモリの出力によって与えられる。最後に、ブロックメモリは次のリストを処理する前に６４回（図１の例において）、または１６回（図５の例において）リストを走査するようにアドレス指定されなければならない。
【図面の簡単な説明】
【図１】この発明の第１の実施例を示す図である。
【図２】この発明の第２の実施例で実現化される方法を理解するために有用な例証的なブロック図である。
【図３】この発明の第２の実施例を示す図である。
【図４】ｕおよびｘの様々な値に対する係数値の表を示す図である。
【図５】逆離散余弦変換を決定するための回路を示す図である。
【符号の説明】
５  座標発生器
１１  乗算器
１３  トータライザ
１７  アキュムレータ
２１  回路
【図１】
0003577325.tif 000014
【図２】
0003577325.tif 000015
【図３】
0003577325.tif 000016
【図４】
0003577325.tif 000017
【図５】
0003577325.tif 000018