令和5年度 弁理士 論文式筆記試験（選択）「理工V（情報理論）」　非公式過去問解答

はじめに

本投稿は有料となっていますが、有料部分にはコンテンツはなく、無料ですべてご覧いただけます。

本記事は、令和5年度弁理士試験論文式筆記試験（選択科目）のうち、「理工V「情報理論」について、非公式に筆者が作成した解答例（およびメモ）です。試験問題は、下記の弁理士試験に関する特許庁サイトから参照が可能です。

https://www.jpo.go.jp/news/benrishi/shiken-mondai/index.html

なお、内容にはできるだけ誤りがないよう注意しながら執筆していますが、万一「おかしいんじゃないかこれ？」といった箇所がありましたら、コメントいただければ幸いです。可能な限り加筆修正等させていただきます。

各問題の解答例

1: 通信路と符号化（40点）

(1) 順に、「通信の効率」「通信の信頼性」「算術符号」「ハミング符号」「ハミングの限界式」「完全符号」

(2) 通信路行列

定義に従って、値を埋めていけばよい。

$${i}$$ 行 $${j}$$ 列は、$${i}$$ 番目の符号が入った場合に、$${j}$$ 番目の符号が出てくる確率、つまり $${P(Y=j|X=i)}$$ である。本問では、入力符号は $${\{0, 1\}}$$、出力符号は $${\{0, E, 1\}}$$ であるから、

$$
\begin{bmatrix}
1-q & q & 0 \\
0 & q & 1-q \\
\end{bmatrix}
$$

となる。（$${1}$$ 行 $${1}$$ 列は、$${0}$$ が入ったときに、$${0}$$ が出てくる確率であるから $${1-q}$$ 。以下同様）

(3) 相互情報量

$${ I(X; Y) = H(X) - H(X|Y) }$$ であり、

$${ H(X) }$$ および $${ H(X|Y) }$$ はそれぞれ、

$$
\begin{align*}
H(X) & = -P(X=0) \log P(X=0) - P(X=1) \log P(X=1) \\
& = -\alpha\log\alpha - (1-\alpha)\log(1-\alpha) \\
\end{align*}
$$

および

$$
\begin{align*}
H(X|Y) &= P(Y=0) H(X|Y=0) + P(Y=1) H(X|Y=1) \\
&
\begin{alignedat}{2}
= P(Y=0) \{ &-P(X=0|Y=0) \log P(X=0|Y=0) \\
& - P(X=1|Y=0) \log P(X=1|Y=0) \} \\
\end{alignedat}\\
&
\begin{alignedat}{2}
+ P(Y=1) \{ &-P(X=0|Y=1) \log P(X=0|Y=1) \\
& - P(X=1|Y=1) \log P(X=1|Y=1) \} \\
\end{alignedat}\\
\end{align*}
$$

である。

ここで、本問では $${P(X=x|Y=y) }$$ がとりうる値が $${0}$$ または $${1}$$ であることに注意すると、$${ P(X=x|Y=y) \log P(X=x|Y=y) }$$ はいずれも $${0}$$ となる。

従って、

$$
H(X|Y) = 0
$$

となる。

よって、$${ I(X;Y) = H(X) = -\alpha\log\alpha - (1-\alpha)\log(1-\alpha) }$$ と求まる。

【参考】真面目に計算をすると上記のようになるが、本件通信路では、$${Y}$$が観測されれば$${X}$$が決まる（通信路上で消失することはあるが、混同は起きない）ことから、$${H(X|Y)=0}$$であることに気づけば速い（決まる＝固定される＝情報量がない＝情報エントロピーは$${0}$$）。

2: ハフマン符号(40点)

(1) 
a に符号語 11 が割り当てられ、abcd が 111011000 となることから、bcd が 1011000 である。この場合、可能性がある符号は、下記各符号語が {a, b, c, d} に対応するとして、
{11, 1, 0, 11000}, {11, 1, 01, 1000}, {11, 1, 011, 000}, {11, 1, 0110, 00}, {11, 1, 01100, 0},
{11, 10, 1, 1000}, {11, 10, 11, 000}, {11, 10, 110, 00}, {11, 10, 1100, 0},
{11, 101, 1, 000}, {11, 101, 10, 00}, {11, 101, 100, 0},
{11, 1011, 0, 00}, {11, 1011, 00, 0},
{11, 10110, 0, 0}
がすべてである。

(2)
前問において示したもののうち、検討するまでもなく一意復号不可能であるものは以下の通り：

• 同一の符号語が複数の記号に割り当てられている。つまり「特異な符号」であるもの：
  {11, 10, 11, 000}, {11, 10110, 0, 0}

