Succinct Representation of Codes with Applications to Testing

Details Succinct Representation of Codes with Applications to Testing Succinct Representation of Codes with Applications to Testing

2009-05-18

arxiv.org/abs/0905.2919v1

Computer Science

Information Theory

Scientific paper

Motivated by questions in property testing, we search for linear error-correcting codes that have the "single local orbit" property: i.e., they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every "sparse" binary code whose coordinates are indexed by elements of F_{2^n} for prime n, and whose symmetry group includes the group of non-singular affine transformations of F_{2^n} has the single local orbit property. (A code is said to be "sparse" if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (i.e., for BCH codes) simple bases were not known. Our result gives the first short (O(n)-bit, as opposed to the natural exp(n)-bit) description of a low-weight basis for BCH codes. The interest in the "single local orbit" property comes from the recent result of Kaufman and Sudan (STOC 2008) that shows that the duals of codes that have the single local orbit property under the affine symmetry group are locally testable. When combined with our main result, this shows that all sparse affine-invariant codes over the coordinates F_{2^n} for prime n are locally testable. If, in addition to n being prime, if 2^n-1 is also prime (i.e., 2^n-1 is a Mersenne prime), then we get that every sparse cyclic code also has the single local orbit. In particular this implies that BCH codes of Mersenne prime length are generated by a single low-weight codeword and its cyclic shifts.

Affiliated with

Also associated with

No associations

Rating

Succinct Representation of Codes with Applications to Testing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Succinct Representation of Codes with Applications to Testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Representation of Codes with Applications to Testing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-610046