# US 8,751,889 B2 · Systems and methods for multi-pass alternate decoding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,751,889 B2
- Document ID: US8751889B2
- Status: Granted
- Kind: B2
- Application number: 13/362,409
- Filed: 2012-01-31
- Published: 2013-08-01
- Granted: 2014-06-10
- Earliest claimed: 2012-01-31
- Assignees: LSI Corporation
- Applicants: Fan Zhang; Shaohua Yang
- Inventors: Fan Zhang; Shaohua Yang
- Web page: https://patentgrep.com/patent/US8751889B2

## CPC

- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/1128: {Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations}
- H03M 13/1142: {using trapping sets}
- H03M 13/2957: {Turbo codes and decoding}
- H03M 13/6331: {Error control coding in combination with equalisation}
- H03M 13/6561: {Parallelized implementations}
- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- H03M 13/41: using the Viterbi algorithm or Viterbi processors
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Various embodiments of the present invention provide systems and methods for data processing. For example, data decoding systems are disclosed that include a data decoder circuit and a decode value modification circuit.

## Claims

### Claim 1

A data decoding system, the data decoding system comprising:
a data decoder circuit operable to:
apply a data decode algorithm to a decoder input to yield a first decoded output and an indication of at least one point of failure of the first decoded output, and
apply the data decode algorithm to the decoder input guided by a first modified decode output to yield a second decoded output and an indication of at least one point of failure of the second decoded output,
a decode value modification circuit operable to:
identify a first symbol of the first decoded output associated with the point of failure of the first decoded output, and to modify a subset of values associated with the identified first symbol to yield the first modified decode output; and
identify a second symbol of the second decoded output associated with the point of failure of the second decoded output, and to modify a subset of values associated with the identified first symbol and the identified second symbol to yield the second modified decode output.

### Claim 2 (depends on 1)

The data decoding system of claim 1, wherein the data decoding system is implemented as part of a device selected from a group consisting of: a storage device, and a receiving device.

### Claim 3 (depends on 1)

The data decoding system of claim 1, wherein the data decoding system is implemented as part of an integrated circuit.

### Claim 4 (depends on 1)

The data decoding system of claim 1, wherein the data decode algorithm is a low density parity check algorithm, and wherein the point of failure of the first decoded output is a failure of a parity check equation implemented as part of the low density parity check algorithm.

### Claim 5 (depends on 4)

The data decoding system of claim 4, wherein the low density parity check algorithm is selected from a group consisting of: a non-binary low density parity check algorithm, and a binary low density parity check algorithm.

### Claim 6 (depends on 4)

The data decoding system of claim 4, wherein the low density parity check algorithm is implemented as a belief propagation data decode algorithm.

### Claim 7 (depends on 1)

The data decoding system of claim 1, wherein the decode value modification circuit includes a partial maximum likelihood decode algorithm to identify the first symbol and the second symbol.

### Claim 8 (depends on 7)

The data decoding system of claim 7, wherein the decode value modification circuit includes:
a syndrome calculation circuit operable to calculate a syndrome based upon a number of symbols associated with the point of failure of the first decoded output;
an array calculator circuit operable to calculate an array of possible hard decision values across the contributors to the point of failure of the first decoded output; and
an index identifier circuit operable to determine a candidate from the array as the identified symbol.

### Claim 9 (depends on 8)

The data decoding system of claim 8, wherein the decode value modification circuit includes further comprises:
a likely symbol value selector circuit operable to determine whether the subset of values associated with the identified symbol includes one log likelihood ratio value or two log likelihood ratio values.

### Claim 10 (depends on 1)

The data decoding system of claim 1, wherein the data decoder circuit further comprises:
a multi-pass controller circuit operable to selectively control generation of the first modified decode output and the second modified decode output.

### Claim 11 (depends on 10)

The data decoding system of claim 10, wherein the multi-pass controller circuit enables generation of the first modified decode output when:
a number of iterations of the data decoder circuit applying the data decode algorithm to the decoder input is greater than a first threshold value;
a number of points of failure corresponding to the first decoded output is less than a second threshold value; and
the number of points of failure corresponding to the first decoded output is the same as the number of points of failure corresponding to a previous decoded output.

### Claim 12 (depends on 1)

The data decoding system of claim 1, wherein the data decoder circuit is further operable to apply the data decode algorithm to the decoder input guided by a second modified decode output to yield a third decoded output.

### Claim 13 (depends on 1)

The data decoding system of claim 1, wherein the applying the data decode algorithm to the decoder input guided by the second modified decode output further yields an indication of at least one point of failure of the third decoded output.

### Claim 14

