I bit scomparsi

[axpgn]

Un agente segreto invia messaggi al centro di comando.
Ogni messaggio è una stringa di 512 caratteri, tutti zeri e uni.
Sfortunatamente il suo trasmettitore funziona male e si mangia $16$ caratteri ad ogni messaggio.
I $16$ caratteri mancanti si trovano sempre nelle stesse posizioni in ogni messaggio.
Come risultato il centro di comando riceve una sequenza di $496$ bit.
Nè l'agente nè il centro sanno dove si trovano i $16$ bit mangiati ad ogni messaggio e neppure possono sostituire il trasmettitore.
Comunque, precedentemente, si sono accordati per l'invio preliminare di $K$ messaggi di test.

Qual è il più piccolo $K$ possibile necessario per individuare le posizioni dei $16$ bit mancanti?


Cordialmente, Alex

[hydro1]

Se il messaggio fosse lungo $16$ bit e ne mancassero $n$, potrei recuperarli sempre con $4$ messaggi, nel modo seguente: prima mando il messaggio con $8$ zeri seguiti da $8$ uni. In questo modo scopro quanti bit mancano in ogni metà del messaggio. Con questa informazione, mando poi il messaggio con $4$ zeri seguiti da $4$ uni e poi di nuovo $4$ zeri seguiti da $4$ uni. Siccome so quanti bit mancano nelle due metà, ricavo quanti bit mancano in ogni quarto. Adesso mando il messaggio $0011001100110011$, così scopro quanti bit mancano in ogni ottavo di messaggio. Infine mando il messaggio $0101010101010101$ e scopro esattamente quali sono i bit mancanti.

Come faccio con $16$ bit mancanti tra $512$? Mando il messaggio fatto così: $16$ zeri seguiti da $16$ uni ripetuti $16$ volte. Così scopro in ogni blocco da $16$ quanti bit mancano. Adesso mi riporto al caso precedente: mando un messaggio che ha tutti $0$ tranne nei blocchi in cui so esserci delle mancanze, lì ci piazzo $8$ zeri seguiti da $8$ uni. Poi proseguo come sopra. In totale sono $5$ messaggi.

[axpgn]

Perfetto!

Adesso però rimane aperta una questione: come si dimostra che è il minimo possibile?

[Quinzio]

"axpgn":Perfetto!

Adesso però rimane aperta una questione: come si dimostra che è il minimo possibile?

Con 4 sequenze di test, un gruppo compatto di 16 bit che spariscono non e' rilevabile.
Le 4 sequenze trasmesse codificano i numeri da 0 a 15 a ripetizione (*), cioe':
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .......

E' ovvio che se sparisce un blocco da 16, la sequenza appare semplicemente troncata di 16 bit, quindi non si riesce a capire in che posizione sono spariti.
Quindi il minimo sono 5 sequenze di test che codificano i numeri da 0 a 31.

(*)
Se le sequenze sono scritte in verticale una di fianco all'altra, compaiono i numeri binari leggibili direttamente

0000  0
0001  1
0010  2
0011  3
0100  4
0101  5
0110  6
0111  7
1000  8
etc...

[axpgn]

Non mi è chiaro il tuo ragionamento, non capisco perché tu dia per scontato che ci siano ripetizioni o regolarità in qualsiasi sequenza che venga inviata (ce ne sono $2^512$)

[Quinzio]

"axpgn":

Non mi è chiaro il tuo ragionamento, non capisco perché tu dia per scontato che ci siano ripetizioni o regolarità in qualsiasi sequenza che venga inviata (ce ne sono $2^512$)

Infatti io parlavo delle K sequenze di test.
Nel thread, hydro ha messo la risposta corretta.
Tu gli hai risposto "benissimo", e poi 'come si dimostra che è il minimo possibile?'
Io stavo rispondendo a questa domanda, quindi sto ancora parlando delle sequenze di test.
Si dimostra che 5 e' il minimo perche' con 4 sequenze non rilevi un blocco di 16 bit mancante in alcune posizioni.
A maggior ragione 3, 2, o 1 sequenza non sono sufficienti. Ce ne vogliono 5.
Poi, per far capire meglio questo concetto, facevo vedere che le 4 sequenze (o le 5) si possono scrivere una vicino all'altra e in questo modo si possono leggere trasversalmente i numeri binari da 0 a 15, o da 0 a 31.
Con questa visualizzazione si capisce ancora meglio perche' 4 sequenze non bastano.

[axpgn]

Probabilmente non mi sono fatto capire ...

Quello che mi chiedo è come sia possibile dimostrare che 5 sequenze sono il minimo possibile, NON che quelle 5 sequenze specifiche trovate da hydro siano il minimo possibile

[Quinzio]

"axpgn":Probabilmente non mi sono fatto capire ...

Quello che mi chiedo è come sia possibile dimostrare che 5 sequenze sono il minimo possibile, NON che quelle 5 sequenze specifiche trovate da hydro siano il minimo possibile

Non credo che ci sia una qualche formula da cui esce il numero minimo.

Pero' sembra che 5 non sia il minimo K per rilevare i 16 caratteri mancanti.

La sequenza periodica il cui periodo e' fatto da:
0102301024501023010246
e' lunga 22 e quindi rileva blocchi compatti mancanti lunghi fino a 21.
Per fare quella sequenza servono le cifre da 0 a 6, quindi si puo' codificare con 3 sequenze binarie, e quindi il K minimo scende a 3.

[axpgn]

Non ho capito ...

[Quinzio]

"axpgn":Non ho capito ...

Bisogna considerare i test da fare per verificare se una sequenza e' valida, cioe' e' una sequenza che permette di scoprire uno o piu' caratteri che sono stati eliminati in una posizione qualsiasi.
L'ultima sequenza che ho proposto non va bene, e quindi si torna a quella semplice 0 1 2 3... 31 siccome la distanza minima tra due caratteri e' 32.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Credo che dovresti dimostrare che \( 4 < H(X \mid Y) \leq 5 \). Dove \( X \) è la variabile aleatoria che descrive lo scegliere \(16\) posizioni tra \(512\) (i bit mancanti) e \( Y \) è la variabile aleatoria di osservare un messaggio dopo cancellazione (le due variabili aleatorie sono dipendenti). Comunque sia \(H(X \mid Y) \) è detta entropia condizionale e descrive la quantità d'informazione necessaria per descrivere il valore di \(X\) noto il valore di \( Y \). Pertanto hai \( K \geq H(X \mid Y)\). Non ho tempo di farlo ma
\[ H(X\mid Y) = - \sum_{y \in Y} p(y) \sum_{x \in X} p(x \mid y) \log p(x \mid y) \]
Dato un messaggio prestabilito, devi cercare la probabilità \(p(y)\) di osservare \( y \in Y \). Dove \(y\) è il messaggio dopo cancellazione di \(16 \) bits scelti casualmente tra \(512\). Ad esempio supponiamo che il messaggio sia lungo 4 bits per semplicità. Se mandiamo \(0000 \) e cancelliamo le ultime due otteniamo \(y=00\). Ma anche se mandiamo \(1001 \) e cancelliamo la prima e l'ultima otteniamo \( y= 00 \). Devi descrivere qual è la probabilità di osservare \(y \).

Successivamente devi descrivere la probabilità che, osservato un \(y\) io abbia scelto di cancellare proprio certe posizioni fissate di bits, per ogni possibile combinazione di bits da cancellare ovviamente, e questo è \(p(x \mid y) \). Una volta fatto questo dovresti poter verificare che
\[ 4 < H(X \mid Y) \leq 5 \]
il che ti dice che sono necessari l'invio di \(5\) messaggi di test.