跳转至

L01 Worksheet

1. 信息和熵

  • A. 给你一个未知的 3 位二进制数。然后你会被告知二进制表示恰好包含两个 1。您获得了多少信息？

    \[ p = 3/8 \\ I = log_2(8/3) = log_2(8) - log_2(3) \approx 1.415 \]

  • B. 额外信息，数字是奇数，获得了多少额外信息？

    \[ I = log_2(3/2) = log_2(3) - log_2(2) \approx 0.585 \]

  • C. X 代表一个不公平的硬币，其中 p(head) = 0.6。请计算 H(X)

    \[ p(HEADS) = 0.6 \\ p(TAILS) = 1 - p(HEADS) \\ \]
    \[ H(X) = p(HEADS)*I(HEADS) + p(TAILS)*I(TAILS) \]

  • D. 随机选择一个十进制数字，并告诉您其值 mod 3 为 0。您了解了多少关于该数字的信息？

    \[ I = \log_2(10) - \log_2(4) \]

  • E. X 是一个未知的 8 位二进制数。现在告诉你 X 和 10101100 的汉明距离为 1。你获取了多少 bit 位的信息。

    \[ I = log_2(2^7/8) = 7 - 3 = 4 \]

  • F. 对于 4 个概率不均匀的字母及编码，如果告诉你 “不是d” 这个消息值多少 bit？

    符号 概率 编码
    a 0.5 000000
    b 0.125 11100
    c 0.25 11011
    d 0.125 10111
    \[ p(!d) = 1 - 0.125 = 0.875 \\ I = log_2(\frac{1}{p}) = log_2(\frac{1}{0.875}) \\ = log_2(\frac{1}{\frac{7}{8}})= log_2(\frac{8}{7}) \\ = 3 - log_2(7) \approx 0.193 bits \]

  • G. 如果你长期观察这个信号源，平均每一个符号能带给你多少比特的“惊喜”？

    • a: $ p = 0.5, I = log_2(1/0.5) = 1 $
    • b: $ p = 0.125, I = log_2(1/0.125) = 3 $
    • c: $ p = 0.25, I = log_2(1/0.25) = 2 $
    • d: $ p = 0.125, I = log_2(1/0.125) = 3 $

    所以 $ H = \sum p \cdot I = 1.75 $

  • H. 给你一个 5 位二进制数，告诉你第一个和最后一个位数相等，你得到了多少信息？

    \[ I = log_2(1/0.5) = 1 \]

  • I. 我随机从字母表中选择一个字母并且告诉你我的选择不是"X", "Y" 也不是 “Z”。你获得了多少信息

    \[ p = 23/26 \\ I = log_2(1/p) \approx 0.178 \]

  • J. 对于一个随机 4 位补码数字，告诉你是正数，信息量多少。

    \[ p = 7/16 \\ I = log_2(16/7) \]

补码

  • A. 6 位十进制 -21 的补码表示？

    $$ 21 = 16 + 4 + 1 = 2^4 + 2^2 + 1 $$ 二进止表示为 010101 取反加1为 101011

  • B. 8 位补码 -51 的十六进制表示

    8 位补码的表示范围是 -2^7 ~ 2^7-1 即 -128 ~ 127，没有溢出 $$ 51 = 32 + 16 + 2 + 1 = 2^5 + 2^4 + 2^1 + 2^0 $$ 补码表示为 00110011 取反加 1 为 11001101 十六进制为 CD

  • C. 8 位补码的十六进制是 0xD6，十进制是多少

    0xD6 的二进制表示为 11010110，说明是一个负数，采用负权重法 $$ -128+64+16+4+2 = -42 $$

  • D. 自1988年开始进行官方投球统计以来，单场比赛的最高投球数为172个。假设这 仍然是投球数的上限，那么我们需要多少位来将每场比赛的投球数记录为补码二进制数

    $$ 2^7 < 172 < 2^8 $$ 所以至少需要 9 位，表示范围为 \(-2^8 ... 2^8-1\)

  • E. 两个补码数 0xB3 + 0x47 的和的值可以用 8 位补码表示法来表示吗？ 如果是这 样，其十六进制的总和是多少？ 如果没有，请写“NO”

    按照十六进制加法 0xB3 + 0x47 = 0xFA，没有溢出，-6

  • F.两个2的补码0xB3 + 0xB1的和的值可以用8位补码表示法来表示吗？ 如果是这 样，十六进制的总和是多少？如果没有，请写“NO”。

    0xB3 + 0xB1 = 0x164 溢出，NO

  • G. 请使用 8 位二进制补码算术计算表达式 0xBB - 8 的值，并以十进制形式给出结果（基数为 10）

    0xBB - 8 = 0xB3 = 11+3 = 14

  • H. 可以表示为 8 位二进制补码整数的最小（最大负数）整数是多少？ 以十进制整数形式给出你的答案。

    \[ -2^8 = -256 \]

  • I. 以下运算在 8 位加法器上执行。 给出每个生成的 8 位总和（以十六进制表示）

    0xF0 + 0x34 = 0x34
