題目
Create functions to encode a number to and decode
a number from Gray code. Display the normal binary
representations, Gray code representations, and
decoded Gray code values for all 5-bit binary
numbers (0-31 inclusive, leading 0's not necessary).
There are many possible Gray codes. The following
encodes what is called "binary reflected Gray code."
Encoding (MSB is bit 0, b is binary, g is Gray code):
if b[i-1] = 1
g[i] = not b[i]
else
g[i] = b[i]
Decoding (MSB is bit 0, b is binary, g is Gray code):
b[0] = g[0]
for other bits:
b[i] = g[i] xor b[i-1]
背景
典型的二進制格雷碼（Binary Gray Code）簡稱格雷碼，因1953年公開的弗蘭克·格雷（Frank Gray，18870913-19690523）專利“Pulse Code Communication”而得名，當(dāng)初是為了通信罕模，現(xiàn)在則常用于模擬－數(shù)字轉(zhuǎn)換和位置－數(shù)字轉(zhuǎn)換中联喘。法國電訊工程師波特（Jean-Maurice-émile Baudot剖效，18450911-19030328）在1880年曾用過的波特碼相當(dāng)于它的一種變形远寸。1941年George Stibitz設(shè)計的一種8元二進制機械計數(shù)器正好符合格雷碼計數(shù)器的計數(shù)規(guī)律覆糟。
二進制碼→格雷碼 說明
此方法從對應(yīng)的n位二進制碼字中直接得到n位格雷碼碼字靡羡，步驟如下：
對n位二進制的碼字系洛，從右到左俊性，以0到n-1編號
如果二進制碼字的第i位和i+1位相同，則對應(yīng)的格雷碼的第i位為0描扯，否則為1（當(dāng)i+1=n時定页，二進制碼字的第n位被認為是0，即第n-1位不變） [4]
公式表示：
關(guān)注點：
- 順序是右到左典徊，和我們通常使用的序號是反的。
- 第n-1位不變恩够，比如 011 0是第n-1位卒落，第n位認為是0，相當(dāng)于在前面加了0變成 0011蜂桶，0和 0 or 1 異或不會改變原來的值儡毕。
輸入 - B : 011 轉(zhuǎn)換 過程 1^1 =1 1^0=0 0^0=0(第n-1位不變) 輸出 G : 010
格雷碼→二進制碼 說明
從左邊第二位起，將每位與左邊一位解碼后的值異或扑媚，作為該位解碼后的值（最左邊一位依然不變）腰湾。依次異或，直到最低位疆股。依次異或轉(zhuǎn)換后的值（二進制數(shù)）就是格雷碼轉(zhuǎn)換后二進制碼的值费坊。
公式表示：
（G：格雷碼，B：二進制碼）
關(guān)注點
- 順序不變旬痹， n-1不變附井。b[n-1] 異或 g[n-2] = b[n-2] 以此類推到第0位。
- 輸入G: 111 b[n-1] = g[n-1] b[n-2] = b[n-1] 異或 g[n-2] 輸出 B: 101
測試代碼
public class GrayCodeTest {
@Test
public void should_001_encode_001(){
String input="001";
String except ="001";
String result = GrayCode.encode(input);
assertEquals(except,result);
}
@Test
public void should_010_encode_011(){
String input="010";
String except ="011";
String result = GrayCode.encode(input);
assertEquals(except,result);
}
@Test
public void should_0111_encode_0100(){
String input="0111";
String except ="0100";
String result = GrayCode.encode(input);
assertEquals(except,result);
}
@Test
public void should_0100_decode_0111(){
String input="0100";
String except ="0111";
String result = GrayCode.decode(input);
assertEquals(except,result);
}
@Test
public void should_100_decode_111(){
String input="100";
String except ="111";
String result = GrayCode.decode(input);
assertEquals(except,result);
}
@Test
public void should_001_decode_001(){
String input="001";
String except ="001";
String result = GrayCode.decode(input);
assertEquals(except,result);
}
}
實現(xiàn)代碼
public class GrayCode {
public static String encode(String input) {
int len = input.length();
String[] result = new String[len];
for (int i = len-1; i>0 ; i--) {
result[i]=String.valueOf(input.charAt(i)^input.charAt(i-1));
}
result[0]=String.valueOf(input.charAt(0));
return String.join("",result);
}
public static String decode(String input) {
int len = input.length();
String[] result = new String[len];
for (int i = 0; i<=len-1 ; i++) {
if(i==0){
result[i] = String.valueOf(input.charAt(0));
}else {
result[i] = String.valueOf(result[i-1].charAt(0)^input.charAt(i));
}
}
return String.join("",result);
}
}
Gray Code 理解如何轉(zhuǎn)碼編碼需要花些時間两残，實現(xiàn)代碼并不復(fù)雜永毅。寫代碼就是需要理解問題，通常需要手工實現(xiàn)然后代碼實現(xiàn)人弓。
