salin an terje mahan cob a

5

Coding Teori

Penulis: Kenneth H. Rosen, AT & T Laboratories

Prasyarat:.Prasyarat untuk bab ini adalah dasar-dasar logika, mengatur teori, teori bilangan, matriks, dan probabilitas. (Lihat bagian 1.1, 1.6, 2.6, 2.7, dan 5.1 dari Matematika dan Aplikasi Its, Fifth Edition, oleh Kenneth H. Rosen.)

Pengantar

Cara biasa untuk mewakili, memanipulasi, dan mengirimkan informasi adalah dengan menggunakan bit string, yaitu , urutan nol dan satu. Hal ini sangat diFFIkultus, dan sering tidak mungkin, untuk mencegah kesalahan ketika data disimpan, diambil, dioperasikan pada, atau dikirimkan. Kesalahan dapat terjadi dari saluran bising komunikasi, gangguan listrik, kesalahan manusia, atau kesalahan peralatan. Demikian pula, kesalahan yang diperkenalkan ke data yang tersimpan selama jangka waktu yang panjang pada pita magnetik tape memburuk.

Hal ini sangat penting untuk memastikan transmisi yang handal ketika file com-puter besar dengan cepat ditransmisikan atau saat data dikirim melalui jarak jauh, seperti data yang dikirimkan dari pesawat antariksa miliaran mil jauhnya. Demikian pula, sering penting untuk memulihkan data yang telah terdegradasi sementara disimpan pada tape. Untuk menjamin transmisi yang handal atau untuk memulihkan data yang rusak, teknik dari teori pengkodean yang digunakan. Pesan, dalam bentuk bit string, dikodekan dengan menerjemahkan mereka ke dalam string sedikit lebih lama, yang disebut codeword. Satu set codeword disebut kode. Seperti yang akan kita lihat, kita dapat mendeteksi kesalahan ketika kita menggunakan kode-kode tertentu. Artinya, selama tidak terlalu banyak kesalahan yang telah dibuat, kita dapat de-termine apakah satu atau lebih kesalahan telah diperkenalkan ketika string bit yang ditransmisikan. Selanjutnya, ketika kode dengan lebih redundansi yang digunakan, kita dapat memperbaiki kesalahan.

Artinya, selama tidak terlalu banyak kesalahan diperkenalkan dalam transmisi, kita dapat memulihkan codeword dari bit string yang diterima saat codeword ini dikirim.

1

2 Aplikasi Matematika Diskrit

Coding teori, studi kode, termasuk kesalahan mendeteksi dan mengoreksi kesalahan kode, telah dipelajari secara ekstensif selama empat puluh tahun terakhir. Hal ini telah menjadi semakin penting dengan pengembangan teknologi baru untuk komunikasi data dan penyimpanan data. Dalam bab ini kita akan mempelajari baik mendeteksi kesalahan dan kode koreksi kesalahan. Kami akan memperkenalkan keluarga penting dari kode koreksi kesalahan. Untuk melampaui cakupan dalam bab ini dan untuk belajar tentang aplikasi terbaru dari coding teori dan perkembangan teknis terbaru, pembaca disebut referensi tercantum di akhir bab ini.

Kesalahan Mendeteksi Kode

Sebuah cara sederhana untuk mendeteksi kesalahan ketika bit string ditransmisikan adalah untuk menambahkan sedikit cek paritas pada akhir string. Jika bit string berisi bahkan jumlah 1s kita menaruh 0 di akhir string. Jika bit string mengandung ganjil 1s kita menempatkan 1 pada akhir string. Dengan kata lain, kita menyandikan pesan x1x2. . . xn

sebagai x1x2. . . xnxn +1,dimana paritas bit cek xn + 1 diberikan oleh

xn + 1 = (x1 + x2 +... + xn)mod 2.

Menambahkan sedikit jaminan cek paritas yang jumlahnya 1s dalam string diperpanjang harus bahkan. Sangat mudah untuk melihat bahwa codewords dalam kode ini sedikit string dengan bahkan jumlah 1s.

Perhatikan bahwa ketika sedikit cek paritas ditambahkan ke string bit, jika satu kesalahan yang dibuat dalam transmisi codeword, total jumlah 1s akan aneh. Akibatnya, kesalahan ini dapat dideteksi. Namun, jika dua kesalahan yang dibuat, kesalahan ini tidak dapat dideteksi, karena jumlah 1s dalam string diperpanjang dengan dua kesalahan akan tetap bahkan. Secara umum, setiap ganjil kesalahan dapat dideteksi, sedangkan bahkan jumlah kesalahan tidak dapat terdeteksi.

Contoh 1 Misalkan sedikit cek paritas ditambahkan ke string bit sebelum dikirim. Apa yang dapat Anda simpulkan jika Anda menerima string bit 1110011 dan 10111101 sebagai pesan

Solusi:Sejak string 1110011 mengandung ganjil 1s, itu tidak bisa menjadi codeword valid (dan harus, karena itu, mengandung ganjil kesalahan). Di sisi lain, string 10111101 berisi bahkan jumlah 1s. Oleh karena itu baik codeword valid atau mengandung bahkan jumlah kesalahan.

Cara lain yang sederhana untuk mendeteksi kesalahan adalah untuk mengulang setiap bit dalam pesan dua kali, seperti yang dilakukan dalam contoh berikut.

Contoh 2 Encode bit string 011.001 dengan mengulangi setiap bit dua kali

Solusi:.Mengulangi setiap bit dua kali menghasilkan codeword 001111000011.

Bab 5 Coding Teori 3

kesalahan Apa yang bisa dideteksi ketika kita ulangi setiap bit codeword dua kali? Karena codeword adalah mereka sedikit string yang berisi pasangan yang cocok bit, yaitu, di mana dua bit pertama setuju, bit ketiga dan keempat setuju, dan sebagainya, kita bisa mendeteksi kesalahan yang mengubah tidak lebih dari satu bit dari setiap pasangan ini cocok bit. Sebagai contoh, kita dapat mendeteksi kesalahan dalam bit kedua, bit ketiga, dan sedikit kedelapan ketika codeword memiliki delapan bit (seperti mendeteksi bahwa 01.101.110, menerima ketika codeword 00.001.111 dikirim, memiliki kesalahan). Di sisi lain, kita tidak dapat mendeteksi kesalahan ketika bit ketiga dan keempat keduanya berubah (seperti mendeteksi bahwa 00.111.111, menerima ketika codeword 00.001.111 dikirim, memiliki kesalahan).

