PERANCANGAN DAN IMPLEMENTASI REED-SOLOMON DECODER (255, 239, T=8) LAPORAN TUGAS AKHIR. Oleh YAN SYAFRI HIDAYAT NIM :

PERANCANGAN DAN IMPLEMENTASI

REED-SOLOMON DECODER (255, 239, T=8)

LAPORAN TUGAS AKHIR Karya Tulis ini sebagai salah satu syarat untuk memperoleh gelar sarjana dari Institut Teknologi Bandung

Oleh

YAN SYAFRI HIDAYAT

NIM : 13203094

Program Studi Teknik Elektro

SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA

INSTITUT TEKNOLOGI BANDUNG

2007

PERANCANGAN DAN IMPLEMENTASI

REED-SOLOMON DECODER (255, 239, T=8)

LAPORAN TUGAS AKHIR Karya Tulis ini sebagai salah satu syarat untuk memperoleh gelar sarjana dari Institut Teknologi Bandung

Oleh

YAN SYAFRI HIDAYAT

NIM : 13203094

Program Studi Teknik Elektro

SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA

INSTITUT TEKNOLOGI BANDUNG

2007

ii

ABSTRAK

PERANCANGAN DAN IMPLEMENTASI REED-SOLOMON

DECODER (255, 239, T=8)

Oleh

Yan Syafri Hidayat NIM : 13203094 Pada tugas akhir ini dirancang sebubah Reed-Solomon Decoder (255, 239, t=8) yang akan digunakan sebagai salah satu modul channel decoder dalam chipset WiMax. Reed-Solomon decoder terdiri dari empat processing element utama yaitu Syndrome generator, Euclidean algorithm, Chien search, dan Fast Komo-Joiner algorithm. Proses perancangan dimulai dengan mengidentifikasi spesifikasi, dalam hal ini spesifikasi standard IEEE 802.16. Langkah selanjutnya adalah memilih algoritma decoding yang akan digunakan. Algoritma yang dipilih adalah yang jika diimplementasikan membutuhkan resource—baik time maupun area— paling sedikit. Algoritma tersebut kemudian dibuat bit-precision-model-nya dalam Matlab. Model tersebut kemudian diukur performanya, yaitu Bit-Error-Rate (BER) dengan cara menggenerate random data, kemudian random data tersebut diencode, lalu diberi random error, lalu data tersebut didecode dengan model RSDecoder yang telah dirancang. Jika performa tersebut sudah memenuhi standard yang diinginkan kemudian dirancang arsitektur sistemnya. Arsitektur sistem terdiri dari data-path, control-unit, dan timing-diagram. Control-unit berfungsi sebagai pengatur handshaking dengan modul diluar Reed-Solomon Code, sebagai modul untuk menginisialisasi nilai register dan memory, serta sebagai pengatur process masking tiap komputasi. Deskripsi model dilakukan dalam Matlab code, sedangkan deskripsi RTL dilakukan dalam Verilog HDL. Verifikasi fungsional dilakukan dengan ModelSim. Rancangan diimplementasikan kedalam board FPGA Xilinx Virtex-II Pro XC2VP30TM. Arsitektur sistem telah dirancang,

iv

diverifikasi, serta diimplementasi dengan frekuensi maksimum 196.323MHz, jumlah slices 2007, dan utilisasi 16%. Kata Kunci: WiMax, Reed-Solomon Decoder, Matlab, Verilog HDL, FPGA.

v

ABSTRACT

PERANCANGAN DAN IMPLEMENTASI REED-SOLOMON

DECODER (255, 239, T=8)

By

Yan Syafri Hidayat NIM : 13203094 In this final project, design of Reed-Solomon Decoder (255,239,t=8) is developed as a part of WiMax chipset module. Reed-Solomon Decoder consists of four main processing elements: syndrome generator, Euclidean algorithm, chien search, and fast Komo-Joiner algorithm. Design step begin with identifying specification, in this case is from IEEE 802.16. Next step is choosing the decoding algorithm that will be used. The chosen algorithm is the algorithm that cost less resource—both time and area. The algorithm then modeled into bit-precision model using Matlab. The performance of the model than measured, which is Bit-Error-Rate (BER), by generating random data, than the data is encoded, than given it some error, than the data decoded by RS-Decoder model that has been designed. If the performance meets the expectation from the standard then the architecture will be designed. System architecture consists of data-path, control-unit, and timingdiagram. Control-unit used as handshaking controller with other module outside RS-Decoder, as a module to initiate register and memory value, and as process masking controller for each computation. Model description uses Matlab code, while RTL description uses Verilog HDL. Functional verification uses ModelSim. The design is implemented in FPGA board Xilinx Virtex-II Pro XC2VP30TM. Architecture has been designed, verified, and implemented with maximum frequency 196.323MHz, number of slices 2007, and utilization 16%. Keywords: WiMax, Reed-Solomon Decoder, Matlab, Verilog HDL, FPGA.

