Menu Close

二进制数域及计算

由于随着数字技术和计算行业的发展,2进制数域的研究也越来越成熟,目前在加解密,加扰,解扰,信道编码,差错校验的领域得到广泛应用。因此本文着重介绍二进制数域的相关内容。

1. 二进制数域定义

在0,1两个值上规定了加、减、乘、除(除数不为零)的四则运算的闭集,称为二进制数域。数域可以用F[0,1]表示。

  • 二进制数域的属性

    • 在定义的数域中可以实现加、减、乘、除(除数不为0)四则运算;
    • 0,1元素,数域中包含元素0和元素1;
    • 逆元素(反元素),如元素a,则-a,1/a也应该包含在数域中。即应该满足a+(-a)=0, a *(1/a)=1(a!=0);
    • 满足加法和乘法运算的交换律,如a+b=b+a, a*b=b*a等。
    • 满足加法和乘法运算的结合律,如 (a+b)+c=a+(b+c);
    • 满足加法和乘法运算的分配律,如a(b+c)=ab+ac;
    • 如果减法和除法用逆元素表示,也满足交换律、结合律以及分配律。

2. 二进制数域的计算

根据二进制数域的属性,二进制数域满足如下运算,假设a,b为2进制数

  • 加法

0+0=0; 0+1=1; 1+0=1; 1+1=0           与“异或”运算等效

a+b=b+a =a^b                                      “ ^ ” 表示异或运算

  • 减法

0-0=0;0-1=1; 1-0=1; 1-1=0;              与“异或”运算等效

a-b=b-a =a^b                                       “ ^ ” 表示异或运算

  • 乘法

0*0=0; 0*1=0; 1*0=0;1*1=1; “与”运算

  • 除法

0/1=0; 1/1=1;

  • 反运算

~0=1; ~1=0;

3. 有序二进制组成的矢量运算

在二进制数域内由0,1组成的n维矢量可以表示如下:

  • 方括号括起来的有序二进制数,如a=[an-1 an-2…a1 a0], a=[10001]
  • 由花括号括起来的有序二进制数,如 a={an-1 an-2…a1 a0}, a={10001}
  • 由标识加有序二进制数表达的二进制数,如a=5’b10011;
  • 由多项式表达的2进制数,如 a=an-1Xn-1+an-2Xn-2+…a1X+a0;

式中an-1 an-2…a1 a0都为[0,1]的二进制数。

  • 二进制矢量运算

    • 带权值的矢量运算

      • 加减运算

带权值的运算,由于二进制的权值为2的幂,因此在做加法运算时逢2进1,低位运算的进位位参与相邻高位的运算,在做减法时借当2。如a=4’b1101, b=4’b0101, a+b=4’b1101+4’b0101=5’b10010。

a-b=4’b1101-4’b0101=4’b1000。

b-a=4’b0101-4’b1101=5’b11000

      • 乘法运算

乘法运算可以通过被乘数错位相加(带进位位)

如a*b=4’b1101 * 4’b0101

乘法竖式如下:

1101 *1 1101

1101 *0 => 0000

1101 *1 1101

1101 *0 0000

1000001

      • 除法运算

在整数二进制运算中,带权值的除法运算的结果由商Q和余数R组成,一般采用除法竖式计算,如a=8’b10110101,b=4’b1011; 计算竖式如下

%title插图%num

图1 除法运算

计算结果: Q=4’b110, R=3’b101

      • 整除:

整除即除法结果Q为有序二进制数, 余数R为0。如何做到整除呢,就是被除数减去余数后的值即可被整除(余数为0)。

如果a,b分别为分别为2进制数的被除数和除数,商为Q,R为余数,其中 a=8’b10110101, b=5’b1101, Q=4’b110,R=3’b101整除被除数的求解可按下列步骤进行:

(1)计算前在a右边补3个0,得实际参与运算得被除数a1=11’b1011_0101_000,

(2)将被除数a1减去余数R,得m=a1-R=11’b1011_0101_000-3’b101=11’b1011_0100_011

