數字系統與資料表示法

數字系統與資料表示法

.電腦的基本單位電腦，顧名思義，它必須是有電才有腦的，它是由許多電子電路所組合而成，它以1代表開，而以0代表關。對於任一條電路，它只能有導電1或不導電0兩種狀況，這也構成了電腦的基本單位，我們稱它為位元(Bit)，而這種只有0或1兩種狀態的系統就叫二進位系統(binarysystem)。

.電腦的基本單位在日常生活中，我們習慣於使用十進位 (由0、1、2至9所組成，逢10就進位)。 舉例而言，若班上有52位同學，使用十進位只要二位數就夠了，因為十進位的二位數可代表0到99，共有100種狀況。 而在電腦中呢? 因為它使用二進位(由0至1所組成，逢2就進位)，故一位數只能代表兩種狀況，二位數只能代表四種狀況，請看右表： 所以，班上有52位同學，若要用二進位來編座號，那至少得要有六位數才夠。.電腦的基本單位 現在請看看您的鍵盤，鍵盤上的A~Z共有二十六個字元，小寫的a~z又有二十六個字元，0~9有十個字元，再加上特殊符號(!@#%&

*…等)就超過九十三個字元了。而您在鍵盤所按下的每個字元都得是不同的代碼，電腦才能得以識別。

例如以ASCII碼來說，您按下”A”，它將傳送01000001的訊息至主記憶體中，而後在螢幕上顯示”A”。 如果是”B”呢?它傳達的訊息是01000010。 所以，電腦的基本單位是位元(Bit)，但一個位元只能代表兩種狀況根本不敷使用，所以它將8個位元，組成一個位元組(byte)。 8位元(bit)=1位元組(byte)

因為一個位元組(8bit)共有28=256種狀況，已足以代表鍵盤上的任一按鍵及功能鍵了。.電腦的基本單位對於使用英文的國家而言，都是由大小寫的A~Z所組成的。但對於中文呢?教育部編地的常用字有4800字，次常用字有7652字，再加上不常用字共有13053字，區區的一個位元組怎夠用呢?如果使用兩個位元組呢?兩個位元組共有65536種狀況，已足以代表任一中文字了，故一個中文字是由兩個位元組所組成的。所以，電腦的基本單位是位元(Bit)﹔而一個位元組(8bit)能代表任一字元(character)，亦即字元、數字或特殊符號；而對於中文字則須以兩個位元組來儲存。.電腦的基本單位 時至今日，電腦的儲存容量是相當大的，因為一個Byte只能代表一個小量的資訊，所以電腦記憶體和儲存媒體的容量通常以千位元組(1,024byte)，百萬位元組(1,048,576byte)，或十億位元組(1,073,741,824byte)來表示。故byte的縮寫為大寫的B，若為小寫的b則是bit的意思。一個中文字需2bytes來表示，若以60G的硬碟而言，約可容納30億個中文字，60億個英文字，因此要放入整個圖書館的資料是輕而易舉的事。.數位與類比數位(Digital)

在電腦中大部分所常見的資訊處理是以二進制位元的組合來編碼、儲存。也就是以兩個狀態(邏輯上的開與關)來代表兩個電壓的層次，並用以代表所有的資訊，包含文字、數字、圖形符號、程式命令。在這種情況下，電腦內的各電路元件之狀態會連續的改變，以移動、操作或儲存資料。一般而言是以高電壓和低電壓來呈現資訊，不像類比訊號是連續不斷變動的。.數位與類比類比(Analog) 某種裝置或訊號在數量或強度上具有連續不斷變動的屬性(如電壓或音頻訊號)，而不是以斷續的訊號為基礎(如電腦訊號中的0與1)。.數位與類比另外為了因應某些工作上的需求，我們需要將數位與類比訊號做轉換，如工程師需要將電壓轉換成數據顯示在電腦上；或需要將溫度以數據表現…等。這時候就需要ADC(類比至數位轉換器)或DAC(數位至類比轉換器)，就是將連續變動訊號轉換成二進碼或反之。.數字系統在日常生活中，我們最常用的數字系統是十進位的，也就是以0、1、2~9共十個數字來作為計數的基底(base)，逢10就進位了。但也有使用其他進制的，例如ㄧ斤有16兩，ㄧ兩有16錢，這就使用16進位系統。 而時間呢?一小時有60分鐘，ㄧ分有60秒，這就是60進位系統了。對於電腦呢?它的基本單位是位元(Bit)，只能代表0或1兩種符號，所以它使用的是二進位系統，也就是說它只能有0與1二個數字，逢2就進位了。.數字系統請看底下的十進制吧!其中的5是千位數，故得乘上10的3次方﹔而2為十位數，故乘上10的1次方﹔8為個位數，於是乘上10的0次方，小數點以後的呢?它即由左而右依次為10的-1次方、10的-2次方…方才說過，日常生活中我們最常使用十進制，這也就有如以下的問題：.數字系統3斤11兩，要怎麼算出共有幾兩呢?它的計算方法如下:它一共有59兩.數字系統又如3小時24分12秒，要怎麼算出一共有幾秒呢?請看如下的計算方法：答案是12252秒.數字系統接下來的問題，二進位的101011是十進位的多少呢?答案是十進位的43現在您已了解如何將二進位轉換成十進位了吧!而為什麼您要了解如何將二進位轉換為十進位呢?因為電腦只懂得二進位，而我們習慣看的是十進位，故電腦得將最終的答案由二進位轉換成十進位於螢幕上秀出給您看，它的原理就是如此!.數字系統反過來，您要如何將十進制轉換為二進制呢?當您要將十進位的數字轉換乘二進位時，只要將該十進制的值一直除以2，求出它的餘數，直至商小於除數即可。

