Ch2: Data Representation 数据的机器级表示

Presentation on theme: "Ch2: Data Representation 数据的机器级表示"— Presentation transcript:

1 Ch2: Data Representation 数据的机器级表示
第一讲 数值数据的表示 第二讲 非数值数据表示及 数据的宽度、存储排列、纠/检错

2 第一讲：数值数据的表示 主 要 内 容 定点数的表示 进位计数制 定点数的二进制编码 原码、补码、移码表示 定点整数的表示
主 要 内 容 定点数的表示 进位计数制 定点数的二进制编码 原码、补码、移码表示 定点整数的表示 无符号整数、带符号整数 浮点数格式和表示范围 浮点数的规格化 IEEE754浮点数标准 单精度浮点数、双精度浮点数 特殊数的表示形式 C语言程序中的整数类型、浮点数类型 十进制数表示

3 信息的二进制编码 计算机的外部信息与内部机器级数据 机器级数据分两大类： 计算机内部所有信息都用二进制（即：0和1）进行编码
数值数据：无符号整数、带符号整数、浮点数（实数）、十进制数 非数值数据：逻辑数（包括位串）、西文字符和汉字 计算机内部所有信息都用二进制（即：0和1）进行编码 用二进制编码的原因： 制造二个稳定态的物理器件容易 二进制编码、计数、运算规则简单 正好与逻辑命题对应，便于逻辑运算，并可方便地用逻辑电路实现算术运算 真值和机器数 机器数：用0和1编码的计算机内部的0/1序列 真值：机器数真正的值，即：现实中带正负号的数 C语言中哪些类型是数值数据？哪些是非…？ 首先考虑数值数据的表示

4 BACK

5 数值数据的表示 数值数据表示的三要素 定/浮点表示（解决小数点问题） 定点数的编码（解决正负号问题） 进位计数制 定、浮点表示
如何用二进制编码 即：要确定一个数值数据的值必须先确定这三个要素。 例如，机器数 的值是多少？ 十进制、二进制、十六进制、八进制数及其相互转换 定/浮点表示（解决小数点问题） 定点整数、定点小数 浮点数（可用一个定点小数和一个定点整数来表示） 定点数的编码（解决正负号问题） 原码、补码、反码、移码 （反码很少用） 答案是：不知道！

6 Sign and Magnitude （原码的表示）
Binary Decimal 01 2 3 4 5 6 7 0000 0001 0010 0011 0100 0101 0110 0111 Decimal Binary -0 -1 -2 -3 -4 -5 -6 -7 1000 1001 1010 1011 1100 1101 1110 1111 容易理解, 但是： 0 的表示不唯一，不利于程序员编程 加、减运算方式不统一 需额外对符号位进行处理，不利于硬件设计 特别当 a<b时，实现 a- b比较困难 Sign and magnitude is convenient for human, but not convenient for computer. Since 1950’s, all computers use 2’s complement representation. Complement: Need different ways to do addition and subtraction. We’ll see soon that 2’s complement need not to distinguish between addition and subtraction. 从 50年代开始，整数都采用补码来表示 但浮点数的尾数用原码定点小数表示

7 回顾：补码特性 - 模运算（modular运算）
重要概念：在一个模运算系统中，一个数与它除以“模”后的余数等价。 时钟是一种模-12系统 假定钟表时针指向10点，要将它拨向６点， 则有两种拨法： ① 倒拨4格：10-4=6 ② 顺拨8格：10+8=18≡ (mod 12) 模12系统中： ≡ (mod 12) -4≡ (mod 12) 则，称8是- 4对模12的补码。 同样有 -3 ≡ （mod 12） -5 ≡ （mod 12）等 Supplement slide: More about 2’s complement. 结论1： 一个负数的补码等于模减该负数的绝对值。 结论2： 对于某一确定的模，某数减去小于模的另一数，总可以用该数加上另一数的补码来代替。 补码（modular运算）：+ and – 的统一

8 模运算系统举例 例1：“钟表”模运算系统 假定时针只能顺拨，从10点倒拨4格后是几点？
10- 4=10+(12- 4)=10+8=6 （mod 12） 例2：“4位十进制数” 模运算系统 假定算盘只有四档，且只能做加法，则在算盘上计算 等于多少？ =9828+( ) = = =7900（mod 104） 取模的含义就是只留余数，高位的“1”被丢弃！相当于只有低4位留在算盘上。

9 运算器是一个模运算系统，适合用补码表示和运算
计算机中的运算器只有有限位，假定为n位，则运算结果只能保留低n位，可看成是个只有n档的二进制运算算盘。所以，其模为2n 。 0000 0001 1000 0010 0100 1110 1111 0111 0101 1010 1011 1100 1101 0011 0110 1001 补码的定义 假定补码有n位，则： ① 定点整数：[X]补= 2n+ X （-2n≤X＜ 2n ，mod 2n） ② 定点小数：[X]补= 2 + X （-1≤X＜1，mod 2） 特殊数的补码（假定有n位） ① [-2n-1]补= 2n-2n-1 = 10…0（n-1个0） （mod 2n） ② [-1]补= 2n-0…01 = 11…1（n个1） （mod 2n） ③ [-1.0]补= = 1.00…0（n-1个0） （mod 2） ④ [+0]补= [-0]补= 00…0（n个0） 当n=4时，共有16个机器数：0000 ~ 1111，可看成是模为24 的钟表系统。真值范围为：-8 ~ +7 15 14 11 13 12 10 9 7 6 5 4 8 3 2 1 -2 -3 -4 -5 -1 -6 -7 -8 [-8,-1] is shifted to [8,15]. The modul here is 10000

10 Two’s Complement （补码的表示）
正数：符号位（sign bit）为0，数值部分不变 负数：符号位为1，数值部分“各位取反，末位加1” 变形（模4）补码：双符号，用于存放可溢出的中间结果。 Bitwise Inverse 1111 1110 1101 1100 1011 1010 1001 1000 0111 Decimal 01 2 3 4 5 6 7 8 补码 0000 0001 0010 0011 0100 0101 0110 -0 -1 -2 -3 -4 -5 -6 -7 -8 变形补码 00000 00001 00010 00011 00100 00101 00110 00111 01000 11111 11110 11101 11100 11011 11010 11001 11000 +0和-0表示唯一 All of you probably know the 2’s complement representation of negative numbers so this should be a quick review. You calculate the 2’s compliment representation by taking the bit-wise inverse of the positive number and then add one to 1. For example, in order to find the 2’s complement representation of negative one: (a) We first take the bit-wise inverse of 0001 to get 1110. (b) Then we need to add 1 to it to complete the transformation. This results in 1111. Notice that in 2’s complement representation, negative numbers always have the most significant bit set to 1 and is referred to as the sign bit. Consequently, the biggest positive number we can represent with four bits is 7, NOT 8 since 1000 is used to represent negative 8, the smallest negative number +2 = 23 min. (Y:03) 值太大，用4位补码无法表示，故“溢出”！但用变形补码可保留符号位和最高数值位。

11 如何求补码的真值 真值范围： 当N=4时，范围为：-23 ~ 23 -1 （即：-8 ~ +7）
根据补码各位上的“权”，可以求出一个补码的值 真值范围： 当N=4时，范围为：-23 ~ （即：-8 ~ +7） 当N=32时，范围为：-231 ~ 由补码计算其真值的方法 令：[A]补= an-1an-2…… a1a0 则： A= -an-1.2n-1+an-2 .2n-2+ …… a a0 .20

12 Excess (biased) notion- 移码表示
°什么是“excess (biased) notation-移码表示”？ 将每一个数值加上一个偏置常数（ Excess / bias） °一般来说，当编码位数为 n时，bias取 2n-1 Ex. n=4: Ebiased = E ( bias= 23 =10002 ) -8 (+8) ~ 00002 -7 (+8) ~ 00012 … 0 (+8) ~ 10002 +7 (+8) ~ 11112 °为什么要用移码来表示指数（阶码）? 便于浮点数加减运算时的对阶操作 0的移码表示惟一 移码和补码仅第一位不同 移码主要用来表示浮点数的阶码！ Exponent is usually represented with excess notation. Anyone knows why? Considering the addition operation for two scientific notation numbers, 3.12x103 , 4.28x10-2, before adding the fractions, we must adjust the exponents to make them the same. We always convert the smaller one. Here 4.28x10-2 should be convert to x103 . So we want to know which is larger and which is smaller. Inside the computer, we compare two numbers by seeing the digits from left to right. If we express the exponent using two’s complement form, the negative numbers will seem to be larger than positive numbers. For example(suppose N=4): –2=>11102, +3=> If we use biased exponent which add certain excess(here say 8=10002), we will have: –2=>01102, +3=>10112 It is obvious that 1011 is larger than 0110. 例：1.01 x x23 1.01 x x23+4 移码：0011< 0111 (3) (7) 补码：1111< 0011 ? (-1) (3) 简化比较

13 Unsigned integer(无符号整数)
机器中字的位排列顺序有两种方式：（例：32位字10112） 高到低位从左到右： 高到低位从右到左： MIPS采用高到低从左往右排列 Leftmost和rightmost这两个词有歧义，故用LSB(Least Significant Bit)来表示最低有效位，用MSB来表示最高有效位 若一个字为n位，则可表示的不同模式的字有2n个 N=4时，16种模式为0000 ~ 1111 一般在全部是正数运算且不出现负值结果的场合下，可使用无符号数表示。例如地址运算 无符号数的编码中没有符号位 在字长相同的情况下，它的表示范围大于有符号数 无符号数总是整数，所以很多时候就简称为“无符号数” 最大8位无符号整数是 B，其值为255 LSB MSB

14 Signed integer（带符号整数）
计算机必须能处理正数(positive) 和负数(negative)，MSB表示数符 有三种表示方式 Signed magnitude （原码） 用来表示浮点（实）数的尾数 One’s complement （反码） 现已不用 Two’s complement （补码） 50年代以来，所有计算机都用补码来表示定点（整）数 为什么用补码表示带符号整数？ 补码运算系统是模运算系统，加、减运算统一 数0的表示惟一，方便使用 比原码和反码多表示一个最小负数 与移码相比，其符号位和真值的符号对应关系清楚

15 带符号数和无符号数的比较 扩充操作有差别 例如，MIPS提供了两种加载指令
无符号数：lbu $t0, 0($s0) ; $t0的高24位补0 （称为0扩展） 带符号整数： lb $t0, 0($s0) ; $t0的高24位补符号 （称为符号扩展） 数的比较有差异 无符号数：MSB为1的数比MSB为0的数大 带符号整数： MSB为1的数比MSB为0的数小 例如，MIPS中提供了不同的比较指令，如： 无符号数：sltu $t0, $s0, $s1 （set less than unsigned） 带符号整数： slt $t1, $s0, $s1 （set less than） 假定： $s0= $s1= 则：$t0和$t1分别为多少？ 答案：$t0和$t1分别为0和1。 溢出判断有差异（无符号数根据最高位是否有进位来判断溢出） MIPS规定：无符号数运算溢出时，不产生“溢出异常”

16 C语言程序中的整数 假定以下关系表达式在32位用补码表示的机器上执行，结果是什么？
无符号数：unsigned int ( short / long)；带符号整数： int ( short / long) 常在一个数的后面加一个“u”或“U”表示无符号数 若同时有无符号数和带符号整数，则C编译器隐含将带符号整数强制转换为无符号数 假定以下关系表达式在32位用补码表示的机器上执行，结果是什么？ 关系表达式 运算类型 结果 说明 0 = = 0U -1 < 0 -1 < 0U > U > > (int) U -1 > -2 (unsigned) -1 > -2

17 C语言程序中的整数 假定以下关系表达式在32位用补码表示的机器上执行，结果是什么？ 带*的结果与常规预想的相反！
无符号数：unsigned int ( short / long)；带符号整数： int ( short / long) 常在一个数的后面加一个“u”或“U”表示无符号数 若同时有无符号数和带符号整数，则C编译器隐含将带符号整数强制转换为无符号数 假定以下关系表达式在32位用补码表示的机器上执行，结果是什么？ 关系表达式 运算类型 结果 说明 0 = = 0U -1 < 0 -1 < 0U > U > > (int) U -1 > -2 (unsigned) -1 > -2 无符 带符 1 0* 1* 00…0B = 00…0B 11…1B (-1) < 00…0B (0) 11…1B (232-1) > 00…0B(0) 011…1B (231-1) > 100…0B (-231) 011…1B (231-1) < 100…0B(231) 011…1B (231-1) > 100…0B (-231) 11…1B (-1) > 11…10B (-2) 11…1B (232-1) > 11…10B (232-2) 带*的结果与常规预想的相反！

18 科学计数法(Scientific Notation)与浮点数
Example: mantissa (尾数) exponent(阶码、指数) x decimal point radix (base，基) ° Normalized form（规格化形式）: 小数点前只有一位非0数 ° 同一个数有多种表示形式。例：对于数 1/1,000,000,000 • Normalized (唯一的规格化形式): 1.0 x 10-9 • Unnormalized（非规格化形式不唯一）: 0.1 x 10-8, 10.0 x 10-10 for Binary Numbers: mantissa（尾数） exponent（指数） 1.011two x binary point 基为2 Before we move on to the floating-point representation, let’s review the familiar scientific notation. For example, we can use 6.02x1021 to represent 6,020,000,000,000,000,000,000. Here, the part before x is called mantissa, the base is 10, the power of ten is called exponent. What the exponent mean? Who knows that? Exponent is used for deciding the position of decimal point. When we change exponent,the decimal point can be floated. In this example, If we change the exponent to 31, it means the number of digits of real value will be 31+1=32,the number become longer and it’s value is more larger, but we need not increase the number of digits in exponent. It’s still 2 digits. In the scientific notation, a mantissa with no leading 0s and only one digit to left of decimal point is called to be normalized. It means an normalized number should have a nonzero leftmost digit. So, there is only one normalized form, whereas there are many unnormalized forms. For example, if we want to represent 1/1,000,000,000, the normalized form is 1.0x10-9 , whereas 0.1x10-8 and 10.0x10-10n are not normalized number. In this example, the exponent is negative (-9), it means the actual decimal point should be to the left of the 9th place. With this scientific notation, We only need to describe mantissa and exponent. Every normalized mantissa is a fixed-point number because there is only one nonzero digit in the integer part. Every exponent is a integer which decides the place of decimal point, so they are short and can be also represented in fixed-point numbers. So we can use two short fixed-point numbers to represent a very long number. 只要对尾数和指数分别编码，就可表示一个浮点数（即：实数）

19 浮点数(Floating Point)的表示范围
例：画出下述32位浮点数格式的表数范围。 第0位为数符S；第1～8位为8位移码表示的阶码E（偏置常数为128）；第9～31位为24位二进制原码小数表示的尾数M。规格化尾数的第一位总是1，故规定第一位默认的“1”不明显表示出来。这样可用23个数位表示24位尾数。 S 阶码E 尾数M 最大正数：0.11…1 x 211…1 =(1-2-24) x 2127 最小正数：0.10…0 x 200…0 =(1/2) x 2-128 因为原码和移码都是对称的，所以其表示范围是关于原点对称的。 机器0：阶码为0 或 落在下溢区中的数 浮点数范围比定点数大，但数的个数没有变多，故数之间更稀疏，且不均匀

20 浮点数的表示 问题：浮点数表示不统一会带来什么问题？ +/-1.xxxxxxxxxxtwo x 2Exponent
°Normal format（规格化数形式） ： +/-1.xxxxxxxxxxtwo x 2Exponent °32-bit 规格化数： S Exponent Significand 1 bit ? bits ? bits S 是符号位（Sign） Exponent用 excess (or biased) notation(移码/增码)来表示 Significand 表示 xxxxxxxxxxxxx，尾数部分 (基可以是 2/ 4 / 8 / 16，约定信息，无需显式表示 ) °早期的计算机，各自定义自己的浮点数格式 小数点前面总是“1”，故可隐含表示 we can use the following format to represent any expressible binary number.Here,for normalized format, the leading digit before binary point is always 1. we can also assume that the base is always 2. So we only need to store sign, x’s and exponent in computers. Therefore, a floating point number has three fields, that is S for storing sign, ……, Here xxxxx is called significand. The base can be 2/ 4/ 8/ 16 , which is implicit and need not to be stored since it is the same for all numbers. Until about 1980, each manufacturer had its own floating-point format. They are all different. How many bits were used for exponent, how many for significand, and which of 2/ 4/ 8/ 16 was used for base, all of these were decided by manufactures. It led to many problems.We can not exchange floating-point data among different computers. Sometimes we may get different results for the same calculation. It is necessary to have one standard of FP representation. This is IEEE 754 Standard. Any question before move on to IEEE 754 Standard? 问题：浮点数表示不统一会带来什么问题？

