LDPC Decoding: VLSI Architectures

and Implementations
Module 1: LDPC Decoding
Ned Varnica
varnica@gmail.com

Marvell Semiconductor Inc

1
 Overview

§  Error Correction Codes (ECC)

§  Intro to Low-density parity-check (LDPC) Codes

§  ECC Decoders Classification

•  Soft vs Hard Information

§  Message Passing Decoding of LDPC Codes

§  Iterative Code Performance Characteristics

2
Error Correction Codes (ECC)

3
 Error Correcting Codes (ECC)
Parity bits
User message bits (redundancy)

0000 0000000
1000 1101000 channel
0100 0110100
1100 1011100 0010000
0010 1110010
1010 0011010 0000000
0110 1000110 4-bit message space 7-bit codeword space
1110 0101110
0001 1010001
1001 0111001
7-bit word space
0101 1100101
1101 0001101
0011 0100011
1011 1001011
0111 0010111
1111 1111111
4-bit message 7-bit codeword

Rate = 4 / 7

4
 Linear Block Codes

§  Block Codes

•  User data is divided into blocks (units) of length K bits/symbols
u1 u2 u3 u4 u5 ...

•  Each K bit/symbol user block is mapped (encoded) into an N bit/symbol codeword,

where N > K
u1 p1 u2 p2 u3 p3 u4 p4 u5 p5 ...

•  Example:
– in Flash Devices user block length K = 2Kbytes or 4Kbytes is typical
– code rate R = K / N is usually ~0.9 and higher

§  Important Linear Block Codes

– Reed-Solomon Codes (non-binary)
– Bose, Chaudhuri, Hocquenghem (BCH) Codes (binary)
– Low Density Parity Check (LDPC) Codes
Iterative (ITR) Codes
– Turbo-Codes

5
 Generator Matrix and Parity Check Matrix

§  A linear block can be defined by a generator matrix

⎡ g 00 g 01 ... g 0, N −1 ⎤
⎢ g g11 ... g 1, N −1 ⎥⎥ encoding
10
G = ⎢ ⎯→ v = u ⋅ G
⎯⎯ ⎯
⎢ ... ... ... ... ⎥
⎢ ⎥
⎣ g K −1,0 g K −1,1 ... g K −1, N −1 ⎦ Codeword User message

§  Matrix associated to G is parity check matrix H, s.t. G ⋅ HT = 0

•  A vector is a codeword if
v ⋅ HT = 0
§  A non-codeword (codeword + noise) will generate a non-zero vector, which is called
syndrome
vˆ ⋅ H T = s
§  The syndrome can be used in decoding

6
 Example

Encoding
⎡1 1 0 1 0 0 0⎤
⎢0 1 1 0 1 0 0⎥⎥ u = (1 1 0 1)
G = ⎢
⎢1 1 1 0 0 1 0⎥ v = u ⋅ G = (0 0 0 1 1 0 1)
⎢ ⎥
⎣1 0 1 0 0 0 1⎦
v ⋅ HT = 0

Decoding
⎡1 0 0 1 0 1 1⎤
vˆ = (0 0 0 1 1 0 0)
H = ⎢⎢0 1 0 1 1 1 0⎥⎥
vˆ ⋅ H T = (1 0 1)
⎢⎣0 0 1 0 1 1 1⎥⎦

7
Low-Density Parity-Check (LDPC) Codes

David MacKay

8
 LDPC Codes

§  LDPC code is often defined by parity check matrix H

•  The parity check matrix, H, of an LDPC code with practical length has low density (most
entries are 0’s, and only few are 1’s), thus the name Low-Density Parity-Check Code

§  Each bit of an LDPC codeword corresponds to a column of parity check matrix

§  Each rows of H corresponds to a single parity check

•  For example, the first row indicates that for any codeword the sum (modulo 2) of
bits 0,1, and N-1 must be 0

bit 0 bit 1 bit N-1

⎡ 1 1 0 0 ... 0 1 ⎤
⎢ 0 0 0 1 ... 0 0 ⎥
⎢ ⎥
H = ⎢ 0 0 1 0 ... 0 1 ⎥
⎢ ⎥
⎢... ... ... ... ... ... ...⎥
⎣ 1
⎢ 0 0 0 ... 1 0 ⎥
⎦ Parity check equation

