is encoded into n bits codeword x=[v.0,..,v.n-1]of Sourceword-sumz和 channel codes.The channel codes adopted here are systematic ∑ek,(au+w1) low-density parity check (LDPC)codes [16].For each k bits Sourceword-sum z1 ∑ey(a+e1) sourceword bo,it is appended with n-k parity bits provided Sourceword-sum z2 by LDPC codes encoder,and form the n bits codeword x. ∑.e月n+1) To enable PhyArith,we require the quantized update vector Sourceword-sum到- chunks transmitted simultaneously share the same LDPC dd up and codes codebook,i.e.,the mapping from b to x should be eed update vector chun the same for different client v.Besides,for modulation,the vector chank mapping from x to s=[sv.0,....so.m-1]should be the same as well. Averaged update vector At D.Compatibility with Commodity 802.11 Devices Fig.4.Decoding process of server In 802.1lax,similar with PhyArith,systematic LDPC codes are taken for error correction.For fixed coding rate,the code- A.Building of the Factor-Graph book mapping from scrambled sourceword to LDPC codes codeword is fixed.Besides,for fixed modulation,the mapping We first show how to directly decode each sourceword- sum zi based on the superimposed RF signal.Let y;= from codeword to symbols transmitted in the same time- frequency resource is also fixed.As a conclusion,the encoding be the j-th observation vector.The process of 802.1lax is fully compatible with PhyArith.That decoding problem here can be formulated as the following optimization problem is,we can directly use commodity single antenna 802.1lax devices to send the sourceword b of PhyArith via a raw z,…,z-1 socket,where the channel codes related process is provided =ag,maxP(z0,·,z4y-1yo,·,ym-1) (5) by 802.1lax devices. z0,…,zy1-1 Since jointly optimize zo,...,z-1 is too complicated to VII.DECODING PROCESS OF PHYARITH solve.We can relax(5)as follows In this section,we demonstrate the decoding process of zij=arg max P(zi.jlyo,..ym-1), PhyArith.Limited by the decoding complexity,client set V in PhyArith is randomly partitioned into subsets V= where the marginal probability can be written as the following {V6,…,v-i}first,where VVi∈y,lVA≤△and△is sum-product form via factorization the subset size limit.Then,as shown in Fig.4,based on the superimposed RF signal,PhyArith directly decodes the P(2,ly0,…,ym-1 sourceword-sum of each subset Vi,which is denoted by = ∑P(yo,…,ym-1,z0,…,z4-1)/P(yo,…,ym-1) w24,3 z1=[,0…,2.k-il=ab A∑[P(yo,…,ym-ilso…,s-i) w24.d where B.,is an odd integer given by v1-1 ΠIΠIs,x,b6∑a,b。-zrlh】 B+1,with probability 1/2, i'=0 vEV UEV (6 6n·2-1,0.w. Here denotes all random variables exceptz and is a randomly chosen integer ensuring Vo E V,B.. I(sv,x,b)is the indicator function to ensure x is a valid 2f∈N,B,·2s≥l.For these obtained sourceword-sumz: LDPC codes codeword encoded from be,and su is a valid verified to be correct,the summation of update vector chunks symbol sequence modulated from x.And 6()denotes the of Vi,i.e..v(B+),is recovered.And for these Dirac delta function. Zi verified to be incorrect,retransmission is requested.Finally, A general method to efficiently obtain the marginal prob- all these recovered summations can be added up and averaged, ability of each zi;is the factor-graph based sum-product then assembled into the averaged update vector At,given by algorithm [18],which operates in a message-passing man- ner.Specifically,while=2,the factorization (6)can A,=[…,∑a+1/W,…] be visualized by a factor-graph,a kind of bipartite graph ViEV vEV like Fig.5,which consists of two kind of nodes.One is called variable node (denoted by circles),representing random Note that here we let each B be a large odd integer to facilitate variables,and the other is called check node (denoted by the verification of zi in Section VII-C,and make sure the squares),representing the local functions of variables.By recovered v1)is accurate in Section VII-D. exchanging messages in the form of probability mass functionis encoded into n bits codeword xv = [xv,0, · · · , xv,n−1] of channel codes. The channel codes adopted here are systematic low-density parity check (LDPC) codes [16]. For each k bits sourceword bv, it is appended with n−k parity bits provided by LDPC codes encoder, and form the n bits codeword xv. To enable PhyArith, we require the quantized update vector chunks transmitted simultaneously share the same LDPC codes codebook, i.e., the mapping from bv to xv should be the same for different client v. Besides, for modulation, the mapping from xv to sv = [sv,0, · · · , sv,m−1] should be the same as well. D. Compatibility with Commodity 802.11 Devices In 802.11ax, similar with PhyArith, systematic LDPC codes are taken for error correction. For fixed coding rate, the code￾book mapping from scrambled sourceword to LDPC codes codeword is fixed. Besides, for fixed modulation, the mapping from codeword to symbols transmitted in the same time￾frequency resource is also fixed. As a conclusion, the encoding process of 802.11ax is fully compatible with PhyArith. That is, we can directly use commodity single antenna 802.11ax devices to send the sourceword bv of PhyArith via a raw socket, where the channel codes related process is provided by 802.11ax devices. VII. DECODING PROCESS OF PHYARITH In this section, we demonstrate the decoding process of PhyArith. Limited by the decoding complexity, client set V in PhyArith is randomly partitioned into subsets V = {V0, · · · , V|V |−1} first, where ∀Vi ∈ V, |Vi | ≤ ∆ and ∆ is the subset size limit. Then, as shown in Fig. 4, based on the superimposed RF signal, PhyArith directly decodes the sourceword-sum of each subset Vi , which is denoted by zi = [zi,0, · · · , zi,k−1] = X v∈Vi βˆ vbv, where βˆ v is an odd integer given by βˆ v = ( βv · 2 ζ + 1, with probability 1/2, βv · 2 ζ − 1, o.w., and ζ is a randomly chosen integer ensuring ∀v ∈ V, βv · 2 ζ ∈ N, βv · 2 ζ ≫ 1. For these obtained sourceword-sum zi verified to be correct, the summation of update vector chunks of Vi , i.e., P v∈Vi (βvav + γv1), is recovered. And for these zi verified to be incorrect, retransmission is requested. Finally, all these recovered summations can be added up and averaged, then assembled into the averaged update vector At, given by At = h · · · , X Vi∈V X v∈Vi (βvav + γv1)/|V |, · · · i . Note that here we let each βˆ v be a large odd integer to facilitate the verification of zi in Section VII-C, and make sure the recovered P v∈Vi (βvav + γv1) is accurate in Section VII-D. Sourceword-sum z|V|−1 Sourceword-sum z2 Sourceword-sum z1 Sourceword-sum z0 · · · Superimposed RF signal Sum-product derived decoder Recover or request retransmit P v∈Vl (βvav + γv1) P v∈Vj (βvav + γv1) P v∈Vi (βvav + γv1) · · · · · · Add up and average Averaged update vector chunk Averaged update vector chunk Averaged update vector chunk · · · Averaged update vector At Assemble Fig. 4. Decoding process of server A. Building of the Factor-Graph We first show how to directly decode each sourceword￾sum zi based on the superimposed RF signal. Let yj = [yu0,j , · · · , yu|U|−1,j ] T be the j-th observation vector. The decoding problem here can be formulated as the following optimization problem z ∗ 0 , · · · , z ∗ |V |−1 =arg max z0,··· ,z|V|−1 P(z0, · · · , z|V |−1|y0, · · · , ym−1). (5) Since jointly optimize z0, · · · , z|V |−1 is too complicated to solve. We can relax (5) as follows z ∗ i,j = arg max zi,j P(zi,j |y0, · · · , ym−1), where the marginal probability can be written as the following sum-product form via factorization P(zi,j |y0, · · · , ym−1) = X ∼zi,j P(y0, · · · , ym−1, z0, · · · , z|V |−1)/P(y0, · · · , ym−1) = A· X ∼zi,j P(y0, · · · , ym−1|sv0 , · · · , sv|V |−1 )· |V |− Y 1 i ′=0 [ Y v∈Vi ′ I(sv, xv, bv)]δ(k X v∈Vi ′ βˆ vbv − zi ′k1) . (6) Here ∼ zi,j denotes all random variables except zi,j . I(sv, xv, bv) is the indicator function to ensure xv is a valid LDPC codes codeword encoded from bv, and sv is a valid symbol sequence modulated from xv. And δ(·) denotes the Dirac delta function. A general method to efficiently obtain the marginal prob￾ability of each zi,j is the factor-graph based sum-product algorithm [18], which operates in a message-passing man￾ner. Specifically, while |V| = 2, the factorization (6) can be visualized by a factor-graph, a kind of bipartite graph like Fig. 5, which consists of two kind of nodes. One is called variable node (denoted by circles), representing random variables, and the other is called check node (denoted by squares), representing the local functions of variables. By exchanging messages in the form of probability mass function