数字逻辑基础

概念

物理量有两种表示方法:模拟表示法数字表示法

模拟量和数字量的主要区别:模拟量=连续,数字量=离散

数字系统是用来处理逻辑信息或以数字形式表示的物理量的器件组合,即其数值只能取离散值。或称是有一组或几种基本的标准逻辑门来构成的复杂的、使用数字量来传递和加工、处理信息的实际工程系统

最常见的数字系统:计算机、数字音像及世界上最大的数字系统——手机电话系统

数字逻辑电路是以逻辑门为基本单元构成的复杂的数字系统中的硬件部分。

逻辑门:以能完成独立逻辑功能的一组电子元件和器件所组成的线路。

模拟系统所包含的装置能处理以模拟形式表示的物理量。

数字技术的优点:易设计、信息存储方便、操作可编程、数字电路抗干扰能力强、多数数字电路能制造在IC芯片上

数字技术的缺点:

  1. 由于必须在信息的模拟形式与数字形式之间进行转换,从而增加了系统的复杂性和费用;
  2. 数字(二进制数)信号的处理需要时间。所需要的数据越精确,处理时间越长。

当涉及到模拟输入、输出时,为了利用数字技术的优点,必须采用下面3步:

  1. 把实际中的模拟输入转换为数字形式;
  2. 数字信息处理;
  3. 把数字输出变换为模拟输出。

原则:随着信号在系统中的流动,在输入通道中尽可能早地把信号数字化,在输出通道中尽可能晚地把信号转换为模拟信号。

数的表示

进制表示

不同进位计数制的数值具有等值关系:

其中M是十进制数N的S进制形式,K是N的T进制形式。

也就是说,加了括号的括号内一定是转换数制后的数,不加括号就是原来的十进制数。例如:

数值转换时小数位数的确定:

数的表示和运算

计算机中表示小数点位置的方法通常有两种:定点表示法和浮点表示法。

定点表示法

小数点位置固定,一般固定在数的最高位之前或最低位之后。

浮点表示法

例如,二进制数101.1和10.11可表示为:

其中10和11是二进制数,转换为十进制就是2和3.

因此,这两个二进制数可以用阶码尾数表示:

这就是浮点表示法。表示时需要将一个字长划分为两部分,分别用来表示阶码和尾数,两个部分的最高位分别为各自的符号位

例如,规定一个16位字长的前5位表示阶码,后11位表示尾数:

0 0011 0 1011000000

0 0010 0 1011000000

原码:符号位加上真值的绝对值,即用第一位表示符号,其余位表示值。

因为第一位是符号位, 所以8位二进制数的取值范围就是[-127, 127]

反码:正数的反码是其本身;负数的反码是在其原码的基础上,符号位不变,其余各个位取反。

补码:正数的补码就是其本身;负数的补码是在其原码的基础上,符号位不变,其余各位取反,最后+1(即在反码的基础上+1)。

一篇可参考的博客:戳这

可靠性编码

目的:解决代码在形成或传输过程中可能会发生的错误,提高系统的安全性

方法:使代码自身具有一种特征或能力

格雷码

任意两个相邻数的代码只有一位二进制数不同

格雷码(Gray code)是1880年由法国工程师Jean-Maurice-Emlle Baudot发明的一种编码,是一种绝对编码方式,典型格雷码是一种具有反射特性和循环特性的单步自补码,它的循环、单步特性消除了随机取数时出现重大误差的可能,它的反射、自补特性使得求反非常方便。格雷码属于可靠性编码,是一种错误最小化的编码方式,因为,虽然自然二进制码可以直接由数/模转换器转换成模拟信号,但在某些情况,例如从十进制的3转换为4时二进制码的每一位都要变,能使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点,它在相邻位间转换时,只有一位产生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。由于这种编码相邻的两个码组之间只有一位不同,引起数字量发生变化时,格雷码仅改变一位,这样与其它编码同时改变两位或多位的情况相比更为可靠,即可减少出错的可能性。

格雷码是一个数列集合,相邻两数间只有一个位元改变,为无权数码,且格雷码的顺序不是唯一的。

例如以下为3位元的格雷码: 000 001 011 010 110 111 101 100 。

如果要产生n位元的格雷码,那么格雷码的个数为$2^n$.

假设原始的值从0开始,格雷码产生的规律是:

第一步,改变最右边的位元值;

第二步,改变右起第一个为1的位元的左边位元;

第三步,第四步重复第一步和第二步,直到所有的格雷码产生完毕(换句话说,已经走了$2^n -1$步)。

用一个例子来说明:

假设产生3位元的格雷码,原始值位 000

