A Novel Channel Coding Scheme for Digital Multiple Access Computing
Xiaojing Yan Saeed Razavikia Carlo Fischione







[LTE-Advanced]
  2GSecond Generation
  3-DAP3-Dimensional Assignment Problem
  3G3^rd Generation
  3GPP3^rd Generation Partnership Project
  4G4^th Generation
  5G5^th Generation
  AAAntenna Array
  ACAdmission Control
  ADAttack-Decay
  ADCanalog-to-digital converter
  ADMMalternating direction method of multipliers
  ADSLAsymmetric Digital Subscriber Line
  AHWAlternate Hop-and-Wait
  AirCompover-the-air computation
  AMCAdaptive Modulation and Coding
  ANNartificial neural network
  APAaccess Ppoint
  APAAdaptive Power Allocation
  ARMAAutoregressive Moving Average
  ARQAautomatic Rrepeat Rrequest
  ATESAdaptive Throughput-based Efficiency-Satisfaction Trade-Off
  AWGNadditive white Gaussian noise
  BAABbroadband Aanalog Aaggregation
  BBBranch and Bound
  BCDblock coordinate descent
  BDBlock Diagonalization
  BERBit Error Rate
  BFBest Fit
  BFDbidirectional full duplex
  BLERBLock Error Rate
  BPCBinary Power Control
  BPSKBinary Phase-Shift Keying
  BRABalanced Random Allocation
  BSbase station
  BSUMblock successive upper-bound minimization
  CAPCombinatorial Allocation Problem
  CAPEXCapital Expenditure
  CBFCoordinated Beamforming
  CBRConstant Bit Rate
  CBSClass Based Scheduling
  CCCongestion Control
  CDFCumulative Distribution Function
  CDMACode-Division Multiple Access
  CECchannel Eestimation
  CLClosed Loop
  CLPCClosed Loop Power Control
  CMLcentralized machine learning
  CNRChannel-to-Noise Ratio
  CNNCconvolutional Nneural Nnetwork
  CPcomputation point
  CPACellular Protection Algorithm
  CPICHCommon Pilot Channel
  CoCoACcommunication efficient distributed dual Ccoordinate Aascent
  CoMACCcomputation over Mmultiple-Aaccess Cchannels
  CoMPCoordinated Multi-Point
  CQIChannel Quality Indicator
  CRMConstrained Rate Maximization
	CRNCognitive Radio Network
  CSCoordinated Scheduling
  CSICchannel Sstate Iinformation
  CSMACcarrier Ssense Mmultiple Aaccess
  CUECellular User Equipment
  D2Ddevice-to-device
  DACdigital-to-analog converter
  DCdirect current
  DCADynamic Channel Allocation
  DEDifferential Evolution
  DFTDiscrete Fourier Transform

  DISTDistance
  DLdownlink
  DMADouble Moving Average
  DMLDistributed Machine Learning
  DMRSdemodulation reference signal
  D2DMD2D Mode
  DMSD2D Mode Selection
  DPCDirty Paper Coding
  DRADynamic Resource Assignment
  DSADynamic Spectrum Access
  DSGDDdistributed Sstochastic Ggradient Ddescent
  DSMDelay-based Satisfaction Maximization
  ECCElectronic Communications Committee
  EFLCError Feedback Based Load Control
  EIEfficiency Indicator
  eNBEvolved Node B
  EPAEqual Power Allocation
  EPCEvolved Packet Core
  EPSEvolved Packet System
  E-UTRANEvolved Universal Terrestrial Radio Access Network
  ESExhaustive Search
  
  FCFfusion Ccenter
  FDFfederated Ddistillation
  FDDfrequency divisionov duplex
  FDMFrequency Division Multiplexing
  FDMAFfrequency Ddivision Mmultiple Aaccess
  FedAvgFfederated Aaveraging
  FERFrame Erasure Rate
  FFFast Fading
  FLfederated learning
  FSBFixed Switched Beamforming
  FSTFixed SNR Target
  FTPFile Transfer Protocol
  GAGenetic Algorithm
  GBRGuaranteed Bit Rate
  GLRGain to Leakage Ratio
  GOSGenerated Orthogonal Sequence
  GPLGNU General Public License
  GRPGrouping
  HARQHybrid Automatic Repeat Request
  HDhalf-duplex
  HMSHarmonic Mode Selection
  HOLHead Of Line
  HSDPAHigh-Speed Downlink Packet Access
  HSPAHigh Speed Packet Access
  HTTPHyperText Transfer Protocol
  ICMPInternet Control Message Protocol
  ICIIntercell Interference
  IDIdentification
  IETFInternet Engineering Task Force
  ILPInteger Linear Program
  JRAPAPJoint RB Assignment and Power Allocation Problem
  UIDUnique Identification
  IIDIindependent and Iidentically Ddistributed
  IIRInfinite Impulse Response
  ILPInteger Linear Problem
  IMTInternational Mobile Telecommunications
  INVInverted Norm-based Grouping
  IoTInternet of Things

  IPInteger Programming
  IPv6Internet Protocol Version 6
  ISDInter-Site Distance
  ISIInter Symbol Interference
  ITUInternational Telecommunication Union
  JAFMjoint assignment and fairness maximization
  JAFMAjoint assignment and fairness maximization algorithm
  JOASJoint Opportunistic Assignment and Scheduling
  JOSJoint Opportunistic Scheduling
  JPJoint Processing
	JSJump-Stay
  KKTKarush-Kuhn-Tucker
  L3Layer-3
  LACLink Admission Control
  LALink Adaptation
  LCLoad Control
  LDCLlearning-Ddriven Ccommunication
  LOSline of sight
  LPLinear Programming
  LTELong Term Evolution
	LTE-ALTE-Advanced
  LTE-AdvancedLong Term Evolution Advanced
  M2MMachine-to-Machine
  MACmultiple access channel
  MANETMobile Ad hoc Network
  MCModular Clock
  MCSModulation and Coding Scheme
  MDBMeasured Delay Based
  MDIMinimum D2D Interference
  MFMatched Filter
  MGMaximum Gain
  MHMulti-Hop
  MIMOMmultiple Iinput Mmultiple Ooutput
  MINLPmixed integer nonlinear programming
  MIPmixed integer programming
  MISOmultiple input single output
  MLmachine learning
  MLEmaximum likelihood estimator
  MLWDFModified Largest Weighted Delay First
  MMEMobility Management Entity
  MMSEminimum mean squared error
  MOSMean Opinion Score
  MPFMulticarrier Proportional Fair
  MRAMaximum Rate Allocation
  MRMaximum Rate
  MRCMaximum Ratio Combining
  MRTMaximum Ratio Transmission
  MRUSMaximum Rate with User Satisfaction
  MSMode Selection
  MSEMmean Ssquared Eerror
  MSIMulti-Stream Interference
  MTCMachine-Type Communication
  MTSIMultimedia Telephony Services over IMS
  MTSMModified Throughput-based Satisfaction Maximization
  MU-MIMOMulti-User Multiple Input Multiple Output
  MUMulti-User
  NASNon-Access Stratum
  NBNode B
	NCLNeighbor Cell List
  NLPNonlinear Programming
  NLOSnon-line of sight
  NMSEnormalized mean square error
  NOMANnon-Oorthogonal Mmultiple Aaccess
  NORMNormalized Projection-based Grouping
  NPnon-polynomial time
  NRTNon-Real Time
  NSPSNational Security and Public Safety Services
  O2IOutdoor to Indoor
  OFDMAOorthogonal Ffrequency Ddivision Mmultiple Aaccess
  OFDMOrthogonal Frequency Division Multiplexing
  OFPCOpen Loop with Fractional Path Loss Compensation
	O2IOutdoor-to-Indoor
  OLOpen Loop
  OLPCOpen-Loop Power Control
  OL-PCOpen-Loop Power Control
  OPEXOperational Expenditure
  ORBOrthogonal Random Beamforming
  JO-PFJoint Opportunistic Proportional Fair
  OSIOpen Systems Interconnection
  PAIRD2D Pair Gain-based Grouping
  PAPRPeak-to-Average Power Ratio
  P2PPeer-to-Peer
  PCPower Control
  PCIPhysical Cell ID
  PDCCHphysical downlink control channel
  PDDpenalty dual decomposition
  PDFProbability Density Function
  PERPacket Error Rate
  PFProportional Fair
  P-GWPacket Data Network Gateway
  PLPathloss
  RLTreformulation linearization technique
  PRBPhysical Resource Block
  PROJProjection-based Grouping
  ProSeProximity Services


  PSPparameter Sserver
  PSOParticle Swarm Optimization
  PUCCHphysical uplink control channel
  PZFProjected Zero-Forcing
  QAMquadrature amplitude modulation
  QoSquality of service
  QPSKquadrature phase shift keying
  QCQPquadratically constrained quadratic programming
  RAISESReallocation-based Assignment for Improved Spectral Efficiency and Satisfaction
  RANRadio Access Network
  RAResource Allocation
  RATRadio Access Technology
  RATERate-based
  RBresource block
  RBGResource Block Group
  REFReference Grouping
  ReLUrectified linear unit
  RFradio frequency
  RLCRadio Link Control
  RMRate Maximization
  RNCRadio Network Controller
  RNDRandom Grouping
  RRARadio Resource Allocation
  RRMRradio Rresource Mmanagement
  RSCPReceived Signal Code Power
  RSRPreference signal receive power
  RSRQReference Signal Receive Quality
  RRRound Robin
  RRCRadio Resource Control
  RSSIreceived signal strength indicator
  RTReal Time
  RUResource Unit
  RUNERUdimentary Network Emulator
  RVRandom Variable
  SAASmall Argument Approximation
  SACSession Admission Control
  SCMSpatial Channel Model
  SC-FDMASingle Carrier - Frequency Division Multiple Access
  SDSoft Dropping
  S-DSource-Destination
  SDPCSoft Dropping Power Control
  SDMASpace-Division Multiple Access
  SDRsemidefinite relaxation
  SDPsemidefinite programming
  SERSymbol Error Rate
  SESSimple Exponential Smoothing
  S-GWServing Gateway
  SGDSstochastic Ggradient Ddescent  
  SINRsignal-to-interference-plus-noise ratio

  SIself-interference
  SIPSession Initiation Protocol
  SISOSsingle Iinput Ssingle Ooutput
  SIMOSingle Input Multiple Output
  SIRSignal to Interference Ratio
  SLNRSignal-to-Leakage-plus-Noise Ratio
  SMASimple Moving Average
  SNRSsignal-to-Nnoise Rratio
  SORASatisfaction Oriented Resource Allocation
  SORA-NRTSatisfaction-Oriented Resource Allocation for Non-Real Time Services
  SORA-RTSatisfaction-Oriented Resource Allocation for Real Time Services
  SPFSingle-Carrier Proportional Fair
  SRASequential Removal Algorithm
  SRSsounding reference signal
  SU-MIMOSingle-User Multiple Input Multiple Output
  SUSingle-User
  SVDSingular Value Decomposition
  SVMSsupport Vvector Mmachine
  TCPTransmission Control Protocol
  TDDtime division duplex
  TDMATtime Ddivision Mmultiple Aaccess
  TNFDthree node full duplex
  TETRATerrestrial Trunked Radio
  TPTransmit Power
  TPCTransmit Power Control
  TTItransmission time interval
  TTRTime-To-Rendezvous
  TSMThroughput-based Satisfaction Maximization
  TUTypical Urban
  UEUuser Eequipment
  UEPSUrgency and Efficiency-based Packet Scheduling
  ULuplink
  UMTSUniversal Mobile Telecommunications System
  URIUniform Resource Identifier
  URMUnconstrained Rate Maximization
  VRVirtual Resource
  VoIPVoice over IP
  WANWireless Access Network
  WCDMAWideband Code Division Multiple Access
  WFWater-filling
  WiMAXWorldwide Interoperability for Microwave Access
  WINNERWireless World Initiative New Radio
  WLANWireless Local Area Network
  WMMSEweighted minimum mean square error
  WMPFWeighted Multicarrier Proportional Fair
  WPFWeighted Proportional Fair
  WSNWireless Sensor Network
  WWWWorld Wide Web
  XIXO(Single or Multiple) Input (Single or Multiple) Output
  ZFZero-Forcing
  ZMCSCGZero Mean Circularly Symmetric Complex Gaussian










