|
DataMuseum.dkPresents historical artifacts from the history of: Rational R1000/400 Tapes |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about Rational R1000/400 Tapes Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - metrics - downloadIndex: C T
Length: 4997 (0x1385)
Types: TextFile
Names: »CRC_THEORY«
└─⟦180fe333a⟧ Bits:30000405 8mm tape, Rational 1000, SW CATALOG, 10_20_0
└─⟦180fe333a⟧ Bits:30000537 8mm tape, Rational 1000, SW Catalog 10_20_0
└─⟦5cb1d1d7f⟧ »DATA«
└─⟦3b1ee7bd8⟧
└─⟦this⟧
This CRC algorithm is taken from "A CRC Algorithm", Marton
& Frambs, Honeywell Computer Journal, Vol. 5, No. 3, 1971.
Here's a summary:
CRC calculation is often implemented in hardware by a 16-bit
shift register, as follows:
+-- R(15) <-- XOR <-- R(14) ... R(1) <-- XOR <-- R(0) <----+
| ^ ^ |
| | | |
| | | |
| P(15) --> AND ... P(1) --> AND P(0) --> AND
| ^ ^ |
| | | |
V | | |
XOR ------------+----------- ... -----------+----------------+
^
|
|
+-- D(0) <-- D(1) ... <-- D(7)
R is the CRC accumulator; R(I) is the Ith bit, MSB = 15.
P is the CRC polynomial bit mask, that is, P(I) = 1 if
X**I is a polynomial term. D is a data byte, MSB = 7.
AND and XOR are the usual single-bit boolean operators.
To calculate a checksum, R is initialized to some value
(usually all 0's or all 1's), and data bits are shifted
into R in transmission order. When all the data bits
have been shifted in, the value in R is the checksum.
Data bits are transmitted least significant bit first,
but CRC bits are transmitted most significant bit first.
This software algorithm also has an accumulator R, which is
initialized to some value, but data bits are accumulated
into R a whole byte at a time. The accumulation algorithm
uses a pre-calculated table of the zero-preset CRC's of all
256 possible data bytes.
In the software algorithm, all checksums (including the
table entries and accumulation registers) are stored
bit-reversed, that is, the byte bit sequence MSB..LSB
corresponds to the checksum bit sequence LSB..MSB.
This is done so that the checksum gets transmitted in
the right bit order when transmitted as bytes, and to
speed up the accumulation algorithm.
To construct the table, we first calculate zero-preset CRC's
for each data byte having exactly one bit = 1. M(0) is the
CRC for D = 1, and M(7) is the CRC for D = 128. Note that
this terminology is bit-reversed relative to Marton & Frambs.
What they call M1 is M(7) here, and what they call M8 is M(0).
M(7) is the CRC polynomial P. In the shift register, D(0..6)
leave R = 0, and D(7) causes P to be stored into R:
R(15) <-- XOR <-- R(14) ... R(1) <-- XOR <-- R(0) <----+
^ ^ |
| | |
| | |
P(15) --> AND ... P(1) --> AND P(0) --> AND
^ ^ |
| | |
| | |
D(7) = 1 ------+----------- ... -----------+----------------+
For M(6), D(6) stores P into R, and D(7) transforms R thus:
+-- R(15) <-- XOR <-- R(14) ... R(1) <-- XOR <-- R(0) <----+
| ^ ^ |
| | | |
| | | |
| P(15) --> AND ... P(1) --> AND P(0) --> AND
| ^ ^ |
| | | |
| | | |
+--------------+----------- ... -----------+----------------+
If R(15) = 0, then R := Shift_Left (R).
If R(15) = 1, then R := Shift_Left (R) XOR P.
We iterate this same transformation to calculate M(0..5).
Having calculated M(0..7), we can calculate the entire table
of checksums. Each entry is the XOR sum of the M values for
each of the non-zero bits in the byte, since for any two bytes
X and Y, CRC (X XOR Y) = CRC (X) XOR CRC (Y).
The accumulation algorithm implements the following data flow:
D(7..0) R(8..15) R(0..7)
| | |
| | |
| V |
+--------> XOR +------+
| |
| |
V |
checksum table |
| | |
| | |
V V |
M(8..15) M(0..7) |
| | |
| | |
V | |
XOR <--------------+
| |
| |
V V
R(8..15) R(0..7)