109 專技高考高等考試 資訊技師 計算機系統 考古題詳解

109 年・專技高考・高等考試・資訊技師
試題代碼 計算機系統

第 一 題10 分

針對多工(Multi-Programming)的作業系統:

(一) 請畫出一個 Process 的五種狀態關係圖。

(二) 請指出一個 PCB(Process Control Block)必須要維護的基本資訊有哪些。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題評量作業系統(Operating System)核心之「行程管理(Process Management)」機制,聚焦於兩大經典考點:

  1. 行程五狀態模型(Five-State Process Model):依據作業系統權威教科書(Silberschatz 之《Operating System Concepts》),行程在其生命週期中會因 CPU 排班、中斷(Interrupt)及 I/O 事件而在不同狀態間移轉。
  2. 行程控制區塊(Process Control Block, PCB):PCB 是作業系統核心用來追蹤、保存與排班管理各行程的資料結構(Data Structure),又稱為工作控制區塊(Task Control Block)。當進行內文切換(Context Switch)時,PCB 負責保存行程的硬體執行狀態,以確保後續能正確復原執行。

解題方法

  1. 第 (一) 小題——五狀態關係圖之繪製:
  • 先定位五大核心狀態節點:New(新建)、Ready(就緒)、Running(執行)、Waiting / Blocked(等待/阻塞)、Terminated(終止)。
  • 正確標記狀態轉移的 6 條方向性箭頭,並於各箭頭旁清楚標註觸發的系統事件(如:Admitted、Scheduler Dispatch、Interrupt、I/O wait、I/O completion、Exit)。
  1. 第 (二) 小題——PCB 基本維護資訊之條列:
  • 採系統化架構分類列述,避免雜亂無章。依據功能層次涵蓋:行程狀態、程式計數器、CPU 暫存器群、CPU 排班資訊、記憶體管理資訊、會計/記帳資訊、I/O 狀態資訊。
  • 每項資訊均須具體說明其「紀錄內容」與「作業系統維護該項資訊的目的」。

選項分析

本題為申論問答題,無選擇題選項。針對國考評分標準,考生常見的觀念盲點與狀態移轉正誤分析如下:

  • Waiting →\rightarrow Running(錯誤):I/O 完成或事件發生後,行程絕不可直接奪回 CPU 進入 Running;必須先回到 Ready 佇列等待 CPU 排班器(Scheduler)重新指派。
  • New →\rightarrow Running(錯誤):剛建立的行程必須先經作業系統長期排班器(Long-term Scheduler)配置記憶體後送入 Ready 佇列,不可直接上 CPU 執行。
  • Ready ↔\leftrightarrow Running(正確,雙向關係):Ready 經排班分派(Dispatch)進入 Running;Running 因時間配額(Time Slice)用盡中斷,則退回 Ready。
  • Running →\rightarrow Waiting(正確,單向關係):行程主動提出 I/O 請求或等待同步事件,放棄 CPU 進入 Waiting。

解題技巧

  1. 繪圖口訣——「新就執等終」:
  • 排版佈局採「中間三狀態(Ready、Running、Waiting)形成三角迴圈,左為 New、右為 Terminated」,版面整齊、不易漏畫箭頭。
  1. 箭頭方向檢核竅門:
  • 整個圖形中,只有 Ready 與 Running 之間是雙向的(一去一回),其餘皆為單向路徑。
  • Waiting 狀態「只進不出到 CPU」:只接受來自 Running 的輸入,輸出只能通往 Ready。
  1. PCB 記憶口訣——「態、計、暫、排、記、帳、設」:
  • 狀態(State)、程式計數器(PC)、暫存器(Registers)、排班資訊(Scheduling)、記憶體資訊(Memory)、記帳資訊(Accounting)、I/O 設備資訊(I/O Status)。

【答案】

(一) 行程五種狀態關係圖(Five-State Process Model)

🔒

後續完整解題步驟與【答案】

免費註冊,享 3 天全站完整詳解閱覽。

免費註冊

第 二 題10 分

請詳述 CISC 的架構與 RISC 的架構在下列兩項的不同點:

(一) 每個指令需要到記憶體存取的次數。

(二) 指令管線(Instruction Pipeline)的效率。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題評量計算機系統結構(Computer Architecture)中兩大經典指令集架構(ISA)——**CISC(複雜指令集電腦)**與 RISC(精簡指令集電腦) 的本質差異,核心概念涵蓋:

  1. 指令集設計哲學與執行時間公式: CPU Execution Time=IC×CPI×τ\text{CPU Execution Time} = \text{IC} \times \text{CPI} \times \tau 其中 IC\text{IC} 為指令總數(Instruction Count),CPI\text{CPI} 為每指令平均週期數(Cycles Per Instruction),τ\tau 為時脈週期時間(Clock Cycle Time)。CISC 追求降低 IC\text{IC},而 RISC 追求降低 CPI\text{CPI} 與 τ\tau。
  2. 記憶體存取模式(Memory Access Pattern):
  • Load/Store 架構:運算指令僅限於暫存器之間操作,唯有專屬的載入/儲存指令方能存取記憶體。
  • Memory-to-Memory / Register-to-Memory 架構:運算指令可直接以記憶體位址作為來源或目的運算元。
  1. 指令管線(Instruction Pipeline)效率要素:
  • 管線級數平衡(Stage Balance)、指令格式一致性(Regularity)、解碼複雜度(Hardwired vs. Microprogrammed)、管線衝擊與停頓(Pipeline Hazards / Stalls)。

解題方法

解答本科申論題時,應採用「先提設計核心機制,再作量化與定性對比」之結構化寫法:

  1. 子題 (一) 記憶體存取次數:
  • 拆解「單一指令生命週期」的存取需求:指令擷取(Instruction Fetch, IF) 階段與 資料存取(Data Memory Access, MEM) 階段。
  • 分析 CISC 之變長指令與複雜定址模式對記憶體存取次數的累加效應。
  • 分析 RISC 之固定長度與 Load/Store 限制如何將單一指令記憶體存取次數嚴格約束在 11 次(純運算)或 22 次(載入/儲存)。
  1. 子題 (二) 指令管線效率:
  • 從管線理想效能指標 CPI≈1\text{CPI} \approx 1 切入。
  • 分別從「指令長度與格式」、「控制單元設計(微程式 vs. 硬體布線)」、「各階段執行時間之均勻度」以及「管線危障(Hazards)發生率」四個維度,嚴謹論證兩者管線輸送量(Throughput)之高低。

選項分析(本題為申論題,評分要點對比剖析)

本題非選擇題,評閱標準取決於考生能否精準對比以下指標:

評比維度CISC 架構RISC 架構命題得分焦點
(一) 單指令記憶體存取次數次數多且不固定<br>(可能高達 3∼43\sim 4 次以上)嚴格受限且固定<br>(非 Load/Store 指令為 1 次;Load/Store 為 2 次)須指出 RISC 的 Load/Store 架構 與 CISC 支援 Memory Operand 的根本差異。
(二) 管線效率與 CPI管線效率低<br>(CPI 遠大於 1,管線時鐘受限於最長階段)管線效率高<br>(CPI 趨近於 1,時脈頻率高)須說明 指令等長、硬體解碼、各階段延遲均衡 對消除管線停頓的決定性作用。

解題技巧

  1. 切忌遺漏「指令擷取(IF)」階段:許多考生只計算「運算元(Operand)」存取記憶體的次數,而忽略了指令本體從記憶體載入也算一次記憶體存取。
  2. 精確使用架構專有名詞:提及 RISC 必提「Load/Store Architecture」與「Hardwired Control」;提及 CISC 必提「Variable-length Instructions」與「Microprogrammed Control」。
  3. 管線效率的量化指標:討論效率時,使用「Throughput(輸送量)」與「CPI→1\text{CPI} \to 1」作答,能大幅提升答題專業度。

🔒

後續完整解題步驟與【答案】

免費註冊,享 3 天全站完整詳解閱覽。

免費註冊

第 三 題20 分

請詳述 Shared-Memory Multiprocessors 與 Message-Passing Multicomputer 在下列功能的差異:

(一) 通訊成本(Communication Cost)。

(二) 可程式(Programming)的方便性。

(三) Cache 的一致性(Consistency)。

