Parallel Encoding Algorithm for LDPC Codes
Based on Block-Diagonalization
Takayuki Nozaki
Yamaguchi University
This study is supported by a research granted from The Murata Science Foundation

ISIT2015
18th June 2015

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 2015

1 / 15

Abstract
Purpose of Research: Reduce the encoding time for LDPC codes
Main Idea: Parallel encoding based on block-diagonalization of HPH( PH1OO
H2P

H1I
H2I

row perm.
H1Pcolumn perm.
-O

H1IO

H2P

H2I{)
(p1 , p2 , m) = 0⇒H1P p1 = −H1I m
H2P p2 = −H2I m

Contributions of Research
Propose an eﬃcient parallel encoding algorithm for LDPC codes
Evaluate the number of operations of the proposed algorithm
The number of operations of each processor is almost equal
The encoding time becomes 1/K compared with conventional one
Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 2015

2 / 15

Background
Low-Density Parity-Check (LDPC) code
Linear code defined by a sparse parity check matrix H ∈ FM ×N

Encoder
DecoderComplexityO(N + δ 2 )O(N )Parallelization?
(δ = O(N ), δ ≪ N )Possible

Researches of Encoding Algorithm
Generator matrix[Richardson 2001], [Kaji 2006]
This study

Takayuki Nozaki(Yamaguchi Univ.)

Complexity
O(N 2 )
O(N + δ 2 )O(N + δ 2 )Parallel Encoding Algorithm for LDPC Codes

Parallelization
Possible?
Possible

18th June 2015

3 / 15

General Framework of Encoding
Encoding algorithm is divided into precoding step and encoding step
Precoding Step
Input: Parity check matrix H
Output: Systematic form (HP | HI )P HQ = (HP | HI )P , Q are permutation matrices)p=0(HP | HI )m(⇒HP p = −HI m

Encoding Step
Input: Message m
Output: Parity part pSolve linear equation HP p = −HI m
Encoding algorithm is regarded as an algorithm finding P, Q such thatHP p = −HI m is eﬃciently solved
Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 2015

4 / 15

Outline of Proposed Algorithm
Precoding Step of Proposed Algorithm
1(To realize parallel algorithm,) Transform H into singly borderedblock-diagonal (SBBD) matrix [Aykanat 2004]()
A1 O B1SBBD
H ⇒ H2=O A2 B22(To eﬃciently solve the linear equations,)
Rearrange row and column of Ai by conventional algorithm(e.g. Approximate triangularization [Richardson 2001])

Outline of the remaining slides
1 Approximate triangularization [Richardson 2001]
2 Singly bordered block-diagonalization [Aykanat 2004]
3 Propose parallel encoding algorithm
123

Precoding step
Encoding step
Number of operation

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 2015

5 / 15[Richardson 2001] (1: Precoding Step)[Richardson 2001]
Transform HP into approximate triangular matrix (ATM)
Complexity O(N + δ 2 )15001008

111200200400504
15005001008

11200200400400400504504⇒

1008504
15001008()
T C HuIH⇒H=
D E HlI()T C HuI(p1 , p2 , m)T = 0T
D E HlIATM

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 2015

6 / 15

[Richardson 2001] (2: Encoding Step)()
T C HuI(p1 , p2 , m)T = 0T
D E HlI

p2 T = ϕ−1 (DT −1 HuI − HlI )mTI mT
2 T p1 T = −Cp2 T − Hu
where ϕ := E − DT −1 C ∈ Fδ×δ
Number of Operations
1

Number of multiplication (For non-binary case)µ = wt(HlI ) + wt(HuI ) + wt(C) + wt(D) + 2wt(T ) + wt(ϕ−1 )Number of addition
α = S(HlI ) + S(HuI ) + S(C) + S(D) + 2S(T ) + S(ϕ−1 ) + M
where S(A) := wt(A) − (# of non-zero rows)
Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 2015

7 / 15Block-diagonalization (1: Singly bordered BD)
Singly bordered block-diagonalization (SBBD) [Aykanat 2004]
15001008

1

11200200400504
15005001008

11200200400400400504504⇒1008

H ⇒ H2SBBD =504
15001008()
A1 O B1
O A 2 B2

(To simplify the notation, we assume the number of diagonal blocks
K = 2 in this talk)To transform H into SBBD matrix, hypergraph partition is used
1Show a hypergraph representation of H

2Solve the hypergraph partition problem

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 20158 / 15SBBD for H (1: Hypergraph representation of a matrix)
Row-net model [Çatalyürek 1999]
i-th column ⇒ i-th net (or hyperedge) ei
j-th row ⇒ j-th vertex ujExample
e1



1
 0

 0

 1

 0

 1
0

1
000
1
1
0

1
0
0
00
1
0

1
000
1
000
10
1
001010010
10
1
0000
101
000000011000001011000
10001

00 
1 1 0 
0 e5u1e2e7u2e6u4e3e8u3e10u5e9u7u6e4e110e12

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 2015

9 / 15SBBD for H (2: Hypergraph partition)
K-way hypergraph partition Π = {U1 , U2 , . . . , Uk }(1) ∅ ̸= Ui ⊆ U,

(2) Ui ∩ Uj = ∅ (for i ̸= j),(3)∪Ki=1 Ui = UCuts is the nets which connecting to more than one parts
Cutset X (Π) is the set of cuts for the partition ΠExample
e1e5
u1

K=2
U1 = {u1 , u4 , u5 , u6 }U2 = {u2 , u3 , u7 }X (Π) = {e5 , e6 , e10 , e11 , e12 }

e2

e7
u2

e6u4

e3

e8
u3

e10
u5

e9
u7

u6
e4

e11

e12

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 201510 / 15

SBBD for H (3: Hypergraph partition problem andTransformation of matrix)
K-way hypergraph partition problem
minimize : |X (Π)|
s.t. Balance condition maxi |Ui | < |U|(1 + ϵ)/K
There exist some heuristic algorithms (e.g. PaToH [Çatalyürek])
Block-diagonalization of H (K = 2)
(i)

(ii)

(iii)
(1)

H=Takayuki Nozaki(2)(3)(Yamaguchi Univ.)(1) U1(2) U2(3) Vertexes only connected tocutset X (Π)(i) Nets only connecting to U1(ii) Nets only connecting to U2(iii) Cutset X (Π)

Parallel Encoding Algorithm for LDPC Codes

18th June 201511 / 15Proposed Algorithm (1: Precoding step)
1500

1008

1

1

1200200

400400504

504
1500

1008

1500

1008
1200200

4005045001008⇒

ATM1008
1200200

400400504



11SBBD

500

1504
1500

1008

1500

1008

1

1200200

400

400

400504504⇒

504
15001008

I 
T1 C1 O O H1,uI D1 E1 O O H1,lT
TI O O T2 C2 H2,u  (p1,1 , p1,2 , p2,2 , p2,2 , m) = 0IO O D2 E2 H2,l

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 201512 / 15

Proposed Algorithm (2: Encoding Step)I 
T1 C1 O O H1,uI D1 E1 O O H1,lTT
I O O T2 C2 H2,u  (p1,1 , p1,2 , p2,1 , p2,2 , m) = 0
I
O O D2 E2 H2,l⇒(T1D1(T2D2)
I
C1 H1,u(p1,1 , p1,2 , m)T = 0T
I
E1 H1,l)I
C2 H2,u(p2,1 , p2,2 , m)T = 0T
I
E2 H2,lParity parts p1 , p2 are parallelly solved in dual processor system
Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 201513 / 15

Numerical Example (Computational Complexity)
Name [MacKay]

RU Algorithmµ/α (δ)PEGReg504x1008
4599/3542 (21)2283/1739 (16)PEGReg252x504
PEGirReg504x1008
5068/4058 (1)2560/2054 (1)PEGirReg252x504
32000.2240.3.105
102659/98159 (7)16383.2130.3.103
55472/51164 (16)4095.737.3.101
14418/12915 (10)10000.10000.3.631 144200/123378 (337)
8000.4000.3.483
45006/36709 (141)4000.2000.3.243
20240/16075 (74)504.504.3.504
4572/3517 (19)

Proposed Algorithmµ1 /α1 (δ1 )µ2 /α2 (δ2 )2369/1802 (23) 2384/1819 (23)1125/839 (13)1124/843 (13)2587/2079 (2) 2599/2093 (1)1284/1028 (2) 1289/1034 (1)50366/48136 (10) 52180/49871 (10)27453/25298 (15) 28055/25848 (19)7192/6428 (9) 7174/6412 (9)87501/76950 (302) 96271/85278 (325)23913/19638 (117) 25204/20868 (127)10417/8279 (64) 10475/8298 (61)2262/1721 (14) 2273/1729 (16)µi : The number of multiplication of i-th processor
αi : The number of addition of i-th processor
The number of operations of each processor is almost equal
The encoding time becomes 1/K compared with conventional one
Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 201514 / 15

Conclusion

We have proposed a parallel encoding algorithm for LDPC codes
Main Idea : Block-diagonalization of parity part HP

We have evaluated the number of operations of the proposedalgorithm
The number of operations of each processor is almost equal
The encoding time becomes 1/K compared with conventional one

Takayuki Nozaki(Yamaguchi Univ.)

Parallel Encoding Algorithm for LDPC Codes

18th June 201515 / 15