Construction of Strongly Optimal Linear Binary Codes with Minimum Distance of 5 and 7

Abstract

A code 􀜥 􀙃 􀥲􀬶 􀯡 which is also a subspace of 􀥲􀬶 􀯡 is called linear binary code. If C has length n, dimension k and minimum distance d, then C is an [n, k, d] code. The main problem in coding theory is optimizing one of the parameters n, k, and d for given values of the others. In this research, the strongly optimal linear binary codes are constructed by using Gilbert-Varshamov bound and implemented using MAPLE software. In this case, the constructed basic code C[n, k, d] is then extended to obtain the code 􀜥􁇱 [􀝊􁇱, 􀝇􁇱, 􀝀], which can not be extended anymore and which is known from the previus research that 􀜥􁇱􁇱 [􀝊􁇱+1, 􀝇􁇱+1,d] does not exist. As a result, 􀜥􁇱 [􀝊􁇱, 􀝇􁇱, 􀝀] is strongly optimal code. The strongly optimal codes that has been successfully constructed are the codes with parameters [8,2,5], [11,4,5], [17,9,5], [23,14,5], [31,21,5], [33,23,5], [11,2,7], [15,5,7], [23,12,7], [27,14,7], [30,16,7] and [31,17,7].

Kode diciptakan untuk mendeteksi atau mengoreksi galat (error) akibat saluran terganggu. Dalam hal ini sebelum dikirim , semua pesan akan diubah menjadi kata kode (codeword) dengan cara menambahkan beberapa simbol ekstra pada simbol pesan. Proses pengubahan pesan menjadi kata kode disebut enkoding. Perangkat yang mengubah pesan menjadi kata kode disebut enkoder. Kode merupakan himpunan kata kode. Pendefinisian kode ini dilakukan sedemikian sehingga apabila terjadi perubahan beberapa simbol pada kata kode, maka galat itu bisa dipulihkan oleh dekoder. Dekoder merupakan perangkat yang mengubah barisan s ang diterima menjadi kata kode. Kata kode tersebut dipulihkan menjadi pesan asli. imbol y Suatu kode 􀜥 􀙃 􀥲􀬶 􀯡 subruang dari ruang vektor 􀥲􀬶 􀯡 disebut kode linear biner. Jika kode C dengan panjang n, dimensi k dan jarak minimum d maka disebut kode [n, k, d]. Masalah utama di dalam aljabar teori koding adalah mengoptimalkan salah satu parameter n, k, dan d ketika dua nilai yang lain telah ditentukan. Masalah tersebut mengarah pada pendefinisian fungsi D ( n, k ) = maks { d / kode [ n, k, d ] ada } untuk optimal-D K ( n, d ) = maks { k / kode [ n, k, d ] ada } untuk optimal-K N ( k, d ) = min { n / kode [ n, k, d ] ada } untuk optimal-N Dalam hal ini, suatu kode C dengan parameter [ n, k, d ] disebut optimal-D (optimal jarak minimum), jika C ada (telah berhasil dikonstruksi) dan telah pula dibuktikan bahwa tidak ada kode dengan parameter [ n, k, d + 1]. Jika kode linear [n, k, d] ada dan telah berhasil dibuktikan bahwa kode linear [n-1, k, d] tidak ada maka kode disebut optimal-N. Selanjutnya jika kode linear [n, k, d] ada dan telah berhasil dibuktikan bahwa kode linear [n, k+1, d] tidak ada, maka kode tersebut disebut optimal –K. Kode linear C dengan parameter [n, k, d] disebut kode optimal kuat jika kode [n, k, d] ada dan telah dibuktikan bahwa kode [n+1, k+1, d] tidak ada. Pada penelitian ini akan dikonstruksi kode-kode optimal kuat berjarak minimum 5 dan 7 berdasarkan teorema Gilbert-Varshamov bound dan pengembangan metode komputasi dengan software MAPLE. Dalam hal ini dikonstruksi kode dasar [n, k, d], selanjutnya dari kode dasar ini dikonstruksi tahap demi tahap kode [n+1, k+1,d], [n+2, k+2, d],…dan seterusnya sampai diperoleh kode C dengan parameter [􀝊􁇱, 􀝇􁇱, 􀝀􁈿 yang tidak bisa diperluas lagi dan telah diketahui dari hasil penelitian sebelumnya kode dengan parameter [􀝊􁇱 􀵅 1, 􀝇􁇱 􀵅 1, 􀝀􁈿 tidak ada. (informasi terkini eksistensi suatu kode berdasarkan tabel Brouwer terbarukan secara online). Hasil konstruksi kode C [􀝊􁇱, 􀝇􁇱, 􀝀􁈿 ini yang disebut kode optimal kuat. Kode C dapat digunakan sebagai kode dasar untuk diperluas menjadi kode optimal kuat berikutnya.