Pendahuluan

Error Control Coding

- Bagian ini membahas perencanaan code untuk mengirimkan informasi
dalam bentuk digital melalui kanal yang bernoise

- Code dapat diperbaiki atau hanya dideteksi kesalahannya tergantung

pada banyaknya redundancy didalam code

- Code yang dapat dideteksi kesalahannya dinamakan error-detecting

codes
1
 Pendahuluan
Error Control Coding
- Code yang dapat diperbaiki kesalahannya dinamakan error
correction codes

- Error control codes diklasifikasikan kedalam block codes dan

convolutional codes

- Code dibuat dalam bentuk code biner untuk setiap huruf yang
terdiri hanya dua elemen: “0” dan “1”

- Set {0,1} dinotasikan sebagai K

2
 Channel Coding
A. Channel Coding
- Blok diagram dasar untuk channel coding seperti pada
gambar berikut:

- Deretan pesan biner pada input dari cahnnel encoder akan

menghasilkan output pada source encoder

3
 Channel Coding
A. Channel Coding
- Channel encoder tersebut memberikan sistematik redundancy
kedalam aliran data dengan menambahkan bit-bit ke bit-bit
pesan yang berfungsi untuk deteksi dan koreksi dari bit yang
error untuk pesan yang diterima

- Channel decoder pada receiver memanfaatkan redundancy

tersebut untuk menentukan bit-bit pesan yang mana yang
sesuai dengan yang dikirim

- Kombinasi dari channel encoder dan decoder adalah untuk

meminimisasi effect dari channel noise

4
 Channel Coding
B. Theorema Channel Coding

- Theorema channel coding untuk DMC adalah sebagai berikut:

- Sebuah DMS X dengan entropy H(X) bits/symbol dan DMC

dengan kapasitas Cs bits/symbol

- Bila H(X)  Cs , maka coding yang berasal dari source output

dapat dikirimkan melalui channel dengan probabilitas kesalahan
yang kecil

- Bila H(X) > Cs , maka tidak memungkinkan untuk ditransmisikan

melalui channel dengan probabilitas kesalahan yang kecil

5
 Block Codes
- Block code merupakan sebuah code yang mempunyai
words dengan panjang sama
- Dalam block codes pesan biner atau deretan data dibagi
dalam deretan block dengan panajang setiap block
sebesar k bits
- Setiap k bits block dikonversi dalam n-bit block, dimana
n>k
- Hasil dari block code dinamakan (n, k) block code
- k-bit block mempunyai 2k deretan pesan yang berbeda
direferensikan sebagai k-tuples

6
 Block Codes
- n-bit block dapat berbentuk sebanyak 2n deretan tertentu
direferensikan sebagai n-tuples

- Sebuah set dari semua n-tuples didefinisikan melalui K={0,1}

dinotasikan dengan Kn

- Mapping dari channel encoder adalah:

T: UV
dimana U merupakan sebuah set data word biner dengan panjang k dan
V merupakan sebuah set dari code word biner dengan panjang n
dengan n > k

- setiap 2k data word dimapping kedalam code word yang unik

7
 Matrix Desription pada Linier Code

- Sebuah (n, k) linier code secara lengkap merupakan

generator matrik G dimensi k x n
- Setiap baris dari G merupakan sebuah n-tuple melalui
GF(2) dan setiap kolom merupakan k-tuple melalui GF(2)
- Bila deretan baris dari G merupakan sebuah set dari
basis vektor untuk k-dimensi, maka kode word c
merupakan kombinasi linier dari baris G didasarkan pada
informasi data d=(d0, d1, …, dk-1) sehingga:

c=d0g0 + d1g1 + … + dk-1gk-1

8
 Matrix Parity Check

-Misal C merupakan sebuah (n, k) linear code merupakan semua

linier (n,k), code tersebut adalah dual code CD dengan dimensi (n-k)

- Dual code merupakan linier (n, n-k) code dengan 2n-k code word

- Dual code merupakan null space dari linier (n, k) code.

- Generator matrik untuk dual code dinotasikan dengan H yang

terdiri dari (n-k) linier independen vektor yang merupakan semua
vektor pada baris dari G adalah orthogonal terhadap baris H.

- Matrik H dinamakan parity check matrik linier code C.

- Matrik ini merupakan sebuah (n-k) x n matrik dari barisan n-k

- Sebuah n-tuple c merupakan code word jika dan hanya jika

9
orthogonal untuk setiap baris vektor pada H
 Matrix Parity Check

- Sehingga:
c . HT = 0

dimana 0 merupakan notasi baris vektor semuanya nol dengan

n-k elemen

- Disini adalah untuk mengetahui kebenaran dari word apakah

merupakan kode vektor

- Bila c . HT = 0 dipertahankan untuk setiap code word dari

(n,k) code, maka akan diperoleh:

G . HT = 0

dimana 0 sekarang menjadi matrik k x (n-k) dengan semua elemen

nol
10
 Matrix Parity Check

- Bila matrik generator G merupakan code sistematik (n,k) dengan

bentuk seperti berikut:

maka, matrik parity check akan mempunyai bentuk:

dimana, PT adalah
transpose submatrix P

11
 Matrix Parity Check

- Untuk semua k x n matrik generator G dengan baris g0, g1, …, gk-1

adalah linier independen, dan (n-k) x n matrik parity check H
dengan baris h0, h1, …, hn-k-1 adalah linier independen juga, maka
inner product semua baris gi dalam G dan semua baris hj dalam H
harus nol

- Sebagai contoh gi . Hj = 0 untuk 0 i  k-1 dan 0 j  n-k-1

12
 Contoh

- Sebuah (7, 4) linier code dengan matrik generator:

Vector informasi d = (0 1 1 0) merupakan salah satu encode

sistematik dalam codeword sehingga:

13
 Contoh

- Sehingga diperoleh tabel code word sbb:

Tabel disamping
menampilkan 16 code word
yang berhubungan dengan
24 = 16 word informasi

14
Contoh

Berdasarka persamaan c . HT = 0 , maka matrik parity check untuk

code (7, 4) adalah:

15
Implementasi EncoderLinier Block Code

- Berdasarkan pembahasan sebelumnya hubungan data informasi

dengan code word dapat digunakan prosedur encoding melalui
persamaan:
c = d . G

dimana d adalah k-tuple deretan informasi untuk encode dan c

berhubungan dengan n-tuple codeword

- Bila persamaan encoding digunakan untuk mendefinisikan encoder,

pasangan antara d dan c bergantung pada pilihan dasar vector yang
merupakan baris dari G

16
Implementasi EncoderLinier Block Code

- Berdasarkan dua persamaan berikut:

encoder (n, k) linier sistematik code dapat diimplementasikan

dengan mudah
17
 Implementasi EncoderLinier Block Code

- Hasil dari struktur sistematik, deretan informasi d = (d0, d1, …, dk-1)

digeser kedalam channel untuk reproduksi bit-bit informasi dan pada
waktu yang bersamaan digeser didalam shift register dengan format
n-k bit-bit parity check

- Kemudian deretan serial bit-bit redundancy digeser didalam channel

menghasilkan bentuk code word sistematik

18
 Contoh

- Sebuah code linier (7, 4) mempunyai generator matrik:

bila d = (d0, d1, d2, d3) merupakan bit-bit informasi untuk encoding,
berdasarkan persamaan (3.4), n – k parity check bit I, i=0, 1, 2
Diexpresikan dengan:

19
 Contoh

Berdasarkan persamaan tersebut, encoder untuk (7, 4) code dapat

diimplementasikan seperti gambar berikut:

Dalam gambar diatas, sistematik codeword dikirimkan ke channel

c = (0, 1, 2, d0, d1, d2, d3)

20
 Contoh

Sebagai contoh, bila deretan informasi d = (0 1 1 0) digeser didalam

shift register, kemudian n – k = 3 parity check digit diformat pada
Output dari n – k = 3 penambahan modulo 2.
Dengan 0 = 1, 1 = 0, 2 = 0, maka bentuk code word c = (1 0 0 0 1 1 0)

21
 Syndrome

- Bila c = (c0, c1, …, cn-1) merupakan code word yang ditransmisikan

- Dan r = (r0, r1, …, rn-1) merupakan output demodulator

- Word r mungkin sama atau tidak sama dengan c tergantung pada

noise yang terdapat pada channel

- Bila r  c, maka r = c + e, dimana,

e = r +c
= (e0, e1, …, en-1)

