PaperlayerView exact revision on arXiv

Source-linked AI summary

Task-Oriented Boolean Function Computation: Practical Code Constructions

Yangshuo He, Guanding Yu, Jingge Zhu

arXiv:2610.01228v2cs.ITmath.IT

TL;DR

BFC requires determining how many channel uses suffice to reliably compute a receiver-selected function of a message that the transmitter cannot know. The paper adapts RS tagging for noiseless BFC and extends it to noisy channels by packing tagging codes and concatenating them with a standard channel code. At error probability 10−5, gains are 6.4 dB for rank-test task and 3.4 dB for exact-weight task; asymptotic computation rate can be arbitrarily close to 1/2.

  • Problem

    BFC requires determining how many channel uses suffice to reliably compute a receiver-selected function of a message that the transmitter cannot know.

    Source: §I · p. 1

  • Method

    The paper adapts RS tagging for noiseless BFC and extends it to noisy channels by packing tagging codes and concatenating them with a standard channel code.

    Source: §I · p. 1, A. RS Tagging Code Construction · p. 2

  • Results

    At error probability 10−5, gains are 6.4 dB for rank-test task and 3.4 dB for exact-weight task; asymptotic computation rate can be arbitrarily close to 1/2.

    Source: C. Asymptotic Results · p. 4, C. Numerical Results · p. 7

  • Takeaways & Limitations

    The construction supports task computation without requiring transmission of the complete message, with guarantees stated in effective channel uses per BFC message.

    Source: §I · pp. 1–2

Abstract

from arXiv · show

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 rate function, 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 scheme achieves SNR coding gains of approximately $3.4$ and $6.4$ dB at an average task error probability of $10^{-5}$ for the exact-weight and rank-test tasks, respectively.

I. INTRODUCTION

Task-oriented communication targets the information needed for a downstream decision, and BFC formalizes binary tasks where the receiver must compute a function of the transmitter’s message. This paper adapts RS tagging to general BFC, deriving finite-blocklength and asymptotic guarantees for noiseless and noisy channels.

I. INTRODUCTION

  • BFC models settings where a transmitter’s binary message is unknown to the receiver, who must compute a function selected from a known family.The transmitter does not know the selected function, so it cannot directly send the function’s result.Source: §I · p. 1
  • Prior BFC results characterize asymptotic message-length scaling for Hamming-weight families, but do not provide an explicit finite-blocklength coding scheme.Existing RS tagging constructions are tailored to identification and do not directly yield finite-blocklength codes for general BFC problems.Source: §I · p. 1
  • The paper develops RS tagging for BFC, derives noiseless finite-blocklength and rate-reliability results, and extends the construction to noisy channels by concatenating with a standard channel code.For noisy channels, the results are expressed in effective channel uses per BFC message.Source: §I · pp. 1–2
  • The RS tagging construction achieves SNR coding gains of 3.4 dB for exact-weight tasks and 6.4 dB for rank-test tasks over conventional full-message transmission.The paper derives finite-blocklength worst-case error bounds and rate-reliability tradeoffs for noiseless channels, and extends the construction to noisy channels.Source: §I · pp. 1–2

II. BFC PROBLEM FORMULATION

In BFC, the receiver knows a function family but not the transmitter’s message or the selected function at the transmitter, and needs only the function value. The supported message-length scaling depends on the function family, motivating a general rate function.

II. BFC PROBLEM FORMULATION

  • The receiver selects a function from a shared family and seeks f(i), while the transmitter knows the binary message i but not the selected function.The function represents the receiver’s task; the receiver need not recover the complete message.Source: §II · p. 2
  • A BFC code uses an encoder for each message and a decoding region for each function, with false-negative and false-positive probabilities bounded by λ1 and λ2.The formulation applies independently of the channel model, covering noiseless and noisy settings.Source: §II · p. 2
  • The supported message length need not scale linearly with channel uses and its scaling depends on the Boolean function family.A general rate function captures that scaling, with the computation rate as its leading constant.Source: §II · p. 2
  • With L(R, n) = nR, message length scales linearly as in Shannon transmission, while L(R, n) = 2^nR represents exponential scaling for identification via channels.Computing functions of Hamming weight at most S defines a family; S = 1 corresponds to identification via channels.Source: §II · p. 2
  • The paper treats noiseless binary channels first, then extends the construction to noisy channels by concatenating multiple tagging codewords with a channel code.Source: §II · p. 2

A. RS Tagging Code Construction

The noiseless BFC construction adapts polynomial-hash RS tagging: it maps message blocks to finite-field symbols, encodes them with an RS code, and sends a randomly selected symbol as a tag.

A. RS Tagging Code Construction

  • A length-m binary message is divided into K consecutive r-bit blocks, each interpreted as a symbol over Fq, where q = 2^r.Zero-padding is used when r does not divide m.Source: A. RS Tagging Code Construction · p. 2
  • A (T, K) RS code maps the K-symbol message sequence to a length-T codeword over Fq, with 1 ≤ K ≤ T ≤ q.The codeword symbols are evaluations of the message-associated polynomial at distinct field elements.Source: A. RS Tagging Code Construction · p. 2
  • The encoder draws U uniformly from [T] and selects the corresponding RS codeword symbol cU(i) as the tag.Source: A. RS Tagging Code Construction · p. 2
  • Each tag has a binary representation of length nt = ⌈log T⌉ + r, encoding the index U and the selected r-bit RS symbol.The construction is illustrated as RS tagging for BFC over a noiseless channel.Source: A. RS Tagging Code Construction · p. 2, Figure 1 · p. 2

B. Finite-Blocklength Results

The RS tagging construction gives finite-blocklength worst-case error guarantees for noiseless-channel BFC and an explicit computation-rate/error-exponent tradeoff. With rate function LS, it supports computation rate 1/2 − E2 for the selected block parameters.

B. Finite-Blocklength Results

  • The error analysis reduces to collisions between RS codeword symbols; larger S or K raises collision probability, while larger T lowers it through positional randomization.The stated finite-blocklength guarantee is for RS parameters satisfying 1 ≤ K ≤ T ≤ q.Source: B. Finite-Blocklength Results · p. 3
  • For fixed nt, the RS parameters are coupled by nt = ⌈log T⌉ + r, and substituting the selected parameters yields the explicit finite-blocklength tradeoff.The relaxed error bound is mS(m)/(rT), so parameter choice controls its denominator.Source: B. Finite-Blocklength Results · p. 3
  • The finite-blocklength computation rate is 1/2 − E2 with rate function LS, for parameters selected by (15).The result applies when E2 ∈ (0, 1/2) and the set in (15) is non-empty.Source: B. Finite-Blocklength Results · pp. 3–4
  • At nt = 60, increasing E2 exponentially reduces the false-positive bound 2^-60E2 while decreasing computation rate.Fig. 2(a) plots log(m)/nt against E2 with m chosen using (15).Source: B. Finite-Blocklength Results · p. 4, Figure 2 · p. 4

C. Asymptotic Results

The RS tagging construction supports computation rates near 1/2 under the function-dependent rate function, with supported message-length scaling varying by Boolean-function weight growth. Compared with prior achievable rates, it matches the medium-weight rate but falls short in the exact-weight and large-weight comparisons reported.

C. Asymptotic Results

  • For any fixed η > 0, the RS tagging construction supports rate 1/2−η with arbitrarily small error for sufficiently large blocklengths, approaching 1/2.This is stated for the function-dependent rate function LS.Source: C. Asymptotic Results · p. 4
  • The rate 1/2 arises from dividing channel uses asymptotically equally between the random index and RS tag.The construction chooses r = ⌈nt/2⌉ and T = 2⌊nt/2⌋.Source: C. Asymptotic Results · p. 4
  • For small-weight growth log S(m)/log m → a, the achievable rate is 1/[2(1+a)] with Lsmall(R, n) = 2^Rn.The polynomial-growth case S(m) = m^a therefore permits exponential scaling of supported message length.Source: C. Asymptotic Results · pp. 4–5
  • For medium-weight growth, the achievable rate is 1/2 with Lmedium(R, n) = S←(2^Rn); for large-weight growth, it is 1/2 with Llarge(R, n) = Rn.In the large-weight regime, supported message length scales linearly with n.Source: C. Asymptotic Results · pp. 4–5
  • For exact-weight (a=2), the construction achieves 1/6 versus 1/5 in [7]; for identification and rank-test (a=0), it reaches half the theoretical capacity limit.In the medium-weight regime, its explicit code attains the 1/2 achievable rate reported in [7].Source: C. Asymptotic Results · p. 5
  • In the large-weight regime, the construction achieves rate 1/2, while transmitting the entire message achieves rate 1 under Llarge, making conventional transmission better there.Source: C. Asymptotic Results · p. 5

D. Numerical Results

The numerical study evaluates three Boolean-function tasks and finds that false-positive probabilities decline with more channel uses, while the stated bound is generally conservative.

D. Numerical Results

  • The tasks are fixed-target identification, rank-test with threshold 2000, and exact-weight testing for Hamming weight 2, with message lengths 100,000, 150, and 100.Their respective numbers of positive inputs are 1, 2,001, and 4,950.Source: D. Numerical Results · p. 5
  • For nt from 28 to 46 in steps of two, the study sets r = nt/2, T = 2r, and K = ceil(m/r), then estimates false positives using 2,000 sampled negative messages.The false-positive probability is evaluated by enumerating all T indices.Source: D. Numerical Results · p. 5
  • False-positive probabilities decrease as channel uses increase, and the bound is generally conservative for the three Boolean-function families.The plotted maximum is over sampled messages, not all possible messages and functions.Source: D. Numerical Results · p. 5

IV. CONCATENATED EXTENSION TO NOISY CHANNELS

The paper extends RS tagging to noisy channels by concatenating with a conventional channel code and packing independent task codewords into each information block. This packing addresses the inefficiency of using a channel code whose information block is much larger than a tagging codeword.

IV. CONCATENATED EXTENSION TO NOISY CHANNELS

  • The RS tagging construction produces an nt = ceil(log T) + r bit codeword A(i) for each message.The codeword is introduced as the noiseless BFC construction to be protected over a noisy channel.Source: §IV · p. 5
  • Directly concatenating each tagging codeword with a channel code can be highly inefficient because nt is considerably smaller than the channel code’s information block in practical applications..Source: §IV · p. 5
  • The proposed extension packs tagging codewords from independent messages into each channel-code block before deriving error bounds and an asymptotic achievable rate..Source: §IV · p. 5

A. Packed Concatenated RS Tagging Code Construction

The construction packs independent RS tagging codewords into a conventional channel-code information block and processes each task separately after channel decoding. Its stated channel-code model uses a maximal frame error rate, and the task-level normalization is effective channel uses per task.

A. Packed Concatenated RS Tagging Code Construction

  • The channel code maps Ni information bits to Nb transmitted bits, has maximal frame error rate ξ, and rate Rc = Ni/Nb.The encoder and decoder are denoted ϕc and ψc.Source: A. Packed Concatenated RS Tagging Code… · p. 6
  • When nt divides Ni, one information block packs G = Ni/nt independent tagging codewords; implementations use zero padding otherwise.The effective channel-use count is normalized per task as neff = Nb/G.Source: A. Packed Concatenated RS Tagging Code… · p. 6
  • For each of the G slots, the sender forms its noiseless BFC codeword, concatenates the codewords in a known order into V, and channel-encodes V.Each slot carries a message ig and its corresponding tagging codeword Ag.Source: A. Packed Concatenated RS Tagging Code… · p. 6
  • After channel decoding recovers the tagging codewords, the receiver selects a function for each slot and decides using its symbol-level decoding region.The received channel output is passed through ψc before the per-slot decisions.Source: A. Packed Concatenated RS Tagging Code… · p. 6
  • If channel distortion makes the decoded index invalid, the receiver declares zero; choosing T = 2^t with t ≤ r ensures the binary sequence maps to an index in [T]..Source: A. Packed Concatenated RS Tagging Code… · p. 6

B. Finite-Blocklength and Asymptotic Performance

The noisy-channel construction packs multiple BFC tasks and concatenates their tagging codes with a channel code, expressing guarantees per effective channel use per task. Its finite-blocklength rate is R_c/2 − E_2, and asymptotically it achieves R_c/2, or C/2 with capacity-achieving channel codes.

Effective channel uses

  • Packing makes N_b channel uses jointly serve G tasks, so n_eff denotes effective channel uses per task rather than a single-task code blocklength.The guarantees are stated for an effective BFC code.Source: B. Finite-Blocklength and Asymptotic… · p. 6

Error guarantees

  • Given correct channel decoding, FN and FP bounds remain those of the noiseless construction; channel failure adds at most ξ, without a factor G in per-task error.This preserves the individual task’s worst-case error structure when multiple tasks are packed.Source: B. Finite-Blocklength and Asymptotic… · p. 6

Finite-blocklength performance

Rate-reliability tradeoff

  • The exponent E_2 trades rate against error, while R_c scales the asymptotic rate because only a fraction of physical channel uses carry RS tagging bits.The noisy-channel rate function applies the noiseless tradeoff using effective channel uses.Source: B. Finite-Blocklength and Asymptotic… · pp. 6–7

Asymptotic performance

  • As n_eff grows and channel decoding error vanishes, the construction achieves computation rate R_c/2, reaching C/2 with capacity-achieving channel codes.The factor R_c reflects channel coding, while the remaining 1/2 comes from RS tagging.Source: B. Finite-Blocklength and Asymptotic… · p. 7

C. Numerical Results

The simulations compare packed BFC with conventional full-message transmission over AWGN using the same channel uses and BPSK symbol energy. The packed construction obtains lower-SNR task computation for the reported exact-weight and rank-test tasks.

Simulation setup

  • The packed simulation uses n_t = 60, G = 360, N_b = 64,800, and n_eff = 180 effective channel uses per task.The 21,600-bit packed codewords use a rate-1/3 DVB-S2 LDPC code over AWGN with belief-propagation decoding.Source: C. Numerical Results · p. 7

Comparison setup

  • The comparison uses 64,800 channel uses for 360 tasks and the same BPSK symbol energy; conventional transmission sends each complete message before evaluating its function.Full-message transmission for identification would require 100,000 channel uses even with a noiseless channel.Source: C. Numerical Results · p. 7

AWGN results

  • At error probability 10^-5, the construction achieves a 6.4 dB gain for rank-test and 3.4 dB gain for exact-weight task; the gains stem from conveying task-relevant information through a short tagging code.Source: C. Numerical Results · p. 7

Scope and limitation

  • The construction’s rate remains suboptimal because it uses single-layer tagging; a two-layer improvement for S = 1 does not directly extend when S grows with m.Explicit capacity-achieving BFC constructions are left for future work.Source: C. Numerical Results · p. 7
Loading 2610.01228v2…