抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

进制与编码

进位计数制

基本要素

  1. 基数:计数制中所用到符号的个数

  2. 位权:用来表示不同数位上数值大小的一个的一个固定常数。

    RR 进制数的的位权是 RR 的整数幂

表示方法

  1. 并列表示法

    (N)R=Kn1Kn2Kn3K1K0.K1K2Km(N)_R=K_{n-1}K_{n-2}K_{n-3}\cdots K_1K_0.K_{-1}K_{-2} \cdots K_{-m}

  2. 多项式表示法

    $(N)R=K{n-1} \times R^{n-1} + K*{n-2} \times R^{n-2} + K*{n-3} \times R^{n-3} + \cdots $

进制转换

graph TB

BIN(二进制)--位权乘法-->DEC(十进制)
BIN--三位一组-->OCT(八进制)
BIN--四位一组-->HEX(十六进制)


DEC--降幂法或除法-->BIN
DEC--降幂法或除法-->OCT
DEC--降幂法或除法-->HEX

OCT--按位拓展-->BIN
HEX--按位拓展-->BIN
  1. 十进制到任意进制:

    • 降幂法:写出最高为二进制权值,作差,再将差减去二进制权值,以此类推。
    • 除法:整数部分除权取余,小数部分乘权取整。
  2. 任意进制到十进制:按位权进行展开。

  3. 二进制到八进制和十六进制:以小数点为起点,三位(十六进制为四位)一组,用十六进制表示出来。缺位的补零。

  4. 八进制和十六进制到二进制:将每一位展开。

带符号数的表示

机器码和真值

  1. 真值:用 ++- 表示的二进制数。
  2. 机器码:将符号和数值一起编码表示的二进制数。

原码、反码、补码

类型 正数表示 负数表示 范围 例子(1 字节)
原码 符号为为 0,数值位转换成二进制 符号为 1,数值位转换成二进制 (2N1)(2N1)-(2^N-1) \sim (2^N-1) 00=00000000 00000000=10001000 00000000
127127=01110111 11111111
127-127=11111111 11111111
反码 同原码 符号为 1,数值位取反 (2N1)(2N1)-(2^N-1) \sim (2^N-1) 00=00000000 00000000=11111111 11111111
127127=01110111 11111111
127-127=10001000 00000000
补码 同原码 反码加 1 (2N)(2N1)-(2^N) \sim (2^N-1) 00=00000000 00000000
127127=01110111 11111111
127-127=10001000 00010001
128-128=10001000 00000000
1-1=11111111 11111111

原码、反码、补码的转换

  • 正数: ==原码=反码=补码
  • 负数:
graph TB

CC--减一-->IC
CC--数值位取反加一-->OC

IC--数值位取反-->OC
IC--加一-->CC(补码)

OC(原码)--数值位取反-->IC(反码)
OC--数值位取反加一-->CC

补码的加法和减法

  1. 加法 $ [X+Y]{补}=[X]{补} + [Y]_{补} $
  2. 减法 [XY]=[X]+[Y][X-Y]_{补}=[X]_{补} + [-Y]_{补} ,其中 [Y][-Y]_{补} 只需对 YY 求补即可。

进位和溢出

  1. 溢出:有符号数运算结果超过范围。

    例如:

    • 正数和正数相加得到负数
    • 负数和负数相加得到正数

例子 图形法判断溢出

假设数据的大小为 1 个字节,则补码的表示范围为 $ [-128,127] 。当溢出发生时,最高位由于长度限制被舍去,因此进入了下一个 [-128,127] $轮回。

我们可以画一个圆,来表示 -128 到 127 直接的数,并标出 0:

对于含有正数的加法运算,结果会变大,即往逆时针方向旋转,当偏移到 127 左边时,发生溢出;
对于减数为正数的减法运算,结果会变小,即往顺时针方向旋转,当偏移到-128 右边时,发生溢出;


  1. 进位:无符号数运算结果超出范围。

