如前所述,码字多项式的循环移位和消息多项式的编码需要将一个多项式除以另外一个多项式,这种操作可以由除法电路(反馈移位寄存器)实现。考虑两个多项式V(X)和g(X):

和

对于m≥p,图8.10的除法电路实现了多项式V(X)除以g(X)的除法运算,并求出了商和余项:

寄存器的各级首先初始化为0。第一个p移入V(X)的最高有效系数。在p次移位后,商输出是,这是商的最高项。对于商的每一个系数qi,都要从被除式中减去qig(X)。图8.10中的反馈连接实现了这个减法。在每次移位时,计算被除式中剩下的最左边p项和反馈项qig(X)之差,并将此作为寄存器中的内容。寄存器每移位一次,差就向前移动一位;阶数最高的项(刚开始时是0)被移出,而V(X)中下一个有意义的系数被移进。在总共m+1次进入寄存器的移位之后,商串行输出而余式留在寄存器中。

图8.10　多项式除法电路

【例8.9】除法电路

使用图8.10所示的除法电路将V(X)=X3+X5+X6(V=0001011)除以g(X)=(1+X+X3),求出商和余项。比较多项式除法的电路实现和手工实现。(www.daowen.com)

解:除法电路需要实现以下操作:

依据图8.10的一般形式,所需要的反馈移位寄存器如图8.11所示。假定寄存器的内容初始化为0,那么电路实现以下操作步骤:

4次移位后,商的系数{qi}串行出现在输出端,是1111,或者商多项式q(X)=(1+X+X2+X3),余式系数{pi}是100,或者余数多项式是p(X)=1。总之,电路计算V(X)/g(X)的结果为

多项式除法步骤如下:

移位后的输出,