4 桁の 2 進数. 一般に k 桁の 2 進数は 2k 個
文字で文章を送ることを考えてみましょう. 英語のアルファベットは大文字, 小文字を区別すると 52 文字ありますが, これは「52 個の異なる記号があって, その組み合わせで文章を作っている」と考えられます. 文章を記録, 伝達するには, 使う文字の数 (この場合 52 個) だけの 2 進数を用意し, それらの組み合わせで文章を 0, 1 の列に置き換えることになります. 1 桁の 2 進数は「0, 1」の 2 つ, つまり 2 つの異なるものが区別でき, 2 桁の 2 進数は「00, 01, 10, 11」の 4 つですから 4 つの異なるもの (文字) が区別できます. 3 桁だと
では 52 文字ほしいとするとどうなるでしょうか. 5 桁の 2 進数は全部で 25=32 個, これでは足りません. 次に 26=64 ですから, 6 桁までの 2 進数を用意すれば 52 文字それぞれに違う 2 進数を割り当てることができ, アルファベット全部を 2 進数で表して通信ができます.
実は文字だけではダメで, スペース, コンマ, ピリオド, ハイフンなど, いろいろな記号が必要です. 実際に使われている「ASCII (アスキー) コード」は 7 桁の 2 進数 (27=128) を使い, 通常の英文で使われる文字や記号, さらには改行などの「制御文字」まで表しています.
| 文字 | 2 進 | 10 進 |
| NL (改行) | 0001010 | 10 |
| a | 1100001 | 97 |
| b | 1100010 | 98 |
| c | 1100011 | 99 |
| d | 1100100 | 100 |
| e | 1100101 | 101 |
| z | 1111010 | 122 |
ひらがなを 4 文字だけ使って文を作り, それを送ることを考えましょう. なぜ 4 文字かというと, 単に説明を簡単にするためです (6,7 桁もある 2 進数はこういう場所では見づらいですから). 4 文字なら 2 桁の 2 進数で済みます. ここでは
| 2 進 | かな |
| 00 | け |
| 01 | た |
| 10 | ぶ |
| 11 | や |
ラジオをつけているときに部屋の蛍光灯のスイッチを入れると「バチバチ」と雑音が入ることがよくあります. 文章を 2 進数に置き換え, さらにそれを電気信号に置き換えて (0 → OFF, 1 → ON) 電波で送っている途中にこういう雑音が入ると, もとの情報はすっかり形が変わってしまうでしょう. これが情報伝達途中に発生する誤りです. 通常の情報伝達では, すべての信号は 0 または 1 のいずれかと解釈されますから, 途中で誤りが発生するということは,
もともと 0 として送られた信号が 1 に置き換わってしまう, あるいは 1 として送られた信号が 0 に置き換わってしまう, ということです. つまり, 誤りの発生は数学的には
そのまま上の「たけやぶやけた」(01 00 11 10 11 00 01) を送っても誤りの検出はできません. あらかじめ
| もとの情報 | 付け加えたあと |
| 00 | 000 |
| 01 | 011 |
| 10 | 101 |
| 11 | 110 |
なお, 上のような規則で符号化を行う符号を「パリティ検査符号」(parity check code) といいます.
4. 誤り検出
誤りが起きなければ情報の受け手は 011 000 110 101 110 000 011 を受け取ることになり, 上の符号化の表を見ながらもとの情報 01 00 11 10 11 00 01 を取り出します (尤も, 今の規則だと単に左側の 2 桁を採ればよいので表を見るまでもありませんが). この過程を「復号」といいます. さらに, かなとの対応表からこれが「たけやぶやけた」とわかるわけです.
ではもし
そこで, 上の符号化の表を見て, 符号化した 3 桁の数の共通する特徴を探してみましょう. それは
ちょっと考えると「111 は 110 の一番右の桁が入れ替わったものだから, すぐに 110 と直せばいい」という気がします. しかし残念ながらそう簡単にはいかないのです. というのは, 1 つの桁の 0, 1 が入れ替わって 111 となるのは 110 だけではないからです. 他に 011, 101 も 0 が 1 に変わることで 111 になってしまいます. ですから 111 がやってきたとき, 正しい情報は 011, 101, 110 の 3 つの可能性があるのです. 人間が見れば文脈から「これは『や』に違いない」などと, 「知的誤り訂正」を行うわけですが, 情報の記録や伝達のみを行う機械はそのようなことをしません. 通常, 誤りはランダムに発生する, という状況で考えますから, 無理に訂正してもそれが合っている確率は 1/3. これでは訂正しても意味がないですね.
あと, 恐らく多くの方の疑問は「3 桁中 2 か所で誤りが発生したらどうなるか」ということと思います. 例えば 000 の左 2 桁が反転して 110 になった場合などです. 残念ながら 110 が符号化の表に載っている以上, 機械は「誤りは起きなかった」と判断し, 素通りさせてしまいます. これは困ったことなのですが, 誤りがそう頻繁に起きないような状況 (例えば 20 桁に 1 回の割合で誤りが起きるとか) であれば, これでも何とか間に合いそう, という気がします. 誤りの発生確率は状況によりいろいろです. たくさん誤りが起きても大丈夫なようにするのはいいことですが, それには訂正のための余分な情報をより多く追加する必要があり, 必要以上に訂正能力を上げるのは効率の低下を引き起こします (上の例では 2 桁の情報を 3 桁にしましたから, 送られたデータのうち 67% が本来必要な情報, この場合の効率とはこの割合のことです).
いずれにしても, ある程度効率もよくて, 訂正までできるようにする, あるいは訂正の能力を上げるには, もっと性能のよい符号を作る, ということになります. それにはベクトルや行列に関する知識が必要になります. もう一つの文書 ★誤り訂正符号の実例 では, そうした知識を使って, 実際に誤りの訂正が可能な符号を作っています.
高校から大学にかけて学ぶ数学が一体どんな役に立つのだろうと思われる方もおありでしょうが, 先端技術を支える学問の出発点として, やはり大切な役割を果たしているのです.
2008.3 公開, 2019.7 改訂
応用代数学研究室に戻る