Algorithmic complexity of ${\hat{I}}^2$-expansions and application to A/D conversion

Abstract

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