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

はじめに

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

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

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

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

各問題の解答例

1: 巡回符号（40点）

(1)
情報ビット $${(1, 0, 0)}$$ に対応する多項式は $${ X(x) = x^2 }$$ である。生成多項式の次数は $${4}$$ であることから $${X(x)}$$ に $${x^4}$$ を乗じた　$${x^6}$$ を生成多項式 $${G(x) = x^4 + x^3 + x^2 + 1}$$ で除した剰余を計算すると、その剰余は $${x^3+x^2+x \rightarrow (1, 1, 1, 0)}$$ である。

従って、情報ビット$${(1,0,0)}$$ を符号化した結果は、$${w=(1, 0, 0, 1, 1, 1, 0)}$$ である。

【参考】剰余を求める計算は以下のとおり

$$
\begin{array}{cccccccc}
&1&0&0&0&0&0&0\\
\oplus&1&1&1&0&1&&\\\hline
&&1&1&0&1&0&0\\
\oplus&&1&1&1&0&1&\\\hline
&&&&1&1&1&0\\
\end{array}
$$

(2)
$${C}$$は巡回符号であるから、(1)で求めた符号$${(1, 0, 0, 1, 1, 1, 0)}$$を巡回シフトさせた下記の符号、および零ベクトルもまた$${C}$$の符号である。

$$
(1, 0, 0, 1, 1, 1, 0) \\
(0, 0, 1, 1, 1, 0, 1) \\
(0, 1, 1, 1, 0, 1, 0) \\
(1, 1, 1, 0, 1, 0, 0) \\
(1, 1, 0, 1, 0, 0, 1) \\
(1, 0, 1, 0, 0, 1, 1) \\
(0, 1, 0, 0, 1, 1, 1) \\
(0, 0, 0, 0, 0, 0, 0) \\
$$

情報ビット数は$${3}$$ビットであり、符号語の個数は$${2^3=8}$$となるから、上記が全ての符号語である。

(3)
前問の解答で得られた符号を比較すると、最小ハミング距離は$${4}$$である。従って$${1}$$ ビットまでの誤りを訂正できる。

【参考】
線形符号（$${\supset}$$巡回符号）の最小ハミング距離は、非零符号のハミング重み（つまり$${1}$$のビット数）の最小値に等しくなることから、全ての符号の組み合わせについて確認する必要はなく、

$$
\left[
\begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
\end{matrix}
\right]
\begin{matrix}
\rightarrow & 零であるため対象外 \\
\rightarrow & 4 \\
\rightarrow & 4 \\
\rightarrow & 4 \\
\rightarrow & 4 \\
\rightarrow & 4 \\
\rightarrow & 4 \\
\rightarrow & 4 \\\end{matrix}
$$

と確認できれば十分である（※１）。

最小ハミング距離$${d_{min}}$$と、訂正可能ビット数$${t}$$との関係は、$${d_{min}\ge 2t+1}$$ であるから、$${t\le1}$$となる。

【参考の参考】
※１と言える理由について。この符号が線形符号であるということは、2つの符号語の線形結合もまた符号語であることを意味する。一方、2つの符号語の間のハミング距離を求めることは、2つの符号語の差にあたるベクトルを求め、そのハミング重み（$${1}$$であるビットの個数）を数えることになる。しかし、2つの符号語の差は、2つの符号語の線形結合の一種であるから、求めた差は、当初の符号語のいずれかと一致する。従って、2つの符号語間のハミング距離の最小値は、全符号語（零を除く）のハミング重みの最小値に等しくなる。

(4)
$${𝑦=(1,0,1,0,1,0,0)}$$ は、$${(1, 1, 1, 0, 1, 0, 0)}$$ とのハミング距離が$${1}$$ で最も近い。従って、復号される情報ビットは $${(1, 1, 1)}$$ である。

【参考】
上記は目視で実施する簡便な解法である。きちんと解く場合は、以下のようになるだろう。

生成行列$${G}$$を元に、検査行列$${H}$$を求める。

まず、生成行列$${G}$$（のうち標準形のもの）は、以下の通りである。これは、(2)で挙げた符号語のうち、情報ビット部分のハミング重み（つまり$${1}$$であるビット数）が$${1}$$であるものを連結したものである。

