KR101461840B1 - 낮은 복잡도의 타깃 벡터 식별 - Google Patents

Abstract

특히 복수의 후보 벡터들로부터 하나 이상의 타깃 벡터들을 식별하되, 각각의 후보 벡터는 소팅된 요소들을 가지고 코드북의 하나 이상의 코드 벡터들의 개별 클래스와 관련되고, 후보 벡터들 중 적어도 하나는 개별 후보 벡터 및 순열 및 부호 순열 중 하나에 의해 개별 후보 벡터로부터 획득할 수 있는 적어도 하나의 코드 벡터를 포함하는 둘 이상의 코드 벡터들의 개별 클래스와 관련되며, 타깃 벡터들은 복수의 후보 벡터들의 모든 후보 벡터들 가운데에서 입력 벡터의 적어도 소팅된 표현에 대해 최소 거리를 가지는 것이 개시된다. 식별은 복수의 후보 벡터들 중 한 후보 벡터에 대해, 적어도 그 후보 벡터 및 기준 벡터 사이의 거리 및 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리에 기반하여, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 큰지를 체크하는 단계를 포함한다. 식별은 후보 벡터에 대해, 체크하는 단계가 부정적 결과를 산출하는 경우에만 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리를 계산하는 동작을 더 포함한다.

Description

낮은 복잡도의 타깃 벡터 식별{LOW COMPLEXITY TARGET VECTOR IDENTIFICATION}

본 발명의 실시예들은 코딩, 특히 음성 및 오디오 코딩에 관한 것이다.

음성 및 오디오 코딩을 위한 낮은 복잡도의 알고리즘들은 예컨대 모바일 단말 기반 통신을 위해 매우 관련이 깊은 자산이 된다. 코딩 효율성을 유지하면서도 낮은 저장성 및 낮은 복잡도로 인해, 구조화된 코드북들이 예컨대 3GPP(Third Generation Partnership Project) 내에서 표준화될 인핸스드 보이스 서비스(EVS(Enhanced Voice Service)) 같은 몇몇 최신 음성 및 오디오 코덱들에서 선호될 수 있다.

이러한 음성 및 오디오 코덱들 내에서 사용되는 코드북들은 예컨대 참고 문헌인 엘세비어(Elsevier), 신호 처리, 2002년, 제82호, 563-586 페이지, A. Vasilache, B. Dumitrescu 및 I. Tabus의 "LSF 양자화에 대한 응용을 가진 다중 스케일 리더 격자 구조 VQ(Multiple-scale leader-lattice VQ with application to LSF quantization)"에 서술된 바와 같은 격자 구조들에 기반할 수 있으며, 이 참고 문헌은 참조에 의해 본 명세서에 통합된다.

격자 코드북을 리더 클래스들의 결합으로서 정의하는 것이 가능하며, 리더 클래스들 각각은 리더 벡터에 의해 특징지어진다. 리더 벡터는 n 차원 벡터(n은 정수를 나타냄)이며 그것의 (가령, 양의) 성분들은 (가령, 내림 차순으로) 정렬된다. 리더 벡터에 대응하는 리더 클래스는 이때 상기 리더 벡터 및 상기 리더 벡터의 모든 부호 순열을 통해 획득되는 모든 벡터들로 구성된다(일부 가능한 한계가 있음). 하나, 일부, 또는 모든 리더 클래스들은 각기 하나 이상의 스케일들과 결부되며 그런 다음 격자 코드북이 스케일링되고/되거나 확증되지 않은(unsealed) 리더 클래스들의 결합으로서 형성되는 것 역시 가능하다.

입력 벡터는 예컨대 코드북에서 가장 가까운 이웃 코드 벡터, 즉 입력 벡터를 기준으로 가장 짧은 거리를 가진 코드 벡터를 찾음으로써 (가령 양자화 시) 부호화될 수 있다. 이 코드 벡터의 식별자(가령, 이 코드 벡터에 할당된 인덱스)는 여기서 입력 벡터의 부호화된 표현으로서 기능할 수 있다.

구조화된 코드북들의 사용이 이미 입력 벡터를 부호화하기 위해 요구되는 메모리 량과 계산상의 복잡도를 감소시키지만, 예컨대 모바일 장치에서의 코드북 기반 부호화의 적용과 관련하여 메모리 요건 및/또는 계산 복잡도의 추가 감축이 바람직하다.

본 발명의 제1양태에 따르면, 복수의 후보 벡터들로부터 하나 이상의 타깃 벡터들을 식별하되, 각각의 후보 벡터는 소팅된 요소들을 가지고 코드북의 하나 이상의 코드 벡터들의 개별 클래스와 관련되고, 후보 벡터들 중 적어도 하나는 개별 후보 벡터 및 순열 및 부호 순열 중 하나에 의해 개별 후보 벡터로부터 획득할 수 있는 적어도 하나의 코드 벡터를 포함하는 둘 이상의 코드 벡터들의 개별 클래스와 관련되며, 타깃 벡터들은 복수의 후보 벡터들의 모든 후보 벡터들 가운데에서 입력 벡터의 적어도 소팅된 표현에 대해 최소 거리를 가지는 단계를 포함하는 방법이 개시된다. 상기 식별 단계는 복수의 후보 벡터들 중 한 후보 벡터에 대해, 적어도 그 후보 벡터 및 기준 벡터 사이의 거리 및 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리에 기반하여, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 큰지를 체크하는 단계를 포함한다. 상기 식별 단계는 후보 벡터에 대해, 체크하는 단계가 부정적 결과를 산출하는 경우에만 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리를 계산하는 단계를 더 포함한다. 본 발명의 제1양태에 따른 방법은 예컨대 입력 벡터를 양자화 및/또는 부호화하기 위한 방법일 수 있다.

본 발명의 제2양태에 따르면, 본 발명의 제1양태에 따른 방법을 수행하도록 구성되거나, 본 발명의 제1양태에 따른 방법을 수행하기 위한 수단, 즉 하나 이상의 타깃 벡터들을 식별하기 위한 수단을 포함하고, 다시 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 긴지를 체크하기 위한 수단 및 상기 체크 동작이 부정적 결과를 산출하는 경우에만 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리를 계산하기 위한 수단을 포함하는 장치가 개시된다.

본 발명의 제3양태에 따르면, 적어도 하나의 프로세서, 및 컴퓨터 프로그램 코드를 포함하는 적어도 하나의 메모리를 포함하는 장치가 개시되며, 상기 적어도 하나의 메모리 및 컴퓨터 프로그램 코드는 상기 적어도 하나의 프로세서를 사용하여 상기 장치가 적어도 본 발명의 제1양태에 따른 방법을 수행하게 유도하도록 구성된다. 메모리에 포함된 컴퓨터 프로그램 코드는 예컨대 적어도 부분적으로, 프로세서를 위한 소프트웨어 및/또는 펌웨어를 나타낼 수 있다. 메모리의 비한정적 예들에는 프로세서에 의해 액세스 가능한 RAM(Random-Access Memory) 또는 ROM(Read-Only Memory)이 있다.

본 발명의 제4양태에 따라 컴퓨터 프로그램이 개시되며, 상기 컴퓨터 프로그램은 프로세서 상에서 실행될 때 본 발명의 제1양태에 따른 방법을 수행하기 위한 프로그램 코드를 포함한다. 컴퓨터 프로그램은 예를 들어, 인터넷과 같은 네트워크를 통해 배포될 수 있다. 컴퓨터 프로그램은 예를 들어 컴퓨터 판독가능 매체 안에서 저장 또는 부호화될 수 있다. 컴퓨터 프로그램은 예컨대 적어도 부분적으로, 프로세서의 소프트웨어 및/또는 펌웨어를 나타낼 수 있다.

본 발명의 제5양태에 따르면, 본 발명의 제4양태에 따른 컴퓨터 프로그램이 저장된 컴퓨터 판독가능 매체가 개시된다. 컴퓨터 판독가능 매체는 예컨대, 전기, 자기, 전자기, 광학 또는 기타 저장 매체로서 구현될 수 있으며, 착탈가능 매체이거나 장치나 기기에 고정 인스톨되는 매체일 수 있다. 그러한 컴퓨터 판독가능 매체의 비한정적 예들이 RAM 또는 ROM이다. 컴퓨터 판독가능 매체는 예컨대 유형의 매체, 예컨대 유형의 저장 매체일 수 있다. 컴퓨터 판독가능 매체는 예컨대 프로세서와 같은 컴퓨터에 의해 판독될 수 있는 것으로 이해된다.

이하에서는 본 발명의 상술한 양태들 전체에 속하는 특징들과 실시예들이 간략히 요약될 것이다.

상술한 바와 같이 각각의 후보 벡터는 하나 이상의 코드 벡터들의 개별 클래스와 연관된다. 여기서 코드 벡터들의 모든 클래스들의 코드 벡터들은 동일한 코드북으로부터 나온다. 상이한 다른 후보 벡터들과 각각 연관된 코드 벡터들의 클래스들은 예컨대 서로 상이할 수 있다. 코드 벡터들의 클래스들은 예컨대 코드북의 서로 다른 부분들을 형성하는 것으로 간주될 수 있다.

여기서, 후보 벡터들과 연관된 코드 벡터들의 클래스들 각각의 사이즈들은 동일하거나 적어도 부분적으로(즉, 적어도 후보 벡터들의 일부에 대해) 상이할 수 있다.

각각의 후보 벡터의 요소들은 예컨대 내림차순 또는 오름차순으로 소팅된다.

후보 벡터들의 요소들은 예컨대 비한정적으로 예를 들자면 모두 양이거나 모두 음이거나, 다른 (예컨대 소정의) 부호(sign) 규범을 따른다.

후보 벡터는 예컨대, 적어도 이 후보 벡터가 이 클래스 내 코드 벡터로서 구비되기 때문에 코드 벡터들의 관련 클래스와 연관된다고 간주될 수 있다. 이것은 예컨대 복수의 후보 벡터들의 모든 후보 벡터들의 경우에 해당할 수 있다.

적어도 한 후보 벡터가 둘 이상의 코드 벡터들의 개별 클래스와 연관된다. 그런 경우, 둘 이상의 코드 벡터들 중 하나는 둘 이상의 코드 벡터들 자체의 클래스와 관련된 후보 벡터이며, 또 다른 코드 벡터들 중 적어도 하나는 순열(예컨대 벡터의 요소들의 재정렬) 또는 부호 순열(예컨대 벡터의 요소들의 재정렬 및/또는 벡터의 요소들의 하나 이상의 부호들의 변화)를 통해 후보 벡터로부터 획득될 수 있는 코드 벡터이다. 이것은 후보 벡터와 연관된 코드 벡터들의 클래스가 후보 벡터를 포함하는 경우일 수 있으며, 여기서 코드 벡터들의 클래스의 모든 다른 코드 벡터들은 순열 또는 부호 순열에 의해 후보 벡터로부터 획득될 수 있다. 이것은 예컨대 복수의 후보 벡터들 중 일부나 모든 후보 벡터들과 각기 연관된 코드 벡터들의 클래스들에 해당할 수 있다.

적어도 하나의 후보 벡터는 예컨대 후보 벡터에 상응하는 하나의 코드 벡터만을 포함하는 하나 이상의 코드 벡터들의 클래스와 관련될 수 있다. 이 후보 벡터는 가령, (0 값의 요소들만을 가지는) 널(null) 벡터일 수 있다. 이 경우, 순열이나 부호 순열에 의해 어떤 추가 벡터들도 생성될 수 없다.

각기 복수의 후보 벡터들의 후보 벡터들과 연관된 코드 벡터들의 클래스들은 예컨대 모두 하나의 코드 벡터(가령, 널 벡터)만을 포함하는 코드 벡터들의 한 클래스를 제외한 둘 이상의 코드 벡터를 포함할 수 있다. 마찬가지로, 각기 복수의 후보 벡터들의 후보 벡터들과 연관된 코드 벡터들의 모든 클래스들 역시 둘 이상의 코드 벡터를 포함할 수 있다.

후보 벡터들 중 일부나 전부는 가령 각기 리더 클래스들과 연관되는 리더 벡터들일 수 있으며, 각각의 리더 클래스는 각기 복수의 하나 이상의 코드 벡터들을 포함한다. 리더 벡터는 예컨대 내림차순(또는 오름차순으로) 정렬된 양의 요소들을 가진 벡터일 수 있다. 리더 벡터와 연관된 리더 클래스는 예컨대 리더 벡터, 및 리더 벡터의 부호 순열을 통해 얻어지는 모든 벡터들을 포함할 수 있으며(이는 예컨대, 리더 벡터가 널 벡터인 경우, 어떤 부호 순열들도 가능하지 않고 그에 따라 리더 클래스가 널 벡터만을 포함한다는 것을 의미할 수 있음), 이때 부호 결합에는 예컨대 벡터 내 부호들의 개수가 쌍수나 홀수여야 한다는 것과 같은 어떤 제한조건이 존재할 수 있다. 리더 클래스들의 결합이 예컨대 코드북(가령, 격자 코드북)을 형성할 수 있다. 이 코드북은 예컨대 음성, 오디오 및/또는 비디오 신호들의 예컨대 양자화를 위해 사용될 수 있다.