theoremTheorem
propProposition
lemLemma




A Novel Channel Coding Scheme 
 for Digital Multiple Access Computing




    Xiaojing Yan, Saeed Razavikia, Carlo Fischione

	School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Stockholm, Sweden

	Email: {xiay, sraz, carlofi}@kth.se

    Accepted XXX, Received YYY; in original form ZZZ
=======================================================================================================================================================================================================

empty
empty



In this paper, we consider the ChannelComp framework, which facilitates the computation of desired functions by multiple transmitters over a common receiver using digital modulations across a multiple access channel. While ChannelComp currently offers a broad framework for computation by designing digital constellations for over-the-air computation and employing symbol-level encoding, encoding the repeated transmissions of the same symbol and using the corresponding received sequence may significantly improve the computation performance and reduce the encoding complexity. In this paper, we propose an enhancement involving the encoding of the repetitive transmission of the same symbol at each transmitter over multiple time slots and the design of constellation diagrams, with the aim of minimizing computational errors. We frame this enhancement as an optimization problem, which jointly identifies the constellation diagram and the channel code for repetition, which we call ReChCompCode. To manage the computational complexity of the optimization, we divide it into two tractable subproblems. Through numerical experiments, we evaluate the performance of ReChCompCode. The simulation results reveal that ReChCompCode can reduce the computation error by approximately up to 30 dB compared to standard ChannelComp, particularly for product functions. 



