| Candidates should be able to: | Notes and guidance |
|---|---|
| Show understanding of binary magnitudes and the difference between binary prefixes and decimal prefixes | Understand the difference between and use: • kibi and kilo • mebi and mega • gibi and giga • tebi and tera |
| Show understanding of different number systems | Use the binary, denary, hexadecimal number bases and Binary Coded Decimal (BCD) and one’s complement and two’s complement representation for binary numbers |
| Convert an integer value from one number base/ representation to another | |
| Perform binary addition and subtraction | Using positive and negative binary integers |
| Show understanding of how overflow can occur | |
| Describe practical applications where Binary Coded Decimal (BCD) and Hexadecimal are used | |
| Show understanding of and be able to represent character data in its internal binary form, depending on the character set used | Students are expected to be familiar with ASCII (American Standard Code for Information Interchange), extended ASCII and Unicode. Students will not be expected to memorise any particular character codes |
信息表示
A-Level 计算机科学 · 第 1 主题
1.1
数据表示
大纲
来源:剑桥国际大纲
你必须使用的三种数制(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。
二进制与十进制词头
两个词头族看起来相似但不同——十进制(10 的幂)和二进制(2 的幂):
| 十进制(SI) | 二进制(内存) |
|---|---|
| kilo $= 10^{3}$ | kibi (Ki) $= 2^{10} = 1024$ |
| mega $= 10^{6}$ | mebi (Mi) $= 2^{20}$ |
| giga $= 10^{9}$ | gibi (Gi) $= 2^{30}$ |
| tera $= 10^{12}$ | tebi (Ti) $= 2^{40}$ |
所以一个 tebibyte(TiB)略多于一个 terabyte(TB)。一个"1 TB"的驱动器容纳 $10^{12}$ 字节,但一个以 TiB 报告的操作系统显示一个较小的数字。
探索
Binary, denary and hex
Type a number and see it in binary, denary and hexadecimal at once — and how the place values add up.
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| number system | 数制 | shù zhì |
| denary | 十进制 | shí jìn zhì |
| binary | 二进制 | èr jìn zhì |
| byte | 字节 | zì jié |
| bit | 位 | wèi |
| hexadecimal | 十六进制 | shí liù jìn zhì |
| digit | 数位 | shù wèi |
| place value | 位值 | wèi zhí |
| nibble | 半字节 | bàn zì jié |
1.1
二进制运算
二进制加法
从右边起逐列相加,像十进制那样进位:
| 位 A | 位 B | 进位输入 | 和位 | 进位输出 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
当结果需要的位比寄存器(register)能容纳的更多时,发生溢出(overflow)——最左列的进位输出就是溢出位。
二进制减法
通常的方法是补码(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$。
有符号运算中的溢出发生在真实结果落在这个范围之外时——当符号位错误地翻转时可以发现(两个正数给出一个负数,或两个负数给出一个正数)。
反码
在补码之前,一个较老的方案叫反码(one's complement),它表示一个负数只是把正数的每一位取反——没有"加 1"步骤。
- $+30 = 00011110$,所以在反码中 $-30 = 11100001$(就是取反)。
- 缺点:它有两个零——$00000000$($+0$)和 $11111111$($-0$)——这浪费了一个位模式,并使运算别扭。
补码(取反并加 1)去除了负零:它有单一的零,并让加法和减法使用同一个电路。这就是为什么现代计算机以补码而非反码存储有符号整数。
探索
Binary & signed integers
byte = Σ place values
See how an 8-bit pattern maps to a number (and how it would overflow past 255).
探索
Two's complement signed bits
The leftmost bit carries a negative place value. Flip any bit — or hit Negate (invert every bit, then add 1) — and watch the signed value change.
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| overflow | 溢出 | yì chū |
| register | 寄存器 | jì cún qì |
| two's complement | 补码 | bǔ mǎ |
| most significant bit | 最高有效位 | zuì gāo yǒu xiào wèi |
| sign bit | 符号位 | fú hào wèi |
| signed integer | 有符号整数 | yǒu fú hào zhěng shù |
| unsigned | 无符号 | wú fú hào |
| one's complement | 反码 | fǎn mǎ |
1.1
二进制编码的十进制(BCD)
在 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 | 二进码十进数 | èr jìn mǎ shí jìn shù |
| 7-segment display | 七段显示器 | qī duàn xiǎn shì qì |
1.1
十六进制 —— 实际用途
十六进制是写二进制的一种紧凑方式(1 个十六进制数位 = 4 位):
- 底层编程中的内存地址(memory addresses)——
0x7FFE。 - HTML/CSS 中的颜色值——
#FF8800。 - MAC 地址——
AC:DE:48:00:11:22。
十六进制不改变存储的数据——它只是使二进制对人类更容易。
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| memory address | 内存地址 | nèi cún dì zhǐ |
1.1
字符编码
计算机把文本存储为数字;每个字符有一个由字符集(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 文件通常更大。
探索
A character is stored as a number
Each character has a code number — 'A' is 65. Flip the bits to see that code in binary and hex, exactly how the computer holds it.
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| code point | 码点 | mǎ diǎn |
| character set | 字符集 | zì fú jí |
| encoding | 编码 | biān mǎ |
1.2
多媒体
大纲
| Candidates should be able to: | Notes and guidance |
|---|---|
| Show understanding of how data for a bitmapped image are encoded | Use and understand the terms: pixel, file header, image resolution, screen resolution, colour depth / bit depth |
| Perform calculations to estimate the file size for a bitmap image | |
| Show understanding of the effects of changing elements of a bitmap image on the image quality and file size | Use the terms: image resolution, colour depth / bit depth |
| Show understanding of how data for a vector graphic are encoded | Use the terms: drawing object, property, drawing list |
| Justify the use of a bitmap image or a vector graphic for a given task | |
| Show understanding of how sound is represented and encoded | Use the terms: sampling, sampling rate, sampling resolution, analogue and digital data |
| Show understanding of the impact of changing the sampling rate and resolution | Including the impact on file size and accuracy |
来源:剑桥国际大纲
一个位图(bitmap)图像(也叫位映射图像)在一个网格中存储每个像素(pixel)的颜色。在文件的开头,一个文件头(file header)记录图像的元数据——它的宽度、高度和颜色深度——这样软件就知道如何读取随后的像素数据。
- 图像分辨率(image resolution):位图自身的大小,以像素计的宽 × 高(例如 1920 × 1080)。
- 屏幕分辨率(screen resolution):显示器能显示的宽 × 高。如果一个图像的分辨率比屏幕大,它被缩小以适应;一个低分辨率图像被拉伸到一个较高分辨率的屏幕上时看起来有块状感。
- 颜色深度(colour depth,位深度(bit depth)):每像素的位数。1 位 → 黑/白;8 位 → 256 种颜色;24 位 → 1670 万("真彩色")。
文件大小
$$\text{size in bits} = \text{width} \times \text{height} \times \text{bit depth}.$$
除以 8 得字节,除以 1024 得 KiB,等等。例子:一个 $3000 \times 2000$、24 bpp 的图像是 $3000 \times 2000 \times 24 = 1.44 \times 10^{8}$ 位 $\approx 17.2\ \text{MiB}$。
改变设置
- 较低分辨率 → 较小的文件,较少的细节(放大时看起来有块状感)。
- 较低颜色深度 → 较小的文件,但平滑的色调显示出条带。
- 两者中较高的 → 较大的文件,更好的质量。
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| bitmap | 位图 | wèi tú |
| pixel | 像素 | xiàng sù |
| file header | 文件头 | wén jiàn tóu |
| image resolution | 图像分辨率 | tú xiàng fēn biàn lǜ |
| screen resolution | 屏幕分辨率 | píng mù fēn biàn lǜ |
| colour depth | 颜色深度 | yán sè shēn dù |
| bit depth | 位深度 | wèi shēn dù |
1.2
矢量图形
一个矢量图形(vector graphic)把画图像的指令存储为一个绘图列表(drawing list)——一个有序的绘图对象(drawing objects,几何图元(primitives):线、曲线、多边形、圆)列表。每个绘图对象有属性(properties),如颜色、填充、线宽和位置(坐标)。要显示它,程序以所需的任何分辨率渲染(renders)这个绘图列表。
位图与矢量
| 任务 | 较好的选择 | 为什么 |
|---|---|---|
| 照片 | 位图 | 复杂的像素级细节不能被描述为形状。 |
| 徽标、图标、标志 | 矢量 | 边缘清晰;缩放到任何大小都不模糊。 |
| 工程图 | 矢量 | 精确的几何和缩放。 |
| 绘画、纹理 | 位图 | 每个区域平滑的色调细节。 |
矢量的优点:它缩放而不损失质量——一个矢量徽标在任何大小都保持清晰,而一个位图放大时会模糊。矢量的缺点:它不能描述任意的像素细节(照片)。
探索
Computing concept lab
Classify concrete examples by the computing idea they demonstrate.
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| vector graphic | 矢量图形 | shǐ liàng tú xíng |
| drawing list | 绘图列表 | huì tú liè biǎo |
| drawing object | 绘图对象 | huì tú duì xiàng |
| primitive | 图元 | tú yuán |
| property | 属性 | shǔ xìng |
| render | 渲染 | xuàn rǎn |
1.2
声音
一个连续的模拟数据(analogue data,声音)波通过采样(sampling)被转换成数字数据(digital data):
- 采样率(sampling rate)——每秒的采样数(Hz)。CD 质量是 $44.1\ \text{kHz}$。
- 采样分辨率(sampling resolution,位深度)——每个采样的振幅(amplitude)的位数。CD 质量是 16 位。
文件大小
$$\text{size in bits} = \text{sampling rate} \times \text{resolution} \times \text{duration} \times \text{channels}.$$
一段 10 秒的立体声 CD 片段:$44100 \times 16 \times 10 \times 2 = 14\,112\,000$ 位 $\approx 1.68\ \text{MiB}$。
改变设置
- 较高采样率 → 捕捉较高的音调,较大的文件。
- 较高采样分辨率 → 更精细的振幅步长,较少的量化(quantisation)噪声,较大的文件。
- 两者中较低的 → 较小的文件,明显的质量损失。
(采样率必须至少是你想保留的最高频率的两倍。)
探索
Sound sampling
y = a sin(bt + c)
Sampling measures a sound wave at regular intervals — a higher rate copies it more truly.
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| analogue data | 模拟数据 | mó nǐ shù jù |
| digital data | 数字数据 | shù zì shù jù |
| sampling | 采样 | cǎi yàng |
| sampling rate | 采样率 | cǎi yàng lǜ |
| sampling resolution | 采样分辨率 | cǎi yàng fēn biàn lǜ |
| amplitude | 振幅 | zhèn fú |
| quantisation | 量化 | liàng huà |
1.3
压缩
大纲
| Candidates should be able to: | Notes and guidance |
|---|---|
| Show understanding of the need for and examples of the use of compression | |
| Show understanding of lossy and lossless compression and justify the use of a method in a given situation | |
| Show understanding of how a text file, bitmap image, vector graphic and sound file can be compressed | Including the use of run-length encoding (RLE) |
来源:剑桥国际大纲
压缩(compression)减小文件大小,节省存储和传输的带宽(bandwidth)。两种:
- 无损(lossless)——原始数据被精确恢复(文本、程序、ZIP/PNG)。
- 有损(lossy)——为了小得多的文件丢弃一些细节(JPEG、MP3、视频)。
何时用哪种
- 无损用于文档、源代码、医学图像——任何需要精确数据的东西。
- 有损用于流媒体。实时视频流用有损压缩,因为它必须在有限的带宽上实时发送大量数据;无损不能把它缩得足够小。原始高清视频是每分钟几个吉字节,所以没有压缩画面会不断卡住。
无损方法
- 行程编码(run-length encoding,RLE):存储"接下来的 $n$ 个值是 $x$",而不是重复 $x$。对平坦区域很好;对噪声数据没用。
- 字典编码(dictionary methods,ZIP、PNG):用一个短引用替换重复的字节序列。对文本和代码很好。
- 霍夫曼编码(Huffman coding):给常见符号短码、给罕见符号长码,使平均码长接近数据的熵(entropy)。
有损方法
- 图像(JPEG):丢弃眼睛几乎看不见的精细细节和颜色差异。
- 声音(MP3、AAC):丢弃我们听得不太清楚的音调,以及被较响声音掩盖的安静声音。
- 视频结合空间(spatial)压缩(在每一帧内,像 JPEG)与时间(temporal)压缩(大多数帧只存储与前一帧的差异)。
探索
Run-length encoding
Watch a run of repeated symbols get squashed into a count — simple lossless compression.
词汇表
训练
| 英文 | 中文 | 拼音 |
|---|---|---|
| compression | 压缩 | yā suō |
| bandwidth | 带宽 | dài kuān |
| lossless | 无损 | wú sǔn |
| lossy | 有损 | yǒu sǔn |
| run-length encoding | 行程编码 | xíng chéng biān mǎ |
| dictionary methods | 字典编码 | zì diǎn biān mǎ |
| Huffman coding | 霍夫曼编码 | huò fū màn biān mǎ |
| entropy | 熵 | shāng |
| spatial | 空间 | kōng jiān |
| temporal | 时间 | shí jiān |
1.3
考试技巧
- 显示进制转换的过程:十进制 → 二进制用位值,二进制 → 十六进制分半字节(4 位一组)。
- 对于补码,MSB 是负的;要取负,取反并加 1;当符号位错误地翻转时留意溢出。
- 区分位图(像素;文件大小 $=$ 宽 $\times$ 高 $\times$ 颜色深度)和矢量(绘图命令;缩放而不损失)。
- 声音文件大小取决于采样率 $\times$ 位深度 $\times$ 时间——每样越多意味着越好的质量但越大的文件。
- 比较无损与有损压缩并给出各自的一个用途。
本主题的互动课程
逐步学习,并即时检测练习。