求反和求补

  1. 求反:对每一个二进制位求反
  2. 求补:对每一个二进制位求反,再加一
  3. 关系:求补=求反+1

符号拓展

  1. 概念:位数少向位数多扩展,以表示更大或更小的数
  2. 方法:补码表示的正数扩展时前补 0,负数扩展时前补 1

例子

[+46]=0010,1110=0000,0000,0010,1110[ + 46 ]_{补 }={0010},{1110} = {0000}, {0000} ,{0010} ,{1110}

[46]=1101,0010=1111,1111,1101,0010[ - 46 ]_{补 }={1101},{0010} = {1111}, {1111} ,{1101} ,{0010}


浮点数的表示

  1. 浮点数在内存中的存储方式
阶符 阶码 数符 尾数
  1. 浮点数的值 V=××2×V=数符 \times 尾数 \times 2^{阶码 \times 阶符}
  2. 阶码是指数,尾数是纯小数
  3. 阶符和数符分别表示指数和数字的符号

例子

(110.011)B=+0.110011×2+11(110.011)B=+0.110011 × 2^{+11}

其中它在内存中的表示为:

1 11 0 110011

常用编码

BCD 码

使用 4 位二进制代码对十进制数字符号进行编码。

编码 8421(最常用) 2421 余 3 码
位权 8-4-2-1 2-4-2-1 无权
运算 直接十进制和二进制相互转换 按照位权运算 8421 码加 3
不足 容易出现加法问题 一个数可以有多种表示方法

格雷码

  1. 特点:任意两个相邻的数字仅有一位不同,表示方法不唯一。
  2. 转换:
    • 二进制转换成格雷码:最高位不变,其余位和上位进行异或运算。

奇偶检验码

  1. 特点:

    • 只有一位
    • 只能检验出奇数个错误
    • 编码简单、容易实现
  2. 检验方法

检验方法 错误时机
偶检验吗 奇数个 1
奇检验吗 偶数个 1
  1. 数 1 是奇数个还是偶数个:异或运算,结果为 1,则是奇数个 1。

逻辑代数

基本公式