대안적으로, 후보 벡터들의 일부나 전체가 예컨대 하나 이상의 리더 벡터들의 스케일링된 표현일 수 있다. 예를 들어, N 개의 리더 벡터들이 존재할 수 있고, 리더 벡터들 각각은 개별 리더 클래스와 연관되며, 이 리더 클래스들 각각은 다른 리더 클래스들과 동일하거나 상이할 수 있는 L 개의 서로 다른 스케일들(스케일링 요인들)의 집합과 연관된다. 여기서 코드북은 예컨대 N-L 개의 스케일링된 리더 클래스들의 결합으로서 형성될 수 있고, 리더 클래스들은 각기 리더 벡터들의 N-L 개의 스케일링된 표현들(이들은 각각이 동일한 리더 벡터에 속하는 리더 벡터들의 L 개의 스케일링된 표현들을 구비하는 N 개의 그룹들임)로 표현된다.

마찬가지로, 후보 벡터들 중 하나 이상이 리더 벡터들일 수 있고, 후보 벡터들 중 일부 또는 그 이상이 하나 이상의 리더 벡터들의 스케일링된 표현들일 수 있다.

복수의 후보 벡터들로부터 하나 이상의 타깃 벡터들이 식별된다. 따라서 타깃 벡터들이 후보 벡터들이다.

타깃 벡터들은 복수의 후보 벡터들의 모든 후보 벡터들 가운데에서, (거리 함수, 예컨대 미리 정해진 거리 함수에 따라) 입력 벡터의 적어도 소팅된 표현에 대해 최소 거리들을 가진다.

후보 벡터들로부터 하나 이상의 타깃 벡터들의 식별이 유용할 수 있는데, 이는 복수의 후보 벡터들 각각의 후보 벡터에 대해 해당 후보 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리가 입력 벡터에 대해-이 클래스의 코드 벡터들의 모든 코드 벡터들 사이에서- 최소 거리를 가지는 후보 벡터와 연관된 코드 벡터들의 클래스의 코드 벡터의 거리와 동일하기 때문이다.

오직 하나의 타깃 벡터만이 식별되면, 이 타깃 벡터는 입력 벡터의 적어도 소팅된 표현에 대해 최소 거리를 가진다. 또한 이 타깃 벡터는 여기서 코드북의 모든 코드 벡터들 사이에서 입력 벡터에 대해 최소 거리를 가지는 코드 벡터를 포함하는 코드 벡터들의 클래스와도 연관된다.

두 타깃 벡터들이 식별되는 경우, 이 두 타깃 벡터들은 여기서-복수의 후보 벡터들의 모든 후보 벡터들 사이에서- 입력 벡터의 적어도 소팅된 표현에 대해 두 개의 최소 거리들을 가진다. 이 거리들은 동일할 수 있으나, 마찬가지로 상이할 수도 있다. 마찬가지로 이것은 둘을 넘는 타깃 벡터들의 경우에 대해서도 유효하다.

타깃 벡터들이 (예컨대, 제1타깃 벡터가 입력 벡터에 대해 최소 거리를 가진 코드 벡터와 연관되고, 제2타깃 벡터가 입력 벡터에 대해 제2최소 거리를 가지는 코드 벡터와 연관되는 방식으로) 코드북의 모든 코드 벡터들 사이에서 입력 벡터에 대해 최소 거리들을 가지는 개별 코드 벡터들을 포함하는 코드 벡터들의 개별 클래스들과 반드시 연관되는 것은 아닐 수 있다. 예를 들어 두 개의 타깃 벡터들(상술한 바와 같이 제1타깃 벡터 및 제2타깃 벡터)이 식별되면, 그것은 그들이 입력 벡터와 관련하여 코드북으로부터 제1 및 제2의 최근접 코드 벡터들과 각기 연관되지 않고, 입력 벡터와 관련하여 코드북으로부터 제 및 오직 제3의 최근접 코드 벡터들과 연관되는 경우일 수 있다. 이것은 전체 코드북으로부터 제2의 최근접 코드 벡터가 제1타깃 벡터와도 연관될 수 있다는 사실에 기인한다. 그러나, 출원의 관점에서 이것은 관심 사항이 되지 않을 것인 바, 이는 동일한 타깃 벡터와 연관된 코드 벡터들은 그들의 표현에 대해 동일한 수의 비트들을 필요로 할 것이기 때문이다. 예컨대, 동일한 비트레이트가 사용되는 경우 품질(더 높은 왜곡/거리)에 대해 무시하는 것은 소용이 없을 수 있다(즉, 그러면 제1최근접 코드 벡터 및 그 보다 못하지 않은 제2최근접 코드 벡터가 사용되는 바, 이는 둘 모두 동일한 비트 수를 필요로 하기 때문임).

입력 벡터는 예컨대 본 발명의 제1양태에 따른 방법의 어느 단계에서 수신될 수 있고, 본 발명의 제2 또는 제3양태에 따른 장치들, 본 발명의 제4양태에 따른 컴퓨터 프로그램 및 본 발명의 제5양태에 따른 컴퓨터 판독가능 매체가 그에 따라 구성될 수 있다.

입력 벡터의 적어도 소팅된 표현은 예컨대 후보 벡터들의 요소들이 (가령, 내림차순이나 오름차순으로) 소팅되는 것과 같은 방식으로 자신의 요소들을 소팅하기만 함으로써 입력 벡터로부터 얻어질 수 있다. 입력 벡터의 적어도 소팅된 표현을 획득하기 위해, 그러나 하나 이상의 추가 변환 단계들, 예컨대 입력 벡터의 요소들을 후보 벡터들과 동일한 부호 기준(가령, 입력 벡터의 모든 요소들이 양이 되거나 모든 요소들이 음이 됨)을 따르도록 변환하는 단계 및 그에 따라 변환된 요소들을 예컨대 후보 벡터들의 요소들과 같은 방식으로 소팅하는 단계 역시 수행될 수 있다. 입력 벡터의 적어도 소팅된 표현은 그에 따라 예컨대, 입력 벡터의 소팅된 부호 변환된 표현, 예컨대 입력 벡터의 모든 요소들이 그들의 절대값들로 변환되고 이어서 소팅되는 입력 벡터의 소팅된 절대값 표현을 포함하는 것으로도 간주된다.

하나 이상의 타깃 벡터들이 식별되었으면, 각각의 타깃 벡터에 대해 (타깃 벡터와 연관된 코드 벡터들의 클래스 내 모든 코드 벡터들 사이에서) 입력 벡터에 대해 최소 거리들을 가지는 코드 벡터가 예컨대 입력 벡터에 의존하여 타깃 벡터의 요소들에 부호들을 할당 및/또는 요소들을 순열함으로써 정해질 수 있다. 하나 이상의 타깃 벡터들은 예컨대 다른 (가령, 기능) 유닛으로 추가적으로나 대안적으로 출력될 수 있다. 하나 이상의 타깃 벡터들은 예컨대, 하나 이상의 타깃 벡터들 각각의 식별자(가령 인덱스)를 출력함으로써 출력될 수 있다. 하나 이상의 타깃 벡터들은 예컨대 입력 벡터의 적어도 소팅된 표현에 대한 타깃 벡터의 개별 거리와 함께 출력될 수 있다. 이러한 거리들에 기반하여, 예컨대 최종적으로 선택된 타깃 벡터(이 최종적으로 선택된 타깃 벡터와 연관된 코드 벡터는 예컨대 입력 벡터의 양자화/부호화를 위해 사용됨)에 도달하기 위해 하나 이상의 타깃 벡터들로부터 하나 이상의 타깃 벡터들의 추가 선택이 가능할 수 있다.

상술한 본 발명의 양태들에 따라, 입력 벡터의 적어도 소팅된 표현이 복수의 후보 벡터들의 후보 벡터들 중 적어도 하나와 비교된다. 이러한 적어도 소팅된 표현은 예컨대 본 발명의 제1양태에 따른 방법의 어느 단계에서 생성될 수 있고, 본 발명의 제2 또는 제3양태에 따른 장치들, 본 발명의 제4양태에 따른 컴퓨터 프로그램 및 본 발명의 제5양태에 따른 컴퓨터 판독가능 매체가 그에 따라 구성될 수 있다.

그러나 복수의 후보 벡터들의 모든 후보 벡터들에 대한 입력 벡터의 거리가 산출되어야 하는 경우를 (가능하다면) 피하기 위해, 후보 벡터에 대해 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 긴지가 체크된다. 이러한 체크 동작은 타깃 벡터를 식별하기 위하여 예컨대 복수의 후보 벡터들의 모든 후보 벡터들이나 모든 후보 벡터들에서 하나의 사전선택되거나 임의 선택된 후보 벡터를 뺀 후보 벡터들을 체크하는 루프의 개별 반복을 통해 수행될 수 있다.

이 안에서 기준 벡터는 예컨대 입력 벡터의 적어도 소팅된 표현에 대해 지금까지 체크된 후보 벡터들 사이에서 입력 벡터의 적어도 소팅된 표현에 대해 최소 거리를 가진 복수의 후보 벡터들 중 한 후보 벡터일 수 있다. 입력 벡터의 적어도 소팅된 표현에 대해 지금까지 아무 다른 후보 벡터들이 체크되지 않았다면, 기준 벡터는 예컨대 복수의 후보 벡터들 중 미리 정의된 것이나 무작위로 선택된 것일 수 있다. 기준 벡터가 복수의 후보 벡터들 중 한 후보 벡터이나, 그것은 복수의 후보 벡터들의 후보 벡터들에 대해 수행되는 모든 체크 동작 중에 고정된 상태가 유지되는 것임이 또한 가능할 수 있다.

여기서, 체크 동작 중에 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리를 실제로 계산하는 것이 회피된다. 이는 계산상의 복잡도를 줄인다. 대신, 체크 동작은 후보 벡터 및 기준 벡터 사이의 거리 및 기준 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리에 적어도 기반하여 수행된다. 전자의 거리는 예컨대 후보 벡터들의 모든 쌍들 사이의 거리들(또는 기준 벡터 및 기준 벡터와 일치하지 않은 모든 후보 벡터들 사이의 거리들)을 포함하는 미리 계산된 데이터베이스로부터 검색될 수 있으며, 후자의 거리는 예컨대 기준 벡터에 대해 수행되는 이전의 체크 동작으로부터 이미 입수될 수 있다.

체크 동작에서, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리에 대한 실제 계산의 회피는 예컨대 삼각 부등식(또는 그 미분식)을 활용함으로써 달성될 수 있다.

체크 동작이 양의 결과를 산출하였으면(즉, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 더 크다는 것이 드러났으면), 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리는 산출되지 않으며, 그렇지 않은 경우는 산출된다.

복수의 후보 벡터들 중 하나 이상의 타깃 벡터들을 식별하기 위해, 입력 벡터의 적어도 소팅된 표현 및 모든 후보 벡터들 사이의 거리들이 반드시 계산될 필요는 없다. 대신, 이러한 계산 전에 체크 동작을 도입함으로써 거리의 실제 계산이 실제로 필요한지가 평가될 수 있다. 이러한 체크 동작의 일부 또는 전부는 이전 체크 동작들에서 이미 입수 가능한 거리들에 기반하거나, 후보 벡터들 및/또는 동일한 코드북이 사용되는 한 변하지 않고 그에 따라 미리 계산될 수 있는(예컨대 입력 벡터 수신 전에) 기준 벡터들 사이의 거리들을 참조할 수 있다.

여기서, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리는 입력 벡터 및 후보 벡터와 관련된 코드 벡터들의 클래스 내 최근접 코드 벡터 사이의 거리와 동일하다. 이것은 복수의 후보 벡터들 내 모든 후보 벡터들에 대해 유효하다. 따라서 (코드북의 모든 코드 벡터들을 체크하는 대신) 후보 벡터들을 체크하는 것으로 충분하다.

임의의 벡터들 간의 거리들은 예컨대 예를 들자면 유클리드 메트릭, 맨해튼 메트릭 또는 체비셰프 메트릭과 같은 예컨대 민코프스키 메트릭 같은 거리 메트릭에 따라 계산될 수 있다.

하나 이상의 타깃 벡터들과 관련된 코드 벡터들의 개별 클래스들의 코드 벡터들은 이제 예컨대 입력 벡터(가령 비디오 신호, 이미지 신호, 음성 신호 또는 오디오 신호일 수 있음)의 양자화 및/또는 부호화를 위한 기반으로서 기능할 수 있다.

본 발명의 제1양태에 따른 방법은 예컨대 하나 이상의 타깃 벡터들과 연관된 코드 벡터들의 개별 클래스들의 코드 벡터들에 기반하여 입력 벡터의 양자화 및/또는 부호화된 표현을 획득하기 위해 하나 이상의 타깃 벡터들에 기반하여 입력 벡터를 양자화 및/또는 부호화하는 단계를 포함할 수 있다. 본 발명의 제2 또는 제3양태에 따른 장치들, 본 발명의 제4양태에 따른 컴퓨터 프로그램 및 본 발명의 제5양태에 따른 컴퓨터 판독가능 매체가 그에 따라 구성될 수 있다. 예를 들어 하나의 타깃 벡터만이 얻어지면, 입력 벡터는 이 타깃 벡터와 연관된 코드 벡터들의 클래스의 어떤 코드 벡터, 예컨대 코드 벡터들의 이 클래스 내 모든 코드 벡터들 사이에서 입력 벡터에 대해 최소 거리를 가진 코드 벡터에 기반하여 양자화될 수 있다. 이 코드 벡터는 예컨대 입력 벡터의 양자화 및 부호화된 표현을 구성하는 식별자(가령, 비트 스트링)에 의해 표현될 수 있다. 여러 개의 타깃 벡터들이 식별되면, 입력 벡터의 부호화/양자화는 예컨대 (코드 벡터들의 개별 클래스의 코드 벡터들 가운데에서) 입력 벡터에 대해 최소 거리를 가지는 타깃 벡터들과 연관된 코드 벡터들의 개별 클래스들로부터 개별 코드 벡터들을 식별하는 단계, (예컨대 이 코드 벡터들을 나타내는데 필요한 개별 비트 수 및/또는 입력 벡터로부터 이 코드 벡터들의 개별 거리에 대한 고려 하에서) 이 식별된 코드 벡터들로부터 한 코드 벡터를 선택하는 단계, 및 선택된 코드 벡터를 식별자를 사용하여 표현하는 단계를 포함할 수 있다.

