BAB 3 PERANCANGAN AWAL INVERSE-CABAC
Pada program JM 11.0 yang digunakan sebagai program acuan pada tugas akhir ini, algoritma binary arithmetic coding untuk modul Inverse-CABAC dimuat dalam file biaridecod.c. Proses perancangan awal arsitektur Inverse-CABAC ini selain dilakukan berdasarkan pemahaman yang didapat dari standard, juga dilakukan dengan mengidentifikasi kode C yang mendeskripsikan kerja InverseCABAC pada program acuan tersebut. 3.1
Proses Inisialisasi
Pada standard dijelaskan bahwa sebelum memulai proses decoding diperlukan proses inisialisasi. Ada dua proses inisialisasi yang dijelaskan pada standard, yaitu proses inisialisasi variabel context dan proses inisialisasi untuk decoding engine. 3.1.1
Proses Inisialisasi untuk Variabel Context Tabel 3.1 Kode C untuk Proses Inisialisasi Variabel Context
/*! ************************************************************************ * \brief * Initializes a given context with some pre-defined probability state ************************************************************************ */ void biari_init_context (struct img_par* img, BiContextTypePtr ctx, const int* ini) { int pstate; pstate = ((ini[0]* max(0,img->qp) )>>4) + ini[1]; pstate = min (max ( 1, pstate), 126); if ( pstate >= 64 ) { ctx->state = pstate - 64; ctx->MPS = 1; } else { ctx->state = 63 - pstate; ctx->MPS = 0; } }
Kode C untuk proses inisialisasi nilai variabel context ditunjukkan pada tabel 3.1. 16
Standard menjelaskan bahwa nilai state (pStateIdx) dan MPS (valMPS) untuk inisialisasi ini bergantung pada parameter kuantisasi (SliceQPY). Bila nilai m dan n diberikan dalam bentuk tabel, berikut adalah algoritma yang digunakan untuk menentukan nilai state dan MPS tersebut. Tabel 3.2 Pseudo Code Penghitungan Nilai Context Model [5]
1.
preCtxState = Clip3(1, 126, (( m ∗ Clip3( 0, 51, SliceQPY )) >> 4 ) + n )
2.
if( preCtxState <= 63 ) { pStateIdx = 63 - preCtxState valMPS = 0 } else { pStateIdx = preCtxState - 64 valMPS = 1 }
Dari tabel 3.2 di atas, bagian pertama fungsi inisialisasi variabel context, nilai preCtxState, dapat dibagi menjadi beberapa tahap komputasi. Pertama, perkalian nilai parameter kuantisasi (SliceQPY) dengan nilai m. Kedua, penjumlahan hasil perkalian yang di-shift kanan dengan nilai n. Ketiga, proses clipping terhadap hasil penjumlahan, yaitu membatasi nilai ini di antara 1 sampai 126. Bagian kedua fungsi inisialisasi adalah pembentukan nilai context model dari output clipping. Dengan demikian komponen datapath untuk proses inisialiasasi context model dapat diidentifikasi sebagai berikut : 1. Multiplier Multiplier yang dibutuhkan memiliki lebar data input masing-masing 8-bit, yaitu input pertama untuk nilai parameter kuantisasi, sedangkan input kedua untuk nilai m. Dengan demikian lebar data output multiplier adalah 16-bit. Karena output multiplier akan selalu di-shift right sebanyak 4-bit, maka nilai efektif dari multiplier yang akan diambil untuk proses berikutnya adalah 12 MSB bit. Ilustrasi untuk input dan output multiplier ini dapat dilihat pada gambar 3.1.
17
Gambar 3.1 Komponen Multiplier untuk Proses Inisialisasi
2. Adder Adder yang diperlukan pada proses inisialisasi context model adalah adder 12bit, seperti yang terlihat pada gambar 3.2. Input adder adalah 12-bit data keluaran multiplier dan nilai n. Karena nilai n adalah data 8-bit, maka data ini perlu di-sign extend terlebih dahulu sebelum menjadi input multiplier.
Gambar 3.2 Komponen Adder untuk Proses Inisialisasi
3. Clipper Fungsi clipper adalah membatasi nilai keluaran proses penjumlahan pada tahap kedua proses inisialisasi agar berada pada range yang ditentukan, yaitu antara 1 sampai 126. 1 ≤ Smi ≤ 126
Secara fungsional, proses clipping dapat diimplementasikan dengan menggunakan dua buah komparator dan dua buah multiplexer. Akan tetapi, untuk mendapatkan rancangan hardware yang optimum dalam hal area maupun combination delay, maka bagian komparator digantikan dengan menggunakan bit processing secara hard-wired.
18
Berdasarkan range yang telah ditentukan, maka keluaran clipper cukup untuk direpresentasikan dalam data 8-bit. Dengan demikian untuk proses komparasi akan dilakukan berdasarkan nilai bit ke-0 sampai ke-7 dari data tersebut. a. Komparator pertama Pseudo-code untuk proses komparasi bagian pertama adalah sebagai berikut : If (mQn > 1) Sma = mQn Else Sma = 1
Dengan demikian, secara hardware, proses komparasi dapat dilakukan dengan melakukan operasi OR setiap bit mQn seperti yang terlihat pada gambar 3.3. Hasil proses OR ini digunakan sebagai sinyal kontrol untuk memilih data input atau “1”.
Gambar 3.3 Operasi OR sebagai Pengganti Komparator
b. Komparator kedua Pseudo-code untuk proses komparasi bagian pertama adalah sebagai berikut : If (Sma > 126) Smi = 126 Else Smi = Sma
19
Dengan demikian, secara hardware, proses komparasi di atas dapat dilakukan dengan melakukan operasi OR bit ke-7 Smi dengan hasil operasi AND bit ke-0 sampai bit ke-6 Smi seperti yang terlihat pada gambar 3.4. Hasil operasi logika ini digunakan sebagai sinyal kontrol untuk memilih data input atau “126”.
Gambar 3.4 Konfigurasi OR dan AND sebagai Pengganti Komparator
4. Logic Unit untuk pembentukan context model Bagian ini merupakan tahap terakhir proses inisialisasi untuk variabel context. Dari tabel 3.2 dapat dilihat variabel context terdiri dari dua data, yaitu nilai state, berupa data 6-bit dan nilai MPS, data 1-bit. Dengan demikian, untuk proses pembentukan state dan MPS hanya akan memperhitungkan 7-bit terakhir Smi (Smi[6:0]). Proses pembentukan nilai state dan MPS dilakukan berdasarkan range nilai Smi. Pertama, nilai Smi yang lebih besar dari 63, dan kedua, nilai Smi lebih kecil atau sama dengan 63. Dengan demikian, batas pembagian range nilai Smi, yang juga menunjukkan nilai MPS, dapat diidentifikasi dari nilai Smi[6].
20
Gambar 3.5 Proses Mappping untuk Pembentukan Nilai State
Setelah nilai MPS diperoleh, tahap selanjutnya, yaitu pembentukan nilai state, dapat dilakukan. Pembentukan nilai state dapat digambarkan dalam data mapping seperti gambar 3.5. Bagian kiri, merupakan mapping untuk nilai MPS sama dengan “0”, sedangkan bagian kanan adalah mapping untuk nilai MPS sama dengan “1”. Proses mapping ini, secara fungsional, seperti ditunjukkan dalam pseudo code, dapat dilakukan dengan menggunakan substractor dan multiplexer. Akan tetapi, dengan mempertimbangkan area yang digunakan, maka proses pembentukan nilai state dilakukan dengan menggunakan rangkaian dalam bentuk gate level. Dari proses mapping terlihat bahwa, untuk nilai MPS “0” data akan di-mapping menjadi nilai 1’s complement atau hasil bit-wise NOT dari data masukan. Sedangkan untuk nilai MPS “1” data akan di-bypass. Dengan demikian, rancangan rangkaian pembentuk nilai state dan MPS dapat digambarkan seperti gambar 3.6.
21
Gambar 3.6 Arsitektur Pembentuk Nilai State dan MPS
Untuk proses inisialisasi context model, nilai m dan n yang diberikan dalam bentuk tabel, dapat diimplementasikan menjadi ROM, seperti yang terlihat pada gambar 3.7.
ROMContext 844 x 16 bit 10
address
data
16
Gambar 3.7 ROM Context
Ada 844 nilai m dan n yang akan digunakan untuk menghitung state dan MPS yang akan membentuk context model. Dengan demikian, untuk mengakses ROM ini diperlukan input adress sepanjang 10 bit. Nilai m dan n ini sendiri panjang masing-masingnya adalah 8 bit, sehingga bila data output dari ROM ini, berupa nilai m dan n yang penulisannya disatukan, maka panjang data output ROM ini menjadi 16 bit, seperti yang diilustrasikan pada gambar berikut.
Gambar 3.8 Struktur Data Output ROM Context
22
Nilai state dan MPS (context model) yang dihasilkan dari algoritma di atas kemudian akan disimpan ke dalam suatu memory. Nilai state maksimum pada context model ini adalah 63, yang kemudian direpresentasikan ke dalam 6 bit bilangan biner, sedangkan nilai MPS hanya 1 bit sehingga bila nilai state dan mps disatukan terlebih dahulu sebelum ditulis ke memory maka data input untuk memory ini adalah sebanyak 7 bit. Karena jumlah context model yang dihitung adalah sejumlah nilai m dan n yang disimpan di dalam ROM Context, maka dengan demikian ukuran memory yang diperlukan untuk menampung nilai state dan MPS awal adalah 7 bit x 844. Gambar 3.9 adalah diagram blok memory yang digunakan untuk menyimpan context model.
RAMContext 844 x 7 bit 10
address data_out
7
16
data_in write_enable read_enable
Gambar 3.9 RAM_Context
3.1.2
Proses Inisialisasi untuk Decoding Engine
Proses ini berlangsung sebelum men-decode macroblock pertama pada suatu slice atau setelah men-decode pcm_alignment_zero_bit, pcm_sample_luma, dan pcm_sample_chroma dari suatu macroblock tipe I_PCM. Output proses ini, yaitu: •
codIRange diset sama dengan 0x01FE
•
codIOffset diset sama dengan nilai 9 bit pertama dari bitstream
Standar mendefinisikan penggunaan register 16-bit untuk kedua variabel di atas, tetapi kebutuhan minimum untuk kedua variabel tersebut adalah 9 bit. Pada perancangan inverse CABAC ini, output proses ini akan disimpan pada register 16-bit.
23
Gambar 3.10 Register Range dan Offset
Selain digunakan untuk menyimpan nilai inisialisasi yang dibutuhkan oleh decoding engine, register range dan offset ini juga digunakan untuk menyimpan nilai update range dan offset setelah proses pada decoding engine. Nilai update range dan offset ini akan digunakan untuk proses berikutnya pada decoding engine. Gambar 3.10 menunjukkan diagram blok register yang digunakan untuk menyimpan nilai range dan offset. 3.2
Tahapan pada Decoding Engine
Setelah proses inisialisasi selesai, maka proses arithmetic decoding dapat dilakukan. Ada tiga mode untuk proses arithmetic decoding ini, yaitu mode normal (DecodeDecision), mode bypass (DecodeBypass), dan mode terminate (DecodeTerminate). Standard menjelaskan input dan langkah-langkah yang dibutuhkan untuk menjalankan proses arithmetic decoding sesuai masing-masing mode, beserta diagram alir yang dapat membantu pemahaman tentang proses yang terjadi pada decoding engine tersebut. 3.2.1
Proses Arithmetic Decoding untuk Mode Normal
Input untuk proses ini adalah nilai range, offset, serta nilai state dan MPS (context model), sedangkan output proses ini adalah nilai decoded bit, dan update nilai range dan offset, serta update nilai context model. Gambar 3.11 menunjukkan diagram alir proses decoding untuk mode normal.
24
3.2.1.1 Proses Pengaksesan Tabel Dari diagram alir tersebut terlihat bahwa proses pertama yang dilakukan pada proses arithmetic decoding ini adalah menentukan nilai qCodIRangeIdx yang akan digunakan untuk mengakses tabel rangeTabLPS, seperti dispesifikasikan dalam tabel 9-35 pada dokumen standard H.264 dari ITU-T [5]. Beberapa nilai rangeRLPS pada tabel rangeTabLPS tersebut dapat dilihat pada tabel 3.3.
Gambar 3.11 Diagram Alir Proses Decoding untuk Mode Normal [5]
Tabel 3.3 Nilai rangeTabLPS
pStateIdx 0 1 2 ... 63
0 128 128 128 ... 2
qCodRangeIdx 1 2 176 208 167 197 158 187 ... ... 2 2
25
3 240 227 216 ... 2
Untuk proses decoding, nilai rangeTabLPS seperti ditunjukkan tabel 3.3 diimplementasikan dengan ROM. Alamat ROM rLPS dibentuk dari nilai qCodRangeIdx dan pStateIdx. Berdasarkan kemungkinan nilai qCodRangeIdx dan pStateIdx, maka alamat ROM dapat direpresentasikan dalam 8-bit. Proses pembentukan ROM rLPS dan alamat ROM rLPS diilustrasikan dalam mapping, seperti terlihat pada gambar 3.12.
pStateIdx
qCodIrangeIdx 0
1
2
3
0 1 2 3 4 ... 63 ROM_rLPS 0 1 2
ROM_rLPS Address 7 6 5
0
3
127
pStateIdx[5:0] qCodeIrangeIdx[1:0]
255
Gambar 3.12 Mapping Data dan Alamat untuk ROM rLPS
Selain menggunakan tabel rangeTabLPS untuk menentukan nilai codIRangeLPS, diagram alir proses arithmetic decoding untuk mode normal menunjukkan bahwa nilai state juga akan di-update dengan mengakses tabel. Tabel yang digunakan untuk update nilai state pada proses decoding ini dispesifikasikan dalam tabel 936 pada dokumen standard H.264 dari ITU-T [5]. Beberapa nilai update state untuk setiap index, ditunjukkkan pada tabel 3.4.
26
Dari tabel 3.4 dapat dilihat untuk setiap nilai index, nilai state terdiri dari dua buah data, yaitu nilai state LPS dan state MPS. Nilai-nilai state tersebut, untuk realisasi rancangan Inverse CABAC diimplemetasikan dalam ROM, dimana nilai state LPS dan MPS digabung menjadi satu data. Dengan penggabungan data dalam satu alamat, maka proses decoding alamat ROM hanya diperlukan sekali saja. Dengan demikian, hasil rancangan akan memiliki area yang lebih kecil. Tabel 3.4 Nilai Update untuk State
pStateIdx 0 1 2 3 ... 63
State transIdxLPS 0 0 1 2 ... 63
transIdxMPS 1 2 3 4 ... 63
Gambar 3.13 menunjukkan pembentukan ROM state dari tabel nilai state.
7
0
0 7 State LPS
State MPS
ROM State Data
Gambar 3.13 Format Data ROM state
Walaupun diagram alir menunjukkan bahwa tabel rangeTabLPS dan tabel state diakses pada urutan yang berbeda, akan tetapi secara hardware proses ini dapat dilakukan dalam clock cycle yang sama. Arsitektur pembacaan ROM rLPS dan ROM State dapat dilihat pada gambar 3.14.
27
Gambar 3.14 Akses ROM rLPS dan ROM State
3.2.1.2 Proses Update Nilai Range dan Offset Pada proses decoding, nilai range dan offset akan di-update. Dari diagram alir terlihat bahwa output proses update ini akan dipilih berdasarkan hasil perbandingan nilai offset dan range (codIOffset >= codIRange), seperti yang terlihat pada tabel 3.5. Selain mempengaruhi update nilai range dan offset, hasil perbandingan nilai offset dan range juga akan mempengaruhi output bit yang didecode. Tabel 3.5 Proses Update Range dan Offset Mode Normal
codIOffset >= codIRange
codIOffset < codIRange
update Range = codIRangeLPS
= codIRange - codIRangeLPS
update Offset = codIOffset – (codIRange – codIRangeLPS)
= codIOffset
decoded bit
= valMPS
= !valMPS
Dari tabel di atas terlihat bahwa dibutuhkan 2 komponen substractor dan 2 multiplexer untuk membentuk datapath yang digunakan untuk proses update range dan offset. Arsitektur untuk proses update range dan offset ini dapat dilihat pada gambar 3.15.
28
Gambar 3.15 Arsitektur Update Range dan Offset Mode Normal
3.2.1.3 Proses Renormalisasi
Gambar 3.16 Diagram Alir untuk Proses Renormalisasi [5]
Proses berikutnya yang dilakukan pada tahap decoding adalah renormalisasi. Proses renormalisasi ditunjukkan dalam diagram alir pada gambar 3.16. Dari diagram alir dapat dilihat bahwa renormalisasi dilakukan jika nilai range lebih kecil dari 0x100. Dengan demikian tahap pertama dari renormalisasi adalah pengecekan nilai range. Proses pengecekan nilai range dilakukan dengan mengggunakan operasi bit-wise nilai range. Hasil operasi logika ini digunakan sebagai salah satu sinyal kontrol yang menentukan terjadinya proses renormalisasi. Arsitektur rangkaian untuk pengecekan nilai range dapat digambarkan seperti gambar 3.17.
29
range[15] range[14]
low_range_valid
Range[15:0] range[8]
Gambar 3.17 Gate untuk Pengecekan Nilai Range
Nilai renormalisasi range diperoleh dari nilai update range yang dikalikan dua, sedangkan nilai renormalisasi offset diperoleh dengan mengalikan nilai update offset dan ditambah dengan nilai bitstream. Proses renormalisasi ini diimplementasikan dengan menggunakan proses shifting, seperti diilustrasikan gambar 3.18 dan gambar 3.19.
Gambar 3.18 Ilustrasi Renormalisai Nilai Range
offset_out[15:0] offset_out[14:0]
offset_out[14:0] bitstream
Gambar 3.19 Ilustrasi Renormalisasi Nilai Offset
30
3.2.2
Proses Arithmetic Decoding untuk Mode Bypass
Input untuk proses ini adalah nilai range, offset, dan bitstream. Diagram alir proses decoding untuk mode bypass ini dapat dilihat pada gambar 3.20.
Gambar 3.20 Diagram Alir Proses Decoding untuk Mode Bypass [5]
Dari diagram alir dapat dilihat bahwa proses decoding pada mode bypass dimulai dengan menggeser nilai codIOffset ke kiri satu bit, kemudian ditambahkan dengan dengan nilai bitstream. Proses ini dapat dilihat pada gambar 3.21 .
Gambar 3.21 Proses Shifting codIOffset pada Mode Bypass
Pada proses arithmetic decoding untuk mode bypass, hanya nilai offset yang akan di-update sedangkan nilai range update-nya akan selalu sama dengan nilai range inputnya. Proses update range dan offset ini dirangkum pada tabel 3.6, sedangkan arsitektur untuk proses update range dapat dilihat pada gambar 3.22.
31
Tabel 3.6 Proses Update Range dan Offset Mode Bypass
codIOffset >= codIRange
codIOffset < codIRange
update Range = codIRange
= codIRange
update Offset = codIOffset – codIRange
= codIOffset
decoded bit
=0
=1
Gambar 3.22 Arsitektur untuk Proses Update Offset pada Mode Bypass
3.2.3
Proses Arithmetic Decoding untuk Mode Terminate
Diagram alir untuk proses decoding dengan mode terminate ini dapat dilihat pada gambar 3.23.
DecodeTerminate
codIRange = codIRange-2
Yes
codIOffset >= codIRange
No
binVal = 0
binVal = 1
RenormD
Done
Gambar 3.23 Diagram Alir Proses Decoding untuk Mode Terminate [5]
32
Dari diagram alir terlihat bahwa tahap pertama pada proses arithmetic decoding untuk mode terminate adalah meng-update nilai range input. Proses update nilai range ini membutuhkan komponen substractor seperti yang terlihat pada gambar berikut:
Gambar 3.24 Komponen Substractor untuk Update Nilai Range
Berbeda dengan proses arithmetic decoding untuk mode normal dan bypass, update nilai range dan offset tidak akan bergantung pada hasil perbandingan nilai offset dan range (codIOffset >= codIRange). Hasil perbandingan nilai offset dan range tersebut hanya akan mempengaruhi nilai bit yang di-decode. Pengaruh hasil perbandingan nilai offset dan range ini dapat dilihat pada tabel berikut. Tabel 3.7 Proses Update Range dan Offset Mode Terminate
codIOffset >= codIRange
codIOffset < codIRange
update Range = codIRange - 2
= codIRange - 2
update Offset = codIOffset
= codIOffset
decoded bit
=0
=1
Proses decoding pada mode Terminate juga membutuhkan proses renormalisasi. Tahapan proses renormalisasi pada mode Terminate sama dengan proses renormalisasi pada mode Normal, yang membedakan hanya syarat yang diperlukan untuk memulai proses renormalisasi tersebut.
33
Dari perancangan awal Inverse-CABAC, didapatkan komponen-komponen datapath dan format data yang diperlukan untuk proses perancangan lebih lanjut. Dari tahap ini juga dapat diidentifikasi bahwa proses Inverse-CABAC dapat dilakukan dalam beberapa blok, yaitu: 1. Blok Init Context, untuk proses inisialisasi variabel context, 2. Register Range dan Offset, untuk proses inisialisasi decoding engine dan menyimpan nilai update range dan offset, 3. Blok Arithmetic Coding, untuk proses decoding engine. Berdasarkan proses update nilai range, offset dan renormalisasi, maka proses decoding engine dilakukan oleh blok arcod dan blok bypass. Blok arcod digunakan untuk proses decoding pada mode normal dan terminate, sedangkan blok bypass digunakan untuk proses decoding pada mode bypass.
34
