KR20110034603A

KR20110034603A - 스케일링 인터페이스 및 넌-스케일링 인터페이스를 갖는 변환 디자인

Info

Publication number: KR20110034603A
Application number: KR1020107028658A
Authority: KR
Inventors: 유리 레즈닉; 앨버트 스콧 루드윈; 혁준 정; 해리나스 가루대드리; 나빈 비 스리니바사무르티; 품 사게통
Original assignee: 퀄컴 인코포레이티드
Priority date: 2006-03-29
Filing date: 2007-03-29
Publication date: 2011-04-05
Anticipated expiration: 2027-03-29
Also published as: JP2009534723A; KR101131757B1; KR20080107474A; WO2007115127A3; US8849884B2; JP2012105273A; US20070233764A1; CA2644505A1; WO2007115127A2; KR101136770B1; US9727530B2; RU2008142735A; RU2460129C2; JP5529101B2; BRPI0709263A2; EP1999642B1; CN101796506A; EP1999642A2; US20140149478A1; CN101796506B

Abstract

풀 인터페이스 및 스케일링 인터페이스를 통해 수신된 데이터 각각에 대해 풀 변환 및 스케일링 변환을 효율적으로 수행하기 위한 기술이 본 명세서에 기재되어 있다. 풀 변환은, 변환의 완전한 수학적 설명을 구현하는 변환이다. 풀 변환은 풀 변환 계수 (또는 단순히 변환 계수) 를 제공하거나 이 풀 변환 계수에 대해 연산한다. 또한, 풀 변환은 넌-스케일링 변환, 완전 변환 등으로 언급될 수도 있다. 스케일링 변환은, 스케일링 변환 계수를 제공하거나 이 스케일링 변환 계수에 대해 연산하는 변환이고, 이 스케일링 변환 계수는 풀 변환 계수의 스케일링 버전이다. 스케일링 변환은 보다 낮은 계산 복잡도를 가질 수도 있고, 스케일링 변환 계수를 수락할 수 있는 애플리케이션에 의해 이용될 수도 있다. 풀 변환은, 풀 변환 계수를 교환하기를 희망하는 애플리케이션에 의해 이용될 수도 있다. 풀 변환 및 스케일링 변환은 2-차원 (2D) IDCT 에 대한 변환일 수도 있고, 이 2D IDCT 는 분리가능한 방식으로 1-차원 (1D) IDCT 로 구현될 수도 있다. 또한, 풀 변환 및 스케일링 변환은 2D DCT 에 대한 변환일 수도 있고, 이 2D DCT 는 분리가능한 방식으로 1D DCT 로 구현될 수도 있다. 후술되는 바와 같이, 1D IDCT 및 1D DCT 는 계산 효율적인 방식으로 구현될 수도 있다.

Description

스케일링 인터페이스 및 넌-스케일링 인터페이스를 갖는 변환 디자인{TRANSFORM DESIGN WITH SCALED AND NON-SCALED INTERFACES}

본 출원은, 2006 년 3 월 29 일자로 출원되었으며, 발명의 명칭이 "CONVERGENCE OF SCALED AND NON-SCALED IDCT ARCHITECTURES" 인 미국가출원 제 60/787,562 호에 대해 우선권을 주장하는데, 이는 본원의 양수인에게 양도되었으며, 본 명세서에 참조로서 포함되어 있다.

본 개시물은 일반적으로 처리에 관한 것이고, 보다 상세하게는 데이터에 대해 변환을 수행하는 기술에 관한 것이다.

변환은 데이터를 하나의 도메인으로부터 또다른 도메인으로 변환하는데 일반적으로 이용된다. 예를 들어, 이산 코사인 변환 (DCT) 은 데이터를 공간 도메인으로부터 주파수 도메인으로 변환하는데 일반적으로 이용되고, 역이산 코사인 변환 (IDCT) 은 데이터를 주파수 도메인으로부터 공간 도메인으로 변환하는데 일반적으로 이용된다. DCT 는 이미지/비디오 압축에 광범위하게 이용되어, 이미지 또는 비디오 프레임에서 화소 (픽셀) 블록을 공간적으로 역상관시킨다. 통상적으로, 그 결과로서 생기는 변환 계수는 서로에 대해 훨씬 덜 종속적이고, 이는 이들 계수로 하여금 양자화 및 인코딩에 보다 적합하게 한다. 또한, DCT 는 에너지 압축 특성을 나타내는데, 이는 픽셀 블록의 대부분의 에너지를 단지 소수의 (통상적으로, 저차) 변환 계수로 매핑하는 능력이다. 이 에너지 압축 특성은 인코딩 알고리즘의 디자인을 단순화할 수 있다.

DCT 및 IDCT 와 같은 변환은, 상이한 이미지 및 비디오 코딩 표준을 지원할 수도 있는 각종 애플리케이션에 이용될 수도 있다. 그에 따라, 데이터를 수신하여, 이 데이터를 이들 애플리케이션에 적합한 포맷으로 제공할 수 있는 인터페이스를 제공하는 것이 바람직하다. 또한, 변환이 대량의 데이터에 대해 수행될 수도 있기 때문에, 가능한 한 효율적으로 변환을 수행하는 것이 바람직하다.

풀 인터페이스 (full interface) 및 스케일링 인터페이스 (scaled interface) 를 통해 수신된 데이터 각각에 대해 풀 변환 (full transform) 및 스케일링 변환 (scaled transform) 을 효율적으로 수행하기 위한 기술이 본 명세서에 기재되어 있다. 풀 변환은, 변환의 완전한 수학적 설명을 구현하는 변환이다. 풀 변환은 풀 변환 계수 (또는 단순히 변환 계수) 를 제공하거나, 이 풀 변환 계수에 대해 연산한다. 또한, 풀 변환은 넌-스케일링 변환 (non-scaled transform), 완전 변환 등으로 언급될 수도 있다. 스케일링 변환은, 스케일링 변환 계수를 제공하거나, 이 스케일링 변환 계수에 대해 연산하는 변환이고, 이 스케일링 변환 계수는 풀 변환 계수의 스케일링 버전이다. 스케일링 변환은 보다 낮은 계산 복잡도를 가질 수도 있고, 스케일링 변환 계수를 수락할 수 있는 애플리케이션에 의해 이용될 수도 있다. 풀 변환은, 풀 변환 계수를 교환하기를 희망하는 애플리케이션에 의해 이용될 수도 있다. 풀 변환 및 스케일링 변환은 2-차원 (2D) IDCT 에 대한 변환일 수도 있고, 이 2D IDCT 는 분리가능한 방식으로 1-차원 (1D) IDCT 로 구현될 수도 있다. 또한, 풀 변환 및 스케일링 변환은 2D DCT 에 대한 변환일 수도 있고, 이 2D DCT 는 분리가능한 방식으로 1D DCT 로 구현될 수도 있다. 후술되는 바와 같이, 1D IDCT 및 1D DCT 는 계산 효율적인 방식으로 구현될 수도 있다.

이하, 본 개시물의 각종 양태 및 특징이 보다 상세하게 설명된다.

본 명세서에 기재된 기술은, DCT, IDCT, 이산 푸리에 변환 (DFT), 역 DFT (IDFT), MLT (Modulated Lapped Transform), 역 MLT, MCLT (Modulated Complex Lapped Transform), 역 MCLT 등과 같은 각종 타입의 변환에 이용될 수도 있다. 또한, 이들 기술은, 이미지, 비디오, 및 오디오 처리, 통신, 컴퓨팅, 데이터 네트워킹, 데이터 저장, 그래픽 등과 같은 각종 애플리케이션에 이용될 수도 있다. 일반적으로, 이들 기술은 변환을 이용하는 임의의 애플리케이션에 이용될 수도 있다. 명쾌함을 위해, 이들 기술은, 이미지 및 비디오 처리에 일반적으로 이용되는 DCT 및 IDCT 에 대해 후술된다.

본 명세서에 기재된 기술은 각종 타입의 장치에서 구현될 수도 있다. 예를 들어, 이들 기술은, 상이한 타입의 프로세서, 상이한 타입의 집적 회로, 상이한 타입의 전자 디바이스, 상이한 타입의 전자 회로 등에서 구현될 수도 있다.

본 발명이 속하는 기술분야에서 통상의 지식을 가진 자라면, 정보 및 신호가 임의의 각종 상이한 기술 및 기법을 이용하여 표현될 수도 있다는 것을 이해할 것이다. 예를 들어, 전술한 설명 전체에 걸쳐 참조될 수도 있는 데이터, 명령들, 커맨드, 정보, 신호, 비트, 심볼, 및 칩은, 전압, 전류, 전자파, 자계 또는 자기 입자, 광학계 또는 광학 입자, 또는 이들의 임의의 조합으로 표현될 수도 있다.

또한, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자라면, 본 개시물과 관련하여 기재된 각종 예시적인 논리 블록, 모듈, 회로, 및 알고리즘 단계가 전자 하드웨어, 컴퓨터 소프트웨어, 또는 이들의 조합으로 구현될 수도 있다는 것을 인식할 것이다. 이러한 하드웨어와 소프트웨어의 교환성 (interchangeability) 을 명확하게 나타내기 위해서, 각종 예시적인 컴포넌트, 블록, 모듈, 회로, 및 단계가 일반적으로 그 기능성 면에서 전술되었다. 이러한 기능성이 하드웨어 또는 소프트웨어로 구현되는지 여부는 전체 시스템에 부과된 특정 애플리케이션 및 디자인 제약에 종속한다. 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 전술한 기능성을 각 특정 애플리케이션에 대해 상이한 방식으로 구현할 수도 있지만, 이러한 구현 결정은 본 개시물의 범위를 벗어나는 것으로 해석되어서는 안 된다.

