Ter 4 estados por "bit" em vez de 2 significaria o dobro do espaço de armazenamento?

35

Pergunta bastante direta e fundamental, embora ingênua:

Ter 4 estados por "bit" em vez de 2 significaria o dobro do espaço de armazenamento? Caso isso não esteja claro, quero dizer como se toda "estrutura de armazenamento", em vez de representar apenas 2 valores (base 2: 0, 1), pudesse representar 4 valores (base 4: 0, 1, 2, 3 )

Viziionary
fonte
4
Não sei se isso significa 2x o espaço de armazenamento, pois há alguns custos com o armazenamento dos vários níveis.
precisa
13
Consulte Célula multinível , conforme usada em muita memória flash. Agora eles estão migrando para uma célula de nível triplo, ou três bits de dados por célula física.
Alguém em algum lugar
52
Um "bit" é definido como tendo dois estados; portanto, uma célula de armazenamento com quatro estados armazena dois bits por definição.
JacquesB
24
@ JacquesB enquanto tecnicamente correto (o melhor) não é claramente o que o autor da pergunta quis dizer.
MetaFight 10/10
11
Se um "bit" com 4 estados for tão gordo quanto dois "bits" com dois estados cada, o espaço de armazenamento será idêntico.
Mouviciel 10/10

Respostas:

105

A palavra que você está procurando não é "bit", mas "símbolo". "Símbolo" é a palavra usada para descrever o processo de mapeamento de sinais de hardware (como tensões ou padrões magnéticos) em bits lógicos. Se um símbolo pode ter 4 estados, pode codificar 2 bits em informações.

Obviamente, não estamos dizendo nada sobre o uso de recursos do símbolo nesse argumento. Se você estiver enviando símbolos ao longo de um fio como voltagens, os diferentes símbolos parecerão cada vez mais semelhantes à medida que você aumenta o número de estados por símbolo. Se eu tiver um fio de 0-5V e 2 estados por símbolo (1 bit), meus dois estados serão 0V e 5V, com 5V entre cada símbolo. Se eu tiver o mesmo fio, mas codificar 4 estados por símbolo (2 bits), meus estados serão 0V, 1,66V, 3,33V e 5V. Isso é 1,66V entre cada símbolo. Agora ficou mais fácil o ruído corromper meu sinal.

Existe uma lei que os relaciona, conhecida como Lei de Shannon, que relaciona a largura de banda (em bits) à taxa de erros que ocorrem devido ao ruído na linha. Acontece que há um limite para quantos bits você pode prender em um fio. O uso de mais símbolos leva a mais erros, exigindo mais correção de erros.

Nós usamos essa técnica na vida real. A televisão digital usa QAM-64, com 64 estados (e, portanto, 6 bits por símbolo). A Ethernet usa 4 níveis de tensão, portanto, 2 bits por símbolo.

Editar: usei taxas de transmissão de bits em vez de armazenamento, porque é mais comum ver símbolos com mais estados na transmissão, para que eu pudesse tornar a história mais clara. Se alguém deseja examinar especificamente armazenamento e armazenamento sozinho, pode-se observar células de vários níveis na memória flash, como Alguém em algum lugar mencionado nos comentários. Essa memória usa exatamente a mesma abordagem, armazenando 3 bits como 16 níveis de carga diferentes de um capacitor. (ou mais!)

Cort Ammon
fonte
1
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
maple_shaft
esta resposta está completamente errada por conta da Ethernet. Veja aqui - o 100Base-T usual possui MLT3 com 3 níveis e o 1000Base-T possui PAM5 com 5 níveis, 10GBase-T possui PAM16 com 16 níveis. Não há nenhuma versão da Ethernet com quatro níveis que eu conheça ou que eu possa encontrar em qualquer lugar. @CortAmmon, onde na Wikipedia você descobriu que a Ethernet tem 4 níveis de tensão? Eu ficaria mais do que feliz em investigar e verificar de onde isso vem.
vaxquis
21

Uma célula de memória trimestral pode armazenar exatamente tanta informação quanto duas células de memória binária:

Quaternary Binary
0          00
1          01
2          10
3          11

Portanto, se você tiver o mesmo número de células de memória, mas elas forem trimestrais, terá duas vezes mais memória. Mas se essa célula quádrupla ocupa duas vezes mais espaço em um chip, não há benefício.

Ou, de outro modo, se você tivesse 1 gigaquad de algum armazenamento quartenário, ele poderia armazenar tanta informação quanto 2 gigabits de memória binária normal, porque cada quad poderia ser expresso com dois bits.


De certa forma, toda essa linha de pensamento é apenas de interesse acadêmico. Você já pode pensar que os chips de memória armazenam, por exemplo, 2 ^ 32 células de estado, porque você não pode buscar 1 bit delas, sempre recebe uma palavra completa. E se, no futuro, alguém descobrisse uma maneira de armazenar essa palavra nas células físicas de quatro estados com mais eficiência do que nas células de dois estados, isso seria usado, mas não seria visível fora do chip de memória, ainda assim seria capaz de lidar com isso. somente palavras com memória cheia, que podem ter, por exemplo, 2 ^ 32 estados diferentes.

hyde
fonte
1
"Uma célula de memória trimestral pode armazenar exatamente tanta informação quanto 2 células de memória binária" verdadeira, mas 2 números da base-4 podem conter quatro vezes mais que dois valores da base-2.
21717 JimmyJames
1
@JimmyJames Quatro vezes mais estados possíveis não são a mesma coisa que quatro vezes mais armazenamento. Veja a conversa na resposta de Richard Dunn.
Sean Burton
2
Para mim, a pergunta óbvia de acompanhamento para esta resposta é: "Bem ... as células quádruplas ocupam o dobro de espaço no chip?".
Daniel Wagner
5
Depois refizemos: quatro vezes mais estados possíveis não são a mesma coisa que quatro vezes mais informações.
Sean Burton
1
@JimmyJames Isso é uma contradição. 2 células quádruplas equivalem a 4 células binárias. Então, você está dizendo que 4 células binárias armazenam 4 vezes mais informações que 2 células binárias, mesmo que sejam apenas o dobro de células. Você está errado, pelo menos se você calcular informações como "bits" (ou bytes ou terabytes).
Hyde
9

Na teoria básica, sim. Na realidade, não - porque na verdade não armazenamos dados em bits (nos HDDs). Cort Ammon cobre muito bem os problemas de transmissão de dados. RAM, cache e SSDs armazenam dados como bits, mas os HDDs são diferentes devido à natureza de seu material físico e aos nossos esforços para compactar mais dados neles. A maioria dos dados ainda é armazenada em HDs, então vou focar neles. Vou muito além da explicação que você encontrará na maioria das fontes, mas tentarei citar fontes onde eu puder. Essas fontes devem ser desenterradas das profundezas antigas da Internet, porque é - em grande parte - conhecimento verdadeiramente esquecido.

Primeiro, os discos rígidos armazenam informações com campos magnéticos na superfície dos pratos da unidade. A cabeça de acionamento lê esses dados detectando o fluxo da mudança naquele campo - isso é muito mais fácil de medir do que a direção e a força reais do campo magnético. mas se o campo tiver 50 dos mesmos segmentos consecutivos, não será possível contar que houve 50 - ele leu um pico de fluxo ao ler o primeiro segmento, depois nenhum fluxo por um tempo depois e não pode rastrear o tempo com precisão suficiente para ter certeza de que o campo não foi alterado para 50 segmentos.

