A Note on Message Passing Decoding Over Non-Gaussian Channels

A Note on Message Passing Decoding Over Non-Gaussian Channels A. Chawla October 6, 2025 Abstract In these notes, the authors work out the outline of the analysis of SPARC codes when the channel model is free space optical (FSO). In this study, the fading coefficient is assumed to be a known constant. The key contribution is an application of Shannon’s standard noisy channel coding theorem to the aforementioned channel model. 1 Fading Coefficients are Known Constants: Channel Model and Initial Time In this section we setup the case where the fading coefficient of the FSO channel is known. Then we input a SPARC codeword [1] into the channel. Then we step forward in time using the AMP algorithm and obtain the decoding estimate for the input codeword coordinate (see Equation 26 in Subsection 1.2). Working this out explicitly sets the stage for an application of the Shannon theorem in Section 2. x=CoeffF SO ·Aβ0(1) where CoeffF SO is known and Aβ0is a single codeword coordinate. We have the channel equation, Y=Hx +Ith (2) where His treated as a constant at present. Next we let J=Y H=x+Ith H.(3) where Jrepresents a single number and Hrepresents a single fading coefficient. We assume His known. Therefore, Ji=CoeffF SO(Aβ0)i+Ith Hi .(4) 1 Since CoeffF SO is a known constant, Ki≡Ji CoeffF SO = (Aβ)i+Ith CoeffF SO ·Hi (5) where Ais a known, sparse, design matrix, βis a sparse message vector and the last term is the noise term. In vector form,  K=→ −→ A−→ β0+−→ n(6) which belongs to Rnwith −→ β0∈RN. Here → −→ Ais the design matrix of the SPARC code, −→ β0is the message vector and −→ nis the i.i.d. noise vector. The variance of each i.i.d. r.v. is ¯ I2 th (CoeffF SO Hi)2where CoeffF SO = 2RP√Tand Hiis a known constant. Given −→ Kand → −→ A1, we wish to reconstruct −→ β0. Next, we will advance through the AMP algorithm steps, indexed by the time t. We start with Step 1, at time t= 0.We guess β0 0= 0. Therefore, z0=−→ K−→ −→ Aβ0 0+1 δz−11 N N X i=1 η′ −1(→ −→ A†z−1+β−1 0)(7) where δ=n LM . Further, any variable with a negative index is assumed to be 0, as per Montanari. Thus, z−1≡0(8) η′ −1≡0(9) and β−1 0≡0.(10) Therefore, z0=−→ K−→ −→ Aβ0 0+ 0 (11) with β0 0= 0.Therefore, z0=−→ K. (12) 1Note that this design matrix is n×LM, with N≡LM. 2 1.1 First Time Step Next, β1 0=η0(→ −→ A†z0+β0 0)(13) where z0=−→ K(14) and β0 0= 0. Further, η0≡η0 i|i=0(s)(15) and η0 i=pnPl esi√nPl τ2 0 Pj∈sec(i)esj√nPl τ2 0 (16) where 1≤i≤N. Evaluating the expression at i= 0, we get η0=pnPl es0√nPl τ2 0 Pj∈sec(0) esj√nPl τ2 0 (17) We define, τ2 0≡ith 2 (2RP√THi)2+E[β2 0] δ(18) where β0is a random variable whose distribution coincides with the empirical distribution of the entries of −→ β0. This is based on Equation (1.4) and adjoining text from Montanari’s paper [2], and Equation [8] of the reference DMM09 from the same paper. Here δ=n LM and Plis the allocated power. We find, z1=−→ K−→ −→ Aβ0 0+1 δz0⟨η′ 0(→ −→ A†z0+x0)⟩(19) where z0=−→ Kand x0= 02. Recall that η′ 0was specified earlier. Therefore, z1=−→ K+1 δ−→ K⟨η′ 0 → −→ A†−→ K⟩.(20) 2Note that: β0≡x,β0 0≡x0,. . .,βt 0≡xt. 3 1.2 Second Time Step Then β2 0=η1(→ −→ A†z1+β1 0).(21) Here we ask the question as to what is τ2 1, which is needed in η1? We refer the reader to Equation (1.4) from Montanari’s paper. There, τ2 1=ith 2 (2RP√THi)2+1 δE[η0(β0+τ0z)−β0]2(22) where η0is specified in Ⅎ,β0has a pdf which matches the empirical distribution of the entries of −→ β0and z∼N(0,1) is independent of β0. Further, Equation (18) specifies τ0. Next, z2=−→ K−→ −→ Aη1(→ −→ A†z1+β1 0) + 1 δz1⟨η′ 1(→ −→ A†z1+β1 0)⟩(23) and so therefore, z2=−→ K−→ −→ Aη1(→ −→ A†z1+β1 0) + 1 δz1⟨η′ 1(→ −→ A†z1+β1 0)⟩.(24) Therefore, z2=−→ K−→ −→ Aη1(→ −→ A†(−→ K+1 δ−→ K⟨η′ 0 → −→ A†−→ K⟩) + β1 0). . . (25) . . . +1 δ(−→ K+1 δ−→ K⟨η′ 0 → −→ A†−→ K⟩)⟨η′ 1(→ −→ A†(−→ K+1 δ−→ K⟨η′ 0 → −→ A†−→ K⟩) + β1 0)⟩.(26) and so on, for the higher indices. Thus, we have a nested or iterative ztfrom which we reconstruct βt+1 0using Montanari’s Equation (1.1), and that gives us, for large enough t, a good approximation to β0. 2 Analysis Outline In this section, our goal is to characterize the performance of the SPARC-FSOAMP system. We break down the characterization into a sequence of steps. 1. We fix some large t 2. Get the equation for βt+1 0, as in the parts above. It will be in terms of the received vector, −→ k, the empirical distribution of the message vector (via τ), g P−→ β0, the power allocation Pl, the SPARC structure (si, sj, sec(j)etc.) and FSO channel-noise and modulation constants. 4 3. Assume a uniform distribution on the messages and derive g P−→ β0. 4. Fix a power allocation Pl, for example an exponential power allocation. 5. Fix the SPARC structure si, sj, sec(j)etc. 6. Fix the channel noise and modulation parameters as constants. 7. Thus we have, βt+1 0∼f(−→ K, g P−→ β0, Pl, si, sj, Ith, H).(27) Define R′≡(g P−→ β0, Pl, si, sj, Ith, H). That is, βt+1 0∼g(−→ K), since R′is known, where −→ Kwas received and βt+1 0is our approximation to the message vector of the pseudo-channel. 8. Finally, using g(−→ K)as the decoding, we are done. 9. Then we compare g(−→ K)with β0to determine whether the decoding is correct and thus the overall transmission goal is met or not. 10. So we want the following quantity: Pr{β0=g(−→ K)}(28) 11. For different t, we could say that since the decoding structure was different, the code is different. 12. As t→ ∞,we have here a sequence of codes. 13. Recall the noisy channel coding theorem: for every rate R < C, there exists a sequence of codes whose P oemax →0as t→ ∞.3 14. Thus, fix a rate Rand so a SPARC structure (L, n, N)and then we have here a customized (that is, (L, n, N)-dependent) code for each t. That is, we have a code sequence. Find the maximum value of Rsuch that Equation (28) converges to 0 as t→ ∞. This would be the “capacity” or maximum achievable rate Rmax on an FSO, using the SPARC-AMP code. 15. Finally, we may compare this Rmax with LDPC-FSO-Belief-Propagation code’s maximum achiveable rate to decide whether SPARCs are “better” vis-a-vis LDPC codes. 3Note that Equation (1) in Greig-Venkataramanan states that R=Llog(M) n=L n(log N L)(29) where Lis the number of sections and n, N are dimensional parameters. 5 3 Conclusion In this note we have setup the exact analysis outline to determine the comparative performance of different codes such as LDPC and SPARCs over the free space optical channel with approximate message passing decoding. Note that the channel model of the FSO system is itself under development, with effects such as turbulence not fully accounted for yet in the literature (see the text of Andrews and Phillips for example), and therefore the steps presented in this work, if used with the basic model should be taken with some degree of uncertainty. If such a coding/decoding system is to be used in the control setting for say synchronization, then Sahai’s anytime framework will need to be integrated within this setup. One imagines a sequential semi-orthogonal repeated pulse position modulation system, but with AMP decoding which itself plays out online. The coding side will need to be reformulated as well. Some steps in this direction were taken in the following preprint: [3]. References [1] Kuan Hsieh and Ramji Venkataramanan. Modulated sparse superposition codes for the complex awgn channel. IEEE Transactions on Information Theory, 67(7):4385–4404, 2021. [2] Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory, 57(2):764–785, 2011. [3] Aman Chawla. Anytime reliability analysis of finite state slow fading free space optical channels. June 2025. 6