Decoder With Targeted Symbol Flipping Recovery Of Miscorrected Codewords

FIELD OF THE INVENTION

0001Various embodiments of the present inventions provide apparatuses and methods for targeted symbol flipping recovery of miscorrected codewords in a decoder.

BACKGROUND

0002Various data transfer systems have been developed including storage systems, cellular telephone systems, and radio transmission systems. In such systems data is transferred from a sender to a receiver via some medium. For example, in a storage system, data is sent from a sender (i.e., a write function) to a receiver (i.e., a read function) via a storage medium. In some cases, the data processing function receives data sets and applies a data decode algorithm to the data sets to recover an originally written data set. When data fails to converge in a decoder, an error recovery operation can be initiated to change decoder input values before again applying the data decode algorithm. However, such an error recovery operation increases latency and can produce multiple copies of the same results.

SUMMARY

0003An apparatus for decoding data is disclosed including a decoder circuit operable to apply a decoding algorithm to a decoder input to yield a codeword, a convergence detection circuit operable to determine whether parity checks are satisfied by the decoder input and to identify unsatisfied parity checks in the decoder circuit, and a symbol flipping controller operable to change values of at least one symbol in the decoder input based on information about the unsatisfied parity checks. The decoder circuit is restarted to process the decoder input with the changed values. The information about the unsatisfied parity checks is obtained at each of a number of local decoding iterations in the decoder circuit.

0004This summary provides only a general outline of some embodiments of the invention. Additional embodiments are disclosed in the following detailed description, the appended claims and the accompanying drawings.

BRIEF DESCRIPTION OF THE FIGURES

A further understanding of the various embodiments of the present invention may be realized by reference to the figures which are described in remaining portions of the specification. In the figures, like reference numerals may be used throughout several drawings to refer to similar components.

<figref idref="DRAWINGS">FIG. 1</figref> depicts a block diagram of a data processing system with a decoder with targeted symbol flipping recovery of miscorrected codewords in accordance with some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 2</figref> depicts a block diagram of a low density parity check decoder with targeted symbol flipping recovery of miscorrected codewords in accordance with some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 3</figref> depicts a diagram of a codeword memory and hash calculator and comparator in a decoder in accordance with some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 4</figref> depicts a codeword hash calculation in accordance with some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 5</figref> depicts a diagram of an unsatisfied parity check count comparator that can be used to initiate a targeted symbol flipping operation during and between local decoding iterations in a decoder in accordance with some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 6</figref> depicts a flow diagram showing a method for initiating a targeted symbol flipping operation in a decoder based on supplementary unsatisfied parity check information and for preventing duplicate codewords in accordance with various embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 7</figref> depicts a storage system including a decoder with targeted symbol flipping recovery of miscorrected codewords using hashing and supplementary unsatisfied parity check information in accordance with some embodiments of the present invention; and

<figref idref="DRAWINGS">FIG. 8</figref> depicts a wireless communication system including a decoder with targeted symbol flipping recovery of miscorrected codewords using hashing and supplementary unsatisfied parity check information in accordance with some embodiments of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

0014A decoder with targeted symbol flipping recovery of miscorrected codewords is disclosed herein which uses supplementary unsatisfied parity check information to initiate early targeted symbol flipping operations and which uses hashing to prevent duplicate output codewords. The targeted symbol flipping recovery of miscorrected codewords can be applied in any suitable data decoder, such as, but not limited to, a low density parity check (LDPC) decoder. Decoder technology is applicable to transmission of information over virtually any channel or storage of information on virtually any media. Transmission applications include, but are not limited to, optical fiber, radio frequency channels, wired or wireless local area networks, digital subscriber line technologies, wireless cellular, Ethernet over any medium such as copper or optical fiber, cable channels such as cable television, and Earth-satellite communications. Storage applications include, but are not limited to, hard disk drives, compact disks, digital video disks, magnetic tapes and memory devices such as dynamic random-access memory, negated-AND flash, negated-OR flash, other non-volatile memories and solid state drives.

0015A decoder decodes blocks of data, such as a data sector read from a magnetic hard disk drive, generating codewords and yielding hard decisions for the codewords as a decoded output when parity checks are satisfied for the codewords. Targeted symbol flipping is initiated when normal decoding fails, for example when the data in the decoder fails to converge on values that satisfy all parity checks or other error correction code constraints. Targeted symbol flipping is also initiated when the data converges on values that satisfy all parity checks but which are not fully correct, a condition that can be detected using cyclic redundancy checks (CRCs) or other additional tests.

