シャノン限界を達成しかつ実行可能な通信路符号を実現 ～効率の良い光通信や無線通信が可能に～

日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：澤田純、以下　NTT）は、シャノン限界を達成しかつ実行可能な通信路符号　（誤り訂正符号）「CoCONuTS^※1」を実現しました。

本技術は、計算機科学者シャノンによって求められた、通信効率の限界（シャノン限界^※2）を達成する誤り訂正符号を実現する技術です。一つの通信路が与えられた時、そのシャノン限界を達成するためには、一般には膨大な計算量が必要だと考えられていました。一方で、実用的な実装方法でシャノン限界を達成できる符号が知られていましたが、これらの符号がシャノン限界を達成するのは特殊な通信路に限られていました。

本技術により任意の通信路でシャノン限界を達成する通信路符号を構成できることを証明しました。さらに、従来法ではシャノン限界を達成できなかった通信路に対して、実装した符号が従来法を超える性能を持つことを確認しました。

本技術を用いることで、既存の方法よりも効率の良い通信が実現できます。今後、光通信や無線通信技術などに、本技術を応用していく予定です。

背景

通信を行ううえでは、雑音のある環境下でも正しく情報を伝える必要があります。これを実現する技術は「通信路符号」あるいは「誤り訂正符号」と呼ばれており、光通信や無線通信に限らず、計算機の内部やハードディスク・光ディスク等の記録装置、スマートフォン等で情報を読み取るための二次元コード等に応用されています。

雑音のある環境（通信路）が与えられた時、正しくメッセージを伝えることができる効率^※3には限界があります。このような通信効率の限界は、1948年にこれを発表した計算機科学者シャノンにちなんで「シャノン限界」と呼ばれています。しかしながら、シャノンが提案した符号は膨大な計算量を必要としていたため、その実行は困難でした。実行可能なシャノン限界を達成する符号の構成は、シャノンが創始した情報理論の70年にわたる課題です。

その後、シャノン限界を達成する実用的な符号としてLDPC符号※4やポーラ符号が開発され、近年の第5世代移動通信システム（5G）に実装されています。しかしながら、これらの符号がシャノン限界を達成するのはある特殊な通信路に限られており、一般の通信路では限界を達成できません。

研究の成果

NTTコミュニケーション科学基礎研究所は、シャノン限界を達成する符号化技術 CoCoNuTSを開発しました。本技術を用いることにより通信路符号に限らず、情報源符号や情報理論的安全性を持つ暗号などの通信のあらゆる問題に対して、限界を達成と実行可能性を両立させる符号を構築できます。今回は、本技術を通信路符号へ応用することにより、それがシャノン限界を達成できることを数学的に証明しました。また、シミュレーション実験により、従来のLDPC符号ではシャノン限界を達成できなかった通信路に対して、提案法が従来法を超える性能を持つことを確認しました。

技術のポイント

（1）通信路符号（誤り訂正符号）が実現する通信システム

図1は通信路符号が実現する通信システムを示しています。ここでは通信会社の基地局がメッセージを送信する送信者となり、スマートフォンを持ったユーザーが受信者となっています。符号器は送信したいメッセージ M を符号化して通信路入力 X へ変換します。変換された信号は電波の周波数や位相や強度に変換（変調）されて送信されますが、電波を送受信して通信路に出力 Y を得る際に雑音が混入することを想定します。復号器は通信路出力 Y から元の再生メッセージ M ' を復元します。ここで、正しい通信とは、メッセージと再生メッセージが同一（M＝M '）であることを意味しています。そこで、メッセージと再生メッセージが異なる（M≠M '）事象の確率を「復号誤り確率」と定義して、この通信システムでは復号誤り確率が0に限りなく近いような符号化・復号化の方法を実現することを目指します。

（2）符号化の具体例と通信効率

図2ではメッセージ"01"を送信することを例にして、符号化の具体的な方法を示しています。符号器はメッセージ"01"を符号化して通信路入力"01011"を求めています。この符号器では、メッセージを2回繰り返した後でメッセージの左右の2ビットの加えた「検算ビット」（排他的論理和）を付加するという操作を行っています。この例では、受信時にノイズが混入して"01111"という通信路出力が得られました。復号器は符号化のルールからノイズが混入した位置を特定して、再生メッセージ"01"を得ます。この手続きが復号化と呼ばれるものです。今回は正しいメッセージと再生メッセージが一致して正しい通信が行われましたが、雑音によっては正しくメッセージが再生できない場合もあります。