A method for data decoding, the method comprising:
applying a data decode algorithm by a data decoder circuit to a decoder input to yield a first decoded output and an indication of at least one point of failure of the first decoded output;
identifying at least a first symbol and a second symbol associated with the point of failure of the first decoded output;
modifying at least one of the first symbol and the second symbol to yield a first modification;
modifying the first decoded output to incorporate the first modification to yield a first modified decode output;
applying the data decode algorithm to the decoder input guided by the first modified decode output to yield a second decoded output;
identifying at least a third symbol and a fourth symbol associated with the point of failure of the second decoded output;
modifying at least one of the third symbol and the fourth symbol to yield a second modification; and
modifying the second decoded output to incorporate the first modification and the second modification to yield a second modified decode output.

### Claim 15 (depends on 14)

The method of claim 14, wherein the method further comprises:
applying the data decode algorithm to the decoder input guided by the first modified decode output to yield a third decoded output.

### Claim 16 (depends on 14)

The method of claim 14, wherein modifying at least one of the first symbol and the second symbol to yield the first modification comprises:
calculating a syndrome including the first symbol and the second symbol;
calculating an array of possible hard decision values across the contributors to the point of failure of the first decoded output;
determining an index corresponding to a candidate from the array as an identified symbol;
determining a subset values associated with the identified symbol to be modified;
modifying the subset of values to yield a modified decoded output; and
applying the data decode algorithm by the data decoder circuit to the decoder input guided by the modified decoded output to yield a second decoded output.

### Claim 17 (depends on 16)

The method of claim 16, wherein calculating the syndrome is done in accordance with the following equation:
s
=
∑
i
=
0
M
⁢
v
i
×
e
i
,
wherein vi corresponds to hard decision values of variable nodes corresponding to the point of failure of a check node, M is the number of variable nodes corresponding to the check node, and ei corresponds to edge values connecting the variable nodes to the check node.

### Claim 18 (depends on 17)

The method of claim 17, wherein calculating the array of possible hard decision values across the contributors to the point of failure is done in accordance with the following equation:
Arrayi,j=(j×ei−1)−HDi, for iε{1,2, . . . M},jε{1,2,3},
wherein j represents the contribution from the calculated syndrome, HDi represents the most likely symbol for a particular instance i, and ei−1 corresponds to an inverse edge value for the particular instance i.

### Claim 19 (depends on 18)

The method of claim 18, wherein determining the index is done in accordance with the following equation:
indexj=arg mini(LLRHDiXOR Arrayi,j),
wherein, jε{1, 2, 3}, and wherein LLR is a log likelihood ratio of the most likely symbol.

### Claim 20 (depends on 14)

The method of claim 14, wherein modifying at least one of the third symbol and the fourth symbol to yield the first modification comprises:
calculating a syndrome including the third symbol and the fourth symbol;
calculating an array of possible hard decision values across the contributors to the point of failure of the second decoded output;
determining an index corresponding to a candidate from the array as an identified symbol;
determining a subset values associated with the identified symbol to be modified;
modifying the subset of values to yield a modified decoded output; and
applying the data decode algorithm by the data decoder circuit to the decoder input guided by the modified decoded output to yield a second decoded output.

### Claim 21

A storage device, the storage device comprising:
a storage medium;
a head assembly disposed in relation to the storage medium and operable to provide a sensed signal corresponding to information on the storage medium;
a read channel circuit including:
an analog to digital converter circuit operable to sample an analog signal derived from the sensed signal to yield a series of digital samples;
an equalizer circuit operable to equalize the digital samples to yield a data set;
a data detector circuit operable to apply a data detection algorithm to the data set to yield a detected output; and
a data decoding system including:
a data decoder circuit operable to: apply a data decode algorithm to a decoder input to yield a first decoded output and an indication of at least one point of failure of the first decoded output, apply the data decode algorithm to the decoder input guided by a first modified decode output to yield a second decoded output and an indication of at least one point of failure of the second decoded output, and apply the data decode algorithm to the decoder input guided by a second modified decode output to yield a third decoded output and an indication of at least one point of failure of the third decoded output;
a decode value modification circuit operable to:
identify a first symbol of the first decoded output associated with the point of failure of the first decoded output, and to modify a subset of values associated with the identified first symbol to yield the first modified decode output; and
identify a second symbol of the second decoded output associated with the point of failure of the second decoded output, and to modify a subset of values associated with the identified first symbol and the identified second symbol to yield the second modified decode output.

### Claim 22 (depends on 21)

The storage device of claim 21, wherein the decode value modification circuit includes a partial maximum likelihood decode algorithm to identify the first symbol and the second symbol; and wherein the decode value modification circuit includes:
a syndrome calculation circuit operable to calculate a syndrome based upon a number of symbols associated with the point of failure of the first decoded output;
an array calculator circuit operable to calculate an array of possible hard decision values across the contributors to the point of failure of the first decoded output; and
an index identifier circuit operable to determine a candidate from the array as the identified symbol.