$$
G = \left[
\begin{matrix}
1 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 \\
\end{matrix}
\right]
$$

検査行列は、生成行列を元に、

• 単位行列部分の大きさを、（生成行列では情報ビット数であるのに対し）検査ビット数とする。

• 検査ビット列の部分行列を転置する。

• 単位行列部分と検査ビット列部分の配置を入れ替える。

とすることで構成する。すなわち、

$$
G=\left[
I | P
\right]
$$

に対して、

$$
H=\left[P^\top|I\right]
=\left[
\begin{matrix}
1 & 0 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 \\
\end{matrix}
\right]
$$

である。これを用いて、

$$
\begin{align*}
yH^\top&=
\left[
\begin{matrix}
1 & 0 & 1 & 0 & 1 & 0 & 0 \\
\end{matrix}
\right]\left[
\begin{matrix}
1 & 0 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 \\
\end{matrix}
\right]^\top\\
& = \left[
\begin{matrix}
0 & 1 & 1 & 1
\end{matrix}
\right]
\end{align*}
$$

となり、転置検査行列$${H^\top}$$の各行と比較すると、$${2}$$ 行目と一致する。従って、元の信号列には$${2}$$ビット目に誤りがあることがわかる。
よって、復号される情報ビットは、受信したビット列のうち、情報ビット部分 $${(1, 0, 1)}$$ の$${2}$$ビット目を訂正した $${(1, 1, 1)}$$ である。

2: ハフマン符号（40点）

本文は、R5年度第2問と類似の問題である。併せて参照されたい。

(1)
d が 110、e が 111、abcde が 100100110111 にそれぞれ対応するから、abc は 100100 に対応する。

a, b, c のそれぞれに対応する符号語として取りうるものは、以下の組み合わせとなる：

a, b, c =
(1, 0, 0100), (1, 00, 100), (1, 001, 00), (1, 0010, 0),
(10, 0, 100), (10, 01, 00), (10, 010, 0),
(100, 1, 00), (100, 10, 0),
(1001, 0, 0)

(2)
前問で挙げたもののうち、一意復号可能なものは、(10, 01, 00) のみである。
このとき (a, b, c, d, e) = (10, 01, 00, 110, 111) であり、この符号語はいずれも他の符号語のプレフィクスとなっていないから、瞬時復号可能である。

【参考】
上記以外の符号は、「同じ符号語が含まれている（特異である）」あるいは「符号語のうち2つ（あるいは3つ以上）をつなげると別の符号語になる」という性質をもっており、一意復号可能ではない。

(3)
前問に挙げた符号がハフマン符号であるとすると、その符号を構成するためのツリーは以下のようになる。

ハフマン木の構成

このとき、ツリーの構成順序としては以下の場合が考えられ（B4は必ず最後になる）、それぞれの場合において成り立つ不等式を列挙すると：

1. B1 → B2 → B3 → B4 の場合
   （例：$${\{P_a, P_b, P_c, P_d, P_e\} = \{0.35, 0.25, 0.20, 0.15, 0.05\}}$$）
   $${ \max(P_d, P_e) \le \min(P_a, P_b, P_c) }$$（式 1.a）
   $${ \max(P_b, P_c) \le \min(P_a, (P_d + P_e)) }$$（式 1.b）
   $${ \max(P_a, (P_d + P_e)) \le (P_b + P_c) }$$（式 1.c）

2. B1 → B3 → B2 → B4 の場合
   （例：$${\{P_a, P_b, P_c, P_d, P_e\} = \{0.2, 0.35, 0.25, 0.15, 0.05\}}$$）
   $${ \max(P_d, P_e) \le \min(P_a, P_b, P_c) }$$（式 2.a）
   $${ \max(P_a, (P_d + P_e)) \le \min(P_b, P_c) }$$（式 2.b）
   $${ \max(P_b, P_c) \le (P_a + P_d + P_e) }$$（式 2.c）

