顯示具有 CRC 標籤的文章。 顯示所有文章
顯示具有 CRC 標籤的文章。 顯示所有文章

2018年1月22日 星期一

DS18B20-認識CRC(3)

 CRC主題從開始到此篇已進入第三篇,其中有CRC基礎及簡化CRC的詳細步驟,到上一篇將CRC-8的操作步驟規律整理至五步驟,那時,我以為這就是最終的簡化(其實也可以拿來寫程式了),但參考了其他程式庫,才知道還可以更精簡。整理如下!

精簡:提前位移,更好!

其實再簡化的步驟,就只是將向右位移的步驟提前至第二步驟,當計算值經XOR運算後為"0"時,位移值既為最終值,若為"1"時,直接與"10001100"進行XOR的運算既可。
說起來,向右位移的步驟往前,好像也沒什麼,但各位若細細品味,應可體會它對於程式的程序的精簡有不可小看的功效。


CRC-8的概念及程式碼

底下是概念圖及程式碼的整合,上面所說的精簡部份,可參考上一篇"[DS18B20-認識CRC(2)]"的概念圖,必須依初值X="1/0"的狀態與"0x80"與"0x18"進行XOR運算,而精簡後,則只要當初值X為"1"時,與"10001100"(0x8C)進行XOR運算既可,這樣對於程式設計的程序達到了極佳的精簡。

下一步,完整的程式碼!

當初在摸索CRC時,一開始也看不懂,先看CRC數學運算說明,有看沒有懂。再去看程式碼(如上圖),還是看不懂!後來,乾脆就用最笨的方法,進入位元值的角度,用填空格及移位的方式來摸索,這樣才漸漸懂得如何而來,再回頭看數學運算及程式碼,就懂了!

CRC用了三篇來說明,一是因為它扮演著單線數位傳輸的要角,必須懂。二是三篇的過程來說明,是詳細的呈現,我是用何種方法來學習CRC,這是我的「格物」之道!僅供參考!

常見CRC的處理方式還有使用查表法的方式,優點是速度快,但會佔較多的程式碼空間,但其基本仍是依上圖所示!

至此,我們算是完成了CRC的認識及關鍵程式碼的演化程序!

下一步,將並利用它來作參數的調整!







2018年1月15日 星期一

DS18B20-認識CRC(2)

上一篇從基本的CRC認識開始,到簡化的CRC-4 計算中,各位若有依我的建議自已演練一番,應該在過程中會有所領悟,而此篇是我自已的領悟(不是最終答案,只是我自已的思路整理喲!)

CRC-4的規律

下圖是我在簡化的CRC-4中,整理出的運算規律概念圖,以其中一個運算點來呈現CRC-4碼的運算規律,我將其分為五個步驟,各位可以看看先,是否與你的規律相同(※其中A代表位元變數,可能是"1"也可以是"0")


CRC-8的規律

下圖是從CRC-4簡化後,再進行CRC-8運算,整理出的運算規律,同樣將其分為五個步驟,各位可以與CRC-4的一起比較,應可以知曉其基本運算規律相同,只是位元數較長些(※其中X/A/B代表位元變數,可能是"1"也可以是"0")


結語

到目前為止,我們都是用最笨的方式來演練CRC碼的運算,不加入數學運算原理,很笨但若是認真的演練,就能體會【熟】能生【巧】,那麼下一步是什麼?

下一步,從規律中演化出程式碼!

2018年1月13日 星期六

DS18B20-認識CRC(1)

正式進入第六步驟-CRC

上篇說明了,讀取DS18B20中暫存器之數值(共九個字元),然後呢?有兩個選擇,一是再去讀取ROM中的數值?或者,我們深入的探究暫存器中的關鍵值-CRC?前者是讓單pin可連接多個DS18B20的關鍵,但不是此專案的目標,所以先放著。後者,才是通往本專案目標的必經之路。

簡單的來說,CRC是確認你從DS18B20讀取到的數值"於傳輸過程中沒有失真"的關鍵。

掌握了CRC,可以透過它來調整傳輸的參數設定,並能檢測數位傳輸的數值正確性,以防止「傳誤」的狀況產生。

什麼是CRC


【維基百科的解釋】
循環冗餘校驗英語:Cyclic redundancy check,通稱「CRC」)是一種根據網路資料封包或電腦檔案等資料產生簡短固定位數驗證碼的一種雜湊函數,主要用來檢測或校驗資料傳輸或者儲存後可能出現的錯誤。生成的數字在傳輸或者儲存之前計算出來並且附加到資料後面,然後接收方進行檢驗確定資料是否發生變化。(資料來源: https://zh.wikipedia.org/wiki/循環冗餘校驗)

看得懂嗎?我是看不太懂啦!但你若用"CRC"當關鍵字來搜尋相關說明,大部份好心的網友會使用"長除法"來說明如何計算並取得所需之CRC值,但說實在的,我的數學不好,他們說的很清楚,但我還是看不懂!

就我的了解CRC:CRC是透過特定的數值運算規則計算,得到的檢驗碼。在DS18B20的運用中,具體的用法就是暫存器的前八個字元值運算後的CRC碼就置於最後第九個字元。當Arduino讀取了暫存器的九個字元值,透過同樣的CRC運算方式計算前八個字元值,所得之字元值若與讀取到的CRC碼相同,代表此次讀取的資料無誤,反之,則代表此次資料讀取出現錯誤,需捨棄不用。

還是有點硬的說明,不過,沒關係,要使用CRC不見得一定要懂得數學式,我們是要懂得如何使用,而不是去透析一切,底下的影片我認為是認識CRC計算及回推"最直觀"的說明,請耐心觀看!

 YouTube上一個不錯的CRC演示


認識Dallas的CRC-8



CRC碼其實只是種驗證的方法,可依設計者所需來調整位數及算法,以滿足其精確度。上圖是維基百科中所整理常用CRC的部份,其中用紅框圈住的就是Dallas針對1-Wire bus的CRC算法。而下圖就是Datasheet中CRC的操作圖示!

將Datasheet的資料與上述的計算式整合於一起就如同下圖所示:八位元的CRC運算、箭頭是移位方向、XOR(邏輯異或)
其中,圖示中標明的XOR是什麼,其實就是位元的邏輯運算式,常用的符號及運算規則如底下所示:
XOR運算:位元值相同則為"0",相異則為"1"

CRC-8太難,從簡化版的CRC開始

觀看上述影片後,大家應該了解它的運作為何了吧!底下,我將用簡化版的CRC-4(來說明其操作步驟),重點是讓各位了解其運作的順序,用土法煉鋼的笨方法先,先會用,再從中找到規律來簡化。


CRC的練習-0-填零作業

首先,我們要進行運算的數值為"1011",而在作CRC運算前,最先的步驟就是填零,既先將空位及後四碼填值為0

CRC的練習-1-步驟細分解

填零後,就先取出第一個位元值"1"及X4值"0",先作XOR運算(相異得"1"),X2向右位移至X3,再取X1值"0",進行XOR運算(相異得"1")得X2值為1,X0值"0"再向右位移至X1,最後將"1"填入X0值中,既完成了第一步驟的運算。

CRC的練習-1-8-步驟分解

下圖是將運算步驟的圖示表,有點煩,但各位可以自行演算並參照之,很簡單的步驟,但有點煩,建議至少做1~2次。
 如上圖,重覆8次的運算結果,既可得至CRC值為"0001"

 找到規律了嗎?

我們不從數理中去說明,直接用最笨的方法,來作位元的運算及操作,這就是電腦的操作程序,從簡化的例子運算中,若你做過2次以上,那麼你會發覺,CRC運算是十分簡單的步驟,但就是有點煩。簡單是因為規則是別人訂的,我們只要照著操作,就是了。就是步驟很煩,一不小心就會出錯。

下一步,我們就要從CRC的運算中找出規律,再寫程式由電腦來做這簡單又煩雜的工作!