RELATED APPLICATIONSThis application is a divisional of U.S. patent application for “FLASH MEMORY CONTROLLER FOR ELECTRONIC DATA FLASH CARD”, U.S. application Ser. No. 11/466,759, filed Aug. 23, 2006, which is a continuation-in-part of U.S. patent application for “ELECTRONIC DATA STORAGE MEDIUM WITH FINGERPRINT VERIFICATION CAPABILITY”, U.S. application Ser. No. 09/478,720, filed Jan. 6, 2000, a continuation-in-part of U.S. patent application for “ELECTRONIC DATA FLASH CARD WITH FINGERPRINT VERIFICATION CAPABILITY”, U.S. application Ser. No. 11/458,987, filed Jul. 20, 2006, which is a continuation-in-part of U.S. patent application for “HIGHLY INTEGRATED MASS STORAGE DEVICE WITH AN INTELLIGENT FLASH CONTROLLER”, U.S. application Ser. No. 10/761,853, filed Jan. 20, 2004, and a continuation-in-part of U.S. patent application for “SYSTEM AND METHOD FOR CONTROLLING FLASH MEMORY”, U.S. application Ser. No. 10/789,333, filed Feb. 26, 2004.
FIELD OF THE INVENTIONThe invention relates to electronic data flash cards, more particularly to a system and method for controlling flash memory in an electronic data flash card.
BACKGROUND OF THE INVENTIONConfidential data files are often stored in floppy disks or are delivered via networks that require passwords or that use encryption coding for security. Confidential documents are sent by adding safety seals and impressions during delivery. However, confidential data files and documents are exposed to the danger that the passwords, encryption codes, safety seals and impressions may be broken (deciphered), thereby resulting in unauthorized access to the confidential information.
As flash memory technology becomes more advanced, flash memory is replacing traditional magnetic disks as storage media for mobile systems. Flash memory has significant advantages over floppy disks or magnetic hard disks such as having high-G resistance and low power dissipation. Because of the smaller physical size of flash memory, they are also more conducive to mobile systems. Accordingly, the flash memory trend has been growing because of its compatibility with mobile systems and low-power feature. However, advances in flash technology have created a greater variety of flash memory device types that vary for reasons of performance, cost and capacity. As such, a problem arises when mobile systems that are designed for one type of flash memory are constructed using another, incompatible type of flash memory.
New generation personal computer (PC) card technologies have been developed that combine flash memory with architecture that is compatible with the Universal Serial Bus (USB) standard. This has further fueled the flash memory trend because the USB standard is easy to implement and is popular with PC users. In addition to replacing hard drives, flash memory is also replacing floppy disks because flash memory provides higher storage capacity and faster access speeds than floppy drives.
However, the USB standard has several features that require additional processing resources. These features include fixed-frame times, transaction packets, and enumeration processes. For better optimization, these features have been implemented in application-specific integrated circuits (ASICs).
A problem with USB mass-storage devices is that they are slow. The USB interface is significantly slower than IDE (Integrated Drive Electronics) interface in particular. This is because of the overhead associated with the USB standard, which include additional resources required for managing USB commands and handshake packets. Bulk-only transactions introduced by the USB standard have relieved some resources but only if the USB traffic is not too busy.
In addition to the limitations introduced by the USB standard, there are inherent limitations with flash memory. First, flash memory sectors that have already been programmed must be erased before being reprogrammed. Also, flash memory sectors have a limited life span; i.e., they can be erased only a limited number of times before failure. Accordingly, flash memory access is slow due to the erase-before-write nature and ongoing erasing will damage the flash memory sectors over time.
To address the speed problems with USB-standard flash memory, hardware and firmware utilize existing small computer systems interface (SCSI) protocols so that flash memory can function as mass-storage devices similarly to magnetic hard disks. SCSI protocols have been used in USB-standard mass-storage devices long before flash memory devices have been widely adopted as storage media. Accordingly, the USB standard has incorporated traditional SCSI protocols to manage flash memory.
A problem with SCSI protocols is that they do not include an erase command to address the erase-before-write nature of flash memory. Accordingly, the erase operation is handled by the host system, which further ties up the host system resources.
Some solutions have been introduced that involve new USB packet definitions such as write flash, read flash, and erase flash definitions. However, these definitions are not an efficient way to handle flash memory because they introduce additional protocols that require additional computing resources at the host system. They also do not address the sector-wear issues.
Another solution provides a driver procedure for flash memory write transactions. This procedure has three different sub-procedures. Generally, the data of a requested flash memory address is first read. If there is data already written to that address, the firmware executes an erase command. Then, if the erase command executes correctly, the firmware executes a write request. However, this driver procedure utilizes protocols that require additional computing resources at the host system.
Another solution provides a flash sector format that has two fields: a data field and a spare field. The spare field contains control data that include flags that facilitate in the management of the sectors. However the flags introduce ASIC complexity when the host system writes to the sectors.
Disadvantages of many of the above-described and other known arrangements include additional host system resources required to process special protocols and the resulting added processing time required for managing flash memory.
Accordingly, what is needed is an electronic data flash card that includes an intelligent processing unit for flexible flash memory type support.
What is also needed is an improved system and method for controlling flash memory. The system and method should be able to comply with the USB standard, should be suitable for ASIC hardware implementation, and should be simple, cost effective and capable of being easily adapted to existing technology.
SUMMARY OF THE INVENTIONThe present invention is generally directed to an electronic data flash card including a flash memory device, a fingerprint sensor, an input-output interface circuit and a processing unit. The electronic data flash card is adapted to be accessed by a host (external) computer such as a personal computer, notebook computer or other electronic host device. As an electronic data flash card is easier to carry and durable for ruggedness, personal data can be stored inside the flash memory device in an encrypted form such that it can only be accessed, for example, by way of a fingerprint sensor associated with card body to make sure unauthorized person cannot misuse the card.
In accordance with an aspect of the invention, a flash memory controller is part of the processing unit to control the operation of the flash memory device. The processing unit is connected to the flash memory device and the input/output interface circuit. The flash memory controller logic includes a flash type algorithm for detecting whether the flash memory device is of a flash type that is supported by the flash memory controller logic. By storing the dynamic portion of the flash detection algorithm code along with the confidential data in at least one flash memory device, not only can the ROM size of the electronic data flash card be reduced, but new flash types can be supported without hardware alteration simply by changing the dynamic portion of the flash detection algorithm stored in the flash memory. The overall cost is reduced and the unnecessary development time is also eliminated.
In accordance with another embodiment of the present invention, the processing unit of an electronic data flash card is operable selectively in a programming mode, a data retrieving mode, and a resetting mode. When the processing unit is in the programming mode, the processing unit activates the input/output interface circuit to receive the confidential data file from the host computer, and to store the data file in the flash memory device. When the processing unit is in the data retrieving mode, the processing unit activates the input/output interface circuit to transmit the data file to the host computer. In the data resetting mode, the data file (and the reference fingerprint data) is/are erased from the flash memory device.
In one embodiment, the processing unit is a microprocessor including one of an 8051, 8052, 80286, RISC, ARM, MIPS or digital signal processor.
In accordance with an embodiment of the present invention, the input/output (I/O) interface circuit is a USB interface circuit.
In accordance with another embodiment of the present invention, a USB flash device transfers high-speed data between computers using only the Bulk-Only Transfer (BOT) protocol. BOT is a more efficient and faster transfer protocol than command/bulk/interrupt (CBI) protocol because BOT transport of command, data, status rely on Bulk endpoints in addition to default Control endpoints.
In accordance with another embodiment of the present invention, the flash memory controller includes a processor for receiving at least one request from a host system. The flash memory controller further includes an index including information regarding sectors of a flash memory. The processor utilizes the index to determine the sectors of the flash memory that are available for programming, reprogramming, or reading. In another aspect of the present invention, the flash memory controller further includes a first-in-first-out unit (FIFO) for recycling obsolete sectors so that they are available for reprogramming.
According to the system and method disclosed herein, the host system interacts with the flash memory controller without the host system having information regarding the configuration of the flash memory. Consequently, speeds at which data is written to and read from flash memory is significantly increased while the flash memory remains compatible with the USB standard and ASIC architecture.
BRIEF DESCRIPTION OF THE DRAWINGOther features and advantages of the present invention will become apparent in the following detailed description of the preferred embodiment with reference to the accompanying drawings, of which:
FIG. 1 is a block diagram showing an electronic data flash card with fingerprint verification capability in accordance with an embodiment of the present invention.
FIG. 2 is a schematic circuit block diagram illustrating an electronic data flash card according to another embodiment of the present invention.
FIG. 3 is a block diagram of a processing unit utilized in an electronic data flash card in accordance with another embodiment of the present invention.
FIG. 4A is a flow chart showing a process for detecting a flash memory type in accordance with an embodiment of the present invention.
FIG. 4B is a block diagram showing a portion of an electronic data flash card according to another embodiment of the present invention.
FIG. 5A is a block diagram illustrating an 8-bit access with 8-bit data flash memory.
FIG. 5B is a block diagram illustrating a 16-bit access with 16-bit data flash memory.
FIG. 5C is a block diagram illustrating a 16-bit dual channel access with two 8-bit data flash memories via a single control.
FIG. 5D is a block diagram illustrating a 16-bit interleave channel access with two 8-bit data flash memories via separate controls according to an embodiment of the present invention.
FIG. 6 is a schematic circuit block diagram illustrating an electronic data flash card according to another embodiment of the present invention.
FIG. 7 is a block diagram of a flash memory system including a flash memory controller and a flash memory in accordance with the present invention.
FIG. 8 is a block diagram showing in more detail the write look-up table, the read look-up table, the physical usage table, and the recycling first-in-first-out unit ofFIG. 7 in accordance with the present invention.
FIG. 9 is a block diagram showing in more detail the flash memory ofFIG. 7 in accordance with the present invention.
FIG. 10 is a high-level flow chart showing a method for managing flash memory in accordance with the present invention.
FIG. 11 is a flow chart showing a method for transmitting USB mass-storage class service requests in accordance with the present invention.
FIGS. 12A,12B and12C are block diagrams showing a command block wrapper, a reduced block command read format, and a command status wrapper in accordance with the present invention.
FIG. 13 is a flow chart showing a method for reading, writing, and erasing in accordance with the present invention.
FIG. 14 is a high-level flow chart showing a method including a first phase of a write transaction, a second phase of the write transaction, a read transaction, and a recycling operation in accordance with the present invention.
FIGS. 15A,15B,15C and15D are block diagrams illustrating exemplary results from first and second phases of a write transaction in accordance with the present invention.
FIG. 16 is a flow chart showing a method for implementing the first phase of the write transaction ofFIG. 14 in accordance with the present invention.
FIG. 17 is a flow chart showing a method for implementing the second phase of the write transaction ofFIG. 14 in accordance with the present invention.
FIG. 18 is a flow chart showing a method for implementing the read transaction ofFIG. 14 in accordance with the present invention.
FIG. 19 is a flow chart showing a method for implementing the recycling operation ofFIG. 14 in accordance with the present invention.
DETAILED DESCRIPTIONReferring toFIG. 1, according to an embodiment of the present invention, an electronicdata flash card10 is adapted to be accessed by an external (host)computer9 either via aninterface bus13 or acard reader12 or other interface mechanism (not shown), and includes acard body1, aprocessing unit2, one or moreflash memory devices3, afingerprint sensor4, an input/output interface circuit5, anoptional display unit6, an optional power source (e.g., battery)7, and an optional function key set8.
Flash memory device3 is mounted on thecard body1, stores in a known manner therein one or more data files, a reference password, and the reference fingerprint data obtained by scanning a fingerprint of one or more authorized users of the electronicdata flash card10. Only authorized users can access the stored data files. The data file can be a picture file or a text file.
Thefingerprint sensor4 is mounted on thecard body1, and is adapted to scan a fingerprint of a user of electronicdata flash card10 to generate fingerprint scan data. One example of thefingerprint sensor4 that can be used in the present invention is that disclosed in a co-owned U.S. Pat. No. 6,547,130, entitled “INTEGRATED CIRCUIT CARD WITH FINGERPRINT VERIFICATION CAPABILITY”, the entire disclosure of which is incorporated herein by reference. The fingerprint sensor described in the above patent includes an array of scan cells that defines a fingerprint scanning area. The fingerprint scan data includes a plurality of scan line data obtained by scanning corresponding lines of array of scan cells. The lines of array of scan cells are scanned in a row direction as well as column direction of said array. Each of the scan cells generates a first logic signal upon detection of a ridge in the fingerprint of the holder of card body, and a second logic signal upon detection of a valley in the fingerprint of the holder of card body.
The input/output interface circuit5 is mounted on thecard body1, and can be activated so as to establish communication with thehost computer9 by way of an appropriate socket via aninterface bus13 or acard reader12. In one embodiment, input/output interface circuit5 includes circuits and control logic associated with a Universal Serial Bus (USB), PCMCIA or RS232 interface structure that is connectable to an associated socket connected to or mounted on thehost computer9. In another embodiment, the input/output interface circuit5 may include one of a Secure Digital (SD) interface circuit, a Multi-Media Card (MMC) interface circuit, a Compact Flash (CF) interface circuit, a Memory Stick (MS) interface circuit, a PCI-Express interface circuit, a Integrated Drive Electronics (IDE) interface circuit, and a Serial Advanced Technology Attachment (SATA) interface circuit, which interface with thehost computer9 via aninterface bus13 or acard reader12.
Theprocessing unit2 is mounted on thecard body1, and is connected to theflash memory device3, thefingerprint sensor4 and the input/output interface circuit5 by way of associated conductive traces or wires disposed oncard body1. In one embodiment, processingunit2 is one of an 8051, 8052, 80286 microprocessors available, for example, from Intel Corporation. In other embodiments, processingunit2 includes a RISC, ARM, MIPS or other digital signal processors (DSP). In accordance with an aspect of the present invention, processingunit2 is controlled by a program stored at least partially inflash memory device3 such thatprocessing unit2 is operable selectively in: (1) a programming mode, where theprocessing unit2 activates the input/output interface circuit5 to receive the data file and the reference fingerprint data from thehost computer9, and to store the data file and the reference fingerprint data inflash memory device3; (2) a data retrieving mode, where theprocessing unit2 activates the input/output interface circuit5 to transmit the data file stored inflash memory device3 to thehost computer9; and (3) a data resetting mode, where the data file and the reference finger data are erased from theflash memory device3. In operation,host computer9 sends write and read requests to electronicdata flash card10 viainterface bus13 or acard reader12 and input/output interface circuit5 to theprocessing unit2, which in turn utilizes a flash memory controller (not shown) to read from or write to the associated one or moreflash memory devices3. In one embodiment, for further security protection, theprocessing unit2 automatically initiates operation in the data resetting mode upon detecting that a preset time period has elapsed since the last authorized access of the data file stored in theflash memory device3.
Theoptional power source7 is mounted on thecard body1, and is connected to theprocessing unit2 and other associated units oncard body1 for supplying electrical power thereto.
The optional function key set8, which is mounted on thecard body1, is connected to theprocessing unit2, and is operable so as to initiate operation ofprocessing unit2 in a selected one of the programming, data retrieving and data resetting modes. The function key set8 is operable to provide an input password to theprocessing unit2. Theprocessing unit2 compares the input password with the reference password stored in theflash memory device3, and initiates authorized operation of electronicdata flash card10 upon verifying that the input password corresponds with the reference password.
Theoptional display unit6 is mounted on thecard body1, and is connected to and controlled by theprocessing unit2 for showing the data file exchanged with thehost computer9 and for displaying the operating status of the electronicdata flash card10.
The following are some of the advantages of the present invention: first, the electronic data flash card has a small volume but a large storage capability, thereby resulting in convenience during data transfer; and second, because everyone has a unique fingerprint, the electronic data flash card only permits authorized persons to access the data files stored therein, thereby resulting in enhanced security.
Additional features and advantages of the present invention are set forth below.
FIG. 2 is a block diagram of an electronicdata flash card10A in accordance with an alternative embodiment of the present invention that omits the fingerprint sensor and the associated user identification process. The electronicdata flash card10A includes a highlyintegrated processing unit2A including an input/output interface circuit5A and aflash memory controller21 for integration cost reduction reasons. Input/output interface circuit5A includes a transceiver block, a serial interface engine block, data buffers, registers and interrupt logic. Input/output interface circuit5A is coupled to an internal bus to allow for the various elements of input/output interface circuit5A to communicate with the elements offlash memory controller21.Flash memory controller21 includes a microprocessor unit, a ROM, a RAM, flash memory controller logic, error correction code logic, and general purpose input/output (GPIO) logic. In one embodiment, the GPIO logic is coupled to a plurality of LEDs for status indication such as power good, read/write flash activity, etc., and other I/O devices.Flash memory controller21 is coupled to one or moreflash memory devices3.
In this embodiment,host computer9A includes a function key set8A, is connected to theprocessing unit2A via an interface bus or a card reader when electronicdata flash card10A is in operation. Function key set8A is used to selectively set electronicdata flash card10A in one of the programming, data retrieving and data resetting modes. The function key set8A is also operable to provide an input password to thehost computer9A. Theprocessing unit2A compares the input password with the reference password stored in theflash memory device3, and initiates authorized operation of electronicdata flash card10A upon verifying that the input password corresponds with the reference password.
Also in this embodiment, ahost computer9A includes display unit6A, is connected to theprocessing unit2A when electronicdata flash card10A is in operation via an interface bus or a card reader. Display unit6A is used for showing the data file exchanged with thehost computer9A, and for showing the operating status of the electronicdata flash card10A.
FIG. 3 showsprocessing unit2A in additional detail. Electronicdata flash card10A includes apower regulator22 for providing one or more power supplies toprocessing unit2A. The power supplies provide different voltages to associated units of electronicdata flash card10A according to the power requirements. Capacitors (not shown) may be required for power stability. Electronicdata flash card10A includes areset circuit23 for providing a reset signal toprocessing unit2A. Upon power up, resetcircuit23 asserts reset signal to all units. After internal voltages reach a stable level, the reset signal is then de-asserted, and resisters and capacitors (not shown) are provided for adequate reset timing adjustment. Electronicdata flash card10A also includes a quartz crystal oscillator (not shown) to provide the fundamental frequency to a PLL withinprocessing unit2A.
In accordance with an embodiment of the invention, input/output interface circuit5A, resetcircuit23, andpower regulator22 are integrated or partially integrated withinprocessing unit2A. The high integration substantially reduces the overall space needed, the complexity, and the cost of manufacturing.
Compactness and cost are key factors to removable devices such as the electronic data flash cards described herein. Modern IC packaging can integrate discrete IC components with different technology and material into one IC package. For example, the input/output interface circuit is analog and digital mixed circuitry, which can be integrated into the MCP (Multi-Chip Package) package with the processing unit. The reset circuit and power regulator are analog circuitry, which can also be integrated into the MCP (Multi-Chip Package) package with the processing unit.
The nature of mixed signal IC technology allows the hybrid integration of both analog and digital circuitry. Therefore, higher integration can be incorporated into the same die forprocessing unit2A which includes input/output interface circuit5A,flash memory controller21, resetcircuit23 andpower regulator22.
In an alternative embodiment, aprocessing unit2, input/output interface circuit5, andpower regulator22 and areset circuit23 are integrated or partially integrated using Multi-Chip Package technology or mixed signal IC technology.
Advances in flash technology have created a greater variety of flash memory device types that vary for reasons of performance, cost and capacity. For example, Multi Bit Cell (MBC) Flash memory devices have higher capacity than Single Bit Cell (SBC) flash memory devices for the same form factor. AND or Super-AND flash memory have been created to circumvent intellectual property issues associated with NAND flash memory. Also, a large page size (2K Bytes) flash memory has better write performance against a small page size (512 Bytes) flash memory. Further, the rapid development of flash memory has resulted in devices with higher capacities. To support these various flash memory types, the flash memory controller must be able to detect and access them accordingly.
Due to the potential shortage, cost reason, the need for sourcing flexibility of flash memories, and the fact that unique control is required to access each different flash type, it is important to implement a processing unit with intelligent algorithm to detect and access the different flash memory device types.
Typical flash memory devices contains ID code which identifies the flash type, the manufacturer, and the features of the flash memory such as page size, block size organization, capacity, etc. In accordance with an embodiment of the present invention, the processing unit of an electronic data flash card performs a flash detection operation at system power up to determine whether the one or more flash memory devices of the electronic data flash card are supported by the existing flash memory controller.
FIG. 4A illustrates a flash detection algorithm in accordance with the present invention. First, the processing unit is reset (block410). Next, the ID of the flash memory is read to identify the flash memory type (block420). The read ID is then compared against the table of flash types that are supported by the existing flash memory controller (block430). If the flash type is not supported (block435), the flash memory controller will not be able to access the flash memory, and the incompatibility can be indicated by LED via an output port of the controller. If the flash type is supported, the flash memory controller will be configured to the access mode corresponding to that detected flash type (block440), and then the flash memory controller begins accessing the flash memory (block450).
Electronic data flash cards are flash memory systems using flash memories for data storage. For example, as indicated inFIG. 4B, electronicdata flash card10A includesprocessing unit2A,flash memory3A, random-access memory (RAM)24, and read-only memory (ROM)25, with the boot code (BC) and operating system (OS) code residing inROM25. Upon power up, processingunit2A fetches and executes the boot code fromROM25, which initializes the system components and loads the OS code fromROM25 intoRAM24. Once the OS code is loaded into theRAM24, it takes control of the system. The OS includes drivers to perform basic tasks such as controlling and allocating memory, prioritizing the processing of instructions, controlling input and output ports etc. The OS code also includes the flash detection algorithm code and the flash parametric data.
Because of the permanent nature of data stored in a ROM, after the flash memory controller of a conventional electronic data flash card is designed and put into production, the software in ROM is frozen and cannot be changed to support new flash types released to the market at a later time. In such a situation, the development of a new flash memory controller has to support new flash memories from time to time, which is costly and time consuming.
Referring again toFIG. 4B, in accordance with another embodiment of the present invention, electronicdata flash card10A includes a flash detection algorithm code that is separated into astatic portion26 and adynamic portion27, with thestatic portion26 handling contemporary flash memories, and thedynamic portion27 taking control of the detection process after the static portion fails to identify the particular flash memory device implemented in the electronic data flash card. That is, when electronicdata flash card10A is manufactured using an “old” type flash memory device, then the flash detection algorithm code recognizes the flash device ID during the power up process, and utilizesstatic portion26 to execute read and write the “old” type flash memory device. Conversely, when a particular electronic data flash card having the novel configuration is manufactured using a “new” type flash memory device (e.g.,3A, shown inFIG. 4B), then the flash detection algorithm code recognizes the flash device ID during the power up process, and utilizesdynamic portion27 to execute read and write operations to “new” typeflash memory device3A. With this configuration,static portion26 of the flash detection algorithm code is stored inROM25, butdynamic portion27 of the flash detection algorithm code is stored in at least oneflash memory device3A of electronicdata flash card10A. By storingdynamic portion27 along with data (not shown) in at least oneflash memory device3A, not only can the size ofROM25 be reduced, new flash types can be supported without hardware alteration. That is, if at some point the decision is made to implement a “new” flash memory type (i.e., that is not supported by the static portion), instead of having to replace the entire ROM, the process simply requires storing a suitable dynamic portion of the flash algorithm code in the one or more flash memory device. Because the default access and reading of the dynamic portion is already incorporated into execution of the flash detection algorithm code, the content of the dynamic portion can be altered without affecting operation of the flash detection algorithm code. Thus, overall manufacturing costs are reduced, and unnecessary development time is also eliminated.
Because data storing and reading in a flash memory device is necessary for access and verification purpose, speed is also a major concern of the device performance. According to additional aspects of the present embodiment set forth below, a method of dual-channel parallel and interleave access flash is implemented in an electronic data flash card for faster performance than is possible using conventional methods.
A typical electronic data flash card uses a flash memory with single-channel (8-bit) data bus, as shown inFIG. 5A. With multiple-channel data bus, more data bits can be read from or write to the flash memories simultaneously, thereby the access speed is enhanced. For example, dual-channel (16-bit) data bus can double the access speed to the flash memory, quad-channel (32-bit) data can increase the access speed by 4 times, and so on. Electronic data flash card with dual-channel data width can be realized by one 16-bit wide flash memory as illustrated inFIG. 5B, by two 8-bit wide flash memories via a single control as illustrated inFIG. 5C, or by two 8-bit wide flash memories via separate controls as illustrated inFIG. 5D.
Electronicdata flash card10B, which is depicted inFIG. 5D, includes separate control and I/O connections for each flash memory device3B1 and3B2, thereby enabling interleaved programming that enhances system speed and avoids peak power consumption. Flash memory devices consume higher power in the programming (writing) mode, in which data is transferred from page register into the flash cells of the memory array, than in any other operating mode (e.g., reading data from the flash cells, or writing memory to the page register from an external source). In accordance with the present invention, interleaved programming of flash memory devices3B1 and3B2 involves “write staggering”, whereinflash memory controller21B enables one flash memory device (e.g., flash memory device3B1) to program (write) data from its page register into its flash memory array while the other flash memory devices (e.g., flash memory device3B2) are limited to non-programming operations (e.g., enabled to receive data fromflash memory controller21B to the page register (i.e., no writing is performed in flash memory device3B2 while a write operation is being performed by flash memory device3B1). This avoids operating multiple flash memories in programming mode at the same time, and increases the speed of flash memory access by allowing the throughput for access to each flash memory device3B1 and3B2 to match the speed of the host computer interface standard. In addition to enhancing access speed, this interleave access approach allows the system to avoid peak power consumption that can be caused by writing multiple flash devices at the same time.
The various novel aspects described above may be implemented together or independently while remaining within the spirit and scope of the present invention. For example,FIG. 6 shows an electronic data flash card (or electronic data storage medium, or integrated circuit card)10C according to yet another embodiment of the present invention. Electronicdata flash card10C is adapted to be accessed by ahost computer9A via an interface bus or card reader (i.e., communication link), and includes acard body1C, aprocessing unit2C including aflash memory controller21C and an input/output interface circuit5C, and one or more flash memory devices3C in according to one or more of the embodiments described above. Electronicdata flash card10C could be the functional subsystem for electronicdata flash card10A (described above), and also could be a functional subsystem for other applications.
Flash memory device3C is controlled through commands generated byflash memory controller21C, and stores a data file in the flash memory device.
Processing unit2C is connected to flash memory device, said input/output interface circuit.Flash memory controller21C insideprocessing unit2C controls flash memory device3C utilizing one or more of the methods described above. In one embodiment,flash memory controller21C executes a flash type algorithm that determines if flash memory device3C is supported by the static portion of the flash memory controller logic stored in ROM (not shown), and reads a dynamic portion of flash memory controller logic stored in flash memory device3C if the flash type is “new”.
According to another aspect, input/output interface circuit5C is activated so as to establish USB Bulk Only Transport (BOT) communications withhost computer9A via the interface link. There are four types of USB software communication data flow between a host computer and the USB interface circuit of the flash memory device (also referred to as a “USB device” below): control, interrupt, bulk, and isochronous. Control transfer is the data flow over the control pipe from the host computer to the USB device to provide configuration and control information to a USB device. Interrupt transfers are small-data, non-periodic, guaranteed-latency, device-initiated communication typically used to notify the host computer of service needed by the USB device. Movement of large blocks of data across the USB interface circuit that is not time critical relies on Bulk transfers. Isochronous transfers are used when working with isochronous data. Isochronous transfers provide periodic, continuous communication between the host computer and the USB device. There are two data transfer protocols generally supported by USB interface circuits: Control/Bulk/Interrupt (CBI) protocol and Bulk-Only Transfer (BOT) protocol. The mass storage class CBI transport specification is approved for use with full-speed floppy disk drives, but is not used in high-speed capable devices, or in devices other than floppy disk drives (according to USB specifications). In accordance with an embodiment of the present invention, a USB flash device transfers high-speed data between computers using only the Bulk-Only Transfer (BOT) protocol. BOT is a more efficient and faster transfer protocol than CBI protocol because BOT transport of command, data, status rely on Bulk endpoints in addition to default Control endpoints.
As with previous embodiments described above, processingunit2C is selectively operable in a programming mode, where processingunit2C causes input/output interface circuit5C to receive the data file fromhost computer9A, and to store the data file in flash memory device3C through write commands issued fromhost computer9A toflash memory controller21C, a data retrieving mode, where processingunit2C receives the data in flash memory device3C through read command issued fromhost computer9A toflash memory controller21C and to access the data file stored in flash memory device3C, and activates input/output interface circuit5C to transmit the data file tohost computer9A, and a data resetting mode where the data file is erased from flash memory device3C.
Advantages of theintelligent processing unit2C in accordance with the present invention include:
(1) providing high integration, which substantially reduces the overall space needed and reduces the complexity and the cost of manufacturing.
(2) utilizing an intelligent algorithm to detect and access the different flash types, which broadens the sourcing and the supply of flash memory;
(3) by storing the portion of software program along with data in flash memory which results in the cost of the controller being reduced; and
(4) utilizing more advanced flash control logic which is implemented to raise the throughput for the flash memory access.
In accordance with another embodiment of the present invention, a system and method is provided for controlling flash memory in an electronic data flash card. The system and method provide a flash memory controller including a processor for receiving at least one request from a host system, and an index, which comprises look-up tables (LUTs) and a physical usage table (PUT). The index translates logical block addresses (LBAs) provided by the host system to physical block addresses (PBAs) in the flash memory. The index also contains information regarding the flash memory configuration. The processor selectively utilizes the index to determine the sectors of the flash memory that are available for programming, reprogramming, or reading. The flash memory controller further comprises a recycling first-in-first-out (FIFO) that recycles blocks of obsolete sectors so that they are available for reprogramming. The recycling operation involves copy and erase operations, and is performed in the background and thus hidden from the host system. Accordingly, the management of the flash memory and related intelligence resides in the flash memory controller instead of in the host system. As a result, the host system interacts with the flash memory controller without the host system having information regarding the physical configuration of the flash memory. Consequently, speeds at which data is written to and read from the flash memory is significantly increased while the flash memory remains compatible with the USB standard and ASIC architecture.
The following terms are defined as indicated in accordance with the present invention. Block: A basic memory erase unit. Each block contains numerous sectors, e.g., 16, 32, 64, etc. If any sector encounters write error, the whole block is declared a bad block and all valid sectors within the block are relocated to another block. Sector: A sub-unit of a block. Each sector typically has two fields—a data field and a spare field. Obsolete sector: A sector that is programmed with data but the data has been subsequently updated. When the data is updated, the obsolete data remains in the obsolete sector and the updated data is written to new sectors, which become valid sectors. Non-valid blocks: Blocks that contain obsolete sectors. Valid sector: A sector that has been programmed with data and the data is current, i.e., not obsolete. Wear leveling: A method for evenly distributing the number times each block of flash memory is erased in order to prolong the life of the flash memory. Flash memory can be block erased only a limited number of times. For example, one million is a typical maximum number of erases for NAND flash memory. Spare blocks: Reserved space in flash memory. Spare blocks enable flash memory systems to prepare for bad blocks. Cluster: Multiple data sectors used as file access pointers by an operating system to improve memory performance. In small mass-storage memory operation, a cluster normally is a combination of two data sectors, which is a minimum file size unit. 1 k byte is a typical cluster size for small blocks of memory (i.e., 512 bytes per sector), and 4 k bytes is a cluster size for larger blocks of memory (i.e., 2,112 bytes per sector). FAT: File allocation table having file address-linked pointers. A cluster is the unit for a FAT. For example, FAT16 means that a cluster address can be 16 bits. Directory and subdirectory: File pointers as defined by an operating system. Master boot record (MBR): A fixed location to store a root directory pointer and associated boot file if bootable. This fixed location can be the last sector of the first block, or the last sector of the second block if first block is bad. Packet: A variable length format for a USB basic transaction unit. A normal transaction in the USB specification typically consists of three packets—a token packet, a data packet, and a handshake packet. A token packet has IN, OUT, and SETUP formats. A data packet size can be varying in size, e.g., 64 bytes in USB revision 1.1, and 512 bytes in USB revision 2.0. A handshake packet has ACK or NAK formats to inform host of the completion of a transaction. Frame: A bulk transaction that is used that has a high priority for occupying a frame if USB traffic is low. A bulk transaction can also wait for a later frame if USB traffic is high. Endpoint: Three endpoints include control, bulk-in, and bulk-out. The control endpoint is dedicated to system initial enumeration. The bulk-in endpoint is dedicated to host system read data pipe. The bulk-out endpoint is dedicated to a host system write data pipe. Command block wrapper (CBW): A packet contains a command block and associated information, such as Data Transfer Length (512 bytes for example from byte8-11). A CBW always starts at the packet boundary, and ends as short packet with exactly 31 bytes transferred. All CBW transfers shall be ordered with LSB (byte0) first. Command Status Wrapper (CSW): A CSW starts at packet boundary. Reduced block command (RBC) SCSI protocol: a 10 byte command descriptor.
FIG. 7 is a block diagram showing a electronic data flash card (memory system)100 including aflash memory controller110 and aflash memory device112 in accordance with the present invention. Thehost system52 provides resources to process write and read transactions, and erase operations via theflash memory controller110. Theflash memory controller110 is coupled to ahost system52 via ahost system interface116. Thehost system52 can be a personal computer or other type of computer system. The operating system of thehost system52 can be Windows or MacOS but is not limited to these operating systems. In this specific embodiment, theflash memory system100 complies with the USB mass-storage class standard and thehost system interface116 is a USB connection. The USB specification can be revision 1.1 or 2.0 and above. Theflash memory controller110 and theflash memory112 can be either bus-powered or self-powered, and can be used as a mass storage device. The advantage of being used as a mass storage device is that it is a low-power device, it is easy to carry, and it has storage capacity larger than a traditional floppy disk.
Theflash memory controller110 includes adevice transceiver120, which converts analog signals to digital streams and provides a phase lock loop (PLL) circuit for generating precision clocks for internal data latching. For USB 2.0, the PLL functionality can be sensitive and thus useful due to its operating at 480 MHz. Theflash memory controller110 also includes a serial interface engine (SIE)122, which provides serial and parallel data conversion, packet decoding/generation, cyclic redundancy code (CRC) generation/checking, non-return-to-zero (NRZI) encoding/decoding, and bit stuffing according to the USB standard.Endpoints124 and125 receive information from thehost system52 regarding class type (e.g., mass-storage class), flash memory configuration information, and default control information. AnEndpoint126 receives information from thehost system52 regarding read transactions, and anendpoint128 receives information from thehost system52 regarding write transactions. A bulk-only transport (BOT)unit130 receives command block wrappers (CBW) and includes a datatransfer length register132 and a logical block address (LBA)register134.
In accordance with an aspect of the present invention, the allocation of PBAs to LBAs is performed entirely byflash memory controller110, thus allowinghost system52 to interact with flash memory device110 (i.e., perform read, write and erase operations) withouthost system52 having information regarding the actual physical location (configuration) of the data stored inflash memory device112. That is,flash memory controller110 utilizes arbitration logic and data that is entirely stored in electronic data flash card100 (i.e., not received from host system52) to identify bad blocks of memory cells inflash memory device112, to assign LBAs to the PBAs associated with good blocks of memory cells, to recycle non-valid blocks, and to perform wear leveling. Because each of these operations is performed independent ofhost system52, the operation ofhost system52 is enhanced. Additional information regarding the arbitration logic utilized byflash memory controller110 is provided in co-owned and co-pending U.S. patent application Ser. No. 11/471,000, entitled “MANAGING BAD BLOCKS IN FLASH MEMORY FOR ELECTRONIC DATA FLASH CARD”, which is incorporated herein by reference in its entirety.
Asector FIFO140 provides a caching feature when thehost system52 attempts to write data to theflash memory112. A FIFO-not-empty interruptsignal142 triggers an interrupt routine at an interrupthandler148 of aprocessor150. The interrupt routine responds to thehost system52 confirming that data was written to theflash memory112. In the mean time, theprocessor150 executes a write transaction.
A write look-up table (LUT)170, aread LUT172, and a physical usage table (PUT)180 provide an index showing the configuration of theflash memory112. The data stored in write and readLUTs170 and172 andPUT180 is controlled by the arbitration logic (discussed above) utilized byflash memory controller110. The write and readLUTs170 and172 facilitate write and read transactions, respectively, between thehost system52 and theflash memory112. The write and readLUTs170 and172 translate logical block addresses (LBAs) provided by thehost system52 to physical block addresses (PBAs) of theflash memory112. ThePUT180 performs physical sector mapping and provides a bitmap indicating programmed sectors, i.e., sectors to which data has already been written.
Aflash interface controller186 interfaces with theflash memory112 to carry out commands from theprocessor150. Theflash interface controller186 receives PBAs from the write and readLUTs170 and172 to service write and read requests.
Arecycling FIFO190 recycles blocks having obsolete sectors so that they can be reprogrammed, i.e., written to with new data. The recycling operations are executed immediately after and independently from write transactions so as to not interfere with the servicing of write transactions by theflash memory controller110.
For optimal ASIC implementation, the write and readLUTs170 and172, thePUT180, and therecycling FIFO190 are implemented with volatile random access memory (RAM), such as synchronous RAM (SRAM). Theflash memory112 can be implemented using one or more devices, each having one or more flash arrays.
FIG. 8 is a block diagram showing in more detail thewrite LUT170, theread LUT172, thePUT180, and therecycling FIFO190 ofFIG. 7 in accordance with the present invention. Thewrite LUT170 provides an index for the flash memory during write transactions and translates LBAs provided by the host system to PBAs of the flash memory. Thewrite LUT170 contains LBAs302a,302b,302c, and302d. For ease of illustration, only four LBAs per LUT are shown. Each of the LBAs302a-dincludes optional block-offset bits (bit5 to bit0). The block-offset bits correspond to particular sectors in a block.
Each LBA302a-dis associated with a PBA304a-d. Accordingly, each LBAa-d points to an associated PBAa-d, respectively. In this specific example, a PBA is 32-bits long. A sector field306 contains a string of bits indicating programmed sectors within a block.
Thewrite LUT170 records only the starting LBA for a particular write transaction. For example, if a particular write transaction requires two or more consecutive blocks, thewrite LUT170 records the starting LBA.
The readLUT172 provides an index for the flash memory during read transactions and translates LBAs provided by the host system to PBAs of the flash memory. The readLUT172 contains LBAs302′a,302′b,302′c, and302′d. The readLUT172 has the same fields as thewrite LUT170. After the completion of each write transaction, theread LUT172 is updated to reflect the changes to thewrite LUT170 such that the write and readLUTs170 and172 become identical. Once the read LUT is updated, it can be used as an index for read transactions.
ThePUT180 performs physical sector mapping and provides a bitmap indicating programmed sectors, i.e., sectors to which data has already been written. Whenever a write transaction occurs, thePUT180 records the usage information indicating the programmed sectors. This facilitates write transactions in that the processor of the flash memory controller can determine from thePUT180 which sectors are available for programming or reprogramming.
Therecycling FIFO190 recycles non-valid blocks and the recycling process occurs after each successful write transaction. Whenever a block having an obsolete sector is encountered, information regarding that block's physical address is placed in therecycling FIFO190 indicating it's a non-valid block. After finishing the valid sector copy-relocate operations, recyclingFIFO190 provides address information for performing non-valid block erase operations. Therecycling FIFO190 uses awrite pointer192 as updating FIFO address pointer for non-valid blocks and readpointers194 and196 as two read address reference pointers. Readpointer2196 is used for background recycling reading reference and readpointer1194 is a reference for valid block if the erase-recycling is successful. Read pointer1194 should never exceed readpointer2196. Both readpointers194 and196 should not overtakewrite pointer192. In accordance with an aspect of the present embodiment, the copy-relocate (for remaining valid sectors within non-valid blocks) and erase-recycling operations are performed in the background, i.e., independently from write transactions so as to not interfere with the write transactions.
FIG. 9 is a block diagram showing in more detail theflash memory112 ofFIG. 7 in accordance with the present invention. Theflash memory112 has a data structure that comprises adata field402 and aspare field404 for each PBA. Each field holds a certain number of bytes and the specific number will depend on the application. For example, a data field may have 512 bytes, 2,112, or more bytes, and the spare field can have 16, 64, or more bytes.
Thedata field402 stores raw data and thespare field404 stores information related to memory management. Thespare field404 includes a badblock indicator field406, an error correction code (ECC)field408, an erasecount field410, and anLBA field412. Because the LUT and PUT tables170,172, and180 are stored volatile memory and thus do not preserve the valid sector information, theLBA field412 is used to reconstruct the write and readLUTs170,172 and thePUT180 during system initialization and power failure.
The badblock indicator field406 indicates bad blocks. A bad block occurs when an attempt to write to a particular sector or to erase a particular block fails. A special badblock indicator field414 is located at the last block, a location, which is easier for the firmware to read, especially where there is one bit per sector. In this specific embodiment, 64 bits are used for a physical block to record the write sector failure (64 bits×4096 blocks=32 Kbytes=16 sectors=1 quarter block). Any is within a block means that the particular block is bad. To maintain reliability, four copies of bad block indicators are saved in the last block of the flash memory. Of course fewer or more copies can be utilized.
The need for flags in the flash memory is eliminated by the present invention. The only flag used is the valid sector flag used in the LUTs to assist in firmware decision making. This minimizes the complexity with regard to write and read transactions.
FIG. 10 is a high-level flow chart showing a method for managing flash memory in accordance with the present invention. First, at least one request from a host system is received utilizing a processor within a memory controller, in astep502. The request can be a write or read request. Then, the sectors of the flash memory that are available for programming, reprogramming, or reading are determined utilizing the processor and an index within the memory controller, in astep504. The host system interacts with the flash memory controller without the host system having information regarding the configuration of the flash memory.
In a specific embodiment, the flash memory controller receives a request from the host system in compliance with the USB mass-storage class. The following description illustrates this specific embodiment.
FIG. 11 is a flow chart showing a method for transmitting USB mass-storage class service requests in accordance with the present invention. First, the memory controller receives a request from the host system, in astep602. This step can be referred to as acommand transport step602. The request can be a write or read request. If the request is a write request, a write transaction is performed, in astep604. This step can be referred to as a data-outstep604. If the request is a read request, a read transaction is performed, in astep606. This step can be referred to as a data-instep606. Upon completion of a write or read transaction, an acknowledge packet is sent to the host system by the memory controller to confirm completion of the transaction, in astep608. This step can be referred to as astatus transport step608.
Thecommand transport step602 and the data-outstep604 are generally referred to as bulk-out transport steps since data packets are sent out from the host system. The data-instep606 and thestatus transport step608 are generally referred to as bulk-in transport steps since data packets are sent into the host system.
FIGS. 12A-C are block diagrams showing a command block wrapper (CBW)702, a reduced block command read format (RBC)704, and a command status wrapper (CSW)706 in accordance with the present invention. The USB standard involves three packets per request, which include theCBW702, theRBC704, and theCSW706. TheCBW702, theRBC704, and theCSW706 packets are also generally referred to as token, data, and acknowledge handshake packets, respectively, and are utilized in the command transport, data-in/out, and status transport steps602-608 ofFIG. 11, respectively.
Still referring toFIGS. 12A-C, theCBW702 contains information regarding what data from the host system is to follow. TheCBW702 is 31 bytes long and includes command decoding and direction, and a unique LBA. The LBA in theCBW702 can include information regarding the file allocation table (FAT) and directory pointers. TheCBW702 also contains the read/write direction inbyte15 as part of the RBC command. TheRBC704 contains information such as data to be written to the flash memory. TheRBC704 is a SCSI RBC. The length of the data can vary and is defined by different USB standard versions, e.g., 64 bytes in USB 1.1, 512 bytes in USB 2.0. TheCSW706 contains information regarding acknowledge procedures and information for terminating a transaction.Byte12 is a status byte.
FIG. 13 is a flow chart showing a method for reading, writing, and erasing in accordance with the present invention. Referring toFIGS. 12A-C and13 together, first, a request is received from the host system, in astep802. To comply with the USB standard, the request includes theCBW702, theRBC704, and theCSW706. Next, the type of command, whether a write or read request, is determined, in astep804. Next, registers for the CBW and CSW are initialized, in astep806.
If the request is a write request for a write transaction, the sector data FIFO in the flash memory controller is filled, and when 512 bytes of data are ready, a write pointer for the sector data FIFO is incremented and an interrupt is sent to the processor in the flash memory controller, in astep810. Next, the write transaction is executed, in astep812. Finally, an acknowledge packet is sent to the host system confirming that the write transaction was successfully completed, in astep814.
Immediately after a successful write transaction, the firmware of the flash memory controller checks the recycling FIFO status, in astep820. If the recycling FIFO is not empty, the recycling FIFO recycles obsolete sectors, in astep822.
If the request is a read request for a read transaction, the LBA in the CBW is compared with all existing entries of the sector FIFO, in astep828. If there is a match, the requested data is returned to the host system, in astep830. Next, an acknowledge packet is sent to the host system confirming that the read transaction was successfully completed, in astep832. If there is no match, the requested data is read from the flash memory, in astep834. Finally, a status/acknowledge packet is sent to the host system confirming that the read transaction was successfully completed, in a step836.
FIG. 14 is a high-level flow chart showing a method including a first phase of a write transaction, a second phase of the write transaction, a read transaction, and a recycling operation in accordance with the present invention. First, a CBW is received, in astep902. Next, it is determined whether the request is a write request, in astep904. Next, if the request is a write request, the sector FIFO is checked, in astep906. If the sector FIFO is not empty, the write transaction is then initiated.
To maintain block address consistency and to achieve write efficiency, the write transaction has two phases. In the first phase, data is written to a particular number of sectors and an acknowledge packet is then sent to the processor of the flash memory controller and to the host system indicating that the write transaction has been completed, in astep910.
If there is no subsequent read request pending, the second phase of the write transaction is initiated. Accordingly, valid sectors are copied from a non-valid block to a new address in another block, in astep920. Thecopy step920 is accomplished in the background to maintain data coherency.
If it is determined that the request is a read request and if there is a read request pending upon the completion of the first phase of the write transaction, the requested data is fetched from the flash memory using the PBA in the read LUT, in astep930. After the read request is serviced, and if there is a pending second phase of a write request, the second phase is executed, in thestep920.
Obsolete sectors are recycled by the recycling FIFO, in astep940, when there are no requests being serviced. In a specific embodiment, when the recycling FIFO completes the task of erasing one block, the firmware of the flash memory controller can return to servicing other requests from the host system.
FIGS. 15A-D are block diagrams illustrating exemplary results from first and second phases of a write transaction in accordance with the present invention. To further clarify the above-described features of the present invention, the following example is provided.FIGS. 15A-D show four write transactions including varying-length data strings.FIG. 15D shows a write transaction where data is updated. For ease of illustration, only four sectors per block are shown.
Two blocks (PBA0 and PBA1) of theflash memory112 have four sectors each. In a first write transaction, thewrite LUT170 writes to six physical sectors of theflash memory112, beginning the first physical block (PBA0). For this example, it is presumed that theflash memory112 is initially empty. For the purpose of this example, the labels A0-A5 represent data written during the first write transaction.
Bits in thePUT180 corresponding to the sectors of theflash memory112 show a 1 to indicate that those sectors have been programmed, i.e., occupied. The firmware of the flash memory controller utilizes thePUT180 to determine the available sectors. Accordingly, those sectors have data that cannot be reprogrammed until first erased but those sectors can be later read. Thewrite LUT170 having written to the sectors indicates the valid sectors with is. The readLUT172 information is copied from thewrite LUT170 information to reflect the most recent changes. However, theread LUT172 is copied from the previous version of thewrite LUT170 and is ultimately synchronous with thewrite LUT170 once the write phases are completed. Accordingly, until the readLUT172 is updated, it will show the pre-update information of thewrite LUT170 with 0 s shown to indicate empty sectors.
Referring toFIG. 15B, thewrite LUT170 has written new data B in the next available sector inPBA1. This is the second write transaction. Thewrite LUT170, thePUT180, and flash memory block reflect this update. The readLUT172 has been updated with the prior change but has not yet been updated to reflect the current change.
Referring toFIG. 15C, thewrite LUT170 has written new data C0 and C1 to the next available sectors. This is the third write transaction. Note that the data C0 and C1 cross the block boundary as does the data A0-A5. Again, thewrite LUT170, thePUT180, and flash memory blocks reflect this update. The readLUT172 has been updated with the prior change but has not yet been updated to reflect the current change.
Referring toFIG. 15D, thewrite LUT170 has written data to update existing data A0-A4 with updated data a0-a4. This is the fourth transaction. Because theblocks PBA0 andPBA1 need to first be erased before being reprogrammed, the updated data a0-a4 are written to the same sector number but to the next available block, i.e., PBA3-4, in the first phase of the write transaction. Once the first write phase is complete, acknowledge packets can then be sent to the processor of the flash memory controller confirming completion of the first phase of the write transaction. Thewrite LUT170, thePUT180, and the flash memory blocks reflect this update, and the readLUT172 has been updated with the prior change but has not yet been updated to reflect the current change.
Theblocks PBA0 andPBA1 have become non-valid because the data in some of their sectors became obsolete. Accordingly, those blocks can then be recycled by therecycling FIFO190. Therecycling FIFO190 has changed corresponding bits to 0 to indicate this. Thewrite pointer192 of therecycling FIFO190 is incremented to point to the next available position to store the nextnon-valid block address.
In the second phase of this write transaction, the data A5, B, and C0 are copied to new blocks, which are blocks PBA3-4 to maintain consistency in thewrite LUT170. Thewrite LUT170, thePUT180, and the flash memory blocks reflect this update. Theread LUT172 will then be updated to reflect the current change. Also both phases of the write transaction are complete, the write and readLUTs170 and172 will be identical.
FIG. 16 is a flow chart showing a method for implementing the first phase of the write transaction of PBA and sector count updating procedure ofFIG. 14 in accordance with the present invention, which basically does index mapping between LBAx and PBAx so that both read and write addresses are kept in tracking. Table 1 (below) is a simplified example of one entry of LUTs and FIFO with assumed 8 sectors per block in flash memory. An entry of 1 means sector data is valid, and 0 means sector is available for use. Please note that LUTs (mapping table) are pointed by LBAx, but FIFO is pointed by Wr_ptr and Rd_ptrs.
| TABLE 1 |
| |
| PBA w/o sector offset |
| Sector | | | | | | | |
| field |
| 0 | Sec 1 | Sec 2 | Sec 3 | Sec 4 | Sec 5 | Sec 6 | Sec 7 |
| |
Initially, an LBA and sector count (SC) from host system is evaluated, in astep1102. Then, LBA block offset bits are encoded into a sector count, in astep1104. The LBA points to a PBA in the flash memory. For example, if LBA is 0010,0101 and sector number is 16, then 0010 will be the initial LBAx block address for both LUT entry pointers. If the sector field of the PUT is 0, i.e., the sector is available, then the sector count register is equal to the CBW sector count and the PBA field of the write LUT will be loaded, in astep1106.
If the sector field of the write LUT is 1, this means the flash sector is used by previous programming, and the write pointer is positioned to the block to be erased, in astep1108. Next, the entry of recycling FIFO pointed to by write pointer will be filled by current PBAx, in astep1110. During the recycling operation, the block pointed to by the write pointer will be erased. Next, the sector field in the PUT is set to 1, in astep1112, where the PBA indicates that the sector is being used. Next, the sector number in incremented, in astep1114.
Next, the sector number is compared against the block boundary, in astep1116. If the sector number is aligned with the block boundary, the write pointer is incremented, in astep1118. The LBA in the write LUT is incremented, in astep1120, when flash block boundary is reached. Next, the write LUT is updated with the correct sector number position, in astep1122. If the sector number is not aligned with the block boundary, steps1118 and1120 are bypassed and the write LUT is updated with the correct sector number position, in astep1122.
Referring back to thestep1106, if the sector field of write LUT is 0, which means that the flash sector is not used by previous programming, i.e., the write transaction is not finished. The sector count is then compared to the sector count in the CBW, in astep1124. If they are the same, PBAx field of LUT pointed by LBAx will be updated in astep1126, then proceed to step1128. If the sector count register is not equal to the CBW sector count instep1124, the sector field will be set to 1 in both index look up tables and data will be written into the flash memory. Next, the sector number is incremented, in astep1128. After successful write into flash memory, sector count from CBW is decremented, in astep1130.
Next, the sector count is checked, in astep1132. If the sector count is equal to 0, the first phase of the write transaction terminates. If the sector count is not equal to 0, that means the host system did not send the correct amount of data. Accordingly, the sector FIFO is checked to determine whether there is any more available data, in astep1134. If not, a time-out sequence is executed, in astep1136, to flag an abnormal flow termination, and the sector FIFO is continually checked until sufficient data is available. If there is more available data in the sector FIFO, the sector number is compared against the block boundary, as in thestep1116.
FIG. 17 is a flow chart showing a method for implementing the second phase of the write transaction ofFIG. 14 in accordance with the present invention. First, the pointer values of the write and read pointers are compared, in astep1202. The sector field from the recycling FIFO entry pointed to by the read pointer indicates that a valid sector needs to be copied to a new PBA in order to achieve consistency in the write LUT. When the copy is done, the read LUT is updated to be identical to the write LUT, in astep1204. Next, the sector number pointed to by the read pointer is checked, in astep1206. If the sector number is equal to 1, the data in that sector is copied to a new block, in astep1208. Next, the sector number in the PUT is set to 1, in astep1210. Next, the write LUT sector field is updated, in astep1212. Next, the read LUT sector field is updated, in astep1214. Next, the sector number is incremented, in astep1216. Referring back to thestep1206, if the sector number is not equal to 1, the sector number is incremented, as in thestep1216.
The sector copying process will be completed as long as the sector number reaches the block boundary. The sector number is compared against the block boundary, in a step1218. If the sector number is aligned with the block boundary, the read pointer is incremented, in astep1220. Next, the read pointer is compared with the write pointer, as in thestep1202. If in the step1218, the sector number is not aligned with the block boundary, the sector number pointed to by the read pointer is checked, as in thestep1206.
FIG. 18 is a flow chart showing a method for implementing the read transaction ofFIG. 14 in accordance with the present invention. First, a CBW is received and recognized as read request, and an LBA and sector count is loaded from the CBW, in astep1302. Next, the LBA of the write LUT is translated into a corresponding PBA and sector number, in astep1304. Next, the sector field bit is checked, in astep1306. If the sector field bit is equal to 1, the data is read, the sector count is decremented, and the sector number is incremented in preparation for the next read transaction, in astep1308. If the sector field bit is not equal to 1, i.e., equal to 0, the LBA of the read LUT is translated into a corresponding PBA, in astep1309. Then the data is read, the sector count is decremented, and the sector number is incremented, as in thestep1308.
Next, an error correction code (ECC) calculation is performed, in astep1310. Next, the ECC result is compared with a value read from the flash spare field, in astep1312. If the values are identical, the sector count is checked, in astep1314. If the values are not identical, an ECC correction is performed, in astep1316, and then the sector count is checked, as in thestep1314. If the sector count has reached 0, i.e., equals 0, the read process terminates. If the sector count has not reached 0, the block boundary will also be checked, in astep1317. If the sector number is not aligned with the block boundary, the read LUT is updated with the correct sector number position, in astep1318. If the sector number is aligned with the block boundary, the LBA in the read LUT is incremented, in astep1320, and then the read LUT is updated with the correct sector number position, as in thestep1318.
A read transaction is executed immediate after a first phase of a write transaction. The read transaction has a higher priority than the second phase of a previous write transaction. This ensures optimal responses by the flash memory system. A read transaction is significantly faster than a write transaction and read transactions do not result in bad block situations, which only occur during write transactions and erase operations.
A read transaction differs from a disk cache function whenever the contents in the sector FIFO are available. This can happen when the LBA in the read LUT matches the previous LBA in the write LUT. The disk cache concept is borrowed from magnetic hard disk concepts and applied to small-capacity flash storage. This feature is typically disabled to save cache cost.
FIG. 19 is a flow chart showing a method for implementing the recycling operation ofFIG. 14 in accordance with the present invention. First, the recycling FIFO is checked, in astep1402. If the recycling FIFO is empty, the recycling operation terminates. If the recycling FIFO is not empty, the read pointer2 is checked, in astep1404, background erasing operation happens in this case, once erasing is successful, read pointer1 is incremented for another valid block reprogramming address checking operation. The two read pointers should not overtake the write pointer. However, the write pointer may loop back to its original starting position if both read pointers are executed. If the read pointer2 is positioned over the write pointer, the recycling operation terminates. If the read pointer2 is not positioned over the write pointer, the corresponding bit in the PUT is cleared, i.e., 0, in astep1406, to indicate that the physical block is now available for reprogramming. Next, the read pointer2 is positioned to point to the block to be erased, in astep1408. Next, the read pointer2 is incremented after successful erasing, in astep1410, for the next write address checking operation.
Pointer comparison for the recycling FIFO can be achieved by adding one more bit to the index of both the write and read pointers. For example, if the recycling FIFO contains eight PBA entries, four bits instead of three bits will be used for the pointers. The write pointer will start from 0 and increment to 7 and then cycle back to 0. The write pointer value should always be at least equal to or greater than the read pointers. When they are equal, it means that the recycling FIFO is empty. The depth, i.e., the number of entries, of the recycling FIFO affects the tradeoff between line-copy speed and the erase speed. Too few entries makes the recycling FIFO less optimal.
The flash memory controller of the present invention can perform multiple-block data access. The conventional flash memory device has a 512-byte page register built-in. The data write to the flash memory device has to write to the page register first and then to a flash memory cell. The conventional flash memory controller, as well as its built-in firmware, controls the flash memory access cycles. The conventional flash memory controller transfers one single block (512 bytes) of data to the page register of the flash memory device at a time. No other access to the flash memory is allowed once the 512 bytes page register is filled. Consequently, the conventional flash memory controller, which uses the single-block data access methodology, limits the performance of flash memory devices.
In accordance with the present invention, the flash memory controller utilizes a 2K or larger size page register. The flash memory controller of the present invention functions as a multiple-block access controller by sending multiple blocks of data simultaneously to a flash memory to fill up the page register. This significantly improves the performance of the data transfer. Compared to the conventional single-block data-transfer controller, which transfers a single block at a time, the data transfer performance using the flash memory controller of the present invention is significantly improved.
The flash memory controller of the present invention can also provide dual channel processing to improve performance of the flash memory system. Dual channeling provides a second channel, or “freeway,” for executing transactions between the flash memory controller and the flash memory device. A conventional flash memory controller uses a single memory bus such that one or more flash memory devices attached to it. However, the conventional architecture limits the performance of the conventional flash memory controller.
In accordance with the present invention, at least two sets of memory buses are utilized. Each set of memory buses is coupled to separate flash memory devices. The memory controller can access flash memory devices together or separately. As a result, transactions can be executed twice as fast utilizing dual channel processing. Furthermore, each memory bus can also be further expanded to multiple sets of memory buses.
The flash memory controller of the present invention can also interleave operations. A conventional flash memory controller uses a single set of memory buses such that one or more flash memory devices are attached to it. However, the conventional flash memory controller can only access the flash memory devices one at a time. Accordingly, the conventional architecture limits the performance of the conventional flash memory controller.
In accordance with the present invention, at least one or two extra sets of memory control signals (such as separate Chip Enable and Busy signals) are utilized. Furthermore, a shared memory bus having at least two banks of flash memory devices are attached to the shared memory bus. The flash memory controller of the present invention can access one bank of flash memory devices while the other bank is busy reading or writing. Accordingly, the flash memory controller of the present invention fully utilizes the shared memory bus and thus significantly increase the performance. Furthermore, the number of pins of the flash memory controller are reduced by sharing memory I/O and control signals. This minimizes the cost to make flash memory devices.
In accordance with the present invention, one in the art can integrate functions of multiple block access, multiple bank interleaving, and multiple channel operations together in a memory access cycle of a single chip to achieve maximum performance.
In accordance with the present invention, the flash memory controller can be applied to USB as well as PCI-Express plug and receptacle systems. Also, the flash memory controller can be applied to other embodiments involving SD, MMC, MS, CF, IDE, and SATA plug and receptacle systems.
According to the system and method disclosed herein, the present invention provides numerous benefits. For example, it shifts the management of the flash memory and related intelligence from the host system to the flash memory controller so that the host system interacts with the flash memory controller without the host system having information regarding the configuration of the flash memory. For example, the flash memory controller provides LBA-to-PBA translation, obsolete sector recycling, and wear leveling. Furthermore, the recycling operations are performed in the background. Furthermore, flash specific packet definitions and flags in the flash memory are eliminated. Furthermore, the flash memory controller provides multiple-block data access, dual channel processing, and multiple bank interleaving. Consequently, speeds at which data is written to and read from the flash memory is significantly increased while the flash memory remains compatible with the USB standard and ASIC architecture.
A system and method in accordance with the present invention for controlling flash memory are disclosed. The system and method comprise a processor for receiving at least one request from a host system, and an index, which comprises look-up tables (LUTs) and a physical usage table (PUT). The index translates logical block addresses (LBAs) provided by the host system to physical block addresses (PBAs) in the flash memory. The index also contains intelligence regarding the flash memory configuration. The processor can utilize the index to determine the sectors of the flash memory that are available for programming, reprogramming, or reading. The flash memory controller further comprises a recycling first-in-first-out (FIFO) that recycles blocks having obsolete sectors so that they are available for reprogramming. The recycling operation involves copy and erase operations, and is performed in the background and thus hidden from the host system. Accordingly, the management of the flash memory and related intelligence resides in the flash memory controller instead of in the host system. As a result, the host system interacts with the flash memory controller without the host system having information regarding the configuration of the flash memory. Consequently, speeds at which data is written to and read from the flash memory is significantly increased while the flash memory remains compatible with the USB standard and ASIC architecture.
Although the present invention disclosed herein is described in the context of an electronic data flash card with or without fingerprint verification capability, the present invention may apply to other types of memory systems and still remain within the spirit and scope of the present invention. In addition, although the present invention disclosed herein is described in the context of the USB standard, the present invention may apply to other standards and still remain within the spirit and scope of the present invention. Further, embodiments of the present invention can be implemented using hardware, software, a computer readable medium containing program instructions, or combination thereof. Accordingly, many modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the appended claims.