Código Natural/Notação posicional

Termos utilizados na notação posicional de códigos. Em texto: 0125_8h.

Cadeias de bits são a forma mais simples para se registrar números ou códigos naturais, mas para o ser humano elas são muito longas e difíceis de ler. No caso dos números existe a notação posicional em base N, mais compacta que a representação binária para qualquer N>2.

A notação numérica pode ser facilmente adaptada para expressar códigos naturais, basta permitir zeros a esquerda. Exemplos:

Notação / Característica	Código	Número	Código	Número
Base 2. Binária / Ilegível	`000000010010`	10010	`1111`	1111
Base 4. Quaternaria / Melhorou!	`000102`	102	`33`	33
Base 16. Hexadecimal / Compacta	`012`	12	`f`	f

Notar o exemplo do código 000000010010₂ que manteve seus zeros a esquerda na sua representação quaternária, 000102₄. Os zeros a esquerda são importantes diferenciadores dos códigos, todavia existem restrições. Existem códigos binários que não podem ser representados nas bases numéricas usuais. Exemplos:

Base2	`0` (1 dígito)	`00` (2 dígitos)	`0000` (4 dígitos)	`010` (3 dígitos)	`1010` (4 dígitos)	`10100` (5 dígitos)	`010100` (6 dígitos)	`00010100` (8 dígitos)
Base4	`?`	`0`	`00`	`?`	`22`	`?`	`110`	`0110`
Base16	`?`	`?`	`0`	`?`	`a`	`?`	`?`	`14`

O código 010₂ não pode ser representado na base 4 pois se permitíssimos algo como "02₄" seria confundido com o binário 0010₂. Assim nas demais interrogações da base 4, apenas os binários com uma quantidade par de dígitos (2, 4 e 6) podem ser representados. As interrogações da base 16 surgem quando a quantidade de dígitos binários não é divisível por quatro — temos interrogações em 1, 2, 3, 5 ou 6 dígitos binários.

Definição

Para distinguir a notação numérica binária, por exemplo [010]₂=[10]₂, da notação posicional para códigos binários e cadeias de bits, foi convencionado o uso da base 2h, por exemplo 010_2h≠10_2h. O sufixo "h" destaca que queremos preservar a hierarquia.

Para além da base 2, outras convenções e cuidados precisam ser tomados. O conjunto $P_{k}$ dos números naturais de k bits pode ter seus elementos representados por base 2, base 3, base 4, ..., até base N, com $N\leq 2^{k}$ .

O conjunto dos códigos naturais de zero a k bits, $X_{k}=P_{k}\cup X_{k-1}$ , pode também ser representado de maneira compacta, através de uma adaptação da notação posicional numérica, nas seguintes situações:

Códigos base N: é restrita, permite apenas a representação de códigos de u bits, com $u\leq k$ e valores de u múltiplos de $log_{2}(N)$ . Os códigos são representados através de números, mapeando-se o conjunto $\bigcup P_{u}$ no conjunto dos números naturais de u bits. Esses números estão representados na base N, onde cada dígito consome c bits, com $c=log_{2}(N)$ , e a restrição dos múltiplos pode ser expressa como $u~{\bmod {c}}=0$ . É esperado que o código na base N tenha u/c dígitos, de modo que, havendo menos na representação numérica, deve-se preencher com zeros à esquerda. Formalmente, o preenchimento é a função de formatação padstart() (ex.).
Exemplo. A base 4 (c=2) permite valores de u restritos por $u~{\bmod {~}}2=0$ , portanto permite representar o conjunto de códigos com u par: $P_{0}\cup P_{2}\cup P_{4}\cup \dots \cup P_{k}$ . Quanto à notação textual, nesta Wiki distinguimos o código 007₈≠7₈ do número [007]₈=[7]₈ pelo uso da fonte e dos colchetes.
Exemplo. O código 000000111₂ tem comprimento u=9 e pode ser representado na base 8, que tem dígitos de c=3 bits. O código é tomado como número e transformado na base 8: [000000111]₂=[111]₂=[7]₈. Em seguida o número precisa ser formatado como código de $u/c=9/3=3$ dígitos, o que resulta na representação de código 007₈.
Nota. Não tem uso prático, mas matematicamente o número de zeros pode ser previsto. A quantidade v de bits do valor numérico x, $v=\lceil log_{2}(x)\rceil$ , pode ser comparada com u, indicando que são necessários $(u-v)/c$ zeros a esquerda. No exemplo x=7 e v=3, portanto são necessários $(u-v)/c=6/3=2$ zeros à esquerda de [7]₈.