Kode Sejauh ini kita telah membahas yang dapat digunakan untuk mendeteksi kesalahan. Ketika kesalahan yang terdeteksi, semua bisa kita lakukan untuk mendapatkan codeword yang benar adalah untuk meminta pengiriman ulang dan berharap bahwa tidak ada kesalahan akan terjadi ketika hal ini dilakukan. Namun, ada kode yang lebih kuat yang tidak hanya dapat mendeteksi tetapi bisa juga kesalahan yang benar. Kita sekarang mengalihkan perhatian kita untuk kode ini, disebut kode koreksi kesalahan.

Kesalahan Mengoreksi Kode

Kita telah melihat bahwa ketika redundansi termasuk dalam codeword, seperti ketika sedikit cek paritas ditambahkan ke string bit, kita dapat mendeteksi kesalahan transmisi. Kita bisa melakukan lebih baik jika kita memasukkan lebih banyak redundansi. Kami tidak hanya akan mampu mendeteksi kesalahan, tapi kami juga akan dapat memperbaiki kesalahan. Lebih tepatnya, jika suFFIsien beberapa kesalahan telah dibuat dalam transmisi codeword, kita dapat menentukan codeword dikirim. Hal ini digambarkan dengan contoh berikut3.

Contoh Untuk menyandikan pesan kita dapat menggunakan kode pengulangan tiga. Kami mengulangi pesan tiga kali. Artinya, jika pesan tersebut x1x2x3,kita encode sebagai x1x2x3x4x5x6x7x8x9 mana x1 = x4 = x7,x2 = x5 = x8,dan x3 = x6 = x9.The codeword yang valid adalah 000000000, 001001001, 010010010, 011011011, 100100100, 101101101, 110110110, dan 111111111.

Kami decode string bit, yang mungkin mengandung kesalahan, menggunakan aturan mayoritas sederhana. Misalnya, untuk menentukan x1,kita melihat x1,x4,dan x7.Jika dua atau tiga bit ini 1, kami

menyimpulkan bahwa x1 = 1. Jika tidak, jika dua atau tiga bit ini 0, kita menyimpulkan bahwa x1 = 0 Secara umum, kita melihat tiga bit yang sesuai untuk setiap bit dalam pesan asli. Kami memutuskan bahwa sedikit di pesan adalah 1 jika mayoritas bit dalam string yang diterima di posisi yang sesuai dengan bit ini adalah 1s dan kami memutuskan bit ini adalah 0 jika tidak. Menggunakan prosedur ini, kita benar decode pesan selama paling banyak satu kesalahan telah dibuat dalam bit yang sesuai untuk setiap bit dari pesan asli.

Misalnya, ketika kode pengulangan tiga digunakan, jika kita menerima 011111010, kami menyimpulkan bahwa pesan yang dikirim adalah 011. (Misalnya, kami memutuskan bahwa


pertama sedikit pesan itu 0 sejak bit pertama adalah 0, bit keempat adalah 1, dan bit ketujuh adalah 0, membawa kita untuk menyimpulkan bahwa bit keempat adalah salah.)

Untuk membuat ide-ide yang diperkenalkan oleh kode pengulangan tiga lebih tepat kita perlu memperkenalkan beberapa ide tentang jarak antara codeword dan kemungkinan kesalahan. Kami akan mengembangkan beberapa konsep penting sebelum kembali ke kesalahan kode koreksi.

Hamming Distance

Ada cara sederhana untuk mengukur jarak antara dua string bit. Kami melihat jumlah posisi di mana ini sedikit string differ. Pendekatan ini digunakan oleh Richard Hamming * di pekerjaan fundamental di coding teori.

Definisi 1 Jarak Hamming d (x, y) antara string bit x = x1x2. . . xn dan y = y1y2. . . yn adalah jumlah posisi di mana string ini differ, yaitu,

jumlah i (i = 1, 2,..., n) yang xi 6 = yi. Perhatikan bahwa jarak Hamming antara dua string bit sama dengan jumlah perubahan bit

individu yang diperlukan untuk mengubah salah satu string ke yang lain.

Kita akan menemukan pengamatan ini berguna nanti.

Contoh 4 Cari jarak Hamming antara string bit 01.110 dan 11.011 dan jarak Hamming antara bit senar 00000 dan 11111.

Solusi: Sejak 01.110 dan 11.011 differ di pertama, ketiga, dan kelima bit mereka, d (01110, 11011) = 3. Karena 00000 dan 11111 differ di semua lima bit, kita menyimpulkan bahwa d ( 00000, 11111) =

5.Hamming memenuhi jarak semua sifat-sifat fungsi jarak (atau metrik), sebagai teorema berikut menunjukkan.

* Richard W. Hamming (1915-1998) adalah salah satu pendiri teori coding modern. Ia lahir di Chicago dan menerima gelar BS dari University of Chicago, MA dari University of Nebraska, dan gelar Ph.D. dari University of Illinois pada tahun 1942. Dia dipekerjakan oleh University of Illinois 1942-1944 dan University of Louisville dari 1944 ke 1945. Dari 1945 hingga 1946 ia berada distaff Proyek Manhattan di Los Alamos. Dia bergabung Bell Telephone Laboratories pada tahun 1946, di mana ia bekerja sampai 1976. Penelitiannya sudah

termasuk bekerja di bidang coding teori, metode numerik, statistik, dan penyaringan digital. Hamming bergabung dengan fakultas dari Naval Postgraduate School di tahun 1976. Di antara penghargaan yang telah memenangkan adalah Turing Prize dari ACM dan IEEE Hamming Medal (bernama setelah dia).


Teorema 1 Misalkan d (x, y) mewakili jarak Hamming antara bit string x dan y panjang n. Kemudian:

(i) d (x, y) ≥ 0 untuk semua x, y (ii) d (x, y) = 0 jika dan hanya jika x = y (iii)d (x, y) = d (y, x) untuk semua x, y

(iv) d ( x, y) ≤ d (x, z) + d (z, y) untuk semua x, y, z

Bukti:.Properties (i), (ii), dan (iii) mengikuti segera dari definisi jarak Hamming . Untuk membuktikan (iv), kita menggunakan fakta bahwa d (x, y) adalah jumlah perubahan bit yang diperlukan untuk mengubah x ke y. Perhatikan bahwa untuk setiap string yang z panjang n jumlah perubahan yang diperlukan untuk mengubah x ke y tidak melebihi jumlah perubahan yang diperlukan untuk mengubah x ke z dan kemudian mengubah z ke y.

