O conceito de “bit” na programação de computadores é semelhante ao conceito de “bit” na teoria da informação?

7

até hoje eu sabia que um bit é uma variável ou um espaço na memória que pode conter um valor de Um (alto) ou Zero (baixo). Este é o conceito que aprendi estudando programação de computadores, microprocessador ou barramento de dados, etc.

Mas depois de iniciar o curso sobre teoria da informação, descobri que o bit é expresso como o conteúdo informativo de um símbolo na mensagem. Isso é calculado considerando o logaritmo (base 2) do inverso da probabilidade de ocorrência do símbolo.

Esses dois conceitos são iguais? Por um lado, um bit é uma variável que pode armazenar zero ou um. Por outro lado, um bit é a incerteza associada a um dos dois símbolos com probabilidade de ocorrência de 0,5. Então, 1 bit na programação de computadores ou código ASCII significa 1 bit no conteúdo da fonte ou na teoria da informação?

Uma pequena edição: aqui está uma coisa que estou encontrando problemas para entender este tópico. Veja, na transferência de dados de alfabetos ingleses, se usarmos código ASCII, basicamente representamos cada símbolo com 8 bits. Suponha que seja 00000000 para a, 00000001 para b etc. Portanto, estamos essencialmente alocando 8 níveis de quantização para cada símbolo.

Mas quando a teoria da informação entra em jogo, levamos em consideração a probabilidade de cada símbolo. 'E' tem a frequência mais alta, onde 'Z' tem a menor. Então, o conteúdo médio das informações se reduz a 3 ou 4 bits, certo?

Meu livro diz: 'Entropia ou conteúdo médio de informação é o número médio mínimo de bits necessário para representar cada amostra sem distorção'. Portanto, neste caso, para uma transferência de dados eficiente, estamos criando no máximo quatro níveis de quantização para cada símbolo? Porque, em média, eles carregam informações no valor de 4 bits. Se é assim, não é pouco na teoria da informação o mesmo que na programação de computadores, transferência de dados ou código ASCII etc?

Você provavelmente entende que eu sou claramente um noob aqui: p

benjamin
fonte
Uma coisa a acrescentar à resposta do MBaz é que o dimensionamento do "bit" na teoria da informação é tal que o mesmo que "bits" na memória do computador. existem outras unidades de informação na Shannon IT. o que multiplica oI(m)=Clog(P(m))função. se éC=1log(2) que dimensiona a função log, I(m)está em bits.
Robert Bristow-johnson
@ robertbristow-johnson, esse é um bom argumento.
MBaz
11
A codificação de Huffman tenta alcançar o limite teórico da informação atribuindo menos bits aos símbolos frequentes. Este é um processo aproximado, pois as freqüências verdadeiras são desconhecidas e o número de bits deve permanecer um número inteiro. A codificação aritmética funciona melhor e consegue empacotar usando o número fracionário de bits por símbolos.
Yves Daoust
as frequências (digamos, dos caracteres, se for um arquivo de texto) podem ser conhecidas contando. também símbolos diferentes (com um número fracionário de bits) podem ser agrupados em uma única mensagem composta que possui quase um número inteiro de bits. mas sempre será menos eficiente que o limite teórico.
Robert Bristow-johnson

Respostas:

7

Eles não são os mesmos, mas estão relacionados. Em particular, se você olhar para uma memória de computador segurandoM bits de "computador", em que cada bit pode ser considerado aleatório e independente de todos os outros bits, e existem aproximadamente 50% de zeros, então a memória também mantém aproximadamente M bits da "teoria da informação".

Obviamente, esse geralmente não é o caso: os bits do computador geralmente são correlacionados e não uniformemente aleatórios. É por isso que eles podem ser compactados. Programas de compressores como o LZW ("codificadores de origem" na linguagem da teoria da informação) funcionam, em certo sentido, fazendo com que cada bit de computador mantenha um bit de informação.

Editado para adicionar: Este exemplo pode tornar a distinção mais clara. Considere uma fonte sem memória com duas saídas,m1=000 e m2=001, com probabilidade 0,5 para cada um. Claramente, as informações em cada mensagem são de um bit (informação), mas seu comprimento é de três bits (computador). Um codificador de origem, como o algoritmo Huffman, codificará prontamente as mensagens parac1=0 e c2=1, compactando a saída de origem. Você pode facilmente extrapolar este exemplo para uma fonte que produz texto codificado em ASCII.

