(12) United States Patent
`Gorobets
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,917,709 B2
`*Mar. 29, 2011
`
`USOO791 7709B2
`
`(54) MEMORY SYSTEM FOR DATA STORAGE
`AND RETRIEVAL
`
`(75) Inventor: Sergey Anatolievich Gorobets,
`Edinburgh (DE)
`
`(73) Assignee: Lexar Media, Inc., Fremont, 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.
`This patent is Subject to a terminal dis-
`claimer.
`(21) Appl. No.: 12/638,572
`
`7, 1980 Wozniak
`4,210,959 A
`1/1982 Tabata
`4,309,627 A
`4,355,376 A 10, 1982 Gould
`4,398,248 A
`8, 1983 Hsia et al.
`4.405,952 A
`9, 1983 Slakmon
`4.414,627 A 1 1/1983 Nakamura
`4.450,559 A
`5/1984 Bond et al.
`4,456,971 A
`6, 1984 Fukuda et al.
`4,468,730 A
`8, 1984 Dodd et al.
`12. A 88.
`lawsky et al.
`w
`(Continued)
`FOREIGN PATENT DOCUMENTS
`O 557 723
`1, 1987
`(Continued)
`
`AU
`
`(65)
`
`(22) Filed:
`
`Dec. 15, 2009
`O
`O
`Prior Publication Data
`US 201O/OO95055A1
`Apr. 15, 2010
`Related U.S. Application Data
`(63) Synopsis N989, filed on
`
`(30)
`
`Foreign Application Priority Data
`
`Sep. 28, 2001 (GB) ................................... O123410.3
`ep. ZS,
`(GB)
`(51) Int. Cl.
`G06F I3/00
`711/154: 711/159
`(52) U.S. Cl
`71 1f156
`(58) Field O f Classification search- - - - - -
`- - - - - - - - - - - - - - - - - - 711/15 9
`See application file for complete search histo
`pp
`p
`ry.
`References Cited
`
`(2006.01)
`
`(56)
`
`U.S. PATENT DOCUMENTS
`4,099,069 A
`7, 1978 Cricchi et al.
`4,130,900 A 12/1978 Watanabe
`
`
`
`OTHER PUBLICATIONS
`Kai Hwang & Faye A. Briggs, Computer Architecture and Parallel
`Processing, McGraw-Hill Book Co., 1984, p. 64.
`(Continued)
`
`Primary Examiner — Hetul Patel
`(74) Attorney, Agent, or Firm — Leffert Jay & Polglaze, PA.
`
`ABSTRACT
`(57)
`According to a first aspect of an embodiment of the invention
`s
`there is provided a method of data storage and retrieval for use
`in a solid State memory system, having a non-volatile
`memory, wherein data is written to the non-volatile memory
`in the form of at least one logical sector the method compris
`ing: monitoring the logical sector data which is to be written
`to the non-volatile memory, detecting the presence of a pat
`tern in the logical sector data, upon detecting a repetitive
`pattern recording the repetitive pattern of the logical sector in
`a sector address table in the non-volatile memory without
`making a record of the logical sector data in the nonvolatile
`memory.
`
`25 Claims, 5 Drawing Sheets
`
`- - - - - - -
`
`Memory System
`
`Micron Ex. 1062, p. 1
`Micron v. Vervain
`IPR2021-01549
`
`