第一步:改变最右边的位元值: 001

第二步:改变右起第一个为1的位元的左边位元: 011

第三步:改变最右边的位元值: 010

第四步:改变右起第一个为1的位元的左边位元: 110

第五步:改变最右边的位元值: 111

第六步:改变右起第一个为1的位元的左边位元: 101

第七步:改变最右边的位元值: 100

如果按照这个规则来生成格雷码,是没有问题的,但是这样做太复杂了。如果仔细观察格雷码的结构,我们会有以下发现:

  1. 除了最高位(左边第一位),格雷码的位元完全上下对称(看下面列表)。比如第一个格雷码与最后一个格雷码对称(除了第一位),第二个格雷码与倒数第二个对称,以此类推。

  2. 最小的重复单元是 0 , 1

000

001

101

100

所以,在实现的时候,我们完全可以利用递归,在每一层前面加上0或者1,然后就可以列出所有的格雷码。

比如:

第一步:产生 0, 1 两个字符串。

第二步:在第一步的基础上,每一个字符串都加上0和1,但是每次只能加一个,所以得做两次。这样就变成了 00,01,11,10 (注意对称)。

第三步:在第二步的基础上,再给每个字符串都加上0和1,同样,每次只能加一个,这样就变成了 000,001,011,010,110,111,101,100。

好了,这样就把3位元格雷码生成好了。

如果要生成4位元格雷码,我们只需要在3位元格雷码上再加一层0,1就可以了: 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.

也就是说,n位元格雷码是基于n-1位元格雷码产生的

格雷码和自然二进制码之间的转换方法

自然二进制码转换成二进制格雷码,其法则是保留自然二进制码的最高位作为格雷码的最高位,而次高位格雷码为二进制码的高位与次高位相异或,而格雷码其余各位与次高位的求法相类似。

原理: 若二进制码表示为:B[N-1]B[N-2]...B[2]B[1]B[0]

则二进制格雷码表示为:G[N-1]G[N-2]...G[2]G[1]G[0].

其中最高位保留:G[N-1] = B[N-1]

其他各位:G[i] = B[i+1] xor B[i]. (i = 0, 1, 2, ..., n-2)

格雷码转换为二进制码的实现方法

二进制格雷码转换成自然二进制码,其法则是保留格雷码的最高位作为自然二进制码的最高位,而次高位自然二进制码为高位自然二进制码与次高位格雷码相异或,而自然二进制码的其余各位与次高位自然二进制码的求法相类似。

原理: 若二进制格雷码表示为:G[N-1]G[N-2]...G[2]G[1]G[0]

相应地, 则二进制码表示为:B[N-1]B[N-2]...B[2]B[1]B[0].

其中最高位保留:B[N-1] = G[N-1]

其他各位:B[i-1] = G[i-1] xor B[i]. (i = 1, 2, ..., n-1)

