[关闭]
@anboqing 2016-01-09T01:56:05.000000Z 字数 2075 阅读 2530

由补码引发的关于编码的思考

基础知识 编码



导引

本文是由几个问题引发的:
1. 补码是怎么来的?
2. 为什么补码的表示范围不对称,TMin比TMax多了1?
3. 什么是编码? 编码的本质是什么?


一、 补码是怎么产生的?

补码方法 (method of complements)

在数学和计算领域,补数方法是一种用加上一个正数的方法替代减去一个负数的技术,这种技术过去用在机械计算器上,现在依然在电子计算机里使用。因为计算机里只有加法器,没有减法器,所以要把减法操作转化为加法操作。

冯诺依曼在他的1945年的关于EDVAC的第一篇手稿里建议使用2的2进制补码,受这个思想启发,在1949年EDSAC(世界上第二台存储程序数字通用计算机)里使用了补码进行计算。

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 可以像下面这样执行:

  1. 把x的 基数减一补码加到y上得到 或者 ,而这正是 的基数减一补码 少了的结果 ,例如 在 计算 8-3 , 即把 1000 的基数减1补码 0111加上0011得到
    1010 ,而这正是 即 5(0101)的基数减1补码(1010)少了 2-1的结果 。

  2. 基数补码()加到上得到或者
    ,假设 ,那么结果永远大于等于,而且丢掉最高有效位的 '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形成结果的步骤,于是在这个中间过程中,为了描述这个中间状态,就给它起了个名字叫反码。


四、对编码的理解


参考文献

  1. 原码、反码和补码
  2. two's complement Representation
  3. Method of complemet
  4. 关于2的补码
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注