Browse Prior Art Database

Applications of cyclic redundancy checks (CRCs) with factorable generator polynomials

IP.com Disclosure Number: IPCOM000015798D
Original Publication Date: 2002-Apr-11
Included in the Prior Art Database: 2003-Jun-21
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

  Applications of cyclic redundancy checks (CRCs) with factorable generator polynomials

     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.

    (2) In a second application, which is closely related to the first, end-to-end protection through a network may normally be provided by a CRC that is encoded and decoded according to g1(x). In addition, a special class of network attachments may be permitted to encode and decode according to G(x), where the added redundancy bits are carried as part of an info...