算法实现:参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//递归实现
public static String[] GrayCode(int n) {
String[] arr = new String[(int)Math.pow(2, n)];
if(n < 1)
System.out.println("Input Error!");
if(n == 1) {
arr[0] = "0";
arr[1] = "1";
return arr;
}
String[] b = GrayCode(n - 1);
for(int i = 0; i < b.length; i++) {
arr[i] = "0" + b[i];
arr[arr.length - 1 - i] = "1" + b[i];
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//非递归
public static String[] GrayCode(int n) {
int num = (int)Math.pow(2, n);
String[] s1 = {"0", "1"};
if(n < 1)
System.out.println("Input Error!");
for(int i = 2; i <= n; i++) {
int p = (int)Math.pow(2, i);
String[] si = new String[p];
for(int j = 0; j < p; j++) {
if(j < p/2)
si[j] = "0" + s1[j];
else
si[j] = "1" + s1[p - j - 1];
}
s1 = si;
}
return s1;
}

对于典型格雷码(0~15)还有一个特点:所有对应于十进制数$2^m-1$的格雷码,都仅在m位上有1,其余位都为0.

例如:m=1,1的典型格雷码为0001;m=2,3的典型格雷码为0010;m=3,7的典型格雷码为0100;m=4,15的典型格雷码为1000.

15与0的格雷码仍能保持一位差别,所以这种典型格雷码也称作循环码,适用于做二进制码计数器。

十进制格雷码(0~9):代码特征符合格雷码要求,且16选10,使得9到0也只有一位的差别,保持循环码特点。

校验码

参考博客:戳这

奇偶校验码

参考博客1:戳这

参考博客2:戳这

视频链接地址:戳这

问题:

  • 奇偶校验码能发现单错,但不能对单错定位;
  • 奇偶校验码不能发现双错.

海明校验码

参考博客1:戳这

参考博客2:戳这

海明码(Hamming Code)是利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的确定位置插入k个校验位,通过扩大码距来实现检错和纠错。对于m位的数据,加入k位的校验码,它应满足:$m+k+1<2^k$.

逻辑代数

  1. 布尔代数:用一种数学运算来描述人的逻辑思维规律和推理过程的代数系统.

  2. 逻辑代数:将布尔代数的一些基本前提和定理应用于继电器电路的分析与描述。即开关代数,也就是二值布尔代数.

  3. 逻辑变量:用于表示事物的逻辑状态随逻辑条件的变化而变化的量,取值:0或1.

  4. 逻辑常量:逻辑状态保持不变,值为0或1.

  5. 逻辑电路:由实现逻辑变量之间逻辑关系的物理器件所构成的电路称为逻辑电路,即二值逻辑电路.

  6. 逻辑电平:在二值逻辑电路即开关电路中,将物理器件的物理量离散为两种电平.

    噪音区:在高、低电平之间有一逻辑不确定区。若电平稳定于噪音区称为逻辑模糊,这在逻辑电路中不允许。

    一般用H表示高电平,用L表示的低电平

    抽象化的高、低电平忽略了其物理量值的实际含义,实际上它们是代表着一定范围的物理量。

  7. 逻辑状态:事物的某些特性表现为两种互不相容的状态,即
    ① 某一时刻必出现且仅出现一种状态;
    ② 一种状态是另一种状态的反状态.

    用0、1表示,两种状态无大小之分.

  8. 逻辑约定:规定逻辑电平(表示物理器件的物理量)与逻辑状态(表示物理器件的功能)之间的关系,即逻辑规定。这一规定的过程称为逻辑化过程。
    逻辑规定有两种:正逻辑规定和负逻辑规定。

  9. 逻辑函数:输入逻辑变量 $A_1, A_2, …, A_n$,输出逻辑变量F,记为 $F = f(A_1, A_2, …, A_n)$。

    逻辑函数的表示法:真值表、逻辑表达式、卡诺图、时间图

逻辑代数的运算

基本运算

”与“运算(逻辑乘,Logic Multiplication),运算结果是逻辑积(Logic Product)

”与“运算(逻辑乘, Logic Multiplication) ”或“运算(逻辑加, Logic Addition) ”非“运算(逻辑乘, Logic Negation)
运算结果 逻辑积(Logic Product) 逻辑和(Logic Sum) 求补(Complement)
代数式 $F=A\times B=A\cdot B$ $F=A+B$ $F=\overline{A}$

逻辑代数的基本公理

0-1律

$A+0=A$

$A+1=1$

$A\cdot 1=A$

$A\cdot 0=0$

与、或运算满足交换律、结合律、分配律。

互补律:$A+\overline{A}=1$, $A\cdot \overline{A}=0$

重叠律:$A+A=A$, $A\cdot A=A$

对合律:$\overline{\overline{A}}=A$

逻辑代数的基本定理

吸收定理

$A+AB=A$

$A\cdot (A+B)=A$

$A+\overline{A} \cdot B=A+B$

$A\cdot (\overline{A}+B)=A\cdot B$

$A\cdot B+A\cdot \overline{B}=A$

$(A+B)(A+\overline{B})=A$

反演定理

$\overline{A_1+A_2+\dots +A_n}=\overline{A_1}\cdot \overline{A_2}\cdot \dots \overline{A_n}$

$\overline{A_1\cdot A_2\cdot \dots \cdot A_n}=\overline{A_1}+ \overline{A_2}+ \dots \overline{A_n}$

包含定理(多余项定理)

证明:$AB+\overline{A} C+BC=AB+\overline{A} C$

逻辑代数的基本规则

代入规则

已知 $f(x_1,x_2,\dots ,x_i,\dots ,x_n)=g(x_1,x_2,\dots ,x_i,\dots ,x_n)$,有任意函数h,令$x_i=h$,则 $f(x_1,x_2,\dots ,h,\dots ,x_n)=g(x_1,x_2,\dots ,h,\dots ,x_n)$依然成立。

证明:

可以用带入规则证明N变量的德摩根定理。

反演规则

已知原函数 $f(x_1,x_2,\dots ,x_n,0,1,+,\cdot)$,则反函数 $\overline{f}(x_1,x_2,\dots ,x_n,0,1,+,\cdot)=f(\overline{x_1},\overline{x_2},\dots ,\overline{x_n},1,0,\cdot ,+)$

对偶规则

已知原函数 $f(x_1,x_2,\dots ,x_n,0,1,+,\cdot)$,则对偶函数 $f’(x_1,x_2,\dots ,x_n,0,1,+,\cdot)=f(x_1,x_2,\dots ,x_n,1,0,\cdot ,+)$

如果原函数相等,则对偶函数也相等。

复合运算

与非(NAND):$F=\overline{A\cdot B\cdot C}$

可以用与非门实现三种基本运算:

与运算:$F_1=A\cdot B=\overline{\overline{A\cdot B}}$

非运算:$F_2=\overline{A\cdot A}=\overline{A}$

或运算:$F_3=\overline{\overline{A\cdot A}\cdot \overline{B\cdot B}}=\overline{\overline{A}\cdot \overline{B}}=A+B$

或非(NOR):$F=\overline{A+B+C}$

可以用或非门实现三种基本运算:

与运算:$F_1=\overline{\overline{A+A}+\overline{B+B}}=\overline{\overline{A}+\overline{B}}=A\cdot B$

非运算:$F_2=\overline{A+A}=\overline{A}$

或运算:$F_3=\overline{\overline{A+B}}$

与或非(AOI):$F=\overline{AB+CD+EF}$

异或(XOR):$F=A\oplus B=\overline{A}\cdot B+A\cdot \overline{B}$

同或(XNOR):$F=A\odot B=A\cdot B+\overline{A}\cdot\overline{B}$

异或和同或的关系:

$\overline{A\oplus B}=A\odot B$ $\overline{A\odot B}=A\oplus B$

$(A\oplus B)‘=A\odot B$ $(A\odot B)‘=A\oplus B$(用对偶函数的运算性质证明)

$A\oplus B\oplus C=A\odot B\odot C$

证明 $(A\oplus B)‘=A\odot B$

由带入规则可以证明:

当变量n为偶数时,XOR和XNOR具有互补关系:

当变量n为奇数时,XOR和XNOR具有相等关系:

逻辑函数的标准形式

最小项之和:乘积项之和称为积之和表达式(SOP),或称与或表达式。如果构成函数的积之和表达式中每一个与项均为最小项时,称为最小项标准式,且这种表示是唯一的。

最大项之积:和项之积称为和之积表达式(POS),或称或与表达式。如果构成函数的和之积表达式中每一个和项均为最大值,称为最大项标准式,且这种表示是唯一的。

最小项minterm:设有n个变量,它们组成的与项中每个变量或以原变量或以反变量形式出现一次,且仅出现一次,此与项称之为n个变量的最小项。对于n个变量就可构成 $2^n$ 个最小项,记为 $m_i$.
其中下标值i:当各最小项变量按一定顺序排好后,用1代替其中的原变量,0代替其中的反变量,便得一个二进制数,该二进制数的等值十进制即为i的值。

例如$\overline{A}B\overline{C}=m_{(010)_2}=m_2$

为了区别不同n值对应的相同的 $m_i$,可记为 $m_i^n$.

最大项maxterm:与最小项相反,用0代替原变量,1代替反变量,例如:$\overline{A}+B+\overline{C}=M_5$

性质

  1. 对于任意最小项,只有一组变量组合取值可使其值为1;对于任意最大项,只有一组变量组合取值可使其值为0.

  2. 任意两个最小项之积必为0,即:$m_i\cdot m_j=0, i\neq j$.

    任意两个最大项之和必为1,即:$M_i+M_j=1, i\neq j$.

  3. 同变量数(n相同)下标相同的最小项和最大项互为反函数,即 $m_i=\overline{M_i}$,$M_i=\overline{m_i}$.

    则 $m_i\cdot M_i=0$,$m_i+M_i=1$.

最小项与原、反函数的关系:对于n个变量的函数F,它共有 $2^n$ 个最小项,这些最小项不是包含在原函数 $F$ 的最小项表达式中,就是包含在反函数 $\overline{F}$ 的最小项表达式中。

最大项与原、反函数的关系:对于n个变量的函数F,它共有 $2^n$ 个最大项,这些最大项不是包含在原函数 $F$ 的最大项表达式中,就是包含在反函数 $\overline{F}$ 的最大项表达式中。

同一函数的最小项标准式与其最大项标准式的关系

证明:设 $F=\sum m^3(0,2,3)$,则

卡诺图

卡诺图是一种平面方格阵列图

行和列按变量的组合标注,其变量顺序按真值表中输入变量从左至右的顺序,并且行与列坐标按变量组合的二进制格雷码的顺序而小方格左上角标注可用十进制数表示,该数对应最小项。

参考博客:戳这