(12) United States Patent
`Gorobets et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,366,826 B2
`Apr. 29, 2008
`
`USOO7366 826B2
`
`(54) NON-VOLATILE MEMORY AND METHOD
`WITH MULT-STREAM UPDATE TRACKING
`
`(75) Inventors: Sergey Anatolievich Gorobets,
`Edinburgh (GB); Peter John Smith,
`Eskbank (GB); Alan David Bennett,
`Edinburgh (GB)
`(73) Assignee: Sandisk Corporation, Milpitas, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 272 days.
`Appl. No.: 11/192.220
`
`(*)
`
`Notice:
`
`(21)
`(22)
`(65)
`
`Filed:
`
`Jul. 27, 2005
`
`Prior Publication Data
`US 2006/O155921 A1
`Jul. 13, 2006
`
`Related U.S. Application Data
`(63) Continuation-in-part of application No. 11/016,285,
`filed on Dec. 16, 2004, now Pat. No. 7,315,916.
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`Int. C.
`(2006.01)
`G6F 2/
`U.S. Cl. ...................................................... 711/103
`Field of Classification Search .
`711/103;
`365/185.33
`See application file for complete search history.
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`9, 1987 Matsuura
`4,694.454. A
`8, 1991 Harari
`5,043,940 A
`5,070,032 A 12/1991 Yuan et al.
`5,095,344 A
`3, 1992 Harari
`5,172,338 A 12/1992 Mehrotra et al.
`5,263,032 A 11/1993 Porter et al.
`5,270,979 A 12/1993 Harari et al.
`5,313,421 A
`5, 1994 Guterman et al.
`
`5/1994 Harari et al.
`5,315,541 A
`8, 1994 Yuan et al.
`5,343,063 A
`4, 1995 Ban
`5,404,485 A
`5,475,693 A 12/1995 Christopherson et al.
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`GB
`
`2289.779 A 11, 1995
`
`(Continued)
`OTHER PUBLICATIONS
`
`ISA/EPO, “Invitation to Pay Additional Fees (including Partial
`International Search Report), mailed on Feb. 21, 2005 in corre
`sponding PCT/US2004/031788, 5 pages.
`(Continued)
`Primary Examiner Hiep T. Nguyen
`(74) Attorney, Agent, or Firm—Davis Wright Tremaine LLP
`
`(57)
`
`ABSTRACT
`
`Update data to a non-volatile memory may be recorded in at
`least two interleaving streams such as either into an update
`block or a scratch pad block depending on a predetermined
`condition. The scratch pad block is used to buffered update
`data that are ultimately destined for the update block.
`Synchronization information about the order recording of
`updates among the streams is saved with at least one of the
`streams. This will allow the most recently written version of
`data that may exist on multiple memory blocks to be
`identified. In one embodiment, the synchronization infor
`mation is saved in a first block and is a write pointer that
`points to the next recording location in a second block. In
`another embodiment, the synchronization information is a
`time stamp.
`
`41 Claims, 43 Drawing Sheets
`
`Providing first and second nonvolatile storages, each for recording- 8
`data sequentially
`
`Maintaining at least one index for data in first and second
`nonviolatile storages
`
`- 81
`
`
`
`Receiving inputdata
`
`- 82
`
`Determining if a first predetermined condition is satisfied for
`recording the received input data to the first storage
`
`- 84
`
`FALSE
`
`Recording the received input
`data to the first storage
`
`85
`
`Recording the received
`inputdata together with the
`at least one index to the
`second storage
`
`- 88
`
`End, unless there are more input data to be received
`
`
`
`- 88
`
`updating Using Two Streams with Index Stored in One Stream
`
`Micron Ex. 1041, p. 1
`Micron v. Vervain
`IPR2021-01547
`
`

`

`US 7,366,826 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6/2003 Harari et al.
`2003.0109.093 A1
`2003/0206449 A1 11/2003 Harari et al.
`2004/0083335 A1
`4/2004 Gonzalez et al.
`2004/O109357 A1
`6/2004 Cernea et al.
`2004/0177214 A1
`9, 2004 Chiu
`2004/0255076 A1* 12/2004 Oyaizu et al. .............. T11 103
`2005/O144357 A1
`6/2005 Sinclair
`2005. O144358 A1
`6/2005 Conley et al.
`2005. O144360 A1
`6/2005 Bennett et al.
`2005. O144363 A1
`6/2005 Sinclair
`2005. O144365 A1
`6/2005 Gorobets et al.
`2005, 0169.259 A1
`8, 2005 Su
`2005/0235098 A1 10, 2005 Tamura et al.
`2006, O133141 A1
`6/2006 Gorobets
`2006, O161722 A1
`7/2006 Bennett et al.
`2007/OOO5829 A1
`1/2007 Fujimoto
`
`FOREIGN PATENT DOCUMENTS
`
`JP
`JP
`JP
`WO
`
`8-147988
`8-279295
`2000-187992
`WO O2/O58.074
`
`6, 1996
`10, 1996
`T 2000
`T 2002
`
`OTHER PUBLICATIONS
`
`ISA/EPO, “Notification of Transmittal of the International Search
`Report and the Written Opinion of the International Searching
`Authority, or the Declaration', mailed on May 31, 2005 in corre
`sponding PCT/US2004/031788, 21 pages.
`Notification of Transmittal of the International Search Report and
`the Written Opinion of the International Searching Authority, or the
`Declaration, for corresponding Patent Application No. PCT/
`US2005/044001, mailed May 17, 2006, 9 pages.
`Notification of Transmittal of the International Search Report and
`the Written Opinion of the International Searching Authority, or the
`Declaration, for corresponding Patent Application No. PCT/
`US2005/043811, mailed May 19, 2006, 10 pages.
`International Search Report and Written Opinion for related Inter
`national Application No. PCT/US2005/043285, mailed May 8,
`2006, 13 pages.
`International Search Report and Written Opinion for related Inter
`national Application No. PCT/US2005/044649, mailed May 4,
`2006, 10 pages.
`Imamiya et al., “A 125-mm. 1-Gb NAND Flash Memory With
`10-Mbyte's Program Speed”, IEEE Journal of Solid State Circuits,
`vol. 37, No. 11, Nov. 2002, 10 pages.
`Notification of Transmittal of the International Search Report and
`the Written Opinion of the International Searching Authority, or the
`Declaration, for corresponding Patent Application No. PCT/
`US2005/044720, mailed Oct. 10, 2006, 10 pages.
`USPTO, “Office Action,” mailed in related U.S. Appl. No.
`11/192,386 on Jul. 27, 2007, 14 pages.
`USPTO, “Office Action,” mailed in related U.S. Appl. No.
`11/191,686 on Jul. 31, 2007, 14 pages.
`* cited by examiner
`
`5,504,760
`5,532,962
`5,570,315
`5,598,370
`5,652,720
`5,657,332
`5,661,053
`5,696,929
`5,699.297
`5,774,397
`5,798,968
`5,835,413
`5,835,921
`5,890,192
`5,909,449
`5,930, 167
`5,933,368
`5,937.425
`5,963473
`6,046,935
`6,049,899
`6,125,435
`6,145,051
`6,151,246
`6,189,081
`6,199,139
`6,222,762
`6,307,776
`6,345,001
`6,415,352
`6.426,893
`6,434,658
`6,456,528
`6.459,644
`6,522,580
`6,560, 152
`6,567,307
`6,678,785
`6,725,321
`6,725,322
`6,760,255
`6,763,424
`6,772,274
`6,829, 167
`6,898,662
`6,925,007
`6,928,511
`7,076,598
`7,185,154
`7,233,336
`2002, 0083262
`2002/0085416
`2002.0099904
`2003/0065699
`
`4, 1996
`T. 1996
`10, 1996
`1/1997
`7, 1997
`8, 1997
`8, 1997
`12, 1997
`12, 1997
`6, 1998
`8, 1998
`11, 1998
`11, 1998
`3, 1999
`6, 1999
`7, 1999
`8, 1999
`8, 1999
`10, 1999
`4, 2000
`4, 2000
`9, 2000
`11, 2000
`11, 2000
`2, 2001
`3, 2001
`4, 2001
`10, 2001
`2, 2002
`T/2002
`T/2002
`8, 2002
`9, 2002
`10, 2002
`2, 2003
`5/2003
`5/2003
`1, 2004
`4, 2004
`4, 2004
`T/2004
`T/2004
`8, 2004
`12, 2004
`5/2005
`8, 2005
`8, 2005
`T/2006
`2, 2007
`6, 2007
`6, 2002
`T/2002
`T/2002
`4, 2003
`
`Harari et al.
`Auclair et al.
`Tanaka et al.
`Nijima et al.
`Aulas et al.
`Auclair et al.
`Yuan
`Hasbun et al.
`Yamazaki et al.
`Endoh et al.
`Lee et al.
`Hurter et al.
`Sunakawa et al.
`Lee et al.
`So et al.
`Lee et al.
`Ma et al.
`Ban
`Norman
`Takeuchi et al.
`Auclair et al.
`Estakhri et al.
`Estakhri et al.
`So et al.
`Fujio
`Katayama et al.
`Guterman et al.
`So et al.
`Mokhlesi
`Asami et al.
`Conley et al.
`Fukuzumi
`Chen
`Mizushima et al.
`Chen et al.
`Cernea
`Estakhri
`Lasser
`Sinclair et al.
`Shiraishi et al.
`Conley et al.
`Conley
`Estakhri
`Tu et al.
`Gorobets
`Harari et al.
`Chiu
`Wang ..................
`Wong et al. ..........
`Mondal ...............
`Fukuzumi
`Yamagami et al. ....
`Conley
`Burns
`
`- - - - - - - T11 103
`
`- - - - - - T11 156
`
`- - - - - - - 345,547
`
`365,185.09
`
`Micron Ex. 1041, p. 2
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 1 of 43
`
`US 7,366,826 B2
`
`
`
`'O'I Å\/HHV Å HOWNEW
`
`
`
`
`
`
`
`
`
`
`
`Micron Ex. 1041, p. 3
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 2 of 43
`
`US 7,366,826 B2
`
`41
`
`
`
`SYSTEM
`RAM
`
`MICRO
`PROCESSOR
`
`
`
`
`
`
`
`MEMORY
`NTERFACE
`LOGIC
`
`OTHER
`CIRCUITS AND
`SUBSYSTEMS
`
`FIG. 1B
`
`
`
`ERASE
`BLOCK
`59
`
`
`
`39
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`-
`FIG.2
`
`FIG.4
`
`
`
`51
`
`53
`
`55
`
`57
`
`HOST USER DATASECTOR
`
`DATAECC:GESO.H. ECC
`N--/
`OVERHEAD ("O.H.")
`FIG.3
`DATA
`
`Micron Ex. 1041, p. 4
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 3 of 43
`
`US 7,366,826 B2
`
`
`
`| ENW/Tc);
`
`0 ENV/Td
`
`0 XAOOTTOE
`
`ESW/HE
`
`9
`
`Micron Ex. 1041, p. 5
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 4 of 43
`
`US 7,366,826 B2
`
`Z XOOTE^^^
`
`| XHOOTE
`
`
`
`Micron Ex. 1041, p. 6
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 5 of 43
`
`US 7,366,826 B2
`
`ADDRESSES
`
`SELECT
`AND
`WORD
`
`
`
`
`
`ADDRESS
`DATA
`
`BLO
`
`BL(N-1) BLN
`BL1
`BIT LINE DRIVERS
`AND READ CRCUITS
`
`67
`
`FIG.7
`
`Micron Ex. 1041, p. 7
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 6 of 43
`
`US 7,366,826 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Sector 0
`
`Active Block 800
`Sector 1
`Sector 2
`
`Sector 3
`
`Page 0
`X-1 %552.5%.5%
`Page 1
`Page 2
`Page 3
`Page 4
`2Easg32.Éased22EaSeg2Easég2 Page 5
`FIG.8
`
`Sector O
`
`Active Block 900
`Sector 1
`Sector 2
`
`Sector 3
`
`X
`X
`X
`x
`
`Page 0
`X-1 %55%.53%
`Page 1
`x+1
`X+2 2?662
`Page 2
`x+1
`|
`x2
`x3 .
`Page 3
`Page 4
`Page 5
`
`
`
`FIG.9
`
`Active Block 1000 (After First Garbage Collection)
`Sector 0
`Sector 1
`Sector 2
`Sector 3
`
`
`
`X %5%5%55%
`EL25%5%5%
`FIG.10A
`
`Page 0
`Page 1
`Page 2
`Page 3
`Page 4
`Page 5
`
`Micron Ex. 1041, p. 8
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 7 of 43
`
`US 7,366,826 B2
`
`Active Block 1010 (After Second Garbage collection)
`Sector 0
`Sector 1
`Sector 2
`Sector 3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3 *
`%55%5%ÉÉ Page 5
`FIG.10B
`
`Active Block 1010 (After Receipt of Additional Sectors)
`Sector 0
`Sector 1
`Sector 2
`Sector 3
`
`* 525%.5%:
`
`FIG.10C
`
`Micron Ex. 1041, p. 9
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 8 of 43
`
`US 7,366,826 B2
`
`Sector O
`
`Active Block 1110
`Sector 1
`Sector 2
`
`Sector 3
`
`
`
`%55%5%5%5%
`%5%5%55%.5%
`
`
`
`Page 0
`Page 1
`Page 2
`Page 3
`Page 4
`Page 5
`
`
`
`
`
`
`
`
`
`
`
`Sector 0
`
`Scratch Pad Block 1120
`Sector 1
`Sector 2
`
`Sector 3
`
`
`
`
`
`
`
`X %ES5%55%5%
`Page 0
`Page 1
`X
`X-1 %556%55%
`Page 2
`XA 25%.5%55%
`Page 3
`X4
`X5 %55%55.3%
`Page 4
`x+4
`x+5
`x+6 255Ss2
`Page 5
`N--
`FIG.1 1A
`
`Micron Ex. 1041, p. 10
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 9 of 43
`
`US 7,366,826 B2
`
`Set O
`
`Active Block 1130
`1
`2
`
`3 H
`%5%5%5%5%
`
`
`
`
`
`
`
`
`
`
`
`Metapage 0
`Metapage 1
`Metapage 2
`Metapage 3
`Metapage 4
`Metapage 5
`
`Plane O
`
`
`
`Plane 2
`
`Plane 3
`
`
`
`Sector O
`
`Scratch Pad Block 1140
`Sector 1
`Sector 2
`
`Sector 3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Metapage 0
`Metapage 1
`1777.7%W.
`Metapage 2
`Metapage 3
`X5 %55%55%
`X4
`Metapage 4
`X+5
`X+6
`%SfSég2
`X+4
`Metapage 5
`Plane 1
`Plane O
`Plane 3
`N--
`FIG.L11B
`
`
`
`Micron Ex. 1041, p. 11
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 10 of 43
`
`US 7,366,826 B2
`
`Active Block 1252
`
`Sector 0
`X1
`
`Sector 1
`(X+1)
`
`Sector 2
`(X+2)
`
`;
`
`Sector 3
`
`%5%5%5%5%
`%5%5%5%55%
`%5%5%5%5%
`25%5%5%5%
`25%5%5%5%
`25%22E,6E2
`%5%5%É%É
`%5%5%5%5%
`26%É66%éfé6%É6%
`Page N-1
`
`Page 0
`Page 1
`Page 2
`Page 3
`Page 4
`Page 5
`Page 6
`Page 7
`Page 8
`Page 9
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Sector 0
`
`Scratch Pad Block 1250
`Sector 1
`Sector 2
`
`Sector 3
`
`x 25.55%55%55%
`Page O
`%55%5%55%
`Page 1
`X
`X'), 25%5%
`Page 2
`%
`Page 3
`Page 4
`8-1-89-1-89 %5%
`Page 5
`25%5%5%5%
`Page 6
`25%525%5%
`Page 7
`%5%55%5%5%
`Page 8
`Page 9
`
`%6%ffé5%66%E?é6%
`Page N-1
`N--
`FIG.12A
`
`
`
`Micron Ex. 1041, p. 12
`Micron v. Vervain
`IPR2021-01547
`
`

`

`Page 0
`Page 1
`Page 2
`Page 3
`Page 4
`Page 5
`Page 6
`Page 7
`Page 8
`Page 9
`
`
`
`
`
`
`
`%5%5%5%55%
`25%5%5%5%
`2.É
`25%5%5%5%
`2325%5%5%
`%5áSé%5656%éS6%fésé6%
`
`Scratch Pad Block 1250
`
`Sector 0
`
`Sector 1
`
`Sector 2
`
`Sector 3
`
`Page N-1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 11 of 43
`
`US 7,366,826 B2
`
`Active Block 1252
`
`Sector O
`X
`
`Sector 1
`
`Sector 2
`(X+2)
`
`
`
`Sector 3
`(X+3)
`
`25%3%5%5%
`
`
`
`Page O
`Page 1
`Page 2
`Page 3
`Page 4
`Page 5
`Page 6
`Page 7
`Page 8
`Page 9
`
`
`
`
`
`
`
`X,
`
`1
`1
`X
`X
`
`(X+1)
`
`(X+2)
`
`%565%
`%
`(x+2}o 256%
`(x+1)
`%555%
`oth
`to
`a
`on
`92.É
`%5%5%É5%
`%25%2.É
`N--
`FIG.12B
`
`Micron Ex. 1041, p. 13
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 12 of 43
`
`US 7,366,826 B2
`
`Sector O
`Xo
`
`Original Block 1254
`Sector 1
`Sector 2
`(X+1)
`(X+2)
`
`Sector 3
`(X+3)o
`
`
`
`
`
`Data from host
`
`Sector 0
`
`
`
`Scratch Pad Block 1250
`Sector 1
`Sector 2
`
`Sector 3
`
`N
`
`Page 0
`Page 1
`Page 2
`Page 3
`
`Page 0
`Page 1
`Page 2
`Page 3
`
`-
`
`
`
`
`
`
`
`Sector O
`
`Active Block 1252
`Sector 1
`Sector 2
`
`Sector 3
`
`2.85%E2%85%:75% is
`Page
`Page 2
`Page 3
`
`FIG.12C
`
`Number
`of Cells
`
`
`
`Upper Page
`Lower Page
`
`1
`1
`
`1
`O
`O
`O
`FIG.13
`
`O
`
`Micron Ex. 1041, p. 14
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 13 of 43
`
`US 7,366,826 B2
`
`Sector 0
`
`Scratch Pad Block 1460
`Sector 1
`Sector 2
`
`Sector 3
`
`Page 0 - Lower
`Page 0 - Upper
`Page 1 - Lower
`Page 1 - Upper
`Page 2-Lower
`Erased 2 Éfé66
`2 Erased
`%
`2 22 2 22
`Erased AA
`3SSg O
`3S99 2. É66% Page 2 - Upper
`
`2 Erased 2 Erased % Erased 2 £666% Page 3 - Upper
`
`Sector O
`
`Active Block 1462
`Sector 1
`Sector 2
`
`Sector 3
`
`
`
`
`
`Page 0 - Lower
`Page 0 - Upper
`Page 1 - Lower
`Page 1 - Upper
`Page 2 - Lower
`Page 2 - Upper
`Page 3 - Lower
`Page 3 - Upper
`
`FIG.14
`
`Micron Ex. 1041, p. 15
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 14 of 43
`
`US 7,366,826 B2
`
`
`
`
`
`Sector O
`
`Original Block 1570
`Sector 1
`Sector 2
`
`Sector 3
`
`Page 0
`Page 1
`
`(4)-4
`("4)-3
`;
`(4)-2
`:
`(i'4)-1
`Eli C.25%.5%
`
`Page i-1
`Page i
`Page i+1
`
`%
`2S42S322s22s2
`Page n-1
`
`
`
`
`
`
`
`
`
`
`
`
`
`NeW Block 1572
`Sector 0
`Sector 1
`Sector 2
`Sector 3
`(4)
`(4)+1 %4).2%(45.3%
`25% 2
`% %53%g%
`
`O
`
`1
`
`2
`
`Page O
`Page 1
`
`Page i-1
`Page i
`Page i+1
`
`(4)-4
`
`;
`
`(4)-3
`
`;
`
`(4)-2
`
`Page n-1
`
`FIG.15
`
`Micron Ex. 1041, p. 16
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 15 of 43
`
`US 7.366,826 B2
`
`Scratch Pad Block 1674
`Sector 1
`Sector 2
`raSed
`
`Erased
`
`3. S e
`
`rr 3.3. SS ee
`
`New Block 1676
`Sector 1
`Sector 2
`
`Sector 3
`aS6
`
`r 23. SS ee
`
`Sector 3
`
`Page 0
`Page 1
`
`Page n-1
`
`
`
`Sector 0
`%
`Erased
`
`Sector 0
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`%
`%5%.5%:25% Page n-i
`
`O
`
`1
`
`Page n-it-1
`Page n-it-2
`
`Micron Ex. 1041, p. 17
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 16 of 43
`
`US 7.366,826 B2
`
`Scratch Pad Block 1780
`
`Page 0
`
`Page 1
`Page 2
`
`Page 3
`
`N--
`FIG.17
`
`
`
`Scratch Pad Block 1890
`
`F.G. 18
`
`Page 0
`
`Page 1
`Page 2
`
`Page 3
`Page 4
`
`Micron Ex. 1041, p. 18
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 17 of 43
`
`US 7.366,826 B2
`
`
`
`21 10
`Sector 0
`Marking Sector
`Erased
`Erased
`Erased
`
`Scratch Pad Block 2100
`Sector 1
`Sector 2
`Erased
`Erased
`Erased
`Erased
`Erased
`Erased
`Erased
`Erased
`
`Erased
`
`Erased
`Erased
`FIG.19
`
`Sector 3
`Erased
`Erased
`Erased
`Erased
`
`Erased
`
`Page 0
`Page 1
`Page 2
`Page 3
`Page 4
`Page 5
`
`21 10
`Sector 0
`
`Scratch Pad Block 2100
`Sector 1
`Sector 2
`
`Sector 3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Erased
`Erased
`FIG.20
`
`Sector 0
`
`
`
`Scratch Pad Block 2100
`Sector 1
`Sector 2
`
`Sector 3
`
`w
`Group Sec 1 Groupiec 2 '2:59:
`Erased
`Erased
`Erased
`Erased
`Erased
`Erased
`
`FIG.21
`
`
`
`Page 4
`Page 5
`
`Page 0
`Page 1
`Page 2
`Page 3
`Page 4
`Page 5
`
`Micron Ex. 1041, p. 19
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 18 of 43
`
`US 7,366,826 B2
`
`
`
`
`
`
`
`
`
`Scratch Pad Block 2100
`
`Sector O
`
`Sector 1
`
`Sector 2
`
`Sector 3
`
`3/6 66663 Group 1 Sec 1
`
`Group 1 Sec 2
`
`Group 2 Sec 2
`Group 2 Sec1
`Group 3 Sec 2 : Group 3 Sec 3
`2461
`2462
`
`Page 0
`
`Page 1
`Page 2
`
`FIG.22
`
`Sector 0
`
`Scratch Pad Block 2100
`Sector 1
`Sector 2
`
`Sector 3
`
`Group 1 Sec 2 2.999; $55% Page 0
`arking Sector2. Group 1 Sec 1
`Group 2 Sec 1
`Group 2 Sec 2 2 index Sector2. Group 3 Sec 1
`Page 1
`2. index Sector
`index $62 256O2 % Page 2
`Page 3
`
`Group 3 Sec 2 : Group 3 Sec 3
`Erased
`
`Erased
`
`s
`
`FIG.23
`
`Page 4
`
`Page 5
`
`Micron Ex. 1041, p. 20
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 19 of 43
`
`US 7,366,826 B2
`
`
`
`Original
`Block
`
`Host write: Host Write
`#1
`#2
`
`
`
`
`
`
`
`
`
`:ES3:
`22 %
`
`
`
`Update Block
`(Non-
`Sequential)
`
`9,
`
`22.5% H%0 :
`
`1
`2
`3
`4
`
`
`
`Key: %
`
`2%22
`
`- -
`
`-
`
`SINGLE-SECTOR PAGE UPDATE EXAMPLE
`
`FIG. 24 (PRIOR ART)
`
`Micron Ex. 1041, p. 21
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 20 of 43
`
`US 7,366,826 B2
`
`
`
`
`
`
`
`
`
`
`
`1O
`Original
`
`- - - -- m - - -
`
`I Host Write
`
`- - - - - - - - -
`
`Host Write
`2
`
`:
`
`STREAM 1-2O
`Update Block
`(Non
`Sequential)
`
`
`
`2Y
`
`
`
`XXXXXXXXXXX X: KXXXXXXXXXXX &-
`
`- - - - - - - -
`
`Host Write
`#3
`
`G
`
`:
`
`:S:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`%
`
`
`
`Key:
`
`WRITE-ONCE, MULTIPLE-SECTOR PAGE UPDATE EXAMPLE
`
`FIG. 25
`
`Micron Ex. 1041, p. 22
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 21 of 43
`
`US 7,366,826 B2
`
`
`
`Providing first and second nonvolatile storages, each for recording
`data sequentially
`
`Maintaining at least one index for data in first and second
`nonvolatile storages
`
`Receiving input data
`
`Determining if a first predetermined condition is satisfied for
`recording the received input data to the first storage
`
`Recording the received input
`data to the first storage
`
`Recording the received
`input data together with the
`at least one index to the
`second storage
`
`End, unless there are more input data to be received
`
`Updating Using Two Streams With Index Stored in One Stream
`
`FIG. 26
`
`Micron Ex. 1041, p. 23
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 22 of 43
`
`US 7,366,826 B2
`
`1O
`Original
`
`Host Write
`#1
`
`
`
`
`
`2O
`
`3O
`
`
`
`STREAM 0
`Update Block
`(Scratch Pad)
`
`
`
`
`
`
`
`
`
`STREAM 1
`Update Block :
`(Non-
`&
`Sequential)
`
`
`
`
`
`-
`ri--
`
`-
`
`-
`
`-
`
`- - - - - - -
`
`
`
`
`
`
`
`2252 if | 22
`3% %
`
`
`
`
`
`
`
`
`
`
`
`
`%
`
`
`
`|ti
`
`
`
`Key:
`
`%366% Erased
`
`
`
`H> Padding
`
`WRITE-ONCE, MULTIPLE-SECTOR PAGE UPDATE
`WITH SPBINDEX EXAMPLE
`FIG. 27A
`
`Micron Ex. 1041, p. 24
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 23 of 43
`
`US 7,366,826 B2
`
`Original
`Block
`
`- - - - - - - -
`Host Write
`#1
`
`
`
`
`
`:ESO's
`
`
`
`
`
`lid
`32 Host Write
`3'-' is
`
`& | ost Write
`%
`
`20
`
`3O
`
`STREAMO
`Update Block
`(Scratch Pad)
`
`
`
`
`
`
`
`STREAM 1
`Update Block
`(Non-
`Sequential)
`
`S.
`5
`E
`
`
`
`
`
`23%
`so 252
`re- 5á
`3.
`-
`
`:S16:
`
`
`
`SPB/CBI
`
`23%2 % Key:
`
`
`
`H> Padding
`
`WRITE-ONCE, MULTIPLE-SECTOR PAGE
`SEOUENTIAL. UPDATE
`WITH SPB INDEX EXAMPLE
`
`FIG. 27B
`
`Micron Ex. 1041, p. 25
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 24 of 43
`
`US 7,366,826 B2
`
`Organizing a nonvolatile memory into erasable blocks of memory
`units, each memory unit for storing a logical unit of data, and each
`block also organized into one or more pages, with the memory
`units in each page having predetermined page offsets and being
`once programmable together after an erase
`
`Providing a block as an update block for recording update
`versions of logical units of data
`
`Receiving logical units of data from a host
`
`Maintaining an index for data in the update block
`
`
`
`Recording to the update block, page by page, with the received
`data aligned in the page according to their page offsets, and when
`the page to be recorded has a portion unoccupied by data, also
`recording the index to the portion unoccupied by data.
`
`90
`
`92
`
`94
`
`96
`
`98
`
`Updating Using One Stream With Index Stored in Partial Page
`
`FIG. 28
`
`Micron Ex. 1041, p. 26
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 25 of 43
`
`US 7,366,826 B2
`
`3O STREAMO
`Scratch Pad Block
`
`Partial Page for Steam 1
`Partial Page for Stream 2
`
`
`
`
`
`
`
`Partial Page for Stream
`
`
`
`
`
`
`
`2O-K STREAMk
`Update Block k
`
`MULTIPLE-SECTOR PAGE UPDATE USING SCRATCH PAD
`
`FIG. 29
`
`Micron Ex. 1041, p. 27
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 26 of 43
`
`US 7,366,826 B2
`
`STREAM1
`
`22
`
`Write A
`
`
`
`Write B
`
`Write C
`
`Write A
`
`FIG. 30 (PRIOR ART)
`
`Micron Ex. 1041, p. 28
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 27 of 43
`
`US 7,366,826 B2
`
`
`
`STREAM1
`
`22
`
`Write A
`
`Write B
`-a-O
`
`Write C
`
`Write A
`
`FIG. 31A
`
`Micron Ex. 1041, p. 29
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 28 of 43
`
`US 7,366,826 B2
`
`STREAMO
`
`STREAM1
`
`22
`
`4O'
`
`:
`
`'
`
`'
`
`'
`
`'
`
`'
`
`'
`
`'
`
`' ' ' ...: ' '.
`
`40'
`
`:
`
`:
`
`.
`
`. . . .
`
`Write A
`-O-
`
`Write B
`-D
`
`Write C
`-O-
`
`Write A
`
`
`
`
`
`
`
`FIG. 31B
`
`Micron Ex. 1041, p. 30
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 29 of 43
`
`US 7,366,826 B2
`
`
`
`Providing first and second nonvolatile storages, each for recording
`data units sequentially
`
`1 OO
`
`Designating either the first or second storage as the storage for
`priority information, the priority information being used to
`determine whether a first data unit in the first storage was
`recorded before or after a second data unit in the second storage
`
`Receiving input data
`
`1 O2
`
`1 1 O
`
`Determining if a predetermined condition is satisfied for recording
`the recieved input data to the first storage
`
`120
`
`Recording the received input
`data to the first storage, and
`the recording including the
`priority information if the first
`storage is the designated
`storage
`
`Recording the received input
`data to the second storage,
`and the recording including
`the priority information if the
`second storage is the
`designated storage
`
`End, unless there are more input data to be received?
`
`150
`
`Synchronizing Two Update Streams
`
`FIG. 32A
`
`Micron Ex. 1041, p. 31
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 30 of 43
`
`US 7,366,826 B2
`
`
`
`Providing first and second nonvolatile storages, each for recording
`data units sequentially
`
`1OO'
`
`Receiving input data
`
`Determining if a first predetermined condition is satisfied for
`recording the received input data to the first storage
`
`11 O'
`
`12O'
`
`Obtaining an address of the
`location where a next
`recording will take place in the
`second storage
`Recording an address of the
`location together with the
`received input data to the first
`storage
`
`Recording the received
`input data to the second
`storage
`
`14O'
`
`End, unless there are more input data to be received
`
`15O'
`
`Synchronizing Two Update Streams Using Write Pointers
`
`FIG. 32B
`
`Micron Ex. 1041, p. 32
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 31 of 43
`
`US 7,366,826 B2
`
`Original
`
`(Host write:
`#1
`
`30 STREAM O
`Update Block
`(Scratch Pad)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`as
`
`20 STREAM 1
`Update Block
`(Non
`Sequential)
`
`
`
`D
`d
`
`2
`
`s
`
`Key:
`
`
`
`25%2
`%6% Erased
`
`::::
`::::
`
`(Valid LS10" in Full Page of Update Block)
`
`FIG. 33A
`
`Micron Ex. 1041, p. 33
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 32 of 43
`
`US 7,366,826 B2
`
`
`
`&
`2
`
`Original
`
`- - - - - - - -
`Host Write
`#1
`
`3O STREAM O
`Update Block
`(Scratch Pad)
`
`
`
`20 STREAM 1
`Update Block
`(Non-
`Sequential)
`
`i
`
`
`
`
`
`
`
`
`
`
`
`:ESE0:
`Hostwrite
`Y2::::::::
`36 :
`#2
`
`Key: %5% Erased
`: % Erased
`
`11
`
`
`
`Padding
`
`(Valid LS10" in Partial Page of Scratch Pad Block)
`
`FIG. 33B
`
`Micron Ex. 1041, p. 34
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 33 of 43
`
`US 7,366,826 B2
`
`- 50
`
`
`
`Logical Page Starting
`Groupi
`Sector
`
`Update Block
`Sector Run Valid
`Length
`Pagei Write Pointer
`
`Scratch Pad Block (SPB) Index
`
`40
`
`- 50
`Index entry for host write #1 in STREAM 1
`
`1
`
`||
`
`8
`
`||
`
`3
`
`||
`
`0
`
`||
`
`0
`
`Index entry for STREAMk
`
`FIG. 34B
`
`Micron Ex. 1041, p. 35
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 34 of 43
`
`US 7,366,826 B2
`
`Original
`
`HOSt Write
`#1
`
`3O STREAMO 20 STREAM 1
`Update Block
`Update Block
`(Scratch Pad)
`(Non
`Sequential)
`
`
`
`c
`O
`Cl
`
`r
`
`c)
`E
`
`e
`
`Key: % Erased
`
`
`
`(Valid LS10' in Scratch Pad Block)
`
`FIG. 35A
`
`Micron Ex. 1041, p. 36
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 35 of 43
`
`US 7,366,826 B2
`
`
`
`i
`
`|
`
`Original
`
`30 STREAM O
`Update Block
`(Scratch Pad)
`
`
`
`
`
`2O STREAM 1
`Update Block
`(Non-
`Sequential)
`
`&
`
`- - - - - -
`Host Write :
`
`
`
`
`
`
`
`
`
`L
`%3
`
`
`
`Key: 25% Erased
`: %6% Erased
`
`Padding
`
`(Valid LS10' in Update Block)
`
`FIG. 35B
`
`Micron Ex. 1041, p. 37
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 36 of 43
`
`US 7,366,826 B2
`
`Overhead
`
`SCratch Pad
`Write Pointer
`FA
`
`40'
`
`Data
`
`LOGICAL SECTOR
`FIG. 36
`
`Time
`
`Time
`
`
`
`
`
`1
`
`1
`
`1
`3
`
`1
`3
`
`FIG. 37
`
`2
`
`2
`
`2
`
`4.
`
`Micron Ex. 1041, p. 38
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 37 of 43
`
`US 7,366,826 B2
`
`
`
`Organizing a nonvolatile memory into erasable blocks of memory
`units, each memory unit for storing a logical unit of data, and each
`block also organized into one or more pages, with each page
`containing multiple memory units and being once programmable
`together after an erase
`
`Providing a first block for recording, full page by full page, update
`versions of logical units of data
`
`Providing a second block for buffering update versions of logical
`units of data received from a host
`
`2OO
`
`210
`
`220
`
`Receiving data in logical units from a host
`
`230
`
`Parsing the received logical units page by page by locating
`any logical units with a page-end offset
`
`Recording each of the logical units having a page-end
`offset to a new page in the first block while filling the new
`page with latest versions of preceding logical units, and
`recording any remaining received logical units in a partial
`page in the second block
`
`234
`
`236
`
`FIG. 38
`
`Micron Ex. 1041, p. 39
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 38 of 43
`
`US 7,366,826 B2
`
`
`
`
`
`Providing an update block (UB) for recording update versions of
`logical units full page by full page, each logical unit having a
`predetermined page offset according to a predetermined order
`
`Providing a scratch pad block (SPB) for temporarily buffering
`updates directed thereto page by page
`Providing a SPB index for locating valid (latest version) data in the
`SPB
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`
`
`
`
`
`
`
`
`
`
`If the write request has more
`data to be received
`Else
`
`Recording a new page of the
`UB with the current logical
`unit at page end and filling
`the rest of the page with
`valid (latest versions) logical
`units according to the
`predetermined order
`
`
`
`
`
`
`
`lf all received data has been recorded
`
`
`
`
`
`Data transferred to SPB
`if unrecorded received data
`does not belong to the same
`page as any existing valid
`(latest version) data in the
`SPB
`
`Updating the SPB index
`Recording into a new page
`of the SPB the unrecorded
`received data and any
`existing valid data at their
`page offsets, terminating
`With the SPB index
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Consolidating SPB to UB
`Relocating existing valid
`data from SPB to a new
`page of the UB by
`Consolidation
`
`
`
`Updating the SPB index
`
`
`
`Writing into a new page of
`the SPB the unrecorded
`received data at its page
`offsets, terminating with
`the SPB index
`
`FIG. 39
`
`34O
`
`37O
`
`372
`
`374
`
`38O
`
`Micron Ex. 1041, p. 40
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 39 of 43
`
`US 7,366,826 B2
`
`
`
`CONTROL
`CIRCUITRY
`410
`
`O
`c
`w
`Y
`O
`O
`O
`?
`3.
`O
`1.
`
`MEMORY ARRAY
`400
`
`PAGE MULTIPLEXER 35O (optional)
`READ/WRITE CIRCUITS 470
`
`Sense
`Module
`1
`
`Sense
`Module
`
`480
`
`Sense
`Module
`
`COLUMN DECODER 46
`
`HOSt/
`Controller
`
`FIG. 40A
`
`Micron Ex. 1041, p. 41
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 40 of 43
`
`US 7,366,826 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONTROL
`CIRCUITRY
`410
`
`
`
`
`
`
`
`
`
`
`
`Data
`I/O
`COLUMN DECODER 46OB
`
`READ/WRITE CIRCUITS 47OB
`
`PAGE MULTIPLEXER 450B (optional)
`
`MEMORY ARRAY
`400
`
`
`
`
`
`PAGE MULTIPLEXER 450A (optional)
`
`READ/WRITE CIRCUITS 47OA
`
`COLUMN DECODER 46OA
`
`Data
`I/O
`
`Host/
`Controller
`
`FIG. 40B
`
`Micron Ex. 1041, p. 42
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 41 of 43
`
`US 7,366,826 B2
`
`SENSE MODULE 48O
`
`
`
`SENSE AMPS
`
`DATA LATCHES
`
`I/O
`
`FIG. 41
`
`Micron Ex. 1041, p. 43
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 42 of 43
`
`US 7,366,826 B2
`
`Providing first and second storage for recording host data units
`
`500
`
`Receiving Host Write Command indicating the range of data units to
`be Written
`
`Does the range of data units predicts satisfying a predetermined
`condition for recording the data units to the first storage
`
`Setting up addresses in
`preparation for recording to
`the first storage
`
`Setting up addresses in
`preparation for recording to
`the second storage
`
`510
`
`512
`
`530
`
`Loading received data to data
`latches for programming
`
`Loading the received data to
`data latches for programming
`
`532
`
`ls the prediction confirmed by
`the received data units?
`
`Aborting the setup for
`recording to the first storage
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Program data in the data
`latches to the addressed
`storage
`
`End Current Host Write
`
`FIG. 42
`
`54O
`
`550
`
`Micron Ex. 1041, p. 44
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Apr. 29, 2008
`
`Sheet 43 of 43
`
`US 7,366,826 B2
`
`Providing first and second storage for recording host data
`
`6OO
`
`Receiving host data
`
`Loading data as it is being received to data latches used for
`programming the first storage and to data latches used for
`programming the second storage
`
`610
`
`62O
`
`Addressing the first or second storage for recording depending on
`whether or not the received data satisfies a predetermined condition
`
`630
`
`Programming data to the addressed storage from its data latches
`
`640
`
`End Current HOSt Write
`
`-N- 650
`
`
`
`m
`
`FIG. 43
`
`Micron Ex. 1041, p. 45
`Micron v. Vervain
`IPR2021-01547
`
`

`

`US 7,366,826 B2
`
`1.
`NON-VOLATILE MEMORY AND METHOD
`WITH MULT-STREAM UPDATE TRACKING
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-in-part of U.S. patent
`application Ser. No. 11/016,285, filed on Dec. 16, 2004.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`The NAND array utilizes series strings of more than two
`memory cells. Such as 16 or 32, connected along with one or
`more select transistors between individual bit lines and a
`reference potential to form columns of cells. Word lines
`extend across cells within a large number of these columns.
`An individual cell within a column is read and verified
`during programming by causing the remaining cells in the
`string to be turned on hard so that the current flowing
`through a string is dependent upon the level of charge stored
`in the addressed cell. Examples of NAND architecture
`arrays and their operation as part of a memory system are
`found in U.S. Pat. Nos. 5,570,315, 5,774,397, 6,046,935,
`and 6,522,580.
`The charge storage elements of current flash EEPROM
`arrays, as discussed in the foregoing referenced patents, are
`most commonly electrically conductive floating gates, typi
`cally formed from conductively doped polysilicon material.
`An alternate type of memory cell useful in flash EEPROM
`systems utilizes a non-conductive dielectric material in place
`of the conductive floating gate to store charge in a non
`volatile manner. A triple layer dielectric formed of silicon
`oxide, silicon nitride and silicon oxide (ONO) is sandwiched
`between a conductive control gate and a surface of a
`semi-conductive Substrate above the