Evaluasi Unjuk Kerja Good Convolutional Codes pada Skema Penyandian Bertingkat RS-CC

CITEE 2014

Yogyakarta, 7 - 8 Oktober 2014

ISSN: 2085-6350 ISBN: 978-602-71396-1-9

Evaluasi Unjuk Kerja Good Convolutional Codes pada Skema Penyandian Bertingkat RS-CC Daryus Chandra, Adhi Susanto, Sri Suning Kusumawardani Department of Electrical Engineering and Information Technology, Universitas Gadjah Mada

Jalan Grafika no.2, Yogyakarta, 55281, Indonesia [email protected] Abstract—RS concatenated schemes is well-known for its powerful error-correcting capability, hence this scheme is used for many telecommunication standards. Choosing “good convolutional codes” is essential since there are infinite number of convolutional codes that can be created based on its parameter. This paper presents the performance of “good convolutional codes” in concatenated scheme with RS code. The performance is measured by its bit error rate (BER). The simulation results show that good convolutional codes are more superior than others convolutional codes that picked randomly based on the error correcting capability. Good convolutional codes also shows a better performance on RS-CC concatenated schemes than the other convolutioal codes. It means “good convolutional codes” remain “good” in RS-CC concatenated schemes. Intisari—Skema penyandian bertingkat RS-CC dikenal dengan kemampuan koreksi galatnya yang andal sehingga digunakan pada berbagai standar telekomunikasi. Pemilihan good convolutional codes sangat penting mengingat terdapat sejumlah tak hingga kemungkinan sandi konvolusi yang bisa dibentuk berdasarkan parameternya. Makalah ini memaparkan hasil unjuk kerja dari aplikasi good convolutional codes yang disandikan secara bertingkat bersama dengan sandi RS. Unjuk kerja diukur berdasarkan BER yang dihasilkan oleh simulasi. Hasilnya menunjukkan bahwa good convolutional codes jauh lebih unggul dibandingkan dengan sandi konvolusi lain yang dipilih secara acak ditinjau dari aspek koreksi galat. Good convolutional codes juga menunjukkan unjuk kerja yang lebih baik dalam skema penyandian bertingkat RS-CC jika dibandingkan sandi konvolusi lain. Artinya, good convolutional codes tetap menjadi sandi yang “baik” meskipun dalam skema penyandian bertingkat RS-CC. Kata Kunci— Penyandian kanal, teknik koreksi galat, sandi konvolusi, sandi RS, concatenated codes

I. PENDAHULUAN Skema pengkodean bertingkat (concatenated coding schemes) diperkenalkan karena skema pengkodean ini memberikan peroleh penyandian (coding gain) yang relatif besar jika dibandingkan dengan metode penyandian tunggal. Skema penyandian bertingkat biasanya berupa gabungan dari dua sandi yang bersifat berlawanan satu sama lain. Sandi dalam biasanya berupa sandi konvolusi dan sandi luar biasanya berupa sandi blok, misalnya Sandi RS, Sandi BCH, Sandi Hamming dan lain-lain.Skema penyandian bertingkat yang sering digunakan adalah skema RS-CC. Hal ini dikarenakan masing-masing sandi mengatasi kelemahan yang dimiliki satu sama lain. Sandi konvolusi dikenal sebagai sandi yang handal untuk mengatasi galat tipe acak, namun tidak cocok dalam mengatasi galat tipe deburan. Sebaliknya, sandi Reed-Solomon (RS) dikenal sebagai sandi yang memiliki keandalan dalam mengatasi galat tipe deburan dibandingkan

Jurusan Teknik Elektro dan Teknologi Informasi, FT UGM