0016During targeted symbol flipping, the input values to the decoder for selected bits or symbols are changed and decoding is repeated in an attempt to cause the decoder to converge. The term “symbol flipping” is used herein to refer to changing the values of symbols during a decoding operation in an attempt to cause the codewords to converge on values which satisfy parity checks. The symbols may each include one or more bits. In a non-binary decoder, a symbol may be flipped by changing the hard decision and/or log-likelihood ratio (LLR) input value to a different element of the Galois Field associated with the decoder. For example, in a GF(4) decoder, the symbol can be flipped by adding 1, 2 or 3 to the hard decision. The symbol flipping can be performed in any manner suitable to the particular decoder and the format of its input. For example, the input to the decoder can consist of a hard decision identifying one of the Galois Field elements as the most likely real value along with a log likelihood ratio value for each of the other Galois Field elements, indicating the likelihood that the real value corresponds to each of the other Galois Field elements. In this case, the symbol can be flipped by selecting another of the Galois Field elements as the hard decision.

0017In some embodiments, the codeword generated by the decoder corresponds to an entire data sector of a storage device. In some embodiments, the codeword is subdivided into portions referred to as component codewords. For example, in some embodiments the codeword is divided into four component codewords which are independently decoded, with convergence being checked in the decoder for a component codeword at the end of a local decoding iteration and/or at intermediate stages during a local decoding iteration based on supplementary information about unsatisfied parity checks, also referred to herein as intermediate information about unsatisfied parity checks.

0018The supplementary information about unsatisfied parity checks can include a count and list of unsatisfied parity checks generated at the end of each local decoding iteration, and in some embodiments, generated during local decoding iterations as the list of unsatisfied parity checks is updated while the local decoding iteration is performed. Furthermore, after a local decoding iteration with a larger number of unsatisfied parity checks than can typically be resolved with targeted symbol flipping, rather than simply terminating the decoding operation or attempting a different recovery option, additional local decoding iterations can be performed to determine whether the number of unsatisfied parity checks continues to decline. Where the number of unsatisfied parity checks continues to decline with additional local decoding iterations, the decoding process is continued and when the number of unsatisfied parity checks falls below a threshold, the local decoding iterations are stopped and a targeted symbol flipping operation is initiated. Intermediate information about unsatisfied parity checks helps miscorrection recovery by providing information from each local iteration, allowing the decoder to arrive at a state in which targeted symbol flipping can be successful, rather than simply giving up when an iteration results in an overwhelmingly large number of unsatisfied checks.

0019Turning now to <figref idref="DRAWINGS">FIG. 1</figref>, a data processing system <b>100</b> is depicted including a decoder <b>140</b> with targeted symbol flipping recovery of miscorrected codewords in accordance with some embodiments of the present invention. In particular, data processing system <b>100</b> may comprise a read channel for a magnetic storage device such as a hard disk drive. Data processing system <b>100</b> includes an analog front end circuit <b>102</b> that receives an analog signal <b>104</b>. Analog front end circuit <b>102</b> processes analog signal <b>104</b> and provides a processed analog signal <b>106</b> to an analog to digital converter circuit <b>110</b>. Analog front end circuit <b>102</b> may include, but is not limited to, an analog filter and an amplifier circuit as are known in the art. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of circuitry that may be included as part of analog front end circuit <b>102</b>. In some cases, analog signal <b>104</b> is derived from a read/write head assembly that is disposed in relation to a storage medium. In other cases, analog signal <b>104</b> is derived from a receiver circuit that is operable to receive a signal from a transmission medium. The transmission medium may be wired or wireless. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of sources from which analog input <b>104</b> may be derived.

0020Analog to digital converter circuit <b>110</b> converts processed analog signal <b>106</b> into a corresponding series of digital samples <b>112</b>. Analog to digital converter circuit <b>110</b> may be any circuit known in the art that is capable of producing digital samples corresponding to an analog input signal. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of analog to digital converter circuits that may be used in relation to different embodiments of the present invention. Digital samples <b>112</b> are provided to an equalizer circuit <b>114</b>. Equalizer circuit <b>114</b> applies an equalization algorithm to digital samples <b>112</b> to yield an equalized output <b>116</b>. In some embodiments of the present inventions, equalizer circuit <b>114</b> is a digital finite impulse response (DFIR) filter circuit as are known in the art. Equalized output <b>116</b> is stored in a memory or Y buffer <b>118</b>. In some cases, equalized output <b>116</b> is received directly from a storage device in, for example, a solid state storage system. In such cases, analog front end circuit <b>102</b>, analog to digital converter circuit <b>110</b> and equalizer circuit <b>114</b> can be eliminated where the data is received as a digital data input.

