Apparatus, system, and method for generating and decoding a longer linear block codeword using a shorter block length

An apparatus, system, and method for generating and decoding a longer linear block codeword using a shorter block length. The method comprises receiving data from a storage area and generating a codeword from the received data with an encoder, the codeword having a data portion and a parity portion, wherein the codeword has a first block length, and wherein the encoder applies a linear block code, the linear block code having a second block length that is shorter than the first block length.

FIELD OF THE INVENTION

Embodiments of the invention relate generally to the field of error detection and correction. More particularly, embodiments relate to an apparatus, system, and method for generating and decoding a longer linear block codeword using a shorter block length.

BACKGROUND

Error control codes may be used in many applications, such as in error detection or correction for communication or data storage systems. For example, error control codes may be used to correct errors occurring in storage devices, such as in hard drives or NAND memories. Error control codes could also be used to detect or correct errors in data received across a noisy channel.

Attributes of error control codes, such as the type of error control code and an error control code's block length, can impact the coding gain and the complexity of the encoding and decoding implementation. One type of error control code is a Bose-Chaudhuri-Hocquenghem (BCH) code. Another type of error code is a low-density parity-check (LDPC) code. The block length also impacts implementation complexity. For example, in an LDPC code, a larger block length results in increased encoding and decoding complexity.

DETAILED DESCRIPTION

Embodiments relate to an apparatus, system, and method for generating and decoding a longer linear block codeword using a shorter block length.

The term “codeword” refers to encoded data comprising a data portion and a portion of information used for error detection or correction. In one embodiment, the portion of information used for error detection or correction is a parity portion. According to one embodiment, an encoder generates codewords. According to another embodiment, the encoder generates the information used for error detection or correction, and another logic unit generates the codewords by combining the data portion with the generated information.

The term “linear block codeword” means a codeword in a linear block code. The term “code” means a set of valid codewords. A linear block code is a subspace of a Galois field. The term “block length” refers to the length of a codeword. A code, being a set of codewords, also has a block length.

In one embodiment, a codeword is decoded to recover encoded data. In one such embodiment, recovering the encoded data by decoding of the codeword comprises correcting errors in the codeword. In one embodiment, correcting errors in the codeword comprises correcting errors in both the data portion and the parity portion of the codeword.

According to one embodiment, a longer linear block codeword is decoded by independently decoding shorter codewords, wherein the shorter codewords have a block length that is shorter than that of the longer linear block codeword. For example, in one embodiment, the longer linear block codeword comprises a data portion having a length of 4 Kbytes and a parity portion having a length of 500 bytes, and the shorter codewords each have a data portion having a length of 1 Kbyte and a parity portion of 100 bytes. In one such embodiment, the block lengths of the longer linear block codeword and each of the shorter codewords are 4.5 Kbytes and 1.1 Kbytes, respectively.

In one embodiment, partial decoding of the longer linear block codeword may be sufficient to recover encoded data. In one embodiment, if partial decoding is unsuccessful, then full decoding may be resorted to. According to one embodiment, higher coding gain may be achieved with less decoding complexity. The term “coding gain” means the difference in the input bit error rate required to achieve the same output bit error rate without an error control code as with an error control code. According to one embodiment, a coding gain that is comparable to the coding gain achieved with a longer linear block length may be achieved with decoding complexity that is similar in complexity to that for a shorter block length LDPC decoder.

Embodiments may be implemented for any number of error detection or correction applications, such as for non-volatile memories or for the transmission of data over a communication channel. In one such embodiment, the non-volatile memories may be NAND memories. Embodiments may also be implemented for dynamic static random access memory (DRAM), or for other types of storage devices.

In the following description and claims, the term “coupled” and its derivatives may be used. The term “coupled” herein may refer to two or more elements which are in direct contact (physically, electrically, magnetically, optically, etc.). The term “coupled” herein may also refer to two or more elements that are not in direct contact with each other, but still cooperate or interact with each other.

