情報通信システム(特)論II Information and Communication Systems II

情報通信システム

(

)

II

Information and Communication Systems II

第４回講義資料

Lecture notes 4

通信路符号化

Channel Coding

豊橋技術科学大学

Toyohashi University of Technology

電気・電子情報工学系

Department of Electrical and Electronic Information Engineering

准教授 竹内啓悟

Associate Professor Keigo Takeuchi

離散無記憶通信路を通じた情報伝送

Information transmission over discrete memoryless channel (DMC)

符号器(Encoder) DMC 復号器(Decoder)

Message ℳ Message ℳ

符号器(Encoder) 𝑓𝑓:ℳ → 𝓒𝓒 ⊂ 𝒳𝒳^𝑛𝑛 離散無記憶通信路(DMC)

𝑃𝑃 𝒀𝒀 = 𝒚𝒚 𝑿𝑿 = 𝒙𝒙 = �

𝑖𝑖=1

𝑛𝑛 𝑊𝑊(𝑦𝑦_𝑖𝑖|𝑥𝑥_𝑖𝑖) , 𝑊𝑊:𝒴𝒴 × 𝒳𝒳 → (0, 1]

𝒳𝒳：有限入力アルファベット(Input alphabet) 𝒴𝒴：有限出力アルファベット(Output alphabet)

メッセージ𝑚𝑚 ∈ ℳ = {1, … ,𝑀𝑀}を長さ𝑛𝑛の符号語𝒄𝒄(𝑚𝑚) ∈ 𝓒𝓒に写像する。

Mapping of the message 𝑚𝑚 ∈ ℳ onto a codeword𝒄𝒄(𝑚𝑚) ∈ 𝓒𝓒of length 𝑛𝑛.

復号器(Decoder) 𝑔𝑔:𝒴𝒴^𝑛𝑛 → ℳ

長さ𝑛𝑛の受信語𝒚𝒚 ∈ 𝒴𝒴^𝑛𝑛からメッセージ𝑚𝑚 ∈ ℳ� を復号する。

Decoding of a message 𝑚𝑚 ∈ ℳ� from a received word 𝒚𝒚 ∈ 𝒴𝒴^𝑛𝑛 of length 𝑛𝑛.

仮定(Assumption) 復号器は送信メッセージ𝑚𝑚以外のすべてを知っている。

The decoder has the full knowledge except for the transmitted message 𝑚𝑚.

𝓒𝓒 𝒴𝒴^𝑛𝑛

達成可能性と通信路容量(Achievability and channel capacity)

レート(Rate)

𝑅𝑅 = 1

𝑛𝑛 log𝑀𝑀 時点当たりに伝送される情報量

The amount of transmitted information per channel use

平均誤り確率(Average error probability)

𝑝𝑝_e = 1

𝑀𝑀 �_𝑚𝑚=1

𝑀𝑀

𝑃𝑃(𝑚𝑚 ≠ 𝑚𝑚|𝑚𝑚) .�

極限𝑛𝑛 → ∞において、平均誤り確率𝑝𝑝_eが0に収束するような符号器𝑓𝑓と

復号器𝑔𝑔が存在するとき、レート𝑅𝑅は達成可能であると言う。

We say tha a rate 𝑅𝑅 is achievable when there exist an encoder 𝑓𝑓 and a decoder 𝑔𝑔 such that the average error probability 𝑝𝑝_e tends to zero as 𝑛𝑛 → ∞.

通信路容量(Channel capacity)

𝐶𝐶 = sup 𝑅𝑅 ∶ 𝑅𝑅 is achievable.

達成可能なレートの上限(Supremum of achievable rates)

離散無記憶通信路に対する通信路符号化定理(Channel coding theorem for DMC)

𝐶𝐶 = max_{𝑃𝑃(𝑋𝑋)} 𝐼𝐼(𝑋𝑋;𝑌𝑌)

𝐼𝐼 𝑋𝑋;𝑌𝑌 = �

𝑥𝑥∈𝒳𝒳,𝑦𝑦∈𝒴𝒴

𝑊𝑊 𝑦𝑦 𝑥𝑥 𝑃𝑃 𝑋𝑋 = 𝑥𝑥 log𝑊𝑊 𝑦𝑦 𝑥𝑥 𝑃𝑃 𝑋𝑋 = 𝑥𝑥 𝑊𝑊 𝑦𝑦 𝑃𝑃(𝑋𝑋 = 𝑥𝑥) ,

𝑊𝑊 𝑦𝑦 = �

𝑥𝑥∈𝒳𝒳

𝑊𝑊 𝑦𝑦 𝑥𝑥 𝑃𝑃(𝑋𝑋 = 𝑥𝑥) .

相互情報量𝐼𝐼(𝑋𝑋;𝑌𝑌)は、入力分布𝑃𝑃(𝑋𝑋)と通信路𝑊𝑊(𝑦𝑦|𝑥𝑥)を使って以下で 与えられる。

For an input distribution 𝑃𝑃(𝑋𝑋) and the channel 𝑊𝑊(𝑦𝑦|𝑥𝑥), the mutual information 𝐼𝐼(𝑋𝑋;𝑌𝑌)is given by

特に、最大化の解が一様分布𝑃𝑃 𝑋𝑋 = 1/|𝒳𝒳|となるような通信路𝑊𝑊を 対称通信路と呼ぶ。

In particular, the channel 𝑊𝑊 is called symmetricif the solution to the maximization is the uniform distribution 𝑃𝑃 𝑋𝑋 = 1/ 𝒳𝒳 .

加法的白色ガウス雑音(AWGN)通信路を通じた情報伝送

Information transmission over additive white Gaussian noise (AWGN) channel

符号器(Encoder) AWGN 復号器(Decoder)

Message ℳ Message ℳ

符号器(Encoder) 𝑓𝑓:ℳ → 𝓒𝓒 ⊂ ℂ^𝑛𝑛 AWGN通信路(AWGN channel)

𝑝𝑝_{𝒀𝒀|𝑿𝑿} 𝒚𝒚 𝒙𝒙 = �

𝑖𝑖=1

𝑛𝑛 𝑤𝑤(𝑦𝑦_𝑖𝑖|𝑥𝑥_𝑖𝑖) ,

メッセージ𝑚𝑚 ∈ ℳ = {1, … ,𝑀𝑀}を長さ𝑛𝑛の符号語𝒄𝒄(𝑚𝑚) ∈ 𝓒𝓒に写像する。

Mapping of the message 𝑚𝑚 ∈ ℳ onto a codeword𝒄𝒄(𝑚𝑚) ∈ 𝓒𝓒of length 𝑛𝑛.

復号器(Decoder) 𝑔𝑔:ℂ^𝑛𝑛 → ℳ

長さ𝑛𝑛の受信語𝒚𝒚 ∈ ℂ^𝑛𝑛からメッセージ𝑚𝑚 ∈ ℳ� を復号する。

Decoding of a message 𝑚𝑚 ∈ ℳ� from a received word 𝒚𝒚 ∈ ℂ^𝑛𝑛 of length 𝑛𝑛.

仮定(Assumption) 復号器は送信メッセージ𝑚𝑚以外のすべてを知っている。

The decoder has the full knowledge except for the transmitted message 𝑚𝑚.

𝑤𝑤 𝑦𝑦 𝑥𝑥 = 1

𝜋𝜋𝜎𝜎² 𝑒𝑒^{− 𝑦𝑦−𝑥𝑥}

2

𝜎𝜎² .

𝓒𝓒 ℂ^𝑛𝑛

達成可能性と通信路容量(Achievability and channel capacity)

レート(Rate)

𝑅𝑅 = 1

𝑛𝑛 log𝑀𝑀 時点当たりに伝送される情報量

The amount of transmitted information per channel use

平均誤り確率(Average error probability)

𝑝𝑝_e = 1

𝑀𝑀 �_𝑚𝑚=1

𝑀𝑀

𝑃𝑃(𝑚𝑚 ≠ 𝑚𝑚|𝑚𝑚) .�

極限𝑛𝑛 → ∞において、平均誤り確率𝑝𝑝_eが0に収束し、平均電力制約を満たす