galat tipe acak. Dengan alasan tersebut, skema penyandian bertingkat RS-CC banyak digunakan sebagai teknik koreksi galat yang diterapkan berbagai standar komunikasi seperti WLAN 802.11n dan WiMAX 802.16j dari IEEE serta DVB-T dari ETSI. Perkembangan teknologi telekomunikasi juga menuntut adanya sistem komunikasi bergerak dengan rele, kebutuhan komunikasi nirkabel saat ini, tidak hanya menuntut akses dengan pesat data tinggi, namun juga realibilitas yang tinggi pula. Dari berbagai metode penyandian kanal yang diajukan untuk sistem rele komunikasi bergerak, salah satunya adalah sistem penyandian bertingkat RS-CC [1]. Evaluasi unjuk kerja sistem penyandian bertingkat RS-CC telah dilakukan juga baik dalam sistem OFDM pada WiMAX [2], maupun dalam sistem MIMO-OFDM [3]. Sandi konvolusi sendiri memiliki beberapa parameter seperti m, c, r, dan G(D). Hal ini berarti ada sejumlah tak berhingga sandi konvolusi yang bisa dibentuk, sehingga pencarian sandi kovolusi yang “baik” perlu dilakukan. Pencarian yang dilakukan berhasil menemukan apa yang disebut sebagai good convolutional codes [4], [5]. Sandi konvolusi yang ditemukan ini dikatakan baik, jika digunakan sebagai sistem penyandian tunggal. Untuk sistem penyandian bertingkat dengan sandi konvolusi, juga perlu dilakukan pencarian sandi konvolusi yang “baik”, misalnya good convolutional codes pada sistem penyandian turbo [6]. Pencarian good convolutional codes untuk sistem penyandian bertingkat RS-CC perlu juga dilakukan, mengingat sistem penyandian tersebut, sangat banyak diaplikasikan dalam sistem telekomunikasi. Makalah ini menyajikan evaluasi unjuk kerja good convolutional codes [5], jika diaplikasikan pada sistem penyandian bertingkat RS-CC. Hasilnya akan dibandingkan dengan sistem penyandian bertingkat RS-CC yang menggunakan sandi konvolusi lain yang dianggap “tidak baik”. Unjuk kerja dinilai dengan membandingkan pesat galat bit (bit error rate, BER) yang dihasilkan oleh simulasi. II. GOOD CONVOLUTIONAL CODES Sandi konvolusi adalah satu contoh dari sandi nonsistematis. Sandi ini memiliki kemampuan handal dalam mengatasi galat tipe acak (random error). Sandi konvolusi menyandikan kata pesan dengan panjang m menjadi kata sandi dengan panjang c, sehingga pesat penyandian r dirumuskan dengan: m r= (1) c Sandi konvolusi biasanya dinyatakan dalam bentuk (c, m, k), dengan k adalah derajat dari suku banyak pembangkit (generator polynomial) sandi konvolusi atau dalam implementasinya k banyaknya register geser yang digunakan dalam penyandian sandi konvolusi. Panjang kekangan

293

ISSN: 2085-6350 ISBN: 978-602-71396-1-9


(constraint length) yang dinotasikan dengan L, dirumuskan sebagai berikut: (2) L = k +1 Sandi konvolusi dapat dinyatakan dalam sebagai semiinfinite linear codes. Kata pesan disimbolkan sebagai u(D) = [u(1)D u(2)D … u(k)D] dan kata sandi disimbolkan sebagai c(D) = [c(1)D c(2)D … c(k)D]. Hubungan kata pesan u(D) dan kata sandi c(D) dinyatakan seperti yang ditunjukkan sebagai berikut: ( j) (3) c ( j ) ( D ) = ∑ ik=1 u (i ) ( D ) g i ( D) G(k) adalah polinomial pembangkit dengan G(k) = [g0(k), (k) g1 , ... , gM(k)]. Untuk masing panjang kekangan lebih dari dua, dapat dibentuk lebih dari satu generator polynomial, G(D), yang unik. Akibatnya, akan ada sangat banyak generator polynomial sandi konvolusi yang bisa dibentuk. Pencarian good convolutional codes telah dilakukan dengan berdasarkan pada parameter free distance [4]. Free distance sangat erat kaitannya dengan batas kemampuan koreksi galat dalam sistem penyandian. Jika kata terima dirumuskan dengan r = c + e, maka galat pengawasandian akan terjadi jika memenuhi pertidaksamaan sebagai berikut: dist (r , c) = wt (r − c) ≥ dist (r , c' ) = wt (r − c' ) (4) wt (e) ≥ wt (c − c'+e) ≥ wt (c − c' ) − wt (e) Sehingga galat (c – c’) dapat terjadi jika memenuhi syarat pada pertidaksamaan sebagai berikut: wt (c − c' ) (5) wt (e) ≥ 2 Dengan menganalogikan Hamming distance sandi konvolusi dengan sandi blok linier, maka, maka free distance sandi konvolusi dirumuskan dengan: d free = min (c, c' ) c , c '∈C , c ≠ c '