FIG. 1is a block diagram100illustrating data and parity portions for generating a longer linear block codeword using a shorter block length according to one embodiment. In one embodiment, data is received and divided into four data blocks104,106,108, and110. Although this illustration shows the data being divided into four blocks, the data could be divided into any number of blocks.

In one embodiment, one fourth of each of the data blocks104,106,108, and110is selected as portions112,114,116, and118. In one embodiment an equal portion of each of the data blocks104,106,108, and110is selected. In one embodiment, the portions112,114,116, and118may be selected from any portion of the data blocks104,106,108, and110. For example, in one embodiment, the portions112,114,116, and118are selected from the upper most bits of the data blocks104,106,108, and110. In another embodiment, the portions112,114,116, and118may be selected from different bit ranges of the data blocks104,106,108, and110. In another embodiment, the selected data could be selected from any number of the data blocks. For example, in one embodiment the selected portions112,114,116, and118could be selected entirely from data block104.

In one embodiment, each of the data blocks104,106,108, and110is encoded with an encoder to generate corresponding parity portions120,122,124, and126. According to one embodiment, corresponding codewords comprise a data portion, which is the data from a data block104,106,108, and110, and a corresponding parity portion, represented by blocks120,122,124, and126. For example, according to one embodiment, one of the corresponding codewords comprises data block104and the parity portion120.

In one embodiment, the selected portions112,114,116, and118have a combined length equal to each of the data blocks104,106,108, and110. In one embodiment, the selected portions112,114,116, and118are encoded to generate another parity portion128. In one embodiment, another codeword is generated comprising the selected portions112,114,116, and118and the other parity portion128.

According to one embodiment, the longer linear block codeword comprises data portions104,106,108, and110, the corresponding parity portions120,122,124, and126, and the other parity portion128. In another embodiment, the codeword further comprises the selected portions112,114,116, and118.

The ratio of data portions104,106,108, and110to parity portions120,122,124,126, and128in the codeword could be any number. Higher ratios may result in less overhead and increased performance. For example, in one embodiment, the ratio may be between 89 and 91 percent. Lower ratios may result in a more robust error correction scheme with higher coding gain. For example, in one embodiment the ratio may be 50 percent. In another embodiment, the ratio may be lower than 50 percent.

In one embodiment, the data portions104,106,108, and110and the parity portions120,122,124,126, and128may be distributed in any order in the codeword. For example, in one embodiment, the first portion of the codeword may comprise the data portions104,106,108, and110and the last portion of the codeword may comprise the parity portions120,122,124,126, and128. In another embodiment, the data portions104,106,108, and110may be in the last portion of the codeword. In yet another embodiment, the data portions104,106,108, and110and the parity portions120,122,124,126, and128may be distributed according to an algorithm.

FIG. 2is a block diagram200illustrating a parity-check matrix202(also known as an “H matrix”) for a longer linear block codeword using a shorter block length according to one embodiment.FIG. 2illustrates how a codeword with a longer block length can be generated using a shorter block length according to one embodiment. In one embodiment, the parity-check matrix202represents a set of parity-check equations for an LDPC code. A “parity-check equation” is an equation for computing the parity of a data portion of a codeword. For example, in one embodiment, a parity-check equation involves summing, modulo 2, some combination of bits in a data portion of a codeword to obtain a parity bit. In one embodiment, the parity-check matrix202comprises parity-check matrices with shorter block lengths204,206,208, and210. In one embodiment, the parity-check matrices with shorter block lengths204,206,208, and210comprise data portions212,214,216, and218and parity portions220,222,224, and226. In one embodiment, the parity-check matrix202further comprises a parity-check matrix comprising228,230,232,234, and236, which correspond to the selected portions112,114,116, and118and the other parity portion128ofFIG. 1. According to one embodiment, the parity portions220,222,224,226, and236are located in the last portion of the rows of the parity-check matrix202. In one embodiment, the remaining portions238of the parity-check matrix202are zeros.

AlthoughFIG. 2illustrates parity-check equations with a matrix202, in one embodiment, parity-check equations may be represented with other graphical representations. For example, in one embodiment, parity-check equations may be represented by a bipartite graph such as a Tanner graph.

Some embodiments may be described as a process which is usually depicted as a flowchart, a flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed concurrently (i.e., in parallel). Likewise, operations in a flowchart illustrated as concurrent processes may be performed sequentially in some embodiments. In addition, the order of the operations may be re-arranged. A process is terminated when its operations are completed. A process may correspond to a method, a program, a procedure, a method of manufacturing or fabrication, etc.

FIG. 3is a flowchart300illustrating the generation of a longer linear block codeword using a shorter block length according to one embodiment.

According to one embodiment, at block301, data is received from a storage area. In one embodiment, the storage area may be local. For example, in one such embodiment, the storage area may be located in a system which is generating the codeword. In one such embodiment, the storage area may be included in a solid-state drive (SSD). In another embodiment, the storage area may be remote. For example, in one such embodiment, the storage area may be located on a system which is separate from the system generating the codeword. In one such embodiment, the data may be received over a communication channel such as a telecommunications network, for example, the internet or a computer network.

Next, at block302, a codeword having a first length is generated with an encoder that applies a linear block code, wherein the linear block code has a second block length that is shorter than the first block length.

In one embodiment, the applied linear block code is an LDPC code. In another embodiment, the applied linear block code is a BCH code. In yet another embodiment, the applied linear block code could be another linear block code.

FIG. 4is a flowchart400illustrating the generation of a longer linear block codeword using a shorter block length according to another embodiment. The flow chart400ofFIG. 4is illustrated with reference to the embodiments ofFIG. 1. The flowchart400ofFIG. 4continues from block301ofFIG. 3.

In one embodiment, at block404, after receiving data from the storage area, the received data is divided into a plurality of data blocks104,106,108, and110. In one embodiment, each of the plurality of data blocks104,106,108, and110has the same length. In another embodiment, the plurality of data blocks104,106,108, and110may be of different lengths. In one such embodiment, some of the plurality of data blocks104,106,108, and110may be zero-padded to enable the use of the same encoding and decoding hardware for each of the plurality of data blocks104,106,108, and110, despite having different lengths. In one embodiment, the number of data blocks104,106,108, and110that the received data is divided into is an even number. In another embodiment, the number of data blocks104,106,108, and110is four. In yet another embodiment, the number of data blocks104,106,108, and110is an odd number.

The paths beginning at blocks406and408may be in parallel (as illustrated in flowchart400) or sequential. For example, in one embodiment, the operations of blocks406and408may be performed concurrently. In another embodiment, the operations in block408may occur before or after the operations in block406.

At block406, each of the plurality of data blocks104,106,108, and110is encoded with an encoder to generate a plurality of corresponding codewords. In one embodiment, each of the plurality of corresponding codewords, as well as the code applied by the encoder, has a block length that is equal to the second block length. According to one embodiment, each of the corresponding codewords comprises a data portion104,106,108, and110and a parity portion120,122,124, and126.

At block408, one or more portions112,114,116, and118of one or more of the plurality of data blocks104,106,108, and110are selected. In embodiments, this selection could occur at any time after receiving the data. For example, in one embodiment, the selection of one or more portions112,114,116, and118could occur prior to dividing the received data. In one embodiment, the selection of one or more portions112,114,116, and118could occur after dividing the received data into a plurality of data blocks104,106,108, and110and concurrently with the encoding of the plurality of data blocks104,106,108, and110. In one embodiment, the selected portions112,114,116, and118may comprise an equal portion from each of the plurality of data blocks104,106,108, and110.

At block410, after selecting the one or more portions112,114,116, and118, the one or more portions112,114,116, and118are encoded with the encoder to generate another parity portion128. In one embodiment, prior to encoding the selected portions112,114,116, and118, at least one of the selected portions112,114,116, and118is queued in a buffer.

