信息表示

你必须使用的三种数制(number systems):

• 十进制(denary,decimal,基数 10)——用数字 0–9。位值是十的幂。
• 二进制(binary,基数 2)——用 0 和 1。位值是二的幂。每个字节(byte)是 8 个位(bits)。
• 十六进制(hexadecimal,基数 16)——用 0–9 然后 A–F 表示 10–15。每个十六进制数位(digit)恰好代表 4 个位。

转换

十进制 → 二进制:不断除以 2 并记录余数,从下往上读。或者减去装得下的最大位值(place value,2 的幂)。

例子:$558_{10}$:$558 = 512 + 32 + 8 + 4 + 2 = 2^{9} + 2^{5} + 2^{3} + 2^{2} + 2^{1}$。用 12 位:0010 0010 1110。

二进制 → 十六进制:从右边起把位分成半字节(nibbles,4 位)并转换每一个。0010 0010 1110 → 2 2 E → 22E。

十六进制 → 二进制:把每个十六进制数位换成它的 4 位模式。十六进制 → 十进制:把每个数位乘以它的位值。22E $= 2 \times 256 + 2 \times 16 + 14 = 558$。

例题。 把十进制 200 转换成 8 位二进制,然后转换成十六进制。

$200 = 128 + 64 + 8$,所以二进制是 11001000。分成半字节,1100 1000 $= 12$ 和 $8$,即 $\text{C}$ 和 $8$,所以十六进制是 C8。

需要多少位?

考试题会规定寄存器宽度(register width)(8、12 或 16 位)。要用前导零补齐到这个宽度:$558$ 的 12 位形式是 0010 0010 1110,绝不能写成 10 0010 1110。

要找出能存储某个值的最少位数,问自己需要哪些位值:

• 从 $0$ 到 $2^{n} - 1$ 的无符号整数需要 $n$ 位:$200$ 需要 8 位(上限是 $255$),$1000$ 需要 10 位(上限是 $1023$),$16$ 需要 5 位(4 位到 $15$ 为止)。
• 从 $-2^{n-1}$ 到 $2^{n-1} - 1$ 的有符号补码整数需要 $n$ 位:$-200$ 需要 9 位,因为 8 位到 $-128$ 为止。
• 一个十六进制数位需要 4 位,一个 BCD 数位需要 4 位,一个 ASCII 字符需要 7 位(扩展 ASCII 为 8 位)。

二进制与十进制词头

两个词头族看起来相似但不同——十进制(10 的幂)和二进制(2 的幂):

所以一个 tebibyte(TiB)略多于一个 terabyte(TB)。一个"1 TB"的驱动器容纳 $10^{12}$ 字节,但一个以 TiB 报告的操作系统显示一个较小的数字。

二进制加法

从右边起逐列相加,像十进制那样进位:

当结果需要的位比寄存器(register)能容纳的更多时,发生溢出(overflow)——最左列的进位输出就是溢出位。

例题。 把 8 位无符号整数 $10110101$ 和 $01101100$ 相加,并对结果作出评论。

$10110101 + 01101100 = 1\,00100001$。答案需要 9 位,所以放不进一个 8 位寄存器:发生了溢出。一个完整的答案要说出错误的名称并说明原因,用题目给出的字长:"溢出:真实结果($289$)大于 8 位寄存器能容纳的最大值($255$),所以最高有效位的进位输出丢失,存储的结果($00100001 = 33$)是错的。"

二进制减法

