Memperbaiki kesalahan menggunakan Hamming (7,4)

19

Kode Hamming (7,4) kembali ke tahun 1950. Saat itu Richard Hamming bekerja sebagai ahli matematika di Bell Labs. Setiap Jumat, Hamming mengatur mesin penghitung untuk melakukan serangkaian perhitungan, dan mengumpulkan hasilnya pada hari Senin berikutnya. Menggunakan pemeriksaan paritas, mesin-mesin ini dapat mendeteksi kesalahan selama perhitungan. Frustrasi, karena terlalu sering menerima pesan kesalahan, Hamming memutuskan untuk meningkatkan deteksi kesalahan dan menemukan kode Hamming yang terkenal.

Mekanika Hamming (7,4)

Tujuan dari kode Hamming adalah untuk membuat satu set bit paritas yang tumpang tindih sehingga kesalahan bit tunggal (satu bit dibalik) dalam bit data atau bit paritas dapat dideteksi dan diperbaiki. Hanya jika ada beberapa kesalahan, kode Hamming gagal memulihkan data asli. Mungkin tidak melihat kesalahan sama sekali, atau bahkan memperbaikinya dengan salah. Karenanya dalam tantangan ini kita hanya akan berurusan dengan kesalahan bit-tunggal.

Sebagai contoh kode Hamming, kita akan melihat kode Hamming (7,4). Selain itu untuk 4 bit data d1, d2, d3, d4menggunakan 3 bit paritas p1, p2, p3, yang dihitung menggunakan persamaan berikut:

p1 = (d1 + d2 + d4) % 2
p2 = (d1 + d3 + d4) % 2
p3 = (d2 + d3 + d4) % 2

Codeword yang dihasilkan (bit data + paritas) berbentuk form p1 p2 d1 p3 d2 d3 d4.

Mendeteksi kesalahan berfungsi sebagai berikut. Anda menghitung ulang bit paritas, dan memeriksa apakah cocok dengan bit paritas yang diterima. Dalam tabel berikut, Anda dapat melihat, bahwa setiap variasi kesalahan bit tunggal menghasilkan pencocokan yang berbeda dari bit paritas. Oleh karena itu setiap kesalahan bit tunggal dapat dilokalkan dan diperbaiki.

error in bit | p1 | p2 | d1 | p3 | d2 | d3 | d4 | no error
-------------|---------------------------------------------
p1 matches   | no | yes| no | yes| no | yes| no | yes
p2 matches   | yes| no | no | yes| yes| no | no | yes
p3 matches   | yes| yes| yes| no | no | no | no | yes

Contoh

Biarkan data Anda 1011. Bit paritas adalah p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1dan p3 = 0 + 1 + 1 = 0. Gabungkan data dan bit paritas dan Anda mendapatkan kata sandi 0110011.

data bits   |   1 011
parity bits | 01 0
--------------------
codeword    | 0110011

Katakanlah selama transmisi atau perhitungan bit ke-6 (= bit data ke-3) terbalik. Anda menerima kata itu 0110001. Data yang diterima diduga adalah 1001. Anda menghitung paritas bit lagi p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. Hanya p1cocok dengan bit paritas codeword 0110001. Karenanya terjadi kesalahan. Melihat tabel di atas, memberi tahu kami bahwa kesalahan terjadi d3dan Anda dapat memulihkan data asli 1011.

Tantangan:

Tulis fungsi atau program, yang menerima kata (7 bit), salah satu bit mungkin salah, dan pulihkan data aslinya. Format input (melalui STDIN, argumen baris perintah, argumen cepat atau fungsi) dapat berupa string "0110001", daftar atau array [0, 1, 1, 0, 0, 0, 1]atau integer di MSB 0b0110001 = 49. Seperti dijelaskan di atas, urutan input adalah p1 p2 d1 p3 d2 d3 d4. Output (melalui nilai balik atau STDOUT) harus dalam format yang sama, tetapi dalam urutand1 d2 d3 d4 . Hanya kembalikan / hasilkan 4 bit data.

Ini adalah kode-golf. Karenanya kode terpendek menang.

Kasus uji:

1110000 -> 1000  # no error
1100000 -> 1000  # error at 1st data bit
1111011 -> 1111  # error at 2nd data bit
0110001 -> 1011  # error at 3rd data bit (example)
1011011 -> 1010  # error at 4th data bit
0101001 -> 0001  # error at 1st parity bit
1010000 -> 1000  # error at 2nd parity bit
0100010 -> 0010  # error at 3rd parity bit

Tampilkan cuplikan kode

