Algorithmic complexity of ß-expansions and application to A/D conversion

Authors

Valentin Abadie and Helmut Bölcskei

Reference

arXiv:2405.03816, May 2025.

Abstract

We establish diverse relationships between the algorithmic (Kolmogorov) complexity of the prefixes of any binary expansion and ß-expansions. These relationships allow to develop intuition on the complexity behavior of ß-expansions, and raise problems related to compressibility of binary sequences generated in the context of A/D conversion relying on ß-expansions. Our last contribution is to solve these problems.

Download this document:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.