본 개시물과 관련하여 기재된 각종 예시적인 논리 블록, 모듈, 및 회로는 범용 프로세서, DSP, ASIC, 필드 프로그래머블 게이트 어레이 (FPGA) 또는 다른 프로그래머블 논리 디바이스, 이산 게이트 또는 트랜지스터 로직, 이산 하드웨어 컴포넌트, 또는 본 명세서에 기재된 기능을 수행하도록 디자인된 이들의 임의의 조합으로 구현 또는 수행될 수도 있다. 범용 프로세서는 마이크로프로세서일 수도 있지만, 대안적으로 이 프로세서는 임의의 종래의 프로세서, 제어기, 마이크로제어기, 또는 상태 머신일 수도 있다. 또한, 프로세서는, 예를 들어 DSP 와 마이크로프로세서의 조합, 복수의 마이크로프로세서, DSP 코어와 결합된 하나 이상의 마이크로프로세서, 또는 이러한 임의의 다른 구성과 같은 컴퓨팅 디바이스의 조합으로 구현될 수도 있다.

본 개시물과 관련하여 기재된 알고리즘 또는 방법의 단계는 직접적으로 하드웨어로, 프로세서에 의해 실행되는 소프트웨어 모듈로, 또는 이들의 조합으로 구체화될 수도 있다. 소프트웨어 모듈은 RAM 메모리, 플래시 메모리, ROM 메모리, EPROM 메모리, EEPROM 메모리, 레지스터, 하드디스크, 착탈식 디스크, CD-ROM, 또는 본 발명이 속하는 기술분야에 공지된 임의의 다른 형태의 저장 매체에 존재할 수 있다. 예시적인 저장 매체는 프로세서에 접속되어, 프로세서가 저장 매체로부터 정보를 판독할 수 있고, 저장 매체에 정보를 기록할 수 있게 된다. 대안적으로, 저장 매체는 프로세서에 통합될 수도 있다. 프로세서 및 저장 매체는 ASIC 에 존재할 수도 있다. ASIC 는 사용자 단말기에 존재할 수도 있다. 대안적으로, 프로세서 및 저장 매체는 개별 컴포넌트로서 사용자 단말기에 존재할 수도 있다.

본 발명이 속하는 기술분야에서 통상의 지식을 가진 자가 본 개시물을 실시하거나 이용할 수 있도록 본 개시물의 전술한 설명이 제공된다. 이러한 개시물에 대한 각종 변형은 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 명백해질 수도 있고, 본 명세서에 정의된 일반적인 원리는, 본 개시물의 사상 또는 범위를 벗어나지 않으면서 다른 디자인에 적용될 수도 있다. 따라서, 본 개시물은 본 명세서에 제시된 실시예에 한정되도록 의도된 것이 아니라, 본 명세서에 개시된 원리 및 신규 특징에 부합하는 가장 광범위한 범위를 따르는 것이다.

도 1a 는 2D 스케일링을 이용하는 분리가능한 풀 2D IDCT 를 도시한 도면이다.
도 1b 는 행-열 스케일링을 이용하는 분리가능한 풀 2D IDCT 를 도시한 도면이다.
도 1c 는 1D 스케일링을 이용하는 분리가능한 풀 2D IDCT 를 도시한 도면이다.
도 1d 는 분리가능한 스케일링 2D IDCT 를 도시한 도면이다.
도 2 는 8-포인트 1D IDCT 의 인수 분해 (factorization) 의 플로우 그래프이다.
도 3a 는 2D 스케일링을 이용하는 분리가능한 풀 2D DCT 를 도시한 도면이다.
도 3b 는 행-열 스케일링을 이용하는 분리가능한 풀 2D DCT 를 도시한 도면이다.
도 3c 는 1D 스케일링을 이용하는 분리가능한 풀 2D DCT 를 도시한 도면이다.
도 3d 는 분리가능한 스케일링 2D DCT 를 도시한 도면이다.
도 4 는 8-포인트 1D DCT 의 인수 분해의 플로우 그래프이다.
도 5 는 풀 인터페이스 및 스케일링 인터페이스를 지원하는 IDCT 프로세서를 도시한 도면이다.
도 6 은 풀 인터페이스 및 스케일링 인터페이스를 지원하는 DCT 프로세서를 도시한 도면이다.
도 7 은 변환을 수행하는 프로세스를 도시한 도면이다.
도 8 은 인코딩 시스템 및 디코딩 시스템을 도시한 도면이다.
도 9 는 인코딩 시스템의 블록도이다.
도 10 은 디코딩 시스템의 블록도이다.

타입 Ⅱ 의 N-포인트 1D DCT 및 N-포인트 1D IDCT 는,

와 같이 정의될 수도 있는데, 여기서

이고,

은 1D 공간 도메인 함수이고,

은 1D 주파수 도메인 함수이다.

[수학식 1] 에서의 1D DCT 는 N 개의 입력 샘플 또는 공간 도메인 값

내지

에 대해 연산하고, N 개의 변환 계수

내지

을 발생시킨다. [수학식 2] 에서의 1D IDCT 는 N 개의 변환 계수에 대해 연산하여, N 개의 출력 샘플을 발생시킨다. 타입 Ⅱ DCT 는 일 타입의 변환이고, 일반적으로 종종 이미지/비디오 압축을 위해 제안된 각종 에너지 압축 변환 중에서 가장 효율적인 변환 중 하나로 여겨진다.

1D DCT 및 1D IDCT 는 각각 [수학식 1] 및 [수학식 2] 에 나타낸 오리지널 형태로 구현될 수도 있다. 그러나, 후술되는 바와 같이, 가능한 한 소수의 승산 및 가산을 야기하는 인수 분해를 발견함으로써, 계산 복잡도에서의 상당한 감소가 실현될 수도 있다.

[수학식 1] 에서의 1D DCT 는,

와 같이 행렬 형태로 표현될 수도 있는데,

여기서,

는 입력 샘플의 N×1 벡터이고,

는 풀 1D DCT 의 N×N 행렬이고,

는 변환 계수의 N×1 벡터이다.

는 입력 샘플

내지

을 포함하고,

는 변환 계수

내지

을 포함한다.

의 엘리먼트는 [수학식 1] 에 기초하여 획득될 수도 있다.

1D DCT 는,

와 같이 행렬의 곱으로 인수 분해될 수도 있는데,

여기서,

는 스케일 인수 (scale factor) 의 대각 행렬이고,

는 스케일링 1D DCT 의 N×N 행렬이다.

[수학식 3] 및 [수학식 4] 는, 먼저

에 대해 스케일링 1D DCT 를 수행한 다음, 그 결과를

로 스케일링함으로써,

에 대해 풀 1D DCT 가 수행될 수도 있다는 것을 나타낸다.

예를 들어, [수학식 4] 에 나타낸 바와 같이, 스케일링 연산 및 스케일링 변환으로 풀 변환을 분해하는 이점은, 스케일 인수를 적절하게 선택함으로써, 스케일링 변환의 승산 복잡도가 감소될 수도 있다는 것이다. 예를 들어, "A Fast DCT-SQ Scheme for Images" (Transactions of the IEICE, 1988 년 11 월) 에서의 AAN (Arai, Agui, and Nakajima) 의 잘 알려진 분해는, 단지 무리 인수 (irrational factor) 에 의한 5 회의 승산만으로 구현될 수도 있는 스케일링 8-포인트 DCT 를 생성한다. 이에 반해, 가장 잘 알려진 풀 8-포인트 DCT 는 11 회의 이러한 승산을 필요로 한다.

N×N 2D DCT 는,

와 같이 정의될 수도 있는데,

여기서,

는

와

의 크로네커 (Kroneker) 곱이고, 풀 2D DCT 의 행렬이고,

는 스케일링 2D DCT 의 행렬이고,

는 스케일링 2D DCT 에 대한 스케일 인수의 행렬이다.

[수학식 5] 에서의 연산의 결과는 N×N 2D DCT 의 행렬이다.

한번에 1 차원에 대해, 분리가능한 방식으로 입력 샘플의 N×N 행렬

에 대해 2D DCT 가 수행될 수도 있다. 예를 들어,

의 각 행에 대해 1D DCT 가 수행될 수도 있고, 그런 다음 중간 행렬의 각 열에 대해 1D DCT 가 수행될 수도 있다. 대안적으로,

의 각 열에 대해 1D DCT 가 수행되고, 그 다음에 중간 행렬의 각 행에 대해 1D DCT 가 수행될 수도 있다.

[수학식 5] 는, 먼저

에 대해 스케일링 2D DCT 를 수행한 다음, 그 결과를 스케일링함으로써,

에 대해 2D DCT 가 수행될 수도 있다는 것을 나타낸다. 또한, [수학식 5] 는, 행 1D DCT 및 열 1D DCT 에 대한 스케일링이 스케일링 2D DCT 의 결과에 대해 적용되는 (

에 의한 행렬 곱인) 단일 단계로 병합될 수도 있다는 것을 나타낸다.

