Kolmogorov complexity and the asymptotic bound for error-correcting codes

Details Kolmogorov complexity and the asymptotic bound for error-correcting codes Kolmogorov complexity and the asymptotic bound for error-correcting codes

2012-03-03

arxiv.org/abs/1203.0653v1

Computer Science

Information Theory

21 pages

Scientific paper

The set of all error--correcting block codes over a fixed alphabet with $q$ letters determines a recursively enumerable set of rational points in the unit square with coordinates $(R,\delta)$:= {\it (relative transmission rate, relative minimal distance).} Limit points of this set form a closed subset, defined by $R\le \alpha_q(\delta)$, where $\alpha_q(\delta)$ is a continuous decreasing function called {\it asymptotic bound.} Its existence was proved by the first--named author in 1981 ([Man1]), but no approaches to the computation of this function are known, and in [Man5] it was even suggested that this function might be uncomputable in the sense of constructive analysis. In this note we show that the asymptotic bound becomes computable with the assistance of an oracle producing codes in the order of their growing Kolmogorov complexity. Moreover, a natural partition function involving complexity allows us to interpret the asymptotic bound as a curve dividing two different thermodynamic phases of codes.

Affiliated with

Also associated with

No associations

Rating

Kolmogorov complexity and the asymptotic bound for error-correcting codes 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 Kolmogorov complexity and the asymptotic bound for error-correcting codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov complexity and the asymptotic bound for error-correcting codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345665