例如本例即除至商為1(已小於除數的2)最後，您只要寫下商值，再將餘數由下至上，一次寫下即得如下的二進位數值.八進位系統請看底下的二進位數值:有問題了吧!您只看到一堆0與1，但還要解讀共有幾個0幾個1、以及前後順序為何，這根本是個難題!所以，為了方便閱讀或記憶，人們想出了各種不同的速記法，來取代二進制系統，這其中以八進位系統(octalsystem)與十六進位系統(hexadecimalsystem)最為普遍，也最方便轉換。八進位以0、1、2~7，共八個數字來做為基底，逢8就進位，所以在八進位系統中，您只能看到0~7的八個數字。為何二進位與八進位容易轉換呢?因為二進位的3位數正好等於八進位的1位數(23=8)，故只要將二進位的值由右至左，每3位取成一單位就可直接轉換成八近位了。請看下表：.八進位系統二進位的000至111轉換成八進位正好是0~7。故：您看!二進位的1000111101轉換成八進位是1075。這又是個問題了，如果您先寫出1075，又如何判別這是十進位或八進位呢?在數字的表示法中，我們將基底至於數字的右下角，以示出它是哪種進位系統!例如10758代表是八進位制的，而107510或1075(未標示基底)則代表為十進位制的，通常我們習慣使用十進位制，故未標示基底時，就表示為十進位制。.十六進位系統就像一斤共有16兩一樣，十六進位系統是逢16才進位，所以它需要有能代表0、1、2~15的值，這十六個值必須是一位數的，阿拉伯數字的0、1~9一共才十個值，還少了六個，所以十六進位制就以A、B、C、D、E、F來代表10、11、12、13、14、15。.各種進位之間的轉換前面曾經說過二進位與十進位之間的轉換，其實八進位、十六進位與十進位之間的轉換也是相同的做法，只是其基底不同而已。底下即示範將十進位的125轉換成八進位：當您需要將十進位的數字轉換成八進位時，只要將該十進制的值，一再除以8求出它的餘數，直至商小於除數為止。例如本例即除至商為1(已小於除數的8)，最後，您只要寫下商值，再將餘數由下至上一次寫下，即得該八進位數值：.各種進位之間的轉換如何在二進位、八進位與十六進位之間進行轉換呢?先前曾談到，二進位由右至左依序取3位可轉換成八進位，依序取4位可轉換成十六進位。故反過來，若要將八進位轉換成二進位，只要將八進位的每一位數轉換成3位數的二進位。 如果是十六進位呢?那只要將它每一位數轉換成4位數的二進位即可。 底下即示範將175的八進位轉換成二進位：由上述可知1758為二進位的11111012，前置0是可以省略的。例如十進位的069就等於69。.各種進位之間的轉換底下再示範將十六進位的23D轉換為二進位：由上述可知23D8為二進位的10001111012。同樣的，前置0是可以省略的。.各種進位之間的轉換上面所談的都是整數之間的轉換，如果有小數呢? 底下即示範將含小數的二進位制轉換成十進制：由上表得知.各種進位之間的轉換反過來，若您要將十進位的45.625轉換成二進位呢？ 它的處理步驟如下：

1.首先請將十進制的值分開成整數部分與小數部分。例如45.625的整數部分為45，而小數部分為0.625。2.將整數部分轉換成二進制。這在前面已談過了，45轉換成二進制為101101。3.將小數部分轉換成二進制。 整數部分要轉換成二進制要一直除以2，直至商小於2為止。 反過來呢?小數部分要一直乘以2，取乘績的整數部分，直至小數部分為0或出現循環為止。 請看以下示範：.各種進位之間的轉換4.將整數部分與小數部分合併本例的整數部分為101101小數部分為.101故合併後為101101.101故本例的小數部位為.101.各種進位之間的轉換什麼時候小數的部份會造成循環呢?底下即示範將十進位的21.6轉換八進位。它與轉換成二進位的做法完全相同，只是基底不同而已。1.將十進制的數字分成整數與小數二部分

21.6的整數部分為21，而小數部分為0.6。2.將整數部分換成八進制。故2110轉換成八進制為2583.將小數部分轉換成八進制整數部分需一直除以8，直至商小於8為止，反過來說呢?小數部分需一直乘以8，直至乘績的小數部分為0或造成循環為止。.各種進位之間的轉換4.將整數部分與小數部份合併本例的整數部分為25小數部分為.4631

故轉換後的八進位值為25.46318故本例的小數部份為4631——.Homework_3H9XB1OO，OO=學號2進位的(學號)位數字可代表幾種情況？學號10=()2學號16=()2學號8=()16學號8=()10學號10=()16學號.學號10=()2(請抄題目並含演算過程以Word方式繳交。記得寫姓名及學號).數值資料表示法上節所談到的數字系統，它能正確的表示出整數，也可代表出包含有小數的數字，但所處理的都是正數。對於數值，它也可能會有負數的，那如果要處理的數值包含有正負數，在電腦中可用什麼方式來表示呢?本節即介紹較為知名的幾種表示法：.帶符號大小（Signedbit）如果數值是有正數也有負數，那很簡單呀!它不是正數就是負數，而一個位元(Bit)可代表0或1兩種狀態，我們取其最高位元來代表正負數，以0代表正數，而以1代表負數，那不就得了。以一個位元組來講，若它所儲存的資料並沒有負數(例如庫存的庫存量、單價)，那8個位元可代表256(28=256)種狀況，它的數字範圍可為0~255。

請看此表：.帶符號大小（Signedbit） 如果您要以帶符號大小來表示呢?那它能代表的範圍為-127~+127。 請看底下說明：上式代表+5，最高位元的0代表正數，其後的7個位元代表數字。.帶符號大小（Signedbit）由上述兩表您可看到，對於0，有+0與-0兩種表示法。除此之外，以帶符號大小的表示法，其加/減法器的邏輯電路並不易設計，故不被電腦所採用。承上頁正數的範圍請參考下表:負數的範圍請參考下表:.1’S補數（1’Scomplement）對於1’S補數，它的正數範圍其表示式與帶符號大小是完全一樣的，亦即以最高位元的0代表正數，其後的各位元代表大小，請您參考上一小節的正數範圍。.1’S補數（1’Scomplement） 而對於負數呢? 它是取其正數的表示法，而後將所有的0改為1，將所有的1改為0，以此來代表負數。所以，在1’S補數表示法中，一個位元組能代表的範圍仍為-127~+127，其中的0也有+0與-0二種表示法。為了改進此缺點，電腦目前使用的是下一小節所介紹的2’S補數。.2’S補數（2’Scomplement）2’S補數比1’S補數多1，它的正數範圍其表示是與1’S補數表示法是一樣的(帶符號大小的表示法也一樣)。 而對於負數呢?它是以1’S補數法再加1來代表該負數。舉例來說，00000101是+5，如果要表示-5呢?

以1’S補數表示法就是將所有的0與1對調，故11111010為-5的2’S補數表示法。 而2’S補數表示法呢?

它將11111010再加1，得11111011，故11111011為-5的 2’S補數表示法。

它有怎樣的差異呢?.2’S補數（2’Scomplement）所以，在2’S補數表示法中，一個位元組(8bit)所能代表的範圍為-128-(27)~+127+

(27-1)。而在資料庫系統中，如此的範圍是太小了，故它以二個位元組(8bit×2=16bit)來代表整數欄位，它的儲存範圍為-32768-(215)

~32767+(215-1)。您看!所謂的+0與-0，在帶符號大小與1’S補數表示法中都有兩種表示方式。在2’S補數表示法中終於統一了。不管是+0或是-0，在2’S補數表示法中就是00000000。.2’S補數（2’Scomplement）請看右表：如果在資料庫系統中，某薪資的欄位內您要儲存的是整數，但又怕+32767不夠大(某些人的薪資是十幾萬的)，那也沒關係，您可指定該欄位以長整數(它佔用４個位元組的空間，共有8bitx4=32bit)來儲存，它能儲存的範圍為-2,147,483,648~+2,147,483,647，怎樣?夠大了吧!.浮點表示法（floating-pointnotation）除了整數的儲存外，對於實數的儲存，電腦是採用一種依科學記號演變而來的浮點表示法。

那什麼是浮點表示法呢？請看底下例子：它將整個數字以正負符號、小數部位及偏移指數來表示。-314726800.45=-31472.680045x104

=-3.1472680045x108=-0.31472680045x109.浮點表示法（floating-pointnotation） 請再看底下的例子：上面的等式都是成立的，但在電腦的儲存中，它必須有個統一的標準，此即所謂正規化(normalization)，亦即它必須使整數的部位為0，而小數點之後的第一位不得為0。現在請再看上數的各個等式，正規化的表示式該是0.11010110011011×210因為它的整數部位是0，而小數點之後的第一位數為1。如此在電腦中，它只要儲存它是正數、小數部位的值及多少次方即可。.Homework_4H9XB1OO，OO=學號-(學號)10

以”帶符號大小”的2進位8位數表示法為？-(學號)10

以”1’S補數”的2進位8位數表示法為？-(學號)10

以”2’S補數”的2進位8位數表示法為？-(學號.25)10的2進位正規化表示為？-(學號.25)10以ANSIStandard的32位元浮點表示法為？(請抄題目並寫出答案以Word方式繳交，記得寫姓名及學號。).複習帶正負號整數10的2進位表示法帶符號大小1’S補數2’S補數正數(8bit)完全相同00000000→+000000001→+1/01111110→+12601111111→+12700000000→+000000001→+1/01111110→+12601111111→+12700000000→+000000001→+1/01111110→+12601111111→+127負數(8bit)10000000→-010000001→-1/11111110→-12611111111→-12711111111→-011111110→-1/10000001→-12610000000→-12700000000→-011111111→-1/10000001→-12710000000→-128n-bit-(2n-1-1)

~+(2n-1-1)-(2n-1-1)

~+(2n-1-1)-(2n-1)

~+(2n-1-1).浮點表示法（floating-pointnotation）除了整數的儲存外，對於實數的儲存，電腦是採用一種依科學記號演變而來的浮點表示法。

那什麼是浮點表示法呢？請看底下例子：-314726800.45=-31472.680045x104

=-3.1472680045x108=-0.31472680045x109.浮點表示法（floating-pointnotation） 請再看底下的例子：上面的等式都是成立的，但在電腦的儲存中，它必須有個統一的標準，此即所謂正規化(normalization)，亦即它必須使整數的部位為0，而小數點之後的第一位不得為0。現在請再看上數的各個等式，正規化的表示式該是0.11010110011011×210因為它的整數部位是0，而小數點之後的第一位數為1。如此在電腦中，它只要儲存它是正數、小數部位的值及多少次方即可。.浮點表示法（floating-pointnotation）正規化：±0.有效數字x2次方1-bit次方2有效數字(2-12-22-3…..)32bits±：0為正，1為負正負整數值.浮點表示法（floating-pointnotation）ANSI(AmericanNationalStandardInstitute)1-bit7-bit次方224-bit有效數字(2-12-22-3…2-24)32bits+62.7510=+111110.112=+0.111110112x2+6=0

1000110

111110110000000000000000-0.4062510=-0.011012=-0.11012x2-1=1

0111111