At block412, the codeword is formed from the plurality of corresponding codewords and the other parity portion128, according to one embodiment. In one such embodiment, the length of the data portion of the codeword is an integer multiple of the length of the data portion of each of the corresponding codewords. For example, in one such embodiment, the length of the data portion of the codeword is 4 Kbytes and the length of the data portion of each of the corresponding codewords is 1 Kbyte. In another embodiment, the lengths of the data portions of the codeword and of each of the corresponding codewords may be 8 Kbytes and 1 Kbyte, or 8 Kbytes and 2 Kbytes, respectively. In another embodiment, the codeword further comprises another codeword, the other codeword comprising the other parity portion128and the selected one or more portions112,114,116, and118.

FIG. 5is a flowchart500illustrating decoding a longer linear block codeword using a shorter block length according to one embodiment. The flowchart500ofFIG. 5continues from block412ofFIG. 4.

At block502, the codeword is received. At block504, the received codeword is decoded with a decoder, wherein the decoder applies the linear block code, and wherein the decoding comprises decoding the corresponding codewords. In one embodiment, the decoding of the corresponding codewords is done with parity-check matrices having shorter block lengths204,206,208, and210. In one embodiment, the decoder applies hard input decoding. In another embodiment, the decoder applies soft input decoding. For example, in one embodiment the decoder may perform just one read to generate hard information. In another embodiment, multiple reads corresponding to different reference voltages are performed to generate soft information.

The codeword could be received from any number of locations. For example, in one embodiment, the codeword is received from a non-volatile memory located on the system decoding the codeword. In another embodiment, the codeword is received from a remote location. For example, the codeword may be received over the internet from a system that is separate from the system decoding the codeword.

FIG. 6is a flowchart600illustrating another embodiment in which a longer linear block codeword is decoded using a shorter block length. The flowchart600ofFIG. 6continues from block412ofFIG. 4.

At block602, the codeword is received. At block604, the received codeword is divided into the corresponding codewords. In one embodiment, each of the corresponding codewords comprises a data portion104,106,108, and110and a corresponding parity portion120,122,124, and126. At block606, each of the corresponding codewords is decoded. In one embodiment, the decoding of the corresponding codewords occurs sequentially. In one such embodiment, the hardware implementation for decoding the codeword may comprise a single decoder to apply the linear block code. In another embodiment, the decoding of the corresponding codewords occurs concurrently. In one such embodiment, performance (e.g., the speed of decoding due to parallel processing) increases may be achieved at the cost of more hardware. For example, one such hardware implementation would comprise more than one decoder to apply the linear block code.

FIG. 7is a flowchart700illustrating another embodiment in which a longer linear block codeword is decoded using a shorter block length. The flowchart700ofFIG. 7continues from block412ofFIG. 4.

At block702, the codeword is received. At block704, the received codeword is divided into the corresponding codewords. At block706, each of the corresponding codewords is decoded. At block708, if a determination is made that the decoding of all of the corresponding codewords was successful, then the process of decoding is complete as indicated by block710. In one embodiment, a codeword is successfully decoded if the syndrome is equal to 0, wherein the syndrome is cHT, c being the codeword and H being a parity-check matrix.

At block708, if a determination is made that the decoding of one or more of the corresponding codewords was unsuccessful, at block712, the other parity portion is decoded. According to one embodiment, the decoding of the other parity portion may comprise receiving the codeword again and extracting the selected portions from the data portion of the received codeword. In another embodiment, the selected portions are buffered, and therefore decoding the other parity portion does not comprise receiving the codeword again.

At block714, information obtained from decoding the other parity portion is applied to re-decode one or more of the corresponding codewords. In one embodiment, recovering one or more unsuccessfully decoded corresponding codewords may be done in a variety of ways. In one embodiment, the corresponding codewords are decoded via hard decision decoding. In another embodiment, soft information combination is applied. In one such embodiment, the soft information combining is done in a similar way as the soft information is updated at the bit node of a min-sum LDPC decoder. For example, in one embodiment, extrinsic information from another codeword (comprising the other parity portion) is treated as independent information and added to a channel Log Likelihood Ratio (LLR) of failed portions of one or more of the unsuccessfully decoded corresponding codewords.

