Algoritmo de Verhoeff

Na edição 16 da Revista PROGRAMAR em Outubro de 2008 foi publicado o artigo Algoritmos para o Cálculo de Dígito Verificador que descreveu o cálculo de dígito verificador para códigos de identificação a partir dos métodos de módulo 10 e 11. Além dos algoritmos já apresentados existem outros mecanismos para cálculo e obtenção de dígitos verificadores, podendo-se destacar o algoritmo de Verhoeff, tema deste artigo.

O algoritmo ora apresentado foi desenvolvido por Jacobus (Koos) Verhoeff, matemático holandês para sua tese de doutorado em 1969 (GARCIA, et. al., 2007, p. 47). Verhoeff escreveu um algoritmo capaz de operacionalizar sequências de dígitos decimais de qualquer tamanho, evitando desta forma a ocorrência de erros de dados (HAMMING, 1986, p.27) e de transposição de dígitos adjacentes quando efectuados por utilizadores humanos (WAGNER & PUTTER,1989), tais como:

  • Substituir um dígito por um outro dígito. Por exemplo, invés de informar os dígitos 5678 acaba-se por informar 4678, onde o dígito que deveria ser 5 foi substituído pelo dígito 4. Este tipo de erro ocorre quando se acciona no teclado uma tecla adjacente à tecla que deveria ter sido realmente accionada. Ocorre em cerca de 60% a 90% dos casos.
  • Omissões ou adições de dígitos. Este tipo de erro ocorre normalmente por falta de atenção do utilizador. Ocorre em cerca de 10% a 20% dos casos.
  • Trocar da ordem entre dois dígitos. Por exemplo, invés de informar os dígitos 5678 acaba-se por informar 6578, onde os dígitos 56 foram trocados pelos dígitos 65. Este tipo de erro ocorre quando se escreve muito rápido em um teclado. Ocorre em cerca de 10% a 20% dos casos.

Além das formas habituais de detecção de erros que podem ser equacionadas com o algoritmo de Verhoeff, é possível também descobrir algumas formas menos comuns de erros (WAGNER & PUTTER, 1989), tais como:

  • Erros gémeos contínuos. Por exemplo, invés de informar os dígitos 1123 acaba-se por informar 7723, onde os dígitos 11 foram trocados pelos dígitos 77. Este tipo de erro pode ocorrer por distracção do utilizador na entrada da sequência de dígitos ou por ilegibilidade na escrita manual do código a ser verificado. Ocorrem em cerca de 0,5% a 1,5% dos casos.
  • Erros gémeos irregulares. Por exemplo, invés de informar os dígitos 1214 acaba-se por informa a sequência 7274, onde os dígitos 121 foram trocados pelos dígitos 727. Este tipo de erro pode ocorrer pelas mesmas razões apontadas na ocorrência de erros gémeos contínuos ou por ilegibilidade na escrita manual dos dígitos numéricos. Ocorrem em menos de 1% dos casos.
  • Transposição irregular. Por exemplo, invés de informar os dígitos 1234 acaba-se por informar a sequência 3214, onde os dígitos 123 foram transpostos de forma irregular pelos dígitos 321. Este tipo de erro pode ocorrer por distracção do utilizador. Ocorre em cerca de 0,5% a 1% dos casos.
  • Erros fonéticos. Por exemplo, invés de informar os dígitos 6-123 acaba-se por informar 3-123, onde o dígito 6 foi trocado pelo dígito 3. Este tipo de erro ocorre normalmente quando o código numérico é transmitido por voz por meio de um telefone, o interlocutor fala “seis” e o utilizador do outro lado entende “três”. Ocorre em cerca de 0,5% a 1,5% dos casos.

Os percentuais de erros apontados por Paul Putter e Neal R. Wagner basearam-se num estudo de erros com 12.000 ocorrências de erros humanos quando da utilização de códigos de identificação.

