Cadeia de bits: mudanças entre as edições
Sem resumo de edição |
mSem resumo de edição |
||
Linha 22: | Linha 22: | ||
O tamanho permite classificar cadeias: toda cadeia de tamanho ''k'' é elemento da "classe k", ou seja, o conjunto infinito de todas as cadeias de tamanho ''k''. | O tamanho permite classificar cadeias: toda cadeia de tamanho ''k'' é elemento da "classe k", ou seja, o conjunto infinito de todas as cadeias de tamanho ''k''. | ||
== Números naturais e cadeias 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. | Nos computadores, tradicionalmente, os números inteiros positivos são representados com zeros a esquerda para completar o número de bits desejado. | ||
Edição das 11h01min de 10 de julho 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 0001001
é equivalente a 1001
, mas se dizemos que 0001001
é uma cadeia de bits, aí essa equivalência deixa de existir.
A rigor, portanto, a cadeia de bits não pode ser vista como número natural. Uma alternativa seria a interpretação como código natural, que não afeta a integridade da cadeia.
Notação
A cadeia de bits é intrinsecamente posicional, apesar de não ter uma semântica numérica associada. Por exemplo a cadeia 0101100
é considerada diferente de 0000111
, justamente porque os zeros e uns ocupam posições diferentes em cada uma delas.
A título descritivo, para se referenciar bit a bit, convenciona-se que os bits da cadeia são indexados da direita para a esquerda, e iniciando pelo bit-zero.
PS: no PostgreSQL adota-se a convenção "da esquerda para a direita". A convenção aqui adotada é da notação posicional.
Não há necessidade de se associar a cadeia a um significado, a notação é meramente sintática, livre de semântica.
Tamanho
Toda cadeia de bits pode ter seu tamanho medido: é a quantidade de bits na cadeia. Uma cadeia de zero bits é uma cadeia vazia.
A função lenght(x) retorna a medida de tamanho da cadeia x. Exemplos: lenght(00
)=2; lenght(11
)=2; lenght(010101001
)=9.
O tamanho permite classificar cadeias: toda cadeia de tamanho k é elemento da "classe k", ou seja, o conjunto infinito de todas as cadeias de tamanho k.
Números naturais e cadeias 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.
Há um claro isomorfismo entre as cadeias de e os números naturais de zero a .
Erros e adulterações em cadeias
No computador, por tradição (ou culpa de softwares mal projetados), pode-se erroneamente forçar que uma cadeia de bits de tamanho fixo seja interpretada como um número. Com a promoção dos códigos naturais a cidadões de primera classe, esse erro pode ser evitado.
Referências
Formalizações históricas:
- 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.
Uso prático: