Practical coding boosts computing Boolean functions over noisy channels

Task-Oriented Boolean Function Computation: Practical Code Constructions

Information Theory

Summary

Sometimes computers need to figure out yes-or-no answers about information sent over a communication line, even when that information is hidden. The authors created a new way to build codes that let a receiver figure out a true or false answer (a Boolean function) accurately, even if the channel is noisy or imperfect. Their method uses special codes called Reed--Solomon codes and shows how fast and reliably these answers can be found. They also tested how well this works with different functions and found it improves the signal quality needed for accurate results compared to older methods.

What this means in practice

  • For network engineers: Develop communication systems that efficiently compute binary decisions over noisy channels with fewer errors and improved reliability.
  • For wireless system designers: Design coding schemes that reduce signal strength requirements for decision-based tasks in wireless communications, enhancing performance under interference.

Authors

Yangshuo He, Guanding Yu, Jingge Zhu

Abstract

Task-oriented communication conveys information that is necessary for downstream tasks. For binary decision tasks, this paradigm is information-theoretically formalized by Boolean function computation (BFC) via channels, where the receiver aims to determine the value of a function unknown to the transmitter. In this paper, we devise a practical code construction for the BFC problem based on a Reed--Solomon code. For noiseless binary channels, we derive finite-blocklength worst-case error bounds. By defining a rate function that captures how supported message length scales with channel uses, we characterize the rate-reliability tradeoff for different Boolean function families. With respect to this scaling, the proposed construction achieves an asymptotic computation rate of $1/2$. We further extend this construction to noisy channels by packing multiple BFC tasks into a single block and concatenating them with a conventional channel code. The corresponding finite-blocklength guarantees are expressed in terms of effective channel uses per function evaluation. With a channel code rate $R_c$, this construction achieves an asymptotic computation rate of $R_c/2$, yielding $C/2$ when capacity-achieving channel codes are employed. Numerical results illustrate the derived bounds and demonstrate substantial performance gains over conventional transmission. As examples, the proposed coding scheme achieves SNR coding gains of approximately $3.4$ and $6.4$~dB for the exact-weight and rank-test tasks, respectively.