Programmable logic device including multipliers and configurations thereof to reduce resource utilization Number:7,142,010 from the United States Patent and Trademark Office (PTO) owispatent

Title: Programmable logic device including multipliers and configurations thereof to reduce resource utilization

Abstract: In a programmable logic device having dedicated multiplier circuitry, some of the scan chain registers normally used for testing the device are located adjacent input registers of the multipliers. Those scan chain registers are ANDed with the input registers, and can be loaded with templates of ones and zeroes. This allows, e.g., subset multiplication if the least significant bits are loaded with zeroes and the remaining bits are loaded with ones. The multipliers preferably are arranged in blocks with other components, such as adders, that allow them to be configured as finite impulse response (FIR) filters. In such configurations, the scan chain registers can be used to load filter coefficients, avoiding the use of scarce logic and routing resources of the device.

Patent Number: 7,142,010 Issued on 11/28/2006 to Langhammer,   et al.

---

Inventors:	Langhammer; Martin (Salisbury, GB), Hwang; Chiao Kai (Fremont, CA), Starr; Gregory (San Jose, CA)
Assignee:	Altera Corporation (San Jose, CA)
Appl. No.:	10/742,746
Filed:	December 19, 2003

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	10377962	Feb., 2003	6693455
	09955647	Sep., 2001	6556044

---

Current U.S. Class:	326/40 ; 326/39; 708/523; 708/625; 714/724; 714/725; 714/726
Current International Class:	H03K 19/177 (20060101); G01R 31/28 (20060101); G06F 7/52 (20060101)
Field of Search:	326/38-40 708/535,620,625,505,670 714/724-727

---

References Cited [Referenced By]

---

U.S. Patent Documents

	3473160		October 1969		Wahlstrom
	4799004		January 1989		Mori
	4839847		June 1989		Laprade
	4871930		October 1989		Wong et al.
	4912345		March 1990		Steele et al.
	4967160		October 1990		Quievy et al.
	4982354		January 1991		Takeuchi et al.
	4994997		February 1991		Martin et al.
	5122685		June 1992		Chan et al.
	5128559		July 1992		Steele
	5371422		December 1994		Patel et al.
	5381357		January 1995		Wedgwood et al.
	5483178		January 1996		Costello et al.
	5563819		October 1996		Nelson
	5636150		June 1997		Okamoto
	5646545		July 1997		Trimberger et al.
	5689195		November 1997		Cliff et al.
	5696708		December 1997		Leung
	5754459		May 1998		Telikepalli
	5761483		June 1998		Trimberger
	5777912		July 1998		Leung et al.
	5812562		September 1998		Baeg
	5825202		October 1998		Tavana et al.
	5874834		February 1999		New
	5880981		March 1999		Kojima et al.
	5931898		August 1999		Khoury
	5968196		October 1999		Ramamurthy et al.
	5991898		November 1999		Rajski et al.
	6064614		May 2000		Khoury
	6066960		May 2000		Pedersen
	6069487		May 2000		Lane et al.
	6091261		July 2000		De Lange
	6097988		August 2000		Tobias
	6107821		August 2000		Kelem et al.
	6130554		October 2000		Kolze et al.
	6157210		December 2000		Zaveri et al.
	6163788		December 2000		Chen et al.
	6167415		December 2000		Fischer et al.
	6175849		January 2001		Smith
	6215326		April 2001		Jefferson et al.
	6243729		June 2001		Staszewski
	6246258		June 2001		Lesea
	6279021		August 2001		Takano et al.
	6286024		September 2001		Yano et al.
	6314551		November 2001		Borland
	6321246		November 2001		Page et al.
	6323680		November 2001		Pedersen et al.
	6359468		March 2002		Park et al.
	6367003		April 2002		Davis
	6407576		June 2002		Ngai et al.
	6407694		June 2002		Cox et al.
	6480980		November 2002		Koe
	6483343		November 2002		Faith et al.
	6542000		April 2003		Black et al.
	6574762		June 2003		Karimi et al.
	6591283		July 2003		Conway et al.
	6600788		July 2003		Dick et al.
	6700581		March 2004		Baldwin et al.
	6728901		April 2004		Rajski et al.
	6745254		June 2004		Boggs et al.
	6904471		June 2005		Boggs et al.
	2002/0089348		July 2002		Langhammer
	2004/0064770		April 2004		Xin
	2004/0083412		April 2004		Corbin et al.
	2004/0193981		September 2004		Clark et al.