d free = min wt (c)

(6)

c∈C , c ≠ 0

Galat dapat dipulihkan jika jumlah galat pada kata terima memenuhi persamaan sebagaiberikut:  d free − 1  e= (7)   2  Tabel 1. Generator sequences sandi konvolusi untuk beberapa constraint length

Constraint Length 2 3 4 5 6 7 8 9 10 11 12 13

294

Generator Sequences (1 3)8 (5 7)8 (15 17)8 (23 35)8 (53 75)8 (131 177)8 (247 371)8 (561 753)8 (1131 1537)8 (2473 3217)8 (4325 6747)8 (10627 16765)8

CITEE 2014

Pencarian good convolutional codes dengan berdasarkan pada free distance dianggap belum cukup sehingga pencarian masih terus dilakukan dengan parameter sebagai berikut: transfer function matrices, distance spectra, dan informationweight spectra [5]. Hasil pencarian yang dilakukan menunjukkan beberapa perbaikan dibandingkan pencarian sebelumnya. Hasil pencarian good convolutional codes tersebut dapat dilihat pada Tabel 1. III. REED-SOLOMON CODES Sandi Reed-Solomon atau sering disingkat dengan sandi RS adalah salah satu contoh dari sandi blok atau sandi sistematis yang handal dalam menangani galat tipe deburan (burst error). Sandi RS banyak diaplikasikan pada sistem penyimpanan elektronis maupun sistem komunikasi. Sandi RS adalah sandi blok yang dapat direpresentasikan sebagai RS(n,k). Peubah n adalah panjang kata sandi dan k adalah panjang kata pesan. kemampuan koreksi galat disimbolkan sebagai t yang dirumuskan dengan: n−k (8) t= 2 Sandi RS adalah sandi blok yang memetakan k simbol kata pesan menjadi n simbol kata sandi yang masing-masing simbolnya memiliki panjang m bit. Hubungan antara panjang bit masing-masing simbol dengan panjang kata sandi ditunjukkan sebagai berikut: (9) n = 2m − 1 Masing-masing simbol akan dipetakan dalam finite fields yang disebut juga sebagai Galois Field yang dinotasikan dalam GF(q). Penyandian sandi RS sangat tergantung pada generator polynomial yang ditentukan oleh kemampuan koreksi galat sandi RS. Jika sandi RS memiliki kemampuan koreksi galat t simbol, maka polinomial generator sandi RS dirumuskan dengan: g ( X ) = ( X + α )( X + α 2 )...( X + α 2t −1 )( X + α 2t ) (10) g ( X ) = g + g X + g X 2 + ... + g X 2t 0

1

2

2t

Pengawasandian RS(n,k) diawali dengan menggeser polinomial kata pesan m(X) sejauh (n – k) lalu membagi hasilnya dengan polinomial generator g(X) yang secara matematis dirumuskan sebagai berikut: (11) X n − k .m( X ) = q( X ).g ( X ) + p( X ) q(X) adalah hasil bagi antara kata pesan yang digeser sejauh (n–k) dengan polinomial generator g(X). p(X) adalah hasil bagi yang dapat dinyatakan ulang sebagai berikut: (12) p( X ) = X n− k .m( X ) mod g ( X ) Sehingga diperoleh kata sandi kata sandi c(X) yang dinyatakan sebagai berikut: (13) c( X ) = p( X ) + X n− k .m( X ) Kata sandi selanjutnya dipancarkan melalui kanal transmisi. Kanal transmisi yang bersifat tidak ideal, misalnya karena adanya pudaran, pelemahan, atau derau, menyebabkan kata sandi dapat saja mengalami galat. Oleh karena itu, kata sandi yang tiba di penerima, yang selanjutnya disebut dengan kata terima, perlu mengalami proses pengawasandian.


CITEE 2014


