Avere 4 stati per "bit" anziché 2 significa due volte lo spazio di archiviazione?

36

Semplice, fondamentale, anche se ingenua, domanda:

Avere 4 stati per "bit" anziché 2 significa due volte lo spazio di archiviazione? Nel caso in cui non sia chiaro, intendo come se ogni "struttura di memoria", anziché rappresentare solo 2 valori, (base 2: 0, 1), potesse rappresentare 4 valori (base 4: 0, 1, 2, 3 ).

    
posta Viziionary 10.10.2017 - 04:34
fonte

8 risposte

106

La parola che stai cercando non è "bit" ma "simbolo". "Simbolo" è la parola usata per descrivere il processo di mappatura di segnali hardware (come tensioni o schemi magnetici) in bit logici. Se un simbolo può avere 4 stati, può codificare informazioni di valore pari a 2 bit.

Naturalmente, non stiamo dicendo nulla sull'uso delle risorse del simbolo in quell'argomento. Se si inviano simboli lungo un filo come tensioni, i diversi simboli appaiono sempre più simili man mano che si aumenta il numero di stati per simbolo. Se ho un cavo 0-5V e 2 stati per simbolo (1 bit), i miei due stati sono 0V e 5V, con 5V tra ciascun simbolo. Se ho lo stesso filo, ma codifico 4 stati per simbolo (2 bit), i miei stati sono 0V, 1.66V, 3.33V e 5V. Quello è 1,66 V tra ogni simbolo. Adesso è più facile che il rumore corrompa il mio segnale.

C'è una legge che li riguarda, nota come Legge di Shannon che mette in relazione la larghezza di banda (in bit) alla frequenza degli errori che si verificano a causa del rumore sulla linea. Si scopre che c'è un limite al numero di bit che si possono stipare su un filo. L'utilizzo di più simboli porta a più errori, richiedendo più correzione degli errori.

Usiamo questa tecnica nella vita reale. La televisione digitale utilizza QAM-64, con 64 stati (e quindi 6 bit per simbolo). Ethernet utilizza 4 livelli di tensione, quindi 2 bit per simbolo.

Modifica: ho usato i tassi di trasmissione bit piuttosto che l'archiviazione perché è più comune vedere i simboli con più stati in trasmissione, quindi potrei rendere la storia più chiara. Se si desidera esaminare in modo specifico solo l'archiviazione e l'archiviazione, è possibile consultare celle multilivello nella memoria flash, come Some Somewhere menzionato nei commenti. Tale memoria usa lo stesso identico approccio, memorizzando 3 bit come 16 diversi livelli di carica di un condensatore. (o più!)

    
risposta data 10.10.2017 - 05:02
fonte
21

Una cella di memoria quarta può memorizzare esattamente tante informazioni quante 2 celle di memoria binarie:

Quaternary Binary
0          00
1          01
2          10
3          11

Quindi, se hai lo stesso numero di celle di memoria, ma sono di quarzo, allora hai il doppio della memoria. Ma se questa cella quadrupla occupa il doppio dello spazio su un chip, non c'è alcun vantaggio.

O in un altro modo, se avessi 1 gigaquad di una memoria quartaria, potrebbe memorizzare quante più informazioni di 2 gigabit di memoria binaria normale, perché ogni quad potrebbe essere espresso con due bit.

In un certo senso tutta questa linea di pensiero è solo di interesse accademico. Puoi già pensare che i chip di memoria memorizzino per esempio le celle di stato 2 ^ 32, perché non puoi recuperare 1 bit da loro, ottieni sempre una parola completa. E se in futuro qualcuno avesse trovato un modo per memorizzare quella parola nelle celle fisiche a 4 stati in modo più efficiente rispetto alle celle a 2 stati, allora sarebbe usato, ma non sarebbe visibile al di fuori del chip di memoria, gestirà comunque solo parole a memoria intera, che possono avere ad esempio 2 ^ 32 stati diversi.

    
risposta data 10.10.2017 - 13:09
fonte
9

Nella teoria di base, sì. In realtà no - perché in realtà non archiviamo i dati in bit (su HDD). Cort Ammon copre molto bene i problemi nella trasmissione dei dati. RAM, cache e SSD memorizzano i dati come bit, ma gli HDD sono diversi a causa della natura del loro materiale fisico e dei nostri sforzi per impacchettare più dati su di essi. La maggior parte dei dati è ancora archiviata su HDD, quindi mi concentrerò su quelli. Andrò ben oltre la spiegazione che troverai dalla maggior parte delle fonti, ma proverò a citare fonti dove posso. Queste fonti devono essere dissotterrate dalle antiche profondità di Internet perché è - in larga misura - una conoscenza veramente dimenticata.