9
 ECC Decoder Classification:
Hard vs Soft Decision Decoding

10
 Hard vs. Soft Decoder Classification
§  Hard decoders only take hard decisions (bits) as the input

010101110 010101010
decoder

•  E.g. Standard BCH and RS ECC decoding algorithm (Berlekamp-Massey

algorithm) is a hard decision decoder
§  Hard decoder algorithm could be used if one read is available

EDC BCH
encoder encoder

Hard decisions {1,0}

EDC BCH Front End

decoder decoder / Detection

11
 Hard vs. Soft Decoder Classification
§  Error-and-Erasure decoder is a variant of soft information decoder: in addition
to hard decisions, it takes erasure flag as an input

010101**0 010101010
decoder

§  Error-and-Erasure decoder algorithm could be used if two reads are available

EDC encoder
encoder

decisions {1,0,*}

“error-and-
EDC Front End
erasure”
decoder / Detection
decoder

12
 Hard vs. Soft Decoder Classification

§  Erasure flag is an example of soft information (though very primitive)

§  Erasure flag points to symbol locations that are deemed unreliable by
the channel

§  Normally, for each erroneous symbol, decoder has to determine that
the symbol is in error and find the correct symbol value. However, if
erasure flag identifies error location, then only error value is unknown

§  Therefore, erasure flag effectively reduces number of unknowns that

decoder needs to resolve

13
 Hard vs. Soft Decoder Classification

§  Example. Rate 10/11 Single parity check (SPC) code

•  Each valid 11-bit SPC codeword c=(c0,c1,…c10) has the sum (mod 2) of all the
bits equal to 0

•  Assume that (0,0,0,0,0,0,0,0,0,0,0) is transmitted, and (0,0,0,0,1,0,0,0,0,0,0) is

received by decoder

•  The received vector does not satisfy SPC code constraint, indicating to the
decoder that there are errors present in the codeword

•  Furthermore, assume that channel detector provides bit level reliability metric in
the form of probability (confidence) in the received value being correct

•  Assume that soft information corresponding to the received codeword is given

by (0.9,0.8,0.86,0.7,0.55,1,1,0.8,0.98,0.68,0.99)

•  From the soft information it follows that bit c4 is least reliable and should be
flipped to bring the received codeword in compliance with code constraint

14
Obtaining Hard or Soft Information
from Flash Devices

15
 One Read: Hard Information

§  Obtaining hard information (decision) via one read

§  One VREF threshold is available: Threshold value should be selected so that the
average raw bit-error-rate (BER) is minimized

Decision bin Decision bin

VREF
hd = 1 hd = 0

§  In each bit-location, the hard-decision hd = 0 or hd = 1 is made

§  This information can be used as input into decoder
§  Shaded area denotes the probability that a bit error is made
 Multiple Reads: Soft Information

§  Obtaining soft information via multiple reads

•  Create bins
•  Bins can be optimized in terms of their sizes / distribution of VREF values
given the number of available reads (e.g. 5 reads)
•  These bins can be mapped into probabilities
•  Typically, the closer the bin to the middle point, the lower the confidence
that the bit value (hard-read value) is actually correct

Decision bin Decision bin Decision Decision Decision bin Decision bin
A1 B1 bin C1 bin C0 B0 A0

VREF 5 VREF 3 VREF 1 VREF 2 VREF 4

Pr(bit=1) = 90% Pr(bit=1) = 65% Pr(bit=1) = 55%

Pr(bit=0) = 55% Pr(bit=0) = 65% Pr(bit=0) = 90%

17
 ITR Decoders with Soft Information
0
10
§  Soft ITR decoders
RS code: t=20
significantly outperform
LDPC code"
hard decision
-1 (same parity size) counterparts
10

-2
10

Hard, single
SFR

pass decoder
-3
10
Hard input,
soft ITR decoder
-4
10
Soft input,
Soft ITR decoder

7.6 7.8 8 8.2 8.4 8.6 8.8 9 9.2 9.4 9.6 9.8
SNR [dB]

Raw BER

18
Decoding LDPC Codes

19
 Representation on Bi-Partite (Tanner) Graphs
0" 0" 0" 0" 0" parity check constraints

check nodes

variable nodes
0" 1" 0" 1" 1" 0" encoded bits

Each bit “1” in the parity check matrix is represented by an edge between
corresponding variable node (column) and check node (row)

⎡0 1 0 1 0 0⎤
⎢1 1 0 1 0 0⎥⎥
⎢
H = ⎢0 1 1 0 1 0⎥
⎢ ⎥
⎢1 0 0 0 0 1⎥
⎢⎣0 0 1 1 1 1⎥⎦
20
 Hard Decision Decoding: Bit-Flipping Decoder

§  Decision to flip a bit is made based on the number of unsatisfied checks
connected to the bit

End
First
Second
of step
firststep
step

0"
1" 0"
1" 1"
0" 0"
1" 0"

Valid
codeword

0"
1" 1"
0" 0" 1" 1" 0"

TheThe
second
Examine
left-most
bit from
number
bit Flip
is
the
the
the
left
of
Flip
only
second
unsatisfied
isthe
the
bitleft-most
that
only
bit has
from
bit
check
that
bit
2the
unsatisfied
neighbors
has
left2 unsatisfied
check
for each
neighbors
check
bit neighbors

21
 Bit-Flipping Decoder Progress on a Large
LDPC Code
§  Decoder starts with a relatively large number of errors
§  As decoder progresses, some bits are flipped to their correct values
§  Syndrome weight improves
•  As this happens, it becomes easier to identify the bits that are erroneous and
to flip the remaining error bits to actual (i.e. written / transmitted) values

Number
of bit errors
91

50

21
10
6 4 2 0
Iteration
Syndrome
weight
310

136

60
26 14 10 6 0

1 2 3 4 5 6 7 Iteration

22
 Soft Information Representation

§  The information used in soft LDPC decoder represents bit reliability metric,
LLR (log-likelihood-ratio)
⎛ P(bi = 0) ⎞
LLR(bi ) = log⎜⎜ ⎟⎟
⎝ P(bi = 1) ⎠

§  The choice to represent reliability information in terms of LLR as opposed

to probability metric is driven by HW implementation consideration

§  The following chart shows how to convert LLRs to probabilities (and vice
versa)

23
 Soft Information Representation

§  Bit LLR>0 implies bit=0 is more likely, while LLR<0 implies bit=1 is more likely

0.9

0.8

0.7

0.6
P(bl=1)

P(bi = 0) 0.5
0.4

0.3

0.2

0.1

0
-100 -80 -60 -40 -20 0 20 40 60 80 100
LLR

24
 Soft Message Passing Decoder

§  LDPC decoding is carried out via message passage algorithm on the
graph corresponding to a parity check matrix H
Check nodes
(rows of H)
m=0 m=1 m=2
⎡1 1 0 1 0 0 0⎤
⎢0 0 1 1 1 0 0⎥
⎢ ⎥
⎢⎣0 0 0 1 0 1 1⎥⎦

Bit nodes
(columns of H) n = 0 n=1 n=2 n=3 n=4 n=5 n=6

§  The messages are passed along the edges of the graph
•  First from the bit nodes to check nodes
•  And then from check nodes back to bit nodes

25
 Soft LDPC Decoder
§  There are four types of messages
•  Message from the channel to the n-th bit node Ln
•  Message from n-th bit node to the m-th check node Qn( i−> )
m
•  Message from the m-th check node to the n-th bit node R ( i )
m −> n
•  Overall reliability information for n-th bit-node at the end of iteration Pn( i )
m=0 m=1 m=2
(i) (i)
R0- >3 R 2 - >3

Q 3(i-)>1

P 6(i )

n=0 n=1 n=2 n=3 n=4 n=5 n=6

L3

Channel
ChannelDetector
Detector

26
 Soft LDPC Decoder (cont.)

§  Message passing algorithms are iterative in nature

§  One iteration consists of

•  upward pass (bit node processing/variable node processing): bit nodes
pass the information to the check nodes
•  downward pass (check node processing): check nodes send the
updates back to bit nodes

§  The process then repeats itself for several iterations

27
 Soft LDPC Decoder (cont.)
(i )
§  Bits-to-checks pass: Qn −> m : n-th bit node sums up all the information it has
received at the end of last iteration, except the message that came from m-th
check node, and sends it to m-th check node
•  At the beginning of iterative decoding all R messages are initialized to zero

m=0 m=1 m=2

i -1 i -1
R 0 - >3 R 2 - >3

i i -1
Q 3- >1 = L 3 + ∑ R m '- >3
m '≠1

∑
n=0 n=1 n=2 n=3 n= 4 n=5 n=6

L3

Channel
ChannelDetector
Detector

28
 Soft LDPC Decoder (cont.)
§  Checks-to-bits pass:
•  Check node has to receive the messages from all participating bit nodes
before it can start sending messages back
•  Least reliable of the incoming extrinsic messages determines magnitude of
check-to-bit message. Sign is determined so that modulo 2 sum is satisfied

bits to checks checks to bits

m m

Qn1i - >m = - 10

i Q ni3- >m = 13 R mi - >n1 = -5 Rmi - >n2 = -10 R mi - >n3 = 5

Q n2 - > m
= -5

n1 n2 n3 n1 n2 n3

29
 Soft LDPC Decoder (cont.)

§  At the end of each iteration, the bit node computes overall reliability information
by summing up ALL the incoming messages

Pn(i ) = Ln + ∑ Rm(i−>
)
n
m

§  Pn(i ) ’s are then quantized to obtain hard decision values for each bit
(i )
) ⎧⎪1, if Pn < 0
xn = ⎨
⎪⎩ 0, else

§  Stopping criterion for an LDPC decoder

•  Maximum number of iterations have been processed OR
•  All parity check equations are satisfied

30
 LDPC Decoder Error Correction: Example 1

§  1st iteration: m=0 m=1 m=2

-12 +7 +4
+4 -11
-9 +7 +4 +10

n=0 n=1 n=2 n=3 n=4 n=5 n=6

-9 +7 -12 +4 +7 +10 -11

m=0 m=1 m=2

-4 -10
-7 +4 +4
+4 -4 -7 -4

n=0 n=1 n=2 n=3 n=4 n=5 n=6

31
 LDPC Decoder Error Correction: Example 1

§  APP messages and hard decisions after 1st iteration:

m=0 m=1 m=2

-4 -10
-7 +4 +4
+4 -4 -7 -4

n=0 n=1 n=2 n=3 n=4 n=5 n=6

-9 +7 -12 +4 +7 +10 -11

P: -5 +3 -8 -20 +3 +6 -7

​𝑥┴⌢ ↓ HD: 1 0 1 1 0 0 1

Valid codeword (syndrome = 0)

32
 LDPC Decoder Error Correction: Example 2

§  1st iteration: m=0 m=1 m=2

-12 +7 -4
-4 -11
-9 -7 -4 +10

n=0 n=1 n=2 n=3 n=4 n=5 n=6

-9 -7 -12 -4 +7 +10 -11

m=0 m=1 m=2

+4 -10
+7 -4 -4
+4 +4 -7 +4

n=0 n=1 n=2 n=3 n=4 n=5 n=6

33
 LDPC Decoder Error Correction: Example 2

§  2nd iteration: m=0 m=1 m=2

-12 +7 -4
-21 -11
-9 -7 -7 +10

n=0 n=1 n=2 n=3 n=4 n=5 n=6

-9 -7 -12 -4 +7 +10 -11

m=0 m=1 m=2

+7 -10
+7 -7 -4
+7 +9 -7 +4

n=0 n=1 n=2 n=3 n=4 n=5 n=6

34
 LDPC Decoder Error Correction: Example 2

§  APP messages and hard decisions after 2nd iteration:

m=0 m=1 m=2

+7 -10
+7 -7 -4
+7 +9 -7 +4

n=0 n=1 n=2 n=3 n=4 n=5 n=6

-9 -7 -12 -4 +7 +10 -11

P: -2 +2 -19 -14 +14 +14 -15

HD: 1 0 1 1 0 0 1

Valid codeword (syndrome = 0)

35
 Sum-Product and Min-Sum Decoders

§  Sum-Product: Optimal update rules at the check nodes request implementation
of fairly complex tanh() function and its inverse

§  Instead of these update rules, simple approximate rules have been devised: The
rules require only computing minimum messages at each check node
•  In order to make approximation work, it is necessary/critical to utilize
scaling/offsetting of messages from check to bit nodes
§  This algorithm is widely known as min-sum with scaling/offset and is often
choice of implementation in Hardware
m m

Q ni1- >m = - 10

i Q ni3- >m = 13 R mi - >n1 = -4 R mi - >n2 = -8 R mi - >n3 = 4

Q n2 - > m
= -5

n1 n2 n3 n1 n2 n3
36
 Histogram of LLRs on Large LDPC Codes

§  LDPC min-sum decoder on AWGN channel

§  One critical advantage of soft (min-sum) decoder is that it can utilize the
information on bits provided by several reads
§  Using multiple reads reveals additional information for each individual bit
position (bin allocation / LLR mapping)
§  Soft decoder could start with a fairly large number of LLRs with incorrect signs

Decision bin Decision bin Decision Decision Decision bin Decision bin
A1 B1 bin C1 bin C0 B0 A0

VREF 5 VREF 3 VREF 1 VREF 2 VREF 4

Pr(bit=1) = 90% Pr(bit=1) = 65% Pr(bit=1) = 55%

Pr(bit=0) = 55% Pr(bit=0) = 65% Pr(bit=0) = 90%

37
 Histogram of LLRs on Large LDPC Codes
§  Soft decoder could start with a fairly large number of LLRs with incorrect signs
§  Decoder takes advantage of the original soft information and improves the information
on some bits during the initial iteration
§  As iterations progress, propagation of improved information continues. This reduces
the number of bit positions with incorrect LLR signs (hard-decisions)
§  Eventually, all bit positions receive correct sign of LLRs: at this point the syndrome will
verify that a valid codeword is found and decoder can terminate

900 Number
of bit errors
442

294
224
166
104
53
2 0
Iteration
Syndrome
weight
0
-60 240 874

Iteration counter
420
7
6
5
4
3
2
1
0 322
266
196
116
8 0

1 2 3 4 5 6 7 Iteration
 Performance / Complexity Trade-Offs
§  The choice of number of iterations is typically made
with consideration of the following parameters:
§  Throughput / Latency
§  SNR performance (Capacity gain)
SNR
§  Implementation Complexity performance
Implementation
Complexity
(Capacity gain)
§  Power Consumption

0
10 Throughput Power
& Latency Consumption
System
-1 Performance
10

-2
10
SFR

-3 Fixing throughput/latency &

10
increasing parallelism in
-4
implementation
10

SNR [dB]

Raw BER

39
Code Design, Code Performance Characteristics
and Efficient Hardware

40
 Quasi-Cyclic LDPC Codes

§  Generally, structure of the matrix needs to accommodate easier HW implementation

P
§  Typical approach is to use quasi-cyclic LDPC codes 1
1
1 P
1
1

§  With such matrix structures, row/column processing in decoding can be parallelized,
e.g. process P variable/check nodes in a single clock cycle
§  The same processors could be utilized with scheduling and memory addressing
handling different portions of the parity check matrix in different clock cycles

41
 Layered / Flooding Decoder

§  Updates of messages may be done in a “flooding” fashion or in a layered (serial)

fashion

§  Both of these decoders benefit from structured matrices that naturally allow for
parallel processing of a portion of the matrix, i.e. parallel processing of some
number of rows / columns in the matrix

§  The main difference in layered decoding approach is that the information is
utilized in serial fashion: New messages are utilized during the current iteration,
as opposed to the flooding decoder that obtains new information on all nodes
exactly once in each iteration

§  It has been demonstrated that layered/serial decoder can converge in about ½
of the number of iterations needed by flooding decoder

42
 LDPC Iterative Decoder
Performance Characteristics

43
 RS-ECC Performance Characterization

§  RS ECC performance is completely determined by its correction power t (in

symbols)

§  For example, RS ECC with correction power t = 16 symbols.

•  This code is capable of correcting up to 2t = 32 symbols of erasure. There is

no restriction on the erasure symbol locations within a sector.

•  The code is capable of correcting t = 16 symbol errors regardless of type and

location.

§  Sector failure rate of RS ECC keeps falling at exponential rate with SNR increase
•  No flattening of SFR vs. SNR curve is observed at higher SNR’s

44
 LDPC Decoder Performance Characterization

§  LDPC ITR decoder correction guarantees LDPC system

