Ter 4 estados por “bit” em vez de 2 significa o dobro do espaço de armazenamento?

36

Questão simples e direta, embora ingênua:

Ter 4 estados por "bit" em vez de 2 significa 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 ).

    
por Viziionary 10.10.2017 / 04:34
fonte

8 respostas

106

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 voltagens ou padrões magnéticos) em bits lógicos. Se um símbolo pode ter 4 estados, ele pode codificar 2 bits de informação.

Naturalmente, 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 serão cada vez mais parecidos à 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 sã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 é mais fácil para o ruído corromper meu sinal.

Existe uma lei que relaciona estes, 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 enfiar em um fio. Usar 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 olhar especificamente para armazenamento e armazenamento sozinho, pode-se olhar para Multi-Level Cells 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 diferentes de carga de um capacitor. (ou mais!)

    
por 10.10.2017 / 05:02
fonte
21

Uma célula de memória quaternária pode armazenar exatamente o máximo de informações que duas células binárias de memória:

Quaternary Binary
0          00
1          01
2          10
3          11

Então, se você tem o mesmo número de células de memória, mas elas são de quarentena, então você tem o dobro de memória. Mas se essa célula quádrupla ocupa o dobro de espaço em um chip, então não há benefício.

Ou de outra forma, se você tivesse 1 gigaquad de algum armazenamento quaterná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 deles, você sempre recebe uma palavra completa. E se no futuro alguém descobrir uma maneira de armazenar essa palavra em células físicas de 4 estados de forma mais eficiente do que em células de 2 estados, então isso seria usado, mas não seria visível fora do chip de memória, somente palavras de memória completa, que podem ter, por exemplo, 2 ^ 32 estados diferentes.

    
por 10.10.2017 / 13:09
fonte
9

Na teoria básica, sim. Na verdade, não - porque na verdade não armazenamos dados em bits (em HDDs). Cort Ammon cobre os problemas na transmissão de dados muito bem. RAM, cache e SSDs armazenam dados como bits, mas os HDs são diferentes devido à natureza do seu material físico e aos nossos esforços para incluir mais dados neles. A maioria dos dados ainda está armazenada no HDD, então vou me concentrar neles. Eu irei 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 antigas profundezas da internet porque são - em grande parte - um conhecimento verdadeiramente esquecido.

Primeiro, os discos rígidos armazenam informações com campos magnéticos na superfície dos pratos da unidade. O cabeçote de acionamento lê esses sensores detectando o fluxo da mudança nesse 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 for 50 dos mesmos segmentos em uma linha, ele não pode realmente contar que havia 50 - ele leu um pico de fluxo ao ler o primeiro segmento, depois nenhum fluxo por um tempo depois disso, e não pode controlar o tempo com precisão suficiente para ter certeza de que o campo estava inalterado por 50 segmentos.

Assim, o modelo básico (supers simplificado) é armazenar um bit como um par de campos magnéticos. O primeiro sempre seria uma mudança do segmento anterior, e o segundo seria um flip para representar 1 ou nenhum flip para representar 0. Assim, um 0 é FN (flip-null) e um 1 é FF (flip-flip). O tempo de acionamento é preciso o suficiente para reconhecer a diferença entre um pico de fluxo e dois pontos de fluxo dentro de um segmento. Esse formato é chamado de modulação de frequência. Então isso dá sinais claros, MAS significa que cada pedaço de memória requer dois espaços na unidade - isso é muito ineficiente. Portanto, nenhum disco rígido realmente tinha essa forma básica de codificação; Utilizou truques de compressão simples. O mais simples é modulação de freqüência modificada, que altera o padrão para que o flip magnético extra seja usado somente se um 0 for precedido por outro 0. Isso permite que os engenheiros coloquem quase o dobro de dados no mesmo espaço e, portanto, sejam usados no primeiros HDDs, e é o formato em disquetes. Depois disso, um sistema mais avançado chamado Run Length Limited foi desenvolvido com uma ideia 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 a cabeça leia um comprimento e colete a amostra magnética, e então compara-a a um conjunto de referência de amostras armazenadas para determinar qual delas corresponde melhor. Ele ignora todo o conceito de picos de fluxo e, em vez disso, usa a correspondência de padrões (eu simplifico demais, mas a supersimplificação 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 traduzir cada forma de onda em um conjunto de bits. Nesse sentido, os dados são realmente armazenados mais em um formato analógico do que um digital, porque o material físico pode suportar as variações graduais do analógico melhor do que os saltos repentinos do digital.

O melhor guia para isso é no link (pressione o botão Avançar algumas vezes para leia tudo isso) e existem algumas outras fontes - a maioria das pessoas que criaram grandes repositórios de conhecimento de informática que ninguém tem qualquer razão para saber. Uma fonte adicional decente (que é boa, mas não é 100% perfeita, até onde eu sei) está em link

TL; DR: Os discos do disco rígido não armazenam dados em um formato como 1 e 0; Em vez disso, eles usam processamento complexo de sinais para encaixar sinais no menor espaço possível e decodificá-lo durante a leitura. Então, eles são realmente agnósticos de base.

Eu não ficaria surpreso se o armazenamento de base 4 foi tentado em SSDs ou RAM em algum momento. Tudo depende da física e química dos materiais. Os engenheiros e cientistas vão empurrar esses materiais o mais longe que puderem, e seguirão por qualquer rota que produza os melhores resultados.

    
por 10.10.2017 / 21:21
fonte
6

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

Mas não há almoço grátis, precisamos ser capazes de distinguir esses estados. Acontece que é fácil construir portais lógicos binários e muito mais difícil construir portões 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 o pior caso de atenuação, em um sistema de quatro estados onde a atenuação significativa é esperada, você precisa adaptar seus limites à atenuação particular de seu sistema, não apenas ao pior atenuação de caixa. Na prática, isso significa que você precisa adicionar um sistema de medição de atenuação ao seu sistema de comunicação.

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

    
por 10.10.2017 / 16:24
fonte
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 , 0 ou 1 . Assim, cada porta física poderia armazenar "três" valores, em vez de "dois".

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.

Ao começar 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 da nossa capacidade de fabricar material fisicamente.) resulta que a constante e , a base do log natural (~ 2.71828), tem a melhor economia de raiz, seguida por 3, depois 2, depois 4.

