APPENDIX A

The following Fortran subroutine implements the Viterbi algorithm:

	subroutine rviterbi(n1,n2,npath,in,out,qqsum,qqmin)
c
c  ------------------------------------
c		find the shortest-path with viterbi algorithm
c  ------------------------------------
c
c	n1,n2				dimension of the array
c	npath				number of allowed paths
c	in				input array
c	qqsum,qqmin			auxiliary array
c	out				output array
c
c  ------------------------------------
c
	implicit none

integer n1,n2,i1,i2
	integer npath,ipath
	integer i2min,i2max,npathh,ipathmin,ipathmax
	integer i2pick,i2newpick
	real minvalue
	real in(n1,n2)
	real qqsum(n1,n2),qqmin(n2)
	real out(n1)

npathh = (npath-1)/2
c VITERBI ALGORITHM
c    forward error accumulation
	call zero(n2,qqmin)
	call zero(n1*n2,qqsum)
	do i2 = 1,n2
	   qqsum(1,i2) = in(1,i2)
	enddo
	do i1 = 2,n1
	   do i2 = 1,n2
	      qqmin(i2) = 1.e+30
	   enddo
	   do ipath = -npathh,npathh
	      i2min = max(1,1-ipath)
	      i2max = min(n2,n2-ipath)
	      do i2 = i2min,i2max
	         qqmin(i2) = min(qqmin(i2),qqsum(i1-1,i2+ipath))
	      enddo
	   enddo
	   do i2 = 1,n2
	      qqsum(i1,i2) = qqmin(i2)+in(i1,i2)
	   enddo
	enddo

c    backward tracing
	i1 = n1
	i2pick = (n2-1)/2
	minvalue = qqsum(i1,i2pick)
	do i2 = 1,n2
	   if(qqsum(i1,i2) .lt. minvalue)then
	      i2pick = i2
	      minvalue = qqsum(i1,i2pick)
	   endif
	enddo
	out(i1) = real(i2pick)
	do i1 = n1-1,1,-1
	   minvalue = 1.e+30
	   if(qqsum(i1,i2pick) .le. minvalue)then
	      minvalue = qqsum(i1,i2pick)
	      i2newpick = i2pick
	   endif
	   ipathmin = max(-npathh,1-i2pick)
	   do ipath = ipathmin,-1
	      if(qqsum(i1,i2pick+ipath) .lt. minvalue)then
	         minvalue = qqsum(i1,i2pick+ipath)
	         i2newpick = i2pick+ipath
	      endif
	   enddo
	   ipathmax = min(npathh,n2-i2pick)
	   do ipath = 1,ipathmax
	      if(qqsum(i1,i2pick+ipath) .lt. minvalue)then
	         minvalue = qqsum(i1,i2pick+ipath)
	         i2newpick = i2pick+ipath
	      endif
	   enddo
	   i2pick = i2newpick
	   out(i1) = real(i2pick)
	enddo

return
	end