(四) 可擴充性(Scalability)。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題評量平行計算機架構(Parallel Computer Architecture)中兩大主流模型——**共享記憶體多處理機(Shared-Memory Multiprocessors)與訊息傳遞多計算機(Message-Passing Multicomputer)**的硬體設計與軟體執行特性:

  1. 共享記憶體多處理機(Shared-Memory Multiprocessors,常稱 Multiprocessors 或 SMP/NUMA):
  • 所有處理器共用單一全域實體位址空間(Single Global Physical Address Space)。
  • 處理器之間透過對相同記憶體位址執行一般指令(Load / Store)達成隱式通訊(Implicit Communication)。
  1. 訊息傳遞多計算機(Message-Passing Multicomputer,常稱 Multicomputer 或 Cluster/MPP):
  • 每個節點(處理器)擁有各自獨立且封閉的私有記憶體位址空間(Disjoint/Private Address Space)。
  • 節點間無法直接存取對方的記憶體,必須透過互連網路(Interconnection Network),以常規的 I/O 函式庫或系統呼叫(如 Send、Receive,常見標準為 MPI)進行顯式通訊(Explicit Communication)。

解題方法

本題為典型的申論比較題,評分標準取決於能否從「底層硬體機制」連結到「上層軟體抽象層」,並針對題目指定的四項評估指標切入分析:

  • 通訊成本:從「通訊機制(硬體匯流排 vs. 網路協定堆疊)」與「延遲(Latency)/頻寬(Bandwidth)/軟體額外負擔(Software Overhead)」切入。
  • 可程式方便性:從「程式設計師心智模型(單一位址空間 vs. 分散位址空間)」、「資料分割責任」與「同步除錯難度」切入。
  • 快取一致性:從「硬體是否允許多份相同位址資料存在於不同處理器的快取中」切入。
  • 可擴充性:從「系統架構瓶頸(記憶體匯流排頻寬、一致性通訊量 vs. 模組化網路拓撲)」切入。

深入分析與功能差異比較

(一) 通訊成本(Communication Cost)

通訊成本包含通訊延遲(Latency)、傳輸頻寬(Bandwidth)以及 CPU 處理通訊所消耗的軟體額外負擔(Software Overhead):

  1. Shared-Memory Multiprocessors:
  • 成本極低(低延遲、低額外負擔)。
  • 資料交換直接在實體記憶體或快取層級完成,僅需透過硬體執行記憶體的讀寫操作(Memory Read/Write 指令)。
  • 通訊過程完全由硬體控制器與匯流排/交錯開關(Crossbar Switch)處理,不需要作業系統核心(OS Kernel)介入,無封包打包(Packetization)、通訊協定堆疊解析或記憶體多次複製(Buffer Copying)的負擔。
  1. Message-Passing Multicomputer:
  • 成本較高(高延遲、高額外負擔)。
  • 通訊需仰賴呼叫訊息傳遞協定介面(如 MPI)。
  • 訊息需經過作業系統中斷、資料緩衝區複製、封包化、網路卡傳輸協定處理(如 TCP/IP 堆疊,即便使用 RDMA 亦有網路介面延遲)。每個訊息交換涉及較高的啟動延遲(Start-up Latency / Overhead),微秒(μs\mu\text{s})級的網路延遲遠高於奈秒(ns\text{ns})級的記憶體匯流排存取。

(二) 可程式(Programming)的方便性

  1. Shared-Memory Multiprocessors:
  • 入門容易、資料共享直觀,但並行除錯困難。
  • 優點:程式設計師面對的是單一平坦的位址空間,撰寫多執行緒程式(如 OpenMP、Pthreads)非常平覺。程式設計師不需要顯式定義資料存放於何處,可隨時透過全域變數存取共用資料。
  • 缺點:競爭條件(Race Conditions)、死結(Deadlocks)及臨界區間(Critical Section)互斥控制難以掌握。由於資料隱式共享,除錯與效能調校(如避免虛假共享 False Sharing)複雜度高。
  1. Message-Passing Multicomputer:
  • 架構繁瑣、資料配置痛苦,但狀態隔離明確。
  • 缺點:程式設計師必須手動對問題與資料結構進行「領域分解(Domain Decomposition)」,並明確寫出每個節點何時透過 Send 與 Receive 傳送何種資料結構,開發門檻高、程式碼規模龐大。
  • 優點:各節點位址空間相互隔離,不存在共用變數被多執行緒同時修改的競爭條件問題;程式的同步點(如 Barrier 或通訊完成)明確,除錯時追蹤狀態轉移相對直觀。