`

`U.S. PATENT DOCUMENTS
`Martinez
`2, 1985
`4,498,146
`Nozawa et al.
`6, 1985
`4,525,839
`Wallach et al.
`7, 1985
`4,532,590
`9, 1986
`4,609,833
`Gutterman
`10, 1986
`4,616,311
`Sato
`3, 1987
`4,654,847
`Dutton
`Belknap et al.
`12, 1987
`4,710,871
`5, 1988
`Robinson et al.
`4,746,998
`5, 1988
`Yorimoto et al.
`4,748,320
`T. 1988
`Fukushi et al.
`4,757,474
`9, 1988
`Satoh et al.
`4,774,700
`10, 1988
`Iida et al.
`4,780,855
`11, 1988
`Fukuda et al.
`4,788,665
`1, 1989
`Watanabe
`4,797.543
`Iijima
`1, 1989
`4,800,520
`5, 1989
`Watanabe
`4,829,169
`6, 1989
`Ohta et al.
`4,843,224
`7, 1989
`Tokumitsu
`4,845,662
`Wayama et al.
`1, 1990
`4,896,262
`4, 1990
`Bonke
`4.914,529
`4, 1990
`Nakamura et al.
`4,920,518
`5, 1990
`Robinson et al.
`4.924,331
`7, 1990
`Watanabe et al.
`4,943,745
`8, 1990
`Williams
`4,953,122
`11, 1990
`4,970,642
`Yamamura
`Miyawaki et al.
`11, 1990
`4,970,727
`12, 1991
`Tuma et al.
`5,070.474
`Iijima
`3, 1992
`5,093,785
`12, 1992
`Harari
`5,168,465
`3, 1993
`Harari
`5, 198,380
`4, 1993
`Gross et al.
`5,200,959
`6, 1993
`Novecket al.
`5,218,695
`Haq
`6, 1993
`5,220,518
`Kobayashi et al.
`7, 1993
`5,226,168
`7, 1993
`5,227,714
`Lou
`10, 1993
`Yamamoto et al.
`5,253,351
`11, 1993
`Elbert
`5,267,218
`12, 1993
`Harari
`5,268,318
`12, 1993
`Harari
`5,268,870
`12, 1993
`Harari et al.
`5,270,979
`3, 1994
`Harari
`5,293,560
`3, 1994
`Harari et al.
`5,297,148
`4, 1994
`Adachi et al.
`5,303,198
`Uenoyama
`4, 1994
`5,305,276
`4, 1994
`5,305,278
`Inoue
`5, 1994
`Harari et al.
`5,315,541
`Hag
`5, 1994
`5,315,558
`T. 1994
`Brown et al.
`5,329,491
`8, 1994
`5,337,275
`Garner
`8, 1994
`Wells et al.
`5,341,330
`8, 1994
`Wells
`5,341,339
`8, 1994
`FukuZo
`5,341,341
`10, 1994
`Fandrich et al.
`5,353.256
`10, 1994
`Hasbun et al.
`5,357,475
`Fujita et al.
`10, 1994
`5,359,569
`Manley
`11, 1994
`5,365,127
`11, 1994
`Harari et al.
`5,369,615
`12, 1994
`Nakai et al.
`5,371,702
`1, 1995
`Yanai et al.
`5,381,539
`1, 1995
`Shinohara
`5,382,839
`Rouy
`1, 1995
`5,384,743
`2, 1995
`Assar et al.
`5,388,083
`3, 1995
`Harari et al.
`5,396,468
`4, 1995
`5,404,485
`Ban
`4, 1995
`5,406,527
`Honma
`5, 1995
`Harari et al.
`5,418,752
`6, 1995
`Cernea et al.
`5,422,842
`6, 1995
`Sasaki et al.
`5,422,856
`6, 1995
`Mehrotra et al.
`5,428,621
`7, 1995
`Ishikawa et al.
`5.430,682
`7, 1995
`Norman et al.
`5.430,859
`7, 1995
`Wieres
`5.431,330
`7, 1995
`Harari
`5.434,825
`Mangan et al.
`8, 1995
`5.438,573
`Miyamoto
`11, 1995
`5,465,235
`Clay
`11, 1995
`5,465.338
`Mangan et al.
`11, 1995
`5,471.478
`12, 1995
`Gibbons et al.
`5,473,765
`
`US 7,917,709 B2
`Page 2
`
`5,479,638
`5,485,595
`5.490,117
`5,495,442
`5,504,760
`5,508,971
`5,513,138
`5,515,333
`5,519,847
`5,523,980
`5,524,230
`5,530,673
`5,530,828
`5,530,938
`5,532,962
`5,532.964
`5,534.456
`5,535,328
`5,541,551
`5,544,118
`5,544,356
`5,552,698
`5,554,553
`5,563,825
`5,566,314
`5,568.439
`5,572.466
`5,579,502
`5,581,723
`5,583,812
`5,592,415
`5,592.420
`5,596,526
`5,598,370
`5,600,316
`5,602987
`5,603,001
`5,606,660
`5,611,067
`5,640,528
`5,642,312
`5,648,929
`5,663,901
`5,693,570
`5,712,819
`5,719,808
`5,723,990
`5,734,567
`5,745,418
`5,754,567
`5,757,712
`5,758,100
`5,761,117
`5,768, 190
`5,768,195
`5,773,901
`5,778.418
`5,781,478
`5,787.445
`5,787,484
`RE35,881
`5,799,168
`5,802,551
`5,809,515
`5,809,558
`5,809,560
`5,818,350
`5,818,781
`5,822.245
`5,822,252
`5,822,781
`5,831,929
`5,835,935
`5,838,614
`5,845,313
`5,847,552
`5,860,083
`5,860,124
`5,862,099
`
`12, 1995
`1, 1996
`2, 1996
`2, 1996
`4, 1996
`4, 1996
`4, 1996
`5, 1996
`5, 1996
`6, 1996
`6, 1996
`6, 1996
`6, 1996
`6, 1996
`T/1996
`T/1996
`T/1996
`T/1996
`T/1996
`8, 1996
`8, 1996
`9, 1996
`9, 1996
`10, 1996
`10, 1996
`10, 1996
`11, 1996
`11, 1996
`12, 1996
`12, 1996
`1/1997
`1/1997
`1/1997
`1/1997
`2, 1997
`2, 1997
`2, 1997
`2, 1997
`3, 1997
`6, 1997
`6, 1997
`7/1997
`9, 1997
`12, 1997
`1, 1998
`2, 1998
`3, 1998
`3, 1998
`4, 1998
`5, 1998
`5, 1998
`5, 1998
`6, 1998
`6, 1998
`6, 1998
`6, 1998
`7, 1998
`7, 1998
`7, 1998
`7, 1998
`8, 1998
`8, 1998
`9, 1998
`9, 1998
`9, 1998
`9, 1998
`10, 1998
`10, 1998
`10, 1998
`10, 1998
`10, 1998
`11, 1998
`11, 1998
`11, 1998
`12, 1998
`12, 1998
`1/1999
`1/1999
`1/1999
`
`Assar et al.
`Assar et al.
`Oda et al.
`Cernea et al.
`Harari et al.
`Cernea et al.
`Manabe et al.
`Fujita et al.
`Fandrich et al.
`Sakui et al.
`Sakaue et al.
`Tobita et al.
`Kaki et al.
`Akasaka et al.
`Auclair et al.
`Cernea et al.
`Yuan et al.
`Harari et al.
`Brehner et al.
`Harari
`Robinson et al.
`Tai et al.
`Harari
`Cernea et al.
`DeMarco et al.
`Harari
`Sukegawa
`Konishi et al.
`Hasbun et al.
`Harari
`Kato et al.
`Cernea et al.
`Assar et al.
`Nijima et al.
`Moll
`Harari et al.
`Sukegawa et al.
`Estakhri et al.
`Okamoto et al.
`Harney et al.
`Harari
`Miyamoto
`Wallace et al.
`Cernea et al.
`Harari
`Harari et al.
`Roohparvar
`Griffiths et al.
`Ma et al.
`Norman
`Nagel et al.
`Odisho
`Uchino et al.
`Tanaka et al.
`Nakamura et al.
`Kantner
`Auclair et al.
`Takeuchi et al.
`Daberko
`Norman
`Barrett et al.
`Ban
`Komatsu et al.
`Kaki et al.
`Matthews et al.
`Schneider
`Estakhri et al.
`Estakhri et al.
`Gupta et al.
`Lee et al.
`Wells et al.
`Manning
`Estakhri et al.
`Estakhri et al.
`Estakhri et al.
`Brown
`Sukegawa
`Matthews et al.
`Gannage et al.
`
`Micron Ex. 1062, p. 2
`Micron v. Vervain
`IPR2021-01549
`
`

`

`3/1999 Lee et al.
`5,890,192 A
`5/1999 Wang et al.
`5,901,086 A
`5/1999 Estakhri et al.
`5,907,856 A
`6/1999 Anderson
`5,909,586 A
`7/1999 Jennings, III et al.
`5,920,884. A
`7/1999 Estakhri et al.
`5,924,113 A
`7/1999 ASnaashari
`5,928,370 A
`7/1999 Estakhri et al.
`5,930,815. A
`8/1999 Ma et al.
`5,933,368 A
`8/1999 Endo
`5,933,846 A
`8/1999 Harariet al.
`5,936,971 A
`8/1999 Ban
`5.937,425 A
`9/1999 Estakhri et al.
`5,953,737 A
`9, 1999 Ma et al.
`5,956,473 A
`9, 1999 Jones et al.
`5,959,926 A
`10/1999 Nishino
`5.966,727 A
`5,986,933 A 1 1/1999 Takeuchi et al.
`5,987,563 A 1 1/1999 Itoh et al.
`5,987,573 A 11/1999 Hiraka
`5.991,847 A 1 1/1999 Ballard et al.
`5.991,849 A 1 1/1999 Yamada et al.
`6,000,006 A 12/1999 Bruce et al.
`6,011,322. A
`1/2000 Stumfall et al.
`6,011.323 A
`1/2000 Camp
`6,018,265 A
`1/2000 Keshtbod
`6,021,408 A
`2, 2000 Ledain et al.
`6,026,020 A
`2/2000 Matsubara et al.
`6,026,027 A
`2/2000 Terrell, II et al.
`6,034,897 A
`3/2000 Estakhri et al.
`6,035,357. A
`3/2000 Sakaki
`6,040,997 A
`3/2000 Estakhri
`6,041,001 A
`3/2000 Estakhri
`6,047,352. A
`4/2000 Lakhani et al.
`6,055,184. A
`4/2000 Acharya et al.
`6,055,188 A
`4/2000 Takeuchi et al.
`6,069,827 A
`5, 2000 Sinclair
`6,072,796 A
`6/2000 Christensen et al.
`6,076,137 A
`6/2000 ASnaashari
`6,081.447 A
`6/2000 Lofgren et al.
`6,081,878 A
`6/2000 Estakhri et al.
`6,084,483. A
`7/2000 Keshtbod
`6,097.666 A
`8/2000 Sakuiet al.
`6,115,785. A
`9/2000 Estakhri et al.
`6,122,195 A
`9/2000 Estakhri et al.
`6,125,424. A
`9/2000 Komatsu et al.
`6,125,435 A
`9/2000 Estakhri et al.
`6,128,695. A 10/2000 Estakhri et al.
`6,134,145 A 10/2000 Wong
`6,134,151 A 10/2000 Estakhri et al.
`6,141,249 A 10/2000 Estakhri et al.
`6,145,051 A 1 1/2000 Estakhri et al.
`6,151,247 A 1 1/2000 Estakhri et al.
`6,172,906 B1
`1/2001 Estakhri et al.
`6,173,362 B1
`1/2001 Yoda
`6,181,118 B1
`1/2001 Meehan et al.
`6,182,162 B1
`1/2001 Estakhri et al.
`6,202,138 B1
`3/2001 Estakhri et al.
`6,223,308 B1
`4/2001 Estakhri et al.
`6,226,708 B1
`5/2001 McGoldricket al.
`6,230,234 B1
`5/2001 Estakhri et al.
`6,262,918 B1
`7/2001 Estakhri et al.
`6,272.610 B1
`8/2001 Katayama et al.
`6,275,436 B1
`8/2001 Tobita et al.
`6,279,069 B1
`8/2001 Robinson et al.
`6.279,114 B1
`8, 2001 Toombs et al.
`6,285,607 B1
`9, 2001 Sinclair
`6,327,639 B1
`12/2001 ASnaashari
`6,345,367 B1
`2/2002 Sinclair
`6,374,337 B1
`4/2002 Estakhri
`6,385,667 B1
`5/2002 Estakhri et al.
`6,393,513 B2
`5/2002 Estakhri et al.
`6,397.314 B1
`5/2002 Estakhri et al.
`f
`akhri etal
`6,411,546 B1
`6/2002 Estakhri et al.
`10/2002 Sinclair
`6,467,021 B1
`6,490,649 B2 12/2002 Sinclair
`6,567,307 B1
`5/2003 Estakhri
`6,571,318 B1
`5/2003 Sander et al.
`6,578,127 B1
`6/2003 Sinclair
`6,587,382 B1
`7/2003 Estakhri et al.
`
`US 7,917,709 B2
`Page 3
`
`3/2004 Sinclair et al.
`6,711,059 B2
`4/2004 Estakhri et al.
`6,721,819 B2
`4/2004 Estakhri
`6,721,843 B1
`4/2004 Sinclair et al.
`6,725,321 B1
`4/2004 Coulson
`6,725,342 B1
`4/2004 Estakhri et al.
`6,728,851 B1
`6/2004 Gorobets
`6,751,155 B2
`6/2004 Estakhri et al.
`6,757,800 B1
`1 1/2004 Sinclair et al.
`6,813,678 B1
`5/2005 Gorobets
`6,898,662 B2
`6/2005 Estakhri et al.
`6,912,618 B2
`9/2005 Estakhri
`6,950,918 B1
`6,957,295 B1 10/2005 Estakhri
`6,973,519 B1 12/2005 Estakhri et al.
`6,978,342 B1
`12/2005 Estakhri et al.
`7,000,064 B2
`2/2006 Payne et al.
`2003, OO33471 A1
`2/2003 Lin et al.
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`FR
`GB
`GB
`GB
`GB
`GB
`GB
`GB
`GB
`GB
`GB
`GB
`p
`JP
`E.
`JP
`JP
`JP
`JP
`JP
`E.
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`
`FOREIGN PATENT DOCUMENTS
`O 220 718 A2
`5, 1987
`O 243 503 A1 11, 1987
`O 392 895 A2 10, 1990
`O 424 191 A2
`4, 1991
`O 489 204 A1
`6, 1992
`O 522 780 A2
`1/1993
`O 522 780 B1
`1/1993
`O 544, 252 A2
`6, 1993
`O 613 151 A2
`8, 1994
`O 617 363 A2
`9, 1994
`O 619 541 A2 10, 1994
`O 663 636 A1
`T 1995
`O 686 976 A2 12/1995
`O 897 579 B1
`7, 2000
`O 891 580 B1
`11, 2000
`O 896 669 B1
`11, 2000
`f
`O 852 766 B1
`5, 2001
`9, 2001
`O 852 765 B1
`O 722,585 B1
`5, 2002
`O 910 826 B1
`6, 2002
`O 691 008 B1
`11, 2002
`O 861 468 B1
`4, 2003
`O978 040 B1
`5, 2004
`1 157328 B1
`5/2005
`93 O1908
`8, 1993
`2251 323
`7, 1992
`229 1990
`2, 1996
`229 1991
`2, 1996
`2 297 637
`T 1996
`2304 428
`3, 1997
`2348,991
`12/2002
`235.1822
`1, 2003
`2384 337
`T 2003
`2.384883
`10/2005
`2384.338
`11, 2005
`2384 O72
`12/2005
`f
`239;
`24.
`59-45695
`9, 1982
`f
`:::::
`33
`55163665
`9, 1984
`60-212900
`10, 1985
`f
`61-96.598
`5, 1986
`12/1987
`62-283496
`62-283497
`12/1987
`f
`619.
`'3.
`3-228377
`10, 1991
`4-57295
`2, 1992
`4-254994
`9, 1992
`4-298.284
`9, 1992
`4-278297
`10, 1992
`4-332999
`11, 1992
`5-128877
`5, 1993
`5-282883
`10, 1993
`6-36578
`2, 1994
`6-124175
`5, 1994
`6-124231
`5, 1994
`6-132747
`5, 1994
`
`Micron Ex. 1062, p. 3
`Micron v. Vervain
`IPR2021-01549
`
`

`

`US 7,917,709 B2
`Page 4
`
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`SU
`SU
`SU
`SU
`SU
`SU
`WO
`WO
`
`6-149395
`6-131889
`6-266596
`T-93499
`T-3 11708
`8-18018
`8-69696
`9-147581
`1388877
`1408.439
`1515164
`1541619
`1573458
`16864.49
`WO 84.00628
`WO94,20906
`
`5, 1994
`6, 1994
`9, 1994
`4f1995
`11, 1995
`1, 1996
`3, 1996
`6, 1997
`4f1988
`T 1988
`10, 1989
`2, 1990
`6, 1990
`10, 1991
`2, 1984
`9, 1994
`
`OTHER PUBLICATIONS
`Walter Lahti and Dean McCarron, “State of the Art: Magnetic VS
`Optical Store Data in a Flash'. Byte Magazine, Nov. 1, 1990.311, vol.
`15, No. 12.
`Ron Wilson, Technology Updates, Integrated Circuits, “I-Mbit flash
`memories seek their role in System design”. Computer Design 28
`Mar. 1, 1989, No. 5, Tulsa OK, US, pp. 30 and 32.
`Mendel Rosenblum and John K. Ousterhout, “The Design and Imple
`mentation of a Log-Structured File System.” 1991, 15 pgs. Berkeley,
`USA.
`Brian Dipert and Markus Levy, Designing with Flash Memory,
`Annabooks, Apr. 1994, 445 pgs.
`Science Forum, Inc. “Flash Memory Symposium'95", 1995, 13 pgs.
`Tokyo.
`Ross S. Finlayson and David R. Cheriton, “An Extended FileService
`Exploiting Write-Once Storage.” ACM Symposium On Operating
`Systems Principles, 1987, 10 pgs.
`Jason Gait, “The Optical File Cabinet: A Random-Access File Sys
`tem for Write-Once Storage'. Computer, Jun. 1988, 12 pgs.
`Henry G. Baker, Memory Management, 1995, Springer-Verlag
`Heidelberg, Germany, 19 pgs.
`Sape J. Mullender and Andrew S. Tanenbaum, "A Distributed File
`Service Based on Optimistic Concurrency Control”. ACM Press,
`1985, 12 pgs. New York, New York.
`Hiroshi Nakamura, Junichi Miyamoto, Kenichi Imamiya and
`Yoshihisa Iwata, “A Novel Sense Amplifier for Flexible Voltage
`Operation NAND Flash Memories”. VLSI Circuits, 1995, Digest of
`Technical Papers, 2 pgs.
`Hiroshi Nakamura, Junichi Miyamoto, Kenichi Imamiya, Yoshihisa
`Iwata and Hideko Oodaira, "A Novel Sensing Scheme with On-Chip
`Page Copy for Flexible Voltage NAND Flash Memories”, IEICE
`Transactions on Electronics, vol. E79-C, No. 6, pp. 836-844.
`Takaaki Nozaki, Toshiaki Tanaka, Yoshiro Kijiya, Eita Kinoshita,
`Tatsuo Tsuchiya and Yutaka Hayashi. “A 1-Mb EEPROM with
`MONOS Memory Cell for Semiconductor Disk Application”, Jour
`nal of Solid-State Circuits, vol. 26, No. 4, 5 pgs.
`
`S. Mehroura, J.H. Yuan, R.A. Cemea, W.Y. Chien, D.C. Guteman, G.
`Samachisa, R.D. Norman, M. Mofidi, W. Lee, Y. Fong, A. Mihnea, E.
`Hann, R.W. Gregor, E.P. Eberhardt, J.R. Radosevich, K.R. Stiles,
`R.A. Kohler, C.W. Leung, and T.J. Mulrooney, "Serial 9Mb F
`EEPROM for Solid State Disk Applications', symposium, 2 pgs.
`1992, Mountain View, CA.
`Steven H. Leibson, “Nonvolatile, In-Circuit-Reprogrammable
`Memories”, EDNSpecial Report, Jan. 3, 1991, No. 12, 12 pgs.
`Walter Lahti and Dean McCarron, “State of the Art: Magnetic vs.
`Optical Store Data in a Flash'. Byte Magazine, 1990, vol. 15, No. 12,
`7 pgs.
`Ramon Caceres, Fred Douglis, Kai Li and Brian Marsh, “Operating
`System Implications of Solid-State Mobile Computers'. Workshop
`on Workstation Operating Systems, Oct. 1993, pp. 21-27.
`Michael Wu and Wily Zwaenepoel, “A Non-Volatile, Main Memory
`Storage System”, ACM Press, 1994, 12 pgs. San Jose, CA.
`Dave Bursky, “Innovative flash memories match DRAM densities:
`available with a choice of features, flash memories are finding homes
`in many systems (including related articles on the origins of flash, and
`on the differences between NAND and NOR flash memories), Elec
`tronic Design, May 16, 1994, vol. 42, No. 10, 9 pgs.
`Anthony Cataldo, “New flash enhancements up ante. (Intel's
`28F400BV-120 and 28F004BV-120, Atmel's AT29BV010 and
`AT29BV020, and Samsung Semiconductor's KM29V3200 flash
`memory devices)” (product announcement), Electronic News, Mar.
`13, 1995, vol. 41, No. 2056, 4pgs.
`Sam Weber, "Flash modules' portability, reusability, Small size val
`ued for a host of APPs-Consumer formats flocking to flash”, Elec
`tronic Engineering Times, Jul. 22, 1996, No. 911, 9 pgs.
`Stan Baker, “But Integration Calls for Hardware, Software Changes:
`Flash designers face the dawn of a new memory age'. Electronic
`Engineering Times, Dec. 3, 1990, vol. 41, No. 619, 5 pgs.
`Toshiba, MOS Memory (Non-Volatile), 1995, Data Book.
`Toshiba, Toshiba MOS Digital Integrated Circuit Silicon Gate
`CMOS, (TC58NS512DC), Mar. 21, 2001, 43 pgs. Data Book.
`Toshiba, Toshiba Corporation, SMIL (Smartmedia Interface Library)
`Hardware Edition Version 1.00, Jul. 1, 2000, 136 pgs. Data Book.
`Toshiba, Toshiba MOS Digital Integrated Circuit Silicon Gate,
`(TC58512FT), Mar. 5, 2001, 43 pgs. Data Book.
`Toshiba, Toshiba MOS Digital Integrated Circuit Silicon Gate,
`(TC58DVM92A1FT00), Jan. 10, 2003, 44pgs. Data Book.
`Toshiba, Toshiba MOS Digital Integrated Circuit Silicon Gate,
`(TC58DVGO2A1FT00), Jan. 10, 2003, 44pgs. Data Book.
`Toshiba, Toshiba MOS Digital Integrated Circuit Silicon Gate,
`(TC58 100FT), Mar. 5, 2001, 43 pgs. Data Book.
`Toshiba, MOS Memory (Non-Volatile), 1996, 279 pgs. Data Book.
`“Fifth Biennial Nonvolatile Memory Technology Review.” 1993
`Conference, Jun. 22-24, 1993, Linthicum Heights, MD, USA.
`Dan Auclair, "Optimal Solid State Disk Architecture For Portable
`Computers'. Silicon Valley PC Design Conference, Jul. 9-10, 1991,
`pp. 811-815.
`
`Micron Ex. 1062, p. 4
`Micron v. Vervain
`IPR2021-01549
`
`