Pengawasandian RS dimulai dengan menghitung nilai dari syndrome kata terima. Syndrome dari kata terima dihitung dengan: (14) Si ( X ) = r ( X ) X =α i = r (α i ) i = 1,2,3,..., n − k r(X) adalah kata terima yang merupakan jumlahan modulo-2 dari kata pesan dan galat saluran transmisi sebagaimana yang ditunjukkan sebagai berikut: (15) r ( X ) = c ( X ) + e( X ) Berdasarkan persamaan (15) maka persamaan (14) dapat dinyatakan sebagai berikut: Si ( X ) = r ( X ) X =α i = [c( X ) + e( X )] X =α i

Si ( X ) = c(α i ) + e(α i ) = 0 + e(α i ) = e(α i )

ISSN: 2085-6350 ISBN: 978-602-71396-1-9

kanal AWGN. Penyandi dalam (inner coding) yang digunakan adalah penyandi konvolusi. Sandi konvolusi yang digunakan adalah sandi konvolusi dengan panjang kekangan L = 3, 4, 5, 6, dan 7. Untuk masing-masing panjang kekangan digunakan good convolutional codes untuk panjang kekangan tersebut, dapat dilihat pada Tabel 1, dan sebagai pembanding dipilih sandi konvolusi yang dipilih secara acak untuk masing-masing panjang kekangan. Untuk penyandi luar (outer coding), sandi yang digunakan adalah sandi RS. Sandi RS yang dipilih adalah sandi RS (255,239) dengan t = 8. Unjuk kerja yang ditinjau pada penelitan kali ini adalah pesat galat bit yang dihasilkan oleh setiap skenario.

(16)

Nilai c(α i ) bernilai nol, karena α i adalah akar-akar dari kata pesan c(X). Jika syndrome kata terima sudah diperoleh, maka polinomial galat yang dinyatakan pada persamaan (17) harus ditentukan agar kata pesan dapat dipulihkan. (17) e( X ) = e j1 X j1 + e j2 X j2 + ... + e jv X jv Langkah yang dilakukan untuk menentukan posisi dan besarnya galat pada polinomial galat adalah dengan menyusun error-locatorpolynomial. Error-locator polynomial disusun dengan persamaan sebagai berikut: σ ( X ) = (1 + β 1 X )(1 + β 2 X )...(1 + β v X ) (18) σ ( X ) = 1 + σ X + σ X 2 + ... + σ X v 1

2

v

Nilai β diperoleh dengan persamaan sebagai berikut: S i = r (α i ) = e j1 β 1i + e j 2 β 2i + .. + e jv β vi i = 1,2,..,2t

(19)

Hasil perhitungan syndrome dari persamaan (16) dapat disusun matriks yang akan digunakan untuk menentukan lokasi galat dari kata terima. Matriks tersebut dinyatakan sebagai berikut: S 2 L S t −1 S t   σ t   S t +1   S1 S S3 L St S t +1  σ t −1   S t + 2   2  × M  =  M  M (20)       S S L S S S t 2t −3 2t − 2   t −1  σ 2   2t −1   S t S t +1 L S 2t − 2 S 2t −1   σ   S 2t     1    Dengan ditemukannya nilai σi maka posisi dan besarnya galat dapat dipulihkan dengan menggunakan persamaan (18) dan persamaan (19) [7]. IV. MODEL SISTEM Model yang digunakan pada penelitian kali ini adalah model sistem komunikasi dengan penyandian kanal tunggal untuk mengevaluasi unjuk kerja good convolutional codes sedangkan model sistem komunikasi dengan penyandian kanal bertingkat digunakan untuk mengevaluasi unjuk kerja good convolutional codes pada skema penyandian bertingkat RSCC. Model sistem komunikasi yang digunakan dapat dilihat berturut-turut pada Gambar 1 dan Gambar 2. Untuk kedua model ditinjau hasil unjuk kerjanya yang berupa pesat galat bit (BER). Modulasi yang digunakan adalah Binary Phase Shift Keying (BPSK) dan kanal komunikasi yang digunakan adalah


Gambar 1. Model sistem komunikasi dengan penyandian tunggal

Gambar 2. Model sistem komunikasi dengan skema penyandian bertingkat