Bagaimana bisa jarak Hamming digunakan dalam decoding? Secara khusus, sup-berpose bahwa ketika codeword x dari C kode dikirim, bit string y diterima. Jika transmisi yang bebas dari kesalahan, maka y akan sama dengan x. Tetapi jika kesalahan yang diperkenalkan oleh transmisi, misalnya dengan garis bising, maka y tidak sama dengan x. Bagaimana kita bisa memperbaiki kesalahan, yaitu, bagaimana bisa kita memulihkan x?

Salah satu pendekatan akan menghitung jarak Hamming antara y dan masing-masing codeword di C. Kemudian untuk memecahkan kode y, kita mengambil codeword dari jarak Hamming minimum dari y, jika codeword seperti unik. Jika jarak antara codewords terdekat di C cukup besar dan jika suFFIsien beberapa kesalahan yang dibuat dalam transmisi, codeword ini harus x, codeword yang dikirim. Jenis decoding disebut tetangga terdekat decodingSolusi:..

Contoh 5 Gunakan terdekat tetangga decoding untuk menentukan kode yang kata dikirim dari C kode = {0000, 1110, 1011} jika 0110 diterima

Kami pertama menemukan jarak antara 0110 dan masing-masing codeword. Kami menemukan bahwa

d (0000, 0110) = 2 d (1110, 0110) = 1 d (1011, 0110) = 3.

Karena codeword terdekat dengan 0110 adalah 1110, kami menyimpulkan bahwa 1110 adalah codeword yang dikirim.

Akan terdekat tetangga decoding menghasilkan codeword kemungkinan besar yang dikirim dari string biner yang diterima? Hal ini tidak sulit untuk melihat bahwa itu akan jika setiap bit dikirim memiliki probabilitas p sama yang diterima tidak benar dan p <1/2. Kita sebut saluran transmisi dengan properti ini saluran simetris biner. Seperti saluran ditampilkan pada Gambar 1.

6 Aplikasi Matematika

Gambar 1. Saluran simetris biner.

Contoh 6 Misalkan ketika sedikit dikirim melalui saluran biner simetris probabilitas itu diterima salah adalah 0,01. ? Berapa probabilitas bahwa bit string 100010 diterima ketika bit string 000000 dikirim

Solusi: Sejak probabilitas sedikit diterima salah adalah 0,01, yang prob-kemampuan yang sedikit diterima dengan benar adalah 1-0,01 = 0,99. Untuk 100.010 yang akan diterima, ketika 000000 dikirim, perlu untuk pertama dan kelima bit yang akan diterima tidak benar dan yang lain empat bit yang akan diterima dengan benar. Prob-kemampuan yang ini terjadi adalah

(0.99)4(0,01)2 = ,000096059601.

Sekarang kita akan menunjukkan bahwa tetangga terdekat decoding memberi kita codeword yang paling mungkin dikirim, sehingga juga maksimum decoding kemungkinan.

Teorema 2 codeword Misalkan dari C kode biner ditransmisikan menggunakan saluran simetris biner. Kemudian, tetangga terdekat decoding dari string bit yang diterima menghasilkan codeword yang paling mungkin mengirim

Bukti:.Untuk membuktikan teorema ini pertama kita perlu mencari

probabilitas bahwa ketika codeword panjang n dikirim, string bit dengan kesalahan k di posisi yang ditentukan menerima. Karena probabilitas setiap bit diterima dengan benar adalah 1 - p dan probabilitas setiap bit diterima dalam kesalahan adalah p, maka bahwa kemungkinan kesalahan k di posisi yang ditentukan adalah pk(1 - p)n-

k.Sejak p <1/2 dan 1 - p> 1/2, bahwaberikut

pi(1 - p)n-i> pj (1 - p)n-j

setiap kali i <j. Oleh karena itu, jika i <j, probabilitas bahwa kesalahan string bit dengan i ditentukan diterima lebih besar dari probabilitas bahwa string bit dengan kesalahan j ditentukan diterima. Sejak lebih mungkin bahwa kesalahan yang dibuat pada posisi tertentu lebih sedikit ketika sebuah codeword yang ditransmisikan, tetangga terdekat decoding menghasilkan codeword yang paling mungkin.


Hamming jarak antara codewords dalam kode biner menentukan kemampuannya untuk mendeteksi dan / atau benar kesalahan. Kita perlu membuat definisi berikut sebelum memperkenalkan dua teorema kunci yang berkaitan dengan kemampuan ini.

Definisi 2 Jarak minimum dari C kode biner jarak terkecil antara dua codeword berbeda, yaitu,

d (C) = min {d (x, . y) | x, y ∈ C, x 6 = y}

Contoh 7 Cari jarak minimum dari

kodeC = {00000, 01110, 10011, 11111}menemukan.

Solusi: Untuk menghitung jarak minimum kode ini kita akan jarak antara setiap pasangan codeword dan kemudian menemukan terkecil seperti dis-dikan. Kami telah d (00000, 01110) = 3, d (00000, 10011) = 3, d (00000, 11111) = 5, d (01110, 10011) = 4, d (01110, 11111) = 2, dan d ( 10011, 11111) = 2. Kita melihat bahwa jarak minimum C adalah 2.

Contoh 8 Cari jarak minimum dari kode C = {000000, 111111}

Solusi:.Karena hanya ada dua codeword dan d (000000, 111111) = 6, jarak minimum dari kode ini adalah 6.

Jarak minimum kode memberitahu kita berapa banyak kesalahan yang dapat mendeteksi dan berapa banyak kesalahan yang dapat memperbaiki, sebagai dua teorema berikut menunjukkan.

Teorema 3 A C kode biner dapat mendeteksi sampai k kesalahan dalam codeword apapun jika dan hanya jika d (C) ≥ k + 1.

Bukti: Misalkan C adalah kode biner dengan d (C) ≥ k + 1. Misalkan

sebuah codeword x ditransmisikan dan diterima dengan k atau lebih sedikit kesalahan. Karena jarak minimum antara codeword setidaknya k + 1, bit string yang diterima tidak bisa codeword lain. Oleh karena itu, penerima dapat mendeteksi kesalahan ini.

Sekarang anggaplah bahwa C dapat mendeteksi sampai k kesalahan dan d (C) ≤ k. Kemudian ada dua codeword dalam C yang differ tidak lebih dari k bit. Hal ini kemudian memungkinkan untuk kesalahan k untuk diperkenalkan ketika salah satu codeword ini ditransmisikan sehingga codeword lainnya diterima, bertentangan dengan fakta bahwa C dapat mendeteksi sampai k kesalahan.


Teorema 4 A C kode biner dapat memperbaiki up k kesalahan dalam codeword apapun jika dan hanya jika d (C) ≥ 2 k + 1.

