JP2007199828A - Nonvolatile storage device and address management method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a nonvolatile storage device that uses a high-capacity flash memory having many physical blocks and can execute retrieval of an empty block in a short time. <P>SOLUTION: The addresses of the physical blocks after data writing are listed on a logical/physical conversion table 106, and the addresses of the physical blocks after data deleting are listed on an empty block table 107. A controller 104, in writing data in the flash memory 103, (a) selects the address of an arbitrary physical block in which effective data is not written from the empty block table 107, and writes data into the physical block of the address, and (b) stores the address of the physical block in which data is written in the logical/physical conversion table 106 in a form corresponding to the logic address provided from the outside. <P>COPYRIGHT: (C)2007,JPO&INPIT

Description

  The present invention relates to a nonvolatile memory device using a nonvolatile memory such as a flash memory and an address management method thereof.

  In recent years, memory cards equipped with non-volatile memory have been expanding the market as memory cards for digital cameras and mobile phones. Memory cards are also expanding to higher capacities for applications such as increasing the pixel count of digital cameras and recording video on mobile phones.

  For this reason, in order to realize a larger capacity memory card, a method for easily and rapidly controlling a large capacity nonvolatile memory is required. In order to handle a larger capacity non-volatile memory, a volatile memory for managing a larger capacity address information is required.

  Address information is managed using a logical-physical conversion table and an erased table. The logical-physical conversion table converts the correspondence between an address (hereinafter referred to as a logical address) specified by a host device outside the memory card and an address of a nonvolatile memory (hereinafter referred to as a physical address), that is, a logical address into a physical address. It is a table storing information. The erased table is a table that stores, for each physical address per erase unit of the nonvolatile memory, information indicating whether the physical address has been written or erased.

Hereinafter, a configuration of a conventional nonvolatile memory device and a writing method will be described with reference to the drawings (see Patent Document 1).
FIG. 10 is a block diagram of a memory card which is a kind of nonvolatile storage device. The memory card 702 is mainly composed of a flash memory 1003 composed of a nonvolatile memory for storing data, and a controller that controls the I / F with the host 1001 and controls the flash memory 1003. The controller 1004 has an address management table composed of a volatile memory for managing the flash memory 1003. The address management table 1005 includes a logical / physical conversion table 1006 that stores, as information, a physical address of the flash memory 1003 corresponding to a logical address designated by the host 1001, and whether the physical block state of the flash memory 1003 has been written or erased. Is composed of an erased table 1007 stored as bit information.

  FIG. 11 is a diagram showing an internal configuration of the flash memory 1003. The flash memory 1003 is numbered in units of physical blocks, which are data erasure units, and each has 1024 physical blocks 1101 PBA0000 to PBA0123. The logical-physical conversion table 1006 stores 0000 to 1023 which are addresses of the physical blocks.

  FIG. 12A is a diagram showing the configuration of the logical / physical conversion table 1006. A capacity that can be covered by 1000 physical blocks out of 1024 physical blocks of the flash memory 1003 is an area accessible from the host 1001. Therefore, the logical addresses 0x000 to 0x3E7 (expressed in 12-hexadecimal notation and 0-999 in decimal notation) are areas of the logical-physical conversion table, and each of the corresponding physical blocks when the logical address is the address of the table. The address is stored as data. The area of addresses 0x3E8 to 0x3FF following the logical-physical conversion table is an area where nothing is used as a spare area.

  On the other hand, FIG. 12B shows the configuration of the erased table 1007. Corresponding to the number of physical blocks 1024 in the flash memory 1003, each is 1-bit information, the erased physical block is represented by data “1”, and the written physical block is represented by data “0”.

  FIG. 13 is a flowchart showing the operation of the controller 1004 at the time of writing, FIGS. 14A and 14B are diagrams showing the states of the logical-physical conversion table 1006 and the erased table 1007 before writing, and FIG. (B) is a diagram showing the state of the logical-physical conversion table 1006 and the erased table 1007 after writing. Hereinafter, a conventional writing method of the nonvolatile memory device will be described with reference to FIGS.

  Before entering the write flow of FIG. 13, the host 1001 sends a write command and write data to the memory card 1002. Here, a case where the host 1001 writes data to the logical address 0x100 will be described.

  Upon receiving a command from the host 1001, the controller 1004 determines a write destination (step S1301). Specifically, the erased physical block is obtained by searching the erased table 1007 for the location where the data “1” is stored.

  At this time, since it is necessary to sequentially read and check the erased table 1007, it takes a considerable time to search for the erased physical block. Since 1000 physical addresses are registered in the erased table 1007 with respect to 1000 logical addresses registered in the logical-physical conversion table 1006, 1001 bit information is finally read under the worst condition. An erased physical block can be obtained. In the example shown in FIG. 14B, information indicating that the physical block address 0x321 is an erased physical block is obtained by searching the erased table 1007 and reading the data “1” stored at the address 0x321.

  Next, the controller 1004 writes the data transferred from the host 1001 to the physical block 0x321 determined in S1301 (S1302).

  Next, the controller 1004 erases the old data remaining in the flash memory 1003 (S1303). Since the old data should exist in the physical block of the address originally written in the logical-physical conversion table 1006, 0x123 stored in the logical address 0x100 designated by the host 1001 in FIG. This is the address of the physical block where the data exists. The data of this physical block 0x123 is erased.

  Next, the table is updated (S1304). As shown in FIG. 15A, the address 0x321 of the physical block written in S1302 is stored at the position corresponding to the logical address 0x100 designated by the host in the logical-physical conversion table 1006, and shown in FIG. Thus, in the erased table 1007, the bit information at the position of the address 0x321 of the written physical block is updated to “0”, and the bit information at the position of the address 0x123 of the erased physical block is updated to “1”. To do. FIG. 15A shows a state after the logical-physical conversion table 1006 is updated, and FIG. 15B shows a state after the erased table 1007 is updated.

In this way, the controller 1004 finishes writing. Thereafter, the controller 1004 notifies the host 1001 of the end of writing, whereby the writing of data from the host 1001 to the memory card 1002 is completed.
JP 2001-142774 A

In the above conventional writing method, when writing data to the flash memory, the controller searches for the write destination physical block using the empty block table in order to determine the physical block to be written. However, the empty block table is held in bitmap format, and in order to search for empty blocks, in the worst case, it takes time to search almost the entire area of the bitmap. Has become a situation that can not be ignored.
An object of the present invention is to provide a non-volatile storage device capable of executing a search for an empty block in a short time in view of the above conventional problems.

In order to achieve the above object, the nonvolatile memory device of the present invention provides:
A non-volatile memory composed of a plurality of physical blocks which are erasure units, and an address is assigned to each physical block;
An address management table for managing the address of each physical block, and a controller for controlling data writing to the plurality of physical blocks or data reading from the plurality of physical blocks based on the address A non-volatile storage device,
The address management table is
(A) a logical-physical conversion table that stores the address of a physical block in which valid data is written in a form corresponding to a logical address provided from the outside;
(B) It is composed of an empty block table for storing addresses of physical blocks to which valid data is not written.

  In the nonvolatile storage device of the present invention, an empty block index is provided in the address management table, and an address of a physical block to which data is next written out of physical block addresses stored in the empty block table. Is preferably stored. The free block index may cyclically select addresses of a plurality of physical blocks stored in the free block table.

  In the nonvolatile storage device of the present invention, when the number of physical blocks to which valid data is not written exceeds the number that can be stored in the empty block table, an identification flag is attached to the address and It is preferable to store in the object conversion table.

  In the nonvolatile memory device of the present invention, a part of the empty block table may be used as a bad block table, and the bad block address may be stored in the bad block table. Similarly, a bad block count may be provided in the address management table, and the number of bad blocks stored in the bad block table may be stored in the bad block count.

Next, the address management method of the nonvolatile memory device of the present invention is
A non-volatile memory composed of a plurality of physical blocks which are erasure units, and an address is assigned to each physical block;
An address management table for managing the address of each physical block, and a controller for controlling data writing to the plurality of physical blocks or data reading from the plurality of physical blocks based on the address A non-volatile storage device address management method comprising:
The controller is
(A) Select an arbitrary address from the free block table storing the address of the physical block to which valid data is not written, and write the data to the physical block at that address;
(B) Store the address of the physical block in which the data is written in a logical-physical conversion table that manages the address of the physical block in which valid data is written, in a form corresponding to the logical address provided from the outside. It is characterized by.

  In the nonvolatile memory device address management method of the present invention, after the address of the physical block is written in the logical-physical conversion table, it is first stored in the logical-physical conversion table in a form corresponding to the logical address. It is preferable to erase the data of the physical block at the address and store the address of the physical block in the empty block table.

  The nonvolatile storage device of the present invention abolishes the management of empty blocks by the erased table, holds the addresses of the empty blocks of the flash memory in a list format, and sequentially uses the write destination physical block according to the list order, The search time for empty blocks can be substantially eliminated.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
(Embodiment 1)
FIG. 1 is a block diagram of a nonvolatile memory device according to Embodiment 1 of the present invention.
In FIG. 1, a memory card 102 as a non-volatile storage device mainly controls the I / F between the flash memory 103 composed of a non-volatile memory for storing data and the host 101 and the control of the flash memory 103. It consists of a controller that performs

  The controller 104 incorporates an address management table 105 composed of a volatile memory for managing the flash memory 103. In the address management table 105, 106 is a logical-physical conversion table that stores the address of the physical block of the flash memory 103 corresponding to the logical address specified by the host 101, and 107 is data of the logical address specified by the host in the flash memory 103. Is a free block table in which a plurality of physical blocks other than the physical block in which are stored are stored as a list of physical addresses.

  Therefore, the logical-physical conversion table 106 and the empty block table 107 store lists of physical block addresses of the flash memory 103, but do not store overlapping data. An empty block index 108 stores index information indicating which row of the list of the empty block table 107 is selected.

  As shown in FIG. 11, the flash memory 103 is numbered in units of physical blocks, which are data erasing units, and each has 1024 physical blocks from PBA0000 to PBA0123. Both the logical-physical conversion table 106 and the empty block table 107 store addresses 0000 to 1023 that are addresses of the physical blocks.

  FIG. 2 is a diagram showing the configuration of the logical / physical conversion table 106 and the empty block table 107. The number of physical blocks in the flash memory 103 is 1024, which is a power of 2. This is true for all common memories, which usually have a power of two. This is because having an address that is a power of 2 has the highest capacity efficiency with respect to area. Therefore, in the present embodiment, a case will be described in which the logical-physical conversion table 106 and the empty block table 107 are combined on one volatile memory.

  The memory card 102 does not have the same capacity as all the physical blocks of the flash memory 103, and the capacity of the memory card 102 is actually set smaller than the capacity of the flash memory 103. In general, such a configuration is adopted due to the presence of defective blocks in the flash memory 103 and the problem of wear leveling of physical blocks. In the example of FIG. 2, the logical addresses are indicated by 0x000 to 0x3E7 (expressed in hexadecimal 12 bits and 0-999 in decimal notation). That is, addresses 0x000 to 0x3E7 are areas of the logical-physical conversion table 106, and in this table, the addresses of the corresponding physical blocks when the logical addresses are the addresses of the tables are stored as data.

  In FIG. 2, the area of addresses 0x3E8 to 0x3FF following the logical address area is the free block table 107, and addresses of physical blocks not corresponding to the logical address of the host are listed.

  The number of words (here, 0 × 400 words) that is the sum of the number of words in the logical-physical conversion table 106 and the number of words in the free block table 107 is equal to the number of physical blocks in the flash memory 103. This is because a physical block in which valid data is written is listed in the logical-physical conversion table, and a physical block in which valid data is not written is listed in the free block table.

  3 is a flowchart showing the control operation of the controller 104 when writing data to the flash memory 103, and FIGS. 4A and 4B are the logical-physical conversion table 106 and the empty block table before and after data writing. FIG. Hereinafter, an address management method for writing data to the memory card will be described with reference to FIGS.

  Before entering the write flow of FIG. 3, the host 101 sends a write command and write data to the memory card 102. Here, a case where the host 101 writes data to the logical address 0x100 will be described.

  In response to the command from the host 101, the controller 104 acquires an index (step S301). Specifically, the value of the free block index 108 is acquired. Here, it is assumed that the value of the empty block index 108 is 0x009.

  Next, the controller 104 determines the write destination (S302). Specifically, the physical block whose address is stored in the free block table 107 corresponding to the index acquired in step S301 is determined as the write destination of the flash memory 103. Since the index is 0x009, the physical block address stored in 0x3F1 (= 0x3E8 + 0x009) with 0x3E8 that is the start address of the empty block table 107 as an offset, that is, 0x321 stored in the address 0x3F1 in FIG. This is the address of the write destination physical block. This write destination determination can be made immediately because it only reads the data at the designated address, and the conventional search operation is not necessary.

  Next, the controller 104 writes the data transferred from the host 101 to the physical block address 0x321 determined in step S302 (S303).

  Next, the controller 104 erases old data remaining in the flash memory 103 (S304). Since the old data should exist in the physical block of the address originally written in the logical-physical conversion table 106, the address 0x123 stored in the logical address 0x100 designated by the host 101 in FIG. Is the address of the physical block of the flash memory 103 where The data at address 0x123 of this physical block is erased.

  Next, the table is updated (S305). As shown in FIG. 4B, the address 0x321 of the physical block written in the current step S303 is stored at the position corresponding to the logical address 0x100 designated by the host in the logical-physical conversion table 106, and the free block table 107 is stored. The address 0x123 of the physical block that has been erased in step S304 is stored in 0x3F1, which is the position designated from the index.

  Finally, index increment is performed (S306). Specifically, an address 0x00A obtained by incrementing the address 0x009 stored in the free block index 108 by 1 is stored in the free block index 108. When the index overflows beyond the area of the free block table 107, the index value is set to 0x000 and looped. Thus, the free block index 108 cyclically stores the addresses stored in the free block table 107.

  In this way, the controller 104 ends the writing. Thereafter, the controller 104 notifies the host 101 of the end of writing, whereby the writing of data from the host 101 to the memory card 102 is completed.

  In the present embodiment, the number of physical block addresses listed in the free block table 107 is limited to 24, and the physical block exceeding that number has no valid data corresponding to the logical block, or is in the logical block. When the corresponding data has been erased and is in an unwritten state, it can be dealt with by writing the address of the physical block together with a flag indicating the unwritten state in the logical-physical conversion table 106, for example.

  FIG. 5 shows the logical-physical conversion table 106 in a state where all the physical blocks have already been erased. The most significant bit of the physical block address is set to “1” (“8” in hexadecimal notation). Represents a data erased block. FIG. 6 shows the state of the logical-physical conversion table 106 and the empty block table 107 before and after data writing when the above configuration is adopted. Note that the value of the empty block index 108 is 0x000. Therefore, the write start address is offset value 0x3E8 + 0x000 = 0x3E8.

  A simple flow of writing will be described with reference to FIG. 6. Data is written to the physical block 0x3E8 specified by the free block index 108. In the description of FIG. 4, the old data is erased following the data writing. However, in FIG. 6, since all the physical blocks have been erased, it is not necessary to erase the old data. Therefore, the table is updated next.

  As indicated by an arrow in FIG. 6, the address 0x3E8 of the physical block that has been written is stored at the position corresponding to the logical address 0x000 in the logical-physical conversion table 106 designated by the host 101, and stored at the logical address 0x000 instead. The physical block address 0x000 (in the logical-physical conversion table 106, “1” indicating the erased block is added to the most significant bit and 0x800 is stored, but the physical block address has the most significant bit “1”. The removed portion (0x00) is stored in 0x3E8, which is the position designated by the empty block index 108. Finally, index increment is performed, and 0x001 obtained by incrementing 0x000 stored in the free block index 108 by 1 is stored in the free block index 108.

By repeating the above operation, data is written in the physical block and the logical-physical conversion table 106 and the empty block table 107 are updated.
(Embodiment 2)

In the second embodiment of the present invention, management of a physical address when a defective block is newly added is added to the address management table 105.
FIG. 7 is a block diagram of the nonvolatile memory device according to the second embodiment. The difference from the configuration of the first embodiment shown in FIG. 1 is that a bad block table 701 and a bad block count 702 are added to the address management table 105. The bad block table 701 holds physical addresses of bad blocks (bad blocks) in a list format. Since the number of empty blocks decreases when a bad block occurs, the empty block table 107 is used. . The bad block count 702 holds the number of physical blocks of defective blocks.

  FIG. 8 is a diagram showing the configuration of the logical-physical conversion table 106, the empty block table 107, and the bad block count 702. In FIG. 8, the addresses 0x000 to 0x3E7 are the areas of the logical-physical conversion table 106 as in FIG. A part of the empty block table 107 is allocated to the bad block table 701, and the number of bad block counts 702 matches the number of addresses of defective blocks included in the bad block table 701. When there is no defective block, the bad block table 701 is lost or the capacity becomes zero.

  The address management method for writing data to the physical block is basically the same as the method described in the first embodiment, but the processing in the free block index 108 is different. In other words, the value of the empty block index 108 cyclically changes from (the maximum value of the logical address + 1) to (the maximum value of the physical address−the number of bad blocks).

  For example, when there is no bad block (the bad block count value is 0), as described in the first embodiment, the value of the empty block index 108 continues to 0x3E8, 0x3E9, ... 0x3FE, 0x3FF, and so on. However, if there are two bad blocks (the bad block count value is 2), it continues with 0x3E8, 0x3E9, ... 0x3FC, 0x3FD, and then returns to the beginning.

  As described above, in the present embodiment, the bad block address can be easily managed by adding the bad block table 701 to the address management table 105.

In each of the above embodiments, the example in which the address management table having a capacity capable of managing all the logical addresses of the memory card is arranged on the volatile memory has been described. However, the non-volatile memory (for storing data) is described. The present invention is also applicable to a case in which a part of the address management table is cached in a volatile memory and used as necessary in a non-volatile memory such as another FeRAM or RRAM). Applicable. By doing so, the capacity of the volatile memory can be reduced. FIG. 9 shows a case where the whole is divided into four and two of them are cached in a volatile memory. In this case, the capacity of the volatile memory can be halved by caching while selectively switching the areas 0 to 2 and always caching the area 3.
In each of the above embodiments, the example in which the address management table is arranged on the volatile memory has been described. However, any memory that can be rewritten in units of words can be applied to the present invention. An address management table may be arranged on a non-volatile memory.

  Since the nonvolatile memory device according to the present invention can search for a writable free block at high speed even when a flash memory having more physical blocks is used, moving image recording that requires a larger capacity nonvolatile memory device It is useful as a recording medium for AV equipment such as playback devices.

Block diagram of the nonvolatile memory device according to Embodiment 1 of the present invention The figure which showed the structure of the address management table in the same Embodiment 1. The flowchart which showed the write-in operation of the controller in Embodiment 1 The figure which showed the address map of the address management table before and behind writing in Embodiment 1 The figure which showed the other example of the address map of the address management table in Embodiment 1 The figure which showed the address map before and behind writing using the address management table of FIG. Block diagram of a nonvolatile memory device according to Embodiment 2 of the present invention The figure which showed the structure of the address management table in Embodiment 2 The figure which shows the example which the address management table was divided | segmented into the several area | region, and was stored in the volatile memory A block diagram of a conventional nonvolatile memory device Diagram showing internal structure of non-volatile memory The figure which showed the address map of the logical-physical conversion table and the erased table in the conventional nonvolatile memory device Flow chart showing controller and roller writing operation in a conventional nonvolatile memory device The figure which showed the address map of the logical-physical conversion table before writing in the conventional non-volatile memory device, and the erased table The figure which showed the address map of the logical-physical conversion table after writing in the conventional non-volatile memory device, and the erased table

Explanation of symbols

101 Host 102 Memory card 103 Flash memory 104 Controller 105 Address management table 106 Empty block table 107 Erased table 108 Empty block index 701 Bad block table 702 Bad block count

