モールス信号は瞬時復号可能なのか？
最近妻のお腹（現在妊娠７か月目）にたまに話しかけます。
どうも胎児には高い音のほうが伝わりやすいようで、裏声で話しかけると結構胎動が返ってきて楽しいです。
今日は普通に話しかける代わりにモールス信号で話しかけてみました。（トンツーを「アー」と「アッ」で表現）
話しかけている途中でふと不安になりました。
「お腹の子はモールス信号で何を言っているのか分かるのだろうか…？」
と。
そんなわけで今日はモールス信号の復号可能性を調べてみようかと思います。
そもそもモールス信号とは
モールス信号は「トン」「ツー」あるいは「・」「－」という短点・長点の組み合わせをアルファベットに対応させた符号化方式です。
アルファベットのモールス信号での表現は下記の通りです。1
| アルファベット | モールス信号での表現 |
|---|---|
| A | ・－ |
| B | －・・・ |
| C | －・－・ |
| D | －・・ |
| E | ・ |
| F | ・・－・ |
| G | －－・ |
| H | ・・・・ |
| I | ・・ |
| J | ・－－－ |
| K | －・－ |
| L | ・－・・ |
| M | －－ |
| N | －・ |
| O | －－－ |
| P | ・－－・ |
| Q | －－・－ |
| R | ・－・ |
| S | ・・・ |
| T | － |
| U | ・・－ |
| V | ・・・－ |
| W | ・－－ |
| X | －・・－ |
| Y | －・－－ |
| Z | －－・・ |
| ピリオド | ・－・－・－ |
| カンマ | －－・・－－ |
| 重点又は除去の記号 | －－－・・・ |
| 疑問符 | ・・－－・・ |
ふむふむ。有名な「SOS」は「・・・－－－・・・」であることが上の表で分かりますね。
一意復号可能性と瞬時復号可能性
一意復号可能性
一意復号可能性というのは情報を符号化、つまり特定の信号パターンに変換する際にもっとも重要な概念です。
モールス信号ではアルファベットを「・」「－」に変換してから送信しますが、その「・」「－」を受け取った時にアルファベットに逆変換（これを復号といいます）できなければ、結局何を言っているか分かりませんよね。
さらに言えば、「AB」を変換した符号化列が「AB」「CD」どちらにも復号可能だとすると、送り手の言いたかったこととは別の意味に解釈されてしまう（「AB」と言いたかったのに「CD」として伝わってしまう）かもしれません。
それを防止するために、「AB」を符号化したものは必ず「AB」に復号可能である、というのを保証するのが一意復号可能性です。
瞬時復号可能性
さらに瞬時復号可能性という概念があります。
瞬時復号可能性とは、ある符号を受け取ったら後続の符号が到着するのを待たずに復号可能であることを保証するものです。 これは通信などに符号を利用する上では非常に重要な性質です。符号が全て届くまで元の情報に逆変換できないとなると、電話などの双方向通信は出来なくなってしまいます。
で、どうやってそれを調べるの？
当然ですが「瞬時復号可能な符号は一意復号可能である」という性質があります。 なので瞬時復号可能性を調べることにしましょう。
符号の木
瞬時復号可能性を調べる方法に符号の木というものがあります2。 これは符号の構成をツリー状に表現したものです。符号列の符号を先頭から順番に見ていき、符号が「・」であれば左下、「－」であれば右下に進んでいくというものです。木構造の中の－を枝、枝と枝の間にある◯を節、それ以上先に枝がない◯を葉といいます3
「全符号が葉に割り当てられている」のであればその符号は瞬時復号可能です。
下の図はモールス信号を符号の木で表現した図です。
これを見ると全アルファベットが葉に割り当てられているわけではないので、少なくとも瞬時復号可能ではないことが分かります。
これは困りました。モールス信号は本当に瞬時復号不可能なのでしょうか？
実はモールス信号の送信時にはアルファベットとアルファベットの間隔を「・」の3倍空けなければいけないのです。
というわけで、アルファベット間の空白も一つの符号と捉えて符号の木を再構成したのが下の図です。枝に「・」も「－」も書いていないものが空白を表しています。
これを見ると全ての記号が葉に割り当てられており、瞬時復号可能であることが分かります。 （そもそも空白はアルファベット間にしか使われないのでアルファベットを一意に符号化すれば瞬時復号可能なのは自明ですが……）
というわけで無事モールス信号の瞬時復号可能性を示せました。なのでこれからもお腹の子にモールス信号を使って話しかけていこうと思います。