Bukti: Misalkan C adalah kode biner dengan d (C) ≥ 2 k + 1. Misalkan codeword x ditransmisikan dan diterima dengan k atau sedikit kesalahan sebagai bit string z, sehingga d (x, z) ≤ k. Untuk melihat C yang dapat memperbaiki kesalahan ini, diketahui bahwa jika y adalah codeword lain selain x, maka d (z, y) ≥ k + 1. Untuk melihat catatan ini bahwa jika d (z, y) ≤ k, maka oleh ketidaksamaan segitiga d (x, y) ≤ d (x, z) + d (z, y) ≤ k + k = 2k, bertentangan dengan asumsi bahwa d (C) ≥ 2 k + 1.

Sebaliknya, misalkan C dapat memperbaiki up k kesalahan. Jika d (C) ≤ 2k, maka ada dua codeword yang differ di 2k bit. Mengubah k bit di salah satu codeword ini menghasilkan sedikit string yangdiffersdari masing-masing dua codeword ini persis posisi k, sehingga membuat tidak mungkin untuk memperbaiki kesalahan k ini.

Contoh 9 Let C menjadi kode {00000000, 11111000 , 01010111, 10101111}. ? Berapa banyak kesalahan bisa C mendeteksi dan berapa banyak itu dapat memperbaiki

Solusi: Komputasi jarak antara codeword menunjukkan bahwa jarak min-Imum dari C adalah 5. Dengan Teorema 3, berikut bahwa C dapat mendeteksi sampai 5-1 = 4 kesalahan . . Sebagai contoh, ketika kita menggunakan C untuk mendeteksi kesalahan, kita dapat de-TECT empat kesalahan yang dibuat dalam transmisi ketika kita menerima 11110000 ketika codeword 00000000 dikirim

Berdasarkan Teorema 4, berikut bahwa C dapat memperbaiki hingga b (5-1 ) / 2c = 2 kesalahan. Sebagai contoh, ketika kita menggunakan C untuk memperbaiki kesalahan, kita bisa memperbaiki dua er-Rors diperkenalkan pada transmisi ketika kita menerima 11100000 ketika codeword 11111000 dikirim.

Kode Sempurna

Untuk memungkinkan koreksi kesalahan kami ingin membuat jarak minimum antara codeword besar. Namun hal ini batas berapa banyak codeword yang tersedia. Di sini kita akan mengembangkan terikat pada jumlah codeword dalam kode biner dengan jarak minimum yang diberikan.

Lema 1 Misalkan x adalah string bit dengan panjang n dan k itu adalah bilangan bulat positif yang tidak melebihi n. Lalu ada

C (n, 0) + C (n, 1) + · + C (n, k).

Bit string y panjang n sehingga d (x, y) ≤ k (di mana d adalah Hamming yang . dis-dikan)


Bukti: Biarkan saya menjadi bilangan bulat positif. Jumlah bit string y dengan d (x, y) = i sama dengan sejumlah cara untuk memilih lokasi di mana saya x dan y differ. Hal ini dapat dilakukan di C (n, i) cara. Ini mengikuti bahwa ada

C (n, 0) + C (n, 1) + · + C (n, k)string bit sehingga d (x, y) ≤ k.

Kita bisa menjelaskan pernyataan di Lema 1 dalam hal geometris. Dengan lingkup radius k berpusat di x kita maksud himpunan semua string bit y seperti

Pkyang d (x, y) ≤ k. Lema 1 mengatakan bahwa ada persis i = 0 C (n, i) sengatan bit dalam lingkup radius k berpusat di x.

Lema 2 Let C menjadi kode biner yang mengandung codeword panjang n dan membiarkan d (C) = 2k + 1. Kemudian diberi y bit string dengan panjang n, ada paling banyak satu codeword x sehingga y adalah di bidang radius k berpusat di x

Bukti:.Misalkan y adalah di bidang radius k berpusat di dua diffcodeword erent x1 dan x2.Kemudian d (x1,y) ≤ k dan d (x2,y) ≤ k. Oleh ketidaksetaraan segitiga untuk jarak Hamming ini menyiratkan bahwa

d (x1,x2)≤ d (x1,y) + d (x2,y) ≤ k + k = 2k,bertentangan fakta bahwa jarak minimum antara codeword yaitu 2k + 1.

Sekarang kita dapat memberikan terikat berguna pada berapa banyak codewords bisa dalam kode yang terdiri dari n-tupel yang dapat memperbaiki sejumlah tertentu dari kesalahan.

Teorema 5 Sphere Packing atau (Hamming) Bound Misalkan bahwa C adalah kode string bit dengan panjang n dengan d (C) = 2k + 1. Kemudian | C |, jumlah codeword di C, tidak dapat melebihi

2n

C (n, 0) + C (n, 1) + · . · + C (n, k)

Bukti: Ada 2n bit string dengan panjang n. Dengan Lemma 1 lingkup radius k berpusat pada codeword x mengandung

C (n, 0) + C (n, 1) + · + C (n, k)

string bit. Karena tidak ada bit string bisa berada di dua bidang tersebut (dengan Lemma 2), jumlah string bit dengan panjang n setidaknya sama besar dengan jumlah codeword kali jumlah string bit di setiap lingkup tersebut. Oleh karena itu,

2n ≥ | C | [C (n, 0) + C (n, 1) + · + C (n, k)]oleh.


Kami mendapatkan ketidaksetaraan yang kita inginkan dengan membagi Faktor kedua di sisi kanan dari ketidaksetaraan ini (dan menulis ketidaksetaraan dengan istilah yang lebih kecil pertama).

Contoh 10 Cari batas atas untuk jumlah codeword dalam kode C di mana codeword adalah string sedikit panjang tujuh dan jarak minimum antara codeword adalah tiga

Solusi:.Jarak minimum antara codeword adalah 3 = 2k + 1, sehingga k = 1. Oleh karena itu kemasan lingkup menunjukkan bahwa ada terikat tidak lebih dari

27 128

= = 16

8C (7, 0) + C (7,

1)codewords di kode tersebut.

Lingkup kemasan terikat memberi kita batas atas untuk jumlah codeword dalam kode biner dengan jarak minimum yang diberikan di mana codeword adalah string bit dengan panjang n. Kode yang benar-benar mencapai ini batas atas, yaitu, yang memiliki paling codeword mungkin, adalah dari minat khusus karena mereka adalah yang palingeFFIkodekesalahan efisien mengoreksi. Kode tersebut dikenal sebagai kode yang sempurnaSolusi:..

Contoh 11 Tunjukkan bahwa kode yang terdiri dari hanya dua codeword 00000 dan 11111 adalah kode biner sempurna

