多项式除法的数据结构
5.00/5 (5投票s)
本文在两个应用场景下，使用熟悉的長整數除法算法来实现多项式除法。
本文在两个应用场景下，使用熟悉的長整數除法算法来实现多项式除法。第一个应用涉及哈希表索引的计算，第二个应用涉及循环冗余校验码（CRC）的计算。在简要描述这两个应用之后，将描述用于多项式除法的数据结构。
多项式除法散列
一种基于代数编码理论的散列技术使用多项式除法来计算哈希表的索引（参见 Knuth, D. The Art of Computer Programming, Vol. 3: Sorting and Searching. Boston, Massachusetts: Addison Wesley, 1973, pp. 512-513; Second Edition, 1998, p. 520）。假设表的大小 \(m\) 是 2 的幂，即 ，对于某个 \(m > 1\)。为了将键散列到表中，该技术使用一个 m 次多项式
当 \(x = 2\) 时，它可以被解释为整数的二进制表示。
要散列的键被假定为一个 \(q\) 个字符的字符串。字符串的 ASCII 码构成一串比特，这无非是一个 \(n\) 比特（\(n = 8q\)）的二进制数。这样的数字也可以被解释为一个关于 \(x\) 的多项式
哈希表中的哈希索引是通过多项式除法 \(x^mK(x) \pmod{P(x)}\) 的余数获得的，其中使用模 2 算术。乘法 \(x^mK(x)\) 等同于将键的比特向左移动 \(m\) 位，除法的余数是多项式
它表示 \(m\) 比特的二进制数 \(h_{m-1}...h_1h_0\)。这个数字是表的正确索引，因为对于大小为 \(2^m\) 的表，索引范围从 0 到 \(2^m-1\)，每个索引都用 \(m\) 个比特进行二进制编码。
作为说明，考虑一个二进制编码为 110100110111 的键。该二进制数的多项式表示为
现在假设这个键要被索引到一个大小为 \(2^5\)（32 个元素，索引范围由 5 比特的数字 00000 到 11111 跨越）的哈希表中，并且除数多项式选择为
在模运算中，我们不关心商，只关心長除法 \(x^mK(x) \pmod{P(x)}\) 的余数。因此，除法使用 \(\oplus \) 进行减法（不借位），如下所示
11010011011100000
110101
------
00000111011100000
110101
------
001110100000
110101
------
0011110000
110101
------
00100100
110101
------
010001
余数为 10001，其整数等价物（17）是该键在哈希表中的索引。
散列中最难解决的问题是避免冲突，而明智地选择散列函数至关重要。在多项式除法散列的情况下，除数多项式决定了该方法的有效性。Knuth 指出，对于由 15 个比特组成的键，10 次的除数多项式可以为任意两个相差少于七个比特位置的键产生不同的余数。
循环冗余校验 (CRC) 码的计算
CRC 码用于计算机之间通过通信线路的数据传输，以及硬盘和 CPU 之间的数据传输，以检测突发错误（参见 Ercegovac, M.D., and T. Lang Digital Systems and Hardware/ Firmware Algorithms. New York: Wiley, 1985, pp. 744-745）。“突发”定义为高速传输的大块数据。
CRC 码由 \(k\) 个数据比特（或消息比特）和 \(r < k\) 个校验比特组成。校验比特是通过将一个 *数据比特向量* 除以一个 *生成器比特向量* 的余数得到的。为了降低除法运算的复杂性，减法是以按位方式进行的，不借位。因此，如果 \(X=x_{n-1}x_{n-2}...x_1x_0\) 和 \(Y=y_{n-1}y_{n-2}...y_1y_0\) 表示两个长度为 \(n\) 的比特向量，则减法 \(X-Y=D=d_{n-1}d_{n-2}...d_1d_0\) 按位进行，其中 \(d_i=x_i\oplus y_i\)，对于 \(0\leq i< n\)。
由于二进制数的比特等于 2 的多项式的系数，因此一个 \(k\) 比特的消息可以被看作是一个 \(k-1\) 次的多项式 \(M(x)\)。类似地，为了得到一个 \(r\) 比特的 CRC 校验向量，可以使用一个 \(r\) 次的多项式 \(G(x)\) 作为生成器。具体来说，消息多项式 \(M(x)\) 除以生成器多项式 \(G(x)\)，得到
其中 \(Q(x)\) 是商多项式，\(R(x)\) 是通过类似于長整數除法的过程获得的余数多项式。商多项式被丢弃，余数多项式就是消息的 CRC 码。为了数据传输的目的，通过将 CRC 码附加到消息后面来形成一个 *编码消息*。编码消息也可以看作是关于 \(x\) 的多项式，定义为
数据传输中的错误效果形式化描述如下。令 \(E(x)\) 表示错误多项式，它是一个比特向量，在消息中被错误修改（翻转）的比特位置为 1，在未更改的比特位置为 0。错误会将编码消息修改为形式为
这个 *有错误的编码消息* 模拟了通信线路上的噪声影响，并代表了接收到的消息。
为了验证传输错误是否发生，将接收到的消息除以相同的生成器多项式 \(G(x)\)。数学上执行该操作，
最终结果是由于异或算子自身的抵消性质。由于商多项式无关紧要，如果除法 \(E(x) / G(x)\) 的余数不等于零比特向量，即 \(E(x)\) 不能被 \(G(x)\) 整除，则会检测到传输错误。生成器多项式的选择是为了检测所有长度 *小于* 该多项式次数的突发错误。常见的生成器多项式次数为 16 或 32。
作为说明，考虑多项式除法散列示例的一个变体。一个系统要处理 12 比特的消息，生成器多项式的次数为 5 (CRC-5)，定义为
要传输的消息是 110100110111，其多项式表示为
消息的 CRC 码是通过長除法计算的，使用 \(\oplus \) 进行不借位的减法
11010011011100000
110101
------
00000111011100000
110101
------
001110100000
110101
------
0011110000
110101
------
00100100
110101
------
010001
得到余数 10001。因此，编码消息将是 11010011011110001。
现在假设传输错误改变了编码消息中 *三个* 连续的比特，如错误向量 00001110000000000 所描述。得到的错误编码消息是 11011101011110001，除以生成器多项式得到非零余数，因此检测到了错误。另一方面，如果发生错误，如 00101111100000000，改变了五个或更多比特，则错误消息将是 11111100111110001，除以生成器多项式将得到零余数，结果是该错误将未被检测到。
八位移位寄存器
通过多项式除法计算哈希索引和 CRC 码是同一问题的两个方面。这两种计算通常在硬件中通过移位寄存器来实现，但是可以定义一组数据结构在软件中高效地实现多项式除法。第一步是定义一个类来建模（即模拟）基本移位寄存器的操作。考虑建模一个通用的、组合式的 8 位移位寄存器，它具有以下硬件框图和功能规范。
寄存器有八个并行输入比特（\(i_7...i_0\)）、八个并行输出比特（\(o_7...o_0\)）、一个串行输入比特（\(s_{in}\)）、一个串行输出比特（\(s_{out}\)）以及三个命令输入（*load*、*clear* 和 *shift left*）。如果激活 clear 信号，则比特 \(o_7...o_0\) 都设置为零。如果激活 load 信号，则比特 \(i_7...i_0\) 被复制到比特 \(o_7...o_0\)。如果激活 shift left 信号，寄存器将其比特向左移动一位：\(s_{out}\leftarrow o_7,o_{k+1}\leftarrow o_k\) （对于 \(0\leq k< 7\)），并且 \(o_0\leftarrow s_{in}\)。 \(s_{in}\) 和 \(s_{out}\) 线允许将多个寄存器级联连接。输出比特 \(o_7...o_0\) 可以随时读取。
要在软件中建模硬件移位寄存器，可以定义一个 C# 类来将寄存器的比特表示为私有数据成员，并通过成员函数实现其操作。（此后，所有 C# 类都假定位于 PolynomialDivision 命名空间中，并且所有代码都假定在控制台应用程序的上下文中运行。）
public class _8bitShiftRegister
{
private byte data; // register's data bits
public _8bitShiftRegister()
{
data = 0x00;
}
public _8bitShiftRegister( byte _data )
{
data = _data;
}
public byte Data
{
get { return data; }
set { data = value; }
}
public void Load( byte _data ) // "Load" command (signal)
{ // "parameterized" version of Data.set
data = _data;
}
public byte Read() // "Read" command (signal)
{ // "parameterized" version of Data.get
return data;
}
public void Clear() // "Clear" command (signal)
{
data = 0x00;
}
public byte ShiftLeft( byte SerialIn ) // "Shift left" command (signal)
{
byte SerialOut = (byte)( data >> 7 );
data <<= 1; // shift left 1 bit
if ( SerialIn != 0x00 )
{
data |= 0x01;
}
return SerialOut;
}
public void Divide( _8bitShiftRegister source ) // "Divide" command
{
data ^= source.Data; // modulo 2 division via bitwise xor operator
}
public void Print( NL nl = NL.no )
{
Console.Write( String.Format( "{0:x2}", data ) );
if ( nl == NL.yes )
{
Console.WriteLine();
}
}
public void SelfTest()
{
byte sIn = 0;
int i;
Console.WriteLine( "Self-test 1\n" );
data = 0xff;
Print( NL.yes );
for ( i = 0; i < 8; ++i )
{
byte sOut;
sOut = ShiftLeft( sIn );
Console.WriteLine(
String.Format( "{0} <-- {1:x2} <-- {2}", sOut, data, sIn ) );
}
Console.WriteLine();
Console.WriteLine( "Self-test 2\n" );
sIn = 0x01
data = 0x00;
Print( NL.yes );
for ( i = 0; i < 8; ++i )
{
byte sOut;
sOut = ShiftLeft( sIn );
Console.WriteLine(
String.Format( "{0} <-- {1:x2} <-- {2}", sOut, data, sIn ) );
}
Console.WriteLine();
}
}// _8bitShiftRegister (class)
类 _8bitShiftRegister 的成员函数 Load、Read、Clear 和 ShiftLeft 构成了对寄存器行为规范的直接实现。函数 Divide 的定义是为了在实现多项式除法时使用此基本数据结构。它通过按位异或算子实现了模 2 算术中的 8 位除法。类似地，函数 Print 和 SelfTest 不是寄存器规范的一部分，但对于仿真很方便。可以通过以下程序来行使类的自测试能力。
class Program
{
static void Main( string[] args )
{
_8bitShiftRegister reg = new _8bitShiftRegister();
reg.SelfTest();
}
}// Program (class)
执行此程序后，在命令提示符窗口中会产生以下输出（此处以两列格式显示）。
| 自测试 1 | 自测试 2 |
第一个测试将 0xff 加载到寄存器中，将串行输入设置为 0，然后左移八次。第二个测试将 0x00 加载到寄存器中，将串行输入设置为 1，然后左移八次。程序输出的格式是 serial-out <-- data-bits <-- serial-in。读者可以验证结果是否符合预期。
使用移位数组进行多项式除法
为了通过移位比特来实现多项式除法，_8bitShiftRegister 类可以用作 *移位数组* 的基本数据结构。在进行長整數除法时，手算时是将除数在被除数下方移位，而在软件中，可以将被除数在除数上方移位。如果被除数存储在 8 位移位寄存器数组中，那么对数组进行左移操作是一项简单的任务。
为了能够用除数除被除数的某个前缀，必须有一种方法通过名称引用移位数组的某个部分以便对其进行显式操作，这可以通过 C/C++ 的 union 来命名移位数组的前缀来实现。（此时 mArg 和 mChars 的值无关紧要。）
union {
_8bitShiftRegister arg[ mArg ]; // argument to generator polynomial
_8bitShiftRegister chars[ mChars + mArg // character buffer
+ mArg ]; // + area to append zeros
} AC;
C# 没有 union 数据类型。但是，System.Runtime.InteropServices 命名空间提供了使用 struct 来模拟 unions 的功能，如下所示。
[StructLayout( LayoutKind.Explicit, Size = 8 )]
struct Union
{
[FieldOffset( 0 )]
public _8bitShiftRegister[] arg; // argument to generator polynomial
[FieldOffset( 0 )]
public _8bitShiftRegister[] chars; // character buffer (dividend) + area to append zeros
}// Union
这些信息是从 James Kovacs 在 Microsoft Developer Network 的网页上获得的。（在 Google 中使用搜索字符串“Union in C#”，第一个标题为“C# equivalent to C union”的链接指向他的文章。）重要的是要认识到这里定义的 Union 是一个 *类型*，而不是一个变量。
假设要操作的多项式的最大次数为 31，因此需要 32 位表示，并且被除数始终由 8 的倍数个比特表示。此后，所有变量和函数将分别是类 ShiftArray 的数据成员和方法。（完整代码在文件 ShiftArray.cs 中）。数据成员的定义以及注释解释如下。
private _8bitShiftRegister[] poly, // divisor polynomial
mask; // mask used by function ShiftLeftToMSb
private Union AC;
private uint uiPoly, // uint equivalent of poly
uiMask; // uint equivalent of mask
private uint[] uiDmask; // masks used to print a polynomial
private int nBits, // # of bits in AC.chars
nBytes, // # of bytes in AC.chars == ceiling( nBits / 8 )
cBits, // current # of bits in AC.chars
cBytes, // current # of bytes in AC.chars
divMSb, // most significant bit of divisor polynomial
pBits, // degree (# of bits) of divisor polynomial
quot, // quotient of divMSb / 8
max, // maximum print position for AC.chars
mMessage; // # of characters in message
private byte[] message; // copy of message in AC.chars
构造函数为所有数组分配空间，并使用文件 Cnst.cs 中定义的常量初始化数据成员。然后它调用函数 GenerateBitMasks 来初始化用于打印多项式的位掩码数组，然后调用函数 InitPolyAndMask 来初始化生成器多项式和在左移时使用的最高有效比特的掩码。
public ShiftArray( int pOf2, uint uiP, int msb )
{
int i;
poly = new _8bitShiftRegister[ Cnst.mArg ]; // divisor polynomial
mask = new _8bitShiftRegister[ Cnst.mArg ]; // mask used by function ShiftLeftToMSb
AC.arg = new _8bitShiftRegister[ Cnst.mArg ]; // argument to generator polynomial
for ( i = 0; i < Cnst.mArg; ++i )
{
poly[ i ] = new _8bitShiftRegister();
mask[ i ] = new _8bitShiftRegister();
AC.arg[ i ] = new _8bitShiftRegister();
}
AC.chars = new _8bitShiftRegister[ Cnst.mChars + Cnst.mArg2 ]; // arg/buffer + area to
// append zeros and remainder
for ( i = 0; i < Cnst.nChars; ++i )
{
AC.chars[ i ] = new _8bitShiftRegister();
}
message = new byte[ Cnst.mChars + Cnst.mArg ];
cBits = nBits = Util.Min( pOf2, Cnst.mBits );
cBytes = nBytes = Util.BitsToBytes( nBits );
max = cBytes + Cnst.mArg;
divMSb = msb;
pBits = msb + 1;
quot = divMSb >> 3;
Console.WriteLine( "Initializing ShiftArray\n" );
Console.WriteLine( String.Format( "bits == {0}, bytes == {1}", nBits, nBytes ) );
Console.WriteLine( String.Format( "generator msb == {0}, bits == {1}\nquot == {2}",
divMSb, pBits, quot ) );
GenerateBitMasks();
InitPolyAndMask( uiP );
}// ShiftArray
private void GenerateBitMasks()
{
uint m = 0x00000001;
uiDmask = new uint[ 32 ];
for ( int i = 0; i < 32; ++i )
{
uiDmask[ i ] = m;
m <<= 1;
}
}
private void InitPolyAndMask( uint uiP )
{
uint uiM;
uiPoly = uiP;
uiMask = ( (uint)1 ) << divMSb;
uiM = uiMask;
for ( int i = Cnst.mArg - 1; i > -1; --i )
{
poly[ i ].Load( (byte)uiP );
mask[ i ].Load( (byte)uiM );
uiP >>= 8;
uiM >>= 8;
}
Console.Write( "Generator polynomial" );
PrintPolynomial( uiPoly );
PrintRange( " MSb mask == 0x", mask, Cnst.mArg );
}// InitPolyAndMask
在描述更多函数之前，我将处理函数 SelfTest（以 _8bitShiftRegister 类的自测试功能为精神定义的），它演示了 CRC 处理的整个过程。此函数引导了代码的自上而下的开发。
public void SelfTest()
{
LoadString( "M.I.T.EE" );
GenerateCRC();
PrintCRC();
VerifyCRC();
}// SelfTest
函数 LoadString 接收一个字符串形式的消息（str），清除 AC.chars 的 AC.arg 部分，在 AC.arg 部分之后将字符串复制到 AC.chars 中，为 CRC 验证目的制作原始消息的副本，并清除 AC.chars 的其余部分。然后它计算要处理的比特数和字节数。
public void LoadString( string str )
{
int i, j, m, n = str.Length, p;
m = n > Cnst.mChars ? Cnst.mChars : n; // maximum number of characters to load
p = m + Cnst.mArg; // add size of area to append zeros
for ( i = 0; i < Cnst.mArg; ++i ) // clear AC.arg section of AC.chars
{
AC.chars[ i ].Clear();
}
for ( i = Cnst.mArg, j = 0; i < p; ++i, ++j ) // load characters from str
{
byte b = (byte)str[ j ];
AC.chars[ i ].Load( b );
message[ j ] = b;
}
mMessage = j;
while ( i < Cnst.nChars ) // clear remaining part of AC.chars
{
AC.chars[ i++ ].Clear();
}
cBits = (n << 3) + divMSb;
cBytes = Util.BitsToBytes( cBits );
PrintMessage( "loaded" );
}// LoadString
正如函数 GenerateCRC 中的注释所解释的，它首先对齐被除数和除数。然后，只要还有重要的比特要处理，函数就会重复应用除数多项式到被除数，并重新对齐被除数和除数。最后，剩余的比特（构成 CRC）被全部左移。
public void GenerateCRC()
{
Console.WriteLine( "\nGenerating CRC\n" );
Console.WriteLine( "cBits cBytes | arg. | chars\n" );
ShiftLeftToMSb( DCR.no ); // align dividend with divisor
while ( cBits > pBits )
{
ArgDivPoly(); // apply divisor polynomial
ShiftLeftToMSb(); // re-align dividend with divisor
}
ShiftLeftToEnd(); // shift remainder all the way to the left
}// GenerateCRC
就比特操作而言，左移函数和函数 ArgDivPoly 是不言自明的，并在下面定义。在整个定义中，请注意对 _8bitShiftRegister 功能的使用。
public void ShiftLeftToMSb( DCR dcr = DCR.yes )
{
byte mskByte = mask[ 3 - quot ].Read();
while ( ( cBits > 0 )
&&
( ( AC.arg[ 3 - quot ].Read() & mskByte ) != mskByte ) )
{
ShiftLeft( dcr );
}
Print();
}// ShiftLeftToMSb
public void ArgDivPoly()
{
for ( int i = 0; i < Cnst.mArg; ++i )
{
AC.arg[ i ].Divide( poly[ i ] );
}
Print();
}// ArgDivPoly
public void ShiftLeftToEnd()
{
if ( !ZeroArg() )
{
Console.WriteLine( "\nShifting AC.arg to end\n" );
while ( ( AC.arg[ 0 ].Read() & 0x80 ) != 0x80 )
{
ShiftLeft( DCR.no );
}
Print();
}
}// ShiftLeftToEnd
private bool ZeroArg() // is AC.arg all 0's ?
{
bool zero = true;
for ( int i = 0; i < Cnst.mArg; ++i )
{
if ( AC.arg[ i ].Read() != 0x00 )
{
zero = false; break;
}
}
return zero;
}// ZeroArg
public void ShiftLeft( DCR dcr )
{
int i, m = Cnst.mChars + ( Cnst.mArg << 1 );
byte Cout;
if ( cBits > 0 )
{
Cout = 0;
for ( i = m - 1; i > -1; --i )
{
Cout = AC.chars[ i ].ShiftLeft( Cout );
}
if ( dcr == DCR.yes )
{
--cBits;
if ( ( cBits % 8 ) == 0 )
{
--cBytes;
}
}
}
}// ShiftLeft
在生成 CRC 的过程中，会调用许多打印函数进行日志记录。这些函数（PrintPolynomial、Print、PrintACarg、PrintACchars 和 PrintCRC）定义在文件 ShiftArray.cs 中，为了简洁起见，我将不作描述。生成样本消息的 CRC 在命令提示符窗口中产生的输出如下（为节省空间，以两列格式显示）。十六进制表示的消息中的两个末尾零 *不* 是消息的一部分。
Initializing ShiftArray
bits == 64, bytes == 8
generator msb == 5, bits == 6
quot == 0
Generator polynomial == 0x00000035 == x^5 + x^4 + x^2 + 1
MSb mask == 0x00000020
Message: 'M.I.T.EE' loaded
4d2e492e542e454500
Generating CRC
cBits cBytes | arg. | chars
69 9 000000269724972a1722a28000
69 9 000000139724972a1722a28000
68 9 000000272e492e542e45450000
68 9 000000122e492e542e45450000
67 9 000000245c925ca85c8a8a0000
67 9 000000115c925ca85c8a8a0000
66 9 00000022b924b950b915140000
66 9 00000017b924b950b915140000
65 9 0000002f724972a1722a280000
65 9 0000001a724972a1722a280000
64 8 00000034e492e542e4545000
64 8 00000001e492e542e4545000
59 8 0000003c925ca85c8a8a0000
59 8 00000009925ca85c8a8a0000
57 8 000000264972a1722a280000
57 8 000000134972a1722a280000
56 7 0000002692e542e4545000
56 7 0000001392e542e4545000
55 7 0000002725ca85c8a8a000
55 7 0000001225ca85c8a8a000
54 7 000000244b950b91514000
54 7 000000114b950b91514000
53 7 00000022972a1722a28000
53 7 00000017972a1722a28000
52 7 0000002f2e542e45450000
52 7 0000001a2e542e45450000
51 7 000000345ca85c8a8a0000
51 7 000000015ca85c8a8a0000
46 6 0000002b950b91514000
46 6 0000001e950b91514000
45 6 0000003d2a1722a28000
45 6 000000082a1722a28000
43 6 00000020a85c8a8a0000
43 6 00000015a85c8a8a0000
42 6 0000002b50b915140000
42 6 0000001e50b915140000
41 6 0000003ca1722a280000
41 6 00000009a1722a280000
39 5 0000002685c8a8a000
39 5 0000001385c8a8a000
cBits cBytes | arg. | chars
38 5 000000270b91514000
38 5 000000120b91514000
37 5 000000241722a28000
37 5 000000111722a28000
36 5 000000222e45450000
36 5 000000172e45450000
35 5 0000002e5c8a8a0000
35 5 0000001b5c8a8a0000
34 5 00000036b915140000
34 5 00000003b915140000
30 4 0000003b91514000
30 4 0000000e91514000
28 4 0000003a45450000
28 4 0000000f45450000
26 4 0000003d15140000
26 4 0000000815140000
24 3 00000020545000
24 3 00000015545000
23 3 0000002aa8a000
23 3 0000001fa8a000
22 3 0000003f514000
22 3 0000000a514000
20 3 00000029450000
20 3 0000001c450000
19 3 000000388a0000
19 3 0000000d8a0000
17 3 00000036280000
17 3 00000003280000
13 2 000000328000
13 2 000000078000
10 2 0000003c0000
10 2 000000090000
8 1 0000002400
8 1 0000001100
7 1 0000002200
7 1 0000001700
6 1 0000002e00
Shifting AC.arg to end
6 1 b800000000
CRC: b8
函数 VerifyCRC 用于检查生成的 CRC 是否正确。为此，该函数重新加载原始消息，将 CRC 附加到消息，然后再次调用 GenerateCRC。结果应该是一个等于零的 CRC。
private void VerifyCRC()
{
Console.WriteLine( "\nVerifying CRC\n" );
ReloadMessage();
AppendCRC();
GenerateCRC();
PrintCRC();
}// VerifyCRC
private void ReloadMessage()
{
// Copy message into AC.chars without
// altering AC.arg
for ( int i = Cnst.mArg, j = 0; i < max; ++i, ++j )
{
AC.chars[ i ].Load( message[ j ] );
}
PrintMessage( "reloaded" );
}// ReloadMessage
private void AppendCRC()
{
int crcBytes, crcBits, i, j;
Console.WriteLine( "\nAppending CRC\n" );
crcBytes = cBytes;
crcBits = cBits;
cBytes = nBytes;
cBits = nBits;
i = cBytes + Cnst.mArg;
j = 0;
while ( crcBytes > 0 )
{
AC.chars[ i++ ].Load( AC.arg[ j ].Read() );
AC.arg[ j++ ].Clear();
++cBytes;
--crcBytes;
if ( crcBits >= 8 )
{
crcBits -= 8;
cBits += 8;
}
}
cBits += crcBits;
Print();
}// AppendCRC
CRC 验证过程中产生的输出如下。（同样，消息的十六进制表示中的两个末尾零 *不* 是消息的一部分。）
Verifying CRC
Message: 'M.I.T.EE' reloaded
4d2e492e542e454500
Appending CRC
70 9 000000004d2e492e542e4545b8
Generating CRC
cBits cBytes | arg. | chars
70 9 000000269724972a1722a2dc00
70 9 000000139724972a1722a2dc00
69 9 000000272e492e542e4545b800
69 9 000000122e492e542e4545b800
68 9 000000245c925ca85c8a8b7000
68 9 000000115c925ca85c8a8b7000
67 9 00000022b924b950b91516e000
67 9 00000017b924b950b91516e000
66 9 0000002f724972a1722a2dc000
66 9 0000001a724972a1722a2dc000
65 9 00000034e492e542e4545b8000
65 9 00000001e492e542e4545b8000
60 8 0000003c925ca85c8a8b7000
60 8 00000009925ca85c8a8b7000
58 8 000000264972a1722a2dc000
58 8 000000134972a1722a2dc000
57 8 0000002692e542e4545b8000
57 8 0000001392e542e4545b8000
56 7 0000002725ca85c8a8b700
56 7 0000001225ca85c8a8b700
55 7 000000244b950b91516e00
55 7 000000114b950b91516e00
54 7 00000022972a1722a2dc00
54 7 00000017972a1722a2dc00
53 7 0000002f2e542e4545b800
53 7 0000001a2e542e4545b800
52 7 000000345ca85c8a8b7000
52 7 000000015ca85c8a8b7000
47 6 0000002b950b91516e00
47 6 0000001e950b91516e00
46 6 0000003d2a1722a2dc00
46 6 000000082a1722a2dc00
44 6 00000020a85c8a8b7000
44 6 00000015a85c8a8b7000
43 6 0000002b50b91516e000
43 6 0000001e50b91516e000
42 6 0000003ca1722a2dc000
42 6 00000009a1722a2dc000
cBits cBytes | arg. | chars
40 5 0000002685c8a8b700
40 5 0000001385c8a8b700
39 5 000000270b91516e00
39 5 000000120b91516e00
38 5 000000241722a2dc00
38 5 000000111722a2dc00
37 5 000000222e4545b800
37 5 000000172e4545b800
36 5 0000002e5c8a8b7000
36 5 0000001b5c8a8b7000
35 5 00000036b91516e000
35 5 00000003b91516e000
31 4 0000003b91516e00
31 4 0000000e91516e00
29 4 0000003a4545b800
29 4 0000000f4545b800
27 4 0000003d1516e000
27 4 000000081516e000
25 4 00000020545b8000
25 4 00000015545b8000
24 3 0000002aa8b700
24 3 0000001fa8b700
23 3 0000003f516e00
23 3 0000000a516e00
21 3 0000002945b800
21 3 0000001c45b800
20 3 000000388b7000
20 3 0000000d8b7000
18 3 000000362dc000
18 3 000000032dc000
14 2 00000032dc00
14 2 00000007dc00
11 2 0000003ee000
11 2 0000000be000
9 2 0000002f8000
9 2 0000001a8000
8 1 0000003500
8 1 0000000000
0 0 00000000
CRC: 00
正如预期的那样，结果 CRC 为零。最后要做的就是编写一个主程序来启动移位数组自测试的 CRC 计算。
namespace PolynomialDivision
{
class Program
{
static void Main( string[] args )
{
ShiftArray shArray = new ShiftArray( 64, 0x00000035, 5 );
shArray.SelfTest();
}
}// Program (class)
}// PolynomialDivision (namespace)
此程序创建一个移位数组，将一个 2 的幂（64 位）传递给它，以帮助计算需要处理的最小比特数，生成器多项式的十六进制表示，以及除数最高有效比特的位置。
运行代码
要执行代码，请将其解压缩到 Visual Studio 2010（或更高版本）的 Projects 目录下的合适子目录中，并将其构建为控制台应用程序。本文关于多项式除法的数据结构到此结束。