2024/05/14 by Daniella Bar-Lev, Bar-Lev, Daniella, Adir Kobovich +5 · 1 citation
Mathematics · #Advanced Banach Space Theory #Approximation Theory and Sequence Spaces #FOS: Computer and information sciences #Fixed Point Theorems Analysis #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2405.08625
openalex publication_date 2024/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a novel approach to address the constrained coding challenge of generating almost-balanced sequences. While strictly balanced sequences have been well studied in the past, the problem of designing efficient algorithms with small redundancy, preferably constant or even a single bit, for almost balanced sequences has remained unsolved. A sequence is ε(n)-almost balanced if its Hamming weight is between 0.5n± ε(n). It is known that for any algorithm with a constant number of bits, ε(n) has to be in the order of Θ(√(n)), with O(n) average time complexity. However, prior solutions with a single redundancy bit required ε(n) to be a linear shift from n/2. Employing an iterative method and arithmetic coding, our emphasis lies in constructing almost balanced codes with a single redundancy bit. Notably, our method surpasses previous approaches by achieving the optimal balanced order of Θ(√(n)). Additionally, we extend our method to the non-binary case considering q-ary almost polarity-balanced sequences for even q, and almost symbol-balanced for q=4. Our work marks the first asymptotically optimal solutions for almost-balanced sequences, for both, binary and non-binary alphabet.