dan e dinamakan n-tupple error pattern

- Dengan adanya hal tersebut, word r yang diterima akan dilakukan

proses decoder untuk memulai menghitung syndrome untuk menda-
patkan lokasi kesalahan dan membetulkan kesalahan
22
 Syndrome

- Syndrome dinotasikan sebagai s terhadap r dengan (n-k) vektor

dengan persamaan sbb:
s = r . HT
= (s0, s1, …, sn-k-1)

- Bila r merupakan penjumlahan vektor dari c dan e, maka:

s = (c + e)HT = e . HT
karena c . HT = 0

menunjukkan hubungan antara syndrome dan error pattern

- Parity check matrik digunakan untuk menentukan jumlah kesalahan
yang tergantung pada error pattern e

- Pemakaian syndrome berdasar pada bentuk error detection dan

error correction

- Lebih jelasnya adalah untuk s = 0 jika dan hanya jika e = 0 23

 Syndrome

- Bila s  0, maka r bukan merupakan code word dan menunjukkan

terdapat error yang kemungkinan dapat dideteksi

Contoh

Sebuah linier code (7,4) dengan parity check matrik sbb:

bila r = (1 1 1 0 0 1 0) vektor yang diterima, maka syndrome dapat

diperoleh:

24
 Lanjutan Contoh
Secara umum bahwa untuk word r = (r0, r1, …, rn-1), diperoleh sindrome:

Sehingga bit-bit sindrome adalah:

25
 Lanjutan Contoh
Sehingga untuk r0=r1=r2=1 , r3=r4=0 , r5=1 dan r6=0 maka vektor
syndromenya adalah s0=0, s1=0 dan s2=1.
Implementasi rangkaian untuk problem contoh ini adalah sebagai
berikut:

26
 Contoh
Sebuah linier code (6,3) dengan parity check matrix sbb:

Bila c = (1 1 0 0 1 0) code word yang dikirim dan r = (1 1 0 1 1 0) word

yang diterima. Dengan kondisi tersebut, decoder akan menghasilkan
Syndrome sbb:
s = r . HT = (1 0 1)

Decoder dapat menentukan error pattern e = (e0, e1, …, e5) mengguna-

Kan persamaan sebelumnya:

27
 Contoh
Dengan n-k =3 maka mempunyai kemungkinan 2k = 8, bila diasumsikan
e3 e4 e5 dipilih sebagai kolom pertama dari tabel berikut, dan e0 e1 e2
merupakan kolom kedua, maka akan diperoleh error pattern sbb:

Bila menggunakan BSC channel berdasarkan minimum weight element

maka dipilih error pattern sebagai contoh e =(0 0 0 1 0 0) yang mungkin.
Salah satu error pattern e telah diperoleh untuk digunakan dalam per-
samaan vektor r + e sehingga bisa diperoleh code word yang diterima
sesuai dengan code word yang dikirim. 28
 Contoh
Menggunakan error pattern e = (0 0 0 1 0 0) yang merupakan error
pattern yang benar, maka decoder akan mengkodekan kembali
r = (1 1 0 1 1 0) menjadi code word yang benar sbb:

29
 Contoh
1. Suatu kode Hamming (7.4) memiliki generator matrix.

Bila data yang diberikan oleh sumber data adalah d = 1 0 0 0

Tentukanlah kode setelah melalui encoder.

30
 Penyelesaian
Kode Hamming merupakan hasil perkalian Matrix antara data dan
generator. Sehingga diperoleh :

C = [d] [G]

C=[1101000]

31
 Contoh
2. Suatu kode Hamming (7,4) memiliki parity check

Bila kode yang dikirim adalah r = 1 1 0 1 0 0 0 tentukanlah data

yang dikirimkan. Tentukanlah apakah kode yang dikirim tersebut
terkena error ?

32
 Penyelesaian
Sindrom dari kode yang diterima :

S = [r] [HT]

Dimana r = kode yang diterima, HT Transposisi Pariti Check Matrix.

S= 0 0 0 33
 Penyelesaian

Karena Sindrom bernilai nol, maka kode yang dikirim tersebut

tidak terkena error. Sehingga diperoleh r = [ 1 1 0 1 0 0 0 ]
Untuk memperoleh data yang dikirim, maka dikeluarkan pariti di
depan, sehingga diperoleh data d = 1 0 0 0

34
 Contoh

3. Kode Hamming (7,4) yang memiliki generator seperti soal no. 1

dan parity check seperti no. 2. Bila kode yang diterima adalah 1
1 0 0 0 0 0 Buatlah data yang dikirimkan.

35
 Penyelesaian

Sindrom dari kode yang diterima :

S = [r] [HT]

S = [ 1 1 0]

36
 Penyelesaian

Karena sindrom tidak bernilai nol, maka ada error terdeteksi.

Kemudian dilakukan pencarian posisi error. Untuk ini dilakukan
transposisi pada sindrom yakni baris menjadi kolom.

Setelah itu ditentukan posisi ke berapa sindrom tersebut pada

kolom parity check, diperoleh sindrom tersebut berada pada kolom
ke empat. Langkah berikutnya adalah mengkoreksi bit-bit yang
terkena error. Yakni dengan cara menginvert nilai dari kode yang
diterima, bila 0 menjadi 1 pada kolom yang terkena error.
Kode yang diterima r = 1 1 0 0 0 0 0
Maka kode yang dikirimkan adalah r = 1 1 0 1 0 0 0. Setelah bit
pariti dikeluarkan, maka diperoleh data d = 1 0 0 0.
37
 KODE BCH

Algoritma pengkodean kode BCH

- bit stream dari sumber data yang masuk ke encoder dikodekan
dengan menggunakan suatu generator

- proses pengkodean kode BCH diperlukan suatu generator

Generator
- kode yang dipergunakan adalah kode BCH ( 15.7 )
- kode BCH dapat diperoleh dari hasil perkalian antara bit stream
dengan generator matriks kode Hamming
- diperlukan suatu generator matriks
- dipilih kode BCH yang sistematik
- bentuk umum generator matriks dari kode BCH yang sistematik
dengan bit-bit parity didepan

G = [ Pk x (n-k) Ik ]
38
 KODE BCH

- dimana panjang baris menentukan banyak bit dalam satu blok

data dan panjang kolom menentukan panjang kode dalam satu
blok kode
- Generator matriks kode BCH ini disimpan pada array 2 dimensi

39
 KODE BCH

Generator matriks dari kode BCH (15,7) adalah :

40
 KODE BCH
Algoritma Pembentukan Kode BCH
- Algoritma pembentukan kode BCH dimulai dengan mengambil
sebanyak k bit data dimana k adalah banyaknya bit dalam satu
blok data pada kode BCH.

- Kemudian k bit tersebut dikalikan dengan generator matriks.

Hasilnya merupakan kode BCH

- Proses dimulai dengan membuat inisialisasi pada mark data dan

mark code dengan nilai nol. Proses selanjutnya mengambil bit-
bit data sebanyak k bit, kemudian bit-bit tersebut dikalikan
dengan generator matriks. Hasilnya adalah kode BCH. Kode ini
disimpan pada array kode.

- Untuk pengkodean blok kode berikutnya, diambil k bit

berikutnya. Pada saat pengambilan k bit berikutnya maka angka
markdata bertambah sebanyak k bit. Bila markdata lebih besar
41
dari nbit-k maka proses pengkodean selesai.
 KODE BCH

Diagram Alir
Pembentukan kode BCH

42
 KODE BCH
Algoritma Pengkodean
Proses pengdekodean mempunyai tujuan untuk memperbaiki tujuan
untuk memperbaiki kesalahan dan menghilangkan bit-bit pariti.

Algoritma Pengdekodean Kode BCH

Algoritma pengkodean dari bit stream yang diterima oleh sistem
penerima dengan menggunakan kode BCH, dipilih algoritma
Peterson Berlekamp.

43
 KODE BCH
Langkah-langkah algoritma pengdekodean kode BCH (15,7) dengan
kemampuan koreksi kesalahan 2 adalah sebagai berikut.

1. Hitung sindrom S1 dan S3.

2. Hitung error locator σ dan susun error locator polinominal σ
(x).
3. Cari posisi error.
4. Perbaiki bit yang terkena error.
5. Selesai.

44
 KODE BCH

Diagram Alir Pembentukan

kode BCH (15,7)

45
 KODE BCH

- Dengan mengacu pada diagram alir kode BCH (15,7) yang

