Cadeia de bits: mudanças entre as edições
mSem resumo de edição |
|||
Linha 11: | Linha 11: | ||
Toda cadeia de bits pode ter seu tamanho medido: é a quantidade de bits na cadeia. Uma cadeia de zero bits é uma cadeia vazia. | Toda cadeia de bits pode ter seu tamanho medido: é a quantidade de bits na cadeia. Uma cadeia de zero bits é uma cadeia vazia. | ||
Em particular um conjunto de cadeias de bits com todos elementos apresentando o mesmo tamanho ''k'', é uniforme quanto a ''k''. O conjunto <math>P_k</math> de todas as cadeias possíveis de tamanho ''k'' pode ser expresso como conjunto de todos os números naturais de zero a <math>2_k-1</math>, acrescentando-se zeros à esquerda quando seu tamanho for menor que ''k''. | Em particular um conjunto de cadeias de bits com todos elementos apresentando o mesmo tamanho ''k'', é uniforme quanto a ''k''. | ||
=== Números natuais de tamanho fixo === | |||
Nos computadores, tradicionalmente, os números inteiros positivos são representados com zeros a esquerda para completar o número de bits desejado. | |||
O conjunto <math>P_k</math> de todas as cadeias possíveis de tamanho ''k'' pode ser expresso como conjunto de todos os números naturais de zero a <math>2_k-1</math>, acrescentando-se zeros à esquerda quando seu tamanho for menor que ''k''. | |||
== Referências == | == Referências == |
Edição das 18h20min de 30 de maio de 2023
A noção de "cadeia de bits" (bit string) foi desenvolvida pela Lógica Matemática, principalmente no início dos anos 1900, e consagrada pelos trabalhos de Turing (1937) e Shannon (1948).
Ela difere de um número natural binário por permitir zeros à esquerda. Por exemplo o número natural binário 1001
é equivalente a 0001001
, mas se dizemos que 0001001
é um código, aí essa equivalência deixa de existir.
A rigor, portanto, a cadeia de bits não é um número natural mas um código natural, conforme conceituamos para OSMcodes. Implementações em https://git.osm.codes/NaturalCodes
Cadeias de tamanho fixo
Toda cadeia de bits pode ter seu tamanho medido: é a quantidade de bits na cadeia. Uma cadeia de zero bits é uma cadeia vazia.
Em particular um conjunto de cadeias de bits com todos elementos apresentando o mesmo tamanho k, é uniforme quanto a k.
Números natuais de tamanho fixo
Nos computadores, tradicionalmente, os números inteiros positivos são representados com zeros a esquerda para completar o número de bits desejado.
O conjunto de todas as cadeias possíveis de tamanho k pode ser expresso como conjunto de todos os números naturais de zero a , acrescentando-se zeros à esquerda quando seu tamanho for menor que k.
Referências
A. M. Turing (1937), “On Computable Numbers, with an Application to the Entscheidungsproblem”. urn:doi:10.1112/plms/s2-42.1.230.
C. E. Shannon (1948), “A Mathematical Theory of Communication”. urn:doi:10.1002/j.1538-7305.1948.tb01338.x.