Observe que, no caso das línguas escritas em geral e do inglês em particular, ninguém sabe qual é a entropia da fonte real, porque não há modelo para ela. É por isso que existem concursos para a melhor compactação de grandes corpos de texto; ninguém sabe ao certo qual é o algoritmo de compactação ideal para o inglês.

MBaz
fonte
Obrigado MBaz. Mas aqui está uma coisa que estou encontrando problemas para entender este tópico. Veja, na transferência de dados de alfabetos ingleses, se usarmos código ASCII, basicamente representamos cada símbolo com 8 bits. Suponha que seja 00000000 para a, 00000001 para b etc. Portanto, estamos essencialmente alocando 8 níveis de quantização para cada símbolo. Mas quando a teoria da informação entra em jogo, levamos em consideração a probabilidade de cada símbolo. 'E' tem a frequência mais alta, onde 'Z' tem a menor. Então, o conteúdo médio das informações se reduz a 3 ou 4 bits, certo?
Benjamin
@ Benjaminjamin, isso mesmo, e é por isso que o texto pode ser compactado tanto. Ele contém muito menos informações do que o número de bits (de computador) usados ​​para representá-los.
MBaz 14/10/2015
Olá, Postei o comentário na seção de respostas em detalhes, na verdade, pois estava ficando muito tempo. Deve ter esquecido de excluí-lo. btw, isso basicamente significa que os símbolos de texto contêm informações de 3 a 4 bits, enquanto usamos 8 bits para transferi-los, certo? Portanto, eles contêm bits ou redundância inúteis. Assim, para uma transferência de dados eficiente, podemos codificá-los usando menos bits e, assim, compactá-los. Isso significa que podemos criar níveis menores de quantização para codificá-los. Anteriormente, criamos 8 níveis de quantização, mas agora 4 níveis de quantização seriam suficientes.
Benjamin
Um nível de quantização é 1 bit de dígito binário. Portanto, agora podemos usar níveis menores de quantização ou menos bits de dígitos binários. Então, não estamos considerando bits de dígitos binários e bits de quantização como basicamente a mesma coisa? Naquela época, usamos 8 bits para transmitir um único símbolo. Mas agora sabemos que os símbolos valem apenas 4 bits de informação em média. Então, estamos enviando-os usando 4 níveis de quantização ou 4 bits de dígitos binários, porque eles carregam 4 bits de informação. Na verdade, tentei aprender um pouco sobre a codificação de Hoffman por conta própria, mas aqui é onde fiquei realmente preso.
benjamin
@ Benjaminjam, eu acho que você está no caminho certo aqui. Pense dessa maneira, quando o texto (ou qualquer arquivo ou data do computador) estiver perfeitamente compactado, cada bit do computador contenha um bit de informação.
MBaz
2

Bit é uma unidade de medida e várias quantidades são medidas em bits. Não é tão pouco assim em programação e teoria da informação que significam coisas diferentes. É que o conteúdo da memória e da informação representa quantidades conceitualmente diferentes.

Por exemplo, podemos usar a senha '' 123456 ''. Se codificado em UTF-8, requer 6 * 8 = 48 bits de memória. Para fins do mundo real, seu conteúdo de informação é de cerca de 10 bits. Bit significa o mesmo em ambos os casos, a quantidade que é medida é a que é diferente. Se você compactar a senha, a quantidade de memória necessária diminuirá, mas o conteúdo das informações não será alterado.

Uma analogia: grandezas físicas como gravidade e força eletromagnética são medidas em Newtons, mas representam diferentes tipos de interações. Você pode empiricamente ver que a unidade Newton representa a mesma idéia nos dois casos - a gravidade e a força eletromagnética podem se equilibrar (levitação magnética).

Espero que ajude :)

martinkunev
fonte
0

No barramento de dados, em teoria podemos fazer melhor do que a teoria da informação diz. Eu sei como construir um circuito que me permitirá enviar 8 bits em paralelo abaixo de 6 fios. Isso envolve um truque usando diodos e resistores pull / up que permitem o uso dos três estados de não queima de um fio digital para transmitir informações. Com 3 estados de 6 linhas, recebo 729 estados possíveis, o que me permite transportar EOF, INT, CLK e desconectado no canal principal e ainda tenho muito espaço (isso usa apenas 518 dos 729 estados).

Joshua
fonte
3
Agora que acabou de redefinir o canal e memória adicionando;)
brilhante estrelas
11
O que Trevor disse. Você assume implicitamente que o "teórico da informação" apenas usa o canal uma vez a cada duração de símbolo para enviar 1 informação de H ou L, mas se você adicionar estados, estará fazendo algo que não é o mesmo :)
Marcus Müller,