¿¸µLDPCÉä¹æ¤È¤½¤Î±þÍÑ

. . . .

多元

LDPC

符号とその応用

笠井 健太

東京工業大学

あらまし

• 効率的に復号可能な符号の現状 • 多元LDPC符号の設計法，復号法，解析法 • 多元LDPC符号の応用 レートコンパチブル符号，噴水符号，量子誤り訂正 目的：多元LDPC符号を2元LDPC符号の単なる拡張とは思わなくなり， 応用を見て使いたくなる．

. . . .

通信路容量に接近するまたは達成する効率的に

復号可能な符号

• Irregular LDPC Codes 未証明 通信路に応じて次数分布(λ(x ), ρ(x ))の最適化が必要 • Polar Codes 構成的 通信路に応じて凍結ビットの選択が必要

• Spatially Coupled Regular LDPC Codes

有限長の性能限界

[‘08 Polyanskiy and Poor]

log M∗(n, PB) = nC ()− √ nV ()Q−1(PB) + O(log n) M∗(n, PB) は， ブロック誤り率PBを達成可能な符号長nの符号の最大符号語数 は通進路を規定するパラメータ V ()はBSC()ならV = (1− ) + log2(1−_ ) BEC()ならV = (1− )

. . . .

有限長の性能限界（続き）

0.30 0.35 0.40 0.45 0.50 102 103 104 105 106 107 108 Coding Rate R *

Block Length n [bit] BEC C=0.5 BSC C=0.5

Figure: 通信路容量 C = 1/2 の通信路で，ブロック誤り率 10−3を達成する最適な

有限長の性能限界（続き）

符号化率を固定したときの,符号長nの符号の最適な誤り率 PB= Q (√ n(C ()− R∗) √ V () ) (1 + o(1)) R∗ := 1 nlog M ∗_{(n, P} B)

. . . .

有限長の性能限界（続き）

0.50 0.55 0.60 0.65 0.70 102 103 104 105 106 107 108 Channel Capacity C( ε )=1-ε

Block Length n [bit] Finite Polar Code

Infinite (2,4)-NBLDPCC GF(28)

Finite (2,4)-NBLDPCC GF(28)

Infinite (3,6)-BLDPCC Finite (3,6)-BLDPCC Finite Optimal Code

Figure: BEC() において，符号化率 1/2 の符号が，ブロック誤り率 10−3を達成 するために耐えられる通信路容量 C () の最小値

多元

LDPC

符号

• シンボル mビットを１シンボルとしてあつかう． • 符号の定義 C = { x∈ GF(2m)N | Hx = 0 } H : GF(2m)上の疎なM× N 行列 • パリティ検査方程式 ∑ v∈∂c hvcxv= 0∈ GF(2m)

. . . .

2

元

vs

多元

LDPC

符号の設計法発展の歴史

2元 • Gallager[‘62]発明 • Tanner[‘83]一般化LDPC符号 • MacKay[‘95]再発見 • Luby[‘98]非正則化

• Richardson & Urbanke[‘99] Density Evolution

• Richardson & Urbanke[‘02] Multi-edge

• Di[‘02] Stopping Set

• Tian[‘03] ACE algorithm

• Thorpe[‘03] Protograph

多元

• Gallager[‘62]発明

• Davey[‘96] m∼ 8に対して，ランダムなGF(2m)上の (2,dc)-正則多元LDPC符号が経験的に最良

GF(2

m

)

上の

(2,d

c

)-

正則多元

LDPC

符号

• 短い符号長から，復号性能が良いことが経験的に知られている． • mに対してスレショルドは単調ではない．m∼ 8が最適． • とても疎なパリティ検査行列 • 最小距離がlog(N)で抑えられてしまう． • m≥ 8だと観測できないくらいエラーフロアが低い • レート1/3より低いレートの符号を作れない

. . . .

多元

LDPC

符号の数少ない最適化法

• 各構成単一パリティ検査符号 { (xv)v∈∂c | ∑ v∈∂c hvcxv= 0∈ GF(2m) } のバイナリハミング重みが最大になるように， 係数_{{hv} ∈ GF(2}m_{) (v ∈ ∂c)を定める} • グラフ上の小さな部分サイクルによって定義されるタナーグラフが 符号語を持たないように係数を定める． これらの設計法は，GF(26)までの多元LDPC符号に対しては有意な効果 が見られる. 最良のGF(28_{)ではランダムに係数を選んでもほとんど性能} は変わらない．

復号法

