US 6,597,743 B1Granted

Reduced search symbol estimation algorithm

AssigneeEricsson Inc.

InventorsAli S. Khayrallah, Gregory E. Bottomley, Ravinder David Koilpillai, Kambiz Zangi

Life of this patent

Estimating the term…

Loading patent…

Abstract

A reduced search symbol estimation algorithm includes a forward recursion, a backward recursion, and a combining step. To reduce complexity, during the forward and backward recursions, the number of survivor states retained at each stage is less than the total number of states of the trellis. The survivor states are selected from a group of candidate states, that are connected by branches to survivors from the previous stage of the recursion. The decoder compares the accumulated path metrics for each candidate state and retains a specified number of states that is less than the total possible number of states. For the forward recursion, the retained states or survivor states, denoted as Qk, are stored along with the corresponding state metrics. For the backward recursion, the retained states, denoted as Rk, are stored along with the corresponding state metrics. During the combining step, the computation of a soft value is restricted to branches (s′,s) connecting survivor states s′ and s in the forward and backward recursions respectively.

A method for decoding a received sequence to obtain an estimate of a transmitted sequence comprising:

forming a trellis comprising a plurality of nodes and a plurality of branches, wherein each node represents a particular state at one instant of time and wherein each branch represents a transition between states at different time instants and corresponds to a possible transmitted symbol associated with said transition;
assigning branch metrics to said branches of said trellis;
performing a forward recursion through said trellis starting from a beginning state and, at each stage in said forward recursion:
forming a set of candidate states, wherein said candidate states are those states having entry branches leading from a survivor state in the previous recursion;
computing the forward path metric for each candidate state based on said branch metrics;
forming a set Q of forward survivor states selected from said set of candidate states based on the forward path metrics for said candidate states, wherein the number of members in Q is less than the number of candidate states;
storing the forward path metric for each member state in Q;
performing a backward recursion through said trellis starting from an ending state and, at each stage in said backward recursion;
forming a set of candidate states, wherein said candidate states are those states having entry branches leading from a survivor state in the previous recursion;
computing the backward path metric for each candidate state based on said branch metrics;
forming a set R of backward survivor states selected from said set of candidate states based on the backward path metrics for said candidate states, wherein the number of members in R is less than the number of candidate states;
storing the backward path metric for each member state in Q;
for each stage k of said trellis, computing a soft value based on said accumulated forward path metrics for the survivor states in the set Qk−1, the accumulated backward path metric for the survivor states in the set Rk, and the branch metrics for the branches in the set B of branches connecting survivors states in Qk−1 and Rk.

10 more elements

Abstract

Claims11