[수학식 2] 에서의 1D IDCT 는,

와 같이 행렬 형태로 표현될 수도 있는데,

여기서,

은 풀 1D IDCT 의 N×N 행렬이고,

는 전치 행렬 (transpose) 을 나타낸다.

2D IDCT 는,

으로 표현될 수도 있다.

[수학식 7] 은, 먼저 변환 계수에 대해 스케일링한 다음, 스케일링 변환 계수에 대해 스케일링 2D IDCT 를 수행함으로써, 변환 계수의 N×N 행렬

에 대해 2D IDCT 가 수행될 수도 있다는 것을 나타낸다. 또한, [수학식 7] 은, 행 1D IDCT 및 열 1D IDCT 에 대한 스케일링이 스케일링 2D IDCT 에 선행하는 단일 단계로 병합될 수도 있다는 것을 나타낸다.

스케일링 아키텍처는 스케일링 변환을 이용하는 디자인이고, 풀 아키텍처는 풀 변환을 이용하는 디자인이다. 스케일링 아키텍처는 풀 아키텍처보다 낮은 승산 복잡도를 가질 수도 있다. 예를 들어, 스케일링 아키텍처는 분리가능한 행-열 방식으로 스케일링 2D IDCT (

) 를 수행할 수도 있고, 각 행 및 각 열에 대한 AAN 분해로부터 8-포인트 스케일링 1D IDCT

를 이용할 수도 있다. 이 스케일링 아키텍처의 승산 복잡도는, 8 개의 행 및 8 개의 열 각각에 대해 5 회의 승산과 스케일링을 위한 64 회의 승산, 또는 8*8 + 16*5 = 64 + 80 = 144 회의 승산일 수도 있다. 특정 상황에 있어서, 스케일링은 양자화와 결합될 수도 있는데, 이 경우 스케일링 아키텍처의 승산 복잡도는 약 80 회의 승산으로 감소될 수도 있다. 풀 아키텍처는 행-열 방식으로 2D IDCT (

) 를 수행할 수도 있고, 각 행 및 각 열에 대해 가장 잘 알려진 풀 8-포인트 1D IDCT

를 이용할 수도 있다. 이 풀 아키텍처의 승산 복잡도는, 8 개의 행 및 8 개의 열 각각에 대해 11 회의 승산, 또는 16*11 = 176 회의 승산일 수도 있다. 분리가능한 구현에 있어서, 스케일링 아키텍처는 풀 아키텍처보다 낮은 승산 복잡도를 가질 수도 있다.

스케일링 아키텍처는 저복잡도를 지지하는 디자인에 이용될 수도 있다. 스케일링할 단지 소수의 넌-제로 (non-zero) 변환 계수가 존재하는 경우에 스케일링 아키텍처가 유리할 수도 있는데, 이는 종종 이미지/비디오 디코더에서의 2D IDCT 에 대한 경우일 수도 있다. 또한, 스케일링 아키텍처는, 예를 들어 도 8 에 도시된 바와 같이, 변환 계수의 스케일링이 이미지/비디오 인코더/디코더 (코덱) 에서 양자화 및/또는 역양자화와 결합되는 것을 허용하는 디자인에 유리할 수도 있다.

풀 아키텍처는, 이용 용이성을 지지하는 디자인에 바람직할 수도 있다. 예를 들어, 다수의 컴퓨팅 환경 및 애플리케이션은 다수의 이미지 및 비디오 코딩 표준을 지원할 수도 있다. 이들 경우에, 풀 변환을 구현하는 변환 엔진을 갖고, 플렉시블 입/출력 인터페이스를 제공하여, 변환 엔진이 각종 양자화기 및 코덱과 함께 사용될 수 있게 하는 것이 보다 편리할 수도 있다. 풀 아키텍처는 단순한 인터페이스를 제공할 수도 있고, 이러한 환경에 보다 적합할 수도 있다.

스케일링 인터페이스 및 풀 인터페이스를 통해 상이한 애플리케이션을 유연하게 지원할 수 있는 변환 디자인이 본 명세서에 기재되어 있다. 풀 아키텍처와 유사하게, 변환 디자인은 풀 인터페이스를 통해 풀 입력값을 수신하고, 이들 입력값에 대해 풀 변환을 수행하여, 풀 출력값을 제공할 수도 있다. 또한, 스케일링 아키텍처와 유사하게, 변환 디자인은 스케일링 인터페이스를 통해 스케일링 입력값을 수신하고, 이들 입력값에 대해 스케일링 변환을 수행하여, 스케일링 출력값을 제공할 수도 있다. 변환 디자인은 내부적으로 분리가능한 스케일링 변환을 구현하여, 잠재적으로 보다 낮은 복잡도 및/또는 개선된 정밀도를 달성할 수도 있다. 따라서, 변환 디자인은 특정 애플리케이션에 대해서는 보다 낮은 복잡도를 달성가능할 수도 있고, 다른 애플리케이션에 대해서는 이용 용이성을 제공가능할 수도 있고, 또는 특정 경우에는 보다 낮은 복잡도 및 이용 용이성 모두를 제공가능할 수도 있다. 변환 디자인은 순방향 변환 (forward transform ; 예를 들어, DCT) 및 역방향 변환 (inverse transform ; 예를 들어, IDCT) 모두에 이용될 수도 있다. 명쾌함을 위해, 변환 디자인은 IDCT 에 대해 상세하게 후술된다.

스케일링 2D IDCT 아키텍처 및 넌-스케일링/풀 2D IDCT 아키텍처는,

와 같이 표현될 수도 있다.

풀/넌-스케일링 인터페이스는 변환 계수를 수신할 수도 있다. 이들 변환 계수에 대해,

와 같이 풀 2D IDCT 가 수행될 수도 있는데,

여기서,

는 변환 계수의 행렬이고,

은 풀 2D IDCT 의 근사이고,

는 출력 샘플의 행렬이다.

[수학식 10] 에서의 연산자 표시

은, 고정 소수점 근사 (fixed-point approximation) 가 단지 선형 연산에만 기초하지 않을 수도 있다는 것을 나타내는데 이용된다.

의 각 행 및 각 열에 대해,

와 같이 풀 1D IDCT 를 수행함으로써, 풀 2D IDCT 가 달성될 수도 있는데,

여기서,

는

의 i 번째 행 또는 열이고,

은 풀 1D IDCT 의 근사이다.

은 2D 연산자

의 행-열 구현에 이용될 수도 있다.

스케일링 인터페이스는 스케일링 변환 계수를 수신할 수도 있고, 이 스케일링 변환 계수는,

와 같이 획득될 수도 있는데,

여기서,

은 2D 스케일링 연산의 근사이고,

는 스케일링 변환 계수의 행렬이다.

스케일링 변환 계수에 대해,

와 같이 스케일링 2D IDCT 가 수행될 수도 있는데,

여기서,

은 스케일링 2D IDCT 의 근사이다.

스케일링 2D IDCT 는,

와 같이

의 각 행 및 각 열에 대해 스케일링 1D IDCT 를 수행함으로써 달성될 수도 있는데,

여기서,

은

의 i 번째 행 또는 열이고,

은 스케일링 1D IDCT 의 근사이다.

은 2D 연산자

의 행-열 구현에 이용될 수도 있다.

[수학식 13] 에 나타낸 바와 같이, 스케일링 인터페이스는 2D 연산자

을 구현함으로써 실현될 수도 있다. [수학식 12] 및 [수학식 13] 에 나타낸 바와 같이, 풀 인터페이스는 2D 연산자

에 부가하여 2D 스케일링 연산자

을 구현함으로써 실현될 수도 있다. 그런 다음,

와 같이 풀 2D IDCT 가 수행될 수도 있다.

[수학식 15] 는, 먼저 2D 스케일링 연산자

으로 풀 변환 계수를 스케일링 한 다음, 2D 연산자

으로 스케일링 변환 계수에 대해 스케일링 2D IDCT 를 수행함으로써, 이들 풀 변환 계수

에 대해 풀 2D IDCT 가 수행될 수도 있다는 것을 나타낸다. 다음에, 2D 연산자

은 1D 연산자

의 행-열 캐스케이드로 구현될 수도 있다.

따라서, 분리가능한 풀 2D IDCT 에 대한 2D 연산자

은 2D 스케일링 연산자

및 분리가능한 스케일링 2D IDCT 에 대한 2D 연산자

으로 구현될 수도 있다. 후술되는 바와 같이, 2D 스케일링은 각종 방식으로 구현될 수도 있다. 그 결과로서 생기는 2D 스케일링 및 분리가능한 스케일링 2D IDCT 로 구현된 분리가능한 풀 2D IDCT 의 복잡도 및 성능은, 고유하게 구현된 풀 2D IDCT 와 동등할 수도 있다.

도 1a 는 2D 스케일링을 이용하는 분리가능한 풀 2D IDCT (100) 의 일 디자인을 도시한 도면이다. 2D IDCT (100) 는 2D 스케일링 스테이지 (112), 그 다음의 행 (또는 열) 에 대한 스케일링 1D IDCT 스테이지 (114), 또한 그 다음의 열 (또는 행) 에 대한 스케일링 1D IDCT 스테이지 (116), 및 끝으로 출력 포맷팅 스테이지 (118) 를 포함한다. 2D 스케일링 스테이지 (112) 는 변환 계수의 N×N 블록