sistematik, proses dimulai dengan membuat inisialisasi pada
markdata dan markcode dengan nilai nol.
- Proses selanjutnya adalah mengambil 15 bit data.
- Kemudian sindrom dihitung dengan persamaan berikut:
S1= r0 + r1α + r2α2 + … + r14 α14
S3= r0 + r1(α3)1 + r2(α3)2+ … + r14 (α3)14

- Jika sindrom pertama ( S1) dan sindrom ketiga ( S3 ) sama dengan

nol, decoder tidak melakukan pengkoreksian
- Kemudian bit-bit pariti dibuang dan bit-bit data disimpan pada
array

46
 KODE BCH
- Bila S1 dan S3 tidak sama dengan nol, susun error locator
polinomial.
σ (x ) = 1+ σ1x + σ2x2
dimana:
S3
 1  S1 ; 2  S 1
2

S1
- Kemudian dicari posisi error, dengan cara menginvers harga akar-
akar persamaan

- Misalnya diperoleh akar-akar persamaan adalah 4 dan 5 maka

posisi kesalahan adalah 1/ 4 = -4 , ini berarti mundur 4 baris
dari bit ke 15, dan pada 1/ 5 = -5 berarti mundur 5 baris dari
bit ke 15, sehingga diperoleh posisi error pada bit ke 11 dan bit
ke 10
47
 KODE BCH
- Proses selanjutnya adalah memperbaiki bit yang salah pada posisi
error tersebut, dengan cara bit yang ada pada posisi tersebut
diganti
- Bila sebelumnya Bit 0 maka menjadi bit 1dan bit 1 menjadi bit 0
- Setelah error diperbaiki maka bit-bit dikeluarkan. Kemudian bit-
bit data disimpan pada array
- Diagram alir pengkodean satu blok kode diperlihatkan dalam garis
putus-putus
- Untuk pengkodean blok kode berikutnya diambil n bit berikutnya
- Pada saat pengambilan n bit berikutnya maka angka mark code
bertambah sebanyak n bit
- Bila markcode lebih besar dari n bit – n maka proses pengkodean
selesai
48
 KODE BCH

Diagram Alir Pengkodean kode BCH

49
 Contoh

1. Suatu kode BCH (15,7) memiliki generator matrix :

Bila data yang diberikan oleh sumber data adalah d = 1 0 0 0 0 0 0

tentukanlah kode, setelah melalui enkoder

50
 Penyelesaian
Kode BCH merupakan hasil perkalian matrix antara data dan
generator, sehingga diperoleh :

51
 Contoh

2. Suatu dekoder BCH (15,7) menerima kode : r = 1 0 0 0 1 0 1 1 1

0 0 0 0 0 0. Tentukanlah data yang dikirim oleh sumber.

52
Penyelesaian

53
 Penyelesaian
Untuk memperoleh S1 ubah notasi eksponensial ke notasi binari dan
jumlahkan dengan modulo 2

Sehingga diperoleh S1 = 0 0 0 0, kemudian diubah kembali ke notasi

exponensial, maka S1 = 0, ini berarti tidak ada error.

Kemudian dicari S3

54
 Penyelesaian
α yang lebih besar daripada pangkat 15 harus dikurangi dengan 15.
Sehingga diperoleh :

S3 = 0 0 0 0, kemudian diubah ke notasi exponensial sehingga S3 = 0

S1 dan S3 = 0, maka tidak ada terdeteksi error

Bila sindrom = 0, maka bit pariti dikeluarkan, dalam hal ini 8 bit dari
depan, sehingga data yang diperoleh adalah :

d=1000000 55
 Contoh
3. Bila kode yang diterima r = 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0.
Tentukanlah kode dan data yang dikirimkan.

Bila terjadi S3 = (S1)3, maka untuk mencari posisi error langsung pada
sindrom 1 (S1) yaitu α4. 56
 Penyelesaian

Perbaiki bit yang terkena error dengan menginvert bit tersebut

sehingga diperoleh kode yang dikirimkan adalah :

C=100010111000000

dan data yang dikirim adalah :

d=1000000

57
 Contoh

4. Bila kode yang diterima r = 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0.

Tentukanlah kode dan data yang dikirimkan.

58
Penyelesaian

59
Penyelesaian

60
Penyelesaian
Cari dari i = 1 sampai dengan 15, bila tidak ada akar yang lain,
berhenti.
Dilakukan pencarian posisi error. Posisi error diperoleh dengan
mengurangi pangkat akar-akar dengan 15, sehingga :
Posisi error I = 15 – 1 = 14
Posisi error II = 15 – 3 = 12
Jadi error terjadi pada bit ke 12 dan ke 14.
Untuk memperbaiki bit yang terkena error, pada posisi bit yang
terkena error dilakukan invert, bila bit 1 menjadi 0 dan sebaliknya.
Sehingga diperoleh kode yang dikirimkan :

r = 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 menjadi

C=100010111000000

Untuk memperoleh data, bit pariti dikeluarkan sebanyak 8 bit dari

depan sehingga diperoleh data :
d=1000000 61
 KODE REED SOLOMON

Algoritma pembentukan Kode Reed Salomon

- Algoritma pembentukan kode Reed Salomon ( 15,11 ) dimulai
dengan mengambil k bit data sebanyak 44 bit
- Kemudian 44 bit ini, diubah kedalam bentuk simbol dimana tiap 4
bit menjadi satu simbol
- Dari 44 bit diperoleh 11 simbol. Kemudian simbol tersebut
dikalikan dengan generator polinomial. Hasilnya adalah kode Reed
Salomon

62
KODE REED SALOMON

Diagram Alir
Pembentukan Kode Reed
Salomon

63
 KODE REED SALOMON

- Dengan mengacu diagram alir proses dimulai dengan membuat

inisialisasi pada markdata dan markcode dengan nilai nol

- Proses selanjutnya mengambil 44 bit data dan diubah kedalam

bentuk simbol kemudian dikalikan dengan generator polinomial

- Hasil perkaliannya adalah kode Reed Salomon

- Hasil pengkodean yang masih dalam bentuk simbol, diubah

menjadi bentuk binary (bit), kemudian disimpan pada array kode

- Pada diagram alir, pengkodean satu blok kode diperlihatkan

berada dalam garis putus-putus

64
 KODE REED SALOMON

- Untuk pengkodean blok kode berikutnya , diambil 44 bit

berikutnya

- Pada saat pengambilan 44 bit berikutnya maka angka markdata

bertambah sebanyak 44 bit

- Bila markdata lebih besar dari nbit-k maka proses pengkodean

selesai

65
 KODE REED SALOMON

Algoritma Pengdekodean kode Reed Salomon

- Algoritma pengdekodean dari bit stream yang diterima oleh

sistem penerima dengan menggunakan kode reed Salomon

- Dipilih algoritma Peterson Gorenstein Zieler

Langkah – langkah dari algoritma adalah sebagai berikut:

1. Hitung sindrom dari bit stream yang telah melalui saluran
transmisi.
2. Susun matriks sindrom P.
3. Hitung determinan matriks sindrom. Jika determinan tidak nol,
lakukan langkah 5.
4. Jika determinan nol, susun matriks sindrom yang baru, dengan
cara menghapus kolom paling kanan dan baris paling bawah dari
sindrom yang lama. 66
 KODE REED SALOMON

5. Hitung error locator σ dan susun error locator polinomial σ ( x ).

6. Hitung akar – akar persamaan error locator polinomial.
7. Hitung error magnitude
8. Susun error polinomial
9. Jumlahkan error polinomial dengan kode yang diterima.
10. Selesai

67
 KODE REED SALOMON

Diagram alir pengdekodean kode

Reed Salomon ( n,k ) seperti
gambar disamping

68
 KODE REED SALOMON

- Dengan mengacu pada diagram alir pengdekodean kode Reed

Salomon (15,11)

- proses dimulai dengan membuat inisialisasi pada markdata dan

markcode dengan nilai nol

- Proses selanjutnya adalah mengambil sebanyak 60 bit data

- Kode yang diterima diubah kedalam bentuk simbol dimana tiap 4
bit menjadi satu simbol

- Sehingga dari 60 bit menjadi 15 simbol

- Kemampuan koreksi kesalahan dari kode Reed Salomon ( 15,11 )

adalah 2

- Banyaknya sindrom adalah dua kali kemampuan koreksi kesalahan

69
 KODE REED SALOMON
- Sehingga sindromnya ada sebanyak 4, yang dihitung dengan
persamaan berikut:

Dimana :

R= Simbol kode yang diterima

α = anggota dari GF(24)
- Kemudian sindrom S1, S2, S3, S4 diuji
- Jika semuanya nol, berarti tidak ada error terdeteksi
- Decoder tidak melakukan pengkoreksian. Kemudian bit- bit pariti
dibuang dan bit-bit data disimpan pada array 70
 KODE REED SALOMON
- Jika sindrom tidak sama dengan nol, hitung determinan matriks P
dimana:

- Ada dua kasus yaitu, untuk determinan sama dengan nol dan
determinan tidak sama dengan nol

Determinan sama dengan nol

- hitung error locator σ dengan menggunakan persamaan :

- Selanjutnya hitung error magnitude ei1 dengan menggunakan

persamaan :

71
 KODE REED SALOMON
- kemudian disusun error polinomial e(x).

- Untuk memperoleh kode yang sebenarnya c (x), jumlahkan kode

yang diterima r(x) dengan error polinomial e(x)

c(x) = r (x) + e (x)

- Setelah kode diperoleh, maka bit-bit pariti dibuang,kemudian

bit-bit data disimpan pada array

72
 KODE REED SALOMON
Determinan tidak sama dengan nol
- susun error locator polinomial dengan menggunakan persamaan

- Kemudian dicari akar-akar persamaan, Yaitu β1 dan β2

- Selanjutnya akar-akar persamaan di invers sehingga diperoleh 1-1

dan 2-2

- Kemudian dihitung error magnitude ei1 dan ei2 dengan menggunakan

persamaan:

73
 KODE REED SALOMON
- Setelah diperoleh harga kesalahan ei1 dan ei2 maka disusun error
polinomial e (x)

- Untuk memperoleh kode yang sebenarnya, jumlahkan kode yang

diterima r(x) dengan error polinomial e(x) adalah:

C (x) = r (x) + e (x )

- Setelah kode diperoleh, bit-bit pariti dibuang. Kemudian bit-bit

data disimpan pada array

74
Contoh
1. Suatu kode Reed Salomon (15, 11), memiliki generator polinominal :
g (x) = α10 + α3 x + α6 x2 + α13x3 + x4
Bila data yang diberikan oleh sumber adalah :
d = 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
Tentukanlah kode, setelah melalui enkoder

Penyelesaian :

Data yang masuk, yang masih merupakan notasi binari diubah ke

notasi eksponensial sehingga :
d= α0 0 0 0 0 0 0 0 0 0
Dari generator polinominal tersebut dapat dibuat persamaan
enkoder untuk RS (15,11)

75
Penyelesaian

R0, R1, R2 dan R3 adalah register

76
Penyelesaian

77
Penyelesaian

78
 Penyelesaian
Sehingga diperoleh isi register pada saat t = 1 atau pada saat data 1,
telah di encode.
R0(11) = α11 ; R1(11) = α4 ; R2(11) = α7 ; R3(11) = α14
Ini merupakan parity yang diletakkan di depan sehingga kode yang
dikirimkan :
R0(11) R1(11) R2(11) R3(11) d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 d11
Dalam simbol : α11 α4 α7 α14 α 0 0 0 0 0 0 0 0 0 0 0
Dalam bentuk binari : 0111 1100 1101 1001 0100 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000

79
Contoh
2. Suatu dekoder Reed Salomon (15,11) menerima kode r = 0111 1100
1101 1001 0100 0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 Dengan generator polinominal seperti contoh no. 1.
Tentukanlah data yang dikirim oleh sumber.

Penyelesaian :

80
Penyelesaian :

81
Penyelesaian :

Sindrom-sindrom yang diperoleh :

S1 = 0 S2 = 0 S 3 = 0 S 4 = 0
Bila S1, S2, S3, S4 = 0 maka tidak ada error terdeteksi.
Kirimkan data.
Sebelum data dikirimkan ubah ke bentuk binary.
Data yang dikirim, telah dibuang paritinya, yaitu 16 bit di depan
(4 simbol).
Sehingga diperoleh data yang dikirim oleh sumber :
0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

82
Contoh
3. Suatu dekoder Reed Salomon (15,11) menerima kode
r = 0011 1100 1101 1001 0100 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000
Tentukan data yang dikirim oleh sumber
Penyelesaian :

83
 Penyelesaian :
II. Susun Matrix Sindrom

III. Hitung Determinan dari matrix Sindrom

84
 Penyelesaian :
Maka diperoleh error locator polinominal = 
Karena hanya ada 1 error locator polinominal Λ1 = 
Maka error locator (lokasi error) hanya 1, yaitu pada  tersebut.
Jadi  merupakan error locator  x1.
Kemudian langkah berikutnya mencari besaran error (error
magnitude)

85
 Penyelesaian :
langkah berikutnya mencari error polinominal.
e(x) =  . x1

Kemudian e (x) dibuat ke binary :

e = 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000

r = 0011 1100 1101 1001 0100 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000

C = e+r = 0111 1100 1101 1001 0100 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000

Maka diperoleh data yang dikirimkam sumber adalah :

0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

86
Contoh
4. Suatu dekoder Reed Salomon (15,11) menerima kode r = 0011 1100
1101 1001 0000 0000 0000 0000 0000 0000 0000 0000 0000
0000 0000.
Tentukan data yang dikirim oleh sumber.
Penyelesaian :

87
Penyelesaian :

II. Buat Matrix Sindrom

88
 Penyelesaian :
III. Hitung Determinan

IV. Mencari error locator Polinominal

4.2. Buat adjoint matrix, dengan cara transposisi, matrix Ac (Baris

jadi kolom, kolom jadi baris).

89
Penyelesaian :
4.3. Cari invers matrix, dengan cara mengalikan dengan adjoint
matrix dengan reciprocal determinan A (harga mutlaknya).

90
Penyelesaian :
V. Mencari akar-akar error locator polinomial

VI. Mencari posisi error

91
Penyelesaian :
VII. Mencari besaran error (error magnitudes)

7.2. Hitung determinant

7.3. Hitung cofaktor dari matrix

92
Penyelesaian :
7.4. Hitung Adjoint A yakni dengan cara membuat baris jadi kolom
dari kofaktor matrix yang diperoleh

7.5. Hitung invers matrix dengan cara mengalikan harga absolut

determinan dengan Adjoint A

93
Penyelesaian :
7.6. Hitung e1 dan e2

94
Penyelesaian :
VIII. Cari error pattern (pola error) e (x)

95
 KODE KONVOLUSI
Algoritma pengkodean kode Konvolusi
- Bit stream dari sumber data yang masuk ke encoder dikodekan
dengan menggunakan suatu generator

- Oleh karena itu dalam proses pengkodean kode Konvolusi diperlukan

suatu generator

Generator
- Kode yang dipergunakan adalah kode Konvolusi ( 2,1,2 )

- Kode Konvolusi merupakan hasil perkalian antara bit stream dengan

generator sekuens oleh karena itu diperlukan suatu generator
sequensial

- Dipilih kode Konvolusi yang non sistematik

96
 KODE KONVOLUSI
Bentuk umum generator sequens dari kode Konvolusi adalah:

- Kode Konvolusi dinotasikan dengan ( n,k,m ) dimana n menyatakan

output, k menyatakan input dan m menyatakan memori

- Generator sequens dari kode konvolusi ( 2,1,2 ) adalah:

97
 KODE KONVOLUSI
Agoritma Pembentukan Kode Konvolusi
- Algoritma pembentukan kode
Konvolusi dapat menggunakan operasi
diagram state

- Pada Kode Konvolusi ( n,k,m ) tiap k

bit data yang masuk pada satu
satuan waktu, keluarannya menjadi n
bit pada satu satuan waktu

- Diagram alir pembentukan kode

konvolusi diperlihatkan oleh gambar
disamping

98
 KODE KONVOLUSI
- Dengan mengacu pada diagram alir
pengkodean kode konvolusi (2,1,2)
gambar disamping

-Proses dimulai dengan membuat

inisialisasi pada state mula dan
markcode dengan nilai nol dan I = 1,
dimana I merupakan penghitung bit

- Proses selanjutnya mengambil k bit

data pada satu satuan waktu

- Kemudian k bit data tersebut

dikodekan dengan operasi diagram
state, yang menggunakan tabel dari
state

99
 KODE KONVOLUSI
