有限長解析情報理論と最適化理論による高信頼高効率通信の相乗的基礎研究
A synergistic fundamental study of high reliability and high efficiency communication based on nonasymptotic information theory and optimization(アプローチ a-0) ある理想的な状況を仮定したもとで、符号化レートと誤り確率の一方を制約条件として、他方を最適化することにより理論限界を導出する。
(アプローチ b-0) 上述した(アプローチ a-0)で示された理論限界を達成する符号器（符号化関数）や復号器（復号関数）を構成する。

松嶋 敏泰 ( Toshiyasu MATSUSHIMA, Dr.Eng.)早稲田大学 基幹理工学部 応用数理学科 教授(アプローチ a-0)により理論限界を示す事自体、情報(Professor, Waseda University, School of Fundamental Scienceand Engineering, Department of Applied Mathematics)を科学する意味で意味があり、また(アプローチ b-0)を行う上でも理想的目標が掲げられる意味は大きい。し電子情報通信学会 IEEE 他
研究専門分野：データ科学、情報理論、符号理論、暗号理論

かしながら、これまで(アプローチ a-0)と(アプローチb-0)はほとんど独立に発展し、融合することはほとん

あらましどなかった。これに対して、近年、以下の(アプローチ

本研究の目的は、通信の基礎理論として大きな成功をa-1)、(アプローチ a-1')、(アプローチ b-1)のような、収めてきた情報理論・符号理論をさらに推し進め、有新たなアプローチによる研究が行われるようになって限の長さのデータ系列や符号長が有限の場合など、よきた。

り実用に則した条件のもとでの通信システムの性能の理論限界を導出し、その理論限界を達成する符号、復(アプローチ a-1) 有限のデータ長や微小な誤り確率を号法の組を構成することである。その際、符号化・復許したもとで、符号化レートや誤り確率の理論限界を号システム全体を最適化理論の枠組みに落とし込む点導出する。に特色がある。結果として、符号化レートや誤り確率の理論限界を、実用的なデータ長や実用的な誤り確率(アプローチ a-1') 符号と復号のクラスを固定したもとを許したもとで導出することができた。また、符号化・で、データの長さが限りなく大きくなることを許した

復号システムにおいて一部を最適化問題とみなした際際の平均誤り確率を導出する。の目的関数やヒューリスティクスとして用いられうる量の整理、拡張を行うことができた。

(アプローチ b-1) 最適化理論を用いた復号アルゴリズムの構築や符号の探索による構成を行う。

１．研究の背景
情報理論・符号理論は、通信の数理的基礎理論とし２．研究の目的てのみならず、情報を扱う科学及び工学の基礎理論と従来の伝統的なアプローチである(アプローチ a-0)して現代の情報化社会の発展に寄与してきた。情報理と(アプローチ b-0)の関係に比べれば、(アプローチ a-論・符号理論では、雑音のある通信路を通して送信者

1)、(アプローチ a-1')、(アプローチ b-1)の研究アプロ

から受信者に情報を効率的に高信頼度で送る問題を数ーチは接近してきたと言える。(アプローチ a-0)と違い、理モデル化して研究を行う。通信の効率性を測る評価(アプローチ a-1)は実際に(アプローチ b-1)で到達すべ基準として符号化レート*1 が、信頼性を測る評価基準

き工学的目標となりうる。また、(アプローチ a-1')はとして復号誤り確率*2 が用いられる。両者はトレード(アプローチ b-1)の符号のクラスの設定や符号の探索オフの関係があり、伝統的に以下の(アプローチ a-0)、(アプローチ b-0)により研究が行われてきた。に直接役立ち、２つのアプローチが融合してきている。
そこで本研究では、この流れをさらに加速させ、以下の(アプローチ a-2)と(アプローチ b-2)により、理論

1

TELECOM FRONTIER No.110 2021 WINTER

有限長解析情報理論と最適化理論による高信頼高効率通信の相乗的基礎研究
A synergistic fundamental study of high reliability and high efficiency communication based on nonasymptotic information theory and optimization
限界の導出と符号・復号法の構築の研究をさらに接近・システム全体を大きな最適化問題として捉え、(アプロ融合させ、相乗的研究を目指すことを目的とした。

ーチ a-2)によって求められた実用的な制約のもとでの理論限界を目標とした大局的最適化を行うことを目指(アプローチ a-2) 符号化レートや誤り確率の理論限界した。もちろん、今までの重要な成果である、高性能を、実用的なデータ長や実用的な誤り確率を許して導な代数的復号法や確率伝搬法などはアルゴリズムの中出する。に組み入れ、高性能な符号の構造や性能が良いとされる符号のクラスも積極的に符号の探索で用いていく。

(アプローチ b-2) 符号化復号システム全体を大きな最適化問題として定式化し、より実用的な制約のもと（準）３．２．現在までに得られた研究成果
現在までに、(アプローチ a-2)に関しては以下の成果

最適な符号と復号の組として求める。

が得られた。
例えば、(アプローチ a-2)で導出された実用に近い条
件での理論限界は、(アプローチ b-2)の最適化による符(α-1) 情報理論においては、情報源から確率的にデー号・復号法の構成の直接的な目標となる上、ヒューリタが出力されると仮定したもとで議論が行われる。こスティック関数*3 として、アルゴリズムの高速化や大の情報源から出力されたデータ𝑥と、復号後のデータ𝑦局的最適性の保証に役立つ。この研究により、より工との間に違いを許容することで、データ𝑥と𝑦が完全に学的見地から有用な高効率・高信頼度の通信や情報処一致する場合に比べて圧縮の効率を高めることが可能

理システムの設計に直接的に役立つ基礎理論の構築をである。このようなデータ圧縮は、有歪みデータ圧縮目指した。と呼ばれる。例えば、画像や音声のデータは、もとのデータと復号後のデータが多少異なっていても問題な３．研究の方法、研究の結果い場合が多いため、これらのデータの圧縮には有歪み３．１．研究の進め方データ圧縮の研究成果が用いられる。データ圧縮の効

従来、(アプローチ a-1)による研究（例えば、[1]、 [2]）率を測る代表的な評価基準として平均符号語長（情報では、確率論における中心極限定理等を用いて、理論源の確率分布により符号語長の期待値を取った量）が限界の解析が行われている。しかしながら、データがあり、これを一般化した尺度として符号語長のキュム独立同分布に従うという理想的な仮定や、数値的に求ラント母関数がある。本研究では、有限の実用的なデめにくい限界が導出されている。

ータ長に対する符号語長のキュムラント母関数の理論

したがって、(アプローチ a-2)の研究では、実用に近限界を、レニーエントロピーに基づいた情報量によりい仮定のもとでの理論限界の導出や、より精密に数値明らかにした[12]。

的に誤り確率等が導出できる解析手法を構築することを目指した。また、通信路容量*4 等、最大、最小を求(α-2) データ圧縮の研究において、平均符号語長以外める最適化問題として解かなければ数値が得られないにも幾つかの評価基準が考えられている。その中の一問題もあり、このような問題を解く最適化法も明らかつに、オーバーフロー確率がある。これは、データ 1にすることを目指した。

シンボル当たりの符号語長が、あるレート（しきい値）

一方で、従来、(アプローチ b-1)による研究（例えば、を超過する確率として定義される。本研究では、有歪[3], [4], [5], [6]）では復号問題、符号構成問題を制約付みデータ圧縮問題に対して、オーバーフロー確率を微き最適化問題とみなして研究が行われている。しかし小量以下にしたもとでの最小のレートが、有限の実用ながら、それらは復号問題、符号構成問題をそれぞれ的なデータ長に対して、スムース最大エントロピーと単体で最適化問題とみなすにとどまっている。

いう情報量を用いて特徴付けられることを明らかにしそこで、(アプローチ b-2)の研究では、符号化・復号

た[9], [13]。
2

TELECOM FRONTIER No.110 2021 WINTER

有限長解析情報理論と最適化理論による高信頼高効率通信の相乗的基礎研究
A synergistic fundamental study of high reliability and high efficiency communication based on nonasymptotic information theory and optimization(α-3) 情報理論において、データ圧縮と密接に関係の度の通信や情報処理システムの設計に直接的に役立つある問題として guessing がある。これは、確率変数列ような基礎理論を、ある程度打ち立てることができたの実現値を、なるべく少ない回数の質問により推測すと考えている。

る問題である。この問題に対して、有限の系列長の確率変数を推定する場合、最小の推定回数の理論限界が、レニーエントロピーに基づいた情報量により特徴づけ

４．将来展望本研究で得られた基礎理論は今後、高信頼度かつ高られることを解明した[16]。

効率の通信や処理が要求されるような通信工学関連分野において、システムの設計や構築に寄与することが(α-4) 情報源の確率分布が未知である場合のデータ期待される。

圧縮をユニバーサルデータ圧縮と呼ぶ。ユニバーサルデータ圧縮において、有限のデータ長に対して圧縮率

用語解説の高いデータ圧縮法として、ベイズ符号がある。ベイ*1 符号化レート・・・情報源から発生する𝑘シンボル

ズ符号は平均符号語長という評価基準のもとでは多くの情報系列を符号器（符号化関数）により𝑛シンボの研究がなされてきた。しかしながら、オーバーフロ

ルの符号語に変換するとき、符号化レートは𝑘/𝑛とー確率という評価基準のもとでは、これまで殆ど研究定義される。

が な さ れ て い な か っ た 。 本 研 究 で は 、 moderate*2 復号誤り確率・・・雑音等の影響で符号語が確率的

deviation の枠組み*5 において、ベイズ符号をオーバーに変化した𝑛シンボルの受信語は、復号器（復号関フロー確率という評価基準のもとで理論解析を行った。

数）により情報系列に復号される。この際に、元のその結果、ベイズ符号は、オーバーフロー確率が最小情報系列と異なる場合に復号誤りとなり、そのようという意味で最適な符号と同様の性質を有することをな事象が生起する確率が復号誤り確率である。
*3 ヒューリスティック関数・・・経験的な知識をもと明らかにした[7]。に構成した評価関数のこと。
一方で、(アプローチ b-2)に関しては以下の成果*4 通信路容量・・・符号長𝑛を十分大きくしたとき、復号誤り確率を漸近的に 0 にするという条件のもが得られた。とで達成可能な符号化レート𝑘/𝑛の上限を通信路(β-1) 符号構成の目的関数になりうる量として、重み容量と呼ぶ。

分布という量がある。従来、我々は富士山型空間結合*5 moderate deviation の枠組み・・・オーバーフロー

符号[8]と呼ばれる新たな符号クラスを提案していた

確率とレート（しきい値）はどちらも小さい方が望が、この符号に対して重み分布を解明し、Expected

ましいが、これらの量の間にはトレードオフの関係

Graph Evolution や Covariance Evolution による評がある。そのため、オーバーフロー確率とレートの価を行った[10], [11], [14], [15]。

トレードオフをコントロールするパラメータを導入し、これを上手く設定することで、オーバーフロ(β-2) 様々な最適化問題とその解法アルゴリズムにー確率とレートのどちらもある速度で小さくなっついての従来研究の整理を行った。また、現状の符号ていくという問題設定で解析を行うことがある。こ化復号システムにおいてシステムの一部を最適化問題のような問題設定は、情報理論の研究において、とみなした際の目的関数やヒューリスティクスとして

moderate deviation の枠組みと呼ばれる。

用いられうる量の整理、拡張を行った[17]。
参考文献
[1]

３．３．本研究の意義及び研究者自身の見解

ShotaSaito,

NozomiMiya,

Toshiyasu

Matsushima, Evaluation of the Bayes Code from

本研究により、より工学的見地から高効率・高信頼
3TELECOM FRONTIER No.110 2021 WINTER

有限長解析情報理論と最適化理論による高信頼高効率通信の相乗的基礎研究
A synergistic fundamental study of high reliability and high efficiency communication based on nonasymptotic information theory and optimization
Viewpoints of the Distribution of Its Codeword[10] 中原悠太，松嶋敏泰，富士山型空間結合符号の重Lengths, IEICE Trans. on Fundamentals of

み分布に関する一考察，第 40 回情報理論とその応Electronics, Communications and Computer用シンポジウム，2017.

Sciences, vol. E98-A, no. 12, pp. 2407-2414, 2015.

[11] Yuta Nakahara, Toshiyasu Matsushima, A Note

[2] Y. Polyanskiy, H. V. Poor, and S. Verdú, Channel

on Weight Distributions of Spatially “Mt. Fuji”

Coding Rate in the Finite Blocklength Regime,

Coupled LDPC Codes, IEICE Transactions onIEEE Trans. Inf. Theory, vol.56, no.5, pp.2307-

Fundamentals of Electronics, Communications

2359, 2010.

and Computer Sciences, E101.A(12), pp.2194 -[3]ShunsukeHorii,Toshiyasu

Matsushima,Hirasawa,LinearProgramming[12] Shota Saito, Toshiyasu Matsushima, Cumulant

Decoding of Binary Linear Codes for Symbol-Pair

Generating Function of Codeword Lengths in

Read Channels, Proceedings of 2016

Variable-Length Lossy Compression Allowing

Shigeichi[4]

Shunsuke
Shigeichi

2198, 2018.

Horii,Toshiyasu

Matsushima,

Positive Excess Distortion Probability, IEEEHirasawa,Linear

Programming

International Symposium on Information Theory,

Decoding of Binary Linear Codes for Symbol-Pair

2018.

Read Channels, Proceedings of 2016[13]Shota

Saito,

HidekiYagi,Toshiyasu[5] 堀井俊佑, 松嶋敏泰, 平澤茂一, シンボルペア通Matsushima, New Results on Variable-Length

信路における 2 元線形符号の線形計画復号法にLossy Compression Allowing Positive Overflow

ついて, 電子情報通信学会技術研究報告, vol.115,andno.214, IT2015-34, pp.1-6,

International Symposium on Information Theory

2015．

[6] E. Sharon and S. Litsyn, Constructing LDPCDistortion

Probabilities,and Its Applications, 2018.

Codes by Error Minimization Progressive Edge

[14]

Yuta

Nakahara,

Toshiyasu

Matsushima,Growth, IEEE Trans. Commun. vol.56, no.3,

Expected Graph Evolution for Spatially ``Mt.

pp.359-368, 2008.

Fuji''[7] Shota Saito, Toshiyasu Matsushima, Evaluation

CoupledLDPC

Codes,

International

Symposium on Information Theory and Itsof overflow probability of Bayes code in moderate

Applications, 2018.

on[15] 中原悠太，松嶋敏泰，富士山型空間結合符号に対Fundamentals of Electronics, Communications

する Covariance Evolution，第 41 回情報理論とそand Computer Sciences, E100A(12), pp.2728 -の応用シンポジウム，2018.

deviation

regime,IEICE

Transactions

2731, 2017.
[8]

ExcessYuta

Nakahara,[16] Shota Saito, Toshiyasu Matsushima, NonShota

Saito,

Toshiyasu

Asymptotic Fundamental Limits of Guessing

Matsushima, Spatially "Mt. Fuji" Coupled LDPC

SubjecttoDistortion,IEEEInternational

codes, IEICE Transactions on Fundamentals ofSymposium on Information Theory, 2019.
[17] 中原悠太，松嶋敏泰，Spatially Coupled Uneven

Electronics, Communications and Computer

LDPC Codes，第 42 回情報理論とその応用シンポ

Sciences, E100A(12), pp.2594 - 2606, 2017.
[9] Shota Saito, Hideki Yagi, Toshiyasu Matsushima,

ジウム予稿集，2019.

Variable-Length Lossy Compression Allowing
Positive

OverflowandExcess

Distortion

この研究は、平成 28 年度ＳＣＡＴ研究助成の対象とProbabilities, IEEE International Symposium on

して採用され、平成 29 年～令和元年度に実施された

Information Theory 2017

ものです。
4

TELECOM FRONTIER No.110 2021 WINTER