Homeworks ( 第 三 版 ):.4 (,, 3).5 (, 3).6. (, 3, 5). (, 4).4.6.7 (,3).9 (, 3, 5)
Chapter. Number systems and codes 第 一 章. 数 制 与 编 码
. Overview 概 述 Information is of digital forms in a digital system, and thus it is necessary to have ways to represent information in digital forms. 数 字 系 统 中 通 过 数 字 信 号 的 形 式 存 储 和 处 理 信 息 因 此, 有 必 要 学 习 信 息 的 数 字 表 示 方 法 Number conversion 数 制 变 换 Content 本 章 内 容 :. Number systems and their conversions 数 制 及 其 相 互 转 换. BCD and Grey codes BCD 和 格 雷 码 3. Signed binaries 带 符 号 的 二 进 制 数 Extended learning 后 续 课 程 : Information theory and coding 信 息 论 与 编 码 3
. Overview 概 述 Information is of digital forms in a digital system, and thus it is necessary to have ways to represent information in digital forms. 数 字 系 统 中 通 过 数 字 信 号 的 形 式 存 储 和 处 理 信 息 因 此, 有 必 要 学 习 信 息 的 数 字 表 示 方 法 Number conversion 数 制 变 换 Content 本 章 内 容 :. Number systems and their conversions 数 制 及 其 相 互 转 换. BCD and Grey codes BCD 和 格 雷 码 3. Signed binaries 带 符 号 的 二 进 制 数 Extended learning 后 续 课 程 : Information theory and coding 信 息 论 与 编 码 Therefore, in a general sense, information is "Knowledge communicated or received concerning a particular fact or circumstance", or rather, information is an answer to a question. Information cannot be predicted and resolves uncertainty. 4
. Number systems 数 制. A number system consists of an ordered set of digits, with relationship defined for addition, substraction, multiplication, and division. 定 义 了 加 减 乘 除 关 系, 并 按 照 一 定 顺 序 进 行 排 列 的 数 字 集 合 称 为 数 制. Instead of decimal used in ordinary life, binary, octal and hexadecimal are more commonly used in digital systems. 同 生 活 中 常 用 十 进 制 数 不 同, 数 字 系 统 中 更 常 用 的 数 制 是 二 进 制 八 进 制 和 十 六 进 制 3. The radix (r), or base, of the number system is the total number of digits allowed. 数 字 的 总 个 数 称 为 数 制 的 基 数 : Number systems decimal (r =) binary (r =) octal (r =8) hexadecimal (r =6) 5
. Decimal 十 进 制 Ten symbols in decimal system:,,, 3, 4, 5, 6, 7, 8, 9. The radix is. 十 进 制 包 含 十 个 数 码, 基 数 为 ( 逢 十 进 一 ) Digits are located at different positions, the values of which are different. The value of a position is defined as the weight. 权 : 表 示 该 位 置 的 大 小 The weight of each position in the decimal system is a power of radix 十 进 制 中 每 一 个 位 置 对 应 的 权 都 是 其 基 数 的 幂 A number can be written in polynomial ( 多 项 式 ) form: (.3) = 94 + 9 + 4 + 3 + 6
In general, any number N of radix r can be written in the polynomial form ( 按 权 展 开 ): Integer digits Radix point Fractional digits N = a,..., a, a a,..., a. n m n -- number of integer digits 整 数 部 分 的 位 数 m -- number of fractional digits 小 数 部 分 的 位 数 a r i i i -- The digit 第 i 个 数 字 th i th n = i= m -- weight of the digit 第 i 个 数 字 的 权 值 ar i i 7
. Binary 二 进 制 Two symbols in a binary system:,. The radix is. 二 进 制 包 含 两 个 数 字, 基 数 为 ( 逢 二 进 一 ) The weights in the binary system are powers of radix 二 进 制 权 值 都 是 基 数 的 幂 A number can be written in polynomial ( 多 项 式 ) form: (. ) = = 4 6.75 + 3 + + + + + 8
Table. Decimal vs. Binary Decimal 3 4 5 6 7 8 9 3 4 5 6 Binary 3 3 4 4 n = (...) n zeros (...) n = n ones 9
The advantage of using binary in digital systems 数 字 系 统 中 使 用 二 进 制 的 优 点. Easy to describe with hardware. 便 于 硬 件 描 述 Switch 开 关 Lamp 灯 泡 Diode/Transistor 二 极 管 / 晶 体 管 Impulse 脉 冲 Voltage 电 压 On On Conduct Exist High Off Off Cut off Vanish Low. Nice properties of identifiability and anti-interference. 易 于 辨 识 抗 干 扰 能 力 强
However, the binary system uses too many bits to represent a large number, and thus may be sometimes inconvienence to use. 然 而, 二 进 制 表 示 大 数 时 占 用 位 数 过 多, 因 此 在 某 些 场 合 下 不 便 使 用 65: 4 bits in decimal, but bits in binary () The larger the number is, the more obvious the disadvantage is. So octal and hexadecimal systems are also used. 因 此, 八 进 制 和 十 六 进 制 也 常 常 使 用
3. Octal 八 进 制 Eight symbols in an octal system:,,, 3, 4, 5, 6, 7. The radix is 8. 八 进 制 包 含 八 个 数 码, 基 数 为 8( 逢 八 进 一 ) The weights in the octal system are powers of radix 8 八 进 制 权 值 为 基 数 8 的 幂 A number can be written in polynomial ( 多 项 式 ) form: ( 36.47) 8 = 3 8 + 8 + 6 8 + 4 8 + = 9 + 6 + 6 +.5 +. 7 8 = (4.6)
3 Table. Octal vs. Decimal and Binary 3 4 5 6 7 8 9 3 4 5 6 Decimal Binary Octal 3 4 5 6 7 3 4 5 6 7
4. Hexadecimal 十 六 进 制 Sixteen symbols in a hexadecimal system:,,, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. The radix is 6. 十 六 进 制 包 含 十 六 个 数 码, 基 数 为 6( 逢 十 六 进 一 ) The weights in the hexadecimal system are powers of radix 6. 十 六 进 制 权 值 为 基 数 6 的 幂 A number can be written in polynomial ( 多 项 式 ) form: ( 3CE.4B) 6 = 3 6 + 6 + 4 6 + 4 6 + 6 = 768 + 9 + 4 +.5 +.43 = (974.93) 4
5 Table.3 Hexadecimal vs. Decimal, Binary, and Octal 3 4 5 6 7 8 9 3 4 5 6 Decimal Binary Octal 3 4 5 6 7 3 4 5 6 7 Hexadecimal 3 4 5 6 7 8 9 A B C D E F
5. γ system 任 意 进 制 γ symbols:,,, γ-. The radix is γ. 包 含 γ 个 数 码, 基 数 为 γ The weights in the γ system are powers of radix γ. 任 意 进 制 权 值 为 其 基 数 的 幂 A number can be written in polynomial ( 多 项 式 ) form: (345.6) = 3 7 + 4 7 + 5 7 + 6 7 + 7 7 6
.3 Base conversions 数 制 间 转 换. Convert γ system to decimal 任 意 进 制 向 十 进 制 转 换 : Write the number in γ system in polynomial form 按 权 展 开 即 可 : (.) = 5 4 3 ( + + + + ) = (57.5). Convert decimal to γ system 十 进 制 向 任 意 进 制 转 换 : ) For the integer part of a number, divide it by the radix until the quotient is, put the remainders in reversed order; 整 数 部 分, 除 以 γ 取 余, 直 到 商 为 为 止, 余 数 按 逆 序 排 列 ) For the fraction part of a number, multiply radix and put the integer in order. 小 数 部 分, 乘 γ 取 整, 整 数 部 分 按 顺 序 排 列 7
An example: Convert (39.) to binary ) 整 数 部 分, 除 γ 取 余, 直 到 商 为 为 止, 逆 序 Integer: 39 remainder 9.. 9.. 4.... LSB (least significant bit) In reversed order 逆 序.. MSB (most significant bit) ( 39) ( ) 8
) 小 数 部 分, 乘 γ 取 整, 顺 序 排 列 MSB In order 顺 序 integer.... x.4 x.8 x.6.6 x. ( 39.) = (.) (.) (.) 9
Decimal to octal 十 进 制 向 八 进 制 转 换 Convert ( 79.46) to octal: 8 79..3 8..6 8.. Radix point 3 5.46 8 3.68.68 8 5.44 ( 79.46) = (63.35 ) 8
Decimal to hexadecimal 十 进 制 向 十 六 进 制 转 换 Convert ( 78.46) to hexadecimal 6 6 78 B 7..46 6 76 46 7.36 ( 78.46) = (B.7 ) 6
3. Conversions between Binary and Octal 二 进 制 和 八 进 制 的 互 相 转 换 3 8 = One bit of octal can be expressed by three bits of binary. Method: Group the digits in groups of 3 digits in both directions from the radix point. 以 小 数 点 为 界 向 两 侧 划 分, 三 位 一 组, 不 够 添 (. ) = 5 6 3 5 4 (53.6) 8 = (. (563.54) 8 ) Note the last : ---4 the first : --- The zeros at both ends could be ignored.
4. Conversions between Binary and Hexadecimal 4 6 = One bit of hexadecimal can be expressed by four bits of binary Method: Group the digits in groups of 4 digits in both directions from the radix point. 以 小 数 点 为 界 向 两 侧 划 分, 四 位 一 组, 不 够 添 (. ) = (5ED.BA) 6 5 E D B A (3D5E.7A8) 6 = (. ) 3
.4 Codes 码 代 码 是 指 用 于 表 示 信 息 的 一 组 符 号, 通 常 在 计 算 机 以 及 其 他 数 字 系 统 中, 用 于 不 同 种 类 信 息 的 处 理 存 储 和 交 换 MSB integer In order. 顺 序.. (.) =(. ).. x.4 x.8 x.6.6 x. Many non-integral values may have infinite digits in binary. 很 多 有 限 小 数 的 二 进 制 形 式 包 含 无 限 多 个 数 字 Binary coded decimal (BCD). 二 - 十 进 制 代 码 4
.4. BCD Code 二 - 十 进 制 代 码 : The BCD code: 4 bits of binary are used to represent bit of decimal. 用 四 位 二 进 制 数 表 示 一 位 十 进 制 数 ; BCD is a weighted code. BCD 码 为 加 权 码 ; 5
Table.4 Hexadecimal vs. Decimal, Binary, and Octal Decimal 3 4 5 6 7 8 9 3 4 5 6 Binary Octal 3 4 5 6 7 3 4 5 6 7 Hexadecimal 3 4 5 6 7 8 9 A B C D E F 84BCD 6
It is important to note that ~ are forbidden codes in 84BCD code system. 需 要 注 意 的 是,~ 是 84BCD 码 的 禁 用 码 The subscript of 84BCD must be written. 用 84BCD 码 表 示 数 的 时 候, 角 标 一 定 不 能 漏 写 (. ) 84BCD Practice 练 习 : (85.67) = (. ) 84BCD (. ) 84BCD = ( 769.83 ) 7
The conversion can be done directly between decimal and 84BCD code. 十 进 制 和 84BCD 码 可 直 接 转 换 But binary can be not converted to BCD code directly. We need to convert it to decimal first. 二 进 制 和 84BCD 码 不 可 直 接 转 换, 需 要 首 先 将 其 转 换 为 十 进 制 decimal binary 84BCD ( ) 84BCD = ( 8) ( ) = ( 4 ) = ( ) 84BCD 8
.4. Gray code 格 雷 码 : 84 BCD The ideal case: Four bits switch simutaneously 理 想 情 况 : 四 比 特 同 时 变 化 In practice: Simutaneous switch of all the four bits is hard to realize 实 际 中 : 很 难 实 现 所 有 四 比 特 的 同 时 翻 转 Gray code: only one bit switches between two adjacent numbers 格 雷 码 : 相 邻 的 两 个 数 之 间 仅 有 一 位 不 同 9
Gray code 格 雷 码 : Unweighted code. 不 是 加 权 码 ; Only one bit changes between adjacent numbers. 相 邻 数 之 间 仅 有 一 位 不 同 Cyclic code. 循 环 码 Decimal Binary 3 4 5 6 7 Gray code Decimal Binary Gray code 8 9 3 4 5 3
.5 Signed binary numbers 带 符 号 的 二 进 制 数 We use positive (+) and negative sign (-) in decimal system. There are some methods for indicating the sign in binary system. 在 十 进 制 中 我 们 采 用 (+) 和 (-) 表 示 正 负, 在 二 进 制 中 我 们 可 采 用 如 下 方 法 表 示 数 的 正 负 Sign-magnitude ( 原 码 ) Ones complement ( 反 码 ) Two s complement ( 补 码 ) Shift codes ( 偏 移 码 ) 3
.5. Sign-magnitude 原 码 : The most significant bit represent the sign ( for positive, and for negative). 原 码 的 最 高 位 表 示 数 的 正 负 ( 表 示 正 数, 表 示 负 数 ); The rest is the binary representation of the magnitude. 除 了 符 号 位 之 外 的 其 余 部 分 为 数 绝 对 值 的 二 进 制 形 式 ; + 45-37 + + 45-37 + 8 3
.5. Ones complement 反 码 : The most significant bit represent the sign ( for positive, and for negative). 反 码 的 最 高 位 表 示 数 的 正 负 ( 表 示 正 数, 表 示 负 数 ); The ones complement of a positive number is equal to its signmagnitude. 正 数 的 反 码 与 其 原 码 相 等 ; The ones complement of a negative number is obtained by applying bitwise NOT to its positive counterpart. 负 数 的 反 码 通 过 对 正 数 逐 位 取 反 ( 变 成, 变 成 ) 获 得 原 码 反 码 + 45-37 + 37 逐 位 求 反 -37 33
.5. Ones complement 反 码 : Ones Complement Ones Complement - N - +37-37 = + 因 此, 负 数 的 反 码 表 示 可 以 看 作 是 由 N -(Ones) 减 去 相 应 正 数 而 获 得 (Complement) N: 包 含 符 号 位 在 内 的 总 比 特 数 + + + 45-37 + 8 反 码 可 以 用 加 法 实 现 减 法 运 算, 但 需 要 将 进 位 重 新 加 一 遍 ; 的 表 示 方 法 不 唯 一 :(+),(-) 34
.5.3 Two complement 补 码 : The most significant bit represent the sign ( for positive, and for negative). 最 高 位 表 示 数 的 正 负 ( 表 示 正 数, 表 示 负 数 ); The two s complement of a positive number is equal to its signmagnitude and ones complement. 正 数 的 补 码 原 码 反 码 相 等 ; The two s complement of a negative number is obtained by adding one to its ones complement. 负 数 的 补 码 等 于 其 反 码 加 ; The two s complement of a negative number is also obtained by inversing its positive counterpart bitwisely from the leftmost bit to the first from the right. 对 正 数 原 码 从 左 边 第 一 位 依 次 取 反, 直 至 从 右 边 起 第 一 个 为 止 ( 不 包 含 该 位 ), 也 可 获 得 相 应 负 数 的 补 码 35
.5.3 Two complement 补 码 : 原 码 反 码 + 45-36 Power of Two Complement Two s Complement + - N - 44 补 码 + 36 = +44 + - 36 因 此, 负 数 的 补 码 表 示 可 以 看 作 是 由 N (Power of two) 减 去 相 应 正 数 而 获 得 (Complement) N: 包 含 符 号 位 在 内 的 总 比 特 数 36
.5.3 Two s complement 补 码 : + 45 + - 36 + 9 = + + 9-7 - 8 = 补 码 可 以 用 加 法 实 现 减 法 运 算 37
.5.4 Shift Codes 偏 移 码 : - Shift codes: invert the sign bit of s complement. 偏 移 码 的 构 成 : 补 码 的 符 号 位 取 反 Why the name Shift Codes? To be continued in Chapter 9 38
.6 Summary 总 结 Digital represations of numerical numbers 用 数 字 表 示 数 学 量 的 方 法. 不 同 数 制 下 的 直 接 表 示 二 进 制 八 进 制 十 六 进 制 数 制 相 互 转 换 BCD 码 格 雷 码. 编 码 表 示 BCD 码 同 十 进 制 和 二 进 制 的 相 互 转 换 3. 带 符 号 的 二 进 制 数 原 码 反 码 补 码 偏 移 码 39