United States Patent 19
`Cliff et al.
`
`54
`
`(75)
`
`PROGRAMMABLE LOGICARRAY
`CIRCUITS COMPRISING LOOK UP TABLE
`IMPLEMENTATION OF EAST CARRY
`ADDERS AND COUNTERS
`
`Inventors: Richard G. Cliff, Milpitas; L. Todd
`Cope, San Jose; Kerry Veenstra, San
`Jose; Bruce B. Pedersen, San Jose, all
`of Calif.
`
`Assignee: Altera Corporation, San Jose, Calif.
`
`Appl. No.:
`09/136,317
`Aug. 19, 1998
`Filed:
`Related U.S. Application Data
`
`Continuation of application No. 08/847,004, May 1, 1997,
`Pat. No. 5,828.229, which is a continuation of application
`No. 08/555,106, Nov. 8, 1995, Pat. No. 5,633,830, and
`application No. 08/655,870, May 24, 1996, Pat. No. 5,668,
`771, which is a continuation of application No. 08/245,509,
`May 18, 1994, Pat. No. 5,550,782, which is a continuation
`in-part of application No. 08/111,693, Aug. 25, 1993, Pat.
`No. 5,436,575, which is a continuation-in-part of application
`No. 07/754,017, Sep. 3, 1991, Pat. No. 5,260,610, and a
`continuation-in-part of application No. 07/880,942, May 8,
`1992, Pat. No. 5,260,611.
`Int. Cl. ................................................ H03K 19/177
`U.S. C. ....
`326/40, 326/39; 326/41
`Field of Search .................................. 326/37, 39, 40,
`326/41
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`2
`
`5 8
`
`56)
`
`4,124,899 11/1978 Birkner et al. .......................... 364/716
`4,623,982 11/1986 Ware ....................................... 364/788
`4,642,487 2/1987 Carter.
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`European Pat. Off. .......... G06F 7/50
`456475 11/1991
`9/1988 United Kingdom......... HO3K 19/173
`22O2356
`
`USOO5926036A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,926,036
`Jul. 20, 1999
`
`OTHER PUBLICATIONS
`E.J. McCluskey, “Iterative Combinational Switching Net
`works-General Design Considerations”, IRE Transactions
`on Electronic Computers, Dec. 1958, pp. 285-291.
`R.C. Minnick, “A Survey of Microcellular Research”, Jour
`nal of the ASSociation for Computing Machinery, Vol. 14,
`No. 2, pp. 203–241, Apr. 1967.
`(List continued on next page.)
`Primary Examiner Michael Tokar
`Assistant Examiner Daniel D. Chang
`Attorney, Agent, or Firm Fish & Neave; Robert R.
`Jackson; Walter M. Egbert, III
`57
`ABSTRACT
`A programmable logic array integrated circuit has a number
`of programmable logic modules which are grouped together
`in a plurality of logic array blocks (“LABs”). The LABs are
`arranged on the circuit in a two dimensional array. A
`conductor network is provided for interconnecting any logic
`module with any other logic module. In addition, adjacent or
`nearby logic modules are connectable to one another for
`Such special purposes as providing a carry chain between
`logic modules and/or for connecting two or more modules
`together to provide more complex logic functions without
`having to make use of the general interconnection network.
`Another network of So-called fast or universal conductorS is
`provided for distributing widely used logic Signals Such as
`clock and clear Signals throughout the circuit. Multiplexers
`can be used in various ways to reduce the number of
`programmable interconnections required between Signal
`conductors. Look up tables for use in programmable logic
`devices are modified to facilitate use of those tables to
`provide adders (including Subtracters) and various types of
`counters. Each look up table is effectively partitioned into
`Smaller look up tables when an adder or counter is required.
`One portion of the partitioned table is used to provide a Sum
`out Signal, while the other portion of the partitioned table is
`used to provide a fast carry out Signal for application to the
`next Stage of the adder or counter.
`
`15 Claims, 31 Drawing Sheets
`
`240
`
`244-
`242
`
`280
`28-- -
`
`
`
`R
`
`R
`
`2803r
`a
`
`is 2805
`
`284-3
`30-22828-s:
`280-3
`al-II
`282-
`3:04 is
`280S D.
`4 is
`244-6 281-8 E. 282-8
`R
`o
`2306
`
`288
`2 of
`s
`s:
`
`7?
`
`AA
`
`Y
`
`y
`20
`
`2852
`284- 4
`
`3.
`
`244-3
`2444
`245
`28-3
`As
`8
`&280-8
`-280i
`as
`-
`34.8 28-4
`" * - as
`Rios
`£2809
`44-10 281-5
`vil-
`280-IO
`- at
`Rai as E
`280-II
`R
`244.13
`
`R
`
`R
`
`Intel Exhibit 1008
`Intel v. Iida
`
`

`

