Apparatus and method for implementing viterbi butterflies
AssigneeMotorola, Inc.
InventorsMichael Zarubinsky, Yoram Salant, Natan Baron
Life of this patent
Estimating the term…
Abstract
The Viterbi algorithm (20) is performed with a reduced number of calculations when the comparing step (C, 80, 50) is anticipated before the selecting (S, 62, 64, 66, 68) and adding steps (A, 74, 76). During comparing (C), selection decisions (e.g., D (i)) are obtained by analyzing pairs of old path metrics (e.g., P (2i, j−1) at 91, P (2i+1, j−1) at 92) by subtracting and multiplying the path metrics with branch metrics (e.g., B (i, j) at 95) and combining intermediate sign (e.g., SP, SB, SΔ) by e.g., and-logic (50). Selecting decisions (e.g., D (i/2, j+1), D (i/2+N/2, j+1) and new path metrics (e.g., P (i, j), P (i+12, j) are continuously stored and updated.
Claims19
A method for implementing Viterbi butterflies with the steps of adding, comparing, and selecting, characterized in that the step of comparing is anticipated before the steps of selecting and adding and that:
- in said step of comparing, a first path metric P (2i, j−1), a second path metric P (2i+1, j−1) and a branch metric+B (i, j) are related to a sign vector {SP, SB, SΔ} and components SP, SB, SΔ of said sign vector {SP, SB, SΔ} are related to a binary decision vector {D (i, j), D (i+N/2, j)} having first component D (i, j) and second component D (i+N/2, j);
- in said step of selecting, a first intermediate path metric P (i, j) is selected from P (2i, j−1) and P (2i+1, j−1) according to D (i, j), a second intermediate path metric P (i+N/2, j) is selected from P (2i, j−1) and P (2i+1, j−1) according to D (i+N/2, j), a first intermediate branch metric B1 (i, j) is selected from +B (i, j) and an inversion−B (i, j) of +B (i, j), and a second intermediate branch metric B2 (i, j) is selected from +B (i, j) and −B (i, j);
- in said step of adding, P (i, j) and B1 (i, j) are added to third path metric P (i, j)=P (i, j) +B1 (i, j), and P (i+N/2, j) and B2 (i, j) are added to fourth path metric P (i+N/2, j)=P (i+N/2, j) +B2 (i, j).
An apparatus for implementing Viterbi butterflies, said apparatus performing the steps of
- adding, comparing, and selecting,
- characterized in that
- said apparatus performs said step of comparing prior to performing said steps of
- selecting and adding and that:
- in said step of comparing, said apparatus relates a first path metric P (2i, j−1), a second path metric P (2i+1, j−1) and a branch metric +B (i, j) to a sign vector {SP, SB, SΔ}, said apparatus relates said components SP, SB, SΔ of said sign vector {SP, SB, SΔ} to a binary decision vector {D (i, j), D (i+N/2, j) } having first component D (i, j) and second component D (i+N/2, j);
- in said step of selecting, said apparatus selects a first intermediate path metric P (i, j) from P (2i, j−1) and P (2i+1, j−1) according to D (i, j), selects a second intermediate path metric P (i+N/2, j) from P (2i, j−1) and P (2i+1, j−1) according to D (i+N/2, j), selects a first intermediate branch metric B1 (i, j) from +B (i, j) and an inversion −B (i, j) of +B (i, j), and selects a second intermediate branch metric B2 (i, j) from +B (i, j) and −B (i, j);
- in said step of adding, said apparatus adds P (i, j) and B1 (i, j) to third path metric P (i, j)=P (i, j) +B1 (i, j), and adds P (i+N/2, j) and B2 (i, j) to fourth path metric P (i+N/2, j)=P (i+N/2, j) +B2 (i, j).
A method for transforming a first plurality of path metrics into a second plurality of path metrics, said method comprising the steps of:
- providing a first decision vector;
- and
- cyclically dividing said first plurality of path metrics into sub-pluralities of at least a first path metric, a second path metric, a third path metric, and a fourth path metric, thereby receiving a first branch metric and a second branch metric, selecting substantially simultaneously according to said first decision vector,
- (a) a first intermediate branch metric which is either a positive representation of said first branch metric or a negative representation of said first branch metric,
- (b) a second intermediate branch metric which is either a positive representation of said second branch metric or a negative representation of said second branch metric,
- (c) a first intermediate path metric which is either said first path metric or said second path metric, and
- (d) a second intermediate path metric which is either said third path metric of said fourth path metric,
- adding said first intermediate path metric and said first intermediate branch metric and adding said second intermediate path metric and said second intermediate branch metric, thereby providing said path metrics or said second plurality, and
- receiving a third branch metric and comparing said third branch metric with said path metrics of said second plurality, thereby providing a second decision vector, which in repetitions of said method updates said first decision vector.
Dependencies are inferred from the claim text.