Portanto, o modelo básico (simplificado) é armazenar um pouco como um par de campos magnéticos. O primeiro seria sempre uma alternância do segmento anterior e o segundo seria um flip para representar 1 ou nenhum flip para representar 0. Portanto, 0 é FN (flip-null) e 1 é FF (flip-flip). O tempo do inversor é preciso o suficiente para reconhecer a diferença entre um pico de fluxo e dois pontos de fluxo dentro de um segmento. Este formato é chamado de modulação de frequência. Portanto, isso fornece sinais claros, mas significa que cada bit de memória requer dois espaços na unidade - isso é muito ineficiente. Portanto, nenhum disco rígido realmente tinha essa forma mais básica de codificação; usou truques simples de compressão. A mais simples é a Modulação de Frequência Modificada, que altera o padrão para que o flip magnético extra seja usado apenas se um 0 for precedido por outro 0. Isso permite que os engenheiros agrupem quase o dobro de dados no mesmo espaço e, portanto, foram usados ​​nos primeiros HDDs, e é o formato em disquetes. Depois disso, um sistema mais avançado chamado Run Length Limited foi desenvolvido com uma idéia geral semelhante, na qual não vou entrar porque fica muito mais complicado e há várias implementações.

Mas não usamos nenhum sistema como esse hoje. Em vez disso, usamos um sistema chamado Resposta Parcial, Máxima Verossimilhança (PRML). O PRML exige que o cabeçote leia um comprimento e colete a amostra magnética e, em seguida, compare-o com um conjunto de referência de amostras armazenadas para determinar qual delas corresponde melhor. Ele renuncia a todo o conceito de picos de fluxo e usa a correspondência de padrões (simplifico demais, mas a simplificação excessiva vale a pena), e o padrão corresponde a um conjunto de bits. Ele usa filtros de ruído e outras tecnologias para remover possíveis erros. É melhor pensar nisso como uma forma de onda complexa, e o HDD sabe como converter cada forma de onda em um conjunto de bits. Nesse sentido, os dados são realmente armazenados mais em formato analógico do que digital,

O melhor guia para isso está em http://www.pcguide.com/ref/hdd/geom/data.htm (pressione o botão Avançar algumas vezes para ler tudo) e existem algumas outras fontes - principalmente de pessoas que criaram repositórios maciços de conhecimentos de informática que ninguém tem motivos para conhecer. Uma fonte adicional decente (que é boa, mas não 100% perfeita, tanto quanto eu sei) está em http://www.tomshardware.com/reviews/hard-drive-magnetic-storage-hdd,3005-6.html

TL; DR: Os discos do disco rígido não armazenam dados em um formato como 1 e 0; eles usam um processamento de sinal complexo para amontoar os sinais no menor espaço possível e decodificá-los ao ler. Então, eles são realmente agnósticos.

Eu não ficaria surpreso se o armazenamento base-4 fosse tentado em SSDs ou RAM em algum momento. Tudo depende da física e química dos materiais. Os engenheiros e cientistas empurrarão esses materiais o máximo que puderem e seguirão o caminho que produz os melhores resultados.

user3685427
fonte
Gostaria de discutir um conceito de armazenamento? Se armazenarmos símbolos com base em um plano de coordenadas em vez de sequencialmente, parece-me que poderíamos armazenar bits extras com base na posição das coordenadas e na posição relativa a outros bits. chat.stackexchange.com/rooms/66911/vizs-discussion-2
Viziionary
Manchester Coding foi desenvolvido para fita magnética e Phase Shift Keying para rádio. Idéias semelhantes ao que você está dizendo.
Não sabia disso, mas também não realmente surpreendeu.
11307 Walfrat
O armazenamento base-4 em SSDs é chamado MLC.
user253751
6

Sim, ter mais estados permitirá que cada "célula" de armazenamento ou cada símbolo em uma linha de transmissão de dados leve mais informações.

Mas não há almoço grátis, precisamos realmente distinguir esses estados. Acontece que é fácil construir portas lógicas binárias e muito mais difícil construir portas que distinguem, processam e regeneram mais de dois níveis lógicos.

E depois há a questão dos sinais atenuados. Em um sistema de dois níveis, você pode simplesmente projetar seu limite para que ele funcione com a atenuação do pior caso, em um sistema de quatro estados em que é esperada uma atenuação significativa. É necessário adaptar seus limites à atenuação específica do sistema, não apenas ao pior atenuação em caixa. Na prática, isso significa que você precisa adicionar um sistema de medição de atenuação ao seu sistema de comunicações.

