# 數位系統 第 7 次實驗報告
###### tags: `digital system`
姓名：高聖傑
系級：資工113
學號：B093040016
實驗日期：11/22

## 實驗一

### 內容

- 目標 & 要求
- 使用 Structural level modeling 模擬並驗證 8-bit ripple-carry adder
- 其內部由兩個 4-bit cla adder 所組成

### 過程

上次的 ripple-carry adder 在 bit 越多時，效能會越差。
原因是在算第 N 位時，必須等待第 N-1 位的 Cout 進位輸出。
而 carry-look ahead adder 可以把加法的邏輯展開，
直接使用 $A_i\oplus B_i$ 和 $A_i\cdot B_i$ 的組合來算 carry 輸出。

- 比較兩者：
- ripple-carry adder
- 優點：構造簡單、模組化，可以像積木一個一個拼起來
- 缺點：在 bit 越多時，效能會越差
- 時間複雜度 : 線性時間 $O(2n+1) = O(n)$
- carry-look ahead adder
- 優點：很快。
- 時間複雜度 : 常數時間 $O(4) = O(1)$
- 缺點：把加法的邏輯展開需要大量 AND & OR gate，造成電路過於複雜

:::info
單獨使用其中一個都有其缺點，因此我們可以採取折衷做法，
例如使用 4 個 4-bit carry-look ahead adder 串連成共 16 bit 的加法器，
速度比 16 bit ripple-carry adder 快，在設計上也不至於太過複雜，

4 bit 版本的線路就已經夠複雜了，要是真的實做 16 bit 一定會很恐怖。
:::

- 公式
* carry propagate: $P_i = A_i\oplus B_i$
* carry generate: $G_i = A_iB_i$
* sum: $S_i = P_i\oplus C_i$
* carry: $C_{i+1} = G_i+P_iC_i$

* 展開以下第 n 項 carry 算式
* $C_0 =$ input carry
* $C_1 = G_0+P_0C_0$
* $C_2 = G_1+P_1C_1 = G_1+P_1(G_0+P_0C_0) = G_1+P_1G_0+P_1P_0C_0$
* $C_3 = G_2+P_2C_2 = G_2+P_2G_1+P_2P_1G_0+ P_2P_1P_0C_0$
* $C_4 = G_3+P_3C_3 = G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+ P_3P_2P_1P_0C_0$

先做出一個 4-bit carry-look ahead adder。
小規模測試合格後，接著串接兩個 4-bit cla adder，分別處理前、後各 4 bit，
中間用一條傳遞 $C_4$ 的 wire 連起來，即組成一個 8-bit cla adder

#### module code
cla_4bit, cla_8bit 使用 Structural level modeling

module cla_4bit(
    output [3: 0] sum, output ovfl, 
    input [3:0] A, B, input cin);
	
    wire [3:0] g, p, c;
    wire[10:0] w;
    //wire c1, c2, c3
    and a0(g[0],A[0],B[0]); 
    and a1(g[1],A[1],B[1]); 
    and a2(g[2],A[2],B[2]); 
    and a3(g[3],A[3],B[3]); 
    
    xor x0(p[0],A[0],B[0]);
    xor x1(p[1],A[1],B[1]);
    xor x2(p[2],A[2],B[2]);
    xor x3(p[3],A[3],B[3]);
    
    buf(c[0], cin);
    
    and(w[0],p[0],c[0]);
    or (c[1],g[0],w[0]);
    
    and(w[1],p[1],p[0],c[0]);
    and(w[2],p[1],g[0]);
    or (c[2],g[1],w[2],w[1]);
    
    and(w[3],p[2],p[1],p[0],c[0]);
    and(w[4],p[2],p[1],g[0]);
    and(w[5],p[2],g[1]);
    or (c[3],g[2],w[5],w[4],w[3]);
    
    and(w[6],p[3],p[2],p[1],p[0],c[0]);
    and(w[7],p[3],p[2],p[1],g[0]);
    and(w[8],p[3],p[2],g[1]);
    and(w[9],p[3],g[2]);
    or (ovfl,g[3],w[9],w[8],w[7],w[6]);
    
    xor(sum[0],p[0],c[0]);
    xor(sum[1],p[1],c[1]);
    xor(sum[2],p[2],c[2]);
    xor(sum[3],p[3],c[3]);
endmodule

module cla_8bit(
    output [7: 0] sum, output ovfl, 
    input [7:0] A, B, input cin);
	
    wire mid;
    cla_4bit s0(sum[3:0],  mid, A[3:0], B[3:0], cin);
    cla_4bit s1(sum[7:4], ovfl, A[7:4], B[7:4], mid);
endmodule

#### testbench code