Códigos base Nh: além de permitir a representação dos elementos de $P_{k}$ , permite a dos elementos de $X_{k-1}$ ; ou seja, permite a representação de todos os códigos naturais $X_{k}$ . É detalhada abaixo nas seções Base Nh e Algoritmos base h.
A base Nh também preserva a hierarquia do código natural. Na prática $N\in \{2,4,8,16\}$ por não haverem convenções para bases maiores, nem hierarquia fora das potências de dois. Ou seja Nh está limitado às bases 2h, 4h, 8h e 16h.

Outras notações: o "padding" descrito na RFC 4648, com escopo na conversão de bytes (base256) em baseN, oferece um padrão adequado para $N\in \{16,32,64\}$ , mas não para a baseNh, justamente porque, mesmo com o recurso de "padding" orientado ao tamanho arbitrário de bytes, falha em expressar códigos com tamanho arbitrário de bits.

Em particular, para N=2 as notações base 2h e base 2 são equivalentes. Convenciona-se base 2h como canônica (preferível). A equivalência decorre de $log_{2}(2)=1$ , implicando que todos os códigos naturais $X_{k}$ possuem representação base 2: $X_{k}=P_{0}\cup P_{1}\cup P_{2}\cup \dots \cup P_{k}$ .

Notações padronizadas

Alfabetos e demais convenções da notação posicional de códigos naturais. Lista completa de IDs com respectivos alfabetos-padrão para conversão de base, para as “bases potência de 2”.

O identificador é a concatenação da palavra “base” com o valor da base e o rótulo (label) do alfabeto. O número de bits por dígito é o log₂ da base. No alfabeto foram destacados os nhDigits (non-hierarchical digits) conforme notação Natural Code.

Base N

base	label	ID	bits	alphabet	Reference standard
4	js	base4js	2	`0123`	[ECMA-262]
8	js	base8js	3	`01234567`	ECMA-262
16	js	base16js	4	`0123456789abcdef`	ECMA-262 and RFC 4648/sec8
32	hex	base32hex	5	`0123456789abcdefghijklmnopqrstuv`	ECMA-262 and RFC 4648/sec7
32	ghs	base32ghs	5	`0123456789bcdefghjkmnpqrstuvwxyz`	Geohash
32	nvu	base32nvu	5	`0123456789BCDFGHJKLMNPQRSTUVWXYZ`	No-Vowels except U (near non-syllabic)
32	rfc	base32rfc	5	`ABCDEFGHIJKLMNOPQRSTUVWXYZ234567`	RFC 4648/sec6
64	url	base64url	6	`ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_`	RFC 4648/sec5
64	rfc	base64rfc	6	`ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/`	RFC 4648/sec4
All base32 here are using with leading zeros, they are valid instances of “restricted hiearchy”, base32rh.

Exemplos. Os códigos 007_10rh, 33_4h e ab12T_16h, abaixo exemplifiados em cada notação:

base ID	007, 33, ab12T `000000000111`_2h, `1111`_2h e `1010101100010010101`_2h
base4js	`000013`_4js, `33`_4js e `?`_4js
base8js	`0007`_8js, `?`_8js e `?`_8js
base16js	`007`_16js, `f`_16js e `?`_16js
base32hex	`k7`_32hex, `?`_32hex e `?`_32hex
base32ghs	`n7`_32ghs, `?`_32ghs e `?`_32ghs
base32nvu	`N7`_32nvu, `?`_32nvu e `?`_32nvu
base32rfc	`UH`_32rfc, `?`_32rfc e `?`_32rfc
base64url	`?`_64url, `?`_64url e `?`_64url
base64rfc	`?`_64rfc, `?`_64rfc e `?`_64rfc

A interrogação, "?", indica que a representação da cadeia de bits daquele tamanho não existe naquela base.

Base 32

Ver wikipedia:Base 32 e acima em Base N as variantes (base32hex, base32ghs, etc.). Para aplicações que requerem maior grau de compactação, a base 32 é a potência de 2 que se encontra ainda abaixo do limite superior. São dois limites, conforme o tipo de aplicação:

base 36 é o limite alfanumérico resiliente, onde não há confusão entre maiúsculas e minúsculas.
É o limite adotado em aplicações que envolvem interpretação ou comunicação humanas, tais como voz, chat, URLs curtas, aplicações cartoriais, placas, etc. Algumas tecnologias, como QR-Codes também se beneficiam do case-insensitive. Como 36 não é potência de 2 (portanto não é interoperável), o 32 é preferido como máximo.

base 64 é o limite alfanumérico (10 + 26*2 + 2 caracteres ASCII usuais).
É o limite para aplicações onde é permitida a diferenciação maiúsculas/minúsculas. A bsase32 seria preferível à base64 em códigos de poucos bits, onde o ganho de compactação seja notado, e a oferta de hierarquia tenha um papel importante.

Até o momento foram aceitas apenas 4 "variantes padronizadas", conforme tabela acima: base32hex, base32ghs, base32nvu e base32rfc.

Base Nh

A regra de "eliminar zeros a esquerda", que caracteriza números, deve ser eliminada quando expressamos códigos. No contexto binário os códigos são equivalentes a cadeias de bits justamente por isso. Mas tão logo desejarmos usar uma base maior, por exemplo base 4, surge um novo problema: garantir que todas as possíveis cadeias de bits serão traduzidas para a base?

Exceto pela base2h, portanto, todas as outras bases-h (4h, 8h, etc.) requerem um sistema mais sofisticados para se manterem hierárquicas, e, para que sejam compatíveis entre si, não há margem para a eleição de alfabetos alternativos.

base	label	ID	bits	alphabet (depois do espaço os nhDigits)	Reference standard
2	h	base2h	1	`01`	[ECMA-262]
4	h	base4h	2	`0123 GQ`	ECMA + nhDigits alphabet
8	h	base8h	3	`01234567 GQ HMRV`	ECMA + nhDigits alphabet
16	h	base16h	4	`0123456789abcdef GQ HMRV JKNPSTZY`	ECMA + nhDigits alphabet

Exemplos. Os códigos 007_10rh, 33_4h e ab12T_16h, abaixo exemplifiados em cada notação:

base ID	007, 33, ab12T
base2h	`000000000111`_2h, `1111`_2h e `1010101100010010101`_2h
base4h	`000013`_4h, `33`_4h e `222301022q`_4h
base8h	`0007`_8h, `7q`_8h e `526112q`_8h
base16h	`007`_16h, `33`_16h e `ab12T`_16h

Bases de interesse prático

Podemos supor que as bases com maior leque de aplicações são 2h, 4h e 16h, destacando também a base32, por ser semi-compatível com a base 4h e suprir representação mais compacta. As bases 16 e 32 também são destacadas na RFC 4648, sendo a base 16 a de uso mais amplo e consolidado.

Na discussão a seguir, para justificar a preferência por estas bases, acrescentaremos o contexto de aplicação. Focaremos no contexto da utilização dos Códigos Naturais como geocódigos, principalmente GGeohash.

A base 2 (binária) é a mais fundamental, com dígitos de 1 bit. A base 2 é fundamental nos sistemas digitais:

apenas bases N, com N sendo uma potência de 2, $N\in \{2^{2},2^{3},2^{4},...\}$ , é que terão dígitos fazendo uso integral dos bits que os representam.
Por exemplo a base 10 do sistema numérico decimal usual, requer 4 bits por dígito, descartando informação (usa valores 0 a 9 e descarta 10 a 15).

Existe um limite prático para N, tendo em vista que a função precípua de uma base N>2 é proporcionar a visualização do código para os seres humanos. Requisitos subjetivos da base N:

