(完整word版)計(jì)算機(jī)鼓輪(word文檔良心出品)

1、14-1計(jì)算機(jī)鼓輪假設(shè)一個(gè)旋轉(zhuǎn)鼓的表面被等分為16個(gè)部分，如圖14-1所示，其中每一部分分別由導(dǎo)體或絕緣體構(gòu)成，圖中陰影部分表示導(dǎo) 體，空白部分表示絕緣體，導(dǎo)體部分給出信號(hào) 1, 絕緣體部分給出信號(hào)0。根據(jù)鼓輪轉(zhuǎn)動(dòng)時(shí)所處的位 置，四個(gè)觸頭A、B、C、D將獲得一定的信息。因 此，鼓輪的位置可用二進(jìn)制信號(hào)表示。試問(wèn)如何選 取鼓輪16個(gè)部分的材料才能使鼓輪每轉(zhuǎn)過(guò)一個(gè)部 分得到一個(gè)不同的二進(jìn)制信號(hào)，即每轉(zhuǎn)一周，能得到0000到1111的16個(gè)數(shù)。這個(gè)問(wèn)題也可表示為：把16個(gè)二進(jìn)制數(shù)排成一個(gè)圓圈，使得四個(gè)依次相連的數(shù)字所組成的16個(gè)四位二進(jìn)制數(shù)互不相同這個(gè)問(wèn)題的解決思想是這樣的。設(shè)0,1 (i = 1,

2、2,3,16)，鼓輪每轉(zhuǎn)一個(gè)部分，信號(hào)就從a1a2a3a4變?yōu)閍2&a4a5，前者的右三位決定了后者的左三位。因此, 我們可把所有三位二進(jìn)制數(shù)作為結(jié)點(diǎn)，從每個(gè)結(jié)點(diǎn)a1a2a3到a2a3a4連一條有向邊表示a1a2a3a4這個(gè)四位二進(jìn)制數(shù)，作出如圖14-2所示的所有可能的碼變換的有向 圖。于是問(wèn)題就轉(zhuǎn)化為在這個(gè)有向圖中找一條歐拉回路。這個(gè)有向圖中 8個(gè)結(jié)點(diǎn)的出度和入度都是2，因此存在歐拉回路。例如(僅寫(xiě)出邊的序列)ae1 6469636661361065611 e715e14e12e8 就是一 -條歐拉回路。根據(jù)鄰接邊的標(biāo)號(hào)記法，這16個(gè)二進(jìn)制數(shù)可寫(xiě)成對(duì)應(yīng)的二進(jìn)制序列 0000100110101111把這個(gè)序列 排成一個(gè)圓圈，與所求的鼓輪相對(duì)應(yīng)，就得到如圖14-1的鼓輪設(shè)計(jì)。圖 14-2用類似的論證，我們可以證明：存在一個(gè)2n個(gè)二進(jìn)制數(shù)的循環(huán)序列，其中2n個(gè)由n位二進(jìn)制數(shù)組成的子序列全不相同。我們將上述2n個(gè)二進(jìn)制數(shù)的循環(huán)序列稱為布魯因( De Brujin )序列。en=0000e= 1000=0001e9=1001e=0010el0-1010勺=0011en=IOlle4=0100ep=l100