US0078l8490B2
`
`(12) United States Patent
`
`Conley
`
`(10) Patent No.:
`
`(45) Date of Patent:
`
`US 7,818,490 B2
`*Oct. 19, 2010
`
`(54) PARTIAL BLOCK DATA PROGRAMMING
`AND READING OPERATIONS IN A
`NO.\I—VOLATILE MEMORY
`
`5,o43.94o A
`5,172,338 A
`5,341,330 A
`
`8/1991
`12/1992
`8/1994
`
`Harari
`Mehrotra et :11.
`Wells et al.
`
`Inventor: Kevin M. Conley, San Jose. CA (US)
`
`Assignee: SanDisk Corporation, Milpitas, CA
`(US)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`0 250 876
`
`5/1987
`
`(Continued)
`OTHER PUBLICATIONS
`
`This patent is subject to a terminal dis-
`claimer.
`
`The Patent Office ofthe People’s Republic of China, "Notification of
`the First Office Action,” mailed in related Chinese Application No.
`028038827 on Jan. 27, 2006, 14 pages, including translation,
`
`11/250,238
`
`Oct. 13, 2005
`
`Prior Publication Data
`
`US 2006/0031627 Al
`
`Feb. 9, 2006
`
`Related U.S. Application Data
`
`Continuation of application No. 10/841,388, filed on
`May 7, 2004, now Pat. No. 6,968,421, which is a
`continuation of application No. 09/766,436, filed on
`Jan. 19, 2001. now Pat. No. 6,763,424.
`
`Int. Cl.
`
`(2006.01)
`G06F 9/24
`U.S. Cl.
`...................... .. 711/103; 711/113; 711/115
`Field of Classification Search ................ .. 711/103
`
`See application file for complete search history.
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`(Continued)
`
`Primary Examiner—Hong Kim
`Assistant Examiner—Ngoc V Dinh
`(74) Attorney, Agent. or Firm—Davis Wright Tremaine LLP
`
`(57)
`
`ABSTRACT
`
`Data in less than all of tlie pages of a non-volatile memory
`block are updated by programming the new data in unused
`pages of either the same or another block. In order to prevent
`having to copy unchanged pages of data into the new block, or
`to program flags i11to superceded pages of data, the pages of
`new data are identified by the same logical address as the
`pages of data which they superceded and a time stamp is
`added to note when each page was written. When reading the
`data, the most recent pages of data are used and the older
`superceded pages of data are ignored. This technique is also
`applied to metablocks that include one block from each of
`several different units of a memory array. by directing all page
`updates to a single unused block in one of the units.
`
`5,012.132 A
`
`4/1991 Wang
`
`106 Claims, 9 Drawing Sheets
`
`Receive Data
`From Host
`
`Enough
`Data To Fill At
`Least One
`E‘nck
`7
`
`IS
`There A Farttalty
`Wrrtten Block Vtfith
`Enougt; Pages
`
`Address The Panratty
`Written Block
`
`Address At Least One
`New Erased Black
`
`wnteiuew Data In
`Addressed B|ar:k(s)
`
`Mark All Other Blacks
`Wrth Same LBN For
`EH58
`
`Address A New
`Erased Block
`
`Write New Data In
`Addressed Block
`
`Does
`This Result in A
`Blow VWIIV All its Da'
`Out—f.‘;t-Date
`Mark E ock Wtlh
`0ut-Of-Date Tag
`For Erase
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0001
`
`