본 발명의 모든 양태들의 전형적 실시예에 따르면, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 큰지를 체크하는 단계는 후보 벡터 및 기준 벡터 사이의 거리 및 기준 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리 간의 차이에 대한 절대 값이 기준 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 큰지를 체크함으로써 수행된다. 이러한 종류의 체크 동작은 삼각 부등식으로부터 파생될 수 있다.

본 발명의 모든 양태들의 전형적 실시예에 따르면, 체크 동작 및 개별 체크 동작이 부정적 결과를 산출하는 경우 거리의 계산 동작은 예컨대 적어도 한번(가령 최초로 새로운 입력 벡터에 대해 식별이 수행될 때) 기준 벡터로서 사용되는 하나의 후보 벡터를 제외한 복수의 후보 벡터들의 모든 후보 벡터들에 대해 하나 이상의 타깃 벡터들에 대한 식별 시 수행될 수 있다. 기준 벡터의 역할을 하는 이 후보 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리는 그럼에도 불구하고 추후 참조를 위해 계산되어야 할 것이다.

본 발명의 모든 양태들의 전형적 실시예에 따르면, 기준 벡터는 복수의 후보 벡터들로부터 사전선택되거나 무작위로 선택된 후보 벡터이다. 기준 벡터는 예컨대 항상 복수의 후보 벡터들 중 제1후보 벡터이거나 가령 새 입력 벡터가 수신될 때마다 복수의 후보 벡터들 사이에서 무작위로 선택될 수 있다. 기준 벡터는 예컨대 복수의 입력 벡터들의 하나 이상의 특징들에 대한 분석에 기반하고/하거나 입력 벡터의 하나 이상의 통계적 특성들에 기반하여 복수의 후보 벡터들로부터 사전선택될 수도 있다.

본 발명의 전형적 실시예에 따르면, (하나 이상의 타깃 벡터들의) 식별 동작은 후보 벡터에 대한 체크 동작이 부정적 결과를 산출하는 경우, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 계산된 거리가 기준 벡터 미 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 작은지(또는 대안으로서 작거나 같은지)를 체크하는 동작, 및 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 계산된 거리가 기준 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 작은 경우(혹은 위에서 주어진 대안에서 작거나 같은 경우) 기준 벡터를 후보 벡터로 정의하는 동작을 더 포함한다.

입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 크다고 체크하는 동작이 부정적이면, 한편으로는 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리 및 다른 한편으로 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리간 관계에 대한 아무 정보도 사용 능하지 않을 것이다. 따라서, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리가 계산되고 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리와 비교되며, 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 계산된 거리가 기준 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 작으면 그 후보 벡터가 기준 벡터가 된다(기준 벡터가 재정의된다).

복수의 후보 벡터들의 개별 후보 벡터들에 대한 여러 체크 동작들이 수행될 때, 이것은 기준 벡터가 항상 입력 벡터의 적어도 소팅된 표현에 대해 최저 거리를 가진 후보 벡터임을 확실히 한다.

예컨대 오직 하나의 타깃 벡터만이 복수의 후보 벡터들로부터 식별될 수 있고, 타깃 벡터는 이때 복수의 후보 벡터들의 마지막 후보 벡터가 체크된 이후의 기준 벡터에 해당할 수 있다. 입력 벡터의 적어도 소팅된 표현에 대해 복수의 후보 벡터들 중 마지막 후보 벡터가 체크된 후, 기준 벡터는 그에 따라 코드북의 모든 코드 벡터들 가운데에서 입력 벡터에 대해 최소 거리를 가진 코드 벡터를 포함하는 코드 벡터들의 클래스와 연관되는 타깃 벡터를 나타낸다.

후보 벡터 및 기준 벡터 사이의 거리는 예컨대 복수의 후보 벡터들의 후보 벡터들의 모든 가능한 쌍들에 대한 거리들을 포함하는 메모리로부터 검색될 수 있다. 상기 거리들은 (예컨대 입력 벡터의 수신 이전에) 미리 계산될 수 있다. 상기 거리들은 예컨대 본 발명의 제1양태에 따른 방법을 구현하는 장치의 ROM이나 본 발명의 제2 및 제3양태에 따른 장치나 그러한 장치의 펌웨어 부분에 포함될 수 있다. 예컨대 코드북이 바뀌는 경우 그 거리들을 업데이트/변경하는 것이 가능할 수 있다. 후보 벡터들 사이의 거리들이 입력 벡터로부터 독립적이기 때문에, 현재의 입력 벡터의 적어도 소팅된 표현 및 기준 벡터 사이의 거리보다 큰지를 체크하는 동작을 수행하기 위해 그러한 거리들이 되풀이하여 계산되어야 하는 경우를 피하기 위해 현재의 입력 벡터의 적어도 소팅된 표현 및 후보 벡터 사이의 거리를 미리 계산하고 그들을 메모리에 저장하는 것이 계산상 효율적이고 따라서 바람직하다.

기준 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리가 복수의 후보 벡터들 중 앞서 체크된 후보 벡터 및 앞서 체크된 후보 벡터에 대해 계산된 입력 벡터의 적어도 소팅된 표현 사이의 거리에 해당할 수 있고, 적어도 일시적으로 저장된 경우 메모리로부터 검색될 수 있다. 이것은 후보 벡터들의 모든 쌍들 사이의 미리 계산된 거리들의 저장에 더하여(그러나 기본적으로 그로부터 독립적으로) 타깃 벡터의 식별에 대한 계산 상의 복잡도를 줄이는 데 추가로 크게 기여한다. 따라서 타깃 벡터의 식별은 그에 따라 예컨대 입력 벡터의 적어도 소팅된 표현 및 나중에 참조될 후보 벡터 사이의 계산 거리를 적어도 일시적으로 저장하는 동작을 더 포함한다.

본 발명의 모든 양태들의 한 전형적 실시예에 따르면, 입력 벡터와 관련하여 하나 이상의 타깃 벡터들의 식별 동작 시, 체크 동작은 복수의 후보 벡터들의 적어도 몇몇 후보 벡터들에 대해 수행되고, 이때 각각의 체크 동작 시 동일한 기준 벡터가 사용된다. 기준 벡터는 예컨대 복수의 후보 벡터들로부터의 어느 한 후보 벡터, 예컨대 널 벡터일 수 있다. 기준 벡터는 복수의 후보 벡터들로부터 미리 정의되거나 사전선택될 수 있다.

체크하는 동작은 예컨대, 기준 벡터로서 사용되는 후보 벡터를 제외하고 복수의 후보 벡터들의 모든 후보 벡터들에 대해 수행될 수 있다.

다른 대안으로서, 체크 동작은 예컨대 기준 벡터가 후보 벡터들 중 하나가 아닌 경우 복수의 후보 벡터들의 모든 후보 벡터들에 대해 수행될 수 있다. 체크 동작 시 동일한(가령, 일정한) 기준 벡터를 사용하는 것은 예컨대 하나가 넘는 타깃 벡터 및 그에 따라 결과적으로 입력 벡터에 대해 작은 거리들을 가진 하나가 넘는 코드 벡터들을 식별하는 것을 가능하게 할 수 있다. 이것은 예컨대 후보 벡터들과 각기 연관된 코드 벡터들의 클래스들 중 적어도 일부가 부호화를 위한 서로 다른 비트 수들의 여유가 되는 상황들에서 활용될 수 있다. 입력 벡터와 가깝다고 모두 간주될 수 있고 그에 따라 입력 벡터의 부호화/양자화된 표현으로서 적합할 수 있는 (적어도 부분적으로 상이한 비트 요건들을 가진 코드 벡터들의 서로 다른 클래스들로부터) 여러 코드 벡터들을 가질 때, 정확도 및 비트 요건들 사이의 타협이 이루어질 수 있다(예컨대 입력 벡터에 가장 가까운 코드 벡터를 선택하는 대신 입력 벡터로부터 더 먼 코드 벡터(가령, 두 번째 최근접 코드 벡터)가 선택될 수 있는데, 이는 그것이 더 적은 비트들을 필요로 하지만 여전히 비교적 정확한 입력 벡터의 표현을 이루기 때문이다).

후보 벡터 및 기준 벡터 사이의 거리는 이때 기준 벡터 및 복수의 후보 벡터들의 모든 후보 벡터들 사이의 거리들을 포함하는 메모리, 또는 기준 벡터가 후보 벡터들 중 하나인 경우 후보 벡터를 제외한 복수의 후보 벡터들의 모든 후보 벡터들 및 기준 벡터 사이의 거리들을 포함하는 메모리로부터 검색될 수 있다. 이 거리들이 입력 벡터로부터 독립적이기 때문에, 그 거리들은 예컨대 본 발명의 제2 및 제3양태에 따른 장치의 펌웨어 안에서 미리 계산될 수 있다(예컨대 입력 벡터가 수신되기 전에).

입력 벡터에 대한 하나 이상의 타깃 벡터들의 식별 시, 기준 벡터 및 입력 벡터의 적어도 소팅된 표현 사이의 거리는 단 한번만 계산될 수 있다. 입력 벡터에 대한 하나 이상의 타깃 벡터의 식별 중에 기준 벡터나 입력 벡터 어느 것도 바뀌지 않으므로, 이러한 거리를 단 한번만 (예컨대 최초 체크 동작 이전에) 계산하고 적어도 일시적으로 저장하고 그런 다음 다음 체크 동작 시 그것을 검색하도록 하는 것이 바람직하다.

본 발명의 모든 양태들의 전형적 실시예에 따르면, 본 발명의 제1양태에 따른 방법은 하나 이상의 타깃 벡터들 중 적어도 하나에 대해 코드 벡터들의 개별 클래스 내 모든 코드 벡터들 사이에서 입력 벡터에 대해 최소 거리를 가진 적어도 하나의 타깃 벡터와 연관된 코드 벡터들의 개별 클래스에 포함되는 개별 코드 벡터를 결정하는 동작을 더 포함할 수 있다. 본 발명의 다른 양태들에 따른 장치들, 컴퓨터 프로그램들 및 컴퓨터 판독가능 매체가 그에 따라 구성될 수 있다. 여기서 몇몇 타깃 벡터들이 식별되었더라도, 각자 연관된 코드 벡터들의 하위 그룹(가령, 오직 하나)을 실제로 결정하는 것만이 요망될 수 있다. 예를 들어 실제로 입력 벡터의 부호화/양자화된 표현으로서의 역할을 해야 하는 코드 벡터만이 그 관련 타깃 벡터에 기반하여 결정될 수 있다.

개별 코드 벡터의 결정은 예컨대, 타깃 벡터의 순열화된 표현을 얻기 위해 입력 벡터의 적어도 소팅된 표현에 대한 소팅을 취소할 개별 코드 벡터를 포함하는 코드 벡터들의 클래스와 연관된 타깃 벡터에 대해 순열 연산을 적용하는 단계; 타깃 벡터의 부호 순열화된 표현을 얻기 위해 입력 벡터 내 해당 위치들에 있는 요소들의 부호들에 해당하는 타깃 벡터의 순열화된 표현의 요소들로 부호들을 할당하는 단계, 및 타깃 벡터와 연관된 코드 벡터들의 클래스에 대해 부호 제약요건이 부과되는 경우에만, 그리고 부호 제약요건이 타깃 벡터의 부호 순열화된 표현에 의해 만족되지 않는 경우, 코드 벡터를 얻기 위해 타깃 벡터의 부호 순열화된 표현의 최소 요소의 부호를 토글(toggle)하는 단계 및 그렇지 않은 경우 타깃 벡터의 부호 순열화된 표현을 코드 벡터로서 간주하는 단계를 포함할 수 있다.

본 발명의 모든 양태들의 전형적 실시예들에 따르면, 입력 벡터는 비디오, 이미지, 오디오 및 음성 신호 중 적어도 하나를 적어도 부분적으로 나타낸다.

본 발명의 모든 양태들의 전형적 실시예에 따르면, 타깃 벡터의 식별은 3GPP(Third Generation Partnership Project) 음성 및 오디오 코덱, 특히 EVS(Enhanced Voice Service) 코덱의 일부를 형성한다.

본 발명의 모든 양태들의 기타 특성들은 이후 첨부된 도면과 함께 제시되는 본 발명의 실시예들에 대한 상세 설명으로부터 자명할 수 있으며 그를 참조하여 명료해질 수 있다. 그러나, 도면들은 예시의 목적만을 위한 것으로 첨부된 청구범위를 참조해야 할 본 발명의 한계에 대한 경계를 정하는 것으로서 계획된 것이 아니라는 것을 알아야 한다. 도면들이 축척비율 그대로 그려진 것은 아니며 다만 기술되는 구조들 및 과정들을 개념적으로 예시하기 위해 의도된 것이라는 것 역시 알아야 한다. 특히 도면들의 특성들의 존재가 본 발명에 대해 강제되는 특성들을 표현하는 것으로 간주되어서는 안 된다.

