Back to results
US 5,537,444 AGranted
Extended list output and soft symbol output viterbi algorithms
AssigneeAT&T Corp.
InventorsChristiane G. Nill, Carl-Erik W. Sundberg
Life of this patent
Estimating the term…
Abstract
A family of extended Generalized Viterbi Algorithm (GVA) and Soft Output Viterbi Algorithm (SOVA) decoders is disclosed. In one embodiment structural aspects of a SOVA are used to develop a new implementation for a serial GVA. Another aspect of the invention provides a low complexity SOVA that generates a reliability measure for decoded information using a list output of the GVA. In a further aspect, reliability information from a SOVA is used to develop a low complexity GVA.
Claims25
A method of processing a sequence of signals, said method comprising the steps of:
- receiving said signals over a communications channel corrupted by noise,
- determining a set of L best candidate sequences of signals, wherein each candidate sequence l, 1.ltoreq.l.ltoreq.L, in said set of best candidate sequences represents a sequence of length N,
- wherein candidate sequence l, 1.ltoreq.l.ltoreq.L, in said set of L best candidate sequences corresponds to a path through a trellis structure having N stages and a plurality of states at each stage,
- wherein the (l+1) th best candidate sequence is derived from knowledge of the first l best candidate sequences,
- wherein the l=1 best path through said trellis is known,
- wherein each path entering each state at each stage has a cumulative metric associated with it,
- wherein each path entering each state at each stage has a metric increment associated with a transition to another state at a next stage,
- wherein the state at each stage for each path is known,
- wherein l' is the number of the path with which the (l+1).sup.th best path re-merges,
- wherein the stage where the (l+1).sup.th best path re-merges with path l' is a re-merging point, and
- wherein initially the re-merging point is set equal to the N.sup.th stage of said trellis and wherein l=l'=1,
- and further comprising the steps of:
- a. calculating and storing along the l.sup.th best path a plurality of absolute differences, said absolute differences representing at each stage the magnitude of the difference of the cumulative metrics of the paths merging at said stage;
- b. excluding all re-merging points;
- c. finding the minimum absolute difference along the l.sup.th best path and storing the position of said minimum absolute difference;
- d. computing and storing the cumulative metric at the last state of the next best candidate to path l which goes through said re-merging point;
- e. repeating steps (b) through (d) if candidate l exists on the list of proposed candidates for the (l+1).sup.th best path;
- f. repeating steps (b) through (d) for path l' if l.gtoreq.2;
- g. selecting as the (l+1).sup.th best candidate the one of l candidate paths with the best cumulative metric at the final state;
- storing as l' the path with which the (l+1).sup.th best path re-merges and storing the re-merging point;
- h. incrementing l by one;
- i. repeating steps (a)-(h) until l=L.
19 more elements
A method of processing a first sequence of signals to determine a reliability measure for each symbol in a second sequence of signals, said first sequence of signals having been received over a communications channel corrupted by noise
- wherein a set of L best estimates of said second sequence are known,
- wherein each element l, 1.ltoreq.l.ltoreq.L, in said set of L best estimates corresponds to an l.sup.th best path through a binary trellis structure having a plurality of stages and a plurality of states at each stage, wherein each of the l, 1.ltoreq.l.ltoreq.L, best paths has a cumulative metric associated with it,
- said method comprising the steps of:
- initializing the i.sup.th element of a reliability vector with a first difference value, said first difference value equal to the difference between the cumulative metrics of paths merging at state i;
- shifting the elements in said reliability vector to the left by a specified number of elements, v, and substituting for the specified number of right most elements a constant high value;
- calculating for each path l, 2.ltoreq.l.ltoreq.L, a second difference value, said second difference value equal to the difference between the cumulative metric for said path and the cumulative metric of the best path;
- comparing for each path the bit sequence of the 1.sup.th best path, 2.ltoreq.l.ltoreq.L to the bit sequence of the best path and marking the positions where the paths differ;
- storing in the positions in said reliability vector where said paths differ, the smaller of said first difference or said second difference.
5 more elements
A method of processing a first sequence of signals, said first sequence of signals having been received over a communications channel corrupted by noise, to determine a reliability measure for each symbol in a second sequence of signals,
- wherein a set of L best estimates of said second sequence are known, wherein each element l, 1.ltoreq.l.ltoreq.L, in said set of L best estimates corresponds to an l.sup.th best path through a trellis structure having a plurality of stages and a plurality of states at each stage, wherein each of the l, 1.ltoreq.l.ltoreq.L, best paths has a cumulative metric associated with it,
- said method comprising the steps of:
- initializing a reliability vector with a first constant value, wherein said reliability vector is of length equal to the number of symbols in said second sequence;
- selecting for each 2.ltoreq.l.ltoreq.L best path a respective second value;
- comparing the symbol sequence of the l.sup.th best path 2.ltoreq.l.ltoreq.L to the symbol sequence of the l=1 best path and determining the positions where said symbol sequences differ;
- storing, in those positions where the l=1 best path and the l.sup.th path 2.ltoreq.l.ltoreq.L differ, the higher of the difference or of the value in said positions in said reliability vector.
3 more elements
A method of processing a coded information sequence of signals, said method comprising the steps of:
- decoding said information sequence to yield a set of N decoded information symbols wherein each decoded information symbol in said set of decoded information symbols has a corresponding reliability value in a set of reliability values;
- ordering, from lowest to highest, the amplitudes of said reliability values to form an ordered set of reliability values;
- associating the first l, l.ltoreq.N, of said reliability values in said ordered set of reliability values with a one-state trellis structure,
- wherein said one-state trellis structure has l stages, and
- wherein said associating is according to the rule that the i.sup.th reliability value in said ordered set of reliability values is associated with the i.sup.th stage of said one-state trellis structure, 1.ltoreq.i.ltoreq.l;
- determining a set of l best candidates for the decoded information sequence,
- wherein each of said candidates corresponds to a path through said one-state trellis structure,
- wherein each path through said one-state trellis structure has a cumulative metric associated with it, and
- wherein the set of l best candidates are, respectively, those paths with the l best cumulative metrics.
6 more elements
A method of processing an information signal, wherein said information signal comprises a sequence of values, said method comprising the steps of:
- determining an l+1.sup.th best candidate sequence of values representing said information signal based on a signal representing a set of first l best candidate sequences of values,
- wherein each of said candidate sequences of values corresponds to a path through a trellis structure, said trellis structure having a plurality of stages and a plurality of states at each stage, and wherein each state at each stage corresponds to a value in a candidate sequence of values and wherein each state has metric associated wherein said metric is a reliability measure corresponding to said value;
- said determining further comprising finding the state with the minimum metric along each path through said trellis structure, and identifying as the l+1.sup.th best candidate path the path which merges with the one of the l best paths at the state with the smallest minimum metric among the l best paths.
A method for determining a reliability value for each element in a sequence included in an information signal, each of said reliability values being stored in a reliability vector, the method comprising the steps of:
- receiving a signal representing a set of L best candidate sequences representing said sequence included in said information signal, said signal having been received over a communications channel corrupted by noise;
- receiving a signal representing a metric for each candidate sequence in said set of L best candidate sequences, wherein said metric is indicative of the relative similarity of each candidate sequence in said set of L best candidate sequences to said sequence;
- initializing said reliability vector with initial values;
- and
- storing, in said reliability vector in those positions where corresponding elements of said best candidate sequence and of the l.sup.th (l>1) best candidate sequence differ, the higher of said initial value in said reliability vector or a difference value.
2 more elements
A method for processing an information signal, said signal having been received over a communications channel corrupted by noise, wherein said information signal comprises a sequence of values, said method comprising the steps of:
- determining a set of L (>1) best candidate sequences representing said information signal based on a signal containing a best candidate sequence and reliability values for individual bits in said best candidate sequence;
- said determining further comprising:
- ordering, from lowest to highest, said reliability values to form an ordered set;
- associating elements in said ordered set as metrics for successive stages with a one state trellis;
- finding a set of successive best paths through said one state trellis, wherein each of said paths corresponds to a candidate sequence for said sequence of values, wherein the quality of said best path is the sum of said metrics, and
- wherein the relative quality of each successive best paths in said set of successive best paths is measured by subtracting from said sum of said metrics for said best path twice the metric corresponding to the stages in which each of said successive best paths and said best path through said trellis differ.
3 more elements
Dependencies are inferred from the claim text.