Over-the-air computation, channel coding, digital communication, digital modulation  




§ INTRODUCTION




The rise of IoT-centric applications increases the demand for reliable and spectrum-efficient wireless protocols to gather data from distributed smart devices. A notable strategy to enhance spectral efficiency is AirComp <cit.>. AirComp is an analog communication scheme that concurrently allocates all devices over the same frequency resources and leverages the inherent waveform superposition of wireless signals. AirComp has shown its effectiveness in supporting machine learning services <cit.>. Specifically, integrating federated learning with AirComp turns out to be promising in resource-constrained settings, often yielding superior model outcomes due to diverse device knowledge.

Nonetheless, the dependency of AirComp on analog modulations raises questions about its suit for present-day IoT applications <cit.>. The analog communication lacks an effective noise countermeasure, merely diminishing the estimation error, which compromises its reliability <cit.>. Addressing these analog communication challenges, a digital computation framework named ChannelComp has been introduced in <cit.>. This method, which constitutes a paradigm shift compared to AirComp, is a framework for general function computation over MAC using digital modulations <cit.>. 


Standard digital communications rely on channel coding to ensure robust communication, embedding redundant information to compensate channel noise <cit.>. In the AirComp's literature, the primary methodology centers on nested lattice codes' linearity <cit.>. This enables computations over Gaussian channels. A nested lattice coding-based computation scheme further reinforces function computation against noise <cit.>. Yet, such codes, including the coded AirComp tailored for federated learning model aggregation <cit.>, are constrained to simple digital modulations, such as ASK, and do not generalize in terms of modulation formats or function computations.