O maior questionamento encontrado a respeito do uso do algoritmo de Verhoeff é sua complexidade de implantação. Pelo fato de ser baseado em tabelas numéricas, essas tabelas necessitam ser implementadas em memória e de forma correcta. Normalmente se utiliza técnicas de uso de matrizes ou faz-se o armazenamento dos valores em uma tabela de banco de dados. Neste artigo estará sendo considerado a primeira forma de implementação.

Método Algorítmico

O método algorítmico apresentado por Verhoeff (1969) baseia-se no uso de três tabelas de valores fixos, sendo: tabela de localização do inversor, tabela do índice de inversão e tabela do dígito verificador. Há referência a essas tabelas, na Wikipédia, como: tabela de permuta, tabela de multiplicação e tabela de inversão. No entanto, essas denominações não representam seu sentido operacional, dificultando seu entendimento didáctico. Por esta razão neste artigo as referências as três tabelas obedecerá a seguinte nomenclatura:

Nomenclatura
Forma em alguns documentosForma documentada neste artigo
tabela de permutatabela de localização do inversor
tabela de multiplicaçãotabela do índice de inversão
tabela de inversãotabela do dígito verificado

A primeira tabela—tabela de localização do inversor—possui os valores dos índices que são obtidos a partir do fornecimento de um código de identificação que terá o dígito verificador conferido ou mesmo gerado e que serão usados na tabela do índice de inversão.

Tabela de localização do inversor
 0123456789
00123456789
11576283094
25803796142
38916043527
49453126870
54286573901
62793806415
77046913258

Para que esta tabela seja usada é necessário inverter-se a disposição (da esquerda para a direita) dos valores constantes do código de identificação, que serão usados como coordenadas das colunas.

Assim que o código de identificação é invertido numera-se a partir de 0 (zero) até 7 (sete) da esquerda para a direita toda a sequência de código de identificação, repetindo-se a sequência de zero a sete por toda a extensão do código de identificação não importando o seu tamanho para que desta forma tenha-se os valores das coordenadas das linhas.

A segunda tabela—tabela do índice de inversão—possui os valores de inversão de retorno para auxiliar a obtenção do dígito verificador da tabela do dígito verificador. Para que esta tabela seja utilizada é necessário ter primeiramente os valores de localização da tabela de localização do inversor.

Tabela do índice de inversão
 0123456789
00123456789
11234067895
22340178956
33401289567
44012395678
55987604321
66598710432
77659821043
88765932104
99876543210

Para uso desta tabela é necessário obter as coordenadas de linha e coluna. A coordenada de coluna da tabela do índice de inversão é obtida a partir do índice de localização seleccionado na tabela de localização do inversor. Já a coordenada de linha é obtida por meio da definição do valor de verificação.

O primeiro valor de verificação é por definição 0 (zero), os demais valores são obtidos a partir da obtenção do índice de localização e do índice verificador localizados na própria tabela.

O índice verificador obtido na tabela do índice de inversão de um dos dígitos do código de identificação torna-se o próximo valor de verificação para o próximo dígito do código de identificação. O último valor obtido como índice verificador será utilizado como índice de localização do dígito verificador na tabela do dígito verificador.

A terceira tabela—tabela do dígito verificador—apresenta os valores que serão utilizados como dígitos verificadores a partir da definição do índice verificador (que é o último valor obtido como índice verificador) extraído a partir da tabela do índice de inversão.

Tabela do dígito verificador
Índice verificador0123456789
Dígito verificador0432156789

Determinar dígito verificador

No sentido de entender o mecanismo de funcionamento do algoritmo de Verhoeff considere como código de identificação 9.234.876-7. O objectivo será estabelecer as transposições necessárias no sentido de determinar se o dígito verificador informado é correcto ou não.

Como primeira etapa de trabalho é necessário inverter a sequência do número do código de identificação excluindo-se desta inversão o dígito verificador, neste caso 7. Assim sendo, considere apenas do código de identificação fornecido o valor 9234876. Após efectuar a inversão da esquerda para à direita fica o código de identificação invertido grafado como 6784329. Em seguida acrescente o valor 0 (zero) à frente do código de identificação invertido de forma que fique assim definido 06784329.

