Czy jest jakiś sposób na użycie półbitów?

19

Jak większość ludzi tutaj wie, używając 4 bitów jesteśmy w stanie policzyć od 0 do 15 (0123456789ABCDEF w systemie szesnastkowym). Ale gdybyśmy policzyli tylko do 9, nadal używalibyśmy 4 bity, a cyfry od A do F byłyby zmarnowane.

Jednak strona z kodem QR Wikipedii stwierdza, że ​​użycie tylko cyfr od 0 do 9 używa 3⅓ bitów na znak, co jest poprawne z statystycznego punktu widzenia. A jednak jedna trzecia bitu nie jest przedmiotem fizycznym, a wysłanie numeru od 0 do 9 wykorzystuje moją wiedzę o co najmniej 4 bitach.

Czy istnieje sposób na wykorzystanie zmarnowanych kombinacji, aby skutecznie wysłać postać z ułamkami bitów?

OK, podaję przykład: Dwie cyfry „27” muszą zostać wysłane. Przy normalnych technikach kodowania wysyłane bity miałyby wartość 00100111. Moglibyśmy wówczas wyobrazić sobie system, który zastąpiłby cyfrę „2” cyfrą „E” lub „F”, w zależności od następnego bitu; w tym przypadku następnym bitem jest 0, więc „2” zastępuje się „E”. Wynikowy ciąg bitów wynosiłby wtedy 1101 0 111. Z drugiej strony, jeśli cyfry „28” muszą zostać wysłane, pierwszy bit po „2” to 1, więc zamiast tego jest zastępowany cyfrą „F”, uzyskując ciąg 1111 1 000.

W obu przypadkach uzyskano oszczędność 1 bitu, ponieważ dla dwóch różnych znaków użyto jednego skrawka. Innymi słowy, trzy i pół bitu są używane na każdym znaku.

Galahad78
źródło
2
Aby spojrzeć z innej perspektywy na pakowanie wartości w mniejszej przestrzeni cyfrowej, sprawdź komputery Ternary ( en.wikipedia.org/wiki/Ternary_computer ) Jeśli jest wystarczająco dobry dla Knutha, to dla mnie wystarczający!
RLH
3
Jeszcze lepiej rozpoznać, że można to obliczyć (10 * first_digit) + second_digiti zakodować w 7 bitach, reprezentujących 0 ... 99, z kodami 100-127 pozostałymi dla innych rzeczy. I jeszcze więcej oszczędności dzięki 3 cyfrom skompresowanym do 10 bitów.
Hot Licks
Aby wysłać wszystkie 100 różnych wartości osobno, najlepiej jest zapakować w 7 bitów. Jeśli masz więcej cyfr, pakowanie będzie bardziej wydajne. Jeśli masz mniej niż 64 wartości do wysłania, możesz wysłać je przy użyciu tylko 6 bitów
phuclv,

Odpowiedzi:

22

Nie możesz wysłać pół bita, ale możesz skutecznie spakować dwa półbity w jednym bicie przed transmisją lub przechowywaniem.

Dajesz przykład sam, więc skutecznie odpowiedziałeś na swoje pytanie TAK.

Być może nieco łatwiejszym sposobem jest proste zakodowanie wartości dwóch cyfr dziesiętnych w 7 bitach. (Rodzaj podwójnie dziesiętnego kodowanego binarnie).

Wouter van Ooijen
źródło
1
Dobrym przykładem użycia do pakowania par cyfr w siedem bitów jest przesyłanie plików ASCII, które składają się głównie z danych liczbowych. Każda wartość bajtu poniżej 128 reprezentuje pojedynczy znak ASCII, a 128-227 reprezentuje dwie cyfry ASCII. Łatwy do kodowania lub dekodowania i nie wymaga, aby dane zawierały głównie cyfry (lub nawet dowolne cyfry), ale może bardzo łatwo kompresować ciągi cyfr o 50%.
supercat
Albo ten format PDP11, który upakował 3 znaki alfanumeryczne do 16 bitów z jednym bitem zapasowym ...
Brian Drummond,
@BrianDrummond: Można użyć 16 bitów do przechowywania dokładnie trzech znaków z zestawu 40, lub maksymalnie trzech z zestawu 39, ale nie byłoby wolnej części. Zwykle „alfanumeryczny” oznaczałby zestaw co najmniej 36, ale jedynym sposobem byłby zapasowy bit, gdyby zestaw był ograniczony do 32.
supercat
Myślałem, że to 5 bitów / char. Alfanumeryczny został podzielony na dwa zestawy kodów, z jednym symbolem zarezerwowanym dla „zestawu kodów przełączania”. Myliłem się: en.wikipedia.org/wiki/DEC_Radix-50 Wystarczająco dziwaczne, widziałem to jednak tylko jednej nocy, kiedy musiałem odkodować raport, który ktoś mi dał na 8-calowej dyskietce, w systemie CP / M, tylko z przyciemnieniem wspomnienie asm Z80
Brian Drummond,
19

