1 The Velocity of the Propagating Wave for Spatially Coupled Systems with Applications to LDPC Codes Rafah El-Khatib, Student Member, IEEE and Nicolas Macris, Member, IEEE 7 1 0 2 Abstract n a We consider the dynamics of message passing for spatially coupled codes and, in particular, the set of density J evolutionequationsthattrackstheprofileofdecodingerrorsalongthespatialdirectionofcoupling.Itisknownthat, 6 1 forsuitableboundaryconditionsandafteratransientphase,theerrorprofileexhibitsa“solitonicbehavior”.Namely,a uniquely-shapedwavelikesolutiondevelops,thatpropagateswithconstantvelocity.Underthisassumptionwederive ] T an analytical formula for the velocity in the framework of a continuum limit of the spatially coupled system. The I . general formalism is developed for spatially coupled low-density parity-check codes on general binary memoryless s c symmetricchannelswhichformthemainsystemofinterestinthiswork.Weapplytheformulaforspecialchannels [ and illustrate that it matches the direct numerical evaluation of the velocity for a wide range of noise values. A 1 possible application of the velocity formula to the evaluation of finite size scaling law parameters is also discussed. v 8 We conduct a similar analysis for general scalar systems and illustrate the findings with applications to compressive 1 sensing and generalized low-density parity-check codes on the binary erasure or binary symmetric channels. 3 4 0 Index Terms . 1 0 Message passing, density evolution, potential functional, threshold saturation, soliton, wave propagation, com- 7 pressive sensing. 1 : v i X I. INTRODUCTION r a Spatial coupling was first introduced by Felstrom and Zigangirov in the context of low-density parity-check (LDPC) codes [1]. Spatially coupled codes have been shown to be capacity-achieving on binary memoryless symmetric (BMS) channels under belief propagation (BP) decoding. The capacity-achieving property is due to the “threshold saturation” of the BP threshold of the coupled system towards the maximum a-posteriori (MAP) threshold of the uncoupled code ensemble [2], [3]. Spatial coupling has also been applied to several other problems besideschannelcoding[4],[5],suchaslossysourcecompression[6],[7],compressivesensing[8],[9],[10],random constraint satisfaction problems [11], [12], [13], and a coupled Curie-Weiss (toy) model [14], [15]. R.El-KhatibandNicolasMacrisarewiththeSchoolofComputerandCommunicationSciences,E´colePolytechniqueFe´de´raledeLausanne (EPFL),Lausanne,Switzerland,e-mails:{rafah.el-khatib,nicolas.macris}epfl.ch. January17,2017 DRAFT 2 Considerasingle(uncoupled)LDPCcode.ToconstructthecorrespondingcoupledcodeofspatiallengthL +w, c we take L +w replicas of the single system and “couple” every w adjacent single systems by means of a uniform c windowfunction.AteveryiterationoftheBPalgorithm,thevariableandchecknodesofthecoupledgraphexchange messageswhicharedescribedbyasetofcoupleddensityevolution(DE)iterativeequations.ThesolutiontotheDE equations, called the decoding profile x, is a vector of “error distributions” (more precisely, distributions of the BP log-likelihood estimates) along the spatial axis of coupling. More specifically, let the integer z ∈{−w+1,...,L } c denotethepositionalongthespatialdirectionofthegraphconstruction(onwhichthereplicasarespread).Thenthe zth component of x, call it x , denotes the distribution of the BP log-likelihood estimate at the zth position. In the z special case of the binary erasure channel (BEC) this component is reduced to the usual scalar erasure probability 0≤x ≤1 at position z along the spatial axis of coupling. z Spatially coupled codes perform well, and are capacity achieving, due to the threshold saturation phenomenon that is proved for general BMS channels in [2], [3]. More specifically, as long as the channel noise is below the MAP threshold, the decoding profile of a spatially coupled code converges to the all-∆ vector after enough ∞ iterations of the BP algorithm, where ∆ is the Dirac mass at infinite log-likelihood (i.e. perfect knowledge of ∞ the bits). In the special case of the BEC, the all-∆ vector corresponds to a vector of scalar erasure probabilities ∞ driven to zero by DE iterations. On the other hand, the probability distribution of the log-likelihoods of bits of the corresponding uncoupled code only converge to ∆ when the channel noise is below the BP threshold (which is ∞ lower than the MAP threshold). Thethresholdsaturationphenomenonismadepossibledueto“seeding”attheboundariesofthespatiallycoupled code.Seedingmeansthatwefixthebitsattheboundariessothattheprobabilitydistributionsoftheirlog-likelihoods are∆ .ThisfacilitatesBPdecodingneartheboundaries,andthiseffectispropagatedalongtherestofthecoupled ∞ chain. The minimum size of the seed that guarantees the propagation of the decoding effect is of the same order as the size w of the coupling window; however, an exact determination of the minimum possible such size is an still an interesting open question. When the channel noise is between the BP and the MAP thresholds, and the underlying uncoupled ensemble has a unique non-trivial stable BP fixed point that blocks decoding, an interesting phenomenon that has been empirically observed is the appearance of a solitonic decoding wave after a certain number of transient iterations of the BP algorithm. This soliton is characterized by a fixed shape that seems independent of the initial condition and has a constant traveling velocity that we henceforth call v. This phenomenology is discussed in more details in Section II-C. Figures 2 and 3 in Section II-C show an example of the transient phase and of the soliton in the case of spatially coupled codes on the BEC. The main goal of this work is to derive a formula for the velocity of the soliton for general BMS channels. The decoding wave has recently been studied in the context of coding when transmission takes place over the BEC. In [16], it is proved that the solitonic wave solution exists and bounds on the velocity of the soliton are derived. However, the independence of the unique shape of the wave from the initial conditions remains an open question.In[17],morecomplexcoupledsystemsarestudied,whereitispossibletohavemorethanonenon-trivial stable BP fixed point, and there again some bounds on the velocity of the soliton are provided. The solitonic January17,2017 DRAFT 3 behavior has also been studied for the coupled Curie-Weiss toy model [14] and in [15] a formula for the velocity, as well as an approximation, are derived and tested numerically. In the first part of this work, we derive a general formula for the velocity of the wave in the asymptotic limit L (cid:29) w (cid:29) 1 in the context of coding when transmission takes place over general BMS channels (see Equ. c (15)). This limit enables us to formulate the problem in a “continuum limit” which makes the derivations quite tractable. We show, with the use of numerical simulations, that this continuum limit yields good approximations for the velocity of the original discrete system. For simplicity, we limit ourselves to the case where the underlying uncoupled LDPC code has only one non-trivial stable BP fixed point. Our derivation rests on the assumption that the soliton indeed appears. More precisely, we assume that after an initialtransientphase,thedecodingprofiledevelopsauniqueshape,independentoftheinitialcondition,andtravels with a constant velocity v. This assumption can be strictly true only in an asymptotic limit of a very large chain length and a large iteration number (or time). It is an interesting open problem to make this space-time asymptotic limitpreciseandrigorouslyprovethatthesolitonappearsandisindependentoftheinitialcondition.Weconjecture that our velocity formula is exact in such a limit. TheformulaforthevelocityofthewavegreatlysimplifieswhenweconsidertransmissionovertheBEC,because thedecodingprofilereducestoascalarvectoroferasureprobabilities.FortransmissionovergeneralBMSchannels, we also simplify the analysis by applying the Gaussian approximation [18], [19]. This consists of approximating the DE densities and the channel by suitable “symmetric” Gaussian densities. Since the mean m and the variance σ2 of these symmetric Gaussian densities are related by σ2 = 2m, the analysis then reduces to that of a one- dimensional scalar system, whose technical difficulty is similar to that of the case of transmission over the BEC. We thus obtain a more tractable velocity formula and compare the numerical predictions of these velocity formulas with the empirical value of the velocity for finite values of L and w. Good agreement is found, on practically the c whole range of values within [(cid:15) ,(cid:15) ], even for small values of the window size w. BP MAP It is of theoretical as well as practical interest to have a hold on the analytical expression of the velocity of the wave. The velocity is also related to other fundamental quantities that describe a coding system, such as the finite-size scaling law that predicts the error probability of finite-length spatially coupled codes. In [20], the scaling law for a finite-length spatially coupled ((cid:96),r,L ) code, when transmission takes place over the BEC, is derived. c Involved in this scaling law are parameters that can be estimated using the value of the velocity of the decoding wave.Usingvaluesofthevelocitycomputedinourwork,weprovidereasonablygoodestimatesoftheseparameters. In the second part of this work, we consider general spatially coupled scalar bipartite systems (that are not restricted to coding) governed by a general message passing algorithm. In this setting, the system is scalar (one- dimensional) since the messages exchanged between the nodes are scalar. Due to seeding at the boundary, the “profile” (we no longer call it the “decoding profile”) exhibits the same phenomenology as in coding. Namely, a solitonic behavior appears after a short transient phase. We derive a formula for the velocity of the soliton for such systems and illustrate it on two applications: compressive sensing and generalized LDPC (GLDPC) codes. The derivations of the velocity formulas in both parts of the work use the same tools and assumptions. We combine the use of the “potential functional” introduced and used in a series of works [3], [11], [14], [21], [22], January17,2017 DRAFT 4 as well as the continuum limit L (cid:29)w (cid:29)1 which makes the derivations analytically tractable. The potential is a c “variational formulation” of the message passing algorithm on coding systems. It is a functional whose stationary points are the fixed points of the density evolution equations described by this algorithm, and has been used to prove threshold saturation in [3] for general BMS channels. A significant part of the formalism in [3] is used in the present work. We also note that potential formulations have been used to characterize the fixed point(s) of general scalar systems at the MAP threshold using displacement convexity in [23], [24]. An extension of the ideas in these works could shed some light on the question of the independence of the soliton’s shape from the initial conditions. SectionIIintroducesafewpreliminarynotionsthatwewillneedandreviewsthephenomenologyofthesolitonic wave. In Section III, we formulate the continuum limit and state our main formula for the velocity of the soliton on general BMS channels; the derivation is presented in Section IV. Comparisons with numerical experiments are presented in Section V. These concern transmission over the BEC as well as general BMS channels in the so-called Gaussian approximation. We also discuss a possible application of our formula to scaling laws for finite- size ensembles in Section VI. The case of general scalar spatially coupled systems is treated in Section VII, and illustrated for the examples of generalized LDPC codes (on the BEC or BSC channels) and compressive sensing. We present concluding remarks and propose further directions in Section VIII. A summary of this work has appeared in [25], [26]. II. PRELIMINARIES Weconsider(almost)thesamesettingasin[3]andadoptmostofthenotationintroducedinthatwork.Formore information about the formalism in these preliminaries, one can consult [27]. We denote by M(R¯) the space of probability measures x on the extended real numbers α ∈ R¯ = R∪{∞}. Here α∈R¯ should be interpreted as a “log-likelihood variable”. We call the measure x symmetric if (cid:82) dx(α)= E (cid:82) e−αdx(α) for all measurable sets E ⊂R¯. −E WedefineanentropyfunctionalH :M→RthatmapsafiniteprobabilitymeasurefromM(R¯)toarealnumber. It is defined as (cid:90) H(x)= dx(α)log (1+e−α). (1) 2 Note that this is a linear functional. Linearity is used in an important way to compute the entropy of convex combinationsofmeasures(whichalsoyieldprobabilitymeasures).Butwewillalsocomputethe“entropy”associated to differences of measures by setting H(x −x ) ≡ H(x )−H(x ). In other words, the entropy functional is 1 2 1 2 extended in an obvious way to the space of signed measures. Intheremainderofthiswork,wewillusetheDiracmasses∆ (α)and∆ (α)atzeroandinfinitelog-likelihood, 0 ∞ that have entropies H(∆ )=1 and H(∆ )=0, respectively. 0 ∞ We will also use the standard variable-node and check-node convolution operators and for log-likelihood (cid:16) (cid:24) ratio message distributions involved in DE equations [27]. For x , x ∈ M(R¯), the usual convolution x x is 1 2 1 2 (cid:16) the density of α=α +α , 1 2 January17,2017 DRAFT 5 and x x is the density of 1 2 (cid:24) α α α=2tanh−1(tanh 1 tanh 2). 2 2 More formally, for any measurable set E ∈R, the operators are defined by  (x1 x2)(E) =(cid:82) dx2(α)x1(E−α), (cid:16) (2) (cid:16) (cid:16) (cid:17)(cid:17) (x1 x2)(E) =(cid:82) dx2(α)x1 2tanh−1 ttaannhh((Eα//22)) . (cid:24) We note that the identities of the and operators are ∆ and ∆ , and their annihilators are ∆ and ∆ . More ∞ 0 0 ∞ (cid:16) (cid:24) explicitly,  ∆∞ x=x, ∆0 x=∆0, (cid:24) (cid:24) (3) ∆0 x=x, ∆∞ x=∆∞. (cid:16) (cid:16) Each operation, taken separately, is associative, commutative, and linear. However, when they are taken together, there is no distributive law; also, they don’t associate in the sense that x (x x ) (cid:54)= (x x ) x and 1 2 3 1 2 3 (cid:16) (cid:24) (cid:16) (cid:24) x (x x )(cid:54)=(x x ) x . We will also use the so-called duality rules 1 2 3 1 2 3 (cid:24) (cid:16) (cid:24) (cid:16)  H(x(cid:16)y)+H(x(cid:24)y)=H(x)+H(y), H(x a)+H(x a)=H(a), (4) H(a(cid:16)b)+H(a(cid:24)b)=0, (cid:16) (cid:24) where x,y ∈ M(R¯) and a, b are differences of probability measures a = x −x , b = x −x , x ∈ M(R¯), 1 2 3 4 i i=1,2,3,4. A. Single System Consider an (uncoupled) LDPC(λ,ρ) code ensemble and transmission over the BMS channel. Here, λ(y) = (cid:80) λ yl−1 andρ(y)=(cid:80) ρ yr−1 aretheusualedge-perspectivevariable-nodeandcheck-nodedegreedistributions, l l r r respectively. The node-perspective degree distributions L and R are defined by L(cid:48)(y) = L(cid:48)(1)λ(y) and R(cid:48)(y) = R(cid:48)(1)ρ(y), respectively. Moreover, consider communication over a family of BMS channels whose distribution c (α) in the log-likelihood domain is parametrized by the channel entropy1 H(c )=h. h h Let x˜(t) denote the variable-node output distribution of the BP algorithm at iteration t ∈ N. We can track the average behavior of the BP decoder by means of the DE iterative equations that are written as a recursion in terms of the variable-node output distribution as follows x˜(t+1) =c λ (ρ (x˜(t))), (5) h (cid:16) (cid:24) (cid:16) with initial condition x˜(0) =∆ (equivalently, we can take the perhaps more natural initial condition x˜(0) =c ). 0 h There are two thresholds of interest for us. The first one is the algorithmic threshold; it is defined for a family of BMS channels whose channel distributions c (α):R→M(R¯) are ordered by degradation and parametrized by h their entropy H(c )=h. It is also called the BP threshold of the family and is defined as h h ={h∈[0,1]: x˜=c λ (ρ (x˜)) =⇒ x˜=∆ }. BP h (cid:16) (cid:24) ∞ (cid:16) 1Intheliterature,thisquantityisoftendenotedbyc(h). January17,2017 DRAFT 6 The second threshold corresponds to optimal (MAP) decoding 1 h ={h∈[0,1]:liminf E[H(Xn|Yn(h))]>0}, MAP n→∞ n where H(Xn|Yn(h)) is the conditional Shannon entropy of the input given by the channel observations, and E is the expectation over the code ensemble. The potential functional W (x), x∈M(R¯), of the “single” or uncoupled system is s 1 1 W (x)= H(R (x))+H(ρ (x))−H(x ρ (x))− H(c L (ρ (x))). (6) s R(cid:48)(1) (cid:24) (cid:24) (cid:24) (cid:24) L(cid:48)(1) (cid:16) (cid:16) (cid:24) The fixed point form of the DE equation (5) is obtained by setting to zero the functional derivative of W (x;c) s with respect to x. In other words, x=c λ (ρ (x)) is equivalent to h (cid:16) (cid:24) (cid:16) 1 lim (W (x)+γη)−W (x))=0, (7) γ→0γ s s where η is a difference of two probability measures (see [3] for the proof of this statement). The BP and MAP thresholds, h and h , respectively, can be obtained from the analysis of the stationary points of the potential BP MAP function. See [3], [28] for more details and a rigorous discussion of this issue. Remark about notation. In the remainder of this work, most of the time, we omit the subscript h from c and the h argument α from x(α). This is because we will need a subscript (resp. an argument) z that represents the position along the chain in the discrete (resp. continuous) case. B. Spatially Coupled System ForstandardLDPCcodes,theBPthresholdh is,ingeneral,lowerthantheMAPthresholdh .Thedefinitions BP MAP oftheBPandMAPthresholdsaboveextendtothespatiallycoupledsetting.Spatialcouplingexhibitstwoattractive properties. First, the MAP threshold is conserved under coupling in the limit L →+∞ and for all w. The proof c of this statement is found in [28] (see also [29], [30]). Second, the BP threshold of the coupled system saturates to its MAP threshold as proved in [2], [3]. The main consequence of threshold saturation is that one can decode perfectly up to the h . MAP Let us now describe the density evolution and potential functional formalism for the spatially coupled code ensemble.ConsiderL +w“replicas”ofthesinglesystemdescribedinSectionII-A,placedonthespatialcoordinates c z ∈ {−w+1,...,L }. The system at position z is coupled to w neighboring systems by means of a coupling c window. For simplicity, we consider a uniform coupling window. We denote by x˜(t) the variable-node output z distribution at position z ∈ {−w +1,...,L } on the spatial axis and at time t ∈ N. The DE equation of the c coupled system takes the form (cid:32) w−1 w−1 (cid:33) x˜(t+1) =c λ 1 (cid:88)ρ (cid:16)1 (cid:88)x˜(t) (cid:17) . (8) z z(cid:16) (cid:16) w (cid:24) w z+i−j i=0 j=0 In this equation, c = c, for z ∈ {1,...,L } and c = ∆ for z ∈ {−w+1,...,0}. Furthermore, we fix the z c z ∞ left boundary to x(t) =∆ for z ∈{−w+1,...,0}, for all t∈N. These conditions express perfect information z ∞ January17,2017 DRAFT 7 at the left boundary which is what enables seeding and the decoding wave propagation along the chain of coupled codes. The initial condition (8) is x(0) =∆ for z ∈{1,...,L +w−1}. z 0 c w−1 It will be convenient to work with a smoothed version of the profile x˜(t), namely x(t) = 1 (cid:80) x˜(t) , which is z z w z−i i=0 the check-node input distribution. Then, using this change of variables, (8) can be rewritten as w−1 (cid:32) w−1 (cid:33) x(t+1) = 1 (cid:88)c λ 1 (cid:88)ρ (cid:16)x(t) (cid:17) . (9) z w z−i(cid:16) (cid:16) w (cid:24) z−i+j i=0 j=0 Just as in the single system case, this DE equation can be expressed as the stationarity condition of a potential functional (see [3]) L w−1 (cid:88) (cid:110) 1 1 (cid:16) (cid:0)1 (cid:88) (cid:1)(cid:17)(cid:111) W(x)= H(R (x ))+H(ρ (x ))−H(x ρ (x ))− H c L ρ (x ) . R(cid:48)(1) (cid:24) z (cid:24) z z(cid:24) (cid:24) z L(cid:48)(1) z(cid:16) (cid:16) w (cid:24) z+i z=−w+1 i=0 (10) wherex=(x ,...,x ).Thefixedpointformof(9)isequivalenttolim γ−1(W(x+γη)−W(x))=0 −w+1 L+w−1 γ→0 for η =(η ,...,η ) where η are differences of probability measures. −w+1 L+w−1 i C. Phenomenological observations Our derivation is far from rigorous and is based on an assumption derived from a phenomenological picture observedfromsimulations.Wesummarizethemainobservationsinthisparagraphforthecaseoftransmissionover the BEC channel. This channel also gives us the opportunity to illustrate the formalism outlined in Sections II-A and II-B in a concrete case. The BEC has channel distribution c (α)=(cid:15)∆ +(1−(cid:15))∆ , where (cid:15) is the erasure probability, and H(c )=(cid:15) (cid:15) 0 ∞ (cid:15) (hence h = (cid:15)). The density of the BP estimates of log-likelihood variables can be parametrized as x(t)(α) = x(t)∆ (α)+(1−x(t))∆ (α), where x(t) ∈[0,1] is interpreted as the erasure probability at iteration t∈N. The 0 ∞ DE equation becomes a one-dimensional iterative map x(t+1) =(cid:15)λ(1−ρ(1−x(t))) (11) over scalars in [0,1]. These iterations are always initialized with x(0) = 1 or, equivalently, x(0) = (cid:15). The corresponding fixed point equation is the stationarity condition for the potential function 1 (cid:15) W (x)= (1−R(1−x))−xρ(1−x)− L(1−ρ(1−x)). (12) BEC R(cid:48)(1) L(cid:48)(1) NotethatthepotentialfunctionisdefineduptoaconstantwhichissetheresothatW (0)=0.Figure1illustrates BEC the potential function for a (3,6)-regular Gallager ensemble, for several values of (cid:15). For (cid:15)<0.4294, the potential function (12) is strictly increasing, and equivalently the DE iterations are driven to the unique minimum at x=0. At (cid:15) = 0.4294 a horizontal inflexion point appears and a second non-trivial local minimum x appears; this BP BP minimum corresponds to the non-trivial fixed point reached by DE iterations. It is known that the MAP threshold is equal to the erasure probability where the non-trivial local minimum is at the same height as the trivial one and that decoding becomes impossible once the non-trivial minimum becomes a global minimum. For this example, this happens when (cid:15) = 0.4881. Figure 1 also shows the energy gap that is defined for (cid:15) ≤ (cid:15) ≤ (cid:15) as MAP BP MAP ∆E =W (x )−W (0). At the MAP threshold, we have ∆E =0. BEC BP BEC January17,2017 DRAFT 8 0.05 Below the BP threshold At the BP threshold 0.04 Between the BP and MAP thresholds At the MAP threshold 0.03 ) x (s W 0.02 0.01 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 x Fig. 1. We plot the potential function of the (3,6) regular LDPC when transmission takes place over the BEC((cid:15)) for several values of the erasureprobability(cid:15).Notethatx=0isalwaysatrivialstationarypoint.For(cid:15)<0.4294=(cid:15) thepotentialfunctionisstrictlyincreasingand BP x=0istheonlyminimum.At(cid:15) =0.4294ahorizontalinflexionpointdevelopsandasecondnon-trivialminimumexistsforlarger(cid:15).At BP (cid:15) =0.4881thetrivialandnon-trivialminimumareatthesameheightandtheenergygap∆E vanishes. MAP 1 0.8 0.6 xz 0.4 0.2 0 0 2 4 6 8 10 12 14 16 z Fig.2. WeconsiderthespatiallycoupledLDPC(λ(x),ρ(x))ensemble,withλ(x)=0.3x3+0.4x5+0.3x6andρ(x)=x5,withtransmission overtheBEC(0.7).TheparametersofcouplingareLc+w=16andw=3.Weplotthedecodingprofileduringthefirst10iterations,where theprofileisinitializedto0whenz≤3andto1elsewhere.Weobservethatthesegmentinitializedto1decreasesquicklyandconvergesto theBPthresholdx =0.6907.Weobservethatthetransientphaseisonlyabout5iterationshere,beforethedecodingprofileconvergestoa BP fixedshape. Letusnowdescribethephenomenologyofthesoliton(decodingwave)forspatiallycoupledcodes.Ourdiscussion is limited to the case where the underlying code ensemble has a single non-trivial DE fixed point (equivalently, the potential function has a single non-trivial local minimum). One can show that this is always the case for regular code ensembles. For irregular degree distributions the situation may be more complicated with many non-trivial fixed points that appear. For transmission over the BEC, equation (9) reads w−1 w−1 x(t+1) = 1 (cid:88)(cid:15) λ(cid:16)1 (cid:88)(cid:0)1−ρ(1−x(t) )(cid:1)(cid:17). (13) z w z−i w z−i+j i=0 j=0 Here, (cid:15) = 0 for z ∈ {−w+1,...,0} and (cid:15) = (cid:15) for z ∈ {1,...,L }. Furthermore, we fix the left boundary z z c to x(t) = 0 for z ∈ {−w+1,...,0}, for all t ∈ N. These are the “perfect seeding” conditions which enable the z initiation of decoding. The initial condition for the iterations is x(0) =1 (or (cid:15)) for z ∈{1,...,L +w−1}. z c Theevolutionofthedecodingwavecanbedecomposedintotwophases:atransientandastationaryphase.Inthe January17,2017 DRAFT 9 0.4 0.35 0.3 0.25 xz 0.2 Iteration 30 0.15 Iteration 60 0.1 Iteration 90 Iteration 120 0.05 Iteration 150 0 0 5 10 15 20 25 30 35 40 45 50 z Fig. 3. We consider the (3,6)-regular LDPC spatially coupled code with L = 50, w = 3 on the BEC(0.46). We plot the error probability along the spatial dimension and observe the “decoding wave”. This “soliton” is plotted every 30 iterations until iteration 150 and is seen to makeaquicktransitionfromzeroerrorprobabilitytotheBP-valuex =0.3798oftheerrorprobability.Theoptimal(MAP)noisethreshold BP is(cid:15) =0.4881. MAP transientphase,weobserveaprofileoferasureprobabilitiesx changingshape.Thesegmentinitializedtox(0) =1 z z quickly drops to x ≈x where it remains stuck on the far right for large values of z. The seeding region, on the z BP other hand, starts progressing towards the right-hand side and, after a few iterations, a fixed profile shape develops. This transient phase is illustrated in Figure 2 for an irregular code. Overall, it only lasts for a few iterations (of the order of 5 iterations in this example). After this transient phase is over, one observes a stationary phase with a solitonic behavior, as depicted in Figure 3. The profile of erasure probabilities has a stationary shape with a front at position z that moves, at a constant speed, towards the right. The soliton is relatively well-localized within front approximately 2w positions and quickly approaches x →0 for z <z and x →x for z >z . The stationary z front z BP front phaseanditssolitonaredepictedinFigure3forafinitespatiallycoupled(3,6)-regularensemblewithchainlength L = 50 and w = 3 for (cid:15) = 0.46. In this figure, we plot the decoding profile every 30 iterations starting at the c 30th iteration (the leftmost curve) and until the 150th iteration (the rightmost curve). The kink increases sharply from x =0 to x =x =0.3789 over a width of the order of 2w =6. z z BP III. CONTINUUMLIMITANDMAINRESULT A. Continuum Limit We now consider the coupled system in the continuum limit, in which the length of the coupling chain L is c first taken very large L →+∞, and then the window size is taken very large w →+∞. The continuum limit has c already been considered for the special case of the BEC in [16], [23], [24]. We slightly abuse notation by keeping the same symbols for the profile, the spatial position, and the channel distribution in the continuum limit. Thus, we denote by x(·,·) the continuous profile of distributions and set x(z,t)≡x(t). We then replace z →z so that the w z w new z is the continuous variable on the spatial axis, z ∈R. In view of the discussion of the phenomenology in Section II-C, we consider the class of profiles satisfying the “natural boundary conditions” x(z,t) → ∆ when z → −∞ for all t ∈ R, x(z,t) → x when z → +∞ for all ∞ BP t∈N, where x is the unique non-trivial stable fixed point of DE for the single system Equ. (5). BP January17,2017 DRAFT 10 The BMS channel distribution is now also continuous, and we denote by c(z) the channel distribution at the continuous spatial position z ∈R. The DE equation (9) then takes the form (cid:90) 1 (cid:16)(cid:90) 1 (cid:0) (cid:1)(cid:17) x(z,t+1)= duc(z−u) λ dsρ x(z−u+s,t) . (14) (cid:16) (cid:24) 0 (cid:16) 0 The initial condition at t=0 is given by a profile x(z,0) that interpolates between the two limiting values of the boundary condition, namely x(z,0)→∆ when z →−∞ and x(z,0)→x when z →+∞. ∞ BP B. Statement of Main Result We consider the channel entropy h∈[h ,h ]. The phenomenology tells us that: (i) after a transient phase, the BP MAP profile develops a fixed shape X(·); (ii) the shape is independent of the initial condition; (iii) the shape travels at constant speed v; (iv) the shape satisfies the boundary conditions X(z) → ∆ for z → −∞ and X(z) → x for ∞ BP z →+∞. We thus formalize these observations and make an ansatz: Ansatz. For each h ∈ [h ,h ] there exist a constant v ≥ 0 and a family of probability measures X(z) (indexed BP MAP by z ∈R) satisfying the boundary conditions X(z)→∆ for z →−∞ and X(z)→x for z →+∞, such that, ∞ BP for t → +∞ and |z −vt| = O(1), the solution of DE (14) is independent of the initial condition and satisfies x(z,t)→X(z−vt). Implicit in this ansatz is that we restrict ourselves here to underlying code ensembles that have only one non- trivial (stable) BP fixed point. This is true for regular codes for example (but is not limited to this case). Ensembles with many non-trivial fixed points could lead to more complicated phenomenologies as emphasized in [17] and would require to modify the ansatz. Velocity of the soliton for general BMS channels.Undertheassumptionabovethevelocityofthesolitonisgiven by ∆E v = , (15) (cid:16) (cid:17) (cid:82) dzH ρ(cid:48) (X(z)) X(cid:48)(z) 2 R (cid:24) (cid:24) (cid:24) where ∆E is the energy gap defined as ∆E =W (x )−W (∆ ), (16) s BP s ∞ and we recall that W is the potential (6) of the uncoupled system , x is the non-trivial BP fixed point to which s BP the uncoupled system converges, and ∆ is the trivial fixed point (Dirac mass at infinity). ∞ Letusmakeafewremarks.Inthisformula,theprimedenotesthederivativeX(cid:48)(z)=lim δ−1(X(z+δ)−X(z)) δ→0 whichistobeinterpretedasadifferencebetweentwomeasures.Theenergygapisonlydefinedforh ≤h≤h , BP MAP that is, when the single potential W has a non-trivial non-negative local minimum (see e.g. Figure 1). It is exactly s equal to zero when h=h , which confirms the fact that the velocity of decoding is zero (no decoding occurs) in MAP this case. Note also that, with our normalizations, W (∆ )=0. s ∞ January17,2017 DRAFT