Preparata code

In coding theory, the Preparata codes form a class of non-linear double-error-correcting codes. They are named after Franco P. Preparata who first described them in 1968.

Construction

Let m be an odd number, and n = 2^m − 1. We first describe the extended Preparata code of length 2n + 2 = 2^m + 1: the Preparata code is then derived by deleting one position. The words of the extended code are regarded as pairs (X, Y) of 2^m-tuples, each corresponding to subsets of the finite field GF(2^m) in some fixed way.

The extended code contains the words (X, Y) satisfying three conditions

1. X, Y each have even weight;
2. $\sum_{x \in X} x = \sum_{y \in Y} y;$
3. $\sum_{x \in X} x^3 + \left(\sum_{x \in X} x\right)^3 = \sum_{y \in Y} y^3.$

The Peparata code is obtained by deleting the position in X corresponding to 0 in GF(2^m).

Properties

The Preparata code is of length 2^m+1 − 1, size 2^k where k = 2^m + 1 − 2m − 2, and minimum distance 5.

When m = 3, the Preparata code of length 15 is also called the Nordstrom–Robinson code.

References

• F.P. Preparata (1968). "A class of optimum nonlinear double-error-correcting codes". Information and Control 13 (4): 378–400. doi:10.1016/S0019-9958(68)90874-7. 
• J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (2nd ed.). Springer-Verlag. pp. 111–113. ISBN 3-540-54894-7. 

This algebra-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Error detection and correction Finite fields Coding theory Algebra stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно сделать НИР? Web Help Desk Kōya Station (Tokyo) Look at other dictionaries: Franco P. Preparata — (born December 1935) is a computer scientist, the An Wang Professor of Computer Science at Brown University. He is best known for his 1985 computational geometry book with Michael Shamos, for many years the standard textbook in the field, but… …   Wikipedia List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia List of books in computational geometry — This is a list of books in computational geometry. There are two major, largely nonoverlapping categories: *Combinatorial computational geometry, which deals with collections of discrete objects or defined in discrete terms: points, lines,… …   Wikipedia Convex hull algorithms — Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science, see Convex hull applications . In computational geometry, numerous algorithms are proposed for computing the convex… …   Wikipedia List of computer scientists — Expand list|date=August 2008This is a list of well known computer scientists, people who do work in computer science, in particular researchers and authors.Some persons notable as programmers are included here because they work in research as… …   Wikipedia Interval tree — In computer science, an interval tree, also called a segment tree or segtree, is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is… …   Wikipedia Convex hull — The convex hull of the red set is the blue convex set. See also: Convex set and Convex combination In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the min …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”