計算機概論報告

卡諾圖

卡諾圖是一種以圖形化的方式來進行布林代數化簡的表示圖。

由於卡諾圖本身亦記錄布林函數的數值，因此我們也可以視其為一種特別版本的真值表(truth table)。 (因為其變數的排列順序較為特殊)

當我們使用卡諾圖進行布林代數化簡時，需注意每次以2的指數次方擴大，儘可能以較大的方塊將布林值為1的部份給包起來，且不得包涵布林值為0的部份。

---

• 兩個變數的卡諾圖...
  
  • 兩個變數的卡諾圖

    a\b	b = 1	b = 0
    a = 1	11	10
    a = 0	01	00

    注意，藍色區塊內的每一個方格都有兩個位元，第一個位元代表a的數值，第二個位元代表b的數值。
    每個相鄰的區塊都只會相差一個位元，如果相鄰的區塊彼此的數值相同，則表示可以化簡一個布林變數。 (表示有一個變數不會有影響布林函數的結果)
    
  • 兩個布林變數的範例

    a\b	b	b'
    a	1	1
    a'	1	0

    注意，綠色區塊為布林值。
    
    • 第一次選取

      a\b	b	b'
      a	1	1
      a'	1	0

      注意，兩個黃色區塊即為被選定的區塊。
      黃色區塊所代表的函數為 a (因為 b的數值不會影響結果)
      
    • 第二次選取

      a\b	b	b'
      a	1	1
      a'	1	0

      注意，兩個黃色區塊即為被選定的區塊。
      黃色區塊所代表的函數為 b (因為 a的數值不會影響結果)
      
      由以上可知，該布林函數可化簡為 F = a + b

  ---

  
  
• 三個變數的卡諾圖...
  
  • 三個變數的卡諾圖

    a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
    a = 1	111	110	100	101
    a = 0	011	010	000	001

    注意，藍色區塊內的每一個方格都有三個位元，第一個位元代表a的數值，第二個位元代表b的數值，第三個位元代表c的數值。
    每個相鄰的區塊都只會相差一個位元，如果相鄰的區塊彼此的數值相同，則表示可以化簡一個布林變數。 (表示有一個變數不會有影響布林函數的結果)
    
  • 三個布林變數的範例

    a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
    a = 1	1	0	1	1
    a = 0	1	0	0	1

    注意，綠色區塊為布林值。
    
    • 第一次選取

      a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
      a = 1	1	0	1	1
      a = 0	1	0	0	1

      注意，四個黃色區塊即為被選定的區塊。
      ps. 卡諾圖的邊緣仍然是相連接。
      黃色區塊所代表的函數為 c (因為 a 與 b的數值不會影響結果)
      
      理由如下：
      (A) 我們使用 (a,b,c) 來表達literal a, b, c的數值...
      請注意看黃色區塊 (總共有4個1)
      先看左邊的兩個1，這兩個1所表示的minterm分別為 (1,1,1) 與 (0,1,1)
      有沒有發現，不管第一個literal a 是 1 還是 0，布林函數值都是 1。
      所以，a 不管是1還是0，都不會影響。因此，這兩個minterm可以變成 b c
      也就是 a b c + a' b c = b c
      ps. 即，當 b=1且c=1時，布林函數值為1。
      
      同理，我們再看右邊兩個1所表示的minterm分別為 (1,0,1) 與 (0,0,1)
      我們再度發現，不管第一個literal a 是 1 還是 0，布林函數值仍是 1。
      所以，a 不管是1還是0，都不會影響。因此，這兩個minterm可以變成 b' c
      也就是 a b' c + a' b' c = b' c
      ps. 即，當 b=0且c=1時，布林函數值為1。
      
      (B) 在下面的內容，我們使用 (b,c) 來表達literal b, c的數值...
      由(A)，我們可以得到 b c 與 b' c，相當於 (1,1) 與 (0,1)
      我們發現，不管第一個literal (b) 是 1 還是 0，其結果仍然是 1。
      所以，b 不管是1還是0，都不會影響。因此，可以得到 c
      也就是 b c + b' c = c
      ps. 即，c=1時，布林函數值為1。
      
      所以，我們將發現，在這四個1的minterm所組成的方塊中，
      literal a 和 literal b 將不會影響布林函數值。 (因為都是1)
      
      而化簡後的布林函數就是 c
      也就是 a b c + a' b c + a b' c + a' b' c = c
      
    • 第二次選取

      a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
      a = 1	1	0	1	1
      a = 0	1	0	0	1

      注意，兩個黃色區塊即為被選定的區塊。
      黃色區塊所代表的函數為 a b' (因為 c的數值不會影響結果)
      
      由以上可知，該布林函數可化簡為 F = c + a b'

  ---

  
  