In one embodiment, the information obtained from decoding the other parity portion is applied only to unsuccessfully decoded codewords. In one embodiment, only the unsuccessfully decoded corresponding codewords are re-decoded. In another embodiment, all of the corresponding codewords are re-decoded.

FIG. 8is a flowchart800illustrating another embodiment in which a longer linear block codeword is decoded using a shorter block length. The flowchart800ofFIG. 8continues from block706ofFIG. 7.

At block802, if a determination is made that the decoding of all of the corresponding codewords was successful, then the process of decoding is complete as indicated by block804. At block802, if a determination is made that the decoding of one or more of the corresponding codewords was unsuccessful, at block806, the other parity portion is decoded. At block808, if a determination is made that the decoding of the other parity portion is successful, at block810, at least one portion of the corresponding codewords is replaced with one or more corresponding portions obtained from decoding the other parity portion. In one embodiment, only the unsuccessfully decoded corresponding codewords have their portions replaced.

At block808, if a determination is made that the decoding of the other parity portion is unsuccessful, at block812, at least one portion of the corresponding codewords is replaced with the one or more corresponding portions obtained from decoding the other parity portion by output soft information combination, according to one embodiment. In another embodiment, unsuccessful decoding of the other parity portion may result in no portions the corresponding codewords being replaced.

FIG. 9is a system900according to one embodiment with a non-volatile memory902and logic operable to generate a codeword having a block length equal to the first block length using the second block length (wherein the first and second block lengths are the same as those referred to in block302ofFIG. 3). In one embodiment, the logic operable to generate the codeword having a block length equal to the first block length comprises an encoder904, a decoder906, and error correction logic907.

In one embodiment, the system900comprises a solid-state drive (SSD)901. In one embodiment, the system900comprises a system on chip (SOC)909including a memory controller908, and a processor914coupled to the memory controller908. In one embodiment the memory controller908comprises the logic operable to generate the codeword having a block length equal to the first block length using the second block length, including the encoder904, the decoder906, and the error correction logic907. In one embodiment, the SOC909includes other components, for example, a wireless antenna, memory, processor, etc.

In one embodiment, the SOC909communicates with the host910via a Serial Advance Technology Attachment (SATA) input-output (I/O) bus912. In one embodiment, the SOC909communicates with the host910via a Serially Attached Small System Computer (SAS) input-output (I/O) bus912. In other embodiments, other types of buses can be used for912without changes the essence of the embodiments, for example, any of a Small Computer Systems Interface (SCSI) input-output (I/O) bus, a Fibre Channel (FC) input-output (I/O) bus, a SCSI over Internet input-output (I/O) bus (iSCSI), or a Universal Serial Bus (USB) input-output (I/O) bus.

In accordance with such embodiments, if the host910is to exchange data and/or commands with a memory device in accordance with a SCSI protocol, the SCSI protocol may comply and/or be compatible with the protocol described in American National Standards Institute (ANSI) Small Computer Systems Interface-2 (SCSI-2) ANSI/InterNational Committee for Information Technology Standards (INCITS) 131-1994 Specification.

In one embodiment, the SOC909and the non-volatile memory902is part of the SSD901. In one such embodiment, the SOC909is an SSD controller. In one embodiment, the SSD901is positioned inside a personal computer, a tablet, a smart phone (also referred to as a smart device), etc. In one embodiment, the memory controller908and/or the SOC909is a standalone integrated circuit coupled to the host910and the non-volatile memory902. In another embodiment, the memory controller908and/or the SOC909is integrated in the host910.