`5,926,036
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`4,706,216 11/1987 Carter ........................................ 365/94
`4,742,520 5/1988 Hoac et al. ............................... 371/49
`4,758,985
`7/1988 Carter ........................................ 365/94
`4,815,022 3/1989 Glaeser et al. .......................... 364/716
`4,870,302 9/1989 Freeman.
`5,053,647 10/1991 Shizukuishi et al..
`5,059,828 10/1991 Tanagawa.
`5,274,581 12/1993 Cliff et al. .............................. 364/784
`5,349.250 9/1994 New .
`5,386,156
`1/1995 Britton et al. ............................ 326/37
`5,481,206
`1/1996 New et al. ................................ 326/38
`5,481,486
`1/1996 Cliff et al. .............................. 364/716
`5,631,576 5/1997 Lee et al. .................................. 326/39
`OTHER PUBLICATIONS
`Recent Developments in Switching Theory, A. Mukho
`padhyay, ed., Academic Press, New York, 1971, Chapters VI
`and IX, pp. 229-254 and 369-422.
`
`
`
`H. Fleisher, “An Introduction to Array Logic', IBM Journal
`of Research and Development, Mar. 1975, pp. 98-109.
`B. Kitson et al., “Programmable Logic Chip Rivals Gate
`Array in Flexibility”, Electronic Design, Dec. 8, 1983, pp.
`95-102.
`“The World's Most Versatile Logic Tool; AmPAL22V10”,
`Advanced Micro Devices, Inc., May 1984.
`R.H. Freeman, “XC3000 Family of User-Programmable
`Gate Arrays”, Microprocessors and Microsystems, vol. 13,
`No. 5, Jun. 1989, pp. 313–320.
`D.D. Hill et al., “Preliminary Description of Tabula Rasa, an
`Electrically Reconfigurable Hardware Engine', Proceedings
`1990 IEEE International Conference on Computer Design:
`VSLI in Computers and Processors, Sep. 17-19, 1990, pp.
`391-395.
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 1 of 31
`
`5,926,036
`
`yuajed‘S'0
`
`
`6661‘07‘TL
`TeJO[yous
`
`/ 9 / -/
`
`a TT Sw —— ee
`
`'
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 2 of 31
`
`5,926,036
`
`S- sH a
`
`IIllllllllllllll
`
`
`
`
`
`
`
`
`
`
`
`
`
`as -d
`
`-5:HE
`
`as
`
`ot It AlllllI.
`
`Illlllllllllllll
`III Distill
`
`
`
`
`C
`
`II. se
`
`Siitiitiitii
`CNU Essi
`ERRERH
`EssRH
`ERIERH
`assi
`EERIERH
`EssRH
`as EEE H
`Essi
`SEERH
`25-3EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
`(S-NH. SEH Q
`SEERH
`Se: |MII S
`assiutit U
`S2ERH
`HIN
`ES-SEEIH
`as EEE MI 3
`sts
`L Hi
`Ess C
`SEE
`
`
`
`
`
`
`
`
`
`
`
`
`
`IWILLIALW
`Illill
`Ill
`
`Ill HEEE a
`
`e N Y-H -- - -
`CN
`
`n
`
`C
`c
`
`N
`e
`
`mo II.
`
`titl III
`
`III.
`
`SE
`
`It is
`
`telli MIL
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 3 of 31
`Sheet 3 of 31
`
`5,926,036
`5,926,036
`
`£Old
`
`
`
`
`
`318¥1df¥001INdN
`
`
`-b+dO-dlld
`
`
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 4 of 31
`
`5,926,036
`
`
`
`LOOK-UP TABLE
`
`A / G 4
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 5 of 31
`
`5,926,036
`
`
`
`
`
`
`U.S.PatentJul.20,1999Sheet5of315,926,036
`
`
`
`
`
`
`
`
`
`
`- - - s
`
`
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 6 of 31
`
`5,926,036
`
`59
`
`50
`
`56
`
`50w
`56
`
`56
`50
`56n
`
`50w
`
`A / G 7
`
`50
`
`56
`
`40
`
`42
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 7 of 31
`Sheet 7 of 31
`
`5,926,036
`5,926,036
`
`40 OR 42
`40 OR 42
`
`540
`54 /
`54 7
`
`540
`
`50
`00
`
`55
`30
`
`54
`
`I
`
`50
`90
`
`i'
`
`ti
`
`500
`30a
`
`50b
`00b
`
`A / G 3
`FIG. &
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 8 of 31
`
`5,926,036
`
`es
`
`Crd -
`
`us
`
`C
`e
`
`
`
`
`S.
`
`S.
`
`
`
`
`
`
`
`du
`-
`so
`s
`s
`c
`e
`o
`C
`Ca
`Q
`
`ue
`Coca
`S.
`
`has
`
`uld
`
`|
`
`|
`|
`
`|
`|
`
`|
`|
`
`|
`|
`
`y
`
`s
`
`N |
`|
`|
`s fill R.
`
`|
`|
`
`|
`|
`| |
`
`y
`
`t
`
`s s
`
`ld
`al
`as a
`ar
`e
`al
`s
`se
`d
`C
`Q
`
`s S.
`
`ld
`
`N
`
`H H H SS
`
`as
`
`s
`
`a
`
`as
`
`A
`
`g
`Ls
`
`|
`
`|
`
`|
`
`|
`
`SS
`
`N
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 9 of 31
`
`5,926,036
`
`so
`r
`N
`
`Filmlaimilami,
`
`s s
`
`Film ITE
`
`S
`
`T
`
`
`
`T
`DTD
`DTTT
`TTE
`TDOT DITED
`DOT DITE
`EDT
`III.
`To
`TTTTTTTT
`DTD
`DTD
`Tin
`DTTOT
`still
`DDDDD
`SDTD
`TTTTTTTTTTTTTTT
`Sir
`
`N,
`s a
`-
`N an
`N
`
`S.
`sa
`S
`Sw
`
`ar
`N
`&n
`
`e
`&r &
`S
`
`e
`Sn
`SN
`
`sm
`
`es
`n
`N
`
`se
`a.
`N
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 10 of 31
`
`5,926,036
`
`- - - - - - - - - - - - - - - - - - - -
`
`-
`
`25
`
`Hi-fi
`
`F FR Romeowmomes
`
`E
`
`I"
`His
`HIES. i
`HE Elit-8
`Hi-Fi
`II
`.
`.
`HH
`y
`is ti
`2542 22 H E.
`-
`|HH
`'Eic
`It is
`HH
`Hi
`III-252
`III O
`25:
`254
`
`it --
`- - -and
`
`.255.
`
`-
`
`
`
`
`
`224
`
`226
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 11 of 31
`Sheet 11 of 31
`
`5,926,036
`
`e
`so
`N
`
`S.
`
`CN
`SN
`
`O~
`
`CN
`re
`GN
`
`C
`es
`CN
`
`e
`e
`
`e
`N
`
`ed
`s
`N
`
`5,926,036 Ni~
`
`
`
`<>
`
`gawite
`
`ow
`
`S&S
`
`am|™FfWS Nw!
`
`oS
`||
`&
`a
`ee ee
`
`(=)
`
`=
`i+)
`
`s
`s
`
`S-
`N
`
`=o
`
`eo
`s
`as ©=
`
`S.
`14
`
`S.
`212
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 12 of 31
`
`5,926,036
`
`
`
`AF/G /3
`PROR ART
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 13 of 31
`
`5,926,036
`
`ed
`e
`
`ac
`N
`
`De C & D
`
`es
`es
`N
`
`c Oc )
`
`is
`
`es
`es
`N
`
`to
`
`se
`
`s
`e
`
`SAF C - C) R
`2-CD o O o O
`
`n O ORP C-CP
`
`R
`
`C - --
`
`
`
`
`CO
`
`is
`
`O
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 14 of 31
`
`5,926,036
`
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 15 of 31
`Sheet 15 0f 31
`
`5,926,036
`5,926,036
`
`
`
`
`2\2
`
`FIG. 156
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 16 of 31
`Sheet 16 of 31
`
`5,926,036
`5,926,036
`
`S.
`
`= N
`
`I
`
`.o
`
`FIG/éa
`
`S
`
`=c
`
`co
`
`O
`
`s
`
`o
`O
`CCD
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`
`
`922
`
`bee
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 17 of 31
`Sheet 17 of 31
`
`5,926,036
`5,926,036
`
`IFDIA
`
`2ldAyaN}9208
`
`

`