`

`U.S. Patent
`
`Mar. 29, 2011
`
`Sheet 1 of 5
`
`US 7,917,709 B2
`
`FIG. 1
`Prior Art
`
`Evaluate
`Repeat
`Possibilit
`
`
`
`
`
`
`
`40
`
`
`
`4.
`
`Calculate WA
`
`58
`
`44
`
`Get VA from
`SAT or SAT
`Cache
`
`Get t from
`
`N
`O
`
`ls
`Sector Deleted
`
`No
`
`ls
`Sector Bad
`
`
`
`60
`
`50
`
`Yes
`
`48
`
`46 Yes
`
`47
`
`WA= Deleted
`
`WA=Bad
`
`Micron Ex. 1062, p. 5
`Micron v. Vervain
`IPR2021-01549
`
`

`

`U.S. Patent
`
`Mar. 29, 2011
`
`Sheet 2 of 5
`
`US 7,917,709 B2
`
`FIG. 2
`Prior Art
`
`
`
`
`
`Sector Log
`Addr (LA)
`
`
`
`
`
`Address
`Translation
`
`130
`
`132
`
`
`
`ls
`Sector Deleted
`or Bad
`
`Set all bytes of
`host's data buffer
`to 0xFF
`
`134
`
`ls
`Sector Deleted
`
`NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`138
`
`Return valid status
`to a host
`
`Return error status
`to a host
`
`Micron Ex. 1062, p. 6
`Micron v. Vervain
`IPR2021-01549
`
`

`