V. HASIL DAN PEMBAHASAN Hasil simulasi untuk sistem penyandian bertingkat RS-CC dengan menggunakan good convolutional codes beserta pembahasannya diuraikan pada sub bab sebagai berikut. A. Unjuk kerja good convolutional codes Good convolutional codes adalah sandi konvolusi yang dalam pencariannya memiliki distance spectra dan information-weight spectra yang paling baik di antara sandi konvolusi lainnya. Dengan demikian, good convolutional codes untuk panjang kekangan L tertentu, secara teoritis akan memberikan kemampuan koreksi galat yang paling baik jika dibandingkan dengan sandi konvolusi yang memiliki panjang kekangan L yang sama. Teori ini dibuktikan pada simulasi yang telah dilakukan. Untuk L = 3 dan L = 7, hasilnya dapat dilihat pada Gambar 3. Pada simulasi ini digunakan model sistem komunikasi dengan penyandian kanal tunggal, dengan penyandian tunggal yang digunakan adalah sandi konvolusi.

295

ISSN: 2085-6350 ISBN: 978-602-71396-1-9


Gambar 3. Perbandingan unjuk kerja antara convolutional codes dengan good convolutional codes untuk L = 3 dan L = 7

CITEE 2014

Gambar 6. Perbandingan unjuk kerja untuk L = 6 antara convolutional codes (56,75) dengan good convolutional codes (53,75)

Hasil selengkapnya untuk L = 4, 5, dan 6 dapat dilihat berturut-turut pada Gambar 4, Gambar 5, dan Gambar 6. Semua hasil simulasi menunjukkan bahwa good convolutional codes memberikan kemampuan koreksi galat yang lebih baik dibandingkan dengan sandi konvolusi yang dipilih secara acak.

Gambar 7. Perbandingan unjuk kerja antara convolutional codes dengan good convolutional codes untuk L = 3, 4, 5, 6, dan 7



296

Untuk good convolutional codes masing-masing panjang kekangan, terlihat bahwa semakin besar nilai panjang kekangan, maka kemampuan koreksi galat good convolutional codes akan semakin baik. Hal ini dikarenakan, semakin besar nilai panjang kekangan, maka semakin banyak pula diagram keadaan yang dibentuk pada proses pengawasandian. Diagram keadaan yang semakin banyak akan mengurangi peluang terjadinya kesalahan pada proses pengawasandian. Hasil simulasi dapat dilihat pada Gambar 7. B. Unjuk kerja penyandian bertingkat RS-CC dengan good convolutional codes Pada skenario ini good convolutional codes digandeng dengan sandi RS(255,239) sehingga membentuk skema penyandian bertingkat RS-CC dengan sandi konvolusi sebagai penyandi dalam (inner coding) dan sandi RS sebagai penyandi luar (outer coding). Penambahan sandi RS pada skema penyandian menghasilkan kemampuan koreksi galat yang jauh lebih baik dibandingkan dengan skema penyandian tunggal menggunakan sandi konvolusi. Efek penambahan sandi RS pada good convolutional codes untuk L = 3 dan L = 7 dapat dilihat pada Gambar 8. Perbaikan kemampuan koreksi galat terjadi karena sandi RS menutupi kelemahan yang dimiliki


CITEE 2014


ISSN: 2085-6350 ISBN: 978-602-71396-1-9

oleh sandi konvolusi, yaitu kelemahan dalam hal menangani galat tipe deburan (burst error).

Gambar 10. Perbandingan antara skema RS-CC dengan convolutional codes terhadap skema RS-CC dengan good convolutional codes untuk L = 4 Gambar 8. Perbandingan skema penyandian tunggal sandi konvolusi dengan skema penyandian bertingkat RS-CC untuk L = 3 dan L = 7

Selanjutnya ditinjau perbandingan kemampuan good convolutional codes yang digandeng dengan sandi RS terhadap sandi konvolusi terpilih acak yang digandeng dengan sandi RS. Hasilnya menunjukkan bahwa sandi RS yang disusun bertingkat dengan good convolutional codes memiliki kemampuan koreksi galat yang lebih baik jika dibandingkan dengan sandi RS yang dirangkai serial dengan sandi konvolusi yang dipilih secara acak. Hal ini disebabkan karena pada dasarnya good convolutional codes sudah memiliki kemampuan koeksi galat yang lebih unggul, sandi RS hanya menutupi kelemahan dalam hal menangani galat yang berupa galat tipe deburan (burst error). Untuk hasil simulasi skema penyandian bertingkat RS-CC dengan good convolutional codes untuk panjang kekangan L = 3, 4, 5, 6, dan 7 secara berturut-turut dapat dilihat pada Gambar 9, Gambar 10, Gambar 11, Gambar 12, dan Gambar 13.

