位移連續(xù)碼的編碼

位移連續(xù)碼的編碼

1位長為2n位編碼的編碼所謂的“連續(xù)位移碼”編碼是一種由0.1位組成的編碼。它的任何一個編碼的后繼編碼可視為其前趨編碼平移一位后再補一個“1”或“0”。不失一般性,可設(shè)其向左平移一位。去掉最左一位并在最右端之后補位。例如果當(dāng)前編碼為0100110100,那么去掉最左位后變成100110100,向左平移一位并在最右端之后補位則有1001101000或1001101001。雖然平移補位的方式有兩種,但實際上每個編碼的后繼編碼都是唯一的。究竟如何選擇,要看整個最終編碼序列是否滿足編碼的唯一性原則。即在整個編碼序列中不得有重碼。對于具有n位的位移連續(xù)編碼,在相鄰兩個編碼中有連續(xù)n-1位是相同的。如果把一個位移連續(xù)編碼序列中的相鄰編碼按它們的相同部分重疊排列,就會得到一個位移連續(xù)碼的重疊序列。例如下面的編碼序列:0000100110101111000,這是一個位長為4的位移連續(xù)碼的重疊序列。其中每4位相鄰的0/1數(shù)碼組成一個唯一的編碼。若以任意一個位置上的數(shù)碼為首,并與其右鄰3個數(shù)碼組成一個編碼,就可得到一個與數(shù)碼位置相關(guān)的編碼序列,如表1。可以看到,任何一個編碼的后繼編碼是其前趨編碼平移一位后再補一個“1”或“0”。定理:對于位長為n的位移連續(xù)碼,其最大編碼范圍為2n。并且存在最大編碼重疊序列長度為2n+n-1位。證明:考慮編碼重疊序列的長度為k,(k≤2n)。不失一般性,可假定編碼序列的首碼為00…0(n個0)。當(dāng)k=2時編碼序列長度為k+n-1=n+1,編碼序列為:00…01。其中有兩個n位編碼,分別為00…0和0…01。顯然滿足編碼的唯一性原則。設(shè)k≤2n時編碼序列同樣滿足編碼的唯一性原則。若存在k+1≤2n使得編碼序列仍舊滿足編碼的唯一性原則,定理將得證(歸納法)。這里用反證法證明這個k+1的存在。設(shè)有一個位移連續(xù)編碼重疊序列,其中共有k個互不相同的編碼。第k個編碼可表示為0β或1β(β表示由n-1個0/1組成的編碼),則第k+1個編碼應(yīng)該是β0或β1。若第k+1個編碼違反了唯一性原則,就意味著在前k個編碼中已包含了β0和β1且其前趨編碼為0β或1β。但它們的前趨編碼若相同,即或同是0β,或同是1β,則在前k個編碼中存在相同的編碼,這與最初假設(shè)矛盾。若它們的前趨編碼不相同,即如果其中一個為0β而另一個為1β,則必有一個與第k個編碼相同,說明在前k個編碼中也存在相同的編碼,這與最初假設(shè)仍矛盾。因此,對于位移連續(xù)編碼,若前k個編碼滿足唯一性原則,那么第k+1個滿足唯一性原則的編碼必定存在。由于位長為n的二進制編碼最多只有2n個不相同的,所以k的最大值為2n。因為k=1時編碼序列的長度為一個編碼的長度n,也即n=k+n-1(k=1)。當(dāng)k=2n時即有最大編碼重疊序列長度為2n+n-1位。定理得證。2求解約束條件的問題接下來的問題是如何求出位移連續(xù)編碼的序列。實際上就是確定每個編碼的后繼編碼。設(shè)最大編碼重疊序列為解向量(x1,x,…,xk,…,xm,xm+1,…,xm+n-1),其中k<m,m=2n,n為一個編碼的位長,xk的值取0或1。在這個向量中的任何兩個部分量(xi,xi+1,…,xi+n-1)和(xj,xj+1,…,xj+n-1)都必須滿足xi+p≠xj+p,其中1≤i,j≤m,0≤p≤n-1。此為解的約束條件。如果解向量的前k個分量中有重碼,使上述約束條件得不到滿足,則整個解都不成立。由此可知,這個問題具有完備性。眾所周知,具有完備性的問題可用回溯法求解。這里給出求編碼序列(如表1中的序列)的算法原理。其基本思想是:不失一般性,設(shè)n位編碼的第一個編碼為全0碼。先把它計入編碼集合,然后進行左移編碼。所謂左移編碼就是將當(dāng)前編碼左移一位(去掉最左一位)。然后先在最右端補0,檢查左移補0后的新編碼在前面的編碼過程中是否出現(xiàn)過,即新編碼是否是重碼。如果不是重碼則將新編碼計入編碼集合,然后繼續(xù)左移編碼。如果是重碼,則要將新編碼的末位改為1,然后再進行左移編碼。如果新編碼的末位已是1了,并且是重碼,就要重新處理新編碼的直接前趨位置編碼。找出編碼集合中最后一個編碼作為當(dāng)前碼(回溯),并從集合中刪掉它?？疾楫?dāng)前編碼的末位,若為0,則去0補1;若為1,還需重新處理當(dāng)前碼的直接前趨碼(再回溯)。如此往復(fù)地左移編碼直至2n個編碼全部產(chǎn)生。算法流程見圖1。3位移連續(xù)編碼的應(yīng)用3.1cd編碼位的編碼和發(fā)直線編碼器是一種用于長度和位置測量的器具。由于傳統(tǒng)編碼方式的缺陷,現(xiàn)有的直線編碼器只是用于解決小范圍和低精度測量的問題。位移連續(xù)碼直線編碼器的原理結(jié)構(gòu)設(shè)計如圖2(a),主要由兩部分組成。一個是直線編碼尺(簡稱編碼尺),在編碼尺上刻有表示位置的二進制編碼刻線如圖2(b)。編碼刻在光學(xué)材料上,可以是透射線式,也可以是反射式。以實刻線表示“1”,而“0”則以空白表示。圖2(c)表示了圖2(b)的二進制編碼含意。編碼器的另一組成部分是CCD細(xì)分讀數(shù)頭,它的核心元件就是一個CCD線陣電荷耦合器件,簡稱CCD。照明系統(tǒng)將刻線影像投影到CCD器件上,CCD就獲得一幅編碼圖像,經(jīng)過光電轉(zhuǎn)換和計算處理,系統(tǒng)就可識別編碼的數(shù)值,進而獲得這個編碼的位置信息。CCD細(xì)分讀數(shù)頭除了具有識別編碼的作用外,另一個主要的功能就是細(xì)分。仍以圖2(b)中的編碼尺為例,來詳細(xì)說明位移連續(xù)碼直線編碼器的編碼原理。在普通的線紋尺中(如鋼卷尺),被測的長度數(shù)值用線紋尺上兩條刻線間刻線的數(shù)目加1表示。同時每條刻線都有自己的標(biāo)稱值,代表刻線當(dāng)前位置與測量起點(0位)刻線間刻線數(shù)目加1。由于所有刻線間距均勻相等,所以刻線間距與刻線數(shù)目的乘積即為標(biāo)稱值的長度。盡管每條刻線都有其標(biāo)稱值,但單獨一條刻線本身不能給出標(biāo)稱信息,只好用文字標(biāo)注刻線的標(biāo)稱信息。因為無法每條刻線都標(biāo)注,現(xiàn)在的通用做法是間隔幾條刻線標(biāo)注一次。對編碼尺上的所有位置采用所謂“位移連續(xù)碼”。在編碼尺上編碼刻線的間距是不相等的,如圖2(b),但任何相鄰刻線的間距都是某個常數(shù)的整數(shù)倍。在編碼尺上,以這個常數(shù)的間距連續(xù)均勻地分布編碼位。在編碼位的位置上,用刻線表示編碼“1”,若無刻線則表示“0”。任何一個編碼位都以自身及其右鄰若干位編碼值組成該編碼位的位置標(biāo)稱值。它表示了該編碼位與編碼起始位間的距離。在圖2(b)中,編碼尺以4位編碼表示編碼位置的標(biāo)稱值。每個編碼位的編碼值與表1中的相等。編碼尺上每個編碼的位長,決定了編碼的范圍,也決定了編碼器的測量最大值。圖2(b)中編碼器的編碼位長為4,則編碼范圍為0～15,測量范圍為(0～15)×編碼位間距。3.2cd編碼盤上的漸開線刻制高精度的分度盤一般采用圓光柵做分度基準(zhǔn)。但光柵有一些難以克服的缺點,如制造及安裝精度要求高、只能相對位置測量等。采用位移連續(xù)碼的編碼分度盤也可達(dá)到很高的精度并能避免圓光柵的不足。漸開線型CCD細(xì)分光學(xué)分度盤的結(jié)構(gòu)如圖3,主要由兩部分組成。其一是漸開線編碼轉(zhuǎn)盤(簡稱編碼轉(zhuǎn)盤),上面刻有表示轉(zhuǎn)盤轉(zhuǎn)角位置的漸開線。另一部分是CCD細(xì)分讀數(shù)頭。CCD的感光單元在編碼轉(zhuǎn)盤漸開線的法線方向上依次排列,光學(xué)系統(tǒng)將漸開線的影像放大并投射到CCD的感光單元上。編碼盤轉(zhuǎn)動時的不同位置會在讀數(shù)頭中產(chǎn)生不同的漸開線編碼。CCD在識別轉(zhuǎn)角編碼的同時也對漸開線所移動的位置進行精細(xì)測量。為了在CCD讀數(shù)頭上直接讀出編碼盤偏轉(zhuǎn)角的值,編碼盤上的漸開線以編碼的形式刻制,如圖4。在普通的線紋式圓刻度盤上,被測的角度值用刻度盤上兩條刻線數(shù)目加1表示。實際上每條刻線都有自己的標(biāo)稱值,代表當(dāng)前刻線與測量起點(零位)間的角度值(即刻線的數(shù)目)。由于刻線間的弧度是相等的,所以刻線間的弧度與刻線數(shù)目的乘積即為被測量的角度。盡管每條刻線都有標(biāo)稱值,但不可能所有的刻線都進行標(biāo)注。在編碼盤上,以不相等的間距刻制漸開線,如圖4,但任何相鄰刻線的間距都是某個常數(shù)的整數(shù)倍。在編碼盤上,以這個常數(shù)的間距連續(xù)均勻地分布編碼的位置。在編碼的位置上,用刻線表示編碼“1”,若無刻線則表示“0”。任何一條刻線都以自身及其右鄰若干條刻線組成該條刻線的位置標(biāo)稱值。它表示了該條刻線與起始刻線間的