0021Equalized data <b>106</b> is provided to a data detector circuit <b>120</b>, which is operable to apply a data detection algorithm to a received codeword or data set, and in some cases data detector circuit <b>120</b> can process two or more codewords in parallel. In some embodiments of the present invention, data detector circuit <b>120</b> is a Viterbi algorithm data detector circuit as is known in the art. In other embodiments of the present inventions, data detector circuit <b>120</b> is a maximum a posteriori data detector circuit as is known in the art. Of note, the general phrases “Viterbi data detection algorithm” or “Viterbi algorithm data detector circuit” are used in their broadest sense to mean any Viterbi detection algorithm or Viterbi algorithm detector circuit or variations thereof including, but not limited to, bi-direction Viterbi detection algorithm or bi-direction Viterbi algorithm detector circuit. Also, the general phrases “maximum a posteriori data detection algorithm” or “maximum a posteriori data detector circuit” are used in their broadest sense to mean any maximum a posteriori detection algorithm or detector circuit or variations thereof including, but not limited to, simplified maximum a posteriori data detection algorithm and a max-log maximum a posteriori data detection algorithm, or corresponding detector circuits. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of data detector circuits that may be used in relation to different embodiments of the present inventions. Data detector circuit <b>120</b> is started based upon availability of a data set from Y buffer <b>118</b> or from a central memory circuit <b>130</b>.

0022Upon completion, data detector circuit <b>120</b> provides detector output <b>122</b>, or soft data. As used herein, the phrase “soft data” is used in its broadest sense to mean reliability data with each instance of the reliability data indicating a likelihood that a corresponding bit position or group of bit positions has been correctly detected. In some embodiments of the present inventions, the soft data or reliability data is log likelihood ratio data as is known in the art. Detected output <b>122</b> is provided to a local interleaver circuit <b>124</b>. Local interleaver circuit <b>124</b> is operable to shuffle sub-portions (i.e., local chunks) of the data set included as detected output <b>122</b> and provides an interleaved codeword <b>126</b> that is stored to central memory circuit <b>130</b>. Interleaver circuit <b>124</b> may be any circuit known in the art that is capable of shuffling data sets to yield a re-arranged data set. Interleaved codeword <b>126</b> is stored to central memory circuit <b>130</b>. The interleaved codeword <b>126</b> is accessed from central memory circuit <b>130</b> as a stored codeword <b>132</b> and globally interleaved by a global interleaver/de-interleaver circuit <b>134</b>. Global interleaver/De-interleaver circuit <b>134</b> may be any circuit known in the art that is capable of globally rearranging codewords. Global interleaver/De-interleaver circuit <b>134</b> provides a decoder input <b>136</b> to a low density parity check decoder <b>140</b> with targeted symbol flipping recovery of miscorrected codewords. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize other decode algorithms that may be used in relation to different embodiments of the present invention, in association with the targeted symbol flipping recovery of miscorrected codewords disclosed herein. The decoder <b>140</b> applies a data decode algorithm to decoder input <b>136</b> in a variable number of local iterations.

0023Where the decoder <b>140</b> fails to converge (i.e., fails to yield the originally written data set) and a number of local iterations through LDPC decoder <b>140</b> exceeds a threshold, the resulting decoded output can be provided as a decoded output <b>142</b> back to central memory circuit <b>130</b> where it is stored awaiting another global iteration through data detector circuit <b>120</b> and decoder <b>140</b>. Multiple sectors may be processed simultaneously in the data processing system <b>100</b>, with additional sectors being admitted to the data detector <b>120</b> as other sectors converge in the decoder <b>140</b> and are output and cleared from the Y buffer <b>118</b> and central memory circuit <b>130</b>.

0024Prior to storage of decoded output <b>142</b> to central memory circuit <b>130</b>, decoded output <b>142</b> is globally de-interleaved to yield a globally de-interleaved output <b>144</b> that is stored to central memory circuit <b>130</b>. The global de-interleaving reverses the global interleaving earlier applied to stored codeword <b>132</b> to yield decoder input <b>136</b>. Once data detector circuit <b>120</b> is available, a previously stored de-interleaved output <b>144</b> is accessed from central memory circuit <b>130</b> and locally de-interleaved by a de-interleaver circuit <b>146</b>. De-interleaver circuit <b>146</b> re-arranges stored decoder output <b>150</b> to reverse the shuffling originally performed by interleaver circuit <b>124</b>. A resulting de-interleaved output <b>152</b> is provided to data detector circuit <b>120</b> where it is used to guide subsequent detection of a corresponding data set received as equalized output <b>116</b>.

0025Alternatively, where the decoded output converges (i.e., yields the originally written data set) in the decoder <b>140</b>, the resulting decoded output is provided as an output codeword <b>160</b> to a hard decision deinterleaver <b>162</b>, which rearranges the data to reverse both the global and local interleaving applied to the data to yield a de-interleaved output <b>164</b>. De-interleaved output <b>164</b> is stored in a hard decision memory <b>166</b> and is then provided to a read interface <b>172</b>, which can perform additional error checking such as cyclic redundancy checks (CRC) on the de-interleaved output <b>164</b>. Data <b>174</b> can then be forwarded to a hard disk controller <b>176</b> or other destination, either automatically or as instructed by the decoder <b>140</b>.

0026When the decoder input <b>136</b> fails to converge in the decoder <b>140</b>, or converges on incorrect codewords, one or more symbols at a time can be flipped in the decoder <b>140</b>, based on a list of check nodes in the decoder <b>140</b> which fail parity checks. Supplemental or intermediate information about the unsatisfied parity checks can be used to trigger targeted symbol flipping in the decoder <b>140</b>, in some cases even if the number of unsatisfied parity checks is initially larger than can normally be resolved with targeted symbol flipping, and in some cases by monitoring information about unsatisfied parity checks that is updated as while decoding is ongoing, during a local decoding iteration.

0027Turning to <figref idref="DRAWINGS">FIG. 2</figref>, a low density parity check decoder <b>200</b> with targeted symbol flipping recovery of miscorrected codewords is depicted in accordance with some embodiments of the present invention. A decoder input <b>202</b> is stored in memory <b>204</b>, representing the likelihoods or perceived values of each symbol in the data being decoded. A variable node processor <b>212</b> reads the perceived values <b>206</b> and stores updated values <b>210</b>, and exchanges variable node to check node messages <b>214</b> and check node to variable node messages <b>220</b> with a check node processor <b>216</b> in an iterative decoding process.

0028A convergence detector and hash calculation circuit <b>224</b> determines whether data has converged in the decoder <b>200</b> by determining whether the syndrome s=cH^Tis all zero. A low density parity check code is defined by a sparse parity check matrix H of size m×n, where m&lt;n. A codeword c of length n satisfies all the m parity check equations defined by H, i.e., cH^T=0, where 0 is a zero vector. The syndrome is a vector of length m, with each bit corresponding to a parity check in the parity check matrix or H matrix. A zero bit in a syndrome means the check is satisfied, while a non-zero bit in the syndrome is an unsatisfied check (USC). By definition, a codeword c, defined by the hard decisions <b>222</b> from the variable node processor <b>212</b>, has syndrome s=0. A non-codeword has a non-zero syndrome. The syndrome is calculated in the convergence detector and hash calculation circuit <b>224</b> as the dot product of the codeword c and the parity check matrix H.

0029The convergence detector and hash calculation circuit <b>224</b> also calculates a hash value for the codeword c or for component codewords that combine to form codeword c. As codewords are generated in the decoder <b>200</b>, they can be stored in codeword buffer <b>230</b>, forming a pool or candidate codewords, some of which may be miscorrected codewords that satisfy the parity checks but which are not identical to the original data. The convergence detector and hash calculation circuit <b>224</b> includes a comparator that compares the newly calculated hash value for the current codeword or component codeword with previously calculated hash values <b>232</b> corresponding to codewords or component codewords stored in a codeword buffer <b>230</b>, generated by previous decoding iterations for the same data sector. If the newly calculated hash value for the current codeword or component codeword is different from the previously calculated hash values <b>232</b>, it is assumed that the current codeword or component codeword is unique and not identical to any stored in codeword buffer <b>230</b>, and the codeword or component codeword and its hash value <b>226</b> are stored in codeword buffer <b>230</b>. After storing a number of codewords in codeword buffer <b>230</b>, one of them is selected as the output codeword and the corresponding hard decisions <b>234</b> are output. The selection of the output codeword can be performed in any suitable manner, for example using a cyclic redundancy check to identify the correct codeword. The selection of the output codeword can be triggered in one more manners, such as when the codeword buffer <b>230</b> is full, or after a particular number of local and/or global decoding iterations has been performed, or when a read interface has requested that another data sector be read and the data processing system is needed for other tasks, etc. The convergence detector and hash calculation circuit <b>224</b> can be implemented as independent circuits or as a combined circuit containing syndrome and hash calculation circuits.