- Tabel dibawah memperlihatkan tabel dari state kode Konvolusi
(2,1,2) yang non sistematik

100
 KODE KONVOLUSI
Agoritma Pengdekodean
- Proses pengdekodean mempunyai tujuan untuk memperbaiki
kesalahan dan menghilangkan bit-bit pariti

Algoritma Pengdekodean Kode Konvolusi

- Algoritma pengdekodean dari bit stream yang diterima oleh
sistem penerima dengan menggunakan kode Konvolusi dipilih
algoritma viterbi

- Prinsip dasar algoritma viterbi adalah memilih lintasan yang

mempunyai node minimum

- Dekoder kode Konvolusi dipilih menggunakan Hard decision

decoding

101
 KODE KONVOLUSI
- Diagram alir pengdekodean kode
Konvolusi (2,1,2) diperlihatkan oleh
diagram alir gambar disamping

- Dengan mengacu pada diagram alir

pengkodean kode Konvolusi (2,1,2)
gambar disamping, proses dimulai
dengan membuat inisialisasi pada titik
awal S0 dengan nilai nol

- Proses selanjutnya mengambil set

dari kode yang dikirimkan ( r ) yang
pertama, sebanyak 2 bit

- Kemudian membandingkan set tersebut

dengan set disemua lintasan keluar dari
titik awal tadi, beri nilai nilai yang sama
denganbeda set lintasan dengan set
102
yang diterima
 KODE KONVOLUSI
- Kemudian ditentukan nilai dari node yang
kini dicapai. Besarnya nilai node yang
dicapai diperoleh dengan menjumlahkan
nilai node asal dengan nilai lintasan

- Apabila set dari r belum habis, diambil set

r yang berikutnya sebanyak 2 bit lagi,
kemudian diulangi proses diatas

- Jika satu node dicapai lebih dari satu arah,

sisakan lintasan yang menghasilkan nilai
node minimum

- Kemudian buat lintasan yang dianggap

benar. Lintasan yang dianggap benar,
adalah lintasan yang menghasilkan node
minimum

- Setelah dibuat lintasan yang dianggap 103

benar maka proses pengdekodean selesai
Contoh
1. Kode konvolusi dinotasikan dengan (N, K, M) dimana N adalah
jumlah Adder, K banyaknya input dan M adalah banyaknya memori
atau register. Gambarlah enkoder dari kode konvolusi (2,1,2)
bilamana generator-generatornya adalah G1 = 1 1 0 dan G2 = 0 0 1.
Penyelesaian :

104
Penyelesaian :

105
 Contoh
2. Buatlah tabel State kode konvolusi seperti soal no. 1 diatas.

Penyelesaian :

106
Penyelesaian :

107
Penyelesaian :

108
Penyelesaian :

109
 Contoh
3. Dari tabel state seperti no. 2 diatas gambarlah diagram state :

Penyelesaian :
Buat gambar state seperti berikut ini :

Tarik garis untuk state, yang dimulai

dari state S0, perhatikan input, output
dan state transisinya. State transisi ini
berguna untuk menghubungkan antara
state awal dan state berikutnya.

Untuk S0 = 0 0 dengan input 0 maka output 0 0 dan state

transisi 0 0 , sehingga diperoleh gambar sebagai berikut :

110
 Penyelesaian :
Untuk input 1  output 1 0, dan state transisinya 1 0 sehingga dari
S0 ditarik garis ke S2.

Perhatikan S3 = 1 1
Untuk input 0  output 1 0 dan state transisi 0 1.
Untuk input 1  output 0 0 dan state transisi 1 1

111
 Penyelesaian :
Perhatikan S1 = 0 1
Untuk input 0  output 01 dan state transisi 00.
Untuk input 1  output 1 1 dan state transisi 1 0
Sehingga diperoleh state diagramnya :

112
 Contoh
4. Suatu kode konvolusi (2,12) yang mempunyai state diagram seperti
soal no. 3. Bila data dari sumber data adalah 1 0 1 1 0 0 0 0
Tentukanlah kode yang diterima.
Penyelesaian :
Sesuai dengan state diagram pada soal no. 3 state dimulai dari S0 = 0 0
Untuk S0 = 0 0 ;
Input 1; maka output 1 0; state transisi 1 0 (S2).
Untuk S2 = 1 0
Input 0; maka output 1 1; state transisi 0 1 (S1).
Untuk S1 = 0 1
Input 1; maka output 1 1, state transisi 1 0 (S2)
Untuk S2 = 1 0
Input 1; maka output 0 1; state transisi 1 1 (S3).
Untuk S3 = 1 1
Input 0; maka output 1 0; state transisi 0 1 (S1)
113
Penyelesaian :
Untuk S1 = 0 1
Input 0; maka output 0 1; state transisi 0 1 (S0)
Untuk S0 = 0 0
Input 0; maka output 0 0 ; state transisi 0 0 (S0)
Untuk S0 = 0 0
Input 0; maka output 0 0 ;
Sehingga diperoleh kode adalah :
C = (1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0)

114
 Contoh
5. Suatu kode konvolusi (2,1,2) yang sistematik mempunyai generator
sekuens, g1(1) = ( 1 0 0 ) dan g2(2) = ( 1 1 1 ). Tentukanlah kode yang
dibentuk bila data dari sumber data adalah d = 1 0 1 0 1 dengan
pendekatan matrix skalar.
Penyelesaian :
Diketahui g1(1) = 1 0 0 dan g1(2) = 1 1 1. Baris pertama dari generator
adalah : G = (G0 G1 G2) = ( 1 1 0 1 0 1). Maka, bila data yang keluar dari
sumber d = 1 0 1 0 1, maka kode yang terbentuk adalah :

115
 Contoh
6. Enkoder kode konvolusi (2,1,2), memiliki tabel state dan state
diagram sebagai berikut :

State diagram :

Gambarkan Trellis Diagramnya. Bila kode

yang diterima r = (11, 01, 00, 10, 10, 11, 00,
00) Tentukan data yang diberikan oleh
sumber dengan menggunakan Algoritma
viterbi.

116
Penyelesaian :
Trellis diagramnya :

117
Penyelesaian :

118
 Penyelesaian :

Untuk memperoleh data yang dikirimkan dengan cara melihat ke

state diagram.
Dari S0 ke S1 dengan output = 1 1, maka input = 1
Dari S1 ke S2 dengan output = 0 1, maka input = 0
Dari S2 ke S1 dengan output = 0 0, maka input = 1
Dari S3 ke S2 dengan output 1 0, maka input = 0
Dari S2 ke S0 dengan output = 1 1, maka input = 0
Dari S0 ke S0 dengan output 0 0, maka input = 0 dan seterusnya
hingga 0.

Sehingga data yang diperoleh : 119

D=(10110000)
 Standard Array

- Standard array merupakan suatu cara menyusun dalam bentuk tabel

dari 2n n-tuples melalui GF(2)

- Merupakan bentuk array 2n-k x 2k dengan konsep dasar seperti pada

decoding linier block code

- Misal sebuah linier code C (n,k) dalam GF(2) berupa vektor space

- c1, c2, …, c2k dengan 2k code word C. Faktor space {ei + C}, dimana
ei adalah coset leader yang sangat berarti dalam decoding

- n-tuple dari coset ditampilkan dalam bentuk baris dari sebuah array

120
 Standard Array

- Step-step yang harus dilakukan dalam menyusun bentuk standard

array dengan hasil seperti tabel berikut adalah:

121
 Standard Array
- Pertama, menempatkan 2k code word C pada baris top dengan all-zero
word c = (0 0 … 0) untuk elemen yang paling kiri

- Dari sisa 2n – 2k n-tuple, n-tuple e2 dipilih dan ditempatkan dibawah

elemen all-zero word c1

- Kemudian baris kedua dibentuk dengan menambahkan e2 untuk masing-

masing code word ci, 2  i  2k, pada baris top dan menempatkan
penjumlahan e2 + ci dibawah ci

122
 Contoh
Sebuah (6, 3) linier code dihasilkan menggunakan matrik generator:

Kode ini menggunakan minimum distance dmin=3 untuk membetulkan satu

Kesalahan, sehingga standard error untuk single error correction
seperti table berikut:

123
 Standard Array
- Secara umum sebuah (n, k) kode linier dengan minimum distance dmin
mempunyai kemampuan pembetulan kesalahan menggunakan error
pattern adalah t=[(dmin – 1)]/2] atau kesalahan terkecil

