Browse Prior Art Database

TESTING A CRC CHECKER

IP.com Disclosure Number: IPCOM000005582D
Original Publication Date: 1985-Oct-01
Included in the Prior Art Database: 2001-Oct-17
Document File: 3 page(s) / 109K

Publishing Venue

Motorola

Related People

Yehuda Shaik: AUTHOR

Abstract

In data transmission systems which include error detection/correction circuits of the Cyclic Redundance Check (CRC) type, the transmitter serially transmits each block of data while simultaneously processing the data using a selected N-bit CRC generator, and then transmits the resulting N-bit CRC polynomial to complete a "Frame". At the receiver, each Frame is continuously processed by an identical CRC generator. After the last bit in the Frame is processed, the remainder polynominal R(x) is compared against a constant remainder polynomial C(x). If the two polynomials are identical, there was no error in the Frame.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 3

0 M

MOTOROLA Technical Developments Volume 5 October 1985

TESTING A CRC CHECKER

by Yehuda Shaik

THE PROBLEM

   In data transmission systems which include error detection/correction circuits of the Cyclic Redundance Check (CRC) type, the transmitter serially transmits each block of data while simultaneously processing the data using a selected N-bit CRC generator, and then transmits the resulting N-bit CRC polynomial to complete a "Frame". At the receiver, each Frame is continuously processed by an identical CRC generator. After the last bit in the Frame is processed, the remainder polynominal R(x) is compared against a constant remainder polynomial C(x). If the two polynomials are identical, there was no error in the Frame.

   During testing of the receiver's CRC circuitry, the operation of the polynomial comparator must be verified before the functionality of the generator can be verified. If the inputs to the comparator are not directly accessible, it would be convenient to utilize the generator to generate test inputs into the comparator. The problem thus becomes one of creating a set of N test Frames, each of which will produce a CRC error in just one bit n of the remainder polynomial.

THE GOAL

Let us define:

G(x) generator polynomial (length=N+l) P(x) received polynomial (FRAME with CRC, length> =N) R(x) remainder polynomial (length=N+l)

C(x) constant remainder polynomial (length=N +l) i is an integer (0 N-l).

Our goal is to find:
(1) R(x) = remainder of Pi(x)

G(x)

so that:

We;N ==, CJp) + (0

+ means XOR over the binary field
x.7 indicates the "i'th" bit position for testing.

However:
(3) Pi(x) = Pti(x) + Pei(x) where Pti(x) is a Frame without a CRC error

Pei(x) is the same Frame with a CRC error.

Thus we have:
(4) C(x) + (x-7) is the remainder of Pti(x) + Pei(xJ

G(x)

Note that equation (4) can be broken into two equations:
(5) C(x) is the remainder of PtiJxJ

G(x)

(6) x"i is the remainder of Pei(x)

G(x)

Note that equation (5) is simply the remainder for the Frame without a CRC error, while equation (6) is the remainder for the same Frame with the CRC error.

Our task, therefore, is to solve equation 6 in order to find: Pei(x) for i=(O N-l)

0 Motorola, Inc. 1985 44

[This page contains 15 pictures or other non-text objects]

Page 2 of 3

0 M

MOTOROLA Technical Developments Volume 5 October 1985

THE SOLUTION

1.

2.

3.

1.

Let us define the following data structures:

A table with 2 elements: P(x), F(x) each element is an array of bits which represents a p...