小学5年生が理解する「誤り訂正符号」（デジタル社会を支えるテクノロジー：誤り訂正符号って何？その42）

前回まででは『畳込み符号』の代表的な復号法『ビタビ復号法』を紹介した。また『ビタビ復号法』の発明者のビタビ氏が、第3世代携帯電話の基本方式や、その技術を実装したLSIを作っているQualcomm社の創業者であることも紹介した。

私：「『畳込み符号』と、その復号法である『ビタビ復号法』はどうだった？」

息子：「何か『ブロック符号』の時よりも、簡単だった。」

私：「おっ！凄いね。ちなみにパパは『ブロック符号』を先に覚えたことや、『有限体』を先に学んだこともあって、逆に『畳込み符号』に慣れるまで時間がかかったよ。」

息子：「そうなの？」

私：「うん。だけど、タクムの言ってることの方が普通の感覚なんだ。『ブロック符号』の場合、実用的な『BCH符号』や『リード・ソロモン符号』などに代表される『巡回符号』を理解するには『有限体』が必要で符号化の段階から、なかなか理解できない人が多い。けど『木符号』の場合は『畳込み符号』やその復号法『ビタビ復号』も『有限体』を使わずに済むので、『有限体』を知らなくても理解できて簡単に感じる人が多いんだ。」

息子：「うん、タクムもそう思った。他の人もそうなんだね。」

私：「そうなんだ。ただ、『畳込み符号』などの『木符号』は理論的には浅いこともあって研究対象になり難くて、『誤り訂正符号』の研究対象としては『ブロック符号』が中心だったんだ。その流れが、一時期大きく変えたのが2つの『畳込み符号』を組合せて使う『ターボ符号』なんだ。」

息子：「じゃあ、今は『ターボ符号』が研究対象の中心なの？」

私：「それが違うんだ。『ターボ符号』が研究対象の中心だった時期もそんなには長く続かなかったんだ。20年位前までの10年もない期間ぐらいだったんだ。」

息子：「どうして？」

私：「20年位前に『低密度パリティ検査符号』、略して『LDPC符号』が再発見されて、『ターボ符号』と同じような『繰り返し復号法』を使うことで『ターボ符号』を上回る誤り訂正能力があることがわかったからなんだ。何よりも『ターボ符号』は特許のせいで使うのに面倒な手続きや、お金がかかるけど、『LDPC符号』はそれが無かったからなんだ。」

息子：「再発見されたってことは、もっと前に誰かが発明してあったの？」

私：「驚くことに1963年にギャラガーさんが博士論文の中で発表してたんだけど、当時は実現不可能だったから、暫く忘れ去られていたんだ。ところが50年位たってから、マッカイさんが再発見して紹介したことから注目されるようになったんだ。」