はじめに

2022 SA am1

01-02: https://blog.yexca.net/archives/184
03-05: https://blog.yexca.net/archives/185
06-10: https://blog.yexca.net/archives/186
11-15: https://blog.yexca.net/archives/189
16-30: https://blog.yexca.net/archives/190

さて、この記事についてだけど、ちょっと挑戦してみようかなと思って書いているんだ。合格するかどうかは別として、システムアーキテクト試験、つまり情報処理技術者試験の高度試験を受けてみようと思う。この試験で手に入る資格や知識は、普段のコーディングではあまり使わないかもしれないけど（本当は使えるのに気づいてないだけかもしれないけどね）、持っていて損はないはず。少しずつでもこの過去問を解き進めて、現実感を取り戻していけたらいいな。

独り言

ここ2年くらい、本当にふわふわした感じで過ごしちゃってて、その状態が今の物事の進め方にも大きく影響してるんだ。このままじゃダメだよね。選べないなら、せめて今できることを精一杯やろうと思う。少なくとも挑戦はしてみたい。挑戦する勇気がないのが一番怖いことだし、それで最近もチャンスを一つ逃しちゃったから。少しずつでも変化を起こして、もっと「生きてる」実感を持ちたいんだ。時々、自分が夢の中にいるような感覚になることがあるけど、それは良い意味じゃなくて、現実味がないっていうか。言葉の力には限界があるけど、実際の経験には説得力があるよね。たとえそれが作り物だったとしても、今は信じてみることにしたんだ。

うーん、なんか日記みたいになっちゃったね。まあまあ、そんな感じ。

「夢を見てるみたい」って書いたけど、それで面白い修仙小説（仙人を目指す中国の小説）を思い出した。ある魔宗の人が、自分は仙人で今の世界はただの幻影、修行のために来てるんだって思い込んでる設定。僕もたまにその設定に影響されてる気がする。だからもう無駄話はやめようね。

第1問

ハミング符号とは、データに冗長ビットを付加して、1ビットの誤りを訂正できるようにしたものである。ここでは。$X_1, X_2, X_3, X_4$ の4ビットから成る数据に3ビットの冗長ビット $P_3, P_2, P_1$ を付加したハミング符号 $X_1X_2X_3P_3X_4P_2P_1$ を考える。付加したビット $P_1, P_2, P_3$ は、それぞれ

となるように決める。ここで、$\oplus$ は排他的論理和を表す。

ハミング符号1110011には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア　0110011

イ　1010011

ウ　1100011

エ　1110111

ハミング符号の問題だね。問題文に公式があるから、それぞれ代入して排他的論理和（XOR）を計算すると、

となる。これから誤りがある位置は $(111)_2$、つまり第7位だとわかる。だから、正しいデータは 0110011、つまり選択肢 ア だね。

ハミング符号を見たとき、懐かしいなとは思ったけど、具体的にどんなものだったか全然覚えてなかった。あぁ、前は何を学んでたんだろうね。

ハミング符号はデータの誤りチェックと1ビットの訂正ができる。元のデータが 1100 の場合を例に、ハミング符号にする手順はこんな感じ。

まず、冗長ビット（チェックビット）の数 $k$ を計算する。$2^k \ge k + m + 1$ （mは元のデータ数、kはチェックビット数）。この例だと $k=3$ になる。チェックビットは $2^n$ の位置、つまり 1, 2, 4, 8 ··· に配置される。ここでは右から数えて 1, 2, 4番目だね。

3ビットのチェックビットと4ビットのデータで合計7ビット。2進数で表すとこうなる（チェックビット3ビット分なので3桁の2進数）。

チェックビットの位置、つまり 1, 2, 4 の数字はそれぞれ 001, 010, 100 に対応している。つまり 1 が立っている位置が1桁目、2桁目、3桁目ということ。次に、同じ位置に 1 を持つものを探し出すよ。

次に、各グループ（上の表の各行）ごとにチェックビットを計算する。元のデータを使うとこんな感じ。

チェックビットの値はまだ決まってないから、一旦空欄にしておく。

第1グループは、1, 3, 5, 7番目の数字で決める。1が1個あるから、1の数を偶数にするために 1 を補う（偶数パリティの場合）。

第2グループは、2, 3, 6, 7番目の数字で決める。1が2個あるから、0 を補う。

第3グループは、4, 5, 6, 7番目の数字で決める。1が2個あるから、0 を補う。

だから、ハミング符号の各位置はこうなる。

つまり、データ 1100 のハミング符号は 1100001 になる。チェック方法は問題文と同じだね。問題の例も7ビットだし。

どうやってチェックするかというと、問題の3つの式の位置を右から数えるように変換してみると、さっきチェックビットを決める時に分けた3つのグループと同じだってことがわかる。だから、チェック方法は各グループでXOR操作をして、得られた結果（全部0ならエラーなし）を右から並べればいいんだ。つまり、

···第3グループ、第2グループ、第1グループ

得られた2進数が、データが変化した位置を表している。その位置の数値を反転させれば元のハミング符号に戻るよ。

参考記事

海明码一篇文章彻底搞懂

海明码的编码和校验方法

排他的論理和（XOR）

第2問

リストには、配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として、適切なものはどれか。ここで、配列を用いたリストは配列に要素を連続して格納することによってリストを構成し、ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。

ア　リストにある実際の要素数にかかわらず、リストに入れられる要素の最大個数に対応した領域を確保し、実際には使用されない領域が発生する可能性がある。

イ　リストの中間要素を参照するには、リストの先頭から順番に要素をたどっていくことから、要素数に比例した時間が必要となる。

ウ　リストの要素を格納する領域の他に、次の要素を指し示すための領域が別途必要となる。

エ　リストへの挿入位置が分かる場合には、リストにある実際の要素数にかかわらず、要素の挿入を一定時間で行うことができる。

この問題は、配列で実現したリストの特徴を聞いているね。ア 以外は全部ポインタで構成されたリスト（連結リスト）の特徴だから、答えは選択肢 ア だ。

内容はかなり分かりやすいね。間違えるとしたら、日本語が読めなかったときかな :cry:。各選択肢の解説はこんな感じ：

ア：リストの実際の要素数に関係なく、あらかじめ最大個数分のメモリを確保するから、使われない無駄な領域ができる可能性がある。

イ：中間要素にアクセスするのに先頭から辿る必要があるのは連結リストの特徴。配列ならインデックスで直接アクセスできる。

ウ：次の要素を指すための追加領域（ポインタ）が必要なのは連結リストの特徴。

エ：挿入を一定時間で行えるのは連結リスト（位置がわかっている場合）。配列だと、要素をずらす必要があるから時間がかかる。