# 2024q1 Homework5 (assessment)
contributed by < [chihen0709](https://github.com/chihen0709) >
## 測驗題之改進

## 〈因為自動飲料機而延畢的那一年〉及 前五周課程 的啟發及心得
### 前五周課程之心得
先跟老師說聲抱歉，因為我不夠強，沒辦法跟著老師的進度走，前陣子因為論文被換題目，那一個多月都在應付指導教授所要求的進度，所以沒辦法將前幾周的課程教材和作業全數研讀完畢及做出相應的實作，目前是跟到約第三周的教材及課程，應會先將 `homework2` 及 `lab0-c` 實作程式碼及共筆於近期完成，目前跟到第三周快第四周的心得是:我一開始就知道這一門課會相較老師上學期開的計算機結構還要精實，我卻異想天開只需要付出計算機結構所花費的時間，就還能得到一些還行的成果，但這個想法根本就是不可行的，在第一周至第六周這種高強度的課程下，突然有種深深的絕望感，因為教材十分多，光是觀看講解的錄影跟教材就所耗時間不少加上要撰寫作業並且補足許多我未曾了解的資料結構以及演算法，都是耗費我許多時間的過程，加上中途被換題目那種深深的無力感，令我前陣子有想說退選這門課程，但仔細想想老師第一周的大綱就是誠實面對自己，我選修了這門課卻沒有好好的面對自己來學習這門課，老師所教的都是在刷新我原本對於 `C` 語言程式設計的認知，每份教材好好拜讀完成後才知道自己對於計算機科學領域是一無所知，一開始寫 `lab0-c ` 時前幾個函式還可以慢慢想出來，一牽扯到自己沒學過的演算法就卡關，去參照過往學長的實作以及觀看同學們的共筆和在 `Github `的提交，總是讓我很焦慮，為何程式流程規劃以及演算法跟資料結構都這麼精簡以及有效率，本來想說就此放棄，但還是先將 `lab0-c` 的最基本要求做完，轉而去應付換題目的窘境，看著同學們一直在臉書社團提問以及更新，總覺得自己離他們很遠，但就如同老師所說的誠實面對自己，或許我可能沒辦法做到那些強者同學們的程度，但我想通過這門課程更加了解 `C` 語言程式設計 以及作業系統相關的知識，並且最好能做出一個嵌入式系統的小專案是我在這門課程的目標，或許沒辦法像同學們真正提交 `patch` 至 `linux kernel` 但還是能從這門課學到一些我能帶走的東西，就如同老師上學期期末專案對我們所說的話就是希望我們能從這堂課學到一些東西並且能帶得走的，雖然我知道自己 `C` 語言超級不熟練、看 `linux kernel` 的程式碼一知半解、看英文規格書看得霧煞煞，但我還是會繼續跟完剩餘的課程，直至我離開成功大學，記得老師從課程一開始就一直跟我們講的事情：「要誠實面對自己。」，正是因為可以誠實面對自己，才可以坦然接受失敗，再從失敗中改進並且學習。

### 〈因為自動飲料機而延畢的那一年〉研讀心得
文章中提及
> 「資工系的學生不會寫程式，機械系的學生不會做機械」

這其實說明了硬體跟軟體以及物理現象的世界是不太一樣的，本身是土木輔機械背景出身的，那時候因為對實作結構力學相關的硬體物件感到沒有興趣，而去輔修機械系的課程，這樣大學四年下來，我除了基本的 `CNC` 和鑽床之外對於機械加工的設計以及製造還是不甚了解，到了研究所以為在頂尖大學的機械類科至少會將基本的機械加工及製造教完，但其實不然很多時候都是我們這些助教來去帶著學弟妹甚至幫他們實作完成，畢竟機械工廠機台有限，要帶完整個系上大一的學生基本上是不太可能的，所以這就導致他們對於機械加工以及製造是不太了解的，對於我們研究所使用的工件往往都是送去外面工廠做機械加工，那等待時間十分漫長，並且常常會有做出來的機械工件是不符合公差的，直接導致加工成本浪費，而明明是需要透過硬體實作的我們卻常常使用計算機輔助設計後送出去的工件以及物件背後的結構行為或是動力行為不甚了解，甚至也不太了解為何使用微控制器控制那些機器的控制理論，只覺得電腦跑來結果是可行的就直接去用並沒有透過理論或其他方式驗證，而對於資工系的學生們可能有更多可以幫忙程式碼除錯以及開發網路、演算法、數位積體電路、人工智慧，但過度依賴工具而不去了解背後的數學背景以及程式碼運作的原理，常常會有 `garbage in garbage out` 的情形，可能跑出來的結果是對的，但其效能是不符合我們所預期的效果，這告訴了我們不管是做硬體還是軟體方面的工作，都必須去了解其背後的原理以及動手做做中學這個道理。

>「你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望 … 你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」

這段話給我的啟發不亞於老師常常對我們說的:「誠實面對自己」，我個性是相較於其他較愛玩耍且沒這麼自律的個性，如果不是選修老師這門課，或許我連老師的教材點開的勇氣可能都沒有，我很怕面對失敗，雖然從一直失敗是我的常態，失敗也是一直我成長的基石和動力，但對於這門課程我總害怕失敗，我對於不熟悉的程式碼或是演算法或是實作，每次看到他們的描述總會覺得力不從心，心裡有開始害怕的感覺，並不是對於開發程式碼或是照著老師的共筆做實驗而感到害怕，而是想說是否能像其他人一樣達成老師的作業要求以及品質，進而有時候會不想面對自我的進度無論是實驗以及課程的，但拜讀完這篇文章後，對於來說有個啟發，就是失敗其實沒什麼，無論對於強者抑或者是我這種普通人，都會有失敗的時候，如果我因為這幾次的挫折而去放棄學習及更加了解 `C` 語言程式設計和其背後的行為，我甚至連理解嵌入式系統或者自己開發程式的所有背後知識的機會都沒有，雖然前幾周課程進度不盡人意，但透過這幾周帶來的失敗及挫折感讓我更加了解其實坦然面對失敗沒什麼，只是在於自己是否還有前進的勇氣跟膽識。

## 研讀第 1 到第 6 週「課程教材」和 CS:APP 3/e 之啟發及心得
### 解讀計算機編碼/你所不知道的 C 語言:浮點數運算及數值系統篇
對於做計算流體力學的我來說，因為計算流體力學不僅僅只是用計算機去模擬流場問題，其背後橫跨的學科就我所知就有:流體力學、偏微分方程、數值分析、資料處理、計算機科學和拓樸學等學科，故常常接觸到背後一些數值的技巧以及方法，如果不去了解背後的演算法及數值方法是如何由數學構思並且開發的話，常常會建構出不符合物理及流場問題的計算模型，往往會導致解的可用性及穩定性和收斂性非常之糟糕，因為是使用 `linux-based` 的計算軟體不外乎基本的 `shell` 命令和資訊都要有一定的了解，常常因為數值震盪過大而導致計算過程停止迭代及平行運算，所耗費的計算成本是過於龐大的，但往往錯誤訊息都是會出現浮點數異常，常常去查看論壇前人們的討論，都不外乎是不符合數值條件以及物理問題，透過這三份教材以及老師所講解的影片，能讓我更了解我當時在計算機結構所沒所能完全了解的數值編碼以及其知識，雖然是都是因為解的不穩定性以及收斂性而導致數值計算的結果發散，但透過教材能了解，或許就是因為數值震盪過大而導致計算機無法去處理那些變化過大的數值又或者在計算的時候出現了 `NaN` 導致在計算過程而報錯，透過學習能更加確定背後出錯的原因，並且可以去查看計算軟體背後的開源程式碼，來去了解為何其出現某個值計算結果會導致其發生異常，也透過學習了解一些群的相關知識，詢問教授才知道，其實群論也常常用於我們計算流體力學領域的求解方法裡，例如:李代數、李群等都是數學應用在計算流體力學上的應用。

### 你所不知道的 C 語言:指標及鏈結串列篇(要再次拜讀)
對於指標大家都是唯恐避之不及的一個概念，總常常在論壇看人談起指標都說是學習 `C `語言程式設計的一個門檻，透過老師的講座刷新了我對於指標那粗淺的理解，以為就是普通的 `C` 語言之特性，用來指向記憶體位址而已，但一開始搭配老師的講解錄影以及共筆卻發現自己對於指標的認知過於膚淺，對於指標的基礎用法以及指標的指標或是函式指標的概念都沒有這麼清楚，第一周拜讀完指標篇讓我可以更好的理解下一篇你所不知道的 `C` 語言鏈結串列篇，沒想到再次刷新我的認知，原以為能實作出這種基礎的資料結構就已經還不錯了，但在 `linux `核心大量使用鏈結串列來去連結所需要的操作，對於這種用法刷新了我對鏈結串列應用的認知，並且透過實例的操作讓我們更加熟稔鏈結串列的概念。

### 閱讀錯誤更正碼(Error-Correcting code)的啟發以及疑惑
錯誤更正碼的概念常用通訊理論中，而其中最簡易明瞭的是 (7,4) Hamming code ，真實資料只有4個位元的資料剩餘三個位元是當作 parity 用來修正及檢查錯誤的資料，但最多只能修正一位元的錯誤資料。

:::info
為何 Hamming code 中 x 與 y 的 Hamming distance 會等於 $x+y$ 的 NonCarryIn 的 hamming weight ? 是因為真實資料只有四位元而總共資料長度為七位元如果採用 CarryIn 的加法會讓其從 0100 + 1100 = 10000 (1會 overflow 導致其 Hamming weight 計算出與 x 和 y 的Hamming distance 不同。
:::

其中提到了 $d_{min}C=min{d_H(x,y)|x,y\in C,x \ne y}$ ，定義了 codeword 集合中任兩個編碼的最小 Hamming distance 而對於 d 個資料錯誤的位元其 mimimum Hamming distance 為`2d+1` 所以對於這個 Hamming (7,4) code 演算法只能修正一個位元的錯誤。

#### Reed-solomon codes
屬於 BCH code 其中之一的演算法，對於這些背景知識還不夠熟稔，有找了一本 ECC 相關數學原理以及演算法實作的書籍 [Error Correction Coding Mathematical Methods and Algorithms ](https://www.semanticscholar.org/paper/Error-Correction-Coding%3A-Mathematical-Methods-and-Moon/85c582be5fab1e6315164ce9b68c079ea5a8e1bc)
其中的 BCH code 的理論以及實作是在較後面的章節才會開始實作，我應會從前面的章節慢慢往後推薦讀至 BCH code，閱讀這篇文章有發現自身本來沒有的概念以及疑惑，後續會一一列出，而對於要實作 Reed-solomon codes的前提是必須了解其數學背景，這個演算法的概念是應用於 伽羅瓦域也就是 Finite Field 中的 symbol中，其中 Primitive element $\alpha$ 的意義是代表這個 field 裡所有數值可以被表示非 0 且不重複的。
:::info
為何 Reed-solomon codeword的 編碼會定義為 $s(x)= M(x)x^m-[(M(x)x^m) mod g(x)]$ 是因為不需要讓 $M(x)x^m$ 有計算的互動嗎?
:::
:::info
在 Peterson-Gorenstein-Zierler decoder 中的
\begin{equation}
\begin{bmatrix}
\alpha^{0\times 0} & \alpha^{1\times0} &... & \alpha^{(n-1)\times 0} \\
\alpha^{0\times 1} & \alpha^{1\times1} &... & \alpha^{(n-1)\times 1} \\
\alpha^{0\times 2} & \alpha^{1\times2} &... & \alpha^{(n-1)\times 2} \\
...\\
\alpha^{0\times(m-1)} & \alpha^{1\times(m-1)}&... &\alpha^{(n-1)\times(m-1)}
\end{bmatrix} \cdot
\begin{bmatrix}
e_{0} \\
e_1 \\
... \\
e_{n-1}\\
\end{bmatrix} =\begin{bmatrix}
S_{0} \\
S_1 \\
... \\
S_{m-1}\\
\end{bmatrix}
\end{equation}
這個最後得出可以求解誤差項的方程因為方程組不封閉所以才需要後續猜 error loaction 的這個動作嗎? 是否還會有其他方式來讓解封閉?
:::
透過 Find error locations 的步驟我們可以定義 error locator polynomial$\lambda(x)=\prod_{i=0}^{v-1}(1-X_ix)=1+\lambda_1x+\lambda_2x^2+...+\lambda_vx^v$後續透過步驟會得到此線性系統的矩陣，透過求解此線性系統的矩陣可以得到我們 codeword 在哪裡會有錯誤，但如果此線性矩陣的解不連續或者連續但相依的則無法得到我們想要的錯誤之位置。
在 **BCH** 之 decode 中常見的演算法為 **Berlekamp-Massey algorithm** 來求出我們的錯誤碼的位置再由 **Forney algorithm** 來還原錯誤碼，兩者時間複雜度為 $\Theta(m^2)$ 而文中提到的編碼技術時間複雜度為 $\Theta(m^3+mk)$。

:::info
在 Reed-Solomon codes 常用 BCH code 來進行編碼，先檢查錯誤碼再來修正，其中我們 Finite Field 是使用 mod 256 避免溢位也稱此 Finite Field 為$GF(2^8)$ 因為 Finite Field 四則運算必須滿足交換律、結合律、分配律、封閉性、inverse、identiy等六大性質，但其中加法的實作為何不能採用 CarryIn 的加法? 是因為限制於8位元的資料長度嗎? 還是因為其滿足 $GF(2^n)$的特性才使用 XOR 來代替加減法
:::
其中在 linux 實作中 Reed-Solomon codes 時最重要的資料結構是` rs_codec `

struct rs_codec {
	int		mm;
	int		nn;
	uint16_t	*alpha_to;
	uint16_t	*index_of;
	uint16_t	*genpoly;
	int		nroots;
	int		fcr;
	int		prim;
	int		iprim;
	int		gfpoly;
	int		(*gffunc)(int);
	int		users;
	struct list_head list;
};

在前面我們會透過建立一個 generator number = 2 的 $\alpha$ 之表格來讓我們查快速查詢，假設為八位元 $\alpha^0$ ~ $\alpha^255$ 都不會有重複值因為這個是 Galois Field 的特性。
:::info
但實作中不考慮 gffnuc 的使用，為何 $\alpha$ 會設定為 2 是因為我們是一切的前提建立在$GF(2^n)$上面嗎 會不會有其他的 primitive element?
:::
在 linux 中 [linux/include/linux/rslib.h](https://github.com/torvalds/linux/blob/0fe5f9ca223573167c4c4156903d751d2c8e160e/include/linux/rslib.h)可以看到許多函式的實作方式，但不太了解其中 gffnuc 和 iprim 的意義。
:::info
在取餘運算 `rs_modnn` 中， Mersenne Number的概念不太熟悉，應待找數學証明來去釐清概念。
:::
:::info
在文章最後 `decode_rs8` 的實作中，對於 error+erasure locator polynoimal 求根時為何會使用 Chien serach 來去求根?而不是使用 Honer Method 來去求根，因為前者時間複雜度為$O(n^2)$ 後者為 $O(NlogN)$。
:::

### CS:APP 3/e

:::danger
command 是「命令」，而非「指令」(instruction)，注意細節！
> 已修正，謝謝老師
:::

## 簡述你想投入的專案及規劃
### Prerequisite
**TODO:**
> 1. 先將課程教材研讀完畢至第七周，並且完成 `lab0-c(include homework3)` 和 `homework2、4` 之作業實作，並且將後續的考試題目撰寫完成，後續再實作專案。
> 2. 補足資料結構及演算法和作業系統之背景知識。
> 3. 拜讀[並行程式設計: 概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)、[現代處理器設計：原理和關鍵特徵](https://hackmd.io/@sysprog/cpu-basics)、[Demystifying the Linux CPU Scheduler](https://)等相關文章

### 有興趣的專案
未來想做嵌入式的韌體工程師，因為動手實作並且能驅動裝置，是我十分嚮往的產業，在碩二上才確定往兩方發展一方面是熱流工程師，另一方面是嵌入式韌體工程師，對於嵌入式韌體工程師的方向，雖然有點功利導向及自不量力，但如果能開發用於 `Aerospace` 或是開發某產品給予社會大眾使用或許也是一種貢獻，再煩請老師幫我挑選適合我的專案後續會再跟老師約時間討論。

:::danger
修正下方無效的超連結。
"for example" 簡稱是 "e.g."，而非 "ex"
> 已修正，謝謝老師。
:::

1.[在 RISC-V 處理器運作 Linux 核心 (FPGA/虛擬機器)](https://)

> * 透過在計算機結構所學習的 `RISC-V` 組合語言及自己目前在學的 `HDL` 來去將 `Linux` 核心運行在 `FPGA` 開發版上。
> * Prerequisite:必須先將組合語言跟計算機結構複習並參考前人文章實作。
> 2023執行人:[Chiwawachiwawa ](https://hackmd.io/@sysprog/B1Jl_HlBn)
2022執行人:[fennecJ](https://hackmd.io/@sysprog/S1jNiYgr2)
[從零開始的RISC-V SoC架構設計與Linux核心運行 - 硬體篇](https://hackmd.io/@w4K9apQGS8-NFtsnFXutfg/B1Re5uGa5)

2.嵌入式相關的作品(e.g: linux driver for MCU or Embedding system for Aeronautics and Astronautics )
> * 自身想將課堂學習結合自身領域來實作嵌入式系統。
> * 未來想學習嵌入式相關的實作，但首要還是先把 C 語言程式設計達到一個可以應用的標準，並切嘗試開發嵌入式系統運用於實驗室未來計畫的電路開發(目前是應用於衛星的電磁閥，或許可以嘗試開發取代學弟開發的版本(優化程式碼及簡化其邏輯電路或者類比電路)或者是自鎖閥)，又或者是可以將這種 `MCU` 或 `FPGA` 應用在我們火箭的姿態控制或者控制點火時間上。

---

TODO: 理解 Documentation/core-api/librs.rst 用法
TODO: 準備 Linux kernel module 利用 librs (參照 MTD/NAND)