规律 公式
交换律 A+B=B+A,AB=BAA+B=B+A,A \cdot B = B \cdot A
结合律 (A+B)+C=A+(B+C),(AB)C=A(BC)(A+B)+C=A+(B+C),(A \cdot B) \cdot C=A \cdot (B \cdot C)
分配律 A+(BC)=(A+B)(A+C),A(B+C)=AB+ACA+(B \cdot C)=(A+B) \cdot (A+C),A\cdot(B + C)=A\cdot B + A\cdot C
同一律 A+0=A,A+0=AA+0=A, A+0=A
零律 A+1=1,A0=0A+1=1, A \cdot 0=0
矛盾律 AA=0A \cdot \overline{A}=0
排中律 A+A=1A+\overline{A}=1
幂等律 A+A=A,AA=AA+A=A, A \cdot A = A
德摩根律 A+B=AB,AB=A+B\overline{A + B} = \overline{A} \cdot \overline{B},\overline{A \cdot B} = \overline{A} + \overline{B}
吸收律 A+AB=A,A(A+B)=AA+A \cdot B=A, A \cdot (A+B) = A
并项公式 AB+AB=A,(A+B(A+B)=AA \cdot \mathbf{B} + A \cdot \mathbf{\overline{B}} = A,(A + \mathbf{B}) \cdot (A + \mathbf{\overline{B}}) = A
消因子公式 A+AB=A+B,A(A+B)=ABA+\mathbf{\overline{A}} \cdot B=A + B, A \cdot (\mathbf{\overline{A}+B}) = A \cdot B
消项公式 AB+AC+BC=AB+ACA \cdot B + \overline{A} \cdot C + {\mathbf{B \cdot C}} = A \cdot B + \overline{A} \cdot C

三大规则

代入规则

将出现变量的位置用逻辑函数替代,等式仍然成立。

反演规则

  1. 反函数的表示F\overline{F}
  2. 求反函数的方法:
    1. \cdot 变成 ++,将 ++ 变成 $ \cdot$
    2. 00 变成 11,将 11 变成 00
    3. 将变量全部取反
    4. 保持运算顺序不变

注意乘号的省略


例子
F=AB+CDF=\overline{A}B+C\overline{D},则F=(A+B)(C+D)\overline{F}=(A+\overline{B})(\overline{C}+D)


对偶规则

  1. 对偶函数的表示FF'
  2. 求对偶函数的方法:
    1. \cdot 变成 ++,将 ++ 变成 $ \cdot$
    2. 00 变成 11,将 11 变成 00
    3. 保持运算顺序不变

无需对变量取反,但 0 和 1 仍要变换。


例子
F=AB+CDF=\overline{A}B+C\overline{D},则F=(A+B)(C+D)F'=(\overline{A}+B)(C+\overline{D})


  1. 自对偶函数F=FF'=F

常见复合逻辑

逻辑 函数表示 功能
与非逻辑 F=ABC...F=\overline{ABC...} AA,BB,CC 全部为 1 时,FF为 0,否则为 1
或非逻辑 F=A+B+C+...F=\overline{A+B+C+...} AA,BB,CC 全部为 0 时,FF为 1,否则为 0
与或非逻辑 F=AB+CD+...F=\overline{AB+CD+...} 与项均为 0 时,F 为 1,否则 F 为 0
异或逻辑 F=AB=AB+ABF=A \oplus B=A\overline{B}+\overline{A}B AABB不同时为 1,否则为 0
同或逻辑 F=AB=AB+ABF=A \odot B=\overline{A}\cdot\overline{B}+A\cdot B AABB不同时为 0,否则为 1
  1. 同或逻辑和异或逻辑互为相反,也互为对偶
  2. 当多个变量进行异或运算时,若有奇数个 1,则结果为 1,否则结果为 0。

逻辑函数表达式

基本形式

  1. 与或式:积之和
  2. 或与式:和之积

最小项和最大项

最小项
  1. 定义:与项包含全部变量,每个变量以原变量和反变量的形式出现,且只出现一次
  2. 表示:mim_i,其中 ii 是与项中 反变量替换成 0,原变量替换成 1 后转换成的 10 进制数。
  3. 个数:22^{变量个数}
  4. 性质:
    • 任意两个最小项相与为 0
    • 所有最小项相或为 1
最小项和最大项的关系
  1. 存在互补关系
    • mi=Mi\overline{m_i} = M_i

标准表达式

  1. 最小项表达式:m(i1,i2,...)\sum m(i_1,i_2,...)

    • 求法:逐项画真值表
  2. 最大项表达式:M(i1,i2,...)\prod M(i_1,i_2,...)

  3. 最小项表达式的性质

    • F1F_1F2F_2 相或,\sum括号内的数取并集
    • F1F_1F2F_2 相与,\sum括号内的数取交集
    • F1F_1 取反,\sum括号内的数相取补集

例子
F1(A,B,C)=m(1,3,5)F_1(A,B,C)=\sum m(1,3,5),F2(A,B,C)=m(0,1,2,3)F_2(A,B,C)=\sum m(0,1,2,3),则

  • F1=m(0,2,4,6,7)\overline{F_1}=\sum m(0,2,4,6,7)
  • F1+F2=m(0,1,2,3,5)F_1+F_2=\sum m(0,1,2,3,5)
  • F1F2=m(1,3)F_1F_2=\sum m(1,3)

  1. 相互转化
    • 最大项表达式中括号内的数,等于最小项表达式中的数的补集

例子
F(A,B,C)=m(1,3,5)F(A,B,C)=\sum m(1,3,5),则F=M(0,1,2,4,6,7)F=\prod M(0,1,2,4,6,7)


  1. 标准表达式和真值表、函数值的关系
    • 对于标准与或式,括号中的每个数对于的二进制数函数值为 1,其余为 0
    • 对于标准或与式,括号中的每个数对于的二进制数函数值为 0,其余为 1

例子
F(A,B,C)=m(1,3,5)=M(0,1,2,4,6,7)F(A,B,C)=\sum m(1,3,5)=\prod M(0,1,2,4,6,7),则其真值表如下:

A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0

任意项和无关条件

  1. 任意项:不会出现的逻辑变量取值对应的函数值,由 dd 和 $ \emptyset $ 表示。
  2. 无关条件:由不会出现的逻辑变量取值构成的逻辑函数表达式
  3. 约束条件:限制逻辑变量只能取某些值的表达式

例子

一个带有约束条件的逻辑函数表达式:
F(A,B,C)=m(1,3,5)+d(0,1,2)F(A,B,C)=\sum m(1,3,5) + \sum d(0,1,2)


逻辑函数的化简

代数化简法

  1. 常用公式:吸收律、并项公式、消因子公式、消项公式
  2. 与或式化简两个条件:与项个数最少、每个与项中变量个数最少
  3. 或与式化简方法
    • 求对偶式
    • 将对偶式化简成最简与或式
    • 将最简与或式对偶

卡诺图化简法

  1. 行列排布:按照格雷码进行排布:0000010111111010

  2. 合并规则:相邻项可合并,需要注意边角位置。

  3. 方格填写:只填写 1 和任意项 d

  4. 要求:

    • 覆盖全部 1,但不要求全部覆盖 d
    • 圈尽量小
    • 圈尽量大

    优先保证圈的个数,再保证圈的大小


例子


带任意项的化简:


组合逻辑电路

特点

  1. 由逻辑门电路构成,不含记忆元件
  2. 信号单向传输,不含任何回路

分析

步骤

  1. 根据电路图写出表达式
  2. 化简表达式
  3. 写出真值表
  4. 进行功能描述

案例

  1. 不一致电路:检测输入中各位是否不一致
  2. 半加器:输入两位二进制数,得到结果和进位
  3. 全加器:输入两位二进制数和进位,得到结果和进位
  4. 编码转换:8421 码转余 3 码

设计

步骤

  1. 画卡诺图
  2. 求最简与或式
  3. 根据给定门电路,调整表达式

竞争和险象

  1. 竞争:
    • 概念:输入信号经过不同路径到达终点的时间不一样
    • 判断:一个逻辑函数表达式中既出现了原变量,又出现了反变量
  2. 险象:
    • 概念:输入信号的变化引起非预期的错误输出
    • 判断:其他逻辑变量取某些值时,出现 X+XX+\overline{X}XXX\cdot\overline{X}
    • 消除:根据 消项公式 增加冗余项,使得其他逻辑变量取这些值时,出现 X+X+1X+\overline{X} + 1XX0X\cdot\overline{X} \cdot 0

例子

  1. F=AB+ACF=AB+\overline{A}C

    • 既有 AA,又有 A\overline{A},有 竞争
    • B=C=1B=C=1 时,F=A+AF=A+\overline{A},有 险象
    • 根据 消项公式,为其加上冗余项 BCBC,即F=AB+AC+BCF=AB+\overline{A}C+BC,使得当 B=C=1B=C=1 时,出现 A+A+1A+\overline{A}+1
  2. F=AB+ABF=A\overline{B}+\overline{A}B

    • 既有 AA,又有 A\overline{A},有 竞争
    • 无论 B=1B=1 还是 B=0B=0,都不会出现F=A+AF=A+\overline{A}的情况,没有险象

时序逻辑电路

时序电路

概念

  1. 构成:组合电路和存储电路
  2. 常用符号:
    • 输入 XX
    • 存储电路输入 YY
    • 次态 yn+1y^{n+1}
    • 输出 ZZ
  3. 状态:
    • 现态:某个时钟脉冲到来前电路所处的状态
    • 次态:时钟脉冲后电路的状态
    • 关系:次态不断成为现态,产生新的次态
  4. 工作方式:
    • 同步:各触发器的时钟脉冲信号 CP 和统一的时钟信号相连接
    • 异步:电路没有统一的时钟信号同步,输入信号的变化直接导致电路状态的变化
  5. 输入输出关系:
    • Mealy 型:
      • 输出和输入、历史输入有关
      • 特点: ZZXX 有关
    • Moore 型:
      • 输出和输入、历史输入无关,或没有输出
      • 输入会转变成状态,再输出
      • 特点:ZZXX 无关,或者没有 ZZ

描述

  1. 逻辑函数表达式:

    • 输出函数 Z=xxxZ=xxx
    • 激励函数 Y=xxxY=xxx
    • 次态函数 yn+1=xxxy^{n+1}=xxx
  2. 状态表 分成两块,左边是输入和现态,右边是输出和次态

  3. 状态图

    • 用一个点表示状态
    • 用箭头表示状态变化,上面标注输入和输出

基本触发器

R-S 触发器

  1. 次态方程: Qn+1=S+RQQ^{n+1}=S+R \cdot Q
  2. 功能表:
R S 功能
0 0 未知
0 1 置 0
1 0 置 1
1 1 状态不变
  1. 激励表:根据状态变化查询条件
QQ Qn+1Q^{n+1} R S
0 0 d 1
0 1 1 0
1 0 0 1
1 1 1 d
  1. 默认触发方式:上跳触发

J-K 触发器

  1. 次态方程: Qn+1=JQ+KQQ^{n+1}=J\overline{Q}+\overline{K}Q
  2. 功能表:
J K 功能
0 0 不变
0 1 置 0
1 0 置 1
1 1 翻转
  1. 激励表:根据状态变化查询条件
QQ Qn+1Q^{n+1} J K
0 0 0 d
0 1 1 d
1 0 d 1
1 1 d 0
  1. 默认触发方式:上跳触发

D 触发器

  1. 次态方程: Qn+1=DQ^{n+1}=D
  2. 功能表:
D 功能
0 置 0
1 置 1
  1. 激励表:根据状态变化查询条件
QQ Qn+1Q^{n+1} D
0 0 0
0 1 1
1 0 0
1 1 1
  1. 默认触发方式:上跳触发

T 触发器

  1. 次态方程: Qn+1=QQ^{n+1}=\overline{Q}
  2. 功能表:
D 功能
0 不变
1 翻转
  1. 激励表:根据状态变化查询条件
QQ Qn+1Q^{n+1} D
0 0 0
0 1 1
1 0 1
1 1 0
  1. 默认触发方式:下跳触发(此时 CP 处有个圈)

分析

步骤

  1. 列方程:列出输出函数、次态方程和激励函数表达式

    异步时序电路需要注意时钟脉冲的表达式

  2. 列状态表

  3. 画状态图

  4. 功能描述

案例

  1. (可逆)计数器:加 1 计数,减 1 计数
  2. 序列检测器
  3. 串行加法器
    • 优点:不限制位数
    • 缺点:不能同时输入,不能并行计算

自校功能

  • 自校:特殊的状态能够回到原来的状态
  • 挂起:特殊的状态能够不能回到原来的状态

设计

步骤

  1. 画原始状态图和状态表
  2. 状态化简
    • 等效状态:
      • 输出相同
      • 次态相同 A1BA \overset{1}{\rightarrow} B,C1BC \overset{1}{\rightarrow} B
      • 次态交错 A1BA \overset{1}{\rightarrow} B, B1AB \overset{1}{\rightarrow} A
      • 次态等于现态 A1AA \overset{1}{\rightarrow} A
      • 次态循环 A1CA \overset{1}{\rightarrow} C B1DB \overset{1}{\rightarrow} D C1AC \overset{1}{\rightarrow} A D1BD \overset{1}{\rightarrow} B
      • 等效对 SiS_iSjS_j 的次态已为等效状态
    • 等效类:等效状态构成的集合
  3. 状态编码
    • 相同输入,相同次态的现态:相邻编码
    • 相邻输入,同一现态的次态:相邻编码
    • 输出相同的现态:相邻编码
  4. 求真值表:根据各触发器的激励表
  5. 求表达式:使用卡诺图进行化简

评论