Infinite Loop

【介紹】Code::Blocks

2010-09-19T14:18:00.006+08:00

為了能撰寫 C/C++ 的程式，你可能需要在自己的電腦中建置一套 IDE（Integrated Development Environment，整合開發環境），卻又不想用需要付費、又只能在 Windows 上執行的 Visual Studio（雖然 VS 也有提供免費的 Express Edition）。

　　或許會有人推薦你使用 Dev-C++ 這套 open source 的免費軟體。不過根據我自己使用過的經驗，Dev-C++ 時常在執行到一半的時候當掉。而且其最新版本 4.9.9.2 是在 2005 年 2 月發佈的，顯然已經好幾年都沒有在繼續更新。

　　在這裡，我要為各位介紹另一款同樣免費又穩定的 IDE - Code::Blocks。

　　Code::Blocks 是一個 open source 的 IDE。由於其是由 wxWidgets 寫成，因此也具備了跨多種平台（Windows、Mac OS X、Linux 等）的能力。

　　Code::Blocks 也支援多種編譯器（compiler），如常見的 GCC / MinGW、Microsoft 的 Visual C++、Intel 的 ICC 等。除此之外，Code::Blocks 還支援匯入 Dev-C++ 與 Visual C++ 專案的能力，可謂功能相當豐富。

　　在這裡簡單示範一下如何在 Windows （XP Pro SP3）下安裝 Code::Blocks。

　　首先，先進到下載頁，找到 Windows 用的 binary 版本。當前的最新版本為 10.05，提供了 "codeblocks-10.05-setup.exe" 與 "codeblocks-10.05mingw-setup.exe" 兩個安裝檔，分別為單純的 Code::Blocks 與包含 MinGW 的版本。

　　在這裡，我選擇的是不包含 MinGW 的版本。

　　下載完成、執行安裝檔後，會出現選擇安裝元件的畫面。基本上，遵照預設值，直接按 "Next" 即可。

　　接著選擇安裝的目錄。

　　接著就可以等待安裝完成了。

　　在 Code::Blocks 安裝完成之後，我們還需要安裝 MinGW 作為其使用的編譯環境。（假如在第一步下載的就是包含 MinGW，這一步可以跳過。當然，你也可以選擇 MinGW 以外的編譯環境，如 ICC。）

　　MinGW 的安裝方式請參見這篇。

　　第一次開啟 Code::Blocks 時，它會請你選擇一個預設的編譯器。後面有寫 "Detected" 的，代表 Code::Blocks 在你電腦偵測到的已安裝的編譯器。

　　這裡我們選擇 "GNU GCC Compiler"。

　　安裝到這邊，就可以開始使用 Code::Block 了！

　　想利用 Code::Block 新增一個 C/C++ 的檔案，請點選選單的 File > New > File...。

　　接著選擇 "C/C++ source"。

　　然後選擇 "C" 或 "C++"。

　　並設定檔案建立的路徑。

　　撰寫完程式，再按下工具列的 "Run" 就可以編譯執行了。

Reference:

Code::Blocks

Code::Blocks - Wikipedia

Writing C++ Application Without Visual C++

【雜記】漫談樹狀結構

2010-09-15T00:34:00.008+08:00

在之前寫的「樹（tree）」這篇文章中，有網友提到：希望能夠瞭解 tree 能夠在應用上什麼問題上面。不過，由於我本身對樹的瞭解也很粗淺，所以這篇就野人獻曝一下，隨意講講一些我知道的東西。學得不甚透徹，可能會有些不完整或是錯誤的地方，就請各位別見怪囉 :P

　　先前曾經提到：在樹狀結構中，節點（node）的分支度（degree）代表其子節點（child）數量。若是有一種樹狀結構至多只會有 n 個子節點，即樹中的任何節點分支度均小於或等於 n，則我們會將這種樹稱為一棵「n 元樹｣。

　　其中，大概就屬二元樹（binary tree）的應用最為廣泛。如上所述，其節點至多只會有兩個子節點。通常我們會直接將之稱為左子（left child）與右子（right child）。下圖是一棵二元樹：

　　在談應用之前，讓我們先來看看一個樹狀結構常見的操作：尋訪（traversal），也就是依照某種順序訪問樹中的所有節點。一般來說，常見的尋訪方式包含深度優先尋訪（depth-first traversal）與廣度優先尋訪（breadth-first traversal）。

　　以上面的樹狀圖來說明，深度優先尋訪會先從根節點 F 開始，走訪 F 的第一個子節點 B，再接著走訪 B 的第一個子節點 A。由於 A 不具有子節點，所以我們退回上一層，再接著走訪 B 的第二個子節點 D。完整的尋訪順序為：F B A D C E G I H。

　　而廣度優先尋訪相對於深度優先尋訪的不斷深入，是以層級順序（level-order）來進行尋訪。所以同樣由根節點 F 開始，走訪 F 的第一個子節點 B，再接著走訪 F 的第二個子節點 G。由於 F 只有兩個子節點，所以我們接著尋訪下一層 B 的子節點 A 與 D，然後是 G 的子節點 I。完整的尋訪順序為：F B G A D I C E H。

　　其中，二元樹又具有三種特殊的尋訪方式：前序（pre-order）、中序（in-order）、與後序（post-order）。若是把尋訪根節點、尋訪左子樹、尋訪右子樹分別記做 D、L、R，則前序的尋訪順序為 D L R、中序的尋訪順序為 L D R、後序的尋訪順序為 L R D。

