The term “Chien search” is used herein to refer to any typically recursive method or apparatus for determining roots of polynomials defined over a finite field. The term is also used herein to refer to any method or apparatus used for finding the roots of error-locator polynomials encountered in decoding, e.g. Reed-Solomon Odes and BCH codes in various applications such as but not limited to flash memory and other data storage applications, and data communications applications.
According to Wikipedia, in conventional Chien searches:
“We denote the polynomial (over the finite field GF(q)) whose roots we wish to determine as (formula I): Λ(x)=λ0+λ1x+λ2x2+ . . . +λtxt 
Conceptually, we may evaluate Λ(β) for each non-zero in GF(q). Those resulting in 0 are roots of the polynomial.
The Chien search is based on two observations:                Each non-zero β may be expressed as αiβ for some iβ, where α is the primitive element of GF(q). Therefore, the powers αi for 0≦i≦(N−1) cover the entire field (excluding the zero element).The following relationship exists (formula II):        
                                          Λ            ⁡                          (                              α                i                            )                                =                    ⁢                                    λ              0                        +                                          λ                1                            ⁡                              (                                  α                  i                                )                                      +                                                            λ                  2                                ⁡                                  (                                      α                    i                                    )                                            2                        +            …            +                                                            λ                  t                                ⁡                                  (                                      α                    i                                    )                                            t                                                                                =            Δ                    ⁢                    ⁢                                    γ                              0                ,                i                                      +                          γ                              1                ,                i                                      +                          γ                              2                ;                i                                      +            …            +                          λ                              t                ,                i                                                                                                  Λ            ⁡                          (                              α                                  i                  +                  1                                            )                                =                    ⁢                                    λ              0                        +                                          λ                1                            ⁡                              (                                  α                                      i                    +                    1                                                  )                                      +                                                            λ                  2                                ⁡                                  (                                      α                                          i                      +                      1                                                        )                                            2                        +            …            +                                                            λ                  t                                ⁡                                  (                                      α                                          i                      +                      1                                                        )                                            t                                                                    =                    ⁢                                    λ              0                        +                                                            λ                  1                                ⁡                                  (                                      α                    i                                    )                                            ⁢              α                        +                                                                                λ                    2                                    ⁡                                      (                                          α                      i                                        )                                                  2                            ⁢                              α                2                                      +            …            +                                                                                λ                    t                                    ⁡                                      (                                          α                      i                                        )                                                  t                            ⁢                              α                t                                                                                  =                    ⁢                                    γ                              0                ,                i                                      +                                          γ                                  1                  ,                  i                                            ⁢              α                        +                                          γ                                  2                  ,                  i                                            ⁢                              α                2                                      +            …            +                                          γ                                  t                  ,                  i                                            ⁢                              α                t                                                                                              =            Δ                    ⁢                    ⁢                                    γ                              0                ,                                  i                  +                  1                                                      +                          γ                              1                ,                                  i                  +                  1                                                      +                          γ                              2                ,                                  i                  +                  1                                                      +            …            +                          γ                              t                ,                                  i                  +                  1                                                                                    γ              j        ,                  i          +          1                      =                  γ                  j          ,          i                    ⁢              α        j            
In this way, we may start at i=0 with γj,0=λj, and iterate through each value of i up to (N−1). If at any stage the resultant summation is zero, i.e.
                    ∑                  j          =          0                t            ⁢              γ                  j          ,          i                      =    0    ,then Λ(αi)=0 also, so αi is a root. In this way, we check every element in the field.
When implemented in hardware, this approach significantly reduces the complexity, as all multiplications consist of one variable and one constant, rather than two variables as in the brute-force approach.”
A Chien search therefore may comprise the following steps:
a. Receive a polynomial, Λ(x)=λ0+λ1x+λ2x2+ . . . +λtxt defined over the finite field GF(q)) whose roots are to be determined, where the roots are the set of non-zero β in GF(q), for which Λ(β)=0
Repeat the following steps b-d for all non-zero β in GF(q)
b. Express β as αiB for some iβ, where α a is the primitive element of GF(q).
c. Define each Λ(αi) as the sum of a set of terms {γj,i|0≦j≦t}
d. Start at i=0 with γj,0=λj, and iterate through each value of i up to i=(N−1) where the iteration comprises deriving successive sets of terms using (formulae III):γj,i+1=γj,iαi 
However, if at any stage the resultant summation is zero, i.e.
                    ∑                  j          =          0                t            ⁢              γ                  j          ,          i                      =    0    ,stop and output that αi is a root.
Generally, any alpha^i for which the above error locator polynomial is zero, is termed a root. The above polynomial is encountered when decoding error correction code using Reed-Solomon code or BCH code. The alpha's are all primitive elements in a finite field over which the above polynomial is defined. The index of the power of the root indicates locations of errors. In BCH, each error is a flipped bit. In Reed-Solomon, each error is a symbol in which at least one bit is wrong. In other words, if αn is a root of the Error Locator Polynomial (ELP) then if binary BCH code is being used, an error has occurred in bit n of the data being read or received. If non-binary BCH code, or RS code, is used, the fact that αn is a root of the Error Locator Polynomial (ELP) implies that an error has occurred in symbol n of the received or read data.
The state of the art is believed to be represented by the following prior art documents inter alia:
a. U.S. Pat. Nos. 6,954,892; 6,990,624; 7,113,968; Published US Application 2007245220.
b. Error Correction Coding Mathematical Methods and Algorithms, Todd K. Moon, A JOHN WILEY & SONS, INC., 2005.
c. Introduction to Coding Theory, Ron M. Roth, Cambridge University Press, 2006.
d. Algebraic Codes for Data Transmission, Richard E. Blahut, Cambridge University Press, 2003.
e. Introduction to Error Correcting Codes, Michael Purser, Artech House Inc, 1995.
f. “High throughput and low-power architectures for Reed Solomon Decoder”, by Akash Kumar (a.kumar at tue.nl, Eindhoven University of Technology) and Sergei Sawitzki (Sergei.sawitzki at philips.com).
g. “Low power decoding of BCH codes”, by Yuejian Wu, Nortel Networks, Ottawa, Ont., Canada, in Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on Circuits and Systems, published 23-26 May 2004, Volume: 2, page(s): II-369-72 Vol. 2.h. “Small area parallel Chien search architectures for long BCH codes”, Yanni Chen; Parhi, K. K. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on. Volume 12, Issue 5, May 2004 Page(s): 545-549. Digital Object Identifier 10.1109/TVLSI.2004.826203.
The following terms may be construed either in accordance with any definition thereof appearing in the prior art literature or in accordance with the specification, or as follows:
Block=a set of flash memory device cells which must, due to physical limitations of the flash memory device, be erased together. Also termed erase sector, erase block.
Cell: A component of flash memory that stores one bit of information (in single-level cell devices) or n bits of information (in a multi-level device having 2 exp n levels). Typically, each cell comprises a floating-gate transistor. n may or may not be an integer. “Multi-level” means that the physical levels in the cell are, to an acceptable level of certainty, statistically partitionable into multiple distinguishable regions, plus a region corresponding to zero, such that digital values each comprising multiple bits can be represented by the cell. In contrast, in single-level cells, the physical levels in the cell are assumed to be statistically partitionable into only two regions, one corresponding to zero and one other, non-zero region, such that only one bit can be represented by a single-level cell.Charge level: the measured voltage of a cell which reflects its electric charge.Cycling: Repeatedly writing new data into flash memory cells and repeatedly erasing the cells between each two writing operations.Decision regions: Regions extending between adjacent decision levels, e.g. if decision levels are 0, 2 and 4 volts respectively, the decision regions are under 0 V, 0 V-2 V, 2V-4 V, and over 4 V.Demapping: basic cell-level reading function in which a digital n-tuple originally received from an outside application is derived from a physical value representing a physical state in the cell having a predetermined correspondence to the digital n-tuple.Digital value or “logical value”: n-tuple of bits represented by a cell in flash memory capable of generating 2 exp n distinguishable levels of a typically continuous physical value such as charge, where n may or may not be an integer.Erase cycle: The relatively slow process of erasing a block of cells (erase sector), each block typically comprising more than one page, or, in certain non-flash memory devices, of erasing a single cell or the duration of so doing. An advantage of erasing cells collectively in blocks as in flash memory, rather than individually, is enhanced programming speed: Many cells and typically even many pages of cells are erased in a single erase cycle.Erase-write cycle: The process of erasing a block of cells (erase sector), each block typically comprising a plurality of pages, and subsequently writing new data into at least some of them. The terms “program” and “write” are used herein generally interchangeably.Flash memory: Non-volatile computer memory including cells that are erased block by block, each block typically comprising more than one page, but are written into and read from, page by page. Includes NOR-type flash memory, NAND-type flash memory, and PRAM, e.g. Samsung PRAM, inter alia, and flash memory devices with any suitable number of levels per cell, such as but not limited to 2, 4, or (as in the embodiment illustrated herein) 8.Mapping: basic cell-level writing function in which incoming digital n-tuple is mapped to a program level by inducing a program level in the cell, having a predetermined correspondence to the incoming logical value.Page=A portion, typically 512 or 2048 or 4096 bytes in size, of a flash memory e.g. a NAND or NOR flash memory device. Writing can be performed page by page, as opposed to erasing which can be performed only erase sector by erase sector. A few bytes, typically 16-32 for every 512 data bytes are associated with each page (typically 16, 64 or 128 per page), for storage of error correction information. A typical block may include 32 512-byte pages or 64 2048-byte pages.Precise read, soft read: Cell threshold voltages are read at a precision (number of bits) greater than the number of Mapping levels (2^n). The terms precise read or soft read are interchangeable. In contrast, in “hard read”, cell threshold voltages are read at a precision (number of bits) smaller than the number of Mapping levels (2^n where n=number of bits per cell).Present level, Charge level: The amount of charge in the cell. The amount of charge currently existing in a cell, at the present time, as opposed to “program level”, the amount of charge originally induced in the cell (i.e. at the end of programming).Program: same as “write”.Program level (programmed level, programming level): amount of charge originally induced in a cell to represent a given logical value, as opposed to “present level”.Reprogrammability (Np): An aspect of flash memory quality. This is typically operationalized by a reprogrammability parameter, also termed herein “Np”, denoting the number of times that a flash memory can be re-programmed (number of erase-write cycles that the device can withstand) before the level of errors is so high as to make an unacceptably high proportion of those errors irrecoverable given a predetermined amount of memory devoted to redundancy. Typically recoverability is investigated following a conventional aging simulation process which simulates or approximates the data degradation effect that a predetermined time period e.g. a 10 year period has on the flash memory device, in an attempt to accommodate for a period of up to 10 years between writing of data in flash memory and reading of the data therefrom.Resolution: Number of levels in each cell, which in turn determines the number of bits the cell can store; typically a cell with 2^n levels stores n bits. Low resolution (partitioning the window, W, of physical values a cell can assume into a small rather than large number of levels per cell) provides high reliability.Retention: of original physical levels induced in the cells; retention is typically below 100% resulting in deterioration of original physical levels into present levels.Retention time: The amount of time that data has been stored in a flash device, typically without, or substantially without, voltage having been supplied to the flash device i.e. the time which elapses between programming of a page and reading of the same page.Symbol: Logical valueThreshold level: the voltage (e.g.) against which the charge level of a cell is measured. For example, a cell may be said to store a particular digital n-tuple D if the charge level or other physical level of the cell falls between two threshold values T.
Unless specifically stated otherwise, as apparent from the following discussions, it is appreciated that throughout the specification discussions, utilizing terms such as, “processing”, “computing”, “selecting”, “ranking”, “grading”, “calculating”, “determining”, “generating”, “reassessing”, “classifying”, “generating”, “producing”, “stereo-matching”, “registering”, “detecting”, “associating”, “superimposing”, “obtaining” or the like, refer to the action and/or processes of a computer or computing system, or processor or similar electronic computing device, that manipulate and/or transform data represented as physical, such as electronic; quantities within the computing system's registers and/or memories into other data similarly represented as physical quantities within the computing system's memories, registers or other such information storage, transmission or display devices.
The disclosures of all publications and patent documents mentioned in the specification, and of the publications and patent documents cited therein directly or indirectly, are hereby incorporated by reference.
USPTO Backgrounds
USPTO Backgrounds