O Universal Product Code (UPC) é o código utilizado nos códigos de barra e consiste em um vetor
tal que
em
Mostre que um erro causado pela troca entre o segundo e terceiro dígitos no UPC
é detectado. Por outro lado, mostre que existe uma troca entre dois dígitos adjacentes neste UPC que não é detectado.
Mostre que um erro causado pela troca entre o segundo e terceiro dígitos no UPC
Passo 1
O enunciado define o UPC como o vetor
que satisfaz
Queremos mostrar que, no código
a troca entre os dígitos segundo e terceiro é detectada, mas existe outra troca de dígitos adjacentes que não é detectada.
Passo 2
Denotemos por é ímpar},\ 1,&se
é par. \end{cases}]
Se trocamos os dígitos
e
, o novo somatório difere do original por
Como
, a troca é indetectável se, e somente se,
Isto significa que apenas trocas de dígitos adjacentes cuja diferença seja
deixam
.
Passo 3
No nosso UPC,
e
. Aqui
e
, logo
Portanto a troca entre os dígitos segundo e terceiro é de fato detectada.
Passo 4
Buscamos agora um par adjacente
tal que
. Observando
nos dígitos terceiro e quarto, vemos que
,
, portanto
Como
, a mudança no somatório é
ou seja, essa troca não é detectada.
Resposta
A troca entre o segundo e o terceiro dígitos
é detectada, pois altera o somatório em
.
Já a troca entre o terceiro e o quarto dígitos não é detectada, pois altera o somatório em
.
Já a troca entre o terceiro e o quarto dígitos