0030A scheduler and targeted symbol flipping controller <b>240</b> controls both normal decoding and retry operations in the decoder <b>200</b>. The scheduler and targeted symbol flipping controller <b>240</b> provides decoding instructions <b>244</b>, <b>246</b> to the variable node processor and check node processor <b>216</b> about circulants to be processed, etc. During a symbol flipping operation, the scheduler and targeted symbol flipping controller <b>240</b> also includes symbols flipping information in instructions <b>244</b>, and receives unsatisfied check information <b>236</b> and symbol values <b>242</b> enabling it to determine which symbols to flip and which values can be tried.

0031Turning to <figref idref="DRAWINGS">FIG. 3</figref>, a codeword memory with hash calculator and comparator <b>300</b> that can be used in a decoder to store codeword candidates in accordance with some embodiments of the present invention. As a codeword <b>302</b> is generated during a decoding and/or retry operation in a decoder (e.g., <b>200</b>), a hash calculator and comparator circuit <b>304</b> calculates a hash value for the codeword <b>302</b> using any suitable technique, such as, but not limited to, an XOR operation of the bits in the codeword <b>302</b>. In some embodiments, the hash calculator and comparator circuit <b>304</b> computes the hash value for the uniqueness check based on the accumulated syndrome of the processed data set. The hash calculator and comparator circuit <b>304</b> compares the newly calculated hash value with hash values <b>330</b> stored in memory <b>308</b> for codewords stored in memory <b>308</b> that were generated previously in the decoding or retry operation. If the newly calculated hash value is different than any of the hash values <b>330</b> stored in memory <b>308</b>, it can be assumed that the codeword <b>302</b> is unique and not already stored in memory <b>308</b>. A codeword gate <b>310</b> allows the codeword <b>302</b> to be stored in memory <b>308</b> based on the indication <b>306</b> from the hash calculator and comparator circuit <b>304</b> that the hash value for the codeword <b>302</b> is unique. For example, assume that three different codewords were previously generated for a data sector and stored in codeword slots <b>314</b>, <b>316</b>, <b>320</b> of memory <b>308</b>, with their hash values stored in hash slots <b>332</b>, <b>334</b>, <b>336</b> of memory <b>308</b>, and assuming that memory <b>308</b> can contain 6 codewords. Codeword slots <b>322</b>, <b>324</b>, <b>326</b> and corresponding hash slots <b>340</b>, <b>342</b>, <b>344</b> remain available for use. When a newly generated codeword <b>302</b> is available, hash calculator and comparator circuit <b>304</b> calculates the hash value for codeword <b>302</b> and compares it with the hashes stored in hash slots <b>332</b>, <b>334</b>, <b>336</b>. If the new hash value matches any of the previous hashes, codeword <b>302</b> is a duplicate of one of those stored in codeword slots <b>314</b>, <b>316</b>, <b>320</b> and is discarded. If, on the other hand, the new hash value does not match any of the previous hashes, codeword <b>302</b> is stored in an available slot (e.g., <b>322</b>) in memory <b>308</b>. Thus, memory <b>308</b> is prevented from filling up with duplicate codewords that might be generated during the targeted symbol flipping operation.

0032In some embodiments, the contents of the codeword memory <b>308</b> are updated each time a component codeword is available, or a portion of a codeword, and in these cases, the hash calculation, storage and comparison can be done on a component codeword basis.

0033Completion of a symbol flipping operation can be based on any suitable conditions, such as, but not limited to, the codeword memory <b>308</b> becoming full, or a limit on processing time for a sector being reached, or a read request for other data requiring the decoder to move on, etc. Any suitable technique can be used to select one of the codewords <b>350</b> stored in codeword memory being selected as output <b>354</b> by a codeword selector <b>352</b>. For example, in some embodiments the codeword selector <b>352</b> applies cyclic redundancy checks to candidate codewords in codeword memory <b>308</b> to select the correct codeword.

