日本語
メニュー

情報理論と符号の基礎

情報量とエントロピー、相互情報量、冗長度、固定長符号と可変長符号、接頭符号とクラフトの不等式、ハフマン符号の平均符号長と効率、ランレングス符号化、LZ77方式、可逆圧縮と非可逆圧縮、パリティと垂直水平パリティ、チェックサム、CRCの計算、ハミング距離と誤りの検出・訂正の能力、ハミング符号とSECDED、符号化率、インターリーブ、ARQとFEC、二元対称通信路の通信路容量、通信路符号化定理、グレイコードの変換を、計算問題を中心とした3択問題で学べます。

10問練習するこの分野からランダムに10問・約5分 この分野を解くこの分野の問題をすべて、ランダムな順で出題します 苦手問題直近で間違えた問題だけを解き直します

情報理論と符号の基礎の要点

「この情報は何ビット分か?」「このデータは、どこまで小さくできるか?」「雑音で誤ったビットを、どうすれば見つけて直せるか?」。こうした問いに答えるのが、シャノンが始めた情報理論と符号の理論です。ファイルの圧縮、メモリのECC、通信路の誤り訂正、記憶装置のCRCなど、コンピュータと通信のあらゆるところで使われています。

ここでは、情報量 −log₂ p とエントロピー、エントロピーが最大になる条件、条件付きエントロピーと相互情報量、冗長度、区別に必要なビット数を計算で確かめます。続いて、固定長符号と可変長符号、接頭符号とクラフトの不等式、ハフマン符号の作り方と平均符号長、エントロピーと比べた効率、記号をまとめて符号化する効果、ランレングス符号化とLZ77方式、可逆圧縮と非可逆圧縮の使い分けを学びます。後半では、パリティと垂直水平パリティ、チェックサムの弱点、CRCの検査ビットの計算とバースト誤りの検出、ハミング距離と誤りを検出・訂正できるビット数、ハミング符号(7, 4)のシンドロームによる誤りの位置の特定、SECDEDの検査ビットの数、符号化率、インターリーブ、ARQとFEC、二元対称通信路の通信路容量と通信路符号化定理を扱い、最後にグレイコードの変換を確かめます。基本情報技術者試験・応用情報技術者試験の基礎理論(情報に関する理論、通信に関する理論)の学習に役立ちます。計算問題の値は、選択肢の誤りの値やハフマン符号の木も含めて、Pythonで計算して確かめています。2進数と浮動小数点は「計算機算術」、パリティビットの計算とグレイコードの性質は「論理回路」、2進数からグレイコードへの変換は「タイミング解析とCDC」、パリティで見逃す誤りの確率は「確率・統計と待ち行列」、シャノン・ハートレーの定理による通信路容量の計算は「無線通信の基礎」、メモリのECCは「DRAM」、8b/10b符号化とPCI ExpressのCRCは「インターフェース・バス規格」、Base64とgzipは「Web技術の基礎」、交差エントロピーは「機械学習の基礎」、ハッシュと暗号は「情報セキュリティの基礎」の分野で扱います。

情報理論と符号の基礎の問題一覧（40問）
  1. 事象の確率をpとするとき、その事象が起こったと知らされて得られる情報量を −log₂ p ビットとする。確率1/8で起こる事象が起こったと知らされたときの情報量はどれか。
  2. 情報量(確率pの事象が起こったと知らされたときの −log₂ p)の性質として、正しいものはどれか。
  3. 記号A、B、C、Dをそれぞれ確率1/2、1/4、1/8、1/8で、互いに独立に出す情報源がある。この情報源のエントロピー(1記号あたりの平均情報量)はどれか。
  4. 8種類の記号を出す情報源のエントロピーの最大値と、最大になる条件の組み合わせとして、正しいものはどれか。
  5. 0を確率0.9、1を確率0.1で、互いに独立に出す2値の情報源がある。log₂ 0.9 ≈ −0.152、log₂ 0.1 ≈ −3.32 とする。この情報源のエントロピーに最も近いものはどれか。
  6. 8種類の記号を出す情報源のエントロピーが2.4ビットであった。冗長度を 1 − (エントロピー ÷ 最大エントロピー) と定義するとき、この情報源の冗長度はどれか。
  7. 2つの確率変数X、Yについて、条件付きエントロピー H(X|Y) と相互情報量 I(X;Y) の説明として、正しいものはどれか。
  8. 2つの確率変数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種類の文字を、どれも同じ長さのビット列(固定長符号)で区別したい。1文字あたりに必要な最小のビット数はどれか。
  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. 記号A、B、C、Dを確率0.4、0.3、0.2、0.1で、互いに独立に出す情報源を、ハフマン符号で符号化する。1記号あたりの平均符号長はどれか。
  16. 記号A〜Eを確率0.3、0.25、0.2、0.15、0.1で、互いに独立に出す情報源を、ハフマン符号で符号化する。等しい確率のものをどちらから選ぶかで符号語は変わることがあるが、平均符号長は変わらない。1記号あたりの平均符号長はどれか。
  17. 記号A、B、Cを確率0.6、0.3、0.1で、互いに独立に出す情報源があり、そのエントロピーは約1.30ビットである。この情報源をハフマン符号で符号化したときの効率(エントロピー ÷ 平均符号長)に最も近いものはどれか。
  18. 0を確率0.8、1を確率0.2で、互いに独立に出す2値の情報源がある。2記号ずつまとめた00、01、10、11の4種類をそれぞれ1つの記号とみなし、ハフマン符号で符号化する。元の1記号あたりの平均符号長はどれか。
  19. 可逆圧縮と、情報源のエントロピーの関係の説明として、正しいものはどれか。
  20. 40文字の文字列 AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD(Aが12個、Bが4個、Cが20個、Dが4個)を、同じ文字の連続を「文字(1バイト)と個数(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ビットを付ける。検査ビットは、データの後ろに0を3つ付けた 1101000 を 1011 で割った余りで、割り算では引き算の代わりに排他的論理和を使う。検査ビットはどれか。
  29. 生成多項式の次数がr(検査ビットがrビット)で、定数項が1のCRCの性質として、正しいものはどれか。
  30. 2つの7ビットの符号語 1011010 と 0110011 のハミング距離はどれか。
  31. ある符号の最小ハミング距離(どの2つの符号語の間のハミング距離のうちの最小値)が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. ハミング符号(7, 4)の符号語を5つ並べ、各符号語の1ビット目を5つ、次に2ビット目を5つ、という順に送る(深さ5のインターリーブ)。受信側で元の順に並べ戻してから、符号語ごとに1ビットの誤りを訂正する。連続したビットに集中して起こるバースト誤りのうち、必ず訂正できる最大の長さはどれか。
  37. 通信で誤りに対処する方式のARQ(自動再送要求)とFEC(前方誤り訂正)の説明として、正しいものはどれか。
  38. 0と1を送り、各ビットが互いに独立に確率0.1で反転する二元対称通信路がある。2値のエントロピー関数を H(p) = −p log₂ p − (1 − p) log₂(1 − p) とすると、H(0.1) ≈ 0.469 である。この通信路の、1回の伝送あたりの通信路容量に最も近いものはどれか。
  39. シャノンの通信路符号化定理の内容として、正しいものはどれか。
  40. グレイコードを通常の2進数に直すには、最上位のビットはそのまま使い、それより下位のビットは、1つ上位の位置で求めた2進数のビットと、同じ位置のグレイコードのビットとの排他的論理和で求める。4ビットのグレイコード 1101 を2進数に直したものはどれか。

情報理論と符号の基礎の参考書を探す PR

Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。

コンピュータシステムのほかの分野