Tudo o que disse, há situações em que a complexidade extra FAZ faz sentido. Muitos SSDs agora usam mais de dois níveis por célula flash (conhecida como MLC ou TLC); os protocolos modernos de comunicação de alta velocidade também quase sempre usam codificações em vários níveis.

Peter Green
fonte
Ternário não é muito difícil. Computadores foram construídos usando isso.
1
Sim, ternário é mais fácil que trimestral porque você só precisa distinguir "positivo", "negativo" e "desligado", em vez de precisar distinguir vários níveis do mesmo sinal. Ainda mais difícil que o binário.
Peter Green
2
O interessante do código Morse por rádio é que o sinal está ligado ou não. A condição não está presente não é informação. Portanto, não é a alternância de ligar e desligar que carrega informações, é o comprimento e o espaçamento dos pulsos ligados. Nenhum outro sistema de representação moderno funciona dessa maneira que eu conheço.
1
Códigos de barra? Barra e espaço separam os dígitos e a largura determina o valor.
Sopuli 10/10
@Sopuli ok, nesse caso, a parte escura do código de barras não reflete a luz; portanto, seria o estado "desligado" ou "sem sinal". Eu acho que meu argumento era que a codificação nem sempre é simplesmente dois estados de sinal, mas poderia ser sinal versus nenhum sinal, o que parece estranho, exceto em casos reais, como código Morse, códigos de barras, fala etc. Representações de computador geralmente não perdem espaço ao armazenar regiões "sem sinal", elas são mais eficientes que os sistemas de sinais físicos. No caso físico, não temos a liberdade de "avançar rapidamente" sobre as lacunas no conteúdo, precisamos esperar por elas.
2

Você pode estar interessado em saber que os russos desenvolveram um chip que era ternário , em vez de binário. Isso significa que cada símbolo pode ter os valores de -1, 0ou 1. Portanto, cada porta física poderia armazenar "três" valores, em vez de "dois".

Potenciais aplicações futuras

Com o advento dos componentes binários produzidos em massa para computadores, os computadores ternários diminuíram de importância. No entanto, Donald Knuth argumenta que eles serão trazidos de volta ao desenvolvimento no futuro para aproveitar a elegância e a eficiência da lógica ternária.

Quando você começa a suspeitar, pode haver uma maneira mais eficiente de implementar um sistema de numeração de base. (Embora essa capacidade de expressar isso de forma mais eficiente dependa de nossa capacidade de fabricar fisicamente o material.) Acontece que a constante e, a base do log natural (~ 2,71828), tem a melhor economia de raiz, seguida por 3 e 2, então 4.

Economia Radix é a quantidade de número que você pode representar versus quantos símbolos você precisa usar para fazer isso.

Por exemplo, o número matemático três é representado como 3na base 10, mas como 11na base 2 (binária). A base 10 pode expressar números maiores com menos símbolos que a lata binária, mas a tabela de símbolos da base 10 é 5x maior (0 ... 9) do que a tabela de símbolos da base 2 (0, 1). A comparação da potência expressiva com o tamanho do conjunto de símbolos é denominada "economia de raiz" (raiz sendo o número da base, por exemplo, 2 em binário ou "base 2"). A pergunta natural a seguir é: onde eu quero estar em termos dessa troca? Que número devo adotar como raiz? Posso otimizar a troca entre poder expressivo e tamanho do conjunto de símbolos?

Se você olhar para o gráfico no artigo de economia básica na wikipedia, poderá comparar as economias de várias bases. Em nosso exemplo, a base 2 tem uma economia de raiz de 1,0615, enquanto a base 10 tem uma economia de 1,5977. Quanto menor o número, melhor, portanto, a base 2 é mais eficiente que a base 10.

Sua pergunta sobre a base 4 tem uma eficiência de 1,0615, que é do mesmo tamanho da base 2 (ou binária), portanto, adotá-la sobre a base 2 fornece apenas o mesmo tamanho exato de armazenamento por número, em média.

