Leakage Tutorial

Farid N. Najm

Description

A Bit-Serial Approximate Min-Sum LDPC Decoder and FPGA Implementation Ahmad Darabiha, Anthony Chan Carusone, Frank R . Ksc hischangUniversity of Toronto, Toronto, CanadaISCAS, Kos, GreeceMay 2006 IS CAS 2006Outline• Introduction to LDPC co des/decoders• Proposed techniques• B it-se rial message passing• Approximate Min-S um decoding• FPGA implementation• Conclusion2IS CAS 2006Introduction• Low -Density Parity-C heck (LDPC) codes• A sub-class of Error Control Codes (ECC)• Perform better than Turbo and Reed-Solomon codes• Approach Shannon limit • LDPC codes are adopted for • IEEE 802.3 10Gbit Ethernet standard-3• Input B ER > 10-13• Output B ER < 10 • Code rate 0.84 • DVB -S2 Digital Video B roadcast standard3IS CAS 2006LDPC Codes: StructureM=5 checkD = 4 nodesCN=1 0D = 2V variablenodes1 0 0 10 10 0 100 11 0 10 0 10 00 0 0 10 110 10H = MxN1 10 0 0 0 10 0 10 0 1 0 10 0 10 1• Each bit participates in D parity checksv• Each check consists of D bitsc• Good LDPC codes are long (large N) and with a random-like graph4IS CAS 2006Min-Sum LDPC Decoding • A form of iterative message passing decodingchecks• Messages in Log-Likelihood Ratio (LLR) Log(P(x=0) / P (x=1))•CV m• Each iteration does two updates: 1V V2 m-1• Check node updatec = chk(v , .., v )m 1 m-1variable = (sgn(v) .. sgn(v )) Min(|v |, …, |v |)1 m-1 1 m-1checksC• Variable node update n-1C2C1 Vnv = var(c , c ,..,c ) n 1 2 n-1 = ...

Informations

• Publié par: Hamef
• Nombre de lectures: 15
• Langue: English

Extrait

A Bit-Serial Approximate Min-Sum LDPC Decoder

and FPGA Implementation

Ahmad Darabiha, Anthony Chan Carusone, Frank R. Kschischang

University of Toronto, Toronto, Canada ISCAS, Kos, Greece May 2006

                                         

SIC

2

AS 2060

•

•

•

•

Outline

Introduction to LDPC codes/decoders

Proposed techniques

• Bit-serial  message passing

• Approximate  Min-Sum decoding

FPGA implementation

Conclusion

ISC

3

AS 2

•

006

Introduction

Low-Density Parity-Check (LDPC) codes • A  sub-class of Error Control Codes (ECC)

•

•

•

Perform better than Turbo and Reed-Solom

Perform better than Turbo and Reed-Solomon codes

Approach Shannon limit

Approach Shannon limit

LDPC codes are adopted for • IEEE  802.3 10Gbit Ethernet standard • Input  BER > 10 -3 -13 • Output BER < 10 • Code  rate 0.84 • DVB-S2  Digital Video Broadcast standard

SIC

4

AS 2060

= D C  4

D V  = 2

LDPC Codes: Structure

H MxN =  

• Each bit participates in D v parity checks

• Each check consists of D c bits

M = 5 c h e c k n o d e s

N = 1 0 v a ria b l e n o d e s

1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1

• Good LDPC codes are long (large N) and with a random-like graph

SIC 5 AS 2060

Min-Sum LDPC Decoding

• A  form of iterative message passing decoding

• Messages  in Log-Likelihood Ratio (LLR) •    Log(P(x= 0 ) / P ( x=1 ))

• Each iteration does two updates: •   Check node update    c m = chk ( v 1 , .., v m-1 )  = ( sgn ( v 1 ) .. sgn ( v m-1 ))   Min ( |v 1 |, …, |v m-1 | )

•   Variable node update v n = var ( c 1 , c 2 ,..,c n-1 )     = c 1 + c 2 + .. + c n-1

checks

V 1 V C m 2 V m-1

variable

checks

C 1 C 2 C n-1 V n

Variables

ISC

6

AS 2006

LDPC Decoders: Architecture

• We use fully-parallel architecture • Allows high throughput • Graph is directly mapped to hardware

• Major challenge: • Complex interconnection • Wire capacitance - Power dissipation Wire delay - • Routing congestion - Larger area

We propose a bit-serial scheme to reduce • interconnections  

ISC

7

AS 2

•

 

006

C l k

L i n e # 1 L i n e # 2

Bit-Serial Message-Passing

b 1 b 2

L i n e # n b n B it- p a r a lle l

C l k

S e r i a l l i n e

b 1 b 2

n c y c l e s

b n

B it- s e r ia l

bit-serial scheme • transfers an   n -bit message in n clock cycles over a single wire • is Ideal for Min-Sum decoding • reduces the number of wires => reduced routing congestion • both Min and Sum functions are naturally bit-serial • facilitates  efficient gear shift decoding

ISCAS 2006

8

Min-Sum Approximation

ISC 9 AS 2006

Approximation to Min-Sum Decoding

• In  original Min-Sum each check node needs to find first and second minimum

• We  approximate Min-Sum:

• Variable node the same as conventional Min-Sum • Check node update: c m = check ( v 1 , .., v m )  = ( sgn ( v 1 ) .. sgn ( v m-1 ))   Min ( |v 1 |, …, |v m | )

c h e c k s

V 1 2 V m - 1 V m C m V

v a r ia b le

• In  Approximate Min-Sum only the first minimum needs to be found • reduces the check node logic by about 50%

SIAC

10

S2 060

Approximate Min-Sum: Performance (Full-Precision)

1.E-01

1.E-02

1.E-03

1.E-04

1.E-05

1.E-06 3.5

4

4.5

Original MS, LDPC-2048 Original MS, LDPC-992 Approx. MS, LDPC-2048 Approx. MS, LDPC-992

6

6.5

5 5.5 EbNo(dB) Under full-precision computations, conventional Min-Sum and approximate Min-Sum perform closely

ISCAS2 006

Approximate Min-Sum: Performance (Quantized)

11

1.E-01

1.E-02

1.E-03

1.E-04

1.E-05

1.E-06

1.E-07 3.5

4

4.5

Original MS, 4bit Approx. MS, 4bit

5

5.5

6

EbNo (dB) With quantized calculations, there is more than 0.5dB difference in performance between conventional and approximate Min-Sum