二进制数域及计算

二进制数域及计算

由于随着数字技术和计算行业的发展，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 = [a_n-1 a_n-2…a₁ a₀]， a = [10001]
• 由花括号括起来的有序二进制数，如 a = {a_n-1 a_n-2…a₁ a₀}， a = {10001}
• 由标识加有序二进制数表达的二进制数，如a = 5’b10011;
• 由多项式表达的2进制数，如 a = a_n-1X^n-1 + a_n-2X^n-2 + …a₁X¹ + a₀;

式中a_n-1 a_n-2…a₁ a₀都为[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; 计算竖式如下

图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

图2 二进制整除

4. 不带权值的运算

不带权值的二进制矢量没有权值的概念，矢量仅仅是表示有序数列，如a = a_n-1X^n-1 + a_n-2X^n-2 + …a₁X¹ + a₀;中X幂仅表示不同位置的元素，因此不带权值的加减运算既没有进位位，也没有借位位，不带权值的2进制运算又称为模2运算。

• 加减法法运算

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

• • 模2加法

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

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

1. • 模2减法

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

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

假设 a = a_n-1X^n-1 + a_n-2X^n-2 + …a₁X¹ + a₀,   b = b_n-1X^n-1 + b_n-2X^n-2 + …b₁X¹ + b₀,

a + b = (a_n-1 + b_n-1)X^n-1 + (a_n-2 + b_n-2)X^n-2 + …(a₁ + b₁)X¹ + (a₀ + b₀)

= (a_n-1^b_n-1)X^n-1 +  (a_n-2^b_n-2)X^n-2 + …(a₁^b₁)X¹ + (a₀^b₀)

a – b = (a_n-1 – b_n-1)X^n-1 + (a_n-2 – b_n-2)X^n-2 + …(a₁ – b₁)X¹ + (a₀ – b₀)

= (a_n-1^b_n-1)X^n-1 + (a_n-2^b_n-2)X^n-2 + …(a₁^b₁)X¹ + (a₀^b₀)

• 模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除法一般也常用竖式表达，只是在做减法运算时不产生借位，多项式中Xⁿ仅表示矢量中二进制数的位置。

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

图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除法竖式

图4 模2整除

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

• 多项式模2除法

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

a = X⁷ + X⁵ + X⁴ + X + 1 ， b = X⁴ + X³ + 1，将a左移4位的a1 = X¹¹ + X¹⁰ + X⁸ + X⁵ + X⁴，相当于在a后面补4个0。

图5 多项式模2除

图5计算结果，最后的商Q = X⁷ + X⁶ + X⁴ + X², 余数R = X² （4’b0100)

• 多项式整除

多项式整除，选择m = a1 – R = X¹¹ + X¹⁰ + X⁸ + X⁵ + X⁴ – X²,由于模2加法与加法相同，因此m = X¹¹ + X¹⁰ + X⁸ + X⁵ + X⁴ + X² , 这也相当于将余数直接拼接在a1的右边。结果可以通过图5验证。

图6  多项式模2整除

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