Browse Prior Art Database

Cyclic Redundancy Checking for Multiple Valued Logic

IP.com Disclosure Number: IPCOM000108088D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 4 page(s) / 137K

Publishing Venue

IBM

Related People

Barcelo Jr, P: AUTHOR [+3]

Abstract

Described is a cyclic redundancy checking (CRC) method (1) for multiple valued logic (MVL) (2,3) computer systems using various polynomials with coefficients of either zero or one.

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

Cyclic Redundancy Checking for Multiple Valued Logic

       Described is a cyclic redundancy checking (CRC) method
(1) for multiple valued logic (MVL) (2,3) computer systems using
various polynomials with coefficients of either zero or one.

      Generally, error detection codes are used in maintaining data
integrity during the transmission and storage between computer system
devices.  A popular technique for error detection is the use of
redundancy checks.  In data communications, a form of redundancy
checking is the CRC which utilizes cyclic redundancy code, also known
as the polynomial code.

      In prior art, shift register circuits were constructed to
compute CRC in hardware utilizing Exclusive OR gates and feedback
taps.  Fig.  1 illustrates a typical logic representation of a
generator polynomial G(x)=X**16+X**12+X**5+1.  CRC checking limited
to binary polynomial modulo 2 arithmetic is based on the rules of
algebraic field theory, such as the absence of borrows or carries for
subtraction or addition.  As a result, the algorithm can be performed
with the Exclusive OR function.

      Although the Exclusive OR function exists for binary systems as
defined by Boolean algebra, the Exclusive OR function does not exist
in MVL systems with a radix greater than 2.  Therefore, CRC
computations cannot be performed using the Exclusive OR function in
MVL systems.  Postian algebra defines the functions and rules of MVL,
and the cycle function is defined in Postian algebra as:
             A CYCLE B = (A plus B) mod N
where N is the base, or radix, of the system.  N is an integer
greater than 2.  For example, N = 3 for ternary systems.  A and B are
input variables with values being integers from 0 to N-1.  The cycle
function is shifting the value of A to the right by B.  For example,
in ternary, the values used are 0, 1, 2.  Therefore, the following is
observed:
     1 CYCLE 0 = 1,   1 CYCLE 1 = 2,   1 CYCLE 2 = 0,
2 CYCLE 2 = 1

      A function is also needed which can shift the value of A to the
left by B and is a counter-clockwise (CCW) cycle defined as:
           A CCW CYCLE B = (A minus B) mod N

 ...