Distribua a sequência do código de identificação invertido linearmente como sendo a informação de definição da coordenada de coluna na tabela de localização do inversor.

Para a definição da coordenada de linha relacione a partir do primeiro valor do código de identificação invertido a sequência numérica de 0 (zero) até o valor máximo de tamanho do código de identificação invertido, limitando o valor máximo da sequência em 7 (sete). Chegando-se em 7 (sete) reinicia-se a contagem a partir de (zero) se assim for necessário.

Linha01234567Sequência numérica
Coluna06784329Código de identificação invertido

Observe a definição dos valores da coordenada de coluna (código de identificação invertido) e da coordena de linha (sequência numérica de 0 até 7).

Acompanhe a extracção dos valores de localização da tabela de localização do inversor por meio da definição das cores.

A partir do momento em que se tem definido as coordenadas de linha e coluna basta obter na tabela de localização do inversor o valor de índice de localização. A sequência a seguir mostra a obtenção de cada um dos valores de localização da tabela de localização do inversor.

Valores de linha 0 e 1 com valor de coluna 0 e 6 e índice de localização obtido 0 e 3, respectivamente:

Tabela de localização do inversor
 0123456789
00123456789
11576283094
25803796142
38916043527
49453126870
54286573901
62793806415
77046913258
Tabela de localização do inversor
 0123456789
00123456789
11576283094
25803796142
38916043527
49453126870
54286573901
62793806415
77046913258

O processo continua de forma idêntica para as restantes linhas.

A partir do momento em que se possui os valores dos índices de localização basta relacionar os valores das coordenadas de linha e coluna e deixar registado os valores obtidos na tabela de localização do inversor como sendo os valores de índice de localização.

LinhaColunaÍndice de localização
000
163
271
382
441
536
629
798

A próxima etapa consiste em obter o índice verificador na tabela do índice de inversão a partir da definição das coordenadas de linha (valor de verificação) e coluna (índice de localização). Para tanto, é necessário obter os valores das coordenadas de linhas a partir da tabela do índice de inversão.

O primeiro valor de verificação a ser utilizado com o primeiro índice de verificação é por definição 0 (zero). Assim sendo, fica definido que o valor do índice verificador é por definição inicial 0 (zero), uma vez que é 0 (zero) também o índice de localização. Se for feito o posicionamento da linha 0 (zero) com a coluna 0 (zero) na tabela do índice de inversão obter-se-á o valor 0 (zero).

Linha0       Valor de verificação
Coluna03121698Índice de localização
Índice0       Índice verificador

A partir do valor 0 (zero) do índice verificador faz-se a transposição deste valor para a próxima posição livre para o valor de verificação de forma que se possa buscar na tabela de inversão o próximo valor de verificação.

Linha00      Valor de verificação
Coluna03121698Índice de localização
Índice0       Índice verificador

Neste momento têm-se o valor de verificação 0 e o índice de localização 3 que deverão se posicionados na tabela do índice de inversão a fim de obter-se o valor do índice verificador que neste caso é o valor 3, como se apresenta a seguir:

Tabela do índice de inversão
 0123456789
00123456789
11234067895
22340178956
33401289567
44012395678
55987604321
66598710432
77659821043
88765932104
99876543210

A partir desta sequência pega-se o valor de índice verificador 3 e faz-se a transposição deste valor para a próxima posição livre para o valor de verificação.

Linha003     Valor de verificação
Coluna03121698Índice de localização
Índice03      Índice verificador

O processo continua da mesma forma, até termos a tabela completamente preenchida:

Linha00341284Valor de verificação
Coluna03121698Índice de localização
Índice03412847Índice verificador

As operações anteriormente efectuadas para a extracção dos índices de inversão a título de ilustração podem ser representadas da seguinte forma:

Índice verificadorValor de verificaçãoÍndice de localização
000
303
431
142
211
826
489
748