`U.S. Patent
`
`Mar. 29, 2011
`
`Sheet 3 of 5
`
`US 7,917,709 B2
`
`FIG. 3
`
`10
`
`Logical
`int
`erce
`
`- - - - - - - - - - - - - - -
`
`Memory System
`
`FIG. 4A
`
`
`
`Expansion
`(optional)
`
`Logical
`Interface
`tO
`Host
`System
`
`Physical
`Interface
`tO
`Flash
`Memory
`
`Micron Ex. 1062, p. 7
`Micron v. Vervain
`IPR2021-01549
`
`

`

`U.S. Patent
`
`Mar. 29, 2011
`
`Sheet 4 of 5
`
`US 7,917,709 B2
`
`FIG. 4B
`16
`
`30
`
`32
`
`Expansion
`(o Rall
`p
`
`Logical
`Interface
`tO
`Host
`System 14
`
`
`
`interface
`Control
`
`M
`CO
`Processor
`
`Interface
`Control
`
`22
`
`24
`
`26
`
`Physical
`Interface
`tO
`Flash
`18 Memory
`
`block O
`
`
`
`
`
`
`
`
`
`
`
`
`
`block 1
`
`block
`
`Micron Ex. 1062, p. 8
`Micron v. Vervain
`IPR2021-01549
`
`

`

`U.S. Patent
`
`Mar.29, 2011
`
`Sheet 5 of 5
`
`roe 46
`Write
`
`BlockZ/3/3/=BlockX
`
`US 7,917,709 B2
`
`Micron Ex. 1062, p. 9
`Micron v. Vervain
`IPR2021-01549
`
`Micron Ex. 1062, p. 9
`Micron v. Vervain
`IPR2021-01549
`
`

`

`US 7,917,709 B2
`
`1.
`MEMORY SYSTEM FOR DATA STORAGE
`AND RETREVAL
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This application is a Continuation of U.S. application Ser.
`No. 10/256,891, titled “MEMORY SYSTEM FOR DATA
`STORAGE AND RETRIEVAL.” filed Sep. 27, 2002 now
`U.S. Pat. No. 7,634,624, which claims the benefit of the
`priority date of British Application No. 0123410.3, entitled
`MEMORY SYSTEM FOR DATA STORAGE AND
`RETRIEVAL.” filed on Sep. 28, 2001.
`
`10
`
`FIELD OF THE INVENTION
`
`15
`
`The present invention relates generally to a solid state
`memory system for a data storage and retrieval having a
`memory controller for controlling access to a non-volatile
`memory of the Solid state memory system and particularly to
`a method and apparatus for accessing data stored within the
`non-volatile memory of the Solid state memory system at an
`increased speed when the data has a repetitive pattern.
`
`DESCRIPTION OF THE PRIOR ART
`
`25
`
`2
`is written, the obsolete copy of the logical sector should be
`erased before or after. Here, the term erased memory sector
`will be used for a memory sector which has all the cells
`erased. Quite often the memory sectors are not individually
`erasable, but, grouped to be erasable in units or blocks. The
`controller can use various methods to maintain the flash
`memory. Any memory sector which has been written to will
`be treated by the controller as a memory sector which has not
`been erased.
`The host can issue a sector erase command to erase the
`logical sector in the memory in order to delete all the sector
`data and pre-erase the card for a faster sector write operation
`in the future. This results in the sector write operation con
`sisting of Flash memory writes only and no erases. The term
`erased logical sector is generally used not only for a logical
`sector which has been erased, but, also for a sector which has
`not yet been written. Due to the complexity of flash memory
`organization and complexity of its maintenance, various
`algorithms can be used which allows an erased logical sector
`to be temporarily marked in the SAT as obsolete, but, the
`memory sector containing the logical sector can be erased
`later. The example of such a memory system is illustrated in
`the “Memory System' detailed in patent application WO
`00/49488 PCT/GB0000550). FIG. 1 (prior art) illustrates the
`address translation algorithm of the Memory System of WO
`00/49488. FIG. 2 illustrates the sector read operation of the
`Memory System of WO 00/49488. WO 00/49488 describes
`the technique of using the SAT Table not only to define
`physical locations of the written logical sectors, but, also to
`mark them as deleted or bad. In the case of the deleted or never
`written sector the corresponding SAT entry includes the vir
`tual address value showing that the sector includes no data the
`controller sets all the bytes of the sector data buffer to all 1s
`and the sector then will be output to the host.
`Thus, a need arises to obviate or mitigate at least one of the
`aforementioned problems.
`
`IN THE DRAWINGS
`
`FIG. 1 shows an address translation algorithm of a prior art
`memory system;
`FIG. 2 shows a sector read operation of a prior art memory
`system;
`FIG.3 shows a flash memory system in accordance with an
`embodiment of the present invention;
`FIG. 4a shows a first embodiment of the hardware archi
`tecture of the controller of the flash memory of FIG. 3;
`FIG. 4b shows a second embodiment of the hardware archi
`tecture of the controller of the flash memory of FIG. 3;
`FIG. 5 shows a graphical representation of the virtual
`blocks into which the flash memory of the flash memory
`system is organized; and
`FIG. 6 shows a schematic representation of the data write
`operation used in FIG. 5.
`
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`With reference to FIG. 3, there is shown a flash memory
`system 10 in which a method of achieving faster access of the
`data in the memory system is adopted. The memory system
`10 comprises a controller 16 and flash memory 20 which are
`connected by physical interface 18. The memory system 10 is
`connected to an associated host system 12 by logical interface
`14. The logical interface 14 connects to the controller 16 of
`the memory system 10 and reads from, and writes data to the
`host system 12 in logical sectors of 512 bytes of data. Each
`
`It is known to use Solid state memory systems to try to
`emulate magnetic disk storage devices in computer systems.
`In particular, it is an aim of the industry to try to increase the
`speed of operation of Solid state memory systems to better
`emulate magnetic disc storage.
`A typical memory system comprises a non-volatile
`memory, such as a Flash memory, and a controller. The flash
`memory has individually addressable sectors wherein a
`memory sector is a group of flash memory locations which is
`allocated for storage of one Logical Sector. A memory sector
`need not be a physical partition within Flash memory, nor
`need it be contiguous Flash memory locations, so the memory
`sector address may be a virtual address conveniently used by
`the controller. The controller writes data structures to and
`reads data structures from the memory, and translates logical
`addresses received from the host to physical, or virtual
`addresses, of the memory sectors in the memory.
`When a logical sector write command is received from the
`host, the controller translates a logical address received from
`the host and allocates a memory sector for the logical sector to
`be written to. The controller is also responsible for maintain
`ing a table of logical addresses with respective physical
`addresses which have been allocated by the controller. The
`table is referred to as the Sector Allocation Table or SAT.
`There is also, in Some cases, a system or hierarchy of SATs to
`provide improved ease of access and to reduce the update
`frequency required.
`The physical or virtual, sector addresses in the SAT are
`typically ordered by logical sector address, where the Nth
`SAT entry includes the physical address of a sector to which
`data having logical address N has been written. When a sector
`read command is received from the host, the controller looks
`up a logical sector address received from the host in the SAT
`in order to obtain the physical sector address which the con
`troller previously allocated to the logical sector. On some
`occasions one SAT entry is used to define the address of a
`group of contiguous memory sectors containing a group of
`contiguous logical sectors.
`A feature of the flash memory is that the flash memory must
`be pre-erased before the data can be written. This means that,
`in general, in the flash memory system, when a logical sector
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Micron Ex. 1062, p. 10
`Micron v. Vervain
`IPR2021-01549
`
`