In one embodiment, the host910comprises a processor914and an operating system916. In one embodiment, the processor914in the host910is a micro-processor designed and manufactured by INTEL CORP. of Santa Clara, Calif. In another embodiment, other processors made and designed by other vendors may be used for the host910. In one embodiment, the host910is one of a personal computer, server, client, laptop, smart-phone, and/or tablet, etc. Embodiments may have one or multiple non-volatile memories918,920,922, and924coupled to the memory controller908. While some embodiments are described with respect to the memory controller908communicating with the host910and the non-volatile memory902, it is understood that embodiments also operate with the SOC909communicating with the host910and the non-volatile memory902.

In one embodiment, the non-volatile memory902is a random-access non-volatile memory (NVRAM). In one embodiment, the non-volatile memory902is part of an SSD. In one embodiment the non-volatile memory902is a NAND flash memory. In one embodiment the non-volatile memory902is a NOR flash memory. In one embodiment, the non-volatile memory902is one of a phase change memory (PCM), stacked PCM (PCMS, also referred to as PCM and switch), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), or any other type of non-volatile memory device. In one embodiment, the non-volatile memory902is a removable drive, e.g., a Universal Serial Bus (USB) memory stick, flash card, etc.

In one embodiment, the memory controller908further comprises logic (also referred to as the first logic unit) to receive data, and logic (also referred to as the second logic unit) to divide the received data into a plurality of data blocks and to send each of the plurality of data blocks to the encoder904, wherein the encoder applies a linear block code to each of the plurality of data blocks to generate corresponding codewords, the applied linear block code and the corresponding codewords having a block length that is equal to the second block length. In one embodiment, the linear block code is an LDPC code. In one embodiment, the memory controller908further comprises logic to select and store one or more portions of the received data and logic (also referred to as a fourth logic unit) to send the one or more portions to the encoder904to generate another parity portion. In one embodiment, the logic to select and store the one or more portions comprises a buffer. In one embodiment, the memory controller908further comprises logic to generate the codeword having a block length that is equal to the first block length from the corresponding codewords and the other parity portion.

In one embodiment, the memory controller908further comprises logic (also referred to as the fifth logic unit) to receive the codeword, and logic (also referred to as the sixth logic unit) to divide the received codeword into the corresponding codewords and to send each of the corresponding codewords to the decoder906.

In one embodiment, the memory controller908further comprises logic (also referred to as the seventh logic unit) to determine whether decoding of the corresponding codewords is successful, and logic (also referred to as the eighth logic unit) to send another codeword to the decoder906when the decoding of one or more of the corresponding codewords is unsuccessful, wherein the other codeword comprises the selected portions and the other parity portion. In one embodiment, the memory controller908further comprises logic (also referred to as the ninth logic unit) operable to replace one or more portions of the corresponding codewords with corresponding portions of the other codeword and logic (also referred to as the tenth logic unit) to resend one or more of the corresponding codewords to the decoder906. In one such embodiment, that logic is in the error correction logic907.

Although logic units are referred to individually (for example, “the first logic unit,” “the second logic unit,” etc.), the functions performed by the logic units may be combined. For example, in one embodiment, the decoder906may comprise the fifth logic unit and the sixth logic unit.

FIG. 10is a block diagram1000of a controller1001comprising logic operable to generate and decode a longer block length codeword using a shorter block length according to one embodiment.FIG. 10is illustrated with reference to the embodiments ofFIGS. 3-8. The following description of block diagram1000is not intended to limit the embodiments ofFIGS. 3-8, but rather to illustrate, according to one embodiment, the relationships amongst the lengths of the data and data blocks, and the block lengths of the codewords.

According to one embodiment, the data1004has a length of ‘xL’, wherein the data1004is the same as the received data in block301ofFIG. 3, and wherein x, a positive integer, is the number of data blocks that the received data is divided into according to block404ofFIG. 4.

In one embodiment, each of the plurality of data blocks in block404ofFIG. 4is sent as a data block1008to the encoder1006, wherein each data block1008has a length of ‘L’. In one embodiment, the encoder1006applies a linear block code having a block length equal to ‘L+p’, wherein ‘p’ is the length of a parity portion generated by the encoder1006. According to one embodiment, the encoder1006generates a codeword1009, wherein the codeword1009has a block length equal to ‘L+p’. In one embodiment, each of the corresponding codewords in block406ofFIG. 4, is generated by the encoder1006as the codeword1009.