Możesz użyć kodowania Huffmana, aby liczby miały różną długość bitów. jeśli znasz cyfrę, która pojawi się częściej niż inne, to pomoże.

przykład (z równym wystąpieniem):

0–1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

przykład odbioru na końcu dla uzyskania numeru 1:

Wchodzi pierwszy bit i pozostawia tylko 0 do 4 jako opcje.

wchodzi drugi bit i pozostawia tylko 0 do 2 jako opcje.

trzeci bit wchodzi i pozostawia 0 do 1 jako opcje.

pojawia się czwarty bit, a liczba przychodząca to 1

markg
źródło
12

Być może szukasz kodowania arytmetycznego, które może efektywnie kodować ciąg symboli, z których każdy w zasadzie może wymagać ułamkowej (niecałkowitej) liczby bitów. (chociaż łączna wiadomość musi zawierać całą liczbę bitów)

Cytując Wikipedię :

Kodowanie arytmetyczne różni się od innych form kodowania entropijnego, takich jak kodowanie Huffmana tym, że zamiast rozdzielać dane wejściowe na symbole składowe i zastępować je kodem, kodowanie arytmetyczne koduje całą wiadomość na pojedynczą liczbę, ułamek n gdzie (0,0 ≤ n < 1.0).

Hugh Allen
źródło
10

Nowy IEEE P754 do arytmetyki zmiennoprzecinkowej oprócz formatów binarnych definiuje teraz również formaty dziesiętne. Jedno z kodowań proponuje pogrupowanie cyfr cyfrowych według 3 na 10 bitów.

kodowanie od 0 do 999 przy użyciu 10 bitów = 1024 możliwych kodów jest dość wydajne, a cyfry dziesiętne są często i tak pogrupowane według trzech.

Gęsto zapakowany po przecinku : http://en.wikipedia.org/wiki/Densely_packed_decimal

TEMLIB
źródło
Nawet jeśli cyfry dziesiętne są pogrupowane według trzech, poprawna semantyka zmiennoprzecinkowa może wymagać (1) skalowania mantysy przez potęgę dziesiętną niepodzielną z trzech, co oznacza pomnożenie lub podzielenie wszystkich składników przez 10 lub 100; (2) niektóre bity mogą być użyte dla górnej lub dolnej części liczby, w zależności od (wykładnik mod 3); (3) Jeśli wykładnik jest przechowywany base-1000, wówczas dolna grupa trzech cyfr może czasami wymagać zaokrąglenia do najbliższej 10 lub najbliższej 100, a nie do najbliższej jednostki.
supercat
Osobiście uważam, że typy podobne BigDecimaldo wielu celów byłyby bardziej wydajne, gdyby każde słowo zawierało 9 cyfr dziesiętnych zamiast 32 bitów, ale grupowanie cyfr nie powinno mieć wpływu na zachowanie zaokrąglania.
supercat
4

Korespondencja binarna (lub szesnastkowa) 1: 1 to tylko jeden symbol kodujący bity. Tak, jak pokazałeś, jest to możliwe. Innym miejscem, w którym jest to używane, jest (ale nieco inaczej) kodowanie / dekodowanie kraty w systemach komunikacyjnych, w których przejścia bitów są umieszczone dalej od siebie, aby ułatwić dekodowanie. I oczywiście kodowanie 8b / 10b i 64b / 66b itp. Itd. Jest podobnym pomysłem, w którym mniejsza przestrzeń symboli jest kodowana w nieco redundantnej większej przestrzeni, aby uzyskać kody równowagi DC, separacji symboli i kontroli w podpasmach.

symbol zastępczy
źródło
4

Reprezentacja danych zależy od interpretacji, którą Ty lub Twój program je podajesz.

Możemy wysłać „27” również jako znaki ASCII, na przykład, dając 0x3237 = 0b0011001000110111.

xn(x)log2)n(x)

x1,x2)n(x1),n(x2))log2)n(x1)+log2)n(x2))log2)(n(x1)n(x2)))