11010000000000000000000000000000000001/01111111000000100000110000101000011100010010001011000110/1111110111111101/+63+64+65+66+67+68+69+70/+126+127-64-63/-10+1+2+3+4+5+6/+62+63次方：超64法.浮點表示法（floating-pointnotation）IEEE-754(InstituteofElectricalandElectronicsEngineers)1-bit8-bit次方223-bit有效數字(2-12-22-3…2-23)正規化：±1.有效數字x2次方+62.7510=+111110.112=+1.11110112x2+5=0

10000100

111101100000000000000000-0.4062510=-0.011012=-1.1012x2-2=1

01111101

1010000000000000000000000000000000000001/0111110101111110011111111000000010000001100000101000001110000100/111111101111111101/+125+126+127+128+129+130+131+132/+254+255例外-126/-2-10+1+2+3+4+5/+127例外32bits次方：超127法.浮點表示法（floating-pointnotation）ANSI與IEEE-754的比較相同：均以32-bit來表示帶有正負號的實數的表示法。相異：ANSIIEEE正規化±0.有效數字x2次方±1.有效數字x2次方規格1-7-241-8-23次方超64法(-64~+63)超127法(-126~+127)小數相同相同.Homework_4H9XB1OO，OO=學號-(學號)10

以”帶符號大小”的2進位8位元數表示法為？-(學號)10

以”1’S補數”的2進位8位元表示法為？-(學號)10

以”2’S補數”的2進位8位元表示法為？-(學號.6875)10的ANSI正規化=？-(學號.6875)10以ANSI的32位元浮點表示法為？-(學號.6875)10的IEEE正規化=？-(學號.6875)10以IEEE-754的32位元浮點表示法為？(請抄題目並寫出答案以Word方式繳交。記得寫姓名及學號).電腦架構

.Von-NewmanMachine透過內儲程式的控制，配合適當(時)的Input，產生正確的Output的機器。電腦的5大架構C.U.(ControlUnit)A.L.U.(Arithmetic&LogicUnit)MemoryInputOutputC.P.U.(CentralProcessingUnit)I/O有缺陷，所以需要輔助記憶體.電腦硬體架構程式

資料MemoryCPUC.U.A.L.U.InputOutputA.S.(AuxiliaryStorage)輔助記憶體指令資料存取.MemoryMemory實作之缺陷速度太慢

階層式記憶體(MemoryHierarchy)解決，如：快取記憶體(Cache)容量有限揮發性記憶體