ような符号器𝑓𝑓と復号器𝑔𝑔が存在するとき、レート𝑅𝑅は達成可能であると言う。

We say tha a rate 𝑅𝑅 is achievable when there exist an encoder 𝑓𝑓 and a decoder 𝑔𝑔 such that the

average error probability 𝑝𝑝_e tends to zero as 𝑛𝑛 → ∞, and that the average power constraint is satisfied.

通信路容量(Channel capacity)

𝐶𝐶 = sup 𝑅𝑅 ∶ 𝑅𝑅 is achievable.

達成可能なレートの上限(Supremum of achievable rates)

平均電力制約

Average power constraint

1

𝑛𝑛 𝒄𝒄 𝑚𝑚 ^H𝒄𝒄 𝑚𝑚 ≤ 𝑃𝑃 for all 𝑚𝑚 ∈ ℳ.

AWGN通信路に対する通信路符号化定理(Channel coding theorem for AWGN)

𝐶𝐶 = max

𝑝𝑝_𝑋𝑋:𝔼𝔼 𝑋𝑋 ² ≤𝑃𝑃𝐼𝐼(𝑋𝑋;𝑌𝑌) = log 1 + 𝑃𝑃 𝜎𝜎²

𝐼𝐼 𝑋𝑋;𝑌𝑌 = �

ℂ²𝑤𝑤 𝑦𝑦 𝑥𝑥 𝑝𝑝_𝑋𝑋 𝑥𝑥 log𝑤𝑤 𝑦𝑦 𝑥𝑥 𝑝𝑝_𝑋𝑋 𝑥𝑥

𝑤𝑤 𝑦𝑦 𝑝𝑝_𝑋𝑋(𝑥𝑥) 𝑑𝑑𝑥𝑥𝑑𝑑𝑦𝑦 𝑤𝑤 𝑦𝑦 = �

ℂ𝑤𝑤 𝑦𝑦 𝑥𝑥 𝑝𝑝_𝑋𝑋 𝑥𝑥 𝑑𝑑𝑥𝑥.

相互情報量𝐼𝐼(𝑋𝑋;𝑌𝑌)は、入力確率密度関数𝑝𝑝_𝑋𝑋と通信路𝑤𝑤(𝑦𝑦|𝑥𝑥)を使って以 下で与えられる。

For an input probability density function (pdf) 𝑝𝑝_𝑋𝑋 and the channel 𝑤𝑤(𝑦𝑦|𝑥𝑥), the mutual information 𝐼𝐼(𝑋𝑋;𝑌𝑌)is given by

特に、最大値は円対称複素ガウス分布𝑋𝑋 ∼ 𝒞𝒞𝒞𝒞(0,𝑃𝑃)のときのみに達成される。

In particular, the maximization is attained only when 𝑋𝑋 follows the circularly symmetric complex Gaussian (CSCG) distribution with variance 𝑃𝑃.

信号点が複素平面上にガウス分布しているような変調が最良である。

Constellation points are Gaussian-distributed on the complex plane in the best modulation.

最適入力分布の証明(Proof of the optimum input distribution)

ℎ 𝑌𝑌 𝑋𝑋 = 𝑥𝑥 = − �

ℂ𝑤𝑤 𝑦𝑦 𝑥𝑥 log𝑤𝑤(𝑦𝑦|𝑥𝑥)𝑑𝑑𝑦𝑦

最初に、条件付き微分エントロピーℎ(𝑌𝑌|𝑋𝑋 = 𝑥𝑥)を計算する。

We first compute the conditional differential entropy ℎ(𝑌𝑌|𝑋𝑋 = 𝑥𝑥).

= �

ℂ𝑤𝑤 𝑦𝑦 𝑥𝑥 𝑦𝑦 − 𝑥𝑥 ²

𝜎𝜎² + log 𝜋𝜋𝜎𝜎² 𝑑𝑑𝑦𝑦 = log 𝜋𝜋𝑒𝑒𝜎𝜎² .

𝐼𝐼 𝑋𝑋;𝑌𝑌 = ℎ 𝑌𝑌 − ℎ 𝑌𝑌 𝑋𝑋 ≤ log{𝜋𝜋𝑒𝑒 𝔼𝔼 𝑋𝑋 ² − 𝜇𝜇 ² + 𝜎𝜎² } − log 𝜋𝜋𝑒𝑒𝜎𝜎² . 命題3.1’から、相互情報量𝐼𝐼(𝑋𝑋;𝑌𝑌)に関する上界を得る。

From Proposition 3.1’, we obtain an upper bound on the mutual information 𝐼𝐼(𝑋𝑋;𝑌𝑌)

𝑁𝑁 ∼ 𝒞𝒞𝒞𝒞(0,𝜎𝜎²)を𝑋𝑋と独立な確率変数として、𝑌𝑌 = 𝑋𝑋 + 𝑁𝑁と表せるので、

Suppose that 𝑁𝑁 ∼ 𝒞𝒞𝒞𝒞(0,𝜎𝜎²) is independent of 𝑋𝑋. The representation 𝑌𝑌 = 𝑋𝑋+𝑁𝑁 implies

𝔼𝔼 𝑌𝑌 = 𝔼𝔼 𝑋𝑋 ≝ 𝜇𝜇, 𝕍𝕍 𝑌𝑌 = 𝕍𝕍 𝑋𝑋 + 𝕍𝕍 𝑁𝑁 = 𝔼𝔼 𝑋𝑋 ² − 𝜇𝜇 ² + 𝜎𝜎².

≤ log 1 + 𝑃𝑃 𝜎𝜎² .

等号は𝑋𝑋 ∼ 𝒞𝒞𝒞𝒞(0,𝑃𝑃)に限る。(The equality holds only for 𝑋𝑋 ∼ 𝒞𝒞𝒞𝒞(0,𝑃𝑃).) ∎

２ユーザAWGN通信路を通じた情報伝送

Information transmission over 2-user AWGN channel

符号器１(Encoder 1)

AWGN 復号器(Decoder)

Message ℳ₁ Message ℳ₁

符号器𝑘𝑘^{(Encoder 𝑘𝑘)} 𝑓𝑓_𝑘𝑘:ℳ_𝑘𝑘 → 𝓒𝓒_𝑘𝑘 ⊂ ℂ^𝑛𝑛, 𝑘𝑘 = 1, 2 AWGN通信路(AWGN channel)

𝑝𝑝_{𝒀𝒀|𝑿𝑿1,𝑿𝑿2} 𝒚𝒚 𝒙𝒙₁,𝒙𝒙₂ = �

𝑖𝑖=1

𝑛𝑛 𝑤𝑤(𝑦𝑦_𝑖𝑖|𝑥𝑥_1,𝑖𝑖,𝑥𝑥_2,𝑖𝑖) ,

メッセージ𝑚𝑚_𝑘𝑘 ∈ ℳ_𝑘𝑘 = {1, … ,𝑀𝑀_𝑘𝑘}を長さ𝑛𝑛の符号語𝒄𝒄_𝑘𝑘(𝑚𝑚_𝑘𝑘) ∈ 𝓒𝓒_𝑘𝑘に写像する。

Mapping of the message 𝑚𝑚_𝑘𝑘 ∈ ℳ_𝑘𝑘 onto a codeword𝒄𝒄_𝑘𝑘(𝑚𝑚_𝑘𝑘)∈ 𝓒𝓒_𝑘𝑘 of length 𝑛𝑛.

復号器(Decoder) 𝑔𝑔:ℂ^𝑛𝑛 → ℳ₁ × ℳ₂

長さ𝑛𝑛の受信語𝒚𝒚 ∈ ℂ^𝑛𝑛からメッセージ𝑚𝑚�₁ ∈ ℳ₁と𝑚𝑚�₂ ∈ ℳ₂を復号する。

Decoding of messages 𝑚𝑚�₁ ∈ ℳ₁ and 𝑚𝑚�₂ ∈ ℳ₂ from a received word 𝒚𝒚 ∈ ℂ^𝑛𝑛 of length 𝑛𝑛.

𝑤𝑤 𝑦𝑦 𝑥𝑥₁,𝑥𝑥₂ = 1

𝜋𝜋𝜎𝜎² 𝑒𝑒^{− 𝑦𝑦−𝑥𝑥1−𝑥𝑥2}

