Source: https://patents.google.com/patent/US8516332B1/en
Timestamp: 2019-12-06 07:45:13
Document Index: 652107221

Matched Legal Cases: ['art.\n1', 'art 11', 'art 11', 'art 11', 'art 11', 'art 11', 'art 11']

US8516332B1 - Methods and algorithms for joint channel-code decoding of linear block codes - Google Patents
Methods and algorithms for joint channel-code decoding of linear block codes Download PDF
US8516332B1
US8516332B1 US13/608,390 US201213608390A US8516332B1 US 8516332 B1 US8516332 B1 US 8516332B1 US 201213608390 A US201213608390 A US 201213608390A US 8516332 B1 US8516332 B1 US 8516332B1
US13/608,390
2005-06-23 Priority to US11/166,548 priority Critical patent/US7571372B1/en
2009-07-06 Priority to US12/498,320 priority patent/US8291290B1/en
2012-09-10 Application filed by Marvell International Ltd filed Critical Marvell International Ltd
2012-09-10 Priority to US13/608,390 priority patent/US8516332B1/en
2013-08-20 Publication of US8516332B1 publication Critical patent/US8516332B1/en
201000010874 syndrome Diseases 0 abstract description 15
102100019523 PLIN5 Human genes 0 description 1
101700046681 PLIN5 family Proteins 0 description 1
Circuits, architectures, methods and algorithms for joint channel-code decoding of linear block codes, and more particularly, for identifying and correcting one or more errors in a code word and/or for encoding CRC (or parity) information. In one aspect, the invention focuses on use of (i) remainders, syndromes or other polynomials and (ii) Gaussian elimination to determine and correct errors. Although this approach may be suboptimal, the present error checking and/or detection scheme involves simpler computations and/or manipulations than conventional schemes, and is generally easier to implement logically. Since the complexity of parity-based error correction schemes increases disproportionately to the number of potential error events, the present invention meets a long-felt need for a scheme to manage error detection and/or correction in systems (such as magnetic recording applications) where there may be a relatively large number of likely error events, thereby advantageously improving reliability and/or performance in channel communications.
This application is a continuation of U.S. patent application Ser. No. 12/498,320, filed Jul. 6, 2009 (currently pending), which is a divisional of U.S. patent application Ser. No. 11/166,548, filed Jun. 23, 2005, now U.S. Pat. No. 7,571,372, each of which is hereby incorporated by reference herein in its entirety.
The present invention relates generally to joint channel-code detectors. More particularly, the present invention relates to the design and (hardware) implementation of joint channel-code detectors for linear block codes. Although the discussion of the present invention herein below shall primarily refer to applications to magnetic recording channels, the approaches discussed herein can easily be adapted to many other communication channels.
For some linear block codes, one may design a joint Maximum Likelihood (ML) channel-code detector. However, these detectors tend to be very complicated, even for relatively simple (and ultimately weak) codes. In some special cases, one may obtain reasonable performance by completely separating the channel detector 12 from the code decoder 14, as shown in the system 10 in FIG. 1.
FIG. 3 shows an exemplary decoder 30 for a magnetic recording system, matched to the encoder system 20 in FIG. 2. Decoder 30 generally includes a Viterbi detector 32, a post processor 34, and a RS ECC decoder 36. In the decoder architecture 30 of FIG. 3, the inner CRC code is decoded with Post Processor circuit (“PP detector”) 34. PP detector 34 assumes the presence of a primary channel detector (e.g., Viterbi detector 32). Thereafter, two further simplifying assumptions are typically made to enable PP-based implementations.
In CRC code theory, it is helpful to represent CRC code words as polynomials over some finite field, F. With each codeword c=(c0, c1, . . . . , cn-1) (i.e., a string of symbols from field F), we can associate a polynomial c(x) over F of degree less than n, given by
c ⁡ ( x ) = ∑ i = 0 n - 1 ⁢ c i ⁢ x i .
Equivalently, every polynomial over field F of degree less than n can be represented as a string of n symbols, where the ith symbol coincides with the coefficient of xi, i=0, 1, . . . , n−1. CRC code may be specified in terms of a generator polynomial g(x). The codeword c(x) is said to belong to the codeword space of the CRC(n,k) code defined by the generating polynomial g(x) if and only if g(x) divides c(x) without a remainder (i.e., Rem(c(x),g(x))=0, where 0 stands for a zero polynomial). The invention will be explained often herein with reference to binary CRC codes (i.e., where F=GF(2)); however, it should be apparent to those skilled in art that the inventive concepts described herein can be easily applied to or extended to codes over higher order fields. It is also convenient to represent members of E in polynomial notation as well, e.g. E={1, 1+x, 1+x+x2, 1+x2, 1+x+x2+x3, 1+x+x2+x3+x4}.
MLDP ⁡ ( e ) = ∑ i = 1 k ⁢ MLDP ⁡ ( e i ) ,
where MLDP(ei) is the composite penalty of the individual component error events, i=1, 2, . . . , k. If the component error events overlap, or if the number of bits between two component error events (from the end of one to the beginning of the next) is less than channel memory, the above formula does not apply. Consequently, MLDP for overlapped error events are difficult to calculate. Therefore, even if such error events are selected by a PP algorithm, they should be disabled in the correction block if their MLDP can not be accurately calculated.
Once the penalties corresponding to various error events have been computed, PP 34 searches for an alternative path corresponding to a combination of at most M error events that (1) bring v(x) into the codeword space of the inner ECC and (2) has smallest MLDP among all such paths. Herein, the term “v(x)” is used to denote the plurality of Viterbi decisions, as well as a subset of these decisions corresponding to a particular CRC codeword. Where applicable, the context of any given use of “v(x)” herein may impart a particular meaning to those skilled in the art.
1. Compute the remainder r(x)=Rem(v(x), g(x)). If r(x)=0, then the Viterbi decoder has output either a codeword with no errors or a codeword that cannot be corrected using PP 34; otherwise go to step 2.
2. Form a set of alternative paths P, where each path p in P corresponds to some dominant error event e(x) in E, i.e. p(x)=v(x)+e(x). For each such path, compute MLDP(e) and Rem(e(x), g(x)).
3. Extend the collection P by possibly adding paths corresponding to composite error events, whose MLDP and remainders can be computed based on similar quantities for individual components of e(x).
4. Search for the path p(x) in P corresponding to an error event or a combination of error events satisfying:
a. Rem(p(x), g(x))=0; and
b. Among the p(x) satisfying 4(a), choose the one with the smallest MLDP:
p = min p ′ ∈ P ⁢ ( MLDP ⁡ ( p ′ ) ) .
5. If step 4 produces a non-trivial candidate p(x), then correct the codeword using candidate p(x); otherwise decoder failure is declared.
( 10 1 ) + ( 10 2 ) + ( 10 3 ) + ( 10 4 ) = 394.
In the past, the choice of CRC codes which can be implemented in practice were limited to codes having relatively small block length n (generally, under 120 bits), due to the complexity of having to search through a large number of paths. As n grows, the parameter M also generally increases, since the probability of having multiple error events in a single CRC codeword increases with codeword size. However, as previously discussed, the complexity of a PP-based architecture is ultimately related to the choice of parameter M. On the other hand, short CRC codes are not optimal either due to (i) the relatively low error detection and correction capability of these codes and/or (ii) the high code rate penalty they inflict on the communication system.
FIG. 5 shows a conventional process 50 for checking and correcting errors in data blocks transmitted over a channel using CRC code. First, a code word or code block is received in step 52. The channel typically introduces some noise into the transmitted code, and as a result, the received code word or block may be considered “noisy.” Thereafter, in step 54, the received code words are decoded, then in step 56, the received code word is divided by a generator polynomial g(x) to determine the remainder r(x)=Rem(v(x),g(x)) (g(x) is generally known to the receiver as well as the transmitter, and does not change from codeword to codeword or sector to sector). Step 56 is essentially the error checking part of the process 50. A processing decision is made in step 60, depending on whether a zero remainder is obtained form the code word division step 56. If a zero remainder is obtained, then one may conclude that there is no error in the transmitted code word in result 62, and the decoded code word obtained in step 54 may be output.
Embodiments of the present invention relate to circuitry, architectures, systems, methods, algorithms and software for joint channel-code detectors, particularly for linear block codes. In one aspect, the present invention relates to a post processor, comprising (a) a list generator and (b) search logic. The list generator is generally configured to (1) generate a list of most likely error events for a data block and (2) compute an error event remainder for each of the most likely error events. The search logic is generally configured to determine a number of error correction solutions for the data block from (i) the most likely error event remainders and (ii) a remainder for the data block.
The present invention focuses on the joint channel-code decoding of inner CRC, generally implemented in a post processor or circuit including a post processor. Thus, the present invention concerns, in one important aspect, a detector implementation for performing steps 3 and 4 of the five steps listed above as applying to each received CRC codeword, described with reference to a PP decoding architecture. The outer RS ECC decoder may be separated from inner CRC decoding circuitry, as discussed above. The new architecture facilitates PP implementation for codes with large block length and allows parameter N to be set as high as deg(g(x)). For instance, the present PP design can easily support (1023, 1012) CRC codes with g(x)=1+x+x7+x8+0+x10+x11, where n=deg(g(x))=11, or (4096+43, 4096) code where n=deg(g(x))=43.
FIG. 1 is a block diagram showing a conventional data receiving system, in which the channel detector is separated from the code detector.
Furthermore, for the sake of convenience and simplicity, the terms “clock,” “time,” “rate,” “period” and “frequency” are generally used interchangeably herein, but are generally given their art-recognized meanings. Also, for convenience and simplicity, the terms “data,” “data stream,” “waveform” and “information” may be used interchangeably, as may the terms “connected to,” “coupled with,” “coupled to,” and “in communication with” (which terms also refer to direct and/or indirect relationships between the connected, coupled and/or communication elements unless the context of the term's use unambiguously indicates otherwise), but these terms are also generally given their art-recognized meanings. More specifically, however, the terms “finite impulse response filter,” “FIR filter” and “equalizer” generally have the same meaning (as explained in greater detail below).
Although this application primarily describes and discusses CRC codes, all of the inventive concepts disclosed herein can be readily applied to a wider class of block linear codes. Linear block (n,k) codes over the finite field F can be defined in terms of a k-by-n generator matrix G or an (n−k)-by-n parity check matrix H (both matrices are over the field F). The codeword space then includes all of the n-tuples c in Fn satisfying HcT=0. If v is a received codeword, then one can compute a syndrome s=HvT. Clearly v is in the codeword space if and only ifs equals a zero vector. In most respects, syndromes for linear block codes are equivalent to remainders for CRC (of course, the latter has more structure). It turns out that the properties of remainders which are used by PP architectures also hold true for syndromes. Therefore, to extend a PP architecture to linear block code, one simply replaces remainder computations and manipulations with those of syndrome vectors. For example, H(v+e1+e2+ . . . +ek)T=HvT+He1 T+He2 T+ . . . +Hek T, similar to the principle of linearity of remainders. Thus, the present invention further relates to a circuit, comprising (a) a list generator configured to (i) generate a list of most likely error events for a binary data block and (ii) compute an error event syndrome for each of said most likely error events; and (b) search logic configured to determine a number of error correction solutions for the binary data block from (i) the error event syndromes and (ii) a syndrome for the binary data block. As discussed herein, any other aspect of the present invention that relates to CRC code and/or remainders that can apply to binary block codes and/or syndromes is applicable to the circuit in the preceding sentence.
Referring now to FIG. 6, CRC(n,k) encoder 106 partitions the incoming bit stream into the blocks of length k, and encodes each k-bit word into an n-bit codeword. Each k-bit CRC word may be denoted by w(x), and each n-bit CRC codeword by c(x). Then, a systematic encoder forms a codeword c, as c(x)=w(x) xd+r(x), where d=(n−k) and is the degree of generator polynomial g(x), and r(x)=Rem(w(x) xd, g(x)). The implementation of the systematic encoder may merely include or consist of polynomial division logic to compute r(x). Once the remainder is computed, it is augmented at (or concatenated with) the end of the CRC word to form the CRC codeword, c(x). FIG. 4 shows exemplary remainder logic 40, which is a conventional long division circuit.
Unlike RS ECC redundancy (which is usually on the order of 400 bits), CRC redundancy per codeword is somewhat short, anywhere from couple of bits to about 10-20 bits. For this reason, it is not always feasible to encode CRC redundancy using a special RLL code. Instead, the CRC encoder 106 may be configured in such a way as to preserve the existing RLL constraints) to as great an extent as is possible. Of course, during the encoding process, RLL constraints can be a “slightly degraded” (e.g., in the case of a constraint requiring at least one transition every six bits, transmission of a codeword having one or two instances of at most six consecutive bits without a transition may not always fail). However, it is paramount to avoid total breakdown of an RLL constraint near a parity insertion region.
The preferential positions for parity insertion are dictated by the particular nature of the RLL constraint(s) existing in the data going into CRC encoder 106. Exemplary RLL codes include (d,k) and (0, G/I) codes. For (d,k) RLL code, parameter d is a constraint on the number of zero bits that must follow a bit having a digital value of one (a so-called “one” bit), and k is a constraint on the maximum number of consecutive bits having the same digital value (so-called “same state” bits). (0, G/I) code guarantees at most G consecutive bits having the same digital value, and at most I consecutive bits having the same digital value in each of the odd/even interleaves.
To avoid or minimize breakdown of the G and I constraints, odd and even interleaves may be switched between successive (e.g., every other pair of) parity bits. Referring to FIG. 7, if CRC parity bit 215 is the first such parity bit inserted into first code word 210, then even/odd interleaves are swapped between parity bits 215 and 216 (in subblock or region 212), but not between parity bits 216 and 217 (in subblock or region 213). Naturally, the even and odd interleaves in first subblock 211 are not switched, either. Thus, if region 212 is originally given by the sequence ‘0101010101’, then after swapping odd/even interleaves, it becomes ‘1010101010’.
It thus becomes necessary to develop an encoder that inserts parity at predetermined locations. First, let {l1, l2, . . . ln-k} be a set of predetermined parity locations. An object of the present (systematic) CRC encoder is to configure the RLL encoded data with parity positions corresponding to those specified in the list of predetermined parity locations. FIG. 8 shows an exemplary CRC encoder 250, including placeholder logic 260, memory 270, multiplexer 280, remainder logic 292 and parity logic 294.
First, the input word w(x) is paced through, or input into, parity placeholder logic 260, which outputs pseudo-codeword c′(x) obtained from w(x) by inserting a zero (0) bit into every parity location specified by the list (e.g., {l1, l2, . . . ln-k}). Code word remainders r(x) are computed in remainder logic 292 according to the equation:
q=rG −1 [3]
In other embodiments, the search logic may be further configured to combine the most likely error events, or the most likely error event remainders, to determine the error correction solutions. Thus, the means for determining error correction solutions may further comprise a means for combining the most likely error events or the most likely error event remainders. In another variation, the present post processor may further comprise matrix processing logic configured to form a matrix from one or more of the error event remainders. As described elsewhere herein, incidence vectors generally comprise a plurality of the most likely error events (a so-called “composite error”); thus, remainders of a combination of most likely error events (or remainders corresponding to a composite error) are generally included within the meaning of “error event remainders.” In one implementation, the post processor further comprises matrix augmenting logic configured to augment the matrix with a data block remainder (i.e., a remainder calculated from the data block itself). In this latter implementation, the post processor may also further comprise computing logic configured to compute the data block remainder from the data block. Thus, the present post processor may further comprise (i) a means for forming a matrix from one or more of the most likely error event remainders, and/or (ii) a means for augmenting the matrix with a data block remainder, in which case the post processor may further include a means for computing the data block remainder from the data block. As will be apparent from the following description of the exemplary post processor architecture, the search logic may comprise a matrix inverter and/or row reducing logic configured to reduce the matrix to row echelon form. Thus, the means for determining error correction solutions may comprise a means for inverting the matrix and/or a means for reducing the matrix to row echelon form.
1. Compute the remainder r(x)=Rem(v(x), g(x)). If r(x)=0, then the Viterbi decoder has output either a codeword with no errors or a codeword that cannot be corrected using the PP block. If r(x)≠0, go to step 2.
2. Form a set of alternative paths P, where each path p in P corresponds to some dominant error event e(x) in E. For each such path, compute MLDP(e) and Rem(e(x), g(x)).
3. Limit the collection P to the N most likely error events (e.g., the error events having smallest MLDP).
4. Optionally, extend the collection P by adding paths corresponding to composite error events, whose MLDP and remainders can be computed based on similar quantities for individual components of e(x).
5. Search for the path p(x) in P corresponding to an error event or a combination of error events satisfying:
b. Among the p(x) satisfying 5(a), choose the one with the smallest MLDP:
6. If step 5 produces a non-trivial candidate p(x), then correct the codeword using (best) candidate p(x); otherwise, decoder failure is declared.
The second stage periodically (e.g. every 4 cycles) selects the most likely error event from the local list (i.e., choose one event in the right most column, namely the one with the smallest MLDP; this is sometimes known as a “choose 1 out of N” operation) and sends it for possible insertion into global list 356. In the context of the present hardware for error detection and/or correction, the term “global list” is generally synonymous with LMLE. Global list 356 comprises an array or plurality of memory elements (generally located in list search logic 336; see FIG. 9) similar to those used for local list 352, but generally larger than local list 352. To facilitate insertion of the updated most likely error events into global list 356, the LMLE events may be arranged (and maintained) as a square matrix. In one embodiment, the matrix is a 6×6 square. Similar to the above description, LMLE is always ordered in ascending order by MLDP, where the information is written into a matrix form, generally column-by-column.
Referring back to FIG. 10, the penalty associated with an error event selected from local list 352 is then compared against the penalties associated with error events in the first row 338 of global list 356. Assuming the updated LMLE events is in the form of an m-by-m matrix, this “m choose 1” operation determines the column in global list 356 in which the error event is to be inserted. Once the column is known, the penalty associated with an updated error event is compared against all error events in that column. This “m choose 1” operation determines the row in global list 356 in which the error event is to be stored. In one implementation, the error event in local list 352 is stored in global list 356 when its associated penalty is less than one or more of the penalties associated with the error events already stored in global list 356.
e ⁡ ( x ) = ∑ k = 0 ⁢ e k ⁢ x l + k [ 4 ]
Then, by linearity:
Re ⁢ ⁢ m ⁡ ( e ⁡ ( x ) , g ⁡ ( x ) ) = ∑ k = 0 ⁢ e k ⁢ Re ⁢ m ⁡ ( x k + l , g ⁡ ( x ) ) [ 5 ]
Rem(xk,g(x)) can be either (i) pre-computed and stored for all values of k=0, 1, . . . , n−1, using essentially the same divider circuit as is shown in FIG. 4, or (ii) recursively obtained from Rem(xk−1,g(x)) by applying a conventional cyclic shift operation (e.g., a right shift) using the circuit 400 shown in FIG. 12, which is generally configured to determine the remainder for a shifted pseudo code word from the non-shifted pseudo code word remainder.
For purposes related to an explanation of this exemplary aspect of the invention, we will assume that r(x) is not equal to a zero polynomial. Otherwise, either the received codeword v(x) has no errors, or the error(s) in received codeword v(x) cannot be corrected using this approach. Also, for purposes related to an explanation of this exemplary aspect of the invention, we will assume that the LMLE list generated by list generator 334 may be represented by L={e1, e2, . . . , eN}.
The exemplary list search logic 336 may implement algorithm 500 as shown in FIG. 13. In a first step 510, a binary N×N matrix R whose columns are given by (or equal to) Rem(ek(x),g(x)), where k=1, 2, . . . , N, may be formed. In a second step 520, an N×1 binary vector a (a so-called “incidence vector”) may be defined for a combination of error events. Each combination of at most N error events can be identified by its own incidence vector α. For example, the error event combination consisting of error events el and e2 from the LMLE may have the incidence vector α=(1, 1, 0, 0, 0, . . . , 0).
Then, mathematically, beginning in step 530, the search for all possible combinations of error events that bring received codeword v(x) into the codeword space can be restated as simply identifying a solution set to a N×N system of linear equations Rα=r, with N unknowns (more particularly, the coefficients of incidence vector[s] α). For example, a Gaussian elimination technique can be performed in step 530 to obtain the set of all possible solutions. In one implementation, an augmented matrix A=[R|r] is formed and row reduced to a row echelon form to identify the solution set of error events and/or error event combinations that bring received codeword v(x) into the codeword space.
Application of the Search Algorithm Simple Example #1
[ 1 1 0 1 1 1 0 0 1 ]
Then the augmented matrix is:
[ 1 1 0 1 1 1 1 0 0 0 1 0 ]
Row reduction to solve Rα=r gives:
[ 1 1 0 1 1 1 1 0 0 0 1 0 ] → [ 1 1 0 1 0 0 1 1 0 0 1 0 ] → [ 1 1 0 1 0 0 1 1 0 0 0 1 ]
The left portion (i.e., the first three columns) of the last row is all zeros, but the right portion (i.e., the position in the augmented column of the last row) is one. Therefore, there are no solutions.
Application of the Search Algorithm Simple Example #2
Let r(x)=(1,0,0) and L={e1, e2, e3} be the LMLE event list generated by list generator 352. Let R be given by the following matrix:
[ 1 1 0 1 1 1 0 1 1 ]
[ 1 1 0 1 1 1 1 0 0 1 1 0 ]
[ 1 1 0 1 1 1 1 0 0 1 1 0 ] → [ 1 1 0 1 0 0 1 1 0 1 1 0 ] → [ 1 1 0 1 0 1 1 0 0 0 1 1 ] → [ 1 0 1 1 0 1 1 0 0 0 1 1 ] → [ 1 0 0 0 0 1 0 1 0 0 1 1 ]
The left portion of the matrix is the identity matrix. As a result, there is a unique solution defined by the right portion (i.e., the last column) of the matrix, (0,1,1).
Application of the Search Algorithm Simple Example #3
[ 1 1 0 0 1 1 1 0 1 ]
[ 1 1 0 1 0 1 1 1 1 0 1 0 ]
[ 1 1 0 1 0 1 1 1 1 0 1 0 ] → [ 1 1 0 1 0 1 1 1 0 1 1 1 ] → [ 1 0 1 0 0 1 1 1 0 0 0 0 ]
The reduced matrix has an “all zeros” row (the last row). As a result, α3 is a free variable, and there is one solution, defined in part by the right portion of the matrix, for each value of the free variable. Therefore, when α3=0, the solution is (0,1,0), and when α3=1, the solution is (1,0,1).
Thus, the present invention provides circuits, architectures, systems, methods and algorithms for joint channel-code detectors, particularly for linear block codes, and more specifically for encoding CRC (or parity) information and/or for identifying, detecting and/or correcting one or more errors in a data block or code word. In one important aspect, the invention focuses on use of syndromes or remainders to determine errors in code words. Although suboptimal, the present error detection scheme based on syndromes or remainders involves simpler computations and/or manipulations, and is generally logically easier to implement, than previous “brute-force” methods involving trying all 2^N combinations of N most likely error events. Thus, the present invention meets a long-felt need for a scheme to manage error detection and/or correction in systems (such as magnetic recording applications) where there may be a relatively large list of most likely and/or likely errors.
insert dummy linear parity information segments at or between a plurality of positions in a data block; and
output a dummy-padded data block;
encoding circuitry configured to compute actual linear parity information for the data block; and
control circuitry configured to substitute portions of the actual linear parity information for the dummy linear parity information segments in the dummy-padded data block.
2. The circuit of claim 1, wherein the encoding circuitry comprises:
remainder logic configured to compute a remainder for the dummy-padded data block; and
parity computing logic configured to provide the actual linear parity information portions to the control circuitry.
3. The circuit of claim 1, further comprising a buffer configured to receive the dummy-padded data block and provide the dummy-padded data block to the control circuitry.
4. The circuit of claim 1, wherein the control circuitry comprises a multiplexer.
5. The circuit of claim 1, wherein the linear parity information comprises CRC information.
6. The circuit of claim 1 further comprising a channel encoder configured to generate the data block.
7. The circuit of claim 6, wherein the channel encoder comprises a run length limited (RLL) encoder, wherein the run length limited (RLL) encoder is configured to encode data according to a plurality of coding constraints.
8. A method of encoding linear parity information for a data block, the method comprising:
inserting dummy linear parity information segments at or between a plurality of predetermined positions in the data block to generate a dummy-padded data block;
computing actual linear parity information for the data block; and
substituting corresponding segments of the actual linear parity information for the dummy linear parity information in the plurality of predetermined positions in the dummy-padded data block to generate a linear parity encoded data block.
9. The method of claim 8, wherein the linear parity information comprises a remainder generated by dividing the data block by a generator polynomial.
10. The method of claim 8, wherein the data block comprises a run length limited (RLL) code.
11. A non-transitory computer program containing a set of instructions which, when executed by a processing device configured to execute computer-readable instructions, is configured to perform the method of claim 8.
12. The method of claim 8, wherein the linear parity information comprises CRC information.
13. The method of claim 8, wherein computing the actual linear parity information comprises computing a remainder for the dummy-padded data block.
14. The method of claim 13, wherein the actual linear parity information consists of the remainder, and segments of the remainder have a length equal to the dummy linear parity information segments.
US13/608,390 2005-06-23 2012-09-10 Methods and algorithms for joint channel-code decoding of linear block codes Active US8516332B1 (en)
US11/166,548 US7571372B1 (en) 2005-06-23 2005-06-23 Methods and algorithms for joint channel-code decoding of linear block codes
US12/498,320 US8291290B1 (en) 2005-06-23 2009-07-06 Methods and algorithms for joint channel-code decoding of linear block codes
US13/608,390 US8516332B1 (en) 2005-06-23 2012-09-10 Methods and algorithms for joint channel-code decoding of linear block codes
US12/498,320 Continuation US8291290B1 (en) 2005-06-23 2009-07-06 Methods and algorithms for joint channel-code decoding of linear block codes
US8516332B1 true US8516332B1 (en) 2013-08-20
ID=40910265
US11/166,548 Active 2028-06-02 US7571372B1 (en) 2005-06-23 2005-06-23 Methods and algorithms for joint channel-code decoding of linear block codes
US12/498,320 Active 2026-06-03 US8291290B1 (en) 2005-06-23 2009-07-06 Methods and algorithms for joint channel-code decoding of linear block codes
US13/608,390 Active US8516332B1 (en) 2005-06-23 2012-09-10 Methods and algorithms for joint channel-code decoding of linear block codes
US (3) US7571372B1 (en)
US20170201346A1 (en) * 2013-03-15 2017-07-13 Quanta Computer, Inc. Error-correcting code
US8321771B1 (en) 2008-10-13 2012-11-27 Marvell International Ltd. Modified trace-back using soft output viterbi algorithm (SOVA)
US20160269046A1 (en) * 2015-03-10 2016-09-15 Kabushiki Kaisha Toshiba Memory controller, memory system, and decoding method
US9996412B2 (en) 2015-06-16 2018-06-12 SK Hynix Inc. Enhanced chip-kill schemes by using sub-trunk CRC
US9899104B2 (en) * 2016-03-18 2018-02-20 Silicon Motion Inc. Raid decoding architecture with reduced bandwidth
US4916702A (en) 1988-06-17 1990-04-10 Cyclotomics, Inc. Elongated burst trapping
US5471486A (en) 1992-08-21 1995-11-28 U.S. Philips Corporation Methods and devices for encoding data symbols in accordance with a BCH code to obtain a code word in which parity symbols are located in the middle of the code word
US5802078A (en) 1992-11-27 1998-09-01 Kokusai Electric Co., Ltd. Error detector for error detecting codes
US6456208B1 (en) 2000-06-30 2002-09-24 Marvell International, Ltd. Technique to construct 32/33 and other RLL codes
US6823487B1 (en) 2001-11-15 2004-11-23 Lsi Logic Corporation Method and apparatus for enhancing correction power of reverse order error correction codes
US20050160351A1 (en) 2003-12-26 2005-07-21 Ko Young J. Method of forming parity check matrix for parallel concatenated LDPC code
US6981201B2 (en) 2001-10-03 2005-12-27 Stmicroelectronics S.R.L. Process for decoding signals and system and computer program product therefore
US20060026486A1 (en) 2004-08-02 2006-02-02 Tom Richardson Memory efficient LDPC decoding methods and apparatus
US20060107193A1 (en) 2004-10-12 2006-05-18 Samsung Electronics Co., Ltd. Method and apparatus for efficiently decoding low density parity check code
US20060156169A1 (en) 2005-01-10 2006-07-13 Ba-Zhong Shen LDPC (Low Density Parity Check) coding and interleaving implemented in MIMO communication systems
US20060156163A1 (en) 2004-12-03 2006-07-13 Stmicroelectronics N.V. Method and device for decoding packets of data within a hybrid ARQ scheme
US7765458B1 (en) 2005-09-29 2010-07-27 Marvell International Ltd. Error pattern generation for trellis-based detection and/or decoding
2005-06-23 US US11/166,548 patent/US7571372B1/en active Active
2009-07-06 US US12/498,320 patent/US8291290B1/en active Active
2012-09-10 US US13/608,390 patent/US8516332B1/en active Active
US7590920B2 (en) 2005-08-05 2009-09-15 Hitachi Global Storage Technologies Netherlands, B.V. Reduced complexity error correction encoding techniques
Chaichanavong, P. et al., "Tensor-Product Parity Code for Magnetic Recording"; IEEE Transactions on Magnetics, vol. 42, No. 2, pp. 350-352, Feb. 2006.
Cideciyan, R. et al., "Noise Predictive Maximum Likelihood Detection Combined with Parity-Based Post-Processing"; IEEE Transactions on Magnetics, vol. 37, No. 2, pp. 714-720, Mar. 2001.
Conway, T., "A New Target Response with Parity Coding for High Density Magnetic Recording Channels"; IEEE Transactions on Magnetics, vol. 34, No. 4, pp. 2382-2386, Jul. 1998.
Fan, J.L. et al., "A Modified Concatenated Coding Scheme, with Applications to Magnetic Data Storage"; IEEE Transactions on Information Theory, vol. 44, No. 4, pp. 1565-1574, Jul. 1998.
Feng, W. et al., "On the Performance of Parity Codes in Magnetic Recording Systems"; pp. 1877-1881, 2000 IEEE.
IEEE P802.11g/D8.2, Apr. 2003 (Supplement to ANSI/IEEE Std 802.11-1999(Reaff.2003)); Draft Supplement to Standard [for] Information Technology-Telecommunications and information exchange between systems-Local and metropolitan area networks-Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Further Higher Data Rate Extension in the 2.4 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 69 pages.
IEEE P802.11g/D8.2, Apr. 2003 (Supplement to ANSI/IEEE Std 802.11-1999(Reaff.2003)); Draft Supplement to Standard [for] Information Technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Further Higher Data Rate Extension in the 2.4 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 69 pages.
IEEE Std 802.11g/D2.8, May 2002 (Supplement to ANSI/IEEE Std 802.11, 1999 Edition) Draft Supplement to Standard [for] Information Technology-Telecommunications and information exchange between systems-Local and metropolitan area networks-Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Further Higher-Speed Physical Layer Extension in the 2.4 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 47 pages.
IEEE Std 802.11g/D2.8, May 2002 (Supplement to ANSI/IEEE Std 802.11, 1999 Edition) Draft Supplement to Standard [for] Information Technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Further Higher-Speed Physical Layer Extension in the 2.4 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 47 pages.
IEEE Std 802.11h-2003 (Amendment to IEEE Std 802.11, 1999 Edition (Reaff 2003)); as amended by IEEE Stds 802.11a-1999, 802.11b-1999, 802.11b-1999/Cor 1-2001, 802.11d2001, and 802.11g-2003; IEEE Standard for Information technology-Telecommunications and information exchange between systems-Local and metropolitan area networks-Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 5: Spectrum and Transmit Power Management Extensions in the 5 GHz band in Europe; IEEE Computer Society LAN/MAN Standards Committee; Oct. 14, 2003; 75 pages.
IEEE Std 802.11h-2003 (Amendment to IEEE Std 802.11, 1999 Edition (Reaff 2003)); as amended by IEEE Stds 802.11a-1999, 802.11b-1999, 802.11b-1999/Cor 1-2001, 802.11d2001, and 802.11g-2003; IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 5: Spectrum and Transmit Power Management Extensions in the 5 GHz band in Europe; IEEE Computer Society LAN/MAN Standards Committee; Oct. 14, 2003; 75 pages.
K.A.S. Immink, Codes for Mass Data Storage Systems; pp. 221-223, 1991.
Li, Z. et al; "Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes"; IEEE Transactions on Communications, vol. 54, No. 1, Jan. 2006; pp. 71-81.
Marcus, B. et al., "Finite-State Modulation Codes for Data Storage"; IEEE Journal on Selected Areas in Communications, vol. 10, No. 1, pp. 5-37, Jan. 1992.
Morita, T. et al., "Efficiency of Short LDPC Codes Combined with Long Reed-Solomon Codes for Magnetic Recording Channels"; IEEE Transactions on Magnetics, vol. 40, No. 4, pp. 3078-3080, Jul. 2004.
Ryan, W. et al., "Performance of High Rate Turbo Codes on a PR4-Equalized Magnetic Recording Channel"; pp. 947-951, 1998 IEEE.
U.S. Appl. No. 11/449,066; "Tensor Product Codes Containing an Iterative Code", Jun. 7, 2006; 71 pages.
U.S. Appl. No. 11/518,020; "Error Pattern Generation for Trellis-Based Detection and/or Decoding"; Sep. 8, 2006; 95 pages.
Widmer, A.X. et al., "A DC-Balanced, Partitioned-Block, 8B/10B Transmission Code"; IBM J. Res. Develop., vol. 27, No. 5, pp. 440-451, Sep. 1983.
US10148292B2 (en) * 2013-03-15 2018-12-04 Quanta Computer, Inc. Error-correcting code
US8291290B1 (en) 2012-10-16
US7571372B1 (en) 2009-08-04
JP4198904B2 (en) 2008-12-17 Recording / reproducing apparatus, signal decoding circuit, error correcting method, and iterative decoder
JP3966993B2 (en) 2007-08-29 Product code error correction and parallel checking