Jarak minimum antara codewords dalam kode ini 5. lingkup pengepakan negara terikat yang ada di paling

25

=

32

= 216

C (5, 0) + C (5, 1) + C (5, 2)

codeword dalam kode yang terdiri dari 5-tupel dengan jarak minimum 5. Karena ada 2 codeword dalam kode ini , itu adalah kode biner yang sempurna.

Kode dalam Contoh 11 disebut sepele kode yang sempurna karena hanya terdiri dari dua codeword, satu berisi hanya 0s dan lainnya hanya berisi 1s. Sebagai Latihan 8 menunjukkan, ketika n adalah bilangan bulat positif ganjil ada kode sempurna sepele yang terdiri dari dua codeword yang string bit dengan panjang n terdiri dari semua 0s dan semua 1s. Menemukan sempurna biner kode different dari kode sepele telah menjadi salah satu masalah yang paling penting dalam teori pengkodean. Pada bagian berikutnya kita akan memperkenalkan kelas kode biner yang sempurna dikenal sebagai kode Hamming.

Bab 5 Coding Teori

Generator Matriks

Sebelum menjelaskan kode Hamming, kita perlu untuk menggeneralisasi konsep sedikit cek paritas. Ketika kita menggunakan sedikit cek paritas, kita menyandikan pesan x1x2. . . xk sebagai x1x2. . . xkxk + 1 di mana xk + 1 = (x1 + x2 + · + xk)2. mod Untuk menggeneralisasi gagasan ini, kami menambahkan lebih dari satu cek bit. Lebih tepatnya, kita menyandikan pesan x1x2. . . xk sebagai x1x2. . . xkxk + 1.. . xn,di mana n terakhir - k bit xk +1,..., xn,adalah paritas bit cek, yang diperoleh dari bit k dalam pesan. Kami akan menjelaskan bagaimana bit cek paritas ditentukan.

Pertimbangkan pesan k-bit x1x2 · xk

sebagai 1 × k matriks x. Misalkan G ak × n matriks yang dimulai dengan k × matriks identitas k akuk.Artinya, G = (Ik| A), di mana A adalah × ak (n - k) matriks, yang dikenal sebagai generator matriks. Kami mengkodekan x sebagai E (x) = XG, di mana kita melakukan Modulo aritmatika 2. Coding menggunakan sedikit cek paritas dan menggunakan kode pengulangan tiga adalah kasus khusus dari teknik ini, seperti yang digambarkan dalam Contoh 12 dan 13.

Contoh 12 kita dapat mewakili encoding dengan menambahkan sedikit cek paritas untuk pesan tiga bit sebagai E (x) = XG, di mana

G = 1 0 0 10 1 0 1

.

0 0 1 1Perhatikan bahwa untuk mendapatkan G kami menambahkan kolom 1s ke I3,matriks identitas 3 × 3. Artinya, G = (I3| A), di mana

1

A = 1. 1

Contoh 13 Kita dapat mewakili pengkodean menggunakan pengulangan kode triple untuk pesan tiga bit sebagai E (x) = XG, di mana

1 0 0 1 0 0 1 0 0

G = 0 1 0 0 1 0 0 10.

0 0 1 0 0 1 0 0 1Perhatikan bahwa G dibentuk dengan mengulangi matriks identitas urutan tiga, aku3,tiga kali, yaitu,

G = (I3| I3| I3).

Kami sekarang mempertimbangkan contoh yang kita akan gunakan untuk mengembangkan beberapa ide penting=.


Contoh 14Suppose bahwa1 0 0 1 1 1

G = 0 1 0 1 10,

0 0 1 1 0 1

yaitu, G (I3| A), di mana

1 1 1

.A = 1 1 0

1 0 1Apa codewords dalam kode yang dihasilkan oleh generator matriks ini

Solusi:?Kami menyandikan masing-masing dari delapan pesan tiga-bit x = x1x2x3 sebagai E (x) = XG. Ini menghasilkan codeword 000000, 001101, 010110, 011011, 100111, 101010, 110001, dan 111100. Sebagai contoh, kita mendapatkan ketiga ini dengan menghitung

1 0 0 1 1 1 = (0 1 0 1 1 0).

E ( 010) = (0 1 0) G = (0 1 0)

0 1 0 1 1 0

0 0 1 1 0 1Sangat mudah untuk melihat bahwa kita dapat menemukan kata

kode dalam kode biner yang dihasilkan oleh G generator matriks dengan mengambil semua kombinasi linear yang mungkin dari baris G (karena aritmatika modulo 2, ini berarti semua jumlah dari himpunan bagian dari himpunan baris dari G). Pembaca harus memverifikasi ini untuk codeword dalam kode dalam Contoh 14.

Sangat mudah untuk melihat bahwa kode biner dibentuk dengan menggunakan matriks generator yang memiliki properti bahwa jumlah dua codeword lagi codeword. Artinya, mereka adalah kode linier. Untuk melihat ini, misalkan y1 dan y2 yang codeword yang dihasilkan oleh generator matriks G. Kemudian ada string bit x1 dan x2 sehingga E (x1)= y1 dan E (x2)= y2,dimana E (x) = XG. Oleh karena itu y1 + y2

juga merupakan codeword sejak E (x1 + x2)= y1 + y2.(Di sini kita menambahkan sedikit string dengan menambahkan komponen mereka dalam posisi yang sama menggunakan aritmatika modulo 2.)

Kami akan melihat bahwa ada cara mudah untuk menemukan jarak minimum dari kode linier. Sebelum kita melihat ini, kita perlu membuat definisi berikut.

Definisi 3 Berat dari codeword x, dinotasikan denganw (x), dalam kode biner adalah jumlah 1s dalam codeword ini.

Contoh 15 Cari bobot dari codeword 00000, 10111, dan 11111.

Solusi: Menghitung jumlah 1s di masing-masing codeword ini kita menemukan bahwa w (00000) = 0, w (10111) = 4, dan w (11111) = 5.


Lema 3 Misalkan x dan y adalah codeword dalam kode C. linear Kemudian d (x, y) = w (x + y)

Bukti:.Posisi dengan 1s di dalam x + y adalah posisi di mana x dan y differ. Oleh karena d (x, y) = w (x + y).

Kami juga akan membutuhkan fakta bahwa 0, string bit dengan semua 0s, milik kode linier.

Lemma 4 Misalkan C adalah kode linier tidak kosong. Maka 0 adalah codeword di C.

Bukti: Biarkan x menjadi codeword di C. Karena C adalah linear x + x = 0 milik C.

Teorema 6 Jarak minimum dari C kode linier sama dengan berat minimum dari codeword nol di C.

Bukti: Misalkan jarak minimal C d. Lalu ada kode-kata x dan y sehingga d (x, y) = d. Dengan Lemma 3 berikut bahwa w (x + y) = d. Oleh karena itu w, berat minimum codeword, tidak lebih besar dari d.

Sebaliknya, misalkan codeword x adalah codeword nol berat-min Imum. Kemudian menggunakan Lemma 4 kita melihat bahwa w = w (x) = w (x + 0) = d (x, 0) ≥ d. Berikut bahwa w = d, mendirikan teorema.

Paritas Periksa Matriks

Perhatikan bahwa dalam Contoh 14 bit string x1x2x3 dikodekan sebagai x1x2x3x4x5x6 di mana x4 = x1 + x2 + x3,x5 = x1 + x2,dan x6 = x1 + x3 (di sini, aritmatika dilakukan modulo 2). Karena kita melakukan aritmatika modulo 2, kita melihat bahwa

x1 + x2 + x3 + x4 = 0 x1 + x2 + x5 = 0 x1 + x3 + x6 = 0.

Selanjutnya, mudah melihat bahwa x1x2x3x4x5xadalah 6codeword jika dan hanya jika memenuhi sistem ini persamaan.


Kami dapat mengungkapkan sistem ini persamaan sebagai

x1

1 1 1 1 0 0 x2 0

1 1 0 0 1 0x3

= 0,x4

1 0 1 0 0 1x5

0

x6

yaitu,HE (x)t = 0,

di mana E (x)t adalah transpose dari E ( x) dan H, paritas cek matriks, diberikan oleh

H =

1 1 1 1 0 0

1 1 0 0 1 0|.

1 0 1 0 0 1Perhatikan bahwa H = (AtAkun-k).Dengan notasi ini kita melihat bahwa x = x1x2x3x4x5xadalah 6codeword jika dan hanya jika Hxt = 0, karena memeriksa persamaan ini adalah sama seperti memeriksa apakah persamaan cek paritas terus.

Secara umum , misalkan G adalah ak × n matriks pembangkit dengan

G = (Ik| A),

di mana A adalah × ak (n - k) matriks. Untuk G kita kaitkan H paritas cek matriks,dimana

H = (At| In-k).

Kemudian x adalah codeword jika dan hanya jika Hxt = 0. Perhatikan bahwa dari G generator matriks kita dapat menemukan paritas terkait memeriksa matriks H, dan sebaliknya, diberi cek paritas matriks H, kita dapat menemukan terkait Generator matriks G. Lebih tepatnya, diketahui bahwa jika H = (B | Ir),maka G = (In-r| Bt).

Kita telah melihat bahwa matriks cek paritas dapat digunakan untuk mendeteksi kesalahan. Artinya, untuk menentukan apakah x adalah codeword kita memeriksa apakah

Hxt = 0

Tidak hanya dapat paritas cek matriks digunakan untuk mendeteksi kesalahan, tetapi ketika kolom matriks ini adalah berbeda dan semua nol, ia juga dapat digunakan untuk memperbaiki kesalahan. Berdasarkan asumsi ini, anggaplah bahwa codeword x dikirim dan y yang diterima, yang mungkin atau mungkin tidak sama dengan x. Menulis y = x + e, dimana e adalah string kesalahan. (Kami memiliki e = 0 jika tidak ada kesalahan muncul dalam transmisi). Secara umum, kesalahan tali e memiliki 1s di posisi manay differsdari x dan 0s di semua posisi lain. Sekarang anggaplah bahwa hanya satu kesalahan telah diperkenalkan ketika x ditransmisikan. Kemudian e adalah bit string yang hanya


satu nol bit yang berada dalam posisi di mana x dan y differ, mengatakan posisi j. Sejak Hxt = 0, berarti

Hyt = H (xt + e)=Hxt + et =et =cj

di mana cj adalah kolom ke-j dari H.

Oleh karena itu, jika kita menerima y dan menganggap bahwa ada lebih dari satu kesalahan ini, kita dapat menemukan codeword x yang dikirim oleh komputasi Hyt.Jika ini adalah nol, kita tahu bahwa y adalah codeword dikirim. Jika tidak, itu akan sama dengan kolom j dari H untuk beberapa bilangan bulat j. Ini berarti bahwa bit j y harus diubah untuk menghasilkan x.

Contoh 16 Gunakan matriks cek paritas untuk menentukan codeword dari kode dalam Contoh 14 dikirim jika 001.111 diterima. Asumsikan bahwa paling banyak satu kesalahan dibuat

Solusi:.Kami menemukan bahwa

01 1 1 1 0 0 0 0

Hyt = 1 1 0 0 1 01

=1kelima.1

1 0 1 0 0 1 01

1

ini adalah kolom H. Jika mengikuti bahwa bit kelima dari 001.111 tidak benar. Oleh karena itu kata kode yang dikirim adalah 001101.

Hamming Kode

Kita sekarang dapat mendefinisikan kode Hamming. Kami mendefinisikan mereka menggunakan matriks cek paritasr.

Definisi kode 4 A Hamming order r di mana r adalah bilangan bulat positif, adalah kode yang dihasilkan ketika kita ambil sebagai cek paritas matriks H merupakan × (2r - 1) matriks dengan kolom yang semua 2r -. 1 string bit nol panjang r dalam urutan sehingga kolom r terakhir membentuk matriks identitas


Interchanging urutan kolom mengarah ke apa yang dikenal sebagai kode equiv-alent. Untuk rincian tentang kesetaraan kode pembaca disebut referensi di akhir bab iniSolusi:.

Contoh 17 Cari codewords dalam kode Hamming order 2.

Cek paritas matriks kode ini

H = 1 1 0 1. 0 11.

Oleh karena itu, matriks pembangkit G dari

Kami memiliki H = (B | I2)dimana B = 1

kode ini sama dengan G = (I3-2| Bt)= (1 1 1). Karena codeword adalah kombinasi linear dari baris G, kita melihat bahwa kode ini memiliki dua codeword, 000 dan 111. Ini adalah kode pengulangan linear order 3.

Contoh 18 Cari codewords dalam kode Hamming order 3.

Solusi: Untuk matriks cek paritas dari kode ini kita menggunakan

0 1 1 1 1 0 0H = 1 0 1 1 0 1 0

Kami memiliki H = (B | I3).di mana

1 1 0 1 0 0 1

1 1 101 0 1 1

B = 1 1 0 1Oleh karena itu generator matriks G kode ini

sama dengan

3. Bt)=

