Apakah kode biner dengan panjang 6, ukuran 32 dan jarak 2 ada?

9

Masalahnya adalah untuk membuktikan atau menyangkal keberadaan , st, ; ; d (c_i, c_j) \ geq2,1 \ leq i <j \ leq32 . ( d singkatan jarak hamming)C|c|=6,cC|C|=32d(ci,cj)2,1i<j32d

Saya mencoba membuat kode yang memuaskan. Yang terbaik yang bisa saya dapatkan adalah membiarkan C=C×C , gabungan dari C={000,011,110,101} , yang berukuran 16. 32 kebetulan adalah batas atas teoritis ukuran, sekarang saya tidak tidak tahu apa yang harus dilakukan selanjutnya untuk menyelesaikan masalah.

Miangu
sumber

Jawaban:

9

Ya, ada set seperti itu. Anda sebenarnya berada di jalur yang benar untuk menemukan contoh berikut.

Biarkan C={c:|c|=6 dan bahkan ada angka 1 dalam c} . Anda dapat memeriksa yang berikut ini.

  • |C|=32 .
  • d(kamu,v)2 untuk semua , . (Faktanya, atau 4 atau 6.)kamu,vCkamuvd(u,v)=2

Berikut adalah empat latihan terkait, yang tercantum dalam urutan meningkatnya kesulitan. Seperti dalam pertanyaan, hanya kode biner yang bersangkutan.

Latihan 1. Berikan contoh lain dari himpunan 32 kata dengan panjang 6 dan jarak berpasangan minimal 2.

Latihan 2. Perlihatkan bahwa hanya ada dua perangkat seperti itu, seperti yang diberikan dalam jawaban dan dalam latihan 1.

Latihan 3. Buat generalisasi kata-kata di atas dengan panjang berapa pun dan jarak berpasangan minimal 2. (Petunjuk, .)32=261

Latihan 4. (generalisasi lebih lanjut yang dinyatakan dalam jawaban Yuval) Jika adalah ukuran maksimum kode panjang dan jarak berpasangan minimum , maka .A(n,d)ndA(d,2d)=A(n1,2d1)

John L.
sumber
1
Saya pikir mungkin juga 6, khusus untuk dan , karena keduanya dan karena keduanya memiliki angka genap 1. Atau apakah saya melewatkan sesuatu? d(u,v)u=000000v=111111uCvC
siegi
@siegi, terima kasih. Diperbarui.
John L.
@Miangu apakah jawaban saya bermanfaat? Sudahkah Anda mempertimbangkan untuk menerimanya?
John L.
7

Semua kata paritas genap dari kode linier dengan 2n-1 codeword dan jarak minimum 2 .

Lebih umum, jika SEBUAH2(n,d) adalah ukuran maksimum dari kode panjang n dan jarak minimum d , maka A2(n,2d)=A2(n1,2d1) .

Yuval Filmus
sumber
1
A(n,d)A2(n,d)
1
F2