(VolatileStorage)快閃記憶體(FlashMemory)RAM(RandomAccessMemory)MainMemory主體，有volatile。ROM(ReadOnlyMemory)唯讀，沒有volatile，將程式燒入其中，開機時將作業系統(OperatingSystem)搬入Memory中。A.S.解決.MemoryROM儲存程式分類自我檢查程式Bootstrap載入：將OS載入Memory中(BootstrapLoader)：靴帶程式，可以上工了！BIOS(BasicInputOutputSystem)所有有關I/O操控程式的集合，以備其他程式呼叫。.MemoryRegister暫存器(工人的口袋)一排Flip/Flop(正反器)，儲存一組資訊，速度極快，存CPU最近馬上要用/常用的資訊(資料，位址，指令)CPU內有許多Registers(現在約十幾個，以後會更多≒250個Register可分為DataRegisterGeneral-PurposeRegister:AX,BX,CX,DX等Accumulator(累加器):Acc等ControlRegisterSpecial-PurposeRegister慢CPUMemory暫存器工人倉庫資料指令.MemoryControlRegisterPC:ProgramCounter(計數器)存電腦正要/將要執行的指令的位址IR:InstructionRegister存電腦正在執行的指令內容MAR(MemoryAddressRegister)決定Memory實際大小之上限MBR(MemoryBufferRegister)決定電腦之位元數FlagRegister(旗標暫存器)存一串bits，分成數個欄位，每個欄位紀錄正在執行程式的某一狀態，代表某個狀態發生了沒？CUALUPCIRMemory位址++指令CPU…….1GigaBytes=230MARMBR位址30bits資料(指令).Co-Processor副處理器(副手)能執行指令，處理資料的電路，平時不作用，只執行特定指令，專門負責CPU不會做：如80386時代80486之80387浮點算器，目前之DSP數位訊號處理器(DigitalSignalProcessor)等。不願做：如I/O指令由I/Oprocessor負責，因為CPU執行速度快(us)，而I/O速度慢(ms)。為使CPU速度不被I/O拖住，所以以I/Oprocessor代為執行，可使CPU以Multi-programming方式，多工處理多個程式。I/Oprocessor又稱為channel(通道)PC(PersonalComputer)以DMA(DirectMemoryAccess)代替I/Oprocessor。沒有I/Oprocessor窮人的I/Oprocessor.Bus(匯流排)分類Addressbus

DataBusControlBusCPU…….MARMBRR/WAddress單向MemoryALE送位址門鎖DIR方向DEN送資料雙向AddressLetchEnableDataENable.C.U.:ControlUnitCPU/電腦中最複雜的部分製作方式Hardwired(硬體接線)：將C.U.視為一種邏輯電路1940’s~1960’s,1985’s~未來缺點：工程浩大費時修改不易優點：速度快Micro-programmed(微程式)：將C.U.視為一ROM(ReadOnlyMemory)1960’s~1980’s中缺點：反應速度慢優點發展迅速修改方便.指令運作原理指令：機器碼Machinecode(一串0/1)抓指令執行OP-codeOperandsOperandsOperands運算碼運算元動作對象.指令運作原理TimeInstructionCycle(指令週期)S1S2S3S4．．．．．．S1:ADDDX,100[BX]FetchInstruction

把指令抓進Memory中Decode

解碼，CU發出該Op-code之控制訊號OperandAddressing

找出運算元在Memory中的位址OperandFetch

抓取運算元Execution

執行運算WriteBack

將執行結果寫回Memory中.指令運作原理CISC:Complex

Instruction

Set

Computer

複雜指令集電腦六階段RISC:Reduced

Instruction

Set

Computer

簡單指令集電腦四階段ADDAX,100[BX]AX←AX+Mem[100+BX]

FetchIns.DecodeOperandAddressingOperandFetchExecutionWritebackFetchDecodeExecutionWriteback.指令運作原理RISCvs.CISCCISC：1970’s因以Micro-Programmed來製作C.U的方式(軟體)被重用，C.U的大小及功能被不斷擴充，所以指令集中的指令數目增加到500~800個之多。RISC：1970’s末，IBM-801以Hardwired的方式(硬體)製作C.U，所需指令少，速度快。RISC指令集架構是由DavidPeterson(U.CBerkeley)及JohnHennessy(Stanford)所發揚光大。WhyRISC?80%的CPU時間執行20%的基本指令。.RISCvs.CISCRISCCISC指令數目100個之內數百個定址法固定數種(Direct,Immediate等…)複雜而變化多指令長度與格式固定(4Bytes)各指令隨需要而不同指令週期固定各指令隨需要而不同控制邏輯HardwiredMicroprogrammed程式所需指令數目較多較少特性較適用於Pipeline,Cache等設計程式設計較簡單CodeSize大小代表機型ALPHA,PowerPC等僅Pentium系列Register數目多(數十~數百個)少(數個).指令運作原理Pipeline：將指令分成數個獨立階段(stage)，分別由不同之硬體負責，使連續指令能同時按順序在不同階段重疊(overlap)執行TimeInstructionCycle(指令週期)F1S1S2S3S4．．．．．．D1E1W1F1D1E1W1F1D1E1W1F1D1E1W1.指令運作原理Pipeline三大危障(Hazard)StructuralHazard(結構危障)：

因硬體資源衝突

LOADAX,100[BX]DataHazard(資料危障)：因連續指令有資料相依的關係ControlHazard(控制危障)：因更改控制流程指令如：Jump,Call,Return,Int

等…F1S1S2S3．．．．．．D1E1W1F1D1E1W1F1D1E1W1同時作MemoryAccess.指令運作原理Problems增加電腦執行效率(performance)的方法？Pipeline:可加快程式執行速度Cache:可減少程式執行時間加快指令執行速度的方法？CachePipelinePipeline將延長指令週期(latency).DMA(DirectMemoryAccess)窮人的I/Oprocessor除CPU之外唯一會主動透過Bus存取Memory，來執行I/O動作。(協調Bus，CycleStealing)DMA使用Bus作I/O的方式CycleStealing:DMA向CPU借Bus，趁CPU不用Bus時，作一次存取。BurstModeI/O一旦借到Bus使用權，就一直用到完成I/O為止。CPUDMACMemoryBufferDiskBufferBus*DMA使用Bus的優先權比CPU高？因為DMA使用Bus的頻率遠比CPU低.記憶體儲存裝置VirtualMemory(虛擬記憶體)使user執行program時，能不受限於實際memory的大小，主要是O.S(作業系統)的技術配合硬體完成)。MemoryHierarchyConcept(階層式記憶體概念)Cache(快取記憶體)Disk/Tape(磁碟/磁帶).記憶體儲存裝置MemoryHierarchyConcept(階層式記憶體概念)透過多層次記憶元件，考量效能(Performance)，容量(capacity)，成本(Cost)等因素，所作成的記憶體配置。Register–Cache–MainMemory–Disk–Tape愈快

←速度→愈慢愈昂貴

←價格→愈便宜愈小

←容量→愈大.記憶體儲存裝置MainMemoryROMRAMMaskROM

已寫入資料的ROMProgrammableROM

尚未寫入資料的ROMErasablePROM

可修改重置(抹去)的ROMElectricalEPROM

可以電壓寫入/抹去的ROMFlashMemory

更新式的EEPROM(金氧半導體MOS技術)，NoVolatile，未來可取代RAM。SRAM(StaticRAM)：用Flip/Flop儲存，速度快，密度低(元件大)，成本高，作Cache等快速記憶體，不須Refresh。DRAM(DynamicRAM)：用電容器製作，速度慢，密度高(元件小)，成本低，為MainMemory的主體，須Refresh。.記憶體儲存裝置記憶體儲存方式分類SAM(SequentialAccessMemory)循序存取記憶體資料存取時間與資料所在位置有線性關係，適用於批次檔案及備份檔案，如磁帶等。RAM(RandomAccessMemory)隨選存取記憶體資料存取時間與資料所在位置無關，存取時間為常數，如ROM，RAM等。DAM(DirectAccessMemory)直接存取記憶體資料存取時間與資料所在位置有關，但不可預測，如Disk，CD-ROM等。CAM(ContentAccessMemory)內容存取記憶體以內容(資料)決定存取位置，如Cache.記憶體儲存裝置Cache:可有可無的記憶體存CPU最近常用的區塊：Cache大小約為主記憶體1/1000，卻可滿足CPU95%以上的存取需求。運用LocalityofReference原理Temporallocality：CPU存取某資料X，則未來馬上會再存取X，如變數資料，程式迴路(loop)等。Spatiallocality：CPU存取某資料X，則未來馬上可能用下一個/前一個或附近的資料，如陣列資料，循序指令等。CPUCacheMainMemoryDataMem.Address時間上空間上.記憶體儲存裝置Cache有三種結構分類成本Cost效果HitRate失誤率MissRateDirectmapped(貧民版)低廉$5最差88%12%FullyAssociative(尊王版)昂貴$500000最好99.8%0.02%N-waysetAssociative(國民版)便宜$20~$50很好98~99%1~2%.記憶體儲存裝置例：CPU存取Mem.須200ns，存取Cache須10ns，若CPU執行指令中有1/3是load/store指令，則在一個90%hitrate的Cache支援下，其指令執行速度比沒有Cache時，加速多少倍？ANS:加速(Speedup)=