3. B2→ B1 → B3 → B4 の場合
   （例：$${\{P_a, P_b, P_c, P_d, P_e\} = \{0.28, 0.18, 0.18, 0.18, 0.18\}}$$）
   $${ \max(P_b, P_c) \le \min(P_a, P_d, P_e) }$$（式 3.a）
   $${ \max(P_d, P_e) \le \min(P_a, (P_b + P_c)) }$$（式 3.b）
   $${ \max(P_a, (P_d + P_e)) \le (P_b + P_c) }$$（式 3.c）
   この場合、$${P_b = P_c = P_d = P_e}$$ に限られることに注意。

①
$${P_a}$$ と $${P_d}$$ の関係は、常に $${P_a \ge P_d}$$ である。
（式 1.a, 2.a, 3.b のいずれかから）

②
$${P_a}$$ と $${P_e}$$ の関係は、常に $${P_a \ge P_e}$$ である。
（式 1.a, 2.a, 3.b のいずれかから）

③
$${P_a}$$ と $${P_b + P_c}$$ との関係は、常に $${P_a \le P_b + P_c}$$ である。
（式 1.c, 2.b, 3.c のいずれかから）

④
$${P_b}$$ と $${P_a + P_d + P_e}$$ との関係は、常に $${P_b \le P_a + P_d + P_e}$$ である。
（式 1.b, 2.c, 3.a のいずれかから）

【参考】別の見方をすれば、ハフマン符号において、2つの記号とそれらに対応する符号語があったとき、出現確率が低いほうの記号に短い符号語が割り当てられることはない。

記号$${a\rightarrow10}$$の符号長は2、記号$${d\rightarrow110}$$および$${e\rightarrow111}$$ の符号長は3であるから、$${d}$$および$${e}$$の出現確率が、$${a}$$の出現確率を超えることなく、$${P_a\ge P_d}$$、$${P_a\ge P_e}$$ と言える。

また、ツリーのある節以下にある複数の記号をひとまとめにして考えることも可能である。例えば、B1は符号語$${11}$$に対応し、その出現確率に相当する値は、$${d}$$と$${e}$$の出現確率の総和である。

記号$${b\rightarrow01}$$および$${c\rightarrow00}$$の出現確率の和は、符号語$${0}$$の符号長1に対応するから、符号長が2である記号$${a}$$との関係で、出現確率について$${P_b+P_c\ge P_a}$$ が言える。

記号$${a\rightarrow10}$$、$${d\rightarrow110}$$、$${e\rightarrow111}$$の出現確率の和は、符号語$${1}$$の符号長1に対応するから、符号長が2である記号$${b}$$との関係で、出現確率について$${P_b\le P_a+P_d+P_e}$$ が言える。

3: 用語説明 (20点)

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

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

「自己情報量」
生起確率$${p}$$である事象に対して、$${2}$$を底とする対数を用いて$${-\log p}$$と定義される値。事象の生起しにくさに対応する値と解釈することもでき、$${p=1}$$の時に自己情報量も$${0}$$となる。また、独立事象の同時確率に対応する自己情報量が、それぞれの自己情報量の和になるという加法性を充足するために、生起確率の対数を基礎として計算される。

「白色ガウス雑音」
周波数解析をした際に全帯域にわたってほぼ等しいパワーを持ち（白色性）、かつ時間領域において雑音の値が平均$${0}$$の正規分布に従う（ガウス性）雑音信号を意味する。

「暗号理論における計算量的安全性」
暗号の強度を、暗号を解読するために要する計算量に依拠することをいう。例えば暗号解読に要する計算量が鍵に相当するデータ長の指数オーダーとなっている場合、鍵長が十分であれば、実用上強度をいくらでも高めることが可能と言える。

「秘密計算」
暗号化されたデータに対して、復号することなく演算することができる手法を指す。復号を要しないことから、暗号によって保護される機密情報が計算の過程で漏洩するリスクを減らすことができる。

「HDRI」
High Dynamic Range Image の略であり、カメラ等で通常の方法で撮影して得られたデジタル画像、あるいは特殊な方法で撮影された画像の集合等を元に、各画素値の範囲を調整することによって幅広いダイナミックレンジを実現した画像をいう。例えば、特に明るい部分と暗い部分が存在する画像について、色つぶれを軽減し、視認性・再現性を高めることができる。

以上

解答は以上です。

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