搜索
计算机鼓轮假设一个旋转鼓的表面被等分为16个部分，如图14-1所示，其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示绝缘体，导体部分给出信号1，绝缘体部分给出信号0。根据鼓轮转动时所处的位置，四个触头A、B、C、D将获得一定的信息。因此，鼓轮的位置可用二进制信号表示。试问如何选取鼓轮16个部分的材料才能使鼓轮每转过一个部分得到一个不同的二进制信号，即每转一周，能得到0000到1111的16个数。这个问题也可表示为：把16个二进制数排成一个圆圈，使得四个依次相连的数字所组成的16个四位二进制数互不相同。这个问题的解决思想是这样的。设ai∈{0,1}（i=1,2,3,…,16），鼓轮每转一个部分，信号就从a1a2a3a4变为a2a3a4a5，前者的右三位决定了后者的左三位。因此，我们可把所有三位二进制数作为结点，从每个结点a1a2a3到a2a3a4连一条有向边表示a1a2a3a4这个四位二进制数，作出如图14-2所示的所有可能的码变换的有向图。于是问题就转化为在这个有向图中找一条欧拉回路。这个有向图中8个结点的出度和入度都是2，因此存在欧拉回路。例如（仅写出边的序列）e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8就是一条欧拉回路。根据邻接边的标号记法，这16个二进制数可写成对应的二进制序列0000100110101111，把这个序列排成一个圆圈，与所求的鼓轮相对应，就得到如图14-1的鼓轮设计。图14-1图14-2用类似的论证，我们可以证明：存在一个2n个二进制数的循环序列，其中2n个由n位二进制数组成的子序列全不相同。我们将上述2n个二进制数的循环序列称为布鲁因（DeBrujin）序列。