　　以同樣的圖舉例的話，前序的尋訪順序為：F B A D C E G I H、中序的尋訪順序為：A B C D E F G H I、後序的尋訪順序為：A C E D B H I G F。（正確來說，二元樹只比一般的樹多了中序與後序兩種尋訪方式，因為前序尋訪與深度優先尋訪的順序其實是相同的。）

　　說完了尋訪，不過跟應用有什麼關聯呢？其中一個常見的用途是排序（sorting）。

　　我們可以定義一個特殊的二元樹：樹狀結構中，其左子樹所有節點所存的值必定小於根節點的值，且其右子樹所有節點所存的值必定大於等於根節點的值。如下圖：

　　有沒有發現，當我們用中序來尋訪這棵二元樹，我們便可以得到一個升序（ascending order）的數列。

　　若是根據定義，給出一個新增節點的操作：

Function insertNode(TreeNode root, Type value)
    If root.value > value then
        If root.hasLeftChild Then
            insertNode(root.leftChild, value)
        Else
            root.leftChild = CreateNode(value)
    Else
        If root.hasRightChild Then
            insertNode(root.rightChild, value)
        Else
            root.rightChild = CreateNode(value)
End

　　利用這個新增節點的操作，我們便可以將一堆資料建立成一棵符合定義的二元樹。於是，我們便可以利用這個操作，在加上中序尋訪來得到一串排序過的資料。

　　事實上，這種特殊的二元樹，被稱為二元搜尋樹（binary search tree）。其義如其名，這種二元樹也可以用以進行「已排序資料」的搜尋（search）。

　　根據定義我們可以得知：若是欲尋找的值小於二元搜尋樹的根節點，則其右子樹必定不可能出現欲尋找的值；同樣的，若是欲尋找的值大於二元搜尋樹的根節點，則其左子樹必定不可能出現欲尋找的值。而這種方式其實就跟二分搜尋法（binary search）的原理有異曲同工之妙。

　　我們可以定義搜尋的操作如下：

Function search(TreeNode root, Type value)
    If root.value = value then
        print "Found"
    Else If root.value > value then
        If root.hasLeftChild Then
            search(root.leftChild, value)
        Else
            print "Not Found"
    Else
        If root.hasRightChild Then
            search(root.rightChild, value)
        Else
            print "Not Found"
End

　　而這種利用二元搜尋樹的搜尋方式，其複雜度為 O(h)。其中 h 為樹的高度（height）。而若每棵子樹的左右子樹節點數量都相同（或差一），則 h 即等同於 lg n，也就是說搜尋的複雜度為 O(lg n)，與二分搜尋法相當。

　　由以上這些例子，可以知道「樹」不僅可以用來處理常見的排序與搜尋問題，還是種挺有效率的方式呢。

References：

Tree (data structure) - Wikipedia

Binary tree - Wikipedia

Tree traversal - Wikipedia

Binary search tree - Wikipedia

Tree - 演算法筆記

由樹的前序、中序、後序走法來談資料結構 - MMDays

二元樹在排序的應用 - MMDays

二元樹排序對搜尋的影響 - MMDays

【轉貼】Visualization of Quick sort

2010-07-23T21:46:00.003+08:00

偶然在網路上看到的影片：用動畫展示氣泡排序法（Bubble Sort）跟快速排序法（Quicksort）的運作原理，並比較兩者的效率（進行比較的次數）。整支影片看起來還滿可愛的。

Visualization of Quick sort

【雜記】FLOLAC '10

2010-07-11T12:21:00.009+08:00

2010 Formosan Summer School on Logic, Language, and Computation（FLOLAC ’10），是辦在台大進修推廣部的暑期碩士學分班。雖然是碩士學分班，但由於剛好符合相關學系大二以上的報名資格，又在半自願被網友 yen3 「騙來」的狀態下還是報名了XD。

　　對於一個語言，我們可以從兩個觀點來看它：一個是語法（syntax），即語言本身的規則（rule）與形式（form）；另一個則是語意（semantics），為語言本身所表達的意義（meaning）。

　　寫出可以執行的程式也許不難，要寫出正確的程式卻不簡單。當我們得到一段程式，我們該如何分析、驗證這個程式的結果，以確保其確實符合我們的預期？更甚者，我們該如何在撰寫程式的同時，也確保我們建構出來的程式一定是正確的？

　　對於程式語法上的錯誤（syntax error）可以經由編譯器（compiler）或直譯器（interpreter）來幫我們檢查出來。但是，語意上的錯誤（logic error 或稱 semantic error）卻難以經由其他工具來協助我們察覺。

　　一般我們也許習慣利用測試資料來確認程式的正確性：只要程式能通過所有的測試資料（即輸出結果符合預期），我們就可以「假設」程式是正確的了。不過，要產出全面性的測試資料本身有其難度，再加上此種方式必須仰賴於程式的實作（implement），作為驗證並不是一種非常好的方式。

　　而 FLOLAC '10 這一系列的課程，主要的內容就是教導如何以邏輯推理為基礎，從語意的角度將程式形式化（formalize）並進行分析。以及用以輔助的 Frama-C 分析工具的使用。

　　不過 FLOLAC ’10 的時程有兩天跟期末考撞期，所以一開始就請了兩天假。直到第三天的 Logic 跟 Op 課都已經是第二堂課，FP 課甚至已經結束了。要在沒聽過第一堂課的情況下銜接上內容，一開始還真是一個頭兩個大。還好後來漸漸跟上了，總算有種進入狀況的感覺。

　　歷經了兩週八點準時起床出門上課，直到下午五點下課，比暑假前還規律的暑假生活，水深火熱的 FLOLAC '10 終於順利結束了。雖然課程有點辛苦，不過接觸了不少人、也接觸了不少新東西，感覺收獲也相當多。

　　遇見了 yen3、GSR、dryman，還有其他周圍的人、努力想搞懂 Frama-C 到底在做什麼、跟 dryman 一起到麥當勞邊念書邊聊天、期末考前在 Google Wave 上熱烈的討論。對於整個 FLOLAC 的課程，我想我還滿樂在其中的。

　　雖然不知道自己能學到多少，又能應用多少。不過也許就像 yen3 所說：「能體會，就能產生質變」。或許在之後就會發現，現在學過的這些，其實都有潛移默化的作用也說不定。

【演算】插入排序法 - Insertion Sort

2010-04-11T12:06:00.001+08:00

插入排序法（insertion sort）與選擇排序法（selection sort）類似，同為較簡易、直觀的排序演算法（sorting algorithm）。其原理都是將資料分為「已排序」與「未排序」兩個部份。再將未排序資料中的第一筆資料插入到已排序資料的適當位置。

與選擇排序法相同，一般我們習慣將「已排序」的資料擺在資料序列的前端，並將「未排序」的資料擺在資料序列的後端。

若是我們需要將資料由小排到大。則我們會依序取出每個「未排序」的資料，然後由「已排序」資料的最後一筆開始，往前依序尋找第一個比這筆「未排序」資料還小的元素，並將其後的所有資料往後移一格，再將這筆「未排序」資料「插入」在這個「空出來的位子」。

其虛擬碼如下：

Function insertionSort(Type data[1..n])
    Index i, j;
    Type value;
    For i from 2 to n do
        value = data[i];

        j = i - 1;
        While j >= 1 and data[j] > value do
            data[j + 1] = data[j];
            j = j - 1;

        data[j + 1] = value;
End

讓我們看看實際操作的例子。若是我們需要將以下資料由小排到大：

83 31 96 17 42 14 54

則每一次迴圈的執行結果如下：

83 31 96 17 42 14 54

31 83 96 17 42 14 54

17 31 83 96 42 14 54

17 31 42 83 96 14 54

14 17 31 42 83 96 54

14 17 31 42 54 83 96

同樣的，我們必須要分析這種演算法的執行效率如何。

在資料都已排序的最佳情況下，資料大小為 n 的敘述執行次數如下：

Function insertionSort(Type data[1..n])
    Index i, j;                                     // 1
    Type value;                                     // 1
    For i from 2 to n do                            // n - 1
        value = data[i];                            // n - 1

        j = i - 1;                                  // n - 1
        While j >= 1 and data[j] > value do         // n - 1
            data[j + 1] = data[j];                  // 0
            j = j - 1;                              // 0

        data[j + 1] = value;                        // n - 1
End

敘述的執行次數總和：B(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + (n - 1) + (n - 1) = 5n - 3 ∈ Ο(n)。複雜度為線性時間。

但是在資料完全反序的最差情況（註1）：

Function insertionSort(Type data[1..n])
    Index i, j;                                     // 1
    Type value;                                     // 1
    For i from 2 to n do                            // n - 1
        value = data[i];                            // n - 1

        j = i - 1;                                  // n - 1
        While j >= 1 and data[j] > value do         // n(n - 1) / 2
            data[j + 1] = data[j];                  // n(n - 1) / 2
            j = j - 1;                              // n(n - 1) / 2

        data[j + 1] = value;                        // n - 1
End

敘述的執行次數總和：W(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + (n - 1) = (3n² + 3n - 4) / 2 ∈ Ο(n²)，複雜度為平方時間。

平均來說，這種演算法的執行效率並不算高，因此也比較不適合用以處理數量較多的資料。

註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。

【演算】合併排序法 - Mergesort

2010-04-10T15:23:00.009+08:00

合併排序法（mergesort）是一個典型利用分治法（divide and conquer，D&C）解決問題的例子。其原理為不斷地將資料分成兩等分，直到每份的資料量小到一個程度後，各自排序後再一一合併起來。

　　假設現在有 n 筆資料需要進行排序。

　　則我們首先會將這 n 筆資料分成兩等分（大小皆為 n/2）；接著，再將這兩堆大小為 n/2 的資料各自分為兩等分（大小皆為 n/4）；同樣的，我們再將這四堆大小為 n/4 的資料各自分為兩等分（大小皆為 n/8）。

　　如此進行下去，直到每堆的資料量足夠小（例如：每堆只剩 1 筆資料）之後，我們就分別將每堆資料進行排序，再將這些資料堆兩兩一對進行合併，直到排序完成為止。

　　其虛擬碼大致如下：

Function mergeSort(Type data[1..n])
    If n <= 1 then return

    Index x, y, i, j
    x = n / 2
    y = n - x

    Type left[1..x], right[1..y]
    For i from 1 to x do
        left[i] = data[i]
    For i from 1 to y do
        right[i] = data[x + i]

    mergeSort(left)
    mergeSort(right)
    merge(data, left, right)
End

Function merge(Type data[1..n], Type left[1..x], Type right[1..y])
    Index i, j, k
    i = j = k = 1

    While i <= x and j <= y do
        If left[i] < right[j] then
            data[k] = left[i]
            i = i + 1
        Else
            data[k] = right[j]
            j = j + 1
        k = k + 1

    While i <= x do
        data[k] = left[i]
        i = i + 1
        k = k + 1

    While j <= y do
        data[k] = right[j]
        j = j + 1
        k = k + 1
End

　　讓我們舉個實際的例子說明：現在我們有八筆資料需要排序（由小而大）：

(84、13、73、26、32、19、91、38)

　　且只要每堆的資料量大於 1 時，就需要再將資料進行分割。

　　首先，我們先將資料分成兩等分：

(84、13、73、26)　(32、19、91、38)

　　此時每堆的資料量為 4 (8 / 2) > 1。因此，我們還需要將每堆資料再各自分成兩等分：

(84、13)　(73、26)　(32、19)　(91、38)

　　此時每堆的資料量為 2 (4 / 2) > 1。再一次，我們將每堆資料各自分成兩等分：

(13)　(84)　(26)　(73)　(19)　(32)　(38)　(91)

　　此時每堆的資料量為 1 (2 / 2) = 1 ，符合停止切割的條件。所以接下來，我們要將資料兩兩合併。在合併的同時，同時確保資料排序：

(13、84)　(26、73)　(19、32)　(38、91)

　　同樣的，我們將資料兩兩合併：

(13、26、73、84)　(19、32、38、91)

　　同樣的，我們將資料兩兩合併：

(13、19、26、32、38、73、84、91)

　　最後，我們從時間效率上來討論合併排序法。設 merge sort 的時間複雜度函數為 T(n)。

　　我們可以知道，在每一次呼叫 mergeSort() 函式時，我們都需要分別將前半段與後半段的資料複製給 left 跟 right，所以複製資料的時間花費為 c₁n。

　　然後，我們需要遞迴呼叫兩次資料大小為 n/2 的 mergeSort()，時間花費為 2T(n / 2)。最後再加上呼叫 merge() 函式所需的時間花費 c₂n。所以我們可以得到：T(n) = 2T(n / 2) + cn (n > 1)，且 T(1) = 1。

　　若是將式子展開：T(n) = 2T(n / 2) + cn = 4T(n / 4) + 2c(n / 2) + cn = 8T(n / 8) + 4c(n / 4) + 2c(n / 2) + cn = ... = cn + cn + cn + ... + cn = cn(lg n + 1) ∈ O(n lg n)（註1）。

　　由此可見，合併排序的的時間效率是相當不錯的。

　　另外，因為有網友詢問非遞迴的合併排序法，因此試著寫了以下這個虛擬碼：

Function mergeSort(Type data[1..n])
    If n <= 1 then return

    Index i, j, k
    For i from 2 to (n / 2) do
        For j from 0 to (n - 1) step (2 * i) do
            Index x, y
            x = min(i, n - j)
            y = min(i, max(0, n - i - j))

            Type left[1..x], right[1..y]
            For k from 1 to x do
                left[k] = data[j + k]
            For k from 1 to y do
                right[k] = data[i + j + k]

            Index p, q, r
            p = q = 1
            r = j
            While p <= x and q <= y do
                If left[p] < right[q] then
                    data[r] = left[p]
                    p = p + 1
                Else
                    data[r] = right[q]
                    q = q + 1
                r = r + 1

            While p <= x do
                data[r] = left[p]
                p = p + 1
                r = r + 1

            While q <= y do
                data[r] = right[q]
                q = q + 1
                r = r + 1
End

　　寫起來感覺不太直觀，如果有錯誤歡迎糾正我：）

註1. 其實可以直接利用支配定理（Master theorem）來求出複雜度 T(n)。

【演算】選擇排序法 - Selection Sort

2010-03-20T19:12:00.003+08:00

選擇排序法（selection sort）為一種較直觀的排序演算法（sorting algorithm）。其將資料分為「已排序」與「未排序」兩部份，並從「未排序」的資料中找出最大（最小）值，放入「已排序」資料的最後端。如是進行，直到排序結束（未排序資料為空）為止。

　　一般來說，我們的作法是：將「已排序」的資料擺在資料序列的前端，並將「未排序」的資料擺在資料序列的後端。

　　假設我們需要將 n 筆資料由大排到小。在起初，這 n 筆資料都是「未排序」的。於是，我們從這 n 筆資料取出其中的最大值，並將之放在「已排序」資料的最後端。換言之，就是將之與第一筆資料進行交換。

　　接著，我們再從剩下的 n - 1 筆資料取出最大值，同樣放入「已排序」資料的最後端（與第二筆資料進行交換）；再從剩下的 n - 2 筆資料取出最大值，放入「已排序」資料的最後端（與第三筆資料進行交換）。

　　以此類推，直到沒有任何「未排序」的資料為止。

　　選擇排序法的虛擬碼大致如下：

Function selectionSort(Type data[1..n])
    Index i, j, max
    For i from 1 to n do
        max = i
        For j from i + 1 to n do
            If data[j] > data[max] then
                max = j

        Exchange data[i] and data[max]
End

　　舉例來說，若我們需要將以下資料由大排到小：

19 58 33 41 28 14 53 84

　　則以此演算法運作的過程如下：

84 58 33 41 28 14 53 19

84 58 53 41 28 14 33 19

84 58 53 41 33 14 28 19

84 58 53 41 33 28 14 19

84 58 53 41 33 28 19 14

　　若是我們分析在最差情況下（所有資料的順序剛好完全相反），使用選擇排序法將 n 筆資料排序的敘述執行次數（註1）：

Function selectionSort(Type data[1..n])
    Index i, j, max                                 // 1
    For i from 1 to n do                            // n
        max = i                                     // n
        For j from i + 1 to n do                    // n(n - 1) / 2
            If data[j] > data[max] then             // n(n - 1) / 2
                max = j                             // n(n - 1) / 2

        Exchange data[i] and data[max]              // n
End

　　經由以上，我們可以得到最差情況下，敘訴的執行次數總和：W(n) = 1 + n + n + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + n = (3n² + 3n - 2) / 2 ∈ Ο(n²)。

　　由此可知，選擇排序法的時間複雜度與之前介紹過的氣泡排序法（bubble sort）相當，同樣為效率不大優良的排序演算法。

註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。

【目錄】Verilog

2010-03-13T12:49:00.000+08:00

Verilog 相關一覽

筆記

‧Introduction to Verilog
‧Quartus II Installation
‧Verilog Module
‧Create a Verilog Project

【筆記】Create a Verilog Project

2010-03-13T12:48:00.005+08:00

安裝好 Verilog 的撰寫環境－－Quartus II 之後，我們還需要建置好一個專案（project）才能正式開始。所以，這裡簡單的描述一下建立專案，以及編譯 Verilog 原始碼的流程。

　　首先，點選選單的 File/New Project Wizard。就會跳出一個專案的建置精靈：

　　在「What is the working directory for this project?」中輸入你專案的擺放路徑，並在「What is the name of this project?」中輸入專案的名稱（註1）。

　　若是專案路徑的資料夾不存在，會跳出訊息問你是否要建立它：

　　確定要建立，就選擇「是」。

　　按下 Next 之後，我們可以加入一些現有的檔案到專案裡頭：

　　你可以利用 File name 後方的「...」按鈕開啟檔案對話方塊，選擇要加入的檔案，再按下 Add 按鈕加入專案。也可以直接按下 Add All 將目錄下的檔案都加到專案中。

　　不過，這裡我們還沒有任何現存的檔案可以加入，所以直接按下 Finish 完成專案建置（註2）。

　　建立好專案之後，我們還需要建立一個 Verilog 的原始碼檔案。按下選單的 File/New，就會出現對話框詢問你新增的檔案類型：

　　由於我們要是 Verilog 的原始碼檔案，所以選擇「Verilog HDL File」。

　　新增完成之後，就可以直接開始撰寫程式碼（下圖中的程式碼為先前 Verilog Module 解釋的 AndGate Module）：

　　接下來將檔案存檔：

　　請記得，Quartus II 的主要模組一定要跟檔案名稱相同。

　　接下來，就可以按下選單的 Precessing/Start Compilation 開始編譯的動作。假如跳出「Full Compilation was successful」的對話框，就代表編譯成功了（註3）：

註1. 建議將專案放在獨立的地方，並為專案取個有意義的名稱，方便以後重複使用專案。
註2. 實際上後面還有一些設定燒錄晶片跟相關工具的部份，不過這裡我們目前都用不到。
註3. 這裡會看到其實編譯過程中會有些警告訊息。雖然這裡我們並不在意它，不過你也可以去看看這些警告訊息，查查到底為什麼。

【筆記】Verilog Module

2010-03-13T00:09:00.004+08:00

在之前的簡介中提到，Verilog 以模組（module）作為描述的基本單位。模組如同程式語言中的函式（function），可以將一部份的程式碼封裝起來，並提供對外溝通的介面（interface）。如此一來，我們便可以重複利用這些定義好的模組，以構成較大、較複雜的系統。

　　我們可以將模組看成兩個部份：連接埠（port）的宣告，以及模組的主體（body）。

　　其中，連接埠類似於程式語言中函式的參數（parameter），提供了對外溝通的介面。包含了輸入埠（input）、輸出埠（output）、或是兼具輸出入的雙向埠（inout）。簡單來說的話，其實可以把連接埠想成一顆 IC 上面的接腳（pin）。

　　而模組主體則類似於程式語言中的函式主體，表達了模組的結構，或是模組的功能與行為。

　　以下是一個 Verilog 的模組，代表一個 and 邏輯閘：

module AndGate(out, a, b);
    input   a, b;
    output  out;

    and(out, a, b);
endmodule

　　接著，讓我們一步一步理解這個簡易的模組。

module AndGate(out, a, b);

　　這裡的「module」為 Verilog 語法的關鍵字，代表一個模組宣告的開頭；「AndGate」為這個模組的名稱（註1）；而括號中的 out、a、跟 b，則是這個模組的連接埠（註2）。

　　不過，在這裡並沒有指明連接埠的類型（input、output、或是 inout）。所以我們將在下面兩行宣告它們：

    input   a, b;
    output  out;

　　我們宣告 a 跟 b 為 AndGate 的輸入埠，且 out 為 AndGate 的輸出埠。

　　而模組主體的部份，我們只做了一個簡單的動作：

    and(out, a, b);

　　「and」為 Verilog 提供的內建邏輯閘。這裡的動作是將輸入埠 a 跟 b 進行 and 運算，並以輸出埠 out 作為運算後的結果（註3）。

　　最後，我們以「endmodule」關鍵字結束模組的宣告：

endmodule

　　這個模組的示意圖大致如下：

註1. 你可以根據模組的功能，自行取一個有意義的名稱。
註2. 一般來說，我們習慣將 output 寫在前面、將 input 寫在後面。
註3. 或許想成「將 a 跟 b 接到 and gate 的 input 接腳，並將 out 接到 and gate 的 output 接腳」會比較好理解。

【筆記】Quartus II Installation

2010-03-12T19:34:00.007+08:00

在實際開始撰寫 Verilog 之前，我們需要先安裝好撰寫執行 Verilog 程式的環境工具。而這裡我們採用的工具，是 Altera 公司的 Quartus II 這套軟體。

　　Quartus II 是一套用以撰寫 Verilog、VHDL、AHDL 等 HDL 的開發工具，除了可以進行程式的編輯與編譯之外，也可以用以產生邏輯圖、狀態圖、波形圖等等，在功能上算是相當齊全。

　　現行的 Quartus II 有兩個不同的版本：Web Edition 與 Subscription Edition。

　　其中 Subscription Edition 有提供 30 天的試用期。超過試用期之後，是需要經過授權才可以繼續使用的。而 Web Edition 則是免費的版本，可以直接下載來使用。

　　這裡我們要使用的是 Web Edition。

　　要取得 Quartus II Web Edition，需要先連到其下載頁面：

　　然後，選擇下載「Quartus® II Web Edition Software v9.1 Service Pack 1」（請依照當前最新版本自行尋找）。

　　接著會進到 Account Sign-In 的畫面。假設各位都沒有 Altera 的帳號，可以選擇「Get One-Time Access」並在下面的文字框輸入你的 E-mail，就能夠不經由註冊的步驟繼續下載。

　　當然，若是你真的想註冊一個帳號，選擇「Create Your myAltera Account」並完成註冊步驟也是可以的。

　　最後，拉到頁面下方，點選「Click to Download Your File Now」，就可以進行下載，並開始安裝（因為安裝過程只需要選擇安裝路徑，這裡就不花版面贅述了）。

　　由於檔案大小高達 1.5GB，下載跟安裝的動作比較耗時，所以可能需要耐心等待一下子。

　　安裝完成之後，就可以開始使用 Quartus II 這套功能強大的工具囉：

【筆記】Introduction to Verilog

2010-03-12T19:31:00.004+08:00

因為系上這學期有一門要寫 Verilog 的必修課，所以想說乾脆直接在 blog 上做個筆記整理內容，並供一起上課的同學們作為參考。不過，其中的許多內容都不是我非常瞭解的，假如有任何錯誤或問題，都歡迎各位提出來。

　　說到 Verilog 就不能不先提到 HDL（Hardware Description Language，硬體描述語言）。

　　所謂 HDL，即是利用一般高階語言的程式撰寫法，以達成數位電路功能或結構的設計、驗證與模擬。利用 HDL，我們便可以不必透過傳統的手繪方式設計電路，再在麵包板上接出電路來進行驗證與模擬。而 Verilog 則是主流的兩種 HDL 之一（註1）。

　　Verilog 在設計時採用了近似於 C 語言的語法，以類似於函式（function）的模組（module）作為描述的基本單位。對於熟悉 C 語言的程式設計師來說，Verilog 還算是相當容易學習。

　　在實際的設計上，Verilog 則提供了四種層級的描述方式，供設計者在不同層次的觀點上設計電路。分別為：開關層級（Switch Level）、邏輯閘層級（Gate Level）、資料流層級（Dataflow Level）與行為層級（Behavioral Level）。

　　開關層級是 Verilog 所提供的最低層級。在這個層級上，設計者需要瞭解電路的開關－－電晶體（transistor）的元件特性，並以此進行電路的設計。

　　在邏輯閘層級中，設計者的觀點從一個個的電晶體，轉到較高層的邏輯閘（logic gate）。以此觀點，設計者可以直接利用如 and、or、not、xor 等邏輯閘，與將之連接的線路來進行設計。

　　在資料流層級中，我們關注的則是資料如何經由硬體元件進行處理、儲存、與流向；而在最高層級的行為層級上，設計者只需要知道模組與函式間的功能，而不去考慮硬體實作的細節。

註1. 另一種常用的硬體描述語言是 VHDL（Very-High-Speed Integrated Circuit Hardware Description Language）。

【演算】氣泡排序法 - Bubble Sort

2010-03-07T13:09:00.005+08:00

氣泡排序法（bubble sort）是排序演算法（sorting algorithm）中較簡易的一種。其運作的原理是藉由逐次比較相鄰的兩筆資料，並依照排序條件（由大至小或由小至大）交換資料直到排序完成為止。

　　假設現在我們需要將 n 筆資料 A₁、A₂、......、A_n 由小排到大。

　　一開始，我們需要先比較 A₁ 與 A₂ 兩筆資料的大小。若是 A₁ > A₂，則交換兩筆資料；接著比較 A₂ 與 A₃。若是 A₂ > A₃，則交換兩筆資料；以此類推，一直到比較完 A_{n - 1} 與 A_n 為止。

　　這樣就完了嗎？當然還沒。到目前為止，我們只確定 A_n 是 n 筆資料中最大的數字。

　　接下來，重複剛剛的動作：比較 A₁ 與 A₂、A₂ 與 A₃、A₃ 與 A₄、......，不同的是，這一次只需要比較到 A_{n - 2} 與 A_{n - 1} 即可。到目前為止，我們可以確定 A_{n - 1} 是 n 筆資料中次大的數字。

　　接著就繼續重複同樣的動作，便能確定每一輪比較中的最大資料，皆在這些資料的最後面。直到所有資料排序完成為止。

　　其原理的虛擬碼大致如下：

Function bubbleSort(Type data[1..n])
    Index i, j;
    For i from n to 2 do
        For j from 1 to i - 1 do
            If data[j] > data[j + 1] then
                Exchange data[j] and data[j + 1]
End

　　讓我們舉個實際的例子來說明。若是我們現在要將以下這些資料由大排到小：

1 43 6 79 50 2

　　則第一輪的比較與交換過程如下：

43 1 6 79 50 2

43 6 1 79 50 2

43 6 79 1 50 2

43 6 79 50 1 2

43 6 79 50 2 1

　　第二輪的比較與交換過程如下：

43 6 79 50 2 1

43 79 6 50 2 1

43 79 50 6 2 1

43 79 50 6 2 1

　　接下來以此類推。

　　由此可以看到，資料中較小的一筆會藉由交換慢慢「浮」到資料頂端，其「氣泡排序」之名也是因此而來。

　　若是我們分析在最差情況下（即所有資料的順序剛好完全相反，因為我們必須在每一輪迴圈，藉由不斷交換兩筆資料的動作，把最前頭的資料移到最後面），使用氣泡排序法將 n 筆資料排序的敘述執行次數（註1）：

Function bubbleSort(Type data[1..n])
    Index i, j;                                     // 1
    For i from n to 2 do                            // n - 1
        For j from 1 to i - 1 do                    // n(n - 1) / 2
            If data[j] > data[j + 1] then           // n(n - 1) / 2
                Exchange data[j] and data[j + 1]    // n(n - 1) / 2
End

　　可得出所有敘述的執行次數總和為：W(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 = (3n² - n) / 2 ∈ Ο(n²)，為一個平方時間（quadratic time）的演算法。

　　而在最好的情況下（即所有資料都為已排序狀態，因為不需要進行任何一次交換動作）：

Function bubbleSort(Type data[1..n])
    Index i, j;                                     // 1
    For i from n to 2 do                            // n - 1
        For j from 1 to i - 1 do                    // n(n - 1) / 2
            If data[j] > data[j + 1] then           // n(n - 1) / 2
                Exchange data[j] and data[j + 1]    // 0
End

　　所有敘述的執行次數總和為：B(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + 0 = n² ∈ Ο(n²)。複雜度依舊為平方時間。

　　對於一種排序演算法而言，這樣複雜度是相當沒有效率的。因此這個方法多半只是被拿來簡單的解釋排序概念，而不是拿來實際應用。

註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。

【演算】遞迴函式 - Recursive Function

2010-03-07T00:02:00.004+08:00

所謂的遞迴（recursion），簡單來說就是「函式（function）不斷呼叫自身」的一種程式撰寫法。遞迴的意義，在於把一個問題切割成相同性質的較小問題來解決。而為了防止程式無窮盡的遞迴下去，我們還必須為所寫出來的遞迴函式設定一個終止條件（termination condition）。

　　遞迴的原理，是利用函式本身的堆疊（stack）性質－－後進先出（last in, first out，LIFO）來達成的。說得簡單一點，就是當某個函式呼叫另一個函式時，其會先執行完被呼叫的函式，才繼續執行自身的函式內容。

　　讓我們舉一個常見的例子來解釋：階乘（factorial）。

　　在數學上的定義中，對於一個非負整數 n，其階乘代表的是所有小於或等於 n 的正整數乘積，記作 n!。即 n! = 1 × 2 × 3 × ... × n。若我們規定 0! = 1，則可以將之改寫成：對於所有非負整數 n，(n + 1)! = (n + 1) × n!。

　　於是，我們便可以利用程式寫出計算階乘的遞迴函式。以下為其虛擬碼：

Function factorial(Integer n)
    If n = 0 then
        Return 1
    Else
        Return n × factorial(n - 1)
End

　　在這裡，我們相當於將原始的問題 n! 看作是 n × (n - 1)! 這個較小的問題。也就是得知 (n - 1)! 的值，就可以求得 n! 的解。同樣的，又可以將 (n - 1)! 看作是 (n - 1) × (n - 2)!、將 (n - 2)! 看作是 (n - 2) × (n - 3)!、......。

　　舉例來說，若是我們需要利用程式求出 6! 的值。則在我們呼叫 factorial(6) 時，為了得出結果，亦須求出 factorial(5) 的值。而為了得出 factorial(5) 的結果，我們亦須求出 factorial(4) 的值......。一直不斷遞迴下去，直到達到終止條件：n = 0 為止。

　　實際運作的結果，就如下圖所示意的（藍箭頭代表呼叫，紅箭頭代表回傳）：

　　除此之外，遞迴還可以解決相當多其他的問題。例如斐波那契數列（fibonacci sequence）、老鼠走迷宮（mouse in a maze）、以及河內塔（tower of hanoi）等等，這裡我就不加贅述了。

　　雖然利用程式的遞迴解法較為直觀，但是不斷堆疊函式的結果，極有可能浪費了過多的記憶體空間。其實，遞迴的程式多半都能藉由迴圈的方式替代，只是程式也可能會因此變得複雜難懂。至於實際上要使用何者，就看你怎麼選擇囉。

【演算】複雜度分析 - Complexity Analysis

2010-03-06T21:34:00.006+08:00

在演算法簡介中，我們提到了「找電話」問題的兩個演算法：分別為「依序找」跟「按筆劃找」。我們可以知道，對於相同的問題，可能會同時存在許多不同的解法。然而在這種擁有多種可能解法的情況下，我們理應對這些演算法進行評估，並從中選擇一種最有效的方式。

　　從比較執行時間的層面來看，或許你會想到：直接利用計時器來比較不同演算法實現程式的執行時間。但是，這種方式的變因太多。實作演算法的程式語言、記憶體大小、不同的編譯（直譯）器、甚至是電腦中運行的程式，可能都會影響計時所得的結果。相對的，這種方式也就顯得不太準確。

　　除了實際去計時之外，我們也可以假設演算法中「每一步」的執行時間都相同。於是，我們也可以直接拿演算法所有「步驟」的執行次數總和來進行比較。

　　讓我們同樣以「依序找電話」演算法為例。

　　先考慮在最差情況（worst case）下（也就是欲尋找的電話號碼不在電話簿中，因為你必須搜遍整本電話簿），「依序找電話」虛擬碼每行敘述的執行次數如下（方便起見，我們以變數 n 代表電話簿的大小 phoneBook.size）：

Input name                                          // 1
While True do                                       // n
    If index > phoneBook.size then                  // n
        Output "phone number not found"             // 1
        Break loop                                  // 1

    If phoneBook.record[index].name = name then     // n
        Output phoneBook.record[index].phone        // 0
        Break loop                                  // 0

    index = index + 1                               // n

　　因此在最差情況下，每行敘述的執行次數總和：W(n) = 1 + n + n + 1 + 1 + n + 0 + 0 + n = 4n + 3。

　　由此可以發現，一個演算法的執行時間通常會隨著輸入資料的大小 n 的成長而成長（註1）。而這個與資料大小 n 相關的時間（或空間）函數，則稱為這個演算法的複雜度（complexity）。

　　不過，我們還可以用更簡明、更具數學意義的方式來表達它。

　　首先，我們可以知道當 n 是一個相當大的數字時，4n 是遠大於 3 的。換句話說，就是我們只需要保留函數的最高項，也就是這個例子中的 4n。而若是只想考慮其函數的成長趨勢，我們甚至可以連其係數一併省略，只注意 n 這個部份，代表這個演算法是一個線性時間（linear time）的演算法，記作 O(n)。

　　Ο（big-omicron，或是稱作 big-O）是一個漸進符號（asymptotic notation），代表了函數的漸進上限（asymptotic upper bound）。其定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ f(n) ≤ cg(n)，則 f(n) ∈ Ο(g(n))。

　　簡單來說，若是我們說一個演算法的複雜度函數 f(n) ∈ Ο(g(n))，就代表函數 f(n) 的成長趨勢與 g(n) 相似或是更慢的。

　　除了 big-omicron 之外，我們還可以使用 Ω（big-omega）、Θ（big-theta）、ο（little-omicron）與 ω（little-omega）來表達一個演算法的複雜度。

　　big-omega 代表了函數的漸進下限（asymptotic lower bound）。簡單來說，若是我們說一個演算法的複雜度函數 f(n) ∈ Ω(g(n))，就代表 f(n) 函數圖形的成長趨勢與 g(n) 相似或是更快的。其正式的定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ cg(n) ≤ f(n)，則 f(n) ∈ Ω(g(n))。

　　那麼 big-theta 呢？其實，big-theta 也就相等於 big-omicron 與 big-omega 的交集，也就是 Θ(g(n)) = Ο(g(n)) ∩ Ω(g(n))，代表 f(n) 函數圖形的成長趨勢與 g(n) 是相似的。其正式的定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀, c₁與 c₂ > 0，使得所有整數 n ≥ n₀ 都滿足 c₁g(n) ≤ f(n) ≤ c₂g(n)，則 f(n) ∈ Θ(g(n))。

　　而 little-omicron 與 little-omega 則分別為 big-omicron 與 big-omega 和 big-theta 的差集，即 ο(g(n)) = Ο(g(n)) - Θ(g(n)), ω(g(n)) = Ω(g(n)) - Θ(g(n))。以下為其正式定義：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ f(n) < cg(n)，則 f(n) ∈ ο(g(n))。

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ cg(n) < f(n)，則 f(n) ∈ ω(g(n))。

　　為了方便比較，我們可以將 f(n) 與 g(n) 比擬成 a 跟 b，則：

f(n) ∈ Ο(g(n)) ≈ a ≤ b
f(n) ∈ Ω(g(n)) ≈ a ≥ b
f(n) ∈ Θ(g(n)) ≈ a = b
f(n) ∈ ο(g(n)) ≈ a < b
f(n) ∈ ω(g(n)) ≈ a > b

　　雖然存在這麼多種漸進符號以表達演算法的複雜度，但是一般來說，當我們分析一個演算法的複雜度，比較常使用 big-omicron 來表達估算後的結果。這是因為對於一個演算法，其所耗費的時間（或是記憶體）上限，通常才是我們需要關注的重點。

註1. 對於演算法所使用的記憶體空間，通常也是如此。