Se você está se perguntando, existe um número ideal para adotar como base, este gráfico mostra que, não é um número inteiro, mas a constante matemática e(~ 2,71828) que é a melhor, com uma economia de 1,0. Isso significa que é o mais eficiente possível. Para qualquer conjunto de números, em média, a base efornecerá o melhor tamanho de representação, considerando sua tabela de símbolos. É o melhor "retorno do seu investimento".

Portanto, embora você ache que sua pergunta talvez seja simples e básica, ela é realmente sutilmente complexa e é uma questão muito interessante a considerar ao projetar computadores. Se você pudesse projetar um computador discreto ideal, usar a base 4 oferece o mesmo negócio - o mesmo espaço de custo - que o binário (base 2); o uso da base 3, ou ternário, oferece um acordo melhor do que o binário (e os russos construíram um computador físico e funcional com representação da base 3 em transistores); mas, idealmente, você usaria a base e. Não sei se alguém construiu um computador físico funcional com base e, mas matematicamente, ele ofereceria uma melhor quantidade de espaço do que o binário e o ternário - na verdade, o melhor negócio de todos os números reais.

user1936
fonte
isso nem parece tentar resolver a questão, ter 4 estados por "bit" em vez de 2 significaria o dobro do espaço de armazenamento? Veja como responder
gnat
@gnat Acho que o conceito de economia radix trata diretamente da quantidade de dados que você obtém por símbolo. Não apenas responde ao caso de 4, mas também ao caso de qualquer número. É a solução geral.
user1936
1
I duas vezes verificada no link Wikipedia escondido sob "acaba" e, francamente, eu ainda não consigo ver como ele se relaciona com o espaço de armazenamento
mosquito
2
@gnat Atualizei a resposta. Felizmente, neste ponto, você vê como, pelo menos, tenta responder à pergunta.
user1936
2

Você acreditaria que posso codificar a soma total do conhecimento humano com uma única correspondência?

Se eu codificar um pouco em uma única correspondência, os símbolos podem ficar assim:

insira a descrição da imagem aqui insira a descrição da imagem aqui

Com fósforos suficientes, posso dizer qualquer coisa. Mas posso dizer o dobro da mesma correspondência se adicionar mais dois símbolos. Que pode ser assim:

insira a descrição da imagem aqui insira a descrição da imagem aqui

O dobro de informações com a mesma correspondência! Bem, porque não? Bem, por que parar? Gire cada símbolo 45 graus e dobramos novamente. 30, 15 e assim por diante. Em breve tenho símbolos suficientes para dizer tudo e qualquer coisa com apenas uma partida! Uma vez que faço isso, temos um problema. O que esta partida diz?

insira a descrição da imagem aqui

Como você pode ter certeza exatamente de qual símbolo está agora? Quanto tempo você precisa ter certeza? Esse é o problema. Quanto mais símbolos adicionar, mais esforço será necessário para diferenciá-los.

Ter 4 estados por "bit" em vez de 2 significaria o dobro do espaço de armazenamento?

Se estamos falando por partida, com certeza. Mas, mesmo que isso não diminua a velocidade da leitura, agora estamos ocupando mais espaço no meu balcão da cozinha. Sempre é alguma coisa.

candied_orange
fonte
É basicamente assim que funcionam os esquemas de modulação por rádio, como Quadrature AM e Phase Modulation. Se você quiser se divertir de verdade, estude como os vetores de fase rotativos representam dois tons simultâneos na banda lateral única ou na FM.
2

Se um bit tivesse 4 estados em vez de dois em um símbolo (bit), sim, você teria o dobro da quantidade de memória. Isso pode ou não ocupar o dobro de espaço, dependendo da tecnologia usada.

Há um exemplo da vida real que você tem diante de seus olhos todos os dias: Ethernet (que não é memória, mas é semelhante na medida em que transmite dados), você tem, entre outros, o "fast ethernet" comum a 100 MBit 100BASE -TX, e você tem 1GbE Ethernet.

Claramente, 1GbE requer frequências 10 vezes mais altas que 100 MBit (como 100 MBit requer frequência 10 vezes maior que 10 MBit), é por isso que você também precisa de cabos mais caros. Obviamente.