`

`US 7,917,709 B2
`
`3
`logical sector is identified by a logical address which in this
`case is a sequential logical blockaddress (LBA) and may be
`accessed randomly for either reading or writing data. Data is
`written to and read from the flash memory 20 in physical
`sectors each of which typically has sufficient capacity for 512
`bytes of data from the host system, plus 16 bytes of overhead
`data appended by the controller 16. Each physical sector is
`identified by a physical sector address which normally has
`separate components identifying the flash chip within the
`memory subsystem, the flash block within the flash chip and
`the physical sector within the flash block. Data may only be
`written to a physical sector if the sector has previously been
`erased, and erasure takes place in response to a command at
`the physical interface 18 in units of a flash block which
`typically includes 32 physical sectors. Physical sectors may
`be randomly accessed for reading data. In the present arrange
`ment, wherein the memory comprises NAND Flash chips, a
`physical sector is equivalent to a physical page within the
`flash array and has a capacity of 528 bytes. In this case, each
`flash chip is considered to comprise four arrays, each of
`which can be programmed with one sector at any time.
`The controller 16 provides a method of detecting the pat
`tern of the logical sector data which is due to be written to the
`flash memory 20 when a sector write command is issued by
`the host 12. If the sector data has a flat repetitive pattern, for
`example, if all the bytes of the sector data are the same, then
`the controller 16 may use the corresponding sector address
`table (SAT) entry to record the pattern, which in this case is a
`content of any one byte of sector data, and mark the logical
`sector as being erased. It is therefore, not necessary to write
`the sector data to the flash memory 20 in order to record the
`sector data, instead it is enough to keep the information about
`the sector pattern in the SAT. The obsolete copy of the sector
`data must then be erased in flash memory, as is the case when
`any new sector data is written to the flash memory system.
`However, in this case, the new valid sector data is stored in a
`SAT entry instead of in a memory sector in flash memory.
`When it is desired that the sector data be read, a logical
`sector read command is sent by the host 12 and the controller
`16 looks up the SAT and checks the virtual address value
`provided by the SAT shows that the sector data is deleted, the
`controller 16 takes the sector data pattern value from the entry
`within the SAT to output the sector data as if it was being
`retrieved from the flash memory 20.
`This operation results in the speed of the access to the flash
`data by the host 12 being greatly improved as the sector write
`operation no longer comprises the step of sector data write to
`the flash memory 20 and the sector read operation does not
`comprise the step of sector data read from the flash memory
`20.
`Some hosts may write a large number of flat data sectors
`which can be a part of large uncompressed database files. It
`is also the case that the host 12 can deliberately precondition
`or format the memory system by writing all O’s or 1's in order
`to delete all the information (which is a standard security
`feature). The ATA standard Format Track command can also
`be treated as the flat sector write command.
`With reference to FIGS. 4a and 4b there is shown the
`hardware architecture of the controller 16 of flash memory
`system 10. The controller comprises memory access control,
`or system bus 28, host interface control block 22 to which
`logical interface 14 connects, microprocessor 24, flash inter
`face control block 26 to which physical interface 18 connects,
`Read Only Memory (ROM) 30, and synchronous random
`access memory (SRAM) 32.
`The host interface control block 22 provides the path to the
`controller 16 for data flow to and from host system 12.
`
`40
`
`45
`
`4
`With reference to FIG. 4a there is shown a first embodi
`ment of the hardware architecture of controller 16 in which
`the host interface control block 22 has, embedded within
`itself, a pattern detection circuit 23a which compares all the
`data portions of incoming data when the host 12 issues a
`sector write command and sends sector data to the memory
`system 10. The pattern detection circuit 23a then indicates to
`the microprocessor whether the incoming data has a flat pat
`tern. The pattern detection circuit 23a compares all the sector
`data portions (1, 2 or 4 bytes) with each other. This can be
`done, for example, by fetching the first data portion and
`XOR-ing it with all other data portions, at least one non-zero
`result triggers signaling of a non-flat pattern. Flat pattern can
`also be detected by XOR-ing every incoming data portion
`with the previous one. The pattern value of the incoming data
`then can be obtained by the microprocessor 24 from the
`pattern detection circuit 23a or by reading any data portion
`from the sector buffer SRAM. 32.
`The host interface 22 has pattern output circuit 23b which
`can be programmed by the microprocessor 24 to output a
`certain pattern to the host 22 when the sector read command
`is received from the host, instead of transferring the sector
`data from the sector buffer SRAM. 32. The pattern value is
`obtained by the microprocessor 24 from the corresponding
`SAT entry when the sector is marked there as erased.
`With reference to FIG. 4b there is shown a second embodi
`ment of the hardware architecture of controller 16 in which
`firmware 25 of the microprocessor 24 provides a pattern
`detection facility which can compare all the data portions of
`the sector data by reading the sector buffer in SRAM. 32.
`Firmware 25 is instruction code for the microprocessor and is
`normally stored in one of the memories (ROM, SRAM or
`Flash memory).
`In this arrangement the pattern output can also be provided
`by the firmware of microprocessor 24 which