Source: https://patents.google.com/patent/US8291290B1/en
Timestamp: 2019-12-06 08:38:37
Document Index: 521336589

Matched Legal Cases: ['art 11', 'art 11', 'art 11', 'art 11', 'art 11', 'art 11']

US8291290B1 - Methods and algorithms for joint channel-code decoding of linear block codes - Google Patents
US8291290B1
US8291290B1 US12/498,320 US49832009A US8291290B1 US 8291290 B1 US8291290 B1 US 8291290B1 US 49832009 A US49832009 A US 49832009A US 8291290 B1 US8291290 B1 US 8291290B1
US12/498,320
2009-07-06 Application filed by Marvell International Ltd filed Critical Marvell International Ltd
2012-10-16 Publication of US8291290B1 publication Critical patent/US8291290B1/en
This application is a divisional of U.S. patent application Ser. No. 11/166,548, filed Jun. 23, 2005, incorporated herein by reference in its entirety.
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
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}.
M ⁢ ⁢ L ⁢ ⁢ D ⁢ ⁢ P ⁡ ( e ) = ∑ i = 1 k ⁢ M ⁢ ⁢ L ⁢ ⁢ D ⁢ ⁢ P ⁡ ( 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.
p = min p ′ ∈ P ⁢ ( M ⁢ ⁢ L ⁢ ⁢ D ⁢ ⁢ P ⁡ ( p ′ ) ) .
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 if s 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.
he present invention, in its various aspects, will be explained in a greater detail in the context of magnetic recording system applications.
FIG. 7 shows an exemplary serial data block 200, comprising code words 210 and 220. First code word 210 comprises odd and even interleaved data subblocks 211, 212, 213 and 214 and CRC parity bits 215-217, and second code word 220 comprises odd and even interleaved data subblocks 221, 222, 223 and 224 and CRC parity bits 225-227. The basic idea is to switch the even and odd interleaves between successive CRC parity bits in a given code word. For example, in any of interleaved data subblocks 211-214 and 221-224, the even interleaved data contains bits x2k, while the odd interleaved data contains bits x2k+1, where k=0,1,2, . . . . For an exemplary data stream or data subblock 0101010101, the even interleaf is given by 00000, and the odd interleaf is 11111. If a (0,G/I) RLL encoder encodes data block 200, then inserting CRC parity information into the RLL encoded data one bit at a time degrades the G constraint by 1, and can cause a complete breakdown of the I constraint.
It thus becomes necessary to develop an encoder that inserts parity at predetermined locations. First, let {11,12, . . . 1n-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., {11,12, . . . 1n-k}). Code word remainders r(x) are computed in remainder logic 292 according to the equation:
c. Rem(p(x), g(x))=0; and
d. Among the p(x) satisfying 5(a), choose the one with the smallest MLDP:
To compute the remainder corresponding to error events, it is convenient to represent error events in polynomial notation. To this end, a polynomial xle(x) may be assigned to an error event, where 1 is the starting position of the error event in the CRC encoded data, and e(x) is the polynomial representation for error event type. For example, if e(x) is a single bit error, then e(x)=1. Similarly, if e(x) is a di-bit error, then e(x)=1+x. If such a di-bit error occurs at position 1=100, then the error event may be represented as x100(1+x). More generally,
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 e1 and e2 from the LMLE may have the incidence vector α=(1,1,0,0,0, . . . ,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 ]
placeholding logic configured to
insert dummy CRC information segments at or between a plurality of predetermined positions in a data block; and
a CRC encoding circuit configured to compute actual CRC information for the data block; and
a CRC information substituting circuit configured to substitute portions of the actual CRC information for the dummy CRC information segments in the dummy-padded data block.
2. The encoder of claim 1, wherein the CRC encoding circuit comprises:
parity computing logic configured to provide the actual CRC information portions to the CRC information substituting circuit.
3. The encoder of claim 1, further comprising a buffer configured to receive the dummy-padded data block and provide the dummy-padded data block to the CRC information substituting circuit.
4. The encoder of claim 1, wherein the CRC information substituting circuit comprises a multiplexer.
5. An encoding circuit, comprising:
a channel encoder configured to generate the data block.
6. The encoding circuit of claim 5, 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.
7. A method of encoding CRC information for a data block, the method comprising:
inserting dummy CRC information segments at or between a plurality of predetermined positions in the data block to generate a dummy-padded data block;
computing actual CRC information for the data block; and
substituting corresponding segments of the actual CRC information for the dummy CRC information in the plurality of predetermined positions in the dummy-padded data block to generate an CRC-encoded data block.
8. The method of claim 7, wherein the CRC information comprises a remainder generated by dividing the data block by a generator polynomial.
9. The method of claim 7, wherein the data block comprises a run length limited (RLL) code.
10. 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 7.
11. The method of claim 7, wherein computing the actual CRC information comprises computing a remainder for the dummy-padded data block.
12. The method of claim 11, wherein the actual CRC information consists of the remainder, and segments of the remainder have a length equal to the dummy CRC information segments.
US12/498,320 2005-06-23 2009-07-06 Methods and algorithms for joint channel-code decoding of linear block codes Active 2026-06-03 US8291290B1 (en)
US11/166,548 Division US7571372B1 (en) 2005-06-23 2005-06-23 Methods and algorithms for joint channel-code decoding of linear block codes
US13/608,390 Continuation US8516332B1 (en) 2005-06-23 2012-09-10 Methods and algorithms for joint channel-code decoding of linear block codes
US8291290B1 true US8291290B1 (en) 2012-10-16
802.11n; IEEE P802.11-0410889r6; Wireless LANs, TGn Sync Proposal Technical Specification; May 2005; 131 pages.
IEEE 802.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 802.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.11a-1999 (Supplement to IEEE Std 802.11-1999) [Adopted by ISO/IEC and redesignated as ISO/IEC 8802-11: 1999/Amd 1:2000(E)]; Supplement to 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 High-speed Physical Layer in the 5 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 91 pages.
IEEE Std 802.11a-1999 (Supplement to IEEE Std 802.11-1999) [Adopted by ISO/IEC and redesignated as ISO/IEC 8802-11: 1999/Amd 1:2000(E)]; Supplement to 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 High-speed Physical Layer in the 5 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 91 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 Jan. 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 Jan. 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.
Ryan, W. et al., "Performance of High Rate Turbo Codes on a PR4-Equalized.Magnetic Recording Channel"; pp. 947-951, 1998 IEEE.
US8516332B1 (en) 2013-08-20