O último valor obtido, neste caso 7, é o valor de índice verificador que será utilizado para indicar o valor do dígito verificador. Observe a tabela do dígito verificador seguinte:

Tabela do dígito verificador
Índice verificador0123456789
Dígito verificador0432156789

Note que o índice verificador 7 indica o dígito verificador 7 que é o dígito verificador do código de identificação 9.234.876-7. Neste caso, o valor obtido de dígito verificador é igual ao valor previamente informado. A obtenção de um valor diferente indica que o código de identificação está incorrecto.

Obtenção de dígito verificador

Por exemplo, o código de identificação 2468019753 necessita ter obtido seu dígito verificador. Assim sendo, deve este ser representado de forma inversa: 3579108642. Os valores invertidos serão usados como valores de índices de localização de valores na coluna da tabela índice de localização. Para tanto, acrescente o valor 0 (zero) a partir da primeira posição do código de identificação invertido de forma que o código de identificação fique expresso como: 03579108642. Desta forma, cada um dos valores que compõe o código de verificação invertido será utilizado como valor de índice de coluna da tabela de localização do inversor.

É necessário estabelecer também os valores de índices de localização de linhas da tabela de localização do inversor. Assim sendo, basta serializar o código de verificação invertido com valores de 0 (zero) até 7 (sete), repetindo-se esta sequência quantas vezes for necessária até atingir o tamanho total do código de identificação. Observe a seguir a definição das coordenadas (linha x coluna) que serão utilizadas:

Linha01234567012
Coluna03579108642

A identificação da coordenada Linha representa o valor serial de 0 a 7 do código de identificação invertido que se encontra definido acima da coordenada Coluna que é o valor do código de identificação invertido. A partir da definição dos valores de índices das coordenadas linha e coluna é possível descobrir os valores de localização na tabela de localização do inversor que serão usados como coordenadas de coluna na tabela do índice de inversão Assim sendo, observe os valores seguintes:

Obtenção do índice de localização
LinhaColunaÍndice de localização
000
136
259
375
490
512
602
785
066
142
220

Observe que os valores de índice de localização são obtidos a partir das coordenadas de linha e coluna existentes na tabela de localização do inversor.

O processo de obtenção de um índice de localização deve ser efectuado um a um para todos os valores da composição do código de verificação invertido.

Índice verificadorValor de verificaçãoÍndice de localização
000
606
269
725
770
572
852
385
936
792
770

O último valor de índice verificador obtido na tabela é o valor 7. Este valor caracteriza-se em ser o valor de índice da tabela do dígito verificador.

A partir do valor do índice verificador basta localizar o dígito verificador na tabela do dígito verificador. No caso apresentado o dígito verificador do índice verificador 7 é o valor 7. Assim sendo, o código de identificação 2468019753 possui o dígito verificador 7, podendo este código de identificação ser representado como 2468019753-7.

Função Verhoeff() em LPP

A título de ilustração e no sentido de facilitar a implementação em programação de computadores do algoritmo de Verhoeff segue o projecto de um código de função escrito em LPP (Linguagem de Projecto de Programação) com a finalidade de retornar o valor de dígito verificador de um código de identificação fornecido.

O algoritmo a seguir pode ser facilmente implementado em várias linguagens de programação, desde que respeitadas as limitações e estilos de cada uma das linguagens escolhidas.

função Verhoeff(CÓDIGO : cadeia) : inteiro

