Bab III Desain Arsitektur Sistem Reed-Solomon Decoder (255, 239, t=8)
Pada Bab ini akan dipaparkan proses perancangan dimulai dari identifikasi spesifikasi, pembuatan bit-precission model, perancangan arsitektur, sampai implementasi RTL-nya.
III.1.
Spesifikasi Sistem
Spesifikasi sistem Reed-Solomon Decoder berdasarkan pada standard IEEE 802.16 untuk komunikasi wireless. Input blok Reed-Solomon Code adalah 255 codeword, dengan lebar word 8 bit. Data yang masuk adalah parity check-word pada LSB. Output dari system adalah 239 codewoord hasil decoding. Berikut adalah tabel I/O dan deskripsinya: Tabel 2 Spesifikasi I/O Reed-Solomon Decoder (255, 239, t=8)
No Unit
Port
Width
Length
Keterangan
1
Input
8 bit
255
Codeword yang masuk
encoded_word
adalah
LSB
terlebih
dahulu. Dan posisi paritycheck codeword adalah pada MSB. 2
mode
Input
3 bit
-
000: rate (255, 239) 001: RESERVED 010: RESERVED 011: RESERVED
28
100: RESERVED 101: RESERVED 110: RESERVED 3
start_signal
Input
1 bit
-
111: RESERVED Sinyal untuk menandakan bahwa
data
pertama
sudah masuk dan RS Decoder siap dijalankan. 4
input_valid
Input
1 bit
-
Sinyal
input
untuk
menandakan bahwa data yang
masuk
saat
itu
adalah valid 5
decoded_word
Output 8 bit
239
Codeword hasil decoding.
6
output_valid
Output 1 bit
-
Sinyal untuk menandakan bahwa data pertama hasil decoding sudah keluar
III.2.
Modeling Algoritma
Seperti yang telah dijalaskan pada Bab 1, metodologi perancangan dimulai dengan membuat model bit-precission-nya dengan Matlab yang sudah terverifikasi dan terukur performanya.
III.2.1.
Model Matlab Reed-Solomon Code
Arsitektur sistem Reed-Solomon Code (255, 239, t=8) ini dibangun berdasarkan model bit-precission matlab yang sudah didesain dan diverifikasi. Flow desain Matlab yang sudah dibuat adalah sebagai berikut:
29
Gambar 6 Matlab Code hierarchy
Dari masing-masing tahap, dibuat dump filenya untuk menyimpan hasil-hasil perhitungan dalam format biner ke dalam suatu file (dalam hal ini dipakai ekstensi .ref). File-file tersebut yang nantinya dipakai sebagai test vector verifikasi desain. Number of error dipakai oleh modul errorgen.m untuk menggenerate sejumlah random error. Error yang dipakai untuk verifikasi adalah dari 0 – 9 error. % adding error err_value = zeros(1,255); if (err_num == 0) received = c_received; else for e = 1 : err_num 30
err_pos = randint(1,1,255); if (err_pos == 0) err_pos = 1; else err_pos = err_pos; end err_value(err_pos) = randint(1,1,255); disp(['error value gen ' num2str(err_value(err_pos))]) disp(['error loc gen ' num2str(err_pos)]) end received = bitxor(c_received, err_value); end
III.2.2.
Performa BER Model pada proses encoding-decoding
Model matlab kemudian diverifikasi dan dihitung performansinya. Performa yang diukur adalah Bit Error Rate (BER). Yaitu jumlah data error setelah didecode per jumlah data yang dikirimkan. Cara menghitung performa BER terlihat pada gambar berikut ini: % BER computation disp('log: BER computation') BER(index) = biterr (message, decoded) / length(decoded); disp(['log: BER : ' num2str(BER(index))])
Gambar 7 Simulasi performa model matlab
Berikut ini adalah performa Bit Error Rate (BER) untuk RS decoder yang berdiri sendiri. Data diambil pada 10 kali percobaan untuk error 1 sampai 12 buah. Dari grafik tersebut diketahui bahwa model RS Decoder tersebut sudah benar karena mampu mengoreksi 8 bit error secara sempurna. 31
Gambar 8 Hasil pengukuran performa bit error rate (BER)
III.2.3.
Performa Model pada sistem WiMax
Gambar 9 Diagram blok pengukuran performa BER model WiMax dengan FEC ReedSolomon Code (255, 239, t=8)
Performa RS Code dilihat dalam suatu sistem terintegrasi, dalam hal ini WiMax. Model RS Code dibuat dalam matlab lalu diintegrasikan dengan model matlab WiMax. Model WiMax tersebut kemudian dihitung bit-error-ratenya. Diagram di atas menunjukkan simulasi performa BER pada Matlab. Grafik di bawah adalah BER system WiMax dengan model RS decoder matlab library dan model RS Decoder hasil desain.
32
Gambar 10 Grafik perbandingan performa BER model RS-Decoder Maltab Library dengan model RS-Decoder hasil desain
Dari grafik tersebut diketahui bahwa model RS decoder tersebut masih reasonable untuk diterapkan pada system WiMax. Tidak ada perbedaan yang signifikan antara performa BER WiMax RS Decoder Matlab Library dengan BER WiMax RS Decoder hasil desain sendiri.
III.3.
Desain Reed-Solomon Encoder RS(255, 239)
Input RS Encoder (255, 239, t=8) adalah 239 8-bit message word. Outputnya adalah 255 8-bit words, dimana 239 word LSB adalah message word, dan 16 word MSB adalah parity word. Parity word didapat dari perhitungan modulo dari message word terhadap primitive polynomial yang digunakan untuk mendapatkan remainder dengan persamaan berikut ini.
33
III.3.1.
Arsitektur Sistem
Gambar 11 Struktur Reed-Solomon Encoder
Berikut ini block diagram RS Encoder. Block terdiri dari core yaitu generator parity yang terdiri dari LFSR(Linear Feedback Shift Register), dan controller yang mengatur data output dan menonaktifkan LFSR. Pada saat 239 word data masuk, controller memilih datain sebagai output, ketika selesai, controller menonaktifkan LFSR dan memilih output dari register secara serial mulai dari register 16 sampai register 1.
Gambar 12 Arsitektur LFSR Reed-Solomon Encoder
LFSR terdiri dari register yang berjumlah 16 buah, masing-masing register merepresentasikan koefisien polynomial. Tiap input register, dikalikan dengan konstanta generator polynomial RS(255, 239, t=8). Kemudian dengan skema Feed-Back degenerate remainder dari input terhadap generator polynomial tersebut.
34
III.3.2.
Desain Control Unit
start_encoder
Contol Unit
enable/disable
datain
MUX_select
LFSR MUX
dataout
CORE
Gambar 13 RS Encoder (255, 239, t=8)
Control unit untuk RS Encoder ini terdiri dari sebuah counter. Counter akan mengatur MUX output, saat 239 cycle pertama, output didapat dari bypass data input, setelah selesai 239 cycle, CU mengeluarkan sinyal disable untuk mendisable LFSR. Lalu nilai dari register LFSR tersebut dikeluarkan secara serial mulai dari register 16 sampai register 1 melalui MUX output. CU akan mulai bekerja ketika ada sinyal start_encode. RS Ecnoder (255, 239, t=8) ini memakai struktur pipeline dengan latency nol.
III.4.
Desain Reed-Solomon Decoder RS(255, 239)
Arsitektur sistem Reed-Solomon Decoder terdiri dari 5 block utama, yaitu syndrome generator block, improved euclidean block, chien search block, fast komo-joiner block, dan error correcting block. Data code word disimpan dalam input RAM selama proses decoding masih berlangsung. Komunikasi tiap block dilakukan dengan memberikan sinyal start dan stop yang dikendalikan oleh main control unit. Berikut blok diagram sistemnya. Beberapa improvisasi algoritma dilakukan untuk mendapatkan struktur hardware yang lebih simpel dan latensi yang lebih kecil. 35
Gambar 14 Arsitektur Sistem (data-path dan control unit) Reed-Solomon Decoder
III.4.1.
Full Parallel Galois Field (216) Multiplier
Yang dimaksud dengan full parallel disini tidak ada strukstur feed-backnya, seperti yang biasa dilakukan pada serial Galois Field Multiplier. Multiplier GF(216) atau GF(256) adalah perkalian terbatas pada 256 elemen bilangan.
Untuk
primitive
polynomial 1 + x 2 + x 3 + x 4 + x 8 ,
didapatkan
x 8 = x 4 + x 3 + x 2 + 1 secara definisi. Sehingga untuk perkalian dua elemen bilangan
GF(256),
a( x) = a8 x8 + a7 x7 + ... + a2 x 2 + a1x1 + a0 , dan b( x) = b8 x8 + b7 x 7 + ... + b2 x 2 + b1 x1 + b0 , didapatkan, c( x) = c '16 x16 + c '15 x15 + ... + c '2 x 2 + c '1 x1 + c '0 , dimana
36
c '16 = a8b8 c '15 = a8b7 + a7b8 c '14 = a8b6 + a7b7 + a6b8 c '13 = a8b5 + a7b6 + a6b7 + a5b8 c '12 = a8b4 + a7b5 + a6b6 + a5b7 + a4b8 c '11 = a8b3 + a7b4 + a6b5 + a5b6 + a4b7 + a3b8 c '10 = a8b2 + a7b3 + a6b4 + a5b5 + a4b6 + a3b7 + a2b8 c '9 = a8b1 + a7b2 + a6b3 + a5b4 + a4b5 + a3b6 + a2b7 + a1b8 c '8 = a8b0 + a7b1 + a6b2 + a5b3 + a4b4 + a3b5 + a2b6 + a1b7 + a0b8 c '7 = a7b0 + a6b1 + a5b2 + a4b3 + a3b4 + a2b5 + a1b6 + a0b7 c '6 = a6b0 + a5b1 + a4b2 + a3b3 + a2b4 + a1b5 + a0b6 c '5 = a5b0 + a4b1 + a3b2 + a2b3 + a1b4 + a0b5 c '4 = a4b0 + a3b1 + a2b2 + a1b3 + a0b4 c '3 = a3b0 + a2b1 + a1b2 + a0b3 c '2 = a2b0 + a1b1 + a0b2 c '1 = a1b0 + a1b1 c '0 = a0b0 Untuk polynomial pangkat lebih dari delapan, dilakukan reduksi Galois Field (256) yaitu:
x8 = x 4 + x3 + x 2 + 1 x 9 = x( x 4 + x3 + x 2 + 1) = x 5 + x 4 + x 3 + x x10 = x 2 ( x 4 + x3 + x 2 + 1) = x 6 + x5 + x 4 + x 2 x11 = x3 ( x 4 + x3 + x 2 + 1) = x 7 + x 6 + x 5 + x3 x12 = x 4 ( x 4 + x3 + x 2 + 1) = x8 + x 7 + x 6 + x 4 = x 7 + x 6 + x3 + x 2 + 1 x13 = x5 ( x 4 + x3 + x 2 + 1) = x 9 + x8 + x 7 + x5 = x 7 + x 2 + x + 1 x14 = x 6 ( x 4 + x3 + x 2 + 1) = x10 + x 9 + x8 + x 6 = x 4 x15 = x 7 ( x 4 + x3 + x 2 + 1) = x11 + x10 + x9 + x 7 = x5 + x 2 + x x16 = x8 ( x 4 + x3 + x 2 + 1) = x12 + x11 + x10 + x8 = x 6 + x 3 + x 2 Substitusi persamaan di atas kedalam c(x) didapatkan:
c( x) = c 7 x7 + c6 x 6 + ... + c2 x 2 + c1 x1 + c0 , dimana 37
c7 = c '13 + c '12 + c '11 + c '7 c6 = c '12 + c '11 + c '10 + c '6 c5 = c '11 + c '10 + c '9 + c '5 c4 = c '14 + c '10 + c '9 + c '8 + c '4 c3 = c '12 + c '11 + c '9 + c '8 + c '3 c2 = c '13 + c '12 + c '10 + c '8 + c '2 c1 = c '14 + c '13 + c '9 + c '1 c0 = c '14 + c '13 + c '12 + c '8 + c '0 III.4.1.1.
Arsitektur Sistem
Dari persamaan terakhir dapat dibuat struktur Galois Field (256) full parallel dengan sebuah register pipeline sebagai berikut:
Gambar 15 Data-path Full Parallel Galois Multipplier GF(256)
Antara konstanta c’ dan c diberi pipeline register untuk memperkecil delay dan mensinkronkan timing fungsi logikannya. Ketika diberi sinyal disable pada register pipeline, maka output multiplier akan nol. Berikut timing diagramnya:
38
Gambar 16 Timing diagram Full Parallel Galois Field Multiplier GF(256)
III.4.2.
Syndrome Generator
Persamaan syndrome adalah Si = Rn-1(αi)n-1 + Rn-2(αi)n-2 + … + R1(αi) + R0. Untuk RS(255, 239, t=8), maka S1 = R255α255 + R254α254 + ... + R0. S1 = R255α255 + R254α254 + ... + R0. … S1 = R255α255 + R254α254 + ... + R0. Syndrome generator didesain berdasarkan metode Horner, dimana hanya digunakan sebuah multiplier dan adder yang digunakan secara simultan atau iteratif. Sehingga persamaan syndrome menjadi Si = ( …(Rn-1αi + Rn-2)αi + … + R1)αi + R0. III.4.2.1.
Arsitektur Sistem
Untuk sebuah cell sydrome terdisri dari Rnαi+1 + Rn. Perhitungan ini akan diulang secara rekursif sampai seluruh 239 message word masuk. Data pertama yang masuk adalah r255 atau MSB dari received word.
39
Gambar 17 Satu Cell Syndrome Generator
Nilai register adalah setelah beberapa clock terlihat pada table berikut. Dari tebel tersebut dapat diketahui bahwa output system adalah: S1 = R255α255 + R254α254 + ... + R0. S1 = R255α255 + R254α254 + ... + R0. … S1 = R255α255 + R254α254 + ... + R0.
Tabel 3 Isi register syndrome cell
Clock
Rn
αi+1, i = 0
Nilai register
0
R255
α
-
1
R254
α
R255α
2
R253
α
R254α + R255α2
3
R252
α
R253α + R254α2 + R255α3
4
R251
α
R252α + R253α2 + R254α3 + R255α4
...
…
...
…
Dengan cara rekursif tersebut, hanya dibutuhkan satu multiplier dan adder untuk setiap cell syndrome. Pada gambar 17 terlihat struktur 16 cell syndrome yang 40
disusun serial. Untuk keperluan block selanjutnya, hasil perhitungan syndrome dioutput-kan secara serial.
Gambar 18 Struktur Blok Syndrome Generator
Timing diagram syndrome generator terlihat pada gambar di bawah ini. Syndrome akan aktif ketika ada signal start syndrome datang dan 1 cycle setelahnya data pertama yaitu R255 masuk. Syndrome generator akan berhenti setelah 255 data masuk dan mengeluarkan signal head-out. Data syndrome akan dibaca block selanjutnya 1 cycle setelah head_out.
Gambar 19 Timing diagram Blok Syndrome Generator
III.4.3.
Blok Improved Euclidean (IE)
Algoritma Euclidean adalah solusi yang paling banyak dipakai orang untuk menyelesaikan key equation. Secara umum, ada dua pendekatan desain implementasi algoritma Euclidean, struktur pipeline yang high-speed, atau arsitektur array sistolik dengan area yang kecil. Desain-desain tersebut didasarkan 41
pada algoritma Euclidean murni sehingga memakan waktu dan juga memerlukan data swap. Karena itu, kompleksitas desain hardwarenya menjadi tinggi dan latency yang panjang [2]. Algoritma Euclidean yang baru diperkenalkan disini [2]. Dengan meng-improve algoritma tersebut, kompleksitas hardware dan latensi menjadi semakin kecil. Hardware tersebut hanya memerlukan 2 Galois Filed multiplier dan sebuah Galois Field Adder. Desain yang dahulu lebih banyak menggunakan shift register diubah menjadi RAM addressing yang lebih simpel. Dalam implementasinya, yang digunakan hanyalah variable R dan Q, Flow-chart improved Euclidean (IE) diberikan pada gambar berikut:
Gambar 20 Flow-Chart Algoritma Improved Euclidean
42
Jika deg(Ri(x)) < deg(Qi(x)), R(x) tidak berubah dan Q(x) akan dihitung untuk mengurangi degree-nya. Sebaliknya jika deg(Ri(x)) < deg(Qi(x)), Q(x) tidak berubah dan R(x) akan dihitung untuk mengurangi degree-nya. Improvisasi yang dilakukan adalah membuat simpel proses swapnya. III.4.3.1.
Arsitektur Sistem
Arsitektur sistemnya terlihat pada gambar di bawah ini. Koefisien Ri(x) dan Qi(x), disimpan dalam dua block memory RAM_R dan RAM_Q. Masing-masing RAM terisi oleh 2t+1 register, dimana t = 8. Koefisien yang disimpan dalam RAM tersebut dapat diakses dengan RAM addressing saat proses iterative. Degree dari R(x) dan Q(x) disimpan dalam register degree.
Gambar 21 data-path dan control unit R dan U Improved Euclidean
Blok komputasi terdiri dari dua multiplier yang mengalikan R(x) dengan koefisien b, dan mengalikan Q(x) dengan koefisien a, dan satu buah modulo-2 adder. 43
III.4.3.2.
Desain Control Unit
Blok control unit akan membandingkan degree Ri(x) dengan degree Qi(x) lalu menentukan algoritma mana yang dijalankan. Jika komputasi R yang dijalankan, maka RAM Q tidak ditulis, sebaliknya jika komputasi Q yang dijalankan, maka RAM R tidak ditulis. Berikut ini adalah state machine untuk control unitnya:
Gambar 22 FSM untuk contol unit blok Impoved Euclidean
Algoritma Euclidean dimulai ketika ada sinyal start_euclidean. State akan berubah dari kondisi IDLE ke kondisi RAM_access_control, dimana pada state ini, nilai 44
syndrome dari blok syndrome generator akan disimpan dalam RAM Q. State kemudian berubah INIT_ALG seteleh seluruh nilai syndrome, yaitu S1 s/d S16 sudah masuk ke RAM, dengan urutan address. Tabel 4 State control unit IE
NO STATE
KETERANGAN
1
State setelah diberi sinyal restart, state akan berubah ke
IDLE
RAM_ACC jika ada sinyal start_euclid. 2
RAM_ACC
State dimana blok IE mengambil data input syndrome ke RAM Q. Algoritma akan dimulai (pindah ke state INIT_ALG) jika semua data syndrome sudah masuk.
3
INIT_ALG
State untuk melakukan inisialisasi algoritma, semua counter dan register yang berhubungan di reset.
4
CALC_L
State untuk mengecheck nilai V_COEF .
5
REQ_B
State untuk meminta data RAM Q, saat state ini address RAM Q di-assign.
6
CHECK_B
State untuk mengecheck nilai data RAM yang direquest saat stete REQ_B, proses checking akan berulang lewat REQ_B sampai ketemu nilai yang tidak nol.
7
DEC_DQ
State ini akan diambil jika diketahui data RAM Q yang direquest bernilai nol, maka algoritma akan mengurangi degree Q.
8
INIT_R
State ini akan diambil jika diketahui data RAM Q yang di-request tidak nol, maka dilakukan inisialisasi untuk menghitung polynomial R
9
CALC_R
State ini akan diabil satu cycle setelah INIT_R. Pada state ini, nilai RAM R dihitung untuk di feedback-kan kembali ke RAM R.
10
CHECK_DEGR State ini diambil setelah proses perhitungan polynomial R selesai, algoritma akan mengecheck nilai degree R, jika degree sudah sama dengan 8 maka algoritma 45
berhenti 11
REQ_A
State untuk meminta data RAM R, saat state ini address RAM R di-assign.
12
CHECK_A
State untuk mengecheck nilai data RAM yang direquest saat state REQ_A, proses checking akan berulang lewat REQ_A sampai ketemu nilai yang tidak nol.
13
DEC_DR
State ini diambil jika diketahui data RAM R yang direquest bernilai nol, maka algoritma akan mengurangi degree R
14
INIT_Q
State ini akan diambil jika diketahui data RAM R yang di-request tidak nol, maka dilakukan inisialisasi untuk menghitung polynomial Q.
15
CALC_Q
State ini akan diabil satu cycle setelah INIT_Q. Pada state ini, nilai RAM Q dihitung untuk di feedback-kan kembali ke RAM Q.
16
CHECK_DEGQ State ini diambil setelah proses perhitungan polynomial Q selesai, algoritma akan mengecheck nilai degree Q, jika degree sudah sama dengan 8 maka algoritma berhenti.
17
RAM_REQ
State ini adalah state ketika algoritma sudah selesai, dan nilai RAM diminta oleh blok sesudahnya.
Output dari improved Euclidean ini adalah error locator polynomial σ(x) = xt + σtt-1 1x
+ … + σ1x + σ0. Nilai ini tersimpan dalam RAM R [1:8], dan akan diambil
oleh block chien search dengan memasukkannya ke S/P register. III.4.4.
Blok Chien Search
Jika ada error locator polynomial degree n pada GF(2m) didefinisikan sebagai σ(x) = xt + σt-1xt-1 + … + σ1x + σ0, dimana koefisien σi anggota dari GF(2m) untuk 0 ≤ i ≤ t – 1. Maka, akar dari polynomial tersebut dapat dicari dengan algorthma chien search berikut ini: 46
For I = 1 to 255 If (σ(αi) == 0) then Error occurs, location at αi End if End for III.4.4.1.
Sama
Arsitektur Sistem
seperti
desain
syndrome
generator,
polynomial
σ(x)
dapat
diimplementasikan menggunakan struktur feed-back. Input Chien cell adalah konstanta pda polynomial σ(x), yaitu σ0, …, σ8. Berikut ini adalah satu cell chien search. Cx D
Ci
αi
Gambar 23 Satu Cell Chien Search
Nilai dari register setelah beberapa clock dapat dilihat pada tabel di bawah ini: Tabel 5 Isi register chien search cell
Clock
0
Cx
σ8
α i, i = 8
Nilai register
α
8
-
8
σ8 α8
1
σ8
α
2
σ8
α8
σ8 α16
3
σ8
α8
σ8 α24
4
σ8
α8
σ8 α32
...
…
...
… 47
Chen cell tersebut kemudian disusun menjadi Blok Chien dengan struktur berikut: σ3
σ5
C3
σ1
C5
σ7 C7
C1
σ0
σ(αi) D
C2
σ2
C4
σ4
C6
σ6
C8
σ8
Gambar 24 Struktur Blok Chien Search
Sehingga output chien search seteleh beberapa clock dilihatkan dalam tabel di bawah ini. Tabel 6 Isi register output blok chien search
Clk Nilai register
0
-
1
σ8α8 + σ7α7 + σ6α6 + σ5α5 + σ4α4 + σ3α3 + σ2α2 + σ1α + σ0
2
σ8α16 + σ7α14 + σ6α12 + σ5α10 + σ4α8 + σ3α6 + σ2α4 + σ1α2 + σ0
3
σ8α24 + σ7α21 + σ6α18 + σ5α15 + σ4α12 + σ3α9 + σ2α6 + σ1α3 + σ0
4
σ8α32 + σ7α28 + σ6α24 + σ5α20 + σ4α16 + σ3α12 + σ2α8 + σ1α4 + σ0
...
…
Dari tabel tersebut diketahui bahwa output system chien search adalah: Λ (1) = σ 8 + σ 7 + σ 6 + σ 5 + σ 4 + σ 3 + σ 2 + σ 1 + σ 0 Λ (α ) = σ 8α 8 + σ 7α 7 + σ 6α 6 + σ 5α 5 + σ 4α 4 + σ 3α 3 + σ 2α 2 + σ 1α 1 + σ 0 Λ (α 2 ) = σ 8α 16 + σ 7α 14 + σ 6α 12 + σ 5α 10 + σ 4α 8 + σ 3α 6 + σ 2α 4 + σ 1α 2 + σ 0
...
48
Yang berarti sudah sesuai dengan hasil yang diinginkan dari algoritma chien search. Algoritma search berlanjut sampai 255 posisi. Tiap posisi dicheck. Berikut ini adalah timing diagram sistemnya.
Gambar 25 Timing diagram Chien Search
III.4.5.
Blok Fast Komo-Joiner Algorithm (FKJA)
Blok Fast Komo-Joiner Algorithm menggunakan tujuh buah algoritma. Ketujuh buah algoritma ini akan didesain data-pathnya secara terpisah. III.4.5.1.
Arsitektur Sistem
Sistem arsitektur Fast Komo-Joiner Algorithm terdiri dari sel-sel algoritma, yang ditandai dengan ALG1, ALG2, ALG3, …, ALG7, dan sebuah control unit. Dengan arsitektur ini, komputasi error value hanya membutuhkan 4 buah multiplier Galois Field (256) dan 7 buah Galois Field (256).
49
Gambar 26 Arsitektur Sistem (data-path dan contol unit) Blok FKJA
Berikut penjelasan arsitektur tiap algoritmanya. III.4.5.2.
Data-path Algoritma 1
Rumus untuk algoritma 1 adalah:
Sv − j = Sv − j − βi Sv − j −1 , j = 0,..., v − i − 1; i = 1,..., v − 2 Dari rumus tersebut diketahui bahwa dibutuhkan sebuah GF substractor (yang berarti sama dengan adder), dan sebuah GF multiplier. Multiplier digunakan untuk mengalikan syndrome dengan beta dimana address untuk syndrome yaitu v-j-1 dan address untuk beta v-j degenerate oleh control unit. Berikut gambar data-pathnya:
50
Gambar 27 Data-path algoritma 1
III.4.5.3.
Data-path Algoritma 2
Rumus untuk algoritma 2 adalah:
Sv =
( Sv − β v −1Sv −1 ) , j = 1,..., i; i = 1,..., v − 2 ( β v − β v −1 )
Diperlukan dua buah GF substractor/adder untuk Sv − βv−1Sv−1 dan βv − βv−1 , sebuah inverse GF LUT untuk
(...) , dan sebuah multipler untuk ( β v − β v −1 )
mengalikan hasil inverse GF dengan Sv − βv−1Sv−1 . Sehingga didapat data-path seperti gambar berikut:
Gambar 28 Data-path algoritma 2
51
III.4.5.4.
Data-path Algoritma 3
Rumus untuk algoritma 2 adalah:
Sv = Sv −i − Sv −i + j , j = 1,..., i; i = 1,..., v − 2 Dari rumus diketahui diperlukan hanya sebuah GF substractor/adder uuntuk mengimplementasikan Sv−i − Sv−i + j . Berikut data-path-nya:
Gambar 29 Data-path algoritma 3
III.4.5.5.
Data-path Algoritma 4
Rumus untuk algoritma 4 adalah:
S v −i =
( Sv −1 ) , j = 1,..., i; i = 1,..., v − 2 ( β v −i − β v −i −1 )
Dari rumus tersebut diketahui, diperlukan sebuah GF substractor/adder untuk
βv−i − βv−i−1 , sebuah inverse GF LUT untuk
(...) , dan sebuah GF ( βv −i − βv −i −1 )
multiplier untuk mengalikan hasil inverse GF dengan Sv −1 .
52
Gambar 30 Data-path algoritma 4
III.4.5.6.
Data-path Algoritma 5
Rumus untuk algoritma 5 adalah:
Sv − i + j =
(Sv −1+ j ) (βv −i + j − βv −i −1 )
, j = 1,..., i; i = 1,..., v − 2
Dari rumus diatas diketahui, algoritma 5 ini mirip dengan algoritma sebelmunya, hanya addressing MUX-nya yang berbeda. Berikut data-path-nya:
Gambar 31 Data-path algoritma 5
III.4.5.7.
Data-path Algoritma 6
Rumus untuk algoritma 6 adalah:
S1 = S1 − S j +1 , j = 1,..., v − 1 Dari rumus tersebut diketahui bahwa algoritma ini mirip dengan algoritma 3, sehingga data-path-nya juga mirip, yaitu hanya diperlukan sebuah GF substractor/adder. 53
Gambar 32 Data-path algoritma 6
III.4.5.8.
Data-path Algoritma 7
Rumus untuk algoritma 5 adalah:
S1 =
Sj
βj
, j = 1,..., v
Dari rumus tersebut diketahui bahwa diperlukan sebuah inverse GF untuk
...
βj
,
dan sebuah GF multipler untuk mengalikan hasil inverse dengan S j , berikut datapath-nya:
Gambar 33 Data-path algoritma 7
Dari semua data-path tersebut kemudian dibuat data-path pengontrol berupa multiplexer untuk memilih algoritma mana yang sedang dijalankan. Struktur datapath keseluruhan seperti yang terlihat pada gambar berikut:
54
addrs_a
addrs_b
alg_result
alg1 alg2 alg3 alg4 alg5 alg6 alg7 alg8
alg_select s1_in s1
s1
sa
s1_in
ALG1
s2
s2
ba
s1_in
sb
s3
s3
sa
s1_in
INV ALPHA LUT
s4
s4
s1_in ALG2 s5
s5
sb
s1_in
ba
s6
s6
bb
sa
sb
s1_in sa
s7
s7
ALG3
s1_in sb s8
s8
reg_acc b1
INV ALPHA LUT
ALG4
b1 ba
bb
sa
b2 b2
b3
INV ALPHA LUT
b3
ALG5
ba ba b4
bb
sa
b4 sa
b5 b5
ALG6 bb
b6
sb
b6 sa
b7 b7
b8
sb
INV ALPHA LUT
b8 ALG7
addrb_a
addrb_b
Gambar 34 Struktur data-path dan multiplexer Processing Element FJKA
55
III.4.5.9.
Desain Control Unit
Setelah semua data-path uuntuk semua algoritma selesai, didefinisikan control unitnya. Karena algoritma ini bersifat dinamik karena eksekusinya tergantung nilai V_COEF, maka control unit didesain menggunakan Finite State Machines (FSM). FSM dibagi menjadi tiga path berdasarkan nilai V_COEF, yaitu INIT_1, INIT_2, dan INIT_3.
Gambar 35 Skema pengontrolan FKJA
INIT_1 akan dieksekusi apabila diketahui nilai V_COEF sama dengan 2, INIT_2 akan dieksekusi apabila diketahui V_COEF lebih dari 2 dan kurang dari atau sama dengan 8, dan INIT_3 akan dieksekusi apabila diketahui V_COEF sama dengan 1. Setelah semua state berhasil didefinisikan, selanjutnya membuat scheduling, yaitu mendesain korelasi address register Syndrome dan Beta dengan variable-variabel lainnya. Variabel yang dijadikan pembanding untuk menggenerate address bisa state, V_COEF, ataupun address register lainnya. Perhitungan korelasi tersebut diperlihatkan pada tabel di lampiran. Berikut gambar FSM control unit blok FKJA.
56
rst
IDLE
OUTGEN
start
REG_ACC
CHECK_V
v_coef = 2
2 < v_coef <= 8
v_coef = 1
INIT_1
INIT_2
ALG2A
ALG1
INIT_3
max_count_alg1 = 0 max_count_alg1 /= 0
ALG2B
count_alg7 = max_count_alg7 count_alg7 /= max_count_alg7
count_alg3 /= max_count_alg345 ALG3
ALG7
count_alg3 = max_count_alg345
count_alg6 = max_count_alg6
ALG6
ALG4 count_alg5 = max_count_alg345
count_alg6 /= max_count_alg6
INTM max_count_alg345 = v_coef - 3
ALG5 count_alg5 /= max_count_alg345
Gambar 36 FSM Control Unit Fast-Komo Algorithm
57
Berikut ini tabel kondisi state yang ada beserta penjelasannya: Tabel 7 State control untuk unit FJKA
NO STATE
KETERANGAN
1
State setelah kondisi reset, state akan terus IDLE sampai
IDLE
ada sinyal start_komo masuk yang mengindikasikan algoritma siap dijalankan. 2
REG_ACC
State dimana blok FKJA memasukkan mengambil nilai syndrome yang didapat dari syndrome generator dan v_coef yang didapat dari chien_search.
3
CHECK_V
State dimana FKJA mengecek nilai V_COEF untuk mengambil keputusan path berikutnya. Jika nilai V_COEF = 2 state berpindah ke INIT_1, jika nilai V_COEF = 1, state berpindah ke INIT_3, dan jika 2 < V_COEF ≤ 8 state berpindah ke INIT_2.
4
INIT_1
State untuk inisialisai path 1. Saat state ini, kondisi counter dan register control yang berhubungan dengan algoritma 2, 6, dan 7 di reset.
5
INIT_2
State untuk inisialisasi path 2. Saat state ini, kondisi counter dan register control yang berhubungan dengan algoritma 1, 2, 3, 4, 5, 6, dan 7 direset.
6
INIT_3
State untuk inisialisasi path 3. Saat state ini, kondisi counter dan register control yang berhubungan dengan algoritma 7 direset.
7
ALG1
State untuk menjalankan komputasi algoritma 1. State akan berpindah ke ALG2B jika counternya sudah mencapai nilai maksimal.
8
ALG2A
State untuk menjalankan komputasi algoritma 2 dari path 2. State akan berpindah ke ALG3 jika counternya sudah mencapai nilai maksimal.
9
ALG2B
State untuk menjalankan komputasi algoritma 2 dari path 1. 58
State akan berpindah ke ALG3 jika counternya sudah mencapai nilai maksimal. 10
ALG3
State untuk menjalankan komputasi algoritma 3. State akan berpindah ke ALG4 jika setelah satu clock cycle. Algoritma 3 hanya dilakukan dalam 1 clock cycle.
11
ALG4
State untuk menjalankan komputasi algoritma 4. State akan berpindah ke ALG5 setelah 1 clcock cycle. Algoritma 4 hanya dieksekusi dalam 1 clock cycle.
12
ALG5
State untuk menjalankan komputasi algoritma 5. State akan berpindah ke ALG3 jika counter sudah mencapai nilai maksimal, dan akan berpindah ke state ALG6 jika counter mencpai niai V_COEF – 3.
13
ALG6
State untuk menjalankan komputasi algoritma 5. State akan berpindah ke ALG7 jika counter sudah mencapai nilai maksimal.
14
ALG7
State untuk menjalankan komputasi algoritma 7. State akan berpindah ke OUTGEN jika counter sudah mencapai nilai maksimal.
15
OUTGEN
State dimana output dari blok ini sudah selesai dihitung. Pada state ini, sinyal head_out degenerate dan output berupa nilai error disimpan pada register input blok selanjutnya.
16
INTM
State intermediate dimana dichek apakah nilai count maksimal sudah mencpai harga batas, jika sudah maka state akan berpindah ke ALG6.
59
III.4.6.
Integrasi Blok
Pada bagian ini akan dijelaskan bagaimana mekanisme proses decoding dan komunikasi antar bloknya. III.4.6.1.
Handshaking
Karena proses yang dilakukan bukan bitsteam, maka pada tiap blok perlu diberi unit buffer. Buffer-buffer tersebut terutama berfungsi sebagai Serial to Parallel. Proses yang dilakukan oleh beberapa blok tidak menentu kebutuhan clock cyclenya sehingga perlu dibuat unit handshake untuk menandakan bahwa proses blok sebelumnya sudah selesai atau belum. Blok-blok yang memerlukan handshake adalah blok IE dan blok FKJA. Berikut ini ilustrasinya:
Gambar 37 Proses handshaking
Chien search membutuhkan nilai sigma yang dihasilkan oleh blok IE dimana waktu selesai algoritmanya tergantung dari nilai-nilai pada syndrome. Proses selesai ditandai dengan sinyal finish_euclid. Jika proses IE sudah selasai, maka SWP_BUFF yaitu buffer Serial to Parallel akan meminta data dari RAM L yang ada di blok IE. Blok IE akan mengeluarkan flag ready kepada SWAP_BUFF untuk memberitahu bahwa data pada RAM L sudah siap diambil. Jika diberi flag ready untuk write, 60
SWAP_BUFF akan mengirimkan request address RAM ke RAM L. Lalu IE akan mengirimkan data-data yang diminta kemudian SWAP_BUFF menyimpannya dalam register Parallel. Pada Blok FKJA, dibutuhkan input syndrome dari SYND_GEN dan sigma_alpha dan CHIEN_SEARCH. Algoritma FKJA akan dimulai ketika ada sinyal start_komo
yang
didapatkan
setelah
ada
sinyal
finish_chien
dari
CHIEN_SEARCH. Saat algoritma dimulai, blok FJKA akan meminta data syndrome dari SYND_BUFF, dan data sigma_alpha dari CHIEN_SEARCH. Untuk memastikan bahwa ada data pada SYND_BUFF, maka buffer tersebut mengeluarkan flag ready kepada FJKA. Jika ada flag ready dan start_komo maka FJKA akan meminta data dari buffer tersebut. III.4.6.2.
Desain Main Control Unit
Gambar 38 Main control unit
Interface proses handshaking dapat dibuat pada masing-masing blok ataupun pada sebuah unit tersendiri. Pada desain kali ini, proses handshaking dilakukan oleh 61
unit MCU. Selain sebagai unit handshaking, MCU berfungsi untuk memberikan nilai initial untuk blok IE. Fungsi utama blok MCU ini adalah untuk mengatur code rate RS decoder untuk implementasi pada WiMax. Pengaturan ini dilakukan oleh parameter mode dari luar blok RS Decoder ini. III.4.6.3.
Aliran Proses Decoding
Gambar 39 Aliran proses decoding
Aliran proses decoding adalah sebagai berikut: 62
1.
Proses awal: RAM INPUT terisi penuh, kemudian start sinyal untuk decoder muncul.
2.
SYNDROME GENERATOR dan pengisian RAM OUTPUT: Saat start sinyal muncul, Syndrome generator mulai mengkalkulasi nilai-nilai syndrome. Sambil data diinputkan ke blok SYNDROME GENERATOR, data dari RAM INPUT di-copy ke RAM OUTPUT.
3.
SYNDROME
BUFFER:
setelah
SYNDROME
GENERATOR
menyelesaikan komputasinya, sinyal finish syndrome dibuat kemudian nilai-nilai syndrome disimpan pada SYNDROME BUFFER. 4.
EUCLIDEAN ALGORITHM: sambil disimpan di buffer, data syndrome diinputkan ke blok Euclidean secara serial. Kemudian blok tersebut menjalankan kalkulasi algoritma Euclidean.
5.
SWAP BUFFER: data dari blok Euclidean kemudian disimpan dalam buffer. Buffer ini memiliki interface handshaking sehingga akan bekerja saat diberi sinyal start oleh blok sebelumnya.
6.
CHIEN_SEARCH: setelah buffer mengeluarkan sinyal ready, data dari EUCLIDEAN ALGORITHM yang sudah dishift manjadi parallel pada SWAP_BUFFER diambil oleh CHIEN_SEARCH untuk dikomputasi algoritma Chiennya.
7.
FJKA: Setelah CHIEN_SEARCH selesai dan mengeluarkan sinyal finish, maka blok FJKA aktif dan meminta data dari SYNDROME BUFFER dan CHIEN_SEARH untuk dikomputasi.
8.
ERROR_CORRECTING: Setelah diketahui posisi dan nilai error, blok ERROR_CORRECTING mengoreksi data yang ada pada RAM Output kedalam data yang sudah di-decode.
9.
OUTPUT_RAM: Setelah semua koreksi error selesai, RS Decoder akan mengeluarkan datanya ketika diminta.
63
III.5.
Implementasi RTL Code
Implementasi RTL code dilakukan dengan menggunakan Verilog HDL. Verilog dipakai karena lebih mudah dalam hal verifikasi karena dengan mudah dapat memanggil file biner sebagai input. Juga kemampuannya untuk men-display-kan hasil, dan kemudahan untuk auto-compare hasil HDL dengan test vector yang dibuat dari Matlab, juga kemampuannya untuk men-trace sinyal-sinyal di dalam module. Simulasi HDLnya dilakukan mengunakan ModelSim. //read from file $readmemb ("../../matlabfix/vectors/datain.ref", encoded_word_ref); Berikut adalah RTL hierarchy pada desain yang sudah dibuat: M: rsDecoder.v M: rsDecCore.v M: rsDecSyndBlock.v M: rsDecSyndCell.v M: rsDecEuclid.v M: rsDecEuclidCU.v M: rsDecEuclidPE.v M: rsDecChienBlock.v M: rsDecChienCell.v M: rsDecKomo.v M: rsDecKomoCU.v M: rsDecKomoPE.v M: rsDecErrCorr.v M: rsMCU.v
64
