PaperlayerView exact revision on arXiv

Source-linked AI summary

HiCoMAC: Histogram-State Coded Multiple Access Computing via Computation-Oriented Modulation Design

Xiaojing Yan, Carlo Fischione

arXiv:2609.34808v1eess.SP

TL;DR

Digital AirComp seeks reliable computation from superposed transmissions, while existing coded methods do not exploit permutation invariance to form decoding states or use computation-output separation in modulation design. HiCoMAC decodes arithmetic sums with histogram states and uses computational free distance to design QAM; simulations report larger distance and lower NMSE than square QAM, and lower NMSE than considered multi-symbol baselines.

  • Problem

    Existing coded AirComp either retains user-specific decoding states or focuses on reliable coded aggregation, without exploiting permutation invariance or explicitly using computation-output signal separation in modulation design.

    Source: A. Related Work and Motivation · p. 2

  • Method

    HiCoMAC uses histogram-state log-max MAP Viterbi decoding to recover arithmetic sums and computational free distance to optimize the rectangular ratio of a fixed labeled QAM constellation.

    Source: B. Contributions · p. 2

  • Results

    HiCoMAC achieves a larger computational free distance and lower NMSE than square QAM, and lower NMSE than the considered multi-symbol AirComp strategies.

    Source: B. Contributions · p. 2

  • Takeaways & Limitations

    The simulations demonstrate improved computation reliability in computational free distance and NMSE, alongside substantially reduced decoding complexity.

    Source: §VII · p. 12

Abstract

from arXiv · show

Nowadays, over-the-air computation (AirComp) exploits the waveform superposition property of the wireless multiple access channel to directly compute a function of distributed data from simultaneously transmitted signals. In this paper, we propose Histogram-State Coded Multiple Access Computing (HiCoMAC), a fundamentally new convolutional-coded method for digital AirComp that directly recovers the arithmetic-sum sequence from the superposition of coded and modulated user signals. HiCoMAC exploits the permutation invariance of the sum function to represent the multi-user convolutional encoder state by the numbers of users occupying the individual encoder states. This central idea enables log-max maximum a posterior (MAP) histogram-state Viterbi decoding with substantially reduced state complexity compared to joint full-state decoding. We further introduce the computational free distance to distinguish histogram paths that produce different arithmetic-sum sequences and develop a weighted product graph for its shortest path evaluation. This distance is then used to optimize the rectangular ratio of a fixed labeled quadrature amplitude modulation (QAM) constellation to improve the computational accuracy. Simulation results show that the computation-oriented modulation design increases the computational free distance and reduces the normalized mean square error (NMSE), while HiCoMAC outperforms the considered multi-symbol digital AirComp baselines under equal transmission and energy budgets.

I. INTRODUCTION

AirComp computes aggregates directly from superposed wireless transmissions, but existing coded methods do not exploit computation symmetry to construct decoding states or guide modulation design. HiCoMAC uses histogram-state decoding and a computation-oriented distance criterion to design a fixed labeled QAM constellation.

A. Related Work and Motivation

  • Prior digital AirComp methods do not incorporate finite-state channel-code memory into multi-symbol designs or use computation-output separation to guide modulation design.Existing coded approaches retain user-specific states or focus on reliable coded aggregation.Source: A. Related Work and Motivation · pp. 1–2

B. Contributions

  • Under an ideally aligned AWGN multiple-access channel, HiCoMAC represents the joint convolutional encoder state by counts of users in each state, without distinguishing user identities.Source: B. Contributions · p. 2
  • Its log-max MAP histogram-state Viterbi decoder directly recovers the arithmetic-sum sequence, with state count growing polynomially rather than exponentially in users for fixed encoder memory.The exponential-growth comparison is with the joint full-state Viterbi decoder in.Source: B. Contributions · p. 2
  • Computational free distance measures minimum signal-space separation between irreducible error events producing different arithmetic-sum sequences, and a modified product graph evaluates it by shortest-path search.Source: B. Contributions · p. 2
  • HiCoMAC optimizes the rectangular ratio of a fixed labeled QAM constellation using computational free distance, evaluated through a coarse-to-fine search and Dijkstra algorithm.Source: B. Contributions · p. 2
  • HiCoMAC achieves larger computational free distance and lower NMSE than square QAM, and lower NMSE than the considered multi-symbol AirComp strategies.Source: B. Contributions · p. 2