• 四個變數的卡諾圖...
  
• 四個變數的卡諾圖

  ab\cd	c=1,d=1	c=1,d=0	c=0,d=0	c=0,d=1
  a=1,b=1	1111	1110	1100	1101
  a=1,b=0	1011	1010	1000	1001
  a=0,b=0	0011	0010	0000	0001
  a=0,b=1	0111	0110	0100	0101

  注意，藍色區塊內的每一個方格都有四個位元，第一個位元代表a的數值，第二個位元代表b的數值，第三個位元代表c的數值，第四個位元代表d的數值。
  每個相鄰的區塊都只會相差一個位元，如果相鄰的區塊彼此的數值相同，則表示可以化簡一個布林變數。 (表示有一個變數不會有影響布林函數的結果)

名詞解釋2

1. HTTP： Hypertext Transfer Protocol  超文字傳輸協定

2. TCP： Transmission Control Protocol  傳輸控制協議

3. ISP： Internet Service Provider 網路服務業者

4. SMTP： Simple Mail Transfer Protocol 簡單郵件傳輸協議

5. SNMP： Simple Network Management Protocol 簡單網路管理協議

6. DNS： Domain Name System 域名系統

7. ISDN： Integrated Services for Digital Network  整合服務數位網路

8. NNTP：Network News Transport Protocol 網路新聞傳輸協議

9. DCCP：Datagram Congestion Control Protocol  數據擁塞控制協議

10. DHCP：Dynamic Host Configuration Protocol  動態主機配置協定

名詞解釋

DRAM－Dynamic random-access memory動態隨機存取記憶體

ROM－Read-only memory唯讀記憶體

DDR SROM－ Double data rate(雙資料倍率的) synchronous dynamic random-access memory

PROM－programmable read-only memory可程式化唯讀記憶體

EPROM－erasable(可除式) programmable read-only memory

EEPROM－electrically(電子的) erasable programmable read-only memory
mask ROM

DIMM－dual In-line memory module
register暫存器

PSW－prgram status word程式狀態字組

PC－program counter程式計數器

CPU－central processing unit中央處理器

ALU－Arithmetic logic unit算術邏輯單元

TLB－Translation lookaside buffer轉譯後備緩衝區

BTB－Branch target buffer分支目標緩衝區

cache快取

IR－Instruction Register

漢明碼

所謂漢明碼(Hamming code)是一種錯誤更正碼，可檢查錯誤並更正。有關漢明碼的編碼方式說明如下：


(一)漢明碼的編碼：有關漢明碼的內容可以分成資料位元和核位元兩個部分，以傳輸資料中2的次方位元部分(第1,2,4,8.‥個位元)當核對位元 (check bits)Ci，分別由資料位元第k個位元中符合(2I AND k)0的所有位元中計算1的個數，結果則視採用奇同位檢查或偶同位檢查而定，若採用奇同位檢查則結果若為奇數個1則取0，偶數個l則取1；反之若採偶同 位檢查，則結果若為奇數個l則取l，偶數個1則取0。