2

𝜎𝜎² . 符号器２(Encoder 2)

Message ℳ₂ Message ℳ₂

𝓒𝓒₁ 𝓒𝓒₂

ℂ^𝑛𝑛

仮定(Assumption) ユーザごとに独立な符号化が行われる。

達成可能性と通信路容量域(Achievability and capacity region)

レート(Rate)

𝑅𝑅_𝑘𝑘 = 1

𝑛𝑛 log𝑀𝑀_𝑘𝑘 , 𝑘𝑘 = 1, 2.

平均誤り確率(Average error probability)

𝑝𝑝_e = 1

𝑀𝑀₁𝑀𝑀₂ �

𝑚𝑚₁=1 𝑀𝑀₁

�

𝑚𝑚₂=1 𝑀𝑀₂

𝑃𝑃(𝑚𝑚�₁ ≠ 𝑚𝑚₁ or 𝑚𝑚�₂ ≠ 𝑚𝑚₂|𝑚𝑚₁,𝑚𝑚₂) .

極限𝑛𝑛 → ∞において、平均誤り確率𝑝𝑝_eが0に収束し、平均電力制約を満たすよ

うな符号器{𝑓𝑓_𝑘𝑘}と復号器𝑔𝑔が存在するとき、レートの組(𝑅𝑅₁,𝑅𝑅₂)は達成可能であ ると言う。

We say tha a rate pair (𝑅𝑅₁,𝑅𝑅₂) is achievable when there exist encoders {𝑓𝑓_𝑘𝑘} and a decoder 𝑔𝑔 such that the average error probability 𝑝𝑝_e tends to zero as 𝑛𝑛 → ∞, and that the average power constraint is satisfied.

通信路容量域(Capacity region)

𝐶𝐶 = (𝑅𝑅₁,𝑅𝑅₂) ∶ (𝑅𝑅₁,𝑅𝑅₂) is achievable.

達成可能なレートの組全体(Set of all possible achievable rate pairs)

平均電力制約

Average power constraint

1

𝑛𝑛 𝒄𝒄^𝑘𝑘 𝑚𝑚_𝑘𝑘 ^H𝒄𝒄_𝑘𝑘 𝑚𝑚_𝑘𝑘 ≤ 𝑃𝑃_𝑘𝑘 for all 𝑚𝑚_𝑘𝑘 ∈ ℳ_𝑘𝑘.

２ユーザAWGN通信路に対する通信路符号化定理

Channel coding theorem for 2-user AWGN channel

𝑅𝑅₁ < 𝐼𝐼 𝑋𝑋₁;𝑌𝑌|𝑋𝑋₂ = log 1 + 𝑃𝑃₁ 𝜎𝜎² , 𝑅𝑅₂ < 𝐼𝐼 𝑋𝑋₂;𝑌𝑌|𝑋𝑋₁ = log 1 + 𝑃𝑃₂

𝜎𝜎² , 𝑅𝑅₁ + 𝑅𝑅₂ < 𝐼𝐼 𝑋𝑋₁,𝑋𝑋₂;𝑌𝑌 = log 1 + 𝑃𝑃₁ + 𝑃𝑃₂

𝜎𝜎² .

通信路容量域は以下で与えられる。(The capacity region is given by)

𝑋𝑋₁と𝑋𝑋₂は、互いに独立で、分散がそれぞれ𝑃𝑃₁と𝑃𝑃₂に等しい円対称複素ガウ ス分布に従う。（最良な入力）

𝑋𝑋₁ and 𝑋𝑋₂ follow independent CSCG distributions with variance 𝑃𝑃₁ and 𝑃𝑃₂, respectively. (Best inputs)

通信路容量域(Capacity region)

𝐼𝐼(𝑋𝑋₁;𝑌𝑌) 𝐼𝐼(𝑋𝑋₂;𝑌𝑌)

𝑅𝑅₁ + 𝑅𝑅₂ = 𝐼𝐼(𝑋𝑋₁,𝑋𝑋₂;𝑌𝑌) 𝐼𝐼(𝑋𝑋₂;𝑌𝑌|𝑋𝑋₁)