メッセージパッシングアルゴリズム: サイズ2mの確率ベクトルをメッセージとする µ(`) v→c∈ R 2m :列メッセージ µ(`) c→v∈ R 2m :行メッセージ メッセージ更新: 初期化: µ(0)_v→c(x ) = Pr(x|y) for x ∈ GF (2m) 行処理: µ(`+1)<sub>c→v</sub> (x ) = ∑ x :xv=x I [ ∑ v0∈∂c hv0cxv0 = 0 ] ∏ v0∈∂c\{v} µ(`)_v0_→c(xv0) 列処理: µ(`+1)<sub>v→c</sub> (x ) = ∏ c0∈∂v\{c} µ(`+1)_c→v (x ) 判定: ˆµ(`+1)<sub>v</sub> (x ) = ∏ c0∈∂v µ(`+1)_c→v (x )

. . . .

復号法

Sum-Productアルゴリズム • 行処理の畳み込みをFFTによって高速に計算可能 • 実数の乗算を避けるおよび量子化レベルを下げるために 対数領域で復号を行うと，FFTが使えなくなる • 2元LDPC符号に比べて約2_mm 倍のメモリが必要 • 復号器はbit-LLRではなくsymbol-LLRを渡されるので通信路容量の ロスがなく，ターボ等価の必要がない 低計算量の復号アルゴリズム • 列重みが２なので，低計算量のビットフリップアルゴリズムの 効果を引き出せない．復号性能の損失が大きい

• 有意な確率だけを保存するEMSアルゴリズム[Declercq et al.]が

今のところ唯一の成功例

• メッセージを一貫してフーリエ領域で計算することにより，

性能解析

• 密度発展, GA, EXIT [Bennatan et al.]

• BECの密度発展は(m + 1)パラメータで書ける[Rathi et al.]

• EXIT関数 [Rathi et al.]

• スケーリング[Andrianova et al.]

• 重み分布，ML復号性能

• エラーフロア[Nozaki et al.]

最適化のための性能解析は無駄に終わることが多い．

. . . .

応用研究１：レートコンパチブル低符号化率符号

• ゴール：

低い符号化率から高い符号化率まで

対応したレートコンパチブルLDPC符号

• 戦略：

. . . .

低い符号化率の

LDPC

符号設計の難しさ

• Capacity-approaching irregular LDPC code is available n→ ∞.

• Designing short and moderate low-rate LDPC codes is difficult.

“One encounters a difficulty when designing very low rate LDPC codes

in the standard irregular framework, it is relatively difficult to achieve high thresholds.”

from Multi-Edge type LDPC codes, 2003.

• Structured low-rate LDPC codes have good thresholds. However they tends to have nodes of high degree.

• The optimized structured low-rate LDPC codes need to be used with large code length to exploit the potential decoding performance.

低い符号化率の

LDPC

符号の復号の難しさ

• Low-rate LDPC codes tend to have many check nodes. In fact, LDPC codes with K information nodes and rate R have M = N(1− R) = K(1− R)

R check nodes.

Example: M = 9K for R = 0.1 while M = K /9 for R = 0.9.

• Check nodes require complex computations.

We solve these issues of designing and decoding

low-rate LDPC codes by a very simple scheme.

. . . .

低い符号化率の多元

LDPC

符号

We use (2, 3)-regular non-binary LDPC over GF(28) as a mother code.

Denote the codeword by (x1, . . . , xN)∈ GF(28)N, R = 1/3. Conventional rate-lowering scheme:

• Klinc et al. use shortening for reducing the rate. (x1, 0, x3, 0, . . . , xN), R < 1/3.

• Repetition reduces the rate.

(x1, . . . , xN, x1, . . . , xN), R = 1/6.

Repetition is the worst thing to do for coding, because repetition just uses more N channels without improving Eb/No vs BER curve.

乗法繰り返し多元

LDPC

符号

• Instead of repetition, we propose “Multiplicative Repetition.” (x1, . . . , xN,h1x1, . . . ,hNxN), R = 1/6,

whereh1, . . . ,hN are randomly chosen from GF(28)\{0}.

• Multiplicative repetition twice gives

(x1, x2, . . . , xN, h1x1, . . . ,hNxN, h10x1, . . . ,h0NxN), R = 1/9.

• Multiplicative repetition three times gives

(x1, x2, . . . , xN, h1x1, . . . ,hNxN, h10x1, . . . ,h0NxN, h100x1, . . . ,hN00xN),

. . . .

数値結果

(K =1024 bits, BIAWGNC)

10-8 10-7 10-6 10-5 10-4 10-3 10-2 10-1 100 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5 3.0

Block Error Rate