`
`US 7,818,490 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,388,083
`5,388,248
`5,404,485
`5,457,658
`5,479,638
`5,481,691
`5,485,595
`5,544.356
`5,568,439
`5,598,370
`5,627,783
`5,648,929
`5,649,200
`5,682,499
`5,740,396
`5,822,781
`5,835,935
`5,838,614
`5,845,313
`5,860,090
`5,860,124
`5,867,417
`5,890,192
`5,896,393
`5,907,856
`5,924,092
`5,924,113
`5,937,425
`5,986,933
`5,987,563
`5,999,947
`6,023,423
`6,034,897
`6,040,997
`6,115,785
`6,122,195
`6,125,435
`6,134,151
`6,151,247
`6,161,163
`6,202,138
`6,219,752
`6,219,768
`6,223,308
`6,262,918
`6,288,862
`6,330,633
`6,330,634
`6,426,893
`6,449,625
`6,567,307
`6,584,579
`6,684,289
`6,715,068
`6,725,321
`6,763,424
`6,839,285
`6,845,438
`6,947,332
`6,968,421
`7,167,944
`7,657,702
`
`D>D>D>D>D>D>D>D>D>>i>D>>>>>>3>3>>>3>D>D>D>D>D>D>D>D>D>D>i>3>D>>3>3>3>>
`
`B1 *
`B1
`B2
`132
`B1
`B2
`B2
`B1
`B2
`
`2/1995
`2/1995
`4/1995
`10/1995
`12/1995
`1/1996
`1/1996
`8/1996
`10/1996
`1/1997
`5/1997
`7/1997
`7/1997
`10/1997
`4/1998
`10/1998
`11/1998
`11/1998
`12/1998
`1/1999
`1/1999
`2/1999
`3/1999
`4/1999
`5/1999
`7/1999
`7/1999
`8/1999
`11/1999
`11/1999
`12/1999
`2/2000
`3/2000
`3/2000
`9/2000
`9/2000
`9/2000
`10/2000
`11/2000
`12/2000
`3/2001
`01
`4/2
`01
`4/2
`01
`4/2
`01
`7/2
`01
`9/2
`01
`12/2
`01
`12/2
`02
`7/2
`02
`9/2
`03
`5/2
`03
`6/2
`04
`1/2
`04
`3/2
`04
`4/2
`04
`7/2
`05
`1/2
`1/2
`05
`9/2005
`11/2005
`1/2007
`2/2010
`
`Assar et al.
`Robinson ct al.
`Ban
`Niijima et al.
`Assar et al.
`Day, III et al.
`Assar et al.
`Robinson et al.
`Harari
`N iijima
`Miyauchi
`Miyamoto
`Leblang et al,
`Bakke et al.
`Mason
`Wells et al.
`Estakhri et al.
`Estakhri et al.
`Estakhri et al.
`Clark
`Matthews et al.
`Wallace et al,
`Lee et al.
`Yard et al.
`Estakhri et a1.
`Johnson
`Estakhri et a1.
`Ban
`Takeuchi et al.
`Itoh et al.
`Zollinger et al.
`Aritome
`Estakhri et al.
`Estakhri et al.
`Estakhri et al.
`Estakhri et al.
`Estakhri et al.
`Estakhri et al.
`Estakhri et al.
`Komatsu et al.
`Estakhri et al.
`Sekido
`I-Iirabayashi et al.
`Estakhri et al.
`............. ,. 714/42
`Estakhri et a1.
`Baron et al.
`Kusakabe et al.
`Fuse et :11.
`Conley ct al.
`Wang
`Estakhri
`Kornatsu et al.
`Gonzalez et al.
`Abe ............................ .. 713/1
`Sinclair et al.
`Conley
`[ink et al.
`Tanaka et al.
`Wallace et al.
`Conley
`Estakhri
`Conley
`
`FOREIGN PATENT DOCUMENTS
`
`0 896 280
`0 977 121
`1 352 394
`2 742 893
`2742893
`06-250798
`
`2/1999
`7/1999
`5/2006
`12/1995
`12/1995
`9/1994
`
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`
`8-212019 A
`H08-221223
`10-105661
`H10-091490
`H10-91490
`11-110300 A
`2000-163302 A
`P3070539 B2
`WO94/20906
`W094/22075
`VVO 97/43764 Al
`VVO 98/44420
`VVO 99/07000
`VVO 99/21093
`VVO 00/49488 Al
`VVO 02/49039
`VVO 02/49309 A2
`WO 02/058074 A2
`
`8/1996
`8/1996
`4/1998
`4/1998
`4/1998
`4/1999
`6/2000
`7/2000
`9/1994
`9/1994
`11/1997
`10/1998
`2/1999
`4/1999
`8/2000
`6/2002
`6/2002
`7/2002
`
`OTHER PUBLICATIONS
`
`European Patent Office, “Communication Pursuant to Article 96(2)
`EPC” mailed in related European patent application No. 02703078.
`2-2210 on Dec. 2, 2004, 3 pages.
`“International Preliminary Examination Report”, European Patent
`Office, CorrespondingApplication PCT/US02/00366, J111. 4, 2003, 7
`pages.
`“FTL Updates. PCMCIA Document No, 0165”. Personal Computer
`Memory Card International Association, Version 002, Release 003,
`Mar. 4, 1996, pp. 1-26.
`Mergi, Aryeh and Schneider, Robert, “M-Systems & SCM Flash
`Filing Software Flash Translation Layer—FTL”, PCMCIA, Jul.
`1994, 15 pages.
`Petro ES1:'.I.l(l1l'l et al., “Moving Sectors Within a Block ofInformation
`in a Flash Memory Mass Storage Architecture", U.S. Appl. No.
`09/620,544, filing date Jul. 21, 2000. 48 pages.
`PCT International Search Report, European Patent Office, corre-
`sponding PCT Application No. PC'l'/US02/00366, Jul. 4, 2003, 5
`pages.
`Notice of Opposition to a European Patent for SanDisk Corporation,
`Patent No. 1,352,394, Application No. 02703078.2. dated Mar. 1,
`2007, 17 pages.
`Notification of Reasons for Refusal for SanDisk Corporation, Japa-
`nese Patent Application No. 2002- 558275, mailed Feb. 23. 2007, 10
`pages.
`Japanese Patent Office, “Decision of Refusal.” corresponding Japa-
`nese Patent Application No. 2002-558275 on Nov. 27. 2007. 3 pages.
`(including translation),
`The Patent Office ofthe People’s Republic of China, "Notification of
`the First Office Action,” corresponding Chinese Patent Application
`No. 200610142358.3 on Dec, 14, 2007. 3 pages.
`The Patent Office ofthe People‘s Republic of China, "Notification of
`the First Office Action.” corresponding Chinese Patent Application
`No. 200610142359.8 on Dec. 14,2007, 8 pages. (including transla-
`tion.
`Deposition ofKevin M. Conley dated Jul. 24, 2008, vol, I, 49 pages.
`Deposition ofKevin M. Conley dated Jul. 25,2008, vol. II, 35 pages.
`Deposition of Kevin M. Conley dated Sep. 11, 2008, vol. III, 35
`pages.
`Exhibits No. 1 through No. 12, No. 15 through No. 22, No. 24 through
`No. 26 No. 28 through No. 32, to Deposition of Kevin M. Conley,
`total 573 pages. Feb. 2. 2000.
`Exhibits No. 37 through No. 56, No. 58, No. 59. No. 61 through No.
`72, to Deposition ofKevin M. Conley, total 729 pages. Jan. 13, 2003.
`Deposition of John Mangan dated Jul. 10. 2008. vol. 1. 61 pages.
`Deposition of John Mangan dated Jul. 11, 2008, vol, 2, 37 pages.
`Exhibits No.
`1 through No. 10 to the Deposition of John Mangan,
`total 540 pages. Sep. 12,1989.
`Exhibits No. 11 through No. 15, No. 17 through No. 25, N0. 29, No.
`31, No. 32 to the Deposition of John Mangan, total 504 pages. Apr.
`29, 2008.
`SanDisk Corporation, SDP-32 .\/lbit “Mizer” Low Cost HD, Logical
`Format 20-10-00050, Rev. 8, Dec. 5. 1997, 32 pages.
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0002
`
`

`
`US 7,818,490 B2
`Page 3
`
`United States International Trade Commission, Investigation No.
`337-TA-619, Dr. Subramanian’s testimony dated Oct. 31, 2008, 59
`pages.
`V. Niles Kynett, “Expert Report on the Invalidity of the ’424 Patent.”
`dated Aug. 8, 2008, 99 pages. (including Exhibit 4.).
`Japanese Patent Office. “Notification of Reasons for Refusal,” corre-
`sponding Japanese Patent Application No. 2002-558275, mailed on
`May 13. 2008.3 pages.
`Korean Patent Office, “Office Action.” corresponding Korean Patent
`Application No. 2003-7009551, mailed on Aug. 25, 2008, 14 pages
`(including translation.)
`PCMCIA, PC Card Standard 6.0. PCMCIA Mar. 1997, vol. 1. Over-
`view and Glossary, 29 pages.
`PCMCIA, PC Card Standard 6.0. PCMCIA Mar. 1997, vol. 3, Physi-
`cal Specification, 61 pages.
`PCMCIA, PC Card Standard 6.0. PCMCIA Mar. 1997, vol. 7, Media
`Formats Storage, Specification. 39 pages.
`Barre. “Flash Memory Magnetic Disk Replacement.” IEEE Transac-
`tions on Magnetics. vol. 29. No. 6. Nov. 1993. 4 pages.
`Chan, “VVorld’s Smallest Solid State Storage Device Sets New Indus-
`try Standard,” IEEE. Nov. 4-6, 1997. pp. 484-487.
`Wells et al. “Flash Solid State Drive with 6MB/s ReadWrite Channel
`and Data Compression,”
`ISSCC 93/Session 3/Non-Volatile,
`Dynamic, and Experimental Memories/Paper‘ WP 3.6, 4 pages.
`United States International Trade Commission, In the Matter of Cer-
`tain Flash Memory Controllers, Drivers, Memory Cards, and Media
`Palyers and Products Containing same, lnv. No. 337-'lA-619. Order
`No. 33: Order Construing the Terms of the Asserted Claims of the
`Patents at Issue, Jul. 15, 2008, pp. i-iii, 1-10 and 54-67.
`Exhibits No. 16 through 28 from Kynett’s Expert Report, dated Aug.
`8. 2008. 331 pages.
`Exhibits No. 36 through 41 from Kynett’s Expert Report, dated Aug.
`8, 2008, 69 pages.
`Exhibits No. 46 through 57 from Kyw1ett’s Expert Report, dated Aug.
`8,2008, 157 pages.
`Exhibits No. 65 through 72 from Kynett’s Expert Report, dated Aug.
`8, 2008, 63 pages.
`Korean Patent Office, “Notice of Preliminary Rejections,” corre-
`sponding Korean Patent Application No. 2008-7028861, mailed on
`Mar. 10, 2009. 8 pages (intending translation.)
`USPT(). “Notice of Allowance and Fee(_s) Due.” mailed in related
`U.S. Appl. No. 12/371,460 on Nov. 16, 2009. 24 pages.
`Korean Patent Otlice,“Preliminary Rejection,”
`corresponding
`Korean Patent Application No. 2008-7028861. mailed on Jan. 28,
`2010, 12 pages (including translation).
`corresponding
`Korean Patent Office,“Preliminary Rejection,”
`Korean Patent Application No. 2008-7028861. mailed on Jan. 28,
`2010, 11 pages (including translation.)
`United States International Trade Commission, “In the Matter of
`Certain Flash Memory Controllers, Drives, Memory Cards and
`Media Players, and Products Containing Same,” Inv. No. 337-TA-
`619, Initial Determination on Violation of Section 337 and Recom-
`mended Determination on Remedy and Bond, Administrative Law
`Judge Charles E. Bullock. Public Version. May 5. 2009. 398 pages.
`
`* cited by examiner
`
`Sandisk Israel, MediaClip Memory Card MMC Controller Top Level
`Design, Version 0.1, Nov. 13, 1996, 74 pages.
`SanDisk Corporation, Preliminary MultiMediaCard Product
`Manual, Apr. 28, 1998. 96 pages.
`Photo International, Digital: SanDisk Introduces 64, 80, 96 and 160
`MB CompactFlash Memory, Feb. 1999, 1 page.
`Hsia et al., “A Reconfigurable Interconnect For In-Silicon Electronic
`Assembly”, IEEE, (1982) pp. 7-16.
`Hsia et al., “Adaptive Wafer Scale Integration”, Proceeding of the
`11”“ Conference (1979 International), Japanese Journal ofApplied
`Physics, vol. 19 (1980) Supplement 19-1. pp. 193-202.
`Hsia, "Memory Applications Of The MNOS”, 1972 Wescon Techni-
`cal Papers vol. 16, (1972) pp. 1-5.
`Niijima. “Design ofa solid-state file using flash EEPROM.” IBM J.
`Res. Develop. vol. 39. No. 5. Sep. 1995. 15 pages (as marked up by
`Dr. I-Iarari).
`Hel er Ehrman. I.etter from A. Sharma to J.Yoon identifying I-Ieller’s
`Respondents’ Prior Art, dated Mar. 10, 2008. 7 pages.
`Uni ed States International Trade Commission, Investigation No.
`337-TA-619, Notice ofPrior Art of Respondents Apacer Technology,
`Inc. and Apacer Memory America, Inc.. Silicon Motion Technology
`Comoration, Silicon Motion, Inc. (Taiwan), Silicon Motion, Inc.
`(Ca ifornia) and Silicon Motion International, Inc., Transcend Infor-
`mation, Inc. (Taiwan), Transcend Information, Inc. (California) and
`Transcend Information Maryland, Inc., dated Jul. 11, 2008, 17 pages.
`Uni ed States International Trade Commission, Investigation No.
`337-TA-619, The Heller Respondents’ Notice of Prior Art, dated Jul.
`11, 2008, 23 pages.
`Uni ed States International Trade Commission, Investigation No.
`337-TA-619, Respondents Kingston Technology Co.. Inc., Kingston
`Tec mology Corporation, Memosun. Inc.. Payton Technology Cor-
`poration, and Phison Electronics Corporation’s Notice of Prior Art,
`dated Jul. 11, 2008, 19 pages.
`I ni ed States International Trade Commission, Inves igation No.
`37-TA-619, Respondents LG Electronics, Inc. and LG Electronics
`.S.A., Inc’s Notice of Prior Art. Jul. 11,2008. 16 pages.
`ni ed States International Trade Commission. Inves igation No.
`37-TA-619. Niles Kynett’ s testimony dated Oct. 29, 2008. 22 pages.
`ni ed States International Trade Commission, Inves igation No.
`37-TA-619. Niles Kynett’s testimony dated Oct. 30, 2008, 23 pages.
`ni ed States International Trade Commission, Inves igation No.
`37-TA-619, witness statement of Kevin Conley dated Oct. 9. 2008,
`pages.
`ni ed States International Trade Commission, Inves igation No.
`37—TA—619, Professor M. Ray Mercer’s testimony dated Nov. 3,
`008, 30 pages.
`ni ed States International Trade Cormnission, Inves igation No.
`37-TA-619, Dr. Thomas Rhyne’s testimony dated Oct. 27. 2008, 86
`' es.
`
`3II3I3
`
`(-‘rzjwr-<NL.az-<aoL.ar-<
`/"'59)/“"UbJDJ
`
`ied States International Trade Commission, Inves igation No.
`7-TA-619, Dr. Thomas Rhyne’s testimony dated Oct. 28. 2008, 84
`es.
`
`bJ=i3-
`bu»
`red States International Trade Commission, Inves igation No.
`7-TA-619, Dr. Thomas Rhyne’s testimony dated Oct. 29. 2008, 34
`es.
`13>
`
`ni ed States International Trade Commission, Inves igation No.
`337-TA-619, Dr. Subramanian’s testimony dated Oct. 30. 2008, 60
`pages.
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0003
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`Sheet 1 of 9
`
`US 7,818,490 B2
`
`_..9".
`
`ENEmo_mn_v
`
`
`
`IIV9.ooE>a
`
`«QEiomm$5
`
`%I
`
`'%
`
`"-E.‘
`
`=%
`
`% %
`
`% —
`
`'.—'_
`
`% % % % %
`
`:m<4¢
`
`>mo2m2
`
`><mm<
`
`am
`
`m4o¢Pzoo
`
`>mo2m2
`
` fig
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0004
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`Sheet 2 of9
`
`US 7,818,490 B2
`
`FIG. 2
`
`(PRIOR ART)
`
`Original Block 11
`
`With New Block 15
`
`FIG. 5A
`
`FIG. 5B
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0005
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`9f03teehS
`
`US 7,818,490 B2
`
`C.I.<moan;m.0_n_
`
`:+z:moM
`
`
`
`WT.“1AJ1ITLTil
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0006
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`Sheet 4 of9
`
`US 7,818,490 B2
`
`LBN PAGE
`
`A1557A
`
`A
`
`ddresses
`
`Old/New
`Page Data
`flags
`
`FIG. 6
`
`(PRIOR ART)
`
`LBN Page
`
`PBN Page
`
`LBN Page
`
`PBN Page
`
`CDOOOCDCOC
`
`-\JCDU1-§OJfU—'-C
`
`\lO5U'I-bCaDl\'>#-O
`
`Original Block
`
`With New Block
`
`FIG. 7A
`
`FIG. 7B
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0007
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`Sheet 5 of9
`
`US 7,818,490 B2
`
`LBN PAGE
`
`?¢//mm
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0008
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`Sheet 6 of9
`
`US 7,818,490 B2
`
`OVERHEAD
`
`I
`
`I
`
`III
`
`LBN
`
`PAGE
`TAG
`
`TIME
`STAMP
`
`A.S.
`FLAG
`
`OVERHEAD
`ECC
`
`\____§fi_____./
`41
`
`43
`
`50
`
`FIG. 10
`
`_‘
`
`‘ —
`BLOCK
`FLAG
`
`CONTROLLER
`
`LBN Page
`0
`0
`0
`1
`O
`2
`O
`3
`0
`4
`0
`5
`0
`6
`0
`7
`
`0
`0
`
`8
`9
`
`PBNO Page
`
`PBN1 Page
`
`(.D®'\lC’>U'I.b(a.'Jl\J—L©
`
`
`
`-GCOCCGQGOC
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0009
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`9f07teehS
`
`LUS731&4WDB2
`
`omm<mm
`
`fin.»mom..
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0010
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`Sheet 8 of9
`
`US 7,818,490 B2
`
`55
`
`Address At Least One
`New Erased Block
`
`-
`
`57
`
`gggilg,
`
`59
`
`Mark All Other Blocks
`With Same LBN For
`Erase
`
`Receive Data
`From Host
`
`52
`
`53
`
`Enough
`Data To Fill At
`Least One
`Block
`?
`
`There A Partially
`
`Written Block With
`
`Enough Pages
`?
`
`Add
`A N
`5,3333 Blociw
`
`Address The Partially
`Written Block
`
`' Write New Data In
`Addressed Block
`
`67
`
`Does
`This Result In A
`Block With All It's Data
`Out-Of-Date
`7
`
`Mark Block With
`
`Out-Of-Date Tag
`For Erase
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0011
`
`

`
`U.S. Patent
`
`Oct. 19, 2010
`
`Sheet 9 of9
`
`US 7,818,490 B2
`
`2"Mzzml
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0012
`
`

`
`US 7,818,490 B2
`
`1
`PARTIAL BLOCK DATA PROGRAMMING
`AND READING OPERATIONS IN A
`NON-VOLATILE MEMORY
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`5
`
`10
`
`2
`Another function the controller performs is to maintain the
`integrity of data stored to the subsystem through various
`means, such as by using an error correction code (ECC).
`In an ideal case, the data in all the pages of a block are
`usually updated together by writing the updated data to the
`pages within an unassigned, erased block, and a logical-to-
`physical block number table is updated with the new address
`The original block is then available to be erased. However, it
`is n1ore typical that the data stored in a 11u1nber ofpagcs less
`than all of the pages within a given block must be updated.
`The data stored in the remaining pages of the given block
`remains unchanged. The probability of this occurring is
`higher in systems where the number of sectors of data stored
`per block is higher. One technique now used to accomplish
`such a partial block update is to write the data of the pages to
`be updated into a corresponding number of the pages of an
`unused erased block and then copy the unchanged pages from
`the original block into pages of the new block. The original
`block may then be erased and added to an inventory ofunused
`, blocks in which data may later be programmed. Another
`teclmique similarly writes the updated pages to a new block
`but eliminates the need to copy the other pages ofdata i11to the
`new block by changing the flags of the pages in the original
`block which are being updated to indicate they contain obso-
`lete data. Then when the data are read, the updated data read
`from pages of the new block are combined with the
`unchanged data read from pages of the original block that are
`11ot flagged as obsolete.
`
`This application is a continuation of application Ser. No.
`10/841,388, filed May 7, 2004, now U.S. Pat. No. 6,968,421,
`which in turn is a continuation of application Ser. No. 09/766,
`436, filed Jan. 19, 2001, now U.S. Pat. No. 6.763,424, which
`applications are incorporated herein in their entirety by this
`reference.
`
`BACKGROUND OF THE INVENTION
`
`This invention pertains to the field of semiconductor non-
`volatile data storage system architectures and their methods
`of operation. and has application to data storage systems
`based on flash electrically erasable and programmable read-
`only memories (EEPROMS).
`A co1nn1o11 application of flash EEPROM devices is as a
`n1ass data storage subsystem for electronic devices. Such
`subsystems are connnonly implemented as either removable
`memory cards that can be inserted into multiple host systems
`or as non-removable embedded storage within the l1ost sys-
`tem. In both implementations, the subsystem includes one or
`more flash devices and often a subsystem controller.
`Flash EEPROM devices are composed of one or 111ore
`arrays of transistor cells, each cell capable of non-volatile
`storage of one or more bits ofdata. Thus flash memory does
`not require power to retain the data programmed therein.
`Once programmed however, a cell must be erased before it
`can be reprogrannned with a new data value. These arrays of
`cells are partitioned into groups to provide for efficie11t imple-
`mentation of read, program and erase functions. A typical
`flash memory architecture for mass storage arranges large
`groups of cells into erasable blocks. wherein a block contains
`the smallest number of cells (unit oferase) that are erasable at
`one time.
`
`SUMMARY OF THE INVENTION
`
`According to one principal aspect of the present invention,
`briefly and generally, both the copying of unchanged data
`from the original to the new blocks and the need to update
`flags within the original block are avoided when the data of
`fewer than all of the pages within a block are being updated.
`This is accomplished by maintaining both the superceded
`data pages and the updated pages of data with a common
`logical address. The original and updated pages of data are
`then distinguished by the relative order in which they were
`programmed. During reading, the most recent data stored in
`the pages having the same logical address are combined with
`the unchanged pages of data while data in the original ver-
`sions of the updated pages are ignored. The updated data can
`be written to either pages within a different block than the
`original data, or to available unused pages within the same
`block. In one specific implementation, a form oftime stamp is
`stored with each page of data that allows deten11ini11g the
`relative order that pages with the same logical address were
`written. In another specific implementation,
`in a system
`where pages are programmed in a particular order within the
`blocks, a form oftime stamp is stored with each block ofdata,
`and the most recent copy of a page within a block is estab-
`lished by its physical location within the block.
`These techniques avoid both the necessity for copying
`unchanged data from the original to new block and the need to
`change a flag or other data in the pages of the original block
`whose data have been updated. By not having to change a flag
`or other data in the superceded pages, a potential ofdisturbing
`the previously writte11 data i11 adjacent pages of that same
`block that cai1 occur from such a writing operation is elimi-
`nated. Also, a perfonnance penalty of the additional program
`operation is avoided.
`A further operational feature, which may be used in con-
`junction with the above summarized techniques, keeps track
`of the logical offset of individual pages of data within the
`individual memory cell blocks, so that the updated data need
`
`In one commercial form, each block contains enough cells
`to store one sector of user data plus some overhead data
`related to the user data and/or to the block in which it is stored.
`The amount of user data included in a sector is the standard
`512 bytes in one class of such memory systems but can be of 4;
`son1e other size. Because the isolation of individual blocks of
`
`cells from one another that is required to make them individu-
`ally erasable takes space on the integrated circuit chip,
`another class of flash memories makes the blocks sig11ifi-
`cantly larger so there is less space required for such isolation.
`But since it is also desired to handle user data in much smaller
`sectors, each large block is often further partitioned into indi-
`vidually addressable pages that are the basic unit for reading
`and programming user data (unit of progrannning a11d/or
`reading). Each page usually stores one sector ofuser data, but
`a page may store a partial sector or multiple sectors. A “see-
`tor” is used herein to refer to an amount of user data that is
`transferred to and from the host as a unit.
`
`The subsystem controller in a large block system performs
`a number of functions including the translation between 10gi-
`cal addresses (LBAs) received by the memory sub-systen1
`from a host, and physical block numbers (PBNs) and page
`addresses within the memory cell array. This translation often
`involves use of intermediate terms for a logical block number
`(LBN) and logical page. The controller also manages the low
`level flash circuit operation through a series ofconmiands that
`it issues to the flash memory devices via air interface bus.
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0013
`
`

`
`US 7,818,490 B2
`
`4
`FIG. 12 is a table of corresponding logical and physical
`page numbers for the new block of FIG. 11;
`FIG. 13 illustrates one way to read the updated data in the
`blocks of FIG. 11;
`FIG. 14 is a flow diagram of a process ofprogramming data
`into a memory system organized as illustrated in FIGS. 8 and
`9;
`
`FIG. 15 illustrates an existing multi-unit memory with
`blocks from the individual units being linked together into a
`' metablock and
`
`FIG. 16 illustrates an improved method of updating data of
`a metablock in the m11lti-unit memory of FIG. 12 when the
`amount of updated data is much less that the data storage
`capacity of the metablock.
`
`DESCRIPTION OF EXISTING LARGE BLOCK
`MANAGEMENT TECHNIQUES
`
`3
`not be stored with the same physical page offset as the super-
`ceded data. This allows more eflicient use ofthe pages of11ew
`blocks, and even allows the updated data to be stored in any
`erased pages of the same block as the superceded data.
`Another principal aspect of the present invention groups
`together two or more blocks positioned in separate units ofthe
`memory array (also termed “sub-arrays”) for programming
`and reading together as part of a single operation. Such a
`multiple block group is referenced herein as a “metablock.”
`Its component blocks may be either all located on a single
`memory integrated circuit chip. or, in systems using more
`than one such chip, located on two or more different chips.
`When data in fewer than all ofthe pages ofone ofthese blocks
`is updated, the use of another block in that same unit is
`normally required. I11deed, the tech11iques described above, or
`others, may be employed separately with each block of the
`metablock. Therefore, when data within pages of more than
`one block of the metablock are updated, pages within more
`than one additional block are required to be used. If there are
`four blocks of four different memory units that form the
`metablock. for example, there is some probability that up to
`an additional fourblocks, one in each of tlie units, will be used
`to store updated pages of the original blocks. One update
`block is potentially required in each unit for each block ofthe
`original metablock. In addition. according to the present
`invention, updated data from pages of more than one of the
`blocks in the metablock can be stored in pages of a coimnon
`block i11 only one of the units. This significantly reduces the
`number of unused erased blocks that are needed to store
`
`updated data. thereby making more eflicient use of the avail-
`able memory cell blocks to store data. This technique is
`particularly useful when the memory system frequently
`updates single pages from a metablock.
`Additional aspects, features a11d advantages of the present
`invention are included in the following description of exem-
`plary embodiments, which description should be read in con-
`junction with the accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`—
`
`FIG. 1 shows a typical flash memory device internal archi-
`tecturc. The primary features include an input/output (I/O)
`bus 411 and control signals 412 to interface to ar1 external
`controller, a memory control circuit 450 to control internal
`memory operations with registers for connnand, address and
`status signals. One or more arrays 400 offlash EEPROM cells
`are included, each array having its own row decoder (XDEC)
`401 and column decoder (YDEC) 402, a group of sense
`amplifiers a11d program control circuitry (SA/PROG) 454 a11d
`a data register 404. Presently, the memory cells usually
`include one or more conductive floating gates as storage
`elements but other long term electron charge storage elements
`may he used instead. The memory cell array may be operated
`with two levels of charge defined for each storage element to
`therefore store one bit of data with each element. Alterna-
`
`tively, more than two storage states may be defined for each
`storage element, in which case more than one bit of data is
`stored in each element.
`
`If desired, a plurality of arrays 400, together with related X
`decoders, Y decoders, program/verified circuitry, data regis-
`ters, and the like are provided, for example as taugl1t by U.S.
`Pat. No. 5,890,192, issued Mar. 30, 1999, and assigned to
`Sandisk Corporation, the assignee of this application, which
`is hereby incorporated by this reference. Related memory
`system features are described in co-pending patent applica-
`tion Ser. No. 09/505,555, filed Feb. 17. 2000 by Kevin Conley
`et al., now U.S. Pat. No. 6,426,893, which application is
`expressly incorporated herein by this reference.
`The external interface I/O bus 411 and control signals 412
`can include the following:
`CS Chip Select. Used to activate flash memory interface.
`RS—Read Strobe. Used to indicate the I/O bus is being used
`to transfer data from the memory array.
`VVS—Write Strobe. Used to indicate the I/O bus is being used
`to transfer data to the memory array.
`AS—Address Strobe. Indicates that the I/O bus is being used
`to transfer address information.
`
`AD[7:0]—Address/Data Bus This I/O bus is used to transfer
`data between controller and the flash memory command,
`address and data registers of the memory control 450.
`This interface is given only as an example as other signal
`configurations can be used to give the same functiona ity.
`FIG. 1 shows only one flash memory array 400 with its related
`components. but a multiplicity of such arrays can exist on a
`single flash memory chip that share a common interface and
`memory control circuitry but have separate XDEC. YDEC,
`SA/PROG a11d DATA REG circuitry i11 order to allow parallel
`read and program operations.
`
`FIG. 1 is a block diagram of a typical prior art flash
`EEPROM memory array with memory control logic, data and
`address registers;
`FIG. 2 illustrates an architecture utilizing memories of
`FIG. 1 with a system controller;
`FIG. 3 is a timing diagram showing a typical copy opera-
`tion of the memory system of FIG. 2:
`FIG. 4 illustrates an existing process of updating data in
`less than all of the pages ofa multi-paged block;
`FIGS. 5A and 5B are tables of corresponding logical and
`physical block addresses for each of tlie original and new
`blocks of FIG. 4, respectively;
`FIG. 6 illustrates another existing process ofupdating data
`in less than all of the pages ofa multi-paged block;
`FIGS. 7A and 7B are tables of corresponding logical and 5
`physical page addresses for the original and new blocks of
`FIG. 6, respectively:
`FIG. 8 illustrates an example of an improved process of
`updating data in less than all of the pages of a multi-paged 60
`block;
`FIG. 9 is a table ofcorresponding logical and physical page
`numbers for the new block of FIG. 8:
`
`FIG. 10 provides an example of a layout of the data in a
`page shown in FIG. 8;
`FIG. 11 illustrates a further development oftlie example of
`FIG. 8;
`
`APPLE INC.
`EXHIBIT 1001 - PAGE 0014
`
`

`
`US 7,818,490 B2
`
`5
`Data is transferred from the memory array through the data
`register 404 to an external controller via the data registers’
`coupling to the I/O bus AD[7:0] 411. The data register 404 is
`also coupled the sense arnplifier/programming circuit 454.
`The number of elements of the data register coupled to each
`sense amplifier/prograrnming circuit element may depend on
`the number of bits stored in each storage element of the
`memory cells, flash EEPROM cells each containing one or
`more floating gates as tl1e storage elements. Each storage
`ele111er1t may store a plurality of bits, such as 2 or 4, if the
`memory cells are operated in a multi-state mode. Alterna-
`tively. the memory cells may be operated in a binary mode to
`store one bit of data per storage element.
`The row decoder 401 decodes row addresses for the array
`400 i11 order to select the physical page to be accessed. The
`row decoder 401 receives row addresses via internal row
`
`address lines 419 from the memory control logic 450. A
`column decoder 402 receives column addresses via internal
`column address lines 429 from the memory control logic 450.
`FIG. 2 shows a11 architecture of a typical non-volatile data
`storage system, in this case employing flash memory cells as
`the storage media. In one for111, this system is encapsulated
`within a removable card having an electrical comrector
`extending along one side to provide the host interface when
`inserted into a receptacle of a host. Alternatively. the system
`ofFIG. 2 may be embedded into a host system in the form of
`a permanently installed embedded circuit or otherwise. The
`system utilizes a sir1gle controller 301 that performs high
`level host and memory control functions. The llash memory
`media is composed of one or more flash memory devices,
`each such device often formed on its own integrated circuit
`chip. The system controller and the flash memory are con-
`nected by a bus 302 that allows the controller 301 to load
`command, address, and transfer data to and fr