JPH0526229B2 - - Google Patents
Info
- Publication number
- JPH0526229B2 JPH0526229B2 JP63501201A JP50120187A JPH0526229B2 JP H0526229 B2 JPH0526229 B2 JP H0526229B2 JP 63501201 A JP63501201 A JP 63501201A JP 50120187 A JP50120187 A JP 50120187A JP H0526229 B2 JPH0526229 B2 JP H0526229B2
- Authority
- JP
- Japan
- Prior art keywords
- matrix
- dct
- bit
- data
- dimensional
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/008—Vector quantisation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
- G06F17/147—Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/007—Transform coding, e.g. discrete cosine transform
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Mathematical Optimization (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Discrete Mathematics (AREA)
- Multimedia (AREA)
- Pure & Applied Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Description
請求の範囲
１ 入力データマトリツクスを列ごとに一次元変
換の計算を行つて一次元Ｎ×Ｎ中間変換マトリツ
クスを形成する第１のＮ×１ DCTプロセツサ
と、 前記中間変換マトリツクスを記憶するＮ×Ｎ転
位メモリと、 前記転位メモリの中に記憶された前記中間変換
マトリツクスの転移の一次元変換を計算して所望
の２次元DCTを得る第２のＮ×１ DCTプロセ
ツサと、 を有しており、前記両Ｎ×１ DCTプロセツサ
は、 前記入力データのマトリツクスの列、又は前記
記憶中間変換マトリツクスの行又は列がビツト直
列の形式で印加される入力Ｎ段入力レジスタと、 前記入力レジスタの対応段に接続された段と、
前記入力レジスタの内容をビツト並列形式で前記
入力レジスタが一杯になつた度ごとにホールデイ
ングレジスタにトランスフアする装置とを有する
前記Ｎ段ホールデイングレジスタと、 前記ホールデイングレジスタに接続され、Ｎ個
のベクトル内積を同時に計算する装置であつて、
前記装置は前記ホールデイングレジスタに接続さ
れて第１段デシメーシヨン−イン−フレクエンシ
ーを実行して前記ホールデイングレジスタから受
取つたＮビツトワードから一対のＮ／２ビツトワ
ードを作出す回路装置を有する装置と、 前記回路装置に接続されたＮ個のRACであつ
て、前記各RACは１又はそれ以上のリードオン
リーメモリ（ROM）と累算器とを有し、前記各
RACは一方又は他方の前記Ｎ／２ビツトワード
によつてアドレスされるＮ個のRACと、 前記RACの夫々対応する対応累算器に接続さ
れたその夫々の段を有するＮ段出力レジスタと、
更に、 前記Ｎ個の計算済みベクトル内積を前記出力レ
ジスタに同時にトランスフアする装置と、 を有する、 一対の一次元DCTプロセツサを使用して行−
列デコンポジシヨン法で入力データのＮ×Ｎマト
リツクスの２次元DCTを作出す２次元離散余弦
変換（DCT）プロセツサ。 ２ 前記RACは夫々部分和特性（又は装置）を
有し、前記各RACは前記回路装置から受取つた
前記Ｎ／２ビツトワードの一法又は他方の相違す
る部分によつてアドレスされ、前記各RACは更
に前記２又はそれ以上のROMから検索したワー
ドを加算する装置とこれによつて出来た加算され
たワードをRACに付設された累算器に加える装
置とを有する、特許請求の範囲第１項に記載の２
次元DCT。 ３ 前記入力データマトリツクスの一次元変換を
一時に一列ごとに計算して一次元中間変換マトリ
ツクスを作出す第１のＮ×１ DCTプロセツサ
と、 前記中間変換マトリツクスを記憶するＮ×Ｎ転
位メモリと、更に、 前記転位メモリ内に記憶された前記中間変換マ
トリツクスの転位の一次元変換を計算して所望の
２次元DCTを得る為の第２のＮ×１ DCTプロ
セツサとを有して成り、 前記両Ｎ×１ DCTプロセツサは、 入力データの前記マトリツクスの列又は前記記
憶中間変換マトリツクスの行又は列がビツト直列
形式で加えられるＮ段入力レジスタと、 前記入力レジスタの対応段に接続された段と、
前記入力レジスタの内容をビツト並列形式で前記
入力レジスタが一杯になつた度ごとに前記ホール
デイングレジスタに引渡す装置とを有するＮ段ホ
ールデイングレジスタと、 Ｎ個のベクトル内積を同時に計算する、前記ホ
ールデイングレジスタに接続された分布アリスマ
テイツク回路装置であつて、前記分布アリスマテ
イツク回路装置は、前記ホールデイングレジスタ
の出力に接続された第１段デシメーシヨン−イン
−フレクエンシー回路装置を有し、前記デシメー
シヨン−イン−フレクエンシー回路装置は前記ホ
ールデイングレジスタから受取つた各Ｎビツトワ
ードから一対のＮ／２ビツトワードを作出す装置
を有する分布アリスマテイツク回路装置と、 前記分布アリスマテイツク回路装置は更に、
夫々が１乃至数個のROMプラス累算器を有し、
前記RACは前記デシメーシヨン−イン−フレク
エンシー回路装置の出力に接続されており、更
に、 その各々の段が前記RACの対応累算器に接続
され、前記累算器からビツト並列で前記ベクトル
内積を受取る装置と、前記内積をビツト直列にシ
フトアウトする装置とを有するＮ段出力レジスタ
と、 を有する、一対の一次元DCTプロセツサを有し、
行−列デコンポジシヨン法によつて入力データの
Ｎ×Ｎマトリツクスの２次元DCTを作出す２次
元離散余弦変換（DCT）プロセツサ。 ４ Ｎ＝16であり、前記入力データマトリツクス
は８ビツト２進ワードでエンコードされたビデオ
ピクセルであり、前記回路装置は単一チツプに造
り上げられている、特許請求の範囲第３項に記載
のプロセツサ。 ５ 入力データの列又は行がビツト直列形式で加
えられるＮ段入力レジスタと、 その各段が前記入力レジスタの対応各段に接続
された各段と、前記入力レジスタが一杯になつた
度毎に前記入力レジスタの内容をビツト並列の形
式で前記ホールデイングレジスタにトランスフア
する装置とを有するＮ段ホールデイングレジスタ
と、 Ｎ個のベクトル内積を同時に計算する、前記ホ
ールデイングレジスタに接続された分布アリスマ
テイツク回路装置であつて、前記分布アリスマテ
イツク回路装置は、前記ホールデイングレジスタ
の出力に接続された第１段デシメーシヨン−イン
−フレクエンシー回路装置を有し、前記デシメー
シヨン−イン−フレクエンシー回路装置は前記ホ
ールデイングレジスタから受取つた各Ｎビツトワ
ードから一対のＮ／２ビツトワードを作出す装置
を有する分布アリスマテイツク回路装置と、 前記分布アリスマテイツク回路装置は更に、
夫々が１乃至数個のROMプラス累算器を有する
Ｎ個のRACを有し、前記RACは前記デシメーシ
ヨン−イン−フレクエンシー回路装置の出力に接
続されており、更に、 前記夫々のRACの対応する累算器に接続され
た段を有する出力レジスタであつて、前記出力レ
ジスタはビツト並列方式で前記累算器からの前記
ベクトル内積を受取る装置と、前記内積をビツト
直列形式にシフトアウトする装置とを有する出力
レジスタと、 を有するＮ×１離散余弦変換（DCT）プロセツ
サ。 ６ 前記RACは夫々部分和特性を有し、前記
RACは２又はそれ以上のROMを有し、その夫々
が前記デシメーシヨン−イン−フレクエンシー回
路装置から受取つた前記Ｎ／２ビツトワードの一
方又は他方の別々の部分でアドレスされ、前記
RACは夫々更に前記Ｎ／２ビツトワードの前記
別々の部分で前記２又はそれ以上のROMから検
索されたワードを加える装置と、これによつて作
られた加算されたワードを前記RACに対応する
累算器に印加する装置とを有する、特許請求の範
囲第５項に記載のDCTプロセツサ。 ７ 入力データのＮ×Ｎマトリツクスの２次元
DCTを作り出す２次元離散余弦変換プロセツサ
において、 第１および第２のＮ×１ DCTプロセツサと
Ｎ×Ｎ転位メモリと、 入力データの該Ｎ×Ｎマトリツクスの転位を前
記第１のDCTプロセツサに加えることにより、
中間Ｎ×Ｎマトリツクスを計算する装置と、 該中間マトリツクスを該転位メモリ内に記憶す
る装置と、 前記記憶された中間マトリツクスの転位を前記
第２のＮ×１ DCTプロセツサに読み出すこと
により入力データの前記マトリツクスの２次元
DCTを計算する装置とを有し、 前記Ｎ×１ DCTプロセツサは夫々第１段デ
シメーシヨン−イン−フレクエンシーおよび部分
和により分布アリスマテイツクを行う回路装置に
よつてＮ個のベクトル内積を同時に計算する手段
を有し、 前記転位メモリは別々の読取り書込み端子およ
びこれに接続された読取り書込み制御回路付きＮ
×Ｎランダム・アクセス・メモリ（RAM）アレ
イを有し、記憶されたマトリツクスの転位が前記
第２のＮ×１ DCTプロセツサへの印加のため
に行われるように、前記第１のDCTプロセツサ
の出力が行方向と列方向に交互に読み取られ、前
記第２のDCTプロセツサの入力が行方向と列方
向に交互に読み出される、２次元離散余弦変換プ
ロセツサ。 発明の分野 本発明は空間ドメイン信号、例えばビデオ信号
を離散余弦変換（DCT）として周知の数学的手
順で周波数ドメイン信号に変換するプロセツサに
関する。 発明の背景 DCTはイメージ圧縮即ちビデオ帯域幅圧縮に
関して各種の変換コーデイング法の中で最も効果
的な技術と考えられている。DCTは離散フーリ
エ変換（DFT）に類似してはいるが、余弦項の
みを有する。この方法で帯域幅圧縮を実行する事
によつて、デジタルにエンコードされた画像素子
即ちピクセルの正方形ブロツクが、Ｎ×Ｎブロツ
クのピクセルデータが印加される２次元（Ｎ×
Ｎ）DCTプロセツサによつて周波数ドメインに
変換される事が出来るが、その際入力データマト
リツクスはＮ×Ｎ離散余弦マトリツクスに乗算さ
れて中間マトリツクスが作られ、中間マトリツク
スの転位が同一離散余弦マトリツクスに乗算され
て所望の２次元変換マトリツクスを得る。変換さ
れたマトリツクスの各要素は量子化する事が出
来、その中で最もエネルギーの大きいもののみが
伝送の必要がある。受信機においては、空間ドメ
インの最初のビデオ信号を再構成する為に逆の変
換が行われる。Ｎ×Ｎ DCTにおいては、Ｎが
大きい程圧縮比が大きくなるが、計算が大変にな
る。 マトリツクス乗算は２個のＮ×１ベクトルの内
積を計算して積のマトリツクスの単一要素を得
る。即ち、入力マトリツクスの列の各要素は余弦
マトリツクスの行の各対応要素と乗算されて、積
は加算されて積のマトリツクスの単一要素を得
る。即ち、16×16ブロツクのピクセルの変換に対
しては、16の積が、夫々が256要素を有する中間
及び変換マトリツクスの単一要素又は係数を得る
為に加算されねばならない。多数の高速アルゴリ
ズムが必要とする計算の数を減少する為に誘導さ
れた。例えば、DCTマトリツクスが若干数のス
パース（sparse）マトリツクスに分解されたが、
その結果バタフライ構造となつた。これらのバタ
フライ構造は計算を相当に減少させはするが、し
かし尚集積回路の為に大面積のシリコンを必要と
する多数の高速乗算器が必要で、これは繁雑な内
部配線、チツプ内の悪い接続配線、不規則な形
状、と言う結果を生む。DCTは使用しないがア
ダマール及びハール（Hadamard and Haar）
変換を使用するマトリツクスデコンポジシヨン技
術（matrix−decomposition technique）がフイ
リツプス テクニカル レビユー第38巻第４号／
第５号、1978／79年第119−130頁に、「カラーテ
レビジヨン画像のリアルタイム直交変換」、の題
名で記載されている。ここに説明の方式において
は、変換に必要とされる加算及び減算は、その中
の第１０図及び第１１図に記載されている高速ア
ルゴリズムによつて並列に実行されている。 これらの全ての要因はバタフライ構造のVLSI
（大規模集積）装置を非常に非能率なものにして
しまう。この種の構造を使用するDCTのVLSI装
置の例としては、JEEE Journal on Selected
Areas in Communication 1986年１月第49−61
頁記載の「離散フーリエ余弦変換チツプ」に記載
されている。その中の第１７図に示す出来上りチ
ツプは多数の乗算器を有し、シリコン表面を能率
的に使用してはおらず、８×１一次元変換が行い
得るのみである。２次元変換は２つの一次元変換
を含み、中間の計算結果の一時的な記憶及びマト
リツクス転位が必要であり、従つてこれは一次元
変換に比較して非常に複雑になる。又、IEEE
Transactions on Computers、第Ｃ−32巻第12
号、1983年第1128−1136頁に記載の、「パイプラ
イン化分布アリスメテイツクPFFTプロセツサ」
には、プライムフアクタフーリエ変換（Prime
Facter Fourier Transform−PFFT）が記載さ
れているが、これは離散フーリエ変換を比較的短
いプライム長さの変換（relatively short prime
length transform）の組に分解する事を含んで
おり、上述した形式に類似したマトリツクス分解
技術である。PFFTの実行にはROMに記憶され
たルツクアツプテーブルを含む分布アリスメテイ
ツクを利用している。ROMに記憶されているル
ツクアツプテーブルにデータを供給する入力回路
装置はコーナーターニング（corner turning）回
路と、一対のRAMのワード選択カウンタと、
「パイプラインラツチ」（”pipeline latch）とを
含んでいる。エキストラの小型ROMと加算器と
を加えてROMのサイズを減少させる技術も又、
その第８図に公開されている。 本発明は現在の技術状態におけるVLSI技術を
効果的に使用できる２次元DCTのリアルタイム
処理に対する必要性に応えるものである。本発明
は単一チツプ上の16×16DCTのリアルタイム処
理を提供するものである。これは、ビデオカメラ
によつて16×16入力マトリツクスが作られるのと
同じ割合で量子化装置に印加する変換16×16マト
リツクスをプロセツサから作らねばならぬ事を意
味する。プロセツサは現在のMOS技術によるデ
イジタルビデオシステムで通常使用される定格で
ある14.3MHzの入力サンプル又はピクセルレイト
を取扱う事が可能であるべきである。必要とする
大量の計算の為に、この定格でのリアルタイム処
理は、装置内での固有な同時性と並列性とを開発
する事によつてのみ達成可能である。 発明の要約 高速アルゴリズムをシリコンの中にマツピング
する代りに、本発明においては、ベクトル内積を
同時に得る為及びROM寸法を最小限度にするた
めデシメーシヨン−イン−フレクエンシー
（decimation−in−frequency）と組合わせた分
布アリスメテイツク（distributed arithmetic）
と、ビツト直列（bit−serial）とビツト並列
（bit−parallel）データ構造と、部分和とを使用
する。新しい入出力装置と能率的なマトリツクス
転位回路が考案された。その結果は非常に規則正
しい構造で乗算器の無い構成体即ち回路装置であ
る。変換演算の固有の性質、即ち、(1)変換マトリ
ツクス係数が定数でその為分布アリスメテイツク
の使用が可能であるが、その中で乗算器をメモリ
ルツクアツプテーブル又はROMで置換えが可能
であること、又、(2)マトリツクスベクトル積が若
干数の同時ベクトル内積によつて実現される事の
為にこれが可能となる。デシメーシヨン−イン−
フレクエンシーと部分和は必要とするルツクアツ
プテーブルのサイズを減少させるのに利用され
る。ビツト直列構造はデシメーシヨン−イン−フ
レクエンシーの実施に使用されるがその為シリコ
ンの面積は非常に小さく内部配線（routing）は
非常に単純化された。その結果はメモリと、加算
器と、レジスタのみから構成される２次元DCT
プロセツサであり、乗算器は必要ではない。回路
回りの高度な同時的操作の規則性はモジユール設
計を可能とするが、これはVLSI実現に対する理
想的な特徴である。又、この構成体はビツト直列
とビツト並列回路装置を最大限に組合わせてあ
る。この新規な構造体は他の２次元線形演算にも
応用可能である。 本発明による２次元DCTプロセツサは、Ｎ×
Ｎ入力データブロツクが列ごとに順番に印加され
る一次元（Ｎ×１）列DCTプロセツサを有する。
入力装置即ち列プロセツサは入力データの列変換
を、必要とされるROMの量を低下させる為にデ
シメーシヨン−イン−フレクエンシーの加算特性
と部分和を有する分布アリスメチツクスを使用す
る回路によつて行う様に設計されている。入力用
Ｎ×１プロセツサがＮ回路設けられておりその
夫々がリードオンリーメモリー（ROM）とカス
ケード接続された累算機とを有し、RACと呼ば
れている。この累算機はROMから引出されたデ
ータをシフトの上加算して列転位の要素を同時に
計算する。結果の中間ベクトルはRAMから成る
Ｎ×Ｎ転位メモリの一行に記憶される。データマ
トリツクスの各列は入力用Ｎ×１プロセツサーに
順次加えられてＮ×Ｎ中間マトリツクス(Y)を作る
が、これはデータマトリツクスの転位（Xt）と
ROMに記憶された定数で表示された離散余弦と
マトリツクス(C)との積（XtＣ）である。上記信
号ｔはマトリツクスの転位を示す。第２の出力行
Ｎ×1DCTプロセツサが次に使用されてXtＣの各
列用の一次元Ｎ×1DCTを計算するのに使用され
るが、これはメモリー内の記憶から引出される。
この第２の行変換操作結果は従つてCtXCを得る
事となるが、これが所望の２次元Ｎ×Ｎ DCT
である。プロセツサには制御回路が設けられる
が、これはクロツクその他の制御信号を作り、上
記の各部品の操作を制御する。 入力Ｎ×１ DCTプロセツサはn1本の並列線
路によつて順番に入力データが加えられるＮ段の
入力レジスタを有するが、ここでn1は入力データ
のワード又はピクセル当りのビツト数である。入
力レジスタがデータ列で一杯になると直ちに、列
の全部はビツト並列形式でホールデイングレジス
タに同時にシフトされ、そして入力レジスタは次
のデータ列の収集を開始する。ホールデイングレ
ジスタのＮ段の夫々のデータは、最下位ビツトを
先頭にして一時に１ビツト、同時にシフトアウト
される。この様にして形成されたＮ−ビツトのワ
ードは、これはいわゆる第１段デシメーシヨン−
イン−フレクエンシー（decimation−in−
frequency）技術の一部として２個のＮ／２ビツ
トワードに変換され、出来たＮ／２ビツトのワー
ドはRACのすべてのROMのアドレスに同時に使
用される。第１段デシメーシヨン（decimation）
は符号なしのn1個の入力データを（n1＋２）ビツ
トの２の補数に変換するので、同一操作はn1＋２
回繰返されて各のROMから読み出されたn1＋２
ワードはハードワイアド（hard−wired）１ビツ
ト右シフトを有するシフトレジスタを有する累算
機の内容に順次加算される。データワードの一部
である符号ビツトにより加算ではなく減算が行わ
れる。各列の入力データがプロセスされた後のこ
れらのRACの夫々の累算出力は列変換の要素で
ある単一係数から成る。RACの全ての内容がＮ
段出力レジスタへ同時にビツト並列の形でトラン
スフアされ、その後、その内容はn2並列線の変換
メモリの一行（又は一列）に順次シフトされる。
Ｎ×Ｎメモリがこの要領で一杯になると、第２即
ち出力Ｎ×１列DCTプロセツサーが列ごとに
（又は行ごとに）RAMメモリ中に記憶されたマ
トリツクスを読み出して、これによつてXtＣの
変換が得られる。第2N×１ DCTは第１即ち入
力プロセツサが行つたのと同様な要領で所望のＮ
×２次元DCTを発生する。両方のＮ×１プロセ
ツサは、第2N×１プロセツサのデータを表示す
るのに多数のビツトを必要とすることを除けば、
同様な回路で構成し得る。 この新規な２次元Ｎ×Ｎプロセツサは第1N×
１プロセツサを有するが、これには最初のマトリ
ツクスを列ごとに読み出して入力データのＮ×Ｎ
ブロツクの転位が印加され、この第1N×１プロ
セツサは分布アリスマテイツクを使用して前記入
力データの各列のＮベクトル内積を同時に計算す
る装置を有するが、ここでＮ×Ｎ離散余弦マトリ
ツクスはＮ個のRACに記憶され、この夫々は
ROMと累算機から成り、このROMは入力デー
タの前記列のデータワードから誘導されたＮ／２
ビツトワードによつてアドレスされる。この要領
でROMから検索されたワーズはシフト及び加算
操作によつてシフトレジスタに累算され、Ｎ個の
RACの各々の出力は、入力データブロツクのＮ
×１変換を有するＮ×Ｎ中間マトリツクスの一行
（又は一列）の各要素又は係数を有する。Ｎ×Ｎ
RAMアレーに中間マトリツクスを記憶し、そ
の転位を第2N×１ DCTプロセツサに読み出す
回路が設けられるが、この第２プロセツサは所望
の２次元Ｎ×Ｎ DCTを、前記中間Ｎ×Ｎマト
リツクスを発生するのに使用したものと類似の回
路によつて発生する。適当な制御回路が所要の制
御信号を発生する為に設置される。 従つて、リアルタイムベースで２進化コードビ
デオデータの16×16ブロツクの変換を発生する事
の出来る２次元DCTプロセツサを提供する事が
本発明の目的であるが、この場合、前記プロセツ
サの構造体、回路、及びアルゴリズムは実現の容
易性からして現在状態でのVLSI技術が選定され、
これが単一CMOSチツプの上に実現される事を
目的とするものである。 本発明の別の目的は入力データマトリツクスか
らのデータ列（又は行）を瞬時に処理して、入力
データの列（又は行）と、プロセツサ内のＮ
RACに記憶されている離散余弦マトリツクスの
Ｎ列とのベクトル内積を有する要素の行を形成す
る一次元Ｎ×１ DCTプロセツサを提供する事
であり、ここで、このＮ×１プロセツサはベクト
ル内積を計算するのに分布アリスマテイツクと、
第１段デシメーシヨン−イン−フレクエンシー
と、部分和とを利用しており、このプロセツサは
レジスタと、小容量のメモリと、加算器とのみを
有するものである。 本発明の更に別の目的は、入力データの列と
RACの中に記憶されている離散余弦マトリツク
スのベクトル内積を構成する複数の要素を効果的
に、瞬時に計算する為に、分布アリスマテイツク
と、RACsと、デシメーシヨン−イン−フレクエ
ンシーと、部分和とを使用する回路を有する一次
元DCTで構成された２次元DCTを提供する事で
あるが、この際、入力データの列は順次に処理さ
れてRAMアレーに記憶される中間Ｎ×Ｎマトリ
ツクスを発生し、次に中間マトリツクスの転位
が、所望の２次元Ｎ×Ｎ DCTを同様に発生す
る類似の一次元DCTプロセツサに読み出される
ものである。 本発明の別の目的は、プロセツサの構造体、回
路、及びアルゴリズムが、構造物乃至回路が少な
く、且つ制御が簡単で、高速で、複雑な計算を達
成する様に選定された、16×16ビデオピクセルの
ブロツクのリアルタイム処理可能の16×16 ２次
元DCTを提供する事である。選定された構造と
回路とは、乗算器を使用する事なしに小容量の
ROMを使用して若干数のベクトル内積の瞬時
（又は同時）計算を可能とし、又、ビツト直列及
びビツト並列フオーマツトが組合わせて使用され
て、シリコンチツプ面積を減少させ、回路内配線
の簡単化を図り、ビデオ信号のリアルタイム処理
を行うために高速操作を可能とするものである。 【図面の簡単な説明】 第１図は本発明を単一チツプに実現した時に必
要な接続を示す。 第２図は本発明の一実施例の全体のブロツク図
を示す。 第３図は分布アリスマテイツクその他の特徴を
使用するDCTプロセツサを示す。 第４図はRACのブロツク図である。 第５図はデシメーシヨン−イン−フレクエンシ
ーを使用するDCTプロセツサのブロツク図であ
る。 第６図は部分和を使用しないRACの回路図で
ある。第７図と第８図とは部分和を使用する
RACの回路図である。 第９図は第２図のＮ×１ DCTの完成回路図
である。 詳細な説明 離散余弦変換（DCT）は、余弦関数によつて
サンプリングされた基礎ベクトルの組から成る直
交変換である。Ｎ式のDCT変換マトリツクス、
Ｃ、は次の式で示される、 ここに、ｋ＝１、２、３、…ｌ＝１、２、３、
…、又、ｌ＝１に対して、Ck、l＝N-1/2である。
DCTによつて帯域幅圧縮を行う為には、符号無
しの２進コード化ピクセルの形のＮ×Ｎビデオデ
ータのブロツクは２次元変換を行わねばならな
い。Ｎ次の２次元DCTは、 Ｙ＝CtXC (2) ここに、Ｙは変換されたマトリツクス、Ｘはデ
ータ即ちビデオピクセルマトリツクス、Ctは式(1)
で定義された離散余弦マトリツクス、Ｃの転位で
ある。 ２次元Ｎ×Ｎ DCTの実行は行−列デコンポ
ジシヨン技術と称される公知技術によつてなされ
るが、その詳細は1984年刊行のプレンテイスホー
ル信号処理シリーズのダツジオン、マーサロー
（Dudgeon ＆ Mersareau）共著の著書“多次
元デジタル信号処理”を参照されたい。この公知
技術において、２次元DCTは２つの逐次型一次
元DCTによつてなされるが、データマトリツク
スは第１の一次元DCTに行ごとに印加される。
本発明においては、この技術の変形が使用された
が、ここでは、上述の様に、データマトリツクス
の転位が行われるように、行ごとにではなく列ご
とに読み出す事によつてデータマトリツクスの転
位がなされて、これが第１の一次元DCTプロセ
ツサに加えられる。これは回路の簡単化をもたら
す。従つて本発明においては、第１の一次元Ｎ×
１ DCTプロセツサの出力はXtＣであり、これ
は一時的に転位メモリに記憶され、次に別のＮ×
１ DCTが記憶されたマトリツクスの転位から
計算されて所望の式(2)の２次元DCT(Y)を得る。
速度が重要ではない場合には、２つのＮ×1DCT
計算は同一回路で時分割処理する事も出来るが、
リアルタイム操作が必要な現在の場合には２個の
Ｎ×１プロセツサを使用する。 第１図は単一チツプ上に実施した本発明を示す
図である。このチツプへの接続はバイアス電圧
Vcc、接地、サンプルクロツク、及びブロツクの
始動（Start−of−Block）ストローブを有する。
入力データはn1本の並列線を介して並列に、ピク
セルワードの各ビツト毎に印加される。変換出力
データは長い変換ワードに対してはn3並列線で構
成されよう。入出力データは同一クロツクレート
で連続的にチツプにシフトして出し入れされる。 第２図は、n1本の並列線で入力データが印加さ
れる第１の列Ｎ×１ DCT、３、を有し、DCT
３の出力は一時的に、行又は列状にＮ×Ｎ変換メ
モリ５に記憶されるが、これは図示の通り別々の
入出力端を有するランダムアクセスメモリ
（RAM）を有する。DCT３からメモリ５へのn2
本の並列線は、必要とされる精度によつて変化は
するが、通常は入力データよりもビツト数が大き
くなる。記憶されたマトリツクスは列又は行ごと
に（中間マトリツクスの記憶の仕方に応じて）n2
本の並列線を介して第２の行Ｎ×1DCT７に印加
される。即ち、記憶マトリツクスの転位が読み出
される。変換出力データはＮ×１ DCTプロセ
ツサからn3本の並列線を介して得られる。タイミ
ング及び制御回路９はクロツク信号と、外部回路
からこれに印加されたブロツクの始動ストローブ
とを有し、また、回路９は若干のタイミング及び
制御信号１１及び１２をプロセツシング回路に供
給している。読取り／書込みアドレス及び制御回
路１６は回路９から制御信号１２を受取り、線１
４を介して適当な読取り／書込みアドレスその他
の制御信号をメモリ５に加える。 前述のベクトル内積は夫々Ｎ個の積の和を有す
る。この計算はROMから成るルツクアツプテー
ブルを使用して乗算なしで出来る事は数学的に証
明する事も出来るが、この場合、変換されたマト
リツクスの必要とする係数はROMから得たルツ
クアツプテーブル値のシフトと加算によつて得ら
れる。これも又当業者に取つて公知の計算技術で
あるが分布アリスマテイツクとも称されている。
シフトと加算が行われるROMと累算機とはRAC
と称するユニツトを形成し、各RACは離散余弦
マトリツクスの各列を表示する定数を記憶する。 第３図と第４図とは、分布アリスマテイツクが
いかに機能するかと言う事、及び本発明に使用さ
れた若干の回路の特徴を示すものである。第３図
において、入力レジスタ１３はＮ段Q1−Qoを有
する。各ピクセル列又はその他の２次元データ、
X1k…XNKは１／Ｔのデータ又はクロツクレート
でビツト並列形式でレジスタ１３の段Ｑ１に印加
される。ピクセルデータマトリツクスを列ごとに
読む事によつて、その変換が完成する。ビデオデ
イジタルピクセルデータは通常ピクセルの輝度を
表示する８ビツト無符号ワードにエンコードされ
ている。即ちデータ入力はQ1に８（又はn1）並列
線で印加され、各レジスタ段Q1−QNは並列８（又
はn1）ビツトで構成される。Ｎクロツクサイクル
の後、列はレジスタ１３のＮ段に完全に負荷され
る。この時第２図の回路９からの制御信号１１ａ
と１１ｂとが全部の８（又はn1）ビツトワーズを
並列にQ1−QNからホールデイングレジスタ１５
の対応段R1−RNにトランスフアする。入力デー
タの次の列が入力レジスタ１３への入力開始を始
めるが、その時回路の残りはホールデイングレジ
スタ内のデータの一次元変換を得る為にＮベクト
ル内積計算を平行して行う。この同時計算を行う
事によつてホールデイングレジスタ内のデータは
１ビツトずつ下の桁の数字を先頭にして制御信号
１１ｃに応じてシフトアウトされる。レジスタ１
５のＮ段からのＮラインはＮ−ビツトバスを形成
するが、そのすべての線にはＮ個の別々のRAC
（RAC(1)−RAC(N)）が印加される。即ち、各ク
ロツクサイクル毎に相違するＮ−ビツトワード
が、各RACの部品であるROMの同時アドレスに
使用される。RAC（１）はそのROMにマトリツ
クスＣの第１列の係数の可能な組み合わせを表示
する2N個の定数を有する。例えば、第１列係数が
c1、1、c2、1、c3、1…cN,1、だつたりするとROMは
これらの係数を個々に、又は可能な全ての和、即
ち、c1、1＋c2、1、c1、1＋c3、1、c1、1＋cN,1、c1、1
′＋
c2、1＋c3、1′など、これらの列係数の全ての和を含
むまでの全てを尽す事となる。例えば、Ｎ＝４に
対して列変換の各要素、yk,lの計算は次の様に表
示される。即ち、c1、1（110101001）＋c2、1
（00101010）＋c3、1（1100111）＋c4、1（10101110）
、
ここで８ビツトワードはデータの列を構成する各
データピクセルを表す。この例において全てのデ
ータワーズの最も下の桁のビツトはワード1010を
形成する。このワードはRAC(1)のROMから記憶
値c1、1＋c3、1を検索するが、これは第４図に示す
様にRAC(1)のシフトレジスタ２５に加えられる。
次のクロツクサイクルにおいて、全てのデータワ
ードの次に下の桁のデジツトが全てのRACに加
えられてどのRACがアドレスされたか、及びＮ
デジツトワードが何であつたかに応じてこれから
各種の値を検索する。この検索されたワードは又
第４図の加算／減算回路２３を介してシフトレジ
スタに加えられるが、ここで加算／減算回路にフ
イードバツクされるシフトレジスタの前の内容は
１ビツトの右シフトされたデータが加えられる。
即ち、ROM２１の第２アドレシングの後、シフ
トレジスタ２５はその中にレスシグニフイカンス
なデータワードのビツトを表示すると言う事実を
反映して最初のワードに1/2の重みを付け（又は
２で割る）をしたデータと次のデータとの２検索
ワードの和を記憶する事となる。このプロセスは
データワードの各ビツトに対して繰返される。加
算／減算回路２３は正規データビツトに対して加
算を行い、符号ビツトに対しては減算を行う。
ROMからのこれらの検索の上重みを付けられた
全てのワードの最終加算は積マトリツクスの係数
の一つ又は一次元変換の一係数に等しい。例え
ば、積マトリツクスXtＣの要素がyk,lである場合、
この要領で第１列の入力データを処理した後の
RAC(1)の出力はy1、1で、同様にRAC(N)の出力は
y1,Nとなろう。即ち、積マトリツクスXtＣの第１
行の全体はこの計算の完成後RAC出力で得られ
る。回路９からの制御信号１１ｄに応じて、各
RACの累算された内容物、yk,1−yK,N、は出力レ
ジスタ１９の段、U1−UNにn2（又はn3）並列線を
介して並列して同時に負荷されるが、これはエキ
ストラ２入力マルチプレクサ付の入力レジスタに
類似している。レジスタ１９の内容は次に順次そ
の段U1かn2（又はn3）並列線を介して転位メモリ
又は２次元プロセツサ出力に制御信号１１ｅに応
動してシフトされる。例えば、Ｎ＝16の場合、デ
ータの１列を入力レジスタ１３に負荷するのに16
クロツクサイクルを要し、従つて16サイクル毎に
制御回路９はホールデイングレジスタ１５へのデ
ータ列のトランスフアを行うのに信号１１ｂを提
供する事が必要である。レジスタ１９はその内容
物yk,lを順番にシフトウト可能であるが、その間
RACは積のマトリツクスの次の行の計算を行い、
入力レジスタは入力データを集めている。第４図
に示すように、ROM２１の出力はワードレング
スn4ビツトを有するが、これはROMの中に記憶
されたワードの長さによつて決定される。回路９
から回路２３に加えられた信号１１ｆは、この回
路が加算用か減算用かを決定する。シフトレジス
タ２５に加えられた制御信号１１ｇ及び１１ｈは
リセツト及び並列負荷信号である。 一次元DCTプロセツサの両方の回路装置はワ
ード当りのビツト数を除けば同一である。第２図
に示すように、第１プロセツサは入力ワード長さ
n1と出力ワード長さn2とを有する。第２のDCT
プロセツサ７は入出力ワード長さn2とn3とを夫々
有する。 第３図及び第４図の回路は乗算器を必要としな
いが、これはこれに付属する各ROMに記憶させ
るべき定数の数の為に重大な制限を受ける。例え
ば、今Ｎ＝16とすると、各RACの各ROMに要求
されるワード数は２の16乗即ち65536個である。
このサイズのROMは、全プロセツサを単一チツ
プに収めようとすると現在のVLSI技術では実現
できない。ROMのサイズを減少させる為に２つ
のアプローチがなされたが、これらは共に僅かな
付加回路を要するのみである。第１のアプローチ
はデシメーシヨン−イン−フレクエンシー技術の
翻案であるが、上記技術は従来の高速フーリエ変
換（FFT）アルゴリズムで従来技術として使用
されているものである。積マトリツクスＹ＝Xt
Ｃの（ｋ、ｌ）番目の要素は、 Yk,l＝ｘ t k・ｃ l＝ｉN 〓m=1 xn,k、cn,l (3) ここに、ｘ kはＸのｋ番目の列ベクトルであり、
又、ｃ lはＣの１番目の列ベクトルである。式(1)
で定義されたＮ×Ｎ DCT変換マトリツクスＣ
を参照すると、偶数のＮに対して、ｌ＝１、３、
…Ｎ−１において、ck,l＋cN+1-k,lであり、１＝２、
４、…Ｎに対してck,l＝−cN+1-k,lである事を示す
事が出来る。これらの関係から式(3)は次の様にな
る、 Yk,l＝N/2 〓m=1 uk,ncm、ｌ (4) ｌ＝１、３、…Ｎ−１に対しては uk,n＝xn,R、＋xN-n+1,k′なので、 Yk、ｌ＝N/2 〓m=1 vkncm、ｌ (5) ｌ＝２、４、…Ｎに対しては Vk,n＝xn,k -XＮ−ｍ＋１、k′となる。式(4)と(5)
とは、変数ｕとｖとが最初のデータシークエンス
ｘと置換された場合、１からＮまでの和は１から
Ｎ／２までの和になる事を意味する。即ち、各
ROMにアドレスすべきデータビツト数は２分の
１に減少され、必要とする記憶すべきワード数は
２のＮ／２乗で減少する。原則的には、このデシ
メーシヨン−イン−フレクエンシー技術は、殆ど
のFFTアルゴリズムが行つているようにこの上
の段階にまで展開可能である。しかし、この節約
は、不規則性が増大するので実施の価値に値しな
い。即ち、モジユール構造を残す為に、第１段の
デシメーシヨンのみを適用した。発明のこの特徴
を第５図の回路で示す。 第５図において、Ｎ／２シリアル加算器３１は
レジスタ１５からの最初のデータシークエンスの
Ｎ／２個の相違する対から変数ｕを作る為に設け
られている。図示の通り、変数uk,1はx1,kとxN,k′の
和から、uk,2はx2,k、プラスxN-1,k′から、又，uk,N/2
はxN/2,kプラスxN/2+1,k′によつて得られる。入力デ
ータ要素の同一の対がＮ／２一ビツトシリアル減
算機３３で相互に減算されて新変換vk,lvk,2…vk,N/2
を作る。即ち、入力データの各列のデータ要素の
対は列の最初の及び最後の行の要素から、第２の
及び最後から一つ手前の要素から、第３の及び最
後の要素から３番目の要素から、などで構成され
る。第５図の入力データビツトxk、lは一時に１
ビツトの割合で（ビツト直列形式で）第３図のそ
れと類似のホールデイングレジスタから得られ、
シリアル加算器３１と減算器３３の出力は一時に
１ビツトずつ現れて２個のＮ／２ラインバスを形
成するがこの各バスはＮ／２個のRACの２個の
別のグループの入力を構成してい。加算器３１に
付設されているＮ／２ラインバスはこれに接続さ
れた奇数個のRAC、１、３、Ｎ−１、を有し、
これらのRACは奇数列のベクトル内積の全ての
要素、即ち、yk,1、yk,3、yk,N-1を計算する。減算
回路３３に付設されたＮ／２ラインバス３６は偶
数個のRAC ２、４、Ｎ、を有し、ベクトル内積
の偶数列の要素を計算する。 第５図のそれの様な第１段デシメーシヨン回路
の使用は各ROMのサイズを16×16マトリツクス
に対して256ワードに減少させる、と言うのは各
RACがこの場合８ビツトワードでアドレスされ
るからである。 本発明はROMサイズを更に減少する為に付加
技術を使用する。この付加技術は、式(4)及び式(5)
のデータ点の数である指数ｍに関する和は部分和
に分割し得る、と言う観察に基ずくものである。
(3)を２つの部分和に分割しようとするならば、次
の通りである。N 〓m=1 xn,kcn,1＝F1（ｃ 1、ｘ k）＋F2（ｃ 1、ｘ 1） …(6) ここで、 Ｆ（Ci、xk）＝i N/2 〓+(i-1)N/2 xn,kcm、1′、ｉ＝１、２ F1とF2との和にはＮサンプルではなく、Ｎ／
２サンプルしか含まれていない事に注意された
い。この様にして分割する事によつて２のＮ乗ワ
ードのROMは２のＮ／２乗ワードに２個の小型
のROMに置換される。更に詳細に説明すると、
各RACの入力時のデータワードは２グループに
分割され、第１グループは１からＮ／２のビツト
から成り、第２グループはデータ数（Ｎ／２）＋
１からＮに至るものである。即ち、RACをアド
レスするのに普通使用されるワードはその前半及
び後半から成る２つの等しい部分に分割される。
夫々の短いワードは分割されたROMのアドレス
用に使用され、ROMの出力は並列に加算されて
和は累算器に印加される。この分割技術で使用さ
れる部分和の数は任意の偶数でよい。Ｎ＝16に対
して各ROMは２個の小型ROMに置換される。
Ｎ＝32の場合、各ROMは４個のROMに置換し
得るが、この場合加算を行う付加段が必要とな
る。Ｎ＝８に対しては、ROMのサイズが既に十
分に小さいので分割は必要としない。 部分和及び第１段デシメーシヨン−イン−フレ
クエンシー技術の両者に使用するRACの構造を
第６図、第７図、及び第８図に夫々８×１、16×
１、及び32×１用のものを示す。第５図のそれと
類似の第１段デシメーシヨン−イン−フレクエン
シー特性を有する８×１用の第６図のRACは、
ROMにアドレスする２個の４デジツトバスを含
んでいる。各ROM３７は２の４乗即ち16ワード
の記憶を行うのみで、従つて部分和の必要はな
く、ROM３７の出力は加算／減算回路３９とシ
フトレジスタ１１とを介して出力４３に加えられ
る。第７図の16×1DCT RACはデシメーシヨン
特性の為に２個の８ビツトバスを有するが、類似
した16ワードROM４５と４７に印加される２個
の４ビツトワードに、上述した様にして分割され
る。加算器４９は２つのROMから検索されたn4
ビツトワードを加算して単一のn4＋１ビツトワー
ドを作るが、これは加算／減算回路５１と、シフ
トレジスタ５３と、シフトレジスタの出力と加算
一減算器５１の間の１ビツト右シフトフイードバ
ツク回路とを有する累算器に印加される。５５に
おけるRAC出力はn2（又はn3）ビツトを有する
が、これはn4＋１ビツトよりも若干長い。 第８図のDCT RACは、夫々が16ワードを記
憶し得る４個の同様なROM、６１，６３，６５
及び６７にアドレスする４個の４ビツトワードに
分割される、16ビツトライン入力バスを含んであ
る。ROM６１と６３の出力でのn4ビツトワード
は加算器６９で加算され、又、ROM６５と６７
からの類似したワードは加算器７１に加えられ
る。これらの３個の加算器は加算器７３に加えら
れるそれらの出力端を有し、これは累算器に加え
られる出力端を有し、この累算器はベクトル内積
の要素の一つを計算する為に前述したものと同様
に作用する。 これら２技術を繰合わせる事によつて、若干の
回路装置が増大するものの、所要のROMサイズ
を小さくする事ができる。例えば、Ｎ＝16に対し
て、16×16 ２次元DCTの直接の実行には216×
16×２＝221ワードのROMを必要とする。反対
に、上述の２技術を使う事によつて第７図の回路
は24×２×16×２＝210、約1kワードのROM、を
必要とするのみとなる。このサイズのROMにお
いては、本発明の新規な回路装置が実現可能であ
るばかりでなく、ICの実現という見地からして
も非常に有効である。 第９図はデシメーシヨン−イン−フレクエンシ
ー特性を備えるＮ×１ DCTの完全ブロツク図
である。第９図のブロツク図はこの回路設計の規
則性と単位性とが強調されている。この図におい
て、入力レジスタはＮ段Q1−QNを有し、その
夫々がn1（又はn2）ビツトを有するが、これはこ
の回路が第２図の第１、第２プロセツサのどちら
に属するかによつて相違しており、データの入力
列、x1,k、x2,k、…xN,kはn1（又はn2）並列線のQ1
に加えられる。Ｎ／２直列加算器８１と同様な直
列減算器８３が設けられて、その夫々がこれに接
続されたホールデイングレジスタの各段R1−RN
からの一対の単線を有する。Ｎ／２ビツトバス８
５は加算器８１から誘導のビツトを有し、Ｎ／２
ビツトバス８７は減算器８３からのビツトを有す
る。Ｎ／２両ビツトバスの第１ビツト、uk,1及び
vk,1を発生する加算器と減算器は共に第１及び最
後のホールデイングレジスタ段R1とRNに接続さ
れていることに注意されたい。同様に、２つのバ
スにおける各ワードの第２ビツトを発生する加算
器と減算器とは第２及び最後の一つ手前のホール
デイングレジスタ段、R2及びRN-1に接続、以下
同様、となつている。この理論規則に従つて、
夫々のバスの最後のビツトはホルデイングレジス
タ段Ｎ／２及び（Ｎ／２）＋１に接続された加算
器と減算器から導出される。第９図のＮ個の
RACは番号の順に並んでいるが、奇数番号のも
のは全ての加算器８１に接続されているバス８５
に接続され、又、全ての偶数番号のRACはバス
８７を介して減算器８３に接続されている。列変
換係数、yk,1、yk,2、…yk,NはRAC出力から出力レ
ジスタの段U1−UNへビツト並列に同時にシフト
される事は、前の実施例と同じてあるが、このレ
ジスタの内容は次に順次にシフトアウトされる。 Ｎ×１ DCTプロセツサの一部としての入力、
出力、及びホールデイングレジスタの設置はチツ
プの入出力ピンの数を減少すると共に、各レジス
タアレーがその隣の物とのみ接続されている為に
接続が簡単になる。又、この回路装置は殆ど全て
の回路が別々の仕事をしながら連続的に作業して
いる同時操作を容易ならしめている。この事は、
リアルタイムプロセツシングを単一チツプによつ
て達成しようとする時には重要な事である。更
に、第１段デシメーシヨン−イン−フレクエンシ
ーを実行する為のビツト直列構造の使用は、所要
の回路装置を減少させ、回路接続を簡単化する。 変換メモリの読取り、書込みアドレツシングの
適当な制御によつて、Ｎ×ＮワードのRAMのみ
が中間結果（又はマトリツクス）の記憶用に及び
記憶された中間結果の読み出し用に要求されるマ
トリツクス転位を行う為の両者に対して要求され
るのみである。転移メモリ（又はRAM）はＮ＝
16の場合16×16ワードを含むが、第２図に示すよ
うに別々の読取り、書込み端を有する。現在流れ
ているブロツクの中間結果は第１のＮ×１プロセ
ツサからメモリ内に連続的に書込まれ、一方前の
ブロツクの中間結果は第２のＮ×１プロセツサに
読み出されるので、読取り、書込み操作は、これ
が読み出される前には損壊されない様に配列され
ねばならない。これを達成する一つの方法は、読
取り、書込み制御及びアドレスを、前のブロツク
のサンプルが読み出されたのと同一の位置に各サ
ンプル（又はワード）が書込まれる様にアレンジ
する事である。この様にすると、読取り、書込み
各操作はクロツクサイクルの半分（Ｔ／２）を必
要とする。これを実行する別の方法は、書込みア
ドレスを一行又は一列読出しアドレスよりも遅ら
せる事である。この様にすると、各読取り、書込
み操作はフルサイクル(T)を取り得るが、２組のア
ドレスデコーダを使用しなければならなくなる。 所望のマトリツクス転位を行うために、前のブ
ロツクが既にRAMに行ごとに書込まれている場
合は、データはメモリ５から列ごとに読み出さ
れ、これが続く。従つて、例えばＮ＝16の場合、
前のブロツクのデータがRAMに０、１、２、
３、…等、の順で書込まれたとすると、データは
０、16、32、48、…等、の順で読み出され、それ
と同時に現在のブロツクのデータは同じ順番
（０、16、32、48、等、）でRAMに書込まれる。
次のブロツクにおいてはデータは再び１、２、３
…、等、と読み出され／書込まれ、この操作が繰
返される。アドレスは８ビツトカウンタによつて
作り出す事が出来、順番の変更は上位４桁と下位
４桁を入れ替える事で容易に行い得る。この回路
装置は第２図の回路１６の一部である。ブロツク
の始動ストローブは読み／書き操作のアドレスの
リセツトに使用される。この要領でのRAMアド
レスの制御の為に必要なカウンタはROMで作ら
れた制御信号によつて加算器とレジスタとによつ
て作ることが出来る事に注意されたい。 この２次元プロセツサにおいては、殆どの応用
においてn1は８である。n2、n3及びn4は回路のコ
ンピユータシミユレーシヨンによつて決定される
が、この回路の中では多数の像がデジタル化され
てそのピクセルが本発明の回路装置で変換されて
逆の変換が次に行われて、像が再現される。n24
＝12、n3＝16、n4＝９によつて非常な精度が得ら
れた。この様な精度を必要としない、例えば低ビ
ツトレートビデオにおいては、n2、n3、及びn4は
１又は２に減少させ得る。 本発明は例示的な実施例に関連して説明した
が、その中での自明的な変形は本発明の実行なし
に当業者には明らかな所であり、従つて、本発明
は添付請求の範囲の範囲からのみ限定されるべき
ものである。 開示の抄録 このプロセツサは、２次元離散余弦変換
（DCT）を行う為にビデオ信号或いはその他の２
次元データのリアルタイムプロセツシングが可能
なものである。プロセツサはビデオ帯域幅或いは
イメージ圧縮システムの一部として使用する事が
出来る。回路装置は、分布アリスマテイツクを使
用して、又、デシメーシヨン−イン−フレクエン
シーを使用して全行又は全列のベクトル内積を同
時に計算する第１の一次元DCTプロセツサ３を
有し必要とするメモリ容量（ROM）の量を減少
させている。ROMのサイズを更に減少する為に
部分和も使用する事が出来る。第１のプロセツサ
からの一次元の変換されたマトリツクスは転位メ
モリ５に記憶されて、記憶されたマトリツクスの
転位は、入力データマトリツクスの所望の２次元
DCTを計算する類似の回路装置である第２の一
次元DCTプロセツサ７に印加される。
換の計算を行つて一次元Ｎ×Ｎ中間変換マトリツ
クスを形成する第１のＮ×１ DCTプロセツサ
と、 前記中間変換マトリツクスを記憶するＮ×Ｎ転
位メモリと、 前記転位メモリの中に記憶された前記中間変換
マトリツクスの転移の一次元変換を計算して所望
の２次元DCTを得る第２のＮ×１ DCTプロセ
ツサと、 を有しており、前記両Ｎ×１ DCTプロセツサ
は、 前記入力データのマトリツクスの列、又は前記
記憶中間変換マトリツクスの行又は列がビツト直
列の形式で印加される入力Ｎ段入力レジスタと、 前記入力レジスタの対応段に接続された段と、
前記入力レジスタの内容をビツト並列形式で前記
入力レジスタが一杯になつた度ごとにホールデイ
ングレジスタにトランスフアする装置とを有する
前記Ｎ段ホールデイングレジスタと、 前記ホールデイングレジスタに接続され、Ｎ個
のベクトル内積を同時に計算する装置であつて、
前記装置は前記ホールデイングレジスタに接続さ
れて第１段デシメーシヨン−イン−フレクエンシ
ーを実行して前記ホールデイングレジスタから受
取つたＮビツトワードから一対のＮ／２ビツトワ
ードを作出す回路装置を有する装置と、 前記回路装置に接続されたＮ個のRACであつ
て、前記各RACは１又はそれ以上のリードオン
リーメモリ（ROM）と累算器とを有し、前記各
RACは一方又は他方の前記Ｎ／２ビツトワード
によつてアドレスされるＮ個のRACと、 前記RACの夫々対応する対応累算器に接続さ
れたその夫々の段を有するＮ段出力レジスタと、
更に、 前記Ｎ個の計算済みベクトル内積を前記出力レ
ジスタに同時にトランスフアする装置と、 を有する、 一対の一次元DCTプロセツサを使用して行−
列デコンポジシヨン法で入力データのＮ×Ｎマト
リツクスの２次元DCTを作出す２次元離散余弦
変換（DCT）プロセツサ。 ２ 前記RACは夫々部分和特性（又は装置）を
有し、前記各RACは前記回路装置から受取つた
前記Ｎ／２ビツトワードの一法又は他方の相違す
る部分によつてアドレスされ、前記各RACは更
に前記２又はそれ以上のROMから検索したワー
ドを加算する装置とこれによつて出来た加算され
たワードをRACに付設された累算器に加える装
置とを有する、特許請求の範囲第１項に記載の２
次元DCT。 ３ 前記入力データマトリツクスの一次元変換を
一時に一列ごとに計算して一次元中間変換マトリ
ツクスを作出す第１のＮ×１ DCTプロセツサ
と、 前記中間変換マトリツクスを記憶するＮ×Ｎ転
位メモリと、更に、 前記転位メモリ内に記憶された前記中間変換マ
トリツクスの転位の一次元変換を計算して所望の
２次元DCTを得る為の第２のＮ×１ DCTプロ
セツサとを有して成り、 前記両Ｎ×１ DCTプロセツサは、 入力データの前記マトリツクスの列又は前記記
憶中間変換マトリツクスの行又は列がビツト直列
形式で加えられるＮ段入力レジスタと、 前記入力レジスタの対応段に接続された段と、
前記入力レジスタの内容をビツト並列形式で前記
入力レジスタが一杯になつた度ごとに前記ホール
デイングレジスタに引渡す装置とを有するＮ段ホ
ールデイングレジスタと、 Ｎ個のベクトル内積を同時に計算する、前記ホ
ールデイングレジスタに接続された分布アリスマ
テイツク回路装置であつて、前記分布アリスマテ
イツク回路装置は、前記ホールデイングレジスタ
の出力に接続された第１段デシメーシヨン−イン
−フレクエンシー回路装置を有し、前記デシメー
シヨン−イン−フレクエンシー回路装置は前記ホ
ールデイングレジスタから受取つた各Ｎビツトワ
ードから一対のＮ／２ビツトワードを作出す装置
を有する分布アリスマテイツク回路装置と、 前記分布アリスマテイツク回路装置は更に、
夫々が１乃至数個のROMプラス累算器を有し、
前記RACは前記デシメーシヨン−イン−フレク
エンシー回路装置の出力に接続されており、更
に、 その各々の段が前記RACの対応累算器に接続
され、前記累算器からビツト並列で前記ベクトル
内積を受取る装置と、前記内積をビツト直列にシ
フトアウトする装置とを有するＮ段出力レジスタ
と、 を有する、一対の一次元DCTプロセツサを有し、
行−列デコンポジシヨン法によつて入力データの
Ｎ×Ｎマトリツクスの２次元DCTを作出す２次
元離散余弦変換（DCT）プロセツサ。 ４ Ｎ＝16であり、前記入力データマトリツクス
は８ビツト２進ワードでエンコードされたビデオ
ピクセルであり、前記回路装置は単一チツプに造
り上げられている、特許請求の範囲第３項に記載
のプロセツサ。 ５ 入力データの列又は行がビツト直列形式で加
えられるＮ段入力レジスタと、 その各段が前記入力レジスタの対応各段に接続
された各段と、前記入力レジスタが一杯になつた
度毎に前記入力レジスタの内容をビツト並列の形
式で前記ホールデイングレジスタにトランスフア
する装置とを有するＮ段ホールデイングレジスタ
と、 Ｎ個のベクトル内積を同時に計算する、前記ホ
ールデイングレジスタに接続された分布アリスマ
テイツク回路装置であつて、前記分布アリスマテ
イツク回路装置は、前記ホールデイングレジスタ
の出力に接続された第１段デシメーシヨン−イン
−フレクエンシー回路装置を有し、前記デシメー
シヨン−イン−フレクエンシー回路装置は前記ホ
ールデイングレジスタから受取つた各Ｎビツトワ
ードから一対のＮ／２ビツトワードを作出す装置
を有する分布アリスマテイツク回路装置と、 前記分布アリスマテイツク回路装置は更に、
夫々が１乃至数個のROMプラス累算器を有する
Ｎ個のRACを有し、前記RACは前記デシメーシ
ヨン−イン−フレクエンシー回路装置の出力に接
続されており、更に、 前記夫々のRACの対応する累算器に接続され
た段を有する出力レジスタであつて、前記出力レ
ジスタはビツト並列方式で前記累算器からの前記
ベクトル内積を受取る装置と、前記内積をビツト
直列形式にシフトアウトする装置とを有する出力
レジスタと、 を有するＮ×１離散余弦変換（DCT）プロセツ
サ。 ６ 前記RACは夫々部分和特性を有し、前記
RACは２又はそれ以上のROMを有し、その夫々
が前記デシメーシヨン−イン−フレクエンシー回
路装置から受取つた前記Ｎ／２ビツトワードの一
方又は他方の別々の部分でアドレスされ、前記
RACは夫々更に前記Ｎ／２ビツトワードの前記
別々の部分で前記２又はそれ以上のROMから検
索されたワードを加える装置と、これによつて作
られた加算されたワードを前記RACに対応する
累算器に印加する装置とを有する、特許請求の範
囲第５項に記載のDCTプロセツサ。 ７ 入力データのＮ×Ｎマトリツクスの２次元
DCTを作り出す２次元離散余弦変換プロセツサ
において、 第１および第２のＮ×１ DCTプロセツサと
Ｎ×Ｎ転位メモリと、 入力データの該Ｎ×Ｎマトリツクスの転位を前
記第１のDCTプロセツサに加えることにより、
中間Ｎ×Ｎマトリツクスを計算する装置と、 該中間マトリツクスを該転位メモリ内に記憶す
る装置と、 前記記憶された中間マトリツクスの転位を前記
第２のＮ×１ DCTプロセツサに読み出すこと
により入力データの前記マトリツクスの２次元
DCTを計算する装置とを有し、 前記Ｎ×１ DCTプロセツサは夫々第１段デ
シメーシヨン−イン−フレクエンシーおよび部分
和により分布アリスマテイツクを行う回路装置に
よつてＮ個のベクトル内積を同時に計算する手段
を有し、 前記転位メモリは別々の読取り書込み端子およ
びこれに接続された読取り書込み制御回路付きＮ
×Ｎランダム・アクセス・メモリ（RAM）アレ
イを有し、記憶されたマトリツクスの転位が前記
第２のＮ×１ DCTプロセツサへの印加のため
に行われるように、前記第１のDCTプロセツサ
の出力が行方向と列方向に交互に読み取られ、前
記第２のDCTプロセツサの入力が行方向と列方
向に交互に読み出される、２次元離散余弦変換プ
ロセツサ。 発明の分野 本発明は空間ドメイン信号、例えばビデオ信号
を離散余弦変換（DCT）として周知の数学的手
順で周波数ドメイン信号に変換するプロセツサに
関する。 発明の背景 DCTはイメージ圧縮即ちビデオ帯域幅圧縮に
関して各種の変換コーデイング法の中で最も効果
的な技術と考えられている。DCTは離散フーリ
エ変換（DFT）に類似してはいるが、余弦項の
みを有する。この方法で帯域幅圧縮を実行する事
によつて、デジタルにエンコードされた画像素子
即ちピクセルの正方形ブロツクが、Ｎ×Ｎブロツ
クのピクセルデータが印加される２次元（Ｎ×
Ｎ）DCTプロセツサによつて周波数ドメインに
変換される事が出来るが、その際入力データマト
リツクスはＮ×Ｎ離散余弦マトリツクスに乗算さ
れて中間マトリツクスが作られ、中間マトリツク
スの転位が同一離散余弦マトリツクスに乗算され
て所望の２次元変換マトリツクスを得る。変換さ
れたマトリツクスの各要素は量子化する事が出
来、その中で最もエネルギーの大きいもののみが
伝送の必要がある。受信機においては、空間ドメ
インの最初のビデオ信号を再構成する為に逆の変
換が行われる。Ｎ×Ｎ DCTにおいては、Ｎが
大きい程圧縮比が大きくなるが、計算が大変にな
る。 マトリツクス乗算は２個のＮ×１ベクトルの内
積を計算して積のマトリツクスの単一要素を得
る。即ち、入力マトリツクスの列の各要素は余弦
マトリツクスの行の各対応要素と乗算されて、積
は加算されて積のマトリツクスの単一要素を得
る。即ち、16×16ブロツクのピクセルの変換に対
しては、16の積が、夫々が256要素を有する中間
及び変換マトリツクスの単一要素又は係数を得る
為に加算されねばならない。多数の高速アルゴリ
ズムが必要とする計算の数を減少する為に誘導さ
れた。例えば、DCTマトリツクスが若干数のス
パース（sparse）マトリツクスに分解されたが、
その結果バタフライ構造となつた。これらのバタ
フライ構造は計算を相当に減少させはするが、し
かし尚集積回路の為に大面積のシリコンを必要と
する多数の高速乗算器が必要で、これは繁雑な内
部配線、チツプ内の悪い接続配線、不規則な形
状、と言う結果を生む。DCTは使用しないがア
ダマール及びハール（Hadamard and Haar）
変換を使用するマトリツクスデコンポジシヨン技
術（matrix−decomposition technique）がフイ
リツプス テクニカル レビユー第38巻第４号／
第５号、1978／79年第119−130頁に、「カラーテ
レビジヨン画像のリアルタイム直交変換」、の題
名で記載されている。ここに説明の方式において
は、変換に必要とされる加算及び減算は、その中
の第１０図及び第１１図に記載されている高速ア
ルゴリズムによつて並列に実行されている。 これらの全ての要因はバタフライ構造のVLSI
（大規模集積）装置を非常に非能率なものにして
しまう。この種の構造を使用するDCTのVLSI装
置の例としては、JEEE Journal on Selected
Areas in Communication 1986年１月第49−61
頁記載の「離散フーリエ余弦変換チツプ」に記載
されている。その中の第１７図に示す出来上りチ
ツプは多数の乗算器を有し、シリコン表面を能率
的に使用してはおらず、８×１一次元変換が行い
得るのみである。２次元変換は２つの一次元変換
を含み、中間の計算結果の一時的な記憶及びマト
リツクス転位が必要であり、従つてこれは一次元
変換に比較して非常に複雑になる。又、IEEE
Transactions on Computers、第Ｃ−32巻第12
号、1983年第1128−1136頁に記載の、「パイプラ
イン化分布アリスメテイツクPFFTプロセツサ」
には、プライムフアクタフーリエ変換（Prime
Facter Fourier Transform−PFFT）が記載さ
れているが、これは離散フーリエ変換を比較的短
いプライム長さの変換（relatively short prime
length transform）の組に分解する事を含んで
おり、上述した形式に類似したマトリツクス分解
技術である。PFFTの実行にはROMに記憶され
たルツクアツプテーブルを含む分布アリスメテイ
ツクを利用している。ROMに記憶されているル
ツクアツプテーブルにデータを供給する入力回路
装置はコーナーターニング（corner turning）回
路と、一対のRAMのワード選択カウンタと、
「パイプラインラツチ」（”pipeline latch）とを
含んでいる。エキストラの小型ROMと加算器と
を加えてROMのサイズを減少させる技術も又、
その第８図に公開されている。 本発明は現在の技術状態におけるVLSI技術を
効果的に使用できる２次元DCTのリアルタイム
処理に対する必要性に応えるものである。本発明
は単一チツプ上の16×16DCTのリアルタイム処
理を提供するものである。これは、ビデオカメラ
によつて16×16入力マトリツクスが作られるのと
同じ割合で量子化装置に印加する変換16×16マト
リツクスをプロセツサから作らねばならぬ事を意
味する。プロセツサは現在のMOS技術によるデ
イジタルビデオシステムで通常使用される定格で
ある14.3MHzの入力サンプル又はピクセルレイト
を取扱う事が可能であるべきである。必要とする
大量の計算の為に、この定格でのリアルタイム処
理は、装置内での固有な同時性と並列性とを開発
する事によつてのみ達成可能である。 発明の要約 高速アルゴリズムをシリコンの中にマツピング
する代りに、本発明においては、ベクトル内積を
同時に得る為及びROM寸法を最小限度にするた
めデシメーシヨン−イン−フレクエンシー
（decimation−in−frequency）と組合わせた分
布アリスメテイツク（distributed arithmetic）
と、ビツト直列（bit−serial）とビツト並列
（bit−parallel）データ構造と、部分和とを使用
する。新しい入出力装置と能率的なマトリツクス
転位回路が考案された。その結果は非常に規則正
しい構造で乗算器の無い構成体即ち回路装置であ
る。変換演算の固有の性質、即ち、(1)変換マトリ
ツクス係数が定数でその為分布アリスメテイツク
の使用が可能であるが、その中で乗算器をメモリ
ルツクアツプテーブル又はROMで置換えが可能
であること、又、(2)マトリツクスベクトル積が若
干数の同時ベクトル内積によつて実現される事の
為にこれが可能となる。デシメーシヨン−イン−
フレクエンシーと部分和は必要とするルツクアツ
プテーブルのサイズを減少させるのに利用され
る。ビツト直列構造はデシメーシヨン−イン−フ
レクエンシーの実施に使用されるがその為シリコ
ンの面積は非常に小さく内部配線（routing）は
非常に単純化された。その結果はメモリと、加算
器と、レジスタのみから構成される２次元DCT
プロセツサであり、乗算器は必要ではない。回路
回りの高度な同時的操作の規則性はモジユール設
計を可能とするが、これはVLSI実現に対する理
想的な特徴である。又、この構成体はビツト直列
とビツト並列回路装置を最大限に組合わせてあ
る。この新規な構造体は他の２次元線形演算にも
応用可能である。 本発明による２次元DCTプロセツサは、Ｎ×
Ｎ入力データブロツクが列ごとに順番に印加され
る一次元（Ｎ×１）列DCTプロセツサを有する。
入力装置即ち列プロセツサは入力データの列変換
を、必要とされるROMの量を低下させる為にデ
シメーシヨン−イン−フレクエンシーの加算特性
と部分和を有する分布アリスメチツクスを使用す
る回路によつて行う様に設計されている。入力用
Ｎ×１プロセツサがＮ回路設けられておりその
夫々がリードオンリーメモリー（ROM）とカス
ケード接続された累算機とを有し、RACと呼ば
れている。この累算機はROMから引出されたデ
ータをシフトの上加算して列転位の要素を同時に
計算する。結果の中間ベクトルはRAMから成る
Ｎ×Ｎ転位メモリの一行に記憶される。データマ
トリツクスの各列は入力用Ｎ×１プロセツサーに
順次加えられてＮ×Ｎ中間マトリツクス(Y)を作る
が、これはデータマトリツクスの転位（Xt）と
ROMに記憶された定数で表示された離散余弦と
マトリツクス(C)との積（XtＣ）である。上記信
号ｔはマトリツクスの転位を示す。第２の出力行
Ｎ×1DCTプロセツサが次に使用されてXtＣの各
列用の一次元Ｎ×1DCTを計算するのに使用され
るが、これはメモリー内の記憶から引出される。
この第２の行変換操作結果は従つてCtXCを得る
事となるが、これが所望の２次元Ｎ×Ｎ DCT
である。プロセツサには制御回路が設けられる
が、これはクロツクその他の制御信号を作り、上
記の各部品の操作を制御する。 入力Ｎ×１ DCTプロセツサはn1本の並列線
路によつて順番に入力データが加えられるＮ段の
入力レジスタを有するが、ここでn1は入力データ
のワード又はピクセル当りのビツト数である。入
力レジスタがデータ列で一杯になると直ちに、列
の全部はビツト並列形式でホールデイングレジス
タに同時にシフトされ、そして入力レジスタは次
のデータ列の収集を開始する。ホールデイングレ
ジスタのＮ段の夫々のデータは、最下位ビツトを
先頭にして一時に１ビツト、同時にシフトアウト
される。この様にして形成されたＮ−ビツトのワ
ードは、これはいわゆる第１段デシメーシヨン−
イン−フレクエンシー（decimation−in−
frequency）技術の一部として２個のＮ／２ビツ
トワードに変換され、出来たＮ／２ビツトのワー
ドはRACのすべてのROMのアドレスに同時に使
用される。第１段デシメーシヨン（decimation）
は符号なしのn1個の入力データを（n1＋２）ビツ
トの２の補数に変換するので、同一操作はn1＋２
回繰返されて各のROMから読み出されたn1＋２
ワードはハードワイアド（hard−wired）１ビツ
ト右シフトを有するシフトレジスタを有する累算
機の内容に順次加算される。データワードの一部
である符号ビツトにより加算ではなく減算が行わ
れる。各列の入力データがプロセスされた後のこ
れらのRACの夫々の累算出力は列変換の要素で
ある単一係数から成る。RACの全ての内容がＮ
段出力レジスタへ同時にビツト並列の形でトラン
スフアされ、その後、その内容はn2並列線の変換
メモリの一行（又は一列）に順次シフトされる。
Ｎ×Ｎメモリがこの要領で一杯になると、第２即
ち出力Ｎ×１列DCTプロセツサーが列ごとに
（又は行ごとに）RAMメモリ中に記憶されたマ
トリツクスを読み出して、これによつてXtＣの
変換が得られる。第2N×１ DCTは第１即ち入
力プロセツサが行つたのと同様な要領で所望のＮ
×２次元DCTを発生する。両方のＮ×１プロセ
ツサは、第2N×１プロセツサのデータを表示す
るのに多数のビツトを必要とすることを除けば、
同様な回路で構成し得る。 この新規な２次元Ｎ×Ｎプロセツサは第1N×
１プロセツサを有するが、これには最初のマトリ
ツクスを列ごとに読み出して入力データのＮ×Ｎ
ブロツクの転位が印加され、この第1N×１プロ
セツサは分布アリスマテイツクを使用して前記入
力データの各列のＮベクトル内積を同時に計算す
る装置を有するが、ここでＮ×Ｎ離散余弦マトリ
ツクスはＮ個のRACに記憶され、この夫々は
ROMと累算機から成り、このROMは入力デー
タの前記列のデータワードから誘導されたＮ／２
ビツトワードによつてアドレスされる。この要領
でROMから検索されたワーズはシフト及び加算
操作によつてシフトレジスタに累算され、Ｎ個の
RACの各々の出力は、入力データブロツクのＮ
×１変換を有するＮ×Ｎ中間マトリツクスの一行
（又は一列）の各要素又は係数を有する。Ｎ×Ｎ
RAMアレーに中間マトリツクスを記憶し、そ
の転位を第2N×１ DCTプロセツサに読み出す
回路が設けられるが、この第２プロセツサは所望
の２次元Ｎ×Ｎ DCTを、前記中間Ｎ×Ｎマト
リツクスを発生するのに使用したものと類似の回
路によつて発生する。適当な制御回路が所要の制
御信号を発生する為に設置される。 従つて、リアルタイムベースで２進化コードビ
デオデータの16×16ブロツクの変換を発生する事
の出来る２次元DCTプロセツサを提供する事が
本発明の目的であるが、この場合、前記プロセツ
サの構造体、回路、及びアルゴリズムは実現の容
易性からして現在状態でのVLSI技術が選定され、
これが単一CMOSチツプの上に実現される事を
目的とするものである。 本発明の別の目的は入力データマトリツクスか
らのデータ列（又は行）を瞬時に処理して、入力
データの列（又は行）と、プロセツサ内のＮ
RACに記憶されている離散余弦マトリツクスの
Ｎ列とのベクトル内積を有する要素の行を形成す
る一次元Ｎ×１ DCTプロセツサを提供する事
であり、ここで、このＮ×１プロセツサはベクト
ル内積を計算するのに分布アリスマテイツクと、
第１段デシメーシヨン−イン−フレクエンシー
と、部分和とを利用しており、このプロセツサは
レジスタと、小容量のメモリと、加算器とのみを
有するものである。 本発明の更に別の目的は、入力データの列と
RACの中に記憶されている離散余弦マトリツク
スのベクトル内積を構成する複数の要素を効果的
に、瞬時に計算する為に、分布アリスマテイツク
と、RACsと、デシメーシヨン−イン−フレクエ
ンシーと、部分和とを使用する回路を有する一次
元DCTで構成された２次元DCTを提供する事で
あるが、この際、入力データの列は順次に処理さ
れてRAMアレーに記憶される中間Ｎ×Ｎマトリ
ツクスを発生し、次に中間マトリツクスの転位
が、所望の２次元Ｎ×Ｎ DCTを同様に発生す
る類似の一次元DCTプロセツサに読み出される
ものである。 本発明の別の目的は、プロセツサの構造体、回
路、及びアルゴリズムが、構造物乃至回路が少な
く、且つ制御が簡単で、高速で、複雑な計算を達
成する様に選定された、16×16ビデオピクセルの
ブロツクのリアルタイム処理可能の16×16 ２次
元DCTを提供する事である。選定された構造と
回路とは、乗算器を使用する事なしに小容量の
ROMを使用して若干数のベクトル内積の瞬時
（又は同時）計算を可能とし、又、ビツト直列及
びビツト並列フオーマツトが組合わせて使用され
て、シリコンチツプ面積を減少させ、回路内配線
の簡単化を図り、ビデオ信号のリアルタイム処理
を行うために高速操作を可能とするものである。 【図面の簡単な説明】 第１図は本発明を単一チツプに実現した時に必
要な接続を示す。 第２図は本発明の一実施例の全体のブロツク図
を示す。 第３図は分布アリスマテイツクその他の特徴を
使用するDCTプロセツサを示す。 第４図はRACのブロツク図である。 第５図はデシメーシヨン−イン−フレクエンシ
ーを使用するDCTプロセツサのブロツク図であ
る。 第６図は部分和を使用しないRACの回路図で
ある。第７図と第８図とは部分和を使用する
RACの回路図である。 第９図は第２図のＮ×１ DCTの完成回路図
である。 詳細な説明 離散余弦変換（DCT）は、余弦関数によつて
サンプリングされた基礎ベクトルの組から成る直
交変換である。Ｎ式のDCT変換マトリツクス、
Ｃ、は次の式で示される、 ここに、ｋ＝１、２、３、…ｌ＝１、２、３、
…、又、ｌ＝１に対して、Ck、l＝N-1/2である。
DCTによつて帯域幅圧縮を行う為には、符号無
しの２進コード化ピクセルの形のＮ×Ｎビデオデ
ータのブロツクは２次元変換を行わねばならな
い。Ｎ次の２次元DCTは、 Ｙ＝CtXC (2) ここに、Ｙは変換されたマトリツクス、Ｘはデ
ータ即ちビデオピクセルマトリツクス、Ctは式(1)
で定義された離散余弦マトリツクス、Ｃの転位で
ある。 ２次元Ｎ×Ｎ DCTの実行は行−列デコンポ
ジシヨン技術と称される公知技術によつてなされ
るが、その詳細は1984年刊行のプレンテイスホー
ル信号処理シリーズのダツジオン、マーサロー
（Dudgeon ＆ Mersareau）共著の著書“多次
元デジタル信号処理”を参照されたい。この公知
技術において、２次元DCTは２つの逐次型一次
元DCTによつてなされるが、データマトリツク
スは第１の一次元DCTに行ごとに印加される。
本発明においては、この技術の変形が使用された
が、ここでは、上述の様に、データマトリツクス
の転位が行われるように、行ごとにではなく列ご
とに読み出す事によつてデータマトリツクスの転
位がなされて、これが第１の一次元DCTプロセ
ツサに加えられる。これは回路の簡単化をもたら
す。従つて本発明においては、第１の一次元Ｎ×
１ DCTプロセツサの出力はXtＣであり、これ
は一時的に転位メモリに記憶され、次に別のＮ×
１ DCTが記憶されたマトリツクスの転位から
計算されて所望の式(2)の２次元DCT(Y)を得る。
速度が重要ではない場合には、２つのＮ×1DCT
計算は同一回路で時分割処理する事も出来るが、
リアルタイム操作が必要な現在の場合には２個の
Ｎ×１プロセツサを使用する。 第１図は単一チツプ上に実施した本発明を示す
図である。このチツプへの接続はバイアス電圧
Vcc、接地、サンプルクロツク、及びブロツクの
始動（Start−of−Block）ストローブを有する。
入力データはn1本の並列線を介して並列に、ピク
セルワードの各ビツト毎に印加される。変換出力
データは長い変換ワードに対してはn3並列線で構
成されよう。入出力データは同一クロツクレート
で連続的にチツプにシフトして出し入れされる。 第２図は、n1本の並列線で入力データが印加さ
れる第１の列Ｎ×１ DCT、３、を有し、DCT
３の出力は一時的に、行又は列状にＮ×Ｎ変換メ
モリ５に記憶されるが、これは図示の通り別々の
入出力端を有するランダムアクセスメモリ
（RAM）を有する。DCT３からメモリ５へのn2
本の並列線は、必要とされる精度によつて変化は
するが、通常は入力データよりもビツト数が大き
くなる。記憶されたマトリツクスは列又は行ごと
に（中間マトリツクスの記憶の仕方に応じて）n2
本の並列線を介して第２の行Ｎ×1DCT７に印加
される。即ち、記憶マトリツクスの転位が読み出
される。変換出力データはＮ×１ DCTプロセ
ツサからn3本の並列線を介して得られる。タイミ
ング及び制御回路９はクロツク信号と、外部回路
からこれに印加されたブロツクの始動ストローブ
とを有し、また、回路９は若干のタイミング及び
制御信号１１及び１２をプロセツシング回路に供
給している。読取り／書込みアドレス及び制御回
路１６は回路９から制御信号１２を受取り、線１
４を介して適当な読取り／書込みアドレスその他
の制御信号をメモリ５に加える。 前述のベクトル内積は夫々Ｎ個の積の和を有す
る。この計算はROMから成るルツクアツプテー
ブルを使用して乗算なしで出来る事は数学的に証
明する事も出来るが、この場合、変換されたマト
リツクスの必要とする係数はROMから得たルツ
クアツプテーブル値のシフトと加算によつて得ら
れる。これも又当業者に取つて公知の計算技術で
あるが分布アリスマテイツクとも称されている。
シフトと加算が行われるROMと累算機とはRAC
と称するユニツトを形成し、各RACは離散余弦
マトリツクスの各列を表示する定数を記憶する。 第３図と第４図とは、分布アリスマテイツクが
いかに機能するかと言う事、及び本発明に使用さ
れた若干の回路の特徴を示すものである。第３図
において、入力レジスタ１３はＮ段Q1−Qoを有
する。各ピクセル列又はその他の２次元データ、
X1k…XNKは１／Ｔのデータ又はクロツクレート
でビツト並列形式でレジスタ１３の段Ｑ１に印加
される。ピクセルデータマトリツクスを列ごとに
読む事によつて、その変換が完成する。ビデオデ
イジタルピクセルデータは通常ピクセルの輝度を
表示する８ビツト無符号ワードにエンコードされ
ている。即ちデータ入力はQ1に８（又はn1）並列
線で印加され、各レジスタ段Q1−QNは並列８（又
はn1）ビツトで構成される。Ｎクロツクサイクル
の後、列はレジスタ１３のＮ段に完全に負荷され
る。この時第２図の回路９からの制御信号１１ａ
と１１ｂとが全部の８（又はn1）ビツトワーズを
並列にQ1−QNからホールデイングレジスタ１５
の対応段R1−RNにトランスフアする。入力デー
タの次の列が入力レジスタ１３への入力開始を始
めるが、その時回路の残りはホールデイングレジ
スタ内のデータの一次元変換を得る為にＮベクト
ル内積計算を平行して行う。この同時計算を行う
事によつてホールデイングレジスタ内のデータは
１ビツトずつ下の桁の数字を先頭にして制御信号
１１ｃに応じてシフトアウトされる。レジスタ１
５のＮ段からのＮラインはＮ−ビツトバスを形成
するが、そのすべての線にはＮ個の別々のRAC
（RAC(1)−RAC(N)）が印加される。即ち、各ク
ロツクサイクル毎に相違するＮ−ビツトワード
が、各RACの部品であるROMの同時アドレスに
使用される。RAC（１）はそのROMにマトリツ
クスＣの第１列の係数の可能な組み合わせを表示
する2N個の定数を有する。例えば、第１列係数が
c1、1、c2、1、c3、1…cN,1、だつたりするとROMは
これらの係数を個々に、又は可能な全ての和、即
ち、c1、1＋c2、1、c1、1＋c3、1、c1、1＋cN,1、c1、1
′＋
c2、1＋c3、1′など、これらの列係数の全ての和を含
むまでの全てを尽す事となる。例えば、Ｎ＝４に
対して列変換の各要素、yk,lの計算は次の様に表
示される。即ち、c1、1（110101001）＋c2、1
（00101010）＋c3、1（1100111）＋c4、1（10101110）
、
ここで８ビツトワードはデータの列を構成する各
データピクセルを表す。この例において全てのデ
ータワーズの最も下の桁のビツトはワード1010を
形成する。このワードはRAC(1)のROMから記憶
値c1、1＋c3、1を検索するが、これは第４図に示す
様にRAC(1)のシフトレジスタ２５に加えられる。
次のクロツクサイクルにおいて、全てのデータワ
ードの次に下の桁のデジツトが全てのRACに加
えられてどのRACがアドレスされたか、及びＮ
デジツトワードが何であつたかに応じてこれから
各種の値を検索する。この検索されたワードは又
第４図の加算／減算回路２３を介してシフトレジ
スタに加えられるが、ここで加算／減算回路にフ
イードバツクされるシフトレジスタの前の内容は
１ビツトの右シフトされたデータが加えられる。
即ち、ROM２１の第２アドレシングの後、シフ
トレジスタ２５はその中にレスシグニフイカンス
なデータワードのビツトを表示すると言う事実を
反映して最初のワードに1/2の重みを付け（又は
２で割る）をしたデータと次のデータとの２検索
ワードの和を記憶する事となる。このプロセスは
データワードの各ビツトに対して繰返される。加
算／減算回路２３は正規データビツトに対して加
算を行い、符号ビツトに対しては減算を行う。
ROMからのこれらの検索の上重みを付けられた
全てのワードの最終加算は積マトリツクスの係数
の一つ又は一次元変換の一係数に等しい。例え
ば、積マトリツクスXtＣの要素がyk,lである場合、
この要領で第１列の入力データを処理した後の
RAC(1)の出力はy1、1で、同様にRAC(N)の出力は
y1,Nとなろう。即ち、積マトリツクスXtＣの第１
行の全体はこの計算の完成後RAC出力で得られ
る。回路９からの制御信号１１ｄに応じて、各
RACの累算された内容物、yk,1−yK,N、は出力レ
ジスタ１９の段、U1−UNにn2（又はn3）並列線を
介して並列して同時に負荷されるが、これはエキ
ストラ２入力マルチプレクサ付の入力レジスタに
類似している。レジスタ１９の内容は次に順次そ
の段U1かn2（又はn3）並列線を介して転位メモリ
又は２次元プロセツサ出力に制御信号１１ｅに応
動してシフトされる。例えば、Ｎ＝16の場合、デ
ータの１列を入力レジスタ１３に負荷するのに16
クロツクサイクルを要し、従つて16サイクル毎に
制御回路９はホールデイングレジスタ１５へのデ
ータ列のトランスフアを行うのに信号１１ｂを提
供する事が必要である。レジスタ１９はその内容
物yk,lを順番にシフトウト可能であるが、その間
RACは積のマトリツクスの次の行の計算を行い、
入力レジスタは入力データを集めている。第４図
に示すように、ROM２１の出力はワードレング
スn4ビツトを有するが、これはROMの中に記憶
されたワードの長さによつて決定される。回路９
から回路２３に加えられた信号１１ｆは、この回
路が加算用か減算用かを決定する。シフトレジス
タ２５に加えられた制御信号１１ｇ及び１１ｈは
リセツト及び並列負荷信号である。 一次元DCTプロセツサの両方の回路装置はワ
ード当りのビツト数を除けば同一である。第２図
に示すように、第１プロセツサは入力ワード長さ
n1と出力ワード長さn2とを有する。第２のDCT
プロセツサ７は入出力ワード長さn2とn3とを夫々
有する。 第３図及び第４図の回路は乗算器を必要としな
いが、これはこれに付属する各ROMに記憶させ
るべき定数の数の為に重大な制限を受ける。例え
ば、今Ｎ＝16とすると、各RACの各ROMに要求
されるワード数は２の16乗即ち65536個である。
このサイズのROMは、全プロセツサを単一チツ
プに収めようとすると現在のVLSI技術では実現
できない。ROMのサイズを減少させる為に２つ
のアプローチがなされたが、これらは共に僅かな
付加回路を要するのみである。第１のアプローチ
はデシメーシヨン−イン−フレクエンシー技術の
翻案であるが、上記技術は従来の高速フーリエ変
換（FFT）アルゴリズムで従来技術として使用
されているものである。積マトリツクスＹ＝Xt
Ｃの（ｋ、ｌ）番目の要素は、 Yk,l＝ｘ t k・ｃ l＝ｉN 〓m=1 xn,k、cn,l (3) ここに、ｘ kはＸのｋ番目の列ベクトルであり、
又、ｃ lはＣの１番目の列ベクトルである。式(1)
で定義されたＮ×Ｎ DCT変換マトリツクスＣ
を参照すると、偶数のＮに対して、ｌ＝１、３、
…Ｎ−１において、ck,l＋cN+1-k,lであり、１＝２、
４、…Ｎに対してck,l＝−cN+1-k,lである事を示す
事が出来る。これらの関係から式(3)は次の様にな
る、 Yk,l＝N/2 〓m=1 uk,ncm、ｌ (4) ｌ＝１、３、…Ｎ−１に対しては uk,n＝xn,R、＋xN-n+1,k′なので、 Yk、ｌ＝N/2 〓m=1 vkncm、ｌ (5) ｌ＝２、４、…Ｎに対しては Vk,n＝xn,k -XＮ−ｍ＋１、k′となる。式(4)と(5)
とは、変数ｕとｖとが最初のデータシークエンス
ｘと置換された場合、１からＮまでの和は１から
Ｎ／２までの和になる事を意味する。即ち、各
ROMにアドレスすべきデータビツト数は２分の
１に減少され、必要とする記憶すべきワード数は
２のＮ／２乗で減少する。原則的には、このデシ
メーシヨン−イン−フレクエンシー技術は、殆ど
のFFTアルゴリズムが行つているようにこの上
の段階にまで展開可能である。しかし、この節約
は、不規則性が増大するので実施の価値に値しな
い。即ち、モジユール構造を残す為に、第１段の
デシメーシヨンのみを適用した。発明のこの特徴
を第５図の回路で示す。 第５図において、Ｎ／２シリアル加算器３１は
レジスタ１５からの最初のデータシークエンスの
Ｎ／２個の相違する対から変数ｕを作る為に設け
られている。図示の通り、変数uk,1はx1,kとxN,k′の
和から、uk,2はx2,k、プラスxN-1,k′から、又，uk,N/2
はxN/2,kプラスxN/2+1,k′によつて得られる。入力デ
ータ要素の同一の対がＮ／２一ビツトシリアル減
算機３３で相互に減算されて新変換vk,lvk,2…vk,N/2
を作る。即ち、入力データの各列のデータ要素の
対は列の最初の及び最後の行の要素から、第２の
及び最後から一つ手前の要素から、第３の及び最
後の要素から３番目の要素から、などで構成され
る。第５図の入力データビツトxk、lは一時に１
ビツトの割合で（ビツト直列形式で）第３図のそ
れと類似のホールデイングレジスタから得られ、
シリアル加算器３１と減算器３３の出力は一時に
１ビツトずつ現れて２個のＮ／２ラインバスを形
成するがこの各バスはＮ／２個のRACの２個の
別のグループの入力を構成してい。加算器３１に
付設されているＮ／２ラインバスはこれに接続さ
れた奇数個のRAC、１、３、Ｎ−１、を有し、
これらのRACは奇数列のベクトル内積の全ての
要素、即ち、yk,1、yk,3、yk,N-1を計算する。減算
回路３３に付設されたＮ／２ラインバス３６は偶
数個のRAC ２、４、Ｎ、を有し、ベクトル内積
の偶数列の要素を計算する。 第５図のそれの様な第１段デシメーシヨン回路
の使用は各ROMのサイズを16×16マトリツクス
に対して256ワードに減少させる、と言うのは各
RACがこの場合８ビツトワードでアドレスされ
るからである。 本発明はROMサイズを更に減少する為に付加
技術を使用する。この付加技術は、式(4)及び式(5)
のデータ点の数である指数ｍに関する和は部分和
に分割し得る、と言う観察に基ずくものである。
(3)を２つの部分和に分割しようとするならば、次
の通りである。N 〓m=1 xn,kcn,1＝F1（ｃ 1、ｘ k）＋F2（ｃ 1、ｘ 1） …(6) ここで、 Ｆ（Ci、xk）＝i N/2 〓+(i-1)N/2 xn,kcm、1′、ｉ＝１、２ F1とF2との和にはＮサンプルではなく、Ｎ／
２サンプルしか含まれていない事に注意された
い。この様にして分割する事によつて２のＮ乗ワ
ードのROMは２のＮ／２乗ワードに２個の小型
のROMに置換される。更に詳細に説明すると、
各RACの入力時のデータワードは２グループに
分割され、第１グループは１からＮ／２のビツト
から成り、第２グループはデータ数（Ｎ／２）＋
１からＮに至るものである。即ち、RACをアド
レスするのに普通使用されるワードはその前半及
び後半から成る２つの等しい部分に分割される。
夫々の短いワードは分割されたROMのアドレス
用に使用され、ROMの出力は並列に加算されて
和は累算器に印加される。この分割技術で使用さ
れる部分和の数は任意の偶数でよい。Ｎ＝16に対
して各ROMは２個の小型ROMに置換される。
Ｎ＝32の場合、各ROMは４個のROMに置換し
得るが、この場合加算を行う付加段が必要とな
る。Ｎ＝８に対しては、ROMのサイズが既に十
分に小さいので分割は必要としない。 部分和及び第１段デシメーシヨン−イン−フレ
クエンシー技術の両者に使用するRACの構造を
第６図、第７図、及び第８図に夫々８×１、16×
１、及び32×１用のものを示す。第５図のそれと
類似の第１段デシメーシヨン−イン−フレクエン
シー特性を有する８×１用の第６図のRACは、
ROMにアドレスする２個の４デジツトバスを含
んでいる。各ROM３７は２の４乗即ち16ワード
の記憶を行うのみで、従つて部分和の必要はな
く、ROM３７の出力は加算／減算回路３９とシ
フトレジスタ１１とを介して出力４３に加えられ
る。第７図の16×1DCT RACはデシメーシヨン
特性の為に２個の８ビツトバスを有するが、類似
した16ワードROM４５と４７に印加される２個
の４ビツトワードに、上述した様にして分割され
る。加算器４９は２つのROMから検索されたn4
ビツトワードを加算して単一のn4＋１ビツトワー
ドを作るが、これは加算／減算回路５１と、シフ
トレジスタ５３と、シフトレジスタの出力と加算
一減算器５１の間の１ビツト右シフトフイードバ
ツク回路とを有する累算器に印加される。５５に
おけるRAC出力はn2（又はn3）ビツトを有する
が、これはn4＋１ビツトよりも若干長い。 第８図のDCT RACは、夫々が16ワードを記
憶し得る４個の同様なROM、６１，６３，６５
及び６７にアドレスする４個の４ビツトワードに
分割される、16ビツトライン入力バスを含んであ
る。ROM６１と６３の出力でのn4ビツトワード
は加算器６９で加算され、又、ROM６５と６７
からの類似したワードは加算器７１に加えられ
る。これらの３個の加算器は加算器７３に加えら
れるそれらの出力端を有し、これは累算器に加え
られる出力端を有し、この累算器はベクトル内積
の要素の一つを計算する為に前述したものと同様
に作用する。 これら２技術を繰合わせる事によつて、若干の
回路装置が増大するものの、所要のROMサイズ
を小さくする事ができる。例えば、Ｎ＝16に対し
て、16×16 ２次元DCTの直接の実行には216×
16×２＝221ワードのROMを必要とする。反対
に、上述の２技術を使う事によつて第７図の回路
は24×２×16×２＝210、約1kワードのROM、を
必要とするのみとなる。このサイズのROMにお
いては、本発明の新規な回路装置が実現可能であ
るばかりでなく、ICの実現という見地からして
も非常に有効である。 第９図はデシメーシヨン−イン−フレクエンシ
ー特性を備えるＮ×１ DCTの完全ブロツク図
である。第９図のブロツク図はこの回路設計の規
則性と単位性とが強調されている。この図におい
て、入力レジスタはＮ段Q1−QNを有し、その
夫々がn1（又はn2）ビツトを有するが、これはこ
の回路が第２図の第１、第２プロセツサのどちら
に属するかによつて相違しており、データの入力
列、x1,k、x2,k、…xN,kはn1（又はn2）並列線のQ1
に加えられる。Ｎ／２直列加算器８１と同様な直
列減算器８３が設けられて、その夫々がこれに接
続されたホールデイングレジスタの各段R1−RN
からの一対の単線を有する。Ｎ／２ビツトバス８
５は加算器８１から誘導のビツトを有し、Ｎ／２
ビツトバス８７は減算器８３からのビツトを有す
る。Ｎ／２両ビツトバスの第１ビツト、uk,1及び
vk,1を発生する加算器と減算器は共に第１及び最
後のホールデイングレジスタ段R1とRNに接続さ
れていることに注意されたい。同様に、２つのバ
スにおける各ワードの第２ビツトを発生する加算
器と減算器とは第２及び最後の一つ手前のホール
デイングレジスタ段、R2及びRN-1に接続、以下
同様、となつている。この理論規則に従つて、
夫々のバスの最後のビツトはホルデイングレジス
タ段Ｎ／２及び（Ｎ／２）＋１に接続された加算
器と減算器から導出される。第９図のＮ個の
RACは番号の順に並んでいるが、奇数番号のも
のは全ての加算器８１に接続されているバス８５
に接続され、又、全ての偶数番号のRACはバス
８７を介して減算器８３に接続されている。列変
換係数、yk,1、yk,2、…yk,NはRAC出力から出力レ
ジスタの段U1−UNへビツト並列に同時にシフト
される事は、前の実施例と同じてあるが、このレ
ジスタの内容は次に順次にシフトアウトされる。 Ｎ×１ DCTプロセツサの一部としての入力、
出力、及びホールデイングレジスタの設置はチツ
プの入出力ピンの数を減少すると共に、各レジス
タアレーがその隣の物とのみ接続されている為に
接続が簡単になる。又、この回路装置は殆ど全て
の回路が別々の仕事をしながら連続的に作業して
いる同時操作を容易ならしめている。この事は、
リアルタイムプロセツシングを単一チツプによつ
て達成しようとする時には重要な事である。更
に、第１段デシメーシヨン−イン−フレクエンシ
ーを実行する為のビツト直列構造の使用は、所要
の回路装置を減少させ、回路接続を簡単化する。 変換メモリの読取り、書込みアドレツシングの
適当な制御によつて、Ｎ×ＮワードのRAMのみ
が中間結果（又はマトリツクス）の記憶用に及び
記憶された中間結果の読み出し用に要求されるマ
トリツクス転位を行う為の両者に対して要求され
るのみである。転移メモリ（又はRAM）はＮ＝
16の場合16×16ワードを含むが、第２図に示すよ
うに別々の読取り、書込み端を有する。現在流れ
ているブロツクの中間結果は第１のＮ×１プロセ
ツサからメモリ内に連続的に書込まれ、一方前の
ブロツクの中間結果は第２のＮ×１プロセツサに
読み出されるので、読取り、書込み操作は、これ
が読み出される前には損壊されない様に配列され
ねばならない。これを達成する一つの方法は、読
取り、書込み制御及びアドレスを、前のブロツク
のサンプルが読み出されたのと同一の位置に各サ
ンプル（又はワード）が書込まれる様にアレンジ
する事である。この様にすると、読取り、書込み
各操作はクロツクサイクルの半分（Ｔ／２）を必
要とする。これを実行する別の方法は、書込みア
ドレスを一行又は一列読出しアドレスよりも遅ら
せる事である。この様にすると、各読取り、書込
み操作はフルサイクル(T)を取り得るが、２組のア
ドレスデコーダを使用しなければならなくなる。 所望のマトリツクス転位を行うために、前のブ
ロツクが既にRAMに行ごとに書込まれている場
合は、データはメモリ５から列ごとに読み出さ
れ、これが続く。従つて、例えばＮ＝16の場合、
前のブロツクのデータがRAMに０、１、２、
３、…等、の順で書込まれたとすると、データは
０、16、32、48、…等、の順で読み出され、それ
と同時に現在のブロツクのデータは同じ順番
（０、16、32、48、等、）でRAMに書込まれる。
次のブロツクにおいてはデータは再び１、２、３
…、等、と読み出され／書込まれ、この操作が繰
返される。アドレスは８ビツトカウンタによつて
作り出す事が出来、順番の変更は上位４桁と下位
４桁を入れ替える事で容易に行い得る。この回路
装置は第２図の回路１６の一部である。ブロツク
の始動ストローブは読み／書き操作のアドレスの
リセツトに使用される。この要領でのRAMアド
レスの制御の為に必要なカウンタはROMで作ら
れた制御信号によつて加算器とレジスタとによつ
て作ることが出来る事に注意されたい。 この２次元プロセツサにおいては、殆どの応用
においてn1は８である。n2、n3及びn4は回路のコ
ンピユータシミユレーシヨンによつて決定される
が、この回路の中では多数の像がデジタル化され
てそのピクセルが本発明の回路装置で変換されて
逆の変換が次に行われて、像が再現される。n24
＝12、n3＝16、n4＝９によつて非常な精度が得ら
れた。この様な精度を必要としない、例えば低ビ
ツトレートビデオにおいては、n2、n3、及びn4は
１又は２に減少させ得る。 本発明は例示的な実施例に関連して説明した
が、その中での自明的な変形は本発明の実行なし
に当業者には明らかな所であり、従つて、本発明
は添付請求の範囲の範囲からのみ限定されるべき
ものである。 開示の抄録 このプロセツサは、２次元離散余弦変換
（DCT）を行う為にビデオ信号或いはその他の２
次元データのリアルタイムプロセツシングが可能
なものである。プロセツサはビデオ帯域幅或いは
イメージ圧縮システムの一部として使用する事が
出来る。回路装置は、分布アリスマテイツクを使
用して、又、デシメーシヨン−イン−フレクエン
シーを使用して全行又は全列のベクトル内積を同
時に計算する第１の一次元DCTプロセツサ３を
有し必要とするメモリ容量（ROM）の量を減少
させている。ROMのサイズを更に減少する為に
部分和も使用する事が出来る。第１のプロセツサ
からの一次元の変換されたマトリツクスは転位メ
モリ５に記憶されて、記憶されたマトリツクスの
転位は、入力データマトリツクスの所望の２次元
DCTを計算する類似の回路装置である第２の一
次元DCTプロセツサ７に印加される。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US029761 | 1987-03-24 | ||
| US07/029,761 US4791598A (en) | 1987-03-24 | 1987-03-24 | Two-dimensional discrete cosine transform processor |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH02501601A JPH02501601A (ja) | 1990-05-31 |
| JPH0526229B2 true JPH0526229B2 (ja) | 1993-04-15 |
Family
ID=21850746
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63501201A Granted JPH02501601A (ja) | 1987-03-24 | 1987-12-15 | ２次元離散余弦変換プロセッサ |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US4791598A (ja) |
| EP (1) | EP0353223B1 (ja) |
| JP (1) | JPH02501601A (ja) |
| CA (1) | CA1290854C (ja) |
| DE (1) | DE3789116T2 (ja) |
| WO (1) | WO1988007725A1 (ja) |
Families Citing this family (105)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6336180B1 (en) | 1997-04-30 | 2002-01-01 | Canon Kabushiki Kaisha | Method, apparatus and system for managing virtual memory with virtual-physical mapping |
| NL8700845A (nl) * | 1987-04-10 | 1988-11-01 | Philips Nv | Een-dimensionale lineaire beeldtransformator. |
| FR2617621B1 (fr) * | 1987-07-03 | 1989-12-01 | Thomson Semiconducteurs | Memoire de transposition pour circuit de traitement de donnees |
| JPH0795320B2 (ja) * | 1988-10-11 | 1995-10-11 | 日本電子株式会社 | 大容量高速フーリエ変換装置 |
| IT8921420V0 (it) * | 1989-07-13 | 1989-07-13 | Telettra Spa | Sistema e circuito per il calcolo di trasformata discreta bidimensionale. |
| US5299025A (en) * | 1989-10-18 | 1994-03-29 | Ricoh Company, Ltd. | Method of coding two-dimensional data by fast cosine transform and method of decoding compressed data by inverse fast cosine transform |
| US5053985A (en) * | 1989-10-19 | 1991-10-01 | Zoran Corporation | Recycling dct/idct integrated circuit apparatus using a single multiplier/accumulator and a single random access memory |
| US5268853A (en) * | 1989-12-01 | 1993-12-07 | Ricoh Company, Ltd. | Orthogonal transformation processor for compressing information |
| US5359549A (en) * | 1989-12-01 | 1994-10-25 | Ricoh Company, Ltd. | Orthogonal transformation processor for compressing information |
| JP2646778B2 (ja) * | 1990-01-17 | 1997-08-27 | 日本電気株式会社 | ディジタル信号処理装置 |
| US5191548A (en) * | 1990-03-14 | 1993-03-02 | C-Cube Microsystems | System for compression and decompression of video data using discrete cosine transform and coding techniques |
| US5128754A (en) * | 1990-03-30 | 1992-07-07 | New York Institute Of Technology | Apparatus and method for encoding and decoding video |
| US5319724A (en) * | 1990-04-19 | 1994-06-07 | Ricoh Corporation | Apparatus and method for compressing still images |
| US5126962A (en) * | 1990-07-11 | 1992-06-30 | Massachusetts Institute Of Technology | Discrete cosine transform processing system |
| US5196930A (en) * | 1990-07-20 | 1993-03-23 | Matsushita Electric Industrial Co., Ltd. | High efficienccy coding and decoding apparatus for lowering transmission or recording rate of transmitted or recorded video signal without reducing picture quality |
| US7142720B1 (en) * | 1990-07-31 | 2006-11-28 | Fujitsu Limited | Image data processing method and apparatus |
| US5875266A (en) * | 1990-07-31 | 1999-02-23 | Fujitsu Limited | Image data processing a method and apparatus |
| EP0469855B1 (en) * | 1990-07-31 | 1999-12-01 | Fujitsu Limited | Image data processing method and apparatus |
| US5933538A (en) * | 1990-07-31 | 1999-08-03 | Fujitsu Limited | Image data processing method and apparatus |
| JP2646844B2 (ja) * | 1990-11-16 | 1997-08-27 | 日本電気株式会社 | 離散コサイン変換装置 |
| JPH04242860A (ja) * | 1990-12-28 | 1992-08-31 | Sony Corp | 演算装置 |
| JPH04236664A (ja) * | 1991-01-18 | 1992-08-25 | Sony Corp | 演算回路 |
| JP2964172B2 (ja) * | 1991-03-08 | 1999-10-18 | 富士通株式会社 | Ｄｃｔマトリクス演算回路 |
| JP2866754B2 (ja) * | 1991-03-27 | 1999-03-08 | 三菱電機株式会社 | 演算処理装置 |
| FR2681962B1 (fr) * | 1991-09-30 | 1993-12-24 | Sgs Thomson Microelectronics Sa | Procede et circuit de traitement de donnees par transformee cosinus. |
| US5285402A (en) * | 1991-11-22 | 1994-02-08 | Intel Corporation | Multiplyless discrete cosine transform |
| US5361220A (en) * | 1991-11-29 | 1994-11-01 | Fuji Photo Film Co., Ltd. | Discrete cosine transformation with reduced components |
| US5410500A (en) * | 1992-02-21 | 1995-04-25 | Sony Corporation | Discrete cosine transform apparatus and inverse discrete cosine transform apparatus |
| US5528736A (en) * | 1992-04-28 | 1996-06-18 | Polytechnic University | Apparatus and method for performing a two-dimensional block data transform without transposition |
| US5394349A (en) * | 1992-07-10 | 1995-02-28 | Xing Technology Corporation | Fast inverse discrete transform using subwords for decompression of information |
| US5654910A (en) * | 1992-08-26 | 1997-08-05 | Sony Corporation | Processing method and apparatus for performing 4 ×4 discrete cosine transformation or inverse discrete cosing transformation |
| KR940004467A (ko) * | 1992-08-26 | 1994-03-15 | 오오가 노리오 | 이산코사인 변환장치 및 그 역변환장치 |
| US5339265A (en) * | 1992-08-31 | 1994-08-16 | University Of Maryland At College Park | Optimal unified architectures for the real-time computation of time-recursive discrete sinusoidal transforms |
| JPH06103301A (ja) * | 1992-09-17 | 1994-04-15 | Sony Corp | ８ｘ８離散コサイン変換回路および８ｘ８離散コサイン逆変換回路 |
| US5523847A (en) * | 1992-10-09 | 1996-06-04 | International Business Machines Corporation | Digital image processor for color image compression |
| JPH06149862A (ja) * | 1992-11-13 | 1994-05-31 | Sony Corp | 行列データ乗算方法及び行列データ乗算装置 |
| KR950000386B1 (ko) * | 1992-12-30 | 1995-01-16 | 재단법인 한국전자통신연구소 | 이산여현 변환회로 |
| US6002809A (en) * | 1993-04-15 | 1999-12-14 | International Business Machines Corporation | Digital image processor for image scaling |
| US5345408A (en) * | 1993-04-19 | 1994-09-06 | Gi Corporation | Inverse discrete cosine transform processor |
| US5572691A (en) * | 1993-04-21 | 1996-11-05 | Gi Corporation | Apparatus and method for providing multiple data streams from stored data using dual memory buffers |
| US5483475A (en) * | 1993-09-15 | 1996-01-09 | Industrial Technology Research Institute | Fast pipelined 2-D discrete cosine transform architecture |
| US5638068A (en) * | 1993-11-24 | 1997-06-10 | Intel Corporation | Processing images using two-dimensional forward transforms |
| JPH07152730A (ja) * | 1993-11-30 | 1995-06-16 | Toshiba Corp | 離散コサイン変換装置 |
| US5583803A (en) * | 1993-12-27 | 1996-12-10 | Matsushita Electric Industrial Co., Ltd. | Two-dimensional orthogonal transform processor |
| JP2677969B2 (ja) * | 1993-12-27 | 1997-11-17 | 松下電器産業株式会社 | 直交変換装置 |
| KR0130446B1 (ko) * | 1994-01-18 | 1998-04-15 | 배순훈 | 이차원 역이산코사인 변환방법 및 장치 |
| US5481487A (en) * | 1994-01-28 | 1996-01-02 | Industrial Technology Research Institute | Transpose memory for DCT/IDCT circuit |
| JP3133601B2 (ja) * | 1994-02-09 | 2001-02-13 | 株式会社東芝 | パラレル・シリアル変換装置及びこれを用いた線形変換装置 |
| US5729484A (en) * | 1994-02-28 | 1998-03-17 | Intel Corporation | Processes, apparatuses, and systems of encoding and decoding signals using transforms |
| KR0150350B1 (ko) * | 1994-05-10 | 1998-10-15 | 모리시다 요이치 | 직교변환 프로세서 |
| TW284869B (ja) * | 1994-05-27 | 1996-09-01 | Hitachi Ltd | |
| KR100357338B1 (ko) * | 1994-08-02 | 2003-02-11 | 가부시끼가이샤 히다치 세이사꾸쇼 | 데이타처리시스템 |
| US5574798A (en) * | 1994-08-03 | 1996-11-12 | International Business Machines Corporation | Visual presentation system which determines length of time to present each slide or transparency |
| JP4035789B2 (ja) * | 1994-10-13 | 2008-01-23 | 富士通株式会社 | 逆離散コサイン変換装置 |
| US5717468A (en) * | 1994-12-02 | 1998-02-10 | International Business Machines Corporation | System and method for dynamically recording and displaying comments for a video movie |
| US5623423A (en) * | 1994-12-12 | 1997-04-22 | Univ. Of Texas | Apparatus and method for video decoding |
| JPH08186723A (ja) * | 1994-12-28 | 1996-07-16 | Ricoh Co Ltd | 画像処理装置用エンコーダ |
| GB2301203B (en) * | 1995-03-18 | 2000-01-12 | United Microelectronics Corp | Real time two dimensional discrete cosine transform/inverse discrete cosine transform circuit |
| GB2302421B (en) * | 1995-03-18 | 1999-11-03 | United Microelectronics Corp | Apparatus for two-dimensional inverse discrete cosine transform |
| US5668748A (en) * | 1995-04-15 | 1997-09-16 | United Microelectronics Corporation | Apparatus for two-dimensional discrete cosine transform |
| US5610849A (en) * | 1995-06-23 | 1997-03-11 | United Microelectronics Corporation | Real time two-dimensional discrete cosine transform/inverse discrete cosine transform circuit |
| JPH0981541A (ja) * | 1995-09-12 | 1997-03-28 | Matsushita Electric Ind Co Ltd | 累算器 |
| US5729691A (en) * | 1995-09-29 | 1998-03-17 | Intel Corporation | Two-stage transform for video signals |
| US5801979A (en) * | 1995-10-20 | 1998-09-01 | Matsushita Electric Corporation Of America | Carry logic that produces a carry value from NLSBs for a ROM accumulator in an inverse discrete cosine transform processor |
| US5805482A (en) * | 1995-10-20 | 1998-09-08 | Matsushita Electric Corporation Of America | Inverse discrete cosine transform processor having optimum input structure |
| US5867601A (en) * | 1995-10-20 | 1999-02-02 | Matsushita Electric Corporation Of America | Inverse discrete cosine transform processor using parallel processing |
| US5959690A (en) * | 1996-02-20 | 1999-09-28 | Sas Institute, Inc. | Method and apparatus for transitions and other special effects in digital motion video |
| US5764553A (en) * | 1996-02-28 | 1998-06-09 | Lsi Logic Corporation | Generalized data processing path for performing transformation and quantization functions for video encoder systems |
| US5999958A (en) * | 1996-04-24 | 1999-12-07 | National Science Council | Device for computing discrete cosine transform and inverse discrete cosine transform |
| US5894430A (en) * | 1996-05-20 | 1999-04-13 | Matsushita Electric Industrial Co., Ltd. | Orthogonal transform processor |
| US5949920A (en) * | 1996-08-13 | 1999-09-07 | Hewlett-Packard Co. | Reconfigurable convolver circuit |
| US6819783B2 (en) | 1996-09-04 | 2004-11-16 | Centerframe, Llc | Obtaining person-specific images in a public venue |
| US6044176A (en) * | 1996-11-12 | 2000-03-28 | Samsung Electronics Co., Ltd. | Method of performing inverse discrete cosine transform |
| JPH10207868A (ja) * | 1997-01-21 | 1998-08-07 | Sharp Corp | ２次元配列転置回路 |
| KR100538607B1 (ko) * | 1997-03-12 | 2005-12-22 | 마츠시타 덴끼 산교 가부시키가이샤 | 부호화방법, 부호화장치 및 기록매체와, 복호화방법, 복호화장치 및 기록매체 |
| AUPO648397A0 (en) | 1997-04-30 | 1997-05-22 | Canon Information Systems Research Australia Pty Ltd | Improvements in multiprocessor architecture operation |
| US6061749A (en) * | 1997-04-30 | 2000-05-09 | Canon Kabushiki Kaisha | Transformation of a first dataword received from a FIFO into an input register and subsequent dataword from the FIFO into a normalized output dataword |
| US6414687B1 (en) | 1997-04-30 | 2002-07-02 | Canon Kabushiki Kaisha | Register setting-micro programming system |
| US6707463B1 (en) | 1997-04-30 | 2004-03-16 | Canon Kabushiki Kaisha | Data normalization technique |
| AUPO647997A0 (en) * | 1997-04-30 | 1997-05-22 | Canon Information Systems Research Australia Pty Ltd | Memory controller architecture |
| US6195674B1 (en) | 1997-04-30 | 2001-02-27 | Canon Kabushiki Kaisha | Fast DCT apparatus |
| US6289138B1 (en) | 1997-04-30 | 2001-09-11 | Canon Kabushiki Kaisha | General image processor |
| CN1147155C (zh) * | 1998-12-14 | 2004-04-21 | 松下电器产业株式会社 | Dct运算装置 |
| KR100313217B1 (ko) * | 1998-12-23 | 2001-12-28 | 서평원 | 파이프라인dct장치 |
| US6499045B1 (en) * | 1999-10-21 | 2002-12-24 | Xilinx, Inc. | Implementation of a two-dimensional wavelet transform |
| US7292730B1 (en) * | 1999-12-09 | 2007-11-06 | Intel Corporation | Two-dimensional inverse discrete cosine transforming |
| US6684235B1 (en) | 2000-11-28 | 2004-01-27 | Xilinx, Inc. | One-dimensional wavelet system and method |
| US6901422B1 (en) | 2001-03-21 | 2005-05-31 | Apple Computer, Inc. | Matrix multiplication in a vector processing system |
| US6870885B2 (en) * | 2001-05-16 | 2005-03-22 | Qualcomm Incorporated | Apparatus and method for decoding and computing a discrete cosine transform using a butterfly processor |
| US6996595B2 (en) * | 2001-05-16 | 2006-02-07 | Qualcomm Incorporated | Apparatus and method for consolidating output data from a plurality of processors |
| TWI220716B (en) * | 2003-05-19 | 2004-09-01 | Ind Tech Res Inst | Method and apparatus of constructing a hardware architecture for transfer functions |
| US7756351B2 (en) * | 2003-12-19 | 2010-07-13 | Stmicroelectronics, Inc. | Low power, high performance transform coprocessor for video compression |
| KR100754167B1 (ko) * | 2004-10-06 | 2007-09-03 | 삼성전자주식회사 | 다양한 크기의 블록에 대한 변환/역변환 방법 및 그 장치 |
| US7730116B2 (en) * | 2004-12-14 | 2010-06-01 | Stmicroelectronics, Inc. | Method and system for fast implementation of an approximation of a discrete cosine transform |
| US8081830B2 (en) * | 2005-01-11 | 2011-12-20 | Hewlett-Packard Development Company, L.P. | Enhancement of digital images |
| WO2006091869A2 (en) | 2005-02-25 | 2006-08-31 | Youfinder Intellectual Property Licensing Limited Liability Company | Automated indexing for distributing event photography |
| US20070009166A1 (en) * | 2005-07-05 | 2007-01-11 | Ju Chi-Cheng | Scalable system for discrete cosine transform and method thereof |
| US8306284B2 (en) | 2005-07-18 | 2012-11-06 | Hysterical Sunset Limited | Manually-assisted automated indexing of images using facial recognition |
| EP2474155A1 (en) | 2009-09-02 | 2012-07-11 | Image Holdings | Method and system for displaying, managing and selling digital images |
| EP2478499A1 (en) | 2009-09-16 | 2012-07-25 | Image Holdings | Method and system of displaying, managing and selling images in an event photography environment |
| US10356440B2 (en) * | 2014-10-01 | 2019-07-16 | Qualcomm Incorporated | Scalable transform hardware architecture with improved transpose buffer |
| US9716852B2 (en) * | 2015-04-03 | 2017-07-25 | Semiconductor Energy Laboratory Co., Ltd. | Broadcast system |
| US10482155B2 (en) * | 2016-12-30 | 2019-11-19 | Intel Corporation | Winograd algorithm on a matrix processing architecture |
| US20230267167A1 (en) * | 2020-07-15 | 2023-08-24 | Nippon Telegraph And Telephone Corporation | Two-dimensional data conversion device, method, and program |
| CN115425988B (zh) * | 2022-07-29 | 2024-02-09 | 北京融为科技有限公司 | 一种高速ldpc全模式列变换方法 |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4385363A (en) * | 1978-12-15 | 1983-05-24 | Compression Labs, Inc. | Discrete cosine transformer |
| US4293920A (en) * | 1979-09-04 | 1981-10-06 | Merola Pasquale A | Two-dimensional transform processor |
| GB2091526B (en) * | 1981-01-13 | 1985-10-02 | Harris Corp | Digital map generator and display system |
| US4449194A (en) * | 1981-09-25 | 1984-05-15 | Motorola Inc. | Multiple point, discrete cosine processor |
| US4541012A (en) * | 1982-01-04 | 1985-09-10 | Compression Labs, Inc. | Video bandwidth reduction system employing interframe block differencing and transform domain coding |
| FR2561010B1 (fr) * | 1984-03-09 | 1986-09-12 | Cit Alcatel | Processeur de calcul d'une transformee discrete du cosinus |
-
1987
- 1987-03-24 US US07/029,761 patent/US4791598A/en not_active Expired - Lifetime
- 1987-12-15 JP JP63501201A patent/JPH02501601A/ja active Granted
- 1987-12-15 DE DE3789116T patent/DE3789116T2/de not_active Expired - Fee Related
- 1987-12-15 WO PCT/US1987/003347 patent/WO1988007725A1/en not_active Ceased
-
1988
- 1988-03-23 CA CA000562276A patent/CA1290854C/en not_active Expired - Lifetime
- 1988-10-18 EP EP88900977A patent/EP0353223B1/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH02501601A (ja) | 1990-05-31 |
| EP0353223B1 (en) | 1994-02-16 |
| WO1988007725A1 (en) | 1988-10-06 |
| DE3789116T2 (de) | 1994-10-06 |
| CA1290854C (en) | 1991-10-15 |
| US4791598A (en) | 1988-12-13 |
| EP0353223A1 (en) | 1990-02-07 |
| DE3789116D1 (de) | 1994-03-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4791598A (en) | Two-dimensional discrete cosine transform processor | |
| US5249146A (en) | Dct/idct processor and data processing method | |
| Chan et al. | On the realization of discrete cosine transform using the distributed arithmetic | |
| KR0130772B1 (ko) | 고속디지탈신호처리프로세서 | |
| US20050004963A1 (en) | Parallel adder-based DCT/IDCT design using cyclic convolution | |
| JPS63136167A (ja) | 直交変換プロセッサ | |
| KR950009472A (ko) | 2차원 이산코사인 변환장치, 2차원 역이산코사인 변환장치 및 디지탈 신호처리 장치 | |
| US6282555B1 (en) | Orthogonal transform processor | |
| JPS62269519A (ja) | ディスクリ−トコサイン変換回路 | |
| US5952685A (en) | Signal processing applications of massively parallel charge domain computing devices | |
| US5867414A (en) | Compact pipelined matrix multiplier utilizing encoding and shifting circuit configurations | |
| US6003058A (en) | Apparatus and methods for performing arithimetic operations on vectors and/or matrices | |
| JP3577325B2 (ja) | 離散余弦変換（ｄｃｔ）によるデータ処理方法、ｄｃｔ方法、およびｄｃｔデータ処理回路 | |
| KR0139699B1 (ko) | 이산 코사인 변환장치 | |
| JPH06149861A (ja) | Ｄｃｔ及び逆ｄｃｔ演算装置並びにその演算方法 | |
| Hsiao et al. | A cost-efficient and fully-pipelinable architecture for DCT/IDCT | |
| KR100444729B1 (ko) | 레딕스-8 단일 경로 지연 전달 구조의 고속 퓨리에 변환장치 및 그 방법 | |
| US5999958A (en) | Device for computing discrete cosine transform and inverse discrete cosine transform | |
| Hsiao et al. | Parallel, pipelined and folded architectures for computation of 1-D and 2-D DCT in image and video codec | |
| JP3970442B2 (ja) | 離散コサイン変換装置及び逆離散コサイン変換装置 | |
| JP3652717B2 (ja) | 離散コサイン高速演算器 | |
| Amira et al. | A novel architecture for Walsh Hadamard transforms using distributed arithmetic principles | |
| KR0154919B1 (ko) | 2차원 역이산 코사인 변환 회로 | |
| JPH05153402A (ja) | 離散コサイン変換器 | |
| Demassieux et al. | Orthogonal transforms |