(57)【特許請求の範囲】
【請求項１】
画像デコンプレッションの方法であって、
（ａ）圧縮された画像定義ディジタル信号を入力する段階と、
（ｂ）信号プロセッサを用いて前記圧縮された画像定義ディジタル信号
をディジタル処理して空間的に冗長な画像定義ディジタル信号を生成する段階であり、複数の二次元８ポイント×８ポイント逆離散余弦変換の計算を行う段階を包含し、各計算が２の累乗の平方根に等しい因数でスケーリングしたスケーリング済み８ポイント一次元逆離散余弦変換の１６回の計算を含み、次いで、前記二次元逆離散余弦変換を前記２の累乗に等しいビット数だけシフトし、前記スケーリング済み８ポイント一次元逆離散余弦変換が離散余弦変換値Ｆ（０）−Ｆ（７）から値ｆ′（０）−ｆ′（７）を有し、１つのスケーリング済み８ポイント一次元逆離散余弦変換の前記計算が
（i）約Ｆ（０）＋Ｆ（４）に等しい中間値Ｐ0を計算する段階と、
（ii）約Ｆ（０）−Ｆ（４）に等しい中間値Ｐ1を計算する段階と、
（iii）約Ｆ（２）＋ｋ1Ｆ（６）（ここで、ｋ1は約２1/2−１である）に等しい中間値Ｐ2を計算する段階と、
（iv）約Ｆ（２）−ｋ2Ｆ（６）（ここで、ｋ2は約２1/2＋１である）に等しい中間値Ｐ3を計算する段階と、
（v）約Ｆ（１）＋ｋ3Ｆ（７）（ここで、ｋ3は約２1/2（２＋２1/2）1/2−２1/2−１である）に等しい中間値Ｐ4を計算する段階と、
（vi）約Ｆ（１）−ｋ4Ｆ（７）（ここで、ｋ4は約２1/2（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｐ5を計算する段階と、
（vii）約Ｆ（５）＋ｋ5Ｆ（３）（ここで、ｋ5は約２1/2（２−２1/2）1/2＋２1/2−１である）に等しい中間値Ｐ6を計算する段階と、
（viii）約Ｆ（５）−ｋ6Ｆ（３）（ここで、ｋ6は約２1/2（２−２1/2）1/2−２1/2＋１である）に等しい中間値Ｐ7を計算する段階と、
（ix）前記中間値Ｐ0、Ｐ2が利用できるようになった後、約Ｐ0＋ｋ7Ｐ2（ここで、ｋ7は約２-1/2（２＋２1/2）1/2である）に等しい中間値Ｑ0を計算する段階と、
（x）前記中間値Ｐ0、Ｐ2が利用できるようになった後、約Ｐ0−ｋ7Ｐ2に等しい中間値Ｑ2を計算する段階と、
（xi）前記中間値Ｐ1、Ｐ3が利用できるようになった後、約Ｐ1＋ｋ8Ｐ3（ここで、ｋ8は約２-1/2（２−２1/2）1/2である）に等しい中間値Ｑ1を計算する段階と、
（xii）前記中間値Ｐ1、Ｐ3が利用できるようになった後、約Ｐ1−ｋ8Ｐ3に等しい中間値Ｑ3を計算する段階と、
（xiii）前記中間値Ｐ4、Ｐ6が利用できるようになった後、約Ｐ4＋ｋ9Ｐ6（ここで、ｋ9は約−（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｑ4を計算する段階と、
（xiv）前記中間値Ｐ4、Ｐ6が利用できるようになった後、約Ｐ4−ｋ9Ｐ6に等しい中間値Ｑ6を計算する段階と、
（xv）前記中間値Ｐ5、Ｐ7が利用できるようになった後、約Ｐ5＋ｋ10Ｐ7（ここで、ｋ10は約（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｑ5を計算する段階と、
（xvi）前記中間値Ｐ5、Ｐ7が利用できるようになった後、約Ｐ5−ｋ10Ｐ7に等しい中間値Ｑ7を計算する段階と、
（xvii）前記中間値Ｑ6、Ｑ7が利用できるようになった後、約Ｑ6＋ｋ3Ｑ7に等しい中間値Ｒ6を計算する段階と、
（xviii）前記中間値Ｑ6、Ｑ7が利用できるようになった後、約Ｑ6−ｋ3Ｑ7に等しい中間値Ｒ7を計算する段階と、
（xix）前記中間値Ｑ0、Ｑ4が利用できるようになった後、約Ｑ0＋ｋ11Ｑ4（ここで、ｋ11は約２-1/2（２＋（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（０）を計算する段階と、
（xx）前記中間値Ｑ0、Ｑ4が利用できるようになった後、約Ｑ0−ｋ11Ｑ4に等しい前記ｆ′（７）を計算する段階と、
（xxi）前記中間値Ｑ1、Ｒ6が利用できるようになった後、約Ｑ1＋ｋ12Ｒ6（ここで、ｋ12は約（１／２）（２＋（２＋２1/2）1/2）1/2である）
に等しい前記ｆ′（１）を計算する段階と、
（xxii）前記中間値Ｑ1、Ｒ6が利用できるようになった後、約Ｑ1−ｋ12Ｒ6に等しい前記ｆ′（６）を計算する段階と、
（xxiii）前記中間値Ｑ2、Ｑ5が利用できるようになった後、約Ｑ2＋ｋ13Ｑ5（ここで、ｋ13は約２-1/2（２−（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（３）を計算する段階と、
（xxiv）前記中間値Ｑ2、Ｑ5が利用できるようになった後、約Ｑ2−ｋ13Ｑ5に等しい前記ｆ′（４）を計算する段階と、
（xxv）前記中間値Ｑ3、Ｒ7が利用できるようになった後、約Ｑ3＋ｋ12Ｒ7に等しい前記ｆ′（２）を計算する段階と、
（xxvi）前記中間値Ｑ3、Ｑ7が利用できるようになった後、約Ｑ3−ｋ12Ｒ7に等しい前記ｆ′（５）を計算する段階とを包含する段階と、
（ｃ）ディスプレイをレンダリングする際に使用するために前記の空間的に冗長な画像定義ディジタル信号を出力する段階とを包含することを特徴とする方法。
【請求項２】
請求の範囲第１項記載の方法において、
段階（i）および（ii）を同時に実施し、
段階（ix）および（x）を同時に実施し、
段階（xi）および（xii）を同時に実施し、
段階（xiii）および（xiv）を同時に実施し、
段階（xv）および（xvi）を同時に実施し、
段階（xvii）および（xviii）を同時に実施し、
段階（xix）および（xx）を同時に実施し、
段階（xxi）および（xxii）を同時に実施し、
段階（xxiii）および（xxiv）を同時に実施し、
段階（xxv）および（xxvi）を同時に実施することを特徴とする方法。
【請求項３】
請求の範囲第１項または第２項記載の方法において、前記中間結果が、その後の少なくとも３つのサイクルが完了するまで使用されないことを特徴とする方法。
【請求項４】
請求の範囲第１項または第２項記載の方法において、前記一次元逆離散余弦変換のうちの８つの各々について、８つのメモリ場所を使用して前記離散余弦変換値Ｆ（０）−Ｆ（７）および前記中間結果を保持することを特徴とする方法。
【請求項５】
請求の範囲第１項または第２項記載の方法において、前記一次元逆離散余弦変換のうちの８つの各々について、８つのメモリ場所を使用して前記中間値および前記逆離散余弦変換値ｆ′（０）−ｆ′（７）を保持することを特徴とする方法。
【請求項６】
請求の範囲第１項記載の方法において、２セットのＸＯＲゲートを使用して加算が行われるか減算が行われるかを決定することを特徴とする方法。
【請求項７】
請求の範囲第３項記載の方法において、
段階（vii）を段階（i）の後に実行し、
段階（v）を段階（vii）の後に実行し、
段階（iii）を段階（v）の後に実行し、
段階（xiii）を段階（iii）の後に実行し、
段階（xv）を段階（xiii）の後に実行し、
段階（ix）を段階（xv）の後に実行し、
段階（xi）を段階（ix）の後に実行し、
段階（xvii）を段階（xi）の後に実行し、
段階（xix）を段階（xvii）の後に実行し、
段階（xxi）を段階（xix）の後に実行し、
段階（xxv）を段階（xxi）の後に実行し、
段階（xxiii）を段階（xxv）の後に実行することを特徴とする方法。
【請求項８】
請求の範囲第４項記載の方法において、前記一次元逆離散余弦変換のうちの８つの各々について、８つのメモリ場所を使用して前記中間値および前記逆離散余弦変換値ｆ′（０）−ｆ′（７）を保持することを特徴とする方法。
【請求項９】
第１バタフライ演算サブシステム入力部、第２バタフライ演算サブシステム入力部およびバタフライ演出サブシステム出力部を有するバタフライ演算サブシステムと、
書き込みポートおよび読み出しポートを有する、メモリと、
バタフライ演算サブシステム出力部から前記メモリの書き込みポートに通じる第１信号パスと、
第１、第２のマルチプレクサ入力部およびマルチプレクサ出力部を有するマルチプレクサと、
マルチプレクサ出力部から第１バタフライ演算サブシステム入力部に通じる第２信号パスと、
前記メモリの読み出しポートから第１マルチプレクサ入力部に通じる第３信号パスと、
前記メモリに読み出し、書き込みアドレスおよび書き込み許可信号を与え、前記マルチプレクサを制御し、第２バタフライ演算サブシステム入力部に係数を与えて２の累乗の平方根に等しい因数でスケーリングしたスケーリング済み８ポイント一次元逆離散余弦変換の１６回の計算を含む二次元８ポイント×８ポイント逆離散余弦変換を演算するコントローラとを包含し、前記スケーリング済みの８ポイント一次元逆離散余弦変換が離散余弦変換値Ｆ（０）−Ｆ（７）からの値ｆ′（０）−ｆ′（７）を有し、前記コントローラが前記計算を次のように実施する、すなわち、
（i）約Ｆ（０）＋Ｆ（４）に等しい中間値Ｐ0を計算し、
（ii）約Ｆ（０）−Ｆ（４）に等しい中間値Ｐ1を計算し、
（iii）約Ｆ（２）＋ｋ1Ｆ（６）（ここで、ｋ1は約２1/2−１である）に等しい中間値Ｐ2を計算し、
（iv）約Ｆ（２）−ｋ2Ｆ（６）（ここで、ｋ2は約２1/2＋１である）に等しい中間値Ｐ3を計算し、
（v）約Ｆ（１）＋ｋ3Ｆ（７）（ここで、ｋ3は約２1/2（２＋２1/2）1/2−２1/2−１である）に等しい中間値Ｐ4を計算し、
（vi）約Ｆ（１）−ｋ4Ｆ（７）（ここで、ｋ4は約２1/2（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｐ5を計算し、
（vii）約Ｆ（５）＋ｋ5Ｆ（３）（ここで、ｋ5は約２1/2（２−２1/2）1/2＋２1/2−１である）に等しい中間値Ｐ6を計算し、
（viii）約Ｆ（５）−ｋ6Ｆ（３）（ここで、ｋ6は約２1/2（２−２1/2）1/2−２1/2＋１である）に等しい中間値Ｐ7を計算し、
（ix）前記中間値Ｐ0、Ｐ2が利用できるようになった後、約Ｐ0＋ｋ7Ｐ2（ここで、ｋ7は約２-1/2（２＋２1/2）1/2である）に等しい中間値Ｑ0を計算し、
（x）前記中間値Ｐ0、Ｐ2が利用できるようになった後、約Ｐ0−ｋ7Ｐ2に等しい中間値Ｑ2を計算し、
（xi）前記中間値Ｐ1、Ｐ3が利用できるようになった後、約Ｐ1＋ｋ8Ｐ3（ここで、ｋ8は約２-1/2（２−２1/2）1/2である）に等しい中間値Ｑ1を計算し、
（xii）前記中間値Ｐ1、Ｐ3が利用できるようになった後、約Ｐ1−ｋ8Ｐ3に等しい中間値Ｑ3を計算し、
（xiii）前記中間値Ｐ4、Ｐ6が利用できるようになった後、約Ｐ4＋ｋ9Ｐ6（ここで、ｋ9は約−（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｑ4を計算し、
（xiv）前記中間値Ｐ4、Ｐ6が利用できるようになった後、約Ｐ4−ｋ9Ｐ6に等しい中間値Ｑ6を計算し、
（xv）前記中間値Ｐ5、Ｐ7が利用できるようになった後、約Ｐ5＋ｋ10Ｐ7（ここで、ｋ10は約（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｑ5を計算し、
（xvi）前記中間値Ｐ5、Ｐ7が利用できるようになった後、約Ｐ5−ｋ10Ｐ7に等しい中間値Ｑ7を計算し、
（xvii）前記中間値Ｑ6、Ｑ7が利用できるようになった後、約Ｑ6＋ｋ3Ｑ7に等しい中間値Ｒ6を計算し、
（xviii）前記中間値Ｑ6、Ｑ7が利用できるようになった後、約Ｑ6−ｋ3Ｑ7に等しい中間値Ｒ7を計算し、
（xix）前記中間値Ｑ0、Ｑ4が利用できるようになった後、約Ｑ0＋ｋ11Ｑ4（ここで、ｋ11は約２-1/2（２＋（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（０）を計算し、
（xx）前記中間値Ｑ0、Ｑ4が利用できるようになった後、約Ｑ0−ｋ11Ｑ4に等しい前記ｆ′（７）を計算し、
（xxi）前記中間値Ｑ1、Ｒ6が利用できるようになった後、約Ｑ1＋ｋ12Ｒ6（ここで、ｋ12は約（１／２）（２＋（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（１）を計算し、
（xxii）前記中間値Ｑ1、Ｒ6が利用できるようになった後、約Ｑ1−ｋ12Ｒ6に等しい前記ｆ′（６）を計算し、
（xxiii）前記中間値Ｑ2、Ｑ5が利用できるようになった後、約Ｑ2＋ｋ13Ｑ5（ここで、ｋ13は約２-1/2（２−（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（３）を計算し、
（xxiv）前記中間値Ｑ2、Ｑ5が利用できるようになった後、約Ｑ2−ｋ13Ｑ5に等しい前記ｆ′（４）を計算し、
（xxv）前記中間値Ｑ3、Ｒ7が利用できるようになった後、約Ｑ3＋ｋ12Ｒ7に等しい前記ｆ′（２）を計算し、
（xxvi）前記中間値Ｑ3、Ｑ7が利用できるようになった後、約Ｑ3−ｋ12Ｒ7に等しい前記ｆ′（５）を計算することを特徴とする装置。
【請求項１０】
第１乗算器入力部、第２乗算器入力部、加算器入力部および乗算累算器出力部を有する乗算累算器と、
書き込みポートおよび読み出しポートを有するメモリと、
乗算累算器入力部から前記メモリの書き込みポートに通じる第１信号パスと、
第１、第２のマルチプレクサ入力部およびマルチプレクサ出力部を有するマルチプレクサと、
マルチプレクサ出力部から前記乗算累算器の第１乗算器入力部に通じる第２信号パスと、
前記マルチプレクサのマルチプレクサ出力部から前記乗算累算器の加算器入力部に通じる第３信号パスと、
前記メモリの読み出しポートから第１マルチプレクサ入力部に通じる第４信号パスと、
前記メモリに読み出し、書き込みアドレスおよび書き込み許可信号を与え、前記マルチプレクサを制御するコントローラであり、前記乗算累算器の第２乗算器入力部に接続した出力部を有する係数ブロックを包含し、２の累乗の平方根に等しい因数でスケーリングしたスケーリング済みの８ポイント一次元逆離散余弦変換の１６回の計算を含む二次元８ポイント×８ポイント逆離散余弦変換を演算するコントローラとを包含し、前記スケーリング済みの８ポイント一次元逆離散余弦変換が離散余弦変換値Ｆ（０）−Ｆ（７）からの値ｆ′（０）−ｆ′（７）を有し、前記コントローラが次のように前記計算を実施する、すなわち、
（i）約Ｆ（０）＋Ｆ（４）に等しい中間値Ｐ0を計算し、
（ii）約Ｆ（０）−Ｆ（４）に等しい中間値Ｐ1を計算し、
（iii）約Ｆ（２）＋ｋ1Ｆ（６）（ここで、ｋ1は約２1/2−１である）に等しい中間値Ｐ2を計算し、
（iv）約Ｆ（２）−ｋ2Ｆ（６）（ここで、ｋ2は約２1/2＋１である）に等しい中間値Ｐ3を計算し、
（v）約Ｆ（１）＋ｋ3Ｆ（７）（ここで、ｋ3は約２1/2（２＋２1/2）1/2−２1/2−１である）に等しい中間値Ｐ4を計算し、
（vi）約Ｆ（１）−ｋ4Ｆ（７）（ここで、ｋ4は約２1/2（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｐ5を計算し、
（vii）約Ｆ（５）＋ｋ5Ｆ（３）（ここで、ｋ5は約２1/2（２−２1/2）1/2＋２1/2−１である）に等しい中間値Ｐ6を計算し、
（viii）約Ｆ（５）−ｋ6Ｆ（３）（ここで、ｋ6は約２1/2（２−２1/2）1/2−２1/2＋１である）に等しい中間値Ｐ7を計算し、
（ix）前記中間値Ｐ0、Ｐ2が利用できるようになった後、約Ｐ0＋ｋ7Ｐ2（ここで、ｋ7は約２-1/2（２＋２1/2）1/2である）に等しい中間値Ｑ0を計算し、
（x）前記中間値Ｐ0、Ｐ2が利用できるようになった後、約Ｐ0−ｋ7Ｐ2に等しい中間値Ｑ2を計算し、
（xi）前記中間値Ｐ1、Ｐ3が利用できるようになった後、約Ｐ1＋ｋ8Ｐ3（ここで、ｋ8は約２-1/2（２−２1/2）1/2である）に等しい中間値Ｑ1を計算し、
（xii）前記中間値Ｐ1、Ｐ3が利用できるようになった後、約Ｐ1−ｋ8Ｐ3に等しい中間値Ｑ3を計算し、
（xiii）前記中間値Ｐ4、Ｐ6が利用できるようになった後、約Ｐ4＋ｋ9Ｐ6（ここで、ｋ9は約−（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｑ4を計算し、
（xiv）前記中間値Ｐ4、Ｐ6が利用できるようになった後、約Ｐ4−ｋ9Ｐ6に等しい中間値Ｑ6を計算し、
（xv）前記中間値Ｐ5、Ｐ7が利用できるようになった後、約Ｐ5＋ｋ10Ｐ7（ここで、ｋ10は約（２＋２1/2）1/2＋２1/2＋１である）に等しい中間値Ｑ5を計算し、
（xvi）前記中間値Ｐ5、Ｐ7が利用できるようになった後、約Ｐ5−ｋ10Ｐ7に等しい中間値Ｑ7を計算し、
（xvii）前記中間値Ｑ6、Ｑ7が利用できるようになった後、約Ｑ6＋ｋ3Ｑ7に等しい中間値Ｒ6を計算し、
（xviii）前記中間値Ｑ6、Ｑ7が利用できるようになった後、約Ｑ6−ｋ3Ｑ7に等しい中間値Ｒ7を計算し、
（xix）前記中間値Ｑ0、Ｑ4が利用できるようになった後、約Ｑ0＋ｋ11Ｑ4（ここで、ｋ11は約２-1/2（２＋（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（０）を計算し、
（xx）前記中間値Ｑ0、Ｑ4が利用できるようになった後、約Ｑ0−ｋ11Ｑ4に等しい前記ｆ′（７）を計算し、
（xxi）前記中間値Ｑ1、Ｒ6が利用できるようになった後、約Ｑ1＋ｋ12Ｒ6（ここで、ｋ12は約（１／２）（２＋（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（１）を計算し、
（xxii）前記中間値Ｑ1、Ｒ6が利用できるようになった後、約Ｑ1−ｋ12Ｒ6に等しい前記ｆ′（６）を計算し、
（xxiii）前記中間値Ｑ2、Ｑ5が利用できるようになった後、約Ｑ2＋ｋ13Ｑ5（ここで、ｋ13は約２-1/2（２−（２＋２1/2）1/2）1/2である）に等しい前記ｆ′（３）を計算し、
（xxiv）前記中間値Ｑ2、Ｑ5が利用できるようになった後、約Ｑ2−ｋ13Ｑ5に等しい前記ｆ′（４）を計算し、
（xxv）前記中間値Ｑ3、Ｒ7が利用できるようになった後、約Ｑ3＋ｋ12Ｒ7に等しい前記ｆ′（２）を計算し、
（xxvi）前記中間値Ｑ3、Ｑ7が利用できるようになった後、約Ｑ3−ｋ12Ｒ7に等しい前記ｆ′（５）を計算することを特徴とする装置。
【請求項１１】
請求の範囲第１０項記載の装置において、
段階（i）および（ii）を同時に実施し、
段階（ix）および（x）を同時に実施し、
段階（xi）および（xii）を同時に実施し、
段階（xiii）および（xiv）を同時に実施し、
段階（xv）および（xvi）を同時に実施し、
段階（xvii）および（xviii）を同時に実施し、
段階（xix）および（xx）を同時に実施し、
段階（xxi）および（xxii）を同時に実施し、
段階（xxiii）および（xxiv）を同時に実施し、
段階（xxv）および（xxvi）を同時に実施することを特徴とする装置。
【請求項１２】
請求の範囲第１０項または第１１項記載の装置において、前記中間結果が、その後の少なくとも３つのサイクルが完了するまで使用されないことを特徴とする方法。
【請求項１３】
請求の範囲第１０項または第１１項記載の装置において、前記一次元逆離散余弦変換のうちの８つの各々について、８つのメモリ場所を使用して前記離散余弦変換値Ｆ（０）−Ｆ（７）および前記中間結果を保持することを特徴とする装置。
【請求項１４】
請求の範囲第１０項または第１１項記載の装置において、前記一次元逆離散余弦変換のうちの８つの各々について、８つのメモリ場所を使用して前記中間値および前記逆離散余弦変換値ｆ′（０）−ｆ′（７）を保持することを特徴とする装置。
【請求項１５】
請求の範囲第１０項記載の装置において、前記第１、第３の信号パスがこれらの信号パスを通る信号を実行するためのＸＯＲゲートのセットを包含し、各ＸＯＲゲートが前記コントローラに接続した入力部を有することを特徴とする装置。
【請求項１６】
請求の範囲第１２項記載の装置において、
段階（vii）を段階（i）の後に実行し、
段階（v）を段階（vii）の後に実行し、
段階（iii）を段階（v）の後に実行し、
段階（xiii）を段階（iii）の後に実行し、
段階（xv）を段階（xiii）の後に実行し、
段階（ix）を段階（xv）の後に実行し、
段階（xi）を段階（ix）の後に実行し、
段階（xvii）を段階（xi）の後に実行し、
段階（xix）を段階（xvii）の後に実行し、
段階（xxi）を段階（xix）の後に実行し、
段階（xxv）を段階（xxi）の後に実行し、
段階（xxiii）を段階（xxv）の後に実行することを特徴とする装置。
【請求項１７】
請求の範囲第１１項記載の装置において、前記第１信号パスが前記第３信号パスに接続した入力部を有する減算器を包含することを特徴とする装置。
【請求項１８】
請求の範囲第１０項記載の装置において、前記コントローラが読み出しカウンタおよび書き込みカウンタを包含し、前記メモリ読み出しアドレスが前記読み出しカウンタの出力部の組み合わせ関数であり、前記メモリ書き込みアドレスが前記書き込みカウンタの出力部の組み合わせ関数であることを特徴とする装置。
【請求項１９】
請求の範囲第１８項記載の装置において、前記読み出しカウンタの出力部の前記組み合わせ関数と前記書き込みカウンタの出力部の前記組み合わせ関数が同じであることを特徴とする装置。
【請求項２０】
請求の範囲第１８項記載の装置において、前記読み出しカウンタが、前記読み出しカウンタおよび前記書き込みカウンタが計数を行っている間の前記書き込みカウンタの前方３つのカウントであることを特徴とする装置。
【請求項２１】
請求の範囲第１８項記載の装置において、前記係数ブロックが前記読み出しカウンタに接続してあり、前記書き込みカウンタに接続していないことを特徴とする装置。
【請求項２２】
請求の範囲第１３項記載の装置において、前記一次元逆離散余弦変換のうち８つの各々について、８つのメモリ場所が使用されて前記中間値および前記逆離散余弦変換値ｆ′（０）−ｆ′（７）を保持することを特徴とする装置。
【発明の詳細な説明】
発明の背景
本発明は、全体的には、画像デコンプレッションに関するものであり、一層詳しくは、画像デコンプレッションの一部としての逆離散余弦変換を評価する装置および方法に関するものである。
電子的に伝達あるいは保存しようとしているたいていの画像は、空間周期性および限られた空間的変化の度合いによる空間冗長性を有し、多くの空間周波数成分がゼロに近い。任意のカラー・スペースを用いて表され、おそらくは動き補償され、予測コード化された画像（静止画あるいは動画フレーム）は、周波数変換を行い、その後、量子化を行ない、或る形態のエントロピー・コード化（通常、ハフマン・コード化あるいは算術コード化）を行うことによって圧縮することができる。
８×８二次元離散余弦変換を用いる画像の空間周波数ドメイン描画が標準になってきている。この技術は、たとえば、静止画用のJoint Photographic Experts Group（JPEG）規格、ＰＣベースのマルチメディア・ハンドヘルド・ビデオ・ゲーム用のMotion Picture Experts Group（MPEG）規格ならびにディジタル・ケーブル・テレビジョン用のMPEG2規格で使用されている。画像は、輝度、クロミナンスあるいはモーション・ベクトルのような、（おそらくは予測コード化された）数量で特徴づけられる画素（ピクセル）のアレイとして表される。これらのアレイは８×８のピクセル値ブロックに分割され、各ブロックが水平方向、垂直方向の空間周波数係数の８×８マトリックスに変換される。
こうして得られた係数が量子化されると、高周波係数に対する媒体の大部分がゼロ値を発生する。これらの係数はほぼ空間周波数を高める順序で順序づけられ、シリーズの早期に非ゼロ係数のクラスタを生じさせ、次いで連続的なゼロ値の実行が続く。このようなデータ・ストリームは統計コード化を用いて有意に圧縮され得る。
画像をデコンプレッションするとき、空間周波数係数の各８×８マトリックスは、二次元逆離散余弦変換（ＩＤＣＴ）を実施することによって８×８ピクセル値ブロックに変換される。この二次元ＩＤＣＴは、まず１つのアレイ・ディメンションに沿って、次いで他のアレイ・ディメンションに沿って実施される一次元ＩＤＣＴのカスケードに分離し得る。たとえば、オリジナルのアレイにおける係数の各桁をＩＤＣＴの対応する値に置き換えることができる。次いで、こうして得た値の各行をそのＩＤＣＴで置き換えることによってオリジナルのピクセル値を得ることができる。こうして、８×８二次元ＩＤＣＴを１６個の一次元８次ＩＤＣＴに圧縮することができる。
８次の一次元ＩＤＣＴが画像デコンプレッションで広範囲にわたる、通常はリアルタイムの用途を持つことがわかる。効率の良いインプリメンテーションを創り出すのにかなりの努力が払われてきた。この努力の大部分は、乗算の回数、そして重要性は低いが、加算の回数を減らすことによって遅延を減らすべきであるという組み合わせインプリメンテーションに焦点を合わせていた。加算と乗算の間のトレードオフにより、乗算よりも多い加算を必要とし、非常に大きな全演算回数を必要とする計算が行われることになる。ＩＤＣＴまたは離散余弦変換（ＤＣＴ）についてのこのような計算は、"Practical Fast 1-D IDCT Algorithms with 11 Multiplications", Christoph Loeffler, Adrian Lightenberg and George S. Moschytz, Proceedings of IEEE ICASSP, vol. 2 pp. 988-991, February 1989および"A Fast DCT-SQ Scheme for Images", Yukihiro Arai, Takeshi Agui and Masayuki Nkajima, The Transactions of the IEICE, vol. E71, no. 11, pp. 1095-1097, November 1988に開示されている。
組み合わせインプリメンテーションは速いけれども、演算毎に異なった装置を必要とするため、大量のハードウエアを必要とする。二次元ＩＤＣＴインプリメンテーションは、すべて、桁、行の一次元ＩＤＣＴの間の転位作業のためのメモリを必要とする。このメモリは、また、ＩＤＣＴが適度な量の補助論理と共に逐次論理回路（たとえば、乗算累算）によって演算されるときに中間結果を保持するのにも使用し得る。周知のように、乗算累算は乗算器と加算器とからなり、乗算器の出力部は加算器入力部に接続されている。この安価なハードウェアでは、最速の計算に、せいぜい１つの乗算を行う最少数のステップが必要である。この場合、必要なステップは加算を行うが、乗算は同様に１回の乗算を含むステップについて利点を与える。
融合乗算／加算を行うハードウェア・インプリメンテーションの方法が、"New Scaled DCT Algorithms for Fused Multiply/Add Architectures", Elliot Linzer and Ephraim Feig, Proceedings of the IEEE ICASSP, pp. 2201-2204, 1991に開示されている。しかしながら、この方法でも、また、上述したArai等に開示されている方法でも、いずれもが得る結果は、スケール因数を掛け合わせたＩＤＣＴの結果である。画像処理量子化マトリックスにおいてこれらのスケール因数を説明することはできるが、この技術はソフトウエア・インプリメンテーションでのみ実用的である。ハードウェア・インプリメンテーションでは、付加的な乗算器およびメモリが必要となるであろう。しかしながら、この付加的なハードウェアは、最終スケーリングが２の累乗である場合には、不要である。この場合、結果のビットの桁移動を用いることができる。二次元ＩＤＣＴの結果の最終スケーリングが２の累乗であるためには、一次元ＩＤＣＴの結果が２の累乗の平方根に等しい因数だけオフでなければならない。
したがって、本発明の目的は、スケーリングされていない二次元ＩＤＣＴ演算のためのハードウェアが１つの乗算器しか必要とせず、このＩＣＤＴ演算が従来可能であったよりも少ないステップで実施される画像デコンプレッションのための装置および方法を提供することにある。
本発明の別の目的は、８×８二次元ＩＤＣＴ演算のための簡略化した装置を提供することにある。
本発明の付加的な目的および利点は、以下の説明に記載し、一部この記載から明らかとなるであろうし、あるいは、発明の実施によって学習し得る。本発明の目的および利点は、特に請求の範囲において指摘する手段および組み合わせによって実現され、獲得され得る。
発明の概要
本発明は画像デコンプレッションの方法に向けたものである。圧縮された画像定義ディジタル信号が入力されると、それが信号プロセッサを用いてディジタル処理されて空間的に冗長な画像定義ディジタル信号を発生する。処理ステップは、複数の二次元８ポイント×８ポイントＩＤＣＴの評価を行うステップを含む。各評価は、２の累乗の平方根に等しい因数でスケーリングしたスケーリング済み８ポイント一次元ＩＤＣＴの１６回の評価を含む。スケーリング済みの一次元ＩＤＣＴの評価を行った後、その結果を上記の２の累乗に等しいビット数分だけ桁移動する。ディスプレイをレンダリングする際に使用するために空間的に冗長な画像定義ディジタル信号が出力される。
出発点の一次元離散余弦変換（ＤＣＴ）値がＦ（０）−Ｆ（７）であり、スケーリングした一次元ＩＤＣＴ値がｆ′（０）−ｆ′（７）である場合、スケーリングした一次元ＩＤＣＴ計算は次のように行われる。特に、以下の値が計算される。すなわち、約Ｆ（０）＋Ｆ（４）に等しい中間値Ｐ0、約Ｆ（０）−Ｆ（４）に等しい中間値Ｐ1、約Ｆ（２）＋ｋ1Ｆ1Ｆ（６）に等しい中間値Ｐ2（ここで、ｋ1は約２1/2−１である）、約Ｆ（２）−ｋ2Ｆ（６）に等しい中間値Ｐ3（ここで、ｋ2は約２1/2＋１である）、約Ｆ（１）＋ｋ3Ｆ（７）に等しい中間値Ｐ4（ここで、ｋ3は約２1/2（２＋２1/2）1/2−２1/2−１である）、約Ｆ（１）＋ｋ4Ｆ（７）に等しい中間値Ｐ5（ここで、ｋ4は約２1/2（２＋２1/2）1/2＋２1/2＋１である）、約Ｆ（５）＋ｋ5Ｆ（３）に等しい中間値Ｐ6（ここで、ｋ5は約２1/2（２−２1/2）1/2＋２1/2−１である）、約Ｆ（５）−ｋ6Ｆ（３）に等しい中間値Ｐ7（ここで、ｋ6は約２1/2（２−２1/2）1/2−２1/2＋１である）、約Ｐ0＋ｋ7Ｐ2に等しい中間値Ｑ0（ここで、ｋ7は約２-1/2（２＋２1/2）1/2である）、約Ｐ0−ｋ7Ｐ2に等しい中間値Ｑ2、約Ｐ1＋ｋ8Ｐ3に等しい中間値Ｑ1（ここで、ｋ8は約２-1/2（２−２1/2）1/2である）、約Ｐ1−ｋ8Ｐ3に等しい中間値Ｑ3、約Ｐ4＋ｋ9Ｐ6に等しい中間値Ｑ4（ここで、ｋ9は約−（２＋２1/2）1/2＋２1/2＋１である）、約Ｐ4−ｋ9Ｐ6に等しい中間値Ｑ6、約Ｐ5＋ｋ10Ｐ7に等しい中間値Ｑ5（ここで、ｋ10は約（２＋２1/2）1/2＋２1/2＋１である）、約Ｐ5−ｋ10Ｐ7に等しい中間値Ｑ7、約Ｑ6−ｋ3Ｑ7に等しい中間値Ｒ6、約Ｑ0＋ｋ11Ｑ4に等しい値ｆ′（０）（ここで、ｋ11は約２-1/2（２＋（２＋２1/2）1/2）1/2である）、約Ｑ0−ｋ11Ｑ4に等しい値ｆ′（７）、約Ｑ1＋ｋ12Ｒ6に等しい値ｆ′（１）（ここで、ｋ12は約１／２（２＋（２＋２1/2）1/2）1/2である）、約Ｑ1−ｋ12Ｒ6に等しい値ｆ′（６）、約Ｑ2＋ｋ13Ｑ5に等しい値ｆ′（３）（ここで、ｋ13は約２-1/2（２−（２＋２1/2）1/2）1/2である）、約Ｑ2−ｋ13Ｑ5に等しい値ｆ′（４）、約Ｑ3＋ｋ12Ｒ7に等しい値ｆ′（２）および約Ｑ3−ｋ12Ｒ7に等しい値ｆ′（５）である。
本発明の装置は、第１入力部、第２入力部および出力部を有するバタフライ演算サブシステムを包含する。メモリが書き込みポートと読み出しポートを有し、この書き込みポートが第１シングルパスによってバタフライ演算サブシステムの出力部に接続してある。この装置は、また、第１、第２の入力部を有するマルチプレクサと、第２シングルパスによってバタフライ演算サブシステムの第１入力部に接続した出力部も包含する。第２シングルパスがメモリの読み出しポートをマルチプレクサの第１入力部に接続している。コントローラがメモリに読み出し、書き込みアドレスおよび書き込み許可信号を与える。このコントローラは、また、マルチプレクサを制御し、係数値をバタフライ演算サブシステムの第２入力部に供給して、上記の段落で説明したようなスケーリングした８ポイント一次元逆離散余弦変換を含む二次元の８ポイント×８ポイントＩＤＣＴを演算する。
【図面の簡単な説明】
添付図面（本明細書に添付されてその一部をなし、また、同様の参照符号が同様の構成要素を示す）は、本発明の好ましい実施例を概略的に示しており、上記の全般的な説明ならびに以下に行う好ましい実施例の詳細な説明と共に、本発明の原理を説明するのに役立つ。
第１図は、本発明によるスケーリングした一次元ＩＤＣＴ計算の流れ図である。
第２図は、本発明に従ってＩＤＣＴを計算する装置のブロック図である。
第３図は、本発明に従ってＩＤＣＴの計算を行う装置の詳細なブロック図である。
第４図は、第３図のアドレス生成ブロック６２、７０のブロック図である。
第５図は、本発明に従ってＩＤＣＴを計算するより速い装置の詳細なブロック図である。
好ましい実施例の説明
以下、本発明をいくつかの好ましい実施例によって説明する。これらの好ましい実施例はＩＤＣＴを決定する装置および方法である。本発明によるスケーリングした一次元ＩＤＣＴを決定するフローグラフ１０が第１図に示してある。
第１図は１３のバタフライを示している。周知のように、１つのバタフライは２つの数量を決定する。これらの数量は共に２つの他の既知の数量の一次結合であり、この同じ既知の数量が決定されつつある数量の両方についてのものである。たとえば、バタフライ・ステップ１２（仮想線の矩形ボックスで囲んである）は、数量Ｐ4＝Ｆ（１）＋ｋ3Ｆ（７）、Ｐ5＝Ｆ（１）−ｋ4Ｆ（７）の決定からなる。第１図の１３つのバタフライのうち１つのバタフライ（Ｐ0、Ｐ1対の決定）は１つの加算と１つの減算を有し、９つのバタフライは１つの乗算、１つの加算および１つの減算を有する（Ｑ0、Ｑ2対、Ｑ1、Ｑ3対、Ｑ4、Ｑ6対、Ｑ5、Ｑ7対、Ｒ6、Ｒ7対、ｆ′（０）、ｆ′（７）対、ｆ′（１）、ｆ′（６）対、ｆ′（３）、ｆ′（４）対およびｆ′（２）、ｆ′（５）対の決定）。そして、２つの乗算、１つの加算、１つの減算を持つ３つのバタフライがある（バタフライ１２およびＰ2、Ｐ3対、Ｐ6、Ｐ7対の決定）。最後の３つのバタフライの各々は第２カテゴリの２つのバタフライに分解することができる。すなわち、１つの乗算、１つの加算、１つの減算を有するバタフライに分解できる。バタフライがせいぜい１つの乗算ステップに限られている場合、第１図の方法は１６のこのようなバタフライを必要とする。したがって、二次元（２Ｄ）ＩＤＣＴの演算には、１６×１６＝２５６個のバタフライが必要であり、各バタフライが１つの乗算、１つの加算、１つの減算を持たなければならない。
乗算がフローグラフのいくつかの領域に集中する他のＩＤＣＴ決定と異なり、本発明の方法は、すべての計算（バタフライ）がほぼ同じ複雑さであり、それらがフローグラフ全体に分布しているという利点を与える。ハードウェア・インプリメンテーションの場合、これは同じタイプの演算を常に行う演算装置を持つ簡単なデータパスで生じる。ハードウェアの構成要素はほとんど同時に用いることができ、無駄は少しである。したがって、この方法の使用は非常に小さくて効率の良いＩＤＣＴインプリメンテーションに通じ得る。
第２図に示すように、本発明のＩＤＣＴ決定装置１３は、コントローラ２２、マルチプレクサ１４、バタフライ演算サブシステム１６、メモリ１８を包含する。コントローラ２２は、マルチプレクサ１４、メモリ１８、バタフライ演算サブシステム１６を制御し、信号ＫＯＵＴを用いてバタフライ演算サブシステム１６にｋ係数を与える。マルチプレクサ１４は、バタフライ演算サブシステム１６に接続した出力部と、ＩＤＣＴ決定システム１３の入力部として作用する入力部と、メモリ１８の読み出しポートに接続した入力部とを有する。バタフライ演算サブシステム１６は、ＩＤＣＴ決定システム１３の出力部として作用する出力部と、メモリ１８の書き込みポートに接続した別の出力部とを有する。上述したように、メモリは桁、行ＩＤＣＴ間の転位演算のための任意の二次元ＩＤＣＴインプリメンテーションで要求される。以下に説明するように、本発明のインプリメンテーションにおいては、転移演算はマルチプレクサによって行われる行・桁アドレス交換に変えることができる。本発明において、一次元（１Ｄ）ＩＤＣＴはまず桁について、次いで行について演算されると好ましい。こうすれば、ＩＤＣＴ出力部が１桁ずつではなくて１行ずつとなり、ＩＤＣＴ決定システム１３の出力部に接続した画像デコンプレッサ（図示せず）の他の機能ユニットに対するインターフェイスが簡単になる。同じメモリ１８を、バタフライ結果を保存する８つのレジスタの一時的な記憶のためにも使用できる。本発明のＩＤＣＴインプリメンテーションは簡単な構造を有し、データフローが非常に局限される。このことは、付加的なシリコン領域保存としても考慮できる非常に簡単なレイアウトに通じる。
バタフライ入力部に割り当てられた１２のビット（第２図においてマルチプレクサ１４によって供給される２つの初期値）とバタフライ入力部に割り当てられた９のビット（第２図においてバタフライ演算サブシステム１６の出力する２つの最終値）を仮定すると、バタフライ出力部のすべての値がレンジ〔−１０４５６、１０４５６〕内にあるのがわかる。広範囲のシミュレーションの後、精度とデータパス幅の間の最良の妥協は、メモリ１８については１６ビット、ｋ係数については１３ビットであることがわかった（第２図の信号ＫＯＵＴ）。１２ビット入力は位置１つ分左へシフトされる。その結果、すべてのバタフライ出力がレンジ〔−２０９１２、２０９１２〕になり、すべてのデータ（入力、中間結果、出力）を１６ビット整数で表すことができる。最終出力は位置４分右へシフトされなければならない。１つは入力シフティングのためであり、３つはこの方法で必要とされるスケーリングのためである。１３ビットｋ係数（ｋ［１］ないしｋ［１３］）の１０進浮動小数点、１６進不動点、２進不動点の標示が以下の表１に示してある。表１において、最後の桁は、コントローラ２２のｋブロックの説明のために後に使用する。
0003857308.tif 000002
８×８逆離散余弦変換のインプリメンテーションのためのＩＥＥＥ規格仕様（IEEE Std 1180-1990, December 6, 1990）に従って演算した、上記のようなＩＤＣＴインプリメンテーションについての丸みエラーは表２の第２桁に示してある。表２において、第３の桁はエラーについてのＩＥＥＥ推奨基準を与えている。
0003857308.tif 000003
本発明による２つの特別のＩＤＣＴインプリメンテーションの説明は以下の通りである。最初のもの１３ａ（第３図）はＰｘ６４、ＭＰＥＧ１のようなローエンドタイプ用途のためのものであり、第２のもの１３ｂ（第５図）はディジタルＴＶ（ＭＰＥＧ２メインレベル）のような媒体複雑性用途のためのものである。これら２つのインプリメンテーションの主要な差異は、バタフライ計算を実行する方法にある。
Ｐｘ６４またはＭＰＥＧ１ソース入力フォーマット（ＳＩＦ）解像度（３５２×２４０×３０フレームあるいは３５２×２８８×２５フレーム）の場合、１秒で演算すべきＩＤＣＴは59,400ある。３３ＭＨｚの妥当なクロック速度の場合、８×８ブロックの二次元ＩＤＣＴを演算するのに利用できるサイクルは約５１２ある。このことは、１つのバタフライを演算するのに２つのサイクルがあることを意味する。これは、２サイクル乗算器で、次いで、一方のサイクルが加算し、他方のサイクルが減算する加算器によって行い得る。しかしながら、シングルサイクル乗算累算（ＭＡＣ）を用いると、インプリメンテーションを簡単にするばかりでなく、全体ゲート・カウントを低減する。ＭＡＣは１サイクルが乗算−加算を行い、他方のサイクルが乗算−減算を行うのに用いられる。乗算−減算は次のようにして乗算−加算演算を用いることができる。
0003857308.tif 000004
ここで、
0003857308.tif 000005
はａの１の補数である。このインプリメンテーションのブロック図が第３図に示してある。
データパスは一時に１つのデータ値を運ぶことができるような１６ビット幅である。メモリ１８ａ（第２図のメモリ１８の或る特別の実施例）はディアルポート式（１つが読み出しポート１９ａで、１つが書き込みポート２１ａである）であり、６４個の１６ビット記憶場所を有し、アドレスの３つの最下位ビットが桁を指定し、次の３つのビットが行を指定する。k係数はレジスタ（ＲＥＧｋ）２４に保持されている。このレジスタの出力部はＭＡＣ２６の乗算器入力部に接続している。マルチプレクサ１４ａ（第２図のマルチプレクサ１４の或る特別な実施例９の１つの入力部が画像デコンプレッサ（図示せず）から入力信号２８を受け取り、マルチプレクサ１４ａの他方の入力部はメモリ１８ａに接続してある。マルチプレクサ１４ａの出力はレジスタ３０（ＲＥＧ１）、３０（ＲＥＧ０）に送られる。レジスタ３０の出力部はＭＡＣ２６の他方の乗算器入力部に接続してある。レジスタ３２の出力は、１セットのＸＯＲゲート３４を介して、レジスタ３６（ＲＥＧ２）に送られる。レジスタ３６の出力部はＭＡＣ２６の加算器入力部に接続してある。ＭＡＣ２６の出力はレジスタ３８（ＲＥＧ３）に送られる。レジスタ３８の出力は別セットのＸＯＲゲート４０を通り、メモリ１８ａの書き込みポートおよびラウンド・シフト・リミット要素４２に送られる。セットになったＸＯＲゲート３４、４０は式（１）の１の補数演算を行う。
ラウンド・シフト・リミット要素４２は上述したように位置４つ分だけその入力を右シフトする。シフティングの後、正数については８を加え、負数については７を加えることによって不偏ラウンディングを行う。結果を右シフトし、〔−２５６、２５５〕間隔に制限する。こうして得た出力はシステム１３ａの出力である。このロジックは２２０個のトランジスタを採用する。
ＭＡＣ２６はｋ係数（二進（基数）点の前では３、後では１０）についての１３ビットの符号のない入力と、２つの１６ビットの符号付き入力とを有する。たいていの場合、レジスタ３８へのＭＡＣ出力は２９ビット符号付きである（二進点前で１９、後で１０）。すべてのバタフライ出力がレンジ〔−２０９１２、２０９１２〕内にあるため、３つの最上位ビットは落とされる可能性がある。これはこれらのビットが４番目の最上位ビットに常に等しいからである。１０個の最下位ビット（二進点の後のビット）も、すべての結果に０．５を加えることによって単純なラウンディングが行われた場合、落とされる可能性がある。１３個のビットを落とすということは、ＭＡＣ構造をかなり簡単にする。この技術分野で周知のように、モディファイされたBoothアルゴリズムを用いると、８つの部分積を加算しなければならない（ｋ係数から７つ、累算から１つ）。各ビットについて３つの４：２：２コンプレッサを使用するのが最も簡単である。符号エクステンションのための「符号発生」法を用いると、５７個のコンプレッサが必要なだけである。このうち３５個は実際に４：２コンプレッサである。残りの２２個は３：２コンプレッサ（全加算器）のような簡略化バージョンであり、あるいはそれよりさらに簡単である。これらすべての最適化処理の故に、ＭＡＣインプリメンテーションが必要とするトランジスタは５４００個未満である。
レジスタ２４、３０、３２、３６、３８、ＭＡＣ２６、ＸＯＲゲート３４、４０およびラウンド・シフト・リミット要素４２は、第２図のバタフライ演算サブシステム１６の実施例１６ａを形成する。
データパスの他に、小形のコントローラ２２ａ（第２図のコントローラ２２の或る特別の実施例である）が、アドレスＲＤＡＤＲ４４、ＷＲＡＤＲ４６を駆動し、信号４８を用いて駆動されるｋブロック２０を用いるｋ係数を与え、出力制御信号ＱＲＤ  ５０、ＳＵＢ０  ５２、ＳＵＢ１  ５４、メモリ書き込み許可信号ＷＥ  ５６、レジスタＲＥＧ０  ３２、ＲＥＧ１  ３０についてのレジスタ許可信号ＲＥＧ１ＥＮ  ５５、ＲＥＧ０ＥＮ  ５７を提供するのに、必要である。コントローラ２２ａは出力信号ＷＲＣＮＴ  ６０を持つ９ビット書き込みカウンタ５８を包含する。出力信号ＷＲＣＮＴ  ６０は、以下により詳しく説明するようにアドレスＷＲＡＤＲ  ４６を発生する組み合わせロジック６２に送られる。出力信号ＷＲＣＴ  ６０の５つの最下位ビットＷＲＣＮＴ〔４：０〕は、書き込み許可信号５６を発生する組み合わせロジック６４にも送られる。ロジック６４についての真理値表が表３の桁ＷＲＣＮＴ、ＷＥによって示してある。信号ＳＵＢ１  ５４はＷＲＣＮＴ６０の最下位ビットである。
0003857308.tif 000006
コントローラ２２ａは出力信号ＲＤＣＮＴ  ６８を持つ９ビット読み出しカウンタも包含する。出力信号ＲＤＣＮＴ  ６６は組み合わせロジック７０に付与される。この組み合わせロジック７０は、好ましい実施例では、後述するようにロジック６２と機能上均等であり、アドレス信号ＲＤＡＤＲ  ４４を発生する。信号ＳＵＢ０  ５２はインバータ７２によって反転された信号ＲＤＣＮＴ  ６８の最下位ビットである。信号ＱＲＤ  ５０は組み合わせロジック７４によって発生させられ、心号ＲＤＣＮＴ  ６８の最上位ビットおよび５つの最下位ビットの関数である。ＲＤＣＮＴ〔８〕が１であるとき、信号ＱＲＤは常にゼロである。さもなければ、信号ＲＣＤＮＴ〔４：０〕の関数としてのその真理値表は表３の桁ＲＤＣＮＴ、ＩＮＰＵＴで与えられる。ここで、ＩＮＰＵＴ桁が空白でないときにはいつでも信号ＱＲＤは１である。ｋブロック２０への入力信号４８はＲＤＣＮＴ〔４：０〕に依存する４ビット入力である。表３からわかるように、信号ＫＯＵＴは、信号ＲＤＣＮＴが或る奇数から次のより高い数に変化するので同じに留まる。こうして、ｋブロック２０への入力４８は、単にＲＤＣＮＴ〔４：０〕を減分し、最下位ビットを廃棄することだけで組み合わせロジック７６によって合成され得る。ｋブロック２０の真理値表は、表１の桁「binary-fixed point」、「(RDCNT-1)〔４：１〕」によって与えられる。信号ＲＥＧ０ＥＮ  ５７はＲＤＣＮＴ〔４：０〕の関数であり、組み合わせロジック７８によって発生させられる。ロジック７８の真理値表は、表３の桁ＲＣＤＮＴ、ＲＥＧ０によって与えられる。ＲＥＧ０ＥＮは、ＲＥＧ０桁が空白あるいは二重引用符を含むときには０であり、そうでない場合には１である。信号ＲＥＧ１ＥＮ  ５５はＲＤＣＮＴ〔４：０〕の関数であり、組み合わせロジック８０で発生する。ロジック７８の真理値表は表３の桁ＲＤＣＮＴ、ＲＥＧ１によって与えられる。ＲＥＧ１桁が空白はるいは二重引用符を含んでいる場合には、ＲＥＧ１ＥＮは０であり、そうでなければ１である。
ｋブロックは読み出し専用メモリ（ＲＯＭ）であってはならない。４ビット入力（係数インデックス）および１３ビット出力（ｋ係数）を備えた組み合わせブロックは２０４個のトランジスタで具体化できる。
ＩＮＰＵＴ信号２８は、通常、画像デコンプレッサのランダムアクセス・メモリ（ＲＡＭ）からのものであり、逆量子化器によって発生させられる。信号ＲＤＡＤＲ  ４４は、ＲＡＭをアドレス指定するのに用いることができ、したがって、入力は表３の桁ＩＮＰＵＴに示す順序で到達する。ここで、二次下付き文字は処理されつつある桁のインデックスを示している。ＲＤＭＥＮ信号８２はマルチプレクサ１４ａに付与されるメモリ１８ａの出力である。
二次元ＩＤＣＴは、それぞれ３２サイクルで演算される１６個の一次元ＩＤＣＴからなる。表３は、制御信号を以下にして駆動し、どんな信号が第１の一次元ＩＤＣＴ（８×８マトリックスの第１桁ＩＤＣＴ）のための出力となるかを示している。ここで使用する表記法は第１図のフローグラフでのものと同じである。第２の下付き文字が第１マトリックス桁が処理されつつあることを示すために加えてある。他のマトリックス桁の場合、第２の下付き文字はマトリックス桁のインデックスであり、ＲＤＣＮＴおよびＷＲＣＮＴはマトリックス桁のインデックスの３２倍に等しい量だけ高くなっており、ＲＤＡＤＲおよびＷＲＡＲＤは下記のロジック６２、７０によって与えられる。マトリックス行が処理されるときには、マルチプレクサ１４ａがＩＮＰＵＴの代わりに信号ＲＤＭＥＭを選ぶ。信号ＲＤＭＥＭは先に行われたマトリックス桁処理と信号ＲＤＡＤＲによって決定される。信号ＲＤＡＤＲおよびＷＲＡＤＲも下記のロジック６２、７０によって決定される。所与のインデックスのマトリックス行が処理されるときには、ＲＤＣＮＴ、ＷＲＣＮＴは、同じインデックスのマトリックス桁が処理されていた場合よりも２５６だけ高くなる。
２つのカウンタ５８、６６を使用することにより、ＩＤＣＴコントローラはかなり簡略化される。ＩＤＣＴパイプラインはこれらのカウンタを単に使用禁止にするだけで任意の段階で停止することができる。
メモリがバタフライ中間結果の一時的な記憶装置としても使用されるため、バタフライ使用順序には多くの制約がある。その内の最大の制約は、バタフライ演算が開始された後、新しいバタフライを演算するのに結果を使用できるようになるまでに少なくとも３つのサイクルが必要であるということである。選んだ順序（表３のＲＥＧ３桁）はこれらの制約のすべてを解決し、それに加えて、制御ロジックを簡略化する（ＷＲＡＤＲロジック６２はＲＤＡＤＲロジック７０と同じであり、ｋ係数シーケンスはｋブロック２０を簡略化し、ＳＵＢ０およびＳＵＢ１はＲＤＣＮＴ〔０〕の補数である）。
最初の８つのマトリックス桁ＩＤＣＴは１桁ずつ０から７まで演算される。表３の最後の８つのテーブル行、テーブル桁ＷＲＡＤＲ、ＲＥＧ３を見るとわ刈るように、一次元ＩＤＣＴの結果が或る特殊な順序で書き込まれる。次の８つのマトリックス行ＩＤＣＴは、マトリックス行アドレス（ＲＤＡＤＲ〔５：３〕、ＷＲＡＤＲ〔５：３〕）として、この特殊な順序を使用し、マトリックス桁アドレス（ＲＤＡＤＲ〔２：０〕、ＷＲＡＤＲ〔２：０〕）のためには、先行マトリックス行アドレス（転位演算）を使用する。これはかなり複雑となるが、アドレス生成は非常に簡単である。第４図はそれをどう行うかを示している。
第４図（第３図の組み合わせロジック６２、７０のアドレス生成ロジックを示している）において、ＣＮＴ〔９：１〕は、読み出しカウンタ６６または書き込みカウンタ５８のうちいずれかの出力となり得るカウンタ出力である。アドレス生成ロジックは１つのＯＲゲート８８、２つのＸＯＲゲート９０、９２、マルチプレクサ８６、アドレス・ユニット８４を包含する。アドレス・ユニット８４は、表３からの桁ＲＤＡＤＲまたはＷＲＡＤＲの３つの最下位ビットを生成する単純な組み合わせ回路である。これは約１８０個のトランジスタを採用している。２つの９ビット・カウンタを含むＩＤＣＴコントローラ全体では６７４個のトランジスタを採用している。
表４はＩＤＣＴの異なったサブシステム・ブロックについて用いるトランジスタの数を示している。本発明による二次元ＩＤＣＴ全体は、ほんの1,255個のセル・ゲートとフリップフロップ（約9,000個のトランジスタ）を用いて実現している。これはこれまで具現された最も簡単なＩＤＣＴ（ＭＰＥＧ１速度）よりもはるかに簡単である。
0003857308.tif 000007
ＭＰＥＧ２主レベル解像度（７２０×４８０×２５フレーム）の場合、１秒で演算されるべきＩＤＣＴは243,000ある。６６ＭＨｚのクロック速度を仮定すると、８×８ブロックの二次元ＩＤＣＴを演算するのに利用できるサイクルは約２５６である。このことは、１つのバタフライを演算するサイクルが１つであることを意味する。これは、第５図に示すようにＭＡＣ２６、減算器９８ならびにコントローラ（図示せず）を備えたシステム１３ｂで実行できる。演算すべき演算式はａ＋ｋｂ、ａ−ｋｂである。第２の演算式は２ａ−（ａ＋ｋｂ）として書き込むことができる。記号２ａはａを１ビット分左へシフトすることによって得ることができる。
減算を実施する方法が異なっているために、第２図のバタフライ演算サブシステム１６の異なった実施例１６ｂを用いる。ＸＯＲゲート３４、４０およびレジスタ１２（第３図）のセットは除いてあり、減算器９８、レジスタ９６（ＲＥＧ４）、１００（ＲＥＧ５）が加えてある。レジスタ３６の出力部とレジスタ９６の入力部の間では、シフト・ブロック９４で示すようにデータは１ビットだけ左シフトされる。周知のように、これは、相互接続によって達成され、なんらロジック要素を必要としない。ここでわかるように、ＭＰＥＧ２主レベルのためのＩＤＣＴはＭＰＥＧ１のためのＩＤＣＴよりもほんの少し大きいだけである。この理由は、ＭＰＥＧ１では、ＭＡＣが繰り返し乗算のためにほとんど利用されないからである（ＭＡＣは約５０％の時間だけ非冗長的に使用される）。ＭＰＥＧ２ＩＤＣＴは付加的な１６ビット・レジスタと１６ビット減算器を有する。制御は、先の実施例とほとんど同じであり、その教示から当業者であれば容易に導き出すことができる。重要な差異は、読み出しポート１９ｂと書き込みポート２１ｂを備えたメモリ１８ｂであり、ここでは、より大きなバンド幅のために、６４×１６の代わりに３２×３２で構成してある。２つのデータ値が今や同時にメモリに書き込まれている。中間結果は１時に１つずつ読み出され、マルチプレクサ１４ｂが１つの記憶場所に格納される２つの値のうちどれを読み出すべきかを選定する。全トランジスタ数は約10,000である。これは、かつて具現された最も簡単なＩＤＣＴ（ＭＰＥＧ２主レベル速度）よりもはるかに簡単である。
要約すると、画像デコンプレッションのための逆離散余弦変換の計算のための装置および方法を説明してきた。この装置は、ＭＰＥＧ２主レベル速度の場合には約10,000個のトランジスタで具現でき、ＭＰＥＧ１主レベル速度の場合には10,000未満のトランジスタで具現できる。インプリメンテーションのチップ面積、電力消費量は最小限であり、こうしてできたデコーダは任意用途の特殊な集積回路（ＡＳＩＣ）に埋め込むことができる。
本発明を好ましい実施例によって説明してきたが、本発明はここに図示し、説明した実施例に限定されるものではない。むしろ、発明の範囲は添付の請求の範囲に定義されているものである。
【図１】
0003857308.tif 000008
【図２】
0003857308.tif 000009
【図３】
0003857308.tif 000010
【図４】
0003857308.tif 000011
【図５】
0003857308.tif 000012