Patent ID: 6999531

Claim:
A method of decoding a received convolutionally encoded data stream having multiple states s, the data stream having been encoded by an encoder, comprising the steps of: deriving normalized values γ′ j (R k ,s j ′,s)(j=0, 1) of branch metrics γ j (R k ,s j ′,s)(j=0, 1), which are defined as γ j ( R k ,s j ′,s )=log( Pr ( d k =j,S k =s,R k |S k−1 =s j ′)) and recursively determining values of forward state metrics α k (s) and reverse state metric β k (s) defined as α k ⁡ ( s ) = log ⁢ ( Pr ⁢ { S k = s | R 1 k } ) β k ⁢ ( s ) = log ⁢ ⁢ ( Pr ⁢ { R k + 1 N ⁢ S k = s } Pr ⁢ { R k + 1 N | R 1 N } ) from the normalized values γ′ j (R k ,s j ′,s)(j=0, 1) and previous values α k−1 (s′) of forward state metrics α k (s) and future values β k+1 (s′) of reverse state metrics β k (s), where Pr represents probability, R 1 k represents received bits from time index 1 to k, S k represents the state of the encoder at time index k, R k represents received bits at time index k, and d k represents transmitted data at time k.