# 2024q1 Homework6 (assessment)

contributed by <`Willsonbo`>

## M06: integration(二)

### 大數法則與資訊熵
1. **Shannon Entropy**：
Shannon Entropy **H(S)** 用來量化一組資料的平均資訊量。它描述了資料中內在的不確定性或隨機性。公式為：
$$ H(S)=−∑ i ​ P(s i ​ )logP(s i ​ ) $$
其中 $P(s_i)$ 是字元 $s_i$ 出現的概率。
2. **大數法則**：
大數法則指出，當重複多次實驗時，結果的平均值會趨近於期望值。在資訊理論中，這表示當處理大量資料時，實際出現的概率分佈會趨近於理論分佈 。
### 資料壓縮中的應用
**高概率集合**：
當我們尋找壓縮後錯誤概率小於 $\epsilon$ 的字串集合時，我們需要找到那些高概率出現的字串。這些字串被稱為$\epsilon$-高概率集合。

**壓縮比例**：
根據 Shannon 的理論，這樣的字串集合的總位元數約為 $2^n \cdot H(S)$。其中，$n$ 是原始字串的位元數。這表示如果原始字串長度為 $n$，則可以按照 Entropy $H(S)$ 的壓縮比例進行壓縮。壓縮比例為 $H(S)$，意味著壓縮後的位元數將大約是原始位元數的 $H(S)$ 倍。

### 總結
- **高概率集合**：識別那些總出現概率高的字串集合，使壓縮後的錯誤概率小於 $\epsilon$。
- **壓縮結果**：總位元數為 $2^n \cdot H(S)$，壓縮比例為 $H(S)$，即資料越隨機（熵值越高），壓縮後所需位元數越多；資料越有規律（熵值越低），壓縮效果越好。
這意味著資料壓縮的效果取決於資料的熵值，熵值越高，壓縮率越低，反之亦然 。
假設我們有一個長度為 1000 位元的字串，經過分析得出其 Shannon Entropy 為 0.5。根據壓縮理論，我們可以預期將此字串壓縮到約 500 位元（即 1000 位元 * 0.5）。這樣，資料壓縮後的錯誤概率小於$\epsilon$，而壓縮效率達到最佳 。
當資料中每個隨機變數的機率與平均值差異越大，代表資料符合特定規律，資料的熵越小，我們可以用較少的位元表現這些資料，並用這些規律壓縮資料。

Fibonacci LFSR的實作是利用一個移位寄存器和異或門（XOR gates）來產生一個長度為 \(2^n - 1\) 的最大長度序列。以下是Fibonacci LFSR的實作說明：

1. **移位寄存器：**
- 移位寄存器是一串可以存儲和移動位元的記憶體元件。在Fibonacci LFSR中，每一個位元在時鐘信號的驅動下會向右移動一位。

2. **抽頭回授：**
- 在Fibonacci結構中，特定位置的位元會通過異或門反饋到移位寄存器的輸入端。這些特定位置稱為抽頭（tap）。例如，如果我們使用多項式 $x^5 + x^3 + 1$，則代表在第5位和第3位設置抽頭。

3. **XOR運算：**
- 每次移位操作前，抽頭位的位元會進行異或運算，結果作為新的位元輸入到移位寄存器的最高位（左端）。

4. **具體實作：**
- 設定初始值：將寄存器初始化為一個非零值。
- 每次時鐘脈衝：
- 進行異或運算計算新的位元。
- 將移位寄存器右移一位。
- 將新位元輸入到最高位。

以下是一個簡單的C語言實作範例：

#include <stdint.h>

void fibonacci_lfsr(uint64_t *reg) {
    uint64_t taps = ((*reg >> 5) ^ (*reg >> 3) ^ (*reg >> 2) ^ (*reg >> 0)) & 1;
    *reg = (*reg >> 1) | (taps << 63);
}

在這個範例中，我們使用了抽頭位5, 3, 2, 和0。每次調用函數時，寄存器會右移一位並將計算得到的新位元填入最高位。

:::danger
注意用語！
避免直接填入 ChatGPT 的內容。
:::

static u_char __init get_hw_addr(struct net_device *dev, u_char * eeprom_image, char chipType)
{
	int i, j, k;
	u_short chksum;
	u_char crc, lfsr, sd, status = 0;
	u_long iobase = dev->base_addr;
	u16 tmp;

	// 如果芯片類型是 LeMAC2
	if (chipType == LeMAC2) {
		// 初始化CRC值為0x6a，並遍歷以太網地址長度（ETH_ALEN，一般為6）
		for (crc = 0x6a, j = 0; j < ETH_ALEN; j++) {
			// 從 EEPROM 中讀取硬件地址的一個字節，並存儲在設備的 dev_addr 中
			sd = dev->dev_addr[j] = eeprom_image[EEPROM_PADDR0 + j];
			// 將這個字節寫入網絡卡的參數寄存器
			outb(dev->dev_addr[j], EWRK3_PAR0 + j);
			// 更新 CRC 值，對該字節的每一位進行計算
			for (k = 0; k < 8; k++, sd >>= 1) {
				// 計算LFSR（線性反饋移位寄存器）值
				lfsr = ((((crc & 0x02) >> 1) ^ (crc & 0x01)) ^ (sd & 0x01)) << 7;
				// 更新 CRC
				crc = (crc >> 1) + lfsr;
			}
		}
		// 如果計算出的 CRC 與 EEPROM 中存儲的不一致，設置狀態為 -1 表示錯誤
		if (crc != eeprom_image[EEPROM_PA_CRC])
			status = -1;
	} else {
		// 初始化 i 和 k
		for (i = 0, k = 0; i < ETH_ALEN;) {
			// k 左移一位
			k <<= 1;
			// 如果 k 大於 0xffff，減去 0xffff
			if (k > 0xffff)
				k -= 0xffff;

			// 從 APROM 讀取一個字節並加到 k
			k += (u_char) (tmp = inb(EWRK3_APROM));
			// 將讀取到的字節存儲到設備的 dev_addr 中
			dev->dev_addr[i] = (u_char) tmp;
			// 將這個字節寫入網絡卡的參數寄存器
			outb(dev->dev_addr[i], EWRK3_PAR0 + i);
			i++;
			// 從 APROM 再讀取一個字節，並將它的高8位加到 k
			k += (u_short) ((tmp = inb(EWRK3_APROM)) << 8);
			// 將讀取到的字節存儲到設備的 dev_addr 中
			dev->dev_addr[i] = (u_char) tmp;
			// 將這個字節寫入網絡卡的參數寄存器
			outb(dev->dev_addr[i], EWRK3_PAR0 + i);
			i++;

			// 如果 k 大於 0xffff，減去 0xffff
			if (k > 0xffff)
				k -= 0xffff;
		}
		// 如果 k 等於 0xffff，將 k 設為 0
		if (k == 0xffff)
			k = 0;
		// 從 APROM 讀取兩個字節組成校驗和
		chksum = inb(EWRK3_APROM);
		chksum |= (inb(EWRK3_APROM) << 8);
		// 如果計算出的 k 與校驗和不匹配，設置狀態為 -1 表示錯誤
		if (k != chksum)
			status = -1;
	}

	// 返回狀態
	return status;
}