計算機概論工教一 39號: 3月 2013

2013年3月29日星期五

浮點數.錯誤更正瑪.CPU.MAR.MBR.IR.PC.Machine Cycle

3/22 計算機概論課程內容

錯誤更正漢明碼介紹
8 bit 為例
回家作業
16 bit 解釋
CPU(ALU AND CU)
Register: MAR , MBR, I/O AR, I/O BR, PC , AC, 等暫存器介紹
機器循環週期(擷取指令/解碼/執行/存回)

錯誤更正碼(ECC)

ECC英文全名為Error Checking and Correction Code，中文名稱為錯誤修正碼檢查。

ECC是使用一種特殊電路，利用較複雜的演算法檢查儲存在記憶體中的資料是否一致。ECC通常在每個byte的資料使用3bit來作檢查碼。而且它不只是可以從多個位元中找出其中錯誤，並且可以將錯誤的位元並予以更正。一個有ECC的系統，不僅能容許錯誤，並可以將錯誤更正，使系統得以持續正常操作，不致因錯誤而中斷。
ECC稱為「錯誤自動檢查與更正」，這也是一種資料檢查的技術，可以檢查資料是否正確；和Parity Check主要的不同點是在只有一個錯誤的狀況下，ECC具有自動更正的能力。

記憶體要具有檢查與修復的功能，就必須記錄更多的資訊，因此這類的記憶體除了負責資料的記錄之外，還要更多的記憶體來保存核對與更正所需的資訊。以前述的Parity Check為例，每8個位元需要增加1個位元來處理。ECC也是類似的做法，但每家廠商的做法並不完全相同，必須視處理資料的方式而定，例如Intel以64個資料位元搭配8個ECC位元，另外也有以8個資料位元搭配4個ECC位元的做法。

一般來說，現今製作記憶體的技術已趨穩定，所以"並非"所有的記憶體模組都具備ECC功能；換句話說，您若是要求購買具有ECC能力的記憶體，可能會稍微貴一點。

漢明碼

漢明碼(Hamming Code)，是在電信領域的一種線性偵錯碼，以發明者Richard Hamming的名字命名。漢明碼在傳輸的訊息流中插入驗證碼，以偵測並更正單一位元錯誤。由於簡單的漢明編碼，它們被廣泛應用於內存(RAM)。其 SECDED (single error correction, double error detection) 版本另外加入一檢測位元，可以偵測兩個以下同時發生的位元錯誤，並能夠更正單一位元的錯誤。因此，當傳送端與接收端的位元樣式的漢明距離 (Hamming distance) 小於或等於1時（僅有 1 bit 發生錯誤），可實現可靠的通訊。相對的，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數個的錯誤。

在數學方面，漢明碼是一種二元線性碼。對於每一個整數 $m>2$ ，存在一個編碼，帶有 $m$ 個奇偶校驗位 $2^m-m-1$ 個資料位。該奇偶檢驗矩陣的漢明碼是通過列出所有米欄的長度是兩兩獨立。

如果一條訊息中包含更多用於糾錯的位，且透過妥善安排這些糾錯位使得不同的出錯位產生不同的錯誤結果，那麼我們就可以找出出錯位了。在一個7位的訊息中，單個位出錯有7種可能，因此3個錯誤控制位就足以確定是否出錯及哪一位出錯了。
漢名研究了包括五取二碼在內的編碼方案，並歸納了他們的想法。

[編輯] 通用演算法

下列通用演算法可以為任意位數位產生一個可以糾錯一位（英語：Single Error Correcting）的漢明碼。

從1開始給數字的數據位（從左向右）標上序號, 1，2，3，4，5...
將這些資料位的位置序號轉換為二進制， 1, 10, 11, 100, 101, 等.
資料位的位置序號中所有為二的冪次方的位（編號1，2，4，8，等，即資料位位置序號的二進制表示中只有一個1）是校驗位
所有其它位置的資料位（資料位位置序號的二進制表示中至少2個是1）是資料位
每一位的資料包含在特定的兩個或兩個以上的校驗位中，這些校驗位取決於這些資料位的位置數值的二進制表示
1. 校驗位 1 覆蓋了所有資料位位置序號的二進制表示倒數第一位是1的資料：1（校驗位自身，這裡都是二進制，下同），11，101，111，1001，等
2. 校驗位 2 覆蓋了所有資料位位置序號的二進制表示倒數第二位是1的資料：10（校驗位自身），11，110，111，1010，1011，等
3. 校驗位 4 覆蓋了所有資料位位置序號的二進制表示倒數第三位是1的資料：100（校驗位自身），101，110，111，1100，1101，1110，1111，等
4. 校驗位 8 覆蓋了所有資料位位置序號的二進制表示倒數第四位是1的資料：1000（校驗位自身），1001，1010，1011，1100，1101，1110，1111，等
5. 簡而言之，所有校驗位覆蓋了資料位置和該校驗位位置的二進制與的值不為0的數。

