How to do that – Binary to Decimal conversion (BCD)


做每件事情, 就是 [人, 機, 物, 法] 四大元素的過程和結果, 這一次呢,

人, 你我他, people

機, 電腦, computer

物, 資料, 計算結果, 目的, result, objective

法, 計算方法, 簡稱 [算法, Algorithm]

計算機或電腦, 其實是工具, 幫助人類去做不斷重複的計算, 有電就不會停, 也不覺得累, 但計算原理和算盤類似.

資料, 只是人類自己定義的一連串很複雜的訊息組合而已. 例如, 一個銅板(硬幣)有正反兩面, 如果這正面稱為 “0″, 反面稱為 “1″

首先, 重溫一下, 甚麼是 “0″ 和 “1″,

neo_img_coins-and-binary1.jpg
neoimgcoins-and-binary1.jpg

那麼, 平放在桌面的每個銅板被看到的, 不是正面就是反面, 所以可以表達 “0″ 或 “1″,

這些最基本的 “0″ 和 “1″, 如果同時用更多的銅板不斷地組合, 不斷地延伸, 結果就有了人認識這個客觀世界的種種紀錄或者經驗, 稱為資訊或資料. 發展到今天, 也只是不斷的重複這種演變過程.

neo_img_binary-and-its-bits.jpg
neoimgbinary-and-its-bits.jpg

neo_img_4-bits-and-numbers.jpg
neoimg4-bits-and-numbers.jpg

為了實現目標, 需要在終端機顯一個以阿拉伯數字表示, 人類易讀的計算結果, 又要讓電腦這個機器能夠處理我們提出的計算需要, 於是有了 Binary To Decimal convesrion 計算的方法 – 演算法的設計或誕生.

其實以前也學過用過了一種 Binary To Decimal conversion 計算法. 可以把電腦能夠處理的2進制數目,轉換成常人熟悉且常用的10進制數目, 一種名為 [除以10的餘商法], 記得除法跟餘數商數, 是小學數學的基本, 可是很少人會注意這樣的規律, 俺自己也不例外, 但需要用到時, 自然也必然需要找到方法, 也就是學習或者溫故知新的過程. 也正是有些這樣那樣的規律, 才能發展成為 [算法], 一種有效率通用可以擴展的計算方法, 不必針對特別機器設計, 原理是可以放在任何地方派上用場. 所以了解 [算法] 的最根本原理, 才是設計的重點, 不然, 不同的場合遇到同樣的問題會顯得一籌莫展. 重溫 [除以10的餘商法], 可以看看最下面表列參考的出處.

後來, 遇到了類似問題, 一個功課, 用 4 BIT 的 CPU, 沒有除法功能, 但需要解決同樣的 Binary To Decimal conversion, 當然 [除以10的餘商法] 就顯得很吃力了, 不是不能做, 而是很辛苦, 沒有效率. 暫且這裡不表述詳細, 因為當看官日後明白了, 也不用俺多作解釋, 因為俺當初看到人家這樣說法, 也是有聽沒有懂. 當實際問題來了, 就要進一步探討, 除了 [除以10的餘商法], 還有沒有其他算法呢. 當然是有的, 要不然你看電子跳字的手表或考試用的計算機怎樣實現呢 !? 結果呢, 學到了一種名為 [Double Dabble Algorithm] 的算法. 無論如何, 絕大多數的 CPU 設計, 都會有 [加法] 及 [乘以2] 及 [除以2] 三種基本的運算指令, [除法] 卻不是每種 CPU 都有, 尤其是人類早期發展應用的 CPU. 那麼這種 [Double Dabble Algorithm] 的算法, 顯然就很適用.

到底 Double dabble algorithm (俺自稱她為 – 連動左移位BCD求取法), 因為沒有專門念過 COMPUTER ENGINEERING, 不知道她的名稱起源, 照字面翻譯也不倫不類的. 作法其實比較簡單,


1) 由右邊往左邊, 依次放置 BIN 數, BCD數的個位, BCD數的百位, BCD數的千位......

2) 檢查各個 BCD 位, 如果大於 4, 就是 5 - 9 之間的話, 就把這個 BCD 位 + 3 (BCD 每個位只能顯示 0 - 9 的任何一個數字)

3) 然後把 BIN 和 BCD 看成一整串, 把她向左移一位 (乘以2的運算)

4) 重複 (2) 到 (3) 的動作, 直到 BINARY 的所有 BIT 全部移到 BCD 個位為止

到底為什麼 BCD數的 每個位  > 4 就要 + 3, 然後再乘以 2 呢 ?

那是因為 BCD 用 4 BIT 來表示 0 – 9 (0000B – 1001B), 但是 4 BIT 都全用的話, 可以表示的範圍是 0 – 15 (0000B – 1111B)

當 10 需要用 BCD 來表示的話, 人會就把 10 分開, 變成1,0, 動用 BCD 的十位和個位, 變成 0001,0000, 這時候, 電腦看這個BCD數是 0001,0000B, 也就是 0x10 HEX (由0開始算的話, 就是 15; 由1開始算的話, 就是 16)

所以, 只要是 10 或以上, 就要 + 6, 二進制的電腦才會出現進位, 這個進位, 就會出現在 BCD 的十位的那個 “1″

公式是 10 + 6 = (10 / 2 + 6 / 2 ) x 2 = ( 5 + 3 ) x 2

也就是 Double dabble algorithm 算法的來源, Double 是雙倍的意思, 就是 x2, dabble 則是 + 3 的動作

實際的作法是 先做 BCD 位的 dabble (if > 4), 再做整串的 Double (那何不叫做 Dabble Double Algorithm 呢?)

她的好處是, 不用理會移位會不會發生進位, 因為事前就準備好了逢10進1的需要, 不用除法指令, 只用加法.

這裡也會看到她的速度優勢, 如果要移 24 BIT 或更多, 最左面越多連續的 “0″, 表示這個 BINARY 越小, 計算的速度會越快, 而且基本上算法的結構是支持無限多的 BIT, 也就是非常大的 BINARY 數目都是一樣的設計.

實際做一次, 就是最好的學習方法, 用紙筆, 可以教人家怎樣計算的話, 也就是差不多可以教會電腦怎樣計算了. 這個就是學習算法設計的原理.

neo_img_bcd-conversion-double-dabble-algorithm.jpg
neoimgbcd-conversion-double-dabble-algorithm.jpg

當然, 最後就交給電腦去慢慢算, 俺的目標達到了 – 在終端機看到一個個以阿拉伯數字表示的10進制數目, 借助了 Binary To Decimal conversion 演算法.

例如, 測溫度的 ADC 讀值 101110100010001B, 經過一連串的轉換計算, 得到的數字是 0x147, 電腦看得懂, 俺卻是….

用這個 Double Dabble 算法 或者 [除以10] 算法, 俺看到 3,2,7, 那就是溫度 = 327度C

看, 資料是一樣的, 不同的方法解讀, 對人的意義就會不一樣, 觀點與角度, 是可以營造出很多不同的結果.

excel file of this assignment

https://xiaolaba.files.wordpress.com/2012/09/bin2bcd_double_dabble_algorithm_jpgnrar.jpg

https://xiaolaba.files.wordpress.com/2012/09/bin2bcddoubledabblealgorithmjpgnrar.jpg

資料與編碼, BCD, EXCESS-3 等等的資料
http://www.gauss.com.tw/logic/ch2/2-3.htm

http://ann.nihs.tp.edu.tw/nihsw9/logic-1-joe/logic/ch2/p7.htm

BCD 算法的設計, Binary to BCD Conversion Algorithm
http://www.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html

http://en.wikipedia.org/wiki/Double_dabble

新臺幣圖樣
http://zh.wikipedia.org/wiki/%E6%96%B0%E8%87%BA%E5%B9%A3

[除以10的餘商法], AVR ATTINY26, 減肥實驗時遇到的問題及解決過程, 老外稱為 [divided by ten algorithm],
http://blog.yahoo.com/_75UIOHG2UVM5RMBLG4ZZVVJLTA/articles/382365
http://xiaolabadiy.tumblr.com/post/62500597513/avr-attiny26
2014-06-30 update link

 

很多電腦學科的算法列表
http://en.wikipedia.org/wiki/Listofalgorithms#Numbertheoreticalgorithms

end

廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s