## SIFAT ALJABAR KODE KUADRATIK RESIDU YANG DIPERLUAS

## Kusbudiono dan Bagus Juliyanto
Jurusan Matematika Fakultas MIPA Universitas Jember
Abstract. In  code  theory  one  of  the  important  code  types  is  binary  code.  At  binary field till, there is a residu quadratic and a permutation  defined with residu  quadratic can form a code called residu quadratic code. This code can be extended. In this paper, we discuss the propertis of group of it.
Keywords: Extension, residu quadratic code, properties of algebra MSC 2020 ( https://zbmath.org/classification )

## 1. Pendahuluan
Dalam penjumlahan (+) dan perkalian (*) yang memenuhi aksioma-aksioma berikut:
1. ( F ,+) adalah grup komutatif, yang memenuhi Untuk semua r , s  F maka r + s  F (tertutup) Untuk semua r , s  F maka r + s = s + r (komutatif) Terdapat elemen 0  F yang untuk setiap r  F maka r + 0 = r Untuk setiap r  F , ada elemen – r  F berlaku r + (- r ) = 0 (invers) Untuk semua r , s , t  F maka r + ( s + t ) = ( r + s ) + t (assosiatif)
2. ( F -{0}) adalah grup komutatif 3. Untuk setiap r , s , t  F maka r * ( s + t ) = ( r * s ) + ( r * t ) (distributif).

## 2. Hasil dan Pembahasan
Suatu kode C(n, k) yang linier merupakan subruang dari ruang vektor linier dimensi n atas GF (2) ( Galoys Field modulo 2). Oleh karena itu ada kemungkinan untuk menemukan k katakode  yang saling bebas, misal g 1 , g 2 , …, g k -1 di C , sedemikian sehingga agar setiap katakode v di C merupakan kombinasi linier dari k katakode tersebut,
v = u 0 g 0 + u 1 g 1 + … + u k-1 g k -1
u i  {0, 1} untuk 0  i  k -1.
Misalkan k katakode  yang  saling  bebas  linier  disusun  sebaga i baris  dari  matriks k x n , seperti berikut ini:
                                              1 , 1 2 , 1 1 , 1 0 , 1 1 , 1 2 , 1 1 , 1 0 , 1 1 , 0 2 , 0 1 , 0 0 , 0 1 1 0 . . . . . . . . . n k k k k n n k g g g g g g g g g g g g g g g G    
dimana g i = { g 1,0 , g i,2 , . . . g i,n-1 } untuk 0  i  k . Jika u = { u 0 , u 1 , . . . , u k -1 } adalah pesan yang dienkoding, hubungannya dengan katakode dapat diberikan sebagai berikut:
V = UG
                 1 1 0 1 1 0 k k g g g u u u  
= u 0 g 0 + u 1 g 1 + . . .  + u k-1 g k -1
Selanjutnya akan didefinisikan kode siklis yang diberikan oleh Ratna.[3] dan generator dari suatu kode siklis yang diberikan oleh Pless.[2]
Definisi  2.1 Suatu  kode  linier C(n,  k) dapat  dikatakan  kode  siklis  jika  setiap  pergeseran siklis (permutasi) dari vektor kode di C juga merupakan vektor di C .
Contoh :
C = {(000000), (1011100), (0010111), (1110010), (0111001), (1001011), (1100101)}.
Definisi  2.2 Misal x n +1 adalah  polinomial  yang  dapat  dinyatakan  sebagai x n +1 = g(x)h(x) dimana g(x) adalah  polinomial  berderajat n-k . g(x) disebut  generator  polinomial  sebagai faktor dari x n +1 . Artinya setiap faktor dari x n +1 dengan derajat n-k membangun suatu kode siklik ( n, k ).
Misalkan g(x) adalah  generator  polinomial  dari  kode  siklik C .  diketahui  bahwa g(x) membagi x n -1 sehingga x n -1 = g(x)h(x). Jika g(x) mempunyai  derajat n  –  k ,  maka C mempunyai dimensi k dan h(x) berderajat k karena h(x ) membagi x n-1 .
Suatu generator e(x) dari sebuah ideal di Rn disebut generator idempoten jika e(x) adalah idempoten, yaitu e 2 (x) = e(x). Generator ini bertindak sebagai unit karena jika a(x) di dalam < e(x) > maka a(x) = b(x)e(x) dan a(x)b(x) = b(x)e 2 (x) = b(x)e(x) = a(x). Selanjutnya akan diberikan lemma dari Pless.[2] tentang generator idempoten.
Lemma  2.3 Suatu  polinomial  biner f(x) adalah  suatu  idempoten  di Rn jika  hanya  jika himpunan S dari pangkat x yang terjadi dengan koefisien tidak nol di f(x) adalah gabungan koset siklotomik untuk n .
Kode  kuadratik  residu  dapat  didefinisikan  atas  sebuah field hingga  umum,  tetapi  pada tulisan  ini  hanya  dibatasi  pada  kode  kuadratik  residu  biner.  Kode-kode  ini  adalah  kode siklik  dan  akan  dibangun  dengan  generator  idempotennya.  Pandang field hingga GF(p) dimana p adalah  prima  ganjil  dan G adalah  grup  perkalian  dari  elemen  tidak  nol  dalam GF(p), maka G mempunyai order p – 1. Misalkan Q adalah subgrup dari kuadrat-kuadrat di G . Anggota-anggota dari Q disebut kuadratik residu, dan Q mempunyai order ( p – 1)/2.
Kode siklik adalah kode-kode yang mentransformasikan pada dirinya sendiri dengan suatu pergeseran siklik. Pada kode kuadratik residu juga ditransformasikan pada dirinya sendiri dengan permutasi i  ai (mod p ) dimana a adalah suatu kuadratik residu.
Jika a adalah sembarang bilangan bulat kurang dari n dan gcd(a, n) = 1, maka permutasi  a yang didefinisikan dengan  a ( i ) = ai (mod n ) membawa koset  siklotomik  pada koset siklotomik. Jika a  2 i (mod n ), maka permutasi  a mentransformasi suatu kode siklik pada dirinya  sendiri.  Anggap a bukan  pangkat  dari  2  (mod n )  maka  permutasi  a mentransformasi  kode  siklik  pada  suatu  kode  siklik  lain  yang  ekivalen,  dan  teorema berikut akan menunjukkan bahwa kode yang ekivalen tersebut juga kode siklik.
Teorema 2.4 Jika C kode silik dengan panjang n , maka permutasi  a yang didefinisikan dengan  a ( i ) = ai (mod n ), i = 1, 2, . . ., n - 1 dimana gcd(a, n) = 1 mentransformasi C ke suatu kode siklik C ’ atau pada C itu sendiri.
Bukti:
Misalkan e(x) adalah generator idempoten kode silik C , jika S = {i sedemikian hingga xi mempunyai  koefisien  1  di e(x), maka S adalah  gabungan  dari  koset  siklotomik    (lemma 2.3). Sehingga vektor e(x) memiliki “1” pada penggabungan koset siklotomik yang sama, maka e(x )  a = e(x) dan e(x)  a -1 = e(x) . Dengan  a   a -1 =  (akibar defini  a ) maka e(x)  a -1   a = e(x)  a dan ( e(x)  )  a = e(x)  a . Hal ini berarti  a mentransformasi e(x) pada e(x) sendiri.  Dan  karena e(x) adalah  generator  idempoten C maka  a mentransformasi C pada C itu sendiri.
Untuk menunjukan bahwa suatu kode siklik adalah kode kuadratik residu, akan diberikan beberapa teorema-teorema yang akan digunakan untuk mengidentifikasi suatu kode siklik adalah kode kuadratik residu dengan mengasumsikan gcd(a, n) = 1.
Teorema  2.5 Untuk  suatu  permutasi  μ a yang  didefinisikan  sebagai μ a =  ai (mod n ) mempertahankan perkalian polinomial.
Bukti :
Dari teorema  diketahui bahwa μ a mengirimkan  sebarang kode siklik pada kode siklik lain. Sehingga benar μ a mempertahankan perkalian polinomial di Rn . Untuk mengetahui hal itu misalkan
b ( x ) = b 0 + b 1 x + .. . + b n-1 x n-1
dan
c ( x ) = c 0 + c 1 x + . . . + c n-1 x n-1
maka
b(x)c(x) = ( b 0 c 0 + b 1 c n-1 + . . .+ b n-1 c 1 ) + ( b 0 c 1 + b 1 c 0 + … + b n-1 c 2 ) x + . . .  + ( b 0 c n-1 + b 1 c n-2 + . . . + b n-1 c 0 ) x n-1 .
Misalkan b ’( x ), c ’( x ),  dan (b(x)c(x)) ’masing-masing  adalah  peta  dari b ( x ), c ( x ),  dan b ( x ) c ( x ) dibawa μ a, maka
b’(x)c’(x) =
Dari  teorema  di  atas  dan  fakta  bahwa  suatu  kode  siklik  dengan  suatu  permutasi  dapat dikirim menjadi suatu kode siklik lain timbul akibat berikut.
Akibat  2.6 Jika  μ a mengirimkan  suatu  kode  siklik C dengan  idempoten e(x) pada  suatu kode C ’, maka C’ adalah siklik dengan idempoten e(x) μ a.
Bukti :
Dari Teorema 2.4 dan 2.5 jelas, karena idempoten adalah unit perkalian dari kode. Misalkan Q 1 dan Q 2 adalah  kode  kuadratik  residu, Q 1 dan Q 2 biasanya  diperluas  dengan menjumlahkan  suatu  parity  chek  keseluruhan.  Untuk  itu  diberikan  koordinat  baru  . Koordinat-koordinat  itu  sekarang  diberi  nama  ,  0,  1,  .  .  ., p -1,  ini  dilakukan  karena koordinat-koordinat  baru itu adalah titik-titik garis proyektif dan akan ditunjukkan bahwa transformasi garis proyektif di dalam grup masing-masing perluasan kode kuadratik residu yang merupakan salah satu sifat dari kode tersebut. Dan untuk perluasan kode Q 1 dan Q 2 dinotasikan  dengan Q 1 ’  dan Q 2 ’.  Selanjutnya  akan  diberikan  teorema  berikut  untuk menunjukkan sifat di atas.
Sebelum membahas teorema yang dimaksud, akan didefinisikan suatu grup linier proyektif khusus yaitu suatu grup tranformasi dari garis proyektif yang mempunyai p + 1 titik yaitu  , 0, 1, . . ., p – 1 untuk p prima. Didefinisikan PSL 2 ( p ) suatu grup permutasi pada  , 0, 1, .. . ., p – 1 untuk p prima adalah dibentuk dengan permutasi elemen-elemen i pada GF(p) berikut:
 : i  i + 1 (mod p ),     a: i  ai (mod p ), untuk a  Q   
 : i  - 1/i (mod p ), i  0, 0   ,   0
Diketahui bahwa PSL 2 ( p ) mempunyai order ( p –1) p ( p + 1)/2 dan dengan teorema Gleason dan  Prange  dalam  Pless.[2]  akan  ditunjukkan  bahwa PSL 2 ( p )  terletak  di  dalam  grup Q 1 ’ dan Q 2 ’.
Teorema 2.7 Grup Q 1 ’ atau Q 2 ’ memuat PSL 2 ( p )
Bukti :
Diketahui bahwa  dan  a didalam G ( Qi )’, i = 1, 2, karena transformasi ini didalam G(Qi)
Majalah Ilmiah Matematika dan Statistika 17  Nomor 2  2017, 61 – 66 https://jurnal.unej.ac.id/index.php/MIMS/index ISSN 1411-6669
dan  transformasi  itu  mempertahankan  koordinat  .  Untuk  menunjukkan  bahwa  mentransformasi  perluasan  kode  kuadratik  residu  pada  dirinya  sendiri  untuk  kode-kode tertentu  rumit,  maka  hanya  dilihat  pada  saat  =  7.  Berikut  ini  adalah  daftar e 1 ( x )  dan semua pergeserannya dengan parity chek tambahan. Ini mencakup suatu matrik generator bagi Q 1 . Sebut baris-baris itu r 0 , r 1 , . . . , r 6 ,
Dengan  mengaplikasikan  pada  kolom-kolom  matriks  ini,  akan  didapatkan  matriks berikut, dimana h adalah vektor satuan.
Ingat  bahwa  1,  2  dan  4  adalah  residu.  Ada  suatu  pola  yang  muncul  yang  berlaku umum. Ketika p  -1 (mod 8), misalkan M adalah matriks dengan baris-baris r i , i = 0, . . ., p -1, dimana r 0 = e 1 ( x ) dan r i , untuk i  0, sama dengan pergeseran ke- i dari e 1 ( x ). Misalkan M ’, dengan baris-baris r i ’, matriks yang dihasilkan dari pengaplikasian  ke M . Maka terlihat bahwa r 0 ’ = r 0 + h , r 1 ’ = r -1/I + r 0 jika i adalah sebuah residu dan r i ’ = r -1/ i + r 0 + h jika i bukan  residu.  Akibatnya M ’  ekivalen  denga M’ ,  sehingga  mentransformasi Q 1 ’ kepada dirinya sendiri, analog untuk Q 2 ’.

## 3. Kesimpulan
Berdasarkan pembahasan tentang salah satu sifat aljabar dari kode kuadratik, maka  dapat ditarik kesimpulan sebagai berikut:
1. Grup  kode  adalah  suatu  himpunan  permutasi  yang  mentransformasi  suatu  kode pada kode itu sendiri.
2. Kode  kuadratik  residu  adalah  suatu  kode  yang  diransformasi  pada  dirinya  sendiri oleh suatu permutasi : i  ai , dengan a suatu kuadratik residu.
3. Grup kode dari perluasan kode kuadratik residu memuat suatu grup linier proyektif khusus ( PSL 2 ( p )).

## Daftar Pustaka
[1] Fraleigh, J.B., (1971), A First Course in Abstract Algebra , Fourth Edition, Addison- Wesley Publishing Company, New York
[2] Pless,  V.,  (1989), Introduction  to  The  Theory  of  Error-Correcting  Codes ,  Second Edition, John Wiley and Sons, New York.
[3] Ratna D.S, dan Sunarsini, (1995), Kode Red-Solomon (RS) dan Penerapannya untuk Koreksi Data , Laporan Penelitian, Institut Teknologi Sepuluh Nopember, Surabaya