Apakah ada cara untuk menggunakan setengah-bit?

Seperti yang diketahui kebanyakan orang di sini, dengan menggunakan 4 bit, kami dapat menghitung dari 0 hingga 15 (0123456789ABCDEF dalam heksadesimal). Tetapi jika kita hanya menghitung hingga 9, kita masih akan menggunakan 4 bit, dan digit dari A sampai F akan terbuang sia-sia.

Namun, halaman QR-Code Wikipedia menyatakan bahwa hanya menggunakan angka numerik dari 0 hingga 9 menggunakan 3⅓ bit per karakter, yang benar dari titik statistik. Namun sepertiga dari sedikit bukanlah objek fisik, dan mengirim angka dari 0 hingga 9 menggunakan setidaknya 4 bit untuk pengetahuan saya.

Apakah ada cara untuk menggunakan kombinasi yang terbuang untuk secara efektif mengirim karakter dengan fraksi bit?

OK, izinkan saya memberi contoh: Dua digit "27" harus dikirim. Dengan teknik pengkodean normal, bit yang dikirim adalah 00100111. Kita dapat membayangkan sebuah sistem yang akan menggantikan digit '2' dengan digit 'E' atau 'F', tergantung pada bit berikutnya; dalam hal ini bit berikutnya adalah 0, sehingga '2' diganti dengan 'E'. Bit-string yang dihasilkan kemudian akan menjadi 1101 0 111. Di sisi lain jika digit "28" harus dikirim, bit pertama setelah '2' adalah 1, jadi itu diganti dengan digit 'F' sebagai gantinya, menghasilkan string 1111 1 000.

Dalam kedua kasus, ekonomi 1 bit telah dipengaruhi, karena satu nibble digunakan untuk dua karakter yang berbeda. Dengan kata lain, tiga setengah bit digunakan pada setiap karakter.

Anda tidak dapat mengirim setengah bit, tetapi Anda dapat secara efektif mengemas dua setengah bit dalam satu bit sebelum pengiriman atau penyimpanan.

Anda memberikan contoh sendiri, sehingga Anda secara efektif telah menjawab pertanyaan Anda sendiri dengan YA.

Cara yang mungkin agak lebih mudah adalah dengan menyandikan nilai dua digit desimal dalam 7 bit. (Semacam kode biner dual-desimal).

Anda dapat menggunakan huffman coding sehingga jumlahnya dengan panjang bit yang bervariasi. jika Anda mengetahui angka yang akan terjadi lebih sering daripada yang lain, itu akan membantu.

contoh (dengan kejadian yang sama):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

menerima-contoh contoh untuk mendapatkan nomor 1:

Bit pertama masuk dan hanya menyisakan 0 hingga 4 sebagai opsi.

bit kedua masuk dan hanya menyisakan 0 hingga 2 sebagai opsi.

bit ketiga masuk dan meninggalkan 0 ke 1 sebagai opsi.

bit keempat datang dan nomor yang masuk adalah 1

Mungkin yang Anda cari adalah Arithmetic Coding, yang dapat secara efisien meng-encode serangkaian simbol, yang masing-masing secara prinsip mungkin memerlukan sejumlah bit (non-integer) bit. (meskipun total pesan harus sejumlah bit)

Mengutip Wikipedia :

Pengkodean aritmatika berbeda dari bentuk pengkodean entropi lainnya seperti pengkodean Huffman dalam hal itu daripada memisahkan input menjadi simbol komponen dan mengganti masing-masing dengan kode, pengkodean aritmatika menyandikan seluruh pesan menjadi satu nomor, fraksi n di mana (0,0 ≤ n < 1.0).

IEEE P754 baru untuk floating point arithmetic sekarang mendefinisikan format desimal selain biner. Salah satu pengodean mengusulkan untuk mengelompokkan digit digital dengan 3 menjadi 10 bit.

pengkodean 0 hingga 999 menggunakan 10 bit = 1024 kode yang mungkin cukup efisien, dan angka desimal sering dikelompokkan berdasarkan tiga.

Paket Desimal Padat : http://en.wikipedia.org/wiki/Densely_packed_decimal

Korespondensi biner 1: 1 (atau Heksadesimal) hanyalah satu simbol yang menyandikan bit. Jadi ya, seperti yang Anda tunjukkan itu mungkin. Tempat lain yang digunakan adalah (tetapi sedikit berbeda) dalam trellis encoding / decoding dalam sistem komunikasi di mana transisi bit disimpan lebih jauh untuk memudahkan decoding. Dan tentu saja 8b / 10b dan 64b / 66b dll. Pengkodean adalah ide yang sama, di mana ruang simbol yang lebih kecil dikodekan dalam ruang yang sedikit lebih besar untuk mendapatkan keseimbangan DC, pemisahan simbol dan kode kontrol dalam sub-band.

Representasi data tergantung pada interpretasi yang Anda atau program Anda berikan padanya.

Kami dapat mengirim '27' juga sebagai karakter ASCII, misalnya, menghasilkan 0x3237 = 0b0011001000110111.

Cara Anda ingin merepresentasikan data dalam bit tergantung pada aplikasi Anda. Pada akhirnya, dengan variabel$x$ dengan $n(x)$ nilai yang berbeda mungkin, Anda akan perlu ${\lceil\log_2{n(x)}\rceil}$ bit.

Sekarang anggaplah Anda memiliki dua variabel $x_1,x_2$ dengan $n(x_1),n(x_2)$nilai yang mungkin. Jika Anda menyimpannya secara terpisah, Anda akan membutuhkannya$\lceil\log_2n(x_1)\rceil+\lceil\log_2n(x_2)\rceil$bit. Namun, jika Anda menyimpannya bersama, Anda hanya perlu$\left\lceil\log_2\left(n(x_1)\cdot n(x_2)\right)\right\rceil$ bit.

Dalam contoh Anda dengan mengirim dua digit, kedua digit dapat memiliki 10 nilai yang berbeda. Jika Anda menyimpannya secara terpisah, Anda perlu$2\cdot\lceil\log_2(10)\rceil=2\cdot4=8$bit. Jika Anda menyimpannya bersama-sama, Anda perlu$\lceil\log_2(10\cdot10)\rceil=7$ bit.

Itu selalu tergantung pada aplikasi, tetapi biasanya ketika Anda 'bergabung' variabel seperti yang Anda sarankan, itu akan membutuhkan daya komputasi yang lebih besar jika Anda ingin melakukan operasi pada variabel-variabel ini. Menambah dan mengurangi operasi pada variabel 'bergabung' lebih kompleks dari biasanya, dan mungkin membutuhkan lebih banyak ruang dalam perangkat keras, atau menyebabkan penundaan lebih lama.

catatan: $\lceil\dots\rceil$adalah notasi untuk mengumpulkan .

The usual way to pack values is by multiplying each value with its range, so you end up with one large number that you can efficiently represent in bits. When unpacking you divide by range, the remainder is the digit, and the result is the remaining packed digits.

If you have 5 values in the range of 0 to 2, you can represent that in 8 bits (you need at least 7.92 bits to represent the values) instead of the 10 bits used by the naive way of using 2 bits for each value, by doing (((n₁ * 3 + n₂) * 3 + n₃) * 3 + n₄) * 3 + n₅

In theory, if you're willing to spend circuit space and power for the high-impedance detector you can send 3 states down a digital wire (1, 0, and high-Z). Disclaimer: this works great in the simulator. I don't know if the circuit has some problems that make it impractical, like say it can't really switch as fast as a normal pair of gates.

My normal term for a signal transition from high-Z to signal (where signal is usually ground in silicon) is a half-bit signal.

You want to send one decimal digit, needing 3⅓ bits. But you will have to use 4 bits, because you can't send a third of a bit.

So, to find out what 3⅓ bits really means, you need two (or three) digits of 3⅓ bits each. If you want to send 2 (3) decimal digits between 0 and 9, each needing slightly less than 3⅓ bits, you can do so using 7 (10) bits. Constructive proof is easy:

7 (10) bits allow you to encode a number between 0 and 128 (1023) - but you will only need 00 (000) to 99 (999), which are all possible encodings of two (three) decimal digits. Q.E.D.

I think you're misunderstanding what is meant in the linked wiki article. What is meant is that for a string of characters that is completely numeric (without spaces, commas, or periods), using ideal compression, you can represent each character using 3 ¹/₃ bits on average. Actually, it's a bit better than this, since the math says you can get log₂(10) = 3.3219 bits/character in the long run.

Similarly, for the set of alphanumeric plus some symbols (uppercase only, and 9 symbols), or 45 characters, you need log₂(45) = 5.4918 bits/character, which is rounded up to 5.5 in the article.

The reduced bits/character is achieved using compression, either with a preset encoding or a compression scheme specified by the QR standard (I'm not sure which is used). It represents the average number of bits a character will need in order to be encoded, so an individual character will be encoded using more or less bits. Also realize the values listed above are the ideal values for infinite, random strings. It's possible to get compression ratios that are better or worse for specially crafted strings.