Economia de radicais é quanto número você pode representar versus quantos símbolos você precisa usar para fazer isso.

Por exemplo, o número matemático três é representado como 3 na base 10, mas como 11 na base 2 (binário). A base 10 pode expressar números maiores com menos símbolos do 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 é chamada de "economia de radix" (sendo radix o número da base, por exemplo, 2 em binário ou "base 2"). A questão natural que se segue é, onde eu quero estar em termos dessa troca? Qual número devo adotar como base? Posso otimizar a troca entre poder expressivo e tamanho do conjunto de símbolos?

Se você olhar para o gráfico no artigo economia de raiz na Wikipédia, poderá comparar as economias de vários bases. No 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, então a base 2 é mais eficiente que a base 10.

Sua questão de base 4 tem uma eficiência de 1,0615, que é do mesmo tamanho que a base 2 (ou binária), então adotá-la na base 2 só te dá o mesmo tamanho de armazenamento por número, em média.

Se você está se perguntando, então 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, tendo uma economia de 1,0. Isso significa que é eficiente quanto possível. Para qualquer conjunto de números, em média, a base e dará a você o melhor tamanho de representação, dada a tabela de símbolos. É o melhor "bang for your buck".

Então, enquanto você acha que sua pergunta é talvez simples e básica, na verdade é sutilmente complexa e uma questão muito interessante a ser considerada ao projetar computadores. Se você pudesse projetar um computador discreto ideal, usar a base 4 oferece o mesmo negócio - o mesmo espaço para custo - como binário (base 2); usar a base 3, ou ternário, oferece um negócio melhor do que o binário (e os russos construíram um computador físico e funcional com a representação da base 3 nos transistores); mas idealmente, você usaria a base e. Eu não sei se alguém construiu um computador físico com base e, mas matematicamente, ele ofereceria um espaço melhor do que o binário e o ternário - na verdade, o melhor negócio entre todos os números reais.

    
por 11.10.2017 / 16:32
fonte
2

Você acredita que eu posso codificar a soma total do conhecimento humano com um único jogo?

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

Comcorrespondênciassuficientes,possodizerqualquercoisa.Maspossodizerodobrocomamesmacorrespondênciaseadicionarmaisdoissímbolos.Oquepodeparecerassim:

Duasvezesmaisinformaçõescomomesmojogo!Bem,porquenão?Bem,porqueparar?Giretodosossímbolosa45grausedobramosnovamente.30,15,assimpordiante.Logotenhosímbolossuficientesparapoderdizerqualquercoisaetudocomapenasumapartida!Umavezqueeufaçoisso,temosumproblema.Oqueessejogodiz?

Como você pode ter certeza de qual símbolo é agora? Quanto tempo você precisa ter certeza? Esse é o problema. Quanto mais símbolos eu adiciono, mais esforço você leva para diferenciá-los.

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

Se estamos falando por jogo, então com certeza. Mas, mesmo que isso não diminuísse nossa velocidade de leitura, agora estamos ocupando mais espaço no balcão da minha cozinha. É sempre algo.

    
por 12.10.2017 / 03:16
fonte
2

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

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

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

Ops ... isso não é verdade .

100 MBit ethernet transmite em dois pares de cabos a 100 MHz, enquanto o GbE transmite a 125 MHz em 4 pares de cabos.

Espere, então o GbE é realmente apenas 2 ½ vezes mais rápido que a Ethernet de 100 Mbit? Eu só recebo 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 cabo, dos quais 2 bits são usados como informação real, e o restante torna o sinal mais resiliente ao ruído. Graças a esses bits fracionários, o 1000BASE-T é capaz de descartar a codificação 8B10B também.

Então você duplicou o número de fios e aumentou ligeiramente a frequência, mas você obtém 10 vezes mais rendimento!

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

EDITAR:
Outro exemplo muito óbvio da vida real que eu esqueci completamente (desde que é óbvio demais, aparentemente!) Que você tem na frente dos seus olhos todos os dias é: pendrives USB.
Aqueles comumente 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" de fato têm 4 estados (eles não , você realmente apenas tira dois bits em vez de um, e você só pode ler setores completos do dispositivo ... mas você pode, sem dúvida, ver isso dessa maneira).
Mesmo número de células, mas o dobro da memória. Mais barato, menor, um pouco menos confiável, mas ... em primeiro lugar, mais barato .

    
por 11.10.2017 / 13:46
fonte
-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 você aumenta a quantidade de dígitos, é possível armazenar mais informações exponencialmente:

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

    
por 10.10.2017 / 10:36
fonte

Tags