二进制多项式除法研究
1、伽罗华域二进制除法
matlab演示过程：
>> a = gf([1 0 1
1],1)
a
= GF(2) array.
Array
elements =
1
0
1
1
>> b = gf([1 1
0],1)
b = GF(2)
array.
Array
elements =
1
1
0
>> c = deconv(a,b)
c = GF(2)
array.
Array
elements =
1
1
>> [c,d] =
deconv(a,b)
c = GF(2)
array.
Array
elements =
1
1
d = GF(2)
array.
Array
elements =
0
0
0
1
>>
CRC-32计算举例：
>> a = gf([0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 1 1 0],1);
>> b = gf([1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1],1)
>> [c,d] =
deconv(a,b)
c = GF(2)
array.
Array
elements =
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
d = GF(2)
array.
Array
elements =
Columns 1 through 18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
Columns 19 through 36
0
1
1
0
0
0
1
0
0
1
1
1
1
1
1
1
1
1
Columns 37 through 48
1
1
1
1
1
0
1
1
0
1
0
0
>>
2、LFS二进制除法
3、用MATLAB实现上面两种方法
%二进制多项式除法研究
clear
clc
%输入区域
LFS_L =
4;%LFS长度
g = [1 0 1
1];%线性反馈一位寄存器系数,g=[1 0 1 1]对应g(x)=x^4 + (x^3 + x + 1)，最高位默认为1
A1 = [1 0
1 1 1];%输入序列，A1 = [1 0 1 1 1]对应x^4 + x^2 + x + 1
%下面的代码实现除法：(A1*x^LFS_L)/g
%举例：
� = [1 0 1
1 1]对应x^4 + x^2 + x + 1
%g=[1 0 1
1]对应g(x)=x^4 + (x^3 + x + 1)，最高位默认为1
%LFS_L =
4
%则：(A1*x^LFS_L)/g = [(x^4 + x^2 + x + 1)*x^4]/[x^4 +
(x^3 + x + 1)]
%除法结果应该为：x^4 + x^3 + 1，二进制格式：[1 1 0 0 1]
%余数结果应该为：x + 1，二进制格式：[0 0 1 1]
%初始化
D =
zeros(1,LFS_L);%寄存器当前状态
D_next =
zeros(1,LFS_L);%寄存器下一个状态
A2 =
zeros(1,LFS_L);%填充序列，添加到输入序列末尾
A =
[A1,A2];%相当于A1*x^LFS_L
LFS_out =
zeros(1,length(A));%线性反馈移位寄存器的输出，相当于除法结果
k =
0;
m =
0;
%1、伽罗华域方法
A_gf =
gf(A,1);
g_gf =
gf([1,g],1);
disp('%%%用伽罗华域方法实现二进制多项式除法%%%')
[div_rst_gf,div_remainder_gf] =
deconv(A_gf,g_gf)
%2、线性反馈移位寄存器方法
g =
g(end:-1:1);
for k =
1:length(A)
D_next(1) = xor(A(k),D(LFS_L));
for m = 2:LFS_L
if(g(m)==1)
D_next(m) = xor(D(m-1),D(LFS_L));
else
D_next(m) = D(m-1);
end
end
LFS_out(k) = D_next(LFS_L);
D = D_next;
end
disp('%%%用LFS实现二进制多项式除法%%%')
disp('线性反馈移位寄存器结构：')
disp('*************************************************************************')
disp('
_____________________________________________________________');
disp('
|g0
|g1
|g2
|g3
...
|gm');
disp('
v
v
v
v
...
|');
disp('输入序列--> + -->[D0]-- +
-->[D1]-- + -->[D2]-- +
-->[D3]--...
-->[Dm-1]--');
disp('*************************************************************************')
disp('线性反馈移位寄存器系数(高->低，不包含最高位gm，最高位默认为1)：'),g
disp('输入序列+填充序列(高->低,填充序列长度为LFS寄存器个数)：'),A
disp('A/g除法结果(高->低)：'),div_rst =
LFS_out(LFS_L:length(LFS_out)-1)%除法结果
disp('A/g余数(高->低)：'),div_remainder = D(end:-1:1)%余数
4、MATLAB运行结果
%%%用伽罗华域方法实现二进制多项式除法%%%
div_rst_gf
= GF(2) array.
Array
elements =
1
1
0
0
1
div_remainder_gf = GF(2) array.
Array
elements =
0
0
0
0
0
0
0
1
1
%%%用LFS实现二进制多项式除法%%%
线性反馈移位寄存器结构：
*************************************************************************
_____________________________________________________________
|g0
|g1
|g2
|g3
...
|gm
v
v
v
v
...
|
输入序列--> +
-->[D0]-- + -->[D1]-- +
-->[D2]-- + -->[D3]--...
-->[Dm-1]--
*************************************************************************
线性反馈移位寄存器系数(高->低，不包含最高位gm，最高位默认为1)：
g
=
1
1
0
1
输入序列+填充序列(高->低,填充序列长度为LFS寄存器个数)：
A
=
1
0
1
1
1
0
0
0
0
A/g除法结果(高->低)：
div_rst
=
1
1
0
0
1
A/g余数(高->低)：
div_remainder =
0
0
1
1