Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2001-11-15
2004-03-23
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S103000, C711S161000
Reexamination Certificate
active
06711663
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an algorithm of flash memory and, more particularly, to an algorithm of flash memory capable of quickly building a table and preventing disorder of data due to abnormal disconnection and a control system thereof.
BACKGROUND OF THE INVENTION
Along with continual progress of the information industry, high-speed data storage devices (memories) play very important roles due to influence of ever faster CPUs and development of information appliance (IA) products. Because flash memories have the characteristics of non-volatility and easily changing access of data, they have been eagerly expected by users.
As shown in
FIG. 1A
, at least a flash storage device (NAND type flash are the most popular)
11
~
19
is connected to a host computer
29
mainly via a control device
20
. Of course, the control device
20
can also be built in a subsystem of the host computer
29
. The control device
20
comprises a microprocessor
25
therein, which can be connected to the host computer
29
via an interface controller
24
conforming to the protocol of PCMCIA, IDE, ATA, ATAPI, USB, or their combination. One end of the microprocessor
25
can be connected to the data storage device
11
via a storage control logic circuit
26
. The microprocessor
25
can also be connected to a buffer controller
22
. The buffer controller
22
can temporarily store the data to be accessed by the host computer
29
into a data storage region
21
(a first buffer
211
, a second buffer
213
, and an N-th buffer
219
). Additionally, an ECC logic circuit
23
is respectively connected to the microprocessor
25
, the buffer controller
22
, and the storage control logic circuit
26
. The ECC logic circuit
22
is controlled by the microprocessor
25
to give a corresponding error-correcting code (ECC) data to a data sector to be accessed. Moreover, the microprocessor
25
can be connected to a lookup table
255
, which can be used to keep logic block addresses (L
0
~L
m+1
) and all physical block addresses (PBA) of the corresponding data storage device
11
.
As shown in
FIG. 1B
, a memory used by the lookup table
255
such as a random access memory (RAM) mainly uses a word as an access unit, and is partitioned into a plurality of word addresses LBA (logic block address, L
0
, L
1
, . . . , L
m
, L
m+1
, . . . ). Each logical block address includes an address data mapping to a corresponding PBA (physical block address; B
3
, B
2
, . . . , B
m
, B
m+1
, . . . ). The flash memory
11
mainly uses a block as an access unit, and is partitioned into a plurality of physical block addresses B
0
~B
n
. A physical block (Data
0
~Data
n
) of each physical block address includes a plurality of block pages. Each page corresponds to a sector of smallest storage unit at the host end. An error-correcting code (ECC; E
0
~E
n
) field of each corresponding page in a record block and an LBA (L
2
, L
3
, L
1
, . . . , L
m+1
) field recording a corresponding logical block address data can be attached behind each physical block. The PBA field of the lookup table
255
corresponds to the LBA field of the memory
11
. For example, the logical address data of the data Data
0
stored in the physical block B
0
of memory points to the LBA L
2
in the lookup table
255
. Therefore, L
2
is recorded in the LBA field thereof (this data will be stored and will not disappear even if disconnection occurs). The PBA field of the sector L
2
of the lookup table
255
points to the B
0
(this data will disappear after disconnection occurs), as the double arrowheads of the solid line shown in FIG.
1
B.
When the system is turned on, the PBA fields of the lookup table
255
do not exist. The microprocessor
25
will scan all physical block addresses and logical block addresses (LBAs) of the flash memories
11
~
19
, and fill corresponding relations into the physical block address (PBA) fields according to the LBAs, thereby building the complete lookup table
255
. However, this way of scanning and then building the lookup table is inconvenient and consumes much operation time.
Moreover, the block B
0
is used as a unit when erasing or accessing data due to the structure of the flash memory
11
. Therefore, when there exists a physical block to be modified (e.g., the B
2
), it is necessary to store the data Data
2
originally stored in the block B
2
into a clean physical block (e.g., B
m+1
), record the logical address L
1
in the LBA field behind the physical block B
m+1
, and then erase the Data
2
in the block B
2
to be modified so that the block becomes a clean block or is recorded as not in use. However, if an abnormal situation such as a sudden disconnection or a crash occurs when the clean block (e.g., B
m+1
) has finished the steps of storing data and filling logical address data but the block B
2
to be modified has not yet finished the step of erasing, the host computer will be turned on again and the microprocessor
25
will again scan all physical block addresses of the memory
11
. The situation that the two data blocks B
2
and B
m+1
are recorded to have the same logical block address L
1
and point to the same corresponding address in the lookup table
255
(as the double arrowheads of the dash line shown in FIG.
1
B), or the situation that some blocks may be disconnected may occur. Erroneous connection of data or even damage of data may thus easily arise.
Accordingly, the present invention aims to propose an algorithm of flash memory capable of quickly building a lookup table and preventing disorder of data due to abnormal disconnection and a control system thereof.
SUMMARY OF THE INVENTION
The primary object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing disorder of data due to abnormal disconnection and a control system thereof, wherein pages of a physical block are utilized to store data of a lookup table. When the system is turned on, quick switching is achieved by directly storing into a buffer from the block pages without a microprocessor utilizing a scan program to perform scan of logical addresses to all physical blocks of each memory. Therefore, the operation of the microprocessor can be simplified, and the operation time can also be greatly saved.
The secondary object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein pages of physical blocks of the memory can store data of a lookup table, thereby preventing abnormality of data due to improper operation.
Another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein data of a lookup table can be protected by a set of ECC data to enhance the accuracy of data.
Yet another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein all memory blocks can be partitioned into a plurality of segments according to capacity of memory of buffers or block pages. Each segment has a corresponding mapping table of buffers to build the mapping relations of data. When there are data of a block modified, only the related data of the mapping table will be affected. Therefore, time of modification of the mapping table can be effectively decreased, and the situation of erroneous connection of data can be effectively reduced.
Still yet another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, whereby all physical blocks can be partitioned into a plurality of segments to let the size of a mapping table be reduced to be just a sector (256 words) so that the mapping table can be used as general data and
Chang Yao Tse
Lai Chen Nan
Lin Chanson
Wang Kuo-Hong
Key Technology Corporation
Nguyen Hiep T.
Rosenberg , Klein & Lee
LandOfFree
Algorithm of flash memory capable of quickly building table... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Algorithm of flash memory capable of quickly building table..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm of flash memory capable of quickly building table... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3223673