Foreign Patent Documents

	0 461 798		Dec., 1991		EP
	0 555 092		Aug., 1993		EP
	0 909 028		Apr., 1999		EP
	0 927 393		Jul., 1999		EP
	1 220 108		Jul., 2002		EP
	2 283 602		May., 1995		GB
	07-135447		May., 1995		JP
	WO 97/08606		Mar., 1997		WO
	WO 00/52824		Sep., 2000		WO
	WO01/13562		Feb., 2001		WO

Other References

Altera Corporation, "Implementing Multipliers in FLEX 10K EABs," Mar. 1996. cited by other . Xilinx, Inc., "Xilinx Unveils New FPGA Architecture to Enable High-Performance, 10 Million System Gate Designs," Jun. 22, 2000. cited by other . Xilinx, Inc., "Xilinx Announces DSP Algorithms, Tools and Features for Virtex-II Architecture," Nov. 21, 2000. cited by other . Xilinx, Inc., "Virtex-II 1.5V Field-Programmable Gate Arrays," module 2 of 4, Jan. 25, 2001. cited by other . Xilinx, Inc., "Virtex-II 1.5V Field-Programmable Gate Arrays," module 1 of 4, Apr. 2, 2001. cited by other . Xilinx, Inc., "Virtex-II 1.5V Field-Programmable Gate Arrays," Apr 2, 2001, module 2 of 4. cited by other . Altera Corporation, "Implementing Logic with the Embedded Array in FLEX 10K Devices," ver. 2.1, May 2001. cited by other . QuickLogic Corporation, "The QuickDSP Design Guide," revision B, Aug. 2001. cited by other . QuickLogic Corporation, "QuickDSP.TM. Family Data Sheet," revision B, Aug. 7, 2001. cited by other . Traika, C., "Embedded digital signal processor (DSP) modules in programmable logic devices (PLDs)," Elektronik, vol. 49, No. 14, Jul. 11, 2000, pp. 84-96. cited by other . Berg. B.L., et al."Designing Power and Area Efficient Multistage FIR Decimators with Economical Low Order Filters," ChipCenter Technical Note, Dec. 2001. cited by other . Gaffar, A.A., et al., "Floating-Point Bitwidth Analysis via Automatic Differentiation," IEEE Conference on Field Programmable Technology, Hong Kong, Dec. 2001. cited by other . Huang, J., et al., "Simulated Performance of 1000BASE-T Receiver with Different Analog Front End Designs," Proceedings of the 35th Asilomar Conference on Signals, Systems, and Computers, Nov. 4-7, 2001. cited by other . Lattice Semiconductor Corp, ORCA.RTM. FPGA Express.TM. Interface Manual; IsoLEVER.RTM. Version 3.0, 2002. cited by other . Lucent Technologies, Microelectronics Group,"Implementing and Optimizing Multipliers in ORCA.TM. FPGAs,", Application Note AP97-008FGPA, Feb. 1997. cited by other . Xiilnx, Inc., "A 1D Systolic FIR," copyright 1994-2002, downloaded from http://www.iro.umontreal.ca/.about.aboulham/F6221/Zilinx%20A%201D%20systo- lic%20FIR.htm. cited by other . Xilinx, Inc., "The Future of FPGA's," White Paper, available Nov. 14, 2005 for download from http://www.xilinx.com/prs.sub.--rls,5yrwhite.htm. cited by other . Valls, J., et al., "A Study About FPGA-Based Filters," Signal Processing Systems, 1998 , SIPS 98, 1998 IEEE Workshop, Oct. 10, 1998, pp. 192-201. cited by other.

Primary Examiner: Tan; Vibol
Attorney, Agent or Firm: Fish & Neave IP Group of Ropes & Gray LLP Ingerman; Jeffrey H.

---

Parent Case Text

---

This is a continuation of commonly-assigned U.S. patent application Ser. No. 10/377,962, filed Feb. 26, 2003, now U.S. Pat. No. 6,693,455, which is a continuation of U.S. patent application Ser. No. 09/955,647, filed Sep. 18, 2001, now U.S. Pat. No. 6,556,044.

---

Claims

---

What is claimed is:

1. A programmable logic device comprising: multiplier means; a plurality of scan chain register means for testing said programmable logic device, at least a portion of said plurality of scan chain register means being located adjacent said multiplier means; and input means for inputting data in said scan chain register means into said multiplier means.

2. The programmable logic device of claim 1 further comprising: a plurality of input means for inputting bits of multiplicands to said multiplier means; wherein: said at least a portion of said plurality of scan chain register means is adjacent said plurality of input means; said input means combines data in said input means with data in said scan chain register means for inputting into said multiplier means.

3. The programmable logic device of claim 2 wherein: said multiplier means is an m.times.n multiplier means for performing multiplication of an m bit number by an n bit number; said input means comprise: m input means for inputting m bits of said m-bit number to said multiplier means, and n input means for inputting n bits of said n-bit number to said multiplier means; and said plurality of scan chain register means includes at least m+n said scan chain register means.

4. The programmable logic device of claim 3 wherein said input means comprises AND means for ANDing data in said input means with data in said plurality of scan chain register means for input to said multiplier means.

5. The programmable logic device of claim 4 wherein: p of said m scan chain register means adjacent said m input means are loaded with p logic ones, and m-p of said m scan chain register means adjacent said m input means are loaded with m-p logic zeroes, where p<m; q of said n scan chain register means adjacent said n input means are loaded with q logic ones, and n-q of said n scan chain register means adjacent said n input means are loaded with n-q logic zeroes, where q<n; and said AND means ANDs data in said m input means with data in said m scan chain register means, and ANDs data in said n input means with data in said n scan chain register means; whereby: said m.times.n multiplier means is configured as a p.times.q multiplier means.

6. The programmable logic device of claim 5 wherein: said p logic ones are in p most significant ones of said m scan chain register means; and said m-p logic zeroes are in m-p least significant ones of said m scan chain register means.

7. The programmable logic device of claim 6 wherein: said q logic ones are in q most significant ones of said n scan chain register means; and said n-q logic zeroes are in n-q least significant ones of said n scan chain register means.

8. The programmable logic device of claim 5 wherein: said q logic ones are in q most significant ones of said n scan chain register means; and said n-q logic zeroes are in n-q least significant ones of said n scan chain register means.

9. The programmable logic device of claim 2 wherein said input means comprises AND means for ANDing data in said input means with data in said plurality of scan chain register means for input to said multiplier means.

10. The programmable logic device of claim 2 wherein: said plurality of input means comprises a plurality of input register means for inputting bits of multiplicands to said multiplier means; said at least a portion of said plurality of scan chain register means is adjacent said plurality of input register means; said input means combines data in said input register means with data in said scan chain register means for inputting into said multiplier means.

11. The programmable logic device of claim 10 wherein: said multiplier means is an m.times.n multiplier means for performing multiplication of an m-bit number by an n-bit number; said input register means comprise: m register means for inputting m bits of said m-bit number to said multiplier means, and n register means for inputting n bits of said n-bit number to said multiplier means; and said plurality of scan chain register means includes at least m+n said scan chain register means.

12. The programmable logic device of claim 11 wherein said input means comprises AND means for ANDing data in said input register means with data in said plurality of scan chain register means for input to said multiplier means.

13. The programmable logic device of claim 12 wherein: p of said m scan chain register means adjacent said m input register means are loaded with p logic ones, and m-p of said m scan chain register means adjacent said m input register means are loaded with m-p logic zeroes, where p<m; q of said n scan chain register means adjacent said n input register means are loaded with q logic ones, and n-q of said n scan chain register means adjacent said n input register means are loaded with n-q logic zeroes, where q<n; and said AND means ANDs data in said m input register means with data in said m scan chain register means, and ANDs data in said n input register means with data in said n scan chain register means; whereby: said m.times.n multiplier means is configured as a p.times.q multiplier means.

14. The programmable logic device of claim 13 wherein: said p logic ones are in p most significant ones of said m scan chain register means; and said m-p logic zeroes are in m-p least significant ones of said m scan chain register means.

15. The programmable logic device of claim 14 wherein: said q logic ones are in q most significant ones of said n scan chain register means; and said n-q logic zeroes are in n-q least significant ones of said n scan chain register means.

16. The programmable logic device of claim 13 wherein: said q logic ones are in q most significant ones of said n scan chain register means; and said n-q logic zeroes are in n-q least significant ones of said n scan chain register means.