constante {definição das tabelas de Verhoeff}

  TLOCAL = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9], {tabela de localização do inversor 8 x10}
           [ 1, 5, 7, 6, 2, 8, 3, 0, 9, 4],
	   [ 5, 8, 0, 3, 7, 9, 6, 1, 4, 2],
	   [ 8, 9, 1, 6, 0, 4, 3, 5, 2, 7],
	   [ 9, 4, 5, 3, 1, 2, 6, 8, 7, 0],
	   [ 4, 2, 8, 6, 5, 7, 3, 9, 0, 1],
	   [ 2, 7, 9, 3, 8, 0, 6, 4, 1, 5],
	   [ 7, 0, 4, 6, 9, 1, 3, 2, 5, 8]

  TINVER = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9], {tabela do índice de inversão 10 x 10}
           [ 1, 2, 3, 4, 0, 6, 7, 8, 9, 5],
	   [ 2, 3, 4, 0, 1, 7, 8, 9, 5, 6],
	   [ 3, 4, 0, 1, 2, 8, 9, 5, 6, 7],
	   [ 4, 0, 1, 2, 3, 9, 5, 6, 7, 8],
	   [ 5, 9, 8, 7, 6, 0, 4, 3, 2, 1],
	   [ 6, 5, 9, 8, 7, 1, 0, 4, 3, 2],
	   [ 7, 6, 5, 9, 8, 2, 1, 0, 4, 3],
	   [ 8, 7, 6, 5, 9, 3, 2, 1, 0, 4],
	   [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

  TDIVER = [ 0, 4, 3, 2, 1, 5, 6, 7, 8, 9]{tabela do dígito verificador 1 x 10}

  variável {definição das variáveis de auxilio à obtenção do dígito verificador}
    I, POSIÇÃO : inteiro
    ÍNDLOC : inteiro {índice de localização}
    ÍNDVER : inteiro {índice verificador}
    CÓDINV : conjunto[0..Tamanho(CÓDIGO)] decadeia {código invertido}

início
  {trecho de algoritmo para inversão docódigo de identificação}
  para I de 1 até Tamanho(CÓDIGO) passo 1
  faça
    CÓDINV[I] ← CÓDIGO[Tamanho(CÓDIGO) + 1- I]
  fim_para
  
  {trecho de algoritmo para obtenção dedígito verificador}
  ÍNDVER ← 0
  para I de 0 até Tamanho(CÓDINV) – 1 passo 1
  faça
    POSIÇÃO ← I + 1
    INDLOC ← TLOCAL[POSIÇÃO – 8 * (POSIÇÃO div 8), CarParaNum(CÓDINV[I])]
    ÍNDVER ← TINVER[ÍNDVER, INDLOC]
  fim_para
  Verhoeff ← TDIVER[ÍNDVER]
fim

O algoritmo da função Verhoeff() proposto faz uso de alguns recursos que depende da disponibilidade destes nas bibliotecas da linguagem de programação em uso como as funções Tamanho() e CarParaNum(). A função Tamanho() retorna o tamanho de um string e a função CarParaNum() converte em dado numérico inteiro um dado numérico do tipo carácter fornecido.

O trecho POSIÇÃO – 8 * (POSIÇÃO div 8) permite obter-se o cálculo do resto da divisão do dividendo POSIÇÃO pelo divisor 8. Este recurso pode ser definido como mod na linguagem Pascal (POSICAO mod 8) e % nas linguagens C, C++, JavaScript, Java, ActionScript, PHP entre outras (POSICAO % 8).

Observe alguns códigos de identificação e seus dígitos verificadores obtidos a partir do algoritmo de Verhoeff: 123- 3, 321-1, 26041965-3, 1-5 e 1234567890-2.

Referências Bibliográficas

  1. GARCIA, A. C. dos S, et. al. A Matemática dos Códigos de Barras. Osasco: Centro Universitário FIEO, 2007. p. 58.
  2. HAMMING, R. Coding and Information Theory. 2nd ed. USA: Prentice-Hall, 1986. p. 272. ISBN-13: 978-0131390720.
  3. VERHOEFF, J. Error Detecting Decimal Codes. Amsterdam: The Mathematical Centre, 1969. p. 118.
  4. WAGNER, N. R. & PUTER, P. Error Detecting Decimal Digits. CACM Publisher ACM, NewYork, v. 32, issue 1, p. 106- 110. jan. 1989. ISSN: 0001-0782.

Publicado na edição 18 (PDF) da Revista PROGRAMAR.