KR100326746B1

KR100326746B1 - 비선형함수를근사시키기위한시스템및방법

Info

Publication number: KR100326746B1
Application number: KR1019940000056A
Authority: KR
Inventors: 시발링에스.마한트-세티; 토마스제이.애톤; 제롤드에이.세이트칙
Original assignee: 윌리엄 비. 켐플러; 텍사스 인스트루먼츠 인코포레이티드
Priority date: 1993-01-04
Filing date: 1994-01-04
Publication date: 2002-06-20
Anticipated expiration: 2014-01-04
Also published as: EP0606775A1; US5367702A; TW377414B; JPH0793295A

Abstract

비선형 함수 근사 시스템(10)이 제공된다. 이 시스템(10)은 제1 양 및 제2 양을 2의 3 제곱까지 곱하기 위한 제1 및 제2 배수 발생 회로(12) 및 (14)를 포함한다. 제1 및 제2 함수 발생 회로(16) 및 (18)은 제1 및 제2 배수 발생 회로(12) 및 (14)에서 발생된 배수들을 결합하므로써 제1 및 제2 양들의 제1 및 제2 함수를 발생한다. 제1 및 제2 근사치 발생 회로(20 및 22)는 제1 및 제2 함수 발생 회로(16 및 18)의 출력을 시프트시켜서 비선형 함수의 제1 및 제2 근사치를 발생한다. 근사치 선택 회로(24)는 제1 및 제2 근사치 발생 회로(20 및 22)에서 발생된 적절한 근사치를 출력시킨다.

Description

비선형 함수를 근사시키기 위한 시스템 및 방법

본 발명은 일반적으로 데이타 처리 시스템에 관한 것으로, 특히 비선형 함수를 근사시키기 위한 시스템 및 방법에 관한 것이다.

현대의 많은 전자 시스템의 동작에서는 비선형 함수의 반복적인 계산이 필요하다. 예를 들어, 여러 시스템은 다수 크기의 벡터를 비교한다. 이러한 시스템에서는, 측정된 벡터량은 벡터들 사이의 유클리드 거리(Euclidean distance)를 계산하여 기억된 벡터량과 비교된다. 예를 들어 많은 음성 인식 시스템에서는 이 방식으로 벡터량을 비교하면서 동작한다.

벡터량을 비교하기 위한 종래의 방법은 다음 식에 따라 벡터들 사이의 유클리드 거리를 결정한다.

그러므로, 벡터및사이의 거리는 n 제곱들의 합의 제곱근이고, 여기에서 n은 벡터및의 차원(dimension)이다. 벡터들 사이의 거리가 0이면, 측정된 벡터가 기억된 벡터와 일치하고 있다.

디지탈 신호 처리 분야에서, 이 거리는 전형적으로 식(1)을 변형하여 계산되어 다음 식이 된다.

(2)

근(radical)의 첫번째 2개 항은 2개의 벡터및의 정규화된 크기를 나타내고 있다. 벡터및의 성분은 엄밀히 8비트이고 제곱된 성분은 정확히 16비트이다. 그러므로, 벡터및의 정규화된 크기, 즉 제곱된 성분들의 합은 256개의 성분 벡터에 대해 정확히 24비트가 될 것이다. 이 거리는 벡터의 각각의 성분을 벡터의 대응하는 성분으로 곱하고, 이들 결과를 누산기에서 합하고 나서 상기 두 벡터 크기들의 제곱의 합에서 누산된 합의 두 배를 감산하여 계산된다. 이 연산은 8 비트 x 8 비트 이상인 멀티플라이어에서 승산을 반복해야 한다. 이것은 저속 처리이고, 이 벡터들이 충분히 근접하여 일치하는 것으로 고려되는 경우에, 벡터들 사이의 계산된 거리는 2 또는 3비트 정도가 될 것이다. 그러나, 이 거리를 계산하기 위해, 곱셈들의 합이 제곱된 성분의 합, 예를 들어, 24 비트와 동일한 정밀도로 계산될 필요가 있다. 2개의 유사한 벡터들 사이의 거리를 계산하려면 상기 정밀도와는 다른 정밀도를 갖는 큰 멀티플라이어를 필요로한다. 사실, 이러한 큰 멀티플라이어로 거리를 계산하는 것은 저속이고 상당한 전력을 요구한다. 그러므로, 정확한 함수의 근사치를 신속하게 계산하고 집적 반도체 장치중 작은 영역으로도 실현할 수 있는 비선형 함수를 근사시키는 방법 및 시스템의 필요성이 대두되었다.

본 발명에 따른 비선형 함수를 근사시키기 위한 시스템 및 방법은 종래의 시스템 및 방법과 관련된 단점 및 문제점을 실질적으로 제거하거나 감소시킨다.

더 상세하게는, 본 발명은 2개의 변수의 비선형 함수의 정확한 값을 근사시키는 방법 및 시스템을 제공하고 있다. 제1 변수에 대한 제1 양을 2의 3 제곱까지 승산하여 한정된 제1 양의 배수를 형성한다. 제2 변수에 대한 제2 양을 2의 3 제곱까지 승산하여 한정된 제2 양의 배수를 형성한다. 제1 및 제2 양의 제1 및 제2 선형 함수는 발생된 제1 및 제2 양의 승산치를 결합하여 발생된다. 제1 및 제2 근사치는 시프터에서 제1 및 제2 함수를 시프트하여 발생된다. 제1 및 제2 변수에 대한 적당한 근사치가 상기 시스템에 의해 출력된다.

본 발명의 중요한 기술적 장점은 비선형 함수를 근사시키기 위해 가산기, 감산기, 멀티플렉서 및 시프터를 사용한다는 사실에 있다. 작고 고속인 상기 회로 부품들을 사용하면, 비선형 함수를 계산하는 반도체 면에서 볼때 속도를 증가시키고경비를 절감할 수 있다. 부수적으로, 작은 3 또는 4비트 가산기 및 감산기를 사용하면, 충분한 정밀도의 근사치가 많은 현대 전자 시스템에 제공될 수 있다.

본 발명 및 그 장점에 대한 완전한 이해를 돕기 위해 동일한 참조 번호가 동일한 소자에 병기된 첨부된 도면을 참조하여 이하 본 발명을 설명하기로 한다.

제1도는 비선형 함수를 근사시키기 위한 본 발명에 따라 구성된 시스템(10)을 도시하고 있다. 이 시스템(10)은 제1 배수 발생 회로(12) 및 제2 배수 발생 회로(14)를 포함하고 있다. 제1 배수 발생 회로(12)는 입력 m을 수신하도록 결합된다. 제1 배수 발생 회로(12)는 제한된 수의 m x 2의 거듭 제곱을 발생시킨다. 제2 배수 발생 회로(14)는 제한된 수의 n x 2의 거듭 제곱을 형성한다. 제1 함수 발생 회로(16)는 제1 및 제2 배수 발생 회로(12 및 14)의 출력에 결합된다. 제1 함수 발생 회로(16)는 m과 n의 선정된 함수를 발생시킨다. 제2 함수 발생 회로(18)은 제1 및 제 2 배수 발생 회로(12 및 14)의 출력에 결합된다. 제2 함수 발생 회로(18)은 m과 n의 선정된 함수를 발생시킨다. 제1 근사치 발생 회로(20)는 제1 함수 발생 회로(16)의 출력에 결합된다. 제2 근사치 발생 회로(22)는 제2 함수 발생 회로(18)의 출력에 결합된다. 근사치 선택 회로(24)는 제1 근사치 발생 회로(20)의 출력 및 제2 근사치 발생 회로(22)의 출력에 결합된다.