In one embodiment, at least one of the selected one or more portions in block408ofFIG. 4is a selected portion1010stored in a buffer1012. In one embodiment, the buffer1012comprises a scan chain. According to one embodiment, the selected portion1010is an equal portion of each of the plurality of data blocks referenced in block406ofFIG. 4. In another embodiment, the length of the selected portion1010is ‘L/x’. In one embodiment, the buffer1012can store ‘L(x−1)/x’ data. For example, in one embodiment, where the data1004is of length 4 Kbytes (i.e., xL=4 Kbytes) and is divided into 4 data blocks (i.e., x=4), the buffer stores 0.75 KBytes of data (i.e., three selected portions, each having a length of 0.25 KBytes). In one such embodiment, once the fourth selected portion is sent to the buffer1012, a data block of length 1 KByte (i.e., L=1 KByte), referred to as selected portions1014, is sent to the encoder1006to generate another parity portion, wherein the other parity portion is described in block410ofFIG. 4. In one embodiment, at least a portion of the selected portions1014may be stored in the buffer1012while each the plurality of data blocks is being sent to the encoder1006as the data block1008. In another embodiment, the selected portions1014may be selected prior to or after encoding each of the plurality of data blocks.

According to one embodiment, the codeword1002is the codeword described in block412ofFIG. 4and block502ofFIG. 5, wherein the codeword1002has a length of ‘xL+(x+1)p’. In one such embodiment, the codeword1002comprises the corresponding codewords and the other parity portion described in blocks406and410ofFIG. 4, respectively. In another embodiment, the codeword1002has a length of ‘x(L+p)’. In one such embodiment, the codeword1002comprises the corresponding codewords, the other parity portion, and the selected portions, described in blocks406,410, and408ofFIG. 4, respectively. In yet another embodiment, the codeword1002has another length, wherein the length of the codeword1002is longer than the block length of the codeword1009.

According to one embodiment, the apparatus further comprises logic to divide the codeword1002into corresponding codewords and to send each of the corresponding codewords to the decoder1016as a codeword1018to recover a data block1022, wherein the data block1022is, at one point in the processes, each of the plurality of data blocks in block606ofFIG. 6, as well as the corresponding portions in block810ofFIG. 8. In one embodiment, the decoder1016applies the linear block code, which is the same code applied by the encoder1006.

In one embodiment, the error correction logic1020is operable to perform the same functions as the error correction logic907ofFIG. 9.

FIG. 11is a system1100according to one embodiment comprising a host system coupled to a solid-state drive and a display, the solid-state drive comprising logic operable to generate a codeword having a block length equal to the first block length using the second block length (wherein the first and second block lengths are the same as those described in block302ofFIG. 3).

FIG. 11also includes a machine-readable storage medium to execute computer readable instructions to perform the methods of various embodiments. Elements of embodiments are also provided as a machine-readable medium for storing the computer-executable instructions (e.g., instructions to implement the flowcharts ofFIGS. 3-8). The machine-readable medium may include, but is not limited to, flash memory, optical disks, CD-ROMs, DVD ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, or other type of machine-readable media suitable for storing electronic or computer-executable instructions. For example, embodiments of the invention may be downloaded as a computer program (e.g., BIOS) which may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals via a communication link (e.g., a modem or network connection).

In one embodiment, the system1100includes, but is not limited to, a desktop computer, a laptop computer, a netbook, a tablet, a notebook computer, a personal digital assistant (PDA), a server, a workstation, a cellular telephone, a mobile computing device, a smart phone, an Internet appliance or any other type of computing device. In another embodiment, the system1100implements the methods disclosed herein and may be a system on a chip (SOC) system.