vi

KATA PENGANTAR

Alhamdulillah, segala puji syukur penulis panjatkan kepada Allah SWT yang telah

melimpahkan

rahmat

dan

hidayah-Nya,

sehingga

penulis

dapat

menyelesaikan tugas akhir ini dengan baik. Tugas akhir ini adalah bagian terakhir dari rangkaian kegiatan akademik mahasiswa di Departemen Teknik Elektro ITB. Pada kesempatan ini penulis ingin menyampaikan rasa terima kasih yang sebesar besarnya kepada semua pihak yang telah membantu dalam pelaksanaan tugas akhir ini, khususnya kepada: 1. Bapak, Ibu, kakak, dan adikku yang selalu memberikan doa restu serta dukungan semangatnya. 2. Bapak Trio Adiono, S.T., M.T., Ph.D. dan Ibu Ir. Amy Hamidah Salman, M.Sc. selaku pembimbing tugas akhir. Atas bimbingan dan petunjuk peliau tugas akhir ini dapat diselesaikan. 3. Dosen-dosen penguji dalam Sidang Tugas Akhir. Terima kasih atas saran dan kritik yang telah diberikan. 4. Ibu Dr. Ir. Aciek Ida Wurwandari, S.T. selaku dosen wali yang telah membantu dalam berbagai hal akademik, serta dosen-dosen lainnya ayng telah membimbing dalam perkuliahan. 5. Rekan-rekan Versatile Silicon Inc., Mas Nana, Mas Muri, Mas Iyas, Mas Mulyanto, Yanari, Ade, Syafiq, Lakso, Iman, Fajar, Zulkifli, Edes, Feni, Teh Irma, Fatimah, Felis, dan Mbak Astri yang selalu memberikan semangat dan menjadi teman berdiskusi, Annisa di Lab. IC Processing, serta teman-temanku yang tidak dapat disebutkan satu-persatu. 6. Pak Parmis, Pak Ismed, dan Pak Budiman selaku karyawan Lab. IC Design ITB yang selalu siap membantu segala kebutuhan yang diperlukan selama proses Tugas Akhir berlangsung. Serta segenap staf Tata Usaha dan karyawan Departemen Elektro, Lab. Elektronika dan Komponen dan Lab. IC Design Pusat Mikroelektronika ITB. Terima kasih atas bantuan dan pelayanannya. 7. Teman-teman kos, Wahyu, Suryo, Ario, Aul, Muslim, dan Herdhy. vii

Semoga segala kebaikan dan dukungan yang diberikan kepada penulis, mendapat balasan dan pahala dari Allah SWT. Penulis menyadari bahwa laporan ini masih banyak terdapat kekurangan. Untuk itu, penulis mengharapkan saran dan kritik guna perbaikan penulisan dimasa yang akan datang. Semoga laporan ini dapat bermanfaat.

Bandung, 28 September 2007

Yan Syafri Hidayat [email protected]

viii

DAFTAR ISI

DAFTAR ISI .......................................................................................................... ix

DAFTAR GAMBAR ............................................................................................ xii

DAFTAR SINGKATAN DAN LAMBANG ...................................................... xiv

Bab I Pendahuluan ................................................................................................. 1

I.1. Latar Belakang ............................................................................................. 1

I.2. Batasan Masalah .......................................................................................... 2

I.3. Tujuan .......................................................................................................... 3

I.4. Metodologi ................................................................................................... 3

I.5. Sistematika Penulisan .................................................................................. 5

Bab II Teori Encoding-Decoding Reed-Solomon Code ......................................... 6

I.1. Aritmatika Galois Field................................................................................ 6

I.1.1. Finite Field GF(p) ....................................................................................... 7

