System and method for storing a tag to identify a functional storage location in a memory device

[0002] The invention relates generally to the use of partially defective memory devices and, in particular, to the use of partially defective random access memory (RAM) devices.

[0003] Not all applications that use computer memory devices require those devices to provide absolute store-and-retrieve fidelity. For example, applications such as telephone answering machines, some video storage devices, and toys may use memory devices that have one or more non-functional memory locations. Systems such as these may use a memory interface device to identify and map out those blocks of memory having one or more defective locations. Referring to FIG. 1, a system 100 capable of using partially defective memory 102 may also include application 104 (e.g., an audio or video storage application), interface 106 through which application 104 communicates with memory 102, and input-output (I/O) unit 108 through which application 104 communicates with external units or users.

[0004] In one prior art technique, interface 106 may generate a table whose entries identify blocks within memory 102 that have one or more defective locations. A block of memory may be a specified number of memory locations, for example, 256 bits, 64 nibbles, 128 bytes, or 64 words. Referring to FIG. 2, interface 106 may write a known pattern (e.g., the zero value) to every location in memory 102 (at 200). Next, a block of memory 102 may be read (at 202) and inspected (at 204). If every location retrieved at 202 reflects the pattern written at 200 (the ‘yes’ prong at 204), a table entry is generated that identifies the block of memory as valid (at 206). If every location retrieved at 202 does not match the pattern written at 200 (the ‘no’ prong at 204), a table entry is generated that identifies the entire block of memory as invalid (at 208). If, after creating a table entry at 206 or 208, the entire memory has been inspected (the ‘yes’ prong at 210), processing terminates (at 212). If, after creating a table entry at 206 or 208, the entire memory has not been inspected (the ‘no’ prong at 210), processing continues at 202. During subsequent operations, interface 106 may read information from and write information to memory 102 while skipping those blocks identified in the table as invalid. A table created in accordance with FIG. 1 may be generated upon system 100 power-up/reset, or once during the manufacture and testing process. Further, the table may be stored in volatile memory such as RAM or nonvolatile memory such as programmable read only memory (PROM), electrically erasable programmable read only memory (EEPROM), or FLASH type memory.

[0005] In another prior art technique, interface 106 may write a pattern to memory 102 indicating whether a block is valid/functional or invalid/nonfunctional. Referring to FIG. 3, interface 106 may write a known pattern (e.g., the zero value) to every location in memory 102 (at 300). Memory 102 may then be read back a block at a time (at 302) and inspected (at 304). If every location retrieved at 302 reflects the pattern written at 300 (the ‘yes’ prong at 304), each location in that block of memory is written with a specified pattern indicating it as valid memory (at 306). If every location retrieved at 302 does not match the pattern written at 300 (the ‘no’ prong at 304), each location in that block of memory is written with a specified pattern indicating it as invalid memory (at 308). If, after storing a pattern to memory at 306 or 308, the entire memory has been inspected (the ‘yes’ prong at 310), processing terminates (at 312). If, after storing a pattern to memory at 306 or 308, the entire memory has not been inspected (the ‘no’ prong at 310), processing continues at 302. During subsequent operations, interface 106 may read information from and write information to memory 102 by skipping over those blocks marked as invalid.

[0006] Current techniques to incorporate partially dysfunctional memory devices into a system include or exclude entire blocks of memory. Because the cost of memory is becoming increasingly important in driving the cost of finished products such as telephone answering machines, video storage devices, and toys, it would be beneficial to provide a mechanism that allows more of a partially dysfunctional memory device to be used.

[0007] In one embodiment, the invention provides a method to demarcate regions of dysfunctional storage locations in a memory device. The method includes identifying a first and a second dysfunctional storage location in the memory device, and storing a first tag before the first storage location, the first tag indicating a storage location immediately after the second storage location.

[0008] In another embodiment, the invention also provides a method to demarcate functional regions of storage locations by identifying a functional storage location, and storing a second tag at the identified functional storage location, the second tag indicating a storage location immediately preceding the first identified dysfunctional storage location.

[0009] Methods in accordance with the invention may be stored in any media that is readable and executable by a programmable control device such as, for example, a microprocessor or custom designed state machine.

[0010] FIG. 1 shows a prior art system that may use partially defective memory devices.

[0011] FIG. 2 shows one prior art method to identify blocks within a memory device that include defective storage locations.

[0012] FIG. 3 shows another prior art method that identifies blocks within a memory device that include defective storage locations.

[0013] FIG. 4 shows a system in accordance with one embodiment of the invention.

[0014] FIG. 5 illustrates a memory device having regions of nonfunctional storage elements.

[0015] FIG. 6 shows one method in accordance with the invention to identify and demarcate memory regions having dysfunctional storage elements.

[0016] FIG. 7 illustrates a memory device having regions of nonfunctional storage elements demarcated by tags in accordance with one embodiment of the invention.

[0017] FIG. 8 shows a tag structure in accordance with one embodiment of the invention.

[0018] FIG. 9 illustrates a memory device having regions of nonfunctional storage elements demarcated by tags in accordance with another embodiment of the invention.

[0019] FIG. 10 shows another tag structure in accordance with one embodiment of the invention.

[0020] FIG. 11 shows another method to identify and demarcate memory regions in accordance with one embodiment of the invention.

[0021] Techniques (including methods and devices) to map out those locations in a memory device determined to be faulty are described. Illustrative systems where such a technique may be beneficial include, but are not limited to, audio applications such as telephone answering machines and toys and video storage devices such as video disks. The following embodiments of this inventive concept are illustrative only and are not to be considered limiting in any respect.

[0022] Referring to FIG. 4, a system 400 in accordance with one embodiment of the invention includes audio application 402, analog to digital (ADC) 404 and digital to analog (DAC) 406 converters, memory interface unit 408, and audio random access memory (ARAM) 410. Audio application 402 may include a combination of hardware and software needed to implement the target application. For example, if the target application is a telephone answering device, audio application 402 may include a microprocessor, programmable microcontroller, or a custom designed state machine to implement the desired answering machine functions. Analog to digital converter 404 provides a mechanism for externally generated sound (e.g., a voice) to be changed to a digital format for processing and/or storage in system 400. Similarly, DAC 406 provides a mechanism for digitally generated and/or stored information to be converted to analog format for external presentation. Interface 408 provides a mechanism for interfacing application 402 to memory 410. For example, interface 408 may include a Z8 microcontroller manufactured by the Zilog corporation. In one embodiment memory 410 includes two 4M×4 ARAM devices to provide a total of 4 megabytes (MB) of memory, e.g., two S4004SA1-0 memory devices sold by Micron Electronics Incorporated. One function of interface unit 408 is to present a uniform memory space to application 402, mapping out any nonfunctional memory locations in memory 410. That is, interface 408 makes any nonfunctional memory locations in memory 410 transparent to application 402.

[0023] Referring to FIG. 5, memory 410 may be visualized as a contiguous sequence of memory locations (each 8 bits, or 1 byte, wide) starting at 000000h (where ‘h’ indicates hexadecimal notation) and ending at 3FFFFFh (4×2²⁰bytes or 4 MB). For illustrative purposes, memory 410 is shown as having two regions of partially dysfunctional memory locations: region 1500 and region 2502 (dysfunctional memory locations are represented by solid horizontal black bars).

[0024] In accordance with one embodiment of the invention (see FIG. 6), interface unit 408 identifies and demarcates regions of memory 410 that include nonfunctional storage elements—storage locations (e.g., bytes) having one or more components (e.g., bits) that do not function correctly. Initially interface 408 may write a known pattern, such as the value 2Ah, to each location in memory 410 (at 600). Interface 408 may then read memory 410 (at 602), and determine if the pattern written at 600 is the same as the pattern read at 602 (at 604). If the patterns match (the ‘yes’ prong at 604), the memory location read at 602 is determined to be valid/functional, and processing continues at 610.