도 1은 본 발명의 일 실시예에 따른 장치의 개략도이다.
도 2는 본 발명의 일 실시예에 따른 방법의 흐름도이다.
도 3은 본 발명의 일 실시예에 따른 유형의 저장 매체이다.
도 4는 본 발명의 일 실시예에 따른 도 2의 흐름도의 단계 202의 처리 흐름도이다.
도 5는 본 발명의 일 실시예에 따른 세 개의 리더 클래스들로 이루어진 코드북의 예시도이다.
도 6은 본 발명의 다른 실시예에 따른 도 2의 흐름도의 단계 202의 처리 흐름도이다.
도 7은 본 발명의 일 실시예에 따른 네 개의 리더 클래스들로 이루어진 다른 코드북의 예시도이다.

도 1은 본 발명의 일 실시예에 따른 장치의 구성요소들을 개략적으로 도시한다. 장치(1)는 예컨대 음성, 오디오 및 비디오 신호들 중 적어도 하나를 부호화할 수 있는 전자 기기 또는 그러한 기기의 구성요소일 수 있다. 장치(1)는 특히 복수의 후보 벡터들로부터 하나 이상의 타깃 벡터들을 식별하도록 구성된다. 장치(1)는 예컨대 모듈로서 구현될 수 있다. 장치(1)의 비한정적 예들이 모바일 전화, PDA(personal digital assistant), 휴대형 멀티미디어(오디오 및/또는 비디오) 플레이어 및 컴퓨터(가령, 랩탑 또는 데스크탑 컴퓨터)이다.

장치(1)는 비한정적 예들로서 거론하면 예컨대 마이크로프로세서, 디지털 시그널 프로세서(DSP) 또는 ASIC(Application Specific Integrated Circuit)으로 구현될 수 있는 프로세서(10)를 포함한다. 프로세서(10)는 프로그램 메모리(11)에 저장되는 프로그램 코드를 실행하며, 예컨대 중간 결과들을 적어도 일시적으로 저장하지만 역시 예컨대 미리 정의되고/거나 미리 계산된 데이터베이스들을 저장하기 위한 작업 메모리로서 메인 메모리(12)를 사용한다. 메모리들(11 및 12)의 일부나 전부 역시 프로세서(10) 안에 포함될 수 있다. 메모리들(11 및/또는 12)은 예컨대 비한정적 예들로서 거론하자면 ROM(Read-Only Memory), RAM(Random Access Memory)으로서 구현될 수 있다. 메모리들(11 및 12) 중 하나나 둘 모두는 프로세서(10)에 고정적으로 연결되거나 프로세서(10)로부터 메모리 카드나 스틱의 형태로 착탈가능할 수 있다.

프로세서(10)는 프로세서가 다른 기능 유닛들로 정보를 제공하거나 수신하게 하는 입/출력(I/O) 인터페이스(13)를 더 제어한다.

이하에 기술되는 바와 같이, 프로세서(10)는 적어도 복수의 후보 벡터들로부터 하나 이상의 타깃 벡터들을 식별하기 위한 프로그램 코드를 실행할 수 있다. 그러나 프로세서(10)가 물론 다른 기능들을 처리할 수 있다. 예를 들어 프로세서(10)는 예컨대 샘플링 된 입력 값들에 기반하여 음성, 오디오 및 비디오 부호화 중 적어도 하나를 수행할 수 있다. 프로세서(10)는 추가적으로나 대안적으로 휴대형 통신 및/또는 멀티미디어 장치의 동작을 제어할 수 있다.

도 1의 장치(1)는 예컨대 장치(1)의 사용자가 프로세서(10)와 상호 동작하게 하는 사용자 인터페이스 또는 장치(1)가 무선 통신을 수행할 수 있게 하는 관련 무선 주파수(RF)를 이용한 안테나와 같은 구성요소들을 더 포함할 수 있다.

장치(1)의 구성요소들에 의해 형성된 회로는 이 명세서의 말미에 더 기술되는 바와 같이 하드웨어만으로, 혹은 부분적으로 하드웨어 및 소프트웨어로, 혹은 소프트웨어만으로 구현될 수 있다.

도 2는 본 발명의 일 실시예에 따른 방법의 흐름도(200)를 도시한다. 이 흐름도(200)의 단계들은 예컨대 도 3에 도시된 바와 같이 유형의 저장 매체(30) 상에 저장된 컴퓨터 프로그램(31)의 개별 프로그램 코드(32)에 의해 정의될 수 있다. 유형의 저장 매체(30)는 예컨대 도 1의 프로그램 메모리(11)를 구현할 수 있으며 그러면 컴퓨터 프로그램(31)이 여기서 도 1의 프로세서(10)에 의해 실행될 수 있다.

도 2로 돌아갈 때, 단계 201에서 입력 벡터가 획득된다. 이 입력 벡터는 예컨대 (가령 도 1의 I/O 인터페이스(13)를 통한) 수신을 통해 얻어지거나 프로세서(10)에 의해 실행되는 프로세스나 프로그램으로부터 내부적으로 얻어질 수 있다. 이러한 프로그램 프로세스는 예컨대 부호화 프로세스의 일부일 수 있다. 입력 벡터는 음성, 오디오, 이미지 및/또는 비디오 신호의 적어도 일부를 나타낼 수 있다. 입력 벡터는 예컨대 몇 가지 예들을 거론하자면 음성 신호의 차동 스펙트럼 데이터나 라인 스펙트럼 주파수(LSF) 계수들을 포함할 수 있다.

단계 202에서, 복수의 후보 벡터들로부터 하나 이상의 타깃 벡터들이 단계 201에서 얻어진 입력 벡터에 대해 식별된다. 여기서 각각의 후보 벡터(가령, 리더 벡터)는 코드 벡터들의 개별 클래스(가령, 리더 벡터와 연관된 리더 클래스)와 연관되며, 여기서 코드 벡터들의 이러한 클래스의 코드 벡터들은 후보 벡터이거나 추가 제한이 적용될 수 있는 경우) 순열 또는 부호 순열에 의해 이 후보 벡터로부터 얻어질 수 있다.

여기서, 만일 후보 벡터가 널 벡터이면 그 관련 코드 벡터들의 클래스는 널 벡터 자체만을 포함한다. 코드 벡터들의 이러한 클래스들의 결합이 코드북을 형성한다. 입력 벡터에 대해 최소 거리를 가진 이러한 코드북 내 코드 벡터를 식별하기 위해, 모든 후보 벡터들로부터 입력 벡터의 소팅된 절대값 표현에 대해 최소 거리를 가진 후보 벡터인 소위 타깃 벡터를 식별하며 그런 다음 타깃 벡터에 기반하여 입력 벡터에 대한 최소 거리를 가진 코드 벡터를 판단하는 것으로 충분할 수 있다. 이하에서 도 4를 참조하여 설명되는 바와 같이, 타깃 벡터를 식별하는 이러한 프로세서의 계산상의 복잡도가 본 발명의 실시예들에 따라 크게 감소될 수 있다. 또한 이하에서 도 6을 참조하여 보여지는 것과 같이 입력 벡터와 가까운 여러 개의 코드 벡터들이 식별되어야 한다면 복수의 후보 벡터들로부터 여러 타깃 벡터들을 식별하는 것 역시 가능하다.

단계 203에서, 단계 202에서 식별된 하나 이상의 타깃 벡터들이 가령 도 1의 I/O 출력(3)을 통해 다른 구성요소로, 또는 내부적으로 프로세서(10)에 의해 실행되는 프로그램의 다른 프로세스로 제공될 수 있다. 대안적으로나 추가적으로 하나 이상의 타깃 벡터들에 기반하는 또 다른 프로세싱이 (프로세서(10)에 의해) 수행될 수 있다. 예를 들어 하나의 타깃 벡터만이 식별되는 경우, 입력 벡터에 대해 최소 거리를 가진 코드 벡터가 타깃 벡터에 기반하여 결정될 수 있다. 이 코드 벡터는 예컨대 인덱스와 같은 개별 식별자와 결부될 수 있으며, 이 식별자는 여기서 입력 벡터의 부호화 및 양자화된 표현을 나타낼 수 있다. 그런 다음 이 표현은 가령 장치(1)(도 1 참조)의 I/O 인터페이스를 통해 출력되거나 프로세서(1)에 의해 더 처리될 수 있다. 하나를 넘는 타깃 벡터가 식별되는 경우, 각자 연관된 코드 벡터들이 그 타깃 벡터들에 기반하여 결정되거나, 한 타깃 벡터(및 그 관련 코드 벡터)에 대한 선택이 예컨대 코드 벡터를 나타내기 위해 요구되는 비트 개수 및 입력 벡터에 대한 코드 벡터의 거리 간의 절충에 기반하여 수행될 수 있다.

도 4는 본 발명의 일 실시예에 따라 복수의 후보 벡터들로부터 단일 타깃 벡터를 식별하기 위한 방법의 흐름도(400)를 도시한다. 여기서, 처음에 사전선택된 후보 벡터가 기준 벡터로서 사용되나 이 기준 벡터는 흐름도(400)의 실행 중에 바뀔 수 있다.

흐름도(400)는 예컨대 장치(1)(도 1 참조)의 프로세서(10)에 의해 도 2의 흐름도(200)의 단계(202)에서 수행될 수 있다. 그에 따라 흐름도(400)의 단계들은 도 3의 유형의 저장 매체(30) 상에 저장되는 컴퓨터 프로그램(31)의 프로그램 코드(32)로서 구현될 수 있다.

흐름도(400)의 설명을 위해, 타깃 벡터가 선택되어야 하는 N 개의 후보 벡터들 {c₁,...,c_N}이 존재한다고 가정한다. 여기서 N은 1보다 큰 정수이다. 이 예에서, 각각의 후보 벡터는 내림차순으로 소팅되는 양의 요소들만을 가지며, 그에 라 후보 벡터의 제1요소는 제2요소보다 크며, 제2요소는 다시 제3요소보다 큰 방식으로 소팅된다. 각각의 후보 벡터는 후보 벡터 및 후보 벡터의 요소들의 부호 순열을 통해 얻어지는 추가 코드 벡터들을 포함하는 코드 벡터들의 클래스와 연관된다고 가장한다. 후보 벡터들 중 하나 이상에 대해, 예컨대 이 후보 벡터들에 대한 음의 부호들의 개수가 쌍수이거나 홀수여야 하는 방식(즉, 이들의 부호 순열)으로 부호 제약이 존재할 수 있다.

단계 401에서 입력 벡터(가령, 도 2의 단계(201)에서 얻어진 입력 벡터)는 이 예에서 입력 벡터의 소팅된 절대값 표현인 적어도 한 소팅된 표현으로 변환된다. 이러한 소팅된 절대값 표현은 이하에서 x로 표시될 것이며, 그 요소들의 개별 절대값을 형성하고 이 절대값 요소들을 후보 벡터들의 소팅에 매칭하도록, 즉 이 예에서 내림차순으로 소팅함으로써 입력 벡터로부터 얻어진다.

단계 402에서 기준 벡터 c_ref가 정의된다. c_ref는 도 4에 도시된 것과 같은 후보 벡터들 {c₁,...,c_N}의 집합 중 제1후보 벡터로서 정의될 수 있으나 이것이 의무사항은 아니다.

단계 403에서 거리 d_{ref , x}는 계산되어 (예컨대 장치(1)의 메인 메모리에-도 1 참조) 저장된다. d_{ref , x}는 거리 메트릭을 기준 벡터 c_ref 및 소팅된 절대값 입력 벡터 x에 적용함으로써 구해진다. 도 4의 흐름도 400에 대한 설명을 위해 이러한 거리 메트릭은 유클리드 메트릭이라 가정하나, 이는 단지 예일 뿐으로 다른 메트릭들 역시 적용 가능하다.

단계 404에서 루프 변수 i는 2에 해당하는 것으로 설정된다.

단계 405에서 거리 d_{i , ref}가 데이터베이스로부터 검색된다. 거리 d_{i , ref}는 후보 벡터 c_i 및 기준 벡터 c_ref 사이의 거리를 나타낸다. 후보 벡터 c_i 및 기준 벡터 c_ref가 모두 소팅된 절대값 입력 벡터 x와 독립적인 후보 벡터들이므로(단계 402 참조), 이 거리 및 모든 가능한 후보 벡터들의 쌍들 사이의 거리 역시 미리 계산되어 메모리, 예컨대 도 1의 장치(1)의 메인 메모리(12)에 저장된다. 이 거리들은 예컨대 도 1의 장치(1)의 펌웨어 안에 포함될 수 있고 후보 벡터들의 집합이 바뀌는 경우에만 변경되거나 업데이트될 수 있다. 그러나 예컨대 서로 다른 타입의 신호들의 코딩이나 서로 다른 양자화 세분도를 가지는 코딩을 위해 서로 다른 후보 벡터들의 집합들이 존재하는 경우, 이들 후보 벡터들의 집합 각각에 대해 각각의 후보 벡터들의 집합 내 모든 가능한 쌍들의 해당 거리들이 미리 계산되어 저장될 수 있다.

단계 406에서, 거리 d_{i , ref} 및 거리 d_{ref ,x} 사이의 차이에 대한 절대값이 거리 d_ref,x보다 큰지 여부가 체크된다. 이러한 체크는 후보 벡터 c_i 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_{i ,x}가 c_ref 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_{ref ,x}보다 클 것인지 여부를 나타낸다. 따라서 거리 d_{i ,x}의 실제 계산은 그것이 확실하게 거리 d_{i , ref}보다 크지 않은 경우에만 이치에 맞다. 여기서, 단계 405에서만 수행되는 체크 동작은 단계 405에서 미리 계산된 데이터베이스로부터 검색되었던 d_{i , ref} 및 단계 403에서 이미 계산되어 저장되었던 d_{ref ,x}에 기반한다(루프 변수 i의 상위 값들에 대해, d_{ref ,x}가 단계 403의 계산 또는 이하에 논의되는 바와 같은 단계 408의 사전 계산으로부터 입수가능하다). 따라서 단계 406에서 수행되는 체크 동작은 계산 방식이 손쉽다.