Eb/No[dB] Punctured C₁ R=1/2 C₁ R=1/3 C₂ R=1/6 MET R=1/2 MET R=1/6 ARA R=1/6

数値結果

(K =192 bits, BIAWGNC)

10-8 10-7 10-6 10-5 10-4 10-3 10-2 10-1 100 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5

Block Error Rate

Punctured C₁ R=1/2

C₁ R=1/3

C₂ R=1/6

. . . .

復号アルゴリズム

Tanner graph of the mother code.

A (2,3)-regular non-binary LDPC code over GF(2

8

).

符号化率に依存しない復号アルゴリズム

R = 1/6.

. . . .

符号化率に依存しない復号アルゴリズム

R = 1/9.

. . . .

乗法繰り返し

vs

短縮

over BEC

0.000

0.050

0.100

0.150

0.200

0.250

0.300

0.350

0.400

0.450

0.0

0.1

0.2

0.3

0.4

0.5

Norm. gap to capacity (1-e

*

-R)/R

PROPOSED, T=1,...,10

Shortened code

. . . .

応用研究２：噴水符号

ブロック符号と噴水符号

•

Conventional Block Codes

Transmitter encodes k bits into n(> k/C ) bits. n is

fixed.

•

Fountain Codes

Transmitter encodes k bits into infinitely limitless

coded bits.

Receiver collects arbitrary n(> k/C ) channel outputs

to recover k information bits. n is not fixed.

. . . .

従来最良の噴水符号：

Raptor

符号

符号化法

1.

Encode k information bits s

1

, . . . , s

k

into n coded bits x

1

, . . . , x

n

with a high-rate LDPC

code.

2.

Repeat the followings infinitely.

2.1

Choose d

∈ {1, 2, . . . } with probability Ω

d

.

2.2

Choose d coded bits x

i1

, . . . , x

id

uniformly at random from x

1

, . . . , x

n

.

2.3

Transmit x

i1

+

· · · + x

id

.

Ω

d

をうまく設計することで消失通信路に対して

Raptor

符号の欠点

1.

The output distribution Ω

d

needs to be optimized for

each k.

2.

The output distribution Ω

d

tends to have a large

maximum max

{d | Ω

d

6= 0}, which leads to large

decoding complexity.

3.

The optimized Raptor codes need to be used with large

information length k to exploit the potential decoding

performance.

4.

Over the channels with small capacity C ,

. . . .

提案：乗法繰り返し多元

LDPC

符号を使った噴水符号

1.

Map k information bits s

1

, . . . , s

k

into K = k/m

non-binary symbols s

1

, . . . , s

K

∈ {0, 1}

m

.

2.

Encode the K non-binary symbols s

1

, . . . , s

K

into N

coded non-binary symbols x

1

, . . . , x

N

with a 2

m

-ary

(2,3)-regular non-binary LDPC code

C

1

.

3.

Repeat the followings infinitely for i = 1, . . . ,

∞.

3.1

Choose a non-singular binary m

× m matrix F

i

,

v

i

∈ {1, . . . , N} and w

i

∈ {1, . . . , m} uniformly at

random.

符号化

/

復号グラフ

An example of a Tanner graph used for encoding/decoding.

White dots represent the transmitted bits correcponding to

collected channel outputs.

. . . .

密度発展によるオーバヘッドの評価

C = 1

オーバヘッド

ε := Cn/k

− 1.

m dc= 3 dc= 4 dc= 5 dc= 6 dc= 7 1 1.0799 1.1972 1.3104 1.4140 1.5082 2 0.5747 0.6637 0.7492 0.8275 0.8987 7 0.0888 0.1180 0.1495 0.1803 0.2091 8 0.0809 0.1013 0.1262 0.1517 0.1763 9 0.0792 0.0913 0.1104 0.1313 0.1522 10 0.0813 0.0858 0.0996 0.1166 0.1343 11 0.0856 0.0831 0.0921 0.1057 0.1207 12 0.0913 0.0822 0.0871 0.0976 0.1102 13 0.0976 0.0826 0.0837 0.0915 0.1019 16 0.1179 0.0877 0.0795 0.0806 0.0859 17 0.1245 0.0901 0.0792 0.0786 0.0825 18 0.1309 0.0925 0.0793 0.0770 0.0797

提案噴水符号の利点

•

No optimization is needed.

•

The decoding complexity does not depend on

the channel capacity.

•

Exhibits good decoding performance at short

information length.

. . . .

Results over AWGN with k = 1024 bits and

m = 8.