Gambar 11. Perbandingan antara skema RS-CC dengan convolutional codes terhadap skema RS-CC dengan good convolutional codes untuk L = 5

Gambar 12. Perbandingan antara skema RS-CC dengan convolutional codes terhadap skema RS-CC dengan good convolutional codes untuk L = 6 Gambar 9. Perbandingan antara skema RS-CC dengan convolutional codes terhadap skema RS-CC dengan good convolutional codes untuk L = 3


297

ISSN: 2085-6350 ISBN: 978-602-71396-1-9


CITEE 2014

VI. KESIMPULAN DAN SARAN

Gambar 13. Perbandingan antara skema RS-CC dengan convolutional codes terhadap skema RS-CC dengan good convolutional codes untuk L = 7

Pada penelitian kali ini diperoleh hasil bahwa good convolutional codes memiliki kemampuan koreksi galat yang lebih handal jika dibandingkan dengan sandi konvolusi yang dipilih secara acak untuk kanal komunikasi AWGN. Kehandalan good convolutional codes juga tampak dalam skema penyandian bertingkat RS-CC. Penelitian ini adalah penelitian empiris, artinya asumsi yang digunakan adalah good convolutional codes pada sistem penyandian tunggal akan menjadi good convolutional codes juga pada sistem penyandian bertingkat RS-CC. Perlu dilakukan kajian teoritis dan matematis untuk menyimpulkan apakah good convolutional codes yang digunakan pada penelitian kali ini adalah sandi konvolusi yang paling “baik” untuk skema penyandian bertingkat RS-CC. UCAPAN TERIMA KASIH Terima kasih penulis ucapkan kepada Biro Perencanaan dan Kerjasama Luar Negeri, Sekretariat Jenderal Kementerian Pendidikan dan Kebudayaan sebagai pengelola Program Beasiswa Unggulan Fast-Track.

[1]

[2]

Gambar 14. . Perbandingan antara skema RS-CC dengan good convolutional codes untuk L = 3, 4, 5, 6, dan 7

Untuk skema penyandian bertingkat RS-CC dengan good convolutional codes, untuk masing-masing panjang kekangan, terlihat bahwa semakin besar nilai panjang kekangan, maka kemampuan koreksi galat dari skema penyandian bertingkat RS-CC. Hal ini seperti yang telah dijelaskan pada sub-bab sebelumnya. Hasil simulasi selengkapnya dapat dilihat pada Gambar 14.

[3]

[4] [5]

[6]

[7]

298

REFERENSI X. Liu, X. Sun, M. Jiang, and C. Zhao, “The Performance of RS-CC Concatenated Codes for the Relay Channel in WiMAX System,” in International Conference on Wireless Communications & Signal Processing, 2009, pp. 1–5. M. D. Hassib, J. Mandeep, M. Abdullah, M. Ismail, R. Nordin, and M. Islam, “Improved Concatenated (RS-CC) for OFDM Systems,” IEICE Electron. Express, vol. 9, no. 6, pp. 538–543, 2012. G. A. Hussain, M. B. Mokhtar, and R. S. A. B. Raja, “Concatenated RS-Convolutional Codes for MIMO-OFDM System,” Asian J. Appl. Sci., vol. 4, no. 7, pp. 720–727, 2011. W. G. Chambers, “On Good Convolutional Codes of Rate 1/2, 1/3, and 1/4,” 1992. J. Chang, D. Hwang, and M. Lin, “Some Extended Results on the Search for Good Convolutional Codes,” IEEE Trans. Inf. Theory, vol. 43, no. 5, pp. 1682–1697, 1997. S. Benedetto, R. Garello, and G. Montorsi, “A Search for Good Convolutional Codes to be Used in the Construction of Turbo Codes,” IEEE Trans. Commun., vol. 46, no. 9, pp. 1101–1105, 1998. B. Sklar, Digital Communications: Fundamentals and Applications, 2nd ed. New Jersey: Prentice-Hall, 2001.


Evaluasi Unjuk Kerja Good Convolutional Codes pada Skema Penyandian Bertingkat RS-CC

Recommend Documents