Saya sedang melakukan beberapa transmisi data dari dsPIC ke PC dan saya sedang melakukan CRC 8-bit untuk setiap blok 512 byte untuk memastikan tidak ada kesalahan. Dengan diaktifkannya kode CRC saya mendapatkan sekitar 33KB / s, tanpa itu saya mendapatkan 67KB / s.

Apa beberapa alternatif algoritma deteksi kesalahan untuk memeriksa yang akan lebih cepat?

Meskipun mungkin ada opsi yang lebih cepat daripada CRC, jika Anda menggunakannya maka Anda cenderung mengorbankan beberapa tingkat kemampuan deteksi kesalahan. Bergantung pada apa persyaratan deteksi kesalahan Anda, alternatifnya mungkin menggunakan kode CRC yang dioptimalkan untuk aplikasi Anda.

Untuk perbandingan CRC dengan opsi lain, lihat jawaban yang sangat bagus oleh Martin Thompson .

Salah satu opsi untuk membantu ini adalah pycrc yang merupakan alat (ditulis dalam python ¹ ) yang dapat menghasilkan kode sumber C untuk puluhan kombinasi model dan algoritma CRC . Ini memungkinkan Anda untuk mengoptimalkan kecepatan dan ukuran untuk aplikasi Anda sendiri dengan memilih dan membandingkan berbagai kombinasi. ^{1: Membutuhkan Python 2.6 atau yang lebih baru.}

Ini mendukung crc-8 model , tetapi juga mendukung crc-5, crc-16dan di crc-32antara yang lainnya. Adapun algoritma , mendukung bit-by-bit, bit-by-bit-fastdan table-driven.

Misalnya (mengunduh arsip):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Anda bahkan dapat melakukan hal-hal yang funky seperti menentukan menggunakan pencarian nibble ganda (dengan tabel pencarian 16 byte) daripada mencari byte tunggal, dengan tabel pencarian 256 byte.

Sebagai contoh (kloning repositori git):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Mengingat keterbatasan memori dan kecepatan Anda, opsi ini mungkin merupakan kompromi terbaik antara kecepatan dan ukuran kode. Satu-satunya cara untuk memastikannya adalah dengan membandingkannya.

The pycrc git repositori pada github , seperti yang pelacak isu , tetapi juga dapat didownload dari sourceforge .

Paritas satu bit sederhana (pada dasarnya XOR data berulang-ulang) adalah secepat yang bisa didapat. Anda kehilangan banyak kesalahan saat memeriksa CRC.

Dalam pseudocode:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);

Makalah yang sangat bagus membandingkan kinerja berbagai checksum dan CRC dalam konteks tertanam:

Efektivitas Checksum untuk Jaringan Tertanam

Beberapa kutipan dari kesimpulan (berdasarkan studi mereka tentang probabilitas kesalahan yang tidak terdeteksi):

Saat burst burst mendominasi

XOR, penambahan komplemen dua, dan checksum CRC memberikan kinerja deteksi kesalahan yang lebih baik daripada penambahan komplemen seseorang, Fletcher, dan checksum Adler.

Di aplikasi lain

polinomial CRC "baik", jika memungkinkan, harus digunakan untuk tujuan deteksi kesalahan

Jika biaya perhitungan sangat dibatasi

(seperti dalam kasus Anda), gunakan (dalam urutan efektivitas):

• Checksum Fletcher
• tambahan pelengkap seseorang
• Selain itu melengkapi dua

Kutipan lainnya:

Fletcher checksum memiliki biaya komputasi yang lebih rendah daripada Adler checksum dan, bertentangan dengan kepercayaan populer, juga lebih efektif dalam kebanyakan situasi.

dan

Secara umum tidak ada alasan untuk melanjutkan praktik umum menggunakan checksum XOR dalam desain baru, karena ia memiliki biaya komputasi perangkat lunak yang sama dengan checksum berbasis penambahan tetapi hanya sekitar setengah efektif dalam mendeteksi kesalahan.