採用奇校驗還是偶校驗都是可行的。偶校驗從數學的角度看更簡單一些，但在實踐中並沒有區別。
校驗位一般的規律可以如下表示：

編碼後資料位置		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
資料位位置		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
奇偶校驗位覆蓋率	p1	X		X		X		X		X		X		X		X		X		X
	p2		X	X			X	X			X	X			X	X			X	X
	p4				X	X	X	X					X	X	X	X					X
	p8								X	X	X	X	X	X	X	X
	p16																X	X	X	X	X

觀察上表可發現一個比較直觀的規律：第i個檢驗位是第2^i-1位，從該位開始，檢驗2^i-1位，跳過2^i-1位……依次類推。例如上表中第3個檢驗位p4從第2^3-1=4位元開始，檢驗4、5、6、7共4位元，然後跳過8、9、10、11共4位元，再檢驗12、13、14、15共4位元……

[編輯] 例子

對11000010進行漢明編碼，求編碼後的碼字。
1. 列出表格，從左往右（或從右往左）填入數位，但2的次方的位置不填。

位置	1	2	3	4	5	6	7	8	9	10	11	12	13	14
資料			1		1	0	0		0	0	1	0

2. 把資料行有的1的列的位置寫為二進制。

位置	1	2	3	4	5	6	7	8	9	10	11	12	13	14
資料			1		1	0	0		0	0	1	0
二進制			0011		0101						1011

3. 收集所有二進制數位，求異或。 $0011 \oplus 0101 \oplus 1011 =1101$
4. 把1101依次填入表格中2的次方的位置。

位置	1	2	3	4	5	6	7	8	9	10	11	12	13	14
資料			1		1	0	0		0	0	1	0
二進制			0011		0101						1011
校驗	1	1		0				1

5. 所以編碼後的碼字是111010010010。

CPU(ALU and CU)

CPU為控制整部電腦運作的中心樞紐，其內部包括控制單元、算術及邏輯單元、暫存器或記憶單元。

v算術及邏輯運算單元(ALU)：加、減、乘、除及比較、選擇、判斷等運算。

v控制單元(CU)：翻譯程式中的指令的解碼功能及協調控制各部門依指令執行使電腦自動化處理資料。

v記憶單元（MU）：儲存目前正要被處理運算的程式或資料，容量以KB為單位。

v暫存器(Register)：暫時儲存資料，如用來儲存運算的累積器。其功能與記憶體相似。

暫存器

暫存器（Register），是中央處理器內的其中組成部份。暫存器是有限存貯容量的高速存貯部件，它們可用來暫存指令、數據和位址。在中央處理器的控制部件中，包含的暫存器有指令暫存器（IR）和程式計數器（PC）。在中央處理器的算術及邏輯部件中，包含的暫存器有累加器（ACC）。
在電腦架構裡，處理器中的暫存器是少量且速度快的電腦記憶體，藉由提供快速共同地存取數值來加速電腦程式的執行：典型地說就是在已知時間點所作的之計算中間的數值。

(1) PC(程式計數器)：存放正要執行的運算碼的位址。

(2) IR(指令暫存器)：存放正要執行的運算碼。

(3) F(旗標暫存器)：存放ALU運算的狀態。

(4) 一般暫存器：存放ALU運算的中間結果，如AX，BX，CX，DX等。

(5) SP(堆疊指標)：為一種後進先出、線性的資料結構，常應用在副程式呼叫及中斷處理。

(6) MAR(記憶體位址暫存器)：到主記憶體中存取資料，必須先將位址存到MAR中。

(7) MBR(記憶體緩衝暫存器)：到主記憶體中I/O的資料暫時放到MBR中。

(8) MDR(記憶資料暫存器)：儲存機器碼指令的位址



資料暫存器: 用來儲存整數數字（參考以下的浮點暫存器）。在某些簡單（或舊）的CPU，特別的資料暫存器是累加器，作為數學計算之用。

位址暫存器: 持有記憶體位址，以及用來存取記憶體。在某些簡單/舊的CPU裡，特別的位址暫存器是索引暫存器（可能出現一個或多個）。

通用目的暫存器: （GPRs）- 可以保存資料或位址兩者，也就是說他們是結合資料/位址暫存器的功用。

浮點暫存器: （FPRs）- 用來儲存浮點數字。

常數暫存器: 用來持有唯讀的數值（例如0、1、圓周率等等）。

向量暫存器: 用來儲存由向量處理器執行SIMD指令所得到的資料。