17. The programmable logic device of claim 10 wherein said input means comprises AND means for ANDing data in said input register means with data in said plurality of scan chain register means for input to said multiplier means.

18. The programmable logic device of claim 1 wherein: said multiplier means comprises a first input for inputting bits of a first multiplicand and a second input for inputting bits of a second multiplicand; and said at least a portion of said plurality of scan chain register means is connected to one of said first and second input means of said multiplier means; whereby: data loaded into said at least a first portion of said plurality of scan chain register means after said testing represent at least one of said first and second multiplicands.

19. The programmable logic device of claim 18 wherein: said data representing said first multiplicand are substantially fixed during a plurality of multiplication operations.

20. The programmable logic device of claim 19 wherein: said at least a portion of said plurality of scan chain register means representing said first multiplicand is clocked by a separate clock means from others of said plurality of scan chain register means; whereby: said first multiplicand is kept substantially fixed by stopping said separate clock means.

21. The programmable logic device of claim 20 wherein said separate clock means is restarted to change said first multiplicand during operation of said programmable logic device.

22. The programmable logic device of claim 19 further comprising: a switch for separating said at least a portion of said plurality of scan chain register means representing said first multiplicand from others of said plurality of scan chain register means; whereby: said first multiplicand is kept substantially fixed by opening said switch.

23. The programmable logic device of claim 22 wherein said switch is closed to change said first multiplicand during operation of said programmable logic device.

24. The programmable logic device of claim 19 comprising: a plurality of said multiplier means arranged in logic block means, each said multiplier means having one said first multiplicand and one said second multiplicand; said logic block means further comprising: a plurality of adder means for accumulating outputs of said plurality of said multiplier means.

25. The programmable logic device of claim 24 wherein: said multiplier means and said adder means in said logic block means are adapted to be configured to form finite impulse response filter means; and each said first multiplicand represents a coefficient of said finite impulse response filter means.

26. The programmable logic device of claim 25 wherein: said logic block means comprises four said multiplier means and three said adder means: a first of said adder means adds outputs of a first and second of said multiplier means; a second of said adder means adds outputs of a third and fourth of said multiplier means; and a third of said adder means adds outputs of said first and second adder means.

27. The programmable logic device of claim 26 further comprising a plurality of register means for registering data in said finite impulse response filter means.

28. The programmable logic device of claim 27 wherein said plurality of register means are chained on an input to said logic block means, each said register providing an output for input to one said multiplier means.

29. The programmable logic device of claim 25 wherein said logic block means comprises a number of said multiplier means and a number of said adder means equal to said number of said multiplier means, each said adder means adding an output of one said multiplier means to a previous sum.

30. The programmable logic device of claim 29 wherein a first said previous sum is an input to said logic block means.

31. The programmable logic device of claim 30 further comprising a plurality of register means for registering data in said finite impulse response filter means.

32. The programmable logic device of claim 31 wherein each said register means registers an output of one of said adder means, each said registered output forming one of said previous sums.

33. The programmable logic device of claim 29 further comprising a plurality of register means for registering data in said finite impulse response filter means.

34. The programmable logic device of claim 33 wherein each said register means registers an output of one of said adder means, each said registered output forming one of said previous sums.

35. The programmable logic device of claim 19 wherein register means in said at least a first portion of said plurality of scan chain register means representing said first multiplicand are prevented from further input after said loading.

36. The programmable logic device of claim 35 wherein said register means in said at least a first portion of said plurality of scan chain register means representing said first multiplicand are prevented from further input after said loading by grounding of a first clock means.

37. The programmable logic device of claim 36 wherein register means in said at least a first portion of said plurality of scan chain register means representing said second multiplicand receive further input after said loading by clock meansing of a second clock means different from said first clock means.

38. The programmable logic device of claim 35 wherein said register means in said at least a portion of said plurality of scan chain register means representing said first multiplicand are prevented from further input after said loading by opening of a connection to said register means representing said first multiplicand.

39. The programmable logic device of claim 38 wherein said register means in said at least a first portion of said plurality of scan chain register means representing said second multiplicand continue to receive further input after said opening of said connection.

40. The programmable logic device of claim 39 comprising: a plurality of said multiplier means arranged in logic block means, each said multiplier means having one said first multiplicand and one said second multiplicand; said logic block means further comprising: a plurality of adder means for accumulating outputs of said plurality of said multiplier means.