"quanto mais compacto melhor" (portanto os humanos desejam N o maior possível),
"a hierarquia precisa ser percebida" (portanto N não pode ser grande demais).

O limite prático, todavia, está nos meios de comunicação: o código base N precisa ser legível e não-ambíguo no meio textual, em voz, e em protocolos internet, tais como URI e Geo URI. Segundo a RFC 4648, a base64 (portanto N≤64) seria o limite superior para esse uso mais amplo.

O critério de não-ambiguidade (resiliência ao "telefone sem fio") tem um limite superior bem conhecido para o alfabeto das línguas ocidentais: 26 letras do alfabeto mais dígitos 0 a 9, resultando no máximo de 36 caracteres. As tentativas de uso da base 64 falham principalmente pela dificuldade do ser humano em distinguir maiúsculas e minúsculas. Há portanto o requisito de

N≤36

As bases mais compactas portanto ficam restritas às potências de dois menores que 36, ou seja, $N\in \{4,8,16,32\}$ . Voltando ao critério subjetivo, as bases desse conjunto, com máxima compressão, são base 16 e base 32, regulando-se uma ou outra pelo critério de "ainda expressar hierarquia".

estabelecendo um mas geocódigos binários com número ímpar de bits serão associados a "grades degeneradas", com células retangulares. Portanto buscamos base N com N≥4.

A base mais simples para a representação de geocódigos é a base 4, pois cada célula é subdividida em 4 células-filhas. Supondo uma célula-mãe identificada como "A", podemos batizar as suas filhas com sufixos base4 conforme ilustrado:

Os dígitos da base 4 ocupam 2 bits, e sua representação geométrica é sempre simétrica — se a célula de nível L0 for quadrada, as células rotuladas por geocódigos da base 4 também serão sempre quadradas.

A base 4 é essencial nesta aplicação, analisaremos agora se outras bases podem ser úteis. Tentaremos responder à pergunta
Será que outra base N, com N≠4, terá também aplicação nesse contexto?

N≠4

A base 2 (binária) é a mais fundamental, com dígitos de 1 bit,

mas geocódigos binários com número ímpar de bits serão associados a "grades degeneradas", com células retangulares. Portanto buscamos base N com N≥4.

A base 2 todavia é fundamental nos sistemas digitais: apenas bases N com N≥4 pertencendo ao conjunto das potências de 2, $N\in \{2^{2},2^{3},2^{4},...\}$ , é que terão dígitos fazendo uso integral dos bits que os representam. Por exemplo a base 10 do sistema numérico decimal usual, requer 4 bits por dígito, descartando informação (usa valores 0 a 9 e descarta 10 a 15).

Iniciamos em N=4, e daí em diante os geocódigos serão úteis se compatíveis com a base 4 e a base 2. Resumindo os requisitos que justificamos até aqui:

base N com N≥4 para ter uma representação mais compacta, e que tenha N múltiplo de 4, para que suas células resultem sempre em células quadradas. Além disso N precisa ser potência de dois.
Portanto N no conjunto {4, 8, 16, 64, …}

Para algumas aplicações, todavia, como a adoção do geocódigo como código postal, maior compressão é solicitada. A experiência com a tecnologia Geohash clássica demonstrou que, apesar de envolver grades degeneradas, nas aplicações logísticas o base 32 seria uma alternativa. Ela não chega a ser totalmente incompatível com a base 4: geocódigos base 32 com quantidade de dígitos par (2, 4, 6, etc.) são compatíveis. A ilustração abaixo mostra o "bate" entre a quantidade de bits, há compatibilidade para múltiplos de 10.

Tomando o caso concreto da grade de um país continental como Brasil, que requer 20 níveis para subdividir L0 até chegar no metro. Fica nítido pelo emparelhamento dos bits que apenas três níveis das grades base 32 e hexadecimal serão comuns: L0, L10 e L20. Abaixo a ilustração da interface para seleção de níveis, com todos e com seus filtrados.