- Bagaimana bila lebih besar dari t error yang terjadi, kemudian error
kemungkinan terjadi pada proses decoding

124
 Contoh
Sebuah (6, 3) kode linier dengan parity check matrik sbb:

Bila menggunakan 2n-k=8 coset yang sudah ada, maka akan mempunyai
8 coset leader atau error pattern yang benar. Coset leader yang
berhubungan dengan syndrome dibentuk dari persamaan s = eHT
Sehingga menghasilkan tabel berikut:

125
 Contoh
Misal sinyal yang diterima r = (1 0 1 1 0 1), bila sinyal yang ditransmisi
kan c = (1 0 1 1 0 0) -- terdapat satu error dikarenakan noise pada
channel. Untuk single error correction, syndrome r dapat dihitung
dengan cara berikut:

126
 Contoh
Dengan menggunakan tabel berikut, (1 1 0) adalah syndrome yang
terdapat pada coset leader e = (0 0 0 0 0 1), yang mana diasumsikan
Error pattern disebabkan oleh noise pada channel.

Sehingga menyebabkan decoded dari r menjadi:

yang mana sama dengan kode yang dikirim. 127

 Contoh
Masalah berikutnya bila all-zero word c = (0 0 0 0 0 0) yang dikirim dan
r = (0 0 1 0 1 0) yang diterima -- terdapat dua error selama transmisi c
Terhadap r dapat diperoleh syndrome dengan cara:

Dari tabel coset leader seperti sebelumnya diperoleh e = (0 1 0 0 0 0)

yang berhubungan dengan syndrome s = (0 1 0), maka decoded dari r
yang diterima adalah:

hasil diatas tidak sesuai dengan kode yang dikirim dalam arti masih
terjadi kesalahan, sehingga error pattern tersebut tidak dapat
Membetulkan kesalahan

128
 Contoh
Dicoba lagi untuk kasus lain dimana c = (1 0 1 1 0 0) yang dikirim dan
r = (1 0 1 0 0 1) yang diterima, dengan cara yang sama akan diperoleh
syndrome s = (0 1 1).
Error pattern dari syndrome tersebut e =(0 0 0 0 1 0).
Sehingga diperoleh hasil:
c = r + e = (1 0 1 0 0 1) + (0 0 0 0 1 0) = (1 0 1 0 1 1)
dan ini bukan kode yang dikirim, artinya masih terjadi kesalahan.

Kesimpulan:
Dari beberapa contoh diatas dapat diketahui bahwa kode linier (6, 3)
tidak mempunyai kemampuan membetulkan kesalahan yang lebih dari
satu kesalahan

129
 Contoh
Rangkaian decoder untuk linier code (6, 3) seperti pada gambar berikut:

130
 Cyclic Codes
- Kode siklik termasuk subklas dari kode blok linier yang paling banyak
digunakan dalam error correcting codes

- Kode siklik di pelajari setelah muncul beberapa model kode sebelumnya,

misal : Hamming Code, Golay Code, Reed Mulerr Codes, Convolutional
Codes, baru setelah itu muncul kode siklik

- Salah satu tipe kode siklik yang sangat terkenal adalah BCH codes
(kode ini dikembangkan oleh Bose, Chabdhuri, dan Hacquenghem),

- Kode BCH ini yang banyak digunakan pada compact disk players

- Tetapi kode siklik sangat menarik dan banyak digunakan pada sistem
pengkodean, karena mempunyai dua alasan

- Pertama perhitungan encoding dan syndrome secara mudah dapat

diimlpementasikan shift registers sederhana menggunakan feedback
connection 131
 Pengertian Cyclic Codes
- Kedua kode ini, mempunyai struktur matematika yang luas, sehingga
memungkinkan desain kode dengan error-corection yang optimal

- Menurut definisinya, siklik berarti putaran

- Jadi dikatakan kode siklik karena kode-kode vektornya merupakan versi

putaran kode vektor lainnya, misal : codeword [ xn, x0, x1, …, xn-1], maka
jika diputar [x0, x1, …, xn-1, xn] juga merupakan codeword dari kode siklik

- kode blok disusun dengan menggunakan matrik vektor, sedangkan kode

siklik di gambarkan sebagai deretan polinomial beserta koefisiennya

- Koefisien polinomial inilah yang sangat membantu dalam pembuatan

struktur kode silik

132
 Dasar-Dasar Field
- Pada bab sebelumnya telah dibicarakan tentang kode blok linier field
yang ditulis dalam bentuk persamaan matrik sederhana, seperti berikut:

c  iG
atau

cH T  0
Sindrom dinyatakan dengan persamaan berikut :

S  eH T
dengan,
c = codeword
i = jumlah bit vektor informasi
G = matrik generator
HT = transpose parity
S = syndrome
e = error vektor 133
 Finite Field
- Kode siklik dengan elemen – elemen field yang terbatas disebut dengan
finite field dan diberi simbol GF ( q ), dimana GF adalah Golais Field, q
adalah jumlah elemen atau orde field

- Setiap finite field GF( q ) terdiri dari sekurang–kurangnya satu elemen

primitif yang disebut 

-  disebut juga sebagai non zero elemen jika mempunyai pangkat hanya
sampai q-1

- Sedangkan non zero elemen yang berubah-ubah secara eksponensial

diberi simbol 

- Nilai terkecil eksponensial berlaku untuk e = 1, hal ini yang disebut

sebagai orde elemen

134
 Finite Field