I.1.2. Extension Field GF(pm) ............................................................................... 7

I.1.3. Representasi Galois Field............................................................................ 7

I.1.4. Polinomial Galois Field .............................................................................. 8

I.1.5. Primitive Polinomial ................................................................................... 9

I.1.6. Aritmatika pada Galois Field ...................................................................... 9

I.1.8. Operasi Perkalian dan Pembagian............................................................. 10

I.2. Encoding Reed-Solomon Code .................................................................. 11

I.2.1. Code Generator Polinomial g(x) ............................................................... 11

I.2.2. Code Generator Polinomial pada GF (255, 239) ...................................... 12

I.2.3. Systematic Encoding Reed-Solomon Code .............................................. 12

I.2.4. Encoding pada RS(255, 239) .................................................................... 14

I.2.5. RS-Shortened Code ................................................................................... 15

I.3. Decoding Reed-Solomon Code .................................................................. 16

I.3.1. Menghitung Syndrome.............................................................................. 17

I.3.1.1. Metode Horner Untuk Menghitung Syndrome ....................................... 18

I.3.1.2. Matriks Persamaan Syndrome ................................................................. 18

ix

I.3.2. Menghitung Polinomial Error Locator ...................................................... 19

I.3.2.1.Metode Euclidean Algorithm ................................................................... 21

I.3.2.2.Modified Euclidean Algorithm ................................................................ 21

I.3.2.3.Metode Improved Euclidean Algorithm .................................................. 22

I.3.3. Mencari Posisi Error ................................................................................. 23

I.3.3.1.Metode Chien Search ............................................................................... 23

I.3.4. Menghitung Error Value ........................................................................... 24

I.3.4.1.Metode Fast Komo-Joiner Algorithm Untuk Mencari Error value .......... 25

Bab III Desain Arsitektur Sistem Reed-Solomon Decoder (255, 239, t=8) ......... 28

III.1. Spesifikasi Sistem .................................................................................... 28

III.2. Modeling Algoritma ................................................................................ 29

III.2.1.Model Matlab Reed-Solomon Code ......................................................... 29

III.2.2.Performa BER Model pada proses encoding-decoding ............................ 31

III.2.3.Performa Model pada sistem WiMax ....................................................... 32

III.3.Desain Reed-Solomon Encoder RS(255, 239) ......................................... 33

III.3.1.Arsitektur Sistem ...................................................................................... 34

III.3.2.Desain Control Unit .................................................................................. 35

III.4.Desain Reed-Solomon Decoder RS(255, 239) ......................................... 35

III.4.1.Full Parallel Galois Field (216) Multiplier ................................................ 36

III.4.1.1. Arsitektur Sistem ................................................................................ 38

III.4.2.Syndrome Generator ................................................................................. 39


III.4.3.Blok Improved Euclidean (IE) ................................................................. 41


III.4.3.2. Desain Control Unit ............................................................................ 44

III.4.4.Blok Chien Search .................................................................................... 46


III.4.5.Blok Fast Komo-Joiner Algorithm (FKJA) .............................................. 49


III.4.5.2. Data-path Algoritma 1 ........................................................................ 50


x






III.4.5.9. Desain Control Unit ............................................................................ 56

III.4.6. Integrasi Blok ....................................................................................... 60

III.4.6.1. Handshaking ....................................................................................... 60

III.4.6.2. Desain Main Control Unit .................................................................. 61

III.4.6.3. Aliran Proses Decoding ...................................................................... 62

III.5. Implementasi RTL Code ........................................................................... 64

Bab IV Verifikasi dan Implementsai .................................................................... 65

IV.1. Metode Verifikasi .................................................................................... 65

IV.1.1.Test-vector Generation ............................................................................. 65

IV.1.2.Auto-Compare Verilog HDL.................................................................... 65

IV.2. Verifikasi Fungsional Sub-Sistem........................................................... 66

IV.2.1.Syndrome Generator................................................................................. 66

IV.2.2.Euclidean Algorithm ................................................................................ 67

IV.2.3.Chien Search............................................................................................. 68

IV.2.4.Fast Komo-Joiner Algorithm.................................................................... 68

IV.3. Implementasi ........................................................................................... 69

Bab V Kesimpulan dan Saran............................................................................... 70

V.1. Kesimpulan ............................................................................................... 70