A. Convolutional Coding and Modulation

  • Each user’s input is quantized, convolutionally encoded, and modulated for simultaneous transmission; the computation point estimates the arithmetic-sum sequence and reconstructs the sum.The users use the same convolutional code, and the encoders are terminated in the all-zero state.Source: A. Convolutional Coding and Modulation · pp. 2–3, Figure 1 · p. 3

B. Histogram-state Representation

The section introduces a histogram-state transition multigraph for multi-user AirComp, using the permutation invariance of arithmetic-sum computation to reduce complexity.

B. Histogram-state Representation

1) Single-User State Transition Graph:

The section moves from single-user encoder transitions to a multigraph whose histogram states aggregate users by encoder state. This representation exploits the sum function’s permutation invariance and retains transition-specific computation and signal information.

1) Single-User State Transition Graph:

  • Each single-user encoder state has two outgoing transitions, one for each binary input.An input bit determines the next state and coded output, which is mapped to a transmitted modulation symbol.Source: 1) Single-User State Transition Graph · p. 4

2) Histogram-State Transition Multigraph:

  • Histogram states group users by their encoder states, making joint states that differ only by user permutation equivalent for sum computation.The ordered joint state space and its outgoing transitions grow exponentially with the number of users.Source: 2) Histogram-State Transition Multigraph · p. 4
  • The histogram-state transition structure is represented as a directed multigraph, with each vertex corresponding to a possible histogram state.Different multi-user inputs can produce parallel transitions between the same source and target states.Source: 2) Histogram-State Transition Multigraph · p. 4
  • A histogram edge represents a multi-user transition specified by an input-count vector and carries an arithmetic-sum label.The edge also retains associated signal information, while its multiplicity counts ordered input realizations represented by the same edge.Source: 2) Histogram-State Transition Multigraph · pp. 4–5
  • For the two-user example, the histogram graph has three states: (2, 0), (1, 1), and (0, 2).Source: 2) Histogram-State Transition Multigraph · p. 5

III. HISTOGRAM-STATE DECODING

The decoder targets the arithmetic-sum sequence rather than individual user messages, using a MAP criterion over histogram paths. A log-max approximation turns this criterion into a minimum-metric trellis-path search.

A. Arithmetic-Sum Sequence Criterion

  • A terminated path starts and ends at the all-zero histogram state; its information-segment edges determine the arithmetic-sum sequence.The final m edges terminate the encoder and are excluded from the information segment.Source: A. Arithmetic-Sum Sequence Criterion · p. 5
  • The prior probability of each terminated histogram path is evaluated under mutually independent, equiprobable information bits.Source: A. Arithmetic-Sum Sequence Criterion · p. 5
  • The MAP sequence decoder aggregates posterior probabilities of terminated histogram paths that produce the same arithmetic-sum sequence.All ordered multi-user realizations of a histogram path have the same noiseless aggregate and can be evaluated without retaining user identities.Source: A. Arithmetic-Sum Sequence Criterion · p. 5
  • The log-max approximation converts the sequence-oriented MAP criterion into a minimum-metric path search on the histogram-state trellis.The original objective is sequence recovery, not direct minimization of reconstructed-value NMSE; NMSE is assessed separately.Source: A. Arithmetic-Sum Sequence Criterion · p. 5
  • In the two-user illustration, the highlighted survivor yields arithmetic-sum symbols (1, 2, 1) over three information transitions, followed by termination.Source: A. Arithmetic-Sum Sequence Criterion · p. 6

B. Log-Max MAP Histogram-State Decoding

The log-max decoder applies Viterbi recursion to the histogram-state trellis, selecting a minimum-metric terminated path and tracing it back to reconstruct the computation. The section also notes that soft-output inference is possible but outside this work’s focus.

B. Log-Max MAP Histogram-State Decoding

  • Viterbi decoding exactly solves the minimum-metric terminated histogram-path problem produced by the log-max approximation.The decoder traces back the lowest-metric surviving path after the final stage and reconstructs the computation value.Source: B. Log-Max MAP Histogram-State Decoding · p. 6
  • The Add-Compare-Select operation updates each target state’s path metric using its incoming histogram edges and stores survivor information.The recursion initializes at the all-zero histogram state.Source: B. Log-Max MAP Histogram-State Decoding · p. 6
  • Soft-output BCJR inference could estimate posterior means of arithmetic-sum symbols, but those means generally need not form a valid terminated-path sequence.The paper focuses on sequence-oriented Viterbi decoding; soft-output Bayesian decoding and modulation design targeting computation MSE are left for future work.Source: B. Log-Max MAP Histogram-State Decoding · p. 6

C. Decoding Complexity

The histogram-state decoder has polynomial complexity in the user count for fixed encoder memory, rather than the full-state decoder’s exponential growth. The computational free distance measures the minimum signal-space separation between computationally distinct paths through irreducible error events, which can be evaluated using a weighted product graph.

C. Decoding Complexity

  • For fixed encoder memory, histogram-state decoding grows polynomially with user count, avoiding the full-state decoder’s exponential growth in states and trellis transitions.Decoding over T transitions requires at most TCH branch evaluations.Source: C. Decoding Complexity · p. 7

A. Computational Error Events and Free Distance

  • Computational free distance distinguishes histogram paths by their arithmetic-sum sequences, because different histogram paths can represent the same computation output.Computationally equivalent paths produce the same arithmetic-sum sequence; computationally distinct paths do not.Source: A. Computational Error Events and Free… · p. 7
  • Irreducible computational error events are path-segment pairs that diverge from a common histogram state, converge without an intermediate common state, and differ in their arithmetic-sum labels.Path pairs can be partitioned at common histogram states; at least one segment pair must have different arithmetic-sum label sequences when the complete paths are distinct.Source: A. Computational Error Events and Free… · p. 7
  • The event distance is the squared Euclidean separation between noiseless aggregated symbols, and zero distance indicates a destructive overlap between computationally distinct paths.The computational free distance is the minimum event distance over all finite irreducible computational error events.Source: A. Computational Error Events and Free… · p. 7
  • The computational free distance lower-bounds the minimum distance between computationally distinct terminated paths and serves as the modulation design criterion.The bound follows by partitioning path pairs at common histogram states and summing their nonnegative segment distances.Source: A. Computational Error Events and Free… · p. 7

IV. COMPUTATIONAL FREE DISTANCE VIA PRODUCT GRAPH ANALYSIS

  • A weighted product graph represents paired histogram-path segments, so computational free distance can be evaluated as the minimum accumulated distance over corresponding paths.The graph construction replaces a search over irreducible error events with a shortest-path evaluation.Source: A. Computational Error Events and Free… · p. 7

B. Product Graph Representation

The product multigraph represents pairs of histogram-path segments as directed paths. A modified version retains transitions needed for irreducible events and consolidates divergence and convergence vertices.

1) Product Multigraph for Paired Histogram Transitions:

  • The product multigraph represents pairs of histogram-path segments, with paired histogram transitions forming directed product edges.The accumulated edge distances along a product-graph path equal the distance of the corresponding path-segment pair.Source: 1) Product Multigraph for Paired… · pp. 7–8
  • Product vertices record two histogram states and a flag indicating whether their arithmetic-sum label sequences have differed so far.The flag is zero while the sequences are identical and one after they have differed on at least one transition.Source: 1) Product Multigraph for Paired… · p. 8