동작시에, 시스템(10)은 구분식 선형 근사치(pieceiwise linear approximation)에 따라 비선형 함수를 근사시킨다. 제1 배수 발생 회로(12)는 예를 들어 제한된 수의 m배수를 발생시키기 위해 결합된 시프터의 조합을 포함할 수 있다. 제1 배수발생 회로(12)의 출력은 예를 들어, m, 2m 및 4m을 포함할 수 있다.제2 배수 발생 회로(14)는 예를 들어 제한된 수의 n 배수를 발생시키기 위해 결합된 시프터의 조합을 포함할 수 있다. 제2 배수 발생 회로(14)의 출력은 예를 들어 n, 2n 및 4n을 포함할 수 있다.

제1 함수 발생 회로(16)는 예를 들어 제1 및 제2 배수 발생 회로(12 및 14)에서 발생되는 m 및 n의 배수로부터 제1 함수를 발생시키기 위한 가산기 및 감산기의 조합을 포함할 수 있다. 제1 함수 발생 회로(16)의 출력은 예를 들어 8m + n을 포함할 수 있다. 제2 함수 발생 회로(18)는 예를 들어 제1 및 제2 배수 발생 회로(12 및 14)에서 발생되는 m 및 n의 배수로부터 제2 함수를 발생시키기 위한 가산기 및 감산기의 제2 조합을 포함할 수 있다. 제2 함수 발생 회로(18)의 출력은 예를 들어 8m + 4n - m을 포함할 수 있다.

제1 근사치 발생 회로(20)는 예를 들어 제1 함수 발생 회로(16)의 출력을 8로 나누기 위해 제1 함수 발생 회로(16)를 3비트만큼 우측으로 시프트시키기 위한 시프터를 포함할 수 있다. 제1 근사치 발생 회로(20)의 출력은 예를 들어을 포함할 수 있다. 제2 근사치 발생 회로(22)는 예를 들어 제2 함수 발생 회로(18)를 8로 나누기 위해 제2 함수 발생 회로(18)를 3비트만큼 우측으로 시프트시키기 위한 시프터를 포함할 수 있다. 제2 근사치 발생 회로(22)의 출력은 예를 들어 m + n/2- m/8을 포함할 수 있다.

근사치 선택 회로(24)는 예를 들어 멀티플렉서 및 멀티플렉서 제어 회로를 포함할 수 있다. 근사치 선택 회로(24)의 출력은 예를 들어 제1 근사치 발생회로(20) 및 제2 근사치 발생 회로(22)의 출력들 중 더 큰 출력을 포함할 수 있다. 선택적으로, 근사치 선택 회로(24)의 출력은 n 대 m의 비가 선정된 브레이크포인트(breakpoint) 보다 작은 경우에 제1 근사치 발생 회로(20)의 출력을 포함하고 n 대 m의 비가 선정된 브레이크포인트 보다 큰 경우에 제2 근사치 발생 회로(22)의 출력을 포함할 수 있다.

제2도는 비선형 함수를 근사시키기 위한 본 발명에 따라 구성된 회로(30)를 도시하고 있다. 이 회로(30)는 제1 및 제2 배수 발생 회로(32 및 34)를 포함하고 있다. 제1 배수 발생 회로(32)는 양 m을 수신하기 위해 결합된다. 제2 배수 발생 회로(34)는 양 n을 수신하기 위해 결합된다. 제1, 제2 및 제3 함수 발생 회로(36, 38 및 40)는 제1 배수 발생 회로(32)의 출력 및 제2 배수 발생 회로(34)의 출력에 결합된다. 제1 근사치 발생 회로(42)는 제1 함수 발생 회로(36)에 결합된다. 제2 근사치 발생 회로(44)는 제2 함수 발생 회로(38)에 결합된다. 제3 근사치 발생 회로(46)는 제3 함수 발생 회로(40)에 결합된다. 근사치 선택 회로(48)는 제1, 제2 및 제3 근사치 발생 회로(42, 44 및 46)에 결합된다.

동작시, 제1 배수 발생 회로(32)는 예를 들어 제한된 수의 시프터를 포함할 수 있다. 제1 배수 발생 회로(32)의 제1 시프터는 양 m에 2의 여러 정수 거듭제곱을 곱한다. 제2 배수 발생 회로(34)는 예를 들어 제한된 수의 시프터를 포함한다. 제2 배수 발생 회로(34)의 시프터는 양 n에 2의 여러 정수 거듭제곱을 곱한다.

제1 함수 발생 회로(36)는 예를 들어 제1 및 제2 배수 발생 회로(32 및 34)에 발생된 m 및 n 배수로부터 제1 함수를 발생시키기 위한 가산기 및 감산기 조합을 포함할 수 있다. 제1 함수 발생 회로(36)의 출력은 예를 들어 함수 8m + 4n - m을 포함하고 있다. 제2 함수 발생 회로(38)는 예를 들어 제1 및 제2 배수 발생 회로(32 및 34)에서 발생되는 m 및 n의 배수로부터 제2 함수를 발생시키기 위한 가산기 및 감산기의 조합을 포함할 수 있다. 제2 함수 발생 회로(38)의 출력은 예를 들어 함수 8m + n - m을 포함할 수 있다. 제3 함수 발생 회로(40)는 예를 들어 제1 및 제 2 배수 발생 회로(32 및 34)에서 발생되는 m 및 n의 배수로부터 제3 함수를 발생시키기 위해 감산기 및 가산기의 조합을 포함할 수 있다. 제3 함수 발생 회로(30)의 출력은 함수 32m + 2On - 7m을 포함할 수 있다.

제1 근사치 발생 회로(42)는 예를 들어 제1 함수 발생 회로(36)의 출력을 8로 나누기 위해 제1 함수 발생 회로(36)의 출력을 3 비트만큼 우측으로 시프트시키기 위한 시프터를 포함하고 있다. 제2 근사치 발생 회로(44)는 예를 들어 제2 함수 발생 회로(38)를 8로 나누기 위해 제2 함수 발생 회로(38)의 출력을 3비트만큼 우측으로 시프트시키기 위한 시프터를 포함하고 있다. 제3 근사치 발생 회로(46)는 예를 들어 제3 함수 발생 회로(40)의 출력을 32로 나누기 위해 제3 함수 발생 회로(40)의 출력을 5비트만큼 우측으로 시프트시키기 위한 시프터를 포함할 수 있다.

근사치 선택 회로(48)는 예를 들어 멀티플렉서 및 멀티플렉서 제어회로를 포함할 수 있다. 근사치 선택 회로(48)는 입력 m 및 n에 대해 적당한 근사치를 출력한다. 이 실시예에서, 적당한 근사치 선택 회로(48)는 제1, 제2 및 제3 근사치 발생회로(42, 44 및 46)의 출력들 중 더 큰 출력을 출력한다. 선택적으로, 근사치 선택회로(48)는 입력 n 및 m의 비와 제1 및 제2 선정된 브레이크포인트와의 비교에 기초하여 적당한 근사치를 출력한다. n 대 m의 비가 제1 선정된 브레이크포인트 보다 작으면, 근사치 선택 회로(48)는 제1 근사치 발생 회로(42)의 출력을 출력한다. n 대 m의 비가 제1 선정된 브레이크포인트 보다 크고 제2 선정된 브레이크포인트보다 작으면, 근사치 선택 회로(48)는 제2 근사치 발생 회로(44)의 출력을 출력한다. n 대 m의 비가 제2 선정된 브레이크포인트 보다 크면, 근사치 선택 회로(48)는 제3 근사치 발생 회로(46)의 출력을 출력한다. 제3 실시예의 근사치 선택 회로(48)는 제 3도를 참조하여 잘 이해할 수 있다.