V.2. Saran ......................................................................................................... 70

DAFTAR PUSTAKA ........................................................................................... 72

LAMPIRAN .......................................................................................................... 73

xi

DAFTAR GAMBAR

Gambar 1 Arsitektur Physical Layer Komunikasi Digital .................................................. 2

Gambar 2 Flow-chart metodologi perancangan.................................................................. 4

Gambar 3 Komuniksi data digital ....................................................................................... 6

Gambar 4 Proses Decoding Reed-Solomon Code ............................................................ 16

Gambar 5 Flow-chart Improved Euclidean....................................................................... 23

Gambar 6 Matlab Code hierarchy..................................................................................... 30

Gambar 7 Simulasi performa model matlab ..................................................................... 31

Gambar 8 Hasil pengukuran performa bit error rate (BER) ............................................. 32

Gambar 9 Diagram blok pengukuran performa BER model WiMax dengan FEC Reed-

Solomon Code (255, 239, t=8).......................................................................................... 32

Gambar 10 Grafik perbandingan performa BER model RS-Decoder Maltab Library

dengan model RS-Decoder hasil desain............................................................................ 33

Gambar 11 Struktur Reed-Solomon Encoder ................................................................... 34

Gambar 12 Arsitektur LFSR Reed-Solomon Encoder...................................................... 34

Gambar 13 RS Encoder (255, 239, t=8)............................................................................ 35

Gambar 14 Arsitektur Sistem (data-path dan control unit) Reed-Solomon Decoder........ 36

Gambar 15 Data-path Full Parallel Galois Multipplier GF(256) ...................................... 38

Gambar 16 Timing diagram Full Parallel Galois Field Multiplier GF(256)..................... 39

Gambar 17 Satu Cell Syndrome Generator....................................................................... 40

Gambar 18 Struktur Blok Syndrome Generator................................................................ 41

Gambar 19 Timing diagram Blok Syndrome Generator................................................... 41

Gambar 20 Flow-Chart Algoritma Improved Euclidean .................................................. 42

Gambar 21 data-path dan control unit R dan U Improved Euclidean............................... 43

Gambar 22 FSM untuk contol unit blok Impoved Euclidean ........................................... 44

xii

Gambar 23 Satu Cell Chien Search................................................................................... 47

Gambar 24 Struktur Blok Chien Search ........................................................................... 48

Gambar 25 Timing diagram Chien Search ....................................................................... 49

Gambar 26 Arsitektur Sistem (data-path dan contol unit) Blok FKJA ............................. 50

Gambar 27 Data-path algoritma 1..................................................................................... 51







Gambar 34 Struktur data-path dan multiplexer Processing Element FJKA...................... 55

Gambar 35 Skema pengontrolan FKJA ............................................................................ 56

Gambar 36 FSM Control Unit Fast-Komo Algorithm...................................................... 57

Gambar 37 Proses handshaking ........................................................................................ 60

Gambar 38 Main control unit............................................................................................ 61

Gambar 39 Aliran proses decoding................................................................................... 62

Gambar 40 waveform sydnrome generator....................................................................... 66

Gambar 41 Waveform Euclidean...................................................................................... 67

Gambar 42 Waveform chien search.................................................................................. 68

Gambar 43Waveform FKJA ............................................................................................. 69

xiii

DAFTAR SINGKATAN DAN LAMBANG SINGKATAN

Kepanjangan

BER

Bit Error Rate

OFDM

Orthogonal Frequency Division Multiplexing

HDL

Hardware Description Language

FEC

Forward Error Correcting

IE

Improved Euclidean

FJKA

Fast Komo-Joiner Algorithm

MCU

Main Control Unit

IEEE

Institut of Electronic and Electrical Engineering

LAMBANG

Arti

α

Elemen bilangan Galois field

f(x)

Primitive polynomial

g(x)

Code generator polynomial

n

Panjang codeword

k

Panjang message

M(x)

Polinomial message

T(x)

Polinomial data yang dikirim (transmitted)

E(x)

Polinomial error

R(x)

Polinomial data yang diterima (received)

xiv

PERANCANGAN DAN IMPLEMENTASI REED-SOLOMON DECODER (255, 239, T=8) LAPORAN TUGAS AKHIR. Oleh YAN SYAFRI HIDAYAT NIM :

Recommend Documents