[0025] If the pattern written at 600 and read at 602 do not match (the ‘no’ prong at 604), interface 408 continues to read storage locations from memory 410 to determine the extent of the dysfunctional memory (at 608). Referring to FIG. 7, if the address of the first dysfunctional memory location is A, and the last dysfunctional storage location has an address of B, the extent of the dysfunctional storage locations is (B-A) and defines region 1500. With the number of dysfunctional storage locations known (at 606), interface 408 may store tag T1700 preceding the region of bad memory (at 608), region 1500 for example.

[0026] Referring now to FIG. 8, tag 700 may include pattern portion 800 and offset portion 802. It is beneficial if pattern portion 800 is selected to uniquely identify the combination of pattern portion 800 and offset portion 802 as a tag. For example, tag pattern portion 800 could be 32-bits represented by an 8-digit hexadecimal value, each of whose digits are not evenly divisible by two. One illustrative pattern portion 800 is 35793579h. Tag offset portion 802 may indicate the next valid storage location in memory 410. For example, offset portion 802 may “point” to storage location B+1. An illustrative offset value may be embodied in a 16-bit value, making it possible to specify offsets as large as approximately 65,000 storage locations (e.g., bytes).

[0027] Following a matched pattern at 604 or a tag insertion at 608, interface 408 determines if all of memory 410 has been inspected (at 610). If memory 410 has been inspected (the ‘yes’ prong at 610), processing terminates at 612. If all of memory 410 has not been inspected (the ‘no’ prong at 610), processing continues at 602. For example, referring again to FIG. 7, interface 408 may continue reading from memory 410 until address location C is inspected. At that point acts 606 and 608 are performed to insert tag T2702.

[0028] As shown in FIG. 7, region 2502 illustrates an area of memory having some non-contiguous dysfunctional storage locations. When non-contiguous dysfunctional storage locations are encountered, interface 408 may specify that if less than N contiguous storage locations are functional, the collection of storage locations are dysfunctional. That is, a dysfunctional region may be defined as that region between two sequences of functional storage locations, each of which are at least N storage locations in length. As a practical matter, it is beneficial if N is set to a value equal to the size of a tag plus the minimum useful memory region. Thus, as an example, if the smallest useable memory area (to store data for example) is 16 bytes, and a tag is 4 bytes, then N may be greater than or equal to 20.

[0029] In accordance with another embodiment of the invention (see FIG. 9), memory regions may be demarcated with multiple tags. Header tags H1900, H2902, and H3904 demarcate regions of memory 410 which include fully functional storage locations. Footer tags T1700 and T2702 demarcate regions of memory 410 which include partially functional, or fully dysfunctional, storage locations.

[0030] Referring now to FIG. 10, a header tag structure 1000 in accordance with one embodiment of the invention may include pattern portion 1002, identifier portion 1004, and length portion 1006. As in the tag structure of FIG. 8, it may be beneficial if pattern portion 1002 is selected to uniquely identify header tag structure 1000 and which is different from tag pattern portion 800. For example, pattern portion 1002 could be 32-bits represented by an 8-digit hexadecimal value, each of whose digits are not evenly divisible by two. One illustrative pattern portion 800 is 97359735h. Tag identifier portion 1004 may be used by interface 408 to identify which data is stored in the memory following the header tag. For example, identifier portion 1004 may be used by interface 408 to assist it in matching a symbolic reference for the tag's associated data (e.g., the symbol used by application 402 to identify the data). An illustrative identifier portion 1004 may be embodied in a 16-bit value. In an embodiment of the invention which utilizes identifier portion 1004, tag length portion 1006 may indicate the number of fully functional storage locations associated with a specified data item. In another embodiment of the invention which does not use identifier portion 1004 (e.g., when each valid memory region is demarcated by a single header tag), tag length portion 1006 may indicate the number of fully functional storage locations available for data storage following tag 1000 (i.e., until the next dysfunctional region or end of memory). An illustrative length portion 1006 may be embodied in a 16-bit value.