단계 406에서 수행되는 체크 동작은 아래 식과 같이 벡터들 c_i, c_ref 및 x에 적용되는 삼각 부등식으로부터 도출될 수 있다.

이것은 다음 식과 등가이다.

이하의 식이 유지되면 거리 d_{i ,x}는 거리 d_{ref ,x} 보다 큰 것이다.

그 경우, 부등식 (3)을 부등식 (2)의 첫 번째 부분에 넣을 때 d_{ref ,x} < d_{i ,x}가 유지되는 것을 알 수 있기 때문에 d_{i ,x}를 계산할 필요가 없다.

단계 406의 체크 동작이 부정적 결과를 산출하면, 현재의 후보 벡터 c_i 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_{i ,x}는 당연히 현재의 후보 벡터 c_i 및 기준 벡터 c_ref (이때까지 최선의 후보 벡터) 사이의 거리 d_{i , ref} 보다 크지 않다. 실제로 이들 두 거리 사이의 관계에 대한 어떤 정보도 전혀 입수가능하지 않다.

결과적으로 현재의 후보 벡터 c_i 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_i,x는 단계 407에서 계산되고 단계 408에서 거리 d_{ref ,x}와 비교된다. 이 체크 동작으로 거리 d_{i ,x}가 거리 d_{ref ,x}보다 작다는 것이 드러나면, (기준 벡터 c_ref는 항상 소팅된 절대값 입력 벡터에 가장 근접하다고 지금까지 체크된 후보 벡터로 간주된다는 사실을 반영할 때) 현재의 후보 벡터 c_i가 단계 409에서 새 기준 벡터 c_ref로 만들어지고, 이 현재의 후보 벡터 c_i 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_{i ,x}는 단계 410에서 (단계 406에 의한 참조를 위해) 거리 d_{ref ,x}로서 저장된다. 단계 408의 체크 동작에서 거리 d_{i ,x}가 거리 d_{ref ,x}보다 작지 않다는 것이 드러나면, 단계들 409-410은 건너 띄게 된다.

단계 411에서 루프 변수 i가 이미 N에 도달하였는지, 즉 모든 후보 벡터들이 이미 체크되었는지가 체크된다. 해당사항이 없으면, 루프 변수 i는 단계 412에서 1만큼 증가되고 흐름도는 다음 후보 벡터를 체크하기 위해 다시 단계 405로 건너간다. 단계 411의 체크동작에서 루프 변수 i가 N과 동일하다는 것이 드러나면, 단계 413에서 기준 벡터가 타깃 벡터가 되고 흐름도는 종료된다.

단계 406의 체크 동작이 정의 결과를 산출하면, 현재의 후보 벡터 및 소팅된 절대값 입력 벡터 사이의 거리 d_{i ,x}에 대한 계산은 그것이 거리 d_{ref ,x}보다 클 것이기 때문에 필요로 되지 않는다. 흐름도는 이제 단계 411로 점프한다.

도 4의 단계 408에서 조건 "d_{i ,x} < d_{ref ,x}"가 (대안으로서) "d_{i ,x} ≤ d_{ref ,x}"로도 변경될 수 있을 것이라는 것을 알아야 한다. 그러면 도 4의 흐름도(400)에 의해 여전히 오직 하나의 타깃 벡터가 식별될 것이다. 그럼에도 불구하고 입력 벡터 x의 소팅된 절대값 표현에 대해 동일한 거리를 가지는 하나 이상의 다른 후보 벡터들이 존재하더라도 기준 벡터가 타깃 벡터로서 식별되게 강제하기 위해 예컨대 조건 "d_{i ,x} < d_{ref ,x}"를 사용하는 것이 바람직할 것이다. 이것은 예컨대 기준 벡터(또는 그와 연관된 하나 이상의 코드 벡터들)가 다른 후보 벡터들(또는 그들과 각기 연관된 하나 이상의 코드 벡터들)과 비교하여 보다 적은 비트들이 식별되는 것을 요하는 경우 및/또는 기준 벡터(또는 그와 연관된 하나 이상의 코드 벡터들)의 식별이 미리 계산되거나 다른 후보 벡터들(또는 그와 각기 연과된 하나 이상의 코드 벡터들)의 식별과 비교하여 보다 쉽게 결정되는 경우 유리할 수 있다.

상술한 바와 같이 후보 벡터들은 각자 개별 후보 벡터들 및 부호 순열(코드 벡터의 음의 부호의 개수와 관련한 어떤 가능한 제약조건을 가짐)을 통해 개별 후보 벡터들로부터 얻어질 수 있는 추가 코드 벡터들을 포함하는 코드 벡터들의 개별 클래스들과 관련된다. 이러한 코드 벡터들 모드가 함께 코드북을 형성한다. 이제 도 4의 흐름도(400)에 의해 식별되는 타깃 벡터에 기반하여 (예컨대 도 2의 흐름도(200)의 단계 203과 같이) 입력 벡터에 대한 최소 거리를 가지는 실제 코드 벡터를 결정하기 위해 예컨대 이하의 단계들이 적용될 수 있다.

(a) 소팅된 절대값 입력 벡터 x를 다시 비소팅(그러나 여전히 절대값) 형태로 전환할 순열 동작이 타깃 벡터 c_target의 요소들에 대해 수행된다.

(b) 오리지널 입력 벡터의 요소들이 음의 부호를 가지는 경우 그 개별 음의 부호가 해당 위치들에 있는 순열화된 타깃 벡터의 요소들에 할당된다.

(c) (예컨대 코드 벡터 내 음의 부호들의 개수와 관련하여) 타깃 벡터 ctarget과 연관된 코드 벡터들에 부과되는 부호 제약조건들이 존재하는 경우, 이 부호 제약조건들은 그에 따라 단계 (b)에서 얻어진 벡터의 최소 요소의 부호를 토글함으로써 충족된다.

그에 따른 벡터는 코드북으로부터 입력 벡터에 대해 최소 거리를 가지는 코드 벡터이다.

타깃 벡터가 식별되는 후보 벡터들이 예컨대 리더 벡터들(예컨대 위에서 인용된 참고 문헌 "LSF 양자화에 대한 응용을 가진 다중 스케일 리더 격자 구조 VQ(Multiple-scale leader-lattice VQ with application to LSF quantization)"에서 정의된 것과 같은 리더 벡터들)일 수 있다는 것을 이미 언급하였다. 마찬가지로, 후보 벡터들은 다시 하나 이상의 스케일들의 집합과 연관된 리더 클래스들과 연관되는 스케일링된 리더 벡터들일 수 있다. 그러한 리더 클래스들의 예들 역시 위에서 언급한 참고 문헌 "LSF 양자화에 대한 응용을 가진 다중 스케일 리더 격자 구조 VQ(Multiple-scale leader-lattice VQ with application to LSF quantization)"에 제시되어 있다. 모든 리더 벡터들에 대해 하나의 공통 스케일이 존재하는 경우, (리더 벡터들을 스케일링하는 대신) 입력 벡터가 그에 따라 스케일링될 수 있으며 도 4의 흐름도가 비스케일링의 경우(그러나 변경된 입력 벡터를 가짐)에서와 같이 (후보 벡터들로서) 리더 벡터들을 이용하여 수행될 수 있다.

후보 벡터들이 부분적으로 리더 벡터들이고 부분적으로 스케일링된 리더 벡터들이 되는 것 역시 가능하다. 이러한 모든 시나리오들에 대해 도 1-4의 실시예들(및 이하에 기술되는 도 6의 실시예 역시)이 적용될 수 있다.

이하에서는 도 5를 참조하여, 후보 벡터들의 집합으로부터 단일 타깃 벡터의 식별 및 그 타깃 벡터에 기반하여 입력 벡터에 대한 최소 거리를 가지는 코드 벡터의 결정을 위한 예가 모든 후보 벡터들이 리더 벡터들이라는 가정 하에서 주어질 것이다.

도 5는 서로 다른 부호들로 표현되는 복수의 이차원 코드 벡터들을 가진 데카르트 좌표 시스템(50)을 도시한다. 코드 벡터들은 세 개의 서로 다른 리더 클래스들에 속하며, 이 리더 클래스들의 결합이 코드북을 형성한다.

제1리더 클래스는 별표로 표시되는 네 개의 코드 벡터들로서 좌표 [4,0]을 가지는 리더 벡터(51)로부터 부호 순열을 통해 도출된다. 이 제1리더 클래스는 다음과 같은 코드 벡터들을 가진다: { [ 4 , 0 ] , [ 0 , 4 ] , [ -4 , 0 ] , [ 0 , -4 ] }. 어떤 부호 제약조건도 존재하지 않음이 명백하다. 리더 벡터 [4,0]은 내림차순으로 정렬된 양의 요소들만을 가진다는 것을 알 수 있다. 이것은 이하에 기술되는 제2 및 제3리더 클래스의 리더 벡터들에도 해당한다.

제2리더 클래스는 원으로 표시되는 여덟 개의 코드 벡터들로서 좌표 [3,1]을 가지는 리더 벡터(52)로부터 부호 순열을 통해 도출된다. 이 제2리더 클래스는 다음과 같은 코드 벡터들을 가진다: {[3,1], [1,3], [-1,3], [-3,1], [-3,-1], [-1,-3], [1,-3], [3, -1] }. 어떤 부호 제약조건도 존재하지 않음이 명백하다.

제3리더 클래스는 점으로 표시되는 네 개의 코드 벡터들로서 좌표 [2,2]을 가지는 리더 벡터(53)로부터 부호 순열을 통해 도출된다. 이 제3리더 클래스는 다음과 같은 코드 벡터들을 가진다: {[2,2], [-2,2], [-2,-2], [2,-2]}. 어떤 부호 제약조건도 존재하지 않음이 명백하다.

이제 입력 벡터에 대해 최소 거리를 가진 (도 5의 16 개의 코드 벡터들로 나타낸) 코드북의 코드 벡터가 결정되어야 할 경우, 이것은 다음의 동작들을 통해 이행될 수 있다

- 모든 세 개의 리더 벡터들에 대한 입력 벡터의 소팅된 절대값 표현 사이의 거리를 계산,

- 가장 작은 거리를 도출하는 리더 벡터를 선택, 및

- 이 선택된 리더 벡터에 기반하여 코드 벡터를 결정.

예로 든 입력 벡터 [0,-3.5](도 5에 도시되지 않음)에 대해 이러한 접근방법을 수행함으로써 다음과 같은 모양을 취하게 될 것이다:

소팅된 절대값 입력 벡터가 [3.5,0]으로서 얻어질 것이다.

제1리더 벡터 [4,0]에 대해 이 소팅된 절대값의 입력 벡터 [3.5,0]의 거리(여기서 유클리드 메트릭이 일례로서 사용됨)는 0.5가 될 것이다.

제2리더 벡터 [3,1]에 대한 소팅된 절대값의 입력 벡터 [3.5,0]의 거리는 1.12가 될 것이다.

제3리더 벡터 [2,2]에 대한 소팅된 절대값의 입력 벡터 [3.5,0]의 거리는 2.5가 될 것이다.

따라서 제1리더 벡터가 소팅된 절대값의 입력 벡터에 대해 최소 거리를 낳기 때문에 제1리더 벡터가 선택될 것이다.

그에 따라 소팅된 절대값의 입력 벡터 [3.5,0]를 절대값의 입력 벡터 [0,3.5]로 다시 변환하는 방식으로 제1리더 벡터 [4,0]의 요소들을 순열함으로써 이러한 제1리더 벡터와 연관된 제1리더 클래스 내 코드 벡터가 획득된다, 즉 제1리더 벡터 [4,0]가 [0,4]로 순열화된다.

그런 다음 입력 벡터 [0,-3.5]의 요소들의 부호들이 순열화된 제1리더 벡터 [0,4] 내 같은 위치에 있는 요소들로 할당됨으로써 코드 벡터 [0, -4]를 도출한다.

알 수 있듯이 도 5의 16 개의 코드 벡터들 전체 가운데에서 코드 벡터 [0,-4]가 입력 벡터 [0,-3.5]에 대해 최소 거리를 가지는 것이다.

그러나 이러한 발견은 삼각 부등식이 활용되지 않았기 때문에 이차원 공간 내 세 개의 거리들에 대한 명시적 산출을 요하였다.

반대로, 본 발명의 실시예들에 따라 입력 벡터 [0,-3.5]에 대해 최소 거리를 가진 코드 벡터를 결정할 때, 이하에서 도 4의 흐름도를 참조하여 보여지게 되듯이 계산 상의 복잡도가 더 줄어들 수 있다.

여기서 세 개의 리더 벡터들 [4,0], [3,1] 및 [2,2] 사이의 거리들이 미리 계산되어 데이터베이스에 저장된다고 가정하므로, 현재의 예에 계산상의 복잡도를 더한다고 간주되지 않는다.

단계 401에서(도 4 참조) 소팅된 절대값의 입력 벡터 x=[3.5,0]는 입력 벡터 [0,-3.5]에 기반하여 결정된다.

단계 402에서 기준 벡터 cref는 제1리더 벡터 [4,0]와 동일하게 설정된다.

단계 403에서 기준 벡터 [4,0]와 소팅된 절대값의 입력 벡터 [3.5,0] 사이의 거리는 0.5로 판단된다.

단계 404에서, 루프 변수 i는 2로 증가되는데 이는 이제 제2리더 벡터가 체크된다는 것을 의미한다.

