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 + …a1X1 + 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 =>       1 1 0 1
1101 * 0 =>     0 0 0 0
1101 * 1 =>   1 1 0 1
1101 * 0 => 0 0 0 0
-------------------------
            1 0 0 0 0 0 1
      • 除法运算

在整数二进制运算中,带权值的除法运算的结果由商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 + …a1X1 + 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 = an-1Xn-1 + an-2Xn-2 + …a1X1 + a0,   b = bn-1Xn-1 + bn-2Xn-2 + …b1X1 + b0,

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

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

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

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

  • 模2乘法运算

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

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

乘法竖式如下:

1101 * 1 =>       1 1 0 1
1101 * 0 =>     0 0 0 0
1101 * 1 =>   1 1 0 1
1101 * 0 => 0 0 0 0
-------------------------------
          0 1 1 1 0 0 0 1
  • 矢量模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 教材教案, 教材与教案, 文章, 资料区

发表回复

相关链接