(三) Cache 的一致性(Consistency / Coherence)

當多個處理器各自的私人快取(Private Cache)同時保留同一塊主記憶體區塊的副本時,若有處理器修改該區塊,就必須保證所有處理器都能讀到最新數值,此即快取一致性問題:

  1. Shared-Memory Multiprocessors:
  • 必須由硬體全力維護(實作複雜度高)。
  • 由於所有處理器共用位址空間,相同記憶體位址的多份快取複本必然存在。硬體必須實作快取一致性協定(Cache Coherence Protocol),主要分為:
  • 窺探協定(Snooping Protocol):利用共用廣播匯流排監聽所有快取存取(適用於小型系統)。
🔒

後續完整解題步驟與【答案】

免費註冊,享 3 天全站完整詳解閱覽。

免費註冊

第 四 題20 分

請執行以下三行組合語言的指令,其中 H 代表 1616 進位且二進位數的最左一個位元是代表正數或負數的位元:

MOVAX, C23HMOVBX, E85HADDAX, BX\begin{aligned} \mathrm{MOV}\quad &\mathrm{AX},\ \mathrm{C23H}\\ \mathrm{MOV}\quad &\mathrm{BX},\ \mathrm{E85H}\\ \mathrm{ADD}\quad &\mathrm{AX},\ \mathrm{BX} \end{aligned}