特殊目的暫存器: 儲存CPU內部的資料，像是程式計數器（或稱為指令指標），堆疊暫存器，以及狀態暫存器（或稱微處理器狀態字組）。

指令暫存器（英語：instruction register） - 儲存現在正在被執行的指令
索引暫存器（英語：Index_register） - 是在程式執行實用來更改運算元位址之用。

在某些架構下，模式指示暫存器（也稱為「機器指示暫存器」）儲存和設定跟處理器自己有關的資料。由於他們的意圖目的是附加到特定處理器的設計，因此他們並不被預期會成微處理器世代之間保留的標準。

有關從隨機存取記憶體提取資訊的暫存器與CPU（位於不同晶片的儲存暫存器集合）

l 一般暫存器（Register）比較

類別	8086/8088暫存器(16 bit)	80386/80486暫存器(32 bit)
通用暫存器	AX，BX，CX，DX	EAX，EBX，ECX，EDX
指標索引暫存器	SP，BP，SI，DI，IP	ESP，EBP，ESI，EDI，EIP
區段暫存器	CS，DS，ES，SS	CS，DS，ES，SS，FS，GS
旗標暫存器	FLAG	EFLAG

機器循環週期(擷取指令/解碼/執行/存回)

1.指令擷取
2.指令解碼
3.指令執行
4.結果存回

I-time

nCU 從記憶體中擷取 (fetch)指令，然後放進暫存器中

nCU 將此指令解碼 (decode)，並決定所需要的資料在記憶體中的位置

E-time

n執行

•CU 將資料從記憶體搬移到 ALU 內的暫存器中

•由 ALU 負責控制與執行指令

•控制權回到 CU

nCU 將運算後的結果存放在記憶體或暫存器中

2013年3月22日星期五

3/15 計算機概論課程作業

3/15課程作業

乘法.浮點數.錯誤更正碼(未教完)

多寫D8已刪

3/15 計算機概論課程內容

電腦算術邏輯單元
加法
減法
乘法概念介紹
介紹浮點數格式
符號位元 1 bit
指數偏移 8 bit (0~255)
代表真實指數(-127~0~128)
另外 23個bit 代表假數

二進位數字的乘法

二進位數字的乘法可用與十進位乘法相同的方法來做。由乘數的最低有效位元開始，將乘數的每個位元乘上被乘數，每次運算皆可產生一個部分積，而後續的部分積都要往左移
一位，最後將這些的部分積加總便可得到最後積。
　　　　　　　　　　　　　　

二進位乘法運算
被乘數			B1	B0
乘數			A1	A0
			A0*B1	A0*B0
		A1*B1	A1*B0
積	C3	C2	C1	C0

所以由左邊的乘法運算我們可以得知：

　C0=A0B0
　C1=（A0B1 + A1B0）的和
　C2=（A1B1 +（A0B1+A1B0）的進位）的和
　C3=（A1B1 +（A0B1+A1B0）的進位）的進位

下面所示即為乘法器的真值表:

B1	B0	A1	A0	C3	C2	C1	C0
0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0
0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	1	0	1	0	0	0	1
0	1	1	0	0	0	1	0
0	1	1	1	0	0	1	1
1	0	0	0	0	0	0	0
1	0	0	1	0	0	1	0
1	0	1	0	0	1	0	0
1	0	1	1	0	1	1	0
1	1	0	0	0	0	0	0
1	1	0	1	0	0	1	1
1	1	1	0	0	1	1	0
1	1	1	1	1	0	0	1

下面所示為乘法器的邏輯電路圖：

四位元的定點二進制乘法器的實現有很多種，若使用解碼對照方式需要一一列表，真是費時且麻煩，所以便觀察我們小學老師所教的直式乘法之計算方式來試圖轉化流程進而完成本次電路。

浮點數表示法

數學上的科學符號就是浮點數表示法，其規則是：將某數表示為a*10^b 其中1≦a<10 。例如：

1023.32=1.02332*10³
23.32=2.332*10¹

若將其規則應用到二進位，則浮點數表示法如下：

(10.0101)₂=1.00101*2¹
(0101001.01)₂=1.0100101*2⁵
(11.1)₂=1.110000000*2¹
(0.10100)₂=1.0100*2^-1

國際電機電子工程師協會(Institute of Electrical and Electronics Engineers IEEE)制定短實數(Short Real)其格式如下：以32位元來表示浮點數，最左邊位元為符號位元，接著用8個位元來表示指數(Exponent)接著剩下的23個位元來表示假數(Mantissa)的部分。由於二進位中所有科學記號的表示法其結果小數點左邊均為1故可省略不記。