上記以外にも、「符号語をいくつか結合すると別の符号語になってしまう」ものも一意復号不可能であるから、以下のものも一意復号不可能である：

• 符号語 $${0}$$ および $${1}$$ がともに割り当てられている
  {11, 1, 0, 11000}, {11, 1, 01100, 0}

• （上記以外で）ある符号語が、別の符号語の繰り返しになっている
  {11, 1, 01, 1000}, {11, 1, 011, 000}, {11, 1, 0110, 00}, {11, 10, 1, 1000},
  {11, 101, 1, 000}, {11, 1011, 0, 00}, {11, 1011, 00, 0}

• （上記以外で）ある符号語が、別の2つ以上の符号語を結合したものになっている
  {11, 10, 1100, 0}, （"1100" = "11" + "0" + "0"）

以上に該当しない以下の3通りの符号：
{11, 10, 110, 00}, {11, 101, 10, 00}, {11, 101, 100, 0}
については、次に示す通り、サーディナス・パターソンの定理から一意復号可能性を満たす。

• {11, 10, 110, 00} の場合

$${ C = \{11, 10, 110, 00\} }$$ であるから、$${ C_1 = \{0\} }$$ である。$${C_0 = C}$$ の要素の末尾に付加して、付加したものも $${ C = C_0 }$$ の要素となるのは、$${ 0 }$$ のみだからである（"11" + "0" = "110"）。

また、$${ C_2 = \{ 0 \} }$$ となる。$${ C = \{11, 10, 110, 00\} }$$ の要素の末尾に付加して $${ C_1 = \{ 0 \} }$$ の要素となる符号語は存在せず、 $${ C_1 = \{ 0 \} }$$ の要素の末尾に付加して $${ C = \{11, 10, 110, 00\} }$$ の要素となる符号語は $${ 0 }$$ のみだからである（"0" + "0" = "00"）。

以上から、帰納的に $${ C_3 = C_4 = … = C_\infty = \{ 0 \} }$$ となることから、$${ C \cap C_\infty = \{ 11, 10, 110, 00 \} \cap \{ 0 \} = \phi }$$ となる。

• {11, 101, 10, 00} の場合

$${ C = \{11, 101, 10, 00\} }$$ であるから、$${ C_1 = \{1\} }$$ である。$${C_0 = C}$$ の要素の末尾に付加して、付加したものも $${ C = C_0 }$$ の要素となるのは、$${ 1 }$$ のみだからである（"10" + "1" = "101"）。

また、$${ C_2 = \{ 0, 1, 01 \} }$$ となる。$${ C = \{11, 101, 10, 00\} }$$ の要素の末尾に付加して $${ C_1 = \{ 1 \} }$$ の要素となる符号語は存在せず、 $${ C_1 = \{ 1 \} }$$ の要素の末尾に付加して $${ C = \{11, 101, 10, 00\} }$$ の要素となる符号語は $${ 0, 1, 01 }$$ だからである（"1" + "0" = "10" 等）。

さらに、$${ C_3 = \{ 0, 1, 01 \} }$$ となる。$${ C = \{11, 101, 10, 00\} }$$ の要素の末尾に付加して $${ C_2 = \{ 0, 1, 01 \} }$$ の要素となる符号語は存在せず、 $${ C_2 = \{ 0, 1, 01 \} }$$ の要素の末尾に付加して $${ C = \{11, 101, 10, 00\} }$$ の要素となる符号語は $${ 0, 1, 01 }$$ だからである（"1" + "0" = "10" 等）。

以上から、帰納的に $${ C_4 = C_5 = … = C_\infty = \{ 0, 1, 01 \} }$$ となることから、$${ C \cap C_\infty = \{ 11, 101, 10, 00 \} \cap \{ 0, 1, 01 \} = \phi }$$ となる。

• {11, 101, 100, 0} の場合

$${ C = \{11, 101, 100, 0\} }$$ であるから、$${ C_1 = \phi }$$ である。$${C_0 = C}$$ の要素の末尾に付加して、付加したものも $${ C = C_0 }$$ の要素となる符号語は存在しないためである。

従って、帰納的に $${ C_2 = C_3 = … = C_\infty = \phi }$$ となることから、$${ C \cap C_\infty = \{ 11, 101, 10, 00 \} \cap \phi = \phi }$$ となる。

(3)
瞬時復号可能であるための必要十分条件は、「どの符号語も、他の符号語のプレフィクスとなっていない」ことである。

この条件について検証すると、

• {11, 10, 110, 00} → "11" が "110" のプレフィクスとなっている

• {11, 101, 10, 00} → "10" が "101" のプレフィクスとなっている

• {11, 101, 100, 0} → どの符号語も、他の符号語のプレフィクスとなっていない