41. The programmable logic device of claim 40 wherein: said multiplier means and said adder means in said logic block means are adapted to be configured to form finite impulse response filter means; and each said first multiplicand represents a coefficient of said finite impulse response filter means.

42. The programmable logic device of claim 41 wherein: said logic block means comprises four said multiplier means and three said adder means: a first of said adder means adds outputs of a first and second of said multiplier means; a second of said adder means adds outputs of a third and fourth of said multiplier means; and a third of said adder means adds outputs of said first and second adder means.

43. The programmable logic device of claim 42 further comprising a plurality of register means for registering data in said finite impulse response filter means.

44. The programmable logic device of claim 43 wherein said plurality of register means are chained on an input to said logic block means, each said register providing an output for input to one said multiplier means.

45. The programmable logic device of claim 41 wherein said logic block means comprises a number of said multiplier means and a number of said adder means equal to said number of said multiplier means, each said adder means adding an output of one said multiplier means to a previous sum.

46. The programmable logic device of claim 45 wherein a first said previous sum is an input to said logic block means.

47. The programmable logic device of claim 46 further comprising a plurality of register means for registering data in said finite impulse response filter means.

48. The programmable logic device of claim 47 wherein each said register means registers an output of one of said adder means, each said registered output forming one of said previous sums.

49. The programmable logic device of claim 45 further comprising a plurality of register means for registering data in said finite impulse response filter means.

50. The programmable logic device of claim 49 wherein each said register means registers an output of one of said adder means, each said registered output forming one of said previous sums.

51. The programmable logic device of claim 41 further comprising a plurality of register means for registering data in said finite impulse response filter means.

52. A programmable logic device comprising: a plurality of multiplier means arranged in logic block means, each said multiplier means having a first multiplicand and a second multiplicand; said logic block means further comprising: a plurality of adder means for accumulating outputs of said plurality of multiplier means; wherein: said multiplier means and said adder means in said logic block means are adapted to be configured to form finite impulse response filter means.

53. The programmable logic device of claim 52 wherein: said logic block means comprises four said multiplier means and three said adder means: a first of said adder means adds outputs of a first and second of said multiplier means; a second of said adder means adds outputs of a third and fourth of said multiplier means; and a third of said adder means adds outputs of said first and second adder means.

54. The programmable logic device of claim 53 further comprising a plurality of register means for registering data in said finite impulse response filter means.

55. The programmable logic device of claim 54 wherein said plurality of register means are chained on an input to said logic block means, each said register means providing an output for input to one said multiplier means.

56. The programmable logic device of claim 52 wherein said logic block means comprises a number of said multiplier means and a number of said adder means equal to said number of said multiplier means, each said adder means adding an output of one said multiplier means to a previous sum.

57. The programmable logic device of claim 56 wherein a first said previous sum is an input to said logic block means.

58. The programmable logic device of claim 57 wherein said input to said logic block means is an output of another said logic block means.

59. The programmable logic device of claim 57 further comprising a plurality of register means for registering data in said finite impulse response filter means.

60. The programmable logic device of claim 59 wherein each said register means registers an output of one of said adder means, each said registered output forming one of said previous sums.

61. The programmable logic device of claim 52 further comprising a plurality of register means for registering data in said finite impulse response filter means.

62. The programmable logic device of claim 52 wherein each said first multiplicand represents a coefficient of said finite impulse response filter means.

63. A digital processing system comprising: processing means; memory means coupled to said processing means; and a programmable logic device as defined in claim 1 coupled to the processing means and the memory means.

64. A printed circuit board on which is mounted a programmable logic device as defined in claim 1.

65. The printed circuit board defined in claim 64 further comprising: memory means mounted on the printed circuit board and coupled to the programmable logic device.

66. The printed circuit board defined in claim 65 further comprising: memory means mounted on the printed circuit board and coupled to the memory.

67. The printed circuit board defined in claim 66 further comprising: processing means mounted on the printed circuit board and coupled to the memory means.

68. A digital processing system comprising: processing means; a memory coupled to said processing means; and a programmable logic device as defined in claim 52 coupled to the processing means and the memory.

69. A printed circuit board on which is mounted a programmable logic device as defined in claim 52.

70. The printed circuit board defined in claim 69 further comprising: a memory mounted on the printed circuit board and coupled to the programmable logic device.