2) Modified Product Graph for Irreducible Events:

  • The modified product graph retains divergence, off-diagonal, and convergence transitions, merging divergence vertices into one start and convergence vertices into one end.Its edges merge product edges with the same modified source and destination, and the resulting graph contains the transitions needed to evaluate computational free distance.Source: 1) Product Multigraph for Paired… · p. 8, 2) Modified Product Graph for… · p. 8

C. Fixed Ratio Shortest Path Characterization

For a fixed rectangular ratio, the computational free distance is obtained by a shortest-path search on a weighted modified product graph. The paper uses this distance to design a QAM rectangular ratio, with a coarse-to-fine search over the prescribed interval.

C. Fixed Ratio Shortest Path Characterization

  • Fig. 4 illustrates the weighted modified product graph for the two-user histogram-state trellis, with arrow colors indicating edge weights.The example graph is constructed from the transition graph in Fig. 2(b).Source: Figure 4 · p. 9, C. Fixed Ratio Shortest Path… · p. 9
  • For fixed ratio ρ, the computational free distance equals the shortest-path distance from the initial to the final vertex of the weighted modified product graph.Each modified edge is assigned the minimum distance among the product edges in its candidate set, and path weights accumulate these edge weights.Source: C. Fixed Ratio Shortest Path… · pp. 8–9

A. Modulation Design Formulation

  • The modulation design optimizes the rectangular ratio of a fixed labeled QAM constellation using computational free distance, a lower bound on minimum distance for the finite terminated trellis.The stated geometric criterion could be extended to include event multiplicities, prior probabilities, and errors’ numerical significance across bit positions.Source: A. Modulation Design Formulation · p. 9

V. MODULATION DESIGN AND SOLUTION

  • Because the ratio objective can be nondifferentiable, the search uses an initial coarse grid followed by local grid refinement, evaluating each trial ratio by shortest-path computation.The component energies are evaluated once and remain fixed throughout the ratio search.Source: A. Modulation Design Formulation · p. 9, §V · p. 9

B. Coarse-to-Fine Ratio Search

The ratio search begins with an initial grid, then refines locally around the selected ratio until the grid spacing meets the specified tolerance. The final ratio is an approximate solution over the prescribed interval.

B. Coarse-to-Fine Ratio Search

  • Fig. 5 compares NMSE for exact MAP decoding and log-max MAP histogram-state decoding.Source: Figure 5 · p. 10
  • The search evaluates computational free distance at each initial-grid ratio using Dijkstra’s algorithm, then selects a ratio for refinement.The initial grid uses G points.Source: B. Coarse-to-Fine Ratio Search · pp. 9–10
  • Each refinement round centers a restricted search interval on the current ratio and evaluates only grid points not previously evaluated.The evaluated set and selected ratio are updated after each round.Source: B. Coarse-to-Fine Ratio Search · p. 10
  • The search stops when grid spacing is at most ϵρ and returns the selected ratio as an approximate solution to P0.The tolerance controls the search resolution.Source: B. Coarse-to-Fine Ratio Search · p. 10

C. Computational Complexity

HiCoMAC’s histogram-state decoding has polynomial complexity in the number of users for a fixed encoder, though offline graph construction and ratio search can remain demanding for large systems. Simulations validate the log-max approximation and report that larger computational free distance generally accompanies improved NMSE.

C. Computational Complexity

  • For a fixed convolutional encoder, Algorithm 1’s complexity grows polynomially with users, but product-edge enumeration can be demanding for large K or m.The graph construction and ratio search are intended for offline design at moderate problem sizes.Source: C. Computational Complexity · p. 10

A. Validation of the Log-Max Approximation

  • At high SNR, the log-max MAP histogram-state decoder’s NMSE closely approaches the exact MAP decoder’s performance.The comparison uses K = 2, B = 8, and a memory-order-1 convolutional encoder; exact MAP is evaluated by exhaustive enumeration of terminated histogram paths.Source: A. Validation of the Log-Max… · p. 10

