Soft output Viterbi algorithm （SOVA） is a turbo decoding algorithm that is suitable for hardware implementation. But its performance is not so good as maximum a posterior probability（MAP） algorithm. So it is very ...Soft output Viterbi algorithm （SOVA） is a turbo decoding algorithm that is suitable for hardware implementation. But its performance is not so good as maximum a posterior probability（MAP） algorithm. So it is very important to improve its performance. The non-correlation between minimum and maximum likelihood paths in SOVA is analyzed. The metric difference of both likelihood paths is used as iterative soft information, which is not the same as the traditional SOVA. The performance of the proposed SOVA is demonstrated by the simulations. For 1 024-bit frame size and 9 iterations with signal to noise ratio from 1 dB to 4 dB, the experimental results show that the new SOVA algorithm obtains about more 0. 4 dB and 0. 2 dB coding gains more than the traditional SOVA and Bi-SOVA algorithms at bit error rate（BER） of 1 × 10^-4 , while the latency is only half of the Bi-direction SOVA decoding.展开更多
In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is sho...In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.展开更多
基金Guangzhou Science and Technology Project(2004Z3 -D0321) Guangdong Science and Technology Project(200510101013)
文摘Soft output Viterbi algorithm （SOVA） is a turbo decoding algorithm that is suitable for hardware implementation. But its performance is not so good as maximum a posterior probability（MAP） algorithm. So it is very important to improve its performance. The non-correlation between minimum and maximum likelihood paths in SOVA is analyzed. The metric difference of both likelihood paths is used as iterative soft information, which is not the same as the traditional SOVA. The performance of the proposed SOVA is demonstrated by the simulations. For 1 024-bit frame size and 9 iterations with signal to noise ratio from 1 dB to 4 dB, the experimental results show that the new SOVA algorithm obtains about more 0. 4 dB and 0. 2 dB coding gains more than the traditional SOVA and Bi-SOVA algorithms at bit error rate（BER） of 1 × 10^-4 , while the latency is only half of the Bi-direction SOVA decoding.
基金Research supported by the Science Foundation of Shandong Province.
文摘In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.