In this paper, we propose repetition of the transmissions and an associated channel coding scheme for the ChannelComp framework to provide a reliable and spectral-efficient communication strategy. To reduce the computation error, we design both the digital constellation and the coding of the repeated symbol sequence, where we call the resulting code ReChCompCode. Specifically, we propose the conditions for a valid function computation, which leads to an optimization problem to determine the constellation diagram of digital modulation over the time slots. The proposed optimization problem involves the parameters of both channel and source codes. To handle the complexity, we decompose the problem into two subproblems. The first subproblem becomes a SDP problem by relaxing non-convex constraints. The second subproblem turns into an MIP format <cit.>, manageable with the branch and bound method <cit.>. Finally, we assess the performance of ReChCompCode for providing a reliable computation through numerical experiments.














The remainder of this paper is structured as follows: Section  <ref> explains the system model for the function computation problem. Section <ref> describes the problem of the selection process for digital modulation formats, and Section <ref> proposes an efficient algorithm for accurate computation across the MAC. In Section <ref>, we present numerical experiments comparing the proposed ReChCompCode with ChannelComp and digital AirComp. Finally, Section <ref> concludes the paper and sketches future works.




 §.§ Notation


Bold lower-case letter x represents vector quantities, while bold upper-case letter X denotes matrices. The transpose and Hermitain of a matrix X are denoted by X^⊤ and X^𝖧, respectively. The Kronecker product is symbolized by ⊗, and the Hadamard product by ⊙. The notation X≽ 0 signifies that matrix X is positive semidefinite. Lastly, X_2 and X_ F represent the Euclidean norm and Frobenius norm of a matrix. For an integer N, we show set {1,2,…,N} by [N].






§ SYSTEM MODEL











We consider a network comprising a CP and K nodes transmitting over a shared communication channel. The main goal is to compute a function f(x_1, …, x_K), where x_k ∈ℝ represents the input value generated by node k. All nodes use digital modulation for transmitting their values over the MAC. In particular, node k initially quantizes its value x_k into x̃_k=𝒬(x_k) ∈𝔽_Q using quantizer 𝒬(·), in which 𝔽 represents a finite field with  Q different values. Afterward, the resultant value x̃_k is mapped into a digital modulation signal (complex domain) using a modulation encoder ℰ_k(·): 𝔽_Q ↦ℂ, resulting in x⃗_k = ℰ_k(x̃_k) ∈ℂ. In this context, the values x_1, …, x_K are selectively retransmitted L times, each within a designated time slot. Thus, in parallel, the quantized value x̃_k goes through channel encoder via 𝒞: 𝔽_Q ↦𝔽_2^L, generating a length L binary sequence. This sequence serves as an indicator that x̃_k is allocated to one or more time slots, i.e., 𝐜̃_k = 𝒞_k(x̃_k) ∈{0,1}^L.  Subsequently, the modulated signals x⃗_k's are simultaneously transmitted within the assigned time slot over the MAC[We assumed that all the nodes and the CP are perfectly synchronized. Note that the existing techniques of analog AirComp for addressing poor synchronization, e.g., <cit.>, <cit.>, can be applied to digital AirComp model as well.]. The CP receives the superposition  of the transmitted signals at each time slot, i.e.,


    y⃗_ℓ = ∑_k=1^K h_k,ℓp_k,ℓx⃗_k·c̃_k,ℓ+z⃗_ℓ,  ∀ ℓ∈ [L],


where c̃_k,ℓ denotes element ℓ of vector 𝐜̃_k, and
h_k,ℓ∈ℂ is the channel attenuation between node k and CP at time slot ℓ. It is assumed that the wireless channel remains unchanged within every time slot. Also, p_k,ℓ is the transmit power of node k at time slot ℓ, and z⃗_ℓ denotes the AWGN with zero-mean and variance σ_z^2 for time slot ℓ. 