In primo luogo, i dischi rigidi memorizzano le informazioni con campi magnetici sulla superficie dei piatti del disco. La testina di trasmissione legge questi rilevando il flusso dal cambiamento in quel campo - questo è molto più facile da misurare rispetto alla direzione effettiva e alla forza del campo magnetico. ma se il campo è 50 degli stessi segmenti in una riga, non può effettivamente contare che ce ne fossero 50 - legge un picco di flusso durante la lettura del primo segmento, quindi nessun flusso dopo un po 'e non può tracciare il tempo abbastanza accuratamente per essere certi che il campo è rimasto invariato per 50 segmenti.

Quindi, il modello di base (semplificato) è quello di memorizzare un po 'come una coppia di campi magnetici. Il primo sarebbe sempre un interruttore dal segmento precedente, e il secondo sarebbe un flip per rappresentare 1 o nessun flip per rappresentare 0. Quindi uno 0 è FN (flip-null) e un 1 è FF (flip-flip). I tempi del convertitore sono abbastanza precisi da riconoscere la differenza tra un picco di flusso e due picchi di flusso all'interno di un segmento. Questo formato è chiamato modulazione di frequenza. Quindi questo dà segnali chiari, MA significa che ogni bit di memoria richiede due spazi sul disco - questo è molto inefficiente. Quindi nessun disco rigido in realtà aveva questa forma più elementare di codifica; invece utilizzava semplici trucchi di compressione. La più semplice è Modified Frequency Modulation, che cambia il pattern in modo che il flip magnetico extra venga usato solo se uno 0 è preceduto da un altro 0. Ciò consente agli ingegneri di racchiudere quasi il doppio di dati nello stesso spazio, e quindi è stato usato sul primi HDD, ed è il formato su floppy disk. Dopo di che, un sistema più avanzato chiamato Run Length Limited è stato sviluppato con un'idea generale simile, a cui non entrerò perché diventa molto più complicato e ci sono più implementazioni.

