Ferramenta em Python para análise de sequências binárias com base nos postulados de Golomb: balanceamento, distribuição de sequências e autocorrelação.
Este programa realiza a análise de uma sequência binária para verificar se ela cumpre os três pressupostos de Golomb:
- Proporção entre zeros e uns: Percentagens de 0’s e 1’s dentro de uma margem aceitável.
- Frequência de subsequências de tamanhos diferentes: Blocos menores devem ocorrer mais vezes que blocos maiores.
- Distribuição equilibrada de padrões binários: Evita repetições ou “espelhamentos” indesejados.
Nota: Este projeto é apenas para fins educacionais.
-
O programa apresenta duas opções:
- Analisar uma sequência existente;
- Gerar uma nova sequência (aleatória ou que cumpra os pressupostos).
-
Para Análise:
- Recebe uma sequência binária do usuário.
- Extrai dados básicos: número de bits, blocos contínuos, frequências e tamanhos em ordem.
- Verifica cada um dos três pressupostos, acumulando informações sobre conformidade, avisos relevantes e alertas.
- Exibe um relatório final com ✔/✘ e mensagens de alerta.
-
Para Geração:
- O usuário pode gerar uma sequência binária aleatória ou que satisfaça os pressupostos de Golomb.
- O programa solicita o comprimento da sequência e os pressupostos a serem ativados.
- Tenta gerar até 5.000 sequências aleatórias que cumpram os requisitos.
- Exibe a sequência válida gerada.
-
Clone o repositório:
git clone https://github.com/Nespre/bitstream-verifier.git -
Navegue até o diretório do projeto:
cd bitstream-verifier -
Execute o script Python desejado. Exemplo:
pressuposto_golomb.py
Estes valores são internos ao programa e representam os dados usados em cada verificação:
-
num_bits (
dict): Contagens totais de bitsall: número de bits, zeros: contagem de 0’s, ones: contagem de 1’s. -
runs (
dict): Listas de blocos contínuos encontrados emall, zeros, ones. -
run_frequencies (
dict): Frequência de ocorrência de cada tamanho de bloco emall, zeros, ones. -
ordered_run_sizes (
dict): Tamanhos dos blocos, na ordem em que aparecem, emall, zeros, ones. -
postulates (
dict): Para cada pressuposto (1, 2 e 3), armazena:comply (bool), relevants (list[str]), warnings (list[str]).
Função: check_first_postulate()
Verifica se a proporção de 0's e 1's está dentro de um limite mínimo aceitável com base no comprimento da sequência.
Regras:
A percentagem mínima permitida para cada bit (0 ou 1) depende do comprimento da sequência:
≤ 10: 40.00%11–20: 0.5 * length + 35 (ex: length 16 → 43.5%)21–1000: 41.6 + 1.15 * ln(length)> 1000: 49.00%
Exemplo:
Sequência: 00001001
0's: 75.00%
1's: 25.00%
Mínimo permitido: 40.00%
→ ⚠️ Não cumpre pressuposto 1
Função: verify_frequency_runs()
Verifica se blocos menores ocorrem com mais frequência que blocos maiores.
Regras:
- Um bloco de tamanho n deve ser mais frequente que um de tamanho n+1.
- Se houver empate ou inversão de frequência, o pressuposto é violado.
- Avisos opcionais são emitidos se a diferença for pequena.
Exemplo:
Tamanhos: [1, 1, 2, 2]
Contagem: [2, 2]
→ Frequências iguais → ⚠️ Não cumpre
Verificações relacionadas a padrões, simetrias ou repetições estruturais nos blocos.
Função: verify_sizes_pattern()
Identifica padrões repetidos nos tamanhos dos blocos.
Regras:
- 2 blocos iguais consecutivos →
⚠️ Relevante - 3 blocos com 2 repetições → 🔍 Aviso
- 3 blocos com 3+ repetições →
⚠️ Relevante - 4+ blocos com 2+ repetições →
⚠️ Relevante - Padrões só de tamanho 1 são ignorados
Exemplo:
Tamanhos: [1, 2, 2, 1, 1, 2, 1, 1]
→ [2,1,1] se repete 2x → 🔍 Aviso
Função: verify_excessive_run_frequency()
Detecta se um tamanho específico ocorre em excesso, usando limites baseados em formulas.
Regras:
- Relevante se ultrapassa: max(40, 70 - 14 * log10(num_blocos))
- Aviso se ultrapassa: max(35, 60 - 14 * log10(num_blocos))
- Separado para blocos de 0 e de 1.
Exemplo:
Blocos de '1': [1,1,1,1,111]
→ 1 aparece 80% → ⚠️ Relevante
Função: verify_successively_same_size()
Verifica blocos consecutivos com mesmo tamanho.
Regras:
- Até 3 blocos de tamanho 1–2 → 🔍 Aviso
- 3–4 blocos de tamanho >2 →
⚠️ Relevante - 5+ blocos consecutivos (qualquer tamanho) →
⚠️ Relevante - 2 blocos consecutivos de tamanho ≥ 4 →
⚠️ Relevante
Exemplo:
Tamanhos: [2,2,2,2,2]
→ 5 blocos de tamanho 2 → ⚠️ Relevante
Função: verify_mirror_pattern()
Detecta padrões simétricos (espelhados) com base no centro da sequência.
Regras:
- Padrões de 5 blocos → 🔍 Aviso
- Padrões de 7+ blocos →
⚠️ Relevante - Só analisa número ímpar de blocos
Exemplo:
Blocos: [0,1,0,111,0,1,0]
→ Padrão espelhado de 7 blocos → ⚠️ Relevante
Função: verify_match_between_zeros_and_ones()
Compara padrões entre blocos de 0 e blocos de 1 em termos de padrão e proporção.
Regras (modo EXATO):
- Blocos exatamente iguais com mesma quantidade →
⚠️ Relevante - Alternância perfeita > 5 blocos →
⚠️ Relevante - 4+ blocos iguais →
⚠️ Relevante - 3 blocos iguais com soma ≥ 8 →
⚠️ Relevante - 3 blocos iguais com soma < 8 → 🔍 Aviso
Regras (modo RELATIVO):
- Qualquer padrão → 🔍 Aviso
Exemplo:
Blocos 0: [3,1,1,3,1]
Blocos 1: [1,1,3,1,1]
→ Padrão [1,1,3,1] → ⚠️ Relevante
Pressupostos de Golomb analisados:
- Proporção (✔)
- Frequência (✘) — “Blocos de tamanho 1 (5) não mais frequentes que tamanho 2 (5)”
- Padrões (✘) — “Repetição de [00 1]”
Tabela Resumo:
| Pressuposto | Status | Mensagens |
|---|---|---|
| 1 | ✔ | — |
| 2 | ✘ | Blocos de tamanho 1 não são mais frequentes |
| 3 | ✘ | Padrão [00, 1] repete-se |
Sinta-se à vontade para contribuir! Abra um pull request ou crie um issue para discutir melhorias.
Este projeto está licenciado sob a MIT License. Veja LICENSE para mais detalhes.