1 0 0 0 0 1 1G = (I 7 1 0 0 1 0 1

-0

|.0 0 1 0 1 1 00 0 0 1 1 1 1

16 codeword di C kode ini dapat ditemukan dengan mengambil semua kemungkinan jumlah dari barisan G. Kami meninggalkan ini sebagai latihan pada akhir bab ini.

Untuk menunjukkan bahwa kode Hamming adalah kode pertama yang sempurna kita perlu menetapkan dua lemmas.

Bab 5 Coding Teori

17Lema 5 A Hamming Kode pesanan r berisi 2n-r codeworddi mana n =2r - 1.

Bukti: Cek paritas matriks kode Hamming adalah r × n matriks karena itu, matriks generator kode ini adalah (n - r. ) × n matriks. Ingat bahwa codeword adalah kombinasi linear dari baris. Sebagai pembaca dapat menunjukkan, tidak ada dua kombinasi linear dari baris yang sama. Karena ada2n-r diffkombinasi linearerent baris, ada2n-r

diff.codeworderent dalam kode Hamming order r

Lema 6 Jarak minimum dari kode Hamming order r adalah 3 saat-pernah r adalah bilangan bulat positif

Bukti:.Cek paritas matriks Hr memiliki kolom yang semuanya nol dan tidak ada dua yang sama. Oleh karena itu, dari diskusi kita sebelumnya, kode Hamming order r dapat memperbaiki kesalahan tunggal. Dengan Teorema 3 kita menyimpulkan bahwa jarak minimum kode ini setidaknya 3. Di antara kolom Hr adalah sebagai berikut tiga kolom:

1 1 01 0 1

c1 = 0, c2 = 0, c3 =0.

..

..

..

...

0 0 0

Perhatikan bahwa c1 + c2 + c3 = 0 Biarkan x menjadi string bit dengan 1 di posisi kolom ini dan nol di tempat lain. Kemudian Hx= t0,karena c1 + c2 + c3.Berikut bahwa x adalah sebuah codeword. Sejak w (x) = 3, dengan Teorema 6 berikut bahwa jarak minimum tidak lebih dari 3. Kami menyimpulkan bahwa jarak minimum dari kode Hamming order r adalah 3.

Teorema 7 Kode Hamming order r adalah sempurna Koden-tupel..

Bukti: Misalkan n = 2r - 1. Dengan Lemma 5 kode Hamming order r berisi 2n-r, codeword yang masing-masing merupakan Dengan Lemma 6 jarak minimum dari kode Hamming order r adalah 3. Kami melihat bahwa kode ini mencapai jumlah maksimum codeword diizinkan oleh kemasan lingkup terikat. Untuk melihat ini, bahwadiketahui

2n-r(1 + C (n, 1)) = 2n-r(1 + n) = 2(1 + 2r - 1) = 2nn-r.

ini adalah batas atas lingkup-packing terikat. maka kode Hamming order r sempurna.

Dengan Teorema 7 kita melihat bahwa kode Hamming adalah contoh kode yang sempurna. Studi tentang Kode sempurna telah menjadi salah satu daerah yang paling penting dari

18 Aplikasi Matematika Terpisah

penelitiandi coding teori dan telah mengarah pada pengembangan dari banyak hasil penting. Lihat referensi di akhir bab ini untuk belajar tentang apa yang diketahui tentang Kode sempurna.

Ringkasan

Dalam bab ini kita telah mempelajari bagaimana kode dapat digunakan untuk deteksi kesalahan dan koreksi kesalahan. Kami telah memperkenalkan sebuah kelas penting dari kode yang dikenal sebagai kode Hamming. Namun, kita hanya menyentuh permukaan subjek yang menarik dan penting yang telah menjadi sangat penting untuk komputasi modern dan komunikasi. Pembaca yang tertarik dapat berkonsultasi dengan referensi yang terdaftar di akhir bab ini untuk belajar tentang banyak kelas lain dari kode yang memiliki aplikasi praktis.

Misalnya, gambar dari planet yang diambil oleh pesawat antariksa telah en-kode menggunakan kode yang kuat, seperti kode yang dikenal sebagai kode Reed-Muller (lihat [5] untuk rincian). Kode ini telah digunakan untuk mengkodekan string bit dengan panjang 6 mewakili kecerahan setiap pixel dari suatu gambar dengan string sedikit panjang 32. kode Reed-Muller ini terdiri dari 64 codeword, masing-masing string bit dengan panjang 32, dengan minimum jarak 16. Contoh lain yang menarik adalah penggunaan keluarga kode yang dikenal sebagai kode Reed-Solomon digunakan dalam rekaman audio digital (lihat [5] untuk rincian). Akhirnya, banyak konsep dan teknik dari kedua aljabar linier dan aljabar abstrak digunakan dalam pengkodean teori. Mempelajari teori pengkodean mungkin con-vinsi pembaca skeptis tentang penerapan beberapa daerah yang lebih abstrak matematika.

Disarankan Bacaan

1. E. Berlekamp, ed., Makalah Kunci dalam Pengembangan Teori

Coding, IEEE Press, 1974.

2. R. Hamming, Coding dan Teori Informasi, Prentice-Hall, 1980.

3. R. Hill, A Course Pertama di Coding Teori, Oxford University Press, 1986.

4. V. Pless, Pengantar Teori Error-Memperbaiki Codes, MIT Press, 1972.

5. S. Vanstone dan P. van Oorschot, Sebuah Pengantar Kesalahan Memperbaiki Codes dengan Aplikasi, Kluwer, 1989.


Latihan

1. Bisa string bit berikut telah diterima dengan benar jika bit terakhir adalah bit paritas?

A) 1000011 b) 111111000

c) 10101010101d) 110111011100

2. Cari jarak Hamming antara masing-masing pasangan berikut sedikit string.

a) 00000, 11111 b) 1010101, 0011100

c) 000000001, 111000000d) 1111111111, 0100100011

3. Misalkan bit string 01.011 dikirim menggunakan biner channel simetris di mana probabilitas bit yang diterima salah adalah 0,01. Berapa probabilitas

a) bahwabit string yang dikirim diterima? b) 11.011 diterima?

c) 01.101 diterima? d) 10111 diterima?

e) tidak lebih dari satu kesalahan hadir dalam bit string diterima?

4. Berapa banyak kesalahan masing-masing kode biner berikut dapat mendeteksi dan berapa banyak itu bisa benar?

a) { 0000000, 1111111}

b) {00000, 00111, 10101, 11011}

c) {00000000, 11111000, 01100111, 100101101}

