Method and apparatus for generating deterministic, non-repeating, pseudo-random addresses

• US 20040006680A1
• Filed: 06/28/2002
• Published: 01/08/2004
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Duncan, Kevin
• Granted Patent: US 6,865,660 B2
• Time in Patent Office: Days
• US Class Current: 711/219
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/586 using an integer algorithm, e.g. using linear congruential method
• CPC Class Codes: G11C 29/10 Test algorithms, e.g. memory scan [MScan] algorithms; Test patterns, e.g. checkerboard patterns
• CPC Class Codes: G11C 29/56 External testing equipment for static stores, e.g. automatic test equipment [ATE]; Interfaces therefor
• CPC Class Codes: G11C 29/56004 Pattern generation

Abstract

A system and method for rapidly generating a series of non-repeating, deterministic, pseudo-random addresses is disclosed. A deterministic, pseudo-random number generator is implemented in hardware. Once a number in a pseudo-random sequence is generated, a pattern eliminator alters the number to remove any pattern existing in the low order bits. The number may then be combined with an offset and a base to form a memory address for testing a memory device. The generated memory address is output directly to the memory device being tested.

Claims

1. A method for testing a memory circuit, the method comprising:

multiplying a first number in a sequence of deterministic pseudo-random numbers by a multiplier;

discarding all of the product of said act of multiplying except for a first plurality of low order bits representing a portion of said product, said first plurality of low order bits also representing a first memory address; and

testing a portion of said memory circuit represented by said first memory address.

2. The method of claim 1 further comprising:

multiplying said first plurality of low order bits by said multiplier;

discarding all of the product of said first plurality of low order bits and said multiplier except for a second plurality of low order bits, said second plurality of low order bits representing a second memory address; and

testing a portion of said memory circuit represented by said second memory address.

3. The method of claim 1 further comprising eliminating a pattern existing in said first plurality of low order bits.

4. The method of claim 1, wherein said act of discarding comprises discarding one-half of the bits representing said product.

5. The method of claim 4, wherein said act of discarding comprises discarding the upper 18 bits of said product and retaining the lower 18 bits of said product.

6. A method for testing a memory circuit, the method comprising:

generating a first number in a sequence of deterministic pseudo-random numbers, said first number representing a first portion of a first address within said memory circuit to be tested;

combining said first address portion with a second address portion to form said first address; and

testing a portion of said memory circuit represented by said first address.

7. The method of claim 6, wherein said act of generating comprises:

multiplying an initial value by a multiplier and

discarding all bits representing the product of said act of multiplying except for a first plurality of low order bits, said first plurality of low order bits representing said first number in said sequence of deterministic pseudo-random numbers.

8. The method of claim 7, wherein said act of generating further comprises:

multiplying said first number in said sequence by said multiplier; and

discarding all bits representing the product of said first number in said sequence and said multiplier except for a second plurality of low order bits, said second plurality of low order bits representing a second number in said sequence of deterministic pseudo-random numbers.

9. The method of claim 7, wherein said act of multiplying comprises multiplying an 18-bit initial value by an 18-bit multiplier.

10. The method of claim 9, wherein said act of discarding comprises discarding the 18 most significant bits of said product and retaining the 18 least significant bits of said product.

11. The method of claim 10, wherein said act of multiplying comprises multiplying 18 bits representing said first number by an 1

12. The method of claim 11, wherein said act of discarding comprises discarding the 18 most significant bits of the product of said act of multiplying and retaining the 18 least significant bits of said product.

13. A method for forming a sequence of memory addresses, the method comprising:

multiplying an initial value by a multiplier;

discarding all of the product of said first multiplying operation except for a first plurality of low order bits;

forwarding said first plurality of low order bits to a memory address builder for forming a first memory address;

multiplying said first plurality of low order bits by said multiplier;

discarding all of the product of said second multiplying operation except for a second plurality of low order bits; and

forwarding said second plurality of low order bits to said memory address builder for forming a second memory address.

14. The method of claim 13, wherein said first multiplying operation further comprises multiplying a first plurality of bits representing said initial value by a plurality of bits representing a value of said multiplier.

15. The method of claim 14, wherein said first multiplying operation further comprises multiplying 18 bits representing said initial value by 18 bits representing said multiplier.

16. The method of claim 13, wherein said first discarding operation further comprises discarding one-half of the bits representing the product of said first multiplying operation.

17. The method of claim 16, wherein said first discarding operation further comprises discarding 18 most significant bits of 36 bits representing the product.

18. The method of claim 13, wherein said first forwarding operation further comprises forwarding said first plurality of low order bits to a pattern eliminator for eliminating a pattern in said first plurality of low order bits.

19. The method of claim 18, wherein said first forwarding operation further comprises forwarding said first plurality of low order bits to an address assembler for assembling the memory address.

20. The method of claim 19, wherein said act of assembling comprises:

receiving a third plurality of bits at said address assembler, said third plurality of bits representing a predetermined base of said memory address; and

combining said first plurality of low order bits with said third plurality of bits, thereby forming said first memory address.

21. The method of claim 20, wherein said act of combining further comprises:

receiving an offset value at said address assembler, said offset value specifying the relative locations of said base and said first plurality of low order bits in said memory address.

22. The method of claim 18, wherein said act of eliminating comprises removing bits 0 and 1 from said first plurality of low order bits.

23. The method of claim 18, wherein said act of eliminating comprises hard wiring two bits of said first plurality of low order bits other than bits 0 and 1 into bits 0 and 1.

24. The method of claim 18, wherein said act of eliminating comprises:

performing an exclusive OR operation on 4 bits other than bits 0 through 3 of said first plurality of low order bits; and

inverting one of bits 0 and 1 depending upon a result of said performing operation.

25. The method of claim 24, wherein said act of performing further comprises:

performing an exclusive OR operation on bits 4 through 7 of said first plurality of low order bits;

determining a result of said performing operation is “

0”

;

determining bit 1 of said initial value was a “

0”

; and

inverting bit 1 of the first plurality of low order bits.

26. The method of claim 24, wherein said act of performing further comprises:

performing an exclusive OR operation on bits 4 through 7 of said first plurality of low order bits;

determining a result of said performing operation is “

1”

;

determining bit 1 of said initial value was a “

0”

; and

inverting bit 0 of the first plurality of low order bits.

27. The method of claim 24, wherein said act of performing further comprises:

performing an exclusive OR operation on bits 4 through 7 of said first plurality of low order bits;

determining a result of said performing operation is “

0”

;

determining bit 1 of said initial value was a “

1”

; and

inverting bit 0 of the first plurality of low order bits.

28. The method of claim 24, wherein said act of performing further comprises:

performing an exclusive OR operation on bits 4 through 7 of said first plurality of low order bits;

determining a result of said performing operation is “

1”

;

determining bit 1 of said initial value was a “

1”

; and

inverting bit 1 of said first plurality of low order bits.

29. The method of claim 13, wherein said second multiplying operation comprises:

feeding back said first plurality of low order bits into a multiplier circuit in addition to forwarding said first plurality of low order bits to said memory address builder.

30. A system for forming a sequence of memory addresses, the system comprising:

a pseudo-random number generator for generating a first plurality of bits representing a first pseudo-random number in a sequence of deterministic pseudo-random numbers; and

an address builder coupled to an output of said pseudo-random number generator for receiving said first plurality of bits and combining said first plurality of bits with a second plurality of bits, such that said combined first and second plurality of bits form a first memory address.

31. The system of claim 30, wherein said generator comprises:

a multiplier for multiplying a predetermined initial value by a predetermined multiplier, thereby generating a first product, said multiplier also being configured to discard all bits of said first product except for a first plurality of low order bits representing said first pseudo-random number.

32. The system of claim 31 further comprising a feedback loop from an output of said generator to an input of said generator for multiplying said first plurality of low order bits by said predetermined multiplier value, thereby generating a second product, said multiplier being configured to discard all bits of said second product except for a second plurality of low order bits representing a second number in said sequence of deterministic pseudo-random numbers.

33. The system of claim 31, wherein said address builder further comprises:

a pattern eliminator configured to receive at least a portion of said first plurality of low order bits and to remove a pattern that exists in said portion.

34. The system of claim 31, wherein said address builder further comprises:

a second input for receiving a predetermined base value, said predetermined base value being represented by said second plurality of bits.

35. The system of claim 34, wherein said address builder further comprises:

a third input for receiving a predetermined offset value, said predetermined offset value specifying the relative positions within each of said memory addresses of said base value and said first pseudo-random number.

36. The system of claim 34, wherein said address builder further comprises:

an address assembler having a first input for receiving said first plurality of low order bits and a second input for receiving said base value, said address assembler combining said first plurality of low order bits with said base value to form said first memory address.

37. The system of claim 35, wherein said address builder further comprises:

an address assembler having a first input for receiving said first plurality of low order bits, a second input for receiving said base value, and a third input for receiving said offset value, said address assembler combining said first plurality of low order bits with said base value according to said offset value so as to form said first memory address.

38. The system of claim 30, wherein said system is contained on a memory card.

39. The system of claim 31, wherein said multiplier comprises a programmable logic circuit.

40. The system of claim 38, wherein said memory card is a PCI card.

41. The system of claim 38, wherein said memory card is a PCMCIA card.

42. A system for forming a memory address, the system comprising:

a pseudo-random number generator for generating a first plurality of bits representing a first pseudo-random number in a sequence of deterministic pseudo-random numbers, said first pseudo-random number representing at least a portion of a first memory address; and

a pattern eliminator coupled to said pseudo-random number generator and configured to receive at least a portion of said first plurality of low order bits and to remove a pattern that exists in said portion.

43. A memory card containing a system for forming a memory address, the system comprising:

a pseudo-random number generator for generating a first plurality of bits representing a first pseudo-random number in a sequence of deterministic pseudo-random numbers; and

an address builder coupled to an output of said pseudo-random number generator for receiving said first plurality of bits and combining said first plurality of bits with a second plurality of bits, such that said combined first and second plurality of bits form a first memory address.