(二)漢明碼的檢查：對各組核對位元作檢查，若引為核對位元Ci與其相關資料位元的同位檢查結果，則(Em-1, Em-2, ….E0)即為錯誤的位元位置，只要更正此一位元即可。


通用演算法
下列通用演算法可以為任意位數位產生一個可以糾錯一位（英語：Single Error Correcting）的漢明碼。
從1開始給數字的數據位（從左向右）標上序號, 1，2，3，4，5...
將這些資料位的位置序號轉換為二進制， 1, 10, 11, 100, 101, 等.
資料位的位置序號中所有為二的冪次方的位（編號1，2，4，8，等，即資料位位置序號的二進制表示中只有一個1）是校驗位
所有其它位置的資料位（資料位位置序號的二進制表示中至少2個是1）是資料位
每一位的資料包含在特定的兩個或兩個以上的校驗位中，這些校驗位取決於這些資料位的位置數值的二進制表示
校驗位 1 覆蓋了所有資料位位置序號的二進制表示倒數第一位是1的資料：1（校驗位自身，這裡都是二進制，下同），11，101，111，1001，等
校驗位 2 覆蓋了所有資料位位置序號的二進制表示倒數第二位是1的資料：10（校驗位自身），11，110，111，1010，1011，等
校驗位 4 覆蓋了所有資料位位置序號的二進制表示倒數第三位是1的資料：100（校驗位自身），101，110，111，1100，1101，1110，1111，等
校驗位 8 覆蓋了所有資料位位置序號的二進制表示倒數第四位是1的資料：1000（校驗位自身），1001，1010，1011，1100，1101，1110，1111，等
簡而言之，所有校驗位覆蓋了資料位置和該校驗位位置的二進制與的值不為0的數。
採用奇校驗還是偶校驗都是可行的。偶校驗從數學的角度看更簡單一些，但在實踐中並沒有區別。

因為2的0次方，2的1次方，2的2次方...（以下類推）要作為漢明碼
的填入位置，所以先寫成如下這樣

1   2   3   4   5   6   7   8   9   先在紙上寫出1-9再將資料
          1       1   0   1       0   由左至右順序填入

為什麼有四個空格（或者說怎麼知道要空這四格），是因為有一個
公式：2^K>=M+K+1（M就是資料位元有5，所以2^K要>=5+K+1，算出
K=4）

接下來再畫一個如下的表
     8   4   2   1        ←這一行只是方便我們看十進位的值是多少
1   0   0   0   □         ←先留空格是因為還不知道該填什麼
2   0   0   □   0          填表的方式是
3   0   0   1   1          (a)若資料為 0 則相對應的位置填 0。
4   0   □   0   0          (b)若資料為 1 則以其相對應的位置值
5   0   1   0   1             化成二進位碼，並填入相對應的位置中。
6   0   0   0   0        ←所以這一行才會都是0
7   0   1   1   1        ←這一行就是因為上面7的地方是1所以改為
8   □   0   0   0          二進制後填入
9   0   0   0   0        ←這一行也都是0
---------------------

再來就要依另一個規則決定漢明碼：各數位的 1 值個數需為偶數個
依此原則決定所有漢明碼的值
     8   4   2   1
1   0   0   0   □         ←空格填1，最右邊這行由上往下數有3個1，如
2   0   0   □   0          果要湊成偶數個1，則空格要填入1
3   0   0   1   1
4   0   □   0   0        ←空格填0，因為由上往下數已經有2個1，所以
5   0   1   0   1          不用另外填1
6   0   0   0   0
7   0   1   1   1
8   □   0   0   0
9   0   0   0   0
---------------------

再回到剛剛寫的兩列數字
1   2   3   4   5   6   7   8   9
        1       1   0   1       0
1   0       0               0       這時候就知道空白該填入什麼了
----------------------------------
1   0   1   0   1   0   1   0   0   所以兩個合併出來的就是漢明碼
                                        也就是（101010100） 

