操作码优化与编码技术：哈夫曼编码与扩展压缩

"计算机系统结构复习笔记及习题.pdf" 这篇文档主要讨论的是计算机系统中的指令操作码优化问题，特别是如何通过不同的编码方式减少信息冗余度，提高存储和处理效率。以下是相关知识点的详细说明： 1. **信息熵与信息冗余度**： - 信息熵（Entropy）是衡量一个信息源的平均信息量，它表示信息的不确定性。公式为：\( H = -\sum p_i \log_2 p_i \)，其中 \( p_i \) 是第 i 个事件发生的概率。 - 信息冗余度是指在信息传输或存储过程中，实际平均信息量与信息熵的差值，它代表了可以被压缩的信息量。 2. **定长编码与信息冗余**： - 定长编码是一种每个符号都用固定长度的二进制位来表示的方法。如文中提到的3位编码方式，即使某些指令出现的概率很低，也会分配相同的位数，导致浪费。 3. **哈夫曼编码**： - 哈夫曼编码是一种可变长度的前缀编码方法，它根据符号出现的频率进行编码，频率高的符号使用较短的编码，从而降低信息冗余度。文中的哈夫曼树展示了不同操作码的频率和对应的编码。 4. **扩展压缩编码**： - 扩展压缩编码介于定长编码和哈夫曼编码之间，它允许操作码有不同的长度，但通过特定规则（如高两位表示高频操作码）来减少冗余。这种编码方式在实践中可以实现较好的效率和实用性。 5. **编码效率比较**： - 文中比较了三种编码方式的信息冗余度：定长编码的信息冗余度最高，哈夫曼编码次之，而扩展压缩编码虽然比哈夫曼编码的冗余度略大，但在实际应用中更为可行。 6. **涨编码和分段法**： - 涨编码可能是文中提及的一种特定编码技术，但具体细节未给出。分段法（如15-15-15分法）可能是将操作码分为等长段，然后对每个段进行编码的策略。 7. **编码长度的扩展**： - 提到了编码长度从2位扩展到4位的过程，通过扩展编码，可以增加编码的表示范围，以适应更复杂的操作码频率分布。 通过以上知识点，我们可以理解计算机系统在设计指令集时如何考虑信息熵和冗余度，以及如何选择合适的编码策略来优化存储和处理效率。这些概念对于理解计算机系统结构和编译原理至关重要。