제3도는 본 발명의 지시에 따라 비선형 함수를 근사시키기 위해 제2 시스템에서 사용될 수 있는 근사 그래프이다. 제3도에는 3개의 영역 즉, 영역 A, 영역 B, 영역 C를 갖고 있는 비선형 함수(50)가 도시되어 있다. 제3도의 X 성분은 n/m의 비를 나타내고 있다. 제3도의 Y 성분은 비선형 함수(50)의 값 및 X에 대한 대응값을 나타내고 있다. 제1 근사 성분(5O)은 제1 근사치 발생 회로(42)의 출력에 대응한다. 제2 근사 성분(54)은 제2 근사치 발생 회로(44)의 출력에 대응한다. 제3 근사성분(56)은 제3 근사치 발생 회로(46)의 출력에 대응한다. 이 실시예에서, n,/m의 비가 영역 A 내에 있는 경우에 근사치 선택 회로(48)는 제1 근사 성분(52)을 출력한다. n/m의 비가 영역 B내에 있는 경우에 근사치 선택 회로(48)는 제2 근사 성분(54)을 출력한다. m/n의 비가 영역 C 내에 있는 경우에 근사치 선택 회로(48)는 제 3 근사 성분(54)을 출력한다.

제4도에는 2개의 벡터및사이의 유클리드 거리를 근사시키기 위해 본 발명에 따라 구성된 회로(60)가 도시되어 있다. 이 회로(60)은 벡터및를 형성하는 개개의 성분을 수신하고 기억하는 메모리 회로(62)를 포함하고 있다.

프리프로세서 회로(64)는 벡터및의 대응 성분을 판독하고, 대응 성분들 사이의 차를 계산하며, 메모리(62) 내의 이 차이 값을 기억한다. 루팅 논리 회로(66)은 회로(60)을 통해 먼저 통과하는 2개의 기억된 차이 값 및 다음에 통과하는 기억된 차이 값을 판독하기 위해 메모리(62)에 결합된다.

루팅 논리회로(66)의 두 출력 x 및 y는 감산기(68) 및 제1 및 제2 멀티플렉서(70 및 72)에 결합된다. 감산기(68)의 캐리 비트는 멀티플렉서(70 및 72)에 역시 결합되는데, 감산기(68)과 조합하여 멀티플렉서(72)의 출력 m이 x 및 y의 최대값이 되고 멀티플렉서(70)의 출력 n이 x 및 y의 최소값이 되게 루팅 논리 회로(66)의 출력을 분류한다.

최대값 m 및 최소값 n의 함수가 선정된 브레이크포인트와 비교된다. 이 함수는 비를 포함한다. 한 실시예에서, 멀티플렉서(72)의 출력 m은 양 m을 2비트 우측으로 시프트하는 시프터(74)에 결합되어 효과적으로 m을 4로 나눈다. 시프터(74)의 출력 m/4 및 멀티플렉서(70)의 출력 n은 감산기(76)에 결합되어 다음에 상세히 설명되는 신규한 기술을 이용하여 실제로 n을 m으로 나누지 않고 n/m의 비를 1/4과 효과적으로 비교한다.

멀티플렉서(70)의 출력 n은 시프터(78)에 결합되는데, 여기에서 양 n은 3 비트 우측으로 시프트되어 유클리드 거리의 2개의 근사치 중 제1 근사치를 계산하는데 이용된다. 시프터(78)의 출력 및 멀티플렉서(72)의 출력 m은 가산기(80)에 결합된다. 가산기(80)의 출력은 m 및 n의 함수를 포함하는 유클리드 거리의 제1 근사치 이다.

감산기(76)의 출력은 또한 시프터(82)에서 1 비트만큼 우측으로 시프트시킴으로써 유클리드 거리의 2개의 근사치 중 제2 근사치를 계산하는데 이용된다. 시프터(82)의 출력 및 멀티플렉서(72)의 출력 m은 가산기(84)에 결합된다. 가산기(84)의 출력은 n 및 m의 함수를 포함하는 유클리드 거리의 제2 근사치이다.

가산기(84 및 80)의 출력, 즉 회로(60)을 통해서 계산되는 유클리드 거리의 2개의 근사치가 멀티플렉서(86)에 결합된다. 감산기(76)의 캐리 비트는 n/m의 비가 1/4보다 큰지의 여부에 따라 유클리드 거리의 2개의 적당한 근사치를 출력하도록 멀티플렉서(86)을 제어하기 위해 결합된다. 멀티플렉서(86)의 출력은 누산기(88)에 가산되고 이 값은 루팅 논리 회로(66)에 부수적인 입력으로서 궤환된다.

회로(60)을 통한 후속적인 통과시, 루팅 논리 회로(66)은 누산기(88)의 현재 값 및 메모리 회로(62)에 기억된 차이값을 값 x 및 y로서 통과시킨다. 메모리 회로(62)에 기억된 모든 차이 값이 루팅 논리회로(66)은 일단 통과하면, 본 발명의 시스템에 의해 발생되는 벡터및사이의 유클리드 거리의 근사치가 누산기(88)에 기억된다.

동작시에, 회로(60)은 상기 식(1)의 구분식 선형 근사치를 계산한다. 간단하게 하기 위해, 거리 식이 다음과 같이 표시될 수 있다.

여기에서, a, b, c 및 d는 대응하는 벡터량들 사이의 차이이다. 식(3)에서 a²+ b²의 제곱근을 q로 치환하면 거리 식은 다음과 같다.

유사하게 식(4)에서 q²+ c²의 제곱근을 r로 치환하면 식(4)는 다음과 같이 변형된다.

거리 식(5)를 유사하게 반복하여 치환하면 거리 식이 다음과 같이 아주 간단한 형태가 된다.

여기에서 y는 두 벡터의 대응하는 성분들 사이의 차이들 중 하나이고 x는 대응하는 성분들 사이의 모든 다른 차이의 제곱의 합의 제곱근이다. 상술한 각 치환 및 최종 식(6)이 2개의 제곱의 합의 제곱근 형태이기 때문에, 반복적으로 이용되는 2개의 제곱의 합의 제곱근의 1차 근사치는 벡터들 사이의 정확한 거리와 근접한 근사치를 산출한다. 이 설명의 참은 3차원 벡터를 이용하여 설명될 수 있다. 3차원에서 거리 식은 다음과 같고

여기에서 양 x, y 및 z는 대응하는 벡터 성분들 사이의 차이를 나타낸다. 이 식은 다음 형태로 나타낼 수 있고,

p²이 x²+ y²과 동일하면, 다음과 같다.

양 x 및 y를 알 수 있기 때문에, 2개의 제곱된 양 x 및 y의 함수인 2개의 제곱의 합의 제곱근에 대한 근사치를 이용하여 값 P가 근사될 수 있다. P의 값이 결정되면, 양 P 및 z를 알 수 있다. 2개의 제곱된 양 P 및 z의 함수에서와 같이 2개의 제곱의 합의 제곱근에 대한 동일한 근사치를 이용하여 식(9)의 거리 D를 결정하게 된다. 벡터들 사이의 유클리드 거리를 근사시키기 위한 반복 기술이 소정 차원의 벡터에 동일하게 적용될 수 있다.

상슬한 바와 같이, 식(3)의 유클리드 거리 D는 다음 형태의 식을 근사시킴으로써 반복적으로 계산된다.

이 식은 다음 형태로 다시 쓸 수 있고

x가 2개의 양 x 및 y 중 큰양인 경우에 근 내의 수는 1보다 작은 수와 1을 더한 값과 같다. 그러므로, 적 P는 1과 y 대 x의 비에 따른 2의 제곱근 사이의 수의 x배와 같다.

제5도는 본 발명에 따른 유클리드 거리를 근사시키기 위해 제1 시스템에 이용되는 근사치를 나타내고 있다. 제5도에서는 양 n 및 m이 각각 y 및 x 대신 치환된다. 곡선(90)은 다음 식으로 나타내는데,

