# US 2013/0254635 A1 · Chien Search Using Multiple Basis Representation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2013/0254635 A1 - Document ID: US20130254635A1 - Status: Published application - Kind: A1 - Application number: 13/895,650 - Filed: 2013-05-16 - Published: 2013-09-26 - Earliest claimed: 2009-06-30 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Micha Anholt - Web page: https://patentgrep.com/patent/US20130254635A1 ## CPC - H03M 13/09: Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit - G06F 11/1008: {in individual solid state devices (G06F11/1004 takes precedence)} - H03M 13/152: {Bose-Chaudhuri-Hocquenghem [BCH] codes} - H03M 13/1525: {Determination and particular use of error location polynomials} - H03M 13/1545: {Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial} - 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 A method for decoding an Error Correction Code (ECC) includes accepting coefficients, including at least first and second coefficients, of an Error Locator Polynomial (ELP) that is defined over a vector space and has at least one root that is indicative of a location of an error in a set of bits, which represent data that has been encoded with the ECC. The first coefficient is represented using a first basis of the vector space, and the second coefficient is represented using a second basis of the vector space, different from the first basis. Using processing circuitry, the root of the ELP is identified by applying algebraic operations to the coefficients, such that the algebraic operations are applied to the first coefficient using the first basis, and to the second coefficient using the second basis. The error is corrected responsively to the identified root of the ELP. ## Claims ### Claim 1 A non-transitory computer-accessible storage medium having program instructions stored therein that, in response to execution by a computer system, causes the computer system to perform operations including: receiving a code word, wherein the code word is encoded with an Error Correction Code (ECC); generating one or more syndromes dependent upon the received code word; determining an Error Locator Polynomial (ELP) dependent upon the generated syndromes, wherein the ELP is defined over a field, and wherein the ELP includes at least one root indicative of a location of an error within the code word; determining roots of the ELP; and decoding the received code word dependent upon the determined roots of the ELP. ### Claim 2 (depends on 1) The non-transitory computer-accessible storage medium of claim 1, wherein the computer system performs operations further including storing each coefficient of the ELP is a respective one of a plurality of registers. ### Claim 3 (depends on 1) The non-transitory computer-accessible storage medium of claim 1, wherein determining the roots of the ELP comprises selecting one of a first operational mode and a second operational mode. ### Claim 4 (depends on 3) The non-transitory computer-accessible storage medium of claim 3, the computer system performs, in response to the selection of the first operational mode, operations further including evaluating the ELP on a single element of the field. ### Claim 5 (depends on 3) The non-transitory computer-accessible storage medium of claim 3, wherein the computer system performs, in response to the selection of the second operational mode, operations further including evaluating the ELP on at least two elements of the field concurrently. ### Claim 6 (depends on 1) The non-transitory computer-accessible storage medium of claim 1, wherein generating the one or more syndromes comprises multiplying the received code word by a parity check matrix. ### Claim 7 (depends on 2) The non-transitory computer-accessible storage medium of claim 2, wherein determining the ELP comprises transforming the coefficients of the ELP to a respective basis ### Claim 8 A data storage system, comprising: one or more memories, wherein each memory of the one or more memories includes: a read/write unit; and a plurality of data storage cells; and a memory controller coupled to the one or more memories, wherein the memory controller is configured to: retrieve a code word stored in the one or more memories, wherein the code word is encoded with an Error Correction Code (ECC); generate one or more syndromes dependent upon the retrieved code word; determine an Error Locator Polynomial (ELP) dependent upon the generated syndromes, wherein the ELP is defined over a field, and wherein the ELP includes at least one root indicative of a location of an error within the code word; determine roots of the ELP; and decode the retrieved code word dependent upon the determined roots of the ELP. ### Claim 9 (depends on 8) The system of claim 8, wherein the memory controller is further configured to output the decoded code word to a host processor. ### Claim 10 (depends on 8) The system of claim 8, wherein each memory of the one or more memories comprises a non-volatile memory. ### Claim 11 (depends on 8) The system of claim 8, wherein to determine the roots of the ELP, the memory controller is further configured to transform coefficients of the ELP to a respective basis. ### Claim 12 (depends on 8) The system of claim 8, wherein the memory controller includes a plurality of registers, wherein each register of the plurality of registers is configured to store a respective coefficient of the ELP. ### Claim 13 (depends on 12) The system of claim 12, wherein the memory controller further includes a plurality of multiplier circuits, wherein each multiplier circuit of the plurality of multiplier circuits is coupled to a respective one of the plurality of registers. ### Claim 14 (depends on 8) The system of claim 8, wherein the ELP is defined over a field. ### Claim 15 A method of operating an Error Correction Code (ECC) decoder, comprising: receiving a code word, wherein the code word is encoded with an ECC; generating one or more syndromes dependent upon the received code word; determining an Error Locator Polynomial (ELP) dependent upon the generated syndromes, wherein the ELP is defined over a field, and wherein the ELP includes at least one root indicative of a location of an error within the code word; determining roots of the ELP; and decoding the received code word dependent upon the determined roots of the ELP. ### Claim 16 (depends on 15) The method of claim 15, wherein the code word is received from a memory. ### Claim 17 (depends on 15) The method of claim 15, wherein the code word is received from a radio frequency (RF) signal. ### Claim 18 (depends on 15) The method of claim 15, wherein determining the roots of the ELP comprises transforming each coefficient of the ELP to a respective basis. ### Claim 19 (depends on 15) The method of claim 15, wherein determining the roots of the ELP comprises storing each coefficient of the ELP is a respective one of a plurality of registers. ### Claim 20 (depends on 15) The method of claim 15, further comprising sending the decoded code word to a processor.