71. The printed circuit board defined in claim 70 further comprising: memory means mounted on the printed circuit board and coupled to the memory.

72. The printed circuit board defined in claim 71 further comprising: processing means mounted on the printed circuit board and coupled to the memory means.

73. A programmable logic device comprising: a plurality of scan chain register means; and function block means configurable as finite impulse response filter means; said function block means comprising: a plurality of multiplier means, each of said multiplier means having a respective first input means for data to be filtered by said finite impulse response filter means, and a respective second input means for a respective coefficient of said finite impulse response filter means; a plurality of adder means for accumulating outputs of said multiplier means; and a plurality of filter register means, each of said filter register means being operatively connected to at least one of (a) one of said multiplier means, and (b) one of said adder means; wherein: each of said respective second input means is connected to a respective one of said scan chain register means that is adjacent said function block means; whereby: coefficients for said finite impulse response filter means are loaded via said scan chain register means.

74. The programmable logic device of claim 73 wherein: respective ones of said scan chain register means are connected to respective ones of said second input means; and said coefficients are stored in said respective ones of said scan chain register means.

75. The programmable logic device of claim 73 further comprising coefficient storage register means connected to respective ones of said second input means; wherein: respective ones of said scan chain register means are located adjacent said coefficient storage register means; and said coefficients are loaded into said coefficient storage register means from said respective ones of said scan chain register means.

76. The programmable logic device of claim 73 wherein: said filter register means are connected to said respective first input means; and said adder means add together outputs of all of said multiplier means; whereby: said function block means is configured as a Direct Form II finite impulse response filter means.

77. The programmable logic device of claim 76 wherein: said filter register means form a serial chain of filter register means connected to a single data source, each of said filter register means having an output; and said output of each said filter register means is connected to said first input of a respective one of said multiplier means.

78. The programmable logic device of claim 77 comprising: first, second, third and fourth ones of said filter register means; first, second, third and fourth ones of said multiplier means; and first, second and third ones of said adder means; wherein: each of said multiplier means and said adder means has a first input, a second input and an output; said output of said first filter register means is connected to said first input of said first multiplier means; said output of said second filter register means is connected to said first input of said second multiplier means; said output of said third filter register means is connected to said first input of said third multiplier means; said output of said fourth filter register means is connected to said first input of said fourth multiplier means; said outputs of said first and second multiplier means are connected to said first and second inputs of said first adder means; said outputs of said third and fourth multiplier means are connected to said first and second inputs of said second adder means; said outputs of said first and second adder means are connected to said first and second inputs of said third adder means; and said output of said third adder means is output of said Direct Form II finite impulse response filter means.

79. The programmable logic device of claim 73 wherein: each of said multiplier means and said adder means has an output; each of said adder means adds an output of one said multiplier means to another datum; and a respective one of said filter register means is connected to said output of each respective one of said adder means; whereby: said function block means is configured as a Direct Form I finite impulse response filter means.

80. The programmable logic device of claim 79 wherein all of said first inputs of said respective multiplier means are connected to a single data source.

81. The programmable logic device of claim 80 further comprising: first, second, third and fourth ones of said filter register means; first, second, third and fourth ones of said multiplier means; and first, second, third and fourth ones of said adder means; wherein: for said first one of said adder means, said another datum comprises one of (a) an external input, and (b) ground; for each of said second, third and fourth ones of said adder means, said another datum comprises contents of a respective one of said first, second and third filter register means; and output of said Direct Form I finite impulse response filter means comprises contents of said fourth one of said filter register means.

82. A method of programming a programmable logic device, said programmable logic device having scan chain register means and having function block means configurable as finite impulse response filter means, at least some of said scan chain register means being adjacent said function block means, said method comprising: testing said programmable logic device by clocking test data through said scan chain register means; and after completion of said testing, clocking finite impulse response filter means coefficients into said at least some of said scan chain register means.

---

Description

---

BACKGROUND OF THE INVENTION

This invention relates to programmable logic devices that include dedicated multipliers, and more particularly to such programmable logic devices in which the multipliers are used in particular configurations that reduce resource utilization.

It has become more common to provide multiplier circuits on programmable logic devices, rather than requiring users of such devices to construct multipliers from the available programmable logic resources. However, a multiplier circuit consumes a relatively large area, and its inputs can consume significant routing resources.