再來舉錯誤更正
題目：101010101

一樣先寫出1-9，這次不用什麼公式了，因為資料就是9位元，而且我們
現在要反推，所以也不用空格
1   2   3   4   5   6   7   8   9
1   0   1   0   1   0   1   0   1   ←同樣由左至右順序填入

再來畫一個表格，照上面所說的填表方式填入
     8   4   2   1
1   0   0   0   1
2   0   0   0   0
3   0   0   1   1
4   0   0   0   0
5   0   1   0   1
6   0   0   0   0
7   0   1   1   1
8   0   0   0   0
9   1   0   0   1
-------------------

這時候可以記一個規則，一行內有奇數個1則線下方填1，反之，有偶數個1
則線下方填0。所以可以把表改成這樣：
     8   4   2   1
1   0   0   0   1
2   0   0   0   0
3   0   0   1   1
4   0   0   0   0
5   0   1   0   1
6   0   0   0   0
7   0   1   1   1
8   0   0   0   0
9   1   0   0   1
-------------------
    1   0   0   1

把線下方取得的二進位碼轉成十進位得到9，這代表第＂9＂個位元出錯了，
所以把原來題目（101010101）的第9個位元（一樣由左往右算）改成0，
得到答案 

浮點數

浮點數的意思為用二進位來表示很大或很小的數值，就像自然界中十進位的指數一樣！
浮點數分成三個部分總共32位元，第一部分是符號共1位元：正數0、負數1；第二部分共八位元，表示指數的部分，是採用指數+127來表示；第三部分則是假數，及為數值用二進位法表示！

例如：(35.5)₁₀
=(100011.1)₂
=(1.000111000000000000000*2⁵)₂

補數運算

補數(Complement)：是指兩數字加起來等於某數時，則二數互為某數的補數；例如3的10補數為7，7的10補數為3。
二進位系統有
1的補數(1‘ Complement)

2的補數(2’ Complement)

1的補數(1‘ Complement) ：指兩數的和為1，則此兩數互為1 的補數，即1和0互為1的補數。

例如：

原數為	1	0	1	1	0	1
1補數為	0	1	0	0	1	0
即將原數的0變1，1變0

2的補數(2’ Complement)：指二兩數的和使每一位均為0而產生溢位(進位)。
求法：先取該數的1補數，再加1即可
例如：求01101的2‘補數為何？

原數為	0	1	1	0	1
1補數為	1	0	0	1	0
1的補數再加1	1	0	0	1	1

整數表示法

以二進位(0 & 1)來表示的正整數（無號整數）

—比如： 41=00101001

—無負號

—無標點

以二進位(0 & 1)來表示的正負整數（有號整數）

—符號位元表示法

—2’s補數表示法

整數加法

正常的二進位整數加法

以符號位元來觀察溢位情況

整數減法

整數減法可以先取負值，再加上這個負值

即 a - b = a + (-b)

所以，需要：加法電路和補數電路

無號整數乘法

例如:

 

 

 

數字系統

1.二進位系統 (binary system) 是以0、1等兩個數字做為計數的基底。

2.八進位系統 (octal system) 是以0、1、2 ~ 7等八個數字做為計數的基底。

3.十六進位系統 (hexadecimal system) 是以0、1、2 ~ 9、A、B、C、D、E、F等十六個數字做為計數的基底。

十進位	二進位	八進位	十六進位
0	0000	0	0
1	0001	1	1
2	0010	2	2
3	0011	3	3
4	0100	4	4
5	0101	5	5
6	0110	6	6
7	0111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F

將二、八、十六進位數字轉換成十進位數字 

例如:

 

將十進位數字轉換成二、八、十六進位數字

(1) 將十進位數字分成整數部分及小數部

(2) 找出整數部分的二進位表示法

（3）找出小數部分的二進位表示法

 

（4）將整數部分及小數部分的二進位表示法合併

 

將八或十六進位數字轉換成二進位數字