According to the optimal power control policy suggested by AirComp literature <cit.>, we consider the selection of transmit power as
the inverse of the channel, i.e., p_k,ℓ=h_k,ℓ^*/|h_k,ℓ|^2. Note that insufficient power nodes would only result in weaker signal strength.  With this, we can express (<ref>) as follows:


    y⃗_ℓ = ∑_k=1^Ks⃗_k,ℓ + z⃗_ℓ,   ∀ ℓ∈ [L],


 where s⃗_k,ℓ:=  x⃗_k ·c̃_k,ℓ denotes the transmitted signal at time slot ℓ by node k for ℓ∈ [L] and k∈ [K].  Because every transmitted  s⃗_k,ℓ possesses finite possible constellation points, the received signal y⃗_ℓ acquires a finite constellation diagram. To compute the desired function f, we employ a Tabular mapping 𝒯 on the sequence of y⃗_1, …, y⃗_L to obtain the corresponding output.  The entire procedure of this channel computing coding is illustrated in Fig. <ref>.

In the next section, we design encoders and decoders to enable performing the computation of the desired function f over the MAC. 









§ PROBLEM FORMULATION




This section introduces the proposed channel computing code termed ReChCompCode, which enables robust computation over the MAC. 

Towards acquiring a robust and efficient computation, we need to jointly design modulation encoder ℰ_k and channel encoder 𝒞_k for all users k ∈ [K] to avoid any destructive overlaps of constellation points in the receiver side. Therefore, the tabular function 𝒯 can uniquely map the constellation points of  y_1, …, y_L to the corresponding outputs of the function f. Specifically, consider a noiseless MAC. Then, let f^(i) and f^(j) be two output values from the range of function f(x_1,…,x_K) for two sets of input values x_1^(i),…,x_K^(i) and  x_1^(j),…,x_K^(j), respectively. 
Then, the induced constellation points at time slot ℓ can be expressed by v_ℓ^(i):= ∑_ks⃗_k,ℓ^(i)
and v_ℓ^(j):= ∑_ks⃗_k,ℓ^(j). To have a valid computation, the sequence of the induced points v^(i):=[v_1^(i),…,v_L^(i)] and v^(j):=[v_1^(j),…,v_L^(j)] need to satisfy the following constraint <cit.>:

    if  f^(i)≠ f^(j) ⇒ v^(i)≠v^(j),  ∀ (i,j)∈ [M]^2,

where [M]^2 = [M]× [M] is the Cartesian product and  M is the cardinality of the range of function f. The constraint in (<ref>) ensures that the tabular function 𝒯 can correctly map v^(i) to output value f^(i) based on the design of ℰ_k and 𝒞_k. Therefore,  the problem formulation involves designing the constellation points in a way that ensures condition (<ref>) is satisfied.




 §.§ Illustrative Example



