📖 講義スライド
符号理論
開く ↗
ℹ️
注意: この年度では 「オートマトン・符号理論」 として統合試験になっています。
📝 オートマトン・符号理論 (2016)
PDF ↗ 1
平均70点のテストで75点と採点された時の偏差値が60点だった。この時の標準偏差を求めよ
▶ 解答を表示
A. 5
解説: 偏差値 = 50 + 10×(得点-平均)/σ。60 = 50 + 10×(75-70)/σ、10 = 50/σ、σ = 5
2
正規表現 [A-C]+[1-3]+@[A-C]*.*[A-C]+ で受理される文字列を全て選べ
ア 3BB@AC.CA
イ B32@AAA
ウ 33@AA.
エ BB@AC.CA
▶ 解答を表示
A. エ
解説: [A-C]+で文字1つ以上、[1-3]+で数字1つ以上、@、[A-C]*で文字0個以上、.（任意1文字）、*で0回以上、[A-C]+で文字1つ以上。エのみ全条件を満たす
3
次のBNF記法で定義される<M>であらわされる文字列を全て選べ。 <A> ::= A|B|C <N> ::= 1|2|3 <D> ::= <A>|<A><D>|<D><N> <M> ::= <D>@<D>
ア 32@AA
イ B3@CA
ウ B32@A
エ ABA@CA
▶ 解答を表示
A. イ，エ
解説: <D>は文字から始まり、文字か数字が続く形。イ(B3@CA)とエ(ABA@CA)が条件を満たす
4
式 (A+B)*C-(D/A) を逆ポーランド表記法で表せ
▶ 解答を表示
A. AB+C*DA/-
解説: (A+B)→AB+、(A+B)*C→AB+C*、(D/A)→DA/、全体→AB+C*DA/-
5
次の概念の中で、有限オートマトンでないものを選べ
ア BNF記法
イ スタック
ウ 正規表現
エ 全加算器
▶ 解答を表示
A. イ
解説: スタックは無限のメモリを持つ可能性があり、有限オートマトンでは表現できない。BNF記法、正規表現、全加算器は有限オートマトンで表現可能
1
出現確率が次の表に従って生起する情報源がある。この情報源のハフマン符号化し、平均符号長Lを求めよ。
| 文字 | 確率 |
|---|---|
| A | 0.76 |
| B | 0.08 |
| C | 0.05 |
| D | 0.06 |
| E | 0.05 |
▶ 解答を表示
A. 1.48 bit/symbol
解説: ハフマン符号化: A=1(1bit), B=01(2bit), D=001(3bit), C=0001(4bit), E=0000(4bit)。平均符号長 = 0.76×1 + 0.08×2 + 0.06×3 + 0.05×4 + 0.05×4 = 0.76 + 0.16 + 0.18 + 0.20 + 0.20 = 1.48 bit/symbol
2
(1)の符号化を用いて、情報ABDを符号化せよ
▶ 解答を表示
A. 1011010
解説: A=1, B=011, D=010（ハフマン符号化の結果による）。ABD = 1 + 011 + 010 = 1011010
3
式 c = x1⊕x2 と同値なものを全て選べ
ア x1 = x2 ⊕ c
イ 0 = x1⊕x2⊕c
ウ x1⊕x2⊕1 = c
エ x1⊕x2⊕c = c
▶ 解答を表示
A. ア，イ
解説: XOR演算の性質: c = x1⊕x2 ⟺ x1 = x2⊕c（アは同値）。また c⊕c = 0 なので x1⊕x2⊕c = 0（イも同値）
4
7ビットの値 4A(16)の8ビット目に偶数パリティビットを追加した値を16進数で求めよ
▶ 解答を表示
A. CA
解説: 4A(16) = 1001010(2)（1が3個で奇数）。偶数パリティにするためパリティビット1を追加: 11001010(2) = CA(16)
5
二重誤りを検出できる方式を次の選択肢から全て挙げよ
ア 偶数パリティ
イ 奇数パリティ
ウ 水平垂直パリティ
エ CRC符号
▶ 解答を表示
A. ウ，エ
解説: 偶数/奇数パリティは二重誤りを検出できない（偶数個の誤りはパリティが変化しない）。水平垂直パリティとCRC符号は二重誤りを検出可能
📝 符号理論 (2016)
PDF ↗ 1
出現確率が次の表に従って生起する情報源がある。この情報源のハフマン符号化し、平均符号長Lを求めよ。
| 文字 | 確率 |
|---|---|
| A | 0.76 |
| B | 0.08 |
| C | 0.05 |
| D | 0.06 |
| E | 0.05 |
▶ 解答を表示
A. 1.48 bit/symbol
解説: ハフマン符号化: A=1(1bit), B=01(2bit), D=001(3bit), C=0001(4bit), E=0000(4bit)。平均符号長 = 0.76×1 + 0.08×2 + 0.06×3 + 0.05×4 + 0.05×4 = 0.76 + 0.16 + 0.18 + 0.20 + 0.20 = 1.48 bit/symbol
2
(1)の符号化を用いて、情報ABDを符号化せよ
▶ 解答を表示
A. 1011010
解説: A=1, B=011, D=010（ハフマン符号化の結果による）。ABD = 1 + 011 + 010 = 1011010
3
式 c = x1⊕x2 と同値なものを全て選べ
ア x1 = x2 ⊕ c
イ 0 = x1⊕x2⊕c
ウ x1⊕x2⊕1 = c
エ x1⊕x2⊕c = c
▶ 解答を表示
A. ア，イ
解説: XOR演算の性質: c = x1⊕x2 ⟺ x1 = x2⊕c（アは同値）。また c⊕c = 0 なので x1⊕x2⊕c = 0（イも同値）
4
7ビットの値 4A(16)の8ビット目に偶数パリティビットを追加した値を16進数で求めよ
▶ 解答を表示
A. CA
解説: 4A(16) = 1001010(2)（1が3個で奇数）。偶数パリティにするためパリティビット1を追加: 11001010(2) = CA(16)
5
二重誤りを検出できる方式を次の選択肢から全て挙げよ
ア 偶数パリティ
イ 奇数パリティ
ウ 水平垂直パリティ
エ CRC符号
▶ 解答を表示
A. ウ，エ
解説: 偶数/奇数パリティは二重誤りを検出できない（偶数個の誤りはパリティが変化しない）。水平垂直パリティとCRC符号は二重誤りを検出可能