Opa ... isso não é verdade .

Ethernet de 100 MBit transmite mais de dois pares de cabos a 100 MHz, enquanto GbE transmite a 125 MHz e mais de 4 pares de cabos.

Espere, então o GbE é realmente apenas duas vezes e meia mais rápido que a Ethernet de 100 Mbit? Eu só ganho 250 MBit / s?

Não, ele também usa a codificação 5-PAM, que pode codificar 2,32 bits por pulso por par de cabos, dos quais 2 bits são usados ​​como informações reais e o restante torna o sinal mais resistente ao ruído. Graças a esses bits fracionários, o 1000BASE-T também pode eliminar a codificação 8B10B.

Então, você dobrou o número de fios e aumentou um pouco a frequência, mas obtém 10 vezes mais taxa de transferência!

Agora, se você acha que isso é pura mágica, veja como a televisão digital a cabo funciona e, se ainda não está convencido, veja o ADSL, que usa 32768-QAM para codificar 15 bits em um símbolo.
O mesmo velho fio de cobre, a mesma banda de frequência, 15 vezes mais coisas passando.

EDIT:
Outro exemplo muito óbvio da vida real que eu esqueci completamente (já que é óbvio demais!) Que você tem diante de seus olhos todos os dias é: pendrives USB.
Aqueles geralmente usam memória flash MLC . O que é isso? É um tipo de célula de memória que armazena um dos quatro níveis de carga diferentes. Essa é a menor unidade que você pode acessar em um nível de hardware. Então, você poderia dizer que seus "bits" realmente têm 4 estados (eles não têm , você realmente só sai dois bits em vez de um, e você só pode ler setores completos do dispositivo de qualquer maneira ... mas você poderia discuti-lo dessa maneira).
Mesmo número de células, mas o dobro da memória. Mais barato, menor, um pouco menos confiável, mas ... acima de tudo, mais barato .

Damon
fonte
Trata-se de utilizar totalmente a largura de banda disponível.
O 100BASE-TX usa apenas um par por direção, enquanto o 1000BASE-T usa 4 pares por direção (com cancelamento de eco).
user253751
-5

Ter 4 símbolos por dígito em vez de dois significa que você pode armazenar o dobro de informações em um único dígito. No entanto, à medida que aumenta a quantidade de dígitos, você pode armazenar exponencialmente mais informações:

Quaisquer n dígitos na base 2 podem codificar 2 ^ n estados, enquanto a base 4 pode codificar 4 ^ n.

marstato
fonte
6
sua declaração é: "4 símbolos / bit". Isso mostra uma falta de entendimento. São 4 estados / símbolo e, com esses 4 estados / símbolo, codificaria 2 bits.
Pieter B
4
@Kapep está errado. Ele está usando "quantidade de informação" e "pode ​​codificar N estados" de forma intercambiável, o que não está absolutamente correto. As informações são medidas em bits, não em número de estados. Dobrar bits por símbolo adiciona tanta informação quanto dobrar o número de símbolos.
user5226582
3
Você deve editar isso para esclarecer que, quando diz "4 símbolos por dígito", significa que cada local do dígito possui 4 valores possíveis (ou estados ou "símbolos"). Quando vejo a frase "4 símbolos por dígito", a primeira coisa que penso é que escrever um dígito implica escrever 4 símbolos. Enquanto você está nisso, sua resposta contém 9 palavras incorretamente capitalizados que você pode corrigir ...
Tanner Swett
2
@TannerSwett Como estamos em terra pedante, 'digit' implica 10 valores, e é por isso que é engraçado que normalmente chamamos de tecnologias que usam 'binário' digital.
21717 JimmyJames
2
(4^n) / (2^n) = 2^no que significa que você pode representar exponencialmente ( 2^nvezes) mais estados, mas isso representa apenas duas vezes ( log2(4^n) / log2(2^n) = 2n / n = 2) mais armazenamento. Lembre-se dissostorage capacity in bits = log2(number of states)
zakinster 10/10