44. The memory card of claim 43, wherein said generator comprises:

a multiplier for multiplying a predetermined initial value by a predetermined multiplier, thereby generating a first product, said multiplier also being configured to discard all bits of said first product except for a first plurality of low order bits representing said first pseudo-random number.

45. The memory card of claim 44 further comprising a feedback loop from an output of said generator to an input of said generator for multiplying said first plurality of low order bits by said predetermined multiplier value, thereby generating a second product, said multiplier being configured to discard all bits of said second product except for a second plurality of low order bits representing a second number in said sequence of deterministic pseudo-random numbers.

46. The memory card of claim 44, wherein said address builder further comprises:

a pattern eliminator configured to receive at least a portion of said first plurality of low order bits and to remove a pattern that exists in said portion.

47. The memory card of claim 44, wherein said address builder further comprises:

a second input for receiving a predetermined base value, said predetermined base value being represented by said second plurality of bits.

48. The memory card of claim 47, wherein said address builder further comprises:

a third input for receiving a predetermined offset value, said predetermined offset value specifying the relative positions within each of said memory addresses of said base value and said first pseudo-random number.

49. The memory card of claim 47, wherein said address builder further comprises:

an address assembler having a first input for receiving said first plurality of low order bits and a second input for receiving said base value, said address assembler combining said first plurality of low order bits with said base value to form said first memory address.

50. The memory card of claim 48, wherein said address builder further comprises:

an address assembler having a first input for receiving said first plurality of low order bits, a second input for receiving said base value, and a third input for receiving said offset value, said address assembler combining said first plurality of low order bits with said base value according to said offset value so as to form said first memory address.

51. The memory card of claim 43, wherein said memory card is a PCI card.

52. The memory card of claim 43, wherein said memory card is a PCMCIA card.

53. The memory card of claim 43, wherein said multiplier comprises a programmable logic circuit.

54. A memory card containing a system for forming a memory address, the system comprising:

a pseudo-random number generator for generating a first plurality of bits representing a first pseudo-random number in a sequence of deterministic pseudo-random numbers, said first pseudo-random number representing at least a portion of a first memory address; and

a pattern eliminator coupled to said pseudo-random number generator and configured to receive at least a portion of said first plurality of low order bits and to remove a pattern that exists in said portion.

55. A processor system, comprising:

a central processing unit;

a memory card coupled to said processor, said memory card containing a system for forming a memory address, the system comprising;

a pseudo-random number generator for generating a first plurality of bits representing a first pseudo-random number in a sequence of deterministic pseudo-random numbers; and

an address builder coupled to an output of said pseudo-random number generator for receiving said first plurality of bits and combining said first plurality of bits with a second plurality of bits, such that said combined first and second plurality of bits form a first memory address.

56. The processor system of claim 55, wherein said generator comprises:

a multiplier for multiplying a predetermined initial value by a predetermined multiplier, thereby generating a first product, said multiplier also being configured to discard all bits of said first product except for a first plurality of low order bits representing said first pseudo-random number.

57. The processor system of claim 56 further comprising a feedback loop from an output of said generator to an input of said generator for multiplying said first plurality of low order bits by said predetermined multiplier, thereby generating a second product, said multiplier being configured to discard all bits of said second product except for a second plurality of low order bits representing a second number in said sequence of deterministic pseudo-random numbers.

58. The processor system of claim 56, wherein said address builder further comprises:

a pattern eliminator configured to receive at least a portion of said first plurality of low order bits and to remove a pattern that exists in said portion.

59. The processor system of claim 56, wherein said address builder further comprises:

a second input for receiving a predetermined base value, said predetermined base value being represented by said second plurality of bits.

60. The processor system of claim 59, wherein said address builder further comprises:

a third input for receiving a predetermined offset value, said predetermined offset value specifying the relative positions within each of said memory addresses of said base value and said first pseudo-random number.

61. The processor system of claim 59, wherein said address builder further comprises:

an address assembler having a first input for receiving said first plurality of low order bits and a second input for receiving said base value, said address assembler combining said first plurality of low order bits with said base value to form said first memory address.

62. The processor system of claim 60, wherein said address builder further comprises:

an address assembler having a first input for receiving said first plurality of low order bits, a second input for receiving said base value, and a third input for receiving said offset value, said address assembler combining said first plurality of low order bits with said base value according to said offset value so as to form said first memory address.

63. The processor system of claim 55, wherein said memory card is a PCI card.

64. The processor system of claim 55, wherein said memory card is a PCMCIA card.

65. The processor system of claim 55, wherein said multiplier comprises a programmable logic circuit.

66. A processor system, comprising:

a central processing unit;

a memory card coupled to said processor, said memory card containing a system for forming a memory address, the system comprising;

a pseudo-random number generator for generating a first plurality of bits representing a first pseudo-random number in a sequence of deterministic pseudo-random numbers, said first pseudo-random number representing at least a portion of a first memory address; and

a pattern eliminator coupled to said pseudo-random number generator and configured to receive at least a portion of said first plurality of low order bits and to remove a pattern that exists in said portion.