quinta-feira, 9 de agosto de 2012

Truque Paridade Mágica


Esse truque demonstra o conceito de checagem de erros usando bits de paridade. Infelizmente, as informações transmitidas e/ou armazenadas podem ser corrompidas ou modificadas. 

É importante saber identificar se e onde um erro ocorreu. Para isso, vamos adicionar um bit de paridade para garantir que sempre exista uma quantidade de par de uns em cada coluna e em cada linha das informações, podemos descobrir se os erros aconteceram e onde eles aconteceram.  

Observe que em cada linha e coluna, a quantidade de células pretas é  par. Depois da alteração, a quinta linha e quinta coluna ficam com uma quantidade impar de células pretas. 

Observe que nesse modelo para enviar 25 bits de informação (matriz 5x5), utilizamos 11 bits de informação de paridade, ou seja, para enviar n*n bits de informação, utilizaremos 2*n +1 bits de paridade.




Referências
Error detection and correction
http://en.wikipedia.org/wiki/Error_detection_and_correction

Competition-style programming problems for Computer Science
Unplugged activities

http://icpc.baylor.edu/ICPCWiki/attach/CLIS%202009/VoigtBellAspvall-UnpluggedProgrammingComp%20v2.pdf

Card Flip Magic
http://csunplugged.org/error-detection

Nenhum comentário: