Peso di Hamming matriciale
Salve,
cercando soluzione ad un problema di un altro post mi sono imbattuto in una proprietà che penso sia interessane, dovrebbe essere conosciuta ma non trovo riscontri in rete.
Una distanza di hamming $d()$ è definita come il numero di differenze unitarie tra due numeri, nel mio caso numeri in base $2$ si riduce ad uno XOR.
$01011\ XOR\ 10111 = 11100 = d(11100) = 3$
Si può creare con ciò una matrice dove si confrontano ogni coppia per sapere la sua distanza con tutti gli altri.
Nel caso di $n$ bit si avrà una matrice $2^nx2^n$.
es. $n=4$
si può notare essere una matrice simmetrica.
Ora la questione: dati gli indici (che corrispondono alla rappresentazione binaria stessa) è possibile trovare una formula chiusa che esprima la distanza di hamming senza calcolare la matrice?
es. $d(15,3)=$formula chiusa$=2$. Penso sia possibile, finora ho pensato che si potesse solo calcolando almeno la prima sottomatrice di ordine $2^(n-1)x2^(n-1)$ dove sarebbe triangolare superiore, diciamo per risparmiare memoria ma comunque ciò ha un costo.
Penso sia possibile fare ciò, ma non trovi riscontri validi. Che ne pensate?
cercando soluzione ad un problema di un altro post mi sono imbattuto in una proprietà che penso sia interessane, dovrebbe essere conosciuta ma non trovo riscontri in rete.
Una distanza di hamming $d()$ è definita come il numero di differenze unitarie tra due numeri, nel mio caso numeri in base $2$ si riduce ad uno XOR.
$01011\ XOR\ 10111 = 11100 = d(11100) = 3$
Si può creare con ciò una matrice dove si confrontano ogni coppia per sapere la sua distanza con tutti gli altri.
Nel caso di $n$ bit si avrà una matrice $2^nx2^n$.
es. $n=4$
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 1 0 2 1 2 1 3 2 2 1 3 2 3 2 4 3 2 1 2 0 1 2 3 1 2 2 3 1 2 3 4 2 3 3 2 1 1 0 3 2 2 1 3 2 2 1 4 3 3 2 4 1 2 2 3 0 1 1 2 2 3 3 4 1 2 2 3 5 2 1 3 2 1 0 2 1 3 2 4 3 2 1 3 2 6 2 3 1 2 1 2 0 1 3 4 2 3 2 3 1 2 7 3 2 2 1 2 1 1 0 4 3 3 2 3 2 2 1 8 1 2 2 3 2 3 3 4 0 1 1 2 1 2 2 3 9 2 1 3 2 3 2 4 3 1 0 2 1 2 1 3 2 10 2 3 1 2 3 4 2 3 1 2 0 1 2 3 1 2 11 3 2 2 1 4 3 3 2 2 1 1 0 3 2 2 1 12 2 3 3 4 1 2 2 3 1 2 2 3 0 1 1 2 13 3 2 4 3 2 1 3 2 2 1 3 2 1 0 2 1 14 3 4 2 3 2 3 1 2 2 3 1 2 1 2 0 1 15 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0
si può notare essere una matrice simmetrica.
Ora la questione: dati gli indici (che corrispondono alla rappresentazione binaria stessa) è possibile trovare una formula chiusa che esprima la distanza di hamming senza calcolare la matrice?
es. $d(15,3)=$formula chiusa$=2$. Penso sia possibile, finora ho pensato che si potesse solo calcolando almeno la prima sottomatrice di ordine $2^(n-1)x2^(n-1)$ dove sarebbe triangolare superiore, diciamo per risparmiare memoria ma comunque ciò ha un costo.
Penso sia possibile fare ciò, ma non trovi riscontri validi. Che ne pensate?
Risposte
Non so se esista una formula chiusa, ma direi che da un punto di vista computazionale si fa prima a fare uno XOR e contare i bit rimasti a 1. O no?
Ciao,
certamente utilizzare uno XOR e degli shift, che vengono eseguiti direttamente sull'architettura (con qualche linguaggio), sono le operazioni più semplici e veloci da farsi. Guarda caso quella matrice l'ho creata in questo modo
Le operazioni da fare sono più di uno (XOR + contare i valori uguali), invece avere un singolo calcolo sarebbe più interessante, diciamo una formulazione alternativa e diretta
Il mio era più un giochetto (poi era anche perchè si poteva utilizzare per risolvere il problema di quel post, per alcune proprietà secondarie di quella matrice).
Ho notato che le operazioni sono tutte uguale per le righe e colonne.
Se prendiamo tipo riga $0$: $[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]$
si vede che a corrispondenza delle potenze di $2$ c'è una formulazione ricorsiva. Con raggruppamenti e differenze sempre di $1$ rispetto alla posizione dell'unione dei gruppi precedenti.
$[0]$
$[1]$
$[1,2]$
$[1,2,2,3]$
$[1,2,2,3,2,3,3,4]$
$1*:[0]$
$2*:[0]->[1]$
$3*:[0,1]->[1,2]$
$4*:[0,1,1,2]->[1,2,2,3]$
$5*:[0,1,1,2,1,2,2,3]->[1,2,2,3,2,3,3,4]$
per il momento ho trovato questo, che ne dite, riuscite a vedere qualcosa?
PS: ho pure trovato una curiosità che mi ha un po' stupito: la cardinalità degli insiemi delle varie distanze distinte per un dato $n$, corrisponde al $k-$esimo coefficiente binomiale di $n$.
edit:
sembra che una tale matrice si chiami Hamming scheme. Sembra esserci una relazione con ciò che avevo notato, cioè con il coefficiente binomiale. La distanza di hammming sembra essere quella che viene chiamata $i$-associatività, ma non comprendo come venga relazionata in calcoli, a parte come relazione sull'ipercurbo.
"Rigel":
Non so se esista una formula chiusa, ma direi che da un punto di vista computazionale si fa prima a fare uno XOR e contare i bit rimasti a 1. O no?
certamente utilizzare uno XOR e degli shift, che vengono eseguiti direttamente sull'architettura (con qualche linguaggio), sono le operazioni più semplici e veloci da farsi. Guarda caso quella matrice l'ho creata in questo modo
Le operazioni da fare sono più di uno (XOR + contare i valori uguali), invece avere un singolo calcolo sarebbe più interessante, diciamo una formulazione alternativa e diretta
Il mio era più un giochetto (poi era anche perchè si poteva utilizzare per risolvere il problema di quel post, per alcune proprietà secondarie di quella matrice).
Ho notato che le operazioni sono tutte uguale per le righe e colonne.
Se prendiamo tipo riga $0$: $[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]$
si vede che a corrispondenza delle potenze di $2$ c'è una formulazione ricorsiva. Con raggruppamenti e differenze sempre di $1$ rispetto alla posizione dell'unione dei gruppi precedenti.
$[0]$
$[1]$
$[1,2]$
$[1,2,2,3]$
$[1,2,2,3,2,3,3,4]$
$1*:[0]$
$2*:[0]->[1]$
$3*:[0,1]->[1,2]$
$4*:[0,1,1,2]->[1,2,2,3]$
$5*:[0,1,1,2,1,2,2,3]->[1,2,2,3,2,3,3,4]$
per il momento ho trovato questo, che ne dite, riuscite a vedere qualcosa?
PS: ho pure trovato una curiosità che mi ha un po' stupito: la cardinalità degli insiemi delle varie distanze distinte per un dato $n$, corrisponde al $k-$esimo coefficiente binomiale di $n$.
edit:
sembra che una tale matrice si chiami Hamming scheme. Sembra esserci una relazione con ciò che avevo notato, cioè con il coefficiente binomiale. La distanza di hammming sembra essere quella che viene chiamata $i$-associatività, ma non comprendo come venga relazionata in calcoli, a parte come relazione sull'ipercurbo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo