Chien search

Last updated

In abstract algebra, the Chien search, named after Robert Tienwen Chien, is a fast algorithm for determining roots of polynomials defined over a finite field. Chien search is commonly used to find the roots of error-locator polynomials encountered in decoding Reed-Solomon codes and BCH codes.

Algorithm

The problem is to find the roots of the polynomial Λ(x) (over the finite field GF(q)):

The roots may be found using brute force: there are a finite number of x, so the polynomial can be evaluated for each element xi. If the polynomial evaluates to zero, then that element is a root.

For the trivial case x = 0, only the coefficient λ0 need be tested for zero. Below, the only concern will be for non-zero xi.

A straightforward evaluation of the polynomial involves O(t2) general multiplications and O(t) additions. A more efficient scheme would use Horner's method for O(t) general multiplications and O(t) additions. Both of these approaches may evaluate the elements of the finite field in any order.

Chien search improves upon the above by selecting a specific order for the non-zero elements. In particular, the finite field has a (constant) generator element α. Chien tests the elements in the generator's order α1, α2, α3, ..... Consequently, Chien search needs only O(t) multiplications by constants and O(t) additions. The multiplications by constants are less complex than general multiplications.

The Chien search is based on two observations:

In other words, we may define each as the sum of a set of terms , from which the next set of coefficients may be derived thus:

In this way, we may start at with , and iterate through each value of up to . If at any stage the resultant summation is zero, i.e.

then also, so 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.

Related Research Articles

In the mathematical field of representation theory, a weight of an algebra A over a field F is an algebra homomorphism from A to F, or equivalently, a one-dimensional representation of A over F. It is the algebra analogue of a multiplicative character of a group. The importance of the concept, however, stems from its application to representations of Lie algebras and hence also to representations of algebraic and Lie groups. In this context, a weight of a representation is a generalization of the notion of an eigenvalue, and the corresponding eigenspace is called a weight space.

In mathematics, the classical orthogonal polynomials are the most widely used orthogonal polynomials: the Hermite polynomials, Laguerre polynomials, Jacobi polynomials.

Quantum group Algebraic construct of interest in theoretical physics

In mathematics and theoretical physics, the term quantum group denotes one of a few different kinds of noncommutative algebras with additional structure. These include Drinfeld–Jimbo type quantum groups, compact matrix quantum groups, and bicrossproduct quantum groups.

Lindemann–Weierstrass theorem On algebraic independence of exponentials of linearly independent algebraic numbers over Q

In transcendental number theory, the Lindemann–Weierstrass theorem is a result that is very useful in establishing the transcendence of numbers. It states the following.

Polynomial ring Algebraic structure

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In field theory, the primitive element theorem or Artin's theorem on primitive elements is a result characterizing the finite degree field extensions that possess a primitive element, or simple extensions. It says in that a finite extension is simple if and only if there are only finitely many intermediate fields. In particular, finite separable extensions are simple, more general.

The Gell-Mann matrices, developed by Murray Gell-Mann, are a set of eight linearly independent 3×3 traceless Hermitian matrices used in the study of the strong interaction in particle physics. They span the Lie algebra of the SU(3) group in the defining representation.

In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.

In differential geometry, a tensor density or relative tensor is a generalization of the tensor field concept. A tensor density transforms as a tensor field when passing from one coordinate system to another, except that it is additionally multiplied or weighted by a power W of the Jacobian determinant of the coordinate transition function or its absolute value. A distinction is made among (authentic) tensor densities, pseudotensor densities, even tensor densities and odd tensor densities. Sometimes tensor densities with a negative weight W are called tensor capacity. A tensor density can also be regarded as a section of the tensor product of a tensor bundle with a density bundle.

In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set which represents the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.

In continuum mechanics, the finite strain theory—also called large strain theory, or large deformation theory—deals with deformations in which strains and/or rotations are large enough to invalidate assumptions inherent in infinitesimal strain theory. In this case, the undeformed and deformed configurations of the continuum are significantly different, requiring a clear distinction between them. This is commonly the case with elastomers, plastically-deforming materials and other fluids and biological soft tissue.

In mathematics, the Weyl character formula in representation theory describes the characters of irreducible representations of compact Lie groups in terms of their highest weights. It was proved by Hermann Weyl. There is a closely related formula for the character of an irreducible representation of a semisimple Lie algebra. In Weyl's approach to the representation theory of connected compact Lie groups, the proof of the character formula is a key step in proving that every dominant integral element actually arises as the highest weight of some irreducible representation. Important consequences of the character formula are the Weyl dimension formula and the Kostant multiplicity formula.

In mathematics, the Schur orthogonality relations, which is proven by Issai Schur through Schur's lemma, express a central fact about representations of finite groups. They admit a generalization to the case of compact groups in general, and in particular compact Lie groups, such as the rotation group SO(3).

A synchronous frame is a reference frame in which the time coordinate defines proper time for all co-moving observers. It is built by choosing some constant time hypersurface as an origin, such that has in every point a normal along the time line ; all interval elements on this hypersurface are space-like. A family of geodesics normal to this hypersurface are drawn and defined as the time coordinates with a beginning at the hypersurface.

In coding theory, the Forney algorithm calculates the error values at known error locations. It is used as one of the steps in decoding BCH codes and Reed–Solomon codes. George David Forney Jr. developed the algorithm.

In mathematics, Ricci calculus constitutes the rules of index notation and manipulation for tensors and tensor fields in a Riemannian manifold. It is also the modern name for what used to be called the absolute differential calculus, developed by Gregorio Ricci-Curbastro in 1887–1896, and subsequently popularized in a paper written with his pupil Tullio Levi-Civita in 1900. Jan Arnoldus Schouten developed the modern notation and formalism for this mathematical framework, and made contributions to the theory, during its applications to general relativity and differential geometry in the early twentieth century.

Relativistic angular momentum Angular momentum in special and general relativity

In physics, relativistic angular momentum refers to the mathematical formalisms and physical concepts that define angular momentum in special relativity (SR) and general relativity (GR). The relativistic quantity is subtly different from the three-dimensional quantity in classical mechanics.

The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields. This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results. When applied to a DFT over , this algorithm has a very low multiplicative complexity. In practice, since there usually exist efficient algorithms for circular convolutions with specific lengths, this algorithm is very efficient.

In mathematics, the exterior algebra has a rich algebraic structure. The exterior algebra of vector fields on manifolds has an even richer structure driven by the interplay of differentiation on the manifold with the properties of the exterior algebra. This article summarizes several identities in exterior calculus.

References