The present invention is directed to providing a directory for data stored in a memory and, in particular, to a technique which avoids the necessity of having an error free section in the memory for storing the directory.
Two well known types of electronic memory devices are dynamic random access memories ("DRAM") and Flash electrically erasable and programmable read only memories ("FLASH"). DRAM and FLASH devices are often put to use in applications which require them to be defect free, or essentially so. However, various applications exist which can tolerate a certain number of defects in the memory. One example is in the area of voice and other audio information storage, such as in a telephone answering machine. Due to the somewhat forgiving nature of the human ear and brain, loss or alteration of a certain portion of data related to such information can be tolerated. Consequently, it is not necessary to use an error free memory. Instead, memory devices with a specified defect level can provide an adequate degree of performance, and the advantage in using such devices is that they can be obtained at a significant cost saving.
A DRAM having a quality of a less than a defect-free grade, and for further cost reductions may also have relaxed AC and DC specifications, but which is nevertheless usable in the above-described type of applications is commonly known as an audio quality DRAM ("ARAM"), and is available from Micron Customer Manufacturing Services, Inc. of Boise, Id. as 4P4001JDJ-4N. The term "grade" is used herein to denote the number of errors in data stored in the ARAM which still allow the ARAM or a portion of it to be used, and this depends on the voice storage format/compression algorithm, the storage method and the desired voice quality/price trade-off. A FLASH with comparable characteristics for this purpose is referred to herein as an AFLASH.
Various items of information can be retained in memory by storing associated units of data related thereto. For example, in an application such as a telephone answering machine, the items of information are the recorded voice messages. Each message can be regarded as one item of information. Digital bits of data are stored in the memory, with such bits that are associated with each other jointly composing one recorded message. The memory must store not only the audio information but also a directory which contains information on the location of recorded voice messages. Two approaches have been used for handling the directory stored in an ARAM, namely (1) static data and (2) garbage collection,
In the static data method, as used in the "NSVOICE Revision 2.2" software package available from National Semiconductor Corp. of Santa Clara, Calif. under the code no. NSW-VC-BCSX4, the data storage area of the memory is virtually partitioned into blocks. Each block includes one message or part of a message. A certain portion of the memory is dedicated to the directory in which one entry per block is made. For example, an entry can be a storage location that holds a unit of data such as a byte which identifies what data is stored in the associated block, as by a message number. Certain values are reserved to indicate an empty block or an unusable block. Initially, the data derived from the received voice message(s) is stored in the first "n" free blocks. As a block is used for data storage it is marked with an identification code ("ID"), such as the message number. When a particular message is erased, every block having the corresponding ID is marked as being "free" for subsequent use in recording another message. Thus, eventually the directory may link blocks dispersed throughout the memory to form one message, and the data storage portion of the memory may have free and filled blocks interspersed with each other.
In the garbage collection approach, as used in the model D6055A answering machine available from The DSP Group, Inc. of San Jose, Calif., the data is always stored sequentially, message after message, with no intervening free blocks. As a message is erased, the resulting "hole" is closed by copying all of the remaining stored data with a process called "garbage collection". The directory contains pointers to the beginning of each message and to the beginning of the free memory. The copied data is then sequentially re-stored into the memory so as to fill the first "m" blocks, as required, to thereby close the "hole". Due to repetitive movements of the data with this scheme, it is necessary to apply error correction to all the data. This prevents deterioration in the quality of the data due to an accumulation of errors during copying.
A significant disadvantage attendant to the use of both of the above-described approaches is the need for a lengthy, continuous portion of memory that is of sufficient capacity to retain the directory data and which is "recoverable". The term "recoverable" means that original data written to this portion can be recovered by either such portion being error-free or by applying an error-correction code. The data stored in the directory is of such vital importance that no corruption in it can be tolerated.
Upon activating the prior art system, a memory check procedure is executed which classifies blocks as being "good" or "bad". Bad blocks are so marked and are not used for storage of message data. The marking is done with a specifically reserved value stored in the appropriate directory entry for that block. Thus, for example, a 4.times.1 Mbyte ARAM is partitioned into 1024 blocks, each one having the length of a row (i.e. 4096 bits). The first four blocks are dedicated to the directory, and are error-free. The directory includes 1024 entries, with 8-bits in each entry. Each such entry is related to one block. Also, the directory stores 32-bits per message of message-related data, such as time and date of occurrence. A maximum of 128 messages can be stored. Therefore, 4 Kbits is required to store all of the message-related information. Thus, the prior art directory requires 8 Kbits for the directory information, and 4 Kbits for the message-related information for a total of 12 Kbits.
The necessity for such a recoverable portion, which in the prior art is a 12 Kbit error-free portion that is continuous, seriously limits the extent to which the specification of the memory device can be relaxed. Consequently, the cost savings which accrues from using an ARAM rather than a DRAM is less than what it otherwise could be because out of several grades of quality of a manufactured device, a higher grade must be used to meet this requirement for a lengthy, continuous, recoverable portion. Of course, the directory can also be stored in a separate device, such as a static RAM, but this also increases the total system cost.
A further shortcoming of both approaches is the impracticality of their use with FLASH memories. FLASH memories have the characteristics of (a) being erasable only by simultaneously erasing large portions of, or even the entire, memory, and (b) having a limited number of write/erase cycles, such as 100,000. The combination of these two characteristics can severely limit the usable life of an AFLASH. This is because the directory must be revised every time any one of the blocks of data is written into or erased. If the directory is simultaneously erasable with N blocks, and N=10 for example, then as the directory has been cycled 100,000 times, each of the blocks can experience as few as only 10,000 cycles (if the number of changes of the memory blocks has been equalized, such as by revising them sequentially). Thus, conceivably the blocks could have 90% of their usable life left if it were not for the much higher usage of the blocks storing the directory.