Por fim, por garantir a representação "humanamente legível" de todas as grades, a base 16h é adotada como canônica dos geocódigos. Sua representação geométrica é ilustra abaixo.

Resumo formal matemático

Os requisitos e justificativas foram formulados de maneira axiomática, cada item representa um axioma:

$N\in \{2^{1},2^{2},2^{3},2^{4},...\}$ . Apenas potências de 2 são válidas, pois apenas elas garantem a utilização integral da informação carregada por cada dígito da base.
$N\leq 36$ é o limite superior. Queremos apenas representações alfanuméricas não-ambíguas e legiveis ao humano, válidas para qualquer protocolo ou meio de comunicação usual (voz, texto, URI, etc.).
$N=4$ é válido. A base 4 tem aplicação fundamental em GGeohash.
$N>4$ é desejado, pois queremos representações mais compactas.
Flexibilização: satisfazer apenas axioma-1 e axioma-2, deixando os demais axiomas como eventuais.
O GGeohash permite grades degeneradas, então se uma certa base N permitir a representação de ambas, grades degeneradas e não-degeneradas, será aceitável.

O axioma-5 é uma contradição, ignoremos ele para obter uma primeira conclusão racional.

Do axioma-3 e do axioma-4 concluímos que $N\in \{4^{2},4^{3},...\}=\{2^{4},2^{6},2^{8},...\}=\{16,64,256,...\}$ . As potências de 4 são válidas, conseguem satisfazer o axioma-3 e ao mesmo tempo representar valores de forma mais compacta, satisfazendo o axioma-4. Percebemos que essas potências também satisfazem o axioma-1. Resta portanto aplicar o axioma-2, resultando em $N\in \{16\}$ .

Obtemos uma solução, a base 16 é a eleita, mas esperávamos mais de uma solução (!). Voltando ao axioma-5, entendemos que a flexibilização permitiria usar $N\in \{2,4,8,16,32\}$ .

De fato, é o que foi tecnicamente possível e padronizamos: bases 2h, 4h, 8h e 16h, e a base 32. Para N=32 não temos uma "base 32h" porque as extensões "h" requerem ao todo um alfabeto de $N\times 2-2$ , o que, para N=32 resultaria em 62, excedendo o limite de 36.

Algoritmos base h

Algoritmos de reconhecimento e conversão dos códigos expressos em bases hierárquicas.

As funções de referência foram escritas em SQL, ver git.osm.codes/GGeohash/src/step03def-lib.sql.

Base2h

Cadeias de bits podem ser representadas por números binários, mas, como exposto acima, devido à eliminação dos zeros à esquerda da representação numérica, uma parte das cadeias de bits não pode ser representada por números.

Para diferenciar 001 de 1 é necessário tomar o cuidado de dizer que a sequência de bits não é um "número na base 2", mas um "código na base 2h", onde "h" é relativo a hierárquico.

Base4h

Como converter as cadeias de bits 0 e 1, de um dígito, para base4? Ou cadeias de bits como 000?

Certas traduções, de cadeias de bits para números na base 4, fazem sentido; por exemplo [00]_2h=[0]₄ e [01]_2h=[1]₄. Mas não há uma convenção conhecida para traduzir cadeias de bits de 1 bit, 3 bits, 5 bits etc. Por exemplo: [0]_2h=[?]₄ ; [1]_2h=[?]₄ ; [000]_2h=[?]₄. Ver ilustração acima.

A solução é usar um dígito falso que represente esses valores. Para evitar confusão com letras hexadecimais podemos usar "G" para representar a cadeia 0 e "Q" para representar 1. É denominado “dígito não-hierárquico” (nhDigit), pois, apesar de acomodar representação hierárquica, não é membro da hierarquia. A “base4 estendida para hierarquia” foi abreviada para “Base4h”. Nas listagens ilustrativas são apresentadas todas as representações Base4h do conjunto X₄.

Os códigos Base4h são strings com o padrão base4 usual e o nhDigit como sufixo opcional. Esta regra de sintaxe, para reconhecimento de códigos Base4h arbitrários, pode ser expressa por uma expressão regular:
/^([0123]*)([GQ]?)$/