The Adler checksum harus cukup untuk memeriksa distorsi transmisi. Ini digunakan oleh pustaka kompresi Zlib, dan diadopsi oleh Java 3D Mobile Graphics Standard untuk memberikan pemeriksaan integritas data yang cepat namun efektif.

Dari halaman wikipedia :

Sebuah checksum Adler-32 diperoleh dengan menghitung dua checksum 16-bit A dan B dan menggabungkan bit-bit mereka ke dalam integer 32-bit. A adalah jumlah semua byte dalam string plus satu, dan B adalah jumlah nilai individu A dari setiap langkah.

Pada awal menjalankan Adler-32, A diinisialisasi ke 1, B ke 0. Jumlahnya dilakukan modulo 65521 (bilangan prima terbesar lebih kecil dari 2 ^ 16 atau 65536). Byte disimpan dalam urutan jaringan (big endian), B menempati dua byte paling signifikan.

Fungsi dapat dinyatakan sebagai

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

di mana D adalah string byte di mana checksum harus dihitung, dan n adalah panjang D.

Saya tidak mengetahui apa pun yang seefektif deteksi kesalahan sebagai CRC dan lebih cepat - jika ada, orang akan menggunakannya sebagai gantinya.

Anda dapat mencoba checksum sederhana, tetapi itu jauh lebih kecil kemungkinannya untuk mendeteksi kesalahan.

Logika checksum itu sendiri bagus dan orang dapat membantu dengan algoritma yang lebih cepat.

Jika Anda ingin meningkatkan kecepatan komponen Anda, Anda mungkin perlu melihat mengubah teknik keseluruhan Anda untuk memisahkan komponen transfer dari komponen validasi.

Jika Anda memiliki ini sebagai dua item independen (pada utas berbeda) maka Anda bisa mendapatkan kecepatan transfer penuh dan hanya mengirim ulang paket yang gagal.

Algoritma akan terlihat seperti:

• Server terpecah menjadi ukuran paket yang diketahui (katakanlah potongan 1K). Menempatkan mereka dalam antrian "untuk dikirim".
• Setiap paket dikirim dengan ID 16 atau 32 bit DAN checksum-nya.
• Klien menerima setiap paket dan menempatkannya dalam antrian untuk diproses.
• Pada utas terpisah, klien mengambil paket sekaligus, melakukan validasi.
  • Jika berhasil, ia menambahkannya ke koleksi akhir paket (dalam urutan ID)
  • Pada kegagalan itu melaporkan ID gagal kembali ke server, yang mengantri paket yang akan dikirim ulang.
• Setelah Anda menerima dan memvalidasi paket-paket dan Anda memiliki ID di sequnce yang benar (mulai dari 1) Anda dapat mulai menulis ini ke disk (atau melakukan apa pun yang diperlukan).

Ini akan memungkinkan Anda trasmit pada kecepatan setinggi mungkin dan jika Anda bermain dengan ukuran paket Anda, Anda bisa menghitung tingkat kegagalan optimium VS memvalidasi / mengirim ulang tingkat.

Checksum tradisional

(kurangi # '+ aliran)

XOR seperti yang diberikan di atas akan bekerja juga

(kurangi aliran XOR # ')

Skema yang sedikit lebih rumit (lebih lambat) adalah pemeriksaan paritas standar untuk koneksi serial.

Pada level ini, Anda memperdagangkan kebenaran untuk kecepatan. Ini terkadang akan gagal.

Pada tingkat paling canggih berikutnya, Anda dapat menggunakan beberapa jenis barang crc / hash.

Desain lain adalah meningkatkan ukuran blok yang digunakan untuk aliran.

Anda harus memiliki perkiraan tingkat kesalahan aktual untuk menyesuaikan pemilihan algoritma dan parameter untuk ukuran blok.