5. Misalkan probabilitas kesalahan bit dalam transmisi melalui saluran simetris biner adalah 0,001. Berapa probabilitas bahwa ketika codeword dengan delapan bit dikirim dari kode dengan jarak minimal lima, bit string yang diterima diterjemahkan sebagai

codeword dikirim (ketika tetangga terdekat decoding

digunakan)??6. Menunjukkan bahwa jika jarak minimum antara codeword adalah empat adalah mungkin untuk memperbaiki kesalahan dalam satu bit dan untuk mendeteksi dua kesalahan bit tanpa koreksi.

7. Gunakan kemasan lingkup terikat untuk memberikan batas atas jumlah codeword dalam kode biner mana codeword adalah string sedikit panjang sembilan dan jarak minimum antara codeword lima.

8. Tunjukkan bahwa setiap kali n adalah bilangan bulat positif ganjil, kode biner yang terdiri dari dua string bit dengan panjang n yang berisi semua 0s atau semua 1s adalah kode yang sempurna.

9. Misalkan bahwa x dan y adalah string bit dengan panjang n dan m adalah jumlah posisi di mana kedua x dan y memiliki 1s. Menunjukkan bahwa w (x + y) = w (x) + w (y) -. 2m


10. Cari matriks cek paritas yang terkait dengan kode dibentuk dengan menambahkan sedikit cek paritas ke string sedikit panjang 4.

11. Cari matriks cek paritas yang terkait dengan pengulangan kode triple untuk string bit dengan panjang 3.

12. Misalkan matriks generator kode biner

1 0 0 0 1 1

1.

1 0 0 0 1 0 10 0 1 0 0 1 10 0 0 1 1 1 0

Apa cek paritas matriks H untuk kode ini?

13. Misalkan matriks cek paritas untuk kode biner

1 0 1 0 0

1 1 0 10.

0 1 0 0 1Apa generator matriks G untuk kode ini?

14. Cari 16 codewords dalam kode Hamming dari order 3 dijelaskan dalam Ex-cukup

18.?15. Kadang-kadang, bukan kesalahan, bit terhapus selama transmisi pesan atau dari tape atau media penyimpanan lainnya. Posisi, tetapi tidak nilai, sebuah bit terhapus dikenal. Kami mengatakan bahwa kode C dapat memperbaiki erasures r jika pesan yang diterima tanpa kesalahan dan dengan tidak lebih dari erasures r dapat dikoreksi dengan codeword unik yang setuju dengan pesan yang diterima di semua posisi yang tidak terhapus.

a) Tunjukkan bahwa biner Kode jarak minimum d dapat memperbaiki d -. 1 erasures

b) Tunjukkan bahwa kode biner dari jarak minimum d dapat memperbaiki kesalahan t dan erasures r jika d = 2t + r + 1.

Proyek Komputer

1. Mengingat kode biner, menentukan jumlah kesalahan yang dapat mendeteksi dan jumlah kesalahan yang dapat memperbaiki-.

2. Mengingat kode biner dengan k jarak minimum, di mana k adalah bilangan bulat positif, menulis sebuah program yang akan mendeteksi kesalahan dalam codeword di sebanyak k 1 posisi dan memperbaiki kesalahan di sebanyak b (k - 1)./ 2c posisi

Bab5 Coding Teori 21

Solusi 1.

Latihan

a) tidak ada b) ya ¸) ya d) ya6..

2. a) 5 b) 3 c) 4 d)

3. a) ,9509900499 b)0,096059601 c) ,0000970299 d) ,0000009801

e) ,9990198504

4.a) mendeteksi 6, benar 3

b) mendeteksi 1, benar 0 c) mendeteksi 4, yang benar 2.

5. 0,999999944209664279880021

6. Let C menjadi kode biner dengan d (C) = 4. Kami dapat memperbaiki satu kesalahan dan mendeteksi dua kesalahan sebagai berikut. Biarkan y menjadi bit string yang kita terima. If y is a codeword x or has distance 1 from a codeword x we decode it as x since, as can be shown using the triangle inequality, every other codeword would have distance at least three from y. If y has distance at least two from every codeword, we detect at least two errors, and we ask for retransmission.

7. 11 1)/2

C(n, j) =8. The minimum distance is n. We find that 2n/ (nj−

=0

(n

−

1)/2 n P

2n/2n−1 = 2, since C(n, j) = ( C(n, j))/2 = 2n/2 = 2n−1. Since=0 j=0

jP Pthere are two codewords in this code and this is the maximum number of codewords possible by the sphere packing bound, this code is perfect.

9. There is a 1 in a specified position in x + y if there is a 1 in this position in exactly one of x and y. Note that w(x) + w(y) is the sum of the number of positions where x is 1 and the number of positions where y is 1. It follows that the number of positions where exactly one of x and y equals 1 is this sum minus the number of positions where both x and y are 1. The result now follows.

10.H = (1 1 1 1 1).1 0 0 1 0 0 0 0 00 1 0 0 1 0 0 0 0

11. H =0 0 1 0 0 1 0 0 0

.1 0 0 0 0 0 1 0 0

0 1 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0 1

1 1 0 1 1 0 0

H =

1 0 1 1 0 1 0 .

12. 1 1 1 0 0 0 1

22 Applications of Discrete Mathematics

0 1 113. G =

1 0

0 1 0 1 1 .

14. 0000000, 0001111, 0010110, 0011001, 0110011, 0100101, 0101010, 0111100, 1000011, 1001100, 1010101, 1011010, 1100110, 1101001, 1110000, 1111111.

15. a) Suppose that when the codeword x is sent, y is received, where y contains l erasures, where l ≤ d − 1. Since the minimum distance between codewords is d there can be at most one codeword that agrees with y is the n − l positions that were not erased. This codeword is x. Consequently, we correct y to be x.

b) Suppose that when the codeword x is sent, y is received and y contains at m errors and l erasures, such that m ≤ t and l ≤ r. Suppose that S is the set of bit strings that agree with y in the n − l positions that were not erased. Then there is a bit string s1 ∈ S with d(x, s1) ≤ t. We will show that x is the only such codeword. Suppose that there was another codeword z ∈ S. Then d(z, s2) ≤ t for some string s2 ∈ S. By the triangle

inequality, we then would have d(x, z) ≤ d(x, s1) + d(s1, s2) + d(s2, z). But since the first and third terms in the sum of the right hand side of this inequality equal m and the middle term is no larger than l, it follows that d(x, z) ≤ m + l + m = 2m + l ≤ 2t + r, which is a contradiction since both x and z are codewords and the minimum distance between codewords is d = 2t + r + 1.

salin an terje mahan cob a

Documents