를 수신하고, 각 변환 계수

와 스케일 인수

를 승산할 수도 있고, 또한 각 스케일링 변환 계수를 P 비트만큼 좌측으로 시프트시킬 수도 있는데, 여기서 P 는 예약된 "가수 (mantissa)" 비트의 수를 나타낸다. 스케일링 이후에,

의 양이 DC 변환 계수에 부가되어, 출력 샘플에서의 적절한 라운딩을 달성할 수도 있다. 스케일링의 정밀도를 향상시키기 위해서, 정수로의 스케일 인수의 변환시 S=P+R 비트가 이용될 수도 있고, 승산 이후에 R 비트만큼의 우측 시프트가 수행될 수도 있다. S 는 하드웨어 플랫폼 상의 구현을 용이하게 할 수 있는 임의의 적합한 값일 수도 있고, 예를 들어 S 는 부호있는/부호없는 16-비트 승산기를 갖는 플랫폼에 대해 15 또는 16 일 수도 있다.

스케일링 1D IDCT 스테이지 (114) 는 2D 스케일링 스테이지 (112) 로부터의 스케일링 변환 계수의 블록의 각 행에 대해 N-포인트 스케일링 1D IDCT 를 수행한다. 스케일링 1D IDCT 스테이지 (116) 는 스케일링 1D IDCT 스테이지 (114) 에 의해 발생된 중간 블록의 각 열에 대해 N-포인트 스케일링 1D IDCT 를 수행한다. 스케일링 1D IDCT 스테이지 (114 및 116) 에 대한 스케일링 1D IDCT 는 임의의 내부 사전-스케일링 또는 사후-스케일링을 수행하지 않고 입력 데이터에 대해 직접적으로 연산할 수도 있다. 행 및 열 모두가 처리된 이후에, 출력 포맷팅 스테이지 (118) 는 스케일링 1D IDCT 스테이지 (116) 로부터의 결과적인 양을 P 비트만큼 우측으로 시프트시켜, 풀 2D IDCT 에 대한 출력 샘플의 N×N 블록

를 발생시킬 수도 있다. 전체 2D IDCT 가 원하는 폭의 레지스터를 사용하여 구현될 수도 있도록, 스케일 인수 및 정밀도 상수 P 가 선택될 수도 있다.

2D 스케일링 스테이지 (112) 에서의 2D 스케일링은,

와 같이 표현될 수도 있는데,

여기서,

는

의 i 번째 행 및 j 번째 열에서의 변환 계수이고,

및

는 각각

의 i 번째 대각 엘리먼트 및 j 번째 대각 엘리먼트이고,

는

의 i 번째 행 및 j 번째 열에서의 스케일링 변환 계수이고, "

" 은 R 비트만큼의 부호있는 우측 시프트 연산을 나타낸다.

R 은 스케일링 변환 계수

에서의 부가된 고정 소수점 정밀도의 P 비트를 보장하는 상수이다.

테이블은 스케일 인수

(여기서, i = 0, …, N-1 이고, j = 0, …, N-1) 를 저장할 수도 있다.

의 각 엘리먼트는 테이블에서의 대응 스케일 인수와 승산될 수도 있다.

의 N·N 개의 엘리먼트에 대해 최대 N·N 회의 승산이 수행될 수도 있다.

도 1b 는 분리가능한 행-열 스케일링을 이용하는 분리가능한 풀 2D IDCT (102) 의 일 디자인을 도시한 도면이다. 2D IDCT (102) 는 분리가능한 행-열 스케일링 스테이지 (122), 그 다음의 행 (또는 열) 에 대한 스케일링 1D IDCT 스테이지 (124), 또한 그 다음의 열 (또는 행) 에 대한 스케일링 1D IDCT 스테이지 (126), 및 끝으로 출력 포맷팅 스테이지 (128) 를 포함한다. 분리가능한 행-열 스케일링 스테이지 (122) 는 변환 계수의 N×N 블록

를 수신하고, 각 행 i 에서의 각 변환 계수

와 스케일 인수

를 승산한 다음, 각 열 j 에서의 각 결과적인 계수와 스케일 인수

를 승산하여,

와 같이 스케일링 변환 계수를 획득할 수도 있다.

따라서, 분리가능한 행-열 스케일링 스테이지 (122) 는 행 다음에 열에 대해 (또는 열 다음에 행에 대해) 분리가능한 방식으로 2D 스케일링을 수행할 수도 있다. 분리가능한 행-열 스케일링은, 동일한 하드웨어가 행의 스케일링 및 열의 스케일링에 이용되는 것을 허용할 수도 있고, 이는 구현 복잡도를 감소시킬 수도 있다.

의 N·N 개의 엘리먼트에 대해 최대 2·N·N 회의 승산이 수행될 수도 있다. 그러나, 실제 승산 횟수는 2·N·N 보다 훨씬 적을 수도 있는데, 그 이유는 스케일 인수

내지

의 일부가 명백한 (trivial) 값 (예를 들어, 256) 을 가질 수도 있고, 이들 명백한 스케일 인수와의 승산이 단순한 시프트 연산으로 구현될 수도 있기 때문이다. 스테이지 (124, 126 및 128) 는 각각 도 1a 에서의 스테이지 (114, 116 및 118) 와 동일한 방식으로 동작할 수도 있다.

도 1c 는 각 스케일링 1D IDCT 이전에 스케일링을 이용하는 분리가능한 풀 2D IDCT (104) 의 일 디자인을 도시한 도면이다. 2D IDCT (104) 는, 행 (또는 열) 에 대해 스케일링을 이용하는 스케일링 1D IDCT 스테이지 (134), 그 다음의 열 (또는 행) 에 대해 스케일링을 이용하는 스케일링 1D IDCT 스테이지 (136), 및 끝으로 출력 포맷팅 스테이지 (138) 를 포함한다. 스케일링 1D IDCT 스테이지 (134) 는, 변환 계수의 블록의 각 행에 대해 N-포인트 스케일링 1D IDCT 이전에 스케일링을 수행한다. 스케일링 1D IDCT 스테이지 (136) 는, 스케일링 1D IDCT 스테이지 (134) 에 의해 발생된 중간 블록의 각 열에 대해 N-포인트 스케일링 1D IDCT 이전에 스케일링을 수행한다. 스케일링 1D IDCT 스테이지 (134 및 136) 는 본질적으로 스케일링 1D IDCT 를 이용하여 풀 1D IDCT 를 수행한다. 후술하는 바와 같이, 스케일링 1D IDCT 내의 상수 인수 및 스케일 인수

내지

은 풀 1D IDCT 에 대한 정밀도를 향상시키고/향상시키거나 복잡도를 감소시키도록 선택될 수도 있다. 출력 포맷팅 스테이지 (138) 는 도 1a 에서의 출력 포맷팅 스테이지 (118) 와 동일한 방식으로 동작할 수도 있다.

도 1d 는 분리가능한 스케일링 2D IDCT (106) 의 일 디자인을 도시한 도면이다. 2D IDCT (106) 는, 행 (또는 열) 에 대한 스케일링 1D IDCT 스테이지 (144), 그 다음의 열 (또는 행) 에 대한 스케일링 1D IDCT 스테이지 (146), 및 끝으로 출력 포맷팅 스테이지 (148) 를 포함한다. 스케일링 1D IDCT 스테이지 (144) 는 스케일링 변환 계수의 N×N 블록

의 각 행에 대해 N-포인트 스케일링 1D IDCT 를 수행한다. 스케일링 1D IDCT 스테이지 (146) 는 스케일링 1D IDCT 스테이지 (144) 에 의해 발생된 중간 블록의 각 열에 대해 N-포인트 스케일링 1D IDCT 를 수행한다. 출력 포맷팅 스테이지 (148) 는 도 1a 에서의 출력 포맷팅 스테이지 (118) 와 동일한 방식으로 동작할 수도 있다.

도 1a 내지 도 1c 에 도시된 바와 같이, 풀 2D IDCT 에 대한 스케일링은, 도 1a 에서의 행-열 1D IDCT 이전에 2D 스케일링을 이용하는 것, 도 1b 에서의 행-열 1D IDCT 이전에 분리가능한 행-열 스케일링을 이용하는 것, 또는 도 1c 에서의 각 1D IDCT 이전에 스케일링을 이용하는 것과 같이 각종 방식으로 달성될 수도 있다. 또한, 스케일링은 다른 방식으로 수행될 수도 있다. 도 1d 에 도시된 바와 같이, 스케일링 2D IDCT 는, 단순히 스케일링을 생략하고, 행 및 열에 대해 1D IDCT 를 수행함으로써 달성될 수도 있다.

각종 타입의 스케일링 1D IDCT 가 도 1a 내지 도 1d 에서의 행-열 1D IDCT 에 이용될 수도 있다. 예를 들어, AAN 분해에 기초한 스케일링 1D IDCT 가 이용될 수도 있다. 가능하게는 보다 낮은 복잡도를 갖는 또다른 스케일링 IDCT 가 후술된다.