10-7 10-6 10-5 10-4 10-3 10-2 10-1 100 0.0 0.1 0.2 0.3 0.4 0.5

Block Error Rate

ε PROPOSED C=1.0 PROPOSED C=0.5 PROPOSED C=0.1 RAPTOR C=1.0 RAPTOR C=0.5

提案噴水符号の悪い点

•

Not capacity-achieving even for channels with

C = 1, while Raptor codes achieve the capacity.

. . . .

オーバヘッドの頻度分布

C = 1

0.00 0.05 0.10 0.15 0.20 0.25

OVERHEAD ε

Histograms of the overheads at which the proposed fountain code over

{0, 1}8 _{successfully recovers k = 192, 2}9_{, 2}10_{, 2}11_{, 2}13_{, 2}14 _{and 2}15

. . . .

CSS(Calberbank, Shor, Steane) codes

CSS codes are quantum error correcting codes.

A CSS code is defined by classical binary linear code pair (C , D) satisfying the followings.

• C ⊃ D⊥ (or equivalently⇔ C⊥⊂ D)

• Both C , D are good classical error correcting codes decodable from the syndromes. And hopefully, efficiently decodable.

The first condition is equivalent to HCH_DT= 0, where HC and HD are the parity-check matrices of C and D, respectively.

Non-binary Low-Density Parity-Check(LDPC) codes

• Non-binary LDPC codes are linear codes over GF(2m) defined by a sparse parity-check matrix over GF(2m).

• A non-binary LDPC code C defined by a parity-check matrix H

C :={x ∈ GF(2m)N|Hx = 0}

H∈ GF(2m)M×N is a sparse matrix.

• We focus on uniform column and row weight J and L.

• J = 2 is empirically known to be best performing.

. . . .

Companion Matrices

Companion Matrices[MacWilliams and Sloane]

The following map A is isomorphism from GF(2m_{) from GF(2)}m×m_{, where} GF(2m) is defined by primitive polynomial xm+∑m_{i =0}−1aixi = 0. Let α be the primitive element s.t. αm+∑m−1_{i =0} aiαi = 0.

αi 7→ A(αi) := A(α)i ∈ GF(2)m×m A(α) :=        0 0 0 0 a0 1 0 0 0 a1 0 1 0 0 a2 .. . ... . .. ... 0 0 0 1 am−1       

What’s more, we have

A(αi)v (αj) = v (αi +j)

v (αi) = (a0, . . . , am−1)T ∈ GF(2)m

Example of Companion Matrices

Ex. The primitive polynomial is given as x3+ x + 1 for GF(8). The companion matrix for each element in GF(8) is given as follows.

A(0) =  00 00 00 0 0 0   A(α0_{) =}  10 01 00 0 0 1   A(α) =  01 00 11 0 1 0   A(α2_{) =}  00 11 01 1 0 1   A(α3_{) =}  11 01 11 0 1 1   A(α4_{) =}  01 11 10 1 1 1   A(α5_{) =}  11 10 10 1 1 0   A(α6_{) =}  10 10 01 1 0 0  

. . . .

How to make binary orthogonal matrices from GF(2

m

)

ones

Lemma

For two M× N matrices HΓ and H∆ over GF(2m)

and two mM× mN matrices HC and HD over GF(2).

HΓ=    γ0,0 · · · γ0,N−1 . . . . .. ... γM−1,0 · · · γM−1,N−1    , H∆=    δ0,0 · · · δ0,N−1 . . . . .. ... δM−1,0 · · · δM−1,N−1    , HC =    A(γ0,0) · · · A(γ0,N−1) . . . . .. ... A(γM−1,0) · · · A(γM−1,N−1)    , HD=    A(δ0,0)T · · · A(δ0,N−1)T . . . . .. ... A(δM−1,0)T _{· · · A(δ} M−1,N−1)T    ,

In this setting, if HΓH_∆T = 0, then HCH_DT = 0. proof: (HCHDT)i ,j = ∑N−1 k=0 A(γi ,k)A(δk,j) = ∑N−1 k=0 A(γi ,kδj ,k) = A(∑N_k=0−1γi ,kδj ,k) = A((HΓH_∆T)i ,j) = A(0) = 0

How to construct NB-CSS-LDPC codes

Goal:Construct two sparse matrices HΓ, H∆ over GF(2m) such that HΓH_∆T = 0.

1. By Hagiwara-Imai method, construct binary sparse matrices ˆHC, ˆHD of culumn weight J such that ˆHCHˆ_DT = 0

2. Solve an equation HΓH∆T= 0, where HΓ and H∆are GF(2m)-matrix