O inverso, para traduzir da cadeia de bits com b bits, quando b é par, podemos usar a conversão base4 comum e, quando b é ímpar, concatenar o nhDigit. Dividindo (por exemplo, com Javascript) o valor binário como partes de prefixo e sufixo,
let part = bitString.match(/^((?:[01]{2,2})*)([01]*)$/)
o prefixo (part[0]) será convertido para o número base4 usual e o sufixo (part[1]), quando existir (um último bit restante), será traduzido para nhDigit por este mapa JSON: {"0": "G","1":"Q"}.

Exemplo: converter 001010010 em base4h, dividindo em partes, part[0]=00101001 dos blocos de 2 bits de início, que resultará em “0221”, e parte[1]=0 do bit restante, resultando em “G”. Concatenando os resultados das partes, “0221G”.

Base8h

...

Base16h

Esta extensão de codificação para base16 (RFC 4648, sec 8) foi inspirada na codificação Base4h. Ele usa o mesmo conceito nhDigit: uma sintaxe complementar à representação de base comum onde o último dígito pode usar um alfabeto alternativo para representar valores parciais (com menos bits) de dígitos comuns.

Podemos usar representação hexadecimal para qualquer número inteiro, mas ao controlar o comprimento de bit, podemos usar apenas comprimentos compatíveis com Base16: 4 bits, 8 bits, 12 bits, ... múltiplos de 4.

Então, como transformar em Base16 as cadeias de bits como 0, 1, 00, 01, 10, ... ?

A solução é estender uma representação hexadecimal, de maneira semelhante à anterior usada para base4h: o último dígito como um dígito falso que pode representar todos esses valores incompatíveis — portanto, usando os valores nhDigit G e Q para valores de 1 bit , e incluindo mais valores para 2 bits (4 valores) e 3 bits (8 valores). O total é 2+4+8=14 valores, eles podem ser representados pelas letras "G" a "T" ou qualquer outro conjunto de 14 letras — a tabela 3 mostra nossas escolhas.

O conjunto foi otimizado excluindo vogais ("I", "O", "U") e símbolos que podem ser facilmente confundidos entre si (como L), e excluindo "X" porque é usado como prefixo de conversão hexadecimal (por exemplo, x0123).

Tabela da representação dos códigos naturais de até 4 bits, em bases 2h, 4h, 8h e, com um dígito, 16h.

O nome desta nova representação é base16h, porque é a “base16 ordinária estendida para hierarquia”: /^([0-9a-f]*)([GHJKMNP-TVZY])?$/

O inverso, para traduzir de uma cadeia de bits com b bits, há b%4 últimos bits a serem traduzidos para um nhDigit. Dividindo (por exemplo, com Javascript) o valor como partes de prefixo e sufixo,

let part = bitString.match(/^((?:[01]{4,4})*)([01]*)$/)

o prefixo (parte[0]) será traduzido para o número hexadecimal usual, e o sufixo (parte[1]), quando existir (com 1, 2 ou 3 últimos bits), será traduzido por este "últimos bits para nhDigit" Mapa JSON:

{ "0":"G", "00":"H", "000":"J", "001":"K", 
  "01":"M", "010":"N", " 011":"P",
  "1":"Q", "10":"R", "100":"S", "101":"T", 
  "11":"V", "110":"Z", "111 ":"S"
}

A tabela ao lado resume as convenções adotadas, e demonstra que há consistência entre as bases 4h, 8h e 16h.

Exemplo: para converter 0010100101 em Base16h, divida em part[0]=00101001 de blocos de 4 bits desde o início, e part[1]=01, dos bits restantes. Converta parte[0] em hexadecimal comum (00101001 é “29”) e part[1] pela tabela JSON acima (01 é “M”), resultando em “29M”.

Encode e decode Nh

A seguir os algoritmos completos, expressos como funções linguagem PLpgSQL: "encode" codifica em base Nh, e "decode" decodifica a base Nh.

