NAND MEMORY MANAGEMENT
Apparatus, systems, and methods manage NAND memory are described. In one embodiment, an apparatus comprises a memory controller logic to apply a binary parity check code to a binary string and convert the binary string to a ternary string. Other embodiments are also disclosed and claimed.
View as Search Results
|Apparatus and method for mapping binary to ternary and its reverse|
Patent #US 10,454,495 B2
Current AssigneeIntel Corporation
Sponsoring EntityIntel Corporation
|Content Addressable Memory (CAM) Parity And Error Correction Code (ECC) Protection|
Patent #US 20120110411A1
Current AssigneeBrocade Communications Systems Inc.
Sponsoring EntityBrocade Communications Systems Inc.
|Method and Device for Correction of Ternary Stored Binary Data|
Patent #US 20130305119A1
Current AssigneeInfineon Technologies AG
Sponsoring EntityInfineon Technologies AG
|Binary to ternary code conversion recording system|
Patent #US 3,274,611 A
Current AssigneeFrederick F. Sellers Jr, David T. Brown
Sponsoring EntityFrederick F. Sellers Jr, David T. Brown
- 1. An apparatus comprising:
a memory controller logic to; apply a binary parity check code to a binary string; and convert the binary string to a ternary string.
- View Dependent Claims (2, 3, 4, 5, 6)
- 7. A system comprising:
a 3-level NAND memory device having a plurality of memory cells; a processor to access the 3-level NAND memory device; and a 3-level NAND memory controller logic to; apply a binary parity check code to a binary string; and convert the binary string to a ternary string.
- View Dependent Claims (8, 9, 10, 11)
- 12. A method comprising:
applying a binary parity check code to a binary string; and converting the binary string to a ternary string.
- View Dependent Claims (13, 14, 15, 16)
The present disclosure generally relates to the field of electronics. More particularly, some embodiments of the invention generally relate to error control codes and mapping techniques for three (3) level NAND flash memory.
NAND memory is a type of flash memory that is non-volatile. NAND memory may be used in memory cards, flash drives, solid-state drives, and other memory products. Flash memory has a limitation on the number of erase/rewrite cycles, before it becomes unusable, or a finite number of program-erase cycles (typically written as P/E cycles). This finite limitation is sometimes referred to as the “erase endurance” or simply as “endurance” of a flash memory device.
Flash memory may be designed using single-level cells (SLCs), which store a single bit of information in each memory cell, or as multi-level cells (MLCs), which store multiple bits of information in each memory cell. In general, single-level cells have higher endurance than multi-level cells. However, multi-level cells provide higher storage density than single-level cells.
Binary information may be mapped directly to a single-level cell memory. However, multi-level cells require memory mapping operations to map binary information onto the number of levels in the multi-level cells. Hence, techniques to manage memory mapping and error correction in multi-level NAND cells may find utility.
The detailed description is provided with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items.
In the following description, numerous specific details are set forth in order to provide a thorough understanding of various embodiments. However, various embodiments of the invention may be practiced without the specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail so as not to obscure the particular embodiments of the invention. Further, various aspects of embodiments of the invention may be performed using various means, such as integrated semiconductor circuits (“hardware”), computer-readable instructions organized into one or more programs (“software”), or some combination of hardware and software. For the purposes of this disclosure reference to “logic” shall mean either hardware, software, or some combination thereof.
Mapping an binary string onto a NAND memory device which is programmed to n-levels, where n is a power of 2, is relatively straightforward. However, mapping a binary string onto a NAND memory device which is programmed to n-levels, where n is not a multiple of 2, raises issues with respect to both mapping and error correction. The subject matter described herein provides techniques to address both mapping and error correction issues for programming n-level NAND devices where n is not a multiple of 2.
The techniques discussed herein may be provided in various computing systems (e.g., including smart phones, tablets, portable game consoles, etc.
In an embodiment, the processor 102-1 may include one or more processor cores 106-1 through 106-M (referred to herein as “cores 106,” or more generally as “core 106”), a cache 108 (which may be a shared cache or a private cache in various embodiments), and/or a router 110. The processor cores 106 may be implemented on a single integrated circuit (IC) chip. Moreover, the chip may include one or more shared and/or private caches (such as cache 108), buses or interconnections (such as a bus or interconnection 112), memory controllers (such as those discussed with reference to
In one embodiment, the router 110 may be used to communicate between various components of the processor 102-1 and/or system 100. Moreover, the processor 102-1 may include more than one router 110. Furthermore, the multitude of routers 110 may be in communication to enable data routing between various components inside or outside of the processor 102-1.
The cache 108 may store data (e.g., including instructions) that are utilized by one or more components of the processor 102-1, such as the cores 106. For example, the cache 108 may locally cache data stored in a memory/storage 114 for faster access by the components of the processor 102. As shown in
As shown in
In various embodiments, memory 114 may be implemented as a 3-level NAND memory and NAND controller logic 125 implements operations to facilitate programming a 3-level NAND memory 114. A first embodiment is described with reference to FIGS. 2 and 3A-3B.
Referring to FIGS. 2 and 3A-3B, in some embodiments the NAND controller logic 125 may comprise a converter 210 to convert strings between a binary format (0/1) and a ternary format (0/1/2) and a ternary low-density parity check (LDPC) module 215. In the write path data is received (operation 305) in a binary string. At operation 310 the converter 210 converts (operation 310) the binary string to a ternary character string. The ternary data output from the converter 210 is input to an error correction module. In the embodiment depicted in
A binary to ternary mapping is a function which takes binary data and maps it to ternary symbols. In some embodiments the converter 210 implements a trivial binary to ternary mapping operation, which first obtains a decimal representation of the binary string and then converts this decimal number to its ternary representation. The compression obtained by this mapping is approximately 1.5848 which is the theoretical limit.
Trivial binary to ternary mapping suffers inherently from error propagation. For example, consider a binary string (000 . . . 001111 which is to be stored. The decimal representation of this string is 15 and the ternary representation is 000 . . . 00120, which is stored as level information in NAND cells. If there is an error on reading the ternary information from the cells, e.g., if 0000 . . . 00121, so the last level 0 is readout as level 1. The binary representation for this noisy readout is 000 . . . 0010000.
Hence an error reading a single level in the NAND memory translates to 5 bits in error in the resulting binary character string. The trivial mapping results in an error propagation by a factor of 3.5, which means that the bit error rate is 3.5× the level error rate.
In the read path ternary data retrieved (operation 330) from the NAND memory 114 is input to the ternary LDPC 215, which decodes (operation 335) the data and performs a parity check on the ternary data. The binary data output by the ternary LDPC 215 is input to the converter 210, which converts (operation 340) the ternary string to a binary string. The binary string may then be passed to the requestor (operation 345). Because error correction is performed on the ternary data (i.e., in the error free domain), read errors are corrected before the ternary data is converted to binary data. This eliminates, or at least reduces, the inherent error propagation associated with trivial binary to ternary mapping described above.
Thus, in some the embodiments depicted in FIGS. 2 and 3A-3B provide an apparatus comprising a memory controller logic to convert a binary string to a ternary string, and apply a ternary parity check code to the ternary string. The apparatus comprises logic to write the ternary string to a 3-level NAND memory. In some embodiments the logic to convert a binary string to a ternary string applies a trivial binary to ternary mapping function. The apparatus further comprises logic to read the ternary string from the 3-level NAND memory, decode a ternary string read from the 3-level NAND memory and convert the ternary string to a binary string. In some embodiments the apparatus may comprise one or more processor cores are coupled to the memory controller logic to access data stored in the 3-level NAND memory.
In some embodiments the embodiments depicted in FIGS. 2 and 3A-3B provide a system comprising a 3-level NAND memory device having a plurality of memory cells, a processor to access the 3-level NAND memory device, and a 3-level NAND memory controller logic to convert a binary string to a ternary string and apply a ternary parity check code to the ternary string. In some embodiments the system of may comprise logic to write the ternary string to the 3-level NAND memory, to convert a binary string to a ternary string applies a trivial binary to ternary mapping function, to read the ternary string from the 3-level NAND memory, decode a ternary string read from the 3-level NAND memory and convert the ternary string to a binary string.
In some embodiments the embodiments depicted in FIGS. 2 and 3A-3B provide a method comprising converting a binary string to a ternary string and applying a ternary parity check code to the ternary string. The method may further comprise writing the ternary string to a 3-level NAND memory, applying a trivial binary to ternary mapping function to the binary string, decoding a ternary string read from the 3-level NAND memory, and converting the ternary string to a binary string.
A second embodiment is described with reference to FIGS. 4 and 5A-5B.
Referring to FIGS. 4 and 5A-5B, in some embodiments the NAND controller logic 125 may comprise a binary low-density parity check (LDPC) module 410. In the write path data is received (operation 505) in a binary string. At operation 510 the binary LDPC 410 applies (510) a parity check on the binary data string. The output of the binary LDPC 410 is input to a binary/ternary converter 415, which converts (operation 515) the binary string to a ternary character string. The ternary data output from the converter 415 programmed (operation 520) into the NAND memory 114.
In the read path ternary data retrieved (operation 530) from the NAND memory 114 is input to the converter 415, which converts (operation 535) the ternary string to a binary string. The output of the converter 415 is input to the binary LDPC 410, which decodes (operation 540) the data and performs a parity check on the ternary data. The binary data output by the binary LDPC 215 may then be passed to the requestor (operation 545).
In some embodiments the converter implements a binary ternary mapping operation which maps 11 binary bits to 7 ternary symbols to provide a compression of (11/7), or approximately 1.571. Error propagation is controlled by the design of the mapping between an 11 bit binary string and a 7 symbol ternary string. The mapping is designed under the constraint that if the Hamming distance (i.e., the number of positions at which the strings are different) in the ternary domain is 1, then the Hamming distance of the corresponding binary images should also be 1. This constraint ensures that if the level information has read errors, the errors are not over-amplified by the ternary-binary mapping in the read path.
One embodiment of a method to provide a mapping between an 11 bit binary string to a 7 ternary symbol string is described with reference to
At operation 625 a ternary combination which has 11 neighbors is selected as the root node 710, and at operation 630 vertices are assigned to all ternary combinations having a Hamming distance of 1 from the ternary combination selected as the root. At operation 635 the mapping tree is populated iteratively until all 2048 remaining combinations are exhausted, thereby completing the ternary symbol portion of the mapping tree.
Once the ternary combinations are positioned on the mapping tree the binary combinations may be assigned to the nodes of the mapping tree. Thus, at operation 640 the binary 0 combination is assigned to the root node 710. At operation 645 the binary strings with a single 1 are assigned to the 11 vertices connected to the root node 710. At operation 650 the mapping tree is populated by assigning the binary labels with 2-ones to the next set of vertices and making the assignment such that the Hamming distance of 1 is attained. If a Hamming distance of 1 is not possible, choose the best possible binary label with Hamming distance 2 if possible. This process is repeated until the mapping tree is populated.
In an embodiment, one or more of the processors 802 may be the same or similar to the processors 102 of
A chipset 806 may also communicate with the interconnection network 804. The chipset 806 may include a graphics and memory control hub (GMCH) 808. The GMCH 808 may include a memory controller 810 (which may be the same or similar to the memory controller 120 of
The GMCH 808 may also include a graphics interface 814 that communicates with a graphics accelerator 816. In one embodiment of the invention, the graphics interface 814 may communicate with the graphics accelerator 816 via an accelerated graphics port (AGP). In an embodiment of the invention, a display (such as a flat panel display) may communicate with the graphics interface 814 through, for example, a signal converter that translates a digital representation of an image stored in a storage device such as video memory or system memory into display signals that are interpreted and displayed by the display. The display signals produced by the display device may pass through various control devices before being interpreted by and subsequently displayed on the display.
A hub interface 818 may allow the GMCH 808 and an input/output control hub (ICH) 820 to communicate. The ICH 820 may provide an interface to I/O devices that communicate with the computing system 800. The ICH 820 may communicate with a bus 822 through a peripheral bridge (or controller) 824, such as a peripheral component interconnect (PCI) bridge, a universal serial bus (USB) controller, or other types of peripheral bridges or controllers. The bridge 824 may provide a data path between the CPU 802 and peripheral devices. Other types of topologies may be utilized. Also, multiple buses may communicate with the ICH 820, e.g., through multiple bridges or controllers. Moreover, other peripherals in communication with the ICH 820 may include, in various embodiments of the invention, integrated drive electronics (IDE) or small computer system interface (SCSI) hard drive(s), USB port(s), a keyboard, a mouse, parallel port(s), serial port(s), floppy disk drive(s), digital output support (e.g., digital video interface (DVI)), or other devices.
The bus 822 may communicate with an audio device 826, one or more drive(s) 828, which may be embodied as a disk drive or a solid state drive, and a network interface device 830 (which is in communication with the computer network 803). Other devices may communicate via the bus 822. Also, various components (such as the network interface device 830) may communicate with the GMCH 808 in some embodiments of the invention. In addition, the processor 802 and the GMCH 808 may be combined to form a single chip. Furthermore, the graphics accelerator 816 may be included within the GMCH 808 in other embodiments of the invention.
Furthermore, the computing system 800 may include volatile and/or nonvolatile memory (or storage). For example, nonvolatile memory may include one or more of the following: read-only memory (ROM), programmable ROM (PROM), erasable PROM (EPROM), electrically EPROM (EEPROM), a disk drive (which may be a magnetic hard disk drive or a NAND flash memory based solid state drive) (e.g., 828), a floppy disk, a compact disk ROM (CD-ROM), a digital versatile disk (DVD), flash memory, a magneto-optical disk, or other types of nonvolatile machine-readable media that are capable of storing electronic data (e.g., including instructions).
As illustrated in
In an embodiment, the processors 902 and 904 may be one of the processors 802 discussed with reference to
As shown in
The chipset 920 may communicate with a bus 940 using a PtP interface circuit 941. The bus 940 may have one or more devices that communicate with it, such as a bus bridge 942 and I/O devices 943. Via a bus 944, the bus bridge 943 may communicate with other devices such as a keyboard/mouse 945, communication devices 946 (such as modems, network interface devices, or other communication devices that may communicate with the computer network 803), audio I/O device, and/or a data storage device 948. The data storage device 948 (which may be a hard disk drive or a NAND flash based solid state drive) may store code 949 that may be executed by the processors 902 and/or 904.
In various embodiments of the invention, the operations discussed herein, e.g., with reference to
Although the embodiments described herein is directed to binary to ternary mapping, one skilled in the art will recognize that the techniques may be adapted for binary to n-ary mapping, where n may be 5, 7, 9 or any non-trivial mapping between binary to n-ary.
Additionally, such tangible computer-readable media may be downloaded as a computer program product, wherein the program may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals (such as in a carrier wave or other propagation medium) via a communication link (e.g., a bus, a modem, or a network connection).
Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment may be included in at least an implementation. The appearances of the phrase “in one embodiment” in various places in the specification may or may not be all referring to the same embodiment.
Also, in the description and claims, the terms “coupled” and “connected,” along with their derivatives, may be used. In some embodiments of the invention, “connected” may be used to indicate that two or more elements are in direct physical or electrical contact with each other. “Coupled” may mean that two or more elements are in direct physical or electrical contact. However, “coupled” may also mean that two or more elements may not be in direct contact with each other, but may still cooperate or interact with each other.
Thus, although embodiments of the invention have been described in language specific to structural features and/or methodological acts, it is to be understood that claimed subject matter may not be limited to the specific features or acts described. Rather, the specific features and acts are disclosed as sample forms of implementing the claimed subject matter.