operating
•  Little to no deterministic performance region
guarantees are provided by the code
•  Error correction is probabilistic LDPC RS/BCH
–  Code is capable of fixing hundreds of
bit errors, but may fail (with small
probability) even if there are only few
bit errors present
waterfall region
SyER/SFR
•  Decoder implementation (e.g. quantization of
messages) is just as important to the final
performance as code design
–  For a fixed ITR code, the differences error floor region
in decoder implementation can have
significant effect on overall
SNR [dB]
performance
Poor decoder implementation
might result in high error floor

45
 LDPC ITR Decoder Error Rate Characteristics

§  Waterfall region

•  BER/SFR drops rapidly with small change in SNR
§  Error Floor (EF) region (High SNR region)
•  BER/SFR drop is much slower
§  Specific structures in the LDPC code graph lead to decoding errors at high SNRs
•  structures known as Near-Codewords (trapping sets) are dominant in the EF region

LDPC RS/BCH

LDPC system
operating region

waterfall region
SyER/SFR

error floor region

SNR [dB]
46
 Near-Codeword (Trapping Set) Example
(7,3) near-codeword (trapping set):
x
x

•  Can we remove loops in the graph: Only to an extent.

•  Typically, it is not possible to design codes w/out short loops at high rates
•  Reduction of the number of loops
•  Reduction of number of trapping-sets (even with the same statistical number of loops)

47
 Mitigating Error Floor of LDPC Code

Retry mode performance of Iterative code; Rate .89; 0.5K sector size;
0
10
Bit-true Simulator §  Code design can be tailored to
On-The-Fly Error Floor achieve the error floor bellow
Error Floor After Retry
-5
HER requirements
10

§  Another strategy to push error

-10
10
floor to desired levels is via
post-processing methodologies
SFR

-15
10

-20
10

17 17.5 18 18.5 19
SNR[dB]

48
 Summary

§  Iterative LDPC codes can enable FLASH industry to hit new capacity milestones

§  Types of Decoders:

•  Hard: Bit-Flipping Decoders
•  Soft: Sum-Product (Min-Sum) Decoders

§  Soft message passing decoders offer large SNR gains – this translates to
capacity gains

§  Optimized ITR codes/decoders are known to deliver performance near the
theoretical limits in the channels dominated by random noise, e.g. AWG noise
§  Handling the error floor phenomenon in ITR decoders
•  Code matrix design
•  Decoder design
•  Post-processing

49
APPENDIX

50
 LDPC Iterative Error Rate Characteristics

§  In “high-SNR” region, dominant errors are near-codewords (trapping sets)

§  As the name suggests, near-codewords look similar to true codewords.
•  More precisely they have low syndrome weight – violating only few of the
parity check equations
•  Recall that a valid codeword has syndrome weight of 0

§  Iterative decoder gets trapped into one of NCW’s, and is unable to come out of
this steady state (or oscillating state)
•  Even if decoder has time to run 100’s of iterations, it would not be able to
come out of the trapping set

51
 Code Selection
SFR profile
as a function of code/decoder selection
0
10
lower error floor
higher error floor
§  Optimizing code/decoder selection
-2
10 based on the performance at low
SNR’s only may lead to impractical
-4 code selection.
10

§  There is a trade-off to be made

SFR

-6
10
between performance at low SNR’s,
-8
defect correction, and error floor
10 (performance at high SNR’s)
-10
10

-12
10
17 17.5 18 18.5 19
SNR

52
Mis-Correction in LDPC Decoding

53
 Minimum Distance of a Code

§  The minimum of all the distance between any two code words is called the
minimum distance of the code, denoted by dmin

dmin

54
 Decoder Miscorrection

§  Miscorrection: For an error correcting code, when the received sequence
falls into the decoding area of an erroneous code word, the decoder may
deliver the wrong code word as the decoding result.

Received sequence
transmitted code word

Erroneous code word

Decoder Error

55
 Iterative Error Rate Characteristics
§  Production grade devices will operate in the Error Floor region (High SNR
region)

•  Dominant Error Events in error floor region are near-codewords

•  Mis-correction is much lower probability event than dominant near-
codewords

BER/SFR LDPC system

operating
region
waterfall region

error floor region

mis-correction

SNR [dB]

56