繁體中文
選單

資訊理論與編碼基礎

以計算題為主的三選一題型，學習資訊量與熵、互資訊、冗餘度、固定長度碼與可變長度碼、前綴碼與克拉夫特不等式、霍夫曼編碼的平均碼長與效率、行程長度編碼、LZ77方式、無失真壓縮與有失真壓縮、同位位元與垂直水平同位檢查、檢查和、循環冗餘檢查（CRC）的計算、漢明距離與錯誤偵測、更正的能力、漢明碼與SECDED、碼率、交錯、ARQ與FEC、二元對稱通道的通道容量、通道編碼定理，以及格雷碼的轉換。

練習10題從本領域隨機抽取10題 · 約5分鐘 練習這個領域以隨機順序出題，涵蓋這個領域的所有題目 弱項題目只重做最近答錯的題目

資訊理論與編碼基礎的重點

「這個資訊值多少位元？」「這筆資料最多能縮小到什麼程度？」「被雜訊弄錯的位元，要怎麼找出來並修正？」回答這類問題的，就是由夏農開創的資訊理論與編碼理論。檔案壓縮、記憶體的ECC、通道的錯誤更正、儲存裝置的CRC等，在電腦與通訊的各個地方都會用到。

本單元先透過計算確認資訊量 −log₂ p 與熵、熵達到最大的條件、條件熵與互資訊、冗餘度，以及區分所需的位元數。接著學習固定長度碼與可變長度碼、前綴碼與克拉夫特不等式、霍夫曼編碼的做法與平均碼長、與熵相比的效率、把符號合併編碼的效果、行程長度編碼與LZ77方式，以及無失真壓縮與有失真壓縮的區分使用。後半部介紹同位位元與垂直水平同位檢查、檢查和的弱點、CRC檢查位元的計算與叢發錯誤的偵測、漢明距離與可偵測、更正的錯誤位元數、以漢明碼(7, 4)的症狀找出錯誤位置、SECDED的檢查位元數、碼率、交錯、ARQ與FEC，以及二元對稱通道的通道容量與通道編碼定理，最後確認格雷碼的轉換。有助於準備日本資訊技術人員考試中基礎理論（資訊相關理論、通訊相關理論）的範圍。計算題的數值，包括錯誤選項的數值與霍夫曼編碼的樹，都已用 Python 計算確認。二進位數與浮點數在「電腦算術」，同位位元的計算與格雷碼的性質在「邏輯電路」，二進位轉格雷碼在「時序分析與CDC」，同位檢查漏掉錯誤的機率在「機率、統計與等候理論」，以夏農-哈特利定理計算通道容量在「無線通訊基礎」，記憶體的ECC在「DRAM」，8b/10b編碼與PCI Express的CRC在「介面與匯流排規格」，Base64與gzip在「Web技術基礎」，交叉熵在「機器學習基礎」，雜湊與加密則在「資訊安全基礎」單元中介紹。

