Lewati ke konten utama

\(\newcommand{\aatavdots}[1]{\vdots} \newcommand{\codeword}{} \newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Bagian 8.9 Sage

Sage menyediakan seperangkat lengkap kode linear dan beragam metode yang dapat digunakan untuk menyelidikinya.

Subbagian 8.9.1 Mengonstruksi Kode Linear

Objek codes dapat digunakan untuk memperoleh daftar ringkas kode terimplementasi yang tersedia. Ketik codes. dan tekan tombol Tab; sebagian besar antarmuka Sage akan menampilkan suatu daftar. Selanjutnya, Anda dapat menggunakan tanda tanya di akhir nama metode untuk mempelajari berbagai parameternya.

Kode Sage (cadangan statis)

codes.

Sebagai ilustrasi, kita akan menggunakan kode Hamming biner klasik \((7,4)\text{.}\) “Biner” berarti kita memiliki vektor yang hanya memuat 0 dan 1; \(7\) adalah panjangnya dan berarti bahwa vektor-vektor tersebut memiliki \(7\) koordinat, sedangkan \(4\) adalah dimensinya, yang berarti bahwa kode ini terdiri atas \(2^4=16\) vektor. Dokumentasi tersebut mengasumsikan bahwa kita telah mengetahui beberapa hal dari bagian akhir mata kuliah. Kita menggunakan GF(2) untuk menetapkan bahwa kode kita bersifat biner — hal ini akan lebih masuk akal pada akhir mata kuliah. Parameter kedua adalah r, dan dari rumus-rumus dalam dokumentasi kita dapat melihat bahwa menetapkan r=3 akan menghasilkan panjang \(7\text{.}\)

Kode Sage (cadangan statis)

H = codes.HammingCode(GF(2), 3); H

Keluaran referensi (cadangan statis)

[7, 4] Hamming Code over GF(2)

Subbagian 8.9.2 Sifat-sifat Kode Linear

Kita dapat memeriksa kode Hamming yang baru saja dibangun. Pertama, dimensinya.

Kode Sage (cadangan statis)

H.dimension()

Keluaran referensi (cadangan statis)

Kode tersebut cukup kecil sehingga kita dapat mencantumkan semua kata kodenya.

Kode Sage (cadangan statis)

H.list()

Keluaran referensi (cadangan statis)

[(0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 1, 1), (0, 1, 0, 0, 1, 0, 1),
 (1, 1, 0, 0, 1, 1, 0), (0, 0, 1, 0, 1, 1, 0), (1, 0, 1, 0, 1, 0, 1),
 (0, 1, 1, 0, 0, 1, 1), (1, 1, 1, 0, 0, 0, 0), (0, 0, 0, 1, 1, 1, 1),
 (1, 0, 0, 1, 1, 0, 0), (0, 1, 0, 1, 0, 1, 0), (1, 1, 0, 1, 0, 0, 1),
 (0, 0, 1, 1, 0, 0, 1), (1, 0, 1, 1, 0, 1, 0), (0, 1, 1, 1, 1, 0, 0),
 (1, 1, 1, 1, 1, 1, 1)]

Jarak minimum barangkali merupakan salah satu sifat terpenting. Kode Hamming selalu memiliki jarak minimum \(d=3\text{,}\) sehingga selalu dapat mengoreksi kesalahan tunggal.

Kode Sage (cadangan statis)

H.minimum_distance()

Keluaran referensi (cadangan statis)

Kita mengetahui bahwa matriks pemeriksa paritas dan matriks pembangkit berguna dalam konstruksi, deskripsi, dan analisis kode linear. Nama-nama metode Sage agak sukar dipahami. Sage memiliki rutin-rutin yang luas untuk menganalisis matriks dengan unsur dari berbagai lapangan, sehingga sebagian besar analisis lanjutan atas matriks-matriks ini kita lakukan di dalam Sage.

Kode Sage (cadangan statis)

C = H.parity_check_matrix(); C

Keluaran referensi (cadangan statis)

[1 0 1 0 1 0 1]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]