No padrão SQL:1992 a representação interna em cadeia de bits foi denominada BIT VARYING, sendo descontinuada em 2003. No PostgreSQL, todavia, o tipo de dado e seus operadores e funções foram mantidos, sendo abreviado como varbit — e nos nomes de função da biblioteca NatCod abreviada como vbit.

O "encode" é a conversão "vbit to base-h", o "decode" é a conversão "base-h to vbit". Daí os nomes de função vbit_to_baseh() e baseh_to_vbit(), com implementação completa no SQL-schema NatCode. A seguir os algoritmos simplificados.

Função simplificada de "encode bitstring", converte uma cadeia de bits em texto base-h.

CREATE FUNCTION natcod.vbit_to_baseh(
  p_val varbit,  -- input
  p_base int DEFAULT 16 -- 16 for base16h (default), 8 for base8h, 4 for base4h or 2 for base2h.
) RETURNS text AS $f$
DECLARE
    vlen int;
    pos0 int;
    ret text := '';
    blk varbit;
    bits_per_digit int;
    tr int[] := '{ {1,2,0,0}, {1,3,4,0}, {1,3,5,6} }'::int[]; -- --4h(bits,pos), 8h(bits,pos)
    tr_selected JSONb;
    trtypes JSONb := '{"2":[1,1], "4":[1,2], "8":[2,3], "16":[3,4]}'::JSONb;
    trpos int;
    baseh "char"[] := array[ -- the standards for Baseh:
      '[0:15]={G,Q,x,x,x,x,x,x,x,x,x,x,x,x,x,x}'::"char"[], --1. 1 bit in 4h,8h,16h
      '[0:15]={0,1,2,3,x,x,x,x,x,x,x,x,x,x,x,x}'::"char"[], --2. 2 bits in 4h
      '[0:15]={H,M,R,V,x,x,x,x,x,x,x,x,x,x,x,x}'::"char"[], --3. 2 bits 8h,16h
      '[0:15]={0,1,2,3,4,5,6,7,x,x,x,x,x,x,x,x}'::"char"[], --4. 3 bits in 8h
      '[0:15]={J,K,N,P,S,T,Z,Y,x,x,x,x,x,x,x,x}'::"char"[], --5. 3 bits in 16h
      '[0:15]={0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}'::"char"[]  --6. 4 bits in 16h
      -- Hexadecimals by standard alphabet of https://tools.ietf.org/html/rfc4648#section-6
    ]; -- jumpping I,O and L,U,W,X letters.
BEGIN
  vlen := bit_length(p_val);
  tr_selected := trtypes->(p_base::text);
  IF p_base=2 THEN
    RETURN $1::text; -- bit string as string
  END IF;
  bits_per_digit := (tr_selected->>1)::int;
  pos0  := (tr_selected->>0)::int;
  trpos := tr[pos0][bits_per_digit];
  FOR counter IN 1..(vlen/bits_per_digit) LOOP
      blk := substring(p_val FROM 1 FOR bits_per_digit);
      ret := ret || baseh[trpos][ varbit_to_int(blk,bits_per_digit) ];
      p_val := substring(p_val FROM bits_per_digit+1);
  END LOOP;
  vlen := bit_length(p_val);
  IF p_val!=b'' THEN
    trpos := tr[pos0][vlen];
    ret := ret || baseh[trpos][ varbit_to_int(p_val,vlen) ];
  END IF;
  RETURN ret;
END
$f$ LANGUAGE PLpgSQL IMMUTABLE;

Função geral de "decode base Nh". Converte o texto base-h para sua representação interna bitstring.