이는 2개의 제곱의 합의 정규화된 제곱근을 정확히 계산한 것이다. 곡선(92)은 본 발명의 교시에서 이용된 하나의 근사치를 나타내고 있다. 1/4를 포함하는 한 실시예에 따라 0과 선정된 브레이크포인트(94) 사이의 n/m의 값들에 대해, 근사 곡선(92)은 제1 근사 성분(96)에 계속되고 있다. 한 실시예에 따른 제1 근사 성분(96)은 다음 식에 따른 m과 n의 함수를 포함한다.

제1 근사 성분(96)이 정수를 포함한다는 것을 알 수 있다.

선정된 브레이크포인트(94) 보다 큰 n/m 값에 대하여, 근사 곡선(92)이 다음 식에 따라 제2 근사 성분(98)에 계속된다.

제4도의 회로(60)는 루팅 논리회로(66)로부터 수신된 출력 x 및 y를 먼저 분류함으로써 제5도의 근사 곡선(92)을 생성한다. 감산기(68)는 루팅 논리회로(66)의 출력 x 및 y 사이의 차이를 계산하고 캐리 비트를 발생시킨다. 감산기(68)에 의해발생된 이 캐리 비트에 기초하여 멀티플렉서(72)는 값 x 및 y의 최대값 m을 출력하는 반면에 멀티플렉서(70)는 값 x 및 y의 최소값 n을 출력한다. 값 n 및 m이 얻어지면, n/m의 비는 시프터(74) 및 감간기(76)를 사용하여 제5도의 선정된 브레이크포인트(94)와 비교된다. 감산기(76)에서, 양 m/4는 양 n으로부터 감산되고 캐리비트가 발생된다. 이 프로세스는 다음 식으로 표시된다.

D가 0 보다 크면, 식(15)은 다음과 같이 다시 쓸 수 있고,

반면에, D가 0 보다 작으면, 식(15)은 다음과 같이 쓸 수 있다.

그러므로, 감산기(76)의 캐리 비트는 실제로 n을 m으로 나누지 않고서 n/m의 비를과 비교하는 방법을 결정하고, 곡선(90)이 회로(60)를 통과하는 동안 제5도의 곡선(92)의 어떤 근사 성분이 곡선(90)을 근사시키는데 사용될 것인지를 결정하게 된다.

제4도의 회로(60)는 시프터(78)에서 양 n을 3 비트 우측으로 시프트시키고, n을 8로 효과적으로 나누고, 가산기(80)에서 양 m을 시프트된 양에 가산함으로써 제1 근사 성분(96)을 계산한다. 또한, 회로(60)는 시프터(82)에서 감산기(76)의 출력을 1비트 우측으로 시프트시키고, 가산기(84)에서 양 m을 시프터(82)의 출력에 가산함으로써 제2 근사 성분(98)을 계산한다. 감산기(76)의 캐리 비트에 기초하여,n/m의 비를 선정된 브레이크포인트(94)와 비교하는 방법에 따라, 멀티플렉서(86)는 가산기(80)의 출력이나 가산기(84)의 출력 중 하나를 누산기(88)에 출력한다.

제6도는 본 발명의 기술에 따라 구성된 참조번호(100)으로 표시된 벡터들 사이의 유클리드 거리를 근사시키기 위한 제2 시스템을 도시한다. 회로(100)는 제4도의 회로(60)의 다른 실시예이다. 회로(100)는 회로(60)의 모든 소자들을 포함하며 선택적인 브레이크포인트를 계산하기 위한 3개의 부가적인 소자들을 더 포함하고 있다. 이 실시예에서, 브레이크포인트는 1/3을 포함한다. 멀티플렉서(70)의 출력 n은 양 n을 1비트만큼 좌측으로 시프트시킴으로써 효과적으로 n을 2로 곱하는 시프터(102)에 결합된다. 멀티플렉서(70)의 출력 n은 또한 가산기(104)의 입력에 결합될 수 있다. 시프터(102)의 출력은 가산기(104)의 입력에 결합된다. 가산기(104)의 출력 3n 및 멀티플렉서(72)의 출력 m은 제4 및 5도와 관련하여 기술한 바와 유사한 방식으로, 실제로 n을 m으로 나누지 않고서 n/m의 비를 1/3과 효과적으로 비교하는 감간기(106)에 결합된다. 이 실시예에서, 감산기(106)의 캐리 비트는 멀티플렉서(86)를 제어하기 위해 결합된다. 제4도의 실시예와는 다르게, 감산기(76)의 캐리 비트는 멀티플렉서(86)을 제어하기 위해 결합되지 않는다.

제7도는 본 발명에 따른 유클리드 거리를 근사시키기 위한 제2 시스템에서 사용되는 근사치를 그래프로서 나타내고 있다. 제5도에서와 같이, 곡선(90)은 2개의 제곱의 합의 제곱근의 정확한 계산값을 나타낸다. 곡선(108)은 본 발명이 제시하는 바에서 사용되는 한 근사치를 나타낸다. 1/3을 포함하는 이 실시예에 따라 0과 선정된 브레이크포인트(110) 사이의 n/m 의 값에 대해, 근사 곡선(108)은 제1근사 성분(96)에 계속된다. 선정된 브레이크포인트(110)보다 큰 n/m의 값에 대해서는 근사곡선(108)은 제2 근사 성분(98)에 계속된다.

제6도의 회로는 브레이크포인트(110)의 계산을 제외하고는 제4도의 회로와 동일한 방식으로 제7도의 근사 곡선(108)을 생성한다. 값 n 및 m이 멀티플렉서(72) 및 멀티플렉서(70)에서 얻어지면, n/m의 비는 시프터(102), 가산기(104) 및 감산기(106)을 사용하여 제7도의 선정된 브레이크포인트(110)과 비교된다. 감산기(106)에서 양 m은 양 3n으로부터 감산되어 캐리 비트가 생성된다. 이 처리는 다음의 식으로 나타내어진다.

D가 O보다 크면, 식(18)은 다음과 같이 다시 쓸 수 있다.

D가 0보다 작으면, 식(18)은 다음과 같이 다시 쓸 수 있다.

그러므로, 감산기(106)의 캐리 비트는 실제로 n을 m으로 나누지 않고서 n/m의 비를 1/3과 비교하는 방법을 결정하고, 제7도의 곡선(108)의 어떤 근사 성분이 회로(100)을 통과하고 있는 동안 곡선(90)을 근사시키는데 사용될 것인지를 결정하게 된다.

제8도는 본 발명이 제시하는 바에 따라 구성된 참조번호(120)으로 표시된 벡터들 사이의 유클리드 거리를 근사시키기 위한 제3 시스템을 도시한다. 회로(120)은 3개의 유클리드 거리의 근사 곡선과 2개의 브레이크포인트를 포함하는 회로(100)의 선택적인 실시예이다. 회로(120)은 제3 근사치 및 제2 브레이크포인트를 계산하기 위한 10개의 성분이 부가되어 회로(100)과 실제적으로 동일하다.

이 실시예에서, 제2 브레이크포인트는 3/4를 포함한다. 멀티플렉서(72)의 출력 m은 시프터(122)에 결합되는데, 이 시프터에서 양 m은 좌측으로 1비트 시프트되어 양 m에 2가 곱해지도록 한다. 시프터(122)의 출력 및 멀티플렉서(72)의 출력 m은 가산기(124)에 결합된다. 멀티플렉서(70)의 출력 n은 시프터(126)에 결합되는데, 여기서 양 n은 좌측으로 2비트 시프터되어 양 n에 4가 곱해지도록 한다. 가산기(124)의 출력 3m은 상술한 새로운 기술을 사용하여 실제적으로 n을 m으로 나누지 않으면서 n/m의 비를 3/4와 효과적으로 비교하는 감산기(128)에서 시프터(126)의 출력인 4n으로부터 감산된다. 감산기(128)의 캐리 비트는 멀티플렉서(86)에 결합된다.

이 실시예에서, 유클리드 거리의 제3 근사치가 계산된다. 멀티플렉서(70)의 출력 n은 시프터(130)에 결합되는데, 여기서 양 n은 좌측으로 4 비트 시프트되어 양 n에 16이 곱해지도록 한다. 시프터(130) 및 시프터(126)의 출력은 가산기(132)에서 가산된다. 멀티플렉서(72)의 출력 m은 감산기(134)에서 시프터(78)의 출력으로부터 감산된다. 감산기(134)의 출력은 감산기(136)에서 가산기(132)의 출력으로부터 감산된다. 감산기(136)의 출력, 2On-7m은 시프터(138)에 결합되는데, 여기서 양 2On-7m 은 양 2On-7m을 32로 나누기 위해 우측으로 5비트 시프트된다. 멀티플렉서(72)의 출력 및 시프터(138)의 출력은 가산기(140)에 결합된다. 가산기(140)의출력은 멀티플렉서(86)의 입력에 결합된다. 가산기(140)의 출력은 유클리드 거리의 제3 근사치를 포함한다.

제9도는 본 발명이 제시하는 바에 따른 유클리드 거리를 근사시키기 위한 제3 시스템에 사용되는 근사치를 그래프로서 나타낸다. 곡선(142)는 본 발명에 사용되는 한 근사치를 나타낸다. 1/3을 포함하는 이 실시예에 따라 0과 제1 선정된 브레이크포인트(110) 사이의 n/m의 비에 대해 근사 곡선(142)는 제1 근사 성분(96)에 계속된다. 제1 선정된 브레이크포인트(110) 보다 크고 제2 선정된 브레이크포인트(144) 보다 작은 n/m의 비에 대해서는 근사 곡선(142)는 제2 근사 성분(98)에 계속된다. 제2 선정된 브레이크포인트(144)보다 큰 n/m의 값에 대해서는 근사 곡선(142)가 다음 방정식에 따른 제3 근사 성분(146)에 계속된다.

제8도의 회로(120)은 제6도의 회로(100)과 동일한 방식에 제2 선정된 브레이크포인트(144) 및 제3 근사 성분(146)을 계산하는 것을 부가하여 제9도의 근사 곡선(142)를 생성한다.

n 및 m의 값이 얻어지면, n/m의 비는 시프터(122), 가산기(124), 시프터(126) 및 감산기(128)을 사용하여 제9도의 제2 선정된 브레이크포인트(144)와 비교된다. 감산기(128)에서, 양 3m은 양 4n으로부터 감산되고 캐리 비트가 생성된다. 이 처리는 다음의 식으로 나타내어진다;

D > 0이면, 식(22)는 다음과 같이 다시 쓸 수 있다:

D < 0이면, 식(22)는 다음과 같이 다시 쓸 수있다.

그러므로, 감산기(128)의 캐리 비트는 실제로 n을 m 으로 나누지 않으면서 n/m의 비를 3/4와 비교하는 방법을 결정하고, 감산기(106)의 캐리 비트와 조합하여, 이것이 회로(120)을 통과하는 동안 제9도의 곡선(142)의 어떤 근사 성분이 근사 곡선(90)에 사용될 것인지를 결정할 것이다.

제8도의 회로(120)은 시프터(138)의 출력, (20-7m)/32에 멀티플렉서(72)의 출력 m을 가산함으로써 가산기(140)에서 제3 근사 성분(146)을 계산한다.

제10도는 두 벡터및사이의 유클리드 거리를 근사시키기 위한 본 발명의 제시에 따라 구성된 참조번호(150)으로 표시된 회로를 도시한다. 회로(150)은 벡터및를 형성하는 각각의 성분들을 수신하고 기억하는 메모리 회로(152)를 포함한다. 프리프로세서 회로(154)는 벡터및의 대응 성분들을 판독하고, 벡터들의 대응 성분들 사이의 차를 계산하고, 메모리(152)에 이들 차이 값을 기억한다. 루팅 논리회로(156)은 메모리(152)에 결합되어 처음 회로(150)을 통과하는 2개의 기억된 차이 값 및 그 다음으로 통과하는 1개의 기억된 차이 값을 판독한다. 루팅 논리 회로(156)의 2개의 출력 x, y는 감산기(158) 및 제1 및 제2멀티플렉서(160 및 162)에 결합된다. 감산기(158)의 캐리 비트는 또한 멀티플렉서(160 및 162)에 접속되는데, 이들 멀티플렉서는 감산기(158)과 조합하여 멀티플렉서(160)의 출력 n이 x 및 y의 최소값이 되고, 멀티플렉서(162)의 출력 m이 x 및 y의 최대값이 되도록 루팅 논리회로(156)의 출력 x 및 y를 분류시킨다.

루팅 논리 회로(156)의 출력 x 및 y의 출력의 함수는 선정된 브레이크포인트와 비교된다. 함수는 비일 수 있다. 한 실시예에서, 루팅 논리 회로(156)의 출력 x는 시프터(164) 및 감산기(166)에 결합된다. 루팅 논리 회로(156)의 출력 y는 시프터(168) 및 감산기(170)에 결합된다. 감산기(170)의 나머지 입력은 시프터(164)의 출력에 결합된다. 감산기(166)의 나머지 입력은 시프터(168)의 출력에 결합된다. 감산기(168 및 170)은 x/y 및 y/x의 비를 상술한 바와 동일한 새로운 기술을 사용하여 1/4와 효과적으로 비교한다.

멀티플렉서(160)의 출력 n은 시프터(172)에 결합되는데, 여기서 유클리드 거리의 2개의 근사치 중 처음 것에 사용되게 하기 위해 양 n은 우측으로 3비트 시프트된다. 시프터(172)의 출력 및 멀티플렉서(162)의 출력 m은 가산기(174)에 결합된다. 가산기(174)의 의 출력은 n 및 m의 함수를 포함하는 유클리드 거리의 제1 근사치이다.

또한 감산기(166 및 170)의 출력이 감산기(166 및 170)의 출력을 시프터(176 및 178)에서 각각 우측으로 1비트씩 시프트시킴으로써 유클리드 거리의 선택적인 제 2 근사치를 계산하는데 사용된다. 시프터(178)의 출력 및 멀티플렉서(162)의 출력 m은 가산기(180)에 결합되고, 여기서 n 및 m의 함수로서 유클리드 거리의 제1의선택적인 제2 근사치가 계산된다. 시프터(176)의 출력 및 멀티플렉서(162)의 출력 m은 가산기(182)에 결합되고, 여기에서 n 및 m의 함수로서 유클리드 거리의 제2의 선택적인 제2 근사치가 계산된다.

가산기(174, 180 및 182)의 출력은 멀티플렉서(184)에 결합되는 감산기(158, 166 및 170)에 의해 발생되는 캐리 비트에 따라 유클리드 거리의 적당한 근사치를 출력하는 멀티플렉서(184)에 결합된다. 멀티플렉서(184)의 출력은 누산기(186)의 현재 값에 가산되고 누산기(186)의 출력은 루팅 논리회로(156)에 부수적인 입력으로서 궤환된다. 회로(150)을 통과한 다음, 루팅 논리회로(156)은 값 x 및 y로서 누산기(186)의 현재 값 및 메모리(152) 내에 기억된 차이 값을 통과시킨다. 메모리(152)에 기억된 차이 값이 모두 루팅 논리회로(156)을 통과하면, 본 발명의 시스템에 의해 발생된 벡터및사이의 유클리드 거리의 근사치는 누산기(186)에 기억된다.

동작시, 회로(15O)은 제4도의 회로(60)과 동일한 방식으로 식(1)의 제1차 근사치를 계산한다. 최대값 m 대 최소값 n의 비와 선정된 브레이크포인트(94)를 비교하면, 회로(60)과 회로(150)의 동작 사이의 유일한 차이를 알 수 있다. 회로(60)에서, 이 비교는 루팅 논리회로(76)으로부터 수신된 x 및 y 값이 멀티플렉서(70 및 72)에서 분류된 후에 감산기(76) 및 시프터(74)에서 실행된다. 회로(120)에서는, 이 비교가 루팅 논리회로(156)의 x 및 y 값을 분류하기 전에 실행된다. 선택적인 비교는 시프터(164)와 조합하여 감산기(170)을 사용하여 그리고 시프터(168)과 조합하여 감산기(166)을 사용하여 이루어진다. 멀티플렉서(184)는 유클리드 거리의 적정한 근사치를 출력하기 위해 감산기(158, 166 및 170)으로부터의 캐리 비트에 의해 제어된다.

지금까지 본 발명의 양호한 실시예에 대해 기술하였다. 본 분야에 숙련된 기술자들은 첨부한 특허 청구 범위에 의해 한정된 본 발명의 원리 및 범위를 벗어나지 않으면서 본 발명을 여러가지 형태로 수정 및 변형시킬 수 있다.

제1도는 본 발명에 따라 함수의 근사치를 구하기 위한 제1 시스템의 블럭도.

제2도는 본 발명에 따라 함수의 근사치를 구하기 위한 제2 시스템의 블럭도.

제3도는 본 발명에 따라 제2 시스템에 의해 이용된 근사치를 나타내는 그래프.

제4도는 본 발명에 따라 구성된 벡터들 사이의 유클리드 거리의 근사치를 구하기 위한 제1 시스템의 블럭도.

제5도는 본 발명에 따라 유클리드 거리의 근사치를 구하기 위한 제1 시스템에 이용되는 근사치를 나타내는 그래프.

제6도는 본 발명에 따라 구성된 벡터들 사이의 유클리드 함수의 근사치를 구하기 위한 제2 시스템의 블럭도.

제7도는 본 발명에 따라 유클리드 거리의 근사치를 구하기 위한 제2 시스템에 이용되는 근사치를 나타내는 그래프.

제8도는 본 발명에 따라 구성된 벡터들 사이의 유클리드 거리의 근사치를 구하기 위한 제2 시스템의 블럭도.

제9도는 본 발명에 따라 유클리드 거리의 근사치를 구하기 위한 제3 시스템에 이용되는 근사치를 나타내는 그래프.

제1O도는 본 발명에 따라 구성된 벡터들 사이의 유클리드 거리의 근사치를 구하기 위한 제4 시스템의 블럭도.

도면의 주요 부분에 대한 부호의 설명

10 : 시스템 12, 32 : 제1 배수 발생 회로

14, 34 : 제2 배수 발생 회로 16, 36 : 제1 함수 발생 회로

18, 38 : 제2 함수 발생 회로 20, 42 : 제1 근사치 발생 회로

22, 44 : 제2 근사치 발생 회로 24, 48 : 근사치 선택 회로

40 : 제3 함수 발생 회로 46 : 제3 근사치 발생 회로

Claims

제1 양에 최대 3개의 2의 거듭제곱을 곱하기 위하여 상기 제1 양을 시프트시키는 회로,

제2 양에 최대 3개의 2의 거듭제곱을 곱하기 위하여 상기 제2 양을 시프트시키는 회로,

상기 제1 및 상기 게2 양을 시프트시키는 상기 회로와 통신하여 상기 제1 및 상기 제2 양의 제1 함수를 발생시키는 회로,

상기 제1 및 상기 제2 양을 시프트시키는 상기 회로와 통신하여 상기 제1 및 상기 제2 양의 제2 함수를 발생시키는 회로,

상기 제1 함수를 발생시키는 상기 회로와 통신하여 상기 제1 함수를 시프터에서 2의 정수배로 나누어서 제1 근사치를 발생시키는 회로,

상기 제2 함수를 발생시키는 상기 회로와 통신하여 상기 제2 함수를 시프터에서 2의 정수배로 나누어서 제2 근사치를 발생시키는 회로, 및

상기 제1 및 상기 제2 근사치를 발생시키는 상기 회로와 통신하여 상기 제1 근사치 또는 상기 제2 근사치를 선택하는 회로

를 포함하는 비선형 함수 근사 시스템.
제1항에 있어서,

상기 선택 회로가 상기 제1 및 상기 제2 근사치 중 큰 값을 출력시키는 회로를 포함하는 비선형 함수 근사 시스템.
제1항에 있어서,

상기 선택 회로는,

상기 제1 및 상기 제2 양의 비가 선정된 브레이크포인트(breakpoint)보다 작은 경우에는 상기 제1 근사치를 출력하는 회로, 및

상기 제1 및 상기 제2 양의 비가 선정된 브레이크포인트보다 큰 경우에는 상기 제2 근사치를 출력하는 회로

를 포함하는 비선형 함수 근사 시스템.
제1 양에 최대 3개의 2의 거듭제곱을 곱하기 위하여 상기 제1 양을 시프트시키는 회로,

제2 양에 최대 3개의 2의 거듭제곱을 곱하기 위하여 상기 제2 양을 시프트시키는 회로,

상기 제1 및 상기 제2 양을 시프트시키는 상기 회로와 통신하여 상기 제1 및 상기 제2 양의 제1 함수를 발생시키는 회로,

상기 제1 및 상기 제2 양을 시프트시키는 상기 회로와 통신하여 상기 제1 및 상기 제2 양의 제2 함수를 발생시키는 회로,

상기 제1 및 상기 제2 양을 시프트시키는 상기 회로와 통신하여 상기 제1 및 상기 제2 양의 제3 함수를 발생시키는 회로,

상기 제1 함수를 발생시키는 상기 회로와 통신하여 상기 제1 함수를 시프터에서 2의 정수배로 나누어서 제1 근사치를 발생시키는 회로,

상기 제2 함수를 발생하는 상기 회로와 통신하여 상기 제2 함수를 시프터에서 2의 정수배로 나누어서 제2 근사치를 발생시키는 회로,

상기 제2 함수를 발생하는 상기 회로와 통신하여 상기 제2 함수를 시프터에서 2의 정수배로 나누어서 제3 근사치를 발생시키는 회로, 및

상기 제1, 상기 제2, 및 상기 제3 근사치를 발생하는 상기 회로와 통신하여 상기 제1, 상기 제2 또는 상기 제3 근사치를 선택하는 회로

를 포함하는 함수 근사 시스템.
제4항에 있어서,

상기 선택 회로는

상기 제1 및 제2 양의 비가 제1 선정된 브레이크포인트보다 적은 경우 상기 제1 근사치를 출력하는 회로;

상기 제1 및 제2 양의 비가 상기 제1 선정된 브레이크포인트와 제2 선정된 브레이크포인트 사이인 경우 상기 제2 근사치를 출력하는 회로; 및

상기 제1 및 제2 양의 비가 상기 제2 선정된 브레이크포인트보다 더 큰 경우 상기 제3 근사치를 출력하는 회로

를 포함하는 시스템.
대응하는 벡터 성분들 간의 제1 및 제2 차이의 함수로서 제1 근사치를 계산하는 회로 - 상기 제1 근사치를 계산하는 회로는, 제1 및 제2 차이를 선택하는 회로, 상기 선택 회로에 결합되어 상기 제1 및 제2 선택된 차이로부터 최대값 및 최소값을 출력하는 회로, 및 상기 선택 회로 및 상기 출력 회로와 통신하여 상기 최대값 및 상기 최소값의 함수로서 제1 근사치를 계산하는 회로를 포함함 -,

상기 제1 및 제2 차이의 제2 함수로서 제2 근사치를 계산하는 회로 - 상기 제2 근사치를 계산하는 회로는 제1 및 제2 차이를 선택하는 회로, 상기 선택 회로에 결합되어 상기 제1 및 제2의 선택된 차이로부터 최대값 및 최소값을 출력하는 회로, 및 상기 선택 회로 및 상기 출력 회로와 통신하여 상기 최대값 및 상기 최소값의 함수로서 제2 근사치를 계산하는 회로를 포함함 -, 및

상기 제1 근사치를 계산하는 상기 회로 및 제2 근사치를 계산하는 상기 회로와 통신하여 상기 제1 및 제2 차이의 제3 함수를 선정된 브레이크포인트와 비교하여 상기 제1 및 상기 제2 근사치 중 어느 한 근사치를 선택하는 회로

를 포함하며,

상기 계산 회로와 상기 선택 회로는 시프터들, 가산기들 및 멀티플렉서들로 구성되는 벡터 처리 시스템.
제6항에 있어서,

상기 제1 또는 제2 근사치를 선택하기 위한 상기 회로는,

제1 및 제2 차이를 선택하는 회로,

상기 선택 회로에 결합되어 상기 제1 및 제2의 선택된 차이로부터 최대값 및 최소값을 출력하는 회로,

상기 선택 회로와 통신하여 상기 제1 차이 및 상기 제2 차이의 제3 함수를 선정된 브레이크포인트와 비교하는 회로, 및

상기 비교 회로, 상기 제1 근사치 계산 회로, 및 상기 제2 근사치 계산 회로에 결합되어 상기 제1 근사치나 상기 제2 근사치중 어느 하나를 출력하는 회로

를 포함하는 벡터 처리 시스템.
제1 및 제2 벡터 간의 유클리드 거리(Euclidean distance) 근사 시스템에 있어서,

상기 제1 및 제2 벡터의 각각의 성분에 대응하는 값을 기억하는 회로,

상기 기억 회로에 결합되어, 제1 및 제2 벡터의 대응하는 성분 간의 차이를 계산하고 이 차이를 상기 기억 회로 내에 기억시키는 회로,

상기 기억 회로에 결합되어, 제1 및 제2 값을 선택하는 회로 - 상기 제1 및 제2 값 중 적어도 하나는 상기 차이중 하나를 포함함 -,

상기 선택 회로에 결합되어 상기 제1 및 제2의 선택된 값들로부터 최대값 및 최소값을 출력시키는 회로,

상기 선택 회로와 통신하여 상기 제1 값 및 상기 제2 값의 제1 함수를 상기 선정된 브레이크포인트와 비교하는 회로,

상기 비교 회로 및 상기 출력 회로에 결합되어, 상기 제1 함수가 상기 선정된 브레이크포인트보다 작거나 같다면 상기 제1 및 상기 제2 값의 제2 함수를 누산기에 가산시키는 회로, 및

상기 비교 회로 및 상기 출력 회로에 결합되어, 상기 제1 함수가 상기 선정된 브레이크포인트보다 크다면 상기 제1 및 상기 제2 값의 제3 함수를 상기 누산기에 가산시키는 회로

를 포함하며,

상기 누산기의 출력은 상기 선택 회로에 결합되는 제1 및 제2 벡터 간의 유클리드 거리 근사 시스템.
제8항에 있어서,

최대값 및 최소값을 출력시키는 상기 회로는,

상기 선택 회로에 결합되어 상기 제1 및 제2 값의 최대값을 출력시키도록 동작하는 제1 멀티플렉서,

상기 선택 회로에 결합되어 상기 제1 및 제2 값의 최소값을 출력시키도록 동작하는 제2 멀티플렉서, 및

상기 선택 회로에 결합되어 상기 제1 및 제2 멀티플렉서에 전달되는 캐리 비트를 발생하기 위해 상기 제1 값을 상기 제2 값으로부터 감산하고, 상기 제1 및 제2 멀티플렉서의 출력을 제어하도록 동작하는 감산기

를 포함하는 유클리드 거리 근사 시스템.
제8항에 있어서,

상기 비교 회로는,

상기 출력 회로로부터 최대값을 수신하도록 결합되어, 상기 최대값을 4로 나누기 위해 상기 최대값을 2비트만큼 우측으로 시프트시키는 시프터, 및

상기 출력 회로로부터 최소값을 수신하고 상기 시프터로부터의 출력을 수신하도록 결합되어, 상기 최대값에 대한 상기 최소값의 비가 1/4보다 작은지의 여부를 가리키는 캐리 비트를 발생하는 감산기

를 포함하는 유클리드 거리 근사 시스템.
제8항에 있어서,

상기 비교 회로는,

상기 출력 회로로부터 상기 최소값을 수신하도록 결합되어, 상기 최소값에 2를 곱하기 위해 상기 최소값을 1 비트만큼 좌측으로 시프트시키는 시프터,

상기 출력 회로로부터의 상기 최소값에 상기 시프터의 출력을 가산시키도록 결합되어 있는 가산기, 및

상기 출력 회로로부터의 상기 최대값을 수신하고 상기 가산기로부터의 출력을 수신하도록 결합되어, 상기 최대값에 대한 상기 최소값의 비가 1/3보다 작은지의 여부를 가리키기 위한 캐리 비트를 발생하는 감산기

를 포함하는 유클리드 거리 근사 시스템.
제8항에 있어서,

제2 함수를 가산하는 상기 회로와 제3 함수를 가산하는 상기 회로는,

상기 출력 회로로부터 상기 최대값을 수신하도록 결합되어, 상기 최대값을 4로 나누기 위하여 상기 최대값을 2비트만큼 우측으로 시프트시키는 제1 시프터,

상기 출력 회로로부터의 상기 최소값과 상기 제1 시프터로부터의 출력을 감산하도록 결합되어 있는 감산기,

상기 출력 회로로부터의 상기 최소값을 수신하도록 결합되어, 상기 최소값을 8로 나누기 위하여 상기 최소값을 3비트만큼 우측으로 시프트시키는 제2 시프터,

상기 감산기의 출력에 결합되어, 상기 감산기의 상기 출력을 2로 나누기 위하여 상기 출력을 1 비트만큼 우측으로 시프트시키는 제3 시프터,

상기 출력 회로로부터의 상기 최대값과 상기 제2 시프터의 상기 출력을 수신하도록 결합되어, 상기 최대값과 상기 제2 시프터의 상기 출력을 가산하는 제1 가산기,

상기 출력 회로로부터의 상기 최대값과 상기 제3 시프터의 출력을 수신하도록 결합되어, 상기 최대값과 상기 제3 시프터의 상기 출력을 가산하는 제2 가산기,

상기 제1 및 제2 가산기로부터의 출력을 수신하도록 결합되어 있고 상기 비교 회로로부터의 제어 비트에 결합되어 그의 출력이 상기 제1 가산기의 상기 출력 또는 상기 제2 가산기의 상기 출력이 되도록 제어되는 멀티플렉서, 및

상기 멀티플렉서의 상기 출력에 결합되어 상기 멀티플렉서의 출력을 가산하기 위해서 상기 선택 회로에 결합되어 있는 출력 단자를 갖는 누산기

를 포함하는 유클리드 거리 근사 시스템.
제1 및 제2 벡터 간의 유클리드 거리 근사 시스템에 있어서,

제1 및 제2 벡터의 각각의 성분에 대응하는 값을 기억하는 회로,

상기 기억 회로에 결합되어, 상기 제1 및 제2 벡터의 대응하는 성분들 간의 차이를 계산하고 이 차이를 상기 기억 회로에 기억시키는 회로,

상기 기억 회로에 결합되어, 제1 및 제2 값을 선택하는 회로 - 상기 제1 및 제2 값 중 적어도 하나는 상기 차이를 포함함 -,

상기 선택 회로에 결합되어, 상기 제1 및 제2의 선택된 값들로부터 최대값 m과 최소값 n를 출력하는 회로,