21 “Father” of the IEEE 754 standard
直到80年代初，各个机器内部的浮点数表示格式还没有统一 因而相互不兼容，机器之间传送数据时，带来麻烦 1970年代后期, IEEE成立委员会着手制定浮点数标准 1985年完成浮点数标准IEEE754的制定 现在所有计算机都采用IEEE754来表示浮点数 Prof. William Kahan ieee754status/754story.html This standard was primarily the work of one person, UC Berkeley math professor William Kahan. In the late 1970s, IEEE set up a committee to standardize floating-point arithmetic. The goal was not only to permit floating-point data to be exchanged among different computers but also to provide hardware designers with a model known to be correct. The resulting work led to IEEE Standard 754 which was finished in Nowadays, most computers use IEEE 754 standard to represent floating-point numbers. This standard was primarily the work of one person, UC Berkeley math professor William Kahan. People call him the father of the IEEE 754 standard. Because of his contribution to the standard, he won ACM Turing Award in This is the highest prize in computation field, It’s equivalent to Nobel Prize.

22 IEEE 754 Floating Point Standard
Single Precision ： ( Double Precision is similar ) S Exponent Significand 1 bit bits bits ° Sign bit: 1 表示negative ; 0表示 positive °Exponent（阶码 / 指数）: SP规格化数阶码范围为 (-126) ~ (127) bias为127 (single), 1023 (double) 全0和全1编码要用来表示特殊的值！ 为什么用127？若用128,则阶码范围为多少？ °Significand（尾数）: • 规格化尾数最高位总是1，所以隐含表示，省1位 • bits （ single）， bits （double） (-127) ～ (126) IEEE 754 standard defines three formats: Single precision(32 bits), double precision (64 bits) and extended precision (80 bits). (The extended-precision format is intended to reduce round off errors. It is used primarily inside floating-point arithmetic units.) All of them start with a sign bit for the number as a whole, 1 means negative, 0 means positive. Next is the exponent, using bias (or excess) of 127 for single precision, 1023 for double precision. The minimum 0 and maximum exponent (255 and 2047) are not used for normalized numbers, because they have special uses. It means the exponents of normalized numbers range from 1 to 254 for single precision. Finally, we have significand field. Because normalized numbers always have a leading 1 before binary point, so we needn’t store this bit. In order to pack more bits, the standard use one implicit bit of leading 1 for normalized numbers. So for single precision, the mantissa of an normalized number has bits. To summarize the above information, we can get the formula for single precision number. From this formula, we can see that : if s is 1, the number will be negative, if s is 0, the number will be positive. This 1 is the implicit leading 1, and then plus significand, will be the mantissa. Because we store the biased exponent which add 127 to the real value in this bit pattern, it means that the real value of the exponent should be subtract 127 from biased exponent. For normalized double precision numbers, the formula is similar except for …. Any question for this? If we know the bit pattern of an normalized floating-point number, we can calculate the value of this number using the formula. SP: (-1)S x (1 + Significand) x 2(Exponent-127) DP: (-1)S x (1 + Significand) x 2(Exponent-1023)

23 Ex: Converting Binary FP to Decimal
BEE00000H is the hex. Rep. Of an IEEE 754 SP FP number (-1)S x (1 + Significand) x 2(Exponent-127) °Sign: 1 => negative °Exponent: • two = 125ten • Bias adjustment: = -2 °Significand: 1 + 1x2-1+ 1x x x x = = = 1.75 If we know the hexadecimal representation of an IEEE 754 single precision number, how to calculate the actual value of this number? Here is an example. Suppose the hex form is BEE00000H. At first, we should convert the hex form to binary form, we get the binary form …0000, and for single precision, we have 1 sign bit, which is 1, 8 bits for exponent, which is , and the remainder is 23-bit significand. Then we can use the formula to calculate the value. Step 1: sign bit is 1, it means the number is negative Step 2: exponent is = = =125, because we use excess 127, so we should subtract 127 to get the actual value of exponent =-2 Step 3: here actual mantissa is , so the value should be 1+…., …. The result is 1.75 Step 4: So the actual value is Any question about that? °Represents: -1.75tenx2-2 = (= x10-1 )

24 Ex: Converting Decimal to FP
1. Denormalize: 2. Convert integer part: 12 = = 11002 3. Convert fractional part: .75 = = .112 4. Put parts together and normalize: = x 23 5. Convert exponent: = = If we know the value of an number, how to represent it in floating-point form? Here is an exercise. Please spend 4 minutes to try it. Let’s check your answers. Firstly, then, and then, finally, the result is C14C0000H. Have you got that? Any question? The Hex rep. is C14C0000H

25 Normalized numbers（规格化数）
前面的定义都是针对规格化数（normalized form） How about other patterns? Exponent Significand Object anything Norms implicit leading 1 ? nonzero ? ? nonzero ?

26 Representation for 0 significand: all zeros
How to represent 0? exponent: all zeros significand: all zeros What about sign? Both cases valid. +0: -0: If exponent and significand bits are all zeros, it means the value is 0. It could be positive 0 or negative 0. They are equal.

27 Representation for +∞/-∞
∞ ：infinity In FP, 除数为0的结果是 +/- ∞, 不是溢出异常. 为什么要这样处理? • 可以利用+∞/-∞作比较。 例如：X/0 > Y 可作为一个有效比较 How to represent +∞/-∞? • Exponent : all ones ( B = 255) • Significand: all zeros +∞ : -∞ : Operations 5 / 0 = +∞, / 0 = -∞ 5+(+∞) = +∞, (+∞)+(+∞) = +∞ 5 - (+∞) = -∞, (-∞) - (+∞) = -∞ etc Do you know the infinity symbol ∞? Who can tell me the meaning of this symbol? As we know, if x!=0, when y tend to 0, then x/y tend to ∞. So IEEE 754 suggested x/0 (any finite number divided by 0)should produce infinity, not overflow. Because we can do further computations with infinity, For example, if a program have comparison X/0 > Y, it won’t produce overflow, it can be a valid comparison. If exponent bits are all ones and significand bits are all zeros, the value is infinity. It could be positive infinity or negative infinity. They are not equal. There are some operations with infinity. Any finite number add infinity will be infinity.

28 Representation for “Not a Number”
Sqrt (- 4.0) = ? /0 = ? Called Not a Number (NaN) - “非数” How to represent NaN Exponent = 255 Significand: nonzero NaNs can help with debugging Operations sqrt(-4.0) = NaN /0 = NaN op(NaN,x) = NaN ∞+(-∞) = NaN +∞-(+∞) = NaN ∞/∞ = NaN etc. Who can tell me what is the result of the square root of –4.0 ? Yes, the result is undefined. 0 divided by 0, infinity divided by infinity are all the same. If infinity is not an error, these should not be either. We call them Not a Number. We read it NaN. In this situation, the exponent bits will be all ones, the significand will be nonzero bit pattern. We can use NaN to help with debugging. If the calculating result is NaN, we can set some test point to see what happened. There are some operations which may produce NaN. We can define any finite number operate with NaN will produce NaN. Infinity minus infinity will produce NaN, and so on.

29 Representation for Denorms(非规格化数)
What have we defined so far? (for Single Precision) Used to represent Denormalized numbers Exponent Significand Object /-0 nonzero Denorms anything Norms implicit leading 1 /- infinity nonzero NaN We have defined normalized number, we briefly call them norms, we also have defined 0, infinity and NaN, we have know that: …….. we have used all combination except for this one, we can use this combination to represent denormalized numbers.

