Estou fazendo alguma transmissão de dados de um dsPIC para um PC e estou fazendo um CRC de 8 bits para cada bloco de 512 bytes para garantir que não haja erros. Com o meu código CRC ativado, recebo cerca de 33 KB / s, sem ele recebo 67 KB / s.
Quais são alguns algoritmos alternativos de detecção de erros para verificar que seriam mais rápidos?
embedded-systems
error-detection
FigBug
fonte
fonte
Respostas:
Embora possa haver opções mais rápidas que o CRC, se você usá-las, é provável que acabe sacrificando algum grau de capacidade de detecção de erros. Dependendo dos requisitos de detecção de erros, uma alternativa pode ser usar o código CRC otimizado para o seu aplicativo.
Para uma comparação do CRC com outras opções, consulte a excelente resposta de Martin Thompson .
Uma opção para ajudar nisso é o pycrc, que é uma ferramenta (escrita em python 1 ) que pode gerar código-fonte C para dezenas de combinações de modelo e algoritmo crc . Isso permite otimizar a velocidade e o tamanho do seu próprio aplicativo, selecionando e comparando diferentes combinações. 1: Requer Python 2.6 ou posterior.
Ele suporta o
crc-8
modelo , mas também suportacrc-5
,crc-16
ecrc-32
entre outros. Quanto aos algoritmos , ele suportabit-by-bit
,bit-by-bit-fast
etable-driven
.Por exemplo (baixando o arquivo):
Você pode até fazer coisas descoladas, como especificar usando pesquisas de mordidelas duplas (com uma tabela de pesquisa de 16 bytes) em vez de pesquisa de byte único, com tabela de pesquisa de 256 bytes.
Por exemplo (clonando o repositório git):
Dadas as restrições de memória e velocidade, essa opção pode ser o melhor compromisso entre velocidade e tamanho do código. A única maneira de ter certeza seria compará-lo.
O repositório pycrc git está no github , assim como seu rastreador de problemas , mas também pode ser baixado no sourceforge .
fonte
A paridade simples de um bit (basicamente XORing os dados repetidamente) é quase o mais rápido possível. Você perde muito a verificação de erros de um CRC.
No pseudocódigo:
fonte
Um artigo realmente bom comparando o desempenho de várias somas de verificação e CRCs em um contexto incorporado:
A eficácia das somas de verificação para redes incorporadas
Algumas citações das conclusões (baseadas em seus estudos de probabilidades de erro não detectadas):
Quando erros de burst dominam
Em outras aplicações
Se o custo da computação for muito restrito
(como no seu caso), use (em ordem de eficácia):
Outras citações:
e
fonte
A soma de verificação Adler deve ser suficiente para verificar distorções na transmissão. É usado pela biblioteca de compactação Zlib e foi adotado pelo Java 3D Mobile Graphics Standard para fornecer uma verificação rápida mas eficaz da integridade dos dados.
Na página da Wikipedia :
fonte
Não tenho conhecimento de nada que seja tão eficaz na detecção de erros quanto um CRC e mais rápido - se houvesse, as pessoas o usariam.
Você pode tentar uma soma de verificação simples, mas é muito menos provável detectar erros.
fonte
Bem, a própria lógica de soma de verificação é boa e as pessoas podem ajudar com algoritmos mais rápidos.
Se você deseja melhorar a velocidade do seu componente, pode ser necessário alterar sua técnica geral para separar o componente de transferência do componente de validação.
Se você tiver esses dois itens independentes (em threads diferentes), poderá obter toda a velocidade de transferência e reenviar apenas pacotes com falha.
Algoritmo seria algo como:
Isso permitirá que você transmita na velocidade mais alta possível e, se você jogar com o tamanho do pacote, poderá calcular a taxa de falhas otimizada VS, validar / reenviar a taxa.
fonte
Checksums são tradicionais
(reduzir # '+ stream)
XOR, como indicado acima, também funcionaria
(reduzir o fluxo XOR # ')
Um esquema um pouco mais elaborado (mais lento) é a verificação de paridade padrão para conexões seriais.
Nesse nível, você está trocando correção por velocidade. Estes irão ocasionalmente falhar.
No próximo nível mais sofisticado, você pode usar algumas coisas do tipo crc / hash.
Outro design seria aumentar o tamanho do bloco usado para o fluxo.
Você deve ter uma estimativa da taxa de erro real para ajustar a seleção do algoritmo e os parâmetros para o tamanho do bloco.
fonte