단계 405에서 제1 및 제2리더 벡터 사이의 미리 계산된 거리가 검색되며, 그것은 1.41에 달한다.

단계 406에서의 체크 동작은 (1.41-0.5)가 0.5보다 크기 때문에 양의 결과를 산출한다. 따라서 제2리더 벡터 및 소팅된 절대값의 입력 벡터 사이의 거리는 계산되지 않는다(단계 407이 실행되지 않는다). 대신 흐름도가 단계 411로 건너가고 그런 다음 다음 412로 가며, 여기서 i는 3으로 증가된다.

이것은 현재 제3리더 벡터가 체크됨을 의미한다. 이러한 목적을 위해 제1리더 벡터 및 제3리더 벡터 사이의 미리 계산된 거리가 단계 405에서 검색되고 그것은 2.82에 달한다.

단계 406에서의 체크 동작은 (2.8-0.5)가 0.5보다 크기 때문에 다시 정이 된다. 따라서 제3리더 벡터 및 소팅된 절대값의 입력 벡터 사이의 거리는 계산되지 않는다(단계 407이 실행되지 않는다). 대신 흐름도는 단계 411로 건너가고 그런 다음, 리더 벡터의 개수 N이 3(i와 같은)이므로 단계 413으로 가며, 여기서 기준 벡터 cref(단계 402에서 설정된 바와 같이 여전히 제1리더 벡터 [4.0])가 타깃 벡터 ctarget으로 정의된다.

이러한 제1리더 벡터 [4.0]에 기반하여, 입력 벡터 [0,-3.5]에 대해 최소 거리를 가진 코드북의 코드 벡터 [0,-4]가 위에서 도시된 바와 같이 순열 및 부호 할당을 통해 결정될 수 있다.

따라서 소팅된 절대값의 입력 벡터에 대한 모든 세 개의 리더 벡터들의 거리를 계산하고 이 결과들을 서로 비교하는 대신, 제1리더 벡터 및 소팅된 절대값의 입력 벡터 사이의 거리만이 계산되고 각각의 리더 벡터에 대해 이미 계산된 값들의 비교가 수행되어야 한다는 것을 알 수 있다. 단계 406에 포함된 추가 계산(차 및 그 절대값을 형성하는 것 같은 계산)은 특히 리더 벡터들의 차원들(요소들의 개수들)이 증가하는 경우 무시할 수준의 계산적 복잡도를 가진다.

상기 예로부터 계산적 복잡도의 감소량은 리더 벡터들이 체크되는 순서에도 좌우된다는 것을 알 수 있을 것이다. 만약 최선의 리더 벡터가 먼저 체크되는 경우(상기 예에서와 같이), 다른 리더 벡터들에 대한 거리들이 계산될 필요가 없고 계산 복잡도의 감소는 최대가 된다. 그러나, 최선의 리더 벡터가 먼저 체크되지 않는 경우에도 여전히 상당한 계산 복잡도의 감소가 이뤄지는데, 이는 앞서 체크된 리더 벡터들과 비교할 때 소팅된 절대값의 입력 벡터에 대해 확실히 보다 큰 거리를 가지지 않는 리더 벡터들에 대해서만 이러한 거리가 실제로 계산되기 때문이다.

도 6은 본 발명의 일 실시예에 따라 복수의 후보 벡터들로부터 하나 이상의 타깃 벡터들을 식별하기 위한 방법의 흐름도(600)를 도시한다. 이때 모든 체크 동작들에서 동일한 후보 벡터가 기준 벡터로서 사용된다. 도 4의 흐름도 400와 대조적으로, 이것은 하나를 초과하는 타깃 벡터(및 역시 입력 벡터에 근접한 하나를 초과하는 코드 벡터)의 잠정적 식별을 가능하게 한다. 그러나 식별된 타깃 벡터들의 실제 개수는 이하에 기술되는 바와 같이, 무엇보다 기준 벡터의 선택에 좌우된다.

흐름도(600)는 예컨대 장치(1)(도 1 참조)의 프로세서(10)에 의해 도 2의 흐름도(200)의 단계(202)에서 수행될 수 있다. 그에 따라 흐름도(600)의 단계들은 도 3의 유형의 저장 매체(30) 상에 저장되는 컴퓨터 프로그램(31)의 프로그램 코드(32)로서 구현될 수 있다.

흐름도(600)의 설명을 위해, 하나 이상의 타깃 벡터들이 선택되어야 하는 N 개의 후보 벡터들 {c₁,...,c_N}이 존재한다고 가정한다. 여기서 N은 1보다 큰 정수이다. (일례로서) 각각의 후보 벡터는 다시, 내림차순으로 소팅되는 양의 요소들만을 가지며, 그에 따라 후보 벡터의 제1요소는 제2요소보다 크고, 제2요소는 다시 제3요소보다 큰 방식으로 소팅된다. 각각의 후보 벡터는 후보 벡터 및 후보 벡터의 요소들의 부호 순열을 통해 얻어지는 추가 코드 벡터들을 포함하는 코드 벡터들의 클래스와 연관된다고 가장한다. 후보 벡터들 중 하나 이상에 대해, 예컨대 이 후보 벡터들에 대한 음의 부호들의 개수가 쌍수이거나 홀수여야 한다는 방식으로(즉, 이들의 부호 순열들에 따라) 부호 제약이 존재할 수 있다. 개별 후보 벡터만을 포함하고 어떤 추가 코드 벡터들도 포함하지 않는 코드 벡터들의 클래스들과 연관되는 N 개의 후보 벡터들의 집합 내 하나 이상의 후보 벡터들이 또한 존재할 수 있다(예컨대 후보 벡터가 널 벡터인 경우 어떤 추가 코드 벡터들도 부호 순열을 통해 얻어질 수 없다).

흐름도(600)의 단계 601에서, 입력 벡터(예컨대 도 2의 단계 201에서 얻어진 입력 벡터)는 자신의 요소들의 개별 절대값을 형성하고 이 절대값의 요소들을 후보 벡터들의 소팅에 매칭하도록 소팅, 즉 이 예에서 내림차순으로 소팅함으로써 소팅된 절대값의 입력 벡터 x(입력 벡터의 적어도 소팅된 표현의 일례임)로 변환된다.

단계 602에서 타깃 벡터들에 대한 카운터 변수 j가 1로 설정된다.

단계 603에서 기준 벡터 c_ref가 정의된다. c_ref는 도6에 도시된 것과 같은 후보 벡터들 {c₁,...,c_N}의 집합 중 제1후보 벡터로서 정의될 수 있으나 이것이 의무사항은 아니다. 이 기준 벡터 c_ref는 흐름도(600)의 모든 다음 동작들에 있어서 일정하게 유지된다.

단계 604에서 거리 d_{ref , x}가 계산된다 (예컨대 장치(1)의 메인 메모리에서-도 1 참조). 저장된다. d_{ref , x}는 거리 메트릭을 기준 벡터 c_ref 및 소팅된 절대값 입력 벡터 x에 적용하으로써 구해진다. 도 6의 흐름도 600에 대한 설명을 위해 이러한 거리 메트릭은 유클리드 메트릭이라 가정하나, 이는 단지 예일 뿐으로 다른 메트릭들 역시 적용 가능하다.

단계 605에서 변수 ind_j가 1로 설정되어 저장된다. 또한 변수 dist_j가 d_{ref ,x}와 동일하게 설정되어 저장된다. j=1일 때(단계 602 참조) 변수들 ind_j 및 dist_j의 쌍은 도 6의 흐름도 600에 의해 식별되는 제1타깃 벡터를 나타내며 단계 613에서 출력될 것이다. 여기서 변수 ind_j는 후보 벡터들의 집합 {c₁,...,c_N} 내 그 제1타깃 벡터의 인덱스 i를 나타내고, dist_j는 입력 벡터의 소팅된 절대값 표현에 대한 그 제1타깃 벡터 사이의 거리를 나타낸다.

단계 606에서 루프 변수 i는 2에 해당하는 것으로 설정된다.

단계 607에서 거리 d_{i , ref}가 데이터베이스로부터 검색된다. 거리 d_{i , ref}는 후보 벡터 c_i 및 기준 벡터 c_ref 사이의 거리를 나타낸다. 후보 벡터 c_i 및 기준 벡터 c_ref가 모두 소팅된 절대값 입력 벡터 x와 독립적이므로, 이 거리 및 기준 벡터와 모든 다른 후보 벡터들(기준 벡터 제외) 사이의 거리 역시 미리 계산되어 메모리, 예컨대 도 1의 장치(1)의 메인 메모리(12)에 저장된다. 이 거리들은 예컨대 도 1의 장치(1)의 펌웨어 안에 포함될 수 있고 후보 벡터들의 집합이 바뀌는 경우에만 변경되거나 업데이트될 수 있다. 그러나 예컨대 서로 다른 타입의 신호들의 코딩이나 서로 다른 양자화 세분도를 가지는 코딩을 위해 서로 다른 후보 벡터들의 집합들이 존재하는 경우, 이들 후보 벡터들의 집합 각각에 대해 기준 벡터 및 각각의 후보 벡터들의 집합 내 모든 다른 후보 벡터들 사이의 해당 거리들이 미리 계산되어 저장될 수 있다.

단계 608에서, 거리 d_{i , ref} 및 거리 d_{ref ,x} 사이의 차이에 대한 절대값이 거리 d_ref,x보다 큰지 여부가 체크된다.

이러한 체크는 후보 벡터 ci 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_i,x가 c_ref 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_{ref ,x}보다 확실히 더 클 것인지 여부를 나타낸다. 따라서 거리 d_{i ,x}의 실제 계산은 그것이 확실하게 거리 d_{i , ref}보다 크지 않은 경우에만 이치에 맞다. 여기서 단계 608에서만 수행되는 체크 동작은 단계 607에서 미리 계산된 데이터베이스로부터 검색되었던 d_{i , ref} 및 단계 603에서 이미 계산되어 단계 604에서 저장되었던 d_{ref ,x}에 기반한다는 것을 알아야 한다. 따라서 단계 608에서 수행되는 체크 동작은 계산 방식이 손쉽다.

단계 608의 체크 동작이 부정적 결과를 산출하면, 현재의 후보 벡터 c_i 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_{i ,x}는 당연히 현재의 후보 벡터 ci 및 기준 벡터 c_ref 사이의 거리 d_{i , ref} 보다 크지 않다. 결과적으로 이러한 현재의 후보 벡터 c_i 및 소팅된 절대값의 입력 벡터 x 사이의 거리 d_{i ,x}가 단계 609에서 계산되어 저장된다.

그런 다음 단계 610에서 거리 d_{i ,x}가 거리 d_{ref ,x}보다 작은지가 체크된다. 작은 경우, 식별된 타깃 벡터들을 카운트하는 변수 j가 단계 611에서 1 만큼 증가하고, 단계 612에서 i의 현재 값이 변수 ind_j 안에 저장되며 현재의 거리 d_{i ,x}가 변수 dist_j에 저장된다. 단계 610의 체크 동작이 부정적 결과를 산출하면, 단계 611 및 612가 건너 띄게 된다.

단계 613에서 루프 변수 i가 이미 N에 도달하였는지, 즉 모든 후보 벡터들이 이미 체크되었는지가 체크된다. 해당사항이 없으면, 루프 변수 i는 단계 614에서 1만큼 증가되고 흐름도는 다음 후보 벡터를 체크하기 위해 다시 단계 607로 건너간다. 단계 612의 체크 동작에서 루프 변수 i가 N과 동일하다는 것이 드러나면, j 개의 식별된 타깃 벡터들의 인덱스들을 저장하는 모든 변수들 ind₁...ind_j 및 입력 벡터의 소팅된 절대값 표현에 대한 그들 각자의 거리들 dist₁....dist_j이 단계 615에서 출력된다. 이제 흐름도는 종료된다.

단계 608의 체크 동작이 정의 결과를 산출하면, 현재의 후보 벡터 c_i 및 소팅된 절대값 입력 벡터 x 사이의 거리 d_{i ,x}에 대한 계산은 거리 d_{ref ,x}보다 확실히 더 클 것이기 때문에 필요로 되지 않는다. 흐름도는 이제 단계 613으로 건너간다.

도 6의 흐름도 600에 의해 식별된 j 개의 타깃 벡터들이 이제, 예컨대 도 2의 흐름도 200의 단계 203에 따라 더 처리될 수 있다. 예컨대 j 개의 타깃 벡터들 각각에 대해, (각자의 클래스들의 코드 벡터들 사이에서) 입력 벡터에 가장 가까운 타깃 벡터들과 연관된 코드 벡터들의 개별 클래스 내 개별 코드 벡터들이 상기 도 4와 관련하여 하나의 타깃 벡터에 대해 이미 서술된 것과 같은 방식으로 결정될 수 있다.

여기서 도 6의 흐름도 600에 의해 식별된 타깃 벡터들의 개수 j는 기준 벡터 c_ref 및 입력 벡터의 소팅된 절대값 표현 사이의 거리에 강력히 좌우된다는 것을 알 수 있다.

예를 들어, 그 거리가 N 개의 후보 벡터들의 집합에서 달성될 수 있는 예컨대 최소 거리인 경우, 기준 벡터만이 도 6의 흐름도 600에 의해 타깃 벡터로서 식별될 것인 바, 이는 모든 다른 후보 벡터들에 대해 단계 608의 체크 동작은 정이 될 것이기 때문이다.

그렇지 않고 만일 이 거리가 N 개의 후보 벡터들의 집합에서 달성될 수 있는 예컨대 최대 거리인 경우, 모든 다른 N-1 개의 후보 벡터들에 대한 거리들 d_{i ,x}이 계산될 것인 바, 이는 단계 608의 체크 동작이 이 N-1 개의 후보 벡터들 모두에 대해 음이 될 것이기 때문이다. 그런 다음 모든 후보 벡터들(기준 벡터 포함)이 단계 614에서 타깃 벡터들로서 출력될 것이다.

따라서 예컨대, 기준 벡터로서 가령 널 벡터와 같이 입력 벡터의 평균 위치(가령, 복수의 상이한 입력 벡터들을 고려할 때 평균 위치)에 가까운 후보 벡터를 선택하는 것이 권장될 수 있을 것이다.

이하에서는 도 7을 참조하여, 후보 벡터들의 집합으로부터 여러 개의 타깃 벡터들의 식별 및 그 타깃 벡터들에 기반하여 (타깃 벡터들과 연관된 코드 벡터들의 개별 클래스들 안에서) 입력 벡터에 대한 최소 거리들을 가지는 코드 벡터들의 결정을 위한 예가 모든 후보 벡터들이 리더 벡터들이라는 가정 하에서 주어질 것이다.

도 7은 서로 다른 부호들로 표현되는 복수의 이차원 코드 벡터들을 가진 데카르트 좌표 시스템(70)을 도시한다. 코드 벡터들은 네 개의 서로 다른 리더 클래스들에 속하며, 이 리더 클래스들의 결합이 코드북을 형성한다. 널 벡터인 제1리더 벡터(74)가 존재한다. 이 리더 벡터(74)는 정사각형 부호로 표시되며 리더 벡터(74)만을 포함하는 리더 클래스를 가진다. 또한 세 개의 리더 벡터들(71, 72 및 73)과 이들 각자와 관련된 리더 클래스들이 존재하며, 이들은 도 5와 관련하여 이미 기술된 바와 같이 리더 벡터들(51, 52 및 53) 및 이들 각자와 관련된 리더 클래스들에 대응한다.

따라서 리더 벡터들의 집합이 {[0,0], [4,0], [3,1], [2,2]}로서 정의된다. 제1리더 벡터 [0,0]가 기준 벡터로서 사용될 것임을 가정할 때(도 6의 흐름도(600)의 단계 601 참조), 다음과 같은 거리들이 미리 계산될 것이다:

이제 입력 벡터 [0,2](도 7에 도시되지 않음)에 대해 타깃 벡터들이 식별되어야 하는 경우를 고려할 수 있다

단계 601에서 입력 벡터 [0,2]의 소팅된 절대값 표현이 이제 x=[0,2]로서 얻어진다. 단계 604에서 거리 d_{ref ,x=2}가 결정되어 단계 605에서 dist₁=2로서 ind₁=1과 함께 저장된다.

단계 608의 체크 동작이 이제 d_{ref ,x}(단계 604에서 계산됨) 및 d_{2 , ref}(미리 계산됨)에 기반하여 수행된다. 따라서 2<2가 유지되는지가 체크되고 그것이 음이므로, 거리 d_{2 ,x=2}가 단계 609에서 계산된다. 단계 610의 체크 동작이 여기서 d_{2 ,x=2}가 d_ref,x=2보다 작지 않다는 것을 드러내므로, 단계들 611 및 612는 건너 띄게 된다, 즉 c₂가 타깃 벡터로서 식별되지 않는다.

제3리더 벡터(i=3)에 대한 체크 동작이 이제 d_{ref ,x}(단계 604에서 계산됨) 및 d_3,ref(미리 계산됨)에 기반하여 수행된다. 따라서 2<1.16이 유지되는지가 체크되고 그것이 음이므로, 거리 d_{3 ,x}=1.41이 단계 609에서 계산된다. 여기서 단계 610의 체크 동작이 d_{3 ,x}=1.41이 d_{ref ,x}=2보다 작다는 것을 드러내므로, 거리 d_{3 ,x}가 dist₂=2로서 index₂=3과 함께 단계 612에서 저장된다, 즉 c₃가 타깃 벡터로서 식별된다.

마지막으로 제4리더 벡터(i=4)에 대한 체크 동작이 이제 d_{ref ,x}(단계 604에서 계산됨) 및 d_{4 , ref}(미리 계산됨)에 기반하여 수행된다. 따라서 2<0.82가 유지되는지가 체크되고 그것이 음이므로, 거리 d_{4 ,x=2}가 단계 609에서 계산된다. 단계 610의 체크 동작이 여기서 d_{4 ,x=2}가 d_{ref ,x}=2보다 작지 않다는 것을 드러내므로, 단계들 611 및 612는 건너 띄게 된다, 즉 c₄가 타깃 벡터로서 식별되지 않는다.

따라서 리더 벡터들 c₁(거리 d_{1 ,x}=2를 가짐) 및 c₃(거리 d_{3 ,x}=1.41을 가짐)이 타깃 벡터들로서 입력 벡터 x의 소팅된 절대값 표현에 대한 그들의 해당 거리들과 함께 출력된다.

여기서 거리 d_{ref ,x}=2가 입력 벡터의 소팅된 절대값 표현에 대한 다른 리더 벡터들의 거리들보다 크거나 같았다는 사실이 단계 608의 각각의 체크 동작이 음이 되게 하였고 그에 따라 거리들이 계산되게 하였다(단계 609).

대안적 예로서, 이제 입력 벡터 [1,1](도 7에 도시되지 않음)에 대해 타깃 벡터들이 식별되어야 하는 경우를 고려할 수 있다

단계 601에서 입력 벡터 [1,1]의 소팅된 절대값 표현이 이제 x=[1,1]로서 얻어진다.

단계 604에서 거리 d_{ref ,x}=1.41이 결정되어 단계 605에서 dist₁=1.41로서 ind₁=1과 함께 저장된다.

단계 608의 체크 동작이 이제 d_{ref ,x}(단계 604에서 계산됨) 및 d_{2 , ref}(미리 계산됨)에 기반하여 수행된다. 따라서 1.41<2.59가 유지되는지가 체크되고 그것이 정이므로, 거리 d_{2 ,x}는 계산되지 않는다.

제3리더 벡터(i=3)에 대한 체크 동작이 이제 d_{ref ,x}(단계 604에서 계산됨) 및 d_3,ref(미리 계산됨)에 기반하여 수행된다. 따라서 1.41<1.75가 유지되는지가 체크되고 그것이 정이므로, 거리 d_{3 ,x}는 계산되지 않는다.

마지막으로 제4리더 벡터(i=4)에 대한 체크 동작이 이제 d_{ref ,x}(단계 604에서 계산됨) 및 d_{4 , ref}(미리 계산됨)에 기반하여 수행된다. 따라서 1.41<1.41이 유지되는지가 체크되고 그것이 부정이므로, 거리 d_{4 ,x}=1.41이 단계 609에서 계산된다. 이제 단계 610의 체크 동작이 d_{4 ,x}=1.41이 d_{ref ,x}=1.41보다 작지 않다는 것을 드러내므로 단계들 611 및 612는 건너 띄게 된다.

따라서 오직 하나의 리더 벡터(c_ref=c₁)만이 타깃 벡터로서, 입력 벡터 x의 소팅된 절대값 표현에 대한 그 해당 거리와 함께 출력된다.

여기서, 거리 d_{ref ,x}=1.41이 입력 벡터의 소팅된 절대값 표현에 대한 제2 및 제3리더 벡터들의 거리들보다 작았다는 사실은 단계 608에서의 체크 동작이 이러한 두 리더 벡터들에 대해 정이 되게 하였고, 그에 따라 그들 각자의 거리들은 계산되지 않았다. 제4리더 벡터 c₄에 대해 단계 608의 체크 동작은 부정이었고, 그에 따라 거리 d_{4 ,x}가 단계 609에서 계산되었지만, 이때 단계 610의 체크 동작이 c₄가 c_ref보다 x에 더 가깝다는 것을 드러냈으므로 c₄는 타깃 벡터로서 식별되지 않았다.

따라서 입력 벡터 ([1,1])에 대해 최소 거리를 가진 코드 벡터 ([0,0])를 포함하는 리더 클래스와 연관된 타깃 벡터 ([0,0])가 네 개의 리더 벡터들의 집합 내 세 개의 다른 리더 벡터들 중 적어도 둘 ([4,0] 및 [3,1])의 거리들을 산출할 필요 없이 식별되었다.

결과적으로 상기 예들로부터 하나 이상의 타깃 벡터들이 식별되어야 하는 복수의 서로 다른 입력 벡터들을 고려할 때, 입력 벡터 x의 소팅된 절대값 표현에 대한 리더 벡터들의 모든 거리들이 다 계산되어야 하는 것은 아닌 여러 상황들이 있을 것이고(단계 609 참조) 그에 따라 일반적으로 단일 타깃 벡터(및 그 관련 코드 벡터)뿐 아니라 이 단일 타깃 벡터 이상(및 그 관련 코드 벡터들)이 얻어진다는 이점을 계속 유지하면서, 입력 벡터의 소팅된 절대값 표현 및 모든 리더 벡터들 간의 거리들에 대한 억지 기법(brute-force)의 계산과 비교하여 계산상의 복잡도가 훨씬 낮게 된다. 이것은 예컨대 선택된 타깃 벡터(나 그 관련 코드 벡터)를 나타내는데 필요한 비트 개수와 같은 하나 이상의 추가 기준에 기반하여 식별된 타깃 벡터들로부터 이들 타깃 벡터들 중 하나(및 그 관련 코드 벡터)를 선택하는 데 예컨대 활용될 수 있다.

여기서 도 6의 단계 610의 조건 "d_{i ,x} < d_{ref ,x}"을 "d_{i ,x} ≤ d_{ref ,x}"로 바꿈으로써 식별된 타깃 벡터의 개수가 더 증가될 수 있다는 것을 알아야 한다. 상기 마지막 예에서, 리더 벡터 c₄ 역시 타깃 벡터로 식별될 수 있을 것이다.

이 출원에 사용된 바와 같이, '회로'라는 용어는 다음과 같은 것들 모두를 나타낸다:

(a) 하드웨어 만의 회로 구성(아날로그 및/또는 디지털 회로 만으로 된 구성과 같은 것); 및

(b) (적용 가능할 경우) 다음과 같은 회로들 및 소프트웨어(및/또는 펌웨어)의 조합:

(i) 프로세서(들)의 조합 또는

(ii) 모바일 전화나 위치식별 장치와 같은 장치가 다양한 기능들을 수행하도록 함께 작업하는 (디지털 시그널 프로세서(들)을 포함하는) 프로세서(들)/소프트웨어의 일부, 소프트웨어 및 메모리(들) 및

(c) 소프트웨어나 펌웨어가 물리적으로 존재하지 않더라도 동작을 위해 소프트웨어나 펌웨어를 필요로 하는 마이크로프로세서(들)이나 마이크로프로세서(들)의 일부와 같은 회로들.

이러한 "회로"의 정의는 청구범위를 포함하여 이 출원 안에서의 그 용어에 대한 모든 사용에 적용된다. 추가 예로서 이 출원에 사용된 바와 같이, "회로"라는 용어는 또한 단지 프로세서(또는 다중 프로세서들)이나 프로세서의 일부 및 그것에(또는 그것들에) 동반하는 소프트웨어 및/또는 펌웨어의 구현예를 포괄할 것이다. "회로"라는 용어는 또한, 예컨대 특정 청구 요소에 적용가능한 경우, 모바일 전화기나 위치식별 장치를 위한 기저대역 집적 회로 또는 응용 프로세서 집적 회로를 또한 포괄할 것이다.

이 출원에서 설명한 본 발명의 양태들 및 그 실시예들과 관련하여, 어떤 행위나 단계에 대한 개시는 해당 장치의 해당 (기능적) 구성(가령 컴퓨터 프로그램 코드 및/또는 프로세서 및/또는 해당 장치의 어떤 다른 수단의 구성), 실행시 그러한 행위나 단계를 야기하도록 정의된 해당 컴퓨터 프로그램 코드 및/또는 시스템(이나 그 일부)의 해당 (기능적) 구성에 대한 개시로서 이해되어야 한다는 것을 알 수 있다.

이 출원서에 제시된 발명 및 그 실시예들의 양태들 및 그들의 단일 특성들 또한 서로 간에 모든 가능한 조합으로 개시되는 것으로 이해될 것이다. 위에서 제시된 흐름도들 내 방법의 단계들의 순서는 의무적인 것이 아니고 다른 대안적 순서들 또한 가능할 수 있다는 것이 역시 이해되어야 한다.

본 발명은 위에서 비한정적 예들에 의해 기술되었다. 특히, 당업자에게 자명하며 첨부된 청구범위의 범위 및 사상으로부터 벗어나지 않으면서 구현될 수 있는 대안적 방식들 및 변형들이 존재한다는 것이 주목되어야 한다.

Claims (35)

1. 복수의 후보 벡터로부터 하나 이상의 타깃 벡터를 식별하는 단계―각각의 후보 벡터는 소팅된 요소를 가지고 코드북의 하나 이상의 코드 벡터의 개별 클래스와 관련되고, 상기 후보 벡터 중 적어도 하나는 상기 개별 후보 벡터로부터 순열(permutation) 및 부호 순열(signed permutation) 중 하나에 의해 획득할 수 있는 적어도 하나의 코드 벡터 및 상기 개별 후보 벡터를 포함하는 둘 이상의 코드 벡터의 개별 클래스와 관련되며, 상기 타깃 벡터는 상기 복수의 후보 벡터의 모든 후보 벡터 가운데에서 입력 벡터의 적어도 소팅된 표현에 대해 최소 거리를 가짐―를 포함하되, 상기 식별하는 단계는
   상기 복수의 후보 벡터 중 한 후보 벡터에 대해, 적어도 상기 후보 벡터와 기준 벡터 사이의 거리 및 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리에 기반하여, 상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 거리가 상기 입력 벡터의 적어도 소팅된 표현과 상기 기준 벡터 사이의 거리보다 큰지를 체크하는 단계와,
   상기 후보 벡터에 대해, 상기 체크하는 단계가 부정적 결과를 산출하는 경우에만, 상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 거리를 계산하는 단계를 포함하는
   방법.