通常的方法是补码(two's complement)加法:要做 $A - B$,构成 $B$ 的补码(每一位取反并加 1),然后相加,并丢弃任何最终的进位输出。

从 $01100100$ 中减去 $00011110$(无符号 8 位):

• $00011110$ 的补码:取反 → $11100001$,加 1 → $11100010$。
• 加到 $01100100$:结果 $1\,01000110$(9 位)——丢弃前导的 1 → $01000110 = 70_{10}$。检验:$100 - 30 = 70$。✓

补码有符号整数

在一个 $n$ 位补码数中:

• 最高有效位(most significant bit,MSB)是符号位(sign bit):0 = 正,1 = 负。
• 要读一个负数:每一位取反,加 1,然后取负。

所以 $11100010$ 是负的;取反 → $00011101$,加 1 → $00011110 = 30$,所以它是 $-30$。这是一个有符号整数(signed integer,不同于无符号(unsigned)的)。$n$ 位的范围是 $-2^{n-1}$ 到 $+2^{n-1} - 1$;对 8 位,$-128$($10000000$)到 $+127$($01111111$)。

例题。 8 位补码数 $10110100$ 表示什么十进制值?

MSB 是 1,所以它是负的。取反 → $01001011$,加 1 → $01001100 = 76$,所以值是 $-76$。用位值检验:$-128 + 32 + 16 + 4 = -76$。

例题。 把 $-108$ 写成 12 位补码整数。

从 12 位的 $+108$ 开始:$108 = 64 + 32 + 8 + 4$,所以是 0000 0110 1100。每一位取反:1111 1001 0011。加 1:1111 1001 0100。用位值检验,其中最高位的值是 $-2^{11} = -2048$:$-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$。✓

对于 12 位,范围是 $-2048$(1000 0000 0000)到 $+2047$(0111 1111 1111)。要求写出最小值和最大值的题目要的就是这两个模式,所以记住规律:最小的负数是一个 1 后面全是 0;最大的正数是一个 0 后面全是 1。

算术移位(arithmetic shift)把每一位向左或向右移动,但保持符号:向右移一位使数值减半,并把符号位复制到左边空出的位置,所以负数仍是负数(1111 1001 0100 向右移三位得到 1111 1111 0010,即 $-14$:$-108 / 8 = -13.5$,右移时向下取整)。向左移一位使数值加倍。移位属于主题 4 的汇编指令集,但这道题是和这里的数制内容一起考的。

有符号运算中的溢出发生在真实结果落在这个范围之外时——当符号位错误地翻转时可以发现(两个正数给出一个负数,或两个负数给出一个正数)。

反码

在补码之前,一个较老的方案叫反码(one's complement),它表示一个负数只是把正数的每一位取反——没有"加 1"步骤。

• $+30 = 00011110$,所以在反码中 $-30 = 11100001$(就是取反)。
• 缺点:它有两个零——$00000000$($+0$)和 $11111111$($-0$)——这浪费了一个位模式,并使运算别扭。

补码(取反并加 1)去除了负零:它有单一的零,并让加法和减法使用同一个电路。这就是为什么现代计算机以补码而非反码存储有符号整数。

在 BCD(二进码十进数)中,每个十进制数位被写成它自己的 4 位模式。数字 $93$ 在 BCD 中是 1001 0011——不是二进制 93($01011101$)。每个半字节只用 0–9;模式 $1010$–$1111$ 是无效的。

BCD 读法:0010 0111 0101 → 2, 7, 5 → 275。

用途:计算器、数字钟,以及显示十进制数位的设备——每个数位驱动一个七段显示器(7-segment display)。货币代码常用 BCD 以避免把像 0.1 这样的分数转换成二进制时的舍入误差。

"说明理由"类的答案必须把用途和 BCD 的某个性质联系起来:每个十进制数位都有自己的 4 位,所以一个数位可以直接送到它的显示器,或逐位相加,而不必转换整个数;而且像 $0.10$ 这样的十进制小数能被精确存储,二进制小数做不到这一点。

十六进制是写二进制的一种紧凑方式(1 个十六进制数位 = 4 位):

• 底层编程中的内存地址(memory addresses)——0x7FFE。
• HTML/CSS 中的颜色值——#FF8800。
• MAC 地址——AC:DE:48:00:11:22。

十六进制不改变存储的数据——它只是使二进制对人类更容易。

计算机把文本存储为数字;每个字符有一个由字符集(character set)设定的数字码点(code point)。

ASCII

• ASCII 用 7 位——128 个码点。基本拉丁字母、数字、标点和控制码。
• 扩展 ASCII 用 8 位——256 个码点;低 128 个与 ASCII 相符,高 128 个因地区而异。

Unicode

• Unicode 是一个通用字符集,涵盖几乎每一种文字,加上符号和表情符号。
• 常见的编码(encodings):UTF-8(1–4 字节,兼容 ASCII)、UTF-16(2 或 4 字节)、UTF-32(固定 4 字节)。

为什么 Unicode 胜过 ASCII

• 它表示多得多的字符(每一种文字、表情符号);ASCII 只涵盖基本英语。
• 文件可移植、没有代码页混乱,并允许一个文档中的多语言文本。
• 权衡:对于纯英语文本,Unicode 文件通常更大。

当题目要求区别时,要成对地、带着数字来给出:ASCII 用 7 位(扩展 ASCII 8 位),所以有 128(256)个字符;Unicode 最多用 32 位(UTF-8 用 1 到 4 个字节),所以有超过一百万个码点。ASCII 只涵盖基本英语;Unicode 涵盖每一种文字,而且它的前 128 个码点就是 ASCII 的那些。在 UTF-8 中一个英文字母仍只占 1 个字节,所以一个 40 个字母的英文文件名在 ASCII 和 UTF-8 中都是 40 字节,而一个汉字占 3 个字节。

一个位图(bitmap)图像(也叫位映射图像)在一个网格中存储每个像素(pixel)的颜色。在文件的开头,一个文件头(file header)记录图像的元数据——它的宽度、高度和颜色深度——这样软件就知道如何读取随后的像素数据。

• 图像分辨率(image resolution):位图自身的大小,以像素计的宽 × 高(例如 1920 × 1080)。
• 屏幕分辨率(screen resolution):显示器能显示的宽 × 高。如果一个图像的分辨率比屏幕大,它被缩小以适应;一个低分辨率图像被拉伸到一个较高分辨率的屏幕上时看起来有块状感。
• 颜色深度(colour depth,位深度(bit depth)):每像素的位数。1 位 → 黑/白;8 位 → 256 种颜色;24 位 → 1670 万("真彩色")。

文件大小

除以 8 得字节,除以 1024 得 KiB,等等。例子:一个 $3000 \times 2000$、24 bpp 的图像是 $3000 \times 2000 \times 24 = 1.44 \times 10^{8}$ 位 $\approx 17.2\ \text{MiB}$。

写明你用的单位。评分标准接受 $1\ \text{MB} = 10^{6}$ 字节(SI 词头)或 $1\ \text{MiB} = 1024 \times 1024$ 字节(二进制词头),只要你的过程表明用的是哪一个;同一幅图像是 $18.0\ \text{MB}$ 或 $17.2\ \text{MiB}$。如果题目给出了文件头的大小,要把它加上。

视频是一系列位图图像,每一幅是一帧(frame)。压缩前它的大小是一帧的大小 $\times$ 帧率(frame rate,每秒帧数)$\times$ 以秒计的时长:每秒 30 帧、每帧 $1920 \times 1080$ 像素、24 位,就是每秒 $30 \times 1920 \times 1080 \times 24 \approx 1.5 \times 10^{9}$ 位,约 $187\ \text{MB}$。这就是为什么视频总是要压缩。

改变设置

• 较低分辨率 → 较小的文件,较少的细节(放大时看起来有块状感)。
• 较低颜色深度 → 较小的文件,但平滑的色调显示出条带。
• 两者中较高的 → 较大的文件,更好的质量。

一个矢量图形(vector graphic)把画图像的指令存储为一个绘图列表(drawing list)——一个有序的绘图对象(drawing objects,几何图元(primitives):线、曲线、多边形、圆)列表。每个绘图对象有属性(properties),如颜色、填充、线宽和位置(坐标)。要显示它,程序以所需的任何分辨率渲染(renders)这个绘图列表。

位图与矢量

矢量的优点:它缩放而不损失质量——一个矢量徽标在任何大小都保持清晰,而一个位图放大时会模糊。矢量的缺点:它不能描述任意的像素细节(照片)。

"说明理由"类的答案要把选择和任务联系起来。"这个标志既要印在名片上又要印在广告牌上,所以应该用矢量图形:它以绘图对象的形式存储,能在任何尺寸下清晰地重新渲染;而位图放大时会显出像素。"对于照片,论证方向相反:没有可以描述的形状,所以必须存储每个像素的颜色。

一个连续的模拟数据(analogue data,声音)波通过采样(sampling)被转换成数字数据(digital data):

• 采样率(sampling rate)——每秒的采样数(Hz)。CD 质量是 $44.1\ \text{kHz}$。
• 采样分辨率(sampling resolution,位深度)——每个采样的振幅(amplitude)的位数。CD 质量是 16 位。

文件大小

一段 10 秒的立体声 CD 片段:$44100 \times 16 \times 10 \times 2 = 14\,112\,000$ 位 $\approx 1.68\ \text{MiB}$。

改变设置

• 较高采样率 → 捕捉较高的音调,较大的文件。
• 较高采样分辨率 → 更精细的振幅步长,较少的量化(quantisation)噪声,较大的文件。
• 两者中较低的 → 较小的文件,明显的质量损失。

(采样率必须至少是你想保留的最高频率的两倍。)

压缩(compression)减小文件大小,节省存储和传输的带宽(bandwidth)。两种:

• 无损(lossless)——原始数据被精确恢复(文本、程序、ZIP/PNG)。
• 有损(lossy)——为了小得多的文件丢弃一些细节(JPEG、MP3、视频)。

何时用哪种

• 无损用于文档、源代码、医学图像——任何需要精确数据的东西。
• 有损用于流媒体。实时视频流用有损压缩,因为它必须在有限的带宽上实时发送大量数据;无损不能把它缩得足够小。原始高清视频是每分钟几个吉字节,所以没有压缩画面会不断卡住。

"说明理由"类的答案先说方法,再给出来自情境的原因:"无损,因为电子表格必须被精确地恢复;一个数值变了,账目就错了。"或者:"有损,因为这些照片是在手机屏幕上看的,丢掉的细节看不出来,而更小的文件上传更快、占的存储更少。"

无损方法

• 行程编码(run-length encoding,RLE):存储"接下来的 $n$ 个值是 $x$",而不是重复 $x$。对平坦区域很好;对噪声数据没用。
• 字典编码(dictionary methods,ZIP、PNG):用一个短引用替换重复的字节序列。对文本和代码很好。
• 霍夫曼编码(Huffman coding):给常见符号短码、给罕见符号长码,使平均码长接近数据的熵(entropy)。

各类文件如何压缩:

• 文本文件:字典编码和霍夫曼编码把重复的单词和常见字符变成短码。文本必须保持无损,因为改变一个字符就改变了意思。
• 位图图像:对相同像素的连续段用 RLE(图标、图表、黑白扫描件);对照片用有损的 JPEG,或降低颜色深度或分辨率。
• 矢量图形:绘图列表本来就小;删去不需要的绘图对象,坐标存更少的小数位,或对文件应用 ZIP 之类的无损方法。
• 声音文件:有损的 MP3 或 AAC 去掉耳朵听不到的部分;降低采样率或采样分辨率也是有损的;无损格式保留每一个样本,文件缩小得少得多。

有损方法

• 图像(JPEG):丢弃眼睛几乎看不见的精细细节和颜色差异。
• 声音(MP3、AAC):丢弃我们听得不太清楚的音调,以及被较响声音掩盖的安静声音。
• 视频结合空间(spatial)压缩(在每一帧内,像 JPEG)与时间(temporal)压缩(大多数帧只存储与前一帧的差异)。

定义题按固定的表述给分。把这些记准确,并且只写一个答案。

• 显示进制转换的过程:十进制 → 二进制用位值,二进制 → 十六进制分半字节(4 位一组)。
• 对于补码,MSB 是负的;要取负,取反并加 1;当符号位错误地翻转时留意溢出。
• 区分位图(像素;文件大小 $=$ 宽 $\times$ 高 $\times$ 颜色深度)和矢量(绘图命令;缩放而不损失)。
• 声音文件大小取决于采样率 $\times$ 位深度 $\times$ 时间——每样越多意味着越好的质量但越大的文件。
• 比较无损与有损压缩并给出各自的一个用途。

常见错误

• 用"答案大于 255"或"它有 9 位"来解释溢出。先说出题目给的字长,再说结果无法用它表示。
• 把最高位设为 1、其余不动来构造负数(原码)。补码的意思是把正数的每一位取反,再加 1。
• 忘记把转换后的数补齐到题目要求的寄存器宽度。
• 在文件大小计算中混淆位和字节。先按位计算,只除以 8 一次,并说明用的是 1000 还是 1024。
• 用日常语言回答"描述"题("图片变差了")。要用大纲术语:颜色更少、出现条带、图像分辨率更低、像素更大。