資訊理論與編碼基礎的題目列表（40題）
  1. 設事件的機率為p時，得知該事件發生所獲得的資訊量為 −log₂ p 位元。得知機率為1/8的事件發生時，所獲得的資訊量為下列何者？
  2. 關於資訊量（得知機率為p的事件發生時的 −log₂ p）的性質，下列何者正確？
  3. 某資訊源分別以機率1/2、1/4、1/8、1/8彼此獨立地輸出符號A、B、C、D。此資訊源的熵（每個符號的平均資訊量）為下列何者？
  4. 輸出8種符號之資訊源的熵的最大值，與達到最大值的條件，下列組合何者正確？
  5. 某二元資訊源以機率0.9輸出0、以機率0.1輸出1，且彼此獨立。設 log₂ 0.9 ≈ −0.152、log₂ 0.1 ≈ −3.32。此資訊源的熵最接近下列何者？
  6. 某輸出8種符號之資訊源的熵為2.4位元。若冗餘度定義為 1 −（熵 ÷ 最大熵），此資訊源的冗餘度為下列何者？
  7. 關於兩個隨機變數X、Y的條件熵 H(X|Y) 與互資訊 I(X;Y)，下列說明何者正確？
  8. 兩個隨機變數X（值為0或1）與Y（值為a、b、c之一）的聯合機率為 P(0, a) = P(0, b) = P(1, b) = P(1, c) = 1/4，其他組合的機率為0。互資訊 I(X;Y) 為下列何者？
  9. 想以長度全部相同的位元串（固定長度碼）區分英文大寫字母26種與數字10種，共36種字元。每個字元所需的最少位元數為下列何者？
  10. 與固定長度碼相比，下列關於可變長度碼的說明何者正確？
  11. 下列分配給4個符號的碼字組合中，何者是前綴碼（任何碼字都不是其他碼字開頭部分的碼）？
  12. 某前綴碼對符號A、B、C、D分配碼字 A = 0、B = 10、C = 110、D = 111。從開頭解碼位元串 110100111 的結果為下列何者？
  13. 想對4個符號A～D分配下列長度（位元數）的碼字，做成由0與1構成的前綴碼。能做成前綴碼的碼長組合為下列何者？
  14. 正在製作由0與1構成的前綴碼，已經使用了長度2的碼字 00 與 01。在維持前綴碼條件下，可以追加之長度3碼字的最大個數為下列何者？
  15. 某資訊源以機率0.4、0.3、0.2、0.1彼此獨立地輸出符號A、B、C、D，以霍夫曼編碼進行編碼。每個符號的平均碼長為下列何者？
  16. 某資訊源以機率0.3、0.25、0.2、0.15、0.1彼此獨立地輸出符號A～E，以霍夫曼編碼進行編碼。相等的機率先選哪一個，可能會使碼字不同，但平均碼長不變。每個符號的平均碼長為下列何者？
  17. 某資訊源以機率0.6、0.3、0.1彼此獨立地輸出符號A、B、C，其熵約為1.30位元。以霍夫曼編碼對此資訊源編碼時，效率（熵 ÷ 平均碼長）最接近下列何者？
  18. 某二元資訊源以機率0.8輸出0、以機率0.2輸出1，且彼此獨立。把每2個符號合成的00、01、10、11這4種分別視為1個符號，以霍夫曼編碼進行編碼。原本每個符號的平均碼長為下列何者？
  19. 關於無失真壓縮與資訊源之熵的關係，下列說明何者正確？
  20. 以行程長度編碼壓縮40個字元的字串 AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD（A 12個、B 4個、C 20個、D 4個），把相同字元的連續以「字元（1位元組）與個數（1位元組）」的組合表示。原本的字串為每個字元1位元組，若壓縮率定義為「壓縮後大小 ÷ 壓縮前大小」，壓縮率為下列何者？
  21. 以行程長度編碼壓縮時，下列何種資料最容易變得最小？
  22. 關於ZIP、gzip等所使用之LZ77方式的想法，下列何者正確？
  23. 要還原以LZ77方式壓縮的資料。資料依序為「字元A」「字元B」「（距離2、長度5）」。（距離d、長度L）表示把「將已還原字串從末尾往前數第d個字元複製到末尾」這個動作，一次1個字元地重複L次。還原後的字串為下列何者？
  24. 壓縮資料時，下列何者必須使用無失真壓縮，而不能使用有失真壓縮？
  25. 在資料的位元串上加1個偶同位位元，使1的個數為偶數後傳送，接收端檢查1的個數。關於此檢查的性質，下列何者正確？
  26. 對4列4位元的資料，在各列右端加上該列的偶同位位元，最後再加上一列各行的偶同位位元後傳送（垂直水平同位檢查）。收到的位元為第1列 1011 1、第2列 0100 0、第3列 1100 0、第4列 0101 0、同位列 0100（各列最右端的1位元為該列的同位位元）。只有1個位元出錯時，出錯位元的位置為下列何者？
  27. 把資料以1位元組為單位相加，並把和的低8位元作為檢查值（檢查和）附加後傳送。此檢查無法偵測的錯誤為下列何者？
  28. 要在資料 1101 後附加生成多項式 x³ + x + 1（位元串 1011）之循環冗餘檢查（CRC）的3位元檢查碼。檢查碼是把資料後面加上3個0的 1101000 除以 1011 的餘數，除法中以互斥或代替減法。檢查碼為下列何者？
  29. 關於生成多項式的次數為r（檢查位元為r位元）且常數項為1的CRC，下列性質何者正確？
  30. 兩個7位元碼字 1011010 與 0110011 的漢明距離為下列何者？
  31. 某碼的最小漢明距離（任兩個碼字間漢明距離的最小值）為5。考慮只用於偵測錯誤，以及只用於更正錯誤的情形。一定能偵測的錯誤位元數與一定能更正的錯誤位元數，下列組合何者正確？
  32. 由4個碼字 00000、01011、10101、11110 構成之碼的最小漢明距離，與一定能更正的錯誤位元數，下列組合何者正確？
  33. 在4位元資料上附加3位元檢查位元，做成7位元碼字的漢明碼(7, 4)，其碼率最接近下列何者？
  34. 在漢明碼(7, 4)中，把7個位元從左起稱為第1～7位元，第1、2、4位元為檢查位元。檢查1使第1、3、5、7位元，檢查2使第2、3、6、7位元，檢查4使第4、5、6、7位元中1的個數分別為偶數。收到的 0110001 有1位元錯誤時，出錯的位元為下列何者？
  35. 在32位元的資料上附加可更正1位元錯誤、偵測2位元錯誤的SECDED碼。漢明碼的檢查位元數r是滿足 2^r ≥ 資料位元數 + r + 1 的最小值，SECDED再加上1位元的整體同位位元。所需的檢查位元數為下列何者？
  36. 把5個漢明碼(7, 4)的碼字排在一起，依序送出5個碼字各自的第1位元，接著5個碼字各自的第2位元，依此類推（深度5的交錯）。接收端先恢復原本的順序，再對每個碼字更正1位元的錯誤。集中發生在連續位元上的叢發錯誤中，一定能更正的最大長度為下列何者？
  37. 關於通訊中處理錯誤的方式ARQ（自動重傳請求）與FEC（前向錯誤更正），下列說明何者正確？
  38. 某二元對稱通道傳送0與1，各位元彼此獨立地以機率0.1翻轉。設二元熵函數為 H(p) = −p log₂ p − (1 − p) log₂(1 − p)，則 H(0.1) ≈ 0.469。此通道每次傳輸的通道容量最接近下列何者？
  39. 關於夏農的通道編碼定理的內容，下列何者正確？
  40. 把格雷碼轉換為一般二進位數時，最高位元直接使用，其下的各位元則以前一個較高位置求得的二進位位元，與相同位置之格雷碼位元的互斥或求得。把4位元格雷碼 1101 轉換為二進位數的結果為下列何者？

電腦系統的其他領域