For better insight, we illustrate the mechanism by a simple case. Consider a network involving K=4 nodes, where they employ a simple digital modulation, such as quadrature phase shift keying modulation, to compute the product function, i.e.,  f(x_1,x_2,x_3,x_4) = x_1x_2x_3x_4 over L=2 time slots. The input value x_k ∈{1, 2, 3, 4} is quantized into a two-bit representation, denoted as x̃_k ∈{00, 01, 10, 11}. Each quantized value can be encoded as x⃗_k ∈{1,-1,i,-i}. In the case of a noiseless MAC, when the four nodes transmit the same signals in both time slots, a conflict occurs at point 0 in the constellation, where point 0 corresponds to three different output values, i.e., {4,24,144}.  However, this overlapping can be avoided by performing the computation over two separate time slots using the channel encoder defined as follows. 


    c̃_k,0 = {
    1,      if x̃_k ∈{00,10}
    
    0,      if x̃_k ∈{01,11}.  
    
    ,c̃_k,1 = {
    0,      if x̃_k ∈{00,10}
    
    1,      if x̃_k ∈{01,11}.



Table <ref> provides an explicit comparison. As the received signals y⃗_ℓ = ∑_k=1^Kx⃗_k·c̃_k,ℓ for ℓ∈{1,2} are distinct over time slots, the corresponding function outputs can be distinguished by using a tabular function 𝒯.



In the following subsection, we propose an optimization problem to jointly design the modulation encoder and channel computing encoder for a general function computation. 







































 §.§ ReChCompCode Design


In the following discussion, we will use matrix notation to represent points in the function domain for improved clarity. For each node k, we define  x_k := [x_k^(1),…,x_k^(Q)]^𝖳∈ℂ^Q × 1 as modulation vector containing all Q possible constellation points created by the modulation encoder ℰ_k(·). Similarly, the channel matrix of node k can be defined as C_k ∈{0,1}^L× Q whose [C_k]_(ℓ,q) := c_k,ℓ^(q)∈{0,1} denotes  whether the modulated signal x_k^(q) is transmitted in time slot ℓ. We further define  x := [x_1^𝖳, …, x_K^𝖳]^𝖳∈ℂ^N × 1 and the block matrix C := [C_1, …, C_K]^𝖳∈{0,1}^N × L, where N:= Q K.  Then, all the possible transmitted signals can be expressed by S: = X⊙C, in which X = x⊗1_L^𝖳∈ℂ^N× L and 1_L is a L× 1 column vector of 1s. As a result, we can express all possible constellation points over the MAC for all L time slots as 


    V = AS∈ℂ^M × L,


where A∈{0, 1}^M × N is a binary matrix whose i-th row is a binary vector with the same support as input values corresponding to f^(i). Indeed, A selects elements of S such that column ℓ of matrix V consists of all possible constellation points experienced by the CP at time slot ℓ. 

To hold an error-free computation over the MAC, the necessary and sufficient condition is to have distinct sequences of constellation points for corresponding different function output values. In particular, for a pair f^(i) and f^(j), the resulting vectors v^(i) and v^(j) must satisfy the following constraint:


    v^(i) - v^(j)_2^2 ≥ϵ |f^(i) - f^(j)|^2,   ∀ (i,j)∈ [M]^2,


where v^(i)∈ℂ^L involves all L induced constellation points corresponding to f^(i), and ϵ is a positive constant that needs to be adjusted based on the input function values and the variance of the noise at the receiver as given in <cit.>. The inequality in (<ref>) ensures that resultant constellation points are distinguishable for tabular function 𝒯. Certainly, the modulation vector that can satisfy this constraint is not unique. To attain a robust and power-efficient channel computing coding, we pose the following optimization problem:


    𝒫_0 :=min_x,C      ||S||_ F
     s.t.      (a_i - a_j)^𝖳S_ F^2 ≥ϵ |f^(i) - f^(j)|^2,  
        (i,j) ∈ [M]^2,    x_2^2 ≤ P_max,


where a_i^𝖳 denotes the i-th row of matrix A and a_i^𝖳S = v^(i). Problem 𝒫_0 jointly optimize the modulation vector X and channel vector C while guaranteeing that computation constraint holds. By solving Problem 𝒫_0, we acquire the optimum X^* and C^*, thereafter, we obtain the modulation encoders ℰ_1(·), …, ℰ_K(·)  and channel encoders 𝒞_1(·), …, 𝒞_K(·), respectively, that map the input values to the resultant modulation vector and channel vector. 


From <cit.>, we note that  Problem 𝒫_0 is NP-hard due to the nonconvex quadratic constraints in (<ref>). Hence, we provide an efficient algorithm to compute an approximate solution in the next section.   




§ MODULATION AND CHANNEL CODING CO-DESIGN 



In this section, to find an approximate solution for Problem 𝒫_0, we first pose an alternating optimization problem, and then we solve it and analyze its optimality. Based on such a solution, we establish a receiver architecture for recovering the function output from the received constellation vector. 



 §.§ Approximate Solution via alternating Minimization 


The proposed optimization by Problem 𝒫_0 is an ill-posed problem due to the Hadamard product of X and C. To circumvent this, we approximate the objective function with the following upper bound:


    S_ F    =  X⊙C_ F≤X_ FC_ F,
       ≤1/2(X_ F^2 + C_ F^2) = 1/2( L x_2^2 + ∑_ℓ=1^Lc_ℓ_2^2),


where c_ℓ denotes column ℓ of matrix C for ℓ∈ [L].  Therefore, using (<ref>), we minimize the upper bound of the objective function in (<ref>) as follows

  

    𝒫_1 :=min_x,C      L||x||_2^2 + ∑_ℓ=1^L ||c_ℓ||^2_2  
    s.t.     ∑_ℓ=1^L |(a_i-a_j)^⊤(x⊙c_ℓ)|^2 ≥Δ f_i,j, 
         x_2^2 ≤ P_max,



where Δ f_i,j:=ϵ|f^(i)-f^(j)|^2 and the digital vector as x∈ℂ^N × 1 and the time slot vector as c_ℓ∈{0,1}^N × 1.

To explore the transmission efficiency, we can find the minimum value of total time slot L from Problem 𝒫_1.

For a given function f, to obtain a feasible solution for Problem 𝒫_1   satisfying the power constraint (<ref>), the number of time slots L must be greater than or equal to the following lower bound. 


    L_min≥max_i,jΔ f_i,j· N/P_max.






Given the lower bound L_min, we set a fixed value for L to solve Problem 𝒫_1. By using an alternating approach, Problem 𝒫_1 can be split into two subproblems by iteratively optimizing decision variables x and C. More precisely, given c_ℓ^(n-1) at iteration n,  we optimize over x in the following subproblem.



    x^(n)    = min_x Lx^2_2 
    s.t.    ∑_ℓ=1^L |(a_i-a_j)^⊤(x⊙c_ℓ^(n-1))|^2 ≥Δ f_i,j, 
         x_2^2 ≤ P_max.




For the variable c_ℓ,  we have


    c_ℓ^(n)    = min_c_ℓ ∑_ℓ=1^L||c_ℓ||^2_2 
    s.t.    ∑_ℓ=1^L |(a_i-a_j)^⊤(x^(n)⊙c_ℓ)|^2 ≥Δ f_i,j.



For the first subproblem in (<ref>), invoking the self-adjoint property of the Hadamard product, i.e., |x^⊤(y⊙z)|^2 = |(x⊙z)^⊤y|^2, we reformulate the constraint as:


    min_x       Lx^2_2   
    s.t.     ∑_ℓ=1^L |((a_i-a_j)⊙c_ℓ^(n-1))^⊤x|^2 ≥Δ f_i,j, 
         x_2^2 ≤ P_max.



The optimization problem in (<ref>) is a QCQP, which is non-convex and NP-hard <cit.>. One possible way to handle this problem is to use the lifting trick <cit.>, where the non-convexity appears as a rank constraint.  
In particular, we rewrite the problem in terms of a new lifted matrix variable W:= xx^𝖧 as (<ref>).  




    W^(n) = min_W      Tr(W)   
     s.t.      Tr(W·B_i,j^(n-1)) ≥Δ f_i,j,
       W≽0,    rank(W)=1,  
       Tr(𝐖) ≤ P_max,



where 
    B_i,j^(n-1)=∑_ℓ=1^L((a_i-a_j)⊙c_ℓ^(n-1))((a_i-a_j)⊙c_ℓ^(n-1))^⊤.
 Next, dropping the rank-one constraint in (<ref>), the optimization problem in (<ref>) becomes SDP and can be solved by convex solver tolls such as CVX <cit.>. After solving the SDP problem, x^(n) is obtained via Cholesky decomposition of W^(n) with rank one property. In case  W^(n) possess a rank higher than one, an approximate solution x^(n) can be recovered using the Gaussian randomization method <cit.>.

Similarly, for the subproblem in (<ref>), since c_ℓ is binary, the quadratic objective c_ℓ_2^2 is equivalent to a linear one as ∑_l=1^Lw^⊤c_ℓ, where w is 1_L. Moreover, using self-adjoint property of the Hadamard product, we can rewrite (<ref>) as 




    c_ℓ^(n) = min_c_ℓ     ∑_ℓ=1^Lw^⊤c_ℓ
     s.t.     ∑_ℓ=1^L|d_i,j^(n)𝖧c_ℓ|^2 ≥Δ f_i,j,


where d_i,j^(n): = (a_i - a_j) ⊙x^(n).  The optimization problem in (<ref>) is a MIP problem with linear objective and quadratic constraints. This category of problems can be solved through solvers like Gurobi <cit.> by using the branch and bound method <cit.>.
The entire procedure of the alternating minimization approach is summarized in Algorithm <ref>.


















 §.§ Optimality Analysis


We analyze the optimality of Algorithm <ref>, where we use an alternating minimization approach for solving Problem 𝒫_1. 
First, considering the QCQP problem in (<ref>), 
since the rank constraint is removed, the solution W^* is suboptimal. However, if W^* becomes a rank-one matrix, it is feasible to (<ref>), and in fact, optimal solution. 
In addition, the MIP problem in (<ref>) has non-convex quadratic constraints. By translating these quadratic constraints into bilinear ones, we can apply the reformulation linearization technique and an implicit enumeration strategy, and the global optimum can be obtained, as outlined in <cit.>. The convergence of the alternating minimization algorithm for the bilinear constraint is studied in <cit.>. Overall, by relaxing the objective function in Problem 𝒫_1, the final solution x^* and C^* serves as an approximate solution to Problem 𝒫_0.






 §.§ Designing Tabular Function





The tabular function 𝒯 is uniquely determined by the decision boundaries based on the reshaped constellation points over the MAC. Indeed,  the CP uses a set of constellation points v^(i) = [v⃗^(i)_1, …, v⃗^(i)_L]^𝖳∈ℂ^L × 1 to decode the function output f^(i), where v⃗_ℓ^(i)=∑_k=1^K x⃗_k·c̃_k,ℓ. Then, the problem becomes finding the corresponding points of v⃗^(i) when y is received. Following similar steps as in <cit.>, one can show the maximum likelihood estimator results in the problem below.


    f̂^(i)=min_i||y - v^(i)||_2^2.


The decoder generates the constellation diagram, which consists of all possible constellation points {v⃗_ℓ^(1),…,v⃗_ℓ^(M)} along with their corresponding Voronoi cells {𝒱_1,ℓ,…,𝒱_M,ℓ}. Each Voronoi cell contains the points in the signal space that are closer to a specific constellation point than to any other.
The desired function f̂ for all time slots is given by f̂=∑_j=1^M𝒯_j(v), where 𝒯_j(·) is an indicator function: 


    𝒯_j(v) := f̂^(j),      if v⃗_ℓ∈𝒱_j,ℓ, ℓ∈ [L], 
    
    0,      o.w.


For the points that the overlapping is not resolved, i.e., corresponding constraints in (<ref>) are not satisfied, their Voronoi cells merge into one Voronoi cell, and the decoder has to assign only one number as the output of two different output values for the desired functions, e.g., the average of output values corresponding to the Voronoi cells <cit.>.  

In the next section, we check the performance of the proposed ReChCompCode over the MAC. 






§ NUMERICAL EXPERIMENTS



In this section, we assess the performance of ReChCompCode for computing different functions over the MAC. Moreover, we make a comparison of the ReChCompCode with ChannelComp <cit.> and the retransmission strategy for digital AirComp proposed in <cit.>. More precisely, we use a naive repetition strategy for the ChannelComp <cit.> and AirComp, where the CP average the received signal over multiple transmission as the estimation value for the output of the function.    




 §.§ Performance of ReChCompCode







For the first experiment, we consider a network of K=4 nodes for computing the product function f=∏_k=1^Kx_k and max function f=max_kx_k, where x_k∈{0,1,…,3}.  We make the comparison in terms of the NMSE metric, NMSE:=∑_j=1^N_s|f^(i)-f̂_j^(i)|^2/(N_s|f^(i)|), defined as the sum of squared differences between desired function values f^(i) and their estimated counterparts f̂_j^(i) divided by N_s times the absolute value of f^(i), where N_s is the number of Monte Carlo trials. Since L=2 is enough to resolve the overlaps for given functions, we run the optimization problem in  (<ref>) for L=2. Then, we repeat the pattern several times for transmission more than L>2.


Fig. <ref> and Fig. <ref> show the NMSE of the function computation for the product and max functions, respectively over different SNR levels, which is defined as SNR:=20log(x_2/σ_z). We observe a monotonic reduction in NMSE for computing both functions. Especially within the SNR range of  5 dB to 25 dB, repetition yields rapid reduction results, which shows the effectiveness of the ReChCompCode method in concealing the channel noise.



 §.§ Comparison to AirComp and ChannelComp


This subsection compares the  ReChCompCode method to AirComp and ChannelComp. Specifically, we evaluate the ReChCompCode approach using two critical functions: summation and product functions denoted as f=∑_k=1^4x_k, and f=∏_k=1^4x_k, respectively. Here, the parameter x_k takes values from the set {0, 1, …, 7}, and the evaluation is carried out over a network comprising K=4 nodes. To ensure a fair comparison, we allocate the same power budget overall time slots, L× P_ max, for all the methods. 



Fig. <ref> and Fig. <ref> depict that NMSE value for computing the summation and the product functions over different time slots L, respectively. ReChCompCode performs better than both AirComp and ChannelComp in terms of NMSE. In particular, ReChCompCode and ChannelComp show similar performance for computing the summation function. When computing the product function, since AirComp approximates the product using the log function <cit.>, it cannot compute accurately even in high SNR scenarios. Additionally, due to the co-design of the channel code with constellation points, ReChCompCode achieves better performance than ChannelComp, which has already been proven to outperform OFDM <cit.>. Notably, ReChCompCode reduces the computation error by approximately 30 dB in NMSE compared to ChannelComp for the product function with 100 time slots. 






§ CONCLUSION


This paper introduced ReChCompCode, a channel code for repetition in digital over-the-air computation to provide a reliable communication protocol. Building upon the ChannelComp framework, we designed the channel coding scheme to reduce the computation error over MAC. To this end, we proposed an optimization problem that jointly determines the encoding for digital modulation over multiple time slots. To manage the computational complexity of the proposed optimization problem, we developed an alternating minimization technique. Moreover, we evaluated the effectiveness of ReChCompCode through the numerical experiment by comparing it to existing state-of-the-art methods, such as digital AirComp and ChannelComp. Notably, we observed approximately 30 dB improvement in reducing the NMSE of the computation error of the product function with 100 time slots.

Looking forward, we plan to further study the convergence of the alternating minimization problem. Considering the challenge posed by its NP-hard complexity, we're also eager to explore simpler solutions. Notably, we anticipate demonstrating the substantial impact of this channel computing coding approach on applications such as federated edge learning. Additionally, we want to evolve from the current single antenna setup to a more comprehensive configuration with multiple inputs and outputs.

IEEEtran










 §.§ Proof of Proposition <ref>




We recall the constraints from the optimization problem in (<ref>) as

    ∑_ℓ=1^L |(a_i-a_j)^⊤(x⊙c_ℓ)|^2 ≥Δ f_i,j,
 
for all (i,j) ∈ [M]^2. Using Hölder Inequality <cit.>, we can bound the absolute value of the inner product as follows.


    |(a_i-a_j)^⊤(x⊙c_ℓ)|^2    ≤a_i-a_j^2_1 ·x⊙c_ℓ^2_∞
       ≤a_i-a_j^2_1 ·x^2_∞·c_ℓ^2_∞
       ≤a_i-a_j^2_1 P_ max.


Since the minimum distance between a_i and a_j is 1, by summing over all L terms, we reach to


    ∑_ℓ=1^L |(a_i-a_j)^⊤(x⊙c_ℓ)|^2    ≤∑_ℓ=1^La_i-a_j^2_1 ·x^2_∞·c_ℓ^2_∞
       ≤P_max/N· L.


By substituting (<ref>) into (<ref>), we obtain the lower bound of L as follows. 


    L_min≥max_i,jΔ f_i,j· N/P_max.


This concludes the proof. 