For example, multipliers are provided to multiply m bits by n bits--e.g., 18.times.18 bits (frequently m=n). However, a user of the programmable logic device might have need of a p-bit by q-bit multiplier, where p and q are chosen by the user at the time of programming and may be different in every case, and p<m and q<n. This can be accomplished during programming by pre-loading or padding the unused bits with zeroes. However, the inputs to those unused bits have to be driven by a source, and the source has to be routed to the inputs. Therefore, padding the unused bits consumes resources which then are unavailable for other uses, even though the inputs remain constant throughout device operation.

Alternatively, additional registers could be provided and ANDed with the multiplier input registers, and each additional register could be set to either one (this would be the case for the most significant multiplier bits, which will be used) or zero (in the case of the least significant multiplier bits, which will not be used). Whether a particular register was set to zero or one could be controlled by configuration bits. While this consumes fewer resources than routing the zeroes directly to the less significant multiplier inputs, it still requires providing additional registers and configuration bits.

In another example, a multiplier might be used in a configuration in which one of its inputs is a constant coefficient, again consuming routing resources for the constant coefficient. Indeed, one such use is in a finite impulse response (FIR) filter, which requires several multipliers, compounding the use of routing resources. Moreover, in such a filter, the outputs of the various multipliers must be accumulated by a plurality of adders, consuming further routing resources to direct the various products to the adders and the sums to other adders.

It would be desirable to be able to provide programmable logic devices with multiplier circuits, where those multiplier circuits are configured to reduce resource utilization.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide programmable logic devices with multiplier circuits, where those multiplier circuits are configured to reduce resource utilization.

In accordance with the present invention, there is provided a programmable logic device comprising a multiplier circuit, which may be that described in commonly-assigned U.S. Pat. No. 6,628,140, which is hereby incorporated by reference in its entirety. The programmable logic device includes a plurality of scan chain registers for testing purposes, and at least a portion of the plurality of scan chain registers are located adjacent the multiplier circuit. Input circuitry is provided for using data in the scan chain registers to modify input data to the multiplier circuit.

In accordance with one aspect of the invention, the multiplier circuit, which can multiply two numbers having m and n bits, respectively (frequently, m=n), can be configured to multiply instead p.times.q bits, where p<m and q<n. (frequently, p=q). This is known as subset multiplication, and the multiplier is known as a subset multiplier. To avoid wasting routing resources to pad the inputs with zeroes to account for the missing m-p bits and the missing n-q bits, the scan chains normally provided for testing of the programmable logic device are used.

Scan chains typically are provided throughout a programmable logic device for testing purposes. After the device is manufactured, a predetermined pattern of ones and zeroes is clocked through the scan chains and the progression of that pattern through the chain, which has registers throughout all parts of the device, is checked. If there is any deviation from the input pattern, that indicates a potential manufacturing flaw, which can be isolated by determining where in the chain the pattern becomes corrupted.

In accordance with this aspect of the invention, scan chain registers adjacent the multiplier inputs are ANDed with the multiplier inputs. The scan chain registers corresponding to the least significant m-p and n-q bits of the multiplier inputs are loaded, after device testing, with zeroes, while the p and q most significant bits are loaded with ones. Because no further data are input to the scan chain registers, they retain the values loaded into them throughout device operation. ANDing the scan chain registers, loaded with ones and zeroes as described above, with the multiplier inputs has the same effect as padding the least significant bits with zeroes, but without using routing resources. Thus, the routing resources connected to the least significant bits of the multiplier inputs can be used for other functions, because it does not matter for multiplication purposes what values appear in those bits, which will always be ANDed with zeroes. Because the remaining bits of the scan chain registers are loaded with ones, the values in the most significant bits of the multiplier inputs pass through the AND operation to the multiplier. Normally, the multiplier inputs are registered (synchronous input), and the scan chain registers are ANDed with the input registers. Sometimes, however, the multiplier inputs are asynchronous and not registered, in which case the scan chain registers are ANDed with the inputs themselves.

In accordance with another aspect of the present invention, there is provided a programmable logic device comprising a plurality of multiplier circuits arranged in a logic block. The logic block further comprises a plurality of adders for accumulating outputs of the plurality of multiplier circuits, as described in commonly-assigned U.S. Pat. No. 6,538,470, which is hereby incorporated by reference in its entirety. The multipliers and the adders in the logic block are configured for various uses, including formation of a finite impulse response filter.