=

==6.9倍此題中，如果hitrate=95%時，加速多少倍？沒有Cache時的執行時間有Cache時的執行時間20029設CPU總共執行X道指令{(X-X)*1+X*2}*200ns{(X-X)*1+X*2}*(90%*10ns+10%*200ns)執行指令時，所需要存取Mem.的總次數Cache真偉大！.補充在一管線計算機中有四個管線，其處理某運算所需時間分別為3、1、4、2，則全部計算完10個此種運算所需時間為何？Ans：

TimeS1S2S3S4S5S6S7S8S9S103142312243312413312413312413312413312413312413312413312413開始結束總計運算時間=3*2+4*10+2*1=48(時間單位)如果不使用管線，做完10個此種運算所需時間為何？如果全部計算完10000個此種運算所需時間為何？如果不使用管線，做完10000個此種運算所需時間為何？Pipeline真偉大！.資料結構簡介.堆疊(Stack)與佇列(Queue)堆疊資料插入(push)與刪除(pop)的動作只能在串列的一端(top)進行。FILO：先進後出(firstinlastout)LIFO：後進先出(lastinfirstout)堆疊是空的，top=0a將a插入(push)堆疊中，top=1ba再將b插入(push)堆疊中，top=2a將b從堆疊中刪除(pop)，top=1再將a從堆疊中刪除(pop)，堆疊空了，top=0.堆疊的應用運算式的中序，後序，前序表示法中序(infix)：運算符號在運算元中間，如a+b。後序(postfix)：運算符號在運算元後面，如ab+。前序(prefix)：運算符號在運算元前面，如+ab。中序表示法在運算時，須考慮：運算符號的優先順序（priority）結合性（左結合或右結合）括弧內先處理前序式與後序式則無上述困擾(A+B)/(C-D)*E+F/G.堆疊的應用電腦如何經由後序表示法了解運算式？自左而右輸入後序運算式逢運算元，存入堆疊(push)逢運算符號α，從堆疊取出(pop)必要數目的運算元，執行α運算結果再存回堆疊運算式掃描完畢，後序式之計算結果就在堆疊頂部，pop出來即可計算後序式：63/1-42*+堆疊是空的，top=06將6存入堆疊中，top=136將3再存入堆疊中，top=22將結果2存回堆疊中，top=1將3,6取出，執行/運算，結果=212將1再存入堆疊中，top=21將結果1存回堆疊中，top=1將1,2取出，執行-運算，結果=1241將4,2存入堆疊中，top=381將8存回堆疊中，top=2將2,4取出，執行*運算，結果=89將9存回堆疊中，top=1將8,1取出，執行+運算，結果=9.堆疊的應用中序式→後序式：將運算式依各運算符號的優先順序完全地以括弧括起來即每一運算符號對應一對括弧移動運算符號到對應的右括弧前面去掉所有括弧例：將中序式改為後序式：(A+B)/(C-D)*E+F/G(A+B)/(C-D)*E+F/G((((A+B)/(C-D))*E)+(F/G))…((((AB+)(CD-)/)E*)(FG/)+)…AB+CD-/E*FG/+…HW_6第一題：將中序式改為後序式：(a+b*c)-d/e+f.堆疊的應用將後序(postfix)運算式abc*+de*-f+轉換成前序(prefix)運算式之結果為何？Ans：abc*+de*-f+a(b*c)+de*-f+a(b*c)+de*-f+(a+(b*c))de*-f+(a+(b*c))de*-f+(a+(b*c))(d*e)-f+((a+(b*c))-(d*e))f+(((a+(b*c))-(d*e))+f)(a+b*c)-d*e+f.堆疊的應用HW_6第二題：後序運算式(postfixexpression)”235*27-/+63*+”中的運算元(operand)皆為個位數，則其運算結果為何？.堆疊(Stack)與佇列(Queue)佇列資料插入(insertion)的動作在串列的尾端(rear)進行資料刪除(deletion)的動作在串列的頭端(front)進行。FIFO：先進先出(firstinfirstout)LILO：後進後出(lastinlastout)ABARear=0Front=0Rear=1Front=0Rear=2Front=0BRear=2Front=1Rear=2Front=2.二元樹A是B,C的父節點，D,E是B的子節點，M是Z,+的父節點，P,Q是H的子節點。A(樹根)有B,C兩棵子樹…，C是C子樹的樹根。P,Q,R,S,T…*,/,$是終端節點(樹葉)，其餘的皆是非終端節點，如A,D,F,M…。階度(level)：樹根A階度為1，B,C階度為2，J,K,L,M…階度為4。高度(hight)：整棵樹的高度為4，F子樹的高度為3，H子樹的高度為2。APQRSTUVWXYZ+-*/$HIJKLMNODEFGBC.二元樹的追蹤(trace)中序(inorder)追蹤：BCAEDGFHI

左根

右

前序(preorder)追蹤：ABCDEFGIH

根左

右後序(postorder)追蹤：CBEGHIFDA

左右

根GICEFBDAHHome_work_7請將右列二元樹，分別以中序，前序追蹤列出節點順序。GHIJDEFBCA.河內塔(HanoiTower)右圖，如要將n個碟子由A搬到C，則先將n-1個碟子由A搬到B再將最大的碟子由A搬到C最後再將B的n-1個碟子搬到C規定：大盤子不可以疊在小盤子上面ABCABC3211AC2AB1CB3AC1BA2BC1ACN個碟子共須搬2n-1次.程式語言簡介.程式語言的演進一、機器語言(machinelanguage)由一堆的「0」或「1」所組成。對於不同型態的電腦，因為其結構不同就有不同的機器語言。不容易撰寫外，對於程式的維護也相對的困難。二、組合語言(assemblylanguage)使用輔助記憶碼以方便記憶。不同型態的電腦，其組合語言也是不相同的。須經由assembler(組譯程式)組譯成機器碼後，才可執行。.程式語言的演進三、高階語言(high-levellanguage)

使用人們所熟悉的語法來描述。大大減低了程式設計的難度，這使得它廣為程式設計師所採用。須經由compiler(編譯程式)或interpreter(直譯程式)翻譯成機器碼後，才可執行。四、非常高階語言(veryhigh-levellanguage)

第四代程式語言

(fourth–GenerationLanguage；4GL)程式設計師只要設定它所要的格式及其結果，這種語言會自動推展出所期望的程式碼。.語言轉譯程式非常高階語言高階語言組合語言Compiler編譯程式Interpreter直譯程式Assembler組譯程式MachineCode機器程式碼機器語言BASICFortranCOBOLPASCALCC++BCBASSEMBLY.語言轉譯程式對於高階(HighLevel)語言，您仍得將其翻譯成機械碼才得以執行。 翻譯的方式有兩種：

直譯法（為直譯程式的翻譯方式） 亦即當演講者講了一句後，翻譯員立即將此句翻譯給聽眾，聽眾馬上了解演講者所講的這句話；如此一直到演講者講完為止。全譯法（為編譯程式的翻譯方式） 亦即讓演講者將整篇講稿講完後，翻譯員才將整篇講稿翻譯出來，而後聽眾才了解整個演講的內容。

.語言轉譯程式直譯器(Interpreter)直譯法的優點是：

1.在直譯法下，使用者欲執行程式時，一般是執行一條命令即可。2.直譯程式該翻譯程式在被使用者使用過程中，一般都儲存在主記憶體，所以當使用者每次執行程式時，不必浪費取出直譯程式的I/O時間。3.由於在直譯法下，使用者不需要執行連結的工作，所以可以省去不少有關連結工作的I/O時間。4.直譯程式在執行時，是採用交談式(Interactive)的方式。亦即使用者可以很容易的與電腦作溝通之工作。

.語言轉譯程式編譯器(Compiler)

欲利用編譯器來完成高階語言之翻譯然後執行時，一般需要逐次完成下列三個步驟後，才能完成使用者程式之執行工作。 1.產生目的程式 利用編譯程式將原始程式全部翻譯成機器語言程式，亦即翻譯成目的程式。 2.產生可執行之機器語言程式 利用廠商所提供的連結程式(Linker)執行連結的工作。此時才產生一個可執行的機器語言程式。該可執行的機器語言程式，在IBMPC下稱之為可執行程式(ExecutableProgram)，其延伸檔名(FilenameExtension)一般為EXE或COM。 3.執行程式 執行使用者程式，亦即執行機器語言程式。.程式語言的應用科學計算FORTRAN(MathematicalFORmulaTRANslatingSystem)商業應用COBOL(CommonBusinessLanguage)人工智慧LISP,Prolog系統程式語言C,C++.資料型態整數型態int：2bytes,-32768(-216)~+32767(+216-1)long：4bytes,-2147483648(-232)~+2147483647(+232-1)浮點數型態IEEE-754單精準度：Sign(1bit)+Exponent(8bits)+Mantissa(23bits)字符型態char：1byte,ASCII陣列型態一群具有相同資料型態的變數所組成，如intA[100]資料型態可為：整數，浮點數，字符…等。A[0]A[1]A[2]………………A[99].資料型態紀錄型態又稱為結構型態，存放的是不同類型的資料型態，由一群欄位(Field)所結合而成。指標型態指標型態所存放的值是位址。完成資料結構的好幫手。structscoretable{intid;charname;intscore[5];}student[100]inta;int*p;

a=10;P=&a;.變數的範疇(scope)靜態範疇依程式本身，變數的實際位置來決定。動態範疇依程式執行時，副程式的呼叫順序來決定。副程式sub1並未定義x的值為10。如果採用“靜態範疇”規則，印出的x=?為什麼？如果採用“動態範疇”規則，印出的x=?為什麼？PROGRAMmainINTEGERx;PROCEDUREsub1BEGINPRINTx;ENDPROCEDUREsub2INTEGERx;BEGINx=20;CALLsub1;ENDBEGINx=10;CALLsub2;END.副程式參數傳遞法形式參數副程式本身所定義的參數名稱及型態實際參數呼叫者(主程式)呼叫副程式時，所附上一些該有的參數。voidswap(inta,intb){intt;t=a;a=b;b=t;}main(){intx=5,y=10;swap(x,y);Printf(“%d,%d”.x,y);}形式參數實際參數.副程式參數傳遞法CallbyValue(傳值)僅將主程式實際參數的值，copy給副程式的形式參數，主程式實際參數的值不會改變，沒有sideeffect(副作用)。C語言只有callbyvalue5x10y5a10bvoidswap(inta,intb){intt;t=a;a=b;b=t;}main(){intx=5,y=10;swap(x,y);Printf(“%d,%d”.x,y);}5t/10/5.副程式參數傳遞法CallbyAddress(傳址)又稱“CallbyReference”將只程式實際參數的位址，傳給副程式的形式參數，主程式實際參數的值可能改變，有sideeffect(副作用)。C++採用CallbyAddress5x100010y15001000a1500b/10/5位址voidswap(inta,intb){intt;t=a;a=b;b=t;}main(){intx=5,y=10;swap(x,y);Printf(“%d,%d”.x,y);}1000t1500//1000.副程式參數傳遞法CallbyName(傳名)以實際參數的名稱取代形式參數(早期的做法)，有sideeffect(副作用)。voidswap(inta,intb){intt;t=a;a=b;b=t;}main(){intx=5,y=10;swap(x,y);Printf(“%d,%d”.x,y);}5x10y5a10b5t/10/5/x/y/10/5.副程式參數傳遞法CallbyValue/Result取代CallbyAddress，因為在分散式環境裡，主副程式的address配置不同，所以不能用CallbyAddress，有sideeffect(副作用)。voidswap(inta,intb){intt;t=a;a=b;b=t;}main(){intx=5,y=10;swap(x,y);Printf(“%d,%d”.x,y);}5x10y5a10b5t/10/510/5/.副程式參數傳遞法Homework_8請分別以下列參數傳遞法callbyvaluecallbyaddresscallbynamecallbyvalue/result寫出右列程式之最後輸出結果。programmain(input，output)；procedurep(x，y，z)；beginy：=y＋1；z：=z＋x；end；begina：=2；b：=3；p(a+b，a，a)；print"a="，a；end.副程式參數傳遞法請分別以下列參數傳遞法callbyvaluecallbyaddresscallbynamecallbyvalue/result寫出右列程式之最後輸出結果。main(){inta[5]={2,4,6,8,10};intx=1;f(x,a[x]);print“x=“,x;printa[0],a[1],a[2],a[3],a[4];}voidf(inti,intj){i=3;j=100;}.作業系統簡介.作業系統(OperatingSystem)的目的方便的人機介面命令列介面：Commandline，如DOS圖形化使用者介面：GUI(GraphicUserInterface)，如WindowsXP，MacOS等有效的管理資源Memory：虛擬記憶體(virtualmemory)Processor：程序排程(processscheduling)Device：死結(deadlock)Information：檔案(file)Others：載入(loader)，鏈結(linker)，庫存程式(library)，公用程式(utility).計算機作業方式Batch(批次)：將程式及資料事先準備好(一疊卡片，一個.bat檔)交給電腦一次完成。適用於周期性，時效要求低的作業。如：聯考閱卷，稅務申報等。

RealTime(即時)：輸入資料後立即處理，並在一定時限內產生輸出。(Responsetime≦時限)用於Special-Purpose電腦系統，如飛機自動導航/駕駛系統，證卷交易系統。(事關人命，金錢交易).計算機作業方式On-Line(線上作業)

Off-Line(離線作業)I/O設備與主機有實體連線，能立即作I/O處理，為Realtime的必要條件。變化：分散式系統中，電腦透過網路，與系統取得連線。Time-Sharing(分時作業)Multiprogramming的一種，各程式分配一段時間輪流交替執行，為最普遍的執行方式(公平，簡單，效果不錯)Multiprogramming：電腦Memory內有2個以上互不相關的程式可同時被執行，CPU交替執行之，使得User產生電腦專屬執行某一程式的錯覺。由OS控制.計算機作業方式Multiprogramming(多工程式處理)-1970’s同時(currently)執行數個程式(以軟體方式)，各個程式感覺是同時執行。Multiprocessing(多元處理)-1970’s同時(simultaneously)執行數個程式(以硬體方式)，格個程式真正是同時執行。Multitasking(多工處理)-1980’s電腦Memory內有2個以上屬於同一程式的工作(task)可被同時執行。Task：執行一個特定功能的一段程序(副程式)Multithreading(多序執行)-1990’s如Java.VirtualMemory虛擬記憶體優點使User的程式不受實際Memory容量的限制。Memory內部程式/資料的保護。Memory內部資訊的共享(sharing)。作法DemandPage(分頁)：以Mem的使用為主，將程式/資料分成等量大小(頁)，沒有fragment(碎片)。DemandSegment(分段)：以程式的保護為主，根據程式性質，分成數個大小不同的區段(段)，有fragment(碎片)。.VirtualMemory虛擬記憶體PageFault代換策略FIFO(FirstInFirstOut)先進先出，最直觀，效果差LRU(LeastRecentlyUsed)最近最久未用，合理Optimal最晚才會再用，最佳，理論上限Random：實際上使用CPUMainMemoryPageframePageframePageframePageframeHardDiskPage1Page2Page3Page4Page5Page6Page7Page8Page9Page10某段程式或一段資料例：CPU需要順序(頁參考順序)：1,3,6,9,10,4,7…Page1Page3Page6Page9？PageFault.PageFault代換策略實作FIFO(先進先出)頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0Pageframe=3參考順序01234215672374560PF0PF1PF2PageFault＊＊＊＊＊＊＊＊＊＊＊＊000033335552222551111444466633336222221117777444共發生pagefault(＊)=次34＊＊＊156723456015.自我練習FIFO(先進先出)頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0Pageframe=4參考順序PF0PF1PF2PF3Fault共發生pagefault(＊)=次.0PageFault代換策略實作LRU(最近最久未用)LeastRecentlyUsed頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0Pageframe=3參考順序01234215672374560PF0PF1PF2PageFault＊＊＊＊＊＊＊＊＊＊＊＊0共發生pagefault(＊)=次3＊＊＊15033311177777760111444555222444122222266633355241567234560.自我練習LRU(最近最久未用)LeastRecentlyUsed頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0Pageframe=4參考順序PF0PF1PF2PF3Fault共發生pagefault(＊)=次.PageFault代換策略實作Optimal(取代最晚才會再用的)效果最好理論上限，但不可行頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0Pageframe=3參考順序01234215672374560PF0PF1PF2PageFault＊＊＊＊＊＊＊＊＊＊＊＊0共發生pagefault(＊