2)log2)(10)=2)4=8log2)(1010)=7

Zawsze zależy to od aplikacji, ale zwykle, kiedy „łączysz” zmienne, jak sugerujesz, będzie to kosztować więcej mocy obliczeniowej, jeśli chcesz wykonywać operacje na tych zmiennych. Dodawanie i odejmowanie operacji na zmiennych „połączonych” jest bardziej złożone niż zwykle i może wymagać więcej miejsca w sprzęcie lub powodować dłuższe opóźnienia.



źródło
2

Zwykle sposób pakowania wartości polega na pomnożeniu każdej wartości przez jej zakres, dzięki czemu otrzymujesz jedną dużą liczbę, którą możesz skutecznie przedstawić w bitach. Podczas rozpakowywania dzielisz według zakresu, reszta to cyfra, a wynikiem są pozostałe spakowane cyfry.

Jeśli masz 5 wartości z zakresu od 0 do 2, możesz przedstawić to w 8 bitach (potrzebujesz co najmniej 7,92 bitów do przedstawienia wartości) zamiast 10 bitów używanych przez naiwny sposób używania 2 bitów dla każdej wartości, wykonując (((n 1 * 3 + n 2 ) * 3 + n 3 ) * 3 + n 4 ) * 3 + n 5

Rinze Smits
źródło
Czy istnieje nazwa dla tej metody kodowania?
Keegan Jay
1

Teoretycznie, jeśli chcesz wydać przestrzeń i energię na detektor o wysokiej impedancji, możesz wysłać 3 stany cyfrowym przewodem (1, 0 i wysokie Z). Oświadczenie: działa świetnie w symulatorze. Nie wiem, czy w obwodzie występują jakieś problemy, które sprawiają, że jest niepraktyczny, na przykład nie można tak szybko zmienić się jak zwykła para bram.

Mój normalny termin przejścia sygnału z wysokiej Z na sygnał (gdzie sygnał jest zwykle uziemiony w krzemie) to sygnał półbitowy.

Jozuego
źródło
1

Chcesz wysłać jedną cyfrę dziesiętną, wymagającą 3⅓ bitów. Ale będziesz musiał użyć 4 bitów, ponieważ nie możesz wysłać jednej trzeciej.

Tak więc, aby dowiedzieć się, co tak naprawdę oznaczają 3, bity, potrzebujesz dwóch (lub trzech) cyfr po 3⅓ bitu każdy. Jeśli chcesz wysłać 2 (3) cyfry dziesiętne z przedziału od 0 do 9, z których każda wymaga nieco mniej niż 3⅓ bitów, możesz to zrobić przy użyciu 7 (10) bitów. Konstruktywny dowód jest łatwy:

7 (10) bitów pozwala ci zakodować liczbę od 0 do 128 (1023) - ale potrzebujesz tylko 00 (000) do 99 (999), które wszystkie są możliwymi kodowaniami dwóch (trzech) cyfr dziesiętnych. CO BYŁO DO OKAZANIA

Alexander
źródło
1

Myślę, że nie rozumiesz, co oznacza linkowany artykuł wiki. Co to znaczy, że na ciąg znaków, który jest całkowicie liczbowa (bez spacji, przecinków, lub okresów), przy użyciu kompresji idealne, można reprezentować każdy znak przy użyciu 3 1 / 3 bity na średniej . W rzeczywistości jest to nieco lepsze, ponieważ matematyka mówi, że możesz uzyskać log 2 (10) = 3,3219 bitów / znak na dłuższą metę.

Podobnie, dla zestawu znaków alfanumerycznych plus niektórych symboli (tylko wielkie litery i 9 symboli) lub 45 znaków, potrzebujesz log 2 (45) = 5,4918 bitów / znak, który jest zaokrąglany w górę do 5,5 w artykule.

Zmniejszoną liczbę bitów / znaków uzyskuje się za pomocą kompresji, albo ze wstępnie ustawionym kodowaniem, albo ze schematu kompresji określonego przez standard QR (nie jestem pewien, który jest używany). Reprezentuje średnią liczbę bitów potrzebnych do zakodowania znaku, więc pojedynczy znak będzie zakodowany przy użyciu większej lub mniejszej liczby bitów. Pamiętaj również, że wartości wymienione powyżej są wartościami idealnymi dla nieskończonych, losowych ciągów. Możliwe jest uzyskanie lepszych lub gorszych współczynników kompresji dla specjalnie wykonanych strun.

MBraedley
źródło