0034Depending on the complexity of the hash algorithm applied by hash calculator and comparison circuit <b>304</b>, it is possible that some duplication of codewords may remain. However, the goal of avoiding duplicate codewords can be balanced against the need for efficient hash calculations and for compact and low power hardware. A simpler hash algorithm can be faster and require less power and complex circuitry, at the greater risk of duplicate codewords. A more complex hash algorithm can provide better protection against duplicate codewords, at the possible costs of higher memory requirements to store hash values, greater latency in calculating hash values and more complex hash calculation circuits.

0035Turning to <figref idref="DRAWINGS">FIG. 4</figref>, a diagram <b>400</b> depicts an example hash calculation in accordance with some embodiments of the invention. In this embodiment, all bits in the same circulant <b>420</b>, <b>422</b>, <b>424</b>, <b>426</b>, <b>430</b> are XORed together to yield hash bits <b>406</b>, <b>410</b>, <b>412</b>, <b>414</b>, <b>416</b>. For example, bits <b>432</b>, <b>434</b>, <b>436</b>, <b>440</b> of circulant <b>420</b> are XORed to yield hash bit <b>406</b>. (The diagram <b>400</b> is simplified, not showing all bits of circulants for a codeword <b>404</b> or all resulting bits in the hash <b>402</b>.) Again, the codeword can be divided in any convenient manner with sub-portions updated when they are available from the decoder, calculating hash values circulant by circulant in a quasi-cyclic decoder that processes in circulant-wise fashion. In such a decoder, with a code having 108 circulants, the hash will be a 108 bit vector, one bit per circulant.

0036Targeted symbol flipping can be initiated at various times during decoding when the number of unsatisfied parity checks falls below a threshold, and not just at the end of the first local decoding iteration. Turning to <figref idref="DRAWINGS">FIG. 5</figref>, a <b>500</b> diagram depicts an unsatisfied parity check count comparator <b>502</b> that can be used to initiate a targeted symbol flipping operation during and between local decoding iterations in a decoder in accordance with some embodiments of the present invention. The unsatisfied parity check count <b>504</b> is compared with a threshold <b>506</b> by the comparator <b>502</b>, and a trigger signal <b>510</b> is asserted to initiate targeted symbol flipping when the number of unsatisfied parity checks is below the threshold <b>506</b>. The threshold <b>506</b> is set at a level low enough that targeted symbol flipping can be expected to overcome the remaining unsatisfied parity checks to help data converge. When the number of unsatisfied parity checks is above the threshold, targeted symbol flipping is generally not effective or efficient enough.

0037However, in some embodiments, when the number of unsatisfied parity checks <b>504</b> is greater than the threshold <b>506</b>, for example at the end of the first local decoding iteration of a particular global decoding iteration, local decoding iterations can be continued while the number of unsatisfied parity checks <b>504</b> decreases, in the hope that it will fall below the threshold <b>506</b> and targeted symbol flipping can be initiated. For example, Table 1 below gives the number of unsatisfied parity checks for two component codewords as they are processed in parallel in a low density parity check decoder:

0000<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="70pt" align="center" /><colspec colname="2" colwidth="63pt" align="center" /><colspec colname="3" colwidth="84pt" align="center" /><thead><row><entry namest="1" nameend="3" rowsep="1">TABLE 1</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry>Local Iteration</entry><entry>USC Count CCW0</entry><entry>USC Count CCW1</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="70pt" align="center" /><colspec colname="2" colwidth="63pt" align="char" char="." /><colspec colname="3" colwidth="84pt" align="char" char="." /><tbody valign="top"><row><entry>0</entry><entry>146</entry><entry>180</entry></row><row><entry>1</entry><entry>51</entry><entry>58</entry></row><row><entry>2</entry><entry>16</entry><entry>35</entry></row><row><entry>3</entry><entry>7</entry><entry>16</entry></row><row><entry>4</entry><entry>2</entry><entry>0</entry></row><row><entry>5</entry><entry>0</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0038At the end of the first local decoding iteration, the number of unsatisfied parity checks for a first component codeword CCW0 is 146, and for a second component codeword CCW1 is 180. If at most 7 unsatisfied parity checks can be expected to be corrected by targeted symbol flipping in an acceptable manner, the threshold is set at 7 (for a less than or equal to comparison) or 8 (for a less than comparison). Notably, although the number of unsatisfied parity checks is unacceptably high for targeted symbol flipping initially, additional local decoding iterations can be performed until the number of unsatisfied parity checks falls. In this case, targeted symbol flipping can be initiated for the first component codeword CCW0 after local decoding iteration 3, when the number of unsatisfied parity checks has fallen to 7. In some embodiments which process multiple circulants in parallel, the number of unsatisfied parity checks is examined for circulant pairs that are being processed in parallel, and targeted symbol flipping is initiated at the first convergence check for the circulant pair that satisfies the threshold.