code-golf error-correction coding-theory Jakube
sumber
1
Apakah ada alasan tertentu bit paritas terakhir diberikan setelah bit data pertama?
xnor
2
@ xnor Secara matematis tidak ada bedanya, di mana posisi bit paritas. Secara historis mereka ditempatkan pada posisi kekuasaan dua. Misalnya Hamming (15,11) memiliki bit paritas di posisi 1, 2, 4 dan 8.
Jakube
4
@ xnor Jika Anda mengambil [is_p3_wrong][is_p2_wrong][is_p1_wrong]di basis dua itu memberikan posisi bit yang salah dalam kata. (Berdasarkan tabel pada pertanyaan.) Ini mungkin akan berguna untuk beberapa algoritma.
randomra
Sangat bagus :) Ketika Anda menulis "Tulis fungsi atau program, yang menerima kata (7 bit), salah satunya mungkin salah, [...]" Saya pikir maksud Anda salah satu bit mungkin salah tetapi Anda sebenarnya mengatakan salah satu kata mungkin.
@Lembik Tentu, jelaskan.
Jakube

Jawaban:

6

Oktaf, 70 66 55 byte

Fungsi Fini mengatur matriks decodingH , menemukan kesalahan dan memperbaiki posisi kesalahan (jika ada). Kemudian mengembalikan bit data yang benar. Input adalah vektor baris standar.

@ Jakube menyarankan saya harus menggunakan Oktaf daripada Matlab di mana Anda dapat menggunakan indeks pada ekspresi, yang membuat semuanya lagi lebih pendek 11 byte:

F=@(c)xor(c,1:7==bi2de(mod(c*de2bi(1:7,3),2)))([3,5:7])

Berikut ini adalah solusi terpendek di Matlab , karena Anda tidak bisa langsung menggunakan pengindeksan pada ekspresi. (Ini bekerja di oktaf juga, tentu saja.) Mampu mengganti penambahan / mod2 dengan xor:

f=@(c)c([3,5:7]);F=@(c)f(xor(c,1:7==bi2de(mod(c*de2bi(1:7,3),2))))

Tua:

f=@(c)c([3,5:7]);F=@(c)f(mod(c+(1:7==bi2de(mod(c*de2bi(1:7,3),2))),2))
cacat
sumber
Terima kasih, tetapi ini tidak berhasil, sayangnya Anda hanya dapat mengakses variabel seperti itu ...
flawr
1
Belum Matlab diinstal, saya hanya menggunakan http://octave-online.net/, di mana ia bekerja Mungkin mengubah bahasa?
Jakube
Oh, aku sudah curiga bahwa oktaf bisa melakukannya, tapi kemudian aku akan mengubah bahasanya tentu saja, terima kasih banyak!
flawr
14

Piet 50x11 = 550

masukkan deskripsi gambar di sini

ukuran codel adalah 15. Tidak terlalu peduli tentang ukuran, tetapi melewati semua tes.

captncraig
sumber
4
Saya lebih suka ini mengingat konteks masalahnya.
1
@Optimizer "ukuran kode" pada dasarnya adalah faktor pembesaran dari program piet. Di sini, setiap pixel logis (atau codel) telah diperluas ke blok 15x15 untuk membuat visibilitas lebih mudah. Itulah yang saya maksud, bukan "ukuran kode"
captncraig
ah ..... salahku.
Pengoptimal
8

Python, 79

f=lambda x,n=0,e=3:e&~-e and f(x,n+1,(n&8)*14^(n&4)*19^(n&2)*21^n%2*105^x)or~-n

Ambil input dan output sebagai angka dengan bit paling signifikan di sebelah kanan.

Alih-alih mencoba pemulihan kesalahan, kami hanya mencoba menyandikan setiap pesan yang mungkin ndari 0 hingga 15 hingga kami mendapatkan penyandian yang agak jauh dari yang diberikan. Rekursi terus bertambahn hingga menemukan yang berfungsi dan mengembalikannya. Meskipun tidak ada penghentian eksplisit, itu harus berakhir dalam 16 loop.

Ekspresi (n&8)*14^(n&4)*19^(n&2)*21^n%2*105mengimplementasikan matriks Hamming bitwise.

Untuk memeriksa satu kesalahan, kami memperbaiki pesan yang diberikan dengan yang dihitung e, dan memeriksa apakah kekuatan dua (atau 0) dengan bit-trick klasik e&~-e==0. Tapi, kita tidak bisa benar-benar menetapkan variabel edalam lambda, dan kita merujuknya dua kali dalam ekspresi ini, jadi kita melakukan hack untuk meneruskannya sebagai argumen opsional ke langkah rekursif berikutnya.

Tidak
sumber
7

JavaScript (ES6), 92 87 81

Berfungsi mendapatkan dan mengembalikan integer di MSB.
Implementasinya sangat mudah berikut komentar @randomra:

  • calc p3wrong | p2wrong | p1wrong (baris 2,3,4)
  • gunakan itu sebagai bit mask untuk membalik bit yang salah (baris 1),
  • lalu kembalikan hanya bit data (baris terakhir)
F=w=>(w^=128>>(
  (w^w*2^w*4^w/2)&4|
  (w/8^w^w*2^w/16)&2|
  (w/16^w/4^w^w/64)&1
))&7|w/2&8

Tes di konsol Frefox / FireBug

;[0b1110000,0b1100000,0b1111011,0b0110001,
0b1011011,0b0101001,0b1010000,0b0100010]
.map(x=>x.toString(2)+'->'+F(x).toString(2))

Keluaran