도 2 는 8-포인트 1D IDCT 의 예시적인 인수 분해의 플로우 그래프 (200) 이다. 플로우 그래프 (200) 에 있어서, 각 가산은 심볼 "

" 으로 표현되고, 각 승산은 박스로 표현된다. 각 가산은 2 개의 입력값을 합산하거나 감산하여, 출력값을 제공한다. 각 승산은 입력값과 박스 내부에 표시된 상수 인수를 승산하여, 출력값을 제공한다. 도 2 에서의 인수 분해는 다음의 상수 인수와의 승산을 갖는다:

,

플로우 그래프 (200) 는 8 개의 변환 계수

내지

을 수신하고, 이들 변환 계수를 스케일 인수

내지

로 스케일링하여, 8 개의 스케일링 변환 계수

내지

을 획득할 수도 있다. 대안적으로, 플로우 그래프 (200) 는 직접적으로 8 개의 스케일링 변환 계수를 수신할 수도 있다. 어느 경우에도, 플로우 그래프 (200) 는 8 개의 스케일링 변환 계수에 대해 8-포인트 1D IDCT 를 수행하여, 8 개의 출력 샘플

내지

을 발생시킨다. 스케일 인수

내지

은 다음과 같다:

플로우 그래프 (200) 는 다수의 버터플라이 연산을 포함한다. 버터플라이 연산은 2 개의 입력값을 수신하여, 2 개의 출력값을 발생시키는데, 여기서 하나의 출력값은 2 개의 입력값의 합이고, 다른 출력값은 2 개의 입력값의 차이다. 예를 들어, 입력값

및

에 대한 버터플라이 연산은 상부 브랜치에 대해서는 출력값

를 발생시키고, 하부 브랜치에 대해서는 출력값

를 발생시킨다.

도 2 에 도시된 인수 분해는 총 6 회의 승산 및 28 회의 가산을 야기하는데, 이는 실질적으로 [수학식 2] 의 직접 계산에 필요한 승산 및 가산의 횟수보다 적다. 승산은 상이한 각도의 사인 및 코사인을 나타내는 무리 상수에 대해 이루어지는데, 이들 각도는 8-포인트 1D IDCT 에 대해 π/8 의 배수이다. 무리 상수는, 2 개의 정수의 비율이 아닌 상수이다. 무리 상수와의 승산은, 각 무리 상수가 유리 이항 상수 (rational dyadic constant) 에 의해 근사되는 경우에 고정 소수점 정수 연산에서 효율적으로 수행될 수도 있다. 유리 이항 상수는 이항 분모를 갖는 유리 상수이고,

의 형태를 갖는데, 여기서 b 및 c 는 정수이고, b > 0 이다.

고정 소수점 정수 연산에서 무리 상수

와 정수 변수

의 승산은,

와 같이 무리 상수를 유리 이항 상수에 대해 근사시킴으로써 달성될 수도 있는데,

여기서,

은 근사될 무리 상수이고,

은 유리 이항 상수이다.

정수 변수

및 유리 이항 상수

이 주어지는 경우, 정수값 곱인,

이, 다음의 중간값 시리즈인,

을 이용하여 근사될 수도 있는데,

여기서,

,

이고, 모든

값에 대해,

와 같이

가 획득되고,

여기서,

은

비트만큼 중간값

의 (상수

의 부호에 종속하는) 좌측 시프트 또는 우측 시프트 중 어느 하나를 포함한다.

[수학식 22] 에 있어서,

는

,

, 또는

와 동등할 수도 있다. 시리즈에서의 각 중간값

는 시리즈에서의 2 개의 이전의 중간값

및

에 기초하여 도출될 수도 있는데, 여기서

또는

중 어느 하나는 제로와 동등할 수도 있다. 각 중간값

는 1 회의 시프트 및/또는 1 회의 가산으로 획득될 수도 있다.

가 제로와 동등한 경우, 시프트가 필요하지 않다.

인 경우, 가산이 필요하지 않다. 승산에 대한 시프트 및 가산의 총 수는, 각 중간값에 이용된 수학식뿐만 아니라, t 인 시리즈에서의 중간값의 개수에 의해 결정된다. 유리 이항 상수 u 에 의한 승산은 본질적으로 시프트 및 가산 연산의 시리즈로 전개된다. 이 시리즈는, 이 시리즈에서의 최종값이 원하는 정수값 곱, 또는

이 되도록 정의된다.

고정 소수점 정수 연산에서 정수 변수

와 2 개의 무리 상수

및

의 승산은,

여기서,

및

는 2 개의 유리 이항 상수이고,

b, c, d 및 e 는 정수이고, b > 0 이고, d > 0 이다.

정수 변수

및 유리 이항 상수

및

가 주어지는 경우, 2 개의 정수값 곱인,

은, 다음의 중간값 시리즈인,

을 이용하여 근사될 수도 있는데,

여기서,

,

이고, 모든

값에 대해,

와 같이

가 획득된다.

이 시리즈는,

와 같이 스텝 m 및 n 에서 원하는 정수값 곱이 획득되도록 정의되는데,

여기서, m, n ≤ t 이고, m 또는 n 중 어느 하나는 t 와 동등하다.

[수학식 24] 내지 [수학식 28] 에 나타낸 바와 같이, 정수 변수

와 무리 상수

및

의 승산은, 연산의 총 수를 감소시키도록 중간 결과를 이용하여 시프트 및 가산 연산에 의해 발생된 중간값의 공통 시리즈로 근사될 수도 있다.

전술한 계산에 있어서, 제로 비트만큼의 시프트 및 제로의 가산 및 감산과 같은 명백한 연산 (trivial operation) 은 생략될 수도 있다. 다음의 단순화가 이루어질 수도 있다:

[수학식 29] 에 있어서, "

" 의 우측에 대한 수학식으로 나타낸 바와 같이, "

" 의 좌측에 대한 수학식은 (

으로 표시된) 제로의 가산 또는 감산을 수반하고, 1 회의 시프트로 수행될 수도 있다. [수학식 30] 에 있어서, "" 의 우측에 대한 수학식으로 나타낸 바와 같이, "

" 의 좌측에 대한 수학식은 (

으로 표시된) 제로 비트만큼의 시프트를 수반하고, 1 회의 가산으로 수행될 수도 있다. [수학식 29] 및 [수학식 30] 은

의 계산시 [수학식 22] 및 [수학식 27] 에 적용될 수도 있다.

계산을 간단하게 하기 위해서, 다음과 같이, 플로우 그래프 (200) 에서 상수 인수

및

에 대해 제 1 공통 인수

이 적용될 수도 있고, 상수 인수

,

및

에 대해 제 2 공통 인수

가 적용될 수도 있다:

, 및

또한, 다음과 같이, 공통 인수

및

를 설명하도록 스케일 인수

내지

이 스케일링될 수도 있다:

공통 인수

및

에 대한 값의 상이한 조합이 평가될 수도 있다.

및

값의 각 조합에 있어서, 출력 샘플의 정밀도 및 1D IDCT 에 대한 논리적 및 산술적 연산의 총 수가 결정될 수도 있다.

표 1 은

및

를 이용하는 도 2 에서의 1D IDCT 에 대한 예시적인 고정 소수점 근사를 나타낸다. 표 1 에 있어서, 제 1 열에는 스케일 인수

내지

및 스케일링 공통 인수가 주어진다. 각 인수는 제 2 열에 주어지는 유리 이항 상수에 대해 근사될 수도 있다. 제 3 열에는 변수

와 하나 또는 2 개의 유리 이항 상수의 승산에 대한 중간값 시리즈가 주어진다. 각각 제 4 열 및 제 5 열에는 각 승산에 대한 시프트 연산 및 가산 연산의 횟수가 주어진다. 제 6 열에는, 1D IDCT 에 각 승산이 이용되는 횟수가 주어진다. 1D IDCT 에 대한 가산 연산의 총 수는, 제 6 열에 주어진 횟수 × 제 4 열에서의 가산 연산의 횟수의 합과 동등하다. 1D IDCT 에 대한 시프트 연산의 총 수는, 제 6 열에 주어진 횟수 × 제 5 열에서의 시프트 연산의 횟수의 합과 동등하다.

표 1 에 있어서, 8 만큼의 우측 시프트는, 스케일 인수

,

및

에서 256 의 인수에 의한 승산을 취소하는데, 이는 부가적인 복잡도 감소를 가능하게 한다.

표 1 에 나타낸 디자인에 있어서, 8-포인트 스케일링 1D IDCT 는 50 회의 가산 연산 및 24 회의 시프트 연산으로 수행될 수도 있다. 8-포인트 풀 1D IDCT 는 61 회의 가산 연산 및 39 회의 시프트 연산으로 수행될 수도 있다. 스케일 인수

내지

을 이용하는 스케일링은 (도 1c 에 도시된 바와 같이) 스케일링 1D IDCT 이전에 수행될 수도 있고, 또는 (도 1a 및 도 1b 에 도시된 바와 같이) 행-열 1D IDCT 이전에 수행될 수도 있다. 8×8 풀 2D IDCT 는 977 회의 가산 연산 및 688 회의 시프트 연산으로 수행될 수도 있다. 977 회의 가산 연산은, 8 개의 행 및 8 개의 열에 대해 16 회의 1D IDCT 각각에 대한 61 회의 가산 + 스케일링 이후에 DC 변환 계수와

