[go: up one dir, main page]

KR100359965B1 - 프로세서와이의연산방법 및 데이타프로세서 - Google Patents

프로세서와이의연산방법 및 데이타프로세서 Download PDF

Info

Publication number
KR100359965B1
KR100359965B1 KR1019960010745A KR19960010745A KR100359965B1 KR 100359965 B1 KR100359965 B1 KR 100359965B1 KR 1019960010745 A KR1019960010745 A KR 1019960010745A KR 19960010745 A KR19960010745 A KR 19960010745A KR 100359965 B1 KR100359965 B1 KR 100359965B1
Authority
KR
South Korea
Prior art keywords
addition
data
bit
input
processor
Prior art date
Application number
KR1019960010745A
Other languages
English (en)
Other versions
KR960038594A (ko
Inventor
다께시 이찌가와
Original Assignee
캐논 가부시끼가이샤
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 캐논 가부시끼가이샤 filed Critical 캐논 가부시끼가이샤
Publication of KR960038594A publication Critical patent/KR960038594A/ko
Application granted granted Critical
Publication of KR100359965B1 publication Critical patent/KR100359965B1/ko

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/53—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel
    • G06F7/5318—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel with column wise addition of partial products, e.g. using Wallace tree, Dadda counters
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/50—Adding; Subtracting
    • G06F7/505—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination
    • G06F7/509—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination for multiple operands, e.g. digital integrators
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/607—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers number-of-ones counters, i.e. devices for counting the number of input lines set to ONE among a plurality of input lines, also called bit counters or parallel counters
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03K—PULSE TECHNIQUE
    • H03K19/00—Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits
    • H03K19/20—Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits characterised by logic function, e.g. AND, OR, NOR, NOT circuits
    • H03K19/23—Majority or minority circuits, i.e. giving output having the state of the majority or the minority of the inputs
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
    • G06F2207/3804—Details
    • G06F2207/3808—Details concerning the type of numbers or the way they are handled
    • G06F2207/3832—Less usual number representations
    • G06F2207/3836—One's complement
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
    • G06F2207/48—Indexing scheme relating to groups G06F7/48 - G06F7/575
    • G06F2207/4802—Special implementations
    • G06F2207/4816—Pass transistors
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
    • G06F2207/48—Indexing scheme relating to groups G06F7/48 - G06F7/575
    • G06F2207/4802—Special implementations
    • G06F2207/4818—Threshold devices
    • G06F2207/4822—Majority gates

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Computer Hardware Design (AREA)
  • Complex Calculations (AREA)
  • Logic Circuits (AREA)

Abstract

다수의 다중 비트 데이타의 가산을 포함하는 연산을 수행하는 프로세서에서, 다수의 다중 비트 데이타의 공통 자리상의 값은 각각의 자리에 의해 설정된 수 검출기 내로 병렬로 입력되고, 입력 값의 고 신호의 수는 2진 표시로 출력되고, 다수의 ND로부터의 출력은 캐리 없이 고속 연산을 실행하도록 전 가산기에 의해 가산된다. 가산시에, 공통 자리를 갖지 않는 값은 가산되기 전에 단일 데이타로 통합된다.

Description

프로세서와 이의 연산 방법 및 데이타 프로세서{PROCESSOR, ITS OPERATION METHOD, AND DATA PROCESSOR}
본 발명은 가산 및 승산을 위한 반도체 디바이스와 같은 프로세서, 이 디바이스에서 사용된 연산 방법, 및 상기 프로세서가 사용된 데이타 프로세서에 관한 것이다.
최근 몇 년 동안, 소형화로 인한 반도체 제조 기술 및 알고리즘을 포함하는 반도체 회로 기술의 놀라운 발전으로 인해 가산기 또는 승산기의 연산 속도가 상당히 증가되고 있다. 산술 프로세싱은 CPU(central processing unit) 또는 DSP(digital signal processor)를 포함하는 다양한 종류의 반도체 디바이스들에서 사용되고 있다. 그러나, 기술이 발전될 수록, 보다 높은 성능을 갖는, 즉, 고속의 산술 프로세싱이 필요하게 되었다.
특히, 다중 매체 시대에서 영상 처리 및 매트릭스 연산과 같이 상당량의 계산들을 필요로 하는 분야에서는, 고속 프로세싱이 필요하게 되었고, 특히, 가산기 또는 승산기 프로세싱은 그 성능을 결정하기 위한 가장 중요한 프로세싱 중 하나이고 고속으로 실행될 필요가 있다.
본 연산 방법의 가산기의 일례로서, "CMOS VLSI(Supervised by Sugano Takuo, Baifukan)의 설계"로 기술된 가산기에 관해 기술하겠다.
2개의 이진수들의 가산을 위해, X 및 Y가 이진수를 나타내고, S가 X 및 Y의 합을 나타내고, C가 캐리를 나타낸다고 가정하면, X 및 Y가 각각 단일 자리를 가지는 경우 다음 4개의 타입들의 계산들이 성립된다.
X = 0 및 Y = 0일 때, S = 0 및 C = 0.
X = 0 및 Y = 1일 때, S = 1 및 C = 0.
X = 1 및 Y = 0일 때, S = 1 및 C = 0.
X = 1 및 Y = 1일 때, S = 0 및 C = 1.
합 S와 캐리 C가 상술된 바를 진리 테이블로 고려하여 논리 식으로 표현하면, S = X + Y 및 C = X × Y가 얻어진다. 이는 제41A도에 도시된 바와 같이 단일 배타적 OR 및 단일 AND를 기초로 하여 2-입력 2-출력 회로에서 달성될 수 있다. 이 기능을 갖는 회로는 반 가산기라고 한다.
이진수들이 각각 다수의 자리를 가지면, 다시 말해서, 2개 또는 그 이상의 비트들의 비트 폭을 각각 가지면, 하위 자리로부터 캐리 신호의 프로세싱을 실행할 필요가 있다. 따라서 프로세싱은 한 자리에서 3개의 이진수들, Xi, Yi, 및 Ci-1이 가산될 수 있는 회로를 필요로 한다. 이 3-입력 2-출력 회로는 전 가산기라고 한다. 제 41C도는 진리 테이블 및 그 동작을 나타내는 논리 형태를 도시한 것이다. 임의의 수의 자리의 가산을 실행하기 위한 회로는 요구된 수의 전 가산기들을 장치함으로써 또한 하위 가산기의 캐리 신호가 상위 가산기에 입력되도록 가산기들을 접속시킴으로써 달성될 수 있다. 이는 리플 캐리 가산기(ripple carry adder)라고 한다. 4-비트 가산기로서 형성된 일례는 제41B도에 도시되어 있다. 제41C도의 진리표의 액션을 정확하게 반영하는 단일-비트 전 가산기를 위한 다수의 회로가 있더라도, 섬 신호(sum signal)를 생성하는 것이 아니라 가능한한 빨리 하위 자리로부터 상위 자리로 입력된 캐리 신호를 송신하는 고속 동작을 목적으로 설계하기 위한 것이다. 제41D도는 이 점을 고려해서 설계된 전 가산기들의 일례를 도시한 것이다.
예를 들어, 자리의 수가 16 비트로 증가되면, 개별적인 전 가산기의 향상으로 인해 달성된 속도 상승에는 한계가 생기고, 따라서 속도 상승은 전체 16-비트 가산기에 의해 달성될 수 있다. 가산기의 연산 속도가 상술된 바와 같이 캐리 송신 속도에 의해 조절되기 때문에, 가산기 자체의 캐리 신호가 하위 가산기로부터의 캐리 신호를 기다리지 않고 결정될 수 있는 경우 속도 상승은 달성될 수 있다.
모든 자리를 위한 캐리 신호는 자신의 자리의 입력 값 및 최하위 자리의 캐리 신호로부터만 생성될 수 있다. 이는 캐리 록 어헤드(CLA : carry look ahead)라고 한다. 이 방법이 적용된 회로(CLA 회로)의 일례는 제42A도에 도시되어 있다. 제42A도에서, HA는 제42B도의 반 가산기를 나타내고, 점선에 의해 표시된 부분은 제42C도의 CMOS 회로에 의해 달성된다.
회로의 실제 구현에서, 모든 자리를 위한 대부분의 캐리 신호는 하드웨어의 양 또는 효율성을 고려하여 CLA에서 생성되지 않지만, 캐리 신호는 예를 들면 4개의 비트들로 구성된 블럭과 같은 각각의 블럭을 위한 CLA를 사용하여 송신되고, 캐리 신호는 각 블럭(블럭 CLA) 내의 리플을 사용하여 송신된다. 이 방법에서 16-비트 가산기의 일례는 제43도에 도시되어 있다.
가산기를 사용하여 감산기의 2의 보수를 피감수에 가산함으로써 감산이 달성된다.
그러나, 상술된 방법에서, 소자들의 수 및 동작 시간이 피연산자들의 수의 증가로 인해 상당히 증가되기 때문에 피연산자들의 증가에 대항하여 동작 속도를 더 빠르게 하는 것은 쉽지 않다.
예를 들어, 데이타의 63개의 피스들이 전체적으로 가산되는 경우, 가산 동작들의 병렬 6 단계들이 제44도에 도시된 바와 같이 빠른 동작 속도로 실행될 수 있지만, 62개의 전 가산기들이 필요하다. 한편, 소자들의 수가 감소되는 경우 제45도에 도시된 바와 같이 단일 전 가산기에 의해서만 이 동작이 실행될 수 있지만 가산은 순차적으로 62회 실행되어야만 한다.
다음으로, 병렬 승산기는 본 연산 방법의 승산기의 일례로서 이하에 간단히 기술된다.
(n ×n) 비트들의 승산에서, 부분 적은 다음과 같이 구해진다.
여기에서 부분 적은 승산기 Y의 단일 비트 2iyj(J = 0, 1, ..., n-1)에 의해 다음의 피승수를 곱한 결과이다:
2진수들에는 0과 1만 있기 때문에, Yj가 0일 때 Pij는 항상 0이고, Yj가 1일 때 Pij각 비트는 Xi의 각 비트와 동일하다. 따라서, 부분 적은 피승수의 각 비트 및 승산기의 비트간에 AND를 함으로써 달성될 수 있다. 승산기 비트들의 가중에 따라 생성된 부분 적들의 자리를 조정하고 이들을 서로 가산함으로써, 다음 승산 결과가얻어질 수 있다:
가장 기본적인 병렬 승산기는 상술된 부분 적들을 생성하기 위한 하드웨어(AND 게이트) 및 어레이의 부분 적들을 가산하기 위한 회로를 장치하고 이들을 연결시킴으로써 달성될 수 있다. 8비트 ×8비트의 병렬 승산기는 제46도의 일례로서 도시되어 있다. 이 도면에 도시된 바와 같이, 병렬 승산기는 전 가산기(301), 반 가산기(302) 및 AND 게이트(303)를 포함한다.
이 예에 도시된 바와 같이, (n ×n) 비트들의 승산에서, 부분 적들은 n2개의 AND 게이트들로 쉽고 빠르게 계산되고 부분 적들을 가산하기 위한 가산 단계는 연산 속도를 조절한다. 따라서, 부분 적들을 위한 가산 단계의 속도를 증가시키는 것이 승산기의 속도 상승에 중요한 열쇠이다.
향상된 방법으로서, 연산 속도를 증가시키기 위해, 부분 적들을 위한 가산 단계의 캐리 신호를 다음 가산 단계의 가산기에 송신함으로써 자신의 단계에서 캐리 신호를 송신할 필요가 없는 캐리 세이브 가산기 방법, 동일한 자리에서 가산 단계를 병렬로 실행하기 위한 월리스-트리(Wallace-tree) 방법(Wallace, C., IEEE Trans, on Electronic Computers, EC-13, 1, 1964, pp14-17), 및 생성된 부분 적들의 수를 감소시키기 위한 부쓰(Booth) 알고리즘이 사용되는 방법이 있다.
그러나, 상술된 방법에서, 소자들의 수 및 동작 시간은 비트들의 수의 증가로 상당히 증가되고 비트들의 증가에 대항하여 속도를 더 증가시키는 것은 쉽지 않다. 따라서, 다치 논리(multivalued logic)가 적용된 승산기가 최근 보고되었다(T. Hanyu et al. Proc. IEEE Int. Symp. on MVL, pp19-26, May (1994), Nov. 1993). 그러나,본 방법에서 실제로 사용되지 않았다.
본 발명의 목적은 보다 적은 소자들로 고속 연산들을 실행하는 프로세서와 그 방법 및 데이타 프로세서를 제공하여, 상술된 기술적인 문제점들을 해결하는데 있다.
본 발명의 다른 목적은 필요한 소자들의 수를 감소시키고 연산 속도가 증가된 프로세서 및 데이타 프로세서의 전력 소비를 감소시키는데 있다.
본 발명의 다른 목적은 가산에서 캐리 신호들의 송신을 제거함으로써 연산 속도를 증가시키는데 있다.
본 발명의 또 다른 목적은 연산 속도를 증가시키기 위해 데이타의 재구성에 의해 가산될 데이타의 양을 감소시키고 연산에 필요한 소자들의 수를 감소시키는데 있다.
본 발명의 다른 목적은 병렬로 연산들을 실행함으로써 프로세싱 속도를 증가시키는데 있다.
한 특성에 따라서, 이 목적들을 달성하는 본 발명은 다수의 다중 비트 데이타의 공통 자리에서 데이타를 함께 가산하기 위한 제1 가산 수단 및 제1 가산 수단에 의해 구해진 가산 결과들의 합을 계산하기 위한 제2 가산 수단을 포함하는 다수의 다중 비트 데이타를 가산하기 위한 프로세서에 관한 것이다.
다른 특성에 따라서, 이 목적들을 달성하는 본 발명은 다수의 다중 비트 데이타의 각각의 단일 비트들의 부분 적들을 생성하기 위한 부분 적 생성 수단, 부분 적 생성 수단에 의해 생성된 다수의 부분 적들의 공통 자리에서 데이타를 함께 가산하기 위한 제1 가산 수단, 및 제1 가산 수단에 의해 구해진 가산 결과들의 합을 계산하기 위한 제2 가산 수단을 포함하는 다수의 다중 비트 데이타를 승산하기 위한 프로세서에 관한 것이다.
또 다른 특성에 따라서, 이 목적들을 달성하는 본 발명은 독립적으로 각각의 자리를 가산하기 위한 제1 가산 단계 및 제1 가산 단계에서 구해진 가산 결과들의 합을 계산하기 위한 제2 가산 단계를 포함하는 다수의 다중 비트 데이타를 가산하기 위한 연산 방법에 관한 것이다.
다른 특성에 따라서, 이 목적들을 달성하는 본 발명은 다수의 다중 비트 데이타의 각각의 단일 비트들의 부분 적들을 생성하기 위한 부분 적 생성 단계, 부분 적 생성 단계에서 생성된 다수의 부분 적들의 공통 자리에서 데이타를 함께 가산하기 위한 제1 가산 단계, 및 제1 가산 단계에서 구해진 가산 결과들의 합을 계산하기 위한 제2 가산 단계를 포함하는 다수의 다중 비트 데이타를 승산하기 위한 연산 방법에 관한 것이다.
다른 특성에 따라서, 이 목적들을 달성하는 본 발명은 데이타를 입력하기 위한 입력 수단, 데이타를 저장하기 위한 기억 수단, 기억 수단에 저장된 데이타 및 입력 수단에 의해 입력된 데이타를 규정된 프로세싱 프로시져로 프로세싱하기 위한 프로세싱 수단, 및 프로세싱 수단의 프로세싱 결과들을 출력하기 위한 출력 수단에 관한 것으로, 프로세싱 수단은 다수의 다중 비트 데이타의 공통 자리에서 데이타를함께 가산하기 위한 제1 가산 수단 및 제1 가산 수단에 의해 구해진 가산 결과들의 합을 계산하기 위한 제2 가산 수단을 포함하여 다수의 다중 비트 데이타의 가산을 실행한다.
여타 목적들 및 장점들은 다음의 본 발명의 양호한 실시예의 설명으로부터 본 기술 분야에 숙련된 자들에게 명백해질 것이다. 이 설명은 본 발명의 일부를 형성하고 본 발명의 일례를 도시하고 있는 첨부된 도면을 참조한다. 그러나, 이 예는 본 발명의 다수의 실시예들을 철저히 규명해 낸 것은 아니고, 따라서 본 발명의 범위를 결정하기 위해 상세한 설명 후의 청구 범위가 참조된다.
본 발명은 첨부된 도면을 사용하여 이하에 상세히 기술하겠다.
[ 제1 실시예 ]
본 실시예에 따라서, 다수의 다중 비트 데이타의 가산 방법을 7개의 8-비트 데이타 시퀀스들의 가산 연산을 일례로 사용하여 설명하겠다.
제1도를 참조하면, 이 실시예가 도시되어 있다. 이 실시예에서 7개의 8-비트 데이타 시퀀스를 가산하기 위해, 제1 가산 단계는 먼저 각각의 자리에서 7개의 8-비트 데이타 시퀀스를 가산함으로써 실행된다. 이 가산 구조는 상세히 후술되고, 계산은 이진 모드에서 n 입력 동안 얼마나 많은 데이타가 하이인지를 출력하는 기능을 갖는 블럭(11)을 사용하여 실행된다. [이는 제1도의 S(pq)로 표시된다.] (p : 자리 가중, q : S의 자리 가중).
이제부터, 이 기능을 갖는 블럭(11)은 수 검출기(Number Detector)라고 하고, ND로 약해진다. 제1도에서, ND(11) 블럭은 박스로 표시된다. 각 박스의 수는각각 슬래쉬(/)의 왼쪽과 오른 쪽에서 입력들의 수(In) 및 출력들의 수(Out)를 나타낸다. 출력들의 수는 입력들의 수에 의해 결정되고 Out = [Log2(In)]으로 표시되고, 여기에서 [a]는 a 보다 큰 최소 정수 Z이다.
이 실시예에 따라서, 연산 속도는 제1 가산 단계를 병렬로 실행하기 위한 모든 ND들에서 가장 느린 ND 속도에 의해 결정된다. 여기에서는 연산 속도가 항상 동일하기 때문에, 하나의 ND의 연산 속도에 의해 결정된다. 이 실시예에서, 데이타 시퀀스는 8개의 비트들을 갖고 8개의 ND들이 사용된다. 7개의 8-비트 데이타 시퀀스의 가산 연산 때문에 최대 7개의 입력들이 ND에 입력된다.
일반적인 가산 연산에서 캐리가 생성하기 때문에, 연산 속도는 캐리 전달에 의해 저하된다. 그러나, 이 실시예는 캐리 없이 병렬로 가산을 실행함으로써 함께 데이타를 가산하는 특징을 가져서, 연산 속도를 증가시킬 수 있다. 이 실시예가 7개의 8-비트 데이타 시퀀스만을 가산하는 일례를 보여 주지만, 본 발명은 이 예로만 제한되지 않고 다수의 비트들의 다수의 다중 비트 데이타에 있을 수 있음을 알 수 있다.
그 다음, 요구된 가산 결과 Q는 이진 모드로 표시된 모든 8개의 가산 결과들을 가산하기 위한 제2가산 단계를 실행함으로써 고속으로 달성될 수 있다.
상술된 ND는 이하에 기술된다. 먼저, 5-입력(A, B, C, D 및 E) 다수결 논리 회로(majority logic circuit)의 회로도가 제2도에 도시되어 있다. 5-입력 다수결 논리 회로는 5개의 입력 중 3개 이상의 입력들이 하이일 때 하이가 출력되는 논리를 갖는다. 부울 대수 식에서, A(B+C)(D+E)+C(B+E)(A+D)+E(A+B)(C+D)로 표시되고, AND(21) 및 OR(22)로 이루어진 CMOS 회로로 쉽게 형성될 수 있다. 5개의 입력들이 여기에서 사용되더라도, 일반적으로 n개의 입력들로 확장될 수 있음이 명백하다.
제3A도를 참조하면, 다수의 5-입력 다수결 논리 회로(31)를 사용하여 m개의 비트들 중 n개의 비트들이 참임을 결정하기 위한 회로가 도시되어 있는데, 여기에서 출력 Fj(X1...X7)은 입력들의 수가 i와 같거나 보다 클 때 하이가 출력됨을 나타낸다.
제3B도는 제3A도의 회로에 대응하는 어레이의 출력(32)을 출력 데이타를 3-비트 이진수들의 이진 코드들로 변경시키기 위한 회로(33)에 연결시킴으로써 ND로 작용하는 회로를 도시한 것이다. 이 실시예에서, 출력 예는 7개의 비트들 중 5개의 비트들이 참임을 가정한 것이다. CMOS 회로를 포함하는 ND가 여기에서 ND 예로 설명되더라도, 본 발명은 이로 제한되지 않고 상술된 ND 기능을 갖는 회로가 사용될 수 있다.
[ 제2 실시예 ]
이 실시예에서, 제1 실시예에서의 가산 연산 속도를 증가시키기 위해 제2 가산 단계의 속도를 증가시키는 일례가 제공된다.
제4도를 참조하면, 이 실시예의 가산기의 구성이 도시되어 있다. 이 도면에 도시된 바와 같이, 공통 자리가 없는 가산 결과들은 제1 실시예에서 ND에 의해 구해진 3-비트 출력 데이타의 하나의 10-비트 데이타 시퀀스로 통합된다. 이는 제4도의 일례를 사용하여 이하에 기술될 것이다.
이 도면에서, 타원형 프레임에 의해 둘러싸인 자리의 3-비트 출력 데이타는 공통 자리를 갖지 않기 때문에 10-비트 데이타 시퀀스 A로 통합될 수 있다(3개의 가산 결과들이 통합될 때 값을 가지지 않는 자리가 있고, 이들은 0으로 설정된다.이 예에서, 제1 자리가 0으로 설정된다). 알고리즘에서 하나의 단계로서 처리되더라도 회로의 프로세싱으로서 배선만을 갖는 프로세싱에서는 어느 연산도 실행되지 않는 다는 것이 중요하다.
이 단계에서, 8개의 가산 결과들은 3개의 10-비트 데이타 시퀀스들로 변환될 수 있다. 지연 시간은 다른 단계들과 비교해 볼 때 무시될 수 있을 정도로 짧다. 마지막으로, 3개의 10-비트 데이타 시퀀스들을 가산함으로써, 최종 연산 결과가 구해질 수 있다. 3개의 10-비트 데이타 시퀀스들이 제4도의 일례에서 사용되기 때문에, 최종 가산 결과는 제5도에 도시된 2개의 단계들에서만 전 가산기들의 통과에 의해 구해질 수 있고 다수의 다중 비트 데이타는 고속으로 가산될 수 있다.
다음으로, 이 실시예는 최대 n-비트 데이타 시퀀스들이 m개의 피스들에 의해 가산되는 일반적인 연산을 위해 이하에 기술된다. n개의 ND들로부터 출력된 가산 결과는 최대 [Log2m] 비트들을 갖고, 따라서, 최대 [Log2m](n+[Log2m]) 비트 데이타 시퀀스들로 변환될 수 있다. 마지막으로, [Log2m](n+[Log2m]) 비트 데이타 시퀀스들을 가산함으로써, 최종 연산 결과가 구해질 수 있다. 전 가산기 통과 단계들의 수는 [Log2[Log2m]]로 표시되고, 여기에서, [a]는 a 보다 크거나 같은 최소 정수 Z이다. 상술된 표현으로부터, 전 가산기 통과 단계들의 수는 다중 비트 데이타 시퀀스들의 수가 보다 많더라도 적게 유지될 수 있다.
[ 제3 실시예 ]
이 실시예에서, 다중 비트 데이타의 승산이 설명될 것이다. 8 ×8 비트 승산기가 일례로 이하에 기술되었지만, 일반적으로 m ×n 비트 승산으로 확장될 수 있다.
X ×Y = Q라고 가정하자. 여기에서 X(X7X6X5X4X3X2X1X0)는 피승수이고 Y(Y7Y6Y5Y4Y3Y2Y1Y0)는 승수이다. X 및 Y 모두의 최대 값이 10진수에서 28-1이기 때문에, 식 Q < (28-1)2< 216-1이 구해지고 Q는 최대 16 비트로 표현된다. m ×n 비트의 경우, 식 Q < (2m-1)(2n-1) < 2m+n- 1이 구해지고 Q는 최대 m + n 비트로 표현된다.
제6도에 도시된 바와 같이, 부분 적 X ×Yj가 먼저 생성된다. 부분 적이 일반적인 CMOS 승산기와 같이 피승수 X의 각 비트 Xi와 승수 Yj의 AND에 의해 계산될 수 있더라도, 공통 게이트 전극들을 갖는 nMOS 트랜지스터가 이 실시예에서 제7도에 도시된 바와 같이 편의상 사용된다. 또한, nMOS 트랜지스터가 일례로서 사용되더라도, 다른 송신 게이트 MOS 트랜지스터들이 사용될 수 있음이 명백하다.
양호하게, 초기 상태에서 Xi는 Low(0)으로 Yj는 high(1)로 설정되어야만 하고모든 출력들은 0으로 설정되어야만 한다. 그 다음, Xi는 Yj를 Low 상태로 세팅한 후에 입력된다. 연산에서, High(1) 또는 Low(0)은 이 상태로 Yj에 입력된다. 다시 말하면, Yj가 high로 설정될 때, high 신호는 게이트 전극에 입력되고 nMOS 트랜지스터가 턴 온 되어 다음의 8-비트 데이타 시퀀스를 생성한다:
X×Yj= (X7Yj, X6Yj, X5Yj, X4Yj, X3Yj, X2Yj, X1Yj, X0Yj)
= X(X7, X6, X5, X4, X3, X2, X1, X0)
Yj가 Low(0)으로 설정될 때, Low 신호는 게이트 전극에 입력되어서, nMOS 트랜지스터가 턴 오프되고 8-비트 데이타 시퀀스 (0,0,0,0,0,0,0,0)가 초기 상태로 생성된다. 이것은 일반적인 AND 회로 보다 작은 크기로 X ×Y용 AND 회로를 형성할 수 있게 한다. 그러나, 일반적인 AND 회로가 사용될 수 있다.
그 다음, 제6도의 부분 적들의 각각의 자리의 데이타는 각 자리에 대한 ND에 의해 함께 가산된다. 가산이 이 단계에서 병렬로 실행되기 때문에, 고속 연산에 적합하다. (m+n-1)개의 ND들이 m×n-비트 승산기 회로에서 사용된다. ND들에 입력된 입력들의 최대 수는 Min(m,n)이다. 제6도에 도시된 바와 같이, 15개의 ND 유니트들이 8×8-비트 승산기의 일례에서 사용된다. 입력 최대 수는 8이다. (연산 X7Y0+X6Y1+X5Y2+X4Y3+X3Y4+X2Y5+X1X6+X0Y7이 실행된다.)
1-입력 1-출력 장치에서 배선에 의해 ND들이 대체될 수 있는 위치에서 ND들이 사용될 때 다수의 ND들이 적용된다. 대체 가능 ND들이 생략되면, (m+n-3)개의ND들이 사용된다. 또한, ND들이 2-입력 2-출력 HA(HA가 ND의 한 종류이더라도, ND와 구별됨)들로 대체될 수 있는 위치를 제외하고는 ND들이 3개 또는 그 이상의 입력들에 대해서만 사용되는 경우, (m+n-5)개의 ND들이 사용될 수 있다.
일반적으로, 3개 또는 그 이상의 입력들의 경우, 가산 연산은 복잡해지고 연산 속도는 이 상태에서 특히 생성할 수 있는 캐리들의 전달로 인해 저하된다. 이 실시예가 데이타를 함께 가산함으로써 캐리 없이 연산을 실행할 수 있기 때문에, 고속 연산이 실행될 수 있다. 제8도는 제6도의 도면의 블럭도이다. 편의상, 입력 유니트로서의 부분 적 형성 유니트는 생략된다. 부분 적 형성 유니트는 AND 회로로 대체될 수 있다. 이 도면에서, ND는 박스로 표시된다.
그 후 이진 모드로 표시된 (m+n-1)개의 가산 결과들 모두를 가산하기 위한 제2 가산 단계를 실행함으로써,요구된 승산 결과 Q는 고속으로 구해진다.
또한, 가산 연산 수를 감소시키기 위해, 다음 연산 방법이 제2 실시예와 동일한 방법으로 도입된다.
다시 말해서, (m+n-1)개의 ND들로부터 출력된 가산 결과는 최대[Log2(Min(m,n))]개의 비트들을 가져서, 자리의 일부만이 각각 최종 승산 결과 Q의 (m+n)개의 비트들에서 사용된다. 제6도의 일례에서, MD로부터의 출력은 최대 4개의 비트들을 갖고 최종 승산 결과는 16개의 비트들을 갖는다. 따라서, (m+n-1)개의 ND들로부터 출력된 가산 결과들 중에서 공통 자리가 없는 가산 결과들은 하나의 (m+n)-비트 데이타 시퀀스로 통합될 수 있다.
상술된 연산은 제6도의 일례를 사용하여 설명된다. 타원으로 둘러싸인 자리의 ND들로부터 출력된 가산 결과들은 공통 자리를 갖지 않기 때문에, 16-비트 데이타 시퀀스 B로 통합될 수 있다. [ND들로부터의 4개의 가산 결과들의 자리에 값이 없는 경우에 0이 설정된다. 이 일례에서, 0은 자리(2 내지 4, 8, 12, 15 및 16)에 설정된다]. 알고리즘의 단계로서 처리되더라도 회로의 프로세싱으로서 배선만을 갖는 프로세싱에서는 어느 연산도 실행되지 않는다는 것이 중요하다.
이 단계에서, (m+n-1)개의 가산 결과들은 [Log2(Min(m,n))](m+n)-비트 데이타 시퀀스들로 변환될 수 있다. 지연 시간은 다른 단계들에 비해 무시될 수 있을 정도로 짧다. 마지막으로, [Log2(Min(m,n))](m+n)-비트 데이타 시퀀스들을 가산함으로써, 최종 연산 결과가 구해질 수 있다.
4개의 16-비트 데이타 시퀀스들이 제6도 및 제8도의 일례에서 사용되기 때문에, 적의 최종 결과가 제9도에 도시된 바와 같이 2개의 단계들에서만 전 가산기들의 통과에 의해 구해질 수 있다. 일반적으로, 전 가산기 통과 단계들의 수는 제2 실시예와 동일한 심볼을 사용하여 [Log2[Log2(Min(m,n))]]로 표현될 수 있다.
제10도를 참조하면, 가로 좌표가 Min(m,n)이고 세로 좌표가 전 가산기 통과 단계들의 수인 그래프가 도시되어 있다. 이 그래프에 도시된 바와 같이, m 및 n이 증가되더라도, 전 가산기 통과 단계들의 수는 전 가산기 통과 단계들의 수가 2번 로그(log)되기 때문에 적게 유지될 수 있다. 다시 말해서, 비트들의 수가 증가되더라도 고속 연산은 유지된다.
상술된 연산 방법의 플로우챠트가 제11도에 도시되어 있다.
먼저, 단계(S111)에서, 부분 적 X ×Yj는 AND 회로 또는 스위치에 의해 생성된다. 다음으로, 단계(S112)에서, 생성된 부분 적 X ×Yj의 각각의 자리의 데이타는 ND들에 의해 병렬로 함께 가산된다. 따라서, 단계(S113)에서, 공통 자리를 갖지 않는 비트들은 단계(S112)의 가산 결과로부터 하나의 데이타 시퀀스로 통합된다. 그러나, 상술된 바와 같이, 이 단계에 대응하는 디바이스의 동작이 없고, 다음 단계에서 ND로부터의 출력과 전 가산기들로의 입력이 서로 연결된다. 마지막으로, 단계(S113)에서 통합된 데이타는 단계(S114)에서 전 가산기들에 의해 가산된다.
다음으로, 제12도를 참조하여 이 실시예에서 사용된 ND들과 같이 상술된 연산 방법을 실행하기 위한 실제 승산 회로들이 설명된다. 피승수 입력 유니트(71)는 피승수 X를 입력하는데 사용된다. 승수 입력 유니트(72)는 승수 Y를 입력하는데 사용된다. 부분 적 생성기 유니트(73)는 제7도에 도시된 AND 회로 또는 스위치로서 부분 적들을 생성한다, 상술된 바와 같이, 부분 적들은 다른 구성들을 갖는 임의의 회로들에 의해 생성될 수 있다. ND(74)는 다수의 다중 비트 데이타(이 실시예에서의 각각의 부분 적들)의 동일한 자리에서 데이타를 병렬로 함께 가산하는데 사용된다.
제13도를 참조하면, 7-입력 ND가 도시되어 있다. 이 실시예에서 사용된 ND들은 다수결 논리 회로 블럭(131-A, 131-B, 131-C) 및 인버터(132)를 갖는데, 이 구성은 제1 실시예의 구성과 상이하다. 터미날(134 및 135)로 입력된 신호는 입력 터미날(133)에 입력된 신호와 동일하다. 터미날들(136, 137 및 138)은 전 단계에서 다수결 논리 회로 블럭으로부터 출력 신호들을 입력하기 위한 목적지로서 사용된다. 제13도에서, C가 일반적인 입력 터미날에 연결된 용량을 나타낸다는 가정 하에서 참조 번호(2C 및 4C)는 입력 터미날들(136, 137 및 138)에 대응해서 연결된 캐패시터 값들을 나타낸다. 이 도면에서, 신호들은 다수결 논리 회로 블럭(131-A, 131-B, 131-C)에 입력된다.
예를 들어, 신호가 7-입력 다수결 논리 회로 블럭(131-A)에 입력될 때, 다수의 HIGH LEVEL 데이타가 있는 경우 또는 7개의 입력들 중 4개 이상의 입력들이 HIGH LEVEL인 경우 블럭(131-A)으로부터 HIGH LEVEL이 출력된다. 예를 들면, 동일한 방법으로, 6개 이상의 입력들이 11-입력 다수결 논리 회로 블럭에서 HIGH LEVEL이면, 그리고 13-입력 다수결 논리 회로 블럭에서 7개 이상의 입력들이 HIGH LEVEL이면, HIGH LEVEL이 출력된다. 테이블 1에서, S3은 각 HIGH LEVEL 입력 계수를 위한 7-입력 다수결 논리 회로 블럭의 출력 값을 나타낸다.
따라서, 제13도에 도시된 바와 같이, 7-입력 다수결 논리 회로 블럭(131-A)의 출력은 인버터에 의해 반전되고 다수결 논리 회로 블럭(131-B)의 가중된 입력 터미날(136)에 입력된다. 다수결 논리 회로 블럭(131-B)의 회로 구성은 제14도에 도시되어 있다. 이 도면에서, 캐패시터(212)는 다른 입력 터미날 경로에 접속된 캐패시터(202)의 캐패시터 값의 약 4배이다. C가 입력 터미날 경로에 접속된 캐패시터 값이라고 가정하면, 회로는 11개의 C들이 공통으로 접속되어 있는 구성을 갖는 11-입력 다수결 논리 회로이고 가중된 입력 터미날로부터의 신호는 11개의 C들 중4개의 C들로 입력되고 블럭(131-A)에 입력된 것과 동일한 신호는 다른 7개의 터미날들에 입력된다.
예를 들어, 7개의 입력들 중 4개 이상의 입력들이 HIGH LEVEL이면, LOW LEVEL은 상술된 바와 같이 가중된 입력 터미날에 입력된다. 가중 입력 터미날이 아닌 입력 터미날들에 입력된 신호들에서 7개의 입력들 중 6개 이상의 입력들이 HIGH LEVEL이면, 11-입력 다수결 논리 회로는 전체 중에서 다수결로 결정하고 HIGH LEVEL을 출력한다. 7개의 입력들 중 4개 이상 그리고 5개 이하의 입력들이 HIGH LEVEL이면, 다수로 결정되지 않고 LOW LEVEL이 출력된다. 7개의 입력들 중에서 3개 이하의 입력들이 HIGH LEVEL이면, HIGH LEVEL이 가중 입력 터미날에 입력된다. 7개의 입력들 중에서 2개 이상 그리고 3개 이하의 입력들이 HIGH LEVEL이면, 4 + 2 또는 4 + 3, 즉 6 또는 그 이상의 입력들이 있어서, 다수로 결정되어 HIGH LEVEL이 출력된다. 1개 이상의 입력이 HIGH LEVEL이면, 4 + 0 또는 4 + 1, 즉, 5개 이하의 입력들이 있어서 LOW LEVEL이 출력된다.
테이블 1에서, S2는 각각의 HIGH LEVEL 입력 계수를 위한 다수결 논리 회로 블럭(131-B)의 출력 값을 나타낸다. 다수결 논리 회로 블럭(131-C)에 있어서, 테이를 1의 S1로 도시된 출력들은 다수결 논리 회로들(131-A 및 131-B)의 출력에 대한 반전 신호를 연산 전에 4폴드 캐패시터 값 및 2폴드 캐패시터 값을 갖는 2개의 가중 터미날들에 입력시킴으로써 구해질 수 있다.
이 회로 구성에 따라서, HIGH LEVEL 입력들의 수는 3개의 자리에서 2진수로 변환되어 테이블1에 도시된 바와 같이 2개 이상의 입력들로부터 출력될 수 있다.
다수결 논리 회로 블럭의 일반적인 회로도가 제15도에 도시되어 있다. 이 다수결 논리 회로 블럭은 리셋 스위치(201), 캐패시터(202), 신호 전송 스위치(203), 감지 증폭기(205), 감지 증폭기의 인버터(206), 감지 증폭기의 제2 인버터(204), 인버터(206)를 리셋하기 위한 제2 리셋 스위치(207), 리셋 전원(208), 제2 리셋 전원(210), 출력 터미날(211), 및 공통으로 접속된 캐패시터(202) 단부의 기생 캐패시터(209)를 포함한다. 이는 제15도에 도시되어 있는데, 본 발명은 이 구성으로 제한되지 않는다.
제16도는 제15도의 회로의 연산 타이밍도이다. 이 도면을 참조하여, 이 연산이 이하에 기술된다. 먼저, 캐패시터(202)의 단부의 터미날은 리셋 펄스 ØRES에 의해 리셋된다. 예를 들어, 리셋 전압의 경우, 공급 전압이 직렬로 5V이면, 이 전압의 절반인 2.5V가 사용된다. 그러나, 리셋 전압은 이에 제한되지 않고, 다른 임의의 전압들이 사용될 수 있다. 거의 동시에, 감지 증폭기의 인버터(206)의 입력 터미날은 리셋 스위치(207)를 도전시킴으로써 리셋된다. 이 때에, 값은 인버터의 출력을 반전하기 위해 논리 반전 전압에 가까운 리셋 전압으로서 선택된다. 리셋 펄스 ØRES가 오프로 설정되면, 캐패시터(202)의 양 터미날들은 각각의 리셋 전위들로 유지된다.
다음으로, 전송 스위치(203)가 전송 펄스 ØT로 인해 도전 상태가 될 때, 신호는 캐패시터(202)의 터미날에 전송되고 이 캐패시터의 터미날의 전위는 예를 들어 2.5V 리셋 전압으로부터 로우 레벨과 등가인 0V 또는 하이 레벨과 등가인 5V로변경된다. C가 캐패시터(202)의 용량을 나타낸다고 가정하면, C0은 기생 캐패시터의 캐패시터 값을 나타내고, 캐패시터(202)의 N개의 유니트들은 병렬로 접속되고, 캐패시터(202)의 단부에 공통으로 접속된 터미날들은 용량 분할(capacity division)로 인해 입력으로 인버터의 논리 반전 전압에 가까운 값으로부터 ±[2.5C / (C0+ CN)] ×│V │로 변경된다.
인버터(206)의 입력 터미날 전압이 논리 반전 전압으로부터 변경될 때, 인버터(206)의 출력 터미날 전압은 이에 따라 반전된다. N개의 입력들에 대한 각각의 신호들이 입력될 때, 용량 분할 출력들의 N개의 합들은 인버터(206)의 입력 터미날에 입력된다. 다수의 HIGH LEVEL 신호들이 N개의 입력들로부터 입력되면, 인버터(206)의 입력 터미날은 논리 반전 전압을 보다 높은 전위로 시프트하고 HIGH LEVEL이 감지 증폭기의 출력 터미날(211)로 출력된다. 다수의 LOW LEVEL 신호들이 입력되면, LOW LEVEL이 출력된다. 상술된 구성을 사용하여, 제15도의 회로는 2개 이상의 입력들의 다수로 논리 값을 출력하기 위해 다수결 논리 회로로서 작용한다.
제13도에서는 비록 일례로서 7-입력 ND를 도시하였지만, 이러한 구성에만 국한되는 것이 아니고 용이하게 다수 입력 구성으로 확장시킬 수 있음을 알 수 있다. 또한, 연산 속도를 더 증가시키기 위한 구성으로서 다수결 논리 회로 사이에 파이프 라인 프로세싱을 위한 래치 회로들을 자유로이 접속시킬 수 있다.
ND에서 필요한 다수결 논리 회로 블럭의 수는 [Log2n]으로 표현되며, 여기서 n은 ND로의 입력들의 수이다. ND의 입력 수로서는, m ×n - 비트 승산기의 경우 1내지 Min(m, n)의 값이 적용되며, 그 연산 시간은 입력 계수가 최대 입력수인 Min(m, n)인 ND에서 가장 길게 된다. 그것은 다수결 논리 회로단계들의 수가 입력 수가 n인 경우 [Log2n]에 따라 증가되기 때문이다. 그러나, 논리 회로 단계들의 수는 로그 함수에 따라 증가하므로 비트 수가 증가될 때 단계들의 수가 상당히 증가되지 않는다는 것은 명백하다.
연산은 병렬로 행해지므로, 입력 Min(m, n)의 최대수를 갖는 ND의 연산 속도로 다수의 ND(74)에서 종료된다. 연산이 보다 일찍 종료되는 ND의 경우, 래치 회로(78)를 접속시켜 타이밍을 조절하는 것이 양호하지만, 이것에만 국한되는 것은 아니다.
이와 같이 ND를 구성하면 병렬 연산으로 인해 연산 속도가 보다 빠르게 되며 필요한 소자들이 적게 되어 전력 소모가 감소되어서, 상술된 실시예에서의 연산 방법 특성들을 상당히 개선시킬 수 있다.
다수의 ND로부터 출력된 데이타를 하나의 알고리즘으로 하나의 데이타 시퀀스로 통합시키는 단계가 존재하지만, 상술된 회로에서와 같은 프로세싱은 실행되지 않으므로 제12도의 단계에 대응하는 회로들이 생략된다. 전 가산기(75, 76 및 77)는 제6도에서 도시된 8 ×8 비트 승산의 일례로 16 또는 그 이하의 비트 가산기이다. 제12도에서는, 8 ×8 비트 승산기를 사용하므로, 3개의 가산기가 필요하여 이들은 2단으로 배치된다. 일반적인 캐리 록 어헤드(CLA)형의 전 가산기를 가산기로서 사용하였지만, 본 발명은 이것에만 국한되는 것은 아님을 알 수 있다.
또한, 래치 회로(79)가 가산기 사이에 접속되어 고속 연산을 달성하기 위한 소위 파이프라인 방법으로 제2단의 가산기와 함께 연산하면서 제1 가산기와 함께 연산을 행하지만, 본 발명은 이것에만 한정되지는 않는다. 연산 결과 출력 유니트(80)는 8 ×8 비트 승산의 일례로 16비트의 연산 결과를 출력시킨다.
상술된 승산기를 구성할 경우, 소자 수의 감소, 저전력 소모 및 병렬 연산으로 인해 고속 승산기를 구성할 수 있다.
[제4 실시예]
제1 내지 제3 실시예의 병렬 배치 가산용 ND 부에 대한 다른 구성에 대해 후술하기로 한다.
제17도는 병렬 연산 회로 블럭(401) 및 래치 회로(12)를 포함하고 이 실시예에서 사용되는 ND의 일반적인 도면이다. 제18도는 병렬 연산 회로블럭(401)의 회로도이다. 제18도에서 터미날(501, 502 및 503)은 각각 제1 가중 입력 터미날, 제2 가중 입력 터미날 및 제3 가중 입력 터미날이다. 각각의 터미날은 대부분 다른 입력 터미날 경로에 접속된 1-폴드, 2-폴드 또는 3-폴드 캐패시터 값을 갖는 캐패시터를 갖는다. 제19도에서는 이 실시예의 연산 타이밍도가 도시되어 있다. 병렬 연산 회로 블럭(401)은 펄스 ØRES 또는 ØT에 의해 동작된다. 래치 회로(12)는 펄스 ØPH에 의해 동작된다.
우선, 제18도를 참조하면서 기본 동작에 대해서 설명하기로 한다. 입력 신호가 래치 회로(12-A)에서 래치된다. 이때, 저레벨에 해당하는 OV가 가중 터미날(501 및 502)에 인가되며 고레벨에 해당하는 5V가 펄스 ØSET와 함께 가중 터미날(503)에 인가된다. 다음에 캐패시터(202) 양단간의 전압을 리셋 펄스 ØRES에 의해 리셋 전압으로 각각 리셋시킨다.
다음에, 전송 스위치(203)가 전송 펄스 ØT에 의해 도전 상태가 되면, 캐패시터(202)의 종단에 신호가 전달되어 그 캐패시터의 종단의 전위는, 예를 들어, 저 레벨 또는 고 레벨로 변경된다. 공통 접속된 캐패시터(202)의 종단 전압은 입력 용량분할에 따라서 변경된다. 인버터(206)의 입력 터미날 전압이 논리 반전 전압으로부터 변경될 경우, 인버터(206)의 출력 터미날 전압은 이에 응답하여 반전된다. 각 신호가 N 입력에 응답하여 입력되면, 용량 분할 출력의 N 합이 인버터(206)의 입력 터미날에 입력된다.
이 실시예에 있어서는, 반대 극성의 신호들이 3-폴드 캐패시터 값을 갖는 가중 터미날(503)와 1-폴드 및 2-폴드 캐패시터값을 갖는 가중 터미날(501 및 502)에 입력되므로, 공통 접속된 캐패시터(2)의 종단에서의 전압 변경량은 서로 옵셋(offset)된다. 가중 입력 터미날이 아닌 각각의 입력 터미날에 접속된 캐패시터(2)는 거의 동일한 캐패시터 값을 갖는다. 따라서, N 입력 중에서 고레벨 신호가 대다수 입력되면, 인버터(206)의 입력 터미날은 논리 반전 전압을 보다 높은 전위로 시프트시켜 감지 증폭기의 출력 터미날(211)에 HIGH LEVEL이 출력된다. LOW LEVEL 신호들이 대다수 입력되면, LOW LEVEL이 출력된다.
상기한 구성을 이용함으로써, 제18도의 회로는 2 또는 그 이상의 입력이 대다수인 논리값을 출력시키는 다수결 논리 회로로서 동작할 수 있다. 제17도는 일례로서 7-입력 ND를 도시하고 있다.
제17도에서, 다수결 논리 회로 블럭(401)에 신호가 입력된다. C가 입력 터미날 경로에 접속하기 위한 캐패시터 값이라고 가정하면, 다수결 논리 회로 블럭(401)은 고레벨 신호가 가중 입력터미날로부터 공통 접속된 13개 C중 3개 C에 입력되고, 저레벨 신호가 가중 입력터미날로부터 나머지 3개 C에 입력되고, 참조번호(402)로부터의 신호가 나머지 7개 터미날로 입력되어지는 구성을 갖는 13-입력 다수결 논리 회로로서 고려될 수 있다.
따라서, 입력 값이 입력될 경우, 고레벨 신호의 수가 대다수이면, 바꾸어 말해 7개 입력중 4개 또는 그 이상이 HIGH LEVEL 입력이면, 다수결 논리 회로 블럭으로부터 HIGH LEVEL이 출력된다. 테이블 1에서, S3은 각각의 HIGH LEVEL 입력계수에 대한 13-입력 다수결 논리 회로 블럭의 출력값을 표시한 것이다. 따라서, 래치 회로(12)에는 펄스 ØLAT1 및 ØLAT2와 함께 출력 신호가 래치된다. 예를 들어, 7개 입력중 4개 또는 그 이상 입력이 HIGH LEVEL이면, HIGH LEVEL이 가중 입력터미날(501)에 입력되며, LOW LEVEL이 가중 입력터미날(502 및 503)에 입력된다.
7개 입력중 6개 또는 그 이상 입력이 가중 입력터미날이 아닌 입력터미날에 입력된 HIGH LEVEL 신호이면, 13-입력 다수결 논리 회로는 이것을 전부 다수결로서 결정하고 HIGH LEVEL을 출력한다. 7개 입력중 4 또는 그 이상과 5개 또는 그 이하의 입력이 HIGH LEVEL이면, 이것을 다수결로서 결정하지 않고 LOW LEVEL 을 출력한다. 동일하게, 테이블 1의 출력은 출력 신호의 극성 또는 스위치(403)를 스위칭하면서 가중 터미날에 입력되는 신호들을 변경시킴으로써 얻어질 수 있다.
이와 같은 회로 구성에 따르면, 고레벨 입력 신호수는 저전력 소모의 초소형 회로에서 테이블 1에서 도시된 바와같이 2 또는 그 이상의 입력중에서 출력될 3자리의 2진수로 변환될 수 있다. 다른 기술은 제3 실시예의 것과 동일하지만, 이러한 구성에 의해서 소자수를 더욱 감소시킬 수 있으며, 소형 회로의 전력 소모를 감소시킬 수 있으며 병렬 연산으로 인한 고속 반도체 소자를 구성할 수 있다.
[제5 실시예]
제1 내지 제4 실시예의 병렬 배치 가산용 ND 부에 대한 다른 구성에 대해 기술하고자 한다.
이 실시예는 제3 실시예의 15개 ND 중 2개 또는 그 이상의 ND를 통합시킨 연산 방법이다.
제20도에서는 2 ×2 승산기에 적용시킨 2 ×2 다수결 논리 회로에 근거한 예를 도시하고 있다. 즉, 이 회로는 제3 실시예를 나타낸 제13도의 제1단의 다수결 논리 회로이다. 제1 자리의 데이타(20의 자리에서 x0y0)가 단위 캐패시터 C에 입력된다. 제2 자리에서의 두 데이타(21의 자리에서 x1y0및 x0y1)는 2-폴드 용량 2C를 각각 갖는 터미날로 입력되므로, 1개 입력은 2로 계수된다. 또한 제3 자리의 데이타(22의 자리에서 x1y1)는 22로 가중되어 1개 입력은 4로 계수된다.
다른 설명은 제1 내지 제4 실시예의 것들과 동일하며 7개 입력까지 각 ND에서 4개 입력을 사용하여 2진 모드로 출력된다. 이러한 가중 방식을 사용함으로써,병렬 배치가산 기능을 보다 효율적으로 사용할 수 있다.
예를 들어, 제3 실시예의 8 ×8 비트 승산기의 경우, 가중이 0, 1, 2 및 3인 자리의 데이타를 가산하는 ND는 제21도에서 도시된 ND(91)와 통합되며, 가중이 (4, 5, 6), (7, 8, 9), (10, 11, 12, 13, 14)인 자리의 영역이 각 영역[제21도의 ND(92) 내지 ND(94)]에 통합된다.
제21도의 ND에 대해서는 입력수와 출력수를 표시하였지만, ND가 56개 입력까지 계수할 수 있는 한 어떠한 ND라도 사용할 수 있다. 각각의 ND는 6-비트 출력을 생성한다. A, B, C 및 D가 올림차순의 자리를 갖는 6-비트 데이타 시퀀스라고 가정하면, 제3 실시예의 제11도의 플로우챠트에서 단계(S113)인 새로운 데이타 시퀀스를 형성하는 단계에서 A와 C는 데이타 시퀀스 P로 통합될 수 있으며 B 및 D는 데이타 시퀀스 Q로 통합될 수 있다.
따라서, 단지 가산 연산 P + Q 만이 실행될 수 있다. 바꾸어 말하면, 이 실시예에서는 8 ×8 비트 승산이 2단계로 실행되는데, 한 단계에서는 ND에서 병렬 배치 가산이 실행되며, 다른 한 단계에서는 16-비트 가산이 한번만 행해진다.
다른 설명은 제3 및 제4실시예의 것들과 동일하지만, 이와 같은 승산회로의 구성에 의해서 소자수를 더 감소시킬 수 있으며, 소형 회로에서의 전력소모를 감소시킬 수 있으며, 병렬 연산과 가산단의 감소로 인해 승산기의 속도를 빠르게 할 수있다.
비록 이 실시예의 일반적인 가중 예에서는 인접한 자리들을 통합시켰지만,본 발명은 이러한 방법에만 국한되지 않고 불연속 가중(예를 들어, 20자리의 데이타 및 22자리의 데이타가 통합되어 입력되는 경우)이나 또는 서로 다른 ND에 상이한 가중을 입력시키기 위해 한 자리의 데이타를 분할(예를 들어, 28자리의 데이타를 2 종류로 분할하여 서로 다른 ND에 입력)하는 것과 같은 효율적인 방법을 융통성 있게 사용할 수 있다.
[제6 실시예]
부분 적을 병렬로 가산하는 한 단에 여러 ND들이 존재하며 제3 내지 제5 실시예의 후단에 전 가산기가 존재하지만 이들 ND들 다음에 다른 ND들이 접속될 수 있다. 제22도를 참조해보면, 32 ×32 비트 승산기의 일례가 도시되어 있다. 이 도면은 32-입력 ND에 대해 도시하고 있다. 32-입력 ND의 경우, 7-비트 출력이 구성된다. 보다 적은 비트로서는, 16 내지 31 입력 ND로 6-비트 출력이 구성되며, 이들 출력들은 ND로부터의 연산 결과인 부분 적으로서 고려될 수 있다.
따라서, 3-비트 출력들은 ND를 다시 사용하여 구성할 수 있다. 이러한 상태에서, 데이타는 데이타 시퀀스로서 3개의 64-비트 데이타 A, B 및 C로 분류될 수 있으며, 연산은 단지 2개의 전 가산기 단으로만 행하여질 수 있다. 이러한 방식은 특히 대다수의 비트 연산에 유효하지만, 가산기 및 ND의 성능에 따라 정해진다. 또한, 이러한 방법을 제5 실시예에서 기술된 가중 ND와 결합하여 사용하면 문제가 없다.
[제7 실시예]
이 실시예의 승산기를 제23도에서 도시하고 있다. 이 실시예에 있어서는, 먼저 ND로부터의 출력인 (S73, S72, S71, S70) 및 (S102, S101, S100)에 대해 가산이 행해진다. 실제로는 단순한 3-비트 가산기에 의해 S73은 S102, S101 및 S100에 바로 가산된다.
이 단계의 결과로서, 이 실시예에서는 3개의 16-비트 데이타 시퀀스 A, B 및 C가 형성되지만, 제3 실시예에서는 4개의 16-비트 데이타 시퀀스가 형성된다. 따라서, 제3 실시예에 비해 소자가 더 감소된다.
[제8 실시예]
제8 실시예에서는 3개의 데이타를 승산시키는 방법에 대해 기술하고 있다. 여기서는 단순 예로서 2-비트 데이타를 사용하여 설명하였지만, 이 방법은 다중 비트 데이타에서 각 데이타의 비트수가 동일하지 않을 경우에도 동일한 방법으로 달성될 수 있으며, 데이타 수는 3개에만 한정되지 않고 임의 다수 데이타로 확장될 수 있다.
승산 값은 A(a1, a0), B(b1, b0) 및 C(c1, c0)인 것으로 추정된다. 계산 (A ×B ×C)의 경우, 제24도에서 도시된 바와 같이 부분 적 ∑aibjck이 생성되며 그 합을 계산함으로써 승간 결과 Q를 얻을 수 있다. 부분 적 ∑aibjck를 구하기 위해, 상기 실시예에서와 동일한 방법으로 각각 AND를 취한다. 3개 또는 그 이상의 데이타의 경우라도 부분 적의 연산속도는 고속이며 부분 적을 병렬처리로 행할 수 있다.
따라서, 이러한 부분 적에서 동일자리의 데이타에 대한 배치 가산이 행해진다. 제24도의 예에서는 동일 자리의 데이타를 함께 가산하였지만, 상기 실시예에서 기술된 바와 같이 가중 또는 다른 단계들을 사용할 수도 있다. 제24도에서, 타원형의 프레임으로 둘러싸인 자리에 대한 배치 가산 출력 결과들은 공통자리가 없기 때문에 하나의 데이타 시퀀스로 통합되어 3개의 7-비트 데이타 시퀀스가 생성되어지며 이들이 함께 가산되어져 3개의 3-비트 데이타의 승산 결과 Q가 얻어진다.
보다 상세히 기술하자면, 하위 2자리(20및 21자리)의 데이타는 7-비트 데이타 시퀀스에서 가산될 필요가 없으며 S00 및 S10은 각각 이들의 출력결과이다. 그러므로, 제2 단계인 가산 단계에서 3개의 5-비트 데이타 시퀀스가 가산되어져 연산 속도가 보다 빠르게 된다.
이들 설명으로부터 명백한 바와 같이, 3개 또는 그 이상의 데이타 시퀀스의 승산의 경우에도 본 발명의 연산방법이 효과적이므로, 전력 소모가 적은 적은수의 소자로 고속 승산을 행할 수 있다.
[제9 실시예]
이 실시예에 있어서는 63개의 7-비트 데이타 시퀀스를 가산하는 일례를 들어 적어도 하나의 음수값을 포함하는 다수의 다중 비트 데이타에 대한 가산방법에 대해 기술하고 있다.
음수값은 2의 보수로 표현된다. 바꾸어 말하면, 7비트중 최상위 비트 0은 부호를 나타내는데, 이것이 0로 설정되면 양수값이며, 1로 설정되면 음수값이다. 데이타 시퀀스 X=(X6X5X4X3X2X1X0)는 다음과 같이 표현된다. 즉
제25도는 이 실시예를 도시한 것이다. 이 실시예에서는, 우선, 7개의 8-비트 데이타 시퀀스의 각 자리의 데이타에 대한 배치 가산을 행한다. 제1 가산은 상기 실시예에서와 동일한 방법으로 ND를 사용하여 행한다. 데이타 시퀀스가 이 실시예에서는 플래그를 포함하여 7비트이므로 7개의 ND가 사용된다.
이러한 가산 단계에서의 처리는 병렬로 행해지므로, 단일 ND의 속도에 의해 연산속도가 정해진다. 모든 ND의 연산 속도가 동일하므로, 단일 ND의 연산속도에 의해 정해진다. 또한, 이 실시예에서는 63개의 7-비트 데이타 시퀀스가 가산되므로, ND의 최대 입력수는 63이다.
일반적인 가산에서는 캐리가 생성하므로, 캐리의 전달로 인해 연산속도가 감소된다. 그러나, 이 실시예에서는, 캐리 없이 플래그를 포함하여 배치 가산을 병렬로 행하므로, 가산단을 줄일 수 있어서 고속 연산을 달성할 수 있다. 이 실시예의 실례에서는 단지 63개의 7-비트 데이타 시퀀스만을 도시하였지만 본 발명은 이것에만 한정되지 않고 적어도 하나의 음수갑을 포함하는 각종 비트수의 다수의 다중 비트 데이타가 있을 수 있다.
따라서, 2진 모드로 표시된 8개 가산 결과 모두를 가산하는 제2 가산을 행함으로써 고속으로 희망의 가산결과 Q가 얻어진다.
다음으로, +부호 또는 -부호를 나타내는 플래그 비트에 대해 후술하기로 한다.
플래그 비트가 1로 설정되면, 이것은 2의 보수 표시법으로 (-1) ·26을 나타낸다. 따라서, 1의 수가 63개 입력중 n으로 표시되면, -n ·26이 그 값을 나타낸다. n이 63과 동일할때 최소값이 얻어지며 식 -63 ·26= -(26-1) ·26은 절대값으로 212를 초과하지 않는 상태에서도 유효하다. (SF5, SF4, SF3, SF2, SF1, SF0)가 n의 2진 표시인 것으로 추정되며 (BSF6, BSF5, ..., BSF0)가 이와 같은 음수값을 2의 보수로서 사용하고 플래그로서 제13 비트를 사용하여 반전되어진 것으로 추정되는 경우, 다음식이 얻어진다. 즉
따라서, F는 다음식이 유효하므로 가산되어진다.
A - │F│= A + F(│F│ + F = 0, 제13 비트는 1+1과 제14 비트가 없으므로 0으로 설정된다)
제25도에서, 피연산자의 플래그 비트는 ND에 의해 2진 표시 SF로 변환되고 BSF는 그들의 반전을 취함으로써 생성된다. 또한, F는 음수값을 나타내는 플래그 데이타의 2의 보수 표시인 1을 제7 비트와 제13 비트에 가산시킴으로써 생성될 수 있다.
이 다음에, 2진 모드로 표시된 7개 가산 결과 모두를 가산하는 제2가산 단계를 행하여 고속으로 희망하는 가산 결과 Q를 얻을 수 있다.
상술된 바와 같이, 플래그 비트는 숫자를 나타내는 비트에서와 같은 방식으로 처리될 수 있으며, 적어도 하나의 음수값을 포함하는 63개의 7-비트 데이타는 ND에 통과되면서 7개의 6-비트 데이타로 변환된다. 플래그의 2의 보수 변환을 위한 제7 비트 및 제13 비트의 값 1을 예를 들어 제25도의 (b)로 도시된 바와 같은 임의 연산 없이도 각각을 Son 또는 BSF 데이타 시퀀스에 가산시킴으로써 통합시킬 수 있다.
이러한 방법에서는 플래그로서 제13비트를 사용할 수 있다. 즉
Xij가 i번째 데이타 시퀀스의 (j+i)번째 비트를 표시한다고 가정하면, 상기 계산은 다음과 같이 수치적으로 표현될 수 있다.
따라서, out가 0이거나 그 이상이면, 상기식으로부터 다음식이 얻어진다.
바꾸어 말하면, 제13 비트에 1이 가산되어 0으로 설정된다.
out가 0보다 작으면
따라서, 제13 비트는 음수 값인 1로 남아있는다.
일반적인 설명의 경우 제 m비트가 플래그 비트이며 플래그 비트는 플래그 비트가 아닌 다른 수치 비트와 동일한 비트로서 처리되어 연산을 보다 쉽게 할 수 있으므로 m + [log2n] 번째 비트를 1로 설정시키고 2의 보수 표시를 위해 제 m 비트에 1을 가산시킴으로써 ND의 사용중에 n개 피연산자에 대한 가산 연산을 행할 수 있다.
[제10 실시예]
이 실시예는 제9 실시예의 가산 연산 속도를 고속으로 달성하기 위해 제2 가산 단계의 연산 속도를 증가시킨 일례를 들어 후술하기로 한다.
제26도는 이 실시예의 가산기의 구성을 도시한다. 여기서는 ND로부터 얻어진 3-비트 출력 데이타중 공통자리를 갖지 않는 가산 결과가 하나의 11-비트 데이타 시퀀스에 통합되어지는, 플래그를 포함하는 7개의 8-비트 데이타를 가산하는 일례가 도시되어 있다. 이러한 연산은 제26도의 예를 사용하여 설명하기로 한다. 플래그 비트에 있어서 이들 비트는 제9 실시예에서 기술된 2의 보수로서 고려되며 ND로부터의 출력은 인버터를 통해 전달된다. 또한 3-비트 출력 데이타와 0001로써 표현되는 데이타는 1을 가산시키는 전 가산기에서 가산되지만, 본 발명은 이것에만 한정되지 않는다. 또한, (a)로 표시된 MSB의 1은 제9 실시예에서와 같은 방법으로 존재한다.
제26도에서, 타원형 프레임으로 둘러싸인 자리의 3-비트 또는 4-비트 출력 데이타는 이들이 공통자리를 갖고 있지 않으므로 11-비트 데이타 시퀀스 A로 통합될 수 있다(3개의 가산 결과가 통합될때의 값을 갖지 않는 자리들이 있으며, 이들은 0로 설정된다. 이 예에서는, 제1자리는 0로 설정된다). 이러한 프로세싱에서는 그 알고리즘의 한 단계로서 취급되더라도 이 회로에서의 프로세싱으로서 단지 배선만을 갖는 프로세싱에서는 연산이 행해지지 않는것이 중요하다.
이 단계에서, 8개의 가산 결과를 3개의 11-비트 데이타 시퀀스로 변환시킬 수 있다. 지연 시간은 다른 단계와 비교하여 무시될 수 있을 정도로 짧다. 마지막으로 3개의 11-비트 데이타 시퀀스를 가산함으로써 최종 연산 결과를 얻을 수 있다. 제26도의 예에서 3개의 11-비트 데이타 시퀀스를 사용하였으므로, 최종 가산 결과는 제5도에서 도시된 단지 2개단의 전 가산기를 통과시킴으로써 얻어지며 다수의 다중 비트 데이타를 고속 연산으로 가산시킬 수 있다.
다음으로, 이 실시예의 최대 n-비트 데이타 시퀀스가 m개로 가산되는 일반적인 연산에 대해 후술하기로 한다. n개의 ND로부터 출력된 가산 결과는 [Log2m] 비트를 가지므로, 최대 [Log2m](n + [Log2m]-1)비트 데이타 시퀀스로 변환될 수 있다. 마지막으로 [Log2m](n + [Log2m]-1) 비트 데이타 시퀀스를 가산함으로써, 최종 연산 결과를 얻을 수 있다. 전 가산기 통과단의 수는 [log2[log2m]] 표현될 수 있다. 상기 식으로부터, 전 가산기 통과단의 수는 다중 비트 데이타 시퀀스의 수가 많아지더라도 적게 유지될 수 있다.
플래그 비트는 소형 전 가산기를 통해 전달된다. 이들이 단일 단으로 배열되어 있으면, [log2[log2m]+1이 얻어진다. 전 가산기가 그 장소에 접속되어 있지 않지만 플래그 비트가 ℓ로 표시되는 경우, 단지 ℓ비트가 1인 데이타 시퀀스가 최종 가산되며 전 가산기 통과단의 수가 [log2[log2m]+1로 표현될 수 있다라는 가정하에 [log2m]+1 데이타 시퀀스가 존재한다. 어쨋든, 비트수가 증가되더라도, 전 가산기 통과단의 수는 적게 유지될 수 있다.
[제11 실시예]
이 실시예에서는 적어도 하나의 음수값을 포함하는 다수의 다중 비트 데이타에 대한 가산 방법을 63개의 7-비트 데이타 시퀀스를 가산하는 일례를 들어 후술하고자 한다.
음수값은 이 실시에에서는 1의 보수로 표현된다. 1의 보수는 수치 비트에 대해 단지 반전을 행하기만하면 되므로 사전처리를 용이하게 간단히 행할 수 있다는 장점을 지닌다.
제27도를 참조해보면, 이 실시예가 도시되어 있다. 이 도면에서, 63개의 7-비트 데이타 시퀀스를 가산하기 위해 각 자리의 데이타가 모두 가산된다. 이러한 가산은 63-입력 6-출력 ND에 의해 행해진다.
이 실시예에서 가산 단계에서의 처리는 병렬로 행해지므로, 연산 속도는 각 ND의 연산속도에 의해 정해진다. 이 실시예의 경우, 7-비트 데이타 시퀀스 때문에7개의 ND를 사용하였다. 또한, 63개의 7-비트 데이타 시퀀스가 이러한 연산시에 가산되므로, ND의 입력수는 63이다.
일반적인 가산에서는 캐리가 생성되므로, 캐리의 전달로 인해 연산 속도가 감소된다. 그러나, 이 실시예에서는 캐리없이 배치 가산을 병렬로 수행하므로, 가산 단계를 줄일 수 있으며 고속 연산이 가능하다. 비록 이 실시예의 예에서는 가산을 위해 단지 63개의 7-비트 데이타 시퀀스만을 도시하였지만, 본 발명은 이것에만 한정되지 않고 적어도 하나의 음수값을 포함하는 각종 비트수의 다수의 다중 비트 데이타가 있을 수 있다.
따라서, 희망하는 가산 결과 Q는 2진 모드로 표현된 8개의 가산 결과 모두를 가산시키는 제2가산 단계를 수행함으로써 고속으로 얻어진다.
플래그 비트에 대한 설명은 제9 실시예의 것과 동일하지만, 1의 보수를 2의 보수로 변환시키기 위해서는 플래그 수(음수 데이타 시퀀스의 수)의 가산이 필요하다. 이것은 제27도의 (a)로 표시된 (SF5, SF4, SF3, SF2, SF1, SF0)로 표현된 데이타에 대응한다. 또한 이것은 ND로부터의 출력으로서 인버터에 의해 반전되어 데이타 시퀀스 BSF가 생성된다. 제27도의 (b)는 -부호를 표시하는 플래그 데이타의 1의 보수 표시를 위한 1을 나타낸다. 그 ND로서는, 제13도 또는 제17도에서 기술된 ND를 사용할 수 있다.
[제12 실시예]
이 실시예에서는, 제10 실시예의 8개의 ND를 다수의 유니트에 통합시킴으로써 연산이 행해진다. 제28도에서는 X(X1X0로 표현) + Y(Y1Y0로 표현)의 2-비트 가산기에 대한 일례를 들어 다수결 논리 회로에 대해 후술하기로 한다.
제1 자리 X0및 Y0의 데이타가 단위 캐패시터 C에 입력된다. 제2 자리의 2개의 데이타는 2-폴드 캐패시터 2C를 각각 갖는 터미날로 입력되어 하나의 입력이 2로 계수된다.
예를 들어, 제10 실시예에서는, 제29도에서 도시된 바와 같이, 가중이 0, 1 및 2인 자리의 데이타를 가산시키는 ND를 ND(91)에 통합시킬 수 있으며, 동일한 방법으로 가중이 3, 4 및 5인 자리의 영역을 ND(92)에 통합시킬 수 있다. 제29도의 ND의 경우 입력 및 출력의 수를 숫자로 표시하였지만, 최대 49개의 21-입력까지 계수할 수 있으면 어떠한 ND라도 사용될 수 있다. 각각의 ND는 6-비트 출력을 생성한다. ND(91)의 경우, 자리 0의 데이타는 단위 캐패시터 C에 입력되며, 제1 자리의 데이타는 1C에 입력되며, 제2 자리의 데이타는 (22=) 4C에 입력된다.
또한, 플래그 비트(제8비트)는 수치 비트[제7 비트, MSB(최상위 비트)]와 결합될 수 있다 제29도에서, 플래그 비트는 인버터를 통해 ND(93)에 입력된다. 비록 이 플래그 비트가 상기 실시예에서는 반전용 ND를 통과한 후 인버터를 통과하였지만, 어느 순서로 해도 상관없다. 그러나, 이 실시예에 따르면, ND의 전체 용량은 (2n-1)C(n은 정수)인 것으로 측정된다.
또한, 2의 보수(00010)가 플래그 비트에 가산되어 가중으로서 캐패시터 2C에입력되어진다. 수치 비트는 캐패시터 C에 입력된다. 제29도에서 도시된 바와같이, 각각의 출력은 2의 보수용인 제11 비트의 1에 가산되며 2개의 데이타 시퀀스가 한번에 삭제될 수 있으므로, 단지 2개의 데이타 시퀀스만이 가산되어진다. 가중을 사용함으로서 보다 병렬적으로 처리되어, 연산 속도가 증가되고 소자수 및 전력소모가 감소된다.
이 실시예의 일반적인 가중에 대한 설명의 일례로 인접한 자리들을 통합시켰지만, 본 발명은 이것에만 한정되지 않고 불연속 가중(예를 들어, 20자리의 데이타와 22자리의 데이타가 통합되어 입력) 또는 서로 다른 ND에 상이한 가중을 입력시키기 위해 하나의 자리의 데이타를 분할하는 것과 같은 보다 효율적인 방법을 융통성 있게 사용할 수 있다.
[제13 실시예]
이 실시예에서는, 7개의 8-비트 데이타 시퀀스 가산에 대한 일례를 들어 다수의 다중 비트 데이타의 가산 방식에 대해 기술한다.
제30도를 참조해 보면, 이 실시예가 도시되어 있다. 이 실시예에서는 먼저 7개의 8-비트 데이타 시퀀스의 각 자리의 데이타를 가산하기 위해 배치 가산이 행해진다. 이러한 가산은 ND에 의해 실행된다.
제2 실시예에서와 동일한 방식으로 이 가산 단계의 연산 속도는 단일 ND의 연산 속도에 의해 정해지며, 8개의 ND가 사용되며, ND의 최대 입력수는 7개이다. 또한, 캐리없이 가산이 병렬로 행해져 연산속도가 증가되고 각종 비트수의 다수의다중 비트 데이타가 있을 수 있다는 것도 상기 실시예에서와 동일하다.
희망하는 가산 결과 Q는 2진 모드로 표현된 8개의 가산 결과 모두를 가산시키는 제2가산 단계를 행함으로써 고속으로 얻어진다.
모든 데이타를 가산하지 않고 이 가산 단계의 수행시에 다수의 데이타를 하나의 데이타로 통합시킴으로써 보다 효율적으로 처리를 행할 수 있다. 이러한 관점에서 제30도의 배치 가산 결과 MSB에 주의를 기울여 보면, 각각마다 식 Si2(0 ≤ i ≤ 7)가 얻어지며, 공통 데이타가 없으므로 데이타 시퀀스에 대한 식은 다음과 같이 얻어진다. 즉
다음 자리 및 LSB(최하위 비트)의 각 데이타는 동일한 방법으로 단일의 데이타 시퀀스로 표현될 수 있다. 이들 데이타 시퀀스가 생성되는 단계에 대한 연산은 필요치 않다.
상기 단계는 이하에서 기술하기로 한다. 제3 자리의 I4(I=T, U, ..., Z)의 배치 가산에 의해 3개의 데이타 S30, S31, S32가 생성되며, 각 자리는 3+0, 3+1, 3+2이다. 제 m자리(m ≤1)에 대한 배치 가산에 의해 제(m+n) 자리의 데이타가 생성된다([Log2(IN)]≥n≥0(IN: 데이타 계수), 2≥n≥0(IN=7)). 제 m'(m' ≠ m) 자리에 대한 배치 가산에 의해 동일한 방법으로 제(m'+n) 자리의 데이타가 생성된다. m+n≠m'+n이므로, 데이타에서 공통된 자리는 존재하지 않는다. 따라서, 어떠한 연산 없이도 이들을 하나의 데이타로 통합시킬 수 있다. 연산을 이와 같이 보다 효율적으로 행하면, 데이타는 제30도에서 도시된 예에서는 3개의 데이타 A, B 및 C로 통합될 수 있다.
이는 그 알고리즘의 한 단계로서 취급되더라도 회로에서의 프로세싱으로서 단지 배선만을 갖는 프로세싱에서는 어떠한 연산도 행해지지 않는다는 점에서 제2 실시예와 동일하다.
이 단계에서, 8개의 가산 결과를 3개의 8-비트 데이타 시퀀스로 변환시킬 수 있다. 지연 시간은 다른 단계와 비교하여 무시될 수 있을 정도로 짧다. 마지막으로 3개의 8-비트 데이타 시퀀스를 가산함으로써 최종 연산 결과를 얻을 수 있다. 제30도의 예에서 3개의 8-비트 데이타 시퀀스를 사용하였으므로, 최종 가산 결과는 제5도에서 도시된 단지 2개단의 전 가산기를 통과시킴으로써 얻어지며 다수의 다중 비트 데이타를 고속 연산으로 가산시킬 수 있다.
다음으로, 이 실시예에서는 최대 n-비트 데이타 시퀀스가 m개로 가산되는 일반적인 연산에 대해 후술하기로 한다. n개의 ND로부터 출력된 가산결과는 최대[Log2m] 비트를 가지므로, [Log2m] 데이타 시퀀스로 변환될 수 있다. 마지막으로 [Log2m] 데이타 시퀀스를 가산함으로써, 최종 연산 결과를 얻을 수 있다. 전 가산기 통과단의 수는 [log2[log2m]]으로 표현할 수 있다. 상기 식으로부터, 전 가산기 통과단의 수는 다중 비트 데이타 시퀀스의 수가 많아지더라도 적게 유지될 수 있다. 이러한 효율적인 방법을 2개 이상의 데이타에도 적용시킬 수 있다는 것은 명백한 사실이다.
[제14 실시예]
이 실시예에서는, 제31도의 일례를 들어 다중 비트 데이타간의 승산에 대해 기술한다. 이러한 설명은 (8 ×8)-비트 승산기예 대한 일례를 들어 후술하기로 하며, 이 승산기는 일반적인 (m ×n)-비트 승산으로 확장시킬 수 있다.
X × Y = Q라고 가정하며, 여기서 X(X7X6X5X4X3X2X1X0)는 피승수이며 Y(Y7Y6Y5Y4Y3Y2Y1Y0)는 승수이다. 제3도에서 기술된 바와 같이, Q는 최대 16비트로 표현되며, Q는 m ×n비트시 최대 m + n 비트를 갖는다.
제31도에서 도시된 바와 같이, 부분 적 XixYj가 우선 생성된다. 비록 일반적 CMOS 승산기와 같이 피승수 X의 각 비트 Xi와 승수 Yj를 AND를 취하여 부분전을 계산하였지만, 다른 방법, 예를 들어, 제3 실시예에서 기술된 방법을 사용할 수 있다.
따라서, 제31도의 각 자리에 대한 부분 적인 합을 한번에 ND에 의해 각 자리마다 가산한다. 이러한 가산단계시에 처리는 병렬로 이루어지므로, 고속 연산시에 적합하다. (m ×n)-비트 승산 회로에서는 (m + n - 1) 단위의 ND가 사용된다. ND의 최대 입력수는 Min(m, n)과 동일하다. 제31도에서 도시된 (8 ×8)-비트 승산기의 일례에서는 15개 ND가 사용된다. 최대 8개 입력이 구성된다 (X7Y0+X6Y1+X5Y2+X4Y3+X3Y4+X2Y5+X1Y6+X0Y7연산의 경우).
1-입력 1-출력 구성에서 ND대신 배선으로 대치될 수 있는 장소에서 ND가 사용될때 ND 수가 적용된다. 대체가능한 ND를 생략하면, (m+n-3)개의 ND가 사용된다. 또한, ND대신 2-입력 2-출력 HA(HA가 ND의 일종이지만, ND와는 구별됨)로 대치될 수 있는 장소를 제외하고 단지 3개 이상의 입력에서만 ND를 사용하면, (m+n-5)개의 ND가 사용될 수 있다.
일반적으로, 3개 이상의 입력의 경우, 가산 연산은 복잡해지며 연산 속도는 특히 이 상태에서 발생할 수 있는 캐리의 전달로 인해 감소된다. 이 실시예는 데이타를 모두 가산시켜 캐리없이 연산을 행하는 특징을 지니고 있으므로, 고속 연산이 달성된다.
이후에 2진 모드로 표시된 (m+n-1)개의 가산 결과 모두를 가산시키는 제2가산 단계를 행함으로서, 희망하는 승산 결과 Q가 고속으로 얻어진다.
가산 횟수를 더 감소시키기 위해, 제13 실시예에 따라 데이타를 재배열시킨다. 이것에 대해서는 제32도의 일례를 사용하여 설명되어 있다. 제8 자리의 부분 적의 합은 4(비트)와 동일하다. S73에서 다른 배치 가산으로부터의 3-비트 출력으로 인해, 조건을 만족시키는 데이타는 존재하지 않는다. 따라서, 단일 데이타(A)로서 고려된다. S72의 경우에는, 제4 내지 제12 자리의 부분 적은 3-비트 데이타이며 S72에서는 공통자리가 없는 데이타가 존재한다. 이것은 Si2(3 ≤i ≤11)로 표현된 9-비트 데이타(B)에 대응한다. 동일한 방법으로, 데이타는 Si1 및 SiO로서 하나의 데이타 시퀀스로 통합될 수 있으며 그 데이타는 최종에는 4개의 데이타(A, B, C, D)로 재배열 될 수 있다. 상술된 바와 같이, 이러한 처리에서는 그 알고리즘에 대한 한 단계로서 단지 배선에 의한 연산은 행해지지 않는다.
지연 시간은 다른 단계에 비해 무시될 수 있을 정도로 짧다. 이 단계에서, (m+n-1)개의 가산 결과는 [Log2(Min(m,n))]개의 데이타 시퀀스로 변환될 수 있다. 최종 연산 결과는 최종 처리로서 [Log2(Min(m,n))]개의 데이타 시퀀스를 가산시킴으로서 얻어질 수 있다.
제32도의 예에서는 4개의 데이타를 사용하므로, 최종 적은 제9도에서 도시된 단지 2개단의 전 가산기를 통과함으로써 얻어질 수 있다. 일반적으로, 전 가산기 통과단의 수는 제3 실시예에서와 동일한 방법으로 [Log2[Log2(Min(m,n))]]으로 표현될 수 있다. 따라서, m 및 n이 증가하더라도, 전 가산기 통과단의 수는 제10도의 그래프에 따라 적게 유지될 수 있다. 바꾸어 말하면, 비트수가 증가하더라도, 감소된 소자수와 저전력 소모로 고속 연산을 달성할 수 있다. 또한, S73 및 Si2의 가산시에는, 제11자리 또는 그 이상 자리(S73 + S112 S102 S92 S82)에 대한 가산이 행해지므로 4-비트(캐리를 포함하여 5비트 출력) 가산기를 사용할 수 있다. 이러한 연산 방법은 제3 실시예에서도 동일한 제12도와 동일한 구성을 갖는 승산회로에 적용시킬 수 있다.
이 실시예에 따르면, 제13도와 동일한 구성을 갖는 ND를 사용할 수 있다. 이러한 회로 구성에 의하면, HIG LEVEL 입력수는 제13도의 테이블 1에서 도시된 다수의 입력중 출력될 3자리수의 2진수로 변환될 수 있다. 이 회로에서, 2진수로 변환된 값은 MSB부터 출력되며 각각의 MSB는 거의 동일한 시기에 출력된다. 이들 ND를 사용하면, 거의 동시에 출력된 MSB를 단일 데이타로 통합시킬수 있으므로, 상기 연산시 데이타 압축에 보다 효과적이다.
상기 구성의 승산회로를 사용함으로써, 감소된 소자수와 저전력 소모로 병렬 연산하는 고속 승산기를 구성할 수 있다.
[제15 실시예]
제4 실시예에서와 동일한 방법으로 제17도의 구성은 제13 및 제14 실시예에서 기술된 병렬 배치 가산을 행하는 ND 부에 응용될 수 있다. 제17도의 테이블 1에서 도시된 바와 같이 저전력 소모도 초소형 회로에서 다수의 입력중 고레벨 신호의 입력수를 출력될 3자리수의 2진수로 변환시킬 수 있다. 이 회로에서, 2진수로 변환된 값은 MSB부터 출력된다. 다른 설명은 제13 및 14실시예에서와 동일하지만, 이러한 구성에 의해 소자수가 감소되고 사이즈가 감소되었으므로 전력 소모가 적은 병렬 연산의 고속 반도체 소자를 구성할 수 있다.
[제16 실시예]
이 연산 방법에서는, 제5 실시예에서와 동일하게 제13 실시예의 15개 ND중에서 다수의 ND가 통합된다. ND는 제21도의 구성을 갖는 것으로 가정한다.
제21도의 ND에서는 입력수와 출력수를 수치로 표시하였지만, 56개 입력까지 계수할 수만 있으면 어떠한 ND라도 사용 가능하다. 배선의 경우, 21개 입력까지 사용가능하다. 각각의 ND는 6-비트 출력을 생성한다. 따라서, 데이타는 재배열로 통합되며, MSB에 대응하는 S105, S85, S45 및 S05는 제13 실시예의 규칙에 따라 처리된다. 다음자리의 S104, S84, S44 및 S43은 단일의 데이타로 통합될 수 있으며 MSB 데이타 시퀀스와 공통된 자리를 갖고 있지 않으므로, 또한 하나의 데이타 시퀀스로통합될 수 있다. 따라서, 데이타는 최종에는 2개의 데이타 시퀀스로 통합될 수 있다. 다른 설명은 제13 및 14 실시예의 것과 동일하지만, 승산 회로 이러한 구성에 의해 소자수를 더 감소시킬 수 있으며, 소형 회로의 전력 소모를 감소시킬 수 있으며, 병렬 연산과 가산단계의 감소로 인해 고속 승산기를 구성할 수 있다.
이 실시예의 경우 일반적인 가중에 대한 일례로서 인접한 자리들을 통합시켰지만, 본 발명은 이것에만 한정되지 않고 불연속 가중(예를 들어, 20자리의 데이타와 22자리의 데이타가 통합되어 입력) 또는 서로 다른 ND에 상이한 가중을 입력시키기 위해 하나의 자리의 데이타를 분할(예를 들어, 28자리의 데이타를 2 종류로 분할하여 이들을 서로 다른 ND에 입력)하는 것과 같은 보다 효율적인 방법을 융통성있게 사용할 수 있다.
[제17 실시예]
이 실시예는 63개의 7-비트 데이타 시퀀스가 가산되어지는 일례를 들어 후술한다. 제33도는 이 실시에에 대한 설명을 도시한 것이다. 우선, 63개의 7-비트 데이타 시퀀스를 가산하기 위해 각 자리의 데이타를 함께 가산한다. 이러한 가산은 제14 내지 16 실시예에서와 동일한 회로로 수행된다. 7-비트 데이타 시퀀스를 사용하므로, 이 실시예에서는 7개의 ND가 사용된다. 각 ND의 연산속도는 동일하므로, 전체 연산속도는 단일 ND의 연산속도에 의해 정해진다. 또한, 이 연산시에 63개의 7-비트 데이타 시퀀스가 가산되어지므로, ND의 입력수는 63개와 동일하다. ND는 MSB로부터 순차로 6-비트 출력 데이타를 생성한다. ND에 의해 병렬로 캐리없이 가산을 수행함으로써, 고속 연산이 달성된다. 이 실시예의 예에서는 가산시에 63개의 7-비트 데이타 시퀀스만이 도시되었지만, 본 발명은 이것에만 국한되지 않고 각종 비트수의 다수의 다중 비트 데이타가 있을 수 있다.
따라서, 원하는 가산 결과 Q가 2진 모드로 표현된 8개의 가산 결과의 모두를 가산하는 제2가산 단계를 수행함으로써 고속으로 얻어진다.
이 가산 단계가 아래에 설명된다. 상술한 바와 같이, ND는 MSB로부터 차례로 데이타를 출력하고, 모든 ND로부터의 MSB 및 다음 자리의 데이타는 동일한 시간에 출력된다. MSB의 설명에 관하여는, m번째 자리 (m≥1)에 대한 ND로부터의 MSB는 (m+5)번째 자리에서 출력된다. 바꾸어 말하면, 1 ≤m ≤7의 조건하에서의 m번째 자리에 대한 ND로부터의 MSB는 어떠한 공통 자리도 갖지 않고, 이들은 어떤 연산 없이 하나의 데이타로 통합될 수 있다(제33도에서 프레임으로 둘러싸인 영역). 동일한 방법으로, MSB보다 하나 낮은 자리의 출력은 (m+4)번째 자리의 데이타와 결합될 수 있고, 다음 자리의 데이타는 (m+3)번째 자리의 데이타와 결합될 수 있고, 다음 데이타는 순차적으로 출력 순으로 이와 같이 통합될 수 있다. 제33도에서, 각각의 MSB는 Si5(0≤i≤6)으로 표현될 수 있고 다음의 데이타는 Sik(0≤i≤6)으로 표현될 수 있으므로, (0≤k≤5)의 조건하에서의 6개의 데이타는 순차적으로 출력된다. 이들 데이타는 함께 가산된다. 상기 데이타 재배열로 인해, MSB 데이타 Si5 및 다음 자리의 데이타 Si4가 출력되고, 다음에 Si5 + Si4의 연산이 각 ND가 Si3을 계산하는 동안 실행될 수 있다. 동일한 방법으로, Si3 및 Si2가 출력된 후에, Si3 + Si2의 연산이 ND가 Si1을 계산하는 동안 수행될 수 있다. 따라서, 제2 가산 단계를 시작하여 ND로부터의 결과의 모든 출력을 기다리지 않고서 고속 연산이 달성될 수 있다.
극단적인 경우의 예로서, Si3의 계산중에 Si5 + Si4의 연산이 실행되면, Si3는 Si2의 계산중에 (Si5 + Si4)의 결과에 가산되고, 그 다음에, 가산이 제34도에 도시한 바와 같이 순차적으로 더 실행되고, 전체 연산 속도가 증가될 수 있고 한개의 가산기 만이 필요하기 때문에 소자가 감소될 수 있다. ND 연산 시간과 제2가산 시간간의 최적 값이 있지만, 제2 가산은 ND 가산과 병렬로 수행될 수 있거나, 또는 공통 자리들의 데이타의 배치 가산이 이루어질 수 있어서, 연산 속도가 빨라질 뿐만 아니라 소자 수가 감소되고 따라서 전력 소비가 낮아진다.
[제 18 실시예]
이 실시예는 각종 비트수를 갖는 다수의 데이타 순차를 가산하는 예를 들어 아래에 설명된다. 제35도는 이 실시예의 설명도이다. 8개의 n비트(8≤n≤1) 데이타 시퀀스가 여기서 가산된다. 먼저, 각 자리의 데이타가 8개의 n비트 데이타 시퀀스에 대해 함께 가산된다. 제1 가산은 ND에 의해 수행된다.
최대 8비트 데이타 시퀀스가 이 실시예에서 사용되고, 따라서 8개의 ND가 사용된다(Z7은 수를 나타내고, 7개의 ND가 요구된다. Y6 + Z6은 2개의 입력을 나타내고 HA가 사용될 수 있으나 여기서는 ND가 사용된다). 이 실시예에 따르면 처리가 이 가산 단계와 병렬로 수행되기 때문에, 연산 속도는 ND의 가장 느린 연산 속도에 의해 결정된다. 최대 8개의 입력은 8개의 데이타 시퀀스가 이 연산으로 가산되기 때문에 ND 내로 입력된다. 각각의 ND의 연산 속도는 동일하지 않고 이것은 8-입력ND에 의해 조정된다.
캐리가 일반적인 가산 연산에서 생성하기 때문에, 연산 속도는 캐리 전달에 의해 감소된다. 그러나, 이 실시예는 캐리 없이 데이타를 병렬로 가산하는 특징을 가지어, 보다 높은 연산 속도가 달성된다. 이 실시예가 서로 다른 1에서 8까지의 비트의 다양한 수를 갖는 8개의 데이타 시퀀스를 가산하는 예를 보였지만, 본 발명은 이 예에 제한되지 않는다는 것을 이해할 것이다.
원하는 가산 결과 Q가 2진 모드로 표현된 8개의 가산 결과 모두를 가산하는 제 2 가산 단계를 수행함으로써 고속으로 얻어진다.
처리가 모든 데이타를 간단히 가산함으로써는 효율적이지 않으나, 이 가산 단계를 수행하는 데 있어 다수의 데이타를 하나의 데이타로 통합시킴으로써 보다 효율적으로 된다. 이러한 관점에서 제35도의 배치 가산 결과를 주목하면, 예를 들어, S70, S51, 및 S50의 자리는 전혀 중첩하지 않고, 이들은 어떤 연산을 하지 않고서 하나의 데이타로 통합될 수 있다. 알고리즘상의 단계로서 취급되지만 회로내에서의 처리로서 배선만으로 이루어지는 이 처리에서 연산이 수행되지 않고 지연 시간이 다른 단계들에 비해 무시될 수 있을 정도로 짧은 제2 실시예와 동일하다. 이러한 효율적인 방법으로, 데이타의 2개의 조각은 제35도의 예에서 하나의 데이타로 통합될 수 있다. 그러나, 연산은 데이타의 2개 이상의 조각이 있는 경우에만 동일한 방법으로 보다 효율적일 수 있다.
연산 속도를 더욱 증가시키기 위해서, 제1 및 제2 가산 단계는 병렬로 수행된다. 제35도에서, 8번째 자리의 데이타 또는 S70(Z7)은 ND로부터의 데이타중 가장빨리 출력되고, 7번째 자리의 데이타 S61 및 S60가 출력되고, 다음 데이타는 6번째, 5번째, ... 자리의 순서로 출력된다. 따라서, 제35도의 예에서, S70, S51, S50 + S61, 및 S60에 대한 계산이 예를 들어 제1 자리의 데이타의 계산의 완료를 기다리지 않고서 실행된다. 그 이후에, 다음 출력 결과 S42, S41, S40, S12, S11 및 S10이 가산된다(실제적으로 S42 및 S41이 가산된다), 제1 가산 단계에 대응하는 ND 연산이 제2 가산 단계에 대응하는 연산과 병렬로 실행될 수 있어서, 연산 속도가 빨라진다.
[제19 실시예]
이 실시예에서, 다중 비트 데이타간의 승산이 제31도의 예를 들어 설명된다. (8 ×8) 비트 승산기의 예를 들음으로써 설명되고, 일반적인 (m ×n) 비트 승산으로 확장될 수 있다.
X(X7X6X5X4X3X2X1X0)가 피승수이고 Y(Y7Y6Y5Y4 Y3 Y2Y1Y0)가 승수인 경우 X ×Y=Q라고 가정하자. 제3도에서 설명된 바와 같이, Q는 최대 16 비트로 표현된다. Q는 m ×n 비트에 대한 최대 m + n 비트를 갖는다.
제31도에 도시한 바와 같이, 부분 적 XxYj가 먼저 생성된다. 부분 적이 일반적인 CMOS 승산기와 같이 피승수 X의 각 비트 Xi와 승수 Yj에 AND를 취함으로써 계산되지만, 다른 방법들 중 하나, 예를 들어 제3 실시예에서 설명된 방법이 또한 사용될 수 있다.
다음으로, 제31도의 각각의 자리의 부분 적의 합들은 한번에 ND에 의해 각자리에 대해 가산된다. 처리가 이 가산 단계에서 병렬로 수행되기 때문에, 고속 연산을 위해 적합하다. (m ×n) 비트 승산 회로에서, ND의 (m + n - 1) 유니트가 사용된다. ND로의 입력의 최대수는 Min(m, n)과 동일하다. 제31도에 도시한 (8 ×8) 비트 승산기의 예에서, 15개의 ND가 사용된다. 최대 8개의 입력이 (X7Y0+ X6Y1+ X5Y2+ X4Y3+ X3Y4+ X2Y5+ X1Y6+ X0Y7의 연산에 대해) 가능하다.
ND의 수는 ND가 1-입력 1-출력 배열에서 배선에 의해 대체될 수 있는 위치에 대해 ND가 사용될 때 적용된다. 대체가능한 ND가 생략되는 경우에, (m + n - 3)개의 ND가 사용된다. 또한, ND가 2 입력 2 출력 HA로 대체될 수 있는 위치를 제외한 3개 이상의 입력에 대해서만 사용되는 경우에 (HA는 ND의 일종이지만, ND와는 구별된다), (m + n - 5) 개의 ND가 사용될 수 있다.
일반적으로, 3개 이상의 입력에 대해, 가산 연산은 복잡해지고 연산 속도는 이 상태에서 특히 생성할 수 있는 캐리의 전달로 인해 낮아진다. 이 실시예는 데이타를 함께 가산함으로써 캐리 없이 연산을 수행하는 특징을 갖기 때문에 고속 연산이 달성된다.
그 이후에 2진 모드로 표시된 (m + n - 1)개의 가산 결과의 모두를 가산하는 제2 가산 단계를 수행함으로써, 고속으로 원하는 승산 결과 Q가 얻어진다.
가산의 수를 더욱 감소시키기 위해서, 데이타는 제18 실시예와 동일한 방법으로 통합되어 데이타의 4개의 조각(A, B, C, D)를 재배열하여 준다. 상술한 바와 같이, 그것의 알고리즘상의 단계로서 취급되지만 회로내의 처리로서 배선으로만 이루어지는 이 처리에서 연산이 수행되지 않는다.
지연 시간은 다른 단계들에 비해 무시될 수 있을 만큼 짧다. 제13도 및 제12도의 구성은 각각 ND 및 승산 회로에 적용될 수 있다, 파이프라인 처리는 제3 실시예에서 설명된 바와 같은 제13도에서 수행될 수 있다.
ND에 의해 요구되는 다수결 논리 회로 블럭의 수는 [Log2n]으로 표현되고, 여기서 n은 ND로의 입력의 수이다. ND로의 입력의 수에 관해서는, m ×n 비트 승산기에서 1에서 Min(m, n)까지의 값이 적용되고, 분명히 이것의 연산 시간은 입력 계수가 입력의 최대수인 Min(m, n)인 ND에서 가장 길게 된다. 이것은 다수결 논리 회로 단의 수는 [Log2n]으로 입력 n의 수에 따라 증가되기 때문이다. 그러나, 단의 수는 로그 함수에 따라 증가하기 때문에 비트의 수가 증가될 때 상당히 증가되지 않는 것은 분명하다.
연산이 병렬로 수행되기 때문에, 입력의 최대수 Min(m, n)을 갖는 ND의 연산 속도로 다수의 ND(74)로 종료한다. 이 구성에서, S73(A)가 먼저 출력된다. 다음에, 이것은 연산을 민저 종료한 B에 가산되나, 다른 출력은 이때에 완료되지 않는다. 동일한 방법으로, C는 D가 완전히 출력되기 전에 가산된다, 연산은 이와 같은 병렬 처리로 인해 고속으로 수행될 수 있다.
이 ND 구성은 병렬 연산으로 인해 연산 속도를 빠르게 하고 필요한 소자수가 적어져 ND에 의한 전력 소비를 낮추어, 상기 실시예들에서의 연산 방법의 특성이 상당히 개선될 수 있다.
다수의 ND로부터 출력된 데이타를 알고리즘 상의 하나의 데이타 시퀀스로 통합시키는 단계가 있으나, 상술한 바와 같이 처리가 회로내에서 수행되지 않으므로 제12도의 이 단계에 대응하는 회로는 없다.
상기 승산기 구성은 적은 수의 소자, 저 전력 소모, 및 병렬 연산으로 인해 고속 승산기를 형성하는 것을 가능하게 해준다. 부가적으로, 제17도의 구성은 제4 실시예에서 설명된 ND에 적용될 수 있다.
[제20 실시예]
이 실시예에 따르면, 다수의 ND가 연산에 대해 제19 실시예에서 설명된 제31도의 15개의 ND로부터 통합된다. 연산 방법이 2개의 (8 ×8) 승산 결과를 가산하는 예를 들어 설명되지만, 본 발명은 이 예에 제한되지 않는다.
이것의 예는 2 ×2 승산기에 적용된 2 ×2 다수결 논리 회로에 기초하여 제20도에 도시되어 있다. 바꾸어 말하면, 이것은 제19 실시예의 제13도의 제1 단 내의 다수결 논리 회로이다. 제1 자리의 데이타(20의 자리내의 X0Y0)는 단위 캐패시터 C에 입력된다. 제2 자리의 데이타의 2개의 조각(21의 자리의 X1Y0와 X0Y1)은 2-폴드 용량 2C를 각각 갖는 터미날에 입력되고, 따라서 하나의 입력은 2번 계수된다. 또한, 제3 자리의 데이타(22자리내의 X1Y1)은 22로 가중되고, 하나의 입력은 4번 계수된다.
다른 설명은 제19 실시예와 동일하고 7개까지의 입력은 각 ND 내의 4개의 입력을 갖는 2진 모드에서 출력된다. 이 가중 방법을 사용함으로써, 병렬 배치 가산 기능이 보다 효율적으로 사용될 수 있다.
예를 들어, 제19 실시예의 8 ×8 비트 승산기에서, 가중이 0, 1, 2, 및 3인 자리의 데이타를 가산하는 ND는 제36도에 도시한 ND(91)로 통합되고, 가중이 (4, 5, 6), (7, 8, 9), (10, 11, 12, 13, 14)인 자리의 영역은 각각의 영역[제21도의 ND(92) 내지 ND(94)]으로 통합된다.
입력의 수와 출력의 수가 제36도의 ND에 대한 수로 표시되지만, 56개까지의 입력으로 계수할 수 있는 경우에만 임의의 ND가 사용될 수 있다. 배선을 위해, 21개 까지의 입력이 인가된다. 각각의 ND는 6비트출력을생성한다. 그러므로, 적은 수의 ND가 요구되고 소자가 상당히 감소될 수 있다. 다른 (8 ×8) 승산의 결과 Q'의 가산에서, S105가 출력되고, S105에 대한 S105'가 ND94가 S104를 계산하는 동안 가산될 수 있다. 이것은 또한 다른 데이타 S85 및 S45에 적용될 수 있고, S104 및 S104'는 따라서 그들의 합에 가산될 수 있다. 동일한 계산이 S103 및 S103'에 적용될 수 있고, 부분 합 S"가 ND 연산 및 병렬 연산에 의해 생성될 수 있다.
이 실시예에서, 데이타의 3개의 조각 P, Q, 및 R 만이 마지막으로 가산되어야 한다. 게다가, ND(92)로부터의 S"46이 별도로 P에 가산되면, P와 Q는 하나의 데이타 시퀀스로 통합될 수 있고, 따라서, 데이타의 2개의 조각만이 가산되어야 한다.
따라서, 고속 연산이 달성되고 가산기가 반복적으로 사용될 수 있기 때문에 소자가 상당히 감소될 수 있다. 특히, 상기 다수결 논리 회로를 갖는 ND의 사용은이것의 클럭 동작으로 인해 효과적이다. 승산 회로의 이러한 구성은 소자를 더욱 감소시키게 하고, 소형 회로로 전력 소모를 감소시키고 병렬 연산 및 적은 가산 단으로 인해 고속 승산기를 형성할 수 있다.
연속하는 자리가 이 실시예에서 일반적인 가중 예로 통합되지만, 본 발명은 이 방법에 제한되지 않고, 불연속 가중(예를 들어, 20자리와 22자리 상의 데이타가 통합되어 입력), 또는 서로 다른 ND에 서로 다른 가중값으로 입력시키기 위해 한 자리의 데이타를 분할(예를 들어, 28자리의 데이타를 2종류로 나누고, 이들을 서로 다른 ND에 입력)하는 것과 같은 보다 효율적인 방법들이 융통성 있게 사용될 수 있다.
[제21 실시예]
이 실시예에서, DSP를 위해 사용되는 상기 연산 방법들이 연산을 수행하기 위한 반도체 장치를 갖는 데이타 프로세서를 예를 들어 설명된다.
전형적인 DSP인 고정점 연산을 위한 DSP가 이 실시예에서 설명되었지만, 본 발명은 이것에 제한되지 않고, 이것은 다른 형태의 DSP와 CPU에 적용될 수 있다는 것을 알 수 있다.
상기 실시예들에서의 프로세서는 일반적인 반도체 MOS 트랜지스터를 사용함으로써 형성될 수 있기 때문에 극히 호환성이 있다. 따라서, 이전 반도체 장치가 입력-출력 버퍼의 부착물의 대체물로서 사용될 수 있다.
이 실시예에 따른 DSP의 구성은 제37도에 도시된다. 승산기 및 누산기는 연산유니트로서 DSP 상에 장착된다. 승산기는 31-비트 출력을 얻기 위해 16-비트 데이타의 2개의 조각을 승산하는데 사용된다. 누산기는 16-비트 산술 및 논리 유니트(ALU)와 ALU로부터의 출력 신호를 저장하는 레지스터를 포함한다.
4개의 형태의 온 칩 메모리가 아래에 설명되어 있다. 데이타 RAM은 입력 신호를 저장하는데 사용되고, 입력 신호의 어드레스는 8-비트 데이타 포인터(DP)에 의해 지정된다. DP의 하위 4개의 비트는 4-비트 업-다운 계수기에 의해 처리되고, 상위 4개의 비트는 4-비트 레지스터에 의해 처리된다. 데이타 ROM은 가중 팩터를 저장하기 위해 사용된다. 그것의 어드레스는 10-비트 다운 계수기의 ROM 포인터(RP)에 의해 지정된다. 16-비트 임시 레지스터(TR)는 데이타를 임시 저장하기 위해 사용된다. 코맨드 ROM은 명령을 저장하기 위해 사용되고, 그것의 어드레스는 명령 계수기(PC)에 의해 지정된다.
DSP의 외부 영역과의 신호 수신 또는 송신은 1-비트 직렬 출력 레지스터, 1-비트 직렬 입력 레지스터, 및 8-비트 병렬 입력-출력 레지스터를 통해 수행된다. 직렬 출력 또는 직렬 입력은 출력 제어 신호(SOEN) 또는 입력 제어 신호(SIEN)가 각각 OV일 때 직렬 입력-출력 클럭(SCK)와 동기로 실행된다. 8-비트 병렬 출력은 판독/기록 제어 신호(CS)가 OV일때 기록 제어 신호(WR) 또는 판독 제어 신호(RD)를 OV로 설정한 후에 수행된다. SO으로부터 출력될 8개의 비트에 대한 데이타가 직렬 출력 레지스터 내에 저장될 때, 출력 준비 신호(SORQ)가 5V로 설정된다.
각각의 명령은 프로그램 계수기(PC)의 지정에 의해 매 클럭 주기마다 ROM으로부터 판독된다. 연산 유니트 또는 메모리는 각각의 판독 명령의 각 디코딩 결과에 따라 동작한다.
리셋 펄스(RST)가 인가되면, PC의 포인터 위치는 어드레스 0으로 설정되고 DSP는 그것의 동작을 시작한다. 그 다음 인터럽트 펄스(INT)가 따라서 인가되면, PC 포인터 위치는 어드레스 256으로 점프된다. 입력-출력 모드(8-비트 또는 16-비트)의 선택과 인터럽트가 받아들여져야 하는지 여부의 선택이 8-비트 병렬 입력-출력 레지스터 내의 16-비트 상태 레지스터(SR)에 의해 결정된다. 클럭 구동기는 외부 영역으로부터의 클럭 펄스(CLK)에 기초하여 2 위상 클럭 T0와 T2를 생성하고 이들을 연산 유니트 또는 메모리에 제공한다. 데이타는 입력-출력 레지스터, 연산 유니트 및 메모리간에 16-비트 버스를 통해 전송된다.
이 실시예에서, 상기 16-비트 ×16-비트 고속 승산기는 다른 논리 회로 및 메모리와 동일한 회로 보드 상에 그리고 동일한 공정으로 형성된다.
이 DSP의 실제 동작 타이밍은 12-단 파이프라인 적 및 합 연산을 예를 들어 아래에 설명된다. 제38도는 연산 중의 2-위상 클럭 펄스를 도시한 것이다. 데이타 ROM 또는 데이타 RAM 내에 저장된 판독한 입력 신호 또는 가중 팩터는 판독되고, 바꾸어 말하면, 승산기에 데이타를 공급하는 것은 클럭 주기 m의 T0가 하이(5V)로 될 때(이후, T0타이밍) 수행되고 승산은 다음으로 실행된다. 승산 결과는 다음 클럭 주기(m+1)의 T0타이밍에서 레지스터에 래치된다. 동시에, 다음 데이타의 승산은 승산기예서 병렬로 처리된다.
일반적으로, 연산 속도는 비트의 수가 증가할수록 감소되고 특히 승산 속도는 이것에 기여한다. 그러나, 이 실시예에 따른 고속 승산기를 사용함으로써, 연산 속도가 증가되어, DSP 성능에 주목할만한 개선을 가져다 준다. 또한, 이것은 일반적인 CMOS 처리가 형성될 수 있다는 장점을 갖는다. 연산 방법이 이 실시예에서 승산기로서 DSP에 적용되지만, 본 발명은 본래 이것에 제한되지 않고, 입력 및 출력 또는 처리가 일반적인 CMOS 처리와 동일하다는 융통성을 고려하여, 다른 응용의 예로서 다수의 다중 비트에 대한 가산 또는 승산 프로세스를 포함하는 다양한 연산 회로에 적용될 수 있다는 것은 분명하다. 본 발명은 연산 속도를 증가시킬 뿐만 아니라 칩 면적의 감소와 저 전력 소비와 같은 여러가지 효과를 갖는다.
[제22 실시예]
이 실시예에서, 상기 프로세서는 확산 스펙트럼 통신(SS 통신)을 위한 수신 회로내의 상관 연산 유니트에 적용된다. 이 수신 회로의 구성이 제39도에 도시되어 있다. 제39도에 도시한 바와 같이, 수신 회로는 수신 안테나(1401), 신호를 증폭하는 증폭기 유니트(1402), 상관 연산 유니트(1403A 및 1403B), A/D 변환 유니트(1404), 선택기(1405), 및 검출기(1406)을 포함한다.
SS 통신에서, 신호는 PN 코드라고 하는 다중 비트 코드로 변환되고 PN 코드가 송신된다. 수신 회로에서, 이전에 저장된 유사한 PN 코드는 수신된 신호와 비교되고 최고의 상관 상태가 송신된 신호를 복조하기 위해 검출된다.
제39도를 참조하면, 안테나(1401)에 의해 수신된 신호는 검출기(1406)에 의해 주로 복조되고, 하나는 상관 연산 유니트(1403A)에 송신되고 다른 것은 A/D 변환 유니트에서 디지탈 신호로 변환되고 그 다음에 상관 연산 유니트(1403B)에 입력된다. 입력된 신호는 수신 회로에 이전에 저장된 PN 코드와 비교되고, 상관 연산 유니트(1403A)는 2개의 신호간의 상관 정도로부터 동기 신호를 생성하고, 상관 연산 유니트(1403B)는 동기 신호와 동기로 상관 스코어(score)를 계산한다. 다음에, 신호는 선택기(1405)에 의해 상관 연산 유니트(1403B)로부터 출력된 상관 스코어에 기초하여 복조된다.
SS 통신이 신호가 송신되기 전에 다중 비트 코드로 변환되기 때문에 호출 프라이버시 및 잡음 방지의 고 성능의 탁월한 특징을 갖지만, 송신된 정보량의 증가로 인해 수신된 신호를 PN 코드와 비교함으로써 높은 상관 상태를 검출하기 위해서 제 45도에 도시한 가산 회로에서 가산의 반복을 필요로 하기 때문에 상당한 로드가 실제 신호 처리에 부과된다는 문제를 갖고 있다.
그러나, 상기 실시예에 따른 프로세서에서 이들 가산을 수행함으로써, 연산 속도가 빠를 뿐 아니라 소자 수가 적고 전력 소비가 적은 SS 통신 수신 회로를 형성하는 것이 가능하다. 따라서, SS 통신 시스템에서 무선 통신을 위한 휴대용 정보 장치를 만드는 것이 가능하다.
또한, 제40도에 도시한 것과 같은 컴팩트 카드형 수신/송신 유니트(2001)가 만들어질 수 있다. 왜냐하면 높은 연산 속도는 적은 수의 소자 및 낮은 전력 소비로 많은 양의 정보를 통신하는 것을 가능하게 하기 때문이다. 그러므로, 통상적인 퍼스널 컴퓨터의 인터페이스를 갖는 PCMCIA 카드에 SS 통신을 적용하는 것이 용이해 진다. PCMCIA 카드가 이 예에서 사용되지만, 본 발명은 다른 인터페이스에 용이하게 적용될 수 있다. 입력 및 출력은 통상 CMOS 호환성이 있으므로 크기를 줄이고전력 소비를 낮추는 것이 상기 프로세서에 의해 용이하게 달성될 수 있다.
상기 설명이 SS 통신을 위한 데이타 프로세서를 예를 들어 이루어졌지만, 입력-출력 인터페이스는 상술한 바와 같이 CMOS 호환성이 있고, 본 발명은 특히 음수값을 포함하는 다수의 다중 비트 데이타를 가산하기 위한 다른 데이타 프로세서에 예를 들어 상기 언급된 DSP 또는 CPU 또는 영상 또는 음성을 처리하기 위한 병렬연산 처리 유니트에 적용될 수 있다. 또한, 평균 또는 표준 편차 및 최소 제곱법과 같은 수치 연산을 얻기 위한 통계 처리에도 사용될 수 있다.
또한, 고속 연산, 크기 감소 및 저전력 소비의 장점으로 인해 와이어리스 LAN, I/O 관리 시스템, 정산 시스템, 비디오 회의 시스템과 같은 다양한 시스템을 상당히 개선시키는데 효과적이다.
상기 실시예에 따르면, 다수의 다중 비트 데이타가 고속으로 가산될 수 있다.
또한, 음수 값을 포함하는 다수의 다중 비트 데이타가 고속으로 가산될 수 있다.
또, 다수의 다중 비트 데이타가 고속으로 승산될 수 있다.
나아가, 다수의 다중 비트 데이타를 고속으로 연산하기 위한 프로세서가 반도체 장치를 낮은 전력 소비로 사용함으로써 적은 칩 면적 내에 형성될 수 있다.
이 프로세서는 일반적인 반도체 공정에서 만들어질 수 있기 때문에 다양한 데이타 프로세서에 적용될 수 있고, 따라서 DSP, CPU와 같은 데이타 프로세서, 및 고속 연산 및 작은 칩 면적과 저 전력 소비를 갖는 장치와 같은 SS 통신을 위한 수신/송신유니트를 만드는 것이 가능하다.
본 발명이 어느 정도의 특정성을 가지고, 양호한 형태로 설명되었지만, 본 발명의 많은 명백히 폭넓은 다른 실시예가 본 발명의 원리 및 범위를 벗어나지 않고서 이루어질 수 있다. 본 발명은 첨부된 특허 청구의 범위에 정의된 것을 제외하고 그 특정 실시예에 제한되지 않는다.
제1도는 제1 실시예의 가산기를 도시한 도면.
제2도는 제1 실시예의 다수결 논리 회로를 도시한 도면.
제3A도 및 제3B도는 ND를 도시한 도면.
제4도는 제2 실시예의 가산기를 도시한 도면.
제5도는 제2 실시예의 제2 가산 단계를 실행하기 위한 가산기를 도시한 도면.
제6도는 제3 실시예의 가산기를 도시한 도면.
제7도는 제3 실시예의 부분 적 생성 회로를 도시한 도면.
제8도는 제3 실시예의 승산기를 도시한 도면.
제9도는 제3 실시예의 가산기를 도시한 도면.
제10도는 제3 실시예의 총 가산기 통과 단계들의 수를 도시한 도면.
제11도는 제3 실시예의 승산 프로세싱 프로시져를 도시한 도면.
제12도는 제3 실시예의 승산 회로를 도시한 도면,
제13도는 제3 실시예에서 사용된 ND를 도시한 도면.
제14도는 제3 실시예에서 사용된 다수결 논리 회로를 도시한 도면.
제15도는 제3 실시예에서 사용된 다수결 논리 회로를 도시한 도면.
제16도는 제3 실시예에서 사용된 신호들의 타이밍도.
제17도는 제4 실시예에서 사용된 ND를 도시한 도면.
제18도는 제4 실시예에서 사용된 다수결 논리 회로를 도시한 도면.
제19도는 제4 실시예에서 사용된 신호들의 타이밍도.
제20도는 제5 실시예에서 사용된 다수결 논리 회로를 도시한 도면.
제21도는 제5 실시예의 승산기를 도시한 도면.
제22도는 제6 실시예의 승산기를 도시한 도면.
제23도는 제7 실시예의 승산기를 도시한 도면.
제24도는 제8 실시예의 승산기를 도시한 도면.
제25도는 제9 실시예의 가산기를 도시한 도면.
제26도는 제10 실시예의 가산기를 도시한 도면.
제27도는 제11 실시예의 가산기를 도시한 도면.
제28도는 제12 실시예의 2 비트 가산기를 도시한 도면.
제29도는 제12 실시예의 가산기를 도시한 도면.
제30도는 제13 실시예의 가산기를 도시한 도면.
제31도는 제14 실시예의 승산기를 도시한 도면.
제32도는 제14 실시예의 다른 승산기를 도시한 도면.
제33도는 제17 실시예의 가산기를 도시한 도면.
제34도는 제17 실시예의 다른 가산기를 도시한 도면.
제35도는 제18 실시예의 가산기를 도시한 도면.
제36도는 제20 실시예의 승산기를 도시한 도면.
제37도는 제21 실시예의 DSP를 도시한 도면.
제38도는 제21 실시예의 동작 타이밍도.
제39도는 제22 실시예의 수신 회로를 도시한 도면.
제40도는 제22 실시예의 카드형 송신/수신 유니트를 도시한 도면.
제41A도 내지 제41D도는 종래의 가산기를 설명하기 위한 도면.
제42A도 내지 제42C도는 종래의 CLA 회로의 설명을 위한 도면.
제43도는 블럭 CLA가 인가되는 종래의 가산기의 구성의 일례를 도시한 도면.
제44도는 종래의 가산기의 구성의 일례를 도시한 도면.
제45도는 종래의 가산기의 구성의 일례를 도시한 도면.
제46도는 종래의 승산기의 구성의 일례를 도시한 도면.
도면의 주요 부분에 대한 부호의 설명
11 : 수 검출기(ND) 31 : 5-입력 다수결 논리 회로
71 : 피승수 입력 유니트 72 : 승수 입력 유니트
73 : 부분 적 생성기 유니트 132 : 인버터
133 내지 138 : 터미날

Claims (31)

  1. 다수의 다중 비트 데이타 (multiple bit data)를 가산하는 프로세서에 있어서,
    다수의 수 검출 수단들 (number detection means) - 상기 수 검출 수단들 각각은, 각각의 하나의 비트 자리에 대하여 상기 다수의 다중 비트 데이타로부터 값 1을 갖는 비트들의 수를 검출하고, 상기 검출된 수를 상기 각각의 하나의 비트 자리에 대한 가산 결과로서 이진 표시 (binary representation)로 출력함 -을 구비하는 제1 가산 수단, 및
    상기 제1 가산 수단에 의해 얻어진 상기 가산 결과들의 합을 계산하는 제2 가산 수단
    을 포함하고,
    상기 수 검출 수단들 각각은,
    다수의 다수결 논리 연산들 (majority logic operations)을 연속적으로 수행하는 다수결 논리 연산 수단 - 각각의 상기 다수결 논리 연산은 검출 대상인 모든 비트들과 선행(先行)의 다수결 논리 연산의 가중 결과 (weighted result)를 입력들로서 수신하여, 각각의 하나의 비트 자리의 값으로서 상기 다수결 논리 연산들의 각각의 결과를 검출될 수의 이진 표시로 출력함으로써 수행됨 -
    을 포함하는 것을 특징으로 하는 프로세서.
  2. 제1항에 있어서, 상기 제1 가산 수단은 상기 다수의 다중 비트 데이타에 대해 개별적으로 각각의 자리상의 데이타를 가산하는 것을 특징으로 하는 프로세서.
  3. 제1항에 있어서, 상기 제1 가산 수단은 상기 다수의 다중 비트 데이타에 대해 다수의 자리 상에서의 데이타를 가산하는 것을 특징으로 하는 프로세서.
  4. 제1항에 있어서, 상기 제2 가산 수단은 가산 연산 시에 공통 자리를 갖지 않는 다수의 가산 결과들을 상기 제1 가산 수단의 상기 가산 결과들 중의 단일 데이타로 통합하는 것을 특징으로 하는 프로세서.
  5. 제1항에 있어서, 다수의 상기 수 검출 수단들로부터의 출력들은 적어도 하나의 다른 수 검출 수단으로 입력되는 것을 특징으로 하는 프로세서.
  6. 제1항에 있어서, 상기 다수결 논리 연산 수단들은, 각각이 상기 다수의 다수결 논리 연산들 중의 각각의 연산을 수행하는 다수의 다수결 논리 회로들을 포함하는 것을 특징으로 하는 프로세서.
  7. 제1항에 있어서, 상기 다수의 다수결 논리 회로들 준의 적어도 하나는, 다수의 입력 터미날들, 상기 다수의 입력 터미날들과 스위치들을 통해 접속된 다수의 캐패시터들, 및 상기 다수의 캐패시터들이 공통으로 접속된 감지 증폭기를 포함하는 것을 특징으로 하는 프로세서.
  8. 제8항에 있어서, 상기 선행의 다수결 논리 연산의 결과는 특정 캐패시터의 용량을 상기 다수의 캐패시터들 중의 다른 캐패시터들의 용량의 소정 수의 배수와 동일하게 함으로써 가중화되는 것을 특징으로 하는 프로세서.
  9. 제1항에 있어서, 상기 다수결 논리 연산 수단은, 후속하는(succeeding) 다수결 논리 연산을 위한 입력으로서 상기 선행의 다수결 논리 연산의 결과를 피드백함으로써 상기 다수의 다수결 논리 연산들을 수행하는 다수결 논리회로를 포함하는 것을 특징으로 하는 프로세서.
  10. 제7항에 있어서, 상기 감지 증폭기로부터의 출력들은 래치 수단을 통해 상기 다수의 입력 터미널들중 적어도 하나에 접속되는 것을 특징으로 하는 프로세서.
  11. 제1항에 있어서, 상기 다수의 다중 비트 데이타는 부호를 나타내는 플래그비트를 포함하고 상기 제1 가산 수단은 상기 플래그 비트를 포함하는 상기 다수의 다중 비트 데이타의 각각의 자리 상의 데이타를 개별적으로 가산하는 것을 특징으로 하는 프로세서.
  12. 제11항에 있어서, 상기 다수의 다중 비트 데이타는 2의 보수로 표현된 음의값을 포함하는 것을 특징으로 하는 프로세서.
  13. 제11항에 있어서, 상기 다수의 다중 비트 데이타는 1의 보수로 표현된 음의 값을 포함하는 것을 특징으로 하는 프로세서.
  14. 제1항에 있어서, 상기 제2 가산 수단은 가산 연산 시에 상기 제1 가산 수단에 의해 생성된 서로 다른 자리들의 가산 결과들 중 각 자리로부터 카운트된 n번째(n ≥0) 자리 상의 데이타를 단일 데이타로 통합하는 것을 특징으로 하는 프로세서.
  15. 제1항에 있어서, 상기 제2 가산 수단은 상기 제1 가산 수단에 의해 생성된 각 자리에 대한 가산 결과들 중 각 자리로부터 계수된 n번째 (n ≥ 0) 자리 상의 데이타를 통합하는 것을 특징으로 하는 프로세서.
  16. 제14항에 있어서, 상기 n번째 자리는 각각의 자리의 가산 결과들의 최상위 자리에 대응하는 것을 특징으로 하는 프로세서.
  17. 제16항에 있어서, 상기 제1 가산 수단은 상기 최상위 자리로부터의 가산 결과들을 순차적으로 출력하는 것을 특징으로 하는 프로세서.
  18. 제1항에 있어서, 상기 제2 가산 수단은 상기 제1 가산 수단에 의해 이미 실행된 부분 자리들에 대한 가산 결과들을 사용하여 상기 제1 가산 수단에 의해 실행된 다른 부분 자리들에 대한 가산과 병행해서 가산을 실행하는 것을 특징으로 하는 프로세서.
  19. 제18항에 있어서, 상기 제2 가산 수단은 상기 제1 가산 수단에 의해 실행된 가산 결과들을 서로 가산하는 것을 특징으로 하는 프로세서.
  20. 제18항에 있어서, 상기 제2 가산 수단은 상기 제1 가산 수단에 의해 실행된 가산 결과들을 상기 제2 가산 수단에 의해 이미 실행된 가산 결과들에 가산하는 것을 특징으로 하는 프로세서.
  21. 다수의 다중 비트 데이타를 승산하는 프로세서에 있어서,
    상기 다수의 다중 비트 데이타의 부분 적들(partial product)을 생성하는 부분적 생성 수단;
    다수의 수 검출 수단들 - 상기 수 검출 수단들 각각은, 각각의 하나의 비트 자리에 대하여 상기 부분 적 생성 수단에 의해 생성된 다수의 부분 적들로부터 값 1을 갖는 비트들의 수를 검출하고, 상기 검출된 수를 상기 각각의 하나의 비트 자리에 대한 가산 결과로서 이진 형태로 출력함 -을 구비하는 제1 가산 수단; 및
    상기 제1 가산 수단에 의해 얻어진 상기 가산 결과들의 합을 계산하는 제2가산 수단
    을 포함하고,
    상기 수 검출 수단들 각각은,
    다수의 다수결 논리 연산들을 연속적으로 수행하는 다수결 논리 연산 수단 - 각각의 상기 다수결 논리 연산은 검출 대상인 모든 비트들과 선행의 다수결 논리 연산의 가중 결과를 입력으로서 수신하여, 각각의 하나의 비트 자리의 값으로서 상기 다수결 논리 연산들의 각각의 결과를 검출될 수의 이진 표시로 출력함으로써 수행됨 -
    을 포함하는 것을 특징으로 하는 프로세서.
  22. 제21항에 있어서, 상기 부분 적 생성 수단은 제1 다중 비트 데이타의 각각의 비트와 제2 다중 비트 데이타의 특정 비트의 부분 적들을 동시에 생성시키는 것을 특징으로 하는 프로세서.
  23. 제21항에 있어서, 상기 부분 적 생성 수단은,
    상기 제1 다중 비트 데이타의 각각의 비트들을 병렬로 입력하는 입력 수단, 및
    상기 제2 다중 비트 데이타의 각각의 비트의 값에 따라 상기 입력 수단으로부터의 입력들에 대해 온 또는 오프를 설정하는 스위치 수단을 포함하는 것을 특징으로 하는 프로세서.
  24. 제21항에 있어서, 상기 부분 적 생성 수단은 게이트 전극들이 공통으로 접속되어 있는 다수의 트랜지스터들을 포함하는 것을 특징으로 하는 프로세서.
  25. 제21항에 있어서, 상기 부분 적 생성 수단은 다수의 AND 회로들을 포함하는 것을 특징으로 하는 프로세서.
  26. 제21항에 있어서, 상기 제2 가산 수단은 가산 연산 시에 상기 제1 가산 수단에 의해 생성된 서로 다른 자리들의 가산 결과들 중 각 자리로부터 카운트된 n번째(n ≥0) 자리상의 데이타를 단일 데이타로 통합하는 것을 특징으로 하는 프로세서.
  27. 제21항에 있어서, 상기 제2 가산 수단은 상기 제1 가산 수단에 의해 이미 실행된 부분 자리들에 대한 가산 결과들을 사용하여 상기 제1 가산 수단에 의해 실행된 다른 부분 자리들에 대한 가산과 병행해서 가산을 실행하는 것을 특징으로 하는 프로세서.
  28. 프로세서에 있어서,
    데이타를 입력하는 입력 수단,
    데이타를 저장하는 저장 수단,
    상기 저장 수단에 의해 저장된 데이타와 상기 입력 수단으로부터 입력된 데이타를 주어진 처리 절차로 처리하는 처리 수단, 및
    상기 처리 수단으로부터의 처리 결과들을 출력하는 출력 수단
    을 포함하고,
    상기 처리 수단은,
    다수의 수 검출 수단들 - 상기 수 검출 수단들 각각은,.각각의 하나의 비트 자리에 대하여 상기 다수의 다중 비트 데이타로부터 값 1을 갖는 비트들의 수를 검출하고, 상기 검출된 수를 상기 각각의 하나의 비트 자리에 대한 가산 결과로서 이진 형태로 출력함 -을 구비하는 제1 가산 수단, 및
    상기 제1 가산 수단에 의해 얻어진 가산 결과들의 합을 계산하는 제2 가산 수단
    을 포함하며,
    상기 수 검출 수단들 각각은,
    다수의 다수결 논리 연산들을 연속적으로 수행하는 다수결 논리 연산 수단 - 각각의 상기 다수결 논리 연산은 검출 대상인 모든 비트들과 선행의 다수결 논리 연산의 가중 결과를 입력들로서 수신하여, 각각의 하나의 비트 자리의 값으로서 상기 다수결 논리 연산들의 각각의 결과를 검출될 수의 이진 표시로 출력함으로써 수행됨 -
    을 포함하는 것을 특징으로 하는 프로세서.
  29. 제28항에 있어서, 상기 처리 수단은 다수의 다중 비트 데이타 부분 적들을 생성하는 부분 적 생성 수단을 더 포함하고, 상기 부분 적 생성 수단에 의해 생성된 부분 적들은 상기 제1 및 제2 가산 수단을 사용하여 가산되는 것을 특징으로 하는 데이타 프로세서.
  30. 제28항에 있어서, 상기 입력 수단은 신호들을 입력하고, 상기 저장 수단은 가중 팩터들 (weighting factor)을 저장하고, 상기 처리 수단은 입력된 신호들을 누산하기 위해 각각의 가중 팩터로 승산하는 것을 특징으로 하는 데이타 프로세서.
  31. 제28항에 있어서, 상기 입력 수단은 다중 비트 부호들을 입력하고, 상기 저장 수단은 다중 비트 부호들을 이미 저장하고 있으며, 상기 처리 수단은 입력된 다중 비트 부호들과 저장된 다중 비트 부호들 간의 상관량을 계산하여 이 계산된 상관량에 기초하여 입력된 다중 비트 부호들을 복조하는 것을 특징으로 하는 프로세서.
KR1019960010745A 1995-04-11 1996-04-10 프로세서와이의연산방법 및 데이타프로세서 KR100359965B1 (ko)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP96-089541 1995-04-11
JP8525595 1995-04-11
JP95-085255 1995-04-11
JP08954196A JP3658079B2 (ja) 1995-04-11 1996-04-11 演算処理装置及びデータ処理装置

Publications (2)

Publication Number Publication Date
KR960038594A KR960038594A (ko) 1996-11-21
KR100359965B1 true KR100359965B1 (ko) 2003-03-15

Family

ID=32827169

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1019960010745A KR100359965B1 (ko) 1995-04-11 1996-04-10 프로세서와이의연산방법 및 데이타프로세서

Country Status (6)

Country Link
US (1) US5978827A (ko)
EP (1) EP0741354B1 (ko)
JP (1) JP3658079B2 (ko)
KR (1) KR100359965B1 (ko)
CN (1) CN1129066C (ko)
DE (1) DE69632978T2 (ko)

Families Citing this family (50)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3607494B2 (ja) * 1998-03-03 2005-01-05 東芝マイクロエレクトロニクス株式会社 加算器
US6490608B1 (en) * 1999-12-09 2002-12-03 Synopsys, Inc. Fast parallel multiplier implemented with improved tree reduction schemes
EP1178397B1 (en) * 2000-08-01 2006-10-04 STMicroelectronics S.A. Carry save adders
US7136888B2 (en) 2000-08-04 2006-11-14 Arithmatica Limited Parallel counter and a logic circuit for performing multiplication
US6883011B2 (en) 2000-08-04 2005-04-19 Arithmatica Limited Parallel counter and a multiplication logic circuit
GB2365636B (en) * 2000-08-04 2005-01-05 Automatic Parallel Designs Ltd A parallel counter and a multiplication logic circuit
US6729168B2 (en) * 2000-12-08 2004-05-04 Stmicroelectronics, Inc. Circuit for determining the number of logical one values on a data bus
US6701339B2 (en) * 2000-12-08 2004-03-02 Intel Corporation Pipelined compressor circuit
GB2373602B (en) * 2001-03-22 2004-11-17 Automatic Parallel Designs Ltd A multiplication logic circuit
US7080111B2 (en) * 2001-06-04 2006-07-18 Intel Corporation Floating point multiply accumulator
US6779013B2 (en) * 2001-06-04 2004-08-17 Intel Corporation Floating point overflow and sign detection
EP1308836A1 (en) * 2001-10-31 2003-05-07 Motorola, Inc. Adder tree structure with reduced carry ripple adder stage
US20030154227A1 (en) * 2002-02-08 2003-08-14 Intel Corporation Multi-threaded multiply accumulator
US7734675B1 (en) * 2002-12-05 2010-06-08 Cisco Technology, Inc. System and method for generating a binary result in a data processing environment
US7293056B2 (en) * 2002-12-18 2007-11-06 Intel Corporation Variable width, at least six-way addition/accumulation instructions
US7260595B2 (en) * 2002-12-23 2007-08-21 Arithmatica Limited Logic circuit and method for carry and sum generation and method of designing such a logic circuit
US6909767B2 (en) 2003-01-14 2005-06-21 Arithmatica Limited Logic circuit
US7042246B2 (en) 2003-02-11 2006-05-09 Arithmatica Limited Logic circuits for performing threshold functions
US7308471B2 (en) 2003-03-28 2007-12-11 Arithmatica Limited Method and device for performing operations involving multiplication of selectively partitioned binary inputs using booth encoding
US7170317B2 (en) 2003-05-23 2007-01-30 Arithmatica Limited Sum bit generation circuit
JP2005182238A (ja) * 2003-12-17 2005-07-07 Renesas Technology Corp 演算装置
US20050228845A1 (en) * 2004-04-12 2005-10-13 Mathstar, Inc. Shift and recode multiplier
US20060020655A1 (en) * 2004-06-29 2006-01-26 The Research Foundation Of State University Of New York Library of low-cost low-power and high-performance multipliers
JP4810090B2 (ja) * 2004-12-20 2011-11-09 キヤノン株式会社 データ処理装置
US8271572B2 (en) * 2008-10-14 2012-09-18 The Research Foundation Of State University Of New York Generating partial sums
JP2011107972A (ja) * 2009-11-17 2011-06-02 Fujitsu Ltd 総和計算方法及び数値演算装置
JP5048748B2 (ja) * 2009-12-18 2012-10-17 三菱電機株式会社 試験テーブル生成装置及び試験テーブル生成方法
CN102999310A (zh) * 2012-12-14 2013-03-27 蒋海勇 一种新型芯片晶体管阵列方法
US9355066B1 (en) * 2012-12-17 2016-05-31 Marvell International Ltd. Accelerated calculation of array statistics
RU2547625C2 (ru) * 2013-06-28 2015-04-10 федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский ядерный университет МИФИ" (НИЯУ МИФИ) Многовходовой сумматор
US9836218B2 (en) * 2014-10-03 2017-12-05 Micron Technology, Inc. Computing reduction and prefix sum operations in memory
US10171105B2 (en) 2016-08-25 2019-01-01 International Business Machines Corporation Carry-less population count
US11283453B2 (en) 2019-12-27 2022-03-22 Kepler Computing Inc. Low power ferroelectric based majority logic gate carry propagate and serial adder
US11018672B1 (en) * 2019-12-27 2021-05-25 Kepler Computing Inc. Linear input and non-linear output majority logic gate
US10944404B1 (en) * 2019-12-27 2021-03-09 Kepler Computing, Inc. Low power ferroelectric based majority logic gate adder
US11374574B2 (en) 2019-12-27 2022-06-28 Kepler Computing Inc. Linear input and non-linear output threshold logic gate
US11165430B1 (en) * 2020-12-21 2021-11-02 Kepler Computing Inc. Majority logic gate based sequential circuit
US11381244B1 (en) 2020-12-21 2022-07-05 Kepler Computing Inc. Low power ferroelectric based majority logic gate multiplier
US11394387B1 (en) 2021-05-21 2022-07-19 Kepler Computing Inc. 2-input NAND gate with non-linear input capacitors
US11764790B1 (en) * 2021-05-21 2023-09-19 Kepler Computing Inc. Majority logic gate having paraelectric input capacitors coupled to a conditioning scheme
US11303280B1 (en) 2021-08-19 2022-04-12 Kepler Computing Inc. Ferroelectric or paraelectric based sequential circuit
US12118327B1 (en) 2021-09-02 2024-10-15 Kepler Computing Inc. Ripple carry adder with inverted ferroelectric or paraelectric based adders
US11705905B1 (en) 2021-12-14 2023-07-18 Kepler Computing, Inc. Multi-function ferroelectric threshold gate with input based adaptive threshold
US12218045B1 (en) 2021-12-14 2025-02-04 Kepler Computing Inc. Stacked planar capacitors based multi-function linear threshold gate with input based adaptive threshold
US11664370B1 (en) 2021-12-14 2023-05-30 Kepler Corpating inc. Multi-function paraelectric threshold gate with input based adaptive threshold
US11716083B1 (en) 2021-12-23 2023-08-01 Kepler Computing Inc. Asynchronous circuit with threshold logic
US11855627B1 (en) 2022-01-13 2023-12-26 Kepler Computing Inc. Asynchronous consensus circuit using multi-function threshold gate with input based adaptive threshold
US11967357B2 (en) * 2022-01-21 2024-04-23 National Tsing Hua University Memory unit with time domain edge delay accumulation for computing-in-memory applications and computing method thereof
US11967954B1 (en) 2022-04-20 2024-04-23 Kepler Computing Inc. Majority or minority logic gate with non-linear input capacitors without reset
US11765908B1 (en) 2023-02-10 2023-09-19 Kepler Computing Inc. Memory device fabrication through wafer bonding

Family Cites Families (18)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3524977A (en) * 1967-01-17 1970-08-18 Rca Corp Binary multiplier employing multiple input threshold gate adders
US3535502A (en) * 1967-11-15 1970-10-20 Ibm Multiple input binary adder
US3636334A (en) * 1969-01-02 1972-01-18 Univ California Parallel adder with distributed control to add a plurality of binary numbers
US3603776A (en) * 1969-01-15 1971-09-07 Ibm Binary batch adder utilizing threshold counters
US3675001A (en) * 1970-12-10 1972-07-04 Ibm Fast adder for multi-number additions
US3723715A (en) * 1971-08-25 1973-03-27 Ibm Fast modulo threshold operator binary adder for multi-number additions
US3795880A (en) * 1972-06-19 1974-03-05 Ibm Partial product array multiplier
US3950636A (en) * 1974-01-16 1976-04-13 Signetics Corporation High speed multiplier logic circuit
FR2454136B1 (fr) * 1979-04-12 1985-12-06 Materiel Telephonique Additionneur sequentiel rapide
FR2536922A1 (fr) * 1982-11-26 1984-06-01 Efcis Comparateur logique a plusieurs fonctions
CA1236220A (en) * 1984-10-11 1988-05-03 Sterling R. Whitaker Multiplier circuitry using pass transistors
DE3524797A1 (de) * 1985-07-11 1987-01-22 Siemens Ag Anordnung zur bitparallelen addition von binaerzahlen
GB2189630B (en) * 1986-04-23 1990-02-14 Stc Plc Multiplier
FR2599526A1 (fr) * 1986-05-29 1987-12-04 Centre Nat Rech Scient Additionneur mos et multiplicateur binaire mos comprenant au moins un tel additionneur
KR920007505B1 (ko) * 1989-02-02 1992-09-04 정호선 신경회로망을 이용한 곱셈기
US5161119A (en) * 1990-02-14 1992-11-03 Lsi Logic Corporation Weighted-delay column adder and method of organizing same
KR920006323B1 (ko) * 1990-05-31 1992-08-03 삼성전자 주식회사 스킵(Skip)배열과 수정형 월리스(Wallace)트리를 사용하는 병렬 승산기
DE69303725D1 (de) * 1992-11-20 1996-08-22 Unisys Corp Verbesserter schneller multiplizierer

Also Published As

Publication number Publication date
EP0741354A2 (en) 1996-11-06
JPH08339292A (ja) 1996-12-24
EP0741354A3 (en) 1997-05-02
CN1129066C (zh) 2003-11-26
DE69632978T2 (de) 2005-07-21
EP0741354B1 (en) 2004-07-28
CN1139777A (zh) 1997-01-08
KR960038594A (ko) 1996-11-21
JP3658079B2 (ja) 2005-06-08
DE69632978D1 (de) 2004-09-02
US5978827A (en) 1999-11-02

Similar Documents

Publication Publication Date Title
KR100359965B1 (ko) 프로세서와이의연산방법 및 데이타프로세서
US5465226A (en) High speed digital parallel multiplier
US6523055B1 (en) Circuit and method for multiplying and accumulating the sum of two products in a single cycle
US5771186A (en) System and method for multiplying in a data processing system
Wang et al. A high-speed residue-to-binary converter for three-moduli (2/sup k/, 2/sup k/-1, 2/sup k-1/-1) RNS and a scheme for its VLSI implementation
EP0328063A2 (en) Absolute value calculating circuit having a single adder
Uya et al. A CMOS floating point multiplier
WO1996028774A1 (en) Exponentiation circuit utilizing shift means and method of using same
US5343417A (en) Fast multiplier
EP0416869B1 (en) Digital adder/accumulator
JPH10187418A (ja) パストランジスターロジックを使用する条件合加算器及びそれを具備した集積回路
EP0670061B1 (en) Enhanced fast multiplier
US5867412A (en) Modular multiplication device for information security
KR19990074385A (ko) 부동소수점 곱셈기에서 반올림과 덧셈을 동시에 수행하는 장치및 방법
US5935202A (en) Compressor circuit in a data processor and method therefor
US5777907A (en) Processor for selectively performing multiplication/division
US7225217B2 (en) Low-power Booth-encoded array multiplier
KR100663679B1 (ko) 고속 가산기
Varalakshmi et al. Implementation of Multiplier Architecture Using Efficientcarry Select Adders for Synthesizing Fir Filters
EP1014260B1 (en) Sticky bit value predicting circuit
KR19990003926A (ko) 곱셈기의 면적 감소와 고속 동작을 위한 부분곱 생성과 부분곱 가산 트리를 구현하는 방법
JP2894749B2 (ja) 並列乗算器
Erdogan et al. Low power multiplication schemes for single multiplier CMOS based FIR digital filter implementations
US6058411A (en) Method and device for computing product sums
Abraham et al. An ASIC design of an optimized multiplication using twin precision

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 19960410

PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 19960410

Comment text: Request for Examination of Application

AMND Amendment
AMND Amendment
PG1501 Laying open of application
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 19990420

Patent event code: PE09021S01D

AMND Amendment
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 19991125

Patent event code: PE09021S01D

AMND Amendment
E601 Decision to refuse application
PE0601 Decision on rejection of patent

Patent event date: 20010216

Comment text: Decision to Refuse Application

Patent event code: PE06012S01D

Patent event date: 19991125

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I

Patent event date: 19990420

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I

J201 Request for trial against refusal decision
PJ0201 Trial against decision of rejection

Patent event date: 20010525

Comment text: Request for Trial against Decision on Refusal

Patent event code: PJ02012R01D

Patent event date: 20010216

Comment text: Decision to Refuse Application

Patent event code: PJ02011S01I

Appeal kind category: Appeal against decision to decline refusal

Decision date: 20020731

Appeal identifier: 2001101001430

Request date: 20010525

AMND Amendment
PB0901 Examination by re-examination before a trial

Comment text: Amendment to Specification, etc.

Patent event date: 20010625

Patent event code: PB09011R02I

Comment text: Request for Trial against Decision on Refusal

Patent event date: 20010525

Patent event code: PB09011R01I

Comment text: Amendment to Specification, etc.

Patent event date: 20000525

Patent event code: PB09011R02I

Comment text: Amendment to Specification, etc.

Patent event date: 19990920

Patent event code: PB09011R02I

Comment text: Amendment to Specification, etc.

Patent event date: 19960810

Patent event code: PB09011R02I

Comment text: Amendment to Specification, etc.

Patent event date: 19960711

Patent event code: PB09011R02I

B601 Maintenance of original decision after re-examination before a trial
PB0601 Maintenance of original decision after re-examination before a trial
J301 Trial decision

Free format text: TRIAL DECISION FOR APPEAL AGAINST DECISION TO DECLINE REFUSAL REQUESTED 20010525

Effective date: 20020731

PJ1301 Trial decision

Patent event code: PJ13011S01D

Patent event date: 20020801

Comment text: Trial Decision on Objection to Decision on Refusal

Appeal kind category: Appeal against decision to decline refusal

Request date: 20010525

Decision date: 20020731

Appeal identifier: 2001101001430

PS0901 Examination by remand of revocation
S901 Examination by remand of revocation
GRNO Decision to grant (after opposition)
PS0701 Decision of registration after remand of revocation

Patent event date: 20020909

Patent event code: PS07012S01D

Comment text: Decision to Grant Registration

Patent event date: 20020807

Patent event code: PS07011S01I

Comment text: Notice of Trial Decision (Remand of Revocation)

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20021024

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20021025

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20051011

Start annual number: 4

End annual number: 4

FPAY Annual fee payment

Payment date: 20061011

Year of fee payment: 5

PR1001 Payment of annual fee

Payment date: 20061011

Start annual number: 5

End annual number: 5

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

Termination category: Default of registration fee

Termination date: 20080910