["1110000->1000", "1100000->1000", "1111011->1111", "110001->1011", "1011011->1010", "101001->1", "1010000->1000", "100010->10"]
edc65
sumber
1
Saya sangat suka solusi operasi bitwise ringkas Anda =)
flawr
4

Python 2, 71

f=lambda i,b=3:i&7|i/2&8if chr(i)in'\0%*3<CLUZfip'else f(i^b/2,b*2)

Beberapa karakter adalah ASCII yang tidak dapat dicetak, jadi ini adalah versi yang lolos:

f=lambda i,b=3:i&7|i/2&8if chr(i)in'\0\x0f\x16\x19%*3<CLUZfip\x7f'else f(i^b/2,b*2)

Input dan output ke fungsi dilakukan sebagai bilangan bulat.

Saya mengambil keuntungan dari kenyataan bahwa jumlah pesan yang valid hanya 16, dan mengkodekan semuanya. Lalu saya mencoba membalik bit yang berbeda sampai saya mendapatkan salah satunya.

feersum
sumber
3

Haskell, 152 byte

a(p,q,d,r,e,f,g)=b$(d+e)#p+2*(d+f)#q+4*(e+f)#r where b 3=(1-d,e,f,g);b 5=(d,1-e,f,g);b 6=(d,e,1-f,g);b 7=(d,e,f,g-1);b _=(d,e,f,g);x#y=abs$(x+g)`mod`2-y

Penggunaan: a (1,1,1,1,0,1,1)output mana(1,1,1,1)

Solusi mudah: jika p<x>tidak cocok, atur bit <x>dalam angka. Jika angka ini 3, 5, 6atau 7, flip yang sesuai d<y>.

nimi
sumber
Bisakah Anda menambahkan beberapa instruksi tentang cara memanggil kode Anda (misalnya menggunakan kompiler online seperti ideone.com )? Saya selalu mendapatkan beberapa kesalahan aneh (sangat mungkin kesalahan saya).
Jakube
@Jakube: menyimpan kode ke dalam sebuah file, mengatakan hamming.hsdan beban ke dalam ghci Haskell repl: ghci hamming.hs. Panggil fungsi aseperti dijelaskan di atas. Satu-satunya juru bahasa haskell online yang saya ketahui ( tryhaskell.org ) memerlukan beberapa kode lagi:let a(p,q, ... 2-y in a (1,1,1,1,0,1,1)
nimi
3

Kode mesin IA-32, 36 byte

Hexdump:

33 c0 40 91 a8 55 7a 02 d0 e1 a8 66 7a 03 c0 e1
02 a8 78 7a 03 c1 e1 04 d0 e9 32 c1 24 74 04 04
c0 e8 03 c3

Kode C Setara:

unsigned parity(unsigned x)
{
    if (x == 0)
        return 0;
    else
        return x & 1 ^ parity(x >> 1);
}

unsigned fix(unsigned x)
{
    unsigned e1, e2, e3, err_pos, data;
    e1 = parity(x & 0x55);
    e2 = parity(x & 0x66);
    e3 = parity(x & 0x78);
    err_pos = e1 + e2 * 2 + e3 * 4;
    x ^= 1 << err_pos >> 1;
    data = x;
    data &= 0x74;
    data += 4;
    data >>= 3;
    return data;
}

CPU x86 secara otomatis menghitung paritas dari setiap hasil antara. Ini memiliki instruksi khususjp yang melompat atau tidak melompat tergantung pada paritas.

Itu tidak ditentukan secara eksplisit dalam tantangan, tetapi properti nyaman dari kode hamming adalah bahwa Anda dapat menafsirkan bit paritas sebagai angka biner, dan angka ini menunjukkan bit mana yang rusak selama transmisi. Sebenarnya, nomor ini berbasis 1, dengan 0 artinya tidak ada kesalahan transmisi. Ini diimplementasikan dengan menggeser 1 ke kiri err_poslalu ke kanan 1.

Setelah memperbaiki kesalahan transmisi, kode mengatur bit data dalam urutan yang diperlukan. Kode dioptimalkan untuk ukuran, dan mungkin tidak jelas pada awalnya cara kerjanya. Untuk menjelaskannya, saya menyatakan dengan a, b, c, dbit data, dan oleh P, Qdan Rparitas bit. Kemudian:

    data = x;     // d  c  b  R  a  Q  P
    data &= 0x74; // d  c  b  0  a  0  0
    data += 4;    // d  c  b  a ~a  0  0
    data >>= 3;   // d  c  b  a

Sumber perakitan ( fastcallkonvensi, dengan input masuk ecx, dan keluaran masuk eax):

    xor eax, eax;
    inc eax;
    xchg eax, ecx;

    test al, 0x55;
    jp skip1;
    shl cl, 1;

skip1:
    test al, 0x66;
    jp skip2;
    shl cl, 2;

skip2:
    test al, 0x78;
    jp skip3;
    shl ecx, 4;

skip3:
    shr cl, 1;
    xor al, cl;

    and al, 0x74;
    add al, 4;
    shr al, 3;

    ret;
anatolyg
sumber