Claims (15)

A non-volatile memory composed of a plurality of physical blocks which are erasure units, and an address is assigned to each physical block;
An address management table for managing the address of each physical block, and a controller for controlling data writing to the plurality of physical blocks or data reading from the plurality of physical blocks based on the address A non-volatile storage device,
The address management table is
(A) a logical-physical conversion table that stores the address of a physical block in which valid data is written in a form corresponding to a logical address provided from the outside;
(B) A non-volatile storage device comprising an empty block table for storing addresses of physical blocks to which valid data is not written.   A free block index is provided in the address management table, and an address of a physical block to which data is next written out of physical block addresses stored in the free block table is stored in the free block index. Item 4. The nonvolatile memory device according to Item 1.   The non-volatile storage device according to claim 2, wherein the free block index cyclically selects addresses of a plurality of physical blocks stored in the free block table.   When the number of physical blocks to which valid data has not been written exceeds the number that can be stored in the empty block table, an identification flag is attached to the address and stored in the logical-physical conversion table. The nonvolatile memory device according to claim 1.   The nonvolatile memory device according to claim 1, wherein a part of the empty block table is used as a bad block table, and an address of a defective block is stored in the bad block table.   6. The nonvolatile memory device according to claim 5, wherein a bad block count is provided in the address management table, and the number of defective blocks stored in the bad block table is stored in the bad block count.   The nonvolatile storage device according to claim 1, wherein the address management table is arranged on a volatile memory or a nonvolatile memory.   The nonvolatile memory according to claim 1, wherein the address management table is held in a nonvolatile memory, and a part of the address management table is cached and used in a volatile memory as necessary. Sex memory device. A non-volatile memory composed of a plurality of physical blocks which are erasure units, and an address is assigned to each physical block;
An address management table for managing the address of each physical block, and a controller for controlling data writing to the plurality of physical blocks or data reading from the plurality of physical blocks based on the address A non-volatile storage device address management method comprising:
The controller is
(A) Select an arbitrary address from the free block table storing the address of the physical block to which valid data is not written, and write the data to the physical block at that address;
(B) Store the address of the physical block in which the data is written in a logical-physical conversion table that manages the address of the physical block in which valid data is written, in a form corresponding to the logical address provided from the outside. An address management method for a nonvolatile storage device.   After the address of the physical block is written in the logical-physical conversion table, the physical block data of the address previously stored in the logical-physical conversion table in a form corresponding to the logical address is erased, and the physical block The address management method for a non-volatile storage device according to claim 9, wherein the address is stored in the empty block table.   11. The address of a physical block to which data is next written among physical block addresses stored in the free block table is stored in a free block index provided in the address management table. The address management method of the non-volatile storage device described.   12. The nonvolatile memory device address management method according to claim 11, wherein the free block index cyclically selects addresses of a plurality of physical blocks stored in the free block table.   When the number of physical blocks to which valid data has not been written exceeds the number that can be stored in the empty block table, an identification flag is attached to the address and stored in the logical-physical conversion table. The address management method for a nonvolatile memory device according to claim 9.   14. The address management method for a non-volatile storage device according to claim 9, wherein the address management table is arranged on a volatile memory or a non-volatile memory. The nonvolatile memory according to claim 9, wherein the address management table is held in a nonvolatile memory, and a part of the address management table is cached and used in a volatile memory as necessary. Address management method for portable storage device

Images