0039In some embodiments, the targeted symbol flipping is performed on the initial decoder input. In some other embodiments, the targeted symbol flipping is performed on the later results of one or more local decoding iterations, effectively rolling back the state of the data to a point where targeted symbol flipping can be productive.

0040Turning to <figref idref="DRAWINGS">FIG. 6</figref>, a flow diagram <b>600</b> depicts an operation for initiating a targeted symbol flipping operation in a decoder based on supplementary unsatisfied parity check information and for preventing duplicate codewords in accordance with various embodiments of the present invention. Following flow diagram <b>600</b>, the number of unsatisfied parity checks is retrieved during a local decoding iteration. (Block <b>602</b>) This can be performed as convergence checks are performed to update the list of unsatisfied parity checks in the middle of a local decoding iteration or at the end of the local decoding iteration. A determination is made as to whether the number of unsatisfied parity checks is less than a threshold. (Block <b>604</b>) If the number of unsatisfied parity checks is not less than the threshold, local decoding iterations can be continued in an attempt to reduce the number of unsatisfied parity checks. If the number of unsatisfied parity checks is less than the threshold, a targeted symbol flipping operation is initiated, thereby changing symbol values associated with unsatisfied parity check list and running local decoding iterations. (Block <b>606</b>) As a resulting codeword is generated, the hash value of the codeword is calculated. (Block <b>610</b>) The hash value can be calculated for an entire codeword in one operation, or can be calculated piecewise, for example by component codeword, with the resulting hashes either combined for the overall codeword or kept separate. A determination is made as to whether a previously stored codeword exists with the same hash value. (Block <b>612</b>) If so, the new codeword is a duplicate and is discarded. (Block <b>614</b>) If not, the new codeword is assumed to be unique and is stored. (Block <b>616</b>)

0041Although the targeted symbol flipping recovery of miscorrected codewords disclosed herein is not limited to any particular application, several examples of applications are presented in <figref idref="DRAWINGS">FIGS. 7 and 8</figref> that benefit from embodiments of the present invention. Turning to <figref idref="DRAWINGS">FIG. 7</figref>, a storage system <b>700</b> is illustrated as an example application of targeted symbol flipping recovery of miscorrected codewords in accordance with some embodiments of the present inventions. The storage system <b>700</b> includes a read channel circuit <b>702</b> with a decoder with targeted symbol flipping recovery of miscorrected codewords in accordance with some embodiments of the present invention. Storage system <b>700</b> may be, for example, a hard disk drive. Storage system <b>700</b> also includes a preamplifier <b>704</b>, an interface controller <b>706</b>, a hard disk controller <b>710</b>, a motor controller <b>712</b>, a spindle motor <b>714</b>, a disk platter <b>716</b>, and a read/write head assembly <b>720</b>. Interface controller <b>706</b> controls addressing and timing of data to/from disk platter <b>716</b>. The data on disk platter <b>716</b> consists of groups of magnetic signals that may be detected by read/write head assembly <b>720</b> when the assembly is properly positioned over disk platter <b>716</b>. In one embodiment, disk platter <b>716</b> includes magnetic signals recorded in accordance with either a longitudinal or a perpendicular recording scheme.

