EE/Ma 127c Error-Correcting Codesdraft of April 25, 2001R. J. McEliece162 MooreThe Forward–Backward AlgorithmIntroduction.In these notes I will present my somewhat idiosyncratic view of the famous forward-backward algorithm. The presentation will for now be restricted to a bare descriptionof the simple mathematical underpinnings, with no discussion of the many possible gen-eralizations and applications. In essense, the idea is simply this: If we have a set ofN elements of a noncommutative ring, say x1,...,xN, and are asked to compute the Nproducts of the formXi=Nj=1j=ixj, for i =1, 2,...,Nit is a good idea to first compute (recursively) the “forward” and “backward” partialproductsαi= x1···xifor i =0,...,Nβj= xj+1···xNfor j =0,...,Nand then use the relationshipXi= αi−1βifor i =1, 2,...,N.it is easy to see that this simple trick reduces the number of multiplications required tocompute X1,...,XNfrom O(N2)toO(N).It will be good to keep this basic idea in mind as we go through the formalities. Webegin in the next section with a desription of the basic problem solved by the FBA, whichinvolves the notion of a weighted trellis.1V1V2V3V4V0V5ABbcdefghjkmFigure 1. A trellis of rank 5.1. The Underlying Problems.A trellis is a special kind of directed graph, like the one illustrated in Figure 1. Thevertices are sorted according to rank, and the set of vertices of rank i is denoted by Vi, fori =0, 1,...,N. The number N is caled the rank of the trellis. The number of vertices ofrank i is denoted by qi. There is a single vertex of rank 0 caled the source, and denotedby A, and a single vertex of rank N , called the sink, and denoted by B. The only allowed(directed) edges are between vertices whose rank differs by 1, and the set of edges joiningvertices of rank i −1 to those of rank i is denoted by Ei−1,i. The initial vertex of an edgee is denoted by init(e), and the final vertex of e is denoted by fin(e). For example, InFigure 1 we see a trellis with N = 5 and q0=1,q1=2,q2=3,q3=3,q4= 2, and q5=1.Also, V0= {A}, V1= {b, c}, E0,1= {(A, b), (A, c)}, etc.A path P in a trellis is a set of connected edges: P = e1e2...ek, with fin(e1)=init(e2),...,fin(ek−1) = init(ek). The number of edges in P is called the length of P .Ifapath P = e1e2···ekhas initial vertex u = init(e1) and final vertex v =fin(ek), we writeP : u → v.If in addition the path P passes through the vertex w, we writeP : uw→ v.Finally, if the path P contains the edge e, we writeP : ue→ v.Next, we suppose that each edge e in the trellis is assigned a weight w(e), which fornow we assume is a real number.2V1V2V3V4V0V5ABbcdefghjkm1231241231212311133Figure 2. Weights assigned to the trellis of Figure 1.For example, in Figure 2 we see the trellis of Figure 1 with a weight associated with eachedge. If P = e1e2···ekis a path of length k in T , its weight is defined as the product ofthe weights of the component edges:w(P )=w(e1)w(e2) ···w(ek).The fundamental quantities computed by the FBA are the flows, defined as follows.Definitions. If u and v are vertices in a trellis, the flow from u to v, denoted µ(u, v),isdefined as the sum of the weights of all paths from u to v:µ(u, v)= P :u→vw(P ).(If there are no such paths, µ(u, v) is defined to be zero.) Similarly, if u, x, and v arevertices in T , the flow from u to v through x is defined asµx(u, v)= P :ux→vw(P ).Finally, u and v are vertices and e is an edge, the flow from u to v through e is defined asµe(u, v)= P :ue→vw(P ).The following simple result is one of the great secrets of the FBA. It shows how to usethe humble distributuve law to greatly simplify the calculation of the constrained flowsµx(u, v) and µe(u, v).3Theorem 1 . We have(1) µx(u, v)=µ(u, x)µ(x, v).Similarly, if init(e)=x and fin(e)=y,(2) µe(u, v)=µ(u, x) · w(e) · µ(y, v).Proof: We will prove (1), leaving (2) as an exercise.Suppose there are m paths from u to x,sayP1,...,Pm, and n paths from x to v,sayQ1,...,Qn. Then there are exactly mn paths from u to v through x, namely paths of theform Pi∗ Qj, where “∗” denotes concatenation. Then we haveµx(u, v)= P :ux→vw(P )=m i=1n j=1w(Pi∗ Qj)=m i=1n j=1w(Pi)w(Qj)= i=1w(Pi)n j=1w(Qj)(The distributive law)= µ(u, x)µ(x, v).The forward-backward algorithm (FBA) addresses the following three problems.Problem 1. Compute the flow from A to B, i.e.,µ(A, B)= P :A→Bw(P ).Since there may be as many as q1q2···qN−1paths from A to B, the computation ofµ(A, B) appears to be a formidable task. However, as we shall see, the FBA computes thisflow using at most 2(q0q1+ q1q2+ ···+ qN−1qN) arithmetic operations.Problem 2. For each vertex v, compute the flow from A to B through v, i.e.,µv(A, B)= P :Av→Bw(P ).4Note that we have v∈Viµv(A, B)=µ(A, B),since each path from A to B must pass through exactly one of the vertices in Vi.Thusthe ratio µv(A, B)/µ(A, B) can be interpreted as a kind of probability that a randomlyselected path from A to B passes through v.Problem 3. For each edge e, compute the flow from A to B through e, i.e.,µe(A, B)= P :Ae→Bw(P ).Note that we have e∈Ei−1,iµe(A, B)=µ(A, B),since each path from A to B must traverse exactly one of the edges in Ei−1,i. Thus theratio µe(A, B)/µ(A, B) can be interpreted as the probability that a randomly selected pathfrom A to B traverses the edge e.52. The Forward and Backward Recursions.For each i =1, 2,...N, define a qi−1×qimatrix Wi, whose rows are indexed by the verticesin Vi−1and columns are indexed by the vertices in Vi:Wi(u, v)=w(e) if there is an edge e joining u to v0 otherwise.For example, the Wi’s associated with the weighted trellis of Figure 2 are as follows:W1=bcA 12W2=defb 301c 240W3=ghjd 012e 312f 013W4=kmg 20h 31j 01W5=Bk 1m 3The heart of the forward-backward algorithm is the recursive computation of certain“forward” vectors αi, for i =0, 1,...,N and “backward” vectors βi, for i = N,N− 1,...,0.Here αiis a row vector of dimension qi, and βiis a column vector of dimension qi. Bothαiand βihave components indexed by Vi.Ifv ∈ Vi, we will denote the vth component ofαi(resp. βi)byαi(v) (resp. βi(v)).The αi’s are defined by the following forward recursion:(3) α0=1, αi= αi−1Wi, for i =1,...,N.and the βi’s are defined by a corresponding backward recursion:(4) βN=1, βi=