2. 제1항에 있어서,
   상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 거리가 상기 입력 벡터의 적어도 소팅된 표현과 상기 기준 벡터 사이의 거리보다 큰지를 체크하는 단계는 상기 후보 벡터와 상기 기준 벡터 사이의 거리 및 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리 간의 차이에 대한 절대 값이 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 큰지를 체크함으로써 수행되는
   방법.
   
3. 제1항 또는 제2항에 있어서,
   상기 체크하는 단계, 및 각각의 상기 체크 단계가 부정적 결과를 산출하는 경우 상기 거리를 계산하는 단계는 상기 기준 벡터로서 적어도 한 번 사용된 하나의 후보 벡터를 제외한 상기 복수의 후보 벡터의 모든 후보 벡터에 대한 상기 하나 이상의 타깃 벡터의 식별 시에 수행되는
   방법.
   
4. 제1항 또는 제2항에 있어서,
   상기 기준 벡터는 상기 복수의 후보 벡터로부터 사전선택되거나 무작위로 선택된 후보 벡터인
   방법.
   
5. 제1항 또는 제2항에 있어서,
   상기 식별하는 단계는 상기 후보 벡터에 대한 상기 체크 단계가 부정적 결과를 산출하는 경우 상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 계산 거리가 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 작은지를 체크하는 단계, 및 상기 입력 벡터의 소팅된 표현과 상기 후보 벡터 사이의 계산 거리가 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 작은 경우 상기 기준 벡터를 상기 후보 벡터로 정의하는 단계를 더 포함하는
   방법,
   
6. 제5항에 있어서,
   상기 복수의 후보 벡터로부터 오직 하나의 타깃 벡터가 식별되며, 상기 타깃 벡터는 상기 복수의 후보 벡터 중 마지막 후보 벡터가 체크된 뒤 상기 기준 벡터에 해당하는
   방법.
   
7. 제5항에 있어서,
   상기 후보 벡터와 상기 기준 벡터 사이의 거리는 상기 복수의 후보 벡터의 모든 가능한 후보 벡터의 쌍에 대한 거리를 포함하는 메모리로부터 검색되는
   방법.
   
8. 제5항에 있어서,
   상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리가 상기 복수의 후보 벡터 중 앞서 체크된 후보 벡터와 상기 앞서 체크된 후보 벡터에 대해 계산된 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리에 해당하며, 그것이 적어도 일시적으로 저장된 메모리로부터 검색되는
   방법.
   
9. 제1항 또는 제2항에 있어서,
   입력 벡터에 대한 상기 하나 이상의 타깃 벡터의 식별 시, 상기 체크 단계는 상기 복수의 후보 벡터 중 적어도 몇몇 후보 벡터에 대해 수행되며, 각각의 상기 체크 단계에서 동일한 기준 벡터가 사용되는
   방법.
   
10. 제9항에 있어서,
    후보 벡터와 상기 기준 벡터 사이의 거리는 상기 기준 거리 및 상기 복수의 후보 벡터의 모든 후보 벡터 사이의 거리를 포함하는 메모리로부터 검색되는
    방법.
    
11. 제9항에 있어서,
    입력 벡터에 대한 상기 하나 이상의 타깃 벡터의 식별 시, 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리가 단 한 번 계산되는
    방법.
    
12. 제1항 또는 제2항에 있어서,
    상기 하나 이상의 타깃 벡터 중 적어도 하나에 대해, 코드 벡터의 상기 개별 클래스 내 모든 코드 벡터 중에서 상기 입력 벡터에 대한 최소 거리를 가진 상기 적어도 하나의 타깃 벡터와 연관된 코드 벡터의 상기 개별 클래스에 포함되는 개별 코드 벡터를 결정하는 단계를 더 포함하는
    방법.
    
13. 제12항에 있어서,
    상기 개별 코드 벡터에 대한 상기 결정 단계는
    상기 타깃 벡터의 순열화된 표현(a permuted representation)을 얻기 위해 상기 입력 벡터의 상기 적어도 소팅된 표현에 대한 소팅을 취소할 상기 개별 코드 벡터를 포함하는 코드 벡터의 상기 클래스와 연관된 상기 타깃 벡터에 대해 순열 연산을 적용하는 단계와,
    상기 타깃 벡터의 부호 순열화된 표현(a signed permuted representation)을 얻기 위해 상기 입력 벡터 내 해당 위치에 있는 요소의 부호에 해당하는 상기 타깃 벡터의 상기 순열화된 표현의 요소로 부호를 할당하는 단계와,
    상기 타깃 벡터와 연관된 코드 벡터의 상기 클래스에 대해 부호 제약요건이 부과되는 경우에만, 그리고 상기 부호 제약요건이 상기 타깃 벡터의 상기 부호 순열화된 표현에 의해 만족되지 않는 경우에, 상기 코드 벡터를 얻기 위해 상기 타깃 벡터의 상기 부호 순열화된 표현의 최소 요소의 부호를 토글(toggle)하며, 그렇지 않은 경우 상기 타깃 벡터의 상기 부호 순열화된 표현을 상기 코드 벡터로서 간주하는 단계를 포함하는
    방법.
14. 제1항 또는 제2항에 있어서,
    상기 입력 벡터는 비디오, 이미지, 오디오 및 음성 신호 중 적어도 하나를 적어도 부분적으로 나타내는
    방법.
    
15. 제1항 또는 제2항에 있어서,
    상기 방법은 3GPP EVS 코덱(Third Generation Partnership Project Enhanced Voice Service codec)의 일부를 형성하는
    방법.
    
16. 복수의 후보 벡터로부터 하나 이상의 타깃 벡터를 식별하는 수단―각각의 후보 벡터는 소팅된 요소를 가지고 코드북의 하나 이상의 코드 벡터의 개별 클래스와 관련되고, 상기 후보 벡터 중 적어도 하나는 상기 개별 후보 벡터로부터 순열 및 부호 순열 중 하나에 의해 획득할 수 있는 적어도 하나의 코드 벡터 및 상기 개별 후보 벡터를 포함하는 둘 이상의 코드 벡터의 개별 클래스와 관련되며, 상기 타깃 벡터는 상기 복수의 후보 벡터의 모든 후보 벡터 가운데에서 입력 벡터의 적어도 소팅된 표현에 대해 최소 거리를 가짐―을 포함하되, 상기 식별하는 수단은
    상기 복수의 후보 벡터 중 한 후보 벡터에 대해, 적어도 상기 후보 벡터와 기준 벡터 사이의 거리 및 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리에 기반하여, 상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 거리가 상기 입력 벡터의 적어도 소팅된 표현과 상기 기준 벡터 사이의 거리보다 큰지를 체크하는 수단과,
    상기 후보 벡터에 대해, 상기 체크의 동작이 부정적 결과를 산출하는 경우에만 상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 거리를 계산하는 수단을 포함하는
    장치.
    
17. 제16항에 있어서,
    상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 거리가 상기 입력 벡터의 적어도 소팅된 표현과 상기 기준 벡터 사이의 거리보다 큰지를 체크하는 수단은 상기 후보 벡터와 상기 기준 벡터 사이의 거리 및 상기 기준 벡터 와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리 간의 차이에 대한 절대 값이 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 큰지를 체크하는 수단에 의하여 수행되는
    장치.
    
18. 제16항 또는 제17항에 있어서,
    상기 체크하는 수단, 및 각각의 상기 체크 단계가 부정적 결과를 산출하는 경우 상기 거리를 계산하는 수단은 상기 기준 벡터로서 적어도 한 번 사용된 하나의 후보 벡터를 제외한 상기 복수의 후보 벡터의 모든 후보 벡터에 대해 수행되는
    장치.
    
19. 제16항 또는 제17항에 있어서,
    상기 기준 벡터는 상기 복수의 후보 벡터로부터 사전선택되거나 무작위로 선택된 후보 벡터인
    장치.
    
20. 제16항 또는 제17항에 있어서,
    상기 후보 벡터에 대한 상기 체크 단계가 부정적 결과를 산출하는 경우 상기 입력 벡터의 적어도 소팅된 표현과 상기 후보 벡터 사이의 계산 거리가 상기 기준 벡터과 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 작은지를 체크하는 수단과, 상기 입력 벡터의 소팅된 표현과 상기 후보 벡터 사이의 계산 거리가 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리보다 작은 경우 상기 기준 벡터를 상기 후보 벡터로 정의하는 수단을 더 포함하는
    장치.
    
21. 제20항에 있어서,
    상기 복수의 후보 벡터로부터 오직 하나의 타깃 벡터가 식별되며, 상기 타깃 벡터는 상기 복수의 후보 벡터 중 마지막 후보 벡터가 체크된 뒤 상기 기준 벡터에 해당하는
    장치.
    
22. 제20항에 있어서,
    상기 후보 벡터와 상기 기준 벡터 사이의 거리는 상기 복수의 후보 벡터의 모든 가능한 후보 벡터의 쌍에 대한 거리를 포함하는 메모리로부터 검색하는 수단을 더 포함하는
    장치.
    
23. 제20항에 있어서,
    상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리가 상기 복수의 후보 벡터 중 앞서 체크된 후보 벡터와 상기 앞서 체크된 후보 벡터에 대해 계산된 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리에 해당하며, 그것이 적어도 일시적으로 저장된 메모리로부터 검색되는
    장치.
    
24. 제16항 또는 제17항에 있어서,
    입력 벡터에 대한 상기 하나 이상의 타깃 벡터의 식별 시, 상기 복수의 후보 벡터 중 적어도 몇몇 후보 벡터에 대해 체크하는 수단을 수행하는 것을 더 포함하며, 각각의 체크 시에 동일한 기준 벡터가 사용되는
    장치.
    
25. 제24항에 있어서,
    상기 후보 벡터와 상기 기준 벡터 사이의 거리를 상기 기준 벡터와 상기 복수의 후보 벡터의 모든 후보 벡터 사이의 거리를 포함하는 메모리로부터 검색하는 수단을 더 포함하는
    장치.
    
26. 제24항에 있어서,
    입력 벡터에 대한 상기 하나 이상의 타깃 벡터의 식별 시, 상기 기준 벡터와 상기 입력 벡터의 적어도 소팅된 표현 사이의 거리를 단 한번 계산하는 수단을 더 포함하는
    장치.
27. 제16항 또는 제17항에 있어서,
    상기 하나 이상의 타깃 벡터 중 적어도 하나에 대해, 코드 벡터의 상기 개별 클래스 내 모든 코드 벡터 중에서 상기 입력 벡터에 대한 최소 거리를 가진 상기 적어도 하나의 타깃 벡터와 연관된 코드 벡터의 상기 개별 클래스에 포함되는 개별 코드 벡터를 결정하는 수단을 더 포함하는
    장치.
    
28. 제27항에 있어서,
    상기 개별 코드 벡터를 결정하는 수단은
    상기 타깃 벡터의 순열화된 표현을 얻기 위해 상기 입력 벡터의 상기 적어도 소팅된 표현에 대한 소팅을 취소할 상기 개별 코드 벡터를 포함하는 코드 벡터의 상기 클래스와 연관된 상기 타깃 벡터에 대해 순열 연산을 적용하는 수단과,
    상기 타깃 벡터의 부호 순열화된 표현을 얻기 위해 상기 입력 벡터 내 해당 위치에 있는 요소의 부호에 해당하는 상기 타깃 벡터의 상기 순열화된 표현의 요소로 부호를 할당하는 수단과,
    상기 타깃 벡터와 연관된 코드 벡터의 상기 클래스에 대해 부호 제약요건이 부과되는 경우에만, 그리고 상기 부호 제약요건이 상기 타깃 벡터의 상기 부호 순열화된 표현에 의해 만족되지 않는 경우, 상기 코드 벡터를 얻기 위해 상기 타깃 벡터의 상기 부호 순열화된 표현의 최소 요소의 부호를 토글(toggle)하고, 그렇지 않은 경우 상기 타깃 벡터의 상기 부호 순열화된 표현을 상기 코드 벡터로서 간주하는 수단을 더 포함하는
    장치.
    
29. 제16항 또는 제17항에 있어서,
    상기 입력 벡터는 비디오, 이미지, 오디오 및 음성 신호 중 적어도 하나를 적어도 부분적으로 나타내는
    장치.
    
30. 제16항 또는 제17항에 있어서,
    상기 하나 이상의 타깃 벡터는 3GPP EVS 코덱(Third Generation Partnership Project Enhanced Voice Service codec)에 따라 식별되는
    장치.
    
31. 제16항 또는 제17항에 있어서,
    사용자 인터페이스 및 안테나 중 적어도 하나를 더 포함하는
    장치.
    
32. 컴퓨터 프로그램이 프로세서에 의해 실행될 때 제1항 또는 제2항에 따른 방법을 수행하기 위한 프로그램 코드를 포함하는 컴퓨터 프로그램을 저장한
    컴퓨터 판독가능 저장 매체.
33. 삭제
34. 삭제
35. 삭제

Images