[0031] One technique using header and footer tags to demarcate regions within memory 410 in accordance with FIGS. 9 and 10 is shown in FIG. 11. As before, interface 408 may initially write a known-pattern to each location in memory 410 (at 1100). Interface 408 may then initialize header tag structure 1000 at the start of memory 410 (at 1102). For example, interface 408 may write pattern portion 1002 to memory 410 and zeros' to identifier 1004 and length 1006 portions, This operation is generally possible as many ARAM devices (and other types of memory devices) guarantee the first M storage locations to be valid. For example, the S4004SA1-0 memory device sold by Micron Electronics, Incorporated guarantees that the first 16 storage locations are valid/functional. Following header tag initialization, interface 408 may read memory 410 (at 1104), and determine if the pattern written at 1100 is the same as the pattern read at 1104 (at 1106). If the two patterns match (the ‘yes’ prong at 1106), the memory location read at 1104 is determined to be valid/functional, and processing continues at 1114.

[0032] If the pattern written at 1100 and read at 1104 do not match (the ‘no’ prong at 1106), interface 408 completes the header tag structure initialized at 1102 (at 1108) by, for example, writing to the tag's length portion 1006 the extent of the valid/functional storage location. Interface 408 may then continue to read storage locations from memory 410 to determine the extent of the dysfunctional memory (at 1110). With the number of dysfunctional storage locations known, interface 408 may insert a tag structure preceding the region of bad memory (at 1112), e.g., tag T1700 or tag T2702 in FIG. 9. Following a matched pattern at 1106 or a tag insertion at 1112, interface 408 determines if all of memory 410 has been inspected (at 1114). If memory 410 has been inspected (the ‘yes’ prong at 1114), processing terminates at 1116. If all of memory 410 has not been inspected (the ‘no’ prong at 1114), processing continues at 1102.

[0033] In summary, those storage locations in a memory device that are partially or fully dysfunctional cannot be used for normal data storage methods such as utilized by conventional applications. Techniques in accordance with the invention “map out” failed memory locations on a region-by-region basis, where a region is defined by the extent of the dysfunctional memory. Prior art techniques, on the other hand, map out failed memory locations on a per-block basis, where a block is related to the memory's underlying physical architecture. Thus, if a memory device has a single dysfunctional storage location, prior art techniques would map out an entire block (e.g., 256 bytes). In contrast, a method in accordance with the invention may map only out the one faulty location while also consuming a minimal amount of additional memory for a tag structure (or two tag structures if both a header and footer tag embodiment is used). Thus, techniques in accordance with the invention effectively increase the amount of memory available to a system (e.g., an application and/or memory interface) for data storage over prior art techniques.

[0034] Various changes in the materials, components, circuit elements, as well as in the details of the illustrated operational methods are possible without departing from the scope of the claims. For instance, the invention is not limited to audio or video applications—the invention may be used with any application that uses memory. For example, partially dysfunctional high speed memory devices may be used in accordance with the invention in a system that can tolerate a less than maximum data transfer rate from memory (to accommodate the overhead of “skipping over” dysfunctional storage locations). Thus, the invention may be used in standard computer systems comprising a central processor, a main bus, a memory (e.g., system RAM), bridge circuits, and peripherals.

[0035] In addition, acts in accordance with FIGS. 6 and 11 may be performed by a programmable control device executing instructions organized into a program module. A programmable control device may be a computer processor or a custom designed state machine. Custom designed state machines may be embodied in a hardware device such as a printed circuit board comprising discrete logic, integrated circuits, or specially designed application specific integrated circuits (ASICs). Storage devices suitable for tangibly embodying program instructions include all forms of non-volatile memory including, but not limited to: semiconductor memory devices such as EPROM, EEPROM, and flash devices; magnetic disks (fixed, floppy, and removable); other magnetic media such as tape; and optical media such as CD-ROM disks.