상기 선택 회로와 통신하여, 상기 제1 값 및 상기 제2 값의 제1 함수를 선정된 제1 브레이크포인트와 비교하고, 상기 제1 값 및 상기 제2 값의 상기 제1 함수를 선정된 제2 브레이크포인트와 비교하는 회로,

상기 비교 회로 및 상기 출력 회로에 결합되어, 상기 제1 함수가 상기 제1의 선정된 브레이크포인트보다 작거나 같다면 상기 제1 및 상기 제2 값의 제2 함수를 누산기에 가산시키는 회로,

상기 비교 회로 및 상기 출력 회로에 결합되어, 상기 제1 함수가 상기 제1의 선정된 브레이크포인트보다 크고 상기 제1 함수가 상기 제2 브레이크포인트보다 작다면 상기 제1 및 상기 제2 값의 제3 함수를 상기 누산기에 가산시키는 회로, 및

상기 비교 회로 및 상기 출력 회로에 결합되어 상기 제1 함수가 상기 제2 선정된 브레이크포인트보다 크다면 상기 제1 및 상기 제2 값의 제4 함수를 상기 누산기에 가산시키는 회로 - 상기 누산기의 출력은 상기 선택 회로에 결합됨 -

를 포함하는 제1 및 제2 벡터 간의 유클리드 거리 근사 시스템.
제13항에 있어서,

상기 선정된 제1 브레이크포인트는 1/3을 포함하며, 상기 선정된 제2 브레이크포인트는 3/4를 포함하는 유클리드 거리 근사 시스템.
제13항에 있어서,

상기 제2 함수가 함수을 포함하는 유클리드 거리 근사 시스템.
제13항에 있어서,

상기 제3 함수가 함수을 포함하는 유클리드 거리 근사 시스템.
제13항에 있어서,

상기 제4 함수가 함수을 포함하는 유클리드 거리 근사 시스템.
제1 및 제2 벡터 간의 유클리드 거리 계산 방법에 있어서,

상기 제1 및 제2 벡터의 각각의 성분에 대응하는 값을 메모리 회로에 기억시키는 단계,

감산기 회로에서 상기 제1 및 제2 벡터의 대응 성분 간의 차이를 계산하는 단계,

계산된 차이를 메모리 회로에 기억시키는 단계,

두개의 값을 선택하는 단계로서, 상기 선텍된 두개의 값 중 적어도 하나가 상기 기억된 차이가 되는 2개의 값을 선택하는 단계,

상기 선택된 값들로부터 최대값 및 최소값을 결정하는 단계,

상기 선택된 값들의 제1 함수를 선정된 브레이크포인트와 비교하는 단계,

상기 제1 함수가 상기 선정된 브레이크포인트보다 작거나 같다면 선택된 값들의 제2 함수를 누산기에 가산시키는 단계,

상기 제1 함수가 상기 선정된 브레이크포인트보다 크다면 선택된 값들의 제3 함수를 상기 누산기에 가산시키는 단계, 및

상기 2개의 값을 선택하고 상기 선택된 값들을 비교한 다음 누산기에 가산시키는 단계들을 반복하는 단계

를 포함하며,

상기 2개의 값을 선택하는 단계는 모든 기억되어 있는 차이들이 선택될 때까지 하나의 기억되어 있는 차이와 상기 누산기의 현재 값을 선택하는

제1 및 제2 벡터 간의 유클리드 거리 계산 방법,
제18항에 있어서,

최대값 및 최소값을 결정하는 상기 단계는,

감산기에서 상기 두개의 선택된 값들을 감산하여 캐리 비트를 발생하는 단계,

상기 감산기에 의해서 발생된 상기 캐리 비트에 기초해서 최대값을 출력시키기 위해 선택된 값들을 제1 멀티플렉서를 통해서 통과시키는 단계, 및

상기 감산기에 의해서 발생된 상기 캐리 비트에 기초해서 최소값을 출력시키기 위해 선택된 값들을 제2 멀티플렉서를 통해서 통과시키는 단계

를 포함하는 유클리드 거리 근사 방법.
제18항에 있어서, 비를 비교하는 단계는,

시프터에서 최대값을 2 비트만큼 우측으로 시프트시켜서 상기 최대값을 4로 나누는 단계,

감산기에서 상기 최소값과 상기 시프트된 최대값을 감산하는 단계,

상기 최대값에 대한 상기 최소값의 비가 상기 선정된 브레이크포인트보다 크거나, 같거나 또는 작은지의 여부를 가리키도록 감산기에서 캐리 비트를 발생하는 단계

를 포함하는 유클리드 거리 근사 방법.
제18항에 있어서,

상기 비를 비교하는 단계는,

제1 및 제2 시프터에서 상기 두개의 선택된 값을 2 비트만큼 우측으로 시프트시켜서 상기 두개의 선택된 값들을 4로 나누는 단계,

제1 감산기에서 상기 제1 선택된 값과 상기 시프트된 제2 값을 감산하는 단계,

제2 감산기에서 상기 제2 선택된 값과 상기 시프트된 제1 값을 감산하는 단계, 및

상기 비들이 선정된 브레이크포인트보다 크거나, 같거나 또는 작은지 여부를 가리키기 위하여 캐리 비트를 제1 감산기 및 제2 감산기에서 발생시키는 단계

를 포함하며,

상기 비를 비교하는 단계를 최대값 및 최소값을 결정하는 상기 단계와 동시에 수행되는 유클리드 거리 근사 방법.
제18항에 있어서,

상기 제2 함수를 가산하는 상기 단계와 상기 제3 함수를 가산하는 상기 단계는,

시프터에서 상기 최소값을 3 비트만큼 우측으로 시프트시켜서 상기 최소값을 8로 나누는 단계,

시프터에서 상기 비를 비교하는 단계의 상기 출력을 1 비트만큼 우측으로 시프트시켜서 상기 비를 비교하는 단계의 상기 출력을 2로 나누는 단계,

상기 최대값과 상기 시프트된 최소값을 가산기에서 가산하는 단계,

상기 최대값과 상기 비를 비교하는 단계의 시프트된 출력을 가산기에서 가산하는 단계,

멀티플렉서에서, 상기 비를 비교하는 단계의 상기 출력에 기초해서 두개의 가산 단계에 의해 발생된 합을 출력하는 단계, 및

상기 출력 단계에 의해 발생된 출력을 누산기에 가산시키는 단계

를 포함하는 유클리드 거리 근사 방법.
제18항에 있어서,

제2 함수를 가산하는 상기 단계와 제3 함수를 계산하는 상기 단계는,

시프터에서 최소값을 3 비트만큼 우측으로 시프트시켜서 상기 최소값을 8로 나누는 단계,

상기 비를 비교하는 단계의 제1 출력을 우측으로 1 비트만큼 시프트시켜서 상기 비를 비교하는 단계의 상기 제1 출력을 2로 나누는 단계,

상기 비를 비교하는 단계의 제2 출력을 우측으로 1 비트만큼 시프트시켜서 상기 비를 비교하는 단계의 상기 제2 출력을 2로 나누는 단계,

가산기에서 상기 최대값과 상기 시프트된 최소값을 가산하는 단계,

가산기에서 상기 최대값과 상기 비를 비교하는 단계의 상기 시프트된 최소값을 가산하는 단계,

상기 가산기에서 상기 최소값과 상기 비를 비교하는 단계의 상기 시프트된 제2 출력 가산하는 단계,

멀티플렉서에서, 상기 비를 비교하는 단계의 상기 출력들과 최대값을 결정하는 단계의 출력에 기초해서 상기 3개의 가산 단계에 의해 발생된 합을 출력하는 단계, 및

상기 출력 단계에 의해 발생된 상기 출력을 누산기에 가산하는 단계를 포함하는 유클리드 거리 근사 방법.