variables which have non-zero entries at the same location as ˆHC, ˆHD, respectively.

3. The equation HΓH∆T = 0 is a system of quadratic equations over Galois

fields, hence in general, known to be NP-Complete. Fortunatelly this is reduced to linear equations when J = 2 under some assumption.

. . . .

Quasi-Cyclic Low-Density Parity-Check Codes

A(J, L, P) QC-LDPC code is a binary linear code defined by the following

parity-check matrix ˆHC. ˆ HC =      I (c0,0) I (c0,1) · · · I (c0,L−1) I (c1,0) I (c1,1) · · · I (c1,L−1) .. . . .. ... I (cJ−1,0) I (cJ−1,1) · · · I (cJ−1,L−1)      I (1) =        0 1 0 0 0 0 0 1 0 0 0 0 0 . .. 0 0 0 0 0 1 1 0 0 0 0       ∈ {0, 1} P×P I (cj ,`) = I (1)cj ,`

Hagiwara-Imai method

Output binary QC matrices ˆHC and ˆHD such that ˆHCHˆDT = 0.

ˆ HC =      I (c0,0) I (c0,1) · · · I (c0,L−1) I (c1,0) I (c1,1) · · · I (c1,L−1) .. . . .. ... I (cJ−1,0) I (cJ−1,1) · · · I (cJ−1,L−1)      ˆ HD =      I (d0,0) I (d0,1) · · · I (d0,L−1) I (d1,0) I (d1,1) · · · I (d1,L−1) .. . . .. ... I (dJ−1,0) I (dJ−1,1) · · · I (dJ−1,L−1)     

Hagiwara and Imai ’07

If #{0 ≤ ` ≤ P − 1 | cj ,`− dk,`= p mod P} is even

. . . .

Conjecture on Hagiwara-Imai method

For J = 2, let HC, HD be parity-check matrices of (J, L, P) QC-LDPC codes

C and D constructed by Hagiwara-Imai method. Let n0, . . . , nL−1 be the

indices of non-zero entries in the m-th row of HD.

In this setting, we conjecture that in the Tanner graph of HC, the L variable nodes corresponding to the n0, . . . , nL−1-th columns and the L adjacent check nodes form a cycle of length 2L.

To be precise in other words,

HC のnj 列目(j = 0, . . . , L− 1)の要素が１である行のインデックスを

mj ,0, mj ,1とするとある[0, L− 1]上の順列σが存在して

How to solve H

∆

H

_ΓT

= 0

The m-th row of H∆ is orthogonal with HΓ, i.e.,

     γmσ(0),0,n0 γmσ(0),1,n1 . .. . .. γmσ(L−2),0,nL−2 γmσ(L−2),1,nL−2 γm_σ(L−1),1,n0 γmσ(L−1),0,nL−1            δm,n0 .. . .. . δm,n_L−1      = 0 Then, δm,nj 6= 0 (j = 0, . . . , L − 1) exist if L∏−1 j =0 γmσ(j ),0,njγ −1 mσ(j ),1,nj = 1.

For αx ∈ GF(2m), define log(αx) := x

the equation above is reduced to the following integer equations. L−1 ∑ j =0 log(γmσ(j ),0,nj)− L−1 ∑ j =0 log(γmσ(j ),1,nj) = 0.

. . . .

Depolarizing

通信路での復号性能

10-5 10-4 10-3 10-2 10-1 100 0.00 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

Block Error Rate

R_Q=5/7, n=14,224, q=28 R_Q=5/7, n=35,406, q=29 R_Q=1/2, n= 8,768, q=28 R_Q=1/2, n=10,728, q=29 R_Q=1/2, n=20,560, q=210 RQ=1/3, n= 4,656, q=28 RQ=1/3, n=10,746, q=29 R_Q=1/3, n=11,940, q=210

Depolarizing

通信路での復号性能

0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 1.00 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 Quantum Rate R Q Shannon limit S2 BDD limit Bicycle, n=3,786 Caley, n=4,096 Turbo, n=4,000 Proposed, n=14,224, q=28 Proposed, n=35,406, q=29 Proposed, n= 8,768, q=28 Proposed, n=10,728, q=29 Proposed, n=15,760, q=210 Proposed, n= 4,656, q=28 Proposed, n=10,746, q=29 Proposed, n=11,940, q=210

. . . .

まとめ

• 設計法，復号法，解析法を眺めて 2元LDPC符号とずいぶん違うことを見た • レートコンパチブル符号，噴水符号，量子誤り訂正への応用を眺め， 多元LDPC符号ならではの使い方があることを見た