Ma oggi non usiamo alcun sistema del genere. Invece, usiamo un sistema chiamato Partial Response, Maximum Likelihood (PRML). Il PRML richiede che la testa legga una lunghezza e raccolga il campione magnetico, quindi lo confronta con un insieme di riferimento di campioni memorizzati per determinare quale si adatta meglio. Rinuncia a tutto il concetto di picchi di flusso e utilizza invece la corrispondenza di modelli (io semplificano eccessivamente, ma ne vale la pena l'eccessiva semplificazione) e il modello corrisponde a un insieme di bit. Usa i filtri di rumore e altre tecnologie per rimuovere potenziali errori. È meglio pensarlo come una forma d'onda complessa e l'HDD sa come tradurre ogni forma d'onda in un insieme di bit. In questo senso, i dati vengono effettivamente archiviati più in un formato analogico che in uno digitale, perché il materiale fisico può supportare le variazioni graduali dell'analogico meglio dei salti improvvisi del digitale.

La migliore guida a questo è il link (premi il pulsante Avanti alcune volte per leggi tutto) e ci sono poche altre fonti - principalmente da persone che hanno creato enormi repository di conoscenza del computer che nessuno ha motivo di sapere. Una fonte addizionale decente (che è buona ma non del tutto perfetta al 100% per quanto ne so) è link

TL; DR: i dischi del disco rigido non memorizzano i dati in un formato diverso da 1 e 0; usano invece un'elaborazione complessa del segnale per inserire i segnali nello spazio più piccolo possibile e decodificarlo durante la lettura. Quindi, sono davvero indipendenti dalla base.

Non mi sorprenderebbe che in qualche punto si tentasse di archiviare la memoria di base 4 su SSD o RAM. Tutto dipende dalla fisica e dalla chimica dei materiali. Gli ingegneri e gli scienziati spingeranno questi materiali il più lontano possibile e perseguiranno qualsiasi percorso produca i migliori risultati.

    
risposta data 10.10.2017 - 21:21
fonte
6

Sì, avere più stati consentirà a ciascuna "cella" di archiviazione o ciascun simbolo su una linea di trasmissione dati di portare più informazioni.

Ma non c'è un pranzo gratis, dobbiamo effettivamente essere in grado di distinguere quegli stati. Abbiamo scoperto che è facile costruire porte logiche binarie e molto più difficile costruire porte che distinguono, elaborano e rigenerano più di due livelli logici.

E poi c'è il problema dei segnali attenuati. Su un sistema a due livelli puoi semplicemente progettare la soglia in modo che funzioni con l'attenuazione del caso peggiore, su un sistema a quattro stati in cui è prevista un'attenuazione significativa devi adattare le soglie alla particolare attenuazione del tuo sistema, non solo al peggiore -assetto attenuatore. In pratica, ciò significa che devi aggiungere un sistema di misurazione dell'attenuazione al tuo sistema di comunicazione.

Tutto ciò che ha detto ci sono situazioni in cui la complessità extra fa ha senso. Un sacco di SSD ora usano più di due livelli per cella flash (noto come MLC o TLC), i moderni protocolli di comunicazione ad alta velocità utilizzano quasi sempre codifiche multi-livello.

    
risposta data 10.10.2017 - 16:24
fonte
2

Potresti essere interessato a sapere che i russi hanno sviluppato un chip che era ternario , invece di binario. Ciò significa che ciascun simbolo potrebbe avere i valori di -1 , 0 o 1 . Quindi ogni porta fisica può memorizzare "tre" valori, anziché "due".

Potential future applications

With the advent of mass-produced binary components for computers, ternary computers have diminished in significance. However, Donald Knuth argues that they will be brought back into development in the future to take advantage of ternary logic's elegance and efficiency.

Come si inizia a sospettare, potrebbe esserci un modo più efficiente per implementare un sistema di numerazione di base. (Anche se questa capacità di esprimerlo in modo più efficiente dipende dalla nostra capacità di produrre materialmente sul materiale.) risulta che la costante e , la base del log naturale (~ 2.71828), ha la migliore economia di radix, seguita per 3, quindi 2, poi 4.

L'economia del Radix è la quantità di numero che puoi rappresentare rispetto a quanti simboli devi prendere per farlo.

Ad esempio, il numero matematico tre è rappresentato come 3 in base 10, ma come 11 in base 2 (binario). La Base 10 può esprimere numeri più grandi con meno simboli della scatola binaria, ma la tabella dei simboli della base 10 è 5x più grande (0 ... 9) della tabella dei simboli della base 2 (0, 1). Il confronto tra la potenza espressiva e le dimensioni del set di simboli è chiamato "economia del radix" (il radix è il numero della base, ad esempio 2 in binario o "base 2"). La domanda naturale che segue è, dove voglio essere in termini di questo compromesso? Quale numero dovrei adottare come radix? Posso ottimizzare il compromesso tra la potenza espressiva e la dimensione del set di simboli?

Se osservi il grafico nell'articolo radix economy in wikipedia, puoi confrontare le economie di varie basi. Nel nostro esempio, la base 2 ha un'economia radix di 1,0615, mentre la base 10 ha un'economia di 1,5977. Più basso è il numero, meglio è, quindi la base 2 è più efficiente della base 10.

La tua domanda di base 4 ha un'efficienza di 1.0615, che ha le stesse dimensioni della base 2 (o binaria), quindi adottarla sulla base 2 ti dà solo la stessa esatta di memoria per numero, in media.

Se ti stai chiedendo, allora c'è un numero ideale da adottare come base, questo grafico ti mostra che, non è un numero intero, ma la costante matematica e (~ 2.71828) che è la migliore, avendo un'economia di 1,0. Ciò significa che è il più efficiente possibile. Per ogni serie di numeri, in media, base e ti darà la migliore dimensione di rappresentazione di esso, data la sua tabella dei simboli. È il miglior "bang for your buck".

Quindi, anche se pensi che la tua domanda sia forse semplice ed essenziale, in realtà è sottilmente complessa e un argomento molto utile da considerare quando si progettano i computer. Se si potesse progettare un computer discreto ideale, l'uso della base 4 offre la stessa soluzione - lo stesso spazio per i costi - come binario (base 2); usare la base 3, o ternaria, offre un affare migliore rispetto al binario (ei russi hanno costruito un computer fisico, funzionante con rappresentazione di base 3 nei transistor); ma idealmente, useresti base e. Non so se qualcuno ha costruito un computer fisico funzionante con base e, ma matematicamente, offrirà una migliore quantità di spazio su binario e ternario - in effetti, la migliore quantità di tutti i numeri reali.

    
risposta data 11.10.2017 - 16:32
fonte
2

Crederesti che posso codificare la somma totale della conoscenza umana con una singola corrispondenza?

Se codifico un bit in una singola corrispondenza, i simboli potrebbero assomigliare a questo:

Conabbastanzafiammiferipossodirequalsiasicosa.Mapossodireildoppiodellastessapartitaseaggiungoaltriduesimboli.Chepotrebbeassomigliareaquesto:

Duevoltepiùinformazioniconlastessapartita!Behperchèno?Beneperchéfermarsi?Ruotaognisimbolodi45gradieraddoppiamodinuovo.30,15,ecosìvia.Prestohoabbastanzasimbolichepossodirequalsiasicosaetuttoconunasolacorrispondenza!Unavoltachelofaccioabbiamocomunqueunproblema.Cosadicequestacorrispondenza?

Come puoi essere sicuro di quale simbolo sia ora? Quanto tempo hai bisogno per essere sicuro? Questo è il problema. Più simboli aggiungo, più lo sforzo ti porta a distinguerli.

Would having 4 states per “bit” rather than 2 mean twice the storage space?

Se stiamo parlando di partita, allora sicuro. Ma, anche se ciò non ha rallentato la velocità di lettura della nostra partita, ora stiamo prendendo più spazio sul mio spazio di lavoro della mia cucina. È sempre qualcosa.

    
risposta data 12.10.2017 - 03:16
fonte
2

Se un bit aveva 4 stati anziché due in un simbolo (bit), allora sì avresti il doppio della quantità di memoria. Questo potrebbe o non potrebbe richiedere il doppio dello spazio, a seconda della tecnologia utilizzata.

C'è un esempio di vita reale che hai davanti ai tuoi occhi ogni giorno: Ethernet (che non è memoria, ma è simile nella misura in cui trasmette dati) hai, tra l'altro, l'ordinaria "veloce ethernet" a 100 MBit 100BASE-TX, e hai 1GbE ethernet.

Chiaramente, 1 GbE richiede frequenze 10 volte superiori a 100 MBit (poiché 100 MBit richiedono una frequenza 10 volte più alta di 10 MBit), ecco perché sono necessari anche cavi più costosi. Ovviamente.

Oops ... che non è affatto vero .

100 MBit ethernet trasmette su due coppie di cavi a 100 MHz mentre GbE trasmette a 125 MHz su 4 coppie di cavi.

Aspetta, quindi GbE è davvero solo 2 1/2 volte più veloce di 100 Mbit Ethernet? Ho solo 250 MBit / s in uscita?

No, utilizza anche la codifica 5-PAM, che può codificare 2,32 bit per impulso per ogni coppia di cavi, di cui 2 bit vengono utilizzati come informazioni effettive e il resto rende il segnale più resiliente al rumore. Grazie a questi bit frazionari, 1000BASE-T è in grado di eliminare anche la codifica 8B10B.

Quindi hai raddoppiato il numero di cavi e aumentato leggermente la frequenza, ma ottieni un throughput 10 volte maggiore!

Ora, se pensi che sia pura magia, guarda come funziona la televisione via cavo digitale , e se non lo sei ancora convinto, guarda in ADSL, che usa 32768-QAM per codificare 15 bit in un unico simbolo.
Lo stesso vecchio filo di rame, stessa banda di frequenza, 15 volte più cose che passano attraverso.

Modifica
Un altro esempio di vita reale molto ovvio che ho completamente dimenticato (dato che è troppo ovvio, apparentemente!) Che hai davanti ai tuoi occhi ogni giorno è: chiavette USB.
Quelle comunemente usano la memoria flash MLC . Cos'è quello? È un tipo di cella di memoria che memorizza uno dei quattro diversi livelli di carica. Questa è l'unità più piccola a cui è possibile accedere a livello hardware. Quindi potresti dire che i tuoi "bit" hanno effettivamente 4 stati (loro non , in realtà ottieni solo due bit invece di uno, e puoi comunque leggere solo i settori completi dal dispositivo ... ma si potrebbe discutibilmente guardare in questo modo).
Stesso numero di celle, ma doppio della memoria. Più economico, più piccolo, un po 'meno affidabile, ma ... in primo luogo, più economico .

    
risposta data 11.10.2017 - 13:46
fonte
-5

Avere 4 simboli per cifra anziché due significa che è possibile memorizzare il doppio delle informazioni in una singola cifra. Tuttavia, man mano che aumenti la quantità di cifre, puoi memorizzare in modo esponenziale più informazioni:

Qualsiasi n cifra in base 2 può codificare 2 ^ n stati mentre la base 4 può codificare 4 ^ n.

    
risposta data 10.10.2017 - 10:36
fonte

Leggi altre domande sui tag