0xF0 + 0x80 = 0x80

  • J. 用 5 位二进制补码表示，单个 5 位数量可以表示的整数范围是多少？

    \[ -2^4 ... 2^4-1 \]

  • K. 考虑以下减法问题，其中操作数是 5 位二进制补码数。 计算结果并以十进制（以 10 为基数）形式给出答案。10101 − 00011

    减一个数可以看作加上一个数的负数，取负数表示为
10101 - 00011 = 10101 + 11101 = 110010，

结果为 -2^4 + 2 = -14

什么情况下会溢出？ 只有两个数同号，且结果为不同号时才发生溢出
在电路里 \(V = C_{in} C_{out}\)
\(C_{in}\) 表示最高位的进位
\(C_{out}\) 表示最高位向外产生的进位
如果发生溢出，两者必然一个是 1，另一个是 0

3. 可变长编码

  • A. 变量 X 可以表示为 A，B，C或D，以下是他们的概率，如果使用霍夫曼编码对该变量进行编码，则每个符号的编码中有多少位？
    A 0.5
    B 0.3
    C 0.1
    D 0.1

    使用 huffman 编码 ||| |--|--| |A| 0| |B |11| |C| 100| |D |101|

    \(H = 1*0.5 + 2*.03 + 3*0.2 = 0.5+0.6+0.6 = 1.7\)

    \[ 0.5*log_2(1/0.5) + 0.3*log_2(1/0.3) + 0.1*log_2(1/0.1) + 0.1*log_2(1/0.1) \\ \approx 1.685 \]

    根据概率，判断以下属于概率可能对应哪个树，选择霍夫曼编码树或通过对这些概率分布运行霍夫曼算法而产生的树 图片

  • B. p(A) = 0.3, p(B) = 0.3, p(C) = 0.2, p(D) = 0.1, p(E) = 0.1

    Tree(s): 1

  • C. p(A) = 0.6, p(B) = 0.1, p(C) = 0.1, p(D) = 0.1, p(E) = 0.1

    Tree(s): 3

  • D. p(A) = 0.5, p(B) = 0.15, p(C) = 0.15, p(D) = 0.1, p(E) = 0.1

    Tree(s): 3

  • E. p(A) = 0.5, p(B) = 0.2, p(C) = 0.15, p(D) = 0.05, p(E) = 0.1.

    Tree(s): 2

棒球热爱统计！投手可以投出多种不同类型的投球 - 下表显示了 2014 年每种投球类型的概率