30 Representation for Denorms
1.0…0x2-126~ 1.1…1x2-126 GAP 2-125 2-124 2-123 2-126 Normalized numbers 0.0…0x2-126~ 0.1…1x2-126 As we know, in IEEE standard, normalized numbers are those with the form: +/- 1.aa…a x 2bb…b, where aa…a can be anything(from 00…0 to 11…1), bb…b can be from 00…01 ( the value is 1-127=-126) to 11…10 (the value is =127). Considering positive number, the smallest number is 1.00…0 x Between 0 and the smallest number there is a big gap. IEEE use the combination of exponent=00…0 and significand=nonzero to fill in this gap. These number are called denormalized numbers. We briefly call them denorms. In denorm form, the exponent is always 00…0, and no implicit leading 1, the significand is nonzero bit pattern. It means denormalized numbers have form of +/- 0.aa…a x , here aa…a can be 0.00…01, 0.000…10, ……., 0.11…1. Any questions about that? There are a lot of things you should think about here. Like 1….,2…..3….. 2-126 2-125 2-124 2-123 Denorms (-1) s×0.aa…a ×2-126

31 Questions about IEEE 754 What’s the range of representable values?
The largest number for single: +1.11…1X 2127 How about double? What about following type converting: not always true! if ( i == (int) ((float) i) ) { printf (“true”); } if ( f == (float) ((int) f) ) { How about FP add associative? FALSE! x = – 1.5 x 1038, y = 1.5 x 1038, z = 1.0 (x+y)+z = (–1.5x x1038 ) +1.0 = 1.0 x+(y+z) = –1.5x1038+ (1.5x ) = 0.0 约 +3.4 X 1038 约 +1.8 X 10308 How about double? True! How about double? Not always true! Any questions so far? After this class, we should think of some important questions. Here are some examples: We should know what’s the range of expressible value for single-precision and double-precision. We consider this question by finding the largest number form. For normalized form, we know the largest one is that the significand should be all ones, exponent should be , which is 254, the true value is =127, so the value of the largest number is …., which is about +1.99…99x27x2120 = +1.99…99x27x(210)12 ~ +1.99…99x1.28x102x(103)12 ~ +2.0x1038 We should know why use biased exponent. Considering the addition operation for two scientific notation numbers, 3.12x x10-2, before adding the fractions, we must adjust the exponents to make them the same. We always convert the smaller one. Here 4.28x10-2 should be convert to x103 . So we want to know which is larger and which is smaller. Inside the computer, we compare two numbers by seeing the digits from left to right. If we express the exponent using two’s complement form, the negative numbers will seem to be larger than positive numbers. For example(suppose N=4): –2=>11102, +3=> If we use biased exponent which add certain excess(here say 8=10002), we will have: –2=>01102, +3=>10112 It is obvious that 1011 is larger than Generally, we always choose 2N-1 as the excess(or bias) for N bits number. Before IEEE 754 standard, Almost all the computer did in this way. IEEE 754 chose 2N-1 –1, it’s a clever selection, because it can enlarge the range of the expressible value. Say N=4, if we choose 1000 as bias, the largest number is +7 (=>11112), if we choose 0111 as bias, the largest number can be +8 (=>11112) For the first case, we convert i from int to float and then to int. If i is a very large integer, it will lose some lower significant digits when converting to float (because 31>24). So it will be not true. How about Double? (it’s OK, because 31<53). For the second case, we convert f from float to int and then to float. If f is a very small number (<1), it will have no integer representation when converting to int. So it will be not always true. How about Double? The situation is the same, so it’s also not always true. When we add a very small number to a very large number, we will get the result which is exact the larger number. Because we should adjust the exponents to make them the same, so for very small exponent, the significand will be lost after moving the point to left and truncating the lower significant digits.

32 十进制数的表示 数值数据（numerical data）的两种表示 Binary (二进制数)
定点整数：Fixed-point number (integer) Unsigned and signed int 浮点数：Floating-point number (real number) Decimal (十进制数) 用ASCII码表示 用BCD（Binary coded Decimal）码表示 计算机中为什么要用十进制数表示数值？ 日常使用的都是十进制数，所以，计算机外部都使用十进制数。在一些有大量数据输入/出的系统中，为减少二进制数和十进制数之间的转换，在计算机内部直接用十进制数表示数值。 BCD码用在一些要求直接用十进制数进行计算的场合。这种十进制数用二进制进行编码的形式被称为BCD码（BinaryCoded Decimal）。许多计算机都有专门的十进制运算指令，并有专门的逻辑线路在BCD码运算时使每4位二进制数按十进制处理。 例如，处理1000个信息，需要3位十进制数，因而至少需要3×4=12位的设备量，而对于二进制系统，因为210=1024，所以只需10位的设备量就足够了。

33 用ASCII码表示十进制数 缺点：占空间大，且需转换成二进制数或BCD码才能计算。 前分隔数字串 符号位单独用一个字节表示，位于数字串之前。
正号用“+”的ASCII码(2BH)表示；负号用“-”的ASCII码(2DH)表示 例：十进制数+236表示为: 2B H B 十进制数-2369表示为: 2D H B 后嵌入数字串 符号位嵌入到最低一位数字的ASCII码的高4位中。比前分隔方式省一个字节。 正数不变；负数高4位变为0111. 例：十进制数+236表示为: H B 十进制数-2369表示为: H B 缺点：占空间大，且需转换成二进制数或BCD码才能计算。

34 用BCD码表示十进制数 编码思想 编码方案 3．其他编码方案 （5中取2码、独热码等） 符号位的表示：
每个十进数位必须至少有4位二进制位来表示。而4位二进制位可以组合成16种状态，去掉10种状态后还有6种冗余状态。 编码方案 1． 十进制有权码 指表示每个十进制数位的4个二进制数位（称为基2码）都有一个确定的权。8421码是最常用的十进制有权码。也称自然BCD（NBCD）码。 2． 十进制无权码 指表示每个十进制数位的4个基2码没有确定的权。在无权码方案中，用的较多的是余3码和格雷码。 3．其他编码方案 （5中取2码、独热码等） 符号位的表示： “+”：1100 ； “-”：1101 例：+236=( ) (占2个字节) - 2369=( ) (占3个字节) 每位十进制数的取值可以是0/1/2/…/9这十个数之一，因此，每一个十进制数位必须至少有4位二进制位来表示。而4位二进制位可以组合成16种状态，去掉10种状态后还有6种冗余状态，所以从16种状态中选取10种状态表示十进制数位0 ~ 9的方法很多，可以产生多种BCD码方案。 补0以使数占满一个字节

35 第一讲小结 计算机内所有信息都用二进制编码，在机器内部编码后的数称为机器数，其值称为真值 定义数值数据有三个要素：进制、定点/浮点、编码
定点数编码：原码、补码、移码 定点数： 定点整数：表示整数或浮点数中的指数（阶码）；定点小数：表示浮点数中的尾数 整数的表示 无符号数：正整数，用来表示地址等；带符号整数：用补码表示 C语言中的整数 无符号数：unsigned int ( short / long)；带符号数： int ( short / long) 浮点数的表示 符号；尾数：定点小数；指数（阶）：定点整数（基不用表示） 浮点数的范围 不可表示区域：正上溢、正下溢、负上溢、负下溢；与阶码的位数和基的大小有关 浮点数的精度 与尾数的位数和是否规格化有关；规格化操作：左规、右规 浮点数的表示（IEEE754标准）：单精度SP（float）和双精度DP（double） 规格化数(SP)：阶码1~254，尾数最高位隐含为1 “零” (阶为全0，尾为全0) ∞ (阶为全1，尾为全0) NaN (阶为全1，尾为非0) 非规格化数 (阶为全0，尾为非0) 十进制数的表示：用ASCII码、BCD码表示

36 第二讲 非数值数据、数据排列、纠/检错 主 要 内 容 非数值数据的表示 数据的宽度 数据的存储排列 数据的纠错和检错 逻辑数据 西文字符
主 要 内 容 非数值数据的表示 逻辑数据 西文字符 汉字 数据的宽度 数据的存储排列 大端方式 小端方式 数据的纠错和检错 奇偶校验 海明校验 循环冗余校验

37 逻辑数据的编码表示 表示 用一位表示 真：1 / 假：0 N位二进制数可表示N个逻辑数据，或一个位串 运算 按位进行
用一位表示 真：1 / 假：0 N位二进制数可表示N个逻辑数据，或一个位串 运算 按位进行 如:按位与 / 按位或 / 逻辑左移 / 逻辑右移 等 识别 逻辑数据和数值数据在形式上并无差别，也是一串0/1序列，机器靠指令来识别。

38 西文字符的编码表示 特点 是一种拼音文字，用有限几个字母可以拼写出所有单词 只要对有限个少量字母和数学符号、标点符号等辅助字符进行编码
所有字符总数不超过256个，使用7或8个二进位可表示 表示（常用编码为7位ASCII码） 要求必须熟悉数字、字母和空格(SP)的表示 十进制数字：0/1/2…/9 英文字母：A/B/…/Z/a/b/…/z 专用符号：+/-/%/*/&/…… 控制字符（不可打印或显示） 操作 字符串操作，如:传送/比较　等

39 汉字及国际字符的编码表示 特点 编码形式 问题：西文字符有没有输入码？有没有内码？有没有字模点阵码或轮廓描述？
汉字是表意文字，一个字就是一个方块图形。 汉字数量巨大，总数超过6万字，给汉字在计算机内部的表示、汉字的传输与交换、汉字的输入和输出等带来了一系列问题。 编码形式 有以下几种汉字代码： 输入码：对汉字用相应按键进行编码表示，用于输入。 　内码：用于在系统中进行存储、查找、传送等处理。 　字模点阵码或轮廓描述: 描述汉字字模点阵或轮廓，用于显示/打印。 问题：西文字符有没有输入码？有没有内码？有没有字模点阵码或轮廓描述？

40 汉字的输入码 向计算机输入汉字的方式： 使用汉字输入码的原因：
① 手写汉字联机识别输入，或者是印刷汉字扫描输入后自动识别，这两种方法现均已达到实用水平。 ② 用语音输入汉字，虽然简单易操作，但离实用阶段还相差很远。 ③ 利用英文键盘输入汉字： 每个汉字用一个或几个键表示，这种对每个汉字用相应的按键进行的编码表示称为汉字的“输入码”，又称外码。输入码的码元为键盘上的按键。这是最简便、最广泛采用的汉字输入方法。 常用的方法有：搜狗拼音、五笔字型、智能ABC、微软拼音等 使用汉字输入码的原因： ① 键盘面向西文设计，一个或两个西文字符对应一个按键，非常方便。 ② 汉字是大字符集，专门的汉字输入键盘由于键多、查找不便、成本高等原因而几乎无法采用。

41 字符集与汉字的内码 问题：西文字符常用的内码是什么？ 其内码就是ASCII码。 对于汉字内码的选择，必须考虑以下几个因素：
② 尽量与汉字在字库中的位置有关系，便于汉字查找和处理。 ③ 编码应尽量短。 国标码（国标交换码） 1981年我国颁布了《信息交换用汉字编码字符集·基本集》(GB2312—80)。该标准选出6763个常用汉字，为每个汉字规定了标准代码，以供汉字信息在不同计算机系统之间交换使用。 可在汉字国标码的基础上产生汉字机内码

42 GB2312-80字符集 由三部分组成： 汉字的区位码 汉字的国标码 ② 一级常用汉字，共3755个，按汉语拼音排列；
① 字母、数字和各种符号，包括英文、俄文、日文平假名与片假名、罗马字母、汉语拼音等共687个； ② 一级常用汉字，共3755个，按汉语拼音排列； ③ 二级常用汉字，共3008个 ，因不太常用，所以按偏旁部首排列。 汉字的区位码 码表由94行、94列组成，行号称为区号，列号称为位号，各占7位 指出了该汉字在码表中的位置。区位码共14位，区号在左、位号在右 汉字的国标码 每个汉字的区号和位号各自加上32（20H），得到它的“国标码” 国标码中区号和位号各占7位。在计算机内部，为方便处理与存储，前面添一个0，构成一个字节。

43 汉字内码 至少需2个字节才能表示一个汉字内码，为什么？ 可在GB2312国标码的基础上产生汉字内码 国际字符集的必要性 国际多字符集，例如：
将国标码的两个字节的第一位置“1”后得到内码 例如，汉字“大”的国标码为：3473h（ B），前面的34h和字符“4”的ACSII码相同，后面的73h和字符“s”的ACSII码相同，将每个字节的最高位各设为“1”后，就得到其内码：B4F3h ( B)。 国际字符集的必要性 不同地区使用不同的字符集内码，如中文GB2312/Big5、日文Shift-JIS/EUC-JP等。一台安装了中文系统的计算机，若打开一个日文文件，便会出现乱码。为使所有国际字符都能互换，必须创建一种涵盖全部字符的多字符集。通过对已有各种地区性字符集规定使用范围来唯一定义各字符的编码。 国际多字符集，例如： 国际标准ISO/IEC 10646提出了一种包括全世界现代书面语言文字所使用的所有字符的标准编码，每个字符用4个字节编码(UCS-4)和2字节编码(UCS-2) 。 我国（包括香港、台湾地区）与日本、韩国联合制订了一个统一的汉字字符集（CJK编码），共收集了上述不同国家和地区的共约2万多汉字及符号，采用2字节编码(即：UCS-2) ，现已被批准为国家标准(GB13000 )。 微软公司新板的Windows操作系统(中文版)中已采用中西文统一编码，收集了中、日、韩三国常用的约2万汉字，称为“Unicode”，采用2字节编码，与UCS-2一致 。  

44 汉字的字模点阵码和轮廓描述 为便于汉字的打印、显示等，每个汉字的字形都必须预先存在机内
一套汉字所有字符的形状描述信息集合在一起称为字形信息库，简称字库 (font) 不同字体 (如宋体、仿宋、楷体、黑体等) 对应不同字库 输出汉字时，先到字库中找到字形描述信息，然后送相应设备输出 字形主要有两种描述方法： 字模点阵描述（图像方式） 轮廓描述（图形方式） 直线向量轮廓 曲线轮廓（True Type字形）

45 数据的基本宽度 比特（bit）是计算机中处理、存储、传输信息的最小单位
在计算机内部，二进制信息的计量单位是“字节”(Byte)，也称“位组” 现代计算机中，存储器按字节编址 字节是最小可寻址单位(addressable unit ) 除了比特和字节之外，还经常使用“字”(word)作为单位 “字”和 “字长”的概念不同 “字长”指数据通路的宽度。 （数据通路指CPU内部的数据流经的路径以及路径上的部件，主要是CPU内部进行数据运算、存储和传送的部件，这些部件的宽度基本上要一致，才能相互匹配。因此，“字长”应该等于CPU内部总线的宽度、运算器的位数、通用寄存器的宽度等。 ） “字”用来表示被处理信息的单位，用来度量各种数据类型的宽度。 字和字长的宽度可以一样，也可不同。 例如，Intel微处理器从386开始就是32位字长，但其定义的“字”的宽度为16位

46 数据量的度量单位 存储二进制信息时的度量单位要比字节或字大得多 容量经常使用的单位有： 通信中的带宽使用的单位有：
“千字节”(KB)，1KB=210字节=1024B “兆字节”(MB)，1MB=220字节=1024KB “千兆字节”(GB)，1GB=230字节=1024MB “兆兆字节”(TB)，1TB=240字节=1024GB 通信中的带宽使用的单位有： “千比特/秒”(kb/s)，1kbps=103 b/s=1000 bps “兆比特/秒”(Mb/s)，1Mbps=106 b/s =1000 kbps “千兆比特/秒”(Gb/s)，1Gbps=109 b/s =1000 Mbps “兆兆比特/秒”(Tb/s)，1Tbps=1012 b/s =1000 Gbps 如果把b换成B，则表示字节而不是比特（位） 例如，10MBps表示 10兆字节/秒

47 程序中数据类型的宽度 char short int int long int 1 2 4 8 char* float double
高级语言支持多种类型、多种长度的数据 例如，C语言中Char类型的宽度为1个字节，可表示一个字符（非数值数据），也可表示一个8位的整数（数值数据） 不同机器上表示的同一种类型的数据可能宽度不同 必须能够提供相应的机器级数据表示和相应的处理指令 (在第五章指令系统介绍具体指令) C语言中数值数据类型的宽度 (单位：字节) C声明 典型32位机器 Compaq Alpha机器 char short int int long int 1 2 4 8 char* float double 从表中看出：同类型数据并不是所有机器都采用相同的宽度，分配的字节数随机器的字长和编译器的不同而不同。 Compaq Alpha是一个针对高端应用的64位机器，即：字长为64位。

48 数据的存储和排列顺序 Word: BYTE Addressing: (字节编址) 80年代开始，几乎所有机器都用字节编址
ISA设计时要考虑的两个问题： 如何从一个字节地址中取到一个32位的字？- 字的存放问题 一个字能否存放在任何字节边界？- 字的边界对齐问题 例如，若 int i = 0x ，存放在内存100号单元，则用“取数”指令访问100号单元取出 i 时，必须清楚i的4个字节是如何存放的。 msb lsb little endian word 100 big endian word 100 Word: 大端方式（Big Endian）: MSB所在的地址是数的地址 e.g. IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA 小端方式（ Little Endian）: LSB所在的地址是数的地址 e.g. Intel 80x86, DEC VAX 有些机器两种方式都支持，可以通过特定的控制位来设定采用哪种方式。

49 BIG Endian versus Little Endian
Example 1: Memory layout of a number ABCDH located in 1000 In Big Endian: CD AB 1001 1000 In Little Endian: AB CD 1001 1000 Example 2: Memory layout of a number 00ABCDEFH located in 1000 In Big Endian: 00 AB CD EF 1000 1001 1002 1003 In Little Endian: 00 AB CD EF 1003 1002 1001 1000 Example 3: Memory layout of a instruction located in 1000 假定小端机器中指令：mov AX, 0x12345(BX) 其中操作码mov为40H，寄存器AX和BX分别为 0001B和0010B，立即数占32位，则存放顺序为： MOV AX BX 0x 45 23 01 00 12 40 00 01 23 45 12 40 1005 1004 1003 1002 1001 1000 40 1 2 若在大端机器上，则存放顺序如何？ 40 1 2

50 Byte Swap Problem（字节交换问题）
78 3 12 3 56 2 34 2 34 1 increasing byte address 56 1 12 78 Big Endian Little Endian 上述存放在0号单元的数据（字）是什么？ H？ H？ 两个存放方式不同的机器间程序移植或数据通信时，会发生什么问题？ 每个系统内部都是一致的，但在系统间通信时可能会发生问题！ 因为顺序不同，需要顺序转换 任何像音频、视频和图像等文件格式或处理程序都涉及到字节顺序问题 ex. Little endian: GIF, PC Paintbrush, Microsoft RTF,etc Big endian: Adobe Photoshop, JPEG, MacPaint, etc

51 Alignment(对齐) Alignment: 要求数据的地址是相应边界地址
目前计算机所用数据字长一般为32位或64位，而存储器地址按字节编址 指令系统支持对字节、半字、字及双字的运算，也有位处理指令 各种不同长度的数据存放时，有两种处理方式: 按边界对齐 （假定字的宽度为32位，按字节编址） 字地址：4的倍数(低两位为0) 半字地址：2的倍数(低位为0) 字节地址：任意 不按边界对齐 坏处：可能会增加访存次数！ （学了第四章存储器组织后会更明白！）

52 Alignment(对齐) 0004081216 0004081216 示例 假设数据顺序：字-半字-双字-字节-半字-…… 按边界对齐
示例 假设数据顺序：字-半字-双字-字节-半字-…… 按边界对齐 边界不对齐 如：int i, short k, double x, char c, short j,…… 0 字节 1字节 2字节 3字节 x：2个周期 j：1个周期 则：&i=0; &k=4; &x=8; &c=16; &j=18;…… 0 字节 1字节 2字节 3字节 x：3个周期 j：2个周期 增加了访存次数！ 则： &i=0; &k=4; &x=6; &c=14; &j=15;……

53 数据的检/纠错（Error Detect/Correct）
为什么要进行数据的错误检测与校正？ 计算、存取和传送时，由于元器件故障或噪音干扰等原因会出现差错。措施： (1) 从计算机硬件本身的可靠性入手，在电路、电源、布线等各方面采取必要的措施，提高计算机的抗干扰能力； (2) 采取相应的数据检错和校正措施，自动地发现并纠正错误。 如何进行错误检测与校正？ 大多采用“冗余校验”思想，即除原数据信息外，还增加若干位编码，这些新增的代码被称为校验位。 存储器 或 传输线路 f 比较 纠正器 M P M’ P” P’ 出错信号 数据输出 数据输入

54 数据的检/纠错 f 数据检/校过程： 存储器 或 传输线路 比较 纠正器 M P M’ P” P’ 出错信号 数据输出 数据输入
数据被存入存储器或从源部件传输时，对数据M进行某种运算（用函数f 表示），以产生相应的代码P= f (M)，这里P就是校验位。这样原数据信息和相应的校验位一起被存储或传送。当数据被读出或传送到终部件时，和数据信息一起被存储或传送的校验位也被得到，用于检错和纠错。假定读出后的数据为M’，通过同样的运算f 对M’也得到一个新的校验位P’=f (M’)，假定原来被存储的校验位P取出后其值为P’’，将校验位P’’与新生成的校验位P’进行某种比较，根据其比较结果确定是否发生了差错。 比较的结果为以下三种情况之一： ① 没有检测到错误，得到的数据位直接传送出去。 ② 检测到差错，并可以纠错。数据位和比较结果一起送入纠错器，将正确数据位传送出去。 ③ 检测到错误，但无法确认哪位出错，因而不能进行纠错处理，此时，报告出错情况。 存储器 或 传输线路 f 比较 纠正器 M P M’ P” P’ 出错信号 数据输出 数据输入 BACK

55 码字和码距 什么叫码距？ 数据校验中的“码字”是指数据位和校验位按某种规律排列得到的代码 码距与检错、纠错能力的关系（当d≤4）
由若干位代码组成的一个字叫“码字” 两个码字中具有不同代码的位的个数叫做这两个码字间的“距离” 一种码制各码字间的最小距离称为“码距”，它就是这个码制的距离。 　　问题：“8421”码的码距是几？ 2（0010）和3（0011）间距离为1，“8421”码制的码距为1。 数据校验中的“码字”是指数据位和校验位按某种规律排列得到的代码 码距与检错、纠错能力的关系（当d≤4） 　　① 如果码距d为奇数，则能发现d-1位错，或者能纠正(d-1)/2位错。 　　② 如果码距d为偶数，则能发现d /2位错，并能纠正(d/2-1)位错。 常用的数据校验码有： 　　奇偶校验码、海明校验码和循环冗余校验码。

56 奇偶校验码 　基本思想：增加一位奇校验位（或偶校验位），然后将原数据和得到的校验位一起进行存储或传送，对存取后或在传送的终部件得到的相应数据和校验位，再进行一次编码，求出新校验位，最后根据得到的这个新校验位的值，确定是否发生了错误。 　实现原理：假设将数据B=bn-1bn-2...b1b0从源部件传送至终部件。在终部件接收到的数据为B’=bn-1’bn-2’...b1’b0’。 　第一步：在源部件求出奇（偶）校验位P。 　　　若采用奇校验，则P=bn-1⊕bn-2 ⊕...⊕b1⊕b0⊕1。 　　　若采用偶校验，则P=bn-1⊕bn-2 ⊕...⊕b1⊕b0。 　第二步：在终部件求出奇（偶）校验位P’。 　　　若采用奇校验，则P’= bn-1’⊕bn-2 ’⊕...⊕b1’⊕b0’⊕1。 　　　若采用偶校验，则P’=bn-1’⊕bn-2 ’⊕...⊕b1’⊕b0’。 　第三步：计算最终的校验位P*，并根据其值判断有无奇偶错。 　　假定P在终部件接受到的值为P’’，则P*= P’⊕P” 　　① 若P*=1，则表示终部件接受的数据有奇数位错。 　　② 若P*=0，则表示终部件接受的数据正确或有偶数个错。

57 奇偶校验法的特点 特点： 优点： 问题：奇偶校验码的码距是几？为什么？
码距d=2。在奇偶校验码中，若两个数中有奇数位不同，则它们相应的校验位就不同；若有偶数位不同，则虽校验位相同，但至少有两位数据位不同。因而任意两个码字之间至少有两位不同。 根据码距和纠/检错能力的关系，它只能发现奇数位出错，不能发现偶数位出错，而且也不能确定发生错误的位置，不具有纠错能力。 优点： 开销小 适用于校验一字节长的代码，故常被用于存储器读写检查或按字节传输过程中的数据校验 因为一字节长的代码发生错误时，1位出错的概率较大，两位以上出错则很少，所以可用奇偶校验。

58 海明校验码 每一组一个校验位，校验码位数等于组数！ 由Richard Hamming于1950年提出，目前还被广泛使用。
主要用于存储器中数据存取校验。 基本思想：奇偶校验码对整个数据编码生成一位校验位。因此这种校验码检错能力差，并且没有纠错能力。如果将整个数据按某种规律分成若干组，对每组进行相应的奇偶检测，就能提供多位检错信息，从而对错误位置进行定位，并将其纠正。 海明校验码实质上就是一种多重奇偶校验码。 处理过程： 最终比较时按位进行异或，根据异或结果，确定是否有差错。 这种异或操作所得到的结果称为故障字（syndrome word）。显然，校验码和故障字的位数是相同。 每一组一个校验位，校验码位数等于组数！

59 校验码位数的确定 1+n+k种情况 2K≥1+n+k， 即：2K-1≥n+k
假定数据位数为n，校验码为k位，则故障字的位数也为k位。k位故障字所能表示的状态最多是2K，每种状态可用来说明一种出错情况。 若只有一位错，则结果可能是： 数据中某一位错 (n种可能) 校验码中有一位错 (k种可能) 无错 ( 1 种可能) 要能对最多一位错的所有结果进行正确表示，则n和k必须满足下列关系： 2K≥1+n+k， 即：2K-1≥n+k 有效数据位数和校验码位数间的关系 从表中可以看出，当数据有8位时，校验码和故障字都应有4位。 说明：4位的故障字最多可以表示16种状态，而单个位出错情况最多只有12种可能（8个数据位和4个校验位），再加上无错的情况，一共有13种。所以，用16种状态表示13种情况应是足够了。 1+n+k种情况

60 有效数据位数和校验码位数间的关系 单纠错 单纠错/双检错 数据位数 校验位数 增加百分率 8 4 50 5 62.5 16 31.25 6 37.5 32 18.75 7 21.875 64 10.94 12.5 128 6.25 9 7.03 256 3.52 10 3.91

61 海明码的分组 基本思想:　数据位和校验位按某种方式排列为一个n+k的码字，将该字中每一位的出错位置与故障字的数值建立关系，通过故障字的值确定该码字中哪一位发生了错误，并将其取反来纠正。 　 根据上述基本思想，按以下规则来解释各故障字的值。 规则1： 若故障字每位全部是0，则表示没有发生错误。 规则2：若故障字中有且仅有一位为1，则表示校验位中有一位出错，因而不需纠正。 规则3：若故障字中多位为1，则表示有一个数据位出错，其在码字中的出错位置由故障字的数值来确定。纠正时只要将出错位取反即可。

62 海明码的分组 以8位数据进行单个位检错和纠错为例说明。
假定一个8位数据M= M8M7M6M5M4M3M2M1，其相应的4位校验位为P=P4P3P2P1。根据规则将数据M和校验位P按一定的规律排到一个12位码字中。 据规则1，故障字为0000时，表示无错，因此没有和位置号0000对应的出错情况，所以位置号从0001开始。 据规则2，故障字中有且仅有一位为1时，表示校验位中有一位出错，此时，故障字只可能是0001、0010、0100、1000四种情况，我们将这四种状态分别代表校验位中第P1、P2、P3、P4位发生错误的情况，因此，校验位P1、P2、P3、P4应分别位于码字的第1、2、4、8位。 据规则3，将其他多位为1的故障字依次表示数据位M1~M8发生错误的情况。因此，数据位M1~M8应分别位于码字的第0011(3)、0101(5)、0110(6)、0111(7)、1001(9)、1010(10)、1011(11)、1100(12)位。即码字的排列为： M8M7M6M5P4M4M3M2P3M1P2P1 这样，得到故障字S=S4S3S2S1的各个状态和出错情况的对应关系表，可根据这种对应关系对整个数据进行分组。 逻辑上的一个顺序，物理上M和P是分开的

63 海明校验码分组情况 根据故障字S4S3S2S1的值确定哪位出错，因此，某位出错一定会影响与之相对应的故障字中为1的位所在组的奇偶性。
例：若M1出错，则故障字为0011，所以一定会改变S2和S1所在分组的奇偶性。故M1同时被分到第2(S2)组和第1(S1) 组。 码字：M8M7M6M5P4M4M3M2P3M1P2P1 问题：若P1出错，则如何？若M8出错，则如何？ P1~0001，分在第1组 M8~1100，分在第4组和第3组 BACK

64 校验位的生成和检错、纠错 分组完成后，就可对每组采用相应的奇（偶）校验，以得到相应的一个校验位。
假定采用偶校验 (取校验位Pi，使对应组中有偶数个1)，则得到校验位与数据位之间存在如下关系： 　　　 P1 = M1⊕M2⊕M4⊕M5⊕M7 　　　P2 = M1⊕M3⊕M4⊕M6⊕M7 　　　P3 = M2⊕M3⊕M4⊕M8 　　　P4 = M5⊕M6⊕M7⊕M8

65 海明校验过程 f 根据公式求出每一组对应的校验位Pi (i=1,2,3,4) 数据M和校验位P一起被存储，根据读出数据M’，得新校验位P’
读出校验位P’’与新校验位P’ 按位进行异或操作，得故障字 S = S4S3S2S1 根据S的值确定：无错、仅校验位错、某个数据位错 存储器 或 传输线路 f 比较 纠正器 M P M’ P” P’ 出错信号 数据输出 数据输入

66 海明码举例 假定一个8位数据M为：M8M7M6M5M4M3M2M1= 01101010，根据上述公式求出相应的校验位为：
　　P1 = M1⊕M2⊕M4⊕M5⊕M7 =0⊕1⊕1⊕0⊕1=1 　　P2 = M1⊕M3⊕M4⊕M6⊕M7 =0⊕0⊕1⊕1⊕1=1 　　P3 = M2⊕M3⊕M4⊕M8=1⊕0⊕1⊕0=0 　　P4 = M5⊕M6⊕M7⊕M8=0⊕1⊕1⊕0=0 　假定12位码字(M8M7M6M5P4M4M3M2P3M1P2P1)读出后的结果是: (1) 数据位M’=M= ，校验位P’’=P=0011 (2) 数据位M’= ，校验位P’’=P=0011 (3) 数据位M’=M= ，校验位P’’= 1011 　要求分别考察每种情况的故障字。 (1) 数据位M’=M= ，校验位P’’=P=0011，即：所有位都无错。 这种情况下，因为M’=M，所以P’= P， 因此 S = P’’⊕P’=P⊕P = 0000。

67 海明码举例 (2) 数据位M’= 01111010，校验位P’’=P=0011，即：数据位第5位(M5)错。
P1 ’= M1’⊕M2’⊕M4’⊕M5’⊕M7’=0⊕1⊕1⊕1⊕1=0 P2’ = M1’⊕M3’⊕M4’⊕M6’⊕M7’ =0⊕0⊕1⊕1⊕1=1 P3 ’= M2’⊕M3’⊕M4’⊕M8’=1⊕0⊕1⊕0=0 P4’ = M5’⊕M6’⊕M7’⊕M8’=1⊕1⊕1⊕0=1 故障字S为： S1= P1 ’⊕ P1’’= 0⊕1=1 S2= P2 ’⊕ P2’’=1⊕1=0 S3= P3 ’⊕ P3’’=0⊕0=0 S4= P4 ’⊕ P4’’=1⊕0=1 根据故障字的数值1001，可以判断出发生错误的位是在12位码字的第 1001位(即：第9位)，在这一位上排列的是数据位M5，所以检错正确, 纠错时，只要将码字的第9位（即：第5个数据位）取反即可。

68 海明码举例 (3) 数据位M’=M=01101010，校验位P’’= 1011， 即：校验码第4位(P4)错。
这种情况下，因为M’=M，所以P’= P，因此故障位S为： S1= P1 ’⊕ P1’’= 1⊕1=0 S2= P2 ’⊕ P2’’=1⊕1=0 S3= P3 ’⊕ P3’’=0⊕0=0 S4= P4 ’⊕ P4’’=0⊕1=1 根据故障字的数值1000，可以判断出发生错误的位是在12位码字的第1000位(即：第8位)，在这一位上排列的是校验位P4，所以检错正确，不需纠错。

69 单纠错和双检错码 单纠错码（SEC） 问题：上述(n=8/k=4)海明码的码距是几？
码距d=3。因为，若有一位出错，则因该位至少要参与两组校验位的生成，因而至少引起两个校验位的不同。两个校验位加一个数据位等于3。 根据码距与检错、纠错能力的关系，知：这种码制能发现两位错，或对单个位出错进行定位和纠错。这种码称为单纠错码（SEC）。 单纠错和双检错码（SEC-DED） 如果校验码同时具有发现两位错和纠正一位错的能力，则称为单纠错和双检错码（SEC-DED）。 一般半导体存储器都采用这种校验码进行数据校验。 若要使上述单纠错码成为SEC-DED ，则码距需扩大到d= 4。为此，还需要增加一位校验位P5，将P5排列在码字的最前面，即：P5M8M7M6M5P4M4M3M2P3M1P2P1，并使得数据中的每一位都参与三个校验位的生成。从表中可看出除了M4 和M7参与了三个校验位的生成外，其余位都只参与了两个校验位的生成。因此P5按下式求值： 　　　 P5= M1⊕M2⊕M3⊕M5⊕M6⊕M8 当任意一个数据位发生错误时，必将引起三个校验位发生变化，所以码距为4。

70 SEC-DED的检错／纠错规则 ① 当S5S4S3S2S1为00000时，表明无错。
　　引入P5后，故障字S也增加了一位，即S=S5S4S3S2S1，根据S5S4S3S2S1的取值情况，可按如下规则发现两位错并纠正一位错。 ① 当S5S4S3S2S1为00000时，表明无错。 ② 当S5S4S3S2S1中仅一位不为0时，表明由S指定的位置上那个校验位发生了错误，或是在数据和校验位中有三位同时出错，但后面这种可能性非常小，所以一般认为发生了前一种情况。 　　③ 当S5S4S3S2S1中有两位不为0时，表明数据和校验位中有两位同时出错，此时只能发现这种错误，但无法确定是哪两位错。 　　④ 当S5S4S3S2S1中有三位不为0时，表明有一个数据位发生了错误，或是三个校验位同时出错，但后面这种可能性非常小，所以一般认为发生了前一种情况。此时，出错的位置由S4S3S2S1的数值指定。 　　⑤ 当S5S4S3S2S1中有四位或五位都不为0时，表明出错情况严重，系统可能出现故障，应检查系统硬件的正确性。

71 循环冗余码 循环冗余校验码（Cyclic Redundancy Check），简称CRC码 具很强的检错、纠错能力。
用于大批量数据存储和传送(如：外存和通信)中的数据校验。 奇偶校验码是在每个字符信息后增加一位校验位进行数据校验的，这样对大批量传输数据进行校验时，会增加大量的额外开销，尤其是在网络通信中，传输的数据信息都是二进制比特流，因而没有必要将数据再分解成一个个字符，也就无法采用奇偶校验码，因此，通常采用CRC码进行校验。 通过某种数学运算来建立数据和校验位之间的约定关系。 奇偶校验码和海明校验码都是以奇偶检测为手段的。 网络或通信课程中会学到。

72 CRC码的检错方法 基本思想： 数据(n位) 校验位(k位) CRC码(n+k位)
假设要进行校验的数据信息M(x)为一个n位的二进制数据，将M(x)左移k位后，用一个约定的“生成多项式”G(x)相除，G(x)是一个k+1位的二进制数，相除后得到的k位余数就是校验位。这些校验位拼接到M(x)的n位数据后面，形成一个n+k位的代码，我们称这个代码为循环冗余校验 ( CRC ) 码，也称 （n+k,n）码。 一个CRC码一定能被生成多项式整除，所以当数据和校验位一起送到接受端后，只要将接受到的数据和校验位用同样的生成多项式相除，如果正好除尽，表明没有发生错误；若除不尽，则表明某些数据位发生了错误。 数据(n位) 校验位(k位) CRC码(n+k位)

73 循环冗余码举例 校验位的生成：用一个例子来说明校验位的生成过程。 假设要传送的数据信息为：100011，即报文多项式为：
M(x)= x5 + x + 1。数据信息位数n=6。 若约定的生成多项式为：G(x)= x3+ 1，则生成多项式位数为4位，所以校验位位数k=3，除数为1001。 生成校验位时，用x3.M(x)去除以G(x)，即： ÷1001。 相除时采用“模２运算”的多项式除法。

74 循环冗余码举例 X3.M(x)÷G(x)＝(x8+ x4 + x3)÷(x3 + 1) 100111 1001 0011 0000 0111 1110 111 (模２运算不考虑加法进位和减法借位，上商的原则是当部分余数首位是１时商取１，反之商取０。然后按模２相减原则求得最高位后面几位的余数。这样当被除数逐步除完时，最后的余数位数比除数少一位。这样得到的余数就是校验位，此例中最终的余数有3位。) 校验位为111，CRC码为 。如果要校验CRC码，则可将CRC码用同一个多项式相除，若余数为0，则说明无错；否则说明有错。例如，若在接收方的CRC码也为 时，用同一个多项式相除后余数为0。若接收方CRC码不为 时，余数则不为0。

75 第二讲小结 非数值数据的表示 数据的宽度 数据的存储排列 数据的纠错和检错 逻辑数据用来表示真/假或N位位串，按位运算
西文字符：用ASCII码表示 汉字：汉字输入码、汉字内码、汉字字模码 数据的宽度 位、字节、字（不一定等于字长），k/K/M/G/…有不同的含义 数据的存储排列 大端方式：用MSB存放的地址表示数据的地址 小端方式：用LSB存放的地址表示数据的地址 按边界对齐可减少访存次数 数据的纠错和检错 奇偶校验：适应于一字节长数据的校验 海明校验：分组后，各组内用奇偶校验，用于内存储器数据的校验 循环冗余校验：用在通信和外存中，适合于大批量数据的校验

76 附录： Decimal / Binary（十 / 二进制数）
The decimal number in powers of 10: 5     10 0 + 4   10 -2 The binary number in powers of 2 : 用一个下标表示数的基（ radix / base） = 2510 1      2 0 = = 25

77 附录： Octal / Hexadecimal ( 八 / 十六进制数)
23=8 24=16 计算机用二进制表示所有信息！ 为什么要引入 8 / 16进制？ 8 / 16进制是二进制的简便表示。便于阅读和书写！ 它们之间对应简单，转换容易。 在机器内部用二进制，在屏幕或其他外部设备上表示时，转换为8/16进制数，可缩短长度

78 附录： Conversions of numbers
按“权”展开 (a power of R) 例1: ( )2=1x24+1x 22+1x20+1x2-2=(21.25)10 例2: (307.6)8=3x82+7x80+6x8-1=(199.75)10 例1: (3A. 1)16=3x161+10x160+1x16-1=( )10 (2)十进制数 => R进制数 整数部分和小数部分分别转换 ① 整数(integral part)----“除基取余，上右下左” ② 小数(fractional part)----“乘基取整，上左下右”

79 附录： Decimal to Binary Conversions
例1:( )10=( )2 整数----“除基取余，上右下左” 小数----“乘基取整，上左下右”

80 附录： Decimal to Binary Conversions
例2:(835.63)10=( …)8 整数----“除基取余，上右下左” 小数----“乘基取整，上左下右” 有可能乘积的小数部分总得不到0 ，此时得到一个近似值。

81 附录： Conversions of numbers
(3) 二/八/十六进制数的相互转换 ① 八进制数转换成二进制数 (13.724) 8=( ) 2=( ) 2 ② 十六进制数转换成二进制数 (2B.5E)16 = ( ) 2 = ( ) 2   ③ 二进制数转换成八进制数   ( ) 2 = ( ) 2 = ( 0.52) 8   ④ 二进制数转换成十六进制数 ( ) 2 = ( ) 2 = ( 19.C ) 16