Matriks pembangkit dalam teks ini memiliki kolom-kolom yang merupakan kata kode, dan kombinasi linear dari kolom-kolom tersebut (ruang kolom matriks) merupakan kata kode. Dalam Sage, matriks pembangkit memiliki baris-baris yang merupakan kata kode, dan ruang baris matriks tersebut adalah kodenya. Jadi, di sini pun kita perlu menyesuaikan secara mental pilihan dalam teks dengan pilihan yang dibuat oleh para pengembang Sage.

Kode Sage (cadangan statis)

G = H.generator_matrix(); G

Keluaran referensi (cadangan statis)

[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[0 0 1 0 1 1 0]
[0 0 0 1 1 1 1]

Berikut adalah pengujian parsial bahwa kedua matriks ini benar, dengan menerapkan Lema 8.3.5. Perhatikan bahwa kita perlu menggunakan transpos dari matriks pembangkit, atas alasan yang dijelaskan di atas.

Kode Sage (cadangan statis)

C*G.transpose() == zero_matrix(3, 4)

Keluaran referensi (cadangan statis)

True

Perhatikan bahwa matriks pemeriksa paritas mungkin tidak kanonik dan matriks pembangkit mungkin tidak standar. Sage dapat menghasilkan matriks pembangkit yang memiliki sekumpulan kolom yang membentuk matriks identitas, meskipun tidak ada jaminan bahwa kolom-kolom tersebut merupakan kolom-kolom pertama. (Kolom, bukan baris.) Matriks semacam itu disebut sistematis, dan metode Sage-nya adalah .systematic_generator_matrix().

Kode Sage (cadangan statis)

H.systematic_generator_matrix()

Keluaran referensi (cadangan statis)

[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[0 0 1 0 1 1 0]
[0 0 0 1 1 1 1]

Subbagian 8.9.3 Mendekode dengan Kode Linear

Kita dapat mendekode pesan yang diterima dan berasal dari suatu kode linear. Misalkan kita menerima vektor biner dengan panjang \(7\text{,}\) yaitu r.

Kode Sage (cadangan statis)

r = vector(GF(2), [1, 1, 1, 1, 0, 0, 1]); r

Keluaran referensi (cadangan statis)

(1, 1, 1, 1, 0, 0, 1)

Kita dapat mengenali bahwa satu atau lebih kesalahan telah terjadi, sebab r tidak berada dalam kode, sebagaimana terlihat karena perhitungan berikut tidak menghasilkan vektor nol.

Kode Sage (cadangan statis)

C*r

Keluaran referensi (cadangan statis)

(1, 1, 0)

Suatu kode linear memiliki metode .decode. Anda dapat memilih di antara beberapa algoritma yang berbeda, sedangkan kode Hamming memiliki algoritma khusus tersendiri. Algoritma bakunya adalah pendekodean sindrom.

Kode Sage (cadangan statis)

H.decode_to_code(r)

Keluaran referensi (cadangan statis)

(1, 1, 0, 1, 0, 0, 1)

Jadi, jika kita bersedia mengasumsikan bahwa hanya satu kesalahan yang terjadi (asumsi yang mungkin kita ambil jika probabilitas kesalahan pada suatu entri tunggal vektor sangat rendah), kita melihat bahwa kesalahan terjadi pada posisi ketiga.

Ingatlah bahwa mungkin saja terjadi lebih dari satu kesalahan. Sebagai contoh, misalkan pesannya sama seperti sebelumnya dan kesalahan terjadi pada posisi ketiga, kelima, dan keenam.

Kode Sage (cadangan statis)

message = vector(GF(2), [1, 1, 0, 1, 0, 0, 1])
errors = vector(GF(2), [0, 0, 1, 0, 1, 1, 0])
received = message + errors
received

Keluaran referensi (cadangan statis)

(1, 1, 1, 1, 1, 1, 1)

Dalam keadaan ini, tampaknya kita telah menerima suatu kata kode, sehingga kita mengasumsikan bahwa sama sekali tidak ada kesalahan dan melakukan pendekodean secara keliru.

Kode Sage (cadangan statis)

H.decode_to_code(received) == message

Keluaran referensi (cadangan statis)

False

Kode Sage (cadangan statis)

H.decode_to_code(received) == received

Keluaran referensi (cadangan statis)

True

Sblm.Paling Atas Lanjut