𝐼𝐼(𝑋𝑋₁;𝑌𝑌|𝑋𝑋₂)

𝑂𝑂 𝑅𝑅₁

𝑅𝑅₂

A

C B

準最適な戦略：３G(Suboptimal strategy: 3G)

点Cにおけるレートの組(Rate pair at the point C)

𝑅𝑅₁, 𝑅𝑅₂ = (𝐼𝐼 𝑋𝑋₁;𝑌𝑌 ,𝐼𝐼 𝑋𝑋₂;𝑌𝑌 )

復号戦略(Decoding strategy)

各ユーザの符号語を復号する際には、もう一方のユーザが送った信号をノイズ とみなす。

In decoding the codeword for each user, the decoder regards the signals sent from the other user as noise.

符号化戦略(Encoding strategy)

各ユーザは、送信信号がガウス分布するような符号化を行う。

Each user performs encoding such that the transmitted signals are Gaussian-distributed.

相互情報量(Mutual information)

𝐼𝐼 𝑋𝑋₁;𝑌𝑌 = log 1 + 𝑃𝑃₁

𝜎𝜎² + 𝑃𝑃₂ , 𝐼𝐼 𝑋𝑋₂;𝑌𝑌 = log 1 + 𝑃𝑃₂

𝜎𝜎² + 𝑃𝑃₁ .

最適な戦略：5G(Optimal strategy: 5G)

点Aにおけるレートの組(Rate pair at the point A)

𝑅𝑅₁, 𝑅𝑅₂ = (𝐼𝐼 𝑋𝑋₁;𝑌𝑌 ,𝐼𝐼 𝑋𝑋₂;𝑌𝑌|𝑋𝑋₁ ) 相互情報量(Mutual information)

𝐼𝐼 𝑋𝑋₁;𝑌𝑌 = log 1 + 𝑃𝑃₁

𝜎𝜎² + 𝑃𝑃₂ , 𝐼𝐼 𝑋𝑋₂;𝑌𝑌|𝑋𝑋₁ = log 1 + 𝑃𝑃₂ 𝜎𝜎² . 符号化戦略(Encoding strategy)

各ユーザは、送信信号がガウス分布するような符号化を行う。

Each user performs encoding such that the transmitted signals are Gaussian-distributed.

逐次干渉除去戦略(Successive interference cancellation (SIC) strategy)

• ユーザ２の信号をノイズとみなして、ユーザ１の符号語を復号する。

Regard the signals of user 2 as noise, and decode the codeword of user 1.

• 復号結果を使ってユーザ１による干渉を除去し、ユーザ２の復号を行う。

Decode the codeword of user 2 after eliminating the interference due to user 1 with the decoding results.

周波数分割戦略：2G/4G(Frequency-division strategy: 2G/4G)

ユーザ１と２にそれぞれ𝛼𝛼 ∈ [0, 1]と1 − 𝛼𝛼の割合で、通信資源を配分する。

Allocate channel resources to users 1 and 2 at ratios 𝛼𝛼 and 1− 𝛼𝛼, respectively.

𝑅𝑅₁ = 𝛼𝛼 log 1 + 𝑃𝑃₁

𝛼𝛼𝜎𝜎² , 𝑅𝑅₂ = 1 − 𝛼𝛼 log 1 + 𝑃𝑃₂

1 − 𝛼𝛼 𝜎𝜎² . 割り当てられた通信資源の利用に、電力を集中できる。

Power can be concentrated on use of the allocated channel resources.

𝛼𝛼 = 𝑃𝑃₁/(𝑃𝑃₁ + 𝑃𝑃₂)とすると、(Letting 𝛼𝛼 = 𝑃𝑃₁/(𝑃𝑃₁+𝑃𝑃₂) yields)

𝑅𝑅₁ + 𝑅𝑅₂ = log 1 + 𝑃𝑃₁ + 𝑃𝑃₂

𝜎𝜎² = 𝐼𝐼 𝑋𝑋₁,𝑋𝑋₂;𝑌𝑌 . 周波数分割戦略は、総和通信路容量を達成できる。

The frequency-division strategy can achieve the sum capacity.