In accordance with this aspect of the invention, the finite impulse response (FIR) filter may be a "Direct Form I" FIR filter or a "Direct Form II" FIR filter. Either type of FIR filter requires, in addition to the multipliers and adders, registers for registering either input data (samples) or intermediate data, with the number of registers preferably equaling the number of multipliers in the FIR filter. In the case of a Direct Form I FIR filter, the registers are at the outputs of the multipliers, while in a Direct Form II FIR filter, the registers are at the inputs of the multipliers.

In either type of FIR filter, one of the inputs to each multiplier sometimes is a coefficient fixed at the time of programming and specific to the use that will be made of the filter, although in other cases, such as in an adaptive FIR filter, the coefficients may vary over time. Because the coefficient may be fixed, it would be a waste of routing resources to consume those resources with the values for the coefficients. Therefore, as discussed above in connection with subset multipliers, in accordance with this aspect of the invention, the scan chain registers that are ANDed with the multiplier coefficient inputs are loaded with the filter coefficients after testing of the device is complete.

In a variant of this aspect of the invention, the scan chain registers are also used for the data (sample) inputs to the FIR filter. This is accomplished by ANDing other scan chain registers to the other inputs (or input registers) of each multiplier, and then clocking data through the scan chain during use to provide the filter sample inputs. If this variant is used, then a way must be provided to prevent the coefficient data in the scan chain registers, which are supposed to be fixed, from being clocked through the scan chain as the input sample data are clocked through. This is preferably accomplished using one or both of two methods.

The first method to prevent coefficient data from being clocked through the scan chain as the input sample data are clocked through is to provide in the scan chain one or more switches or links that can be opened after the coefficient data are loaded into the appropriate scan chain registers opening the link or switch would then isolate those registers from the remainder of the scan chain, so that the input sample data are not clocked through into the coefficient registers. This requires arranging the scan chain so that all of the scan chain registers to be used for coefficient data are downstream of any scan chain registers to be used for input sample data.

The second method to prevent coefficient data from being clocked through the scan chain as the input sample data are clocked through is to provide a first coefficient clock for those scan chain registers that are to be used for coefficient input, and a second separate data or sample clock for the other scan chain registers, including those to be used for sample data input. The two clocks would be connected, or run in synchrony, during "normal" scan chain testing operation and clocking in of the coefficient data. The coefficient clock would then be disconnected from the sample data clock or simply turned off, and preferably grounded, to prevent alteration of the coefficient data even though the coefficient registers remain connected to the scan chain and data is being clocked through any registers clocked by the data or sample clock. This still requires arranging the scan chain registers in the correct order with foreknowledge of which will be used for coefficients, so that all coefficient registers are downstream from all sample data registers, because even though the coefficient registers are not removed from the chain as in the previous embodiment, no data will be able to be clocked through the coefficient registers to downstream sample data registers. This also requires using the same foreknowledge to connect the correct clock to each scan chain register. This second method may be, and preferably is, used in conjunction with the first method.

For some applications, such as in adaptive FIR filters, it may be desirable or necessary to change coefficients on the fly, or at least occasionally, during operation of the device. The use of scan chains to load coefficients facilitates such on-the-fly changes. Thus, in an embodiment where the coefficients are loaded using a separate scan chain with its own clock, the clock can be restarted whenever it is desired to change the coefficients. In an embodiment where the samples and coefficients are loaded using the same scan chain, which is then broken after the coefficients are loaded, when it is desired to change the coefficients the break must be closed (as by a switch). In the latter embodiment, there will be a period, while the new coefficient data propagates through the sample portion of the chain, `that the filter output is not meaningful.

Separate and apart from the use of scan chain registers as coefficient and/or sample data inputs to a FIR filter, the logic block described above including multipliers and adders that can be configured as a FIR filter includes the routing necessary to connect those elements as a FIR filter, relieving the load on the general routing of the programmable logic device. Thus, the logic block, which may be referred to as a multiplier-accumulator (MAC) block or, because it is frequently used in digital signal processing, a DSP block, includes multipliers, adders, registers in the two different locations required for the two different types of FIR filters, as discussed below, and multiplexers for selecting between the two configurations, again as discussed below.

BRIEF DESCRIPTION OF THE DRAWINGS

The above and other objects and advantages of the invention will be apparent upon consideration of the following detailed description, taken in conjunction with th