0042In a typical read operation, read/write head assembly <b>720</b> is accurately positioned by motor controller <b>712</b> over a desired data track on disk platter <b>716</b>. Motor controller <b>712</b> both positions read/write head assembly <b>720</b> in relation to disk platter <b>716</b> and drives spindle motor <b>714</b> by moving read/write head assembly <b>720</b> to the proper data track on disk platter <b>716</b> under the direction of hard disk controller <b>710</b>. Spindle motor <b>714</b> spins disk platter <b>716</b> at a determined spin rate (RPMs). Once read/write head assembly <b>720</b> is positioned adjacent the proper data track, magnetic signals representing data on disk platter <b>716</b> are sensed by read/write head assembly <b>720</b> as disk platter <b>716</b> is rotated by spindle motor <b>714</b>. The sensed magnetic signals are provided as a continuous, minute analog signal representative of the magnetic data on disk platter <b>716</b>. This minute analog signal is transferred from read/write head assembly <b>720</b> to read channel circuit <b>702</b> via preamplifier <b>704</b>. Preamplifier <b>704</b> is operable to amplify the minute analog signals accessed from disk platter <b>716</b>. In turn, read channel circuit <b>702</b> decodes and digitizes the received analog signal to recreate the information originally written to disk platter <b>716</b>. This data is provided as read data <b>722</b> to a receiving circuit. As part of decoding the received information, read channel circuit <b>702</b> applies targeted symbol flipping recovery of miscorrected codewords when decoding fails to converge normally. Such targeted symbol flipping recovery of miscorrected codewords can be implemented consistent with that disclosed above in relation to <figref idref="DRAWINGS">FIGS. 2-6</figref>. A write operation is substantially the opposite of the preceding read operation with write data <b>724</b> being provided to read channel circuit <b>702</b>. This data is then encoded and written to disk platter <b>716</b>.

0043It should be noted that storage system <b>700</b> may be integrated into a larger storage system such as, for example, a RAID (redundant array of inexpensive disks or redundant array of independent disks) based storage system. Such a RAID storage system increases stability and reliability through redundancy, combining multiple disks as a logical unit. Data may be spread across a number of disks included in the RAID storage system according to a variety of algorithms and accessed by an operating system as if it were a single disk. For example, data may be mirrored to multiple disks in the RAID storage system, or may be sliced and distributed across multiple disks in a number of techniques. If a small number of disks in the RAID storage system fail or become unavailable, error correction techniques may be used to recreate the missing data based on the remaining portions of the data from the other disks in the RAID storage system. The disks in the RAID storage system may be, but are not limited to, individual storage systems such storage system <b>700</b>, and may be located in close proximity to each other or distributed more widely for increased security. In a write operation, write data is provided to a controller, which stores the write data across the disks, for example by mirroring or by striping the write data. In a read operation, the controller retrieves the data from the disks. The controller then yields the resulting read data as if the RAID storage system were a single disk.

0044Turning to <figref idref="DRAWINGS">FIG. 8</figref>, a wireless communication system <b>800</b> or data transmission device including a receiver <b>804</b> with targeted symbol flipping recovery of miscorrected codewords is shown in accordance with some embodiments of the present inventions. Communication system <b>800</b> includes a transmitter <b>802</b> that is operable to transmit encoded information via a transfer medium <b>806</b> as is known in the art. The encoded data is received from transfer medium <b>806</b> by receiver <b>804</b>. Receiver <b>804</b> incorporates a decoder with targeted symbol flipping recovery of miscorrected codewords. Such targeted symbol flipping recovery of miscorrected codewords can be implemented consistent with that disclosed above in relation to <figref idref="DRAWINGS">FIGS. 2-6</figref>.

0045It should be noted that the various blocks discussed in the above application may be implemented in integrated circuits along with other functionality. Such integrated circuits may include all of the functions of a given block, system or circuit, or only a subset of the block, system or circuit. Further, elements of the blocks, systems or circuits may be implemented across multiple integrated circuits. Such integrated circuits may be any type of integrated circuit known in the art including, but are not limited to, a monolithic integrated circuit, a flip chip integrated circuit, a multichip module integrated circuit, and/or a mixed signal integrated circuit. It should also be noted that various functions of the blocks, systems or circuits discussed herein may be implemented in either software or firmware. In some such cases, the entire system, block or circuit may be implemented using its software or firmware equivalent. In other cases, the one part of a given system, block or circuit may be implemented in software or firmware, while other parts are implemented in hardware.

0046In conclusion, the present invention provides novel apparatuses and methods for low density parity check decoding with targeted symbol flipping recovery of miscorrected codewords. While detailed descriptions of one or more embodiments of the invention have been given above, various alternatives, modifications, and equivalents will be apparent to those skilled in the art without varying from the spirit of the invention. Therefore, the above description should not be taken as limiting the scope of the invention, which is defined by the appended claims.