`timescale 1ns / 1ps

module tbGen();

reg [7:0] A;
reg [7:0] B;
reg cin;
wire ovfl;
wire [7:0] sum;

cla_8bit _tb(.A(A), .B(B), .cin(cin),
.sum(sum), .ovfl(ovfl));
	
initial begin
    cin = 1'b0; A = 8'd8; B = 8'd7;
    #10
    cin = 1'b0; A = 8'd17; B = 8'd23;
    #10
    cin = 1'b1; A = 8'd0; B = 8'd9;
    #10
    cin = 1'b1; A = 8'd250; B = 8'd5;
    #10
$finish;
end
endmodule

### 模擬結果
兩數字的加法運算結果正確，加入 carry in 的運算結果也正確

## 實驗二

### 內容

- 目標 & 要求
- 模擬並驗證 2-digit BCD adder
### 過程

需存下 A + B 的運算過程半成品 Z，以便判斷 > 9 及後續運算。

- 重點：「偵測 4-bit binary sum > 9」，有 3 種情況
- binary sum 發生溢位 (ovfl=1) >= 16
- binary sum 在 $Z_8Z_4$ 的情況 >= 12
- binary sum 在 $Z_8Z_2$ 的情況 >= 10
- 取聯集（OR），得到 $C = K +Z_8Z_4 + Z_8Z_2$
- 若 C > 9 ，則 +6（等效於 -10）
- 作用：記錄進位，且把超出 10 的部分壓回去 0 ~ 9 之間
- 實做：再加一個 4-bit adder 處理 +6 的部分，根據 C 決定是否 +6
- C = True : Sum = Z+6
- C = False : Sum = Z+0

先做出一個 1-digit BCD adder。
小規模測試合格後，接著串接兩個 1-digit BCD adder，分別處理前、後各 1 digit，
中間用一條傳遞 $C_1$ 的 wire 連起來，即組成一個 2-digit BCD adder

#### module code
dec_adder, dec_adder_v2 使用 Structural level modeling

module dec_adder(
    output [3: 0] sum, output ovfl, 
    input [3:0] A, B, input cin);
	
    wire k0, k1, k2, o1, p;
    wire[3:0] w, z;
    cla_4bit s0(z[3:0],  k0, A[3:0], B[3:0], cin);
    and(k1, z[3], z[2]);
    and(k2, z[3], z[1]);
    or(o1, k0, k1, k2);
    buf(w[3], w[0], 0);
    buf(w[2], w[1], o1);
    cla_4bit s1(sum[3:0], p, z[3:0], w[3:0], 0);
    or(ovfl, o1, p);
endmodule

module dec_adder_v2(
    output [7: 0] sum, output ovfl, 
    input [7:0] A, B, input cin);
	
    wire mid;
    dec_adder s0(sum[3:0],  mid, A[3:0], B[3:0], cin);
    dec_adder s1(sum[7:4], ovfl, A[7:4], B[7:4], mid);
endmodule

#### testbench code

`timescale 1ns / 1ps

module tbGen();

reg [7:0] A;
reg [7:0] B;
reg cin;
wire ovfl;
wire [7:0] sum;

dec_adder_v2 _tb(.A(A), .B(B), .cin(cin),
.sum(sum), .ovfl(ovfl));
	
initial begin
    cin = 1'b0;    
    A = 8'b00110010; B = 8'b01000001;
    #10
    A = 8'b00100101; B = 8'b01010111;
    #10
    A = 8'b10000110; B = 8'b01111001;
    #10
$finish;
end
endmodule

### 模擬結果
測資為簡報中範例數字，其加法運算結果正確。

## 實驗心得
> 這次的實驗主要是讓我們練習用 verilog 程式碼實做進階版的加法器 module。

> 在做實驗一時，我們知道 carry-look ahead 即是「用空間換時間」。
> 其原理是把邏輯展開，用大量的運算過程半成品（$A_i\oplus B_i$ 和 $A_i\cdot B_i$）快速得出進位輸出。
> 我們同時也觀察到一個現象，carry-look ahead 把運算時長壓低的副作用，就是增加所佔用的面積，以及所使用的邏輯閘。
>
> 實驗二則是處理 10 進位的 BCD 編碼加法，我先完成「偵測 4-bit binary sum > 9」的部分，後半段卡了很久在思考怎麼在滿足條件時「+6」
> 我在測試時有試過能不能直接對 wire 賦予初始值，後來看了看網路上才知道有人使用 buf() 在最後的 argument 放入 0 或 1，且可以一個輸入對到多個輸出。

## Extra
網路上看到有人在使用 buf() 時，給了 2 個以上的 argument，這令我覺得非常困惑，
buf, not 居然不是單輸入、單輸出的嗎？
我可以理解 and, or, xor, nand, nor, xor, xnor 是屬於多輸入、單輸出
所以我先猜測 buf, not 是屬於單輸入、多輸出（不可能是多輸入、多輸出）
接著寫一個 module 實際驗證 / 測試

module test_buf(output[7:0] ans);
    buf(ans[5], ans[2], ans[1], 1);
endmodule


驗證結果：buf, not 確實是單輸入、多輸出。
不過我覺得這樣記很奇怪，就把他理解成 output 到很多根 wire 上吧