図2の例では、2ビットのメッセージを5ビットの通信路入力へ変換しました。通信効率は2／5＝0.4 で評価できます。この比が大きいほど効率は高くなり、高速な通信が可能であることを意味しています。

（3）シャノン限界

図3はシャノン限界（通信路容量）を説明しています。図1では、符号が満たすべき条件として、復号誤り確率が0に限りなく近いことを要請しました。一方で図2では、送信したいシンボル数と送信信号数（例では符号化前後のビット数）の比を符号の効率と定義しました。シャノン限界は復号誤りが0に限りなく近い符号の通信効率限界です。シャノンは効率の限界が図3に示されている式に等しいことを示しました。シャノン限界を超えた効率を持つ符号を設計することは理論上不可能であり、もしもこの限界を達成する方法が実現できれば、理論的にはこれ以上の性能向上が見込めないことになります。なお、シャノン限界を達成するためには、通信路入力分布 P を最適化する必要があります。

（4）提案法CoCoNuTSの技術ポイント

図4は、CoCoNuTSを用いた通信路符号の構成を示しています。提案法では、二つの疎行列（成分のほとんどが0の行列） A，B とベクトル c を用いて構成しています。さらに符号器と復号器に現れる写像 fA,B ，gA （図4の赤枠の部分）として、後述の「拘束条件を満たす乱数生成器」を用いて最適な通信路入力分布 P を実現することにより、シャノン限界を達成することができるようになりました。

従来法であるLDPC符号では、パリティ検査行列Aを用いて、Ax =c を満たすすべてのx を通信路入力とします。このため、得られる通信路入力の分布は一様分布になります。従って、図3で示したシャノン限界の式で、通信路入力分布 P が一様分布の時に最大値（max）を達成していれば、LDPC符号はシャノン限界を達成していると言えます。逆に、最大値を達成する通信路入力分布 P が一様分布ではない場合はシャノン限界を達成できないことが分かります。

（5）拘束条件を満たす乱数生成器

図5，6は、符号化・復号化で用いる「拘束条件を満たす乱数生成器」の具体的な説明を示しています。それぞれのページで示した確率分布 Q を用いて発生させた乱数 x を用いることにより、図4にある写像 fA,B ，gA の実現が容易になります。そこでは、高次元の乱数 x を直接生成するかわりに、確率分布 q を用いて一次元の乱数 xj を逐次的に発生させることにより、計算の実行が可能になりました。

（6）シミュレーション実験

図7はシミュレーション実験で提案法とLDPC符号を比較した結果を示しています。グラフの横軸は通信効率を示しており、右にあるほど性能が良いことになります。グラフの縦軸は復号誤り確率を示しており、下にあるほど性能が良いことになります。グラフは提案法がLDPCよりもよい性能を持つことを示しています。例えば、縦軸の誤り確率 10-4 で両者を比較したとき、提案法は符号化レートで0.03、情報量に換算すると2000ビットあたり60ビットの情報を多く送信できることが分かりました。

続く図8では、通信効率を固定して両者を比較したものを可視化しています。図7にある実験条件で通信効率0.6の符号化を1200回繰り返した時に、復号に失敗した場合を黒点で示して頻度を可視化しました。LDPC符号では7回の復号誤りを観測したのに対して、提案法は一度も復号誤りを観測しませんでした。この結果から、同じ雑音環境で同じ量のメッセージを送信した場合は、提案法は従来法に比べてより信頼性が高いことが分かりました。

図9では、提案法と従来法を実際の通信に近い状況で実行した場合を比較しました。実際の通信は復号誤りがないことを想定して画像を圧縮したうえで符号化しています。このため一箇所でも復号誤りが起こればファイルが破壊され、画像の大部分は再生不可能となります。通信効率0.5では、提案法も従来法のLDPC符号も正しく復号が行われていますが、通信効率0.6のLDPC符号では、復号誤りが発生してファイルが破壊されていることが観測できました。このことからLDPC符号による符号化の限界は0.5と0.6の間にあり、提案法はそれを超える性能を持つことが確認できました。また最適な符号を用いた時の通信効率であるシャノン限界は0.6よりも大きいことが分かります。

今後の展開

今回実現した技術について、今後、実装のための周辺技術の確立を進め、実環境においてより高速な通信を実現するための要素技術として、本技術の応用の検討を進めます。

用語解説