回分類題庫
d042: 2.循環冗餘檢查CRC
關鍵字: 100年台中區複賽

測資點 : 2 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 75 Times / 73 Users | Submit : 204 Times / 74 Users | Accepted rate : 99%
題目加入時間 : 2012-07-06 14:42

Content: 简体中文

循環冗餘檢查CRC(Cyclic Redundancy Check)是網路通訊中一種常見的傳輸錯誤檢查技術。 CRC的計算方式是將待傳輸的資料區塊視為一堆連續位元所構成的一整個數值,並將此數值除以一特定的除數,兩數相除後得到的餘數即為循環冗餘檢查碼(CRC code),除數值的位元數目視欲得到的循環冗餘檢查碼的位元長度而定,目前較常使用的CRC code位元長度有 8、16及32。傳送方會將計算所得的循環冗餘檢查碼附在待傳資料之後一併送出,當接收方收到資料後以相同方式計算CRC code,比較收到的循環冗餘檢查碼與自己計算的循環冗餘檢查碼是否相同,便可以判斷出資料在傳輸過程中是否遭到干擾而產生錯誤。

在CRC運算中我們稱除數(或Divisor)為poly,而寬度W就是poly最高位的位置。例如poly 1001的W是3,而不是4,請注意poly最高位總是1。假如我們想計算一個資料區塊的CRC code,並要保證每一位元都要被處理,因此我們需要在資料區塊後面加上W個0。CRC計算與普通的除法計算有所不同。普通的除法計算是借位相減的,而CRC計算則是互斥或(XOR)運算。以下面例子展示CRC算法的過程,請注意每個除法步驟的細節,此例中待傳輸資料為11110後面補上W(=3)個0,而poly(或除數)為1011,計算得到的餘數(Remainder)則做為待傳輸資料的CRC code,此例為101。

Input:

第一列有一正整數N表示測試資料組數
接下來有N組資料,每一組資料內容如下:
第一列有一個二元字串代表待傳資料(被除數)
第二列有一個二元字串代表poly(除數)

Output:

依資料組數分別輸出一個代表CRC code (餘數)的二元字串。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
10111
1011
11110
1011

Sample Output :

CRC code:011
CRC code:101

Hint :

Author :

100年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum