US 6,272,187 B1 · Device and method for efficient decoding with time reversed data

Abstract

A novel device which efficiently decodes data encoded with a cyclic code in communications systems where a convolutional code is applied after the cyclic code during encoding. Specifically, the device accepts data provided in time reversed order by a Viterbi decoder which decodes the convolutional code. In a preferred version, the device employs linear feedback shift registers with multiple feedback paths. A set of multipliers corresponding to a set of coefficients is interposed in the feedback paths such that when data is shifted through the feedback shift registers, the device performs division by x for an input bit equal to 0, and, for an input bit equal to 1, performs division by x and then adds xk+m−1. The set of multipliers includes a set of weighting multipliers corresponding to coefficients of a weighting polynomial such that addition of xk+m−1 is performed for an input bit equal to 1. In another preferred version, the device compares a known initial state to a final state generated by shifting time reversed data through the linear feedback shift registers such that the final state equals the known initial state if there are no errors.

Claims13

Dependent claims

A device which decodes data encoded with a cyclic code in communications svstems where a convolutional code is applied after the cyclic code during encoding, comprising:

a decoder which decodes the convolutional code;
and
a cyclic redundancy check circuit comprising a plurality of linear feedback shift registers having a plurality of feedback paths,
wherein the device is configured to accept data provided in time reversed order, and
wherein a set of multipliers corresponding to a set of coefficients is interposed in the feedback paths such that when data is shifted through the feedback shift registers, the device performs division by x for an input bit equal to 0, and, for an input bit equal to 1, performs division by x and then adds xk+m−1, where x is a variable of a generating polynomial g(x)=gkxk+gk−1xk−1+ . . . +g1x+g0, k is the highest order of the generating polynomial, and m is the total number of input bits to be decoded.

2 more elements

A method for efficiently decoding data encoded with a cyclic code in communications systems where a convolutional code is applied after the cyclic code during encoding, wherein the data is represented as a polynomial a(x)=a0+a1x+a2x2 . . . +am−1xm−1 where the coefficients ai correspond to the data encoded with the cyclic code and m is the total number of input bits to be decoded, and wherein the cyclic code is based upon a generating polynomial g(x)=gkxk+gk−1xk−1+ . . . +g1x+g0, where k is the highest order of the generating polynomial, the method comprising the steps of:

(a) receiving decoded data from a convolutional decoder in time reversed order;
and
(b) inputting the decoded data in said time reversed order into a cyclic redundancy check circuit comprising a plurality of linear feedback shift registers having a plurality of feedback paths,
wherein a set of multipliers corresponding to a set of coefficients is interposed in the feedback paths such that when data is shifted through the feedback shift registers, division by x is performed for an input bit equal to 0, and, for an input bit equal to 1, division by x is performed and then xk+m−1 is added, where x is a variable of the generating polynomial g(x).

1 more element

Dependencies are inferred from the claim text.

Device and method for efficient decoding with time reversed data

Life of this patent

Device and method for efficient decoding with time reversed data

Life of this patent

Abstract

Claims13