CREATE FUNCTION natcod.baseh_to_vbit(
  p_val text,  -- input (enforced lower case)
  p_base int DEFAULT 16 -- selecting base2h, base4h, base8h, or base16h.
) RETURNS varbit AS $f$
DECLARE
  tr_hdig jsonb := '{
    "G":[1,0],"Q":[1,1],
    "H":[2,0],"M":[2,1],"R":[2,2],"V":[2,3],
    "J":[3,0],"K":[3,1],"N":[3,2],"P":[3,3],
    "S":[3,4],"T":[3,5],"Z":[3,6],"Y":[3,7]
  }'::jsonb;
  tr_full jsonb := '{
    "0":0,"1":1,"2":2,"3":3,"4":4,"5":5,"6":6,"7":7,"8":8,
    "9":9,"a":10,"b":11,"c":12,"d":13,"e":14,"f":15
  }'::jsonb;
  blk text[];
  bits varbit;
  n int;
  i char;
  ret varbit;
  BEGIN
  ret = '';
  blk := regexp_match(p_val,'^([0-9a-f]*)([GHJKMNP-TVZY])?$');
  IF blk[1] >'' THEN
    FOREACH i IN ARRAY regexp_split_to_array(blk[1],'') LOOP
      ret := ret || CASE p_base
        WHEN 16 THEN (tr_full->>i)::int::bit(4)::varbit
        WHEN 8 THEN (tr_full->>i)::int::bit(3)::varbit
        WHEN 4 THEN (tr_full->>i)::int::bit(2)::varbit
        END;
    END LOOP;
  END IF;
  IF blk[2] >'' THEN
    n = (tr_hdig->blk[2]->>0)::int;
    ret := ret || CASE n
      WHEN 1 THEN (tr_hdig->blk[2]->>1)::int::bit(1)::varbit
      WHEN 2 THEN (tr_hdig->blk[2]->>1)::int::bit(2)::varbit
      WHEN 3 THEN (tr_hdig->blk[2]->>1)::int::bit(3)::varbit
      END;
  END IF;
  RETURN ret;
  END
$f$ LANGUAGE PLpgSQL IMMUTABLE;

Ilustrando em geocódigos

Geocódigos do tipo GGeohash identificam células de grades quadriláteras. Podemos imaginar, sobre um mapa geográfico, a célula-mãe de 512 km de lado, rotulada pelo ID 82. Ela pode ser subdividida recursivamente em 4 partes para manter a forma quadrada nas grades resultantes, ou ainda ser subdivida recursivamente em 2, resultando em grades quadradas e retangulares alternadamente:

Na Base 16h portanto apresenta rótulos para todos os níveis, do L0 ao L4 e seus intermediários: L0, L0.5, L1, L1.5, L2, L2.5, L3, L3.5, L4. Resulta em um sistema com 5×2-1=9 grades hierárquicas, conforme a ilustração acima. Para qualquer que seja o nível máximo LM (no exemplo L4 portanto M=4), a Base 16h resultará em um sistema completo de grades, com (M+1)×2-1 níveis.

Abaixo células L0 de cobertura base16 do Brasil, ilustrando caso concreto de grades de diferentes níveis. Elas foram rotuladas pela Curva-Z espelhada verticalmente — a orientação adotada nos eixos resulta em variantes da curva (N e И) e da sua ordenação.

Da direita para a esquerda temos:

1 célula-mãe (L0), identificada pelo código 8_16h, quadrada, com h₀=1048.58 km de lado (área de 1099511.63 km²);

2 células L0.5, filhas da 7: 7Q, 7G; retangulares, com lados h₀ × h₀/2 = 1048.58 km × 524,29 km (área de 549756 km²);

4 células L1, filhas da 6: 6H, 6M, 6R, 6V; quadradas, com lados h₀/2 = 524,29 km × 1048.58 km (área de 274878 km²);

16 células L2, filhas da 5: 50, 51, 52, 53, ..., , 5f; quadradas, com h₀/4 = 262.14 km (área de 68720 km²).

A base16h é utilizada na chamada "grade científica" do Brasil, ilustrada acima. A representação em base32 também foi adotada no Brasil, para expressar a "grade logística", que requer maior compressão (menos dígitos).

Mais especificamente, foi adotada a Base32nvu. Geometricamente, ela faz uso de um subconjunto da Grade Científica, com níveis múltiplos de dois e meio: L0, L2.5, L5, L7.5, L10, ... Não possuindo representação textual para outros níveis, portanto não é um conjunto completo. A Base32nvu garante a hierarquia apenas por reconhecer os zeros a esquerda. Devido à intercalação entre níveis inteiros e níveis-meio, alterna quadrados e retângulos: