# 重做 quiz1，並完成延伸題目
contributed by < `type59ty` , `littlepee` >
###### tags: `sysprog2018`
## 測驗 `1`
考慮以下程式碼:
```C
int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3 OP4 y); }
int main() {
int x = 3, y = 5;
return my_xor(x, y);
}
```
`my_xor` 嘗試不用 XOR 運算子做出等效的 XOR 運算，其中 OP1, OP2, OP3, OP4 都是 operator，請補完實作。
OP1 = ==&==
OP2 = ==~==
OP3 = ==|==
OP4 = ==~==
## 解題思路
題目要求做出 xor 等效運算，所以可以從邏輯閘的角度去想，用 and, or gate 組出 xor gate
xor 真值表如下
| A | B |$A \oplus B$|
|--|--|---|
| 0 | 0 | 0|
| 0 | 1 | 1|
| 1 | 0 | 1|
| 1 | 1 | 0|
根據真值表寫成布林代數表示式：$A \oplus B$ = $\overline{\rm A}B + A\overline{\rm B}$
:::info
運用 [demorgan's law](https://zh.wikipedia.org/wiki/%E5%BE%B7%E6%91%A9%E6%A0%B9%E5%AE%9A%E5%BE%8B) ，可以對原本的 xor 做等效電路
:::
簡單來說： **先相乘再反相 ＝ 先反相再相加，先相加再反相 ＝ 先反相再相乘**
- 而反相再反相，不會改變原本電路
$\overline{A}B + A\overline{B}$ $=$ $\overline{{\overline{\overline{\rm A}B + A\overline{B}}}}$
$=$ $({\overline{\overline{\overline{A}B})({\overline {A\overline{B}}}}})$
- 再根據 demorgan's law ，將第一個 bar 後面的 A,B 化成
$=$ ${(\overline{A+\overline{B}) (\overline{A}+B})}$
- 將裡面的 A,B 乘開
$=$ ${(\overline{\rm \overline{A}.\overline{B}) + (AB})}$
- 最後再將第二個 bar 後面化成
$=$ $(A+B) (\overline{A}+\overline{B})$
- 所以原本的 xor： $\overline{\rm A}B + A\overline{\rm B}$ 可以等效化成 $(A+B) (\overline{\rm A}+\overline{\rm B})$
補上測試程式碼:
```C
#include <stdio.h>
int my_xor(int x, int y) { return (x | y) & (~ x | ~ y); }
int main() {
int x = 3, y = 5;
printf("xor(%d, %d) = %d\n", x, y, my_xor(x, y));
return 0;
}
```
測試結果:
```shell
$ gcc -o test_xor test_xor.c
$ ./test_xor
xor(3, 5) = 6
```
---
## 測驗 `2`
parity (check) bit 可翻譯為「奇偶校驗位元」或「同位檢查位元」，常見於降低資料傳輸的錯誤。在資料傳送出去前，先在資料原有位元額外加上一個 parity bit，再將 parity bit 與資料的位元所組成的位元傳送出去，待接收完畢後，就檢查看看是否有奇數個 `1` 或偶數個 `1`，以判斷有無發生錯誤。
parity bit 有兩種類型：
* 偶校驗位 (even): `1` 的個數加起來須為偶數個
* 奇校驗位 (odd): `1` 的個數加起來須為奇數個
範例 1:
* 輸入: 254
* 輸出: odd parity
* 解釋
* 254~10~ 的二進位表示為 `11111110`，其中共有 7 個 `1`，奇數個
範例 2:
* 輸入: 1742346774
* 輸出: even parity
同位元檢查已經廣泛地應用到電腦的主記憶體，其優點是只要利用 XOR 或 NOT，就能製造成硬體；缺點則是無法更正錯誤，也無法偵測到所有錯誤，一旦接收到的位元圖樣同時有偶數個 (2, 4, 6, ...個) 位元錯誤，就偵測不到錯誤，因為在這種情況下，`1` 的個數仍舊會維持奇數個或偶數個。
考慮到以下判斷 parity bit 的程式碼
```cpp
#include <stdio.h>
/* Generate look-up table while pre-processing */
#define P2(n) n, n ^ 1, n ^ 1, n
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)
/* LOOK_UP is the macro expansion to generate table */
unsigned int table[256] = { LOOK_UP };
int parity(int num) {
/* Number is considered to be of 32 bits */
int max = 16;
// Dividing the number into 8-bit
// chunks while performing XOR
while (max >= 8) {
num = num ^ (num >> max);
max /= N;
}
// Masking the number with 0xff (11111111)
// to produce valid 8-bit result
return table[num & 0xff];
}
int main() {
unsigned int num = 1742346774;
/* Result is 1 for odd parity, 0 for even parity */
int result = parity(num);
printf("%s parity\n", parity(num) ? "odd" : "even");
return 0;
}
```
補完程式碼。
N = ==2==
### 解題思路
下圖為 num 變化的過程， parity check 的原則就是將所有 bits 之間作 xor 運算
(0 ^ 1 ^ 2 ^ ... ^ 31 )，所以這邊 while 裡面做的就是讓所有的 bits 作 xor ，結果最後會集中到 LSB
```clike
int max = 16;
while (max >= 8) {
num = num ^ (num >> max);
max /= 2;
}
```
以下用 8 bit 當作例子，相連的字母代表 `xor` 運算， `*` 代表 don't care ，可以看到最後結果會集中到 LSB
```
a b c d e f g h
a b c d
------------------------------------------------------------- xor
* * * * ae bf cg dh
* * * * ae bf
------------------------------------------------------------- xor
* * * * * * aceg bdfh
* * * * * * aceg
------------------------------------------------------------- xor
* * * * * * * * abcdefgh
```
:::warning
延伸題目: 解釋和實作循環冗餘碼 (CRC) 程式碼
:::
### 循環冗餘碼 (CRC)
- [循環冗餘校驗 - 維基百科](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E6%A0%A1%E9%A9%97)
- [[教學] CRC(循環冗餘碼)長除法](http://oilcut123.pixnet.net/blog/post/354497867-%5B%E6%95%99%E5%AD%B8%5D-crc%28%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E7%A2%BC%29%E9%95%B7%E9%99%A4%E6%B3%95-%E6%95%99%E4%BD%A0%E5%A6%82%E4%BD%95%E7%AE%97crc%E9%95%B7)
- [CRC Series, Part 3: CRC Implementation Code in C/C++](https://barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code)
- [最通俗的CRC校驗原理剖析](http://blog.51cto.com/winda/1063951)
### 基本介紹
CRC 是兩個位元組資料流採用 [modulo 2 division](https://www.geeksforgeeks.org/modulo-2-binary-division/)（沒有進位，使用 XOR 來代替減法）相除所得到的餘數。
假設資料位元為: $\ x^7+x^5+x^3+x$ ( $1010\ 1010$ )
產生的多項式為: $\ \ \ \ x^4+x^2+x^1+1$ ( $10111$ )
由於產生多項式 $x^4+x^2+x^1+1$ 的羃次為 4 (最高 $x^4$)，故先在資料位元 $1010\ 1010$ 的後面加上四個 0 得到 $1010\ 1010\ 0000$
以長除法求取 $1010\ 1010\ 0000$ 除以生成多項式 $x^4+x^2+x^1+1$
($10111$) 的餘數
CRC 使用 [modulo 2 division](https://www.geeksforgeeks.org/modulo-2-binary-division/)，不能化為十進位做減法運算，相減時規則為：
$1-1=0$
$0-0=0$
$1-0=1$
$0-1=1$
等同XOR運算 數字相同為 0，相異為 1
| A | B |$A \oplus B$|
|--|--|---|
| 0 | 0 | 0|
| 0 | 1 | 1|
| 1 | 0 | 1|
| 1 | 1 | 0|
CRC 碼為上述所求出的餘數 $1100$，而完整訊息則是在原始的資料位元
$1010\ 1010$ 後面加上 CRC 碼 $1100$ ，得到 $1010\ 1010\ 1100$ ，只要收訊端有正確的接收到訊息，該資訊將能被產生的多項式整除 (餘數為零)。
- 常用的 CRC
|名稱 | 多項式 |表示法|
|--|--|---|
| CRC-1 | $x+1$（用途：硬體，也稱為奇偶校驗位）| 0x1 |
| CRC-8 | $x^8+x^7+x^6+x^4+x^2+1$ | 0xD5|
| CRC-12 | $x^{12}+x^{11}+x^3+x^2+x^1+1$（用途：通訊系統） | 0x180F|
| ... | | |
### 原理分析
CRC是基於[有限域](https://zh.wikipedia.org/zh-tw/%E6%9C%89%E9%99%90%E5%9F%9F)GF(2)的多項式環 (除以2的同餘)，所有係數皆為 0 或 1 的多項式係數的集合，並且集合對於所有的代數操作都是封閉的，例如：
$x^3+2x+1$ 等價於 $x^3+1$
> $2x$ 的部份因為除2同餘的關係被消除了。
同樣可以對多項式作除法並且得到商和餘數
例如，如果用 $x^3 + x^2 + x$ 除以 $x + 1$ ，會得到：
$\frac{(x^3+x^2+x)}{(x+1)} = (x^2+1)-\frac{1}{(x+1)}$
移項一下
$(x^3+x^2+x)=(x^2+1)(x+1)-1$
等價於：
$(x^2+x+1)x=(x^2+1)(x+1)-1$
這裡除法得到了商 $x^2 + 1$ 和餘數 -1，因為是奇數所以最後一位是 1。
字串中的每一位其實就對應了這樣類型的多項式的係數。為了得到CRC，我們首先將其乘以 $x^n$，這裡 n 是一個固定多項式的階數，然後再將其除以這個固定的多項式，餘數的係數就是CRC。
在上面的等式中， $x^2+x+1$ 表示了本來的資訊位是 `111` ， $x+1$ 是 CRC 的==鑰匙==，最高次為 1，所以將原來的資訊乘上 $x^1$ 得到 $(x^3+x^2+x)$，可視為原來的資訊位補1個零成為 `1110`。
一般來說，其形式為：
$M(x)\cdotp x^n=Q(x)K(x)-R(x)$
這裡的 $M(x)$ 是原始的資訊多項式，$K(x)$ 是 n 階的 CRC==鑰匙==多項式， $Q(x)$ 為商， $R(x)$ 為餘
$M(x)\cdotp x^n$ 表示了將原始資訊後面加上 n 個 0， $R(x)$ 是餘數多項式，即是 CRC 的「校驗和」，在通訊中，發送者在原始的資訊資料M後附加上 n 位的 R（替換本來附加的0）再發送。
接收者收到 M 和 R 後，檢查 $M(x)\cdotp x^n+R(x)$ 是否能被 $K(x)$ 整除。如果是，則接收者認為該資訊是正確的。
其中 $M(x)\cdotp x^n+R(x)$ 就是發送者所想要發送的資料，也稱作 **codeword**。
### 實作
以下為 CRC-8 的程式碼實作
```cpp
#include <stdio.h>
#define POLYNOMIAL 0xD5
unsigned int crc8(unsigned int message) {
unsigned int remainder;
remainder = message;
for (unsigned int bit = 0; bit < 8; ++bit) {
if (remainder & 0x80)
remainder ^= POLYNOMIAL;
remainder = (remainder << 1);
}
return (remainder >> 4);
}
int main() {
unsigned int data = 0x56;
unsigned int crc = crc8(data);
printf("Input data: %x\n", data);
printf("CRC code : %x\n", crc);
}
```
輸出結果：
```shell
$ gcc -o crc crc.c
$ ./crc
Input data: 56
CRC code : c
```
說明：
* 一開始定義產生多項式 (除數) 為 0xD5 ，跟 input data (被除數) 0x56 做 [modulo 2 division](https://www.geeksforgeeks.org/modulo-2-binary-division/)
* 若被除數之 MSB 為 `1`，就執行運算，並且每次將餘數左移 1 bit，至多 bit length 次，最後取 remainder 前 4 bits 為回傳值，這個值即是上述分析所提到的 CRC 的「校驗和」，這個值會被附加在 input data 之後 ( $M(x)\cdotp x^n+R(x)$ )，即上述的 **codeword**。
* 將 codeword 除以 CRC 多項式，若餘數為 0 代表傳送的資料正確，否則錯誤，此例中 0x56c $\div$ 0xD5 餘數為 0 代表結果正確
Sign in with Wallet
Connect another wallet