을 합산하는 1 회의 가산을 포함한다. 688 회의 시프트 연산은, 8 개의 행 및 8 개의 열에 대한 16 회의 IDCT 각각에 대한 39 회의 시프트 + P 비트만큼의 제 2 IDCT 스테이지로부터의 64 개의 값을 시프트시키는 64 회의 시프트를 포함한다. 표 1 에 나타낸 디자인은 IEEE 표준 1180-1190 및 그 보류 대체물 (pending replacement) 에 정의된 정밀도 메트릭을 충족시키거나 초과한다.

표 1 은 도 2 에서의 1D IDCT 에 대한 예시적인 고정 소수점 근사를 나타낸다. 또한, 스케일 인수

내지

및 상수 인수

,

및

은 다른 유리 이항 상수에 대해 근사될 수도 있는데, 이는 상이한 복잡도 및/또는 정밀도를 가질 수도 있다. 또한, 다른 타입의 스케일링 IDCT 가 분리가능한 스케일링 2D IDCT 및 풀 2D IDCT 를 구현하는데 이용될 수도 있다.

도 3a 는 2D 스케일링을 이용하는 분리가능한 풀 2D DCT (300) 의 일 디자인을 도시한 도면이다. 2D DCT (300) 는 입력 포맷팅 스테이지 (312), 그 다음의 행 (또는 열) 에 대한 스케일링 1D DCT 스테이지 (314), 또한 그 다음의 열 (또는 행) 에 대한 스케일링 1D DCT 스테이지 (316), 및 끝으로 2D 스케일링 스테이지 (318) 를 포함한다. 입력 포맷팅 스테이지 (312) 는 입력 샘플의 N×N 블록을 사전-승산할 수도 있다. 스케일링 1D DCT 스테이지 (314) 는 입력 포맷팅 스테이지 (312) 로부터의 사전-승산된 샘플의 블록의 각 행에 대해 N-포인트 스케일링 1D DCT 를 수행하여, 제 1 중간 블록을 발생시킨다. 스케일링 1D DCT 스테이지 (316) 는 제 1 중간 블록의 각 열에 대해 N-포인트 스케일링 1D DCT 를 수행하여, 제 2 중간 블록을 발생시킨다. 2D 스케일링 스테이지 (318) 는 제 2 중간 블록의 각 엘리먼트를 스케일링하여, 풀 2D DCT 에 대한 변환 계수의 블록을 제공한다.

도 3b 는 분리가능한 행-열 스케일링을 이용하는 분리가능한 풀 2D DCT (302) 의 일 디자인을 도시한 도면이다. 2D DCT (302) 는 입력 포맷팅 스테이지 (322), 그 다음의 행 (또는 열) 에 대한 스케일링 1D DCT 스테이지 (324), 또한 그 다음의 열 (또는 행) 에 대한 스케일링 1D DCT 스테이지 (326), 및 끝으로 분리가능한 행-열 스케일링 스테이지 (328) 를 포함한다. 스테이지 (322, 324 및 326) 는 각각 도 3a 에서의 스테이지 (312, 314 및 316) 와 동일한 방식으로 동작할 수도 있다. 분리가능한 행-열 스케일링 스테이지 (328) 는 행-단위 다음에 열-단위로 스케일링 1D DCT 스테이지 (326) 로부터의 제 2 중간 블록을 스케일링하여, 풀 2D DCT 에 대한 변환 계수의 블록을 발생시킬 수도 있다.

도 3c 는 각 스케일링 1D DCT 이후에 스케일링을 이용하는 분리가능한 풀 2D DCT (304) 의 일 디자인을 도시한 도면이다. 2D DCT (304) 는 입력 포맷팅 스테이지 (332), 행 (또는 열) 에 대한 스케일링을 이용하는 스케일링 1D DCT 스테이지 (334), 또한 그 다음의 열 (또는 행) 에 대한 스케일링을 이용하는 스케일링 1D DCT 스테이지 (336) 를 포함한다. 입력 포맷팅 스테이지 (332) 는 도 3a 에서의 입력 포맷팅 스테이지 (312) 와 동일한 방식으로 동작할 수도 있다. 스케일링 1D DCT 스테이지 (334) 는, 입력 포맷팅 스테이지 (332) 로부터의 사전-승산된 샘플의 블록의 각 행에 대해 N-포인트 스케일링 1D DCT 다음에 스케일링을 수행한다. 스케일링 1D DCT 스테이지 (336) 는, 스케일링 1D DCT 스테이지 (334) 에 의해 발생된 중간 블록의 각 열에 대해 N-포인트 스케일링 1D DCT 다음에 스케일링을 수행한다.

도 3d 는 분리가능한 스케일링 2D DCT (306) 의 일 디자인을 도시한 도면이다. 2D DCT (306) 는 입력 포맷팅 스테이지 (342), 행 (또는 열) 에 대한 스케일링 1D DCT 스테이지 (344), 또한 그 다음의 열 (또는 행) 에 대한 스케일링 1D DCT 스테이지 (346) 를 포함한다. 입력 포맷팅 스테이지 (342) 는 도 3a 에서의 입력 포맷팅 스테이지 (312) 와 동일한 방식으로 동작할 수도 있다. 스케일링 1D DCT 스테이지 (344) 는, 입력 포맷팅 스테이지 (342) 로부터의 사전-승산된 샘플의 블록의 각 행에 대해 N-포인트 스케일링 1D DCT 를 수행한다. 스케일링 1D DCT 스테이지 (346) 는 스케일링 1D DCT 스테이지 (344) 에 의해 발생된 중간 블록의 각 열에 대해 N-포인트 스케일링 1D DCT 를 수행한다.

도 3a 내지 도 3c 에 도시된 바와 같이, 풀 2D DCT 에 대한 스케일링은, 도 3a 에서의 행-열 1D DCT 이후에 2D 스케일링을 이용하는 것, 도 3b 에서의 행-열 1D DCT 이후에 분리가능한 행-열 스케일링을 이용하는 것, 또는 도 3c 에서의 각 1D DCT 이후에 스케일링을 이용하는 것과 같이 각종 방식으로 달성될 수도 있다. 또한, 스케일링은 다른 방식으로 수행될 수도 있다. 도 3d 에 도시된 바와 같이, 스케일링 2D DCT 는, 단순히 스케일링을 생략하고, 행 및 열에 대해 1D DCT 를 수행함으로써 달성될 수도 있다.

각종 타입의 스케일링 1D DCT 가 도 3a 내지 도 3d 에서의 행-열 1D DCT 에 이용될 수도 있다. 낮은 복잡도를 갖는 예시적인 스케일링 DCT 가 후술된다.

도 4 는 8-포인트 1D DCT 의 예시적인 인수 분해의 플로우 그래프 (400) 이다. 플로우 그래프 (400) 는 8 개의 입력 샘플

내지

을 수신하고, 이들 입력 샘플에 대해 8-포인트 스케일링 1D DCT 를 수행하여, 8 개의 스케일링 변환 계수

내지

을 발생시킨다. 스케일 인수

내지

가 전술한 바와 같이 주어진다. 도 4 에서의 인수 분해는 다음의 상수 인수와의 승산을 갖는다:

도 2 에서의 IDCT 에 대한 플로우 그래프 및 도 4 에서의 DCT 에 대한 플로우 그래프는 유사하고, 본질적으로 (1/2 의 차이를 갖는) 동일한 상수 인수에 의한 승산을 수반한다. 이러한 유사성은 집적 회로 상에서의 DCT 및 IDCT 의 구현에 대해 유리할 수도 있다. 특히, 이러한 유사성은, 실리콘 또는 다이 영역의 절약이 변환 상수에 의한 승산 및 버터플라이를 구현하는 것을 가능하게 할 수도 있는데, 이들 변환 상수는 순방향 변환 및 역방향 변환 모두에서 이용된다.

도 5 는 풀 인터페이스 및 스케일링 인터페이스를 지원하는 IDCT 프로세서 (500) 의 일 디자인의 블록도이다. IDCT 프로세서 (500) 내에서, 스케일링 유닛 (510) 은 풀 인터페이스를 통해 변환 계수의 블록을 수신하고, 이 변환 계수의 블록에 대해 스케일링 (예를 들어, 엘리먼트-단위 (element-wise) 2D 스케일링 또는 분리가능한 행-열 스케일링) 을 수행하여, 스케일링 변환 계수의 블록을 제공한다. 다중화기 (Mux ; 512) 는, 풀 인터페이스가 선택되는 경우에는 스케일링 유닛 (510) 으로부터 스케일링 변환 계수를 수신하여, 이들 스케일링 변환 계수를 제공한다. 또한, 다중화기 (512) 는, 스케일링 인터페이스가 선택되는 경우에는 스케일링 인터페이스를 통해 스케일링 변환 계수를 수신하여, 이들 스케일링 변환 계수를 제공한다. 다중화기 (514) 는 다중화기 (512) 의 출력 또는 버퍼 (518) 의 출력을 IDCT 엔진 (516) 으로 제공한다.

IDCT 엔진 (516) 은 다중화기 (512) 로부터의 스케일링 변환 계수의 블록의 행에 대해 스케일링 1D IDCT 를 수행하여, 중간 결과의 블록의 행을 버퍼 (518) 로 제공할 수도 있다. 그런 다음, IDCT 엔진 (516) 은 버퍼 (518) 로부터의 중간 결과의 블록의 열에 대해 스케일링 1D IDCT 를 수행하여, 최종 결과의 블록을 버퍼 (518) 로 제공할 수도 있다. 출력 포맷팅 유닛 (520) 은 버퍼 (518) 에서의 최종 결과에 대해 출력 포맷팅을 수행하여, 출력 샘플을 제공한다.

도 6 은 풀 인터페이스 및 스케일링 인터페이스를 지원하는 DCT 프로세서 (600) 의 일 디자인의 블록도이다. DCT 프로세서 (600) 내에서, 입력 포맷팅 유닛 (610) 은 입력 샘플의 블록에 대해 입력 포맷팅을 수행한다. DCT 엔진 (614) 은 다중화기 (612) 를 통해 입력 포맷팅 유닛 (610) 으로부터 입력 샘플의 블록을 수신하고, 이 입력 샘플의 블록의 행에 대해 스케일링 1D DCT 를 수행하여, 중간 결과의 블록을 버퍼 (616) 로 제공한다. 그런 다음, DCT 엔진 (614) 은 버퍼 (616) 로부터의 중간 결과의 블록의 열에 대해 스케일링 1D DCT 를 수행하여, 스케일링 변환 계수의 블록을 버퍼 (616) 로 제공할 수도 있다. 버퍼 (616) 는 스케일링 인터페이스에 대한 스케일링 변환 계수의 블록을 제공한다. 스케일링 유닛 (618) 은 스케일링 변환 계수의 블록을 수신 및 스케일링하여, 풀 인터페이스에 대한 풀 변환 계수를 제공한다.

*명쾌함을 위해, 대부분의 전술한 설명은 DCT 및 IDCT 에 대한 것이다. 일반적으로, 본 명세서에 기재된 기술은, DCT, IDCT, DFT, IDFT, MLT, 역 MLT, MCLT, 역 MCLT 등과 같은 임의의 타입의 변환에 이용될 수도 있다. 또한, 이들 기술은 변환의 임의의 인수 분해에 이용될 수도 있는데, 몇몇 예시적인 인수 분해가 도 2 및 도 4 에 주어진다. 또한, 이들 기술은 임의의 크기의 변환에 이용될 수도 있는데, 8-포인트 변환이 도 2 및 도 4 에 주어진다. 일반적으로, 8×8 DCT 및 8×8 IDCT 가 이미지 및 비디오 처리에 이용된다. 또한, 이들 기술은, JPEG, MPEG-1, MPEG-2, MPEG-4 (P.2), H.261, H.263 등과 같은 각종 이미지 및 비디오 코딩 표준에 이용될 수도 있다.

도 7 은 변환을 수행하는 프로세스 (700) 의 일 디자인을 도시한 도면이다. 제 1 인터페이스 (풀 또는 넌-스케일링 인터페이스) 를 통해 제 1 입력값이 수신될 수도 있다 (블록 712). 제 1 입력값에 대해 풀 변환이 수행되어, 제 1 출력값을 획득할 수도 있다 (블록 714). 제 2 인터페이스 (스케일링 인터페이스) 를 통해 제 2 입력값이 수신될 수도 있다 (블록 716). 제 2 입력값에 대해 스케일링 변환이 수행되어, 제 2 출력값을 획득할 수도 있다 (블록 718).

풀 변환은 풀 2D 역방향 변환일 수도 있다. 이 경우, 제 1 인터페이스를 통해 제 1 입력값의 블록이 수신 및 스케일링되어, 스케일링 입력값의 블록을 획득할 수도 있다. 스케일링 입력값의 블록의 각 행에 대해 스케일링 1D 변환이 수행되어, 중간 블록을 획득할 수도 있다. 중간 블록의 각 열에 대해 스케일링 1D 변환이 수행되어, 제 1 출력값의 블록을 획득할 수도 있다. 또한, 열 다음에 행에 대해 스케일링 1D 변환이 수행될 수도 있다.

또한, 풀 변환은 풀 2D 순방향 변환일 수도 있다. 이 경우, 제 1 인터페이스를 통해 제 1 입력값의 블록이 수신될 수도 있다. 입력값의 블록의 각 행에 대해 스케일링 1D 변환이 수행되어, 제 1 중간 블록을 획득할 수도 있다. 제 1 중간 블록의 각 열에 대해 스케일링 1D 변환이 수행되어, 제 2 중간 블록을 획득할 수도 있다. 제 2 중간 블록이 스케일링되어, 제 1 출력값의 블록을 획득할 수도 있다.

풀 변환은 풀 2D IDCT 일 수도 있다. 이 경우, 제 1 인터페이스를 통해 변환 계수의 블록이 수신 및 스케일링되어, 스케일링 변환 계수의 블록을 획득할 수도 있다. 예를 들어, 도 1a 에 도시된 바와 같이, 각 변환 계수는 각각의 스케일 인수로 스케일링되어, 대응하는 스케일링 변환 계수를 획득할 수도 있다. 대안적으로, 예를 들어, 도 1b 에 도시된 바와 같이, 변환 계수의 블록은 행-단위 및 열-단위로 스케일링되어, 스케일링 변환 계수의 블록을 획득할 수도 있다. 스케일링 변환 계수의 블록의 각 행에 대해 스케일링 1D IDCT 가 수행되어, 중간 블록을 획득할 수도 있다. 중간 블록의 각 열에 대해 스케일링 1D IDCT 가 수행되어, 출력 샘플의 블록을 획득할 수도 있다. 대안적으로, 예를 들어, 도 1c 에 도시된 바와 같이, 변환 계수의 블록의 각 행에 대해 스케일링 및 일 스케일링 1D IDCT 가 수행되어, 중간 블록을 획득할 수도 있고, 중간 블록의 각 열에 대해 스케일링 및 스케일링 1D IDCT 가 수행될 수도 있다.

스케일링 변환은 스케일링 2D IDCT 일 수도 있다. 이 경우, 제 2 인터페이스를 통해 스케일링 변환 계수의 블록이 수신될 수도 있다. 그런 다음, 스케일링 변환 계수의 블록의 각 행에 대해 스케일링 1D IDCT 가 수행되어, 중간 블록을 획득할 수도 있다. 중간 블록의 각 열에 대해 스케일링 1D IDCT 가 수행되어, 출력 샘플의 블록을 획득할 수도 있다.

풀 변환은 풀 2D DCT 일 수도 있고, 스케일링 변환은 스케일링 2D DCT 일 수도 있다. 전술한 바와 같이 입력 샘플의 블록에 대해 풀 2D DCT 가 수행되어, 제 1 인터페이스에 대한 풀 변환 계수의 블록을 획득할 수도 있다. 또한, 입력 샘플의 블록에 대해 스케일링 2D DCT 가 수행되어, 제 2 인터페이스에 대한 스케일링 변환 계수의 블록을 획득할 수도 있다.

도 8 은 인코딩 시스템 (810) 및 디코딩 시스템 (850) 의 일 디자인의 블록도이다. 인코딩 시스템 (810) 에서, 이미지/비디오 인코더 (820) 는 픽셀 블록을 수신하여, 특정 이미지 또는 비디오 압축 알고리즘에 따라 각 픽셀 블록에 대해 압축을 수행할 수도 있다. 이미지/비디오 인코더 (820) 는 픽셀 차이값 (또는 오차 (residual)) 블록 및 픽셀 블록을 제공할 수도 있다. DCT 유닛 (822) 은 입력 샘플의 블록으로서 오차 블록 및 픽셀 블록을 수신하고, 각 입력 샘플 블록에 대해 2D DCT 를 수행하여, 풀 변환 계수의 블록 또는 스케일링 변환 계수의 블록을 제공할 수도 있다. DCT 유닛 (822) 은 풀 인터페이스 및 스케일링 인터페이스 모두를 지원할 수도 있다. 양자화기 (824) 는 풀 변환 계수 또는 스케일링 변환 계수를 양자화하여, 양자화된 계수를 제공할 수도 있다. 엔트로피 인코더 (826) 는 양자화된 계수에 대해 엔트로피 인코딩을 수행하여, 스토리지 및/또는 통신 채널을 통한 송신 (840) 을 위해 패킷 또는 비트 스트림으로 압축 데이터를 제공할 수도 있다.

디코딩 시스템 (850) 에서, 엔트로피 디코더 (860) 는, 엔트로피 인코더 (826) 에 의한 엔트로피 인코딩에 상보적인 방식으로 압축 데이터에 대해 엔트로피 디코딩을 수행하여, 양자화된 계수를 제공할 수도 있다. 역양자화기 (862) 는 양자화된 계수를 풀 변환 계수 또는 스케일링 변환 계수에 매핑할 수도 있다. IDCT 유닛 (864) 은 풀 변환 계수에 대해서는 풀 2D IDCT 를 수행하고 또는 스케일링 변환 계수에 대해서는 스케일링 2D IDCT 를 수행하여, 출력 샘플의 블록을 제공할 수도 있다. IDCT 유닛 (864) 은 풀 인터페이스 및 스케일링 인터페이스 모두를 지원할 수도 있다. 이미지/비디오 디코더 (866) 는 출력 샘플의 블록에 대해 압축해제를 수행하여, 픽셀 블록을 제공할 수도 있다.

인코딩 시스템 (810) 에서, DCT 유닛 (822) 은 스케일링 2D DCT 를 수행하여, 스케일링 변환 계수를 제공할 수도 있다. 양자화기 (824) 는, 스케일링 변환 계수의 양자화뿐만 아니라, 스케일링 (예를 들어, 도 3a 에서의 2D 스케일링 스테이지 (318) 또는 도 3b 에서의 분리가능한 행-열 스케일링 스테이지 (328)) 을 수행할 수도 있다. 디코딩 시스템 (850) 에서, 역양자화기 (862) 는, 변환 계수에 대한 스케일링 (예를 들어, 도 1a 에서의 2D 스케일링 스테이지 (112) 또는 도 1b 에서의 분리가능한 행-열 스케일링 스테이지 (122)) 뿐만 아니라, 역양자화를 수행할 수도 있다. 그런 다음, IDCT 유닛 (864) 은 역양자화기 (862) 로부터의 스케일링 변환 계수에 대해 스케일링 2D IDCT 를 수행할 수도 있다.

도 9 는 도 8 에서의 인코딩 시스템 (810) 에 사용될 수도 있는 인코딩 시스템 (900) 의 블록도이다. 캡처 디바이스/메모리 (910) 는 소스 신호를 수신하고, 디지털 포맷으로의 변환을 수행하여, 입력/미처리 (raw) 데이터를 제공할 수도 있다. 캡처 디바이스 (910) 는 비디오 카메라, 디지타이저, 또는 일부 다른 디바이스일 수도 있다. 프로세서 (920) 는 미처리 데이터를 처리하여, 압축 데이터를 발생시킨다. 프로세서 (920) 내에서, 미처리 데이터는 DCT 유닛 (922) 에 의해 변환되고, 지그재그 스캔 유닛 (924) 에 의해 스캔되고, 양자화기 (926) 에 의해 양자화되고, 엔트로피 인코더 (928) 에 의해 인코딩되고, 패킷화기 (930) 에 의해 패킷화될 수도 있다. DCT 유닛 (922) 은 본 명세서에 기재된 기술에 따라 미처리 데이터에 대해 2D DCT 를 수행할 수도 있고, 풀 인터페이스 및 스케일링 인터페이스 모두를 지원할 수도 있다. 유닛 (922 내지 930) 각각은 하드웨어, 펌웨어 및/또는 소프트웨어로 구현될 수도 있다. 예를 들어, DCT 유닛 (922) 은 전용 하드웨어, ALU (Arithmetic Logic Unit) 를 위한 명령들 세트 등으로 구현될 수도 있다.

저장 유닛 (940) 은 프로세서 (920) 로부터의 압축 데이터를 저장할 수도 있다. 송신기 (942) 는 압축 데이터를 송신할 수도 있다. 제어기/프로세서 (950) 는 인코딩 시스템 (900) 에서 각종 유닛의 동작을 제어한다. 메모리 (952) 는 인코딩 시스템 (900) 을 위한 프로그램 코드 및 데이터를 저장한다. 하나 이상의 버스 (960) 는 인코딩 시스템 (900) 에서 각종 유닛을 상호접속시킨다.

도 10 은 도 8 에서의 디코딩 시스템 (850) 에 사용될 수도 있는 디코딩 시스템 (1000) 의 블록도이다. 수신기 (1010) 는 인코딩 시스템으로부터 압축 데이터를 수신할 수도 있고, 저장 유닛 (1012) 은 수신된 압축 데이터를 저장할 수도 있다. 프로세서 (1020) 는 압축 데이터를 처리하여, 출력 데이터를 발생시킨다. 프로세서 (1020) 내에서, 압축 데이터는 역패킷화기 (1022) 에 의해 역패킷화되고, 엔트로피 디코더 (1024) 에 의해 디코딩되고, 역양자화기 (1026) 에 의해 역양자화되고, 역 지그재그 스캔 유닛 (1028) 에 의해 적절한 순서로 배치되고, IDCT 유닛 (1030) 에 의해 변환될 수도 있다. IDCT 유닛 (1030) 은 본 명세서에 기재된 기술에 따라 풀 변환 계수 또는 스케일링 변환 계수에 대해 2D IDCT 를 수행할 수도 있고, 풀 인터페이스 및 스케일링 인터페이스 모두를 지원할 수도 있다. 유닛 (1022 내지 1030) 각각은 하드웨어, 펌웨어 및/또는 소프트웨어로 구현될 수도 있다. 예를 들어, IDCT 유닛 (1030) 은 전용 하드웨어, ALU 를 위한 명령들 세트 등으로 구현될 수도 있다.

디스플레이 유닛 (1040) 은 프로세서 (1020) 로부터의 복원 이미지 및 비디오를 디스플레이한다. 제어기/프로세서 (1050) 는 디코딩 시스템 (1000) 에서 각종 유닛의 동작을 제어한다. 메모리 (1052) 는 디코딩 시스템 (1000) 을 위한 프로그램 코드 및 데이터를 저장한다. 하나 이상의 버스 (1060) 는 디코딩 시스템 (1000) 에서 각종 유닛을 상호접속시킨다.

프로세서 (920 및 1020) 각각은, 하나 이상의 주문형 집적 회로 (ASIC), 디지털 신호 프로세서 (DSP), 및/또는 일부 다른 타입의 프로세서로 구현될 수도 있다. 대안적으로, 프로세서 (920 및 1020) 각각은, 하나 이상의 RAM (Random Access Memory), ROM (Read Only Memory), EPROM (Electrical Programmable ROM), EEPROM (Electrically Erasable PROM), 자기 디스크, 광학 디스크, 및/또는 본 발명이 속하는 기술분야에 공지된 다른 타입의 휘발성 및 비휘발성 메모리로 대체될 수도 있다.

Claims

변환 계수들의 제 1 블록을 스케일링하여 스케일링된 변환 계수들의 제 2 블록을 획득하고, 상기 제 2 블록의 각 행에 대해 스케일링 1-차원 (1D) 변환을 수행하여 중간 블록을 획득하고, 상기 중간 블록의 각 열에 대해 스케일링 1D 변환을 수행하여 출력 샘플들의 블록을 획득하고, 각 스케일링 1D 변환에 대해 무리 상수들의 세트에 근사하는 유리 이항 상수 (rational dyadic constant) 의 세트와 변수들의 세트에 대한 승산을 수행하도록 구성된 프로세서; 및
상기 프로세서에 연결되어, 상기 중간 블록을 저장하도록 구성된 메모리를 포함하는, 장치.
제 1 항에 있어서,
상기 스케일링 1D 변환은 스케일링 1D 역이산 코사인 변환 (IDCT) 인, 장치.
변환 계수들의 제 1 블록을 스케일링하여, 스케일링된 변환 계수들의 제 2 블록을 획득하는 단계;
상기 제 2 블록의 각 행에 대해 스케일링 1-차원 (1D) 변환을 수행하여, 중간 블록을 획득하는 단계;
상기 중간 블록의 각 열에 대해 스케일링 1D 변환을 수행하여, 출력 샘플들의 블록을 획득하는 단계; 및
각 스케일링 1D 변환에 대해 무리 상수들의 세트에 근사하는 유리 이항 상수 (rational dyadic constant) 의 세트와 변수들의 세트에 대한 승산을 수행하는 단계를 포함하는, 방법.
제 3 항에 있어서,
상기 스케일링 1D 변환은 스케일링 1D 역이산 코사인 변환 (IDCT) 인, 방법.
입력 샘플들의 블록의 각 행에 대해 스케일링 1-차원 (1D) 변환을 수행하여 제 1 중간 블록을 획득하고, 상기 제 1 중간 블록의 각 열에 대해 스케일링 1D 변환을 수행하여 제 2 중간 블록을 획득하고, 상기 제 2 중간 블록을 스케일링하여 변환 계수들의 블록을 획득하고, 각 스케일링 1D 변환에 대해 무리 상수들의 세트에 근사하는 유리 이항 상수 (rational dyadic constant) 의 세트와 변수들의 세트에 대한 승산을 수행하도록 구성된 프로세서; 및
상기 프로세서에 연결되어, 상기 제 1 중간 블록 및 상기 제 2 중간 블록을 저장하도록 구성된 메모리를 포함하는, 장치.
제 5 항에 있어서,
상기 스케일링 1D 변환은 스케일링 1D 이산 코사인 변환 (DCT) 인, 장치.
입력 샘플들의 블록의 각 행에 대해 스케일링 1-차원 (1D) 변환을 수행하여, 제 1 중간 블록을 획득하는 단계;
상기 제 1 중간 블록의 각 열에 대해 스케일링 1D 변환을 수행하여, 제 2 중간 블록을 획득하는 단계;
상기 제 2 중간 블록을 스케일링하여, 변환 계수들의 블록을 획득하는 단계;
각 스케일링 1D 변환에 대해 무리 상수들의 세트에 근사하는 유리 이항 상수 (rational dyadic constant) 의 세트와 변수들의 세트에 대한 승산을 수행하는 단계를 포함하는, 방법.
제 7 항에 있어서,
상기 스케일링 1D 변환은 스케일링 1D 이산 코사인 변환 (DCT) 인, 방법.