(3)将m除以b,得余数为零, 即m是小于等于a1,且最接近a1得值,计算过程如图2

%title插图%num

图2 二进制整除

4. 不带权值的运算

不带权值的二进制矢量没有权值的概念,矢量仅仅是表示有序数列,如a=an-1Xn-1+an-2Xn-2+…a1X+a0;中X幂仅表示不同位置的元素,因此不带权值的加减运算既没有进位位,也没有借位位,不带权值的2进制运算又称为模2运算

  • 加减法法运算

两个二进制矢量加法运算仅考虑矢量中对应位运算,有进位,则丢弃进位位。减法也是一样,仅对矢量中对应位运算,因此对应位应满足下式,

    • 模2加法

0+0=0; 0+1=1; 1+0=1; 1+1=0 “异或”运算

m+n=n+m =m^n m,n为二进制数, “ ^ ” 表示异或运算

    • 模2减法

0-0=0;0-1=1; 1-0=1; 1-1=0; “异或”运算

m-n=n-m =m^n m,n为二进制数, “ ^ ” 表示异或运算

假设a=a=an-1Xn-1+an-2Xn-2+…a1X+a0, b=bn-1Xn-1+bn-2Xn-2+…b1X+b0,

a+b=(an-1+bn-1)Xn-1+(an-2+bn-2)Xn-2+…(a1+b1)X+(a0+b0

=(an-1^bn-1)Xn-1+(an-2^bn-2)Xn-2+…(a1^b1)X+(a0^b0

    1. b=(an-1-bn-1)Xn-1+(an-2-bn-2)Xn-2+…(a1-b1)X+(a0-b0

=(an-1^bn-1)Xn-1+(an-2^bn-2)Xn-2+…(a1^b1)X+(a0^b0

  • 模2乘法运算

乘法运算可以通过被乘数错位相加(不带进位位)

如a*b=4’b1101 * 4’b0101

乘法竖式如下:

1101 *1 1101

1101 *0 => 0000

1101 *1 1101

1101 *0 0000

01110001

  • 矢量模2除法

模2除法一般也常用竖式表达,只是在做减法运算时不产生借位,多项式中Xn仅表示矢量中二进制数的位置。

假设a=8’b10110011, b=5’b11001,则模2除法如图3所示,

%title插图%num

图3 二进制模2除法

  • 矢量模2整除

模2整除m的求解步骤与带权值的矢量求法类似,只是在加减运算中始终遵循模2运算的原则,假设a=8’b10110011, b=5’b11001,Q=8’b1101_0100,R=4’b0100,

a1=12’b1011_0011_0000, m=a1-R=12’b1011_0011_0000-4’b0100

按照模2运算的原则m=12’b1011_0011_0100,

    • 模2除法竖式

%title插图%num

图4 模2整除

从图4的结果可以看出m的求解正确,而且m=a1-R的减法运算,变成了拼接运算,即直接将余数拼接在被除数a1的右边即可求得能被整除的数m。

  • 多项式模2除法

假设a=8’b10110011, b=5’b11001,则a, b可以表示为多项式的形式

a=X7+X5+X4+X+1 , b=X4+X3+1,将a左移4位的a1=X11+X10+X8 +X5+X4,相当于在a后面补4个0。

%title插图%num

图5 多项式模2除

图5计算结果,最后的商Q=X7+X6+X4+X2, 余数R=X2 (4’b0100)

  • 多项式整除

多项式整除,选择m=a1-R=X11+X10+X8 +X5+X4-X2,由于模2加法与加法相同,因此m=X11+X10+X8 +X5+X4+X2 , 这也相当于将余数直接拼接在a1的右边。结果可以通过图5验证。

%title插图%num 图6  多项式模2整除

模2加减乘除由于计算简单,在数字通信中被广泛应用于差错编码,信道编码等领域。后续内容将会讲解模2运算的应用。

 

 

Posted in FPGA, FPGA, 教材与教案, 文章, 资料区

发表评论

相关链接