Applications of cyclic redundancy checks (CRCs) with factorable generator polynomials
Original Publication Date: 2002-Apr-11
Included in the Prior Art Database: 2003-Jun-21
Cyclic redundancy checks are often used to ensure the integrity of data transmitted across a channel that is noisy and therefore capable of inducing errors. Conventionally, a primitive polynomial is chosen as the generator of the CRC. Because the advantages of using a primitive generator are substantial, the deliberate applicaion of a CRC that has a factorable, non-primitive generator is largely uninvestigated. Here, a CRC based on a factorable generator polynomial of the form G(x) g1(x)g2(x) is considered, where g1(x) and g2(x) are each primitive. Although a primitive polynomial is conventionally chosen for the generator G(x) , suppose that G(x) is not primitive, however, but is instead factorable as G(x)=g1(x)g2(x) , where g1(x) and g2(x) are themselves primitive, with degrees k1 and k2 , respectively, where k1 k2 k . Encoding a CRC using a generator G(x) that is factorable opens the possibility of partial decoding, i.e., decoding only according to one of the factors of G(x) rather than according to G(x) in its entirety. Partial decoding supports five new applications: (1) In a first application, a packet T(x) may enter a network at node A, and traverse from A to B, from B to C, from C to D, and from D to E, where the intermediate nodes B, C, and D check for transmission errors before forwarding packets. Suppose that AB and DE are metallic-conductor or wireless links, that BC and CD are optical-fiber links, and that the factors of G(x), have degree k1=16 and k2=48 . In this case, T(x) may be encoded at A and decoded at E according to G(x) , where G(x) has degree k1+k2 . Thus T(x) is protected end-to-end, although not maximally, by a CRC with a degree- 64 generator. Node B may decode T(x) according to G(x) , thereby providing degree- 64 protection also over wireline link AB. Nodes C and D, however, may decode T(x) according only to g1(x) , thereby providing degree- 16 protection over the optical-fiber links BC and CD. Thus, the network equipment at nodes C and D, which may be required to support hundreds or thousands of simultaneous connections, may be simplified or speeded, as these nodes need only to provide degree- 16 decoding.