@anboqing
2016-01-09T09:56:05.000000Z
字数 2075
阅读 2706
由补码引发的关于编码的思考
基础知识 编码
导引
本文是由几个问题引发的：
1. 补码是怎么来的？
2. 为什么补码的表示范围不对称,TMin比TMax多了1？
3. 什么是编码？ 编码的本质是什么？
一、 补码是怎么产生的？
补码方法 (method of complements)
在数学和计算领域，补数方法是一种用加上一个正数的方法替代减去一个负数的技术，这种技术过去用在机械计算器上，现在依然在电子计算机里使用。因为计算机里只有加法器，没有减法器，所以要把减法操作转化为加法操作。
冯诺依曼在他的1945年的关于EDVAC的第一篇手稿里建议使用2的2进制补码，受这个思想启发，在1949年EDSAC(世界上第二台存储程序数字通用计算机)里使用了补码进行计算。
许多早期计算机使用了 ones' complement（反码）表示。IBM700/7000系列科学计算机用了符号数值表示法（原码）,但是寄存器下标用了补码.早期使用补码的商用计算机包括DEC的PDP-5和1963PDP-6.在1964年IBM生产并迅速主宰了市场的 System/360，使补码表示成为了计算机工业界最广泛使用的表示法。第一台微型计算机PDP-8使用了 two's complement,以后的几乎所有微型计算机都使用了二进制补码表示。
先上几张机械计算器的图：
Various desktop mechanical calculators used in the office from 1851 onwards. Each one has a different user interface. This picture shows clockwise from top left: An Arithmometer, A Comptometer, A Dalton adding machine, a Sundstrand and an Odhner Arithmometer
不解释。。。
数值补码 (numeric complements)
n位数字y在以b为基数的系统里的基数补码(radix complement) 是 . 这里 就是模。
基数补码通常可以用 diminished radix complement（基数减一的补码，也就是课本上说的反码）来轻易的获取,即,因为 是 重复了n次，即 [b-1,b-1,b-1,....b-1] , 基数减一的补码可以通过将每一位补满 b-1来得到（即，把y里每一位用b-1减掉）.
x-y 可以像下面这样执行：
把x的 基数减一补码加到y上得到 或者 ,而这正是 的基数减一补码 少了的结果 ，例如 在 计算 8-3 ， 即把 1000 的基数减1补码 0111加上0011得到
1010 ，而这正是 即 5（0101）的基数减1补码（1010）少了 2-1的结果 。把的基数补码()加到上得到或者
,假设 ,那么结果永远大于等于，而且丢掉最高有效位的 '1'相当于减去了,那么结果就变成了，或者仅仅是,这就是需要的结果;
这正好解释了把减法转换为加法后，如果产生了加法溢出，那么虽然溢出丢掉了进位，结果仍然是正确的，多奇妙！
当b等于2的时候，我们就得到了计算机里用的 Two's complement.
补码建立起了 从 二进制数字向量 到 某一个范围内的数字 之间的 双射（bijection)
二、 为什么补码的负数范围 |Tmin| 比 |Tmax| 多 1？
看图说话，可以把它想象成钟表，而钟表上的刻度数量就是所能编码的数量，我们设计一套规则赋予每个刻度一个意义，建立起 意义 和 刻度 之间的 一一映射 ，这个过程就是编码的过程，用同一套规则，可以去解释意义，找到刻度本身，这就是解码的过程。
而在设计补码的时候，把钟表的12个刻度分成2部分，让一部分表示负数，另一半表示非负数，而0也是非负数，所以0把最大的正数的位置占了，于是造成了范围不对称。
A+B = 模，那么 A和B是互补关系
补数顾名思义就是那个能把自己补满成模的大小的数
三、为什么要有反码原码这等鸡肋概念？
上面也说过，反码(ones' complement)的提出，只不过是因为在直观感受上，把一个二进制数01011011补满 成11111111再加1 , 比把它直接补成11111111要来的容易，也容易在硬件上实现。所以产生了求补码前先用
diminished radix complement（反码） 求补，再加1形成结果的步骤，于是在这个中间过程中，为了描述这个中间状态，就给它起了个名字叫反码。