浮點數表示法轉換範例：
符號部分則由於該數(3.14159)為正數故為0
指數部分：指數為1，由於指數部分是採用超127，也就是將原數加上127再放入圖中的指數部分，因此指數部分表示如後：(128)₁₀=(1000 0000)₂
假數部分取23位放入圖中的假數部分
(3.14159)₁₀= (11.00100100)₂= (1.1001001000011111100111110*2¹)₂
將上述各位元放入記憶體中便可得到如下圖的表示法：

範例：

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

5=(00000101) ₂
5超127=(00000101) ₂+(01111111) ₂
=(1000100) ₂

s(1位元)+e(8位元)+m(23位元)

其中:s為符號位元(0表示正數,1表示負數),e為指數,bias為偏移量,m為假數

在單精確度(32位元)下

(指數偏移量為127)

2013年3月17日星期日

3/8 計算機概論課程作業

修改了很多次，一開始不太會寫，但是慢慢就習慣2.8.16位元的寫法.算法了~

2013年3月15日星期五

3/8 計算機概論課程內容

3/8 計算機概論課程

這一週進度

二進位/八進位/十六進位轉十進位

十進位轉二進位/十六進位/八進位

八進位透過三個一數轉成二進位再依四個一數轉成十六進位

十六進位透過四個一數轉成二進位再依三個一數轉成八進位

1的補數

2的補數

以10的補數作說明

一.數字系統

十進位

用0,1,2,3,4,5,6,7,8,9十個符號代表所有的數

逢十進一位

例如：15、397

二進位

用0,1二個符號代表所有的數

逢二進一位

例如：00111011₍₂₎、100101111₍₂₎

八進位

用0,1,2,3,4,5,6,7八個符號代表所有的數

逢八進一位

例如：21₍₈₎、47₍₈₎

十六進位

用0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F十六個符號代表所有的數

逢十六進一位

例如：13_(16)、4A_(16)、3E5.E4₍₁₆₎ 或13H、4AH、3E5.E4H (H是符號，表16進位數)　

Ｎ進位

用0,1,2,3,4......N-1等N個符號表示所有的數

逢Ｎ進一位

例如15_(n), 115_(n)

二.基本進位轉換

十進位	二進位	八進位	十六進位
1	1	1	1
2	10	2	2
3	11	3	3
4	100	4	4
5	101	5	5
6	110	6	6
7	111	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
16	10000	20	10

EX:二進位換成十進位

將2進位每一位數分別乘以其位值，再把結果加起來即可。由此可類推八進位十六進位轉十進位。

十進位轉換成二進位

將十進位整數連除以2，直到商數為0，再從下往上依次取出餘數。故(63)10=111111(2)

將十進位小數連乘以2，直到適當位數為止，從上往下依序取其整數。故(0.625)10=(0.101)2
由此可類推神十進位轉八進位和十六進位

八進位轉換成二進位

當八進位要轉換成二進位時, 只要將八進位的數值轉換成每3個1組的二進位數值即可。

十六進位要轉換成二進位

十六進位要轉換成二進位時, 只要將十六進位的數值轉換成每4個1組的二進位數值即可

十六進位數轉換成八進位數，八進位數轉換成十六進位數
按照前面所述將十六進位數轉人二進位數如此便可以再轉為八進位數
八進位數亦同理。

三.補數系統

對二進位而言有1補數系統和2補數系統兩個。
(1) 1的補數系統(1's Complement)：1補數系統是指兩數之和為1，則此兩數互為1的補數，亦即0和1互為１的補數。換言之，欲求得二進位數的1補數，只需將0變成1，1變成0即可；例如1010₂ 的1補數為0101₂。
(2) 2的補數系統(2's Complement)：2補數系統的求法是先取該數的1補數，再加1即可。

B1	B0	A1	A0	C3	C2	C1	C0
0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0
0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	1	0	1	0	0	0	1
0	1	1	0	0	0	1	0
0	1	1	1	0	0	1	1
1	0	0	0	0	0	0	0
1	0	0	1	0	0	1	0
1	0	1	0	0	1	0	0
1	0	1	1	0	1	1	0
1	1	0	0	0	0	0	0
1	1	0	1	0	0	1	1
1	1	1	0	0	1	1	0
1	1	1	1	1	0	0	1

B1	B0	A1	A0	C3	C2	C1	C0
0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0
0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	1	0	1	0	0	0	1
0	1	1	0	0	0	1	0
0	1	1	1	0	0	1	1
1	0	0	0	0	0	0	0
1	0	0	1	0	0	1	0
1	0	1	0	0	1	0	0
1	0	1	1	0	1	1	0
1	1	0	0	0	0	0	0
1	1	0	1	0	0	1	1
1	1	1	0	0	1	1	0
1	1	1	1	1	0	0	1

2013年3月29日 星期五

3/22 計算機概論 課程作業