In one embodiment, the processor1102has one or more processing cores1106and1106N, where1106N represents the Nth processor core inside the processor1102where N is a positive integer. In one embodiment, the system1100includes multiple processors including processors1102and1104, where processor1104has logic similar or identical to logic of processor1102. In one embodiment, the system1100includes multiple processors including processors1102and1104such that processor1104has logic that is completely independent from the logic of processor1102. In such an embodiment, a multi-package system1100is a heterogeneous multi-package system because the processors1104and1102have different logic units. In one embodiment, the processing core1106includes, but is not limited to, pre-fetch logic to fetch instructions, decode logic to decode the instructions, execution logic to execute instructions and the like. In one embodiment, the processor1102has a cache memory1108to cache instructions and/or data of the system1100. In another embodiment of the invention, the cache memory1108includes level one, level two and level three, cache memory, or any other configuration of the cache memory within the processor1102.

In one embodiment, processor1102includes a memory control hub (MCH)1110, which is operable to perform functions that enable the processor1102to access and communicate with a memory1112that includes a volatile memory1114and/or a non-volatile memory1116. In one embodiment, the memory control hub (MCH)1110is positioned outside of the processor1102as an independent integrated circuit.

In one embodiment, the processor1102is operable to communicate with the memory1112and a chipset1118. In one embodiment, the processor1102(same as914ofFIG. 9) and the chipset1118are part of the host910ofFIG. 9. In one embodiment, the chipset1118is coupled to an SSD1120(same as901ofFIG. 9) via a SATA bus1122(same as bus912ofFIG. 9). In one embodiment, the SSD1120includes machine-readable medium for storing the computer-executable instructions to implement the flowchart ofFIGS. 3-8. In such an embodiment, the SSD1120executes the computer-executable instructions when the SSD1120is powered up.

In one embodiment, the processor1102is also coupled to a wireless antenna1124to communicate with any device configured to transmit and/or receive wireless signals. In one embodiment, the wireless antenna interface1124operates in accordance with, but is not limited to, the IEEE 802.11 standard and its related family, HomePlug AV (HPAV), Ultra Wide Band (UWB), Bluetooth, WiMAX, or any form of wireless communication protocol.

The memory1112stores information and instructions to be executed by the processor1102. In one embodiment, memory1112may also store temporary variables or other intermediate information while the processor1102is executing instructions. In one embodiment, chipset1118connects with processor1102via Point-to-Point (PtP or P-P) interfaces1126and1128. In one embodiment, chipset1118enables processor1102to connect to other modules in the system1100. In one embodiment of the invention, interfaces1126and1128operate in accordance with a PtP communication protocol such as the INTEL® QuickPath Interconnect (QPI) or the like.

In one embodiment, the chipset1118is operable to communicate with the processor1102,1104, display device1130, and other devices1132,1134,1136,1138,1140,1142,1144,1146, etc. In one embodiment, the chipset1118is also coupled to a wireless antenna1124to communicate with any device configured to transmit and/or receive wireless signals.

In one embodiment, chipset1118connects to a display device1130via an interface1148. In one embodiment, the display1130includes, but is not limited to, liquid crystal display (LCD), plasma, cathode ray tube (CRT) display, or any other form of visual display device. In one embodiment of the invention, processor1102and chipset1118are merged into a single SOC. In addition, the chipset1118connects to one or more buses1122and1150that interconnect various modules1136,1138,1140,1142, and1144. In one embodiment, buses1122and1150may be interconnected together via a bus bridge1132if there is a mismatch in bus speed or communication protocol. In one embodiment, chipset1118couples with, but is not limited to, a non-volatile memory1138, a mass storage device(s)1140, a keyboard/mouse1142, and a network interface1144via interface1124, smart TV1134, consumer electronics1146, etc.

While the modules shown inFIG. 11are depicted as separate blocks within the system1100, the functions performed by some of these blocks may be integrated within a single semiconductor circuit or may be implemented using two or more separate integrated circuits. For example, although the cache memory1108is depicted as a separate block within the processor1102, the cache memory1108can be incorporated into the processor core1106respectively. In one embodiment, the system1100may include more than one processor/processing core in another embodiment of the invention.