Error correction apparatus using a viterbi decoder

Claim 2

An error correcting apparatus comprising: a source of path metrics associated respectively with states in a given time slot of a Viterbi trellis diagram, said path metrics being updated sequentially in response to new path metrics; branch metric generating means for sequentially generating a branch metric in response to input convolutional code data and providing a plurality of sums of the branch metrics over successive branches diverging from said given time-slot states to later time-slot states; adder means coupled to said source and to said branch metric generating means for adding the updated path metrics to a respective one of the branch metric sums to provide a plurality of second sums; comparing means coupled to said adder means for comparing said second sums and detecting the highest of the compared second sums to provide a control signal representing the highest of the compared second sums; selecting means coupled to said comparing means for selecting the detected highest second sum in response to said control signal for providing a new path metric to said source for updating a previous path metric; and storage means coupled to said comparing means for storing data indicating the path associated with the selected highest second sum.

Claim 3

An error correcting apparatus comprising: a source of path metrics associated respectively with states in a given time slot of a Viterbi trellis diagram, said path metrics being updated sequentially in response to new path metrics; branch metric generating means for sequentially generating a branch metric in response to input convolutional code data and providing a plurality of sums of the branch metrics over successive branches diverging from said given time-slot states to later time-slot states; adder means coupled to said source and to said branch metric generating means for adding the updated path metrics to a respective one of the branch metric sums to provide second sums; first comparing means coupled to said adder means for comparing said second sums to provide a plurality of first control signals each representing the highest of the second sums; first selecting means coupled to said first comparing means for selecting said highest second sums in response to said first control signals; second comparing means coupled to said first selecting means for comparing the selected second sums to provide a plurality of second control signals each representing the highest of the selected highest second sums; second selecting means coupled to said second comparing means for selecting said highest selected second sums in response to said second control signals for providing path metrics to said source for updating previous path metrics; and storage means coupled to said first and second comparing means for storing data indicating the paths associated with the sums selected in response to said first and second control signals.

Claim 4

An error correcting apparatus comprising: a source of path metrics associated respectively with states in a given time slot of a Viterbi trellis diagram, said path metrics being updated sequentially in response to new path metrics; branch metric generating means for sequentially generating a branch metric in response to input convolutional code data and providing a plurality of sums of the branch metrics over successive branches diverging from said given time-slot states to later time-slot states; adder means coupled to said source and to said branch metric generating means for adding the updated path metrics to a respective one of the branch metric sums to provide second sums; first comparing means coupled to said adder means for comparing said second sums to provide a plurality of first control signals each representing the highest of the second sums; first selecting means coupled to said first comparing means for selecting said highest second sums in response to said first control signals; second comparing means coupled to said first selecting means for comparing the selected second sums to provide a plurality of second control signals each representing the highest of the selected highest second sums; second selecting means coupled to said second comparing means for selecting said highest selected second sums in response to said second control signals for providing path metrics to said source for updating previous path metrics; and storage means coupled to said first and second comparing means for storing data indicating the paths associated with the sums selected in response to said first and second control signals.

Claim 5

An error correcting-apparatus as claimed in claim 2, wherein said adder means comprises first and second pairs of adders and third and fourth pairs of adders, the adders of each pair being associated respectively with the states of said given time slot, said first, second, third and fourth pairs being associated respectively with the states of a later time slot, the adders of each pair adding the updated path metrics of the associated given time-slot states to the branch metric sums associated respectively with different branches diverging from said given time-slot states to the one of the later time-slot states with which said each pair is associated.

Claim 6

An error correcting apparatus as claimed in claim 3, wherein the branches associated with the adders of said first and second pairs share a common state of the Viterbi trellis diagram in an intermediate time slot with the branches associated with the adders of said third and fourth pairs.

Claim 7

An error correcting apparatus as claimed in claim 4, wherein said first comparing means comprises: a pair of first and second comparators respectively connected to the outputs of the adders of said first and second pairs for generating first and second comparator outputs as said first control signals, said first selecting means comprising: first and second pairs of selectors, the selectors of the first pair being connected respectively to the outputs of the adders of said first and second pairs and being respectively responsive to said first and second comparator outputs to selectively apply the last-mentioned outputs to said second comparing means, the selectors of the second pair being connected respectively to the outputs of the adders of said third and fourth pairs and being respectively responsive to said first and second comparator outputs to selectively apply the last-mentioned outputs to said second comparing means.

Claim 8

Error correcting apparatus comprising an arrangement of adders (301-304 etc), comparators (305, 306, 309, 409, etc) and selectors (307, 308, 310 etc) which effect additions over a plurality of depths of a Viterbi trellis diagram of stored path metrics (M 1 , M 2 , etc) and branch metrics (Z 11 + Z 11 , Z 31 + Z 11 etc), comparisons of the resulting sums and selections in accordance with the comparisons to update the stored path metrics and determine output bits in accordance with the selections, characterised in that the branch metrics ( Z 11 + Z 11 , Z 31 + Z 11 ) are sums of branch metrics over branches defining possible routes through a plurality of depths of the trellis diagram, the adders (301-304 etc) effect all the said additions in parallel and the comparators (305, 306, 309, 409 etc) and selectors (307, 308, 310 etc) effect a plurality of levels of comparison and selection.

Claim 9

Error correcting apparatus comprising an arrangement of adders (301-304 etc), comparators (305, 306, 309, 409, etc) and selectors (307, 308, 310 etc) which effect additions over a plurality of depths of a Viterbi trellis diagram of stored path metrics (M 1 , M 2 , etc) and branch metrics (Z 11 + Z 11 , Z 31 + Z 11 etc), comparisons of the resulting sums and selections in accordance with the comparisons to update the stored path metrics and determine output bits in accordance with the selections, characterised in that the branch metrics ( Z 11 + Z 11 , Z 31 + Z 11 ) are sums of branch metrics over branches defining possible routes through a plurality of depths of the trellis diagram, the adders (301-304 etc) effect all the said additions in parallel and the comparators (305, 306, 309, 409 etc) and selectors (307, 308, 310 etc) effect a plurality of levels of comparison and selection.

Claim 10

Apparatus according to claim 6, characterised in that in at least the first level of comparison and selection, each comparator (e.g. 305) controls the selector (307) effecting selection between the sums compared by that comparator and also controls at least one other selector (407) effecting selection between a further pair of sums from two of the adders (401, 402).