- Non zero elemen pada finite field, mempunyai sifat perkalian invers yang
khas, yaitu misal elemen  mempunyai 2 invers yaitu  dan ’, maka dapat
dituliskan persamaan sebagai berikut :

   ' 1
 (  ' )   '
( ) '  

jadi :
 '

Jadi jumlah non zero elemen yang dihasilkan oleh GF ( q ), untuk q = 1

adalah q-1 = 0 = 1, atau q-1 = 0 =1, jadi jumlah elemen dalam finite
field dapat ditunjukkan dalam bentuk eksponensial dari  berbasis 

135
 Finite Field
- Sebagai contoh : Finite field GF ( 5 ) dengan nilai  = 5, untuk nilai  = 2
dan  = 3, maka dapat dilihat hubungan antara jumlah elemen non zero
dengan elemen fieldnya seperti pada tabel

Tabel: Hub. Jml elemen field dan NZE

Non zero Elemen field
elemen
 Log 2  Log 3 
0 - -
1 0 0
2 1 3
3 3 1
4 2 2

136
 Vektor Elemen Field
- Vektor atau dikenal dengan istilah m- tuples, jika m adalah bilangan
bulat positip maka m-tuple adalah sebuah urutan bilangan riil
(a1,a2,…..am )

- Penyusunan urutan ini berdasarkan koefisien polinomial, baik dari

operasi penambahan maupun perkalian vektor

- Banyaknya m- tuples elemen dalam finite field GF ( q ) adalah qm, Jadi

jika mensubstitusi vector space m-dimensi ke dalam GF ( q ), hasilnya
merupakan vektor lain yang berbeda dengan vektor spacenya

- Untuk penyelesaian operasi vektor, maka setiap vektor diwakili dengan

koefisien polinomialnya

- Karena sifat-sifat perkalian polinomial sudah ditemukan, maka dapat

disusun finite field dengan qm elemen dengan catatan pangkat polinomial
< m – 1.
137
 Vektor Elemen Field
- Contoh: 2-nonzero elemen i dan j ditunjukkan dengan a (x) dan b(x),
kemudian diasumsikan bahwa 
pangkat m polinomial direduksi dengan

p(x), maka dapat ditulis dalam persamaan berikut :

a ( x)b( x) mod p ( x)  0
atau
a( x)b( x)  c ( x ) p ( x)

- Sedangkan finite field GF ( q ) yang terdiri dari dua elemen qm ,akan

dinotasikan dengan GF (2)

138
 Vektor Elemen Field
- Sebagai contoh: misalnya 4 buah elemen dari 2-tuples, maksudnya
adalah 4 elemen dalam GF (4), masing-masing polinomial di wakili dengan
biner 2-tuple, misal: 0 = 00 dan 1 + x = 11 dikalikan dengan p( x)  x  x  1
2

, maka hasil perkalian non zero elemennya dapat dilihat pada tabel

Tabel perkalian nonzero polinomial

 0 1 x x+1
0 0 0 0 0
1 0 1 x x+1
x 0 x x+1 1
x+1 0 x+1 1 x

139
 Vektor Elemen Field
- Dari contoh diatas operasi penambahan elemen-elemen fieldnya dapat
dilakukan dengan operasi Exclusive-OR, seperti pada tabel

Operasi penambahan Ex-OR elemen field

=x  = x+1
- = 0 = 00 - = 0 = 00
0 = 1 = 01 0 = 1 = 01
1 = x = 10 1 = x+1= 11
2 = x+1 = 11 2 = x = 10

140
 Vektor Elemen Field
- Dari contoh-contoh diatas, elemen primitif dapat di tes dengan cara
menaikkan pangkat dari x sampai mencapai orde yang memerlukan
reduksi dengan modulo dalam perhitungannya
Contoh : x1 = x ; x2 = x+1; x3 = x2+1= (x+1)+1=1, disini tampak bahwa
untuk menghitung x2 dan x3 diperlukan modulo x2+x+1. Jika x mempunyai
orde e=3 berarti q-1=3, maka x disebut elemen primitif.

141
 Extension field dan polinomial primitif
- Pada umumnya elemen pada finite field GF(pm) berlaku untuk setiap
jumlah pm dimana p adalah prime dan m adalah bilangan bulat positip dan
biasa disebut sebagai orde dari fieldnya itu sendiri

- Sub field dari GF(pm) adalah GF(p), jadi setiap elemen dari GF(p)
merupakan anggota himpunan dari elemen GF(pm)

- Dalam hal ini GF(pm) disebut sebagai extension field

- Sebagai contoh apabila extension field merupakan kumpulan dari

bilangan kompleks, maka bilangan riil merupakan anggota himpunan dari
bilangan kompleks tersebut

- Sedangkan penggabungan dari field-field itu dapat dilakukan dengan

menambahkan koefisien-koefisien polinomialnya

- Polinomial yang akar-akarnya mempunyai elemen primitif disebut sebagai

polinomial primitif 142
 Extension field dan polinomial primitif
- Koefisien polinomial primitif untuk GF(23) dihasilkan dari polinomial
p(x) = x3+x+1, dapat dilihat pada tabel

GF(p3) dengan p(x) = x3+x+1

Nol dan orde x Polinomial GF(2) Vektor GF(2)

0 0 000
x0 1 001
x1 x 010
x2 x2 100
x3 x+1 011
x4 x2+x 110
x5 x2+x 110
x5 x2+x+1 111
x6 x2+1 101

143
 Sequences Dalam Kode Siklik
- ditunjukkan hubungan antara elemen field yang dihasilkan dari polinomial
yang tidak dapat diperkecil lagi dengan sequence yang dihasilkan dengan
feedback shift register untuk polinomial yang sama

- Pada tabel sebelumnya ditunjukkan bahwa shift register dibuat untuk

polinomial x3+x+1, sedangkan tap feedback mempunyai hubungan x3=x+1
dan operasi penambahan dilakukan dengan modulo 2

- Secara blok diagram sequence generator untuk polinomial x3+x+1, dapat

dilihat pada gambar sbb:

Sequence Generator Untuk Polinomial x3+x+1

144
 Struktur Kode Siklik (n,k)
- Kode siklik mempunyai struktur aljabar dengan derajat polinomial
tertinggi n-1, dengan codeword yang dirumuskan dalam bentuk polinomial
berikut:
c( x)  c0  c1 x  c2 x 2  ........  cn1 x n 1
sebuah kode siklik dapat dibentuk dari:
c( x)  d ( x).g ( x)
dimana, c(x) = codeword yang akan dibentuk
d(x) = polinomial data/informasi
g(x) = generator polinomial, derajat tertinggi dari g(x)
adalah n-k

145
 Struktur Kode Siklik (n,k)
- Ditinjau dari strukturnya, kode siklik dibagi dalam dau macam kode yaitu
kode sistematik dan non sistematik dimana keduanya mempunyai struktur
pembentukan kode yang berbeda

- Untuk membentuk codeword maka langkah-langkah yang harus ditempuh

adalah:
- Menetapkan generator polinomial g(x)
- Proses perhitungan untuk mendapatkan bit parity check
- Pembentukan codeword

146
 Kode siklik non sistematik
- Pembentukan kode siklik non sistematik lebih mudah daripada
pembentukan kode siklik sistematik

- Dari generator polinomial yang telah didapatkan, data sebagai urutan

informasi dikalikan untuk mendapatkan codeword non sistematik

- Sebagai contoh, sebuah kode siklik (7,4) mempunyai generator

polinomial yaitu g(x) = 1+x+x2

- Misalkan d = (1010) adalah urutan informasi yang akan dikirimkan

dengan polinomial d(x) = 1+x2 , maka akan diperoleh kode polinomial
dengan bentuk non sistematik sbb:

c(x) = d(x).g(x)
= (1+x2) (1+x+x3)
= 1+x+x2+x3 , dimana kode ini akan membentuk
codeword c = (1110010)
147
 Kode siklik non sistematik
- Kode siklik (7,4) yang dihasilkan dari g(x) = 1+x+x3 secara lengkap
ditunjukkan oleh tabel berikut, dimana kode memiliki jarak minimum 3
dan merupakan single error correcting code

Kode Siklik Non Sistematik (7,4) dengan g(x) = 1+x+x3

Urutan d(x) c(x)=d(x).g(x) Codeword
Informasi d
0000 0 0 0000000
0001 x3 x3+x4+x6 0001101
0010 x2 x2+x3+x5 0011010
0011 x2+x3 x2+x4+x5+x6 0010111
0100 x x+x2+x4 0110100
0101 x+x3 x+x2+x3+x6 0111001
0110 x+x2 x+x3+x4+x5 0101110
0111 x+x2+x3 x+x5+x6 0100011
1000 1 1+x+x3 1101000
1001 1+x3 1+x+x4+x6 1100101
148
Kode siklik non sistematik
Kode Siklik Non Sistematik (7,4) dengan g(x) = 1+x+x3
(Lanjutan)

Urutan d(x) c(x)=d(x).g(x) Codeword

Informasi d
1010 1+x2 1+x+x2+x5 1110010
1011 1+x2+x3 1+x+x2+x3+x4+x5+x6 1111111
1100 1+x 1+x2+x3+x4 1011100
1101 1+x+x3 1+x2+x6 1010001
1110 1+x+x2 1+x4+x5 1000110
1111 1+x+x2+x3 1+x3+x5+x6 1001011

149
 Kode Siklik Sistematik
- Dengan generator polinomial g(x) dari sebuah kode siklik, codeword
dapat dibentuk secara matematis dengan rumusan:

c  ( 0 ,  1 ,.....,  n  k 1 , d 0 , d1 ,....., d k 1 )

- Dari persamaan diatas, informasi polinomial d(x) dan check polinomial

(x) dapat dinyatakan sebagai berikut:

d ( x)  d 0  d1 x  ......  d k 1 x k 1

 ( x)   0   1 x  ......   n  k 1 x n  k 1

dimana, (x) adalah sisa pembagian polinomial berderajat n-k-1

atau kurang, yang diperoleh dari pembagian x n k d (x) dengan
g(x)
x n  k d ( x) : g ( x)  q ( x)  r ( x)
dengan, q(x) adalah hasil bagi
150
r(x) adalah sisa pembagian
Contoh

Sebuah kode siklik (7,4) mempunyai :

Generator polinomial g(x) = 1+x+x3
Urutan informasi yang akan dikirim d = (1100)
Informasi polinomial d(x) = 1+x
Karena n-k = 3, maka didapatkan x3 d(x) = x3+x4

Pembagian x3+x4 dengan g(x) = 1+x+x3, menghasilkan sisa polinomial :

(x) = 1+x2

Jadi code polinomial yang didapat adalah :

c(x) = 1+ x2+x3+x4

Codeword c = (1011100)

151
Contoh
16 codeword
sistematik yang mungkin terbentuk seperti terlihat pada tabel

Kode Siklik Sistematik (7,4) dengan g(x) = 1+x+x3

Urutan d(x) x3d(x) r(x) Codeword c
Informasi d
0000 0 0 0 0000000
0001 x3 x6 1+x2 1010001
0010 x2 x5 1+x+x2 1110010
0011 x2+x3 x5+x6 x 0100011
0100 x x4 x+x2 0110100
0101 x+x3 x4+x6 1+x 1100101
0110 x+x2 x4+x5 1 1000110
0111 x+x2+x3 x4+x5+x6 x2 0010111
1000 1 x3 1+x 1101000
1001 1+x3 x3+x6 x+x2 0111001
1010 1+x2 x3+x5 x2 0011010
1011 1+x2+x3 x3+x5+x6 1 1001011
152
 Kode Siklik Sistematik

- Perbedaan yang mendasar antara kode siklik sistematik dan non

sistematik adalah pada codeword yang dihasilkan oleh encodernya

- Pada kode sistematik dapat dibedakan antara bit-bit informasi

dengan bit-bit paritynya

- sedangkan pada kode non sistematik tidak dapat dibedakan

- Karena sifatnya tersebut, maka kode siklik yang banyak digunakan

adalah kode siklik yang sistematik

153
 Kode Siklik Sistematik

- Secara blok diagram encoder dapat digambarkan pada gambar berikut:

154
 Kode Siklik Sistematik

- Operasi pengkodean untuk gambar pengkodean seperti pada tabel sbb:

Bit Input Input register Output

register
 d ri0 ri1 ri1 ri0 ri1 ri1
 - 0 0 0 0 0 0
 
1 1 1 0  shift1  1 1 0
0 0 1 1  shift2  0 1 1
1 0 0 1  shift3  0 0 1
0 1 1 0  shift4  1 1 0
 

155
 Generator Matriks dan Parity Check Matriks

- Generator matrik G dalam bentuk sistematik dapat diperoleh dengan

dua cara:
- Pertama adalah mengambil tiap codeword siklik sistematik yang
merupakan vektor basis, yaitu codeword yang bit informasinya
berbobot satu (artinya bahwa dalam urutan informasi codeword
tersebut hanya ada satu bit komponen non zero)

- Kedua untuk mendapatkan generator matriks kode siklik sistematik

adalah dengan menggunakan persamaan :

x n  k i  qi ( x) g ( x)   i ( x) i  0,1,...., k  1
dimana,

 i ( x)   i ,0   i ,1 x   i , 2 x 2  .....   i ,n  k 1 x n k 1
adalah sisa pembagian polinomial dengan derajat n-k-1 atau
kurang
156
 Generator Matriks dan Parity Check Matriks
- Sedangkan perkalian dengan g(x) dapat ditulis dengan persamaan
berikut :
ci ( x )  q i ( x ) g ( x )   i ( x )  x n  k  i i  0,1,..., k  1

- Struktur generator matriks kode siklik sistematik adalah:

c 0   0,0  0,1 ..... 0,n  k 1 100....0 
c   
 110 ....0 
G 1   1, 0
 1,1 ...... 1,n  k 1

  G
  
c k 1  .  
 
 k 1,0  k 1,1 ... k 1,n  k 1 000....1
 


G  Rkx ( n  k ) I k 
157
 Generator Matriks dan Parity Check Matriks
- Dari generator matriks ini dapat dibentuk parity check matriks H
sbb:


H  I n  k R(Tn  k ) xk 
100  0  0, 0  1, 0  k 1,0 
 
100  0  0,1  1,1  k 1,1 
 
 
H  100  0  0, 2  1, 2  k 1, 2 
 
 
 
0001  0,n  k 1  1,n  k 1  k 1,k 1 
 

158
 Contoh
- Kode siklik (7,4) dengan generator g(x) = 1+x+x3, maka hasil
pembagian x3+i dapat dilihat pada tabel

Pembagian x3+i dengan g(x)=1+x+x3

i x3+i i(x) ci(x)= i(x)+ x3+i ci

0 x3 1+x 1+x+ x3 1101000

1 x4 x+ x2 x+ x2+ x4 0110100
2 x5 1+x+ x2 1+x+ x2+ x5 1110010
3 x6 1+ x2 1+ x2+ x6 1010001

159
 Contoh
- Dengan menggunakan keempat codeword tersebut sebagai baris
dari matriks berukuran 4x7 didapatkan generator matriks G dalam
bentuk sistematik sebagai berikut

1101000 
0110100 
G    R4 x 3 I 4 x 4 
1110010 
 
1010001 
Diperoleh juga parity check matriks H dalam bentuk sistematik


H  I 3 x 3 R3Tx 4 
1001011 
H  0101110 
0010111 
160
 Contoh
- Dengan cara yang lebih sederhana, dapat dibentuk generator
matriks G untuk kode siklik dalam bentuk non sistematik, yaitu
dengan struktur sbb:
 g 0 ( x)  g ( x) 
 g ( x)  xg ( x) 
G 
1

 
 k 1

 g k 1 ( x)  x g ( x) 

- jika diperhatikan, maka baris kedua dan seterusnya merupakan

hasil pergeseran siklik dari baris sebelumnya.

161
 Metode Deteksi dan Koreksi pada Kode Siklik
Metode Deteksi Error
- Secara umum dikenal 2 metode pendeteksian error yang sederhana,
yaitu : Vertical Redundancy Check (VCR) dan Longitudinal
Redundancy
Check(LCR), kedua sistem ini menggunakan bit parity untuk men-
deteksi kesalahan.
Metode Koreksi Error
- Sistem koreksi error dikenal dengan istilah error control

- Bertujuan agar data yang telah berubah dalam transmisi diperbaiki

sebelum diproses lebih lanjut

- Error dapat dikoreksi dengan 2 prinsip metode, yaitu : Sistem

Automatic Repeat Request (ARQ) dan Sistem Forward Error
Correction (FEC)

- Pada kode siklik digunakan sistem FEC dalam mengoreksi kesalahan

162
 Metode Deteksi dan Koreksi pada Kode Siklik
Metode deteksi dan koreksi Error Pada Kode Siklik
- Dilakukan dengan cara menghitung sindrom, untuk mengetahui apakah
word r (received word) yang diterima merupakan codeword c yang
sesuai atau bukan

- Bila hasil perhitungan sindrom adalah nol maka word r merupakan

codeword yang dikirimkan

- Sebaliknya jika hasil perhitungan sindrom bukan nol, berarti word r

mengandung error yang membutuhkan proses koreksi

163
 Metode Deteksi dan Koreksi pada Kode Siklik
Perhitungan Sindrom Kode Siklik
- Perhitungan sindrom dapat dilakukan dengan menggunakan persamaan-
persamaan berikut :
r ( x)  q ( x).g ( x)  s ( x)
dimana:
r(x) adalah word r yang diterima.
g(x) adalah generator matriks
s(x) adalah sisa pembagian (merupaka sindrom s yang
dicari)
atau dapat dinyatakan dengan:
s(x) = r(x) mod g(x)
= s0+s1x+…+sn-k-1xn-k-1
Bila nilai s(x)=0, maka r(x)=c(x) dan bila nilai s(x) tidak sama dengan
0 maka r(x) bukan merupakan codeword c(x) yang diharapkan karena
masih terdapat error e(x).
164
r(x) = c(x) + e(x)
 Contoh
Sebuah kode siklik (7,4) mempunyai generator polinomial g(x) = 1+x+x3,
dengan matrik generator sbb:
1101000 
0110100 
G 
1110010 
 
1010001 
Sedangkan parity check matriknya adalah :

1001011 
H  0101110 
0010111 

165
 Contoh
Apabila word yang diterima adalah r = (1011011), maka dapat dihitung:

s  r T .H
1 
0 
 
1001011  1 
 
 0101110 .1   (001)
0010111  0
 
1 
1 
 

Jadi polinomial sidrom s(x)=x2 merupakan sisa pembagian dari r(x)

dengan g(x) :
r ( x)  (1  x 2  x 3  x 5  x 6 ) /(1  x  x 3 )
 ( x 3  x 2  x  1) g ( x)  x 2 166
 DAFTAR PUSTAKA

1. Man Young Rhee, “ Error Corecting Coding Theory ”, McGraw-Hill

Inc, 1989.
2. Peebles, Peyton. Z, “ Probability, Random Variables, and Random
Signal Principles“, McGraw-Hill, Inc, 1993.
3. Shu Lin and Costello, Daniel. J.” Error Control Coding :
Fundamental and Aplication“, Prentice – Hall Inc, Englewood Cliffs,
New Jersey, 1983.
4. Simon, Marvin. K, Hinedi, Sami. M and Lindsey. William. C, Digital
Communication Techniques Signal Design and Detection “, Prentice
- Hall International, Inc, Englewood Cliffs, New Jersey, 1995.
5. Wicker. Stephen. B.,” Error Control Systems for Digital
Communication and Storage,” Prentice-Hall International, Inc,
1995.

167