`5,926,036
`5,926,036
`
`ZlOIAFQek
`
`U.S. Patent
`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 18 of 31
`
`“j0vIsv9
`
`ale
`
`4
`
`2b¢be
`
`lee
`
`
`TronTSHAINN(419ONAS/318¥N38
`fdNoi3000|(NOG/dN)¥
`
`
`indi.n0|Ty822sys)91901(vivay)
`1NdINDABBV—_19913AUBVI|41)
`
`
`
` ale
`Q¥O1ONASY9=2419
`
`
`viv(avo1)d
`
`WOUINOD¥90T919LnaNt
`
`
`
`
`
`
`acul)i|aw/tyy
`
`
`
`41901AuuydLSW4
`
`
`
`oe¢Loannod3d¥9S¥9
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 19 of 31
`Sheet 19 of 31
`
`5,926,036
`5,926,036
`
`TRIOUT
`
`g
`VOC
`
`S
`18.
`S
`F/G
`
`s
`VCC
`
`
`
`veC
`
`= =—
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 20 of 31
`
`5,926,036
`
`402
`
`404
`
`406
`
`400
`
`BLACK BOX
`
`
`
`A/G /9
`
`
`
`428
`
`
`
`4.
`
`
`
`4.
`
`CONTROL
`UNIT
`
`MEMORY BLOCK
`
`A/G 20
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 21 of 31
`
`5,926,036
`
`'FAST====th
`INPUISHE is
`II2 EEE
`CH NESSEE
`464
`O
`
`56 CH LINES
`
`-
`64 PROGRAMMING
`ADDRESSES H is
`24. MyxESS
`FOR 8 DATA LINES
`
`
`
`
`
`
`
`64
`repara FRON 4 CONTROL RAMS.
`
`465
`
`469
`
`5 NSB ADDRESSES 4.72
`450
`
`DATA IN
`BUFFERS
`
`
`
`
`
`6
`43
`
`A.
`GISTER CLK
`,468
`ADD
`RESS
`DEC
`6
`ODE
`
`READ/
`As
`32
`480
`
`TO2
`ADDRESS
`MUXING
`
`
`
`
`
`
`
`
`
`READ
`ADDR
`64
`
`TE
`ADDR
`64
`
`414 (iii)
`24: MUXES I
`RE473
`FOR 6 LEAST
`6TH
`SES47 ADEREs.
`SiGNIFICAN 462B
`REG/6
`c
`ADDRESS LINES
`P M
`WE
`80CR 47
`E
`474
`Pros of I
`ADDCLki.
`24: MUXES
`FOR 5 MOST
`TSE
`SIGNIFICANT 462C
`ADDRESS LINES
`ii
`. 5 MSB ADDR
`AND WRITE
`iiiiC 476
`ENABLE
`24: NUXES I REGISTER CLK
`FOR CLKA 462D
`{ it: USER TR-STATE OE
`OE LINES
`446° 47' is
`TO TR-STATE DRIVERS OE
`FOR CV DRIVERS ONLY
`A/G 2/-/
`
`FRON 4
`CONTROL RAMST
`
`
`
`469
`READ/WRITE W
`
`472
`
`478
`
`
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 22 of 31
`
`5,926,036
`
`C230
`
`220
`
`I
`
`
`
`- - EEBS EEEEEEEEEEEEE
`
`EPP-Ele-ROn
`--
`K.
`EE ICC
`
`O
`
`-7
`
`HR as
`
`PROG DATA
`FRON PREVIOUS ROW
`32 - 479
`
`
`
`
`
`
`
`
`
`COLUMN DECODER AE SELECTION AND CONTROL
`447
`3ricou or 323ERYE ANW
`
`460
`
`RAM BLOCK
`64 X 32 BITS - 2K BITS
`PROGRAMMABLE RAM WIDTH WITH 1, 2, 4 OR 8 BIT
`WIDE OPTIONS
`
`32 BITS
`
`/V 9/V
`A VA V
`
`452
`RAM DATA OUTPUT SELECTION
`454
`8PROGRAMMABLE DATAOUT 32-482
`
`H.
`
`8 RAM REGISTERS
`
`TO NEXT ROW
`DATAOUT 7
`
`EEI
`
`DATA OUT O
`
`8 REGISTERED OUTPUTS
`A/G 2/-2
`
`s
`
`456
`
`s
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 23 of 31
`
`5,926,036
`
`
`
`L.
`3."
`3"
`DDD 3D
`3"
`
`N --/
`A/G 224
`
`A/6 22A
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 24 of 31
`
`5,926,036
`
`
`
`600
`
`M 60
`
`A/G 234
`
`A/G 25E9
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 25 of 31
`
`5,926,036
`
`230
`LABLENE FROM ABOVE
`4 FASTEEEEEEFA
`INPUTS-FFFFFSF't
`
`68 EEEEEEE
`CHEEEEEEE
`
`6 SRAMEEEEEEE
`CH
`
`535
`
`LAB
`CONNECTION
`64
`up
`---, BLOCK
`PROGRAMMING
`ADRESSESIm
`9,
`i
`24: NUXES 536A
`REG, el JDATA IN
`FOR 8 DATA LINES
`
`
`
`FULLY
`O = POPULATED
`MUXES
`
`8, DAAIN
`
`560
`
`508 READ/
`WRITE
`
`4 ADDRESS
`
`524
`
`S.
`32
`
`BLOCK
`INTERFACETE
`SIDE ADDR
`32
`
`32
`5
`RE
`554
`WE
`
`6THLEAST SIGNIFICANT
`ADDRESS LINE
`560 4 ADDRESS
`
`
`
`44
`
`EEEEEEEEEEEEEEEEEEEEEE
`24: MUXES
`FOR 6 LEAST 536B R
`SIGNIFICANT
`ADDRESS LINES
`
`
`
`
`
`PROG MODE
`24: NUXES
`FOR 5 NOST
`SIGNIFICANT 536C
`ADDRESS LINES
`AND WRITE
`ENABLE
`
`sts
`
`
`
`
`
`C
`
`
`
`TR-STATE OE
`5441R-STATEOE D CONTROL
`546
`24: MUXES I El SIAE
`FORGE 536D-
`66
`OE LINES
`
`TO TR-STATE
`DRIVERS OE
`
`AIG 24-/
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 26 of 31
`
`5,926,036
`
`--ARTIALLY
`() = POPULATED
`MUXES
`
`FROM PROC.
`DATA REG.
`321-555
`
`522
`RAN BLOCK INTERFACE, TOP
`DINBO(3:01.4 520
`4DNB73:0
`X8
`
`32
`GW
`
`yVyV
`tf\
`
`- a
`
`ma mo as amus - - - - - - a m - - -
`
`-
`
`-
`
`a
`
`as on a
`
`re-
`
`222
`
`64BITS
`
`RAM BLOCK
`32 X 64. BITS
`
`IB
`
`RAN IS ARRANGED IN 4 BLOCKS OF 8 BITS BY 64
`WORDS
`32 BITS
`
`/KYV
`VA M
`
`
`
`
`
`
`
`
`
`8 D087A(3-0), D087B(3:OX8, DOBOAC3-0),DOBOB(3:018 SL II
`RAM BLOCK iNTERFACE, BOTTOM
`
`it."
`an or
`
`
`
`
`
`ESI
`
`Cs
`
`DATA OUT O
`
`8 REGISTERED OUTPUTS
`A/G 24-2
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 20, 1999
`Jul. 20, 1999
`
`Sheet 27 of 31
`Sheet 27 Of 31
`
`5,926,036
`5,926,036
`
`
`
`
`
`A/G 264
`FIG. 25A
`
`A/G 26A
`FIG. 258
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 28 of 31
`
`5,926,036
`
`| | | }}
`||
`
`
`
`
`
`
`
`tae92 '9/-/
`
`}0010
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 29 of 31
`
`5,926,036
`
`56
`
`050
`
`- at Y
`52
`54
`st-
`4.050
`1152- . 154 FROM DATA BUFFER
`62
`164\PROG VERIFY USER
`T2
`
`60
`
`74
`
`A/G 27
`
`READ
`BT
`NE
`
`&
`70
`SEVENODD7 COL SELECTION2 - 190?
`READ WORD LNE it O
`WRITE WORD LNE HO
`T1-18
`READ WORD LNE
`WRITE WORD LNEE
`
`- T-4-
`
`
`
`80
`
`READ WORD LNE it 63
`WRITE WORD LNE it 63
`
`9 OW
`WRITE
`ENE
`LN
`PROG VERIFY
`1222
`: s 1220
`56
`
`050
`52-18
`54
`
`56
`
`52
`
`1050
`
`54
`
`r
`230
`20
`W8 4 x2 XM
`
`22
`
`TO OUTPUT REGISTER
`
`232
`
`

`

`U.S. Patent
`
`Jul. 20, 1999
`
`Sheet 30 of 31
`
`5,926,036
`
`240
`
`24
`
`
`
`
`
`
`
`
`
`
`
`2, CE
`3D
`E)
`280-6
`
`244-6 281-8
`
`Y
`
`V
`240b
`
`M
`L
`K
`
`His H.
`
`A/G 23
`
`

`

`U.S. Patent
`
`
`
`
`Jul. 20, 1999
`
`Sheet 31 of 31
`
`5,926,036
`
`yuajed‘S'0
`
`
`6661‘07TL
`TeJOTe04s
`
`OUT
`
`eae
`CASCADE
`|
`CONNECT
`|
`
`i
`
`| 92/982
`
`
`
`240
`
`|
`An
`
`L CONNECT
`
`2i20
`
`R)
`
`

`

`5,926,036
`
`1
`PROGRAMMABLE LOGICARRAY
`CIRCUITS COMPRISING LOOK UP TABLE
`IMPLEMENTATION OF EAST CARRY
`ADDERS AND COUNTERS
`
`2
`distance connections to be made without tying up more
`general purpose and therefore long distance interconnection
`resources, etc. There is also a continuing demand for logic
`devices with larger capacity. This produces a need to imple
`ment logic functions more efficiently and to make better use
`of the portion of the device which is devoted to intercon
`necting individual logic modules.
`It is therefore an object of this invention to provide
`improved programmable logic array integrated circuits.
`It is a more particular object of this invention to provide
`programmable logic array integrated circuits with additional
`possibilities for interconnections between the logic modules.
`It is a further object of this invention to provide improved
`techniques for organizing and interconnecting the program
`mable logic elements in programmable logic array inte
`grated circuits.
`Cliff et al. U.S. Pat. Nos. 5,550,782 and 5,689,195 show
`programmable logic array integrated circuit devices with
`relatively large blocks of random access memory (“RAM”)
`in addition to the usual large number of programmable logic
`modules and the usual programmable network of intercon
`nection conductors. (These two references are hereby incor
`porated by reference herein.) These RAM blocks can be
`programmed at the same time that the rest of the device is
`programmed and thereafter used as read-only memory
`(“ROM") to perform logic, arithmetic functions, state
`machine operations, etc., that may be more efficiently per
`formed in one large memory block (or a Small number of
`such blocks) rather than in several of the individually
`relatively small logic modules. Alternatively, the RAM
`blocks may be used as random acceSS memory during use of
`the device to perform logic.
`From the foregoing it will be seen that the above
`mentioned RAM blocks have several possible uses and
`require several different modes of operation. They should be
`programmable like other memory cells on the device (i.e.,
`the other memory cells that control the functioning of the
`logic modules and the interconnection conductor network).
`This is necessary when the RAM blocks are to be used as
`ROM. Their programming in this way should be capable of
`verification like other memory cells on the device (i.e.,
`reading out of the programmed data to ensure that the
`memory cells are programming properly). The RAM blocks
`should also be programmable as random acceSS memory
`during use of the device to perform logic. And the RAM
`blocks should be readable as random access memory or
`read-only memory, also during use of the device to perform
`logic. All of these possible uses and modes of operation of
`these RAM blocks tend to significantly complicate the
`circuitry required to provide Such blockS.
`In view of the foregoing, it is still another object of this
`invention to improve and simplify the provision of blocks of
`RAM on programmable logic array integrated circuit
`devices.
`It is a more particular object of this invention to provide
`RAM block circuitry for use on programmable logic array
`integrated circuit devices that facilitates programming and
`verification of the RAM block for use as ROM, and that also
`facilitates programming and reading the block as RAM
`during use of the device to perform logic.
`Programmable logic devices are also known in which
`programmable look up tables are used to perform relatively
`elementary logic functions (See, for example, Wahlstrom
`U.S. Pat. No. 3,473,160 (FIG. 8) and Pedersen et al. U.S.
`Pat. No. 5,260,610). A look up table may provide as an
`output any desired logical function of Several inputs. The
`
`25
`
`35
`
`40
`
`15
`
`This is a continuation of application Ser. No. 08/847,004,
`filed May 1, 1997, now U.S. Pat. No. 5,828,229, which is a
`continuation of application Ser. No. 08/555,106, filed Nov.
`8, 1995, now U.S. Pat. No. 5,633,830, and application Ser.
`No. 08/655,870, filed May 24, 1996, now U.S. Pat. No.
`5,668,771, which is a continuation of application Ser. No.
`08/245,509, filed May 18, 1994, now U.S. Pat. No. 5,550,
`782, which is a continuation-in-part of application Ser. No.
`08/111,693, filed Aug. 25, 1993, now U.S. Pat. No. 5,436,
`575, which is a continuation-in-part of application Ser. No.
`07/754,017, filed Sep. 3, 1991, now U.S. Pat. No. 5,260,610,
`and a continuation-in-part of application Ser. No. 07/880,
`942, filed May 8, 1992, now U.S. Pat. No. 5,260,611.
`BACKGROUND OF THE INVENTION
`This invention relates to programmable logic array inte
`grated circuits, and more particularly to programmable logic
`array integrated circuits with improved arrangements of the
`programmable logic elements and improved interconnec
`tions between those elements. The invention also relates to
`the provision of relatively large blocks of random acceSS
`memory (“RAM”) on programmable logic array integrated
`circuit devices. This invention still further relates to logic
`devices employing look up tables, and more particularly to
`improved ways of providing fast carry functions in Such
`devices when the devices are to be used for Such purposes
`as performing addition, Subtraction, and counting.
`Programmable logic arrays are known in which Substan
`tial numbers of relatively elementary individual program
`mable logic elements are provided in a two-dimensional
`array. The array also includes a grid of interSecting Signal
`conductors for conducting logic Signals to, from, and
`between the programmable logic elements. Such program
`mable logic arrays are shown, for example, in Carter U.S.
`Pat. Nos. 4,642.487, 4,706,216, and 4,758,985, and in Free
`man U.S. Pat. No. 4,870,302.
`AS integrated circuit fabrication techniques progreSS, it
`becomes possible to put more and more programmable logic
`elements on a chip. AS the number of elements increases, it
`becomes important to improve the techniques used to inter
`connect them. For example, it is important to provide
`enough interconnection pathways between the program
`mable logic elements So that the capabilities of those ele
`ments can be fully utilized and So that complex logic
`functions (requiring concatenation of programmable logic
`elements) can be performed, without providing So many
`Such pathways that there is a wasteful excess of this type of
`resource. Similarly, as the number of programmable ele
`ments increases, the complexity of the logic which can be
`performed also increases. But this in turn tends to increase
`the complexity of the task of programming the circuit unless
`additional logical Structure is included in the circuit to help
`correspondingly structure the programming task.
`There is always room for further improvement, however,
`and there are Some situations in which the provision of
`additional or alternative types of interconnections between
`the logic modules would have benefits sufficient to justify
`the additional circuit and programming complexity. Such
`additional interconnection paths may be desirable for mak
`65
`ing frequently needed kinds of interconnections, for Speed
`ing certain kinds of interconnections, for allowing short
`
`45
`
`50
`
`55
`
`60
`
`

`

`3
`outputs of Several Such look up tables may be combined
`(e.g., by other similar look up tables) in any desired way to
`perform much more complex logic functions.
`Look up tables which are a good size for performing many
`elementary logic functions in programmable logic devices
`tend to be too large for performing the extremely simple
`functions required to provide two-input adders (including
`Subtracters) and various kinds of counters. For example,
`four-input look up tables are a very good size for general
`use, but are larger than necessary for use in the individual
`binary places of adders and counters. Nevertheless, adders
`and counters are very often required in digital logic. It is
`therefore wasteful to use four-input look up tables for adders
`and counters. This is especially So when fast carry logic is
`used because for each binary place one four-input look up
`table is required to provide the Sum out bit, and another
`four-input look table is required to provide the carry out bit.
`Neither of these look up tables is being fully utilized.
`Moreover, if large numbers of bit positions or places are
`required, the need to use two look up tables per bit position
`may exact a significant Speed penalty because of the exten
`Sive use which must be made of the interconnect circuitry to
`interconnect the large number of look up tables involved.
`In View of the foregoing, it is an object of this invention
`to provide improved ways of implementing adders
`(including Subtracters) and counters in programmable logic
`devices made up of programmable look up tables.
`It is a more particular object of this invention to provide
`programmable logic devices made up of look up tables in
`which adders and counters can be implemented more effi
`ciently and with leSS waste of look up table resources.
`It is still another more particular object of this invention
`to provide ways of achieving faster adders and counters in
`programmable logic devices made up of look up tables.
`SUMMARY OF THE INVENTION
`These and other objects of the invention are accomplished
`in accordance with the principles of the invention by pro
`Viding programmable logic array integrated circuits in which
`Signal conductors are interconnected not by relatively large
`and complex programmable interconnections, but by rela
`tively Small and Simple fixed interconnections to multiplex
`erS which can then be programmed to effect the desired
`interconnections. Instead of having a signal conductor which
`crosses Several other signal conductors programmably con
`nectable to each of those other conductors by programmable
`elements at or near the interSection, a simple non
`programmable transverse connection is made to each of
`those other conductors, and the transverse connections are
`applied in parallel to a multiplexer. The multiplexer can then
`be programmed to Select one of its inputs as its output. The
`output of the multiplexer can be an input to a programmable
`logic element, an output from the integrated circuit, or a lead
`which is programmably connectable to one or more of
`Several other conductors in the device.
`Another interconnection technique which can be advan
`tageously employed in accordance with the principles of this
`invention is to group the programmable logic elements into
`a plurality of mutually exclusive groups, each group having
`asSociated with it one or more conductors which can only be
`used to interconnect the elements in that group. In addition,
`there are other conductors which can be used to convey
`Signals between the groupS. Grouping the programmable
`logic elements in mutually exclusive (i.e., non-overlapping)
`groups helps to Simplify the task of programming the device
`by breaking the device down into Several discrete parts, each
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,926,036
`
`4
`of which is Smaller and more easily managed than the whole
`device. Providing Signal conductors which Serve only to
`interconnect the programmable logic elements in each group
`avoids tying up much longer conductors just to make Short
`interconnections between adjacent programmable logic ele
`ments. This helps to reduce the required number of long
`conductors.
`In the above-described arrangement in which the pro
`grammable logic elements are grouped and each group is
`uniquely associated with certain interconnection Signal
`conductors, each programmable logic element may be aug
`mented with a programmable output stage which can be
`used either to feed the output of that programmable logic
`element to conductors which go beyond the associated group
`or to the interconnect conductors of the associated group.
`Multiplexers can also be used in combination with pro
`grammable Signal conductor interconnections to allow cer
`tain of the conductors to be laid down more densely, to
`reduce the size of the interconnection array, and to reduce
`the capacitive loading on each output conductor of the array.
`Instead of one output conductor crossing a large number of
`parallel input conductors with a programmable interconnec
`tion at each interSection of the output conductor with the
`input conductors (which tends to force relatively wide
`spacing of the input conductors because of the relatively
`large size of the programmable interconnections), two Sub
`Stantially parallel output conductorS feeding a programma
`bly controlled output multiplexer are used. Each of these
`output conductorS has a programmable interconnection only
`with every other one of the input conductors, and the input
`conductors which are thus connectable to one of the output
`conductors are interdigitated with the input conductors
`which are connectable to the other one of the output con
`ductors. By thus spreading the programmable interconnec
`tions Somewhat parallel to the longitudinal axes of the input
`conductors, the input conductors can be placed more closely
`together, which may Save valuable Space on the integrated
`circuit. This technique can also be used and further enhanced
`to reduce the number of programmable elements required to
`control the programmable interconnections between the
`input and output conductors if desired. In particular, a Single
`programmable element can be used to control two
`interconnections, one of which is on one output conductor,
`and the other of which is on the other output conductor. The
`output multiplexer then makes the final Selection of the
`desired output Signal. Reducing the number of program
`mable elements in this way may be especially beneficial
`when the programmable elements are relatively large (e.g.,
`as compared to the Signal conductor interconnection ele
`ments they control). Indeed, it may be desirable to use more
`than two output Signal conductors feeding the programma
`bly controlled output multiplexer and to have each program
`mable element control one interconnection element on each
`of the more than two output conductors to still further reduce
`the required number of programmable elements.
`Furthermore, other objects of the invention are accom
`plished in accordance with the principles of this invention by
`providing programmable logic array integrated circuits
`which basically employ a highly modular structure of logic
`elements and logic element interconnection pathways, but
`which also have one or more of Several types of additional
`interconnection pathways for Such purposes as making inter
`connections locally without tying up resources in the general
`interconnection Structure. For example, Such local intercon
`nections may include carry chain interconnections between
`adjacent or nearby logic modules, or cascade logic connec
`tions between Such modules in order to allow concatenation
`
`

`

`5,926,036
`
`15
`
`45
`
`50
`
`25
`
`S
`of the logic in those modules without recourse to the general
`interconnection Structure. Where, as is preferred, the logic
`modules are grouped in logic array blocks (“LABS”) which
`are in turn arranged on the integrated circuit in rows and
`columns, these additional local interconnections may not
`only be provided between logic modules within a LAB, but
`also to logic modules in the LABs in another (typically
`adjacent) row and/or column.
`Alternative embodiments of LABs are disclosed. In one
`embodiment, a RAM-LAB which includes a memory block
`and control circuitry is disclosed. The memory block
`includes four columns of memory, each of which are divided
`into upper and lower portions. The control circuitry gener
`ates the necessary control signals to route the data and
`address information to the proper memory column in the
`memory block. The present invention provides for accessing
`the RAM-LAB directly by the user or via programming
`Software during the initialization process. In the present
`invention, a RAM-LAB can be accessed using the network
`of So-called global horizontal and Vertical conductors in
`addition to conductors associated with each RAM-LAB.
`In embodiments employing a network of So-called global
`horizontal and vertical conductors, interconnections
`between those conductors are preferably made through
`tri-State drivers rather than mere passive connections in
`order to boost Signals which may be required to travel
`relatively long distances through the circuit. Such drivers
`may alternatively or in addition be used on all logic module
`output signals which drive relatively long conductors on the
`circuit.
`In addition to the network of global horizontal and
`Vertical conductors typically used for making interconnec
`tions between all but relatively closely adjacent logic mod
`ules and connections to most of the input and output
`35
`terminals of the circuit, another auxiliary network of hori
`Zontal and vertical conductors (so-called universal fast
`conductors) may be provided for distributing certain widely
`used logic Signals. Such as clock and clear Signals throughout
`the circuit. For example, conductors in this universal fast
`40
`conductor network may be connectable to every logic mod
`ule in the circuit.
`Still other objects of the invention are accomplished in
`accordance with the principles of the invention by providing
`programmable logic array integrated circuit devices with
`RAM blocks, the columns of which can be connected in the
`usual first-in-first-out (“FIFO") chains of other memory cells
`on the device for programming and Verification with the
`other memory cells. Such programming and Verification of
`the RAM block is row by row, similar to the programming
`and Verification of the other memory cells. During use of the
`device to perform logic, the RAM block is disconnected
`from the FIFO chains, and the RAM becomes instead
`addressable by the other logic on the device for reading and
`Writing. This addressing is preferably based on both row and
`column selection, an