以上から、瞬時復号可能な符号化方法は、
a=11, b=101, c=100, d=0
である。

(4)
ハフマン符号である場合、その符号表を構築する際のツリーは下記のようになる：

a 11  -------------+ (1)
                   |
b 101 -----+ (1)   +-------+ (1)
           +-------+ (0)   |
c 100 -----+ (0)           +-----
                           |
d 0   ---------------------+ (0)

この場合、各記号の出現確率について、以下のことが言える：

1. $${ P_a, P_b, P_c, P_d }$$ のうち、他より大きくないもの2つとして$${ P_b, P_c }$$を選択可能である。すなわち、$${ P_a, P_d \ge P_b, P_c }$$（カンマの左右どちらを選んでも数式が成り立つことを意味する）。

2. $${ P_a, (P_b + P_c), P_d }$$ のうち、他より大きくないもの2つとして$${ P_a, (P_b + P_c) }$$を選択可能である。すなわち、$${ P_d \ge P_a, (P_b + P_c) }$$。

以上から、
① $${ P_a \ge P_b }$$ は 1. から「○常に成立」。
② $${ P_b \gt P_c }$$ は 1. の右辺の大小関係は不定なので「△不定」。
③ $${ P_c \lt P_d }$$ は 1. から「×常に不成立」。
④ $${ P_d \lt P_a }$$ は 2. から「×常に不成立」。
⑤ $${ P_a \ge P_b + P_c }$$ は 2. の右辺の大小関係は不定なので「△不定」。
⑥ $${ P_b + P_c \gt P_d }$$ は 2. から「×常に不成立」。
⑦ $${ P_a + P_b + P_c \lt 2/3 }$$ は 2. から「○常に成立」（$${P_d \ge P_a }$$かつ$${ P_d \ge P_b + P_c }$$ であるから、$${ 3P_d \ge P_a + P_b + P_c + P_d = 1}$$ あたりから導出 ）。

一見脈絡のない不等式だが、ハフマン符号の構築手順を理解しているかどうかを問う良問に思える。

3: 用語説明 (20点)

以下の説明は、必ずしも辞書的な定義等にはなっていないものがあるが、試験の場において答案を作成する場合にはそのような「品質」の解答を期待するのは現実的ではないうえ、そのような高品質の解説は教科書や情報源となるサイト等においていくらでも参照可能である。

そこで以下は、筆者が個人的に「このくらい書けていれば十分では」という程度の内容としている。基本的には、持っている知識に基づいて書いた上で、その後定義や解説を参照して誤りがないか確認し、必要な箇所は加筆修正をしたものである。

「折り返し雑音」
連続信号をサンプリングにより離散信号化する場合、離散信号が表現可能な周波数には上限があり、原信号に含まれている周波数成分のうち、サンプリング周波数の半分（ナイキスト周波数）を超えるものは正しく離散信号化されない。
このような成分は、ナイキスト周波数を中心として折り返した周波数の成分として離散信号化され、これにより、本来存在していなかった成分が離散信号に混入することとなる。これを折り返し雑音と呼ぶ。

「巡回冗長検査」
通信路符号化において誤り検出を目的として付加される符号の一種。伝送すべき符号列に対して、巡回多項式で除した剰余をその末尾に付与して伝送する。受信側では、実際に受信した符号列を巡回多項式で除し、その剰余が0となることをもって、伝送に誤りがなかったことを確認する。

「フィッシング」
悪意を持った攻撃者が、銀行やECサイトから送られたメールを装うなどしてIDやパスワード等の機密情報の窃取を狙う攻撃手法。自らが用意した偽装サイトに誘導し、そこでユーザに入力させる手口が用いられることが多い。

「セキュア・バイ・デザイン」
製品やサービスの設計段階で、ユーザのセキュリティを確保できるよう考慮すべきという考え方。
運用開始後に脆弱性が見つかってから対処するのではなく、脆弱性が入り込まない設計を意識することで、全体でのコストの低下が期待される。

「DoS攻撃」
Denial of Service の略であり、Webサービス等に対し不正な通信を行うことでサービスを機能不全に陥らせることを意図した攻撃を意味する。
サービスが想定していない通信によりサーバの状態を不安定化させる方法のほか、Webサービスの処理可能容量を超えるアクセスを、分散したホストを用いるなどして同時に行うことで、機能不全に陥らせる方法もこれに含まれる（DDoS：Distributed DoS）。

以上

解答は以上です。

以下は有料エリアとなっていますが、追加のコンテンツは特にありません。
本記事を読んで、「まあこれでビールでも飲めや」という方がいらっしゃいましたら、ご購入いただければ励みになります。