B. Performance of Computational Free Distance Optimization

  • Table I summarizes computational free distance and NMSE gain across encoder and modulation configurations.The reported results are framed as computational-free-distance optimization and resulting NMSE improvement.Source: B. Performance of Computational Free… · p. 10, Table I · p. 11
  • A larger computational free distance generally accompanies improved NMSE by increasing separation between computationally distinct paths and reducing incorrect sum-sequence selection.The NMSE gain depends on encoder, modulation order, and operating SNR; when the optimized ratio is ρ̂ = 1, neither distance nor NMSE improves.Source: B. Performance of Computational Free… · p. 11

C. Performance of System Parameters

Across the tested digital AirComp comparisons, HiCoMAC has lower NMSE than Repetition ChannelComp and ReMAC as SNR rises, while FSJD is more robust at low SNR and HiCoMAC is more accurate at high SNR. System-parameter results show that quantization precision sets the high-SNR error floor, and histogram states reduce decoder branch evaluations as user count grows.

C. Performance of System Parameters

  • For 4QAM and 16QAM, NMSE approaches a quantization-error floor at high SNR, with larger B yielding a lower floor.At intermediate SNR, decoding errors can dominate; above 9 dB in the reported 4QAM setting, decoding errors are gradually suppressed.Source: C. Performance of System Parameters · p. 11
  • With K = 2, rate R = 1/4 achieves lower NMSE than R = 1/2 from approximately 3 to 12 dB, and above approximately 12 dB the curves approach quantization-dependent floors.The reported comparison also notes that higher-order 16QAM can increase separation between computationally distinct aggregated signal paths under the same energy budgets.Source: C. Performance of System Parameters · pp. 11–12
  • With K ∈ {2, 3, 4, 5}, NMSE tends to decrease as user count increases at higher SNR, approaching a quantization-determined floor that decreases approximately as 1/K.Minor curve crossings occur at low SNR in the reported setting.Source: C. Performance of System Parameters · p. 12, Figure 10 · p. 12

D. Comparison with Existing Digital AirComp Methods

  • At high SNR, HiCoMAC achieves higher computation accuracy than FSJD, while FSJD is more robust at low SNR; as SNR increases, HiCoMAC also has lower NMSE than Repetition ChannelComp and ReMAC.Source: D. Comparison with Existing Digital… · p. 12

E. Complexity Analysis

  • The histogram-state decoder processes CH histogram transitions per stage rather than the joint decoder’s (2N)^K transitions, and the gap grows with K, particularly for larger encoder memory.Permutation invariance lets one histogram transition represent multiple joint full-state transitions, substantially reducing online branch evaluations.Source: E. Complexity Analysis · p. 12

VII. CONCLUSION

  • HiCoMAC combines convolutional-coded arithmetic-sum recovery with histogram-state Viterbi decoding and computational-free-distance-based modulation design; simulations report improved free distance and NMSE alongside reduced decoding complexity.The conclusion identifies imperfect channel compensation, heterogeneous encoders, and reducing offline product-graph complexity as future work.Source: §VII · p. 12

APPENDIX

The appendix supports the histogram-transition count through a generating-function argument and the computational-free-distance result through a correspondence between irreducible error events and modified product-graph paths.

A. Proof of Proposition 1

  • The outgoing histogram-edge count is obtained by counting feasible input-count vectors and extracting the coefficient of x^K from (1 − x)^−2N.The proof uses the generalized binomial expansion to complete the count.Source: A. Proof of Proposition 1 · pp. 12–13

B. Proof of Theorem 1

  • Each irreducible computational error event maps to a modified product path, and conversely, supporting the shortest-path characterization through candidate edge sets.For a fixed modified path, its minimum distance is computed from the candidates sharing each modified edge’s endpoints.Source: B. Proof of Theorem 1 · p. 13
Loading 2609.34808v1…