請列出執行加法後的結果(使用 1616 進位表示)與以下四個旗標(Flags)的值:Carry Flag(CF)、Overflow Flag(OF)、Odd Parity Flag(OPF)、Sign Flag(SF)。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題主要測驗計算機算術運算(Computer Arithmetic)與處理器狀態旗標(Status Flags)的判定機制:

  1. 二進位有號數表示法(二補數系統,2's Complement): 題幹明確指示「二進位數的最左一個位元是代表正數或負數的位元」,且運算元 C23H\mathrm{C23H} 與 E85H\mathrm{E85H} 各由 3 個十六進位數碼組成(即 3×4=12 位元3 \times 4 = 12\text{ 位元})。在有號數系統中,最高有效位元(MSB)即為符號位元:00 代表正數、11 代表負數。
  2. 狀態旗標之定義與判定準則:
  • 進位旗標(Carry Flag, CF):針對無號數(Unsigned)運算設計。當最高有效位元產生進位輸出(Carry-out, CoutC_{\mathrm{out}})或借位時,CF=1\mathrm{CF} = 1;否則為 00。
  • 溢位旗標(Overflow Flag, OF):針對有號數(Signed)運算設計。當兩個同號數相加卻產生異號結果時發生溢位;在硬體邏輯上,以「最高位元的進位輸入 CinC_{\mathrm{in}}」與「進位輸出 CoutC_{\mathrm{out}}」進行互斥或(XOR)運算判定: OF=Cin⊕Cout\mathrm{OF} = C_{\mathrm{in}} \oplus C_{\mathrm{out}}
  • 符號旗標(Sign Flag, SF):反映運算結果的代數符號,其值直接等於運算結果的最高有效位元(MSB)。若 MSB=1\mathrm{MSB} = 1,則 SF=1\mathrm{SF} = 1(負數);若 MSB=0\mathrm{MSB} = 0,則 SF=0\mathrm{SF} = 0(正數)。
  • 奇同位旗標(Odd Parity Flag, OPF):檢驗運算結果二進位數碼中「11 的總個數」。若 11 的個數為奇數(Odd),則 OPF=1\mathrm{OPF} = 1;若為偶數(Even),則 OPF=0\mathrm{OPF} = 0。(註:x86 傳統架構內建為偶同位旗標 PF\mathrm{PF},本題依題意明確指定為「Odd Parity Flag」)。

解題方法

步驟一:將十六進位數展開為 12 位元二進位數並判斷符號

  • AX=C23H=1100 0010 00112\mathrm{AX} = \mathrm{C23H} = 1100\ 0010\ 0011_2(最高位元為 11,為負數)
  • BX=E85H=1110 1000 01012\mathrm{BX} = \mathrm{E85H} = 1110\ 1000\ 0101_2(最高位元為 11,為負數)

步驟二:執行二進位加法運算並追蹤各級進位

依位元位置由右至左(由第 0 位元 LSB 至第 11 位元 MSB)逐位相加:

bit 11∼bit 8bit 7∼bit 4bit 3∼bit 0C23H+E85H(1)AA8H\begin{array}{rcccc} & \text{bit 11} \sim \text{bit 8} & \text{bit 7} \sim \text{bit 4} & \text{bit 3} \sim \text{bit 0} & \\ & \mathrm{C} & 2 & 3 & \mathrm{H} \\ + & \mathrm{E} & 8 & 5 & \mathrm{H} \\ \hline (1) & \mathrm{A} & \mathrm{A} & 8 & \mathrm{H} \end{array}

各項細部二進位加法推導如下:

  1. 第 0∼30 \sim 3 位元(最低 Nibble): 00112+01012=10002=8160011_2 + 0101_2 = 1000_2 = 8_{16},向第 4 位元進位 00。
  2. 第 4∼74 \sim 7 位元(中間 Nibble): 00102+10002+0=10102=A160010_2 + 1000_2 + 0 = 1010_2 = \mathrm{A}_{16},向第 8 位元進位 00。
  3. 第 8∼118 \sim 11 位元(最高 Nibble):
  • 第 8 位元:0+0+0=00 + 0 + 0 = 0,進位 00。
  • 第 9 位元:0+1+0=10 + 1 + 0 = 1,進位 00。
🔒

後續完整解題步驟與【答案】

免費註冊,享 3 天全站完整詳解閱覽。

免費註冊

第 五 題20 分

解釋並詳細比較下列名詞的不同點:

(一) Multi-Core vs. VM(Virtual Machines)

(二) DRAM vs. SDRAM

(三) Direct-Mapping Cache vs. Fully-Associate Cache

(四) Parallelism vs. Pipelining

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題為計算機架構(Computer Architecture)與計算機組織的核心經典比較題,主要測驗考生對計算機硬體層次、記憶體階層、處理器效能加速技術之基本原理與架構特性的掌握程度:

  1. 處理器與虛擬化架構(Hardware vs. System Virtualization):評估多核心處理器(實體硬體複製)與虛擬機器(軟體抽象化隔離)在架構層次、資源管理與隔離機制上的本質差異。
  2. 記憶體介面控制技術(Asynchronous vs. Synchronous Memory):測驗動態隨機存取記憶體(DRAM)由傳統「非同步交握(Asynchronous Handshaking)」演進至「同步時脈匯流排(Synchronous Clocked Bus)」之控制時序與資料傳輸原理。
  3. 快取記憶體對應策略(Cache Mapping Policies):依據組相聯公式評估區塊對應靈活度、硬體比較器成本及失誤率(Cache Misses):
  • 直接對應(Direct-Mapping):區塊位置固定,即 Line Index=(Block Address)(modNumber of Lines)\text{Line Index} = (\text{Block Address}) \pmod{\text{Number of Lines}}。
  • 全關聯(Fully-Associative):區塊可放置於任意快取行,需平行比對所有標籤(Tags)。
  1. 平行運算與效能優化概念(Spatial Parallelism vs. Temporal Concurrency):釐清「空間平行(硬體倍增平行運作)」與「時間重疊(管線化切分時槽重疊運作)」之根本原理。

解題方法

解答國家考試此類名詞比較題,切忌僅以零散條列隨意書寫。標準參考書級的答題結構應遵循「定義 →\rightarrow 運作架構/機制 →\rightarrow 關鍵向度綜合比較表 →\rightarrow 優缺點總結」,以確保閱卷委員能一目了然其深度與廣度:

  1. 名詞個別精確定義:給出權威且標準的學術定義,避免語意含糊。
  2. 架構層次切入:區分該技術屬於「硬體層(Hardware)」、「韌體/Hypervisor 層」或「微架構層(Microarchitecture)」。
  3. 結構化比較矩陣(Comparison Table):選取一致且具區別性的維度(如:實現層級、硬體成本、延遲/吞吐量、瓶頸與限制)進行對稱比較。

解題技巧

  1. 辨析關鍵字母陷阱:
  • 「SDRAM vs. DRAM」之「S」為 Synchronous(同步),絕非 Static(靜態);切勿將 SDRAM 誤答為 SRAM。
  • Fully-Associate 即 Fully-Associative(全相聯/全關聯快取)。
  1. 快取比較公式化:
  • 記憶體位址切割:直接對應為「Tag + Index + Offset」;全關聯為「Tag + Offset」(無 Index 欄位)。
  • 碰撞失誤(Conflict Miss):直接對應快取的致命傷是碰撞失誤(Thrashing);全關聯快取在容量足夠下無任何碰撞失誤(Conflict Miss =0= 0)。
  1. 平行與管線之時空對比法則:
  • 平行性(Parallelism)是「空間上的多工(Spatial Concurrency)」,靠硬體倍增;
  • 管線化(Pipelining)是「時間上的重疊(Temporal Concurrency)」,靠階段切割。

【答案】

(一) Multi-Core vs. VM(Virtual Machines)

1. 名詞解釋

  • Multi-Core(多核心處理器): 指在單一實體晶片(Die/Chip)或單一處理器封裝內,整合了兩個或兩個以上獨立的實體運算核心(Cores)。每個核心具備獨立的微架構執行單元(ALU、暫存器、解碼器),通常各自擁有第一階快取(L1 Cache),並共用晶片上的末級快取(LLC/L3 Cache)、記憶體控制器及系統匯流排,在硬體層次上真正達到硬體線程的同時平行執行(Hardware Parallelism)。
  • VM(Virtual Machines,虛擬機器): 是一種軟體或系統虛擬化技術。透過虛擬機器監視器(Hypervisor / Virtual Machine Monitor, VMM,如 Type-1 Bare-metal 或 Type-2 Hosted),將底層實體的硬體資源(CPU、記憶體、I/O 裝置等)抽象化,分割並虛擬化成數個邏輯上獨立的計算單元。每個虛擬機器內部均可運行獨立且相異的作業系統(Guest OS)及應用程式。

2. 詳細差異比較

比較維度Multi-Core(多核心)VM(虛擬機器)
實現層級純實體硬體層(晶片微架構整合)系統軟體/虛擬化層(Hypervisor/VMM)
主要目的突破單核時脈牆(Frequency Wall),提升硬體運算吞吐量提高實體硬體利用率、伺服器整合、環境隔離與遷移
資源配置機制核心屬於固定實體資產,共用晶片內記憶體匯流排由 Hypervisor 動態調配與排程虛擬資源(vCPU、vRAM)
隔離安全性共用快取與記憶體匯流排,易受微架構側信道攻擊(如 Spectre)具備高度作業系統層級隔離,單一 VM 崩潰不影響其他 VM
額外開銷(Overhead)極低(純硬體原生速度,僅有快取一致性協定開銷)較高(CPU 特權切換、影子分頁/EPT 轉換、I/O 模擬開銷)
作業系統需求通常由單一作業系統管理所有實體核心每一虛擬機器皆需載入獨立完整的客體作業系統(Guest OS)

(二) DRAM vs. SDRAM

1. 名詞解釋

  • DRAM(Dynamic Random Access Memory,傳統非同步動態隨機存取記憶體): 利用電容儲存電荷、單一電晶體作為開關(1T-1C 架構)構成記憶單元,因電容會隨時間自然漏電,必須定期進行重新整理(Refresh)。其介面屬於**非同步(Asynchronous)**架構,記憶體控制器的存取信號(RAS‾\overline{\text{RAS}}、CAS‾\overline{\text{CAS}}、WE‾\overline{\text{WE}})並未與系統匯流排或處理器的主時脈信號同步,每次存取時 CPU 必須發出控制信號並等待固定的傳遞延遲(如 tRACt_{\text{RAC}})後再行讀寫,易造成匯流排等待週期。
  • SDRAM(Synchronous DRAM,同步動態隨機存取記憶體): 內部記憶單元同樣為動態電容結構,但其外部介面與內部控制邏輯皆與系統時脈(System Clock)完全同步。
🔒

後續完整解題步驟與【答案】

免費註冊,享 3 天全站完整詳解閱覽。

免費註冊

第 六 題20 分

當我們使用 Hamming Single-Error Correction Code 在 Code Word = 1001101110011011 時,假設 D1 是最右邊的位元,D8 是最左邊的位元:

(一) 請計算出 4 個位元的 Syndrome word。

(二) 假如 D6 有錯誤,且已經從 00 變成 11,請詳述 Hamming Code 是如何檢查出錯誤的位元是在 D6。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

  1. 漢明碼(Hamming Code)架構原理: 漢明碼為一種能實現「單一錯誤更正(Single-Error Correction, SEC)」的線性區塊碼(Linear Block Code)。其核心精神是將同位檢查位元(Parity bits)安排在位置編號為 2k2^k(即第 1,2,4,8,…1, 2, 4, 8, \dots 個位元)之處,其餘位置則放置資料位元(Data bits)。
  2. 同位檢查群組劃分(偶同位原則,Even Parity): 每個同位位元各自負責檢查「位置編號的二進位表示中,對應位元為 11」的所有位元集合:
  • 第 11 位元(202^0):檢查二進位最低位為 11 的位置(1,3,5,7,…1, 3, 5, 7, \dots)。
  • 第 22 位元(212^1):檢查二進位次低位為 11 的位置(2,3,6,7,…2, 3, 6, 7, \dots)。
  • 第 44 位元(222^2):檢查二進位第 3 位為 11 的位置(4,5,6,7,…4, 5, 6, 7, \dots)。
  • 第 88 位元(232^3):檢查二進位第 4 位為 11 的位置(8,9,10,…8, 9, 10, \dots)。
  1. 校驗子(Syndrome Word)定義: 在接收端,將各檢查群組的所有位元進行模二加法(XOR 運算)所得出的結果稱為校驗子 S=S4S3S2S1S = S_4 S_3 S_2 S_1(亦常記為 C8C4C2C1C_8 C_4 C_2 C_1)。
  • 若碼字完全無誤,校驗子為 000020000_2。
  • 若發生單一位元錯誤,校驗子轉成十進位的數值,剛好等於該錯誤位元的位置編號。

解題方法

題目給定 8 位元的碼字 Code Word=10011011\text{Code Word} = 10011011。 依題目定義,最左邊位元為 D8D_8,最右邊位元為 D1D_1,各位置位元數值對照如下:

位元名稱D8D_8D7D_7D6D_6D5D_5D4D_4D3D_3D2D_2D1D_1
位置編號(Position)87654321
位置二進位表示100021000_2011120111_2011020110_2010120101_2010020100_2001120011_2001020010_2000120001_2
位元數值(Bit Value)10011011
位元性質同位元 P8P_8資料位元資料位元資料位元同位元 P4P_4資料位元同位元 P2P_2同位元 P1P_1

(一) 計算 4 個位元的 Syndrome word

在 8 位元的漢明碼字中,設 4 個位元的 Syndrome word 為 S=S4S3S2S1S = S_4 S_3 S_2 S_1(分別對應權重 23,22,21,202^3, 2^2, 2^1, 2^0)。各校驗子位元的偶同位檢查式及計算如下:

  1. 計算 S1S_1(檢查位置 1,3,5,71, 3, 5, 7): S1=D1⊕D3⊕D5⊕D7=1⊕0⊕1⊕0=0S_1 = D_1 \oplus D_3 \oplus D_5 \oplus D_7 = 1 \oplus 0 \oplus 1 \oplus 0 = 0

  2. 計算 S2S_2(檢查位置 2,3,6,72, 3, 6, 7): S2=D2⊕D3⊕D6⊕D7=1⊕0⊕0⊕0=1S_2 = D_2 \oplus D_3 \oplus D_6 \oplus D_7 = 1 \oplus 0 \oplus 0 \oplus 0 = 1

  3. 計算 S3S_3(檢查位置 4,5,6,74, 5, 6, 7): S3=D4⊕D5⊕D6⊕D7=1⊕1⊕0⊕0=0S_3 = D_4 \oplus D_5 \oplus D_6 \oplus D_7 = 1 \oplus 1 \oplus 0 \oplus 0 = 0

  4. 計算 S4S_4(檢查位置 88): S4=D8=1S_4 = D_8 = 1

將四個位元組合為 Syndrome word(由高位至低位 S4S3S2S1S_4 S_3 S_2 S_1): S=10102S = 1010_2

觀念補充:

  1. 若題目給定的 Code Word 為接收端收到的碼字,直接代入同位檢驗方程式計算所得之校驗子即為 101021010_2。
🔒

後續完整解題步驟與【答案】

免費註冊,享 3 天全站完整詳解閱覽。

免費註冊

其他考古題