Type of pitch Probability
Fastball 0.34
Change-up 0.14
Curveball 0.08
Slider 0.28
Other 0.16

  • F. 当得知该特定投球不是快球时，您收到了多少信息？如果您愿意，您可以将答案表达为公式

    \[ p = 1-0.34 \\ I = log_2(1/1-0.34) \]

  • G. 为了节省存储成本，美国职业棒球大联盟希望使用最佳的可变长度代码来一次一个记录每个投球的类 型（即记录上表中显示的 5 种类型之一）。使用霍夫曼算法导出这样的代码并在下面列出生成的二进制编码。
    A 00
    B 111
    C 110
    D 01
    E 10

    实际平均编码长度 20.78 + 30.22 = 2.22
    理想编码长度 \(I = \sum p*log_2(1/p) \approx 2.15\)

  • H. 下表显示了 2012-13 学年各 EECS 专业的招生情况。为了节省数据库中的一些空间，该系希望使用可变 长度的霍夫曼代码来对学生选择的专业进行编码。对于四个专业中的每一个，请给出该部门应使用的编码

    图片

    编码 - A: 0 - B: 10 - C: 110 - D: 111

    平均编码长度 10.44 + 20.41 + 3*0.15 = 1.71

  • I. 希望传递下面四个符号及其概率和编码组成的消息，使用 Huffman 算法构建可变长编码，结果可能是？

    Symbol p(symbol) encoding
    a 0.5 00000
    b 0.125 11100
    c 0.25 11011
    d 0.125 10111

    (1) a: 00, b:01, c: 10, d: 10 (2) a: 00, b: 01, c:100, d: 101 (3) a: 1, b: 01, c: 000, d: 001 (4) a: 0, b: 110, c: 01, d: 111 (5) none of above

    答案：5

NerdLink 是一家新的网络初创公司，旨在让 MIT EECS 学生与家长保持联系。 NerdLink 通过为每个学生提供五条消息之一的在线选择来简化家长沟通，然后自动填写样板并通过电子邮件向家长发送一条长而迷人的消息版本。下面列出了这五个消息及其相对概率：

Message# Message to parents p(Message)
M1 Send money! 60%
M2 I love this course called 6.004 8%
M3 I'm changing my major to Poetry 2%
M4 I'm getting a 5.0 this term! 1%
M5 Nothing much is new...(none of above) 29%

NerdLink 最开始使用定长编码传递这些信息。

  • J. 使用定长编码传递消息所需的平均多少位。

    五种消息，需要 3 位

  • K. 给定消息的概率分布，消息 M5 实际传递的信息量是多少

    \[ I_{M5}=log_2(1/p_{M5}) = log_2(1/0.29) \]

  • L. 为了纠错，将同一个固定长度的消息连续发送 5 次。在最坏的情况下，接收端可以纠正多少个比特错误？

    使用重复码，由于重复码遵循少数服从多数的原则，其最多纠正的比特数为 $$ t = \frac{n-1}{2} $$ 最多 2 位错误

NerdLink，希望节省通信成本，聘请您作为顾问，设计用于发送消息的霍夫曼代码

  • M. 给出您的霍夫曼代码为每条消息（M1 到 M5）发送的位数，以及使用您的代码发送的每条消息的平均位数（公式即可）

    M1: 0 M2: 110 M3: 1110 M4: 1111 M5: 10

    平均编码长度 1.54 \ 理想编码长度 1.43

教务处希望对一个拥有 1000 名学生的大型 GIR 的字母成绩（A、B、C、D、F）进行编码。 他们计划使用可变长度代码对每个等级单独进行编码。

Grade p plog(1/p)
A 0.24 0.49
B 0.35 0.53
C 0.21 0.47
D 0.13 0.38
F 0.07 0.27
Totals 1.00 2.14

  • N. 使用 Huffman 算法构造可变长编码

    A: 00 B: 01 C: 10 D: 110 F: 111

    实际编码长度 2.2

  • O. 两名 6.004 学生提出了相互竞争的可变长度代码。 Alice 说，使用她的代码对 1000 个等级进行编码，平均会产生 2200 位的消息。 Bob 说，使用他的代码对 1000 个等级进行编码，平均会产生 1950 位的消息。 当书记官长询问您的意见时，以下哪一项是您的最佳回应？

    (A) 选择 Bob，拥有更短的平均长度 (B) 选择 Alice，更多的 bit 意味着更多的信息 (C) 选择 Bob，Bob 的平均长度低于理论值 (D) 选择 Alice，Bob 的平均长度低于理论值 (E) 都不选，定长编码拥有更低的平均长度

    答案：D