一种实现MSD加法的新方法

通过对三值光学计算机的工作原理及MSD加法算法进行分析，发挥三值光计算机位数多、易于完成逻辑运算的优点，在三值光计算机上实现了MSD加法。

三值光学计算机MSD加法

一、引言

随着上世纪60年代激光技术的问世，兴起了以傅里叶光学为基础的模拟光学计算的研究。该技术是将光束作为信息载体，利用改变光状态进行信息处理的一种新型计算技术。研究光计算的初衷是为了解决光学控制、光学检测、图像处理等各种各样的实际问题。然而由于电子计算机固有的某些缺陷随运算速度的提高而明显的暴露出来，而光计算技术的许多研究成果如光学运算部件的问世促使光计算的研究越来越向光计算机靠拢，吸引了众多计算机学者对其展开研究。考虑到光学方法具有天然的处理“平面”信息的特性，研究者开始探索求解矢量运算的光学方法。

二、三值光学计算机简介

由于电子计算机存在着因电子本性造成的固有局限性，如：冯诺曼瓶颈、互连带宽窄和时钟歪斜等问题，限制了其计算能力的进一步提高。而且处理器集成度的提高和超级电子计算机中微处理器数量的增多，将大幅度提高系统的复杂度和功耗。同时，功耗增大使得系统的发热量急剧上升，将会威胁到电子计算机系统的运行稳定性和可持续性，最终将导致电子计算机的投入产出比严重下降，且缺乏足够的适用性。

三值光学计算机（Ternary Optical Computer，TOC）是从构造计算机的基本原则和光的基本特性出发，充分利用光的空间巨并行性和无高频辐射衰减性，将光强度与光的偏振方向结合起来表示三值信息，提出的一种全新的光计算机体系结构。三值光学计算机用两个正交的偏振态和无光态表示信息，所以，它的一个数据位上有三个取值，除0和1之外，还可以再取一个值。它用液晶阵列控制光束的偏振方向，配合偏振片来完成信息处理。由于液晶阵列的像素非常多，所以三值光学计算机的数据位数非常多，而且很容易继续扩大。另一方面，数百万像素液晶屏的功耗也在毫瓦级，决定了三值光学计算机将耗能很小。

三值光学计算机实验系统的光学处理器依据降值设计原理建造，对这种处理器而言，降值设计原理表述为：在39（=19683）个三值逻辑处理器中，任意一个都可以用18种运算基元组合而成，而且用到基元总数不多于6个。于是，三值光学处理器中只要对18种运算基元准备好足够的数量，就可以随时把光学处理器的任何部分构造成用户需要的某个三值逻辑运算器。这称为三值光学处理器的重构性。

由于逻辑运算的位和位之间没有关联，因此可以把一个光学处理器的不同位置，即数据位的不同片段，构造成不同的逻辑运算器，于是，在一个操作指令下，这个光学处理器的不同区域能完成不同的逻辑运算。这是电子计算机所做不到的。另一方面，又可以把一个光学处理器看作是一个大光学处理器的一部分，当这个光学处理器的数据位数不够多时，可以启用大光学处理器的其他部分，即给这个光学处理器拼接一个新的光学处理器，二者形成一个较大的光学处理器，而不像电子计算机形成“多CPU”或“多核”。因此，当用几个光学处理器拼接成一个大处理器时不存在“核间通信”和“核间同步”问题。这是与电子计算机的又一个不同点。同时，光学处理器的这种直接拼接性，更使得三值光学计算机可以有很多的数据位数，理论上多到满足任何用户的需要。

正是由于上述结构特点、可重构特性、以及位数众多的优势，三值光学计算机适合进行矢量运算。

三、MSD加法算法及改进

（一）MSD加法原理

改良符号数（modified signed-digit，MSD）系统是符号数系统的子集，基于MSD编码的加法没有进位传播，算法的复杂度与加法操作数的位数无关，这些特性有利于充分发挥光的并行性，特别适合用光学方法实现。

常规n进制计数制中有n个计数符号，用p0，p1，p2，…，pn-1分别表示0，1，2，…n-1，并逢n进1。MSD计数是一种有一个冗余符号i的二进制表示，其中i表示-1。

MSD加法是通过T，W，T’，W’这四种变换完成的，这四个变换都是二元三值逻辑运算，运算法则如表1至表4所示。

可以看出两个n位的MSD数相加的结果是一个n+2位MSD数，而且所需的步数与两操作数的位数无关，MSD加法可以克服两高位数相加时由于进位传播导致的计算速度瓶颈问题。

（二）用三值光学计算机改进MSD加法算法

MSD加法在完成加法时，首先把两个加法操作数的每一个数据位转换成辅助中间数，然后对中间数进行几次逻辑变换，因此需要数倍于数据位数的运算器位数和很多逻辑运算器，这也是以前各种实现MSD加法的方法通用性较差的原因。三值光学计算机的位数多，而且三值逻辑光学处理器具有可重构特性，随时把处理器的任意区域构造成需要的二元三值逻辑运算器，这使得三值光计算机更适合处理数据位之间没有关联的逻辑运算，因此在三值光计算机上实现了MSD加法。四、结论

本文通过对三值光学计算机的工作原理及MSD加法算法进行分析，发挥三值光计算机位数多、易于完成逻辑运算的优点，随时把处理器的任意区域构造成需要的二元三值逻辑运算器，在三值光计算机上实现MSD加法，弥补了MSD加法的不足，较以往的实现方法而言，三值光计算机实现MSD加法的方法的通用性得到提高。

参考文献：

[1]黄平，何善宝，赵春明.基于稀疏序列LDPC的多层码的迭代译码[J].东南大学学报（自然科学版），2006（02）.

[2]王先超，姚云飞，金翊.基于三值光计算机的并行无进位加法[J].计算机科学，2010（02）.