2014/08/25 by Shigeaki Kuzuoka, Shun Watanabe, Kuzuoka, Shigeaki +1
Computer Science · Engineering · Mathematics · #Computability, Logic, AI Algorithms #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1408.5971
29 pages, 4 figures. In v2, results in Section 3.D are added. In v3, a terminology is changed. In v4, a typo is fixed
openalex publication_date 2014/08/25 · arxiv created 2015/05/09 · arxiv updated 2015/05/12 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
The problem of distributed data compression for function computation is considered, where (i) the function to be computed is not necessarily symbol-wise function and (ii) the information source has memory and may not be stationary nor ergodic. We introduce the class of smooth sources and give a sufficient condition on functions so that the achievable rate region for computing coincides with the Slepian-Wolf region (i.e., the rate region for reproducing the entire source) for any smooth sources. Moreover, for symbol-wise functions, the necessary and sufficient condition for the coincidence is established. Our result for the full side-information case is a generalization of the result by Ahlswede and Csiszar to sources with memory; our dichotomy theorem is different from Han and Kobayashi's dichotomy theorem, which reveals an effect of memory in distributed function computation. All results are given not only for fixed-length coding but also for variable-length coding in a unified manner. Furthermore, for the full side-information case, the error probability in the moderate deviation regime is also investigated.